// SPDX-License-Identifier: GPL-2.0/* *  Kernel internal timers * *  Copyright (C) 1991, 1992  Linus Torvalds * *  1997-01-28  Modified by Finn Arne Gangstad to make timers scale better. * *  1997-09-10  Updated NTP code according to technical memorandum Jan '96 *              "A Kernel Model for Precision Timekeeping" by Dave Mills *  1998-12-24  Fixed a xtime SMP race (we need the xtime_lock rw spinlock to *              serialize accesses to xtime/lost_ticks). *                              Copyright (C) 1998  Andrea Arcangeli *  1999-03-10  Improved NTP compatibility by Ulrich Windl *  2002-05-31	Move sys_sysinfo here and make its locking sane, Robert Love *  2000-10-05  Implemented scalable SMP per-CPU timer handling. *                              Copyright (C) 2000, 2001, 2002  Ingo Molnar *              Designed by David S. Miller, Alexey Kuznetsov and Ingo Molnar */ #include <linux/kernel_stat.h>#include <linux/export.h>#include <linux/interrupt.h>#include <linux/percpu.h>#include <linux/init.h>#include <linux/mm.h>#include <linux/swap.h>#include <linux/pid_namespace.h>#include <linux/notifier.h>#include <linux/thread_info.h>#include <linux/time.h>#include <linux/jiffies.h>#include <linux/posix-timers.h>#include <linux/cpu.h>#include <linux/syscalls.h>#include <linux/delay.h>#include <linux/tick.h>#include <linux/kallsyms.h>#include <linux/irq_work.h>#include <linux/sched/signal.h>#include <linux/sched/sysctl.h>#include <linux/sched/nohz.h>#include <linux/sched/debug.h>#include <linux/slab.h>#include <linux/compat.h>#include <linux/random.h> #include <linux/uaccess.h>#include <asm/unistd.h>#include <asm/div64.h>#include <asm/timex.h>#include <asm/io.h> #include "tick-internal.h" #define CREATE_TRACE_POINTS#include <trace/events/timer.h> __visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES; EXPORT_SYMBOL(jiffies_64); /* * The timer wheel has LVL_DEPTH array levels. Each level provides an array of * LVL_SIZE buckets. Each level is driven by its own clock and therefor each * level has a different granularity. * * The level granularity is:		LVL_CLK_DIV ^ lvl * The level clock frequency is:	HZ / (LVL_CLK_DIV ^ level) * * The array level of a newly armed timer depends on the relative expiry * time. The farther the expiry time is away the higher the array level and * therefor the granularity becomes. * * Contrary to the original timer wheel implementation, which aims for 'exact' * expiry of the timers, this implementation removes the need for recascading * the timers into the lower array levels. The previous 'classic' timer wheel * implementation of the kernel already violated the 'exact' expiry by adding * slack to the expiry time to provide batched expiration. The granularity * levels provide implicit batching. * * This is an optimization of the original timer wheel implementation for the * majority of the timer wheel use cases: timeouts. The vast majority of * timeout timers (networking, disk I/O ...) are canceled before expiry. If * the timeout expires it indicates that normal operation is disturbed, so it * does not matter much whether the timeout comes with a slight delay. * * The only exception to this are networking timers with a small expiry * time. They rely on the granularity. Those fit into the first wheel level, * which has HZ granularity. * * We don't have cascading anymore. timers with a expiry time above the * capacity of the last wheel level are force expired at the maximum timeout * value of the last wheel level. From data sampling we know that the maximum * value observed is 5 days (network connection tracking), so this should not * be an issue. * * The currently chosen array constants values are a good compromise between * array size and granularity. * * This results in the following granularity and range levels: * * HZ 1000 steps * Level Offset  Granularity            Range *  0      0         1 ms                0 ms -         63 ms *  1     64         8 ms               64 ms -        511 ms *  2    128        64 ms              512 ms -       4095 ms (512ms - ~4s) *  3    192       512 ms             4096 ms -      32767 ms (~4s - ~32s) *  4    256      4096 ms (~4s)      32768 ms -     262143 ms (~32s - ~4m) *  5    320     32768 ms (~32s)    262144 ms -    2097151 ms (~4m - ~34m) *  6    384    262144 ms (~4m)    2097152 ms -   16777215 ms (~34m - ~4h) *  7    448   2097152 ms (~34m)  16777216 ms -  134217727 ms (~4h - ~1d) *  8    512  16777216 ms (~4h)  134217728 ms - 1073741822 ms (~1d - ~12d) * * HZ  300 * Level Offset  Granularity            Range *  0	   0         3 ms                0 ms -        210 ms *  1	  64        26 ms              213 ms -       1703 ms (213ms - ~1s) *  2	 128       213 ms             1706 ms -      13650 ms (~1s - ~13s) *  3	 192      1706 ms (~1s)      13653 ms -     109223 ms (~13s - ~1m) *  4	 256     13653 ms (~13s)    109226 ms -     873810 ms (~1m - ~14m) *  5	 320    109226 ms (~1m)     873813 ms -    6990503 ms (~14m - ~1h) *  6	 384    873813 ms (~14m)   6990506 ms -   55924050 ms (~1h - ~15h) *  7	 448   6990506 ms (~1h)   55924053 ms -  447392423 ms (~15h - ~5d) *  8    512  55924053 ms (~15h) 447392426 ms - 3579139406 ms (~5d - ~41d) * * HZ  250 * Level Offset  Granularity            Range *  0	   0         4 ms                0 ms -        255 ms *  1	  64        32 ms              256 ms -       2047 ms (256ms - ~2s) *  2	 128       256 ms             2048 ms -      16383 ms (~2s - ~16s) *  3	 192      2048 ms (~2s)      16384 ms -     131071 ms (~16s - ~2m) *  4	 256     16384 ms (~16s)    131072 ms -    1048575 ms (~2m - ~17m) *  5	 320    131072 ms (~2m)    1048576 ms -    8388607 ms (~17m - ~2h) *  6	 384   1048576 ms (~17m)   8388608 ms -   67108863 ms (~2h - ~18h) *  7	 448   8388608 ms (~2h)   67108864 ms -  536870911 ms (~18h - ~6d) *  8    512  67108864 ms (~18h) 536870912 ms - 4294967288 ms (~6d - ~49d) * * HZ  100 * Level Offset  Granularity            Range *  0	   0         10 ms               0 ms -        630 ms *  1	  64         80 ms             640 ms -       5110 ms (640ms - ~5s) *  2	 128        640 ms            5120 ms -      40950 ms (~5s - ~40s) *  3	 192       5120 ms (~5s)     40960 ms -     327670 ms (~40s - ~5m) *  4	 256      40960 ms (~40s)   327680 ms -    2621430 ms (~5m - ~43m) *  5	 320     327680 ms (~5m)   2621440 ms -   20971510 ms (~43m - ~5h) *  6	 384    2621440 ms (~43m) 20971520 ms -  167772150 ms (~5h - ~1d) *  7	 448   20971520 ms (~5h) 167772160 ms - 1342177270 ms (~1d - ~15d) */ /* Clock divisor for the next level */#define LVL_CLK_SHIFT	3#define LVL_CLK_DIV	(1UL << LVL_CLK_SHIFT)#define LVL_CLK_MASK	(LVL_CLK_DIV - 1)#define LVL_SHIFT(n)	((n) * LVL_CLK_SHIFT)#define LVL_GRAN(n)	(1UL << LVL_SHIFT(n)) /* * The time start value for each level to select the bucket at enqueue * time. We start from the last possible delta of the previous level * so that we can later add an extra LVL_GRAN(n) to n (see calc_index()). */#define LVL_START(n)	((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT)) /* Size of each clock level */#define LVL_BITS	6#define LVL_SIZE	(1UL << LVL_BITS)#define LVL_MASK	(LVL_SIZE - 1)#define LVL_OFFS(n)	((n) * LVL_SIZE) /* Level depth */#if HZ > 100# define LVL_DEPTH	9# else# define LVL_DEPTH	8#endif /* The cutoff (max. capacity of the wheel) */#define WHEEL_TIMEOUT_CUTOFF	(LVL_START(LVL_DEPTH))#define WHEEL_TIMEOUT_MAX	(WHEEL_TIMEOUT_CUTOFF - LVL_GRAN(LVL_DEPTH - 1)) /* * The resulting wheel size. If NOHZ is configured we allocate two * wheels so we have a separate storage for the deferrable timers. */#define WHEEL_SIZE	(LVL_SIZE * LVL_DEPTH) #ifdef CONFIG_NO_HZ_COMMON# define NR_BASES	2# define BASE_STD	0# define BASE_DEF	1#else# define NR_BASES	1# define BASE_STD	0# define BASE_DEF	0#endif struct timer_base {	raw_spinlock_t		lock;	struct timer_list	*running_timer;#ifdef CONFIG_PREEMPT_RT	spinlock_t		expiry_lock;	atomic_t		timer_waiters;#endif	unsigned long		clk;	unsigned long		next_expiry;	unsigned int		cpu;	bool			next_expiry_recalc;	bool			is_idle;	bool			timers_pending;	DECLARE_BITMAP(pending_map, WHEEL_SIZE);	struct hlist_head	vectors[WHEEL_SIZE];} ____cacheline_aligned; static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]); #ifdef CONFIG_NO_HZ_COMMON static DEFINE_STATIC_KEY_FALSE(timers_nohz_active);static DEFINE_MUTEX(timer_keys_mutex); static void timer_update_keys(struct work_struct *work);static DECLARE_WORK(timer_update_work, timer_update_keys); #ifdef CONFIG_SMPunsigned int sysctl_timer_migration = 1; DEFINE_STATIC_KEY_FALSE(timers_migration_enabled); static void timers_update_migration(void){	if (sysctl_timer_migration && tick_nohz_active)		static_branch_enable(&timers_migration_enabled);	else		static_branch_disable(&timers_migration_enabled);}#elsestatic inline void timers_update_migration(void) { }#endif /* !CONFIG_SMP */ static void timer_update_keys(struct work_struct *work){	mutex_lock(&timer_keys_mutex);	timers_update_migration();	static_branch_enable(&timers_nohz_active);	mutex_unlock(&timer_keys_mutex);} void timers_update_nohz(void){	schedule_work(&timer_update_work);} int timer_migration_handler(struct ctl_table *table, int write,			    void *buffer, size_t *lenp, loff_t *ppos){	int ret; 	mutex_lock(&timer_keys_mutex);	ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);	if (!ret && write)		timers_update_migration();	mutex_unlock(&timer_keys_mutex);	return ret;} static inline bool is_timers_nohz_active(void){	return static_branch_unlikely(&timers_nohz_active);}#elsestatic inline bool is_timers_nohz_active(void) { return false; }#endif /* NO_HZ_COMMON */ static unsigned long round_jiffies_common(unsigned long j, int cpu,		bool force_up){	int rem;	unsigned long original = j; 	/*	 * We don't want all cpus firing their timers at once hitting the	 * same lock or cachelines, so we skew each extra cpu with an extra	 * 3 jiffies. This 3 jiffies came originally from the mm/ code which	 * already did this.	 * The skew is done by adding 3*cpunr, then round, then subtract this	 * extra offset again.	 */	j += cpu * 3; 	rem = j % HZ; 	/*	 * If the target jiffie is just after a whole second (which can happen	 * due to delays of the timer irq, long irq off times etc etc) then	 * we should round down to the whole second, not up. Use 1/4th second	 * as cutoff for this rounding as an extreme upper bound for this.	 * But never round down if @force_up is set.	 */	if (rem < HZ/4 && !force_up) /* round down */		j = j - rem;	else /* round up */		j = j - rem + HZ; 	/* now that we have rounded, subtract the extra skew again */	j -= cpu * 3; 	/*	 * Make sure j is still in the future. Otherwise return the	 * unmodified value.	 */	return time_is_after_jiffies(j) ? j : original;} /** * __round_jiffies - function to round jiffies to a full second * @j: the time in (absolute) jiffies that should be rounded * @cpu: the processor number on which the timeout will happen * * __round_jiffies() rounds an absolute time in the future (in jiffies) * up or down to (approximately) full seconds. This is useful for timers * for which the exact time they fire does not matter too much, as long as * they fire approximately every X seconds. * * By rounding these timers to whole seconds, all such timers will fire * at the same time, rather than at various times spread out. The goal * of this is to have the CPU wake up less, which saves power. * * The exact rounding is skewed for each processor to avoid all * processors firing at the exact same time, which could lead * to lock contention or spurious cache line bouncing. * * The return value is the rounded version of the @j parameter. */unsigned long __round_jiffies(unsigned long j, int cpu){	return round_jiffies_common(j, cpu, false);}EXPORT_SYMBOL_GPL(__round_jiffies); /** * __round_jiffies_relative - function to round jiffies to a full second * @j: the time in (relative) jiffies that should be rounded * @cpu: the processor number on which the timeout will happen * * __round_jiffies_relative() rounds a time delta  in the future (in jiffies) * up or down to (approximately) full seconds. This is useful for timers * for which the exact time they fire does not matter too much, as long as * they fire approximately every X seconds. * * By rounding these timers to whole seconds, all such timers will fire * at the same time, rather than at various times spread out. The goal * of this is to have the CPU wake up less, which saves power. * * The exact rounding is skewed for each processor to avoid all * processors firing at the exact same time, which could lead * to lock contention or spurious cache line bouncing. * * The return value is the rounded version of the @j parameter. */unsigned long __round_jiffies_relative(unsigned long j, int cpu){	unsigned long j0 = jiffies; 	/* Use j0 because jiffies might change while we run */	return round_jiffies_common(j + j0, cpu, false) - j0;}EXPORT_SYMBOL_GPL(__round_jiffies_relative); /** * round_jiffies - function to round jiffies to a full second * @j: the time in (absolute) jiffies that should be rounded * * round_jiffies() rounds an absolute time in the future (in jiffies) * up or down to (approximately) full seconds. This is useful for timers * for which the exact time they fire does not matter too much, as long as * they fire approximately every X seconds. * * By rounding these timers to whole seconds, all such timers will fire * at the same time, rather than at various times spread out. The goal * of this is to have the CPU wake up less, which saves power. * * The return value is the rounded version of the @j parameter. */unsigned long round_jiffies(unsigned long j){	return round_jiffies_common(j, raw_smp_processor_id(), false);}EXPORT_SYMBOL_GPL(round_jiffies); /** * round_jiffies_relative - function to round jiffies to a full second * @j: the time in (relative) jiffies that should be rounded * * round_jiffies_relative() rounds a time delta  in the future (in jiffies) * up or down to (approximately) full seconds. This is useful for timers * for which the exact time they fire does not matter too much, as long as * they fire approximately every X seconds. * * By rounding these timers to whole seconds, all such timers will fire * at the same time, rather than at various times spread out. The goal * of this is to have the CPU wake up less, which saves power. * * The return value is the rounded version of the @j parameter. */unsigned long round_jiffies_relative(unsigned long j){	return __round_jiffies_relative(j, raw_smp_processor_id());}EXPORT_SYMBOL_GPL(round_jiffies_relative); /** * __round_jiffies_up - function to round jiffies up to a full second * @j: the time in (absolute) jiffies that should be rounded * @cpu: the processor number on which the timeout will happen * * This is the same as __round_jiffies() except that it will never * round down.  This is useful for timeouts for which the exact time * of firing does not matter too much, as long as they don't fire too * early. */unsigned long __round_jiffies_up(unsigned long j, int cpu){	return round_jiffies_common(j, cpu, true);}EXPORT_SYMBOL_GPL(__round_jiffies_up); /** * __round_jiffies_up_relative - function to round jiffies up to a full second * @j: the time in (relative) jiffies that should be rounded * @cpu: the processor number on which the timeout will happen * * This is the same as __round_jiffies_relative() except that it will never * round down.  This is useful for timeouts for which the exact time * of firing does not matter too much, as long as they don't fire too * early. */unsigned long __round_jiffies_up_relative(unsigned long j, int cpu){	unsigned long j0 = jiffies; 	/* Use j0 because jiffies might change while we run */	return round_jiffies_common(j + j0, cpu, true) - j0;}EXPORT_SYMBOL_GPL(__round_jiffies_up_relative); /** * round_jiffies_up - function to round jiffies up to a full second * @j: the time in (absolute) jiffies that should be rounded * * This is the same as round_jiffies() except that it will never * round down.  This is useful for timeouts for which the exact time * of firing does not matter too much, as long as they don't fire too * early. */unsigned long round_jiffies_up(unsigned long j){	return round_jiffies_common(j, raw_smp_processor_id(), true);}EXPORT_SYMBOL_GPL(round_jiffies_up); /** * round_jiffies_up_relative - function to round jiffies up to a full second * @j: the time in (relative) jiffies that should be rounded * * This is the same as round_jiffies_relative() except that it will never * round down.  This is useful for timeouts for which the exact time * of firing does not matter too much, as long as they don't fire too * early. */unsigned long round_jiffies_up_relative(unsigned long j){	return __round_jiffies_up_relative(j, raw_smp_processor_id());}EXPORT_SYMBOL_GPL(round_jiffies_up_relative);  static inline unsigned int timer_get_idx(struct timer_list *timer){	return (timer->flags & TIMER_ARRAYMASK) >> TIMER_ARRAYSHIFT;} static inline void timer_set_idx(struct timer_list *timer, unsigned int idx){	timer->flags = (timer->flags & ~TIMER_ARRAYMASK) |			idx << TIMER_ARRAYSHIFT;} /* * Helper function to calculate the array index for a given expiry * time. */static inline unsigned calc_index(unsigned long expires, unsigned lvl,				  unsigned long *bucket_expiry){ 	/*	 * The timer wheel has to guarantee that a timer does not fire	 * early. Early expiry can happen due to:	 * - Timer is armed at the edge of a tick

Lines 1–500 of 2077. Load more