mcount and latency tracing utility -v7

lib/tracing/mcount.c new file +13 -0

+	mcount_list = ops;
+	/*
+	 * For one func, simply call it directly.
+	 * For more than one func, call the chain.
+	 */
+	if (ops->next == &mcount_list_end)
+		mcount_trace_function = ops->func;
+	else
+		mcount_trace_function = mcount_list_func;
+	spin_unlock_irqrestore(&mcount_func_lock, flags);
+
+	return 0;
+}

lib/tracing/mcount.c line 72

Quoted 8 lines · Steven Rostedt

lib/tracing/mcount.c new file +8 -0

+int register_mcount_function(struct mcount_ops *ops)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&mcount_func_lock, flags);
+	ops->next = mcount_list;
+	/* must have next seen before we update the list pointer */
+	smp_wmb();

That comment does not explain which race it closes; this is esp important as there is no paired barrier to give hints.

Quoted 14 lines

lib/tracing/mcount.c new file +13 -0

+	mcount_list = ops;
+	/*
+	 * For one func, simply call it directly.
+	 * For more than one func, call the chain.
+	 */
+	if (ops->next == &mcount_list_end)
+		mcount_trace_function = ops->func;
+	else
+		mcount_trace_function = mcount_list_func;
+	spin_unlock_irqrestore(&mcount_func_lock, flags);
+
+	return 0;
+}

Quoted 14 lines · Peter Zijlstra

lib/tracing/mcount.c line 72

Quoted 8 lines · Steven Rostedt

lib/tracing/mcount.c new file +8 -0

+int register_mcount_function(struct mcount_ops *ops)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&mcount_func_lock, flags);
+	ops->next = mcount_list;
+	/* must have next seen before we update the list pointer */
+	smp_wmb();

That comment does not explain which race it closes; this is esp important as there is no paired barrier to give hints.

OK, fair enough. I'll explain it a bit more.

How's this:

/*
* We are entering ops into the mcount_list but another
* CPU might be walking that list. We need to make sure
* the ops->next pointer is valid before another CPU sees
* the ops pointer included into the mcount_list. */

Quoted 18 lines

Quoted 15 lines

lib/tracing/mcount.c new file +13 -0

+	mcount_list = ops;
+	/*
+	 * For one func, simply call it directly.
+	 * For more than one func, call the chain.
+	 */
+	if (ops->next == &mcount_list_end)
+		mcount_trace_function = ops->func;
+	else
+		mcount_trace_function = mcount_list_func;
+	spin_unlock_irqrestore(&mcount_func_lock, flags);
+
+	return 0;
+}

Paul,

Peter and I are having a discussion on craziness of archs and memory barriers. You seem to understand crazy archs pretty well, and we would like some advice. :-)

See below:

Quoted 21 lines · Steven Rostedt

Quoted 14 lines · Peter Zijlstra

lib/tracing/mcount.c line 72

Quoted 8 lines · Steven Rostedt

lib/tracing/mcount.c new file +8 -0

+int register_mcount_function(struct mcount_ops *ops)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&mcount_func_lock, flags);
+	ops->next = mcount_list;
+	/* must have next seen before we update the list pointer */
+	smp_wmb();

That comment does not explain which race it closes; this is esp important as there is no paired barrier to give hints.

OK, fair enough. I'll explain it a bit more.

Quoted 9 lines

How's this:

/*
* We are entering ops into the mcount_list but another
* CPU might be walking that list. We need to make sure
* the ops->next pointer is valid before another CPU sees
* the ops pointer included into the mcount_list. */

The above is my new comment. But Peter says that it's still not good enough and that all write memory barriers need read barriers.

Let me explain the situation here.

We have a single link list called mcount_list that is walked when more than one function is registered by mcount. Mcount is called at the start of all C functions that are not annotated with "notrace". When more than one function is registered, mcount calls a loop function that does the following:

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = mcount_list;

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = op->next;

        };
}

A registered function must already have a "func" filled, and the mcount register code takes care of "next". It is documented that the calling function should "never" change next and always expect that the func can be called after it is unregistered. That's not the issue here.

The issue is how to insert the ops into the list. I've done the following, as you can see in the code this text is inserted between.

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

The read side pair is the reading of ops to ops->next, which should imply a smp_rmb() just by the logic. But Peter tells me things like alpha is crazy enough to do better than that! Thus, I'm asking you.

Can some arch have a reader where it receives ops->next before it received ops? This seems to me to be a phsyic arch, to know where ops->next is before it knows ops!

Remember, that the ops that is being registered, is not viewable by any other CPU until mcount_list = ops. I don't see the need for a read barrier in this case. But I could very well be wrong.

Help!

-- Steve

Quoted 19 lines

Quoted 18 lines

Quoted 15 lines

lib/tracing/mcount.c new file +13 -0

+	mcount_list = ops;
+	/*
+	 * For one func, simply call it directly.
+	 * For more than one func, call the chain.
+	 */
+	if (ops->next == &mcount_list_end)
+		mcount_trace_function = ops->func;
+	else
+		mcount_trace_function = mcount_list_func;
+	spin_unlock_irqrestore(&mcount_func_lock, flags);
+
+	return 0;
+}

Quoted 5 lines · Steven Rostedt

Paul,

Peter and I are having a discussion on craziness of archs and memory barriers. You seem to understand crazy archs pretty well, and we would like some advice. :-)

Quoted 35 lines

See below:

Quoted 30 lines · Steven Rostedt

Quoted 14 lines · Peter Zijlstra

lib/tracing/mcount.c line 72

Quoted 8 lines · Steven Rostedt

lib/tracing/mcount.c new file +8 -0

+int register_mcount_function(struct mcount_ops *ops)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&mcount_func_lock, flags);
+	ops->next = mcount_list;
+	/* must have next seen before we update the list pointer */
+	smp_wmb();

That comment does not explain which race it closes; this is esp important as there is no paired barrier to give hints.

OK, fair enough. I'll explain it a bit more.

How's this:

/*
* We are entering ops into the mcount_list but another
* CPU might be walking that list. We need to make sure
* the ops->next pointer is valid before another CPU sees
* the ops pointer included into the mcount_list. */

Quoted 2 lines

The above is my new comment. But Peter says that it's still not good enough and that all write memory barriers need read barriers.

To clarify, either: full mb, rmb or read depend.

Quoted 11 lines

Let me explain the situation here.

We have a single link list called mcount_list that is walked when more than one function is registered by mcount. Mcount is called at the start of all C functions that are not annotated with "notrace". When more than one function is registered, mcount calls a loop function that does the following:

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = mcount_list;

When thinking RCU, this would be rcu_dereference and imply a read barrier.

Quoted 3 lines

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = op->next;

Same here; the rcu_dereference() would do the read depend barrier.

Quoted 11 lines

        };
}

A registered function must already have a "func" filled, and the mcount register code takes care of "next". It is documented that the calling function should "never" change next and always expect that the func can be called after it is unregistered. That's not the issue here.

The issue is how to insert the ops into the list. I've done the following, as you can see in the code this text is inserted between.

