1Review Checklist for RCU Patches
   4This document contains a checklist for producing and reviewing patches
   5that make use of RCU.  Violating any of the rules listed below will
   6result in the same sorts of problems that leaving out a locking primitive
   7would cause.  This list is based on experiences reviewing such patches
   8over a rather long period of time, but improvements are always welcome!
  100.      Is RCU being applied to a read-mostly situation?  If the data
  11        structure is updated more than about 10% of the time, then you
  12        should strongly consider some other approach, unless detailed
  13        performance measurements show that RCU is nonetheless the right
  14        tool for the job.  Yes, RCU does reduce read-side overhead by
  15        increasing write-side overhead, which is exactly why normal uses
  16        of RCU will do much more reading than updating.
  18        Another exception is where performance is not an issue, and RCU
  19        provides a simpler implementation.  An example of this situation
  20        is the dynamic NMI code in the Linux 2.6 kernel, at least on
  21        architectures where NMIs are rare.
  23        Yet another exception is where the low real-time latency of RCU's
  24        read-side primitives is critically important.
  261.      Does the update code have proper mutual exclusion?
  28        RCU does allow -readers- to run (almost) naked, but -writers- must
  29        still use some sort of mutual exclusion, such as:
  31        a.      locking,
  32        b.      atomic operations, or
  33        c.      restricting updates to a single task.
  35        If you choose #b, be prepared to describe how you have handled
  36        memory barriers on weakly ordered machines (pretty much all of
  37        them -- even x86 allows later loads to be reordered to precede
  38        earlier stores), and be prepared to explain why this added
  39        complexity is worthwhile.  If you choose #c, be prepared to
  40        explain how this single task does not become a major bottleneck on
  41        big multiprocessor machines (for example, if the task is updating
  42        information relating to itself that other tasks can read, there
  43        by definition can be no bottleneck).
  452.      Do the RCU read-side critical sections make proper use of
  46        rcu_read_lock() and friends?  These primitives are needed
  47        to prevent grace periods from ending prematurely, which
  48        could result in data being unceremoniously freed out from
  49        under your read-side code, which can greatly increase the
  50        actuarial risk of your kernel.
  52        As a rough rule of thumb, any dereference of an RCU-protected
  53        pointer must be covered by rcu_read_lock(), rcu_read_lock_bh(),
  54        rcu_read_lock_sched(), or by the appropriate update-side lock.
  55        Disabling of preemption can serve as rcu_read_lock_sched(), but
  56        is less readable.
  583.      Does the update code tolerate concurrent accesses?
  60        The whole point of RCU is to permit readers to run without
  61        any locks or atomic operations.  This means that readers will
  62        be running while updates are in progress.  There are a number
  63        of ways to handle this concurrency, depending on the situation:
  65        a.      Use the RCU variants of the list and hlist update
  66                primitives to add, remove, and replace elements on
  67                an RCU-protected list.  Alternatively, use the other
  68                RCU-protected data structures that have been added to
  69                the Linux kernel.
  71                This is almost always the best approach.
  73        b.      Proceed as in (a) above, but also maintain per-element
  74                locks (that are acquired by both readers and writers)
  75                that guard per-element state.  Of course, fields that
  76                the readers refrain from accessing can be guarded by
  77                some other lock acquired only by updaters, if desired.
  79                This works quite well, also.
  81        c.      Make updates appear atomic to readers.  For example,
  82                pointer updates to properly aligned fields will
  83                appear atomic, as will individual atomic primitives.
  84                Sequences of perations performed under a lock will -not-
  85                appear to be atomic to RCU readers, nor will sequences
  86                of multiple atomic primitives.
  88                This can work, but is starting to get a bit tricky.
  90        d.      Carefully order the updates and the reads so that
  91                readers see valid data at all phases of the update.
  92                This is often more difficult than it sounds, especially
  93                given modern CPUs' tendency to reorder memory references.
  94                One must usually liberally sprinkle memory barriers
  95                (smp_wmb(), smp_rmb(), smp_mb()) through the code,
  96                making it difficult to understand and to test.
  98                It is usually better to group the changing data into
  99                a separate structure, so that the change may be made
 100                to appear atomic by updating a pointer to reference
 101                a new structure containing updated values.
 1034.      Weakly ordered CPUs pose special challenges.  Almost all CPUs
 104        are weakly ordered -- even x86 CPUs allow later loads to be
 105        reordered to precede earlier stores.  RCU code must take all of
 106        the following measures to prevent memory-corruption problems:
 108        a.      Readers must maintain proper ordering of their memory
 109                accesses.  The rcu_dereference() primitive ensures that
 110                the CPU picks up the pointer before it picks up the data
 111                that the pointer points to.  This really is necessary
 112                on Alpha CPUs.  If you don't believe me, see:
 116                The rcu_dereference() primitive is also an excellent
 117                documentation aid, letting the person reading the code
 118                know exactly which pointers are protected by RCU.
 119                Please note that compilers can also reorder code, and
 120                they are becoming increasingly aggressive about doing
 121                just that.  The rcu_dereference() primitive therefore
 122                also prevents destructive compiler optimizations.
 124                The rcu_dereference() primitive is used by the
 125                various "_rcu()" list-traversal primitives, such
 126                as the list_for_each_entry_rcu().  Note that it is
 127                perfectly legal (if redundant) for update-side code to
 128                use rcu_dereference() and the "_rcu()" list-traversal
 129                primitives.  This is particularly useful in code that
 130                is common to readers and updaters.  However, lockdep
 131                will complain if you access rcu_dereference() outside
 132                of an RCU read-side critical section.  See lockdep.txt
 133                to learn what to do about this.
 135                Of course, neither rcu_dereference() nor the "_rcu()"
 136                list-traversal primitives can substitute for a good
 137                concurrency design coordinating among multiple updaters.
 139        b.      If the list macros are being used, the list_add_tail_rcu()
 140                and list_add_rcu() primitives must be used in order
 141                to prevent weakly ordered machines from misordering
 142                structure initialization and pointer planting.
 143                Similarly, if the hlist macros are being used, the
 144                hlist_add_head_rcu() primitive is required.
 146        c.      If the list macros are being used, the list_del_rcu()
 147                primitive must be used to keep list_del()'s pointer
 148                poisoning from inflicting toxic effects on concurrent
 149                readers.  Similarly, if the hlist macros are being used,
 150                the hlist_del_rcu() primitive is required.
 152                The list_replace_rcu() and hlist_replace_rcu() primitives
 153                may be used to replace an old structure with a new one
 154                in their respective types of RCU-protected lists.
 156        d.      Rules similar to (4b) and (4c) apply to the "hlist_nulls"
 157                type of RCU-protected linked lists.
 159        e.      Updates must ensure that initialization of a given
 160                structure happens before pointers to that structure are
 161                publicized.  Use the rcu_assign_pointer() primitive
 162                when publicizing a pointer to a structure that can
 163                be traversed by an RCU read-side critical section.
 1655.      If call_rcu(), or a related primitive such as call_rcu_bh(),
 166        call_rcu_sched(), or call_srcu() is used, the callback function
 167        must be written to be called from softirq context.  In particular,
 168        it cannot block.
 1706.      Since synchronize_rcu() can block, it cannot be called from
 171        any sort of irq context.  The same rule applies for
 172        synchronize_rcu_bh(), synchronize_sched(), synchronize_srcu(),
 173        synchronize_rcu_expedited(), synchronize_rcu_bh_expedited(),
 174        synchronize_sched_expedite(), and synchronize_srcu_expedited().
 176        The expedited forms of these primitives have the same semantics
 177        as the non-expedited forms, but expediting is both expensive
 178        and unfriendly to real-time workloads.  Use of the expedited
 179        primitives should be restricted to rare configuration-change
 180        operations that would not normally be undertaken while a real-time
 181        workload is running.
 183        In particular, if you find yourself invoking one of the expedited
  85Reointer to ial ry use structu cabewing efully order,ven x8rom misordering
  86 updates      as the noreference()onter moking he ist ewind is running.
 176  88 as the noreferenced_expe atom chaCU wiCU wecomctivn update-writers- must
 179nvokingsysizman it soundsd unfriendly to real-tia>       lback function
  90update-w9nvokingsysizmd is running.
  92Ihat h    b,.  Not ato perf)onte mut/a>        The expet be called from
  93     -hotplugs thifitersU reunderholdhen pumed uructu se other l called from
  94e tr    -hotplugs thifiteme Failbut is obemptiotoints   c.   lback function
  95 atom      couldead it cannot block.
  48 183      Y3Lr   ioand be prel risk 3olass="linclass="02 made
 "> 183e="L6t##L19" id="L1"> 18 class="la>      Y3Lr   ioand be prel risk 3olass="lin NMIs arelues.
 ng a>      Y3Lr   ioand be prel risk 3olass="lin="L22">  2
  55       3e="L6t##L19" id="L1"        24        read-side primitives is criticter loads2to be
        sy class="line" nsynchronize_rcu_expedited(), synchronize_rcu2ust take 2ll of
  48        any sort of irq context.  The same 2"L107"> 127
  92Ih="L46">  4676   as#L14" idir id="L86" clas        any sort of irq context.  The same 2" -writersemory
 me="L8 157                type of RCU-protect2cks up th2 data
 160d="L1le:t.txt#L46" id="L46" cxt##L19" id="L19"cklist.tx1t#L91" id="L91" class="l1ine" 19e2l="L22">   see:
 136 "> 183e="L6t##L19" id="L1"> 18cklist.tx1t#L91" id="L91" class="l1ine" 19e2llmost al23
  "line"="L"l1_looku hal  46alL19"y id="n      are weakly ordered -- even x86 CPUs allow l2z_2637.ht2l
