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