[PATCH v5 00/18] timer: Move from a push remote at enqueue to a pull at expiry model

[PATCH v5 00/18] timer: Move from a push remote at enqueue to a pull at expiry model

[Anna-Maria Behnsen]

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 a idle
timerqueue and eventually expired by some other 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 seperated 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.


Testing
~~~~~~~

The impact of wasting cycles during enqueue by using the heuristic in
contrast to always queueing the timer on the local CPU was measured with a
micro benchmark. Therefore a timer is enqueued and dequeued in a loop with
1000 repetitions on a isolated CPU. The time the loop takes is measured. A
quater of the remaining CPUs was kept busy. This measurement was repeated
several times. With the patch queue the average duration was reduced by
approximately 25%.

	145ns	plain v6
	109ns	v6 with patch queue


Furthermore the impact of residence in deep idle states of an idle system
was investigated. The patch queue doesn't downgrade this behavior.


During testing on a mostly idle machine a ping pong game could be observed:
a process_timeout timer is expired remotely on a non idle CPU. Then the CPU
where the schedule_timeout() was executed to enqueue the timer comes out of
idle and restarts the timer using schedule_timeout() and goes back to idle
again. This is due to the fair scheduler which tries to keep the task on
the CPU which it previously executed on.


Next Steps
~~~~~~~~~~

Simple deferrable timers are no longer required as they can be converted to
global timers. If a CPU goes idle, a formerly deferrable timer will not
prevent the CPU to sleep as long as possible. Only the last migrator CPU
has to take care of them. Deferrable timers with timer pinned flags needs
to be expired on the specified CPU but must not prevent CPU from going
idle. They require their own timer base which is never taken into account
when calculating the next expiry time. This conversation and required
cleanup will be done in a follow up series.

v4..v5:
  - address review feedback of Frederic Weisbecker
  - fix issue with group timer update after remote expiry

v3..v4:
  - address review feedback of Frederic Weisbecker
  - address kernel test robot fallout
  - Move patch 16 "add_timer_on(): Make sure callers have TIMER_PINNED
    flag" at the begin of the queue to prevent timers to end up in global
    timer base when they were queued using add_timer_on()
  - Fix some comments and typos

v2..v3: https://lore.kernel.org/r/20170418111102.490432548@linutronix.de/
  - Minimize usage of locks by storing data using atomic_cmpxchg() for
    migrator information and information about active cpus.


Thanks,

	Anna-Maria


Anna-Maria Behnsen (15):
  tick-sched: Warn when next tick seems to be in the past
  timer: Add comment to get_next_timer_interrupt() description
  timer: Move store of next event into __next_timer_interrupt()
  timer: Split next timer interrupt logic
  add_timer_on(): Make sure callers have TIMER_PINNED flag
  timers: Ease code in run_local_timers()
  timers: Create helper function to forward timer base clk
  timer: Keep the pinned timers separate from the others
  timer: Retrieve next expiry of pinned/non-pinned timers seperately
  timer: Split out "get next timer interrupt" functionality
  timer: Add get next timer interrupt functionality for remote CPUs
  timer: Check if timers base is handled already
  timer: Implement the hierarchical pull model
  timer_migration: Add tracepoints
  timer: Always queue timers on the local CPU

Richard Cochran (linutronix GmbH) (2):
  timer: Restructure internal locking
  tick/sched: Split out jiffies update helper function

Thomas Gleixner (1):
  timer: Rework idle logic

 arch/x86/kernel/tsc_sync.c             |    3 +-
 drivers/char/random.c                  |    2 +-
 include/linux/cpuhotplug.h             |    1 +
 include/linux/timer.h                  |    5 +-
 include/trace/events/timer_migration.h |  277 +++++
 kernel/time/Makefile                   |    3 +
 kernel/time/clocksource.c              |    2 +-
 kernel/time/tick-internal.h            |    9 +
 kernel/time/tick-sched.c               |   20 +-
 kernel/time/timer.c                    |  370 +++++--
 kernel/time/timer_migration.c          | 1279 ++++++++++++++++++++++++
 kernel/time/timer_migration.h          |  123 +++
 kernel/workqueue.c                     |   15 +-
 13 files changed, 2017 insertions(+), 92 deletions(-)
 create mode 100644 include/trace/events/timer_migration.h
 create mode 100644 kernel/time/timer_migration.c
 create mode 100644 kernel/time/timer_migration.h

-- 
2.30.2

[PATCH v5 01/18] tick-sched: Warn when next tick seems to be in the past

[Anna-Maria Behnsen]

When the next tick is in the past, the delta between basemono and the next
tick gets negativ. But the next tick should never be in the past. The
negative effect of a wrong next tick might be a stop of the tick and timers
might expire late.

To prevent expensive debugging when changing underlying code, add a
WARN_ON_ONCE into this code path.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
Reviewed-by: Thomas Gleixner <tglx@linutronix.de>
Reviewed-by: Frederic Weisbecker <frederic@kernel.org>
---
 kernel/time/tick-sched.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index b0e3c9205946..7ffdc7ba19b4 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -826,6 +826,8 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
 	 * If the tick is due in the next period, keep it ticking or
 	 * force prod the timer.
 	 */
+	WARN_ON_ONCE(basemono > next_tick);
+
 	delta = next_tick - basemono;
 	if (delta <= (u64)TICK_NSEC) {
 		/*
-- 
2.30.2

[PATCH v5 02/18] timer: Add comment to get_next_timer_interrupt() description

[Anna-Maria Behnsen]

get_next_timer_interrupt() does more than simply getting the next timer
interrupt. The timer bases are forwarded and also marked as idle whenever
possible.

To get not confused, add a comment to function description.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
v5: New patch, which adds only a comment to get_next_timer_interrupt()
instead of changing the function name
---
 kernel/time/timer.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 63a8ce7177dd..ffb94bc3852f 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1915,6 +1915,10 @@ static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
  * @basej:	base time jiffies
  * @basem:	base time clock monotonic
  *
+ * If required, base->clk is forwarded and base is also marked as
+ * idle. Idle handling of timer bases is allowed only to be done by CPU
+ * itself.
+ *
  * Returns the tick aligned clock monotonic time of the next pending
  * timer or KTIME_MAX if no timer is pending.
  */
-- 
2.30.2

[PATCH v5 03/18] timer: Move store of next event into __next_timer_interrupt()

[Anna-Maria Behnsen]

Both call sides of __next_timer_interrupt() store return value directly in
base->next_expiry. Move the store into __next_timer_interrupt() and to make
purpose more clear, rename function to next_expiry_recalc().

No functional change.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
Reviewed-by: Thomas Gleixner <tglx@linutronix.de>
---
 kernel/time/timer.c | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index ffb94bc3852f..08e855727ff8 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1803,8 +1803,10 @@ static int next_pending_bucket(struct timer_base *base, unsigned offset,
 /*
  * Search the first expiring timer in the various clock levels. Caller must
  * hold base->lock.
+ *
+ * Store next expiry time in base->next_expiry.
  */
-static unsigned long __next_timer_interrupt(struct timer_base *base)
+static void next_expiry_recalc(struct timer_base *base)
 {
 	unsigned long clk, next, adj;
 	unsigned lvl, offset = 0;
@@ -1870,10 +1872,11 @@ static unsigned long __next_timer_interrupt(struct timer_base *base)
 		clk += adj;
 	}
 
+	base->next_expiry = next;
 	base->next_expiry_recalc = false;
 	base->timers_pending = !(next == base->clk + NEXT_TIMER_MAX_DELTA);
 
-	return next;
+	return;
 }
 
 #ifdef CONFIG_NO_HZ_COMMON
@@ -1937,7 +1940,7 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 
 	raw_spin_lock(&base->lock);
 	if (base->next_expiry_recalc)
-		base->next_expiry = __next_timer_interrupt(base);
+		next_expiry_recalc(base);
 	nextevt = base->next_expiry;
 
 	/*
@@ -2020,7 +2023,7 @@ static inline void __run_timers(struct timer_base *base)
 		WARN_ON_ONCE(!levels && !base->next_expiry_recalc
 			     && base->timers_pending);
 		base->clk++;
-		base->next_expiry = __next_timer_interrupt(base);
+		next_expiry_recalc(base);
 
 		while (levels--)
 			expire_timers(base, heads + levels);
-- 
2.30.2

[PATCH v5 04/18] timer: Split next timer interrupt logic

[Anna-Maria Behnsen]

Logic for getting next timer interrupt (no matter of recalculated or
already stored in base->next_expiry) is split into a separate function
"next_timer_interrupt()" to make it available for new call sites.

No functional change.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
Reviewed-by: Thomas Gleixner <tglx@linutronix.de>
Reviewed-by: Frederic Weisbecker <frederic@kernel.org>
---
 kernel/time/timer.c | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 08e855727ff8..9e6c2058889b 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1913,6 +1913,14 @@ static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
 	return DIV_ROUND_UP_ULL(nextevt, TICK_NSEC) * TICK_NSEC;
 }
 
+static unsigned long next_timer_interrupt(struct timer_base *base)
+{
+	if (base->next_expiry_recalc)
+		next_expiry_recalc(base);
+
+	return base->next_expiry;
+}
+
 /**
  * get_next_timer_interrupt - return the time (clock mono) of the next timer
  * @basej:	base time jiffies
@@ -1939,9 +1947,8 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 		return expires;
 
 	raw_spin_lock(&base->lock);
-	if (base->next_expiry_recalc)
-		next_expiry_recalc(base);
-	nextevt = base->next_expiry;
+
+	nextevt = next_timer_interrupt(base);
 
 	/*
 	 * We have a fresh next event. Check whether we can forward the
-- 
2.30.2

[PATCH v5 05/18] timer: Rework idle logic

[Anna-Maria Behnsen]

From: Thomas Gleixner <tglx@linutronix.de>

To improve readability of the code, split base->idle calculation and
expires calculation into separate parts.

Thereby the following subtle change happens if the next event is just one
jiffy ahead and the tick was already stopped: Originally base->is_idle
remains true in this situation. Now base->is_idle turns to false. This may
spare an IPI if a timer is enqueued remotely to an idle CPU that is going
to tick on the next jiffy.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
Reviewed-by: Frederic Weisbecker <frederic@kernel.org>
---
 kernel/time/timer.c | 29 ++++++++++++++---------------
 1 file changed, 14 insertions(+), 15 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 9e6c2058889b..d74d538e06a2 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1962,21 +1962,20 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 			base->clk = nextevt;
 	}
 
-	if (time_before_eq(nextevt, basej)) {
-		expires = basem;
-		base->is_idle = false;
-	} else {
-		if (base->timers_pending)
-			expires = basem + (u64)(nextevt - basej) * TICK_NSEC;
-		/*
-		 * If we expect to sleep more than a tick, mark the base idle.
-		 * Also the tick is stopped so any added timer must forward
-		 * the base clk itself to keep granularity small. This idle
-		 * logic is only maintained for the BASE_STD base, deferrable
-		 * timers may still see large granularity skew (by design).
-		 */
-		if ((expires - basem) > TICK_NSEC)
-			base->is_idle = true;
+	/*
+	 * Base is idle if the next event is more than a tick away. Also
+	 * the tick is stopped so any added timer must forward the base clk
+	 * itself to keep granularity small. This idle logic is only
+	 * maintained for the BASE_STD base, deferrable timers may still
+	 * see large granularity skew (by design).
+	 */
+	base->is_idle = time_after(nextevt, basej + 1);
+
+	if (base->timers_pending) {
+		/* If we missed a tick already, force 0 delta */
+		if (time_before(nextevt, basej))
+			nextevt = basej;
+		expires = basem + (u64)(nextevt - basej) * TICK_NSEC;
 	}
 	raw_spin_unlock(&base->lock);
 
-- 
2.30.2

[PATCH v5 06/18] add_timer_on(): Make sure callers have TIMER_PINNED flag

[Anna-Maria Behnsen]

The implementation of the hierachical timer pull model will change the
timer bases per CPU. Timers, that have to expire on a specific CPU, require
the TIMER_PINNED flag. Otherwise they will be queued on the dedicated CPU
but in global timer base and those timers could also expire on other
CPUs. Timers with TIMER_DEFERRABLE flag end up in a separate base anyway
and are executed on the local CPU only.

Therefore add the missing TIMER_PINNED flag for those callers who use
add_timer_on() without the flag. No functional change.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Dave Hansen <dave.hansen@linux.intel.com>
Cc: x86@kernel.org
Cc: "H. Peter Anvin" <hpa@zytor.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: "Jason A. Donenfeld" <Jason@zx2c4.com>
Cc: John Stultz <jstultz@google.com>
Cc: Stephen Boyd <sboyd@kernel.org>
Cc: Tejun Heo <tj@kernel.org>
Cc: Lai Jiangshan <jiangshanlai@gmail.com>
---
v5: Add comment in workqueue.c that it's only a workaround for now
---
 arch/x86/kernel/tsc_sync.c |  3 ++-
 drivers/char/random.c      |  2 +-
 kernel/time/clocksource.c  |  2 +-
 kernel/workqueue.c         | 15 +++++++++++++--
 4 files changed, 17 insertions(+), 5 deletions(-)

diff --git a/arch/x86/kernel/tsc_sync.c b/arch/x86/kernel/tsc_sync.c
index 9452dc9664b5..eab827288e0f 100644
--- a/arch/x86/kernel/tsc_sync.c
+++ b/arch/x86/kernel/tsc_sync.c
@@ -110,7 +110,8 @@ static int __init start_sync_check_timer(void)
 	if (!cpu_feature_enabled(X86_FEATURE_TSC_ADJUST) || tsc_clocksource_reliable)
 		return 0;
 
-	timer_setup(&tsc_sync_check_timer, tsc_sync_check_timer_fn, 0);
+	timer_setup(&tsc_sync_check_timer, tsc_sync_check_timer_fn,
+		    TIMER_PINNED);
 	tsc_sync_check_timer.expires = jiffies + SYNC_CHECK_INTERVAL;
 	add_timer(&tsc_sync_check_timer);
 
diff --git a/drivers/char/random.c b/drivers/char/random.c
index ce3ccd172cc8..db6a7c0695de 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1007,7 +1007,7 @@ static DEFINE_PER_CPU(struct fast_pool, irq_randomness) = {
 #define FASTMIX_PERM HSIPHASH_PERMUTATION
 	.pool = { HSIPHASH_CONST_0, HSIPHASH_CONST_1, HSIPHASH_CONST_2, HSIPHASH_CONST_3 },
 #endif
-	.mix = __TIMER_INITIALIZER(mix_interrupt_randomness, 0)
+	.mix = __TIMER_INITIALIZER(mix_interrupt_randomness, TIMER_PINNED)
 };
 
 /*
diff --git a/kernel/time/clocksource.c b/kernel/time/clocksource.c
index 91836b727cef..e982c119e3c9 100644
--- a/kernel/time/clocksource.c
+++ b/kernel/time/clocksource.c
@@ -561,7 +561,7 @@ static inline void clocksource_start_watchdog(void)
 {
 	if (watchdog_running || !watchdog || list_empty(&watchdog_list))
 		return;
-	timer_setup(&watchdog_timer, clocksource_watchdog, 0);
+	timer_setup(&watchdog_timer, clocksource_watchdog, TIMER_PINNED);
 	watchdog_timer.expires = jiffies + WATCHDOG_INTERVAL;
 	add_timer_on(&watchdog_timer, cpumask_first(cpu_online_mask));
 	watchdog_running = 1;
diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index b8b541caed48..a428d94084ee 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -1677,10 +1677,21 @@ static void __queue_delayed_work(int cpu, struct workqueue_struct *wq,
 	dwork->cpu = cpu;
 	timer->expires = jiffies + delay;
 
-	if (unlikely(cpu != WORK_CPU_UNBOUND))
+	if (unlikely(cpu != WORK_CPU_UNBOUND)) {
+		/*
+		 * TODO: Setting the flag is a workaround for now; needs to
+		 * be cleaned up with new work initializers and defines
+		 */
+		timer->flags |= TIMER_PINNED;
 		add_timer_on(timer, cpu);
-	else
+	} else {
+		/*
+		 * TODO: Resetting the flag is a workaround for now; needs
+		 * to be cleaned up with new work initializers and defines
+		 */
+		timer->flags &= ~TIMER_PINNED;
 		add_timer(timer);
+	}
 }
 
 /**
-- 
2.30.2

[PATCH v5 07/18] timers: Ease code in run_local_timers()

[Anna-Maria Behnsen]

The logic for raising a softirq the way it is implemented right now, is
readable for two timer bases. When increasing numbers of timer bases, code
gets harder to read. With the introduction of the timer migration
hierarchy, there will be three timer bases.

Therefore ease the code. No functional change.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
v5: New patch to decrease patch size of follow up patches
---
 kernel/time/timer.c | 14 ++++++--------
 1 file changed, 6 insertions(+), 8 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index d74d538e06a2..d3e1776b505b 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -2058,16 +2058,14 @@ static void run_local_timers(void)
 	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
 
 	hrtimer_run_queues();
-	/* Raise the softirq only if required. */
-	if (time_before(jiffies, base->next_expiry)) {
-		if (!IS_ENABLED(CONFIG_NO_HZ_COMMON))
-			return;
-		/* CPU is awake, so check the deferrable base. */
-		base++;
-		if (time_before(jiffies, base->next_expiry))
+
+	for (int i = 0; i < NR_BASES; i++, base++) {
+		/* Raise the softirq only if required. */
+		if (time_after_eq(jiffies, base->next_expiry)) {
+			raise_softirq(TIMER_SOFTIRQ);
 			return;
+		}
 	}
-	raise_softirq(TIMER_SOFTIRQ);
 }
 
 /*
-- 
2.30.2

[PATCH v5 08/18] timers: Create helper function to forward timer base clk

[Anna-Maria Behnsen]

The logic for forwarding timer base clock is splitted into a separte
function to make it accessible for other call sites.

No functional change.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
v5: New patch to simplify next patch
---
 kernel/time/timer.c | 25 +++++++++++++++++--------
 1 file changed, 17 insertions(+), 8 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index d3e1776b505b..1629ccf24dd0 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1921,6 +1921,21 @@ static unsigned long next_timer_interrupt(struct timer_base *base)
 	return base->next_expiry;
 }
 
+/*
+ * Forward base clock is done only when @basej is past base->clk, otherwise
+ * base-clk might be rewind.
+ */
+static void forward_base_clk(struct timer_base *base, unsigned long nextevt,
+			     unsigned long basej)
+{
+	if (time_after(basej, base->clk)) {
+		if (time_after(nextevt, basej))
+			base->clk = basej;
+		else if (time_after(nextevt, base->clk))
+			base->clk = nextevt;
+	}
+}
+
 /**
  * get_next_timer_interrupt - return the time (clock mono) of the next timer
  * @basej:	base time jiffies
@@ -1952,15 +1967,9 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 
 	/*
 	 * We have a fresh next event. Check whether we can forward the
-	 * base. We can only do that when @basej is past base->clk
-	 * otherwise we might rewind base->clk.
+	 * base.
 	 */