n"L171 1am="L167"> 167 Comeredial ry use structu cabewing efully order,ven x2"L115"> 125
91">  hotpss="l, id="L135"!me="ame="Ljuryline" 1t#L nam is the dynamic NMI code in the Linux 2.6 kernetion pro2llent
he 49  d"linedid="L39" "L9> 157                type of RCU-protect2cL107"> 12 code
n"d="L19"  cla9" co 12   id="L5ine" name="a>      Y3Lr   ioand be prel risk 3olass="lifks up th2east on
  oss="line" naame="L" id="L16synchronize_rcu_expedited(), synchronize_rcu2e NMIs are  rare.
   pme="L135"1ine" 1ae="L126ynchronize_rcu_expedited(), synchronize_rcu2e="L22">   22
   name=ty id="L90" L172" id="L17ssklist.txt#L123" id="L123" class="line" name2n_2637.ht2ortant.
 12 25
 12 27
  s="l1ine""L179" .txtici27" c nam  id="L5L99" iis the dynamic NMI code in the Linux 2.6 kernt -writerss- must
  "line"d="L47" class=delay    171<" na="liOOM > 192" id"> 157                type of RCU-protect2owever, l2ckdep
  s="l1inecklist.tx1t#L91" id="L91" class="l1ine" 19e2r="L22">  222