Quoted 7 lines

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

The read side pair is the reading of ops to ops->next, which should imply a smp_rmb() just by the logic. But Peter tells me things like alpha is crazy enough to do better than that! Thus, I'm asking you.

Quoted 3 lines

Can some arch have a reader where it receives ops->next before it received ops? This seems to me to be a phsyic arch, to know where ops->next is before it knows ops!

Quoted 3 lines

Remember, that the ops that is being registered, is not viewable by any other CPU until mcount_list = ops. I don't see the need for a read barrier in this case. But I could very well be wrong.

Quoted 24 lines

Help!

-- Steve

Quoted 19 lines

Quoted 18 lines

Quoted 15 lines

lib/tracing/mcount.c new file +13 -0

+	mcount_list = ops;
+	/*
+	 * For one func, simply call it directly.
+	 * For more than one func, call the chain.
+	 */
+	if (ops->next == &mcount_list_end)
+		mcount_trace_function = ops->func;
+	else
+		mcount_trace_function = mcount_list_func;
+	spin_unlock_irqrestore(&mcount_func_lock, flags);
+
+	return 0;
+}

Quoted 12 lines

Quoted 12 lines

Quoted 11 lines

OK, fair enough. I'll explain it a bit more.

How's this:

/*
* We are entering ops into the mcount_list but another
* CPU might be walking that list. We need to make sure
* the ops->next pointer is valid before another CPU sees
* the ops pointer included into the mcount_list. */

Quoted 4 lines

Quoted 2 lines

The above is my new comment. But Peter says that it's still not good enough and that all write memory barriers need read barriers.

To clarify, either: full mb, rmb or read depend.

This is true. A write barrier ensures that the writes remain ordered, but unless the reads are also ordered, the reader can still get confused. For example (assuming all variables are initially zero):

writer:

	a = 1;
	smp_wmb();  /* or smp_mb() */
	b = 1;

reader:

	tb = b;
	ta = a;

The writer will (roughly speaking) execute the assignments in order, but the reader might not. If the reader executes the assignment from "a" first, it might see tb==1&&ta==0. To prevent this, we do:

reader:

	tb = b;
	smp_rmb();  /* or smp_mb() */
	ta = a;

There are a lot of variations on this theme.

Quoted 13 lines

Quoted 9 lines

Let me explain the situation here.

We have a single link list called mcount_list that is walked when more than one function is registered by mcount. Mcount is called at the start of all C functions that are not annotated with "notrace". When more than one function is registered, mcount calls a loop function that does the following:

Quoted 3 lines

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = mcount_list;

Quoted 8 lines

When thinking RCU, this would be rcu_dereference and imply a read barrier.

Quoted 3 lines

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = op->next;

Same here; the rcu_dereference() would do the read depend barrier.

Specifically:

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = rcu_dereference(mcount_list);

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = rcu_dereference(op->next);

This assumes that you are using call_rcu(), synchronize_rcu(), or whatever to defer freeing/reuse of the ops structure.

Quoted 12 lines

Quoted 12 lines

        };
}

A registered function must already have a "func" filled, and the mcount register code takes care of "next". It is documented that the calling function should "never" change next and always expect that the func can be called after it is unregistered. That's not the issue here.

The issue is how to insert the ops into the list. I've done the following, as you can see in the code this text is inserted between.

Quoted 7 lines

Quoted 7 lines

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

The read side pair is the reading of ops to ops->next, which should imply a smp_rmb() just by the logic. But Peter tells me things like alpha is crazy enough to do better than that! Thus, I'm asking you.

Peter is correct when he says that Alpha does not necessarily respect data dependencies. See the following URL for the official story:

	http://www.openvms.compaq.com/wizard/wiz_2637.html

And I give an example hardware cache design that can result in this situation here:

	http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf

See the discussion starting with the "Why Reorder Memory Accesses?" heading in the second column of the first page.

Strange, but true. It took an Alpha architect quite some time to convince me of this back in the late 90s. ;-)

Quoted 3 lines

Quoted 3 lines

Can some arch have a reader where it receives ops->next before it received ops? This seems to me to be a phsyic arch, to know where ops->next is before it knows ops!

The trick is that the machine might have a split cache, with (say) odd-numbered cache lines being processed by one half and even-numbered lines processed by the other half. If reading CPU has one half of the cache extremely busy (e.g., processing invalidation requests from other CPUs) and the other half idle, memory misordering can happen in the receiving CPU -- if the pointer is processed by the idle half, and the pointed-to struct by the busy half, you might see the unitialized contents of the pointed-to structure. The reading CPU must execute a memory barrier to force ordering in this case.

Quoted 3 lines

Quoted 3 lines

Remember, that the ops that is being registered, is not viewable by any other CPU until mcount_list = ops. I don't see the need for a read barrier in this case. But I could very well be wrong.

And I was right there with you before my extended discussions with the aforementioned Alpha architect!

Quoted 38 lines · Paul E. McKenney

Quoted 12 lines

Quoted 12 lines

Quoted 11 lines

OK, fair enough. I'll explain it a bit more.

How's this:

/*
* We are entering ops into the mcount_list but another
* CPU might be walking that list. We need to make sure
* the ops->next pointer is valid before another CPU sees
* the ops pointer included into the mcount_list. */

Quoted 4 lines

Quoted 2 lines

The above is my new comment. But Peter says that it's still not good enough and that all write memory barriers need read barriers.

To clarify, either: full mb, rmb or read depend.

This is true. A write barrier ensures that the writes remain ordered, but unless the reads are also ordered, the reader can still get confused. For example (assuming all variables are initially zero):

writer:

	a = 1;
	smp_wmb();  /* or smp_mb() */
	b = 1;

reader:

	tb = b;
	ta = a;

The writer will (roughly speaking) execute the assignments in order, but the reader might not. If the reader executes the assignment from "a" first, it might see tb==1&&ta==0. To prevent this, we do:

reader:

Quoted 5 lines

	tb = b;
	smp_rmb();  /* or smp_mb() */
	ta = a;

There are a lot of variations on this theme.

Yep, this is all clear, but not quite what this code does.

Quoted 31 lines

Quoted 12 lines

Quoted 11 lines

Let me explain the situation here.

We have a single link list called mcount_list that is walked when more than one function is registered by mcount. Mcount is called at the start of all C functions that are not annotated with "notrace". When more than one function is registered, mcount calls a loop function that does the following:

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = mcount_list;

Quoted 8 lines

When thinking RCU, this would be rcu_dereference and imply a read barrier.

Quoted 3 lines

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = op->next;

Same here; the rcu_dereference() would do the read depend barrier.

Specifically:

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = rcu_dereference(mcount_list);

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = rcu_dereference(op->next);

Quoted 2 lines

This assumes that you are using call_rcu(), synchronize_rcu(), or whatever to defer freeing/reuse of the ops structure.

One special part of this is that the ops structure is never to be freed (this is documented). It should be a static read-mostly structure. Since it is not to be freed, I did not export the registered functions to keep modules from using it. I may later add an export that will cause the module to increment it's usage count so that it may never be freed.

