Skip to main content

scx_utils/
topology.rs

1// Copyright (c) Meta Platforms, Inc. and affiliates.
2
3// This software may be used and distributed according to the terms of the
4// GNU General Public License version 2.
5
6//! # SCX Topology
7//!
8//! A crate that allows schedulers to inspect and model the host's topology, in
9//! service of creating scheduling domains.
10//!
11//! A Topology is comprised of one or more Node objects, which themselves are
12//! comprised hierarchically of LLC -> Core -> Cpu objects respectively:
13//!```rust,ignore
14//!                                   Topology
15//!                                       |
16//! o--------------------------------o   ...   o----------------o---------------o
17//! |         Node                   |         |         Node                   |
18//! | ID      0                      |         | ID      1                      |
19//! | LLCs    <id, Llc>              |         | LLCs    <id, Llc>              |
20//! | Span    0x00000fffff00000fffff |         | Span    0xfffff00000fffff00000 |
21//! o--------------------------------o         o--------------------------------o
22//!                 \
23//!                  --------------------
24//!                                      \
25//! o--------------------------------o   ...   o--------------------------------o
26//! |             Llc                |         |             Llc                |
27//! | ID     0                       |         | ID     1                       |
28//! | Cores  <id, Core>              |         | Cores  <id, Core>              |
29//! | Span   0x00000ffc0000000ffc00  |         | Span   0x00000003ff00000003ff  |
30//! o--------------------------------o         o----------------o---------------o
31//!                                                             /
32//!                                        ---------------------
33//!                                       /
34//! o--------------------------------o   ...   o--------------------------------o
35//! |              Core              |         |              Core              |
36//! | ID     0                       |         | ID     9                       |
37//! | Cpus   <id, Cpu>               |         | Cpus   <id, Cpu>               |
38//! | Span   0x00000000010000000001  |         | Span   0x00000002000000000200  |
39//! o--------------------------------o         o----------------o---------------o
40//!                                                             /
41//!                                        ---------------------
42//!                                       /
43//! o--------------------------------o   ...   o---------------------------------o
44//! |              Cpu               |         |               Cpu               |
45//! | ID       9                     |         | ID       49                     |
46//! | online   1                     |         | online   1                      |
47//! | min_freq 400000                |         | min_freq 400000                 |
48//! | max_freq 5881000               |         | min_freq 5881000                |
49//! o--------------------------------o         o---------------------------------o
50//!```
51//! Every object contains a Cpumask that spans all CPUs in that point in the
52//! topological hierarchy.
53//!
54//! Creating Topology
55//! -----------------
56//!
57//! Topology objects are created using the static new function:
58//!
59//!```  
60//!     use scx_utils::Topology;
61//!     let top = Topology::new().unwrap();
62//!```
63//!
64//! Querying Topology
65//! -----------------
66//!
67//! With a created Topology, you can query the topological hierarchy using the
68//! set of accessor functions defined below. All objects in the topological
69//! hierarchy are entirely read-only. If the host topology were to change (due
70//! to e.g. hotplug), a new Topology object should be created.
71
72use crate::Cpumask;
73use crate::compat::ROOT_PREFIX;
74use crate::cpumask::read_cpulist;
75use crate::misc::find_best_split_size;
76use crate::misc::read_file_byte;
77use crate::misc::read_file_usize_vec;
78use crate::misc::read_from_file;
79use anyhow::Result;
80use anyhow::bail;
81use glob::glob;
82use log::debug;
83use log::info;
84use log::warn;
85use sscanf::sscanf;
86use std::cmp::min;
87use std::collections::{BTreeMap, BTreeSet};
88use std::io::Write;
89use std::path::Path;
90use std::sync::{Arc, OnceLock};
91
92#[cfg(feature = "gpu-topology")]
93use crate::gpu::{Gpu, GpuIndex, create_gpus};
94
95lazy_static::lazy_static! {
96    /// The maximum possible number of CPU IDs in the system. As mentioned
97    /// above, this is different than the number of possible CPUs on the
98    /// system (though very seldom is). This number may differ from the
99    /// number of possible CPUs on the system when e.g. there are fully
100    /// disabled CPUs in the middle of the range of possible CPUs (i.e. CPUs
101    /// that may not be onlined).
102    pub static ref NR_CPU_IDS: usize = read_cpu_ids().unwrap().last().unwrap() + 1;
103
104    /// The number of possible CPUs that may be active on the system. Note
105    /// that this value is separate from the number of possible _CPU IDs_ in
106    /// the system, as there may be gaps in what CPUs are allowed to be
107    /// onlined. For example, some BIOS implementations may report spans of
108    /// disabled CPUs that may not be onlined, whose IDs are lower than the
109    /// IDs of other CPUs that may be onlined.
110    pub static ref NR_CPUS_POSSIBLE: usize = libbpf_rs::num_possible_cpus().unwrap();
111
112    /// The range to search for when finding the number of physical cores
113    /// assigned to a partition to split a large number of cores that share
114    /// an LLC domain. The suggested split for the cores isn't a function of
115    /// the underlying hardware's capability, but rather some sane number
116    /// to help determine the number of CPUs that share the same DSQ.
117    pub static ref NR_PARTITION_MIN_CORES: usize = 2;
118    pub static ref NR_PARTITION_MAX_CORES: usize = 8;
119}
120
121#[derive(Debug, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
122pub enum CoreType {
123    Big { turbo: bool },
124    Little,
125}
126
127#[derive(Debug, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
128pub enum Powermode {
129    Turbo,
130    Performance,
131    Powersave,
132    Any,
133}
134
135/// Return the list of CPU IDs matching the requested power mode.
136///
137/// Selects CPUs from the system topology based on [`Powermode`]:
138/// - [`Powermode::Turbo`]: only turbo-capable big cores
139/// - [`Powermode::Performance`]: all big cores
140/// - [`Powermode::Powersave`]: only little cores
141/// - [`Powermode::Any`]: all CPUs
142///
143/// Fall back to all CPUs if the requested core class is unavailable.
144pub fn get_primary_cpus(mode: Powermode) -> std::io::Result<Vec<usize>> {
145    let topo = Topology::new().unwrap();
146
147    let cpus: Vec<usize> = topo
148        .all_cores
149        .values()
150        .flat_map(|core| &core.cpus)
151        .filter_map(|(cpu_id, cpu)| match (&mode, &cpu.core_type) {
152            (Powermode::Turbo, CoreType::Big { turbo: true })
153            | (Powermode::Performance, CoreType::Big { .. })
154            | (Powermode::Powersave, CoreType::Little) => Some(*cpu_id),
155            (Powermode::Any, ..) => Some(*cpu_id),
156            _ => None,
157        })
158        .collect();
159
160    if cpus.is_empty() {
161        Ok(topo.all_cpus.keys().copied().collect())
162    } else {
163        Ok(cpus)
164    }
165}
166
167#[derive(Debug, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
168pub struct Cpu {
169    pub id: usize,
170    pub min_freq: usize,
171    pub max_freq: usize,
172    /// Base operational frqeuency. Only available on Intel Turbo Boost
173    /// CPUs. If not available, this will simply return maximum frequency.
174    pub base_freq: usize,
175    /// The best-effort guessing of cpu_capacity scaled to 1024.
176    pub cpu_capacity: usize,
177    /// The kernel scheduler's exact topology capacity, when exported by sysfs.
178    ///
179    /// Unlike [`Cpu::cpu_capacity`], this is never inferred from CPPC or CPU
180    /// frequency data. It is read only from cpuX/cpu_capacity and corresponds
181    /// to topology_get_cpu_scale().
182    pub kernel_cpu_capacity: Option<usize>,
183    pub smt_level: usize,
184    /// CPU idle resume latency
185    pub pm_qos_resume_latency_us: usize,
186    pub trans_lat_ns: usize,
187    pub l2_id: usize,
188    pub l3_id: usize,
189    /// Per-CPU cache size of all levels.
190    pub cache_size: usize,
191    pub core_type: CoreType,
192
193    /// Ancestor IDs.
194    pub core_id: usize,
195    pub llc_id: usize,
196    pub node_id: usize,
197    pub package_id: usize,
198    pub cluster_id: isize,
199}
200
201#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
202pub struct Core {
203    /// Monotonically increasing unique id
204    pub id: usize,
205    /// The sysfs value of core_id
206    pub kernel_id: usize,
207    pub cluster_id: isize,
208    pub cpus: BTreeMap<usize, Arc<Cpu>>,
209    /// Cpumask of all CPUs in this core.
210    pub span: Cpumask,
211    pub core_type: CoreType,
212
213    /// Ancestor IDs.
214    pub llc_id: usize,
215    pub node_id: usize,
216}
217
218#[derive(Debug, Clone)]
219pub struct Llc {
220    /// Monotonically increasing unique id
221    pub id: usize,
222    /// The kernel id of the llc
223    pub kernel_id: usize,
224    pub cores: BTreeMap<usize, Arc<Core>>,
225    /// Cpumask of all CPUs in this llc.
226    pub span: Cpumask,
227
228    /// Ancestor IDs.
229    pub node_id: usize,
230
231    /// Skip indices to access lower level members easily.
232    pub all_cpus: BTreeMap<usize, Arc<Cpu>>,
233}
234
235#[derive(Debug, Clone)]
236pub struct Node {
237    pub id: usize,
238    pub distance: Vec<usize>,
239    pub llcs: BTreeMap<usize, Arc<Llc>>,
240    /// Cpumask of all CPUs in this node.
241    pub span: Cpumask,
242
243    /// Skip indices to access lower level members easily.
244    pub all_cores: BTreeMap<usize, Arc<Core>>,
245    pub all_cpus: BTreeMap<usize, Arc<Cpu>>,
246
247    #[cfg(feature = "gpu-topology")]
248    pub gpus: BTreeMap<GpuIndex, Gpu>,
249}
250
251/// Source used to reconstruct scheduler-domain policy.
252#[derive(Debug, Clone, Copy, Eq, PartialEq)]
253pub enum SchedDomainSource {
254    /// Live scheduler-domain masks read from `/proc/schedstat`.
255    Schedstat,
256    /// Portable approximation built from sysfs topology.
257    Topology,
258}
259
260/// Scheduler-domain policy needed by userspace schedulers.
261#[derive(Debug, Clone, Copy, Eq, PartialEq)]
262pub struct SchedDomainInfo {
263    /// Size of the highest domain on which fork balancing is enabled.
264    pub fork_span: usize,
265    /// Size of the highest domain on which wake-affine is enabled.
266    pub wake_affine_span: usize,
267    /// Size of the lowest domain spanning every CPU-capacity class.
268    pub asym_capacity_span: usize,
269    /// Source used to reconstruct the domains.
270    pub source: SchedDomainSource,
271}
272
273const SCHEDSTAT_VERSION: usize = 17;
274const NUMA_RECLAIM_DISTANCE: usize = 30;
275
276#[derive(Debug)]
277pub struct Topology {
278    pub nodes: BTreeMap<usize, Node>,
279    /// Nodes without online CPUs, such as GPU or CXL memory nodes, that
280    /// split_cpuless_nodes() moved out of `nodes`.
281    pub cpuless_nodes: BTreeMap<usize, Node>,
282    /// Cpumask all CPUs in the system.
283    pub span: Cpumask,
284    /// True if SMT is enabled in the system, false otherwise.
285    pub smt_enabled: bool,
286
287    /// Skip indices to access lower level members easily.
288    pub all_llcs: BTreeMap<usize, Arc<Llc>>,
289    pub all_cores: BTreeMap<usize, Arc<Core>>,
290    pub all_cpus: BTreeMap<usize, Arc<Cpu>>,
291
292    // `/proc/schedstat` does not expose sched_domain::flags, but its masks are
293    // still useful when the statistics static key is disabled. Policy is
294    // reconstructed from these live masks and the same topology inputs used
295    // by the kernel. If schedstat is unavailable, topology masks are used.
296    sched_domains: OnceLock<Option<BTreeMap<usize, Vec<Cpumask>>>>,
297}
298
299impl Topology {
300    fn instantiate(span: Cpumask, mut nodes: BTreeMap<usize, Node>) -> Result<Self> {
301        // Build skip indices prefixed with all_ for easy lookups. As Arc
302        // objects can only be modified while there's only one reference,
303        // skip indices must be built from bottom to top.
304        let mut topo_llcs = BTreeMap::new();
305        let mut topo_cores = BTreeMap::new();
306        let mut topo_cpus = BTreeMap::new();
307
308        for node in nodes.values_mut() {
309            let mut node_cores = BTreeMap::new();
310            let mut node_cpus = BTreeMap::new();
311
312            for (&llc_id, llc) in node.llcs.iter_mut() {
313                let llc_mut = Arc::get_mut(llc).unwrap();
314                let mut llc_cpus = BTreeMap::new();
315
316                for (&core_id, core) in llc_mut.cores.iter_mut() {
317                    let core_mut = Arc::get_mut(core).unwrap();
318                    let smt_level = core_mut.cpus.len();
319
320                    for (&cpu_id, cpu) in core_mut.cpus.iter_mut() {
321                        let cpu_mut = Arc::get_mut(cpu).unwrap();
322                        cpu_mut.smt_level = smt_level;
323
324                        if topo_cpus
325                            .insert(cpu_id, cpu.clone())
326                            .or(node_cpus.insert(cpu_id, cpu.clone()))
327                            .or(llc_cpus.insert(cpu_id, cpu.clone()))
328                            .is_some()
329                        {
330                            bail!("Duplicate CPU ID {}", cpu_id);
331                        }
332                    }
333
334                    // Note that in some weird architectures, core ids can be
335                    // duplicated in different LLC domains.
336                    topo_cores
337                        .insert(core_id, core.clone())
338                        .or(node_cores.insert(core_id, core.clone()));
339                }
340
341                llc_mut.all_cpus = llc_cpus;
342
343                if topo_llcs.insert(llc_id, llc.clone()).is_some() {
344                    bail!("Duplicate LLC ID {}", llc_id);
345                }
346            }
347
348            node.all_cores = node_cores;
349            node.all_cpus = node_cpus;
350        }
351
352        Ok(Topology {
353            nodes,
354            cpuless_nodes: BTreeMap::new(),
355            span,
356            smt_enabled: is_smt_active().unwrap_or(false),
357            all_llcs: topo_llcs,
358            all_cores: topo_cores,
359            all_cpus: topo_cpus,
360            sched_domains: OnceLock::new(),
361        })
362    }
363
364    fn sched_domains(&self) -> Option<&BTreeMap<usize, Vec<Cpumask>>> {
365        self.sched_domains
366            .get_or_init(|| {
367                let path = format!("{}/proc/schedstat", *ROOT_PREFIX);
368                match std::fs::read_to_string(&path).and_then(|data| {
369                    parse_schedstat(&data).map_err(|err| std::io::Error::other(err.to_string()))
370                }) {
371                    Ok(domains)
372                        if self
373                            .all_cpus
374                            .keys()
375                            .all(|cpu| domains.get(cpu).is_some_and(|spans| !spans.is_empty())) =>
376                    {
377                        Some(domains)
378                    }
379                    Ok(_) => {
380                        debug!("{path} has incomplete scheduler domains; using topology fallback");
381                        None
382                    }
383                    Err(err) => {
384                        debug!("cannot use {path}: {err}; using topology fallback");
385                        None
386                    }
387                }
388            })
389            .as_ref()
390    }
391
392    /// Build a complete host Topology
393    pub fn new() -> Result<Topology> {
394        Self::with_virt_llcs(None)
395    }
396
397    pub fn with_virt_llcs(nr_cores_per_vllc: Option<(usize, usize)>) -> Result<Topology> {
398        let span = cpus_online()?;
399        let mut topo_ctx = TopoCtx::new();
400
401        // If the kernel is compiled with CONFIG_NUMA, then build a topology
402        // from the NUMA hierarchy in sysfs. Otherwise, just make a single
403        // default node of ID 0 which contains all cores.
404        let path = format!("{}/sys/devices/system/node", *ROOT_PREFIX);
405        let nodes = if Path::new(&path).exists() {
406            create_numa_nodes(&span, &mut topo_ctx, nr_cores_per_vllc)?
407        } else {
408            create_default_node(&span, &mut topo_ctx, false, nr_cores_per_vllc)?
409        };
410
411        Self::instantiate(span, nodes)
412    }
413
414    pub fn with_flattened_llc_node() -> Result<Topology> {
415        let span = cpus_online()?;
416        let mut topo_ctx = TopoCtx::new();
417        let nodes = create_default_node(&span, &mut topo_ctx, true, None)?;
418        Self::instantiate(span, nodes)
419    }
420
421    /// Build a topology with configuration from CLI arguments.
422    /// This method integrates with the TopologyArgs from the cli module to
423    /// create a topology based on command line parameters.
424    pub fn with_args(topology_args: &crate::cli::TopologyArgs) -> Result<Topology> {
425        // Validate the CLI arguments first
426        topology_args.validate()?;
427
428        // Get the virtual LLC configuration
429        let nr_cores_per_vllc = topology_args.get_nr_cores_per_vllc();
430
431        // Build topology with the specified configuration
432        Self::with_virt_llcs(nr_cores_per_vllc)
433    }
434
435    /// Move nodes without online CPUs from `nodes` to `cpuless_nodes`, so
436    /// that schedulers sizing per-node state from `nodes` only see nodes
437    /// that can run tasks.
438    pub fn split_cpuless_nodes(&mut self) {
439        let (cpu_nodes, cpuless_nodes) = std::mem::take(&mut self.nodes)
440            .into_iter()
441            .partition(|(_, node)| !node.all_cpus.is_empty());
442        self.nodes = cpu_nodes;
443        self.cpuless_nodes.extend(cpuless_nodes);
444    }
445
446    /// Get a vec of all GPUs on the hosts.
447    #[cfg(feature = "gpu-topology")]
448    pub fn gpus(&self) -> BTreeMap<GpuIndex, &Gpu> {
449        let mut gpus = BTreeMap::new();
450        for node in self.nodes.values() {
451            for (idx, gpu) in &node.gpus {
452                gpus.insert(*idx, gpu);
453            }
454        }
455        gpus
456    }
457
458    /// Returns whether the Topology has a hybrid architecture of big and little cores.
459    pub fn has_little_cores(&self) -> bool {
460        self.all_cores
461            .values()
462            .any(|c| c.core_type == CoreType::Little)
463    }
464
465    /// Returns a vector that maps the index of each logical CPU to the
466    /// sibling CPU. This represents the "next sibling" CPU within a package
467    /// in systems that support SMT. The sibling CPU is the other logical
468    /// CPU that shares the physical resources of the same physical core.
469    ///
470    /// Assuming each core holds exactly at most two cpus.
471    pub fn sibling_cpus(&self) -> Vec<i32> {
472        let mut sibling_cpu = vec![-1i32; *NR_CPUS_POSSIBLE];
473        for core in self.all_cores.values() {
474            let mut first = -1i32;
475            for &cpu in core.cpus.keys() {
476                if first < 0 {
477                    first = cpu as i32;
478                } else {
479                    sibling_cpu[first as usize] = cpu as i32;
480                    sibling_cpu[cpu] = first;
481                    break;
482                }
483            }
484        }
485        sibling_cpu
486    }
487
488    /// Count how many physical cores have at least one CPU set in the cpumask.
489    pub fn cpumask_nr_cores(&self, cpumask: &Cpumask) -> usize {
490        let mut count = 0;
491        for core in self.all_cores.values() {
492            if core.cpus.keys().any(|&cpu_id| cpumask.test_cpu(cpu_id)) {
493                count += 1;
494            }
495        }
496        count
497    }
498
499    /// Reconstruct scheduler-domain policy for `cpu_id`.
500    ///
501    /// Linux does not expose scheduler-domain flags through a stable ABI.
502    /// When schedstat v17 is available, use its live domain masks and apply
503    /// the kernel's NUMA-reclaim and capacity-class rules. The counters may
504    /// all be zero when `kernel.sched_schedstats=0`; that does not affect the
505    /// masks consumed here. If schedstat is absent or incompatible, construct
506    /// portable core, LLC, NUMA-node and system masks from sysfs instead.
507    pub fn sched_domain_info(&self, cpu_id: usize) -> Result<SchedDomainInfo> {
508        let cpu = self
509            .all_cpus
510            .get(&cpu_id)
511            .ok_or_else(|| anyhow::anyhow!("CPU {cpu_id} is not in the topology"))?;
512
513        let (mut domains, source) = match self.sched_domains().and_then(|all| all.get(&cpu_id)) {
514            Some(domains) => (domains.clone(), SchedDomainSource::Schedstat),
515            None => {
516                let mut domains = vec![
517                    self.all_cores[&cpu.core_id].span.clone(),
518                    self.all_llcs[&cpu.llc_id].span.clone(),
519                    self.nodes[&cpu.node_id].span.clone(),
520                    self.span.clone(),
521                ];
522                domains.sort_by_key(Cpumask::weight);
523                domains.dedup();
524                (domains, SchedDomainSource::Topology)
525            }
526        };
527        domains = domains
528            .into_iter()
529            .map(|span| span.and(&self.span))
530            .filter(|span| span.test_cpu(cpu_id))
531            .collect();
532        domains.sort_by_key(Cpumask::weight);
533        domains.dedup();
534
535        let balance_span = domains
536            .iter()
537            .filter(|span| self.within_numa_reclaim_distance(cpu.node_id, span))
538            .map(Cpumask::weight)
539            .max()
540            .unwrap_or(1);
541
542        let capacities: Option<BTreeMap<_, _>> = self
543            .all_cpus
544            .iter()
545            .map(|(&id, cpu)| Some((id, cpu.kernel_cpu_capacity?)))
546            .collect();
547        let asym_capacity_span = capacities
548            .as_ref()
549            .map(|capacities| smallest_full_capacity_span(&domains, capacities))
550            .unwrap_or(0);
551
552        Ok(SchedDomainInfo {
553            fork_span: balance_span,
554            wake_affine_span: balance_span,
555            asym_capacity_span,
556            source,
557        })
558    }
559
560    fn within_numa_reclaim_distance(&self, source_node: usize, span: &Cpumask) -> bool {
561        let Some(source) = self.nodes.get(&source_node) else {
562            return false;
563        };
564
565        span.iter().all(|cpu_id| {
566            self.all_cpus
567                .get(&cpu_id)
568                .and_then(|cpu| source.distance.get(cpu.node_id))
569                .is_some_and(|&distance| distance <= NUMA_RECLAIM_DISTANCE)
570        })
571    }
572
573    /// Format a cpumask as a topology-aware visual grid.
574    ///
575    /// Each physical core is represented by a single character:
576    /// - `░` = no CPUs set
577    /// - `▀` = first HT only (top half)
578    /// - `▄` = second HT only (bottom half)
579    /// - `█` = both HTs (or all HTs for >2-way SMT)
580    ///
581    /// Cores within an LLC are split into evenly-sized groups of at
582    /// most 8 with spaces. LLCs are separated by `|`. Wrapping
583    /// happens at LLC boundaries. One line per NUMA node (may wrap).
584    pub fn format_cpumask_grid<W: Write>(
585        &self,
586        w: &mut W,
587        cpumask: &Cpumask,
588        indent: &str,
589        max_width: usize,
590    ) -> Result<()> {
591        for node in self.nodes.values() {
592            // Build the core characters for each LLC in this node.
593            // Within each LLC, cores are grouped by 4 with spaces.
594            let mut llc_segments: Vec<(usize, String)> = Vec::new();
595
596            for llc in node.llcs.values() {
597                let mut seg = String::new();
598                let nr_cores = llc.cores.len();
599                let nr_groups = nr_cores.div_ceil(8);
600                let base = nr_cores / nr_groups;
601                let rem = nr_cores % nr_groups;
602                // First `rem` groups get base+1, rest get base
603                let mut next_break = if rem > 0 { base + 1 } else { base };
604                let mut group_idx = 0;
605                for (i, core) in llc.cores.values().enumerate() {
606                    if i > 0 && i == next_break {
607                        seg.push(' ');
608                        group_idx += 1;
609                        next_break += if group_idx < rem { base + 1 } else { base };
610                    }
611                    let nr_cpus = core.cpus.len();
612                    let cpu_ids: Vec<usize> = core.cpus.keys().copied().collect();
613                    let nr_set: usize = cpu_ids.iter().filter(|&&c| cpumask.test_cpu(c)).count();
614
615                    let ch = if nr_cpus == 1 {
616                        if nr_set > 0 { '█' } else { '░' }
617                    } else if nr_cpus == 2 {
618                        let first_set = cpumask.test_cpu(cpu_ids[0]);
619                        let second_set = cpumask.test_cpu(cpu_ids[1]);
620                        match (first_set, second_set) {
621                            (false, false) => '░',
622                            (true, false) => '▀',
623                            (false, true) => '▄',
624                            (true, true) => '█',
625                        }
626                    } else {
627                        // >2 HTs (e.g. 4-way SMT)
628                        if nr_set == 0 {
629                            '░'
630                        } else if nr_set == nr_cpus {
631                            '█'
632                        } else {
633                            '▄'
634                        }
635                    };
636                    seg.push(ch);
637                }
638                llc_segments.push((llc.id, seg));
639            }
640
641            if llc_segments.is_empty() {
642                continue;
643            }
644
645            // Build prefix: "N{id} L{first_llc}: "
646            let first_llc_id = llc_segments[0].0;
647            let prefix = format!("{}N{} L{:02}: ", indent, node.id, first_llc_id);
648            let prefix_width = prefix.chars().count();
649            let cont_indent = format!(
650                "{}{}",
651                indent,
652                " ".repeat(prefix_width - indent.chars().count())
653            );
654
655            // Join LLCs with "|", wrapping at LLC boundaries
656            let mut line = prefix.clone();
657            let mut first_llc = true;
658
659            for (_, seg) in &llc_segments {
660                let seg_width = seg.chars().count();
661                let separator = if first_llc { "" } else { "|" };
662                let sep_width = separator.chars().count();
663                let current_line_width = line.chars().count();
664
665                if !first_llc && current_line_width + sep_width + seg_width > max_width {
666                    writeln!(w, "{}", line)?;
667                    line = format!("{}{}", cont_indent, seg);
668                } else {
669                    line = format!("{}{}{}", line, separator, seg);
670                }
671                first_llc = false;
672            }
673            writeln!(w, "{}", line)?;
674        }
675        Ok(())
676    }
677
678    /// Format a cpumask header line with cpu count, core count, and range.
679    pub fn format_cpumask_header(&self, cpumask: &Cpumask, min_cpus: u32, max_cpus: u32) -> String {
680        let nr_cpus = cpumask.weight();
681        let nr_cores = self.cpumask_nr_cores(cpumask);
682        format!(
683            "cpus={:3}({:3}c) [{:3},{:3}]",
684            nr_cpus, nr_cores, min_cpus, max_cpus
685        )
686    }
687}
688
689fn parse_schedstat(data: &str) -> Result<BTreeMap<usize, Vec<Cpumask>>> {
690    let mut lines = data.lines();
691    let version = lines
692        .next()
693        .and_then(|line| line.strip_prefix("version "))
694        .ok_or_else(|| anyhow::anyhow!("missing schedstat version"))?
695        .parse::<usize>()?;
696    if version != SCHEDSTAT_VERSION {
697        bail!("unsupported schedstat version {version}");
698    }
699
700    let mut domains = BTreeMap::<usize, Vec<Cpumask>>::new();
701    let mut current_cpu = None;
702    for line in lines {
703        let mut fields = line.split_ascii_whitespace();
704        let Some(kind) = fields.next() else {
705            continue;
706        };
707        if let Some(cpu) = kind.strip_prefix("cpu") {
708            let cpu = cpu.parse::<usize>()?;
709            domains.entry(cpu).or_default();
710            current_cpu = Some(cpu);
711            continue;
712        }
713        if !kind.starts_with("domain") {
714            continue;
715        }
716
717        let cpu = current_cpu.ok_or_else(|| anyhow::anyhow!("domain before CPU record"))?;
718        let _name = fields
719            .next()
720            .ok_or_else(|| anyhow::anyhow!("missing scheduler-domain name"))?;
721        let mask = fields
722            .next()
723            .ok_or_else(|| anyhow::anyhow!("missing scheduler-domain mask"))?
724            .replace(',', "");
725        domains
726            .entry(cpu)
727            .or_default()
728            .push(Cpumask::from_str(&mask)?);
729    }
730
731    for spans in domains.values_mut() {
732        spans.sort_by_key(Cpumask::weight);
733        spans.dedup();
734    }
735    Ok(domains)
736}
737
738fn smallest_full_capacity_span(domains: &[Cpumask], capacities: &BTreeMap<usize, usize>) -> usize {
739    let all = capacities.values().copied().collect::<BTreeSet<_>>();
740    if all.len() <= 1 {
741        return 0;
742    }
743
744    domains
745        .iter()
746        .find(|span| {
747            span.iter()
748                .filter_map(|cpu| capacities.get(&cpu).copied())
749                .collect::<BTreeSet<_>>()
750                == all
751        })
752        .map(Cpumask::weight)
753        .unwrap_or(0)
754}
755
756/******************************************************
757 * Helper structs/functions for creating the Topology *
758 ******************************************************/
759/// TopoCtx is a helper struct used to build a topology.
760struct TopoCtx {
761    /// Mapping of NUMA node core ids
762    node_core_kernel_ids: BTreeMap<(usize, usize, usize), usize>,
763    /// Mapping of NUMA node LLC ids
764    node_llc_kernel_ids: BTreeMap<(usize, usize, usize), usize>,
765    /// Mapping of L2 ids
766    l2_ids: BTreeMap<String, usize>,
767    /// Mapping of L3 ids
768    l3_ids: BTreeMap<String, usize>,
769}
770
771impl TopoCtx {
772    fn new() -> TopoCtx {
773        let core_kernel_ids = BTreeMap::new();
774        let llc_kernel_ids = BTreeMap::new();
775        let l2_ids = BTreeMap::new();
776        let l3_ids = BTreeMap::new();
777        TopoCtx {
778            node_core_kernel_ids: core_kernel_ids,
779            node_llc_kernel_ids: llc_kernel_ids,
780            l2_ids,
781            l3_ids,
782        }
783    }
784}
785
786pub(crate) fn cpus_online() -> Result<Cpumask> {
787    let path = format!("{}/sys/devices/system/cpu/online", *ROOT_PREFIX);
788    let online = std::fs::read_to_string(path)?;
789    Cpumask::from_cpulist(&online)
790}
791
792fn get_cache_id(topo_ctx: &mut TopoCtx, cache_level_path: &Path, cache_level: usize) -> usize {
793    // Check if the cache id is already cached
794    let id_map = match cache_level {
795        2 => &mut topo_ctx.l2_ids,
796        3 => &mut topo_ctx.l3_ids,
797        _ => return usize::MAX,
798    };
799
800    let path = &cache_level_path.join("shared_cpu_list");
801    let key = match std::fs::read_to_string(path) {
802        Ok(key) => key,
803        Err(_) => return usize::MAX,
804    };
805
806    let id = *id_map.get(&key).unwrap_or(&usize::MAX);
807    if id != usize::MAX {
808        return id;
809    }
810
811    // In case of a cache miss, try to get the id from the sysfs first.
812    let id = read_from_file(&cache_level_path.join("id")).unwrap_or(usize::MAX);
813    if id != usize::MAX {
814        // Keep the id in the map
815        id_map.insert(key, id);
816        return id;
817    }
818
819    // If the id file does not exist, assign an id and keep it in the map.
820    let id = id_map.len();
821    id_map.insert(key, id);
822
823    id
824}
825
826fn get_per_cpu_cache_size(cache_path: &Path) -> Result<usize> {
827    let path_str = cache_path.to_str().unwrap();
828    let paths = glob(&(path_str.to_owned() + "/index[0-9]*"))?;
829    let mut tot_size = 0;
830
831    for index in paths.filter_map(Result::ok) {
832        // If there is no size information under sysfs (e.g., many ARM SoCs),
833        // give 1024 as a default value. 1024 is small enough compared to the
834        // real cache size of the CPU, but it is large enough to give a penalty
835        // when multiple CPUs share the cache.
836        let size = read_file_byte(&index.join("size")).unwrap_or(1024_usize);
837        let cpulist: String = read_from_file(&index.join("shared_cpu_list"))?;
838        let num_cpus = read_cpulist(&cpulist)?.len();
839        tot_size += size / num_cpus;
840    }
841
842    Ok(tot_size)
843}
844
845#[allow(clippy::too_many_arguments)]
846fn create_insert_cpu(
847    id: usize,
848    node: &mut Node,
849    online_mask: &Cpumask,
850    topo_ctx: &mut TopoCtx,
851    cs: &CapacitySource,
852    flatten_llc: bool,
853) -> Result<()> {
854    // CPU is offline. The Topology hierarchy is read-only, and assumes
855    // that hotplug will cause the scheduler to restart. Thus, we can
856    // just skip this CPU altogether.
857    if !online_mask.test_cpu(id) {
858        return Ok(());
859    }
860
861    let cpu_str = format!("{}/sys/devices/system/cpu/cpu{}", *ROOT_PREFIX, id);
862    let cpu_path = Path::new(&cpu_str);
863
864    // Physical core ID
865    let top_path = cpu_path.join("topology");
866    let core_kernel_id = read_from_file(&top_path.join("core_id"))?;
867    let package_id = read_from_file(&top_path.join("physical_package_id"))?;
868    let cluster_id = read_from_file(&top_path.join("cluster_id"))?;
869
870    // Evaluate L2, L3 and LLC cache IDs.
871    //
872    // Use ID 0 if we fail to detect the cache hierarchy. This seems to happen on certain SKUs, so
873    // if there's no cache information then we have no option but to assume a single unified cache
874    // per node.
875    let cache_path = cpu_path.join("cache");
876    let l2_id = get_cache_id(topo_ctx, &cache_path.join(format!("index{}", 2)), 2);
877    let l3_id = get_cache_id(topo_ctx, &cache_path.join(format!("index{}", 3)), 3);
878    let llc_kernel_id = if flatten_llc {
879        0
880    } else if l3_id == usize::MAX {
881        l2_id
882    } else {
883        l3_id
884    };
885
886    // Per-CPU cache size
887    let cache_size = get_per_cpu_cache_size(&cache_path).unwrap_or(0_usize);
888
889    // Min and max frequencies. If the kernel is not compiled with
890    // CONFIG_CPU_FREQ, just assume 0 for both frequencies.
891    let freq_path = cpu_path.join("cpufreq");
892    let min_freq = read_from_file(&freq_path.join("scaling_min_freq")).unwrap_or(0_usize);
893    let max_freq = read_from_file(&freq_path.join("scaling_max_freq")).unwrap_or(0_usize);
894    let base_freq = read_from_file(&freq_path.join("base_frequency")).unwrap_or(max_freq);
895    let trans_lat_ns =
896        read_from_file(&freq_path.join("cpuinfo_transition_latency")).unwrap_or(0_usize);
897
898    // CPU capacity. Keep the kernel scheduler's exported value separate from
899    // the best-effort estimate, whose source may instead be CPPC or cpufreq.
900    let kernel_cpu_capacity = read_from_file(&cpu_path.join("cpu_capacity"))
901        .ok()
902        .filter(|capacity| *capacity > 0);
903    let cap_path = cpu_path.join(cs.suffix.clone());
904    let rcap = read_from_file(&cap_path).unwrap_or(cs.max_rcap);
905    let cpu_capacity = (rcap * 1024) / cs.max_rcap;
906
907    // Power management
908    let power_path = cpu_path.join("power");
909    let pm_qos_resume_latency_us =
910        read_from_file(&power_path.join("pm_qos_resume_latency_us")).unwrap_or(0_usize);
911
912    let num_llcs = topo_ctx.node_llc_kernel_ids.len();
913    let llc_id = topo_ctx
914        .node_llc_kernel_ids
915        .entry((node.id, package_id, llc_kernel_id))
916        .or_insert(num_llcs);
917
918    let llc = node.llcs.entry(*llc_id).or_insert(Arc::new(Llc {
919        id: *llc_id,
920        cores: BTreeMap::new(),
921        span: Cpumask::new(),
922        all_cpus: BTreeMap::new(),
923
924        node_id: node.id,
925        kernel_id: llc_kernel_id,
926    }));
927    let llc_mut = Arc::get_mut(llc).unwrap();
928
929    let core_type = if cs.avg_rcap < cs.max_rcap && rcap == cs.max_rcap {
930        CoreType::Big { turbo: true }
931    } else if !cs.has_biglittle || rcap >= cs.avg_rcap {
932        CoreType::Big { turbo: false }
933    } else {
934        CoreType::Little
935    };
936
937    let num_cores = topo_ctx.node_core_kernel_ids.len();
938    let core_id = topo_ctx
939        .node_core_kernel_ids
940        .entry((node.id, package_id, core_kernel_id))
941        .or_insert(num_cores);
942
943    let core = llc_mut.cores.entry(*core_id).or_insert(Arc::new(Core {
944        id: *core_id,
945        cpus: BTreeMap::new(),
946        span: Cpumask::new(),
947        core_type: core_type.clone(),
948
949        llc_id: *llc_id,
950        node_id: node.id,
951        kernel_id: core_kernel_id,
952        cluster_id,
953    }));
954    let core_mut = Arc::get_mut(core).unwrap();
955
956    core_mut.cpus.insert(
957        id,
958        Arc::new(Cpu {
959            id,
960            min_freq,
961            max_freq,
962            base_freq,
963            cpu_capacity,
964            kernel_cpu_capacity,
965            smt_level: 0, // Will be initialized at instantiate().
966            pm_qos_resume_latency_us,
967            trans_lat_ns,
968            l2_id,
969            l3_id,
970            cache_size,
971            core_type: core_type.clone(),
972
973            core_id: *core_id,
974            llc_id: *llc_id,
975            node_id: node.id,
976            package_id,
977            cluster_id,
978        }),
979    );
980
981    if node.span.test_cpu(id) {
982        bail!("Node {} already had CPU {}", node.id, id);
983    }
984
985    // Update all of the devices' spans to include this CPU.
986    core_mut.span.set_cpu(id)?;
987    llc_mut.span.set_cpu(id)?;
988    node.span.set_cpu(id)?;
989
990    Ok(())
991}
992
993fn read_cpu_ids() -> Result<Vec<usize>> {
994    let mut cpu_ids = vec![];
995    let path = format!("{}/sys/devices/system/cpu/cpu[0-9]*", *ROOT_PREFIX);
996    let cpu_paths = glob(&path)?;
997    for cpu_path in cpu_paths.filter_map(Result::ok) {
998        let cpu_str = cpu_path.to_str().unwrap().trim();
999        if ROOT_PREFIX.is_empty() {
1000            match sscanf!(cpu_str, "/sys/devices/system/cpu/cpu{usize}") {
1001                Some(val) => cpu_ids.push(val),
1002                None => {
1003                    bail!("Failed to parse cpu ID {}", cpu_str);
1004                }
1005            }
1006        } else {
1007            match sscanf!(cpu_str, "{str}/sys/devices/system/cpu/cpu{usize}") {
1008                Some((_, val)) => cpu_ids.push(val),
1009                None => {
1010                    bail!("Failed to parse cpu ID {}", cpu_str);
1011                }
1012            }
1013        }
1014    }
1015    cpu_ids.sort();
1016    Ok(cpu_ids)
1017}
1018
1019struct CapacitySource {
1020    /// Path suffix after /sys/devices/system/cpu/cpuX
1021    suffix: String,
1022    /// Average raw capacity value
1023    avg_rcap: usize,
1024    /// Maximum raw capacity value
1025    max_rcap: usize,
1026    /// Does a system have little cores?
1027    has_biglittle: bool,
1028}
1029
1030fn get_capacity_source() -> Option<CapacitySource> {
1031    // Sources for guessing cpu_capacity under /sys/devices/system/cpu/cpuX.
1032    // They should be ordered from the most precise to the least precise.
1033    let sources = [
1034        "cpufreq/amd_pstate_prefcore_ranking",
1035        "cpufreq/amd_pstate_highest_perf",
1036        "acpi_cppc/highest_perf",
1037        "cpu_capacity",
1038        "cpufreq/cpuinfo_max_freq",
1039    ];
1040
1041    // Find the most precise source for cpu_capacity estimation.
1042    let prefix = format!("{}/sys/devices/system/cpu/cpu0", *ROOT_PREFIX);
1043    let mut raw_capacity;
1044    let mut suffix = sources[sources.len() - 1];
1045    'outer: for src in sources {
1046        let path_str = [prefix.clone(), src.to_string()].join("/");
1047        let path = Path::new(&path_str);
1048        raw_capacity = read_from_file(path).unwrap_or(0_usize);
1049        if raw_capacity > 0 {
1050            // It would be an okay source...
1051            suffix = src;
1052            // But double-check if the source has meaningful information.
1053            let path = format!("{}/sys/devices/system/cpu/cpu[0-9]*", *ROOT_PREFIX);
1054            let cpu_paths = glob(&path).ok()?;
1055            for cpu_path in cpu_paths.filter_map(Result::ok) {
1056                let raw_capacity2 = read_from_file(&cpu_path.join(suffix)).unwrap_or(0_usize);
1057                if raw_capacity != raw_capacity2 {
1058                    break 'outer;
1059                }
1060            }
1061            // The source exists, but it tells that all CPUs have the same
1062            // capacity. Let's search more if there is any source that can
1063            // tell the capacity differences among CPUs. This can happen when
1064            // a buggy driver lies (e.g., "acpi_cppc/highest_perf").
1065        }
1066    }
1067
1068    // Find the max raw_capacity value for scaling to 1024.
1069    let mut max_rcap = 0;
1070    let mut min_rcap = usize::MAX;
1071    let mut avg_rcap = 0;
1072    let mut nr_cpus = 0;
1073    let mut has_biglittle = false;
1074    let path = format!("{}/sys/devices/system/cpu/cpu[0-9]*", *ROOT_PREFIX);
1075    let cpu_paths = glob(&path).ok()?;
1076    for cpu_path in cpu_paths.filter_map(Result::ok) {
1077        let rcap = read_from_file(&cpu_path.join(suffix)).unwrap_or(0_usize);
1078        if max_rcap < rcap {
1079            max_rcap = rcap;
1080        }
1081        if min_rcap > rcap {
1082            min_rcap = rcap;
1083        }
1084        avg_rcap += rcap;
1085        nr_cpus += 1;
1086    }
1087
1088    if nr_cpus == 0 || max_rcap == 0 {
1089        suffix = "";
1090        avg_rcap = 1024;
1091        max_rcap = 1024;
1092        warn!("CPU capacity information is not available under sysfs.");
1093    } else {
1094        avg_rcap /= nr_cpus;
1095        // We consider a system to have a heterogeneous CPU architecture only
1096        // when there is a significant capacity gap (e.g., 1.3x). CPU capacities
1097        // can still vary in a homogeneous architecture—for instance, due to
1098        // chip binning or when only a subset of CPUs supports turbo boost.
1099        //
1100        // Note that we need a more systematic approach to accurately detect
1101        // big/LITTLE architectures across various SoC designs. The current
1102        // approach, with a significant capacity difference, is somewhat ad-hoc.
1103        has_biglittle = max_rcap as f32 >= (1.3 * min_rcap as f32);
1104    }
1105
1106    Some(CapacitySource {
1107        suffix: suffix.to_string(),
1108        avg_rcap,
1109        max_rcap,
1110        has_biglittle,
1111    })
1112}
1113
1114fn is_smt_active() -> Option<bool> {
1115    let path = format!("{}/sys/devices/system/cpu/smt/active", *ROOT_PREFIX);
1116    let smt_on: u8 = read_from_file(Path::new(&path)).ok()?;
1117    Some(smt_on == 1)
1118}
1119
1120fn replace_with_virt_llcs(
1121    node: &mut Node,
1122    min_cores: usize,
1123    max_cores: usize,
1124    start_id: usize,
1125) -> Result<usize> {
1126    let mut next_id = start_id;
1127    let mut core_to_partition: BTreeMap<usize, usize> = BTreeMap::new();
1128    let mut partition_to_kernel_id: BTreeMap<usize, usize> = BTreeMap::new();
1129    let num_orig_llcs = node.llcs.len();
1130
1131    // First pass: determine core to partition mapping, partition to
1132    // kernel_id mapping, and total partitions needed
1133    for llc in node.llcs.values() {
1134        // Group cores by type (big/little) to partition separately
1135        let mut cores_by_type: BTreeMap<bool, Vec<usize>> = BTreeMap::new();
1136
1137        for (core_id, core) in llc.cores.iter() {
1138            let core_type = core.core_type == CoreType::Little;
1139            cores_by_type.entry(core_type).or_default().push(*core_id);
1140        }
1141
1142        for core_ids in cores_by_type.values() {
1143            let num_cores_in_bucket = core_ids.len();
1144
1145            // Find optimal partition size within specified range
1146            let best_split = find_best_split_size(num_cores_in_bucket, min_cores, max_cores);
1147            let num_partitions = num_cores_in_bucket / best_split;
1148
1149            // Assign cores to partitions within a group type
1150            for (bucket_idx, &core_id) in core_ids.iter().enumerate() {
1151                let partition_idx = min(bucket_idx / best_split, num_partitions - 1);
1152                let current_partition_id = next_id + partition_idx;
1153                core_to_partition.insert(core_id, current_partition_id);
1154                partition_to_kernel_id.insert(current_partition_id, llc.kernel_id);
1155            }
1156
1157            next_id += num_partitions;
1158        }
1159    }
1160
1161    // Create new virtual LLC structures based on partitioning found above
1162    let mut virt_llcs: BTreeMap<usize, Arc<Llc>> = BTreeMap::new();
1163
1164    for vllc_id in start_id..next_id {
1165        let kernel_id = partition_to_kernel_id.get(&vllc_id).copied().unwrap();
1166        virt_llcs.insert(
1167            vllc_id,
1168            Arc::new(Llc {
1169                id: vllc_id,
1170                kernel_id,
1171                cores: BTreeMap::new(),
1172                span: Cpumask::new(),
1173                node_id: node.id,
1174                all_cpus: BTreeMap::new(),
1175            }),
1176        );
1177    }
1178
1179    // Second pass: move cores to the appropriate new LLC based on partition
1180    for llc in node.llcs.values_mut() {
1181        for (core_id, core) in llc.cores.iter() {
1182            if let Some(&target_partition_id) = core_to_partition.get(core_id)
1183                && let Some(target_llc) = virt_llcs.get_mut(&target_partition_id)
1184            {
1185                let target_llc_mut = Arc::get_mut(target_llc).unwrap();
1186
1187                // Clone core and update its LLC ID to match new partition
1188                let mut new_core = (**core).clone();
1189                new_core.llc_id = target_partition_id;
1190
1191                // Update all CPUs within this core to reference new LLC ID
1192                let mut updated_cpus = BTreeMap::new();
1193                for (cpu_id, cpu) in new_core.cpus.iter() {
1194                    let mut new_cpu = (**cpu).clone();
1195                    new_cpu.llc_id = target_partition_id;
1196
1197                    // Add CPU to the virtual LLC's span
1198                    target_llc_mut.span.set_cpu(*cpu_id)?;
1199
1200                    updated_cpus.insert(*cpu_id, Arc::new(new_cpu));
1201                }
1202                new_core.cpus = updated_cpus;
1203
1204                // Add the updated core to the virtual LLC
1205                target_llc_mut.cores.insert(*core_id, Arc::new(new_core));
1206            }
1207        }
1208    }
1209
1210    // Replace original LLCs with virtual LLCs
1211    node.llcs = virt_llcs;
1212
1213    let num_virt_llcs = next_id - start_id;
1214    let vllc_sizes: Vec<usize> = node.llcs.values().map(|llc| llc.cores.len()).collect();
1215
1216    if vllc_sizes.is_empty() {
1217        return Ok(next_id);
1218    }
1219
1220    // Most vLLCs should have the same size, only the last one might differ
1221    let common_size = vllc_sizes[0];
1222    let last_size = *vllc_sizes.last().unwrap();
1223
1224    if common_size == last_size {
1225        info!(
1226            "Node {}: split {} LLC(s) into {} virtual LLCs with {} cores each",
1227            node.id, num_orig_llcs, num_virt_llcs, common_size
1228        );
1229    } else {
1230        info!(
1231            "Node {}: split {} LLC(s) into {} virtual LLCs with {} cores each (last with {})",
1232            node.id, num_orig_llcs, num_virt_llcs, common_size, last_size
1233        );
1234    }
1235
1236    Ok(next_id)
1237}
1238
1239fn create_default_node(
1240    online_mask: &Cpumask,
1241    topo_ctx: &mut TopoCtx,
1242    flatten_llc: bool,
1243    nr_cores_per_vllc: Option<(usize, usize)>,
1244) -> Result<BTreeMap<usize, Node>> {
1245    let mut nodes = BTreeMap::<usize, Node>::new();
1246
1247    let mut node = Node {
1248        id: 0,
1249        distance: vec![],
1250        llcs: BTreeMap::new(),
1251        span: Cpumask::new(),
1252        #[cfg(feature = "gpu-topology")]
1253        gpus: BTreeMap::new(),
1254        all_cores: BTreeMap::new(),
1255        all_cpus: BTreeMap::new(),
1256    };
1257
1258    #[cfg(feature = "gpu-topology")]
1259    {
1260        let system_gpus = create_gpus();
1261        if let Some(gpus) = system_gpus.get(&0) {
1262            for gpu in gpus {
1263                node.gpus.insert(gpu.index, gpu.clone());
1264            }
1265        }
1266    }
1267
1268    let path = format!("{}/sys/devices/system/cpu", *ROOT_PREFIX);
1269    if !Path::new(&path).exists() {
1270        bail!("/sys/devices/system/cpu sysfs node not found");
1271    }
1272
1273    let cs = get_capacity_source().unwrap();
1274    let cpu_ids = read_cpu_ids()?;
1275    for cpu_id in cpu_ids.iter() {
1276        create_insert_cpu(*cpu_id, &mut node, online_mask, topo_ctx, &cs, flatten_llc)?;
1277    }
1278
1279    if let Some((min_cores_val, max_cores_val)) = nr_cores_per_vllc {
1280        replace_with_virt_llcs(&mut node, min_cores_val, max_cores_val, 0)?;
1281    }
1282
1283    nodes.insert(node.id, node);
1284
1285    Ok(nodes)
1286}
1287
1288fn create_numa_nodes(
1289    online_mask: &Cpumask,
1290    topo_ctx: &mut TopoCtx,
1291    nr_cores_per_vllc: Option<(usize, usize)>,
1292) -> Result<BTreeMap<usize, Node>> {
1293    let mut nodes = BTreeMap::<usize, Node>::new();
1294    let mut next_virt_llc_id = 0;
1295
1296    #[cfg(feature = "gpu-topology")]
1297    let system_gpus = create_gpus();
1298
1299    let path = format!("{}/sys/devices/system/node/node*", *ROOT_PREFIX);
1300    let numa_paths = glob(&path)?;
1301    for numa_path in numa_paths.filter_map(Result::ok) {
1302        let numa_str = numa_path.to_str().unwrap().trim();
1303        let node_id = if ROOT_PREFIX.is_empty() {
1304            match sscanf!(numa_str, "/sys/devices/system/node/node{usize}") {
1305                Some(val) => val,
1306                None => {
1307                    bail!("Failed to parse NUMA node ID {}", numa_str);
1308                }
1309            }
1310        } else {
1311            match sscanf!(numa_str, "{str}/sys/devices/system/node/node{usize}") {
1312                Some((_, val)) => val,
1313                None => {
1314                    bail!("Failed to parse NUMA node ID {}", numa_str);
1315                }
1316            }
1317        };
1318
1319        let distance = read_file_usize_vec(
1320            Path::new(&format!(
1321                "{}/sys/devices/system/node/node{}/distance",
1322                *ROOT_PREFIX, node_id
1323            )),
1324            ' ',
1325        )?;
1326        let mut node = Node {
1327            id: node_id,
1328            distance,
1329            llcs: BTreeMap::new(),
1330            span: Cpumask::new(),
1331
1332            all_cores: BTreeMap::new(),
1333            all_cpus: BTreeMap::new(),
1334
1335            #[cfg(feature = "gpu-topology")]
1336            gpus: BTreeMap::new(),
1337        };
1338
1339        #[cfg(feature = "gpu-topology")]
1340        {
1341            if let Some(gpus) = system_gpus.get(&node_id) {
1342                for gpu in gpus {
1343                    node.gpus.insert(gpu.index, gpu.clone());
1344                }
1345            }
1346        }
1347
1348        let cpu_pattern = numa_path.join("cpu[0-9]*");
1349        let cpu_paths = glob(cpu_pattern.to_string_lossy().as_ref())?;
1350        let cs = get_capacity_source().unwrap();
1351        let mut cpu_ids = vec![];
1352        for cpu_path in cpu_paths.filter_map(Result::ok) {
1353            let cpu_str = cpu_path.to_str().unwrap().trim();
1354            let cpu_id = if ROOT_PREFIX.is_empty() {
1355                match sscanf!(cpu_str, "/sys/devices/system/node/node{usize}/cpu{usize}") {
1356                    Some((_, val)) => val,
1357                    None => {
1358                        bail!("Failed to parse cpu ID {}", cpu_str);
1359                    }
1360                }
1361            } else {
1362                match sscanf!(
1363                    cpu_str,
1364                    "{str}/sys/devices/system/node/node{usize}/cpu{usize}"
1365                ) {
1366                    Some((_, _, val)) => val,
1367                    None => {
1368                        bail!("Failed to parse cpu ID {}", cpu_str);
1369                    }
1370                }
1371            };
1372            cpu_ids.push(cpu_id);
1373        }
1374        cpu_ids.sort();
1375
1376        for cpu_id in cpu_ids {
1377            create_insert_cpu(cpu_id, &mut node, online_mask, topo_ctx, &cs, false)?;
1378        }
1379
1380        if let Some((min_cores_val, max_cores_val)) = nr_cores_per_vllc {
1381            next_virt_llc_id =
1382                replace_with_virt_llcs(&mut node, min_cores_val, max_cores_val, next_virt_llc_id)?;
1383        }
1384
1385        nodes.insert(node.id, node);
1386    }
1387    Ok(nodes)
1388}
1389
1390/// Test topology construction helpers.
1391///
1392/// Provides [`make_test_topo()`] for building synthetic [`Topology`] instances
1393/// with configurable node/LLC/core/HT counts, and [`mask_from_bits()`] for
1394/// building [`Cpumask`] values from a list of CPU IDs. Enable via the
1395/// `testutils` feature of `scx_utils`.
1396#[cfg(any(test, feature = "testutils"))]
1397pub mod testutils {
1398    use super::*;
1399    use crate::set_cpumask_test_width;
1400
1401    /// Create a [`Cpu`] with the given IDs and default frequencies/capacity.
1402    pub fn test_cpu(id: usize, core_id: usize, llc_id: usize, node_id: usize) -> Cpu {
1403        Cpu {
1404            id,
1405            core_id,
1406            llc_id,
1407            node_id,
1408            min_freq: 0,
1409            max_freq: 0,
1410            base_freq: 0,
1411            cpu_capacity: 1024,
1412            kernel_cpu_capacity: Some(1024),
1413            smt_level: 0, // filled by instantiate()
1414            pm_qos_resume_latency_us: 0,
1415            trans_lat_ns: 0,
1416            l2_id: 0,
1417            l3_id: llc_id,
1418            cache_size: 0,
1419            core_type: CoreType::Big { turbo: false },
1420            package_id: node_id,
1421            cluster_id: 0,
1422        }
1423    }
1424
1425    /// Create a [`Core`] from a set of CPUs with the given IDs.
1426    pub fn test_core(
1427        id: usize,
1428        cpus: BTreeMap<usize, Arc<Cpu>>,
1429        llc_id: usize,
1430        node_id: usize,
1431    ) -> Core {
1432        let mut span = Cpumask::new();
1433        for &cpu_id in cpus.keys() {
1434            span.set_cpu(cpu_id).unwrap();
1435        }
1436        Core {
1437            id,
1438            kernel_id: id,
1439            cluster_id: 0,
1440            cpus,
1441            span,
1442            core_type: CoreType::Big { turbo: false },
1443            llc_id,
1444            node_id,
1445        }
1446    }
1447
1448    /// Create an [`Llc`] from a set of cores with the given IDs.
1449    pub fn test_llc(id: usize, cores: BTreeMap<usize, Arc<Core>>, node_id: usize) -> Llc {
1450        let mut span = Cpumask::new();
1451        for core in cores.values() {
1452            for &cpu_id in core.cpus.keys() {
1453                span.set_cpu(cpu_id).unwrap();
1454            }
1455        }
1456        Llc {
1457            id,
1458            kernel_id: id,
1459            cores,
1460            span,
1461            node_id,
1462            all_cpus: BTreeMap::new(), // filled by instantiate()
1463        }
1464    }
1465
1466    /// Create a [`Node`] from a set of LLCs with the given IDs.
1467    pub fn test_node(id: usize, llcs: BTreeMap<usize, Arc<Llc>>, nr_nodes: usize) -> Node {
1468        let mut span = Cpumask::new();
1469        for llc in llcs.values() {
1470            for core in llc.cores.values() {
1471                for &cpu_id in core.cpus.keys() {
1472                    span.set_cpu(cpu_id).unwrap();
1473                }
1474            }
1475        }
1476        Node {
1477            id,
1478            distance: vec![10; nr_nodes],
1479            llcs,
1480            span,
1481            all_cores: BTreeMap::new(), // filled by instantiate()
1482            all_cpus: BTreeMap::new(),  // filled by instantiate()
1483            #[cfg(feature = "gpu-topology")]
1484            gpus: BTreeMap::new(),
1485        }
1486    }
1487
1488    /// Build a synthetic [`Topology`] with the specified dimensions.
1489    ///
1490    /// Returns `(topology, total_cpu_count)`. CPU IDs are assigned
1491    /// sequentially starting from 0: node 0's LLCs get the lowest IDs,
1492    /// then node 1, etc.
1493    ///
1494    /// Sets the Cpumask test width override to `total_cpus` so that all
1495    /// masks created during the test have consistent width.
1496    pub fn make_test_topo(
1497        nr_nodes: usize,
1498        llcs_per_node: usize,
1499        cores_per_llc: usize,
1500        hts_per_core: usize,
1501    ) -> (Topology, usize) {
1502        let total_cpus = nr_nodes * llcs_per_node * cores_per_llc * hts_per_core;
1503        set_cpumask_test_width(total_cpus);
1504
1505        let mut cpu_id = 0usize;
1506        let mut core_id = 0usize;
1507        let mut llc_id = 0usize;
1508        let mut nodes = BTreeMap::new();
1509
1510        for node_idx in 0..nr_nodes {
1511            let mut llcs = BTreeMap::new();
1512            for _ in 0..llcs_per_node {
1513                let mut cores = BTreeMap::new();
1514                for _ in 0..cores_per_llc {
1515                    let mut cpus = BTreeMap::new();
1516                    for _ in 0..hts_per_core {
1517                        cpus.insert(
1518                            cpu_id,
1519                            Arc::new(test_cpu(cpu_id, core_id, llc_id, node_idx)),
1520                        );
1521                        cpu_id += 1;
1522                    }
1523                    cores.insert(
1524                        core_id,
1525                        Arc::new(test_core(core_id, cpus, llc_id, node_idx)),
1526                    );
1527                    core_id += 1;
1528                }
1529                llcs.insert(llc_id, Arc::new(test_llc(llc_id, cores, node_idx)));
1530                llc_id += 1;
1531            }
1532            nodes.insert(node_idx, test_node(node_idx, llcs, nr_nodes));
1533        }
1534
1535        let mut span = Cpumask::new();
1536        for i in 0..total_cpus {
1537            span.set_cpu(i).unwrap();
1538        }
1539
1540        (Topology::instantiate(span, nodes).unwrap(), total_cpus)
1541    }
1542
1543    pub fn make_het_test_topo(
1544        cores_per_llc: &[&[usize]],
1545        hts_per_core: usize,
1546    ) -> (Topology, usize) {
1547        let nr_nodes = cores_per_llc.len();
1548
1549        let total_cpus = cores_per_llc
1550            .iter()
1551            .map(|node| node.iter().sum::<usize>())
1552            .sum::<usize>()
1553            * hts_per_core;
1554
1555        set_cpumask_test_width(total_cpus);
1556
1557        let mut cpu_id = 0usize;
1558        let mut core_id = 0usize;
1559        let mut llc_id = 0usize;
1560        let mut nodes = BTreeMap::new();
1561
1562        for (node_id, llcs_in_node) in cores_per_llc.iter().enumerate() {
1563            let mut llcs = BTreeMap::new();
1564
1565            for &cores_in_llc in *llcs_in_node {
1566                let mut cores = BTreeMap::new();
1567
1568                for _ in 0..cores_in_llc {
1569                    let mut cpus = BTreeMap::new();
1570
1571                    for _ in 0..hts_per_core {
1572                        cpus.insert(cpu_id, Arc::new(test_cpu(cpu_id, core_id, llc_id, node_id)));
1573                        cpu_id += 1;
1574                    }
1575
1576                    cores.insert(core_id, Arc::new(test_core(core_id, cpus, llc_id, node_id)));
1577                    core_id += 1;
1578                }
1579
1580                llcs.insert(llc_id, Arc::new(test_llc(llc_id, cores, node_id)));
1581                llc_id += 1;
1582            }
1583
1584            nodes.insert(node_id, test_node(node_id, llcs, nr_nodes));
1585        }
1586
1587        let mut span = Cpumask::new();
1588        for i in 0..total_cpus {
1589            span.set_cpu(i).unwrap();
1590        }
1591
1592        (Topology::instantiate(span, nodes).unwrap(), total_cpus)
1593    }
1594
1595    /// Create a [`Cpumask`] from a list of set CPU IDs.
1596    pub fn mask_from_bits(_total: usize, bits: &[usize]) -> Cpumask {
1597        let mut mask = Cpumask::new();
1598        for &b in bits {
1599            mask.set_cpu(b).unwrap();
1600        }
1601        mask
1602    }
1603}
1604
1605#[cfg(test)]
1606mod tests {
1607    use super::testutils::*;
1608    use super::*;
1609    use crate::set_cpumask_test_width;
1610
1611    fn grid_output(topo: &Topology, cpumask: &Cpumask) -> String {
1612        let mut buf = Vec::new();
1613        topo.format_cpumask_grid(&mut buf, cpumask, "    ", 80)
1614            .unwrap();
1615        String::from_utf8(buf).unwrap()
1616    }
1617
1618    #[test]
1619    fn test_parse_schedstat_domains() {
1620        set_cpumask_test_width(8);
1621        let data = concat!(
1622            "version 17\n",
1623            "timestamp 42\n",
1624            "cpu0 0 0 0 0 0 0 0 0 0\n",
1625            "domain0 SMT 03 0 0\n",
1626            "domain1 MC 0f 0 0\n",
1627            "cpu1 0 0 0 0 0 0 0 0 0\n",
1628            "domain0 SMT 03 0 0\n",
1629            "domain1 MC ff 0 0\n",
1630        );
1631        let domains = parse_schedstat(data).unwrap();
1632        assert_eq!(
1633            domains[&0].iter().map(Cpumask::weight).collect::<Vec<_>>(),
1634            [2, 4]
1635        );
1636        assert_eq!(
1637            domains[&1].iter().map(Cpumask::weight).collect::<Vec<_>>(),
1638            [2, 8]
1639        );
1640        assert!(parse_schedstat(&data.replace("version 17", "version 18")).is_err());
1641    }
1642
1643    #[test]
1644    fn test_capacity_domain_selection() {
1645        set_cpumask_test_width(8);
1646        let domains = vec![
1647            mask_from_bits(8, &[0, 1]),
1648            mask_from_bits(8, &[0, 1, 2, 3]),
1649            mask_from_bits(8, &[0, 1, 2, 3, 4, 5, 6, 7]),
1650        ];
1651        let capacities = (0..8)
1652            .map(|cpu| (cpu, if cpu < 4 { 512 } else { 1024 }))
1653            .collect();
1654        assert_eq!(smallest_full_capacity_span(&domains, &capacities), 8);
1655
1656        let capacities = (0..8).map(|cpu| (cpu, 1024)).collect();
1657        assert_eq!(smallest_full_capacity_span(&domains, &capacities), 0);
1658    }
1659
1660    #[test]
1661    fn test_topology_sched_domain_fallback() {
1662        let (mut topo, _) = make_test_topo(2, 1, 2, 1);
1663        topo.sched_domains.set(None).unwrap();
1664        topo.nodes.get_mut(&0).unwrap().distance = vec![10, 100];
1665        topo.nodes.get_mut(&1).unwrap().distance = vec![100, 10];
1666
1667        let info = topo.sched_domain_info(0).unwrap();
1668        assert_eq!(info.source, SchedDomainSource::Topology);
1669        assert_eq!(info.fork_span, 2);
1670        assert_eq!(info.wake_affine_span, 2);
1671        assert_eq!(info.asym_capacity_span, 0);
1672    }
1673
1674    #[test]
1675    fn test_grid_2node_2llc_3core_2ht() {
1676        // 2 nodes, 2 LLCs/node, 3 cores/LLC, 2 HTs/core = 24 CPUs
1677        let (topo, total) = make_test_topo(2, 2, 3, 2);
1678        assert_eq!(total, 24);
1679
1680        // Set some specific CPUs:
1681        // Node0 LLC0: core0(cpu0,1) core1(cpu2,3) core2(cpu4,5)
1682        // Node0 LLC1: core3(cpu6,7) core4(cpu8,9) core5(cpu10,11)
1683        // Node1 LLC2: core6(cpu12,13) core7(cpu14,15) core8(cpu16,17)
1684        // Node1 LLC3: core9(cpu18,19) core10(cpu20,21) core11(cpu22,23)
1685        //
1686        // Set: cpu1(core0 2nd HT), cpu2+3(core1 both), cpu12(core6 1st HT)
1687        let cpumask = mask_from_bits(total, &[1, 2, 3, 12]);
1688
1689        let output = grid_output(&topo, &cpumask);
1690        // Node0: LLC0=[▄ █ ░] LLC1=[░ ░ ░]
1691        // Node1: LLC2=[▀ ░ ░] LLC3=[░ ░ ░]
1692        assert!(output.contains("N0 L00:"));
1693        assert!(output.contains("N1 L02:"));
1694        // LLC0=▄█░, LLC1=░░░ separated by |
1695        assert!(output.contains("▄█░|░░░"));
1696        // LLC2=▀░░, LLC3=░░░ separated by |
1697        assert!(output.contains("▀░░|░░░"));
1698
1699        // Core count: cores 0,1,6 have at least one CPU set = 3
1700        assert_eq!(topo.cpumask_nr_cores(&cpumask), 3);
1701    }
1702
1703    #[test]
1704    fn test_grid_empty_cpumask() {
1705        let (topo, total) = make_test_topo(1, 2, 3, 2);
1706        let cpumask = mask_from_bits(total, &[]);
1707        let output = grid_output(&topo, &cpumask);
1708        // All chars should be ░
1709        assert!(!output.contains('█'));
1710        assert!(!output.contains('▀'));
1711        assert!(!output.contains('▄'));
1712        assert!(output.contains('░'));
1713        assert_eq!(topo.cpumask_nr_cores(&cpumask), 0);
1714    }
1715
1716    #[test]
1717    fn test_grid_full_cpumask() {
1718        let (topo, total) = make_test_topo(1, 2, 3, 2);
1719        let cpumask = mask_from_bits(total, &(0..total).collect::<Vec<_>>());
1720        let output = grid_output(&topo, &cpumask);
1721        // All chars should be █
1722        assert!(!output.contains('░'));
1723        assert!(!output.contains('▀'));
1724        assert!(!output.contains('▄'));
1725        assert!(output.contains('█'));
1726        assert_eq!(topo.cpumask_nr_cores(&cpumask), 6);
1727    }
1728
1729    #[test]
1730    fn test_grid_mixed_ht() {
1731        // 1 node, 1 LLC, 4 cores, 2 HTs = 8 CPUs
1732        let (topo, total) = make_test_topo(1, 1, 4, 2);
1733        // core0: cpu0,1  core1: cpu2,3  core2: cpu4,5  core3: cpu6,7
1734        // Set: cpu0 only (▀), cpu3 only (▄), cpu4+5 (█), none on core3 (░)
1735        let cpumask = mask_from_bits(total, &[0, 3, 4, 5]);
1736        let output = grid_output(&topo, &cpumask);
1737        assert!(output.contains('▀'));
1738        assert!(output.contains('▄'));
1739        assert!(output.contains('█'));
1740        assert!(output.contains('░'));
1741    }
1742
1743    #[test]
1744    fn test_grid_single_node() {
1745        let (topo, total) = make_test_topo(1, 1, 2, 2);
1746        let cpumask = mask_from_bits(total, &[0, 1]);
1747        let output = grid_output(&topo, &cpumask);
1748        assert!(output.contains("N0 L00:"));
1749        assert!(!output.contains("N1"));
1750    }
1751
1752    #[test]
1753    fn test_grid_overflow_wrap() {
1754        // 1 node, 12 LLCs, 4 cores each, 2 HTs = many characters
1755        // 12 LLCs grouped by 4 = 3 groups per line, should wrap
1756        let (topo, total) = make_test_topo(1, 12, 4, 2);
1757        let cpumask = mask_from_bits(total, &[0]);
1758        let mut buf = Vec::new();
1759        topo.format_cpumask_grid(&mut buf, &cpumask, "    ", 60)
1760            .unwrap();
1761        let output = String::from_utf8(buf).unwrap();
1762        // Should have multiple lines for node 0 due to wrapping
1763        let lines: Vec<&str> = output.lines().collect();
1764        assert!(
1765            lines.len() > 1,
1766            "Expected wrapping with narrow width, got {} lines",
1767            lines.len()
1768        );
1769    }
1770
1771    #[test]
1772    fn test_grid_smt_off() {
1773        // 1 node, 1 LLC, 4 cores, 1 HT = no SMT
1774        let (topo, total) = make_test_topo(1, 1, 4, 1);
1775        // core0: cpu0, core1: cpu1, core2: cpu2, core3: cpu3
1776        let cpumask = mask_from_bits(total, &[0, 2]);
1777        let output = grid_output(&topo, &cpumask);
1778        // Only █ and ░ should appear
1779        assert!(output.contains('█'));
1780        assert!(output.contains('░'));
1781        assert!(!output.contains('▀'));
1782        assert!(!output.contains('▄'));
1783    }
1784
1785    #[test]
1786    fn test_grid_4way_smt() {
1787        // 1 node, 1 LLC, 2 cores, 4 HTs = 8 CPUs
1788        let (topo, total) = make_test_topo(1, 1, 2, 4);
1789        // core0: cpu0-3, core1: cpu4-7
1790        // Set all of core0 → █, set 2 of core1 → ▄ (partial)
1791        let cpumask = mask_from_bits(total, &[0, 1, 2, 3, 4, 5]);
1792        let output = grid_output(&topo, &cpumask);
1793        assert!(output.contains('█')); // core0: all 4 set
1794        assert!(output.contains('▄')); // core1: partial (2 of 4)
1795    }
1796
1797    #[test]
1798    fn test_cpumask_header() {
1799        let (topo, total) = make_test_topo(1, 1, 4, 2);
1800        // 4 cores, 8 CPUs. Set cpu0,1,2 (2 cores touched)
1801        let cpumask = mask_from_bits(total, &[0, 1, 2]);
1802        let header = topo.format_cpumask_header(&cpumask, 5, 10);
1803        assert!(header.contains("cpus=  3(  2c)"));
1804        assert!(header.contains("[  5, 10]"));
1805    }
1806}