srcu.c 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258
  1. /*
  2. * Sleepable 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, 2006
  19. *
  20. * Author: Paul McKenney <paulmck@us.ibm.com>
  21. *
  22. * For detailed explanation of Read-Copy Update mechanism see -
  23. * Documentation/RCU/ *.txt
  24. *
  25. */
  26. #include <linux/module.h>
  27. #include <linux/mutex.h>
  28. #include <linux/percpu.h>
  29. #include <linux/preempt.h>
  30. #include <linux/rcupdate.h>
  31. #include <linux/sched.h>
  32. #include <linux/slab.h>
  33. #include <linux/smp.h>
  34. #include <linux/srcu.h>
  35. /**
  36. * init_srcu_struct - initialize a sleep-RCU structure
  37. * @sp: structure to initialize.
  38. *
  39. * Must invoke this on a given srcu_struct before passing that srcu_struct
  40. * to any other function. Each srcu_struct represents a separate domain
  41. * of SRCU protection.
  42. */
  43. int init_srcu_struct(struct srcu_struct *sp)
  44. {
  45. sp->completed = 0;
  46. mutex_init(&sp->mutex);
  47. sp->per_cpu_ref = alloc_percpu(struct srcu_struct_array);
  48. return (sp->per_cpu_ref ? 0 : -ENOMEM);
  49. }
  50. /*
  51. * srcu_readers_active_idx -- returns approximate number of readers
  52. * active on the specified rank of per-CPU counters.
  53. */
  54. static int srcu_readers_active_idx(struct srcu_struct *sp, int idx)
  55. {
  56. int cpu;
  57. int sum;
  58. sum = 0;
  59. for_each_possible_cpu(cpu)
  60. sum += per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx];
  61. return sum;
  62. }
  63. /**
  64. * srcu_readers_active - returns approximate number of readers.
  65. * @sp: which srcu_struct to count active readers (holding srcu_read_lock).
  66. *
  67. * Note that this is not an atomic primitive, and can therefore suffer
  68. * severe errors when invoked on an active srcu_struct. That said, it
  69. * can be useful as an error check at cleanup time.
  70. */
  71. int srcu_readers_active(struct srcu_struct *sp)
  72. {
  73. return srcu_readers_active_idx(sp, 0) + srcu_readers_active_idx(sp, 1);
  74. }
  75. /**
  76. * cleanup_srcu_struct - deconstruct a sleep-RCU structure
  77. * @sp: structure to clean up.
  78. *
  79. * Must invoke this after you are finished using a given srcu_struct that
  80. * was initialized via init_srcu_struct(), else you leak memory.
  81. */
  82. void cleanup_srcu_struct(struct srcu_struct *sp)
  83. {
  84. int sum;
  85. sum = srcu_readers_active(sp);
  86. WARN_ON(sum); /* Leakage unless caller handles error. */
  87. if (sum != 0)
  88. return;
  89. free_percpu(sp->per_cpu_ref);
  90. sp->per_cpu_ref = NULL;
  91. }
  92. /**
  93. * srcu_read_lock - register a new reader for an SRCU-protected structure.
  94. * @sp: srcu_struct in which to register the new reader.
  95. *
  96. * Counts the new reader in the appropriate per-CPU element of the
  97. * srcu_struct. Must be called from process context.
  98. * Returns an index that must be passed to the matching srcu_read_unlock().
  99. */
  100. int srcu_read_lock(struct srcu_struct *sp)
  101. {
  102. int idx;
  103. preempt_disable();
  104. idx = sp->completed & 0x1;
  105. barrier(); /* ensure compiler looks -once- at sp->completed. */
  106. per_cpu_ptr(sp->per_cpu_ref, smp_processor_id())->c[idx]++;
  107. srcu_barrier(); /* ensure compiler won't misorder critical section. */
  108. preempt_enable();
  109. return idx;
  110. }
  111. /**
  112. * srcu_read_unlock - unregister a old reader from an SRCU-protected structure.
  113. * @sp: srcu_struct in which to unregister the old reader.
  114. * @idx: return value from corresponding srcu_read_lock().
  115. *
  116. * Removes the count for the old reader from the appropriate per-CPU
  117. * element of the srcu_struct. Note that this may well be a different
  118. * CPU than that which was incremented by the corresponding srcu_read_lock().
  119. * Must be called from process context.
  120. */
  121. void srcu_read_unlock(struct srcu_struct *sp, int idx)
  122. {
  123. preempt_disable();
  124. srcu_barrier(); /* ensure compiler won't misorder critical section. */
  125. per_cpu_ptr(sp->per_cpu_ref, smp_processor_id())->c[idx]--;
  126. preempt_enable();
  127. }
  128. /**
  129. * synchronize_srcu - wait for prior SRCU read-side critical-section completion
  130. * @sp: srcu_struct with which to synchronize.
  131. *
  132. * Flip the completed counter, and wait for the old count to drain to zero.
  133. * As with classic RCU, the updater must use some separate means of
  134. * synchronizing concurrent updates. Can block; must be called from
  135. * process context.
  136. *
  137. * Note that it is illegal to call synchornize_srcu() from the corresponding
  138. * SRCU read-side critical section; doing so will result in deadlock.
  139. * However, it is perfectly legal to call synchronize_srcu() on one
  140. * srcu_struct from some other srcu_struct's read-side critical section.
  141. */
  142. void synchronize_srcu(struct srcu_struct *sp)
  143. {
  144. int idx;
  145. idx = sp->completed;
  146. mutex_lock(&sp->mutex);
  147. /*
  148. * Check to see if someone else did the work for us while we were
  149. * waiting to acquire the lock. We need -two- advances of
  150. * the counter, not just one. If there was but one, we might have
  151. * shown up -after- our helper's first synchronize_sched(), thus
  152. * having failed to prevent CPU-reordering races with concurrent
  153. * srcu_read_unlock()s on other CPUs (see comment below). So we
  154. * either (1) wait for two or (2) supply the second ourselves.
  155. */
  156. if ((sp->completed - idx) >= 2) {
  157. mutex_unlock(&sp->mutex);
  158. return;
  159. }
  160. synchronize_sched(); /* Force memory barrier on all CPUs. */
  161. /*
  162. * The preceding synchronize_sched() ensures that any CPU that
  163. * sees the new value of sp->completed will also see any preceding
  164. * changes to data structures made by this CPU. This prevents
  165. * some other CPU from reordering the accesses in its SRCU
  166. * read-side critical section to precede the corresponding
  167. * srcu_read_lock() -- ensuring that such references will in
  168. * fact be protected.
  169. *
  170. * So it is now safe to do the flip.
  171. */
  172. idx = sp->completed & 0x1;
  173. sp->completed++;
  174. synchronize_sched(); /* Force memory barrier on all CPUs. */
  175. /*
  176. * At this point, because of the preceding synchronize_sched(),
  177. * all srcu_read_lock() calls using the old counters have completed.
  178. * Their corresponding critical sections might well be still
  179. * executing, but the srcu_read_lock() primitives themselves
  180. * will have finished executing.
  181. */
  182. while (srcu_readers_active_idx(sp, idx))
  183. schedule_timeout_interruptible(1);
  184. synchronize_sched(); /* Force memory barrier on all CPUs. */
  185. /*
  186. * The preceding synchronize_sched() forces all srcu_read_unlock()
  187. * primitives that were executing concurrently with the preceding
  188. * for_each_possible_cpu() loop to have completed by this point.
  189. * More importantly, it also forces the corresponding SRCU read-side
  190. * critical sections to have also completed, and the corresponding
  191. * references to SRCU-protected data items to be dropped.
  192. *
  193. * Note:
  194. *
  195. * Despite what you might think at first glance, the
  196. * preceding synchronize_sched() -must- be within the
  197. * critical section ended by the following mutex_unlock().
  198. * Otherwise, a task taking the early exit can race
  199. * with a srcu_read_unlock(), which might have executed
  200. * just before the preceding srcu_readers_active() check,
  201. * and whose CPU might have reordered the srcu_read_unlock()
  202. * with the preceding critical section. In this case, there
  203. * is nothing preventing the synchronize_sched() task that is
  204. * taking the early exit from freeing a data structure that
  205. * is still being referenced (out of order) by the task
  206. * doing the srcu_read_unlock().
  207. *
  208. * Alternatively, the comparison with "2" on the early exit
  209. * could be changed to "3", but this increases synchronize_srcu()
  210. * latency for bulk loads. So the current code is preferred.
  211. */
  212. mutex_unlock(&sp->mutex);
  213. }
  214. /**
  215. * srcu_batches_completed - return batches completed.
  216. * @sp: srcu_struct on which to report batch completion.
  217. *
  218. * Report the number of batches, correlated with, but not necessarily
  219. * precisely the same as, the number of grace periods that have elapsed.
  220. */
  221. long srcu_batches_completed(struct srcu_struct *sp)
  222. {
  223. return sp->completed;
  224. }
  225. EXPORT_SYMBOL_GPL(init_srcu_struct);
  226. EXPORT_SYMBOL_GPL(cleanup_srcu_struct);
  227. EXPORT_SYMBOL_GPL(srcu_read_lock);
  228. EXPORT_SYMBOL_GPL(srcu_read_unlock);
  229. EXPORT_SYMBOL_GPL(synchronize_srcu);
  230. EXPORT_SYMBOL_GPL(srcu_batches_completed);
  231. EXPORT_SYMBOL_GPL(srcu_readers_active);