-	if (time_after(basej, base->clk)) {
-		if (time_after(nextevt, basej))
-			base->clk = basej;
-		else if (time_after(nextevt, base->clk))
-			base->clk = nextevt;
-	}
+	forward_base_clk(base, nextevt, basej);
 
 	/*
 	 * Base is idle if the next event is more than a tick away. Also
-- 
2.30.2

[PATCH v5 09/18] timer: Keep the pinned timers separate from the others

[Anna-Maria Behnsen]

Separate the storage space for pinned timers. Deferrable timers (doesn't
matter if pinned or non pinned) are still enqueued into their own base.

This is preparatory work for changing the NOHZ timer placement from a push
at enqueue time to a pull at expiry time model.

When a timer is added via add_timer_on(), TIMER_PINNED flag is required to
ensure it expires on the specified CPU. Otherwise it will be enqueued in
the global timer base which could be expired by a remote CPU. WARN_ONCE()
is added to prevent misuse.

Beside of that no functional change because all callers of add_timer_on()
already use TIMER_PINNED flag.

Originally-by: Richard Cochran (linutronix GmbH) <richardcochran@gmail.com>
Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
Reviewed-by: Frederic Weisbecker <frederic@kernel.org>
---
v5:
  - Add WARN_ONCE() in add_timer_on()
  - Decrease patch size by splitting into three patches (this patch and the
    two before)
---
 kernel/time/timer.c | 91 +++++++++++++++++++++++++++++++++------------
 1 file changed, 68 insertions(+), 23 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 1629ccf24dd0..7656eab1bf20 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -187,12 +187,18 @@ EXPORT_SYMBOL(jiffies_64);
 #define WHEEL_SIZE	(LVL_SIZE * LVL_DEPTH)
 
 #ifdef CONFIG_NO_HZ_COMMON
-# define NR_BASES	2
-# define BASE_STD	0
-# define BASE_DEF	1
+/*
+ * If multiple bases need to be locked, use the base ordering for lock
+ * nesting, i.e. lowest number first.
+ */
+# define NR_BASES	3
+# define BASE_LOCAL	0
+# define BASE_GLOBAL	1
+# define BASE_DEF	2
 #else
 # define NR_BASES	1
-# define BASE_STD	0
+# define BASE_LOCAL	0
+# define BASE_GLOBAL	0
 # define BASE_DEF	0
 #endif
 