.tu n id="L90    be id=d="a-t#L85" id=    klist.txt#L134" id="L134" class="line" name2"L115"> 12quot;
   8" id="L68" class="line" name,x49     ="L47" clasname=lapsa9" Etxt#e" n ry use structu cabewing efully order,ven x2tL107"> 12ters.
     be,e" n="d="Lne" name=s>      e="L1 to  ry use structu cabewing efully order,ven x2t -writers8
de="Lr.    eass="l.txt#Lme="Lname="L67">  6 ry use structu cabewing efully order,ven x2_add_tail2rcu()
    > 157                type of RCU-protect2rom misor2ering
  /a>    sp"L  93 --="L77"   Weakly ordered CPUs pose special challenges. 2ve is req2ired.
  63    93 .txt#L"L141" ca>   ="L47" clasakly ordered CPUs pose special challenges. 2vL115"> 125
  .)tx=""L77" wa"l1in" n="s="line" namakly ordered CPUs pose special challenges. 2vute for 2rcu()
1 tocatorne" name="L9>  /rlassr     callakly ordered CPUs pose special challenges. 2v -writersrrent
  62  id="L135" mt#L1            an RCU-protected list.  Alternativel2ve is req2ired.
 .txt          readers see valid data at all phase2"L151"> 121
        c83" 2" classoccur  tlyhecklist.txt#L22" id="L22" class="line" nameceing use2w one
 150  "L85"" clas16"> 1L19"y baclasbro80< class=dcac"la>      Y3Lr   ioand be prel risk 3olass="li"L155"> 125
 71">  71 --=" class="lin>      a>      Y3Lr   ioand be prel risk 3olass="li"ute for 2quot;
      Y3Lr   ioand be prel risk 3olass="lit structu2e are
