RCU fundamentals

Read-Copy-Update (RCU)

Read-Copy-Update is a synchronization mechanism. This mechanism is notable in that RCU readers do not directly synchronize with RCU updaters, which makes RCU read paths extremely fast and also permits RCU readers to accomplish useful work even when running concurrently with RCU updaters¹.

pro, the read path is very fast. In some cases (non-preempt kernels) RCU’s read-side primitives have zero overhead.

RCU supports concurrency between a single updater and multiple readers. RCU ensures that reads are coherent by maintaining multiple versions of objects and ensuring that they are not freed up until all pre-existing read-side critical sections complete².

The great advantage of RCU is that it can wait for each of (say) 20,000 different things without having to explicitly track each and every one of them, and without having to worry about the performance degradation, scalability limitations, complex deadlock scenarios, and memory-leak hazards that are inherent in schemes using explicit tracking. ²

I’m a little skeptical about this claim: IIUC all RCU protected objects essentially share one single big lock. One RCU object may be blocked by its busy neighbour … even though they are totally unrelated.. right? Isnt’ this the same approach as the big-kernel-lock?

Glossary

read-side critical section

An RCU read-side critical section starts with an rcu_read_lock() and ends with a corresponding rcu_read_unlock(); RCU read-side CS can be nested, and may contain pretty muc hany code, as long as that code does not explicitly block or sleep.

SRCU, RCU Clasic / realtime RCU

/// TODO ///

Grace Period⁵

An RCU grace period is informally defined as any time period such that all RCU read-side critical sections in existence at the beginning of that period have completed before its end⁶.

A time period during which all such pre-existing readers complete (so that the updater can reclaim old versions of data structures.) is called a “grace period”⁷.

what is

RCU is made up of three fundamental mechanisms

• insertion: Publish-Subscribe Mechanism
• deletion: Wait fore pre-existing RCU readers to complete
• to allow readers to tolerate concurrent insertions and deletions: maintaining multiple versions of recent updated objects.

Part I. Publish-Subscribe Mechanism (insertion)

using example from²

1
2
3
4
5
6
7
8

struct foo {
    int a;
    int b;
    int c;
};
struct foo *gp = NULL; // a global pointer
p = kmalloc(sizeof(*p), GFP_KERNEL)
// SNIP

1
2
3
4

p->a = 1;
p->b = 2;
p->c = 3;
gp = p;     // not fences here

1
2
3
4

p->a = 1;
p->b = 2;
p->c = 3;
rcu_assign_pointer(gp, p); // guaranteed after initialzation

1
2
3
4
5
6
7

lp = gp; // local reference to the global data

if (lp != NULL) {
    // could be speculation;
    // dereferencing
    do_something_with(p->a, p->b, p->c);
}

1
2
3
4
5
6

rcu_read_lock();
p = rcu_dereference(gp);
if (p != NULL) {
    do_something_with(p-a, p->b, p->c);
}
rcu_read_unlock();

• the rcu_read_{lock,unlock} never spin or block, nor do they prevent the list_add_rcu() from executing concurrently.
• rcu_{assign_pointer, dereference} can be used to construct RCU-protected structure but better to use higher-level constructs.

linked list w/ RCU

Linux has 2 variants of doubly linked list: circular struct list_head (the first and last elements are linked via their next/prev pointers) and linear struct hlist_headr/struct hlist_nod.

Publishing a new element to an RCU-protected hlist:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

typedef struct foo {
    struct list_head list;
    int a;
    int b;
    int c;
} node;
LIST_HEAD(head) // create a global linked list
node *p = NULL;

// SNIP

// create and initialize a new node;
p = kmalloc(sizeof(*p), GFP_KERNEL);
p->a = 1;
p->b = 2;
p->c = 3;

// insert the node into the list.
list_add_rcu(&p->list, &head); // must be procted w/ sync

Subscribe to an RCU-protected hlist:

1
2
3
4
5

rcu_read_lock();
hlist_for_each_entry_rcu(p, head, list) {
    do_something_with(p->a, p->b, p->c);
}
rcu_read_unlock();

Part II. Wait for Pre-Existing Readers to Complete (deletion)

RCU decide when things have finished indirectly .PREEMPT, NON_PREEMPT and RT kernels’ RCU work differently.

• on NON_PREEMPT kernels the rcu_read_lock() and rcu_read_unlock() don’t generate any code. synchronize_cpu() works by forcing each CPU to execute at least one context switch.
• for PREEMPT_RT kernel, realtime RCU uses a different approach based loosely on reference counters.

Part III. Multiple Versions of Recent Updated Objects

APIs

void list_add_rcu(struct list_head * new, struct list_head * head);

add a new entry to rcu-protected list

hlist_bl_for_each_entry_rcu (tpos, pos, head, member)

macro

tpos: type * to use as a loop cursor

pos: sturct hlist_bl_node to use as a loop cursor

head: the head for the list

member: the name of hlist_bl_node within the struct