There's no guarantees that prevent the func from being called after it was unregistered, nor should the users of this, ever touch the "next" pointer.

This makes things easy when you don't need to free ;-)

Quoted 49 lines

Quoted 11 lines

Quoted 11 lines

        };
}

A registered function must already have a "func" filled, and the mcount register code takes care of "next". It is documented that the calling function should "never" change next and always expect that the func can be called after it is unregistered. That's not the issue here.

The issue is how to insert the ops into the list. I've done the following, as you can see in the code this text is inserted between.

Quoted 7 lines

Quoted 7 lines

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

The read side pair is the reading of ops to ops->next, which should imply a smp_rmb() just by the logic. But Peter tells me things like alpha is crazy enough to do better than that! Thus, I'm asking you.

Peter is correct when he says that Alpha does not necessarily respect data dependencies. See the following URL for the official story:

	http://www.openvms.compaq.com/wizard/wiz_2637.html

And I give an example hardware cache design that can result in this situation here:

	http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf

See the discussion starting with the "Why Reorder Memory Accesses?" heading in the second column of the first page.

Strange, but true. It took an Alpha architect quite some time to convince me of this back in the late 90s. ;-)

Quoted 3 lines

Quoted 3 lines

Can some arch have a reader where it receives ops->next before it received ops? This seems to me to be a phsyic arch, to know where ops->next is before it knows ops!

The trick is that the machine might have a split cache, with (say) odd-numbered cache lines being processed by one half and even-numbered lines processed by the other half. If reading CPU has one half of the cache extremely busy (e.g., processing invalidation requests from other CPUs) and the other half idle, memory misordering can happen in the receiving CPU -- if the pointer is processed by the idle half, and the pointed-to struct by the busy half, you might see the unitialized contents of the pointed-to structure. The reading CPU must execute a memory barrier to force ordering in this case.

Quoted 6 lines

Quoted 3 lines

Quoted 3 lines

Remember, that the ops that is being registered, is not viewable by any other CPU until mcount_list = ops. I don't see the need for a read barrier in this case. But I could very well be wrong.

And I was right there with you before my extended discussions with the aforementioned Alpha architect!

hmm, I'm still not convinced ;-)

This is a unique situation. We don't need to worry about items being freed because there's too many races to allow that. The items are only to register functions and are not to be dynamically allocated or freed. In this situation we do not need to worry about deletions.

The smp_wmb is only for initialization of something that is about to enter the list. It is not to protect against freeing.

Specifically:

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

What this is to prevent is a new item that has next = NULL being viewable to other CPUS before next is initalized.

On another cpu we have (simplified by removing loop):

  op = mcount_list;
  op->func();
  op = op->next;
  if (op->next != NULL)
     op->func;

What we want to prevent is reading of the new ops before ops->next is set.

What you are saying is that on alpha, even though the write to ops->next has completed before mcount_list is set, we can still get a reversed order?

ops->next = mcount_list; -- in one cache line
smp_wmb();
mcount_list = ops; -- in another cache line

Even though the ops->next is completed, we can have on another cpu:

op = mcount_list; (which is the ops from above) op = op->next; -- still see the old ops->next?

I just want to understand this. I already put in the read_barrier_depends because it doesn't hurt on most archs anyway (nops).

Thanks,

-- Steve

Yep, you have dependencies, so something like the following:

initial state:

	struct foo {
		int a;
	};
	struct foo x = { 0 };
	struct foo y = { 0 };
	struct foo *global_p = &y;
	/* other variables are appropriately declared auto variables */

	/* No kmalloc() or kfree(), hence no RCU grace periods. */
	/* In the terminology of http://lwn.net/Articles/262464/, we */
	/* are doing only publish-subscribe, nothing else. */

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

reader:

	p = global_p;
	ta = p->a;

Both Alpha and aggressive compiler optimizations can result in the reader seeing the new value of the pointer (&x) but the old value of the field (0). Strange but true. The fix is as follows:

reader:

	p = global_p;
	smp_read_barrier_depends();  /* or use rcu_dereference() */
	ta = p->a;

So how can this happen? First note that if smp_read_barrier_depends() was unnecessary in this case, it would be unnecessary in all cases.

Second, let's start with the compiler. Suppose that a highly optimizing compiler notices that in almost all cases, the reader finds p==global_p. Suppose that this compiler also notices that one of the registers (say r1) almost always contains this expected value of global_p, and that cache pressure ensures that an actual load from global_p almost always generates an expensive cache miss. Such a compiler would be within its rights (as defined by the C standard) to generate code assuming that r1 already had the right value, while also generating code to validate this assumption, perhaps as follows:

	r2 = global_p;  /* high latency, other things complete meanwhile */
	ta == r1->a;
	if (r1 != r2)
		ta = r2->a;

Now consider the following sequence of events on a superscalar CPU:

	reader: r2 = global_p; /* issued, has not yet completed. */
	reader: ta = r1->a; /* which gives zero. */
	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: r2 = global_p; /* this instruction now completes */
	reader: if (r1 != r2) /* and these are equal, so we keep bad ta! */

I have great sympathy with the argument that this level of optimization is simply insane, but the fact is that there are real-world compilers that actually do this sort of thing. In addition, there are cases where the compiler might be able to figure out that a value is constant, thus breaking the dependency chain. This is most common for array references where the compiler might be able to figure out that a given array index is always zero, thus optimizing away the load and the dependency that the programmer might expect to enforce ordering. (I have an example of this down at the end.)

This sort of misordering is also done by DEC Alpha hardware, assuming split caches. This can happen if the variable x is in an odd-numbered cache line and the variable global_p is in an even-numbered cache line. In this case, the smp_wmb() affects the memory order, but only within the writing CPU. The ordering can be defeated in the reading CPU as follows:

	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: p = global_p;
	reader: ta = p->a;

		But the reader's odd-numbered cache shard is loaded
		down with many queued cacheline invalidation requests,
		so the old cached version of x.a==0 remains in the
		reader's cache, so that the reader sees ta==0.

In contrast:

	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: p = global_p;
	reader: smp_read_barrier_depends();

		The above barrier forces all cacheline invalidation
		requests that have arrived at the reading CPU to be
		processed  before any subsequent reads, including
		the pending invalidation request for the variable x.

	reader: ta = p->a;

		So ta is now guaranteed to be 1, as desired.

Quoted 41 lines

Quoted 32 lines

Quoted 13 lines

Quoted 9 lines

Let me explain the situation here.

We have a single link list called mcount_list that is walked when more than one function is registered by mcount. Mcount is called at the start of all C functions that are not annotated with "notrace". When more than one function is registered, mcount calls a loop function that does the following:

Quoted 3 lines

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = mcount_list;

Quoted 8 lines

When thinking RCU, this would be rcu_dereference and imply a read barrier.

Quoted 3 lines

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = op->next;

Same here; the rcu_dereference() would do the read depend barrier.

Specifically:

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = rcu_dereference(mcount_list);

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = rcu_dereference(op->next);

Quoted 2 lines