u" c29"r1 1L19"y h=s>loline" t#L63" icras  various "_rcu()" list-traversal 2ucture th2t can
 me="L183"> 183L99he" 187=L165" id="L16in" class=o1 180klist.txt#L164" id="L164" class="line" name2"L155"> 12bh(),
 18a>     l1ine" d="L47" class         readers see valid data at all phase2iute for 2ction
 156 183e="Lme="L183"e="L172         readers see valid data at all phase2"er() pri2s for
 125           ss="li49 ,26" class="line" name="L126 ry use structu cabewing efully order,ven x2cu_expedi2ed().
 163      3      Y3Lr   ioand be prel risk 3olass="li same sem2ntics
 118  ame="L54">  54        rce="L105a>      Y3Lr   ioand be prel risk 3olass="li In parti2nsive
 163      s=del nam  a>  .txt#L46" id="La>      Y3Lr   ioand be prel risk 3olass="li  cannot 2dited
 1a>      Y3Lr   ioand be prel risk 3olass="liguration-2hange
 "> 183e="L6t##L19" id="L1"> 1816in"ss="li91">a>      Y3Lr   ioand be prel risk 3olass="ligbe calle2-time
 140                and list_add_rcu() primitives must 2oad is ru2ning.
 18         and list_add_rcu() primitives must 2oronize_s22
  90s the >       ne" nassib es="l29" ne" "lin25"> 125 12ering
 1dlablo180"ng m"L130"  1dla           as the list_for_each_entry_rcu(). 2ind is ru2ning.
  ss="line" name="L130"> AL92" id                  as the list_for_each_entry_rcu(). 2iIn parti2, the
viddiscus                       and list_add_rcu() primitives must 2o cannot 2 must
 163      6 ry use structu cabewing efully order,ven x2zmd is ru2ning.
  54        rc,cne" -140"    Sequences of perations performed under a2"L151"> 121
 128      lass=nt  91 ed u"> 149 120 neL99" bad               (smp_wmb(), smp_rmb(), smp_mb()) t2r l calle2 from
 me47" o    nam1ame="Lname="L85" cla         and list_add_rcu() primitives must 2 lback fu2ction
  55 1>   =nteaklist.txt#L123" id="L123" class="line" name2= cannot 2, the
 1okingsys" nam106<   NMI   "L55" c_dtxt#Le"La>      Y3Lr   ioand be prel risk 3olass="l3nclass="03 made
 1s id="L131" Lme="LT        ne" nlinedos" id6"> a>      Y3Lr   ioand be prel risk 3olass="l3n1lass="03 ing.
  55 163      s,edos        Sequences of perations performed under a3n NMIs ar3lues.
   id"L11cL23"t#Le=136"> 136 18 clC         att5" css="l29" "L55" clasklist.txt#L123" id="L123" class="line" name3A6most al3 ock.
  9L179" cla0  55 137
  ="liaam at "" nam106">he 49flu135"191<"L55" c_dtxt#Le"L,cne" inst>     iorrencyr   a.      R                rcu3v1lass="03 data
 3 see:
    140"> 14plugs thaelse"linehecklist.txt#L72" id="L72" class="line" nam3llmost al33
 "167s"> 126 ry use structu cabewing efully order,ven x3z_2637.ht3l
 "> 1816etcl1ine" 1ame="Ldtxt#Le=L171 n>        e.      Updates must ensure that initializ3"L115"> 135
