xref: /linux/kernel/time/timer.c (revision 987cbafe628ae67fe6cad0ce1dcc41743147ef3e)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  *  Kernel internal timers
4  *
5  *  Copyright (C) 1991, 1992  Linus Torvalds
6  *
7  *  1997-01-28  Modified by Finn Arne Gangstad to make timers scale better.
8  *
9  *  1997-09-10  Updated NTP code according to technical memorandum Jan '96
10  *              "A Kernel Model for Precision Timekeeping" by Dave Mills
11  *  1998-12-24  Fixed a xtime SMP race (we need the xtime_lock rw spinlock to
12  *              serialize accesses to xtime/lost_ticks).
13  *                              Copyright (C) 1998  Andrea Arcangeli
14  *  1999-03-10  Improved NTP compatibility by Ulrich Windl
15  *  2002-05-31	Move sys_sysinfo here and make its locking sane, Robert Love
16  *  2000-10-05  Implemented scalable SMP per-CPU timer handling.
17  *                              Copyright (C) 2000, 2001, 2002  Ingo Molnar
18  *              Designed by David S. Miller, Alexey Kuznetsov and Ingo Molnar
19  */
20 
21 #include <linux/kernel_stat.h>
22 #include <linux/export.h>
23 #include <linux/interrupt.h>
24 #include <linux/percpu.h>
25 #include <linux/init.h>
26 #include <linux/mm.h>
27 #include <linux/swap.h>
28 #include <linux/pid_namespace.h>
29 #include <linux/notifier.h>
30 #include <linux/thread_info.h>
31 #include <linux/time.h>
32 #include <linux/jiffies.h>
33 #include <linux/posix-timers.h>
34 #include <linux/cpu.h>
35 #include <linux/syscalls.h>
36 #include <linux/delay.h>
37 #include <linux/tick.h>
38 #include <linux/kallsyms.h>
39 #include <linux/irq_work.h>
40 #include <linux/sched/signal.h>
41 #include <linux/sched/sysctl.h>
42 #include <linux/sched/nohz.h>
43 #include <linux/sched/debug.h>
44 #include <linux/slab.h>
45 #include <linux/compat.h>
46 #include <linux/random.h>
47 #include <linux/sysctl.h>
48 
49 #include <linux/uaccess.h>
50 #include <asm/unistd.h>
51 #include <asm/div64.h>
52 #include <asm/timex.h>
53 #include <asm/io.h>
54 
55 #include "tick-internal.h"
56 #include "timer_migration.h"
57 
58 #define CREATE_TRACE_POINTS
59 #include <trace/events/timer.h>
60 
61 __visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
62 
63 EXPORT_SYMBOL(jiffies_64);
64 
65 /*
66  * The timer wheel has LVL_DEPTH array levels. Each level provides an array of
67  * LVL_SIZE buckets. Each level is driven by its own clock and therefore each
68  * level has a different granularity.
69  *
70  * The level granularity is:		LVL_CLK_DIV ^ level
71  * The level clock frequency is:	HZ / (LVL_CLK_DIV ^ level)
72  *
73  * The array level of a newly armed timer depends on the relative expiry
74  * time. The farther the expiry time is away the higher the array level and
75  * therefore the granularity becomes.
76  *
77  * Contrary to the original timer wheel implementation, which aims for 'exact'
78  * expiry of the timers, this implementation removes the need for recascading
79  * the timers into the lower array levels. The previous 'classic' timer wheel
80  * implementation of the kernel already violated the 'exact' expiry by adding
81  * slack to the expiry time to provide batched expiration. The granularity
82  * levels provide implicit batching.
83  *
84  * This is an optimization of the original timer wheel implementation for the
85  * majority of the timer wheel use cases: timeouts. The vast majority of
86  * timeout timers (networking, disk I/O ...) are canceled before expiry. If
87  * the timeout expires it indicates that normal operation is disturbed, so it
88  * does not matter much whether the timeout comes with a slight delay.
89  *
90  * The only exception to this are networking timers with a small expiry
91  * time. They rely on the granularity. Those fit into the first wheel level,
92  * which has HZ granularity.
93  *
94  * We don't have cascading anymore. timers with a expiry time above the
95  * capacity of the last wheel level are force expired at the maximum timeout
96  * value of the last wheel level. From data sampling we know that the maximum
97  * value observed is 5 days (network connection tracking), so this should not
98  * be an issue.
99  *
100  * The currently chosen array constants values are a good compromise between
101  * array size and granularity.
102  *
103  * This results in the following granularity and range levels:
104  *
105  * HZ 1000 steps
106  * Level Offset  Granularity            Range
107  *  0      0         1 ms                0 ms -         63 ms
108  *  1     64         8 ms               64 ms -        511 ms
109  *  2    128        64 ms              512 ms -       4095 ms (512ms - ~4s)
110  *  3    192       512 ms             4096 ms -      32767 ms (~4s - ~32s)
111  *  4    256      4096 ms (~4s)      32768 ms -     262143 ms (~32s - ~4m)
112  *  5    320     32768 ms (~32s)    262144 ms -    2097151 ms (~4m - ~34m)
113  *  6    384    262144 ms (~4m)    2097152 ms -   16777215 ms (~34m - ~4h)
114  *  7    448   2097152 ms (~34m)  16777216 ms -  134217727 ms (~4h - ~1d)
115  *  8    512  16777216 ms (~4h)  134217728 ms - 1073741822 ms (~1d - ~12d)
116  *
117  * HZ  300
118  * Level Offset  Granularity            Range
119  *  0	   0         3 ms                0 ms -        210 ms
120  *  1	  64        26 ms              213 ms -       1703 ms (213ms - ~1s)
121  *  2	 128       213 ms             1706 ms -      13650 ms (~1s - ~13s)
122  *  3	 192      1706 ms (~1s)      13653 ms -     109223 ms (~13s - ~1m)
123  *  4	 256     13653 ms (~13s)    109226 ms -     873810 ms (~1m - ~14m)
124  *  5	 320    109226 ms (~1m)     873813 ms -    6990503 ms (~14m - ~1h)
125  *  6	 384    873813 ms (~14m)   6990506 ms -   55924050 ms (~1h - ~15h)
126  *  7	 448   6990506 ms (~1h)   55924053 ms -  447392423 ms (~15h - ~5d)
127  *  8    512  55924053 ms (~15h) 447392426 ms - 3579139406 ms (~5d - ~41d)
128  *
129  * HZ  250
130  * Level Offset  Granularity            Range
131  *  0	   0         4 ms                0 ms -        255 ms
132  *  1	  64        32 ms              256 ms -       2047 ms (256ms - ~2s)
133  *  2	 128       256 ms             2048 ms -      16383 ms (~2s - ~16s)
134  *  3	 192      2048 ms (~2s)      16384 ms -     131071 ms (~16s - ~2m)
135  *  4	 256     16384 ms (~16s)    131072 ms -    1048575 ms (~2m - ~17m)
136  *  5	 320    131072 ms (~2m)    1048576 ms -    8388607 ms (~17m - ~2h)
137  *  6	 384   1048576 ms (~17m)   8388608 ms -   67108863 ms (~2h - ~18h)
138  *  7	 448   8388608 ms (~2h)   67108864 ms -  536870911 ms (~18h - ~6d)
139  *  8    512  67108864 ms (~18h) 536870912 ms - 4294967288 ms (~6d - ~49d)
140  *
141  * HZ  100
142  * Level Offset  Granularity            Range
143  *  0	   0         10 ms               0 ms -        630 ms
144  *  1	  64         80 ms             640 ms -       5110 ms (640ms - ~5s)
145  *  2	 128        640 ms            5120 ms -      40950 ms (~5s - ~40s)
146  *  3	 192       5120 ms (~5s)     40960 ms -     327670 ms (~40s - ~5m)
147  *  4	 256      40960 ms (~40s)   327680 ms -    2621430 ms (~5m - ~43m)
148  *  5	 320     327680 ms (~5m)   2621440 ms -   20971510 ms (~43m - ~5h)
149  *  6	 384    2621440 ms (~43m) 20971520 ms -  167772150 ms (~5h - ~1d)
150  *  7	 448   20971520 ms (~5h) 167772160 ms - 1342177270 ms (~1d - ~15d)
151  */
152 
153 /* Clock divisor for the next level */
154 #define LVL_CLK_SHIFT	3
155 #define LVL_CLK_DIV	(1UL << LVL_CLK_SHIFT)
156 #define LVL_CLK_MASK	(LVL_CLK_DIV - 1)
157 #define LVL_SHIFT(n)	((n) * LVL_CLK_SHIFT)
158 #define LVL_GRAN(n)	(1UL << LVL_SHIFT(n))
159 
160 /*
161  * The time start value for each level to select the bucket at enqueue
162  * time. We start from the last possible delta of the previous level
163  * so that we can later add an extra LVL_GRAN(n) to n (see calc_index()).
164  */
165 #define LVL_START(n)	((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT))
166 
167 /* Size of each clock level */
168 #define LVL_BITS	6
169 #define LVL_SIZE	(1UL << LVL_BITS)
170 #define LVL_MASK	(LVL_SIZE - 1)
171 #define LVL_OFFS(n)	((n) * LVL_SIZE)
172 
173 /* Level depth */
174 #if HZ > 100
175 # define LVL_DEPTH	9
176 # else
177 # define LVL_DEPTH	8
178 #endif
179 
180 /* The cutoff (max. capacity of the wheel) */
181 #define WHEEL_TIMEOUT_CUTOFF	(LVL_START(LVL_DEPTH))
182 #define WHEEL_TIMEOUT_MAX	(WHEEL_TIMEOUT_CUTOFF - LVL_GRAN(LVL_DEPTH - 1))
183 
184 /*
185  * The resulting wheel size. If NOHZ is configured we allocate two
186  * wheels so we have a separate storage for the deferrable timers.
187  */
188 #define WHEEL_SIZE	(LVL_SIZE * LVL_DEPTH)
189 
190 #ifdef CONFIG_NO_HZ_COMMON
191 /*
192  * If multiple bases need to be locked, use the base ordering for lock
193  * nesting, i.e. lowest number first.
194  */
195 # define NR_BASES	3
196 # define BASE_LOCAL	0
197 # define BASE_GLOBAL	1
198 # define BASE_DEF	2
199 #else
200 # define NR_BASES	1
201 # define BASE_LOCAL	0
202 # define BASE_GLOBAL	0
203 # define BASE_DEF	0
204 #endif
205 
206 /**
207  * struct timer_base - Per CPU timer base (number of base depends on config)
208  * @lock:		Lock protecting the timer_base
209  * @running_timer:	When expiring timers, the lock is dropped. To make
210  *			sure not to race against deleting/modifying a
211  *			currently running timer, the pointer is set to the
212  *			timer, which expires at the moment. If no timer is
213  *			running, the pointer is NULL.
214  * @expiry_lock:	PREEMPT_RT only: Lock is taken in softirq around
215  *			timer expiry callback execution and when trying to
216  *			delete a running timer and it wasn't successful in
217  *			the first glance. It prevents priority inversion
218  *			when callback was preempted on a remote CPU and a
219  *			caller tries to delete the running timer. It also
220  *			prevents a life lock, when the task which tries to
221  *			delete a timer preempted the softirq thread which
222  *			is running the timer callback function.
223  * @timer_waiters:	PREEMPT_RT only: Tells, if there is a waiter
224  *			waiting for the end of the timer callback function
225  *			execution.
226  * @clk:		clock of the timer base; is updated before enqueue
227  *			of a timer; during expiry, it is 1 offset ahead of
228  *			jiffies to avoid endless requeuing to current
229  *			jiffies
230  * @next_expiry:	expiry value of the first timer; it is updated when
231  *			finding the next timer and during enqueue; the
232  *			value is not valid, when next_expiry_recalc is set
233  * @cpu:		Number of CPU the timer base belongs to
234  * @next_expiry_recalc: States, whether a recalculation of next_expiry is
235  *			required. Value is set true, when a timer was
236  *			deleted.
237  * @is_idle:		Is set, when timer_base is idle. It is triggered by NOHZ
238  *			code. This state is only used in standard
239  *			base. Deferrable timers, which are enqueued remotely
240  *			never wake up an idle CPU. So no matter of supporting it
241  *			for this base.
242  * @timers_pending:	Is set, when a timer is pending in the base. It is only
243  *			reliable when next_expiry_recalc is not set.
244  * @pending_map:	bitmap of the timer wheel; each bit reflects a
245  *			bucket of the wheel. When a bit is set, at least a
246  *			single timer is enqueued in the related bucket.
247  * @vectors:		Array of lists; Each array member reflects a bucket
248  *			of the timer wheel. The list contains all timers
249  *			which are enqueued into a specific bucket.
250  */
251 struct timer_base {
252 	raw_spinlock_t		lock;
253 	struct timer_list	*running_timer;
254 #ifdef CONFIG_PREEMPT_RT
255 	spinlock_t		expiry_lock;
256 	atomic_t		timer_waiters;
257 #endif
258 	unsigned long		clk;
259 	unsigned long		next_expiry;
260 	unsigned int		cpu;
261 	bool			next_expiry_recalc;
262 	bool			is_idle;
263 	bool			timers_pending;
264 	DECLARE_BITMAP(pending_map, WHEEL_SIZE);
265 	struct hlist_head	vectors[WHEEL_SIZE];
266 } ____cacheline_aligned;
267 
268 static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
269 
270 #ifdef CONFIG_NO_HZ_COMMON
271 
272 static DEFINE_STATIC_KEY_FALSE(timers_nohz_active);
273 static DEFINE_MUTEX(timer_keys_mutex);
274 
275 static void timer_update_keys(struct work_struct *work);
276 static DECLARE_WORK(timer_update_work, timer_update_keys);
277 
278 #ifdef CONFIG_SMP
279 static unsigned int sysctl_timer_migration = 1;
280 
281 DEFINE_STATIC_KEY_FALSE(timers_migration_enabled);
282 
283 static void timers_update_migration(void)
284 {
285 	if (sysctl_timer_migration && tick_nohz_active)
286 		static_branch_enable(&timers_migration_enabled);
287 	else
288 		static_branch_disable(&timers_migration_enabled);
289 }
290 
291 #ifdef CONFIG_SYSCTL
292 static int timer_migration_handler(const struct ctl_table *table, int write,
293 			    void *buffer, size_t *lenp, loff_t *ppos)
294 {
295 	int ret;
296 
297 	mutex_lock(&timer_keys_mutex);
298 	ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
299 	if (!ret && write)
300 		timers_update_migration();
301 	mutex_unlock(&timer_keys_mutex);
302 	return ret;
303 }
304 
305 static struct ctl_table timer_sysctl[] = {
306 	{
307 		.procname	= "timer_migration",
308 		.data		= &sysctl_timer_migration,
309 		.maxlen		= sizeof(unsigned int),
310 		.mode		= 0644,
311 		.proc_handler	= timer_migration_handler,
312 		.extra1		= SYSCTL_ZERO,
313 		.extra2		= SYSCTL_ONE,
314 	},
315 };
316 
317 static int __init timer_sysctl_init(void)
318 {
319 	register_sysctl("kernel", timer_sysctl);
320 	return 0;
321 }
322 device_initcall(timer_sysctl_init);
323 #endif /* CONFIG_SYSCTL */
324 #else /* CONFIG_SMP */
325 static inline void timers_update_migration(void) { }
326 #endif /* !CONFIG_SMP */
327 
328 static void timer_update_keys(struct work_struct *work)
329 {
330 	mutex_lock(&timer_keys_mutex);
331 	timers_update_migration();
332 	static_branch_enable(&timers_nohz_active);
333 	mutex_unlock(&timer_keys_mutex);
334 }
335 
336 void timers_update_nohz(void)
337 {
338 	schedule_work(&timer_update_work);
339 }
340 
341 static inline bool is_timers_nohz_active(void)
342 {
343 	return static_branch_unlikely(&timers_nohz_active);
344 }
345 #else
346 static inline bool is_timers_nohz_active(void) { return false; }
347 #endif /* NO_HZ_COMMON */
348 
349 static unsigned long round_jiffies_common(unsigned long j, int cpu,
350 		bool force_up)
351 {
352 	int rem;
353 	unsigned long original = j;
354 
355 	/*
356 	 * We don't want all cpus firing their timers at once hitting the
357 	 * same lock or cachelines, so we skew each extra cpu with an extra
358 	 * 3 jiffies. This 3 jiffies came originally from the mm/ code which
359 	 * already did this.
360 	 * The skew is done by adding 3*cpunr, then round, then subtract this
361 	 * extra offset again.
362 	 */
363 	j += cpu * 3;
364 
365 	rem = j % HZ;
366 
367 	/*
368 	 * If the target jiffie is just after a whole second (which can happen
369 	 * due to delays of the timer irq, long irq off times etc etc) then
370 	 * we should round down to the whole second, not up. Use 1/4th second
371 	 * as cutoff for this rounding as an extreme upper bound for this.
372 	 * But never round down if @force_up is set.
373 	 */
374 	if (rem < HZ/4 && !force_up) /* round down */
375 		j = j - rem;
376 	else /* round up */
377 		j = j - rem + HZ;
378 
379 	/* now that we have rounded, subtract the extra skew again */
380 	j -= cpu * 3;
381 
382 	/*
383 	 * Make sure j is still in the future. Otherwise return the
384 	 * unmodified value.
385 	 */
386 	return time_is_after_jiffies(j) ? j : original;
387 }
388 
389 /**
390  * __round_jiffies - function to round jiffies 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  * __round_jiffies() rounds an absolute time in the future (in jiffies)
395  * up or down to (approximately) full seconds. This is useful for timers
396  * for which the exact time they fire does not matter too much, as long as
397  * they fire approximately every X seconds.
398  *
399  * By rounding these timers to whole seconds, all such timers will fire
400  * at the same time, rather than at various times spread out. The goal
401  * of this is to have the CPU wake up less, which saves power.
402  *
403  * The exact rounding is skewed for each processor to avoid all
404  * processors firing at the exact same time, which could lead
405  * to lock contention or spurious cache line bouncing.
406  *
407  * The return value is the rounded version of the @j parameter.
408  */
409 unsigned long __round_jiffies(unsigned long j, int cpu)
410 {
411 	return round_jiffies_common(j, cpu, false);
412 }
413 EXPORT_SYMBOL_GPL(__round_jiffies);
414 
415 /**
416  * __round_jiffies_relative - function to round jiffies to a full second
417  * @j: the time in (relative) jiffies that should be rounded
418  * @cpu: the processor number on which the timeout will happen
419  *
420  * __round_jiffies_relative() rounds a time delta  in the future (in jiffies)
421  * up or down to (approximately) full seconds. This is useful for timers
422  * for which the exact time they fire does not matter too much, as long as
423  * they fire approximately every X seconds.
424  *
425  * By rounding these timers to whole seconds, all such timers will fire
426  * at the same time, rather than at various times spread out. The goal
427  * of this is to have the CPU wake up less, which saves power.
428  *
429  * The exact rounding is skewed for each processor to avoid all
430  * processors firing at the exact same time, which could lead
431  * to lock contention or spurious cache line bouncing.
432  *
433  * The return value is the rounded version of the @j parameter.
434  */
435 unsigned long __round_jiffies_relative(unsigned long j, int cpu)
436 {
437 	unsigned long j0 = jiffies;
438 
439 	/* Use j0 because jiffies might change while we run */
440 	return round_jiffies_common(j + j0, cpu, false) - j0;
441 }
442 EXPORT_SYMBOL_GPL(__round_jiffies_relative);
443 
444 /**
445  * round_jiffies - function to round jiffies to a full second
446  * @j: the time in (absolute) jiffies that should be rounded
447  *
448  * round_jiffies() rounds an absolute time in the future (in jiffies)
449  * up or down to (approximately) full seconds. This is useful for timers
450  * for which the exact time they fire does not matter too much, as long as
451  * they fire approximately every X seconds.
452  *
453  * By rounding these timers to whole seconds, all such timers will fire
454  * at the same time, rather than at various times spread out. The goal
455  * of this is to have the CPU wake up less, which saves power.
456  *
457  * The return value is the rounded version of the @j parameter.
458  */
459 unsigned long round_jiffies(unsigned long j)
460 {
461 	return round_jiffies_common(j, raw_smp_processor_id(), false);
462 }
463 EXPORT_SYMBOL_GPL(round_jiffies);
464 
465 /**
466  * round_jiffies_relative - function to round jiffies to a full second
467  * @j: the time in (relative) jiffies that should be rounded
468  *
469  * round_jiffies_relative() rounds a time delta  in the future (in jiffies)
470  * up or down to (approximately) full seconds. This is useful for timers
471  * for which the exact time they fire does not matter too much, as long as
472  * they fire approximately every X seconds.
473  *
474  * By rounding these timers to whole seconds, all such timers will fire
475  * at the same time, rather than at various times spread out. The goal
476  * of this is to have the CPU wake up less, which saves power.
477  *
478  * The return value is the rounded version of the @j parameter.
479  */
480 unsigned long round_jiffies_relative(unsigned long j)
481 {
482 	return __round_jiffies_relative(j, raw_smp_processor_id());
483 }
484 EXPORT_SYMBOL_GPL(round_jiffies_relative);
485 
486 /**
487  * __round_jiffies_up - function to round jiffies up to a full second
488  * @j: the time in (absolute) jiffies that should be rounded
489  * @cpu: the processor number on which the timeout will happen
490  *
491  * This is the same as __round_jiffies() except that it will never
492  * round down.  This is useful for timeouts for which the exact time
493  * of firing does not matter too much, as long as they don't fire too
494  * early.
495  */
496 unsigned long __round_jiffies_up(unsigned long j, int cpu)
497 {
498 	return round_jiffies_common(j, cpu, true);
499 }
500 EXPORT_SYMBOL_GPL(__round_jiffies_up);
501 
502 /**
503  * __round_jiffies_up_relative - function to round jiffies up to a full second
504  * @j: the time in (relative) jiffies that should be rounded
505  * @cpu: the processor number on which the timeout will happen
506  *
507  * This is the same as __round_jiffies_relative() except that it will never
508  * round down.  This is useful for timeouts for which the exact time
509  * of firing does not matter too much, as long as they don't fire too
510  * early.
511  */
512 unsigned long __round_jiffies_up_relative(unsigned long j, int cpu)
513 {
514 	unsigned long j0 = jiffies;
515 
516 	/* Use j0 because jiffies might change while we run */
517 	return round_jiffies_common(j + j0, cpu, true) - j0;
518 }
519 EXPORT_SYMBOL_GPL(__round_jiffies_up_relative);
520 
521 /**
522  * round_jiffies_up - function to round jiffies up to a full second
523  * @j: the time in (absolute) jiffies that should be rounded
524  *
525  * This is the same as round_jiffies() except that it will never
526  * round down.  This is useful for timeouts for which the exact time
527  * of firing does not matter too much, as long as they don't fire too
528  * early.
529  */
530 unsigned long round_jiffies_up(unsigned long j)
531 {
532 	return round_jiffies_common(j, raw_smp_processor_id(), true);
533 }
534 EXPORT_SYMBOL_GPL(round_jiffies_up);
535 
536 /**
537  * round_jiffies_up_relative - function to round jiffies up to a full second
538  * @j: the time in (relative) jiffies that should be rounded
539  *
540  * This is the same as round_jiffies_relative() except that it will never
541  * round down.  This is useful for timeouts for which the exact time
542  * of firing does not matter too much, as long as they don't fire too
543  * early.
544  */
545 unsigned long round_jiffies_up_relative(unsigned long j)
546 {
547 	return __round_jiffies_up_relative(j, raw_smp_processor_id());
548 }
549 EXPORT_SYMBOL_GPL(round_jiffies_up_relative);
550 
551 
552 static inline unsigned int timer_get_idx(struct timer_list *timer)
553 {
554 	return (timer->flags & TIMER_ARRAYMASK) >> TIMER_ARRAYSHIFT;
555 }
556 
557 static inline void timer_set_idx(struct timer_list *timer, unsigned int idx)
558 {
559 	timer->flags = (timer->flags & ~TIMER_ARRAYMASK) |
560 			idx << TIMER_ARRAYSHIFT;
561 }
562 
563 /*
564  * Helper function to calculate the array index for a given expiry
565  * time.
566  */
567 static inline unsigned calc_index(unsigned long expires, unsigned lvl,
568 				  unsigned long *bucket_expiry)
569 {
570 
571 	/*
572 	 * The timer wheel has to guarantee that a timer does not fire
573 	 * early. Early expiry can happen due to:
574 	 * - Timer is armed at the edge of a tick
575 	 * - Truncation of the expiry time in the outer wheel levels
576 	 *
577 	 * Round up with level granularity to prevent this.
578 	 */
579 	expires = (expires >> LVL_SHIFT(lvl)) + 1;
580 	*bucket_expiry = expires << LVL_SHIFT(lvl);
581 	return LVL_OFFS(lvl) + (expires & LVL_MASK);
582 }
583 
584 static int calc_wheel_index(unsigned long expires, unsigned long clk,
585 			    unsigned long *bucket_expiry)
586 {
587 	unsigned long delta = expires - clk;
588 	unsigned int idx;
589 
590 	if (delta < LVL_START(1)) {
591 		idx = calc_index(expires, 0, bucket_expiry);
592 	} else if (delta < LVL_START(2)) {
593 		idx = calc_index(expires, 1, bucket_expiry);
594 	} else if (delta < LVL_START(3)) {
595 		idx = calc_index(expires, 2, bucket_expiry);
596 	} else if (delta < LVL_START(4)) {
597 		idx = calc_index(expires, 3, bucket_expiry);
598 	} else if (delta < LVL_START(5)) {
599 		idx = calc_index(expires, 4, bucket_expiry);
600 	} else if (delta < LVL_START(6)) {
601 		idx = calc_index(expires, 5, bucket_expiry);
602 	} else if (delta < LVL_START(7)) {
603 		idx = calc_index(expires, 6, bucket_expiry);
604 	} else if (LVL_DEPTH > 8 && delta < LVL_START(8)) {
605 		idx = calc_index(expires, 7, bucket_expiry);
606 	} else if ((long) delta < 0) {
607 		idx = clk & LVL_MASK;
608 		*bucket_expiry = clk;
609 	} else {
610 		/*
611 		 * Force expire obscene large timeouts to expire at the
612 		 * capacity limit of the wheel.
613 		 */
614 		if (delta >= WHEEL_TIMEOUT_CUTOFF)
615 			expires = clk + WHEEL_TIMEOUT_MAX;
616 
617 		idx = calc_index(expires, LVL_DEPTH - 1, bucket_expiry);
618 	}
619 	return idx;
620 }
621 
622 static void
623 trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer)
624 {
625 	/*
626 	 * Deferrable timers do not prevent the CPU from entering dynticks and
627 	 * are not taken into account on the idle/nohz_full path. An IPI when a
628 	 * new deferrable timer is enqueued will wake up the remote CPU but
629 	 * nothing will be done with the deferrable timer base. Therefore skip
630 	 * the remote IPI for deferrable timers completely.
631 	 */
632 	if (!is_timers_nohz_active() || timer->flags & TIMER_DEFERRABLE)
633 		return;
634 
635 	/*
636 	 * We might have to IPI the remote CPU if the base is idle and the
637 	 * timer is pinned. If it is a non pinned timer, it is only queued
638 	 * on the remote CPU, when timer was running during queueing. Then
639 	 * everything is handled by remote CPU anyway. If the other CPU is
640 	 * on the way to idle then it can't set base->is_idle as we hold
641 	 * the base lock:
642 	 */
643 	if (base->is_idle) {
644 		WARN_ON_ONCE(!(timer->flags & TIMER_PINNED ||
645 			       tick_nohz_full_cpu(base->cpu)));
646 		wake_up_nohz_cpu(base->cpu);
647 	}
648 }
649 
650 /*
651  * Enqueue the timer into the hash bucket, mark it pending in
652  * the bitmap, store the index in the timer flags then wake up
653  * the target CPU if needed.
654  */
655 static void enqueue_timer(struct timer_base *base, struct timer_list *timer,
656 			  unsigned int idx, unsigned long bucket_expiry)
657 {
658 
659 	hlist_add_head(&timer->entry, base->vectors + idx);
660 	__set_bit(idx, base->pending_map);
661 	timer_set_idx(timer, idx);
662 
663 	trace_timer_start(timer, bucket_expiry);
664 
665 	/*
666 	 * Check whether this is the new first expiring timer. The
667 	 * effective expiry time of the timer is required here
668 	 * (bucket_expiry) instead of timer->expires.
669 	 */
670 	if (time_before(bucket_expiry, base->next_expiry)) {
671 		/*
672 		 * Set the next expiry time and kick the CPU so it
673 		 * can reevaluate the wheel:
674 		 */
675 		base->next_expiry = bucket_expiry;
676 		base->timers_pending = true;
677 		base->next_expiry_recalc = false;
678 		trigger_dyntick_cpu(base, timer);
679 	}
680 }
681 
682 static void internal_add_timer(struct timer_base *base, struct timer_list *timer)
683 {
684 	unsigned long bucket_expiry;
685 	unsigned int idx;
686 
687 	idx = calc_wheel_index(timer->expires, base->clk, &bucket_expiry);
688 	enqueue_timer(base, timer, idx, bucket_expiry);
689 }
690 
691 #ifdef CONFIG_DEBUG_OBJECTS_TIMERS
692 
693 static const struct debug_obj_descr timer_debug_descr;
694 
695 struct timer_hint {
696 	void	(*function)(struct timer_list *t);
697 	long	offset;
698 };
699 
700 #define TIMER_HINT(fn, container, timr, hintfn)			\
701 	{							\
702 		.function = fn,					\
703 		.offset	  = offsetof(container, hintfn) -	\
704 			    offsetof(container, timr)		\
705 	}
706 
707 static const struct timer_hint timer_hints[] = {
708 	TIMER_HINT(delayed_work_timer_fn,
709 		   struct delayed_work, timer, work.func),
710 	TIMER_HINT(kthread_delayed_work_timer_fn,
711 		   struct kthread_delayed_work, timer, work.func),
712 };
713 
714 static void *timer_debug_hint(void *addr)
715 {
716 	struct timer_list *timer = addr;
717 	int i;
718 
719 	for (i = 0; i < ARRAY_SIZE(timer_hints); i++) {
720 		if (timer_hints[i].function == timer->function) {
721 			void (**fn)(void) = addr + timer_hints[i].offset;
722 
723 			return *fn;
724 		}
725 	}
726 
727 	return timer->function;
728 }
729 
730 static bool timer_is_static_object(void *addr)
731 {
732 	struct timer_list *timer = addr;
733 
734 	return (timer->entry.pprev == NULL &&
735 		timer->entry.next == TIMER_ENTRY_STATIC);
736 }
737 
738 /*
739  * timer_fixup_init is called when:
740  * - an active object is initialized
741  */
742 static bool timer_fixup_init(void *addr, enum debug_obj_state state)
743 {
744 	struct timer_list *timer = addr;
745 
746 	switch (state) {
747 	case ODEBUG_STATE_ACTIVE:
748 		del_timer_sync(timer);
749 		debug_object_init(timer, &timer_debug_descr);
750 		return true;
751 	default:
752 		return false;
753 	}
754 }
755 
756 /* Stub timer callback for improperly used timers. */
757 static void stub_timer(struct timer_list *unused)
758 {
759 	WARN_ON(1);
760 }
761 
762 /*
763  * timer_fixup_activate is called when:
764  * - an active object is activated
765  * - an unknown non-static object is activated
766  */
767 static bool timer_fixup_activate(void *addr, enum debug_obj_state state)
768 {
769 	struct timer_list *timer = addr;
770 
771 	switch (state) {
772 	case ODEBUG_STATE_NOTAVAILABLE:
773 		timer_setup(timer, stub_timer, 0);
774 		return true;
775 
776 	case ODEBUG_STATE_ACTIVE:
777 		WARN_ON(1);
778 		fallthrough;
779 	default:
780 		return false;
781 	}
782 }
783 
784 /*
785  * timer_fixup_free is called when:
786  * - an active object is freed
787  */
788 static bool timer_fixup_free(void *addr, enum debug_obj_state state)
789 {
790 	struct timer_list *timer = addr;
791 
792 	switch (state) {
793 	case ODEBUG_STATE_ACTIVE:
794 		del_timer_sync(timer);
795 		debug_object_free(timer, &timer_debug_descr);
796 		return true;
797 	default:
798 		return false;
799 	}
800 }
801 
802 /*
803  * timer_fixup_assert_init is called when:
804  * - an untracked/uninit-ed object is found
805  */
806 static bool timer_fixup_assert_init(void *addr, enum debug_obj_state state)
807 {
808 	struct timer_list *timer = addr;
809 
810 	switch (state) {
811 	case ODEBUG_STATE_NOTAVAILABLE:
812 		timer_setup(timer, stub_timer, 0);
813 		return true;
814 	default:
815 		return false;
816 	}
817 }
818 
819 static const struct debug_obj_descr timer_debug_descr = {
820 	.name			= "timer_list",
821 	.debug_hint		= timer_debug_hint,
822 	.is_static_object	= timer_is_static_object,
823 	.fixup_init		= timer_fixup_init,
824 	.fixup_activate		= timer_fixup_activate,
825 	.fixup_free		= timer_fixup_free,
826 	.fixup_assert_init	= timer_fixup_assert_init,
827 };
828 
829 static inline void debug_timer_init(struct timer_list *timer)
830 {
831 	debug_object_init(timer, &timer_debug_descr);
832 }
833 
834 static inline void debug_timer_activate(struct timer_list *timer)
835 {
836 	debug_object_activate(timer, &timer_debug_descr);
837 }
838 
839 static inline void debug_timer_deactivate(struct timer_list *timer)
840 {
841 	debug_object_deactivate(timer, &timer_debug_descr);
842 }
843 
844 static inline void debug_timer_assert_init(struct timer_list *timer)
845 {
846 	debug_object_assert_init(timer, &timer_debug_descr);
847 }
848 
849 static void do_init_timer(struct timer_list *timer,
850 			  void (*func)(struct timer_list *),
851 			  unsigned int flags,
852 			  const char *name, struct lock_class_key *key);
853 
854 void init_timer_on_stack_key(struct timer_list *timer,
855 			     void (*func)(struct timer_list *),
856 			     unsigned int flags,
857 			     const char *name, struct lock_class_key *key)
858 {
859 	debug_object_init_on_stack(timer, &timer_debug_descr);
860 	do_init_timer(timer, func, flags, name, key);
861 }
862 EXPORT_SYMBOL_GPL(init_timer_on_stack_key);
863 
864 void destroy_timer_on_stack(struct timer_list *timer)
865 {
866 	debug_object_free(timer, &timer_debug_descr);
867 }
868 EXPORT_SYMBOL_GPL(destroy_timer_on_stack);
869 
870 #else
871 static inline void debug_timer_init(struct timer_list *timer) { }
872 static inline void debug_timer_activate(struct timer_list *timer) { }
873 static inline void debug_timer_deactivate(struct timer_list *timer) { }
874 static inline void debug_timer_assert_init(struct timer_list *timer) { }
875 #endif
876 
877 static inline void debug_init(struct timer_list *timer)
878 {
879 	debug_timer_init(timer);
880 	trace_timer_init(timer);
881 }
882 
883 static inline void debug_deactivate(struct timer_list *timer)
884 {
885 	debug_timer_deactivate(timer);
886 	trace_timer_cancel(timer);
887 }
888 
889 static inline void debug_assert_init(struct timer_list *timer)
890 {
891 	debug_timer_assert_init(timer);
892 }
893 
894 static void do_init_timer(struct timer_list *timer,
895 			  void (*func)(struct timer_list *),
896 			  unsigned int flags,
897 			  const char *name, struct lock_class_key *key)
898 {
899 	timer->entry.pprev = NULL;
900 	timer->function = func;
901 	if (WARN_ON_ONCE(flags & ~TIMER_INIT_FLAGS))
902 		flags &= TIMER_INIT_FLAGS;
903 	timer->flags = flags | raw_smp_processor_id();
904 	lockdep_init_map(&timer->lockdep_map, name, key, 0);
905 }
906 
907 /**
908  * init_timer_key - initialize a timer
909  * @timer: the timer to be initialized
910  * @func: timer callback function
911  * @flags: timer flags
912  * @name: name of the timer
913  * @key: lockdep class key of the fake lock used for tracking timer
914  *       sync lock dependencies
915  *
916  * init_timer_key() must be done to a timer prior to calling *any* of the
917  * other timer functions.
918  */
919 void init_timer_key(struct timer_list *timer,
920 		    void (*func)(struct timer_list *), unsigned int flags,
921 		    const char *name, struct lock_class_key *key)
922 {
923 	debug_init(timer);
924 	do_init_timer(timer, func, flags, name, key);
925 }
926 EXPORT_SYMBOL(init_timer_key);
927 
928 static inline void detach_timer(struct timer_list *timer, bool clear_pending)
929 {
930 	struct hlist_node *entry = &timer->entry;
931 
932 	debug_deactivate(timer);
933 
934 	__hlist_del(entry);
935 	if (clear_pending)
936 		entry->pprev = NULL;
937 	entry->next = LIST_POISON2;
938 }
939 
940 static int detach_if_pending(struct timer_list *timer, struct timer_base *base,
941 			     bool clear_pending)
942 {
943 	unsigned idx = timer_get_idx(timer);
944 
945 	if (!timer_pending(timer))
946 		return 0;
947 
948 	if (hlist_is_singular_node(&timer->entry, base->vectors + idx)) {
949 		__clear_bit(idx, base->pending_map);
950 		base->next_expiry_recalc = true;
951 	}
952 
953 	detach_timer(timer, clear_pending);
954 	return 1;
955 }
956 
957 static inline struct timer_base *get_timer_cpu_base(u32 tflags, u32 cpu)
958 {
959 	int index = tflags & TIMER_PINNED ? BASE_LOCAL : BASE_GLOBAL;
960 	struct timer_base *base;
961 
962 	base = per_cpu_ptr(&timer_bases[index], cpu);
963 
964 	/*
965 	 * If the timer is deferrable and NO_HZ_COMMON is set then we need
966 	 * to use the deferrable base.
967 	 */
968 	if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
969 		base = per_cpu_ptr(&timer_bases[BASE_DEF], cpu);
970 	return base;
971 }
972 
973 static inline struct timer_base *get_timer_this_cpu_base(u32 tflags)
974 {
975 	int index = tflags & TIMER_PINNED ? BASE_LOCAL : BASE_GLOBAL;
976 	struct timer_base *base;
977 
978 	base = this_cpu_ptr(&timer_bases[index]);
979 
980 	/*
981 	 * If the timer is deferrable and NO_HZ_COMMON is set then we need
982 	 * to use the deferrable base.
983 	 */
984 	if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && (tflags & TIMER_DEFERRABLE))
985 		base = this_cpu_ptr(&timer_bases[BASE_DEF]);
986 	return base;
987 }
988 
989 static inline struct timer_base *get_timer_base(u32 tflags)
990 {
991 	return get_timer_cpu_base(tflags, tflags & TIMER_CPUMASK);
992 }
993 
994 static inline void __forward_timer_base(struct timer_base *base,
995 					unsigned long basej)
996 {
997 	/*
998 	 * Check whether we can forward the base. We can only do that when
999 	 * @basej is past base->clk otherwise we might rewind base->clk.
1000 	 */
1001 	if (time_before_eq(basej, base->clk))
1002 		return;
1003 
1004 	/*
1005 	 * If the next expiry value is > jiffies, then we fast forward to
1006 	 * jiffies otherwise we forward to the next expiry value.
1007 	 */
1008 	if (time_after(base->next_expiry, basej)) {
1009 		base->clk = basej;
1010 	} else {
1011 		if (WARN_ON_ONCE(time_before(base->next_expiry, base->clk)))
1012 			return;
1013 		base->clk = base->next_expiry;
1014 	}
1015 
1016 }
1017 
1018 static inline void forward_timer_base(struct timer_base *base)
1019 {
1020 	__forward_timer_base(base, READ_ONCE(jiffies));
1021 }
1022 
1023 /*
1024  * We are using hashed locking: Holding per_cpu(timer_bases[x]).lock means
1025  * that all timers which are tied to this base are locked, and the base itself
1026  * is locked too.
1027  *
1028  * So __run_timers/migrate_timers can safely modify all timers which could
1029  * be found in the base->vectors array.
1030  *
1031  * When a timer is migrating then the TIMER_MIGRATING flag is set and we need
1032  * to wait until the migration is done.
1033  */
1034 static struct timer_base *lock_timer_base(struct timer_list *timer,
1035 					  unsigned long *flags)
1036 	__acquires(timer->base->lock)
1037 {
1038 	for (;;) {
1039 		struct timer_base *base;
1040 		u32 tf;
1041 
1042 		/*
1043 		 * We need to use READ_ONCE() here, otherwise the compiler
1044 		 * might re-read @tf between the check for TIMER_MIGRATING
1045 		 * and spin_lock().
1046 		 */
1047 		tf = READ_ONCE(timer->flags);
1048 
1049 		if (!(tf & TIMER_MIGRATING)) {
1050 			base = get_timer_base(tf);
1051 			raw_spin_lock_irqsave(&base->lock, *flags);
1052 			if (timer->flags == tf)
1053 				return base;
1054 			raw_spin_unlock_irqrestore(&base->lock, *flags);
1055 		}
1056 		cpu_relax();
1057 	}
1058 }
1059 
1060 #define MOD_TIMER_PENDING_ONLY		0x01
1061 #define MOD_TIMER_REDUCE		0x02
1062 #define MOD_TIMER_NOTPENDING		0x04
1063 
1064 static inline int
1065 __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int options)
1066 {
1067 	unsigned long clk = 0, flags, bucket_expiry;
1068 	struct timer_base *base, *new_base;
1069 	unsigned int idx = UINT_MAX;
1070 	int ret = 0;
1071 
1072 	debug_assert_init(timer);
1073 
1074 	/*
1075 	 * This is a common optimization triggered by the networking code - if
1076 	 * the timer is re-modified to have the same timeout or ends up in the
1077 	 * same array bucket then just return:
1078 	 */
1079 	if (!(options & MOD_TIMER_NOTPENDING) && timer_pending(timer)) {
1080 		/*
1081 		 * The downside of this optimization is that it can result in
1082 		 * larger granularity than you would get from adding a new
1083 		 * timer with this expiry.
1084 		 */
1085 		long diff = timer->expires - expires;
1086 
1087 		if (!diff)
1088 			return 1;
1089 		if (options & MOD_TIMER_REDUCE && diff <= 0)
1090 			return 1;
1091 
1092 		/*
1093 		 * We lock timer base and calculate the bucket index right
1094 		 * here. If the timer ends up in the same bucket, then we
1095 		 * just update the expiry time and avoid the whole
1096 		 * dequeue/enqueue dance.
1097 		 */
1098 		base = lock_timer_base(timer, &flags);
1099 		/*
1100 		 * Has @timer been shutdown? This needs to be evaluated
1101 		 * while holding base lock to prevent a race against the
1102 		 * shutdown code.
1103 		 */
1104 		if (!timer->function)
1105 			goto out_unlock;
1106 
1107 		forward_timer_base(base);
1108 
1109 		if (timer_pending(timer) && (options & MOD_TIMER_REDUCE) &&
1110 		    time_before_eq(timer->expires, expires)) {
1111 			ret = 1;
1112 			goto out_unlock;
1113 		}
1114 
1115 		clk = base->clk;
1116 		idx = calc_wheel_index(expires, clk, &bucket_expiry);
1117 
1118 		/*
1119 		 * Retrieve and compare the array index of the pending
1120 		 * timer. If it matches set the expiry to the new value so a
1121 		 * subsequent call will exit in the expires check above.
1122 		 */
1123 		if (idx == timer_get_idx(timer)) {
1124 			if (!(options & MOD_TIMER_REDUCE))
1125 				timer->expires = expires;
1126 			else if (time_after(timer->expires, expires))
1127 				timer->expires = expires;
1128 			ret = 1;
1129 			goto out_unlock;
1130 		}
1131 	} else {
1132 		base = lock_timer_base(timer, &flags);
1133 		/*
1134 		 * Has @timer been shutdown? This needs to be evaluated
1135 		 * while holding base lock to prevent a race against the
1136 		 * shutdown code.
1137 		 */
1138 		if (!timer->function)
1139 			goto out_unlock;
1140 
1141 		forward_timer_base(base);
1142 	}
1143 
1144 	ret = detach_if_pending(timer, base, false);
1145 	if (!ret && (options & MOD_TIMER_PENDING_ONLY))
1146 		goto out_unlock;
1147 
1148 	new_base = get_timer_this_cpu_base(timer->flags);
1149 
1150 	if (base != new_base) {
1151 		/*
1152 		 * We are trying to schedule the timer on the new base.
1153 		 * However we can't change timer's base while it is running,
1154 		 * otherwise timer_delete_sync() can't detect that the timer's
1155 		 * handler yet has not finished. This also guarantees that the
1156 		 * timer is serialized wrt itself.
1157 		 */
1158 		if (likely(base->running_timer != timer)) {
1159 			/* See the comment in lock_timer_base() */
1160 			timer->flags |= TIMER_MIGRATING;
1161 
1162 			raw_spin_unlock(&base->lock);
1163 			base = new_base;
1164 			raw_spin_lock(&base->lock);
1165 			WRITE_ONCE(timer->flags,
1166 				   (timer->flags & ~TIMER_BASEMASK) | base->cpu);
1167 			forward_timer_base(base);
1168 		}
1169 	}
1170 
1171 	debug_timer_activate(timer);
1172 
1173 	timer->expires = expires;
1174 	/*
1175 	 * If 'idx' was calculated above and the base time did not advance
1176 	 * between calculating 'idx' and possibly switching the base, only
1177 	 * enqueue_timer() is required. Otherwise we need to (re)calculate
1178 	 * the wheel index via internal_add_timer().
1179 	 */
1180 	if (idx != UINT_MAX && clk == base->clk)
1181 		enqueue_timer(base, timer, idx, bucket_expiry);
1182 	else
1183 		internal_add_timer(base, timer);
1184 
1185 out_unlock:
1186 	raw_spin_unlock_irqrestore(&base->lock, flags);
1187 
1188 	return ret;
1189 }
1190 
1191 /**
1192  * mod_timer_pending - Modify a pending timer's timeout
1193  * @timer:	The pending timer to be modified
1194  * @expires:	New absolute timeout in jiffies
1195  *
1196  * mod_timer_pending() is the same for pending timers as mod_timer(), but
1197  * will not activate inactive timers.
1198  *
1199  * If @timer->function == NULL then the start operation is silently
1200  * discarded.
1201  *
1202  * Return:
1203  * * %0 - The timer was inactive and not modified or was in
1204  *	  shutdown state and the operation was discarded
1205  * * %1 - The timer was active and requeued to expire at @expires
1206  */
1207 int mod_timer_pending(struct timer_list *timer, unsigned long expires)
1208 {
1209 	return __mod_timer(timer, expires, MOD_TIMER_PENDING_ONLY);
1210 }
1211 EXPORT_SYMBOL(mod_timer_pending);
1212 
1213 /**
1214  * mod_timer - Modify a timer's timeout
1215  * @timer:	The timer to be modified
1216  * @expires:	New absolute timeout in jiffies
1217  *
1218  * mod_timer(timer, expires) is equivalent to:
1219  *
1220  *     del_timer(timer); timer->expires = expires; add_timer(timer);
1221  *
1222  * mod_timer() is more efficient than the above open coded sequence. In
1223  * case that the timer is inactive, the del_timer() part is a NOP. The
1224  * timer is in any case activated with the new expiry time @expires.
1225  *
1226  * Note that if there are multiple unserialized concurrent users of the
1227  * same timer, then mod_timer() is the only safe way to modify the timeout,
1228  * since add_timer() cannot modify an already running timer.
1229  *
1230  * If @timer->function == NULL then the start operation is silently
1231  * discarded. In this case the return value is 0 and meaningless.
1232  *
1233  * Return:
1234  * * %0 - The timer was inactive and started or was in shutdown
1235  *	  state and the operation was discarded
1236  * * %1 - The timer was active and requeued to expire at @expires or
1237  *	  the timer was active and not modified because @expires did
1238  *	  not change the effective expiry time
1239  */
1240 int mod_timer(struct timer_list *timer, unsigned long expires)
1241 {
1242 	return __mod_timer(timer, expires, 0);
1243 }
1244 EXPORT_SYMBOL(mod_timer);
1245 
1246 /**
1247  * timer_reduce - Modify a timer's timeout if it would reduce the timeout
1248  * @timer:	The timer to be modified
1249  * @expires:	New absolute timeout in jiffies
1250  *
1251  * timer_reduce() is very similar to mod_timer(), except that it will only
1252  * modify an enqueued timer if that would reduce the expiration time. If
1253  * @timer is not enqueued it starts the timer.
1254  *
1255  * If @timer->function == NULL then the start operation is silently
1256  * discarded.
1257  *
1258  * Return:
1259  * * %0 - The timer was inactive and started or was in shutdown
1260  *	  state and the operation was discarded
1261  * * %1 - The timer was active and requeued to expire at @expires or
1262  *	  the timer was active and not modified because @expires
1263  *	  did not change the effective expiry time such that the
1264  *	  timer would expire earlier than already scheduled
1265  */
1266 int timer_reduce(struct timer_list *timer, unsigned long expires)
1267 {
1268 	return __mod_timer(timer, expires, MOD_TIMER_REDUCE);
1269 }
1270 EXPORT_SYMBOL(timer_reduce);
1271 
1272 /**
1273  * add_timer - Start a timer
1274  * @timer:	The timer to be started
1275  *
1276  * Start @timer to expire at @timer->expires in the future. @timer->expires
1277  * is the absolute expiry time measured in 'jiffies'. When the timer expires
1278  * timer->function(timer) will be invoked from soft interrupt context.
1279  *
1280  * The @timer->expires and @timer->function fields must be set prior
1281  * to calling this function.
1282  *
1283  * If @timer->function == NULL then the start operation is silently
1284  * discarded.
1285  *
1286  * If @timer->expires is already in the past @timer will be queued to
1287  * expire at the next timer tick.
1288  *
1289  * This can only operate on an inactive timer. Attempts to invoke this on
1290  * an active timer are rejected with a warning.
1291  */
1292 void add_timer(struct timer_list *timer)
1293 {
1294 	if (WARN_ON_ONCE(timer_pending(timer)))
1295 		return;
1296 	__mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
1297 }
1298 EXPORT_SYMBOL(add_timer);
1299 
1300 /**
1301  * add_timer_local() - Start a timer on the local CPU
1302  * @timer:	The timer to be started
1303  *
1304  * Same as add_timer() except that the timer flag TIMER_PINNED is set.
1305  *
1306  * See add_timer() for further details.
1307  */
1308 void add_timer_local(struct timer_list *timer)
1309 {
1310 	if (WARN_ON_ONCE(timer_pending(timer)))
1311 		return;
1312 	timer->flags |= TIMER_PINNED;
1313 	__mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
1314 }
1315 EXPORT_SYMBOL(add_timer_local);
1316 
1317 /**
1318  * add_timer_global() - Start a timer without TIMER_PINNED flag set
1319  * @timer:	The timer to be started
1320  *
1321  * Same as add_timer() except that the timer flag TIMER_PINNED is unset.
1322  *
1323  * See add_timer() for further details.
1324  */
1325 void add_timer_global(struct timer_list *timer)
1326 {
1327 	if (WARN_ON_ONCE(timer_pending(timer)))
1328 		return;
1329 	timer->flags &= ~TIMER_PINNED;
1330 	__mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
1331 }
1332 EXPORT_SYMBOL(add_timer_global);
1333 
1334 /**
1335  * add_timer_on - Start a timer on a particular CPU
1336  * @timer:	The timer to be started
1337  * @cpu:	The CPU to start it on
1338  *
1339  * Same as add_timer() except that it starts the timer on the given CPU and
1340  * the TIMER_PINNED flag is set. When timer shouldn't be a pinned timer in
1341  * the next round, add_timer_global() should be used instead as it unsets
1342  * the TIMER_PINNED flag.
1343  *
1344  * See add_timer() for further details.
1345  */
1346 void add_timer_on(struct timer_list *timer, int cpu)
1347 {
1348 	struct timer_base *new_base, *base;
1349 	unsigned long flags;
1350 
1351 	debug_assert_init(timer);
1352 
1353 	if (WARN_ON_ONCE(timer_pending(timer)))
1354 		return;
1355 
1356 	/* Make sure timer flags have TIMER_PINNED flag set */
1357 	timer->flags |= TIMER_PINNED;
1358 
1359 	new_base = get_timer_cpu_base(timer->flags, cpu);
1360 
1361 	/*
1362 	 * If @timer was on a different CPU, it should be migrated with the
1363 	 * old base locked to prevent other operations proceeding with the
1364 	 * wrong base locked.  See lock_timer_base().
1365 	 */
1366 	base = lock_timer_base(timer, &flags);
1367 	/*
1368 	 * Has @timer been shutdown? This needs to be evaluated while
1369 	 * holding base lock to prevent a race against the shutdown code.
1370 	 */
1371 	if (!timer->function)
1372 		goto out_unlock;
1373 
1374 	if (base != new_base) {
1375 		timer->flags |= TIMER_MIGRATING;
1376 
1377 		raw_spin_unlock(&base->lock);
1378 		base = new_base;
1379 		raw_spin_lock(&base->lock);
1380 		WRITE_ONCE(timer->flags,
1381 			   (timer->flags & ~TIMER_BASEMASK) | cpu);
1382 	}
1383 	forward_timer_base(base);
1384 
1385 	debug_timer_activate(timer);
1386 	internal_add_timer(base, timer);
1387 out_unlock:
1388 	raw_spin_unlock_irqrestore(&base->lock, flags);
1389 }
1390 EXPORT_SYMBOL_GPL(add_timer_on);
1391 
1392 /**
1393  * __timer_delete - Internal function: Deactivate a timer
1394  * @timer:	The timer to be deactivated
1395  * @shutdown:	If true, this indicates that the timer is about to be
1396  *		shutdown permanently.
1397  *
1398  * If @shutdown is true then @timer->function is set to NULL under the
1399  * timer base lock which prevents further rearming of the time. In that
1400  * case any attempt to rearm @timer after this function returns will be
1401  * silently ignored.
1402  *
1403  * Return:
1404  * * %0 - The timer was not pending
1405  * * %1 - The timer was pending and deactivated
1406  */
1407 static int __timer_delete(struct timer_list *timer, bool shutdown)
1408 {
1409 	struct timer_base *base;
1410 	unsigned long flags;
1411 	int ret = 0;
1412 
1413 	debug_assert_init(timer);
1414 
1415 	/*
1416 	 * If @shutdown is set then the lock has to be taken whether the
1417 	 * timer is pending or not to protect against a concurrent rearm
1418 	 * which might hit between the lockless pending check and the lock
1419 	 * acquisition. By taking the lock it is ensured that such a newly
1420 	 * enqueued timer is dequeued and cannot end up with
1421 	 * timer->function == NULL in the expiry code.
1422 	 *
1423 	 * If timer->function is currently executed, then this makes sure
1424 	 * that the callback cannot requeue the timer.
1425 	 */
1426 	if (timer_pending(timer) || shutdown) {
1427 		base = lock_timer_base(timer, &flags);
1428 		ret = detach_if_pending(timer, base, true);
1429 		if (shutdown)
1430 			timer->function = NULL;
1431 		raw_spin_unlock_irqrestore(&base->lock, flags);
1432 	}
1433 
1434 	return ret;
1435 }
1436 
1437 /**
1438  * timer_delete - Deactivate a timer
1439  * @timer:	The timer to be deactivated
1440  *
1441  * The function only deactivates a pending timer, but contrary to
1442  * timer_delete_sync() it does not take into account whether the timer's
1443  * callback function is concurrently executed on a different CPU or not.
1444  * It neither prevents rearming of the timer.  If @timer can be rearmed
1445  * concurrently then the return value of this function is meaningless.
1446  *
1447  * Return:
1448  * * %0 - The timer was not pending
1449  * * %1 - The timer was pending and deactivated
1450  */
1451 int timer_delete(struct timer_list *timer)
1452 {
1453 	return __timer_delete(timer, false);
1454 }
1455 EXPORT_SYMBOL(timer_delete);
1456 
1457 /**
1458  * timer_shutdown - Deactivate a timer and prevent rearming
1459  * @timer:	The timer to be deactivated
1460  *
1461  * The function does not wait for an eventually running timer callback on a
1462  * different CPU but it prevents rearming of the timer. Any attempt to arm
1463  * @timer after this function returns will be silently ignored.
1464  *
1465  * This function is useful for teardown code and should only be used when
1466  * timer_shutdown_sync() cannot be invoked due to locking or context constraints.
1467  *
1468  * Return:
1469  * * %0 - The timer was not pending
1470  * * %1 - The timer was pending
1471  */
1472 int timer_shutdown(struct timer_list *timer)
1473 {
1474 	return __timer_delete(timer, true);
1475 }
1476 EXPORT_SYMBOL_GPL(timer_shutdown);
1477 
1478 /**
1479  * __try_to_del_timer_sync - Internal function: Try to deactivate a timer
1480  * @timer:	Timer to deactivate
1481  * @shutdown:	If true, this indicates that the timer is about to be
1482  *		shutdown permanently.
1483  *
1484  * If @shutdown is true then @timer->function is set to NULL under the
1485  * timer base lock which prevents further rearming of the timer. Any
1486  * attempt to rearm @timer after this function returns will be silently
1487  * ignored.
1488  *
1489  * This function cannot guarantee that the timer cannot be rearmed
1490  * right after dropping the base lock if @shutdown is false. That
1491  * needs to be prevented by the calling code if necessary.
1492  *
1493  * Return:
1494  * * %0  - The timer was not pending
1495  * * %1  - The timer was pending and deactivated
1496  * * %-1 - The timer callback function is running on a different CPU
1497  */
1498 static int __try_to_del_timer_sync(struct timer_list *timer, bool shutdown)
1499 {
1500 	struct timer_base *base;
1501 	unsigned long flags;
1502 	int ret = -1;
1503 
1504 	debug_assert_init(timer);
1505 
1506 	base = lock_timer_base(timer, &flags);
1507 
1508 	if (base->running_timer != timer)
1509 		ret = detach_if_pending(timer, base, true);
1510 	if (shutdown)
1511 		timer->function = NULL;
1512 
1513 	raw_spin_unlock_irqrestore(&base->lock, flags);
1514 
1515 	return ret;
1516 }
1517 
1518 /**
1519  * try_to_del_timer_sync - Try to deactivate a timer
1520  * @timer:	Timer to deactivate
1521  *
1522  * This function tries to deactivate a timer. On success the timer is not
1523  * queued and the timer callback function is not running on any CPU.
1524  *
1525  * This function does not guarantee that the timer cannot be rearmed right
1526  * after dropping the base lock. That needs to be prevented by the calling
1527  * code if necessary.
1528  *
1529  * Return:
1530  * * %0  - The timer was not pending
1531  * * %1  - The timer was pending and deactivated
1532  * * %-1 - The timer callback function is running on a different CPU
1533  */
1534 int try_to_del_timer_sync(struct timer_list *timer)
1535 {
1536 	return __try_to_del_timer_sync(timer, false);
1537 }
1538 EXPORT_SYMBOL(try_to_del_timer_sync);
1539 
1540 #ifdef CONFIG_PREEMPT_RT
1541 static __init void timer_base_init_expiry_lock(struct timer_base *base)
1542 {
1543 	spin_lock_init(&base->expiry_lock);
1544 }
1545 
1546 static inline void timer_base_lock_expiry(struct timer_base *base)
1547 {
1548 	spin_lock(&base->expiry_lock);
1549 }
1550 
1551 static inline void timer_base_unlock_expiry(struct timer_base *base)
1552 {
1553 	spin_unlock(&base->expiry_lock);
1554 }
1555 
1556 /*
1557  * The counterpart to del_timer_wait_running().
1558  *
1559  * If there is a waiter for base->expiry_lock, then it was waiting for the
1560  * timer callback to finish. Drop expiry_lock and reacquire it. That allows
1561  * the waiter to acquire the lock and make progress.
1562  */
1563 static void timer_sync_wait_running(struct timer_base *base)
1564 {
1565 	if (atomic_read(&base->timer_waiters)) {
1566 		raw_spin_unlock_irq(&base->lock);
1567 		spin_unlock(&base->expiry_lock);
1568 		spin_lock(&base->expiry_lock);
1569 		raw_spin_lock_irq(&base->lock);
1570 	}
1571 }
1572 
1573 /*
1574  * This function is called on PREEMPT_RT kernels when the fast path
1575  * deletion of a timer failed because the timer callback function was
1576  * running.
1577  *
1578  * This prevents priority inversion, if the softirq thread on a remote CPU
1579  * got preempted, and it prevents a life lock when the task which tries to
1580  * delete a timer preempted the softirq thread running the timer callback
1581  * function.
1582  */
1583 static void del_timer_wait_running(struct timer_list *timer)
1584 {
1585 	u32 tf;
1586 
1587 	tf = READ_ONCE(timer->flags);
1588 	if (!(tf & (TIMER_MIGRATING | TIMER_IRQSAFE))) {
1589 		struct timer_base *base = get_timer_base(tf);
1590 
1591 		/*
1592 		 * Mark the base as contended and grab the expiry lock,
1593 		 * which is held by the softirq across the timer
1594 		 * callback. Drop the lock immediately so the softirq can
1595 		 * expire the next timer. In theory the timer could already
1596 		 * be running again, but that's more than unlikely and just
1597 		 * causes another wait loop.
1598 		 */
1599 		atomic_inc(&base->timer_waiters);
1600 		spin_lock_bh(&base->expiry_lock);
1601 		atomic_dec(&base->timer_waiters);
1602 		spin_unlock_bh(&base->expiry_lock);
1603 	}
1604 }
1605 #else
1606 static inline void timer_base_init_expiry_lock(struct timer_base *base) { }
1607 static inline void timer_base_lock_expiry(struct timer_base *base) { }
1608 static inline void timer_base_unlock_expiry(struct timer_base *base) { }
1609 static inline void timer_sync_wait_running(struct timer_base *base) { }
1610 static inline void del_timer_wait_running(struct timer_list *timer) { }
1611 #endif
1612 
1613 /**
1614  * __timer_delete_sync - Internal function: Deactivate a timer and wait
1615  *			 for the handler to finish.
1616  * @timer:	The timer to be deactivated
1617  * @shutdown:	If true, @timer->function will be set to NULL under the
1618  *		timer base lock which prevents rearming of @timer
1619  *
1620  * If @shutdown is not set the timer can be rearmed later. If the timer can
1621  * be rearmed concurrently, i.e. after dropping the base lock then the
1622  * return value is meaningless.
1623  *
1624  * If @shutdown is set then @timer->function is set to NULL under timer
1625  * base lock which prevents rearming of the timer. Any attempt to rearm
1626  * a shutdown timer is silently ignored.
1627  *
1628  * If the timer should be reused after shutdown it has to be initialized
1629  * again.
1630  *
1631  * Return:
1632  * * %0	- The timer was not pending
1633  * * %1	- The timer was pending and deactivated
1634  */
1635 static int __timer_delete_sync(struct timer_list *timer, bool shutdown)
1636 {
1637 	int ret;
1638 
1639 #ifdef CONFIG_LOCKDEP
1640 	unsigned long flags;
1641 
1642 	/*
1643 	 * If lockdep gives a backtrace here, please reference
1644 	 * the synchronization rules above.
1645 	 */
1646 	local_irq_save(flags);
1647 	lock_map_acquire(&timer->lockdep_map);
1648 	lock_map_release(&timer->lockdep_map);
1649 	local_irq_restore(flags);
1650 #endif
1651 	/*
1652 	 * don't use it in hardirq context, because it
1653 	 * could lead to deadlock.
1654 	 */
1655 	WARN_ON(in_hardirq() && !(timer->flags & TIMER_IRQSAFE));
1656 
1657 	/*
1658 	 * Must be able to sleep on PREEMPT_RT because of the slowpath in
1659 	 * del_timer_wait_running().
1660 	 */
1661 	if (IS_ENABLED(CONFIG_PREEMPT_RT) && !(timer->flags & TIMER_IRQSAFE))
1662 		lockdep_assert_preemption_enabled();
1663 
1664 	do {
1665 		ret = __try_to_del_timer_sync(timer, shutdown);
1666 
1667 		if (unlikely(ret < 0)) {
1668 			del_timer_wait_running(timer);
1669 			cpu_relax();
1670 		}
1671 	} while (ret < 0);
1672 
1673 	return ret;
1674 }
1675 
1676 /**
1677  * timer_delete_sync - Deactivate a timer and wait for the handler to finish.
1678  * @timer:	The timer to be deactivated
1679  *
1680  * Synchronization rules: Callers must prevent restarting of the timer,
1681  * otherwise this function is meaningless. It must not be called from
1682  * interrupt contexts unless the timer is an irqsafe one. The caller must
1683  * not hold locks which would prevent completion of the timer's callback
1684  * function. The timer's handler must not call add_timer_on(). Upon exit
1685  * the timer is not queued and the handler is not running on any CPU.
1686  *
1687  * For !irqsafe timers, the caller must not hold locks that are held in
1688  * interrupt context. Even if the lock has nothing to do with the timer in
1689  * question.  Here's why::
1690  *
1691  *    CPU0                             CPU1
1692  *    ----                             ----
1693  *                                     <SOFTIRQ>
1694  *                                       call_timer_fn();
1695  *                                       base->running_timer = mytimer;
1696  *    spin_lock_irq(somelock);
1697  *                                     <IRQ>
1698  *                                        spin_lock(somelock);
1699  *    timer_delete_sync(mytimer);
1700  *    while (base->running_timer == mytimer);
1701  *
1702  * Now timer_delete_sync() will never return and never release somelock.
1703  * The interrupt on the other CPU is waiting to grab somelock but it has
1704  * interrupted the softirq that CPU0 is waiting to finish.
1705  *
1706  * This function cannot guarantee that the timer is not rearmed again by
1707  * some concurrent or preempting code, right after it dropped the base
1708  * lock. If there is the possibility of a concurrent rearm then the return
1709  * value of the function is meaningless.
1710  *
1711  * If such a guarantee is needed, e.g. for teardown situations then use
1712  * timer_shutdown_sync() instead.
1713  *
1714  * Return:
1715  * * %0	- The timer was not pending
1716  * * %1	- The timer was pending and deactivated
1717  */
1718 int timer_delete_sync(struct timer_list *timer)
1719 {
1720 	return __timer_delete_sync(timer, false);
1721 }
1722 EXPORT_SYMBOL(timer_delete_sync);
1723 
1724 /**
1725  * timer_shutdown_sync - Shutdown a timer and prevent rearming
1726  * @timer: The timer to be shutdown
1727  *
1728  * When the function returns it is guaranteed that:
1729  *   - @timer is not queued
1730  *   - The callback function of @timer is not running
1731  *   - @timer cannot be enqueued again. Any attempt to rearm
1732  *     @timer is silently ignored.
1733  *
1734  * See timer_delete_sync() for synchronization rules.
1735  *
1736  * This function is useful for final teardown of an infrastructure where
1737  * the timer is subject to a circular dependency problem.
1738  *
1739  * A common pattern for this is a timer and a workqueue where the timer can
1740  * schedule work and work can arm the timer. On shutdown the workqueue must
1741  * be destroyed and the timer must be prevented from rearming. Unless the
1742  * code has conditionals like 'if (mything->in_shutdown)' to prevent that
1743  * there is no way to get this correct with timer_delete_sync().
1744  *
1745  * timer_shutdown_sync() is solving the problem. The correct ordering of
1746  * calls in this case is:
1747  *
1748  *	timer_shutdown_sync(&mything->timer);
1749  *	workqueue_destroy(&mything->workqueue);
1750  *
1751  * After this 'mything' can be safely freed.
1752  *
1753  * This obviously implies that the timer is not required to be functional
1754  * for the rest of the shutdown operation.
1755  *
1756  * Return:
1757  * * %0 - The timer was not pending
1758  * * %1 - The timer was pending
1759  */
1760 int timer_shutdown_sync(struct timer_list *timer)
1761 {
1762 	return __timer_delete_sync(timer, true);
1763 }
1764 EXPORT_SYMBOL_GPL(timer_shutdown_sync);
1765 
1766 static void call_timer_fn(struct timer_list *timer,
1767 			  void (*fn)(struct timer_list *),
1768 			  unsigned long baseclk)
1769 {
1770 	int count = preempt_count();
1771 
1772 #ifdef CONFIG_LOCKDEP
1773 	/*
1774 	 * It is permissible to free the timer from inside the
1775 	 * function that is called from it, this we need to take into
1776 	 * account for lockdep too. To avoid bogus "held lock freed"
1777 	 * warnings as well as problems when looking into
1778 	 * timer->lockdep_map, make a copy and use that here.
1779 	 */
1780 	struct lockdep_map lockdep_map;
1781 
1782 	lockdep_copy_map(&lockdep_map, &timer->lockdep_map);
1783 #endif
1784 	/*
1785 	 * Couple the lock chain with the lock chain at
1786 	 * timer_delete_sync() by acquiring the lock_map around the fn()
1787 	 * call here and in timer_delete_sync().
1788 	 */
1789 	lock_map_acquire(&lockdep_map);
1790 
1791 	trace_timer_expire_entry(timer, baseclk);
1792 	fn(timer);
1793 	trace_timer_expire_exit(timer);
1794 
1795 	lock_map_release(&lockdep_map);
1796 
1797 	if (count != preempt_count()) {
1798 		WARN_ONCE(1, "timer: %pS preempt leak: %08x -> %08x\n",
1799 			  fn, count, preempt_count());
1800 		/*
1801 		 * Restore the preempt count. That gives us a decent
1802 		 * chance to survive and extract information. If the
1803 		 * callback kept a lock held, bad luck, but not worse
1804 		 * than the BUG() we had.
1805 		 */
1806 		preempt_count_set(count);
1807 	}
1808 }
1809 
1810 static void expire_timers(struct timer_base *base, struct hlist_head *head)
1811 {
1812 	/*
1813 	 * This value is required only for tracing. base->clk was
1814 	 * incremented directly before expire_timers was called. But expiry
1815 	 * is related to the old base->clk value.
1816 	 */
1817 	unsigned long baseclk = base->clk - 1;
1818 
1819 	while (!hlist_empty(head)) {
1820 		struct timer_list *timer;
1821 		void (*fn)(struct timer_list *);
1822 
1823 		timer = hlist_entry(head->first, struct timer_list, entry);
1824 
1825 		base->running_timer = timer;
1826 		detach_timer(timer, true);
1827 
1828 		fn = timer->function;
1829 
1830 		if (WARN_ON_ONCE(!fn)) {
1831 			/* Should never happen. Emphasis on should! */
1832 			base->running_timer = NULL;
1833 			continue;
1834 		}
1835 
1836 		if (timer->flags & TIMER_IRQSAFE) {
1837 			raw_spin_unlock(&base->lock);
1838 			call_timer_fn(timer, fn, baseclk);
1839 			raw_spin_lock(&base->lock);
1840 			base->running_timer = NULL;
1841 		} else {
1842 			raw_spin_unlock_irq(&base->lock);
1843 			call_timer_fn(timer, fn, baseclk);
1844 			raw_spin_lock_irq(&base->lock);
1845 			base->running_timer = NULL;
1846 			timer_sync_wait_running(base);
1847 		}
1848 	}
1849 }
1850 
1851 static int collect_expired_timers(struct timer_base *base,
1852 				  struct hlist_head *heads)
1853 {
1854 	unsigned long clk = base->clk = base->next_expiry;
1855 	struct hlist_head *vec;
1856 	int i, levels = 0;
1857 	unsigned int idx;
1858 
1859 	for (i = 0; i < LVL_DEPTH; i++) {
1860 		idx = (clk & LVL_MASK) + i * LVL_SIZE;
1861 
1862 		if (__test_and_clear_bit(idx, base->pending_map)) {
1863 			vec = base->vectors + idx;
1864 			hlist_move_list(vec, heads++);
1865 			levels++;
1866 		}
1867 		/* Is it time to look at the next level? */
1868 		if (clk & LVL_CLK_MASK)
1869 			break;
1870 		/* Shift clock for the next level granularity */
1871 		clk >>= LVL_CLK_SHIFT;
1872 	}
1873 	return levels;
1874 }
1875 
1876 /*
1877  * Find the next pending bucket of a level. Search from level start (@offset)
1878  * + @clk upwards and if nothing there, search from start of the level
1879  * (@offset) up to @offset + clk.
1880  */
1881 static int next_pending_bucket(struct timer_base *base, unsigned offset,
1882 			       unsigned clk)
1883 {
1884 	unsigned pos, start = offset + clk;
1885 	unsigned end = offset + LVL_SIZE;
1886 
1887 	pos = find_next_bit(base->pending_map, end, start);
1888 	if (pos < end)
1889 		return pos - start;
1890 
1891 	pos = find_next_bit(base->pending_map, start, offset);
1892 	return pos < start ? pos + LVL_SIZE - start : -1;
1893 }
1894 
1895 /*
1896  * Search the first expiring timer in the various clock levels. Caller must
1897  * hold base->lock.
1898  *
1899  * Store next expiry time in base->next_expiry.
1900  */
1901 static void next_expiry_recalc(struct timer_base *base)
1902 {
1903 	unsigned long clk, next, adj;
1904 	unsigned lvl, offset = 0;
1905 
1906 	next = base->clk + NEXT_TIMER_MAX_DELTA;
1907 	clk = base->clk;
1908 	for (lvl = 0; lvl < LVL_DEPTH; lvl++, offset += LVL_SIZE) {
1909 		int pos = next_pending_bucket(base, offset, clk & LVL_MASK);
1910 		unsigned long lvl_clk = clk & LVL_CLK_MASK;
1911 
1912 		if (pos >= 0) {
1913 			unsigned long tmp = clk + (unsigned long) pos;
1914 
1915 			tmp <<= LVL_SHIFT(lvl);
1916 			if (time_before(tmp, next))
1917 				next = tmp;
1918 
1919 			/*
1920 			 * If the next expiration happens before we reach
1921 			 * the next level, no need to check further.
1922 			 */
1923 			if (pos <= ((LVL_CLK_DIV - lvl_clk) & LVL_CLK_MASK))
1924 				break;
1925 		}
1926 		/*
1927 		 * Clock for the next level. If the current level clock lower
1928 		 * bits are zero, we look at the next level as is. If not we
1929 		 * need to advance it by one because that's going to be the
1930 		 * next expiring bucket in that level. base->clk is the next
1931 		 * expiring jiffie. So in case of:
1932 		 *
1933 		 * LVL5 LVL4 LVL3 LVL2 LVL1 LVL0
1934 		 *  0    0    0    0    0    0
1935 		 *
1936 		 * we have to look at all levels @index 0. With
1937 		 *
1938 		 * LVL5 LVL4 LVL3 LVL2 LVL1 LVL0
1939 		 *  0    0    0    0    0    2
1940 		 *
1941 		 * LVL0 has the next expiring bucket @index 2. The upper
1942 		 * levels have the next expiring bucket @index 1.
1943 		 *
1944 		 * In case that the propagation wraps the next level the same
1945 		 * rules apply:
1946 		 *
1947 		 * LVL5 LVL4 LVL3 LVL2 LVL1 LVL0
1948 		 *  0    0    0    0    F    2
1949 		 *
1950 		 * So after looking at LVL0 we get:
1951 		 *
1952 		 * LVL5 LVL4 LVL3 LVL2 LVL1
1953 		 *  0    0    0    1    0
1954 		 *
1955 		 * So no propagation from LVL1 to LVL2 because that happened
1956 		 * with the add already, but then we need to propagate further
1957 		 * from LVL2 to LVL3.
1958 		 *
1959 		 * So the simple check whether the lower bits of the current
1960 		 * level are 0 or not is sufficient for all cases.
1961 		 */
1962 		adj = lvl_clk ? 1 : 0;
1963 		clk >>= LVL_CLK_SHIFT;
1964 		clk += adj;
1965 	}
1966 
1967 	base->next_expiry = next;
1968 	base->next_expiry_recalc = false;
1969 	base->timers_pending = !(next == base->clk + NEXT_TIMER_MAX_DELTA);
1970 }
1971 
1972 #ifdef CONFIG_NO_HZ_COMMON
1973 /*
1974  * Check, if the next hrtimer event is before the next timer wheel
1975  * event:
1976  */
1977 static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
1978 {
1979 	u64 nextevt = hrtimer_get_next_event();
1980 
1981 	/*
1982 	 * If high resolution timers are enabled
1983 	 * hrtimer_get_next_event() returns KTIME_MAX.
1984 	 */
1985 	if (expires <= nextevt)
1986 		return expires;
1987 
1988 	/*
1989 	 * If the next timer is already expired, return the tick base
1990 	 * time so the tick is fired immediately.
1991 	 */
1992 	if (nextevt <= basem)
1993 		return basem;
1994 
1995 	/*
1996 	 * Round up to the next jiffie. High resolution timers are
1997 	 * off, so the hrtimers are expired in the tick and we need to
1998 	 * make sure that this tick really expires the timer to avoid
1999 	 * a ping pong of the nohz stop code.
2000 	 *
2001 	 * Use DIV_ROUND_UP_ULL to prevent gcc calling __divdi3
2002 	 */
2003 	return DIV_ROUND_UP_ULL(nextevt, TICK_NSEC) * TICK_NSEC;
2004 }
2005 
2006 static unsigned long next_timer_interrupt(struct timer_base *base,
2007 					  unsigned long basej)
2008 {
2009 	if (base->next_expiry_recalc)
2010 		next_expiry_recalc(base);
2011 
2012 	/*
2013 	 * Move next_expiry for the empty base into the future to prevent an
2014 	 * unnecessary raise of the timer softirq when the next_expiry value
2015 	 * will be reached even if there is no timer pending.
2016 	 *
2017 	 * This update is also required to make timer_base::next_expiry values
2018 	 * easy comparable to find out which base holds the first pending timer.
2019 	 */
2020 	if (!base->timers_pending)
2021 		base->next_expiry = basej + NEXT_TIMER_MAX_DELTA;
2022 
2023 	return base->next_expiry;
2024 }
2025 
2026 static unsigned long fetch_next_timer_interrupt(unsigned long basej, u64 basem,
2027 						struct timer_base *base_local,
2028 						struct timer_base *base_global,
2029 						struct timer_events *tevt)
2030 {
2031 	unsigned long nextevt, nextevt_local, nextevt_global;
2032 	bool local_first;
2033 
2034 	nextevt_local = next_timer_interrupt(base_local, basej);
2035 	nextevt_global = next_timer_interrupt(base_global, basej);
2036 
2037 	local_first = time_before_eq(nextevt_local, nextevt_global);
2038 
2039 	nextevt = local_first ? nextevt_local : nextevt_global;
2040 
2041 	/*
2042 	 * If the @nextevt is at max. one tick away, use @nextevt and store
2043 	 * it in the local expiry value. The next global event is irrelevant in
2044 	 * this case and can be left as KTIME_MAX.
2045 	 */
2046 	if (time_before_eq(nextevt, basej + 1)) {
2047 		/* If we missed a tick already, force 0 delta */
2048 		if (time_before(nextevt, basej))
2049 			nextevt = basej;
2050 		tevt->local = basem + (u64)(nextevt - basej) * TICK_NSEC;
2051 
2052 		/*
2053 		 * This is required for the remote check only but it doesn't
2054 		 * hurt, when it is done for both call sites:
2055 		 *
2056 		 * * The remote callers will only take care of the global timers
2057 		 *   as local timers will be handled by CPU itself. When not
2058 		 *   updating tevt->global with the already missed first global
2059 		 *   timer, it is possible that it will be missed completely.
2060 		 *
2061 		 * * The local callers will ignore the tevt->global anyway, when
2062 		 *   nextevt is max. one tick away.
2063 		 */
2064 		if (!local_first)
2065 			tevt->global = tevt->local;
2066 		return nextevt;
2067 	}
2068 
2069 	/*
2070 	 * Update tevt.* values:
2071 	 *
2072 	 * If the local queue expires first, then the global event can be
2073 	 * ignored. If the global queue is empty, nothing to do either.
2074 	 */
2075 	if (!local_first && base_global->timers_pending)
2076 		tevt->global = basem + (u64)(nextevt_global - basej) * TICK_NSEC;
2077 
2078 	if (base_local->timers_pending)
2079 		tevt->local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
2080 
2081 	return nextevt;
2082 }
2083 
2084 # ifdef CONFIG_SMP
2085 /**
2086  * fetch_next_timer_interrupt_remote() - Store next timers into @tevt
2087  * @basej:	base time jiffies
2088  * @basem:	base time clock monotonic
2089  * @tevt:	Pointer to the storage for the expiry values
2090  * @cpu:	Remote CPU
2091  *
2092  * Stores the next pending local and global timer expiry values in the
2093  * struct pointed to by @tevt. If a queue is empty the corresponding
2094  * field is set to KTIME_MAX. If local event expires before global
2095  * event, global event is set to KTIME_MAX as well.
2096  *
2097  * Caller needs to make sure timer base locks are held (use
2098  * timer_lock_remote_bases() for this purpose).
2099  */
2100 void fetch_next_timer_interrupt_remote(unsigned long basej, u64 basem,
2101 				       struct timer_events *tevt,
2102 				       unsigned int cpu)
2103 {
2104 	struct timer_base *base_local, *base_global;
2105 
2106 	/* Preset local / global events */
2107 	tevt->local = tevt->global = KTIME_MAX;
2108 
2109 	base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
2110 	base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
2111 
2112 	lockdep_assert_held(&base_local->lock);
2113 	lockdep_assert_held(&base_global->lock);
2114 
2115 	fetch_next_timer_interrupt(basej, basem, base_local, base_global, tevt);
2116 }
2117 
2118 /**
2119  * timer_unlock_remote_bases - unlock timer bases of cpu
2120  * @cpu:	Remote CPU
2121  *
2122  * Unlocks the remote timer bases.
2123  */
2124 void timer_unlock_remote_bases(unsigned int cpu)
2125 	__releases(timer_bases[BASE_LOCAL]->lock)
2126 	__releases(timer_bases[BASE_GLOBAL]->lock)
2127 {
2128 	struct timer_base *base_local, *base_global;
2129 
2130 	base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
2131 	base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
2132 
2133 	raw_spin_unlock(&base_global->lock);
2134 	raw_spin_unlock(&base_local->lock);
2135 }
2136 
2137 /**
2138  * timer_lock_remote_bases - lock timer bases of cpu
2139  * @cpu:	Remote CPU
2140  *
2141  * Locks the remote timer bases.
2142  */
2143 void timer_lock_remote_bases(unsigned int cpu)
2144 	__acquires(timer_bases[BASE_LOCAL]->lock)
2145 	__acquires(timer_bases[BASE_GLOBAL]->lock)
2146 {
2147 	struct timer_base *base_local, *base_global;
2148 
2149 	base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
2150 	base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
2151 
2152 	lockdep_assert_irqs_disabled();
2153 
2154 	raw_spin_lock(&base_local->lock);
2155 	raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
2156 }
2157 
2158 /**
2159  * timer_base_is_idle() - Return whether timer base is set idle
2160  *
2161  * Returns value of local timer base is_idle value.
2162  */
2163 bool timer_base_is_idle(void)
2164 {
2165 	return __this_cpu_read(timer_bases[BASE_LOCAL].is_idle);
2166 }
2167 
2168 static void __run_timer_base(struct timer_base *base);
2169 
2170 /**
2171  * timer_expire_remote() - expire global timers of cpu
2172  * @cpu:	Remote CPU
2173  *
2174  * Expire timers of global base of remote CPU.
2175  */
2176 void timer_expire_remote(unsigned int cpu)
2177 {
2178 	struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
2179 
2180 	__run_timer_base(base);
2181 }
2182 
2183 static void timer_use_tmigr(unsigned long basej, u64 basem,
2184 			    unsigned long *nextevt, bool *tick_stop_path,
2185 			    bool timer_base_idle, struct timer_events *tevt)
2186 {
2187 	u64 next_tmigr;
2188 
2189 	if (timer_base_idle)
2190 		next_tmigr = tmigr_cpu_new_timer(tevt->global);
2191 	else if (tick_stop_path)
2192 		next_tmigr = tmigr_cpu_deactivate(tevt->global);
2193 	else
2194 		next_tmigr = tmigr_quick_check(tevt->global);
2195 
2196 	/*
2197 	 * If the CPU is the last going idle in timer migration hierarchy, make
2198 	 * sure the CPU will wake up in time to handle remote timers.
2199 	 * next_tmigr == KTIME_MAX if other CPUs are still active.
2200 	 */
2201 	if (next_tmigr < tevt->local) {
2202 		u64 tmp;
2203 
2204 		/* If we missed a tick already, force 0 delta */
2205 		if (next_tmigr < basem)
2206 			next_tmigr = basem;
2207 
2208 		tmp = div_u64(next_tmigr - basem, TICK_NSEC);
2209 
2210 		*nextevt = basej + (unsigned long)tmp;
2211 		tevt->local = next_tmigr;
2212 	}
2213 }
2214 # else
2215 static void timer_use_tmigr(unsigned long basej, u64 basem,
2216 			    unsigned long *nextevt, bool *tick_stop_path,
2217 			    bool timer_base_idle, struct timer_events *tevt)
2218 {
2219 	/*
2220 	 * Make sure first event is written into tevt->local to not miss a
2221 	 * timer on !SMP systems.
2222 	 */
2223 	tevt->local = min_t(u64, tevt->local, tevt->global);
2224 }
2225 # endif /* CONFIG_SMP */
2226 
2227 static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
2228 					     bool *idle)
2229 {
2230 	struct timer_events tevt = { .local = KTIME_MAX, .global = KTIME_MAX };
2231 	struct timer_base *base_local, *base_global;
2232 	unsigned long nextevt;
2233 	bool idle_is_possible;
2234 
2235 	/*
2236 	 * When the CPU is offline, the tick is cancelled and nothing is supposed
2237 	 * to try to stop it.
2238 	 */
2239 	if (WARN_ON_ONCE(cpu_is_offline(smp_processor_id()))) {
2240 		if (idle)
2241 			*idle = true;
2242 		return tevt.local;
2243 	}
2244 
2245 	base_local = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
2246 	base_global = this_cpu_ptr(&timer_bases[BASE_GLOBAL]);
2247 
2248 	raw_spin_lock(&base_local->lock);
2249 	raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
2250 
2251 	nextevt = fetch_next_timer_interrupt(basej, basem, base_local,
2252 					     base_global, &tevt);
2253 
2254 	/*
2255 	 * If the next event is only one jiffie ahead there is no need to call
2256 	 * timer migration hierarchy related functions. The value for the next
2257 	 * global timer in @tevt struct equals then KTIME_MAX. This is also
2258 	 * true, when the timer base is idle.
2259 	 *
2260 	 * The proper timer migration hierarchy function depends on the callsite
2261 	 * and whether timer base is idle or not. @nextevt will be updated when
2262 	 * this CPU needs to handle the first timer migration hierarchy
2263 	 * event. See timer_use_tmigr() for detailed information.
2264 	 */
2265 	idle_is_possible = time_after(nextevt, basej + 1);
2266 	if (idle_is_possible)
2267 		timer_use_tmigr(basej, basem, &nextevt, idle,
2268 				base_local->is_idle, &tevt);
2269 
2270 	/*
2271 	 * We have a fresh next event. Check whether we can forward the
2272 	 * base.
2273 	 */
2274 	__forward_timer_base(base_local, basej);
2275 	__forward_timer_base(base_global, basej);
2276 
2277 	/*
2278 	 * Set base->is_idle only when caller is timer_base_try_to_set_idle()
2279 	 */
2280 	if (idle) {
2281 		/*
2282 		 * Bases are idle if the next event is more than a tick
2283 		 * away. Caution: @nextevt could have changed by enqueueing a
2284 		 * global timer into timer migration hierarchy. Therefore a new
2285 		 * check is required here.
2286 		 *
2287 		 * If the base is marked idle then any timer add operation must
2288 		 * forward the base clk itself to keep granularity small. This
2289 		 * idle logic is only maintained for the BASE_LOCAL and
2290 		 * BASE_GLOBAL base, deferrable timers may still see large
2291 		 * granularity skew (by design).
2292 		 */
2293 		if (!base_local->is_idle && time_after(nextevt, basej + 1)) {
2294 			base_local->is_idle = true;
2295 			/*
2296 			 * Global timers queued locally while running in a task
2297 			 * in nohz_full mode need a self-IPI to kick reprogramming
2298 			 * in IRQ tail.
2299 			 */
2300 			if (tick_nohz_full_cpu(base_local->cpu))
2301 				base_global->is_idle = true;
2302 			trace_timer_base_idle(true, base_local->cpu);
2303 		}
2304 		*idle = base_local->is_idle;
2305 
2306 		/*
2307 		 * When timer base is not set idle, undo the effect of
2308 		 * tmigr_cpu_deactivate() to prevent inconsistent states - active
2309 		 * timer base but inactive timer migration hierarchy.
2310 		 *
2311 		 * When timer base was already marked idle, nothing will be
2312 		 * changed here.
2313 		 */
2314 		if (!base_local->is_idle && idle_is_possible)
2315 			tmigr_cpu_activate();
2316 	}
2317 
2318 	raw_spin_unlock(&base_global->lock);
2319 	raw_spin_unlock(&base_local->lock);
2320 
2321 	return cmp_next_hrtimer_event(basem, tevt.local);
2322 }
2323 
2324 /**
2325  * get_next_timer_interrupt() - return the time (clock mono) of the next timer
2326  * @basej:	base time jiffies
2327  * @basem:	base time clock monotonic
2328  *
2329  * Returns the tick aligned clock monotonic time of the next pending timer or
2330  * KTIME_MAX if no timer is pending. If timer of global base was queued into
2331  * timer migration hierarchy, first global timer is not taken into account. If
2332  * it was the last CPU of timer migration hierarchy going idle, first global
2333  * event is taken into account.
2334  */
2335 u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
2336 {
2337 	return __get_next_timer_interrupt(basej, basem, NULL);
2338 }
2339 
2340 /**
2341  * timer_base_try_to_set_idle() - Try to set the idle state of the timer bases
2342  * @basej:	base time jiffies
2343  * @basem:	base time clock monotonic
2344  * @idle:	pointer to store the value of timer_base->is_idle on return;
2345  *		*idle contains the information whether tick was already stopped
2346  *
2347  * Returns the tick aligned clock monotonic time of the next pending timer or
2348  * KTIME_MAX if no timer is pending. When tick was already stopped KTIME_MAX is
2349  * returned as well.
2350  */
2351 u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle)
2352 {
2353 	if (*idle)
2354 		return KTIME_MAX;
2355 
2356 	return __get_next_timer_interrupt(basej, basem, idle);
2357 }
2358 
2359 /**
2360  * timer_clear_idle - Clear the idle state of the timer base
2361  *
2362  * Called with interrupts disabled
2363  */
2364 void timer_clear_idle(void)
2365 {
2366 	/*
2367 	 * We do this unlocked. The worst outcome is a remote pinned timer
2368 	 * enqueue sending a pointless IPI, but taking the lock would just
2369 	 * make the window for sending the IPI a few instructions smaller
2370 	 * for the cost of taking the lock in the exit from idle
2371 	 * path. Required for BASE_LOCAL only.
2372 	 */
2373 	__this_cpu_write(timer_bases[BASE_LOCAL].is_idle, false);
2374 	if (tick_nohz_full_cpu(smp_processor_id()))
2375 		__this_cpu_write(timer_bases[BASE_GLOBAL].is_idle, false);
2376 	trace_timer_base_idle(false, smp_processor_id());
2377 
2378 	/* Activate without holding the timer_base->lock */
2379 	tmigr_cpu_activate();
2380 }
2381 #endif
2382 
2383 /**
2384  * __run_timers - run all expired timers (if any) on this CPU.
2385  * @base: the timer vector to be processed.
2386  */
2387 static inline void __run_timers(struct timer_base *base)
2388 {
2389 	struct hlist_head heads[LVL_DEPTH];
2390 	int levels;
2391 
2392 	lockdep_assert_held(&base->lock);
2393 
2394 	if (base->running_timer)
2395 		return;
2396 
2397 	while (time_after_eq(jiffies, base->clk) &&
2398 	       time_after_eq(jiffies, base->next_expiry)) {
2399 		levels = collect_expired_timers(base, heads);
2400 		/*
2401 		 * The two possible reasons for not finding any expired
2402 		 * timer at this clk are that all matching timers have been
2403 		 * dequeued or no timer has been queued since
2404 		 * base::next_expiry was set to base::clk +
2405 		 * NEXT_TIMER_MAX_DELTA.
2406 		 */
2407 		WARN_ON_ONCE(!levels && !base->next_expiry_recalc
2408 			     && base->timers_pending);
2409 		/*
2410 		 * While executing timers, base->clk is set 1 offset ahead of
2411 		 * jiffies to avoid endless requeuing to current jiffies.
2412 		 */
2413 		base->clk++;
2414 		next_expiry_recalc(base);
2415 
2416 		while (levels--)
2417 			expire_timers(base, heads + levels);
2418 	}
2419 }
2420 
2421 static void __run_timer_base(struct timer_base *base)
2422 {
2423 	if (time_before(jiffies, base->next_expiry))
2424 		return;
2425 
2426 	timer_base_lock_expiry(base);
2427 	raw_spin_lock_irq(&base->lock);
2428 	__run_timers(base);
2429 	raw_spin_unlock_irq(&base->lock);
2430 	timer_base_unlock_expiry(base);
2431 }
2432 
2433 static void run_timer_base(int index)
2434 {
2435 	struct timer_base *base = this_cpu_ptr(&timer_bases[index]);
2436 
2437 	__run_timer_base(base);
2438 }
2439 
2440 /*
2441  * This function runs timers and the timer-tq in bottom half context.
2442  */
2443 static __latent_entropy void run_timer_softirq(void)
2444 {
2445 	run_timer_base(BASE_LOCAL);
2446 	if (IS_ENABLED(CONFIG_NO_HZ_COMMON)) {
2447 		run_timer_base(BASE_GLOBAL);
2448 		run_timer_base(BASE_DEF);
2449 
2450 		if (is_timers_nohz_active())
2451 			tmigr_handle_remote();
2452 	}
2453 }
2454 
2455 /*
2456  * Called by the local, per-CPU timer interrupt on SMP.
2457  */
2458 static void run_local_timers(void)
2459 {
2460 	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
2461 
2462 	hrtimer_run_queues();
2463 
2464 	for (int i = 0; i < NR_BASES; i++, base++) {
2465 		/* Raise the softirq only if required. */
2466 		if (time_after_eq(jiffies, base->next_expiry) ||
2467 		    (i == BASE_DEF && tmigr_requires_handle_remote())) {
2468 			raise_softirq(TIMER_SOFTIRQ);
2469 			return;
2470 		}
2471 	}
2472 }
2473 
2474 /*
2475  * Called from the timer interrupt handler to charge one tick to the current
2476  * process.  user_tick is 1 if the tick is user time, 0 for system.
2477  */
2478 void update_process_times(int user_tick)
2479 {
2480 	struct task_struct *p = current;
2481 
2482 	/* Note: this timer irq context must be accounted for as well. */
2483 	account_process_tick(p, user_tick);
2484 	run_local_timers();
2485 	rcu_sched_clock_irq(user_tick);
2486 #ifdef CONFIG_IRQ_WORK
2487 	if (in_irq())
2488 		irq_work_tick();
2489 #endif
2490 	sched_tick();
2491 	if (IS_ENABLED(CONFIG_POSIX_TIMERS))
2492 		run_posix_cpu_timers();
2493 }
2494 
2495 /*
2496  * Since schedule_timeout()'s timer is defined on the stack, it must store
2497  * the target task on the stack as well.
2498  */
2499 struct process_timer {
2500 	struct timer_list timer;
2501 	struct task_struct *task;
2502 };
2503 
2504 static void process_timeout(struct timer_list *t)
2505 {
2506 	struct process_timer *timeout = from_timer(timeout, t, timer);
2507 
2508 	wake_up_process(timeout->task);
2509 }
2510 
2511 /**
2512  * schedule_timeout - sleep until timeout
2513  * @timeout: timeout value in jiffies
2514  *
2515  * Make the current task sleep until @timeout jiffies have elapsed.
2516  * The function behavior depends on the current task state
2517  * (see also set_current_state() description):
2518  *
2519  * %TASK_RUNNING - the scheduler is called, but the task does not sleep
2520  * at all. That happens because sched_submit_work() does nothing for
2521  * tasks in %TASK_RUNNING state.
2522  *
2523  * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
2524  * pass before the routine returns unless the current task is explicitly
2525  * woken up, (e.g. by wake_up_process()).
2526  *
2527  * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
2528  * delivered to the current task or the current task is explicitly woken
2529  * up.
2530  *
2531  * The current task state is guaranteed to be %TASK_RUNNING when this
2532  * routine returns.
2533  *
2534  * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
2535  * the CPU away without a bound on the timeout. In this case the return
2536  * value will be %MAX_SCHEDULE_TIMEOUT.
2537  *
2538  * Returns 0 when the timer has expired otherwise the remaining time in
2539  * jiffies will be returned. In all cases the return value is guaranteed
2540  * to be non-negative.
2541  */
2542 signed long __sched schedule_timeout(signed long timeout)
2543 {
2544 	struct process_timer timer;
2545 	unsigned long expire;
2546 
2547 	switch (timeout)
2548 	{
2549 	case MAX_SCHEDULE_TIMEOUT:
2550 		/*
2551 		 * These two special cases are useful to be comfortable
2552 		 * in the caller. Nothing more. We could take
2553 		 * MAX_SCHEDULE_TIMEOUT from one of the negative value
2554 		 * but I' d like to return a valid offset (>=0) to allow
2555 		 * the caller to do everything it want with the retval.
2556 		 */
2557 		schedule();
2558 		goto out;
2559 	default:
2560 		/*
2561 		 * Another bit of PARANOID. Note that the retval will be
2562 		 * 0 since no piece of kernel is supposed to do a check
2563 		 * for a negative retval of schedule_timeout() (since it
2564 		 * should never happens anyway). You just have the printk()
2565 		 * that will tell you if something is gone wrong and where.
2566 		 */
2567 		if (timeout < 0) {
2568 			printk(KERN_ERR "schedule_timeout: wrong timeout "
2569 				"value %lx\n", timeout);
2570 			dump_stack();
2571 			__set_current_state(TASK_RUNNING);
2572 			goto out;
2573 		}
2574 	}
2575 
2576 	expire = timeout + jiffies;
2577 
2578 	timer.task = current;
2579 	timer_setup_on_stack(&timer.timer, process_timeout, 0);
2580 	__mod_timer(&timer.timer, expire, MOD_TIMER_NOTPENDING);
2581 	schedule();
2582 	del_timer_sync(&timer.timer);
2583 
2584 	/* Remove the timer from the object tracker */
2585 	destroy_timer_on_stack(&timer.timer);
2586 
2587 	timeout = expire - jiffies;
2588 
2589  out:
2590 	return timeout < 0 ? 0 : timeout;
2591 }
2592 EXPORT_SYMBOL(schedule_timeout);
2593 
2594 /*
2595  * We can use __set_current_state() here because schedule_timeout() calls
2596  * schedule() unconditionally.
2597  */
2598 signed long __sched schedule_timeout_interruptible(signed long timeout)
2599 {
2600 	__set_current_state(TASK_INTERRUPTIBLE);
2601 	return schedule_timeout(timeout);
2602 }
2603 EXPORT_SYMBOL(schedule_timeout_interruptible);
2604 
2605 signed long __sched schedule_timeout_killable(signed long timeout)
2606 {
2607 	__set_current_state(TASK_KILLABLE);
2608 	return schedule_timeout(timeout);
2609 }
2610 EXPORT_SYMBOL(schedule_timeout_killable);
2611 
2612 signed long __sched schedule_timeout_uninterruptible(signed long timeout)
2613 {
2614 	__set_current_state(TASK_UNINTERRUPTIBLE);
2615 	return schedule_timeout(timeout);
2616 }
2617 EXPORT_SYMBOL(schedule_timeout_uninterruptible);
2618 
2619 /*
2620  * Like schedule_timeout_uninterruptible(), except this task will not contribute
2621  * to load average.
2622  */
2623 signed long __sched schedule_timeout_idle(signed long timeout)
2624 {
2625 	__set_current_state(TASK_IDLE);
2626 	return schedule_timeout(timeout);
2627 }
2628 EXPORT_SYMBOL(schedule_timeout_idle);
2629 
2630 #ifdef CONFIG_HOTPLUG_CPU
2631 static void migrate_timer_list(struct timer_base *new_base, struct hlist_head *head)
2632 {
2633 	struct timer_list *timer;
2634 	int cpu = new_base->cpu;
2635 
2636 	while (!hlist_empty(head)) {
2637 		timer = hlist_entry(head->first, struct timer_list, entry);
2638 		detach_timer(timer, false);
2639 		timer->flags = (timer->flags & ~TIMER_BASEMASK) | cpu;
2640 		internal_add_timer(new_base, timer);
2641 	}
2642 }
2643 
2644 int timers_prepare_cpu(unsigned int cpu)
2645 {
2646 	struct timer_base *base;
2647 	int b;
2648 
2649 	for (b = 0; b < NR_BASES; b++) {
2650 		base = per_cpu_ptr(&timer_bases[b], cpu);
2651 		base->clk = jiffies;
2652 		base->next_expiry = base->clk + NEXT_TIMER_MAX_DELTA;
2653 		base->next_expiry_recalc = false;
2654 		base->timers_pending = false;
2655 		base->is_idle = false;
2656 	}
2657 	return 0;
2658 }
2659 
2660 int timers_dead_cpu(unsigned int cpu)
2661 {
2662 	struct timer_base *old_base;
2663 	struct timer_base *new_base;
2664 	int b, i;
2665 
2666 	for (b = 0; b < NR_BASES; b++) {
2667 		old_base = per_cpu_ptr(&timer_bases[b], cpu);
2668 		new_base = get_cpu_ptr(&timer_bases[b]);
2669 		/*
2670 		 * The caller is globally serialized and nobody else
2671 		 * takes two locks at once, deadlock is not possible.
2672 		 */
2673 		raw_spin_lock_irq(&new_base->lock);
2674 		raw_spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING);
2675 
2676 		/*
2677 		 * The current CPUs base clock might be stale. Update it
2678 		 * before moving the timers over.
2679 		 */
2680 		forward_timer_base(new_base);
2681 
2682 		WARN_ON_ONCE(old_base->running_timer);
2683 		old_base->running_timer = NULL;
2684 
2685 		for (i = 0; i < WHEEL_SIZE; i++)
2686 			migrate_timer_list(new_base, old_base->vectors + i);
2687 
2688 		raw_spin_unlock(&old_base->lock);
2689 		raw_spin_unlock_irq(&new_base->lock);
2690 		put_cpu_ptr(&timer_bases);
2691 	}
2692 	return 0;
2693 }
2694 
2695 #endif /* CONFIG_HOTPLUG_CPU */
2696 
2697 static void __init init_timer_cpu(int cpu)
2698 {
2699 	struct timer_base *base;
2700 	int i;
2701 
2702 	for (i = 0; i < NR_BASES; i++) {
2703 		base = per_cpu_ptr(&timer_bases[i], cpu);
2704 		base->cpu = cpu;
2705 		raw_spin_lock_init(&base->lock);
2706 		base->clk = jiffies;
2707 		base->next_expiry = base->clk + NEXT_TIMER_MAX_DELTA;
2708 		timer_base_init_expiry_lock(base);
2709 	}
2710 }
2711 
2712 static void __init init_timer_cpus(void)
2713 {
2714 	int cpu;
2715 
2716 	for_each_possible_cpu(cpu)
2717 		init_timer_cpu(cpu);
2718 }
2719 
2720 void __init init_timers(void)
2721 {
2722 	init_timer_cpus();
2723 	posix_cputimers_init_work();
2724 	open_softirq(TIMER_SOFTIRQ, run_timer_softirq);
2725 }
2726 
2727 /**
2728  * msleep - sleep safely even with waitqueue interruptions
2729  * @msecs: Time in milliseconds to sleep for
2730  */
2731 void msleep(unsigned int msecs)
2732 {
2733 	unsigned long timeout = msecs_to_jiffies(msecs) + 1;
2734 
2735 	while (timeout)
2736 		timeout = schedule_timeout_uninterruptible(timeout);
2737 }
2738 
2739 EXPORT_SYMBOL(msleep);
2740 
2741 /**
2742  * msleep_interruptible - sleep waiting for signals
2743  * @msecs: Time in milliseconds to sleep for
2744  */
2745 unsigned long msleep_interruptible(unsigned int msecs)
2746 {
2747 	unsigned long timeout = msecs_to_jiffies(msecs) + 1;
2748 
2749 	while (timeout && !signal_pending(current))
2750 		timeout = schedule_timeout_interruptible(timeout);
2751 	return jiffies_to_msecs(timeout);
2752 }
2753 
2754 EXPORT_SYMBOL(msleep_interruptible);
2755 
2756 /**
2757  * usleep_range_state - Sleep for an approximate time in a given state
2758  * @min:	Minimum time in usecs to sleep
2759  * @max:	Maximum time in usecs to sleep
2760  * @state:	State of the current task that will be while sleeping
2761  *
2762  * In non-atomic context where the exact wakeup time is flexible, use
2763  * usleep_range_state() instead of udelay().  The sleep improves responsiveness
2764  * by avoiding the CPU-hogging busy-wait of udelay(), and the range reduces
2765  * power usage by allowing hrtimers to take advantage of an already-
2766  * scheduled interrupt instead of scheduling a new one just for this sleep.
2767  */
2768 void __sched usleep_range_state(unsigned long min, unsigned long max,
2769 				unsigned int state)
2770 {
2771 	ktime_t exp = ktime_add_us(ktime_get(), min);
2772 	u64 delta = (u64)(max - min) * NSEC_PER_USEC;
2773 
2774 	for (;;) {
2775 		__set_current_state(state);
2776 		/* Do not return before the requested sleep time has elapsed */
2777 		if (!schedule_hrtimeout_range(&exp, delta, HRTIMER_MODE_ABS))
2778 			break;
2779 	}
2780 }
2781 EXPORT_SYMBOL(usleep_range_state);
2782