timer.c 50 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950
  1. /*
  2. * linux/kernel/timer.c
  3. *
  4. * Kernel internal timers, kernel timekeeping, basic process system calls
  5. *
  6. * Copyright (C) 1991, 1992 Linus Torvalds
  7. *
  8. * 1997-01-28 Modified by Finn Arne Gangstad to make timers scale better.
  9. *
  10. * 1997-09-10 Updated NTP code according to technical memorandum Jan '96
  11. * "A Kernel Model for Precision Timekeeping" by Dave Mills
  12. * 1998-12-24 Fixed a xtime SMP race (we need the xtime_lock rw spinlock to
  13. * serialize accesses to xtime/lost_ticks).
  14. * Copyright (C) 1998 Andrea Arcangeli
  15. * 1999-03-10 Improved NTP compatibility by Ulrich Windl
  16. * 2002-05-31 Move sys_sysinfo here and make its locking sane, Robert Love
  17. * 2000-10-05 Implemented scalable SMP per-CPU timer handling.
  18. * Copyright (C) 2000, 2001, 2002 Ingo Molnar
  19. * Designed by David S. Miller, Alexey Kuznetsov and Ingo Molnar
  20. */
  21. #include <linux/kernel_stat.h>
  22. #include <linux/module.h>
  23. #include <linux/interrupt.h>
  24. #include <linux/percpu.h>
  25. #include <linux/init.h>
  26. #include <linux/mm.h>
  27. #include <linux/swap.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 <asm/uaccess.h>
  39. #include <asm/unistd.h>
  40. #include <asm/div64.h>
  41. #include <asm/timex.h>
  42. #include <asm/io.h>
  43. u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
  44. EXPORT_SYMBOL(jiffies_64);
  45. /*
  46. * per-CPU timer vector definitions:
  47. */
  48. #define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
  49. #define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
  50. #define TVN_SIZE (1 << TVN_BITS)
  51. #define TVR_SIZE (1 << TVR_BITS)
  52. #define TVN_MASK (TVN_SIZE - 1)
  53. #define TVR_MASK (TVR_SIZE - 1)
  54. typedef struct tvec_s {
  55. struct list_head vec[TVN_SIZE];
  56. } tvec_t;
  57. typedef struct tvec_root_s {
  58. struct list_head vec[TVR_SIZE];
  59. } tvec_root_t;
  60. struct tvec_t_base_s {
  61. spinlock_t lock;
  62. struct timer_list *running_timer;
  63. unsigned long timer_jiffies;
  64. tvec_root_t tv1;
  65. tvec_t tv2;
  66. tvec_t tv3;
  67. tvec_t tv4;
  68. tvec_t tv5;
  69. } ____cacheline_aligned_in_smp;
  70. typedef struct tvec_t_base_s tvec_base_t;
  71. tvec_base_t boot_tvec_bases;
  72. EXPORT_SYMBOL(boot_tvec_bases);
  73. static DEFINE_PER_CPU(tvec_base_t *, tvec_bases) = &boot_tvec_bases;
  74. /**
  75. * __round_jiffies - function to round jiffies to a full second
  76. * @j: the time in (absolute) jiffies that should be rounded
  77. * @cpu: the processor number on which the timeout will happen
  78. *
  79. * __round_jiffies() rounds an absolute time in the future (in jiffies)
  80. * up or down to (approximately) full seconds. This is useful for timers
  81. * for which the exact time they fire does not matter too much, as long as
  82. * they fire approximately every X seconds.
  83. *
  84. * By rounding these timers to whole seconds, all such timers will fire
  85. * at the same time, rather than at various times spread out. The goal
  86. * of this is to have the CPU wake up less, which saves power.
  87. *
  88. * The exact rounding is skewed for each processor to avoid all
  89. * processors firing at the exact same time, which could lead
  90. * to lock contention or spurious cache line bouncing.
  91. *
  92. * The return value is the rounded version of the @j parameter.
  93. */
  94. unsigned long __round_jiffies(unsigned long j, int cpu)
  95. {
  96. int rem;
  97. unsigned long original = j;
  98. /*
  99. * We don't want all cpus firing their timers at once hitting the
  100. * same lock or cachelines, so we skew each extra cpu with an extra
  101. * 3 jiffies. This 3 jiffies came originally from the mm/ code which
  102. * already did this.
  103. * The skew is done by adding 3*cpunr, then round, then subtract this
  104. * extra offset again.
  105. */
  106. j += cpu * 3;
  107. rem = j % HZ;
  108. /*
  109. * If the target jiffie is just after a whole second (which can happen
  110. * due to delays of the timer irq, long irq off times etc etc) then
  111. * we should round down to the whole second, not up. Use 1/4th second
  112. * as cutoff for this rounding as an extreme upper bound for this.
  113. */
  114. if (rem < HZ/4) /* round down */
  115. j = j - rem;
  116. else /* round up */
  117. j = j - rem + HZ;
  118. /* now that we have rounded, subtract the extra skew again */
  119. j -= cpu * 3;
  120. if (j <= jiffies) /* rounding ate our timeout entirely; */
  121. return original;
  122. return j;
  123. }
  124. EXPORT_SYMBOL_GPL(__round_jiffies);
  125. /**
  126. * __round_jiffies_relative - function to round jiffies to a full second
  127. * @j: the time in (relative) jiffies that should be rounded
  128. * @cpu: the processor number on which the timeout will happen
  129. *
  130. * __round_jiffies_relative() rounds a time delta in the future (in jiffies)
  131. * up or down to (approximately) full seconds. This is useful for timers
  132. * for which the exact time they fire does not matter too much, as long as
  133. * they fire approximately every X seconds.
  134. *
  135. * By rounding these timers to whole seconds, all such timers will fire
  136. * at the same time, rather than at various times spread out. The goal
  137. * of this is to have the CPU wake up less, which saves power.
  138. *
  139. * The exact rounding is skewed for each processor to avoid all
  140. * processors firing at the exact same time, which could lead
  141. * to lock contention or spurious cache line bouncing.
  142. *
  143. * The return value is the rounded version of the @j parameter.
  144. */
  145. unsigned long __round_jiffies_relative(unsigned long j, int cpu)
  146. {
  147. /*
  148. * In theory the following code can skip a jiffy in case jiffies
  149. * increments right between the addition and the later subtraction.
  150. * However since the entire point of this function is to use approximate
  151. * timeouts, it's entirely ok to not handle that.
  152. */
  153. return __round_jiffies(j + jiffies, cpu) - jiffies;
  154. }
  155. EXPORT_SYMBOL_GPL(__round_jiffies_relative);
  156. /**
  157. * round_jiffies - function to round jiffies to a full second
  158. * @j: the time in (absolute) jiffies that should be rounded
  159. *
  160. * round_jiffies() rounds an absolute time in the future (in jiffies)
  161. * up or down to (approximately) full seconds. This is useful for timers
  162. * for which the exact time they fire does not matter too much, as long as
  163. * they fire approximately every X seconds.
  164. *
  165. * By rounding these timers to whole seconds, all such timers will fire
  166. * at the same time, rather than at various times spread out. The goal
  167. * of this is to have the CPU wake up less, which saves power.
  168. *
  169. * The return value is the rounded version of the @j parameter.
  170. */
  171. unsigned long round_jiffies(unsigned long j)
  172. {
  173. return __round_jiffies(j, raw_smp_processor_id());
  174. }
  175. EXPORT_SYMBOL_GPL(round_jiffies);
  176. /**
  177. * round_jiffies_relative - function to round jiffies to a full second
  178. * @j: the time in (relative) jiffies that should be rounded
  179. *
  180. * round_jiffies_relative() rounds a time delta in the future (in jiffies)
  181. * up or down to (approximately) full seconds. This is useful for timers
  182. * for which the exact time they fire does not matter too much, as long as
  183. * they fire approximately every X seconds.
  184. *
  185. * By rounding these timers to whole seconds, all such timers will fire
  186. * at the same time, rather than at various times spread out. The goal
  187. * of this is to have the CPU wake up less, which saves power.
  188. *
  189. * The return value is the rounded version of the @j parameter.
  190. */
  191. unsigned long round_jiffies_relative(unsigned long j)
  192. {
  193. return __round_jiffies_relative(j, raw_smp_processor_id());
  194. }
  195. EXPORT_SYMBOL_GPL(round_jiffies_relative);
  196. static inline void set_running_timer(tvec_base_t *base,
  197. struct timer_list *timer)
  198. {
  199. #ifdef CONFIG_SMP
  200. base->running_timer = timer;
  201. #endif
  202. }
  203. static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
  204. {
  205. unsigned long expires = timer->expires;
  206. unsigned long idx = expires - base->timer_jiffies;
  207. struct list_head *vec;
  208. if (idx < TVR_SIZE) {
  209. int i = expires & TVR_MASK;
  210. vec = base->tv1.vec + i;
  211. } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
  212. int i = (expires >> TVR_BITS) & TVN_MASK;
  213. vec = base->tv2.vec + i;
  214. } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
  215. int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
  216. vec = base->tv3.vec + i;
  217. } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
  218. int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
  219. vec = base->tv4.vec + i;
  220. } else if ((signed long) idx < 0) {
  221. /*
  222. * Can happen if you add a timer with expires == jiffies,
  223. * or you set a timer to go off in the past
  224. */
  225. vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
  226. } else {
  227. int i;
  228. /* If the timeout is larger than 0xffffffff on 64-bit
  229. * architectures then we use the maximum timeout:
  230. */
  231. if (idx > 0xffffffffUL) {
  232. idx = 0xffffffffUL;
  233. expires = idx + base->timer_jiffies;
  234. }
  235. i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
  236. vec = base->tv5.vec + i;
  237. }
  238. /*
  239. * Timers are FIFO:
  240. */
  241. list_add_tail(&timer->entry, vec);
  242. }
  243. #ifdef CONFIG_TIMER_STATS
  244. void __timer_stats_timer_set_start_info(struct timer_list *timer, void *addr)
  245. {
  246. if (timer->start_site)
  247. return;
  248. timer->start_site = addr;
  249. memcpy(timer->start_comm, current->comm, TASK_COMM_LEN);
  250. timer->start_pid = current->pid;
  251. }
  252. #endif
  253. /**
  254. * init_timer - initialize a timer.
  255. * @timer: the timer to be initialized
  256. *
  257. * init_timer() must be done to a timer prior calling *any* of the
  258. * other timer functions.
  259. */
  260. void fastcall init_timer(struct timer_list *timer)
  261. {
  262. timer->entry.next = NULL;
  263. timer->base = __raw_get_cpu_var(tvec_bases);
  264. #ifdef CONFIG_TIMER_STATS
  265. timer->start_site = NULL;
  266. timer->start_pid = -1;
  267. memset(timer->start_comm, 0, TASK_COMM_LEN);
  268. #endif
  269. }
  270. EXPORT_SYMBOL(init_timer);
  271. static inline void detach_timer(struct timer_list *timer,
  272. int clear_pending)
  273. {
  274. struct list_head *entry = &timer->entry;
  275. __list_del(entry->prev, entry->next);
  276. if (clear_pending)
  277. entry->next = NULL;
  278. entry->prev = LIST_POISON2;
  279. }
  280. /*
  281. * We are using hashed locking: holding per_cpu(tvec_bases).lock
  282. * means that all timers which are tied to this base via timer->base are
  283. * locked, and the base itself is locked too.
  284. *
  285. * So __run_timers/migrate_timers can safely modify all timers which could
  286. * be found on ->tvX lists.
  287. *
  288. * When the timer's base is locked, and the timer removed from list, it is
  289. * possible to set timer->base = NULL and drop the lock: the timer remains
  290. * locked.
  291. */
  292. static tvec_base_t *lock_timer_base(struct timer_list *timer,
  293. unsigned long *flags)
  294. __acquires(timer->base->lock)
  295. {
  296. tvec_base_t *base;
  297. for (;;) {
  298. base = timer->base;
  299. if (likely(base != NULL)) {
  300. spin_lock_irqsave(&base->lock, *flags);
  301. if (likely(base == timer->base))
  302. return base;
  303. /* The timer has migrated to another CPU */
  304. spin_unlock_irqrestore(&base->lock, *flags);
  305. }
  306. cpu_relax();
  307. }
  308. }
  309. int __mod_timer(struct timer_list *timer, unsigned long expires)
  310. {
  311. tvec_base_t *base, *new_base;
  312. unsigned long flags;
  313. int ret = 0;
  314. timer_stats_timer_set_start_info(timer);
  315. BUG_ON(!timer->function);
  316. base = lock_timer_base(timer, &flags);
  317. if (timer_pending(timer)) {
  318. detach_timer(timer, 0);
  319. ret = 1;
  320. }
  321. new_base = __get_cpu_var(tvec_bases);
  322. if (base != new_base) {
  323. /*
  324. * We are trying to schedule the timer on the local CPU.
  325. * However we can't change timer's base while it is running,
  326. * otherwise del_timer_sync() can't detect that the timer's
  327. * handler yet has not finished. This also guarantees that
  328. * the timer is serialized wrt itself.
  329. */
  330. if (likely(base->running_timer != timer)) {
  331. /* See the comment in lock_timer_base() */
  332. timer->base = NULL;
  333. spin_unlock(&base->lock);
  334. base = new_base;
  335. spin_lock(&base->lock);
  336. timer->base = base;
  337. }
  338. }
  339. timer->expires = expires;
  340. internal_add_timer(base, timer);
  341. spin_unlock_irqrestore(&base->lock, flags);
  342. return ret;
  343. }
  344. EXPORT_SYMBOL(__mod_timer);
  345. /**
  346. * add_timer_on - start a timer on a particular CPU
  347. * @timer: the timer to be added
  348. * @cpu: the CPU to start it on
  349. *
  350. * This is not very scalable on SMP. Double adds are not possible.
  351. */
  352. void add_timer_on(struct timer_list *timer, int cpu)
  353. {
  354. tvec_base_t *base = per_cpu(tvec_bases, cpu);
  355. unsigned long flags;
  356. timer_stats_timer_set_start_info(timer);
  357. BUG_ON(timer_pending(timer) || !timer->function);
  358. spin_lock_irqsave(&base->lock, flags);
  359. timer->base = base;
  360. internal_add_timer(base, timer);
  361. spin_unlock_irqrestore(&base->lock, flags);
  362. }
  363. /**
  364. * mod_timer - modify a timer's timeout
  365. * @timer: the timer to be modified
  366. * @expires: new timeout in jiffies
  367. *
  368. * mod_timer() is a more efficient way to update the expire field of an
  369. * active timer (if the timer is inactive it will be activated)
  370. *
  371. * mod_timer(timer, expires) is equivalent to:
  372. *
  373. * del_timer(timer); timer->expires = expires; add_timer(timer);
  374. *
  375. * Note that if there are multiple unserialized concurrent users of the
  376. * same timer, then mod_timer() is the only safe way to modify the timeout,
  377. * since add_timer() cannot modify an already running timer.
  378. *
  379. * The function returns whether it has modified a pending timer or not.
  380. * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
  381. * active timer returns 1.)
  382. */
  383. int mod_timer(struct timer_list *timer, unsigned long expires)
  384. {
  385. BUG_ON(!timer->function);
  386. timer_stats_timer_set_start_info(timer);
  387. /*
  388. * This is a common optimization triggered by the
  389. * networking code - if the timer is re-modified
  390. * to be the same thing then just return:
  391. */
  392. if (timer->expires == expires && timer_pending(timer))
  393. return 1;
  394. return __mod_timer(timer, expires);
  395. }
  396. EXPORT_SYMBOL(mod_timer);
  397. /**
  398. * del_timer - deactive a timer.
  399. * @timer: the timer to be deactivated
  400. *
  401. * del_timer() deactivates a timer - this works on both active and inactive
  402. * timers.
  403. *
  404. * The function returns whether it has deactivated a pending timer or not.
  405. * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
  406. * active timer returns 1.)
  407. */
  408. int del_timer(struct timer_list *timer)
  409. {
  410. tvec_base_t *base;
  411. unsigned long flags;
  412. int ret = 0;
  413. timer_stats_timer_clear_start_info(timer);
  414. if (timer_pending(timer)) {
  415. base = lock_timer_base(timer, &flags);
  416. if (timer_pending(timer)) {
  417. detach_timer(timer, 1);
  418. ret = 1;
  419. }
  420. spin_unlock_irqrestore(&base->lock, flags);
  421. }
  422. return ret;
  423. }
  424. EXPORT_SYMBOL(del_timer);
  425. #ifdef CONFIG_SMP
  426. /**
  427. * try_to_del_timer_sync - Try to deactivate a timer
  428. * @timer: timer do del
  429. *
  430. * This function tries to deactivate a timer. Upon successful (ret >= 0)
  431. * exit the timer is not queued and the handler is not running on any CPU.
  432. *
  433. * It must not be called from interrupt contexts.
  434. */
  435. int try_to_del_timer_sync(struct timer_list *timer)
  436. {
  437. tvec_base_t *base;
  438. unsigned long flags;
  439. int ret = -1;
  440. base = lock_timer_base(timer, &flags);
  441. if (base->running_timer == timer)
  442. goto out;
  443. ret = 0;
  444. if (timer_pending(timer)) {
  445. detach_timer(timer, 1);
  446. ret = 1;
  447. }
  448. out:
  449. spin_unlock_irqrestore(&base->lock, flags);
  450. return ret;
  451. }
  452. /**
  453. * del_timer_sync - deactivate a timer and wait for the handler to finish.
  454. * @timer: the timer to be deactivated
  455. *
  456. * This function only differs from del_timer() on SMP: besides deactivating
  457. * the timer it also makes sure the handler has finished executing on other
  458. * CPUs.
  459. *
  460. * Synchronization rules: Callers must prevent restarting of the timer,
  461. * otherwise this function is meaningless. It must not be called from
  462. * interrupt contexts. The caller must not hold locks which would prevent
  463. * completion of the timer's handler. The timer's handler must not call
  464. * add_timer_on(). Upon exit the timer is not queued and the handler is
  465. * not running on any CPU.
  466. *
  467. * The function returns whether it has deactivated a pending timer or not.
  468. */
  469. int del_timer_sync(struct timer_list *timer)
  470. {
  471. for (;;) {
  472. int ret = try_to_del_timer_sync(timer);
  473. if (ret >= 0)
  474. return ret;
  475. cpu_relax();
  476. }
  477. }
  478. EXPORT_SYMBOL(del_timer_sync);
  479. #endif
  480. static int cascade(tvec_base_t *base, tvec_t *tv, int index)
  481. {
  482. /* cascade all the timers from tv up one level */
  483. struct timer_list *timer, *tmp;
  484. struct list_head tv_list;
  485. list_replace_init(tv->vec + index, &tv_list);
  486. /*
  487. * We are removing _all_ timers from the list, so we
  488. * don't have to detach them individually.
  489. */
  490. list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
  491. BUG_ON(timer->base != base);
  492. internal_add_timer(base, timer);
  493. }
  494. return index;
  495. }
  496. #define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)
  497. /**
  498. * __run_timers - run all expired timers (if any) on this CPU.
  499. * @base: the timer vector to be processed.
  500. *
  501. * This function cascades all vectors and executes all expired timer
  502. * vectors.
  503. */
  504. static inline void __run_timers(tvec_base_t *base)
  505. {
  506. struct timer_list *timer;
  507. spin_lock_irq(&base->lock);
  508. while (time_after_eq(jiffies, base->timer_jiffies)) {
  509. struct list_head work_list;
  510. struct list_head *head = &work_list;
  511. int index = base->timer_jiffies & TVR_MASK;
  512. /*
  513. * Cascade timers:
  514. */
  515. if (!index &&
  516. (!cascade(base, &base->tv2, INDEX(0))) &&
  517. (!cascade(base, &base->tv3, INDEX(1))) &&
  518. !cascade(base, &base->tv4, INDEX(2)))
  519. cascade(base, &base->tv5, INDEX(3));
  520. ++base->timer_jiffies;
  521. list_replace_init(base->tv1.vec + index, &work_list);
  522. while (!list_empty(head)) {
  523. void (*fn)(unsigned long);
  524. unsigned long data;
  525. timer = list_entry(head->next,struct timer_list,entry);
  526. fn = timer->function;
  527. data = timer->data;
  528. timer_stats_account_timer(timer);
  529. set_running_timer(base, timer);
  530. detach_timer(timer, 1);
  531. spin_unlock_irq(&base->lock);
  532. {
  533. int preempt_count = preempt_count();
  534. fn(data);
  535. if (preempt_count != preempt_count()) {
  536. printk(KERN_WARNING "huh, entered %p "
  537. "with preempt_count %08x, exited"
  538. " with %08x?\n",
  539. fn, preempt_count,
  540. preempt_count());
  541. BUG();
  542. }
  543. }
  544. spin_lock_irq(&base->lock);
  545. }
  546. }
  547. set_running_timer(base, NULL);
  548. spin_unlock_irq(&base->lock);
  549. }
  550. #if defined(CONFIG_NO_IDLE_HZ) || defined(CONFIG_NO_HZ)
  551. /*
  552. * Find out when the next timer event is due to happen. This
  553. * is used on S/390 to stop all activity when a cpus is idle.
  554. * This functions needs to be called disabled.
  555. */
  556. static unsigned long __next_timer_interrupt(tvec_base_t *base)
  557. {
  558. unsigned long timer_jiffies = base->timer_jiffies;
  559. unsigned long expires = timer_jiffies + (LONG_MAX >> 1);
  560. int index, slot, array, found = 0;
  561. struct timer_list *nte;
  562. tvec_t *varray[4];
  563. /* Look for timer events in tv1. */
  564. index = slot = timer_jiffies & TVR_MASK;
  565. do {
  566. list_for_each_entry(nte, base->tv1.vec + slot, entry) {
  567. found = 1;
  568. expires = nte->expires;
  569. /* Look at the cascade bucket(s)? */
  570. if (!index || slot < index)
  571. goto cascade;
  572. return expires;
  573. }
  574. slot = (slot + 1) & TVR_MASK;
  575. } while (slot != index);
  576. cascade:
  577. /* Calculate the next cascade event */
  578. if (index)
  579. timer_jiffies += TVR_SIZE - index;
  580. timer_jiffies >>= TVR_BITS;
  581. /* Check tv2-tv5. */
  582. varray[0] = &base->tv2;
  583. varray[1] = &base->tv3;
  584. varray[2] = &base->tv4;
  585. varray[3] = &base->tv5;
  586. for (array = 0; array < 4; array++) {
  587. tvec_t *varp = varray[array];
  588. index = slot = timer_jiffies & TVN_MASK;
  589. do {
  590. list_for_each_entry(nte, varp->vec + slot, entry) {
  591. found = 1;
  592. if (time_before(nte->expires, expires))
  593. expires = nte->expires;
  594. }
  595. /*
  596. * Do we still search for the first timer or are
  597. * we looking up the cascade buckets ?
  598. */
  599. if (found) {
  600. /* Look at the cascade bucket(s)? */
  601. if (!index || slot < index)
  602. break;
  603. return expires;
  604. }
  605. slot = (slot + 1) & TVN_MASK;
  606. } while (slot != index);
  607. if (index)
  608. timer_jiffies += TVN_SIZE - index;
  609. timer_jiffies >>= TVN_BITS;
  610. }
  611. return expires;
  612. }
  613. /*
  614. * Check, if the next hrtimer event is before the next timer wheel
  615. * event:
  616. */
  617. static unsigned long cmp_next_hrtimer_event(unsigned long now,
  618. unsigned long expires)
  619. {
  620. ktime_t hr_delta = hrtimer_get_next_event();
  621. struct timespec tsdelta;
  622. unsigned long delta;
  623. if (hr_delta.tv64 == KTIME_MAX)
  624. return expires;
  625. /*
  626. * Expired timer available, let it expire in the next tick
  627. */
  628. if (hr_delta.tv64 <= 0)
  629. return now + 1;
  630. tsdelta = ktime_to_timespec(hr_delta);
  631. delta = timespec_to_jiffies(&tsdelta);
  632. /*
  633. * Take rounding errors in to account and make sure, that it
  634. * expires in the next tick. Otherwise we go into an endless
  635. * ping pong due to tick_nohz_stop_sched_tick() retriggering
  636. * the timer softirq
  637. */
  638. if (delta < 1)
  639. delta = 1;
  640. now += delta;
  641. if (time_before(now, expires))
  642. return now;
  643. return expires;
  644. }
  645. /**
  646. * next_timer_interrupt - return the jiffy of the next pending timer
  647. * @now: current time (in jiffies)
  648. */
  649. unsigned long get_next_timer_interrupt(unsigned long now)
  650. {
  651. tvec_base_t *base = __get_cpu_var(tvec_bases);
  652. unsigned long expires;
  653. spin_lock(&base->lock);
  654. expires = __next_timer_interrupt(base);
  655. spin_unlock(&base->lock);
  656. if (time_before_eq(expires, now))
  657. return now;
  658. return cmp_next_hrtimer_event(now, expires);
  659. }
  660. #ifdef CONFIG_NO_IDLE_HZ
  661. unsigned long next_timer_interrupt(void)
  662. {
  663. return get_next_timer_interrupt(jiffies);
  664. }
  665. #endif
  666. #endif
  667. /******************************************************************/
  668. /*
  669. * The current time
  670. * wall_to_monotonic is what we need to add to xtime (or xtime corrected
  671. * for sub jiffie times) to get to monotonic time. Monotonic is pegged
  672. * at zero at system boot time, so wall_to_monotonic will be negative,
  673. * however, we will ALWAYS keep the tv_nsec part positive so we can use
  674. * the usual normalization.
  675. */
  676. struct timespec xtime __attribute__ ((aligned (16)));
  677. struct timespec wall_to_monotonic __attribute__ ((aligned (16)));
  678. EXPORT_SYMBOL(xtime);
  679. /* XXX - all of this timekeeping code should be later moved to time.c */
  680. #include <linux/clocksource.h>
  681. static struct clocksource *clock; /* pointer to current clocksource */
  682. #ifdef CONFIG_GENERIC_TIME
  683. /**
  684. * __get_nsec_offset - Returns nanoseconds since last call to periodic_hook
  685. *
  686. * private function, must hold xtime_lock lock when being
  687. * called. Returns the number of nanoseconds since the
  688. * last call to update_wall_time() (adjusted by NTP scaling)
  689. */
  690. static inline s64 __get_nsec_offset(void)
  691. {
  692. cycle_t cycle_now, cycle_delta;
  693. s64 ns_offset;
  694. /* read clocksource: */
  695. cycle_now = clocksource_read(clock);
  696. /* calculate the delta since the last update_wall_time: */
  697. cycle_delta = (cycle_now - clock->cycle_last) & clock->mask;
  698. /* convert to nanoseconds: */
  699. ns_offset = cyc2ns(clock, cycle_delta);
  700. return ns_offset;
  701. }
  702. /**
  703. * __get_realtime_clock_ts - Returns the time of day in a timespec
  704. * @ts: pointer to the timespec to be set
  705. *
  706. * Returns the time of day in a timespec. Used by
  707. * do_gettimeofday() and get_realtime_clock_ts().
  708. */
  709. static inline void __get_realtime_clock_ts(struct timespec *ts)
  710. {
  711. unsigned long seq;
  712. s64 nsecs;
  713. do {
  714. seq = read_seqbegin(&xtime_lock);
  715. *ts = xtime;
  716. nsecs = __get_nsec_offset();
  717. } while (read_seqretry(&xtime_lock, seq));
  718. timespec_add_ns(ts, nsecs);
  719. }
  720. /**
  721. * getnstimeofday - Returns the time of day in a timespec
  722. * @ts: pointer to the timespec to be set
  723. *
  724. * Returns the time of day in a timespec.
  725. */
  726. void getnstimeofday(struct timespec *ts)
  727. {
  728. __get_realtime_clock_ts(ts);
  729. }
  730. EXPORT_SYMBOL(getnstimeofday);
  731. /**
  732. * do_gettimeofday - Returns the time of day in a timeval
  733. * @tv: pointer to the timeval to be set
  734. *
  735. * NOTE: Users should be converted to using get_realtime_clock_ts()
  736. */
  737. void do_gettimeofday(struct timeval *tv)
  738. {
  739. struct timespec now;
  740. __get_realtime_clock_ts(&now);
  741. tv->tv_sec = now.tv_sec;
  742. tv->tv_usec = now.tv_nsec/1000;
  743. }
  744. EXPORT_SYMBOL(do_gettimeofday);
  745. /**
  746. * do_settimeofday - Sets the time of day
  747. * @tv: pointer to the timespec variable containing the new time
  748. *
  749. * Sets the time of day to the new time and update NTP and notify hrtimers
  750. */
  751. int do_settimeofday(struct timespec *tv)
  752. {
  753. unsigned long flags;
  754. time_t wtm_sec, sec = tv->tv_sec;
  755. long wtm_nsec, nsec = tv->tv_nsec;
  756. if ((unsigned long)tv->tv_nsec >= NSEC_PER_SEC)
  757. return -EINVAL;
  758. write_seqlock_irqsave(&xtime_lock, flags);
  759. nsec -= __get_nsec_offset();
  760. wtm_sec = wall_to_monotonic.tv_sec + (xtime.tv_sec - sec);
  761. wtm_nsec = wall_to_monotonic.tv_nsec + (xtime.tv_nsec - nsec);
  762. set_normalized_timespec(&xtime, sec, nsec);
  763. set_normalized_timespec(&wall_to_monotonic, wtm_sec, wtm_nsec);
  764. clock->error = 0;
  765. ntp_clear();
  766. update_vsyscall(&xtime, clock);
  767. write_sequnlock_irqrestore(&xtime_lock, flags);
  768. /* signal hrtimers about time change */
  769. clock_was_set();
  770. return 0;
  771. }
  772. EXPORT_SYMBOL(do_settimeofday);
  773. /**
  774. * change_clocksource - Swaps clocksources if a new one is available
  775. *
  776. * Accumulates current time interval and initializes new clocksource
  777. */
  778. static void change_clocksource(void)
  779. {
  780. struct clocksource *new;
  781. cycle_t now;
  782. u64 nsec;
  783. new = clocksource_get_next();
  784. if (clock == new)
  785. return;
  786. now = clocksource_read(new);
  787. nsec = __get_nsec_offset();
  788. timespec_add_ns(&xtime, nsec);
  789. clock = new;
  790. clock->cycle_last = now;
  791. clock->error = 0;
  792. clock->xtime_nsec = 0;
  793. clocksource_calculate_interval(clock, NTP_INTERVAL_LENGTH);
  794. tick_clock_notify();
  795. printk(KERN_INFO "Time: %s clocksource has been installed.\n",
  796. clock->name);
  797. }
  798. #else
  799. static inline void change_clocksource(void) { }
  800. #endif
  801. /**
  802. * timekeeping_is_continuous - check to see if timekeeping is free running
  803. */
  804. int timekeeping_is_continuous(void)
  805. {
  806. unsigned long seq;
  807. int ret;
  808. do {
  809. seq = read_seqbegin(&xtime_lock);
  810. ret = clock->flags & CLOCK_SOURCE_VALID_FOR_HRES;
  811. } while (read_seqretry(&xtime_lock, seq));
  812. return ret;
  813. }
  814. /**
  815. * read_persistent_clock - Return time in seconds from the persistent clock.
  816. *
  817. * Weak dummy function for arches that do not yet support it.
  818. * Returns seconds from epoch using the battery backed persistent clock.
  819. * Returns zero if unsupported.
  820. *
  821. * XXX - Do be sure to remove it once all arches implement it.
  822. */
  823. unsigned long __attribute__((weak)) read_persistent_clock(void)
  824. {
  825. return 0;
  826. }
  827. /*
  828. * timekeeping_init - Initializes the clocksource and common timekeeping values
  829. */
  830. void __init timekeeping_init(void)
  831. {
  832. unsigned long flags;
  833. unsigned long sec = read_persistent_clock();
  834. write_seqlock_irqsave(&xtime_lock, flags);
  835. ntp_clear();
  836. clock = clocksource_get_next();
  837. clocksource_calculate_interval(clock, NTP_INTERVAL_LENGTH);
  838. clock->cycle_last = clocksource_read(clock);
  839. xtime.tv_sec = sec;
  840. xtime.tv_nsec = 0;
  841. set_normalized_timespec(&wall_to_monotonic,
  842. -xtime.tv_sec, -xtime.tv_nsec);
  843. write_sequnlock_irqrestore(&xtime_lock, flags);
  844. }
  845. /* flag for if timekeeping is suspended */
  846. static int timekeeping_suspended;
  847. /* time in seconds when suspend began */
  848. static unsigned long timekeeping_suspend_time;
  849. /**
  850. * timekeeping_resume - Resumes the generic timekeeping subsystem.
  851. * @dev: unused
  852. *
  853. * This is for the generic clocksource timekeeping.
  854. * xtime/wall_to_monotonic/jiffies/etc are
  855. * still managed by arch specific suspend/resume code.
  856. */
  857. static int timekeeping_resume(struct sys_device *dev)
  858. {
  859. unsigned long flags;
  860. unsigned long now = read_persistent_clock();
  861. write_seqlock_irqsave(&xtime_lock, flags);
  862. if (now && (now > timekeeping_suspend_time)) {
  863. unsigned long sleep_length = now - timekeeping_suspend_time;
  864. xtime.tv_sec += sleep_length;
  865. wall_to_monotonic.tv_sec -= sleep_length;
  866. }
  867. /* re-base the last cycle value */
  868. clock->cycle_last = clocksource_read(clock);
  869. clock->error = 0;
  870. timekeeping_suspended = 0;
  871. write_sequnlock_irqrestore(&xtime_lock, flags);
  872. touch_softlockup_watchdog();
  873. clockevents_notify(CLOCK_EVT_NOTIFY_RESUME, NULL);
  874. /* Resume hrtimers */
  875. hres_timers_resume();
  876. return 0;
  877. }
  878. static int timekeeping_suspend(struct sys_device *dev, pm_message_t state)
  879. {
  880. unsigned long flags;
  881. write_seqlock_irqsave(&xtime_lock, flags);
  882. timekeeping_suspended = 1;
  883. timekeeping_suspend_time = read_persistent_clock();
  884. write_sequnlock_irqrestore(&xtime_lock, flags);
  885. clockevents_notify(CLOCK_EVT_NOTIFY_SUSPEND, NULL);
  886. return 0;
  887. }
  888. /* sysfs resume/suspend bits for timekeeping */
  889. static struct sysdev_class timekeeping_sysclass = {
  890. .resume = timekeeping_resume,
  891. .suspend = timekeeping_suspend,
  892. set_kset_name("timekeeping"),
  893. };
  894. static struct sys_device device_timer = {
  895. .id = 0,
  896. .cls = &timekeeping_sysclass,
  897. };
  898. static int __init timekeeping_init_device(void)
  899. {
  900. int error = sysdev_class_register(&timekeeping_sysclass);
  901. if (!error)
  902. error = sysdev_register(&device_timer);
  903. return error;
  904. }
  905. device_initcall(timekeeping_init_device);
  906. /*
  907. * If the error is already larger, we look ahead even further
  908. * to compensate for late or lost adjustments.
  909. */
  910. static __always_inline int clocksource_bigadjust(s64 error, s64 *interval,
  911. s64 *offset)
  912. {
  913. s64 tick_error, i;
  914. u32 look_ahead, adj;
  915. s32 error2, mult;
  916. /*
  917. * Use the current error value to determine how much to look ahead.
  918. * The larger the error the slower we adjust for it to avoid problems
  919. * with losing too many ticks, otherwise we would overadjust and
  920. * produce an even larger error. The smaller the adjustment the
  921. * faster we try to adjust for it, as lost ticks can do less harm
  922. * here. This is tuned so that an error of about 1 msec is adusted
  923. * within about 1 sec (or 2^20 nsec in 2^SHIFT_HZ ticks).
  924. */
  925. error2 = clock->error >> (TICK_LENGTH_SHIFT + 22 - 2 * SHIFT_HZ);
  926. error2 = abs(error2);
  927. for (look_ahead = 0; error2 > 0; look_ahead++)
  928. error2 >>= 2;
  929. /*
  930. * Now calculate the error in (1 << look_ahead) ticks, but first
  931. * remove the single look ahead already included in the error.
  932. */
  933. tick_error = current_tick_length() >>
  934. (TICK_LENGTH_SHIFT - clock->shift + 1);
  935. tick_error -= clock->xtime_interval >> 1;
  936. error = ((error - tick_error) >> look_ahead) + tick_error;
  937. /* Finally calculate the adjustment shift value. */
  938. i = *interval;
  939. mult = 1;
  940. if (error < 0) {
  941. error = -error;
  942. *interval = -*interval;
  943. *offset = -*offset;
  944. mult = -1;
  945. }
  946. for (adj = 0; error > i; adj++)
  947. error >>= 1;
  948. *interval <<= adj;
  949. *offset <<= adj;
  950. return mult << adj;
  951. }
  952. /*
  953. * Adjust the multiplier to reduce the error value,
  954. * this is optimized for the most common adjustments of -1,0,1,
  955. * for other values we can do a bit more work.
  956. */
  957. static void clocksource_adjust(struct clocksource *clock, s64 offset)
  958. {
  959. s64 error, interval = clock->cycle_interval;
  960. int adj;
  961. error = clock->error >> (TICK_LENGTH_SHIFT - clock->shift - 1);
  962. if (error > interval) {
  963. error >>= 2;
  964. if (likely(error <= interval))
  965. adj = 1;
  966. else
  967. adj = clocksource_bigadjust(error, &interval, &offset);
  968. } else if (error < -interval) {
  969. error >>= 2;
  970. if (likely(error >= -interval)) {
  971. adj = -1;
  972. interval = -interval;
  973. offset = -offset;
  974. } else
  975. adj = clocksource_bigadjust(error, &interval, &offset);
  976. } else
  977. return;
  978. clock->mult += adj;
  979. clock->xtime_interval += interval;
  980. clock->xtime_nsec -= offset;
  981. clock->error -= (interval - offset) <<
  982. (TICK_LENGTH_SHIFT - clock->shift);
  983. }
  984. /**
  985. * update_wall_time - Uses the current clocksource to increment the wall time
  986. *
  987. * Called from the timer interrupt, must hold a write on xtime_lock.
  988. */
  989. static void update_wall_time(void)
  990. {
  991. cycle_t offset;
  992. /* Make sure we're fully resumed: */
  993. if (unlikely(timekeeping_suspended))
  994. return;
  995. #ifdef CONFIG_GENERIC_TIME
  996. offset = (clocksource_read(clock) - clock->cycle_last) & clock->mask;
  997. #else
  998. offset = clock->cycle_interval;
  999. #endif
  1000. clock->xtime_nsec += (s64)xtime.tv_nsec << clock->shift;
  1001. /* normally this loop will run just once, however in the
  1002. * case of lost or late ticks, it will accumulate correctly.
  1003. */
  1004. while (offset >= clock->cycle_interval) {
  1005. /* accumulate one interval */
  1006. clock->xtime_nsec += clock->xtime_interval;
  1007. clock->cycle_last += clock->cycle_interval;
  1008. offset -= clock->cycle_interval;
  1009. if (clock->xtime_nsec >= (u64)NSEC_PER_SEC << clock->shift) {
  1010. clock->xtime_nsec -= (u64)NSEC_PER_SEC << clock->shift;
  1011. xtime.tv_sec++;
  1012. second_overflow();
  1013. }
  1014. /* interpolator bits */
  1015. time_interpolator_update(clock->xtime_interval
  1016. >> clock->shift);
  1017. /* accumulate error between NTP and clock interval */
  1018. clock->error += current_tick_length();
  1019. clock->error -= clock->xtime_interval << (TICK_LENGTH_SHIFT - clock->shift);
  1020. }
  1021. /* correct the clock when NTP error is too big */
  1022. clocksource_adjust(clock, offset);
  1023. /* store full nanoseconds into xtime */
  1024. xtime.tv_nsec = (s64)clock->xtime_nsec >> clock->shift;
  1025. clock->xtime_nsec -= (s64)xtime.tv_nsec << clock->shift;
  1026. /* check to see if there is a new clocksource to use */
  1027. change_clocksource();
  1028. update_vsyscall(&xtime, clock);
  1029. }
  1030. /*
  1031. * Called from the timer interrupt handler to charge one tick to the current
  1032. * process. user_tick is 1 if the tick is user time, 0 for system.
  1033. */
  1034. void update_process_times(int user_tick)
  1035. {
  1036. struct task_struct *p = current;
  1037. int cpu = smp_processor_id();
  1038. /* Note: this timer irq context must be accounted for as well. */
  1039. if (user_tick)
  1040. account_user_time(p, jiffies_to_cputime(1));
  1041. else
  1042. account_system_time(p, HARDIRQ_OFFSET, jiffies_to_cputime(1));
  1043. run_local_timers();
  1044. if (rcu_pending(cpu))
  1045. rcu_check_callbacks(cpu, user_tick);
  1046. scheduler_tick();
  1047. run_posix_cpu_timers(p);
  1048. }
  1049. /*
  1050. * Nr of active tasks - counted in fixed-point numbers
  1051. */
  1052. static unsigned long count_active_tasks(void)
  1053. {
  1054. return nr_active() * FIXED_1;
  1055. }
  1056. /*
  1057. * Hmm.. Changed this, as the GNU make sources (load.c) seems to
  1058. * imply that avenrun[] is the standard name for this kind of thing.
  1059. * Nothing else seems to be standardized: the fractional size etc
  1060. * all seem to differ on different machines.
  1061. *
  1062. * Requires xtime_lock to access.
  1063. */
  1064. unsigned long avenrun[3];
  1065. EXPORT_SYMBOL(avenrun);
  1066. /*
  1067. * calc_load - given tick count, update the avenrun load estimates.
  1068. * This is called while holding a write_lock on xtime_lock.
  1069. */
  1070. static inline void calc_load(unsigned long ticks)
  1071. {
  1072. unsigned long active_tasks; /* fixed-point */
  1073. static int count = LOAD_FREQ;
  1074. count -= ticks;
  1075. if (unlikely(count < 0)) {
  1076. active_tasks = count_active_tasks();
  1077. do {
  1078. CALC_LOAD(avenrun[0], EXP_1, active_tasks);
  1079. CALC_LOAD(avenrun[1], EXP_5, active_tasks);
  1080. CALC_LOAD(avenrun[2], EXP_15, active_tasks);
  1081. count += LOAD_FREQ;
  1082. } while (count < 0);
  1083. }
  1084. }
  1085. /*
  1086. * This read-write spinlock protects us from races in SMP while
  1087. * playing with xtime and avenrun.
  1088. */
  1089. __attribute__((weak)) __cacheline_aligned_in_smp DEFINE_SEQLOCK(xtime_lock);
  1090. EXPORT_SYMBOL(xtime_lock);
  1091. /*
  1092. * This function runs timers and the timer-tq in bottom half context.
  1093. */
  1094. static void run_timer_softirq(struct softirq_action *h)
  1095. {
  1096. tvec_base_t *base = __get_cpu_var(tvec_bases);
  1097. hrtimer_run_queues();
  1098. if (time_after_eq(jiffies, base->timer_jiffies))
  1099. __run_timers(base);
  1100. }
  1101. /*
  1102. * Called by the local, per-CPU timer interrupt on SMP.
  1103. */
  1104. void run_local_timers(void)
  1105. {
  1106. raise_softirq(TIMER_SOFTIRQ);
  1107. softlockup_tick();
  1108. }
  1109. /*
  1110. * Called by the timer interrupt. xtime_lock must already be taken
  1111. * by the timer IRQ!
  1112. */
  1113. static inline void update_times(unsigned long ticks)
  1114. {
  1115. update_wall_time();
  1116. calc_load(ticks);
  1117. }
  1118. /*
  1119. * The 64-bit jiffies value is not atomic - you MUST NOT read it
  1120. * without sampling the sequence number in xtime_lock.
  1121. * jiffies is defined in the linker script...
  1122. */
  1123. void do_timer(unsigned long ticks)
  1124. {
  1125. jiffies_64 += ticks;
  1126. update_times(ticks);
  1127. }
  1128. #ifdef __ARCH_WANT_SYS_ALARM
  1129. /*
  1130. * For backwards compatibility? This can be done in libc so Alpha
  1131. * and all newer ports shouldn't need it.
  1132. */
  1133. asmlinkage unsigned long sys_alarm(unsigned int seconds)
  1134. {
  1135. return alarm_setitimer(seconds);
  1136. }
  1137. #endif
  1138. #ifndef __alpha__
  1139. /*
  1140. * The Alpha uses getxpid, getxuid, and getxgid instead. Maybe this
  1141. * should be moved into arch/i386 instead?
  1142. */
  1143. /**
  1144. * sys_getpid - return the thread group id of the current process
  1145. *
  1146. * Note, despite the name, this returns the tgid not the pid. The tgid and
  1147. * the pid are identical unless CLONE_THREAD was specified on clone() in
  1148. * which case the tgid is the same in all threads of the same group.
  1149. *
  1150. * This is SMP safe as current->tgid does not change.
  1151. */
  1152. asmlinkage long sys_getpid(void)
  1153. {
  1154. return current->tgid;
  1155. }
  1156. /*
  1157. * Accessing ->real_parent is not SMP-safe, it could
  1158. * change from under us. However, we can use a stale
  1159. * value of ->real_parent under rcu_read_lock(), see
  1160. * release_task()->call_rcu(delayed_put_task_struct).
  1161. */
  1162. asmlinkage long sys_getppid(void)
  1163. {
  1164. int pid;
  1165. rcu_read_lock();
  1166. pid = rcu_dereference(current->real_parent)->tgid;
  1167. rcu_read_unlock();
  1168. return pid;
  1169. }
  1170. asmlinkage long sys_getuid(void)
  1171. {
  1172. /* Only we change this so SMP safe */
  1173. return current->uid;
  1174. }
  1175. asmlinkage long sys_geteuid(void)
  1176. {
  1177. /* Only we change this so SMP safe */
  1178. return current->euid;
  1179. }
  1180. asmlinkage long sys_getgid(void)
  1181. {
  1182. /* Only we change this so SMP safe */
  1183. return current->gid;
  1184. }
  1185. asmlinkage long sys_getegid(void)
  1186. {
  1187. /* Only we change this so SMP safe */
  1188. return current->egid;
  1189. }
  1190. #endif
  1191. static void process_timeout(unsigned long __data)
  1192. {
  1193. wake_up_process((struct task_struct *)__data);
  1194. }
  1195. /**
  1196. * schedule_timeout - sleep until timeout
  1197. * @timeout: timeout value in jiffies
  1198. *
  1199. * Make the current task sleep until @timeout jiffies have
  1200. * elapsed. The routine will return immediately unless
  1201. * the current task state has been set (see set_current_state()).
  1202. *
  1203. * You can set the task state as follows -
  1204. *
  1205. * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
  1206. * pass before the routine returns. The routine will return 0
  1207. *
  1208. * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
  1209. * delivered to the current task. In this case the remaining time
  1210. * in jiffies will be returned, or 0 if the timer expired in time
  1211. *
  1212. * The current task state is guaranteed to be TASK_RUNNING when this
  1213. * routine returns.
  1214. *
  1215. * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
  1216. * the CPU away without a bound on the timeout. In this case the return
  1217. * value will be %MAX_SCHEDULE_TIMEOUT.
  1218. *
  1219. * In all cases the return value is guaranteed to be non-negative.
  1220. */
  1221. fastcall signed long __sched schedule_timeout(signed long timeout)
  1222. {
  1223. struct timer_list timer;
  1224. unsigned long expire;
  1225. switch (timeout)
  1226. {
  1227. case MAX_SCHEDULE_TIMEOUT:
  1228. /*
  1229. * These two special cases are useful to be comfortable
  1230. * in the caller. Nothing more. We could take
  1231. * MAX_SCHEDULE_TIMEOUT from one of the negative value
  1232. * but I' d like to return a valid offset (>=0) to allow
  1233. * the caller to do everything it want with the retval.
  1234. */
  1235. schedule();
  1236. goto out;
  1237. default:
  1238. /*
  1239. * Another bit of PARANOID. Note that the retval will be
  1240. * 0 since no piece of kernel is supposed to do a check
  1241. * for a negative retval of schedule_timeout() (since it
  1242. * should never happens anyway). You just have the printk()
  1243. * that will tell you if something is gone wrong and where.
  1244. */
  1245. if (timeout < 0) {
  1246. printk(KERN_ERR "schedule_timeout: wrong timeout "
  1247. "value %lx\n", timeout);
  1248. dump_stack();
  1249. current->state = TASK_RUNNING;
  1250. goto out;
  1251. }
  1252. }
  1253. expire = timeout + jiffies;
  1254. setup_timer(&timer, process_timeout, (unsigned long)current);
  1255. __mod_timer(&timer, expire);
  1256. schedule();
  1257. del_singleshot_timer_sync(&timer);
  1258. timeout = expire - jiffies;
  1259. out:
  1260. return timeout < 0 ? 0 : timeout;
  1261. }
  1262. EXPORT_SYMBOL(schedule_timeout);
  1263. /*
  1264. * We can use __set_current_state() here because schedule_timeout() calls
  1265. * schedule() unconditionally.
  1266. */
  1267. signed long __sched schedule_timeout_interruptible(signed long timeout)
  1268. {
  1269. __set_current_state(TASK_INTERRUPTIBLE);
  1270. return schedule_timeout(timeout);
  1271. }
  1272. EXPORT_SYMBOL(schedule_timeout_interruptible);
  1273. signed long __sched schedule_timeout_uninterruptible(signed long timeout)
  1274. {
  1275. __set_current_state(TASK_UNINTERRUPTIBLE);
  1276. return schedule_timeout(timeout);
  1277. }
  1278. EXPORT_SYMBOL(schedule_timeout_uninterruptible);
  1279. /* Thread ID - the internal kernel "pid" */
  1280. asmlinkage long sys_gettid(void)
  1281. {
  1282. return current->pid;
  1283. }
  1284. /**
  1285. * do_sysinfo - fill in sysinfo struct
  1286. * @info: pointer to buffer to fill
  1287. */
  1288. int do_sysinfo(struct sysinfo *info)
  1289. {
  1290. unsigned long mem_total, sav_total;
  1291. unsigned int mem_unit, bitcount;
  1292. unsigned long seq;
  1293. memset(info, 0, sizeof(struct sysinfo));
  1294. do {
  1295. struct timespec tp;
  1296. seq = read_seqbegin(&xtime_lock);
  1297. /*
  1298. * This is annoying. The below is the same thing
  1299. * posix_get_clock_monotonic() does, but it wants to
  1300. * take the lock which we want to cover the loads stuff
  1301. * too.
  1302. */
  1303. getnstimeofday(&tp);
  1304. tp.tv_sec += wall_to_monotonic.tv_sec;
  1305. tp.tv_nsec += wall_to_monotonic.tv_nsec;
  1306. if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
  1307. tp.tv_nsec = tp.tv_nsec - NSEC_PER_SEC;
  1308. tp.tv_sec++;
  1309. }
  1310. info->uptime = tp.tv_sec + (tp.tv_nsec ? 1 : 0);
  1311. info->loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
  1312. info->loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
  1313. info->loads[2] = avenrun[2] << (SI_LOAD_SHIFT - FSHIFT);
  1314. info->procs = nr_threads;
  1315. } while (read_seqretry(&xtime_lock, seq));
  1316. si_meminfo(info);
  1317. si_swapinfo(info);
  1318. /*
  1319. * If the sum of all the available memory (i.e. ram + swap)
  1320. * is less than can be stored in a 32 bit unsigned long then
  1321. * we can be binary compatible with 2.2.x kernels. If not,
  1322. * well, in that case 2.2.x was broken anyways...
  1323. *
  1324. * -Erik Andersen <andersee@debian.org>
  1325. */
  1326. mem_total = info->totalram + info->totalswap;
  1327. if (mem_total < info->totalram || mem_total < info->totalswap)
  1328. goto out;
  1329. bitcount = 0;
  1330. mem_unit = info->mem_unit;
  1331. while (mem_unit > 1) {
  1332. bitcount++;
  1333. mem_unit >>= 1;
  1334. sav_total = mem_total;
  1335. mem_total <<= 1;
  1336. if (mem_total < sav_total)
  1337. goto out;
  1338. }
  1339. /*
  1340. * If mem_total did not overflow, multiply all memory values by
  1341. * info->mem_unit and set it to 1. This leaves things compatible
  1342. * with 2.2.x, and also retains compatibility with earlier 2.4.x
  1343. * kernels...
  1344. */
  1345. info->mem_unit = 1;
  1346. info->totalram <<= bitcount;
  1347. info->freeram <<= bitcount;
  1348. info->sharedram <<= bitcount;
  1349. info->bufferram <<= bitcount;
  1350. info->totalswap <<= bitcount;
  1351. info->freeswap <<= bitcount;
  1352. info->totalhigh <<= bitcount;
  1353. info->freehigh <<= bitcount;
  1354. out:
  1355. return 0;
  1356. }
  1357. asmlinkage long sys_sysinfo(struct sysinfo __user *info)
  1358. {
  1359. struct sysinfo val;
  1360. do_sysinfo(&val);
  1361. if (copy_to_user(info, &val, sizeof(struct sysinfo)))
  1362. return -EFAULT;
  1363. return 0;
  1364. }
  1365. /*
  1366. * lockdep: we want to track each per-CPU base as a separate lock-class,
  1367. * but timer-bases are kmalloc()-ed, so we need to attach separate
  1368. * keys to them:
  1369. */
  1370. static struct lock_class_key base_lock_keys[NR_CPUS];
  1371. static int __devinit init_timers_cpu(int cpu)
  1372. {
  1373. int j;
  1374. tvec_base_t *base;
  1375. static char __devinitdata tvec_base_done[NR_CPUS];
  1376. if (!tvec_base_done[cpu]) {
  1377. static char boot_done;
  1378. if (boot_done) {
  1379. /*
  1380. * The APs use this path later in boot
  1381. */
  1382. base = kmalloc_node(sizeof(*base), GFP_KERNEL,
  1383. cpu_to_node(cpu));
  1384. if (!base)
  1385. return -ENOMEM;
  1386. memset(base, 0, sizeof(*base));
  1387. per_cpu(tvec_bases, cpu) = base;
  1388. } else {
  1389. /*
  1390. * This is for the boot CPU - we use compile-time
  1391. * static initialisation because per-cpu memory isn't
  1392. * ready yet and because the memory allocators are not
  1393. * initialised either.
  1394. */
  1395. boot_done = 1;
  1396. base = &boot_tvec_bases;
  1397. }
  1398. tvec_base_done[cpu] = 1;
  1399. } else {
  1400. base = per_cpu(tvec_bases, cpu);
  1401. }
  1402. spin_lock_init(&base->lock);
  1403. lockdep_set_class(&base->lock, base_lock_keys + cpu);
  1404. for (j = 0; j < TVN_SIZE; j++) {
  1405. INIT_LIST_HEAD(base->tv5.vec + j);
  1406. INIT_LIST_HEAD(base->tv4.vec + j);
  1407. INIT_LIST_HEAD(base->tv3.vec + j);
  1408. INIT_LIST_HEAD(base->tv2.vec + j);
  1409. }
  1410. for (j = 0; j < TVR_SIZE; j++)
  1411. INIT_LIST_HEAD(base->tv1.vec + j);
  1412. base->timer_jiffies = jiffies;
  1413. return 0;
  1414. }
  1415. #ifdef CONFIG_HOTPLUG_CPU
  1416. static void migrate_timer_list(tvec_base_t *new_base, struct list_head *head)
  1417. {
  1418. struct timer_list *timer;
  1419. while (!list_empty(head)) {
  1420. timer = list_entry(head->next, struct timer_list, entry);
  1421. detach_timer(timer, 0);
  1422. timer->base = new_base;
  1423. internal_add_timer(new_base, timer);
  1424. }
  1425. }
  1426. static void __devinit migrate_timers(int cpu)
  1427. {
  1428. tvec_base_t *old_base;
  1429. tvec_base_t *new_base;
  1430. int i;
  1431. BUG_ON(cpu_online(cpu));
  1432. old_base = per_cpu(tvec_bases, cpu);
  1433. new_base = get_cpu_var(tvec_bases);
  1434. local_irq_disable();
  1435. double_spin_lock(&new_base->lock, &old_base->lock,
  1436. smp_processor_id() < cpu);
  1437. BUG_ON(old_base->running_timer);
  1438. for (i = 0; i < TVR_SIZE; i++)
  1439. migrate_timer_list(new_base, old_base->tv1.vec + i);
  1440. for (i = 0; i < TVN_SIZE; i++) {
  1441. migrate_timer_list(new_base, old_base->tv2.vec + i);
  1442. migrate_timer_list(new_base, old_base->tv3.vec + i);
  1443. migrate_timer_list(new_base, old_base->tv4.vec + i);
  1444. migrate_timer_list(new_base, old_base->tv5.vec + i);
  1445. }
  1446. double_spin_unlock(&new_base->lock, &old_base->lock,
  1447. smp_processor_id() < cpu);
  1448. local_irq_enable();
  1449. put_cpu_var(tvec_bases);
  1450. }
  1451. #endif /* CONFIG_HOTPLUG_CPU */
  1452. static int __cpuinit timer_cpu_notify(struct notifier_block *self,
  1453. unsigned long action, void *hcpu)
  1454. {
  1455. long cpu = (long)hcpu;
  1456. switch(action) {
  1457. case CPU_UP_PREPARE:
  1458. if (init_timers_cpu(cpu) < 0)
  1459. return NOTIFY_BAD;
  1460. break;
  1461. #ifdef CONFIG_HOTPLUG_CPU
  1462. case CPU_DEAD:
  1463. migrate_timers(cpu);
  1464. break;
  1465. #endif
  1466. default:
  1467. break;
  1468. }
  1469. return NOTIFY_OK;
  1470. }
  1471. static struct notifier_block __cpuinitdata timers_nb = {
  1472. .notifier_call = timer_cpu_notify,
  1473. };
  1474. void __init init_timers(void)
  1475. {
  1476. int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
  1477. (void *)(long)smp_processor_id());
  1478. init_timer_stats();
  1479. BUG_ON(err == NOTIFY_BAD);
  1480. register_cpu_notifier(&timers_nb);
  1481. open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
  1482. }
  1483. #ifdef CONFIG_TIME_INTERPOLATION
  1484. struct time_interpolator *time_interpolator __read_mostly;
  1485. static struct time_interpolator *time_interpolator_list __read_mostly;
  1486. static DEFINE_SPINLOCK(time_interpolator_lock);
  1487. static inline cycles_t time_interpolator_get_cycles(unsigned int src)
  1488. {
  1489. unsigned long (*x)(void);
  1490. switch (src)
  1491. {
  1492. case TIME_SOURCE_FUNCTION:
  1493. x = time_interpolator->addr;
  1494. return x();
  1495. case TIME_SOURCE_MMIO64 :
  1496. return readq_relaxed((void __iomem *)time_interpolator->addr);
  1497. case TIME_SOURCE_MMIO32 :
  1498. return readl_relaxed((void __iomem *)time_interpolator->addr);
  1499. default: return get_cycles();
  1500. }
  1501. }
  1502. static inline u64 time_interpolator_get_counter(int writelock)
  1503. {
  1504. unsigned int src = time_interpolator->source;
  1505. if (time_interpolator->jitter)
  1506. {
  1507. cycles_t lcycle;
  1508. cycles_t now;
  1509. do {
  1510. lcycle = time_interpolator->last_cycle;
  1511. now = time_interpolator_get_cycles(src);
  1512. if (lcycle && time_after(lcycle, now))
  1513. return lcycle;
  1514. /* When holding the xtime write lock, there's no need
  1515. * to add the overhead of the cmpxchg. Readers are
  1516. * force to retry until the write lock is released.
  1517. */
  1518. if (writelock) {
  1519. time_interpolator->last_cycle = now;
  1520. return now;
  1521. }
  1522. /* Keep track of the last timer value returned. The use of cmpxchg here
  1523. * will cause contention in an SMP environment.
  1524. */
  1525. } while (unlikely(cmpxchg(&time_interpolator->last_cycle, lcycle, now) != lcycle));
  1526. return now;
  1527. }
  1528. else
  1529. return time_interpolator_get_cycles(src);
  1530. }
  1531. void time_interpolator_reset(void)
  1532. {
  1533. time_interpolator->offset = 0;
  1534. time_interpolator->last_counter = time_interpolator_get_counter(1);
  1535. }
  1536. #define GET_TI_NSECS(count,i) (((((count) - i->last_counter) & (i)->mask) * (i)->nsec_per_cyc) >> (i)->shift)
  1537. unsigned long time_interpolator_get_offset(void)
  1538. {
  1539. /* If we do not have a time interpolator set up then just return zero */
  1540. if (!time_interpolator)
  1541. return 0;
  1542. return time_interpolator->offset +
  1543. GET_TI_NSECS(time_interpolator_get_counter(0), time_interpolator);
  1544. }
  1545. #define INTERPOLATOR_ADJUST 65536
  1546. #define INTERPOLATOR_MAX_SKIP 10*INTERPOLATOR_ADJUST
  1547. void time_interpolator_update(long delta_nsec)
  1548. {
  1549. u64 counter;
  1550. unsigned long offset;
  1551. /* If there is no time interpolator set up then do nothing */
  1552. if (!time_interpolator)
  1553. return;
  1554. /*
  1555. * The interpolator compensates for late ticks by accumulating the late
  1556. * time in time_interpolator->offset. A tick earlier than expected will
  1557. * lead to a reset of the offset and a corresponding jump of the clock
  1558. * forward. Again this only works if the interpolator clock is running
  1559. * slightly slower than the regular clock and the tuning logic insures
  1560. * that.
  1561. */
  1562. counter = time_interpolator_get_counter(1);
  1563. offset = time_interpolator->offset +
  1564. GET_TI_NSECS(counter, time_interpolator);
  1565. if (delta_nsec < 0 || (unsigned long) delta_nsec < offset)
  1566. time_interpolator->offset = offset - delta_nsec;
  1567. else {
  1568. time_interpolator->skips++;
  1569. time_interpolator->ns_skipped += delta_nsec - offset;
  1570. time_interpolator->offset = 0;
  1571. }
  1572. time_interpolator->last_counter = counter;
  1573. /* Tuning logic for time interpolator invoked every minute or so.
  1574. * Decrease interpolator clock speed if no skips occurred and an offset is carried.
  1575. * Increase interpolator clock speed if we skip too much time.
  1576. */
  1577. if (jiffies % INTERPOLATOR_ADJUST == 0)
  1578. {
  1579. if (time_interpolator->skips == 0 && time_interpolator->offset > tick_nsec)
  1580. time_interpolator->nsec_per_cyc--;
  1581. if (time_interpolator->ns_skipped > INTERPOLATOR_MAX_SKIP && time_interpolator->offset == 0)
  1582. time_interpolator->nsec_per_cyc++;
  1583. time_interpolator->skips = 0;
  1584. time_interpolator->ns_skipped = 0;
  1585. }
  1586. }
  1587. static inline int
  1588. is_better_time_interpolator(struct time_interpolator *new)
  1589. {
  1590. if (!time_interpolator)
  1591. return 1;
  1592. return new->frequency > 2*time_interpolator->frequency ||
  1593. (unsigned long)new->drift < (unsigned long)time_interpolator->drift;
  1594. }
  1595. void
  1596. register_time_interpolator(struct time_interpolator *ti)
  1597. {
  1598. unsigned long flags;
  1599. /* Sanity check */
  1600. BUG_ON(ti->frequency == 0 || ti->mask == 0);
  1601. ti->nsec_per_cyc = ((u64)NSEC_PER_SEC << ti->shift) / ti->frequency;
  1602. spin_lock(&time_interpolator_lock);
  1603. write_seqlock_irqsave(&xtime_lock, flags);
  1604. if (is_better_time_interpolator(ti)) {
  1605. time_interpolator = ti;
  1606. time_interpolator_reset();
  1607. }
  1608. write_sequnlock_irqrestore(&xtime_lock, flags);
  1609. ti->next = time_interpolator_list;
  1610. time_interpolator_list = ti;
  1611. spin_unlock(&time_interpolator_lock);
  1612. }
  1613. void
  1614. unregister_time_interpolator(struct time_interpolator *ti)
  1615. {
  1616. struct time_interpolator *curr, **prev;
  1617. unsigned long flags;
  1618. spin_lock(&time_interpolator_lock);
  1619. prev = &time_interpolator_list;
  1620. for (curr = *prev; curr; curr = curr->next) {
  1621. if (curr == ti) {
  1622. *prev = curr->next;
  1623. break;
  1624. }
  1625. prev = &curr->next;
  1626. }
  1627. clocksource_resume();
  1628. write_seqlock_irqsave(&xtime_lock, flags);
  1629. if (ti == time_interpolator) {
  1630. /* we lost the best time-interpolator: */
  1631. time_interpolator = NULL;
  1632. /* find the next-best interpolator */
  1633. for (curr = time_interpolator_list; curr; curr = curr->next)
  1634. if (is_better_time_interpolator(curr))
  1635. time_interpolator = curr;
  1636. time_interpolator_reset();
  1637. }
  1638. write_sequnlock_irqrestore(&xtime_lock, flags);
  1639. spin_unlock(&time_interpolator_lock);
  1640. }
  1641. #endif /* CONFIG_TIME_INTERPOLATION */
  1642. /**
  1643. * msleep - sleep safely even with waitqueue interruptions
  1644. * @msecs: Time in milliseconds to sleep for
  1645. */
  1646. void msleep(unsigned int msecs)
  1647. {
  1648. unsigned long timeout = msecs_to_jiffies(msecs) + 1;
  1649. while (timeout)
  1650. timeout = schedule_timeout_uninterruptible(timeout);
  1651. }
  1652. EXPORT_SYMBOL(msleep);
  1653. /**
  1654. * msleep_interruptible - sleep waiting for signals
  1655. * @msecs: Time in milliseconds to sleep for
  1656. */
  1657. unsigned long msleep_interruptible(unsigned int msecs)
  1658. {
  1659. unsigned long timeout = msecs_to_jiffies(msecs) + 1;
  1660. while (timeout && !signal_pending(current))
  1661. timeout = schedule_timeout_interruptible(timeout);
  1662. return jiffies_to_msecs(timeout);
  1663. }
  1664. EXPORT_SYMBOL(msleep_interruptible);