This assumes that you are using call_rcu(), synchronize_rcu(), or whatever to defer freeing/reuse of the ops structure.

One special part of this is that the ops structure is never to be freed (this is documented). It should be a static read-mostly structure. Since it is not to be freed, I did not export the registered functions to keep modules from using it. I may later add an export that will cause the module to increment it's usage count so that it may never be freed.

Quoted 4 lines

There's no guarantees that prevent the func from being called after it was unregistered, nor should the users of this, ever touch the "next" pointer.

This makes things easy when you don't need to free ;-)

It can indeed make things easier, but it does not help in this case. This memory-ordering problem appears even if you never free anything, as described above. Again, in the terminology laid out in the LWN article at http://lwn.net/Articles/262464/, you are doing a publish-subscribe operation, and it still must be protected.

But yes, my comment above about using call_rcu() and friends did in fact incorrectly assume that you were freeing (or otherwise re-using) the data structures.

Quoted 58 lines

Quoted 49 lines

Quoted 11 lines

Quoted 11 lines

        };
}

A registered function must already have a "func" filled, and the mcount register code takes care of "next". It is documented that the calling function should "never" change next and always expect that the func can be called after it is unregistered. That's not the issue here.

The issue is how to insert the ops into the list. I've done the following, as you can see in the code this text is inserted between.

Quoted 7 lines

Quoted 7 lines

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

The read side pair is the reading of ops to ops->next, which should imply a smp_rmb() just by the logic. But Peter tells me things like alpha is crazy enough to do better than that! Thus, I'm asking you.

Peter is correct when he says that Alpha does not necessarily respect data dependencies. See the following URL for the official story:

	http://www.openvms.compaq.com/wizard/wiz_2637.html

And I give an example hardware cache design that can result in this situation here:

	http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf

See the discussion starting with the "Why Reorder Memory Accesses?" heading in the second column of the first page.

Strange, but true. It took an Alpha architect quite some time to convince me of this back in the late 90s. ;-)

Quoted 3 lines

Quoted 3 lines

Can some arch have a reader where it receives ops->next before it received ops? This seems to me to be a phsyic arch, to know where ops->next is before it knows ops!

The trick is that the machine might have a split cache, with (say) odd-numbered cache lines being processed by one half and even-numbered lines processed by the other half. If reading CPU has one half of the cache extremely busy (e.g., processing invalidation requests from other CPUs) and the other half idle, memory misordering can happen in the receiving CPU -- if the pointer is processed by the idle half, and the pointed-to struct by the busy half, you might see the unitialized contents of the pointed-to structure. The reading CPU must execute a memory barrier to force ordering in this case.

Quoted 6 lines

Quoted 3 lines

Quoted 3 lines

Remember, that the ops that is being registered, is not viewable by any other CPU until mcount_list = ops. I don't see the need for a read barrier in this case. But I could very well be wrong.

And I was right there with you before my extended discussions with the aforementioned Alpha architect!

hmm, I'm still not convinced ;-)

Quoted 7 lines

This is a unique situation. We don't need to worry about items being freed because there's too many races to allow that. The items are only to register functions and are not to be dynamically allocated or freed. In this situation we do not need to worry about deletions.

The smp_wmb is only for initialization of something that is about to enter the list. It is not to protect against freeing.

Similarly, the smp_read_barrier_depends() is only for initialization of something that is about to enter the list. As with the smp_wmb() primitive, smp_read_barrier_depends() also is not to protect against freeing. Instead, it is rcu_read_lock() and rcu_read_unlock() that protect against freeing.

Quoted 8 lines

Specifically:

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

What this is to prevent is a new item that has next = NULL being viewable to other CPUS before next is initalized.

Were it not for aggressive compiler optimizations and DEC Alpha, you would be correct. What this instead does is to do the writer's part of the job of preventing such new items from being visible to other CPUs before ->next is initialized. These other CPUs must do their part as well, and that part is smp_read_barrier_depends() -- or rcu_dereference(), whichever is most appropriate.

Quoted 10 lines

On another cpu we have (simplified by removing loop):

  op = mcount_list;
  op->func();
  op = op->next;
  if (op->next != NULL)
     op->func;

What we want to prevent is reading of the new ops before ops->next is set.

Understood.

Quoted 3 lines

What you are saying is that on alpha, even though the write to ops->next has completed before mcount_list is set, we can still get a reversed order?

That is exactly what I am saying. In addition, I am saying that aggressive compiler optimizations can have this same effect, even on non-Alpha CPUs.

Quoted 8 lines

ops->next = mcount_list; -- in one cache line
smp_wmb();
mcount_list = ops; -- in another cache line

Even though the ops->next is completed, we can have on another cpu:

op = mcount_list; (which is the ops from above) op = op->next; -- still see the old ops->next?

Yes, this bizarre sequence of events really can happen. The fix is to do the following:

op = mcount_list; (which is the ops from above) smp_read_barrier_depends();
op = op->next; -- no longer see the old ops->next

Quoted 2 lines

I just want to understand this. I already put in the read_barrier_depends because it doesn't hurt on most archs anyway (nops).

Very good!!!

And here is the example using array indexes.

initial state:

	struct foo {
		int a;
	};
	struct foo x[ARRAY_SIZE] = { 0 };
	struct foo *global_p = &x[0];
	/* other variables are appropriately declared auto variables */

	/* No kmalloc() or kfree(), hence no RCU grace periods. */
	/* In the terminology of http://lwn.net/Articles/262464/, we */
	/* are doing only publish-subscribe, nothing else. */

writer:

	x[cur_idx].a = 1;
	smp_wmb();  /* or smp_mb() */
	global_idx = cur_idx;

reader:

	i = global_idx;
	ta = x[i].a

Suppose we have ARRAY_SIZE of 1. Then the standard states that the results of indexing x[] with a non-zero index are undefined. Since they are undefined, the compiler is within its rights to assume that the index will always be zero, so that the reader code would be as follows:

reader:

	ta = x[0].a

No dependency, no ordering. So this totally reasonable generated code could see the pre-initialized value of field a. The job of both smp_read_barrier_depends() and rcu_dereference() is to tell both the CPU and the compiler that such assumptions are ill-advised.

Hi Paul,

First I want to say, "Thank you", for taking the time to explain this in considerable detail. But I still have some minor questions.

(Even though you already convinced me, but I still want full
understanding ;-)

Quoted 56 lines

Yep, you have dependencies, so something like the following:

initial state:

	struct foo {
		int a;
	};
	struct foo x = { 0 };
	struct foo y = { 0 };
	struct foo *global_p = &y;
	/* other variables are appropriately declared auto variables */

	/* No kmalloc() or kfree(), hence no RCU grace periods. */
	/* In the terminology of http://lwn.net/Articles/262464/, we */
	/* are doing only publish-subscribe, nothing else. */

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

reader:

	p = global_p;
	ta = p->a;

Both Alpha and aggressive compiler optimizations can result in the reader seeing the new value of the pointer (&x) but the old value of the field (0). Strange but true. The fix is as follows:

reader:

	p = global_p;
	smp_read_barrier_depends();  /* or use rcu_dereference() */
	ta = p->a;

So how can this happen? First note that if smp_read_barrier_depends() was unnecessary in this case, it would be unnecessary in all cases.

Second, let's start with the compiler. Suppose that a highly optimizing compiler notices that in almost all cases, the reader finds p==global_p. Suppose that this compiler also notices that one of the registers (say r1) almost always contains this expected value of global_p, and that cache pressure ensures that an actual load from global_p almost always generates an expensive cache miss. Such a compiler would be within its rights (as defined by the C standard) to generate code assuming that r1 already had the right value, while also generating code to validate this assumption, perhaps as follows:

	r2 = global_p;  /* high latency, other things complete meanwhile */
	ta == r1->a;
	if (r1 != r2)
		ta = r2->a;

Quoted 1 line

Now consider the following sequence of events on a superscalar CPU:

I think you missed one step here (causing my confusion). I don't want to assume so I'll try to put in the missing step:

writer: r1 = p; /* happens to use r1 to store parameter p */

Quoted 7 lines

	reader: r2 = global_p; /* issued, has not yet completed. */
	reader: ta = r1->a; /* which gives zero. */
	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: r2 = global_p; /* this instruction now completes */
	reader: if (r1 != r2) /* and these are equal, so we keep bad ta! */

Is that the case?

Quoted 41 lines

I have great sympathy with the argument that this level of optimization is simply insane, but the fact is that there are real-world compilers that actually do this sort of thing. In addition, there are cases where the compiler might be able to figure out that a value is constant, thus breaking the dependency chain. This is most common for array references where the compiler might be able to figure out that a given array index is always zero, thus optimizing away the load and the dependency that the programmer might expect to enforce ordering. (I have an example of this down at the end.)

This sort of misordering is also done by DEC Alpha hardware, assuming split caches. This can happen if the variable x is in an odd-numbered cache line and the variable global_p is in an even-numbered cache line. In this case, the smp_wmb() affects the memory order, but only within the writing CPU. The ordering can be defeated in the reading CPU as follows:

	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: p = global_p;
	reader: ta = p->a;

		But the reader's odd-numbered cache shard is loaded
		down with many queued cacheline invalidation requests,
		so the old cached version of x.a==0 remains in the
		reader's cache, so that the reader sees ta==0.

In contrast:

	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: p = global_p;
	reader: smp_read_barrier_depends();

		The above barrier forces all cacheline invalidation
		requests that have arrived at the reading CPU to be
		processed  before any subsequent reads, including
		the pending invalidation request for the variable x.

Quoted 3 lines

	reader: ta = p->a;

		So ta is now guaranteed to be 1, as desired.

Thanks, this is starting to clear things up for me (And scare me away from Alpha's)

Quoted 136 lines

Quoted 40 lines

Quoted 31 lines

Quoted 12 lines

Quoted 11 lines

Let me explain the situation here.

We have a single link list called mcount_list that is walked when more than one function is registered by mcount. Mcount is called at the start of all C functions that are not annotated with "notrace". When more than one function is registered, mcount calls a loop function that does the following:

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = mcount_list;

Quoted 8 lines

When thinking RCU, this would be rcu_dereference and imply a read barrier.

Quoted 3 lines

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = op->next;

Same here; the rcu_dereference() would do the read depend barrier.

Specifically:

notrace void mcount_list_func(unsigned long ip, unsigned long parent_ip)

{
        struct mcount_ops *op = rcu_dereference(mcount_list);

        while (op != &mcount_list_end) {
                op->func(ip, parent_ip);
                op = rcu_dereference(op->next);

Quoted 2 lines

This assumes that you are using call_rcu(), synchronize_rcu(), or whatever to defer freeing/reuse of the ops structure.

One special part of this is that the ops structure is never to be freed (this is documented). It should be a static read-mostly structure. Since it is not to be freed, I did not export the registered functions to keep modules from using it. I may later add an export that will cause the module to increment it's usage count so that it may never be freed.

Quoted 4 lines

There's no guarantees that prevent the func from being called after it was unregistered, nor should the users of this, ever touch the "next" pointer.

This makes things easy when you don't need to free ;-)

It can indeed make things easier, but it does not help in this case. This memory-ordering problem appears even if you never free anything, as described above. Again, in the terminology laid out in the LWN article at http://lwn.net/Articles/262464/, you are doing a publish-subscribe operation, and it still must be protected.

But yes, my comment above about using call_rcu() and friends did in fact incorrectly assume that you were freeing (or otherwise re-using) the data structures.

Quoted 58 lines

Quoted 49 lines

Quoted 11 lines

Quoted 11 lines

        };
}

A registered function must already have a "func" filled, and the mcount register code takes care of "next". It is documented that the calling function should "never" change next and always expect that the func can be called after it is unregistered. That's not the issue here.

The issue is how to insert the ops into the list. I've done the following, as you can see in the code this text is inserted between.

Quoted 7 lines

Quoted 7 lines

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

The read side pair is the reading of ops to ops->next, which should imply a smp_rmb() just by the logic. But Peter tells me things like alpha is crazy enough to do better than that! Thus, I'm asking you.

Peter is correct when he says that Alpha does not necessarily respect data dependencies. See the following URL for the official story:

	http://www.openvms.compaq.com/wizard/wiz_2637.html

And I give an example hardware cache design that can result in this situation here:

	http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf

See the discussion starting with the "Why Reorder Memory Accesses?" heading in the second column of the first page.

Strange, but true. It took an Alpha architect quite some time to convince me of this back in the late 90s. ;-)

Quoted 3 lines

Quoted 3 lines

Can some arch have a reader where it receives ops->next before it received ops? This seems to me to be a phsyic arch, to know where ops->next is before it knows ops!

The trick is that the machine might have a split cache, with (say) odd-numbered cache lines being processed by one half and even-numbered lines processed by the other half. If reading CPU has one half of the cache extremely busy (e.g., processing invalidation requests from other CPUs) and the other half idle, memory misordering can happen in the receiving CPU -- if the pointer is processed by the idle half, and the pointed-to struct by the busy half, you might see the unitialized contents of the pointed-to structure. The reading CPU must execute a memory barrier to force ordering in this case.

Quoted 6 lines

Quoted 3 lines

Quoted 3 lines

Remember, that the ops that is being registered, is not viewable by any other CPU until mcount_list = ops. I don't see the need for a read barrier in this case. But I could very well be wrong.

And I was right there with you before my extended discussions with the aforementioned Alpha architect!

hmm, I'm still not convinced ;-)

Quoted 7 lines

This is a unique situation. We don't need to worry about items being freed because there's too many races to allow that. The items are only to register functions and are not to be dynamically allocated or freed. In this situation we do not need to worry about deletions.

The smp_wmb is only for initialization of something that is about to enter the list. It is not to protect against freeing.

Similarly, the smp_read_barrier_depends() is only for initialization of something that is about to enter the list. As with the smp_wmb() primitive, smp_read_barrier_depends() also is not to protect against freeing. Instead, it is rcu_read_lock() and rcu_read_unlock() that protect against freeing.

