Overview Read-copy-update

read-copy-update insertion procedure. thread allocates structure 3 fields, sets global pointer gptr point structure.

a key property of rcu readers can access data structure when in process of being updated: rcu updaters cannot block readers or force them retry accesses. overview starts showing how data can safely inserted , deleted linked structures despite concurrent readers. first diagram on right depicts four-state insertion procedure, time advancing left right.

the first state shows global pointer named gptr null, colored red indicate might accessed reader @ time, requiring updaters take care. allocating memory new structure transitions second state. structure has indeterminate state (indicated question marks) inaccessible readers (indicated green color). because structure inaccessible readers, updater may carry out desired operation without fear of disrupting concurrent readers. initializing new structure transitions third state, shows initialized values of structure s fields. assigning reference new structure gptr transitions fourth , final state. in state, structure accessible readers, , therefore colored red. rcu_assign_pointer primitive used carry out assignment, , ensures assignment atomic in sense concurrent readers either see null pointer or valid pointer new structure, not mash-up of 2 values. additional properties of rcu_assign_pointer described later in article.

read-copy-update deletion procedure

this procedure demonstrates how new data may inserted linked data structure though readers concurrently traversing data structure before, during, , after insertion. second diagram on right depicts four-state deletion procedure, again time advancing left right.

the first state shows linked list containing elements a, b, , c. 3 elements colored red indicate rcu reader might reference of them @ time. using list_del_rcu remove element b list transitions second state. note link element b c left intact in order allow readers referencing element b traverse remainder of list. readers accessing link element either obtain reference element b or element c, either way, each reader see valid , correctly formatted linked list. element b colored yellow indicate while pre-existing readers might still have reference element b, new readers have no way obtain reference. wait-for-readers operation transitions third state. note wait-for-readers operation need wait pre-existing readers, not new readers. element b colored green indicate readers can no longer referencing it. therefore, safe updater free element b, transitioning fourth , final state.

it important reiterate in second state different readers can see 2 different versions of list, either or without element b. in other words, rcu provides coordination in space (different versions of list) in time (different states in deletion procedures). in stark contrast more traditional synchronization primitives such locking or transactions coordinate in time, not in space.

this procedure demonstrates how old data may removed linked data structure though readers concurrently traversing data structure before, during, , after deletion. given insertion , deletion, wide variety of data structures can implemented using rcu.

rcu s readers execute within read-side critical sections, delimited rcu_read_lock , rcu_read_unlock. statement not within rcu read-side critical section said in quiescent state, , such statements not permitted hold references rcu-protected data structures, nor wait-for-readers operation required wait threads in quiescent states. time period during each thread resides @ least once in quiescent state called grace period. definition, rcu read-side critical section in existence @ beginning of given grace period must complete before end of grace period, constitutes fundamental guarantee provided rcu. in addition, wait-for-readers operation must wait @ least 1 grace period elapse. turns out guarantee can provided extremely small read-side overheads, in fact, in limiting case realized server-class linux-kernel builds, read-side overhead zero.

rcu s fundamental guarantee may used splitting updates removal , reclamation phases. removal phase removes references data items within data structure (possibly replacing them references new versions of these data items), , can run concurrently rcu read-side critical sections. reason safe run removal phase concurrently rcu readers semantics of modern cpus guarantee readers see either old or new version of data structure rather partially updated reference. once grace period has elapsed, there can no longer readers referencing old version, safe reclamation phase free (reclaim) data items made old version.

splitting update removal , reclamation phases allows updater perform removal phase immediately, , defer reclamation phase until readers active during removal phase have completed, in other words, until grace period has elapsed.

so typical rcu update sequence goes following:

in above procedure (which matches earlier diagram), updater performing both removal , reclamation step, helpful entirely different thread reclamation. reference counting can used let reader perform removal so, if same thread performs both update step (step (2) above) , reclamation step (step (4) above), helpful think of them separately.

cite error: there <ref group=note> tags on page, references not show without {{reflist|group=note}} template (see page).