Weekly edition	Kernel	Security	Distributions	Contact Us	Search
Archives	Calendar	Subscribe	Write for LWN	LWN.net FAQ	Sponsors

Reader-to-updater upgrade?

Posted Jan 3, 2008 12:44 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246)
Parent article: What is RCU? Part 2: Usage

What exactly are the semantics of this unconditional reader-to-updater upgrade? I thought all writers were serialized, and readers never block with respect to each others or writers. Writers, once finished, updated the "current version" pointer atomically, so earlier readers see an older copy, and later readers and writers see a newer copy.

What happens when a reader wants to become an updater when another writer is already active? To me it seems like that that thread needs to get in line behind the existing writer.

For example, consider a monotonically increasing event counter, protected by RCU. All readers will see a monotonically increasing count. Writers, which must do a read-modify-write cycle to increment the count, work correctly as long as they serialize. What happens if a reader decides to write an incremented count all of the sudden? If there are other updaters in parallel, does the increment get dropped?

Am I misunderstanding the guarantees offered by RCU?

(Log in to post comments)

Reader-to-updater upgrade?

Posted Jan 4, 2008 17:28 UTC (Fri) by PaulMcKenney (subscriber, #9624) [Link]

Good question! As far as I know, the semantics of an RCU read-to-write upgrade have never been formalized. But the informal properties are well understood.

As a general rule, writers will serialize if necessary, but any such serialization will be entirely contained within the RCU read-side critical section. Therefore, a synchronize_rcu() call that started after a pair of upgrade-to-write RCU read-side critical sections would wait for the entire RCU read-side critical sections to complete, including the writes and any required write-side serialization.

However, the exact semantics will depend on the synchronization mechanism used by the writers. Here are some possibilities:

Writers use a single spinlock. This matches your second sentence: "all writers were serialized, and readers never block with respect to each others or writers". In addition, as you say, if a pair of RCU readers try to upgrade concurrently, one of them will go first and the other will spin waiting for the first to complete before starting its update. But both writers will complete unconditionally.
Writers use multiple spinlocks, for example, one spinlock per hash-table bucket. In this case, only writers accessing the same hash-table bucket will be serialized, and writers accessing different hash-table buckets can run in parallel.
Writers use atomic operations, for example, your atomic-increment example (assuming that I understand it correctly). In this case, as long as the atomic increments are being used correctly (all modifications to the variable in question are atomic, etc.), all the atomic operations on the variable will be serialized in hardware -- none of the atomic operations will be dropped.
Allow only a single designated task to perform updates. In this case, the reader would need to check to see if it was this designated task before doing the update. But because there is but one writer, no writer-to-writer serialization is required.

Of course, if the writers' synchronization is buggy, the overall algorithm will still be buggy. For example, suppose that writers atomically increment a given variable, but that readers (erroneously) non-atomically increment that same variable. Some of the writers' increments might be lost, just as they might be if you were not using RCU.

So the fundamental guarantees of RCU are those listed in What is RCU, Fundamentally?:

Subscribers see a completely-initialized version of published data structures.
The synchronize_rcu() primitive (and friends) will wait for all pre-existing readers to complete.
Providing multiple versions permits readers to safely run concurrently with updaters.

However, a separate synchronization mechanism must be supplied to keep the writers from destructively interfering with each other, as noted in the first list above.

Does this answer your question, or did I miss your point?

Reader-to-updater upgrade?

Posted Jan 10, 2008 13:58 UTC (Thu) by jarkao2 (guest, #41960) [Link]

1. "However, a separate synchronization mechanism must be supplied to keep the writers from
destructively interfering with each other, as noted in the first list above."
Maybe I miss or repeat something, but serious downsize of this upgrade-to-write seems to be in
this possibly stale value of the search got as an RCU reader, which would always(?) require
additional verification.

2. This example:
"RCU is a Restricted Reference-Counting Mechanism
 [...]
 Regardless of these restrictions, the following code can safely delete p:

  1 spin_lock(&mylock);
  2 p = head;
  3 head = NULL;
  4 spin_unlock(&mylock);
  5 synchronize_rcu();  /* Wait for all references to be released. */
  6 kfree(p);
 [...]"
 
should probably promote rcu_assign_pointer() more...

3. "And" maybe one more tiny fix:
"RCU is a Bulk Reference-Counting Mechanism
 [...]
 starting and I/O and released [...]"

Many thanks!

Reader-to-updater upgrade?

Posted Jan 10, 2008 21:02 UTC (Thu) by PaulMcKenney (subscriber, #9624) [Link]

1. Indeed, the upgrade-to-update change would be visible to the remainder of the RCU read-side
critical section.  However, in a surprisingly large number of cases, there is no need for
additional verification steps (though verification can be used when needed).  This is a key
difference between RCU and non-blocking synchronization (NBS) -- NBS would absolutely require
the validation steps in order to avoid memory corruption.

2. Good point -- although rcu_assign_pointer(head, NULL) is superfluous, it is good practice,
and there is no performance penalty.

3. Good eyes!!!