Quoted 8 lines

Specifically:

   ops->next = mcount_list;
   smp_wmb();
   mcount_list = ops;

What this is to prevent is a new item that has next = NULL being viewable to other CPUS before next is initalized.

Quoted 6 lines

Were it not for aggressive compiler optimizations and DEC Alpha, you would be correct. What this instead does is to do the writer's part of the job of preventing such new items from being visible to other CPUs before ->next is initialized. These other CPUs must do their part as well, and that part is smp_read_barrier_depends() -- or rcu_dereference(), whichever is most appropriate.

Since the code doesn't use RCU, I'll keep with the smp_read_barrier_depends().

Quoted 73 lines

Quoted 10 lines

On another cpu we have (simplified by removing loop):

  op = mcount_list;
  op->func();
  op = op->next;
  if (op->next != NULL)
     op->func;

What we want to prevent is reading of the new ops before ops->next is set.

Understood.

Quoted 3 lines

What you are saying is that on alpha, even though the write to ops->next has completed before mcount_list is set, we can still get a reversed order?

That is exactly what I am saying. In addition, I am saying that aggressive compiler optimizations can have this same effect, even on non-Alpha CPUs.

Quoted 8 lines

ops->next = mcount_list; -- in one cache line
smp_wmb();
mcount_list = ops; -- in another cache line

Even though the ops->next is completed, we can have on another cpu:

op = mcount_list; (which is the ops from above) op = op->next; -- still see the old ops->next?

Yes, this bizarre sequence of events really can happen. The fix is to do the following:

op = mcount_list; (which is the ops from above) smp_read_barrier_depends();
op = op->next; -- no longer see the old ops->next

Quoted 2 lines

I just want to understand this. I already put in the read_barrier_depends because it doesn't hurt on most archs anyway (nops).

Very good!!!

And here is the example using array indexes.

initial state:

	struct foo {
		int a;
	};
	struct foo x[ARRAY_SIZE] = { 0 };
	struct foo *global_p = &x[0];
	/* other variables are appropriately declared auto variables */

	/* No kmalloc() or kfree(), hence no RCU grace periods. */
	/* In the terminology of http://lwn.net/Articles/262464/, we */
	/* are doing only publish-subscribe, nothing else. */

writer:

	x[cur_idx].a = 1;
	smp_wmb();  /* or smp_mb() */
	global_idx = cur_idx;

reader:

	i = global_idx;
	ta = x[i].a

Suppose we have ARRAY_SIZE of 1. Then the standard states that the results of indexing x[] with a non-zero index are undefined. Since they are undefined, the compiler is within its rights to assume that the index will always be zero, so that the reader code would be as follows:

Quoted 9 lines

reader:

	ta = x[0].a

No dependency, no ordering. So this totally reasonable generated code could see the pre-initialized value of field a. The job of both smp_read_barrier_depends() and rcu_dereference() is to tell both the CPU and the compiler that such assumptions are ill-advised.

Paul,

Thanks again for this lengthy email. It took me several readings to absorb it all in.

I recommend that someone have a pointer to this email because it really does explain why read_barrier_depends is needed.

Excellent job of explaining this!!! Much appreciated.

OK, will see what I can do...

Quoted 57 lines · Paul E. McKenney

Quoted 56 lines

Yep, you have dependencies, so something like the following:

initial state:

	struct foo {
		int a;
	};
	struct foo x = { 0 };
	struct foo y = { 0 };
	struct foo *global_p = &y;
	/* other variables are appropriately declared auto variables */

	/* No kmalloc() or kfree(), hence no RCU grace periods. */
	/* In the terminology of http://lwn.net/Articles/262464/, we */
	/* are doing only publish-subscribe, nothing else. */

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

reader:

	p = global_p;
	ta = p->a;

Both Alpha and aggressive compiler optimizations can result in the reader seeing the new value of the pointer (&x) but the old value of the field (0). Strange but true. The fix is as follows:

reader:

	p = global_p;
	smp_read_barrier_depends();  /* or use rcu_dereference() */
	ta = p->a;

So how can this happen? First note that if smp_read_barrier_depends() was unnecessary in this case, it would be unnecessary in all cases.

Second, let's start with the compiler. Suppose that a highly optimizing compiler notices that in almost all cases, the reader finds p==global_p. Suppose that this compiler also notices that one of the registers (say r1) almost always contains this expected value of global_p, and that cache pressure ensures that an actual load from global_p almost always generates an expensive cache miss. Such a compiler would be within its rights (as defined by the C standard) to generate code assuming that r1 already had the right value, while also generating code to validate this assumption, perhaps as follows:

	r2 = global_p;  /* high latency, other things complete meanwhile */
	ta == r1->a;
	if (r1 != r2)
		ta = r2->a;

Quoted 6 lines

Quoted 1 line

Now consider the following sequence of events on a superscalar CPU:

I think you missed one step here (causing my confusion). I don't want to assume so I'll try to put in the missing step:

writer: r1 = p; /* happens to use r1 to store parameter p */

You lost me on this one... The writer has only the following three steps:

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

Where did the "r1 = p" come from? For that matter, where did "p" come from?

Quoted 8 lines

Quoted 7 lines

	reader: r2 = global_p; /* issued, has not yet completed. */
	reader: ta = r1->a; /* which gives zero. */
	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: r2 = global_p; /* this instruction now completes */
	reader: if (r1 != r2) /* and these are equal, so we keep bad ta! */

Quoted 1 line

Is that the case?

Ah! Please note that I am doing something unusual here in that I am working with global variables, as opposed to the normal RCU practice of dynamically allocating memory. So "x" is just a global struct, not a pointer to a struct.

Quoted 59 lines · Paul E. McKenney

OK, will see what I can do...

Quoted 57 lines · Paul E. McKenney

Quoted 56 lines

Yep, you have dependencies, so something like the following:

initial state:

	struct foo {
		int a;
	};
	struct foo x = { 0 };
	struct foo y = { 0 };
	struct foo *global_p = &y;
	/* other variables are appropriately declared auto variables */

	/* No kmalloc() or kfree(), hence no RCU grace periods. */
	/* In the terminology of http://lwn.net/Articles/262464/, we */
	/* are doing only publish-subscribe, nothing else. */

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

reader:

	p = global_p;
	ta = p->a;

Both Alpha and aggressive compiler optimizations can result in the reader seeing the new value of the pointer (&x) but the old value of the field (0). Strange but true. The fix is as follows:

reader:

	p = global_p;
	smp_read_barrier_depends();  /* or use rcu_dereference() */
	ta = p->a;

So how can this happen? First note that if smp_read_barrier_depends() was unnecessary in this case, it would be unnecessary in all cases.

Second, let's start with the compiler. Suppose that a highly optimizing compiler notices that in almost all cases, the reader finds p==global_p. Suppose that this compiler also notices that one of the registers (say r1) almost always contains this expected value of global_p, and that cache pressure ensures that an actual load from global_p almost always generates an expensive cache miss. Such a compiler would be within its rights (as defined by the C standard) to generate code assuming that r1 already had the right value, while also generating code to validate this assumption, perhaps as follows:

	r2 = global_p;  /* high latency, other things complete meanwhile */
	ta == r1->a;
	if (r1 != r2)
		ta = r2->a;