@@ -902,7 +908,10 @@ static int detach_if_pending(struct timer_list *timer, struct timer_base *base,
 
 static inline struct timer_base *get_timer_cpu_base(u32 tflags, u32 cpu)
 {
-	struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_STD], cpu);
+	int index = tflags & TIMER_PINNED ? BASE_LOCAL : BASE_GLOBAL;
+	struct timer_base *base;
+
+	base = per_cpu_ptr(&timer_bases[index], cpu);
 
 	/*
 	 * If the timer is deferrable and NO_HZ_COMMON is set then we need
@@ -915,7 +924,10 @@ static inline struct timer_base *get_timer_cpu_base(u32 tflags, u32 cpu)
 
 static inline struct timer_base *get_timer_this_cpu_base(u32 tflags)
 {
-	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	int index = tflags & TIMER_PINNED ? BASE_LOCAL : BASE_GLOBAL;
+	struct timer_base *base;
+
+	base = this_cpu_ptr(&timer_bases[index]);
 
 	/*
 	 * If the timer is deferrable and NO_HZ_COMMON is set then we need
@@ -1264,6 +1276,12 @@ void add_timer_on(struct timer_list *timer, int cpu)
 	if (WARN_ON_ONCE(timer_pending(timer)))
 		return;
 
+	WARN_ONCE(!(timer->flags & TIMER_PINNED), "TIMER_PINNED flag for "
+		  "add_timer_on() is missing: timer=%p function=%ps",
+		  timer, timer->function);
+	/* Make sure timer flags have TIMER_PINNED flag set */
+	timer->flags |= TIMER_PINNED;
+
 	new_base = get_timer_cpu_base(timer->flags, cpu);
 
 	/*
@@ -1950,9 +1968,10 @@ static void forward_base_clk(struct timer_base *base, unsigned long nextevt,
  */
 u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 {
-	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	unsigned long nextevt, nextevt_local, nextevt_global;
+	struct timer_base *base_local, *base_global;
+	bool local_first, is_idle;
 	u64 expires = KTIME_MAX;
-	unsigned long nextevt;
 
 	/*
 	 * Pretend that there is no timer pending if the cpu is offline.
@@ -1961,32 +1980,57 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 	if (cpu_is_offline(smp_processor_id()))
 		return expires;
 
-	raw_spin_lock(&base->lock);
+	base_local = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
+	base_global = this_cpu_ptr(&timer_bases[BASE_GLOBAL]);
 
-	nextevt = next_timer_interrupt(base);
+	raw_spin_lock(&base_local->lock);
+	raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
+
+	nextevt_local = next_timer_interrupt(base_local);
+	nextevt_global = next_timer_interrupt(base_global);
 
 	/*
 	 * We have a fresh next event. Check whether we can forward the
 	 * base.
 	 */
-	forward_base_clk(base, nextevt, basej);
+	forward_base_clk(base_local, nextevt_local, basej);
+	forward_base_clk(base_global, nextevt_global, basej);
 
 	/*
-	 * Base is idle if the next event is more than a tick away. Also
+	 * Check whether the local event is expiring before or at the same
+	 * time as the global event.
+	 *
+	 * Note, that nextevt_global and nextevt_local might be based on
+	 * different base->clk values. So it's not guaranteed that
+	 * comparing with empty bases results in a correct local_first.
+	 */
+	if (base_local->timers_pending && base_global->timers_pending)
+		local_first = time_before_eq(nextevt_local, nextevt_global);
+	else
+		local_first = base_local->timers_pending;
+
+	nextevt = local_first ? nextevt_local : nextevt_global;
+
+	/*
+	 * Bases are idle if the next event is more than a tick away. Also
 	 * the tick is stopped so any added timer must forward the base clk
 	 * itself to keep granularity small. This idle logic is only
-	 * maintained for the BASE_STD base, deferrable timers may still
-	 * see large granularity skew (by design).
+	 * maintained for the BASE_LOCAL and BASE_GLOBAL base, deferrable
+	 * timers may still see large granularity skew (by design).
 	 */
-	base->is_idle = time_after(nextevt, basej + 1);
+	is_idle = time_after(nextevt, basej + 1);
+
+	/* We need to mark both bases in sync */
+	base_local->is_idle = base_global->is_idle = is_idle;
 
-	if (base->timers_pending) {
+	if (base_local->timers_pending || base_global->timers_pending) {
 		/* If we missed a tick already, force 0 delta */
 		if (time_before(nextevt, basej))
 			nextevt = basej;
 		expires = basem + (u64)(nextevt - basej) * TICK_NSEC;
 	}
-	raw_spin_unlock(&base->lock);
+	raw_spin_unlock(&base_global->lock);
+	raw_spin_unlock(&base_local->lock);
 
 	return cmp_next_hrtimer_event(basem, expires);
 }
@@ -1998,15 +2042,14 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
  */
 void timer_clear_idle(void)
 {
-	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
-
 	/*
 	 * 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.
 	 */
-	base->is_idle = false;
+	__this_cpu_write(timer_bases[BASE_LOCAL].is_idle, false);
+	__this_cpu_write(timer_bases[BASE_GLOBAL].is_idle, false);
 }
 #endif
 
@@ -2052,11 +2095,13 @@ static inline void __run_timers(struct timer_base *base)
  */
 static __latent_entropy void run_timer_softirq(struct softirq_action *h)
 {
-	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
 
 	__run_timers(base);
-	if (IS_ENABLED(CONFIG_NO_HZ_COMMON))
+	if (IS_ENABLED(CONFIG_NO_HZ_COMMON)) {
+		__run_timers(this_cpu_ptr(&timer_bases[BASE_GLOBAL]));
 		__run_timers(this_cpu_ptr(&timer_bases[BASE_DEF]));
+	}
 }
 
 /*
@@ -2064,7 +2109,7 @@ static __latent_entropy void run_timer_softirq(struct softirq_action *h)
  */
 static void run_local_timers(void)
 {
-	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
+	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
 
 	hrtimer_run_queues();
 
-- 
2.30.2

[PATCH v5 10/18] timer: Retrieve next expiry of pinned/non-pinned timers seperately

[Anna-Maria Behnsen]

For the conversion of the NOHZ timer placement to a pull at expiry time
model it's required to have seperate expiry times for the pinned and the
non-pinned (movable) timers. Therefore struct timer_events is introduced.

No functional change

Originally-by: Richard Cochran (linutronix GmbH) <richardcochran@gmail.com>
Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
Reviewed-by: Frederic Weisbecker <frederic@kernel.org>
---
 kernel/time/timer.c | 45 ++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 40 insertions(+), 5 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 7656eab1bf20..ff41d978cb22 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -221,6 +221,11 @@ struct timer_base {
 
 static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
 
+struct timer_events {
+	u64	local;
+	u64	global;
+};
+
 #ifdef CONFIG_NO_HZ_COMMON
 
 static DEFINE_STATIC_KEY_FALSE(timers_nohz_active);
@@ -1968,17 +1973,17 @@ static void forward_base_clk(struct timer_base *base, unsigned long nextevt,
  */
 u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 {
+	struct timer_events tevt = { .local = KTIME_MAX, .global = KTIME_MAX };
 	unsigned long nextevt, nextevt_local, nextevt_global;
 	struct timer_base *base_local, *base_global;
 	bool local_first, is_idle;
-	u64 expires = KTIME_MAX;
 
 	/*
 	 * Pretend that there is no timer pending if the cpu is offline.
 	 * Possible pending timers will be migrated later to an active cpu.
 	 */
 	if (cpu_is_offline(smp_processor_id()))
-		return expires;
+		return tevt.local;
 
 	base_local = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
 	base_global = this_cpu_ptr(&timer_bases[BASE_GLOBAL]);
@@ -2023,16 +2028,46 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 	/* We need to mark both bases in sync */
 	base_local->is_idle = base_global->is_idle = is_idle;
 
-	if (base_local->timers_pending || base_global->timers_pending) {
+	/*
+	 * If the bases are not marked idle, i.e one of the events is at
+	 * max. one tick away, then the CPU can't go into a NOHZ idle
+	 * sleep. Use the earlier event of both and store it in the local
+	 * expiry value. The next global event is irrelevant in this case
+	 * and can be left as KTIME_MAX. CPU will wakeup on time.
+	 */
+	if (!is_idle) {
 		/* If we missed a tick already, force 0 delta */
 		if (time_before(nextevt, basej))
 			nextevt = basej;
-		expires = basem + (u64)(nextevt - basej) * TICK_NSEC;
+		tevt.local = basem + (u64)(nextevt - basej) * TICK_NSEC;
+		goto unlock;
 	}
+
+	/*
+	 * If the bases are marked idle, i.e. the next event on both the
+	 * local and the global queue are farther away than a tick,
+	 * evaluate both bases. No need to check whether one of the bases
+	 * has an already expired timer as this is caught by the !is_idle
+	 * condition above.
+	 */
+	if (base_local->timers_pending)
+		tevt.local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
+
+	/*
+	 * If the local queue expires first, then the global event can be
+	 * ignored. The CPU wakes up before that. If the global queue is
+	 * empty, nothing to do either.
+	 */
+	if (!local_first && base_global->timers_pending)
+		tevt.global = basem + (u64)(nextevt_global - basej) * TICK_NSEC;
+
+unlock:
 	raw_spin_unlock(&base_global->lock);
 	raw_spin_unlock(&base_local->lock);
 
-	return cmp_next_hrtimer_event(basem, expires);
+	tevt.local = min_t(u64, tevt.local, tevt.global);
+
+	return cmp_next_hrtimer_event(basem, tevt.local);
 }
 
 /**
-- 
2.30.2

[PATCH v5 11/18] timer: Split out "get next timer interrupt" functionality

[Anna-Maria Behnsen]

The functionallity for getting the next timer interrupt in
get_next_timer_interrupt() is splitted into a separate function
fetch_next_timer_interrupt() to be usable by other callsides.

This is preparatory work for the conversion of the NOHZ timer
placement to a pull at expiry time model. No functional change.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
v5: Update commit message
---
 kernel/time/timer.c | 91 +++++++++++++++++++++++++--------------------
 1 file changed, 50 insertions(+), 41 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index ff41d978cb22..dfc744545159 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1944,6 +1944,46 @@ static unsigned long next_timer_interrupt(struct timer_base *base)
 	return base->next_expiry;
 }
 
+static unsigned long fetch_next_timer_interrupt(struct timer_base *base_local,
+						struct timer_base *base_global,
+						unsigned long basej, u64 basem,
+						struct timer_events *tevt)
+{
+	unsigned long nextevt_local, nextevt_global;
+	bool local_first;
+
+	nextevt_local = next_timer_interrupt(base_local);
+	nextevt_global = next_timer_interrupt(base_global);
+
+	/*
+	 * Check whether the local event is expiring before or at the same
+	 * time as the global event.
+	 *
+	 * Note, that nextevt_global and nextevt_local might be based on
+	 * different base->clk values. So it's not guaranteed that
+	 * comparing with empty bases results in a correct local_first.
+	 */
+	if (base_local->timers_pending && base_global->timers_pending)
+		local_first = time_before_eq(nextevt_local, nextevt_global);
+	else
+		local_first = base_local->timers_pending;
+
+	/*
+	 * Update tevt->* values:
+	 *
+	 * If the local queue expires first, then the global event can
+	 * be ignored. If the global queue is empty, nothing to do
+	 * either.
+	 */
+	if (!local_first && base_global->timers_pending)
+		tevt->global = basem + (u64)(nextevt_global - basej) * TICK_NSEC;
+
+	if (base_local->timers_pending)
+		tevt->local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
+
+	return local_first ? nextevt_local : nextevt_global;
+}
+
 /*
  * Forward base clock is done only when @basej is past base->clk, otherwise
  * base-clk might be rewind.
@@ -1976,7 +2016,7 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 	struct timer_events tevt = { .local = KTIME_MAX, .global = KTIME_MAX };
 	unsigned long nextevt, nextevt_local, nextevt_global;
 	struct timer_base *base_local, *base_global;
-	bool local_first, is_idle;
+	bool is_idle;
 
 	/*
 	 * Pretend that there is no timer pending if the cpu is offline.
@@ -1991,8 +2031,11 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 	raw_spin_lock(&base_local->lock);
 	raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
 
-	nextevt_local = next_timer_interrupt(base_local);
-	nextevt_global = next_timer_interrupt(base_global);
+	nextevt = fetch_next_timer_interrupt(base_local, base_global,
+					     basej, basem, &tevt);
+
+	nextevt_local = base_local->next_expiry;
+	nextevt_global = base_global->next_expiry;
 
 	/*
 	 * We have a fresh next event. Check whether we can forward the
@@ -2001,21 +2044,6 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 	forward_base_clk(base_local, nextevt_local, basej);
 	forward_base_clk(base_global, nextevt_global, basej);
 
-	/*
-	 * Check whether the local event is expiring before or at the same
-	 * time as the global event.
-	 *
-	 * Note, that nextevt_global and nextevt_local might be based on
-	 * different base->clk values. So it's not guaranteed that
-	 * comparing with empty bases results in a correct local_first.
-	 */
-	if (base_local->timers_pending && base_global->timers_pending)
-		local_first = time_before_eq(nextevt_local, nextevt_global);
-	else
-		local_first = base_local->timers_pending;
-
-	nextevt = local_first ? nextevt_local : nextevt_global;
-
 	/*
 	 * Bases are idle if the next event is more than a tick away. Also
 	 * the tick is stopped so any added timer must forward the base clk
@@ -2028,6 +2056,9 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 	/* We need to mark both bases in sync */
 	base_local->is_idle = base_global->is_idle = is_idle;
 
+	raw_spin_unlock(&base_global->lock);
+	raw_spin_unlock(&base_local->lock);
+
 	/*
 	 * If the bases are not marked idle, i.e one of the events is at
 	 * max. one tick away, then the CPU can't go into a NOHZ idle
@@ -2040,31 +2071,9 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 		if (time_before(nextevt, basej))
 			nextevt = basej;
 		tevt.local = basem + (u64)(nextevt - basej) * TICK_NSEC;
-		goto unlock;
+		tevt.global = KTIME_MAX;
 	}
 
-	/*
-	 * If the bases are marked idle, i.e. the next event on both the
-	 * local and the global queue are farther away than a tick,
-	 * evaluate both bases. No need to check whether one of the bases
-	 * has an already expired timer as this is caught by the !is_idle
-	 * condition above.
-	 */
-	if (base_local->timers_pending)
-		tevt.local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
-
-	/*
-	 * If the local queue expires first, then the global event can be
-	 * ignored. The CPU wakes up before that. If the global queue is
-	 * empty, nothing to do either.
-	 */
-	if (!local_first && base_global->timers_pending)
-		tevt.global = basem + (u64)(nextevt_global - basej) * TICK_NSEC;
-
-unlock:
-	raw_spin_unlock(&base_global->lock);
-	raw_spin_unlock(&base_local->lock);
-
 	tevt.local = min_t(u64, tevt.local, tevt.global);
 
 	return cmp_next_hrtimer_event(basem, tevt.local);
-- 
2.30.2

[PATCH v5 12/18] timer: Add get next timer interrupt functionality for remote CPUs

[Anna-Maria Behnsen]

To prepare for the conversion of the NOHZ timer placement to a pull at
expiry time model it's required to have functionality available getting the
next timer interrupt on a remote CPU.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
 kernel/time/tick-internal.h |  8 +++++++
 kernel/time/timer.c         | 46 +++++++++++++++++++++++++++++++++----
 2 files changed, 49 insertions(+), 5 deletions(-)

diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h
index 649f2b48e8f0..28471c8f8c9c 100644
--- a/kernel/time/tick-internal.h
+++ b/kernel/time/tick-internal.h
@@ -8,6 +8,11 @@
 #include "timekeeping.h"
 #include "tick-sched.h"
 
+struct timer_events {
+	u64	local;
+	u64	global;
+};
+
 #ifdef CONFIG_GENERIC_CLOCKEVENTS
 
 # define TICK_DO_TIMER_NONE	-1
@@ -164,6 +169,9 @@ static inline void timers_update_nohz(void) { }
 DECLARE_PER_CPU(struct hrtimer_cpu_base, hrtimer_bases);
 
 extern u64 get_next_timer_interrupt(unsigned long basej, u64 basem);
+extern void fetch_next_timer_interrupt_remote(unsigned long basej, u64 basem,
+					    struct timer_events *tevt,
+					    unsigned int cpu);
 void timer_clear_idle(void);
 
 #define CLOCK_SET_WALL							\
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index dfc744545159..9daaef5d2f6f 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -221,11 +221,6 @@ struct timer_base {
 
 static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
 
-struct timer_events {
-	u64	local;
-	u64	global;
-};
-
 #ifdef CONFIG_NO_HZ_COMMON
 
 static DEFINE_STATIC_KEY_FALSE(timers_nohz_active);
@@ -1984,6 +1979,47 @@ static unsigned long fetch_next_timer_interrupt(struct timer_base *base_local,
 	return local_first ? nextevt_local : nextevt_global;
 }
 
+/**
+ * fetch_next_timer_interrupt_remote
+ * @basej:	base time jiffies
+ * @basem:	base time clock monotonic
+ * @tevt:	Pointer to the storage for the expiry values
+ * @cpu:	Remote CPU
+ *
+ * Stores the next pending local and global timer expiry values in the
+ * struct pointed to by @tevt. If a queue is empty the corresponding
+ * field is set to KTIME_MAX. If local event expires before global
+ * event, global event is set to KTIME_MAX as well.
+ */
+void fetch_next_timer_interrupt_remote(unsigned long basej, u64 basem,
+				       struct timer_events *tevt,
+				       unsigned int cpu)
+{
+	struct timer_base *base_local, *base_global;
+	unsigned long flags;
+
+	/* Preset local / global events */
+	tevt->local = tevt->global = KTIME_MAX;
+
+	/*
+	 * Pretend that there is no timer pending if the cpu is offline.
+	 * Possible pending timers will be migrated later to an active cpu.
+	 */
+	if (cpu_is_offline(cpu))
+		return;
+
+	base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
+	base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
+
+	raw_spin_lock_irqsave(&base_local->lock, flags);
+	raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
+
+	fetch_next_timer_interrupt(base_local, base_global, basej, basem, tevt);
+
+	raw_spin_unlock(&base_global->lock);
+	raw_spin_unlock_irqrestore(&base_local->lock, flags);
+}
+
 /*
  * Forward base clock is done only when @basej is past base->clk, otherwise
  * base-clk might be rewind.
-- 
2.30.2

[PATCH v5 13/18] timer: Restructure internal locking

[Anna-Maria Behnsen]

From: "Richard Cochran (linutronix GmbH)" <richardcochran@gmail.com>

Move the locking out from __run_timers() to the call sites, so the
protected section can be extended at the call site. Preparatory patch for
changing the NOHZ timer placement to a pull at expiry time model.

No functional change.

Signed-off-by: Richard Cochran (linutronix GmbH) <richardcochran@gmail.com>
Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
 kernel/time/timer.c | 31 +++++++++++++++++++++----------
 1 file changed, 21 insertions(+), 10 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 9daaef5d2f6f..be085e94afcc 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -2142,11 +2142,7 @@ static inline void __run_timers(struct timer_base *base)
 	struct hlist_head heads[LVL_DEPTH];
 	int levels;
 
-	if (time_before(jiffies, base->next_expiry))
-		return;
-
-	timer_base_lock_expiry(base);
-	raw_spin_lock_irq(&base->lock);
+	lockdep_assert_held(&base->lock);
 
 	while (time_after_eq(jiffies, base->clk) &&
 	       time_after_eq(jiffies, base->next_expiry)) {
@@ -2166,21 +2162,36 @@ static inline void __run_timers(struct timer_base *base)
 		while (levels--)
 			expire_timers(base, heads + levels);
 	}
+}
+
+static void __run_timer_base(struct timer_base *base)
+{
+	if (time_before(jiffies, base->next_expiry))
+		return;
+
+	timer_base_lock_expiry(base);
+	raw_spin_lock_irq(&base->lock);
+	__run_timers(base);
 	raw_spin_unlock_irq(&base->lock);
 	timer_base_unlock_expiry(base);
 }
 
+static void run_timer_base(int index)
+{
+	struct timer_base *base = this_cpu_ptr(&timer_bases[index]);
+
+	__run_timer_base(base);
+}
+
 /*
  * This function runs timers and the timer-tq in bottom half context.
  */
 static __latent_entropy void run_timer_softirq(struct softirq_action *h)
 {
-	struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
-
-	__run_timers(base);
+	run_timer_base(BASE_LOCAL);
 	if (IS_ENABLED(CONFIG_NO_HZ_COMMON)) {
-		__run_timers(this_cpu_ptr(&timer_bases[BASE_GLOBAL]));
-		__run_timers(this_cpu_ptr(&timer_bases[BASE_DEF]));
+		run_timer_base(BASE_GLOBAL);
+		run_timer_base(BASE_DEF);
 	}
 }
 
-- 
2.30.2

[PATCH v5 14/18] timer: Check if timers base is handled already

[Anna-Maria Behnsen]

Due to the conversion of the NOHZ timer placement to a pull at expiry
time model, the per CPU timer bases with non pinned timers are no
longer handled only by the local CPU. In case a remote CPU already
expires the non pinned timers base of the local cpu, nothing more
needs to be done by the local CPU. A check at the begin of the expire
timers routine is required, because timer base lock is dropped before
executing the timer callback function.

This is a preparatory work, but has no functional impact right now.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
 kernel/time/timer.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index be085e94afcc..9553da99e262 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -2144,6 +2144,9 @@ static inline void __run_timers(struct timer_base *base)
 
 	lockdep_assert_held(&base->lock);
 
+	if (!!base->running_timer)
+		return;
+
 	while (time_after_eq(jiffies, base->clk) &&
 	       time_after_eq(jiffies, base->next_expiry)) {
 		levels = collect_expired_timers(base, heads);
-- 
2.30.2

[PATCH v5 15/18] tick/sched: Split out jiffies update helper function

[Anna-Maria Behnsen]

From: "Richard Cochran (linutronix GmbH)" <richardcochran@gmail.com>

The logic to get the time of the last jiffies update will be needed by
the timer pull model as well.

Move the code into a global funtion in anticipation of the new caller.

No functional change.

Signed-off-by: Richard Cochran (linutronix GmbH) <richardcochran@gmail.com>
Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
 kernel/time/tick-internal.h |  1 +
 kernel/time/tick-sched.c    | 18 +++++++++++++++---
 2 files changed, 16 insertions(+), 3 deletions(-)

diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h
index 28471c8f8c9c..296cd06bbb24 100644
--- a/kernel/time/tick-internal.h
+++ b/kernel/time/tick-internal.h
@@ -158,6 +158,7 @@ static inline void tick_nohz_init(void) { }
 #ifdef CONFIG_NO_HZ_COMMON
 extern unsigned long tick_nohz_active;
 extern void timers_update_nohz(void);
+extern u64 get_jiffies_update(unsigned long *basej);
 # ifdef CONFIG_SMP
 extern struct static_key_false timers_migration_enabled;
 # endif
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index 7ffdc7ba19b4..1075697f2aa8 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -782,18 +782,30 @@ static inline bool local_timer_softirq_pending(void)
 	return local_softirq_pending() & BIT(TIMER_SOFTIRQ);
 }
 
-static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
+/*
+ * Read jiffies and the time when jiffies were updated last
+ */
+u64 get_jiffies_update(unsigned long *basej)
 {
-	u64 basemono, next_tick, delta, expires;
 	unsigned long basejiff;
 	unsigned int seq;
+	u64 basemono;
 
-	/* Read jiffies and the time when jiffies were updated last */
 	do {
 		seq = read_seqcount_begin(&jiffies_seq);
 		basemono = last_jiffies_update;
 		basejiff = jiffies;
 	} while (read_seqcount_retry(&jiffies_seq, seq));
+	*basej = basejiff;
+	return basemono;
+}
+
+static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
+{
+	u64 basemono, next_tick, delta, expires;
+	unsigned long basejiff;
+
+	basemono = get_jiffies_update(&basejiff);
 	ts->last_jiffies = basejiff;
 	ts->timer_expires_base = basemono;
 
-- 
2.30.2

[PATCH v5 16/18] timer: Implement the hierarchical pull model

[Anna-Maria Behnsen]

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 a idle
timerqueue and eventually expired by some other 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 seperated 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 <anna-maria@linutronix.de>
---
v5:
  - Review remarks of Frederic
  - Return nextevt when CPU is marked offline in timer migration hierarchy
    instead of KTIME_MAX
  - Fix update of group events issue, after remote expiring

v4:
  - Fold typo fix in comment into proper patch "timer: Split out "get next
    timer interrupt" functionality"
  - Update wrong comment for tmigr_state union definition
  - Fix fallout of kernel test robot
---
 include/linux/cpuhotplug.h    |    1 +
 kernel/time/Makefile          |    3 +
 kernel/time/timer.c           |   67 +-
 kernel/time/timer_migration.c | 1255 +++++++++++++++++++++++++++++++++
 kernel/time/timer_migration.h |  123 ++++
 5 files changed, 1441 insertions(+), 8 deletions(-)
 create mode 100644 kernel/time/timer_migration.c
 create mode 100644 kernel/time/timer_migration.h

diff --git a/include/linux/cpuhotplug.h b/include/linux/cpuhotplug.h
index c6fab004104a..6d79a5f5560b 100644
--- a/include/linux/cpuhotplug.h
+++ b/include/linux/cpuhotplug.h
@@ -244,6 +244,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/timer.c b/kernel/time/timer.c
index 9553da99e262..01e97342ad0d 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -53,6 +53,7 @@
 #include <asm/io.h>
 
 #include "tick-internal.h"
+#include "timer_migration.h"
 
 #define CREATE_TRACE_POINTS
 #include <trace/events/timer.h>
@@ -2044,8 +2045,11 @@ static void forward_base_clk(struct timer_base *base, unsigned long nextevt,
  * idle. Idle handling of timer bases is allowed only to be done by CPU
  * itself.
  *
- * 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)
 {
@@ -2089,6 +2093,40 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 	 */
 	is_idle = time_after(nextevt, basej + 1);
 
+	if (is_idle) {
+		u64 next_tmigr;
+
+		/*
+		 * Enqueue first global timer into timer migration
+		 * hierarchy, afterwards tevt.global is no longer used.
+		 */
+		next_tmigr = tmigr_cpu_deactivate(tevt.global);
+
+		/*
+		 * If CPU is the last going idle in timer migration
+		 * hierarchy, make sure 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;
+			is_idle = time_after(nextevt, basej + 1);
+		}
+		/*
+		 * Update of nextevt is not required in an else path, as it
+		 * is revisited in !is_idle path only.
+		 */
+	}
+
 	/* We need to mark both bases in sync */
 	base_local->is_idle = base_global->is_idle = is_idle;
 
@@ -2099,19 +2137,16 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 	 * If the bases are not marked idle, i.e one of the events is at
 	 * max. one tick away, then the CPU can't go into a NOHZ idle
 	 * sleep. Use the earlier event of both and store it in the local
-	 * expiry value. The next global event is irrelevant in this case
-	 * and can be left as KTIME_MAX. CPU will wakeup on time.
+	 * expiry value. tevt.global update is superfluous and is
+	 * ignored. CPU will wakeup on time.
 	 */
 	if (!is_idle) {
 		/* If we missed a tick already, force 0 delta */
 		if (time_before(nextevt, basej))
 			nextevt = basej;
 		tevt.local = basem + (u64)(nextevt - basej) * TICK_NSEC;
-		tevt.global = KTIME_MAX;
 	}
 
-	tevt.local = min_t(u64, tevt.local, tevt.global);
-
 	return cmp_next_hrtimer_event(basem, tevt.local);
 }
 
@@ -2130,6 +2165,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);
+
+	/* Activate without holding the timer_base->lock */
+	tmigr_cpu_activate();
 }
 #endif
 
@@ -2186,6 +2224,15 @@ static void run_timer_base(int index)
 	__run_timer_base(base);
 }
 
+#ifdef CONFIG_SMP
+void timer_expire_remote(unsigned int cpu)
+{
+       struct timer_base *base = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
+
+       __run_timer_base(base);
+}
+#endif
+
 /*
  * This function runs timers and the timer-tq in bottom half context.
  */
@@ -2195,6 +2242,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();
 	}
 }
 
@@ -2209,7 +2259,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..5a600de3623b
--- /dev/null
+++ b/kernel/time/timer_migration.c
@@ -0,0 +1,1255 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * Infrastructure for migrateable timers
+ *
+ * Copyright(C) 2022 linutronix GmbH
+ */
+#include <linux/cpuhotplug.h>
+#include <linux/slab.h>
+#include <linux/smp.h>
+#include <linux/spinlock.h>
+#include <linux/timerqueue.h>
+
+#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 accross 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 bit 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 migrateable timer expires after the
+ * next local timer or the CPU has no migrateable timer pending then the
+ * CPU does not queue an event in the LVL0 group. If the next migrateable
+ * 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.
+ *
+ * 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 hierachary 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 odering is always bottom up. This also
+ * includes the per CPU locks in struct tmigr_cpu. For updating migrator
+ * and active CPU/group information atomic_cmpxchg() is used instead and
+ * only per CPU tmigr_cpu->lock is held.
+ *
+ * During setup of groups tmigr_level_list is required. It is protected by
+ * tmigr_mutex.
+ */
+
+#ifdef DEBUG
+# define DBG_BUG_ON(x) BUG_ON(x)
+#else
+# define DBG_BUG_ON(x)
+#endif
+
+static DEFINE_MUTEX(tmigr_mutex);
+static struct list_head *tmigr_level_list __read_mostly;
+
+static unsigned int tmigr_cores_per_group __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 DEFINE_STATIC_KEY_FALSE(tmigr_enabled);
+
+static inline bool is_tmigr_enabled(void)
+{
+	return static_branch_unlikely(&tmigr_enabled);
+}
+
+/*
+ * Returns true, when @childmask corresponds to group migrator or when group
+ * is not active - so no migrator is set.
+ */
+static bool tmigr_check_migrator(struct tmigr_group *group, u32 childmask)
+{
+	union tmigr_state s;
+
+	s.state = atomic_read(group->migr_state);
+
+	if ((s.migrator != (u8)childmask) && (s.migrator != TMIGR_NONE))
+		return false;
+
+	return true;
+}
+
+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 {
+		DBG_BUG_ON(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
+ * @evt:		Pointer to tmigr_event which needs to be queued (of idle
+ *			child group)
+ * @childmask:		childmask of child group
+ * @nextexp:		Next CPU event expiry information which is handed
+ *			into tmigr code by timer code
+ *			(get_next_timer_interrupt()); it is furthermore
+ *			used for first event which is queued, if timer
+ *			migration hierarchy is completely idle
+ * @childstate:		tmigr_group->migr_state of child - will be only reread
+ *			when cmpxchg in group fails (is required for deactive
+ *			path and new timer path)
+ * @groupstate:		tmigr_group->migr_state of group - will be only reread
+ *			when cmpxchg in group fails (is required for active,
+ *			deactive and new timer path)
+ * @remote: 		Is set, when new timer path is executed in
+ *			tmigr_handle_remote_cpu()
+ */
+struct tmigr_walk {
+	struct tmigr_event	*evt;
+	u32			childmask;
+	u64			nextexp;
+	union tmigr_state	childstate;
+	union tmigr_state	groupstate;
+	bool			remote;
+};
+
+/**
+ * struct tmigr_remote_data -	data required for (check) remote expiry
+ *				hierarchy walk
+ * @basej:	timer base in jiffies
+ * @now:	timer base monotonic
+ * @childmask:	childmask of child group
+ * @check:	is set to 1 if there is the need to handle remote timers;
+ *		required in tmigr_check_handle_remote() only
+ * @wakeup:	returns expiry of first timer in idle timer migration hierarchy
+ *		to make sure timer is handled in time; it is stored in per CPU
+ *		tmigr_cpu struct of CPU which expires remote timers
+ */
+struct tmigr_remote_data {
+	unsigned long	basej;
+	u64		now;
+	u32		childmask;
+	int		check;
+	u64		wakeup;
+};
+
+/*
+ * Returns next event of timerqueue @group->events
+ *
+ * Removes timers with ignore bits and update next_expiry and event cpu
+ * value in group. Expiry value of group event is 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);
+
+	group->next_expiry = KTIME_MAX;
+
+	while ((node = timerqueue_getnext(&group->events))) {
+		evt = container_of(node, struct tmigr_event, nextevt);
+
+		if (!evt->ignore) {
+			group->next_expiry = evt->nextevt.expires;
+			return evt;
+		}
+
+		/*
+		 * Remove next timers with ignore bits, because group lock
+		 * is held anyway
+		 */
+		if (!timerqueue_del(&group->events, node))
+			break;
+	}
+
+	return NULL;
+}
+
+/*
+ * Return next event which is already expired of group timerqueue
+ *
+ * Event is also removed from 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;
+
+	/*
+	 * Event is already expired. Remove it. If it's not the last event,
+	 * then update all group event related information.
+	 */
+	if (timerqueue_del(&group->events, &evt->nextevt))
+		tmigr_next_groupevt(group);
+	else
+		group->next_expiry = KTIME_MAX;
+
+	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;
+	u32 childmask;
+
+	childmask = data->childmask;
+	newstate = curstate = data->groupstate;
+
+retry:
+	walk_done = true;
+
+	if (newstate.migrator == TMIGR_NONE) {
+		newstate.migrator = (u8)childmask;
+
+		/* Changes need to be propagated */
+		walk_done = false;
+	}
+
+	newstate.active |= (u8)childmask;
+
+	newstate.seq++;
+
+	if (atomic_cmpxchg(group->migr_state, curstate.state, newstate.state) != curstate.state) {
+		newstate.state = curstate.state = atomic_read(group->migr_state);
+		goto retry;
+	}
+
+	if (group->parent && (walk_done == false)) {
+		data->groupstate.state = atomic_read(group->parent->migr_state);
+		data->childmask = group->childmask;
+	}
+
+	/*
+	 * Group is active, event will be ignored - bit is updated without
+	 * holding the lock. In case bit is set while another CPU already
+	 * handles remote events, nothing happens, because it is clear that
+	 * CPU became active just in this moment, or in worst case event is
+	 * handled remote. Nothing to worry about.
+	 */
+	group->groupevt.ignore = 1;
+
+	return walk_done;
+}
+
+static void __tmigr_cpu_activate(struct tmigr_cpu *tmc)
+{
+	struct tmigr_walk data;
+	data.childmask = tmc->childmask;
+	data.groupstate.state = atomic_read(tmc->tmgroup->migr_state);
+
+	tmc->cpuevt.ignore = 1;
+
+	walk_groups(&tmigr_active_up, &data, tmc);
+}
+
+void tmigr_cpu_activate(void)
+{
+	struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
+
+	if (!is_tmigr_enabled() || !tmc->tmgroup || !tmc->online || !tmc->idle)
+		return;
+
+	raw_spin_lock(&tmc->lock);
+	tmc->idle = 0;
+	tmc->wakeup = KTIME_MAX;
+	__tmigr_cpu_activate(tmc);
+	raw_spin_unlock(&tmc->lock);
+}
+
+/*
+ * Returns true, if there is nothing to be propagated to the next level
+ *
+ * @data->nextexp is reset to KTIME_MAX; it is reused for first global
+ * event which needs to be handled by migrator (in toplevel group)
+ *
+ * This is the only place where 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;
+	bool walk_done, remote = data->remote;
+	u64 nextexp;
+
+	if (child) {
+		if (data->childstate.active)
+			return true;
+
+		raw_spin_lock(&child->lock);
+		raw_spin_lock_nested(&group->lock, SINGLE_DEPTH_NESTING);
+
+		first_childevt = tmigr_next_groupevt(child);
+		nextexp = child->next_expiry;
+		evt = &child->groupevt;
+	} else {
+		nextexp = data->nextexp;
+
+		/*
+		 * Set @data->nextexp to KTIME_MAX; it is reused for first
+		 * global event which needs to be handled by migrator (in
+		 * toplevel group)
+		 */
+		data->nextexp = KTIME_MAX;
+
+		first_childevt = evt = data->evt;
+		if (evt->ignore)
+			return true;
+
+		raw_spin_lock(&group->lock);
+	}
+
+	if (nextexp == KTIME_MAX)
+		evt->ignore = 1;
+
+	/*
+	 * When next event could be ignored (nextexp is KTIME MAX) and
+	 * there was no remote timer handling before or the group is
+	 * already active 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 a enqueued
+	 * timer in the non active group. The enqueued timer needs to be
+	 * propagated to a higher level to ensure it is handeld.
+	 */
+	if (nextexp == KTIME_MAX && (!remote || data->groupstate.active)) {
+		walk_done = true;
+		goto unlock;
+	}
+
+	walk_done = !group->parent;
+
+	/*
+	 * Update of event cpu and ignore bit is required only when @child
+	 * is set (child is equal or higher than lvl0), but it doesn't
+	 * matter if it is written once more to per cpu event; make the
+	 * update unconditional.
+	 */
+	evt->cpu = first_childevt->cpu;
+	evt->ignore = 0;
+
+	/*
+	 * If child event is already queued in group, remove it from queue
+	 * when expiry time changed only
+	 */
+	if (timerqueue_node_queued(&evt->nextevt)) {
+		if (evt->nextevt.expires == nextexp)
+			goto check_toplvl;
+		else if (!timerqueue_del(&group->events, &evt->nextevt))
+			group->next_expiry = KTIME_MAX;
+	}
+
+	evt->nextevt.expires = nextexp;
+
+	if (timerqueue_add(&group->events, &evt->nextevt))
+		group->next_expiry = nextexp;
+
+check_toplvl:
+	if (walk_done && (data->groupstate.migrator == TMIGR_NONE)) {
+		/*
+		 * Toplevel group is idle and it has to be ensured global
+		 * timers are handled in time. (This could be optimized by
+		 * keeping track of the last global scheduled event and
+		 * only arming it on CPU if the new event is earlier. Not
+		 * sure if its worth the complexity.)
+		 */
+		data->nextexp = 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;
+	bool walk_done;
+
+	walk_done = tmigr_update_events(group, child, data);
+
+	if (!walk_done) {
+		/* Update state information for next iteration */
+		data->childstate.state = atomic_read(group->migr_state);
+		if (group->parent)
+			data->groupstate.state = atomic_read(group->parent->migr_state);
+	}
+
+	return walk_done;
+}
+
+/*
+ * Returns expiry of next timer that needs to be handled. KTIME_MAX is
+ * returned, when an active CPU will handle all timer migration hierarchy
+ * timers.
+ */
+static u64 tmigr_new_timer(struct tmigr_cpu *tmc, u64 nextexp)
+{
+	struct tmigr_walk data = { .evt = &tmc->cpuevt,
+				   .nextexp = nextexp };
+
+	lockdep_assert_held(&tmc->lock);
+
+	if (tmc->remote)
+		return KTIME_MAX;
+
+	tmc->cpuevt.ignore = 0;
+
+	data.groupstate.state = atomic_read(tmc->tmgroup->migr_state);
+	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.nextexp;
+}
+
+static bool tmigr_inactive_up(struct tmigr_group *group,
+			      struct tmigr_group *child,
+			      void *ptr)
+{
+	union tmigr_state curstate, newstate;
+	struct tmigr_walk *data = ptr;
+	bool walk_done;
+	u32 childmask;
+
+	childmask = data->childmask;
+	newstate = curstate = data->groupstate;
+
+retry:
+	walk_done = true;
+
+	/* Reset active bit when child is no longer active */
+	if (!data->childstate.active)
+		newstate.active &= ~(u8)childmask;
+
+	if (newstate.migrator == (u8)childmask) {
+		/*
+		 * Find a new migrator for the group, because child group
+		 * is idle!
+		 */
+		if (!data->childstate.active) {
+			unsigned long new_migr_bit, active = newstate.active;
+
+			new_migr_bit = find_first_bit(&active, BIT_CNT);
+
+			/* Changes need to be propagated */
+			walk_done = false;
+
+			if (new_migr_bit != BIT_CNT)
+				newstate.migrator = BIT(new_migr_bit);
+			else
+				newstate.migrator = TMIGR_NONE;
+		}
+	}
+
+	newstate.seq++;
+
+	DBG_BUG_ON((newstate.migrator != TMIGR_NONE) && !(newstate.active));
+
+	if (atomic_cmpxchg(group->migr_state, curstate.state, newstate.state) != curstate.state) {
+		/*
+		 * Something changed in child/parent group in the meantime,
+		 * reread the state of child and parent; Update of
+		 * data->childstate is required for event handling;
+		 */
+		if (child)
+			data->childstate.state = atomic_read(child->migr_state);
+		newstate.state = curstate.state = atomic_read(group->migr_state);
+
+		goto retry;
+	}
+
+	data->groupstate = newstate;
+	data->remote = false;
+
+	/* Event Handling */
+	tmigr_update_events(group, child, data);
+
+	if (group->parent && (walk_done == false)) {
+		data->childmask = group->childmask;
+		data->childstate = newstate;
+		data->groupstate.state = atomic_read(group->parent->migr_state);
+	}
+
+	/*
+	 * data->nextexp was set by tmigr_update_events() and contains the
+	 * expiry of first global event which needs to be handled
+	 */
+	if (data->nextexp != KTIME_MAX) {
+		DBG_BUG_ON(group->parent);
+		/*
+		 * Toplevel path - If this cpu is about going offline wake
+		 * up some random other cpu so it will take over the
+		 * migrator duty and program its timer properly. Ideally
+		 * wake the cpu with the closest expiry time, but that's
+		 * overkill to figure out.
+		 */
+		if (!(this_cpu_ptr(&tmigr_cpu)->online)) {
+			unsigned int cpu = smp_processor_id();
+
+			cpu = cpumask_any_but(cpu_online_mask, cpu);
+			smp_send_reschedule(cpu);
+		}
+	}
+
+	return walk_done;
+}
+
+static u64 __tmigr_cpu_deactivate(struct tmigr_cpu *tmc, u64 nextexp)
+{
+	struct tmigr_walk data = { .childmask = tmc->childmask,
+				   .evt = &tmc->cpuevt,
+				   .nextexp = nextexp,
+				   .childstate.state = 0 };
+
+	data.groupstate.state = atomic_read(tmc->tmgroup->migr_state);
+
+	/*
+	 * If nextexp is KTIME_MAX, CPU event will be ignored because,
+	 * local timer expires before global timer, no global timer is set
+	 * or CPU goes offline.
+	 */
+	if (nextexp != KTIME_MAX)
+		tmc->cpuevt.ignore = 0;
+
+	walk_groups(&tmigr_inactive_up, &data, tmc);
+	return data.nextexp;
+}
+
+/**
+ * tmigr_cpu_deactivate - Put current CPU into inactive state
+ * @nextexp:	The next timer event expiry set in the current CPU
+ *
+ * Must be called with interrupts disabled.
+ *
+ * Return: next event of the current CPU or next event from the hierarchy
+ * if this CPU is the top level migrator or hierarchy is completely idle.
+ */
+u64 tmigr_cpu_deactivate(u64 nextexp)
+{
+	struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
+	u64 ret;
+
+	if (!is_tmigr_enabled() || !tmc->tmgroup || !tmc->online)
+		return nextexp;
+
+	raw_spin_lock(&tmc->lock);
+
+	/*
+	 * CPU is already deactivated in timer migration
+	 * hierarchy. tick_nohz_get_sleep_length() calls
+	 * tick_nohz_next_event() and thereby timer idle path is
+	 * executed once more. tmc->wakeup holds the first timer, when
+	 * timer migration hierarchy is completely idle and remote
+	 * expiry was done. If there is no new next expiry value
+	 * handed in which should be inserted into the timer migration
+	 * hierarchy, wakeup value is returned.
+	 */
+	if (tmc->idle) {
+		ret = tmc->wakeup;
+
+		tmc->wakeup = KTIME_MAX;
+
+		if (nextexp != KTIME_MAX) {
+			if (nextexp != tmc->cpuevt.nextevt.expires ||
+			    tmc->cpuevt.ignore)
+				ret = tmigr_new_timer(tmc, nextexp);
+		}
+
+		goto unlock;
+	}
+
+	/*
+	 * When tmigr_remote is active, set cpu inactive path and queuing of
+	 * nextexp is done by handle remote path.
+	 */
+	ret = __tmigr_cpu_deactivate(tmc, nextexp);
+
+	tmc->idle = 1;
+
+unlock:
+	raw_spin_unlock(&tmc->lock);
+	return ret;
+}
+
+static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
+				   unsigned long jif)
+{
+	struct timer_events tevt;
+	struct tmigr_walk data;
+	struct tmigr_cpu *tmc;
+	u64 next = KTIME_MAX;
+	unsigned long flags;
+
+	tmc = per_cpu_ptr(&tmigr_cpu, cpu);
+
+	raw_spin_lock_irqsave(&tmc->lock, flags);
+	/*
+	 * Remote CPU is offline or no longer idle or other cpu handles cpu
+	 * timers already or next event was already expired - return!
+	 */
+	if (!tmc->online || tmc->remote || tmc->cpuevt.ignore ||
+	    now < tmc->cpuevt.nextevt.expires) {
+		raw_spin_unlock_irqrestore(&tmc->lock, flags);
+		return next;
+	}
+
+	tmc->remote = 1;
+
+	/* Drop the lock to allow the remote CPU to exit idle */
+	raw_spin_unlock_irqrestore(&tmc->lock, flags);
+
+	if (cpu != smp_processor_id())
+		timer_expire_remote(cpu);
+
+	/* next event of cpu */
+	fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu);
+
+	raw_spin_lock_irqsave(&tmc->lock, flags);
+	/*
+	 * Nothing more to do when CPU came out of idle in the meantime - needs
+	 * to be checked when holding the base lock to prevent race.
+	 */
+	if (!tmc->idle)
+		goto unlock;
+
+	data.evt = &tmc->cpuevt;
+	data.nextexp = tevt.global;
+	data.groupstate.state = atomic_read(tmc->tmgroup->migr_state);
+	data.remote = true;
+	tmc->cpuevt.ignore = 0;
+
+	walk_groups(&tmigr_new_timer_up, &data, tmc);
+
+	next = data.nextexp;
+
+unlock:
+	tmc->remote = 0;
+	raw_spin_unlock_irqrestore(&tmc->lock, flags);
+
+	return next;
+}
+
+static bool tmigr_handle_remote_up(struct tmigr_group *group,
+				   struct tmigr_group *child,
+				   void *ptr)
+{
+	struct tmigr_remote_data *data = ptr;
+	u64 now, next = KTIME_MAX;
+	unsigned long flags, jif;
+	struct tmigr_event *evt;
+	u32 childmask;
+
+	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_irqsave(&group->lock, flags);
+
+	evt = tmigr_next_expired_groupevt(group, now);
+
+	if (evt) {
+		unsigned int remote_cpu = evt->cpu;
+
+		raw_spin_unlock_irqrestore(&group->lock, flags);
+
+		next = tmigr_handle_remote_cpu(remote_cpu, now, jif);
+
+		/* check if there is another event, that needs to be handled */
+		goto again;
+	} else {
+		raw_spin_unlock_irqrestore(&group->lock, flags);
+	}
+
+	/* Update of childmask for next level */
+	data->childmask = group->childmask;
+	data->wakeup = next;
+
+	return false;
+}
+
+/**
+ * tmigr_handle_remote - Handle migratable timers on 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;
+	unsigned long flags;
+
+	if (!is_tmigr_enabled() || !tmc->tmgroup || !tmc->online)
+		return;
+
+	/*
+	 * NOTE: This is a doubled check because migrator test will be done
+	 * in tmigr_handle_remote_up() anyway. Keep this check to fasten
+	 * the return when nothing has to be done.
+	 */
+	if (!tmigr_check_migrator(tmc->tmgroup, tmc->childmask))
+		return;
+
+	data.now = get_jiffies_update(&data.basej);
+	data.childmask = tmc->childmask;
+	data.wakeup = KTIME_MAX;
+
+	__walk_groups(&tmigr_handle_remote_up, &data, tmc);
+
+	raw_spin_lock_irqsave(&tmc->lock, flags);
+	if (tmc->idle)
+		tmc->wakeup = data.wakeup;
+
+	raw_spin_unlock_irqrestore(&tmc->lock, flags);
+
+	return;
+}
+
+static bool tmigr_requires_handle_remote_up(struct tmigr_group *group,
+					 struct tmigr_group *child,
+					 void *ptr)
+{
+	struct tmigr_remote_data *data = ptr;
+	u32 childmask;
+
+	childmask = data->childmask;
+
+	/*
+	 * Handle the group only if 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;
+
+	/*
+	 * Racy lockless check for next_expiry
+	 */
+	if (data->now >= group->next_expiry) {
+		data->check = 1;
+		return true;
+	}
+
+	/* Update of childmask for next level */
+	data->childmask = group->childmask;
+	return false;
+}
+
+int tmigr_requires_handle_remote(void)
+{
+	struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
+	struct tmigr_remote_data data;
+
+	if (!is_tmigr_enabled() || !tmc->tmgroup || !tmc->online)
+		return 0;
+
+	if (!tmigr_check_migrator(tmc->tmgroup, tmc->childmask))
+		return 0;
+
+	data.now = get_jiffies_update(&data.basej);
+	data.childmask = tmc->childmask;
+
+	__walk_groups(&tmigr_requires_handle_remote_up, &data, tmc);
+
+	return data.check;
+}
+
+static void tmigr_init_group(struct tmigr_group *group, unsigned int lvl,
+			     unsigned int node, atomic_t *migr_state)
+{
+	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_childs = 0;
+
+	/*
+	 * num_cores is required for level=0 groups only during setup and
+	 * when siblings exists but it doesn't matter if this value is set
+	 * in other groups as well
+	 */
+	group->num_cores = 1;
+
+	s.migrator = TMIGR_NONE;
+	s.active = 0;
+	s.seq = 0;
+	atomic_set(migr_state, s.state);
+
+	group->migr_state = migr_state;
+
+	timerqueue_init_head(&group->events);
+	timerqueue_init(&group->groupevt.nextevt);
+	group->groupevt.nextevt.expires = KTIME_MAX;
+	group->next_expiry = KTIME_MAX;
+	group->groupevt.ignore = 1;
+}
+
+static bool sibling_in_group(int newcpu, struct tmigr_group *group)
+{
+	int i, cpu;
+
+	/* Find a sibling of newcpu in group members */
+	for (i = 0; i < group->num_childs; i++) {
+		cpu = group->cpus[i];
+
+		if (cpumask_test_cpu(newcpu, topology_sibling_cpumask(cpu)))
+			return true;
+	}
+	return false;
+}
+
+static struct tmigr_group *tmigr_get_group(unsigned int cpu, unsigned int node,
+					   unsigned int lvl)
+{
+	struct tmigr_group *tmp, *group = NULL;
+	bool first_loop = true;
+	atomic_t *migr_state;
+
+reloop:
+	/* Try to attach to an exisiting 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_childs >= TMIGR_CHILDS_PER_GROUP)
+			continue;
+
+		/*
+		 * If this is the lowest level of the hierarchy, make sure
+		 * that thread siblings share a group. It is only executed
+		 * when siblings exist. ALL groups of lowest level needs to
+		 * be checked for thread sibling, before thread cpu is
+		 * added to a random group with capacity. When all groups
+		 * are checked and no thread sibling was found, reloop of
+		 * level zero groups is required to get a group with
+		 * capacity.
+		 */
+		if (!lvl && (tmigr_cores_per_group != TMIGR_CHILDS_PER_GROUP)) {
+			if (first_loop == true && !sibling_in_group(cpu, tmp)) {
+				continue;
+			} else if (first_loop == false) {
+				if (tmp->num_cores >= tmigr_cores_per_group)
+					continue;
+				else
+					tmp->num_cores++;
+			}
+		}
+
+		group = tmp;
+		break;
+	}
+
+	if (group) {
+		return group;
+	} else if (first_loop == true) {
+		first_loop = false;
+		goto reloop;
+	}
+
+	/* Allocate and	set up a new group with corresponding migr_state */
+	group = kzalloc_node(sizeof(*group), GFP_KERNEL, node);
+	if (!group)
+		return ERR_PTR(-ENOMEM);
+
+	migr_state = kzalloc_node(sizeof(atomic_t), GFP_KERNEL, node);
+	if (!migr_state) {
+		kfree(group);
+		return ERR_PTR(-ENOMEM);
+	}
+
+	tmigr_init_group(group, lvl, node, migr_state);
+	/* 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;
+	unsigned long flags;
+
+	raw_spin_lock_irqsave(&child->lock, flags);
+	raw_spin_lock_nested(&parent->lock, SINGLE_DEPTH_NESTING);
+
+	child->parent = parent;
+	child->childmask = BIT(parent->num_childs++);
+
+	raw_spin_unlock(&parent->lock);
+	raw_spin_unlock_irqrestore(&child->lock, flags);
+
+	/*
+	 * To prevent inconsistent states, active childs needs to be active
+	 * in new parent as well. Inactive childs are already marked
+	 * inactive in parent group.
+	 */
+	childstate.state = atomic_read(child->migr_state);
+	if (childstate.migrator != TMIGR_NONE) {
+		struct tmigr_walk data;
+
+		data.childmask = child->childmask;
+		data.groupstate.state = atomic_read(parent->migr_state);
+
+		/*
+		 * There is only one new level per time. When connecting
+		 * child and parent and set child active when parent is
+		 * inactive, parent needs to be the upperst
+		 * 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;
+	size_t sz;
+
+	sz = sizeof(struct tmigr_group *) * tmigr_hierarchy_levels;
+	stack = kzalloc(sz, GFP_KERNEL);
+	if (!stack)
+		return -ENOMEM;
+
+	do {
+		group = tmigr_get_group(cpu, node, i);
+		if (IS_ERR(group)) {
+			err = IS_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;
+		}
+
+		DBG_BUG_ON(i != group->level);
+
+		/*
+		 * Update tmc -> group / child -> group connection
+		 */
+		if (i == 0) {
+			struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
+			unsigned long flags;
+
+			raw_spin_lock_irqsave(&group->lock, flags);
+
+			tmc->tmgroup = group;
+			tmc->childmask = BIT(group->num_childs);
+
+			group->cpus[group->num_childs++] = cpu;
+
+			raw_spin_unlock_irqrestore(&group->lock, flags);
+
+			/* There are no childs that needs to be connected */
+			continue;
+		} else {
+			child = stack[i - 1];
+			tmigr_connect_child_parent(child, group);
+		}
+
+		/* check if upperst level was newly created */
+		if (top != i)
+			continue;
+
+		DBG_BUG_ON(top == 0);
+
+		lvllist = &tmigr_level_list[top];
+		if (group->num_childs == 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)
+{
+	unsigned 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);
+	unsigned long flags;
+	unsigned 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 = 1;
+		tmc->cpuevt.cpu = cpu;
+
+		tmc->remote = 0;
+		tmc->idle = 0;
+		tmc->wakeup = KTIME_MAX;
+	}
+	raw_spin_lock_irqsave(&tmc->lock, flags);
+	__tmigr_cpu_activate(tmc);
+	tmc->online = 1;
+	raw_spin_unlock_irqrestore(&tmc->lock, flags);
+	return 0;
+}
+
+static int tmigr_cpu_offline(unsigned int cpu)
+{
+	struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
+
+	raw_spin_lock_irq(&tmc->lock);
+	tmc->online = 0;
+	__tmigr_cpu_deactivate(tmc, KTIME_MAX);
+	raw_spin_unlock_irq(&tmc->lock);
+
+	return 0;
+}
+
+static int __init tmigr_init(void)
+{
+	unsigned int cpulvl, nodelvl, cpus_per_node, i, ns;
+	unsigned int nnodes = num_possible_nodes();
+	unsigned int ncpus = num_possible_cpus();
+	int ret = -ENOMEM;
+	size_t sz;
+
+	/* Nothing to do if running on UP */
+	if (ncpus == 1)
+		return 0;
+
+	/*
+	 * Unfortunately there is no reliable way to determine the number of SMT
+	 * siblings in a generic way. tmigr_init() is called after SMP bringup,
+	 * so for the normal boot case it can be assumed that all siblings have
+	 * been brought up and the number of siblings of the current cpu can be
+	 * used. If someone booted with 'maxcpus=N/2' on the kernel command line
+	 * and (at least x86) bring up the siblings later then the siblings will
+	 * end up in different groups. Bad luck.
+	 */
+	ns = cpumask_weight(topology_sibling_cpumask(raw_smp_processor_id()));
+	tmigr_cores_per_group = TMIGR_CHILDS_PER_GROUP;
+	if (ns >= 2 && ns < TMIGR_CHILDS_PER_GROUP)
+		tmigr_cores_per_group /= ns;
+
+	/*
+	 * 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 accross
+	 * nodes. We cannot rely on cpumask_of_node() because there only already
+	 * online CPUs are considered.
+	 */
+	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_CHILDS_PER_GROUP));
+
+	/* Calculate the extra levels to connect all nodes */
+	nodelvl = DIV_ROUND_UP(order_base_2(nnodes),
+			       ilog2(TMIGR_CHILDS_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 accross numa nodes. Store
+	 * this information for the setup code to decide when node matching is
+	 * not longer required.
+	 */
+	tmigr_crossnode_level = cpulvl;
+
+	sz = sizeof(struct list_head) * tmigr_hierarchy_levels;
+	tmigr_level_list = kzalloc(sz, 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 childs per group;"
+		" %d cores_per_group; %d crossnode level\n",
+		tmigr_hierarchy_levels, TMIGR_CHILDS_PER_GROUP,
+		tmigr_cores_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;
+
+	static_branch_enable(&tmigr_enabled);
+
+	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..ceb336e705df
--- /dev/null
+++ b/kernel/time/timer_migration.h
@@ -0,0 +1,123 @@
+#ifndef _KERNEL_TIME_MIGRATION_H
+#define _KERNEL_TIME_MIGRATION_H
+
+/* Per group capacity. Must be a power of 2! */
+#define TMIGR_CHILDS_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;
+	int			ignore;
+};
+
+/**
+ * struct tmigr_group - timer migration hierarchy group
+ * @lock:		Lock protecting the event information
+ * @cpus:		Array with CPUs which are member of group; required for
+ *			sibling CPUs; used only when level == 0
+ * @parent:		Pointer to parent group
+ * @list:		List head that is added to per level tmigr_level_list
+ * @level:		Hierarchy level of group
+ * @numa_node:		Is set to numa node when level < tmigr_crossnode_level;
+ *			otherwise it is set to NUMA_NO_NODE; Required for setup
+ *			only
+ * @num_childs:		Counter of group childs; Required for setup only
+ * @num_cores:		Counter of cores per group; Required for setup only when
+ *			level == 0 and siblings exist
+ * @migr_state:		State of group (see struct tmigr_state)
+ * @childmask:		childmask of group in parent group; is set during setup
+ *			never changed; could be read lockless
+ * @events:		Timer queue for child events queued in the group
+ * @groupevt:		Next event of group; it is only reliable when group is
+ *			!active (ignore bit is set when group is active)
+ * @next_expiry:	Base monotonic expiry time of next event of group;
+ *			Used for racy lockless check whether remote expiry is
+ *			required; it is always reliable
+ */
+struct tmigr_group {
+	raw_spinlock_t		lock;
+	unsigned int		cpus[TMIGR_CHILDS_PER_GROUP];
+	struct tmigr_group	*parent;
+	struct list_head	list;
+	unsigned int		level;
+	unsigned int		numa_node;
+	unsigned int		num_childs;
+	unsigned int		num_cores;
+	atomic_t		*migr_state;
+	u32			childmask;
+	struct timerqueue_head	events;
+	struct tmigr_event	groupevt;
+	u64			next_expiry;
+};
+
+/**
+ * struct tmigr_cpu - timer migration per CPU group
+ * @lock:	Lock protecting tmigr_cpu group information
+ * @online:	Indicates wheter CPU is online
+ * @idle:	Indicates wheter CPU is idle in timer migration hierarchy
+ * @remote:	Is set when timers of CPU are expired remote
+ * @tmgroup:	Pointer to parent group
+ * @childmask:	childmask of tmigr_cpu in parent group
+ * @cpuevt:	CPU event which could be queued into 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 when tmigr_cpu_deactive() is called and group is
+ *		idle; afterwards a reset to KTIME_MAX is required;
+ */
+struct tmigr_cpu {
+	raw_spinlock_t		lock;
+	int			online;
+	int			idle;
+	int			remote;
+	struct tmigr_group	*tmgroup;
+	u32			childmask;
+	struct tmigr_event	cpuevt;
+	u64			wakeup;
+};
+
+/**
+ * union tmigr_state - state of tmigr_group
+ * @state:	Combined version of the state - only used for atomic
+ * 		read/cmpxchg function
+ * @struct:	Splitted version of the state - only use the struct members to
+ *		update information to stay independant of endianess
+ */
+union tmigr_state {
+	u32 state;
+	/**
+	 * struct - splitted state of tmigr_group
+	 * @active:	Contains each childmask bit of active childs
+	 * @migrator:	Contains childmask of child which is migrator
+	 * @seq:	Seqence number to prevent race when update in child
+	 *		group are propagated in wrong order (especially when
+	 *		migrator changes are involved)
+	 */
+	struct {
+		u8	active;
+		u8	migrator;
+		u16	seq;
+	} __packed;
+};
+
+#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON)
+extern void tmigr_handle_remote(void);
+extern int tmigr_requires_handle_remote(void);
+extern void tmigr_cpu_activate(void);
+extern u64 tmigr_cpu_deactivate(u64 nextevt);
+extern void timer_expire_remote(unsigned int cpu);
+#else
+static inline void tmigr_handle_remote(void) { }
+extern inline int tmigr_requires_handle_remote(void) { return 0; }
+static inline void tmigr_cpu_activate(void) { }
+static inline u64 tmigr_cpu_deactivate(u64 nextevt) { return KTIME_MAX; }
+extern inline void timer_expire_remote(unsigned int cpu) { }
+#endif
+
+#endif
-- 
2.30.2

[PATCH v5 17/18] timer_migration: Add tracepoints

[Anna-Maria Behnsen]

The timer pull logic needs proper debugging aids. Add tracepoints so the
hierarchical idle machinery can be diagnosed.

Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
 include/trace/events/timer_migration.h | 277 +++++++++++++++++++++++++
 kernel/time/timer_migration.c          |  24 +++
 2 files changed, 301 insertions(+)
 create mode 100644 include/trace/events/timer_migration.h

diff --git a/include/trace/events/timer_migration.h b/include/trace/events/timer_migration.h
new file mode 100644
index 000000000000..0c4824056930
--- /dev/null
+++ b/include/trace/events/timer_migration.h
@@ -0,0 +1,277 @@
+#undef TRACE_SYSTEM
+#define TRACE_SYSTEM timer_migration
+
+#if !defined(_TRACE_TIMER_MIGRATION_H) || defined(TRACE_HEADER_MULTI_READ)
+#define _TRACE_TIMER_MIGRATION_H
+
+#include <linux/tracepoint.h>
+
+/* Group events */
+TRACE_EVENT(tmigr_group_set,
+
+	TP_PROTO(struct tmigr_group *group),
+
+	TP_ARGS(group),
+
+	TP_STRUCT__entry(
+		__field( void *,	group		)
+		__field( unsigned int,	lvl		)
+		__field( unsigned int,	numa_node	)
+	),
+
+	TP_fast_assign(
+		__entry->group		= group;
+		__entry->lvl		= group->level;
+		__entry->numa_node	= group->numa_node;
+	),
+
+	TP_printk("group=%p lvl=%d numa=%d",
+		  __entry->group, __entry->lvl, __entry->numa_node)
+);
+
+TRACE_EVENT(tmigr_connect_child_parent,
+
+	TP_PROTO(struct tmigr_group *child),
+
+	TP_ARGS(child),
+
+	TP_STRUCT__entry(
+		__field( void *,	child		)
+		__field( void *,	parent		)
+		__field( unsigned int,	lvl		)
+		__field( unsigned int,	numa_node	)
+		__field( unsigned int,	num_childs	)
+		__field( u32,		childmask	)
+	),
+
+	TP_fast_assign(
+		__entry->child		= child;
+		__entry->parent		= child->parent;
+		__entry->lvl		= child->parent->level;
+		__entry->numa_node	= child->parent->numa_node;
+		__entry->numa_node	= child->parent->num_childs;
+		__entry->childmask	= child->childmask;
+	),
+
+	TP_printk("group=%p childmask=%0x parent=%p lvl=%d numa=%d num_childs=%d",
+		  __entry->child,  __entry->childmask, __entry->parent,
+		  __entry->lvl, __entry->numa_node, __entry->num_childs)
+);
+
+TRACE_EVENT(tmigr_connect_cpu_parent,
+
+	TP_PROTO(struct tmigr_cpu *tmc),
+
+	TP_ARGS(tmc),
+
+	TP_STRUCT__entry(
+		__field( void *,	parent		)
+		__field( unsigned int,	cpu		)
+		__field( unsigned int,	lvl		)
+		__field( unsigned int,	numa_node	)
+		__field( unsigned int,	num_childs	)
+		__field( u32,		childmask	)
+	),
+
+	TP_fast_assign(
+		__entry->parent		= tmc->tmgroup;
+		__entry->cpu		= tmc->cpuevt.cpu;
+		__entry->lvl		= tmc->tmgroup->level;
+		__entry->numa_node	= tmc->tmgroup->numa_node;
+		__entry->numa_node	= tmc->tmgroup->num_childs;
+		__entry->childmask	= tmc->childmask;
+	),
+
+	TP_printk("cpu=%d childmask=%0x parent=%p lvl=%d numa=%d num_childs=%d",
+		  __entry->cpu,	 __entry->childmask, __entry->parent,
+		  __entry->lvl, __entry->numa_node, __entry->num_childs)
+);
+
+DECLARE_EVENT_CLASS(tmigr_group_and_cpu,
+
+	TP_PROTO(struct tmigr_group *group, union tmigr_state state, u32 childmask),
+
+	TP_ARGS(group, state, childmask),
+
+	TP_STRUCT__entry(
+		__field( void *,	group		)
+		__field( void *,	parent		)
+		__field( unsigned int,	lvl		)
+		__field( unsigned int,	numa_node	)
+		__field( u8,		active		)
+		__field( u8,		migrator	)
+		__field( u32,		childmask	)
+	),
+
+	TP_fast_assign(
+		__entry->group		= group;
+		__entry->parent		= group->parent;
+		__entry->lvl		= group->level;
+		__entry->numa_node	= group->numa_node;
+		__entry->active		= state.active;
+		__entry->migrator	= state.migrator;
+		__entry->childmask	= childmask;
+	),
+
+	TP_printk("group=%p lvl=%d numa=%d active=%0x migrator=%0x "
+		  "parent=%p childmask=%0x",
+		  __entry->group, __entry->lvl, __entry->numa_node,
+		  __entry->active, __entry->migrator,
+		  __entry->parent, __entry->childmask)
+);
+
+DEFINE_EVENT(tmigr_group_and_cpu, tmigr_group_set_cpu_inactive,
+
+	TP_PROTO(struct tmigr_group *group, union tmigr_state state, u32 childmask),
+
+	TP_ARGS(group, state, childmask)
+);
+
+DEFINE_EVENT(tmigr_group_and_cpu, tmigr_group_set_cpu_active,
+
+	TP_PROTO(struct tmigr_group *group, union tmigr_state state, u32 childmask),
+
+	TP_ARGS(group, state, childmask)
+);
+
+/* CPU events*/
+DECLARE_EVENT_CLASS(tmigr_cpugroup,
+
+	TP_PROTO(struct tmigr_cpu *tmc),
+
+	TP_ARGS(tmc),
+
+	TP_STRUCT__entry(
+		__field( void *,	parent)
+		__field( unsigned int,	cpu)
+	),
+
+	TP_fast_assign(
+		__entry->cpu		= tmc->cpuevt.cpu;
+		__entry->parent		= tmc->tmgroup;
+	),
+
+	TP_printk("cpu=%d parent=%p", __entry->cpu, __entry->parent)
+);
+
+DEFINE_EVENT(tmigr_cpugroup, tmigr_cpu_new_timer,
+
+	TP_PROTO(struct tmigr_cpu *tmc),
+
+	TP_ARGS(tmc)
+);
+
+DEFINE_EVENT(tmigr_cpugroup, tmigr_cpu_active,
+
+	TP_PROTO(struct tmigr_cpu *tmc),
+
+	TP_ARGS(tmc)
+);
+
+DEFINE_EVENT(tmigr_cpugroup, tmigr_cpu_online,
+
+	TP_PROTO(struct tmigr_cpu *tmc),
+
+	TP_ARGS(tmc)
+);
+
+DEFINE_EVENT(tmigr_cpugroup, tmigr_cpu_offline,
+
+	TP_PROTO(struct tmigr_cpu *tmc),
+
+	TP_ARGS(tmc)
+);
+
+DEFINE_EVENT(tmigr_cpugroup, tmigr_handle_remote_cpu,
+
+	TP_PROTO(struct tmigr_cpu *tmc),
+
+	TP_ARGS(tmc)
+);
+
+TRACE_EVENT(tmigr_cpu_idle,
+
+	TP_PROTO(struct tmigr_cpu *tmc, u64 nextevt),
+
+	TP_ARGS(tmc, nextevt),
+
+	TP_STRUCT__entry(
+		__field( void *,	parent)
+		__field( unsigned int,	cpu)
+		__field( u64,		nextevt)
+	),
+
+	TP_fast_assign(
+		__entry->cpu		= tmc->cpuevt.cpu;
+		__entry->parent		= tmc->tmgroup;
+		__entry->nextevt	= nextevt;
+	),
+
+	TP_printk("cpu=%d parent=%p nextevt=%llu",
+		  __entry->cpu, __entry->parent, __entry->nextevt)
+);
+
+TRACE_EVENT(tmigr_update_events,
+
+	TP_PROTO(struct tmigr_group *child, struct tmigr_group *group,
+		 union tmigr_state childstate,	union tmigr_state groupstate,
+		 u64 nextevt),
+
+	TP_ARGS(child, group, childstate, groupstate, nextevt),
+
+	TP_STRUCT__entry(
+		__field( void *,	child			)
+		__field( void *,	group			)
+		__field( u64,		nextevt			)
+		__field( u64,		group_next_expiry	)
+		__field( unsigned int,	group_lvl		)
+		__field( u8,		child_active		)
+		__field( u8,		group_active		)
+		__field( unsigned int,	child_evtcpu		)
+		__field( u64,		child_evt_expiry	)
+	),
+
+	TP_fast_assign(
+		__entry->child			= child;
+		__entry->group			= group;
+		__entry->nextevt		= nextevt;
+		__entry->group_next_expiry	= group->next_expiry;
+		__entry->group_lvl		= group->level;
+		__entry->child_active		= childstate.active;
+		__entry->group_active		= groupstate.active;
+		__entry->child_evtcpu		= child ? child->groupevt.cpu : 0;
+		__entry->child_evt_expiry	= child ? child->groupevt.nextevt.expires : 0;
+	),
+
+	TP_printk("child=%p group=%p group_lvl=%d child_active=%0x group_active=%0x "
+		  "nextevt=%llu next_expiry=%llu child_evt_expiry=%llu child_evtcpu=%d",
+		  __entry->child, __entry->group, __entry->group_lvl, __entry->child_active,
+		  __entry->group_active,
+		  __entry->nextevt, __entry->group_next_expiry, __entry->child_evt_expiry,
+		  __entry->child_evtcpu)
+);
+
+TRACE_EVENT(tmigr_handle_remote,
+
+	TP_PROTO(struct tmigr_group *group),
+
+	TP_ARGS(group),
+
+	TP_STRUCT__entry(
+		__field( void * ,	group	)
+		__field( unsigned int ,	lvl	)
+	),
+
+	TP_fast_assign(
+		__entry->group		= group;
+		__entry->lvl		= group->level;
+	),
+
+	TP_printk("group=%p lvl=%d",
+		   __entry->group, __entry->lvl)
+);
+
+#endif /*  _TRACE_TIMER_MIGRATION_H */
+
+/* This part must be outside protection */
+#include <trace/define_trace.h>
diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
index 5a600de3623b..5a371bc252d4 100644
--- a/kernel/time/timer_migration.c
+++ b/kernel/time/timer_migration.c
@@ -13,6 +13,9 @@
 #include "timer_migration.h"
 #include "tick-internal.h"
 
+#define CREATE_TRACE_POINTS
+#include <trace/events/timer_migration.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
@@ -320,6 +323,8 @@ static bool tmigr_active_up(struct tmigr_group *group,
 	 */
 	group->groupevt.ignore = 1;
 
+	trace_tmigr_group_set_cpu_active(group, newstate, childmask);
+
 	return walk_done;
 }
 
@@ -344,6 +349,7 @@ void tmigr_cpu_activate(void)
 	raw_spin_lock(&tmc->lock);
 	tmc->idle = 0;
 	tmc->wakeup = KTIME_MAX;
+	trace_tmigr_cpu_active(tmc);
 	__tmigr_cpu_activate(tmc);
 	raw_spin_unlock(&tmc->lock);
 }
@@ -450,6 +456,9 @@ static bool tmigr_update_events(struct tmigr_group *group,
 		data->nextexp = tmigr_next_groupevt_expires(group);
 	}
 
+	trace_tmigr_update_events(child, group, data->childstate,
+				  data->groupstate, nextexp);
+
 unlock:
 	raw_spin_unlock(&group->lock);
 
@@ -493,6 +502,8 @@ static u64 tmigr_new_timer(struct tmigr_cpu *tmc, u64 nextexp)
 	if (tmc->remote)
 		return KTIME_MAX;
 
+	trace_tmigr_cpu_new_timer(tmc);
+
 	tmc->cpuevt.ignore = 0;
 
 	data.groupstate.state = atomic_read(tmc->tmgroup->migr_state);
@@ -593,6 +604,8 @@ static bool tmigr_inactive_up(struct tmigr_group *group,
 		}
 	}
 
