]> git.karo-electronics.de Git - karo-tx-linux.git/blob - kernel/timer.c
Merge branch 'for-3.12/upstream' into for-next
[karo-tx-linux.git] / kernel / timer.c
1 /*
2  *  linux/kernel/timer.c
3  *
4  *  Kernel internal timers
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
22 #include <linux/kernel_stat.h>
23 #include <linux/export.h>
24 #include <linux/interrupt.h>
25 #include <linux/percpu.h>
26 #include <linux/init.h>
27 #include <linux/mm.h>
28 #include <linux/swap.h>
29 #include <linux/pid_namespace.h>
30 #include <linux/notifier.h>
31 #include <linux/thread_info.h>
32 #include <linux/time.h>
33 #include <linux/jiffies.h>
34 #include <linux/posix-timers.h>
35 #include <linux/cpu.h>
36 #include <linux/syscalls.h>
37 #include <linux/delay.h>
38 #include <linux/tick.h>
39 #include <linux/kallsyms.h>
40 #include <linux/irq_work.h>
41 #include <linux/sched.h>
42 #include <linux/sched/sysctl.h>
43 #include <linux/slab.h>
44 #include <linux/compat.h>
45
46 #include <asm/uaccess.h>
47 #include <asm/unistd.h>
48 #include <asm/div64.h>
49 #include <asm/timex.h>
50 #include <asm/io.h>
51
52 #define CREATE_TRACE_POINTS
53 #include <trace/events/timer.h>
54
55 u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
56
57 EXPORT_SYMBOL(jiffies_64);
58
59 /*
60  * per-CPU timer vector definitions:
61  */
62 #define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
63 #define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
64 #define TVN_SIZE (1 << TVN_BITS)
65 #define TVR_SIZE (1 << TVR_BITS)
66 #define TVN_MASK (TVN_SIZE - 1)
67 #define TVR_MASK (TVR_SIZE - 1)
68 #define MAX_TVAL ((unsigned long)((1ULL << (TVR_BITS + 4*TVN_BITS)) - 1))
69
70 struct tvec {
71         struct list_head vec[TVN_SIZE];
72 };
73
74 struct tvec_root {
75         struct list_head vec[TVR_SIZE];
76 };
77
78 struct tvec_base {
79         spinlock_t lock;
80         struct timer_list *running_timer;
81         unsigned long timer_jiffies;
82         unsigned long next_timer;
83         unsigned long active_timers;
84         struct tvec_root tv1;
85         struct tvec tv2;
86         struct tvec tv3;
87         struct tvec tv4;
88         struct tvec tv5;
89 } ____cacheline_aligned;
90
91 struct tvec_base boot_tvec_bases;
92 EXPORT_SYMBOL(boot_tvec_bases);
93 static DEFINE_PER_CPU(struct tvec_base *, tvec_bases) = &boot_tvec_bases;
94
95 /* Functions below help us manage 'deferrable' flag */
96 static inline unsigned int tbase_get_deferrable(struct tvec_base *base)
97 {
98         return ((unsigned int)(unsigned long)base & TIMER_DEFERRABLE);
99 }
100
101 static inline unsigned int tbase_get_irqsafe(struct tvec_base *base)
102 {
103         return ((unsigned int)(unsigned long)base & TIMER_IRQSAFE);
104 }
105
106 static inline struct tvec_base *tbase_get_base(struct tvec_base *base)
107 {
108         return ((struct tvec_base *)((unsigned long)base & ~TIMER_FLAG_MASK));
109 }
110
111 static inline void
112 timer_set_base(struct timer_list *timer, struct tvec_base *new_base)
113 {
114         unsigned long flags = (unsigned long)timer->base & TIMER_FLAG_MASK;
115
116         timer->base = (struct tvec_base *)((unsigned long)(new_base) | flags);
117 }
118
119 static unsigned long round_jiffies_common(unsigned long j, int cpu,
120                 bool force_up)
121 {
122         int rem;
123         unsigned long original = j;
124
125         /*
126          * We don't want all cpus firing their timers at once hitting the
127          * same lock or cachelines, so we skew each extra cpu with an extra
128          * 3 jiffies. This 3 jiffies came originally from the mm/ code which
129          * already did this.
130          * The skew is done by adding 3*cpunr, then round, then subtract this
131          * extra offset again.
132          */
133         j += cpu * 3;
134
135         rem = j % HZ;
136
137         /*
138          * If the target jiffie is just after a whole second (which can happen
139          * due to delays of the timer irq, long irq off times etc etc) then
140          * we should round down to the whole second, not up. Use 1/4th second
141          * as cutoff for this rounding as an extreme upper bound for this.
142          * But never round down if @force_up is set.
143          */
144         if (rem < HZ/4 && !force_up) /* round down */
145                 j = j - rem;
146         else /* round up */
147                 j = j - rem + HZ;
148
149         /* now that we have rounded, subtract the extra skew again */
150         j -= cpu * 3;
151
152         /*
153          * Make sure j is still in the future. Otherwise return the
154          * unmodified value.
155          */
156         return time_is_after_jiffies(j) ? j : original;
157 }
158
159 /**
160  * __round_jiffies - function to round jiffies to a full second
161  * @j: the time in (absolute) jiffies that should be rounded
162  * @cpu: the processor number on which the timeout will happen
163  *
164  * __round_jiffies() rounds an absolute time in the future (in jiffies)
165  * up or down to (approximately) full seconds. This is useful for timers
166  * for which the exact time they fire does not matter too much, as long as
167  * they fire approximately every X seconds.
168  *
169  * By rounding these timers to whole seconds, all such timers will fire
170  * at the same time, rather than at various times spread out. The goal
171  * of this is to have the CPU wake up less, which saves power.
172  *
173  * The exact rounding is skewed for each processor to avoid all
174  * processors firing at the exact same time, which could lead
175  * to lock contention or spurious cache line bouncing.
176  *
177  * The return value is the rounded version of the @j parameter.
178  */
179 unsigned long __round_jiffies(unsigned long j, int cpu)
180 {
181         return round_jiffies_common(j, cpu, false);
182 }
183 EXPORT_SYMBOL_GPL(__round_jiffies);
184
185 /**
186  * __round_jiffies_relative - function to round jiffies to a full second
187  * @j: the time in (relative) jiffies that should be rounded
188  * @cpu: the processor number on which the timeout will happen
189  *
190  * __round_jiffies_relative() rounds a time delta  in the future (in jiffies)
191  * up or down to (approximately) full seconds. This is useful for timers
192  * for which the exact time they fire does not matter too much, as long as
193  * they fire approximately every X seconds.
194  *
195  * By rounding these timers to whole seconds, all such timers will fire
196  * at the same time, rather than at various times spread out. The goal
197  * of this is to have the CPU wake up less, which saves power.
198  *
199  * The exact rounding is skewed for each processor to avoid all
200  * processors firing at the exact same time, which could lead
201  * to lock contention or spurious cache line bouncing.
202  *
203  * The return value is the rounded version of the @j parameter.
204  */
205 unsigned long __round_jiffies_relative(unsigned long j, int cpu)
206 {
207         unsigned long j0 = jiffies;
208
209         /* Use j0 because jiffies might change while we run */
210         return round_jiffies_common(j + j0, cpu, false) - j0;
211 }
212 EXPORT_SYMBOL_GPL(__round_jiffies_relative);
213
214 /**
215  * round_jiffies - function to round jiffies to a full second
216  * @j: the time in (absolute) jiffies that should be rounded
217  *
218  * round_jiffies() rounds an absolute time in the future (in jiffies)
219  * up or down to (approximately) full seconds. This is useful for timers
220  * for which the exact time they fire does not matter too much, as long as
221  * they fire approximately every X seconds.
222  *
223  * By rounding these timers to whole seconds, all such timers will fire
224  * at the same time, rather than at various times spread out. The goal
225  * of this is to have the CPU wake up less, which saves power.
226  *
227  * The return value is the rounded version of the @j parameter.
228  */
229 unsigned long round_jiffies(unsigned long j)
230 {
231         return round_jiffies_common(j, raw_smp_processor_id(), false);
232 }
233 EXPORT_SYMBOL_GPL(round_jiffies);
234
235 /**
236  * round_jiffies_relative - function to round jiffies to a full second
237  * @j: the time in (relative) jiffies that should be rounded
238  *
239  * round_jiffies_relative() rounds a time delta  in the future (in jiffies)
240  * up or down to (approximately) full seconds. This is useful for timers
241  * for which the exact time they fire does not matter too much, as long as
242  * they fire approximately every X seconds.
243  *
244  * By rounding these timers to whole seconds, all such timers will fire
245  * at the same time, rather than at various times spread out. The goal
246  * of this is to have the CPU wake up less, which saves power.
247  *
248  * The return value is the rounded version of the @j parameter.
249  */
250 unsigned long round_jiffies_relative(unsigned long j)
251 {
252         return __round_jiffies_relative(j, raw_smp_processor_id());
253 }
254 EXPORT_SYMBOL_GPL(round_jiffies_relative);
255
256 /**
257  * __round_jiffies_up - function to round jiffies up to a full second
258  * @j: the time in (absolute) jiffies that should be rounded
259  * @cpu: the processor number on which the timeout will happen
260  *
261  * This is the same as __round_jiffies() except that it will never
262  * round down.  This is useful for timeouts for which the exact time
263  * of firing does not matter too much, as long as they don't fire too
264  * early.
265  */
266 unsigned long __round_jiffies_up(unsigned long j, int cpu)
267 {
268         return round_jiffies_common(j, cpu, true);
269 }
270 EXPORT_SYMBOL_GPL(__round_jiffies_up);
271
272 /**
273  * __round_jiffies_up_relative - function to round jiffies up to a full second
274  * @j: the time in (relative) jiffies that should be rounded
275  * @cpu: the processor number on which the timeout will happen
276  *
277  * This is the same as __round_jiffies_relative() except that it will never
278  * round down.  This is useful for timeouts for which the exact time
279  * of firing does not matter too much, as long as they don't fire too
280  * early.
281  */
282 unsigned long __round_jiffies_up_relative(unsigned long j, int cpu)
283 {
284         unsigned long j0 = jiffies;
285
286         /* Use j0 because jiffies might change while we run */
287         return round_jiffies_common(j + j0, cpu, true) - j0;
288 }
289 EXPORT_SYMBOL_GPL(__round_jiffies_up_relative);
290
291 /**
292  * round_jiffies_up - function to round jiffies up to a full second
293  * @j: the time in (absolute) jiffies that should be rounded
294  *
295  * This is the same as round_jiffies() except that it will never
296  * round down.  This is useful for timeouts for which the exact time
297  * of firing does not matter too much, as long as they don't fire too
298  * early.
299  */
300 unsigned long round_jiffies_up(unsigned long j)
301 {
302         return round_jiffies_common(j, raw_smp_processor_id(), true);
303 }
304 EXPORT_SYMBOL_GPL(round_jiffies_up);
305
306 /**
307  * round_jiffies_up_relative - function to round jiffies up to a full second
308  * @j: the time in (relative) jiffies that should be rounded
309  *
310  * This is the same as round_jiffies_relative() except that it will never
311  * round down.  This is useful for timeouts for which the exact time
312  * of firing does not matter too much, as long as they don't fire too
313  * early.
314  */
315 unsigned long round_jiffies_up_relative(unsigned long j)
316 {
317         return __round_jiffies_up_relative(j, raw_smp_processor_id());
318 }
319 EXPORT_SYMBOL_GPL(round_jiffies_up_relative);
320
321 /**
322  * set_timer_slack - set the allowed slack for a timer
323  * @timer: the timer to be modified
324  * @slack_hz: the amount of time (in jiffies) allowed for rounding
325  *
326  * Set the amount of time, in jiffies, that a certain timer has
327  * in terms of slack. By setting this value, the timer subsystem
328  * will schedule the actual timer somewhere between
329  * the time mod_timer() asks for, and that time plus the slack.
330  *
331  * By setting the slack to -1, a percentage of the delay is used
332  * instead.
333  */
334 void set_timer_slack(struct timer_list *timer, int slack_hz)
335 {
336         timer->slack = slack_hz;
337 }
338 EXPORT_SYMBOL_GPL(set_timer_slack);
339
340 static void
341 __internal_add_timer(struct tvec_base *base, struct timer_list *timer)
342 {
343         unsigned long expires = timer->expires;
344         unsigned long idx = expires - base->timer_jiffies;
345         struct list_head *vec;
346
347         if (idx < TVR_SIZE) {
348                 int i = expires & TVR_MASK;
349                 vec = base->tv1.vec + i;
350         } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
351                 int i = (expires >> TVR_BITS) & TVN_MASK;
352                 vec = base->tv2.vec + i;
353         } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
354                 int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
355                 vec = base->tv3.vec + i;
356         } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
357                 int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
358                 vec = base->tv4.vec + i;
359         } else if ((signed long) idx < 0) {
360                 /*
361                  * Can happen if you add a timer with expires == jiffies,
362                  * or you set a timer to go off in the past
363                  */
364                 vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
365         } else {
366                 int i;
367                 /* If the timeout is larger than MAX_TVAL (on 64-bit
368                  * architectures or with CONFIG_BASE_SMALL=1) then we
369                  * use the maximum timeout.
370                  */
371                 if (idx > MAX_TVAL) {
372                         idx = MAX_TVAL;
373                         expires = idx + base->timer_jiffies;
374                 }
375                 i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
376                 vec = base->tv5.vec + i;
377         }
378         /*
379          * Timers are FIFO:
380          */
381         list_add_tail(&timer->entry, vec);
382 }
383
384 static void internal_add_timer(struct tvec_base *base, struct timer_list *timer)
385 {
386         __internal_add_timer(base, timer);
387         /*
388          * Update base->active_timers and base->next_timer
389          */
390         if (!tbase_get_deferrable(timer->base)) {
391                 if (time_before(timer->expires, base->next_timer))
392                         base->next_timer = timer->expires;
393                 base->active_timers++;
394         }
395 }
396
397 #ifdef CONFIG_TIMER_STATS
398 void __timer_stats_timer_set_start_info(struct timer_list *timer, void *addr)
399 {
400         if (timer->start_site)
401                 return;
402
403         timer->start_site = addr;
404         memcpy(timer->start_comm, current->comm, TASK_COMM_LEN);
405         timer->start_pid = current->pid;
406 }
407
408 static void timer_stats_account_timer(struct timer_list *timer)
409 {
410         unsigned int flag = 0;
411
412         if (likely(!timer->start_site))
413                 return;
414         if (unlikely(tbase_get_deferrable(timer->base)))
415                 flag |= TIMER_STATS_FLAG_DEFERRABLE;
416
417         timer_stats_update_stats(timer, timer->start_pid, timer->start_site,
418                                  timer->function, timer->start_comm, flag);
419 }
420
421 #else
422 static void timer_stats_account_timer(struct timer_list *timer) {}
423 #endif
424
425 #ifdef CONFIG_DEBUG_OBJECTS_TIMERS
426
427 static struct debug_obj_descr timer_debug_descr;
428
429 static void *timer_debug_hint(void *addr)
430 {
431         return ((struct timer_list *) addr)->function;
432 }
433
434 /*
435  * fixup_init is called when:
436  * - an active object is initialized
437  */
438 static int timer_fixup_init(void *addr, enum debug_obj_state state)
439 {
440         struct timer_list *timer = addr;
441
442         switch (state) {
443         case ODEBUG_STATE_ACTIVE:
444                 del_timer_sync(timer);
445                 debug_object_init(timer, &timer_debug_descr);
446                 return 1;
447         default:
448                 return 0;
449         }
450 }
451
452 /* Stub timer callback for improperly used timers. */
453 static void stub_timer(unsigned long data)
454 {
455         WARN_ON(1);
456 }
457
458 /*
459  * fixup_activate is called when:
460  * - an active object is activated
461  * - an unknown object is activated (might be a statically initialized object)
462  */
463 static int timer_fixup_activate(void *addr, enum debug_obj_state state)
464 {
465         struct timer_list *timer = addr;
466
467         switch (state) {
468
469         case ODEBUG_STATE_NOTAVAILABLE:
470                 /*
471                  * This is not really a fixup. The timer was
472                  * statically initialized. We just make sure that it
473                  * is tracked in the object tracker.
474                  */
475                 if (timer->entry.next == NULL &&
476                     timer->entry.prev == TIMER_ENTRY_STATIC) {
477                         debug_object_init(timer, &timer_debug_descr);
478                         debug_object_activate(timer, &timer_debug_descr);
479                         return 0;
480                 } else {
481                         setup_timer(timer, stub_timer, 0);
482                         return 1;
483                 }
484                 return 0;
485
486         case ODEBUG_STATE_ACTIVE:
487                 WARN_ON(1);
488
489         default:
490                 return 0;
491         }
492 }
493
494 /*
495  * fixup_free is called when:
496  * - an active object is freed
497  */
498 static int timer_fixup_free(void *addr, enum debug_obj_state state)
499 {
500         struct timer_list *timer = addr;
501
502         switch (state) {
503         case ODEBUG_STATE_ACTIVE:
504                 del_timer_sync(timer);
505                 debug_object_free(timer, &timer_debug_descr);
506                 return 1;
507         default:
508                 return 0;
509         }
510 }
511
512 /*
513  * fixup_assert_init is called when:
514  * - an untracked/uninit-ed object is found
515  */
516 static int timer_fixup_assert_init(void *addr, enum debug_obj_state state)
517 {
518         struct timer_list *timer = addr;
519
520         switch (state) {
521         case ODEBUG_STATE_NOTAVAILABLE:
522                 if (timer->entry.prev == TIMER_ENTRY_STATIC) {
523                         /*
524                          * This is not really a fixup. The timer was
525                          * statically initialized. We just make sure that it
526                          * is tracked in the object tracker.
527                          */
528                         debug_object_init(timer, &timer_debug_descr);
529                         return 0;
530                 } else {
531                         setup_timer(timer, stub_timer, 0);
532                         return 1;
533                 }
534         default:
535                 return 0;
536         }
537 }
538
539 static struct debug_obj_descr timer_debug_descr = {
540         .name                   = "timer_list",
541         .debug_hint             = timer_debug_hint,
542         .fixup_init             = timer_fixup_init,
543         .fixup_activate         = timer_fixup_activate,
544         .fixup_free             = timer_fixup_free,
545         .fixup_assert_init      = timer_fixup_assert_init,
546 };
547
548 static inline void debug_timer_init(struct timer_list *timer)
549 {
550         debug_object_init(timer, &timer_debug_descr);
551 }
552
553 static inline void debug_timer_activate(struct timer_list *timer)
554 {
555         debug_object_activate(timer, &timer_debug_descr);
556 }
557
558 static inline void debug_timer_deactivate(struct timer_list *timer)
559 {
560         debug_object_deactivate(timer, &timer_debug_descr);
561 }
562
563 static inline void debug_timer_free(struct timer_list *timer)
564 {
565         debug_object_free(timer, &timer_debug_descr);
566 }
567
568 static inline void debug_timer_assert_init(struct timer_list *timer)
569 {
570         debug_object_assert_init(timer, &timer_debug_descr);
571 }
572
573 static void do_init_timer(struct timer_list *timer, unsigned int flags,
574                           const char *name, struct lock_class_key *key);
575
576 void init_timer_on_stack_key(struct timer_list *timer, unsigned int flags,
577                              const char *name, struct lock_class_key *key)
578 {
579         debug_object_init_on_stack(timer, &timer_debug_descr);
580         do_init_timer(timer, flags, name, key);
581 }
582 EXPORT_SYMBOL_GPL(init_timer_on_stack_key);
583
584 void destroy_timer_on_stack(struct timer_list *timer)
585 {
586         debug_object_free(timer, &timer_debug_descr);
587 }
588 EXPORT_SYMBOL_GPL(destroy_timer_on_stack);
589
590 #else
591 static inline void debug_timer_init(struct timer_list *timer) { }
592 static inline void debug_timer_activate(struct timer_list *timer) { }
593 static inline void debug_timer_deactivate(struct timer_list *timer) { }
594 static inline void debug_timer_assert_init(struct timer_list *timer) { }
595 #endif
596
597 static inline void debug_init(struct timer_list *timer)
598 {
599         debug_timer_init(timer);
600         trace_timer_init(timer);
601 }
602
603 static inline void
604 debug_activate(struct timer_list *timer, unsigned long expires)
605 {
606         debug_timer_activate(timer);
607         trace_timer_start(timer, expires);
608 }
609
610 static inline void debug_deactivate(struct timer_list *timer)
611 {
612         debug_timer_deactivate(timer);
613         trace_timer_cancel(timer);
614 }
615
616 static inline void debug_assert_init(struct timer_list *timer)
617 {
618         debug_timer_assert_init(timer);
619 }
620
621 static void do_init_timer(struct timer_list *timer, unsigned int flags,
622                           const char *name, struct lock_class_key *key)
623 {
624         struct tvec_base *base = __raw_get_cpu_var(tvec_bases);
625
626         timer->entry.next = NULL;
627         timer->base = (void *)((unsigned long)base | flags);
628         timer->slack = -1;
629 #ifdef CONFIG_TIMER_STATS
630         timer->start_site = NULL;
631         timer->start_pid = -1;
632         memset(timer->start_comm, 0, TASK_COMM_LEN);
633 #endif
634         lockdep_init_map(&timer->lockdep_map, name, key, 0);
635 }
636
637 /**
638  * init_timer_key - initialize a timer
639  * @timer: the timer to be initialized
640  * @flags: timer flags
641  * @name: name of the timer
642  * @key: lockdep class key of the fake lock used for tracking timer
643  *       sync lock dependencies
644  *
645  * init_timer_key() must be done to a timer prior calling *any* of the
646  * other timer functions.
647  */
648 void init_timer_key(struct timer_list *timer, unsigned int flags,
649                     const char *name, struct lock_class_key *key)
650 {
651         debug_init(timer);
652         do_init_timer(timer, flags, name, key);
653 }
654 EXPORT_SYMBOL(init_timer_key);
655
656 static inline void detach_timer(struct timer_list *timer, bool clear_pending)
657 {
658         struct list_head *entry = &timer->entry;
659
660         debug_deactivate(timer);
661
662         __list_del(entry->prev, entry->next);
663         if (clear_pending)
664                 entry->next = NULL;
665         entry->prev = LIST_POISON2;
666 }
667
668 static inline void
669 detach_expired_timer(struct timer_list *timer, struct tvec_base *base)
670 {
671         detach_timer(timer, true);
672         if (!tbase_get_deferrable(timer->base))
673                 base->active_timers--;
674 }
675
676 static int detach_if_pending(struct timer_list *timer, struct tvec_base *base,
677                              bool clear_pending)
678 {
679         if (!timer_pending(timer))
680                 return 0;
681
682         detach_timer(timer, clear_pending);
683         if (!tbase_get_deferrable(timer->base)) {
684                 base->active_timers--;
685                 if (timer->expires == base->next_timer)
686                         base->next_timer = base->timer_jiffies;
687         }
688         return 1;
689 }
690
691 /*
692  * We are using hashed locking: holding per_cpu(tvec_bases).lock
693  * means that all timers which are tied to this base via timer->base are
694  * locked, and the base itself is locked too.
695  *
696  * So __run_timers/migrate_timers can safely modify all timers which could
697  * be found on ->tvX lists.
698  *
699  * When the timer's base is locked, and the timer removed from list, it is
700  * possible to set timer->base = NULL and drop the lock: the timer remains
701  * locked.
702  */
703 static struct tvec_base *lock_timer_base(struct timer_list *timer,
704                                         unsigned long *flags)
705         __acquires(timer->base->lock)
706 {
707         struct tvec_base *base;
708
709         for (;;) {
710                 struct tvec_base *prelock_base = timer->base;
711                 base = tbase_get_base(prelock_base);
712                 if (likely(base != NULL)) {
713                         spin_lock_irqsave(&base->lock, *flags);
714                         if (likely(prelock_base == timer->base))
715                                 return base;
716                         /* The timer has migrated to another CPU */
717                         spin_unlock_irqrestore(&base->lock, *flags);
718                 }
719                 cpu_relax();
720         }
721 }
722
723 static inline int
724 __mod_timer(struct timer_list *timer, unsigned long expires,
725                                                 bool pending_only, int pinned)
726 {
727         struct tvec_base *base, *new_base;
728         unsigned long flags;
729         int ret = 0 , cpu;
730
731         timer_stats_timer_set_start_info(timer);
732         BUG_ON(!timer->function);
733
734         base = lock_timer_base(timer, &flags);
735
736         ret = detach_if_pending(timer, base, false);
737         if (!ret && pending_only)
738                 goto out_unlock;
739
740         debug_activate(timer, expires);
741
742         cpu = smp_processor_id();
743
744 #if defined(CONFIG_NO_HZ_COMMON) && defined(CONFIG_SMP)
745         if (!pinned && get_sysctl_timer_migration() && idle_cpu(cpu))
746                 cpu = get_nohz_timer_target();
747 #endif
748         new_base = per_cpu(tvec_bases, cpu);
749
750         if (base != new_base) {
751                 /*
752                  * We are trying to schedule the timer on the local CPU.
753                  * However we can't change timer's base while it is running,
754                  * otherwise del_timer_sync() can't detect that the timer's
755                  * handler yet has not finished. This also guarantees that
756                  * the timer is serialized wrt itself.
757                  */
758                 if (likely(base->running_timer != timer)) {
759                         /* See the comment in lock_timer_base() */
760                         timer_set_base(timer, NULL);
761                         spin_unlock(&base->lock);
762                         base = new_base;
763                         spin_lock(&base->lock);
764                         timer_set_base(timer, base);
765                 }
766         }
767
768         timer->expires = expires;
769         internal_add_timer(base, timer);
770
771 out_unlock:
772         spin_unlock_irqrestore(&base->lock, flags);
773
774         return ret;
775 }
776
777 /**
778  * mod_timer_pending - modify a pending timer's timeout
779  * @timer: the pending timer to be modified
780  * @expires: new timeout in jiffies
781  *
782  * mod_timer_pending() is the same for pending timers as mod_timer(),
783  * but will not re-activate and modify already deleted timers.
784  *
785  * It is useful for unserialized use of timers.
786  */
787 int mod_timer_pending(struct timer_list *timer, unsigned long expires)
788 {
789         return __mod_timer(timer, expires, true, TIMER_NOT_PINNED);
790 }
791 EXPORT_SYMBOL(mod_timer_pending);
792
793 /*
794  * Decide where to put the timer while taking the slack into account
795  *
796  * Algorithm:
797  *   1) calculate the maximum (absolute) time
798  *   2) calculate the highest bit where the expires and new max are different
799  *   3) use this bit to make a mask
800  *   4) use the bitmask to round down the maximum time, so that all last
801  *      bits are zeros
802  */
803 static inline
804 unsigned long apply_slack(struct timer_list *timer, unsigned long expires)
805 {
806         unsigned long expires_limit, mask;
807         int bit;
808
809         if (timer->slack >= 0) {
810                 expires_limit = expires + timer->slack;
811         } else {
812                 long delta = expires - jiffies;
813
814                 if (delta < 256)
815                         return expires;
816
817                 expires_limit = expires + delta / 256;
818         }
819         mask = expires ^ expires_limit;
820         if (mask == 0)
821                 return expires;
822
823         bit = find_last_bit(&mask, BITS_PER_LONG);
824
825         mask = (1 << bit) - 1;
826
827         expires_limit = expires_limit & ~(mask);
828
829         return expires_limit;
830 }
831
832 /**
833  * mod_timer - modify a timer's timeout
834  * @timer: the timer to be modified
835  * @expires: new timeout in jiffies
836  *
837  * mod_timer() is a more efficient way to update the expire field of an
838  * active timer (if the timer is inactive it will be activated)
839  *
840  * mod_timer(timer, expires) is equivalent to:
841  *
842  *     del_timer(timer); timer->expires = expires; add_timer(timer);
843  *
844  * Note that if there are multiple unserialized concurrent users of the
845  * same timer, then mod_timer() is the only safe way to modify the timeout,
846  * since add_timer() cannot modify an already running timer.
847  *
848  * The function returns whether it has modified a pending timer or not.
849  * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
850  * active timer returns 1.)
851  */
852 int mod_timer(struct timer_list *timer, unsigned long expires)
853 {
854         expires = apply_slack(timer, expires);
855
856         /*
857          * This is a common optimization triggered by the
858          * networking code - if the timer is re-modified
859          * to be the same thing then just return:
860          */
861         if (timer_pending(timer) && timer->expires == expires)
862                 return 1;
863
864         return __mod_timer(timer, expires, false, TIMER_NOT_PINNED);
865 }
866 EXPORT_SYMBOL(mod_timer);
867
868 /**
869  * mod_timer_pinned - modify a timer's timeout
870  * @timer: the timer to be modified
871  * @expires: new timeout in jiffies
872  *
873  * mod_timer_pinned() is a way to update the expire field of an
874  * active timer (if the timer is inactive it will be activated)
875  * and to ensure that the timer is scheduled on the current CPU.
876  *
877  * Note that this does not prevent the timer from being migrated
878  * when the current CPU goes offline.  If this is a problem for
879  * you, use CPU-hotplug notifiers to handle it correctly, for
880  * example, cancelling the timer when the corresponding CPU goes
881  * offline.
882  *
883  * mod_timer_pinned(timer, expires) is equivalent to:
884  *
885  *     del_timer(timer); timer->expires = expires; add_timer(timer);
886  */
887 int mod_timer_pinned(struct timer_list *timer, unsigned long expires)
888 {
889         if (timer->expires == expires && timer_pending(timer))
890                 return 1;
891
892         return __mod_timer(timer, expires, false, TIMER_PINNED);
893 }
894 EXPORT_SYMBOL(mod_timer_pinned);
895
896 /**
897  * add_timer - start a timer
898  * @timer: the timer to be added
899  *
900  * The kernel will do a ->function(->data) callback from the
901  * timer interrupt at the ->expires point in the future. The
902  * current time is 'jiffies'.
903  *
904  * The timer's ->expires, ->function (and if the handler uses it, ->data)
905  * fields must be set prior calling this function.
906  *
907  * Timers with an ->expires field in the past will be executed in the next
908  * timer tick.
909  */
910 void add_timer(struct timer_list *timer)
911 {
912         BUG_ON(timer_pending(timer));
913         mod_timer(timer, timer->expires);
914 }
915 EXPORT_SYMBOL(add_timer);
916
917 /**
918  * add_timer_on - start a timer on a particular CPU
919  * @timer: the timer to be added
920  * @cpu: the CPU to start it on
921  *
922  * This is not very scalable on SMP. Double adds are not possible.
923  */
924 void add_timer_on(struct timer_list *timer, int cpu)
925 {
926         struct tvec_base *base = per_cpu(tvec_bases, cpu);
927         unsigned long flags;
928
929         timer_stats_timer_set_start_info(timer);
930         BUG_ON(timer_pending(timer) || !timer->function);
931         spin_lock_irqsave(&base->lock, flags);
932         timer_set_base(timer, base);
933         debug_activate(timer, timer->expires);
934         internal_add_timer(base, timer);
935         /*
936          * Check whether the other CPU is in dynticks mode and needs
937          * to be triggered to reevaluate the timer wheel.
938          * We are protected against the other CPU fiddling
939          * with the timer by holding the timer base lock. This also
940          * makes sure that a CPU on the way to stop its tick can not
941          * evaluate the timer wheel.
942          */
943         wake_up_nohz_cpu(cpu);
944         spin_unlock_irqrestore(&base->lock, flags);
945 }
946 EXPORT_SYMBOL_GPL(add_timer_on);
947
948 /**
949  * del_timer - deactive a timer.
950  * @timer: the timer to be deactivated
951  *
952  * del_timer() deactivates a timer - this works on both active and inactive
953  * timers.
954  *
955  * The function returns whether it has deactivated a pending timer or not.
956  * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
957  * active timer returns 1.)
958  */
959 int del_timer(struct timer_list *timer)
960 {
961         struct tvec_base *base;
962         unsigned long flags;
963         int ret = 0;
964
965         debug_assert_init(timer);
966
967         timer_stats_timer_clear_start_info(timer);
968         if (timer_pending(timer)) {
969                 base = lock_timer_base(timer, &flags);
970                 ret = detach_if_pending(timer, base, true);
971                 spin_unlock_irqrestore(&base->lock, flags);
972         }
973
974         return ret;
975 }
976 EXPORT_SYMBOL(del_timer);
977
978 /**
979  * try_to_del_timer_sync - Try to deactivate a timer
980  * @timer: timer do del
981  *
982  * This function tries to deactivate a timer. Upon successful (ret >= 0)
983  * exit the timer is not queued and the handler is not running on any CPU.
984  */
985 int try_to_del_timer_sync(struct timer_list *timer)
986 {
987         struct tvec_base *base;
988         unsigned long flags;
989         int ret = -1;
990
991         debug_assert_init(timer);
992
993         base = lock_timer_base(timer, &flags);
994
995         if (base->running_timer != timer) {
996                 timer_stats_timer_clear_start_info(timer);
997                 ret = detach_if_pending(timer, base, true);
998         }
999         spin_unlock_irqrestore(&base->lock, flags);
1000
1001         return ret;
1002 }
1003 EXPORT_SYMBOL(try_to_del_timer_sync);
1004
1005 #ifdef CONFIG_SMP
1006 /**
1007  * del_timer_sync - deactivate a timer and wait for the handler to finish.
1008  * @timer: the timer to be deactivated
1009  *
1010  * This function only differs from del_timer() on SMP: besides deactivating
1011  * the timer it also makes sure the handler has finished executing on other
1012  * CPUs.
1013  *
1014  * Synchronization rules: Callers must prevent restarting of the timer,
1015  * otherwise this function is meaningless. It must not be called from
1016  * interrupt contexts unless the timer is an irqsafe one. The caller must
1017  * not hold locks which would prevent completion of the timer's
1018  * handler. The timer's handler must not call add_timer_on(). Upon exit the
1019  * timer is not queued and the handler is not running on any CPU.
1020  *
1021  * Note: For !irqsafe timers, you must not hold locks that are held in
1022  *   interrupt context while calling this function. Even if the lock has
1023  *   nothing to do with the timer in question.  Here's why:
1024  *
1025  *    CPU0                             CPU1
1026  *    ----                             ----
1027  *                                   <SOFTIRQ>
1028  *                                   call_timer_fn();
1029  *                                     base->running_timer = mytimer;
1030  *  spin_lock_irq(somelock);
1031  *                                     <IRQ>
1032  *                                        spin_lock(somelock);
1033  *  del_timer_sync(mytimer);
1034  *   while (base->running_timer == mytimer);
1035  *
1036  * Now del_timer_sync() will never return and never release somelock.
1037  * The interrupt on the other CPU is waiting to grab somelock but
1038  * it has interrupted the softirq that CPU0 is waiting to finish.
1039  *
1040  * The function returns whether it has deactivated a pending timer or not.
1041  */
1042 int del_timer_sync(struct timer_list *timer)
1043 {
1044 #ifdef CONFIG_LOCKDEP
1045         unsigned long flags;
1046
1047         /*
1048          * If lockdep gives a backtrace here, please reference
1049          * the synchronization rules above.
1050          */
1051         local_irq_save(flags);
1052         lock_map_acquire(&timer->lockdep_map);
1053         lock_map_release(&timer->lockdep_map);
1054         local_irq_restore(flags);
1055 #endif
1056         /*
1057          * don't use it in hardirq context, because it
1058          * could lead to deadlock.
1059          */
1060         WARN_ON(in_irq() && !tbase_get_irqsafe(timer->base));
1061         for (;;) {
1062                 int ret = try_to_del_timer_sync(timer);
1063                 if (ret >= 0)
1064                         return ret;
1065                 cpu_relax();
1066         }
1067 }
1068 EXPORT_SYMBOL(del_timer_sync);
1069 #endif
1070
1071 static int cascade(struct tvec_base *base, struct tvec *tv, int index)
1072 {
1073         /* cascade all the timers from tv up one level */
1074         struct timer_list *timer, *tmp;
1075         struct list_head tv_list;
1076
1077         list_replace_init(tv->vec + index, &tv_list);
1078
1079         /*
1080          * We are removing _all_ timers from the list, so we
1081          * don't have to detach them individually.
1082          */
1083         list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
1084                 BUG_ON(tbase_get_base(timer->base) != base);
1085                 /* No accounting, while moving them */
1086                 __internal_add_timer(base, timer);
1087         }
1088
1089         return index;
1090 }
1091
1092 static void call_timer_fn(struct timer_list *timer, void (*fn)(unsigned long),
1093                           unsigned long data)
1094 {
1095         int preempt_count = preempt_count();
1096
1097 #ifdef CONFIG_LOCKDEP
1098         /*
1099          * It is permissible to free the timer from inside the
1100          * function that is called from it, this we need to take into
1101          * account for lockdep too. To avoid bogus "held lock freed"
1102          * warnings as well as problems when looking into
1103          * timer->lockdep_map, make a copy and use that here.
1104          */
1105         struct lockdep_map lockdep_map;
1106
1107         lockdep_copy_map(&lockdep_map, &timer->lockdep_map);
1108 #endif
1109         /*
1110          * Couple the lock chain with the lock chain at
1111          * del_timer_sync() by acquiring the lock_map around the fn()
1112          * call here and in del_timer_sync().
1113          */
1114         lock_map_acquire(&lockdep_map);
1115
1116         trace_timer_expire_entry(timer);
1117         fn(data);
1118         trace_timer_expire_exit(timer);
1119
1120         lock_map_release(&lockdep_map);
1121
1122         if (preempt_count != preempt_count()) {
1123                 WARN_ONCE(1, "timer: %pF preempt leak: %08x -> %08x\n",
1124                           fn, preempt_count, preempt_count());
1125                 /*
1126                  * Restore the preempt count. That gives us a decent
1127                  * chance to survive and extract information. If the
1128                  * callback kept a lock held, bad luck, but not worse
1129                  * than the BUG() we had.
1130                  */
1131                 preempt_count() = preempt_count;
1132         }
1133 }
1134
1135 #define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)
1136
1137 /**
1138  * __run_timers - run all expired timers (if any) on this CPU.
1139  * @base: the timer vector to be processed.
1140  *
1141  * This function cascades all vectors and executes all expired timer
1142  * vectors.
1143  */
1144 static inline void __run_timers(struct tvec_base *base)
1145 {
1146         struct timer_list *timer;
1147
1148         spin_lock_irq(&base->lock);
1149         while (time_after_eq(jiffies, base->timer_jiffies)) {
1150                 struct list_head work_list;
1151                 struct list_head *head = &work_list;
1152                 int index = base->timer_jiffies & TVR_MASK;
1153
1154                 /*
1155                  * Cascade timers:
1156                  */
1157                 if (!index &&
1158                         (!cascade(base, &base->tv2, INDEX(0))) &&
1159                                 (!cascade(base, &base->tv3, INDEX(1))) &&
1160                                         !cascade(base, &base->tv4, INDEX(2)))
1161                         cascade(base, &base->tv5, INDEX(3));
1162                 ++base->timer_jiffies;
1163                 list_replace_init(base->tv1.vec + index, &work_list);
1164                 while (!list_empty(head)) {
1165                         void (*fn)(unsigned long);
1166                         unsigned long data;
1167                         bool irqsafe;
1168
1169                         timer = list_first_entry(head, struct timer_list,entry);
1170                         fn = timer->function;
1171                         data = timer->data;
1172                         irqsafe = tbase_get_irqsafe(timer->base);
1173
1174                         timer_stats_account_timer(timer);
1175
1176                         base->running_timer = timer;
1177                         detach_expired_timer(timer, base);
1178
1179                         if (irqsafe) {
1180                                 spin_unlock(&base->lock);
1181                                 call_timer_fn(timer, fn, data);
1182                                 spin_lock(&base->lock);
1183                         } else {
1184                                 spin_unlock_irq(&base->lock);
1185                                 call_timer_fn(timer, fn, data);
1186                                 spin_lock_irq(&base->lock);
1187                         }
1188                 }
1189         }
1190         base->running_timer = NULL;
1191         spin_unlock_irq(&base->lock);
1192 }
1193
1194 #ifdef CONFIG_NO_HZ_COMMON
1195 /*
1196  * Find out when the next timer event is due to happen. This
1197  * is used on S/390 to stop all activity when a CPU is idle.
1198  * This function needs to be called with interrupts disabled.
1199  */
1200 static unsigned long __next_timer_interrupt(struct tvec_base *base)
1201 {
1202         unsigned long timer_jiffies = base->timer_jiffies;
1203         unsigned long expires = timer_jiffies + NEXT_TIMER_MAX_DELTA;
1204         int index, slot, array, found = 0;
1205         struct timer_list *nte;
1206         struct tvec *varray[4];
1207
1208         /* Look for timer events in tv1. */
1209         index = slot = timer_jiffies & TVR_MASK;
1210         do {
1211                 list_for_each_entry(nte, base->tv1.vec + slot, entry) {
1212                         if (tbase_get_deferrable(nte->base))
1213                                 continue;
1214
1215                         found = 1;
1216                         expires = nte->expires;
1217                         /* Look at the cascade bucket(s)? */
1218                         if (!index || slot < index)
1219                                 goto cascade;
1220                         return expires;
1221                 }
1222                 slot = (slot + 1) & TVR_MASK;
1223         } while (slot != index);
1224
1225 cascade:
1226         /* Calculate the next cascade event */
1227         if (index)
1228                 timer_jiffies += TVR_SIZE - index;
1229         timer_jiffies >>= TVR_BITS;
1230
1231         /* Check tv2-tv5. */
1232         varray[0] = &base->tv2;
1233         varray[1] = &base->tv3;
1234         varray[2] = &base->tv4;
1235         varray[3] = &base->tv5;
1236
1237         for (array = 0; array < 4; array++) {
1238                 struct tvec *varp = varray[array];
1239
1240                 index = slot = timer_jiffies & TVN_MASK;
1241                 do {
1242                         list_for_each_entry(nte, varp->vec + slot, entry) {
1243                                 if (tbase_get_deferrable(nte->base))
1244                                         continue;
1245
1246                                 found = 1;
1247                                 if (time_before(nte->expires, expires))
1248                                         expires = nte->expires;
1249                         }
1250                         /*
1251                          * Do we still search for the first timer or are
1252                          * we looking up the cascade buckets ?
1253                          */
1254                         if (found) {
1255                                 /* Look at the cascade bucket(s)? */
1256                                 if (!index || slot < index)
1257                                         break;
1258                                 return expires;
1259                         }
1260                         slot = (slot + 1) & TVN_MASK;
1261                 } while (slot != index);
1262
1263                 if (index)
1264                         timer_jiffies += TVN_SIZE - index;
1265                 timer_jiffies >>= TVN_BITS;
1266         }
1267         return expires;
1268 }
1269
1270 /*
1271  * Check, if the next hrtimer event is before the next timer wheel
1272  * event:
1273  */
1274 static unsigned long cmp_next_hrtimer_event(unsigned long now,
1275                                             unsigned long expires)
1276 {
1277         ktime_t hr_delta = hrtimer_get_next_event();
1278         struct timespec tsdelta;
1279         unsigned long delta;
1280
1281         if (hr_delta.tv64 == KTIME_MAX)
1282                 return expires;
1283
1284         /*
1285          * Expired timer available, let it expire in the next tick
1286          */
1287         if (hr_delta.tv64 <= 0)
1288                 return now + 1;
1289
1290         tsdelta = ktime_to_timespec(hr_delta);
1291         delta = timespec_to_jiffies(&tsdelta);
1292
1293         /*
1294          * Limit the delta to the max value, which is checked in
1295          * tick_nohz_stop_sched_tick():
1296          */
1297         if (delta > NEXT_TIMER_MAX_DELTA)
1298                 delta = NEXT_TIMER_MAX_DELTA;
1299
1300         /*
1301          * Take rounding errors in to account and make sure, that it
1302          * expires in the next tick. Otherwise we go into an endless
1303          * ping pong due to tick_nohz_stop_sched_tick() retriggering
1304          * the timer softirq
1305          */
1306         if (delta < 1)
1307                 delta = 1;
1308         now += delta;
1309         if (time_before(now, expires))
1310                 return now;
1311         return expires;
1312 }
1313
1314 /**
1315  * get_next_timer_interrupt - return the jiffy of the next pending timer
1316  * @now: current time (in jiffies)
1317  */
1318 unsigned long get_next_timer_interrupt(unsigned long now)
1319 {
1320         struct tvec_base *base = __this_cpu_read(tvec_bases);
1321         unsigned long expires = now + NEXT_TIMER_MAX_DELTA;
1322
1323         /*
1324          * Pretend that there is no timer pending if the cpu is offline.
1325          * Possible pending timers will be migrated later to an active cpu.
1326          */
1327         if (cpu_is_offline(smp_processor_id()))
1328                 return expires;
1329
1330         spin_lock(&base->lock);
1331         if (base->active_timers) {
1332                 if (time_before_eq(base->next_timer, base->timer_jiffies))
1333                         base->next_timer = __next_timer_interrupt(base);
1334                 expires = base->next_timer;
1335         }
1336         spin_unlock(&base->lock);
1337
1338         if (time_before_eq(expires, now))
1339                 return now;
1340
1341         return cmp_next_hrtimer_event(now, expires);
1342 }
1343 #endif
1344
1345 /*
1346  * Called from the timer interrupt handler to charge one tick to the current
1347  * process.  user_tick is 1 if the tick is user time, 0 for system.
1348  */
1349 void update_process_times(int user_tick)
1350 {
1351         struct task_struct *p = current;
1352         int cpu = smp_processor_id();
1353
1354         /* Note: this timer irq context must be accounted for as well. */
1355         account_process_tick(p, user_tick);
1356         run_local_timers();
1357         rcu_check_callbacks(cpu, user_tick);
1358 #ifdef CONFIG_IRQ_WORK
1359         if (in_irq())
1360                 irq_work_run();
1361 #endif
1362         scheduler_tick();
1363         run_posix_cpu_timers(p);
1364 }
1365
1366 /*
1367  * This function runs timers and the timer-tq in bottom half context.
1368  */
1369 static void run_timer_softirq(struct softirq_action *h)
1370 {
1371         struct tvec_base *base = __this_cpu_read(tvec_bases);
1372
1373         hrtimer_run_pending();
1374
1375         if (time_after_eq(jiffies, base->timer_jiffies))
1376                 __run_timers(base);
1377 }
1378
1379 /*
1380  * Called by the local, per-CPU timer interrupt on SMP.
1381  */
1382 void run_local_timers(void)
1383 {
1384         hrtimer_run_queues();
1385         raise_softirq(TIMER_SOFTIRQ);
1386 }
1387
1388 #ifdef __ARCH_WANT_SYS_ALARM
1389
1390 /*
1391  * For backwards compatibility?  This can be done in libc so Alpha
1392  * and all newer ports shouldn't need it.
1393  */
1394 SYSCALL_DEFINE1(alarm, unsigned int, seconds)
1395 {
1396         return alarm_setitimer(seconds);
1397 }
1398
1399 #endif
1400
1401 static void process_timeout(unsigned long __data)
1402 {
1403         wake_up_process((struct task_struct *)__data);
1404 }
1405
1406 /**
1407  * schedule_timeout - sleep until timeout
1408  * @timeout: timeout value in jiffies
1409  *
1410  * Make the current task sleep until @timeout jiffies have
1411  * elapsed. The routine will return immediately unless
1412  * the current task state has been set (see set_current_state()).
1413  *
1414  * You can set the task state as follows -
1415  *
1416  * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
1417  * pass before the routine returns. The routine will return 0
1418  *
1419  * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
1420  * delivered to the current task. In this case the remaining time
1421  * in jiffies will be returned, or 0 if the timer expired in time
1422  *
1423  * The current task state is guaranteed to be TASK_RUNNING when this
1424  * routine returns.
1425  *
1426  * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
1427  * the CPU away without a bound on the timeout. In this case the return
1428  * value will be %MAX_SCHEDULE_TIMEOUT.
1429  *
1430  * In all cases the return value is guaranteed to be non-negative.
1431  */
1432 signed long __sched schedule_timeout(signed long timeout)
1433 {
1434         struct timer_list timer;
1435         unsigned long expire;
1436
1437         switch (timeout)
1438         {
1439         case MAX_SCHEDULE_TIMEOUT:
1440                 /*
1441                  * These two special cases are useful to be comfortable
1442                  * in the caller. Nothing more. We could take
1443                  * MAX_SCHEDULE_TIMEOUT from one of the negative value
1444                  * but I' d like to return a valid offset (>=0) to allow
1445                  * the caller to do everything it want with the retval.
1446                  */
1447                 schedule();
1448                 goto out;
1449         default:
1450                 /*
1451                  * Another bit of PARANOID. Note that the retval will be
1452                  * 0 since no piece of kernel is supposed to do a check
1453                  * for a negative retval of schedule_timeout() (since it
1454                  * should never happens anyway). You just have the printk()
1455                  * that will tell you if something is gone wrong and where.
1456                  */
1457                 if (timeout < 0) {
1458                         printk(KERN_ERR "schedule_timeout: wrong timeout "
1459                                 "value %lx\n", timeout);
1460                         dump_stack();
1461                         current->state = TASK_RUNNING;
1462                         goto out;
1463                 }
1464         }
1465
1466         expire = timeout + jiffies;
1467
1468         setup_timer_on_stack(&timer, process_timeout, (unsigned long)current);
1469         __mod_timer(&timer, expire, false, TIMER_NOT_PINNED);
1470         schedule();
1471         del_singleshot_timer_sync(&timer);
1472
1473         /* Remove the timer from the object tracker */
1474         destroy_timer_on_stack(&timer);
1475
1476         timeout = expire - jiffies;
1477
1478  out:
1479         return timeout < 0 ? 0 : timeout;
1480 }
1481 EXPORT_SYMBOL(schedule_timeout);
1482
1483 /*
1484  * We can use __set_current_state() here because schedule_timeout() calls
1485  * schedule() unconditionally.
1486  */
1487 signed long __sched schedule_timeout_interruptible(signed long timeout)
1488 {
1489         __set_current_state(TASK_INTERRUPTIBLE);
1490         return schedule_timeout(timeout);
1491 }
1492 EXPORT_SYMBOL(schedule_timeout_interruptible);
1493
1494 signed long __sched schedule_timeout_killable(signed long timeout)
1495 {
1496         __set_current_state(TASK_KILLABLE);
1497         return schedule_timeout(timeout);
1498 }
1499 EXPORT_SYMBOL(schedule_timeout_killable);
1500
1501 signed long __sched schedule_timeout_uninterruptible(signed long timeout)
1502 {
1503         __set_current_state(TASK_UNINTERRUPTIBLE);
1504         return schedule_timeout(timeout);
1505 }
1506 EXPORT_SYMBOL(schedule_timeout_uninterruptible);
1507
1508 static int init_timers_cpu(int cpu)
1509 {
1510         int j;
1511         struct tvec_base *base;
1512         static char tvec_base_done[NR_CPUS];
1513
1514         if (!tvec_base_done[cpu]) {
1515                 static char boot_done;
1516
1517                 if (boot_done) {
1518                         /*
1519                          * The APs use this path later in boot
1520                          */
1521                         base = kmalloc_node(sizeof(*base),
1522                                                 GFP_KERNEL | __GFP_ZERO,
1523                                                 cpu_to_node(cpu));
1524                         if (!base)
1525                                 return -ENOMEM;
1526
1527                         /* Make sure that tvec_base is 2 byte aligned */
1528                         if (tbase_get_deferrable(base)) {
1529                                 WARN_ON(1);
1530                                 kfree(base);
1531                                 return -ENOMEM;
1532                         }
1533                         per_cpu(tvec_bases, cpu) = base;
1534                 } else {
1535                         /*
1536                          * This is for the boot CPU - we use compile-time
1537                          * static initialisation because per-cpu memory isn't
1538                          * ready yet and because the memory allocators are not
1539                          * initialised either.
1540                          */
1541                         boot_done = 1;
1542                         base = &boot_tvec_bases;
1543                 }
1544                 spin_lock_init(&base->lock);
1545                 tvec_base_done[cpu] = 1;
1546         } else {
1547                 base = per_cpu(tvec_bases, cpu);
1548         }
1549
1550
1551         for (j = 0; j < TVN_SIZE; j++) {
1552                 INIT_LIST_HEAD(base->tv5.vec + j);
1553                 INIT_LIST_HEAD(base->tv4.vec + j);
1554                 INIT_LIST_HEAD(base->tv3.vec + j);
1555                 INIT_LIST_HEAD(base->tv2.vec + j);
1556         }
1557         for (j = 0; j < TVR_SIZE; j++)
1558                 INIT_LIST_HEAD(base->tv1.vec + j);
1559
1560         base->timer_jiffies = jiffies;
1561         base->next_timer = base->timer_jiffies;
1562         base->active_timers = 0;
1563         return 0;
1564 }
1565
1566 #ifdef CONFIG_HOTPLUG_CPU
1567 static void migrate_timer_list(struct tvec_base *new_base, struct list_head *head)
1568 {
1569         struct timer_list *timer;
1570
1571         while (!list_empty(head)) {
1572                 timer = list_first_entry(head, struct timer_list, entry);
1573                 /* We ignore the accounting on the dying cpu */
1574                 detach_timer(timer, false);
1575                 timer_set_base(timer, new_base);
1576                 internal_add_timer(new_base, timer);
1577         }
1578 }
1579
1580 static void migrate_timers(int cpu)
1581 {
1582         struct tvec_base *old_base;
1583         struct tvec_base *new_base;
1584         int i;
1585
1586         BUG_ON(cpu_online(cpu));
1587         old_base = per_cpu(tvec_bases, cpu);
1588         new_base = get_cpu_var(tvec_bases);
1589         /*
1590          * The caller is globally serialized and nobody else
1591          * takes two locks at once, deadlock is not possible.
1592          */
1593         spin_lock_irq(&new_base->lock);
1594         spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING);
1595
1596         BUG_ON(old_base->running_timer);
1597
1598         for (i = 0; i < TVR_SIZE; i++)
1599                 migrate_timer_list(new_base, old_base->tv1.vec + i);
1600         for (i = 0; i < TVN_SIZE; i++) {
1601                 migrate_timer_list(new_base, old_base->tv2.vec + i);
1602                 migrate_timer_list(new_base, old_base->tv3.vec + i);
1603                 migrate_timer_list(new_base, old_base->tv4.vec + i);
1604                 migrate_timer_list(new_base, old_base->tv5.vec + i);
1605         }
1606
1607         spin_unlock(&old_base->lock);
1608         spin_unlock_irq(&new_base->lock);
1609         put_cpu_var(tvec_bases);
1610 }
1611 #endif /* CONFIG_HOTPLUG_CPU */
1612
1613 static int timer_cpu_notify(struct notifier_block *self,
1614                                 unsigned long action, void *hcpu)
1615 {
1616         long cpu = (long)hcpu;
1617         int err;
1618
1619         switch(action) {
1620         case CPU_UP_PREPARE:
1621         case CPU_UP_PREPARE_FROZEN:
1622                 err = init_timers_cpu(cpu);
1623                 if (err < 0)
1624                         return notifier_from_errno(err);
1625                 break;
1626 #ifdef CONFIG_HOTPLUG_CPU
1627         case CPU_DEAD:
1628         case CPU_DEAD_FROZEN:
1629                 migrate_timers(cpu);
1630                 break;
1631 #endif
1632         default:
1633                 break;
1634         }
1635         return NOTIFY_OK;
1636 }
1637
1638 static struct notifier_block timers_nb = {
1639         .notifier_call  = timer_cpu_notify,
1640 };
1641
1642
1643 void __init init_timers(void)
1644 {
1645         int err;
1646
1647         /* ensure there are enough low bits for flags in timer->base pointer */
1648         BUILD_BUG_ON(__alignof__(struct tvec_base) & TIMER_FLAG_MASK);
1649
1650         err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
1651                                (void *)(long)smp_processor_id());
1652         init_timer_stats();
1653
1654         BUG_ON(err != NOTIFY_OK);
1655         register_cpu_notifier(&timers_nb);
1656         open_softirq(TIMER_SOFTIRQ, run_timer_softirq);
1657 }
1658
1659 /**
1660  * msleep - sleep safely even with waitqueue interruptions
1661  * @msecs: Time in milliseconds to sleep for
1662  */
1663 void msleep(unsigned int msecs)
1664 {
1665         unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1666
1667         while (timeout)
1668                 timeout = schedule_timeout_uninterruptible(timeout);
1669 }
1670
1671 EXPORT_SYMBOL(msleep);
1672
1673 /**
1674  * msleep_interruptible - sleep waiting for signals
1675  * @msecs: Time in milliseconds to sleep for
1676  */
1677 unsigned long msleep_interruptible(unsigned int msecs)
1678 {
1679         unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1680
1681         while (timeout && !signal_pending(current))
1682                 timeout = schedule_timeout_interruptible(timeout);
1683         return jiffies_to_msecs(timeout);
1684 }
1685
1686 EXPORT_SYMBOL(msleep_interruptible);
1687
1688 static int __sched do_usleep_range(unsigned long min, unsigned long max)
1689 {
1690         ktime_t kmin;
1691         unsigned long delta;
1692
1693         kmin = ktime_set(0, min * NSEC_PER_USEC);
1694         delta = (max - min) * NSEC_PER_USEC;
1695         return schedule_hrtimeout_range(&kmin, delta, HRTIMER_MODE_REL);
1696 }
1697
1698 /**
1699  * usleep_range - Drop in replacement for udelay where wakeup is flexible
1700  * @min: Minimum time in usecs to sleep
1701  * @max: Maximum time in usecs to sleep
1702  */
1703 void usleep_range(unsigned long min, unsigned long max)
1704 {
1705         __set_current_state(TASK_UNINTERRUPTIBLE);
1706         do_usleep_range(min, max);
1707 }
1708 EXPORT_SYMBOL(usleep_range);