srcutree.c 47 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * Sleepable Read-Copy Update mechanism for mutual exclusion.
  4. *
  5. * Copyright (C) IBM Corporation, 2006
  6. * Copyright (C) Fujitsu, 2012
  7. *
  8. * Authors: Paul McKenney <paulmck@linux.ibm.com>
  9. * Lai Jiangshan <laijs@cn.fujitsu.com>
  10. *
  11. * For detailed explanation of Read-Copy Update mechanism see -
  12. * Documentation/RCU/ *.txt
  13. *
  14. */
  15. #define pr_fmt(fmt) "rcu: " fmt
  16. #include <linux/export.h>
  17. #include <linux/mutex.h>
  18. #include <linux/percpu.h>
  19. #include <linux/preempt.h>
  20. #include <linux/rcupdate_wait.h>
  21. #include <linux/sched.h>
  22. #include <linux/smp.h>
  23. #include <linux/delay.h>
  24. #include <linux/module.h>
  25. #include <linux/srcu.h>
  26. #include "rcu.h"
  27. #include "rcu_segcblist.h"
  28. /* Holdoff in nanoseconds for auto-expediting. */
  29. #define DEFAULT_SRCU_EXP_HOLDOFF (25 * 1000)
  30. static ulong exp_holdoff = DEFAULT_SRCU_EXP_HOLDOFF;
  31. module_param(exp_holdoff, ulong, 0444);
  32. /* Overflow-check frequency. N bits roughly says every 2**N grace periods. */
  33. static ulong counter_wrap_check = (ULONG_MAX >> 2);
  34. module_param(counter_wrap_check, ulong, 0444);
  35. /* Early-boot callback-management, so early that no lock is required! */
  36. static LIST_HEAD(srcu_boot_list);
  37. static bool __read_mostly srcu_init_done;
  38. static void srcu_invoke_callbacks(struct work_struct *work);
  39. static void srcu_reschedule(struct srcu_struct *ssp, unsigned long delay);
  40. static void process_srcu(struct work_struct *work);
  41. static void srcu_delay_timer(struct timer_list *t);
  42. /* Wrappers for lock acquisition and release, see raw_spin_lock_rcu_node(). */
  43. #define spin_lock_rcu_node(p) \
  44. do { \
  45. spin_lock(&ACCESS_PRIVATE(p, lock)); \
  46. smp_mb__after_unlock_lock(); \
  47. } while (0)
  48. #define spin_unlock_rcu_node(p) spin_unlock(&ACCESS_PRIVATE(p, lock))
  49. #define spin_lock_irq_rcu_node(p) \
  50. do { \
  51. spin_lock_irq(&ACCESS_PRIVATE(p, lock)); \
  52. smp_mb__after_unlock_lock(); \
  53. } while (0)
  54. #define spin_unlock_irq_rcu_node(p) \
  55. spin_unlock_irq(&ACCESS_PRIVATE(p, lock))
  56. #define spin_lock_irqsave_rcu_node(p, flags) \
  57. do { \
  58. spin_lock_irqsave(&ACCESS_PRIVATE(p, lock), flags); \
  59. smp_mb__after_unlock_lock(); \
  60. } while (0)
  61. #define spin_unlock_irqrestore_rcu_node(p, flags) \
  62. spin_unlock_irqrestore(&ACCESS_PRIVATE(p, lock), flags) \
  63. /*
  64. * Initialize SRCU combining tree. Note that statically allocated
  65. * srcu_struct structures might already have srcu_read_lock() and
  66. * srcu_read_unlock() running against them. So if the is_static parameter
  67. * is set, don't initialize ->srcu_lock_count[] and ->srcu_unlock_count[].
  68. */
  69. static void init_srcu_struct_nodes(struct srcu_struct *ssp, bool is_static)
  70. {
  71. int cpu;
  72. int i;
  73. int level = 0;
  74. int levelspread[RCU_NUM_LVLS];
  75. struct srcu_data *sdp;
  76. struct srcu_node *snp;
  77. struct srcu_node *snp_first;
  78. /* Initialize geometry if it has not already been initialized. */
  79. rcu_init_geometry();
  80. /* Work out the overall tree geometry. */
  81. ssp->level[0] = &ssp->node[0];
  82. for (i = 1; i < rcu_num_lvls; i++)
  83. ssp->level[i] = ssp->level[i - 1] + num_rcu_lvl[i - 1];
  84. rcu_init_levelspread(levelspread, num_rcu_lvl);
  85. /* Each pass through this loop initializes one srcu_node structure. */
  86. srcu_for_each_node_breadth_first(ssp, snp) {
  87. spin_lock_init(&ACCESS_PRIVATE(snp, lock));
  88. WARN_ON_ONCE(ARRAY_SIZE(snp->srcu_have_cbs) !=
  89. ARRAY_SIZE(snp->srcu_data_have_cbs));
  90. for (i = 0; i < ARRAY_SIZE(snp->srcu_have_cbs); i++) {
  91. snp->srcu_have_cbs[i] = 0;
  92. snp->srcu_data_have_cbs[i] = 0;
  93. }
  94. snp->srcu_gp_seq_needed_exp = 0;
  95. snp->grplo = -1;
  96. snp->grphi = -1;
  97. if (snp == &ssp->node[0]) {
  98. /* Root node, special case. */
  99. snp->srcu_parent = NULL;
  100. continue;
  101. }
  102. /* Non-root node. */
  103. if (snp == ssp->level[level + 1])
  104. level++;
  105. snp->srcu_parent = ssp->level[level - 1] +
  106. (snp - ssp->level[level]) /
  107. levelspread[level - 1];
  108. }
  109. /*
  110. * Initialize the per-CPU srcu_data array, which feeds into the
  111. * leaves of the srcu_node tree.
  112. */
  113. WARN_ON_ONCE(ARRAY_SIZE(sdp->srcu_lock_count) !=
  114. ARRAY_SIZE(sdp->srcu_unlock_count));
  115. level = rcu_num_lvls - 1;
  116. snp_first = ssp->level[level];
  117. for_each_possible_cpu(cpu) {
  118. sdp = per_cpu_ptr(ssp->sda, cpu);
  119. spin_lock_init(&ACCESS_PRIVATE(sdp, lock));
  120. rcu_segcblist_init(&sdp->srcu_cblist);
  121. sdp->srcu_cblist_invoking = false;
  122. sdp->srcu_gp_seq_needed = ssp->srcu_gp_seq;
  123. sdp->srcu_gp_seq_needed_exp = ssp->srcu_gp_seq;
  124. sdp->mynode = &snp_first[cpu / levelspread[level]];
  125. for (snp = sdp->mynode; snp != NULL; snp = snp->srcu_parent) {
  126. if (snp->grplo < 0)
  127. snp->grplo = cpu;
  128. snp->grphi = cpu;
  129. }
  130. sdp->cpu = cpu;
  131. INIT_WORK(&sdp->work, srcu_invoke_callbacks);
  132. timer_setup(&sdp->delay_work, srcu_delay_timer, 0);
  133. sdp->ssp = ssp;
  134. sdp->grpmask = 1 << (cpu - sdp->mynode->grplo);
  135. if (is_static)
  136. continue;
  137. /* Dynamically allocated, better be no srcu_read_locks()! */
  138. for (i = 0; i < ARRAY_SIZE(sdp->srcu_lock_count); i++) {
  139. sdp->srcu_lock_count[i] = 0;
  140. sdp->srcu_unlock_count[i] = 0;
  141. }
  142. }
  143. }
  144. /*
  145. * Initialize non-compile-time initialized fields, including the
  146. * associated srcu_node and srcu_data structures. The is_static
  147. * parameter is passed through to init_srcu_struct_nodes(), and
  148. * also tells us that ->sda has already been wired up to srcu_data.
  149. */
  150. static int init_srcu_struct_fields(struct srcu_struct *ssp, bool is_static)
  151. {
  152. mutex_init(&ssp->srcu_cb_mutex);
  153. mutex_init(&ssp->srcu_gp_mutex);
  154. ssp->srcu_idx = 0;
  155. ssp->srcu_gp_seq = 0;
  156. ssp->srcu_barrier_seq = 0;
  157. mutex_init(&ssp->srcu_barrier_mutex);
  158. atomic_set(&ssp->srcu_barrier_cpu_cnt, 0);
  159. INIT_DELAYED_WORK(&ssp->work, process_srcu);
  160. if (!is_static)
  161. ssp->sda = alloc_percpu(struct srcu_data);
  162. init_srcu_struct_nodes(ssp, is_static);
  163. ssp->srcu_gp_seq_needed_exp = 0;
  164. ssp->srcu_last_gp_end = ktime_get_mono_fast_ns();
  165. smp_store_release(&ssp->srcu_gp_seq_needed, 0); /* Init done. */
  166. return ssp->sda ? 0 : -ENOMEM;
  167. }
  168. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  169. int __init_srcu_struct(struct srcu_struct *ssp, const char *name,
  170. struct lock_class_key *key)
  171. {
  172. /* Don't re-initialize a lock while it is held. */
  173. debug_check_no_locks_freed((void *)ssp, sizeof(*ssp));
  174. lockdep_init_map(&ssp->dep_map, name, key, 0);
  175. spin_lock_init(&ACCESS_PRIVATE(ssp, lock));
  176. return init_srcu_struct_fields(ssp, false);
  177. }
  178. EXPORT_SYMBOL_GPL(__init_srcu_struct);
  179. #else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */
  180. /**
  181. * init_srcu_struct - initialize a sleep-RCU structure
  182. * @ssp: structure to initialize.
  183. *
  184. * Must invoke this on a given srcu_struct before passing that srcu_struct
  185. * to any other function. Each srcu_struct represents a separate domain
  186. * of SRCU protection.
  187. */
  188. int init_srcu_struct(struct srcu_struct *ssp)
  189. {
  190. spin_lock_init(&ACCESS_PRIVATE(ssp, lock));
  191. return init_srcu_struct_fields(ssp, false);
  192. }
  193. EXPORT_SYMBOL_GPL(init_srcu_struct);
  194. #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
  195. /*
  196. * First-use initialization of statically allocated srcu_struct
  197. * structure. Wiring up the combining tree is more than can be
  198. * done with compile-time initialization, so this check is added
  199. * to each update-side SRCU primitive. Use ssp->lock, which -is-
  200. * compile-time initialized, to resolve races involving multiple
  201. * CPUs trying to garner first-use privileges.
  202. */
  203. static void check_init_srcu_struct(struct srcu_struct *ssp)
  204. {
  205. unsigned long flags;
  206. /* The smp_load_acquire() pairs with the smp_store_release(). */
  207. if (!rcu_seq_state(smp_load_acquire(&ssp->srcu_gp_seq_needed))) /*^^^*/
  208. return; /* Already initialized. */
  209. spin_lock_irqsave_rcu_node(ssp, flags);
  210. if (!rcu_seq_state(ssp->srcu_gp_seq_needed)) {
  211. spin_unlock_irqrestore_rcu_node(ssp, flags);
  212. return;
  213. }
  214. init_srcu_struct_fields(ssp, true);
  215. spin_unlock_irqrestore_rcu_node(ssp, flags);
  216. }
  217. /*
  218. * Returns approximate total of the readers' ->srcu_lock_count[] values
  219. * for the rank of per-CPU counters specified by idx.
  220. */
  221. static unsigned long srcu_readers_lock_idx(struct srcu_struct *ssp, int idx)
  222. {
  223. int cpu;
  224. unsigned long sum = 0;
  225. for_each_possible_cpu(cpu) {
  226. struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu);
  227. sum += READ_ONCE(cpuc->srcu_lock_count[idx]);
  228. }
  229. return sum;
  230. }
  231. /*
  232. * Returns approximate total of the readers' ->srcu_unlock_count[] values
  233. * for the rank of per-CPU counters specified by idx.
  234. */
  235. static unsigned long srcu_readers_unlock_idx(struct srcu_struct *ssp, int idx)
  236. {
  237. int cpu;
  238. unsigned long sum = 0;
  239. for_each_possible_cpu(cpu) {
  240. struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu);
  241. sum += READ_ONCE(cpuc->srcu_unlock_count[idx]);
  242. }
  243. return sum;
  244. }
  245. /*
  246. * Return true if the number of pre-existing readers is determined to
  247. * be zero.
  248. */
  249. static bool srcu_readers_active_idx_check(struct srcu_struct *ssp, int idx)
  250. {
  251. unsigned long unlocks;
  252. unlocks = srcu_readers_unlock_idx(ssp, idx);
  253. /*
  254. * Make sure that a lock is always counted if the corresponding
  255. * unlock is counted. Needs to be a smp_mb() as the read side may
  256. * contain a read from a variable that is written to before the
  257. * synchronize_srcu() in the write side. In this case smp_mb()s
  258. * A and B act like the store buffering pattern.
  259. *
  260. * This smp_mb() also pairs with smp_mb() C to prevent accesses
  261. * after the synchronize_srcu() from being executed before the
  262. * grace period ends.
  263. */
  264. smp_mb(); /* A */
  265. /*
  266. * If the locks are the same as the unlocks, then there must have
  267. * been no readers on this index at some time in between. This does
  268. * not mean that there are no more readers, as one could have read
  269. * the current index but not have incremented the lock counter yet.
  270. *
  271. * So suppose that the updater is preempted here for so long
  272. * that more than ULONG_MAX non-nested readers come and go in
  273. * the meantime. It turns out that this cannot result in overflow
  274. * because if a reader modifies its unlock count after we read it
  275. * above, then that reader's next load of ->srcu_idx is guaranteed
  276. * to get the new value, which will cause it to operate on the
  277. * other bank of counters, where it cannot contribute to the
  278. * overflow of these counters. This means that there is a maximum
  279. * of 2*NR_CPUS increments, which cannot overflow given current
  280. * systems, especially not on 64-bit systems.
  281. *
  282. * OK, how about nesting? This does impose a limit on nesting
  283. * of floor(ULONG_MAX/NR_CPUS/2), which should be sufficient,
  284. * especially on 64-bit systems.
  285. */
  286. return srcu_readers_lock_idx(ssp, idx) == unlocks;
  287. }
  288. /**
  289. * srcu_readers_active - returns true if there are readers. and false
  290. * otherwise
  291. * @ssp: which srcu_struct to count active readers (holding srcu_read_lock).
  292. *
  293. * Note that this is not an atomic primitive, and can therefore suffer
  294. * severe errors when invoked on an active srcu_struct. That said, it
  295. * can be useful as an error check at cleanup time.
  296. */
  297. static bool srcu_readers_active(struct srcu_struct *ssp)
  298. {
  299. int cpu;
  300. unsigned long sum = 0;
  301. for_each_possible_cpu(cpu) {
  302. struct srcu_data *cpuc = per_cpu_ptr(ssp->sda, cpu);
  303. sum += READ_ONCE(cpuc->srcu_lock_count[0]);
  304. sum += READ_ONCE(cpuc->srcu_lock_count[1]);
  305. sum -= READ_ONCE(cpuc->srcu_unlock_count[0]);
  306. sum -= READ_ONCE(cpuc->srcu_unlock_count[1]);
  307. }
  308. return sum;
  309. }
  310. #define SRCU_INTERVAL 1
  311. /*
  312. * Return grace-period delay, zero if there are expedited grace
  313. * periods pending, SRCU_INTERVAL otherwise.
  314. */
  315. static unsigned long srcu_get_delay(struct srcu_struct *ssp)
  316. {
  317. if (ULONG_CMP_LT(READ_ONCE(ssp->srcu_gp_seq),
  318. READ_ONCE(ssp->srcu_gp_seq_needed_exp)))
  319. return 0;
  320. return SRCU_INTERVAL;
  321. }
  322. /**
  323. * cleanup_srcu_struct - deconstruct a sleep-RCU structure
  324. * @ssp: structure to clean up.
  325. *
  326. * Must invoke this after you are finished using a given srcu_struct that
  327. * was initialized via init_srcu_struct(), else you leak memory.
  328. */
  329. void cleanup_srcu_struct(struct srcu_struct *ssp)
  330. {
  331. int cpu;
  332. if (WARN_ON(!srcu_get_delay(ssp)))
  333. return; /* Just leak it! */
  334. if (WARN_ON(srcu_readers_active(ssp)))
  335. return; /* Just leak it! */
  336. flush_delayed_work(&ssp->work);
  337. for_each_possible_cpu(cpu) {
  338. struct srcu_data *sdp = per_cpu_ptr(ssp->sda, cpu);
  339. del_timer_sync(&sdp->delay_work);
  340. flush_work(&sdp->work);
  341. if (WARN_ON(rcu_segcblist_n_cbs(&sdp->srcu_cblist)))
  342. return; /* Forgot srcu_barrier(), so just leak it! */
  343. }
  344. if (WARN_ON(rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)) != SRCU_STATE_IDLE) ||
  345. WARN_ON(srcu_readers_active(ssp))) {
  346. pr_info("%s: Active srcu_struct %p state: %d\n",
  347. __func__, ssp, rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)));
  348. return; /* Caller forgot to stop doing call_srcu()? */
  349. }
  350. free_percpu(ssp->sda);
  351. ssp->sda = NULL;
  352. }
  353. EXPORT_SYMBOL_GPL(cleanup_srcu_struct);
  354. /*
  355. * Counts the new reader in the appropriate per-CPU element of the
  356. * srcu_struct.
  357. * Returns an index that must be passed to the matching srcu_read_unlock().
  358. */
  359. int __srcu_read_lock(struct srcu_struct *ssp)
  360. {
  361. int idx;
  362. idx = READ_ONCE(ssp->srcu_idx) & 0x1;
  363. this_cpu_inc(ssp->sda->srcu_lock_count[idx]);
  364. smp_mb(); /* B */ /* Avoid leaking the critical section. */
  365. return idx;
  366. }
  367. EXPORT_SYMBOL_GPL(__srcu_read_lock);
  368. /*
  369. * Removes the count for the old reader from the appropriate per-CPU
  370. * element of the srcu_struct. Note that this may well be a different
  371. * CPU than that which was incremented by the corresponding srcu_read_lock().
  372. */
  373. void __srcu_read_unlock(struct srcu_struct *ssp, int idx)
  374. {
  375. smp_mb(); /* C */ /* Avoid leaking the critical section. */
  376. this_cpu_inc(ssp->sda->srcu_unlock_count[idx]);
  377. }
  378. EXPORT_SYMBOL_GPL(__srcu_read_unlock);
  379. /*
  380. * We use an adaptive strategy for synchronize_srcu() and especially for
  381. * synchronize_srcu_expedited(). We spin for a fixed time period
  382. * (defined below) to allow SRCU readers to exit their read-side critical
  383. * sections. If there are still some readers after a few microseconds,
  384. * we repeatedly block for 1-millisecond time periods.
  385. */
  386. #define SRCU_RETRY_CHECK_DELAY 5
  387. /*
  388. * Start an SRCU grace period.
  389. */
  390. static void srcu_gp_start(struct srcu_struct *ssp)
  391. {
  392. struct srcu_data *sdp = this_cpu_ptr(ssp->sda);
  393. int state;
  394. lockdep_assert_held(&ACCESS_PRIVATE(ssp, lock));
  395. WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed));
  396. spin_lock_rcu_node(sdp); /* Interrupts already disabled. */
  397. rcu_segcblist_advance(&sdp->srcu_cblist,
  398. rcu_seq_current(&ssp->srcu_gp_seq));
  399. (void)rcu_segcblist_accelerate(&sdp->srcu_cblist,
  400. rcu_seq_snap(&ssp->srcu_gp_seq));
  401. spin_unlock_rcu_node(sdp); /* Interrupts remain disabled. */
  402. smp_mb(); /* Order prior store to ->srcu_gp_seq_needed vs. GP start. */
  403. rcu_seq_start(&ssp->srcu_gp_seq);
  404. state = rcu_seq_state(ssp->srcu_gp_seq);
  405. WARN_ON_ONCE(state != SRCU_STATE_SCAN1);
  406. }
  407. static void srcu_delay_timer(struct timer_list *t)
  408. {
  409. struct srcu_data *sdp = container_of(t, struct srcu_data, delay_work);
  410. queue_work_on(sdp->cpu, rcu_gp_wq, &sdp->work);
  411. }
  412. static void srcu_queue_delayed_work_on(struct srcu_data *sdp,
  413. unsigned long delay)
  414. {
  415. if (!delay) {
  416. queue_work_on(sdp->cpu, rcu_gp_wq, &sdp->work);
  417. return;
  418. }
  419. timer_reduce(&sdp->delay_work, jiffies + delay);
  420. }
  421. /*
  422. * Schedule callback invocation for the specified srcu_data structure,
  423. * if possible, on the corresponding CPU.
  424. */
  425. static void srcu_schedule_cbs_sdp(struct srcu_data *sdp, unsigned long delay)
  426. {
  427. srcu_queue_delayed_work_on(sdp, delay);
  428. }
  429. /*
  430. * Schedule callback invocation for all srcu_data structures associated
  431. * with the specified srcu_node structure that have callbacks for the
  432. * just-completed grace period, the one corresponding to idx. If possible,
  433. * schedule this invocation on the corresponding CPUs.
  434. */
  435. static void srcu_schedule_cbs_snp(struct srcu_struct *ssp, struct srcu_node *snp,
  436. unsigned long mask, unsigned long delay)
  437. {
  438. int cpu;
  439. for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
  440. if (!(mask & (1 << (cpu - snp->grplo))))
  441. continue;
  442. srcu_schedule_cbs_sdp(per_cpu_ptr(ssp->sda, cpu), delay);
  443. }
  444. }
  445. /*
  446. * Note the end of an SRCU grace period. Initiates callback invocation
  447. * and starts a new grace period if needed.
  448. *
  449. * The ->srcu_cb_mutex acquisition does not protect any data, but
  450. * instead prevents more than one grace period from starting while we
  451. * are initiating callback invocation. This allows the ->srcu_have_cbs[]
  452. * array to have a finite number of elements.
  453. */
  454. static void srcu_gp_end(struct srcu_struct *ssp)
  455. {
  456. unsigned long cbdelay;
  457. bool cbs;
  458. bool last_lvl;
  459. int cpu;
  460. unsigned long flags;
  461. unsigned long gpseq;
  462. int idx;
  463. unsigned long mask;
  464. struct srcu_data *sdp;
  465. struct srcu_node *snp;
  466. /* Prevent more than one additional grace period. */
  467. mutex_lock(&ssp->srcu_cb_mutex);
  468. /* End the current grace period. */
  469. spin_lock_irq_rcu_node(ssp);
  470. idx = rcu_seq_state(ssp->srcu_gp_seq);
  471. WARN_ON_ONCE(idx != SRCU_STATE_SCAN2);
  472. cbdelay = srcu_get_delay(ssp);
  473. WRITE_ONCE(ssp->srcu_last_gp_end, ktime_get_mono_fast_ns());
  474. rcu_seq_end(&ssp->srcu_gp_seq);
  475. gpseq = rcu_seq_current(&ssp->srcu_gp_seq);
  476. if (ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, gpseq))
  477. WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, gpseq);
  478. spin_unlock_irq_rcu_node(ssp);
  479. mutex_unlock(&ssp->srcu_gp_mutex);
  480. /* A new grace period can start at this point. But only one. */
  481. /* Initiate callback invocation as needed. */
  482. idx = rcu_seq_ctr(gpseq) % ARRAY_SIZE(snp->srcu_have_cbs);
  483. srcu_for_each_node_breadth_first(ssp, snp) {
  484. spin_lock_irq_rcu_node(snp);
  485. cbs = false;
  486. last_lvl = snp >= ssp->level[rcu_num_lvls - 1];
  487. if (last_lvl)
  488. cbs = snp->srcu_have_cbs[idx] == gpseq;
  489. snp->srcu_have_cbs[idx] = gpseq;
  490. rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
  491. if (ULONG_CMP_LT(snp->srcu_gp_seq_needed_exp, gpseq))
  492. WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
  493. mask = snp->srcu_data_have_cbs[idx];
  494. snp->srcu_data_have_cbs[idx] = 0;
  495. spin_unlock_irq_rcu_node(snp);
  496. if (cbs)
  497. srcu_schedule_cbs_snp(ssp, snp, mask, cbdelay);
  498. /* Occasionally prevent srcu_data counter wrap. */
  499. if (!(gpseq & counter_wrap_check) && last_lvl)
  500. for (cpu = snp->grplo; cpu <= snp->grphi; cpu++) {
  501. sdp = per_cpu_ptr(ssp->sda, cpu);
  502. spin_lock_irqsave_rcu_node(sdp, flags);
  503. if (ULONG_CMP_GE(gpseq,
  504. sdp->srcu_gp_seq_needed + 100))
  505. sdp->srcu_gp_seq_needed = gpseq;
  506. if (ULONG_CMP_GE(gpseq,
  507. sdp->srcu_gp_seq_needed_exp + 100))
  508. sdp->srcu_gp_seq_needed_exp = gpseq;
  509. spin_unlock_irqrestore_rcu_node(sdp, flags);
  510. }
  511. }
  512. /* Callback initiation done, allow grace periods after next. */
  513. mutex_unlock(&ssp->srcu_cb_mutex);
  514. /* Start a new grace period if needed. */
  515. spin_lock_irq_rcu_node(ssp);
  516. gpseq = rcu_seq_current(&ssp->srcu_gp_seq);
  517. if (!rcu_seq_state(gpseq) &&
  518. ULONG_CMP_LT(gpseq, ssp->srcu_gp_seq_needed)) {
  519. srcu_gp_start(ssp);
  520. spin_unlock_irq_rcu_node(ssp);
  521. srcu_reschedule(ssp, 0);
  522. } else {
  523. spin_unlock_irq_rcu_node(ssp);
  524. }
  525. }
  526. /*
  527. * Funnel-locking scheme to scalably mediate many concurrent expedited
  528. * grace-period requests. This function is invoked for the first known
  529. * expedited request for a grace period that has already been requested,
  530. * but without expediting. To start a completely new grace period,
  531. * whether expedited or not, use srcu_funnel_gp_start() instead.
  532. */
  533. static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp,
  534. unsigned long s)
  535. {
  536. unsigned long flags;
  537. for (; snp != NULL; snp = snp->srcu_parent) {
  538. if (rcu_seq_done(&ssp->srcu_gp_seq, s) ||
  539. ULONG_CMP_GE(READ_ONCE(snp->srcu_gp_seq_needed_exp), s))
  540. return;
  541. spin_lock_irqsave_rcu_node(snp, flags);
  542. if (ULONG_CMP_GE(snp->srcu_gp_seq_needed_exp, s)) {
  543. spin_unlock_irqrestore_rcu_node(snp, flags);
  544. return;
  545. }
  546. WRITE_ONCE(snp->srcu_gp_seq_needed_exp, s);
  547. spin_unlock_irqrestore_rcu_node(snp, flags);
  548. }
  549. spin_lock_irqsave_rcu_node(ssp, flags);
  550. if (ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s))
  551. WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s);
  552. spin_unlock_irqrestore_rcu_node(ssp, flags);
  553. }
  554. /*
  555. * Funnel-locking scheme to scalably mediate many concurrent grace-period
  556. * requests. The winner has to do the work of actually starting grace
  557. * period s. Losers must either ensure that their desired grace-period
  558. * number is recorded on at least their leaf srcu_node structure, or they
  559. * must take steps to invoke their own callbacks.
  560. *
  561. * Note that this function also does the work of srcu_funnel_exp_start(),
  562. * in some cases by directly invoking it.
  563. */
  564. static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
  565. unsigned long s, bool do_norm)
  566. {
  567. unsigned long flags;
  568. int idx = rcu_seq_ctr(s) % ARRAY_SIZE(sdp->mynode->srcu_have_cbs);
  569. struct srcu_node *snp = sdp->mynode;
  570. unsigned long snp_seq;
  571. /* Each pass through the loop does one level of the srcu_node tree. */
  572. for (; snp != NULL; snp = snp->srcu_parent) {
  573. if (rcu_seq_done(&ssp->srcu_gp_seq, s) && snp != sdp->mynode)
  574. return; /* GP already done and CBs recorded. */
  575. spin_lock_irqsave_rcu_node(snp, flags);
  576. if (ULONG_CMP_GE(snp->srcu_have_cbs[idx], s)) {
  577. snp_seq = snp->srcu_have_cbs[idx];
  578. if (snp == sdp->mynode && snp_seq == s)
  579. snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
  580. spin_unlock_irqrestore_rcu_node(snp, flags);
  581. if (snp == sdp->mynode && snp_seq != s) {
  582. srcu_schedule_cbs_sdp(sdp, do_norm
  583. ? SRCU_INTERVAL
  584. : 0);
  585. return;
  586. }
  587. if (!do_norm)
  588. srcu_funnel_exp_start(ssp, snp, s);
  589. return;
  590. }
  591. snp->srcu_have_cbs[idx] = s;
  592. if (snp == sdp->mynode)
  593. snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
  594. if (!do_norm && ULONG_CMP_LT(snp->srcu_gp_seq_needed_exp, s))
  595. WRITE_ONCE(snp->srcu_gp_seq_needed_exp, s);
  596. spin_unlock_irqrestore_rcu_node(snp, flags);
  597. }
  598. /* Top of tree, must ensure the grace period will be started. */
  599. spin_lock_irqsave_rcu_node(ssp, flags);
  600. if (ULONG_CMP_LT(ssp->srcu_gp_seq_needed, s)) {
  601. /*
  602. * Record need for grace period s. Pair with load
  603. * acquire setting up for initialization.
  604. */
  605. smp_store_release(&ssp->srcu_gp_seq_needed, s); /*^^^*/
  606. }
  607. if (!do_norm && ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s))
  608. WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s);
  609. /* If grace period not already done and none in progress, start it. */
  610. if (!rcu_seq_done(&ssp->srcu_gp_seq, s) &&
  611. rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
  612. WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed));
  613. srcu_gp_start(ssp);
  614. if (likely(srcu_init_done))
  615. queue_delayed_work(rcu_gp_wq, &ssp->work,
  616. srcu_get_delay(ssp));
  617. else if (list_empty(&ssp->work.work.entry))
  618. list_add(&ssp->work.work.entry, &srcu_boot_list);
  619. }
  620. spin_unlock_irqrestore_rcu_node(ssp, flags);
  621. }
  622. /*
  623. * Wait until all readers counted by array index idx complete, but
  624. * loop an additional time if there is an expedited grace period pending.
  625. * The caller must ensure that ->srcu_idx is not changed while checking.
  626. */
  627. static bool try_check_zero(struct srcu_struct *ssp, int idx, int trycount)
  628. {
  629. for (;;) {
  630. if (srcu_readers_active_idx_check(ssp, idx))
  631. return true;
  632. if (--trycount + !srcu_get_delay(ssp) <= 0)
  633. return false;
  634. udelay(SRCU_RETRY_CHECK_DELAY);
  635. }
  636. }
  637. /*
  638. * Increment the ->srcu_idx counter so that future SRCU readers will
  639. * use the other rank of the ->srcu_(un)lock_count[] arrays. This allows
  640. * us to wait for pre-existing readers in a starvation-free manner.
  641. */
  642. static void srcu_flip(struct srcu_struct *ssp)
  643. {
  644. /*
  645. * Ensure that if this updater saw a given reader's increment
  646. * from __srcu_read_lock(), that reader was using an old value
  647. * of ->srcu_idx. Also ensure that if a given reader sees the
  648. * new value of ->srcu_idx, this updater's earlier scans cannot
  649. * have seen that reader's increments (which is OK, because this
  650. * grace period need not wait on that reader).
  651. */
  652. smp_mb(); /* E */ /* Pairs with B and C. */
  653. WRITE_ONCE(ssp->srcu_idx, ssp->srcu_idx + 1);
  654. /*
  655. * Ensure that if the updater misses an __srcu_read_unlock()
  656. * increment, that task's next __srcu_read_lock() will see the
  657. * above counter update. Note that both this memory barrier
  658. * and the one in srcu_readers_active_idx_check() provide the
  659. * guarantee for __srcu_read_lock().
  660. */
  661. smp_mb(); /* D */ /* Pairs with C. */
  662. }
  663. /*
  664. * If SRCU is likely idle, return true, otherwise return false.
  665. *
  666. * Note that it is OK for several current from-idle requests for a new
  667. * grace period from idle to specify expediting because they will all end
  668. * up requesting the same grace period anyhow. So no loss.
  669. *
  670. * Note also that if any CPU (including the current one) is still invoking
  671. * callbacks, this function will nevertheless say "idle". This is not
  672. * ideal, but the overhead of checking all CPUs' callback lists is even
  673. * less ideal, especially on large systems. Furthermore, the wakeup
  674. * can happen before the callback is fully removed, so we have no choice
  675. * but to accept this type of error.
  676. *
  677. * This function is also subject to counter-wrap errors, but let's face
  678. * it, if this function was preempted for enough time for the counters
  679. * to wrap, it really doesn't matter whether or not we expedite the grace
  680. * period. The extra overhead of a needlessly expedited grace period is
  681. * negligible when amortized over that time period, and the extra latency
  682. * of a needlessly non-expedited grace period is similarly negligible.
  683. */
  684. static bool srcu_might_be_idle(struct srcu_struct *ssp)
  685. {
  686. unsigned long curseq;
  687. unsigned long flags;
  688. struct srcu_data *sdp;
  689. unsigned long t;
  690. unsigned long tlast;
  691. check_init_srcu_struct(ssp);
  692. /* If the local srcu_data structure has callbacks, not idle. */
  693. sdp = raw_cpu_ptr(ssp->sda);
  694. spin_lock_irqsave_rcu_node(sdp, flags);
  695. if (rcu_segcblist_pend_cbs(&sdp->srcu_cblist)) {
  696. spin_unlock_irqrestore_rcu_node(sdp, flags);
  697. return false; /* Callbacks already present, so not idle. */
  698. }
  699. spin_unlock_irqrestore_rcu_node(sdp, flags);
  700. /*
  701. * No local callbacks, so probabalistically probe global state.
  702. * Exact information would require acquiring locks, which would
  703. * kill scalability, hence the probabalistic nature of the probe.
  704. */
  705. /* First, see if enough time has passed since the last GP. */
  706. t = ktime_get_mono_fast_ns();
  707. tlast = READ_ONCE(ssp->srcu_last_gp_end);
  708. if (exp_holdoff == 0 ||
  709. time_in_range_open(t, tlast, tlast + exp_holdoff))
  710. return false; /* Too soon after last GP. */
  711. /* Next, check for probable idleness. */
  712. curseq = rcu_seq_current(&ssp->srcu_gp_seq);
  713. smp_mb(); /* Order ->srcu_gp_seq with ->srcu_gp_seq_needed. */
  714. if (ULONG_CMP_LT(curseq, READ_ONCE(ssp->srcu_gp_seq_needed)))
  715. return false; /* Grace period in progress, so not idle. */
  716. smp_mb(); /* Order ->srcu_gp_seq with prior access. */
  717. if (curseq != rcu_seq_current(&ssp->srcu_gp_seq))
  718. return false; /* GP # changed, so not idle. */
  719. return true; /* With reasonable probability, idle! */
  720. }
  721. /*
  722. * SRCU callback function to leak a callback.
  723. */
  724. static void srcu_leak_callback(struct rcu_head *rhp)
  725. {
  726. }
  727. /*
  728. * Start an SRCU grace period, and also queue the callback if non-NULL.
  729. */
  730. static unsigned long srcu_gp_start_if_needed(struct srcu_struct *ssp,
  731. struct rcu_head *rhp, bool do_norm)
  732. {
  733. unsigned long flags;
  734. int idx;
  735. bool needexp = false;
  736. bool needgp = false;
  737. unsigned long s;
  738. struct srcu_data *sdp;
  739. check_init_srcu_struct(ssp);
  740. idx = srcu_read_lock(ssp);
  741. sdp = raw_cpu_ptr(ssp->sda);
  742. spin_lock_irqsave_rcu_node(sdp, flags);
  743. if (rhp)
  744. rcu_segcblist_enqueue(&sdp->srcu_cblist, rhp);
  745. rcu_segcblist_advance(&sdp->srcu_cblist,
  746. rcu_seq_current(&ssp->srcu_gp_seq));
  747. s = rcu_seq_snap(&ssp->srcu_gp_seq);
  748. (void)rcu_segcblist_accelerate(&sdp->srcu_cblist, s);
  749. if (ULONG_CMP_LT(sdp->srcu_gp_seq_needed, s)) {
  750. sdp->srcu_gp_seq_needed = s;
  751. needgp = true;
  752. }
  753. if (!do_norm && ULONG_CMP_LT(sdp->srcu_gp_seq_needed_exp, s)) {
  754. sdp->srcu_gp_seq_needed_exp = s;
  755. needexp = true;
  756. }
  757. spin_unlock_irqrestore_rcu_node(sdp, flags);
  758. if (needgp)
  759. srcu_funnel_gp_start(ssp, sdp, s, do_norm);
  760. else if (needexp)
  761. srcu_funnel_exp_start(ssp, sdp->mynode, s);
  762. srcu_read_unlock(ssp, idx);
  763. return s;
  764. }
  765. /*
  766. * Enqueue an SRCU callback on the srcu_data structure associated with
  767. * the current CPU and the specified srcu_struct structure, initiating
  768. * grace-period processing if it is not already running.
  769. *
  770. * Note that all CPUs must agree that the grace period extended beyond
  771. * all pre-existing SRCU read-side critical section. On systems with
  772. * more than one CPU, this means that when "func()" is invoked, each CPU
  773. * is guaranteed to have executed a full memory barrier since the end of
  774. * its last corresponding SRCU read-side critical section whose beginning
  775. * preceded the call to call_srcu(). It also means that each CPU executing
  776. * an SRCU read-side critical section that continues beyond the start of
  777. * "func()" must have executed a memory barrier after the call_srcu()
  778. * but before the beginning of that SRCU read-side critical section.
  779. * Note that these guarantees include CPUs that are offline, idle, or
  780. * executing in user mode, as well as CPUs that are executing in the kernel.
  781. *
  782. * Furthermore, if CPU A invoked call_srcu() and CPU B invoked the
  783. * resulting SRCU callback function "func()", then both CPU A and CPU
  784. * B are guaranteed to execute a full memory barrier during the time
  785. * interval between the call to call_srcu() and the invocation of "func()".
  786. * This guarantee applies even if CPU A and CPU B are the same CPU (but
  787. * again only if the system has more than one CPU).
  788. *
  789. * Of course, these guarantees apply only for invocations of call_srcu(),
  790. * srcu_read_lock(), and srcu_read_unlock() that are all passed the same
  791. * srcu_struct structure.
  792. */
  793. static void __call_srcu(struct srcu_struct *ssp, struct rcu_head *rhp,
  794. rcu_callback_t func, bool do_norm)
  795. {
  796. if (debug_rcu_head_queue(rhp)) {
  797. /* Probable double call_srcu(), so leak the callback. */
  798. WRITE_ONCE(rhp->func, srcu_leak_callback);
  799. WARN_ONCE(1, "call_srcu(): Leaked duplicate callback\n");
  800. return;
  801. }
  802. rhp->func = func;
  803. (void)srcu_gp_start_if_needed(ssp, rhp, do_norm);
  804. }
  805. /**
  806. * call_srcu() - Queue a callback for invocation after an SRCU grace period
  807. * @ssp: srcu_struct in queue the callback
  808. * @rhp: structure to be used for queueing the SRCU callback.
  809. * @func: function to be invoked after the SRCU grace period
  810. *
  811. * The callback function will be invoked some time after a full SRCU
  812. * grace period elapses, in other words after all pre-existing SRCU
  813. * read-side critical sections have completed. However, the callback
  814. * function might well execute concurrently with other SRCU read-side
  815. * critical sections that started after call_srcu() was invoked. SRCU
  816. * read-side critical sections are delimited by srcu_read_lock() and
  817. * srcu_read_unlock(), and may be nested.
  818. *
  819. * The callback will be invoked from process context, but must nevertheless
  820. * be fast and must not block.
  821. */
  822. void call_srcu(struct srcu_struct *ssp, struct rcu_head *rhp,
  823. rcu_callback_t func)
  824. {
  825. __call_srcu(ssp, rhp, func, true);
  826. }
  827. EXPORT_SYMBOL_GPL(call_srcu);
  828. /*
  829. * Helper function for synchronize_srcu() and synchronize_srcu_expedited().
  830. */
  831. static void __synchronize_srcu(struct srcu_struct *ssp, bool do_norm)
  832. {
  833. struct rcu_synchronize rcu;
  834. RCU_LOCKDEP_WARN(lock_is_held(&ssp->dep_map) ||
  835. lock_is_held(&rcu_bh_lock_map) ||
  836. lock_is_held(&rcu_lock_map) ||
  837. lock_is_held(&rcu_sched_lock_map),
  838. "Illegal synchronize_srcu() in same-type SRCU (or in RCU) read-side critical section");
  839. if (rcu_scheduler_active == RCU_SCHEDULER_INACTIVE)
  840. return;
  841. might_sleep();
  842. check_init_srcu_struct(ssp);
  843. init_completion(&rcu.completion);
  844. init_rcu_head_on_stack(&rcu.head);
  845. __call_srcu(ssp, &rcu.head, wakeme_after_rcu, do_norm);
  846. wait_for_completion(&rcu.completion);
  847. destroy_rcu_head_on_stack(&rcu.head);
  848. /*
  849. * Make sure that later code is ordered after the SRCU grace
  850. * period. This pairs with the spin_lock_irq_rcu_node()
  851. * in srcu_invoke_callbacks(). Unlike Tree RCU, this is needed
  852. * because the current CPU might have been totally uninvolved with
  853. * (and thus unordered against) that grace period.
  854. */
  855. smp_mb();
  856. }
  857. /**
  858. * synchronize_srcu_expedited - Brute-force SRCU grace period
  859. * @ssp: srcu_struct with which to synchronize.
  860. *
  861. * Wait for an SRCU grace period to elapse, but be more aggressive about
  862. * spinning rather than blocking when waiting.
  863. *
  864. * Note that synchronize_srcu_expedited() has the same deadlock and
  865. * memory-ordering properties as does synchronize_srcu().
  866. */
  867. void synchronize_srcu_expedited(struct srcu_struct *ssp)
  868. {
  869. __synchronize_srcu(ssp, rcu_gp_is_normal());
  870. }
  871. EXPORT_SYMBOL_GPL(synchronize_srcu_expedited);
  872. /**
  873. * synchronize_srcu - wait for prior SRCU read-side critical-section completion
  874. * @ssp: srcu_struct with which to synchronize.
  875. *
  876. * Wait for the count to drain to zero of both indexes. To avoid the
  877. * possible starvation of synchronize_srcu(), it waits for the count of
  878. * the index=((->srcu_idx & 1) ^ 1) to drain to zero at first,
  879. * and then flip the srcu_idx and wait for the count of the other index.
  880. *
  881. * Can block; must be called from process context.
  882. *
  883. * Note that it is illegal to call synchronize_srcu() from the corresponding
  884. * SRCU read-side critical section; doing so will result in deadlock.
  885. * However, it is perfectly legal to call synchronize_srcu() on one
  886. * srcu_struct from some other srcu_struct's read-side critical section,
  887. * as long as the resulting graph of srcu_structs is acyclic.
  888. *
  889. * There are memory-ordering constraints implied by synchronize_srcu().
  890. * On systems with more than one CPU, when synchronize_srcu() returns,
  891. * each CPU is guaranteed to have executed a full memory barrier since
  892. * the end of its last corresponding SRCU read-side critical section
  893. * whose beginning preceded the call to synchronize_srcu(). In addition,
  894. * each CPU having an SRCU read-side critical section that extends beyond
  895. * the return from synchronize_srcu() is guaranteed to have executed a
  896. * full memory barrier after the beginning of synchronize_srcu() and before
  897. * the beginning of that SRCU read-side critical section. Note that these
  898. * guarantees include CPUs that are offline, idle, or executing in user mode,
  899. * as well as CPUs that are executing in the kernel.
  900. *
  901. * Furthermore, if CPU A invoked synchronize_srcu(), which returned
  902. * to its caller on CPU B, then both CPU A and CPU B are guaranteed
  903. * to have executed a full memory barrier during the execution of
  904. * synchronize_srcu(). This guarantee applies even if CPU A and CPU B
  905. * are the same CPU, but again only if the system has more than one CPU.
  906. *
  907. * Of course, these memory-ordering guarantees apply only when
  908. * synchronize_srcu(), srcu_read_lock(), and srcu_read_unlock() are
  909. * passed the same srcu_struct structure.
  910. *
  911. * If SRCU is likely idle, expedite the first request. This semantic
  912. * was provided by Classic SRCU, and is relied upon by its users, so TREE
  913. * SRCU must also provide it. Note that detecting idleness is heuristic
  914. * and subject to both false positives and negatives.
  915. */
  916. void synchronize_srcu(struct srcu_struct *ssp)
  917. {
  918. if (srcu_might_be_idle(ssp) || rcu_gp_is_expedited())
  919. synchronize_srcu_expedited(ssp);
  920. else
  921. __synchronize_srcu(ssp, true);
  922. }
  923. EXPORT_SYMBOL_GPL(synchronize_srcu);
  924. /**
  925. * get_state_synchronize_srcu - Provide an end-of-grace-period cookie
  926. * @ssp: srcu_struct to provide cookie for.
  927. *
  928. * This function returns a cookie that can be passed to
  929. * poll_state_synchronize_srcu(), which will return true if a full grace
  930. * period has elapsed in the meantime. It is the caller's responsibility
  931. * to make sure that grace period happens, for example, by invoking
  932. * call_srcu() after return from get_state_synchronize_srcu().
  933. */
  934. unsigned long get_state_synchronize_srcu(struct srcu_struct *ssp)
  935. {
  936. // Any prior manipulation of SRCU-protected data must happen
  937. // before the load from ->srcu_gp_seq.
  938. smp_mb();
  939. return rcu_seq_snap(&ssp->srcu_gp_seq);
  940. }
  941. EXPORT_SYMBOL_GPL(get_state_synchronize_srcu);
  942. /**
  943. * start_poll_synchronize_srcu - Provide cookie and start grace period
  944. * @ssp: srcu_struct to provide cookie for.
  945. *
  946. * This function returns a cookie that can be passed to
  947. * poll_state_synchronize_srcu(), which will return true if a full grace
  948. * period has elapsed in the meantime. Unlike get_state_synchronize_srcu(),
  949. * this function also ensures that any needed SRCU grace period will be
  950. * started. This convenience does come at a cost in terms of CPU overhead.
  951. */
  952. unsigned long start_poll_synchronize_srcu(struct srcu_struct *ssp)
  953. {
  954. return srcu_gp_start_if_needed(ssp, NULL, true);
  955. }
  956. EXPORT_SYMBOL_GPL(start_poll_synchronize_srcu);
  957. /**
  958. * poll_state_synchronize_srcu - Has cookie's grace period ended?
  959. * @ssp: srcu_struct to provide cookie for.
  960. * @cookie: Return value from get_state_synchronize_srcu() or start_poll_synchronize_srcu().
  961. *
  962. * This function takes the cookie that was returned from either
  963. * get_state_synchronize_srcu() or start_poll_synchronize_srcu(), and
  964. * returns @true if an SRCU grace period elapsed since the time that the
  965. * cookie was created.
  966. */
  967. bool poll_state_synchronize_srcu(struct srcu_struct *ssp, unsigned long cookie)
  968. {
  969. if (!rcu_seq_done(&ssp->srcu_gp_seq, cookie))
  970. return false;
  971. // Ensure that the end of the SRCU grace period happens before
  972. // any subsequent code that the caller might execute.
  973. smp_mb(); // ^^^
  974. return true;
  975. }
  976. EXPORT_SYMBOL_GPL(poll_state_synchronize_srcu);
  977. /*
  978. * Callback function for srcu_barrier() use.
  979. */
  980. static void srcu_barrier_cb(struct rcu_head *rhp)
  981. {
  982. struct srcu_data *sdp;
  983. struct srcu_struct *ssp;
  984. sdp = container_of(rhp, struct srcu_data, srcu_barrier_head);
  985. ssp = sdp->ssp;
  986. if (atomic_dec_and_test(&ssp->srcu_barrier_cpu_cnt))
  987. complete(&ssp->srcu_barrier_completion);
  988. }
  989. /**
  990. * srcu_barrier - Wait until all in-flight call_srcu() callbacks complete.
  991. * @ssp: srcu_struct on which to wait for in-flight callbacks.
  992. */
  993. void srcu_barrier(struct srcu_struct *ssp)
  994. {
  995. int cpu;
  996. struct srcu_data *sdp;
  997. unsigned long s = rcu_seq_snap(&ssp->srcu_barrier_seq);
  998. check_init_srcu_struct(ssp);
  999. mutex_lock(&ssp->srcu_barrier_mutex);
  1000. if (rcu_seq_done(&ssp->srcu_barrier_seq, s)) {
  1001. smp_mb(); /* Force ordering following return. */
  1002. mutex_unlock(&ssp->srcu_barrier_mutex);
  1003. return; /* Someone else did our work for us. */
  1004. }
  1005. rcu_seq_start(&ssp->srcu_barrier_seq);
  1006. init_completion(&ssp->srcu_barrier_completion);
  1007. /* Initial count prevents reaching zero until all CBs are posted. */
  1008. atomic_set(&ssp->srcu_barrier_cpu_cnt, 1);
  1009. /*
  1010. * Each pass through this loop enqueues a callback, but only
  1011. * on CPUs already having callbacks enqueued. Note that if
  1012. * a CPU already has callbacks enqueue, it must have already
  1013. * registered the need for a future grace period, so all we
  1014. * need do is enqueue a callback that will use the same
  1015. * grace period as the last callback already in the queue.
  1016. */
  1017. for_each_possible_cpu(cpu) {
  1018. sdp = per_cpu_ptr(ssp->sda, cpu);
  1019. spin_lock_irq_rcu_node(sdp);
  1020. atomic_inc(&ssp->srcu_barrier_cpu_cnt);
  1021. sdp->srcu_barrier_head.func = srcu_barrier_cb;
  1022. debug_rcu_head_queue(&sdp->srcu_barrier_head);
  1023. if (!rcu_segcblist_entrain(&sdp->srcu_cblist,
  1024. &sdp->srcu_barrier_head)) {
  1025. debug_rcu_head_unqueue(&sdp->srcu_barrier_head);
  1026. atomic_dec(&ssp->srcu_barrier_cpu_cnt);
  1027. }
  1028. spin_unlock_irq_rcu_node(sdp);
  1029. }
  1030. /* Remove the initial count, at which point reaching zero can happen. */
  1031. if (atomic_dec_and_test(&ssp->srcu_barrier_cpu_cnt))
  1032. complete(&ssp->srcu_barrier_completion);
  1033. wait_for_completion(&ssp->srcu_barrier_completion);
  1034. rcu_seq_end(&ssp->srcu_barrier_seq);
  1035. mutex_unlock(&ssp->srcu_barrier_mutex);
  1036. }
  1037. EXPORT_SYMBOL_GPL(srcu_barrier);
  1038. /**
  1039. * srcu_batches_completed - return batches completed.
  1040. * @ssp: srcu_struct on which to report batch completion.
  1041. *
  1042. * Report the number of batches, correlated with, but not necessarily
  1043. * precisely the same as, the number of grace periods that have elapsed.
  1044. */
  1045. unsigned long srcu_batches_completed(struct srcu_struct *ssp)
  1046. {
  1047. return READ_ONCE(ssp->srcu_idx);
  1048. }
  1049. EXPORT_SYMBOL_GPL(srcu_batches_completed);
  1050. /*
  1051. * Core SRCU state machine. Push state bits of ->srcu_gp_seq
  1052. * to SRCU_STATE_SCAN2, and invoke srcu_gp_end() when scan has
  1053. * completed in that state.
  1054. */
  1055. static void srcu_advance_state(struct srcu_struct *ssp)
  1056. {
  1057. int idx;
  1058. mutex_lock(&ssp->srcu_gp_mutex);
  1059. /*
  1060. * Because readers might be delayed for an extended period after
  1061. * fetching ->srcu_idx for their index, at any point in time there
  1062. * might well be readers using both idx=0 and idx=1. We therefore
  1063. * need to wait for readers to clear from both index values before
  1064. * invoking a callback.
  1065. *
  1066. * The load-acquire ensures that we see the accesses performed
  1067. * by the prior grace period.
  1068. */
  1069. idx = rcu_seq_state(smp_load_acquire(&ssp->srcu_gp_seq)); /* ^^^ */
  1070. if (idx == SRCU_STATE_IDLE) {
  1071. spin_lock_irq_rcu_node(ssp);
  1072. if (ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed)) {
  1073. WARN_ON_ONCE(rcu_seq_state(ssp->srcu_gp_seq));
  1074. spin_unlock_irq_rcu_node(ssp);
  1075. mutex_unlock(&ssp->srcu_gp_mutex);
  1076. return;
  1077. }
  1078. idx = rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq));
  1079. if (idx == SRCU_STATE_IDLE)
  1080. srcu_gp_start(ssp);
  1081. spin_unlock_irq_rcu_node(ssp);
  1082. if (idx != SRCU_STATE_IDLE) {
  1083. mutex_unlock(&ssp->srcu_gp_mutex);
  1084. return; /* Someone else started the grace period. */
  1085. }
  1086. }
  1087. if (rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)) == SRCU_STATE_SCAN1) {
  1088. idx = 1 ^ (ssp->srcu_idx & 1);
  1089. if (!try_check_zero(ssp, idx, 1)) {
  1090. mutex_unlock(&ssp->srcu_gp_mutex);
  1091. return; /* readers present, retry later. */
  1092. }
  1093. srcu_flip(ssp);
  1094. spin_lock_irq_rcu_node(ssp);
  1095. rcu_seq_set_state(&ssp->srcu_gp_seq, SRCU_STATE_SCAN2);
  1096. spin_unlock_irq_rcu_node(ssp);
  1097. }
  1098. if (rcu_seq_state(READ_ONCE(ssp->srcu_gp_seq)) == SRCU_STATE_SCAN2) {
  1099. /*
  1100. * SRCU read-side critical sections are normally short,
  1101. * so check at least twice in quick succession after a flip.
  1102. */
  1103. idx = 1 ^ (ssp->srcu_idx & 1);
  1104. if (!try_check_zero(ssp, idx, 2)) {
  1105. mutex_unlock(&ssp->srcu_gp_mutex);
  1106. return; /* readers present, retry later. */
  1107. }
  1108. srcu_gp_end(ssp); /* Releases ->srcu_gp_mutex. */
  1109. }
  1110. }
  1111. /*
  1112. * Invoke a limited number of SRCU callbacks that have passed through
  1113. * their grace period. If there are more to do, SRCU will reschedule
  1114. * the workqueue. Note that needed memory barriers have been executed
  1115. * in this task's context by srcu_readers_active_idx_check().
  1116. */
  1117. static void srcu_invoke_callbacks(struct work_struct *work)
  1118. {
  1119. bool more;
  1120. struct rcu_cblist ready_cbs;
  1121. struct rcu_head *rhp;
  1122. struct srcu_data *sdp;
  1123. struct srcu_struct *ssp;
  1124. sdp = container_of(work, struct srcu_data, work);
  1125. ssp = sdp->ssp;
  1126. rcu_cblist_init(&ready_cbs);
  1127. spin_lock_irq_rcu_node(sdp);
  1128. rcu_segcblist_advance(&sdp->srcu_cblist,
  1129. rcu_seq_current(&ssp->srcu_gp_seq));
  1130. if (sdp->srcu_cblist_invoking ||
  1131. !rcu_segcblist_ready_cbs(&sdp->srcu_cblist)) {
  1132. spin_unlock_irq_rcu_node(sdp);
  1133. return; /* Someone else on the job or nothing to do. */
  1134. }
  1135. /* We are on the job! Extract and invoke ready callbacks. */
  1136. sdp->srcu_cblist_invoking = true;
  1137. rcu_segcblist_extract_done_cbs(&sdp->srcu_cblist, &ready_cbs);
  1138. spin_unlock_irq_rcu_node(sdp);
  1139. rhp = rcu_cblist_dequeue(&ready_cbs);
  1140. for (; rhp != NULL; rhp = rcu_cblist_dequeue(&ready_cbs)) {
  1141. debug_rcu_head_unqueue(rhp);
  1142. local_bh_disable();
  1143. rhp->func(rhp);
  1144. local_bh_enable();
  1145. }
  1146. /*
  1147. * Update counts, accelerate new callbacks, and if needed,
  1148. * schedule another round of callback invocation.
  1149. */
  1150. spin_lock_irq_rcu_node(sdp);
  1151. rcu_segcblist_insert_count(&sdp->srcu_cblist, &ready_cbs);
  1152. (void)rcu_segcblist_accelerate(&sdp->srcu_cblist,
  1153. rcu_seq_snap(&ssp->srcu_gp_seq));
  1154. sdp->srcu_cblist_invoking = false;
  1155. more = rcu_segcblist_ready_cbs(&sdp->srcu_cblist);
  1156. spin_unlock_irq_rcu_node(sdp);
  1157. if (more)
  1158. srcu_schedule_cbs_sdp(sdp, 0);
  1159. }
  1160. /*
  1161. * Finished one round of SRCU grace period. Start another if there are
  1162. * more SRCU callbacks queued, otherwise put SRCU into not-running state.
  1163. */
  1164. static void srcu_reschedule(struct srcu_struct *ssp, unsigned long delay)
  1165. {
  1166. bool pushgp = true;
  1167. spin_lock_irq_rcu_node(ssp);
  1168. if (ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed)) {
  1169. if (!WARN_ON_ONCE(rcu_seq_state(ssp->srcu_gp_seq))) {
  1170. /* All requests fulfilled, time to go idle. */
  1171. pushgp = false;
  1172. }
  1173. } else if (!rcu_seq_state(ssp->srcu_gp_seq)) {
  1174. /* Outstanding request and no GP. Start one. */
  1175. srcu_gp_start(ssp);
  1176. }
  1177. spin_unlock_irq_rcu_node(ssp);
  1178. if (pushgp)
  1179. queue_delayed_work(rcu_gp_wq, &ssp->work, delay);
  1180. }
  1181. /*
  1182. * This is the work-queue function that handles SRCU grace periods.
  1183. */
  1184. static void process_srcu(struct work_struct *work)
  1185. {
  1186. struct srcu_struct *ssp;
  1187. ssp = container_of(work, struct srcu_struct, work.work);
  1188. srcu_advance_state(ssp);
  1189. srcu_reschedule(ssp, srcu_get_delay(ssp));
  1190. }
  1191. void srcutorture_get_gp_data(enum rcutorture_type test_type,
  1192. struct srcu_struct *ssp, int *flags,
  1193. unsigned long *gp_seq)
  1194. {
  1195. if (test_type != SRCU_FLAVOR)
  1196. return;
  1197. *flags = 0;
  1198. *gp_seq = rcu_seq_current(&ssp->srcu_gp_seq);
  1199. }
  1200. EXPORT_SYMBOL_GPL(srcutorture_get_gp_data);
  1201. void srcu_torture_stats_print(struct srcu_struct *ssp, char *tt, char *tf)
  1202. {
  1203. int cpu;
  1204. int idx;
  1205. unsigned long s0 = 0, s1 = 0;
  1206. idx = ssp->srcu_idx & 0x1;
  1207. pr_alert("%s%s Tree SRCU g%ld per-CPU(idx=%d):",
  1208. tt, tf, rcu_seq_current(&ssp->srcu_gp_seq), idx);
  1209. for_each_possible_cpu(cpu) {
  1210. unsigned long l0, l1;
  1211. unsigned long u0, u1;
  1212. long c0, c1;
  1213. struct srcu_data *sdp;
  1214. sdp = per_cpu_ptr(ssp->sda, cpu);
  1215. u0 = data_race(sdp->srcu_unlock_count[!idx]);
  1216. u1 = data_race(sdp->srcu_unlock_count[idx]);
  1217. /*
  1218. * Make sure that a lock is always counted if the corresponding
  1219. * unlock is counted.
  1220. */
  1221. smp_rmb();
  1222. l0 = data_race(sdp->srcu_lock_count[!idx]);
  1223. l1 = data_race(sdp->srcu_lock_count[idx]);
  1224. c0 = l0 - u0;
  1225. c1 = l1 - u1;
  1226. pr_cont(" %d(%ld,%ld %c)",
  1227. cpu, c0, c1,
  1228. "C."[rcu_segcblist_empty(&sdp->srcu_cblist)]);
  1229. s0 += c0;
  1230. s1 += c1;
  1231. }
  1232. pr_cont(" T(%ld,%ld)\n", s0, s1);
  1233. }
  1234. EXPORT_SYMBOL_GPL(srcu_torture_stats_print);
  1235. static int __init srcu_bootup_announce(void)
  1236. {
  1237. pr_info("Hierarchical SRCU implementation.\n");
  1238. if (exp_holdoff != DEFAULT_SRCU_EXP_HOLDOFF)
  1239. pr_info("\tNon-default auto-expedite holdoff of %lu ns.\n", exp_holdoff);
  1240. return 0;
  1241. }
  1242. early_initcall(srcu_bootup_announce);
  1243. void __init srcu_init(void)
  1244. {
  1245. struct srcu_struct *ssp;
  1246. srcu_init_done = true;
  1247. while (!list_empty(&srcu_boot_list)) {
  1248. ssp = list_first_entry(&srcu_boot_list, struct srcu_struct,
  1249. work.work.entry);
  1250. check_init_srcu_struct(ssp);
  1251. list_del_init(&ssp->work.work.entry);
  1252. queue_work(rcu_gp_wq, &ssp->work.work);
  1253. }
  1254. }
  1255. #ifdef CONFIG_MODULES
  1256. /* Initialize any global-scope srcu_struct structures used by this module. */
  1257. static int srcu_module_coming(struct module *mod)
  1258. {
  1259. int i;
  1260. struct srcu_struct **sspp = mod->srcu_struct_ptrs;
  1261. int ret;
  1262. for (i = 0; i < mod->num_srcu_structs; i++) {
  1263. ret = init_srcu_struct(*(sspp++));
  1264. if (WARN_ON_ONCE(ret))
  1265. return ret;
  1266. }
  1267. return 0;
  1268. }
  1269. /* Clean up any global-scope srcu_struct structures used by this module. */
  1270. static void srcu_module_going(struct module *mod)
  1271. {
  1272. int i;
  1273. struct srcu_struct **sspp = mod->srcu_struct_ptrs;
  1274. for (i = 0; i < mod->num_srcu_structs; i++)
  1275. cleanup_srcu_struct(*(sspp++));
  1276. }
  1277. /* Handle one module, either coming or going. */
  1278. static int srcu_module_notify(struct notifier_block *self,
  1279. unsigned long val, void *data)
  1280. {
  1281. struct module *mod = data;
  1282. int ret = 0;
  1283. switch (val) {
  1284. case MODULE_STATE_COMING:
  1285. ret = srcu_module_coming(mod);
  1286. break;
  1287. case MODULE_STATE_GOING:
  1288. srcu_module_going(mod);
  1289. break;
  1290. default:
  1291. break;
  1292. }
  1293. return ret;
  1294. }
  1295. static struct notifier_block srcu_module_nb = {
  1296. .notifier_call = srcu_module_notify,
  1297. .priority = 0,
  1298. };
  1299. static __init int init_srcu_module_notifier(void)
  1300. {
  1301. int ret;
  1302. ret = register_module_notifier(&srcu_module_nb);
  1303. if (ret)
  1304. pr_warn("Failed to register srcu module notifier\n");
  1305. return ret;
  1306. }
  1307. late_initcall(init_srcu_module_notifier);
  1308. #endif /* #ifdef CONFIG_MODULES */