This commit introduces a new timeout backend using a
Pugh skip list, which allows for O(log N) insertion
and removal of timeouts. The skip list maintains
a same-tick firing order and has no capacity
limit, making it suitable for systems with many
concurrent timeouts. The implementation includes
necessary Kconfig options and updates to the timeout
management code to support this new backend.
Signed-off-by: Dhruv Menon <dhruvmenon1104@gmail.com>
The idle path asks this for the time until the next wakeup, and gets a
tick count that never says "there is nothing to wake up for": an empty
timeout list is reported as the capped announce budget, exactly like a
deadline further out than can be programmed in one step. The power
management code cannot then tell the two apart, so it arms the timer in
both cases and a system with sloppy idle enabled keeps waking up for
nothing.
Make the same decision reprogram_next() makes. With
CONFIG_SYSTEM_CLOCK_SLOPPY_IDLE allowing the uptime to drift, an empty
list is reported as K_TICKS_FOREVER; anything else is a wait, whether a
real deadline or the synthetic one that keeps the announce range
covered. Without sloppy idle the empty case stays a wait, so the timer
remains armed and timekeeping is unaffected.
The return type becomes unsigned to match the tick type used throughout
the timer interface. The conversion at the only caller, in the idle
path, is value preserving in both directions: every wait is capped at
SYS_CLOCK_MAX_WAIT, which is INT32_MAX, and K_TICKS_FOREVER is the same
value read either way. Nothing outside the kernel sees the change; the
power management API keeps its signed tick counts.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
An empty timeout list normally still gets the driver a wakeup request.
That is a synthetic timeout: nothing is waiting for it, it is there to
keep the announce baseline moving so uptime stays correct.
CONFIG_SYSTEM_CLOCK_SLOPPY_IDLE is the permission to skip it, which is
why an empty list only becomes visible to a driver when that option is
set, and today it becomes visible as a tick value the driver has to
recognise rather than as a condition of its own.
Add a weak sys_clock_no_timeout() hook, called in place of
sys_clock_set_timeout() when the list is empty and sloppy idle allows the
uptime to drift. Its default asks sys_clock_set_timeout() for UINT32_MAX
ticks, which is what K_TICKS_FOREVER is in the unsigned tick domain this
interface now uses, so an out-of-tree driver that has not migrated still
sees the "no deadline" value it always did. What gets deprecated is the
special meaning, not the call.
next_timeout() no longer decides sloppy idle, so its empty-list and
far-timeout arms collapse into one capped budget. The far-timeout arm no
longer stops a tick short of the cap either: it only did so to stay
distinguishable from the empty case, which now travels out of band.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Header file include/zephyr/sys_clock.h is deprecated and will be removed
someday. Update the whole file tree to include zephyr/sys/clock.h
straight instead of zephyr/sys_clock.h.
This change was made running the sed shell command below:
$ sed -i 's/zephyr\/sys_clock\.h/zephyr\/sys\/clock\.h/' \
`grep -rsl "zephyr/sys_clock\.h" kernel/`
Signed-off-by: Etienne Carriere <etienne.carriere@st.com>
With low-power idle handoff now going through sys_clock_idle_enter(),
nothing passes idle == true to sys_clock_set_timeout() any more, so the
argument is dead. Drop it: sys_clock_set_timeout(uint32_t ticks) now
means exactly "program the next tick, N ticks out", nothing else.
This updates the prototype, the weak default, every in-tree timer driver
definition (including the out-of-tree-style board timer under boards/),
and the core call sites. For the five drivers with low-power behaviour
this only removes the now-unused idle argument that the previous change
left on set_timeout(); the handling itself stays in their
sys_clock_idle_enter().
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
The "no timeout pending, stop the clock" decision under
CONFIG_SYSTEM_CLOCK_SLOPPY_IDLE was expressed by next_timeout()
returning SYS_CLOCK_MAX_WAIT verbatim as a magic sentinel, which every
timer driver then had to recognise. Move the decision into the core and
give it an explicit, resumable interface.
Add a weak sys_clock_unused() hook (no-op default): the kernel calls it
when the timeout list is empty and sloppy idle allows uptime to drift,
in place of programming a wait. A driver may override it to actively
halt its counter; one that does not simply stops being reprogrammed and
quiesces on its own, so sloppy idle now works for every driver. Resume
is the next sys_clock_set_timeout(), exactly as before; the core keeps
no paused state.
next_timeout() no longer special-cases sloppy idle, so its empty-list
and far-timeout arms collapse to the same capped budget and
SYS_CLOCK_MAX_WAIT loses its sentinel meaning. The decision lives in
reprogram_next(), used only at the two sites where the list can drain
(abort, end of announce); the add path always has a pending timeout and
calls sys_clock_set_timeout() directly.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Add a single-level bucketed delta list as a fourth selectable timeout
backend: a simpler relative of the timer wheel that keeps the wheel's
O(1) near-future insertion without its second tier, sift/defer
machinery, or tickless-idle penalty.
Timeouts expiring within the next CONFIG_TIMEOUT_BUCKET_LISTS ticks go
into a per-tick bucket list (O(1) insert and remove), tracked by an
occupancy bitmap so "ticks until next expiry" is O(1). Everything
beyond goes into one overflow list sorted by absolute expiry (O(n)
insert, O(1) remove, no delta fix-up). As curr_tick crosses the bucket
window, overflow entries that have come within range migrate into
buckets.
Like the other backends it is a single implementation header
(kernel/timeout_bucket.h) included only by timeout.c. Two properties
distinguish it from the other non-default backends, both confirmed by
running the full kernel timer/context/common suites with the backend
forced on (qemu_x86, x86_64, cortex_a53 SMP, riscv64):
- It fits the generic next_gap/advance/pop_due announce loop -- no
backend-owned announce. Migration is on demand against the actual
next event, so an idle CPU with a distant timeout sleeps straight
to it: it passes tests/kernel/context cpu_idle / timer_interrupts,
which the wheel fails (the wheel wakes at least every 32 ticks).
- Same-tick firing order stays FIFO (bucket and overflow inserts
append; migration preserves order), so tests/kernel/common's
timeout_order passes, unlike the min-heap.
The per-node representation is the delta list's node + dticks with no
extra field: a bucket entry stores its bucket index (< BUCKET_LISTS) in
dticks, an overflow entry its absolute expiry (>= BUCKET_LISTS); the
ranges never overlap, so it shares the dlist per-node helpers. Absolute
expiry needs 64-bit ticks, so the backend depends on TIMEOUT_64BIT. It
inherits the shared z_add_timeout round-up and the inflight_timeout
synchronization like the other backends. EXPERIMENTAL.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Add a hierarchical timer wheel as a third selectable timeout backend.
Timeouts are bucketed by expiry distance: one list per tick for the
next 32 ticks ("soon"), one list per 32-tick band for the next ~1024
("later"), and a sorted overflow list ("distant"). Insertion and
removal are O(1) for the common near-future case; every 32 ticks the
announce path sifts the current "later" band into "soon" and refills
it from "distant". This scales well when many short-lived timeouts are
pending.
Unlike the dlist and min-heap backends, the wheel does not fit the
generic next_gap/advance/pop_due announce primitives: its per-tick
advance is a bitmap scan that jumps over empty ticks, and its sift is
a time-driven event tied to no single timeout. Rather than contort
that (already subtle) state machine, the wheel uses the backend-owned
announce escape hatch: it defines _TIMEOUT_BACKEND_OWNS_ANNOUNCE and
implements z_timeout_q_announce(), which sys_clock_announce_locked()
calls in place of the generic loop.
Like the other backends the wheel is a single implementation header
(kernel/timeout_wheel.h) included only by timeout.c, so its state, its
operations and that announce loop reach the shared state (curr_tick,
announce_remaining, inflight_timeout) directly; nothing extra needs
exposing. The SMP re-entry guard, announcing_cpu and the reprogram
remain in timeout.c. The wheel fires handlers through the same
inflight_timeout dance, so the post-#109977 abort/in-flight
synchronization works unchanged, and it carries no per-node
ANNOUNCING/ABORTED sentinels.
struct _timeout grows a wheel-only flags field (which wheel tier a
timeout occupies), gated by CONFIG_TIMEOUT_BACKEND_WHEEL so the dlist
and heap builds are unaffected.
The backend is EXPERIMENTAL. Two known limitations, inherent to the
wheel algorithm (not the abstraction):
- No same-tick firing-order guarantee (sifted timeouts are
prepended), so the timeout_order test does not apply.
- next_timeout() never exceeds 32 ticks because a sift is always
pending, so the wheel wakes a tickless-idle CPU at least every 32
ticks. This fails tests that assert zero spurious idle wakeups
(tests/kernel/context cpu_idle / timer_interrupts) and is a power
regression versus the dlist and heap backends.
Verified the timeout-functional suites (timer_api, timeout,
timepoints, sleep, sched/deadline) pass with the wheel on qemu_x86,
x86_64, cortex_a53 SMP and riscv64; dlist and heap remain unaffected.
The timer-wheel data structure, bucketing scheme and sift algorithm
are the work of Peter Mitsis (PR #108339), re-homed here behind the
timeout backend interface.
Co-authored-by: Peter Mitsis <peter.mitsis@intel.com>
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Add a binary min-heap as a selectable timeout backend alongside the
sorted delta list, plugging into the backend abstraction rather than
forking timeout.c. Pending timeouts are kept in a min-heap keyed on
absolute expiry tick; insertion and arbitrary removal are O(log n),
which scales better than the delta list's O(n) insertion when many
timeouts are pending.
The backend is a new kernel/timeout_minheap.h: the heap instance (a
min_heap_ref from the previous commit), its comparator and the
z_timeout_q_*() operations, included only by timeout.c (after curr_tick)
so the whole backend stays private to that translation unit. struct
_timeout gains the abs_ticks + heap_handle representation, selected by
Kconfig (the delta list's node + dticks is the #else), with the common
fn pointer kept as a shared trailing member; the per-node helpers in
timeout_q.h grow a matching min-heap variant. The kernel shell thread
dump prints the backend's raw scheduling field (dticks or abs_ticks)
under #ifdef.
Because the shared z_add_timeout() already applies the post-#107452
conditional tick round-up, the heap inherits it: the backend's insert
simply stores abs_ticks = curr_tick + dticks. Likewise in-flight
handler synchronization (PR #109977) lives in timeout.c, so the heap
node carries no ANNOUNCING/ABORTED sentinels -- "not queued" is just
heap_handle.idx == 0.
The backend is EXPERIMENTAL, depends on TIMEOUT_64BIT (absolute ticks
need 64-bit precision), and uses a fixed-capacity heap
(CONFIG_TIMEOUT_HEAP_MAX_ENTRIES) whose overflow is a fatal error.
The min-heap algorithm, struct fields, Kconfig and capacity model are
derived from Sayooj K Karun's min-heap timeout subsystem (#106013),
reworked here to fit the pluggable backend and the current in-tree
in-flight-handler synchronization.
Co-authored-by: Sayooj K Karun <sayooj@aerlync.com>
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
The timeout queue data structure and the front-end logic in timeout.c
are entangled through first()/next()/remove_timeout()/next_timeout()
and the open-coded insertion and announce loops. This makes it hard to
offer alternative queue implementations (min-heap, timer wheel) without
either forking timeout.c or threading #ifdefs through its trickiest
code, the announce path in particular.
Introduce a backend interface and move the sorted delta list behind it.
The split mirrors how the queue is actually used:
- The per-node helpers z_init_timeout() / z_is_inactive_timeout()
operate on a single struct _timeout and are needed tree-wide
(timer.c, work.c, poll.c, ...), so they live in timeout_q.h and
depend only on struct _timeout's fields.
- The queue itself (its instance and the z_timeout_q_*() operations)
is used only by timeout.c, so it becomes a backend implementation
header (kernel/timeout_list.h) that timeout.c includes directly,
after its shared state. The header is private to that translation
unit; no other file sees the queue or its instance, so the instance
is plain static and needs no extern.
timeout.c keeps all shared state (curr_tick, announce_remaining,
announcing_cpu, inflight_timeout, timeout_lock), the add/abort/query API
translation, the in-flight handler synchronization, and a single
announce loop shared by every future backend.
The backend exposes:
- z_timeout_q_insert / _remove add and arbitrary remove
- z_timeout_q_remainder / _next_timeout queries
- z_timeout_q_next_gap / _advance / _pop_due announce-loop primitives
The announce loop is recast in terms of the last three primitives:
find the gap to the next event, advance the backend (and curr_tick) to
it, then drain whatever is due. For the delta list this is behaviorally
identical to the previous open-coded loop: the residual advance reuses
the same head->dticks fixup, same-tick ties drain via successive
pop_due() calls, and announce_remaining is still decremented per tick
group while announcing_cpu carries the announcing state.
So the front end no longer reaches into the queue representation, three
checks are made backend-neutral: z_add_timeout()'s assert and
z_timer_expiration_handler()'s "restarted?" test now use
z_is_inactive_timeout() instead of sys_dnode_is_linked(), and
Z_TIMER_INITIALIZER zero-inits the queue fields (.fn only) rather than
naming .node/.dticks. struct _timeout is otherwise untouched; no
sentinel or per-node state changes.
The Kconfig backend choice and the divergent node layouts are deferred
until a second backend lands; with only the delta list present they
would be churn with no benefit.
Verified no behavioral change: tests/kernel/timer/{timer_api,timeout},
tests/kernel/common, and tests/kernel/sleep pass on qemu_x86,
qemu_x86_64, qemu_cortex_a53 (SMP) and qemu_riscv64 (exercising the
SMP announcing_cpu path and 64-bit dticks).
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
z_try_abort_timeout() can only set ret to -EAGAIN inside a
CONFIG_SMP-gated branch, so the trailing arch_spin_relax() call is
dead code on non-SMP builds. Optimized builds drop it, but a
coverage build (-O0) keeps the call and the linker then fails with
an undefined reference to arch_spin_relax: its weak definition
lives in idle.c, which is only compiled when CONFIG_MULTITHREADING
is set, so a no-multithreading + coverage build has no definition.
Wrap the check with IS_ENABLED(CONFIG_SMP) so the front end folds
the branch (and the arch_spin_relax reference) away even at -O0.
This is behavior-preserving since ret is never -EAGAIN without SMP.
The issue also triggers when building with llvm.
Signed-off-by: Anas Nashif <anas.nashif@intel.com>
sys_clock_announce() reports ticks elapsed since the previous announce. The
quantity that must stay in range is therefore the distance of the next
timeout from that announce, not its distance from "now" as next_timeout()
previously bounded. When an early timeout is repeatedly replaced by a later
one, announces are deferred and that distance can exceed the range even
though each set_timeout() delay was in range, which every driver has had to
defend against on its own.
Cap it in the core instead: SYS_CLOCK_MAX_WAIT becomes UINT32_MAX/2 (the
clamp, with the upper half of the range left as slack for a late announce)
and next_timeout() clamps the inter-announce distance to it. Drivers no
longer need to clamp for the announce range and only have to honour their
own cycle-count limits.
The core no longer emits K_TICKS_FOREVER; the reported delay is always
finite, saturating at SYS_CLOCK_MAX_WAIT. Drivers that stop the timer
entirely when idle now key off ticks == SYS_CLOCK_MAX_WAIT under
CONFIG_SYSTEM_CLOCK_SLOPPY_IDLE.
z_get_next_timeout_expiry() still reports to the idle and PM paths as a
signed int32_t. It keeps its K_TICKS_FOREVER default and adopts the
next_timeout() value only when that fits, so the unsigned cap can never
surface there as a negative number.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
The sys_clock_set_timeout(), sys_clock_announce() and
sys_clock_announce_locked() interfaces carry a number of ticks to be
scheduled or announced. Those ticks have no negative meaning, so a signed
argument is both wasteful and error prone: it invites incorrect handling in
drivers and it halves the range that sys_clock_announce() can represent.
Switch the tick argument of these interfaces, along with the internal
announce_remaining accounting, from int32_t to uint32_t. This is a
mechanical change: driver bodies perform plain arithmetic on the value and
are unaffected by the signedness, and the kernel never passes a negative
tick count. The freed sign bit doubles the representable announce range,
which a later change will use to move the announce range limit out of the
drivers and into the core.
One config is not strictly neutral: under CONFIG_TIMEOUT_64BIT,
K_TICKS_FOREVER is a 64-bit value that an unsigned 32-bit argument can no
longer compare equal to, so the K_TICKS_FOREVER tests in drivers stop
matching there. K_TICKS_FOREVER is a k_ticks_t concept and has no business
in this tick count interface; a follow-up removes it from the driver side
entirely, which closes this gap.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
The only reader was z_is_aborted_thread_timeout() in kernel/sleep.c,
used to distinguish a normal timeout-driven wakeup from one caused by
k_wakeup(). That distinction can be made entirely from the time
remaining: a normal wakeup leaves left_ticks <= 0, while an early
k_wakeup() leaves a positive remainder. The signed_left > 0 check
that already follows handles both cases correctly. The
z_is_aborted_thread_timeout() check was an early-return optimization
that the time computation makes redundant.
Drop the early-return in z_tick_sleep(), remove z_is_aborted_timeout(),
z_is_aborted_thread_timeout(), and the TIMEOUT_DTICKS_ABORTED macro.
Stop writing dticks = ABORTED in z_try_abort_timeout()'s linked-removal
path; the same-CPU IRQ branch is simplified to a flat -EINVAL fall-
through (the comment is moved to the cross-CPU/-EAGAIN side which is
the only case the caller needs to distinguish).
After this commit, dticks is purely a queue-management delta; there
are no more in-band sentinel values.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
With every caller now using z_try_abort_timeout() and every handler
relying on subsystem-local wake-ownership flags (queue->finished,
K_WORK_DELAYED_BIT, poller.is_polling, killed/pended_on for threads)
rather than the dticks-cancel check, the in-band cancel mechanism is
dead code. Remove it:
- z_abort_timeout(): no callers; remove the function definition
in kernel/timeout.c and the declaration in kernel/include/timeout_q.h.
- z_is_timeout_handler_canceled(): no callers (handlers no longer
bail on dticks); remove.
- TIMEOUT_DTICKS_ANNOUNCING: nothing reads it; remove the macro and
the corresponding t->dticks = ANNOUNCING write in
sys_clock_announce_locked()'s dispatch loop.
TIMEOUT_DTICKS_ABORTED stays. z_is_aborted_timeout() (used by
kernel/sleep.c via z_is_aborted_thread_timeout to distinguish a
k_wakeup'd thread from one that timed out) reads it, and
z_try_abort_timeout() still writes it on the linked-removal and
the same-CPU IRQ best-effort paths.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
When z_try_abort_timeout() finds the target timeout already popped
from the queue and in flight (its handler dispatching), the abort
cannot remove anything from the queue. The handler is about to run
(or is running) the timeout's callback; the aborter needs a way to
tell it "you were aborted, skip your side effects". main carried that
signal in the per-timeout dticks=ABORTED sentinel, which any CPU
could write under timeout_lock and the handler checked at entry via
z_is_timeout_handler_canceled(). Later commits in this series remove
the dticks-cancel mechanism, so the signal needs a new home.
Encode it in the low bit of the file-local inflight_timeout pointer
(struct _timeout is pointer-aligned, so bit 0 is free):
inflight_timeout == NULL no handler in flight
inflight_timeout == t handler in flight, not superseded
inflight_timeout == t | 1 handler in flight, superseded
z_try_abort_timeout() sets the bit whenever the target is the
in-flight timeout -- on the announcing CPU (same-CPU IRQ that
preempted the dispatch, or a stop after a re-arm) and on another CPU
racing the handler.
A handler with non-idempotent side effects (currently only k_timer's
expiry_fn) checks z_timeout_inflight_superseded() at entry and bails
if set. Idempotent handlers (z_thread_timeout, work, poll, ...)
tolerate the race and don't need the check.
The bit is a best-effort signal, not a barrier: an aborter that sets
it after the handler has passed its check has no effect (the handler
already committed), exactly as the dticks sentinel behaved on main.
The -EAGAIN return for the cross-CPU case is a separate mechanism,
used only by callers that must wait for the handler to fully complete
(e.g. before freeing the timeout's storage); they spin, while
best-effort callers ignore -EAGAIN and rely on the bit.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Add an `inflight_timeout` pointer in the timeout subsystem, set by
sys_clock_announce_locked() under timeout_lock before a handler is
dispatched and cleared after the handler returns. The single-announcer
SMP invariant (only one CPU is in the dispatch loop at a time) means a
single global pointer suffices, mirroring announcing_cpu.
Add a new abort function z_try_abort_timeout() that uses this pointer
to detect "popped from the queue but handler not yet finished" without
relying on the in-band dticks == ANNOUNCING sentinel that survives
across the timeout's storage being freed only by coincidence.
The new function returns -EAGAIN when a handler is in flight on
another CPU, signalling that the caller must drop any outer lock the
handler may need and retry. A short arch_spin_relax() is performed
before -EAGAIN is returned so callers don't need to add their own
back-off in the retry path. inflight_timeout itself is kept private
to the timeout subsystem; callers only ever see the return value.
This commit introduces the infrastructure but migrates no callers.
The existing z_abort_timeout() and TIMEOUT_DTICKS_ANNOUNCING-based
cancellation in handlers continue to work; the dispatch loop sets
both inflight_timeout and ANNOUNCING so the two paths coexist while
callers are migrated one module at a time.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
The "+ announce_remaining" added in commit 2ec65238d6 ("kernel:
timeout: make in-announce check CPU-aware") forced elapsed() to push
an 8-byte stack frame, as the compiler can no longer tail-call into
sys_clock_elapsed(). On UP, announce_remaining is always 0 when
this_cpu_announcing() is false, so the add is gratuitous there.
Gate it on CONFIG_SMP: with CONFIG_SMP=n the compiler folds the
addition away and restores the tail call.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Several pieces of state in kernel/timeout.c are read by code paths on
both the announcing CPU and other CPUs: announce_remaining, the
"in-announce" lock that prevents parallel firing on SMP, and
elapsed()/the +1 round-up in z_add_timeout(). Originally all of these
were keyed off announce_remaining != 0, which conflates two distinct
roles -- a remaining-ticks counter and a we-are-announcing flag --
and breaks down on SMP and across same-tick groups.
Symptom 1 (issue #106317): on SMP, while CPU A is announcing, threads
running on CPU B see announce_remaining != 0 and incorrectly take the
in-announce branch -- elapsed() returns 0 so curr_tick + elapsed()
goes backwards relative to a reading taken before the announce
started, and a slice rearm or k_timer_start() coming from CPU B fires
one tick early because the +1 round-up is suppressed even though CPU B
is partway through a tick. The same condition was the root cause of
the test_slice_reset failure on fvp_base_revc_2xaem/v8a/smp/ns and
/a320 once the timer accounting cleanup in #107452 stopped masking it.
Fix: distinguish "this CPU is at a tick edge (announcing)" from "some
CPU is in the firing loop". Add announcing_cpu, set to the CPU id at
the top of sys_clock_announce_locked() and cleared at the bottom;
expose it via this_cpu_announcing() and any_cpu_announcing(). The
former drives elapsed()'s return-0 short-circuit and z_add_timeout()'s
+1 round-up suppression -- both correct only on the announcing CPU.
The latter drives the SMP early-return and z_add_timeout()'s
deferred sys_clock_set_timeout call -- both correct for any CPU
observing that an announce is in progress, and both robust to
announce_remaining hitting 0 mid-loop (which now becomes possible --
see symptom 2 below).
elapsed() on non-announcing CPUs now returns
sys_clock_elapsed() + announce_remaining. The driver bumped its
announced-cycles baseline to (curr_tick_initial + N) * CYC_PER_TICK
at ISR entry while the kernel has only advanced curr_tick by the
ticks already committed in the loop, so announce_remaining is the
residual that must be added to sys_clock_elapsed() to recover
T_real - curr_tick across the announce window. The new invariant is
curr_tick + announce_remaining + sys_clock_elapsed() == T_real
on every CPU at every point inside or outside the announce window.
Symptom 2: that invariant relies on curr_tick and announce_remaining
moving in lock-step. The original loop advanced curr_tick at the top
of each outer iteration but only decremented announce_remaining after
the handler returned, with the lock dropped around the handler. A
non-announcing CPU calling sys_clock_tick_get() during a handler
therefore observed curr_tick + announce_remaining one batch (dt) into
the future, breaking the invariant for the duration of the handler.
Fix: pair the updates so they happen under the same lock acquisition
before the handler runs:
curr_tick += t->dticks;
announce_remaining -= t->dticks;
Symptom 3: commit d157b3da19 ("kernel: timeout: keep announce_remaining
stable across same-tick group") kept announce_remaining > 0 across the
inner drain of a same-tick group so that (a) the SMP early-return
would still detect "another CPU is announcing" and (b) elapsed() in
same-tick handlers would still anchor to the firing tick. With the
lock-state role moved to announcing_cpu, neither property depends on
announce_remaining anymore: any_cpu_announcing() carries (a) and
this_cpu_announcing() carries (b), both throughout the loop on the
announcing CPU regardless of the budget. The inner drain do-while
loop is therefore no longer needed -- the outer loop's
t->dticks <= announce_remaining naturally accepts dticks == 0
follow-on timeouts even when announce_remaining has reached 0.
Fixes#106317
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Since commit 37717b229f ("sys: util: rename Z_MIN Z_MAX Z_CLAMP to min
max and clamp"), <zephyr/sys/util.h> unconditionally defines function-
like macros named `min`, `max`, and `clamp` in the global namespace (in
C mode). util.h gets pulled in transitively by very broad headers,
including the POSIX layer's <pthread.h>, so any third-party C code that
uses these names as ordinary identifiers (e.g. XNNPACK's static `clamp`
helper and its public `clamp` struct field) fails to build as soon as
<pthread.h> is included.
Following the approach used by Linux, move the lowercase `min`, `max`,
`min3`, `max3`, and `clamp` macros (and their helpers) into a new
<zephyr/sys/minmax.h> header that has to be included explicitly by
source files that want them. util.h keeps the uppercase MIN/MAX/CLAMP,
so most code is unaffected; only the (much smaller) set of files that
actually use the lowercase variants needs to pick up the new include.
Fixes#107853.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
z_add_timeout() has always added one tick to the incoming tick count,
as a conservative round-up so that a request issued partway through a
tick still waits for "at least N full ticks" before the fire. This
round-up is correct in the general case, but *wrong* when the call
happens from within sys_clock_announce_locked() -- i.e. from a timer
expiration callback running at the tick-processing boundary where
elapsed() already returns 0. In that context there is no fractional
tick to compensate for, and the round-up simply makes every scheduled
timeout one tick late.
Two in-tree callers were already compensating for this caller-side:
* The k_timer periodic reschedule path in z_timer_expiration_handler
always runs from inside sys_clock_announce_locked() and subtracted
1 from the period before calling z_add_timeout(). Under
CONFIG_TIMEOUT_64BIT, the same path additionally added +1 inside
K_TIMEOUT_ABS_TICKS() to undo a related round-down.
* z_time_slice_reset() armed the slice timer with K_TICKS(slice_size
- 1) so the resulting fire would land at exactly slice_size ticks.
This one is reachable from both thread context (the +1 cancels the
-1) and from announce context via update_cache() during a
ready-thread wakeup (the +1 isn't applied, leaving the slice short
by one tick). The latter is what actually trips
tests/kernel/tickless/tickless_concept on every platform once the
conditional below lands without dropping these workarounds.
All three are symptoms of the same root cause.
Handle it at the source: make the +1 conditional on announce_remaining
== 0. When scheduling from the timer ISR, we are already at a tick
boundary by construction, so no round-up is needed and periodic timers
now reschedule at exact period intervals without any caller-side
compensation. Drop the -1 in z_timer_expiration_handler's period
path, the +1 in its 64-bit absolute-reschedule companion, and the -1
in z_time_slice_reset(), since all three existed solely to paper over
this mismatch.
This change only affects timeouts scheduled from announce context
(periodic k_timers rescheduling themselves, callbacks starting new
timers, slice-timer rearm during ready-thread wakeup). All other
callers -- k_sleep(), z_abort_timeout(), initial k_timer_start() from
a thread, k_sched_time_slice_set() -- continue to use the +1 round-up.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
When sys_clock_announce_locked() processes a tick that has multiple
timeouts queued for it, the timeout queue stores the second and
subsequent ones with dticks == 0 (relative to the first). The original
loop fired each in turn and decremented announce_remaining at the
bottom of every iteration:
announce_remaining -= dt;
For the first timeout in a same-tick group, dt is the cumulative tick
delta that brought us to that tick. After that subtraction
announce_remaining can drop to zero, even though there are still
same-tick callbacks queued for the loop to fire. Each subsequent
same-tick callback then runs while announce_remaining == 0, which
breaks two invariants the rest of the kernel relies on:
* The SMP early-return at the top of sys_clock_announce_locked():
if (IS_ENABLED(CONFIG_SMP) && (announce_remaining != 0)) {
announce_remaining += ticks;
k_spin_unlock(&timeout_lock, key);
return;
}
is meant to detect that another CPU is already inside the loop and
fold the new ticks into the ongoing announce. The lock is released
around each callback, so during a same-tick callback another CPU
can grab the lock, see announce_remaining == 0, miss the early
return, set announce_remaining = ticks of its own, and start
walking the queue in parallel with the original announcer -- the
exact race the early return is supposed to prevent.
* The elapsed() helper:
return announce_remaining == 0 ? sys_clock_elapsed() : 0U;
is meant to return 0 for any z_add_timeout() / z_abort_timeout()
call that happens from inside a tick-processing callback, so that
timeouts scheduled from such a callback are anchored to the
currently-firing tick rather than to a fresh sys_clock_elapsed()
reading. With announce_remaining == 0 mid-loop, two callbacks on
the same tick observe inconsistent semantics: the first one (that
saw announce_remaining > 0) gets dticks anchored to the firing
tick, while subsequent ones (seeing 0) get dticks computed against
a fresh elapsed() reading and end up off by one tick. Two periodic
timers that happen to fire on the same tick will therefore
permanently drift apart by one tick going forward.
Restructure the loop so the announce_remaining decrement happens once
per tick rather than once per timeout: the outer while drives forward
across distinct ticks, and an inner do-while drains all timeouts
queued on the current tick before announce_remaining is updated.
announce_remaining now stays at its pre-tick value for the entire
same-tick group, which both the SMP early return and elapsed()
correctly observe as non-zero.
remove_timeout()'s dticks propagation is also unnecessary in this
loop because curr_tick is advanced by t->dticks before the timeout
is unlinked, which keeps the next item's stored dticks valid relative
to the new curr_tick. sys_dlist_remove() on its own is sufficient.
Loop structure suggested by Peter Mitsis.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Add sys_clock_is_locked(), the analog of z_spin_is_locked() for the
timer lock exposed via sys_clock_lock(). Use it to assert lock
ownership in sys_clock_set_timeout() and sys_clock_elapsed() of the
six timer drivers that were migrated to sys_clock_lock() and
consequently no longer acquire anything internally in those callbacks
(arm_arch_timer, riscv_machine_timer, xtensa_sys_timer, hpet,
apic_tsc, intel_adsp_timer).
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Move time-slice related declarations from ksched.h into the
dedicated kernel/include/timeslicing.h header.
Signed-off-by: Anas Nashif <anas.nashif@intel.com>
On SMP systems with tickless kernels, a race condition exists between
timer driver ISRs and the kernel's tick accounting. The driver updates
its hardware cycle baseline under a private lock, then calls
sys_clock_announce() which updates curr_tick under the separate
timeout_lock. In the gap between these two lock releases, any kernel
code calling sys_clock_elapsed() sees the new driver baseline but the
old curr_tick, producing inconsistent time values that can go backwards.
This affects every code path using the internal elapsed() helper:
uptime queries, timeout scheduling, timeout cancellation, remaining
time queries, and next-expiry calculations.
The root cause is two separate locks protecting state that must be
mutually consistent. Fix this by exposing the kernel's timeout_lock
to timer drivers via sys_clock_lock()/sys_clock_unlock(), and
providing sys_clock_announce_locked() which assumes the lock is
already held.
Timer drivers can now acquire the single lock, update their hardware
state, and announce ticks all under the same lock — eliminating the
race window entirely. The key is passed to sys_clock_announce_locked()
which consumes it (releasing the lock when it returns).
The existing sys_clock_announce() becomes a backward-compatible wrapper,
allowing incremental driver migration with no flag day.
Document that sys_clock_set_timeout(), sys_clock_elapsed(), and
sys_clock_idle_exit() are called by the kernel with the timer lock
held. Update the timer driver guide in clocks.rst accordingly.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
The routine sys_clock_announce() removes the timeout from the timeout
list and unlocks the timeout spinlock before invoking the timeout's
handler. This creates a window where another ISR (or a thread running
on another CPU) can abort or reuse the timeout before the handler
executes. When this happens, the timeout handler should bail early.
Use the dticks field to carry this state: set it to
TIMEOUT_DTICKS_ANNOUNCING after remove_timeout() (which needs
dticks = 0 to propagate remaining ticks) and before calling the
handler. In z_abort_timeout(), set TIMEOUT_DTICKS_ABORTED when the
timeout is either linked (existing behavior) or in the announcing
state (new). The z_add_timeout() path naturally overwrites dticks
with a real tick value, so re-use is also detected.
Provide z_is_timeout_handler_canceled() for handlers to check if
they should bail. This avoids adding a flags field to struct _timeout,
keeping the struct size unchanged.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
- Move the variable declaration and related code from kernel/timeout.c
to a new kernel/sys_clock_hw_cycles.c file. The motivation is that
both functions are part of the system clock frequency plumbing
(runtime query / update) and don’t naturally fit the responsibilities
of timeout.c, which is otherwise focused on timeout queue management
and tick announcement logic.
- Make sys_clock_hw_cycles_per_sec_runtime_get() (and its
z_impl_sys_clock_hw_cycles_per_sec_runtime_get() implementation)
visible under CONFIG_SYSTEM_CLOCK_HW_CYCLES_PER_SEC_RUNTIME_UPDATE
as well, not only under CONFIG_TIMER_READS_ITS_FREQUENCY_AT_RUNTIME.
This allows callers and time unit conversion helpers to retrieve the
current system timer frequency after runtime clock changes even when
the timer driver does not discover the rate by querying hardware.
Signed-off-by: Zhaoxiang Jin <Zhaoxiang.Jin_1@nxp.com>
Adds board overlays for Intel ADSP platforms to use
CONFIG_LLEXT_TYPE_ELF_RELOCATABLE instead of SHAREDLIB
as xt-clang cannot link shared libs for Xtensa, exports
symbols used by Intel ADSP with Xtensa toolchain, and
adds XTENSA MPU / MMU to "no memory protection" config file.
Signed-off-by: Lauren Murphy <lauren.murphy@intel.com>
arch_mem_coherent() is cache related so it is better to move it
under cache subsys. It is renamed to sys_cache_is_mem_coherent()
to reflect this change.
The only user of arch_mem_coherent() is Xtensa. However, it is
not an architecture feature. That's why it is moved to the cache
subsys.
Signed-off-by: Daniel Leung <daniel.leung@intel.com>
Replace all in-function instances of MIN/MAX/CLAMP with the single
evaluation version min/max/clamp.
There's probably no race conditions in these files, but the single
evaluation ones save a couple of instructions each so they should save
few code bytes and potentially perform better, so they should be
preferred in general.
Signed-off-by: Fabio Baltieri <fabiobaltieri@google.com>
Move MAX_WAIT define to the system timer header file
so system timer drivers can use this define.
Signed-off-by: Mahesh Mahadevan <mahesh.mahadevan@nxp.com>
Add return value to z_add_timeout. It returns system tick when timeout
will expire.
Signed-off-by: Krzysztof Chruściński <krzysztof.chruscinski@nordicsemi.no>
Accessing system timer registers can be costly and it shall be avoided
if possible. When thread is waken up in z_tick_sleep it may be because
timeout expired or because thread was waken up before sleeping period
passed.
Add function to detect if timeout is aborted (before it was expired).
Use it in the sleep function and avoid reading system ticks if timeout
was not aborted.
Signed-off-by: Krzysztof Chruściński <krzysztof.chruscinski@nordicsemi.no>
sys_clock_elapsed requires access to system clock register interface
which is often slow. When new relative timeout is added sys_clock_elapsed()
is called once to calculate delta ticks and then if that triggers setting
new timeout sys_clock_elapsed() is called again. This call is redundant
since everything happens under spin lock so it is better to reuse value
returned by the first call.
Signed-off-by: Krzysztof Chruściński <krzysztof.chruscinski@nordicsemi.no>
Convert z_clock_hw_cycles_per_sec to unsigned int to increase
supported frequency range.
Signed-off-by: Anisetti Avinash Krishna <anisetti.avinash.krishna@intel.com>
Introduces the Z_IS_TIMEOUT_RELATIVE() macro to help ensure that
checking for relative/absolute timeouts is consistent. Using this
macro also helps ensure that we get the correct behavior when using
32-bit timeouts (CONFIG_TIMEOUT_64BIT=n).
Signed-off-by: Peter Mitsis <peter.mitsis@intel.com>
Adds a note about the timeout_lock to aid future developers
in following the rules to help prevent deadlocks involving the
timeout and scheduler spinlocks.
Signed-off-by: Peter Mitsis <peter.mitsis@intel.com>
This ensures that the system clock is correctly updated when the first
timeout is aborted, preventing unexpected early wake-up by the system clock
programmed previously.
Signed-off-by: Dong Wang <dong.d.wang@intel.com>
Utilize a code spell-checking tool to scan for and correct spelling errors
in all files within the `kernel` directory.
Signed-off-by: Pisit Sawangvonganan <pisit@ndrsolution.com>
Namespaced the generated headers with `zephyr` to prevent
potential conflict with other headers.
Introduce a temporary Kconfig `LEGACY_GENERATED_INCLUDE_PATH`
that is enabled by default. This allows the developers to
continue the use of the old include paths for the time being
until it is deprecated and eventually removed. The Kconfig will
generate a build-time warning message, similar to the
`CONFIG_TIMER_RANDOM_GENERATOR`.
Updated the includes path of in-tree sources accordingly.
Most of the changes here are scripted, check the PR for more
info.
Signed-off-by: Yong Cong Sin <ycsin@meta.com>
update kernel timeout logic based on retrieve system timer clock
frequency at runtime or static way based on Kconfig
TIMER_READS_ITS_FREQUENCY_AT_RUNTIME
Signed-off-by: Najumon B.A <najumon.ba@intel.com>
Next timeout was set unconditionally at the end of sys_clock_announce.
However, if one of the current expired timeouts was setting a new
timeout which is the first to execute then system clock was configured
twice. Lets configure system clock only once in the isr at the and of
sys_clock_announce.
If timeouts are frequent this optimization can reduce CPU load. In
many cases setting the new sys_clock timeout is the most time
consuming operation in the sys_clock isr handler. As an example,
on the target I used setting new sys_clock timeout is taking 6 uS of
9 uS spent in the isr and it takes 16 uS with the redundant call.
Signed-off-by: Krzysztof Chruściński <krzysztof.chruscinski@nordicsemi.no>
Add a closing comment to the endif with the configuration
information to which the endif belongs too.
To make the code more clearer if the configs need adaptions.
Signed-off-by: Simon Hein <Shein@baumer.com>
This currently calls timeout_rem() then adds back the result of
elapsed() to cancel out the subtraction of another elapsed() call
within timeout_rem(). Better not to make any calls to elapsed() in
that case, especially given that elapsed() may incur hardware access
overhead through sys_clock_elapsed().
Let's move the elapsed() subtraction to the only user of timeout_rem()
that needs it and remove its invocation from the z_timeout_expires()
path entirely.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
- issue found with Ztest case of test_thread_timeout_remaining_expires
on Intel ISH platform when adjust CONFIG_SYS_CLOCK_TICKS_PER_SEC
to 10k.
- timeout_rem() return exact remaining ticks which is calibrated by
decrease elapsed(), while z_timeout_expires try to get expire ticks
to be timeout using current tick as base, so need get exact current
ticks by plus elasped().
Signed-off-by: Qipeng Zha <qipeng.zha@intel.com>