so n>           as the list_for_each_entry_rcu(). 3etion pro3llent
    ine"          as the list_for_each_entry_rcu(). 3eL107"> 13 code
 163                be traversed by an RCU read-side c3otected b3 RCU.
   sxt#76   p  =llela>    mt#L191"> 6 ry use structu cabewing efully order,ven x3fks up th3east on
   id"L1issue (ornem" naaccuratcline56 extent                as the list_for_each_entry_rcu(). 3e="L22"> 3 22
          as the list_for_each_entry_rcu(). 3elmost al3U's
   sxdosmt#ipulcla   shae" nss="line" name,xid="         as the list_for_each_entry_rcu(). 3e_2637.ht3ortant.
 150 13 25
 13 27
   sx"2" -L98" cl- execut/a>3   nameL110l0   ys   -8 9a="l>   =ntead      .1        c83"         e.      Updates must ensure that initializ3owever, l3ckdep
    p63">  ,l ng mul        primitives.  This is particularly use3rence() o3tside
    i1t#Lexecut/>3  /           as the list_for_each_entry_rcu(). 3r="L22"> 3222
    itxt#L"L141" ca>          as the list_for_each_entry_rcu(). 3rlmost al3this.
      Y3Lr   ioand be prel risk 3olass="l3"L134"> 134
  4,xsxt##L19" id="L19"las.txtname="L135"> ,klist.txt#L175" id="L175" class="line" name3"tion pro3 good
 174        syn,3e="Lme="L    syLa>      Y3Lr   ioand be prel risk 3olass="l3"L107"> 13ters.
 167 Un7" c "L77" 76" clasa>      Y3Lr   ioand be prel risk 3olass="l3"tected b38
 163      Y3Lr   ioand be prel risk 3olass="l3_add_tail3rcu()
  48 Sne"128"> :e128"> sleept#Le=ne"128"> a> Pe="L1rn126   line"klist.txt#L175" id="L175" class="line" name3_ence() o3ering
 163      s,ene" 9L179" clklist.txt#L175" id="L175" class="line" name3_="L22"> 3ting.
 1mos  t=t#L63l1ine"klist.txt#L175" id="L175" class="line" name3_lmost al3, the
 163      3 l"lklist.txt#L145" id="L145" class="line" name3vtion pro3rcu()
   name=ame="L16klist.txt#L123" id="L123" class="line" name3vL107"> 13inter
 1nine"     klist.txt#L123" id="L123" class="line" name3vtected b3rrent
 "raw 48 131
 159klist.txt#L151" id="L151" class="line" name3"="L22"> 3tives
 150  pasae128"> s#L85"  183"e#L85"les similar to (4b) and (4c) apply to the "h3rotected 3ists.
  sco="L157       iSne" domai< clO35"1me="L159" 135
="ls 19me="L48">  4,xsxt##L19" id="L19" ry use structu cabewing efully order,ven x3"tion pro3quot;
 174        syn,3e="Lme="L    sy          be traversed by an RCU read-side c3vL107"> 13ists.
 163      Y3Lr   ioand be prel risk 3olass="l3"L158"> 138
  48      Y3Lr   ioand be prel risk 3olass="l3tion of a3given
 1ba>  eas=6    183"e#L85" clastr prame=tya>      Y3Lr   ioand be prel risk 3olass="l3te is req3e are
 163      s=to nat#Le=-    Sequences of perations performed under a3ter() pri3itive
 178            an RCU-protected list.  Alternativel3ucture th3t can
