User: Password:
Subscribe / Log in / New account

Reader-to-updater upgrade?

Reader-to-updater upgrade?

Posted Jan 4, 2008 17:28 UTC (Fri) by PaulMcKenney (subscriber, #9624)
In reply to: Reader-to-updater upgrade? by jzbiciak
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:

  1. 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.
  2. 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.
  3. 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.
  4. 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?:

  1. Subscribers see a completely-initialized version of published data structures.
  2. The synchronize_rcu() primitive (and friends) will wait for all pre-existing readers to complete.
  3. 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?

(Log in to post comments)

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!!!

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds