include/linux/rcupdate.h

   1 /*
   2  * Read-Copy Update mechanism for mutual exclusion
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17  *
  18  * Copyright IBM Corporation, 2001
  19  *
  20  * Author: Dipankar Sarma <dipankar@in.ibm.com>
  21  *
  22  * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
  23  * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
  24  * Papers:
  25  * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf
  26  * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
  27  *
  28  * For detailed explanation of Read-Copy Update mechanism see -
  29  *              http://lse.sourceforge.net/locking/rcupdate.html
  30  *
  31  */
  32
  33 #ifndef __LINUX_RCUPDATE_H
  34 #define __LINUX_RCUPDATE_H
  35
  36 #include <linux/cache.h>
  37 #include <linux/spinlock.h>
  38 #include <linux/threads.h>
  39 #include <linux/cpumask.h>
  40 #include <linux/seqlock.h>
  41 #include <linux/lockdep.h>
  42 #include <linux/completion.h>
  43
  44 #ifdef CONFIG_RCU_TORTURE_TEST
  45 extern int rcutorture_runnable; /* for sysctl */
  46 #endif /* #ifdef CONFIG_RCU_TORTURE_TEST */
  47
  48 /**
  49  * struct rcu_head - callback structure for use with RCU
  50  * @next: next update requests in a list
  51  * @func: actual update function to call after the grace period.
  52  */
  53 struct rcu_head {
  54         struct rcu_head *next;
  55         void (*func)(struct rcu_head *head);
  56 };
  57
  58 /* Exported common interfaces */
  59 extern void synchronize_rcu_bh(void);
  60 extern void synchronize_sched(void);
  61 extern void rcu_barrier(void);
  62 extern void rcu_barrier_bh(void);
  63 extern void rcu_barrier_sched(void);
  64 extern void synchronize_sched_expedited(void);
  65 extern int sched_expedited_torture_stats(char *page);
  66
  67 /* Internal to kernel */
  68 extern void rcu_init(void);
  69 extern int rcu_scheduler_active;
  70 extern void rcu_scheduler_starting(void);
  71
  72 #if defined(CONFIG_TREE_RCU) || defined(CONFIG_TREE_PREEMPT_RCU)
  73 #include <linux/rcutree.h>
  74 #elif defined(CONFIG_TINY_RCU)
  75 #include <linux/rcutiny.h>
  76 #else
  77 #error "Unknown RCU implementation specified to kernel configuration"
  78 #endif
  79
  80 #define RCU_HEAD_INIT   { .next = NULL, .func = NULL }
  81 #define RCU_HEAD(head) struct rcu_head head = RCU_HEAD_INIT
  82 #define INIT_RCU_HEAD(ptr) do { \
  83        (ptr)->next = NULL; (ptr)->func = NULL; \
  84 } while (0)
  85
  86 #ifdef CONFIG_DEBUG_LOCK_ALLOC
  87
  88 extern struct lockdep_map rcu_lock_map;
  89 # define rcu_read_acquire() \
  90                 lock_acquire(&rcu_lock_map, 0, 0, 2, 1, NULL, _THIS_IP_)
  91 # define rcu_read_release()     lock_release(&rcu_lock_map, 1, _THIS_IP_)
  92
  93 extern struct lockdep_map rcu_bh_lock_map;
  94 # define rcu_read_acquire_bh() \
  95                 lock_acquire(&rcu_bh_lock_map, 0, 0, 2, 1, NULL, _THIS_IP_)
  96 # define rcu_read_release_bh()  lock_release(&rcu_bh_lock_map, 1, _THIS_IP_)
  97
  98 extern struct lockdep_map rcu_sched_lock_map;
  99 # define rcu_read_acquire_sched() \
 100                 lock_acquire(&rcu_sched_lock_map, 0, 0, 2, 1, NULL, _THIS_IP_)
 101 # define rcu_read_release_sched() \
 102                 lock_release(&rcu_sched_lock_map, 1, _THIS_IP_)
 103
 104 static inline int debug_lockdep_rcu_enabled(void)
 105 {
 106         return likely(rcu_scheduler_active && debug_locks);
 107 }
 108
 109 /**
 110  * rcu_read_lock_held - might we be in RCU read-side critical section?
 111  *
 112  * If CONFIG_PROVE_LOCKING is selected and enabled, returns nonzero iff in
 113  * an RCU read-side critical section.  In absence of CONFIG_PROVE_LOCKING,
 114  * this assumes we are in an RCU read-side critical section unless it can
 115  * prove otherwise.
 116  *
 117  * Check rcu_scheduler_active to prevent false positives during boot.
 118  */
 119 static inline int rcu_read_lock_held(void)
 120 {
 121         if (!debug_lockdep_rcu_enabled())
 122                 return 1;
 123         return lock_is_held(&rcu_lock_map);
 124 }
 125
 126 /**
 127  * rcu_read_lock_bh_held - might we be in RCU-bh read-side critical section?
 128  *
 129  * If CONFIG_PROVE_LOCKING is selected and enabled, returns nonzero iff in
 130  * an RCU-bh read-side critical section.  In absence of CONFIG_PROVE_LOCKING,
 131  * this assumes we are in an RCU-bh read-side critical section unless it can
 132  * prove otherwise.
 133  *
 134  * Check rcu_scheduler_active to prevent false positives during boot.
 135  */
 136 static inline int rcu_read_lock_bh_held(void)
 137 {
 138         if (!debug_lockdep_rcu_enabled())
 139                 return 1;
 140         return lock_is_held(&rcu_bh_lock_map);
 141 }
 142
 143 /**
 144  * rcu_read_lock_sched_held - might we be in RCU-sched read-side critical section?
 145  *
 146  * If CONFIG_PROVE_LOCKING is selected and enabled, returns nonzero iff in an
 147  * RCU-sched read-side critical section.  In absence of CONFIG_PROVE_LOCKING,
 148  * this assumes we are in an RCU-sched read-side critical section unless it
 149  * can prove otherwise.  Note that disabling of preemption (including
 150  * disabling irqs) counts as an RCU-sched read-side critical section.
 151  *
 152  * Check rcu_scheduler_active to prevent false positives during boot.
 153  */
 154 #ifdef CONFIG_PREEMPT
 155 static inline int rcu_read_lock_sched_held(void)
 156 {
 157         int lockdep_opinion = 0;
 158
 159         if (!debug_lockdep_rcu_enabled())
 160                 return 1;
 161         if (debug_locks)
 162                 lockdep_opinion = lock_is_held(&rcu_sched_lock_map);
 163         return lockdep_opinion || preempt_count() != 0;
 164 }
 165 #else /* #ifdef CONFIG_PREEMPT */
 166 static inline int rcu_read_lock_sched_held(void)
 167 {
 168         return 1;
 169 }
 170 #endif /* #else #ifdef CONFIG_PREEMPT */
 171
 172 #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 173
 174 # define rcu_read_acquire()             do { } while (0)
 175 # define rcu_read_release()             do { } while (0)
 176 # define rcu_read_acquire_bh()          do { } while (0)
 177 # define rcu_read_release_bh()          do { } while (0)
 178 # define rcu_read_acquire_sched()       do { } while (0)
 179 # define rcu_read_release_sched()       do { } while (0)
 180
 181 static inline int rcu_read_lock_held(void)
 182 {
 183         return 1;
 184 }
 185
 186 static inline int rcu_read_lock_bh_held(void)
 187 {
 188         return 1;
 189 }
 190
 191 #ifdef CONFIG_PREEMPT
 192 static inline int rcu_read_lock_sched_held(void)
 193 {
 194         return !rcu_scheduler_active || preempt_count() != 0;
 195 }
 196 #else /* #ifdef CONFIG_PREEMPT */
 197 static inline int rcu_read_lock_sched_held(void)
 198 {
 199         return 1;
 200 }
 201 #endif /* #else #ifdef CONFIG_PREEMPT */
 202
 203 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 204
 205 #ifdef CONFIG_PROVE_RCU
 206
 207 /**
 208  * rcu_dereference_check - rcu_dereference with debug checking
 209  *
 210  * Do an rcu_dereference(), but check that the context is correct.
 211  * For example, rcu_dereference_check(gp, rcu_read_lock_held()) to
 212  * ensure that the rcu_dereference_check() executes within an RCU
 213  * read-side critical section.  It is also possible to check for
 214  * locks being held, for example, by using lockdep_is_held().
 215  */
 216 #define rcu_dereference_check(p, c) \
 217         ({ \
 218                 if (debug_lockdep_rcu_enabled() && !(c)) \
 219                         lockdep_rcu_dereference(__FILE__, __LINE__); \
 220                 rcu_dereference_raw(p); \
 221         })
 222
 223 #else /* #ifdef CONFIG_PROVE_RCU */
 224
 225 #define rcu_dereference_check(p, c)     rcu_dereference_raw(p)
 226
 227 #endif /* #else #ifdef CONFIG_PROVE_RCU */
 228
 229 /**
 230  * rcu_read_lock - mark the beginning of an RCU read-side critical section.
 231  *
 232  * When synchronize_rcu() is invoked on one CPU while other CPUs
 233  * are within RCU read-side critical sections, then the
 234  * synchronize_rcu() is guaranteed to block until after all the other
 235  * CPUs exit their critical sections.  Similarly, if call_rcu() is invoked
 236  * on one CPU while other CPUs are within RCU read-side critical
 237  * sections, invocation of the corresponding RCU callback is deferred
 238  * until after the all the other CPUs exit their critical sections.
 239  *
 240  * Note, however, that RCU callbacks are permitted to run concurrently
 241  * with RCU read-side critical sections.  One way that this can happen
 242  * is via the following sequence of events: (1) CPU 0 enters an RCU
 243  * read-side critical section, (2) CPU 1 invokes call_rcu() to register
 244  * an RCU callback, (3) CPU 0 exits the RCU read-side critical section,
 245  * (4) CPU 2 enters a RCU read-side critical section, (5) the RCU
 246  * callback is invoked.  This is legal, because the RCU read-side critical
 247  * section that was running concurrently with the call_rcu() (and which
 248  * therefore might be referencing something that the corresponding RCU
 249  * callback would free up) has completed before the corresponding
 250  * RCU callback is invoked.
 251  *
 252  * RCU read-side critical sections may be nested.  Any deferred actions
 253  * will be deferred until the outermost RCU read-side critical section
 254  * completes.
 255  *
 256  * It is illegal to block while in an RCU read-side critical section.
 257  */
 258 static inline void rcu_read_lock(void)
 259 {
 260         __rcu_read_lock();
 261         __acquire(RCU);
 262         rcu_read_acquire();
 263 }
 264
 265 /*
 266  * So where is rcu_write_lock()?  It does not exist, as there is no
 267  * way for writers to lock out RCU readers.  This is a feature, not
 268  * a bug -- this property is what provides RCU's performance benefits.
 269  * Of course, writers must coordinate with each other.  The normal
 270  * spinlock primitives work well for this, but any other technique may be
 271  * used as well.  RCU does not care how the writers keep out of each
 272  * others' way, as long as they do so.
 273  */
 274
 275 /**
 276  * rcu_read_unlock - marks the end of an RCU read-side critical section.
 277  *
 278  * See rcu_read_lock() for more information.
 279  */
 280 static inline void rcu_read_unlock(void)
 281 {
 282         rcu_read_release();
 283         __release(RCU);
 284         __rcu_read_unlock();
 285 }
 286
 287 /**
 288  * rcu_read_lock_bh - mark the beginning of a softirq-only RCU critical section
 289  *
 290  * This is equivalent of rcu_read_lock(), but to be used when updates
 291  * are being done using call_rcu_bh(). Since call_rcu_bh() callbacks
 292  * consider completion of a softirq handler to be a quiescent state,
 293  * a process in RCU read-side critical section must be protected by
 294  * disabling softirqs. Read-side critical sections in interrupt context
 295  * can use just rcu_read_lock().
 296  *
 297  */
 298 static inline void rcu_read_lock_bh(void)
 299 {
 300         __rcu_read_lock_bh();
 301         __acquire(RCU_BH);
 302         rcu_read_acquire_bh();
 303 }
 304
 305 /*
 306  * rcu_read_unlock_bh - marks the end of a softirq-only RCU critical section
 307  *
 308  * See rcu_read_lock_bh() for more information.
 309  */
 310 static inline void rcu_read_unlock_bh(void)
 311 {
 312         rcu_read_release_bh();
 313         __release(RCU_BH);
 314         __rcu_read_unlock_bh();
 315 }
 316
 317 /**
 318  * rcu_read_lock_sched - mark the beginning of a RCU-classic critical section
 319  *
 320  * Should be used with either
 321  * - synchronize_sched()
 322  * or
 323  * - call_rcu_sched() and rcu_barrier_sched()
 324  * on the write-side to insure proper synchronization.
 325  */
 326 static inline void rcu_read_lock_sched(void)
 327 {
 328         preempt_disable();
 329         __acquire(RCU_SCHED);
 330         rcu_read_acquire_sched();
 331 }
 332
 333 /* Used by lockdep and tracing: cannot be traced, cannot call lockdep. */
 334 static inline notrace void rcu_read_lock_sched_notrace(void)
 335 {
 336         preempt_disable_notrace();
 337         __acquire(RCU_SCHED);
 338 }
 339
 340 /*
 341  * rcu_read_unlock_sched - marks the end of a RCU-classic critical section
 342  *
 343  * See rcu_read_lock_sched for more information.
 344  */
 345 static inline void rcu_read_unlock_sched(void)
 346 {
 347         rcu_read_release_sched();
 348         __release(RCU_SCHED);
 349         preempt_enable();
 350 }
 351
 352 /* Used by lockdep and tracing: cannot be traced, cannot call lockdep. */
 353 static inline notrace void rcu_read_unlock_sched_notrace(void)
 354 {
 355         __release(RCU_SCHED);
 356         preempt_enable_notrace();
 357 }
 358
 359
 360 /**
 361  * rcu_dereference_raw - fetch an RCU-protected pointer
 362  *
 363  * The caller must be within some flavor of RCU read-side critical
 364  * section, or must be otherwise preventing the pointer from changing,
 365  * for example, by holding an appropriate lock.  This pointer may later
 366  * be safely dereferenced.  It is the caller's responsibility to have
 367  * done the right thing, as this primitive does no checking of any kind.
 368  *
 369  * Inserts memory barriers on architectures that require them
 370  * (currently only the Alpha), and, more importantly, documents
 371  * exactly which pointers are protected by RCU.
 372  */
 373 #define rcu_dereference_raw(p)  ({ \
 374                                 typeof(p) _________p1 = ACCESS_ONCE(p); \
 375                                 smp_read_barrier_depends(); \
 376                                 (_________p1); \
 377                                 })
 378
 379 /**
 380  * rcu_dereference - fetch an RCU-protected pointer, checking for RCU
 381  *
 382  * Makes rcu_dereference_check() do the dirty work.
 383  */
 384 #define rcu_dereference(p) \
 385         rcu_dereference_check(p, rcu_read_lock_held())
 386
 387 /**
 388  * rcu_dereference_bh - fetch an RCU-protected pointer, checking for RCU-bh
 389  *
 390  * Makes rcu_dereference_check() do the dirty work.
 391  */
 392 #define rcu_dereference_bh(p) \
 393                 rcu_dereference_check(p, rcu_read_lock_bh_held())
 394
 395 /**
 396  * rcu_dereference_sched - fetch RCU-protected pointer, checking for RCU-sched
 397  *
 398  * Makes rcu_dereference_check() do the dirty work.
 399  */
 400 #define rcu_dereference_sched(p) \
 401                 rcu_dereference_check(p, rcu_read_lock_sched_held())
 402
 403 /**
 404  * rcu_assign_pointer - assign (publicize) a pointer to a newly
 405  * initialized structure that will be dereferenced by RCU read-side
 406  * critical sections.  Returns the value assigned.
 407  *
 408  * Inserts memory barriers on architectures that require them
 409  * (pretty much all of them other than x86), and also prevents
 410  * the compiler from reordering the code that initializes the
 411  * structure after the pointer assignment.  More importantly, this
 412  * call documents which pointers will be dereferenced by RCU read-side
 413  * code.
 414  */
 415
 416 #define rcu_assign_pointer(p, v) \
 417         ({ \
 418                 if (!__builtin_constant_p(v) || \
 419                     ((v) != NULL)) \
 420                         smp_wmb(); \
 421                 (p) = (v); \
 422         })
 423
 424 /* Infrastructure to implement the synchronize_() primitives. */
 425
 426 struct rcu_synchronize {
 427         struct rcu_head head;
 428         struct completion completion;
 429 };
 430
 431 extern void wakeme_after_rcu(struct rcu_head  *head);
 432
 433 /**
 434  * call_rcu - Queue an RCU callback for invocation after a grace period.
 435  * @head: structure to be used for queueing the RCU updates.
 436  * @func: actual update function to be invoked after the grace period
 437  *
 438  * The update function will be invoked some time after a full grace
 439  * period elapses, in other words after all currently executing RCU
 440  * read-side critical sections have completed.  RCU read-side critical
 441  * sections are delimited by rcu_read_lock() and rcu_read_unlock(),
 442  * and may be nested.
 443  */
 444 extern void call_rcu(struct rcu_head *head,
 445                               void (*func)(struct rcu_head *head));
 446
 447 /**
 448  * call_rcu_bh - Queue an RCU for invocation after a quicker grace period.
 449  * @head: structure to be used for queueing the RCU updates.
 450  * @func: actual update function to be invoked after the grace period
 451  *
 452  * The update function will be invoked some time after a full grace
 453  * period elapses, in other words after all currently executing RCU
 454  * read-side critical sections have completed. call_rcu_bh() assumes
 455  * that the read-side critical sections end on completion of a softirq
 456  * handler. This means that read-side critical sections in process
 457  * context must not be interrupted by softirqs. This interface is to be
 458  * used when most of the read-side critical sections are in softirq context.
 459  * RCU read-side critical sections are delimited by :
 460  *  - rcu_read_lock() and  rcu_read_unlock(), if in interrupt context.
 461  *  OR
 462  *  - rcu_read_lock_bh() and rcu_read_unlock_bh(), if in process context.
 463  *  These may be nested.
 464  */
 465 extern void call_rcu_bh(struct rcu_head *head,
 466                         void (*func)(struct rcu_head *head));
 467
 468 #endif /* __LINUX_RCUPDATE_H */