/a>  pranes="lOOM a>          as the list_for_each_entry_rcu(). 3itical se3tion.
     98" ="L163"> 163      s         as the list_for_each_entry_rcu(). 3iotected 34
 e" e="L163"> 163      sa  assinla>      Y3Lr   ioand be prel risk 3olass="l3 In parti3ular,
  48=6    183"e#L85"    iorrencyr   a.      R                rcu3"L169"> 139
 o"> 2" classshaeme="L1     i1183"e#L85",5L99he" 187= ry use structu cabewing efully order,ven x3"er() pri3s for
  for "L77" 76" clasxpre    iorrencyr   a.      R                rcu3"cture th3cu(),
   pme="L135"1inerw_    phonehecklist.txt#L72" id="L72" class="line" nam3htical se3ed(),
 150d="LSprea>     98" ="L1635" classcimmunitysor   we=ame="L16klist.txt#L123" id="L123" class="line" name3cL155"> 135
    y    iorrencyr   a.      R                rcu3"ute for 3ntics
 161 yn,3e="L" id="sklist.txt#L107" id="L107" class="line" name3oad is ru3ning.
 1finish" naefonehecklist.txt#L72" id="L72" class="line" nam3oronize_s32
  ="l-fir"l-L98m"L8xt#L1p99h         as the list_for_each_entry_rcu(). 3fotected 3 see:
  a>          as the list_for_each_entry_rcu(). 3fL155"> 13ering
    "> yn,3t "  id="s    iorrencyr   a.      R                rcu3gIn parti3, the
      Y3Lr   ioand be prel risk 3olass="l3 lback fu3ction
 1ioaa>      Y3Lr   ioand be prel risk 3olass="l3 be calle3ning.
"afcla    iorrencyr   a.      R                rcu3"L151"> 131
 Ye" 9L179" t        spl#76fo>">he CP5a>      Y3Lr   ioand be prel risk 3olass="l3 lback fu3ction
 163      s="LI/a   x1t#L908" sibilitysoss="la>      Y3Lr   ioand be prel risk 3olass="l3="Lannot 3lock.
      " name="L17="Ld" 1"l1th176is    iorrencyr   a.      R                rcu3=In parti3, the
 CONFIG_PROVE_pre="CONFIG_DEBUG_OBJECTS_pre_HEAD    spa35"      17="Lvali="L85"ne" 6cla9" T  s<   iorrencyr   a.      R                rcu4n1lass="04 ing.
">he prame=L105a>      Y3Lr   ioand be prel risk 3olass="l4A5most al4 tion
 163      61ine" 1ame="L93x1t#Ligh"a>      Y3Lr   ioand be prel risk 3olass="l4A6most al4 ock.
 192" id"a>      Y3Lr   ioand be prel risk 3olass="l4A7most al4 ock.
ame="L54">     iorrencyr   a.      R                rcu4"L107"> 147
      Y3Lr   ioand be prel risk 3olass="l4ve ensure4 that
   obj   1ine" 1ae="L12 (or"  id="s)naefone=7="ne"a>      Y3Lr   ioand be prel risk 3olass="l4v1lass="04 data
=lapsad si35"1iine
      Y3Lr   ioand be prel risk 3olass="l4v NMIs ar4ssary
=6>   nameobj   1ine" 1ae="L12 (or"  id="s)    iorrencyr   a.      R                rcu4l="L22"> 4 see:

  spa35"      1: ta93x1t#1"> 161e56 R id="L68" class="hecklist.txt#L72" id="L72" class="line" nam4z_2637.ht4l
 ,3e="Lspa35" i1t#Lwarnine"  line"klist.txt#L175" id="L175" class="line" name4"L115"> 145
 161el1th nam=6     iorrencyr   a.      R                rcu4lL107"> 14 code

t#LXR "L13unitychec,4e tr      naa.  l 63"    3 ys">lxr@hreux.nochec. k="lclahos8 iorrenchttp://www.rede"">Rede" l Lrepro ASchec,48">vid 1" idame=7=d t#L180" is/aervicnamsi35"11995.