Documentation/RCU/rcu_dereference.txt

   1 PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference()
   2
   3 Most of the time, you can use values from rcu_dereference() or one of
   4 the similar primitives without worries.  Dereferencing (prefix "*"),
   5 field selection ("->"), assignment ("="), address-of ("&"), addition and
   6 subtraction of constants, and casts all work quite naturally and safely.
   7
   8 It is nevertheless possible to get into trouble with other operations.
   9 Follow these rules to keep your RCU code working properly:
  10
  11 o       You must use one of the rcu_dereference() family of primitives
  12         to load an RCU-protected pointer, otherwise CONFIG_PROVE_RCU
  13         will complain.  Worse yet, your code can see random memory-corruption
  14         bugs due to games that compilers and DEC Alpha can play.
  15         Without one of the rcu_dereference() primitives, compilers
  16         can reload the value, and won't your code have fun with two
  17         different values for a single pointer!  Without rcu_dereference(),
  18         DEC Alpha can load a pointer, dereference that pointer, and
  19         return data preceding initialization that preceded the store of
  20         the pointer.
  21
  22         In addition, the volatile cast in rcu_dereference() prevents the
  23         compiler from deducing the resulting pointer value.  Please see
  24         the section entitled "EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH"
  25         for an example where the compiler can in fact deduce the exact
  26         value of the pointer, and thus cause misordering.
  27
  28 o       Avoid cancellation when using the "+" and "-" infix arithmetic
  29         operators.  For example, for a given variable "x", avoid
  30         "(x-x)".  There are similar arithmetic pitfalls from other
  31         arithmetic operators, such as "(x*0)", "(x/(x+1))" or "(x%1)".
  32         The compiler is within its rights to substitute zero for all of
  33         these expressions, so that subsequent accesses no longer depend
  34         on the rcu_dereference(), again possibly resulting in bugs due
  35         to misordering.
  36
  37         Of course, if "p" is a pointer from rcu_dereference(), and "a"
  38         and "b" are integers that happen to be equal, the expression
  39         "p+a-b" is safe because its value still necessarily depends on
  40         the rcu_dereference(), thus maintaining proper ordering.
  41
  42 o       Avoid all-zero operands to the bitwise "&" operator, and
  43         similarly avoid all-ones operands to the bitwise "|" operator.
  44         If the compiler is able to deduce the value of such operands,
  45         it is within its rights to substitute the corresponding constant
  46         for the bitwise operation.  Once again, this causes subsequent
  47         accesses to no longer depend on the rcu_dereference(), causing
  48         bugs due to misordering.
  49
  50         Please note that single-bit operands to bitwise "&" can also
  51         be dangerous.  At this point, the compiler knows that the
  52         resulting value can only take on one of two possible values.
  53         Therefore, a very small amount of additional information will
  54         allow the compiler to deduce the exact value, which again can
  55         result in misordering.
  56
  57 o       If you are using RCU to protect JITed functions, so that the
  58         "()" function-invocation operator is applied to a value obtained
  59         (directly or indirectly) from rcu_dereference(), you may need to
  60         interact directly with the hardware to flush instruction caches.
  61         This issue arises on some systems when a newly JITed function is
  62         using the same memory that was used by an earlier JITed function.
  63
  64 o       Do not use the results from the boolean "&&" and "||" when
  65         dereferencing.  For example, the following (rather improbable)
  66         code is buggy:
  67
  68                 int *p;
  69                 int *q;
  70
  71                 ...
  72
  73                 p = rcu_dereference(gp)
  74                 q = &global_q;
  75                 q += p != &oom_p1 && p != &oom_p2;
  76                 r1 = *q;  /* BUGGY!!! */
  77
  78         The reason this is buggy is that "&&" and "||" are often compiled
  79         using branches.  While weak-memory machines such as ARM or PowerPC
  80         do order stores after such branches, they can speculate loads,
  81         which can result in misordering bugs.
  82
  83 o       Do not use the results from relational operators ("==", "!=",
  84         ">", ">=", "<", or "<=") when dereferencing.  For example,
  85         the following (quite strange) code is buggy:
  86
  87                 int *p;
  88                 int *q;
  89
  90                 ...
  91
  92                 p = rcu_dereference(gp)
  93                 q = &global_q;
  94                 q += p > &oom_p;
  95                 r1 = *q;  /* BUGGY!!! */
  96
  97         As before, the reason this is buggy is that relational operators
  98         are often compiled using branches.  And as before, although
  99         weak-memory machines such as ARM or PowerPC do order stores
 100         after such branches, but can speculate loads, which can again
 101         result in misordering bugs.
 102
 103 o       Be very careful about comparing pointers obtained from
 104         rcu_dereference() against non-NULL values.  As Linus Torvalds
 105         explained, if the two pointers are equal, the compiler could
 106         substitute the pointer you are comparing against for the pointer
 107         obtained from rcu_dereference().  For example:
 108
 109                 p = rcu_dereference(gp);
 110                 if (p == &default_struct)
 111                         do_default(p->a);
 112
 113         Because the compiler now knows that the value of "p" is exactly
 114         the address of the variable "default_struct", it is free to
 115         transform this code into the following:
 116
 117                 p = rcu_dereference(gp);
 118                 if (p == &default_struct)
 119                         do_default(default_struct.a);
 120
 121         On ARM and Power hardware, the load from "default_struct.a"
 122         can now be speculated, such that it might happen before the
 123         rcu_dereference().  This could result in bugs due to misordering.
 124
 125         However, comparisons are OK in the following cases:
 126
 127         o       The comparison was against the NULL pointer.  If the
 128                 compiler knows that the pointer is NULL, you had better
 129                 not be dereferencing it anyway.  If the comparison is
 130                 non-equal, the compiler is none the wiser.  Therefore,
 131                 it is safe to compare pointers from rcu_dereference()
 132                 against NULL pointers.
 133
 134         o       The pointer is never dereferenced after being compared.
 135                 Since there are no subsequent dereferences, the compiler
 136                 cannot use anything it learned from the comparison
 137                 to reorder the non-existent subsequent dereferences.
 138                 This sort of comparison occurs frequently when scanning
 139                 RCU-protected circular linked lists.
 140
 141         o       The comparison is against a pointer that references memory
 142                 that was initialized "a long time ago."  The reason
 143                 this is safe is that even if misordering occurs, the
 144                 misordering will not affect the accesses that follow
 145                 the comparison.  So exactly how long ago is "a long
 146                 time ago"?  Here are some possibilities:
 147
 148                 o       Compile time.
 149
 150                 o       Boot time.
 151
 152                 o       Module-init time for module code.
 153
 154                 o       Prior to kthread creation for kthread code.
 155
 156                 o       During some prior acquisition of the lock that
 157                         we now hold.
 158
 159                 o       Before mod_timer() time for a timer handler.
 160
 161                 There are many other possibilities involving the Linux
 162                 kernel's wide array of primitives that cause code to
 163                 be invoked at a later time.
 164
 165         o       The pointer being compared against also came from
 166                 rcu_dereference().  In this case, both pointers depend
 167                 on one rcu_dereference() or another, so you get proper
 168                 ordering either way.
 169
 170                 That said, this situation can make certain RCU usage
 171                 bugs more likely to happen.  Which can be a good thing,
 172                 at least if they happen during testing.  An example
 173                 of such an RCU usage bug is shown in the section titled
 174                 "EXAMPLE OF AMPLIFIED RCU-USAGE BUG".
 175
 176         o       All of the accesses following the comparison are stores,
 177                 so that a control dependency preserves the needed ordering.
 178                 That said, it is easy to get control dependencies wrong.
 179                 Please see the "CONTROL DEPENDENCIES" section of
 180                 Documentation/memory-barriers.txt for more details.
 181
 182         o       The pointers are not equal -and- the compiler does
 183                 not have enough information to deduce the value of the
 184                 pointer.  Note that the volatile cast in rcu_dereference()
 185                 will normally prevent the compiler from knowing too much.
 186
 187                 However, please note that if the compiler knows that the
 188                 pointer takes on only one of two values, a not-equal
 189                 comparison will provide exactly the information that the
 190                 compiler needs to deduce the value of the pointer.
 191
 192 o       Disable any value-speculation optimizations that your compiler
 193         might provide, especially if you are making use of feedback-based
 194         optimizations that take data collected from prior runs.  Such
 195         value-speculation optimizations reorder operations by design.
 196
 197         There is one exception to this rule:  Value-speculation
 198         optimizations that leverage the branch-prediction hardware are
 199         safe on strongly ordered systems (such as x86), but not on weakly
 200         ordered systems (such as ARM or Power).  Choose your compiler
 201         command-line options wisely!
 202
 203
 204 EXAMPLE OF AMPLIFIED RCU-USAGE BUG
 205
 206 Because updaters can run concurrently with RCU readers, RCU readers can
 207 see stale and/or inconsistent values.  If RCU readers need fresh or
 208 consistent values, which they sometimes do, they need to take proper
 209 precautions.  To see this, consider the following code fragment:
 210
 211         struct foo {
 212                 int a;
 213                 int b;
 214                 int c;
 215         };
 216         struct foo *gp1;
 217         struct foo *gp2;
 218
 219         void updater(void)
 220         {
 221                 struct foo *p;
 222
 223                 p = kmalloc(...);
 224                 if (p == NULL)
 225                         deal_with_it();
 226                 p->a = 42;  /* Each field in its own cache line. */
 227                 p->b = 43;
 228                 p->c = 44;
 229                 rcu_assign_pointer(gp1, p);
 230                 p->b = 143;
 231                 p->c = 144;
 232                 rcu_assign_pointer(gp2, p);
 233         }
 234
 235         void reader(void)
 236         {
 237                 struct foo *p;
 238                 struct foo *q;
 239                 int r1, r2;
 240
 241                 p = rcu_dereference(gp2);
 242                 if (p == NULL)
 243                         return;
 244                 r1 = p->b;  /* Guaranteed to get 143. */
 245                 q = rcu_dereference(gp1);  /* Guaranteed non-NULL. */
 246                 if (p == q) {
 247                         /* The compiler decides that q->c is same as p->c. */
 248                         r2 = p->c; /* Could get 44 on weakly order system. */
 249                 }
 250                 do_something_with(r1, r2);
 251         }
 252
 253 You might be surprised that the outcome (r1 == 143 && r2 == 44) is possible,
 254 but you should not be.  After all, the updater might have been invoked
 255 a second time between the time reader() loaded into "r1" and the time
 256 that it loaded into "r2".  The fact that this same result can occur due
 257 to some reordering from the compiler and CPUs is beside the point.
 258
 259 But suppose that the reader needs a consistent view?
 260
 261 Then one approach is to use locking, for example, as follows:
 262
 263         struct foo {
 264                 int a;
 265                 int b;
 266                 int c;
 267                 spinlock_t lock;
 268         };
 269         struct foo *gp1;
 270         struct foo *gp2;
 271
 272         void updater(void)
 273         {
 274                 struct foo *p;
 275
 276                 p = kmalloc(...);
 277                 if (p == NULL)
 278                         deal_with_it();
 279                 spin_lock(&p->lock);
 280                 p->a = 42;  /* Each field in its own cache line. */
 281                 p->b = 43;
 282                 p->c = 44;
 283                 spin_unlock(&p->lock);
 284                 rcu_assign_pointer(gp1, p);
 285                 spin_lock(&p->lock);
 286                 p->b = 143;
 287                 p->c = 144;
 288                 spin_unlock(&p->lock);
 289                 rcu_assign_pointer(gp2, p);
 290         }
 291
 292         void reader(void)
 293         {
 294                 struct foo *p;
 295                 struct foo *q;
 296                 int r1, r2;
 297
 298                 p = rcu_dereference(gp2);
 299                 if (p == NULL)
 300                         return;
 301                 spin_lock(&p->lock);
 302                 r1 = p->b;  /* Guaranteed to get 143. */
 303                 q = rcu_dereference(gp1);  /* Guaranteed non-NULL. */
 304                 if (p == q) {
 305                         /* The compiler decides that q->c is same as p->c. */
 306                         r2 = p->c; /* Locking guarantees r2 == 144. */
 307                 }
 308                 spin_unlock(&p->lock);
 309                 do_something_with(r1, r2);
 310         }
 311
 312 As always, use the right tool for the job!
 313
 314
 315 EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH
 316
 317 If a pointer obtained from rcu_dereference() compares not-equal to some
 318 other pointer, the compiler normally has no clue what the value of the
 319 first pointer might be.  This lack of knowledge prevents the compiler
 320 from carrying out optimizations that otherwise might destroy the ordering
 321 guarantees that RCU depends on.  And the volatile cast in rcu_dereference()
 322 should prevent the compiler from guessing the value.
 323
 324 But without rcu_dereference(), the compiler knows more than you might
 325 expect.  Consider the following code fragment:
 326
 327         struct foo {
 328                 int a;
 329                 int b;
 330         };
 331         static struct foo variable1;
 332         static struct foo variable2;
 333         static struct foo *gp = &variable1;
 334
 335         void updater(void)
 336         {
 337                 initialize_foo(&variable2);
 338                 rcu_assign_pointer(gp, &variable2);
 339                 /*
 340                  * The above is the only store to gp in this translation unit,
 341                  * and the address of gp is not exported in any way.
 342                  */
 343         }
 344
 345         int reader(void)
 346         {
 347                 struct foo *p;
 348
 349                 p = gp;
 350                 barrier();
 351                 if (p == &variable1)
 352                         return p->a; /* Must be variable1.a. */
 353                 else
 354                         return p->b; /* Must be variable2.b. */
 355         }
 356
 357 Because the compiler can see all stores to "gp", it knows that the only
 358 possible values of "gp" are "variable1" on the one hand and "variable2"
 359 on the other.  The comparison in reader() therefore tells the compiler
 360 the exact value of "p" even in the not-equals case.  This allows the
 361 compiler to make the return values independent of the load from "gp",
 362 in turn destroying the ordering between this load and the loads of the
 363 return values.  This can result in "p->b" returning pre-initialization
 364 garbage values.
 365
 366 In short, rcu_dereference() is -not- optional when you are going to
 367 dereference the resulting pointer.