LWN: Comments on "What is RCU, Fundamentally?"

Links to later articles in the series

fraetor — Sun, 01 Sep 2024 08:23:23 +0000

Links to the other two parts of the series:

What is RCU, Fundamentally?

summergift — Mon, 03 Jun 2024 06:57:08 +0000

Thank you for your explanation!

What is RCU, Fundamentally?

PaulMcKenney — Mon, 08 Jun 2015 18:32:31 +0000

In the following code, we have at most two versions:

mutex_lock(&my_mutex);
p = find_an_element(key);
list_del_rcu(&p->list);
synchronize_rcu();
kfree(p);
mutex_unlock(&my_mutex);

Only one task at a time may hold my_mutex, so there can be at most two versions of the list, the new one with the element deleted, and for pre-existing readers, the old one with that element still in place. (When this article was written, the Linux kernel used semaphores for sleeplocks, but it now uses mutexes.)

In contrast, suppose that the mutex is held only across the deletion:

mutex_lock(&my_mutex);
p = find_an_element(key);
list_del_rcu(&p->list);
mutex_unlock(&my_mutex);
synchronize_rcu();
kfree(p);

In this case, many updaters could be waiting for grace periods in parallel, so there could be many concurrent versions of the list.

What is RCU, Fundamentally?

firolwn — Sun, 24 May 2015 12:50:13 +0000

I really didn't understand Quick Quiz 5.
Why does semaphore affect the numbers of RCU version list?

What is RCU, Fundamentally?

nix — Sat, 06 Aug 2011 13:51:44 +0000

Does this not read like that once announced Microsoft Filesystem called WinFS ?

No. WinFS was a 'store everything in a relational database' thing. This is utterly different, nothing relational at all.

What is RCU, Fundamentally?

stock — Sat, 06 Aug 2011 10:47:10 +0000

"One key attribute of RCU is the ability to safely scan data, even
though that data is being modified concurrently. To provide this
ability for concurrent insertion, RCU uses what can be thought of
as a publish-subscribe mechanism."

Does this not read like that once announced Microsoft Filesystem called
WinFS ? From the WinFS wikipedia penal records :

http://en.wikipedia.org/wiki/WinFS

"WinFS (short for Windows Future Storage)[1] is the code name for a
cancelled[2] data storage and management system project based on
relational databases, developed by Microsoft and first demonstrated
in 2003 as an advanced storage subsystem for the Microsoft Windows
operating system, ...
[ ... ]
WinFS includes a relational database for storage of information,
and allows any type of information to be stored in it, provided
there is a well defined schema for the type."

It's funny to see IBM, amongst others, explain the 'dirty' details about 'RCU'
here on LWN.

Robert
--
Robert M. Stockmann - RHCE
Network Engineer - UNIX/Linux Specialist
crashrecovery.org stock@stokkie.net

Some usages of RCU in the kernel code

PaulMcKenney — Tue, 08 Jan 2008 14:13:30 +0000

Good eyes!!!

Some usages of RCU in the kernel code

jarkao2 — Tue, 08 Jan 2008 11:02:34 +0000

Thanks for this (next) great article too! BTW, probably 'a' tiny fix needed:
"Maintain Multiple Versions of Recently Updated Objects
[...] Two examples are presented showing how a an element [...]"

Some usages of RCU in the kernel code

PaulMcKenney — Mon, 07 Jan 2008 16:52:49 +0000

I was inviting a patch for incorporating the smp_wmb() into the rcu_assign_pointer.

The lock acquisition makes rcu_dereference() unnecessary, but cannot enforce the ordering
provided by the smp_wmb()/rcu_assign_pointer().

Some usages of RCU in the kernel code

fbh — Mon, 07 Jan 2008 16:03:08 +0000

Well, I actually raised 2 points and I'm not sure which one is the good one...

Could you please clarify ?

To answer your question, I don't have any problems for submitting a patch.

---
PS: This interface is pretty hard for discussing on an article. It's like bottom-posting
except we loose all its advantages... Just my 2 cents.

Some usages of RCU in the kernel code

PaulMcKenney — Mon, 07 Jan 2008 15:28:26 +0000

Good point!  Would you like to submit a patch?

Some usages of RCU in the kernel code

fbh — Mon, 07 Jan 2008 10:14:23 +0000