Quoted 8 lines

Quoted 6 lines

Quoted 1 line

Now consider the following sequence of events on a superscalar CPU:

I think you missed one step here (causing my confusion). I don't want to assume so I'll try to put in the missing step:

writer: r1 = p; /* happens to use r1 to store parameter p */

You lost me on this one... The writer has only the following three steps:

You're right. I meant "writer: r1 = x;"

Quoted 18 lines

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

Where did the "r1 = p" come from? For that matter, where did "p" come from?

Quoted 8 lines

Quoted 7 lines

	reader: r2 = global_p; /* issued, has not yet completed. */
	reader: ta = r1->a; /* which gives zero. */
	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: r2 = global_p; /* this instruction now completes */
	reader: if (r1 != r2) /* and these are equal, so we keep bad ta! */

Quoted 7 lines

Quoted 1 line

Is that the case?

Ah! Please note that I am doing something unusual here in that I am working with global variables, as opposed to the normal RCU practice of dynamically allocating memory. So "x" is just a global struct, not a pointer to a struct.

But lets look at a simple version of my original code anyway ;-)

Writer:

void add_op(struct myops *x) {
	/* x->next may be garbage here */
	x->next = global_p;
	smp_wmb();
	global_p = x;
}

Reader:

void read_op(void)

{
	struct myops *p = global_p;

	while (p != NULL) {
		p->func();
		p = next;
		/* if p->next is garbage we crash */
	}
}

Here, we are missing the read_barrier_depends(). Lets look at the Alpha cache issue:

reader reads the new version of global_p, and then reads the next pointer. But since the next pointer is on a different cacheline than global_p, it may have somehow had that in it's cache still. So it uses the old next pointer which contains the garbage.

Is that correct?

But I will have to admit, that I can't see how an aggressive compiler might have screwed this up. Being that x is a parameter, and the function add_op is not in a header file.

-- Steve

Quoted 132 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 59 lines · Paul E. McKenney

OK, will see what I can do...

Quoted 57 lines · Paul E. McKenney

Quoted 56 lines

Yep, you have dependencies, so something like the following:

initial state:

	struct foo {
		int a;
	};
	struct foo x = { 0 };
	struct foo y = { 0 };
	struct foo *global_p = &y;
	/* other variables are appropriately declared auto variables */

	/* No kmalloc() or kfree(), hence no RCU grace periods. */
	/* In the terminology of http://lwn.net/Articles/262464/, we */
	/* are doing only publish-subscribe, nothing else. */

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

reader:

	p = global_p;
	ta = p->a;

Both Alpha and aggressive compiler optimizations can result in the reader seeing the new value of the pointer (&x) but the old value of the field (0). Strange but true. The fix is as follows:

reader:

	p = global_p;
	smp_read_barrier_depends();  /* or use rcu_dereference() */
	ta = p->a;

So how can this happen? First note that if smp_read_barrier_depends() was unnecessary in this case, it would be unnecessary in all cases.

Second, let's start with the compiler. Suppose that a highly optimizing compiler notices that in almost all cases, the reader finds p==global_p. Suppose that this compiler also notices that one of the registers (say r1) almost always contains this expected value of global_p, and that cache pressure ensures that an actual load from global_p almost always generates an expensive cache miss. Such a compiler would be within its rights (as defined by the C standard) to generate code assuming that r1 already had the right value, while also generating code to validate this assumption, perhaps as follows:

	r2 = global_p;  /* high latency, other things complete meanwhile */
	ta == r1->a;
	if (r1 != r2)
		ta = r2->a;

Quoted 8 lines

Quoted 6 lines

Quoted 1 line

Now consider the following sequence of events on a superscalar CPU:

I think you missed one step here (causing my confusion). I don't want to assume so I'll try to put in the missing step:

writer: r1 = p; /* happens to use r1 to store parameter p */

You lost me on this one... The writer has only the following three steps:

You're right. I meant "writer: r1 = x;"

Quoted 18 lines

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

Where did the "r1 = p" come from? For that matter, where did "p" come from?

Quoted 8 lines

Quoted 7 lines

	reader: r2 = global_p; /* issued, has not yet completed. */
	reader: ta = r1->a; /* which gives zero. */
	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: r2 = global_p; /* this instruction now completes */
	reader: if (r1 != r2) /* and these are equal, so we keep bad ta! */

Quoted 7 lines

Quoted 1 line

Is that the case?

Ah! Please note that I am doing something unusual here in that I am working with global variables, as opposed to the normal RCU practice of dynamically allocating memory. So "x" is just a global struct, not a pointer to a struct.

But lets look at a simple version of my original code anyway ;-)

Writer:

void add_op(struct myops *x) {
	/* x->next may be garbage here */
	x->next = global_p;
	smp_wmb();
	global_p = x;
}

Reader:

void read_op(void)

{
	struct myops *p = global_p;

	while (p != NULL) {
		p->func();
		p = next;
		/* if p->next is garbage we crash */
	}
}

Here, we are missing the read_barrier_depends(). Lets look at the Alpha cache issue:

reader reads the new version of global_p, and then reads the next pointer. But since the next pointer is on a different cacheline than global_p, it may have somehow had that in it's cache still. So it uses the old next pointer which contains the garbage.

Quoted 6 lines

Is that correct?

But I will have to admit, that I can't see how an aggressive compiler might have screwed this up. Being that x is a parameter, and the function add_op is not in a header file.

Tell me if I am mistakened, but applying Paul's explanation to your example would give (I unroll the loop for clarity) :

Writer:

void add_op(struct myops *x) {
	/* x->next may be garbage here */
	x->next = global_p;
	smp_wmb();
	global_p = x;
}

Reader:

void read_op(void)

{
	struct myops *p = global_p;

  if (p != NULL) {
		p->func();
		p = p->next;
  /*
   * Suppose the compiler expects that p->next is likely to be equal to
   * p + sizeof(struct myops), uses r1 to store previous p, r2 to store the
   * next p and r3 to store the expected value. Let's look at what the
   * compiler could do for the next loop iteration.
   */
  r2 = r1->next   (1)
  r3 = r1 + sizeof(struct myops)
  r4 = r3->func   (2)
  if (r3 == r2 && r3 != NULL)
    call r4

		/* if p->next is garbage we crash */
	} else
    return;

  if (p != NULL) {
		p->func();
		p = p->next;
		/* if p->next is garbage we crash */
	} else
    return;

.....
}

In this example, we would be reading the expected "r3->func" (2) before reading the real r1->next (1) value if reads are issued out of order.

Paul, am I correct ? And.. does the specific loop optimization I just described actually exist ?

Thanks for your enlightenment :)

Quoted 61 lines · Paul E. McKenney

OK, will see what I can do...

Quoted 59 lines · Paul E. McKenney

Quoted 57 lines

