timer.c 61 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Kernel internal timers
  4. *
  5. * Copyright (C) 1991, 1992 Linus Torvalds
  6. *
  7. * 1997-01-28 Modified by Finn Arne Gangstad to make timers scale better.
  8. *
  9. * 1997-09-10 Updated NTP code according to technical memorandum Jan '96
  10. * "A Kernel Model for Precision Timekeeping" by Dave Mills
  11. * 1998-12-24 Fixed a xtime SMP race (we need the xtime_lock rw spinlock to
  12. * serialize accesses to xtime/lost_ticks).
  13. * Copyright (C) 1998 Andrea Arcangeli
  14. * 1999-03-10 Improved NTP compatibility by Ulrich Windl
  15. * 2002-05-31 Move sys_sysinfo here and make its locking sane, Robert Love
  16. * 2000-10-05 Implemented scalable SMP per-CPU timer handling.
  17. * Copyright (C) 2000, 2001, 2002 Ingo Molnar
  18. * Designed by David S. Miller, Alexey Kuznetsov and Ingo Molnar
  19. */
  20. #include <linux/kernel_stat.h>
  21. #include <linux/export.h>
  22. #include <linux/interrupt.h>
  23. #include <linux/percpu.h>
  24. #include <linux/init.h>
  25. #include <linux/mm.h>
  26. #include <linux/swap.h>
  27. #include <linux/pid_namespace.h>
  28. #include <linux/notifier.h>
  29. #include <linux/thread_info.h>
  30. #include <linux/time.h>
  31. #include <linux/jiffies.h>
  32. #include <linux/posix-timers.h>
  33. #include <linux/cpu.h>
  34. #include <linux/syscalls.h>
  35. #include <linux/delay.h>
  36. #include <linux/tick.h>
  37. #include <linux/kallsyms.h>
  38. #include <linux/irq_work.h>
  39. #include <linux/sched/signal.h>
  40. #include <linux/sched/sysctl.h>
  41. #include <linux/sched/nohz.h>
  42. #include <linux/sched/debug.h>
  43. #include <linux/slab.h>
  44. #include <linux/compat.h>
  45. #include <linux/random.h>
  46. #include <linux/uaccess.h>
  47. #include <asm/unistd.h>
  48. #include <asm/div64.h>
  49. #include <asm/timex.h>
  50. #include <asm/io.h>
  51. #include "tick-internal.h"
  52. #define CREATE_TRACE_POINTS
  53. #include <trace/events/timer.h>
  54. #undef CREATE_TRACE_POINTS
  55. #include <trace/hooks/timer.h>
  56. EXPORT_TRACEPOINT_SYMBOL_GPL(hrtimer_expire_entry);
  57. EXPORT_TRACEPOINT_SYMBOL_GPL(hrtimer_expire_exit);
  58. __visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
  59. EXPORT_SYMBOL(jiffies_64);
  60. /*
  61. * The timer wheel has LVL_DEPTH array levels. Each level provides an array of
  62. * LVL_SIZE buckets. Each level is driven by its own clock and therefor each
  63. * level has a different granularity.
  64. *
  65. * The level granularity is: LVL_CLK_DIV ^ lvl
  66. * The level clock frequency is: HZ / (LVL_CLK_DIV ^ level)
  67. *
  68. * The array level of a newly armed timer depends on the relative expiry
  69. * time. The farther the expiry time is away the higher the array level and
  70. * therefor the granularity becomes.
  71. *
  72. * Contrary to the original timer wheel implementation, which aims for 'exact'
  73. * expiry of the timers, this implementation removes the need for recascading
  74. * the timers into the lower array levels. The previous 'classic' timer wheel
  75. * implementation of the kernel already violated the 'exact' expiry by adding
  76. * slack to the expiry time to provide batched expiration. The granularity
  77. * levels provide implicit batching.
  78. *
  79. * This is an optimization of the original timer wheel implementation for the
  80. * majority of the timer wheel use cases: timeouts. The vast majority of
  81. * timeout timers (networking, disk I/O ...) are canceled before expiry. If
  82. * the timeout expires it indicates that normal operation is disturbed, so it
  83. * does not matter much whether the timeout comes with a slight delay.
  84. *
  85. * The only exception to this are networking timers with a small expiry
  86. * time. They rely on the granularity. Those fit into the first wheel level,
  87. * which has HZ granularity.
  88. *
  89. * We don't have cascading anymore. timers with a expiry time above the
  90. * capacity of the last wheel level are force expired at the maximum timeout
  91. * value of the last wheel level. From data sampling we know that the maximum
  92. * value observed is 5 days (network connection tracking), so this should not
  93. * be an issue.
  94. *
  95. * The currently chosen array constants values are a good compromise between
  96. * array size and granularity.
  97. *
  98. * This results in the following granularity and range levels:
  99. *
  100. * HZ 1000 steps
  101. * Level Offset Granularity Range
  102. * 0 0 1 ms 0 ms - 63 ms
  103. * 1 64 8 ms 64 ms - 511 ms
  104. * 2 128 64 ms 512 ms - 4095 ms (512ms - ~4s)
  105. * 3 192 512 ms 4096 ms - 32767 ms (~4s - ~32s)
  106. * 4 256 4096 ms (~4s) 32768 ms - 262143 ms (~32s - ~4m)
  107. * 5 320 32768 ms (~32s) 262144 ms - 2097151 ms (~4m - ~34m)
  108. * 6 384 262144 ms (~4m) 2097152 ms - 16777215 ms (~34m - ~4h)
  109. * 7 448 2097152 ms (~34m) 16777216 ms - 134217727 ms (~4h - ~1d)
  110. * 8 512 16777216 ms (~4h) 134217728 ms - 1073741822 ms (~1d - ~12d)
  111. *
  112. * HZ 300
  113. * Level Offset Granularity Range
  114. * 0 0 3 ms 0 ms - 210 ms
  115. * 1 64 26 ms 213 ms - 1703 ms (213ms - ~1s)
  116. * 2 128 213 ms 1706 ms - 13650 ms (~1s - ~13s)
  117. * 3 192 1706 ms (~1s) 13653 ms - 109223 ms (~13s - ~1m)
  118. * 4 256 13653 ms (~13s) 109226 ms - 873810 ms (~1m - ~14m)
  119. * 5 320 109226 ms (~1m) 873813 ms - 6990503 ms (~14m - ~1h)
  120. * 6 384 873813 ms (~14m) 6990506 ms - 55924050 ms (~1h - ~15h)
  121. * 7 448 6990506 ms (~1h) 55924053 ms - 447392423 ms (~15h - ~5d)
  122. * 8 512 55924053 ms (~15h) 447392426 ms - 3579139406 ms (~5d - ~41d)
  123. *
  124. * HZ 250
  125. * Level Offset Granularity Range
  126. * 0 0 4 ms 0 ms - 255 ms
  127. * 1 64 32 ms 256 ms - 2047 ms (256ms - ~2s)
  128. * 2 128 256 ms 2048 ms - 16383 ms (~2s - ~16s)
  129. * 3 192 2048 ms (~2s) 16384 ms - 131071 ms (~16s - ~2m)
  130. * 4 256 16384 ms (~16s) 131072 ms - 1048575 ms (~2m - ~17m)
  131. * 5 320 131072 ms (~2m) 1048576 ms - 8388607 ms (~17m - ~2h)
  132. * 6 384 1048576 ms (~17m) 8388608 ms - 67108863 ms (~2h - ~18h)
  133. * 7 448 8388608 ms (~2h) 67108864 ms - 536870911 ms (~18h - ~6d)
  134. * 8 512 67108864 ms (~18h) 536870912 ms - 4294967288 ms (~6d - ~49d)
  135. *
  136. * HZ 100
  137. * Level Offset Granularity Range
  138. * 0 0 10 ms 0 ms - 630 ms
  139. * 1 64 80 ms 640 ms - 5110 ms (640ms - ~5s)
  140. * 2 128 640 ms 5120 ms - 40950 ms (~5s - ~40s)
  141. * 3 192 5120 ms (~5s) 40960 ms - 327670 ms (~40s - ~5m)
  142. * 4 256 40960 ms (~40s) 327680 ms - 2621430 ms (~5m - ~43m)
  143. * 5 320 327680 ms (~5m) 2621440 ms - 20971510 ms (~43m - ~5h)
  144. * 6 384 2621440 ms (~43m) 20971520 ms - 167772150 ms (~5h - ~1d)
  145. * 7 448 20971520 ms (~5h) 167772160 ms - 1342177270 ms (~1d - ~15d)
  146. */
  147. /* Clock divisor for the next level */
  148. #define LVL_CLK_SHIFT 3
  149. #define LVL_CLK_DIV (1UL << LVL_CLK_SHIFT)
  150. #define LVL_CLK_MASK (LVL_CLK_DIV - 1)
  151. #define LVL_SHIFT(n) ((n) * LVL_CLK_SHIFT)
  152. #define LVL_GRAN(n) (1UL << LVL_SHIFT(n))
  153. /*
  154. * The time start value for each level to select the bucket at enqueue
  155. * time. We start from the last possible delta of the previous level
  156. * so that we can later add an extra LVL_GRAN(n) to n (see calc_index()).
  157. */
  158. #define LVL_START(n) ((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT))
  159. /* Size of each clock level */
  160. #define LVL_BITS 6
  161. #define LVL_SIZE (1UL << LVL_BITS)
  162. #define LVL_MASK (LVL_SIZE - 1)
  163. #define LVL_OFFS(n) ((n) * LVL_SIZE)
  164. /* Level depth */
  165. #if HZ > 100
  166. # define LVL_DEPTH 9
  167. # else
  168. # define LVL_DEPTH 8
  169. #endif
  170. /* The cutoff (max. capacity of the wheel) */
  171. #define WHEEL_TIMEOUT_CUTOFF (LVL_START(LVL_DEPTH))
  172. #define WHEEL_TIMEOUT_MAX (WHEEL_TIMEOUT_CUTOFF - LVL_GRAN(LVL_DEPTH - 1))
  173. /*
  174. * The resulting wheel size. If NOHZ is configured we allocate two
  175. * wheels so we have a separate storage for the deferrable timers.
  176. */
  177. #define WHEEL_SIZE (LVL_SIZE * LVL_DEPTH)
  178. #ifdef CONFIG_NO_HZ_COMMON
  179. # define NR_BASES 2
  180. # define BASE_STD 0
  181. # define BASE_DEF 1
  182. #else
  183. # define NR_BASES 1
  184. # define BASE_STD 0
  185. # define BASE_DEF 0
  186. #endif
  187. struct timer_base {
  188. raw_spinlock_t lock;
  189. struct timer_list *running_timer;
  190. #ifdef CONFIG_PREEMPT_RT
  191. spinlock_t expiry_lock;
  192. atomic_t timer_waiters;
  193. #endif
  194. unsigned long clk;
  195. unsigned long next_expiry;
  196. unsigned int cpu;
  197. bool next_expiry_recalc;
  198. bool is_idle;
  199. bool timers_pending;
  200. DECLARE_BITMAP(pending_map, WHEEL_SIZE);
  201. struct hlist_head vectors[WHEEL_SIZE];
  202. } ____cacheline_aligned;
  203. static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
  204. #ifdef CONFIG_NO_HZ_COMMON
  205. static DEFINE_STATIC_KEY_FALSE(timers_nohz_active);
  206. static DEFINE_MUTEX(timer_keys_mutex);
  207. static void timer_update_keys(struct work_struct *work);
  208. static DECLARE_WORK(timer_update_work, timer_update_keys);
  209. #ifdef CONFIG_SMP
  210. unsigned int sysctl_timer_migration = 1;
  211. DEFINE_STATIC_KEY_FALSE(timers_migration_enabled);
  212. static void timers_update_migration(void)
  213. {
  214. if (sysctl_timer_migration && tick_nohz_active)
  215. static_branch_enable(&timers_migration_enabled);
  216. else
  217. static_branch_disable(&timers_migration_enabled);
  218. }
  219. #else
  220. static inline void timers_update_migration(void) { }
  221. #endif /* !CONFIG_SMP */
  222. static void timer_update_keys(struct work_struct *work)
  223. {
  224. mutex_lock(&timer_keys_mutex);
  225. timers_update_migration();
  226. static_branch_enable(&timers_nohz_active);
  227. mutex_unlock(&timer_keys_mutex);
  228. }
  229. void timers_update_nohz(void)
  230. {
  231. schedule_work(&timer_update_work);
  232. }
  233. int timer_migration_handler(struct ctl_table *table, int write,
  234. void *buffer, size_t *lenp, loff_t *ppos)
  235. {
  236. int ret;
  237. mutex_lock(&timer_keys_mutex);
  238. ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
  239. if (!ret && write)
  240. timers_update_migration();
  241. mutex_unlock(&timer_keys_mutex);
  242. return ret;
  243. }
  244. static inline bool is_timers_nohz_active(void)
  245. {
  246. return static_branch_unlikely(&timers_nohz_active);
  247. }
  248. #else
  249. static inline bool is_timers_nohz_active(void) { return false; }
  250. #endif /* NO_HZ_COMMON */
  251. static unsigned long round_jiffies_common(unsigned long j, int cpu,
  252. bool force_up)
  253. {
  254. int rem;
  255. unsigned long original = j;
  256. /*
  257. * We don't want all cpus firing their timers at once hitting the
  258. * same lock or cachelines, so we skew each extra cpu with an extra
  259. * 3 jiffies. This 3 jiffies came originally from the mm/ code which
  260. * already did this.
  261. * The skew is done by adding 3*cpunr, then round, then subtract this
  262. * extra offset again.
  263. */
  264. j += cpu * 3;
  265. rem = j % HZ;
  266. /*
  267. * If the target jiffie is just after a whole second (which can happen
  268. * due to delays of the timer irq, long irq off times etc etc) then
  269. * we should round down to the whole second, not up. Use 1/4th second
  270. * as cutoff for this rounding as an extreme upper bound for this.
  271. * But never round down if @force_up is set.
  272. */
  273. if (rem < HZ/4 && !force_up) /* round down */
  274. j = j - rem;
  275. else /* round up */
  276. j = j - rem + HZ;
  277. /* now that we have rounded, subtract the extra skew again */
  278. j -= cpu * 3;
  279. /*
  280. * Make sure j is still in the future. Otherwise return the
  281. * unmodified value.
  282. */
  283. return time_is_after_jiffies(j) ? j : original;
  284. }
  285. /**
  286. * __round_jiffies - function to round jiffies to a full second
  287. * @j: the time in (absolute) jiffies that should be rounded
  288. * @cpu: the processor number on which the timeout will happen
  289. *
  290. * __round_jiffies() rounds an absolute time in the future (in jiffies)
  291. * up or down to (approximately) full seconds. This is useful for timers
  292. * for which the exact time they fire does not matter too much, as long as
  293. * they fire approximately every X seconds.
  294. *
  295. * By rounding these timers to whole seconds, all such timers will fire
  296. * at the same time, rather than at various times spread out. The goal
  297. * of this is to have the CPU wake up less, which saves power.
  298. *
  299. * The exact rounding is skewed for each processor to avoid all
  300. * processors firing at the exact same time, which could lead
  301. * to lock contention or spurious cache line bouncing.
  302. *
  303. * The return value is the rounded version of the @j parameter.
  304. */
  305. unsigned long __round_jiffies(unsigned long j, int cpu)
  306. {
  307. return round_jiffies_common(j, cpu, false);
  308. }
  309. EXPORT_SYMBOL_GPL(__round_jiffies);
  310. /**
  311. * __round_jiffies_relative - function to round jiffies to a full second
  312. * @j: the time in (relative) jiffies that should be rounded
  313. * @cpu: the processor number on which the timeout will happen
  314. *
  315. * __round_jiffies_relative() rounds a time delta in the future (in jiffies)
  316. * up or down to (approximately) full seconds. This is useful for timers
  317. * for which the exact time they fire does not matter too much, as long as
  318. * they fire approximately every X seconds.
  319. *
  320. * By rounding these timers to whole seconds, all such timers will fire
  321. * at the same time, rather than at various times spread out. The goal
  322. * of this is to have the CPU wake up less, which saves power.
  323. *
  324. * The exact rounding is skewed for each processor to avoid all
  325. * processors firing at the exact same time, which could lead
  326. * to lock contention or spurious cache line bouncing.
  327. *
  328. * The return value is the rounded version of the @j parameter.
  329. */
  330. unsigned long __round_jiffies_relative(unsigned long j, int cpu)
  331. {
  332. unsigned long j0 = jiffies;
  333. /* Use j0 because jiffies might change while we run */
  334. return round_jiffies_common(j + j0, cpu, false) - j0;
  335. }
  336. EXPORT_SYMBOL_GPL(__round_jiffies_relative);
  337. /**
  338. * round_jiffies - function to round jiffies to a full second
  339. * @j: the time in (absolute) jiffies that should be rounded
  340. *
  341. * round_jiffies() rounds an absolute time in the future (in jiffies)
  342. * up or down to (approximately) full seconds. This is useful for timers
  343. * for which the exact time they fire does not matter too much, as long as
  344. * they fire approximately every X seconds.
  345. *
  346. * By rounding these timers to whole seconds, all such timers will fire
  347. * at the same time, rather than at various times spread out. The goal
  348. * of this is to have the CPU wake up less, which saves power.
  349. *
  350. * The return value is the rounded version of the @j parameter.
  351. */
  352. unsigned long round_jiffies(unsigned long j)
  353. {
  354. return round_jiffies_common(j, raw_smp_processor_id(), false);
  355. }
  356. EXPORT_SYMBOL_GPL(round_jiffies);
  357. /**
  358. * round_jiffies_relative - function to round jiffies to a full second
  359. * @j: the time in (relative) jiffies that should be rounded
  360. *
  361. * round_jiffies_relative() rounds a time delta in the future (in jiffies)
  362. * up or down to (approximately) full seconds. This is useful for timers
  363. * for which the exact time they fire does not matter too much, as long as
  364. * they fire approximately every X seconds.
  365. *
  366. * By rounding these timers to whole seconds, all such timers will fire
  367. * at the same time, rather than at various times spread out. The goal
  368. * of this is to have the CPU wake up less, which saves power.
  369. *
  370. * The return value is the rounded version of the @j parameter.
  371. */
  372. unsigned long round_jiffies_relative(unsigned long j)
  373. {
  374. return __round_jiffies_relative(j, raw_smp_processor_id());
  375. }
  376. EXPORT_SYMBOL_GPL(round_jiffies_relative);
  377. /**
  378. * __round_jiffies_up - function to round jiffies up to a full second
  379. * @j: the time in (absolute) jiffies that should be rounded
  380. * @cpu: the processor number on which the timeout will happen
  381. *
  382. * This is the same as __round_jiffies() except that it will never
  383. * round down. This is useful for timeouts for which the exact time
  384. * of firing does not matter too much, as long as they don't fire too
  385. * early.
  386. */
  387. unsigned long __round_jiffies_up(unsigned long j, int cpu)
  388. {
  389. return round_jiffies_common(j, cpu, true);
  390. }
  391. EXPORT_SYMBOL_GPL(__round_jiffies_up);
  392. /**
  393. * __round_jiffies_up_relative - function to round jiffies up to a full second
  394. * @j: the time in (relative) jiffies that should be rounded
  395. * @cpu: the processor number on which the timeout will happen
  396. *
  397. * This is the same as __round_jiffies_relative() except that it will never
  398. * round down. This is useful for timeouts for which the exact time
  399. * of firing does not matter too much, as long as they don't fire too
  400. * early.
  401. */
  402. unsigned long __round_jiffies_up_relative(unsigned long j, int cpu)
  403. {
  404. unsigned long j0 = jiffies;
  405. /* Use j0 because jiffies might change while we run */
  406. return round_jiffies_common(j + j0, cpu, true) - j0;
  407. }
  408. EXPORT_SYMBOL_GPL(__round_jiffies_up_relative);
  409. /**
  410. * round_jiffies_up - function to round jiffies up to a full second
  411. * @j: the time in (absolute) jiffies that should be rounded
  412. *
  413. * This is the same as round_jiffies() except that it will never
  414. * round down. This is useful for timeouts for which the exact time
  415. * of firing does not matter too much, as long as they don't fire too
  416. * early.
  417. */
  418. unsigned long round_jiffies_up(unsigned long j)
  419. {
  420. return round_jiffies_common(j, raw_smp_processor_id(), true);
  421. }
  422. EXPORT_SYMBOL_GPL(round_jiffies_up);
  423. /**
  424. * round_jiffies_up_relative - function to round jiffies up to a full second
  425. * @j: the time in (relative) jiffies that should be rounded
  426. *
  427. * This is the same as round_jiffies_relative() except that it will never
  428. * round down. This is useful for timeouts for which the exact time
  429. * of firing does not matter too much, as long as they don't fire too
  430. * early.
  431. */
  432. unsigned long round_jiffies_up_relative(unsigned long j)
  433. {
  434. return __round_jiffies_up_relative(j, raw_smp_processor_id());
  435. }
  436. EXPORT_SYMBOL_GPL(round_jiffies_up_relative);
  437. static inline unsigned int timer_get_idx(struct timer_list *timer)
  438. {
  439. return (timer->flags & TIMER_ARRAYMASK) >> TIMER_ARRAYSHIFT;
  440. }
  441. static inline void timer_set_idx(struct timer_list *timer, unsigned int idx)
  442. {
  443. timer->flags = (timer->flags & ~TIMER_ARRAYMASK) |
  444. idx << TIMER_ARRAYSHIFT;
  445. }
  446. /*
  447. * Helper function to calculate the array index for a given expiry
  448. * time.
  449. */
  450. static inline unsigned calc_index(unsigned long expires, unsigned lvl,
  451. unsigned long *bucket_expiry)
  452. {
  453. /*
  454. * The timer wheel has to guarantee that a timer does not fire
  455. * early. Early expiry can happen due to:
  456. * - Timer is armed at the edge of a tick
  457. * - Truncation of the expiry time in the outer wheel levels
  458. *
  459. * Round up with level granularity to prevent this.
  460. */
  461. trace_android_vh_timer_calc_index(lvl, &expires);
  462. expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
  463. *bucket_expiry = expires << LVL_SHIFT(lvl);
  464. return LVL_OFFS(lvl) + (expires & LVL_MASK);
  465. }
  466. static int calc_wheel_index(unsigned long expires, unsigned long clk,
  467. unsigned long *bucket_expiry)
  468. {
  469. unsigned long delta = expires - clk;
  470. unsigned int idx;
  471. if (delta < LVL_START(1)) {
  472. idx = calc_index(expires, 0, bucket_expiry);
  473. } else if (delta < LVL_START(2)) {
  474. idx = calc_index(expires, 1, bucket_expiry);
  475. } else if (delta < LVL_START(3)) {
  476. idx = calc_index(expires, 2, bucket_expiry);
  477. } else if (delta < LVL_START(4)) {
  478. idx = calc_index(expires, 3, bucket_expiry);
  479. } else if (delta < LVL_START(5)) {
  480. idx = calc_index(expires, 4, bucket_expiry);
  481. } else if (delta < LVL_START(6)) {
  482. idx = calc_index(expires, 5, bucket_expiry);
  483. } else if (delta < LVL_START(7)) {
  484. idx = calc_index(expires, 6, bucket_expiry);
  485. } else if (LVL_DEPTH > 8 && delta < LVL_START(8)) {
  486. idx = calc_index(expires, 7, bucket_expiry);
  487. } else if ((long) delta < 0) {
  488. idx = clk & LVL_MASK;
  489. *bucket_expiry = clk;
  490. } else {
  491. /*
  492. * Force expire obscene large timeouts to expire at the
  493. * capacity limit of the wheel.
  494. */
  495. if (delta >= WHEEL_TIMEOUT_CUTOFF)
  496. expires = clk + WHEEL_TIMEOUT_MAX;
  497. idx = calc_index(expires, LVL_DEPTH - 1, bucket_expiry);
  498. }
  499. return idx;
  500. }
  501. static void
  502. trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
  503. {
  504. if (!is_timers_nohz_active())
  505. return;
  506. /*
  507. * TODO: This wants some optimizing similar to the code below, but we
  508. * will do that when we switch from push to pull for deferrable timers.
  509. */
  510. if (timer->flags & TIMER_DEFERRABLE) {
  511. if (tick_nohz_full_cpu(base->cpu))
  512. wake_up_nohz_cpu(base->cpu);
  513. return;
  514. }
  515. /*
  516. * We might have to IPI the remote CPU if the base is idle and the
  517. * timer is not deferrable. If the other CPU is on the way to idle
  518. * then it can't set base->is_idle as we hold the base lock:
  519. */
  520. if (base->is_idle)
  521. wake_up_nohz_cpu(base->cpu);
  522. }
  523. /*
  524. * Enqueue the timer into the hash bucket, mark it pending in
  525. * the bitmap, store the index in the timer flags then wake up
  526. * the target CPU if needed.
  527. */
  528. static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
  529. unsigned int idx, unsigned long bucket_expiry)
  530. {
  531. hlist_add_head(&timer->entry, base->vectors + idx);
  532. __set_bit(idx, base->pending_map);
  533. timer_set_idx(timer, idx);
  534. trace_timer_start(timer, timer->expires, timer->flags);
  535. /*
  536. * Check whether this is the new first expiring timer. The
  537. * effective expiry time of the timer is required here
  538. * (bucket_expiry) instead of timer->expires.
  539. */
  540. if (time_before(bucket_expiry, base->next_expiry)) {
  541. /*
  542. * Set the next expiry time and kick the CPU so it
  543. * can reevaluate the wheel:
  544. */
  545. base->next_expiry = bucket_expiry;
  546. base->timers_pending = true;
  547. base->next_expiry_recalc = false;
  548. trigger_dyntick_cpu(base, timer);
  549. }
  550. }
  551. static void internal_add_timer(struct timer_base *base, struct timer_list *timer)
  552. {
  553. unsigned long bucket_expiry;
  554. unsigned int idx;
  555. idx = calc_wheel_index(timer->expires, base->clk, &bucket_expiry);
  556. enqueue_timer(base, timer, idx, bucket_expiry);
  557. }
  558. #ifdef CONFIG_DEBUG_OBJECTS_TIMERS
  559. static const struct debug_obj_descr timer_debug_descr;
  560. static void *timer_debug_hint(void *addr)
  561. {
  562. return ((struct timer_list *) addr)->function;
  563. }
  564. static bool timer_is_static_object(void *addr)
  565. {
  566. struct timer_list *timer = addr;
  567. return (timer->entry.pprev == NULL &&
  568. timer->entry.next == TIMER_ENTRY_STATIC);
  569. }
  570. /*
  571. * fixup_init is called when:
  572. * - an active object is initialized
  573. */
  574. static bool timer_fixup_init(void *addr, enum debug_obj_state state)
  575. {
  576. struct timer_list *timer = addr;
  577. switch (state) {
  578. case ODEBUG_STATE_ACTIVE:
  579. del_timer_sync(timer);
  580. debug_object_init(timer, &timer_debug_descr);
  581. return true;
  582. default:
  583. return false;
  584. }
  585. }
  586. /* Stub timer callback for improperly used timers. */
  587. static void stub_timer(struct timer_list *unused)
  588. {
  589. WARN_ON(1);
  590. }
  591. /*
  592. * fixup_activate is called when:
  593. * - an active object is activated
  594. * - an unknown non-static object is activated
  595. */
  596. static bool timer_fixup_activate(void *addr, enum debug_obj_state state)
  597. {
  598. struct timer_list *timer = addr;
  599. switch (state) {
  600. case ODEBUG_STATE_NOTAVAILABLE:
  601. timer_setup(timer, stub_timer, 0);
  602. return true;
  603. case ODEBUG_STATE_ACTIVE:
  604. WARN_ON(1);
  605. fallthrough;
  606. default:
  607. return false;
  608. }
  609. }
  610. /*
  611. * fixup_free is called when:
  612. * - an active object is freed
  613. */
  614. static bool timer_fixup_free(void *addr, enum debug_obj_state state)
  615. {
  616. struct timer_list *timer = addr;
  617. switch (state) {
  618. case ODEBUG_STATE_ACTIVE:
  619. del_timer_sync(timer);
  620. debug_object_free(timer, &timer_debug_descr);
  621. return true;
  622. default:
  623. return false;
  624. }
  625. }
  626. /*
  627. * fixup_assert_init is called when:
  628. * - an untracked/uninit-ed object is found
  629. */
  630. static bool timer_fixup_assert_init(void *addr, enum debug_obj_state state)
  631. {
  632. struct timer_list *timer = addr;
  633. switch (state) {
  634. case ODEBUG_STATE_NOTAVAILABLE:
  635. timer_setup(timer, stub_timer, 0);
  636. return true;
  637. default:
  638. return false;
  639. }
  640. }
  641. static const struct debug_obj_descr timer_debug_descr = {
  642. .name = "timer_list",
  643. .debug_hint = timer_debug_hint,
  644. .is_static_object = timer_is_static_object,
  645. .fixup_init = timer_fixup_init,
  646. .fixup_activate = timer_fixup_activate,
  647. .fixup_free = timer_fixup_free,
  648. .fixup_assert_init = timer_fixup_assert_init,
  649. };
  650. static inline void debug_timer_init(struct timer_list *timer)
  651. {
  652. debug_object_init(timer, &timer_debug_descr);
  653. }
  654. static inline void debug_timer_activate(struct timer_list *timer)
  655. {
  656. debug_object_activate(timer, &timer_debug_descr);
  657. }
  658. static inline void debug_timer_deactivate(struct timer_list *timer)
  659. {
  660. debug_object_deactivate(timer, &timer_debug_descr);
  661. }
  662. static inline void debug_timer_assert_init(struct timer_list *timer)
  663. {
  664. debug_object_assert_init(timer, &timer_debug_descr);
  665. }
  666. static void do_init_timer(struct timer_list *timer,
  667. void (*func)(struct timer_list *),
  668. unsigned int flags,
  669. const char *name, struct lock_class_key *key);
  670. void init_timer_on_stack_key(struct timer_list *timer,
  671. void (*func)(struct timer_list *),
  672. unsigned int flags,
  673. const char *name, struct lock_class_key *key)
  674. {
  675. debug_object_init_on_stack(timer, &timer_debug_descr);
  676. do_init_timer(timer, func, flags, name, key);
  677. }
  678. EXPORT_SYMBOL_GPL(init_timer_on_stack_key);
  679. void destroy_timer_on_stack(struct timer_list *timer)
  680. {
  681. debug_object_free(timer, &timer_debug_descr);
  682. }
  683. EXPORT_SYMBOL_GPL(destroy_timer_on_stack);
  684. #else
  685. static inline void debug_timer_init(struct timer_list *timer) { }
  686. static inline void debug_timer_activate(struct timer_list *timer) { }
  687. static inline void debug_timer_deactivate(struct timer_list *timer) { }
  688. static inline void debug_timer_assert_init(struct timer_list *timer) { }
  689. #endif
  690. static inline void debug_init(struct timer_list *timer)
  691. {
  692. debug_timer_init(timer);
  693. trace_timer_init(timer);
  694. }
  695. static inline void debug_deactivate(struct timer_list *timer)
  696. {
  697. debug_timer_deactivate(timer);
  698. trace_timer_cancel(timer);
  699. }
  700. static inline void debug_assert_init(struct timer_list *timer)
  701. {
  702. debug_timer_assert_init(timer);
  703. }
  704. static void do_init_timer(struct timer_list *timer,
  705. void (*func)(struct timer_list *),
  706. unsigned int flags,
  707. const char *name, struct lock_class_key *key)
  708. {
  709. timer->entry.pprev = NULL;
  710. timer->function = func;
  711. if (WARN_ON_ONCE(flags & ~TIMER_INIT_FLAGS))
  712. flags &= TIMER_INIT_FLAGS;
  713. timer->flags = flags | raw_smp_processor_id();
  714. lockdep_init_map(&timer->lockdep_map, name, key, 0);
  715. }
  716. /**
  717. * init_timer_key - initialize a timer
  718. * @timer: the timer to be initialized
  719. * @func: timer callback function
  720. * @flags: timer flags
  721. * @name: name of the timer
  722. * @key: lockdep class key of the fake lock used for tracking timer
  723. * sync lock dependencies
  724. *
  725. * init_timer_key() must be done to a timer prior calling *any* of the
  726. * other timer functions.
  727. */
  728. void init_timer_key(struct timer_list *timer,
  729. void (*func)(struct timer_list *), unsigned int flags,
  730. const char *name, struct lock_class_key *key)
  731. {
  732. debug_init(timer);
  733. do_init_timer(timer, func, flags, name, key);
  734. }
  735. EXPORT_SYMBOL(init_timer_key);
  736. static inline void detach_timer(struct timer_list *timer, bool clear_pending)
  737. {
  738. struct hlist_node *entry = &timer->entry;
  739. debug_deactivate(timer);
  740. __hlist_del(entry);
  741. if (clear_pending)
  742. entry->pprev = NULL;
  743. entry->next = LIST_POISON2;
  744. }
  745. static int detach_if_pending(struct timer_list *timer, struct timer_base *base,
  746. bool clear_pending)
  747. {
  748. unsigned idx = timer_get_idx(timer);
  749. if (!timer_pending(timer))
  750. return 0;
  751. if (hlist_is_singular_node(&timer->entry, base->vectors + idx)) {
  752. __clear_bit(idx, base->pending_map);
  753. base->next_expiry_recalc = true;
  754. }
  755. detach_timer(timer, clear_pending);
  756. return 1;
  757. }
  758. static inline struct timer_base *get_timer_cpu_base(u32 tflags, u32 cpu)
  759. {
  760. struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_STD], cpu);
  761. /*
  762. * If the timer is deferrable and NO_HZ_COMMON is set then we need
  763. * to use the deferrable base.
  764. */
  765. if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
  766. base = per_cpu_ptr(&timer_bases[BASE_DEF], cpu);
  767. return base;
  768. }
  769. static inline struct timer_base *get_timer_this_cpu_base(u32 tflags)
  770. {
  771. struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
  772. /*
  773. * If the timer is deferrable and NO_HZ_COMMON is set then we need
  774. * to use the deferrable base.
  775. */
  776. if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
  777. base = this_cpu_ptr(&timer_bases[BASE_DEF]);
  778. return base;
  779. }
  780. static inline struct timer_base *get_timer_base(u32 tflags)
  781. {
  782. return get_timer_cpu_base(tflags, tflags & TIMER_CPUMASK);
  783. }
  784. static inline struct timer_base *
  785. get_target_base(struct timer_base *base, unsigned tflags)
  786. {
  787. #if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON)
  788. if (static_branch_likely(&timers_migration_enabled) &&
  789. !(tflags & TIMER_PINNED))
  790. return get_timer_cpu_base(tflags, get_nohz_timer_target());
  791. #endif
  792. return get_timer_this_cpu_base(tflags);
  793. }
  794. static inline void forward_timer_base(struct timer_base *base)
  795. {
  796. unsigned long jnow = READ_ONCE(jiffies);
  797. /*
  798. * No need to forward if we are close enough below jiffies.
  799. * Also while executing timers, base->clk is 1 offset ahead
  800. * of jiffies to avoid endless requeuing to current jffies.
  801. */
  802. if ((long)(jnow - base->clk) < 1)
  803. return;
  804. /*
  805. * If the next expiry value is > jiffies, then we fast forward to
  806. * jiffies otherwise we forward to the next expiry value.
  807. */
  808. if (time_after(base->next_expiry, jnow)) {
  809. base->clk = jnow;
  810. } else {
  811. if (WARN_ON_ONCE(time_before(base->next_expiry, base->clk)))
  812. return;
  813. base->clk = base->next_expiry;
  814. }
  815. }
  816. /*
  817. * We are using hashed locking: Holding per_cpu(timer_bases[x]).lock means
  818. * that all timers which are tied to this base are locked, and the base itself
  819. * is locked too.
  820. *
  821. * So __run_timers/migrate_timers can safely modify all timers which could
  822. * be found in the base->vectors array.
  823. *
  824. * When a timer is migrating then the TIMER_MIGRATING flag is set and we need
  825. * to wait until the migration is done.
  826. */
  827. static struct timer_base *lock_timer_base(struct timer_list *timer,
  828. unsigned long *flags)
  829. __acquires(timer->base->lock)
  830. {
  831. for (;;) {
  832. struct timer_base *base;
  833. u32 tf;
  834. /*
  835. * We need to use READ_ONCE() here, otherwise the compiler
  836. * might re-read @tf between the check for TIMER_MIGRATING
  837. * and spin_lock().
  838. */
  839. tf = READ_ONCE(timer->flags);
  840. if (!(tf & TIMER_MIGRATING)) {
  841. base = get_timer_base(tf);
  842. raw_spin_lock_irqsave(&base->lock, *flags);
  843. if (timer->flags == tf)
  844. return base;
  845. raw_spin_unlock_irqrestore(&base->lock, *flags);
  846. }
  847. cpu_relax();
  848. }
  849. }
  850. #define MOD_TIMER_PENDING_ONLY 0x01
  851. #define MOD_TIMER_REDUCE 0x02
  852. #define MOD_TIMER_NOTPENDING 0x04
  853. static inline int
  854. __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int options)
  855. {
  856. unsigned long clk = 0, flags, bucket_expiry;
  857. struct timer_base *base, *new_base;
  858. unsigned int idx = UINT_MAX;
  859. int ret = 0;
  860. BUG_ON(!timer->function);
  861. /*
  862. * This is a common optimization triggered by the networking code - if
  863. * the timer is re-modified to have the same timeout or ends up in the
  864. * same array bucket then just return:
  865. */
  866. if (!(options & MOD_TIMER_NOTPENDING) && timer_pending(timer)) {
  867. /*
  868. * The downside of this optimization is that it can result in
  869. * larger granularity than you would get from adding a new
  870. * timer with this expiry.
  871. */
  872. long diff = timer->expires - expires;
  873. if (!diff)
  874. return 1;
  875. if (options & MOD_TIMER_REDUCE && diff <= 0)
  876. return 1;
  877. /*
  878. * We lock timer base and calculate the bucket index right
  879. * here. If the timer ends up in the same bucket, then we
  880. * just update the expiry time and avoid the whole
  881. * dequeue/enqueue dance.
  882. */
  883. base = lock_timer_base(timer, &flags);
  884. forward_timer_base(base);
  885. if (timer_pending(timer) && (options & MOD_TIMER_REDUCE) &&
  886. time_before_eq(timer->expires, expires)) {
  887. ret = 1;
  888. goto out_unlock;
  889. }
  890. clk = base->clk;
  891. idx = calc_wheel_index(expires, clk, &bucket_expiry);
  892. /*
  893. * Retrieve and compare the array index of the pending
  894. * timer. If it matches set the expiry to the new value so a
  895. * subsequent call will exit in the expires check above.
  896. */
  897. if (idx == timer_get_idx(timer)) {
  898. if (!(options & MOD_TIMER_REDUCE))
  899. timer->expires = expires;
  900. else if (time_after(timer->expires, expires))
  901. timer->expires = expires;
  902. ret = 1;
  903. goto out_unlock;
  904. }
  905. } else {
  906. base = lock_timer_base(timer, &flags);
  907. forward_timer_base(base);
  908. }
  909. ret = detach_if_pending(timer, base, false);
  910. if (!ret && (options & MOD_TIMER_PENDING_ONLY))
  911. goto out_unlock;
  912. new_base = get_target_base(base, timer->flags);
  913. if (base != new_base) {
  914. /*
  915. * We are trying to schedule the timer on the new base.
  916. * However we can't change timer's base while it is running,
  917. * otherwise del_timer_sync() can't detect that the timer's
  918. * handler yet has not finished. This also guarantees that the
  919. * timer is serialized wrt itself.
  920. */
  921. if (likely(base->running_timer != timer)) {
  922. /* See the comment in lock_timer_base() */
  923. timer->flags |= TIMER_MIGRATING;
  924. raw_spin_unlock(&base->lock);
  925. base = new_base;
  926. raw_spin_lock(&base->lock);
  927. WRITE_ONCE(timer->flags,
  928. (timer->flags & ~TIMER_BASEMASK) | base->cpu);
  929. forward_timer_base(base);
  930. }
  931. }
  932. debug_timer_activate(timer);
  933. timer->expires = expires;
  934. /*
  935. * If 'idx' was calculated above and the base time did not advance
  936. * between calculating 'idx' and possibly switching the base, only
  937. * enqueue_timer() is required. Otherwise we need to (re)calculate
  938. * the wheel index via internal_add_timer().
  939. */
  940. if (idx != UINT_MAX && clk == base->clk)
  941. enqueue_timer(base, timer, idx, bucket_expiry);
  942. else
  943. internal_add_timer(base, timer);
  944. out_unlock:
  945. raw_spin_unlock_irqrestore(&base->lock, flags);
  946. return ret;
  947. }
  948. /**
  949. * mod_timer_pending - modify a pending timer's timeout
  950. * @timer: the pending timer to be modified
  951. * @expires: new timeout in jiffies
  952. *
  953. * mod_timer_pending() is the same for pending timers as mod_timer(),
  954. * but will not re-activate and modify already deleted timers.
  955. *
  956. * It is useful for unserialized use of timers.
  957. */
  958. int mod_timer_pending(struct timer_list *timer, unsigned long expires)
  959. {
  960. return __mod_timer(timer, expires, MOD_TIMER_PENDING_ONLY);
  961. }
  962. EXPORT_SYMBOL(mod_timer_pending);
  963. /**
  964. * mod_timer - modify a timer's timeout
  965. * @timer: the timer to be modified
  966. * @expires: new timeout in jiffies
  967. *
  968. * mod_timer() is a more efficient way to update the expire field of an
  969. * active timer (if the timer is inactive it will be activated)
  970. *
  971. * mod_timer(timer, expires) is equivalent to:
  972. *
  973. * del_timer(timer); timer->expires = expires; add_timer(timer);
  974. *
  975. * Note that if there are multiple unserialized concurrent users of the
  976. * same timer, then mod_timer() is the only safe way to modify the timeout,
  977. * since add_timer() cannot modify an already running timer.
  978. *
  979. * The function returns whether it has modified a pending timer or not.
  980. * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
  981. * active timer returns 1.)
  982. */
  983. int mod_timer(struct timer_list *timer, unsigned long expires)
  984. {
  985. return __mod_timer(timer, expires, 0);
  986. }
  987. EXPORT_SYMBOL(mod_timer);
  988. /**
  989. * timer_reduce - Modify a timer's timeout if it would reduce the timeout
  990. * @timer: The timer to be modified
  991. * @expires: New timeout in jiffies
  992. *
  993. * timer_reduce() is very similar to mod_timer(), except that it will only
  994. * modify a running timer if that would reduce the expiration time (it will
  995. * start a timer that isn't running).
  996. */
  997. int timer_reduce(struct timer_list *timer, unsigned long expires)
  998. {
  999. return __mod_timer(timer, expires, MOD_TIMER_REDUCE);
  1000. }
  1001. EXPORT_SYMBOL(timer_reduce);
  1002. /**
  1003. * add_timer - start a timer
  1004. * @timer: the timer to be added
  1005. *
  1006. * The kernel will do a ->function(@timer) callback from the
  1007. * timer interrupt at the ->expires point in the future. The
  1008. * current time is 'jiffies'.
  1009. *
  1010. * The timer's ->expires, ->function fields must be set prior calling this
  1011. * function.
  1012. *
  1013. * Timers with an ->expires field in the past will be executed in the next
  1014. * timer tick.
  1015. */
  1016. void add_timer(struct timer_list *timer)
  1017. {
  1018. BUG_ON(timer_pending(timer));
  1019. __mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
  1020. }
  1021. EXPORT_SYMBOL(add_timer);
  1022. /**
  1023. * add_timer_on - start a timer on a particular CPU
  1024. * @timer: the timer to be added
  1025. * @cpu: the CPU to start it on
  1026. *
  1027. * This is not very scalable on SMP. Double adds are not possible.
  1028. */
  1029. void add_timer_on(struct timer_list *timer, int cpu)
  1030. {
  1031. struct timer_base *new_base, *base;
  1032. unsigned long flags;
  1033. BUG_ON(timer_pending(timer) || !timer->function);
  1034. new_base = get_timer_cpu_base(timer->flags, cpu);
  1035. /*
  1036. * If @timer was on a different CPU, it should be migrated with the
  1037. * old base locked to prevent other operations proceeding with the
  1038. * wrong base locked. See lock_timer_base().
  1039. */
  1040. base = lock_timer_base(timer, &flags);
  1041. if (base != new_base) {
  1042. timer->flags |= TIMER_MIGRATING;
  1043. raw_spin_unlock(&base->lock);
  1044. base = new_base;
  1045. raw_spin_lock(&base->lock);
  1046. WRITE_ONCE(timer->flags,
  1047. (timer->flags & ~TIMER_BASEMASK) | cpu);
  1048. }
  1049. forward_timer_base(base);
  1050. debug_timer_activate(timer);
  1051. internal_add_timer(base, timer);
  1052. raw_spin_unlock_irqrestore(&base->lock, flags);
  1053. }
  1054. EXPORT_SYMBOL_GPL(add_timer_on);
  1055. /**
  1056. * del_timer - deactivate a timer.
  1057. * @timer: the timer to be deactivated
  1058. *
  1059. * del_timer() deactivates a timer - this works on both active and inactive
  1060. * timers.
  1061. *
  1062. * The function returns whether it has deactivated a pending timer or not.
  1063. * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
  1064. * active timer returns 1.)
  1065. */
  1066. int del_timer(struct timer_list *timer)
  1067. {
  1068. struct timer_base *base;
  1069. unsigned long flags;
  1070. int ret = 0;
  1071. debug_assert_init(timer);
  1072. if (timer_pending(timer)) {
  1073. base = lock_timer_base(timer, &flags);
  1074. ret = detach_if_pending(timer, base, true);
  1075. raw_spin_unlock_irqrestore(&base->lock, flags);
  1076. }
  1077. return ret;
  1078. }
  1079. EXPORT_SYMBOL(del_timer);
  1080. /**
  1081. * try_to_del_timer_sync - Try to deactivate a timer
  1082. * @timer: timer to delete
  1083. *
  1084. * This function tries to deactivate a timer. Upon successful (ret >= 0)
  1085. * exit the timer is not queued and the handler is not running on any CPU.
  1086. */
  1087. int try_to_del_timer_sync(struct timer_list *timer)
  1088. {
  1089. struct timer_base *base;
  1090. unsigned long flags;
  1091. int ret = -1;
  1092. debug_assert_init(timer);
  1093. base = lock_timer_base(timer, &flags);
  1094. if (base->running_timer != timer)
  1095. ret = detach_if_pending(timer, base, true);
  1096. raw_spin_unlock_irqrestore(&base->lock, flags);
  1097. return ret;
  1098. }
  1099. EXPORT_SYMBOL(try_to_del_timer_sync);
  1100. #ifdef CONFIG_PREEMPT_RT
  1101. static __init void timer_base_init_expiry_lock(struct timer_base *base)
  1102. {
  1103. spin_lock_init(&base->expiry_lock);
  1104. }
  1105. static inline void timer_base_lock_expiry(struct timer_base *base)
  1106. {
  1107. spin_lock(&base->expiry_lock);
  1108. }
  1109. static inline void timer_base_unlock_expiry(struct timer_base *base)
  1110. {
  1111. spin_unlock(&base->expiry_lock);
  1112. }
  1113. /*
  1114. * The counterpart to del_timer_wait_running().
  1115. *
  1116. * If there is a waiter for base->expiry_lock, then it was waiting for the
  1117. * timer callback to finish. Drop expiry_lock and reaquire it. That allows
  1118. * the waiter to acquire the lock and make progress.
  1119. */
  1120. static void timer_sync_wait_running(struct timer_base *base)
  1121. {
  1122. if (atomic_read(&base->timer_waiters)) {
  1123. raw_spin_unlock_irq(&base->lock);
  1124. spin_unlock(&base->expiry_lock);
  1125. spin_lock(&base->expiry_lock);
  1126. raw_spin_lock_irq(&base->lock);
  1127. }
  1128. }
  1129. /*
  1130. * This function is called on PREEMPT_RT kernels when the fast path
  1131. * deletion of a timer failed because the timer callback function was
  1132. * running.
  1133. *
  1134. * This prevents priority inversion, if the softirq thread on a remote CPU
  1135. * got preempted, and it prevents a life lock when the task which tries to
  1136. * delete a timer preempted the softirq thread running the timer callback
  1137. * function.
  1138. */
  1139. static void del_timer_wait_running(struct timer_list *timer)
  1140. {
  1141. u32 tf;
  1142. tf = READ_ONCE(timer->flags);
  1143. if (!(tf & TIMER_MIGRATING)) {
  1144. struct timer_base *base = get_timer_base(tf);
  1145. /*
  1146. * Mark the base as contended and grab the expiry lock,
  1147. * which is held by the softirq across the timer
  1148. * callback. Drop the lock immediately so the softirq can
  1149. * expire the next timer. In theory the timer could already
  1150. * be running again, but that's more than unlikely and just
  1151. * causes another wait loop.
  1152. */
  1153. atomic_inc(&base->timer_waiters);
  1154. spin_lock_bh(&base->expiry_lock);
  1155. atomic_dec(&base->timer_waiters);
  1156. spin_unlock_bh(&base->expiry_lock);
  1157. }
  1158. }
  1159. #else
  1160. static inline void timer_base_init_expiry_lock(struct timer_base *base) { }
  1161. static inline void timer_base_lock_expiry(struct timer_base *base) { }
  1162. static inline void timer_base_unlock_expiry(struct timer_base *base) { }
  1163. static inline void timer_sync_wait_running(struct timer_base *base) { }
  1164. static inline void del_timer_wait_running(struct timer_list *timer) { }
  1165. #endif
  1166. #if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT_RT)
  1167. /**
  1168. * del_timer_sync - deactivate a timer and wait for the handler to finish.
  1169. * @timer: the timer to be deactivated
  1170. *
  1171. * This function only differs from del_timer() on SMP: besides deactivating
  1172. * the timer it also makes sure the handler has finished executing on other
  1173. * CPUs.
  1174. *
  1175. * Synchronization rules: Callers must prevent restarting of the timer,
  1176. * otherwise this function is meaningless. It must not be called from
  1177. * interrupt contexts unless the timer is an irqsafe one. The caller must
  1178. * not hold locks which would prevent completion of the timer's
  1179. * handler. The timer's handler must not call add_timer_on(). Upon exit the
  1180. * timer is not queued and the handler is not running on any CPU.
  1181. *
  1182. * Note: For !irqsafe timers, you must not hold locks that are held in
  1183. * interrupt context while calling this function. Even if the lock has
  1184. * nothing to do with the timer in question. Here's why::
  1185. *
  1186. * CPU0 CPU1
  1187. * ---- ----
  1188. * <SOFTIRQ>
  1189. * call_timer_fn();
  1190. * base->running_timer = mytimer;
  1191. * spin_lock_irq(somelock);
  1192. * <IRQ>
  1193. * spin_lock(somelock);
  1194. * del_timer_sync(mytimer);
  1195. * while (base->running_timer == mytimer);
  1196. *
  1197. * Now del_timer_sync() will never return and never release somelock.
  1198. * The interrupt on the other CPU is waiting to grab somelock but
  1199. * it has interrupted the softirq that CPU0 is waiting to finish.
  1200. *
  1201. * The function returns whether it has deactivated a pending timer or not.
  1202. */
  1203. int del_timer_sync(struct timer_list *timer)
  1204. {
  1205. int ret;
  1206. #ifdef CONFIG_LOCKDEP
  1207. unsigned long flags;
  1208. /*
  1209. * If lockdep gives a backtrace here, please reference
  1210. * the synchronization rules above.
  1211. */
  1212. local_irq_save(flags);
  1213. lock_map_acquire(&timer->lockdep_map);
  1214. lock_map_release(&timer->lockdep_map);
  1215. local_irq_restore(flags);
  1216. #endif
  1217. /*
  1218. * don't use it in hardirq context, because it
  1219. * could lead to deadlock.
  1220. */
  1221. WARN_ON(in_irq() && !(timer->flags & TIMER_IRQSAFE));
  1222. do {
  1223. ret = try_to_del_timer_sync(timer);
  1224. if (unlikely(ret < 0)) {
  1225. del_timer_wait_running(timer);
  1226. cpu_relax();
  1227. }
  1228. } while (ret < 0);
  1229. return ret;
  1230. }
  1231. EXPORT_SYMBOL(del_timer_sync);
  1232. #endif
  1233. static void call_timer_fn(struct timer_list *timer,
  1234. void (*fn)(struct timer_list *),
  1235. unsigned long baseclk)
  1236. {
  1237. int count = preempt_count();
  1238. #ifdef CONFIG_LOCKDEP
  1239. /*
  1240. * It is permissible to free the timer from inside the
  1241. * function that is called from it, this we need to take into
  1242. * account for lockdep too. To avoid bogus "held lock freed"
  1243. * warnings as well as problems when looking into
  1244. * timer->lockdep_map, make a copy and use that here.
  1245. */
  1246. struct lockdep_map lockdep_map;
  1247. lockdep_copy_map(&lockdep_map, &timer->lockdep_map);
  1248. #endif
  1249. /*
  1250. * Couple the lock chain with the lock chain at
  1251. * del_timer_sync() by acquiring the lock_map around the fn()
  1252. * call here and in del_timer_sync().
  1253. */
  1254. lock_map_acquire(&lockdep_map);
  1255. trace_timer_expire_entry(timer, baseclk);
  1256. fn(timer);
  1257. trace_timer_expire_exit(timer);
  1258. lock_map_release(&lockdep_map);
  1259. if (count != preempt_count()) {
  1260. WARN_ONCE(1, "timer: %pS preempt leak: %08x -> %08x\n",
  1261. fn, count, preempt_count());
  1262. /*
  1263. * Restore the preempt count. That gives us a decent
  1264. * chance to survive and extract information. If the
  1265. * callback kept a lock held, bad luck, but not worse
  1266. * than the BUG() we had.
  1267. */
  1268. preempt_count_set(count);
  1269. }
  1270. }
  1271. static void expire_timers(struct timer_base *base, struct hlist_head *head)
  1272. {
  1273. /*
  1274. * This value is required only for tracing. base->clk was
  1275. * incremented directly before expire_timers was called. But expiry
  1276. * is related to the old base->clk value.
  1277. */
  1278. unsigned long baseclk = base->clk - 1;
  1279. while (!hlist_empty(head)) {
  1280. struct timer_list *timer;
  1281. void (*fn)(struct timer_list *);
  1282. timer = hlist_entry(head->first, struct timer_list, entry);
  1283. base->running_timer = timer;
  1284. detach_timer(timer, true);
  1285. fn = timer->function;
  1286. if (timer->flags & TIMER_IRQSAFE) {
  1287. raw_spin_unlock(&base->lock);
  1288. call_timer_fn(timer, fn, baseclk);
  1289. raw_spin_lock(&base->lock);
  1290. base->running_timer = NULL;
  1291. } else {
  1292. raw_spin_unlock_irq(&base->lock);
  1293. call_timer_fn(timer, fn, baseclk);
  1294. raw_spin_lock_irq(&base->lock);
  1295. base->running_timer = NULL;
  1296. timer_sync_wait_running(base);
  1297. }
  1298. }
  1299. }
  1300. static int collect_expired_timers(struct timer_base *base,
  1301. struct hlist_head *heads)
  1302. {
  1303. unsigned long clk = base->clk = base->next_expiry;
  1304. struct hlist_head *vec;
  1305. int i, levels = 0;
  1306. unsigned int idx;
  1307. for (i = 0; i < LVL_DEPTH; i++) {
  1308. idx = (clk & LVL_MASK) + i * LVL_SIZE;
  1309. if (__test_and_clear_bit(idx, base->pending_map)) {
  1310. vec = base->vectors + idx;
  1311. hlist_move_list(vec, heads++);
  1312. levels++;
  1313. }
  1314. /* Is it time to look at the next level? */
  1315. if (clk & LVL_CLK_MASK)
  1316. break;
  1317. /* Shift clock for the next level granularity */
  1318. clk >>= LVL_CLK_SHIFT;
  1319. }
  1320. return levels;
  1321. }
  1322. /*
  1323. * Find the next pending bucket of a level. Search from level start (@offset)
  1324. * + @clk upwards and if nothing there, search from start of the level
  1325. * (@offset) up to @offset + clk.
  1326. */
  1327. static int next_pending_bucket(struct timer_base *base, unsigned offset,
  1328. unsigned clk)
  1329. {
  1330. unsigned pos, start = offset + clk;
  1331. unsigned end = offset + LVL_SIZE;
  1332. pos = find_next_bit(base->pending_map, end, start);
  1333. if (pos < end)
  1334. return pos - start;
  1335. pos = find_next_bit(base->pending_map, start, offset);
  1336. return pos < start ? pos + LVL_SIZE - start : -1;
  1337. }
  1338. /*
  1339. * Search the first expiring timer in the various clock levels. Caller must
  1340. * hold base->lock.
  1341. */
  1342. static unsigned long __next_timer_interrupt(struct timer_base *base)
  1343. {
  1344. unsigned long clk, next, adj;
  1345. unsigned lvl, offset = 0;
  1346. next = base->clk + NEXT_TIMER_MAX_DELTA;
  1347. clk = base->clk;
  1348. for (lvl = 0; lvl < LVL_DEPTH; lvl++, offset += LVL_SIZE) {
  1349. int pos = next_pending_bucket(base, offset, clk & LVL_MASK);
  1350. unsigned long lvl_clk = clk & LVL_CLK_MASK;
  1351. if (pos >= 0) {
  1352. unsigned long tmp = clk + (unsigned long) pos;
  1353. tmp <<= LVL_SHIFT(lvl);
  1354. if (time_before(tmp, next))
  1355. next = tmp;
  1356. /*
  1357. * If the next expiration happens before we reach
  1358. * the next level, no need to check further.
  1359. */
  1360. if (pos <= ((LVL_CLK_DIV - lvl_clk) & LVL_CLK_MASK))
  1361. break;
  1362. }
  1363. /*
  1364. * Clock for the next level. If the current level clock lower
  1365. * bits are zero, we look at the next level as is. If not we
  1366. * need to advance it by one because that's going to be the
  1367. * next expiring bucket in that level. base->clk is the next
  1368. * expiring jiffie. So in case of:
  1369. *
  1370. * LVL5 LVL4 LVL3 LVL2 LVL1 LVL0
  1371. * 0 0 0 0 0 0
  1372. *
  1373. * we have to look at all levels @index 0. With
  1374. *
  1375. * LVL5 LVL4 LVL3 LVL2 LVL1 LVL0
  1376. * 0 0 0 0 0 2
  1377. *
  1378. * LVL0 has the next expiring bucket @index 2. The upper
  1379. * levels have the next expiring bucket @index 1.
  1380. *
  1381. * In case that the propagation wraps the next level the same
  1382. * rules apply:
  1383. *
  1384. * LVL5 LVL4 LVL3 LVL2 LVL1 LVL0
  1385. * 0 0 0 0 F 2
  1386. *
  1387. * So after looking at LVL0 we get:
  1388. *
  1389. * LVL5 LVL4 LVL3 LVL2 LVL1
  1390. * 0 0 0 1 0
  1391. *
  1392. * So no propagation from LVL1 to LVL2 because that happened
  1393. * with the add already, but then we need to propagate further
  1394. * from LVL2 to LVL3.
  1395. *
  1396. * So the simple check whether the lower bits of the current
  1397. * level are 0 or not is sufficient for all cases.
  1398. */
  1399. adj = lvl_clk ? 1 : 0;
  1400. clk >>= LVL_CLK_SHIFT;
  1401. clk += adj;
  1402. }
  1403. base->next_expiry_recalc = false;
  1404. base->timers_pending = !(next == base->clk + NEXT_TIMER_MAX_DELTA);
  1405. return next;
  1406. }
  1407. #ifdef CONFIG_NO_HZ_COMMON
  1408. /*
  1409. * Check, if the next hrtimer event is before the next timer wheel
  1410. * event:
  1411. */
  1412. static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
  1413. {
  1414. u64 nextevt = hrtimer_get_next_event();
  1415. /*
  1416. * If high resolution timers are enabled
  1417. * hrtimer_get_next_event() returns KTIME_MAX.
  1418. */
  1419. if (expires <= nextevt)
  1420. return expires;
  1421. /*
  1422. * If the next timer is already expired, return the tick base
  1423. * time so the tick is fired immediately.
  1424. */
  1425. if (nextevt <= basem)
  1426. return basem;
  1427. /*
  1428. * Round up to the next jiffie. High resolution timers are
  1429. * off, so the hrtimers are expired in the tick and we need to
  1430. * make sure that this tick really expires the timer to avoid
  1431. * a ping pong of the nohz stop code.
  1432. *
  1433. * Use DIV_ROUND_UP_ULL to prevent gcc calling __divdi3
  1434. */
  1435. return DIV_ROUND_UP_ULL(nextevt, TICK_NSEC) * TICK_NSEC;
  1436. }
  1437. /**
  1438. * get_next_timer_interrupt - return the time (clock mono) of the next timer
  1439. * @basej: base time jiffies
  1440. * @basem: base time clock monotonic
  1441. *
  1442. * Returns the tick aligned clock monotonic time of the next pending
  1443. * timer or KTIME_MAX if no timer is pending.
  1444. */
  1445. u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
  1446. {
  1447. struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
  1448. u64 expires = KTIME_MAX;
  1449. unsigned long nextevt;
  1450. /*
  1451. * Pretend that there is no timer pending if the cpu is offline.
  1452. * Possible pending timers will be migrated later to an active cpu.
  1453. */
  1454. if (cpu_is_offline(smp_processor_id()))
  1455. return expires;
  1456. raw_spin_lock(&base->lock);
  1457. if (base->next_expiry_recalc)
  1458. base->next_expiry = __next_timer_interrupt(base);
  1459. nextevt = base->next_expiry;
  1460. /*
  1461. * We have a fresh next event. Check whether we can forward the
  1462. * base. We can only do that when @basej is past base->clk
  1463. * otherwise we might rewind base->clk.
  1464. */
  1465. if (time_after(basej, base->clk)) {
  1466. if (time_after(nextevt, basej))
  1467. base->clk = basej;
  1468. else if (time_after(nextevt, base->clk))
  1469. base->clk = nextevt;
  1470. }
  1471. if (time_before_eq(nextevt, basej)) {
  1472. expires = basem;
  1473. base->is_idle = false;
  1474. } else {
  1475. if (base->timers_pending)
  1476. expires = basem + (u64)(nextevt - basej) * TICK_NSEC;
  1477. /*
  1478. * If we expect to sleep more than a tick, mark the base idle.
  1479. * Also the tick is stopped so any added timer must forward
  1480. * the base clk itself to keep granularity small. This idle
  1481. * logic is only maintained for the BASE_STD base, deferrable
  1482. * timers may still see large granularity skew (by design).
  1483. */
  1484. if ((expires - basem) > TICK_NSEC)
  1485. base->is_idle = true;
  1486. }
  1487. raw_spin_unlock(&base->lock);
  1488. return cmp_next_hrtimer_event(basem, expires);
  1489. }
  1490. /**
  1491. * timer_clear_idle - Clear the idle state of the timer base
  1492. *
  1493. * Called with interrupts disabled
  1494. */
  1495. void timer_clear_idle(void)
  1496. {
  1497. struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
  1498. /*
  1499. * We do this unlocked. The worst outcome is a remote enqueue sending
  1500. * a pointless IPI, but taking the lock would just make the window for
  1501. * sending the IPI a few instructions smaller for the cost of taking
  1502. * the lock in the exit from idle path.
  1503. */
  1504. base->is_idle = false;
  1505. }
  1506. #endif
  1507. /*
  1508. * Called from the timer interrupt handler to charge one tick to the current
  1509. * process. user_tick is 1 if the tick is user time, 0 for system.
  1510. */
  1511. void update_process_times(int user_tick)
  1512. {
  1513. struct task_struct *p = current;
  1514. PRANDOM_ADD_NOISE(jiffies, user_tick, p, 0);
  1515. /* Note: this timer irq context must be accounted for as well. */
  1516. account_process_tick(p, user_tick);
  1517. run_local_timers();
  1518. rcu_sched_clock_irq(user_tick);
  1519. #ifdef CONFIG_IRQ_WORK
  1520. if (in_irq())
  1521. irq_work_tick();
  1522. #endif
  1523. scheduler_tick();
  1524. if (IS_ENABLED(CONFIG_POSIX_TIMERS))
  1525. run_posix_cpu_timers();
  1526. }
  1527. /**
  1528. * __run_timers - run all expired timers (if any) on this CPU.
  1529. * @base: the timer vector to be processed.
  1530. */
  1531. static inline void __run_timers(struct timer_base *base)
  1532. {
  1533. struct hlist_head heads[LVL_DEPTH];
  1534. int levels;
  1535. if (time_before(jiffies, base->next_expiry))
  1536. return;
  1537. timer_base_lock_expiry(base);
  1538. raw_spin_lock_irq(&base->lock);
  1539. while (time_after_eq(jiffies, base->clk) &&
  1540. time_after_eq(jiffies, base->next_expiry)) {
  1541. levels = collect_expired_timers(base, heads);
  1542. /*
  1543. * The two possible reasons for not finding any expired
  1544. * timer at this clk are that all matching timers have been
  1545. * dequeued or no timer has been queued since
  1546. * base::next_expiry was set to base::clk +
  1547. * NEXT_TIMER_MAX_DELTA.
  1548. */
  1549. WARN_ON_ONCE(!levels && !base->next_expiry_recalc
  1550. && base->timers_pending);
  1551. base->clk++;
  1552. base->next_expiry = __next_timer_interrupt(base);
  1553. while (levels--)
  1554. expire_timers(base, heads + levels);
  1555. }
  1556. raw_spin_unlock_irq(&base->lock);
  1557. timer_base_unlock_expiry(base);
  1558. }
  1559. /*
  1560. * This function runs timers and the timer-tq in bottom half context.
  1561. */
  1562. static __latent_entropy void run_timer_softirq(struct softirq_action *h)
  1563. {
  1564. struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
  1565. __run_timers(base);
  1566. if (IS_ENABLED(CONFIG_NO_HZ_COMMON))
  1567. __run_timers(this_cpu_ptr(&timer_bases[BASE_DEF]));
  1568. }
  1569. /*
  1570. * Called by the local, per-CPU timer interrupt on SMP.
  1571. */
  1572. void run_local_timers(void)
  1573. {
  1574. struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
  1575. hrtimer_run_queues();
  1576. /* Raise the softirq only if required. */
  1577. if (time_before(jiffies, base->next_expiry)) {
  1578. if (!IS_ENABLED(CONFIG_NO_HZ_COMMON))
  1579. return;
  1580. /* CPU is awake, so check the deferrable base. */
  1581. base++;
  1582. if (time_before(jiffies, base->next_expiry))
  1583. return;
  1584. }
  1585. raise_softirq(TIMER_SOFTIRQ);
  1586. }
  1587. /*
  1588. * Since schedule_timeout()'s timer is defined on the stack, it must store
  1589. * the target task on the stack as well.
  1590. */
  1591. struct process_timer {
  1592. struct timer_list timer;
  1593. struct task_struct *task;
  1594. };
  1595. static void process_timeout(struct timer_list *t)
  1596. {
  1597. struct process_timer *timeout = from_timer(timeout, t, timer);
  1598. wake_up_process(timeout->task);
  1599. }
  1600. /**
  1601. * schedule_timeout - sleep until timeout
  1602. * @timeout: timeout value in jiffies
  1603. *
  1604. * Make the current task sleep until @timeout jiffies have elapsed.
  1605. * The function behavior depends on the current task state
  1606. * (see also set_current_state() description):
  1607. *
  1608. * %TASK_RUNNING - the scheduler is called, but the task does not sleep
  1609. * at all. That happens because sched_submit_work() does nothing for
  1610. * tasks in %TASK_RUNNING state.
  1611. *
  1612. * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
  1613. * pass before the routine returns unless the current task is explicitly
  1614. * woken up, (e.g. by wake_up_process()).
  1615. *
  1616. * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
  1617. * delivered to the current task or the current task is explicitly woken
  1618. * up.
  1619. *
  1620. * The current task state is guaranteed to be %TASK_RUNNING when this
  1621. * routine returns.
  1622. *
  1623. * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
  1624. * the CPU away without a bound on the timeout. In this case the return
  1625. * value will be %MAX_SCHEDULE_TIMEOUT.
  1626. *
  1627. * Returns 0 when the timer has expired otherwise the remaining time in
  1628. * jiffies will be returned. In all cases the return value is guaranteed
  1629. * to be non-negative.
  1630. */
  1631. signed long __sched schedule_timeout(signed long timeout)
  1632. {
  1633. struct process_timer timer;
  1634. unsigned long expire;
  1635. switch (timeout)
  1636. {
  1637. case MAX_SCHEDULE_TIMEOUT:
  1638. /*
  1639. * These two special cases are useful to be comfortable
  1640. * in the caller. Nothing more. We could take
  1641. * MAX_SCHEDULE_TIMEOUT from one of the negative value
  1642. * but I' d like to return a valid offset (>=0) to allow
  1643. * the caller to do everything it want with the retval.
  1644. */
  1645. schedule();
  1646. goto out;
  1647. default:
  1648. /*
  1649. * Another bit of PARANOID. Note that the retval will be
  1650. * 0 since no piece of kernel is supposed to do a check
  1651. * for a negative retval of schedule_timeout() (since it
  1652. * should never happens anyway). You just have the printk()
  1653. * that will tell you if something is gone wrong and where.
  1654. */
  1655. if (timeout < 0) {
  1656. printk(KERN_ERR "schedule_timeout: wrong timeout "
  1657. "value %lx\n", timeout);
  1658. dump_stack();
  1659. current->state = TASK_RUNNING;
  1660. goto out;
  1661. }
  1662. }
  1663. expire = timeout + jiffies;
  1664. timer.task = current;
  1665. timer_setup_on_stack(&timer.timer, process_timeout, 0);
  1666. __mod_timer(&timer.timer, expire, MOD_TIMER_NOTPENDING);
  1667. schedule();
  1668. del_singleshot_timer_sync(&timer.timer);
  1669. /* Remove the timer from the object tracker */
  1670. destroy_timer_on_stack(&timer.timer);
  1671. timeout = expire - jiffies;
  1672. out:
  1673. return timeout < 0 ? 0 : timeout;
  1674. }
  1675. EXPORT_SYMBOL(schedule_timeout);
  1676. /*
  1677. * We can use __set_current_state() here because schedule_timeout() calls
  1678. * schedule() unconditionally.
  1679. */
  1680. signed long __sched schedule_timeout_interruptible(signed long timeout)
  1681. {
  1682. __set_current_state(TASK_INTERRUPTIBLE);
  1683. return schedule_timeout(timeout);
  1684. }
  1685. EXPORT_SYMBOL(schedule_timeout_interruptible);
  1686. signed long __sched schedule_timeout_killable(signed long timeout)
  1687. {
  1688. __set_current_state(TASK_KILLABLE);
  1689. return schedule_timeout(timeout);
  1690. }
  1691. EXPORT_SYMBOL(schedule_timeout_killable);
  1692. signed long __sched schedule_timeout_uninterruptible(signed long timeout)
  1693. {
  1694. __set_current_state(TASK_UNINTERRUPTIBLE);
  1695. return schedule_timeout(timeout);
  1696. }
  1697. EXPORT_SYMBOL(schedule_timeout_uninterruptible);
  1698. /*
  1699. * Like schedule_timeout_uninterruptible(), except this task will not contribute
  1700. * to load average.
  1701. */
  1702. signed long __sched schedule_timeout_idle(signed long timeout)
  1703. {
  1704. __set_current_state(TASK_IDLE);
  1705. return schedule_timeout(timeout);
  1706. }
  1707. EXPORT_SYMBOL(schedule_timeout_idle);
  1708. #ifdef CONFIG_HOTPLUG_CPU
  1709. static void migrate_timer_list(struct timer_base *new_base, struct hlist_head *head)
  1710. {
  1711. struct timer_list *timer;
  1712. int cpu = new_base->cpu;
  1713. while (!hlist_empty(head)) {
  1714. timer = hlist_entry(head->first, struct timer_list, entry);
  1715. detach_timer(timer, false);
  1716. timer->flags = (timer->flags & ~TIMER_BASEMASK) | cpu;
  1717. internal_add_timer(new_base, timer);
  1718. }
  1719. }
  1720. int timers_prepare_cpu(unsigned int cpu)
  1721. {
  1722. struct timer_base *base;
  1723. int b;
  1724. for (b = 0; b < NR_BASES; b++) {
  1725. base = per_cpu_ptr(&timer_bases[b], cpu);
  1726. base->clk = jiffies;
  1727. base->next_expiry = base->clk + NEXT_TIMER_MAX_DELTA;
  1728. base->timers_pending = false;
  1729. base->is_idle = false;
  1730. }
  1731. return 0;
  1732. }
  1733. int timers_dead_cpu(unsigned int cpu)
  1734. {
  1735. struct timer_base *old_base;
  1736. struct timer_base *new_base;
  1737. int b, i;
  1738. BUG_ON(cpu_online(cpu));
  1739. for (b = 0; b < NR_BASES; b++) {
  1740. old_base = per_cpu_ptr(&timer_bases[b], cpu);
  1741. new_base = get_cpu_ptr(&timer_bases[b]);
  1742. /*
  1743. * The caller is globally serialized and nobody else
  1744. * takes two locks at once, deadlock is not possible.
  1745. */
  1746. raw_spin_lock_irq(&new_base->lock);
  1747. raw_spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING);
  1748. /*
  1749. * The current CPUs base clock might be stale. Update it
  1750. * before moving the timers over.
  1751. */
  1752. forward_timer_base(new_base);
  1753. BUG_ON(old_base->running_timer);
  1754. for (i = 0; i < WHEEL_SIZE; i++)
  1755. migrate_timer_list(new_base, old_base->vectors + i);
  1756. raw_spin_unlock(&old_base->lock);
  1757. raw_spin_unlock_irq(&new_base->lock);
  1758. put_cpu_ptr(&timer_bases);
  1759. }
  1760. return 0;
  1761. }
  1762. #endif /* CONFIG_HOTPLUG_CPU */
  1763. static void __init init_timer_cpu(int cpu)
  1764. {
  1765. struct timer_base *base;
  1766. int i;
  1767. for (i = 0; i < NR_BASES; i++) {
  1768. base = per_cpu_ptr(&timer_bases[i], cpu);
  1769. base->cpu = cpu;
  1770. raw_spin_lock_init(&base->lock);
  1771. base->clk = jiffies;
  1772. base->next_expiry = base->clk + NEXT_TIMER_MAX_DELTA;
  1773. timer_base_init_expiry_lock(base);
  1774. }
  1775. }
  1776. static void __init init_timer_cpus(void)
  1777. {
  1778. int cpu;
  1779. for_each_possible_cpu(cpu)
  1780. init_timer_cpu(cpu);
  1781. }
  1782. void __init init_timers(void)
  1783. {
  1784. init_timer_cpus();
  1785. posix_cputimers_init_work();
  1786. open_softirq(TIMER_SOFTIRQ, run_timer_softirq);
  1787. }
  1788. /**
  1789. * msleep - sleep safely even with waitqueue interruptions
  1790. * @msecs: Time in milliseconds to sleep for
  1791. */
  1792. void msleep(unsigned int msecs)
  1793. {
  1794. unsigned long timeout = msecs_to_jiffies(msecs) + 1;
  1795. while (timeout)
  1796. timeout = schedule_timeout_uninterruptible(timeout);
  1797. }
  1798. EXPORT_SYMBOL(msleep);
  1799. /**
  1800. * msleep_interruptible - sleep waiting for signals
  1801. * @msecs: Time in milliseconds to sleep for
  1802. */
  1803. unsigned long msleep_interruptible(unsigned int msecs)
  1804. {
  1805. unsigned long timeout = msecs_to_jiffies(msecs) + 1;
  1806. while (timeout && !signal_pending(current))
  1807. timeout = schedule_timeout_interruptible(timeout);
  1808. return jiffies_to_msecs(timeout);
  1809. }
  1810. EXPORT_SYMBOL(msleep_interruptible);
  1811. /**
  1812. * usleep_range_state - Sleep for an approximate time in a given state
  1813. * @min: Minimum time in usecs to sleep
  1814. * @max: Maximum time in usecs to sleep
  1815. * @state: State of the current task that will be while sleeping
  1816. *
  1817. * In non-atomic context where the exact wakeup time is flexible, use
  1818. * usleep_range_state() instead of udelay(). The sleep improves responsiveness
  1819. * by avoiding the CPU-hogging busy-wait of udelay(), and the range reduces
  1820. * power usage by allowing hrtimers to take advantage of an already-
  1821. * scheduled interrupt instead of scheduling a new one just for this sleep.
  1822. */
  1823. void __sched usleep_range_state(unsigned long min, unsigned long max,
  1824. unsigned int state)
  1825. {
  1826. ktime_t exp = ktime_add_us(ktime_get(), min);
  1827. u64 delta = (u64)(max - min) * NSEC_PER_USEC;
  1828. for (;;) {
  1829. __set_current_state(state);
  1830. /* Do not return before the requested sleep time has elapsed */
  1831. if (!schedule_hrtimeout_range(&exp, delta, HRTIMER_MODE_ABS))
  1832. break;
  1833. }
  1834. }
  1835. /**
  1836. * usleep_range - Sleep for an approximate time
  1837. * @min: Minimum time in usecs to sleep
  1838. * @max: Maximum time in usecs to sleep
  1839. *
  1840. * In non-atomic context where the exact wakeup time is flexible, use
  1841. * usleep_range() instead of udelay(). The sleep improves responsiveness
  1842. * by avoiding the CPU-hogging busy-wait of udelay(), and the range reduces
  1843. * power usage by allowing hrtimers to take advantage of an already-
  1844. * scheduled interrupt instead of scheduling a new one just for this sleep.
  1845. */
  1846. void __sched usleep_range(unsigned long min, unsigned long max)
  1847. {
  1848. usleep_range_state(min, max, TASK_UNINTERRUPTIBLE);
  1849. }
  1850. EXPORT_SYMBOL(usleep_range);