tree.h 26 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645
  1. /*
  2. * Read-Copy Update mechanism for mutual exclusion (tree-based version)
  3. * Internal non-public definitions.
  4. *
  5. * This program is free software; you can redistribute it and/or modify
  6. * it under the terms of the GNU General Public License as published by
  7. * the Free Software Foundation; either version 2 of the License, or
  8. * (at your option) any later version.
  9. *
  10. * This program is distributed in the hope that it will be useful,
  11. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. * GNU General Public License for more details.
  14. *
  15. * You should have received a copy of the GNU General Public License
  16. * along with this program; if not, you can access it online at
  17. * http://www.gnu.org/licenses/gpl-2.0.html.
  18. *
  19. * Copyright IBM Corporation, 2008
  20. *
  21. * Author: Ingo Molnar <mingo@elte.hu>
  22. * Paul E. McKenney <paulmck@linux.vnet.ibm.com>
  23. */
  24. #include <linux/cache.h>
  25. #include <linux/spinlock.h>
  26. #include <linux/threads.h>
  27. #include <linux/cpumask.h>
  28. #include <linux/seqlock.h>
  29. #include <linux/irq_work.h>
  30. /*
  31. * Define shape of hierarchy based on NR_CPUS, CONFIG_RCU_FANOUT, and
  32. * CONFIG_RCU_FANOUT_LEAF.
  33. * In theory, it should be possible to add more levels straightforwardly.
  34. * In practice, this did work well going from three levels to four.
  35. * Of course, your mileage may vary.
  36. */
  37. #define MAX_RCU_LVLS 4
  38. #define RCU_FANOUT_1 (CONFIG_RCU_FANOUT_LEAF)
  39. #define RCU_FANOUT_2 (RCU_FANOUT_1 * CONFIG_RCU_FANOUT)
  40. #define RCU_FANOUT_3 (RCU_FANOUT_2 * CONFIG_RCU_FANOUT)
  41. #define RCU_FANOUT_4 (RCU_FANOUT_3 * CONFIG_RCU_FANOUT)
  42. #if NR_CPUS <= RCU_FANOUT_1
  43. # define RCU_NUM_LVLS 1
  44. # define NUM_RCU_LVL_0 1
  45. # define NUM_RCU_LVL_1 (NR_CPUS)
  46. # define NUM_RCU_LVL_2 0
  47. # define NUM_RCU_LVL_3 0
  48. # define NUM_RCU_LVL_4 0
  49. #elif NR_CPUS <= RCU_FANOUT_2
  50. # define RCU_NUM_LVLS 2
  51. # define NUM_RCU_LVL_0 1
  52. # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
  53. # define NUM_RCU_LVL_2 (NR_CPUS)
  54. # define NUM_RCU_LVL_3 0
  55. # define NUM_RCU_LVL_4 0
  56. #elif NR_CPUS <= RCU_FANOUT_3
  57. # define RCU_NUM_LVLS 3
  58. # define NUM_RCU_LVL_0 1
  59. # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
  60. # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
  61. # define NUM_RCU_LVL_3 (NR_CPUS)
  62. # define NUM_RCU_LVL_4 0
  63. #elif NR_CPUS <= RCU_FANOUT_4
  64. # define RCU_NUM_LVLS 4
  65. # define NUM_RCU_LVL_0 1
  66. # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
  67. # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
  68. # define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
  69. # define NUM_RCU_LVL_4 (NR_CPUS)
  70. #else
  71. # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
  72. #endif /* #if (NR_CPUS) <= RCU_FANOUT_1 */
  73. #define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3 + NUM_RCU_LVL_4)
  74. #define NUM_RCU_NODES (RCU_SUM - NR_CPUS)
  75. extern int rcu_num_lvls;
  76. extern int rcu_num_nodes;
  77. /*
  78. * Dynticks per-CPU state.
  79. */
  80. struct rcu_dynticks {
  81. long long dynticks_nesting; /* Track irq/process nesting level. */
  82. /* Process level is worth LLONG_MAX/2. */
  83. int dynticks_nmi_nesting; /* Track NMI nesting level. */
  84. atomic_t dynticks; /* Even value for idle, else odd. */
  85. #ifdef CONFIG_NO_HZ_FULL_SYSIDLE
  86. long long dynticks_idle_nesting;
  87. /* irq/process nesting level from idle. */
  88. atomic_t dynticks_idle; /* Even value for idle, else odd. */
  89. /* "Idle" excludes userspace execution. */
  90. unsigned long dynticks_idle_jiffies;
  91. /* End of last non-NMI non-idle period. */
  92. #endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
  93. #ifdef CONFIG_RCU_FAST_NO_HZ
  94. bool all_lazy; /* Are all CPU's CBs lazy? */
  95. unsigned long nonlazy_posted;
  96. /* # times non-lazy CBs posted to CPU. */
  97. unsigned long nonlazy_posted_snap;
  98. /* idle-period nonlazy_posted snapshot. */
  99. unsigned long last_accelerate;
  100. /* Last jiffy CBs were accelerated. */
  101. unsigned long last_advance_all;
  102. /* Last jiffy CBs were all advanced. */
  103. int tick_nohz_enabled_snap; /* Previously seen value from sysfs. */
  104. #endif /* #ifdef CONFIG_RCU_FAST_NO_HZ */
  105. };
  106. /* RCU's kthread states for tracing. */
  107. #define RCU_KTHREAD_STOPPED 0
  108. #define RCU_KTHREAD_RUNNING 1
  109. #define RCU_KTHREAD_WAITING 2
  110. #define RCU_KTHREAD_OFFCPU 3
  111. #define RCU_KTHREAD_YIELDING 4
  112. #define RCU_KTHREAD_MAX 4
  113. /*
  114. * Definition for node within the RCU grace-period-detection hierarchy.
  115. */
  116. struct rcu_node {
  117. raw_spinlock_t lock; /* Root rcu_node's lock protects some */
  118. /* rcu_state fields as well as following. */
  119. unsigned long gpnum; /* Current grace period for this node. */
  120. /* This will either be equal to or one */
  121. /* behind the root rcu_node's gpnum. */
  122. unsigned long completed; /* Last GP completed for this node. */
  123. /* This will either be equal to or one */
  124. /* behind the root rcu_node's gpnum. */
  125. unsigned long qsmask; /* CPUs or groups that need to switch in */
  126. /* order for current grace period to proceed.*/
  127. /* In leaf rcu_node, each bit corresponds to */
  128. /* an rcu_data structure, otherwise, each */
  129. /* bit corresponds to a child rcu_node */
  130. /* structure. */
  131. unsigned long expmask; /* Groups that have ->blkd_tasks */
  132. /* elements that need to drain to allow the */
  133. /* current expedited grace period to */
  134. /* complete (only for TREE_PREEMPT_RCU). */
  135. unsigned long qsmaskinit;
  136. /* Per-GP initial value for qsmask & expmask. */
  137. unsigned long grpmask; /* Mask to apply to parent qsmask. */
  138. /* Only one bit will be set in this mask. */
  139. int grplo; /* lowest-numbered CPU or group here. */
  140. int grphi; /* highest-numbered CPU or group here. */
  141. u8 grpnum; /* CPU/group number for next level up. */
  142. u8 level; /* root is at level 0. */
  143. struct rcu_node *parent;
  144. struct list_head blkd_tasks;
  145. /* Tasks blocked in RCU read-side critical */
  146. /* section. Tasks are placed at the head */
  147. /* of this list and age towards the tail. */
  148. struct list_head *gp_tasks;
  149. /* Pointer to the first task blocking the */
  150. /* current grace period, or NULL if there */
  151. /* is no such task. */
  152. struct list_head *exp_tasks;
  153. /* Pointer to the first task blocking the */
  154. /* current expedited grace period, or NULL */
  155. /* if there is no such task. If there */
  156. /* is no current expedited grace period, */
  157. /* then there can cannot be any such task. */
  158. #ifdef CONFIG_RCU_BOOST
  159. struct list_head *boost_tasks;
  160. /* Pointer to first task that needs to be */
  161. /* priority boosted, or NULL if no priority */
  162. /* boosting is needed for this rcu_node */
  163. /* structure. If there are no tasks */
  164. /* queued on this rcu_node structure that */
  165. /* are blocking the current grace period, */
  166. /* there can be no such task. */
  167. struct completion boost_completion;
  168. /* Used to ensure that the rt_mutex used */
  169. /* to carry out the boosting is fully */
  170. /* released with no future boostee accesses */
  171. /* before that rt_mutex is re-initialized. */
  172. struct rt_mutex boost_mtx;
  173. /* Used only for the priority-boosting */
  174. /* side effect, not as a lock. */
  175. unsigned long boost_time;
  176. /* When to start boosting (jiffies). */
  177. struct task_struct *boost_kthread_task;
  178. /* kthread that takes care of priority */
  179. /* boosting for this rcu_node structure. */
  180. unsigned int boost_kthread_status;
  181. /* State of boost_kthread_task for tracing. */
  182. unsigned long n_tasks_boosted;
  183. /* Total number of tasks boosted. */
  184. unsigned long n_exp_boosts;
  185. /* Number of tasks boosted for expedited GP. */
  186. unsigned long n_normal_boosts;
  187. /* Number of tasks boosted for normal GP. */
  188. unsigned long n_balk_blkd_tasks;
  189. /* Refused to boost: no blocked tasks. */
  190. unsigned long n_balk_exp_gp_tasks;
  191. /* Refused to boost: nothing blocking GP. */
  192. unsigned long n_balk_boost_tasks;
  193. /* Refused to boost: already boosting. */
  194. unsigned long n_balk_notblocked;
  195. /* Refused to boost: RCU RS CS still running. */
  196. unsigned long n_balk_notyet;
  197. /* Refused to boost: not yet time. */
  198. unsigned long n_balk_nos;
  199. /* Refused to boost: not sure why, though. */
  200. /* This can happen due to race conditions. */
  201. #endif /* #ifdef CONFIG_RCU_BOOST */
  202. #ifdef CONFIG_RCU_NOCB_CPU
  203. wait_queue_head_t nocb_gp_wq[2];
  204. /* Place for rcu_nocb_kthread() to wait GP. */
  205. #endif /* #ifdef CONFIG_RCU_NOCB_CPU */
  206. int need_future_gp[2];
  207. /* Counts of upcoming no-CB GP requests. */
  208. raw_spinlock_t fqslock ____cacheline_internodealigned_in_smp;
  209. } ____cacheline_internodealigned_in_smp;
  210. /*
  211. * Do a full breadth-first scan of the rcu_node structures for the
  212. * specified rcu_state structure.
  213. */
  214. #define rcu_for_each_node_breadth_first(rsp, rnp) \
  215. for ((rnp) = &(rsp)->node[0]; \
  216. (rnp) < &(rsp)->node[rcu_num_nodes]; (rnp)++)
  217. /*
  218. * Do a breadth-first scan of the non-leaf rcu_node structures for the
  219. * specified rcu_state structure. Note that if there is a singleton
  220. * rcu_node tree with but one rcu_node structure, this loop is a no-op.
  221. */
  222. #define rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) \
  223. for ((rnp) = &(rsp)->node[0]; \
  224. (rnp) < (rsp)->level[rcu_num_lvls - 1]; (rnp)++)
  225. /*
  226. * Scan the leaves of the rcu_node hierarchy for the specified rcu_state
  227. * structure. Note that if there is a singleton rcu_node tree with but
  228. * one rcu_node structure, this loop -will- visit the rcu_node structure.
  229. * It is still a leaf node, even if it is also the root node.
  230. */
  231. #define rcu_for_each_leaf_node(rsp, rnp) \
  232. for ((rnp) = (rsp)->level[rcu_num_lvls - 1]; \
  233. (rnp) < &(rsp)->node[rcu_num_nodes]; (rnp)++)
  234. /* Index values for nxttail array in struct rcu_data. */
  235. #define RCU_DONE_TAIL 0 /* Also RCU_WAIT head. */
  236. #define RCU_WAIT_TAIL 1 /* Also RCU_NEXT_READY head. */
  237. #define RCU_NEXT_READY_TAIL 2 /* Also RCU_NEXT head. */
  238. #define RCU_NEXT_TAIL 3
  239. #define RCU_NEXT_SIZE 4
  240. /* Per-CPU data for read-copy update. */
  241. struct rcu_data {
  242. /* 1) quiescent-state and grace-period handling : */
  243. unsigned long completed; /* Track rsp->completed gp number */
  244. /* in order to detect GP end. */
  245. unsigned long gpnum; /* Highest gp number that this CPU */
  246. /* is aware of having started. */
  247. bool passed_quiesce; /* User-mode/idle loop etc. */
  248. bool qs_pending; /* Core waits for quiesc state. */
  249. bool beenonline; /* CPU online at least once. */
  250. struct rcu_node *mynode; /* This CPU's leaf of hierarchy */
  251. unsigned long grpmask; /* Mask to apply to leaf qsmask. */
  252. #ifdef CONFIG_RCU_CPU_STALL_INFO
  253. unsigned long ticks_this_gp; /* The number of scheduling-clock */
  254. /* ticks this CPU has handled */
  255. /* during and after the last grace */
  256. /* period it is aware of. */
  257. #endif /* #ifdef CONFIG_RCU_CPU_STALL_INFO */
  258. /* 2) batch handling */
  259. /*
  260. * If nxtlist is not NULL, it is partitioned as follows.
  261. * Any of the partitions might be empty, in which case the
  262. * pointer to that partition will be equal to the pointer for
  263. * the following partition. When the list is empty, all of
  264. * the nxttail elements point to the ->nxtlist pointer itself,
  265. * which in that case is NULL.
  266. *
  267. * [nxtlist, *nxttail[RCU_DONE_TAIL]):
  268. * Entries that batch # <= ->completed
  269. * The grace period for these entries has completed, and
  270. * the other grace-period-completed entries may be moved
  271. * here temporarily in rcu_process_callbacks().
  272. * [*nxttail[RCU_DONE_TAIL], *nxttail[RCU_WAIT_TAIL]):
  273. * Entries that batch # <= ->completed - 1: waiting for current GP
  274. * [*nxttail[RCU_WAIT_TAIL], *nxttail[RCU_NEXT_READY_TAIL]):
  275. * Entries known to have arrived before current GP ended
  276. * [*nxttail[RCU_NEXT_READY_TAIL], *nxttail[RCU_NEXT_TAIL]):
  277. * Entries that might have arrived after current GP ended
  278. * Note that the value of *nxttail[RCU_NEXT_TAIL] will
  279. * always be NULL, as this is the end of the list.
  280. */
  281. struct rcu_head *nxtlist;
  282. struct rcu_head **nxttail[RCU_NEXT_SIZE];
  283. unsigned long nxtcompleted[RCU_NEXT_SIZE];
  284. /* grace periods for sublists. */
  285. long qlen_lazy; /* # of lazy queued callbacks */
  286. long qlen; /* # of queued callbacks, incl lazy */
  287. long qlen_last_fqs_check;
  288. /* qlen at last check for QS forcing */
  289. unsigned long n_cbs_invoked; /* count of RCU cbs invoked. */
  290. unsigned long n_nocbs_invoked; /* count of no-CBs RCU cbs invoked. */
  291. unsigned long n_cbs_orphaned; /* RCU cbs orphaned by dying CPU */
  292. unsigned long n_cbs_adopted; /* RCU cbs adopted from dying CPU */
  293. unsigned long n_force_qs_snap;
  294. /* did other CPU force QS recently? */
  295. long blimit; /* Upper limit on a processed batch */
  296. /* 3) dynticks interface. */
  297. struct rcu_dynticks *dynticks; /* Shared per-CPU dynticks state. */
  298. int dynticks_snap; /* Per-GP tracking for dynticks. */
  299. /* 4) reasons this CPU needed to be kicked by force_quiescent_state */
  300. unsigned long dynticks_fqs; /* Kicked due to dynticks idle. */
  301. unsigned long offline_fqs; /* Kicked due to being offline. */
  302. unsigned long cond_resched_completed;
  303. /* Grace period that needs help */
  304. /* from cond_resched(). */
  305. /* 5) __rcu_pending() statistics. */
  306. unsigned long n_rcu_pending; /* rcu_pending() calls since boot. */
  307. unsigned long n_rp_qs_pending;
  308. unsigned long n_rp_report_qs;
  309. unsigned long n_rp_cb_ready;
  310. unsigned long n_rp_cpu_needs_gp;
  311. unsigned long n_rp_gp_completed;
  312. unsigned long n_rp_gp_started;
  313. unsigned long n_rp_nocb_defer_wakeup;
  314. unsigned long n_rp_need_nothing;
  315. /* 6) _rcu_barrier() and OOM callbacks. */
  316. struct rcu_head barrier_head;
  317. #ifdef CONFIG_RCU_FAST_NO_HZ
  318. struct rcu_head oom_head;
  319. #endif /* #ifdef CONFIG_RCU_FAST_NO_HZ */
  320. /* 7) Callback offloading. */
  321. #ifdef CONFIG_RCU_NOCB_CPU
  322. struct rcu_head *nocb_head; /* CBs waiting for kthread. */
  323. struct rcu_head **nocb_tail;
  324. atomic_long_t nocb_q_count; /* # CBs waiting for kthread */
  325. atomic_long_t nocb_q_count_lazy; /* (approximate). */
  326. struct rcu_head *nocb_follower_head; /* CBs ready to invoke. */
  327. struct rcu_head **nocb_follower_tail;
  328. atomic_long_t nocb_follower_count; /* # CBs ready to invoke. */
  329. atomic_long_t nocb_follower_count_lazy; /* (approximate). */
  330. int nocb_p_count; /* # CBs being invoked by kthread */
  331. int nocb_p_count_lazy; /* (approximate). */
  332. wait_queue_head_t nocb_wq; /* For nocb kthreads to sleep on. */
  333. struct task_struct *nocb_kthread;
  334. int nocb_defer_wakeup; /* Defer wakeup of nocb_kthread. */
  335. /* The following fields are used by the leader, hence own cacheline. */
  336. struct rcu_head *nocb_gp_head ____cacheline_internodealigned_in_smp;
  337. /* CBs waiting for GP. */
  338. struct rcu_head **nocb_gp_tail;
  339. long nocb_gp_count;
  340. long nocb_gp_count_lazy;
  341. bool nocb_leader_sleep; /* Is the nocb leader thread asleep? */
  342. struct rcu_data *nocb_next_follower;
  343. /* Next follower in wakeup chain. */
  344. /* The following fields are used by the follower, hence new cachline. */
  345. struct rcu_data *nocb_leader ____cacheline_internodealigned_in_smp;
  346. /* Leader CPU takes GP-end wakeups. */
  347. #endif /* #ifdef CONFIG_RCU_NOCB_CPU */
  348. /* 8) RCU CPU stall data. */
  349. #ifdef CONFIG_RCU_CPU_STALL_INFO
  350. unsigned int softirq_snap; /* Snapshot of softirq activity. */
  351. #endif /* #ifdef CONFIG_RCU_CPU_STALL_INFO */
  352. int cpu;
  353. struct rcu_state *rsp;
  354. };
  355. /* Values for fqs_state field in struct rcu_state. */
  356. #define RCU_GP_IDLE 0 /* No grace period in progress. */
  357. #define RCU_GP_INIT 1 /* Grace period being initialized. */
  358. #define RCU_SAVE_DYNTICK 2 /* Need to scan dyntick state. */
  359. #define RCU_FORCE_QS 3 /* Need to force quiescent state. */
  360. #define RCU_SIGNAL_INIT RCU_SAVE_DYNTICK
  361. /* Values for nocb_defer_wakeup field in struct rcu_data. */
  362. #define RCU_NOGP_WAKE_NOT 0
  363. #define RCU_NOGP_WAKE 1
  364. #define RCU_NOGP_WAKE_FORCE 2
  365. #define RCU_JIFFIES_TILL_FORCE_QS (1 + (HZ > 250) + (HZ > 500))
  366. /* For jiffies_till_first_fqs and */
  367. /* and jiffies_till_next_fqs. */
  368. #define RCU_JIFFIES_FQS_DIV 256 /* Very large systems need more */
  369. /* delay between bouts of */
  370. /* quiescent-state forcing. */
  371. #define RCU_STALL_RAT_DELAY 2 /* Allow other CPUs time to take */
  372. /* at least one scheduling clock */
  373. /* irq before ratting on them. */
  374. #define rcu_wait(cond) \
  375. do { \
  376. for (;;) { \
  377. set_current_state(TASK_INTERRUPTIBLE); \
  378. if (cond) \
  379. break; \
  380. schedule(); \
  381. } \
  382. __set_current_state(TASK_RUNNING); \
  383. } while (0)
  384. /*
  385. * RCU global state, including node hierarchy. This hierarchy is
  386. * represented in "heap" form in a dense array. The root (first level)
  387. * of the hierarchy is in ->node[0] (referenced by ->level[0]), the second
  388. * level in ->node[1] through ->node[m] (->node[1] referenced by ->level[1]),
  389. * and the third level in ->node[m+1] and following (->node[m+1] referenced
  390. * by ->level[2]). The number of levels is determined by the number of
  391. * CPUs and by CONFIG_RCU_FANOUT. Small systems will have a "hierarchy"
  392. * consisting of a single rcu_node.
  393. */
  394. struct rcu_state {
  395. struct rcu_node node[NUM_RCU_NODES]; /* Hierarchy. */
  396. struct rcu_node *level[RCU_NUM_LVLS]; /* Hierarchy levels. */
  397. u32 levelcnt[MAX_RCU_LVLS + 1]; /* # nodes in each level. */
  398. u8 levelspread[RCU_NUM_LVLS]; /* kids/node in each level. */
  399. u8 flavor_mask; /* bit in flavor mask. */
  400. struct rcu_data __percpu *rda; /* pointer of percu rcu_data. */
  401. void (*call)(struct rcu_head *head, /* call_rcu() flavor. */
  402. void (*func)(struct rcu_head *head));
  403. /* The following fields are guarded by the root rcu_node's lock. */
  404. u8 fqs_state ____cacheline_internodealigned_in_smp;
  405. /* Force QS state. */
  406. u8 boost; /* Subject to priority boost. */
  407. unsigned long gpnum; /* Current gp number. */
  408. unsigned long completed; /* # of last completed gp. */
  409. struct task_struct *gp_kthread; /* Task for grace periods. */
  410. wait_queue_head_t gp_wq; /* Where GP task waits. */
  411. short gp_flags; /* Commands for GP task. */
  412. short gp_state; /* GP kthread sleep state. */
  413. /* End of fields guarded by root rcu_node's lock. */
  414. raw_spinlock_t orphan_lock ____cacheline_internodealigned_in_smp;
  415. /* Protect following fields. */
  416. struct rcu_head *orphan_nxtlist; /* Orphaned callbacks that */
  417. /* need a grace period. */
  418. struct rcu_head **orphan_nxttail; /* Tail of above. */
  419. struct rcu_head *orphan_donelist; /* Orphaned callbacks that */
  420. /* are ready to invoke. */
  421. struct rcu_head **orphan_donetail; /* Tail of above. */
  422. long qlen_lazy; /* Number of lazy callbacks. */
  423. long qlen; /* Total number of callbacks. */
  424. /* End of fields guarded by orphan_lock. */
  425. struct mutex onoff_mutex; /* Coordinate hotplug & GPs. */
  426. struct mutex barrier_mutex; /* Guards barrier fields. */
  427. atomic_t barrier_cpu_count; /* # CPUs waiting on. */
  428. struct completion barrier_completion; /* Wake at barrier end. */
  429. unsigned long n_barrier_done; /* ++ at start and end of */
  430. /* _rcu_barrier(). */
  431. /* End of fields guarded by barrier_mutex. */
  432. atomic_long_t expedited_start; /* Starting ticket. */
  433. atomic_long_t expedited_done; /* Done ticket. */
  434. atomic_long_t expedited_wrap; /* # near-wrap incidents. */
  435. atomic_long_t expedited_tryfail; /* # acquisition failures. */
  436. atomic_long_t expedited_workdone1; /* # done by others #1. */
  437. atomic_long_t expedited_workdone2; /* # done by others #2. */
  438. atomic_long_t expedited_normal; /* # fallbacks to normal. */
  439. atomic_long_t expedited_stoppedcpus; /* # successful stop_cpus. */
  440. atomic_long_t expedited_done_tries; /* # tries to update _done. */
  441. atomic_long_t expedited_done_lost; /* # times beaten to _done. */
  442. atomic_long_t expedited_done_exit; /* # times exited _done loop. */
  443. unsigned long jiffies_force_qs; /* Time at which to invoke */
  444. /* force_quiescent_state(). */
  445. unsigned long n_force_qs; /* Number of calls to */
  446. /* force_quiescent_state(). */
  447. unsigned long n_force_qs_lh; /* ~Number of calls leaving */
  448. /* due to lock unavailable. */
  449. unsigned long n_force_qs_ngp; /* Number of calls leaving */
  450. /* due to no GP active. */
  451. unsigned long gp_start; /* Time at which GP started, */
  452. /* but in jiffies. */
  453. unsigned long jiffies_stall; /* Time at which to check */
  454. /* for CPU stalls. */
  455. unsigned long jiffies_resched; /* Time at which to resched */
  456. /* a reluctant CPU. */
  457. unsigned long gp_max; /* Maximum GP duration in */
  458. /* jiffies. */
  459. const char *name; /* Name of structure. */
  460. char abbr; /* Abbreviated name. */
  461. struct list_head flavors; /* List of RCU flavors. */
  462. };
  463. /* Values for rcu_state structure's gp_flags field. */
  464. #define RCU_GP_FLAG_INIT 0x1 /* Need grace-period initialization. */
  465. #define RCU_GP_FLAG_FQS 0x2 /* Need grace-period quiescent-state forcing. */
  466. /* Values for rcu_state structure's gp_flags field. */
  467. #define RCU_GP_WAIT_INIT 0 /* Initial state. */
  468. #define RCU_GP_WAIT_GPS 1 /* Wait for grace-period start. */
  469. #define RCU_GP_WAIT_FQS 2 /* Wait for force-quiescent-state time. */
  470. extern struct list_head rcu_struct_flavors;
  471. /* Sequence through rcu_state structures for each RCU flavor. */
  472. #define for_each_rcu_flavor(rsp) \
  473. list_for_each_entry((rsp), &rcu_struct_flavors, flavors)
  474. /* Return values for rcu_preempt_offline_tasks(). */
  475. #define RCU_OFL_TASKS_NORM_GP 0x1 /* Tasks blocking normal */
  476. /* GP were moved to root. */
  477. #define RCU_OFL_TASKS_EXP_GP 0x2 /* Tasks blocking expedited */
  478. /* GP were moved to root. */
  479. /*
  480. * RCU implementation internal declarations:
  481. */
  482. extern struct rcu_state rcu_sched_state;
  483. DECLARE_PER_CPU(struct rcu_data, rcu_sched_data);
  484. extern struct rcu_state rcu_bh_state;
  485. DECLARE_PER_CPU(struct rcu_data, rcu_bh_data);
  486. #ifdef CONFIG_TREE_PREEMPT_RCU
  487. extern struct rcu_state rcu_preempt_state;
  488. DECLARE_PER_CPU(struct rcu_data, rcu_preempt_data);
  489. #endif /* #ifdef CONFIG_TREE_PREEMPT_RCU */
  490. #ifdef CONFIG_RCU_BOOST
  491. DECLARE_PER_CPU(unsigned int, rcu_cpu_kthread_status);
  492. DECLARE_PER_CPU(int, rcu_cpu_kthread_cpu);
  493. DECLARE_PER_CPU(unsigned int, rcu_cpu_kthread_loops);
  494. DECLARE_PER_CPU(char, rcu_cpu_has_work);
  495. #endif /* #ifdef CONFIG_RCU_BOOST */
  496. #ifndef RCU_TREE_NONCORE
  497. /* Forward declarations for rcutree_plugin.h */
  498. static void rcu_bootup_announce(void);
  499. long rcu_batches_completed(void);
  500. static void rcu_preempt_note_context_switch(int cpu);
  501. static int rcu_preempt_blocked_readers_cgp(struct rcu_node *rnp);
  502. #ifdef CONFIG_HOTPLUG_CPU
  503. static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp,
  504. unsigned long flags);
  505. #endif /* #ifdef CONFIG_HOTPLUG_CPU */
  506. static void rcu_print_detail_task_stall(struct rcu_state *rsp);
  507. static int rcu_print_task_stall(struct rcu_node *rnp);
  508. static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp);
  509. #ifdef CONFIG_HOTPLUG_CPU
  510. static int rcu_preempt_offline_tasks(struct rcu_state *rsp,
  511. struct rcu_node *rnp,
  512. struct rcu_data *rdp);
  513. #endif /* #ifdef CONFIG_HOTPLUG_CPU */
  514. static void rcu_preempt_check_callbacks(int cpu);
  515. void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu));
  516. #if defined(CONFIG_HOTPLUG_CPU) || defined(CONFIG_TREE_PREEMPT_RCU)
  517. static void rcu_report_exp_rnp(struct rcu_state *rsp, struct rcu_node *rnp,
  518. bool wake);
  519. #endif /* #if defined(CONFIG_HOTPLUG_CPU) || defined(CONFIG_TREE_PREEMPT_RCU) */
  520. static void __init __rcu_init_preempt(void);
  521. static void rcu_initiate_boost(struct rcu_node *rnp, unsigned long flags);
  522. static void rcu_preempt_boost_start_gp(struct rcu_node *rnp);
  523. static void invoke_rcu_callbacks_kthread(void);
  524. static bool rcu_is_callbacks_kthread(void);
  525. #ifdef CONFIG_RCU_BOOST
  526. static void rcu_preempt_do_callbacks(void);
  527. static int rcu_spawn_one_boost_kthread(struct rcu_state *rsp,
  528. struct rcu_node *rnp);
  529. #endif /* #ifdef CONFIG_RCU_BOOST */
  530. static void __init rcu_spawn_boost_kthreads(void);
  531. static void rcu_prepare_kthreads(int cpu);
  532. static void rcu_cleanup_after_idle(int cpu);
  533. static void rcu_prepare_for_idle(int cpu);
  534. static void rcu_idle_count_callbacks_posted(void);
  535. static void print_cpu_stall_info_begin(void);
  536. static void print_cpu_stall_info(struct rcu_state *rsp, int cpu);
  537. static void print_cpu_stall_info_end(void);
  538. static void zero_cpu_stall_ticks(struct rcu_data *rdp);
  539. static void increment_cpu_stall_ticks(void);
  540. static bool rcu_nocb_cpu_needs_barrier(struct rcu_state *rsp, int cpu);
  541. static void rcu_nocb_gp_set(struct rcu_node *rnp, int nrq);
  542. static void rcu_nocb_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp);
  543. static void rcu_init_one_nocb(struct rcu_node *rnp);
  544. static bool __call_rcu_nocb(struct rcu_data *rdp, struct rcu_head *rhp,
  545. bool lazy, unsigned long flags);
  546. static bool rcu_nocb_adopt_orphan_cbs(struct rcu_state *rsp,
  547. struct rcu_data *rdp,
  548. unsigned long flags);
  549. static int rcu_nocb_need_deferred_wakeup(struct rcu_data *rdp);
  550. static void do_nocb_deferred_wakeup(struct rcu_data *rdp);
  551. static void rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp);
  552. static void rcu_spawn_all_nocb_kthreads(int cpu);
  553. static void __init rcu_spawn_nocb_kthreads(void);
  554. #ifdef CONFIG_RCU_NOCB_CPU
  555. static void __init rcu_organize_nocb_kthreads(struct rcu_state *rsp);
  556. #endif /* #ifdef CONFIG_RCU_NOCB_CPU */
  557. static void __maybe_unused rcu_kick_nohz_cpu(int cpu);
  558. static bool init_nocb_callback_list(struct rcu_data *rdp);
  559. static void rcu_sysidle_enter(struct rcu_dynticks *rdtp, int irq);
  560. static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq);
  561. static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
  562. unsigned long *maxj);
  563. static bool is_sysidle_rcu_state(struct rcu_state *rsp);
  564. static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
  565. unsigned long maxj);
  566. static void rcu_bind_gp_kthread(void);
  567. static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp);
  568. static bool rcu_nohz_full_cpu(struct rcu_state *rsp);
  569. static void rcu_dynticks_task_enter(void);
  570. static void rcu_dynticks_task_exit(void);
  571. #endif /* #ifndef RCU_TREE_NONCORE */
  572. #ifdef CONFIG_RCU_TRACE
  573. #ifdef CONFIG_RCU_NOCB_CPU
  574. /* Sum up queue lengths for tracing. */
  575. static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
  576. {
  577. *ql = atomic_long_read(&rdp->nocb_q_count) +
  578. rdp->nocb_p_count +
  579. atomic_long_read(&rdp->nocb_follower_count) +
  580. rdp->nocb_p_count + rdp->nocb_gp_count;
  581. *qll = atomic_long_read(&rdp->nocb_q_count_lazy) +
  582. rdp->nocb_p_count_lazy +
  583. atomic_long_read(&rdp->nocb_follower_count_lazy) +
  584. rdp->nocb_p_count_lazy + rdp->nocb_gp_count_lazy;
  585. }
  586. #else /* #ifdef CONFIG_RCU_NOCB_CPU */
  587. static inline void rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)
  588. {
  589. *ql = 0;
  590. *qll = 0;
  591. }
  592. #endif /* #else #ifdef CONFIG_RCU_NOCB_CPU */
  593. #endif /* #ifdef CONFIG_RCU_TRACE */