+	trace_tmigr_group_set_cpu_inactive(group, newstate, childmask);
+
 	return walk_done;
 }
 
@@ -669,6 +682,7 @@ u64 tmigr_cpu_deactivate(u64 nextexp)
 	tmc->idle = 1;
 
 unlock:
+	trace_tmigr_cpu_idle(tmc, ret);
 	raw_spin_unlock(&tmc->lock);
 	return ret;
 }
@@ -695,6 +709,8 @@ static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
 		return next;
 	}
 
+	trace_tmigr_handle_remote_cpu(tmc);
+
 	tmc->remote = 1;
 
 	/* Drop the lock to allow the remote CPU to exit idle */
@@ -746,6 +762,7 @@ static bool tmigr_handle_remote_up(struct tmigr_group *group,
 
 	childmask = data->childmask;
 
+	trace_tmigr_handle_remote(group);
 again:
 	/*
 	 * Handle the group only if @childmask is the migrator or if the
@@ -979,6 +996,7 @@ static struct tmigr_group *tmigr_get_group(unsigned int cpu, unsigned int node,
 	tmigr_init_group(group, lvl, node, migr_state);
 	/* Setup successful. Add it to the hierarchy */
 	list_add(&group->list, &tmigr_level_list[lvl]);
+	trace_tmigr_group_set(group);
 	return group;
 }
 
