Posted Jan 4, 2008 17:28 UTC (Fri) by PaulMcKenney
In reply to: Reader-to-updater upgrade?
Parent article: What is RCU? Part 2: Usage
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?
to post comments)