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