@@ -997,6 +1015,8 @@ static void tmigr_connect_child_parent(struct tmigr_group *child,
 	raw_spin_unlock(&parent->lock);
 	raw_spin_unlock_irqrestore(&child->lock, flags);
 
+	trace_tmigr_connect_child_parent(child);
+
 	/*
 	 * To prevent inconsistent states, active childs needs to be active
 	 * in new parent as well. Inactive childs are already marked
@@ -1083,6 +1103,8 @@ static int tmigr_setup_groups(unsigned int cpu, unsigned int node)
 
 			raw_spin_unlock_irqrestore(&group->lock, flags);
 
+			trace_tmigr_connect_cpu_parent(tmc);
+
 			/* There are no childs that needs to be connected */
 			continue;
 		} else {
@@ -1151,6 +1173,7 @@ static int tmigr_cpu_online(unsigned int cpu)
 		tmc->wakeup = KTIME_MAX;
 	}
 	raw_spin_lock_irqsave(&tmc->lock, flags);
+	trace_tmigr_cpu_online(tmc);
 	__tmigr_cpu_activate(tmc);
 	tmc->online = 1;
 	raw_spin_unlock_irqrestore(&tmc->lock, flags);
@@ -1164,6 +1187,7 @@ static int tmigr_cpu_offline(unsigned int cpu)
 	raw_spin_lock_irq(&tmc->lock);
 	tmc->online = 0;
 	__tmigr_cpu_deactivate(tmc, KTIME_MAX);
