rcutree.c 64 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141
  1. /*
  2. * Read-Copy Update mechanism for mutual exclusion
  3. *
  4. * This program is free software; you can redistribute it and/or modify
  5. * it under the terms of the GNU General Public License as published by
  6. * the Free Software Foundation; either version 2 of the License, or
  7. * (at your option) any later version.
  8. *
  9. * This program is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write to the Free Software
  16. * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. *
  18. * Copyright IBM Corporation, 2008
  19. *
  20. * Authors: Dipankar Sarma <dipankar@in.ibm.com>
  21. * Manfred Spraul <manfred@colorfullife.com>
  22. * Paul E. McKenney <paulmck@linux.vnet.ibm.com> Hierarchical version
  23. *
  24. * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
  25. * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
  26. *
  27. * For detailed explanation of Read-Copy Update mechanism see -
  28. * Documentation/RCU
  29. */
  30. #include <linux/types.h>
  31. #include <linux/kernel.h>
  32. #include <linux/init.h>
  33. #include <linux/spinlock.h>
  34. #include <linux/smp.h>
  35. #include <linux/rcupdate.h>
  36. #include <linux/interrupt.h>
  37. #include <linux/sched.h>
  38. #include <linux/nmi.h>
  39. #include <linux/atomic.h>
  40. #include <linux/bitops.h>
  41. #include <linux/module.h>
  42. #include <linux/completion.h>
  43. #include <linux/moduleparam.h>
  44. #include <linux/percpu.h>
  45. #include <linux/notifier.h>
  46. #include <linux/cpu.h>
  47. #include <linux/mutex.h>
  48. #include <linux/time.h>
  49. #include <linux/kernel_stat.h>
  50. #include <linux/wait.h>
  51. #include <linux/kthread.h>
  52. #include <linux/prefetch.h>
  53. #include "rcutree.h"
  54. #include <trace/events/rcu.h>
  55. #include "rcu.h"
  56. /* Data structures. */
  57. static struct lock_class_key rcu_node_class[NUM_RCU_LVLS];
  58. #define RCU_STATE_INITIALIZER(structname) { \
  59. .level = { &structname##_state.node[0] }, \
  60. .levelcnt = { \
  61. NUM_RCU_LVL_0, /* root of hierarchy. */ \
  62. NUM_RCU_LVL_1, \
  63. NUM_RCU_LVL_2, \
  64. NUM_RCU_LVL_3, \
  65. NUM_RCU_LVL_4, /* == MAX_RCU_LVLS */ \
  66. }, \
  67. .signaled = RCU_GP_IDLE, \
  68. .gpnum = -300, \
  69. .completed = -300, \
  70. .onofflock = __RAW_SPIN_LOCK_UNLOCKED(&structname##_state.onofflock), \
  71. .fqslock = __RAW_SPIN_LOCK_UNLOCKED(&structname##_state.fqslock), \
  72. .n_force_qs = 0, \
  73. .n_force_qs_ngp = 0, \
  74. .name = #structname, \
  75. }
  76. struct rcu_state rcu_sched_state = RCU_STATE_INITIALIZER(rcu_sched);
  77. DEFINE_PER_CPU(struct rcu_data, rcu_sched_data);
  78. struct rcu_state rcu_bh_state = RCU_STATE_INITIALIZER(rcu_bh);
  79. DEFINE_PER_CPU(struct rcu_data, rcu_bh_data);
  80. static struct rcu_state *rcu_state;
  81. /*
  82. * The rcu_scheduler_active variable transitions from zero to one just
  83. * before the first task is spawned. So when this variable is zero, RCU
  84. * can assume that there is but one task, allowing RCU to (for example)
  85. * optimized synchronize_sched() to a simple barrier(). When this variable
  86. * is one, RCU must actually do all the hard work required to detect real
  87. * grace periods. This variable is also used to suppress boot-time false
  88. * positives from lockdep-RCU error checking.
  89. */
  90. int rcu_scheduler_active __read_mostly;
  91. EXPORT_SYMBOL_GPL(rcu_scheduler_active);
  92. /*
  93. * The rcu_scheduler_fully_active variable transitions from zero to one
  94. * during the early_initcall() processing, which is after the scheduler
  95. * is capable of creating new tasks. So RCU processing (for example,
  96. * creating tasks for RCU priority boosting) must be delayed until after
  97. * rcu_scheduler_fully_active transitions from zero to one. We also
  98. * currently delay invocation of any RCU callbacks until after this point.
  99. *
  100. * It might later prove better for people registering RCU callbacks during
  101. * early boot to take responsibility for these callbacks, but one step at
  102. * a time.
  103. */
  104. static int rcu_scheduler_fully_active __read_mostly;
  105. #ifdef CONFIG_RCU_BOOST
  106. /*
  107. * Control variables for per-CPU and per-rcu_node kthreads. These
  108. * handle all flavors of RCU.
  109. */
  110. static DEFINE_PER_CPU(struct task_struct *, rcu_cpu_kthread_task);
  111. DEFINE_PER_CPU(unsigned int, rcu_cpu_kthread_status);
  112. DEFINE_PER_CPU(int, rcu_cpu_kthread_cpu);
  113. DEFINE_PER_CPU(unsigned int, rcu_cpu_kthread_loops);
  114. DEFINE_PER_CPU(char, rcu_cpu_has_work);
  115. #endif /* #ifdef CONFIG_RCU_BOOST */
  116. static void rcu_node_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu);
  117. static void invoke_rcu_core(void);
  118. static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp);
  119. /*
  120. * Track the rcutorture test sequence number and the update version
  121. * number within a given test. The rcutorture_testseq is incremented
  122. * on every rcutorture module load and unload, so has an odd value
  123. * when a test is running. The rcutorture_vernum is set to zero
  124. * when rcutorture starts and is incremented on each rcutorture update.
  125. * These variables enable correlating rcutorture output with the
  126. * RCU tracing information.
  127. */
  128. unsigned long rcutorture_testseq;
  129. unsigned long rcutorture_vernum;
  130. /*
  131. * Return true if an RCU grace period is in progress. The ACCESS_ONCE()s
  132. * permit this function to be invoked without holding the root rcu_node
  133. * structure's ->lock, but of course results can be subject to change.
  134. */
  135. static int rcu_gp_in_progress(struct rcu_state *rsp)
  136. {
  137. return ACCESS_ONCE(rsp->completed) != ACCESS_ONCE(rsp->gpnum);
  138. }
  139. /*
  140. * Note a quiescent state. Because we do not need to know
  141. * how many quiescent states passed, just if there was at least
  142. * one since the start of the grace period, this just sets a flag.
  143. * The caller must have disabled preemption.
  144. */
  145. void rcu_sched_qs(int cpu)
  146. {
  147. struct rcu_data *rdp = &per_cpu(rcu_sched_data, cpu);
  148. rdp->passed_quiesce_gpnum = rdp->gpnum;
  149. barrier();
  150. if (rdp->passed_quiesce == 0)
  151. trace_rcu_grace_period("rcu_sched", rdp->gpnum, "cpuqs");
  152. rdp->passed_quiesce = 1;
  153. }
  154. void rcu_bh_qs(int cpu)
  155. {
  156. struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu);
  157. rdp->passed_quiesce_gpnum = rdp->gpnum;
  158. barrier();
  159. if (rdp->passed_quiesce == 0)
  160. trace_rcu_grace_period("rcu_bh", rdp->gpnum, "cpuqs");
  161. rdp->passed_quiesce = 1;
  162. }
  163. /*
  164. * Note a context switch. This is a quiescent state for RCU-sched,
  165. * and requires special handling for preemptible RCU.
  166. * The caller must have disabled preemption.
  167. */
  168. void rcu_note_context_switch(int cpu)
  169. {
  170. trace_rcu_utilization("Start context switch");
  171. rcu_sched_qs(cpu);
  172. rcu_preempt_note_context_switch(cpu);
  173. trace_rcu_utilization("End context switch");
  174. }
  175. EXPORT_SYMBOL_GPL(rcu_note_context_switch);
  176. #ifdef CONFIG_NO_HZ
  177. DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
  178. .dynticks_nesting = 1,
  179. .dynticks = ATOMIC_INIT(1),
  180. };
  181. #endif /* #ifdef CONFIG_NO_HZ */
  182. static int blimit = 10; /* Maximum callbacks per rcu_do_batch. */
  183. static int qhimark = 10000; /* If this many pending, ignore blimit. */
  184. static int qlowmark = 100; /* Once only this many pending, use blimit. */
  185. module_param(blimit, int, 0);
  186. module_param(qhimark, int, 0);
  187. module_param(qlowmark, int, 0);
  188. int rcu_cpu_stall_suppress __read_mostly;
  189. module_param(rcu_cpu_stall_suppress, int, 0644);
  190. static void force_quiescent_state(struct rcu_state *rsp, int relaxed);
  191. static int rcu_pending(int cpu);
  192. /*
  193. * Return the number of RCU-sched batches processed thus far for debug & stats.
  194. */
  195. long rcu_batches_completed_sched(void)
  196. {
  197. return rcu_sched_state.completed;
  198. }
  199. EXPORT_SYMBOL_GPL(rcu_batches_completed_sched);
  200. /*
  201. * Return the number of RCU BH batches processed thus far for debug & stats.
  202. */
  203. long rcu_batches_completed_bh(void)
  204. {
  205. return rcu_bh_state.completed;
  206. }
  207. EXPORT_SYMBOL_GPL(rcu_batches_completed_bh);
  208. /*
  209. * Force a quiescent state for RCU BH.
  210. */
  211. void rcu_bh_force_quiescent_state(void)
  212. {
  213. force_quiescent_state(&rcu_bh_state, 0);
  214. }
  215. EXPORT_SYMBOL_GPL(rcu_bh_force_quiescent_state);
  216. /*
  217. * Record the number of times rcutorture tests have been initiated and
  218. * terminated. This information allows the debugfs tracing stats to be
  219. * correlated to the rcutorture messages, even when the rcutorture module
  220. * is being repeatedly loaded and unloaded. In other words, we cannot
  221. * store this state in rcutorture itself.
  222. */
  223. void rcutorture_record_test_transition(void)
  224. {
  225. rcutorture_testseq++;
  226. rcutorture_vernum = 0;
  227. }
  228. EXPORT_SYMBOL_GPL(rcutorture_record_test_transition);
  229. /*
  230. * Record the number of writer passes through the current rcutorture test.
  231. * This is also used to correlate debugfs tracing stats with the rcutorture
  232. * messages.
  233. */
  234. void rcutorture_record_progress(unsigned long vernum)
  235. {
  236. rcutorture_vernum++;
  237. }
  238. EXPORT_SYMBOL_GPL(rcutorture_record_progress);
  239. /*
  240. * Force a quiescent state for RCU-sched.
  241. */
  242. void rcu_sched_force_quiescent_state(void)
  243. {
  244. force_quiescent_state(&rcu_sched_state, 0);
  245. }
  246. EXPORT_SYMBOL_GPL(rcu_sched_force_quiescent_state);
  247. /*
  248. * Does the CPU have callbacks ready to be invoked?
  249. */
  250. static int
  251. cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp)
  252. {
  253. return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL];
  254. }
  255. /*
  256. * Does the current CPU require a yet-as-unscheduled grace period?
  257. */
  258. static int
  259. cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
  260. {
  261. return *rdp->nxttail[RCU_DONE_TAIL] && !rcu_gp_in_progress(rsp);
  262. }
  263. /*
  264. * Return the root node of the specified rcu_state structure.
  265. */
  266. static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
  267. {
  268. return &rsp->node[0];
  269. }
  270. #ifdef CONFIG_SMP
  271. /*
  272. * If the specified CPU is offline, tell the caller that it is in
  273. * a quiescent state. Otherwise, whack it with a reschedule IPI.
  274. * Grace periods can end up waiting on an offline CPU when that
  275. * CPU is in the process of coming online -- it will be added to the
  276. * rcu_node bitmasks before it actually makes it online. The same thing
  277. * can happen while a CPU is in the process of coming online. Because this
  278. * race is quite rare, we check for it after detecting that the grace
  279. * period has been delayed rather than checking each and every CPU
  280. * each and every time we start a new grace period.
  281. */
  282. static int rcu_implicit_offline_qs(struct rcu_data *rdp)
  283. {
  284. /*
  285. * If the CPU is offline, it is in a quiescent state. We can
  286. * trust its state not to change because interrupts are disabled.
  287. */
  288. if (cpu_is_offline(rdp->cpu)) {
  289. trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, "ofl");
  290. rdp->offline_fqs++;
  291. return 1;
  292. }
  293. /* If preemptible RCU, no point in sending reschedule IPI. */
  294. if (rdp->preemptible)
  295. return 0;
  296. /* The CPU is online, so send it a reschedule IPI. */
  297. if (rdp->cpu != smp_processor_id())
  298. smp_send_reschedule(rdp->cpu);
  299. else
  300. set_need_resched();
  301. rdp->resched_ipi++;
  302. return 0;
  303. }
  304. #endif /* #ifdef CONFIG_SMP */
  305. #ifdef CONFIG_NO_HZ
  306. /**
  307. * rcu_enter_nohz - inform RCU that current CPU is entering nohz
  308. *
  309. * Enter nohz mode, in other words, -leave- the mode in which RCU
  310. * read-side critical sections can occur. (Though RCU read-side
  311. * critical sections can occur in irq handlers in nohz mode, a possibility
  312. * handled by rcu_irq_enter() and rcu_irq_exit()).
  313. */
  314. void rcu_enter_nohz(void)
  315. {
  316. unsigned long flags;
  317. struct rcu_dynticks *rdtp;
  318. local_irq_save(flags);
  319. rdtp = &__get_cpu_var(rcu_dynticks);
  320. if (--rdtp->dynticks_nesting) {
  321. local_irq_restore(flags);
  322. return;
  323. }
  324. trace_rcu_dyntick("Start");
  325. /* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
  326. smp_mb__before_atomic_inc(); /* See above. */
  327. atomic_inc(&rdtp->dynticks);
  328. smp_mb__after_atomic_inc(); /* Force ordering with next sojourn. */
  329. WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
  330. local_irq_restore(flags);
  331. }
  332. /*
  333. * rcu_exit_nohz - inform RCU that current CPU is leaving nohz
  334. *
  335. * Exit nohz mode, in other words, -enter- the mode in which RCU
  336. * read-side critical sections normally occur.
  337. */
  338. void rcu_exit_nohz(void)
  339. {
  340. unsigned long flags;
  341. struct rcu_dynticks *rdtp;
  342. local_irq_save(flags);
  343. rdtp = &__get_cpu_var(rcu_dynticks);
  344. if (rdtp->dynticks_nesting++) {
  345. local_irq_restore(flags);
  346. return;
  347. }
  348. smp_mb__before_atomic_inc(); /* Force ordering w/previous sojourn. */
  349. atomic_inc(&rdtp->dynticks);
  350. /* CPUs seeing atomic_inc() must see later RCU read-side crit sects */
  351. smp_mb__after_atomic_inc(); /* See above. */
  352. WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
  353. trace_rcu_dyntick("End");
  354. local_irq_restore(flags);
  355. }
  356. /**
  357. * rcu_nmi_enter - inform RCU of entry to NMI context
  358. *
  359. * If the CPU was idle with dynamic ticks active, and there is no
  360. * irq handler running, this updates rdtp->dynticks_nmi to let the
  361. * RCU grace-period handling know that the CPU is active.
  362. */
  363. void rcu_nmi_enter(void)
  364. {
  365. struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
  366. if (rdtp->dynticks_nmi_nesting == 0 &&
  367. (atomic_read(&rdtp->dynticks) & 0x1))
  368. return;
  369. rdtp->dynticks_nmi_nesting++;
  370. smp_mb__before_atomic_inc(); /* Force delay from prior write. */
  371. atomic_inc(&rdtp->dynticks);
  372. /* CPUs seeing atomic_inc() must see later RCU read-side crit sects */
  373. smp_mb__after_atomic_inc(); /* See above. */
  374. WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
  375. }
  376. /**
  377. * rcu_nmi_exit - inform RCU of exit from NMI context
  378. *
  379. * If the CPU was idle with dynamic ticks active, and there is no
  380. * irq handler running, this updates rdtp->dynticks_nmi to let the
  381. * RCU grace-period handling know that the CPU is no longer active.
  382. */
  383. void rcu_nmi_exit(void)
  384. {
  385. struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
  386. if (rdtp->dynticks_nmi_nesting == 0 ||
  387. --rdtp->dynticks_nmi_nesting != 0)
  388. return;
  389. /* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
  390. smp_mb__before_atomic_inc(); /* See above. */
  391. atomic_inc(&rdtp->dynticks);
  392. smp_mb__after_atomic_inc(); /* Force delay to next write. */
  393. WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
  394. }
  395. /**
  396. * rcu_irq_enter - inform RCU of entry to hard irq context
  397. *
  398. * If the CPU was idle with dynamic ticks active, this updates the
  399. * rdtp->dynticks to let the RCU handling know that the CPU is active.
  400. */
  401. void rcu_irq_enter(void)
  402. {
  403. rcu_exit_nohz();
  404. }
  405. /**
  406. * rcu_irq_exit - inform RCU of exit from hard irq context
  407. *
  408. * If the CPU was idle with dynamic ticks active, update the rdp->dynticks
  409. * to put let the RCU handling be aware that the CPU is going back to idle
  410. * with no ticks.
  411. */
  412. void rcu_irq_exit(void)
  413. {
  414. rcu_enter_nohz();
  415. }
  416. #ifdef CONFIG_SMP
  417. /*
  418. * Snapshot the specified CPU's dynticks counter so that we can later
  419. * credit them with an implicit quiescent state. Return 1 if this CPU
  420. * is in dynticks idle mode, which is an extended quiescent state.
  421. */
  422. static int dyntick_save_progress_counter(struct rcu_data *rdp)
  423. {
  424. rdp->dynticks_snap = atomic_add_return(0, &rdp->dynticks->dynticks);
  425. return 0;
  426. }
  427. /*
  428. * Return true if the specified CPU has passed through a quiescent
  429. * state by virtue of being in or having passed through an dynticks
  430. * idle state since the last call to dyntick_save_progress_counter()
  431. * for this same CPU.
  432. */
  433. static int rcu_implicit_dynticks_qs(struct rcu_data *rdp)
  434. {
  435. unsigned int curr;
  436. unsigned int snap;
  437. curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);
  438. snap = (unsigned int)rdp->dynticks_snap;
  439. /*
  440. * If the CPU passed through or entered a dynticks idle phase with
  441. * no active irq/NMI handlers, then we can safely pretend that the CPU
  442. * already acknowledged the request to pass through a quiescent
  443. * state. Either way, that CPU cannot possibly be in an RCU
  444. * read-side critical section that started before the beginning
  445. * of the current RCU grace period.
  446. */
  447. if ((curr & 0x1) == 0 || UINT_CMP_GE(curr, snap + 2)) {
  448. trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, "dti");
  449. rdp->dynticks_fqs++;
  450. return 1;
  451. }
  452. /* Go check for the CPU being offline. */
  453. return rcu_implicit_offline_qs(rdp);
  454. }
  455. #endif /* #ifdef CONFIG_SMP */
  456. #else /* #ifdef CONFIG_NO_HZ */
  457. #ifdef CONFIG_SMP
  458. static int dyntick_save_progress_counter(struct rcu_data *rdp)
  459. {
  460. return 0;
  461. }
  462. static int rcu_implicit_dynticks_qs(struct rcu_data *rdp)
  463. {
  464. return rcu_implicit_offline_qs(rdp);
  465. }
  466. #endif /* #ifdef CONFIG_SMP */
  467. #endif /* #else #ifdef CONFIG_NO_HZ */
  468. int rcu_cpu_stall_suppress __read_mostly;
  469. static void record_gp_stall_check_time(struct rcu_state *rsp)
  470. {
  471. rsp->gp_start = jiffies;
  472. rsp->jiffies_stall = jiffies + RCU_SECONDS_TILL_STALL_CHECK;
  473. }
  474. static void print_other_cpu_stall(struct rcu_state *rsp)
  475. {
  476. int cpu;
  477. long delta;
  478. unsigned long flags;
  479. int ndetected;
  480. struct rcu_node *rnp = rcu_get_root(rsp);
  481. /* Only let one CPU complain about others per time interval. */
  482. raw_spin_lock_irqsave(&rnp->lock, flags);
  483. delta = jiffies - rsp->jiffies_stall;
  484. if (delta < RCU_STALL_RAT_DELAY || !rcu_gp_in_progress(rsp)) {
  485. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  486. return;
  487. }
  488. rsp->jiffies_stall = jiffies + RCU_SECONDS_TILL_STALL_RECHECK;
  489. /*
  490. * Now rat on any tasks that got kicked up to the root rcu_node
  491. * due to CPU offlining.
  492. */
  493. ndetected = rcu_print_task_stall(rnp);
  494. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  495. /*
  496. * OK, time to rat on our buddy...
  497. * See Documentation/RCU/stallwarn.txt for info on how to debug
  498. * RCU CPU stall warnings.
  499. */
  500. printk(KERN_ERR "INFO: %s detected stalls on CPUs/tasks: {",
  501. rsp->name);
  502. rcu_for_each_leaf_node(rsp, rnp) {
  503. raw_spin_lock_irqsave(&rnp->lock, flags);
  504. ndetected += rcu_print_task_stall(rnp);
  505. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  506. if (rnp->qsmask == 0)
  507. continue;
  508. for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++)
  509. if (rnp->qsmask & (1UL << cpu)) {
  510. printk(" %d", rnp->grplo + cpu);
  511. ndetected++;
  512. }
  513. }
  514. printk("} (detected by %d, t=%ld jiffies)\n",
  515. smp_processor_id(), (long)(jiffies - rsp->gp_start));
  516. if (ndetected == 0)
  517. printk(KERN_ERR "INFO: Stall ended before state dump start\n");
  518. else if (!trigger_all_cpu_backtrace())
  519. dump_stack();
  520. /* If so configured, complain about tasks blocking the grace period. */
  521. rcu_print_detail_task_stall(rsp);
  522. force_quiescent_state(rsp, 0); /* Kick them all. */
  523. }
  524. static void print_cpu_stall(struct rcu_state *rsp)
  525. {
  526. unsigned long flags;
  527. struct rcu_node *rnp = rcu_get_root(rsp);
  528. /*
  529. * OK, time to rat on ourselves...
  530. * See Documentation/RCU/stallwarn.txt for info on how to debug
  531. * RCU CPU stall warnings.
  532. */
  533. printk(KERN_ERR "INFO: %s detected stall on CPU %d (t=%lu jiffies)\n",
  534. rsp->name, smp_processor_id(), jiffies - rsp->gp_start);
  535. if (!trigger_all_cpu_backtrace())
  536. dump_stack();
  537. raw_spin_lock_irqsave(&rnp->lock, flags);
  538. if (ULONG_CMP_GE(jiffies, rsp->jiffies_stall))
  539. rsp->jiffies_stall =
  540. jiffies + RCU_SECONDS_TILL_STALL_RECHECK;
  541. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  542. set_need_resched(); /* kick ourselves to get things going. */
  543. }
  544. static void check_cpu_stall(struct rcu_state *rsp, struct rcu_data *rdp)
  545. {
  546. unsigned long j;
  547. unsigned long js;
  548. struct rcu_node *rnp;
  549. if (rcu_cpu_stall_suppress)
  550. return;
  551. j = ACCESS_ONCE(jiffies);
  552. js = ACCESS_ONCE(rsp->jiffies_stall);
  553. rnp = rdp->mynode;
  554. if ((ACCESS_ONCE(rnp->qsmask) & rdp->grpmask) && ULONG_CMP_GE(j, js)) {
  555. /* We haven't checked in, so go dump stack. */
  556. print_cpu_stall(rsp);
  557. } else if (rcu_gp_in_progress(rsp) &&
  558. ULONG_CMP_GE(j, js + RCU_STALL_RAT_DELAY)) {
  559. /* They had a few time units to dump stack, so complain. */
  560. print_other_cpu_stall(rsp);
  561. }
  562. }
  563. static int rcu_panic(struct notifier_block *this, unsigned long ev, void *ptr)
  564. {
  565. rcu_cpu_stall_suppress = 1;
  566. return NOTIFY_DONE;
  567. }
  568. /**
  569. * rcu_cpu_stall_reset - prevent further stall warnings in current grace period
  570. *
  571. * Set the stall-warning timeout way off into the future, thus preventing
  572. * any RCU CPU stall-warning messages from appearing in the current set of
  573. * RCU grace periods.
  574. *
  575. * The caller must disable hard irqs.
  576. */
  577. void rcu_cpu_stall_reset(void)
  578. {
  579. rcu_sched_state.jiffies_stall = jiffies + ULONG_MAX / 2;
  580. rcu_bh_state.jiffies_stall = jiffies + ULONG_MAX / 2;
  581. rcu_preempt_stall_reset();
  582. }
  583. static struct notifier_block rcu_panic_block = {
  584. .notifier_call = rcu_panic,
  585. };
  586. static void __init check_cpu_stall_init(void)
  587. {
  588. atomic_notifier_chain_register(&panic_notifier_list, &rcu_panic_block);
  589. }
  590. /*
  591. * Update CPU-local rcu_data state to record the newly noticed grace period.
  592. * This is used both when we started the grace period and when we notice
  593. * that someone else started the grace period. The caller must hold the
  594. * ->lock of the leaf rcu_node structure corresponding to the current CPU,
  595. * and must have irqs disabled.
  596. */
  597. static void __note_new_gpnum(struct rcu_state *rsp, struct rcu_node *rnp, struct rcu_data *rdp)
  598. {
  599. if (rdp->gpnum != rnp->gpnum) {
  600. /*
  601. * If the current grace period is waiting for this CPU,
  602. * set up to detect a quiescent state, otherwise don't
  603. * go looking for one.
  604. */
  605. rdp->gpnum = rnp->gpnum;
  606. trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpustart");
  607. if (rnp->qsmask & rdp->grpmask) {
  608. rdp->qs_pending = 1;
  609. rdp->passed_quiesce = 0;
  610. } else
  611. rdp->qs_pending = 0;
  612. }
  613. }
  614. static void note_new_gpnum(struct rcu_state *rsp, struct rcu_data *rdp)
  615. {
  616. unsigned long flags;
  617. struct rcu_node *rnp;
  618. local_irq_save(flags);
  619. rnp = rdp->mynode;
  620. if (rdp->gpnum == ACCESS_ONCE(rnp->gpnum) || /* outside lock. */
  621. !raw_spin_trylock(&rnp->lock)) { /* irqs already off, so later. */
  622. local_irq_restore(flags);
  623. return;
  624. }
  625. __note_new_gpnum(rsp, rnp, rdp);
  626. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  627. }
  628. /*
  629. * Did someone else start a new RCU grace period start since we last
  630. * checked? Update local state appropriately if so. Must be called
  631. * on the CPU corresponding to rdp.
  632. */
  633. static int
  634. check_for_new_grace_period(struct rcu_state *rsp, struct rcu_data *rdp)
  635. {
  636. unsigned long flags;
  637. int ret = 0;
  638. local_irq_save(flags);
  639. if (rdp->gpnum != rsp->gpnum) {
  640. note_new_gpnum(rsp, rdp);
  641. ret = 1;
  642. }
  643. local_irq_restore(flags);
  644. return ret;
  645. }
  646. /*
  647. * Advance this CPU's callbacks, but only if the current grace period
  648. * has ended. This may be called only from the CPU to whom the rdp
  649. * belongs. In addition, the corresponding leaf rcu_node structure's
  650. * ->lock must be held by the caller, with irqs disabled.
  651. */
  652. static void
  653. __rcu_process_gp_end(struct rcu_state *rsp, struct rcu_node *rnp, struct rcu_data *rdp)
  654. {
  655. /* Did another grace period end? */
  656. if (rdp->completed != rnp->completed) {
  657. /* Advance callbacks. No harm if list empty. */
  658. rdp->nxttail[RCU_DONE_TAIL] = rdp->nxttail[RCU_WAIT_TAIL];
  659. rdp->nxttail[RCU_WAIT_TAIL] = rdp->nxttail[RCU_NEXT_READY_TAIL];
  660. rdp->nxttail[RCU_NEXT_READY_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
  661. /* Remember that we saw this grace-period completion. */
  662. rdp->completed = rnp->completed;
  663. trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpuend");
  664. /*
  665. * If we were in an extended quiescent state, we may have
  666. * missed some grace periods that others CPUs handled on
  667. * our behalf. Catch up with this state to avoid noting
  668. * spurious new grace periods. If another grace period
  669. * has started, then rnp->gpnum will have advanced, so
  670. * we will detect this later on.
  671. */
  672. if (ULONG_CMP_LT(rdp->gpnum, rdp->completed))
  673. rdp->gpnum = rdp->completed;
  674. /*
  675. * If RCU does not need a quiescent state from this CPU,
  676. * then make sure that this CPU doesn't go looking for one.
  677. */
  678. if ((rnp->qsmask & rdp->grpmask) == 0)
  679. rdp->qs_pending = 0;
  680. }
  681. }
  682. /*
  683. * Advance this CPU's callbacks, but only if the current grace period
  684. * has ended. This may be called only from the CPU to whom the rdp
  685. * belongs.
  686. */
  687. static void
  688. rcu_process_gp_end(struct rcu_state *rsp, struct rcu_data *rdp)
  689. {
  690. unsigned long flags;
  691. struct rcu_node *rnp;
  692. local_irq_save(flags);
  693. rnp = rdp->mynode;
  694. if (rdp->completed == ACCESS_ONCE(rnp->completed) || /* outside lock. */
  695. !raw_spin_trylock(&rnp->lock)) { /* irqs already off, so later. */
  696. local_irq_restore(flags);
  697. return;
  698. }
  699. __rcu_process_gp_end(rsp, rnp, rdp);
  700. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  701. }
  702. /*
  703. * Do per-CPU grace-period initialization for running CPU. The caller
  704. * must hold the lock of the leaf rcu_node structure corresponding to
  705. * this CPU.
  706. */
  707. static void
  708. rcu_start_gp_per_cpu(struct rcu_state *rsp, struct rcu_node *rnp, struct rcu_data *rdp)
  709. {
  710. /* Prior grace period ended, so advance callbacks for current CPU. */
  711. __rcu_process_gp_end(rsp, rnp, rdp);
  712. /*
  713. * Because this CPU just now started the new grace period, we know
  714. * that all of its callbacks will be covered by this upcoming grace
  715. * period, even the ones that were registered arbitrarily recently.
  716. * Therefore, advance all outstanding callbacks to RCU_WAIT_TAIL.
  717. *
  718. * Other CPUs cannot be sure exactly when the grace period started.
  719. * Therefore, their recently registered callbacks must pass through
  720. * an additional RCU_NEXT_READY stage, so that they will be handled
  721. * by the next RCU grace period.
  722. */
  723. rdp->nxttail[RCU_NEXT_READY_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
  724. rdp->nxttail[RCU_WAIT_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
  725. /* Set state so that this CPU will detect the next quiescent state. */
  726. __note_new_gpnum(rsp, rnp, rdp);
  727. }
  728. /*
  729. * Start a new RCU grace period if warranted, re-initializing the hierarchy
  730. * in preparation for detecting the next grace period. The caller must hold
  731. * the root node's ->lock, which is released before return. Hard irqs must
  732. * be disabled.
  733. */
  734. static void
  735. rcu_start_gp(struct rcu_state *rsp, unsigned long flags)
  736. __releases(rcu_get_root(rsp)->lock)
  737. {
  738. struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
  739. struct rcu_node *rnp = rcu_get_root(rsp);
  740. if (!rcu_scheduler_fully_active ||
  741. !cpu_needs_another_gp(rsp, rdp) ||
  742. rsp->fqs_active) {
  743. if (rcu_scheduler_fully_active &&
  744. cpu_needs_another_gp(rsp, rdp))
  745. rsp->fqs_need_gp = 1;
  746. if (rnp->completed == rsp->completed) {
  747. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  748. return;
  749. }
  750. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  751. /*
  752. * Propagate new ->completed value to rcu_node structures
  753. * so that other CPUs don't have to wait until the start
  754. * of the next grace period to process their callbacks.
  755. */
  756. rcu_for_each_node_breadth_first(rsp, rnp) {
  757. raw_spin_lock(&rnp->lock); /* irqs already disabled. */
  758. rnp->completed = rsp->completed;
  759. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  760. }
  761. local_irq_restore(flags);
  762. return;
  763. }
  764. /* Advance to a new grace period and initialize state. */
  765. rsp->gpnum++;
  766. trace_rcu_grace_period(rsp->name, rsp->gpnum, "start");
  767. WARN_ON_ONCE(rsp->signaled == RCU_GP_INIT);
  768. rsp->signaled = RCU_GP_INIT; /* Hold off force_quiescent_state. */
  769. rsp->jiffies_force_qs = jiffies + RCU_JIFFIES_TILL_FORCE_QS;
  770. record_gp_stall_check_time(rsp);
  771. /* Special-case the common single-level case. */
  772. if (NUM_RCU_NODES == 1) {
  773. rcu_preempt_check_blocked_tasks(rnp);
  774. rnp->qsmask = rnp->qsmaskinit;
  775. rnp->gpnum = rsp->gpnum;
  776. rnp->completed = rsp->completed;
  777. rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state OK. */
  778. rcu_start_gp_per_cpu(rsp, rnp, rdp);
  779. rcu_preempt_boost_start_gp(rnp);
  780. trace_rcu_grace_period_init(rsp->name, rnp->gpnum,
  781. rnp->level, rnp->grplo,
  782. rnp->grphi, rnp->qsmask);
  783. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  784. return;
  785. }
  786. raw_spin_unlock(&rnp->lock); /* leave irqs disabled. */
  787. /* Exclude any concurrent CPU-hotplug operations. */
  788. raw_spin_lock(&rsp->onofflock); /* irqs already disabled. */
  789. /*
  790. * Set the quiescent-state-needed bits in all the rcu_node
  791. * structures for all currently online CPUs in breadth-first
  792. * order, starting from the root rcu_node structure. This
  793. * operation relies on the layout of the hierarchy within the
  794. * rsp->node[] array. Note that other CPUs will access only
  795. * the leaves of the hierarchy, which still indicate that no
  796. * grace period is in progress, at least until the corresponding
  797. * leaf node has been initialized. In addition, we have excluded
  798. * CPU-hotplug operations.
  799. *
  800. * Note that the grace period cannot complete until we finish
  801. * the initialization process, as there will be at least one
  802. * qsmask bit set in the root node until that time, namely the
  803. * one corresponding to this CPU, due to the fact that we have
  804. * irqs disabled.
  805. */
  806. rcu_for_each_node_breadth_first(rsp, rnp) {
  807. raw_spin_lock(&rnp->lock); /* irqs already disabled. */
  808. rcu_preempt_check_blocked_tasks(rnp);
  809. rnp->qsmask = rnp->qsmaskinit;
  810. rnp->gpnum = rsp->gpnum;
  811. rnp->completed = rsp->completed;
  812. if (rnp == rdp->mynode)
  813. rcu_start_gp_per_cpu(rsp, rnp, rdp);
  814. rcu_preempt_boost_start_gp(rnp);
  815. trace_rcu_grace_period_init(rsp->name, rnp->gpnum,
  816. rnp->level, rnp->grplo,
  817. rnp->grphi, rnp->qsmask);
  818. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  819. }
  820. rnp = rcu_get_root(rsp);
  821. raw_spin_lock(&rnp->lock); /* irqs already disabled. */
  822. rsp->signaled = RCU_SIGNAL_INIT; /* force_quiescent_state now OK. */
  823. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  824. raw_spin_unlock_irqrestore(&rsp->onofflock, flags);
  825. }
  826. /*
  827. * Report a full set of quiescent states to the specified rcu_state
  828. * data structure. This involves cleaning up after the prior grace
  829. * period and letting rcu_start_gp() start up the next grace period
  830. * if one is needed. Note that the caller must hold rnp->lock, as
  831. * required by rcu_start_gp(), which will release it.
  832. */
  833. static void rcu_report_qs_rsp(struct rcu_state *rsp, unsigned long flags)
  834. __releases(rcu_get_root(rsp)->lock)
  835. {
  836. unsigned long gp_duration;
  837. WARN_ON_ONCE(!rcu_gp_in_progress(rsp));
  838. /*
  839. * Ensure that all grace-period and pre-grace-period activity
  840. * is seen before the assignment to rsp->completed.
  841. */
  842. smp_mb(); /* See above block comment. */
  843. gp_duration = jiffies - rsp->gp_start;
  844. if (gp_duration > rsp->gp_max)
  845. rsp->gp_max = gp_duration;
  846. rsp->completed = rsp->gpnum;
  847. trace_rcu_grace_period(rsp->name, rsp->completed, "end");
  848. rsp->signaled = RCU_GP_IDLE;
  849. rcu_start_gp(rsp, flags); /* releases root node's rnp->lock. */
  850. }
  851. /*
  852. * Similar to rcu_report_qs_rdp(), for which it is a helper function.
  853. * Allows quiescent states for a group of CPUs to be reported at one go
  854. * to the specified rcu_node structure, though all the CPUs in the group
  855. * must be represented by the same rcu_node structure (which need not be
  856. * a leaf rcu_node structure, though it often will be). That structure's
  857. * lock must be held upon entry, and it is released before return.
  858. */
  859. static void
  860. rcu_report_qs_rnp(unsigned long mask, struct rcu_state *rsp,
  861. struct rcu_node *rnp, unsigned long flags)
  862. __releases(rnp->lock)
  863. {
  864. struct rcu_node *rnp_c;
  865. /* Walk up the rcu_node hierarchy. */
  866. for (;;) {
  867. if (!(rnp->qsmask & mask)) {
  868. /* Our bit has already been cleared, so done. */
  869. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  870. return;
  871. }
  872. rnp->qsmask &= ~mask;
  873. trace_rcu_quiescent_state_report(rsp->name, rnp->gpnum,
  874. mask, rnp->qsmask, rnp->level,
  875. rnp->grplo, rnp->grphi,
  876. !!rnp->gp_tasks);
  877. if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
  878. /* Other bits still set at this level, so done. */
  879. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  880. return;
  881. }
  882. mask = rnp->grpmask;
  883. if (rnp->parent == NULL) {
  884. /* No more levels. Exit loop holding root lock. */
  885. break;
  886. }
  887. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  888. rnp_c = rnp;
  889. rnp = rnp->parent;
  890. raw_spin_lock_irqsave(&rnp->lock, flags);
  891. WARN_ON_ONCE(rnp_c->qsmask);
  892. }
  893. /*
  894. * Get here if we are the last CPU to pass through a quiescent
  895. * state for this grace period. Invoke rcu_report_qs_rsp()
  896. * to clean up and start the next grace period if one is needed.
  897. */
  898. rcu_report_qs_rsp(rsp, flags); /* releases rnp->lock. */
  899. }
  900. /*
  901. * Record a quiescent state for the specified CPU to that CPU's rcu_data
  902. * structure. This must be either called from the specified CPU, or
  903. * called when the specified CPU is known to be offline (and when it is
  904. * also known that no other CPU is concurrently trying to help the offline
  905. * CPU). The lastcomp argument is used to make sure we are still in the
  906. * grace period of interest. We don't want to end the current grace period
  907. * based on quiescent states detected in an earlier grace period!
  908. */
  909. static void
  910. rcu_report_qs_rdp(int cpu, struct rcu_state *rsp, struct rcu_data *rdp, long lastgp)
  911. {
  912. unsigned long flags;
  913. unsigned long mask;
  914. struct rcu_node *rnp;
  915. rnp = rdp->mynode;
  916. raw_spin_lock_irqsave(&rnp->lock, flags);
  917. if (lastgp != rnp->gpnum || rnp->completed == rnp->gpnum) {
  918. /*
  919. * The grace period in which this quiescent state was
  920. * recorded has ended, so don't report it upwards.
  921. * We will instead need a new quiescent state that lies
  922. * within the current grace period.
  923. */
  924. rdp->passed_quiesce = 0; /* need qs for new gp. */
  925. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  926. return;
  927. }
  928. mask = rdp->grpmask;
  929. if ((rnp->qsmask & mask) == 0) {
  930. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  931. } else {
  932. rdp->qs_pending = 0;
  933. /*
  934. * This GP can't end until cpu checks in, so all of our
  935. * callbacks can be processed during the next GP.
  936. */
  937. rdp->nxttail[RCU_NEXT_READY_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
  938. rcu_report_qs_rnp(mask, rsp, rnp, flags); /* rlses rnp->lock */
  939. }
  940. }
  941. /*
  942. * Check to see if there is a new grace period of which this CPU
  943. * is not yet aware, and if so, set up local rcu_data state for it.
  944. * Otherwise, see if this CPU has just passed through its first
  945. * quiescent state for this grace period, and record that fact if so.
  946. */
  947. static void
  948. rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)
  949. {
  950. /* If there is now a new grace period, record and return. */
  951. if (check_for_new_grace_period(rsp, rdp))
  952. return;
  953. /*
  954. * Does this CPU still need to do its part for current grace period?
  955. * If no, return and let the other CPUs do their part as well.
  956. */
  957. if (!rdp->qs_pending)
  958. return;
  959. /*
  960. * Was there a quiescent state since the beginning of the grace
  961. * period? If no, then exit and wait for the next call.
  962. */
  963. if (!rdp->passed_quiesce)
  964. return;
  965. /*
  966. * Tell RCU we are done (but rcu_report_qs_rdp() will be the
  967. * judge of that).
  968. */
  969. rcu_report_qs_rdp(rdp->cpu, rsp, rdp, rdp->passed_quiesce_gpnum);
  970. }
  971. #ifdef CONFIG_HOTPLUG_CPU
  972. /*
  973. * Move a dying CPU's RCU callbacks to online CPU's callback list.
  974. * Synchronization is not required because this function executes
  975. * in stop_machine() context.
  976. */
  977. static void rcu_send_cbs_to_online(struct rcu_state *rsp)
  978. {
  979. int i;
  980. /* current DYING CPU is cleared in the cpu_online_mask */
  981. int receive_cpu = cpumask_any(cpu_online_mask);
  982. struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
  983. struct rcu_data *receive_rdp = per_cpu_ptr(rsp->rda, receive_cpu);
  984. if (rdp->nxtlist == NULL)
  985. return; /* irqs disabled, so comparison is stable. */
  986. *receive_rdp->nxttail[RCU_NEXT_TAIL] = rdp->nxtlist;
  987. receive_rdp->nxttail[RCU_NEXT_TAIL] = rdp->nxttail[RCU_NEXT_TAIL];
  988. receive_rdp->qlen += rdp->qlen;
  989. receive_rdp->n_cbs_adopted += rdp->qlen;
  990. rdp->n_cbs_orphaned += rdp->qlen;
  991. rdp->nxtlist = NULL;
  992. for (i = 0; i < RCU_NEXT_SIZE; i++)
  993. rdp->nxttail[i] = &rdp->nxtlist;
  994. rdp->qlen = 0;
  995. }
  996. /*
  997. * Remove the outgoing CPU from the bitmasks in the rcu_node hierarchy
  998. * and move all callbacks from the outgoing CPU to the current one.
  999. * There can only be one CPU hotplug operation at a time, so no other
  1000. * CPU can be attempting to update rcu_cpu_kthread_task.
  1001. */
  1002. static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)
  1003. {
  1004. unsigned long flags;
  1005. unsigned long mask;
  1006. int need_report = 0;
  1007. struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
  1008. struct rcu_node *rnp;
  1009. rcu_stop_cpu_kthread(cpu);
  1010. /* Exclude any attempts to start a new grace period. */
  1011. raw_spin_lock_irqsave(&rsp->onofflock, flags);
  1012. /* Remove the outgoing CPU from the masks in the rcu_node hierarchy. */
  1013. rnp = rdp->mynode; /* this is the outgoing CPU's rnp. */
  1014. mask = rdp->grpmask; /* rnp->grplo is constant. */
  1015. do {
  1016. raw_spin_lock(&rnp->lock); /* irqs already disabled. */
  1017. rnp->qsmaskinit &= ~mask;
  1018. if (rnp->qsmaskinit != 0) {
  1019. if (rnp != rdp->mynode)
  1020. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  1021. else
  1022. trace_rcu_grace_period(rsp->name,
  1023. rnp->gpnum + 1 -
  1024. !!(rnp->qsmask & mask),
  1025. "cpuofl");
  1026. break;
  1027. }
  1028. if (rnp == rdp->mynode) {
  1029. trace_rcu_grace_period(rsp->name,
  1030. rnp->gpnum + 1 -
  1031. !!(rnp->qsmask & mask),
  1032. "cpuofl");
  1033. need_report = rcu_preempt_offline_tasks(rsp, rnp, rdp);
  1034. } else
  1035. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  1036. mask = rnp->grpmask;
  1037. rnp = rnp->parent;
  1038. } while (rnp != NULL);
  1039. /*
  1040. * We still hold the leaf rcu_node structure lock here, and
  1041. * irqs are still disabled. The reason for this subterfuge is
  1042. * because invoking rcu_report_unblock_qs_rnp() with ->onofflock
  1043. * held leads to deadlock.
  1044. */
  1045. raw_spin_unlock(&rsp->onofflock); /* irqs remain disabled. */
  1046. rnp = rdp->mynode;
  1047. if (need_report & RCU_OFL_TASKS_NORM_GP)
  1048. rcu_report_unblock_qs_rnp(rnp, flags);
  1049. else
  1050. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1051. if (need_report & RCU_OFL_TASKS_EXP_GP)
  1052. rcu_report_exp_rnp(rsp, rnp);
  1053. rcu_node_kthread_setaffinity(rnp, -1);
  1054. }
  1055. /*
  1056. * Remove the specified CPU from the RCU hierarchy and move any pending
  1057. * callbacks that it might have to the current CPU. This code assumes
  1058. * that at least one CPU in the system will remain running at all times.
  1059. * Any attempt to offline -all- CPUs is likely to strand RCU callbacks.
  1060. */
  1061. static void rcu_offline_cpu(int cpu)
  1062. {
  1063. __rcu_offline_cpu(cpu, &rcu_sched_state);
  1064. __rcu_offline_cpu(cpu, &rcu_bh_state);
  1065. rcu_preempt_offline_cpu(cpu);
  1066. }
  1067. #else /* #ifdef CONFIG_HOTPLUG_CPU */
  1068. static void rcu_send_cbs_to_online(struct rcu_state *rsp)
  1069. {
  1070. }
  1071. static void rcu_offline_cpu(int cpu)
  1072. {
  1073. }
  1074. #endif /* #else #ifdef CONFIG_HOTPLUG_CPU */
  1075. /*
  1076. * Invoke any RCU callbacks that have made it to the end of their grace
  1077. * period. Thottle as specified by rdp->blimit.
  1078. */
  1079. static void rcu_do_batch(struct rcu_state *rsp, struct rcu_data *rdp)
  1080. {
  1081. unsigned long flags;
  1082. struct rcu_head *next, *list, **tail;
  1083. int bl, count;
  1084. /* If no callbacks are ready, just return.*/
  1085. if (!cpu_has_callbacks_ready_to_invoke(rdp)) {
  1086. trace_rcu_batch_start(rsp->name, 0, 0);
  1087. trace_rcu_batch_end(rsp->name, 0);
  1088. return;
  1089. }
  1090. /*
  1091. * Extract the list of ready callbacks, disabling to prevent
  1092. * races with call_rcu() from interrupt handlers.
  1093. */
  1094. local_irq_save(flags);
  1095. bl = rdp->blimit;
  1096. trace_rcu_batch_start(rsp->name, rdp->qlen, bl);
  1097. list = rdp->nxtlist;
  1098. rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL];
  1099. *rdp->nxttail[RCU_DONE_TAIL] = NULL;
  1100. tail = rdp->nxttail[RCU_DONE_TAIL];
  1101. for (count = RCU_NEXT_SIZE - 1; count >= 0; count--)
  1102. if (rdp->nxttail[count] == rdp->nxttail[RCU_DONE_TAIL])
  1103. rdp->nxttail[count] = &rdp->nxtlist;
  1104. local_irq_restore(flags);
  1105. /* Invoke callbacks. */
  1106. count = 0;
  1107. while (list) {
  1108. next = list->next;
  1109. prefetch(next);
  1110. debug_rcu_head_unqueue(list);
  1111. __rcu_reclaim(rsp->name, list);
  1112. list = next;
  1113. if (++count >= bl)
  1114. break;
  1115. }
  1116. local_irq_save(flags);
  1117. trace_rcu_batch_end(rsp->name, count);
  1118. /* Update count, and requeue any remaining callbacks. */
  1119. rdp->qlen -= count;
  1120. rdp->n_cbs_invoked += count;
  1121. if (list != NULL) {
  1122. *tail = rdp->nxtlist;
  1123. rdp->nxtlist = list;
  1124. for (count = 0; count < RCU_NEXT_SIZE; count++)
  1125. if (&rdp->nxtlist == rdp->nxttail[count])
  1126. rdp->nxttail[count] = tail;
  1127. else
  1128. break;
  1129. }
  1130. /* Reinstate batch limit if we have worked down the excess. */
  1131. if (rdp->blimit == LONG_MAX && rdp->qlen <= qlowmark)
  1132. rdp->blimit = blimit;
  1133. /* Reset ->qlen_last_fqs_check trigger if enough CBs have drained. */
  1134. if (rdp->qlen == 0 && rdp->qlen_last_fqs_check != 0) {
  1135. rdp->qlen_last_fqs_check = 0;
  1136. rdp->n_force_qs_snap = rsp->n_force_qs;
  1137. } else if (rdp->qlen < rdp->qlen_last_fqs_check - qhimark)
  1138. rdp->qlen_last_fqs_check = rdp->qlen;
  1139. local_irq_restore(flags);
  1140. /* Re-invoke RCU core processing if there are callbacks remaining. */
  1141. if (cpu_has_callbacks_ready_to_invoke(rdp))
  1142. invoke_rcu_core();
  1143. }
  1144. /*
  1145. * Check to see if this CPU is in a non-context-switch quiescent state
  1146. * (user mode or idle loop for rcu, non-softirq execution for rcu_bh).
  1147. * Also schedule RCU core processing.
  1148. *
  1149. * This function must be called with hardirqs disabled. It is normally
  1150. * invoked from the scheduling-clock interrupt. If rcu_pending returns
  1151. * false, there is no point in invoking rcu_check_callbacks().
  1152. */
  1153. void rcu_check_callbacks(int cpu, int user)
  1154. {
  1155. trace_rcu_utilization("Start scheduler-tick");
  1156. if (user ||
  1157. (idle_cpu(cpu) && rcu_scheduler_active &&
  1158. !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
  1159. /*
  1160. * Get here if this CPU took its interrupt from user
  1161. * mode or from the idle loop, and if this is not a
  1162. * nested interrupt. In this case, the CPU is in
  1163. * a quiescent state, so note it.
  1164. *
  1165. * No memory barrier is required here because both
  1166. * rcu_sched_qs() and rcu_bh_qs() reference only CPU-local
  1167. * variables that other CPUs neither access nor modify,
  1168. * at least not while the corresponding CPU is online.
  1169. */
  1170. rcu_sched_qs(cpu);
  1171. rcu_bh_qs(cpu);
  1172. } else if (!in_softirq()) {
  1173. /*
  1174. * Get here if this CPU did not take its interrupt from
  1175. * softirq, in other words, if it is not interrupting
  1176. * a rcu_bh read-side critical section. This is an _bh
  1177. * critical section, so note it.
  1178. */
  1179. rcu_bh_qs(cpu);
  1180. }
  1181. rcu_preempt_check_callbacks(cpu);
  1182. if (rcu_pending(cpu))
  1183. invoke_rcu_core();
  1184. trace_rcu_utilization("End scheduler-tick");
  1185. }
  1186. #ifdef CONFIG_SMP
  1187. /*
  1188. * Scan the leaf rcu_node structures, processing dyntick state for any that
  1189. * have not yet encountered a quiescent state, using the function specified.
  1190. * Also initiate boosting for any threads blocked on the root rcu_node.
  1191. *
  1192. * The caller must have suppressed start of new grace periods.
  1193. */
  1194. static void force_qs_rnp(struct rcu_state *rsp, int (*f)(struct rcu_data *))
  1195. {
  1196. unsigned long bit;
  1197. int cpu;
  1198. unsigned long flags;
  1199. unsigned long mask;
  1200. struct rcu_node *rnp;
  1201. rcu_for_each_leaf_node(rsp, rnp) {
  1202. mask = 0;
  1203. raw_spin_lock_irqsave(&rnp->lock, flags);
  1204. if (!rcu_gp_in_progress(rsp)) {
  1205. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1206. return;
  1207. }
  1208. if (rnp->qsmask == 0) {
  1209. rcu_initiate_boost(rnp, flags); /* releases rnp->lock */
  1210. continue;
  1211. }
  1212. cpu = rnp->grplo;
  1213. bit = 1;
  1214. for (; cpu <= rnp->grphi; cpu++, bit <<= 1) {
  1215. if ((rnp->qsmask & bit) != 0 &&
  1216. f(per_cpu_ptr(rsp->rda, cpu)))
  1217. mask |= bit;
  1218. }
  1219. if (mask != 0) {
  1220. /* rcu_report_qs_rnp() releases rnp->lock. */
  1221. rcu_report_qs_rnp(mask, rsp, rnp, flags);
  1222. continue;
  1223. }
  1224. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1225. }
  1226. rnp = rcu_get_root(rsp);
  1227. if (rnp->qsmask == 0) {
  1228. raw_spin_lock_irqsave(&rnp->lock, flags);
  1229. rcu_initiate_boost(rnp, flags); /* releases rnp->lock. */
  1230. }
  1231. }
  1232. /*
  1233. * Force quiescent states on reluctant CPUs, and also detect which
  1234. * CPUs are in dyntick-idle mode.
  1235. */
  1236. static void force_quiescent_state(struct rcu_state *rsp, int relaxed)
  1237. {
  1238. unsigned long flags;
  1239. struct rcu_node *rnp = rcu_get_root(rsp);
  1240. trace_rcu_utilization("Start fqs");
  1241. if (!rcu_gp_in_progress(rsp)) {
  1242. trace_rcu_utilization("End fqs");
  1243. return; /* No grace period in progress, nothing to force. */
  1244. }
  1245. if (!raw_spin_trylock_irqsave(&rsp->fqslock, flags)) {
  1246. rsp->n_force_qs_lh++; /* Inexact, can lose counts. Tough! */
  1247. trace_rcu_utilization("End fqs");
  1248. return; /* Someone else is already on the job. */
  1249. }
  1250. if (relaxed && ULONG_CMP_GE(rsp->jiffies_force_qs, jiffies))
  1251. goto unlock_fqs_ret; /* no emergency and done recently. */
  1252. rsp->n_force_qs++;
  1253. raw_spin_lock(&rnp->lock); /* irqs already disabled */
  1254. rsp->jiffies_force_qs = jiffies + RCU_JIFFIES_TILL_FORCE_QS;
  1255. if(!rcu_gp_in_progress(rsp)) {
  1256. rsp->n_force_qs_ngp++;
  1257. raw_spin_unlock(&rnp->lock); /* irqs remain disabled */
  1258. goto unlock_fqs_ret; /* no GP in progress, time updated. */
  1259. }
  1260. rsp->fqs_active = 1;
  1261. switch (rsp->signaled) {
  1262. case RCU_GP_IDLE:
  1263. case RCU_GP_INIT:
  1264. break; /* grace period idle or initializing, ignore. */
  1265. case RCU_SAVE_DYNTICK:
  1266. if (RCU_SIGNAL_INIT != RCU_SAVE_DYNTICK)
  1267. break; /* So gcc recognizes the dead code. */
  1268. raw_spin_unlock(&rnp->lock); /* irqs remain disabled */
  1269. /* Record dyntick-idle state. */
  1270. force_qs_rnp(rsp, dyntick_save_progress_counter);
  1271. raw_spin_lock(&rnp->lock); /* irqs already disabled */
  1272. if (rcu_gp_in_progress(rsp))
  1273. rsp->signaled = RCU_FORCE_QS;
  1274. break;
  1275. case RCU_FORCE_QS:
  1276. /* Check dyntick-idle state, send IPI to laggarts. */
  1277. raw_spin_unlock(&rnp->lock); /* irqs remain disabled */
  1278. force_qs_rnp(rsp, rcu_implicit_dynticks_qs);
  1279. /* Leave state in case more forcing is required. */
  1280. raw_spin_lock(&rnp->lock); /* irqs already disabled */
  1281. break;
  1282. }
  1283. rsp->fqs_active = 0;
  1284. if (rsp->fqs_need_gp) {
  1285. raw_spin_unlock(&rsp->fqslock); /* irqs remain disabled */
  1286. rsp->fqs_need_gp = 0;
  1287. rcu_start_gp(rsp, flags); /* releases rnp->lock */
  1288. trace_rcu_utilization("End fqs");
  1289. return;
  1290. }
  1291. raw_spin_unlock(&rnp->lock); /* irqs remain disabled */
  1292. unlock_fqs_ret:
  1293. raw_spin_unlock_irqrestore(&rsp->fqslock, flags);
  1294. trace_rcu_utilization("End fqs");
  1295. }
  1296. #else /* #ifdef CONFIG_SMP */
  1297. static void force_quiescent_state(struct rcu_state *rsp, int relaxed)
  1298. {
  1299. set_need_resched();
  1300. }
  1301. #endif /* #else #ifdef CONFIG_SMP */
  1302. /*
  1303. * This does the RCU core processing work for the specified rcu_state
  1304. * and rcu_data structures. This may be called only from the CPU to
  1305. * whom the rdp belongs.
  1306. */
  1307. static void
  1308. __rcu_process_callbacks(struct rcu_state *rsp, struct rcu_data *rdp)
  1309. {
  1310. unsigned long flags;
  1311. WARN_ON_ONCE(rdp->beenonline == 0);
  1312. /*
  1313. * If an RCU GP has gone long enough, go check for dyntick
  1314. * idle CPUs and, if needed, send resched IPIs.
  1315. */
  1316. if (ULONG_CMP_LT(ACCESS_ONCE(rsp->jiffies_force_qs), jiffies))
  1317. force_quiescent_state(rsp, 1);
  1318. /*
  1319. * Advance callbacks in response to end of earlier grace
  1320. * period that some other CPU ended.
  1321. */
  1322. rcu_process_gp_end(rsp, rdp);
  1323. /* Update RCU state based on any recent quiescent states. */
  1324. rcu_check_quiescent_state(rsp, rdp);
  1325. /* Does this CPU require a not-yet-started grace period? */
  1326. if (cpu_needs_another_gp(rsp, rdp)) {
  1327. raw_spin_lock_irqsave(&rcu_get_root(rsp)->lock, flags);
  1328. rcu_start_gp(rsp, flags); /* releases above lock */
  1329. }
  1330. /* If there are callbacks ready, invoke them. */
  1331. if (cpu_has_callbacks_ready_to_invoke(rdp))
  1332. invoke_rcu_callbacks(rsp, rdp);
  1333. }
  1334. /*
  1335. * Do RCU core processing for the current CPU.
  1336. */
  1337. static void rcu_process_callbacks(struct softirq_action *unused)
  1338. {
  1339. trace_rcu_utilization("Start RCU core");
  1340. __rcu_process_callbacks(&rcu_sched_state,
  1341. &__get_cpu_var(rcu_sched_data));
  1342. __rcu_process_callbacks(&rcu_bh_state, &__get_cpu_var(rcu_bh_data));
  1343. rcu_preempt_process_callbacks();
  1344. /* If we are last CPU on way to dyntick-idle mode, accelerate it. */
  1345. rcu_needs_cpu_flush();
  1346. trace_rcu_utilization("End RCU core");
  1347. }
  1348. /*
  1349. * Schedule RCU callback invocation. If the specified type of RCU
  1350. * does not support RCU priority boosting, just do a direct call,
  1351. * otherwise wake up the per-CPU kernel kthread. Note that because we
  1352. * are running on the current CPU with interrupts disabled, the
  1353. * rcu_cpu_kthread_task cannot disappear out from under us.
  1354. */
  1355. static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp)
  1356. {
  1357. if (unlikely(!ACCESS_ONCE(rcu_scheduler_fully_active)))
  1358. return;
  1359. if (likely(!rsp->boost)) {
  1360. rcu_do_batch(rsp, rdp);
  1361. return;
  1362. }
  1363. invoke_rcu_callbacks_kthread();
  1364. }
  1365. static void invoke_rcu_core(void)
  1366. {
  1367. raise_softirq(RCU_SOFTIRQ);
  1368. }
  1369. static void
  1370. __call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu),
  1371. struct rcu_state *rsp)
  1372. {
  1373. unsigned long flags;
  1374. struct rcu_data *rdp;
  1375. debug_rcu_head_queue(head);
  1376. head->func = func;
  1377. head->next = NULL;
  1378. smp_mb(); /* Ensure RCU update seen before callback registry. */
  1379. /*
  1380. * Opportunistically note grace-period endings and beginnings.
  1381. * Note that we might see a beginning right after we see an
  1382. * end, but never vice versa, since this CPU has to pass through
  1383. * a quiescent state betweentimes.
  1384. */
  1385. local_irq_save(flags);
  1386. rdp = this_cpu_ptr(rsp->rda);
  1387. /* Add the callback to our list. */
  1388. *rdp->nxttail[RCU_NEXT_TAIL] = head;
  1389. rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
  1390. rdp->qlen++;
  1391. if (__is_kfree_rcu_offset((unsigned long)func))
  1392. trace_rcu_kfree_callback(rsp->name, head, (unsigned long)func,
  1393. rdp->qlen);
  1394. else
  1395. trace_rcu_callback(rsp->name, head, rdp->qlen);
  1396. /* If interrupts were disabled, don't dive into RCU core. */
  1397. if (irqs_disabled_flags(flags)) {
  1398. local_irq_restore(flags);
  1399. return;
  1400. }
  1401. /*
  1402. * Force the grace period if too many callbacks or too long waiting.
  1403. * Enforce hysteresis, and don't invoke force_quiescent_state()
  1404. * if some other CPU has recently done so. Also, don't bother
  1405. * invoking force_quiescent_state() if the newly enqueued callback
  1406. * is the only one waiting for a grace period to complete.
  1407. */
  1408. if (unlikely(rdp->qlen > rdp->qlen_last_fqs_check + qhimark)) {
  1409. /* Are we ignoring a completed grace period? */
  1410. rcu_process_gp_end(rsp, rdp);
  1411. check_for_new_grace_period(rsp, rdp);
  1412. /* Start a new grace period if one not already started. */
  1413. if (!rcu_gp_in_progress(rsp)) {
  1414. unsigned long nestflag;
  1415. struct rcu_node *rnp_root = rcu_get_root(rsp);
  1416. raw_spin_lock_irqsave(&rnp_root->lock, nestflag);
  1417. rcu_start_gp(rsp, nestflag); /* rlses rnp_root->lock */
  1418. } else {
  1419. /* Give the grace period a kick. */
  1420. rdp->blimit = LONG_MAX;
  1421. if (rsp->n_force_qs == rdp->n_force_qs_snap &&
  1422. *rdp->nxttail[RCU_DONE_TAIL] != head)
  1423. force_quiescent_state(rsp, 0);
  1424. rdp->n_force_qs_snap = rsp->n_force_qs;
  1425. rdp->qlen_last_fqs_check = rdp->qlen;
  1426. }
  1427. } else if (ULONG_CMP_LT(ACCESS_ONCE(rsp->jiffies_force_qs), jiffies))
  1428. force_quiescent_state(rsp, 1);
  1429. local_irq_restore(flags);
  1430. }
  1431. /*
  1432. * Queue an RCU-sched callback for invocation after a grace period.
  1433. */
  1434. void call_rcu_sched(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
  1435. {
  1436. __call_rcu(head, func, &rcu_sched_state);
  1437. }
  1438. EXPORT_SYMBOL_GPL(call_rcu_sched);
  1439. /*
  1440. * Queue an RCU for invocation after a quicker grace period.
  1441. */
  1442. void call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
  1443. {
  1444. __call_rcu(head, func, &rcu_bh_state);
  1445. }
  1446. EXPORT_SYMBOL_GPL(call_rcu_bh);
  1447. /**
  1448. * synchronize_sched - wait until an rcu-sched grace period has elapsed.
  1449. *
  1450. * Control will return to the caller some time after a full rcu-sched
  1451. * grace period has elapsed, in other words after all currently executing
  1452. * rcu-sched read-side critical sections have completed. These read-side
  1453. * critical sections are delimited by rcu_read_lock_sched() and
  1454. * rcu_read_unlock_sched(), and may be nested. Note that preempt_disable(),
  1455. * local_irq_disable(), and so on may be used in place of
  1456. * rcu_read_lock_sched().
  1457. *
  1458. * This means that all preempt_disable code sequences, including NMI and
  1459. * hardware-interrupt handlers, in progress on entry will have completed
  1460. * before this primitive returns. However, this does not guarantee that
  1461. * softirq handlers will have completed, since in some kernels, these
  1462. * handlers can run in process context, and can block.
  1463. *
  1464. * This primitive provides the guarantees made by the (now removed)
  1465. * synchronize_kernel() API. In contrast, synchronize_rcu() only
  1466. * guarantees that rcu_read_lock() sections will have completed.
  1467. * In "classic RCU", these two guarantees happen to be one and
  1468. * the same, but can differ in realtime RCU implementations.
  1469. */
  1470. void synchronize_sched(void)
  1471. {
  1472. if (rcu_blocking_is_gp())
  1473. return;
  1474. wait_rcu_gp(call_rcu_sched);
  1475. }
  1476. EXPORT_SYMBOL_GPL(synchronize_sched);
  1477. /**
  1478. * synchronize_rcu_bh - wait until an rcu_bh grace period has elapsed.
  1479. *
  1480. * Control will return to the caller some time after a full rcu_bh grace
  1481. * period has elapsed, in other words after all currently executing rcu_bh
  1482. * read-side critical sections have completed. RCU read-side critical
  1483. * sections are delimited by rcu_read_lock_bh() and rcu_read_unlock_bh(),
  1484. * and may be nested.
  1485. */
  1486. void synchronize_rcu_bh(void)
  1487. {
  1488. if (rcu_blocking_is_gp())
  1489. return;
  1490. wait_rcu_gp(call_rcu_bh);
  1491. }
  1492. EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
  1493. /*
  1494. * Check to see if there is any immediate RCU-related work to be done
  1495. * by the current CPU, for the specified type of RCU, returning 1 if so.
  1496. * The checks are in order of increasing expense: checks that can be
  1497. * carried out against CPU-local state are performed first. However,
  1498. * we must check for CPU stalls first, else we might not get a chance.
  1499. */
  1500. static int __rcu_pending(struct rcu_state *rsp, struct rcu_data *rdp)
  1501. {
  1502. struct rcu_node *rnp = rdp->mynode;
  1503. rdp->n_rcu_pending++;
  1504. /* Check for CPU stalls, if enabled. */
  1505. check_cpu_stall(rsp, rdp);
  1506. /* Is the RCU core waiting for a quiescent state from this CPU? */
  1507. if (rcu_scheduler_fully_active &&
  1508. rdp->qs_pending && !rdp->passed_quiesce) {
  1509. /*
  1510. * If force_quiescent_state() coming soon and this CPU
  1511. * needs a quiescent state, and this is either RCU-sched
  1512. * or RCU-bh, force a local reschedule.
  1513. */
  1514. rdp->n_rp_qs_pending++;
  1515. if (!rdp->preemptible &&
  1516. ULONG_CMP_LT(ACCESS_ONCE(rsp->jiffies_force_qs) - 1,
  1517. jiffies))
  1518. set_need_resched();
  1519. } else if (rdp->qs_pending && rdp->passed_quiesce) {
  1520. rdp->n_rp_report_qs++;
  1521. return 1;
  1522. }
  1523. /* Does this CPU have callbacks ready to invoke? */
  1524. if (cpu_has_callbacks_ready_to_invoke(rdp)) {
  1525. rdp->n_rp_cb_ready++;
  1526. return 1;
  1527. }
  1528. /* Has RCU gone idle with this CPU needing another grace period? */
  1529. if (cpu_needs_another_gp(rsp, rdp)) {
  1530. rdp->n_rp_cpu_needs_gp++;
  1531. return 1;
  1532. }
  1533. /* Has another RCU grace period completed? */
  1534. if (ACCESS_ONCE(rnp->completed) != rdp->completed) { /* outside lock */
  1535. rdp->n_rp_gp_completed++;
  1536. return 1;
  1537. }
  1538. /* Has a new RCU grace period started? */
  1539. if (ACCESS_ONCE(rnp->gpnum) != rdp->gpnum) { /* outside lock */
  1540. rdp->n_rp_gp_started++;
  1541. return 1;
  1542. }
  1543. /* Has an RCU GP gone long enough to send resched IPIs &c? */
  1544. if (rcu_gp_in_progress(rsp) &&
  1545. ULONG_CMP_LT(ACCESS_ONCE(rsp->jiffies_force_qs), jiffies)) {
  1546. rdp->n_rp_need_fqs++;
  1547. return 1;
  1548. }
  1549. /* nothing to do */
  1550. rdp->n_rp_need_nothing++;
  1551. return 0;
  1552. }
  1553. /*
  1554. * Check to see if there is any immediate RCU-related work to be done
  1555. * by the current CPU, returning 1 if so. This function is part of the
  1556. * RCU implementation; it is -not- an exported member of the RCU API.
  1557. */
  1558. static int rcu_pending(int cpu)
  1559. {
  1560. return __rcu_pending(&rcu_sched_state, &per_cpu(rcu_sched_data, cpu)) ||
  1561. __rcu_pending(&rcu_bh_state, &per_cpu(rcu_bh_data, cpu)) ||
  1562. rcu_preempt_pending(cpu);
  1563. }
  1564. /*
  1565. * Check to see if any future RCU-related work will need to be done
  1566. * by the current CPU, even if none need be done immediately, returning
  1567. * 1 if so.
  1568. */
  1569. static int rcu_needs_cpu_quick_check(int cpu)
  1570. {
  1571. /* RCU callbacks either ready or pending? */
  1572. return per_cpu(rcu_sched_data, cpu).nxtlist ||
  1573. per_cpu(rcu_bh_data, cpu).nxtlist ||
  1574. rcu_preempt_needs_cpu(cpu);
  1575. }
  1576. static DEFINE_PER_CPU(struct rcu_head, rcu_barrier_head) = {NULL};
  1577. static atomic_t rcu_barrier_cpu_count;
  1578. static DEFINE_MUTEX(rcu_barrier_mutex);
  1579. static struct completion rcu_barrier_completion;
  1580. static void rcu_barrier_callback(struct rcu_head *notused)
  1581. {
  1582. if (atomic_dec_and_test(&rcu_barrier_cpu_count))
  1583. complete(&rcu_barrier_completion);
  1584. }
  1585. /*
  1586. * Called with preemption disabled, and from cross-cpu IRQ context.
  1587. */
  1588. static void rcu_barrier_func(void *type)
  1589. {
  1590. int cpu = smp_processor_id();
  1591. struct rcu_head *head = &per_cpu(rcu_barrier_head, cpu);
  1592. void (*call_rcu_func)(struct rcu_head *head,
  1593. void (*func)(struct rcu_head *head));
  1594. atomic_inc(&rcu_barrier_cpu_count);
  1595. call_rcu_func = type;
  1596. call_rcu_func(head, rcu_barrier_callback);
  1597. }
  1598. /*
  1599. * Orchestrate the specified type of RCU barrier, waiting for all
  1600. * RCU callbacks of the specified type to complete.
  1601. */
  1602. static void _rcu_barrier(struct rcu_state *rsp,
  1603. void (*call_rcu_func)(struct rcu_head *head,
  1604. void (*func)(struct rcu_head *head)))
  1605. {
  1606. BUG_ON(in_interrupt());
  1607. /* Take mutex to serialize concurrent rcu_barrier() requests. */
  1608. mutex_lock(&rcu_barrier_mutex);
  1609. init_completion(&rcu_barrier_completion);
  1610. /*
  1611. * Initialize rcu_barrier_cpu_count to 1, then invoke
  1612. * rcu_barrier_func() on each CPU, so that each CPU also has
  1613. * incremented rcu_barrier_cpu_count. Only then is it safe to
  1614. * decrement rcu_barrier_cpu_count -- otherwise the first CPU
  1615. * might complete its grace period before all of the other CPUs
  1616. * did their increment, causing this function to return too
  1617. * early. Note that on_each_cpu() disables irqs, which prevents
  1618. * any CPUs from coming online or going offline until each online
  1619. * CPU has queued its RCU-barrier callback.
  1620. */
  1621. atomic_set(&rcu_barrier_cpu_count, 1);
  1622. on_each_cpu(rcu_barrier_func, (void *)call_rcu_func, 1);
  1623. if (atomic_dec_and_test(&rcu_barrier_cpu_count))
  1624. complete(&rcu_barrier_completion);
  1625. wait_for_completion(&rcu_barrier_completion);
  1626. mutex_unlock(&rcu_barrier_mutex);
  1627. }
  1628. /**
  1629. * rcu_barrier_bh - Wait until all in-flight call_rcu_bh() callbacks complete.
  1630. */
  1631. void rcu_barrier_bh(void)
  1632. {
  1633. _rcu_barrier(&rcu_bh_state, call_rcu_bh);
  1634. }
  1635. EXPORT_SYMBOL_GPL(rcu_barrier_bh);
  1636. /**
  1637. * rcu_barrier_sched - Wait for in-flight call_rcu_sched() callbacks.
  1638. */
  1639. void rcu_barrier_sched(void)
  1640. {
  1641. _rcu_barrier(&rcu_sched_state, call_rcu_sched);
  1642. }
  1643. EXPORT_SYMBOL_GPL(rcu_barrier_sched);
  1644. /*
  1645. * Do boot-time initialization of a CPU's per-CPU RCU data.
  1646. */
  1647. static void __init
  1648. rcu_boot_init_percpu_data(int cpu, struct rcu_state *rsp)
  1649. {
  1650. unsigned long flags;
  1651. int i;
  1652. struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
  1653. struct rcu_node *rnp = rcu_get_root(rsp);
  1654. /* Set up local state, ensuring consistent view of global state. */
  1655. raw_spin_lock_irqsave(&rnp->lock, flags);
  1656. rdp->grpmask = 1UL << (cpu - rdp->mynode->grplo);
  1657. rdp->nxtlist = NULL;
  1658. for (i = 0; i < RCU_NEXT_SIZE; i++)
  1659. rdp->nxttail[i] = &rdp->nxtlist;
  1660. rdp->qlen = 0;
  1661. #ifdef CONFIG_NO_HZ
  1662. rdp->dynticks = &per_cpu(rcu_dynticks, cpu);
  1663. #endif /* #ifdef CONFIG_NO_HZ */
  1664. rdp->cpu = cpu;
  1665. rdp->rsp = rsp;
  1666. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1667. }
  1668. /*
  1669. * Initialize a CPU's per-CPU RCU data. Note that only one online or
  1670. * offline event can be happening at a given time. Note also that we
  1671. * can accept some slop in the rsp->completed access due to the fact
  1672. * that this CPU cannot possibly have any RCU callbacks in flight yet.
  1673. */
  1674. static void __cpuinit
  1675. rcu_init_percpu_data(int cpu, struct rcu_state *rsp, int preemptible)
  1676. {
  1677. unsigned long flags;
  1678. unsigned long mask;
  1679. struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
  1680. struct rcu_node *rnp = rcu_get_root(rsp);
  1681. /* Set up local state, ensuring consistent view of global state. */
  1682. raw_spin_lock_irqsave(&rnp->lock, flags);
  1683. rdp->beenonline = 1; /* We have now been online. */
  1684. rdp->preemptible = preemptible;
  1685. rdp->qlen_last_fqs_check = 0;
  1686. rdp->n_force_qs_snap = rsp->n_force_qs;
  1687. rdp->blimit = blimit;
  1688. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  1689. /*
  1690. * A new grace period might start here. If so, we won't be part
  1691. * of it, but that is OK, as we are currently in a quiescent state.
  1692. */
  1693. /* Exclude any attempts to start a new GP on large systems. */
  1694. raw_spin_lock(&rsp->onofflock); /* irqs already disabled. */
  1695. /* Add CPU to rcu_node bitmasks. */
  1696. rnp = rdp->mynode;
  1697. mask = rdp->grpmask;
  1698. do {
  1699. /* Exclude any attempts to start a new GP on small systems. */
  1700. raw_spin_lock(&rnp->lock); /* irqs already disabled. */
  1701. rnp->qsmaskinit |= mask;
  1702. mask = rnp->grpmask;
  1703. if (rnp == rdp->mynode) {
  1704. /*
  1705. * If there is a grace period in progress, we will
  1706. * set up to wait for it next time we run the
  1707. * RCU core code.
  1708. */
  1709. rdp->gpnum = rnp->completed;
  1710. rdp->completed = rnp->completed;
  1711. rdp->passed_quiesce = 0;
  1712. rdp->qs_pending = 0;
  1713. rdp->passed_quiesce_gpnum = rnp->gpnum - 1;
  1714. trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpuonl");
  1715. }
  1716. raw_spin_unlock(&rnp->lock); /* irqs already disabled. */
  1717. rnp = rnp->parent;
  1718. } while (rnp != NULL && !(rnp->qsmaskinit & mask));
  1719. raw_spin_unlock_irqrestore(&rsp->onofflock, flags);
  1720. }
  1721. static void __cpuinit rcu_prepare_cpu(int cpu)
  1722. {
  1723. rcu_init_percpu_data(cpu, &rcu_sched_state, 0);
  1724. rcu_init_percpu_data(cpu, &rcu_bh_state, 0);
  1725. rcu_preempt_init_percpu_data(cpu);
  1726. }
  1727. /*
  1728. * Handle CPU online/offline notification events.
  1729. */
  1730. static int __cpuinit rcu_cpu_notify(struct notifier_block *self,
  1731. unsigned long action, void *hcpu)
  1732. {
  1733. long cpu = (long)hcpu;
  1734. struct rcu_data *rdp = per_cpu_ptr(rcu_state->rda, cpu);
  1735. struct rcu_node *rnp = rdp->mynode;
  1736. trace_rcu_utilization("Start CPU hotplug");
  1737. switch (action) {
  1738. case CPU_UP_PREPARE:
  1739. case CPU_UP_PREPARE_FROZEN:
  1740. rcu_prepare_cpu(cpu);
  1741. rcu_prepare_kthreads(cpu);
  1742. break;
  1743. case CPU_ONLINE:
  1744. case CPU_DOWN_FAILED:
  1745. rcu_node_kthread_setaffinity(rnp, -1);
  1746. rcu_cpu_kthread_setrt(cpu, 1);
  1747. break;
  1748. case CPU_DOWN_PREPARE:
  1749. rcu_node_kthread_setaffinity(rnp, cpu);
  1750. rcu_cpu_kthread_setrt(cpu, 0);
  1751. break;
  1752. case CPU_DYING:
  1753. case CPU_DYING_FROZEN:
  1754. /*
  1755. * The whole machine is "stopped" except this CPU, so we can
  1756. * touch any data without introducing corruption. We send the
  1757. * dying CPU's callbacks to an arbitrarily chosen online CPU.
  1758. */
  1759. rcu_send_cbs_to_online(&rcu_bh_state);
  1760. rcu_send_cbs_to_online(&rcu_sched_state);
  1761. rcu_preempt_send_cbs_to_online();
  1762. break;
  1763. case CPU_DEAD:
  1764. case CPU_DEAD_FROZEN:
  1765. case CPU_UP_CANCELED:
  1766. case CPU_UP_CANCELED_FROZEN:
  1767. rcu_offline_cpu(cpu);
  1768. break;
  1769. default:
  1770. break;
  1771. }
  1772. trace_rcu_utilization("End CPU hotplug");
  1773. return NOTIFY_OK;
  1774. }
  1775. /*
  1776. * This function is invoked towards the end of the scheduler's initialization
  1777. * process. Before this is called, the idle task might contain
  1778. * RCU read-side critical sections (during which time, this idle
  1779. * task is booting the system). After this function is called, the
  1780. * idle tasks are prohibited from containing RCU read-side critical
  1781. * sections. This function also enables RCU lockdep checking.
  1782. */
  1783. void rcu_scheduler_starting(void)
  1784. {
  1785. WARN_ON(num_online_cpus() != 1);
  1786. WARN_ON(nr_context_switches() > 0);
  1787. rcu_scheduler_active = 1;
  1788. }
  1789. /*
  1790. * Compute the per-level fanout, either using the exact fanout specified
  1791. * or balancing the tree, depending on CONFIG_RCU_FANOUT_EXACT.
  1792. */
  1793. #ifdef CONFIG_RCU_FANOUT_EXACT
  1794. static void __init rcu_init_levelspread(struct rcu_state *rsp)
  1795. {
  1796. int i;
  1797. for (i = NUM_RCU_LVLS - 1; i > 0; i--)
  1798. rsp->levelspread[i] = CONFIG_RCU_FANOUT;
  1799. rsp->levelspread[0] = RCU_FANOUT_LEAF;
  1800. }
  1801. #else /* #ifdef CONFIG_RCU_FANOUT_EXACT */
  1802. static void __init rcu_init_levelspread(struct rcu_state *rsp)
  1803. {
  1804. int ccur;
  1805. int cprv;
  1806. int i;
  1807. cprv = NR_CPUS;
  1808. for (i = NUM_RCU_LVLS - 1; i >= 0; i--) {
  1809. ccur = rsp->levelcnt[i];
  1810. rsp->levelspread[i] = (cprv + ccur - 1) / ccur;
  1811. cprv = ccur;
  1812. }
  1813. }
  1814. #endif /* #else #ifdef CONFIG_RCU_FANOUT_EXACT */
  1815. /*
  1816. * Helper function for rcu_init() that initializes one rcu_state structure.
  1817. */
  1818. static void __init rcu_init_one(struct rcu_state *rsp,
  1819. struct rcu_data __percpu *rda)
  1820. {
  1821. static char *buf[] = { "rcu_node_level_0",
  1822. "rcu_node_level_1",
  1823. "rcu_node_level_2",
  1824. "rcu_node_level_3" }; /* Match MAX_RCU_LVLS */
  1825. int cpustride = 1;
  1826. int i;
  1827. int j;
  1828. struct rcu_node *rnp;
  1829. BUILD_BUG_ON(MAX_RCU_LVLS > ARRAY_SIZE(buf)); /* Fix buf[] init! */
  1830. /* Initialize the level-tracking arrays. */
  1831. for (i = 1; i < NUM_RCU_LVLS; i++)
  1832. rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
  1833. rcu_init_levelspread(rsp);
  1834. /* Initialize the elements themselves, starting from the leaves. */
  1835. for (i = NUM_RCU_LVLS - 1; i >= 0; i--) {
  1836. cpustride *= rsp->levelspread[i];
  1837. rnp = rsp->level[i];
  1838. for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) {
  1839. raw_spin_lock_init(&rnp->lock);
  1840. lockdep_set_class_and_name(&rnp->lock,
  1841. &rcu_node_class[i], buf[i]);
  1842. rnp->gpnum = 0;
  1843. rnp->qsmask = 0;
  1844. rnp->qsmaskinit = 0;
  1845. rnp->grplo = j * cpustride;
  1846. rnp->grphi = (j + 1) * cpustride - 1;
  1847. if (rnp->grphi >= NR_CPUS)
  1848. rnp->grphi = NR_CPUS - 1;
  1849. if (i == 0) {
  1850. rnp->grpnum = 0;
  1851. rnp->grpmask = 0;
  1852. rnp->parent = NULL;
  1853. } else {
  1854. rnp->grpnum = j % rsp->levelspread[i - 1];
  1855. rnp->grpmask = 1UL << rnp->grpnum;
  1856. rnp->parent = rsp->level[i - 1] +
  1857. j / rsp->levelspread[i - 1];
  1858. }
  1859. rnp->level = i;
  1860. INIT_LIST_HEAD(&rnp->blkd_tasks);
  1861. }
  1862. }
  1863. rsp->rda = rda;
  1864. rnp = rsp->level[NUM_RCU_LVLS - 1];
  1865. for_each_possible_cpu(i) {
  1866. while (i > rnp->grphi)
  1867. rnp++;
  1868. per_cpu_ptr(rsp->rda, i)->mynode = rnp;
  1869. rcu_boot_init_percpu_data(i, rsp);
  1870. }
  1871. }
  1872. void __init rcu_init(void)
  1873. {
  1874. int cpu;
  1875. rcu_bootup_announce();
  1876. rcu_init_one(&rcu_sched_state, &rcu_sched_data);
  1877. rcu_init_one(&rcu_bh_state, &rcu_bh_data);
  1878. __rcu_init_preempt();
  1879. open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
  1880. /*
  1881. * We don't need protection against CPU-hotplug here because
  1882. * this is called early in boot, before either interrupts
  1883. * or the scheduler are operational.
  1884. */
  1885. cpu_notifier(rcu_cpu_notify, 0);
  1886. for_each_online_cpu(cpu)
  1887. rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
  1888. check_cpu_stall_init();
  1889. }
  1890. #include "rcutree_plugin.h"