Hi,
the cleanup patches are already applied and so the contains only two parts:
- Patches 1 - 4: timer base idle marking rework with two preparatory
changes. See the section below for more details.
- Patches 5 - 20: Updated timer pull model on top of timer idle rework
The queue is available here:
git://git.kernel.org/pub/scm/linux/kernel/git/tglx/devel timers/pushpull
Move marking timer bases as idle into tick_nohz_stop_tick()
-----------------------------------------------------------
The idle marking of timer bases is done in get_next_timer_interrupt()
whenever possible. The timer bases are idle, even if the tick will not be
stopped. This lead to an IPI when a new first timer is enqueued remote. To
prevent this, setting timer_base->in_idle flag is postponed to
tick_nohz_stop_tick().
Furthermore this synchronizes the states of timer base is_idle and
tick_stopped. With the timer pull model in place, also the idle state in
the hierarchy of a CPU is synchronized with the other idle related states.
Timer pull model
----------------
Placing timers at enqueue time on a target CPU based on dubious heuristics
does not make any sense:
1) Most timer wheel timers are canceled or rearmed before they expire.
2) The heuristics to predict which CPU will be busy when the timer expires
are wrong by definition.
So placing the timers at enqueue wastes precious cycles.
The proper solution to this problem is to always queue the timers on the
local CPU and allow the non pinned timers to be pulled onto a busy CPU at
expiry time.
Therefore split the timer storage into local pinned and global timers:
Local pinned timers are always expired on the CPU on which they have been
queued. Global timers can be expired on any CPU.
As long as a CPU is busy it expires both local and global timers. When a
CPU goes idle it arms for the first expiring local timer. If the first
expiring pinned (local) timer is before the first expiring movable timer,
then no action is required because the CPU will wake up before the first
movable timer expires. If the first expiring movable timer is before the
first expiring pinned (local) timer, then this timer is queued into 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 separated per node. If more than one CPU group
exist, then a second level in the hierarchy collects the groups. Depending
on the size of the system more than 2 levels are required. Each group has a
"migrator" which checks the timerqueue during the tick for remote timers to
be expired.
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
~~~~~~~
Enqueue
^^^^^^^
The impact of wasting cycles during enqueue by using the heuristic in
contrast to always queuing 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
quarter 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.
dbench test
^^^^^^^^^^^
A dbench test starting X pairs of client servers are used to create load on
the system. The measurable value is the throughput. The tests were executed
on a zen3 machine. The base is the tip tree branch timers/core which is
based on a v6.6-rc1.
governor menu
NR timers/core pull-model impact
----------------------------------------------
1 353.19 (0.19) 353.45 (0.30) 0.07%
2 700.10 (0.96) 687.00 (0.20) -1.87%
4 1329.37 (0.63) 1282.91 (0.64) -3.49%
8 2561.16 (1.28) 2493.56 (1.76) -2.64%
16 4959.96 (0.80) 4914.59 (0.64) -0.91%
32 9741.92 (3.44) 8979.83 (1.13) -7.82%
64 16535.40 (2.84) 16388.47 (4.02) -0.89%
128 22136.83 (2.42) 23174.50 (1.43) 4.69%
256 39256.77 (4.48) 38994.00 (0.39) -0.67%
512 36799.03 (1.83) 38091.10 (0.63) 3.51%
1024 32903.03 (0.86) 35370.70 (0.89) 7.50%
governor teo
NR timers/core pull-model impact
----------------------------------------------
1 350.83 (1.27) 352.45 (0.96) 0.46%
2 699.52 (0.85) 690.10 (0.54) -1.35%
4 1339.53 (1.99) 1294.71 (2.71) -3.35%
8 2574.10 (0.76) 2495.46 (1.97) -3.06%
16 4898.50 (1.74) 4783.06 (1.64) -2.36%
32 9115.50 (4.63) 9037.83 (1.58) -0.85%
64 16663.90 (3.80) 16042.00 (1.72) -3.73%
128 25044.93 (1.11) 23250.03 (1.08) -7.17%
256 38059.53 (1.70) 39658.57 (2.98) 4.20%
512 36369.30 (0.39) 38890.13 (0.36) 6.93%
1024 33956.83 (1.14) 35514.83 (0.29) 4.59%
Ping Pong Oberservation
^^^^^^^^^^^^^^^^^^^^^^^
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.
Possible 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.
v9..v10: https://lore.kernel.org/r/[email protected]/
- Address review Feedback of Bigeasy
v8..v9: https://lore.kernel.org/r/[email protected]
- Address review feedback
- Add more minor cleanup fixes
- fixes inconsistent idle related states
v7..v8: https://lore.kernel.org/r/[email protected]
- Address review feedback
- Move marking timer base idle into tick_nohz_stop_tick()
- Look ahead function to determine possible sleep lenght
v6..v7:
- Address review feedback of Frederic and bigeasy
- Change lock, unlock fetch next timer interrupt logic after remote expiry
- Move timer_expire_remote() into tick-internal.h
- Add documentation section about "Required event and timerqueue update
after remote expiry"
- Fix fallout of kernel test robot
v5..v6:
- Address review of Frederic Weisbecker and Peter Zijlstra (spelling,
locking, race in tmigr_handle_remote_cpu())
- unconditionally set TIMER_PINNED flag in add_timer_on(); introduce
add_timer() variants which set/unset TIMER_PINNED flag; drop fixing
add_timer_on() call sites, as TIMER_PINNED flag is set implicitly;
Fixing workqueue to use add_timer_global() instead of simply
add_timer() for unbound work.
- Drop support for siblings to end up in the same level 0 group (could be
added again in a better way as an improvement later on)
- Do not send IPI for new first deferrable timers
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/[email protected]/
- Minimize usage of locks by storing data using atomic_cmpxchg() for
migrator information and information about active cpus.
Thanks,
Anna-Maria
Anna-Maria Behnsen (18):
timers: Restructure get_next_timer_interrupt()
timers: Split out get next timer interrupt
timers: Move marking timer bases idle into tick_nohz_stop_tick()
timers: Optimization for timer_base_try_to_set_idle()
timers: Introduce add_timer() variants which modify timer flags
workqueue: Use global variant for add_timer()
timers: add_timer_on(): Make sure TIMER_PINNED flag is set
timers: Ease code in run_local_timers()
timers: Split next timer interrupt logic
timers: Keep the pinned timers separate from the others
timers: Retrieve next expiry of pinned/non-pinned timers separately
timers: Split out "get next timer interrupt" functionality
timers: Add get next timer interrupt functionality for remote CPUs
timers: Check if timers base is handled already
timers: Introduce function to check timer base is_idle flag
timers: Implement the hierarchical pull model
timer_migration: Add tracepoints
timers: Always queue timers on the local CPU
Richard Cochran (linutronix GmbH) (2):
timers: Restructure internal locking
tick/sched: Split out jiffies update helper function
MAINTAINERS | 1 +
include/linux/cpuhotplug.h | 1 +
include/linux/timer.h | 16 +-
include/trace/events/timer_migration.h | 297 +++++
kernel/time/Makefile | 3 +
kernel/time/tick-internal.h | 14 +
kernel/time/tick-sched.c | 65 +-
kernel/time/timer.c | 505 +++++--
kernel/time/timer_migration.c | 1693 ++++++++++++++++++++++++
kernel/time/timer_migration.h | 147 ++
kernel/workqueue.c | 2 +-
11 files changed, 2629 insertions(+), 115 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.39.2
tick_nohz_stop_tick()
The timer base is marked idle when get_next_timer_interrupt() is
executed. But the decision whether the tick will be stopped and whether the
system is able to go idle is done later. When the timer bases is marked
idle and a new first timer is enqueued remote an IPI is raised. Even if it
is not required because the tick is not stopped and the timer base is
evaluated again at the next tick.
To prevent this, the timer base is marked idle in tick_nohz_stop_tick() and
get_next_timer_interrupt() is streamlined by only looking for the next
timer interrupt. All other work is postponed to
timer_base_try_to_set_idle() which is called by tick_nohz_stop_tick().
With this, tick_sched::tick_stopped and timer_base::is_idle is always in
sync. So there is no longer the need to execute timer_clear_idle() in
tick_nohz_idle_retain_tick(). This was required before, as
tick_nohz_next_event() set timer_base::is_idle even if the tick would not
be stopped. So timer_clear_idle() is only executed, when timer base is
idle. So the check whether timer base is idle, is now no longer required as
well.
While at it fix some nearby whitespace damage as well.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
kernel/time/tick-internal.h | 1 +
kernel/time/tick-sched.c | 47 +++++++++++++++++++++--------
kernel/time/timer.c | 60 ++++++++++++++++++++++++++-----------
3 files changed, 78 insertions(+), 30 deletions(-)
diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h
index 481b7ab65e2c..47df30b871e4 100644
--- a/kernel/time/tick-internal.h
+++ b/kernel/time/tick-internal.h
@@ -163,6 +163,7 @@ 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);
+u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle);
void timer_clear_idle(void);
#define CLOCK_SET_WALL \
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index a17d26002831..c6223afc801f 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -849,11 +849,6 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
*/
delta = next_tick - basemono;
if (delta <= (u64)TICK_NSEC) {
- /*
- * Tell the timer code that the base is not idle, i.e. undo
- * the effect of get_next_timer_interrupt():
- */
- timer_clear_idle();
/*
* We've not stopped the tick yet, and there's a timer in the
* next period, so no point in stopping it either, bail.
@@ -889,12 +884,41 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
{
struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
+ unsigned long basejiff = ts->last_jiffies;
u64 basemono = ts->timer_expires_base;
- u64 expires = ts->timer_expires;
+ bool timer_idle;
+ u64 expires;
/* Make sure we won't be trying to stop it twice in a row. */
ts->timer_expires_base = 0;
+ /*
+ * Now the tick should be stopped definitely - so the timer base needs
+ * to be marked idle as well to not miss a newly queued timer.
+ */
+ expires = timer_base_try_to_set_idle(basejiff, basemono, &timer_idle);
+ if (!timer_idle) {
+ /*
+ * Do not clear tick_stopped here when it was already set - it
+ * will be retained on the next idle iteration when the tick
+ * expired earlier than expected.
+ */
+ expires = basemono + TICK_NSEC;
+ } else if (expires > ts->timer_expires) {
+ /*
+ * This path could only happen when the first timer was removed
+ * between calculating the possible sleep length and now (when
+ * high resolution mode is not active, timer could also be a
+ * hrtimer).
+ *
+ * We have to stick to the original calculated expiry value to
+ * not stop the tick for too long with a shallow C-state (which
+ * was programmed by cpuidle because of an early next expiration
+ * value).
+ */
+ expires = ts->timer_expires;
+ }
+
/*
* If this CPU is the one which updates jiffies, then give up
* the assignment and let it be taken by the CPU which runs
@@ -930,6 +954,10 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
* scheduler tick in tick_nohz_restart_sched_tick().
*/
if (!ts->tick_stopped) {
+ /* If the timer base is not idle, retain the tick. */
+ if (!timer_idle)
+ return;
+
calc_load_nohz_start();
quiet_vmstat();
@@ -991,7 +1019,7 @@ static void tick_nohz_restart_sched_tick(struct tick_sched *ts, ktime_t now)
touch_softlockup_watchdog_sched();
/* Cancel the scheduled timer and restore the tick: */
- ts->tick_stopped = 0;
+ ts->tick_stopped = 0;
tick_nohz_restart(ts, now);
}
@@ -1147,11 +1175,6 @@ void tick_nohz_idle_stop_tick(void)
void tick_nohz_idle_retain_tick(void)
{
tick_nohz_retain_tick(this_cpu_ptr(&tick_cpu_sched));
- /*
- * Undo the effect of get_next_timer_interrupt() called from
- * tick_nohz_next_event().
- */
- timer_clear_idle();
}
/**
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 2aea55d53416..3a668060692e 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1911,19 +1911,22 @@ static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
return DIV_ROUND_UP_ULL(nextevt, TICK_NSEC) * TICK_NSEC;
}
-static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem)
+static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
+ bool *idle)
{
struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
unsigned long nextevt = basej + NEXT_TIMER_MAX_DELTA;
u64 expires = KTIME_MAX;
- bool was_idle;
/*
* 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()))
+ if (cpu_is_offline(smp_processor_id())) {
+ if (idle)
+ *idle = true;
return expires;
+ }
raw_spin_lock(&base->lock);
if (base->next_expiry_recalc)
@@ -1953,17 +1956,26 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem)
__forward_timer_base(base, basej);
/*
- * Base is idle if the next event is more than a tick away.
- *
- * If the base is marked idle then any timer add operation 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).
+ * Set base->is_idle only when caller is timer_base_try_to_set_idle()
*/
- was_idle = base->is_idle;
- base->is_idle = time_after(nextevt, basej + 1);
- if (was_idle != base->is_idle)
- trace_timer_base_idle(base->is_idle, base->cpu);
+ if (idle) {
+ /*
+ * Base is idle if the next event is more than a tick away.
+ *
+ * If the base is marked idle then any timer add operation 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 (!base->is_idle) {
+ if (time_after(nextevt, basej + 1)) {
+ base->is_idle = true;
+ trace_timer_base_idle(true, base->cpu);
+ }
+ }
+ *idle = base->is_idle;
+ }
raw_spin_unlock(&base->lock);
@@ -1980,7 +1992,21 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem)
*/
u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
{
- return __get_next_timer_interrupt(basej, basem);
+ return __get_next_timer_interrupt(basej, basem, NULL);
+}
+
+/**
+ * timer_base_try_to_set_idle() - Try to set the idle state of the timer bases
+ * @basej: base time jiffies
+ * @basem: base time clock monotonic
+ * @idle: pointer to store the value of timer_base->is_idle
+ *
+ * Returns the tick aligned clock monotonic time of the next pending
+ * timer or KTIME_MAX if no timer is pending.
+ */
+u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle)
+{
+ return __get_next_timer_interrupt(basej, basem, idle);
}
/**
@@ -1998,10 +2024,8 @@ void timer_clear_idle(void)
* sending the IPI a few instructions smaller for the cost of taking
* the lock in the exit from idle path.
*/
- if (base->is_idle) {
- base->is_idle = false;
- trace_timer_base_idle(false, smp_processor_id());
- }
+ base->is_idle = false;
+ trace_timer_base_idle(false, smp_processor_id());
}
#endif
--
2.39.2
When tick is stopped also the timer base is_idle flag is set. When
reentering the timer_base_try_to_set_idle() with the tick stopped, there is
no need to check whether the timer base needs to be set idle again. When a
timer was enqueued in the meantime, this is already handled by the
tick_nohz_next_event() call which was executed before
tick_nohz_stop_tick().
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
kernel/time/tick-sched.c | 2 +-
kernel/time/timer.c | 11 ++++++++---
2 files changed, 9 insertions(+), 4 deletions(-)
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index c6223afc801f..27f1a2ae7f39 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -886,7 +886,7 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
unsigned long basejiff = ts->last_jiffies;
u64 basemono = ts->timer_expires_base;
- bool timer_idle;
+ bool timer_idle = ts->tick_stopped;
u64 expires;
/* Make sure we won't be trying to stop it twice in a row. */
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 3a668060692e..2f69a485a070 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1999,13 +1999,18 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
* timer_base_try_to_set_idle() - Try to set the idle state of the timer bases
* @basej: base time jiffies
* @basem: base time clock monotonic
- * @idle: pointer to store the value of timer_base->is_idle
+ * @idle: pointer to store the value of timer_base->is_idle on return;
+ * *idle contains the information whether tick was already stopped
*
- * 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. When tick was already stopped KTIME_MAX is
+ * returned as well.
*/
u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle)
{
+ if (*idle)
+ return KTIME_MAX;
+
return __get_next_timer_interrupt(basej, basem, idle);
}
--
2.39.2
The implementation of the NOHZ pull at expiry model will change the timer
bases per CPU. Timers, that have to expire on a specific CPU, require the
TIMER_PINNED flag. If the CPU doesn't matter, the TIMER_PINNED flag must be
dropped. This is required for call sites which use the timer alternately as
pinned and not pinned timer like workqueues do.
Therefore use add_timer_global() to make sure TIMER_PINNED flag is dropped.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Acked-by: Tejun Heo <[email protected]>
Cc: Tejun Heo <[email protected]>
Cc: Lai Jiangshan <[email protected]>
---
v6:
- New patch: As v6 provides unconditially setting TIMER_PINNED flag in
add_timer_on() workqueue requires new add_timer_global() variant.
---
kernel/workqueue.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 2989b57e154a..31a6b0831318 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -1955,7 +1955,7 @@ static void __queue_delayed_work(int cpu, struct workqueue_struct *wq,
if (unlikely(cpu != WORK_CPU_UNBOUND))
add_timer_on(timer, cpu);
else
- add_timer(timer);
+ add_timer_global(timer);
}
/**
--
2.39.2
timer flags
A timer might be used as a pinned timer (using add_timer_on()) and later on
as non-pinned timer using add_timer(). When the "NOHZ timer pull at expiry
model" is in place, the TIMER_PINNED flag is required to be used whenever a
timer needs to expire on a dedicated CPU. Otherwise the flag must not be
set if expiration on a dedicated CPU is not required.
add_timer_on()'s behavior will be changed during the preparation patches
for the "NOHZ timer pull at expiry model" to unconditionally set
TIMER_PINNED flag. To be able to clear/ set the flag when queueing a
timer, two variants of add_timer() are introduced.
This is a preparatory patch and has no functional change.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
v10: Commit message reworded as suggested by bigeasy
v9: Update documentation to match kernel-doc style (missing brackets after
function names)
New in v6
---
include/linux/timer.h | 2 ++
kernel/time/timer.c | 34 ++++++++++++++++++++++++++++++++++
2 files changed, 36 insertions(+)
diff --git a/include/linux/timer.h b/include/linux/timer.h
index 26a545bb0153..404bb31a95c7 100644
--- a/include/linux/timer.h
+++ b/include/linux/timer.h
@@ -179,6 +179,8 @@ extern int timer_reduce(struct timer_list *timer, unsigned long expires);
#define NEXT_TIMER_MAX_DELTA ((1UL << 30) - 1)
extern void add_timer(struct timer_list *timer);
+extern void add_timer_local(struct timer_list *timer);
+extern void add_timer_global(struct timer_list *timer);
extern int try_to_del_timer_sync(struct timer_list *timer);
extern int timer_delete_sync(struct timer_list *timer);
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 2f69a485a070..3cf016d6fa59 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1245,6 +1245,40 @@ void add_timer(struct timer_list *timer)
}
EXPORT_SYMBOL(add_timer);
+/**
+ * add_timer_local() - Start a timer on the local CPU
+ * @timer: The timer to be started
+ *
+ * Same as add_timer() except that the timer flag TIMER_PINNED is set.
+ *
+ * See add_timer() for further details.
+ */
+void add_timer_local(struct timer_list *timer)
+{
+ if (WARN_ON_ONCE(timer_pending(timer)))
+ return;
+ timer->flags |= TIMER_PINNED;
+ __mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
+}
+EXPORT_SYMBOL(add_timer_local);
+
+/**
+ * add_timer_global() - Start a timer without TIMER_PINNED flag set
+ * @timer: The timer to be started
+ *
+ * Same as add_timer() except that the timer flag TIMER_PINNED is unset.
+ *
+ * See add_timer() for further details.
+ */
+void add_timer_global(struct timer_list *timer)
+{
+ if (WARN_ON_ONCE(timer_pending(timer)))
+ return;
+ timer->flags &= ~TIMER_PINNED;
+ __mod_timer(timer, timer->expires, MOD_TIMER_NOTPENDING);
+}
+EXPORT_SYMBOL(add_timer_global);
+
/**
* add_timer_on - Start a timer on a particular CPU
* @timer: The timer to be started
--
2.39.2
set
When adding a timer to the timer wheel using add_timer_on(), it is an
implicitly pinned timer. With the timer pull at expiry time model in place,
TIMER_PINNED flag is required to make sure timers end up in proper base.
Add TIMER_PINNED flag unconditionally when add_timer_on() is executed.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
---
kernel/time/timer.c | 8 +++++++-
1 file changed, 7 insertions(+), 1 deletion(-)
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 3cf016d6fa59..fc4c406c9ec7 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1284,7 +1284,10 @@ EXPORT_SYMBOL(add_timer_global);
* @timer: The timer to be started
* @cpu: The CPU to start it on
*
- * Same as add_timer() except that it starts the timer on the given CPU.
+ * Same as add_timer() except that it starts the timer on the given CPU and
+ * the TIMER_PINNED flag is set. When timer shouldn't be a pinned timer in
+ * the next round, add_timer_global() should be used instead as it unsets
+ * the TIMER_PINNED flag.
*
* See add_timer() for further details.
*/
@@ -1298,6 +1301,9 @@ void add_timer_on(struct timer_list *timer, int cpu)
if (WARN_ON_ONCE(timer_pending(timer)))
return;
+ /* Make sure timer flags have TIMER_PINNED flag set */
+ timer->flags |= TIMER_PINNED;
+
new_base = get_timer_cpu_base(timer->flags, cpu);
/*
--
2.39.2
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 <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
---
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 fc4c406c9ec7..793848167852 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -2135,16 +2135,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.39.2
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.
Originally-by: Richard Cochran (linutronix GmbH) <[email protected]>
Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
---
v10:
- Simplify local_first check in __get_next_timer_interrupt() due to
updated next_expiry values of empty timer bases
v9:
- Update was required (change of preceding patches)
v6:
- Drop set TIMER_PINNED flag in add_timer_on() and drop related
warning. add_timer_on() fix is splitted into a separate
patch. Therefore also drop "Reviewed-by" of Frederic Weisbecker
v5:
- Add WARN_ONCE() in add_timer_on()
- Decrease patch size by splitting into three patches (this patch and the
two before)
v4:
- split out logic to forward base clock into a helper function
forward_base_clk() (Frederic)
- ease the code in run_local_timers() and timer_clear_idle() (Frederic)
---
kernel/time/timer.c | 85 +++++++++++++++++++++++++++++----------------
1 file changed, 56 insertions(+), 29 deletions(-)
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 4d6cf49a2fd1..5ca831444954 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
@@ -899,7 +905,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
@@ -912,7 +921,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
@@ -1961,6 +1973,9 @@ static unsigned long next_timer_interrupt(struct timer_base *base,
* Move next_expiry for the empty base into the future to prevent an
* unnecessary raise of the timer softirq when the next_expiry value
* will be reached even if there is no timer pending.
+ *
+ * This update is also required to make timer_base::next_expiry values
+ * easy comparable to find out which base holds the first pending timer.
*/
if (!base->timers_pending)
base->next_expiry = basej + NEXT_TIMER_MAX_DELTA;
@@ -1971,9 +1986,10 @@ static unsigned long next_timer_interrupt(struct timer_base *base,
static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
bool *idle)
{
- 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;
u64 expires = KTIME_MAX;
- unsigned long nextevt;
+ bool local_first;
/*
* Pretend that there is no timer pending if the cpu is offline.
@@ -1985,10 +2001,20 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
return expires;
}
- raw_spin_lock(&base->lock);
- nextevt = next_timer_interrupt(base, basej);
+ base_local = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
+ base_global = this_cpu_ptr(&timer_bases[BASE_GLOBAL]);
- if (base->timers_pending) {
+ raw_spin_lock(&base_local->lock);
+ raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
+
+ nextevt_local = next_timer_interrupt(base_local, basej);
+ nextevt_global = next_timer_interrupt(base_global, basej);
+
+ local_first = time_before_eq(nextevt_local, nextevt_global);
+
+ nextevt = local_first ? nextevt_local : nextevt_global;
+
+ 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;
@@ -1999,31 +2025,31 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
* We have a fresh next event. Check whether we can forward the
* base.
*/
- __forward_timer_base(base, basej);
+ __forward_timer_base(base_local, basej);
+ __forward_timer_base(base_global, basej);
/*
* Set base->is_idle only when caller is timer_base_try_to_set_idle()
*/
if (idle) {
/*
- * Base is idle if the next event is more than a tick away.
+ * Bases are idle if the next event is more than a tick away.
*
* If the base is marked idle then any timer add operation 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).
+ * idle logic is only maintained for the BASE_LOCAL and
+ * BASE_GLOBAL base, deferrable timers may still see large
+ * granularity skew (by design).
*/
- if (!base->is_idle) {
- if (time_after(nextevt, basej + 1)) {
- base->is_idle = true;
- trace_timer_base_idle(true, base->cpu);
- }
+ if (!base_local->is_idle && time_after(nextevt, basej + 1)) {
+ base_local->is_idle = base_global->is_idle = true;
+ trace_timer_base_idle(true, base_local->cpu);
}
- *idle = base->is_idle;
+ *idle = base_local->is_idle;
}
- raw_spin_unlock(&base->lock);
+ raw_spin_unlock(&base_global->lock);
+ raw_spin_unlock(&base_local->lock);
return cmp_next_hrtimer_event(basem, expires);
}
@@ -2067,15 +2093,14 @@ u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle)
*/
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);
trace_timer_base_idle(false, smp_processor_id());
}
#endif
@@ -2126,11 +2151,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]));
+ }
}
/*
@@ -2138,7 +2165,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.39.2
Split the logic for getting next timer interrupt (no matter of recalculated
or already stored in base->next_expiry) into a separate function named
next_timer_interrupt(). Make it available to local call sites only.
No functional change.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
v10: Reword commit message
v9: Adapt to the fix for empty timer bases.
---
kernel/time/timer.c | 32 +++++++++++++++++++-------------
1 file changed, 19 insertions(+), 13 deletions(-)
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 793848167852..4d6cf49a2fd1 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1951,12 +1951,29 @@ 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,
+ unsigned long basej)
+{
+ if (base->next_expiry_recalc)
+ next_expiry_recalc(base);
+
+ /*
+ * Move next_expiry for the empty base into the future to prevent an
+ * unnecessary raise of the timer softirq when the next_expiry value
+ * will be reached even if there is no timer pending.
+ */
+ if (!base->timers_pending)
+ base->next_expiry = basej + NEXT_TIMER_MAX_DELTA;
+
+ return base->next_expiry;
+}
+
static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
bool *idle)
{
struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
- unsigned long nextevt = basej + NEXT_TIMER_MAX_DELTA;
u64 expires = KTIME_MAX;
+ unsigned long nextevt;
/*
* Pretend that there is no timer pending if the cpu is offline.
@@ -1969,24 +1986,13 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
}
raw_spin_lock(&base->lock);
- if (base->next_expiry_recalc)
- next_expiry_recalc(base);
+ nextevt = next_timer_interrupt(base, basej);
if (base->timers_pending) {
- nextevt = base->next_expiry;
-
/* If we missed a tick already, force 0 delta */
if (time_before(nextevt, basej))
nextevt = basej;
expires = basem + (u64)(nextevt - basej) * TICK_NSEC;
- } else {
- /*
- * Move next_expiry for the empty base into the future to
- * prevent a unnecessary raise of the timer softirq when the
- * next_expiry value will be reached even if there is no timer
- * pending.
- */
- base->next_expiry = nextevt;
}
/*
--
2.39.2
timers separately
For the conversion of the NOHZ timer placement to a pull at expiry time
model it's required to have separate 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) <[email protected]>
Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
---
v10: Fix no functional change message
v9: Update was required (change of preceding patches)
---
kernel/time/timer.c | 35 +++++++++++++++++++++++++++++++----
1 file changed, 31 insertions(+), 4 deletions(-)
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 5ca831444954..f119b44e44e0 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);
@@ -1986,10 +1991,11 @@ static unsigned long next_timer_interrupt(struct timer_base *base,
static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
bool *idle)
{
+ struct timer_events tevt = { .local = KTIME_MAX, .global = KTIME_MAX };
unsigned long nextevt, nextevt_local, nextevt_global;
struct timer_base *base_local, *base_global;
- u64 expires = KTIME_MAX;
bool local_first;
+ u64 expires;
/*
* Pretend that there is no timer pending if the cpu is offline.
@@ -1998,7 +2004,7 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
if (cpu_is_offline(smp_processor_id())) {
if (idle)
*idle = true;
- return expires;
+ return tevt.local;
}
base_local = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
@@ -2014,13 +2020,32 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
nextevt = local_first ? nextevt_local : nextevt_global;
- if (base_local->timers_pending || base_global->timers_pending) {
+ /*
+ * If the @nextevt is at max. one tick away, use @nextevt and store
+ * it in the local expiry value. The next global event is irrelevant in
+ * this case and can be left as KTIME_MAX.
+ */
+ if (time_before_eq(nextevt, basej + 1)) {
/* 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 forward;
}
+ /*
+ * 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;
+
+forward:
/*
* We have a fresh next event. Check whether we can forward the
* base.
@@ -2051,6 +2076,8 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
raw_spin_unlock(&base_global->lock);
raw_spin_unlock(&base_local->lock);
+ expires = min_t(u64, tevt.local, tevt.global);
+
return cmp_next_hrtimer_event(basem, expires);
}
--
2.39.2
functionality
The functionality for getting the next timer interrupt in
get_next_timer_interrupt() is split into a separate function
fetch_next_timer_interrupt() to be usable by other call sites.
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 <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
---
v10: Update was required (change of preceding patches)
v9: Update was required (change of preceding patches)
v6: s/splitted/split
v5: Update commit message
v4: Fix typo in comment
---
kernel/time/timer.c | 64 +++++++++++++++++++++++++++------------------
1 file changed, 38 insertions(+), 26 deletions(-)
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index f119b44e44e0..9fa759dd80f5 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1988,30 +1988,13 @@ static unsigned long next_timer_interrupt(struct timer_base *base,
return base->next_expiry;
}
-static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
- bool *idle)
+static unsigned long fetch_next_timer_interrupt(unsigned long basej, u64 basem,
+ struct timer_base *base_local,
+ struct timer_base *base_global,
+ struct timer_events *tevt)
{
- 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;
- u64 expires;
-
- /*
- * 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())) {
- if (idle)
- *idle = true;
- return tevt.local;
- }
-
- base_local = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
- base_global = this_cpu_ptr(&timer_bases[BASE_GLOBAL]);
-
- raw_spin_lock(&base_local->lock);
- raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
nextevt_local = next_timer_interrupt(base_local, basej);
nextevt_global = next_timer_interrupt(base_global, basej);
@@ -2029,8 +2012,8 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
/* If we missed a tick already, force 0 delta */
if (time_before(nextevt, basej))
nextevt = basej;
- tevt.local = basem + (u64)(nextevt - basej) * TICK_NSEC;
- goto forward;
+ tevt->local = basem + (u64)(nextevt - basej) * TICK_NSEC;
+ return nextevt;
}
/*
@@ -2040,12 +2023,41 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
* 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;
+ tevt->global = basem + (u64)(nextevt_global - basej) * TICK_NSEC;
if (base_local->timers_pending)
- tevt.local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
+ tevt->local = basem + (u64)(nextevt_local - basej) * TICK_NSEC;
+
+ return nextevt;
+}
+
+static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
+ bool *idle)
+{
+ struct timer_events tevt = { .local = KTIME_MAX, .global = KTIME_MAX };
+ struct timer_base *base_local, *base_global;
+ unsigned long nextevt;
+ u64 expires;
+
+ /*
+ * 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())) {
+ if (idle)
+ *idle = true;
+ return tevt.local;
+ }
+
+ base_local = this_cpu_ptr(&timer_bases[BASE_LOCAL]);
+ base_global = this_cpu_ptr(&timer_bases[BASE_GLOBAL]);
+
+ raw_spin_lock(&base_local->lock);
+ raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
+
+ nextevt = fetch_next_timer_interrupt(basej, basem, base_local,
+ base_global, &tevt);
-forward:
/*
* We have a fresh next event. Check whether we can forward the
* base.
--
2.39.2
From: "Richard Cochran (linutronix GmbH)" <[email protected]>
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) <[email protected]>
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
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 3e2adfc15f3a..ccb2a5c03b87 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -2223,11 +2223,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)) {
@@ -2251,21 +2247,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.39.2
remote CPUs
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.
Locking of the timer bases and getting the information for the next timer
interrupt functionality is split into separate functions. This is required
to be compliant with lock ordering when the new model is in place.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
---
v10:
- sparse annotations for locks
v8:
- Update comment
v7:
- Move functions into CONFIG_SMP && CONFIG_NO_HZ_COMMON section
- change lock, fetch functions to be unconditional
- split out unlock function into a separate function
v6:
- introduce timer_lock_remote_bases() to fix race
---
kernel/time/tick-internal.h | 10 +++++
kernel/time/timer.c | 80 ++++++++++++++++++++++++++++++++++---
2 files changed, 85 insertions(+), 5 deletions(-)
diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h
index 47df30b871e4..8b0c28edbd09 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
@@ -154,6 +159,11 @@ extern unsigned long tick_nohz_active;
extern void timers_update_nohz(void);
# ifdef CONFIG_SMP
extern struct static_key_false timers_migration_enabled;
+extern void fetch_next_timer_interrupt_remote(unsigned long basej, u64 basem,
+ struct timer_events *tevt,
+ unsigned int cpu);
+extern void timer_lock_remote_bases(unsigned int cpu);
+extern void timer_unlock_remote_bases(unsigned int cpu);
# endif
#else /* CONFIG_NO_HZ_COMMON */
static inline void timers_update_nohz(void) { }
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 9fa759dd80f5..3e2adfc15f3a 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);
@@ -2031,6 +2026,81 @@ static unsigned long fetch_next_timer_interrupt(unsigned long basej, u64 basem,
return nextevt;
}
+# ifdef CONFIG_SMP
+/**
+ * fetch_next_timer_interrupt_remote() - Store next timers into @tevt
+ * @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.
+ *
+ * Caller needs to make sure timer base locks are held (use
+ * timer_lock_remote_bases() for this purpose).
+ */
+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;
+
+ /* Preset local / global events */
+ tevt->local = tevt->global = KTIME_MAX;
+
+ base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
+ base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
+
+ lockdep_assert_held(&base_local->lock);
+ lockdep_assert_held(&base_global->lock);
+
+ fetch_next_timer_interrupt(basej, basem, base_local, base_global, tevt);
+}
+
+/**
+ * timer_unlock_remote_bases - unlock timer bases of cpu
+ * @cpu: Remote CPU
+ *
+ * Unlocks the remote timer bases.
+ */
+void timer_unlock_remote_bases(unsigned int cpu)
+ __releases(timer_bases[BASE_LOCAL]->lock)
+ __releases(timer_bases[BASE_GLOBAL]->lock)
+{
+ struct timer_base *base_local, *base_global;
+
+ base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
+ base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
+
+ raw_spin_unlock(&base_global->lock);
+ raw_spin_unlock(&base_local->lock);
+}
+
+/**
+ * timer_lock_remote_bases - lock timer bases of cpu
+ * @cpu: Remote CPU
+ *
+ * Locks the remote timer bases.
+ */
+void timer_lock_remote_bases(unsigned int cpu)
+ __acquires(timer_bases[BASE_LOCAL]->lock)
+ __acquires(timer_bases[BASE_GLOBAL]->lock)
+{
+ struct timer_base *base_local, *base_global;
+
+ base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
+ base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
+
+ lockdep_assert_irqs_disabled();
+
+ raw_spin_lock(&base_local->lock);
+ raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
+}
+# endif /* CONFIG_SMP */
+
static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
bool *idle)
{
--
2.39.2
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 <[email protected]>
---
v10: s/cpu/CPU/ in commit message
v6: Drop double negation
---
kernel/time/timer.c | 3 +++
1 file changed, 3 insertions(+)
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index ccb2a5c03b87..eb99297a96fe 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -2225,6 +2225,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.39.2
From: "Richard Cochran (linutronix GmbH)" <[email protected]>
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 function in anticipation of the new caller.
No functional change.
Signed-off-by: Richard Cochran (linutronix GmbH) <[email protected]>
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
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 8b0c28edbd09..ccf39befde85 100644
--- a/kernel/time/tick-internal.h
+++ b/kernel/time/tick-internal.h
@@ -157,6 +157,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;
extern void fetch_next_timer_interrupt_remote(unsigned long basej, u64 basem,
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index 27f1a2ae7f39..a3eb5165d439 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -799,18 +799,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.39.2
flag
To prepare for the conversion of the NOHZ timer placement to a pull at
expiry time model it's required to have a function that returns the value
of the is_idle flag of the timer base to keep the hierarchy states during
online in sync with timer base state.
No functional change.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
v10: Fix fallout of 0day: Move function definition of timer_base_is_idle()
into SMP && NO_HZ_COMMON ifdef section
v9: new in v9
---
kernel/time/tick-internal.h | 1 +
kernel/time/timer.c | 10 ++++++++++
2 files changed, 11 insertions(+)
diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h
index ccf39befde85..7e3090109e33 100644
--- a/kernel/time/tick-internal.h
+++ b/kernel/time/tick-internal.h
@@ -165,6 +165,7 @@ extern void fetch_next_timer_interrupt_remote(unsigned long basej, u64 basem,
unsigned int cpu);
extern void timer_lock_remote_bases(unsigned int cpu);
extern void timer_unlock_remote_bases(unsigned int cpu);
+extern bool timer_base_is_idle(void);
# endif
#else /* CONFIG_NO_HZ_COMMON */
static inline void timers_update_nohz(void) { }
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index eb99297a96fe..3c49d8fdfd53 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -2099,6 +2099,16 @@ void timer_lock_remote_bases(unsigned int cpu)
raw_spin_lock(&base_local->lock);
raw_spin_lock_nested(&base_global->lock, SINGLE_DEPTH_NESTING);
}
+
+/**
+ * timer_base_is_idle() - Return whether timer base is set idle
+ *
+ * Returns value of local timer base is_idle value.
+ */
+bool timer_base_is_idle(void)
+{
+ return __this_cpu_read(timer_bases[BASE_LOCAL].is_idle);
+}
# endif /* CONFIG_SMP */
static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
--
2.39.2
The timer pull logic needs proper debugging aids. Add tracepoints so the
hierarchical idle machinery can be diagnosed.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
v10: Make an entry in MAINTAINERS file
v9: Add tmigr_cpu_new_timer_idle tracepoint
v8: Add wakeup value to tracepoints
---
---
MAINTAINERS | 1 +
include/trace/events/timer_migration.h | 297 +++++++++++++++++++++++++
kernel/time/timer_migration.c | 26 +++
3 files changed, 324 insertions(+)
create mode 100644 include/trace/events/timer_migration.h
diff --git a/MAINTAINERS b/MAINTAINERS
index a7c4cf8201e0..9f9f2a695082 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -17244,6 +17244,7 @@ T: git git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git timers/core
F: fs/timerfd.c
F: include/linux/time_namespace.h
F: include/linux/timer*
+F: include/trace/events/timer*
F: kernel/time/*timer*
F: kernel/time/namespace.c
diff --git a/include/trace/events/timer_migration.h b/include/trace/events/timer_migration.h
new file mode 100644
index 000000000000..a2e7e32058f8
--- /dev/null
+++ b/include/trace/events/timer_migration.h
@@ -0,0 +1,297 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+
+#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_children )
+ __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_children;
+ __entry->childmask = child->childmask;
+ ),
+
+ TP_printk("group=%p childmask=%0x parent=%p lvl=%d numa=%d num_children=%d",
+ __entry->child, __entry->childmask, __entry->parent,
+ __entry->lvl, __entry->numa_node, __entry->num_children)
+);
+
+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_children )
+ __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_children;
+ __entry->childmask = tmc->childmask;
+ ),
+
+ TP_printk("cpu=%d childmask=%0x parent=%p lvl=%d numa=%d num_children=%d",
+ __entry->cpu, __entry->childmask, __entry->parent,
+ __entry->lvl, __entry->numa_node, __entry->num_children)
+);
+
+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)
+ __field( u64, wakeup)
+ ),
+
+ TP_fast_assign(
+ __entry->cpu = tmc->cpuevt.cpu;
+ __entry->parent = tmc->tmgroup;
+ __entry->wakeup = tmc->wakeup;
+ ),
+
+ TP_printk("cpu=%d parent=%p wakeup=%llu", __entry->cpu, __entry->parent, __entry->wakeup)
+);
+
+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)
+);
+
+DECLARE_EVENT_CLASS(tmigr_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)
+ __field( u64, wakeup)
+ ),
+
+ TP_fast_assign(
+ __entry->cpu = tmc->cpuevt.cpu;
+ __entry->parent = tmc->tmgroup;
+ __entry->nextevt = nextevt;
+ __entry->wakeup = tmc->wakeup;
+ ),
+
+ TP_printk("cpu=%d parent=%p nextevt=%llu wakeup=%llu",
+ __entry->cpu, __entry->parent, __entry->nextevt, __entry->wakeup)
+);
+
+DEFINE_EVENT(tmigr_idle, tmigr_cpu_idle,
+
+ TP_PROTO(struct tmigr_cpu *tmc, u64 nextevt),
+
+ TP_ARGS(tmc, nextevt)
+);
+
+DEFINE_EVENT(tmigr_idle, tmigr_cpu_new_timer_idle,
+
+ TP_PROTO(struct tmigr_cpu *tmc, u64 nextevt),
+
+ TP_ARGS(tmc, 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 de1905b0bae7..d3b7200a9f4a 100644
--- a/kernel/time/timer_migration.c
+++ b/kernel/time/timer_migration.c
@@ -14,6 +14,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
@@ -537,6 +540,8 @@ static bool tmigr_active_up(struct tmigr_group *group,
*/
group->groupevt.ignore = true;
+ trace_tmigr_group_set_cpu_active(group, newstate, childmask);
+
return walk_done;
}
@@ -546,6 +551,8 @@ static void __tmigr_cpu_activate(struct tmigr_cpu *tmc)
data.childmask = tmc->childmask;
+ trace_tmigr_cpu_active(tmc);
+
tmc->cpuevt.ignore = true;
WRITE_ONCE(tmc->wakeup, KTIME_MAX);
tmc->wakeup_recalc = false;
@@ -703,6 +710,9 @@ bool tmigr_update_events(struct tmigr_group *group, struct tmigr_group *child,
data->firstexp = tmigr_next_groupevt_expires(group);
}
+ trace_tmigr_update_events(child, group, childstate, groupstate,
+ nextexp);
+
unlock:
raw_spin_unlock(&group->lock);
@@ -745,6 +755,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 = false;
data.remote = false;
@@ -787,6 +799,8 @@ static u64 tmigr_handle_remote_cpu(unsigned int cpu, u64 now,
return next;
}
+ trace_tmigr_handle_remote_cpu(tmc);
+
tmc->remote = true;
WRITE_ONCE(tmc->wakeup, KTIME_MAX);
@@ -872,6 +886,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
@@ -1140,6 +1155,7 @@ u64 tmigr_cpu_new_timer(u64 nextexp)
*/
WRITE_ONCE(tmc->wakeup, ret);
+ trace_tmigr_cpu_new_timer_idle(tmc, nextexp);
raw_spin_unlock(&tmc->lock);
return ret;
}
@@ -1243,6 +1259,8 @@ static bool tmigr_inactive_up(struct tmigr_group *group,
}
}
+ trace_tmigr_group_set_cpu_inactive(group, newstate, childmask);
+
return walk_done;
}
@@ -1295,6 +1313,7 @@ u64 tmigr_cpu_deactivate(u64 nextexp)
*/
WRITE_ONCE(tmc->wakeup, ret);
+ trace_tmigr_cpu_idle(tmc, nextexp);
raw_spin_unlock(&tmc->lock);
return ret;
}
@@ -1407,6 +1426,7 @@ static struct tmigr_group *tmigr_get_group(unsigned int cpu, int node,
/* Setup successful. Add it to the hierarchy */
list_add(&group->list, &tmigr_level_list[lvl]);
+ trace_tmigr_group_set(group);
return group;
}
@@ -1424,6 +1444,8 @@ static void tmigr_connect_child_parent(struct tmigr_group *child,
raw_spin_unlock(&parent->lock);
raw_spin_unlock_irq(&child->lock);
+ trace_tmigr_connect_child_parent(child);
+
/*
* To prevent inconsistent states, active children need to be active in
* the new parent as well. Inactive children are already marked inactive
@@ -1504,6 +1526,8 @@ static int tmigr_setup_groups(unsigned int cpu, unsigned int node)
raw_spin_unlock_irq(&group->lock);
+ trace_tmigr_connect_cpu_parent(tmc);
+
/* There are no children that need to be connected */
continue;
} else {
@@ -1571,6 +1595,7 @@ static int tmigr_cpu_online(unsigned int cpu)
WRITE_ONCE(tmc->wakeup, KTIME_MAX);
}
raw_spin_lock_irq(&tmc->lock);
+ trace_tmigr_cpu_online(tmc);
tmc->idle = timer_base_is_idle();
if (!tmc->idle)
__tmigr_cpu_activate(tmc);
@@ -1592,6 +1617,7 @@ static int tmigr_cpu_offline(unsigned int cpu)
* offline; Therefore nextevt value is set to KTIME_MAX
*/
__tmigr_cpu_deactivate(tmc, KTIME_MAX);
+ trace_tmigr_cpu_offline(tmc);
raw_spin_unlock_irq(&tmc->lock);
return 0;
--
2.39.2
The timer pull model is in place so we can remove the heuristics which try
to guess the best target CPU at enqueue/modification time.
All non pinned timers are queued on the local CPU in the separate storage
and eventually pulled at expiry time to a remote CPU.
Originally-by: Richard Cochran (linutronix GmbH) <[email protected]>
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
v9:
- Update to the changes of the preceding patches
v6:
- Update TIMER_PINNED flag description.
v5:
- Move WARN_ONCE() in add_timer_on() into a previous patch
- Fold crystallball magic related hunks into this patch
v4: Update comment about TIMER_PINNED flag (heristic is removed)
---
include/linux/timer.h | 14 ++++----------
kernel/time/timer.c | 34 +++++++++++++---------------------
2 files changed, 17 insertions(+), 31 deletions(-)
diff --git a/include/linux/timer.h b/include/linux/timer.h
index 404bb31a95c7..4dd59e4e5681 100644
--- a/include/linux/timer.h
+++ b/include/linux/timer.h
@@ -50,16 +50,10 @@ 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.
- *
- * Note: Because enqueuing of timers can migrate the timer from one
- * CPU to another, pinned timers are not guaranteed to stay on the
- * initialy selected CPU. They move to the CPU on which the enqueue
- * function is invoked via mod_timer() or add_timer(). If the timer
- * should be placed on a particular CPU, then add_timer_on() has to be
- * used.
+ * @TIMER_PINNED: A pinned timer will always expire on the CPU on which the
+ * timer was enqueued. When a particular CPU is required, add_timer_on()
+ * has to be used. Enqueue via mod_timer() and add_timer() is always done
+ * on the local CPU.
*/
#define TIMER_CPUMASK 0x0003FFFF
#define TIMER_MIGRATING 0x00040000
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index a52f68be8dfd..8d53718af21d 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -590,10 +590,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);
}
@@ -941,17 +944,6 @@ static inline struct timer_base *get_timer_base(u32 tflags)
return get_timer_cpu_base(tflags, tflags & TIMER_CPUMASK);
}
-static inline struct timer_base *
-get_target_base(struct timer_base *base, unsigned tflags)
-{
-#if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON)
- if (static_branch_likely(&timers_migration_enabled) &&
- !(tflags & TIMER_PINNED))
- return get_timer_cpu_base(tflags, get_nohz_timer_target());
-#endif
- return get_timer_this_cpu_base(tflags);
-}
-
static inline void __forward_timer_base(struct timer_base *base,
unsigned long basej)
{
@@ -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) {
/*
@@ -2237,7 +2229,7 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
* granularity skew (by design).
*/
if (!base_local->is_idle && time_after(nextevt, basej + 1)) {
- base_local->is_idle = base_global->is_idle = true;
+ base_local->is_idle = true;
trace_timer_base_idle(true, base_local->cpu);
}
*idle = base_local->is_idle;
@@ -2303,13 +2295,13 @@ u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle)
void timer_clear_idle(void)
{
/*
- * We do this unlocked. The worst outcome is a remote enqueue sending
- * a pointless IPI, but taking the lock would just make the window for
- * sending the IPI a few instructions smaller for the cost of taking
- * the lock in the exit from idle path.
+ * We do this unlocked. The worst outcome is a remote pinned timer
+ * enqueue sending a pointless IPI, but taking the lock would just
+ * make the window for sending the IPI a few instructions smaller
+ * for the cost of taking the lock in the exit from idle
+ * path. Required for BASE_LOCAL only.
*/
__this_cpu_write(timer_bases[BASE_LOCAL].is_idle, false);
- __this_cpu_write(timer_bases[BASE_GLOBAL].is_idle, false);
trace_timer_base_idle(false, smp_processor_id());
/* Activate without holding the timer_base->lock */
--
2.39.2
Le Mon, Jan 15, 2024 at 03:37:26PM +0100, Anna-Maria Behnsen a ?crit :
> @@ -889,12 +884,41 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
> static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> {
> struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
> + unsigned long basejiff = ts->last_jiffies;
> u64 basemono = ts->timer_expires_base;
> - u64 expires = ts->timer_expires;
> + bool timer_idle;
> + u64 expires;
>
> /* Make sure we won't be trying to stop it twice in a row. */
> ts->timer_expires_base = 0;
>
> + /*
> + * Now the tick should be stopped definitely - so the timer base needs
> + * to be marked idle as well to not miss a newly queued timer.
> + */
> + expires = timer_base_try_to_set_idle(basejiff, basemono, &timer_idle);
> + if (!timer_idle) {
> + /*
> + * Do not clear tick_stopped here when it was already set - it
Can that really happen? Looking at __get_next_timer_interrupt(), you're making a
behavioural change: if base->is_idle was previously set and the next timer is
now below/equal a jiffy, base->is_idle is not going to be cleared by
__get_next_timer_interrupt().
Therefore you shouldn't observe ts->tick_stopped && !timer_idle
But I'm assuming that behavioural change wasn't intended?
> + * will be retained on the next idle iteration when the tick
> + * expired earlier than expected.
I'm a bit confused by this sentence.
> + */
> + expires = basemono + TICK_NSEC;
Do you need this line?
> @@ -1147,11 +1175,6 @@ void tick_nohz_idle_stop_tick(void)
> void tick_nohz_idle_retain_tick(void)
> {
> tick_nohz_retain_tick(this_cpu_ptr(&tick_cpu_sched));
Looks like the content of tick_nohz_retain_tick() can move here now.
> - /*
> - * Undo the effect of get_next_timer_interrupt() called from
> - * tick_nohz_next_event().
> - */
> - timer_clear_idle();
> }
Thanks.
Le Mon, Jan 15, 2024 at 03:37:27PM +0100, Anna-Maria Behnsen a ?crit :
> When tick is stopped also the timer base is_idle flag is set. When
> reentering the timer_base_try_to_set_idle() with the tick stopped, there is
> no need to check whether the timer base needs to be set idle again. When a
> timer was enqueued in the meantime, this is already handled by the
> tick_nohz_next_event() call which was executed before
> tick_nohz_stop_tick().
>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
> ---
> kernel/time/tick-sched.c | 2 +-
> kernel/time/timer.c | 11 ++++++++---
> 2 files changed, 9 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> index c6223afc801f..27f1a2ae7f39 100644
> --- a/kernel/time/tick-sched.c
> +++ b/kernel/time/tick-sched.c
> @@ -886,7 +886,7 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
> unsigned long basejiff = ts->last_jiffies;
> u64 basemono = ts->timer_expires_base;
> - bool timer_idle;
> + bool timer_idle = ts->tick_stopped;
> u64 expires;
>
> /* Make sure we won't be trying to stop it twice in a row. */
> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> index 3a668060692e..2f69a485a070 100644
> --- a/kernel/time/timer.c
> +++ b/kernel/time/timer.c
> @@ -1999,13 +1999,18 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
> * timer_base_try_to_set_idle() - Try to set the idle state of the timer bases
> * @basej: base time jiffies
> * @basem: base time clock monotonic
> - * @idle: pointer to store the value of timer_base->is_idle
> + * @idle: pointer to store the value of timer_base->is_idle on return;
> + * *idle contains the information whether tick was already stopped
> *
> - * 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. When tick was already stopped KTIME_MAX is
> + * returned as well.
> */
> u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle)
> {
> + if (*idle)
> + return KTIME_MAX;
Ok now I see the reason behind the behavioural change.
So either:
* We remove the old behaviour consisting in clearing base->is_idle if the new
next timer is within a jiffy while the tick is stopped. But then the changelog
from the previous patch should state that and comments must be clarified.
or:
* We restore the old behaviour, making things a bit more complicated I guess.
Thanks.
Le Mon, Jan 15, 2024 at 03:37:28PM +0100, Anna-Maria Behnsen a ?crit :
> timer flags
Yes ;-)
>
> A timer might be used as a pinned timer (using add_timer_on()) and later on
> as non-pinned timer using add_timer(). When the "NOHZ timer pull at expiry
> model" is in place, the TIMER_PINNED flag is required to be used whenever a
> timer needs to expire on a dedicated CPU. Otherwise the flag must not be
> set if expiration on a dedicated CPU is not required.
>
> add_timer_on()'s behavior will be changed during the preparation patches
> for the "NOHZ timer pull at expiry model" to unconditionally set
> TIMER_PINNED flag. To be able to clear/ set the flag when queueing a
> timer, two variants of add_timer() are introduced.
>
> This is a preparatory patch and has no functional change.
>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Frederic Weisbecker <[email protected]> writes:
> Le Mon, Jan 15, 2024 at 03:37:27PM +0100, Anna-Maria Behnsen a écrit :
>> When tick is stopped also the timer base is_idle flag is set. When
>> reentering the timer_base_try_to_set_idle() with the tick stopped, there is
>> no need to check whether the timer base needs to be set idle again. When a
>> timer was enqueued in the meantime, this is already handled by the
>> tick_nohz_next_event() call which was executed before
>> tick_nohz_stop_tick().
>>
>> Signed-off-by: Anna-Maria Behnsen <[email protected]>
>> ---
>> kernel/time/tick-sched.c | 2 +-
>> kernel/time/timer.c | 11 ++++++++---
>> 2 files changed, 9 insertions(+), 4 deletions(-)
>>
>> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
>> index c6223afc801f..27f1a2ae7f39 100644
>> --- a/kernel/time/tick-sched.c
>> +++ b/kernel/time/tick-sched.c
>> @@ -886,7 +886,7 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
>> struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
>> unsigned long basejiff = ts->last_jiffies;
>> u64 basemono = ts->timer_expires_base;
>> - bool timer_idle;
>> + bool timer_idle = ts->tick_stopped;
>> u64 expires;
>>
>> /* Make sure we won't be trying to stop it twice in a row. */
>> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
>> index 3a668060692e..2f69a485a070 100644
>> --- a/kernel/time/timer.c
>> +++ b/kernel/time/timer.c
>> @@ -1999,13 +1999,18 @@ u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
>> * timer_base_try_to_set_idle() - Try to set the idle state of the timer bases
>> * @basej: base time jiffies
>> * @basem: base time clock monotonic
>> - * @idle: pointer to store the value of timer_base->is_idle
>> + * @idle: pointer to store the value of timer_base->is_idle on return;
>> + * *idle contains the information whether tick was already stopped
>> *
>> - * 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. When tick was already stopped KTIME_MAX is
>> + * returned as well.
>> */
>> u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle)
>> {
>> + if (*idle)
>> + return KTIME_MAX;
>
> Ok now I see the reason behind the behavioural change.
>
> So either:
>
> * We remove the old behaviour consisting in clearing base->is_idle if the new
> next timer is within a jiffy while the tick is stopped. But then the changelog
> from the previous patch should state that and comments must be clarified.
>
I would like to take 'either'. I thought the changelog already mentioned
it. But maybe I have to make it more explicit. I'll go and rework the
comments once more.
Thanks,
Anna-Maria
Frederic Weisbecker <[email protected]> writes:
> Le Mon, Jan 15, 2024 at 03:37:26PM +0100, Anna-Maria Behnsen a écrit :
>> @@ -889,12 +884,41 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
>> static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
>> {
>> struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
>> + unsigned long basejiff = ts->last_jiffies;
>> u64 basemono = ts->timer_expires_base;
>> - u64 expires = ts->timer_expires;
>> + bool timer_idle;
>> + u64 expires;
>>
>> /* Make sure we won't be trying to stop it twice in a row. */
>> ts->timer_expires_base = 0;
>>
>> + /*
>> + * Now the tick should be stopped definitely - so the timer base needs
>> + * to be marked idle as well to not miss a newly queued timer.
>> + */
>> + expires = timer_base_try_to_set_idle(basejiff, basemono, &timer_idle);
>> + if (!timer_idle) {
>> + /*
>> + * Do not clear tick_stopped here when it was already set - it
>
> Can that really happen? Looking at __get_next_timer_interrupt(), you're making a
> behavioural change: if base->is_idle was previously set and the next timer is
> now below/equal a jiffy, base->is_idle is not going to be cleared by
> __get_next_timer_interrupt().
>
> Therefore you shouldn't observe ts->tick_stopped && !timer_idle
>
> But I'm assuming that behavioural change wasn't intended?
It was intended to keep tick_stopped and base->is_idle in sync. So when
tick_stopped is set also base->is_idle needs to be set and dropping it
before tick_stopped is dropped will break the plan to keep it in sync.
>> + * will be retained on the next idle iteration when the tick
>> + * expired earlier than expected.
>
> I'm a bit confused by this sentence.
Me too :) It is there because of a previous version and I didn't cleaned
it up properly.
>> + */
>> + expires = basemono + TICK_NSEC;
>
> Do you need this line?
No. After revisiting it once more, it is not required, as it should be
set properly by the return value of timer_base_try_to_set_idle(). So I
should be able to completely drop this first part of the if statement.
>
>> @@ -1147,11 +1175,6 @@ void tick_nohz_idle_stop_tick(void)
>> void tick_nohz_idle_retain_tick(void)
>> {
>> tick_nohz_retain_tick(this_cpu_ptr(&tick_cpu_sched));
>
> Looks like the content of tick_nohz_retain_tick() can move here now.
I can do this.
>> - /*
>> - * Undo the effect of get_next_timer_interrupt() called from
>> - * tick_nohz_next_event().
>> - */
>> - timer_clear_idle();
>> }
>
> Thanks.
Thanks,
Anna-Maria
Frederic Weisbecker <[email protected]> writes:
> Le Mon, Jan 15, 2024 at 03:37:28PM +0100, Anna-Maria Behnsen a écrit :
>> timer flags
>
> Yes ;-)
Something got broken when importing the quilt series into git... This
also happend to some other patches/commit messages. I'll have a look at
it and will fix it.
Thanks,
Anna-Maria
Le Mon, Jan 22, 2024 at 12:45:03PM +0100, Anna-Maria Behnsen a ?crit :
> Frederic Weisbecker <[email protected]> writes:
>
> > Le Mon, Jan 15, 2024 at 03:37:26PM +0100, Anna-Maria Behnsen a ?crit :
> >> @@ -889,12 +884,41 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
> >> static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> >> {
> >> struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
> >> + unsigned long basejiff = ts->last_jiffies;
> >> u64 basemono = ts->timer_expires_base;
> >> - u64 expires = ts->timer_expires;
> >> + bool timer_idle;
> >> + u64 expires;
> >>
> >> /* Make sure we won't be trying to stop it twice in a row. */
> >> ts->timer_expires_base = 0;
> >>
> >> + /*
> >> + * Now the tick should be stopped definitely - so the timer base needs
> >> + * to be marked idle as well to not miss a newly queued timer.
> >> + */
> >> + expires = timer_base_try_to_set_idle(basejiff, basemono, &timer_idle);
> >> + if (!timer_idle) {
> >> + /*
> >> + * Do not clear tick_stopped here when it was already set - it
> >
> > Can that really happen? Looking at __get_next_timer_interrupt(), you're making a
> > behavioural change: if base->is_idle was previously set and the next timer is
> > now below/equal a jiffy, base->is_idle is not going to be cleared by
> > __get_next_timer_interrupt().
> >
> > Therefore you shouldn't observe ts->tick_stopped && !timer_idle
> >
> > But I'm assuming that behavioural change wasn't intended?
>
> It was intended to keep tick_stopped and base->is_idle in sync. So when
> tick_stopped is set also base->is_idle needs to be set and dropping it
> before tick_stopped is dropped will break the plan to keep it in sync.
Ok that sounds good.
Thanks!
Le Mon, Jan 15, 2024 at 03:37:27PM +0100, Anna-Maria Behnsen a ?crit :
> When tick is stopped also the timer base is_idle flag is set. When
> reentering the timer_base_try_to_set_idle() with the tick stopped, there is
> no need to check whether the timer base needs to be set idle again. When a
> timer was enqueued in the meantime, this is already handled by the
> tick_nohz_next_event() call which was executed before
> tick_nohz_stop_tick().
>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Le Mon, Jan 15, 2024 at 03:37:32PM +0100, Anna-Maria Behnsen a ?crit :
> Split the logic for getting next timer interrupt (no matter of recalculated
> or already stored in base->next_expiry) into a separate function named
> next_timer_interrupt(). Make it available to local call sites only.
>
> No functional change.
>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Le Mon, Jan 15, 2024 at 03:37:37PM +0100, Anna-Maria Behnsen a ?crit :
> From: "Richard Cochran (linutronix GmbH)" <[email protected]>
>
> 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) <[email protected]>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Le Mon, Jan 15, 2024 at 03:37:38PM +0100, Anna-Maria Behnsen a ?crit :
> 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 <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Le Mon, Jan 15, 2024 at 03:37:39PM +0100, Anna-Maria Behnsen a ?crit :
> From: "Richard Cochran (linutronix GmbH)" <[email protected]>
>
> 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 function in anticipation of the new caller.
>
> No functional change.
>
> Signed-off-by: Richard Cochran (linutronix GmbH) <[email protected]>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Le Mon, Jan 15, 2024 at 03:37:40PM +0100, Anna-Maria Behnsen a ?crit :
> flag
>
> To prepare for the conversion of the NOHZ timer placement to a pull at
> expiry time model it's required to have a function that returns the value
> of the is_idle flag of the timer base to keep the hierarchy states during
> online in sync with timer base state.
>
> No functional change.
>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
On 15/01/2024 14:37, Anna-Maria Behnsen wrote:
> Hi,
>
> the cleanup patches are already applied and so the contains only two parts:
>
> - Patches 1 - 4: timer base idle marking rework with two preparatory
> changes. See the section below for more details.
>
> - Patches 5 - 20: Updated timer pull model on top of timer idle rework
>
>
> The queue is available here:
>
> git://git.kernel.org/pub/scm/linux/kernel/git/tglx/devel timers/pushpull
>
>
> Move marking timer bases as idle into tick_nohz_stop_tick()
> -----------------------------------------------------------
>
> The idle marking of timer bases is done in get_next_timer_interrupt()
> whenever possible. The timer bases are idle, even if the tick will not be
> stopped. This lead to an IPI when a new first timer is enqueued remote. To
> prevent this, setting timer_base->in_idle flag is postponed to
> tick_nohz_stop_tick().
>
> Furthermore this synchronizes the states of timer base is_idle and
> tick_stopped. With the timer pull model in place, also the idle state in
> the hierarchy of a CPU is synchronized with the other idle related states.
>
>
> Timer pull model
> ----------------
>
> Placing timers at enqueue time on a target CPU based on dubious heuristics
> does not make any sense:
>
> 1) Most timer wheel timers are canceled or rearmed before they expire.
>
> 2) The heuristics to predict which CPU will be busy when the timer expires
> are wrong by definition.
>
> So placing the timers at enqueue wastes precious cycles.
>
> The proper solution to this problem is to always queue the timers on the
> local CPU and allow the non pinned timers to be pulled onto a busy CPU at
> expiry time.
>
> Therefore split the timer storage into local pinned and global timers:
> Local pinned timers are always expired on the CPU on which they have been
> queued. Global timers can be expired on any CPU.
>
> As long as a CPU is busy it expires both local and global timers. When a
> CPU goes idle it arms for the first expiring local timer. If the first
> expiring pinned (local) timer is before the first expiring movable timer,
> then no action is required because the CPU will wake up before the first
> movable timer expires. If the first expiring movable timer is before the
> first expiring pinned (local) timer, then this timer is queued into 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 separated per node. If more than one CPU group
> exist, then a second level in the hierarchy collects the groups. Depending
> on the size of the system more than 2 levels are required. Each group has a
> "migrator" which checks the timerqueue during the tick for remote timers to
> be expired.
>
> 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
> ~~~~~~~
>
> Enqueue
> ^^^^^^^
>
> The impact of wasting cycles during enqueue by using the heuristic in
> contrast to always queuing 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
> quarter 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.
>
> dbench test
> ^^^^^^^^^^^
>
> A dbench test starting X pairs of client servers are used to create load on
> the system. The measurable value is the throughput. The tests were executed
> on a zen3 machine. The base is the tip tree branch timers/core which is
> based on a v6.6-rc1.
>
> governor menu
>
> NR timers/core pull-model impact
> ----------------------------------------------
> 1 353.19 (0.19) 353.45 (0.30) 0.07%
> 2 700.10 (0.96) 687.00 (0.20) -1.87%
> 4 1329.37 (0.63) 1282.91 (0.64) -3.49%
> 8 2561.16 (1.28) 2493.56 (1.76) -2.64%
> 16 4959.96 (0.80) 4914.59 (0.64) -0.91%
> 32 9741.92 (3.44) 8979.83 (1.13) -7.82%
> 64 16535.40 (2.84) 16388.47 (4.02) -0.89%
> 128 22136.83 (2.42) 23174.50 (1.43) 4.69%
> 256 39256.77 (4.48) 38994.00 (0.39) -0.67%
> 512 36799.03 (1.83) 38091.10 (0.63) 3.51%
> 1024 32903.03 (0.86) 35370.70 (0.89) 7.50%
>
>
> governor teo
>
> NR timers/core pull-model impact
> ----------------------------------------------
> 1 350.83 (1.27) 352.45 (0.96) 0.46%
> 2 699.52 (0.85) 690.10 (0.54) -1.35%
> 4 1339.53 (1.99) 1294.71 (2.71) -3.35%
> 8 2574.10 (0.76) 2495.46 (1.97) -3.06%
> 16 4898.50 (1.74) 4783.06 (1.64) -2.36%
> 32 9115.50 (4.63) 9037.83 (1.58) -0.85%
> 64 16663.90 (3.80) 16042.00 (1.72) -3.73%
> 128 25044.93 (1.11) 23250.03 (1.08) -7.17%
> 256 38059.53 (1.70) 39658.57 (2.98) 4.20%
> 512 36369.30 (0.39) 38890.13 (0.36) 6.93%
> 1024 33956.83 (1.14) 35514.83 (0.29) 4.59%
>
>
>
> Ping Pong Oberservation
> ^^^^^^^^^^^^^^^^^^^^^^^
>
> 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.
>
>
>
>
> Possible 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.
>
>
> v9..v10: https://lore.kernel.org/r/[email protected]/
> - Address review Feedback of Bigeasy
>
>
> v8..v9: https://lore.kernel.org/r/[email protected]
> - Address review feedback
> - Add more minor cleanup fixes
> - fixes inconsistent idle related states
>
>
> v7..v8: https://lore.kernel.org/r/[email protected]
> - Address review feedback
> - Move marking timer base idle into tick_nohz_stop_tick()
> - Look ahead function to determine possible sleep lenght
>
>
> v6..v7:
> - Address review feedback of Frederic and bigeasy
> - Change lock, unlock fetch next timer interrupt logic after remote expiry
> - Move timer_expire_remote() into tick-internal.h
> - Add documentation section about "Required event and timerqueue update
> after remote expiry"
> - Fix fallout of kernel test robot
>
>
> v5..v6:
>
> - Address review of Frederic Weisbecker and Peter Zijlstra (spelling,
> locking, race in tmigr_handle_remote_cpu())
>
> - unconditionally set TIMER_PINNED flag in add_timer_on(); introduce
> add_timer() variants which set/unset TIMER_PINNED flag; drop fixing
> add_timer_on() call sites, as TIMER_PINNED flag is set implicitly;
> Fixing workqueue to use add_timer_global() instead of simply
> add_timer() for unbound work.
>
> - Drop support for siblings to end up in the same level 0 group (could be
> added again in a better way as an improvement later on)
>
> - Do not send IPI for new first deferrable timers
>
> 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/[email protected]/
> - Minimize usage of locks by storing data using atomic_cmpxchg() for
> migrator information and information about active cpus.
>
>
> Thanks,
>
> Anna-Maria
>
>
>
>
> Anna-Maria Behnsen (18):
> timers: Restructure get_next_timer_interrupt()
> timers: Split out get next timer interrupt
> timers: Move marking timer bases idle into tick_nohz_stop_tick()
> timers: Optimization for timer_base_try_to_set_idle()
> timers: Introduce add_timer() variants which modify timer flags
> workqueue: Use global variant for add_timer()
> timers: add_timer_on(): Make sure TIMER_PINNED flag is set
> timers: Ease code in run_local_timers()
> timers: Split next timer interrupt logic
> timers: Keep the pinned timers separate from the others
> timers: Retrieve next expiry of pinned/non-pinned timers separately
> timers: Split out "get next timer interrupt" functionality
> timers: Add get next timer interrupt functionality for remote CPUs
> timers: Check if timers base is handled already
> timers: Introduce function to check timer base is_idle flag
> timers: Implement the hierarchical pull model
> timer_migration: Add tracepoints
> timers: Always queue timers on the local CPU
>
> Richard Cochran (linutronix GmbH) (2):
> timers: Restructure internal locking
> tick/sched: Split out jiffies update helper function
>
> MAINTAINERS | 1 +
> include/linux/cpuhotplug.h | 1 +
> include/linux/timer.h | 16 +-
> include/trace/events/timer_migration.h | 297 +++++
> kernel/time/Makefile | 3 +
> kernel/time/tick-internal.h | 14 +
> kernel/time/tick-sched.c | 65 +-
> kernel/time/timer.c | 505 +++++--
> kernel/time/timer_migration.c | 1693 ++++++++++++++++++++++++
> kernel/time/timer_migration.h | 147 ++
> kernel/workqueue.c | 2 +-
> 11 files changed, 2629 insertions(+), 115 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
Hi Anna-Maria,
I did some quick measurements on a pixel6 Android 14 with 6.6 kernel baseline.
The workload is 5 iterations of uibenchjanktests (~70 Min runtime total).
Backport of timers/pushpull up to:
6b7e23d1f495 ("timers: Always queue timers on the local CPU").
Power:
+------------+--------+------------+-------+-----------+
| channel | metric | tag | value | perc_diff |
+------------+--------+------------+-------+-----------+
| CPU | gmean | mainline_5 | 196.6 | 0.0% |
| CPU-Big | gmean | mainline_5 | 65.3 | 0.0% |
| CPU-Little | gmean | mainline_5 | 99.6 | 0.0% |
| CPU-Mid | gmean | mainline_5 | 31.6 | 0.0% |
| GPU | gmean | mainline_5 | 36.7 | 0.0% |
| Total | gmean | mainline_5 | 233.3 | 0.0% |
| CPU | gmean | pushpull_5 | 195.9 | -0.35% |
| CPU-Big | gmean | pushpull_5 | 64.8 | -0.85% |
| CPU-Little | gmean | pushpull_5 | 98.5 | -1.12% |
| CPU-Mid | gmean | pushpull_5 | 32.6 | 3.13% |
| GPU | gmean | pushpull_5 | 36.8 | 0.19% |
| Total | gmean | pushpull_5 | 232.6 | -0.26% |
+------------+--------+------------+-------+-----------+
(Slightly skewed in favor of mainline because of starting
temperature.)
Idle residency:
+------------+---------+------------+--------+
| tag | cluster | idle_state | time |
+------------+---------+------------+--------+
| mainline_5 | little | -1.0 | 518.42 |
| mainline_5 | little | 0.0 | 238.28 |
| mainline_5 | little | 1.0 | 19.7 |
| mainline_5 | mid | -1.0 | 201.0 |
| mainline_5 | mid | 0.0 | 335.26 |
| mainline_5 | mid | 1.0 | 240.15 |
| mainline_5 | big | -1.0 | 173.86 |
| mainline_5 | big | 0.0 | 330.93 |
| mainline_5 | big | 1.0 | 271.61 |
| pushpull_5 | little | -1.0 | 526.45 |
| pushpull_5 | little | 0.0 | 257.77 |
| pushpull_5 | little | 1.0 | 5.18 |
| pushpull_5 | mid | -1.0 | 220.98 |
| pushpull_5 | mid | 0.0 | 347.43 |
| pushpull_5 | mid | 1.0 | 220.98 |
| pushpull_5 | big | -1.0 | 177.36 |
| pushpull_5 | big | 0.0 | 331.61 |
| pushpull_5 | big | 1.0 | 280.42 |
+------------+---------+------------+--------+
We can see the improvement we were hoping for:
Longer idle times on the big cores.
For completeness here are the idle misses:
+------------+-------+--------------------+
| tag | type | count_perc |
+------------+-------+--------------------+
| mainline_5 | False | 3.4829999999999997 |
| mainline_5 | True | 15.639000000000001 |
| pushpull_5 | False | 3.487 |
| pushpull_5 | True | 15.881 |
+------------+-------+--------------------+
If there is anything else you would like to see some data on, please
let me know.
Kind Regards,
Christian
Hi,
Christian Loehle <[email protected]> writes:
> On 15/01/2024 14:37, Anna-Maria Behnsen wrote:
>> Hi,
>>
>> the cleanup patches are already applied and so the contains only two parts:
>>
>> - Patches 1 - 4: timer base idle marking rework with two preparatory
>> changes. See the section below for more details.
>>
>> - Patches 5 - 20: Updated timer pull model on top of timer idle rework
>>
>>
>> The queue is available here:
>>
>> git://git.kernel.org/pub/scm/linux/kernel/git/tglx/devel timers/pushpull
>>
>>
>> Move marking timer bases as idle into tick_nohz_stop_tick()
>> -----------------------------------------------------------
>>
>> The idle marking of timer bases is done in get_next_timer_interrupt()
>> whenever possible. The timer bases are idle, even if the tick will not be
>> stopped. This lead to an IPI when a new first timer is enqueued remote. To
>> prevent this, setting timer_base->in_idle flag is postponed to
>> tick_nohz_stop_tick().
>>
>> Furthermore this synchronizes the states of timer base is_idle and
>> tick_stopped. With the timer pull model in place, also the idle state in
>> the hierarchy of a CPU is synchronized with the other idle related states.
>>
>>
>> Timer pull model
>> ----------------
>>
>> Placing timers at enqueue time on a target CPU based on dubious heuristics
>> does not make any sense:
>>
>> 1) Most timer wheel timers are canceled or rearmed before they expire.
>>
>> 2) The heuristics to predict which CPU will be busy when the timer expires
>> are wrong by definition.
>>
>> So placing the timers at enqueue wastes precious cycles.
>>
>> The proper solution to this problem is to always queue the timers on the
>> local CPU and allow the non pinned timers to be pulled onto a busy CPU at
>> expiry time.
>>
>> Therefore split the timer storage into local pinned and global timers:
>> Local pinned timers are always expired on the CPU on which they have been
>> queued. Global timers can be expired on any CPU.
>>
>> As long as a CPU is busy it expires both local and global timers. When a
>> CPU goes idle it arms for the first expiring local timer. If the first
>> expiring pinned (local) timer is before the first expiring movable timer,
>> then no action is required because the CPU will wake up before the first
>> movable timer expires. If the first expiring movable timer is before the
>> first expiring pinned (local) timer, then this timer is queued into 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 separated per node. If more than one CPU group
>> exist, then a second level in the hierarchy collects the groups. Depending
>> on the size of the system more than 2 levels are required. Each group has a
>> "migrator" which checks the timerqueue during the tick for remote timers to
>> be expired.
>>
>> 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
>> ~~~~~~~
>>
>> Enqueue
>> ^^^^^^^
>>
>> The impact of wasting cycles during enqueue by using the heuristic in
>> contrast to always queuing 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
>> quarter 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.
>>
>> dbench test
>> ^^^^^^^^^^^
>>
>> A dbench test starting X pairs of client servers are used to create load on
>> the system. The measurable value is the throughput. The tests were executed
>> on a zen3 machine. The base is the tip tree branch timers/core which is
>> based on a v6.6-rc1.
>>
>> governor menu
>>
>> NR timers/core pull-model impact
>> ----------------------------------------------
>> 1 353.19 (0.19) 353.45 (0.30) 0.07%
>> 2 700.10 (0.96) 687.00 (0.20) -1.87%
>> 4 1329.37 (0.63) 1282.91 (0.64) -3.49%
>> 8 2561.16 (1.28) 2493.56 (1.76) -2.64%
>> 16 4959.96 (0.80) 4914.59 (0.64) -0.91%
>> 32 9741.92 (3.44) 8979.83 (1.13) -7.82%
>> 64 16535.40 (2.84) 16388.47 (4.02) -0.89%
>> 128 22136.83 (2.42) 23174.50 (1.43) 4.69%
>> 256 39256.77 (4.48) 38994.00 (0.39) -0.67%
>> 512 36799.03 (1.83) 38091.10 (0.63) 3.51%
>> 1024 32903.03 (0.86) 35370.70 (0.89) 7.50%
>>
>>
>> governor teo
>>
>> NR timers/core pull-model impact
>> ----------------------------------------------
>> 1 350.83 (1.27) 352.45 (0.96) 0.46%
>> 2 699.52 (0.85) 690.10 (0.54) -1.35%
>> 4 1339.53 (1.99) 1294.71 (2.71) -3.35%
>> 8 2574.10 (0.76) 2495.46 (1.97) -3.06%
>> 16 4898.50 (1.74) 4783.06 (1.64) -2.36%
>> 32 9115.50 (4.63) 9037.83 (1.58) -0.85%
>> 64 16663.90 (3.80) 16042.00 (1.72) -3.73%
>> 128 25044.93 (1.11) 23250.03 (1.08) -7.17%
>> 256 38059.53 (1.70) 39658.57 (2.98) 4.20%
>> 512 36369.30 (0.39) 38890.13 (0.36) 6.93%
>> 1024 33956.83 (1.14) 35514.83 (0.29) 4.59%
>>
>>
>>
>> Ping Pong Oberservation
>> ^^^^^^^^^^^^^^^^^^^^^^^
>>
>> 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.
>>
>>
>>
>>
>> Possible 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.
>>
>>
>> v9..v10: https://lore.kernel.org/r/[email protected]/
>> - Address review Feedback of Bigeasy
>>
>>
>> v8..v9: https://lore.kernel.org/r/[email protected]
>> - Address review feedback
>> - Add more minor cleanup fixes
>> - fixes inconsistent idle related states
>>
>>
>> v7..v8: https://lore.kernel.org/r/[email protected]
>> - Address review feedback
>> - Move marking timer base idle into tick_nohz_stop_tick()
>> - Look ahead function to determine possible sleep lenght
>>
>>
>> v6..v7:
>> - Address review feedback of Frederic and bigeasy
>> - Change lock, unlock fetch next timer interrupt logic after remote expiry
>> - Move timer_expire_remote() into tick-internal.h
>> - Add documentation section about "Required event and timerqueue update
>> after remote expiry"
>> - Fix fallout of kernel test robot
>>
>>
>> v5..v6:
>>
>> - Address review of Frederic Weisbecker and Peter Zijlstra (spelling,
>> locking, race in tmigr_handle_remote_cpu())
>>
>> - unconditionally set TIMER_PINNED flag in add_timer_on(); introduce
>> add_timer() variants which set/unset TIMER_PINNED flag; drop fixing
>> add_timer_on() call sites, as TIMER_PINNED flag is set implicitly;
>> Fixing workqueue to use add_timer_global() instead of simply
>> add_timer() for unbound work.
>>
>> - Drop support for siblings to end up in the same level 0 group (could be
>> added again in a better way as an improvement later on)
>>
>> - Do not send IPI for new first deferrable timers
>>
>> 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/[email protected]/
>> - Minimize usage of locks by storing data using atomic_cmpxchg() for
>> migrator information and information about active cpus.
>>
>>
>> Thanks,
>>
>> Anna-Maria
>>
>>
>>
>>
>> Anna-Maria Behnsen (18):
>> timers: Restructure get_next_timer_interrupt()
>> timers: Split out get next timer interrupt
>> timers: Move marking timer bases idle into tick_nohz_stop_tick()
>> timers: Optimization for timer_base_try_to_set_idle()
>> timers: Introduce add_timer() variants which modify timer flags
>> workqueue: Use global variant for add_timer()
>> timers: add_timer_on(): Make sure TIMER_PINNED flag is set
>> timers: Ease code in run_local_timers()
>> timers: Split next timer interrupt logic
>> timers: Keep the pinned timers separate from the others
>> timers: Retrieve next expiry of pinned/non-pinned timers separately
>> timers: Split out "get next timer interrupt" functionality
>> timers: Add get next timer interrupt functionality for remote CPUs
>> timers: Check if timers base is handled already
>> timers: Introduce function to check timer base is_idle flag
>> timers: Implement the hierarchical pull model
>> timer_migration: Add tracepoints
>> timers: Always queue timers on the local CPU
>>
>> Richard Cochran (linutronix GmbH) (2):
>> timers: Restructure internal locking
>> tick/sched: Split out jiffies update helper function
>>
>> MAINTAINERS | 1 +
>> include/linux/cpuhotplug.h | 1 +
>> include/linux/timer.h | 16 +-
>> include/trace/events/timer_migration.h | 297 +++++
>> kernel/time/Makefile | 3 +
>> kernel/time/tick-internal.h | 14 +
>> kernel/time/tick-sched.c | 65 +-
>> kernel/time/timer.c | 505 +++++--
>> kernel/time/timer_migration.c | 1693 ++++++++++++++++++++++++
>> kernel/time/timer_migration.h | 147 ++
>> kernel/workqueue.c | 2 +-
>> 11 files changed, 2629 insertions(+), 115 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
>
> Hi Anna-Maria,
> I did some quick measurements on a pixel6 Android 14 with 6.6 kernel baseline.
> The workload is 5 iterations of uibenchjanktests (~70 Min runtime total).
> Backport of timers/pushpull up to:
> 6b7e23d1f495 ("timers: Always queue timers on the local CPU").
>
> Power:
> +------------+--------+------------+-------+-----------+
> | channel | metric | tag | value | perc_diff |
> +------------+--------+------------+-------+-----------+
> | CPU | gmean | mainline_5 | 196.6 | 0.0% |
> | CPU-Big | gmean | mainline_5 | 65.3 | 0.0% |
> | CPU-Little | gmean | mainline_5 | 99.6 | 0.0% |
> | CPU-Mid | gmean | mainline_5 | 31.6 | 0.0% |
> | GPU | gmean | mainline_5 | 36.7 | 0.0% |
> | Total | gmean | mainline_5 | 233.3 | 0.0% |
> | CPU | gmean | pushpull_5 | 195.9 | -0.35% |
> | CPU-Big | gmean | pushpull_5 | 64.8 | -0.85% |
> | CPU-Little | gmean | pushpull_5 | 98.5 | -1.12% |
> | CPU-Mid | gmean | pushpull_5 | 32.6 | 3.13% |
> | GPU | gmean | pushpull_5 | 36.8 | 0.19% |
> | Total | gmean | pushpull_5 | 232.6 | -0.26% |
> +------------+--------+------------+-------+-----------+
> (Slightly skewed in favor of mainline because of starting
> temperature.)
>
> Idle residency:
> +------------+---------+------------+--------+
> | tag | cluster | idle_state | time |
> +------------+---------+------------+--------+
> | mainline_5 | little | -1.0 | 518.42 |
> | mainline_5 | little | 0.0 | 238.28 |
> | mainline_5 | little | 1.0 | 19.7 |
> | mainline_5 | mid | -1.0 | 201.0 |
> | mainline_5 | mid | 0.0 | 335.26 |
> | mainline_5 | mid | 1.0 | 240.15 |
> | mainline_5 | big | -1.0 | 173.86 |
> | mainline_5 | big | 0.0 | 330.93 |
> | mainline_5 | big | 1.0 | 271.61 |
> | pushpull_5 | little | -1.0 | 526.45 |
> | pushpull_5 | little | 0.0 | 257.77 |
> | pushpull_5 | little | 1.0 | 5.18 |
> | pushpull_5 | mid | -1.0 | 220.98 |
> | pushpull_5 | mid | 0.0 | 347.43 |
> | pushpull_5 | mid | 1.0 | 220.98 |
> | pushpull_5 | big | -1.0 | 177.36 |
> | pushpull_5 | big | 0.0 | 331.61 |
> | pushpull_5 | big | 1.0 | 280.42 |
> +------------+---------+------------+--------+
>
> We can see the improvement we were hoping for:
> Longer idle times on the big cores.
This is good to know, that it works and I didn't break this in the
meantime :)
Thanks a lot for testing!
Anna-Maria
Le Mon, Jan 15, 2024 at 03:37:42PM +0100, Anna-Maria Behnsen a ?crit :
> +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_children )
> + __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_children;
__entry->num_children ?
> + __entry->childmask = child->childmask;
> + ),
> +
> + TP_printk("group=%p childmask=%0x parent=%p lvl=%d numa=%d num_children=%d",
> + __entry->child, __entry->childmask, __entry->parent,
> + __entry->lvl, __entry->numa_node, __entry->num_children)
> +);
> +
> +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_children )
> + __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_children;
Ditto.
Thanks.
Le Mon, Jan 15, 2024 at 03:37:43PM +0100, Anna-Maria Behnsen a ?crit :
> The timer pull model is in place so we can remove the heuristics which try
> to guess the best target CPU at enqueue/modification time.
>
> All non pinned timers are queued on the local CPU in the separate storage
> and eventually pulled at expiry time to a remote CPU.
>
> Originally-by: Richard Cochran (linutronix GmbH) <[email protected]>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Just one detail below:
> @@ -590,10 +590,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)
Is the TIMER_PINNED test necessary? If base->is_idle, then the timer
is now guaranteed to be TIMER_PINNED, right?
Thanks.
Frederic Weisbecker <[email protected]> writes:
> Le Mon, Jan 15, 2024 at 03:37:43PM +0100, Anna-Maria Behnsen a écrit :
>> The timer pull model is in place so we can remove the heuristics which try
>> to guess the best target CPU at enqueue/modification time.
>>
>> All non pinned timers are queued on the local CPU in the separate storage
>> and eventually pulled at expiry time to a remote CPU.
>>
>> Originally-by: Richard Cochran (linutronix GmbH) <[email protected]>
>> Signed-off-by: Anna-Maria Behnsen <[email protected]>
>
> Reviewed-by: Frederic Weisbecker <[email protected]>
>
> Just one detail below:
>
>> @@ -590,10 +590,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)
>
> Is the TIMER_PINNED test necessary? If base->is_idle, then the timer
> is now guaranteed to be TIMER_PINNED, right?
>
Yes, you are right. Should I drop it? To clarify it, I could add a
WARN_ON_ONCE(!timer->flags & TIMER_PINNED)
instead.
Thanks,
Anna-Maria
On Thu, Feb 01, 2024 at 09:58:38PM +0100, Anna-Maria Behnsen wrote:
> Frederic Weisbecker <[email protected]> writes:
>
> > Le Mon, Jan 15, 2024 at 03:37:43PM +0100, Anna-Maria Behnsen a ?crit :
> >> The timer pull model is in place so we can remove the heuristics which try
> >> to guess the best target CPU at enqueue/modification time.
> >>
> >> All non pinned timers are queued on the local CPU in the separate storage
> >> and eventually pulled at expiry time to a remote CPU.
> >>
> >> Originally-by: Richard Cochran (linutronix GmbH) <[email protected]>
> >> Signed-off-by: Anna-Maria Behnsen <[email protected]>
> >
> > Reviewed-by: Frederic Weisbecker <[email protected]>
> >
> > Just one detail below:
> >
> >> @@ -590,10 +590,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)
> >
> > Is the TIMER_PINNED test necessary? If base->is_idle, then the timer
> > is now guaranteed to be TIMER_PINNED, right?
> >
>
> Yes, you are right. Should I drop it? To clarify it, I could add a
>
> WARN_ON_ONCE(!timer->flags & TIMER_PINNED)
Yep, that looks good!
Thanks.
>
> instead.
>
> Thanks,
>
> Anna-Maria
>
The timer base is marked idle when get_next_timer_interrupt() is
executed. But the decision whether the tick will be stopped and whether the
system is able to go idle is done later. When the timer bases is marked
idle and a new first timer is enqueued remote an IPI is raised. Even if it
is not required because the tick is not stopped and the timer base is
evaluated again at the next tick.
To prevent this, the timer base is marked idle in tick_nohz_stop_tick() and
get_next_timer_interrupt() is streamlined by only looking for the next timer
interrupt. All other work is postponed to timer_base_try_to_set_idle() which is
called by tick_nohz_stop_tick(). timer_base_try_to_set_idle() never resets
timer_base::is_idle state. This is done when the tick is restarted via
tick_nohz_restart_sched_tick().
With this, tick_sched::tick_stopped and timer_base::is_idle are always in
sync. So there is no longer the need to execute timer_clear_idle() in
tick_nohz_idle_retain_tick(). This was required before, as
tick_nohz_next_event() set timer_base::is_idle even if the tick would not be
stopped. So timer_clear_idle() is only executed, when timer base is idle. So the
check whether timer base is idle, is now no longer required as well.
While at it fix some nearby whitespace damage as well.
Signed-off-by: Anna-Maria Behnsen <[email protected]>
---
v10a:
- Drop the unnecessary if branch which handles return value of
timer_base_try_to_set_idle()
- Do not open code 'tick_nohz_retain_tick()' and keep
tick_nohz_idle_retain_tick() as is.
---
kernel/time/tick-internal.h | 1 +
kernel/time/tick-sched.c | 40 +++++++++++++++++--------
kernel/time/timer.c | 60 ++++++++++++++++++++++++++-----------
3 files changed, 71 insertions(+), 30 deletions(-)
diff --git a/kernel/time/tick-internal.h b/kernel/time/tick-internal.h
index 481b7ab65e2c..47df30b871e4 100644
--- a/kernel/time/tick-internal.h
+++ b/kernel/time/tick-internal.h
@@ -163,6 +163,7 @@ 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);
+u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle);
void timer_clear_idle(void);
#define CLOCK_SET_WALL \
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index 01fb50c1b17e..4c7ccb1c9307 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -849,11 +849,6 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
*/
delta = next_tick - basemono;
if (delta <= (u64)TICK_NSEC) {
- /*
- * Tell the timer code that the base is not idle, i.e. undo
- * the effect of get_next_timer_interrupt():
- */
- timer_clear_idle();
/*
* We've not stopped the tick yet, and there's a timer in the
* next period, so no point in stopping it either, bail.
@@ -889,12 +884,34 @@ static ktime_t tick_nohz_next_event(struct tick_sched *ts, int cpu)
static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
{
struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
+ unsigned long basejiff = ts->last_jiffies;
u64 basemono = ts->timer_expires_base;
- u64 expires = ts->timer_expires;
+ bool timer_idle;
+ u64 expires;
/* Make sure we won't be trying to stop it twice in a row. */
ts->timer_expires_base = 0;
+ /*
+ * Now the tick should be stopped definitely - so the timer base needs
+ * to be marked idle as well to not miss a newly queued timer.
+ */
+ expires = timer_base_try_to_set_idle(basejiff, basemono, &timer_idle);
+ if (expires > ts->timer_expires) {
+ /*
+ * This path could only happen when the first timer was removed
+ * between calculating the possible sleep length and now (when
+ * high resolution mode is not active, timer could also be a
+ * hrtimer).
+ *
+ * We have to stick to the original calculated expiry value to
+ * not stop the tick for too long with a shallow C-state (which
+ * was programmed by cpuidle because of an early next expiration
+ * value).
+ */
+ expires = ts->timer_expires;
+ }
+
/*
* If this CPU is the one which updates jiffies, then give up
* the assignment and let it be taken by the CPU which runs
@@ -930,6 +947,10 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
* scheduler tick in tick_nohz_restart_sched_tick().
*/
if (!ts->tick_stopped) {
+ /* If the timer base is not idle, retain the tick. */
+ if (!timer_idle)
+ return;
+
calc_load_nohz_start();
quiet_vmstat();
@@ -991,7 +1012,7 @@ static void tick_nohz_restart_sched_tick(struct tick_sched *ts, ktime_t now)
touch_softlockup_watchdog_sched();
/* Cancel the scheduled timer and restore the tick: */
- ts->tick_stopped = 0;
+ ts->tick_stopped = 0;
tick_nohz_restart(ts, now);
}
@@ -1147,11 +1168,6 @@ void tick_nohz_idle_stop_tick(void)
void tick_nohz_idle_retain_tick(void)
{
tick_nohz_retain_tick(this_cpu_ptr(&tick_cpu_sched));
- /*
- * Undo the effect of get_next_timer_interrupt() called from
- * tick_nohz_next_event().
- */
- timer_clear_idle();
}
/**
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 2aea55d53416..3a668060692e 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1911,19 +1911,22 @@ static u64 cmp_next_hrtimer_event(u64 basem, u64 expires)
return DIV_ROUND_UP_ULL(nextevt, TICK_NSEC) * TICK_NSEC;
}
-static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem)
+static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem,
+ bool *idle)
{
struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
unsigned long nextevt = basej + NEXT_TIMER_MAX_DELTA;
u64 expires = KTIME_MAX;
- bool was_idle;
/*
* 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()))
+ if (cpu_is_offline(smp_processor_id())) {
+ if (idle)
+ *idle = true;
return expires;
+ }
raw_spin_lock(&base->lock);
if (base->next_expiry_recalc)
@@ -1953,17 +1956,26 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem)
__forward_timer_base(base, basej);
/*
- * Base is idle if the next event is more than a tick away.
- *
- * If the base is marked idle then any timer add operation 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).
+ * Set base->is_idle only when caller is timer_base_try_to_set_idle()
*/
- was_idle = base->is_idle;
- base->is_idle = time_after(nextevt, basej + 1);
- if (was_idle != base->is_idle)
- trace_timer_base_idle(base->is_idle, base->cpu);
+ if (idle) {
+ /*
+ * Base is idle if the next event is more than a tick away.
+ *
+ * If the base is marked idle then any timer add operation 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 (!base->is_idle) {
+ if (time_after(nextevt, basej + 1)) {
+ base->is_idle = true;
+ trace_timer_base_idle(true, base->cpu);
+ }
+ }
+ *idle = base->is_idle;
+ }
raw_spin_unlock(&base->lock);
@@ -1980,7 +1992,21 @@ static inline u64 __get_next_timer_interrupt(unsigned long basej, u64 basem)
*/
u64 get_next_timer_interrupt(unsigned long basej, u64 basem)
{
- return __get_next_timer_interrupt(basej, basem);
+ return __get_next_timer_interrupt(basej, basem, NULL);
+}
+
+/**
+ * timer_base_try_to_set_idle() - Try to set the idle state of the timer bases
+ * @basej: base time jiffies
+ * @basem: base time clock monotonic
+ * @idle: pointer to store the value of timer_base->is_idle
+ *
+ * Returns the tick aligned clock monotonic time of the next pending
+ * timer or KTIME_MAX if no timer is pending.
+ */
+u64 timer_base_try_to_set_idle(unsigned long basej, u64 basem, bool *idle)
+{
+ return __get_next_timer_interrupt(basej, basem, idle);
}
/**
@@ -1998,10 +2024,8 @@ void timer_clear_idle(void)
* sending the IPI a few instructions smaller for the cost of taking
* the lock in the exit from idle path.
*/
- if (base->is_idle) {
- base->is_idle = false;
- trace_timer_base_idle(false, smp_processor_id());
- }
+ base->is_idle = false;
+ trace_timer_base_idle(false, smp_processor_id());
}
#endif
--
2.39.2
Le Mon, Jan 15, 2024 at 03:37:36PM +0100, Anna-Maria Behnsen a ?crit :
> +# ifdef CONFIG_SMP
> +/**
> + * fetch_next_timer_interrupt_remote() - Store next timers into @tevt
> + * @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.
> + *
> + * Caller needs to make sure timer base locks are held (use
> + * timer_lock_remote_bases() for this purpose).
> + */
> +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;
> +
> + /* Preset local / global events */
> + tevt->local = tevt->global = KTIME_MAX;
> +
> + base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
> + base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
> +
> + lockdep_assert_held(&base_local->lock);
> + lockdep_assert_held(&base_global->lock);
> +
> + fetch_next_timer_interrupt(basej, basem, base_local, base_global, tevt);
If the next timer is global and it is <= jiffies + 1, the result will be
returned in tevt.local only and not on tevt.global. So a remote fetch may miss it.
For this to work on both local and remote fetch, you may need:
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 320eb4ceafa2..64ce9a7760f5 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -2004,6 +2007,8 @@ static unsigned long fetch_next_timer_interrupt(unsigned long basej, u64 basem,
if (time_before(nextevt, basej))
nextevt = basej;
tevt->local = basem + (u64)(nextevt - basej) * TICK_NSEC;
+ if (!local_first)
+ tevt->global = tevt->local;
return nextevt;
}
Frederic Weisbecker <[email protected]> writes:
> Le Mon, Jan 15, 2024 at 03:37:36PM +0100, Anna-Maria Behnsen a écrit :
>> +# ifdef CONFIG_SMP
>> +/**
>> + * fetch_next_timer_interrupt_remote() - Store next timers into @tevt
>> + * @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.
>> + *
>> + * Caller needs to make sure timer base locks are held (use
>> + * timer_lock_remote_bases() for this purpose).
>> + */
>> +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;
>> +
>> + /* Preset local / global events */
>> + tevt->local = tevt->global = KTIME_MAX;
>> +
>> + base_local = per_cpu_ptr(&timer_bases[BASE_LOCAL], cpu);
>> + base_global = per_cpu_ptr(&timer_bases[BASE_GLOBAL], cpu);
>> +
>> + lockdep_assert_held(&base_local->lock);
>> + lockdep_assert_held(&base_global->lock);
>> +
>> + fetch_next_timer_interrupt(basej, basem, base_local, base_global, tevt);
>
> If the next timer is global and it is <= jiffies + 1, the result will be
> returned in tevt.local only and not on tevt.global. So a remote fetch may miss it.
Oh no. But yes, sounds reasonable.
> For this to work on both local and remote fetch, you may need:
>
> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> index 320eb4ceafa2..64ce9a7760f5 100644
> --- a/kernel/time/timer.c
> +++ b/kernel/time/timer.c
> @@ -2004,6 +2007,8 @@ static unsigned long fetch_next_timer_interrupt(unsigned long basej, u64 basem,
> if (time_before(nextevt, basej))
> nextevt = basej;
> tevt->local = basem + (u64)(nextevt - basej) * TICK_NSEC;
> + if (!local_first)
> + tevt->global = tevt->local;
> return nextevt;
> }
>
Will fix it - with a big comment explaining why this is required for
remote call sites and will not hurt when executed on the local cpu.
Thanks a lot!
Le Mon, Feb 19, 2024 at 09:52:36AM +0100, Anna-Maria Behnsen a ?crit :
> The timer base is marked idle when get_next_timer_interrupt() is
> executed. But the decision whether the tick will be stopped and whether the
> system is able to go idle is done later. When the timer bases is marked
> idle and a new first timer is enqueued remote an IPI is raised. Even if it
> is not required because the tick is not stopped and the timer base is
> evaluated again at the next tick.
>
> To prevent this, the timer base is marked idle in tick_nohz_stop_tick() and
> get_next_timer_interrupt() is streamlined by only looking for the next timer
> interrupt. All other work is postponed to timer_base_try_to_set_idle() which is
> called by tick_nohz_stop_tick(). timer_base_try_to_set_idle() never resets
> timer_base::is_idle state. This is done when the tick is restarted via
> tick_nohz_restart_sched_tick().
>
> With this, tick_sched::tick_stopped and timer_base::is_idle are always in
> sync. So there is no longer the need to execute timer_clear_idle() in
> tick_nohz_idle_retain_tick(). This was required before, as
> tick_nohz_next_event() set timer_base::is_idle even if the tick would not be
> stopped. So timer_clear_idle() is only executed, when timer base is idle. So the
> check whether timer base is idle, is now no longer required as well.
>
> While at it fix some nearby whitespace damage as well.
>
> Signed-off-by: Anna-Maria Behnsen <[email protected]>
Reviewed-by: Frederic Weisbecker <[email protected]>
Just a small detail below that can be fixed in a further patch:
> @@ -930,6 +947,10 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> * scheduler tick in tick_nohz_restart_sched_tick().
> */
> if (!ts->tick_stopped) {
> + /* If the timer base is not idle, retain the tick. */
> + if (!timer_idle)
> + return;
This happens after tick_do_timer_cpu has been set to TICK_DO_TIMER_NONE. Ideally
it would be better to do it before. Not that it hurts in practice: another CPU
or this one will take the duty. But it looks weird to stop halfway.
Thanks!
Frederic Weisbecker <[email protected]> writes:
> Le Mon, Feb 19, 2024 at 09:52:36AM +0100, Anna-Maria Behnsen a écrit :
>> The timer base is marked idle when get_next_timer_interrupt() is
>> executed. But the decision whether the tick will be stopped and whether the
>> system is able to go idle is done later. When the timer bases is marked
>> idle and a new first timer is enqueued remote an IPI is raised. Even if it
>> is not required because the tick is not stopped and the timer base is
>> evaluated again at the next tick.
>>
>> To prevent this, the timer base is marked idle in tick_nohz_stop_tick() and
>> get_next_timer_interrupt() is streamlined by only looking for the next timer
>> interrupt. All other work is postponed to timer_base_try_to_set_idle() which is
>> called by tick_nohz_stop_tick(). timer_base_try_to_set_idle() never resets
>> timer_base::is_idle state. This is done when the tick is restarted via
>> tick_nohz_restart_sched_tick().
>>
>> With this, tick_sched::tick_stopped and timer_base::is_idle are always in
>> sync. So there is no longer the need to execute timer_clear_idle() in
>> tick_nohz_idle_retain_tick(). This was required before, as
>> tick_nohz_next_event() set timer_base::is_idle even if the tick would not be
>> stopped. So timer_clear_idle() is only executed, when timer base is idle So the
>> check whether timer base is idle, is now no longer required as well.
>>
>> While at it fix some nearby whitespace damage as well.
>>
>> Signed-off-by: Anna-Maria Behnsen <[email protected]>
>
> Reviewed-by: Frederic Weisbecker <[email protected]>
>
> Just a small detail below that can be fixed in a further patch:
>
>> @@ -930,6 +947,10 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
>> * scheduler tick in tick_nohz_restart_sched_tick().
>> */
>> if (!ts->tick_stopped) {
>> + /* If the timer base is not idle, retain the tick. */
>> + if (!timer_idle)
>> + return;
>
> This happens after tick_do_timer_cpu has been set to TICK_DO_TIMER_NONE. Ideally
> it would be better to do it before. Not that it hurts in practice: another CPU
> or this one will take the duty. But it looks weird to stop halfway.
>
Yes, you are right. I would prefere, to clean it up directly and add
another patch before this patch which simply moves the
TICK_DO_TIMER_NONE related block after the !ts->tick_stopped
block. Because a changed order shouldn't be a problem at the moment as
well, or am I wrong?
Thanks,
Anna-Maria
---8<----
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index 01fb50c1b17e..b93f0e6f273f 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -895,21 +895,6 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
/* Make sure we won't be trying to stop it twice in a row. */
ts->timer_expires_base = 0;
- /*
- * If this CPU is the one which updates jiffies, then give up
- * the assignment and let it be taken by the CPU which runs
- * the tick timer next, which might be this CPU as well. If we
- * don't drop this here, the jiffies might be stale and
- * do_timer() never gets invoked. Keep track of the fact that it
- * was the one which had the do_timer() duty last.
- */
- if (cpu == tick_do_timer_cpu) {
- tick_do_timer_cpu = TICK_DO_TIMER_NONE;
- ts->do_timer_last = 1;
- } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
- ts->do_timer_last = 0;
- }
-
/* Skip reprogram of event if it's not changed */
if (ts->tick_stopped && (expires == ts->next_tick)) {
/* Sanity check: make sure clockevent is actually programmed */
@@ -938,6 +923,21 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
trace_tick_stop(1, TICK_DEP_MASK_NONE);
}
+ /*
+ * If this CPU is the one which updates jiffies, then give up
+ * the assignment and let it be taken by the CPU which runs
+ * the tick timer next, which might be this CPU as well. If we
+ * don't drop this here, the jiffies might be stale and
+ * do_timer() never gets invoked. Keep track of the fact that it
+ * was the one which had the do_timer() duty last.
+ */
+ if (cpu == tick_do_timer_cpu) {
+ tick_do_timer_cpu = TICK_DO_TIMER_NONE;
+ ts->do_timer_last = 1;
+ } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
+ ts->do_timer_last = 0;
+ }
+
ts->next_tick = expires;
/*
Le Tue, Feb 20, 2024 at 11:48:19AM +0100, Anna-Maria Behnsen a ?crit :
> Frederic Weisbecker <[email protected]> writes:
> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> index 01fb50c1b17e..b93f0e6f273f 100644
> --- a/kernel/time/tick-sched.c
> +++ b/kernel/time/tick-sched.c
> @@ -895,21 +895,6 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> /* Make sure we won't be trying to stop it twice in a row. */
> ts->timer_expires_base = 0;
>
> - /*
> - * If this CPU is the one which updates jiffies, then give up
> - * the assignment and let it be taken by the CPU which runs
> - * the tick timer next, which might be this CPU as well. If we
> - * don't drop this here, the jiffies might be stale and
> - * do_timer() never gets invoked. Keep track of the fact that it
> - * was the one which had the do_timer() duty last.
> - */
> - if (cpu == tick_do_timer_cpu) {
> - tick_do_timer_cpu = TICK_DO_TIMER_NONE;
> - ts->do_timer_last = 1;
> - } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
> - ts->do_timer_last = 0;
> - }
> -
> /* Skip reprogram of event if it's not changed */
> if (ts->tick_stopped && (expires == ts->next_tick)) {
> /* Sanity check: make sure clockevent is actually programmed */
That should work but then you lose the optimization that resets
ts->do_timer_last even if the next timer hasn't changed.
Thanks.
> @@ -938,6 +923,21 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> trace_tick_stop(1, TICK_DEP_MASK_NONE);
> }
>
> + /*
> + * If this CPU is the one which updates jiffies, then give up
> + * the assignment and let it be taken by the CPU which runs
> + * the tick timer next, which might be this CPU as well. If we
> + * don't drop this here, the jiffies might be stale and
> + * do_timer() never gets invoked. Keep track of the fact that it
> + * was the one which had the do_timer() duty last.
> + */
> + if (cpu == tick_do_timer_cpu) {
> + tick_do_timer_cpu = TICK_DO_TIMER_NONE;
> + ts->do_timer_last = 1;
> + } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
> + ts->do_timer_last = 0;
> + }
> +
> ts->next_tick = expires;
>
> /*
Frederic Weisbecker <[email protected]> writes:
> Le Tue, Feb 20, 2024 at 11:48:19AM +0100, Anna-Maria Behnsen a écrit :
>> Frederic Weisbecker <[email protected]> writes:
>> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
>> index 01fb50c1b17e..b93f0e6f273f 100644
>> --- a/kernel/time/tick-sched.c
>> +++ b/kernel/time/tick-sched.c
>> @@ -895,21 +895,6 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
>> /* Make sure we won't be trying to stop it twice in a row. */
>> ts->timer_expires_base = 0;
>>
>> - /*
>> - * If this CPU is the one which updates jiffies, then give up
>> - * the assignment and let it be taken by the CPU which runs
>> - * the tick timer next, which might be this CPU as well. If we
>> - * don't drop this here, the jiffies might be stale and
>> - * do_timer() never gets invoked. Keep track of the fact that it
>> - * was the one which had the do_timer() duty last.
>> - */
>> - if (cpu == tick_do_timer_cpu) {
>> - tick_do_timer_cpu = TICK_DO_TIMER_NONE;
>> - ts->do_timer_last = 1;
>> - } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
>> - ts->do_timer_last = 0;
>> - }
>> -
>> /* Skip reprogram of event if it's not changed */
>> if (ts->tick_stopped && (expires == ts->next_tick)) {
>> /* Sanity check: make sure clockevent is actually programmed */
>
> That should work but then you lose the optimization that resets
> ts->do_timer_last even if the next timer hasn't changed.
>
Beside of this optimization thing, I see onther problem. But I'm not
sure, if I understood it correctly: When the CPU drops the
tick_do_timer_cpu assignment and stops the tick, it is possible, that
this CPU nevertheless executes tick_sched_do_timer() and then reassigns
to tick_do_timer_cpu?
Then it is mandatory that we have this drop the assignment also in the
path when the tick is already stopped. Otherwise the problem described
in the comment could happen with stale jiffies, no?
Thanks
> Thanks.
>
>
>
>> @@ -938,6 +923,21 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
>> trace_tick_stop(1, TICK_DEP_MASK_NONE);
>> }
>>
>> + /*
>> + * If this CPU is the one which updates jiffies, then give up
>> + * the assignment and let it be taken by the CPU which runs
>> + * the tick timer next, which might be this CPU as well. If we
>> + * don't drop this here, the jiffies might be stale and
>> + * do_timer() never gets invoked. Keep track of the fact that it
>> + * was the one which had the do_timer() duty last.
>> + */
>> + if (cpu == tick_do_timer_cpu) {
>> + tick_do_timer_cpu = TICK_DO_TIMER_NONE;
>> + ts->do_timer_last = 1;
>> + } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
>> + ts->do_timer_last = 0;
>> + }
>> +
>> ts->next_tick = expires;
>>
>> /*
Le Tue, Feb 20, 2024 at 01:02:18PM +0100, Anna-Maria Behnsen a ?crit :
> Frederic Weisbecker <[email protected]> writes:
>
> > Le Tue, Feb 20, 2024 at 11:48:19AM +0100, Anna-Maria Behnsen a ?crit :
> >> Frederic Weisbecker <[email protected]> writes:
> >> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> >> index 01fb50c1b17e..b93f0e6f273f 100644
> >> --- a/kernel/time/tick-sched.c
> >> +++ b/kernel/time/tick-sched.c
> >> @@ -895,21 +895,6 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> >> /* Make sure we won't be trying to stop it twice in a row. */
> >> ts->timer_expires_base = 0;
> >>
> >> - /*
> >> - * If this CPU is the one which updates jiffies, then give up
> >> - * the assignment and let it be taken by the CPU which runs
> >> - * the tick timer next, which might be this CPU as well. If we
> >> - * don't drop this here, the jiffies might be stale and
> >> - * do_timer() never gets invoked. Keep track of the fact that it
> >> - * was the one which had the do_timer() duty last.
> >> - */
> >> - if (cpu == tick_do_timer_cpu) {
> >> - tick_do_timer_cpu = TICK_DO_TIMER_NONE;
> >> - ts->do_timer_last = 1;
> >> - } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
> >> - ts->do_timer_last = 0;
> >> - }
> >> -
> >> /* Skip reprogram of event if it's not changed */
> >> if (ts->tick_stopped && (expires == ts->next_tick)) {
> >> /* Sanity check: make sure clockevent is actually programmed */
> >
> > That should work but then you lose the optimization that resets
> > ts->do_timer_last even if the next timer hasn't changed.
> >
>
> Beside of this optimization thing, I see onther problem. But I'm not
> sure, if I understood it correctly: When the CPU drops the
> tick_do_timer_cpu assignment and stops the tick, it is possible, that
> this CPU nevertheless executes tick_sched_do_timer() and then reassigns
> to tick_do_timer_cpu?
Yes but in this case a timer interrupt has executed and ts->next_tick
is cleared, so the above skip reprogramm branch is not taken.
Thanks.
>
> Then it is mandatory that we have this drop the assignment also in the
> path when the tick is already stopped. Otherwise the problem described
> in the comment could happen with stale jiffies, no?
>
> Thanks
>
> > Thanks.
> >
> >
> >
> >> @@ -938,6 +923,21 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> >> trace_tick_stop(1, TICK_DEP_MASK_NONE);
> >> }
> >>
> >> + /*
> >> + * If this CPU is the one which updates jiffies, then give up
> >> + * the assignment and let it be taken by the CPU which runs
> >> + * the tick timer next, which might be this CPU as well. If we
> >> + * don't drop this here, the jiffies might be stale and
> >> + * do_timer() never gets invoked. Keep track of the fact that it
> >> + * was the one which had the do_timer() duty last.
> >> + */
> >> + if (cpu == tick_do_timer_cpu) {
> >> + tick_do_timer_cpu = TICK_DO_TIMER_NONE;
> >> + ts->do_timer_last = 1;
> >> + } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
> >> + ts->do_timer_last = 0;
> >> + }
> >> +
> >> ts->next_tick = expires;
> >>
> >> /*
Frederic Weisbecker <[email protected]> writes:
> Le Tue, Feb 20, 2024 at 01:02:18PM +0100, Anna-Maria Behnsen a écrit :
>> Frederic Weisbecker <[email protected]> writes:
>>
>> > Le Tue, Feb 20, 2024 at 11:48:19AM +0100, Anna-Maria Behnsen a écrit :
>> >> Frederic Weisbecker <[email protected]> writes:
>> >> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
>> >> index 01fb50c1b17e..b93f0e6f273f 100644
>> >> --- a/kernel/time/tick-sched.c
>> >> +++ b/kernel/time/tick-sched.c
>> >> @@ -895,21 +895,6 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
>> >> /* Make sure we won't be trying to stop it twice in a row. */
>> >> ts->timer_expires_base = 0;
>> >>
>> >> - /*
>> >> - * If this CPU is the one which updates jiffies, then give up
>> >> - * the assignment and let it be taken by the CPU which runs
>> >> - * the tick timer next, which might be this CPU as well. If we
>> >> - * don't drop this here, the jiffies might be stale and
>> >> - * do_timer() never gets invoked. Keep track of the fact that it
>> >> - * was the one which had the do_timer() duty last.
>> >> - */
>> >> - if (cpu == tick_do_timer_cpu) {
>> >> - tick_do_timer_cpu = TICK_DO_TIMER_NONE;
>> >> - ts->do_timer_last = 1;
>> >> - } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
>> >> - ts->do_timer_last = 0;
>> >> - }
>> >> -
>> >> /* Skip reprogram of event if it's not changed */
>> >> if (ts->tick_stopped && (expires == ts->next_tick)) {
>> >> /* Sanity check: make sure clockevent is actually programmed */
>> >
>> > That should work but then you lose the optimization that resets
>> > ts->do_timer_last even if the next timer hasn't changed.
>> >
>>
>> Beside of this optimization thing, I see onther problem. But I'm not
>> sure, if I understood it correctly: When the CPU drops the
>> tick_do_timer_cpu assignment and stops the tick, it is possible, that
>> this CPU nevertheless executes tick_sched_do_timer() and then reassigns
>> to tick_do_timer_cpu?
>
> Yes but in this case a timer interrupt has executed and ts->next_tick
> is cleared, so the above skip reprogramm branch is not taken.
>
Yes... So I need to change it without dropping the
optimization. Otherwise someone might complain about it.
Two possible solutions:
a) split out this if/else thing for dropping the tick_do_timer_cpu
assignment into a separate function and call it:
- before the return in the skip reprogramm branch
- and after the if clause which contains stopping the tick (where it
is executed in the current proposal)
b) Take my current proposal and add before the return in the skip
reprogramm branch the following lines:
if (tick_do_timer_cpu != TICK_DO_TIMER_NONE)
ts->do_timer_last = 0;
as the first part of the tick_do_timer_cpu/last logic shouldn't be
required (because then also ts->next_tick is already cleared).
What do you prefere? Or do you prefere something else?
Thanks
> Thanks.
>
>>
>> Then it is mandatory that we have this drop the assignment also in the
>> path when the tick is already stopped. Otherwise the problem described
>> in the comment could happen with stale jiffies, no?
>>
>> Thanks
>>
>> > Thanks.
>> >
>> >
>> >
>> >> @@ -938,6 +923,21 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
>> >> trace_tick_stop(1, TICK_DEP_MASK_NONE);
>> >> }
>> >>
>> >> + /*
>> >> + * If this CPU is the one which updates jiffies, then give up
>> >> + * the assignment and let it be taken by the CPU which runs
>> >> + * the tick timer next, which might be this CPU as well. If we
>> >> + * don't drop this here, the jiffies might be stale and
>> >> + * do_timer() never gets invoked. Keep track of the fact that it
>> >> + * was the one which had the do_timer() duty last.
>> >> + */
>> >> + if (cpu == tick_do_timer_cpu) {
>> >> + tick_do_timer_cpu = TICK_DO_TIMER_NONE;
>> >> + ts->do_timer_last = 1;
>> >> + } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
>> >> + ts->do_timer_last = 0;
>> >> + }
>> >> +
>> >> ts->next_tick = expires;
>> >>
>> >> /*
On Tue, Feb 20, 2024 at 03:00:57PM +0100, Anna-Maria Behnsen wrote:
> Frederic Weisbecker <[email protected]> writes:
>
> > Le Tue, Feb 20, 2024 at 01:02:18PM +0100, Anna-Maria Behnsen a ?crit :
> >> Frederic Weisbecker <[email protected]> writes:
> >>
> >> > Le Tue, Feb 20, 2024 at 11:48:19AM +0100, Anna-Maria Behnsen a ?crit :
> >> >> Frederic Weisbecker <[email protected]> writes:
> >> >> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> >> >> index 01fb50c1b17e..b93f0e6f273f 100644
> >> >> --- a/kernel/time/tick-sched.c
> >> >> +++ b/kernel/time/tick-sched.c
> >> >> @@ -895,21 +895,6 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> >> >> /* Make sure we won't be trying to stop it twice in a row. */
> >> >> ts->timer_expires_base = 0;
> >> >>
> >> >> - /*
> >> >> - * If this CPU is the one which updates jiffies, then give up
> >> >> - * the assignment and let it be taken by the CPU which runs
> >> >> - * the tick timer next, which might be this CPU as well. If we
> >> >> - * don't drop this here, the jiffies might be stale and
> >> >> - * do_timer() never gets invoked. Keep track of the fact that it
> >> >> - * was the one which had the do_timer() duty last.
> >> >> - */
> >> >> - if (cpu == tick_do_timer_cpu) {
> >> >> - tick_do_timer_cpu = TICK_DO_TIMER_NONE;
> >> >> - ts->do_timer_last = 1;
> >> >> - } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
> >> >> - ts->do_timer_last = 0;
> >> >> - }
> >> >> -
> >> >> /* Skip reprogram of event if it's not changed */
> >> >> if (ts->tick_stopped && (expires == ts->next_tick)) {
> >> >> /* Sanity check: make sure clockevent is actually programmed */
> >> >
> >> > That should work but then you lose the optimization that resets
> >> > ts->do_timer_last even if the next timer hasn't changed.
> >> >
> >>
> >> Beside of this optimization thing, I see onther problem. But I'm not
> >> sure, if I understood it correctly: When the CPU drops the
> >> tick_do_timer_cpu assignment and stops the tick, it is possible, that
> >> this CPU nevertheless executes tick_sched_do_timer() and then reassigns
> >> to tick_do_timer_cpu?
> >
> > Yes but in this case a timer interrupt has executed and ts->next_tick
> > is cleared, so the above skip reprogramm branch is not taken.
> >
>
> Yes... So I need to change it without dropping the
> optimization. Otherwise someone might complain about it.
>
> Two possible solutions:
>
> a) split out this if/else thing for dropping the tick_do_timer_cpu
> assignment into a separate function and call it:
> - before the return in the skip reprogramm branch
> - and after the if clause which contains stopping the tick (where it
> is executed in the current proposal)
>
> b) Take my current proposal and add before the return in the skip
> reprogramm branch the following lines:
>
> if (tick_do_timer_cpu != TICK_DO_TIMER_NONE)
> ts->do_timer_last = 0;
>
> as the first part of the tick_do_timer_cpu/last logic shouldn't be
> required (because then also ts->next_tick is already cleared).
>
> What do you prefere? Or do you prefere something else?
Wouldn't the following work? If timer_idle is false, then the tick isn't
even stopped and there is nothing to do? So you can early return.
diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
index fdd57f1af1d7..1b2984acafbd 100644
--- a/kernel/time/tick-sched.c
+++ b/kernel/time/tick-sched.c
@@ -924,6 +924,9 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
expires = ts->timer_expires;
}
+ if (!timer_idle)
+ return;
+
/*
* If this CPU is the one which updates jiffies, then give up
* the assignment and let it be taken by the CPU which runs
Frederic Weisbecker <[email protected]> writes:
> On Tue, Feb 20, 2024 at 03:00:57PM +0100, Anna-Maria Behnsen wrote:
>> Frederic Weisbecker <[email protected]> writes:
>>
>> > Le Tue, Feb 20, 2024 at 01:02:18PM +0100, Anna-Maria Behnsen a écrit :
>> >> Frederic Weisbecker <[email protected]> writes:
>> >>
>> >> > Le Tue, Feb 20, 2024 at 11:48:19AM +0100, Anna-Maria Behnsen a écrit :
>> >> >> Frederic Weisbecker <[email protected]> writes:
>> >> >> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
>> >> >> index 01fb50c1b17e..b93f0e6f273f 100644
>> >> >> --- a/kernel/time/tick-sched.c
>> >> >> +++ b/kernel/time/tick-sched.c
>> >> >> @@ -895,21 +895,6 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
>> >> >> /* Make sure we won't be trying to stop it twice in a row. */
>> >> >> ts->timer_expires_base = 0;
>> >> >>
>> >> >> - /*
>> >> >> - * If this CPU is the one which updates jiffies, then give up
>> >> >> - * the assignment and let it be taken by the CPU which runs
>> >> >> - * the tick timer next, which might be this CPU as well. If we
>> >> >> - * don't drop this here, the jiffies might be stale and
>> >> >> - * do_timer() never gets invoked. Keep track of the fact that it
>> >> >> - * was the one which had the do_timer() duty last.
>> >> >> - */
>> >> >> - if (cpu == tick_do_timer_cpu) {
>> >> >> - tick_do_timer_cpu = TICK_DO_TIMER_NONE;
>> >> >> - ts->do_timer_last = 1;
>> >> >> - } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
>> >> >> - ts->do_timer_last = 0;
>> >> >> - }
>> >> >> -
>> >> >> /* Skip reprogram of event if it's not changed */
>> >> >> if (ts->tick_stopped && (expires == ts->next_tick)) {
>> >> >> /* Sanity check: make sure clockevent is actually programmed */
>> >> >
>> >> > That should work but then you lose the optimization that resets
>> >> > ts->do_timer_last even if the next timer hasn't changed.
>> >> >
>> >>
>> >> Beside of this optimization thing, I see onther problem. But I'm not
>> >> sure, if I understood it correctly: When the CPU drops the
>> >> tick_do_timer_cpu assignment and stops the tick, it is possible, that
>> >> this CPU nevertheless executes tick_sched_do_timer() and then reassigns
>> >> to tick_do_timer_cpu?
>> >
>> > Yes but in this case a timer interrupt has executed and ts->next_tick
>> > is cleared, so the above skip reprogramm branch is not taken.
>> >
>>
>> Yes... So I need to change it without dropping the
>> optimization. Otherwise someone might complain about it.
>>
>> Two possible solutions:
>>
>> a) split out this if/else thing for dropping the tick_do_timer_cpu
>> assignment into a separate function and call it:
>> - before the return in the skip reprogramm branch
>> - and after the if clause which contains stopping the tick (where it
>> is executed in the current proposal)
>>
>> b) Take my current proposal and add before the return in the skip
>> reprogramm branch the following lines:
>>
>> if (tick_do_timer_cpu != TICK_DO_TIMER_NONE)
>> ts->do_timer_last = 0;
>>
>> as the first part of the tick_do_timer_cpu/last logic shouldn't be
>> required (because then also ts->next_tick is already cleared).
>>
>> What do you prefere? Or do you prefere something else?
>
> Wouldn't the following work? If timer_idle is false, then the tick isn't
> even stopped and there is nothing to do? So you can early return.
>
> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> index fdd57f1af1d7..1b2984acafbd 100644
> --- a/kernel/time/tick-sched.c
> +++ b/kernel/time/tick-sched.c
> @@ -924,6 +924,9 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> expires = ts->timer_expires;
> }
>
> + if (!timer_idle)
> + return;
> +
> /*
> * If this CPU is the one which updates jiffies, then give up
> * the assignment and let it be taken by the CPU which runs
Yes... And then I can drop the if (!timer_idle) thing inside
!ts->tick_stopped branch.
On Tue, Feb 20, 2024 at 04:23:26PM +0100, Anna-Maria Behnsen wrote:
> Frederic Weisbecker <[email protected]> writes:
>
> > On Tue, Feb 20, 2024 at 03:00:57PM +0100, Anna-Maria Behnsen wrote:
> >> Frederic Weisbecker <[email protected]> writes:
> >>
> >> > Le Tue, Feb 20, 2024 at 01:02:18PM +0100, Anna-Maria Behnsen a ?crit :
> >> >> Frederic Weisbecker <[email protected]> writes:
> >> >>
> >> >> > Le Tue, Feb 20, 2024 at 11:48:19AM +0100, Anna-Maria Behnsen a ?crit :
> >> >> >> Frederic Weisbecker <[email protected]> writes:
> >> >> >> diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> >> >> >> index 01fb50c1b17e..b93f0e6f273f 100644
> >> >> >> --- a/kernel/time/tick-sched.c
> >> >> >> +++ b/kernel/time/tick-sched.c
> >> >> >> @@ -895,21 +895,6 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> >> >> >> /* Make sure we won't be trying to stop it twice in a row. */
> >> >> >> ts->timer_expires_base = 0;
> >> >> >>
> >> >> >> - /*
> >> >> >> - * If this CPU is the one which updates jiffies, then give up
> >> >> >> - * the assignment and let it be taken by the CPU which runs
> >> >> >> - * the tick timer next, which might be this CPU as well. If we
> >> >> >> - * don't drop this here, the jiffies might be stale and
> >> >> >> - * do_timer() never gets invoked. Keep track of the fact that it
> >> >> >> - * was the one which had the do_timer() duty last.
> >> >> >> - */
> >> >> >> - if (cpu == tick_do_timer_cpu) {
> >> >> >> - tick_do_timer_cpu = TICK_DO_TIMER_NONE;
> >> >> >> - ts->do_timer_last = 1;
> >> >> >> - } else if (tick_do_timer_cpu != TICK_DO_TIMER_NONE) {
> >> >> >> - ts->do_timer_last = 0;
> >> >> >> - }
> >> >> >> -
> >> >> >> /* Skip reprogram of event if it's not changed */
> >> >> >> if (ts->tick_stopped && (expires == ts->next_tick)) {
> >> >> >> /* Sanity check: make sure clockevent is actually programmed */
> >> >> >
> >> >> > That should work but then you lose the optimization that resets
> >> >> > ts->do_timer_last even if the next timer hasn't changed.
> >> >> >
> >> >>
> >> >> Beside of this optimization thing, I see onther problem. But I'm not
> >> >> sure, if I understood it correctly: When the CPU drops the
> >> >> tick_do_timer_cpu assignment and stops the tick, it is possible, that
> >> >> this CPU nevertheless executes tick_sched_do_timer() and then reassigns
> >> >> to tick_do_timer_cpu?
> >> >
> >> > Yes but in this case a timer interrupt has executed and ts->next_tick
> >> > is cleared, so the above skip reprogramm branch is not taken.
> >> >
> >>
> >> Yes... So I need to change it without dropping the
> >> optimization. Otherwise someone might complain about it.
> >>
> >> Two possible solutions:
> >>
> >> a) split out this if/else thing for dropping the tick_do_timer_cpu
> >> assignment into a separate function and call it:
> >> - before the return in the skip reprogramm branch
> >> - and after the if clause which contains stopping the tick (where it
> >> is executed in the current proposal)
> >>
> >> b) Take my current proposal and add before the return in the skip
> >> reprogramm branch the following lines:
> >>
> >> if (tick_do_timer_cpu != TICK_DO_TIMER_NONE)
> >> ts->do_timer_last = 0;
> >>
> >> as the first part of the tick_do_timer_cpu/last logic shouldn't be
> >> required (because then also ts->next_tick is already cleared).
> >>
> >> What do you prefere? Or do you prefere something else?
> >
> > Wouldn't the following work? If timer_idle is false, then the tick isn't
> > even stopped and there is nothing to do? So you can early return.
> >
> > diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c
> > index fdd57f1af1d7..1b2984acafbd 100644
> > --- a/kernel/time/tick-sched.c
> > +++ b/kernel/time/tick-sched.c
> > @@ -924,6 +924,9 @@ static void tick_nohz_stop_tick(struct tick_sched *ts, int cpu)
> > expires = ts->timer_expires;
> > }
> >
> > + if (!timer_idle)
> > + return;
> > +
> > /*
> > * If this CPU is the one which updates jiffies, then give up
> > * the assignment and let it be taken by the CPU which runs
>
> Yes... And then I can drop the if (!timer_idle) thing inside
> !ts->tick_stopped branch.
>
Right!