+	trace_tmigr_cpu_offline(tmc);
 	raw_spin_unlock_irq(&tmc->lock);
 
 	return 0;
-- 
2.30.2

[PATCH v5 18/18] timer: Always queue timers on the local CPU

[Anna-Maria Behnsen]

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 seperate storage
and eventually pulled at expiry time to a remote CPU.

Originally-by: Richard Cochran (linutronix GmbH) <richardcochran@gmail.com>
Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
---
v5:
 - Move WARN_ONCE() in add_timer_on() into a previous patch
 - Fold "crystallball magic" related hunks into this patch
---
 include/linux/timer.h |  5 ++---
 kernel/time/timer.c   | 42 ++++++++++++++++++++----------------------
 2 files changed, 22 insertions(+), 25 deletions(-)

diff --git a/include/linux/timer.h b/include/linux/timer.h
index 9162f275819a..aaedacac0b56 100644
--- a/include/linux/timer.h
+++ b/include/linux/timer.h
@@ -50,9 +50,8 @@ struct timer_list {
  * 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.
+ * @TIMER_PINNED: A pinned timer 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
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 01e97342ad0d..a441ec9dae39 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -593,10 +593,13 @@ 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 && timer->flags & TIMER_PINNED)
 		wake_up_nohz_cpu(base->cpu);
 }
 
@@ -944,17 +947,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 jnow = READ_ONCE(jiffies);
@@ -1106,7 +1098,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) {
 		/*
@@ -2127,8 +2119,14 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 		 */
 	}
 
-	/* We need to mark both bases in sync */
-	base_local->is_idle = base_global->is_idle = is_idle;
+	/*
+	 * base->is_idle information is required to wakeup a idle CPU when
+	 * a new timer was enqueued. Only pinned timers could be enqueued
+	 * remotely into a idle base. Therefore do maintain only
+	 * base_local->is_idle information and ignore base_global->is_idle
+	 * information.
+	 */
+	base_local->is_idle = is_idle;
 
 	raw_spin_unlock(&base_global->lock);
 	raw_spin_unlock(&base_local->lock);
@@ -2158,13 +2156,13 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
 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);
 
 	/* Activate without holding the timer_base->lock */
 	tmigr_cpu_activate();
-- 
2.30.2

Re: [PATCH v5 11/18] timer: Split out "get next timer interrupt" functionality

[Frederic Weisbecker]

Le Wed, Mar 01, 2023 at 03:17:37PM +0100, Anna-Maria Behnsen a écrit :
> The functionallity for getting the next timer interrupt in
> get_next_timer_interrupt() is splitted into a separate function
> fetch_next_timer_interrupt() to be usable by other callsides.
> 
> This is preparatory work for the conversion of the NOHZ timer
> placement to a pull at expiry time model. No functional change.
> 
> Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
[...]
> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> index ff41d978cb22..dfc744545159 100644
> --- a/kernel/time/timer.c
> +++ b/kernel/time/timer.c
> @@ -2040,31 +2071,9 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
>  		if (time_before(nextevt, basej))
>  			nextevt = basej;
>  		tevt.local = basem + (u64)(nextevt - basej) * TICK_NSEC;
> -		goto unlock;
> +		tevt.global = KTIME_MAX;
>  	}
>  
> -	/*
> -	 * If the bases are marked idle, i.e. the next event on both the
> -	 * local and the global queue are farther away than a tick,
> -	 * evaluate both bases. No need to check whether one of the bases
> -	 * has an already expired timer as this is caught by the !is_idle
> -	 * condition above.
> -	 */
> -	if (base_local->timers_pending)
> -		tevt.local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
> -
> -	/*
> -	 * If the local queue expires first, then the global event can be
> -	 * ignored. The CPU wakes up before that. If the global queue is
> -	 * empty, nothing to do either.
> -	 */
> -	if (!local_first && base_global->timers_pending)
> -		tevt.global = basem + (u64)(nextevt_global - basej) * TICK_NSEC;
> -
> -unlock:
> -	raw_spin_unlock(&base_global->lock);
> -	raw_spin_unlock(&base_local->lock);
> -
>  	tevt.local = min_t(u64, tevt.local, tevt.global);

So if you leave that last line, it means that the CPU will eventually
and unconditionally wake up for the next global timer if it's before the
next local timer. Am I understanding this right and, if so, is that intended?

Thanks.

Re: [PATCH v5 11/18] timer: Split out "get next timer interrupt" functionality

[Frederic Weisbecker]

On Thu, Mar 09, 2023 at 05:30:12PM +0100, Frederic Weisbecker wrote:
> Le Wed, Mar 01, 2023 at 03:17:37PM +0100, Anna-Maria Behnsen a écrit :
> > The functionallity for getting the next timer interrupt in
> > get_next_timer_interrupt() is splitted into a separate function
> > fetch_next_timer_interrupt() to be usable by other callsides.
> > 
> > This is preparatory work for the conversion of the NOHZ timer
> > placement to a pull at expiry time model. No functional change.
> > 
> > Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
> [...]
> > diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> > index ff41d978cb22..dfc744545159 100644
> > --- a/kernel/time/timer.c
> > +++ b/kernel/time/timer.c
> > @@ -2040,31 +2071,9 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
> >  		if (time_before(nextevt, basej))
> >  			nextevt = basej;
> >  		tevt.local = basem + (u64)(nextevt - basej) * TICK_NSEC;
> > -		goto unlock;
> > +		tevt.global = KTIME_MAX;
> >  	}
> >  
> > -	/*
> > -	 * If the bases are marked idle, i.e. the next event on both the
> > -	 * local and the global queue are farther away than a tick,
> > -	 * evaluate both bases. No need to check whether one of the bases
> > -	 * has an already expired timer as this is caught by the !is_idle
> > -	 * condition above.
> > -	 */
> > -	if (base_local->timers_pending)
> > -		tevt.local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
> > -
> > -	/*
> > -	 * If the local queue expires first, then the global event can be
> > -	 * ignored. The CPU wakes up before that. If the global queue is
> > -	 * empty, nothing to do either.
> > -	 */
> > -	if (!local_first && base_global->timers_pending)
> > -		tevt.global = basem + (u64)(nextevt_global - basej) * TICK_NSEC;
> > -
> > -unlock:
> > -	raw_spin_unlock(&base_global->lock);
> > -	raw_spin_unlock(&base_local->lock);
> > -
> >  	tevt.local = min_t(u64, tevt.local, tevt.global);
> 
> So if you leave that last line, it means that the CPU will eventually
> and unconditionally wake up for the next global timer if it's before the
> next local timer. Am I understanding this right and, if so, is that intended?

Nevermind, that's removed on the main patch.

Sorry for the noise.

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Frederic Weisbecker]

Le Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen a écrit :
> diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
> new file mode 100644
> index 000000000000..5a600de3623b
> --- /dev/null
> +++ b/kernel/time/timer_migration.c
> +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;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +	newstate = curstate = data->groupstate;
> +
> +retry:
> +	walk_done = true;
> +
> +	if (newstate.migrator == TMIGR_NONE) {
> +		newstate.migrator = (u8)childmask;
> +
> +		/* Changes need to be propagated */
> +		walk_done = false;
> +	}
> +
> +	newstate.active |= (u8)childmask;
> +
> +	newstate.seq++;

Are you sure you need this seq counter? What bad scenario can happen without it?

Thanks.
> 

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Anna-Maria Behnsen]

[-- Attachment #1: Type: text/plain, Size: 3271 bytes --]

On Tue, 14 Mar 2023, Frederic Weisbecker wrote:

> Le Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen a écrit :
> > diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
> > new file mode 100644
> > index 000000000000..5a600de3623b
> > --- /dev/null
> > +++ b/kernel/time/timer_migration.c
> > +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;
> > +	u32 childmask;
> > +
> > +	childmask = data->childmask;
> > +	newstate = curstate = data->groupstate;
> > +
> > +retry:
> > +	walk_done = true;
> > +
> > +	if (newstate.migrator == TMIGR_NONE) {
> > +		newstate.migrator = (u8)childmask;
> > +
> > +		/* Changes need to be propagated */
> > +		walk_done = false;
> > +	}
> > +
> > +	newstate.active |= (u8)childmask;
> > +
> > +	newstate.seq++;
> 
> Are you sure you need this seq counter? What bad scenario can happen without it?
> 

Without the seq counter we might get an inconsistent overall state of the
groups when the order of propagating two changes of the child to the parent
changes. To clarify what I mean, let me give you an example what happens
without seqcount (maybe this should be described more detailed in the union
tmigr_state description...).

Let's take three groups and four CPUs (CPU2 and CPU3 as well as Group C
will not change during the scenario):

   	      	  Group A
		  migrator = Group B
		  active = Group B, Group C
	       /             \
    Group B			Group C
    migrator = CPU0		migrator = CPU2
    active = CPU0		active = CPU2
     /    \ 			 /  \
   CPU0   CPU1	 	      CPU2  CPU3
  active  idle               active idle


1. CPU0 goes idle (changes are updated in Group B; afterwards current
states of Group B and Group A are stored in the data for walking the
hierarchy):

   	      	  Group A
		  migrator = Group B
		  active = Group B, Group C
	       /             \
    Group B			Group C
->  migrator = TMIGR_NONE	migrator = CPU2
->  active =    		active = CPU2
     /    \ 			 /  \
   CPU0   CPU1	 	      CPU2  CPU3
-> idle   idle               active idle


2. CPU1 comes out of idle (changes are update in Group B; afterwards
current states of Group B and Group A are stored in the data for walking
the hierarchy):

   	      	  Group A
		  migrator = Group B
		  active = Group B, Group C
	       /             \
    Group B			Group C
->  migrator = CPU1		migrator = CPU2
->  active = CPU1   		active = CPU2
     /    \ 			 /  \
   CPU0   CPU1	 	      CPU2  CPU3
   idle -> active            active idle


3. Here comes the change of the order: Propagating the changes of
   2. through the hierarchy to group A - nothing to be done, because Group
   B is already up to date.

4. Propagating the changes of 1. through the hierarchy to group A:

   	      	  Group A
	      ->  migrator = Group C
	      ->  active =  Group C
	       /             \
    Group B			Group C
    migrator = CPU1		migrator = CPU2
    active = CPU1   		active = CPU2
     /    \ 			 /  \
   CPU0   CPU1	 	      CPU2  CPU3
   idle  active              active idle

And now we have this inconsistent overall state...

Thanks,

	Anna-Maria

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Frederic Weisbecker]

Le Tue, Mar 14, 2023 at 03:49:38PM +0100, Anna-Maria Behnsen a écrit :
> On Tue, 14 Mar 2023, Frederic Weisbecker wrote:
> 
> > Le Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen a écrit :
> > > diff --git a/kernel/time/timer_migration.c b/kernel/time/timer_migration.c
> > > new file mode 100644
> > > index 000000000000..5a600de3623b
> > > --- /dev/null
> > > +++ b/kernel/time/timer_migration.c
> > > +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;
> > > +	u32 childmask;
> > > +
> > > +	childmask = data->childmask;
> > > +	newstate = curstate = data->groupstate;
> > > +
> > > +retry:
> > > +	walk_done = true;
> > > +
> > > +	if (newstate.migrator == TMIGR_NONE) {
> > > +		newstate.migrator = (u8)childmask;
> > > +
> > > +		/* Changes need to be propagated */
> > > +		walk_done = false;
> > > +	}
> > > +
> > > +	newstate.active |= (u8)childmask;
> > > +
> > > +	newstate.seq++;
> > 
> > Are you sure you need this seq counter? What bad scenario can happen without it?
> > 
> 
> Without the seq counter we might get an inconsistent overall state of the
> groups when the order of propagating two changes of the child to the parent
> changes. To clarify what I mean, let me give you an example what happens
> without seqcount (maybe this should be described more detailed in the union
> tmigr_state description...).
> 
> Let's take three groups and four CPUs (CPU2 and CPU3 as well as Group C
> will not change during the scenario):
> 
>    	      	  Group A
> 		  migrator = Group B
> 		  active = Group B, Group C
> 	       /             \
>     Group B			Group C
>     migrator = CPU0		migrator = CPU2
>     active = CPU0		active = CPU2
>      /    \ 			 /  \
>    CPU0   CPU1	 	      CPU2  CPU3
>   active  idle               active idle
> 
> 
> 1. CPU0 goes idle (changes are updated in Group B; afterwards current
> states of Group B and Group A are stored in the data for walking the
> hierarchy):
> 
>    	      	  Group A
> 		  migrator = Group B
> 		  active = Group B, Group C
> 	       /             \
>     Group B			Group C
> ->  migrator = TMIGR_NONE	migrator = CPU2
> ->  active =    		active = CPU2
>      /    \ 			 /  \
>    CPU0   CPU1	 	      CPU2  CPU3
> -> idle   idle               active idle
> 
> 
> 2. CPU1 comes out of idle (changes are update in Group B; afterwards
> current states of Group B and Group A are stored in the data for walking
> the hierarchy):
> 
>    	      	  Group A
> 		  migrator = Group B
> 		  active = Group B, Group C
> 	       /             \
>     Group B			Group C
> ->  migrator = CPU1		migrator = CPU2
> ->  active = CPU1   		active = CPU2
>      /    \ 			 /  \
>    CPU0   CPU1	 	      CPU2  CPU3
>    idle -> active            active idle
> 
> 
> 3. Here comes the change of the order: Propagating the changes of
>    2. through the hierarchy to group A - nothing to be done, because Group
>    B is already up to date.
> 
> 4. Propagating the changes of 1. through the hierarchy to group A:
> 
>    	      	  Group A
> 	      ->  migrator = Group C
> 	      ->  active =  Group C
> 	       /             \
>     Group B			Group C
>     migrator = CPU1		migrator = CPU2
>     active = CPU1   		active = CPU2
>      /    \ 			 /  \
>    CPU0   CPU1	 	      CPU2  CPU3
>    idle  active              active idle
> 
> And now we have this inconsistent overall state..

Ooh I see now. Also that can't ever wrap up since you can only ever have no more than 8 racers
competing on a given node.

Tricky ;)

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Frederic Weisbecker]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
> +				   unsigned long jif)
> +{
> +	struct timer_events tevt;
> +	struct tmigr_walk data;
> +	struct tmigr_cpu *tmc;
> +	u64 next = KTIME_MAX;
> +	unsigned long flags;
> +
> +	tmc = per_cpu_ptr(&tmigr_cpu, cpu);
> +
> +	raw_spin_lock_irqsave(&tmc->lock, flags);
> +	/*
> +	 * Remote CPU is offline or no longer idle or other cpu handles cpu
> +	 * timers already or next event was already expired - return!
> +	 */
> +	if (!tmc->online || tmc->remote || tmc->cpuevt.ignore ||
> +	    now < tmc->cpuevt.nextevt.expires) {
> +		raw_spin_unlock_irqrestore(&tmc->lock, flags);
> +		return next;
> +	}
> +
> +	tmc->remote = 1;
> +
> +	/* Drop the lock to allow the remote CPU to exit idle */
> +	raw_spin_unlock_irqrestore(&tmc->lock, flags);
> +
> +	if (cpu != smp_processor_id())
> +		timer_expire_remote(cpu);
> +
> +	/* next event of cpu */
> +	fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu);

If the target CPU gets an idle interrupt right after the above call and enqueues
a new timer (which becomes the new earliest), tmigr_cpu_deactivate() ->
tmigr_new_timer() is going to ignore it due to tmc->remote = 1, right?

Or am I missing something else that would make that timer correctly handled?

Thanks.

Re: [PATCH v5 00/18] timer: Move from a push remote at enqueue to a pull at expiry model

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:26PM +0100, Anna-Maria Behnsen wrote:
> quater of the remaining CPUs was kept busy. This measurement was repeated

/me hands you a bucket of spare 'r' :-)

Re: [PATCH v5 03/18] timer: Move store of next event into __next_timer_interrupt()

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:29PM +0100, Anna-Maria Behnsen wrote:
> Both call sides of __next_timer_interrupt() store return value directly in

             ^^ sites

> base->next_expiry. Move the store into __next_timer_interrupt() and to make

+its

> purpose more clear, rename function to next_expiry_recalc().
> 
> No functional change.
> 
> Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
> Reviewed-by: Thomas Gleixner <tglx@linutronix.de>
> ---
>  kernel/time/timer.c | 11 +++++++----
>  1 file changed, 7 insertions(+), 4 deletions(-)
> 
> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> index ffb94bc3852f..08e855727ff8 100644
> --- a/kernel/time/timer.c
> +++ b/kernel/time/timer.c
> @@ -1803,8 +1803,10 @@ static int next_pending_bucket(struct timer_base *base, unsigned offset,
>  /*
>   * Search the first expiring timer in the various clock levels. Caller must
>   * hold base->lock.
> + *
> + * Store next expiry time in base->next_expiry.
>   */
> -static unsigned long __next_timer_interrupt(struct timer_base *base)
> +static void next_expiry_recalc(struct timer_base *base)
>  {
>  	unsigned long clk, next, adj;
>  	unsigned lvl, offset = 0;
> @@ -1870,10 +1872,11 @@ static unsigned long __next_timer_interrupt(struct timer_base *base)
>  		clk += adj;
>  	}
>  
> +	base->next_expiry = next;
>  	base->next_expiry_recalc = false;
>  	base->timers_pending = !(next == base->clk + NEXT_TIMER_MAX_DELTA);
>  
> -	return next;
> +	return;
>  }

