scx_rustsched_loader/
tiers.rs

1// SPDX-License-Identifier: GPL-2.0-only
2// Copyright (c) 2026 NVIDIA CORPORATION & AFFILIATES.
3
4//! CPU capacities and asymmetric packing priorities, the loader's half of
5//! scx_rustsched's tiers.rs and topology.rs. The capacities and the
6//! scheduling-domain spans come from scx_utils' Topology. The ITMT priority
7//! and SD_ASYM_PACKING come from the kernel through the rust_cpu_priority()
8//! syscall program, since neither has a user-space ABI. The result goes to
9//! the BPF program per CPU, which translates it to CIDs at init.
10//!
11//! Capacity and packing are separate kernel policies with separate tiers,
12//! 0 the most preferred in both. Capacity tiers group CPUs of close
13//! capacity; packing tiers group CPUs of equal priority, or follow the
14//! capacity tiers when the kernel does not pack.
15
16use std::ffi::OsStr;
17
18use anyhow::{Context, Result, bail, ensure};
19use libbpf_rs::{
20    Btf, MapCore, MapFlags, Object, ProgramInput,
21    btf::types::{Composite, Enum, MemberAttr, Struct},
22};
23
24/// The BPF program's per-CPU table, see scx_rustsched's tiers.rs.
25pub const MAX_CPUS: usize = 8192;
26const _: () = assert!(
27    MAX_CPUS <= 0x3fff,
28    "the asymmetric capacity span takes 14 bits"
29);
30
31/// How capacities are chosen.
32#[derive(Clone, Copy, PartialEq)]
33pub enum CapacityMode {
34    /// The kernel's cpu_capacity, which fair.c builds its domains from.
35    Kernel,
36    /// Every CPU the same.
37    Uniform,
38    /// scx_utils' hardware estimate, which can tell hybrid x86 cores apart
39    /// where the kernel does not.
40    Hardware,
41}
42
43#[derive(Clone)]
44pub struct Cpu {
45    pub id: usize,
46    /// Normalized to 1..=1024, the fastest at 1024.
47    pub capacity: u64,
48    pub capacity_tier: u64,
49    pub place_tier: u64,
50    /// The SMT domain itself packs, so a core's threads rank too.
51    pub smt_asym_packing: bool,
52    /// The lowest domain spanning every capacity class, 0 for none.
53    pub asym_capacity_span: u64,
54}
55
56pub struct Tiers {
57    pub cpus: Vec<Cpu>,
58    pub nr_capacity_tiers: u64,
59    pub nr_place_tiers: u64,
60    /// Placement and balance follow capacity.
61    pub asym_capacity: bool,
62    /// The kernel has an SD_ASYM_CPUCAPACITY domain.
63    pub sched_asym_capacity: bool,
64    /// The hardware estimate was asked for, which makes placement follow
65    /// capacity whether or not the kernel has such a domain.
66    pub forced: bool,
67    pub asym_packing: bool,
68    /// Where the capacities came from: the kernel's falls back to the
69    /// hardware estimate when the kernel exports none.
70    pub mode: CapacityMode,
71    /// Largest capacity difference, in percent, within one tier.
72    pub tolerance: u32,
73}
74
75/// Assign sorted, descending capacities to tiers. Each capacity is compared
76/// with the fastest CPU of the current tier rather than the previous CPU,
77/// so that a chain of small steps does not merge CPUs far apart.
78pub fn capacity_tiers(capacities: &[u64], tolerance_pct: u32) -> Vec<u64> {
79    let Some(&first) = capacities.first() else {
80        return Vec::new();
81    };
82    let keep_pct = 100 - u64::from(tolerance_pct);
83    let mut anchor = first;
84    let mut tier = 0;
85    capacities
86        .iter()
87        .map(|&capacity| {
88            if capacity.saturating_mul(100) < anchor.saturating_mul(keep_pct) {
89                tier += 1;
90                anchor = capacity;
91            }
92            tier
93        })
94        .collect()
95}
96
97/// Packing tiers from (cpu, priority) pairs: equal priorities share a tier,
98/// the highest priority is tier 0. Returns the tier per pair, in the order
99/// given.
100pub fn priority_tiers(priorities: &[(usize, i64)]) -> Vec<u64> {
101    let mut sorted: Vec<i64> = priorities.iter().map(|&(_, priority)| priority).collect();
102    sorted.sort_unstable_by(|a, b| b.cmp(a));
103    sorted.dedup();
104    priorities
105        .iter()
106        .map(|(_, priority)| sorted.iter().position(|p| p == priority).unwrap() as u64)
107        .collect()
108}
109
110impl Tiers {
111    /// Capacities and capacity tiers, from the topology before load.
112    pub fn new(mode: CapacityMode, tolerance_pct: Option<u32>) -> Result<Self> {
113        let topology = scx_utils::Topology::new().context("read CPU topology")?;
114        let forced = mode == CapacityMode::Hardware;
115        let mut mode = mode;
116        let mut cpus: Vec<(usize, usize)> = match mode {
117            CapacityMode::Uniform => topology.all_cpus.keys().map(|&id| (id, 1024)).collect(),
118            CapacityMode::Hardware => topology
119                .all_cpus
120                .values()
121                .map(|cpu| (cpu.id, cpu.cpu_capacity))
122                .collect(),
123            CapacityMode::Kernel => {
124                match topology
125                    .all_cpus
126                    .values()
127                    .map(|cpu| Some((cpu.id, cpu.kernel_cpu_capacity?)))
128                    .collect::<Option<Vec<_>>>()
129                {
130                    Some(cpus) => cpus,
131                    None => {
132                        mode = CapacityMode::Hardware;
133                        topology
134                            .all_cpus
135                            .values()
136                            .map(|cpu| (cpu.id, cpu.cpu_capacity))
137                            .collect()
138                    }
139                }
140            }
141        };
142        ensure!(
143            cpus.iter().all(|&(id, _)| id < MAX_CPUS),
144            "more than {MAX_CPUS} CPUs"
145        );
146        let tolerance = tolerance_pct.unwrap_or(if mode == CapacityMode::Hardware { 5 } else { 0 });
147        cpus.sort_by_key(|&(id, capacity)| (std::cmp::Reverse(capacity), id));
148        let max = cpus.first().map_or(1, |&(_, capacity)| capacity.max(1));
149        let capacities: Vec<u64> = cpus
150            .iter()
151            .map(|&(_, capacity)| (capacity * 1024 / max).clamp(1, 1024) as u64)
152            .collect();
153        let tiers = capacity_tiers(&capacities, tolerance);
154        let nr_capacity_tiers = tiers.last().map_or(1, |tier| tier + 1);
155        let mut entries = Vec::with_capacity(cpus.len());
156        for ((&(id, _), &capacity), &tier) in cpus.iter().zip(&capacities).zip(&tiers) {
157            let domains = topology
158                .sched_domain_info(id)
159                .context("read scheduler domains")?;
160            entries.push(Cpu {
161                id,
162                capacity,
163                capacity_tier: tier,
164                place_tier: tier,
165                smt_asym_packing: false,
166                asym_capacity_span: domains.asym_capacity_span as u64,
167            });
168        }
169        let sched_asym_capacity =
170            mode != CapacityMode::Uniform && entries.iter().any(|cpu| cpu.asym_capacity_span != 0);
171        // A hardware estimate the kernel fell back to does not by itself
172        // make placement follow capacity: only asking for it does.
173        let asym_capacity = nr_capacity_tiers > 1 && (sched_asym_capacity || forced);
174        Ok(Self {
175            cpus: entries,
176            nr_capacity_tiers,
177            nr_place_tiers: 1,
178            asym_capacity,
179            sched_asym_capacity,
180            forced,
181            asym_packing: false,
182            mode,
183            tolerance,
184        })
185    }
186
187    /// Ask the kernel for each CPU's packing priority, after load, and set
188    /// the packing tiers: from the priorities if every CPU packs and they
189    /// differ, otherwise from the capacity tiers if placement follows
190    /// capacity, otherwise one tier.
191    pub fn read_priorities(&mut self, object: &mut Object, disable: bool) -> Result<()> {
192        let btf = Btf::from_vmlinux().context("read running kernel BTF")?;
193        let (flags_offset, child_offset) = domain_offsets(&btf)?;
194        let (asym_packing_flag, share_capacity_flag) = domain_flags(&btf)?;
195        let program = object
196            .progs_mut()
197            .find(|program| program.name() == OsStr::new("rust_cpu_priority"))
198            .context("find rust_cpu_priority")?;
199        let mut priorities = Vec::with_capacity(self.cpus.len());
200        let mut all_pack = !disable;
201        for cpu in &mut self.cpus {
202            let mut args = [
203                cpu.id as u64,
204                flags_offset,
205                child_offset,
206                asym_packing_flag,
207                share_capacity_flag,
208                0,
209                0,
210                0,
211            ];
212            let input = ProgramInput {
213                context_in: Some(unsafe {
214                    std::slice::from_raw_parts_mut(
215                        args.as_mut_ptr().cast::<u8>(),
216                        size_of_val(&args),
217                    )
218                }),
219                ..Default::default()
220            };
221            let output = program.test_run(input).context("run rust_cpu_priority")?;
222            ensure!(output.return_value == 0, "rust_cpu_priority failed");
223            if !disable {
224                all_pack &= args[6] != 0;
225                cpu.smt_asym_packing = args[7] != 0;
226                priorities.push((cpu.id, args[5] as i64));
227            }
228        }
229        let distinct = priorities.windows(2).any(|pair| pair[0].1 != pair[1].1);
230        self.asym_packing = all_pack && distinct;
231        if self.asym_packing {
232            let tiers = priority_tiers(&priorities);
233            for (cpu, tier) in self.cpus.iter_mut().zip(tiers) {
234                cpu.place_tier = tier;
235            }
236            self.nr_place_tiers = self
237                .cpus
238                .iter()
239                .map(|cpu| cpu.place_tier)
240                .max()
241                .unwrap_or(0)
242                + 1;
243        } else {
244            for cpu in &mut self.cpus {
245                cpu.place_tier = if self.asym_capacity {
246                    cpu.capacity_tier
247                } else {
248                    0
249                };
250                cpu.smt_asym_packing = false;
251            }
252            self.nr_place_tiers = if self.asym_capacity {
253                self.nr_capacity_tiers
254            } else {
255                1
256            };
257        }
258        Ok(())
259    }
260
261    /// Hand the tiers to the BPF program, before it attaches.
262    pub fn publish(&self, object: &Object) -> Result<()> {
263        let map = object
264            .maps()
265            .find(|map| map.name() == OsStr::new(".data.tiers"))
266            .context("find the CPU tier table")?;
267        let mut words = vec![0_u64; 4 + MAX_CPUS];
268        words[0] = self.nr_capacity_tiers;
269        words[1] = self.nr_place_tiers;
270        words[2] = u64::from(self.asym_capacity)
271            | u64::from(self.sched_asym_capacity) << 1
272            | u64::from(self.asym_packing) << 2
273            | u64::from(self.forced) << 3
274            | u64::from(self.cpus.iter().any(|cpu| cpu.smt_asym_packing)) << 4;
275        for cpu in &self.cpus {
276            words[4 + cpu.id] = 1 << 63
277                | cpu.capacity
278                | cpu.capacity_tier << 16
279                | cpu.place_tier << 32
280                | u64::from(cpu.smt_asym_packing) << 48
281                | cpu.asym_capacity_span.min(0x3fff) << 49;
282        }
283        let bytes: Vec<u8> = words.iter().flat_map(|word| word.to_ne_bytes()).collect();
284        map.update(&0_u32.to_ne_bytes(), &bytes, MapFlags::ANY)
285            .context("write the CPU tier table")
286    }
287}
288
289/// struct sched_domain's flags and child offsets.
290fn domain_offsets(btf: &Btf<'_>) -> Result<(u64, u64)> {
291    let domain = btf
292        .type_by_name::<Struct<'_>>("sched_domain")
293        .context("find struct sched_domain")?;
294    let composite = Composite::from(domain);
295    let offset = |name: &str| -> Result<u64> {
296        let member = composite
297            .iter()
298            .find(|member| member.name == Some(OsStr::new(name)))
299            .with_context(|| format!("sched_domain has no {name}"))?;
300        match member.attr {
301            MemberAttr::Normal { offset } if offset % 8 == 0 => Ok(u64::from(offset / 8)),
302            _ => bail!("sched_domain.{name} is not byte aligned"),
303        }
304    };
305    Ok((offset("flags")?, offset("child")?))
306}
307
308/// The SD_ASYM_PACKING and SD_SHARE_CPUCAPACITY bits, enumerators of an
309/// anonymous kernel enum.
310fn domain_flags(btf: &Btf<'_>) -> Result<(u64, u64)> {
311    let (mut packing, mut share) = (None, None);
312    for enumeration in btf.type_by_kind::<Enum<'_>>() {
313        for member in enumeration.iter() {
314            match member.name.and_then(OsStr::to_str) {
315                Some("SD_ASYM_PACKING") => packing = Some(member.value as u64),
316                Some("SD_SHARE_CPUCAPACITY") => share = Some(member.value as u64),
317                _ => {}
318            }
319        }
320    }
321    Ok((
322        packing.context("kernel BTF has no SD_ASYM_PACKING")?,
323        share.context("kernel BTF has no SD_SHARE_CPUCAPACITY")?,
324    ))
325}
326
327#[cfg(test)]
328mod tests {
329    use super::*;
330
331    #[test]
332    fn capacity_tiers_anchor_on_the_fastest_of_a_tier() {
333        // 5% tolerance: 1000 and 960 share a tier, 920 is within 5% of 960
334        // but not of 1000, the tier's fastest, so it starts the next one.
335        assert_eq!(
336            capacity_tiers(&[1000, 960, 920, 900, 500], 5),
337            [0, 0, 1, 1, 2]
338        );
339        assert_eq!(capacity_tiers(&[1024, 1024, 1023], 0), [0, 0, 1]);
340        assert!(capacity_tiers(&[], 5).is_empty());
341    }
342
343    #[test]
344    fn priority_tiers_rank_equal_priorities_together() {
345        let priorities = [(0, 70), (1, 70), (4, 80), (12, 50), (13, 50)];
346        assert_eq!(priority_tiers(&priorities), [1, 1, 0, 2, 2]);
347    }
348}
scx_rustsched_loader/tiers.rs

scx_rustsched_loader/
tiers.rs
