rcutree.c 103 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343
  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/export.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 <linux/delay.h>
  54. #include <linux/stop_machine.h>
  55. #include <linux/random.h>
  56. #include "rcutree.h"
  57. #include <trace/events/rcu.h>
  58. #include "rcu.h"
  59. /* Data structures. */
  60. static struct lock_class_key rcu_node_class[RCU_NUM_LVLS];
  61. static struct lock_class_key rcu_fqs_class[RCU_NUM_LVLS];
  62. #define RCU_STATE_INITIALIZER(sname, sabbr, cr) { \
  63. .level = { &sname##_state.node[0] }, \
  64. .call = cr, \
  65. .fqs_state = RCU_GP_IDLE, \
  66. .gpnum = 0UL - 300UL, \
  67. .completed = 0UL - 300UL, \
  68. .orphan_lock = __RAW_SPIN_LOCK_UNLOCKED(&sname##_state.orphan_lock), \
  69. .orphan_nxttail = &sname##_state.orphan_nxtlist, \
  70. .orphan_donetail = &sname##_state.orphan_donelist, \
  71. .barrier_mutex = __MUTEX_INITIALIZER(sname##_state.barrier_mutex), \
  72. .onoff_mutex = __MUTEX_INITIALIZER(sname##_state.onoff_mutex), \
  73. .name = #sname, \
  74. .abbr = sabbr, \
  75. }
  76. struct rcu_state rcu_sched_state =
  77. RCU_STATE_INITIALIZER(rcu_sched, 's', call_rcu_sched);
  78. DEFINE_PER_CPU(struct rcu_data, rcu_sched_data);
  79. struct rcu_state rcu_bh_state = RCU_STATE_INITIALIZER(rcu_bh, 'b', call_rcu_bh);
  80. DEFINE_PER_CPU(struct rcu_data, rcu_bh_data);
  81. static struct rcu_state *rcu_state;
  82. LIST_HEAD(rcu_struct_flavors);
  83. /* Increase (but not decrease) the CONFIG_RCU_FANOUT_LEAF at boot time. */
  84. static int rcu_fanout_leaf = CONFIG_RCU_FANOUT_LEAF;
  85. module_param(rcu_fanout_leaf, int, 0444);
  86. int rcu_num_lvls __read_mostly = RCU_NUM_LVLS;
  87. static int num_rcu_lvl[] = { /* Number of rcu_nodes at specified level. */
  88. NUM_RCU_LVL_0,
  89. NUM_RCU_LVL_1,
  90. NUM_RCU_LVL_2,
  91. NUM_RCU_LVL_3,
  92. NUM_RCU_LVL_4,
  93. };
  94. int rcu_num_nodes __read_mostly = NUM_RCU_NODES; /* Total # rcu_nodes in use. */
  95. /*
  96. * The rcu_scheduler_active variable transitions from zero to one just
  97. * before the first task is spawned. So when this variable is zero, RCU
  98. * can assume that there is but one task, allowing RCU to (for example)
  99. * optimize synchronize_sched() to a simple barrier(). When this variable
  100. * is one, RCU must actually do all the hard work required to detect real
  101. * grace periods. This variable is also used to suppress boot-time false
  102. * positives from lockdep-RCU error checking.
  103. */
  104. int rcu_scheduler_active __read_mostly;
  105. EXPORT_SYMBOL_GPL(rcu_scheduler_active);
  106. /*
  107. * The rcu_scheduler_fully_active variable transitions from zero to one
  108. * during the early_initcall() processing, which is after the scheduler
  109. * is capable of creating new tasks. So RCU processing (for example,
  110. * creating tasks for RCU priority boosting) must be delayed until after
  111. * rcu_scheduler_fully_active transitions from zero to one. We also
  112. * currently delay invocation of any RCU callbacks until after this point.
  113. *
  114. * It might later prove better for people registering RCU callbacks during
  115. * early boot to take responsibility for these callbacks, but one step at
  116. * a time.
  117. */
  118. static int rcu_scheduler_fully_active __read_mostly;
  119. #ifdef CONFIG_RCU_BOOST
  120. /*
  121. * Control variables for per-CPU and per-rcu_node kthreads. These
  122. * handle all flavors of RCU.
  123. */
  124. static DEFINE_PER_CPU(struct task_struct *, rcu_cpu_kthread_task);
  125. DEFINE_PER_CPU(unsigned int, rcu_cpu_kthread_status);
  126. DEFINE_PER_CPU(unsigned int, rcu_cpu_kthread_loops);
  127. DEFINE_PER_CPU(char, rcu_cpu_has_work);
  128. #endif /* #ifdef CONFIG_RCU_BOOST */
  129. static void rcu_boost_kthread_setaffinity(struct rcu_node *rnp, int outgoingcpu);
  130. static void invoke_rcu_core(void);
  131. static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp);
  132. /*
  133. * Track the rcutorture test sequence number and the update version
  134. * number within a given test. The rcutorture_testseq is incremented
  135. * on every rcutorture module load and unload, so has an odd value
  136. * when a test is running. The rcutorture_vernum is set to zero
  137. * when rcutorture starts and is incremented on each rcutorture update.
  138. * These variables enable correlating rcutorture output with the
  139. * RCU tracing information.
  140. */
  141. unsigned long rcutorture_testseq;
  142. unsigned long rcutorture_vernum;
  143. /*
  144. * Return true if an RCU grace period is in progress. The ACCESS_ONCE()s
  145. * permit this function to be invoked without holding the root rcu_node
  146. * structure's ->lock, but of course results can be subject to change.
  147. */
  148. static int rcu_gp_in_progress(struct rcu_state *rsp)
  149. {
  150. return ACCESS_ONCE(rsp->completed) != ACCESS_ONCE(rsp->gpnum);
  151. }
  152. /*
  153. * Note a quiescent state. Because we do not need to know
  154. * how many quiescent states passed, just if there was at least
  155. * one since the start of the grace period, this just sets a flag.
  156. * The caller must have disabled preemption.
  157. */
  158. void rcu_sched_qs(int cpu)
  159. {
  160. struct rcu_data *rdp = &per_cpu(rcu_sched_data, cpu);
  161. if (rdp->passed_quiesce == 0)
  162. trace_rcu_grace_period("rcu_sched", rdp->gpnum, "cpuqs");
  163. rdp->passed_quiesce = 1;
  164. }
  165. void rcu_bh_qs(int cpu)
  166. {
  167. struct rcu_data *rdp = &per_cpu(rcu_bh_data, cpu);
  168. if (rdp->passed_quiesce == 0)
  169. trace_rcu_grace_period("rcu_bh", rdp->gpnum, "cpuqs");
  170. rdp->passed_quiesce = 1;
  171. }
  172. /*
  173. * Note a context switch. This is a quiescent state for RCU-sched,
  174. * and requires special handling for preemptible RCU.
  175. * The caller must have disabled preemption.
  176. */
  177. void rcu_note_context_switch(int cpu)
  178. {
  179. trace_rcu_utilization("Start context switch");
  180. rcu_sched_qs(cpu);
  181. rcu_preempt_note_context_switch(cpu);
  182. trace_rcu_utilization("End context switch");
  183. }
  184. EXPORT_SYMBOL_GPL(rcu_note_context_switch);
  185. DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
  186. .dynticks_nesting = DYNTICK_TASK_EXIT_IDLE,
  187. .dynticks = ATOMIC_INIT(1),
  188. };
  189. static long blimit = 10; /* Maximum callbacks per rcu_do_batch. */
  190. static long qhimark = 10000; /* If this many pending, ignore blimit. */
  191. static long qlowmark = 100; /* Once only this many pending, use blimit. */
  192. module_param(blimit, long, 0444);
  193. module_param(qhimark, long, 0444);
  194. module_param(qlowmark, long, 0444);
  195. static ulong jiffies_till_first_fqs = RCU_JIFFIES_TILL_FORCE_QS;
  196. static ulong jiffies_till_next_fqs = RCU_JIFFIES_TILL_FORCE_QS;
  197. module_param(jiffies_till_first_fqs, ulong, 0644);
  198. module_param(jiffies_till_next_fqs, ulong, 0644);
  199. static void rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
  200. struct rcu_data *rdp);
  201. static void force_qs_rnp(struct rcu_state *rsp, int (*f)(struct rcu_data *));
  202. static void force_quiescent_state(struct rcu_state *rsp);
  203. static int rcu_pending(int cpu);
  204. /*
  205. * Return the number of RCU-sched batches processed thus far for debug & stats.
  206. */
  207. long rcu_batches_completed_sched(void)
  208. {
  209. return rcu_sched_state.completed;
  210. }
  211. EXPORT_SYMBOL_GPL(rcu_batches_completed_sched);
  212. /*
  213. * Return the number of RCU BH batches processed thus far for debug & stats.
  214. */
  215. long rcu_batches_completed_bh(void)
  216. {
  217. return rcu_bh_state.completed;
  218. }
  219. EXPORT_SYMBOL_GPL(rcu_batches_completed_bh);
  220. /*
  221. * Force a quiescent state for RCU BH.
  222. */
  223. void rcu_bh_force_quiescent_state(void)
  224. {
  225. force_quiescent_state(&rcu_bh_state);
  226. }
  227. EXPORT_SYMBOL_GPL(rcu_bh_force_quiescent_state);
  228. /*
  229. * Record the number of times rcutorture tests have been initiated and
  230. * terminated. This information allows the debugfs tracing stats to be
  231. * correlated to the rcutorture messages, even when the rcutorture module
  232. * is being repeatedly loaded and unloaded. In other words, we cannot
  233. * store this state in rcutorture itself.
  234. */
  235. void rcutorture_record_test_transition(void)
  236. {
  237. rcutorture_testseq++;
  238. rcutorture_vernum = 0;
  239. }
  240. EXPORT_SYMBOL_GPL(rcutorture_record_test_transition);
  241. /*
  242. * Record the number of writer passes through the current rcutorture test.
  243. * This is also used to correlate debugfs tracing stats with the rcutorture
  244. * messages.
  245. */
  246. void rcutorture_record_progress(unsigned long vernum)
  247. {
  248. rcutorture_vernum++;
  249. }
  250. EXPORT_SYMBOL_GPL(rcutorture_record_progress);
  251. /*
  252. * Force a quiescent state for RCU-sched.
  253. */
  254. void rcu_sched_force_quiescent_state(void)
  255. {
  256. force_quiescent_state(&rcu_sched_state);
  257. }
  258. EXPORT_SYMBOL_GPL(rcu_sched_force_quiescent_state);
  259. /*
  260. * Does the CPU have callbacks ready to be invoked?
  261. */
  262. static int
  263. cpu_has_callbacks_ready_to_invoke(struct rcu_data *rdp)
  264. {
  265. return &rdp->nxtlist != rdp->nxttail[RCU_DONE_TAIL] &&
  266. rdp->nxttail[RCU_DONE_TAIL] != NULL;
  267. }
  268. /*
  269. * Does the current CPU require a not-yet-started grace period?
  270. * The caller must have disabled interrupts to prevent races with
  271. * normal callback registry.
  272. */
  273. static int
  274. cpu_needs_another_gp(struct rcu_state *rsp, struct rcu_data *rdp)
  275. {
  276. int i;
  277. if (rcu_gp_in_progress(rsp))
  278. return 0; /* No, a grace period is already in progress. */
  279. if (rcu_nocb_needs_gp(rsp))
  280. return 1; /* Yes, a no-CBs CPU needs one. */
  281. if (!rdp->nxttail[RCU_NEXT_TAIL])
  282. return 0; /* No, this is a no-CBs (or offline) CPU. */
  283. if (*rdp->nxttail[RCU_NEXT_READY_TAIL])
  284. return 1; /* Yes, this CPU has newly registered callbacks. */
  285. for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++)
  286. if (rdp->nxttail[i - 1] != rdp->nxttail[i] &&
  287. ULONG_CMP_LT(ACCESS_ONCE(rsp->completed),
  288. rdp->nxtcompleted[i]))
  289. return 1; /* Yes, CBs for future grace period. */
  290. return 0; /* No grace period needed. */
  291. }
  292. /*
  293. * Return the root node of the specified rcu_state structure.
  294. */
  295. static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
  296. {
  297. return &rsp->node[0];
  298. }
  299. /*
  300. * rcu_eqs_enter_common - current CPU is moving towards extended quiescent state
  301. *
  302. * If the new value of the ->dynticks_nesting counter now is zero,
  303. * we really have entered idle, and must do the appropriate accounting.
  304. * The caller must have disabled interrupts.
  305. */
  306. static void rcu_eqs_enter_common(struct rcu_dynticks *rdtp, long long oldval,
  307. bool user)
  308. {
  309. trace_rcu_dyntick("Start", oldval, rdtp->dynticks_nesting);
  310. if (!user && !is_idle_task(current)) {
  311. struct task_struct *idle = idle_task(smp_processor_id());
  312. trace_rcu_dyntick("Error on entry: not idle task", oldval, 0);
  313. ftrace_dump(DUMP_ORIG);
  314. WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s",
  315. current->pid, current->comm,
  316. idle->pid, idle->comm); /* must be idle task! */
  317. }
  318. rcu_prepare_for_idle(smp_processor_id());
  319. /* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
  320. smp_mb__before_atomic_inc(); /* See above. */
  321. atomic_inc(&rdtp->dynticks);
  322. smp_mb__after_atomic_inc(); /* Force ordering with next sojourn. */
  323. WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
  324. /*
  325. * It is illegal to enter an extended quiescent state while
  326. * in an RCU read-side critical section.
  327. */
  328. rcu_lockdep_assert(!lock_is_held(&rcu_lock_map),
  329. "Illegal idle entry in RCU read-side critical section.");
  330. rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map),
  331. "Illegal idle entry in RCU-bh read-side critical section.");
  332. rcu_lockdep_assert(!lock_is_held(&rcu_sched_lock_map),
  333. "Illegal idle entry in RCU-sched read-side critical section.");
  334. }
  335. /*
  336. * Enter an RCU extended quiescent state, which can be either the
  337. * idle loop or adaptive-tickless usermode execution.
  338. */
  339. static void rcu_eqs_enter(bool user)
  340. {
  341. long long oldval;
  342. struct rcu_dynticks *rdtp;
  343. rdtp = &__get_cpu_var(rcu_dynticks);
  344. oldval = rdtp->dynticks_nesting;
  345. WARN_ON_ONCE((oldval & DYNTICK_TASK_NEST_MASK) == 0);
  346. if ((oldval & DYNTICK_TASK_NEST_MASK) == DYNTICK_TASK_NEST_VALUE)
  347. rdtp->dynticks_nesting = 0;
  348. else
  349. rdtp->dynticks_nesting -= DYNTICK_TASK_NEST_VALUE;
  350. rcu_eqs_enter_common(rdtp, oldval, user);
  351. }
  352. /**
  353. * rcu_idle_enter - inform RCU that current CPU is entering idle
  354. *
  355. * Enter idle mode, in other words, -leave- the mode in which RCU
  356. * read-side critical sections can occur. (Though RCU read-side
  357. * critical sections can occur in irq handlers in idle, a possibility
  358. * handled by irq_enter() and irq_exit().)
  359. *
  360. * We crowbar the ->dynticks_nesting field to zero to allow for
  361. * the possibility of usermode upcalls having messed up our count
  362. * of interrupt nesting level during the prior busy period.
  363. */
  364. void rcu_idle_enter(void)
  365. {
  366. unsigned long flags;
  367. local_irq_save(flags);
  368. rcu_eqs_enter(false);
  369. local_irq_restore(flags);
  370. }
  371. EXPORT_SYMBOL_GPL(rcu_idle_enter);
  372. #ifdef CONFIG_RCU_USER_QS
  373. /**
  374. * rcu_user_enter - inform RCU that we are resuming userspace.
  375. *
  376. * Enter RCU idle mode right before resuming userspace. No use of RCU
  377. * is permitted between this call and rcu_user_exit(). This way the
  378. * CPU doesn't need to maintain the tick for RCU maintenance purposes
  379. * when the CPU runs in userspace.
  380. */
  381. void rcu_user_enter(void)
  382. {
  383. rcu_eqs_enter(1);
  384. }
  385. /**
  386. * rcu_user_enter_after_irq - inform RCU that we are going to resume userspace
  387. * after the current irq returns.
  388. *
  389. * This is similar to rcu_user_enter() but in the context of a non-nesting
  390. * irq. After this call, RCU enters into idle mode when the interrupt
  391. * returns.
  392. */
  393. void rcu_user_enter_after_irq(void)
  394. {
  395. unsigned long flags;
  396. struct rcu_dynticks *rdtp;
  397. local_irq_save(flags);
  398. rdtp = &__get_cpu_var(rcu_dynticks);
  399. /* Ensure this irq is interrupting a non-idle RCU state. */
  400. WARN_ON_ONCE(!(rdtp->dynticks_nesting & DYNTICK_TASK_MASK));
  401. rdtp->dynticks_nesting = 1;
  402. local_irq_restore(flags);
  403. }
  404. #endif /* CONFIG_RCU_USER_QS */
  405. /**
  406. * rcu_irq_exit - inform RCU that current CPU is exiting irq towards idle
  407. *
  408. * Exit from an interrupt handler, which might possibly result in entering
  409. * idle mode, in other words, leaving the mode in which read-side critical
  410. * sections can occur.
  411. *
  412. * This code assumes that the idle loop never does anything that might
  413. * result in unbalanced calls to irq_enter() and irq_exit(). If your
  414. * architecture violates this assumption, RCU will give you what you
  415. * deserve, good and hard. But very infrequently and irreproducibly.
  416. *
  417. * Use things like work queues to work around this limitation.
  418. *
  419. * You have been warned.
  420. */
  421. void rcu_irq_exit(void)
  422. {
  423. unsigned long flags;
  424. long long oldval;
  425. struct rcu_dynticks *rdtp;
  426. local_irq_save(flags);
  427. rdtp = &__get_cpu_var(rcu_dynticks);
  428. oldval = rdtp->dynticks_nesting;
  429. rdtp->dynticks_nesting--;
  430. WARN_ON_ONCE(rdtp->dynticks_nesting < 0);
  431. if (rdtp->dynticks_nesting)
  432. trace_rcu_dyntick("--=", oldval, rdtp->dynticks_nesting);
  433. else
  434. rcu_eqs_enter_common(rdtp, oldval, true);
  435. local_irq_restore(flags);
  436. }
  437. /*
  438. * rcu_eqs_exit_common - current CPU moving away from extended quiescent state
  439. *
  440. * If the new value of the ->dynticks_nesting counter was previously zero,
  441. * we really have exited idle, and must do the appropriate accounting.
  442. * The caller must have disabled interrupts.
  443. */
  444. static void rcu_eqs_exit_common(struct rcu_dynticks *rdtp, long long oldval,
  445. int user)
  446. {
  447. smp_mb__before_atomic_inc(); /* Force ordering w/previous sojourn. */
  448. atomic_inc(&rdtp->dynticks);
  449. /* CPUs seeing atomic_inc() must see later RCU read-side crit sects */
  450. smp_mb__after_atomic_inc(); /* See above. */
  451. WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
  452. rcu_cleanup_after_idle(smp_processor_id());
  453. trace_rcu_dyntick("End", oldval, rdtp->dynticks_nesting);
  454. if (!user && !is_idle_task(current)) {
  455. struct task_struct *idle = idle_task(smp_processor_id());
  456. trace_rcu_dyntick("Error on exit: not idle task",
  457. oldval, rdtp->dynticks_nesting);
  458. ftrace_dump(DUMP_ORIG);
  459. WARN_ONCE(1, "Current pid: %d comm: %s / Idle pid: %d comm: %s",
  460. current->pid, current->comm,
  461. idle->pid, idle->comm); /* must be idle task! */
  462. }
  463. }
  464. /*
  465. * Exit an RCU extended quiescent state, which can be either the
  466. * idle loop or adaptive-tickless usermode execution.
  467. */
  468. static void rcu_eqs_exit(bool user)
  469. {
  470. struct rcu_dynticks *rdtp;
  471. long long oldval;
  472. rdtp = &__get_cpu_var(rcu_dynticks);
  473. oldval = rdtp->dynticks_nesting;
  474. WARN_ON_ONCE(oldval < 0);
  475. if (oldval & DYNTICK_TASK_NEST_MASK)
  476. rdtp->dynticks_nesting += DYNTICK_TASK_NEST_VALUE;
  477. else
  478. rdtp->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
  479. rcu_eqs_exit_common(rdtp, oldval, user);
  480. }
  481. /**
  482. * rcu_idle_exit - inform RCU that current CPU is leaving idle
  483. *
  484. * Exit idle mode, in other words, -enter- the mode in which RCU
  485. * read-side critical sections can occur.
  486. *
  487. * We crowbar the ->dynticks_nesting field to DYNTICK_TASK_NEST to
  488. * allow for the possibility of usermode upcalls messing up our count
  489. * of interrupt nesting level during the busy period that is just
  490. * now starting.
  491. */
  492. void rcu_idle_exit(void)
  493. {
  494. unsigned long flags;
  495. local_irq_save(flags);
  496. rcu_eqs_exit(false);
  497. local_irq_restore(flags);
  498. }
  499. EXPORT_SYMBOL_GPL(rcu_idle_exit);
  500. #ifdef CONFIG_RCU_USER_QS
  501. /**
  502. * rcu_user_exit - inform RCU that we are exiting userspace.
  503. *
  504. * Exit RCU idle mode while entering the kernel because it can
  505. * run a RCU read side critical section anytime.
  506. */
  507. void rcu_user_exit(void)
  508. {
  509. rcu_eqs_exit(1);
  510. }
  511. /**
  512. * rcu_user_exit_after_irq - inform RCU that we won't resume to userspace
  513. * idle mode after the current non-nesting irq returns.
  514. *
  515. * This is similar to rcu_user_exit() but in the context of an irq.
  516. * This is called when the irq has interrupted a userspace RCU idle mode
  517. * context. When the current non-nesting interrupt returns after this call,
  518. * the CPU won't restore the RCU idle mode.
  519. */
  520. void rcu_user_exit_after_irq(void)
  521. {
  522. unsigned long flags;
  523. struct rcu_dynticks *rdtp;
  524. local_irq_save(flags);
  525. rdtp = &__get_cpu_var(rcu_dynticks);
  526. /* Ensure we are interrupting an RCU idle mode. */
  527. WARN_ON_ONCE(rdtp->dynticks_nesting & DYNTICK_TASK_NEST_MASK);
  528. rdtp->dynticks_nesting += DYNTICK_TASK_EXIT_IDLE;
  529. local_irq_restore(flags);
  530. }
  531. #endif /* CONFIG_RCU_USER_QS */
  532. /**
  533. * rcu_irq_enter - inform RCU that current CPU is entering irq away from idle
  534. *
  535. * Enter an interrupt handler, which might possibly result in exiting
  536. * idle mode, in other words, entering the mode in which read-side critical
  537. * sections can occur.
  538. *
  539. * Note that the Linux kernel is fully capable of entering an interrupt
  540. * handler that it never exits, for example when doing upcalls to
  541. * user mode! This code assumes that the idle loop never does upcalls to
  542. * user mode. If your architecture does do upcalls from the idle loop (or
  543. * does anything else that results in unbalanced calls to the irq_enter()
  544. * and irq_exit() functions), RCU will give you what you deserve, good
  545. * and hard. But very infrequently and irreproducibly.
  546. *
  547. * Use things like work queues to work around this limitation.
  548. *
  549. * You have been warned.
  550. */
  551. void rcu_irq_enter(void)
  552. {
  553. unsigned long flags;
  554. struct rcu_dynticks *rdtp;
  555. long long oldval;
  556. local_irq_save(flags);
  557. rdtp = &__get_cpu_var(rcu_dynticks);
  558. oldval = rdtp->dynticks_nesting;
  559. rdtp->dynticks_nesting++;
  560. WARN_ON_ONCE(rdtp->dynticks_nesting == 0);
  561. if (oldval)
  562. trace_rcu_dyntick("++=", oldval, rdtp->dynticks_nesting);
  563. else
  564. rcu_eqs_exit_common(rdtp, oldval, true);
  565. local_irq_restore(flags);
  566. }
  567. /**
  568. * rcu_nmi_enter - inform RCU of entry to NMI context
  569. *
  570. * If the CPU was idle with dynamic ticks active, and there is no
  571. * irq handler running, this updates rdtp->dynticks_nmi to let the
  572. * RCU grace-period handling know that the CPU is active.
  573. */
  574. void rcu_nmi_enter(void)
  575. {
  576. struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
  577. if (rdtp->dynticks_nmi_nesting == 0 &&
  578. (atomic_read(&rdtp->dynticks) & 0x1))
  579. return;
  580. rdtp->dynticks_nmi_nesting++;
  581. smp_mb__before_atomic_inc(); /* Force delay from prior write. */
  582. atomic_inc(&rdtp->dynticks);
  583. /* CPUs seeing atomic_inc() must see later RCU read-side crit sects */
  584. smp_mb__after_atomic_inc(); /* See above. */
  585. WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks) & 0x1));
  586. }
  587. /**
  588. * rcu_nmi_exit - inform RCU of exit from NMI context
  589. *
  590. * If the CPU was idle with dynamic ticks active, and there is no
  591. * irq handler running, this updates rdtp->dynticks_nmi to let the
  592. * RCU grace-period handling know that the CPU is no longer active.
  593. */
  594. void rcu_nmi_exit(void)
  595. {
  596. struct rcu_dynticks *rdtp = &__get_cpu_var(rcu_dynticks);
  597. if (rdtp->dynticks_nmi_nesting == 0 ||
  598. --rdtp->dynticks_nmi_nesting != 0)
  599. return;
  600. /* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */
  601. smp_mb__before_atomic_inc(); /* See above. */
  602. atomic_inc(&rdtp->dynticks);
  603. smp_mb__after_atomic_inc(); /* Force delay to next write. */
  604. WARN_ON_ONCE(atomic_read(&rdtp->dynticks) & 0x1);
  605. }
  606. /**
  607. * rcu_is_cpu_idle - see if RCU thinks that the current CPU is idle
  608. *
  609. * If the current CPU is in its idle loop and is neither in an interrupt
  610. * or NMI handler, return true.
  611. */
  612. int rcu_is_cpu_idle(void)
  613. {
  614. int ret;
  615. preempt_disable();
  616. ret = (atomic_read(&__get_cpu_var(rcu_dynticks).dynticks) & 0x1) == 0;
  617. preempt_enable();
  618. return ret;
  619. }
  620. EXPORT_SYMBOL(rcu_is_cpu_idle);
  621. #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU)
  622. /*
  623. * Is the current CPU online? Disable preemption to avoid false positives
  624. * that could otherwise happen due to the current CPU number being sampled,
  625. * this task being preempted, its old CPU being taken offline, resuming
  626. * on some other CPU, then determining that its old CPU is now offline.
  627. * It is OK to use RCU on an offline processor during initial boot, hence
  628. * the check for rcu_scheduler_fully_active. Note also that it is OK
  629. * for a CPU coming online to use RCU for one jiffy prior to marking itself
  630. * online in the cpu_online_mask. Similarly, it is OK for a CPU going
  631. * offline to continue to use RCU for one jiffy after marking itself
  632. * offline in the cpu_online_mask. This leniency is necessary given the
  633. * non-atomic nature of the online and offline processing, for example,
  634. * the fact that a CPU enters the scheduler after completing the CPU_DYING
  635. * notifiers.
  636. *
  637. * This is also why RCU internally marks CPUs online during the
  638. * CPU_UP_PREPARE phase and offline during the CPU_DEAD phase.
  639. *
  640. * Disable checking if in an NMI handler because we cannot safely report
  641. * errors from NMI handlers anyway.
  642. */
  643. bool rcu_lockdep_current_cpu_online(void)
  644. {
  645. struct rcu_data *rdp;
  646. struct rcu_node *rnp;
  647. bool ret;
  648. if (in_nmi())
  649. return 1;
  650. preempt_disable();
  651. rdp = &__get_cpu_var(rcu_sched_data);
  652. rnp = rdp->mynode;
  653. ret = (rdp->grpmask & rnp->qsmaskinit) ||
  654. !rcu_scheduler_fully_active;
  655. preempt_enable();
  656. return ret;
  657. }
  658. EXPORT_SYMBOL_GPL(rcu_lockdep_current_cpu_online);
  659. #endif /* #if defined(CONFIG_PROVE_RCU) && defined(CONFIG_HOTPLUG_CPU) */
  660. /**
  661. * rcu_is_cpu_rrupt_from_idle - see if idle or immediately interrupted from idle
  662. *
  663. * If the current CPU is idle or running at a first-level (not nested)
  664. * interrupt from idle, return true. The caller must have at least
  665. * disabled preemption.
  666. */
  667. static int rcu_is_cpu_rrupt_from_idle(void)
  668. {
  669. return __get_cpu_var(rcu_dynticks).dynticks_nesting <= 1;
  670. }
  671. /*
  672. * Snapshot the specified CPU's dynticks counter so that we can later
  673. * credit them with an implicit quiescent state. Return 1 if this CPU
  674. * is in dynticks idle mode, which is an extended quiescent state.
  675. */
  676. static int dyntick_save_progress_counter(struct rcu_data *rdp)
  677. {
  678. rdp->dynticks_snap = atomic_add_return(0, &rdp->dynticks->dynticks);
  679. return (rdp->dynticks_snap & 0x1) == 0;
  680. }
  681. /*
  682. * Return true if the specified CPU has passed through a quiescent
  683. * state by virtue of being in or having passed through an dynticks
  684. * idle state since the last call to dyntick_save_progress_counter()
  685. * for this same CPU, or by virtue of having been offline.
  686. */
  687. static int rcu_implicit_dynticks_qs(struct rcu_data *rdp)
  688. {
  689. unsigned int curr;
  690. unsigned int snap;
  691. curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);
  692. snap = (unsigned int)rdp->dynticks_snap;
  693. /*
  694. * If the CPU passed through or entered a dynticks idle phase with
  695. * no active irq/NMI handlers, then we can safely pretend that the CPU
  696. * already acknowledged the request to pass through a quiescent
  697. * state. Either way, that CPU cannot possibly be in an RCU
  698. * read-side critical section that started before the beginning
  699. * of the current RCU grace period.
  700. */
  701. if ((curr & 0x1) == 0 || UINT_CMP_GE(curr, snap + 2)) {
  702. trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, "dti");
  703. rdp->dynticks_fqs++;
  704. return 1;
  705. }
  706. /*
  707. * Check for the CPU being offline, but only if the grace period
  708. * is old enough. We don't need to worry about the CPU changing
  709. * state: If we see it offline even once, it has been through a
  710. * quiescent state.
  711. *
  712. * The reason for insisting that the grace period be at least
  713. * one jiffy old is that CPUs that are not quite online and that
  714. * have just gone offline can still execute RCU read-side critical
  715. * sections.
  716. */
  717. if (ULONG_CMP_GE(rdp->rsp->gp_start + 2, jiffies))
  718. return 0; /* Grace period is not old enough. */
  719. barrier();
  720. if (cpu_is_offline(rdp->cpu)) {
  721. trace_rcu_fqs(rdp->rsp->name, rdp->gpnum, rdp->cpu, "ofl");
  722. rdp->offline_fqs++;
  723. return 1;
  724. }
  725. /*
  726. * There is a possibility that a CPU in adaptive-ticks state
  727. * might run in the kernel with the scheduling-clock tick disabled
  728. * for an extended time period. Invoke rcu_kick_nohz_cpu() to
  729. * force the CPU to restart the scheduling-clock tick in this
  730. * CPU is in this state.
  731. */
  732. rcu_kick_nohz_cpu(rdp->cpu);
  733. return 0;
  734. }
  735. static void record_gp_stall_check_time(struct rcu_state *rsp)
  736. {
  737. rsp->gp_start = jiffies;
  738. rsp->jiffies_stall = jiffies + rcu_jiffies_till_stall_check();
  739. }
  740. /*
  741. * Dump stacks of all tasks running on stalled CPUs. This is a fallback
  742. * for architectures that do not implement trigger_all_cpu_backtrace().
  743. * The NMI-triggered stack traces are more accurate because they are
  744. * printed by the target CPU.
  745. */
  746. static void rcu_dump_cpu_stacks(struct rcu_state *rsp)
  747. {
  748. int cpu;
  749. unsigned long flags;
  750. struct rcu_node *rnp;
  751. rcu_for_each_leaf_node(rsp, rnp) {
  752. raw_spin_lock_irqsave(&rnp->lock, flags);
  753. if (rnp->qsmask != 0) {
  754. for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++)
  755. if (rnp->qsmask & (1UL << cpu))
  756. dump_cpu_task(rnp->grplo + cpu);
  757. }
  758. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  759. }
  760. }
  761. static void print_other_cpu_stall(struct rcu_state *rsp)
  762. {
  763. int cpu;
  764. long delta;
  765. unsigned long flags;
  766. int ndetected = 0;
  767. struct rcu_node *rnp = rcu_get_root(rsp);
  768. long totqlen = 0;
  769. /* Only let one CPU complain about others per time interval. */
  770. raw_spin_lock_irqsave(&rnp->lock, flags);
  771. delta = jiffies - rsp->jiffies_stall;
  772. if (delta < RCU_STALL_RAT_DELAY || !rcu_gp_in_progress(rsp)) {
  773. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  774. return;
  775. }
  776. rsp->jiffies_stall = jiffies + 3 * rcu_jiffies_till_stall_check() + 3;
  777. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  778. /*
  779. * OK, time to rat on our buddy...
  780. * See Documentation/RCU/stallwarn.txt for info on how to debug
  781. * RCU CPU stall warnings.
  782. */
  783. printk(KERN_ERR "INFO: %s detected stalls on CPUs/tasks:",
  784. rsp->name);
  785. print_cpu_stall_info_begin();
  786. rcu_for_each_leaf_node(rsp, rnp) {
  787. raw_spin_lock_irqsave(&rnp->lock, flags);
  788. ndetected += rcu_print_task_stall(rnp);
  789. if (rnp->qsmask != 0) {
  790. for (cpu = 0; cpu <= rnp->grphi - rnp->grplo; cpu++)
  791. if (rnp->qsmask & (1UL << cpu)) {
  792. print_cpu_stall_info(rsp,
  793. rnp->grplo + cpu);
  794. ndetected++;
  795. }
  796. }
  797. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  798. }
  799. /*
  800. * Now rat on any tasks that got kicked up to the root rcu_node
  801. * due to CPU offlining.
  802. */
  803. rnp = rcu_get_root(rsp);
  804. raw_spin_lock_irqsave(&rnp->lock, flags);
  805. ndetected += rcu_print_task_stall(rnp);
  806. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  807. print_cpu_stall_info_end();
  808. for_each_possible_cpu(cpu)
  809. totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen;
  810. pr_cont("(detected by %d, t=%ld jiffies, g=%lu, c=%lu, q=%lu)\n",
  811. smp_processor_id(), (long)(jiffies - rsp->gp_start),
  812. rsp->gpnum, rsp->completed, totqlen);
  813. if (ndetected == 0)
  814. printk(KERN_ERR "INFO: Stall ended before state dump start\n");
  815. else if (!trigger_all_cpu_backtrace())
  816. rcu_dump_cpu_stacks(rsp);
  817. /* Complain about tasks blocking the grace period. */
  818. rcu_print_detail_task_stall(rsp);
  819. force_quiescent_state(rsp); /* Kick them all. */
  820. }
  821. static void print_cpu_stall(struct rcu_state *rsp)
  822. {
  823. int cpu;
  824. unsigned long flags;
  825. struct rcu_node *rnp = rcu_get_root(rsp);
  826. long totqlen = 0;
  827. /*
  828. * OK, time to rat on ourselves...
  829. * See Documentation/RCU/stallwarn.txt for info on how to debug
  830. * RCU CPU stall warnings.
  831. */
  832. printk(KERN_ERR "INFO: %s self-detected stall on CPU", rsp->name);
  833. print_cpu_stall_info_begin();
  834. print_cpu_stall_info(rsp, smp_processor_id());
  835. print_cpu_stall_info_end();
  836. for_each_possible_cpu(cpu)
  837. totqlen += per_cpu_ptr(rsp->rda, cpu)->qlen;
  838. pr_cont(" (t=%lu jiffies g=%lu c=%lu q=%lu)\n",
  839. jiffies - rsp->gp_start, rsp->gpnum, rsp->completed, totqlen);
  840. if (!trigger_all_cpu_backtrace())
  841. dump_stack();
  842. raw_spin_lock_irqsave(&rnp->lock, flags);
  843. if (ULONG_CMP_GE(jiffies, rsp->jiffies_stall))
  844. rsp->jiffies_stall = jiffies +
  845. 3 * rcu_jiffies_till_stall_check() + 3;
  846. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  847. set_need_resched(); /* kick ourselves to get things going. */
  848. }
  849. static void check_cpu_stall(struct rcu_state *rsp, struct rcu_data *rdp)
  850. {
  851. unsigned long j;
  852. unsigned long js;
  853. struct rcu_node *rnp;
  854. if (rcu_cpu_stall_suppress)
  855. return;
  856. j = ACCESS_ONCE(jiffies);
  857. js = ACCESS_ONCE(rsp->jiffies_stall);
  858. rnp = rdp->mynode;
  859. if (rcu_gp_in_progress(rsp) &&
  860. (ACCESS_ONCE(rnp->qsmask) & rdp->grpmask) && ULONG_CMP_GE(j, js)) {
  861. /* We haven't checked in, so go dump stack. */
  862. print_cpu_stall(rsp);
  863. } else if (rcu_gp_in_progress(rsp) &&
  864. ULONG_CMP_GE(j, js + RCU_STALL_RAT_DELAY)) {
  865. /* They had a few time units to dump stack, so complain. */
  866. print_other_cpu_stall(rsp);
  867. }
  868. }
  869. /**
  870. * rcu_cpu_stall_reset - prevent further stall warnings in current grace period
  871. *
  872. * Set the stall-warning timeout way off into the future, thus preventing
  873. * any RCU CPU stall-warning messages from appearing in the current set of
  874. * RCU grace periods.
  875. *
  876. * The caller must disable hard irqs.
  877. */
  878. void rcu_cpu_stall_reset(void)
  879. {
  880. struct rcu_state *rsp;
  881. for_each_rcu_flavor(rsp)
  882. rsp->jiffies_stall = jiffies + ULONG_MAX / 2;
  883. }
  884. /*
  885. * Update CPU-local rcu_data state to record the newly noticed grace period.
  886. * This is used both when we started the grace period and when we notice
  887. * that someone else started the grace period. The caller must hold the
  888. * ->lock of the leaf rcu_node structure corresponding to the current CPU,
  889. * and must have irqs disabled.
  890. */
  891. static void __note_new_gpnum(struct rcu_state *rsp, struct rcu_node *rnp, struct rcu_data *rdp)
  892. {
  893. if (rdp->gpnum != rnp->gpnum) {
  894. /*
  895. * If the current grace period is waiting for this CPU,
  896. * set up to detect a quiescent state, otherwise don't
  897. * go looking for one.
  898. */
  899. rdp->gpnum = rnp->gpnum;
  900. trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpustart");
  901. rdp->passed_quiesce = 0;
  902. rdp->qs_pending = !!(rnp->qsmask & rdp->grpmask);
  903. zero_cpu_stall_ticks(rdp);
  904. }
  905. }
  906. static void note_new_gpnum(struct rcu_state *rsp, struct rcu_data *rdp)
  907. {
  908. unsigned long flags;
  909. struct rcu_node *rnp;
  910. local_irq_save(flags);
  911. rnp = rdp->mynode;
  912. if (rdp->gpnum == ACCESS_ONCE(rnp->gpnum) || /* outside lock. */
  913. !raw_spin_trylock(&rnp->lock)) { /* irqs already off, so later. */
  914. local_irq_restore(flags);
  915. return;
  916. }
  917. __note_new_gpnum(rsp, rnp, rdp);
  918. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  919. }
  920. /*
  921. * Did someone else start a new RCU grace period start since we last
  922. * checked? Update local state appropriately if so. Must be called
  923. * on the CPU corresponding to rdp.
  924. */
  925. static int
  926. check_for_new_grace_period(struct rcu_state *rsp, struct rcu_data *rdp)
  927. {
  928. unsigned long flags;
  929. int ret = 0;
  930. local_irq_save(flags);
  931. if (rdp->gpnum != rsp->gpnum) {
  932. note_new_gpnum(rsp, rdp);
  933. ret = 1;
  934. }
  935. local_irq_restore(flags);
  936. return ret;
  937. }
  938. /*
  939. * Initialize the specified rcu_data structure's callback list to empty.
  940. */
  941. static void init_callback_list(struct rcu_data *rdp)
  942. {
  943. int i;
  944. if (init_nocb_callback_list(rdp))
  945. return;
  946. rdp->nxtlist = NULL;
  947. for (i = 0; i < RCU_NEXT_SIZE; i++)
  948. rdp->nxttail[i] = &rdp->nxtlist;
  949. }
  950. /*
  951. * Determine the value that ->completed will have at the end of the
  952. * next subsequent grace period. This is used to tag callbacks so that
  953. * a CPU can invoke callbacks in a timely fashion even if that CPU has
  954. * been dyntick-idle for an extended period with callbacks under the
  955. * influence of RCU_FAST_NO_HZ.
  956. *
  957. * The caller must hold rnp->lock with interrupts disabled.
  958. */
  959. static unsigned long rcu_cbs_completed(struct rcu_state *rsp,
  960. struct rcu_node *rnp)
  961. {
  962. /*
  963. * If RCU is idle, we just wait for the next grace period.
  964. * But we can only be sure that RCU is idle if we are looking
  965. * at the root rcu_node structure -- otherwise, a new grace
  966. * period might have started, but just not yet gotten around
  967. * to initializing the current non-root rcu_node structure.
  968. */
  969. if (rcu_get_root(rsp) == rnp && rnp->gpnum == rnp->completed)
  970. return rnp->completed + 1;
  971. /*
  972. * Otherwise, wait for a possible partial grace period and
  973. * then the subsequent full grace period.
  974. */
  975. return rnp->completed + 2;
  976. }
  977. /*
  978. * Trace-event helper function for rcu_start_future_gp() and
  979. * rcu_nocb_wait_gp().
  980. */
  981. static void trace_rcu_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  982. unsigned long c, char *s)
  983. {
  984. trace_rcu_future_grace_period(rdp->rsp->name, rnp->gpnum,
  985. rnp->completed, c, rnp->level,
  986. rnp->grplo, rnp->grphi, s);
  987. }
  988. /*
  989. * Start some future grace period, as needed to handle newly arrived
  990. * callbacks. The required future grace periods are recorded in each
  991. * rcu_node structure's ->need_future_gp field.
  992. *
  993. * The caller must hold the specified rcu_node structure's ->lock.
  994. */
  995. static unsigned long __maybe_unused
  996. rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp)
  997. {
  998. unsigned long c;
  999. int i;
  1000. struct rcu_node *rnp_root = rcu_get_root(rdp->rsp);
  1001. /*
  1002. * Pick up grace-period number for new callbacks. If this
  1003. * grace period is already marked as needed, return to the caller.
  1004. */
  1005. c = rcu_cbs_completed(rdp->rsp, rnp);
  1006. trace_rcu_future_gp(rnp, rdp, c, "Startleaf");
  1007. if (rnp->need_future_gp[c & 0x1]) {
  1008. trace_rcu_future_gp(rnp, rdp, c, "Prestartleaf");
  1009. return c;
  1010. }
  1011. /*
  1012. * If either this rcu_node structure or the root rcu_node structure
  1013. * believe that a grace period is in progress, then we must wait
  1014. * for the one following, which is in "c". Because our request
  1015. * will be noticed at the end of the current grace period, we don't
  1016. * need to explicitly start one.
  1017. */
  1018. if (rnp->gpnum != rnp->completed ||
  1019. ACCESS_ONCE(rnp->gpnum) != ACCESS_ONCE(rnp->completed)) {
  1020. rnp->need_future_gp[c & 0x1]++;
  1021. trace_rcu_future_gp(rnp, rdp, c, "Startedleaf");
  1022. return c;
  1023. }
  1024. /*
  1025. * There might be no grace period in progress. If we don't already
  1026. * hold it, acquire the root rcu_node structure's lock in order to
  1027. * start one (if needed).
  1028. */
  1029. if (rnp != rnp_root)
  1030. raw_spin_lock(&rnp_root->lock);
  1031. /*
  1032. * Get a new grace-period number. If there really is no grace
  1033. * period in progress, it will be smaller than the one we obtained
  1034. * earlier. Adjust callbacks as needed. Note that even no-CBs
  1035. * CPUs have a ->nxtcompleted[] array, so no no-CBs checks needed.
  1036. */
  1037. c = rcu_cbs_completed(rdp->rsp, rnp_root);
  1038. for (i = RCU_DONE_TAIL; i < RCU_NEXT_TAIL; i++)
  1039. if (ULONG_CMP_LT(c, rdp->nxtcompleted[i]))
  1040. rdp->nxtcompleted[i] = c;
  1041. /*
  1042. * If the needed for the required grace period is already
  1043. * recorded, trace and leave.
  1044. */
  1045. if (rnp_root->need_future_gp[c & 0x1]) {
  1046. trace_rcu_future_gp(rnp, rdp, c, "Prestartedroot");
  1047. goto unlock_out;
  1048. }
  1049. /* Record the need for the future grace period. */
  1050. rnp_root->need_future_gp[c & 0x1]++;
  1051. /* If a grace period is not already in progress, start one. */
  1052. if (rnp_root->gpnum != rnp_root->completed) {
  1053. trace_rcu_future_gp(rnp, rdp, c, "Startedleafroot");
  1054. } else {
  1055. trace_rcu_future_gp(rnp, rdp, c, "Startedroot");
  1056. rcu_start_gp_advanced(rdp->rsp, rnp_root, rdp);
  1057. }
  1058. unlock_out:
  1059. if (rnp != rnp_root)
  1060. raw_spin_unlock(&rnp_root->lock);
  1061. return c;
  1062. }
  1063. /*
  1064. * Clean up any old requests for the just-ended grace period. Also return
  1065. * whether any additional grace periods have been requested. Also invoke
  1066. * rcu_nocb_gp_cleanup() in order to wake up any no-callbacks kthreads
  1067. * waiting for this grace period to complete.
  1068. */
  1069. static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
  1070. {
  1071. int c = rnp->completed;
  1072. int needmore;
  1073. struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
  1074. rcu_nocb_gp_cleanup(rsp, rnp);
  1075. rnp->need_future_gp[c & 0x1] = 0;
  1076. needmore = rnp->need_future_gp[(c + 1) & 0x1];
  1077. trace_rcu_future_gp(rnp, rdp, c, needmore ? "CleanupMore" : "Cleanup");
  1078. return needmore;
  1079. }
  1080. /*
  1081. * If there is room, assign a ->completed number to any callbacks on
  1082. * this CPU that have not already been assigned. Also accelerate any
  1083. * callbacks that were previously assigned a ->completed number that has
  1084. * since proven to be too conservative, which can happen if callbacks get
  1085. * assigned a ->completed number while RCU is idle, but with reference to
  1086. * a non-root rcu_node structure. This function is idempotent, so it does
  1087. * not hurt to call it repeatedly.
  1088. *
  1089. * The caller must hold rnp->lock with interrupts disabled.
  1090. */
  1091. static void rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
  1092. struct rcu_data *rdp)
  1093. {
  1094. unsigned long c;
  1095. int i;
  1096. /* If the CPU has no callbacks, nothing to do. */
  1097. if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
  1098. return;
  1099. /*
  1100. * Starting from the sublist containing the callbacks most
  1101. * recently assigned a ->completed number and working down, find the
  1102. * first sublist that is not assignable to an upcoming grace period.
  1103. * Such a sublist has something in it (first two tests) and has
  1104. * a ->completed number assigned that will complete sooner than
  1105. * the ->completed number for newly arrived callbacks (last test).
  1106. *
  1107. * The key point is that any later sublist can be assigned the
  1108. * same ->completed number as the newly arrived callbacks, which
  1109. * means that the callbacks in any of these later sublist can be
  1110. * grouped into a single sublist, whether or not they have already
  1111. * been assigned a ->completed number.
  1112. */
  1113. c = rcu_cbs_completed(rsp, rnp);
  1114. for (i = RCU_NEXT_TAIL - 1; i > RCU_DONE_TAIL; i--)
  1115. if (rdp->nxttail[i] != rdp->nxttail[i - 1] &&
  1116. !ULONG_CMP_GE(rdp->nxtcompleted[i], c))
  1117. break;
  1118. /*
  1119. * If there are no sublist for unassigned callbacks, leave.
  1120. * At the same time, advance "i" one sublist, so that "i" will
  1121. * index into the sublist where all the remaining callbacks should
  1122. * be grouped into.
  1123. */
  1124. if (++i >= RCU_NEXT_TAIL)
  1125. return;
  1126. /*
  1127. * Assign all subsequent callbacks' ->completed number to the next
  1128. * full grace period and group them all in the sublist initially
  1129. * indexed by "i".
  1130. */
  1131. for (; i <= RCU_NEXT_TAIL; i++) {
  1132. rdp->nxttail[i] = rdp->nxttail[RCU_NEXT_TAIL];
  1133. rdp->nxtcompleted[i] = c;
  1134. }
  1135. /* Record any needed additional grace periods. */
  1136. rcu_start_future_gp(rnp, rdp);
  1137. /* Trace depending on how much we were able to accelerate. */
  1138. if (!*rdp->nxttail[RCU_WAIT_TAIL])
  1139. trace_rcu_grace_period(rsp->name, rdp->gpnum, "AccWaitCB");
  1140. else
  1141. trace_rcu_grace_period(rsp->name, rdp->gpnum, "AccReadyCB");
  1142. }
  1143. /*
  1144. * Move any callbacks whose grace period has completed to the
  1145. * RCU_DONE_TAIL sublist, then compact the remaining sublists and
  1146. * assign ->completed numbers to any callbacks in the RCU_NEXT_TAIL
  1147. * sublist. This function is idempotent, so it does not hurt to
  1148. * invoke it repeatedly. As long as it is not invoked -too- often...
  1149. *
  1150. * The caller must hold rnp->lock with interrupts disabled.
  1151. */
  1152. static void rcu_advance_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
  1153. struct rcu_data *rdp)
  1154. {
  1155. int i, j;
  1156. /* If the CPU has no callbacks, nothing to do. */
  1157. if (!rdp->nxttail[RCU_NEXT_TAIL] || !*rdp->nxttail[RCU_DONE_TAIL])
  1158. return;
  1159. /*
  1160. * Find all callbacks whose ->completed numbers indicate that they
  1161. * are ready to invoke, and put them into the RCU_DONE_TAIL sublist.
  1162. */
  1163. for (i = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++) {
  1164. if (ULONG_CMP_LT(rnp->completed, rdp->nxtcompleted[i]))
  1165. break;
  1166. rdp->nxttail[RCU_DONE_TAIL] = rdp->nxttail[i];
  1167. }
  1168. /* Clean up any sublist tail pointers that were misordered above. */
  1169. for (j = RCU_WAIT_TAIL; j < i; j++)
  1170. rdp->nxttail[j] = rdp->nxttail[RCU_DONE_TAIL];
  1171. /* Copy down callbacks to fill in empty sublists. */
  1172. for (j = RCU_WAIT_TAIL; i < RCU_NEXT_TAIL; i++, j++) {
  1173. if (rdp->nxttail[j] == rdp->nxttail[RCU_NEXT_TAIL])
  1174. break;
  1175. rdp->nxttail[j] = rdp->nxttail[i];
  1176. rdp->nxtcompleted[j] = rdp->nxtcompleted[i];
  1177. }
  1178. /* Classify any remaining callbacks. */
  1179. rcu_accelerate_cbs(rsp, rnp, rdp);
  1180. }
  1181. /*
  1182. * Advance this CPU's callbacks, but only if the current grace period
  1183. * has ended. This may be called only from the CPU to whom the rdp
  1184. * belongs. In addition, the corresponding leaf rcu_node structure's
  1185. * ->lock must be held by the caller, with irqs disabled.
  1186. */
  1187. static void
  1188. __rcu_process_gp_end(struct rcu_state *rsp, struct rcu_node *rnp, struct rcu_data *rdp)
  1189. {
  1190. /* Did another grace period end? */
  1191. if (rdp->completed == rnp->completed) {
  1192. /* No, so just accelerate recent callbacks. */
  1193. rcu_accelerate_cbs(rsp, rnp, rdp);
  1194. } else {
  1195. /* Advance callbacks. */
  1196. rcu_advance_cbs(rsp, rnp, rdp);
  1197. /* Remember that we saw this grace-period completion. */
  1198. rdp->completed = rnp->completed;
  1199. trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpuend");
  1200. /*
  1201. * If we were in an extended quiescent state, we may have
  1202. * missed some grace periods that others CPUs handled on
  1203. * our behalf. Catch up with this state to avoid noting
  1204. * spurious new grace periods. If another grace period
  1205. * has started, then rnp->gpnum will have advanced, so
  1206. * we will detect this later on. Of course, any quiescent
  1207. * states we found for the old GP are now invalid.
  1208. */
  1209. if (ULONG_CMP_LT(rdp->gpnum, rdp->completed)) {
  1210. rdp->gpnum = rdp->completed;
  1211. rdp->passed_quiesce = 0;
  1212. }
  1213. /*
  1214. * If RCU does not need a quiescent state from this CPU,
  1215. * then make sure that this CPU doesn't go looking for one.
  1216. */
  1217. if ((rnp->qsmask & rdp->grpmask) == 0)
  1218. rdp->qs_pending = 0;
  1219. }
  1220. }
  1221. /*
  1222. * Advance this CPU's callbacks, but only if the current grace period
  1223. * has ended. This may be called only from the CPU to whom the rdp
  1224. * belongs.
  1225. */
  1226. static void
  1227. rcu_process_gp_end(struct rcu_state *rsp, struct rcu_data *rdp)
  1228. {
  1229. unsigned long flags;
  1230. struct rcu_node *rnp;
  1231. local_irq_save(flags);
  1232. rnp = rdp->mynode;
  1233. if (rdp->completed == ACCESS_ONCE(rnp->completed) || /* outside lock. */
  1234. !raw_spin_trylock(&rnp->lock)) { /* irqs already off, so later. */
  1235. local_irq_restore(flags);
  1236. return;
  1237. }
  1238. __rcu_process_gp_end(rsp, rnp, rdp);
  1239. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1240. }
  1241. /*
  1242. * Do per-CPU grace-period initialization for running CPU. The caller
  1243. * must hold the lock of the leaf rcu_node structure corresponding to
  1244. * this CPU.
  1245. */
  1246. static void
  1247. rcu_start_gp_per_cpu(struct rcu_state *rsp, struct rcu_node *rnp, struct rcu_data *rdp)
  1248. {
  1249. /* Prior grace period ended, so advance callbacks for current CPU. */
  1250. __rcu_process_gp_end(rsp, rnp, rdp);
  1251. /* Set state so that this CPU will detect the next quiescent state. */
  1252. __note_new_gpnum(rsp, rnp, rdp);
  1253. }
  1254. /*
  1255. * Initialize a new grace period.
  1256. */
  1257. static int rcu_gp_init(struct rcu_state *rsp)
  1258. {
  1259. struct rcu_data *rdp;
  1260. struct rcu_node *rnp = rcu_get_root(rsp);
  1261. raw_spin_lock_irq(&rnp->lock);
  1262. rsp->gp_flags = 0; /* Clear all flags: New grace period. */
  1263. if (rcu_gp_in_progress(rsp)) {
  1264. /* Grace period already in progress, don't start another. */
  1265. raw_spin_unlock_irq(&rnp->lock);
  1266. return 0;
  1267. }
  1268. /* Advance to a new grace period and initialize state. */
  1269. rsp->gpnum++;
  1270. trace_rcu_grace_period(rsp->name, rsp->gpnum, "start");
  1271. record_gp_stall_check_time(rsp);
  1272. raw_spin_unlock_irq(&rnp->lock);
  1273. /* Exclude any concurrent CPU-hotplug operations. */
  1274. mutex_lock(&rsp->onoff_mutex);
  1275. /*
  1276. * Set the quiescent-state-needed bits in all the rcu_node
  1277. * structures for all currently online CPUs in breadth-first order,
  1278. * starting from the root rcu_node structure, relying on the layout
  1279. * of the tree within the rsp->node[] array. Note that other CPUs
  1280. * will access only the leaves of the hierarchy, thus seeing that no
  1281. * grace period is in progress, at least until the corresponding
  1282. * leaf node has been initialized. In addition, we have excluded
  1283. * CPU-hotplug operations.
  1284. *
  1285. * The grace period cannot complete until the initialization
  1286. * process finishes, because this kthread handles both.
  1287. */
  1288. rcu_for_each_node_breadth_first(rsp, rnp) {
  1289. raw_spin_lock_irq(&rnp->lock);
  1290. rdp = this_cpu_ptr(rsp->rda);
  1291. rcu_preempt_check_blocked_tasks(rnp);
  1292. rnp->qsmask = rnp->qsmaskinit;
  1293. ACCESS_ONCE(rnp->gpnum) = rsp->gpnum;
  1294. WARN_ON_ONCE(rnp->completed != rsp->completed);
  1295. ACCESS_ONCE(rnp->completed) = rsp->completed;
  1296. if (rnp == rdp->mynode)
  1297. rcu_start_gp_per_cpu(rsp, rnp, rdp);
  1298. rcu_preempt_boost_start_gp(rnp);
  1299. trace_rcu_grace_period_init(rsp->name, rnp->gpnum,
  1300. rnp->level, rnp->grplo,
  1301. rnp->grphi, rnp->qsmask);
  1302. raw_spin_unlock_irq(&rnp->lock);
  1303. #ifdef CONFIG_PROVE_RCU_DELAY
  1304. if ((prandom_u32() % (rcu_num_nodes + 1)) == 0 &&
  1305. system_state == SYSTEM_RUNNING)
  1306. udelay(200);
  1307. #endif /* #ifdef CONFIG_PROVE_RCU_DELAY */
  1308. cond_resched();
  1309. }
  1310. mutex_unlock(&rsp->onoff_mutex);
  1311. return 1;
  1312. }
  1313. /*
  1314. * Do one round of quiescent-state forcing.
  1315. */
  1316. int rcu_gp_fqs(struct rcu_state *rsp, int fqs_state_in)
  1317. {
  1318. int fqs_state = fqs_state_in;
  1319. struct rcu_node *rnp = rcu_get_root(rsp);
  1320. rsp->n_force_qs++;
  1321. if (fqs_state == RCU_SAVE_DYNTICK) {
  1322. /* Collect dyntick-idle snapshots. */
  1323. force_qs_rnp(rsp, dyntick_save_progress_counter);
  1324. fqs_state = RCU_FORCE_QS;
  1325. } else {
  1326. /* Handle dyntick-idle and offline CPUs. */
  1327. force_qs_rnp(rsp, rcu_implicit_dynticks_qs);
  1328. }
  1329. /* Clear flag to prevent immediate re-entry. */
  1330. if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
  1331. raw_spin_lock_irq(&rnp->lock);
  1332. rsp->gp_flags &= ~RCU_GP_FLAG_FQS;
  1333. raw_spin_unlock_irq(&rnp->lock);
  1334. }
  1335. return fqs_state;
  1336. }
  1337. /*
  1338. * Clean up after the old grace period.
  1339. */
  1340. static void rcu_gp_cleanup(struct rcu_state *rsp)
  1341. {
  1342. unsigned long gp_duration;
  1343. int nocb = 0;
  1344. struct rcu_data *rdp;
  1345. struct rcu_node *rnp = rcu_get_root(rsp);
  1346. raw_spin_lock_irq(&rnp->lock);
  1347. gp_duration = jiffies - rsp->gp_start;
  1348. if (gp_duration > rsp->gp_max)
  1349. rsp->gp_max = gp_duration;
  1350. /*
  1351. * We know the grace period is complete, but to everyone else
  1352. * it appears to still be ongoing. But it is also the case
  1353. * that to everyone else it looks like there is nothing that
  1354. * they can do to advance the grace period. It is therefore
  1355. * safe for us to drop the lock in order to mark the grace
  1356. * period as completed in all of the rcu_node structures.
  1357. */
  1358. raw_spin_unlock_irq(&rnp->lock);
  1359. /*
  1360. * Propagate new ->completed value to rcu_node structures so
  1361. * that other CPUs don't have to wait until the start of the next
  1362. * grace period to process their callbacks. This also avoids
  1363. * some nasty RCU grace-period initialization races by forcing
  1364. * the end of the current grace period to be completely recorded in
  1365. * all of the rcu_node structures before the beginning of the next
  1366. * grace period is recorded in any of the rcu_node structures.
  1367. */
  1368. rcu_for_each_node_breadth_first(rsp, rnp) {
  1369. raw_spin_lock_irq(&rnp->lock);
  1370. ACCESS_ONCE(rnp->completed) = rsp->gpnum;
  1371. rdp = this_cpu_ptr(rsp->rda);
  1372. if (rnp == rdp->mynode)
  1373. __rcu_process_gp_end(rsp, rnp, rdp);
  1374. nocb += rcu_future_gp_cleanup(rsp, rnp);
  1375. raw_spin_unlock_irq(&rnp->lock);
  1376. cond_resched();
  1377. }
  1378. rnp = rcu_get_root(rsp);
  1379. raw_spin_lock_irq(&rnp->lock);
  1380. rcu_nocb_gp_set(rnp, nocb);
  1381. rsp->completed = rsp->gpnum; /* Declare grace period done. */
  1382. trace_rcu_grace_period(rsp->name, rsp->completed, "end");
  1383. rsp->fqs_state = RCU_GP_IDLE;
  1384. rdp = this_cpu_ptr(rsp->rda);
  1385. rcu_advance_cbs(rsp, rnp, rdp); /* Reduce false positives below. */
  1386. if (cpu_needs_another_gp(rsp, rdp))
  1387. rsp->gp_flags = 1;
  1388. raw_spin_unlock_irq(&rnp->lock);
  1389. }
  1390. /*
  1391. * Body of kthread that handles grace periods.
  1392. */
  1393. static int __noreturn rcu_gp_kthread(void *arg)
  1394. {
  1395. int fqs_state;
  1396. unsigned long j;
  1397. int ret;
  1398. struct rcu_state *rsp = arg;
  1399. struct rcu_node *rnp = rcu_get_root(rsp);
  1400. for (;;) {
  1401. /* Handle grace-period start. */
  1402. for (;;) {
  1403. wait_event_interruptible(rsp->gp_wq,
  1404. rsp->gp_flags &
  1405. RCU_GP_FLAG_INIT);
  1406. if ((rsp->gp_flags & RCU_GP_FLAG_INIT) &&
  1407. rcu_gp_init(rsp))
  1408. break;
  1409. cond_resched();
  1410. flush_signals(current);
  1411. }
  1412. /* Handle quiescent-state forcing. */
  1413. fqs_state = RCU_SAVE_DYNTICK;
  1414. j = jiffies_till_first_fqs;
  1415. if (j > HZ) {
  1416. j = HZ;
  1417. jiffies_till_first_fqs = HZ;
  1418. }
  1419. for (;;) {
  1420. rsp->jiffies_force_qs = jiffies + j;
  1421. ret = wait_event_interruptible_timeout(rsp->gp_wq,
  1422. (rsp->gp_flags & RCU_GP_FLAG_FQS) ||
  1423. (!ACCESS_ONCE(rnp->qsmask) &&
  1424. !rcu_preempt_blocked_readers_cgp(rnp)),
  1425. j);
  1426. /* If grace period done, leave loop. */
  1427. if (!ACCESS_ONCE(rnp->qsmask) &&
  1428. !rcu_preempt_blocked_readers_cgp(rnp))
  1429. break;
  1430. /* If time for quiescent-state forcing, do it. */
  1431. if (ret == 0 || (rsp->gp_flags & RCU_GP_FLAG_FQS)) {
  1432. fqs_state = rcu_gp_fqs(rsp, fqs_state);
  1433. cond_resched();
  1434. } else {
  1435. /* Deal with stray signal. */
  1436. cond_resched();
  1437. flush_signals(current);
  1438. }
  1439. j = jiffies_till_next_fqs;
  1440. if (j > HZ) {
  1441. j = HZ;
  1442. jiffies_till_next_fqs = HZ;
  1443. } else if (j < 1) {
  1444. j = 1;
  1445. jiffies_till_next_fqs = 1;
  1446. }
  1447. }
  1448. /* Handle grace-period end. */
  1449. rcu_gp_cleanup(rsp);
  1450. }
  1451. }
  1452. static void rsp_wakeup(struct irq_work *work)
  1453. {
  1454. struct rcu_state *rsp = container_of(work, struct rcu_state, wakeup_work);
  1455. /* Wake up rcu_gp_kthread() to start the grace period. */
  1456. wake_up(&rsp->gp_wq);
  1457. }
  1458. /*
  1459. * Start a new RCU grace period if warranted, re-initializing the hierarchy
  1460. * in preparation for detecting the next grace period. The caller must hold
  1461. * the root node's ->lock and hard irqs must be disabled.
  1462. *
  1463. * Note that it is legal for a dying CPU (which is marked as offline) to
  1464. * invoke this function. This can happen when the dying CPU reports its
  1465. * quiescent state.
  1466. */
  1467. static void
  1468. rcu_start_gp_advanced(struct rcu_state *rsp, struct rcu_node *rnp,
  1469. struct rcu_data *rdp)
  1470. {
  1471. if (!rsp->gp_kthread || !cpu_needs_another_gp(rsp, rdp)) {
  1472. /*
  1473. * Either we have not yet spawned the grace-period
  1474. * task, this CPU does not need another grace period,
  1475. * or a grace period is already in progress.
  1476. * Either way, don't start a new grace period.
  1477. */
  1478. return;
  1479. }
  1480. rsp->gp_flags = RCU_GP_FLAG_INIT;
  1481. /*
  1482. * We can't do wakeups while holding the rnp->lock, as that
  1483. * could cause possible deadlocks with the rq->lock. Deter
  1484. * the wakeup to interrupt context.
  1485. */
  1486. irq_work_queue(&rsp->wakeup_work);
  1487. }
  1488. /*
  1489. * Similar to rcu_start_gp_advanced(), but also advance the calling CPU's
  1490. * callbacks. Note that rcu_start_gp_advanced() cannot do this because it
  1491. * is invoked indirectly from rcu_advance_cbs(), which would result in
  1492. * endless recursion -- or would do so if it wasn't for the self-deadlock
  1493. * that is encountered beforehand.
  1494. */
  1495. static void
  1496. rcu_start_gp(struct rcu_state *rsp)
  1497. {
  1498. struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
  1499. struct rcu_node *rnp = rcu_get_root(rsp);
  1500. /*
  1501. * If there is no grace period in progress right now, any
  1502. * callbacks we have up to this point will be satisfied by the
  1503. * next grace period. Also, advancing the callbacks reduces the
  1504. * probability of false positives from cpu_needs_another_gp()
  1505. * resulting in pointless grace periods. So, advance callbacks
  1506. * then start the grace period!
  1507. */
  1508. rcu_advance_cbs(rsp, rnp, rdp);
  1509. rcu_start_gp_advanced(rsp, rnp, rdp);
  1510. }
  1511. /*
  1512. * Report a full set of quiescent states to the specified rcu_state
  1513. * data structure. This involves cleaning up after the prior grace
  1514. * period and letting rcu_start_gp() start up the next grace period
  1515. * if one is needed. Note that the caller must hold rnp->lock, which
  1516. * is released before return.
  1517. */
  1518. static void rcu_report_qs_rsp(struct rcu_state *rsp, unsigned long flags)
  1519. __releases(rcu_get_root(rsp)->lock)
  1520. {
  1521. WARN_ON_ONCE(!rcu_gp_in_progress(rsp));
  1522. raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags);
  1523. wake_up(&rsp->gp_wq); /* Memory barrier implied by wake_up() path. */
  1524. }
  1525. /*
  1526. * Similar to rcu_report_qs_rdp(), for which it is a helper function.
  1527. * Allows quiescent states for a group of CPUs to be reported at one go
  1528. * to the specified rcu_node structure, though all the CPUs in the group
  1529. * must be represented by the same rcu_node structure (which need not be
  1530. * a leaf rcu_node structure, though it often will be). That structure's
  1531. * lock must be held upon entry, and it is released before return.
  1532. */
  1533. static void
  1534. rcu_report_qs_rnp(unsigned long mask, struct rcu_state *rsp,
  1535. struct rcu_node *rnp, unsigned long flags)
  1536. __releases(rnp->lock)
  1537. {
  1538. struct rcu_node *rnp_c;
  1539. /* Walk up the rcu_node hierarchy. */
  1540. for (;;) {
  1541. if (!(rnp->qsmask & mask)) {
  1542. /* Our bit has already been cleared, so done. */
  1543. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1544. return;
  1545. }
  1546. rnp->qsmask &= ~mask;
  1547. trace_rcu_quiescent_state_report(rsp->name, rnp->gpnum,
  1548. mask, rnp->qsmask, rnp->level,
  1549. rnp->grplo, rnp->grphi,
  1550. !!rnp->gp_tasks);
  1551. if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
  1552. /* Other bits still set at this level, so done. */
  1553. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1554. return;
  1555. }
  1556. mask = rnp->grpmask;
  1557. if (rnp->parent == NULL) {
  1558. /* No more levels. Exit loop holding root lock. */
  1559. break;
  1560. }
  1561. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1562. rnp_c = rnp;
  1563. rnp = rnp->parent;
  1564. raw_spin_lock_irqsave(&rnp->lock, flags);
  1565. WARN_ON_ONCE(rnp_c->qsmask);
  1566. }
  1567. /*
  1568. * Get here if we are the last CPU to pass through a quiescent
  1569. * state for this grace period. Invoke rcu_report_qs_rsp()
  1570. * to clean up and start the next grace period if one is needed.
  1571. */
  1572. rcu_report_qs_rsp(rsp, flags); /* releases rnp->lock. */
  1573. }
  1574. /*
  1575. * Record a quiescent state for the specified CPU to that CPU's rcu_data
  1576. * structure. This must be either called from the specified CPU, or
  1577. * called when the specified CPU is known to be offline (and when it is
  1578. * also known that no other CPU is concurrently trying to help the offline
  1579. * CPU). The lastcomp argument is used to make sure we are still in the
  1580. * grace period of interest. We don't want to end the current grace period
  1581. * based on quiescent states detected in an earlier grace period!
  1582. */
  1583. static void
  1584. rcu_report_qs_rdp(int cpu, struct rcu_state *rsp, struct rcu_data *rdp)
  1585. {
  1586. unsigned long flags;
  1587. unsigned long mask;
  1588. struct rcu_node *rnp;
  1589. rnp = rdp->mynode;
  1590. raw_spin_lock_irqsave(&rnp->lock, flags);
  1591. if (rdp->passed_quiesce == 0 || rdp->gpnum != rnp->gpnum ||
  1592. rnp->completed == rnp->gpnum) {
  1593. /*
  1594. * The grace period in which this quiescent state was
  1595. * recorded has ended, so don't report it upwards.
  1596. * We will instead need a new quiescent state that lies
  1597. * within the current grace period.
  1598. */
  1599. rdp->passed_quiesce = 0; /* need qs for new gp. */
  1600. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1601. return;
  1602. }
  1603. mask = rdp->grpmask;
  1604. if ((rnp->qsmask & mask) == 0) {
  1605. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1606. } else {
  1607. rdp->qs_pending = 0;
  1608. /*
  1609. * This GP can't end until cpu checks in, so all of our
  1610. * callbacks can be processed during the next GP.
  1611. */
  1612. rcu_accelerate_cbs(rsp, rnp, rdp);
  1613. rcu_report_qs_rnp(mask, rsp, rnp, flags); /* rlses rnp->lock */
  1614. }
  1615. }
  1616. /*
  1617. * Check to see if there is a new grace period of which this CPU
  1618. * is not yet aware, and if so, set up local rcu_data state for it.
  1619. * Otherwise, see if this CPU has just passed through its first
  1620. * quiescent state for this grace period, and record that fact if so.
  1621. */
  1622. static void
  1623. rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)
  1624. {
  1625. /* If there is now a new grace period, record and return. */
  1626. if (check_for_new_grace_period(rsp, rdp))
  1627. return;
  1628. /*
  1629. * Does this CPU still need to do its part for current grace period?
  1630. * If no, return and let the other CPUs do their part as well.
  1631. */
  1632. if (!rdp->qs_pending)
  1633. return;
  1634. /*
  1635. * Was there a quiescent state since the beginning of the grace
  1636. * period? If no, then exit and wait for the next call.
  1637. */
  1638. if (!rdp->passed_quiesce)
  1639. return;
  1640. /*
  1641. * Tell RCU we are done (but rcu_report_qs_rdp() will be the
  1642. * judge of that).
  1643. */
  1644. rcu_report_qs_rdp(rdp->cpu, rsp, rdp);
  1645. }
  1646. #ifdef CONFIG_HOTPLUG_CPU
  1647. /*
  1648. * Send the specified CPU's RCU callbacks to the orphanage. The
  1649. * specified CPU must be offline, and the caller must hold the
  1650. * ->orphan_lock.
  1651. */
  1652. static void
  1653. rcu_send_cbs_to_orphanage(int cpu, struct rcu_state *rsp,
  1654. struct rcu_node *rnp, struct rcu_data *rdp)
  1655. {
  1656. /* No-CBs CPUs do not have orphanable callbacks. */
  1657. if (rcu_is_nocb_cpu(rdp->cpu))
  1658. return;
  1659. /*
  1660. * Orphan the callbacks. First adjust the counts. This is safe
  1661. * because _rcu_barrier() excludes CPU-hotplug operations, so it
  1662. * cannot be running now. Thus no memory barrier is required.
  1663. */
  1664. if (rdp->nxtlist != NULL) {
  1665. rsp->qlen_lazy += rdp->qlen_lazy;
  1666. rsp->qlen += rdp->qlen;
  1667. rdp->n_cbs_orphaned += rdp->qlen;
  1668. rdp->qlen_lazy = 0;
  1669. ACCESS_ONCE(rdp->qlen) = 0;
  1670. }
  1671. /*
  1672. * Next, move those callbacks still needing a grace period to
  1673. * the orphanage, where some other CPU will pick them up.
  1674. * Some of the callbacks might have gone partway through a grace
  1675. * period, but that is too bad. They get to start over because we
  1676. * cannot assume that grace periods are synchronized across CPUs.
  1677. * We don't bother updating the ->nxttail[] array yet, instead
  1678. * we just reset the whole thing later on.
  1679. */
  1680. if (*rdp->nxttail[RCU_DONE_TAIL] != NULL) {
  1681. *rsp->orphan_nxttail = *rdp->nxttail[RCU_DONE_TAIL];
  1682. rsp->orphan_nxttail = rdp->nxttail[RCU_NEXT_TAIL];
  1683. *rdp->nxttail[RCU_DONE_TAIL] = NULL;
  1684. }
  1685. /*
  1686. * Then move the ready-to-invoke callbacks to the orphanage,
  1687. * where some other CPU will pick them up. These will not be
  1688. * required to pass though another grace period: They are done.
  1689. */
  1690. if (rdp->nxtlist != NULL) {
  1691. *rsp->orphan_donetail = rdp->nxtlist;
  1692. rsp->orphan_donetail = rdp->nxttail[RCU_DONE_TAIL];
  1693. }
  1694. /* Finally, initialize the rcu_data structure's list to empty. */
  1695. init_callback_list(rdp);
  1696. }
  1697. /*
  1698. * Adopt the RCU callbacks from the specified rcu_state structure's
  1699. * orphanage. The caller must hold the ->orphan_lock.
  1700. */
  1701. static void rcu_adopt_orphan_cbs(struct rcu_state *rsp)
  1702. {
  1703. int i;
  1704. struct rcu_data *rdp = __this_cpu_ptr(rsp->rda);
  1705. /* No-CBs CPUs are handled specially. */
  1706. if (rcu_nocb_adopt_orphan_cbs(rsp, rdp))
  1707. return;
  1708. /* Do the accounting first. */
  1709. rdp->qlen_lazy += rsp->qlen_lazy;
  1710. rdp->qlen += rsp->qlen;
  1711. rdp->n_cbs_adopted += rsp->qlen;
  1712. if (rsp->qlen_lazy != rsp->qlen)
  1713. rcu_idle_count_callbacks_posted();
  1714. rsp->qlen_lazy = 0;
  1715. rsp->qlen = 0;
  1716. /*
  1717. * We do not need a memory barrier here because the only way we
  1718. * can get here if there is an rcu_barrier() in flight is if
  1719. * we are the task doing the rcu_barrier().
  1720. */
  1721. /* First adopt the ready-to-invoke callbacks. */
  1722. if (rsp->orphan_donelist != NULL) {
  1723. *rsp->orphan_donetail = *rdp->nxttail[RCU_DONE_TAIL];
  1724. *rdp->nxttail[RCU_DONE_TAIL] = rsp->orphan_donelist;
  1725. for (i = RCU_NEXT_SIZE - 1; i >= RCU_DONE_TAIL; i--)
  1726. if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL])
  1727. rdp->nxttail[i] = rsp->orphan_donetail;
  1728. rsp->orphan_donelist = NULL;
  1729. rsp->orphan_donetail = &rsp->orphan_donelist;
  1730. }
  1731. /* And then adopt the callbacks that still need a grace period. */
  1732. if (rsp->orphan_nxtlist != NULL) {
  1733. *rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxtlist;
  1734. rdp->nxttail[RCU_NEXT_TAIL] = rsp->orphan_nxttail;
  1735. rsp->orphan_nxtlist = NULL;
  1736. rsp->orphan_nxttail = &rsp->orphan_nxtlist;
  1737. }
  1738. }
  1739. /*
  1740. * Trace the fact that this CPU is going offline.
  1741. */
  1742. static void rcu_cleanup_dying_cpu(struct rcu_state *rsp)
  1743. {
  1744. RCU_TRACE(unsigned long mask);
  1745. RCU_TRACE(struct rcu_data *rdp = this_cpu_ptr(rsp->rda));
  1746. RCU_TRACE(struct rcu_node *rnp = rdp->mynode);
  1747. RCU_TRACE(mask = rdp->grpmask);
  1748. trace_rcu_grace_period(rsp->name,
  1749. rnp->gpnum + 1 - !!(rnp->qsmask & mask),
  1750. "cpuofl");
  1751. }
  1752. /*
  1753. * The CPU has been completely removed, and some other CPU is reporting
  1754. * this fact from process context. Do the remainder of the cleanup,
  1755. * including orphaning the outgoing CPU's RCU callbacks, and also
  1756. * adopting them. There can only be one CPU hotplug operation at a time,
  1757. * so no other CPU can be attempting to update rcu_cpu_kthread_task.
  1758. */
  1759. static void rcu_cleanup_dead_cpu(int cpu, struct rcu_state *rsp)
  1760. {
  1761. unsigned long flags;
  1762. unsigned long mask;
  1763. int need_report = 0;
  1764. struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
  1765. struct rcu_node *rnp = rdp->mynode; /* Outgoing CPU's rdp & rnp. */
  1766. /* Adjust any no-longer-needed kthreads. */
  1767. rcu_boost_kthread_setaffinity(rnp, -1);
  1768. /* Remove the dead CPU from the bitmasks in the rcu_node hierarchy. */
  1769. /* Exclude any attempts to start a new grace period. */
  1770. mutex_lock(&rsp->onoff_mutex);
  1771. raw_spin_lock_irqsave(&rsp->orphan_lock, flags);
  1772. /* Orphan the dead CPU's callbacks, and adopt them if appropriate. */
  1773. rcu_send_cbs_to_orphanage(cpu, rsp, rnp, rdp);
  1774. rcu_adopt_orphan_cbs(rsp);
  1775. /* Remove the outgoing CPU from the masks in the rcu_node hierarchy. */
  1776. mask = rdp->grpmask; /* rnp->grplo is constant. */
  1777. do {
  1778. raw_spin_lock(&rnp->lock); /* irqs already disabled. */
  1779. rnp->qsmaskinit &= ~mask;
  1780. if (rnp->qsmaskinit != 0) {
  1781. if (rnp != rdp->mynode)
  1782. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  1783. break;
  1784. }
  1785. if (rnp == rdp->mynode)
  1786. need_report = rcu_preempt_offline_tasks(rsp, rnp, rdp);
  1787. else
  1788. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  1789. mask = rnp->grpmask;
  1790. rnp = rnp->parent;
  1791. } while (rnp != NULL);
  1792. /*
  1793. * We still hold the leaf rcu_node structure lock here, and
  1794. * irqs are still disabled. The reason for this subterfuge is
  1795. * because invoking rcu_report_unblock_qs_rnp() with ->orphan_lock
  1796. * held leads to deadlock.
  1797. */
  1798. raw_spin_unlock(&rsp->orphan_lock); /* irqs remain disabled. */
  1799. rnp = rdp->mynode;
  1800. if (need_report & RCU_OFL_TASKS_NORM_GP)
  1801. rcu_report_unblock_qs_rnp(rnp, flags);
  1802. else
  1803. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1804. if (need_report & RCU_OFL_TASKS_EXP_GP)
  1805. rcu_report_exp_rnp(rsp, rnp, true);
  1806. WARN_ONCE(rdp->qlen != 0 || rdp->nxtlist != NULL,
  1807. "rcu_cleanup_dead_cpu: Callbacks on offline CPU %d: qlen=%lu, nxtlist=%p\n",
  1808. cpu, rdp->qlen, rdp->nxtlist);
  1809. init_callback_list(rdp);
  1810. /* Disallow further callbacks on this CPU. */
  1811. rdp->nxttail[RCU_NEXT_TAIL] = NULL;
  1812. mutex_unlock(&rsp->onoff_mutex);
  1813. }
  1814. #else /* #ifdef CONFIG_HOTPLUG_CPU */
  1815. static void rcu_cleanup_dying_cpu(struct rcu_state *rsp)
  1816. {
  1817. }
  1818. static void rcu_cleanup_dead_cpu(int cpu, struct rcu_state *rsp)
  1819. {
  1820. }
  1821. #endif /* #else #ifdef CONFIG_HOTPLUG_CPU */
  1822. /*
  1823. * Invoke any RCU callbacks that have made it to the end of their grace
  1824. * period. Thottle as specified by rdp->blimit.
  1825. */
  1826. static void rcu_do_batch(struct rcu_state *rsp, struct rcu_data *rdp)
  1827. {
  1828. unsigned long flags;
  1829. struct rcu_head *next, *list, **tail;
  1830. long bl, count, count_lazy;
  1831. int i;
  1832. /* If no callbacks are ready, just return. */
  1833. if (!cpu_has_callbacks_ready_to_invoke(rdp)) {
  1834. trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, 0);
  1835. trace_rcu_batch_end(rsp->name, 0, !!ACCESS_ONCE(rdp->nxtlist),
  1836. need_resched(), is_idle_task(current),
  1837. rcu_is_callbacks_kthread());
  1838. return;
  1839. }
  1840. /*
  1841. * Extract the list of ready callbacks, disabling to prevent
  1842. * races with call_rcu() from interrupt handlers.
  1843. */
  1844. local_irq_save(flags);
  1845. WARN_ON_ONCE(cpu_is_offline(smp_processor_id()));
  1846. bl = rdp->blimit;
  1847. trace_rcu_batch_start(rsp->name, rdp->qlen_lazy, rdp->qlen, bl);
  1848. list = rdp->nxtlist;
  1849. rdp->nxtlist = *rdp->nxttail[RCU_DONE_TAIL];
  1850. *rdp->nxttail[RCU_DONE_TAIL] = NULL;
  1851. tail = rdp->nxttail[RCU_DONE_TAIL];
  1852. for (i = RCU_NEXT_SIZE - 1; i >= 0; i--)
  1853. if (rdp->nxttail[i] == rdp->nxttail[RCU_DONE_TAIL])
  1854. rdp->nxttail[i] = &rdp->nxtlist;
  1855. local_irq_restore(flags);
  1856. /* Invoke callbacks. */
  1857. count = count_lazy = 0;
  1858. while (list) {
  1859. next = list->next;
  1860. prefetch(next);
  1861. debug_rcu_head_unqueue(list);
  1862. if (__rcu_reclaim(rsp->name, list))
  1863. count_lazy++;
  1864. list = next;
  1865. /* Stop only if limit reached and CPU has something to do. */
  1866. if (++count >= bl &&
  1867. (need_resched() ||
  1868. (!is_idle_task(current) && !rcu_is_callbacks_kthread())))
  1869. break;
  1870. }
  1871. local_irq_save(flags);
  1872. trace_rcu_batch_end(rsp->name, count, !!list, need_resched(),
  1873. is_idle_task(current),
  1874. rcu_is_callbacks_kthread());
  1875. /* Update count, and requeue any remaining callbacks. */
  1876. if (list != NULL) {
  1877. *tail = rdp->nxtlist;
  1878. rdp->nxtlist = list;
  1879. for (i = 0; i < RCU_NEXT_SIZE; i++)
  1880. if (&rdp->nxtlist == rdp->nxttail[i])
  1881. rdp->nxttail[i] = tail;
  1882. else
  1883. break;
  1884. }
  1885. smp_mb(); /* List handling before counting for rcu_barrier(). */
  1886. rdp->qlen_lazy -= count_lazy;
  1887. ACCESS_ONCE(rdp->qlen) -= count;
  1888. rdp->n_cbs_invoked += count;
  1889. /* Reinstate batch limit if we have worked down the excess. */
  1890. if (rdp->blimit == LONG_MAX && rdp->qlen <= qlowmark)
  1891. rdp->blimit = blimit;
  1892. /* Reset ->qlen_last_fqs_check trigger if enough CBs have drained. */
  1893. if (rdp->qlen == 0 && rdp->qlen_last_fqs_check != 0) {
  1894. rdp->qlen_last_fqs_check = 0;
  1895. rdp->n_force_qs_snap = rsp->n_force_qs;
  1896. } else if (rdp->qlen < rdp->qlen_last_fqs_check - qhimark)
  1897. rdp->qlen_last_fqs_check = rdp->qlen;
  1898. WARN_ON_ONCE((rdp->nxtlist == NULL) != (rdp->qlen == 0));
  1899. local_irq_restore(flags);
  1900. /* Re-invoke RCU core processing if there are callbacks remaining. */
  1901. if (cpu_has_callbacks_ready_to_invoke(rdp))
  1902. invoke_rcu_core();
  1903. }
  1904. /*
  1905. * Check to see if this CPU is in a non-context-switch quiescent state
  1906. * (user mode or idle loop for rcu, non-softirq execution for rcu_bh).
  1907. * Also schedule RCU core processing.
  1908. *
  1909. * This function must be called from hardirq context. It is normally
  1910. * invoked from the scheduling-clock interrupt. If rcu_pending returns
  1911. * false, there is no point in invoking rcu_check_callbacks().
  1912. */
  1913. void rcu_check_callbacks(int cpu, int user)
  1914. {
  1915. trace_rcu_utilization("Start scheduler-tick");
  1916. increment_cpu_stall_ticks();
  1917. if (user || rcu_is_cpu_rrupt_from_idle()) {
  1918. /*
  1919. * Get here if this CPU took its interrupt from user
  1920. * mode or from the idle loop, and if this is not a
  1921. * nested interrupt. In this case, the CPU is in
  1922. * a quiescent state, so note it.
  1923. *
  1924. * No memory barrier is required here because both
  1925. * rcu_sched_qs() and rcu_bh_qs() reference only CPU-local
  1926. * variables that other CPUs neither access nor modify,
  1927. * at least not while the corresponding CPU is online.
  1928. */
  1929. rcu_sched_qs(cpu);
  1930. rcu_bh_qs(cpu);
  1931. } else if (!in_softirq()) {
  1932. /*
  1933. * Get here if this CPU did not take its interrupt from
  1934. * softirq, in other words, if it is not interrupting
  1935. * a rcu_bh read-side critical section. This is an _bh
  1936. * critical section, so note it.
  1937. */
  1938. rcu_bh_qs(cpu);
  1939. }
  1940. rcu_preempt_check_callbacks(cpu);
  1941. if (rcu_pending(cpu))
  1942. invoke_rcu_core();
  1943. trace_rcu_utilization("End scheduler-tick");
  1944. }
  1945. /*
  1946. * Scan the leaf rcu_node structures, processing dyntick state for any that
  1947. * have not yet encountered a quiescent state, using the function specified.
  1948. * Also initiate boosting for any threads blocked on the root rcu_node.
  1949. *
  1950. * The caller must have suppressed start of new grace periods.
  1951. */
  1952. static void force_qs_rnp(struct rcu_state *rsp, int (*f)(struct rcu_data *))
  1953. {
  1954. unsigned long bit;
  1955. int cpu;
  1956. unsigned long flags;
  1957. unsigned long mask;
  1958. struct rcu_node *rnp;
  1959. rcu_for_each_leaf_node(rsp, rnp) {
  1960. cond_resched();
  1961. mask = 0;
  1962. raw_spin_lock_irqsave(&rnp->lock, flags);
  1963. if (!rcu_gp_in_progress(rsp)) {
  1964. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1965. return;
  1966. }
  1967. if (rnp->qsmask == 0) {
  1968. rcu_initiate_boost(rnp, flags); /* releases rnp->lock */
  1969. continue;
  1970. }
  1971. cpu = rnp->grplo;
  1972. bit = 1;
  1973. for (; cpu <= rnp->grphi; cpu++, bit <<= 1) {
  1974. if ((rnp->qsmask & bit) != 0 &&
  1975. f(per_cpu_ptr(rsp->rda, cpu)))
  1976. mask |= bit;
  1977. }
  1978. if (mask != 0) {
  1979. /* rcu_report_qs_rnp() releases rnp->lock. */
  1980. rcu_report_qs_rnp(mask, rsp, rnp, flags);
  1981. continue;
  1982. }
  1983. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  1984. }
  1985. rnp = rcu_get_root(rsp);
  1986. if (rnp->qsmask == 0) {
  1987. raw_spin_lock_irqsave(&rnp->lock, flags);
  1988. rcu_initiate_boost(rnp, flags); /* releases rnp->lock. */
  1989. }
  1990. }
  1991. /*
  1992. * Force quiescent states on reluctant CPUs, and also detect which
  1993. * CPUs are in dyntick-idle mode.
  1994. */
  1995. static void force_quiescent_state(struct rcu_state *rsp)
  1996. {
  1997. unsigned long flags;
  1998. bool ret;
  1999. struct rcu_node *rnp;
  2000. struct rcu_node *rnp_old = NULL;
  2001. /* Funnel through hierarchy to reduce memory contention. */
  2002. rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
  2003. for (; rnp != NULL; rnp = rnp->parent) {
  2004. ret = (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) ||
  2005. !raw_spin_trylock(&rnp->fqslock);
  2006. if (rnp_old != NULL)
  2007. raw_spin_unlock(&rnp_old->fqslock);
  2008. if (ret) {
  2009. rsp->n_force_qs_lh++;
  2010. return;
  2011. }
  2012. rnp_old = rnp;
  2013. }
  2014. /* rnp_old == rcu_get_root(rsp), rnp == NULL. */
  2015. /* Reached the root of the rcu_node tree, acquire lock. */
  2016. raw_spin_lock_irqsave(&rnp_old->lock, flags);
  2017. raw_spin_unlock(&rnp_old->fqslock);
  2018. if (ACCESS_ONCE(rsp->gp_flags) & RCU_GP_FLAG_FQS) {
  2019. rsp->n_force_qs_lh++;
  2020. raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
  2021. return; /* Someone beat us to it. */
  2022. }
  2023. rsp->gp_flags |= RCU_GP_FLAG_FQS;
  2024. raw_spin_unlock_irqrestore(&rnp_old->lock, flags);
  2025. wake_up(&rsp->gp_wq); /* Memory barrier implied by wake_up() path. */
  2026. }
  2027. /*
  2028. * This does the RCU core processing work for the specified rcu_state
  2029. * and rcu_data structures. This may be called only from the CPU to
  2030. * whom the rdp belongs.
  2031. */
  2032. static void
  2033. __rcu_process_callbacks(struct rcu_state *rsp)
  2034. {
  2035. unsigned long flags;
  2036. struct rcu_data *rdp = __this_cpu_ptr(rsp->rda);
  2037. WARN_ON_ONCE(rdp->beenonline == 0);
  2038. /* Handle the end of a grace period that some other CPU ended. */
  2039. rcu_process_gp_end(rsp, rdp);
  2040. /* Update RCU state based on any recent quiescent states. */
  2041. rcu_check_quiescent_state(rsp, rdp);
  2042. /* Does this CPU require a not-yet-started grace period? */
  2043. local_irq_save(flags);
  2044. if (cpu_needs_another_gp(rsp, rdp)) {
  2045. raw_spin_lock(&rcu_get_root(rsp)->lock); /* irqs disabled. */
  2046. rcu_start_gp(rsp);
  2047. raw_spin_unlock_irqrestore(&rcu_get_root(rsp)->lock, flags);
  2048. } else {
  2049. local_irq_restore(flags);
  2050. }
  2051. /* If there are callbacks ready, invoke them. */
  2052. if (cpu_has_callbacks_ready_to_invoke(rdp))
  2053. invoke_rcu_callbacks(rsp, rdp);
  2054. }
  2055. /*
  2056. * Do RCU core processing for the current CPU.
  2057. */
  2058. static void rcu_process_callbacks(struct softirq_action *unused)
  2059. {
  2060. struct rcu_state *rsp;
  2061. if (cpu_is_offline(smp_processor_id()))
  2062. return;
  2063. trace_rcu_utilization("Start RCU core");
  2064. for_each_rcu_flavor(rsp)
  2065. __rcu_process_callbacks(rsp);
  2066. trace_rcu_utilization("End RCU core");
  2067. }
  2068. /*
  2069. * Schedule RCU callback invocation. If the specified type of RCU
  2070. * does not support RCU priority boosting, just do a direct call,
  2071. * otherwise wake up the per-CPU kernel kthread. Note that because we
  2072. * are running on the current CPU with interrupts disabled, the
  2073. * rcu_cpu_kthread_task cannot disappear out from under us.
  2074. */
  2075. static void invoke_rcu_callbacks(struct rcu_state *rsp, struct rcu_data *rdp)
  2076. {
  2077. if (unlikely(!ACCESS_ONCE(rcu_scheduler_fully_active)))
  2078. return;
  2079. if (likely(!rsp->boost)) {
  2080. rcu_do_batch(rsp, rdp);
  2081. return;
  2082. }
  2083. invoke_rcu_callbacks_kthread();
  2084. }
  2085. static void invoke_rcu_core(void)
  2086. {
  2087. if (cpu_online(smp_processor_id()))
  2088. raise_softirq(RCU_SOFTIRQ);
  2089. }
  2090. /*
  2091. * Handle any core-RCU processing required by a call_rcu() invocation.
  2092. */
  2093. static void __call_rcu_core(struct rcu_state *rsp, struct rcu_data *rdp,
  2094. struct rcu_head *head, unsigned long flags)
  2095. {
  2096. /*
  2097. * If called from an extended quiescent state, invoke the RCU
  2098. * core in order to force a re-evaluation of RCU's idleness.
  2099. */
  2100. if (rcu_is_cpu_idle() && cpu_online(smp_processor_id()))
  2101. invoke_rcu_core();
  2102. /* If interrupts were disabled or CPU offline, don't invoke RCU core. */
  2103. if (irqs_disabled_flags(flags) || cpu_is_offline(smp_processor_id()))
  2104. return;
  2105. /*
  2106. * Force the grace period if too many callbacks or too long waiting.
  2107. * Enforce hysteresis, and don't invoke force_quiescent_state()
  2108. * if some other CPU has recently done so. Also, don't bother
  2109. * invoking force_quiescent_state() if the newly enqueued callback
  2110. * is the only one waiting for a grace period to complete.
  2111. */
  2112. if (unlikely(rdp->qlen > rdp->qlen_last_fqs_check + qhimark)) {
  2113. /* Are we ignoring a completed grace period? */
  2114. rcu_process_gp_end(rsp, rdp);
  2115. check_for_new_grace_period(rsp, rdp);
  2116. /* Start a new grace period if one not already started. */
  2117. if (!rcu_gp_in_progress(rsp)) {
  2118. struct rcu_node *rnp_root = rcu_get_root(rsp);
  2119. raw_spin_lock(&rnp_root->lock);
  2120. rcu_start_gp(rsp);
  2121. raw_spin_unlock(&rnp_root->lock);
  2122. } else {
  2123. /* Give the grace period a kick. */
  2124. rdp->blimit = LONG_MAX;
  2125. if (rsp->n_force_qs == rdp->n_force_qs_snap &&
  2126. *rdp->nxttail[RCU_DONE_TAIL] != head)
  2127. force_quiescent_state(rsp);
  2128. rdp->n_force_qs_snap = rsp->n_force_qs;
  2129. rdp->qlen_last_fqs_check = rdp->qlen;
  2130. }
  2131. }
  2132. }
  2133. /*
  2134. * Helper function for call_rcu() and friends. The cpu argument will
  2135. * normally be -1, indicating "currently running CPU". It may specify
  2136. * a CPU only if that CPU is a no-CBs CPU. Currently, only _rcu_barrier()
  2137. * is expected to specify a CPU.
  2138. */
  2139. static void
  2140. __call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu),
  2141. struct rcu_state *rsp, int cpu, bool lazy)
  2142. {
  2143. unsigned long flags;
  2144. struct rcu_data *rdp;
  2145. WARN_ON_ONCE((unsigned long)head & 0x3); /* Misaligned rcu_head! */
  2146. debug_rcu_head_queue(head);
  2147. head->func = func;
  2148. head->next = NULL;
  2149. /*
  2150. * Opportunistically note grace-period endings and beginnings.
  2151. * Note that we might see a beginning right after we see an
  2152. * end, but never vice versa, since this CPU has to pass through
  2153. * a quiescent state betweentimes.
  2154. */
  2155. local_irq_save(flags);
  2156. rdp = this_cpu_ptr(rsp->rda);
  2157. /* Add the callback to our list. */
  2158. if (unlikely(rdp->nxttail[RCU_NEXT_TAIL] == NULL) || cpu != -1) {
  2159. int offline;
  2160. if (cpu != -1)
  2161. rdp = per_cpu_ptr(rsp->rda, cpu);
  2162. offline = !__call_rcu_nocb(rdp, head, lazy);
  2163. WARN_ON_ONCE(offline);
  2164. /* _call_rcu() is illegal on offline CPU; leak the callback. */
  2165. local_irq_restore(flags);
  2166. return;
  2167. }
  2168. ACCESS_ONCE(rdp->qlen)++;
  2169. if (lazy)
  2170. rdp->qlen_lazy++;
  2171. else
  2172. rcu_idle_count_callbacks_posted();
  2173. smp_mb(); /* Count before adding callback for rcu_barrier(). */
  2174. *rdp->nxttail[RCU_NEXT_TAIL] = head;
  2175. rdp->nxttail[RCU_NEXT_TAIL] = &head->next;
  2176. if (__is_kfree_rcu_offset((unsigned long)func))
  2177. trace_rcu_kfree_callback(rsp->name, head, (unsigned long)func,
  2178. rdp->qlen_lazy, rdp->qlen);
  2179. else
  2180. trace_rcu_callback(rsp->name, head, rdp->qlen_lazy, rdp->qlen);
  2181. /* Go handle any RCU core processing required. */
  2182. __call_rcu_core(rsp, rdp, head, flags);
  2183. local_irq_restore(flags);
  2184. }
  2185. /*
  2186. * Queue an RCU-sched callback for invocation after a grace period.
  2187. */
  2188. void call_rcu_sched(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
  2189. {
  2190. __call_rcu(head, func, &rcu_sched_state, -1, 0);
  2191. }
  2192. EXPORT_SYMBOL_GPL(call_rcu_sched);
  2193. /*
  2194. * Queue an RCU callback for invocation after a quicker grace period.
  2195. */
  2196. void call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu))
  2197. {
  2198. __call_rcu(head, func, &rcu_bh_state, -1, 0);
  2199. }
  2200. EXPORT_SYMBOL_GPL(call_rcu_bh);
  2201. /*
  2202. * Because a context switch is a grace period for RCU-sched and RCU-bh,
  2203. * any blocking grace-period wait automatically implies a grace period
  2204. * if there is only one CPU online at any point time during execution
  2205. * of either synchronize_sched() or synchronize_rcu_bh(). It is OK to
  2206. * occasionally incorrectly indicate that there are multiple CPUs online
  2207. * when there was in fact only one the whole time, as this just adds
  2208. * some overhead: RCU still operates correctly.
  2209. */
  2210. static inline int rcu_blocking_is_gp(void)
  2211. {
  2212. int ret;
  2213. might_sleep(); /* Check for RCU read-side critical section. */
  2214. preempt_disable();
  2215. ret = num_online_cpus() <= 1;
  2216. preempt_enable();
  2217. return ret;
  2218. }
  2219. /**
  2220. * synchronize_sched - wait until an rcu-sched grace period has elapsed.
  2221. *
  2222. * Control will return to the caller some time after a full rcu-sched
  2223. * grace period has elapsed, in other words after all currently executing
  2224. * rcu-sched read-side critical sections have completed. These read-side
  2225. * critical sections are delimited by rcu_read_lock_sched() and
  2226. * rcu_read_unlock_sched(), and may be nested. Note that preempt_disable(),
  2227. * local_irq_disable(), and so on may be used in place of
  2228. * rcu_read_lock_sched().
  2229. *
  2230. * This means that all preempt_disable code sequences, including NMI and
  2231. * non-threaded hardware-interrupt handlers, in progress on entry will
  2232. * have completed before this primitive returns. However, this does not
  2233. * guarantee that softirq handlers will have completed, since in some
  2234. * kernels, these handlers can run in process context, and can block.
  2235. *
  2236. * Note that this guarantee implies further memory-ordering guarantees.
  2237. * On systems with more than one CPU, when synchronize_sched() returns,
  2238. * each CPU is guaranteed to have executed a full memory barrier since the
  2239. * end of its last RCU-sched read-side critical section whose beginning
  2240. * preceded the call to synchronize_sched(). In addition, each CPU having
  2241. * an RCU read-side critical section that extends beyond the return from
  2242. * synchronize_sched() is guaranteed to have executed a full memory barrier
  2243. * after the beginning of synchronize_sched() and before the beginning of
  2244. * that RCU read-side critical section. Note that these guarantees include
  2245. * CPUs that are offline, idle, or executing in user mode, as well as CPUs
  2246. * that are executing in the kernel.
  2247. *
  2248. * Furthermore, if CPU A invoked synchronize_sched(), which returned
  2249. * to its caller on CPU B, then both CPU A and CPU B are guaranteed
  2250. * to have executed a full memory barrier during the execution of
  2251. * synchronize_sched() -- even if CPU A and CPU B are the same CPU (but
  2252. * again only if the system has more than one CPU).
  2253. *
  2254. * This primitive provides the guarantees made by the (now removed)
  2255. * synchronize_kernel() API. In contrast, synchronize_rcu() only
  2256. * guarantees that rcu_read_lock() sections will have completed.
  2257. * In "classic RCU", these two guarantees happen to be one and
  2258. * the same, but can differ in realtime RCU implementations.
  2259. */
  2260. void synchronize_sched(void)
  2261. {
  2262. rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) &&
  2263. !lock_is_held(&rcu_lock_map) &&
  2264. !lock_is_held(&rcu_sched_lock_map),
  2265. "Illegal synchronize_sched() in RCU-sched read-side critical section");
  2266. if (rcu_blocking_is_gp())
  2267. return;
  2268. if (rcu_expedited)
  2269. synchronize_sched_expedited();
  2270. else
  2271. wait_rcu_gp(call_rcu_sched);
  2272. }
  2273. EXPORT_SYMBOL_GPL(synchronize_sched);
  2274. /**
  2275. * synchronize_rcu_bh - wait until an rcu_bh grace period has elapsed.
  2276. *
  2277. * Control will return to the caller some time after a full rcu_bh grace
  2278. * period has elapsed, in other words after all currently executing rcu_bh
  2279. * read-side critical sections have completed. RCU read-side critical
  2280. * sections are delimited by rcu_read_lock_bh() and rcu_read_unlock_bh(),
  2281. * and may be nested.
  2282. *
  2283. * See the description of synchronize_sched() for more detailed information
  2284. * on memory ordering guarantees.
  2285. */
  2286. void synchronize_rcu_bh(void)
  2287. {
  2288. rcu_lockdep_assert(!lock_is_held(&rcu_bh_lock_map) &&
  2289. !lock_is_held(&rcu_lock_map) &&
  2290. !lock_is_held(&rcu_sched_lock_map),
  2291. "Illegal synchronize_rcu_bh() in RCU-bh read-side critical section");
  2292. if (rcu_blocking_is_gp())
  2293. return;
  2294. if (rcu_expedited)
  2295. synchronize_rcu_bh_expedited();
  2296. else
  2297. wait_rcu_gp(call_rcu_bh);
  2298. }
  2299. EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
  2300. static int synchronize_sched_expedited_cpu_stop(void *data)
  2301. {
  2302. /*
  2303. * There must be a full memory barrier on each affected CPU
  2304. * between the time that try_stop_cpus() is called and the
  2305. * time that it returns.
  2306. *
  2307. * In the current initial implementation of cpu_stop, the
  2308. * above condition is already met when the control reaches
  2309. * this point and the following smp_mb() is not strictly
  2310. * necessary. Do smp_mb() anyway for documentation and
  2311. * robustness against future implementation changes.
  2312. */
  2313. smp_mb(); /* See above comment block. */
  2314. return 0;
  2315. }
  2316. /**
  2317. * synchronize_sched_expedited - Brute-force RCU-sched grace period
  2318. *
  2319. * Wait for an RCU-sched grace period to elapse, but use a "big hammer"
  2320. * approach to force the grace period to end quickly. This consumes
  2321. * significant time on all CPUs and is unfriendly to real-time workloads,
  2322. * so is thus not recommended for any sort of common-case code. In fact,
  2323. * if you are using synchronize_sched_expedited() in a loop, please
  2324. * restructure your code to batch your updates, and then use a single
  2325. * synchronize_sched() instead.
  2326. *
  2327. * Note that it is illegal to call this function while holding any lock
  2328. * that is acquired by a CPU-hotplug notifier. And yes, it is also illegal
  2329. * to call this function from a CPU-hotplug notifier. Failing to observe
  2330. * these restriction will result in deadlock.
  2331. *
  2332. * This implementation can be thought of as an application of ticket
  2333. * locking to RCU, with sync_sched_expedited_started and
  2334. * sync_sched_expedited_done taking on the roles of the halves
  2335. * of the ticket-lock word. Each task atomically increments
  2336. * sync_sched_expedited_started upon entry, snapshotting the old value,
  2337. * then attempts to stop all the CPUs. If this succeeds, then each
  2338. * CPU will have executed a context switch, resulting in an RCU-sched
  2339. * grace period. We are then done, so we use atomic_cmpxchg() to
  2340. * update sync_sched_expedited_done to match our snapshot -- but
  2341. * only if someone else has not already advanced past our snapshot.
  2342. *
  2343. * On the other hand, if try_stop_cpus() fails, we check the value
  2344. * of sync_sched_expedited_done. If it has advanced past our
  2345. * initial snapshot, then someone else must have forced a grace period
  2346. * some time after we took our snapshot. In this case, our work is
  2347. * done for us, and we can simply return. Otherwise, we try again,
  2348. * but keep our initial snapshot for purposes of checking for someone
  2349. * doing our work for us.
  2350. *
  2351. * If we fail too many times in a row, we fall back to synchronize_sched().
  2352. */
  2353. void synchronize_sched_expedited(void)
  2354. {
  2355. long firstsnap, s, snap;
  2356. int trycount = 0;
  2357. struct rcu_state *rsp = &rcu_sched_state;
  2358. /*
  2359. * If we are in danger of counter wrap, just do synchronize_sched().
  2360. * By allowing sync_sched_expedited_started to advance no more than
  2361. * ULONG_MAX/8 ahead of sync_sched_expedited_done, we are ensuring
  2362. * that more than 3.5 billion CPUs would be required to force a
  2363. * counter wrap on a 32-bit system. Quite a few more CPUs would of
  2364. * course be required on a 64-bit system.
  2365. */
  2366. if (ULONG_CMP_GE((ulong)atomic_long_read(&rsp->expedited_start),
  2367. (ulong)atomic_long_read(&rsp->expedited_done) +
  2368. ULONG_MAX / 8)) {
  2369. synchronize_sched();
  2370. atomic_long_inc(&rsp->expedited_wrap);
  2371. return;
  2372. }
  2373. /*
  2374. * Take a ticket. Note that atomic_inc_return() implies a
  2375. * full memory barrier.
  2376. */
  2377. snap = atomic_long_inc_return(&rsp->expedited_start);
  2378. firstsnap = snap;
  2379. get_online_cpus();
  2380. WARN_ON_ONCE(cpu_is_offline(raw_smp_processor_id()));
  2381. /*
  2382. * Each pass through the following loop attempts to force a
  2383. * context switch on each CPU.
  2384. */
  2385. while (try_stop_cpus(cpu_online_mask,
  2386. synchronize_sched_expedited_cpu_stop,
  2387. NULL) == -EAGAIN) {
  2388. put_online_cpus();
  2389. atomic_long_inc(&rsp->expedited_tryfail);
  2390. /* Check to see if someone else did our work for us. */
  2391. s = atomic_long_read(&rsp->expedited_done);
  2392. if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
  2393. /* ensure test happens before caller kfree */
  2394. smp_mb__before_atomic_inc(); /* ^^^ */
  2395. atomic_long_inc(&rsp->expedited_workdone1);
  2396. return;
  2397. }
  2398. /* No joy, try again later. Or just synchronize_sched(). */
  2399. if (trycount++ < 10) {
  2400. udelay(trycount * num_online_cpus());
  2401. } else {
  2402. wait_rcu_gp(call_rcu_sched);
  2403. atomic_long_inc(&rsp->expedited_normal);
  2404. return;
  2405. }
  2406. /* Recheck to see if someone else did our work for us. */
  2407. s = atomic_long_read(&rsp->expedited_done);
  2408. if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
  2409. /* ensure test happens before caller kfree */
  2410. smp_mb__before_atomic_inc(); /* ^^^ */
  2411. atomic_long_inc(&rsp->expedited_workdone2);
  2412. return;
  2413. }
  2414. /*
  2415. * Refetching sync_sched_expedited_started allows later
  2416. * callers to piggyback on our grace period. We retry
  2417. * after they started, so our grace period works for them,
  2418. * and they started after our first try, so their grace
  2419. * period works for us.
  2420. */
  2421. get_online_cpus();
  2422. snap = atomic_long_read(&rsp->expedited_start);
  2423. smp_mb(); /* ensure read is before try_stop_cpus(). */
  2424. }
  2425. atomic_long_inc(&rsp->expedited_stoppedcpus);
  2426. /*
  2427. * Everyone up to our most recent fetch is covered by our grace
  2428. * period. Update the counter, but only if our work is still
  2429. * relevant -- which it won't be if someone who started later
  2430. * than we did already did their update.
  2431. */
  2432. do {
  2433. atomic_long_inc(&rsp->expedited_done_tries);
  2434. s = atomic_long_read(&rsp->expedited_done);
  2435. if (ULONG_CMP_GE((ulong)s, (ulong)snap)) {
  2436. /* ensure test happens before caller kfree */
  2437. smp_mb__before_atomic_inc(); /* ^^^ */
  2438. atomic_long_inc(&rsp->expedited_done_lost);
  2439. break;
  2440. }
  2441. } while (atomic_long_cmpxchg(&rsp->expedited_done, s, snap) != s);
  2442. atomic_long_inc(&rsp->expedited_done_exit);
  2443. put_online_cpus();
  2444. }
  2445. EXPORT_SYMBOL_GPL(synchronize_sched_expedited);
  2446. /*
  2447. * Check to see if there is any immediate RCU-related work to be done
  2448. * by the current CPU, for the specified type of RCU, returning 1 if so.
  2449. * The checks are in order of increasing expense: checks that can be
  2450. * carried out against CPU-local state are performed first. However,
  2451. * we must check for CPU stalls first, else we might not get a chance.
  2452. */
  2453. static int __rcu_pending(struct rcu_state *rsp, struct rcu_data *rdp)
  2454. {
  2455. struct rcu_node *rnp = rdp->mynode;
  2456. rdp->n_rcu_pending++;
  2457. /* Check for CPU stalls, if enabled. */
  2458. check_cpu_stall(rsp, rdp);
  2459. /* Is the RCU core waiting for a quiescent state from this CPU? */
  2460. if (rcu_scheduler_fully_active &&
  2461. rdp->qs_pending && !rdp->passed_quiesce) {
  2462. rdp->n_rp_qs_pending++;
  2463. } else if (rdp->qs_pending && rdp->passed_quiesce) {
  2464. rdp->n_rp_report_qs++;
  2465. return 1;
  2466. }
  2467. /* Does this CPU have callbacks ready to invoke? */
  2468. if (cpu_has_callbacks_ready_to_invoke(rdp)) {
  2469. rdp->n_rp_cb_ready++;
  2470. return 1;
  2471. }
  2472. /* Has RCU gone idle with this CPU needing another grace period? */
  2473. if (cpu_needs_another_gp(rsp, rdp)) {
  2474. rdp->n_rp_cpu_needs_gp++;
  2475. return 1;
  2476. }
  2477. /* Has another RCU grace period completed? */
  2478. if (ACCESS_ONCE(rnp->completed) != rdp->completed) { /* outside lock */
  2479. rdp->n_rp_gp_completed++;
  2480. return 1;
  2481. }
  2482. /* Has a new RCU grace period started? */
  2483. if (ACCESS_ONCE(rnp->gpnum) != rdp->gpnum) { /* outside lock */
  2484. rdp->n_rp_gp_started++;
  2485. return 1;
  2486. }
  2487. /* nothing to do */
  2488. rdp->n_rp_need_nothing++;
  2489. return 0;
  2490. }
  2491. /*
  2492. * Check to see if there is any immediate RCU-related work to be done
  2493. * by the current CPU, returning 1 if so. This function is part of the
  2494. * RCU implementation; it is -not- an exported member of the RCU API.
  2495. */
  2496. static int rcu_pending(int cpu)
  2497. {
  2498. struct rcu_state *rsp;
  2499. for_each_rcu_flavor(rsp)
  2500. if (__rcu_pending(rsp, per_cpu_ptr(rsp->rda, cpu)))
  2501. return 1;
  2502. return 0;
  2503. }
  2504. /*
  2505. * Return true if the specified CPU has any callback. If all_lazy is
  2506. * non-NULL, store an indication of whether all callbacks are lazy.
  2507. * (If there are no callbacks, all of them are deemed to be lazy.)
  2508. */
  2509. static int rcu_cpu_has_callbacks(int cpu, bool *all_lazy)
  2510. {
  2511. bool al = true;
  2512. bool hc = false;
  2513. struct rcu_data *rdp;
  2514. struct rcu_state *rsp;
  2515. for_each_rcu_flavor(rsp) {
  2516. rdp = per_cpu_ptr(rsp->rda, cpu);
  2517. if (rdp->qlen != rdp->qlen_lazy)
  2518. al = false;
  2519. if (rdp->nxtlist)
  2520. hc = true;
  2521. }
  2522. if (all_lazy)
  2523. *all_lazy = al;
  2524. return hc;
  2525. }
  2526. /*
  2527. * Helper function for _rcu_barrier() tracing. If tracing is disabled,
  2528. * the compiler is expected to optimize this away.
  2529. */
  2530. static void _rcu_barrier_trace(struct rcu_state *rsp, char *s,
  2531. int cpu, unsigned long done)
  2532. {
  2533. trace_rcu_barrier(rsp->name, s, cpu,
  2534. atomic_read(&rsp->barrier_cpu_count), done);
  2535. }
  2536. /*
  2537. * RCU callback function for _rcu_barrier(). If we are last, wake
  2538. * up the task executing _rcu_barrier().
  2539. */
  2540. static void rcu_barrier_callback(struct rcu_head *rhp)
  2541. {
  2542. struct rcu_data *rdp = container_of(rhp, struct rcu_data, barrier_head);
  2543. struct rcu_state *rsp = rdp->rsp;
  2544. if (atomic_dec_and_test(&rsp->barrier_cpu_count)) {
  2545. _rcu_barrier_trace(rsp, "LastCB", -1, rsp->n_barrier_done);
  2546. complete(&rsp->barrier_completion);
  2547. } else {
  2548. _rcu_barrier_trace(rsp, "CB", -1, rsp->n_barrier_done);
  2549. }
  2550. }
  2551. /*
  2552. * Called with preemption disabled, and from cross-cpu IRQ context.
  2553. */
  2554. static void rcu_barrier_func(void *type)
  2555. {
  2556. struct rcu_state *rsp = type;
  2557. struct rcu_data *rdp = __this_cpu_ptr(rsp->rda);
  2558. _rcu_barrier_trace(rsp, "IRQ", -1, rsp->n_barrier_done);
  2559. atomic_inc(&rsp->barrier_cpu_count);
  2560. rsp->call(&rdp->barrier_head, rcu_barrier_callback);
  2561. }
  2562. /*
  2563. * Orchestrate the specified type of RCU barrier, waiting for all
  2564. * RCU callbacks of the specified type to complete.
  2565. */
  2566. static void _rcu_barrier(struct rcu_state *rsp)
  2567. {
  2568. int cpu;
  2569. struct rcu_data *rdp;
  2570. unsigned long snap = ACCESS_ONCE(rsp->n_barrier_done);
  2571. unsigned long snap_done;
  2572. _rcu_barrier_trace(rsp, "Begin", -1, snap);
  2573. /* Take mutex to serialize concurrent rcu_barrier() requests. */
  2574. mutex_lock(&rsp->barrier_mutex);
  2575. /*
  2576. * Ensure that all prior references, including to ->n_barrier_done,
  2577. * are ordered before the _rcu_barrier() machinery.
  2578. */
  2579. smp_mb(); /* See above block comment. */
  2580. /*
  2581. * Recheck ->n_barrier_done to see if others did our work for us.
  2582. * This means checking ->n_barrier_done for an even-to-odd-to-even
  2583. * transition. The "if" expression below therefore rounds the old
  2584. * value up to the next even number and adds two before comparing.
  2585. */
  2586. snap_done = ACCESS_ONCE(rsp->n_barrier_done);
  2587. _rcu_barrier_trace(rsp, "Check", -1, snap_done);
  2588. if (ULONG_CMP_GE(snap_done, ((snap + 1) & ~0x1) + 2)) {
  2589. _rcu_barrier_trace(rsp, "EarlyExit", -1, snap_done);
  2590. smp_mb(); /* caller's subsequent code after above check. */
  2591. mutex_unlock(&rsp->barrier_mutex);
  2592. return;
  2593. }
  2594. /*
  2595. * Increment ->n_barrier_done to avoid duplicate work. Use
  2596. * ACCESS_ONCE() to prevent the compiler from speculating
  2597. * the increment to precede the early-exit check.
  2598. */
  2599. ACCESS_ONCE(rsp->n_barrier_done)++;
  2600. WARN_ON_ONCE((rsp->n_barrier_done & 0x1) != 1);
  2601. _rcu_barrier_trace(rsp, "Inc1", -1, rsp->n_barrier_done);
  2602. smp_mb(); /* Order ->n_barrier_done increment with below mechanism. */
  2603. /*
  2604. * Initialize the count to one rather than to zero in order to
  2605. * avoid a too-soon return to zero in case of a short grace period
  2606. * (or preemption of this task). Exclude CPU-hotplug operations
  2607. * to ensure that no offline CPU has callbacks queued.
  2608. */
  2609. init_completion(&rsp->barrier_completion);
  2610. atomic_set(&rsp->barrier_cpu_count, 1);
  2611. get_online_cpus();
  2612. /*
  2613. * Force each CPU with callbacks to register a new callback.
  2614. * When that callback is invoked, we will know that all of the
  2615. * corresponding CPU's preceding callbacks have been invoked.
  2616. */
  2617. for_each_possible_cpu(cpu) {
  2618. if (!cpu_online(cpu) && !rcu_is_nocb_cpu(cpu))
  2619. continue;
  2620. rdp = per_cpu_ptr(rsp->rda, cpu);
  2621. if (rcu_is_nocb_cpu(cpu)) {
  2622. _rcu_barrier_trace(rsp, "OnlineNoCB", cpu,
  2623. rsp->n_barrier_done);
  2624. atomic_inc(&rsp->barrier_cpu_count);
  2625. __call_rcu(&rdp->barrier_head, rcu_barrier_callback,
  2626. rsp, cpu, 0);
  2627. } else if (ACCESS_ONCE(rdp->qlen)) {
  2628. _rcu_barrier_trace(rsp, "OnlineQ", cpu,
  2629. rsp->n_barrier_done);
  2630. smp_call_function_single(cpu, rcu_barrier_func, rsp, 1);
  2631. } else {
  2632. _rcu_barrier_trace(rsp, "OnlineNQ", cpu,
  2633. rsp->n_barrier_done);
  2634. }
  2635. }
  2636. put_online_cpus();
  2637. /*
  2638. * Now that we have an rcu_barrier_callback() callback on each
  2639. * CPU, and thus each counted, remove the initial count.
  2640. */
  2641. if (atomic_dec_and_test(&rsp->barrier_cpu_count))
  2642. complete(&rsp->barrier_completion);
  2643. /* Increment ->n_barrier_done to prevent duplicate work. */
  2644. smp_mb(); /* Keep increment after above mechanism. */
  2645. ACCESS_ONCE(rsp->n_barrier_done)++;
  2646. WARN_ON_ONCE((rsp->n_barrier_done & 0x1) != 0);
  2647. _rcu_barrier_trace(rsp, "Inc2", -1, rsp->n_barrier_done);
  2648. smp_mb(); /* Keep increment before caller's subsequent code. */
  2649. /* Wait for all rcu_barrier_callback() callbacks to be invoked. */
  2650. wait_for_completion(&rsp->barrier_completion);
  2651. /* Other rcu_barrier() invocations can now safely proceed. */
  2652. mutex_unlock(&rsp->barrier_mutex);
  2653. }
  2654. /**
  2655. * rcu_barrier_bh - Wait until all in-flight call_rcu_bh() callbacks complete.
  2656. */
  2657. void rcu_barrier_bh(void)
  2658. {
  2659. _rcu_barrier(&rcu_bh_state);
  2660. }
  2661. EXPORT_SYMBOL_GPL(rcu_barrier_bh);
  2662. /**
  2663. * rcu_barrier_sched - Wait for in-flight call_rcu_sched() callbacks.
  2664. */
  2665. void rcu_barrier_sched(void)
  2666. {
  2667. _rcu_barrier(&rcu_sched_state);
  2668. }
  2669. EXPORT_SYMBOL_GPL(rcu_barrier_sched);
  2670. /*
  2671. * Do boot-time initialization of a CPU's per-CPU RCU data.
  2672. */
  2673. static void __init
  2674. rcu_boot_init_percpu_data(int cpu, struct rcu_state *rsp)
  2675. {
  2676. unsigned long flags;
  2677. struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
  2678. struct rcu_node *rnp = rcu_get_root(rsp);
  2679. /* Set up local state, ensuring consistent view of global state. */
  2680. raw_spin_lock_irqsave(&rnp->lock, flags);
  2681. rdp->grpmask = 1UL << (cpu - rdp->mynode->grplo);
  2682. init_callback_list(rdp);
  2683. rdp->qlen_lazy = 0;
  2684. ACCESS_ONCE(rdp->qlen) = 0;
  2685. rdp->dynticks = &per_cpu(rcu_dynticks, cpu);
  2686. WARN_ON_ONCE(rdp->dynticks->dynticks_nesting != DYNTICK_TASK_EXIT_IDLE);
  2687. WARN_ON_ONCE(atomic_read(&rdp->dynticks->dynticks) != 1);
  2688. rdp->cpu = cpu;
  2689. rdp->rsp = rsp;
  2690. rcu_boot_init_nocb_percpu_data(rdp);
  2691. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  2692. }
  2693. /*
  2694. * Initialize a CPU's per-CPU RCU data. Note that only one online or
  2695. * offline event can be happening at a given time. Note also that we
  2696. * can accept some slop in the rsp->completed access due to the fact
  2697. * that this CPU cannot possibly have any RCU callbacks in flight yet.
  2698. */
  2699. static void __cpuinit
  2700. rcu_init_percpu_data(int cpu, struct rcu_state *rsp, int preemptible)
  2701. {
  2702. unsigned long flags;
  2703. unsigned long mask;
  2704. struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
  2705. struct rcu_node *rnp = rcu_get_root(rsp);
  2706. /* Exclude new grace periods. */
  2707. mutex_lock(&rsp->onoff_mutex);
  2708. /* Set up local state, ensuring consistent view of global state. */
  2709. raw_spin_lock_irqsave(&rnp->lock, flags);
  2710. rdp->beenonline = 1; /* We have now been online. */
  2711. rdp->preemptible = preemptible;
  2712. rdp->qlen_last_fqs_check = 0;
  2713. rdp->n_force_qs_snap = rsp->n_force_qs;
  2714. rdp->blimit = blimit;
  2715. init_callback_list(rdp); /* Re-enable callbacks on this CPU. */
  2716. rdp->dynticks->dynticks_nesting = DYNTICK_TASK_EXIT_IDLE;
  2717. atomic_set(&rdp->dynticks->dynticks,
  2718. (atomic_read(&rdp->dynticks->dynticks) & ~0x1) + 1);
  2719. raw_spin_unlock(&rnp->lock); /* irqs remain disabled. */
  2720. /* Add CPU to rcu_node bitmasks. */
  2721. rnp = rdp->mynode;
  2722. mask = rdp->grpmask;
  2723. do {
  2724. /* Exclude any attempts to start a new GP on small systems. */
  2725. raw_spin_lock(&rnp->lock); /* irqs already disabled. */
  2726. rnp->qsmaskinit |= mask;
  2727. mask = rnp->grpmask;
  2728. if (rnp == rdp->mynode) {
  2729. /*
  2730. * If there is a grace period in progress, we will
  2731. * set up to wait for it next time we run the
  2732. * RCU core code.
  2733. */
  2734. rdp->gpnum = rnp->completed;
  2735. rdp->completed = rnp->completed;
  2736. rdp->passed_quiesce = 0;
  2737. rdp->qs_pending = 0;
  2738. trace_rcu_grace_period(rsp->name, rdp->gpnum, "cpuonl");
  2739. }
  2740. raw_spin_unlock(&rnp->lock); /* irqs already disabled. */
  2741. rnp = rnp->parent;
  2742. } while (rnp != NULL && !(rnp->qsmaskinit & mask));
  2743. local_irq_restore(flags);
  2744. mutex_unlock(&rsp->onoff_mutex);
  2745. }
  2746. static void __cpuinit rcu_prepare_cpu(int cpu)
  2747. {
  2748. struct rcu_state *rsp;
  2749. for_each_rcu_flavor(rsp)
  2750. rcu_init_percpu_data(cpu, rsp,
  2751. strcmp(rsp->name, "rcu_preempt") == 0);
  2752. }
  2753. /*
  2754. * Handle CPU online/offline notification events.
  2755. */
  2756. static int __cpuinit rcu_cpu_notify(struct notifier_block *self,
  2757. unsigned long action, void *hcpu)
  2758. {
  2759. long cpu = (long)hcpu;
  2760. struct rcu_data *rdp = per_cpu_ptr(rcu_state->rda, cpu);
  2761. struct rcu_node *rnp = rdp->mynode;
  2762. struct rcu_state *rsp;
  2763. trace_rcu_utilization("Start CPU hotplug");
  2764. switch (action) {
  2765. case CPU_UP_PREPARE:
  2766. case CPU_UP_PREPARE_FROZEN:
  2767. rcu_prepare_cpu(cpu);
  2768. rcu_prepare_kthreads(cpu);
  2769. break;
  2770. case CPU_ONLINE:
  2771. case CPU_DOWN_FAILED:
  2772. rcu_boost_kthread_setaffinity(rnp, -1);
  2773. break;
  2774. case CPU_DOWN_PREPARE:
  2775. rcu_boost_kthread_setaffinity(rnp, cpu);
  2776. break;
  2777. case CPU_DYING:
  2778. case CPU_DYING_FROZEN:
  2779. for_each_rcu_flavor(rsp)
  2780. rcu_cleanup_dying_cpu(rsp);
  2781. break;
  2782. case CPU_DEAD:
  2783. case CPU_DEAD_FROZEN:
  2784. case CPU_UP_CANCELED:
  2785. case CPU_UP_CANCELED_FROZEN:
  2786. for_each_rcu_flavor(rsp)
  2787. rcu_cleanup_dead_cpu(cpu, rsp);
  2788. break;
  2789. default:
  2790. break;
  2791. }
  2792. trace_rcu_utilization("End CPU hotplug");
  2793. return NOTIFY_OK;
  2794. }
  2795. /*
  2796. * Spawn the kthread that handles this RCU flavor's grace periods.
  2797. */
  2798. static int __init rcu_spawn_gp_kthread(void)
  2799. {
  2800. unsigned long flags;
  2801. struct rcu_node *rnp;
  2802. struct rcu_state *rsp;
  2803. struct task_struct *t;
  2804. for_each_rcu_flavor(rsp) {
  2805. t = kthread_run(rcu_gp_kthread, rsp, rsp->name);
  2806. BUG_ON(IS_ERR(t));
  2807. rnp = rcu_get_root(rsp);
  2808. raw_spin_lock_irqsave(&rnp->lock, flags);
  2809. rsp->gp_kthread = t;
  2810. raw_spin_unlock_irqrestore(&rnp->lock, flags);
  2811. rcu_spawn_nocb_kthreads(rsp);
  2812. }
  2813. return 0;
  2814. }
  2815. early_initcall(rcu_spawn_gp_kthread);
  2816. /*
  2817. * This function is invoked towards the end of the scheduler's initialization
  2818. * process. Before this is called, the idle task might contain
  2819. * RCU read-side critical sections (during which time, this idle
  2820. * task is booting the system). After this function is called, the
  2821. * idle tasks are prohibited from containing RCU read-side critical
  2822. * sections. This function also enables RCU lockdep checking.
  2823. */
  2824. void rcu_scheduler_starting(void)
  2825. {
  2826. WARN_ON(num_online_cpus() != 1);
  2827. WARN_ON(nr_context_switches() > 0);
  2828. rcu_scheduler_active = 1;
  2829. }
  2830. /*
  2831. * Compute the per-level fanout, either using the exact fanout specified
  2832. * or balancing the tree, depending on CONFIG_RCU_FANOUT_EXACT.
  2833. */
  2834. #ifdef CONFIG_RCU_FANOUT_EXACT
  2835. static void __init rcu_init_levelspread(struct rcu_state *rsp)
  2836. {
  2837. int i;
  2838. for (i = rcu_num_lvls - 1; i > 0; i--)
  2839. rsp->levelspread[i] = CONFIG_RCU_FANOUT;
  2840. rsp->levelspread[0] = rcu_fanout_leaf;
  2841. }
  2842. #else /* #ifdef CONFIG_RCU_FANOUT_EXACT */
  2843. static void __init rcu_init_levelspread(struct rcu_state *rsp)
  2844. {
  2845. int ccur;
  2846. int cprv;
  2847. int i;
  2848. cprv = nr_cpu_ids;
  2849. for (i = rcu_num_lvls - 1; i >= 0; i--) {
  2850. ccur = rsp->levelcnt[i];
  2851. rsp->levelspread[i] = (cprv + ccur - 1) / ccur;
  2852. cprv = ccur;
  2853. }
  2854. }
  2855. #endif /* #else #ifdef CONFIG_RCU_FANOUT_EXACT */
  2856. /*
  2857. * Helper function for rcu_init() that initializes one rcu_state structure.
  2858. */
  2859. static void __init rcu_init_one(struct rcu_state *rsp,
  2860. struct rcu_data __percpu *rda)
  2861. {
  2862. static char *buf[] = { "rcu_node_0",
  2863. "rcu_node_1",
  2864. "rcu_node_2",
  2865. "rcu_node_3" }; /* Match MAX_RCU_LVLS */
  2866. static char *fqs[] = { "rcu_node_fqs_0",
  2867. "rcu_node_fqs_1",
  2868. "rcu_node_fqs_2",
  2869. "rcu_node_fqs_3" }; /* Match MAX_RCU_LVLS */
  2870. int cpustride = 1;
  2871. int i;
  2872. int j;
  2873. struct rcu_node *rnp;
  2874. BUILD_BUG_ON(MAX_RCU_LVLS > ARRAY_SIZE(buf)); /* Fix buf[] init! */
  2875. /* Silence gcc 4.8 warning about array index out of range. */
  2876. if (rcu_num_lvls > RCU_NUM_LVLS)
  2877. panic("rcu_init_one: rcu_num_lvls overflow");
  2878. /* Initialize the level-tracking arrays. */
  2879. for (i = 0; i < rcu_num_lvls; i++)
  2880. rsp->levelcnt[i] = num_rcu_lvl[i];
  2881. for (i = 1; i < rcu_num_lvls; i++)
  2882. rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
  2883. rcu_init_levelspread(rsp);
  2884. /* Initialize the elements themselves, starting from the leaves. */
  2885. for (i = rcu_num_lvls - 1; i >= 0; i--) {
  2886. cpustride *= rsp->levelspread[i];
  2887. rnp = rsp->level[i];
  2888. for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) {
  2889. raw_spin_lock_init(&rnp->lock);
  2890. lockdep_set_class_and_name(&rnp->lock,
  2891. &rcu_node_class[i], buf[i]);
  2892. raw_spin_lock_init(&rnp->fqslock);
  2893. lockdep_set_class_and_name(&rnp->fqslock,
  2894. &rcu_fqs_class[i], fqs[i]);
  2895. rnp->gpnum = rsp->gpnum;
  2896. rnp->completed = rsp->completed;
  2897. rnp->qsmask = 0;
  2898. rnp->qsmaskinit = 0;
  2899. rnp->grplo = j * cpustride;
  2900. rnp->grphi = (j + 1) * cpustride - 1;
  2901. if (rnp->grphi >= NR_CPUS)
  2902. rnp->grphi = NR_CPUS - 1;
  2903. if (i == 0) {
  2904. rnp->grpnum = 0;
  2905. rnp->grpmask = 0;
  2906. rnp->parent = NULL;
  2907. } else {
  2908. rnp->grpnum = j % rsp->levelspread[i - 1];
  2909. rnp->grpmask = 1UL << rnp->grpnum;
  2910. rnp->parent = rsp->level[i - 1] +
  2911. j / rsp->levelspread[i - 1];
  2912. }
  2913. rnp->level = i;
  2914. INIT_LIST_HEAD(&rnp->blkd_tasks);
  2915. rcu_init_one_nocb(rnp);
  2916. }
  2917. }
  2918. rsp->rda = rda;
  2919. init_waitqueue_head(&rsp->gp_wq);
  2920. init_irq_work(&rsp->wakeup_work, rsp_wakeup);
  2921. rnp = rsp->level[rcu_num_lvls - 1];
  2922. for_each_possible_cpu(i) {
  2923. while (i > rnp->grphi)
  2924. rnp++;
  2925. per_cpu_ptr(rsp->rda, i)->mynode = rnp;
  2926. rcu_boot_init_percpu_data(i, rsp);
  2927. }
  2928. list_add(&rsp->flavors, &rcu_struct_flavors);
  2929. }
  2930. /*
  2931. * Compute the rcu_node tree geometry from kernel parameters. This cannot
  2932. * replace the definitions in rcutree.h because those are needed to size
  2933. * the ->node array in the rcu_state structure.
  2934. */
  2935. static void __init rcu_init_geometry(void)
  2936. {
  2937. int i;
  2938. int j;
  2939. int n = nr_cpu_ids;
  2940. int rcu_capacity[MAX_RCU_LVLS + 1];
  2941. /* If the compile-time values are accurate, just leave. */
  2942. if (rcu_fanout_leaf == CONFIG_RCU_FANOUT_LEAF &&
  2943. nr_cpu_ids == NR_CPUS)
  2944. return;
  2945. /*
  2946. * Compute number of nodes that can be handled an rcu_node tree
  2947. * with the given number of levels. Setting rcu_capacity[0] makes
  2948. * some of the arithmetic easier.
  2949. */
  2950. rcu_capacity[0] = 1;
  2951. rcu_capacity[1] = rcu_fanout_leaf;
  2952. for (i = 2; i <= MAX_RCU_LVLS; i++)
  2953. rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;
  2954. /*
  2955. * The boot-time rcu_fanout_leaf parameter is only permitted
  2956. * to increase the leaf-level fanout, not decrease it. Of course,
  2957. * the leaf-level fanout cannot exceed the number of bits in
  2958. * the rcu_node masks. Finally, the tree must be able to accommodate
  2959. * the configured number of CPUs. Complain and fall back to the
  2960. * compile-time values if these limits are exceeded.
  2961. */
  2962. if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
  2963. rcu_fanout_leaf > sizeof(unsigned long) * 8 ||
  2964. n > rcu_capacity[MAX_RCU_LVLS]) {
  2965. WARN_ON(1);
  2966. return;
  2967. }
  2968. /* Calculate the number of rcu_nodes at each level of the tree. */
  2969. for (i = 1; i <= MAX_RCU_LVLS; i++)
  2970. if (n <= rcu_capacity[i]) {
  2971. for (j = 0; j <= i; j++)
  2972. num_rcu_lvl[j] =
  2973. DIV_ROUND_UP(n, rcu_capacity[i - j]);
  2974. rcu_num_lvls = i;
  2975. for (j = i + 1; j <= MAX_RCU_LVLS; j++)
  2976. num_rcu_lvl[j] = 0;
  2977. break;
  2978. }
  2979. /* Calculate the total number of rcu_node structures. */
  2980. rcu_num_nodes = 0;
  2981. for (i = 0; i <= MAX_RCU_LVLS; i++)
  2982. rcu_num_nodes += num_rcu_lvl[i];
  2983. rcu_num_nodes -= n;
  2984. }
  2985. void __init rcu_init(void)
  2986. {
  2987. int cpu;
  2988. rcu_bootup_announce();
  2989. rcu_init_geometry();
  2990. rcu_init_one(&rcu_sched_state, &rcu_sched_data);
  2991. rcu_init_one(&rcu_bh_state, &rcu_bh_data);
  2992. __rcu_init_preempt();
  2993. open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
  2994. /*
  2995. * We don't need protection against CPU-hotplug here because
  2996. * this is called early in boot, before either interrupts
  2997. * or the scheduler are operational.
  2998. */
  2999. cpu_notifier(rcu_cpu_notify, 0);
  3000. for_each_online_cpu(cpu)
  3001. rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
  3002. }
  3003. #include "rcutree_plugin.h"