Can skip the return statement for a void function entirely if it is the
last statement.

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Frederic Weisbecker]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +static bool tmigr_inactive_up(struct tmigr_group *group,
> +			      struct tmigr_group *child,
> +			      void *ptr)
> +{
> +	union tmigr_state curstate, newstate;
> +	struct tmigr_walk *data = ptr;
> +	bool walk_done;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +	newstate = curstate = data->groupstate;
> +
> +retry:
> +	walk_done = true;
> +
> +	/* Reset active bit when child is no longer active */
> +	if (!data->childstate.active)
> +		newstate.active &= ~(u8)childmask;
> +
> +	if (newstate.migrator == (u8)childmask) {
> +		/*
> +		 * Find a new migrator for the group, because child group
> +		 * is idle!
> +		 */
> +		if (!data->childstate.active) {
> +			unsigned long new_migr_bit, active = newstate.active;
> +
> +			new_migr_bit = find_first_bit(&active, BIT_CNT);
> +
> +			/* Changes need to be propagated */
> +			walk_done = false;

Do you need to propagate the changes even if you found a new migrator for the
group?

> +
> +			if (new_migr_bit != BIT_CNT)
> +				newstate.migrator = BIT(new_migr_bit);
> +			else
> +				newstate.migrator = TMIGR_NONE;

Thanks.

Re: [PATCH v5 11/18] timer: Split out "get next timer interrupt" functionality

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:37PM +0100, Anna-Maria Behnsen wrote:
> The functionallity for getting the next timer interrupt in
> get_next_timer_interrupt() is splitted into a separate function

s/splitted/split/ -- also in other patches (8 iirc). Split is an
irregular verb and the past tense is the same as the present tense.

Re: [PATCH v5 14/18] timer: Check if timers base is handled already

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:40PM +0100, Anna-Maria Behnsen wrote:
> Due to the conversion of the NOHZ timer placement to a pull at expiry
> time model, the per CPU timer bases with non pinned timers are no
> longer handled only by the local CPU. In case a remote CPU already
> expires the non pinned timers base of the local cpu, nothing more
> needs to be done by the local CPU. A check at the begin of the expire
> timers routine is required, because timer base lock is dropped before
> executing the timer callback function.
> 
> This is a preparatory work, but has no functional impact right now.
> 
> Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
> ---
>  kernel/time/timer.c | 3 +++
>  1 file changed, 3 insertions(+)
> 
> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> index be085e94afcc..9553da99e262 100644
> --- a/kernel/time/timer.c
> +++ b/kernel/time/timer.c
> @@ -2144,6 +2144,9 @@ static inline void __run_timers(struct timer_base *base)
>  
>  	lockdep_assert_held(&base->lock);
>  
> +	if (!!base->running_timer)
> +		return;

You can leave out the double-negation, 'if (base->running_timer)' is
equivalent and reads much easier.

>  	while (time_after_eq(jiffies, base->clk) &&
>  	       time_after_eq(jiffies, base->next_expiry)) {
>  		levels = collect_expired_timers(base, heads);
> -- 
> 2.30.2
> 

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +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;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +	newstate = curstate = data->groupstate;
> +
> +retry:
> +	walk_done = true;
> +
> +	if (newstate.migrator == TMIGR_NONE) {
> +		newstate.migrator = (u8)childmask;
> +
> +		/* Changes need to be propagated */
> +		walk_done = false;
> +	}
> +
> +	newstate.active |= (u8)childmask;
> +
> +	newstate.seq++;
> +
> +	if (atomic_cmpxchg(group->migr_state, curstate.state, newstate.state) != curstate.state) {
> +		newstate.state = curstate.state = atomic_read(group->migr_state);
> +		goto retry;
> +	}

	if (!atomic_try_cmpxchg(group->migr_state, &curstate.state, newstate.state)) {
		newstate.state = curstate.state;
		goto retry;
	}

> +
> +	if (group->parent && (walk_done == false)) {
> +		data->groupstate.state = atomic_read(group->parent->migr_state);
> +		data->childmask = group->childmask;
> +	}
> +
> +	/*
> +	 * Group is active, event will be ignored - bit is updated without
> +	 * holding the lock. In case bit is set while another CPU already
> +	 * handles remote events, nothing happens, because it is clear that
> +	 * CPU became active just in this moment, or in worst case event is
> +	 * handled remote. Nothing to worry about.
> +	 */
> +	group->groupevt.ignore = 1;
> +
> +	return walk_done;
> +}

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +static bool tmigr_inactive_up(struct tmigr_group *group,
> +			      struct tmigr_group *child,
> +			      void *ptr)
> +{
> +	union tmigr_state curstate, newstate;
> +	struct tmigr_walk *data = ptr;
> +	bool walk_done;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +	newstate = curstate = data->groupstate;
> +
> +retry:
> +	walk_done = true;
> +
> +	/* Reset active bit when child is no longer active */
> +	if (!data->childstate.active)
> +		newstate.active &= ~(u8)childmask;
> +
> +	if (newstate.migrator == (u8)childmask) {
> +		/*
> +		 * Find a new migrator for the group, because child group
> +		 * is idle!
> +		 */
> +		if (!data->childstate.active) {
> +			unsigned long new_migr_bit, active = newstate.active;
> +
> +			new_migr_bit = find_first_bit(&active, BIT_CNT);
> +
> +			/* Changes need to be propagated */
> +			walk_done = false;
> +
> +			if (new_migr_bit != BIT_CNT)
> +				newstate.migrator = BIT(new_migr_bit);
> +			else
> +				newstate.migrator = TMIGR_NONE;
> +		}
> +	}
> +
> +	newstate.seq++;
> +
> +	DBG_BUG_ON((newstate.migrator != TMIGR_NONE) && !(newstate.active));
> +
> +	if (atomic_cmpxchg(group->migr_state, curstate.state, newstate.state) != curstate.state) {
> +		/*
> +		 * Something changed in child/parent group in the meantime,
> +		 * reread the state of child and parent; Update of
> +		 * data->childstate is required for event handling;
> +		 */
> +		if (child)
> +			data->childstate.state = atomic_read(child->migr_state);
> +		newstate.state = curstate.state = atomic_read(group->migr_state);
> +
> +		goto retry;
> +	}

Idem:

	if (!atomic_try_cmpxchg(group->migr_state, &curstate.state, newstate.state)) {
		newstate.state = curstate.state;
		if (child)
			data->childstate.state = atomic_read(child->migr_state);
		goto retry;
	}

> +
> +	data->groupstate = newstate;
> +	data->remote = false;
> +
> +	/* Event Handling */
> +	tmigr_update_events(group, child, data);
> +
> +	if (group->parent && (walk_done == false)) {
> +		data->childmask = group->childmask;
> +		data->childstate = newstate;
> +		data->groupstate.state = atomic_read(group->parent->migr_state);
> +	}
> +
> +	/*
> +	 * data->nextexp was set by tmigr_update_events() and contains the
> +	 * expiry of first global event which needs to be handled
> +	 */
> +	if (data->nextexp != KTIME_MAX) {
> +		DBG_BUG_ON(group->parent);
> +		/*
> +		 * Toplevel path - If this cpu is about going offline wake
> +		 * up some random other cpu so it will take over the
> +		 * migrator duty and program its timer properly. Ideally
> +		 * wake the cpu with the closest expiry time, but that's
> +		 * overkill to figure out.
> +		 */
> +		if (!(this_cpu_ptr(&tmigr_cpu)->online)) {
> +			unsigned int cpu = smp_processor_id();
> +
> +			cpu = cpumask_any_but(cpu_online_mask, cpu);
> +			smp_send_reschedule(cpu);
> +		}
> +	}
> +
> +	return walk_done;
> +}

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +static bool tmigr_requires_handle_remote_up(struct tmigr_group *group,
> +					 struct tmigr_group *child,
> +					 void *ptr)
> +{
> +	struct tmigr_remote_data *data = ptr;
> +	u32 childmask;
> +
> +	childmask = data->childmask;
> +
> +	/*
> +	 * Handle the group only if 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;
> +
> +	/*
> +	 * Racy lockless check for next_expiry
> +	 */
> +	if (data->now >= group->next_expiry) {

I'm not far enough along to tell; but on 32bit this can/will suffer from
split loads and basically turn into a random number generator. I'm
presuming the 'check = 1' thing here covers that case?

> +		data->check = 1;
> +		return true;
> +	}
> +
> +	/* Update of childmask for next level */
> +	data->childmask = group->childmask;
> +	return false;
> +}

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Peter Zijlstra]

(since the code is structured such, I also wrote the comments bottom-up)

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:

> +static struct tmigr_group *tmigr_get_group(unsigned int cpu, unsigned int node,
> +					   unsigned int lvl)
> +{
> +	struct tmigr_group *tmp, *group = NULL;
> +	bool first_loop = true;
> +	atomic_t *migr_state;

When first reading this I was wondering what was protecting the lists;
since this is at least 2 deep from where you take the lock. Perhaps add:

	lockdep_assert_held(&tmigr_mutex);

to clarify the locking context.

> +
> +reloop:
> +	/* Try to attach to an exisiting 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_childs >= TMIGR_CHILDS_PER_GROUP)
> +			continue;
> +
> +		/*
> +		 * If this is the lowest level of the hierarchy, make sure
> +		 * that thread siblings share a group. It is only executed
> +		 * when siblings exist. ALL groups of lowest level needs to
> +		 * be checked for thread sibling, before thread cpu is
> +		 * added to a random group with capacity. When all groups
> +		 * are checked and no thread sibling was found, reloop of
> +		 * level zero groups is required to get a group with
> +		 * capacity.
> +		 */
> +		if (!lvl && (tmigr_cores_per_group != TMIGR_CHILDS_PER_GROUP)) {
> +			if (first_loop == true && !sibling_in_group(cpu, tmp)) {
> +				continue;
> +			} else if (first_loop == false) {
> +				if (tmp->num_cores >= tmigr_cores_per_group)
> +					continue;
> +				else
> +					tmp->num_cores++;
> +			}
> +		}
> +
> +		group = tmp;
> +		break;
> +	}
> +
> +	if (group) {
> +		return group;
> +	} else if (first_loop == true) {
> +		first_loop = false;
> +		goto reloop;
> +	}
> +
> +	/* Allocate and	set up a new group with corresponding migr_state */
> +	group = kzalloc_node(sizeof(*group), GFP_KERNEL, node);
> +	if (!group)
> +		return ERR_PTR(-ENOMEM);
> +
> +	migr_state = kzalloc_node(sizeof(atomic_t), GFP_KERNEL, node);
> +	if (!migr_state) {
> +		kfree(group);
> +		return ERR_PTR(-ENOMEM);
> +	}
> +
> +	tmigr_init_group(group, lvl, node, migr_state);
> +	/* 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;
> +	unsigned long flags;
> +
> +	raw_spin_lock_irqsave(&child->lock, flags);

Both callsites are in tmigr_setup_groups(), which must be ran in
preemptible context due to GFP_KERNEL allocations. Please use
raw_spin_lock_irq().

> +	raw_spin_lock_nested(&parent->lock, SINGLE_DEPTH_NESTING);
> +
> +	child->parent = parent;
> +	child->childmask = BIT(parent->num_childs++);
> +
> +	raw_spin_unlock(&parent->lock);
> +	raw_spin_unlock_irqrestore(&child->lock, flags);
> +
> +	/*
> +	 * To prevent inconsistent states, active childs needs to be active
> +	 * in new parent as well. Inactive childs are already marked
> +	 * inactive in parent group.
> +	 */
> +	childstate.state = atomic_read(child->migr_state);
> +	if (childstate.migrator != TMIGR_NONE) {
> +		struct tmigr_walk data;
> +
> +		data.childmask = child->childmask;
> +		data.groupstate.state = atomic_read(parent->migr_state);
> +
> +		/*
> +		 * There is only one new level per time. When connecting
> +		 * child and parent and set child active when parent is
> +		 * inactive, parent needs to be the upperst
> +		 * 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;
> +	size_t sz;
> +
> +	sz = sizeof(struct tmigr_group *) * tmigr_hierarchy_levels;
> +	stack = kzalloc(sz, GFP_KERNEL);
> +	if (!stack)
> +		return -ENOMEM;
> +
> +	do {
> +		group = tmigr_get_group(cpu, node, i);
> +		if (IS_ERR(group)) {
> +			err = IS_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;
> +		}
> +
> +		DBG_BUG_ON(i != group->level);
> +
> +		/*
> +		 * Update tmc -> group / child -> group connection
> +		 */
> +		if (i == 0) {
> +			struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
> +			unsigned long flags;
> +
> +			raw_spin_lock_irqsave(&group->lock, flags);

You're holding a mutex, you just did a GFP_KERNEL allocation; there is
no way IRQs are already disabled here, please use raw_spin_lock_irq() to
reduce confusion.

> +
> +			tmc->tmgroup = group;
> +			tmc->childmask = BIT(group->num_childs);
> +
> +			group->cpus[group->num_childs++] = cpu;
> +
> +			raw_spin_unlock_irqrestore(&group->lock, flags);
> +
> +			/* There are no childs that needs to be connected */
> +			continue;
> +		} else {
> +			child = stack[i - 1];
> +			tmigr_connect_child_parent(child, group);
> +		}
> +
> +		/* check if upperst level was newly created */
> +		if (top != i)
> +			continue;
> +
> +		DBG_BUG_ON(top == 0);
> +
> +		lvllist = &tmigr_level_list[top];
> +		if (group->num_childs == 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)
> +{
> +	unsigned 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);
> +	unsigned long flags;
> +	unsigned 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 = 1;
> +		tmc->cpuevt.cpu = cpu;
> +
> +		tmc->remote = 0;
> +		tmc->idle = 0;
> +		tmc->wakeup = KTIME_MAX;
> +	}
> +	raw_spin_lock_irqsave(&tmc->lock, flags);

You just called tmigr_add_cpu() which takes a mutex, there is no
possible way this can be called with IRQs already disabled. Please use
raw_spin_lock_irq() to reduce confusion.

Also, offline below does that and this is just inconsistent.

> +	__tmigr_cpu_activate(tmc);
> +	tmc->online = 1;
> +	raw_spin_unlock_irqrestore(&tmc->lock, flags);
> +	return 0;
> +}
> +
> +static int tmigr_cpu_offline(unsigned int cpu)
> +{
> +	struct tmigr_cpu *tmc = this_cpu_ptr(&tmigr_cpu);
> +
> +	raw_spin_lock_irq(&tmc->lock);
> +	tmc->online = 0;
> +	__tmigr_cpu_deactivate(tmc, KTIME_MAX);
> +	raw_spin_unlock_irq(&tmc->lock);
> +
> +	return 0;
> +}

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> +		/*
> +		 * There is only one new level per time. When connecting
> +		 * child and parent and set child active when parent is
> +		 * inactive, parent needs to be the upperst
> +		 * level. Otherwise there went something wrong!
> +		 */

> +		/* check if upperst level was newly created */

Sorry for being a pain and with the caveat that I'm not a native speaker
either, but I think upperst should be uppermost. You actually had me
google to see what the word meant..

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:

> +	group->num_childs = 0;
k
> +	 * To prevent inconsistent states, active childs needs to be active
> +	 * in new parent as well. Inactive childs are already marked
> +	 * inactive in parent group.
> +	 */

> +			/* There are no childs that needs to be connected */

s/childs/children/ and s/needs/need/

The child needs ...
The children need ...

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:

> +static void tmigr_init_group(struct tmigr_group *group, unsigned int lvl,
> +			     unsigned int node, atomic_t *migr_state)
> +{
> +	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_childs = 0;
> +
> +	/*
> +	 * num_cores is required for level=0 groups only during setup and
> +	 * when siblings exists but it doesn't matter if this value is set
> +	 * in other groups as well
> +	 */
> +	group->num_cores = 1;
> +
> +	s.migrator = TMIGR_NONE;
> +	s.active = 0;
> +	s.seq = 0;
> +	atomic_set(migr_state, s.state);
> +
> +	group->migr_state = migr_state;
> +
> +	timerqueue_init_head(&group->events);
> +	timerqueue_init(&group->groupevt.nextevt);
> +	group->groupevt.nextevt.expires = KTIME_MAX;
> +	group->next_expiry = KTIME_MAX;
> +	group->groupevt.ignore = 1;
> +}

> +static struct tmigr_group *tmigr_get_group(unsigned int cpu, unsigned int node,
> +					   unsigned int lvl)
> +{
> +	struct tmigr_group *tmp, *group = NULL;
> +	bool first_loop = true;
> +	atomic_t *migr_state;
> +

...

> +
> +	/* Allocate and	set up a new group with corresponding migr_state */
> +	group = kzalloc_node(sizeof(*group), GFP_KERNEL, node);
> +	if (!group)
> +		return ERR_PTR(-ENOMEM);
> +
> +	migr_state = kzalloc_node(sizeof(atomic_t), GFP_KERNEL, node);
> +	if (!migr_state) {
> +		kfree(group);
> +		return ERR_PTR(-ENOMEM);
> +	}
> +
> +	tmigr_init_group(group, lvl, node, migr_state);

I'm confused by migr_state.. why is that allocated seperately, if it is
*always* 1:1 related to the group. Why isn't it a direct member?

> +	/* Setup successful. Add it to the hierarchy */
> +	list_add(&group->list, &tmigr_level_list[lvl]);
> +	return group;
> +}

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Peter Zijlstra]

On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:

> diff --git a/kernel/time/timer_migration.h b/kernel/time/timer_migration.h
> new file mode 100644
> index 000000000000..ceb336e705df
> --- /dev/null
> +++ b/kernel/time/timer_migration.h
> @@ -0,0 +1,123 @@
> +#ifndef _KERNEL_TIME_MIGRATION_H
> +#define _KERNEL_TIME_MIGRATION_H
> +
> +/* Per group capacity. Must be a power of 2! */
> +#define TMIGR_CHILDS_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;
> +	int			ignore;
> +};
> +
> +/**
> + * struct tmigr_group - timer migration hierarchy group
> + * @lock:		Lock protecting the event information
> + * @cpus:		Array with CPUs which are member of group; required for
> + *			sibling CPUs; used only when level == 0

That's 32 bytes wasted for every group that isn't 0, maybe stick on the
end and conditionally allocate? Also, afaict it is only ever used during
setup, and as such should not be placed in a hot line, unless you've
done that explicitly as padding, in which case it needs a comment to
that effect.

Also, since it's setup only, why can't you match against:

  per_cpu_ptr(&tmigr_cpu, cpu)->parent

?

> + * @parent:		Pointer to parent group
> + * @list:		List head that is added to per level tmigr_level_list

Also setup only?

> + * @level:		Hierarchy level of group
> + * @numa_node:		Is set to numa node when level < tmigr_crossnode_level;
> + *			otherwise it is set to NUMA_NO_NODE; Required for setup
> + *			only
> + * @num_childs:		Counter of group childs; Required for setup only
> + * @num_cores:		Counter of cores per group; Required for setup only when
> + *			level == 0 and siblings exist

Also setup only, move the end?

> + * @migr_state:		State of group (see struct tmigr_state)
> + * @childmask:		childmask of group in parent group; is set during setup
> + *			never changed; could be read lockless
> + * @events:		Timer queue for child events queued in the group
> + * @groupevt:		Next event of group; it is only reliable when group is
> + *			!active (ignore bit is set when group is active)
> + * @next_expiry:	Base monotonic expiry time of next event of group;
> + *			Used for racy lockless check whether remote expiry is
> + *			required; it is always reliable

This is basically leftmost of @events? A racy lockless check sorta
implies not reliable, comment is confusing.

Also, isn't this identical to @groupevt.nextevt.expiry ?

> + */
> +struct tmigr_group {
> +	raw_spinlock_t		lock;
> +	unsigned int		cpus[TMIGR_CHILDS_PER_GROUP];
> +	struct tmigr_group	*parent;
> +	struct list_head	list;
> +	unsigned int		level;
> +	unsigned int		numa_node;
> +	unsigned int		num_childs;
> +	unsigned int		num_cores;
> +	atomic_t		*migr_state;

Per the other email; why isn't this:

	union tmigr_state	migr_state;

?

> +	u32			childmask;
> +	struct timerqueue_head	events;
> +	struct tmigr_event	groupevt;
> +	u64			next_expiry;
> +};
> +
> +/**
> + * struct tmigr_cpu - timer migration per CPU group
> + * @lock:	Lock protecting tmigr_cpu group information
> + * @online:	Indicates wheter CPU is online

What I'm missing is *why* we're keeping this state. I suspect you need
serialization on tmigr_cpu->lock between hotplug and something.

> + * @idle:	Indicates wheter CPU is idle in timer migration hierarchy
> + * @remote:	Is set when timers of CPU are expired remote

How are these not the same? When idle timers are expired remote, no?

> + * @tmgroup:	Pointer to parent group
> + * @childmask:	childmask of tmigr_cpu in parent group
> + * @cpuevt:	CPU event which could be queued into 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 when tmigr_cpu_deactive() is called and group is
> + *		idle; afterwards a reset to KTIME_MAX is required;
> + */
> +struct tmigr_cpu {
> +	raw_spinlock_t		lock;
> +	int			online;
> +	int			idle;
> +	int			remote;
> +	struct tmigr_group	*tmgroup;
> +	u32			childmask;
> +	struct tmigr_event	cpuevt;
> +	u64			wakeup;
> +};
> +
> +/**
> + * union tmigr_state - state of tmigr_group
> + * @state:	Combined version of the state - only used for atomic
> + * 		read/cmpxchg function
> + * @struct:	Splitted version of the state - only use the struct members to
> + *		update information to stay independant of endianess
> + */
> +union tmigr_state {
> +	u32 state;
> +	/**
> +	 * struct - splitted state of tmigr_group
> +	 * @active:	Contains each childmask bit of active childs
> +	 * @migrator:	Contains childmask of child which is migrator
> +	 * @seq:	Seqence number to prevent race when update in child
> +	 *		group are propagated in wrong order (especially when
> +	 *		migrator changes are involved)
> +	 */
> +	struct {
> +		u8	active;
> +		u8	migrator;

So childmask is the bit set in either of these masks, but it is u32
elsewhere and u8 here. Surely if the target type is u8, then it is best
to keep it consistently u8 elsewhere too, no?

> +		u16	seq;
> +	} __packed;
> +};

