From 1a4729ecafc239f922d0c758bab7be0038714e88 Mon Sep 17 00:00:00 2001 From: Anna-Maria Behnsen Date: Tue, 23 Jan 2024 17:46:55 +0100 Subject: hrtimers: Move hrtimer base related definitions into hrtimer_defs.h hrtimer base related struct definitions are part of hrtimers.h as it is required there. With this, also the struct documentation which is for core code internal use, is exposed into the general api. To prevent this, move all core internal definitions and the related includes into hrtimer_defs.h. Signed-off-by: Anna-Maria Behnsen Signed-off-by: Thomas Gleixner Link: https://lore.kernel.org/r/20240123164702.55612-2-anna-maria@linutronix.de --- include/linux/hrtimer.h | 103 ------------------------------------------- include/linux/hrtimer_defs.h | 102 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 102 insertions(+), 103 deletions(-) (limited to 'include/linux') diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h index 87e3bedf8eb0..792a0ac75378 100644 --- a/include/linux/hrtimer.h +++ b/include/linux/hrtimer.h @@ -18,12 +18,8 @@ #include #include #include -#include #include -struct hrtimer_clock_base; -struct hrtimer_cpu_base; - /* * Mode arguments of xxx_hrtimer functions: * @@ -98,105 +94,6 @@ struct hrtimer_sleeper { struct task_struct *task; }; -#ifdef CONFIG_64BIT -# define __hrtimer_clock_base_align ____cacheline_aligned -#else -# define __hrtimer_clock_base_align -#endif - -/** - * struct hrtimer_clock_base - the timer base for a specific clock - * @cpu_base: per cpu clock base - * @index: clock type index for per_cpu support when moving a - * timer to a base on another cpu. - * @clockid: clock id for per_cpu support - * @seq: seqcount around __run_hrtimer - * @running: pointer to the currently running hrtimer - * @active: red black tree root node for the active timers - * @get_time: function to retrieve the current time of the clock - * @offset: offset of this clock to the monotonic base - */ -struct hrtimer_clock_base { - struct hrtimer_cpu_base *cpu_base; - unsigned int index; - clockid_t clockid; - seqcount_raw_spinlock_t seq; - struct hrtimer *running; - struct timerqueue_head active; - ktime_t (*get_time)(void); - ktime_t offset; -} __hrtimer_clock_base_align; - -enum hrtimer_base_type { - HRTIMER_BASE_MONOTONIC, - HRTIMER_BASE_REALTIME, - HRTIMER_BASE_BOOTTIME, - HRTIMER_BASE_TAI, - HRTIMER_BASE_MONOTONIC_SOFT, - HRTIMER_BASE_REALTIME_SOFT, - HRTIMER_BASE_BOOTTIME_SOFT, - HRTIMER_BASE_TAI_SOFT, - HRTIMER_MAX_CLOCK_BASES, -}; - -/** - * struct hrtimer_cpu_base - the per cpu clock bases - * @lock: lock protecting the base and associated clock bases - * and timers - * @cpu: cpu number - * @active_bases: Bitfield to mark bases with active timers - * @clock_was_set_seq: Sequence counter of clock was set events - * @hres_active: State of high resolution mode - * @in_hrtirq: hrtimer_interrupt() is currently executing - * @hang_detected: The last hrtimer interrupt detected a hang - * @softirq_activated: displays, if the softirq is raised - update of softirq - * related settings is not required then. - * @nr_events: Total number of hrtimer interrupt events - * @nr_retries: Total number of hrtimer interrupt retries - * @nr_hangs: Total number of hrtimer interrupt hangs - * @max_hang_time: Maximum time spent in hrtimer_interrupt - * @softirq_expiry_lock: Lock which is taken while softirq based hrtimer are - * expired - * @timer_waiters: A hrtimer_cancel() invocation waits for the timer - * callback to finish. - * @expires_next: absolute time of the next event, is required for remote - * hrtimer enqueue; it is the total first expiry time (hard - * and soft hrtimer are taken into account) - * @next_timer: Pointer to the first expiring timer - * @softirq_expires_next: Time to check, if soft queues needs also to be expired - * @softirq_next_timer: Pointer to the first expiring softirq based timer - * @clock_base: array of clock bases for this cpu - * - * Note: next_timer is just an optimization for __remove_hrtimer(). - * Do not dereference the pointer because it is not reliable on - * cross cpu removals. - */ -struct hrtimer_cpu_base { - raw_spinlock_t lock; - unsigned int cpu; - unsigned int active_bases; - unsigned int clock_was_set_seq; - unsigned int hres_active : 1, - in_hrtirq : 1, - hang_detected : 1, - softirq_activated : 1; -#ifdef CONFIG_HIGH_RES_TIMERS - unsigned int nr_events; - unsigned short nr_retries; - unsigned short nr_hangs; - unsigned int max_hang_time; -#endif -#ifdef CONFIG_PREEMPT_RT - spinlock_t softirq_expiry_lock; - atomic_t timer_waiters; -#endif - ktime_t expires_next; - struct hrtimer *next_timer; - ktime_t softirq_expires_next; - struct hrtimer *softirq_next_timer; - struct hrtimer_clock_base clock_base[HRTIMER_MAX_CLOCK_BASES]; -} ____cacheline_aligned; - static inline void hrtimer_set_expires(struct hrtimer *timer, ktime_t time) { timer->node.expires = time; diff --git a/include/linux/hrtimer_defs.h b/include/linux/hrtimer_defs.h index 2d3e3c5fb946..b12869dba59a 100644 --- a/include/linux/hrtimer_defs.h +++ b/include/linux/hrtimer_defs.h @@ -3,6 +3,8 @@ #define _LINUX_HRTIMER_DEFS_H #include +#include +#include #ifdef CONFIG_HIGH_RES_TIMERS @@ -24,4 +26,104 @@ #endif +#ifdef CONFIG_64BIT +# define __hrtimer_clock_base_align ____cacheline_aligned +#else +# define __hrtimer_clock_base_align +#endif + +/** + * struct hrtimer_clock_base - the timer base for a specific clock + * @cpu_base: per cpu clock base + * @index: clock type index for per_cpu support when moving a + * timer to a base on another cpu. + * @clockid: clock id for per_cpu support + * @seq: seqcount around __run_hrtimer + * @running: pointer to the currently running hrtimer + * @active: red black tree root node for the active timers + * @get_time: function to retrieve the current time of the clock + * @offset: offset of this clock to the monotonic base + */ +struct hrtimer_clock_base { + struct hrtimer_cpu_base *cpu_base; + unsigned int index; + clockid_t clockid; + seqcount_raw_spinlock_t seq; + struct hrtimer *running; + struct timerqueue_head active; + ktime_t (*get_time)(void); + ktime_t offset; +} __hrtimer_clock_base_align; + +enum hrtimer_base_type { + HRTIMER_BASE_MONOTONIC, + HRTIMER_BASE_REALTIME, + HRTIMER_BASE_BOOTTIME, + HRTIMER_BASE_TAI, + HRTIMER_BASE_MONOTONIC_SOFT, + HRTIMER_BASE_REALTIME_SOFT, + HRTIMER_BASE_BOOTTIME_SOFT, + HRTIMER_BASE_TAI_SOFT, + HRTIMER_MAX_CLOCK_BASES, +}; + +/** + * struct hrtimer_cpu_base - the per cpu clock bases + * @lock: lock protecting the base and associated clock bases + * and timers + * @cpu: cpu number + * @active_bases: Bitfield to mark bases with active timers + * @clock_was_set_seq: Sequence counter of clock was set events + * @hres_active: State of high resolution mode + * @in_hrtirq: hrtimer_interrupt() is currently executing + * @hang_detected: The last hrtimer interrupt detected a hang + * @softirq_activated: displays, if the softirq is raised - update of softirq + * related settings is not required then. + * @nr_events: Total number of hrtimer interrupt events + * @nr_retries: Total number of hrtimer interrupt retries + * @nr_hangs: Total number of hrtimer interrupt hangs + * @max_hang_time: Maximum time spent in hrtimer_interrupt + * @softirq_expiry_lock: Lock which is taken while softirq based hrtimer are + * expired + * @timer_waiters: A hrtimer_cancel() invocation waits for the timer + * callback to finish. + * @expires_next: absolute time of the next event, is required for remote + * hrtimer enqueue; it is the total first expiry time (hard + * and soft hrtimer are taken into account) + * @next_timer: Pointer to the first expiring timer + * @softirq_expires_next: Time to check, if soft queues needs also to be expired + * @softirq_next_timer: Pointer to the first expiring softirq based timer + * @clock_base: array of clock bases for this cpu + * + * Note: next_timer is just an optimization for __remove_hrtimer(). + * Do not dereference the pointer because it is not reliable on + * cross cpu removals. + */ +struct hrtimer_cpu_base { + raw_spinlock_t lock; + unsigned int cpu; + unsigned int active_bases; + unsigned int clock_was_set_seq; + unsigned int hres_active : 1, + in_hrtirq : 1, + hang_detected : 1, + softirq_activated : 1; +#ifdef CONFIG_HIGH_RES_TIMERS + unsigned int nr_events; + unsigned short nr_retries; + unsigned short nr_hangs; + unsigned int max_hang_time; +#endif +#ifdef CONFIG_PREEMPT_RT + spinlock_t softirq_expiry_lock; + atomic_t timer_waiters; +#endif + ktime_t expires_next; + struct hrtimer *next_timer; + ktime_t softirq_expires_next; + struct hrtimer *softirq_next_timer; + struct hrtimer_clock_base clock_base[HRTIMER_MAX_CLOCK_BASES]; +} ____cacheline_aligned; + + #endif -- cgit v1.3.1 From ca2768bbf5c48d8c048877dfbceafcebc3f06fa6 Mon Sep 17 00:00:00 2001 From: Anna-Maria Behnsen Date: Tue, 23 Jan 2024 17:46:56 +0100 Subject: hrtimers: Update formatting of documentation Documentation of functions lacks the annotations which are used by kernel-doc and *.rst to make appearance in rendered documents more user-friendly. Use those annotations to improve user-friendliness. While at it prevent duplication of comments and use a reference instead. Signed-off-by: Anna-Maria Behnsen Signed-off-by: Thomas Gleixner Link: https://lore.kernel.org/r/20240123164702.55612-3-anna-maria@linutronix.de --- include/linux/hrtimer.h | 14 +++----------- kernel/time/hrtimer.c | 18 ++++++++++-------- 2 files changed, 13 insertions(+), 19 deletions(-) (limited to 'include/linux') diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h index 792a0ac75378..aa1e65ccb615 100644 --- a/include/linux/hrtimer.h +++ b/include/linux/hrtimer.h @@ -342,20 +342,12 @@ extern u64 hrtimer_forward(struct hrtimer *timer, ktime_t now, ktime_t interval); /** - * hrtimer_forward_now - forward the timer expiry so it expires after now + * hrtimer_forward_now() - forward the timer expiry so it expires after now * @timer: hrtimer to forward * @interval: the interval to forward * - * Forward the timer expiry so it will expire after the current time - * of the hrtimer clock base. Returns the number of overruns. - * - * Can be safely called from the callback function of @timer. If - * called from other contexts @timer must neither be enqueued nor - * running the callback and the caller needs to take care of - * serialization. - * - * Note: This only updates the timer expiry value and does not requeue - * the timer. + * It is a variant of hrtimer_forward(). The timer will expire after the current + * time of the hrtimer clock base. See hrtimer_forward() for details. */ static inline u64 hrtimer_forward_now(struct hrtimer *timer, ktime_t interval) diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c index 760793998cdd..4c8dd633ab4a 100644 --- a/kernel/time/hrtimer.c +++ b/kernel/time/hrtimer.c @@ -1021,21 +1021,23 @@ void unlock_hrtimer_base(const struct hrtimer *timer, unsigned long *flags) } /** - * hrtimer_forward - forward the timer expiry + * hrtimer_forward() - forward the timer expiry * @timer: hrtimer to forward * @now: forward past this time * @interval: the interval to forward * * Forward the timer expiry so it will expire in the future. - * Returns the number of overruns. * - * Can be safely called from the callback function of @timer. If - * called from other contexts @timer must neither be enqueued nor - * running the callback and the caller needs to take care of - * serialization. + * .. note:: + * This only updates the timer expiry value and does not requeue the timer. * - * Note: This only updates the timer expiry value and does not requeue - * the timer. + * There is also a variant of the function hrtimer_forward_now(). + * + * Context: Can be safely called from the callback function of @timer. If called + * from other contexts @timer must neither be enqueued nor running the + * callback and the caller needs to take care of serialization. + * + * Return: The number of overruns are returned. */ u64 hrtimer_forward(struct hrtimer *timer, ktime_t now, ktime_t interval) { -- cgit v1.3.1 From c92a7eb6c642812fb08851e580973c3b83e0227c Mon Sep 17 00:00:00 2001 From: Anna-Maria Behnsen Date: Tue, 23 Jan 2024 17:46:59 +0100 Subject: jiffies: Transform comment about time_* functions into DOC block This general note about time_* functions is also useful to be available in kernel documentation. Therefore transform it into a kernel-doc DOC block with proper formatting. Signed-off-by: Anna-Maria Behnsen Signed-off-by: Thomas Gleixner Link: https://lore.kernel.org/r/20240123164702.55612-6-anna-maria@linutronix.de --- include/linux/jiffies.h | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'include/linux') diff --git a/include/linux/jiffies.h b/include/linux/jiffies.h index e0ae2a43e0eb..d9f1435a5a13 100644 --- a/include/linux/jiffies.h +++ b/include/linux/jiffies.h @@ -102,12 +102,15 @@ static inline u64 get_jiffies_64(void) } #endif -/* - * These inlines deal with timer wrapping correctly. You are - * strongly encouraged to use them: - * 1. Because people otherwise forget - * 2. Because if the timer wrap changes in future you won't have to - * alter your driver code. +/** + * DOC: General information about time_* inlines + * + * These inlines deal with timer wrapping correctly. You are strongly encouraged + * to use them: + * + * #. Because people otherwise forget + * #. Because if the timer wrap changes in future you won't have to alter your + * driver code. */ /** -- cgit v1.3.1 From 2ed08e4bc53298db3f87b528cd804cb0cce066a9 Mon Sep 17 00:00:00 2001 From: Feng Tang Date: Wed, 21 Feb 2024 14:08:59 +0800 Subject: clocksource: Scale the watchdog read retries automatically On a 8-socket server the TSC is wrongly marked as 'unstable' and disabled during boot time on about one out of 120 boot attempts: clocksource: timekeeping watchdog on CPU227: wd-tsc-wd excessive read-back delay of 153560ns vs. limit of 125000ns, wd-wd read-back delay only 11440ns, attempt 3, marking tsc unstable tsc: Marking TSC unstable due to clocksource watchdog TSC found unstable after boot, most likely due to broken BIOS. Use 'tsc=unstable'. sched_clock: Marking unstable (119294969739, 159204297)<-(125446229205, -5992055152) clocksource: Checking clocksource tsc synchronization from CPU 319 to CPUs 0,99,136,180,210,542,601,896. clocksource: Switched to clocksource hpet The reason is that for platform with a large number of CPUs, there are sporadic big or huge read latencies while reading the watchog/clocksource during boot or when system is under stress work load, and the frequency and maximum value of the latency goes up with the number of online CPUs. The cCurrent code already has logic to detect and filter such high latency case by reading the watchdog twice and checking the two deltas. Due to the randomness of the latency, there is a low probabilty that the first delta (latency) is big, but the second delta is small and looks valid. The watchdog code retries the readouts by default twice, which is not necessarily sufficient for systems with a large number of CPUs. There is a command line parameter 'max_cswd_read_retries' which allows to increase the number of retries, but that's not user friendly as it needs to be tweaked per system. As the number of required retries is proportional to the number of online CPUs, this parameter can be calculated at runtime. Scale and enlarge the number of retries according to the number of online CPUs and remove the command line parameter completely. [ tglx: Massaged change log and comments ] Signed-off-by: Feng Tang Signed-off-by: Thomas Gleixner Tested-by: Jin Wang Tested-by: Paul E. McKenney Reviewed-by: Waiman Long Reviewed-by: Paul E. McKenney Link: https://lore.kernel.org/r/20240221060859.1027450-1-feng.tang@intel.com --- Documentation/admin-guide/kernel-parameters.txt | 6 ------ include/linux/clocksource.h | 14 +++++++++++++- kernel/time/clocksource-wdtest.c | 13 +++++++------ kernel/time/clocksource.c | 10 ++++------ tools/testing/selftests/rcutorture/bin/torture.sh | 2 +- 5 files changed, 25 insertions(+), 20 deletions(-) (limited to 'include/linux') diff --git a/Documentation/admin-guide/kernel-parameters.txt b/Documentation/admin-guide/kernel-parameters.txt index 31b3a25680d0..763e96dcf8b1 100644 --- a/Documentation/admin-guide/kernel-parameters.txt +++ b/Documentation/admin-guide/kernel-parameters.txt @@ -679,12 +679,6 @@ loops can be debugged more effectively on production systems. - clocksource.max_cswd_read_retries= [KNL] - Number of clocksource_watchdog() retries due to - external delays before the clock will be marked - unstable. Defaults to two retries, that is, - three attempts to read the clock under test. - clocksource.verify_n_cpus= [KNL] Limit the number of CPUs checked for clocksources marked with CLOCK_SOURCE_VERIFY_PERCPU that diff --git a/include/linux/clocksource.h b/include/linux/clocksource.h index 1d42d4b17327..0ad8b550bb4b 100644 --- a/include/linux/clocksource.h +++ b/include/linux/clocksource.h @@ -291,7 +291,19 @@ static inline void timer_probe(void) {} #define TIMER_ACPI_DECLARE(name, table_id, fn) \ ACPI_DECLARE_PROBE_ENTRY(timer, name, table_id, 0, NULL, 0, fn) -extern ulong max_cswd_read_retries; +static inline unsigned int clocksource_get_max_watchdog_retry(void) +{ + /* + * When system is in the boot phase or under heavy workload, there + * can be random big latencies during the clocksource/watchdog + * read, so allow retries to filter the noise latency. As the + * latency's frequency and maximum value goes up with the number of + * CPUs, scale the number of retries with the number of online + * CPUs. + */ + return (ilog2(num_online_cpus()) / 2) + 1; +} + void clocksource_verify_percpu(struct clocksource *cs); #endif /* _LINUX_CLOCKSOURCE_H */ diff --git a/kernel/time/clocksource-wdtest.c b/kernel/time/clocksource-wdtest.c index df922f49d171..d06185e054ea 100644 --- a/kernel/time/clocksource-wdtest.c +++ b/kernel/time/clocksource-wdtest.c @@ -104,8 +104,8 @@ static void wdtest_ktime_clocksource_reset(void) static int wdtest_func(void *arg) { unsigned long j1, j2; + int i, max_retries; char *s; - int i; schedule_timeout_uninterruptible(holdoff * HZ); @@ -139,18 +139,19 @@ static int wdtest_func(void *arg) WARN_ON_ONCE(time_before(j2, j1 + NSEC_PER_USEC)); /* Verify tsc-like stability with various numbers of errors injected. */ - for (i = 0; i <= max_cswd_read_retries + 1; i++) { - if (i <= 1 && i < max_cswd_read_retries) + max_retries = clocksource_get_max_watchdog_retry(); + for (i = 0; i <= max_retries + 1; i++) { + if (i <= 1 && i < max_retries) s = ""; - else if (i <= max_cswd_read_retries) + else if (i <= max_retries) s = ", expect message"; else s = ", expect clock skew"; - pr_info("--- Watchdog with %dx error injection, %lu retries%s.\n", i, max_cswd_read_retries, s); + pr_info("--- Watchdog with %dx error injection, %d retries%s.\n", i, max_retries, s); WRITE_ONCE(wdtest_ktime_read_ndelays, i); schedule_timeout_uninterruptible(2 * HZ); WARN_ON_ONCE(READ_ONCE(wdtest_ktime_read_ndelays)); - WARN_ON_ONCE((i <= max_cswd_read_retries) != + WARN_ON_ONCE((i <= max_retries) != !(clocksource_wdtest_ktime.flags & CLOCK_SOURCE_UNSTABLE)); wdtest_ktime_clocksource_reset(); } diff --git a/kernel/time/clocksource.c b/kernel/time/clocksource.c index 4ef06651ad07..e5b260aa0e02 100644 --- a/kernel/time/clocksource.c +++ b/kernel/time/clocksource.c @@ -210,9 +210,6 @@ void clocksource_mark_unstable(struct clocksource *cs) spin_unlock_irqrestore(&watchdog_lock, flags); } -ulong max_cswd_read_retries = 2; -module_param(max_cswd_read_retries, ulong, 0644); -EXPORT_SYMBOL_GPL(max_cswd_read_retries); static int verify_n_cpus = 8; module_param(verify_n_cpus, int, 0644); @@ -224,11 +221,12 @@ enum wd_read_status { static enum wd_read_status cs_watchdog_read(struct clocksource *cs, u64 *csnow, u64 *wdnow) { - unsigned int nretries; + unsigned int nretries, max_retries; u64 wd_end, wd_end2, wd_delta; int64_t wd_delay, wd_seq_delay; - for (nretries = 0; nretries <= max_cswd_read_retries; nretries++) { + max_retries = clocksource_get_max_watchdog_retry(); + for (nretries = 0; nretries <= max_retries; nretries++) { local_irq_disable(); *wdnow = watchdog->read(watchdog); *csnow = cs->read(cs); @@ -240,7 +238,7 @@ static enum wd_read_status cs_watchdog_read(struct clocksource *cs, u64 *csnow, wd_delay = clocksource_cyc2ns(wd_delta, watchdog->mult, watchdog->shift); if (wd_delay <= WATCHDOG_MAX_SKEW) { - if (nretries > 1 || nretries >= max_cswd_read_retries) { + if (nretries > 1 || nretries >= max_retries) { pr_warn("timekeeping watchdog on CPU%d: %s retried %d times before success\n", smp_processor_id(), watchdog->name, nretries); } diff --git a/tools/testing/selftests/rcutorture/bin/torture.sh b/tools/testing/selftests/rcutorture/bin/torture.sh index d5a0d8a33c27..bbac5f4b03d0 100755 --- a/tools/testing/selftests/rcutorture/bin/torture.sh +++ b/tools/testing/selftests/rcutorture/bin/torture.sh @@ -567,7 +567,7 @@ then torture_bootargs="rcupdate.rcu_cpu_stall_suppress_at_boot=1 torture.disable_onoff_at_boot rcupdate.rcu_task_stall_timeout=30000 tsc=watchdog" torture_set "clocksourcewd-1" tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 45s --configs TREE03 --kconfig "CONFIG_TEST_CLOCKSOURCE_WATCHDOG=y" --trust-make - torture_bootargs="rcupdate.rcu_cpu_stall_suppress_at_boot=1 torture.disable_onoff_at_boot rcupdate.rcu_task_stall_timeout=30000 clocksource.max_cswd_read_retries=1 tsc=watchdog" + torture_bootargs="rcupdate.rcu_cpu_stall_suppress_at_boot=1 torture.disable_onoff_at_boot rcupdate.rcu_task_stall_timeout=30000 tsc=watchdog" torture_set "clocksourcewd-2" tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 45s --configs TREE03 --kconfig "CONFIG_TEST_CLOCKSOURCE_WATCHDOG=y" --trust-make # In case our work is already done... -- cgit v1.3.1 From 8e7e247f64a1e0fee430aba28d9108f7598eb237 Mon Sep 17 00:00:00 2001 From: Anna-Maria Behnsen Date: Wed, 21 Feb 2024 10:05:33 +0100 Subject: timers: Introduce add_timer() variants which modify timer flags A timer might be used as a pinned timer (using add_timer_on()) and later on as non-pinned timer using add_timer(). When the "NOHZ timer pull at expiry model" is in place, the TIMER_PINNED flag is required to be used whenever a timer needs to expire on a dedicated CPU. Otherwise the flag must not be set if expiration on a dedicated CPU is not required. add_timer_on()'s behavior will be changed during the preparation patches for the "NOHZ timer pull at expiry model" to unconditionally set the TIMER_PINNED flag. To be able to clear/ set the flag when queueing a timer, two variants of add_timer() are introduced. This is a preparatory step and has no functional change. Signed-off-by: Anna-Maria Behnsen Signed-off-by: Thomas Gleixner Reviewed-by: Frederic Weisbecker Link: https://lore.kernel.org/r/20240221090548.36600-6-anna-maria@linutronix.de --- include/linux/timer.h | 2 ++ kernel/time/timer.c | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 36 insertions(+) (limited to 'include/linux') diff --git a/include/linux/timer.h b/include/linux/timer.h index f18a2f1eb79e..2be8be6dd317 100644 --- a/include/linux/timer.h +++ b/include/linux/timer.h @@ -165,6 +165,8 @@ extern int timer_reduce(struct timer_list *timer, unsigned long expires); #define NEXT_TIMER_MAX_DELTA ((1UL << 30) - 1) extern void add_timer(struct timer_list *timer); +extern void add_timer_local(struct timer_list *timer); +extern void add_timer_global(struct timer_list *timer); extern int try_to_del_timer_sync(struct timer_list *timer); extern int timer_delete_sync(struct timer_list *timer); diff --git a/kernel/time/timer.c b/kernel/time/timer.c index 74cfe21f8fd9..bef8cb8e7266 100644 --- a/kernel/time/timer.c +++ b/kernel/time/timer.c @@ -1290,6 +1290,40 @@ void add_timer(struct timer_list *timer) } EXPORT_SYMBOL(add_timer); +/** + * add_timer_local() - Start a timer on the local CPU + * @timer: The timer to be started + * + * Same as add_timer() except that the timer flag TIMER_PINNED is set. + * + * See add_timer() for further details. + */ +void add_timer_local(struct timer_list *timer) +{ + if (WARN_ON_ONCE(timer_pending(timer))) + return; + timer->flags |= TIMER_PINNED; + __mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING); +} +EXPORT_SYMBOL(add_timer_local); + +/** + * add_timer_global() - Start a timer without TIMER_PINNED flag set + * @timer: The timer to be started + * + * Same as add_timer() except that the timer flag TIMER_PINNED is unset. + * + * See add_timer() for further details. + */ +void add_timer_global(struct timer_list *timer) +{ + if (WARN_ON_ONCE(timer_pending(timer))) + return; + timer->flags &= ~TIMER_PINNED; + __mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING); +} +EXPORT_SYMBOL(add_timer_global); + /** * add_timer_on - Start a timer on a particular CPU * @timer: The timer to be started -- cgit v1.3.1 From 7ee988770326fca440472200c3eb58935fe712f6 Mon Sep 17 00:00:00 2001 From: Anna-Maria Behnsen Date: Thu, 22 Feb 2024 11:37:10 +0100 Subject: timers: Implement the hierarchical pull model Placing timers at enqueue time on a target CPU based on dubious heuristics does not make any sense: 1) Most timer wheel timers are canceled or rearmed before they expire. 2) The heuristics to predict which CPU will be busy when the timer expires are wrong by definition. So placing the timers at enqueue wastes precious cycles. The proper solution to this problem is to always queue the timers on the local CPU and allow the non pinned timers to be pulled onto a busy CPU at expiry time. Therefore split the timer storage into local pinned and global timers: Local pinned timers are always expired on the CPU on which they have been queued. Global timers can be expired on any CPU. As long as a CPU is busy it expires both local and global timers. When a CPU goes idle it arms for the first expiring local timer. If the first expiring pinned (local) timer is before the first expiring movable timer, then no action is required because the CPU will wake up before the first movable timer expires. If the first expiring movable timer is before the first expiring pinned (local) timer, then this timer is queued into an idle timerqueue and eventually expired by another active CPU. To avoid global locking the timerqueues are implemented as a hierarchy. The lowest level of the hierarchy holds the CPUs. The CPUs are associated to groups of 8, which are separated per node. If more than one CPU group exist, then a second level in the hierarchy collects the groups. Depending on the size of the system more than 2 levels are required. Each group has a "migrator" which checks the timerqueue during the tick for remote expirable timers. If the last CPU in a group goes idle it reports the first expiring event in the group up to the next group(s) in the hierarchy. If the last CPU goes idle it arms its timer for the first system wide expiring timer to ensure that no timer event is missed. Signed-off-by: Anna-Maria Behnsen Signed-off-by: Thomas Gleixner Reviewed-by: Frederic Weisbecker Link: https://lore.kernel.org/r/20240222103710.32582-1-anna-maria@linutronix.de --- include/linux/cpuhotplug.h | 1 + kernel/time/Makefile | 3 + kernel/time/tick-internal.h | 1 + kernel/time/timer.c | 113 ++- kernel/time/timer_migration.c | 1761 +++++++++++++++++++++++++++++++++++++++++ kernel/time/timer_migration.h | 140 ++++ 6 files changed, 2011 insertions(+), 8 deletions(-) create mode 100644 kernel/time/timer_migration.c create mode 100644 kernel/time/timer_migration.h (limited to 'include/linux') diff --git a/include/linux/cpuhotplug.h b/include/linux/cpuhotplug.h index 172d0a743e5d..7651904c6db5 100644 --- a/include/linux/cpuhotplug.h +++ b/include/linux/cpuhotplug.h @@ -231,6 +231,7 @@ enum cpuhp_state { CPUHP_AP_PERF_POWERPC_HV_24x7_ONLINE, CPUHP_AP_PERF_POWERPC_HV_GPCI_ONLINE, CPUHP_AP_PERF_CSKY_ONLINE, + CPUHP_AP_TMIGR_ONLINE, CPUHP_AP_WATCHDOG_ONLINE, CPUHP_AP_WORKQUEUE_ONLINE, CPUHP_AP_RANDOM_ONLINE, diff --git a/kernel/time/Makefile b/kernel/time/Makefile index 7e875e63ff3b..4af2a264a160 100644 --- a/kernel/time/Makefile +++ b/kernel/time/Makefile @@ -17,6 +17,9 @@ endif obj-$(CONFIG_GENERIC_SCHED_CLOCK) += sched_clock.o obj-$(CONFIG_TICK_ONESHOT) += tick-oneshot.o tick-sched.o obj-$(CONFIG_LEGACY_TIMER_TICK) += tick-legacy.o +ifeq ($(CONFIG_SMP),y) + obj-$(CONFIG_NO_HZ_COMMON) += timer_migration.o +endif obj-$(CONFIG_HAVE_GENERIC_VDSO) += vsyscall.o obj-$(CONFIG_DEBUG_FS) += timekeeping_debug.o obj-$(CONFIG_TEST_UDELAY) += test_udelay.o diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h index 7e3090109e33..a3243c4ac45f 100644 --- a/kernel/time/tick-internal.h +++ b/kernel/time/tick-internal.h @@ -166,6 +166,7 @@ extern void fetch_next_timer_interrupt_remote(unsigned long basej, u64 basem, extern void timer_lock_remote_bases(unsigned int cpu); extern void timer_unlock_remote_bases(unsigned int cpu); extern bool timer_base_is_idle(void); +extern void timer_expire_remote(unsigned int cpu); # endif #else /* CONFIG_NO_HZ_COMMON */ static inline void timers_update_nohz(void) { } diff --git a/kernel/time/timer.c b/kernel/time/timer.c index e02ac4607985..3ed135c8de43 100644 --- a/kernel/time/timer.c +++ b/kernel/time/timer.c @@ -53,6 +53,7 @@ #include #include "tick-internal.h" +#include "timer_migration.h" #define CREATE_TRACE_POINTS #include @@ -2169,6 +2170,64 @@ bool timer_base_is_idle(void) { return __this_cpu_read(timer_bases[BASE_LOCAL].is_idle); } + +static void __run_timer_base(struct timer_base *base); + +/** + * timer_expire_remote() - expire global timers of cpu + * @cpu: Remote CPU + * + * Expire timers of global base of remote CPU. + */ +void timer_expire_remote(unsigned int cpu) +{ + struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu); + + __run_timer_base(base); +} + +static void timer_use_tmigr(unsigned long basej, u64 basem, + unsigned long *nextevt, bool *tick_stop_path, + bool timer_base_idle, struct timer_events *tevt) +{ + u64 next_tmigr; + + if (timer_base_idle) + next_tmigr = tmigr_cpu_new_timer(tevt->global); + else if (tick_stop_path) + next_tmigr = tmigr_cpu_deactivate(tevt->global); + else + next_tmigr = tmigr_quick_check(tevt->global); + + /* + * If the CPU is the last going idle in timer migration hierarchy, make + * sure the CPU will wake up in time to handle remote timers. + * next_tmigr == KTIME_MAX if other CPUs are still active. + */ + if (next_tmigr < tevt->local) { + u64 tmp; + + /* If we missed a tick already, force 0 delta */ + if (next_tmigr < basem) + next_tmigr = basem; + + tmp = div_u64(next_tmigr - basem, TICK_NSEC); + + *nextevt = basej + (unsigned long)tmp; + tevt->local = next_tmigr; + } +} +# else +static void timer_use_tmigr(unsigned long basej, u64 basem, + unsigned long *nextevt, bool *tick_stop_path, + bool timer_base_idle, struct timer_events *tevt) +{ + /* + * Make sure first event is written into tevt->local to not miss a + * timer on !SMP systems. + */ + tevt->local = min_t(u64, tevt->local, tevt->global); +} # endif /* CONFIG_SMP */ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem, @@ -2177,7 +2236,7 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem, struct timer_events tevt = { .local = KTIME_MAX, .global = KTIME_MAX }; struct timer_base *base_local, *base_global; unsigned long nextevt; - u64 expires; + bool idle_is_possible; /* * Pretend that there is no timer pending if the cpu is offline. @@ -2198,6 +2257,22 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem, nextevt = fetch_next_timer_interrupt(basej, basem, base_local, base_global, &tevt); + /* + * If the next event is only one jiffie ahead there is no need to call + * timer migration hierarchy related functions. The value for the next + * global timer in @tevt struct equals then KTIME_MAX. This is also + * true, when the timer base is idle. + * + * The proper timer migration hierarchy function depends on the callsite + * and whether timer base is idle or not. @nextevt will be updated when + * this CPU needs to handle the first timer migration hierarchy + * event. See timer_use_tmigr() for detailed information. + */ + idle_is_possible = time_after(nextevt, basej + 1); + if (idle_is_possible) + timer_use_tmigr(basej, basem, &nextevt, idle, + base_local->is_idle, &tevt); + /* * We have a fresh next event. Check whether we can forward the * base. @@ -2210,7 +2285,10 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem, */ if (idle) { /* - * Bases are idle if the next event is more than a tick away. + * Bases are idle if the next event is more than a tick + * away. Caution: @nextevt could have changed by enqueueing a + * global timer into timer migration hierarchy. Therefore a new + * check is required here. * * If the base is marked idle then any timer add operation must * forward the base clk itself to keep granularity small. This @@ -2223,14 +2301,23 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem, trace_timer_base_idle(true, base_local->cpu); } *idle = base_local->is_idle; + + /* + * When timer base is not set idle, undo the effect of + * tmigr_cpu_deactivate() to prevent inconsitent states - active + * timer base but inactive timer migration hierarchy. + * + * When timer base was already marked idle, nothing will be + * changed here. + */ + if (!base_local->is_idle && idle_is_possible) + tmigr_cpu_activate(); } raw_spin_unlock(&base_global->lock); raw_spin_unlock(&base_local->lock); - expires = min_t(u64, tevt.local, tevt.global); - - return cmp_next_hrtimer_event(basem, expires); + return cmp_next_hrtimer_event(basem, tevt.local); } /** @@ -2238,8 +2325,11 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem, * @basej: base time jiffies * @basem: base time clock monotonic * - * Returns the tick aligned clock monotonic time of the next pending - * timer or KTIME_MAX if no timer is pending. + * Returns the tick aligned clock monotonic time of the next pending timer or + * KTIME_MAX if no timer is pending. If timer of global base was queued into + * timer migration hierarchy, first global timer is not taken into account. If + * it was the last CPU of timer migration hierarchy going idle, first global + * event is taken into account. */ u64 get_next_timer_interrupt(unsigned long basej, u64 basem) { @@ -2281,6 +2371,9 @@ void timer_clear_idle(void) __this_cpu_write(timer_bases[BASE_LOCAL].is_idle, false); __this_cpu_write(timer_bases[BASE_GLOBAL].is_idle, false); trace_timer_base_idle(false, smp_processor_id()); + + /* Activate without holding the timer_base->lock */ + tmigr_cpu_activate(); } #endif @@ -2350,6 +2443,9 @@ static __latent_entropy void run_timer_softirq(struct softirq_action *h) if (IS_ENABLED(CONFIG_NO_HZ_COMMON)) { run_timer_base(BASE_GLOBAL); run_timer_base(BASE_DEF); + + if (is_timers_nohz_active()) + tmigr_handle_remote(); } } @@ -2364,7 +2460,8 @@ static void run_local_timers(void) for (int i = 0; i < NR_BASES; i++, base++) { /* Raise the softirq only if required. */ - if (time_after_eq(jiffies, base->next_expiry)) { + if (time_after_eq(jiffies, base->next_expiry) || + (i == BASE_DEF && tmigr_requires_handle_remote())) { raise_softirq(TIMER_SOFTIRQ); return; } diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c new file mode 100644 index 000000000000..23cb6ea3d44e --- /dev/null +++ b/kernel/time/timer_migration.c @@ -0,0 +1,1761 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Infrastructure for migratable timers + * + * Copyright(C) 2022 linutronix GmbH + */ +#include +#include +#include +#include +#include +#include + +#include "timer_migration.h" +#include "tick-internal.h" + +/* + * The timer migration mechanism is built on a hierarchy of groups. The + * lowest level group contains CPUs, the next level groups of CPU groups + * and so forth. The CPU groups are kept per node so for the normal case + * lock contention won't happen across nodes. Depending on the number of + * CPUs per node even the next level might be kept as groups of CPU groups + * per node and only the levels above cross the node topology. + * + * Example topology for a two node system with 24 CPUs each. + * + * LVL 2 [GRP2:0] + * GRP1:0 = GRP1:M + * + * LVL 1 [GRP1:0] [GRP1:1] + * GRP0:0 - GRP0:2 GRP0:3 - GRP0:5 + * + * LVL 0 [GRP0:0] [GRP0:1] [GRP0:2] [GRP0:3] [GRP0:4] [GRP0:5] + * CPUS 0-7 8-15 16-23 24-31 32-39 40-47 + * + * The groups hold a timer queue of events sorted by expiry time. These + * queues are updated when CPUs go in idle. When they come out of idle + * ignore flag of events is set. + * + * Each group has a designated migrator CPU/group as long as a CPU/group is + * active in the group. This designated role is necessary to avoid that all + * active CPUs in a group try to migrate expired timers from other CPUs, + * which would result in massive lock bouncing. + * + * When a CPU is awake, it checks in it's own timer tick the group + * hierarchy up to the point where it is assigned the migrator role or if + * no CPU is active, it also checks the groups where no migrator is set + * (TMIGR_NONE). + * + * If it finds expired timers in one of the group queues it pulls them over + * from the idle CPU and runs the timer function. After that it updates the + * group and the parent groups if required. + * + * CPUs which go idle arm their CPU local timer hardware for the next local + * (pinned) timer event. If the next migratable timer expires after the + * next local timer or the CPU has no migratable timer pending then the + * CPU does not queue an event in the LVL0 group. If the next migratable + * timer expires before the next local timer then the CPU queues that timer + * in the LVL0 group. In both cases the CPU marks itself idle in the LVL0 + * group. + * + * When CPU comes out of idle and when a group has at least a single active + * child, the ignore flag of the tmigr_event is set. This indicates, that + * the event is ignored even if it is still enqueued in the parent groups + * timer queue. It will be removed when touching the timer queue the next + * time. This spares locking in active path as the lock protects (after + * setup) only event information. For more information about locking, + * please read the section "Locking rules". + * + * If the CPU is the migrator of the group then it delegates that role to + * the next active CPU in the group or sets migrator to TMIGR_NONE when + * there is no active CPU in the group. This delegation needs to be + * propagated up the hierarchy so hand over from other leaves can happen at + * all hierarchy levels w/o doing a search. + * + * When the last CPU in the system goes idle, then it drops all migrator + * duties up to the top level of the hierarchy (LVL2 in the example). It + * then has to make sure, that it arms it's own local hardware timer for + * the earliest event in the system. + * + * + * Lifetime rules: + * --------------- + * + * The groups are built up at init time or when CPUs come online. They are + * not destroyed when a group becomes empty due to offlining. The group + * just won't participate in the hierarchy management anymore. Destroying + * groups would result in interesting race conditions which would just make + * the whole mechanism slow and complex. + * + * + * Locking rules: + * -------------- + * + * For setting up new groups and handling events it's required to lock both + * child and parent group. The lock ordering is always bottom up. This also + * includes the per CPU locks in struct tmigr_cpu. For updating the migrator and + * active CPU/group information atomic_try_cmpxchg() is used instead and only + * the per CPU tmigr_cpu->lock is held. + * + * During the setup of groups tmigr_level_list is required. It is protected by + * @tmigr_mutex. + * + * When @timer_base->lock as well as tmigr related locks are required, the lock + * ordering is: first @timer_base->lock, afterwards tmigr related locks. + * + * + * Protection of the tmigr group state information: + * ------------------------------------------------ + * + * The state information with the list of active children and migrator needs to + * be protected by a sequence counter. It prevents a race when updates in child + * groups are propagated in changed order. The state update is performed + * lockless and group wise. The following scenario describes what happens + * without updating the sequence counter: + * + * Therefore, let's take three groups and four CPUs (CPU2 and CPU3 as well + * as GRP0:1 will not change during the scenario): + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:0, GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = CPU0 migrator = CPU2 + * active = CPU0 active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * active idle active idle + * + * + * 1. CPU0 goes idle. As the update is performed group wise, in the first step + * only GRP0:0 is updated. The update of GRP1:0 is pending as CPU0 has to + * walk the hierarchy. + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:0, GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * --> migrator = TMIGR_NONE migrator = CPU2 + * --> active = active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * --> idle idle active idle + * + * 2. While CPU0 goes idle and continues to update the state, CPU1 comes out of + * idle. CPU1 updates GRP0:0. The update for GRP1:0 is pending as CPU1 also + * has to walk the hierarchy. Both CPUs (CPU0 and CPU1) now walk the + * hierarchy to perform the needed update from their point of view. The + * currently visible state looks the following: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:0, GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * --> migrator = CPU1 migrator = CPU2 + * --> active = CPU1 active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * idle --> active active idle + * + * 3. Here is the race condition: CPU1 managed to propagate its changes (from + * step 2) through the hierarchy to GRP1:0 before CPU0 (step 1) did. The + * active members of GRP1:0 remain unchanged after the update since it is + * still valid from CPU1 current point of view: + * + * LVL 1 [GRP1:0] + * --> migrator = GRP0:1 + * --> active = GRP0:0, GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = CPU1 migrator = CPU2 + * active = CPU1 active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * idle active active idle + * + * 4. Now CPU0 finally propagates its changes (from step 1) to GRP1:0. + * + * LVL 1 [GRP1:0] + * --> migrator = GRP0:1 + * --> active = GRP0:1 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = CPU1 migrator = CPU2 + * active = CPU1 active = CPU2 + * / \ / \ + * CPUs 0 1 2 3 + * idle active active idle + * + * + * The race of CPU0 vs. CPU1 led to an inconsistent state in GRP1:0. CPU1 is + * active and is correctly listed as active in GRP0:0. However GRP1:0 does not + * have GRP0:0 listed as active, which is wrong. The sequence counter has been + * added to avoid inconsistent states during updates. The state is updated + * atomically only if all members, including the sequence counter, match the + * expected value (compare-and-exchange). + * + * Looking back at the previous example with the addition of the sequence + * counter: The update as performed by CPU0 in step 4 will fail. CPU1 changed + * the sequence number during the update in step 3 so the expected old value (as + * seen by CPU0 before starting the walk) does not match. + * + * Prevent race between new event and last CPU going inactive + * ---------------------------------------------------------- + * + * When the last CPU is going idle and there is a concurrent update of a new + * first global timer of an idle CPU, the group and child states have to be read + * while holding the lock in tmigr_update_events(). The following scenario shows + * what happens, when this is not done. + * + * 1. Only CPU2 is active: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * next_expiry = KTIME_MAX + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = CPU2 + * active = active = CPU2 + * next_expiry = KTIME_MAX next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle active idle + * + * 2. Now CPU 2 goes idle (and has no global timer, that has to be handled) and + * propagates that to GRP0:1: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * next_expiry = KTIME_MAX + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE --> migrator = TMIGR_NONE + * active = --> active = + * next_expiry = KTIME_MAX next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle --> idle idle + * + * 3. Now the idle state is propagated up to GRP1:0. As this is now the last + * child going idle in top level group, the expiry of the next group event + * has to be handed back to make sure no event is lost. As there is no event + * enqueued, KTIME_MAX is handed back to CPU2. + * + * LVL 1 [GRP1:0] + * --> migrator = TMIGR_NONE + * --> active = + * next_expiry = KTIME_MAX + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = TMIGR_NONE + * active = active = + * next_expiry = KTIME_MAX next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle --> idle idle + * + * 4. CPU 0 has a new timer queued from idle and it expires at TIMER0. CPU0 + * propagates that to GRP0:0: + * + * LVL 1 [GRP1:0] + * migrator = TMIGR_NONE + * active = + * next_expiry = KTIME_MAX + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = TMIGR_NONE + * active = active = + * --> next_expiry = TIMER0 next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle idle idle + * + * 5. GRP0:0 is not active, so the new timer has to be propagated to + * GRP1:0. Therefore the GRP1:0 state has to be read. When the stalled value + * (from step 2) is read, the timer is enqueued into GRP1:0, but nothing is + * handed back to CPU0, as it seems that there is still an active child in + * top level group. + * + * LVL 1 [GRP1:0] + * migrator = TMIGR_NONE + * active = + * --> next_expiry = TIMER0 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = TMIGR_NONE + * active = active = + * next_expiry = TIMER0 next_expiry = KTIME_MAX + * / \ / \ + * CPUs 0 1 2 3 + * idle idle idle idle + * + * This is prevented by reading the state when holding the lock (when a new + * timer has to be propagated from idle path):: + * + * CPU2 (tmigr_inactive_up()) CPU0 (tmigr_new_timer_up()) + * -------------------------- --------------------------- + * // step 3: + * cmpxchg(&GRP1:0->state); + * tmigr_update_events() { + * spin_lock(&GRP1:0->lock); + * // ... update events ... + * // hand back first expiry when GRP1:0 is idle + * spin_unlock(&GRP1:0->lock); + * // ^^^ release state modification + * } + * tmigr_update_events() { + * spin_lock(&GRP1:0->lock) + * // ^^^ acquire state modification + * group_state = atomic_read(&GRP1:0->state) + * // .... update events ... + * // hand back first expiry when GRP1:0 is idle + * spin_unlock(&GRP1:0->lock) <3> + * // ^^^ makes state visible for other + * // callers of tmigr_new_timer_up() + * } + * + * When CPU0 grabs the lock directly after cmpxchg, the first timer is reported + * back to CPU0 and also later on to CPU2. So no timer is missed. A concurrent + * update of the group state from active path is no problem, as the upcoming CPU + * will take care of the group events. + * + * Required event and timerqueue update after a remote expiry: + * ----------------------------------------------------------- + * + * After expiring timers of a remote CPU, a walk through the hierarchy and + * update of events and timerqueues is required. It is obviously needed if there + * is a 'new' global timer but also if there is no new global timer but the + * remote CPU is still idle. + * + * 1. CPU0 and CPU1 are idle and have both a global timer expiring at the same + * time. So both have an event enqueued in the timerqueue of GRP0:0. CPU3 is + * also idle and has no global timer pending. CPU2 is the only active CPU and + * thus also the migrator: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * --> timerqueue = evt-GRP0:0 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = CPU2 + * active = active = CPU2 + * groupevt.ignore = false groupevt.ignore = true + * groupevt.cpu = CPU0 groupevt.cpu = + * timerqueue = evt-CPU0, timerqueue = + * evt-CPU1 + * / \ / \ + * CPUs 0 1 2 3 + * idle idle active idle + * + * 2. CPU2 starts to expire remote timers. It starts with LVL0 group + * GRP0:1. There is no event queued in the timerqueue, so CPU2 continues with + * the parent of GRP0:1: GRP1:0. In GRP1:0 it dequeues the first event. It + * looks at tmigr_event::cpu struct member and expires the pending timer(s) + * of CPU0. + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * --> timerqueue = + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = CPU2 + * active = active = CPU2 + * groupevt.ignore = false groupevt.ignore = true + * --> groupevt.cpu = CPU0 groupevt.cpu = + * timerqueue = evt-CPU0, timerqueue = + * evt-CPU1 + * / \ / \ + * CPUs 0 1 2 3 + * idle idle active idle + * + * 3. Some work has to be done after expiring the timers of CPU0. If we stop + * here, then CPU1's pending global timer(s) will not expire in time and the + * timerqueue of GRP0:0 has still an event for CPU0 enqueued which has just + * been processed. So it is required to walk the hierarchy from CPU0's point + * of view and update it accordingly. CPU0's event will be removed from the + * timerqueue because it has no pending timer. If CPU0 would have a timer + * pending then it has to expire after CPU1's first timer because all timers + * from this period were just expired. Either way CPU1's event will be first + * in GRP0:0's timerqueue and therefore set in the CPU field of the group + * event which is then enqueued in GRP1:0's timerqueue as GRP0:0 is still not + * active: + * + * LVL 1 [GRP1:0] + * migrator = GRP0:1 + * active = GRP0:1 + * --> timerqueue = evt-GRP0:0 + * / \ + * LVL 0 [GRP0:0] [GRP0:1] + * migrator = TMIGR_NONE migrator = CPU2 + * active = active = CPU2 + * groupevt.ignore = false groupevt.ignore = true + * --> groupevt.cpu = CPU1 groupevt.cpu = + * --> timerqueue = evt-CPU1 timerqueue = + * / \ / \ + * CPUs 0 1 2 3 + * idle idle active idle + * + * Now CPU2 (migrator) will continue step 2 at GRP1:0 and will expire the + * timer(s) of CPU1. + * + * The hierarchy walk in step 3 can be skipped if the migrator notices that a + * CPU of GRP0:0 is active again. The CPU will mark GRP0:0 active and take care + * of the group as migrator and any needed updates within the hierarchy. + */ + +static DEFINE_MUTEX(tmigr_mutex); +static struct list_head *tmigr_level_list __read_mostly; + +static unsigned int tmigr_hierarchy_levels __read_mostly; +static unsigned int tmigr_crossnode_level __read_mostly; + +static DEFINE_PER_CPU(struct tmigr_cpu, tmigr_cpu); + +#define TMIGR_NONE 0xFF +#define BIT_CNT 8 + +static inline bool tmigr_is_not_available(struct tmigr_cpu *tmc) +{ + return !(tmc->tmgroup && tmc->online); +} + +/* + * Returns true, when @childmask corresponds to the group migrator or when the + * group is not active - so no migrator is set. + */ +static bool tmigr_check_migrator(struct tmigr_group *group, u8 childmask) +{ + union tmigr_state s; + + s.state = atomic_read(&group->migr_state); + + if ((s.migrator == childmask) || (s.migrator == TMIGR_NONE)) + return true; + + return false; +} + +static bool tmigr_check_migrator_and_lonely(struct tmigr_group *group, u8 childmask) +{ + bool lonely, migrator = false; + unsigned long active; + union tmigr_state s; + + s.state = atomic_read(&group->migr_state); + + if ((s.migrator == childmask) || (s.migrator == TMIGR_NONE)) + migrator = true; + + active = s.active; + lonely = bitmap_weight(&active, BIT_CNT) <= 1; + + return (migrator && lonely); +} + +static bool tmigr_check_lonely(struct tmigr_group *group) +{ + unsigned long active; + union tmigr_state s; + + s.state = atomic_read(&group->migr_state); + + active = s.active; + + return bitmap_weight(&active, BIT_CNT) <= 1; +} + +typedef bool (*up_f)(struct tmigr_group *, struct tmigr_group *, void *); + +static void __walk_groups(up_f up, void *data, + struct tmigr_cpu *tmc) +{ + struct tmigr_group *child = NULL, *group = tmc->tmgroup; + + do { + WARN_ON_ONCE(group->level >= tmigr_hierarchy_levels); + + if (up(group, child, data)) + break; + + child = group; + group = group->parent; + } while (group); +} + +static void walk_groups(up_f up, void *data, struct tmigr_cpu *tmc) +{ + lockdep_assert_held(&tmc->lock); + + __walk_groups(up, data, tmc); +} + +/** + * struct tmigr_walk - data required for walking the hierarchy + * @nextexp: Next CPU event expiry information which is handed into + * the timer migration code by the timer code + * (get_next_timer_interrupt()) + * @firstexp: Contains the first event expiry information when last + * active CPU of hierarchy is on the way to idle to make + * sure CPU will be back in time. + * @evt: Pointer to tmigr_event which needs to be queued (of idle + * child group) + * @childmask: childmask of child group + * @remote: Is set, when the new timer path is executed in + * tmigr_handle_remote_cpu() + */ +struct tmigr_walk { + u64 nextexp; + u64 firstexp; + struct tmigr_event *evt; + u8 childmask; + bool remote; +}; + +/** + * struct tmigr_remote_data - data required for remote expiry hierarchy walk + * @basej: timer base in jiffies + * @now: timer base monotonic + * @firstexp: returns expiry of the first timer in the idle timer + * migration hierarchy to make sure the timer is handled in + * time; it is stored in the per CPU tmigr_cpu struct of + * CPU which expires remote timers + * @childmask: childmask of child group + * @check: is set if there is the need to handle remote timers; + * required in tmigr_requires_handle_remote() only + * @tmc_active: this flag indicates, whether the CPU which triggers + * the hierarchy walk is !idle in the timer migration + * hierarchy. When the CPU is idle and the whole hierarchy is + * idle, only the first event of the top level has to be + * considered. + */ +struct tmigr_remote_data { + unsigned long basej; + u64 now; + u64 firstexp; + u8 childmask; + bool check; + bool tmc_active; +}; + +/* + * Returns the next event of the timerqueue @group->events + * + * Removes timers with ignore flag and update next_expiry of the group. Values + * of the group event are updated in tmigr_update_events() only. + */ +static struct tmigr_event *tmigr_next_groupevt(struct tmigr_group *group) +{ + struct timerqueue_node *node = NULL; + struct tmigr_event *evt = NULL; + + lockdep_assert_held(&group->lock); + + WRITE_ONCE(group->next_expiry, KTIME_MAX); + + while ((node = timerqueue_getnext(&group->events))) { + evt = container_of(node, struct tmigr_event, nextevt); + + if (!evt->ignore) { + WRITE_ONCE(group->next_expiry, evt->nextevt.expires); + return evt; + } + + /* + * Remove next timers with ignore flag, because the group lock + * is held anyway + */ + if (!timerqueue_del(&group->events, node)) + break; + } + + return NULL; +} + +/* + * Return the next event (with the expiry equal or before @now) + * + * Event, which is returned, is also removed from the queue. + */ +static struct tmigr_event *tmigr_next_expired_groupevt(struct tmigr_group *group, + u64 now) +{ + struct tmigr_event *evt = tmigr_next_groupevt(group); + + if (!evt || now < evt->nextevt.expires) + return NULL; + + /* + * The event is ready to expire. Remove it and update next group event. + */ + timerqueue_del(&group->events, &evt->nextevt); + tmigr_next_groupevt(group); + + return evt; +} + +static u64 tmigr_next_groupevt_expires(struct tmigr_group *group) +{ + struct tmigr_event *evt; + + evt = tmigr_next_groupevt(group); + + if (!evt) + return KTIME_MAX; + else + return evt->nextevt.expires; +} + +static bool tmigr_active_up(struct tmigr_group *group, + struct tmigr_group *child, + void *ptr) +{ + union tmigr_state curstate, newstate; + struct tmigr_walk *data = ptr; + bool walk_done; + u8 childmask; + + childmask = data->childmask; + /* + * No memory barrier is required here in contrast to + * tmigr_inactive_up(), as the group state change does not depend on the + * child state. + */ + curstate.state = atomic_read(&group->migr_state); + + do { + newstate = curstate; + walk_done = true; + + if (newstate.migrator == TMIGR_NONE) { + newstate.migrator = childmask; + + /* Changes need to be propagated */ + walk_done = false; + } + + newstate.active |= childmask; + newstate.seq++; + + } while (!atomic_try_cmpxchg(&group->migr_state, &curstate.state, newstate.state)); + + if ((walk_done == false) && group->parent) + data->childmask = group->childmask; + + /* + * The group is active (again). The group event might be still queued + * into the parent group's timerqueue but can now be handled by the + * migrator of this group. Therefore the ignore flag for the group event + * is updated to reflect this. + * + * The update of the ignore flag in the active path is done lockless. In + * worst case the migrator of the parent group observes the change too + * late and expires remotely all events belonging to this group. The + * lock is held while updating the ignore flag in idle path. So this + * state change will not be lost. + */ + group->groupevt.ignore = true; + + return walk_done; +} + +static void __tmigr_cpu_activate(struct tmigr_cpu *tmc) +{ + struct tmigr_walk data; + + data.childmask = tmc->childmask; + + tmc->cpuevt.ignore = true; + WRITE_ONCE(tmc->wakeup, KTIME_MAX); + + walk_groups(&tmigr_active_up, &data, tmc); +} + +/** + * tmigr_cpu_activate() - set this CPU active in timer migration hierarchy + * + * Call site timer_clear_idle() is called with interrupts disabled. + */ +void tmigr_cpu_activate(void) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + + if (tmigr_is_not_available(tmc)) + return; + + if (WARN_ON_ONCE(!tmc->idle)) + return; + + raw_spin_lock(&tmc->lock); + tmc->idle = false; + __tmigr_cpu_activate(tmc); + raw_spin_unlock(&tmc->lock); +} + +/* + * Returns true, if there is nothing to be propagated to the next level + * + * @data->firstexp is set to expiry of first gobal event of the (top level of + * the) hierarchy, but only when hierarchy is completely idle. + * + * The child and group states need to be read under the lock, to prevent a race + * against a concurrent tmigr_inactive_up() run when the last CPU goes idle. See + * also section "Prevent race between new event and last CPU going inactive" in + * the documentation at the top. + * + * This is the only place where the group event expiry value is set. + */ +static +bool tmigr_update_events(struct tmigr_group *group, struct tmigr_group *child, + struct tmigr_walk *data) +{ + struct tmigr_event *evt, *first_childevt; + union tmigr_state childstate, groupstate; + bool remote = data->remote; + bool walk_done = false; + u64 nextexp; + + if (child) { + raw_spin_lock(&child->lock); + raw_spin_lock_nested(&group->lock, SINGLE_DEPTH_NESTING); + + childstate.state = atomic_read(&child->migr_state); + groupstate.state = atomic_read(&group->migr_state); + + if (childstate.active) { + walk_done = true; + goto unlock; + } + + first_childevt = tmigr_next_groupevt(child); + nextexp = child->next_expiry; + evt = &child->groupevt; + + evt->ignore = (nextexp == KTIME_MAX) ? true : false; + } else { + nextexp = data->nextexp; + + first_childevt = evt = data->evt; + + /* + * Walking the hierarchy is required in any case when a + * remote expiry was done before. This ensures to not lose + * already queued events in non active groups (see section + * "Required event and timerqueue update after a remote + * expiry" in the documentation at the top). + * + * The two call sites which are executed without a remote expiry + * before, are not prevented from propagating changes through + * the hierarchy by the return: + * - When entering this path by tmigr_new_timer(), @evt->ignore + * is never set. + * - tmigr_inactive_up() takes care of the propagation by + * itself and ignores the return value. But an immediate + * return is required because nothing has to be done in this + * level as the event could be ignored. + */ + if (evt->ignore && !remote) + return true; + + raw_spin_lock(&group->lock); + + childstate.state = 0; + groupstate.state = atomic_read(&group->migr_state); + } + + /* + * If the child event is already queued in the group, remove it from the + * queue when the expiry time changed only or when it could be ignored. + */ + if (timerqueue_node_queued(&evt->nextevt)) { + if ((evt->nextevt.expires == nextexp) && !evt->ignore) + goto check_toplvl; + + if (!timerqueue_del(&group->events, &evt->nextevt)) + WRITE_ONCE(group->next_expiry, KTIME_MAX); + } + + if (evt->ignore) { + /* + * When the next child event could be ignored (nextexp is + * KTIME_MAX) and there was no remote timer handling before or + * the group is already active, there is no need to walk the + * hierarchy even if there is a parent group. + * + * The other way round: even if the event could be ignored, but + * if a remote timer handling was executed before and the group + * is not active, walking the hierarchy is required to not miss + * an enqueued timer in the non active group. The enqueued timer + * of the group needs to be propagated to a higher level to + * ensure it is handled. + */ + if (!remote || groupstate.active) + walk_done = true; + } else { + evt->nextevt.expires = nextexp; + evt->cpu = first_childevt->cpu; + + if (timerqueue_add(&group->events, &evt->nextevt)) + WRITE_ONCE(group->next_expiry, nextexp); + } + +check_toplvl: + if (!group->parent && (groupstate.migrator == TMIGR_NONE)) { + walk_done = true; + + /* + * Nothing to do when update was done during remote timer + * handling. First timer in top level group which needs to be + * handled when top level group is not active, is calculated + * directly in tmigr_handle_remote_up(). + */ + if (remote) + goto unlock; + + /* + * The top level group is idle and it has to be ensured the + * global timers are handled in time. (This could be optimized + * by keeping track of the last global scheduled event and only + * arming it on the CPU if the new event is earlier. Not sure if + * its worth the complexity.) + */ + data->firstexp = tmigr_next_groupevt_expires(group); + } + +unlock: + raw_spin_unlock(&group->lock); + + if (child) + raw_spin_unlock(&child->lock); + + return walk_done; +} + +static bool tmigr_new_timer_up(struct tmigr_group *group, + struct tmigr_group *child, + void *ptr) +{ + struct tmigr_walk *data = ptr; + + return tmigr_update_events(group, child, data); +} + +/* + * Returns the expiry of the next timer that needs to be handled. KTIME_MAX is + * returned, if an active CPU will handle all the timer migration hierarchy + * timers. + */ +static u64 tmigr_new_timer(struct tmigr_cpu *tmc, u64 nextexp) +{ + struct tmigr_walk data = { .nextexp = nextexp, + .firstexp = KTIME_MAX, + .evt = &tmc->cpuevt }; + + lockdep_assert_held(&tmc->lock); + + if (tmc->remote) + return KTIME_MAX; + + tmc->cpuevt.ignore = false; + data.remote = false; + + walk_groups(&tmigr_new_timer_up, &data, tmc); + + /* If there is a new first global event, make sure it is handled */ + return data.firstexp; +} + +static void tmigr_handle_remote_cpu(unsigned int cpu, u64 now, + unsigned long jif) +{ + struct timer_events tevt; + struct tmigr_walk data; + struct tmigr_cpu *tmc; + + tmc = per_cpu_ptr(&tmigr_cpu, cpu); + + raw_spin_lock_irq(&tmc->lock); + + /* + * If the remote CPU is offline then the timers have been migrated to + * another CPU. + * + * If tmigr_cpu::remote is set, at the moment another CPU already + * expires the timers of the remote CPU. + * + * If tmigr_event::ignore is set, then the CPU returns from idle and + * takes care of its timers. + * + * If the next event expires in the future, then the event has been + * updated and there are no timers to expire right now. The CPU which + * updated the event takes care when hierarchy is completely + * idle. Otherwise the migrator does it as the event is enqueued. + */ + if (!tmc->online || tmc->remote || tmc->cpuevt.ignore || + now < tmc->cpuevt.nextevt.expires) { + raw_spin_unlock_irq(&tmc->lock); + return; + } + + tmc->remote = true; + WRITE_ONCE(tmc->wakeup, KTIME_MAX); + + /* Drop the lock to allow the remote CPU to exit idle */ + raw_spin_unlock_irq(&tmc->lock); + + if (cpu != smp_processor_id()) + timer_expire_remote(cpu); + + /* + * Lock ordering needs to be preserved - timer_base locks before tmigr + * related locks (see section "Locking rules" in the documentation at + * the top). During fetching the next timer interrupt, also tmc->lock + * needs to be held. Otherwise there is a possible race window against + * the CPU itself when it comes out of idle, updates the first timer in + * the hierarchy and goes back to idle. + * + * timer base locks are dropped as fast as possible: After checking + * whether the remote CPU went offline in the meantime and after + * fetching the next remote timer interrupt. Dropping the locks as fast + * as possible keeps the locking region small and prevents holding + * several (unnecessary) locks during walking the hierarchy for updating + * the timerqueue and group events. + */ + local_irq_disable(); + timer_lock_remote_bases(cpu); + raw_spin_lock(&tmc->lock); + + /* + * When the CPU went offline in the meantime, no hierarchy walk has to + * be done for updating the queued events, because the walk was + * already done during marking the CPU offline in the hierarchy. + * + * When the CPU is no longer idle, the CPU takes care of the timers and + * also of the timers in the hierarchy. + * + * (See also section "Required event and timerqueue update after a + * remote expiry" in the documentation at the top) + */ + if (!tmc->online || !tmc->idle) { + timer_unlock_remote_bases(cpu); + goto unlock; + } + + /* next event of CPU */ + fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu); + timer_unlock_remote_bases(cpu); + + data.nextexp = tevt.global; + data.firstexp = KTIME_MAX; + data.evt = &tmc->cpuevt; + data.remote = true; + + /* + * The update is done even when there is no 'new' global timer pending + * on the remote CPU (see section "Required event and timerqueue update + * after a remote expiry" in the documentation at the top) + */ + walk_groups(&tmigr_new_timer_up, &data, tmc); + +unlock: + tmc->remote = false; + raw_spin_unlock_irq(&tmc->lock); +} + +static bool tmigr_handle_remote_up(struct tmigr_group *group, + struct tmigr_group *child, + void *ptr) +{ + struct tmigr_remote_data *data = ptr; + struct tmigr_event *evt; + unsigned long jif; + u8 childmask; + u64 now; + + jif = data->basej; + now = data->now; + + childmask = data->childmask; + +again: + /* + * Handle the group only if @childmask is the migrator or if the + * group has no migrator. Otherwise the group is active and is + * handled by its own migrator. + */ + if (!tmigr_check_migrator(group, childmask)) + return true; + + raw_spin_lock_irq(&group->lock); + + evt = tmigr_next_expired_groupevt(group, now); + + if (evt) { + unsigned int remote_cpu = evt->cpu; + + raw_spin_unlock_irq(&group->lock); + + tmigr_handle_remote_cpu(remote_cpu, now, jif); + + /* check if there is another event, that needs to be handled */ + goto again; + } + + /* + * Update of childmask for the next level and keep track of the expiry + * of the first event that needs to be handled (group->next_expiry was + * updated by tmigr_next_expired_groupevt(), next was set by + * tmigr_handle_remote_cpu()). + */ + data->childmask = group->childmask; + data->firstexp = group->next_expiry; + + raw_spin_unlock_irq(&group->lock); + + return false; +} + +/** + * tmigr_handle_remote() - Handle global timers of remote idle CPUs + * + * Called from the timer soft interrupt with interrupts enabled. + */ +void tmigr_handle_remote(void) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + struct tmigr_remote_data data; + + if (tmigr_is_not_available(tmc)) + return; + + data.childmask = tmc->childmask; + data.firstexp = KTIME_MAX; + + /* + * NOTE: This is a doubled check because the migrator test will be done + * in tmigr_handle_remote_up() anyway. Keep this check to speed up the + * return when nothing has to be done. + */ + if (!tmigr_check_migrator(tmc->tmgroup, tmc->childmask)) + return; + + data.now = get_jiffies_update(&data.basej); + + /* + * Update @tmc->wakeup only at the end and do not reset @tmc->wakeup to + * KTIME_MAX. Even if tmc->lock is not held during the whole remote + * handling, tmc->wakeup is fine to be stale as it is called in + * interrupt context and tick_nohz_next_event() is executed in interrupt + * exit path only after processing the last pending interrupt. + */ + + __walk_groups(&tmigr_handle_remote_up, &data, tmc); + + raw_spin_lock_irq(&tmc->lock); + WRITE_ONCE(tmc->wakeup, data.firstexp); + raw_spin_unlock_irq(&tmc->lock); +} + +static bool tmigr_requires_handle_remote_up(struct tmigr_group *group, + struct tmigr_group *child, + void *ptr) +{ + struct tmigr_remote_data *data = ptr; + u8 childmask; + + childmask = data->childmask; + + /* + * Handle the group only if the child is the migrator or if the group + * has no migrator. Otherwise the group is active and is handled by its + * own migrator. + */ + if (!tmigr_check_migrator(group, childmask)) + return true; + + /* + * When there is a parent group and the CPU which triggered the + * hierarchy walk is not active, proceed the walk to reach the top level + * group before reading the next_expiry value. + */ + if (group->parent && !data->tmc_active) + goto out; + + /* + * The lock is required on 32bit architectures to read the variable + * consistently with a concurrent writer. On 64bit the lock is not + * required because the read operation is not split and so it is always + * consistent. + */ + if (IS_ENABLED(CONFIG_64BIT)) { + data->firstexp = READ_ONCE(group->next_expiry); + if (data->now >= data->firstexp) { + data->check = true; + return true; + } + } else { + raw_spin_lock(&group->lock); + data->firstexp = group->next_expiry; + if (data->now >= group->next_expiry) { + data->check = true; + raw_spin_unlock(&group->lock); + return true; + } + raw_spin_unlock(&group->lock); + } + +out: + /* Update of childmask for the next level */ + data->childmask = group->childmask; + return false; +} + +/** + * tmigr_requires_handle_remote() - Check the need of remote timer handling + * + * Must be called with interrupts disabled. + */ +bool tmigr_requires_handle_remote(void) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + struct tmigr_remote_data data; + unsigned long jif; + bool ret = false; + + if (tmigr_is_not_available(tmc)) + return ret; + + data.now = get_jiffies_update(&jif); + data.childmask = tmc->childmask; + data.firstexp = KTIME_MAX; + data.tmc_active = !tmc->idle; + data.check = false; + + /* + * If the CPU is active, walk the hierarchy to check whether a remote + * expiry is required. + * + * Check is done lockless as interrupts are disabled and @tmc->idle is + * set only by the local CPU. + */ + if (!tmc->idle) { + __walk_groups(&tmigr_requires_handle_remote_up, &data, tmc); + + return data.check; + } + + /* + * When the CPU is idle, compare @tmc->wakeup with @data.now. The lock + * is required on 32bit architectures to read the variable consistently + * with a concurrent writer. On 64bit the lock is not required because + * the read operation is not split and so it is always consistent. + */ + if (IS_ENABLED(CONFIG_64BIT)) { + if (data.now >= READ_ONCE(tmc->wakeup)) + return true; + } else { + raw_spin_lock(&tmc->lock); + if (data.now >= tmc->wakeup) + ret = true; + raw_spin_unlock(&tmc->lock); + } + + return ret; +} + +/** + * tmigr_cpu_new_timer() - enqueue next global timer into hierarchy (idle tmc) + * @nextexp: Next expiry of global timer (or KTIME_MAX if not) + * + * The CPU is already deactivated in the timer migration + * hierarchy. tick_nohz_get_sleep_length() calls tick_nohz_next_event() + * and thereby the timer idle path is executed once more. @tmc->wakeup + * holds the first timer, when the timer migration hierarchy is + * completely idle. + * + * Returns the first timer that needs to be handled by this CPU or KTIME_MAX if + * nothing needs to be done. + */ +u64 tmigr_cpu_new_timer(u64 nextexp) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + u64 ret; + + if (tmigr_is_not_available(tmc)) + return nextexp; + + raw_spin_lock(&tmc->lock); + + ret = READ_ONCE(tmc->wakeup); + if (nextexp != KTIME_MAX) { + if (nextexp != tmc->cpuevt.nextevt.expires || + tmc->cpuevt.ignore) { + ret = tmigr_new_timer(tmc, nextexp); + } + } + /* + * Make sure the reevaluation of timers in idle path will not miss an + * event. + */ + WRITE_ONCE(tmc->wakeup, ret); + + raw_spin_unlock(&tmc->lock); + return ret; +} + +static bool tmigr_inactive_up(struct tmigr_group *group, + struct tmigr_group *child, + void *ptr) +{ + union tmigr_state curstate, newstate, childstate; + struct tmigr_walk *data = ptr; + bool walk_done; + u8 childmask; + + childmask = data->childmask; + childstate.state = 0; + + /* + * The memory barrier is paired with the cmpxchg() in tmigr_active_up() + * to make sure the updates of child and group states are ordered. The + * ordering is mandatory, as the group state change depends on the child + * state. + */ + curstate.state = atomic_read_acquire(&group->migr_state); + + for (;;) { + if (child) + childstate.state = atomic_read(&child->migr_state); + + newstate = curstate; + walk_done = true; + + /* Reset active bit when the child is no longer active */ + if (!childstate.active) + newstate.active &= ~childmask; + + if (newstate.migrator == childmask) { + /* + * Find a new migrator for the group, because the child + * group is idle! + */ + if (!childstate.active) { + unsigned long new_migr_bit, active = newstate.active; + + new_migr_bit = find_first_bit(&active, BIT_CNT); + + if (new_migr_bit != BIT_CNT) { + newstate.migrator = BIT(new_migr_bit); + } else { + newstate.migrator = TMIGR_NONE; + + /* Changes need to be propagated */ + walk_done = false; + } + } + } + + newstate.seq++; + + WARN_ON_ONCE((newstate.migrator != TMIGR_NONE) && !(newstate.active)); + + if (atomic_try_cmpxchg(&group->migr_state, &curstate.state, + newstate.state)) + break; + + /* + * The memory barrier is paired with the cmpxchg() in + * tmigr_active_up() to make sure the updates of child and group + * states are ordered. It is required only when the above + * try_cmpxchg() fails. + */ + smp_mb__after_atomic(); + } + + data->remote = false; + + /* Event Handling */ + tmigr_update_events(group, child, data); + + if (group->parent && (walk_done == false)) + data->childmask = group->childmask; + + /* + * data->firstexp was set by tmigr_update_events() and contains the + * expiry of the first global event which needs to be handled. It + * differs from KTIME_MAX if: + * - group is the top level group and + * - group is idle (which means CPU was the last active CPU in the + * hierarchy) and + * - there is a pending event in the hierarchy + */ + WARN_ON_ONCE(data->firstexp != KTIME_MAX && group->parent); + + return walk_done; +} + +static u64 __tmigr_cpu_deactivate(struct tmigr_cpu *tmc, u64 nextexp) +{ + struct tmigr_walk data = { .nextexp = nextexp, + .firstexp = KTIME_MAX, + .evt = &tmc->cpuevt, + .childmask = tmc->childmask }; + + /* + * If nextexp is KTIME_MAX, the CPU event will be ignored because the + * local timer expires before the global timer, no global timer is set + * or CPU goes offline. + */ + if (nextexp != KTIME_MAX) + tmc->cpuevt.ignore = false; + + walk_groups(&tmigr_inactive_up, &data, tmc); + return data.firstexp; +} + +/** + * tmigr_cpu_deactivate() - Put current CPU into inactive state + * @nextexp: The next global timer expiry of the current CPU + * + * Must be called with interrupts disabled. + * + * Return: the next event expiry of the current CPU or the next event expiry + * from the hierarchy if this CPU is the top level migrator or the hierarchy is + * completely idle. + */ +u64 tmigr_cpu_deactivate(u64 nextexp) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + u64 ret; + + if (tmigr_is_not_available(tmc)) + return nextexp; + + raw_spin_lock(&tmc->lock); + + ret = __tmigr_cpu_deactivate(tmc, nextexp); + + tmc->idle = true; + + /* + * Make sure the reevaluation of timers in idle path will not miss an + * event. + */ + WRITE_ONCE(tmc->wakeup, ret); + + raw_spin_unlock(&tmc->lock); + return ret; +} + +/** + * tmigr_quick_check() - Quick forecast of next tmigr event when CPU wants to + * go idle + * @nextevt: The next global timer expiry of the current CPU + * + * Return: + * * KTIME_MAX - when it is probable that nothing has to be done (not + * the only one in the level 0 group; and if it is the + * only one in level 0 group, but there are more than a + * single group active on the way to top level) + * * nextevt - when CPU is offline and has to handle timer on his own + * or when on the way to top in every group only a single + * child is active and but @nextevt is before next_expiry + * of top level group + * * next_expiry (top) - value of top level group, when on the way to top in + * every group only a single child is active and @nextevt + * is after this value active child. + */ +u64 tmigr_quick_check(u64 nextevt) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + struct tmigr_group *group = tmc->tmgroup; + + if (tmigr_is_not_available(tmc)) + return nextevt; + + if (WARN_ON_ONCE(tmc->idle)) + return nextevt; + + if (!tmigr_check_migrator_and_lonely(tmc->tmgroup, tmc->childmask)) + return KTIME_MAX; + + do { + if (!tmigr_check_lonely(group)) { + return KTIME_MAX; + } else if (!group->parent) { + u64 first_global = READ_ONCE(group->next_expiry); + + return min_t(u64, nextevt, first_global); + } + group = group->parent; + } while (group); + + return KTIME_MAX; +} + +static void tmigr_init_group(struct tmigr_group *group, unsigned int lvl, + int node) +{ + union tmigr_state s; + + raw_spin_lock_init(&group->lock); + + group->level = lvl; + group->numa_node = lvl < tmigr_crossnode_level ? node : NUMA_NO_NODE; + + group->num_children = 0; + + s.migrator = TMIGR_NONE; + s.active = 0; + s.seq = 0; + atomic_set(&group->migr_state, s.state); + + timerqueue_init_head(&group->events); + timerqueue_init(&group->groupevt.nextevt); + group->groupevt.nextevt.expires = KTIME_MAX; + WRITE_ONCE(group->next_expiry, KTIME_MAX); + group->groupevt.ignore = true; +} + +static struct tmigr_group *tmigr_get_group(unsigned int cpu, int node, + unsigned int lvl) +{ + struct tmigr_group *tmp, *group = NULL; + + lockdep_assert_held(&tmigr_mutex); + + /* Try to attach to an existing group first */ + list_for_each_entry(tmp, &tmigr_level_list[lvl], list) { + /* + * If @lvl is below the cross NUMA node level, check whether + * this group belongs to the same NUMA node. + */ + if (lvl < tmigr_crossnode_level && tmp->numa_node != node) + continue; + + /* Capacity left? */ + if (tmp->num_children >= TMIGR_CHILDREN_PER_GROUP) + continue; + + /* + * TODO: A possible further improvement: Make sure that all CPU + * siblings end up in the same group of the lowest level of the + * hierarchy. Rely on the topology sibling mask would be a + * reasonable solution. + */ + + group = tmp; + break; + } + + if (group) + return group; + + /* Allocate and set up a new group */ + group = kzalloc_node(sizeof(*group), GFP_KERNEL, node); + if (!group) + return ERR_PTR(-ENOMEM); + + tmigr_init_group(group, lvl, node); + + /* Setup successful. Add it to the hierarchy */ + list_add(&group->list, &tmigr_level_list[lvl]); + return group; +} + +static void tmigr_connect_child_parent(struct tmigr_group *child, + struct tmigr_group *parent) +{ + union tmigr_state childstate; + + raw_spin_lock_irq(&child->lock); + raw_spin_lock_nested(&parent->lock, SINGLE_DEPTH_NESTING); + + child->parent = parent; + child->childmask = BIT(parent->num_children++); + + raw_spin_unlock(&parent->lock); + raw_spin_unlock_irq(&child->lock); + + /* + * To prevent inconsistent states, active children need to be active in + * the new parent as well. Inactive children are already marked inactive + * in the parent group: + * + * * When new groups were created by tmigr_setup_groups() starting from + * the lowest level (and not higher then one level below the current + * top level), then they are not active. They will be set active when + * the new online CPU comes active. + * + * * But if a new group above the current top level is required, it is + * mandatory to propagate the active state of the already existing + * child to the new parent. So tmigr_connect_child_parent() is + * executed with the formerly top level group (child) and the newly + * created group (parent). + */ + childstate.state = atomic_read(&child->migr_state); + if (childstate.migrator != TMIGR_NONE) { + struct tmigr_walk data; + + data.childmask = child->childmask; + + /* + * There is only one new level per time. When connecting the + * child and the parent and set the child active when the parent + * is inactive, the parent needs to be the uppermost + * level. Otherwise there went something wrong! + */ + WARN_ON(!tmigr_active_up(parent, child, &data) && parent->parent); + } +} + +static int tmigr_setup_groups(unsigned int cpu, unsigned int node) +{ + struct tmigr_group *group, *child, **stack; + int top = 0, err = 0, i = 0; + struct list_head *lvllist; + + stack = kcalloc(tmigr_hierarchy_levels, sizeof(*stack), GFP_KERNEL); + if (!stack) + return -ENOMEM; + + do { + group = tmigr_get_group(cpu, node, i); + if (IS_ERR(group)) { + err = PTR_ERR(group); + break; + } + + top = i; + stack[i++] = group; + + /* + * When booting only less CPUs of a system than CPUs are + * available, not all calculated hierarchy levels are required. + * + * The loop is aborted as soon as the highest level, which might + * be different from tmigr_hierarchy_levels, contains only a + * single group. + */ + if (group->parent || i == tmigr_hierarchy_levels || + (list_empty(&tmigr_level_list[i]) && + list_is_singular(&tmigr_level_list[i - 1]))) + break; + + } while (i < tmigr_hierarchy_levels); + + do { + group = stack[--i]; + + if (err < 0) { + list_del(&group->list); + kfree(group); + continue; + } + + WARN_ON_ONCE(i != group->level); + + /* + * Update tmc -> group / child -> group connection + */ + if (i == 0) { + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + + raw_spin_lock_irq(&group->lock); + + tmc->tmgroup = group; + tmc->childmask = BIT(group->num_children++); + + raw_spin_unlock_irq(&group->lock); + + /* There are no children that need to be connected */ + continue; + } else { + child = stack[i - 1]; + tmigr_connect_child_parent(child, group); + } + + /* check if uppermost level was newly created */ + if (top != i) + continue; + + WARN_ON_ONCE(top == 0); + + lvllist = &tmigr_level_list[top]; + if (group->num_children == 1 && list_is_singular(lvllist)) { + lvllist = &tmigr_level_list[top - 1]; + list_for_each_entry(child, lvllist, list) { + if (child->parent) + continue; + + tmigr_connect_child_parent(child, group); + } + } + } while (i > 0); + + kfree(stack); + + return err; +} + +static int tmigr_add_cpu(unsigned int cpu) +{ + int node = cpu_to_node(cpu); + int ret; + + mutex_lock(&tmigr_mutex); + ret = tmigr_setup_groups(cpu, node); + mutex_unlock(&tmigr_mutex); + + return ret; +} + +static int tmigr_cpu_online(unsigned int cpu) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + int ret; + + /* First online attempt? Initialize CPU data */ + if (!tmc->tmgroup) { + raw_spin_lock_init(&tmc->lock); + + ret = tmigr_add_cpu(cpu); + if (ret < 0) + return ret; + + if (tmc->childmask == 0) + return -EINVAL; + + timerqueue_init(&tmc->cpuevt.nextevt); + tmc->cpuevt.nextevt.expires = KTIME_MAX; + tmc->cpuevt.ignore = true; + tmc->cpuevt.cpu = cpu; + + tmc->remote = false; + WRITE_ONCE(tmc->wakeup, KTIME_MAX); + } + raw_spin_lock_irq(&tmc->lock); + tmc->idle = timer_base_is_idle(); + if (!tmc->idle) + __tmigr_cpu_activate(tmc); + tmc->online = true; + raw_spin_unlock_irq(&tmc->lock); + return 0; +} + +/* + * tmigr_trigger_active() - trigger a CPU to become active again + * + * This function is executed on a CPU which is part of cpu_online_mask, when the + * last active CPU in the hierarchy is offlining. With this, it is ensured that + * the other CPU is active and takes over the migrator duty. + */ +static long tmigr_trigger_active(void *unused) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + + WARN_ON_ONCE(!tmc->online || tmc->idle); + + return 0; +} + +static int tmigr_cpu_offline(unsigned int cpu) +{ + struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu); + int migrator; + u64 firstexp; + + raw_spin_lock_irq(&tmc->lock); + tmc->online = false; + WRITE_ONCE(tmc->wakeup, KTIME_MAX); + + /* + * CPU has to handle the local events on his own, when on the way to + * offline; Therefore nextevt value is set to KTIME_MAX + */ + firstexp = __tmigr_cpu_deactivate(tmc, KTIME_MAX); + raw_spin_unlock_irq(&tmc->lock); + + if (firstexp != KTIME_MAX) { + migrator = cpumask_any_but(cpu_online_mask, cpu); + work_on_cpu(migrator, tmigr_trigger_active, NULL); + } + + return 0; +} + +static int __init tmigr_init(void) +{ + unsigned int cpulvl, nodelvl, cpus_per_node, i; + unsigned int nnodes = num_possible_nodes(); + unsigned int ncpus = num_possible_cpus(); + int ret = -ENOMEM; + + BUILD_BUG_ON_NOT_POWER_OF_2(TMIGR_CHILDREN_PER_GROUP); + + /* Nothing to do if running on UP */ + if (ncpus == 1) + return 0; + + /* + * Calculate the required hierarchy levels. Unfortunately there is no + * reliable information available, unless all possible CPUs have been + * brought up and all NUMA nodes are populated. + * + * Estimate the number of levels with the number of possible nodes and + * the number of possible CPUs. Assume CPUs are spread evenly across + * nodes. We cannot rely on cpumask_of_node() because it only works for + * online CPUs. + */ + cpus_per_node = DIV_ROUND_UP(ncpus, nnodes); + + /* Calc the hierarchy levels required to hold the CPUs of a node */ + cpulvl = DIV_ROUND_UP(order_base_2(cpus_per_node), + ilog2(TMIGR_CHILDREN_PER_GROUP)); + + /* Calculate the extra levels to connect all nodes */ + nodelvl = DIV_ROUND_UP(order_base_2(nnodes), + ilog2(TMIGR_CHILDREN_PER_GROUP)); + + tmigr_hierarchy_levels = cpulvl + nodelvl; + + /* + * If a NUMA node spawns more than one CPU level group then the next + * level(s) of the hierarchy contains groups which handle all CPU groups + * of the same NUMA node. The level above goes across NUMA nodes. Store + * this information for the setup code to decide in which level node + * matching is no longer required. + */ + tmigr_crossnode_level = cpulvl; + + tmigr_level_list = kcalloc(tmigr_hierarchy_levels, sizeof(struct list_head), GFP_KERNEL); + if (!tmigr_level_list) + goto err; + + for (i = 0; i < tmigr_hierarchy_levels; i++) + INIT_LIST_HEAD(&tmigr_level_list[i]); + + pr_info("Timer migration: %d hierarchy levels; %d children per group;" + " %d crossnode level\n", + tmigr_hierarchy_levels, TMIGR_CHILDREN_PER_GROUP, + tmigr_crossnode_level); + + ret = cpuhp_setup_state(CPUHP_AP_TMIGR_ONLINE, "tmigr:online", + tmigr_cpu_online, tmigr_cpu_offline); + if (ret) + goto err; + + return 0; + +err: + pr_err("Timer migration setup failed\n"); + return ret; +} +late_initcall(tmigr_init); diff --git a/kernel/time/timer_migration.h b/kernel/time/timer_migration.h new file mode 100644 index 000000000000..6c37d94a37d9 --- /dev/null +++ b/kernel/time/timer_migration.h @@ -0,0 +1,140 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef _KERNEL_TIME_MIGRATION_H +#define _KERNEL_TIME_MIGRATION_H + +/* Per group capacity. Must be a power of 2! */ +#define TMIGR_CHILDREN_PER_GROUP 8 + +/** + * struct tmigr_event - a timer event associated to a CPU + * @nextevt: The node to enqueue an event in the parent group queue + * @cpu: The CPU to which this event belongs + * @ignore: Hint whether the event could be ignored; it is set when + * CPU or group is active; + */ +struct tmigr_event { + struct timerqueue_node nextevt; + unsigned int cpu; + bool ignore; +}; + +/** + * struct tmigr_group - timer migration hierarchy group + * @lock: Lock protecting the event information and group hierarchy + * information during setup + * @parent: Pointer to the parent group + * @groupevt: Next event of the group which is only used when the + * group is !active. The group event is then queued into + * the parent timer queue. + * Ignore bit of @groupevt is set when the group is active. + * @next_expiry: Base monotonic expiry time of the next event of the + * group; It is used for the racy lockless check whether a + * remote expiry is required; it is always reliable + * @events: Timer queue for child events queued in the group + * @migr_state: State of the group (see union tmigr_state) + * @level: Hierarchy level of the group; Required during setup + * @numa_node: Required for setup only to make sure CPU and low level + * group information is NUMA local. It is set to NUMA node + * as long as the group level is per NUMA node (level < + * tmigr_crossnode_level); otherwise it is set to + * NUMA_NO_NODE + * @num_children: Counter of group children to make sure the group is only + * filled with TMIGR_CHILDREN_PER_GROUP; Required for setup + * only + * @childmask: childmask of the group in the parent group; is set + * during setup and will never change; can be read + * lockless + * @list: List head that is added to the per level + * tmigr_level_list; is required during setup when a + * new group needs to be connected to the existing + * hierarchy groups + */ +struct tmigr_group { + raw_spinlock_t lock; + struct tmigr_group *parent; + struct tmigr_event groupevt; + u64 next_expiry; + struct timerqueue_head events; + atomic_t migr_state; + unsigned int level; + int numa_node; + unsigned int num_children; + u8 childmask; + struct list_head list; +}; + +/** + * struct tmigr_cpu - timer migration per CPU group + * @lock: Lock protecting the tmigr_cpu group information + * @online: Indicates whether the CPU is online; In deactivate path + * it is required to know whether the migrator in the top + * level group is to be set offline, while a timer is + * pending. Then another online CPU needs to be notified to + * take over the migrator role. Furthermore the information + * is required in CPU hotplug path as the CPU is able to go + * idle before the timer migration hierarchy hotplug AP is + * reached. During this phase, the CPU has to handle the + * global timers on its own and must not act as a migrator. + * @idle: Indicates whether the CPU is idle in the timer migration + * hierarchy + * @remote: Is set when timers of the CPU are expired remotely + * @tmgroup: Pointer to the parent group + * @childmask: childmask of tmigr_cpu in the parent group + * @wakeup: Stores the first timer when the timer migration + * hierarchy is completely idle and remote expiry was done; + * is returned to timer code in the idle path and is only + * used in idle path. + * @cpuevt: CPU event which could be enqueued into the parent group + */ +struct tmigr_cpu { + raw_spinlock_t lock; + bool online; + bool idle; + bool remote; + struct tmigr_group *tmgroup; + u8 childmask; + u64 wakeup; + struct tmigr_event cpuevt; +}; + +/** + * union tmigr_state - state of tmigr_group + * @state: Combined version of the state - only used for atomic + * read/cmpxchg function + * @struct: Split version of the state - only use the struct members to + * update information to stay independent of endianness + */ +union tmigr_state { + u32 state; + /** + * struct - split state of tmigr_group + * @active: Contains each childmask bit of the active children + * @migrator: Contains childmask of the child which is migrator + * @seq: Sequence counter needs to be increased when an update + * to the tmigr_state is done. It prevents a race when + * updates in the child groups are propagated in changed + * order. Detailed information about the scenario is + * given in the documentation at the begin of + * timer_migration.c. + */ + struct { + u8 active; + u8 migrator; + u16 seq; + } __packed; +}; + +#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON) +extern void tmigr_handle_remote(void); +extern bool tmigr_requires_handle_remote(void); +extern void tmigr_cpu_activate(void); +extern u64 tmigr_cpu_deactivate(u64 nextevt); +extern u64 tmigr_cpu_new_timer(u64 nextevt); +extern u64 tmigr_quick_check(u64 nextevt); +#else +static inline void tmigr_handle_remote(void) { } +static inline bool tmigr_requires_handle_remote(void) { return false; } +static inline void tmigr_cpu_activate(void) { } +#endif + +#endif -- cgit v1.3.1 From b2cf7507e18649a30512515ec0ca89f26b2c2d0f Mon Sep 17 00:00:00 2001 From: Anna-Maria Behnsen Date: Wed, 21 Feb 2024 10:05:48 +0100 Subject: timers: Always queue timers on the local CPU The timer pull model is in place so we can remove the heuristics which try to guess the best target CPU at enqueue/modification time. All non pinned timers are queued on the local CPU in the separate storage and eventually pulled at expiry time to a remote CPU. Originally-by: Richard Cochran (linutronix GmbH) Signed-off-by: Anna-Maria Behnsen Signed-off-by: Thomas Gleixner Reviewed-by: Frederic Weisbecker Link: https://lore.kernel.org/r/20240221090548.36600-21-anna-maria@linutronix.de --- include/linux/timer.h | 14 ++++---------- kernel/time/timer.c | 36 +++++++++++++++--------------------- 2 files changed, 19 insertions(+), 31 deletions(-) (limited to 'include/linux') diff --git a/include/linux/timer.h b/include/linux/timer.h index 2be8be6dd317..14a633ba61d6 100644 --- a/include/linux/timer.h +++ b/include/linux/timer.h @@ -36,16 +36,10 @@ * workqueue locking issues. It's not meant for executing random crap * with interrupts disabled. Abuse is monitored! * - * @TIMER_PINNED: A pinned timer will not be affected by any timer - * placement heuristics (like, NOHZ) and will always expire on the CPU - * on which the timer was enqueued. - * - * Note: Because enqueuing of timers can migrate the timer from one - * CPU to another, pinned timers are not guaranteed to stay on the - * initialy selected CPU. They move to the CPU on which the enqueue - * function is invoked via mod_timer() or add_timer(). If the timer - * should be placed on a particular CPU, then add_timer_on() has to be - * used. + * @TIMER_PINNED: A pinned timer will always expire on the CPU on which the + * timer was enqueued. When a particular CPU is required, add_timer_on() + * has to be used. Enqueue via mod_timer() and add_timer() is always done + * on the local CPU. */ #define TIMER_CPUMASK 0x0003FFFF #define TIMER_MIGRATING 0x00040000 diff --git a/kernel/time/timer.c b/kernel/time/timer.c index 3ed135c8de43..4f4930da6448 100644 --- a/kernel/time/timer.c +++ b/kernel/time/timer.c @@ -635,11 +635,16 @@ trigger_dyntick_cpu(struct timer_base *base, struct timer_list *timer) /* * We might have to IPI the remote CPU if the base is idle and the - * timer is not deferrable. If the other CPU is on the way to idle - * then it can't set base->is_idle as we hold the base lock: + * timer is pinned. If it is a non pinned timer, it is only queued + * on the remote CPU, when timer was running during queueing. Then + * everything is handled by remote CPU anyway. If the other CPU is + * on the way to idle then it can't set base->is_idle as we hold + * the base lock: */ - if (base->is_idle) + if (base->is_idle) { + WARN_ON_ONCE(!(timer->flags & TIMER_PINNED)); wake_up_nohz_cpu(base->cpu); + } } /* @@ -986,17 +991,6 @@ static inline struct timer_base *get_timer_base(u32 tflags) return get_timer_cpu_base(tflags, tflags & TIMER_CPUMASK); } -static inline struct timer_base * -get_target_base(struct timer_base *base, unsigned tflags) -{ -#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON) - if (static_branch_likely(&timers_migration_enabled) && - !(tflags & TIMER_PINNED)) - return get_timer_cpu_base(tflags, get_nohz_timer_target()); -#endif - return get_timer_this_cpu_base(tflags); -} - static inline void __forward_timer_base(struct timer_base *base, unsigned long basej) { @@ -1151,7 +1145,7 @@ __mod_timer(struct timer_list *timer, unsigned long expires, unsigned int option if (!ret && (options & MOD_TIMER_PENDING_ONLY)) goto out_unlock; - new_base = get_target_base(base, timer->flags); + new_base = get_timer_this_cpu_base(timer->flags); if (base != new_base) { /* @@ -2297,7 +2291,7 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem, * granularity skew (by design). */ if (!base_local->is_idle && time_after(nextevt, basej + 1)) { - base_local->is_idle = base_global->is_idle = true; + base_local->is_idle = true; trace_timer_base_idle(true, base_local->cpu); } *idle = base_local->is_idle; @@ -2363,13 +2357,13 @@ u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle) void timer_clear_idle(void) { /* - * We do this unlocked. The worst outcome is a remote enqueue sending - * a pointless IPI, but taking the lock would just make the window for - * sending the IPI a few instructions smaller for the cost of taking - * the lock in the exit from idle path. + * We do this unlocked. The worst outcome is a remote pinned timer + * enqueue sending a pointless IPI, but taking the lock would just + * make the window for sending the IPI a few instructions smaller + * for the cost of taking the lock in the exit from idle + * path. Required for BASE_LOCAL only. */ __this_cpu_write(timer_bases[BASE_LOCAL].is_idle, false); - __this_cpu_write(timer_bases[BASE_GLOBAL].is_idle, false); trace_timer_base_idle(false, smp_processor_id()); /* Activate without holding the timer_base->lock */ -- cgit v1.3.1 From 3ad6eb0683a1edbb4bb117b85d61f17a879155a1 Mon Sep 17 00:00:00 2001 From: Frederic Weisbecker Date: Sun, 25 Feb 2024 23:54:59 +0100 Subject: tick: Start centralizing tick related CPU hotplug operations During the CPU offlining process, the various timer tick features are shut down from scattered places, sometimes from teardown callbacks on stop machine, sometimes through explicit calls, sometimes from the control CPU after the CPU died. The reason why these shutdown operations are spread around is not always clear and it makes the tick lifecycle hard to follow. The tick should be shut down in order from highest to lowest level: On stop machine from the dying CPU (high-level): 1) Hand-over the timekeeping duty (tick_handover_do_timer()) 2) Cancel the tick implementation called by the clockevent callback (tick_cancel_sched_timer()) 3) Shutdown broadcasting (tick_offline_cpu() / tick_broadcast_offline()) On stop machine from the dying CPU (low-level): 4) Shutdown clockevents drivers (CPUHP_AP_*_TIMER_STARTING states) From the control CPU after the CPU died (low-level): 5) Shutdown/unregister/cleanup clockevents for the dead CPU (tick_cleanup_dead_cpu()) Instead the current order is 2, 4 (both from CPU hotplug states), then 1 and 3 through direct calls. This layout and order don't make much sense. The operations 1, 2, 3 should be gathered together and in order. Sort this situation with creating a new TICK shut-down CPU hotplug state and start with introducing the timekeeping duty hand-over there. The state must precede hrtimers migration because the tick hrtimer will be stopped from it in a further patch. Signed-off-by: Frederic Weisbecker Signed-off-by: Thomas Gleixner Reviewed-by: Thomas Gleixner Link: https://lore.kernel.org/r/20240225225508.11587-8-frederic@kernel.org --- include/linux/cpuhotplug.h | 1 + include/linux/tick.h | 8 ++++++-- kernel/cpu.c | 8 +++++--- kernel/time/tick-common.c | 17 +++++++++++------ 4 files changed, 23 insertions(+), 11 deletions(-) (limited to 'include/linux') diff --git a/include/linux/cpuhotplug.h b/include/linux/cpuhotplug.h index 7651904c6db5..35e78ddb2b37 100644 --- a/include/linux/cpuhotplug.h +++ b/include/linux/cpuhotplug.h @@ -184,6 +184,7 @@ enum cpuhp_state { CPUHP_AP_ARM64_ISNDEP_STARTING, CPUHP_AP_SMPCFD_DYING, CPUHP_AP_HRTIMERS_DYING, + CPUHP_AP_TICK_DYING, CPUHP_AP_X86_TBOOT_DYING, CPUHP_AP_ARM_CACHE_B15_RAC_DYING, CPUHP_AP_ONLINE, diff --git a/include/linux/tick.h b/include/linux/tick.h index 716d17f31c45..afff4c207bd8 100644 --- a/include/linux/tick.h +++ b/include/linux/tick.h @@ -19,16 +19,20 @@ extern void __init tick_init(void); extern void tick_suspend_local(void); /* Should be core only, but XEN resume magic and ARM BL switcher require it */ extern void tick_resume_local(void); -extern void tick_handover_do_timer(void); extern void tick_cleanup_dead_cpu(int cpu); #else /* CONFIG_GENERIC_CLOCKEVENTS */ static inline void tick_init(void) { } static inline void tick_suspend_local(void) { } static inline void tick_resume_local(void) { } -static inline void tick_handover_do_timer(void) { } static inline void tick_cleanup_dead_cpu(int cpu) { } #endif /* !CONFIG_GENERIC_CLOCKEVENTS */ +#if defined(CONFIG_GENERIC_CLOCKEVENTS) && defined(CONFIG_HOTPLUG_CPU) +extern int tick_cpu_dying(unsigned int cpu); +#else +#define tick_cpu_dying NULL +#endif + #if defined(CONFIG_GENERIC_CLOCKEVENTS) && defined(CONFIG_SUSPEND) extern void tick_freeze(void); extern void tick_unfreeze(void); diff --git a/kernel/cpu.c b/kernel/cpu.c index e6ec3ba4950b..263508073da8 100644 --- a/kernel/cpu.c +++ b/kernel/cpu.c @@ -1324,8 +1324,6 @@ static int take_cpu_down(void *_param) */ cpuhp_invoke_callback_range_nofail(false, cpu, st, target); - /* Give up timekeeping duties */ - tick_handover_do_timer(); /* Remove CPU from timer broadcasting */ tick_offline_cpu(cpu); /* Park the stopper thread */ @@ -2205,7 +2203,11 @@ static struct cpuhp_step cpuhp_hp_states[] = { .startup.single = NULL, .teardown.single = hrtimers_cpu_dying, }, - + [CPUHP_AP_TICK_DYING] = { + .name = "tick:dying", + .startup.single = NULL, + .teardown.single = tick_cpu_dying, + }, /* Entry state on starting. Interrupts enabled from here on. Transient * state for synchronsization */ [CPUHP_AP_ONLINE] = { diff --git a/kernel/time/tick-common.c b/kernel/time/tick-common.c index 0084e1ae2583..a89ef450fda7 100644 --- a/kernel/time/tick-common.c +++ b/kernel/time/tick-common.c @@ -397,15 +397,20 @@ EXPORT_SYMBOL_GPL(tick_broadcast_oneshot_control); #ifdef CONFIG_HOTPLUG_CPU /* - * Transfer the do_timer job away from a dying cpu. - * - * Called with interrupts disabled. No locking required. If - * tick_do_timer_cpu is owned by this cpu, nothing can change it. + * Stop the tick and transfer the timekeeping job away from a dying cpu. */ -void tick_handover_do_timer(void) +int tick_cpu_dying(unsigned int dying_cpu) { - if (tick_do_timer_cpu == smp_processor_id()) + /* + * If the current CPU is the timekeeper, it's the only one that + * can safely hand over its duty. Also all online CPUs are in + * stop machine, guaranteed not to be idle, therefore it's safe + * to pick any online successor. + */ + if (tick_do_timer_cpu == dying_cpu) tick_do_timer_cpu = cpumask_first(cpu_online_mask); + + return 0; } /* -- cgit v1.3.1 From ef8969bb552c1c75e997a42d3e2c576b6ed4025a Mon Sep 17 00:00:00 2001 From: Frederic Weisbecker Date: Sun, 25 Feb 2024 23:55:01 +0100 Subject: tick: Move broadcast cancellation up to CPUHP_AP_TICK_DYING The broadcast shutdown code is executed through a random explicit call within stop machine from the outgoing CPU. However the tick broadcast is a midware between the tick callback and the clocksource, therefore it makes more sense to shut it down after the tick callback and before the clocksource drivers. Move it instead to the common tick shutdown CPU hotplug state where related operations can be ordered from highest to lowest level. Signed-off-by: Frederic Weisbecker Signed-off-by: Thomas Gleixner Reviewed-by: Thomas Gleixner Link: https://lore.kernel.org/r/20240225225508.11587-10-frederic@kernel.org --- include/linux/tick.h | 6 ------ kernel/cpu.c | 2 -- kernel/time/tick-common.c | 3 +++ kernel/time/tick-internal.h | 2 ++ 4 files changed, 5 insertions(+), 8 deletions(-) (limited to 'include/linux') diff --git a/include/linux/tick.h b/include/linux/tick.h index afff4c207bd8..c7840ae8ebaf 100644 --- a/include/linux/tick.h +++ b/include/linux/tick.h @@ -73,12 +73,6 @@ extern void tick_broadcast_control(enum tick_broadcast_mode mode); static inline void tick_broadcast_control(enum tick_broadcast_mode mode) { } #endif /* BROADCAST */ -#if defined(CONFIG_GENERIC_CLOCKEVENTS_BROADCAST) && defined(CONFIG_HOTPLUG_CPU) -extern void tick_offline_cpu(unsigned int cpu); -#else -static inline void tick_offline_cpu(unsigned int cpu) { } -#endif - #ifdef CONFIG_GENERIC_CLOCKEVENTS extern int tick_broadcast_oneshot_control(enum tick_broadcast_state state); #else diff --git a/kernel/cpu.c b/kernel/cpu.c index 263508073da8..5a8ad4f5ccf3 100644 --- a/kernel/cpu.c +++ b/kernel/cpu.c @@ -1324,8 +1324,6 @@ static int take_cpu_down(void *_param) */ cpuhp_invoke_callback_range_nofail(false, cpu, st, target); - /* Remove CPU from timer broadcasting */ - tick_offline_cpu(cpu); /* Park the stopper thread */ stop_machine_park(cpu); return 0; diff --git a/kernel/time/tick-common.c b/kernel/time/tick-common.c index b4af8c743b73..522414089c0d 100644 --- a/kernel/time/tick-common.c +++ b/kernel/time/tick-common.c @@ -412,6 +412,9 @@ int tick_cpu_dying(unsigned int dying_cpu) tick_cancel_sched_timer(dying_cpu); + /* Remove CPU from timer broadcasting */ + tick_offline_cpu(dying_cpu); + return 0; } diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h index a3243c4ac45f..5f2105e637bd 100644 --- a/kernel/time/tick-internal.h +++ b/kernel/time/tick-internal.h @@ -142,8 +142,10 @@ static inline bool tick_broadcast_oneshot_available(void) { return tick_oneshot_ #endif /* !(BROADCAST && ONESHOT) */ #if defined(CONFIG_GENERIC_CLOCKEVENTS_BROADCAST) && defined(CONFIG_HOTPLUG_CPU) +extern void tick_offline_cpu(unsigned int cpu); extern void tick_broadcast_offline(unsigned int cpu); #else +static inline void tick_offline_cpu(unsigned int cpu) { } static inline void tick_broadcast_offline(unsigned int cpu) { } #endif -- cgit v1.3.1 From 500f8f9bced86f0c0f2482773bd64a1b7ec9c4e1 Mon Sep 17 00:00:00 2001 From: Frederic Weisbecker Date: Sun, 25 Feb 2024 23:55:07 +0100 Subject: tick: Assume timekeeping is correctly handed over upon last offline idle call The timekeeping duty is handed over from the outgoing CPU on stop machine, then the oneshot tick is stopped right after. Therefore it's guaranteed that the current CPU isn't the timekeeper upon its last call to idle. Besides, calling tick_nohz_idle_stop_tick() while the dying CPU goes into idle suggests that the tick is going to be stopped while it is actually stopped already from the appropriate CPU hotplug state. Remove the confusing call and the obsolete case handling and convert it to a sanity check that verifies the above assumption. Signed-off-by: Frederic Weisbecker Signed-off-by: Thomas Gleixner Reviewed-by: Thomas Gleixner Link: https://lore.kernel.org/r/20240225225508.11587-16-frederic@kernel.org --- include/linux/tick.h | 2 ++ kernel/cpu.c | 1 + kernel/sched/idle.c | 1 - kernel/time/tick-common.c | 4 ++++ kernel/time/tick-sched.c | 13 +------------ 5 files changed, 8 insertions(+), 13 deletions(-) (limited to 'include/linux') diff --git a/include/linux/tick.h b/include/linux/tick.h index c7840ae8ebaf..44fddfa93e18 100644 --- a/include/linux/tick.h +++ b/include/linux/tick.h @@ -29,8 +29,10 @@ static inline void tick_cleanup_dead_cpu(int cpu) { } #if defined(CONFIG_GENERIC_CLOCKEVENTS) && defined(CONFIG_HOTPLUG_CPU) extern int tick_cpu_dying(unsigned int cpu); +extern void tick_assert_timekeeping_handover(void); #else #define tick_cpu_dying NULL +static inline void tick_assert_timekeeping_handover(void) { } #endif #if defined(CONFIG_GENERIC_CLOCKEVENTS) && defined(CONFIG_SUSPEND) diff --git a/kernel/cpu.c b/kernel/cpu.c index 5a8ad4f5ccf3..7e84a7b0675e 100644 --- a/kernel/cpu.c +++ b/kernel/cpu.c @@ -1399,6 +1399,7 @@ void cpuhp_report_idle_dead(void) struct cpuhp_cpu_state *st = this_cpu_ptr(&cpuhp_state); BUG_ON(st->state != CPUHP_AP_OFFLINE); + tick_assert_timekeeping_handover(); rcutree_report_cpu_dead(); st->state = CPUHP_AP_IDLE_DEAD; /* diff --git a/kernel/sched/idle.c b/kernel/sched/idle.c index 31231925f1ec..b15d40cad7ea 100644 --- a/kernel/sched/idle.c +++ b/kernel/sched/idle.c @@ -291,7 +291,6 @@ static void do_idle(void) local_irq_disable(); if (cpu_is_offline(cpu)) { - tick_nohz_idle_stop_tick(); cpuhp_report_idle_dead(); arch_cpu_idle_dead(); } diff --git a/kernel/time/tick-common.c b/kernel/time/tick-common.c index 9cd09eea06d6..fb0fdec8719a 100644 --- a/kernel/time/tick-common.c +++ b/kernel/time/tick-common.c @@ -396,6 +396,10 @@ int tick_broadcast_oneshot_control(enum tick_broadcast_state state) EXPORT_SYMBOL_GPL(tick_broadcast_oneshot_control); #ifdef CONFIG_HOTPLUG_CPU +void tick_assert_timekeeping_handover(void) +{ + WARN_ON_ONCE(tick_do_timer_cpu == smp_processor_id()); +} /* * Stop the tick and transfer the timekeeping job away from a dying cpu. */ diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c index 89d16b8ea2c4..269e21590df5 100644 --- a/kernel/time/tick-sched.c +++ b/kernel/time/tick-sched.c @@ -1160,18 +1160,7 @@ static bool report_idle_softirq(void) static bool can_stop_idle_tick(int cpu, struct tick_sched *ts) { - /* - * If this CPU is offline and it is the one which updates - * jiffies, then give up the assignment and let it be taken by - * the CPU which runs the tick timer next. If we don't drop - * this here, the jiffies might be stale and do_timer() never - * gets invoked. - */ - if (unlikely(!cpu_online(cpu))) { - if (cpu == tick_do_timer_cpu) - tick_do_timer_cpu = TICK_DO_TIMER_NONE; - return false; - } + WARN_ON_ONCE(cpu_is_offline(cpu)); if (unlikely(!tick_sched_flag_test(ts, TS_FLAG_NOHZ))) return false; -- cgit v1.3.1