rcupdate.h 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288
  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 (C) 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. #ifndef __LINUX_RCUPDATE_H
  33. #define __LINUX_RCUPDATE_H
  34. #ifdef __KERNEL__
  35. #include <linux/cache.h>
  36. #include <linux/spinlock.h>
  37. #include <linux/threads.h>
  38. #include <linux/percpu.h>
  39. #include <linux/cpumask.h>
  40. #include <linux/seqlock.h>
  41. /**
  42. * struct rcu_head - callback structure for use with RCU
  43. * @next: next update requests in a list
  44. * @func: actual update function to call after the grace period.
  45. */
  46. struct rcu_head {
  47. struct rcu_head *next;
  48. void (*func)(struct rcu_head *head);
  49. };
  50. #define RCU_HEAD_INIT { .next = NULL, .func = NULL }
  51. #define RCU_HEAD(head) struct rcu_head head = RCU_HEAD_INIT
  52. #define INIT_RCU_HEAD(ptr) do { \
  53. (ptr)->next = NULL; (ptr)->func = NULL; \
  54. } while (0)
  55. /* Global control variables for rcupdate callback mechanism. */
  56. struct rcu_ctrlblk {
  57. long cur; /* Current batch number. */
  58. long completed; /* Number of the last completed batch */
  59. int next_pending; /* Is the next batch already waiting? */
  60. int signaled;
  61. spinlock_t lock ____cacheline_internodealigned_in_smp;
  62. cpumask_t cpumask; /* CPUs that need to switch in order */
  63. /* for current batch to proceed. */
  64. } ____cacheline_internodealigned_in_smp;
  65. /* Is batch a before batch b ? */
  66. static inline int rcu_batch_before(long a, long b)
  67. {
  68. return (a - b) < 0;
  69. }
  70. /* Is batch a after batch b ? */
  71. static inline int rcu_batch_after(long a, long b)
  72. {
  73. return (a - b) > 0;
  74. }
  75. /*
  76. * Per-CPU data for Read-Copy UPdate.
  77. * nxtlist - new callbacks are added here
  78. * curlist - current batch for which quiescent cycle started if any
  79. */
  80. struct rcu_data {
  81. /* 1) quiescent state handling : */
  82. long quiescbatch; /* Batch # for grace period */
  83. int passed_quiesc; /* User-mode/idle loop etc. */
  84. int qs_pending; /* core waits for quiesc state */
  85. /* 2) batch handling */
  86. long batch; /* Batch # for current RCU batch */
  87. struct rcu_head *nxtlist;
  88. struct rcu_head **nxttail;
  89. long qlen; /* # of queued callbacks */
  90. struct rcu_head *curlist;
  91. struct rcu_head **curtail;
  92. struct rcu_head *donelist;
  93. struct rcu_head **donetail;
  94. long blimit; /* Upper limit on a processed batch */
  95. int cpu;
  96. struct rcu_head barrier;
  97. };
  98. DECLARE_PER_CPU(struct rcu_data, rcu_data);
  99. DECLARE_PER_CPU(struct rcu_data, rcu_bh_data);
  100. /*
  101. * Increment the quiescent state counter.
  102. * The counter is a bit degenerated: We do not need to know
  103. * how many quiescent states passed, just if there was at least
  104. * one since the start of the grace period. Thus just a flag.
  105. */
  106. static inline void rcu_qsctr_inc(int cpu)
  107. {
  108. struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
  109. rdp->passed_quiesc = 1;
  110. }
  111. static inline void rcu_bh_qsctr_inc(int cpu)
  112. {
  113. struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu);
  114. rdp->passed_quiesc = 1;
  115. }
  116. extern int rcu_pending(int cpu);
  117. extern int rcu_needs_cpu(int cpu);
  118. /**
  119. * rcu_read_lock - mark the beginning of an RCU read-side critical section.
  120. *
  121. * When synchronize_rcu() is invoked on one CPU while other CPUs
  122. * are within RCU read-side critical sections, then the
  123. * synchronize_rcu() is guaranteed to block until after all the other
  124. * CPUs exit their critical sections. Similarly, if call_rcu() is invoked
  125. * on one CPU while other CPUs are within RCU read-side critical
  126. * sections, invocation of the corresponding RCU callback is deferred
  127. * until after the all the other CPUs exit their critical sections.
  128. *
  129. * Note, however, that RCU callbacks are permitted to run concurrently
  130. * with RCU read-side critical sections. One way that this can happen
  131. * is via the following sequence of events: (1) CPU 0 enters an RCU
  132. * read-side critical section, (2) CPU 1 invokes call_rcu() to register
  133. * an RCU callback, (3) CPU 0 exits the RCU read-side critical section,
  134. * (4) CPU 2 enters a RCU read-side critical section, (5) the RCU
  135. * callback is invoked. This is legal, because the RCU read-side critical
  136. * section that was running concurrently with the call_rcu() (and which
  137. * therefore might be referencing something that the corresponding RCU
  138. * callback would free up) has completed before the corresponding
  139. * RCU callback is invoked.
  140. *
  141. * RCU read-side critical sections may be nested. Any deferred actions
  142. * will be deferred until the outermost RCU read-side critical section
  143. * completes.
  144. *
  145. * It is illegal to block while in an RCU read-side critical section.
  146. */
  147. #define rcu_read_lock() \
  148. do { \
  149. preempt_disable(); \
  150. __acquire(RCU); \
  151. } while(0)
  152. /**
  153. * rcu_read_unlock - marks the end of an RCU read-side critical section.
  154. *
  155. * See rcu_read_lock() for more information.
  156. */
  157. #define rcu_read_unlock() \
  158. do { \
  159. __release(RCU); \
  160. preempt_enable(); \
  161. } while(0)
  162. /*
  163. * So where is rcu_write_lock()? It does not exist, as there is no
  164. * way for writers to lock out RCU readers. This is a feature, not
  165. * a bug -- this property is what provides RCU's performance benefits.
  166. * Of course, writers must coordinate with each other. The normal
  167. * spinlock primitives work well for this, but any other technique may be
  168. * used as well. RCU does not care how the writers keep out of each
  169. * others' way, as long as they do so.
  170. */
  171. /**
  172. * rcu_read_lock_bh - mark the beginning of a softirq-only RCU critical section
  173. *
  174. * This is equivalent of rcu_read_lock(), but to be used when updates
  175. * are being done using call_rcu_bh(). Since call_rcu_bh() callbacks
  176. * consider completion of a softirq handler to be a quiescent state,
  177. * a process in RCU read-side critical section must be protected by
  178. * disabling softirqs. Read-side critical sections in interrupt context
  179. * can use just rcu_read_lock().
  180. *
  181. */
  182. #define rcu_read_lock_bh() \
  183. do { \
  184. local_bh_disable(); \
  185. __acquire(RCU_BH); \
  186. } while(0)
  187. /*
  188. * rcu_read_unlock_bh - marks the end of a softirq-only RCU critical section
  189. *
  190. * See rcu_read_lock_bh() for more information.
  191. */
  192. #define rcu_read_unlock_bh() \
  193. do { \
  194. __release(RCU_BH); \
  195. local_bh_enable(); \
  196. } while(0)
  197. /**
  198. * rcu_dereference - fetch an RCU-protected pointer in an
  199. * RCU read-side critical section. This pointer may later
  200. * be safely dereferenced.
  201. *
  202. * Inserts memory barriers on architectures that require them
  203. * (currently only the Alpha), and, more importantly, documents
  204. * exactly which pointers are protected by RCU.
  205. */
  206. #define rcu_dereference(p) ({ \
  207. typeof(p) _________p1 = p; \
  208. smp_read_barrier_depends(); \
  209. (_________p1); \
  210. })
  211. /**
  212. * rcu_assign_pointer - assign (publicize) a pointer to a newly
  213. * initialized structure that will be dereferenced by RCU read-side
  214. * critical sections. Returns the value assigned.
  215. *
  216. * Inserts memory barriers on architectures that require them
  217. * (pretty much all of them other than x86), and also prevents
  218. * the compiler from reordering the code that initializes the
  219. * structure after the pointer assignment. More importantly, this
  220. * call documents which pointers will be dereferenced by RCU read-side
  221. * code.
  222. */
  223. #define rcu_assign_pointer(p, v) ({ \
  224. smp_wmb(); \
  225. (p) = (v); \
  226. })
  227. /**
  228. * synchronize_sched - block until all CPUs have exited any non-preemptive
  229. * kernel code sequences.
  230. *
  231. * This means that all preempt_disable code sequences, including NMI and
  232. * hardware-interrupt handlers, in progress on entry will have completed
  233. * before this primitive returns. However, this does not guarantee that
  234. * softirq handlers will have completed, since in some kernels, these
  235. * handlers can run in process context, and can block.
  236. *
  237. * This primitive provides the guarantees made by the (now removed)
  238. * synchronize_kernel() API. In contrast, synchronize_rcu() only
  239. * guarantees that rcu_read_lock() sections will have completed.
  240. * In "classic RCU", these two guarantees happen to be one and
  241. * the same, but can differ in realtime RCU implementations.
  242. */
  243. #define synchronize_sched() synchronize_rcu()
  244. extern void rcu_init(void);
  245. extern void rcu_check_callbacks(int cpu, int user);
  246. extern void rcu_restart_cpu(int cpu);
  247. extern long rcu_batches_completed(void);
  248. extern long rcu_batches_completed_bh(void);
  249. /* Exported interfaces */
  250. extern void FASTCALL(call_rcu(struct rcu_head *head,
  251. void (*func)(struct rcu_head *head)));
  252. extern void FASTCALL(call_rcu_bh(struct rcu_head *head,
  253. void (*func)(struct rcu_head *head)));
  254. extern void synchronize_rcu(void);
  255. void synchronize_idle(void);
  256. extern void rcu_barrier(void);
  257. #endif /* __KERNEL__ */
  258. #endif /* __LINUX_RCUPDATE_H */