Regarding the second point, I'm sorry, my fingers typed rcu_dereference() whereas my brain was
thinking to rcu_assign_pointer(). rcu_dereference() could be used in update-side code, as you
pointed out, but obviously not in __list_add_rcu().

Therefore __list_add_rcu() could be:

        new->next = next;
        new->prev = prev;
        rcu_assign_pointer(prev->next, new);
        next->prev = new;

The main advantage of this is readability IMHO.

You said that __list_add_rcu() must be protected by appropriate locking, and a memory barrier
is implied by lock acquisition which should be enough. But __list_add_rcu() has a memory
barrier in its implementation.

Thanks.

Some usages of RCU in the kernel code

PaulMcKenney — Sun, 06 Jan 2008 19:04:05 +0000

The reason that kernel/kprobes.c does not use synchronize_rcu() is that it instead uses synchronize_sched(). The read-side primitives corresponding to synchronize_sched() include preempt_disable()/preempt_enable(), local_irq_save()/local_irq_restore() -- in short, any primitive that disables and re-enables preemption, including entry to hardware irq/exception handlers. The third article in this series will cover these and other nuances of the RCU API.

The reason that __list_add_rcu() does not use rcu_dereference() is that __list_add_rcu() is an update-side primitive, and therefore must be protected by appropriate locking. This means that the list cannot change while the lock is held, and this in turn means that the memory barriers implied by lock acquisition suffice. That said, it is permissible (but again, not necessary) to use rcu_dereference() in update-side code -- in fact, in some situations, doing so promotes code reuse and in some cases readability.

The discussion of Figure 2 in this article and its bibliography is a good place to start on Alpha's memory ordering. I am not all that familiar with value-speculation compiler-optimization research, but one place to start might be here.

Some usages of RCU in the kernel code

fbh — Sun, 06 Jan 2008 10:42:17 +0000

Hi,

I'm probably missing something but I looked at users of RCU in the kernel and found that
kernel/kprobes.c doesn't call rcu_read_lock() function before entering in a critical section.
Does it have any good reasons to do so ?

Another point in include/linux/list.h: sometimes it seems that RCU API is not used for no good
reasons. For example __list_add_rcu() does not use rcu_dereference(). However by using it, the
code could have clearly showed which pointer is RCU protected...

The Alpha memory ordering and value-speculation compiler optimizations done in this
architecture sounds incredibely weird to me. Any avalaible pointers on this subject ?

Anyways, thanks for this article.

Using RCU in userland

PaulMcKenney — Sat, 05 Jan 2008 16:26:04 +0000

Very cool!  Please let me know how it goes!

Using RCU in userland

eduardo.juan — Fri, 04 Jan 2008 20:08:19 +0000

Thanks Paul for answering! I'll be trying it!

Regards

Using RCU in userland

PaulMcKenney — Fri, 04 Jan 2008 18:13:35 +0000

RCU has been used experimentally in user-mode code, and one benchmarking framework may be found at U. of Toronto.

In addition, I vaguely recall at least one user-level RCU implementation being posted on LKML as a programming/debugging aid. There are some others that I am unfortunately unable to release at this time.

As noted in an earlier comment, garbage-collected languages automatically provide much of the wait-for-reader functionality for free -- however, it is still necessary to correctly handle the publish-subscribe operation correctly. One way to do this in Java is to use the recently added "volatile" field specifier (no relation to "volatile" in C/C++) for the pointer that is being published. In other words, instead of using the Linux-kernel rcu_assign_pointer() and rcu_dereference() to publish and subscribe, you instead mark the pointer itself using Java's "volatile" keyword.

Userland

eduardo.juan — Fri, 04 Jan 2008 04:06:55 +0000

Thanks for this excellent article!

I have a fundamentally question! :D

Is any way to use RCU on userland programs? I mean, any lib or implementation of this
constraints in userland?

Thanks and regards!

Forcing the compiler and CPU to execute assignment statements in order ?

Brenner — Wed, 02 Jan 2008 00:09:29 +0000

Thanks a lot for your very informative answer. And Happy New Year!!!

Forcing the compiler and CPU to execute assignment statements in order ?

PaulMcKenney — Tue, 01 Jan 2008 23:10:45 +0000

You are welcome!

Your question about ordering is a good one, and code reordering by both CPU and compiler can be grossly counter-intuitive at times. So an explanation is indeed in order. Let's start with the compiler. The code was as follows:

 11 p->a = 1;
 12 p->b = 2;
 13 p->c = 3;
 14 gp = p;

