rcu_segcblist.c 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * RCU segmented callback lists, function definitions
  4. *
  5. * Copyright IBM Corporation, 2017
  6. *
  7. * Authors: Paul E. McKenney <[email protected]>
  8. */
  9. #include <linux/cpu.h>
  10. #include <linux/interrupt.h>
  11. #include <linux/kernel.h>
  12. #include <linux/types.h>
  13. #include "rcu_segcblist.h"
  14. /* Initialize simple callback list. */
  15. void rcu_cblist_init(struct rcu_cblist *rclp)
  16. {
  17. rclp->head = NULL;
  18. rclp->tail = &rclp->head;
  19. rclp->len = 0;
  20. }
  21. /*
  22. * Enqueue an rcu_head structure onto the specified callback list.
  23. */
  24. void rcu_cblist_enqueue(struct rcu_cblist *rclp, struct rcu_head *rhp)
  25. {
  26. *rclp->tail = rhp;
  27. rclp->tail = &rhp->next;
  28. WRITE_ONCE(rclp->len, rclp->len + 1);
  29. }
  30. /*
  31. * Flush the second rcu_cblist structure onto the first one, obliterating
  32. * any contents of the first. If rhp is non-NULL, enqueue it as the sole
  33. * element of the second rcu_cblist structure, but ensuring that the second
  34. * rcu_cblist structure, if initially non-empty, always appears non-empty
  35. * throughout the process. If rdp is NULL, the second rcu_cblist structure
  36. * is instead initialized to empty.
  37. */
  38. void rcu_cblist_flush_enqueue(struct rcu_cblist *drclp,
  39. struct rcu_cblist *srclp,
  40. struct rcu_head *rhp)
  41. {
  42. drclp->head = srclp->head;
  43. if (drclp->head)
  44. drclp->tail = srclp->tail;
  45. else
  46. drclp->tail = &drclp->head;
  47. drclp->len = srclp->len;
  48. if (!rhp) {
  49. rcu_cblist_init(srclp);
  50. } else {
  51. rhp->next = NULL;
  52. srclp->head = rhp;
  53. srclp->tail = &rhp->next;
  54. WRITE_ONCE(srclp->len, 1);
  55. }
  56. }
  57. /*
  58. * Dequeue the oldest rcu_head structure from the specified callback
  59. * list.
  60. */
  61. struct rcu_head *rcu_cblist_dequeue(struct rcu_cblist *rclp)
  62. {
  63. struct rcu_head *rhp;
  64. rhp = rclp->head;
  65. if (!rhp)
  66. return NULL;
  67. rclp->len--;
  68. rclp->head = rhp->next;
  69. if (!rclp->head)
  70. rclp->tail = &rclp->head;
  71. return rhp;
  72. }
  73. /* Set the length of an rcu_segcblist structure. */
  74. static void rcu_segcblist_set_len(struct rcu_segcblist *rsclp, long v)
  75. {
  76. #ifdef CONFIG_RCU_NOCB_CPU
  77. atomic_long_set(&rsclp->len, v);
  78. #else
  79. WRITE_ONCE(rsclp->len, v);
  80. #endif
  81. }
  82. /* Get the length of a segment of the rcu_segcblist structure. */
  83. static long rcu_segcblist_get_seglen(struct rcu_segcblist *rsclp, int seg)
  84. {
  85. return READ_ONCE(rsclp->seglen[seg]);
  86. }
  87. /* Return number of callbacks in segmented callback list by summing seglen. */
  88. long rcu_segcblist_n_segment_cbs(struct rcu_segcblist *rsclp)
  89. {
  90. long len = 0;
  91. int i;
  92. for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
  93. len += rcu_segcblist_get_seglen(rsclp, i);
  94. return len;
  95. }
  96. /* Set the length of a segment of the rcu_segcblist structure. */
  97. static void rcu_segcblist_set_seglen(struct rcu_segcblist *rsclp, int seg, long v)
  98. {
  99. WRITE_ONCE(rsclp->seglen[seg], v);
  100. }
  101. /* Increase the numeric length of a segment by a specified amount. */
  102. static void rcu_segcblist_add_seglen(struct rcu_segcblist *rsclp, int seg, long v)
  103. {
  104. WRITE_ONCE(rsclp->seglen[seg], rsclp->seglen[seg] + v);
  105. }
  106. /* Move from's segment length to to's segment. */
  107. static void rcu_segcblist_move_seglen(struct rcu_segcblist *rsclp, int from, int to)
  108. {
  109. long len;
  110. if (from == to)
  111. return;
  112. len = rcu_segcblist_get_seglen(rsclp, from);
  113. if (!len)
  114. return;
  115. rcu_segcblist_add_seglen(rsclp, to, len);
  116. rcu_segcblist_set_seglen(rsclp, from, 0);
  117. }
  118. /* Increment segment's length. */
  119. static void rcu_segcblist_inc_seglen(struct rcu_segcblist *rsclp, int seg)
  120. {
  121. rcu_segcblist_add_seglen(rsclp, seg, 1);
  122. }
  123. /*
  124. * Increase the numeric length of an rcu_segcblist structure by the
  125. * specified amount, which can be negative. This can cause the ->len
  126. * field to disagree with the actual number of callbacks on the structure.
  127. * This increase is fully ordered with respect to the callers accesses
  128. * both before and after.
  129. *
  130. * So why on earth is a memory barrier required both before and after
  131. * the update to the ->len field???
  132. *
  133. * The reason is that rcu_barrier() locklessly samples each CPU's ->len
  134. * field, and if a given CPU's field is zero, avoids IPIing that CPU.
  135. * This can of course race with both queuing and invoking of callbacks.
  136. * Failing to correctly handle either of these races could result in
  137. * rcu_barrier() failing to IPI a CPU that actually had callbacks queued
  138. * which rcu_barrier() was obligated to wait on. And if rcu_barrier()
  139. * failed to wait on such a callback, unloading certain kernel modules
  140. * would result in calls to functions whose code was no longer present in
  141. * the kernel, for but one example.
  142. *
  143. * Therefore, ->len transitions from 1->0 and 0->1 have to be carefully
  144. * ordered with respect with both list modifications and the rcu_barrier().
  145. *
  146. * The queuing case is CASE 1 and the invoking case is CASE 2.
  147. *
  148. * CASE 1: Suppose that CPU 0 has no callbacks queued, but invokes
  149. * call_rcu() just as CPU 1 invokes rcu_barrier(). CPU 0's ->len field
  150. * will transition from 0->1, which is one of the transitions that must
  151. * be handled carefully. Without the full memory barriers after the ->len
  152. * update and at the beginning of rcu_barrier(), the following could happen:
  153. *
  154. * CPU 0 CPU 1
  155. *
  156. * call_rcu().
  157. * rcu_barrier() sees ->len as 0.
  158. * set ->len = 1.
  159. * rcu_barrier() does nothing.
  160. * module is unloaded.
  161. * callback invokes unloaded function!
  162. *
  163. * With the full barriers, any case where rcu_barrier() sees ->len as 0 will
  164. * have unambiguously preceded the return from the racing call_rcu(), which
  165. * means that this call_rcu() invocation is OK to not wait on. After all,
  166. * you are supposed to make sure that any problematic call_rcu() invocations
  167. * happen before the rcu_barrier().
  168. *
  169. *
  170. * CASE 2: Suppose that CPU 0 is invoking its last callback just as
  171. * CPU 1 invokes rcu_barrier(). CPU 0's ->len field will transition from
  172. * 1->0, which is one of the transitions that must be handled carefully.
  173. * Without the full memory barriers before the ->len update and at the
  174. * end of rcu_barrier(), the following could happen:
  175. *
  176. * CPU 0 CPU 1
  177. *
  178. * start invoking last callback
  179. * set ->len = 0 (reordered)
  180. * rcu_barrier() sees ->len as 0
  181. * rcu_barrier() does nothing.
  182. * module is unloaded
  183. * callback executing after unloaded!
  184. *
  185. * With the full barriers, any case where rcu_barrier() sees ->len as 0
  186. * will be fully ordered after the completion of the callback function,
  187. * so that the module unloading operation is completely safe.
  188. *
  189. */
  190. void rcu_segcblist_add_len(struct rcu_segcblist *rsclp, long v)
  191. {
  192. #ifdef CONFIG_RCU_NOCB_CPU
  193. smp_mb__before_atomic(); // Read header comment above.
  194. atomic_long_add(v, &rsclp->len);
  195. smp_mb__after_atomic(); // Read header comment above.
  196. #else
  197. smp_mb(); // Read header comment above.
  198. WRITE_ONCE(rsclp->len, rsclp->len + v);
  199. smp_mb(); // Read header comment above.
  200. #endif
  201. }
  202. /*
  203. * Increase the numeric length of an rcu_segcblist structure by one.
  204. * This can cause the ->len field to disagree with the actual number of
  205. * callbacks on the structure. This increase is fully ordered with respect
  206. * to the callers accesses both before and after.
  207. */
  208. void rcu_segcblist_inc_len(struct rcu_segcblist *rsclp)
  209. {
  210. rcu_segcblist_add_len(rsclp, 1);
  211. }
  212. /*
  213. * Initialize an rcu_segcblist structure.
  214. */
  215. void rcu_segcblist_init(struct rcu_segcblist *rsclp)
  216. {
  217. int i;
  218. BUILD_BUG_ON(RCU_NEXT_TAIL + 1 != ARRAY_SIZE(rsclp->gp_seq));
  219. BUILD_BUG_ON(ARRAY_SIZE(rsclp->tails) != ARRAY_SIZE(rsclp->gp_seq));
  220. rsclp->head = NULL;
  221. for (i = 0; i < RCU_CBLIST_NSEGS; i++) {
  222. rsclp->tails[i] = &rsclp->head;
  223. rcu_segcblist_set_seglen(rsclp, i, 0);
  224. }
  225. rcu_segcblist_set_len(rsclp, 0);
  226. rcu_segcblist_set_flags(rsclp, SEGCBLIST_ENABLED);
  227. }
  228. /*
  229. * Disable the specified rcu_segcblist structure, so that callbacks can
  230. * no longer be posted to it. This structure must be empty.
  231. */
  232. void rcu_segcblist_disable(struct rcu_segcblist *rsclp)
  233. {
  234. WARN_ON_ONCE(!rcu_segcblist_empty(rsclp));
  235. WARN_ON_ONCE(rcu_segcblist_n_cbs(rsclp));
  236. rcu_segcblist_clear_flags(rsclp, SEGCBLIST_ENABLED);
  237. }
  238. /*
  239. * Mark the specified rcu_segcblist structure as offloaded (or not)
  240. */
  241. void rcu_segcblist_offload(struct rcu_segcblist *rsclp, bool offload)
  242. {
  243. if (offload)
  244. rcu_segcblist_set_flags(rsclp, SEGCBLIST_LOCKING | SEGCBLIST_OFFLOADED);
  245. else
  246. rcu_segcblist_clear_flags(rsclp, SEGCBLIST_OFFLOADED);
  247. }
  248. /*
  249. * Does the specified rcu_segcblist structure contain callbacks that
  250. * are ready to be invoked?
  251. */
  252. bool rcu_segcblist_ready_cbs(struct rcu_segcblist *rsclp)
  253. {
  254. return rcu_segcblist_is_enabled(rsclp) &&
  255. &rsclp->head != READ_ONCE(rsclp->tails[RCU_DONE_TAIL]);
  256. }
  257. /*
  258. * Does the specified rcu_segcblist structure contain callbacks that
  259. * are still pending, that is, not yet ready to be invoked?
  260. */
  261. bool rcu_segcblist_pend_cbs(struct rcu_segcblist *rsclp)
  262. {
  263. return rcu_segcblist_is_enabled(rsclp) &&
  264. !rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL);
  265. }
  266. /*
  267. * Return a pointer to the first callback in the specified rcu_segcblist
  268. * structure. This is useful for diagnostics.
  269. */
  270. struct rcu_head *rcu_segcblist_first_cb(struct rcu_segcblist *rsclp)
  271. {
  272. if (rcu_segcblist_is_enabled(rsclp))
  273. return rsclp->head;
  274. return NULL;
  275. }
  276. /*
  277. * Return a pointer to the first pending callback in the specified
  278. * rcu_segcblist structure. This is useful just after posting a given
  279. * callback -- if that callback is the first pending callback, then
  280. * you cannot rely on someone else having already started up the required
  281. * grace period.
  282. */
  283. struct rcu_head *rcu_segcblist_first_pend_cb(struct rcu_segcblist *rsclp)
  284. {
  285. if (rcu_segcblist_is_enabled(rsclp))
  286. return *rsclp->tails[RCU_DONE_TAIL];
  287. return NULL;
  288. }
  289. /*
  290. * Return false if there are no CBs awaiting grace periods, otherwise,
  291. * return true and store the nearest waited-upon grace period into *lp.
  292. */
  293. bool rcu_segcblist_nextgp(struct rcu_segcblist *rsclp, unsigned long *lp)
  294. {
  295. if (!rcu_segcblist_pend_cbs(rsclp))
  296. return false;
  297. *lp = rsclp->gp_seq[RCU_WAIT_TAIL];
  298. return true;
  299. }
  300. /*
  301. * Enqueue the specified callback onto the specified rcu_segcblist
  302. * structure, updating accounting as needed. Note that the ->len
  303. * field may be accessed locklessly, hence the WRITE_ONCE().
  304. * The ->len field is used by rcu_barrier() and friends to determine
  305. * if it must post a callback on this structure, and it is OK
  306. * for rcu_barrier() to sometimes post callbacks needlessly, but
  307. * absolutely not OK for it to ever miss posting a callback.
  308. */
  309. void rcu_segcblist_enqueue(struct rcu_segcblist *rsclp,
  310. struct rcu_head *rhp)
  311. {
  312. rcu_segcblist_inc_len(rsclp);
  313. rcu_segcblist_inc_seglen(rsclp, RCU_NEXT_TAIL);
  314. rhp->next = NULL;
  315. WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rhp);
  316. WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], &rhp->next);
  317. }
  318. /*
  319. * Entrain the specified callback onto the specified rcu_segcblist at
  320. * the end of the last non-empty segment. If the entire rcu_segcblist
  321. * is empty, make no change, but return false.
  322. *
  323. * This is intended for use by rcu_barrier()-like primitives, -not-
  324. * for normal grace-period use. IMPORTANT: The callback you enqueue
  325. * will wait for all prior callbacks, NOT necessarily for a grace
  326. * period. You have been warned.
  327. */
  328. bool rcu_segcblist_entrain(struct rcu_segcblist *rsclp,
  329. struct rcu_head *rhp)
  330. {
  331. int i;
  332. if (rcu_segcblist_n_cbs(rsclp) == 0)
  333. return false;
  334. rcu_segcblist_inc_len(rsclp);
  335. smp_mb(); /* Ensure counts are updated before callback is entrained. */
  336. rhp->next = NULL;
  337. for (i = RCU_NEXT_TAIL; i > RCU_DONE_TAIL; i--)
  338. if (rsclp->tails[i] != rsclp->tails[i - 1])
  339. break;
  340. rcu_segcblist_inc_seglen(rsclp, i);
  341. WRITE_ONCE(*rsclp->tails[i], rhp);
  342. for (; i <= RCU_NEXT_TAIL; i++)
  343. WRITE_ONCE(rsclp->tails[i], &rhp->next);
  344. return true;
  345. }
  346. /*
  347. * Extract only those callbacks ready to be invoked from the specified
  348. * rcu_segcblist structure and place them in the specified rcu_cblist
  349. * structure.
  350. */
  351. void rcu_segcblist_extract_done_cbs(struct rcu_segcblist *rsclp,
  352. struct rcu_cblist *rclp)
  353. {
  354. int i;
  355. if (!rcu_segcblist_ready_cbs(rsclp))
  356. return; /* Nothing to do. */
  357. rclp->len = rcu_segcblist_get_seglen(rsclp, RCU_DONE_TAIL);
  358. *rclp->tail = rsclp->head;
  359. WRITE_ONCE(rsclp->head, *rsclp->tails[RCU_DONE_TAIL]);
  360. WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
  361. rclp->tail = rsclp->tails[RCU_DONE_TAIL];
  362. for (i = RCU_CBLIST_NSEGS - 1; i >= RCU_DONE_TAIL; i--)
  363. if (rsclp->tails[i] == rsclp->tails[RCU_DONE_TAIL])
  364. WRITE_ONCE(rsclp->tails[i], &rsclp->head);
  365. rcu_segcblist_set_seglen(rsclp, RCU_DONE_TAIL, 0);
  366. }
  367. /*
  368. * Extract only those callbacks still pending (not yet ready to be
  369. * invoked) from the specified rcu_segcblist structure and place them in
  370. * the specified rcu_cblist structure. Note that this loses information
  371. * about any callbacks that might have been partway done waiting for
  372. * their grace period. Too bad! They will have to start over.
  373. */
  374. void rcu_segcblist_extract_pend_cbs(struct rcu_segcblist *rsclp,
  375. struct rcu_cblist *rclp)
  376. {
  377. int i;
  378. if (!rcu_segcblist_pend_cbs(rsclp))
  379. return; /* Nothing to do. */
  380. rclp->len = 0;
  381. *rclp->tail = *rsclp->tails[RCU_DONE_TAIL];
  382. rclp->tail = rsclp->tails[RCU_NEXT_TAIL];
  383. WRITE_ONCE(*rsclp->tails[RCU_DONE_TAIL], NULL);
  384. for (i = RCU_DONE_TAIL + 1; i < RCU_CBLIST_NSEGS; i++) {
  385. rclp->len += rcu_segcblist_get_seglen(rsclp, i);
  386. WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_DONE_TAIL]);
  387. rcu_segcblist_set_seglen(rsclp, i, 0);
  388. }
  389. }
  390. /*
  391. * Insert counts from the specified rcu_cblist structure in the
  392. * specified rcu_segcblist structure.
  393. */
  394. void rcu_segcblist_insert_count(struct rcu_segcblist *rsclp,
  395. struct rcu_cblist *rclp)
  396. {
  397. rcu_segcblist_add_len(rsclp, rclp->len);
  398. }
  399. /*
  400. * Move callbacks from the specified rcu_cblist to the beginning of the
  401. * done-callbacks segment of the specified rcu_segcblist.
  402. */
  403. void rcu_segcblist_insert_done_cbs(struct rcu_segcblist *rsclp,
  404. struct rcu_cblist *rclp)
  405. {
  406. int i;
  407. if (!rclp->head)
  408. return; /* No callbacks to move. */
  409. rcu_segcblist_add_seglen(rsclp, RCU_DONE_TAIL, rclp->len);
  410. *rclp->tail = rsclp->head;
  411. WRITE_ONCE(rsclp->head, rclp->head);
  412. for (i = RCU_DONE_TAIL; i < RCU_CBLIST_NSEGS; i++)
  413. if (&rsclp->head == rsclp->tails[i])
  414. WRITE_ONCE(rsclp->tails[i], rclp->tail);
  415. else
  416. break;
  417. rclp->head = NULL;
  418. rclp->tail = &rclp->head;
  419. }
  420. /*
  421. * Move callbacks from the specified rcu_cblist to the end of the
  422. * new-callbacks segment of the specified rcu_segcblist.
  423. */
  424. void rcu_segcblist_insert_pend_cbs(struct rcu_segcblist *rsclp,
  425. struct rcu_cblist *rclp)
  426. {
  427. if (!rclp->head)
  428. return; /* Nothing to do. */
  429. rcu_segcblist_add_seglen(rsclp, RCU_NEXT_TAIL, rclp->len);
  430. WRITE_ONCE(*rsclp->tails[RCU_NEXT_TAIL], rclp->head);
  431. WRITE_ONCE(rsclp->tails[RCU_NEXT_TAIL], rclp->tail);
  432. }
  433. /*
  434. * Advance the callbacks in the specified rcu_segcblist structure based
  435. * on the current value passed in for the grace-period counter.
  436. */
  437. void rcu_segcblist_advance(struct rcu_segcblist *rsclp, unsigned long seq)
  438. {
  439. int i, j;
  440. WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
  441. if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
  442. return;
  443. /*
  444. * Find all callbacks whose ->gp_seq numbers indicate that they
  445. * are ready to invoke, and put them into the RCU_DONE_TAIL segment.
  446. */
  447. for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
  448. if (ULONG_CMP_LT(seq, rsclp->gp_seq[i]))
  449. break;
  450. WRITE_ONCE(rsclp->tails[RCU_DONE_TAIL], rsclp->tails[i]);
  451. rcu_segcblist_move_seglen(rsclp, i, RCU_DONE_TAIL);
  452. }
  453. /* If no callbacks moved, nothing more need be done. */
  454. if (i == RCU_WAIT_TAIL)
  455. return;
  456. /* Clean up tail pointers that might have been misordered above. */
  457. for (j = RCU_WAIT_TAIL; j < i; j++)
  458. WRITE_ONCE(rsclp->tails[j], rsclp->tails[RCU_DONE_TAIL]);
  459. /*
  460. * Callbacks moved, so there might be an empty RCU_WAIT_TAIL
  461. * and a non-empty RCU_NEXT_READY_TAIL. If so, copy the
  462. * RCU_NEXT_READY_TAIL segment to fill the RCU_WAIT_TAIL gap
  463. * created by the now-ready-to-invoke segments.
  464. */
  465. for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
  466. if (rsclp->tails[j] == rsclp->tails[RCU_NEXT_TAIL])
  467. break; /* No more callbacks. */
  468. WRITE_ONCE(rsclp->tails[j], rsclp->tails[i]);
  469. rcu_segcblist_move_seglen(rsclp, i, j);
  470. rsclp->gp_seq[j] = rsclp->gp_seq[i];
  471. }
  472. }
  473. /*
  474. * "Accelerate" callbacks based on more-accurate grace-period information.
  475. * The reason for this is that RCU does not synchronize the beginnings and
  476. * ends of grace periods, and that callbacks are posted locally. This in
  477. * turn means that the callbacks must be labelled conservatively early
  478. * on, as getting exact information would degrade both performance and
  479. * scalability. When more accurate grace-period information becomes
  480. * available, previously posted callbacks can be "accelerated", marking
  481. * them to complete at the end of the earlier grace period.
  482. *
  483. * This function operates on an rcu_segcblist structure, and also the
  484. * grace-period sequence number seq at which new callbacks would become
  485. * ready to invoke. Returns true if there are callbacks that won't be
  486. * ready to invoke until seq, false otherwise.
  487. */
  488. bool rcu_segcblist_accelerate(struct rcu_segcblist *rsclp, unsigned long seq)
  489. {
  490. int i, j;
  491. WARN_ON_ONCE(!rcu_segcblist_is_enabled(rsclp));
  492. if (rcu_segcblist_restempty(rsclp, RCU_DONE_TAIL))
  493. return false;
  494. /*
  495. * Find the segment preceding the oldest segment of callbacks
  496. * whose ->gp_seq[] completion is at or after that passed in via
  497. * "seq", skipping any empty segments. This oldest segment, along
  498. * with any later segments, can be merged in with any newly arrived
  499. * callbacks in the RCU_NEXT_TAIL segment, and assigned "seq"
  500. * as their ->gp_seq[] grace-period completion sequence number.
  501. */
  502. for (i = RCU_NEXT_READY_TAIL; i > RCU_DONE_TAIL; i--)
  503. if (rsclp->tails[i] != rsclp->tails[i - 1] &&
  504. ULONG_CMP_LT(rsclp->gp_seq[i], seq))
  505. break;
  506. /*
  507. * If all the segments contain callbacks that correspond to
  508. * earlier grace-period sequence numbers than "seq", leave.
  509. * Assuming that the rcu_segcblist structure has enough
  510. * segments in its arrays, this can only happen if some of
  511. * the non-done segments contain callbacks that really are
  512. * ready to invoke. This situation will get straightened
  513. * out by the next call to rcu_segcblist_advance().
  514. *
  515. * Also advance to the oldest segment of callbacks whose
  516. * ->gp_seq[] completion is at or after that passed in via "seq",
  517. * skipping any empty segments.
  518. *
  519. * Note that segment "i" (and any lower-numbered segments
  520. * containing older callbacks) will be unaffected, and their
  521. * grace-period numbers remain unchanged. For example, if i ==
  522. * WAIT_TAIL, then neither WAIT_TAIL nor DONE_TAIL will be touched.
  523. * Instead, the CBs in NEXT_TAIL will be merged with those in
  524. * NEXT_READY_TAIL and the grace-period number of NEXT_READY_TAIL
  525. * would be updated. NEXT_TAIL would then be empty.
  526. */
  527. if (rcu_segcblist_restempty(rsclp, i) || ++i >= RCU_NEXT_TAIL)
  528. return false;
  529. /* Accounting: everything below i is about to get merged into i. */
  530. for (j = i + 1; j <= RCU_NEXT_TAIL; j++)
  531. rcu_segcblist_move_seglen(rsclp, j, i);
  532. /*
  533. * Merge all later callbacks, including newly arrived callbacks,
  534. * into the segment located by the for-loop above. Assign "seq"
  535. * as the ->gp_seq[] value in order to correctly handle the case
  536. * where there were no pending callbacks in the rcu_segcblist
  537. * structure other than in the RCU_NEXT_TAIL segment.
  538. */
  539. for (; i < RCU_NEXT_TAIL; i++) {
  540. WRITE_ONCE(rsclp->tails[i], rsclp->tails[RCU_NEXT_TAIL]);
  541. rsclp->gp_seq[i] = seq;
  542. }
  543. return true;
  544. }
  545. /*
  546. * Merge the source rcu_segcblist structure into the destination
  547. * rcu_segcblist structure, then initialize the source. Any pending
  548. * callbacks from the source get to start over. It is best to
  549. * advance and accelerate both the destination and the source
  550. * before merging.
  551. */
  552. void rcu_segcblist_merge(struct rcu_segcblist *dst_rsclp,
  553. struct rcu_segcblist *src_rsclp)
  554. {
  555. struct rcu_cblist donecbs;
  556. struct rcu_cblist pendcbs;
  557. lockdep_assert_cpus_held();
  558. rcu_cblist_init(&donecbs);
  559. rcu_cblist_init(&pendcbs);
  560. rcu_segcblist_extract_done_cbs(src_rsclp, &donecbs);
  561. rcu_segcblist_extract_pend_cbs(src_rsclp, &pendcbs);
  562. /*
  563. * No need smp_mb() before setting length to 0, because CPU hotplug
  564. * lock excludes rcu_barrier.
  565. */
  566. rcu_segcblist_set_len(src_rsclp, 0);
  567. rcu_segcblist_insert_count(dst_rsclp, &donecbs);
  568. rcu_segcblist_insert_count(dst_rsclp, &pendcbs);
  569. rcu_segcblist_insert_done_cbs(dst_rsclp, &donecbs);
  570. rcu_segcblist_insert_pend_cbs(dst_rsclp, &pendcbs);
  571. rcu_segcblist_init(src_rsclp);
  572. }