[C++] RCU

Reference:
[Kernel Doc] What is RCU? -- “Read, Copy, Update”
[NMI] Contents hide (Top) History See also Notes External links Non-maskable interrupt
[Kernel Doc] False Sharing with how to detect and analyze

Source code:
https://android.googlesource.com/kernel/common/+/refs/heads/android-mainline/kernel/rcu/rcu.h

Kernel doc has most concise details about RCU, here we jot down
main idea for fast fresh up the concept.

RCU(Read, Copy, Update) is a synchronization mechanism that was added to the Linux kernel during the 2.5 development effort that is optimized for read-mostly situations.

The basic idea behind RCU is to split updates into 

• “removal” and 
• “reclamation” phases.

The removal phase removes references to data items within a data structure (possibly by replacing them with references to new versions of these data items), and can run concurrently with readers. 

The reason that it is safe to run the removal phase concurrently with readers is the semantics of modern CPUs guarantee that readers will see either the old or the new version of the data structure rather than a partially updated reference.

The reclamation phase does the work of reclaiming (e.g., freeing) the data items removed from the data structure during the removal phase. Because reclaiming data items can disrupt any readers concurrently referencing those data items, the reclamation phase must not start until readers no longer hold references to those data items.

typical RCU update sequence goes something like the following: 

• a) Remove pointers to a data structure, so that subsequent readers cannot gain a reference to it. 
  This can be done due to writes to single aligned pointers are atomic on modern CPUs, allowing atomic insertion, removal, and replacement of data items in a linked structure without disrupting readers. This removal phase does not interrupt readers. It is just that the readers could read old values.
• b) Wait for all previous readers to complete their RCU read-side critical sections. 
  How the reader notify reclamation that they are done? A callback function.
• c) At this point, there cannot be any readers who hold references to the data structure, so it now may safely be reclaimed (e.g., kfree()d).

Should think a) and c) separately. c) can be run in different thread, although it is totally fine to have a) and c) run in same thread.

5 core APIs:

• rcu_read_lock()
• rcu_read_unlock()
• synchronize_rcu() / call_rcu()
• rcu_assign_pointer()
• rcu_dereference()

rcu_read_lock()

void rcu_read_lock(void);

This temporal primitive is used by a reader to inform the reclaimer that the reader is entering an RCU read-side critical section. It is illegal to block while in an RCU read-side critical section, though kernels built with CONFIG_PREEMPT_RCU can preempt RCU read-side critical sections. Any RCU-protected data structure accessed during an RCU read-side critical section is guaranteed to remain unreclaimed for the full duration of that critical section. Reference counts may be used in conjunction with RCU to maintain longer-term references to data structures.

Note that anything that disables bottom halves, preemption, or interrupts also enters an RCU read-side critical section. Acquiring a spinlock also enters an RCU read-side critical sections, even for spinlocks that do not disable preemption, as is the case in kernels built with CONFIG_PREEMPT_RT=y. Sleeplocks do not enter RCU read-side critical sections.

rcu_read_unlock()

void rcu_read_unlock(void);

This temporal primitives is used by a reader to inform the reclaimer that the reader is exiting an RCU read-side critical section. Anything that enables bottom halves, preemption, or interrupts also exits an RCU read-side critical section. Releasing a spinlock also exits an RCU read-side critical section.

Note that RCU read-side critical sections may be nested and/or overlapping.

synchronize_rcu()

void synchronize_rcu(void);

This temporal primitive marks the end of updater code and the beginning of reclaimer code. It does this by blocking until all pre-existing RCU read-side critical sections on all CPUs have completed. Note that synchronize_rcu() will not necessarily wait for any subsequent RCU read-side critical sections to complete.