It is possible that the compiler holds the value of gp in a register, but that it will need to spill that value in order to generate the code for lines 11-14. What to do? Well, as long as the compiler can prove that p and gp do not point to overlapping regions of memory, the compiler is within its rights to generate the code for line 14 before generating the code for the other lines. In this case, rearranging the code in this manner reduces code size, probably increases performance, and hurts no one. That is, it hurts no one in the absence of concurrency. However, please keep in mind that the C standard currently does not allow concurrency, strange though that may seem to those of us who have been writing concurrent C programs for decades.

So special non-standard compiler directives (barrier() in the Linux kernel, or, when used properly, volatile) are required to force the compiler to maintain ordering. Note that such directives are included, either directly or indirectly, in primitives that require ordering, for example, the smp_mb() memory barrier in the Linux kernel.

On to the CPU. Suppose that the compiler generates the code in order, and that the CPU executes it in order. What could possibly go wrong?

The store buffer. The CPU will likely commit the new values of p->a, p->b, p->c, and gp to the store buffer. If the cache line referenced by p happens to be owned by some other CPU (for example, if the memory returned by the preceding kmalloc() had been kfree()ed by some other CPU) and if the cache line containing gp is owned by the current CPU, the first three assignments will be flushed from the store buffer (and thus visible to other CPUs) long after the last assignment will be.

In addition, superscalar CPUs routinely execute code out of order. Such beasts might become less common as power-consumption concerns rise to the fore, but there are still quite a few such CPUs out there, dating from the mid-1990s for commodity microprocessors and to the mid-1960s for supercomputers. For example, Tomasulo's Algorithm, dating from the mid-1960s, is specifically designed to allow CPUs to execute instructions out of order. And there were super-scalar supercomputers pre-dating Tomasulo's Algorithm.

In short, if ordering is important to you, use primitives to enforce ordering. Such primitives include locking primitives (e.g., spin_lock() and spin_unlock() in the Linux kernel), the RCU publish-subscribe primitives called out in this article, and of course explicit memory barriers. (I would recommend avoiding explicit memory barriers where feasible -- they are difficult to get right.)

Hey, you asked!!! And Happy New Year!!!

Forcing the compiler and CPU to execute assignment statements in order ?

Brenner — Sun, 30 Dec 2007 16:51:53 +0000

Thanks for the article;

In the 'Publish-Subscribe Mechanism', the article states : "Unfortunately, there is nothing
forcing the compiler and CPU to execute the last four assignment statements in order."

This breaks my mind. I understand concurrency problems with multiple tasks, but here only one
task is considered (or did I misunderstand something ?). Why would the CPU not execute the
last four assignment statements in the order given by the compiler, and why would the compiler
not keep the order given by the programmer ???

Even with multiple tasks, I thought that the order was guaranteed (I agree that many things
can happen between two code lines of one given task if other tasks are running though).

Can anyone enlighten me ?

Backlinks

PaulMcKenney — Fri, 28 Dec 2007 15:35:20 +0000

Glad you liked the article, and thank you for the excellent question! I could give any number of answers, including:

In production systems, trivial techniques are a very good thing.
Show me an example where it is useful to traverse the ->prev pointers under RCU protection. Given several such examples, we could work out how best to support this.
Consistency is grossly overrated. (Not everyone agrees with me on this, though!)
Even with atomic two-pointer updates, consider the following sequence of events: (1) task 1 does p=p->next (2) task 2 inserts a new element between the two that task 1 just dealt with (3) task 1 does p=p->prev and fails to end up where it started! Even double-pointer atomic update fails to banish inconsistency! ;-)
If you need consistency, use locks.

Given the example above, we could support a level of consistency equivalent to the double-pointer atomic update simply by assigning the pointers in sequence -- just remove the prev-pointer poisoning from list_del_rcu(), for example. But doing this would sacrifice the ability to catch those bugs that pointer-poisoning currently catches.

So, there might well come a time when the Linux kernel permits RCU-protected traversal of linked lists in both directions, but we need to see a compelling need for this before implementing it.

What is RCU, Fundamentally?

PaulMcKenney — Fri, 28 Dec 2007 15:22:48 +0000

Thank you for providing the link -- much better than my old hard copy!  It is very good indeed
to see some of these older papers becoming available on the web.

