nros_node/executor/
level_liveness.rs

1// Copyright (c) 2026, NEWSLab NTU.
2// SPDX-License-Identifier: Apache-2.0
3
4//! phase-509 P7 (RFC-0108 D8.1, D8.2) -- which level an executor is, and
5//! whether every level of the image is alive.
6//!
7//! A supervisor that owns a route per level, or feeds a hardware watchdog,
8//! needs two facts the executor alone knows:
9//!
10//! - **Identity.** Each executor runs one level ([`Executor::level`]): 0, the
11//!   most urgent, unless its runner set another ([`Executor::set_level`]).
12//!   The generated entry names each node's level at build time
13//!   (`NROS_ENTRY_LEVEL_OF_<node>` in `nros_priority_plan.h`) by the same
14//!   rule the runner applies: a level's index is its tier's urgency order
15//!   among the image's tiers (until phase-509 P9 a level is a tier).
16//! - **Liveness.** Every spin of an executor checks its level in here, with
17//!   the time ([`level_last_spin_us`]) and a spin count. The watchdog feed is
18//!   [`take_every_level_alive`]: `true` only when every level of the image
19//!   (`0..level_count()`) has checked in since the last `true`, which it
20//!   then clears. A level blocked behind a stuck callback stops checking in,
21//!   so the feed stops even while another level spins on (RFC-0108 D8.2).
22//!
23//! The registry is per image (a `static`): the levels are separate executors
24//! on separate threads until P9, and the watchdog is per image. Lock-free,
25//! 32-bit atomics only, so it works on a core without 64-bit atomics; a time
26//! is the low 32 bits of the executor's microsecond clock, so a consumer
27//! compares two of them with a wrapping difference (71 minutes of range).
28//!
29//! [`Executor::level`]: super::Executor::level
30//! [`Executor::set_level`]: super::Executor::set_level
31
32use portable_atomic::{AtomicU8, AtomicU32, Ordering::SeqCst};
33
34/// Levels one image can have: `CONFIG_NROS_EXECUTOR_MAX_LEVELS`'s upper end,
35/// one bit each in the check-in word.
36pub const MAX_LEVELS: usize = 32;
37
38/// The liveness of an image's levels.
39pub(crate) struct LevelRegistry {
40    count: AtomicU8,
41    checked_in: AtomicU32,
42    spins: [AtomicU32; MAX_LEVELS],
43    last_spin_us: [AtomicU32; MAX_LEVELS],
44}
45
46impl LevelRegistry {
47    pub(crate) const fn new() -> Self {
48        Self {
49            count: AtomicU8::new(1),
50            checked_in: AtomicU32::new(0),
51            spins: [const { AtomicU32::new(0) }; MAX_LEVELS],
52            last_spin_us: [const { AtomicU32::new(0) }; MAX_LEVELS],
53        }
54    }
55
56    fn all(&self) -> u32 {
57        let n = self.count.load(SeqCst) as u32;
58        if n >= 32 { u32::MAX } else { (1u32 << n) - 1 }
59    }
60
61    pub(crate) fn set_count(&self, n: u8) -> bool {
62        if n == 0 || n as usize > MAX_LEVELS {
63            return false;
64        }
65        self.count.store(n, SeqCst);
66        true
67    }
68
69    pub(crate) fn count(&self) -> u8 {
70        self.count.load(SeqCst)
71    }
72
73    /// Every spin of an executor calls this; a build with no executor (no
74    /// RMW seam) has no caller.
75    #[cfg_attr(not(any(has_rmw, test)), allow(dead_code))]
76    pub(crate) fn check_in(&self, level: u8, now_us: Option<u64>) {
77        let l = level as usize;
78        if l >= MAX_LEVELS {
79            return;
80        }
81        if let Some(t) = now_us {
82            self.last_spin_us[l].store(t as u32, SeqCst);
83        }
84        self.spins[l].fetch_add(1, SeqCst);
85        self.checked_in.fetch_or(1u32 << l, SeqCst);
86    }
87
88    pub(crate) fn spins(&self, level: u8) -> u32 {
89        self.spins.get(level as usize).map_or(0, |s| s.load(SeqCst))
90    }
91
92    pub(crate) fn last_spin_us(&self, level: u8) -> Option<u32> {
93        (self.spins(level) != 0).then(|| self.last_spin_us[level as usize].load(SeqCst))
94    }
95
96    pub(crate) fn every_alive(&self) -> bool {
97        let all = self.all();
98        self.checked_in.load(SeqCst) & all == all
99    }
100
101    pub(crate) fn take_every_alive(&self) -> bool {
102        let all = self.all();
103        loop {
104            let cur = self.checked_in.load(SeqCst);
105            if cur & all != all {
106                return false;
107            }
108            if self
109                .checked_in
110                .compare_exchange(cur, cur & !all, SeqCst, SeqCst)
111                .is_ok()
112            {
113                return true;
114            }
115        }
116    }
117}
118
119pub(crate) static LEVELS: LevelRegistry = LevelRegistry::new();
120
121/// The level of tier `index` of an image whose `n` tiers have the kernel
122/// priorities `priority_of(0..n)`: its urgency order, 0 the most urgent,
123/// equal priorities in array order. Until phase-509 P9 a level is a tier, so
124/// this is how a runner places each tier's executor
125/// ([`Executor::set_level`](super::Executor::set_level)). `nros codegen
126/// entry` writes `NROS_ENTRY_LEVEL_OF_<node>` by the same rule, over the same
127/// array. `None` when `index` is out of range.
128pub fn tier_level_by(
129    n: usize,
130    index: usize,
131    smaller_is_urgent: bool,
132    priority_of: impl Fn(usize) -> i64,
133) -> Option<u8> {
134    if index >= n {
135        return None;
136    }
137    let mine = priority_of(index);
138    let ahead = (0..n)
139        .filter(|&j| {
140            let q = priority_of(j);
141            (if smaller_is_urgent {
142                q < mine
143            } else {
144                q > mine
145            }) || (q == mine && j < index)
146        })
147        .count();
148    u8::try_from(ahead).ok()
149}
150
151/// [`tier_level_by`] over a slice of priorities.
152pub fn tier_level(priorities: &[i64], index: usize, smaller_is_urgent: bool) -> Option<u8> {
153    tier_level_by(priorities.len(), index, smaller_is_urgent, |i| {
154        priorities[i]
155    })
156}
157
158/// State how many levels the image runs (its runner does, once, before the
159/// levels spin). `false`, and nothing changed, for 0 or more than
160/// [`MAX_LEVELS`]. An image that never states it has one level.
161pub fn set_level_count(n: u8) -> bool {
162    LEVELS.set_count(n)
163}
164
165/// How many levels the image runs.
166pub fn level_count() -> u8 {
167    LEVELS.count()
168}
169
170/// How many times `level` has spun.
171pub fn level_spins(level: u8) -> u32 {
172    LEVELS.spins(level)
173}
174
175/// The low 32 bits of the executor clock, in microseconds, at `level`'s
176/// latest spin; `None` when it has not spun (or spins with no clock).
177pub fn level_last_spin_us(level: u8) -> Option<u32> {
178    LEVELS.last_spin_us(level)
179}
180
181/// Whether every level of the image has checked in since the last
182/// [`take_every_level_alive`] that returned `true`.
183pub fn every_level_alive() -> bool {
184    LEVELS.every_alive()
185}
186
187/// The watchdog feed: `true` when every level has checked in since the last
188/// `true`, and the check-ins are then cleared; `false`, and nothing cleared,
189/// while any level has not.
190pub fn take_every_level_alive() -> bool {
191    LEVELS.take_every_alive()
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197
198    /// The island's shape on Zephyr (smaller is urgent): a tier at 5 is level
199    /// 0 wherever it sits in the array; equal priorities keep array order;
200    /// the other direction inverts it.
201    #[test]
202    fn a_tiers_level_is_its_urgency_order() {
203        let p = [6, 5, 8, 6];
204        let levels: [Option<u8>; 4] = core::array::from_fn(|i| tier_level(&p, i, true));
205        assert_eq!(levels, [Some(1), Some(0), Some(3), Some(2)]);
206        let levels: [Option<u8>; 4] = core::array::from_fn(|i| tier_level(&p, i, false));
207        assert_eq!(levels, [Some(1), Some(3), Some(0), Some(2)]);
208        assert_eq!(tier_level(&p, 4, true), None);
209        assert_eq!(tier_level(&[5], 0, true), Some(0));
210    }
211
212    /// The aggregate is false while one level has not checked in, true once
213    /// every level has, and taking it starts a new round.
214    #[test]
215    fn every_level_must_check_in_before_the_feed() {
216        let r = LevelRegistry::new();
217        assert_eq!(r.count(), 1, "an image that states nothing has one level");
218        assert!(!r.set_count(0) && !r.set_count(33));
219        assert!(r.set_count(2));
220        assert_eq!(r.last_spin_us(1), None);
221        r.check_in(0, Some(1_000));
222        assert!(!r.every_alive(), "level 1 has not checked in");
223        assert!(!r.take_every_alive());
224        r.check_in(1, Some(1_250));
225        assert!(r.every_alive());
226        assert!(r.take_every_alive());
227        assert!(!r.every_alive(), "taken: a new round starts");
228        r.check_in(0, Some(2_000));
229        assert!(!r.take_every_alive(), "level 0 alone does not feed");
230        assert_eq!(r.last_spin_us(0), Some(2_000));
231        assert_eq!((r.spins(0), r.spins(1)), (2, 1));
232        // A clockless spin still checks in and counts.
233        r.check_in(1, None);
234        assert_eq!(r.last_spin_us(1), Some(1_250));
235        assert!(r.take_every_alive());
236    }
237}
nros_node/executor/level_liveness.rs

nros_node/executor/
level_liveness.rs
