scx_flow/rust/
topology.rs

1// SPDX-License-Identifier: GPL-2.0
2//! Topology view for the flow scheduler.
3//!
4//! Copyright (c) 2026 Galih Tama <galpt@v.recipes>
5
6//! Delegates host discovery to scx_utils::Topology with a sysfs
7//! fallback, then seeds the BPF view in two best-effort phases.
8//! Phase one writes the primary rows with sibling plus node, and phase
9//! two refreshes the LLC bitmaps for the start log. Either phase keeps
10//! the BPF defaults on fault with no trap and no hot-path use.
11//! Sibling assumes two-way SMT as in sibling_cpus, so a third thread
12//! stays single with all ones. Span holds online CPUs at init, so the
13//! seed matches the sysfs online list with no hotplug use.
14
15use scx_utils::Topology;
16
17/// CPU ids past this bound never seed, mirroring FLOW_MAX_CPUS.
18const CPU_BOUND: u32 = 1024;
19
20/// Node ids past this bound fold to zero, mirroring FLOW_MAX_NODES.
21const NODE_BOUND: u32 = 16;
22
23/// One topology row per CPU with sibling plus node.
24/// Sibling comes from the core view with all ones on fault, and node
25/// folds to zero on fault with a cap at sixteen. A Topology failure
26/// falls back to the sysfs lists with the same shape and no panic.
27pub fn topo_rows() -> Vec<(u32, u32, u32)> {
28    init_topology()
29}
30
31/// Build the seeded rows from the shared Topology view.
32/// Uses scx_utils::Topology as the source of truth with a sysfs
33/// fallback on fault, so large hosts fold to the machine queue with
34/// no panic and no extra scan on the hot paths. Span equals the online
35/// list at construction, sorted in rank order with the CPU plus node
36/// bounds, so the seed matches sysfs online with no extra view. Sibling
37/// follows sibling_cpus with two-way assumed, so extra threads on wider
38/// cores stay single with no extra scan.
39pub fn init_topology() -> Vec<(u32, u32, u32)> {
40    if let Ok(topo) = Topology::new() {
41        let sibs = topo.sibling_cpus();
42        let mut rows = Vec::new();
43        let mut online: Vec<u32> = topo.span.iter().map(|c| c as u32).collect();
44        online.sort_unstable();
45        for cpu in online {
46            if cpu >= CPU_BOUND {
47                continue;
48            }
49            let sib = sibs
50                .get(cpu as usize)
51                .copied()
52                .filter(|s| *s >= 0)
53                .map(|s| s as u32)
54                .filter(|s| *s != cpu)
55                .unwrap_or(u32::MAX);
56            let node = topo
57                .all_cpus
58                .get(&(cpu as usize))
59                .map(|c| c.node_id as u32)
60                .unwrap_or(0);
61            let node = if node < NODE_BOUND { node } else { 0 };
62            rows.push((cpu, sib, node));
63        }
64        if !rows.is_empty() {
65            return rows;
66        }
67    }
68    fallback_rows()
69}
70
71/// Primary bitmap text for the start log in rank order.
72/// Best effort with empty on fault, so a failed read never traps.
73pub fn write_primary_bitmap(rows: &[(u32, u32, u32)]) -> String {
74    let mut ids: Vec<u32> = rows.iter().map(|(cpu, _, _)| *cpu).collect();
75    ids.sort_unstable();
76    ids.iter()
77        .map(|c| c.to_string())
78        .collect::<Vec<_>>()
79        .join(",")
80}
81
82/// LLC bitmap texts for the start log, one entry per LLC.
83/// Best effort with empty on fault, so hosts without an LLC view log
84/// no bitmap with no trap and no hot-path use.
85pub fn write_llc_bitmaps() -> Vec<String> {
86    let topo = match Topology::new() {
87        Ok(t) => t,
88        Err(_) => return Vec::new(),
89    };
90    let mut out = Vec::new();
91    for llc in topo.all_llcs.values() {
92        let mut ids: Vec<usize> = llc.all_cpus.keys().copied().collect();
93        ids.sort_unstable();
94        let text = ids
95            .iter()
96            .map(|c| c.to_string())
97            .collect::<Vec<_>>()
98            .join(",");
99        out.push(text);
100    }
101    out.sort();
102    out
103}
104
105/// Short topology line for the start log.
106/// Shows cpus seeded with primary plus llcs counts, so the 4.8.14 start
107/// log carries primary plus llcs past the old cpus seeded line with no
108/// hot-path use.
109pub fn describe_topology(rows: &[(u32, u32, u32)]) -> String {
110    let primary = write_primary_bitmap(rows);
111    let llcs = write_llc_bitmaps();
112    if llcs.is_empty() {
113        format!("cpus={} seeded", rows.len())
114    } else {
115        format!(
116            "cpus={} seeded primary=[{}] llcs={}",
117            rows.len(),
118            primary,
119            llcs.len()
120        )
121    }
122}
123
124/// True when the CPU is the second thread of one core.
125/// Sibling holds all ones on single thread, so single thread stays
126/// false with no panic. A lower sibling marks the second thread, so
127/// only one card per core shows SMT with no extra sysfs use. Two-way
128/// assumed as in sibling_cpus, so a third thread on wider cores stays
129/// single by design with no extra kick and no non-x86 walk.
130pub fn is_smt_thread(cpu: u32, sib: u32) -> bool {
131    sib != u32::MAX && sib < cpu
132}
133
134/// Parse a kernel CPU list like 0-3 plus 5 into ids.
135/// Ranges clamp to the CPU bound before the walk, so a faulty list
136/// never loops the full u32 range. Ids past the bound never seed.
137pub fn parse_cpu_list(s: &str) -> Vec<u32> {
138    let mut out = Vec::new();
139    for part in s.split(',') {
140        let part = part.trim();
141        if part.is_empty() {
142            continue;
143        }
144        if let Some((a, b)) = part.split_once('-')
145            && let (Ok(lo), Ok(hi)) = (a.trim().parse::<u32>(), b.trim().parse::<u32>())
146        {
147            let hi = hi.min(CPU_BOUND - 1);
148            if lo <= hi {
149                for cpu in lo..=hi {
150                    out.push(cpu);
151                }
152            }
153            continue;
154        }
155        if let Ok(cpu) = part.parse::<u32>()
156            && cpu < CPU_BOUND
157        {
158            out.push(cpu);
159        }
160    }
161    out.sort_unstable();
162    out.dedup();
163    out
164}
165
166/// Read one kernel CPU list file into ids with empty on fault.
167pub fn read_cpu_list_file(path: &str) -> Vec<u32> {
168    std::fs::read_to_string(path)
169        .map(|s| parse_cpu_list(&s))
170        .unwrap_or_default()
171}
172
173/// Fallback rows from the sysfs lists with the same shape.
174/// Sibling reads the thread list with all ones on fault, and node
175/// reads the NUMA view with zero on fault and a cap at sixteen.
176fn fallback_rows() -> Vec<(u32, u32, u32)> {
177    let online = read_cpu_list_file("/sys/devices/system/cpu/online");
178    let mut rows = Vec::new();
179    for cpu in online {
180        let sib = thread_sibling(cpu).unwrap_or(u32::MAX);
181        let node = cpu_node(cpu).unwrap_or(0);
182        let node = if node < NODE_BOUND { node } else { 0 };
183        rows.push((cpu, sib, node));
184    }
185    rows
186}
187
188/// Thread sibling of one CPU with None on fault.
189fn thread_sibling(cpu: u32) -> Option<u32> {
190    let path = format!("/sys/devices/system/cpu/cpu{cpu}/topology/thread_siblings_list");
191    let ids = read_cpu_list_file(&path);
192    ids.into_iter().find(|id| *id != cpu)
193}
194
195/// Node of one CPU with None on fault.
196/// Reads the NUMA view through the per CPU node links with a fallback
197/// to the node cpulists, so package ids never shape placement.
198/// A missing link plus a missing cpulist means unknown, so the caller
199/// folds to zero with no panic.
200fn cpu_node(cpu: u32) -> Option<u32> {
201    let dir = format!("/sys/devices/system/cpu/cpu{cpu}");
202    if let Ok(entries) = std::fs::read_dir(&dir) {
203        for entry in entries.flatten() {
204            let name = entry.file_name().to_string_lossy().into_owned();
205            if let Some(suffix) = name.strip_prefix("node")
206                && !suffix.is_empty()
207                && let Ok(node) = suffix.parse::<u32>()
208            {
209                return Some(node);
210            }
211        }
212    }
213    node_from_cpulists(cpu)
214}
215
216/// Node of one CPU from the node cpulists with None on fault.
217/// Scans the online nodes and returns the first node whose cpulist
218/// holds the CPU, so hosts without per CPU links still seed.
219fn node_from_cpulists(cpu: u32) -> Option<u32> {
220    let ids = read_cpu_list_file("/sys/devices/system/node/online");
221    for node in ids {
222        let path = format!("/sys/devices/system/node/node{node}/cpulist");
223        let cpus = read_cpu_list_file(&path);
224        if cpus.contains(&cpu) {
225            return Some(node);
226        }
227    }
228    None
229}
230
231#[cfg(test)]
232mod tests {
233    use super::*;
234
235    #[test]
236    fn parses_ranges_and_singles() {
237        assert_eq!(parse_cpu_list("0-3"), vec![0, 1, 2, 3]);
238        assert_eq!(parse_cpu_list("0-1,3"), vec![0, 1, 3]);
239        assert_eq!(parse_cpu_list(""), Vec::<u32>::new());
240    }
241
242    #[test]
243    fn rows_cap_large_nodes() {
244        let node = 20u32;
245        let capped = if node < NODE_BOUND { node } else { 0 };
246        assert_eq!(capped, 0);
247    }
248
249    #[test]
250    fn clamps_ranges_and_ids_to_cpu_bound() {
251        let wide = parse_cpu_list("0-1100");
252        assert_eq!(wide.len(), 1024);
253        assert!(wide.iter().all(|c| *c < 1024));
254        assert_eq!(parse_cpu_list("1023-1100"), vec![1023]);
255        assert_eq!(parse_cpu_list("1100"), Vec::<u32>::new());
256        assert_eq!(parse_cpu_list("1100-1200"), Vec::<u32>::new());
257    }
258
259    #[test]
260    fn smt_marks_only_second_thread() {
261        assert!(!is_smt_thread(0, u32::MAX));
262        assert!(!is_smt_thread(0, 1));
263        assert!(is_smt_thread(1, 0));
264        assert!(!is_smt_thread(4, 5));
265        assert!(is_smt_thread(5, 4));
266        assert!(!is_smt_thread(7, u32::MAX));
267    }
268
269    #[test]
270    fn primary_bitmap_joins_rank_order() {
271        let rows = vec![(2, u32::MAX, 0), (0, u32::MAX, 0), (1, 0, 0)];
272        assert_eq!(write_primary_bitmap(&rows), "0,1,2");
273        assert_eq!(write_primary_bitmap(&[]), "");
274    }
275
276    #[test]
277    fn init_topology_rows_stay_in_bounds() {
278        let rows = init_topology();
279        assert_eq!(topo_rows(), rows);
280        assert!(
281            rows.iter()
282                .all(|(c, _, n)| *c < CPU_BOUND && *n < NODE_BOUND)
283        );
284        let mut ids: Vec<u32> = rows.iter().map(|(c, _, _)| *c).collect();
285        ids.sort_unstable();
286        ids.dedup();
287        assert_eq!(ids.len(), rows.len());
288    }
289}
scx_flow/rust/topology.rs

scx_flow/rust/
topology.rs