There was indeed some memory-consistency-model research done some decades ago.  Although I
cannot claim comprehensive knowledge of memory-model research, as near as I can tell, almost
all of this older research was swept aside by the notion of sequential consistency in 1979.
The lion's share of later research assumed sequential consistency, which rendered this research
less than helpful on weakly-ordered machines, where "weakly ordered" includes x86.  Algorithms
that fail to work on x86 cannot be said to have much practical value, in my opinion.

There were nevertheless some fundamental papers published in the 90s (e.g., Sarita Adve and
Kourosh Gharachorloo, among others), but many of the researchers focused on "how to emulate
sequential consistency on weak-memory machines" as opposed to "how best to express
memory-ordering constraints while allowing efficient code to be generated for systems with a
wide variety of memory consistency models".  It is this latter statement that the C/C++
standards committee must address.

Backlinks

mmutz — Fri, 28 Dec 2007 12:37:18 +0000

I'm wondering whether the omission of the backlinks in the examples is a 
good thing. The omission makes the technique trivial, since publishing 
only involves one replacing one pointer.

What about the second, back, one? Without support for atomic two-pointer 
updates, how can both the p->prev->next = q and p->next->prev = q updates 
be performed without risking clients to see an inconsistent view of the 
doubly linked list? Or is that not a problem in practice?

Thanks for the article, though. Looking forward to the next installment!

What is RCU, Fundamentally?

scottt — Thu, 27 Dec 2007 23:47:12 +0000

A link to the paper.

With people doing all these advanced concurrent algorithms in the eighties I wonder why we're only just now getting a formal memory model for the C/C++ programming languages.

What is RCU, Fundamentally?

PaulMcKenney — Thu, 27 Dec 2007 19:04:53 +0000

Glad you liked it!!!  ;-)

Garbage-collected languages such as Java implement RCU's "wait for pre-existing RCU readers to
complete" implicitly via the garbage collector.  However, in Java, you must make careful use
of atomic variables in order to correctly implement the publish-subscribe mechanism.  Last I
knew, Java would emit memory barriers for the subscribe operation, even when unnecessary, but
perhaps that has changed by now.  However, in many cases, the memory-barrier overhead might
well be acceptable (e.g., when avoiding contention).

So you might well be able to use RCU techniques in Java!  (For whatever it is worth, Kung and
Lehman described the gist of using garbage collectors in this fashion in their paper entitled
"Concurrent Maintenance of Binary Search Trees" in "ACM Transactions on Database Systems" back
in September 1980.)

Problem with ex 2 ?

PaulMcKenney — Thu, 27 Dec 2007 18:57:35 +0000

Indeed!  As with the preceding example, there must be some sort of mutual exclusion in play,
and as in the preceding example, this mutual exclusion is not shown explicitly.

One approach, as you say, would be to add locking, perhaps similar to that described in the
answer to Quick Quiz 4 (but for the deletion example).  Another approach would be to hold a
mutex (in the old style, "semaphore") across the entire code segment.  Yet a third approach
would be to permit only a single designated task to do updates (in which case the code would
remain as is).  There are other approaches as well.

In any case, I am glad to see that people are sensitized to the need for mutual exclusion in
parallel code!

What is RCU, Fundamentally?

union — Wed, 26 Dec 2007 12:54:46 +0000

Since nobody else said it. 

Thanks for a great article.
I liked the articles about memory and this looks like another great miniseries. While I spend
most of my days programming python and Java,
I believe that understanding such lower level concepts makes me better programmer. 

I hope that there will be more such background or fundamentals articles in the future.

Luka

Problem with ex 2 ?

xav — Sun, 23 Dec 2007 23:23:31 +0000

It looks to me that example 2 is wrong: access to p is unlocked, so it can changed under its
feet if preempted: *q = *p can access freed memory.

example code nitpicks

PaulMcKenney — Fri, 21 Dec 2007 17:08:55 +0000

And many thanks to Jon Corbet for applying the fixes for these problems!

example code nitpicks

PaulMcKenney — Fri, 21 Dec 2007 01:03:29 +0000

Good catch in both cases!

example code nitpicks

ntl — Thu, 20 Dec 2007 21:15:51 +0000

Shouldn't the list_head and hlist_node structs be embedded in struct foo, instead of pointers? That is,

struct foo {
-   struct list_head *list;
+   struct list_head list;
   ...
}

Also, no need to cast the return value of kmalloc :)