Yep, you have dependencies, so something like the following:

initial state:

	struct foo {
		int a;
	};
	struct foo x = { 0 };
	struct foo y = { 0 };
	struct foo *global_p = &y;
	/* other variables are appropriately declared auto variables */

	/* No kmalloc() or kfree(), hence no RCU grace periods. */
	/* In the terminology of http://lwn.net/Articles/262464/, we */
	/* are doing only publish-subscribe, nothing else. */

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

reader:

	p = global_p;
	ta = p->a;

Both Alpha and aggressive compiler optimizations can result in the reader seeing the new value of the pointer (&x) but the old value of the field (0). Strange but true. The fix is as follows:

reader:

	p = global_p;
	smp_read_barrier_depends();  /* or use rcu_dereference() */
	ta = p->a;

So how can this happen? First note that if smp_read_barrier_depends() was unnecessary in this case, it would be unnecessary in all cases.

Second, let's start with the compiler. Suppose that a highly optimizing compiler notices that in almost all cases, the reader finds p==global_p. Suppose that this compiler also notices that one of the registers (say r1) almost always contains this expected value of global_p, and that cache pressure ensures that an actual load from global_p almost always generates an expensive cache miss. Such a compiler would be within its rights (as defined by the C standard) to generate code assuming that r1 already had the right value, while also generating code to validate this assumption, perhaps as follows:

	r2 = global_p;  /* high latency, other things complete meanwhile */
	ta == r1->a;
	if (r1 != r2)
		ta = r2->a;

Now consider the following sequence of events on a superscalar CPU:

Quoted 6 lines

Quoted 4 lines

I think you missed one step here (causing my confusion). I don't want to assume so I'll try to put in the missing step:

writer: r1 = p; /* happens to use r1 to store parameter p */

You lost me on this one... The writer has only the following three steps:

You're right. I meant "writer: r1 = x;"

Quoted 17 lines

writer:

	x.a = 1;
	smp_wmb();  /* or smp_mb() */
	global_p = &x;

Where did the "r1 = p" come from? For that matter, where did "p" come from?

Quoted 8 lines

Quoted 7 lines

	reader: r2 = global_p; /* issued, has not yet completed. */
	reader: ta = r1->a; /* which gives zero. */
	writer: x.a = 1;
	writer: smp_wmb();
	writer: global_p = &x;
	reader: r2 = global_p; /* this instruction now completes */
	reader: if (r1 != r2) /* and these are equal, so we keep bad ta! */

Quoted 6 lines

Quoted 1 line

Is that the case?

Ah! Please note that I am doing something unusual here in that I am working with global variables, as opposed to the normal RCU practice of dynamically allocating memory. So "x" is just a global struct, not a pointer to a struct.

But lets look at a simple version of my original code anyway ;-)

Writer:

void add_op(struct myops *x) {
	/* x->next may be garbage here */
	x->next = global_p;
	smp_wmb();
	global_p = x;
}

Reader:

void read_op(void)

{
	struct myops *p = global_p;

	while (p != NULL) {
		p->func();
		p = next;
		/* if p->next is garbage we crash */
	}
}

Here, we are missing the read_barrier_depends(). Lets look at the Alpha cache issue:

reader reads the new version of global_p, and then reads the next pointer. But since the next pointer is on a different cacheline than global_p, it may have somehow had that in it's cache still. So it uses the old next pointer which contains the garbage.

Is that correct?

But I will have to admit, that I can't see how an aggressive compiler might have screwed this up. Being that x is a parameter, and the function add_op is not in a header file.

arch/x86/kernel/entry_32.S DF_MASK = 0x00000400 · line 84

Quoted 13 lines · Steven Rostedt

arch/x86/kernel/entry_32.S +7 -0

@@ -75,6 +75,31 @@ DF_MASK		= 0x00000400
 NT_MASK		= 0x00004000
 VM_MASK		= 0x00020000
 
+#ifdef CONFIG_MCOUNT
+.globl mcount
+mcount:
+	/* unlikely(mcount_enabled) */
+	cmpl $0, mcount_enabled
+	jnz trace
+	ret

(and the corresponding 64-bit version)

Is the impact of this change on the (already expensive) mcount_enabled case negligible? I worried about use cases where we want to gain some (relative) worst-case numbers via these instrumentations.

In my personal priority scheme, CONFIG_MCOUNT=y && !mcount_enabled comes after mcount_enabled.

well, actually, I disagree. I only set mcount_enabled=1 when I'm about to test something. You're right that we want the impact of the test least affected, but when we have mcount_enabled=1 we usually also have a function that's attached and in that case this change is negligible. But on the normal case where mcount_enabled=0, this change may have a bigger impact.

Remember CONFIG_MCOUNT=y && mcount_enabled=0 is (15% overhead)

         CONFIG_MCOUNT=y && mcount_enabled=1 dummy func (49% overhead)
         CONFIG_MCOUNT=y && mcount_enabled=1 trace func (500% overhead)

The trace func is the one that will be most likely used when analyzing. It gives hackbench a 500% overhead, so I'm expecting this change to be negligible in that case. But after I find what's wrong, I like to rebuild the kernel without rebooting so I like to have mcount_enabled=0 have the smallest impact ;-)

I'll put back the original code and run some new numbers.

plain text document attachment (mcount-add-x86-vdso-notrace-annotations.patch)
Add the notrace annotations to some of the vsyscall functions.

Quoted 3 lines · Steven Rostedt

plain text document attachment (mcount-add-x86-vdso-notrace-annotations.patch)
Add the notrace annotations to some of the vsyscall functions.

Would the VDSO stuff crash a kernel without these annotations and CONFIG_MCOUNT=y ?

If so, I think it would be best of you placed these annotations before adding the core code, this would improve bisectability.

lib/tracing/trace_wakeup.c new file +17 -0

+static void notrace __wakeup_reset(struct tracing_trace *tr)
+{
+	struct tracing_trace_cpu *data;
+	int cpu;
+
+	assert_spin_locked(&wakeup_lock);
+
+	for_each_possible_cpu(cpu) {
+		data = tr->data[cpu];
+		tracing_reset(data);
+	}
+
+	wakeup_cpu = -1;
+	wakeup_prio = -1;
+	if (wakeup_task) {
+		put_task_struct(wakeup_task);
+		tracing_stop_function_trace();

Quoted 1 line · Steven Rostedt

+static void notrace __wakeup_reset(struct tracing_trace *tr)

lib/tracing/trace_wakeup.c line 154

Quoted 9 lines

lib/tracing/trace_wakeup.c new file +9 -0

+
+	wakeup_task = NULL;
+
+	/*
+	 * Don't let the trace_enabled = 1 show up before
+	 * the wakeup_task is reset.
+	 */
+	smp_wmb();
+}

Another un-balanced barrier.

+static DEFINE_PER_CPU(int, tracing_cpu);

Quoted 1 line · Steven Rostedt

+static DEFINE_PER_CPU(int, tracing_cpu);

Is the per-cpu tracing not also needed for irq off tracing?

Also, its not mentioned in the changelog.