* [PATCH 0/2] softirq: fix idle accounting for an interrupted idle task
@ 2026-11-06 9:43 Radu Toader
2026-11-06 9:43 ` [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU Radu Toader
2026-11-06 9:43 ` [PATCH 2/2] softirq: Treat an interrupted idle task as idle in tick_irq_exit() Radu Toader
0 siblings, 2 replies; 8+ messages in thread
From: Radu Toader @ 2026-11-06 9:43 UTC (permalink / raw)
To: peterz, mingo, tj, tglx
Cc: juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall,
mgorman, vschneid, kprateek.nayak, void, arighi, changwoo,
frederic, anna-maria, bigeasy, joshdon, haoluo, brho,
linux-kernel, sched-ext, bpf
tick_irq_exit() decides whether an interrupt that just finished ended
inside the idle loop, and it asked sched_core_idle_cpu(), which is
idle_cpu(): false whenever the run queue is not empty. But a CPU can be
in the idle loop with tasks queued on it - forced idle under core
scheduling, and any task a sched_ext BPF scheduler holds back while
leaving it runnable - and every interrupt taken in that state skipped
tick_nohz_irq_exit(). The fix asks is_idle_task(current) instead, which
is the question the function means to ask.
Patch 1 adds the scheduler that holds the state open long enough to
measure, patch 2 is the one-line change.
Measurements:
One thread spinning 10 ms in every 100 ms in a cgroup, pinned to the
CPU the scheduler holds it on, 20 s windows, three repetitions per
cell, arms interleaved, on one 16-CPU KVM guest booted with
"no-kvmclock tsc=unstable" - which is what it takes to get an unstable
sched_clock in a guest, because mark_tsc_unstable() clears sched_clock
stability only when using_native_sched_clock(). Two kernels from this
tree differing only in patch 2, booted in turn.
The number is the cgroup's cpu.stat usage_usec over the thread's own
CLOCK_MONOTONIC measurement of its busy time, which is an upper bound
on the CPU it can possibly have used. 1.00 is correct accounting;
above 1.00 the kernel charged the task time it did not spend.
hold (ms) without patch 2 with patch 2
7 1.32 0.964
13 1.21 0.963
23 2.00 0.963
37 1.69 0.964
53 1.33 0.964
control, fair class, no BPF scheduler loaded:
1.005 1.006
Nothing in the fixed kernel's figures varies with the hold, and none of
the unfixed kernel's is within 20% of correct. The three repetitions of
each cell span at most 0.04.
The unfixed kernel also understates how long it held the task, which is
the same bug seen from the other side: the scheduler measures the hold
with scx_bpf_now(), the sched_clock that is not being resynchronized.
For the 23 ms cell it reported a 5.1 ms mean hold where the fixed
kernel reported 15.2 ms for the identical configuration. So the fixed
kernel accounts correctly across holds three times longer than the ones
the unfixed kernel gets wrong.
What is not shown, and what was not done:
No loss in /proc/stat. The sum of that CPU's fields 2 to 9 over the
window stayed within 0.6% of the window on both kernels, so in this
configuration the kcpustat_irq_exit() half of what tick_nohz_irq_exit()
does has no visible effect, unlike the forced idle case that commit
548796e2e70b ("sched/core: introduce sched_core_idle_cpu()") widened
the gate for.
The mechanism is bounded rather than measured. A kprobe on
tick_nohz_irq_exit() filtered to the idle task counted 998 calls per
20 s window on the held CPU without patch 2 against 1321 with it, n=3
each, but those ranges overlap and the two kernels run the load on
different timings.
The forced-idle half of the problem is not measured here at all. Patch
2 changes the same gate for core scheduling, where that commit first
widened it, but every number above comes from the sched_ext path.
The figures were taken with an earlier revision of patch 1, before an
automated review of the tool found six defects in it. Four of them
cannot move these numbers: the per-task hold timestamp (only one task
was ever held, so the global it replaces was never overwritten), the
ops.dequeue() bookkeeping (the load never changes affinity or priority
while parked), the release timer's pinning check (a mispinned timer
fails the run loudly, and no run failed) and the userspace CPU
validation. Two could: @target_cpu now stays in the idle loop while it
holds something instead of taking shared work, and a %SCX_ENQ_LAST
enqueue of the tagged task is now held rather than put back. Both make
the held state wider, so both move the unfixed kernel further from
1.00, not closer. The load exhausted a 20 ms slice only if a 10 ms
burst ran long, so the second one was rarely reached. The test machines
are gone and this was not re-measured.
Open question:
The Fixes: tag. The sched_ext path this was found on dates from commit
f0e1a0643a59 ("sched_ext: Implement BPF extensible scheduler class"),
which is what patch 2 carries. But the gate was idle_cpu() before that,
and what put sched_core_idle_cpu() there was commit 548796e2e70b
("sched/core: introduce sched_core_idle_cpu()"). Whichever of the two
you prefer, or neither, is yours to pick.
Tooling:
Both patches were written by Claude Opus 5 (Claude Code), including the
test scheduler, the measurement harness and these changelogs. The
measurements were run and the results checked by hand. The one-line
change in patch 2 and the reasoning for it are in Documentation terms
tool-generated content; review it as such.
Radu Toader (2):
sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle
CPU
softirq: Treat an interrupted idle task as idle in tick_irq_exit()
include/linux/sched.h | 2 -
kernel/sched/syscalls.c | 12 -
kernel/softirq.c | 12 +-
tools/sched_ext/Makefile | 2 +-
tools/sched_ext/README.md | 13 +
tools/sched_ext/scx_tickbug.bpf.c | 534 ++++++++++++++++++++++++++++++
tools/sched_ext/scx_tickbug.c | 177 ++++++++++
7 files changed, 735 insertions(+), 17 deletions(-)
create mode 100644 tools/sched_ext/scx_tickbug.bpf.c
create mode 100644 tools/sched_ext/scx_tickbug.c
base-commit: f66469d9905b39d2c260a15d7d6db450f4db67c1
--
2.43.0
^ permalink raw reply [flat|nested] 8+ messages in thread* [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU 2026-11-06 9:43 [PATCH 0/2] softirq: fix idle accounting for an interrupted idle task Radu Toader @ 2026-11-06 9:43 ` Radu Toader 2026-11-06 16:59 ` Tejun Heo 2026-11-06 20:10 ` bot+bpf-ci 2026-11-06 9:43 ` [PATCH 2/2] softirq: Treat an interrupted idle task as idle in tick_irq_exit() Radu Toader 1 sibling, 2 replies; 8+ messages in thread From: Radu Toader @ 2026-11-06 9:43 UTC (permalink / raw) To: peterz, mingo, tj, tglx Cc: juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall, mgorman, vschneid, kprateek.nayak, void, arighi, changwoo, frederic, anna-maria, bigeasy, joshdon, haoluo, brho, linux-kernel, sched-ext, bpf The state behind the tick_irq_exit() gate - the idle task running on a CPU whose run queue is not empty - is reachable with the existing example schedulers but not holdable with them, which makes everything that depends on how long it lasts impossible to measure. enqueue_task_scx() raises rq->nr_running before it calls ops.enqueue(), so a scheduler that stashes the task in a map of its own leaves it runnable and accounted on that CPU with nothing for the CPU to pick. scx_central already does exactly that, and then calls scx_bpf_kick_cpu() immediately, so the window is microseconds wide. This scheduler is the same thing with the kick removed: a tagged task is parked on the target CPU's run queue and released only by a timer pinned to another CPU, so the window is as wide as -H says. Untagged tasks go through a shared DSQ and per-CPU kthreads keep their local DSQ and preemption, so the machine stays usable and the timer's softirq cannot be starved. Three things it has to get right. The release timer must kick @target_cpu only when something is actually held: an unconditional SCX_KICK_PREEMPT lands on the task released a moment earlier and throws it off the CPU mid-run, whereupon ops.enqueue() holds it again, and the load then reports using half the CPU it asked for. @target_cpu must not take work from the shared DSQ while it is holding something, or the idle stretch under test ends early and the hold reported for the task covers time the CPU spent running. And a tagged task re-enqueued while it is the current scheduling context goes back to its local DSQ instead of being held, so a hold only ever delays the start of a run and never interrupts one - with %SCX_ENQ_LAST excluded from that test, because it arrives from put_prev_task_scx(), where rq->donor is still the task, so scx_bpf_task_running() is true for every enqueue on that path while the CPU is in fact about to go idle with that task as the only runnable one. The hold is tracked per task rather than globally: the timestamp travels with the pid through the queue, and ops.dequeue() gives up the hold when a parked task leaves BPF custody behind the scheduler's back, so a stale queue entry cannot leave the release timer kicking a CPU that is holding nothing. It reports the mean and worst hold it actually achieved, which is the independent variable of any experiment using it and is not otherwise observable from userspace. Do not use a hold that divides the load's period: with a 100 ms spinner, holds of 5/10/20 ms phase-lock and the task is only ever held for microseconds. Tooling: written by Claude Opus 5 (Claude Code) while measuring what the tick_irq_exit() idle gate changes. All of this patch is tool-generated. Signed-off-by: Radu Toader <radu.m.toader@gmail.com> --- tools/sched_ext/Makefile | 2 +- tools/sched_ext/README.md | 13 + tools/sched_ext/scx_tickbug.bpf.c | 534 ++++++++++++++++++++++++++++++ tools/sched_ext/scx_tickbug.c | 177 ++++++++++ 4 files changed, 725 insertions(+), 1 deletion(-) create mode 100644 tools/sched_ext/scx_tickbug.bpf.c create mode 100644 tools/sched_ext/scx_tickbug.c diff --git a/tools/sched_ext/Makefile b/tools/sched_ext/Makefile index 70d2503b6b33..02e1500bf402 100644 --- a/tools/sched_ext/Makefile +++ b/tools/sched_ext/Makefile @@ -191,7 +191,7 @@ $(INCLUDE_DIR)/%.bpf.skel.h: $(SCXOBJ_DIR)/%.bpf.o $(INCLUDE_DIR)/vmlinux.h $(BP SCX_COMMON_DEPS := include/scx/common.h include/scx/user_exit_info.h | $(BINDIR) -c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_userland scx_pair scx_sdt +c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_tickbug scx_flatcg scx_userland scx_pair scx_sdt $(addprefix $(BINDIR)/,$(c-sched-targets)): \ $(BINDIR)/%: \ diff --git a/tools/sched_ext/README.md b/tools/sched_ext/README.md index 0ee5a3d997e5..4addc7c2ed23 100644 --- a/tools/sched_ext/README.md +++ b/tools/sched_ext/README.md @@ -185,6 +185,19 @@ where this could be particularly useful is running VMs, where running with infinite slices and no timer ticks allows the VM to avoid unnecessary expensive vmexits. +## scx_tickbug + +A scheduler whose only job is to keep one task runnable on a CPU that is in the +idle loop, for a length of time given on the command line. That state - the +idle task running while the run queue is not empty - is reachable by several of +the schedulers here, but none of them holds it long enough to observe what +depends on it. Tasks named "spin" are parked on the target CPU's run queue and +released only by a periodic timer; everything else runs through a shared DSQ so +the machine stays usable. + +This is a test scheduler, not a policy. It exists so that the idle-time +bookkeeping skipped by an interrupt taken in that state can be measured. + ## scx_flatcg A flattened cgroup hierarchy scheduler. This scheduler implements hierarchical diff --git a/tools/sched_ext/scx_tickbug.bpf.c b/tools/sched_ext/scx_tickbug.bpf.c new file mode 100644 index 000000000000..3d7ce7423628 --- /dev/null +++ b/tools/sched_ext/scx_tickbug.bpf.c @@ -0,0 +1,534 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * scx_tickbug: keep a task runnable on a CPU that is in the idle loop. + * + * This scheduler exists to hold one state for a controllable length of time: + * the idle task running on a CPU whose run queue is not empty. + * + * enqueue_task_scx() raises rq->nr_running before it calls ops.enqueue(), so a + * BPF scheduler that stashes the task somewhere of its own - here a BPF queue + * map - leaves it runnable and accounted on that CPU with nothing for the CPU + * to pick. The CPU enters the idle loop and stays there. In that state + * idle_cpu() is false, because idle_rq() tests rq->nr_running, while + * is_idle_task(current) is true. + * + * tick_irq_exit() used to ask idle_cpu(), so every interrupt taken in that + * idle loop skipped tick_nohz_irq_exit(). Each skip leaves TS_FLAG_IDLE_ACTIVE + * clear, and the next exit from the idle loop then also skips + * sched_clock_idle_wakeup_event(), so with an unstable sched_clock the CPU's + * clock is never resynchronized: the task picked next starts with a stale + * exec_start and the next tick charges it the whole idle stretch. + * + * The in-tree example schedulers can reach this state but not hold it. + * scx_central stashes a task in a BPF queue exactly like this, then + * immediately calls scx_bpf_kick_cpu(), so the window is microseconds wide and + * nothing measurable accumulates. Here the only thing that releases a held + * task is a periodic timer, so the window is hold_ns wide and can be swept. + * + * Only tasks named by @tag_comm are held; everything else runs through a + * shared DSQ so the machine stays usable while the test runs. @target_cpu does + * not pull from that shared DSQ while it is holding something: shared work + * running there would take the CPU out of the state under test and make the + * hold this scheduler reports an overestimate. + * + * Copyright (c) 2026 Radu Toader + */ +#include <scx/common.bpf.h> + +char _license[] SEC("license") = "GPL"; + +enum { + SHARED_DSQ = 0, + MS_TO_NS = 1000LLU * 1000, +}; + +/* CPU whose run queue holds the tagged task while the CPU idles. */ +const volatile s32 target_cpu; +/* CPU the release timer is pinned to. Must not be @target_cpu. */ +const volatile s32 timer_cpu = 1; +/* How long a tagged task is held before it is allowed to run. */ +const volatile u64 hold_ns = 10 * MS_TO_NS; +const volatile u64 slice_ns; + +bool timer_pinned = true; +bool timer_started; + +/* + * Set by the release timer, consumed by ops.dispatch() on @target_cpu. Without + * it ops.dispatch() would hand the held task straight back out, because the + * core calls ops.dispatch() whenever the CPU is about to go idle. + */ +bool release_now; + +u64 nr_enq, nr_held, nr_released, nr_timers; +u64 nr_passthru, nr_locals, nr_lost, nr_other_cpu, nr_overflow, nr_requeue; +u64 nr_last, nr_dup, nr_stale, nr_undone; +/* + * How many tagged tasks are held right now. The release timer only kicks when + * this is non-zero: a kick with nothing held would preempt whatever is running + * on @target_cpu, and since that is normally the task just released, the task + * would lose most of its CPU to its own release mechanism. The first version of + * this scheduler did exactly that and reported half the usage it should. + */ +u64 nr_held_now; +/* Proof that the hold actually happened, and how wide it was. */ +u64 total_held_ns, max_held_ns; + +UEI_DEFINE(uei); + +/* + * One queued hold. The timestamp travels with the pid: a single global would + * be overwritten by the second task to be held and would then mismeasure both. + */ +struct hold_entry { + s32 pid; + u64 at; +}; + +struct { + __uint(type, BPF_MAP_TYPE_QUEUE); + __uint(max_entries, 1024); + __type(value, struct hold_entry); +} hold_q SEC(".maps"); + +/* + * Whether this task's pid is parked in @hold_q. @hold_q cannot be searched or + * amended, so this flag is the authority on whether a queued entry is still + * live: ops.dequeue() clears it when the task leaves BPF custody behind the + * scheduler's back, and release_one() then drops the entry it finds. + */ +struct task_ctx { + bool held; +}; + +struct { + __uint(type, BPF_MAP_TYPE_TASK_STORAGE); + __uint(map_flags, BPF_F_NO_PREALLOC); + __type(key, int); + __type(value, struct task_ctx); +} task_ctx_stor SEC(".maps"); + +struct tickbug_timer { + struct bpf_timer timer; +}; + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(max_entries, 1); + __type(key, u32); + __type(value, struct tickbug_timer); +} release_timer SEC(".maps"); + +static struct task_ctx *lookup_task_ctx(struct task_struct *p) +{ + struct task_ctx *tctx; + + tctx = bpf_task_storage_get(&task_ctx_stor, p, 0, 0); + if (!tctx) + scx_bpf_error("no task_ctx for %d (%s)", p->pid, p->comm); + return tctx; +} + +/* + * The load generator is called "spin". Compare 5 bytes so the terminating NUL + * has to match too and a longer name starting with "spin" is not held. + */ +static bool is_tagged(struct task_struct *p) +{ + return !bpf_strncmp(p->comm, 5, "spin"); +} + +s32 BPF_STRUCT_OPS(tickbug_select_cpu, struct task_struct *p, + s32 prev_cpu, u64 wake_flags) +{ + if (is_tagged(p)) + return target_cpu; + return prev_cpu; +} + +/* + * Deal with a tagged task: park it on @target_cpu's run queue, or decide that + * it cannot be held. Returns true if @p has been taken care of and must not go + * on to the shared DSQ. + */ +static bool handle_tagged(struct task_struct *p, struct task_ctx *tctx, + u64 enq_flags) +{ + struct hold_entry ent = { .pid = p->pid }; + + if (scx_bpf_task_cpu(p) != target_cpu) { + /* + * ops.select_cpu() is only a hint and is not called on every + * path. Counted rather than forced: a run with a non-zero + * count here did not test what it meant to. + */ + __sync_fetch_and_add(&nr_other_cpu, 1); + return false; + } + + if (tctx->held) { + /* + * Already parked. Pushing the pid again would hold one task + * twice and leave an entry behind for the release timer to + * trip over. + */ + __sync_fetch_and_add(&nr_dup, 1); + return true; + } + + if (!(enq_flags & SCX_ENQ_LAST) && scx_bpf_task_running(p)) { + /* + * Re-enqueued while it is the current scheduling context, e.g. + * after a kthread preempted it. Holding it here would take CPU + * away from work already in progress, which is not the state + * under test: the hold belongs at the start of a run, not in + * the middle of one. Put it straight back so it carries on. + * + * %SCX_ENQ_LAST is excluded because it is not that case. It + * arrives from put_prev_task_scx(), where rq->donor is still + * @p - put_prev_set_next_task() asserts as much - so + * scx_bpf_task_running() is true for every enqueue on that + * path, while the CPU is in fact about to go idle with @p as + * the only runnable task. That is what has to be held. + */ + __sync_fetch_and_add(&nr_requeue, 1); + scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, slice_ns, enq_flags); + return true; + } + + ent.at = scx_bpf_now() ?: 1; + if (bpf_map_push_elem(&hold_q, &ent, 0)) { + __sync_fetch_and_add(&nr_overflow, 1); + return false; + } + + /* + * This is the whole scheduler. The task is already in target_cpu's + * rq->nr_running; parking its pid here and deliberately not kicking + * the CPU leaves it in the idle loop with a runnable task queued. + */ + tctx->held = true; + __sync_fetch_and_add(&nr_held, 1); + __sync_fetch_and_add(&nr_held_now, 1); + return true; +} + +void BPF_STRUCT_OPS(tickbug_enqueue, struct task_struct *p, u64 enq_flags) +{ + bool last = enq_flags & SCX_ENQ_LAST; + struct task_ctx *tctx; + + __sync_fetch_and_add(&nr_enq, 1); + if (last) + __sync_fetch_and_add(&nr_last, 1); + + /* + * ops.init() kicks @timer_cpu so that ops.dispatch() runs there and + * arms the timer, but a kick does not guarantee an ops.dispatch() + * call: dispatch_one() keeps a @prev that still has slice left, and + * takes the local DSQ when it is not empty, without asking the + * scheduler. Retry from here, because a hold taken before the timer is + * up would never be released. + */ + if (unlikely(!timer_started)) + scx_bpf_kick_cpu(timer_cpu, SCX_KICK_PREEMPT); + + /* + * Per-CPU kthreads go to the head of their own CPU's local DSQ with + * preemption. The release timer runs from a softirq, so if a kthread + * such as ksoftirqd were starved behind a user task the held task + * would never be released. + */ + if ((p->flags & PF_KTHREAD) && p->nr_cpus_allowed == 1) { + __sync_fetch_and_add(&nr_locals, 1); + scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, slice_ns, + enq_flags | SCX_ENQ_PREEMPT); + return; + } + + tctx = lookup_task_ctx(p); + if (!tctx) + return; + + if (is_tagged(p) && handle_tagged(p, tctx, enq_flags)) + return; + + __sync_fetch_and_add(&nr_passthru, 1); + + /* + * A %SCX_ENQ_LAST task stays on its own CPU. put_prev_task_scx() sets + * need_resched on the incoming idle task only if the enqueue landed on + * the local DSQ, so a task left in a shared DSQ here would sit there + * until some other CPU happened to drain it. + */ + if (last) + scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, slice_ns, enq_flags); + else + scx_bpf_dsq_insert(p, SHARED_DSQ, slice_ns, enq_flags); +} + +void BPF_STRUCT_OPS(tickbug_dequeue, struct task_struct *p, u64 deq_flags) +{ + struct task_ctx *tctx; + + tctx = bpf_task_storage_get(&task_ctx_stor, p, 0, 0); + if (!tctx || !tctx->held) + return; + + /* + * A parked task is leaving BPF custody without going through + * release_one(): an affinity or property change, a class change, or + * exit. Give up the hold now. Its entry stays in @hold_q, where + * release_one() recognises it by this flag and drops it. + */ + tctx->held = false; + __sync_fetch_and_add(&nr_undone, 1); + __sync_fetch_and_sub(&nr_held_now, 1); +} + +/* Let one held task run on the CPU we are dispatching for. */ +static bool release_one(void) +{ + struct hold_entry ent; + struct task_ctx *tctx; + struct task_struct *p; + + bpf_repeat(BPF_MAX_LOOPS) { + u64 now; + + if (bpf_map_pop_elem(&hold_q, &ent)) + return false; + + /* + * Gone, or the pid belongs to someone else by now. + * ops.dequeue() has already accounted the hold. + */ + p = bpf_task_from_pid(ent.pid); + if (!p) { + __sync_fetch_and_add(&nr_lost, 1); + continue; + } + + tctx = bpf_task_storage_get(&task_ctx_stor, p, 0, 0); + if (!tctx || !tctx->held) { + __sync_fetch_and_add(&nr_stale, 1); + bpf_task_release(p); + continue; + } + + tctx->held = false; + __sync_fetch_and_sub(&nr_held_now, 1); + + /* + * Affinity may have changed while the task sat in the queue. + * Such a task goes to the shared DSQ instead of being pinned + * to a CPU it is no longer allowed on. + */ + if (!bpf_cpumask_test_cpu(target_cpu, p->cpus_ptr) || + is_migration_disabled(p)) { + scx_bpf_dsq_insert(p, SHARED_DSQ, slice_ns, 0); + bpf_task_release(p); + if (!scx_bpf_dispatch_nr_slots()) + return false; + continue; + } + + scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, slice_ns, 0); + bpf_task_release(p); + + now = scx_bpf_now(); + if (ent.at && now > ent.at) { + u64 d = now - ent.at; + + __sync_fetch_and_add(&total_held_ns, d); + if (d > max_held_ns) + max_held_ns = d; + } + + __sync_fetch_and_add(&nr_released, 1); + return true; + } + + return false; +} + +static void start_release_timer(void) +{ + struct bpf_timer *timer; + u32 key = 0; + int ret; + + if (likely(timer_started)) + return; + + /* + * BPF_F_TIMER_CPU_PIN pins to the CPU running bpf_timer_start(), which + * is not necessarily the CPU ops.dispatch() was called for: under core + * scheduling a pick runs for every SMT sibling from one CPU. Arming it + * from the wrong CPU could pin the timer to @target_cpu, which is the + * one CPU the release path cannot run on. + */ + if (bpf_get_smp_processor_id() != timer_cpu) + return; + + timer = bpf_map_lookup_elem(&release_timer, &key); + if (!timer) { + scx_bpf_error("failed to look up the release timer"); + return; + } + + ret = bpf_timer_start(timer, hold_ns, BPF_F_TIMER_CPU_PIN); + if (ret == -EINVAL) { + /* BPF_F_TIMER_CPU_PIN needs >= 6.7 */ + timer_pinned = false; + ret = bpf_timer_start(timer, hold_ns, 0); + } + if (ret) { + scx_bpf_error("bpf_timer_start failed (%d)", ret); + return; + } + + timer_started = true; +} + +void BPF_STRUCT_OPS(tickbug_dispatch, s32 cpu, struct task_struct *prev) +{ + /* + * Arm the timer from the CPU it must be pinned to. ops.init() runs in + * whatever context loaded the scheduler, which is the wrong CPU. + */ + if (cpu == timer_cpu) + start_release_timer(); + + if (cpu == target_cpu) { + if (release_now) { + release_now = false; + if (release_one()) + return; + } + + /* + * Leave @target_cpu in the idle loop for as long as it is + * holding something. Taking shared work here would end the + * idle stretch under test, and the hold reported for the task + * would cover time the CPU spent running. + */ + if (nr_held_now) + return; + } + + scx_bpf_dsq_move_to_local(SHARED_DSQ, 0); +} + +static int release_timerfn(void *map, int *key, struct bpf_timer *timer) +{ + s32 curr_cpu = bpf_get_smp_processor_id(); + int ret; + + if (timer_pinned && curr_cpu != timer_cpu) { + scx_bpf_error("release timer ran on CPU %d, not timer CPU %d", + curr_cpu, timer_cpu); + return 0; + } + + /* + * Nothing held means @target_cpu is either idle with an empty run + * queue or busy with the task released last time. Kicking in either + * case is at best pointless and at worst preempts that task. + */ + if (!nr_held_now) + goto rearm; + + /* + * Allow one held task through and make @target_cpu notice. + * SCX_KICK_PREEMPT sends a reschedule IPI, which does not go through + * irq_enter() and so does not run tick_irq_exit() itself: it only ends + * the idle stretch whose bookkeeping the mis-gated interrupts dropped. + */ + release_now = true; + scx_bpf_kick_cpu(target_cpu, SCX_KICK_PREEMPT); + +rearm: + + __sync_fetch_and_add(&nr_timers, 1); + + ret = bpf_timer_start(timer, hold_ns, + timer_pinned ? BPF_F_TIMER_CPU_PIN : 0); + if (ret) + scx_bpf_error("bpf_timer_start failed (%d)", ret); + return 0; +} + +s32 BPF_STRUCT_OPS(tickbug_init_task, struct task_struct *p, + struct scx_init_task_args *args) +{ + struct task_ctx *tctx; + + /* Sleepable, so this allocation can use GFP_KERNEL. */ + tctx = bpf_task_storage_get(&task_ctx_stor, p, 0, + BPF_LOCAL_STORAGE_GET_F_CREATE); + if (!tctx) + return -ENOMEM; + + tctx->held = false; + + return 0; +} + +int BPF_STRUCT_OPS_SLEEPABLE(tickbug_init) +{ + struct bpf_timer *timer; + u32 key = 0; + int ret; + + if (target_cpu == timer_cpu) { + scx_bpf_error("target and timer CPU must differ (both %d)", + target_cpu); + return -EINVAL; + } + + ret = scx_bpf_create_dsq(SHARED_DSQ, -1); + if (ret) { + scx_bpf_error("scx_bpf_create_dsq failed (%d)", ret); + return ret; + } + + timer = bpf_map_lookup_elem(&release_timer, &key); + if (!timer) + return -ESRCH; + + bpf_timer_init(timer, &release_timer, CLOCK_MONOTONIC); + bpf_timer_set_callback(timer, release_timerfn); + + /* Get ops.dispatch() to run on @timer_cpu so it arms the timer. */ + scx_bpf_kick_cpu(timer_cpu, 0); + + return 0; +} + +void BPF_STRUCT_OPS(tickbug_exit, struct scx_exit_info *ei) +{ + UEI_RECORD(uei, ei); +} + +SCX_OPS_DEFINE(tickbug_ops, + /* + * The last runnable task on a CPU has to come through + * ops.enqueue() too, otherwise the tagged task would simply + * keep running on @target_cpu and never be held. + */ + .flags = SCX_OPS_ENQ_LAST, + + .select_cpu = (void *)tickbug_select_cpu, + .enqueue = (void *)tickbug_enqueue, + .dequeue = (void *)tickbug_dequeue, + .dispatch = (void *)tickbug_dispatch, + .init_task = (void *)tickbug_init_task, + .init = (void *)tickbug_init, + .exit = (void *)tickbug_exit, + /* + * A held task is runnable and not running, which is what the + * watchdog looks for. Keep the timeout well above any hold. + */ + .timeout_ms = 5000U, + .name = "tickbug"); diff --git a/tools/sched_ext/scx_tickbug.c b/tools/sched_ext/scx_tickbug.c new file mode 100644 index 000000000000..1235611a33e1 --- /dev/null +++ b/tools/sched_ext/scx_tickbug.c @@ -0,0 +1,177 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * Copyright (c) 2026 Radu Toader + */ +#define _GNU_SOURCE +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <inttypes.h> +#include <signal.h> +#include <assert.h> +#include <libgen.h> +#include <bpf/bpf.h> +#include <scx/common.h> +#include "scx_tickbug.bpf.skel.h" + +const char help_fmt[] = +"Hold a task runnable on a CPU that is in the idle loop.\n" +"\n" +"Tasks named \"spin\" are queued on the target CPU's run queue and left\n" +"there, so the CPU idles with a runnable task queued, until a periodic\n" +"timer releases one. Every other task runs through a shared DSQ.\n" +"\n" +"See the top-level comment in .bpf.c for more details.\n" +"\n" +"Usage: %s [-c CPU] [-t CPU] [-H HOLD_MS] [-s SLICE_US] [-v]\n" +"\n" +" -c CPU Target CPU, the one that idles with a task queued (default: 0)\n" +" -t CPU CPU the release timer is pinned to (default: 1)\n" +" -H HOLD_MS How long a task is held before release (default: 10)\n" +" -s SLICE_US Override slice duration\n" +" -v Print libbpf debug messages\n" +" -h Display this help and exit\n"; + +static bool verbose; +static volatile int exit_req; + +static int libbpf_print_fn(enum libbpf_print_level level, const char *format, va_list args) +{ + if (level == LIBBPF_DEBUG && !verbose) + return 0; + return vfprintf(stderr, format, args); +} + +static void sigint_handler(int dummy) +{ + exit_req = 1; +} + +int main(int argc, char **argv) +{ + struct scx_tickbug *skel; + struct bpf_link *link; + __u64 seq = 0, ecode; + __u32 nr_cpu_ids; + __s32 opt; + + libbpf_set_print(libbpf_print_fn); + signal(SIGINT, sigint_handler); + signal(SIGTERM, sigint_handler); +restart: + optind = 1; + skel = SCX_OPS_OPEN(tickbug_ops, scx_tickbug); + + nr_cpu_ids = libbpf_num_possible_cpus(); + assert(nr_cpu_ids > 0); + assert(nr_cpu_ids <= INT32_MAX); + + skel->rodata->target_cpu = 0; + skel->rodata->timer_cpu = 1; + skel->rodata->hold_ns = 10ULL * 1000 * 1000; + skel->rodata->slice_ns = __COMPAT_ENUM_OR_ZERO("scx_public_consts", "SCX_SLICE_DFL"); + + while ((opt = getopt(argc, argv, "c:t:H:s:vh")) != -1) { + switch (opt) { + case 'c': + case 't': { + unsigned long cpu = strtoul(optarg, NULL, 0); + + if (cpu >= nr_cpu_ids) { + fprintf(stderr, "invalid CPU id %lu (%u max)\n", + cpu, nr_cpu_ids - 1); + scx_tickbug__destroy(skel); + return 1; + } + if (opt == 'c') + skel->rodata->target_cpu = (s32)cpu; + else + skel->rodata->timer_cpu = (s32)cpu; + break; + } + case 'H': + skel->rodata->hold_ns = strtoull(optarg, NULL, 0) * 1000 * 1000; + break; + case 's': + skel->rodata->slice_ns = strtoull(optarg, NULL, 0) * 1000; + break; + case 'v': + verbose = true; + break; + default: + fprintf(stderr, help_fmt, basename(argv[0])); + scx_tickbug__destroy(skel); + return opt != 'h'; + } + } + + if (skel->rodata->target_cpu >= (s32)nr_cpu_ids || + skel->rodata->timer_cpu >= (s32)nr_cpu_ids) { + fprintf(stderr, "need CPUs 0 and 1 to exist: target %d, timer %d, %u online\n", + skel->rodata->target_cpu, skel->rodata->timer_cpu, nr_cpu_ids); + scx_tickbug__destroy(skel); + return 1; + } + if (skel->rodata->target_cpu == skel->rodata->timer_cpu) { + fprintf(stderr, "the target CPU and the timer CPU must differ (both %d)\n", + skel->rodata->target_cpu); + scx_tickbug__destroy(skel); + return 1; + } + if (!skel->rodata->hold_ns) { + fprintf(stderr, "a hold of 0 would not hold anything\n"); + scx_tickbug__destroy(skel); + return 1; + } + + SCX_OPS_LOAD(skel, tickbug_ops, scx_tickbug, uei); + link = SCX_OPS_ATTACH(skel, tickbug_ops, scx_tickbug); + + printf("target_cpu=%d timer_cpu=%d hold_ms=%llu slice_us=%llu\n", + skel->rodata->target_cpu, skel->rodata->timer_cpu, + (unsigned long long)(skel->rodata->hold_ns / 1000000), + (unsigned long long)(skel->rodata->slice_ns / 1000)); + + if (!skel->data->timer_pinned) + printf("WARNING: BPF_F_TIMER_CPU_PIN unavailable, release timer is not pinned\n"); + + while (!exit_req && !UEI_EXITED(skel, uei)) { + __u64 released = skel->bss->nr_released; + + printf("[SEQ %llu]\n", seq++); + printf("enq :%10" PRIu64 " held:%10" PRIu64 + " released:%10" PRIu64 " timers:%10" PRIu64 "\n", + skel->bss->nr_enq, skel->bss->nr_held, + skel->bss->nr_released, skel->bss->nr_timers); + printf("pass :%10" PRIu64 " local:%10" PRIu64 + " lost:%10" PRIu64 " othrcpu:%10" PRIu64 + " overflow:%10" PRIu64 " requeue:%10" PRIu64 "\n", + skel->bss->nr_passthru, skel->bss->nr_locals, + skel->bss->nr_lost, skel->bss->nr_other_cpu, + skel->bss->nr_overflow, skel->bss->nr_requeue); + printf("last :%10" PRIu64 " dup:%10" PRIu64 + " stale:%10" PRIu64 " undone:%10" PRIu64 + " now:%10" PRIu64 "\n", + skel->bss->nr_last, skel->bss->nr_dup, + skel->bss->nr_stale, skel->bss->nr_undone, + skel->bss->nr_held_now); + /* + * The mean and the worst hold are the independent variable of + * the whole experiment: without them the run proves nothing. + */ + printf("hold_us: mean %8llu max %8llu\n", + (unsigned long long)(released ? + (skel->bss->total_held_ns / released) / 1000 : 0), + (unsigned long long)(skel->bss->max_held_ns / 1000)); + fflush(stdout); + sleep(1); + } + + bpf_link__destroy(link); + ecode = UEI_REPORT(skel, uei); + scx_tickbug__destroy(skel); + + if (!exit_req && UEI_ECODE_RESTART(ecode)) + goto restart; + return 0; +} -- 2.43.0 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU 2026-11-06 9:43 ` [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU Radu Toader @ 2026-11-06 16:59 ` Tejun Heo 2026-11-06 20:10 ` bot+bpf-ci 1 sibling, 0 replies; 8+ messages in thread From: Tejun Heo @ 2026-11-06 16:59 UTC (permalink / raw) To: Radu Toader Cc: peterz, mingo, tglx, juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall, mgorman, vschneid, kprateek.nayak, void, arighi, changwoo, frederic, anna-maria, bigeasy, joshdon, haoluo, brho, linux-kernel, sched-ext, bpf Hello, On Fri, Nov 06, 2026 at 09:43:42AM +0000, Radu Toader wrote: ... > This scheduler is the same thing with the kick removed: a tagged task > is parked on the target CPU's run queue and released only by a timer > pinned to another CPU, so the window is as wide as -H says. Untagged > tasks go through a shared DSQ and per-CPU kthreads keep their local DSQ > and preemption, so the machine stays usable and the timer's softirq > cannot be starved. Thanks for catching the bug. However, this scheduler is more of an one-off debug code and I'm not sure we want to carry this in tree. Maybe put it in a github gist or sth and point to it from the fix patch? Thanks. -- tejun ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU 2026-11-06 9:43 ` [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU Radu Toader 2026-11-06 16:59 ` Tejun Heo @ 2026-11-06 20:10 ` bot+bpf-ci 1 sibling, 0 replies; 8+ messages in thread From: bot+bpf-ci @ 2026-11-06 20:10 UTC (permalink / raw) To: radu.m.toader, peterz, mingo, tj, tglx Cc: juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall, mgorman, vschneid, kprateek.nayak, void, arighi, changwoo, frederic, anna-maria, bigeasy, joshdon, haoluo, brho, linux-kernel, sched-ext, bpf, ast, andrii, daniel, martin.lau, eddyz87, yonghong.song, mason, ihor.solodrai [-- Attachment #1: Type: text/plain, Size: 4479 bytes --] > sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU TL;DR: - Possible starvation of a task pinned to the target CPU until the sched_ext watchdog unloads the scheduler - Question whether this debug scheduler belongs in tree - README tense and a sleepable-comment nit > sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU Tejun Heo replied to the posting of this patch: > this scheduler is more of an one-off debug code and I'm not sure we want > to carry this in tree. Maybe put it in a github gist or sth and point to > it from the fix patch? I didn't see a reply to this. Is the plan still to carry scx_tickbug in tools/sched_ext? > diff --git a/tools/sched_ext/README.md b/tools/sched_ext/README.md > --- a/tools/sched_ext/README.md > +++ b/tools/sched_ext/README.md [ ... ] > +This is a test scheduler, not a policy. It exists so that the idle-time > +bookkeeping skipped by an interrupt taken in that state can be measured. The README says the scheduler measures the bookkeeping skipped by an interrupt in that state, which matches tick_irq_exit() at this commit. The next commit in the series, 24b81cae8220 ("softirq: Treat an interrupted idle task as idle in tick_irq_exit()"), changes the gate so that skip no longer happens, and does not update this README. Meanwhile the header comment in scx_tickbug.bpf.c already says "tick_irq_exit() used to ask idle_cpu()", which is past tense. Could the README say that the scheduler reproduces the condition handled by the tick_irq_exit() change and can be used to check it, and could the README and the BPF header comment use the same tense? > diff --git a/tools/sched_ext/scx_tickbug.bpf.c b/tools/sched_ext/scx_tickbug.bpf.c > --- /dev/null > +++ b/tools/sched_ext/scx_tickbug.bpf.c [ ... ] > +void BPF_STRUCT_OPS(tickbug_dispatch, s32 cpu, struct task_struct *prev) > +{ [ ... ] > + if (cpu == target_cpu) { > + if (release_now) { > + release_now = false; > + if (release_one()) > + return; > + } > + > + /* > + * Leave @target_cpu in the idle loop for as long as it is > + * holding something. Taking shared work here would end the > + * idle stretch under test, and the hold reported for the task > + * would cover time the CPU spent running. > + */ > + if (nr_held_now) > + return; > + } Can this starve an untagged task that is pinned to @target_cpu? tickbug_enqueue() sends everything except per-CPU kthreads and SCX_ENQ_LAST tasks to SHARED_DSQ, which includes a user task pinned with something like taskset -c 0. While nr_held_now is non-zero, the early return above skips: scx_bpf_dsq_move_to_local(SHARED_DSQ, 0); and no other CPU can consume that task, because it fails task_allowed_on_cpu() there. nr_held_now can stay non-zero at every dispatch when two tagged tasks hand off to each other. For example, A wakes B and blocks; B's wakeup on @target_cpu is held, so nr_held_now is 1; ops.dispatch(target_cpu) returns early and the CPU idles; the timer releases B, B wakes A, A is held, B blocks, and so on. The pinned task would then sit on the runnable list until the watchdog (timeout_ms of 5000) raises SCX_EXIT_ERROR_STALL and unloads the scheduler, which doesn't match the commit message's "the machine stays usable". Would sending any task with nr_cpus_allowed == 1 to SCX_DSQ_LOCAL, as is done for per-CPU kthreads, address this? [ ... ] > +s32 BPF_STRUCT_OPS(tickbug_init_task, struct task_struct *p, > + struct scx_init_task_args *args) > +{ > + struct task_ctx *tctx; > + > + /* Sleepable, so this allocation can use GFP_KERNEL. */ > + tctx = bpf_task_storage_get(&task_ctx_stor, p, 0, > + BPF_LOCAL_STORAGE_GET_F_CREATE); This isn't a bug, but is this comment accurate? tickbug_init_task() is declared with BPF_STRUCT_OPS(), not BPF_STRUCT_OPS_SLEEPABLE() as scx_qmap and scx_sdt do for their init_task, so the program isn't sleepable. Also, since commit 136deea435dc ("bpf: Remove gfp_flags plumbing from bpf_local_storage_update()"), bpf_task_storage_get() allocates with bpf_map_kmalloc_nolock() regardless of sleepability. Should the comment be dropped, or should the op be declared with BPF_STRUCT_OPS_SLEEPABLE() if sleepability was intended? --- AI reviewed your patch. Please fix the bug or email reply why it's not a bug. See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md CI run summary: https://github.com/kernel-patches/bpf/actions/runs/42280840441 ^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 2/2] softirq: Treat an interrupted idle task as idle in tick_irq_exit() 2026-11-06 9:43 [PATCH 0/2] softirq: fix idle accounting for an interrupted idle task Radu Toader 2026-11-06 9:43 ` [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU Radu Toader @ 2026-11-06 9:43 ` Radu Toader 2026-11-06 10:23 ` Peter Zijlstra 2026-11-06 19:55 ` bot+bpf-ci 1 sibling, 2 replies; 8+ messages in thread From: Radu Toader @ 2026-11-06 9:43 UTC (permalink / raw) To: peterz, mingo, tj, tglx Cc: juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall, mgorman, vschneid, kprateek.nayak, void, arighi, changwoo, frederic, anna-maria, bigeasy, joshdon, haoluo, brho, linux-kernel, sched-ext, bpf tick_irq_exit() only runs tick_nohz_irq_exit() if sched_core_idle_cpu(), which is idle_cpu() unless core scheduling is built in. idle_cpu() is false when the run queue has tasks while the idle task runs. That is the normal state of a CPU under sched_ext whose BPF scheduler holds back a runnable task of that CPU in one of its queues, e.g. a task of a cgroup at its CPU limit: the task stays queued on the CPU's run queue and counts in rq->nr_running, while the CPU sits in the idle loop. tick_nohz_irq_exit() is what marks an idle CPU as idle again for the scheduler clock after an interrupt in the idle loop (TS_FLAG_IDLE_ACTIVE, sched_clock_idle_sleep_event()). Without it, the next exit from the idle loop doesn't resynchronize the CPU's sched_clock with sched_clock_idle_wakeup_event(). With an unstable sched_clock, e.g. under kvm-clock without a stable TSC, the clock of a CPU in tick-stopped idle is clamped to its last stamp plus a tick, so a task picked after a reschedule IPI (which doesn't go through irq_enter()) starts with a stale exec_start, and the next tick charges the whole idle stretch to it. A cgroup holding one such task was charged twice the CPU time it could possibly have used; numbers are in the cover letter. Commit 548796e2e70b ("sched/core: introduce sched_core_idle_cpu()") fixed this same gate for the other case of "the idle task runs while nr_running > 0", forced idle under core scheduling, where the symptom was too little idle time in /proc/stat. sched_ext made that state reachable without CONFIG_SCHED_CORE, and there the symptom is idle time charged to a task as runtime. Ask whether the idle task is running, which covers both cases. CPUs whose run queue is really empty are unaffected; a CPU interrupted between leaving the idle loop and switching to a task has need_resched() set or has already left the idle accounting, see tick_nohz_irq_exit(). sched_core_idle_cpu() has no users left and goes. The new gate is strictly wider than the old one, and deliberately so. idle_cpu() is idle_rq(), rq->curr == rq->idle && !rq->nr_running && !rq->ttwu_pending, so besides the two cases above it also skipped a CPU idling with a wakeup queued by TTWU_QUEUE whose IPI has not run yet. That case is now covered too, on any kernel and not just under sched_ext. It is the same latch failure for a shorter window, so covering it looks right rather than merely harmless, but it was reached by reading the code and not measured on its own. What keeps the wider gate from giving a CPU idle accounting it should not have is that tick_nohz_irq_exit() tests TS_FLAG_INIDLE itself and only does the idle bookkeeping inside the idle loop. Compile-tested in four x86_64 defconfig variants - SCHED_CORE=y with NO_HZ_FULL=y, SCHED_CORE=n, NO_HZ_COMMON=n, and SCHED_CLASS_EXT=y with SCHED_CORE=y and NO_HZ_FULL=y - with no new warnings at W=1. Tooling: the bug was found and this patch and changelog were written by Claude Opus 5 (Claude Code), in a session measuring cgroup CPU limit enforcement under sched_ext. All of the patch and all of the changelog are tool-generated; the cover letter says what was and was not measured. By the threat model in Documentation/process/threat-model.rst this is a regular bug and not a vulnerability: it misreports CPU time under a legitimate configuration and crosses no privilege or isolation boundary. Fixes: f0e1a0643a59 ("sched_ext: Implement BPF extensible scheduler class") Signed-off-by: Radu Toader <radu.m.toader@gmail.com> --- include/linux/sched.h | 2 -- kernel/sched/syscalls.c | 12 ------------ kernel/softirq.c | 12 ++++++++++-- 3 files changed, 10 insertions(+), 16 deletions(-) diff --git a/include/linux/sched.h b/include/linux/sched.h index 1c93da75226e..0e704ea9416f 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -2326,11 +2326,9 @@ extern void sched_core_free(struct task_struct *tsk); extern void sched_core_fork(struct task_struct *p); extern int sched_core_share_pid(unsigned int cmd, pid_t pid, enum pid_type type, unsigned long uaddr); -extern int sched_core_idle_cpu(int cpu); #else static inline void sched_core_free(struct task_struct *tsk) { } static inline void sched_core_fork(struct task_struct *p) { } -static inline int sched_core_idle_cpu(int cpu) { return idle_cpu(cpu); } #endif extern void sched_set_stop_task(int cpu, struct task_struct *stop); diff --git a/kernel/sched/syscalls.c b/kernel/sched/syscalls.c index 45a127deeadd..22e316680a86 100644 --- a/kernel/sched/syscalls.c +++ b/kernel/sched/syscalls.c @@ -194,18 +194,6 @@ struct task_struct *idle_task(int cpu) return cpu_rq(cpu)->idle; } -#ifdef CONFIG_SCHED_CORE -int sched_core_idle_cpu(int cpu) -{ - struct rq *rq = cpu_rq(cpu); - - if (sched_core_enabled(rq) && rq->curr == rq->idle) - return 1; - - return idle_cpu(cpu); -} -#endif /* CONFIG_SCHED_CORE */ - /** * find_process_by_pid - find a process with a matching PID value. * @pid: the pid in question. diff --git a/kernel/softirq.c b/kernel/softirq.c index 7fc2200392cd..e7d649c29c0c 100644 --- a/kernel/softirq.c +++ b/kernel/softirq.c @@ -738,8 +738,16 @@ static inline void tick_irq_exit(void) #ifdef CONFIG_NO_HZ_COMMON int cpu = smp_processor_id(); - /* Make sure that timer wheel updates are propagated */ - if ((sched_core_idle_cpu(cpu) && !need_resched()) || tick_nohz_full_cpu(cpu)) { + /* + * Make sure that timer wheel updates are propagated. An interrupted + * idle loop counts as idle even with runnable tasks queued on the + * CPU: forced idle under core scheduling, and the tasks sched_ext + * keeps on a CPU's run queue while its BPF scheduler holds them back. + * idle_cpu() would skip the idle bookkeeping of tick_nohz_irq_exit() + * for those, and with an unstable sched_clock the CPU's clock then + * isn't resynchronized when it leaves the idle loop. + */ + if ((is_idle_task(current) && !need_resched()) || tick_nohz_full_cpu(cpu)) { if (hardirq_count() == HARDIRQ_OFFSET) tick_nohz_irq_exit(); } -- 2.43.0 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/2] softirq: Treat an interrupted idle task as idle in tick_irq_exit() 2026-11-06 9:43 ` [PATCH 2/2] softirq: Treat an interrupted idle task as idle in tick_irq_exit() Radu Toader @ 2026-11-06 10:23 ` Peter Zijlstra 2026-11-06 19:55 ` bot+bpf-ci 1 sibling, 0 replies; 8+ messages in thread From: Peter Zijlstra @ 2026-11-06 10:23 UTC (permalink / raw) To: Radu Toader Cc: mingo, tj, tglx, juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall, mgorman, vschneid, kprateek.nayak, void, arighi, changwoo, frederic, anna-maria, bigeasy, joshdon, haoluo, brho, linux-kernel, sched-ext, bpf On Fri, Nov 06, 2026 at 09:43:43AM +0000, Radu Toader wrote: > diff --git a/kernel/softirq.c b/kernel/softirq.c > index 7fc2200392cd..e7d649c29c0c 100644 > --- a/kernel/softirq.c > +++ b/kernel/softirq.c > @@ -738,8 +738,16 @@ static inline void tick_irq_exit(void) > #ifdef CONFIG_NO_HZ_COMMON > int cpu = smp_processor_id(); > > + /* > + * Make sure that timer wheel updates are propagated. An interrupted > + * idle loop counts as idle even with runnable tasks queued on the > + * CPU: forced idle under core scheduling, and the tasks sched_ext > + * keeps on a CPU's run queue while its BPF scheduler holds them back. > + * idle_cpu() would skip the idle bookkeeping of tick_nohz_irq_exit() > + * for those, and with an unstable sched_clock the CPU's clock then > + * isn't resynchronized when it leaves the idle loop. > + */ > + if ((is_idle_task(current) && !need_resched()) || tick_nohz_full_cpu(cpu)) { So is_idle_task() is also true for idle-injection tasks. I *think* that is also right in this case, but it wasn't mentioned. That is, we can have tasks that are not rq->idle for which is_idle_task()/PF_IDLE is true, those tasks will also 'run' an idle state, see play_idle_precise() and its users. > if (hardirq_count() == HARDIRQ_OFFSET) > tick_nohz_irq_exit(); > } > -- > 2.43.0 > ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 2/2] softirq: Treat an interrupted idle task as idle in tick_irq_exit() 2026-11-06 9:43 ` [PATCH 2/2] softirq: Treat an interrupted idle task as idle in tick_irq_exit() Radu Toader 2026-11-06 10:23 ` Peter Zijlstra @ 2026-11-06 19:55 ` bot+bpf-ci 1 sibling, 0 replies; 8+ messages in thread From: bot+bpf-ci @ 2026-11-06 19:55 UTC (permalink / raw) To: radu.m.toader, peterz, mingo, tj, tglx Cc: juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall, mgorman, vschneid, kprateek.nayak, void, arighi, changwoo, frederic, anna-maria, bigeasy, joshdon, haoluo, brho, linux-kernel, sched-ext, bpf, ast, andrii, daniel, martin.lau, eddyz87, yonghong.song, mason, ihor.solodrai [-- Attachment #1: Type: text/plain, Size: 6249 bytes --] > softirq: Treat an interrupted idle task as idle in tick_irq_exit() TL;DR: Commit message only: claims the new is_idle_task() gate is "strictly wider", but it also now covers idle-injection kthreads (PF_IDLE) and not some early-boot cases; the changelog should say so. > softirq: Treat an interrupted idle task as idle in tick_irq_exit() > > tick_irq_exit() only runs tick_nohz_irq_exit() if sched_core_idle_cpu(), > which is idle_cpu() unless core scheduling is built in. idle_cpu() is > false when the run queue has tasks while the idle task runs. > > That is the normal state of a CPU under sched_ext whose BPF scheduler > holds back a runnable task of that CPU in one of its queues, e.g. a task > of a cgroup at its CPU limit: the task stays queued on the CPU's run > queue and counts in rq->nr_running, while the CPU sits in the idle loop. > > tick_nohz_irq_exit() is what marks an idle CPU as idle again for the > scheduler clock after an interrupt in the idle loop > (TS_FLAG_IDLE_ACTIVE, sched_clock_idle_sleep_event()). Without it, the > next exit from the idle loop doesn't resynchronize the CPU's sched_clock > with sched_clock_idle_wakeup_event(). With an unstable sched_clock, e.g. > under kvm-clock without a stable TSC, the clock of a CPU in tick-stopped > idle is clamped to its last stamp plus a tick, so a task picked after a > reschedule IPI (which doesn't go through irq_enter()) starts with a > stale exec_start, and the next tick charges the whole idle stretch to > it. A cgroup holding one such task was charged twice the CPU time it > could possibly have used; numbers are in the cover letter. > > Commit 548796e2e70b ("sched/core: introduce sched_core_idle_cpu()") > fixed this same gate for the other case of "the idle task runs while > nr_running > 0", forced idle under core scheduling, where the symptom > was too little idle time in /proc/stat. sched_ext made that state > reachable without CONFIG_SCHED_CORE, and there the symptom is idle time > charged to a task as runtime. > > Ask whether the idle task is running, which covers both cases. CPUs > whose run queue is really empty are unaffected; a CPU interrupted > between leaving the idle loop and switching to a task has need_resched() > set or has already left the idle accounting, see tick_nohz_irq_exit(). > sched_core_idle_cpu() has no users left and goes. > > The new gate is strictly wider than the old one, and deliberately so. > idle_cpu() is idle_rq(), rq->curr == rq->idle && !rq->nr_running && > !rq->ttwu_pending, so besides the two cases above it also skipped a CPU > idling with a wakeup queued by TTWU_QUEUE whose IPI has not run yet. > That case is now covered too, on any kernel and not just under > sched_ext. It is the same latch failure for a shorter window, so > covering it looks right rather than merely harmless, but it was reached > by reading the code and not measured on its own. What keeps the wider > gate from giving a CPU idle accounting it should not have is that > tick_nohz_irq_exit() tests TS_FLAG_INIDLE itself and only does the idle > bookkeeping inside the idle loop. > > Compile-tested in four x86_64 defconfig variants - SCHED_CORE=y with > NO_HZ_FULL=y, SCHED_CORE=n, NO_HZ_COMMON=n, and SCHED_CLASS_EXT=y with > SCHED_CORE=y and NO_HZ_FULL=y - with no new warnings at W=1. > > Tooling: the bug was found and this patch and changelog were written by > Claude Opus 5 (Claude Code), in a session measuring cgroup CPU limit > enforcement under sched_ext. All of the patch and all of the changelog > are tool-generated; the cover letter says what was and was not measured. > By the threat model in Documentation/process/threat-model.rst this is a > regular bug and not a vulnerability: it misreports CPU time under a > legitimate configuration and crosses no privilege or isolation boundary. > > Fixes: f0e1a0643a59 ("sched_ext: Implement BPF extensible scheduler class") > Signed-off-by: Radu Toader <radu.m.toader@gmail.com> > The commit message says "The new gate is strictly wider than the old one, and deliberately so", and lists the newly covered cases as nr_running > 0 while the idle task runs, and a queued TTWU_QUEUE wakeup. Is that accurate? is_idle_task() tests PF_IDLE on current, which is a different predicate from rq->curr == rq->idle. play_idle_precise() sets PF_IDLE on a SCHED_FIFO kthread and then loops on do_idle(): kernel/sched/idle.c:play_idle_precise() { ... current->flags |= PF_IDLE; ... while (!READ_ONCE(it.done)) do_idle(); ... } During idle injection rq->curr is that kthread, so the old gate was false (except on nohz_full CPUs), while the new gate is true whenever need_resched() is clear. Interrupts during injected idle will now run tick_nohz_irq_exit() with TS_FLAG_INIDLE set, which does tick_nohz_clock_sleep(), updates ts->idle_entrytime, and may start kcpustat idle accounting. This affects users such as intel_powerclamp, cpuidle_cooling and idle_inject, and is not limited to sched_ext. Peter Zijlstra raised the same point on the earlier posting: "So is_idle_task() is also true for idle-injection tasks. I *think* that is also right in this case, but it wasn't mentioned." No reply or changelog update addressing it is visible. Conversely, PF_IDLE is set by cpu_startup_entry(), not by init_idle(), so a CPU running its idle task before that point (rq->curr == rq->idle, nr_running == 0) satisfied idle_cpu() but does not satisfy is_idle_task(current). That looks harmless, since TS_FLAG_INIDLE is only set inside do_idle() and nohz_full CPUs are still covered by tick_nohz_full_cpu(cpu), but it means the gate is not strictly wider. Could the commit message name the idle injection case among the newly covered states, and replace "strictly wider" with wording that matches the PF_IDLE semantics? --- AI reviewed your patch. Please fix the bug or email reply why it's not a bug. See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md CI run summary: https://github.com/kernel-patches/bpf/actions/runs/42280840441 ^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 0/2] softirq: fix idle accounting for an interrupted idle task
@ 2026-11-05 20:02 Radu Toader
2026-11-05 20:02 ` [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU Radu Toader
0 siblings, 1 reply; 8+ messages in thread
From: Radu Toader @ 2026-11-05 20:02 UTC (permalink / raw)
To: peterz, mingo
Cc: juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall,
mgorman, vschneid, kprateek.nayak, tj, void, arighi, changwoo,
frederic, anna-maria, tglx, sched-ext, linux-kernel, Radu Toader
tick_irq_exit() skips tick_nohz_irq_exit() whenever the CPU's run queue
has tasks on it, even though the CPU is sitting in the idle loop. Under
sched_ext that is an ordinary steady state - a BPF scheduler holding a
runnable task back, e.g. a cgroup at its CPU limit - and with an
unstable sched_clock the CPU's clock is then never resynchronized on
the way out of idle, so the idle stretch is charged to the next task as
runtime.
Patch 1 adds scx_tickbug, an example scheduler that holds one tagged
task runnable on an idling CPU for a configurable stretch. It exists
because the in-tree example schedulers do reach that state but leave it
within microseconds, so nothing accumulates and the bug is invisible.
Patch 2 is the fix, one line of behaviour: ask is_idle_task(current)
instead of sched_core_idle_cpu().
The patches are independent in the files they touch, but patch 1 comes
first because without it nothing in this tree can produce the state
patch 2 is about.
Measurements
------------
Two kernels built from this tree, differing only in patch 2, booted in
turn on one 16-CPU x86_64 KVM guest with "no-kvmclock tsc=unstable".
Both are needed: tsc=unstable alone only marks the clocksource,
because mark_tsc_unstable() clears sched_clock stability only when
using_native_sched_clock(), which is false under kvm-clock.
Load: one thread spinning 10 ms in every 100 ms in a cgroup, pinned to
the CPU the scheduler holds it on. 20 s windows, three repetitions per
cell, arms interleaved. The figure is the cgroup's cpu.stat usage_usec
over the thread's own CLOCK_MONOTONIC measurement of its busy time,
which is an upper bound on the CPU it can have used, so correct is
<= 1.00:
hold (ms) without patch 2 with patch 2
7 1.32 0.964
13 1.21 0.963
23 2.00 0.963
37 1.69 0.964
53 1.33 0.964
control, fair class, no BPF scheduler loaded:
1.005 1.006
Nothing in the fixed kernel's figures varies with the hold, and none of
the unfixed kernel's is within 20% of correct. At the 23 ms hold the
matched pair is 0.087 CPU of real work charged as 0.173 unfixed against
0.084 fixed, with 173 and 172 releases respectively - the same work,
accounted twice over.
The unfixed kernel also understates how long it held the task, which is
the same bug from the other side: the scheduler measures the hold with
scx_bpf_now(), the sched_clock that is not being resynchronized. For a
23 ms configured hold it reported a 5.2 ms mean hold where the fixed
kernel reported 15.2 ms for the identical configuration. So the fixed
kernel accounts correctly across holds three times longer than the ones
the unfixed kernel gets wrong.
An earlier measurement, with an out-of-tree sched_ext scheduler that
caps how many threads of a cgroup run at once: one thread spinning in a
cgroup limited to 0.1 CPU in an 8-vCPU guest was charged 0.27 CPUs, and
four such threads 1.12 CPUs, while a sched_switch trace and the work
completed both showed 0.100. With nohz=off, idle=poll or a stable
sched_clock the three agree. That scheduler is not part of this series,
so that one cannot be reproduced from this tree; patch 1 is what makes
everything above reproducible.
What is not shown, and what was not done
----------------------------------------
No loss in /proc/stat. The sum of that CPU's fields 2 to 9 over the
window stayed within 0.6% of the window on both kernels, so in this
configuration the kcpustat_irq_exit() half of what tick_nohz_irq_exit()
does has no visible effect, unlike the forced idle case in 548796e2e70b.
A kprobe on tick_nohz_irq_exit() filtered to the idle task counted 998
calls per 20 s window on the held CPU without patch 2 against 1321 with
it, n=3 each, but those ranges overlap and the two kernels run the load
on different timings, so that bounds the mechanism rather than
measuring it.
The ttwu_pending widening described in patch 2 was reached by reading
the code, not measured on its own. The control arm above bounds any
effect on an ordinary workload (1.005 against 1.006) without isolating
that path.
There is no automated test, and I do not see how to write a useful one.
The wrong number only appears with an unstable sched_clock, which takes
a command line, so a selftest on a machine with a stable TSC would pass
on an unfixed kernel and prove nothing. scx_tickbug reproduces the
state and reports counters, but it asserts nothing and is not a
selftest.
All of the figures come from one 16-CPU x86_64 KVM guest on one host.
No other architecture, topology or guest clocksource was tried.
Open question
-------------
The Fixes: tag on patch 2 names f0e1a0643a59, the commit that made "the
idle task runs while nr_running > 0" reachable without
CONFIG_SCHED_CORE. 548796e2e70b is arguable instead, as the commit that
fixed this same gate for core scheduling with a predicate narrower than
the problem; and the ttwu_pending case predates both. Happy to retag.
Tooling
-------
The bug was found, and both patches, both changelogs and this cover
letter were written, by Claude Opus 5 (Claude Code), in a session
measuring cgroup CPU limit enforcement under sched_ext. The prompts
were about why a cgroup's measured CPU usage disagreed with a
sched_switch trace by a factor of 2.7; the model localized that to this
gate, wrote the fix and the reproducer, ran the measurements and wrote
the text. The content is tool-generated throughout, per
Documentation/process/generated-content.rst. I have reviewed it, I am
signing off on it under the DCO, and I can answer for it in review.
Radu Toader (2):
sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle
CPU
softirq: Treat an interrupted idle task as idle in tick_irq_exit()
include/linux/sched.h | 2 -
kernel/sched/syscalls.c | 12 -
kernel/softirq.c | 12 +-
tools/sched_ext/Makefile | 2 +-
tools/sched_ext/README.md | 13 ++
tools/sched_ext/scx_tickbug.bpf.c | 364 ++++++++++++++++++++++++++++++
tools/sched_ext/scx_tickbug.c | 166 ++++++++++++++
7 files changed, 554 insertions(+), 17 deletions(-)
create mode 100644 tools/sched_ext/scx_tickbug.bpf.c
create mode 100644 tools/sched_ext/scx_tickbug.c
base-commit: 05441d697f7f9a927264f4058cbbc6a03dfcac9d
--
2.43.0
^ permalink raw reply [flat|nested] 8+ messages in thread* [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU 2026-11-05 20:02 [PATCH 0/2] softirq: fix idle accounting for an interrupted idle task Radu Toader @ 2026-11-05 20:02 ` Radu Toader 0 siblings, 0 replies; 8+ messages in thread From: Radu Toader @ 2026-11-05 20:02 UTC (permalink / raw) To: peterz, mingo Cc: juri.lelli, vincent.guittot, dietmar.eggemann, rostedt, bsegall, mgorman, vschneid, kprateek.nayak, tj, void, arighi, changwoo, frederic, anna-maria, tglx, sched-ext, linux-kernel, Radu Toader The state behind the tick_irq_exit() gate - the idle task running on a CPU whose run queue is not empty - is reachable with the existing example schedulers but not holdable with them, which makes everything that depends on how long it lasts impossible to measure. enqueue_task_scx() raises rq->nr_running before it calls ops.enqueue(), so a scheduler that stashes the task in a map of its own leaves it runnable and accounted on that CPU with nothing for the CPU to pick. scx_central already does exactly that, and then calls scx_bpf_kick_cpu() immediately, so the window is microseconds wide. This scheduler is the same thing with the kick removed: a tagged task is parked on the target CPU's run queue and released only by a timer pinned to another CPU, so the window is as wide as -H says. Untagged tasks go through a shared DSQ and per-CPU kthreads keep their local DSQ and preemption, so the machine stays usable and the timer's softirq cannot be starved. Two things it has to get right, both of which cost a measurement round before they were found. The release timer must kick @target_cpu only when something is actually held: an unconditional SCX_KICK_PREEMPT lands on the task released a moment earlier and throws it off the CPU mid-run, whereupon ops.enqueue() holds it again, and the load then reports using half the CPU it asked for. And a tagged task that is already running goes straight back into the local DSQ instead of being held, so the hold only ever delays the start of a run - the state the gate under test mis-judges - and never interrupts one. nr_requeue counts the second case so a run can show whether it happened. It reports the mean and worst hold it actually achieved, which is the independent variable of any experiment using it and is not otherwise observable from userspace. Do not use a hold that divides the load's period: with a 100 ms spinner, holds of 5/10/20 ms phase-lock and the task is only ever held for microseconds. Tooling: written by Claude Opus 5 (Claude Code) while measuring what the tick_irq_exit() idle gate changes. All of this patch is tool-generated. Signed-off-by: Radu Toader <radu.m.toader@gmail.com> --- tools/sched_ext/Makefile | 2 +- tools/sched_ext/README.md | 13 ++ tools/sched_ext/scx_tickbug.bpf.c | 364 ++++++++++++++++++++++++++++++ tools/sched_ext/scx_tickbug.c | 166 ++++++++++++++ 4 files changed, 544 insertions(+), 1 deletion(-) create mode 100644 tools/sched_ext/scx_tickbug.bpf.c create mode 100644 tools/sched_ext/scx_tickbug.c diff --git a/tools/sched_ext/Makefile b/tools/sched_ext/Makefile index 70d2503b6b33..02e1500bf402 100644 --- a/tools/sched_ext/Makefile +++ b/tools/sched_ext/Makefile @@ -191,7 +191,7 @@ $(INCLUDE_DIR)/%.bpf.skel.h: $(SCXOBJ_DIR)/%.bpf.o $(INCLUDE_DIR)/vmlinux.h $(BP SCX_COMMON_DEPS := include/scx/common.h include/scx/user_exit_info.h | $(BINDIR) -c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_flatcg scx_userland scx_pair scx_sdt +c-sched-targets = scx_simple scx_cpu0 scx_qmap scx_central scx_tickbug scx_flatcg scx_userland scx_pair scx_sdt $(addprefix $(BINDIR)/,$(c-sched-targets)): \ $(BINDIR)/%: \ diff --git a/tools/sched_ext/README.md b/tools/sched_ext/README.md index 0ee5a3d997e5..4addc7c2ed23 100644 --- a/tools/sched_ext/README.md +++ b/tools/sched_ext/README.md @@ -185,6 +185,19 @@ where this could be particularly useful is running VMs, where running with infinite slices and no timer ticks allows the VM to avoid unnecessary expensive vmexits. +## scx_tickbug + +A scheduler whose only job is to keep one task runnable on a CPU that is in the +idle loop, for a length of time given on the command line. That state - the +idle task running while the run queue is not empty - is reachable by several of +the schedulers here, but none of them holds it long enough to observe what +depends on it. Tasks named "spin" are parked on the target CPU's run queue and +released only by a periodic timer; everything else runs through a shared DSQ so +the machine stays usable. + +This is a test scheduler, not a policy. It exists so that the idle-time +bookkeeping skipped by an interrupt taken in that state can be measured. + ## scx_flatcg A flattened cgroup hierarchy scheduler. This scheduler implements hierarchical diff --git a/tools/sched_ext/scx_tickbug.bpf.c b/tools/sched_ext/scx_tickbug.bpf.c new file mode 100644 index 000000000000..e6a6d627f042 --- /dev/null +++ b/tools/sched_ext/scx_tickbug.bpf.c @@ -0,0 +1,364 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * scx_tickbug: keep a task runnable on a CPU that is in the idle loop. + * + * This scheduler exists to hold one state for a controllable length of time: + * the idle task running on a CPU whose run queue is not empty. + * + * enqueue_task_scx() raises rq->nr_running before it calls ops.enqueue(), so a + * BPF scheduler that stashes the task somewhere of its own - here a BPF queue + * map - leaves it runnable and accounted on that CPU with nothing for the CPU + * to pick. The CPU enters the idle loop and stays there. In that state + * idle_cpu() is false, because idle_rq() tests rq->nr_running, while + * is_idle_task(current) is true. + * + * tick_irq_exit() used to ask idle_cpu(), so every interrupt taken in that + * idle loop skipped tick_nohz_irq_exit(). Each skip leaves TS_FLAG_IDLE_ACTIVE + * clear, and the next exit from the idle loop then also skips + * sched_clock_idle_wakeup_event(), so with an unstable sched_clock the CPU's + * clock is never resynchronized: the task picked next starts with a stale + * exec_start and the next tick charges it the whole idle stretch. + * + * The in-tree example schedulers can reach this state but not hold it. + * scx_central stashes a task in a BPF queue exactly like this, then + * immediately calls scx_bpf_kick_cpu(), so the window is microseconds wide and + * nothing measurable accumulates. Here the only thing that releases a held + * task is a periodic timer, so the window is hold_ns wide and can be swept. + * + * Only tasks named by @tag_comm are held; everything else runs through a + * shared DSQ so the machine stays usable while the test runs. + * + * Copyright (c) 2026 Radu Toader + */ +#include <scx/common.bpf.h> + +char _license[] SEC("license") = "GPL"; + +enum { + SHARED_DSQ = 0, + MS_TO_NS = 1000LLU * 1000, +}; + +/* CPU whose run queue holds the tagged task while the CPU idles. */ +const volatile s32 target_cpu; +/* CPU the release timer is pinned to. Must not be @target_cpu. */ +const volatile s32 timer_cpu = 1; +/* How long a tagged task is held before it is allowed to run. */ +const volatile u64 hold_ns = 10 * MS_TO_NS; +const volatile u64 slice_ns; +const volatile u32 nr_cpu_ids = 1; /* !0 for veristat, set during init */ + +bool timer_pinned = true; +bool timer_started; + +/* + * Set by the release timer, consumed by ops.dispatch() on @target_cpu. Without + * it ops.dispatch() would hand the held task straight back out, because the + * core calls ops.dispatch() whenever the CPU is about to go idle. + */ +bool release_now; + +u64 nr_enq, nr_held, nr_released, nr_timers; +u64 nr_passthru, nr_locals, nr_lost, nr_other_cpu, nr_overflow, nr_requeue; +/* + * How many tagged tasks are held right now. The release timer only kicks when + * this is non-zero: a kick with nothing held would preempt whatever is running + * on @target_cpu, and since that is normally the task just released, the task + * would lose most of its CPU to its own release mechanism. The first version of + * this scheduler did exactly that and reported half the usage it should. + */ +u64 nr_held_now; +/* Proof that the hold actually happened, and how wide it was. */ +u64 held_at, total_held_ns, max_held_ns; + +UEI_DEFINE(uei); + +struct { + __uint(type, BPF_MAP_TYPE_QUEUE); + __uint(max_entries, 1024); + __type(value, s32); +} hold_q SEC(".maps"); + +struct tickbug_timer { + struct bpf_timer timer; +}; + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(max_entries, 1); + __type(key, u32); + __type(value, struct tickbug_timer); +} release_timer SEC(".maps"); + +/* + * The load generator is called "spin". Compare 5 bytes so the terminating NUL + * has to match too and a longer name starting with "spin" is not held. + */ +static bool is_tagged(struct task_struct *p) +{ + return !bpf_strncmp(p->comm, 5, "spin"); +} + +s32 BPF_STRUCT_OPS(tickbug_select_cpu, struct task_struct *p, + s32 prev_cpu, u64 wake_flags) +{ + if (is_tagged(p)) + return target_cpu; + return prev_cpu; +} + +void BPF_STRUCT_OPS(tickbug_enqueue, struct task_struct *p, u64 enq_flags) +{ + s32 pid = p->pid; + + __sync_fetch_and_add(&nr_enq, 1); + + /* + * Per-CPU kthreads go to the head of their own CPU's local DSQ with + * preemption. The release timer runs from a softirq, so if a kthread + * such as ksoftirqd were starved behind a user task the held task + * would never be released. + */ + if ((p->flags & PF_KTHREAD) && p->nr_cpus_allowed == 1) { + __sync_fetch_and_add(&nr_locals, 1); + scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, slice_ns, + enq_flags | SCX_ENQ_PREEMPT); + return; + } + + if (is_tagged(p)) { + if (scx_bpf_task_cpu(p) != target_cpu) { + /* + * ops.select_cpu() is only a hint and is not called on + * every path. Counted rather than forced: a run with a + * non-zero count here did not test what it meant to. + */ + __sync_fetch_and_add(&nr_other_cpu, 1); + } else if (scx_bpf_task_running(p)) { + /* + * Already on the CPU and merely re-enqueued, e.g. after + * a kthread preempted it. Holding it here would take + * CPU away from work already in progress, which is not + * the state under test: the hold belongs at the start + * of a run, not in the middle of one. Put it straight + * back so it carries on. + */ + __sync_fetch_and_add(&nr_requeue, 1); + scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, slice_ns, enq_flags); + return; + } else if (bpf_map_push_elem(&hold_q, &pid, 0)) { + __sync_fetch_and_add(&nr_overflow, 1); + } else { + /* + * This is the whole scheduler. The task is already in + * target_cpu's rq->nr_running; parking its pid here + * and deliberately not kicking the CPU leaves it in + * the idle loop with a runnable task queued. + */ + held_at = scx_bpf_now() ?: 1; + __sync_fetch_and_add(&nr_held, 1); + __sync_fetch_and_add(&nr_held_now, 1); + return; + } + } + + __sync_fetch_and_add(&nr_passthru, 1); + scx_bpf_dsq_insert(p, SHARED_DSQ, slice_ns, enq_flags); +} + +/* Let one held task run on the CPU we are dispatching for. */ +static bool release_one(void) +{ + struct task_struct *p; + s32 pid; + + bpf_repeat(BPF_MAX_LOOPS) { + u64 now, at; + + if (bpf_map_pop_elem(&hold_q, &pid)) + return false; + + p = bpf_task_from_pid(pid); + if (!p) { + __sync_fetch_and_add(&nr_lost, 1); + __sync_fetch_and_sub(&nr_held_now, 1); + continue; + } + + /* + * Affinity may have changed while the task sat in the queue. + * Such a task goes to the shared DSQ instead of being pinned + * to a CPU it is no longer allowed on. + */ + if (!bpf_cpumask_test_cpu(target_cpu, p->cpus_ptr) || + is_migration_disabled(p)) { + scx_bpf_dsq_insert(p, SHARED_DSQ, slice_ns, 0); + bpf_task_release(p); + __sync_fetch_and_sub(&nr_held_now, 1); + if (!scx_bpf_dispatch_nr_slots()) + return false; + continue; + } + + scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, slice_ns, 0); + bpf_task_release(p); + __sync_fetch_and_sub(&nr_held_now, 1); + + at = held_at; + now = scx_bpf_now(); + if (at && now > at) { + u64 d = now - at; + + __sync_fetch_and_add(&total_held_ns, d); + if (d > max_held_ns) + max_held_ns = d; + } + held_at = 0; + + __sync_fetch_and_add(&nr_released, 1); + return true; + } + + return false; +} + +static void start_release_timer(void) +{ + struct bpf_timer *timer; + u32 key = 0; + int ret; + + if (likely(timer_started)) + return; + + timer = bpf_map_lookup_elem(&release_timer, &key); + if (!timer) { + scx_bpf_error("failed to look up the release timer"); + return; + } + + ret = bpf_timer_start(timer, hold_ns, BPF_F_TIMER_CPU_PIN); + if (ret == -EINVAL) { + /* BPF_F_TIMER_CPU_PIN needs >= 6.7 */ + timer_pinned = false; + ret = bpf_timer_start(timer, hold_ns, 0); + } + if (ret) { + scx_bpf_error("bpf_timer_start failed (%d)", ret); + return; + } + + timer_started = true; +} + +void BPF_STRUCT_OPS(tickbug_dispatch, s32 cpu, struct task_struct *prev) +{ + /* + * Arm the timer from the CPU it must be pinned to. ops.init() runs in + * whatever context loaded the scheduler, which is the wrong CPU. + */ + if (cpu == timer_cpu) + start_release_timer(); + + if (cpu == target_cpu && release_now) { + release_now = false; + if (release_one()) + return; + } + + scx_bpf_dsq_move_to_local(SHARED_DSQ, 0); +} + +static int release_timerfn(void *map, int *key, struct bpf_timer *timer) +{ + s32 curr_cpu = bpf_get_smp_processor_id(); + int ret; + + if (timer_pinned && curr_cpu == target_cpu) { + scx_bpf_error("release timer ran on the target CPU %d", curr_cpu); + return 0; + } + + /* + * Nothing held means @target_cpu is either idle with an empty run + * queue or busy with the task released last time. Kicking in either + * case is at best pointless and at worst preempts that task. + */ + if (!nr_held_now) + goto rearm; + + /* + * Allow one held task through and make @target_cpu notice. + * SCX_KICK_PREEMPT sends a reschedule IPI, which does not go through + * irq_enter() and so does not run tick_irq_exit() itself: it only ends + * the idle stretch whose bookkeeping the mis-gated interrupts dropped. + */ + release_now = true; + scx_bpf_kick_cpu(target_cpu, SCX_KICK_PREEMPT); + +rearm: + + __sync_fetch_and_add(&nr_timers, 1); + + ret = bpf_timer_start(timer, hold_ns, + timer_pinned ? BPF_F_TIMER_CPU_PIN : 0); + if (ret) + scx_bpf_error("bpf_timer_start failed (%d)", ret); + return 0; +} + +int BPF_STRUCT_OPS_SLEEPABLE(tickbug_init) +{ + struct bpf_timer *timer; + u32 key = 0; + int ret; + + if (target_cpu == timer_cpu) { + scx_bpf_error("target and timer CPU must differ (both %d)", + target_cpu); + return -EINVAL; + } + + ret = scx_bpf_create_dsq(SHARED_DSQ, -1); + if (ret) { + scx_bpf_error("scx_bpf_create_dsq failed (%d)", ret); + return ret; + } + + timer = bpf_map_lookup_elem(&release_timer, &key); + if (!timer) + return -ESRCH; + + bpf_timer_init(timer, &release_timer, CLOCK_MONOTONIC); + bpf_timer_set_callback(timer, release_timerfn); + + /* Get ops.dispatch() to run on @timer_cpu so it arms the timer. */ + scx_bpf_kick_cpu(timer_cpu, 0); + + return 0; +} + +void BPF_STRUCT_OPS(tickbug_exit, struct scx_exit_info *ei) +{ + UEI_RECORD(uei, ei); +} + +SCX_OPS_DEFINE(tickbug_ops, + /* + * The last runnable task on a CPU has to come through + * ops.enqueue() too, otherwise the tagged task would simply + * keep running on @target_cpu and never be held. + */ + .flags = SCX_OPS_ENQ_LAST, + + .select_cpu = (void *)tickbug_select_cpu, + .enqueue = (void *)tickbug_enqueue, + .dispatch = (void *)tickbug_dispatch, + .init = (void *)tickbug_init, + .exit = (void *)tickbug_exit, + /* + * A held task is runnable and not running, which is what the + * watchdog looks for. Keep the timeout well above any hold. + */ + .timeout_ms = 5000U, + .name = "tickbug"); diff --git a/tools/sched_ext/scx_tickbug.c b/tools/sched_ext/scx_tickbug.c new file mode 100644 index 000000000000..8acca5c1ff6a --- /dev/null +++ b/tools/sched_ext/scx_tickbug.c @@ -0,0 +1,166 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * Copyright (c) 2026 Radu Toader + */ +#define _GNU_SOURCE +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <inttypes.h> +#include <signal.h> +#include <assert.h> +#include <libgen.h> +#include <bpf/bpf.h> +#include <scx/common.h> +#include "scx_tickbug.bpf.skel.h" + +const char help_fmt[] = +"Hold a task runnable on a CPU that is in the idle loop.\n" +"\n" +"Tasks named \"spin\" are queued on the target CPU's run queue and left\n" +"there, so the CPU idles with a runnable task queued, until a periodic\n" +"timer releases one. Every other task runs through a shared DSQ.\n" +"\n" +"See the top-level comment in .bpf.c for more details.\n" +"\n" +"Usage: %s [-c CPU] [-t CPU] [-H HOLD_MS] [-s SLICE_US] [-v]\n" +"\n" +" -c CPU Target CPU, the one that idles with a task queued (default: 0)\n" +" -t CPU CPU the release timer is pinned to (default: 1)\n" +" -H HOLD_MS How long a task is held before release (default: 10)\n" +" -s SLICE_US Override slice duration\n" +" -v Print libbpf debug messages\n" +" -h Display this help and exit\n"; + +static bool verbose; +static volatile int exit_req; + +static int libbpf_print_fn(enum libbpf_print_level level, const char *format, va_list args) +{ + if (level == LIBBPF_DEBUG && !verbose) + return 0; + return vfprintf(stderr, format, args); +} + +static void sigint_handler(int dummy) +{ + exit_req = 1; +} + +int main(int argc, char **argv) +{ + struct scx_tickbug *skel; + struct bpf_link *link; + __u64 seq = 0, ecode; + __u32 nr_cpu_ids; + __s32 opt; + + libbpf_set_print(libbpf_print_fn); + signal(SIGINT, sigint_handler); + signal(SIGTERM, sigint_handler); +restart: + optind = 1; + skel = SCX_OPS_OPEN(tickbug_ops, scx_tickbug); + + nr_cpu_ids = libbpf_num_possible_cpus(); + assert(nr_cpu_ids > 0); + assert(nr_cpu_ids <= INT32_MAX); + + skel->rodata->nr_cpu_ids = nr_cpu_ids; + skel->rodata->target_cpu = 0; + skel->rodata->timer_cpu = 1; + skel->rodata->hold_ns = 10ULL * 1000 * 1000; + skel->rodata->slice_ns = __COMPAT_ENUM_OR_ZERO("scx_public_consts", "SCX_SLICE_DFL"); + + while ((opt = getopt(argc, argv, "c:t:H:s:vh")) != -1) { + switch (opt) { + case 'c': + case 't': { + unsigned long cpu = strtoul(optarg, NULL, 0); + + if (cpu >= nr_cpu_ids) { + fprintf(stderr, "invalid CPU id %lu (%u max)\n", + cpu, nr_cpu_ids - 1); + scx_tickbug__destroy(skel); + return 1; + } + if (opt == 'c') + skel->rodata->target_cpu = (s32)cpu; + else + skel->rodata->timer_cpu = (s32)cpu; + break; + } + case 'H': + skel->rodata->hold_ns = strtoull(optarg, NULL, 0) * 1000 * 1000; + break; + case 's': + skel->rodata->slice_ns = strtoull(optarg, NULL, 0) * 1000; + break; + case 'v': + verbose = true; + break; + default: + fprintf(stderr, help_fmt, basename(argv[0])); + return opt != 'h'; + } + } + + if (skel->rodata->target_cpu == skel->rodata->timer_cpu) { + fprintf(stderr, "the target CPU and the timer CPU must differ (both %d)\n", + skel->rodata->target_cpu); + scx_tickbug__destroy(skel); + return 1; + } + if (!skel->rodata->hold_ns) { + fprintf(stderr, "a hold of 0 would not hold anything\n"); + scx_tickbug__destroy(skel); + return 1; + } + + SCX_OPS_LOAD(skel, tickbug_ops, scx_tickbug, uei); + link = SCX_OPS_ATTACH(skel, tickbug_ops, scx_tickbug); + + printf("target_cpu=%d timer_cpu=%d hold_ms=%llu slice_us=%llu\n", + skel->rodata->target_cpu, skel->rodata->timer_cpu, + (unsigned long long)(skel->rodata->hold_ns / 1000000), + (unsigned long long)(skel->rodata->slice_ns / 1000)); + + if (!skel->data->timer_pinned) + printf("WARNING: BPF_F_TIMER_CPU_PIN unavailable, release timer is not pinned\n"); + + while (!exit_req && !UEI_EXITED(skel, uei)) { + __u64 released = skel->bss->nr_released; + + printf("[SEQ %llu]\n", seq++); + printf("enq :%10" PRIu64 " held:%10" PRIu64 + " released:%10" PRIu64 " timers:%10" PRIu64 "\n", + skel->bss->nr_enq, skel->bss->nr_held, + skel->bss->nr_released, skel->bss->nr_timers); + printf("pass :%10" PRIu64 " local:%10" PRIu64 + " lost:%10" PRIu64 " othrcpu:%10" PRIu64 + " overflow:%10" PRIu64 " requeue:%10" PRIu64 + " now:%10" PRIu64 "\n", + skel->bss->nr_passthru, skel->bss->nr_locals, + skel->bss->nr_lost, skel->bss->nr_other_cpu, + skel->bss->nr_overflow, skel->bss->nr_requeue, + skel->bss->nr_held_now); + /* + * The mean and the worst hold are the independent variable of + * the whole experiment: without them the run proves nothing. + */ + printf("hold_us: mean %8llu max %8llu\n", + (unsigned long long)(released ? + (skel->bss->total_held_ns / released) / 1000 : 0), + (unsigned long long)(skel->bss->max_held_ns / 1000)); + fflush(stdout); + sleep(1); + } + + bpf_link__destroy(link); + ecode = UEI_REPORT(skel, uei); + scx_tickbug__destroy(skel); + + if (!exit_req && UEI_ECODE_RESTART(ecode)) + goto restart; + return 0; +} -- 2.43.0 ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2026-11-06 20:10 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2026-11-06 9:43 [PATCH 0/2] softirq: fix idle accounting for an interrupted idle task Radu Toader 2026-11-06 9:43 ` [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU Radu Toader 2026-11-06 16:59 ` Tejun Heo 2026-11-06 20:10 ` bot+bpf-ci 2026-11-06 9:43 ` [PATCH 2/2] softirq: Treat an interrupted idle task as idle in tick_irq_exit() Radu Toader 2026-11-06 10:23 ` Peter Zijlstra 2026-11-06 19:55 ` bot+bpf-ci -- strict thread matches above, loose matches on Subject: below -- 2026-11-05 20:02 [PATCH 0/2] softirq: fix idle accounting for an interrupted idle task Radu Toader 2026-11-05 20:02 ` [PATCH 1/2] sched_ext: Add scx_tickbug, a scheduler that holds a task on an idle CPU Radu Toader
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®