rcupdate.c 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271
  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. * Authors: Dipankar Sarma <dipankar@in.ibm.com>
  21. * Manfred Spraul <manfred@colorfullife.com>
  22. *
  23. * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
  24. * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
  25. * Papers:
  26. * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf
  27. * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
  28. *
  29. * For detailed explanation of Read-Copy Update mechanism see -
  30. * http://lse.sourceforge.net/locking/rcupdate.html
  31. *
  32. */
  33. #include <linux/types.h>
  34. #include <linux/kernel.h>
  35. #include <linux/init.h>
  36. #include <linux/spinlock.h>
  37. #include <linux/smp.h>
  38. #include <linux/interrupt.h>
  39. #include <linux/sched.h>
  40. #include <asm/atomic.h>
  41. #include <linux/bitops.h>
  42. #include <linux/percpu.h>
  43. #include <linux/notifier.h>
  44. #include <linux/cpu.h>
  45. #include <linux/mutex.h>
  46. #include <linux/module.h>
  47. #include <linux/kernel_stat.h>
  48. enum rcu_barrier {
  49. RCU_BARRIER_STD,
  50. RCU_BARRIER_BH,
  51. RCU_BARRIER_SCHED,
  52. };
  53. static DEFINE_PER_CPU(struct rcu_head, rcu_barrier_head) = {NULL};
  54. static atomic_t rcu_barrier_cpu_count;
  55. static DEFINE_MUTEX(rcu_barrier_mutex);
  56. static struct completion rcu_barrier_completion;
  57. int rcu_scheduler_active __read_mostly;
  58. static atomic_t rcu_migrate_type_count = ATOMIC_INIT(0);
  59. static struct rcu_head rcu_migrate_head[3];
  60. static DECLARE_WAIT_QUEUE_HEAD(rcu_migrate_wq);
  61. /*
  62. * Awaken the corresponding synchronize_rcu() instance now that a
  63. * grace period has elapsed.
  64. */
  65. void wakeme_after_rcu(struct rcu_head *head)
  66. {
  67. struct rcu_synchronize *rcu;
  68. rcu = container_of(head, struct rcu_synchronize, head);
  69. complete(&rcu->completion);
  70. }
  71. /**
  72. * synchronize_rcu - wait until a grace period has elapsed.
  73. *
  74. * Control will return to the caller some time after a full grace
  75. * period has elapsed, in other words after all currently executing RCU
  76. * read-side critical sections have completed. RCU read-side critical
  77. * sections are delimited by rcu_read_lock() and rcu_read_unlock(),
  78. * and may be nested.
  79. */
  80. void synchronize_rcu(void)
  81. {
  82. struct rcu_synchronize rcu;
  83. if (rcu_blocking_is_gp())
  84. return;
  85. init_completion(&rcu.completion);
  86. /* Will wake me after RCU finished. */
  87. call_rcu(&rcu.head, wakeme_after_rcu);
  88. /* Wait for it. */
  89. wait_for_completion(&rcu.completion);
  90. }
  91. EXPORT_SYMBOL_GPL(synchronize_rcu);
  92. /**
  93. * synchronize_rcu_bh - wait until an rcu_bh grace period has elapsed.
  94. *
  95. * Control will return to the caller some time after a full rcu_bh grace
  96. * period has elapsed, in other words after all currently executing rcu_bh
  97. * read-side critical sections have completed. RCU read-side critical
  98. * sections are delimited by rcu_read_lock_bh() and rcu_read_unlock_bh(),
  99. * and may be nested.
  100. */
  101. void synchronize_rcu_bh(void)
  102. {
  103. struct rcu_synchronize rcu;
  104. if (rcu_blocking_is_gp())
  105. return;
  106. init_completion(&rcu.completion);
  107. /* Will wake me after RCU finished. */
  108. call_rcu_bh(&rcu.head, wakeme_after_rcu);
  109. /* Wait for it. */
  110. wait_for_completion(&rcu.completion);
  111. }
  112. EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
  113. static void rcu_barrier_callback(struct rcu_head *notused)
  114. {
  115. if (atomic_dec_and_test(&rcu_barrier_cpu_count))
  116. complete(&rcu_barrier_completion);
  117. }
  118. /*
  119. * Called with preemption disabled, and from cross-cpu IRQ context.
  120. */
  121. static void rcu_barrier_func(void *type)
  122. {
  123. int cpu = smp_processor_id();
  124. struct rcu_head *head = &per_cpu(rcu_barrier_head, cpu);
  125. atomic_inc(&rcu_barrier_cpu_count);
  126. switch ((enum rcu_barrier)type) {
  127. case RCU_BARRIER_STD:
  128. call_rcu(head, rcu_barrier_callback);
  129. break;
  130. case RCU_BARRIER_BH:
  131. call_rcu_bh(head, rcu_barrier_callback);
  132. break;
  133. case RCU_BARRIER_SCHED:
  134. call_rcu_sched(head, rcu_barrier_callback);
  135. break;
  136. }
  137. }
  138. static inline void wait_migrated_callbacks(void)
  139. {
  140. wait_event(rcu_migrate_wq, !atomic_read(&rcu_migrate_type_count));
  141. smp_mb(); /* In case we didn't sleep. */
  142. }
  143. /*
  144. * Orchestrate the specified type of RCU barrier, waiting for all
  145. * RCU callbacks of the specified type to complete.
  146. */
  147. static void _rcu_barrier(enum rcu_barrier type)
  148. {
  149. BUG_ON(in_interrupt());
  150. /* Take cpucontrol mutex to protect against CPU hotplug */
  151. mutex_lock(&rcu_barrier_mutex);
  152. init_completion(&rcu_barrier_completion);
  153. /*
  154. * Initialize rcu_barrier_cpu_count to 1, then invoke
  155. * rcu_barrier_func() on each CPU, so that each CPU also has
  156. * incremented rcu_barrier_cpu_count. Only then is it safe to
  157. * decrement rcu_barrier_cpu_count -- otherwise the first CPU
  158. * might complete its grace period before all of the other CPUs
  159. * did their increment, causing this function to return too
  160. * early.
  161. */
  162. atomic_set(&rcu_barrier_cpu_count, 1);
  163. on_each_cpu(rcu_barrier_func, (void *)type, 1);
  164. if (atomic_dec_and_test(&rcu_barrier_cpu_count))
  165. complete(&rcu_barrier_completion);
  166. wait_for_completion(&rcu_barrier_completion);
  167. mutex_unlock(&rcu_barrier_mutex);
  168. wait_migrated_callbacks();
  169. }
  170. /**
  171. * rcu_barrier - Wait until all in-flight call_rcu() callbacks complete.
  172. */
  173. void rcu_barrier(void)
  174. {
  175. _rcu_barrier(RCU_BARRIER_STD);
  176. }
  177. EXPORT_SYMBOL_GPL(rcu_barrier);
  178. /**
  179. * rcu_barrier_bh - Wait until all in-flight call_rcu_bh() callbacks complete.
  180. */
  181. void rcu_barrier_bh(void)
  182. {
  183. _rcu_barrier(RCU_BARRIER_BH);
  184. }
  185. EXPORT_SYMBOL_GPL(rcu_barrier_bh);
  186. /**
  187. * rcu_barrier_sched - Wait for in-flight call_rcu_sched() callbacks.
  188. */
  189. void rcu_barrier_sched(void)
  190. {
  191. _rcu_barrier(RCU_BARRIER_SCHED);
  192. }
  193. EXPORT_SYMBOL_GPL(rcu_barrier_sched);
  194. static void rcu_migrate_callback(struct rcu_head *notused)
  195. {
  196. if (atomic_dec_and_test(&rcu_migrate_type_count))
  197. wake_up(&rcu_migrate_wq);
  198. }
  199. extern int rcu_cpu_notify(struct notifier_block *self,
  200. unsigned long action, void *hcpu);
  201. static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self,
  202. unsigned long action, void *hcpu)
  203. {
  204. rcu_cpu_notify(self, action, hcpu);
  205. if (action == CPU_DYING) {
  206. /*
  207. * preempt_disable() in on_each_cpu() prevents stop_machine(),
  208. * so when "on_each_cpu(rcu_barrier_func, (void *)type, 1);"
  209. * returns, all online cpus have queued rcu_barrier_func(),
  210. * and the dead cpu(if it exist) queues rcu_migrate_callback()s.
  211. *
  212. * These callbacks ensure _rcu_barrier() waits for all
  213. * RCU callbacks of the specified type to complete.
  214. */
  215. atomic_set(&rcu_migrate_type_count, 3);
  216. call_rcu_bh(rcu_migrate_head, rcu_migrate_callback);
  217. call_rcu_sched(rcu_migrate_head + 1, rcu_migrate_callback);
  218. call_rcu(rcu_migrate_head + 2, rcu_migrate_callback);
  219. } else if (action == CPU_DOWN_PREPARE) {
  220. /* Don't need to wait until next removal operation. */
  221. /* rcu_migrate_head is protected by cpu_add_remove_lock */
  222. wait_migrated_callbacks();
  223. }
  224. return NOTIFY_OK;
  225. }
  226. void __init rcu_init(void)
  227. {
  228. int i;
  229. __rcu_init();
  230. cpu_notifier(rcu_barrier_cpu_hotplug, 0);
  231. /*
  232. * We don't need protection against CPU-hotplug here because
  233. * this is called early in boot, before either interrupts
  234. * or the scheduler are operational.
  235. */
  236. for_each_online_cpu(i)
  237. rcu_barrier_cpu_hotplug(NULL, CPU_UP_PREPARE, (void *)(long)i);
  238. }
  239. void rcu_scheduler_starting(void)
  240. {
  241. WARN_ON(num_online_cpus() != 1);
  242. WARN_ON(nr_context_switches() > 0);
  243. rcu_scheduler_active = 1;
  244. }