Re: [PATCH v5 00/18] timer: Move from a push remote at enqueue to a pull at expiry model

[Anna-Maria Behnsen]

On Tue, 21 Mar 2023, Peter Zijlstra wrote:

> On Wed, Mar 01, 2023 at 03:17:26PM +0100, Anna-Maria Behnsen wrote:
> > quater of the remaining CPUs was kept busy. This measurement was repeated
> 
> /me hands you a bucket of spare 'r' :-)
> 

Thanks for all the grammar fixes... this was the easy part :)

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Anna-Maria Behnsen]

On Tue, 21 Mar 2023, Frederic Weisbecker wrote:

> On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> > +static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
> > +				   unsigned long jif)
> > +{
> > +	struct timer_events tevt;
> > +	struct tmigr_walk data;
> > +	struct tmigr_cpu *tmc;
> > +	u64 next = KTIME_MAX;
> > +	unsigned long flags;
> > +
> > +	tmc = per_cpu_ptr(&tmigr_cpu, cpu);
> > +
> > +	raw_spin_lock_irqsave(&tmc->lock, flags);
> > +	/*
> > +	 * Remote CPU is offline or no longer idle or other cpu handles cpu
> > +	 * timers already or next event was already expired - return!
> > +	 */
> > +	if (!tmc->online || tmc->remote || tmc->cpuevt.ignore ||
> > +	    now < tmc->cpuevt.nextevt.expires) {
> > +		raw_spin_unlock_irqrestore(&tmc->lock, flags);
> > +		return next;
> > +	}
> > +
> > +	tmc->remote = 1;
> > +
> > +	/* Drop the lock to allow the remote CPU to exit idle */
> > +	raw_spin_unlock_irqrestore(&tmc->lock, flags);
> > +
> > +	if (cpu != smp_processor_id())
> > +		timer_expire_remote(cpu);
> > +
> > +	/* next event of cpu */
> > +	fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu);
> 
> If the target CPU gets an idle interrupt right after the above call and enqueues
> a new timer (which becomes the new earliest), tmigr_cpu_deactivate() ->
> tmigr_new_timer() is going to ignore it due to tmc->remote = 1, right?

It's worse. The newly enqueued timer is updated in the timer migration
hierarchy when CPU goes back idle and afterwards it will be overwritten by
the group walk propagating the old first timer in
tmigr_handle_remote_cpu()...

I will change the code after remote timer expiry:

1. take the remote timer bases locks
2. take the tmc->lock
3. get the next timer interrupt remote
4. drop the remote timer bases locks
5. propagate new timer changes
6. drop the tmc->lock

Thanks,

	Anna-Maria

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Frederic Weisbecker]

On Tue, Apr 04, 2023 at 04:05:27PM +0200, Anna-Maria Behnsen wrote:
> On Tue, 21 Mar 2023, Frederic Weisbecker wrote:
> 
> > On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> > > +static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
> > > +				   unsigned long jif)
> > > +{
> > > +	struct timer_events tevt;
> > > +	struct tmigr_walk data;
> > > +	struct tmigr_cpu *tmc;
> > > +	u64 next = KTIME_MAX;
> > > +	unsigned long flags;
> > > +
> > > +	tmc = per_cpu_ptr(&tmigr_cpu, cpu);
> > > +
> > > +	raw_spin_lock_irqsave(&tmc->lock, flags);
> > > +	/*
> > > +	 * Remote CPU is offline or no longer idle or other cpu handles cpu
> > > +	 * timers already or next event was already expired - return!
> > > +	 */
> > > +	if (!tmc->online || tmc->remote || tmc->cpuevt.ignore ||
> > > +	    now < tmc->cpuevt.nextevt.expires) {
> > > +		raw_spin_unlock_irqrestore(&tmc->lock, flags);
> > > +		return next;
> > > +	}
> > > +
> > > +	tmc->remote = 1;
> > > +
> > > +	/* Drop the lock to allow the remote CPU to exit idle */
> > > +	raw_spin_unlock_irqrestore(&tmc->lock, flags);
> > > +
> > > +	if (cpu != smp_processor_id())
> > > +		timer_expire_remote(cpu);
> > > +
> > > +	/* next event of cpu */
> > > +	fetch_next_timer_interrupt_remote(jif, now, &tevt, cpu);
> > 
> > If the target CPU gets an idle interrupt right after the above call and enqueues
> > a new timer (which becomes the new earliest), tmigr_cpu_deactivate() ->
> > tmigr_new_timer() is going to ignore it due to tmc->remote = 1, right?
> 
> It's worse. The newly enqueued timer is updated in the timer migration
> hierarchy when CPU goes back idle and afterwards it will be overwritten by
> the group walk propagating the old first timer in
> tmigr_handle_remote_cpu()...

Hmm then that would require the remote CPU to exit dynticks and then
re-enter dynticks, right? Yes, sounds possible too.

> 
> I will change the code after remote timer expiry:
> 
> 1. take the remote timer bases locks
> 2. take the tmc->lock
> 3. get the next timer interrupt remote
> 4. drop the remote timer bases locks
> 5. propagate new timer changes
> 6. drop the tmc->lock

Right that sounds good!

Thanks.

> 
> Thanks,
> 
> 	Anna-Maria

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Anna-Maria Behnsen]

On Thu, 23 Mar 2023, Peter Zijlstra wrote:

> On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> 
> > diff --git a/kernel/time/timer_migration.h b/kernel/time/timer_migration.h
> > new file mode 100644
> > index 000000000000..ceb336e705df
> > --- /dev/null
> > +++ b/kernel/time/timer_migration.h
> > @@ -0,0 +1,123 @@
> > +#ifndef _KERNEL_TIME_MIGRATION_H
> > +#define _KERNEL_TIME_MIGRATION_H
> > +
> > +/* Per group capacity. Must be a power of 2! */
> > +#define TMIGR_CHILDS_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;
> > +	int			ignore;
> > +};
> > +
> > +/**
> > + * struct tmigr_group - timer migration hierarchy group
> > + * @lock:		Lock protecting the event information
> > + * @cpus:		Array with CPUs which are member of group; required for
> > + *			sibling CPUs; used only when level == 0
> 
> That's 32 bytes wasted for every group that isn't 0, maybe stick on the
> end and conditionally allocate? Also, afaict it is only ever used during
> setup, and as such should not be placed in a hot line, unless you've
> done that explicitly as padding, in which case it needs a comment to
> that effect.
> 
> Also, since it's setup only, why can't you match against:
> 
>   per_cpu_ptr(&tmigr_cpu, cpu)->parent
> 
> ?

This cpus array is currently used to make sure siblings will end up in the
same level 0 group. When matching against the per_cpu_ptr(&tmigr_cpu,
cpu)->parent, I would need to rely on the topology mask and have a look if
the sibling already has a parent.

My question here is: Is it required that siblings end up in the same group
in level 0, or is it enough if the numa node is the same?

> > + * @parent:		Pointer to parent group
> > + * @list:		List head that is added to per level tmigr_level_list
> 
> Also setup only?

Jupp.

> > + * @level:		Hierarchy level of group
> > + * @numa_node:		Is set to numa node when level < tmigr_crossnode_level;
> > + *			otherwise it is set to NUMA_NO_NODE; Required for setup
> > + *			only
> > + * @num_childs:		Counter of group childs; Required for setup only
> > + * @num_cores:		Counter of cores per group; Required for setup only when
> > + *			level == 0 and siblings exist
> 
> Also setup only, move the end?

Same. Will move all the setup stuff to the end.

> > + * @migr_state:		State of group (see struct tmigr_state)
> > + * @childmask:		childmask of group in parent group; is set during setup
> > + *			never changed; could be read lockless
> > + * @events:		Timer queue for child events queued in the group
> > + * @groupevt:		Next event of group; it is only reliable when group is
> > + *			!active (ignore bit is set when group is active)
> > + * @next_expiry:	Base monotonic expiry time of next event of group;
> > + *			Used for racy lockless check whether remote expiry is
> > + *			required; it is always reliable
> 
> This is basically leftmost of @events? A racy lockless check sorta
> implies not reliable, comment is confusing.

It's always updated and contains the expiry value of the first event which
is enqueued into timer queue "events" - reliable is the wrong term here.

> Also, isn't this identical to @groupevt.nextevt.expiry ?

No, it is not identical. Because groupevt is only used and reliable, when
the group is idle to enqueue the first group event into the parent
group. But the migrator of the group needs to check whether timers needs to
be handled remote because some children are idle. Therefore I do not have to
update the whole event.

> > + */
> > +struct tmigr_group {
> > +	raw_spinlock_t		lock;
> > +	unsigned int		cpus[TMIGR_CHILDS_PER_GROUP];
> > +	struct tmigr_group	*parent;
> > +	struct list_head	list;
> > +	unsigned int		level;
> > +	unsigned int		numa_node;
> > +	unsigned int		num_childs;
> > +	unsigned int		num_cores;
> > +	atomic_t		*migr_state;
> 
> Per the other email; why isn't this:
> 
> 	union tmigr_state	migr_state;
> 
> ?

I will change this into a direct member. The reason for not being a direct
member is - because it grows like this...

Only for handling the tmigr_group->migr_state, atomic operations are used
the splitted members are never accessed. All other states are not handled
with atomic operations. If it is 'union tmigr_state' inside the
tmigr_group, then I would need an atomic_t inside the union and the union
gets more complex. I hope I was able to explain my point.

> > +	u32			childmask;
> > +	struct timerqueue_head	events;
> > +	struct tmigr_event	groupevt;
> > +	u64			next_expiry;
> > +};
> > +

I come back to your other remarks in a separate mail.

Thanks,

	Anna-Maria

Re: [PATCH v5 16/18] timer: Implement the hierarchical pull model

[Anna-Maria Behnsen]

On Tue, 21 Mar 2023, Frederic Weisbecker wrote:

> On Wed, Mar 01, 2023 at 03:17:42PM +0100, Anna-Maria Behnsen wrote:
> > +static bool tmigr_inactive_up(struct tmigr_group *group,
> > +			      struct tmigr_group *child,
> > +			      void *ptr)
> > +{
> > +	union tmigr_state curstate, newstate;
> > +	struct tmigr_walk *data = ptr;
> > +	bool walk_done;
> > +	u32 childmask;
> > +
> > +	childmask = data->childmask;
> > +	newstate = curstate = data->groupstate;
> > +
> > +retry:
> > +	walk_done = true;
> > +
> > +	/* Reset active bit when child is no longer active */
> > +	if (!data->childstate.active)
> > +		newstate.active &= ~(u8)childmask;
> > +
> > +	if (newstate.migrator == (u8)childmask) {
> > +		/*
> > +		 * Find a new migrator for the group, because child group
> > +		 * is idle!
> > +		 */
> > +		if (!data->childstate.active) {
> > +			unsigned long new_migr_bit, active = newstate.active;
> > +
> > +			new_migr_bit = find_first_bit(&active, BIT_CNT);
> > +
> > +			/* Changes need to be propagated */
> > +			walk_done = false;
> 
> Do you need to propagate the changes even if you found a new migrator for the
> group?

No, you shouldn't require the walk then. Will think about it again, fix
(and test) it.

> > +
> > +			if (new_migr_bit != BIT_CNT)
> > +				newstate.migrator = BIT(new_migr_bit);
> > +			else
> > +				newstate.migrator = TMIGR_NONE;
> 
> Thanks.
> 

Thanks,

	Anna-Maria

Re: [PATCH v5 02/18] timer: Add comment to get_next_timer_interrupt() description

[Frederic Weisbecker]

On Wed, Mar 01, 2023 at 03:17:28PM +0100, Anna-Maria Behnsen wrote:
> get_next_timer_interrupt() does more than simply getting the next timer
> interrupt. The timer bases are forwarded and also marked as idle whenever
> possible.
> 
> To get not confused, add a comment to function description.
> 
> Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
> ---
> v5: New patch, which adds only a comment to get_next_timer_interrupt()
> instead of changing the function name
> ---
>  kernel/time/timer.c | 4 ++++
>  1 file changed, 4 insertions(+)
> 
> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> index 63a8ce7177dd..ffb94bc3852f 100644
> --- a/kernel/time/timer.c
> +++ b/kernel/time/timer.c
> @@ -1915,6 +1915,10 @@ static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
>   * @basej:	base time jiffies
>   * @basem:	base time clock monotonic
>   *
> + * If required, base->clk is forwarded and base is also marked as
> + * idle. Idle handling of timer bases is allowed only to be done by CPU
> + * itself.

Idle marking you mean? Because idle handling can be done remotely after
this patchset.

Thanks.

> + *
>   * Returns the tick aligned clock monotonic time of the next pending
>   * timer or KTIME_MAX if no timer is pending.
>   */
> -- 
> 2.30.2
> 

Re: [PATCH v5 02/18] timer: Add comment to get_next_timer_interrupt() description

[Anna-Maria Behnsen]

On Tue, 11 Apr 2023, Frederic Weisbecker wrote:

> On Wed, Mar 01, 2023 at 03:17:28PM +0100, Anna-Maria Behnsen wrote:
> > get_next_timer_interrupt() does more than simply getting the next timer
> > interrupt. The timer bases are forwarded and also marked as idle whenever
> > possible.
> > 
> > To get not confused, add a comment to function description.
> > 
> > Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
> > ---
> > v5: New patch, which adds only a comment to get_next_timer_interrupt()
> > instead of changing the function name
> > ---
> >  kernel/time/timer.c | 4 ++++
> >  1 file changed, 4 insertions(+)
> > 
> > diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> > index 63a8ce7177dd..ffb94bc3852f 100644
> > --- a/kernel/time/timer.c
> > +++ b/kernel/time/timer.c
> > @@ -1915,6 +1915,10 @@ static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
> >   * @basej:	base time jiffies
> >   * @basem:	base time clock monotonic
> >   *
> > + * If required, base->clk is forwarded and base is also marked as
> > + * idle. Idle handling of timer bases is allowed only to be done by CPU
> > + * itself.
> 
> Idle marking you mean? Because idle handling can be done remotely after
> this patchset.
> 

Jupp, will change idle handling to "idle marking".

Thanks,

	Anna-Maria

Re: [PATCH v5 02/18] timer: Add comment to get_next_timer_interrupt() description

[Frederic Weisbecker]

Le Tue, Apr 11, 2023 at 06:10:25PM +0200, Anna-Maria Behnsen a écrit :
> On Tue, 11 Apr 2023, Frederic Weisbecker wrote:
> 
> > On Wed, Mar 01, 2023 at 03:17:28PM +0100, Anna-Maria Behnsen wrote:
> > > get_next_timer_interrupt() does more than simply getting the next timer
> > > interrupt. The timer bases are forwarded and also marked as idle whenever
> > > possible.
> > > 
> > > To get not confused, add a comment to function description.
> > > 
> > > Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
> > > ---
> > > v5: New patch, which adds only a comment to get_next_timer_interrupt()
> > > instead of changing the function name
> > > ---
> > >  kernel/time/timer.c | 4 ++++
> > >  1 file changed, 4 insertions(+)
> > > 
> > > diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> > > index 63a8ce7177dd..ffb94bc3852f 100644
> > > --- a/kernel/time/timer.c
> > > +++ b/kernel/time/timer.c
> > > @@ -1915,6 +1915,10 @@ static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
> > >   * @basej:	base time jiffies
> > >   * @basem:	base time clock monotonic
> > >   *
> > > + * If required, base->clk is forwarded and base is also marked as
> > > + * idle. Idle handling of timer bases is allowed only to be done by CPU
> > > + * itself.
> > 
> > Idle marking you mean? Because idle handling can be done remotely after
> > this patchset.
> > 
> 
> Jupp, will change idle handling to "idle marking".

Thanks and then please add:

Reviewed-by: Frederic Weisbecker <frederic@kernel.org>

(Trying to mark patches I don't need to review again on the next take :-)

Re: [PATCH v5 03/18] timer: Move store of next event into __next_timer_interrupt()

[Frederic Weisbecker]

Le Wed, Mar 01, 2023 at 03:17:29PM +0100, Anna-Maria Behnsen a écrit :
> Both call sides of __next_timer_interrupt() store return value directly in
> base->next_expiry. Move the store into __next_timer_interrupt() and to make
> purpose more clear, rename function to next_expiry_recalc().
> 
> No functional change.
> 
> Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>
> Reviewed-by: Thomas Gleixner <tglx@linutronix.de>

Aside Peter's remarks:

Reviewed-by: Frederic Weisbecker <frederic@kernel.org>

Re: [PATCH v5 07/18] timers: Ease code in run_local_timers()

[Frederic Weisbecker]

On Wed, Mar 01, 2023 at 03:17:33PM +0100, Anna-Maria Behnsen wrote:
> The logic for raising a softirq the way it is implemented right now, is
> readable for two timer bases. When increasing numbers of timer bases, code
> gets harder to read. With the introduction of the timer migration
> hierarchy, there will be three timer bases.
> 
> Therefore ease the code. No functional change.
> 
> Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>

Reviewed-by: Frederic Weisbecker <frederic@kernel.org>

Re: [PATCH v5 08/18] timers: Create helper function to forward timer base clk

[Frederic Weisbecker]

On Wed, Mar 01, 2023 at 03:17:34PM +0100, Anna-Maria Behnsen wrote:
> The logic for forwarding timer base clock is splitted into a separte
> function to make it accessible for other call sites.
> 
> No functional change.
> 
> Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>

Reviewed-by: Frederic Weisbecker <frederic@kernel.org>

Re: [PATCH v5 11/18] timer: Split out "get next timer interrupt" functionality

[Frederic Weisbecker]

Le Wed, Mar 01, 2023 at 03:17:37PM +0100, Anna-Maria Behnsen a écrit :
> The functionallity for getting the next timer interrupt in
> get_next_timer_interrupt() is splitted into a separate function
> fetch_next_timer_interrupt() to be usable by other callsides.
> 
> This is preparatory work for the conversion of the NOHZ timer
> placement to a pull at expiry time model. No functional change.
> 
> Signed-off-by: Anna-Maria Behnsen <anna-maria@linutronix.de>

Reviewed-by: Frederic Weisbecker <frederic@kernel.org>