ktstr/vmm/host_topology/
mod.rs

1//! Host CPU topology discovery for performance_mode.
2//!
3//! Wraps [`TestTopology`](crate::topology::TestTopology) for LLC-aware
4//! vCPU pinning and host resource validation.
5
6use anyhow::{Context, Result};
7use std::cell::RefCell;
8use std::sync::atomic::{AtomicBool, Ordering};
9
10// Advisory flock primitives live in `crate::flock` so both LLC +
11// per-CPU coordination here and per-cache-entry coordination in
12// `crate::cache` share one `try_flock` implementation (with a single
13// `O_CLOEXEC` source of truth) plus one `HolderInfo` /proc/locks
14// parser. Re-importing the names keeps existing in-module call sites
15// (production + `super::*` tests) compiling unchanged.
16#[cfg(test)]
17use crate::flock::try_flock;
18use crate::flock::{FlockMode, TryFlockOutcome, block_flock_deadline, try_flock_with_witness};
19
20// Cross-invocation acquisition protocol: exact fixed-record claims,
21// work-conserving grants, the coordinator watch, and lifecycle-bound blocking.
22// See protocol.rs's module doc for the full model.
23pub(crate) mod protocol;
24
25const RESERVATION_WAIT_PROGRESS_POLL: std::time::Duration = std::time::Duration::from_secs(1);
26
27thread_local! {
28    /// Optional same-thread progress callbacks around a blocking admission
29    /// acquire. A stack keeps nested library callers well-defined without a
30    /// process-global reporter or helper thread.
31    static RESERVATION_WAIT_PROGRESS: RefCell<Vec<Box<dyn FnMut()>>> =
32        RefCell::new(Vec::new());
33}
34
35struct ReservationWaitProgressScope;
36
37impl Drop for ReservationWaitProgressScope {
38    fn drop(&mut self) {
39        RESERVATION_WAIT_PROGRESS.with(|callbacks| {
40            drop(
41                callbacks
42                    .borrow_mut()
43                    .pop()
44                    .expect("reservation wait progress scope remains installed"),
45            );
46        });
47    }
48}
49
50pub(crate) fn with_reservation_wait_progress<T>(
51    progress: impl FnMut() + 'static,
52    operation: impl FnOnce() -> T,
53) -> T {
54    RESERVATION_WAIT_PROGRESS.with(|callbacks| {
55        callbacks.borrow_mut().push(Box::new(progress));
56    });
57    let _scope = ReservationWaitProgressScope;
58    operation()
59}
60
61fn tick_reservation_wait_progress() {
62    RESERVATION_WAIT_PROGRESS.with(|callbacks| {
63        if let Some(progress) = callbacks.borrow_mut().last_mut() {
64            progress();
65        }
66    });
67}
68
69fn reservation_wait_progress_poll() -> Option<std::time::Duration> {
70    RESERVATION_WAIT_PROGRESS.with(|callbacks| {
71        (!callbacks.borrow().is_empty()).then_some(RESERVATION_WAIT_PROGRESS_POLL)
72    })
73}
74
75/// Resource contention error — LLC slots or CPUs unavailable.
76/// Downcast via `anyhow::Error::downcast_ref::<ResourceContention>()`
77/// to distinguish from fatal errors.
78#[derive(Debug, thiserror::Error)]
79#[error("{reason}")]
80pub struct ResourceContention {
81    pub reason: String,
82}
83
84/// The requested topology cannot be realized on this host, and no retry
85/// changes that. Surfaced as a SKIP by the x86_64 VM-creation caps (guest
86/// RAM top above the host MAXPHYADDR, vCPU count above KVM_CAP_MAX_VCPUS,
87/// or max APIC id at/above KVM_CAP_MAX_VCPU_ID): these fire for ANY VM of
88/// this shape, perf-mode or not, so the test cannot run here. Also
89/// returned by the `performance_mode` topology planner when the
90/// host has too few physical CPUs / LLC groups — but that perf-mode caller
91/// RE-MAPS it to [`PerfModeUnavailable`] (a host-insufficiency: skip by
92/// default, fail under `KTSTR_NO_SKIP_MODE`). Also raised by
93/// `resolve_cpu_budget` when an author's per-test `cpu_budget` exceeds the
94/// allowed-CPU count — the author-attribute half of a provenance split (a
95/// capability requirement a bigger host satisfies → skip), mirroring the
96/// operator-knob half [`CpuBudgetUnsatisfiable`] (a concrete `--cpu-cap`
97/// number the host cannot satisfy → hard fail). Distinct
98/// from [`ResourceContention`] (a transient slot/resource shortage a retry
99/// resolves → skip); a too-small host is permanent, so the operator must
100/// provision different hardware or narrow the topology rather than retry.
101///
102/// Downcast via `anyhow::Error::downcast_ref::<TopologyInsufficient>()`
103/// (chain-aware: the `#[ktstr_test]` dispatch and `skip_on_contention!`
104/// walk the full error chain so a `.context(...)`-wrapped instance is
105/// still recognised). This typed error replaced a fragile message
106/// string-match (`"need"` + `"LLC"`/`"CPU"`) that would misclassify any
107/// unrelated error happening to contain those words.
108#[derive(Debug, thiserror::Error)]
109#[error("{reason}")]
110pub struct TopologyInsufficient {
111    pub reason: String,
112}
113
114/// The host cannot honor the `performance_mode` guarantee (an exclusive
115/// host LLC for the test's virtual LLC topology + a service CPU), and no
116/// retry changes that — a permanent host-insufficiency (e.g. a single-LLC
117/// host whose LLC spans every CPU, so LLC + 1 service never fits). Treated
118/// like [`TopologyInsufficient`] / [`ResourceContention`]: a SKIP by
119/// default (the VM never runs unisolated — it errors at build, so a
120/// visible skip informs the operator without reddening CI on a host that
121/// can never satisfy perf-mode), promoted to a hard FAIL under
122/// `KTSTR_NO_SKIP_MODE` for runs that demand perf-mode execution. The
123/// remedy is unchanged: provision a host with a spare LLC/CPU, narrow the
124/// topology, or drop `--perf-mode`.
125///
126/// Downcast via `anyhow::Error::downcast_ref::<PerfModeUnavailable>()`
127/// (chain-aware: the dispatch + macro predicates walk the full error
128/// chain, so a `.context(...)`-wrapped instance is still recognised).
129#[derive(Debug, thiserror::Error)]
130#[error("{reason}")]
131pub struct PerfModeUnavailable {
132    pub reason: String,
133}
134
135/// An operator `--cpu-cap N` (or `KTSTR_CPU_CAP`) the host cannot satisfy: N
136/// exceeds the CPUs this process is allowed on. A HARD ERROR, not a skip —
137/// the operator typed a concrete number that does not exist on this host (a
138/// user-input error). This is the OPERATOR-knob half of a provenance split:
139/// an author's per-test `cpu_budget` over the allowance is instead a
140/// [`TopologyInsufficient`] SKIP (a capability request a bigger host would
141/// satisfy), raised in `resolve_cpu_budget`. Contrast [`ResourceContention`]
142/// (a transient shortage of an otherwise-satisfiable budget → skip/retry).
143///
144/// Downcast via `anyhow::Error::downcast_ref::<CpuBudgetUnsatisfiable>()`
145/// (chain-aware).
146#[derive(Debug, thiserror::Error)]
147#[error("{reason}")]
148pub struct CpuBudgetUnsatisfiable {
149    pub reason: String,
150}
151
152/// The requested topology cannot be represented by this VMM's static
153/// device layout, and the limit is host-INDEPENDENT, so no retry and no
154/// different host changes that. Concretely: the aarch64 vCPU count
155/// exceeds `MAX_VCPUS` (the capacity of the statically sized GICv3
156/// redistributor MMIO window) — with more vCPUs the redistributor region
157/// overruns the device MMIO window and shadows serial/virtio.
158///
159/// A HARD ERROR — distinct from [`TopologyInsufficient`], its deliberate
160/// counterpart. `TopologyInsufficient` is host-DEPENDENT (the VM cannot
161/// boot on *this* host, but a bigger host could → skip);
162/// `TopologyUnrepresentable` is a fixed VMM-layout limit no aarch64 host
163/// can satisfy under this VMM, so it is a test misconfiguration — the
164/// author must narrow the topology, not provision different hardware.
165/// Routes to `EXIT_FAIL` via a DEDICATED hard-fail arm (the
166/// `is_topology_unrepresentable` predicate) in both `result_to_exit_code`
167/// and the `#[ktstr_test]` macro body, placed ABOVE the `expect_err`
168/// inversion and the skip arms — mirroring `CpuBudgetUnsatisfiable` (the
169/// other dedicated hard-fail). That placement is what makes it fail even in
170/// an `expect_err` test (the generic `expect_err` arm would otherwise
171/// invert it to a pass) and keeps it out of the `skip_on_contention!` /
172/// `is_topology_insufficient` skip paths, so the misconfiguration can
173/// never masquerade as the expected failure or be turned into a skip.
174///
175/// Downcast via `anyhow::Error::downcast_ref::<TopologyUnrepresentable>()`
176/// (chain-aware: walks `e.chain()`, so a `.context(...)`-wrapped instance
177/// is still recognised) to identify it programmatically — e.g. tests
178/// asserting the over-`MAX_VCPUS` bail is this hard-fault and not a bare
179/// string-matched error.
180// Constructed only on aarch64 (the GICv3-layout over-MAX_VCPUS bail in
181// aarch64::kvm) and in cross-arch routing tests; a non-aarch64 lib-only
182// build sees no construction site. Keep the dead-code check live on
183// aarch64 (where the bail MUST construct it — a real regression if it
184// stops) and allow it only off-arch.
185#[cfg_attr(not(target_arch = "aarch64"), allow(dead_code))]
186#[derive(Debug, thiserror::Error)]
187#[error("{reason}")]
188pub struct TopologyUnrepresentable {
189    pub reason: String,
190}
191
192/// A physical LLC group on the host, identified by its cache ID.
193#[derive(Debug, Clone)]
194pub struct LlcGroup {
195    /// CPUs sharing this LLC.
196    pub cpus: Vec<usize>,
197}
198
199/// Host CPU topology: LLC groups, NUMA nodes, and online CPU set.
200#[derive(Debug, Clone)]
201pub struct HostTopology {
202    /// LLC groups indexed by their order of discovery.
203    pub llc_groups: Vec<LlcGroup>,
204    /// All online CPUs.
205    pub online_cpus: Vec<usize>,
206    /// NUMA node ID for each online CPU, indexed by CPU ID.
207    /// CPUs not in the map default to node 0.
208    pub cpu_to_node: std::collections::HashMap<usize, usize>,
209    /// LLC indices grouped by their NUMA node. Memoized at construction
210    /// time from `llc_groups + cpu_to_node` so repeated NUMA-aware
211    /// placement queries (perf-mode rotation, `--cpu-cap` consolidation
212    /// PLAN) don't re-walk every LLC's CPU list on every call. Access
213    /// `BTreeMap` (not `HashMap`) gives deterministic iteration order — two ktstr
214    /// invocations on the same host MUST produce identical LLC
215    /// selections so their ACQUIRE phases converge on the same indices.
216    pub(crate) host_node_llcs: std::collections::BTreeMap<usize, Vec<usize>>,
217}
218
219/// Pinning plan: maps each vCPU index to a host CPU, plus a dedicated
220/// CPU for service threads (monitor, watchdog).
221#[derive(Debug)]
222pub struct PinningPlan {
223    /// vcpu_index -> host_cpu
224    pub assignments: Vec<(u32, usize)>,
225    /// Dedicated host CPU for monitor/watchdog threads. Set when
226    /// the planner selects performance-mode isolation.
227    pub service_cpu: Option<usize>,
228    /// Host LLC group indices used by this plan, sorted.
229    pub llc_indices: Vec<usize>,
230    /// Held flock fds for resource reservation. Dropped when the plan
231    /// (and the KtstrVm holding it) is dropped, releasing all locks.
232    #[allow(dead_code)] // RAII: flock fds released on Drop, not read after construction.
233    pub(crate) locks: protocol::Acquired<Vec<protocol::AdmissionFlock>>,
234}
235
236/// Which run path is asking the shared topology planner for placements.
237#[derive(Debug, Clone, Copy, PartialEq, Eq)]
238pub(crate) enum PinningKind {
239    /// Opportunistic default 1:1 candidates first prove their assigned CPUs
240    /// are unshared, then retain only shared CPU/LLC ownership for the run.
241    /// The exact pinning shape is an optimization, not exclusion: later
242    /// default, no-perf, and build work may overlap it.
243    Default,
244    /// Performance runs additionally reserve a service CPU and choose whole
245    /// LLC or CPU-grain isolation from the occupied cache domains.
246    Performance,
247}
248
249/// Non-authoritative, mode-aware availability snapshot used to order one
250/// bounded planner pass. Complete registry claims and flocks remain the
251/// authority; these sets only steer the matcher toward resources the
252/// coordinator just observed ready.
253#[derive(Clone, Copy)]
254pub(crate) struct PinningPreferences<'a> {
255    pub(crate) cpus: &'a std::collections::BTreeSet<usize>,
256    pub(crate) shared_llcs: &'a std::collections::BTreeSet<usize>,
257    pub(crate) exclusive_llcs: &'a std::collections::BTreeSet<usize>,
258}
259
260/// One exact placement and its complete reservation footprint.
261///
262/// Keeping the CPU footprint beside the plan is important for whole-LLC
263/// performance reservations: those take both the LLC EX lock and CPU EX locks
264/// for every CPU in that domain (including siblings outside this process's
265/// cpuset). The CPU locks are the admission
266/// bridge to topology-unavailable overcommitters, which can name CPUs but not
267/// LLCs.
268pub(crate) struct PerformancePinningCandidate {
269    pub(crate) plan: PinningPlan,
270    pub(crate) llc_mode: LlcLockMode,
271    pub(crate) cpu_mode: FlockMode,
272    pub(crate) cpu_reservations: Vec<usize>,
273}
274
275impl PerformancePinningCandidate {
276    #[cfg(test)]
277    pub(crate) fn claim(&self) -> protocol::ClaimSet {
278        resource_claim_with_modes(
279            &self.plan.llc_indices,
280            self.llc_mode,
281            &self.cpu_reservations,
282            self.cpu_mode,
283        )
284    }
285}
286
287#[derive(Debug, Clone, Copy)]
288struct GuestLlcDemand {
289    guest_llc: u32,
290    guest_node: u32,
291    vcpu_start: u32,
292    cpus: usize,
293}
294
295#[derive(Clone, Copy)]
296struct PlannerInputs<'a> {
297    demands: &'a [GuestLlcDemand],
298    kind: PinningKind,
299    allowed: &'a std::collections::BTreeSet<usize>,
300    allowed_rank: &'a std::collections::BTreeMap<usize, usize>,
301    preferred_cpus: &'a std::collections::BTreeSet<usize>,
302    preferred_shared_llcs: &'a std::collections::BTreeSet<usize>,
303    preferred_exclusive_llcs: &'a std::collections::BTreeSet<usize>,
304    performance_prefers_shared: bool,
305}
306
307impl PinningPlan {
308    /// Duplicate the plan's DESCRIPTION (assignments, service CPU,
309    /// LLC indices) with an EMPTY lock set. `PinningPlan` cannot be
310    /// `Clone` — the fds are RAII lock holders — but candidate plans
311    /// (pure topology-planner output, no locks yet) need copying
312    /// between the fast path's scan list and the acquired result.
313    pub(crate) fn clone_unlocked(&self) -> PinningPlan {
314        PinningPlan {
315            assignments: self.assignments.clone(),
316            service_cpu: self.service_cpu,
317            llc_indices: self.llc_indices.clone(),
318            locks: protocol::Acquired::untracked(Vec::new()),
319        }
320    }
321}
322
323/// Process-wide cache for [`HostTopology::cached`]. Only
324/// populated on success — a failed sysfs probe retries on the
325/// next call instead of poisoning the cache.
326static CACHED_HOST_TOPOLOGY: std::sync::OnceLock<HostTopology> = std::sync::OnceLock::new();
327
328fn validate_llc_partition(llc_groups: &[LlcGroup], online_cpus: &[usize]) -> Result<()> {
329    if online_cpus.is_empty() {
330        anyhow::bail!("host CPU discovery returned an empty online CPU set");
331    }
332    if llc_groups.is_empty() {
333        anyhow::bail!("host LLC discovery returned zero LLC groups");
334    }
335    let online = online_cpus
336        .iter()
337        .copied()
338        .collect::<std::collections::BTreeSet<_>>();
339    if online.len() != online_cpus.len() {
340        anyhow::bail!("online CPU discovery contains duplicate CPU IDs");
341    }
342
343    let mut partition = std::collections::BTreeSet::new();
344    for (llc, group) in llc_groups.iter().enumerate() {
345        if group.cpus.is_empty() {
346            anyhow::bail!("host LLC group {llc} is empty");
347        }
348        let mut within = std::collections::BTreeSet::new();
349        for &cpu in &group.cpus {
350            if !within.insert(cpu) {
351                anyhow::bail!("host LLC group {llc} repeats CPU {cpu}");
352            }
353            if !online.contains(&cpu) {
354                anyhow::bail!("host LLC group {llc} contains non-online CPU {cpu}");
355            }
356            if !partition.insert(cpu) {
357                anyhow::bail!("online CPU {cpu} appears in more than one host LLC group");
358            }
359        }
360    }
361    if partition != online {
362        let missing = online.difference(&partition).copied().collect::<Vec<_>>();
363        anyhow::bail!("host LLC groups omit online CPUs {missing:?}");
364    }
365    Ok(())
366}
367
368impl HostTopology {
369    /// Read the host-global physical topology from sysfs. Per-process affinity
370    /// is applied later by placement, never while assigning LLC lock identity.
371    pub fn from_sysfs() -> Result<Self> {
372        let topo = crate::topology::TestTopology::from_system_unfiltered()
373            .context("read host-global topology from sysfs")?;
374        let online_cpus = topo.all_cpus().to_vec();
375        let llc_groups: Vec<LlcGroup> = topo
376            .llcs()
377            .iter()
378            .map(|llc| LlcGroup {
379                cpus: llc.cpus().to_vec(),
380            })
381            .collect();
382        validate_llc_partition(&llc_groups, &online_cpus)
383            .context("host LLC discovery did not produce an exact CPU partition")?;
384        let cpu_to_node: std::collections::HashMap<usize, usize> = topo
385            .llcs()
386            .iter()
387            .flat_map(|llc| llc.cpus().iter().map(|&cpu| (cpu, llc.numa_node())))
388            .collect();
389        let host_node_llcs = Self::compute_host_node_llcs(&llc_groups, &cpu_to_node);
390        Ok(Self {
391            llc_groups,
392            online_cpus,
393            cpu_to_node,
394            host_node_llcs,
395        })
396    }
397
398    /// Return a cached host topology, populating the cache on first
399    /// successful call. Failed reads retry on the next call — the
400    /// cache only stores success so a transient sysfs issue at
401    /// process start doesn't poison every subsequent build().
402    pub fn cached() -> Result<Self> {
403        if let Some(topo) = CACHED_HOST_TOPOLOGY.get() {
404            return Ok(topo.clone());
405        }
406        let topo = Self::from_sysfs()?;
407        let _ = CACHED_HOST_TOPOLOGY.set(topo.clone());
408        Ok(topo)
409    }
410
411    /// Build a synthetic `HostTopology` from `(cpu_list, node_id)`
412    /// pairs for tests. One pair per LLC group; within a pair the
413    /// `cpu_list` becomes the group's CPUs and the `node_id` is the
414    /// NUMA node every CPU in that group is assigned to.
415    /// `online_cpus` is the flattened concatenation of every group's
416    /// CPUs in input order; `cpu_to_node` is built by broadcasting
417    /// each group's node over its CPUs; `host_node_llcs` goes through
418    /// the same [`compute_host_node_llcs`] path production uses, so
419    /// tests never diverge from the sysfs-derived memoization.
420    ///
421    /// Intended for test fixtures that want a deterministic in-memory
422    /// topology without stubbing `/sys/devices/system/cpu/*`.
423    /// Previously this logic was duplicated across three helper
424    /// functions (`synthetic_topo`, `synthetic_topo_numa`,
425    /// `synth_host_topo`) — consolidated here so the
426    /// `HostTopology` invariant is maintained in one place. The
427    /// `#[cfg(test)]` gate keeps the symbol out of release builds.
428    #[cfg(test)]
429    pub(crate) fn new_for_tests(groups: &[(Vec<usize>, usize)]) -> Self {
430        let topology = Self::new_for_tests_unchecked(groups);
431        validate_llc_partition(&topology.llc_groups, &topology.online_cpus)
432            .expect("synthetic host LLC groups must exactly partition online CPUs");
433        topology
434    }
435
436    /// Build an intentionally malformed synthetic topology for focused tests
437    /// of discovery validation and CPU-union behavior. Topology-planner tests
438    /// use [`Self::new_for_tests`], whose disjoint-partition invariant matches
439    /// sysfs discovery.
440    #[cfg(test)]
441    pub(crate) fn new_for_tests_unchecked(groups: &[(Vec<usize>, usize)]) -> Self {
442        let llc_groups: Vec<LlcGroup> = groups
443            .iter()
444            .map(|(cpus, _)| LlcGroup { cpus: cpus.clone() })
445            .collect();
446        let cpu_to_node: std::collections::HashMap<usize, usize> = groups
447            .iter()
448            .flat_map(|(cpus, node)| cpus.iter().map(move |&cpu| (cpu, *node)))
449            .collect();
450        let online_cpus: Vec<usize> = groups
451            .iter()
452            .flat_map(|(cpus, _)| cpus.iter().copied())
453            .collect();
454        let host_node_llcs = HostTopology::compute_host_node_llcs(&llc_groups, &cpu_to_node);
455        HostTopology {
456            llc_groups,
457            online_cpus,
458            cpu_to_node,
459            host_node_llcs,
460        }
461    }
462
463    /// Compute the memoized `host_node_llcs` map from `llc_groups` +
464    /// `cpu_to_node`. Uses the same majority-vote NUMA-assignment rule
465    /// as [`Self::llc_numa_node`], so the memoized map and the one-off query
466    /// method never disagree. Separate fn (not inlined) so
467    /// `from_sysfs` and synthetic-test constructors share one path.
468    fn compute_host_node_llcs(
469        llc_groups: &[LlcGroup],
470        cpu_to_node: &std::collections::HashMap<usize, usize>,
471    ) -> std::collections::BTreeMap<usize, Vec<usize>> {
472        let mut node_llcs: std::collections::BTreeMap<usize, Vec<usize>> =
473            std::collections::BTreeMap::new();
474        for (idx, group) in llc_groups.iter().enumerate() {
475            // Majority-vote NUMA node for this LLC — matches
476            // `llc_numa_node` exactly. We inline the logic here rather
477            // than calling the method because we don't yet have `self`.
478            let mut counts: std::collections::HashMap<usize, usize> =
479                std::collections::HashMap::new();
480            for &cpu in &group.cpus {
481                let node = cpu_to_node.get(&cpu).copied().unwrap_or(0);
482                *counts.entry(node).or_insert(0) += 1;
483            }
484            let node = counts
485                .into_iter()
486                .max_by_key(|&(_, count)| count)
487                .map(|(node, _)| node)
488                .unwrap_or(0);
489            node_llcs.entry(node).or_default().push(idx);
490        }
491        // Within-node LLC ordering: ascending llc_idx. Callers that
492        // walk `host_node_llcs[node]` rely on this for deterministic
493        // output — two ktstr invocations with identical topology see
494        // the same walk order.
495        for llcs in node_llcs.values_mut() {
496            llcs.sort_unstable();
497        }
498        node_llcs
499    }
500
501    /// Maximum cores per LLC group on the host.
502    pub fn max_cores_per_llc(&self) -> usize {
503        self.llc_groups
504            .iter()
505            .map(|g| g.cpus.len())
506            .max()
507            .unwrap_or(0)
508    }
509
510    /// Total available host CPUs.
511    #[cfg(test)]
512    pub fn total_cpus(&self) -> usize {
513        self.online_cpus.len()
514    }
515
516    // ------------------------------------------------------------------
517    // Shared NUMA-placement primitives
518    // ------------------------------------------------------------------
519    //
520    // Used by the bounded topology planner and `--cpu-cap` consolidation.
521
522    /// Memoized map of NUMA node → LLC indices on that node. Returned
523    /// by reference so callers can iterate without cloning; `BTreeMap`
524    /// gives deterministic iteration so two invocations on identical
525    /// topologies produce identical walks.
526    ///
527    /// Test fixtures use this to assert the same memoized map production
528    /// placement traverses.
529    #[cfg(test)]
530    pub(crate) fn host_llcs_by_numa_node(&self) -> &std::collections::BTreeMap<usize, Vec<usize>> {
531        &self.host_node_llcs
532    }
533
534    /// Return NUMA node ids sorted by distance from `anchor` ascending,
535    /// with unreachable nodes (distance 255 per Linux convention)
536    /// demoted to the end. Caller supplies the distance lookup via
537    /// `distance_fn` so this primitive stays independent of any
538    /// specific distance source — consolidation threads
539    /// `TestTopology::numa_distance` through a closure, while callers
540    /// without a distance matrix can pass
541    /// `|from, to| if from == to { 10 } else { 20 }` for a trivial
542    /// near/far split.
543    ///
544    /// `anchor` is included in the output (distance to self = 10 on
545    /// the Linux convention, sorting first). Nodes without any LLCs
546    /// on this host are skipped — spilling to an empty node has no
547    /// value.
548    pub(crate) fn numa_nodes_sorted_by_distance(
549        &self,
550        anchor: usize,
551        distance_fn: impl Fn(usize, usize) -> u8,
552    ) -> Vec<usize> {
553        let mut nodes: Vec<(usize, u8)> = self
554            .host_node_llcs
555            .keys()
556            .map(|&node| (node, distance_fn(anchor, node)))
557            .collect();
558        // Sort: unreachable (255) last; among reachable, ascending
559        // distance; ties broken by ascending node id via the stable
560        // sort applied over a pre-sorted (BTreeMap-ordered) input.
561        nodes.sort_by(|a, b| {
562            let a_unreachable = a.1 == 255;
563            let b_unreachable = b.1 == 255;
564            match (a_unreachable, b_unreachable) {
565                (true, false) => std::cmp::Ordering::Greater,
566                (false, true) => std::cmp::Ordering::Less,
567                _ => a.1.cmp(&b.1),
568            }
569        });
570        nodes.into_iter().map(|(node, _)| node).collect()
571    }
572
573    /// NUMA node for a host LLC group, determined by majority vote of
574    /// its CPUs' NUMA assignments. Returns 0 when the map is empty
575    /// (single-node systems).
576    ///
577    /// Bulk placement traverses the memoized [`host_node_llcs`](Self::host_node_llcs)
578    /// map; this one-off query is used where a selected LLC's node is needed.
579    pub fn llc_numa_node(&self, llc_idx: usize) -> usize {
580        let group = &self.llc_groups[llc_idx];
581        let mut counts: std::collections::HashMap<usize, usize> = std::collections::HashMap::new();
582        for &cpu in &group.cpus {
583            let node = self.cpu_to_node.get(&cpu).copied().unwrap_or(0);
584            *counts.entry(node).or_insert(0) += 1;
585        }
586        counts
587            .into_iter()
588            .max_by_key(|&(_, count)| count)
589            .map(|(node, _)| node)
590            .unwrap_or(0)
591    }
592
593    /// Enumerate performance placements against the synthetic topology's CPU
594    /// set. Production uses [`Self::performance_pinning_candidates_for_cpus`]
595    /// with the process affinity set; this wrapper keeps topology-only tests
596    /// independent of the machine running them.
597    #[cfg(test)]
598    pub(crate) fn performance_pinning_candidates(
599        &self,
600        topo: &super::topology::Topology,
601    ) -> Result<Vec<PerformancePinningCandidate>> {
602        self.topology_pinning_candidates(topo, PinningKind::Performance, &self.online_cpus, None)
603    }
604
605    /// Physical CPUs retained for build, default, and no-perf progress while
606    /// performance-mode cells are active.
607    ///
608    /// This is a deterministic topology partition, not a rotating admission
609    /// preference. Every process with the same allowed CPU set derives the
610    /// same reserve. Modest LLCs are indivisible because a performance claim
611    /// on any CPU in one expands to whole-LLC exclusion. Genuinely huge LLCs
612    /// already support CPU-grain performance claims, so their reserve is
613    /// selected one CPU at a time. Selection advances once per NUMA node per
614    /// round to avoid concentrating the retained capacity on one socket.
615    ///
616    /// At least two allowed CPUs remain available to performance mode. If an
617    /// indivisible LLC is the whole small host, reserving it would leave no
618    /// usable performance placement, so that host deliberately has an empty
619    /// physical reserve rather than silently disabling performance mode.
620    pub(crate) fn performance_reserved_cpus(
621        &self,
622        allowed_cpus: &[usize],
623    ) -> std::collections::BTreeSet<usize> {
624        use std::collections::{BTreeMap, BTreeSet};
625
626        let allowed = allowed_cpus.iter().copied().collect::<BTreeSet<_>>();
627        let mut units_by_node = BTreeMap::<usize, Vec<Vec<usize>>>::new();
628        let mut physical_allowed = 0usize;
629        for (llc, group) in self.llc_groups.iter().enumerate() {
630            let mut cpus = group
631                .cpus
632                .iter()
633                .copied()
634                .filter(|cpu| allowed.contains(cpu))
635                .collect::<Vec<_>>();
636            cpus.sort_unstable();
637            cpus.dedup();
638            physical_allowed = physical_allowed.saturating_add(cpus.len());
639            if cpus.is_empty() {
640                continue;
641            }
642            if group.cpus.len() < PERF_GRAIN_LLC_MIN_CPUS {
643                units_by_node
644                    .entry(self.llc_numa_node(llc))
645                    .or_default()
646                    .push(cpus);
647            } else {
648                for cpu in cpus {
649                    let node = self
650                        .cpu_to_node
651                        .get(&cpu)
652                        .copied()
653                        .unwrap_or_else(|| self.llc_numa_node(llc));
654                    units_by_node.entry(node).or_default().push(vec![cpu]);
655                }
656            }
657        }
658
659        let maximum = physical_allowed.saturating_sub(2);
660        let target = physical_allowed
661            .saturating_mul(BUILD_RESERVED_PERCENT)
662            .div_ceil(100)
663            .min(maximum);
664        if target == 0 {
665            return BTreeSet::new();
666        }
667
668        let mut next_by_node = units_by_node
669            .keys()
670            .copied()
671            .map(|node| (node, 0usize))
672            .collect::<BTreeMap<_, _>>();
673        let mut reserved = BTreeSet::new();
674        while reserved.len() < target {
675            let mut advanced = false;
676            for (&node, units) in &units_by_node {
677                let next = next_by_node
678                    .get_mut(&node)
679                    .expect("reserve cursor exists for every NUMA node");
680                while let Some(unit) = units.get(*next) {
681                    *next += 1;
682                    if reserved.len().saturating_add(unit.len()) > maximum {
683                        continue;
684                    }
685                    reserved.extend(unit.iter().copied());
686                    advanced = true;
687                    break;
688                }
689                if reserved.len() >= target {
690                    break;
691                }
692            }
693            if !advanced {
694                break;
695            }
696        }
697        reserved
698    }
699
700    /// Enumerate performance placements using only CPUs allowed by the
701    /// caller's affinity/cgroup. Ownership-free build mapping and run-time
702    /// admission both call this exact entry point.
703    pub(crate) fn performance_pinning_candidates_for_cpus(
704        &self,
705        topo: &super::topology::Topology,
706        allowed_cpus: &[usize],
707    ) -> Result<Vec<PerformancePinningCandidate>> {
708        let reserved = self.performance_reserved_cpus(allowed_cpus);
709        let performance_cpus = allowed_cpus
710            .iter()
711            .copied()
712            .filter(|cpu| !reserved.contains(cpu))
713            .collect::<Vec<_>>();
714        let mut candidates = self.topology_pinning_candidates(
715            topo,
716            PinningKind::Performance,
717            &performance_cpus,
718            None,
719        )?;
720        // A whole-LLC EX claim expands beyond the CPUs used to construct the
721        // plan. Filter the final physical lock footprint, not merely its vCPU
722        // assignments, so whole-LLC and CPU-grain claims preserve one shared
723        // reserve invariant.
724        candidates.retain(|candidate| {
725            candidate
726                .cpu_reservations
727                .iter()
728                .all(|cpu| !reserved.contains(cpu))
729        });
730        if candidates.is_empty() {
731            return Err(anyhow::Error::new(TopologyInsufficient {
732                reason: "no performance placement preserves reserved host capacity".into(),
733            }));
734        }
735        Ok(candidates)
736    }
737
738    /// Enumerate opportunistic default 1:1 placements using the same mapper as
739    /// performance mode. The policy differences are no service CPU and shared
740    /// LLC ownership. Failure to acquire one falls through to shared
741    /// admission instead of changing the guest topology.
742    pub(crate) fn default_pinning_candidates_for_cpus(
743        &self,
744        topo: &super::topology::Topology,
745        allowed_cpus: &[usize],
746    ) -> Result<Vec<PerformancePinningCandidate>> {
747        self.topology_pinning_candidates(topo, PinningKind::Default, allowed_cpus, None)
748    }
749
750    /// Bounded availability-aware topology planner.
751    ///
752    /// The old enumerator multiplied several unrelated rotation periods with
753    /// LCM and then nested an open-ended intra-LLC window loop. Coprime host
754    /// shapes could therefore perform enormous work before deduplication. This
755    /// planner evaluates at most one seed per actual allowed CPU (or host LLC
756    /// when larger), and canonical claim deduplication bounds its output by
757    /// that same physical-resource count.
758    ///
759    /// Each guest LLC contributes its real demand (`llc_cores[i] * threads`).
760    /// Largest demands claim distinct fitting host LLC bins first. When both
761    /// sides expose usable NUMA information, a bipartite match maps each
762    /// CPU-bearing guest node to a distinct host node and bins are selected
763    /// within that node. If no complete strict match exists, the planner
764    /// deliberately falls back once to a global distinct-LLC match: running
765    /// with correct CPU/LLC identity is preferable to rejecting a host solely
766    /// because its NUMA/cache geometry cannot mirror the guest.
767    ///
768    /// `preferences` is a non-authoritative, mode-aware availability snapshot.
769    /// Exact placement prefers its CPUs and LLC modes but may use the
770    /// remainder; final admission still validates the complete claim under the
771    /// registry fence. Supplying fragmented preferences therefore yields one
772    /// exact globally-distinct plan rather than requiring a contiguous free
773    /// window.
774    pub(crate) fn topology_pinning_candidates(
775        &self,
776        topo: &super::topology::Topology,
777        kind: PinningKind,
778        allowed_cpus: &[usize],
779        preferences: Option<PinningPreferences<'_>>,
780    ) -> Result<Vec<PerformancePinningCandidate>> {
781        use std::collections::BTreeSet;
782
783        let allowed = allowed_cpus.iter().copied().collect::<BTreeSet<_>>();
784        let total_needed =
785            topo.total_cpus() as usize + usize::from(kind == PinningKind::Performance);
786        if total_needed > allowed.len() {
787            return Err(anyhow::Error::new(TopologyInsufficient {
788                reason: format!(
789                    "{}: need {total_needed} distinct host CPUs but only {} are allowed",
790                    if kind == PinningKind::Performance {
791                        "performance_mode"
792                    } else {
793                        "default pinning"
794                    },
795                    allowed.len(),
796                ),
797            }));
798        }
799        if topo.llcs as usize > self.llc_groups.len() {
800            return Err(anyhow::Error::new(TopologyInsufficient {
801                reason: format!(
802                    "need {} distinct host LLC groups for {} guest LLCs, but host has {}",
803                    topo.llcs,
804                    topo.llcs,
805                    self.llc_groups.len(),
806                ),
807            }));
808        }
809
810        let mut vcpu_start = 0u32;
811        let demands = (0..topo.llcs)
812            .map(|guest_llc| {
813                let cpus = topo
814                    .cores_in_llc(guest_llc)
815                    .saturating_mul(topo.threads_per_core) as usize;
816                let demand = GuestLlcDemand {
817                    guest_llc,
818                    guest_node: topo.numa_node_of(guest_llc),
819                    vcpu_start,
820                    cpus,
821                };
822                vcpu_start = vcpu_start.saturating_add(cpus as u32);
823                demand
824            })
825            .collect::<Vec<_>>();
826        if demands.iter().any(|demand| demand.cpus == 0) {
827            return Err(anyhow::Error::new(TopologyInsufficient {
828                reason: "guest topology contains an empty LLC CPU demand".into(),
829            }));
830        }
831        let performance_prefers_shared =
832            kind == PinningKind::Performance && grain_mapping_possible(self, &demands, &allowed);
833
834        let all_llcs = (0..self.llc_groups.len()).collect::<BTreeSet<_>>();
835        let (preferred_cpus, preferred_shared_llcs, preferred_exclusive_llcs) = match preferences {
836            Some(preferences) => (
837                preferences.cpus,
838                preferences.shared_llcs,
839                preferences.exclusive_llcs,
840            ),
841            None => (&allowed, &all_llcs, &all_llcs),
842        };
843        let allowed_rank = allowed
844            .iter()
845            .copied()
846            .enumerate()
847            .map(|(rank, cpu)| (cpu, rank))
848            .collect::<std::collections::BTreeMap<_, _>>();
849        let inputs = PlannerInputs {
850            demands: &demands,
851            kind,
852            allowed: &allowed,
853            allowed_rank: &allowed_rank,
854            preferred_cpus,
855            preferred_shared_llcs,
856            preferred_exclusive_llcs,
857            performance_prefers_shared,
858        };
859        let seeds = planner_seed_schedule(self, &demands, kind, &allowed);
860        let mut seen = BTreeSet::new();
861        let mut candidates = Vec::new();
862        for (seed, local_seed) in seeds {
863            let Some((plan, mut exact_cpus)) = self.plan_topology_seed(inputs, seed, local_seed)
864            else {
865                continue;
866            };
867            let llc_mode = match kind {
868                PinningKind::Default => LlcLockMode::Shared,
869                PinningKind::Performance => perf_llc_lock_mode(self, &plan),
870            };
871            if kind == PinningKind::Performance && llc_mode == LlcLockMode::Exclusive {
872                exact_cpus = plan
873                    .llc_indices
874                    .iter()
875                    .flat_map(|&llc| self.llc_groups[llc].cpus.iter().copied())
876                    .collect();
877            }
878            exact_cpus.sort_unstable();
879            exact_cpus.dedup();
880            let llc_tag = u8::from(llc_mode == LlcLockMode::Exclusive);
881            let identity = (llc_tag, plan.llc_indices.clone(), exact_cpus.clone());
882            if seen.insert(identity) {
883                candidates.push(PerformancePinningCandidate {
884                    plan,
885                    llc_mode,
886                    cpu_mode: FlockMode::Exclusive,
887                    cpu_reservations: exact_cpus,
888                });
889            }
890        }
891        if candidates.is_empty() {
892            return Err(anyhow::Error::new(TopologyInsufficient {
893                reason: "no exact distinct-LLC/CPU host placement fits".into(),
894            }));
895        }
896
897        // Claim identity, not seed traversal, defines uniqueness.
898        candidates.sort_by_key(|candidate| {
899            let availability_miss = preferences.is_some_and(|preferences| {
900                let llcs_ready = match candidate.llc_mode {
901                    LlcLockMode::Shared => candidate
902                        .plan
903                        .llc_indices
904                        .iter()
905                        .all(|llc| preferences.shared_llcs.contains(llc)),
906                    LlcLockMode::Exclusive => candidate
907                        .plan
908                        .llc_indices
909                        .iter()
910                        .all(|llc| preferences.exclusive_llcs.contains(llc)),
911                };
912                let cpus_ready = candidate.llc_mode == LlcLockMode::Exclusive
913                    || candidate
914                        .cpu_reservations
915                        .iter()
916                        .all(|cpu| preferences.cpus.contains(cpu));
917                !(llcs_ready && cpus_ready)
918            });
919            (
920                availability_miss,
921                u8::from(candidate.llc_mode == LlcLockMode::Exclusive),
922                candidate.plan.llc_indices.clone(),
923                candidate.cpu_reservations.clone(),
924            )
925        });
926        Ok(candidates)
927    }
928
929    /// Materialize one deterministic tie rotation of the bounded planner.
930    fn plan_topology_seed(
931        &self,
932        inputs: PlannerInputs<'_>,
933        seed: usize,
934        local_seed: usize,
935    ) -> Option<(PinningPlan, Vec<usize>)> {
936        use std::collections::{BTreeMap, BTreeSet};
937
938        let PlannerInputs {
939            demands,
940            kind,
941            allowed,
942            allowed_rank,
943            preferred_cpus,
944            preferred_shared_llcs,
945            preferred_exclusive_llcs,
946            performance_prefers_shared: _,
947        } = inputs;
948        let mut guest_nodes = BTreeMap::<u32, Vec<usize>>::new();
949        for (index, demand) in demands.iter().enumerate() {
950            guest_nodes
951                .entry(demand.guest_node)
952                .or_default()
953                .push(index);
954        }
955        let guest_node_rank = guest_nodes
956            .keys()
957            .copied()
958            .enumerate()
959            .map(|(rank, node)| (node, rank))
960            .collect::<BTreeMap<_, _>>();
961        let host_node_rank = self
962            .host_node_llcs
963            .keys()
964            .copied()
965            .enumerate()
966            .map(|(rank, node)| (node, rank))
967            .collect::<BTreeMap<_, _>>();
968
969        // First attempt a strict guest-node -> distinct host-node bipartite
970        // mapping. Feasibility is evaluated from the actual per-LLC CPU
971        // capacities after the process's allowed mask is applied.
972        let strict_nodes = if guest_nodes.len() > 1 && !self.cpu_to_node.is_empty() {
973            let mut edges = BTreeMap::<u32, Vec<usize>>::new();
974            let host_count = self.host_node_llcs.len().max(1);
975            for (&guest_node, request_indices) in &guest_nodes {
976                let mut hosts = self
977                    .host_node_llcs
978                    .iter()
979                    .filter_map(|(&host_node, llcs)| {
980                        host_bins_fit(self, demands, request_indices, llcs, allowed)
981                            .then_some(host_node)
982                    })
983                    .collect::<Vec<_>>();
984                hosts.sort_by_key(|host_node| {
985                    (
986                        !host_bins_preferred_fit(
987                            self,
988                            inputs,
989                            request_indices,
990                            &self.host_node_llcs[host_node],
991                        ),
992                        rotated_tie(host_node_rank[host_node], seed, host_count),
993                    )
994                });
995                edges.insert(guest_node, hosts);
996            }
997            match_distinct_nodes(&edges)
998        } else {
999            None
1000        };
1001
1002        let mut mapped = vec![usize::MAX; demands.len()];
1003        let mut used_llcs = BTreeSet::new();
1004        let strict_fit = strict_nodes.as_ref().is_some_and(|node_map| {
1005            let mut trial_mapped = mapped.clone();
1006            let mut trial_used = BTreeSet::new();
1007            let mut nodes = guest_nodes.keys().copied().collect::<Vec<_>>();
1008            nodes.sort_by_key(|guest_node| {
1009                let max_demand = guest_nodes
1010                    .get(guest_node)
1011                    .expect("guest node came from this map")
1012                    .iter()
1013                    .map(|&index| demands[index].cpus)
1014                    .max()
1015                    .unwrap_or(0);
1016                (
1017                    std::cmp::Reverse(max_demand),
1018                    rotated_tie(guest_node_rank[guest_node], seed, guest_nodes.len()),
1019                )
1020            });
1021            for guest_node in nodes {
1022                let host_node = node_map[&guest_node];
1023                let bins = &self.host_node_llcs[&host_node];
1024                if !assign_distinct_bins(
1025                    self,
1026                    inputs,
1027                    guest_nodes
1028                        .get(&guest_node)
1029                        .expect("guest node came from this map"),
1030                    bins,
1031                    seed,
1032                    &mut trial_used,
1033                    &mut trial_mapped,
1034                ) {
1035                    return false;
1036                }
1037            }
1038            mapped = trial_mapped;
1039            used_llcs = trial_used;
1040            true
1041        });
1042
1043        if !strict_fit {
1044            // Documented global fallback: strict NUMA mirroring is optional,
1045            // distinct cache bins and exact CPU identity are not.
1046            let all_requests = (0..demands.len()).collect::<Vec<_>>();
1047            let all_bins = (0..self.llc_groups.len()).collect::<Vec<_>>();
1048            if !assign_distinct_bins(
1049                self,
1050                inputs,
1051                &all_requests,
1052                &all_bins,
1053                seed,
1054                &mut used_llcs,
1055                &mut mapped,
1056            ) {
1057                return None;
1058            }
1059        }
1060
1061        // Each mapped LLC is distinct and host discovery validates LLC CPU
1062        // membership as a partition. Selecting the first demand-sized prefix
1063        // from each independently ordered bin is therefore globally distinct;
1064        // no recursive per-vCPU bipartite match is needed.
1065        let mut assignments = Vec::new();
1066        let mut occupied = BTreeSet::new();
1067        // Static candidates are capacity grains, not every overlapping cyclic
1068        // window. Advancing by the largest material footprint emits a
1069        // pairwise-disjoint family per LLC (for example twelve 3-CPU
1070        // vCPU+service grains on a 36-CPU domain). Availability-aware planning
1071        // can still synthesize an arbitrary fragmented footprint on demand.
1072        for (index, demand) in demands.iter().enumerate() {
1073            let llc = mapped[index];
1074            let mut cpus = self.llc_groups[llc]
1075                .cpus
1076                .iter()
1077                .copied()
1078                .filter(|cpu| allowed.contains(cpu))
1079                .collect::<Vec<_>>();
1080            cpus.sort_unstable();
1081            cpus.dedup();
1082            let local_rank = cpus
1083                .iter()
1084                .copied()
1085                .enumerate()
1086                .map(|(rank, cpu)| (cpu, rank))
1087                .collect::<BTreeMap<_, _>>();
1088            let cpu_count = cpus.len().max(1);
1089            cpus.sort_by_key(|cpu| {
1090                (
1091                    !preferred_cpus.contains(cpu),
1092                    rotated_tie(local_rank[cpu], local_seed, cpu_count),
1093                )
1094            });
1095            if cpus.len() < demand.cpus {
1096                return None;
1097            }
1098            for (local, cpu) in cpus.into_iter().take(demand.cpus).enumerate() {
1099                if !occupied.insert(cpu) {
1100                    // This is unreachable for a validated LLC partition and
1101                    // keeps intentionally malformed test fixtures from
1102                    // producing duplicate host CPU assignments.
1103                    return None;
1104                }
1105                assignments.push((demand.vcpu_start + local as u32, cpu));
1106            }
1107        }
1108        assignments.sort_unstable_by_key(|&(vcpu, _)| vcpu);
1109
1110        let service_cpu = if kind == PinningKind::Performance {
1111            let mut mapped_choice_rank = BTreeMap::<usize, (usize, usize)>::new();
1112            for (mapped_rank, &llc) in mapped.iter().enumerate() {
1113                let mut cpus = self.llc_groups[llc]
1114                    .cpus
1115                    .iter()
1116                    .copied()
1117                    .filter(|cpu| allowed.contains(cpu))
1118                    .collect::<Vec<_>>();
1119                cpus.sort_unstable();
1120                cpus.dedup();
1121                let count = cpus.len().max(1);
1122                for (rank, cpu) in cpus.into_iter().enumerate() {
1123                    let rank = (mapped_rank, rotated_tie(rank, local_seed, count));
1124                    mapped_choice_rank
1125                        .entry(cpu)
1126                        .and_modify(|current| *current = (*current).min(rank))
1127                        .or_insert(rank);
1128                }
1129            }
1130            // Include every allowed unoccupied host CPU. Locality is a
1131            // preference, not an eligibility gate: one busy mapped-local
1132            // leftover must not hide a free service CPU in another LLC.
1133            let mut service_choices = self
1134                .llc_groups
1135                .iter()
1136                .flat_map(|group| group.cpus.iter().copied())
1137                .filter(|cpu| allowed.contains(cpu) && !occupied.contains(cpu))
1138                .collect::<Vec<_>>();
1139            service_choices.sort_unstable();
1140            service_choices.dedup();
1141            service_choices.sort_by_key(|cpu| {
1142                let service_llcs = self
1143                    .llc_groups
1144                    .iter()
1145                    .enumerate()
1146                    .filter(|(_, group)| group.cpus.contains(cpu))
1147                    .map(|(llc, _)| llc)
1148                    .collect::<Vec<_>>();
1149                let candidate_prefers_shared = mapped.iter().enumerate().all(|(index, &llc)| {
1150                    let footprint = demands[index].cpus + usize::from(service_llcs.contains(&llc));
1151                    perf_grain_capable_for_footprint(self, llc, footprint)
1152                }) && service_llcs
1153                    .iter()
1154                    .filter(|&&llc| !mapped.contains(&llc))
1155                    .all(|&llc| perf_grain_capable_for_footprint(self, llc, 1));
1156                let llc_ready = mapped
1157                    .iter()
1158                    .copied()
1159                    .chain(service_llcs.iter().copied())
1160                    .all(|llc| {
1161                        if candidate_prefers_shared {
1162                            preferred_shared_llcs.contains(&llc)
1163                        } else {
1164                            preferred_exclusive_llcs.contains(&llc)
1165                        }
1166                    });
1167                let preferred = preferred_cpus.contains(cpu);
1168                let mapped_local = mapped_choice_rank.contains_key(cpu);
1169                (
1170                    !llc_ready,
1171                    !preferred,
1172                    !candidate_prefers_shared,
1173                    !mapped_local,
1174                    mapped_choice_rank.get(cpu).copied().unwrap_or((
1175                        usize::MAX,
1176                        rotated_tie(allowed_rank[cpu], seed, allowed.len().max(1)),
1177                    )),
1178                )
1179            });
1180            let cpu = *service_choices.first()?;
1181            occupied.insert(cpu);
1182            Some(cpu)
1183        } else {
1184            None
1185        };
1186
1187        let mut llc_indices = mapped;
1188        if let Some(service_cpu) = service_cpu {
1189            // Prefer an already-mapped cache domain. Discovery validates that
1190            // each CPU belongs to exactly one LLC, while the fallback keeps
1191            // this helper defensive for intentionally malformed test fixtures.
1192            let service_llc = llc_indices
1193                .iter()
1194                .copied()
1195                .find(|&llc| self.llc_groups[llc].cpus.contains(&service_cpu))
1196                .or_else(|| {
1197                    (0..self.llc_groups.len())
1198                        .filter(|&llc| self.llc_groups[llc].cpus.contains(&service_cpu))
1199                        .min_by_key(|&llc| rotated_tie(llc, seed, self.llc_groups.len().max(1)))
1200                })?;
1201            llc_indices.push(service_llc);
1202        }
1203        llc_indices.sort_unstable();
1204        llc_indices.dedup();
1205        let exact_cpus = occupied.into_iter().collect();
1206        Some((
1207            PinningPlan {
1208                assignments,
1209                service_cpu,
1210                llc_indices,
1211                locks: protocol::Acquired::untracked(Vec::new()),
1212            },
1213            exact_cpus,
1214        ))
1215    }
1216}
1217
1218fn rotated_tie(value: usize, seed: usize, cardinality: usize) -> usize {
1219    value
1220        .wrapping_add(cardinality)
1221        .wrapping_sub(seed % cardinality.max(1))
1222        % cardinality.max(1)
1223}
1224
1225fn planner_seed_schedule(
1226    host: &HostTopology,
1227    demands: &[GuestLlcDemand],
1228    kind: PinningKind,
1229    allowed: &std::collections::BTreeSet<usize>,
1230) -> Vec<(usize, usize)> {
1231    let stride = planner_local_stride(demands, kind);
1232    let minimum_demand = demands.iter().map(|demand| demand.cpus).min().unwrap_or(1);
1233    let mut seeds = host
1234        .llc_groups
1235        .iter()
1236        .enumerate()
1237        .flat_map(|(llc, group)| {
1238            let capacity = group
1239                .cpus
1240                .iter()
1241                .filter(|cpu| allowed.contains(cpu))
1242                .count();
1243            let grains = if capacity >= minimum_demand {
1244                (capacity / stride).max(1)
1245            } else {
1246                0
1247            };
1248            (0..grains).map(move |grain| (llc, grain.saturating_mul(stride)))
1249        })
1250        .collect::<Vec<_>>();
1251    if seeds.is_empty() {
1252        seeds.push((0, 0));
1253    }
1254    seeds
1255}
1256
1257fn planner_local_stride(demands: &[GuestLlcDemand], kind: PinningKind) -> usize {
1258    demands
1259        .iter()
1260        .map(|demand| demand.cpus)
1261        .max()
1262        .unwrap_or(1)
1263        // The service thread may land in any mapped LLC. Reserve its width in
1264        // every static grain so multi-LLC and heterogeneous topologies do not
1265        // generate overlapping starts on the eventual service domain.
1266        .saturating_add(usize::from(kind == PinningKind::Performance))
1267        .max(1)
1268}
1269
1270fn llc_allowed_cpus(
1271    host: &HostTopology,
1272    llc: usize,
1273    allowed: &std::collections::BTreeSet<usize>,
1274) -> std::collections::BTreeSet<usize> {
1275    host.llc_groups[llc]
1276        .cpus
1277        .iter()
1278        .copied()
1279        .filter(|cpu| allowed.contains(cpu))
1280        .collect()
1281}
1282
1283fn host_bins_fit(
1284    host: &HostTopology,
1285    demands: &[GuestLlcDemand],
1286    request_indices: &[usize],
1287    bins: &[usize],
1288    allowed: &std::collections::BTreeSet<usize>,
1289) -> bool {
1290    let mut request_sizes = request_indices
1291        .iter()
1292        .map(|&index| demands[index].cpus)
1293        .collect::<Vec<_>>();
1294    let mut capacities = bins
1295        .iter()
1296        .map(|&llc| llc_allowed_cpus(host, llc, allowed).len())
1297        .collect::<Vec<_>>();
1298    request_sizes.sort_unstable_by(|a, b| b.cmp(a));
1299    capacities.sort_unstable_by(|a, b| b.cmp(a));
1300    request_sizes.len() <= capacities.len()
1301        && request_sizes
1302            .iter()
1303            .zip(capacities)
1304            .all(|(demand, capacity)| *demand <= capacity)
1305}
1306
1307fn perf_grain_capable_for_footprint(host: &HostTopology, llc: usize, footprint: usize) -> bool {
1308    let llc_cpus = host.llc_groups[llc].cpus.len();
1309    llc_cpus >= PERF_GRAIN_LLC_MIN_CPUS
1310        && footprint.saturating_mul(PERF_GRAIN_MAX_OCCUPANCY_DEN)
1311            < llc_cpus.saturating_mul(PERF_GRAIN_MAX_OCCUPANCY_NUM)
1312}
1313
1314fn grain_mapping_possible(
1315    host: &HostTopology,
1316    demands: &[GuestLlcDemand],
1317    allowed: &std::collections::BTreeSet<usize>,
1318) -> bool {
1319    let matches_with_service =
1320        |service_request: Option<usize>, separate_service_llc: Option<usize>| {
1321            let mut edges = std::collections::BTreeMap::new();
1322            for (request, demand) in demands.iter().enumerate() {
1323                let footprint = demand.cpus + usize::from(service_request == Some(request));
1324                let choices = (0..host.llc_groups.len())
1325                    .filter(|&llc| {
1326                        Some(llc) != separate_service_llc
1327                            && llc_allowed_cpus(host, llc, allowed).len() >= footprint
1328                            && perf_grain_capable_for_footprint(host, llc, footprint)
1329                    })
1330                    .collect::<Vec<_>>();
1331                if choices.is_empty() {
1332                    return false;
1333                }
1334                edges.insert(request, choices);
1335            }
1336            let mut order = (0..demands.len()).collect::<Vec<_>>();
1337            order.sort_by_key(|request| edges[request].len());
1338            match_distinct(&edges, &order).is_some()
1339        };
1340
1341    // The one service CPU may share any guest-mapped LLC...
1342    if (0..demands.len()).any(|request| matches_with_service(Some(request), None)) {
1343        return true;
1344    }
1345    // ...or occupy its own otherwise-unmapped grain-capable LLC.
1346    (0..host.llc_groups.len()).any(|llc| {
1347        !llc_allowed_cpus(host, llc, allowed).is_empty()
1348            && perf_grain_capable_for_footprint(host, llc, 1)
1349            && matches_with_service(None, Some(llc))
1350    })
1351}
1352
1353fn preferred_llc_ready(
1354    host: &HostTopology,
1355    llc: usize,
1356    demand: usize,
1357    kind: PinningKind,
1358    preferred_shared_llcs: &std::collections::BTreeSet<usize>,
1359    preferred_exclusive_llcs: &std::collections::BTreeSet<usize>,
1360    performance_prefers_shared: bool,
1361) -> bool {
1362    match kind {
1363        PinningKind::Default => preferred_shared_llcs.contains(&llc),
1364        PinningKind::Performance
1365            if performance_prefers_shared
1366                && perf_grain_capable_for_footprint(host, llc, demand) =>
1367        {
1368            preferred_shared_llcs.contains(&llc)
1369        }
1370        PinningKind::Performance => preferred_exclusive_llcs.contains(&llc),
1371    }
1372}
1373
1374/// Whether a host NUMA node can satisfy every request entirely from the
1375/// mode-aware resources in the coordinator's latest availability snapshot.
1376/// This is preference input only; the completed candidate's full claim is
1377/// checked authoritatively before acquisition.
1378fn host_bins_preferred_fit(
1379    host: &HostTopology,
1380    inputs: PlannerInputs<'_>,
1381    request_indices: &[usize],
1382    bins: &[usize],
1383) -> bool {
1384    let PlannerInputs {
1385        demands,
1386        kind,
1387        allowed,
1388        preferred_cpus,
1389        preferred_shared_llcs,
1390        preferred_exclusive_llcs,
1391        performance_prefers_shared,
1392        ..
1393    } = inputs;
1394    let mut edges = std::collections::BTreeMap::new();
1395    for &request in request_indices {
1396        let demand = demands[request].cpus;
1397        let choices = bins
1398            .iter()
1399            .copied()
1400            .filter(|&llc| {
1401                let allowed_cpus = llc_allowed_cpus(host, llc, allowed);
1402                allowed_cpus.len() >= demand
1403                    && allowed_cpus
1404                        .iter()
1405                        .filter(|cpu| preferred_cpus.contains(cpu))
1406                        .count()
1407                        >= demand
1408                    && preferred_llc_ready(
1409                        host,
1410                        llc,
1411                        demand,
1412                        kind,
1413                        preferred_shared_llcs,
1414                        preferred_exclusive_llcs,
1415                        performance_prefers_shared,
1416                    )
1417            })
1418            .collect::<Vec<_>>();
1419        if choices.is_empty() {
1420            return false;
1421        }
1422        edges.insert(request, choices);
1423    }
1424    let mut order = request_indices.to_vec();
1425    order.sort_by_key(|request| edges[request].len());
1426    match_distinct(&edges, &order).is_some()
1427}
1428
1429/// Maximum-cardinality bipartite matching over `order`. Unlike a greedy
1430/// "first bin that fits" walk, augmenting paths can displace an earlier
1431/// flexible request when a later request has only that bin available.
1432fn match_distinct<K: Ord + Copy>(
1433    edges: &std::collections::BTreeMap<K, Vec<usize>>,
1434    order: &[K],
1435) -> Option<std::collections::BTreeMap<K, usize>> {
1436    fn augment<K: Ord + Copy>(
1437        left: K,
1438        edges: &std::collections::BTreeMap<K, Vec<usize>>,
1439        owner: &mut std::collections::BTreeMap<usize, K>,
1440        seen: &mut std::collections::BTreeSet<usize>,
1441    ) -> bool {
1442        for &right in edges.get(&left).into_iter().flatten() {
1443            if !seen.insert(right) {
1444                continue;
1445            }
1446            let displaced = owner.get(&right).copied();
1447            if displaced.is_none_or(|other| augment(other, edges, owner, seen)) {
1448                owner.insert(right, left);
1449                return true;
1450            }
1451        }
1452        false
1453    }
1454
1455    let mut owner = std::collections::BTreeMap::new();
1456    for &left in order {
1457        if !augment(
1458            left,
1459            edges,
1460            &mut owner,
1461            &mut std::collections::BTreeSet::new(),
1462        ) {
1463            return None;
1464        }
1465    }
1466    Some(
1467        owner
1468            .into_iter()
1469            .map(|(right, left)| (left, right))
1470            .collect(),
1471    )
1472}
1473
1474/// Maximum-cardinality bipartite matching for strict guest-NUMA placement.
1475fn match_distinct_nodes(
1476    edges: &std::collections::BTreeMap<u32, Vec<usize>>,
1477) -> Option<std::collections::BTreeMap<u32, usize>> {
1478    let mut guests = edges.keys().copied().collect::<Vec<_>>();
1479    guests.sort_by_key(|guest| edges[guest].len());
1480    match_distinct(edges, &guests)
1481}
1482
1483fn assign_distinct_bins(
1484    host: &HostTopology,
1485    inputs: PlannerInputs<'_>,
1486    request_indices: &[usize],
1487    eligible_bins: &[usize],
1488    seed: usize,
1489    used: &mut std::collections::BTreeSet<usize>,
1490    mapped: &mut [usize],
1491) -> bool {
1492    let PlannerInputs {
1493        demands,
1494        kind,
1495        allowed,
1496        preferred_cpus,
1497        preferred_shared_llcs,
1498        preferred_exclusive_llcs,
1499        performance_prefers_shared,
1500        ..
1501    } = inputs;
1502    let mut eligible = eligible_bins
1503        .iter()
1504        .copied()
1505        .filter(|llc| !used.contains(llc))
1506        .collect::<Vec<_>>();
1507    eligible.sort_unstable();
1508    eligible.dedup();
1509    let bin_rank = eligible
1510        .iter()
1511        .copied()
1512        .enumerate()
1513        .map(|(rank, llc)| (llc, rank))
1514        .collect::<std::collections::BTreeMap<_, _>>();
1515
1516    let mut edges = std::collections::BTreeMap::new();
1517    for &request in request_indices {
1518        let demand = demands[request].cpus;
1519        let mut choices = eligible
1520            .iter()
1521            .copied()
1522            .filter_map(|llc| {
1523                let cpus = llc_allowed_cpus(host, llc, allowed);
1524                (cpus.len() >= demand).then(|| {
1525                    let ready = cpus
1526                        .iter()
1527                        .filter(|cpu| preferred_cpus.contains(cpu))
1528                        .count();
1529                    let llc_ready = preferred_llc_ready(
1530                        host,
1531                        llc,
1532                        demand,
1533                        kind,
1534                        preferred_shared_llcs,
1535                        preferred_exclusive_llcs,
1536                        performance_prefers_shared,
1537                    );
1538                    (llc, cpus.len(), ready, llc_ready)
1539                })
1540            })
1541            .collect::<Vec<_>>();
1542        // A complete ready footprint outranks cyclic rotation. This lets the
1543        // coordinator synthesize an arbitrary simultaneously-free combination
1544        // (for example LLCs 0+2 of four) without pre-enumerating every subset.
1545        // When no availability snapshot was supplied, `preferred == allowed`,
1546        // so every fitting bin ties on the capped readiness terms and bounded
1547        // seed rotation still chooses alternate complete matchings. Subsequent
1548        // seeds can therefore recover when exact CPU matching rejects one
1549        // because synthetic LLC descriptions overlap.
1550        choices.sort_by_key(|&(llc, capacity, ready, llc_ready)| {
1551            let phase = bin_rank
1552                .get(&seed)
1553                .copied()
1554                .unwrap_or(seed % eligible.len().max(1));
1555            (
1556                !llc_ready,
1557                ready < demand,
1558                std::cmp::Reverse(ready.min(demand)),
1559                rotated_tie(bin_rank[&llc], phase, eligible.len().max(1)),
1560                capacity,
1561                std::cmp::Reverse(ready),
1562            )
1563        });
1564        if choices.is_empty() {
1565            return false;
1566        }
1567        edges.insert(
1568            request,
1569            choices
1570                .into_iter()
1571                .map(|(llc, _, _, _)| llc)
1572                .collect::<Vec<_>>(),
1573        );
1574    }
1575
1576    let mut requests = request_indices.to_vec();
1577    requests.sort_by_key(|&request| {
1578        (
1579            edges[&request].len(),
1580            std::cmp::Reverse(demands[request].cpus),
1581            rotated_tie(
1582                demands[request].guest_llc as usize,
1583                seed,
1584                demands.len().max(1),
1585            ),
1586        )
1587    });
1588    let Some(assignment) = match_distinct(&edges, &requests) else {
1589        return false;
1590    };
1591    for (&request, &llc) in &assignment {
1592        used.insert(llc);
1593        mapped[request] = llc;
1594    }
1595    true
1596}
1597
1598/// Lock mode for LLC reservation.
1599#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1600pub enum LlcLockMode {
1601    /// Exclusive access to the entire LLC (performance_mode tests).
1602    /// Returns unavailable when any shared or exclusive holder exists.
1603    Exclusive,
1604    /// Shared access to the LLC (non-perf pinned tests).
1605    /// Multiple shared holders coexist; returns unavailable when
1606    /// exclusive holder exists.
1607    Shared,
1608}
1609
1610/// Absolute lower bound, in host CPUs, on an LLC before perf-mode
1611/// reservation may drop from whole-LLC exclusion to per-CPU grain.
1612///
1613/// This is the GUARD on the occupancy ratio below, not the decision
1614/// axis itself. It is anchored ABOVE every validated host LLC — the
1615/// dev box's 16-CPU L3s, x86 CI's (`scx-x64`) ~8-CPU L3s, and native
1616/// arm's (`armly`) 4-CPU L2s — with margin, and far BELOW the
1617/// pathological monolithic L3 the grain switch exists for (the AWS
1618/// Graviton's single 96-CPU L3). Below this bar the reservation is
1619/// ALWAYS whole-LLC [`LlcLockMode::Exclusive`], so the entire measured
1620/// perf campaign (dilation_validation.md, the perf-isolation gates) is
1621/// byte-for-byte unchanged on every host it was validated on.
1622///
1623/// Why a floor at all, when the author's model is a pure occupancy
1624/// ratio: the real perf cells are SMALL (`cores = 2..4`, `threads = 1`
1625/// → 2-4 vCPUs per LLC — see the `performance_mode` e2e fixtures), so on
1626/// the dev box's 16-CPU L3 a cell occupies as little as `2/16 = 0.125`.
1627/// A pure `>= 0.5`-occupancy gate (which assumes ~LLC-filling cells)
1628/// would therefore reclassify the dev box AND x86 CI (`2/8 = 0.25`) to
1629/// per-CPU grain and invalidate their measurements. The floor makes the
1630/// ratio safe precisely because no validated host has an LLC anywhere
1631/// near this size — 32 sits at 2× the largest validated LLC (16) and
1632/// 1/3 of the Graviton's 96 — so the ratio only ever DECIDES on a
1633/// genuinely monolithic cache domain, and the validated hosts are
1634/// off-limits regardless of how small a cell they run.
1635pub(crate) const PERF_GRAIN_LLC_MIN_CPUS: usize = 32;
1636
1637/// Maximum LLC OCCUPANCY (cell's per-LLC pinned CPUs ÷ host LLC CPUs) at
1638/// which perf-mode still drops to per-CPU grain, expressed as an exact
1639/// integer ratio to avoid float. A cell occupying `< 1/2` of the LLC is
1640/// a minority slice: on a huge L3 its per-cell cache share is ample, and
1641/// a per-CPU-grain neighbour is at most a comparable slice, so the
1642/// perf-mode `D≈1` isolation contract still effectively holds (the
1643/// dilation witness + the `D>1.5` perf-isolation gate catch any residual
1644/// perturbation). A cell occupying `>= 1/2` of even a huge LLC wants the
1645/// cache to itself — a neighbour would be a large fraction of its
1646/// working set — so it keeps whole-LLC [`LlcLockMode::Exclusive`]
1647/// regardless of the LLC's absolute size. This is the author's ratio
1648/// gate; on our small cells it is trivially satisfied on the Graviton
1649/// (`2/96 ≈ 0.02`) and only bites a hypothetical LLC-filling perf cell.
1650const PERF_GRAIN_MAX_OCCUPANCY_NUM: usize = 1;
1651const PERF_GRAIN_MAX_OCCUPANCY_DEN: usize = 2;
1652
1653/// Choose the LLC lock mode for a perf-mode reservation of `plan`.
1654///
1655/// The default perf-mode reservation is whole-LLC
1656/// [`LlcLockMode::Exclusive`]: the cell owns its entire cache domain —
1657/// the strongest isolation, and what the dilation campaign measured. On
1658/// a host whose LLC DWARFS the cell (a single monolithic L3 spanning
1659/// scores of CPUs — the AWS Graviton's 96-CPU L3), whole-LLC `LOCK_EX`
1660/// means one small cell exclusively locks the WHOLE machine, so perf
1661/// cells serialize globally (the 20-60× arm-CI makespan blowup). There
1662/// we drop to per-CPU GRAIN: a SHARED (`LOCK_SH`) LLC lock so cells
1663/// coexist on the giant L3, plus EXCLUSIVE per-CPU locks over exactly
1664/// the pinned cores + service CPU. The returned explicit claim therefore
1665/// names the actual CPUs held, not the whole LLC, and peers see the freed
1666/// capacity.
1667///
1668/// The switch requires BOTH gates, evaluated PER occupied host LLC and
1669/// taken conservatively (any occupied LLC that is modest, or that the
1670/// cell fills, keeps the WHOLE plan Exclusive):
1671///
1672/// 1. [`PERF_GRAIN_LLC_MIN_CPUS`] — the LLC is far larger than any
1673///    validated CI/dev cache domain (the absolute guard that keeps
1674///    every validated host on the unchanged whole-LLC path).
1675/// 2. [`PERF_GRAIN_MAX_OCCUPANCY_NUM`]/[`PERF_GRAIN_MAX_OCCUPANCY_DEN`]
1676///    — the cell occupies a minority (`< 1/2`) of that LLC (a cell that
1677///    wants most of even a huge LLC keeps the whole L3).
1678///
1679/// On every validated host gate 1 fails (LLC ≤ 16 < 32), so this
1680/// returns `Exclusive` there no matter how small the cell — behaviour
1681/// is identical to the pre-change whole-LLC campaign.
1682pub(crate) fn perf_llc_lock_mode(host_topo: &HostTopology, plan: &PinningPlan) -> LlcLockMode {
1683    if plan.llc_indices.is_empty() {
1684        return LlcLockMode::Exclusive;
1685    }
1686    // Per-host-LLC pinned footprint: vCPU assignments landing in the
1687    // LLC, plus the service CPU if it lives there.
1688    let footprint_in = |llc_idx: usize| -> usize {
1689        let cpus = &host_topo.llc_groups[llc_idx].cpus;
1690        let in_llc = |c: usize| cpus.contains(&c);
1691        let vcpus = plan.assignments.iter().filter(|&&(_, c)| in_llc(c)).count();
1692        vcpus + usize::from(plan.service_cpu.is_some_and(in_llc))
1693    };
1694    // Grain only when EVERY occupied host LLC is both huge and a
1695    // minority-occupied slice — the fullest / smallest occupied LLC
1696    // dominates the decision, so a plan touching one modest LLC stays
1697    // Exclusive.
1698    let all_grain = plan.llc_indices.iter().all(|&idx| {
1699        let llc_cpus = host_topo.llc_groups[idx].cpus.len();
1700        let footprint = footprint_in(idx);
1701        let huge = llc_cpus >= PERF_GRAIN_LLC_MIN_CPUS;
1702        // footprint / llc_cpus < NUM / DEN  ⇔  footprint*DEN < llc_cpus*NUM.
1703        let minority = footprint.saturating_mul(PERF_GRAIN_MAX_OCCUPANCY_DEN)
1704            < llc_cpus.saturating_mul(PERF_GRAIN_MAX_OCCUPANCY_NUM);
1705        huge && minority
1706    });
1707    if all_grain {
1708        LlcLockMode::Shared
1709    } else {
1710        LlcLockMode::Exclusive
1711    }
1712}
1713
1714/// Resource lock acquisition outcome.
1715#[derive(Debug)]
1716pub enum LockOutcome {
1717    /// All locks acquired successfully.
1718    Acquired {
1719        /// LLC offset consumed; read only by the locking test fixtures.
1720        #[allow(dead_code)]
1721        llc_offset: usize,
1722        locks: protocol::Acquired<Vec<protocol::AdmissionFlock>>,
1723    },
1724    /// Resources busy. The inner string carries the diagnostic reason
1725    /// surfaced to test fixtures; production callers only match the
1726    /// variant tag.
1727    Unavailable(#[allow(dead_code)] String),
1728}
1729
1730/// Degraded CPU-only admission bridge for default shared fallback when host
1731/// LLC topology could not be cached. Whole performance reservations also lock
1732/// every CPU in their claimed LLCs EX, so CPU-SH remains a hard fence against
1733/// performance while allowing default/no-perf/build peers to coexist.
1734pub(crate) fn acquire_shared_fallback_bridge(
1735    cpus: &[usize],
1736    wait: bool,
1737    cancelled: Option<&AtomicBool>,
1738) -> Result<LockOutcome> {
1739    acquire_resource_locks_waiting_impl(
1740        &[],
1741        LlcLockMode::Shared,
1742        cpus,
1743        FlockMode::Shared,
1744        wait,
1745        cancelled,
1746    )
1747}
1748
1749fn acquire_resource_locks_waiting_impl(
1750    llc_indices: &[usize],
1751    llc_mode: LlcLockMode,
1752    cpus: &[usize],
1753    cpu_mode: FlockMode,
1754    wait: bool,
1755    cancelled: Option<&AtomicBool>,
1756) -> Result<LockOutcome> {
1757    if crate::cargo_test_mode::cargo_test_mode_active() {
1758        return Ok(LockOutcome::Acquired {
1759            llc_offset: llc_indices.first().copied().unwrap_or(0),
1760            locks: protocol::Acquired::untracked(Vec::new()),
1761        });
1762    }
1763    let llc_offset = llc_indices.first().copied().unwrap_or(0);
1764    // Fast path: claim-subtracted, non-blocking, all-or-nothing.
1765    let (first_reason, first_evidence) =
1766        match try_acquire_resources(llc_indices, llc_mode, cpus, cpu_mode)? {
1767            TryAcquireAll::Acquired(locks) => {
1768                return Ok(LockOutcome::Acquired { llc_offset, locks });
1769            }
1770            TryAcquireAll::Contended { reason, evidence } => (reason, evidence),
1771        };
1772    if !wait {
1773        return Ok(LockOutcome::Unavailable(first_reason));
1774    }
1775    let target = protocol::canonical_lock_order_with_modes(
1776        llc_indices,
1777        llc_flock_mode(llc_mode),
1778        cpus,
1779        cpu_mode,
1780    );
1781    let claim = resource_claim_with_modes(llc_indices, llc_mode, cpus, cpu_mode);
1782    // Contended: retain one exact ticket while retrying this fixed set only
1783    // when it is compatible with every earlier live waiter claim. This keeps
1784    // disjoint host capacity busy without weakening the reservation: the
1785    // actual flock set is still all-or-nothing and byte-for-byte identical.
1786    let register = |probe: &mut protocol::GrantedProbe| {
1787        probe.try_acquire(&claim, || {
1788            match try_acquire_resources_unfenced(llc_indices, llc_mode, cpus, cpu_mode)? {
1789                RawAcquireAll::Acquired(locks) => Ok(protocol::ProbeOutcome::Acquired(locks)),
1790                RawAcquireAll::Contended {
1791                    evidence: Some(evidence),
1792                    ..
1793                } => Ok(protocol::ProbeOutcome::Contended(evidence)),
1794                RawAcquireAll::Contended { evidence: None, .. } => {
1795                    anyhow::bail!("unfenced resource probe lost exact contention evidence")
1796                }
1797            }
1798        })
1799    };
1800    let ticket = match first_evidence {
1801        Some(evidence) => protocol::register_ticket_after_contention(
1802            claim.clone(),
1803            claim.clone(),
1804            evidence,
1805            cancelled,
1806            register,
1807        )?,
1808        None => {
1809            protocol::register_ticket_or_acquire(claim.clone(), claim.clone(), cancelled, register)?
1810        }
1811    };
1812    let coordinator = match ticket {
1813        protocol::TicketWork::Acquired(locks) => {
1814            return Ok(LockOutcome::Acquired { llc_offset, locks });
1815        }
1816        protocol::TicketWork::Coordinator(coordinator) => coordinator,
1817    };
1818    let mut step = |held: &mut protocol::HeldLocks| {
1819        if let Some(locks) = held.probe_complete_if_ready(&claim, &target)? {
1820            Ok(protocol::CoordinatorStep::Complete {
1821                claim: claim.clone(),
1822                value: locks,
1823            })
1824        } else {
1825            Ok(protocol::CoordinatorStep::Waiting {
1826                claim: claim.clone(),
1827            })
1828        }
1829    };
1830    let outcome = match cancelled {
1831        Some(cancelled) => {
1832            protocol::acquire_as_coordinator_interruptible(coordinator, cancelled, &mut step)?
1833        }
1834        None => protocol::acquire_as_coordinator(coordinator, &mut step)?,
1835    };
1836    Ok(match outcome {
1837        protocol::CoordinatorOutcome::Acquired(locks) => {
1838            LockOutcome::Acquired { llc_offset, locks }
1839        }
1840        protocol::CoordinatorOutcome::Prepared(_) => {
1841            unreachable!("resource-lock coordinator prepared a VM intent")
1842        }
1843        protocol::CoordinatorOutcome::Aborted { reason } => LockOutcome::Unavailable(reason),
1844    })
1845}
1846
1847fn llc_flock_mode(llc_mode: LlcLockMode) -> FlockMode {
1848    match llc_mode {
1849        LlcLockMode::Exclusive => FlockMode::Exclusive,
1850        LlcLockMode::Shared => FlockMode::Shared,
1851    }
1852}
1853
1854/// The published claim for an explicit two-resource-class reservation.
1855pub(crate) fn resource_claim_with_modes(
1856    llc_indices: &[usize],
1857    llc_mode: LlcLockMode,
1858    cpus: &[usize],
1859    cpu_mode: FlockMode,
1860) -> protocol::ClaimSet {
1861    protocol::ClaimSet::with_modes(
1862        llc_indices.iter().copied(),
1863        cpus.iter().copied(),
1864        llc_flock_mode(llc_mode),
1865        cpu_mode,
1866    )
1867}
1868
1869pub(crate) fn resource_claim_with_permits(
1870    llc_indices: &[usize],
1871    llc_mode: LlcLockMode,
1872    cpus: &[usize],
1873    cpu_mode: FlockMode,
1874    permits: &[usize],
1875    admission_class: protocol::AdmissionClass,
1876) -> protocol::ClaimSet {
1877    protocol::ClaimSet::with_permits(
1878        llc_indices.iter().copied(),
1879        cpus.iter().copied(),
1880        permits.iter().copied(),
1881        llc_flock_mode(llc_mode),
1882        cpu_mode,
1883        FlockMode::Exclusive,
1884    )
1885    .with_admission_class(admission_class)
1886}
1887
1888/// Nextest exports this to every test process: the custom test-group
1889/// name, or the literal `@global` for ungrouped tests. A process not
1890/// spawned by nextest has neither this nor `NEXTEST_TEST_NAME`.
1891const NEXTEST_TEST_GROUP_ENV: &str = "NEXTEST_TEST_GROUP";
1892const NEXTEST_TEST_NAME_ENV: &str = "NEXTEST_TEST_NAME";
1893
1894/// Resolve the production lock directory for a real host-resource
1895/// claim, first tripping the fail-closed nextest-misclassification
1896/// guard.
1897///
1898/// ktstr admits every VM boot, resource lock, and build reservation
1899/// through its cross-process registry, which lives under this
1900/// directory. Nextest is only a spawner: `.config/nextest.toml` must
1901/// place resource users in the effectively-unbounded `@global` group
1902/// so they reach that registry, and ordinary host tests in the
1903/// CPU-sized `host-tests` group. That allowlist is hand-maintained,
1904/// so a new test entering production admission without being added
1905/// would silently run inside `host-tests` — booting a second
1906/// scheduler outside ktstr's admission with green CI. Rather than let
1907/// that misclassification stand, abort loudly the moment such a test
1908/// resolves the production lock dir.
1909///
1910/// The nextest group alone is not a sufficient discriminator: a
1911/// `host-tests` test may legitimately take real locks in an ISOLATED
1912/// namespace (e.g. the re-exec'd build-reservation tests point
1913/// `KTSTR_LOCK_DIR` at a private tempdir), and CI itself always sets
1914/// `KTSTR_LOCK_DIR` ambiently, so neither the group nor "is
1915/// `KTSTR_LOCK_DIR` set" can tell isolation from misclassification. The
1916/// seal is [`crate::KTSTR_PRODUCTION_LOCK_DIR_ENV`]: cargo-ktstr stamps
1917/// it with the dir IT resolved when spawning nextest, so a fire
1918/// requires the test to resolve that exact shared namespace — the one
1919/// the real scheduler is using this run. A test redirected elsewhere
1920/// (mismatch) or an ad-hoc run with no reference (absent) proceeds.
1921///
1922/// Temp-path unit tests that use the thread-local lock-prefix override
1923/// never reach this at all: the override short-circuits every
1924/// `*_lock_prefix` caller before it runs.
1925fn production_lock_dir() -> std::path::PathBuf {
1926    let resolved = crate::cache::resolve_lock_dir();
1927    if let Ok(group) = std::env::var(NEXTEST_TEST_GROUP_ENV)
1928        && group == crate::NEXTEST_HOST_TESTS_GROUP
1929        && let Some(reference) = std::env::var_os(crate::KTSTR_PRODUCTION_LOCK_DIR_ENV)
1930        && std::path::Path::new(&reference) == resolved.as_path()
1931    {
1932        let test = std::env::var(NEXTEST_TEST_NAME_ENV).unwrap_or_else(|_| "<unknown>".to_string());
1933        panic!(
1934            "test `{test}` takes production host-resource admission but was \
1935             classified into the CPU-bounded `{group}` nextest group. \
1936             Resource users must run in `@global` so ktstr's cross-process \
1937             registry admits them; running here boots a second scheduler \
1938             outside admission. Add this test to the resource selector in \
1939             .config/nextest.toml (the profile.default `@global` override, \
1940             mirrored as its `host-tests` complement)."
1941        );
1942    }
1943    resolved
1944}
1945
1946/// Compose the LLC lockfile prefix from the resolved lock directory.
1947/// Returns `{lock_dir}/ktstr-llc-`.
1948fn llc_lock_prefix() -> String {
1949    format!("{}/ktstr-llc-", production_lock_dir().display())
1950}
1951
1952/// Compose the per-CPU lockfile prefix from the resolved lock directory.
1953/// Returns `{lock_dir}/ktstr-cpu-`.
1954fn cpu_lock_prefix() -> String {
1955    format!("{}/ktstr-cpu-", production_lock_dir().display())
1956}
1957
1958/// Compose the weighted admission-permit lockfile prefix.
1959fn permit_lock_prefix() -> String {
1960    format!("{}/ktstr-permit-", production_lock_dir().display())
1961}
1962
1963#[cfg(test)]
1964thread_local! {
1965    /// Thread-local override for the LLC lock prefix. Tests set this
1966    /// to a per-test tempdir so the acquire path operates on its
1967    /// own lockfile pool instead of padding the `LlcGroup` vector
1968    /// to 90,000+ entries just to avoid collision with production
1969    /// indices at 0..<host-llcs>. See tests `acquire_llc_plan_*`
1970    /// that build a small synth topo and point the prefix at a
1971    /// `TempDir`.
1972    pub(crate) static LLC_LOCK_PREFIX_OVERRIDE: std::cell::RefCell<Option<String>> =
1973        const { std::cell::RefCell::new(None) };
1974
1975    /// Thread-local override for the per-CPU lock prefix. Symmetric
1976    /// with `LLC_LOCK_PREFIX_OVERRIDE`.
1977    pub(crate) static CPU_LOCK_PREFIX_OVERRIDE: std::cell::RefCell<Option<String>> =
1978        const { std::cell::RefCell::new(None) };
1979}
1980
1981/// Compose the LLC lockfile path for `llc_idx`. Production resolves
1982/// via `KTSTR_LOCK_DIR` (fallback `/tmp`); tests can override the
1983/// prefix via `LLC_LOCK_PREFIX_OVERRIDE` to keep their lockfile
1984/// pool isolated.
1985pub(crate) fn llc_lock_path(llc_idx: usize) -> String {
1986    #[cfg(test)]
1987    {
1988        if let Some(p) = LLC_LOCK_PREFIX_OVERRIDE.with(|p| p.borrow().clone()) {
1989            return format!("{p}{llc_idx}.lock");
1990        }
1991    }
1992    format!("{}{llc_idx}.lock", llc_lock_prefix())
1993}
1994
1995/// Compose the per-CPU lockfile path for `cpu`. Symmetric with
1996/// [`llc_lock_path`] — production resolves via `KTSTR_LOCK_DIR`;
1997/// tests can override via `CPU_LOCK_PREFIX_OVERRIDE`.
1998pub(crate) fn cpu_lock_path(cpu: usize) -> String {
1999    #[cfg(test)]
2000    {
2001        if let Some(p) = CPU_LOCK_PREFIX_OVERRIDE.with(|p| p.borrow().clone()) {
2002            return format!("{p}{cpu}.lock");
2003        }
2004    }
2005    format!("{}{cpu}.lock", cpu_lock_prefix())
2006}
2007
2008/// Compose the per-permit lockfile path. Permit identities are independent of
2009/// host CPU identities; the registry stores them as a first-class resource
2010/// class and physical ownership is always an exclusive flock.
2011pub(crate) fn permit_lock_path(permit: usize) -> String {
2012    #[cfg(test)]
2013    {
2014        if let Some(p) = CPU_LOCK_PREFIX_OVERRIDE.with(|p| p.borrow().clone()) {
2015            return format!("{p}permit-{permit}.lock");
2016        }
2017    }
2018    format!("{}{permit}.lock", permit_lock_prefix())
2019}
2020
2021/// Try to acquire all resource locks (all-or-nothing, non-blocking,
2022/// canonical order — see [`protocol`]). Returns the held fds
2023/// on success, or an error string describing which resource was
2024/// busy; on ANY failure every lock taken so far is released before
2025/// returning, so no partial reservation ever persists.
2026///
2027/// Claim-aware: an incompatible live ticket claim fails the attempt before
2028/// touching its reserved lockfiles.
2029pub(crate) enum TryAcquireAll {
2030    Acquired(protocol::Acquired<Vec<protocol::AdmissionFlock>>),
2031    Contended {
2032        reason: String,
2033        evidence: Option<protocol::ContentionEvidence>,
2034    },
2035}
2036
2037enum RawAcquireAll {
2038    Acquired(Vec<protocol::AdmissionFlock>),
2039    Contended {
2040        reason: String,
2041        evidence: Option<protocol::ContentionEvidence>,
2042    },
2043}
2044
2045pub(crate) fn try_acquire_resources(
2046    llc_indices: &[usize],
2047    llc_mode: LlcLockMode,
2048    cpus: &[usize],
2049    cpu_mode: FlockMode,
2050) -> Result<TryAcquireAll> {
2051    let request = resource_claim_with_modes(llc_indices, llc_mode, cpus, cpu_mode);
2052    if request.is_empty() {
2053        return Ok(TryAcquireAll::Acquired(protocol::Acquired::untracked(
2054            Vec::new(),
2055        )));
2056    }
2057    match protocol::with_registry_fence(&request, || {
2058        try_acquire_resources_unfenced(llc_indices, llc_mode, cpus, cpu_mode)
2059    })? {
2060        protocol::RegistryFence::Fenced => Ok(TryAcquireAll::Contended {
2061            reason: "reservation claimed by an earlier registered ticket".into(),
2062            evidence: None,
2063        }),
2064        protocol::RegistryFence::Ran {
2065            value: RawAcquireAll::Acquired(locks),
2066            ..
2067        } => {
2068            let locks = protocol::publish_acquired(&request, locks)?;
2069            Ok(TryAcquireAll::Acquired(locks))
2070        }
2071        protocol::RegistryFence::Ran {
2072            value: RawAcquireAll::Contended { reason, evidence },
2073            ..
2074        } => Ok(TryAcquireAll::Contended { reason, evidence }),
2075    }
2076}
2077
2078fn try_acquire_resources_unfenced(
2079    llc_indices: &[usize],
2080    llc_mode: LlcLockMode,
2081    cpus: &[usize],
2082    cpu_mode: FlockMode,
2083) -> Result<RawAcquireAll> {
2084    try_acquire_resources_unfenced_with_permits(llc_indices, llc_mode, cpus, cpu_mode, &[])
2085}
2086
2087fn try_acquire_resources_unfenced_with_permits(
2088    llc_indices: &[usize],
2089    llc_mode: LlcLockMode,
2090    cpus: &[usize],
2091    cpu_mode: FlockMode,
2092    permits: &[usize],
2093) -> Result<RawAcquireAll> {
2094    try_acquire_resources_unfenced_with_permits_reusing(
2095        llc_indices,
2096        llc_mode,
2097        cpus,
2098        cpu_mode,
2099        permits,
2100        &[],
2101    )
2102}
2103
2104fn try_acquire_resources_unfenced_with_permits_reusing(
2105    llc_indices: &[usize],
2106    llc_mode: LlcLockMode,
2107    cpus: &[usize],
2108    cpu_mode: FlockMode,
2109    permits: &[usize],
2110    reusable_permits: &[(usize, protocol::AdmissionFlock)],
2111) -> Result<RawAcquireAll> {
2112    let target = protocol::canonical_lock_order_with_permits(
2113        llc_indices,
2114        llc_flock_mode(llc_mode),
2115        cpus,
2116        cpu_mode,
2117        permits,
2118    );
2119    try_acquire_lock_target_unfenced_reusing(&target, reusable_permits)
2120}
2121
2122fn try_acquire_lock_target_unfenced_reusing(
2123    target: &[protocol::ResourceLock],
2124    reusable_permits: &[(usize, protocol::AdmissionFlock)],
2125) -> Result<RawAcquireAll> {
2126    let mut locks = Vec::with_capacity(target.len());
2127    for lock in target {
2128        if let protocol::ResourceKey::Permit(permit) = lock.resource
2129            && let Some((_, fd)) = reusable_permits
2130                .iter()
2131                .find(|(candidate, _)| *candidate == permit)
2132        {
2133            // Reuse shares the same logical owner. The exact reservation keeps
2134            // that owner alive after preparation releases its reference, and
2135            // the final reference performs unlock-before-close.
2136            locks.push(fd.try_clone()?);
2137            continue;
2138        }
2139        match try_flock_with_witness(&lock.path, lock.mode)? {
2140            TryFlockOutcome::Acquired(fd) => {
2141                locks.push(protocol::AdmissionFlock::from_acquired(fd));
2142            }
2143            // Dropping `locks` on return releases everything taken
2144            // so far — the all-or-nothing contract.
2145            TryFlockOutcome::Contended(witness) => {
2146                drop(locks);
2147                return Ok(RawAcquireAll::Contended {
2148                    reason: format!("{} busy", lock.path),
2149                    evidence: Some(protocol::ContentionEvidence {
2150                        blocker: lock.resource,
2151                        mode: lock.mode,
2152                        _witness: witness,
2153                    }),
2154                });
2155            }
2156        }
2157    }
2158    Ok(RawAcquireAll::Acquired(locks))
2159}
2160
2161pub(crate) fn acquire_resources_with_permits_granted(
2162    llc_indices: &[usize],
2163    llc_mode: LlcLockMode,
2164    cpus: &[usize],
2165    cpu_mode: FlockMode,
2166    permits: &[usize],
2167) -> Result<protocol::ProbeOutcome<Vec<protocol::AdmissionFlock>>> {
2168    acquire_resources_with_permits_granted_reusing(
2169        llc_indices,
2170        llc_mode,
2171        cpus,
2172        cpu_mode,
2173        permits,
2174        &[],
2175    )
2176}
2177
2178pub(crate) fn acquire_resources_with_permits_granted_reusing(
2179    llc_indices: &[usize],
2180    llc_mode: LlcLockMode,
2181    cpus: &[usize],
2182    cpu_mode: FlockMode,
2183    permits: &[usize],
2184    reusable_permits: &[(usize, protocol::AdmissionFlock)],
2185) -> Result<protocol::ProbeOutcome<Vec<protocol::AdmissionFlock>>> {
2186    Ok(
2187        match try_acquire_resources_unfenced_with_permits_reusing(
2188            llc_indices,
2189            llc_mode,
2190            cpus,
2191            cpu_mode,
2192            permits,
2193            reusable_permits,
2194        )? {
2195            RawAcquireAll::Acquired(locks) => protocol::ProbeOutcome::Acquired(locks),
2196            RawAcquireAll::Contended {
2197                evidence: Some(evidence),
2198                ..
2199            } => protocol::ProbeOutcome::Contended(evidence),
2200            RawAcquireAll::Contended { evidence: None, .. } => {
2201                anyhow::bail!("unfenced resource probe lost exact contention evidence")
2202            }
2203        },
2204    )
2205}
2206
2207/// Canonical physical target for default's opportunistic exact probe. The
2208/// registry publishes the complete cooperative footprint as LLC-SH/CPU-SH;
2209/// only the mapped vCPU subset is transiently probed CPU-EX. Service headroom
2210/// is acquired CPU-SH in the same all-or-nothing pass, so the physical fds and
2211/// published claim always name the same resource set.
2212pub(crate) fn default_exact_footprint_lock_order_with_permits(
2213    shared_llcs: &[usize],
2214    shared_cpus: &[usize],
2215    exact_cpus: &[usize],
2216    permits: &[usize],
2217) -> Result<Vec<protocol::ResourceLock>> {
2218    let shared = shared_cpus
2219        .iter()
2220        .copied()
2221        .collect::<std::collections::BTreeSet<_>>();
2222    let exact = exact_cpus
2223        .iter()
2224        .copied()
2225        .collect::<std::collections::BTreeSet<_>>();
2226    anyhow::ensure!(
2227        !exact.is_empty(),
2228        "default exact probe requires at least one mapped vCPU"
2229    );
2230    anyhow::ensure!(
2231        exact.is_subset(&shared),
2232        "default exact CPU subset is outside its shared footprint"
2233    );
2234    let mut target = protocol::canonical_lock_order_with_permits(
2235        shared_llcs,
2236        FlockMode::Shared,
2237        shared_cpus,
2238        FlockMode::Shared,
2239        permits,
2240    );
2241    for lock in &mut target {
2242        if matches!(lock.resource, protocol::ResourceKey::Cpu(cpu) if exact.contains(&cpu)) {
2243            lock.mode = FlockMode::Exclusive;
2244        }
2245    }
2246    Ok(target)
2247}
2248
2249pub(crate) fn acquire_default_exact_footprint_with_permits_granted(
2250    shared_llcs: &[usize],
2251    shared_cpus: &[usize],
2252    exact_cpus: &[usize],
2253    permits: &[usize],
2254) -> Result<protocol::ProbeOutcome<Vec<protocol::AdmissionFlock>>> {
2255    acquire_default_exact_footprint_with_permits_granted_reusing(
2256        shared_llcs,
2257        shared_cpus,
2258        exact_cpus,
2259        permits,
2260        &[],
2261    )
2262}
2263
2264pub(crate) fn acquire_default_exact_footprint_with_permits_granted_reusing(
2265    shared_llcs: &[usize],
2266    shared_cpus: &[usize],
2267    exact_cpus: &[usize],
2268    permits: &[usize],
2269    reusable_permits: &[(usize, protocol::AdmissionFlock)],
2270) -> Result<protocol::ProbeOutcome<Vec<protocol::AdmissionFlock>>> {
2271    let target = default_exact_footprint_lock_order_with_permits(
2272        shared_llcs,
2273        shared_cpus,
2274        exact_cpus,
2275        permits,
2276    )?;
2277    let locks = match try_acquire_lock_target_unfenced_reusing(&target, reusable_permits)? {
2278        RawAcquireAll::Acquired(locks) => locks,
2279        RawAcquireAll::Contended {
2280            evidence: Some(evidence),
2281            ..
2282        } => return Ok(protocol::ProbeOutcome::Contended(evidence)),
2283        RawAcquireAll::Contended { evidence: None, .. } => {
2284            anyhow::bail!("default exact probe lost contention evidence")
2285        }
2286    };
2287    convert_default_exact_locks(&target, &locks)?;
2288    Ok(protocol::ProbeOutcome::Acquired(locks))
2289}
2290
2291pub(crate) fn convert_default_exact_locks(
2292    target: &[protocol::ResourceLock],
2293    locks: &[protocol::AdmissionFlock],
2294) -> Result<()> {
2295    use rustix::fs::{FlockOperation, flock};
2296
2297    debug_assert_eq!(target.len(), locks.len());
2298    for (resource, fd) in target.iter().zip(locks) {
2299        if matches!(resource.resource, protocol::ResourceKey::Cpu(_)) {
2300            flock(fd, FlockOperation::LockShared)
2301                .map_err(|errno| std::io::Error::from_raw_os_error(errno.raw_os_error()))
2302                .with_context(|| format!("convert {} from exclusive to shared", resource.path))?;
2303        }
2304    }
2305    Ok(())
2306}
2307
2308/// Diffuse a pid across `[0, max_start)` so adjacent processes do not land on
2309/// adjacent offsets. Topology and permit planners use this to rotate otherwise
2310/// equivalent choices across a launch herd.
2311///
2312/// Bare `pid % max_start` collapses adjacent pids onto adjacent
2313/// offsets (Linux's pid allocator walks `pid_max` sequentially),
2314/// which is the worst spread shape for the common batch-spawn
2315/// case: nextest forks N test processes back-to-back, every pid
2316/// lands within a small contiguous range, every `pid % max_start`
2317/// lands within an equally small contiguous slice of the offset
2318/// space, and they all probe overlapping slots on the first
2319/// pass. AHasher avalanche on the pid bytes diffuses adjacent
2320/// pids across the whole `[0, max_start)` range, so the
2321/// slot-rotation loop has a fair chance of finding a free slot
2322/// without burning the entire lockfile pool.
2323///
2324/// The hasher is `ahash::AHasher` keyed with fixed zero seeds
2325/// (`RandomState::with_seeds(0, 0, 0, 0)`); a per-run random
2326/// seed would defeat reproducibility for unit-test fixtures and
2327/// for any future debug logging that wants to confirm "pid X
2328/// picks offset Y for slot N".
2329///
2330/// Caller invariant: `max_start >= 1`. Panics on `max_start == 0`
2331/// (modulo-by-zero); callers must enforce this upstream (the
2332/// run-lock path floors `max_slots` at 1).
2333pub(crate) fn pid_window_offset(pid: u32, max_start: usize) -> usize {
2334    use std::hash::{BuildHasher, Hasher};
2335    let mut hasher = ahash::RandomState::with_seeds(0, 0, 0, 0).build_hasher();
2336    hasher.write(&pid.to_le_bytes());
2337    (hasher.finish() as usize) % max_start
2338}
2339
2340// ===========================================================================
2341// --cpu-cap PLAN pipeline — CpuCap / LlcSnapshot / LlcPlan + discover/plan/acquire
2342// ===========================================================================
2343//
2344// Entry point [`acquire_llc_plan`] is the workload-time non-perf-mode
2345// reservation path: kernel-build workloads and no-perf VM runs both use it.
2346// The separate KtstrVm builder's no-perf sizing uses the ownership-free
2347// [`plan_llc_selection_only`] twin. `--cpu-cap` is a CPU-count budget:
2348// the planner reserves exactly N host CPUs by walking whole LLCs in
2349// contention- / NUMA-aware order and partial-taking the last LLC
2350// so `plan.cpus.len() == N`. Each plan holds `LOCK_SH` on the selected
2351// LLCs and on exactly those N CPUs. The last LLC is still covered as a
2352// whole cache domain while the exact CPU locks let perf-mode `LOCK_EX`
2353// reservations conflict with only the CPU prefix actually used. When `--cpu-cap`
2354// is absent the planner defaults to 30% of the calling process's
2355// sched_getaffinity cpuset (see [`default_cpu_budget`] and
2356// [`host_allowed_cpus`]) — not 30% of the host's online CPU count,
2357// because a CI runner whose parent cgroup pins ktstr to a 4-CPU
2358// subset must plan within THAT subset or sched_setaffinity on the
2359// resulting mask produces an empty effective set.
2360// Perf-mode never reaches this path; it uses topology-candidate admission
2361// with LLC and CPU modes recorded explicitly in each exact claim.
2362//
2363// The acquisition pipeline has three phases: discover (snapshot holders per
2364// LLC, filtered to the process's allowed cpuset), plan (NUMA-aware
2365// selection under the caller's [`PlacementPolicy`] — Consolidate for
2366// kernel-build workloads, Spread for no-perf VM runs), acquire (non-blocking `LOCK_SH`
2367// on each selected LLC and exact selected CPU). Up to
2368// ACQUIRE_MAX_TOCTOU_RETRIES retries
2369// absorb the window between the discover snapshot and the
2370// non-blocking acquire; between retries the loop sleeps for an
2371// ascending micro-budget (TOCTOU_RETRY_DELAYS) so a peer that
2372// raced us has time to drop its fds before the next snapshot.
2373// If every retry fails, the contention is persistent and the
2374// caller falls back to nextest-retry / operator-wait.
2375
2376/// Return the CPUs the calling process is allowed to run on, per
2377/// `sched_getaffinity(2)` with a `/proc/self/status` Cpus_allowed_list
2378/// fallback. Every consumer of the `--cpu-cap` pipeline plans against
2379/// this set instead of `HostTopology::online_cpus` so
2380/// `sched_setaffinity` on the plan's CPU list never produces an empty
2381/// effective mask under a cgroup-restricted runner (CI hosts, systemd
2382/// slices, sudo -u under a limited cpuset).
2383///
2384/// Returns an empty vec only when BOTH the syscall AND procfs fail —
2385/// a pathological host that can't enumerate its own affinity. Callers
2386/// treat that as a bail reason, not a fallback "every CPU" permission:
2387/// guessing on a misconfigured host is worse than failing visibly.
2388///
2389/// Tests override the return value via `ALLOWED_CPUS_OVERRIDE` so
2390/// the 30% default and allowed-cpu filtering are deterministic in
2391/// unit tests regardless of the CI runner's real cpuset.
2392pub(crate) fn host_allowed_cpus() -> Vec<usize> {
2393    #[cfg(test)]
2394    {
2395        if let Some(override_set) = ALLOWED_CPUS_OVERRIDE.with(|p| p.borrow().clone()) {
2396            return override_set;
2397        }
2398    }
2399    if let Some(cpus) = crate::cpu_util::read_affinity(0) {
2400        return cpus.into_iter().map(|c| c as usize).collect();
2401    }
2402    if let Ok(raw) = std::fs::read_to_string("/proc/self/status") {
2403        for line in raw.lines() {
2404            if let Some(v) = line.strip_prefix("Cpus_allowed_list:")
2405                && let Some(parsed) = crate::cpu_util::parse_cpu_list(v.trim())
2406            {
2407                return parsed.into_iter().map(|c| c as usize).collect();
2408            }
2409        }
2410    }
2411    Vec::new()
2412}
2413
2414/// CPUs eligible for selected-intent preparation. The final claim retains its
2415/// complete topology footprint, but temporary preparation affinity can only
2416/// name CPUs the current process is actually permitted to enter.
2417pub(super) fn preparation_affinity_candidates(
2418    selected: &std::collections::BTreeSet<usize>,
2419    allowed: &[usize],
2420) -> Vec<usize> {
2421    allowed
2422        .iter()
2423        .copied()
2424        .filter(|cpu| selected.contains(cpu))
2425        .collect()
2426}
2427
2428#[cfg(test)]
2429thread_local! {
2430    /// Test-only override for [`host_allowed_cpus`]. Set via
2431    /// [`AllowedCpusGuard`] to make 30%-of-allowed calculations and
2432    /// plan filtering deterministic in unit tests. Mirrors the
2433    /// `LLC_LOCK_PREFIX_OVERRIDE` pattern.
2434    pub(crate) static ALLOWED_CPUS_OVERRIDE: std::cell::RefCell<Option<Vec<usize>>> =
2435        const { std::cell::RefCell::new(None) };
2436}
2437
2438/// Default CPU budget when `--cpu-cap` is not set: 30% of the
2439/// allowed-CPU count, rounded up, with a min-1 floor for small or
2440/// degenerate hosts. 30% leaves enough headroom for concurrent peers
2441/// (tests, builds) while still reserving a non-trivial slice; the
2442/// min-1 floor prevents returning 0 on a 1- or 2-CPU host, where
2443/// ceil(×0.30) ≥ 1 anyway — the `.max(1)` is defense in depth for
2444/// future ratio tweaks.
2445fn default_cpu_budget(allowed_cpus: usize) -> usize {
2446    allowed_cpus.saturating_mul(30).div_ceil(100).max(1)
2447}
2448
2449/// No-perf CPU budget when no explicit `--cpu-cap` (or `cpu_budget` knob) is
2450/// set: the VM's own vCPU count PLUS ONE service CPU, clamped to the allowed
2451/// cpuset (min-1). That is the topology's actual need: one host CPU per
2452/// guest vCPU, plus headroom for the host-side service threads (monitor,
2453/// watchdog, virtio, workload coordination) that live INSIDE the cell's
2454/// cgroup and would otherwise CFS-contend with spinning vCPUs on an
2455/// exactly-vcpus cpuset — the budgeted-path analog of the performance
2456/// planner's dedicated service CPU. Sensing timeliness rides on this: on
2457/// hosts without CAP_SYS_NICE the sensing threads run
2458/// SCHED_OTHER, and a starved monitor thins the contention witness the
2459/// latency verdicts consume.
2460///
2461/// The rationale is TEST VALIDITY, not boot speed — do not "optimize" this
2462/// back to a flat 30%. A scheduler test measures how the GUEST scheduler
2463/// places tasks across the guest's CPUs. If the VM's vCPU threads are
2464/// oversubscribed on the host (256 vCPUs sharing the 30% default mask is
2465/// ~95 pCPUs = 2.7x), the HOST scheduler time-slices them, so guest vCPUs
2466/// stall for reasons unrelated to the workload — a host-contention confound
2467/// that invalidates the guest-scheduler measurement (the silent-wrong-answer
2468/// class the project guards against). Sizing the budget to `vcpus + 1` when
2469/// host capacity permits gives the guest's CPUs real host CPUs and leaves
2470/// service-thread headroom, so its scheduler view tracks real concurrency.
2471/// (A wide boot also drops ~0.7s as the kernel's parallel AP bring-up runs
2472/// unthrottled, but that is incidental.)
2473///
2474/// NOT floored at the 30% `default_cpu_budget`. That floor was a bug: it made
2475/// a SMALL VM over-reserve on a LARGE host — a 2-vCPU interactive shell on a
2476/// ~192-CPU box resolved to `max(58, 2) = 58` CPUs (~30%). The reservation
2477/// walks WHOLE LLCs to reach the budget, so a bigger budget needs more LLCs
2478/// that are free for `LOCK_SH`; when peer runners' perf-mode work holds LLCs
2479/// `LOCK_EX` the plan cannot find 58 CPUs' worth and bails
2480/// (`acquire_llc_plan: could not reserve 58 CPU(s) after 4 attempts`). A
2481/// SMALLER reservation frees LLCs for peers, not the reverse, so a small VM
2482/// asking ~30% is backwards. 30% is the right default for throughput-elastic
2483/// kernel builds (`default_cpu_budget`, `make -j`), never a floor for a VM
2484/// whose need is fixed by its vCPU count. `vcpus + 1 > allowed` clamps to
2485/// `allowed` (the process-cpuset-too-small case), which
2486/// [`overcommit_warning`] surfaces. An explicit cap LOWER than vcpus stays
2487/// the deliberate opt-in to oversubscribe for contention testing.
2488pub(crate) fn no_perf_cpu_budget(allowed_cpus: usize, vm_vcpus: usize) -> usize {
2489    vm_vcpus.saturating_add(1).min(allowed_cpus).max(1)
2490}
2491
2492/// Parsed `--cpu-cap N` value. N is a CPU count: the planner reserves
2493/// exactly N host CPUs by walking whole LLCs in contention- /
2494/// NUMA-aware order (filtered to the calling process's allowed
2495/// cpuset) and partial-taking the last LLC so `plan.cpus.len() == N`.
2496/// The last LLC is flocked whole, while CPU `LOCK_SH` covers only the exact
2497/// prefix entering `plan.cpus`.
2498/// Bounded to `1..=usize::MAX` at the constructor — a cap of 0 is
2499/// nonsensical (reserving zero CPUs is just "don't run") and
2500/// rejected upstream by the CLI layer, but we enforce the bound in
2501/// the type system via `NonZeroUsize` so callers can
2502/// `CpuCap::new(...)?` without a follow-up bounds check.
2503///
2504/// The runtime upper bound — "don't exceed the process's allowed
2505/// CPU count" — is enforced at acquire time via
2506/// [`CpuCap::effective_count`] because the allowed set is not known
2507/// until `host_allowed_cpus` reads `sched_getaffinity`.
2508#[derive(Debug, Clone, Copy, PartialEq, Eq)]
2509pub struct CpuCap {
2510    n: std::num::NonZeroUsize,
2511}
2512
2513impl CpuCap {
2514    /// Construct from a raw `usize` CPU count. Returns `Err` on `0`;
2515    /// `usize::MAX` is accepted here and clamped later by
2516    /// `effective_count`.
2517    pub fn new(n: usize) -> Result<Self> {
2518        std::num::NonZeroUsize::new(n)
2519            .map(|n| CpuCap { n })
2520            .ok_or_else(|| anyhow::anyhow!("--cpu-cap must be ≥ 1 CPU (got 0)"))
2521    }
2522
2523    /// Three-tier resolution: explicit CLI flag wins over env var,
2524    /// which wins over "not set". Returns `None` when neither is present,
2525    /// meaning "use the caller's auto-sized default": the
2526    /// kernel-build/planner path expands `None` to `default_cpu_budget`
2527    /// (30% of the allowed set); the no-perf VM-builder path expands it to
2528    /// `no_perf_cpu_budget` (`vcpus + 1`, clamped to the allowed cpuset and
2529    /// at least 1). The extra CPU leaves room for the VMM/control threads;
2530    /// this default is NOT floored at 30%.
2531    ///
2532    /// Env var is `KTSTR_CPU_CAP` (integer ≥ 1, CPU count). An empty
2533    /// or unset env var is treated as absent; a non-numeric value
2534    /// OR the numeric value `0` is an error — `KTSTR_CPU_CAP=0`
2535    /// flows through `CpuCap::new(0)` which rejects with "--cpu-cap
2536    /// must be ≥ 1 CPU (got 0)". Zero is not a silent fallback to
2537    /// "no cap"; it surfaces as a parse-time error so typos and
2538    /// scripting mistakes don't accidentally disable the resource
2539    /// contract.
2540    pub fn resolve(cli_flag: Option<usize>) -> Result<Option<CpuCap>> {
2541        if let Some(n) = cli_flag {
2542            return Ok(Some(CpuCap::new(n)?));
2543        }
2544        match std::env::var(crate::KTSTR_CPU_CAP_ENV) {
2545            Ok(s) if s.is_empty() => Ok(None),
2546            Ok(s) => {
2547                let n: usize = s
2548                    .parse()
2549                    .with_context(|| format!("KTSTR_CPU_CAP is not a valid integer: {s:?}"))?;
2550                Ok(Some(CpuCap::new(n)?))
2551            }
2552            Err(std::env::VarError::NotPresent) => Ok(None),
2553            Err(std::env::VarError::NotUnicode(raw)) => {
2554                anyhow::bail!(
2555                    "KTSTR_CPU_CAP contains non-UTF-8 bytes ({} bytes): {raw:?}. \
2556                     Set an integer value or unset.",
2557                    raw.len(),
2558                )
2559            }
2560        }
2561    }
2562
2563    /// Runtime-bounded cap: returns the inner count unless it exceeds
2564    /// `allowed_cpus` (the calling process's sched_getaffinity cpuset
2565    /// count), in which case a `CpuBudgetUnsatisfiable` hard error (an
2566    /// explicit cap the host cannot satisfy is a FAIL, not a transient
2567    /// skip) steers the caller toward an actionable message. This check
2568    /// lives at acquire time — not at construction — because the allowed
2569    /// set is not known until `host_allowed_cpus` reads the syscall.
2570    pub fn effective_count(&self, allowed_cpus: usize) -> Result<usize> {
2571        let n = self.n.get();
2572        if n > allowed_cpus {
2573            // An explicit --cpu-cap the host cannot satisfy is a hard ERROR
2574            // (the author typed a concrete number that does not exist here),
2575            // not transient contention: CpuBudgetUnsatisfiable, not
2576            // ResourceContention, so it fails rather than skips.
2577            return Err(anyhow::Error::new(CpuBudgetUnsatisfiable {
2578                reason: format!(
2579                    "--cpu-cap N = {n} exceeds the {allowed_cpus} CPUs this \
2580                     process is allowed on (from sched_getaffinity / \
2581                     Cpus_allowed_list). Pick a value ≤ {allowed_cpus}, \
2582                     release the cgroup/taskset constraint restricting this \
2583                     process, or omit --cpu-cap to use the auto-sized default \
2584                     (30% of the allowed set for kernel builds; \
2585                     min(vCPUs + 1, allowed CPUs) for no-perf VMs)."
2586                ),
2587            }));
2588        }
2589        Ok(n)
2590    }
2591}
2592
2593/// Placement policy for the PLAN phase of [`acquire_llc_plan_interruptible`]:
2594/// which LLCs a reservation prefers when more are eligible than the
2595/// budget needs.
2596///
2597/// `Consolidate` packs onto the LLCs already holding peers
2598/// (holder_count DESC, llc_idx ASC) so the rest of the host stays
2599/// whole for exclusive perf-mode reservations. Elastic build admission
2600/// uses this policy for its LLC footprint while independently using
2601/// [`Spread`](Self::Spread) for the exact CPUs inside that footprint.
2602///
2603/// `Spread` picks the LEAST-held LLCs (holder_count ASC), breaking
2604/// ties by the eligible-list position rotated by `rotation`. Right
2605/// for no-perf VM vCPU placement, where Consolidate is
2606/// pathological: every concurrent VM cell would mask its vCPU
2607/// threads onto the same most-held LLCs — and since plans are
2608/// computed at `build()` without live holder state, a fan-out of
2609/// simultaneously-planning cells all see the same zero-occupancy shape and
2610/// the llc_idx-ASC tiebreak stacks every one of them onto the identical
2611/// LLC-0-upward prefix. Observed in the scx
2612/// verifier sweep: a 30-cell matrix on a 16-LLC runner piled every
2613/// small and mid-sized cell's mask onto the same low-LLC prefix
2614/// (the widest cells' whole-host masks overlapping it) while the
2615/// high LLCs ran near-idle — guests starved hard enough that
2616/// attached schedulers tripped the guest kernel's sched_ext stall
2617/// watchdog and wide-topology boots outran the VM deadline. The
2618/// per-process `rotation` (derive it via `pid_window_offset`) is
2619/// what breaks that zero-knowledge symmetry; holder_count ASC then
2620/// keeps later arrivals off whichever LLCs the earlier ones
2621/// actually locked.
2622#[derive(Debug, Clone, Copy, PartialEq, Eq)]
2623pub enum PlacementPolicy {
2624    /// Pack onto already-held resources. Direct fixed-size kernel builds use
2625    /// this policy for both LLCs and CPUs. Elastic harness and scheduler
2626    /// prebuilds use it only for LLCs, then select least-held CPUs separately.
2627    Consolidate,
2628    /// Fan out across least-held LLCs, tie-broken by `rotation`
2629    /// (no-perf VM placement). `rotation` is reduced modulo the
2630    /// eligible-LLC count internally; any process-stable value works.
2631    Spread { rotation: usize },
2632}
2633
2634impl PlacementPolicy {
2635    /// `Spread` seeded for this process: rotation from
2636    /// `pid_window_offset` over a wide domain so the later
2637    /// modulo-by-eligible-count stays uniform for any LLC count.
2638    pub fn spread_for_process() -> Self {
2639        PlacementPolicy::Spread {
2640            rotation: pid_window_offset(std::process::id(), 1 << 16),
2641        }
2642    }
2643}
2644
2645/// CPU ranking inside an LLC footprint selected by [`PlacementPolicy`].
2646///
2647/// Exact reservations retain the historical per-LLC walk: the same policy
2648/// selects LLCs and orders CPUs within each LLC. Elastic builds instead rank
2649/// every CPU in their already-consolidated footprint together, so a free CPU
2650/// in a later LLC wins over a shared CPU in an earlier LLC without spreading
2651/// the LLC locks themselves.
2652#[derive(Debug, Clone, Copy, PartialEq, Eq)]
2653enum CpuSelectionPolicy {
2654    WithinEachLlc(PlacementPolicy),
2655    LeastHeldAcrossFootprint { rotation: usize },
2656}
2657
2658impl CpuSelectionPolicy {
2659    fn least_held_for_process() -> Self {
2660        Self::LeastHeldAcrossFootprint {
2661            rotation: pid_window_offset(std::process::id(), 1 << 16),
2662        }
2663    }
2664}
2665
2666/// Per-LLC discover snapshot: identity + registered holder occupancy.
2667/// Constructed by [`discover_registered_placement_states`] before the PLAN
2668/// phase.
2669/// `pub(crate)` so the in-crate PLAN pipeline and this module's tests
2670/// can construct and inspect it; the `ktstr locks` observational
2671/// command shares only [`crate::flock::HolderInfo`], not this
2672/// structure. External callers have no reason to construct one.
2673#[derive(Debug, Clone)]
2674pub(crate) struct LlcSnapshot {
2675    /// Host LLC index — matches [`HostTopology::llc_groups`] ordering.
2676    pub(crate) llc_idx: usize,
2677    /// Count of registered holder claims other than this process, cached for
2678    /// PLAN scoring. Derived from the admission registry aggregate, not from a
2679    /// `/proc/locks` walk.
2680    pub(crate) holder_count: usize,
2681    /// Whether the registry aggregate reports a registered `LOCK_EX` holder
2682    /// of this LLC. Live planning drops such an LLC outright — no SH request
2683    /// can coexist with it — while the queued designation deliberately keeps
2684    /// it, being a static full-budget candidate rather than a live selection.
2685    /// The authoritative nonblocking flock still resolves races against
2686    /// holders the aggregate has not published yet.
2687    pub(crate) exclusive_held: bool,
2688    /// Count of in-flight grant charges (GRANTED/REVOKED registry records)
2689    /// covering this LLC. Subordinate rank key only: it biases both policies
2690    /// toward grant-free LLCs but never partitions, filters, or fences —
2691    /// folding it into `holder_count` would turn Consolidate's DESC primary
2692    /// key into a magnet steering builds onto granted footprints.
2693    pub(crate) granted_count: usize,
2694}
2695
2696/// Output of [`acquire_llc_plan_interruptible`]: the concrete LLC reservation plus
2697/// every piece of diagnostic context a downstream consumer could
2698/// want.
2699///
2700/// `mems` is the union of NUMA nodes containing the selected CPUs —
2701/// `BuildSandbox::try_create` writes this to the child cgroup's
2702/// `cpuset.mems` so memory allocations respect the same NUMA locality
2703/// the CPU reservation already implies.
2704///
2705/// `locks` holds shared admission owners whose final logical drop explicitly
2706/// unlocks the kernel-side flock before closing its descriptor; the field is
2707/// `pub(crate)` because direct manipulation from outside the crate would
2708/// defeat that release-order guarantee.
2709#[derive(Debug)]
2710pub struct LlcPlan {
2711    /// Selected host LLC indices, sorted ASCENDING. Acquire order
2712    /// matches this slice — two callers with the same target see the
2713    /// same ordering and converge on the same one-wins-the-others-retry
2714    /// livelock-proof sequence.
2715    pub locked_llcs: Vec<usize>,
2716    /// Flattened host CPU list, sized exactly `target_cpus`. The last
2717    /// locked LLC may contribute only a prefix of its allowed CPUs.
2718    /// Preserves LLC ordering: CPUs from `locked_llcs[0]` come
2719    /// before CPUs from `locked_llcs[1]`, etc.
2720    pub cpus: Vec<usize>,
2721    /// Weighted host-admission permits held atomically with the topology
2722    /// locks. Empty only for ownership-free/static planning paths.
2723    pub(crate) permits: Vec<usize>,
2724    /// Union of NUMA nodes hosting the locked LLCs. When the plan
2725    /// spans > 1 node (cross-node spill — seed node exhausted, plan
2726    /// spilled to nearest-by-distance neighbors), `mems`
2727    /// contains every node — not just the seed node's.
2728    pub mems: std::collections::BTreeSet<usize>,
2729    /// RAII flock holders. Dropped when the plan goes out of scope,
2730    /// releasing each LLC's `LOCK_SH` in declared order.
2731    #[allow(dead_code)] // RAII only — Drop releases flocks, no reads.
2732    pub(crate) locks: protocol::Acquired<Vec<protocol::AdmissionFlock>>,
2733}
2734
2735/// Maximum TOCTOU retry budget for the DISCOVER → PLAN → ACQUIRE
2736/// pipeline. Production sees up to `RETRIES + 1 = 4` attempts: one
2737/// initial DISCOVER and three retries. Between retries the caller
2738/// sleeps for an ascending micro-budget (10ms, 50ms, 200ms — see
2739/// [`TOCTOU_RETRY_DELAYS`]) so two peers that initially raced on the
2740/// same LLC have time to drop their fds before the next snapshot.
2741/// Without the sleep the second DISCOVER often sees the same holder
2742/// state and bails on a transient race; the in-process micro-sleep
2743/// absorbs that without paying the nextest-retry cost.
2744const ACQUIRE_MAX_TOCTOU_RETRIES: u32 = 3;
2745
2746/// Per-retry sleep durations between DISCOVER attempts. Indexed by
2747/// the retry index: after attempt 0 fails the loop sleeps
2748/// `TOCTOU_RETRY_DELAYS[0]`, after attempt 1 fails it sleeps
2749/// `TOCTOU_RETRY_DELAYS[1]`, etc. Length must equal
2750/// [`ACQUIRE_MAX_TOCTOU_RETRIES`] — there are exactly that many
2751/// sleeps before the final attempt that can still bail.
2752const TOCTOU_RETRY_DELAYS: [std::time::Duration; ACQUIRE_MAX_TOCTOU_RETRIES as usize] = [
2753    std::time::Duration::from_millis(10),
2754    std::time::Duration::from_millis(50),
2755    std::time::Duration::from_millis(200),
2756];
2757
2758/// Read the current-version admission registry once and derive every
2759/// placement score from that one coherent image.
2760///
2761/// Every successful current-version acquisition publishes a HELD record
2762/// before it can leave the registry fence. Consequently this is the normal
2763/// planning source for both LLC and CPU occupancy; the final nonblocking
2764/// flocks remain the authority for races and unrelated lock users.
2765fn discover_registered_placement_states(
2766    topo: &HostTopology,
2767    allowed: &std::collections::BTreeSet<usize>,
2768) -> Result<(
2769    Vec<LlcSnapshot>,
2770    std::collections::BTreeMap<usize, CpuPlacementState>,
2771    protocol::RegisteredClaimSnapshot,
2772)> {
2773    let llcs = topo
2774        .llc_groups
2775        .iter()
2776        .enumerate()
2777        .filter_map(|(llc_idx, group)| {
2778            group
2779                .cpus
2780                .iter()
2781                .any(|cpu| allowed.contains(cpu))
2782                .then_some(llc_idx)
2783        })
2784        .collect::<Vec<_>>();
2785    let required = protocol::ClaimSet::with_modes(
2786        llcs.iter().copied(),
2787        allowed.iter().copied(),
2788        FlockMode::Shared,
2789        FlockMode::Shared,
2790    );
2791    let aggregate = protocol::registered_claim_snapshot(&required)?;
2792    // The grant fields below are planner bias only. They must never fold
2793    // into the holder scalars, the unshared filter in `live_cpu_capacity`,
2794    // or `exclusive_held` — wiring them there re-creates the Consolidate
2795    // attraction magnet and the elastic-shrink capacity miscounts.
2796    let snapshots = llcs
2797        .into_iter()
2798        .map(|llc_idx| {
2799            Ok(LlcSnapshot {
2800                llc_idx,
2801                holder_count: aggregate.llc_holder_count(llc_idx)?,
2802                exclusive_held: aggregate.llc_exclusive_held(llc_idx)?,
2803                granted_count: aggregate.llc_grant_count(llc_idx)?,
2804            })
2805        })
2806        .collect::<Result<Vec<_>>>()?;
2807    let cpu_states = allowed
2808        .iter()
2809        .copied()
2810        .map(|cpu| {
2811            Ok((
2812                cpu,
2813                CpuPlacementState {
2814                    exclusive_held: aggregate.cpu_exclusive_held(cpu)?,
2815                    other_holders: aggregate.cpu_holder_count(cpu)?,
2816                    granted_holders: aggregate.cpu_grant_count(cpu)?,
2817                },
2818            ))
2819        })
2820        .collect::<Result<std::collections::BTreeMap<_, _>>>()?;
2821    Ok((snapshots, cpu_states, aggregate))
2822}
2823
2824/// PLAN phase — NUMA-aware placement over discover snapshots.
2825///
2826/// Composite sort driven by three ordered keys:
2827///   1. Placement policy — [`PlacementPolicy::Consolidate`] prefers
2828///      LLCs already holding peers (holder_count DESC); elastic
2829///      callers rotate only the fresh suffix so simultaneous cold
2830///      starts and post-consolidation spill do not converge on one
2831///      prefix;
2832///      [`PlacementPolicy::Spread`] prefers the least-held LLCs
2833///      (holder_count ASC) with a caller-rotated tiebreak.
2834///   2. NUMA locality — after seeding on the highest-scored LLC's
2835///      node, greedily fill the seed node before spilling.
2836///   3. LLC index tiebreak — ASC for Consolidate, ASC rotated by the
2837///      policy's offset for Spread. The final ACQUIRE ordering is
2838///      plain ASC under BOTH policies (step e re-sorts), so every
2839///      concurrent acquirer walks lockfiles in one global order and
2840///      the livelock-safety argument is policy-independent.
2841///
2842/// `target_cpus` is the exact number of allowed CPUs the plan
2843/// reserves. The walk selects whole LLCs (filtered to their
2844/// allowed-CPU overlap) until the accumulated contribution meets
2845/// the budget. The LAST selected LLC may contribute more allowed
2846/// CPUs than the remaining budget needs; the materialization layer
2847/// at [`materialize_plan_cpus`] takes only the needed
2848/// prefix of that LLC's allowed CPUs into `plan.cpus`. The flock
2849/// is always held at LLC granularity — coordination with concurrent
2850/// ktstr peers happens per-LLC, regardless of how many of the LLC's
2851/// CPUs are consumed here. LLCs whose CPUs are all outside
2852/// `allowed` are skipped entirely — locking one would never
2853/// contribute a schedulable CPU to `plan.cpus`.
2854///
2855/// Distance fallback: callers without a distance matrix pass a closure
2856/// that returns `10` for equal nodes and `20` otherwise — primitive 3
2857/// keeps the spill order reasonable even on hosts whose
2858/// `/sys/devices/system/node/*/distance` is unavailable.
2859fn plan_from_snapshots(
2860    snapshots: &[LlcSnapshot],
2861    target_cpus: usize,
2862    topo: &HostTopology,
2863    allowed: &std::collections::BTreeSet<usize>,
2864    distance_fn: impl Fn(usize, usize) -> u8,
2865    policy: PlacementPolicy,
2866) -> Vec<usize> {
2867    plan_from_snapshots_with_fresh_rotation(
2868        snapshots,
2869        target_cpus,
2870        topo,
2871        allowed,
2872        distance_fn,
2873        policy,
2874        None,
2875    )
2876}
2877
2878/// Elastic-build form of [`plan_from_snapshots`].
2879///
2880/// Every simultaneous elastic process would otherwise choose the same
2881/// LLC-index prefix after exhausting any peer-held consolidation candidates.
2882/// An explicit process-stable rotation breaks only the fresh-suffix symmetry;
2883/// peer-held candidates retain ordinary Consolidate scoring and always remain
2884/// ahead of every fresh candidate.
2885fn plan_from_snapshots_with_fresh_rotation(
2886    snapshots: &[LlcSnapshot],
2887    target_cpus: usize,
2888    topo: &HostTopology,
2889    allowed: &std::collections::BTreeSet<usize>,
2890    distance_fn: impl Fn(usize, usize) -> u8,
2891    policy: PlacementPolicy,
2892    consolidate_fresh_rotation: Option<usize>,
2893) -> Vec<usize> {
2894    if target_cpus == 0 {
2895        return Vec::new();
2896    }
2897
2898    // Allowed-CPU count contributed by each LLC. An LLC with zero
2899    // overlap contributes no schedulable CPUs to `plan.cpus`, so
2900    // reserving it adds a useless flock and no planning value — drop
2901    // those up front so every subsequent walk only considers
2902    // candidates that can actually carry budget.
2903    let llc_allowed_cpus = |idx: usize| -> usize {
2904        topo.llc_groups[idx]
2905            .cpus
2906            .iter()
2907            .filter(|c| allowed.contains(c))
2908            .copied()
2909            .collect::<std::collections::BTreeSet<_>>()
2910            .len()
2911    };
2912    let total_allowed_in_llcs = snapshots
2913        .iter()
2914        .flat_map(|snapshot| topo.llc_groups[snapshot.llc_idx].cpus.iter().copied())
2915        .filter(|cpu| allowed.contains(cpu))
2916        .collect::<std::collections::BTreeSet<_>>()
2917        .len();
2918    if target_cpus >= total_allowed_in_llcs {
2919        // Budget ≥ sum of per-LLC contributions: select every LLC
2920        // that has at least one allowed CPU, in ascending order.
2921        // Short-circuits the scoring walk when the cap degenerates
2922        // to "reserve everything we can schedule on."
2923        let mut all: Vec<usize> = snapshots
2924            .iter()
2925            .map(|snapshot| snapshot.llc_idx)
2926            .filter(|&idx| llc_allowed_cpus(idx) > 0)
2927            .collect();
2928        all.sort_unstable();
2929        return all;
2930    }
2931
2932    // Step a: partition + sort. Only LLCs with at least one allowed
2933    // CPU are eligible — locking an out-of-cpuset LLC is useless.
2934    let eligible = |s: &&LlcSnapshot| -> bool { llc_allowed_cpus(s.llc_idx) > 0 };
2935    let ranked: Vec<&LlcSnapshot> = match policy {
2936        // Consolidation candidates first (holder_count DESC, llc_idx
2937        // ASC); fresh candidates after, sorted by llc_idx ASC. A
2938        // single composite sort would do the same work but the
2939        // two-partition form is easier to read and lets future
2940        // "prefer consolidation only if score ≥ threshold" tweaks
2941        // slot in.
2942        PlacementPolicy::Consolidate => {
2943            let mut consolidation: Vec<&LlcSnapshot> = snapshots
2944                .iter()
2945                .filter(|s| s.holder_count > 0)
2946                .filter(eligible)
2947                .collect();
2948            let mut fresh: Vec<&LlcSnapshot> = snapshots
2949                .iter()
2950                .filter(|s| s.holder_count == 0)
2951                .filter(eligible)
2952                .collect();
2953            // `granted_count` is a subordinate key in both partitions: the
2954            // HELD-only holder count keeps its primary DESC sign (so grant
2955            // charge can never become a consolidation magnet), and a
2956            // granted-only LLC still partitions as fresh — grant avoidance
2957            // is a preference among otherwise-equal candidates, never a
2958            // fence.
2959            consolidation.sort_by(|a, b| {
2960                b.holder_count
2961                    .cmp(&a.holder_count)
2962                    .then(a.granted_count.cmp(&b.granted_count))
2963                    .then(a.llc_idx.cmp(&b.llc_idx))
2964            });
2965            fresh.sort_by_key(|s| s.llc_idx);
2966            if let Some(rotation) = consolidate_fresh_rotation
2967                && !fresh.is_empty()
2968            {
2969                let count = fresh.len();
2970                fresh.rotate_left(rotation % count);
2971            }
2972            // Prefer grant-free fresh LLCs while preserving the rotated
2973            // symmetry-breaking order within each grant-charge class. The
2974            // sort is stable, so equal-count candidates keep the rotation.
2975            fresh.sort_by_key(|s| s.granted_count);
2976            consolidation.into_iter().chain(fresh).collect()
2977        }
2978        // Least-held first, ties broken by rotated eligible position
2979        // so simultaneous planners with identical (typically
2980        // all-zero) holder snapshots fan out across the host instead
2981        // of converging on the same LLC-0-upward prefix. The rotation
2982        // is reduced modulo the ELIGIBLE count — rotating over raw
2983        // LLC indices would bias toward whichever indices survive the
2984        // cpuset filter.
2985        PlacementPolicy::Spread { rotation } => {
2986            let mut spread: Vec<&LlcSnapshot> = snapshots.iter().filter(eligible).collect();
2987            spread.sort_by_key(|s| s.llc_idx);
2988            let n = spread.len();
2989            if n > 0 {
2990                let start = rotation % n;
2991                // Rotated position of each eligible snapshot in the
2992                // llc_idx-ASC ordering (`start` maps to 0), keyed by
2993                // llc_idx. Precomputed: the comparator below cannot
2994                // itself search `spread` mid-sort.
2995                let rotated_pos: std::collections::HashMap<usize, usize> = spread
2996                    .iter()
2997                    .enumerate()
2998                    .map(|(p, s)| (s.llc_idx, (p + n - start) % n))
2999                    .collect();
3000                spread.sort_by(|a, b| {
3001                    a.holder_count
3002                        .cmp(&b.holder_count)
3003                        .then(a.granted_count.cmp(&b.granted_count))
3004                        .then(rotated_pos[&a.llc_idx].cmp(&rotated_pos[&b.llc_idx]))
3005                });
3006            }
3007            spread
3008        }
3009    };
3010    if ranked.is_empty() {
3011        // No LLC on this host overlaps the caller's allowed cpuset.
3012        // Bail upstream handles this as ResourceContention; here we
3013        // just return empty so the caller can surface the diagnostic.
3014        return Vec::new();
3015    }
3016
3017    // Step b: seed. Highest-scored eligible LLC; its NUMA node
3018    // anchors the greedy expansion.
3019    let seed = ranked[0];
3020    let seed_node = topo.llc_numa_node(seed.llc_idx);
3021
3022    // Step c–d: walk seed-node LLCs first, then spill to
3023    // nearest-by-distance nodes. Primitives 1 + 3 drive the node
3024    // ordering; the per-node LLC lists come from primitive 1. Within
3025    // each node, we still honour the composite score by walking
3026    // `ranked` and skipping LLCs not on the current target node.
3027    // Accumulation is by allowed-CPU contribution — an LLC with 4
3028    // CPUs of which 2 are in `allowed` counts as 2 toward the
3029    // budget and the other 2 never appear in `plan.cpus`.
3030    let node_order = topo.numa_nodes_sorted_by_distance(seed_node, distance_fn);
3031    let mut selected: Vec<usize> = Vec::new();
3032    let mut picked: std::collections::HashSet<usize> = std::collections::HashSet::new();
3033    let mut accumulated = std::collections::BTreeSet::new();
3034    for node in node_order {
3035        if accumulated.len() >= target_cpus {
3036            break;
3037        }
3038        // Ranked walk, taking every candidate on this node in
3039        // score-order until we've filled `target_cpus` or exhausted
3040        // the node.
3041        for snap in &ranked {
3042            if accumulated.len() >= target_cpus {
3043                break;
3044            }
3045            if picked.contains(&snap.llc_idx) {
3046                continue;
3047            }
3048            if topo.llc_numa_node(snap.llc_idx) != node {
3049                continue;
3050            }
3051            selected.push(snap.llc_idx);
3052            picked.insert(snap.llc_idx);
3053            accumulated.extend(
3054                topo.llc_groups[snap.llc_idx]
3055                    .cpus
3056                    .iter()
3057                    .copied()
3058                    .filter(|cpu| allowed.contains(cpu)),
3059            );
3060        }
3061    }
3062
3063    // Step e: livelock-proof acquire order — ascending index.
3064    selected.sort_unstable();
3065    selected
3066}
3067
3068/// Remove queue-only predecessor reservations when the remaining LLCs can
3069/// still carry the requested budget.
3070///
3071/// These claims have no `/proc/locks` row until their owner acquires a real
3072/// flock. Filtering them before policy scoring makes both Spread and
3073/// Consolidate prefer disjoint capacity. If the filtered capacity cannot
3074/// satisfy the exact budget, return the full snapshot so predecessor resources
3075/// remain eligible as the necessary last resort.
3076fn physical_candidate_for_watch(
3077    llcs: impl IntoIterator<Item = usize>,
3078    cpus: impl IntoIterator<Item = usize>,
3079    llc_mode: FlockMode,
3080    cpu_mode: FlockMode,
3081    watch_class: protocol::AdmissionClass,
3082) -> protocol::ClaimSet {
3083    protocol::ClaimSet::with_modes(llcs, cpus, llc_mode, cpu_mode).with_admission_class(watch_class)
3084}
3085
3086fn avoid_preceding_claims_when_possible(
3087    snapshots: &[LlcSnapshot],
3088    target_cpus: usize,
3089    topo: &HostTopology,
3090    allowed: &std::collections::BTreeSet<usize>,
3091    watch_class: protocol::AdmissionClass,
3092    mut conflicts: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
3093) -> Result<Vec<LlcSnapshot>> {
3094    let mut unreserved = Vec::with_capacity(snapshots.len());
3095    for snapshot in snapshots {
3096        let candidate = physical_candidate_for_watch(
3097            [snapshot.llc_idx],
3098            std::iter::empty(),
3099            FlockMode::Shared,
3100            FlockMode::Shared,
3101            watch_class,
3102        );
3103        if !conflicts(&candidate)? {
3104            unreserved.push(snapshot.clone());
3105        }
3106    }
3107    let available_cpus = unreserved
3108        .iter()
3109        .flat_map(|snapshot| topo.llc_groups[snapshot.llc_idx].cpus.iter().copied())
3110        .filter(|cpu| allowed.contains(cpu))
3111        .collect::<std::collections::BTreeSet<_>>()
3112        .len();
3113    if available_cpus >= target_cpus {
3114        Ok(unreserved)
3115    } else {
3116        Ok(snapshots.to_vec())
3117    }
3118}
3119
3120enum LlcLockAttempt {
3121    Acquired(Vec<protocol::AdmissionFlock>),
3122    Contended(protocol::ContentionEvidence),
3123    #[cfg(test)]
3124    Unavailable,
3125}
3126
3127trait IntoLlcLockAttempt {
3128    fn into_llc_lock_attempt(self) -> LlcLockAttempt;
3129}
3130
3131impl IntoLlcLockAttempt for LlcLockAttempt {
3132    fn into_llc_lock_attempt(self) -> LlcLockAttempt {
3133        self
3134    }
3135}
3136
3137#[cfg(test)]
3138impl IntoLlcLockAttempt for Option<Vec<protocol::AdmissionFlock>> {
3139    fn into_llc_lock_attempt(self) -> LlcLockAttempt {
3140        self.map_or(LlcLockAttempt::Unavailable, LlcLockAttempt::Acquired)
3141    }
3142}
3143
3144impl IntoLlcLockAttempt for protocol::ProbeOutcome<Vec<protocol::AdmissionFlock>> {
3145    fn into_llc_lock_attempt(self) -> LlcLockAttempt {
3146        match self {
3147            protocol::ProbeOutcome::Acquired(locks) => LlcLockAttempt::Acquired(locks),
3148            protocol::ProbeOutcome::Contended(evidence) => LlcLockAttempt::Contended(evidence),
3149            protocol::ProbeOutcome::Unavailable => {
3150                #[cfg(test)]
3151                {
3152                    LlcLockAttempt::Unavailable
3153                }
3154                #[cfg(not(test))]
3155                unreachable!("physical permit probe cannot return unavailable")
3156            }
3157        }
3158    }
3159}
3160
3161fn try_acquire_llc_plan_locks_with_evidence(
3162    selected: &[usize],
3163    cpus: &[usize],
3164    snapshots: &[LlcSnapshot],
3165) -> Result<LlcLockAttempt> {
3166    debug_assert!(
3167        selected
3168            .iter()
3169            .all(|idx| snapshots.iter().any(|snapshot| snapshot.llc_idx == *idx))
3170    );
3171    let target = protocol::canonical_lock_order_with_modes(
3172        selected,
3173        FlockMode::Shared,
3174        cpus,
3175        FlockMode::Shared,
3176    );
3177    let mut locks: Vec<protocol::AdmissionFlock> = Vec::with_capacity(target.len());
3178    for lock in target {
3179        match try_flock_with_witness(&lock.path, lock.mode)? {
3180            TryFlockOutcome::Acquired(fd) => {
3181                locks.push(protocol::AdmissionFlock::from_acquired(fd));
3182            }
3183            TryFlockOutcome::Contended(witness) => {
3184                // Drop previously-held fds so the peer racing us sees
3185                // a consistent post-bail state, then signal "retry".
3186                drop(locks);
3187                return Ok(LlcLockAttempt::Contended(protocol::ContentionEvidence {
3188                    blocker: lock.resource,
3189                    mode: lock.mode,
3190                    _witness: witness,
3191                }));
3192            }
3193        }
3194    }
3195    Ok(LlcLockAttempt::Acquired(locks))
3196}
3197
3198/// `on_acquired` stays a closure so the Acquired-only payload clones never
3199/// run on a contended probe.
3200fn llc_attempt_into_probe<T>(
3201    attempt: LlcLockAttempt,
3202    on_acquired: impl FnOnce(Vec<protocol::AdmissionFlock>) -> T,
3203) -> protocol::ProbeOutcome<T> {
3204    match attempt {
3205        LlcLockAttempt::Acquired(locks) => protocol::ProbeOutcome::Acquired(on_acquired(locks)),
3206        LlcLockAttempt::Contended(evidence) => protocol::ProbeOutcome::Contended(evidence),
3207        #[cfg(test)]
3208        LlcLockAttempt::Unavailable => protocol::ProbeOutcome::Unavailable,
3209    }
3210}
3211
3212/// Exact LLC-SH/CPU-SH planner used for cooperative VM admission.
3213///
3214/// It acquires topology locks and weighted admission permits in one registry
3215/// claim, and observes cancellation while waiting behind hard-exclusive
3216/// pressure.
3217///
3218/// Runs DISCOVER → PLAN → ACQUIRE with up to
3219/// [`ACQUIRE_MAX_TOCTOU_RETRIES`] retries (each separated by a
3220/// per-retry sleep from [`TOCTOU_RETRY_DELAYS`]) as the acquisition
3221/// protocol's non-blocking FAST PHASE — claim-subtracted and
3222/// all-or-nothing (see [`protocol`]). `wait == false` (non-waiting kernel
3223/// builds, the interactive shell, and other non-blocking probes) bails with
3224/// `ResourceContention` the moment that
3225/// budget is spent. `wait == true` (the test run path) then joins the
3226/// cross-invocation registry and, as coordinator, RE-PLANS AGAINST LIVE HOLDER
3227/// STATE ON EVERY WAKE — plans are never cached across waits — waiting
3228/// for a genuine holder's authoritative flock release rather than
3229/// skipping. On success returns an [`LlcPlan`] holding the selected LLCs,
3230/// their flattened CPUs (intersected with the calling process's allowed
3231/// cpuset), the derived `mems` set, and the RAII flock handles.
3232///
3233/// `cpu_cap == None` means "reserve 30% of the allowed-CPU set" (see
3234/// [`default_cpu_budget`]). `cpu_cap == Some(cap)` where
3235/// `cap > allowed_cpus` errors at acquire time via
3236/// [`CpuCap::effective_count`]. The allowed-CPU set comes from
3237/// [`host_allowed_cpus`] — `sched_getaffinity(0)` with a procfs
3238/// fallback — so plans are always schedulable under cgroup-restricted
3239/// runners (CI hosts, systemd slices, sudo under a limited cpuset).
3240///
3241/// `policy` picks the placement preference among eligible LLCs and CPUs for
3242/// exact reservations. Shared VM reservations use process-rotated
3243/// [`PlacementPolicy::Spread`] (see the enum docs for the clustering failure
3244/// Spread exists to prevent); direct fixed-size kernel builds use
3245/// [`PlacementPolicy::Consolidate`].
3246#[allow(clippy::too_many_arguments)] // Each argument is a distinct admission-policy input.
3247pub(crate) fn acquire_llc_plan_interruptible(
3248    topo: &HostTopology,
3249    test_topo: &crate::topology::TestTopology,
3250    cpu_cap: Option<CpuCap>,
3251    policy: PlacementPolicy,
3252    wait: bool,
3253    cancelled: Option<&AtomicBool>,
3254    pending: Option<protocol::PendingAdmission>,
3255    memory_mib: Option<u32>,
3256) -> Result<LlcPlan> {
3257    acquire_llc_plan_impl(LlcPlanAcquireRequest {
3258        topo,
3259        test_topo,
3260        cpu_cap,
3261        llc_policy: policy,
3262        cpu_policy: CpuSelectionPolicy::WithinEachLlc(policy),
3263        wait,
3264        sizing: LlcPlanSizing::Exact,
3265        permit_admission: PermitAdmission::Cooperative,
3266        cancelled,
3267        pending,
3268        memory_mib,
3269    })
3270}
3271
3272/// Work-conserving waiting acquisition for throughput-elastic builds.
3273///
3274/// The resolved CPU budget is a maximum. Each admission turn first sizes
3275/// itself from CPUs with no current holder, preventing every concurrent Cargo
3276/// process from advertising the full maximum while unused CPU capacity still
3277/// exists. Once every compatible CPU has a holder, SH-compatible capacity is
3278/// the fallback so default, no-perf, and build work may continue to overlap.
3279///
3280/// LLC and CPU placement are deliberately independent. The build consolidates
3281/// its LLC footprint among domains carrying the effective free-first CPU set,
3282/// leaving as many whole LLCs as possible available for hard-exclusive
3283/// performance work, while choosing the least-held CPUs inside that footprint
3284/// with a process-rotated tiebreak.
3285/// Performance reservations remain a hard EX fence. When no compatible CPU is
3286/// currently available, the caller queues behind a one-CPU exact designation
3287/// and replans against the full immutable watch on every wake.
3288pub(crate) fn acquire_elastic_build_llc_plan(
3289    topo: &HostTopology,
3290    test_topo: &crate::topology::TestTopology,
3291    cpu_cap: Option<CpuCap>,
3292    cancelled: Option<&AtomicBool>,
3293) -> Result<LlcPlan> {
3294    acquire_llc_plan_impl(LlcPlanAcquireRequest {
3295        topo,
3296        test_topo,
3297        cpu_cap,
3298        llc_policy: PlacementPolicy::Consolidate,
3299        cpu_policy: CpuSelectionPolicy::least_held_for_process(),
3300        wait: true,
3301        sizing: LlcPlanSizing::Elastic,
3302        permit_admission: PermitAdmission::Build,
3303        cancelled,
3304        pending: None,
3305        memory_mib: None,
3306    })
3307}
3308
3309pub(crate) fn acquire_build_llc_plan(
3310    topo: &HostTopology,
3311    test_topo: &crate::topology::TestTopology,
3312    cpu_cap: Option<CpuCap>,
3313    wait: bool,
3314    cancelled: Option<&AtomicBool>,
3315) -> Result<LlcPlan> {
3316    acquire_llc_plan_impl(LlcPlanAcquireRequest {
3317        topo,
3318        test_topo,
3319        cpu_cap,
3320        llc_policy: PlacementPolicy::Consolidate,
3321        cpu_policy: CpuSelectionPolicy::WithinEachLlc(PlacementPolicy::Consolidate),
3322        wait,
3323        sizing: LlcPlanSizing::Exact,
3324        permit_admission: PermitAdmission::Build,
3325        cancelled,
3326        pending: None,
3327        memory_mib: None,
3328    })
3329}
3330
3331/// Cooperative work may oversubscribe each possible host CPU by this factor.
3332/// A full-width VM therefore consumes one of four host-width lanes, while the
3333/// physical CPU/LLC SH locks continue to describe the topology it may share.
3334const COOPERATIVE_OVERSUBSCRIPTION: usize = 4;
3335const BUILD_RESERVED_PERCENT: usize = 30;
3336const MEMORY_PERMIT_CHUNK_MIB: usize = 256;
3337const HOST_MEMORY_RESERVE_MIB: usize = 4 * 1024;
3338const HOST_MEMORY_RESERVE_PERCENT: usize = 10;
3339/// Conservative private/COW working set charged to a process while it builds
3340/// and maps immutable inputs, before guest memory exists.
3341///
3342/// File-backed test text, the content-addressed initramfs suffix, and KVM's
3343/// eventual guest mapping are shared/COW and therefore do not each require a
3344/// private copy of their apparent RSS. Two permit chunks leave one chunk for
3345/// the ordinary 256 MiB process footprint and one for transient dirtied pages
3346/// without mistaking a future guest's (possibly much larger) allocation for
3347/// preparation memory. Run admission replaces this fixed charge with the
3348/// computed guest-memory demand before KVM allocates that guest memory.
3349const PREPARATION_PRIVATE_WORKING_SET_MIB: usize = 2 * MEMORY_PERMIT_CHUNK_MIB;
3350
3351#[derive(Clone, Copy, Debug, PartialEq, Eq)]
3352enum PermitAdmission {
3353    None,
3354    Cooperative,
3355    Build,
3356}
3357
3358struct AdmissionPermitPool {
3359    general: Vec<usize>,
3360    reserved: Vec<usize>,
3361}
3362
3363impl AdmissionPermitPool {
3364    /// `cpu_count` is the host's possible CPU width, never the caller's
3365    /// cpuset: permit identities are lockfiles in one host-wide namespace, so
3366    /// every participant sharing a lock directory has to derive the same
3367    /// indices and the same general/reserved boundary. A cpuset-derived width
3368    /// would also truncate the pool below the identities a preparation permit
3369    /// (always possible-width) already holds, dropping the inherited OFD from
3370    /// the run selection that is meant to reuse it.
3371    fn for_host(cpu_count: usize) -> Self {
3372        let total_count = cpu_count.saturating_mul(COOPERATIVE_OVERSUBSCRIPTION);
3373        let reserved_count = total_count
3374            .saturating_mul(BUILD_RESERVED_PERCENT)
3375            .div_ceil(100)
3376            .min(total_count.saturating_sub(1));
3377        let general_count = total_count - reserved_count;
3378        Self {
3379            general: (0..general_count).collect(),
3380            reserved: (general_count..total_count).collect(),
3381        }
3382    }
3383
3384    fn all(&self) -> impl Iterator<Item = usize> + '_ {
3385        self.general.iter().chain(&self.reserved).copied()
3386    }
3387
3388    fn len(&self) -> usize {
3389        self.general.len() + self.reserved.len()
3390    }
3391
3392    /// Performance already owns a disjoint physical placement and must not
3393    /// borrow the cooperative suffix retained for build/default progress.
3394    fn for_performance_host(cpu_count: usize) -> Self {
3395        let ordinary = Self::for_host(cpu_count);
3396        Self {
3397            general: ordinary.general,
3398            reserved: Vec::new(),
3399        }
3400    }
3401
3402    /// Build concurrency is bounded independently from cooperative VM CPU
3403    /// accounting. Default VMs may occupy the cooperative reserved suffix, but
3404    /// that ownership is deliberately soft: a build never waits for those
3405    /// borrower OFDs and is constrained only by this build-only namespace plus
3406    /// the ordinary physical LLC/CPU SH locks. Performance CPU/LLC EX remains
3407    /// the hard fence.
3408    fn for_build_host(cpu_count: usize) -> Result<Self> {
3409        Ok(Self {
3410            general: build_permit_range(cpu_count)?.collect(),
3411            reserved: Vec::new(),
3412        })
3413    }
3414}
3415
3416struct MemoryPermitPool {
3417    permits: Vec<usize>,
3418    usable_mib: usize,
3419}
3420
3421fn possible_cpu_width() -> usize {
3422    std::fs::read_to_string("/sys/devices/system/cpu/possible")
3423        .ok()
3424        .map(|raw| parse_cpu_list_lenient(&raw))
3425        .and_then(|cpus| cpus.into_iter().max())
3426        .unwrap_or(63)
3427        .saturating_add(1)
3428}
3429
3430fn memory_permit_base_for_possible_width(possible_width: usize) -> usize {
3431    possible_width.saturating_mul(COOPERATIVE_OVERSUBSCRIPTION)
3432}
3433
3434/// Exclusive permit identities below this bound account cooperative VM CPU
3435/// pressure. Later permit namespaces account memory, preparation tokens, and
3436/// builds independently. The queue publishes each record's cooperative watch
3437/// cardinality against the same boundary.
3438pub(super) fn cooperative_cpu_permit_end() -> usize {
3439    memory_permit_base_for_possible_width(possible_cpu_width())
3440}
3441
3442fn host_mem_total_mib() -> Result<usize> {
3443    let meminfo = std::fs::read_to_string("/proc/meminfo").context("read /proc/meminfo")?;
3444    let kib = meminfo
3445        .lines()
3446        .find_map(|line| {
3447            let value = line.strip_prefix("MemTotal:")?.trim();
3448            value.split_whitespace().next()?.parse::<usize>().ok()
3449        })
3450        .ok_or_else(|| anyhow::anyhow!("/proc/meminfo does not contain a valid MemTotal"))?;
3451    Ok(kib / 1024)
3452}
3453
3454fn memory_capacity_from_total(total_mib: usize) -> (usize, usize) {
3455    let percentage = total_mib
3456        .saturating_mul(HOST_MEMORY_RESERVE_PERCENT)
3457        .div_ceil(100);
3458    let reserve = HOST_MEMORY_RESERVE_MIB.max(percentage).min(total_mib);
3459    let usable_mib = total_mib.saturating_sub(reserve);
3460    (usable_mib, usable_mib / MEMORY_PERMIT_CHUNK_MIB)
3461}
3462
3463impl MemoryPermitPool {
3464    fn for_host() -> Result<Self> {
3465        let total_mib = host_mem_total_mib()?;
3466        let (usable_mib, chunks) = memory_capacity_from_total(total_mib);
3467        let base = memory_permit_base_for_possible_width(possible_cpu_width());
3468        let end = base
3469            .checked_add(chunks)
3470            .ok_or_else(|| anyhow::anyhow!("memory permit namespace overflow"))?;
3471        Ok(Self {
3472            permits: (base..end).collect(),
3473            usable_mib,
3474        })
3475    }
3476
3477    /// Number of `MEMORY_PERMIT_CHUNK_MIB` permits a cell must hold for
3478    /// `memory_mib` MiB of admission-charged memory.
3479    ///
3480    /// The permit reserves what a *trusted deferred* workload makes
3481    /// resident — its touch ceiling — NOT the guest's sized RAM. Callers
3482    /// pass `max(touch_ceiling, declared_memory)` (see
3483    /// `vmm::setup`'s `permit_memory_mib` /
3484    /// `vmm::memory_budget::touch_ceiling_mib`), so a wide cell whose sized
3485    /// RAM is the `64 MiB/vCPU` floor charges only the fraction it actually
3486    /// faults in. This is sound because default/no-perf guest RAM is
3487    /// `MAP_NORESERVE` demand-paged (`super::numa_mem`'s
3488    /// `anonymous_node_map_flags`): untouched pages cost no host memory, so
3489    /// the gap between the resident set and the advertised size is free to
3490    /// oversubscribe. A test that touches more than its ceiling must declare
3491    /// the memory (`.memory_mib(...)`, which raises the charge); the only
3492    /// host-OOM exposure is an undeclared over-allocating test. Performance
3493    /// mode is charged its full sized RAM (prefaulted / physically-reserved
3494    /// hugetlb pool), so this oversubscription applies only to the
3495    /// demand-paged path.
3496    fn required_chunks(&self, memory_mib: u32) -> Result<usize> {
3497        let requested = usize::try_from(memory_mib).context("guest memory does not fit usize")?;
3498        let chunks = requested.div_ceil(MEMORY_PERMIT_CHUNK_MIB);
3499        anyhow::ensure!(
3500            chunks <= self.permits.len(),
3501            "guest requests {requested}MiB, exceeding the host admission capacity of {}MiB \
3502             after reserving max({HOST_MEMORY_RESERVE_MIB}MiB, \
3503             {HOST_MEMORY_RESERVE_PERCENT}% of MemTotal) for the host",
3504            self.usable_mib,
3505        );
3506        Ok(chunks)
3507    }
3508}
3509
3510/// Capacity held while a test process prepares immutable artifacts. Active
3511/// preparation is expressed in the same abstract CPU and memory namespaces as
3512/// a running VM. The physical preparation resources stay claimed and held,
3513/// while the selected final intent remains attached to the same ticket's watch
3514/// until exact admission atomically replaces both with computed guest demand.
3515pub(super) struct PreparationPermit {
3516    pub(super) index: usize,
3517    pub(super) token_permit: usize,
3518    pub(super) cpu_permits: Vec<usize>,
3519    pub(super) memory_permits: Vec<usize>,
3520    pub(super) permit_fds: Vec<(usize, protocol::AdmissionFlock)>,
3521    /// One real CPU-SH owner matching `affinity_cpu`. The PENDING claim
3522    /// publishes the same CPU, so a performance reservation cannot enter
3523    /// between placement and `sched_setaffinity`.
3524    affinity_lock: Option<protocol::AdmissionFlock>,
3525    affinity_cpu: usize,
3526    original_affinity: Vec<usize>,
3527    affinity_constrained: bool,
3528}
3529
3530impl PreparationPermit {
3531    fn all_permits(&self) -> Vec<usize> {
3532        let mut permits =
3533            Vec::with_capacity(1 + self.cpu_permits.len() + self.memory_permits.len());
3534        permits.push(self.token_permit);
3535        permits.extend_from_slice(&self.cpu_permits);
3536        permits.extend_from_slice(&self.memory_permits);
3537        permits.sort_unstable();
3538        permits
3539    }
3540
3541    pub(super) fn claim(&self) -> protocol::ClaimSet {
3542        let cpu = AdmissionPermitPool::for_host(possible_cpu_width());
3543        let admission_class = if self
3544            .cpu_permits
3545            .iter()
3546            .any(|permit| cpu.reserved.contains(permit))
3547        {
3548            protocol::AdmissionClass::DefaultBorrow
3549        } else {
3550            protocol::AdmissionClass::Ordinary
3551        };
3552        let claimed_cpu = self
3553            .affinity_lock
3554            .as_ref()
3555            .map(|_| std::slice::from_ref(&self.affinity_cpu))
3556            .unwrap_or_default();
3557        resource_claim_with_permits(
3558            &[],
3559            LlcLockMode::Shared,
3560            claimed_cpu,
3561            FlockMode::Shared,
3562            &self.all_permits(),
3563            admission_class,
3564        )
3565    }
3566
3567    pub(super) fn clone_permit_fds(&self) -> Result<Vec<(usize, protocol::AdmissionFlock)>> {
3568        anyhow::ensure!(
3569            self.all_permits().len() == self.permit_fds.len(),
3570            "preparation permit {} has inconsistent resource/fd counts",
3571            self.index,
3572        );
3573        self.permit_fds
3574            .iter()
3575            .map(|(permit, fd)| Ok((*permit, fd.try_clone()?)))
3576            .collect()
3577    }
3578
3579    /// The thread mask is deliberately NOT required to be constrained
3580    /// here: `prepare_pending_exec_handoff` restores the original mask
3581    /// before exec (the pin must not leak into the child's pre-import
3582    /// budget resolution), and the import side re-pins for the child's
3583    /// own preparation phase. Only the physical CPU lock must still be
3584    /// held — it is what crosses exec.
3585    pub(super) fn affinity_handoff_parts(&self) -> Result<(usize, std::os::fd::RawFd, &[usize])> {
3586        use std::os::fd::AsRawFd;
3587        let fd = self
3588            .affinity_lock
3589            .as_ref()
3590            .ok_or_else(|| anyhow::anyhow!("preparation physical CPU lock was already released"))?;
3591        Ok((self.affinity_cpu, fd.as_raw_fd(), &self.original_affinity))
3592    }
3593
3594    pub(super) fn constrain_affinity(&mut self) -> Result<()> {
3595        anyhow::ensure!(
3596            self.affinity_lock.is_some(),
3597            "preparation physical CPU lock was already released",
3598        );
3599        if self.affinity_constrained {
3600            return Ok(());
3601        }
3602        // Mark the transition active before the multi-thread walk. If a later
3603        // thread rejects the mask after earlier threads accepted it, Drop must
3604        // still restore the original mask rather than leaving a partially
3605        // pinned process behind.
3606        self.affinity_constrained = true;
3607        if let Err(error) = set_process_thread_affinity(&[self.affinity_cpu]) {
3608            let restore = self.restore_affinity();
3609            return match restore {
3610                Ok(()) => Err(error).with_context(|| {
3611                    format!(
3612                        "pin preparation work to admitted host CPU {}",
3613                        self.affinity_cpu
3614                    )
3615                }),
3616                Err(restore) => Err(error).with_context(|| {
3617                    format!(
3618                        "pin preparation work to admitted host CPU {}; restoring the original \
3619                         mask also failed: {restore:#}",
3620                        self.affinity_cpu
3621                    )
3622                }),
3623            };
3624        }
3625        Ok(())
3626    }
3627
3628    pub(super) fn restore_affinity(&mut self) -> Result<()> {
3629        if !self.affinity_constrained {
3630            return Ok(());
3631        }
3632        set_process_thread_affinity(&self.original_affinity)
3633            .context("restore affinity before exact VM admission")?;
3634        self.affinity_constrained = false;
3635        Ok(())
3636    }
3637
3638    /// The exact registry claim has atomically replaced PENDING, so its
3639    /// predecessor fence now protects this process while it probes the exact
3640    /// physical target. Drop the preparation CPU-SH and weighted CPU/memory
3641    /// flocks here; retaining any of them makes the exact claim observe its
3642    /// own preparation owner as unavailable. The preparation token stays held
3643    /// until exact HELD publication, bounding the number of resident prepared
3644    /// processes without overlapping the exact claim's resource footprint.
3645    pub(super) fn release_resources_for_exact(&mut self) -> Result<()> {
3646        anyhow::ensure!(
3647            !self.affinity_constrained,
3648            "preparation affinity must be restored before exact activation",
3649        );
3650        drop(self.affinity_lock.take());
3651        let token = self
3652            .permit_fds
3653            .iter()
3654            .position(|(permit, _)| *permit == self.token_permit)
3655            .ok_or_else(|| {
3656                anyhow::anyhow!(
3657                    "preparation permit {} lost token permit {}",
3658                    self.index,
3659                    self.token_permit,
3660                )
3661            })?;
3662        let (_, token_fd) = self.permit_fds.swap_remove(token);
3663        self.permit_fds.clear();
3664        self.permit_fds.push((self.token_permit, token_fd));
3665        self.cpu_permits.clear();
3666        self.memory_permits.clear();
3667        Ok(())
3668    }
3669
3670    #[allow(clippy::too_many_arguments)] // Mirrors the fixed exec-handoff descriptor fields.
3671    pub(super) fn imported(
3672        index: usize,
3673        token_permit: usize,
3674        cpu_permits: Vec<usize>,
3675        memory_permits: Vec<usize>,
3676        permit_fds: Vec<(usize, protocol::AdmissionFlock)>,
3677        affinity_cpu: usize,
3678        affinity_lock: protocol::AdmissionFlock,
3679        original_affinity: Vec<usize>,
3680    ) -> Self {
3681        Self {
3682            index,
3683            token_permit,
3684            cpu_permits,
3685            memory_permits,
3686            permit_fds,
3687            affinity_lock: Some(affinity_lock),
3688            affinity_cpu,
3689            original_affinity,
3690            // The parent restored the original mask before exec, so the
3691            // imported permit arrives UNCONSTRAINED;
3692            // `PendingAdmission::from_imported_ticket` re-pins via
3693            // `constrain_affinity` for this process's preparation phase.
3694            affinity_constrained: false,
3695        }
3696    }
3697}
3698
3699impl Drop for PreparationPermit {
3700    fn drop(&mut self) {
3701        if let Err(error) = self.restore_affinity() {
3702            tracing::warn!(
3703                error = %error,
3704                preparation_cpu = self.affinity_cpu,
3705                "failed to restore process affinity while releasing preparation admission"
3706            );
3707        }
3708    }
3709}
3710
3711/// Apply one affinity mask to every thread currently in this process. The
3712/// calling thread is changed first, so newly-created children inherit the new
3713/// mask; the bounded rescan closes the race with threads spawned by an older
3714/// already-running worker while the first `/proc/self/task` walk is in flight.
3715fn set_process_thread_affinity(cpus: &[usize]) -> Result<()> {
3716    anyhow::ensure!(!cpus.is_empty(), "cannot install an empty affinity mask");
3717    let max_cpu = cpus.iter().copied().max().unwrap_or(0);
3718    let word_bits = libc::c_ulong::BITS as usize;
3719    let words = max_cpu
3720        .checked_div(word_bits)
3721        .and_then(|word| word.checked_add(1))
3722        .ok_or_else(|| anyhow::anyhow!("affinity mask size overflow"))?;
3723    let mut mask = vec![0 as libc::c_ulong; words];
3724    for &cpu in cpus {
3725        mask[cpu / word_bits] |= (1 as libc::c_ulong) << (cpu % word_bits);
3726    }
3727    let bytes = std::mem::size_of_val(mask.as_slice());
3728    let apply = |tid: libc::pid_t| -> Result<()> {
3729        // SAFETY: `mask` is live for `bytes` and the syscall only reads it.
3730        let result =
3731            unsafe { libc::syscall(libc::SYS_sched_setaffinity, tid, bytes, mask.as_ptr()) };
3732        if result == -1 {
3733            let error = std::io::Error::last_os_error();
3734            if error.raw_os_error() == Some(libc::ESRCH) {
3735                return Ok(());
3736            }
3737            return Err(error).with_context(|| format!("sched_setaffinity tid={tid}"));
3738        }
3739        Ok(())
3740    };
3741
3742    // `0` is the calling thread and establishes inheritance before walking
3743    // the rest of the process.
3744    apply(0)?;
3745    let mut previous = std::collections::BTreeSet::new();
3746    for _ in 0..8 {
3747        let tids = std::fs::read_dir("/proc/self/task")
3748            .context("enumerate process threads for affinity transition")?
3749            .filter_map(|entry| {
3750                entry
3751                    .ok()?
3752                    .file_name()
3753                    .to_str()?
3754                    .parse::<libc::pid_t>()
3755                    .ok()
3756            })
3757            .collect::<std::collections::BTreeSet<_>>();
3758        for &tid in &tids {
3759            apply(tid)?;
3760        }
3761        if tids == previous {
3762            return Ok(());
3763        }
3764        previous = tids;
3765    }
3766    anyhow::bail!("process thread set did not stabilize during affinity transition")
3767}
3768
3769const PREPARATION_MEMORY_FRACTION: usize = 4;
3770const PREPARATION_CPU_PERMITS: usize = COOPERATIVE_OVERSUBSCRIPTION;
3771
3772fn preparation_memory_chunks() -> usize {
3773    PREPARATION_PRIVATE_WORKING_SET_MIB.div_ceil(MEMORY_PERMIT_CHUNK_MIB)
3774}
3775
3776fn preparation_slot_capacity(
3777    memory_permit_count: usize,
3778    cpu_permit_count: usize,
3779    possible_width: usize,
3780) -> usize {
3781    let memory_per_slot = preparation_memory_chunks();
3782    if memory_per_slot == 0 {
3783        return 0;
3784    }
3785
3786    // Preparation can consume at most one quarter of the common memory
3787    // namespace. The uncharged three quarters remain available while every
3788    // preparation token is occupied, so a prepared process can replace its
3789    // fixed private/COW charge with its actual computed guest demand rather
3790    // than deadlocking behind a second complete preparation wave.
3791    let preparation_memory_budget = memory_permit_count / PREPARATION_MEMORY_FRACTION;
3792    let memory_slots = preparation_memory_budget / memory_per_slot;
3793    let cpu_slots = cpu_permit_count / PREPARATION_CPU_PERMITS;
3794    memory_slots
3795        .min(cpu_slots)
3796        .min(possible_width.saturating_mul(2))
3797}
3798
3799fn preparation_token_range() -> Result<std::ops::Range<usize>> {
3800    // Host topology is fixed for the process lifetime, and this range is
3801    // consulted on hot paths — every physical preparation sweep, every grant
3802    // scan a coordinator drives, and every claim-metadata write. Compute it
3803    // once so those callers pay a cached load, not repeated /proc and /sys
3804    // reads (which also keeps the coordinator's latency footprint small on the
3805    // timing-sensitive cross-process wake paths).
3806    static RANGE: std::sync::OnceLock<std::ops::Range<usize>> = std::sync::OnceLock::new();
3807    if let Some(range) = RANGE.get() {
3808        return Ok(range.clone());
3809    }
3810    let range = preparation_token_range_uncached()?;
3811    let _ = RANGE.set(range.clone());
3812    Ok(range)
3813}
3814
3815fn preparation_token_range_uncached() -> Result<std::ops::Range<usize>> {
3816    let possible_width = possible_cpu_width();
3817    let cpu = AdmissionPermitPool::for_host(possible_width);
3818    let memory = MemoryPermitPool::for_host()?;
3819    let memory_per_slot = preparation_memory_chunks();
3820    anyhow::ensure!(
3821        memory_per_slot > 0,
3822        "preparation memory weight resolved to zero"
3823    );
3824
3825    let slots = preparation_slot_capacity(memory.permits.len(), cpu.len(), possible_width);
3826    anyhow::ensure!(
3827        slots > 0,
3828        "host admission capacity cannot fund one \
3829         {PREPARATION_PRIVATE_WORKING_SET_MIB}MiB preparation slot"
3830    );
3831
3832    let base = memory.permits.last().copied().map_or_else(
3833        || memory_permit_base_for_possible_width(possible_width),
3834        |last| last.saturating_add(1),
3835    );
3836    let end = base
3837        .checked_add(slots)
3838        .ok_or_else(|| anyhow::anyhow!("preparation token namespace overflow"))?;
3839    Ok(base..end)
3840}
3841
3842/// The first permit index of the preparation-token sub-range. Used by the hot
3843/// metadata path (`ScanMetadata::for_claims`, which asks whether a watch covers
3844/// the token pool once per claim write); the underlying range is memoized.
3845pub(super) fn preparation_token_pool_start() -> Result<usize> {
3846    Ok(preparation_token_range()?.start)
3847}
3848
3849fn build_permit_range(cpu_count: usize) -> Result<std::ops::Range<usize>> {
3850    let preparation = preparation_token_range()?;
3851    let cooperative_capacity = cpu_count.saturating_mul(COOPERATIVE_OVERSUBSCRIPTION);
3852    let build_capacity = cooperative_capacity
3853        .saturating_mul(BUILD_RESERVED_PERCENT)
3854        .div_ceil(100)
3855        .max(1);
3856    let base = preparation.end;
3857    let end = base
3858        .checked_add(build_capacity)
3859        .ok_or_else(|| anyhow::anyhow!("build permit namespace overflow"))?;
3860    Ok(base..end)
3861}
3862
3863/// One past the highest permit index any same-host participant can claim.
3864/// Cooperative CPU permits, memory permits, preparation tokens, and build
3865/// permits stack in that order, so the build range's end bounds them all.
3866/// The registry derives its creation width from this so the first creator —
3867/// whatever it claims itself — sizes the file for every later claim.
3868pub(super) fn permit_namespace_end() -> Result<usize> {
3869    build_permit_range(possible_cpu_width()).map(|range| range.end)
3870}
3871
3872/// Choose and physically hold the CPU on which immutable preparation runs.
3873/// CPU-EX claims/holders are excluded. Among the remaining SH-compatible
3874/// CPUs, prefer the complement of live Build-class claims, then the lowest
3875/// holder count, with a process/permit-derived rotation as the final tie
3876/// breaker. If builds cover the complete allowed set the first key is equal
3877/// and preparation cooperatively overlaps the least-held CPU instead of
3878/// stalling an otherwise runnable host.
3879enum PreparationAffinityAttempt {
3880    Acquired(usize, protocol::AdmissionFlock),
3881    Contended(Option<protocol::ContentionEvidence>),
3882}
3883
3884fn try_acquire_preparation_affinity_cpu(
3885    allowed: &[usize],
3886    rotation: usize,
3887    wait_for_registry: bool,
3888) -> Result<PreparationAffinityAttempt> {
3889    anyhow::ensure!(!allowed.is_empty(), "preparation has no allowed host CPU");
3890    let required = protocol::ClaimSet::with_modes(
3891        std::iter::empty(),
3892        allowed.iter().copied(),
3893        FlockMode::Shared,
3894        FlockMode::Shared,
3895    );
3896    let snapshot = if wait_for_registry {
3897        protocol::registered_claim_snapshot(&required)?
3898    } else {
3899        let Some(snapshot) = protocol::try_registered_claim_snapshot(&required)? else {
3900            return Ok(PreparationAffinityAttempt::Contended(None));
3901        };
3902        snapshot
3903    };
3904    let start = rotation % allowed.len();
3905    let mut candidates = Vec::with_capacity(allowed.len());
3906    for (rank, &cpu) in allowed
3907        .iter()
3908        .cycle()
3909        .skip(start)
3910        .take(allowed.len())
3911        .enumerate()
3912    {
3913        let shared = protocol::ClaimSet::with_modes(
3914            std::iter::empty(),
3915            [cpu],
3916            FlockMode::Shared,
3917            FlockMode::Shared,
3918        );
3919        candidates.push((
3920            snapshot.conflicts(&shared)? || snapshot.cpu_exclusive_held(cpu)?,
3921            snapshot.cpu_build_claimed(cpu)?,
3922            snapshot.cpu_holder_count(cpu)?,
3923            rank,
3924            cpu,
3925        ));
3926    }
3927    candidates.sort_unstable();
3928    let mut first_contended = None;
3929    for (registry_blocked, _, _, _, cpu) in candidates {
3930        if registry_blocked {
3931            continue;
3932        }
3933        match try_flock_with_witness(cpu_lock_path(cpu), FlockMode::Shared)? {
3934            TryFlockOutcome::Acquired(fd) => {
3935                return Ok(PreparationAffinityAttempt::Acquired(
3936                    cpu,
3937                    protocol::AdmissionFlock::from_acquired(fd),
3938                ));
3939            }
3940            TryFlockOutcome::Contended(witness) => {
3941                first_contended.get_or_insert(protocol::ContentionEvidence {
3942                    blocker: protocol::ResourceKey::Cpu(cpu),
3943                    mode: FlockMode::Shared,
3944                    _witness: witness,
3945                });
3946            }
3947        }
3948    }
3949    Ok(PreparationAffinityAttempt::Contended(first_contended))
3950}
3951
3952/// A queue grant already proved that the selected final CPU claim has no
3953/// conflicting predecessor. Ignore the aggregate here (which includes the
3954/// caller's own published CPU-EX intent) and use the physical CPU-SH flock as
3955/// authority for an active holder or unrelated lock user.
3956fn try_acquire_selected_preparation_affinity_cpu(
3957    candidates: &[usize],
3958    rotation: usize,
3959) -> Result<PreparationAffinityAttempt> {
3960    anyhow::ensure!(
3961        !candidates.is_empty(),
3962        "preparation has no selected host CPU"
3963    );
3964    let start = rotation % candidates.len();
3965    let mut first = None;
3966    for &cpu in candidates.iter().cycle().skip(start).take(candidates.len()) {
3967        match try_flock_with_witness(cpu_lock_path(cpu), FlockMode::Shared)? {
3968            TryFlockOutcome::Acquired(fd) => {
3969                return Ok(PreparationAffinityAttempt::Acquired(
3970                    cpu,
3971                    protocol::AdmissionFlock::from_acquired(fd),
3972                ));
3973            }
3974            TryFlockOutcome::Contended(witness) => {
3975                first.get_or_insert(protocol::ContentionEvidence {
3976                    blocker: protocol::ResourceKey::Cpu(cpu),
3977                    mode: FlockMode::Shared,
3978                    _witness: witness,
3979                });
3980            }
3981        }
3982    }
3983    Ok(PreparationAffinityAttempt::Contended(Some(
3984        first.expect("non-empty selected CPU set was fully probed"),
3985    )))
3986}
3987
3988enum PreparationPermitAttempt {
3989    Acquired(PreparationPermit, protocol::ClaimSet),
3990    TokenContended(protocol::ContentionEvidence),
3991    ResourceContended(Option<protocol::ContentionEvidence>),
3992}
3993
3994#[cfg(test)]
3995thread_local! {
3996    static PREPARATION_RESOURCE_PROBES: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
3997}
3998
3999#[cfg(test)]
4000fn reset_preparation_resource_probe_count_for_tests() {
4001    PREPARATION_RESOURCE_PROBES.with(|count| count.set(0));
4002}
4003
4004#[cfg(test)]
4005fn preparation_resource_probe_count_for_tests() -> usize {
4006    PREPARATION_RESOURCE_PROBES.with(std::cell::Cell::get)
4007}
4008
4009fn try_acquire_preparation_permit_at(
4010    index: usize,
4011    token_permit: usize,
4012    rotation: usize,
4013    wait_for_registry: bool,
4014    affinity_candidates: Option<&[usize]>,
4015) -> Result<PreparationPermitAttempt> {
4016    let cpu = AdmissionPermitPool::for_host(possible_cpu_width());
4017    let memory = MemoryPermitPool::for_host()?;
4018    let memory_required = preparation_memory_chunks();
4019    let mut permit_fds = Vec::with_capacity(1 + PREPARATION_CPU_PERMITS + memory_required);
4020
4021    let acquire_one = |permit| -> Result<
4022        std::result::Result<protocol::AdmissionFlock, protocol::ContentionEvidence>,
4023    > {
4024        match try_flock_with_witness(permit_lock_path(permit), FlockMode::Exclusive)? {
4025            TryFlockOutcome::Acquired(fd) => Ok(Ok(protocol::AdmissionFlock::from_acquired(fd))),
4026            TryFlockOutcome::Contended(witness) => Ok(Err(protocol::ContentionEvidence {
4027                blocker: protocol::ResourceKey::Permit(permit),
4028                mode: FlockMode::Exclusive,
4029                _witness: witness,
4030            })),
4031        }
4032    };
4033    let token_fd = match acquire_one(token_permit)? {
4034        Ok(fd) => fd,
4035        Err(evidence) => {
4036            return Ok(PreparationPermitAttempt::TokenContended(evidence));
4037        }
4038    };
4039    permit_fds.push((token_permit, token_fd));
4040    #[cfg(test)]
4041    PREPARATION_RESOURCE_PROBES.with(|count| count.set(count.get().saturating_add(1)));
4042
4043    let ordered_cpu = cpu.all().collect::<Vec<_>>();
4044    let cpu_start = rotation % ordered_cpu.len();
4045    let mut first_cpu_contention = None;
4046    for offset in 0..ordered_cpu.len() {
4047        let permit = ordered_cpu[(cpu_start + offset) % ordered_cpu.len()];
4048        match acquire_one(permit)? {
4049            Ok(fd) => {
4050                permit_fds.push((permit, fd));
4051                if permit_fds.len() == 1 + PREPARATION_CPU_PERMITS {
4052                    break;
4053                }
4054            }
4055            Err(evidence) => {
4056                first_cpu_contention.get_or_insert(evidence);
4057            }
4058        }
4059    }
4060    if permit_fds.len() != 1 + PREPARATION_CPU_PERMITS {
4061        let evidence =
4062            first_cpu_contention.expect("incomplete CPU preparation weight observed contention");
4063        return Ok(PreparationPermitAttempt::ResourceContended(Some(evidence)));
4064    }
4065    let cpu_permits = permit_fds[1..]
4066        .iter()
4067        .map(|(permit, _)| *permit)
4068        .collect::<Vec<_>>();
4069
4070    let memory_start = rotation % memory.permits.len();
4071    let mut first_memory_contention = None;
4072    for offset in 0..memory.permits.len() {
4073        let permit = memory.permits[(memory_start + offset) % memory.permits.len()];
4074        match acquire_one(permit)? {
4075            Ok(fd) => {
4076                permit_fds.push((permit, fd));
4077                if permit_fds.len() == 1 + PREPARATION_CPU_PERMITS + memory_required {
4078                    break;
4079                }
4080            }
4081            Err(evidence) => {
4082                first_memory_contention.get_or_insert(evidence);
4083            }
4084        }
4085    }
4086    if permit_fds.len() != 1 + PREPARATION_CPU_PERMITS + memory_required {
4087        let evidence = first_memory_contention
4088            .expect("incomplete memory preparation weight observed contention");
4089        return Ok(PreparationPermitAttempt::ResourceContended(Some(evidence)));
4090    }
4091    let memory_permits = permit_fds[1 + PREPARATION_CPU_PERMITS..]
4092        .iter()
4093        .map(|(permit, _)| *permit)
4094        .collect::<Vec<_>>();
4095    let original_affinity = host_allowed_cpus();
4096    anyhow::ensure!(
4097        !original_affinity.is_empty(),
4098        "could not determine allowed CPU set for preparation admission",
4099    );
4100    let selected_affinity = affinity_candidates.is_some();
4101    let affinity_candidates = affinity_candidates.unwrap_or(&original_affinity);
4102    anyhow::ensure!(
4103        !affinity_candidates.is_empty()
4104            && affinity_candidates
4105                .iter()
4106                .all(|cpu| original_affinity.binary_search(cpu).is_ok()),
4107        "preparation affinity candidates are empty or outside the process cpuset",
4108    );
4109    let affinity_rotation = cpu_permits
4110        .iter()
4111        .fold(rotation, |seed, permit| seed.rotate_left(7) ^ permit);
4112    let affinity_attempt = if selected_affinity {
4113        try_acquire_selected_preparation_affinity_cpu(affinity_candidates, affinity_rotation)?
4114    } else {
4115        try_acquire_preparation_affinity_cpu(
4116            affinity_candidates,
4117            affinity_rotation,
4118            wait_for_registry,
4119        )?
4120    };
4121    let (affinity_cpu, affinity_lock) = match affinity_attempt {
4122        PreparationAffinityAttempt::Acquired(cpu, fd) => (cpu, fd),
4123        PreparationAffinityAttempt::Contended(evidence) => {
4124            return Ok(PreparationPermitAttempt::ResourceContended(evidence));
4125        }
4126    };
4127    permit_fds.sort_by_key(|(permit, _)| *permit);
4128    let preparation = PreparationPermit {
4129        index,
4130        token_permit,
4131        cpu_permits,
4132        memory_permits,
4133        permit_fds,
4134        affinity_lock: Some(affinity_lock),
4135        affinity_cpu,
4136        original_affinity,
4137        affinity_constrained: false,
4138    };
4139    let claim = preparation.claim();
4140    Ok(PreparationPermitAttempt::Acquired(preparation, claim))
4141}
4142
4143pub(super) enum PreparationCandidateDecision<T> {
4144    Accepted(T),
4145    Retry,
4146    /// This complete physical tuple is fenced by a live registry claim.
4147    /// Keep scanning immediately available tuples before sleeping; if none
4148    /// succeeds, the first sampled wake epoch closes every improvement race
4149    /// which occurred during the sweep.
4150    RegistryContended(u32),
4151    Contended,
4152}
4153
4154pub(super) enum PreparationProbe<T> {
4155    Acquired(T),
4156    Contended(protocol::ContentionEvidence),
4157    RegistryContended(u32),
4158    Unavailable,
4159}
4160
4161#[cfg(test)]
4162thread_local! {
4163    static PREPARATION_CONTENTION_WAIT_HOOK: std::cell::RefCell<Option<Box<dyn FnOnce()>>> =
4164        const { std::cell::RefCell::new(None) };
4165}
4166
4167#[cfg(test)]
4168fn set_preparation_contention_wait_hook_for_tests(hook: impl FnOnce() + 'static) {
4169    PREPARATION_CONTENTION_WAIT_HOOK.with(|slot| {
4170        assert!(
4171            slot.replace(Some(Box::new(hook))).is_none(),
4172            "preparation contention wait hook was already installed",
4173        );
4174    });
4175}
4176
4177/// Visit each immediately available preparation tuple once without sleeping.
4178/// A registry claim conflict may reject one tuple and continue at the next
4179/// token; registry-lock or global physical contention terminates the sweep.
4180pub(super) fn try_preparation_candidates_once<T>(
4181    rotation_bias: usize,
4182    affinity_candidates: &[usize],
4183    decide: impl FnMut(PreparationPermit, protocol::ClaimSet) -> Result<PreparationCandidateDecision<T>>,
4184) -> Result<PreparationProbe<T>> {
4185    try_preparation_candidates_once_impl(rotation_bias, affinity_candidates, false, decide)
4186}
4187
4188/// Blocking counterpart of [`try_preparation_candidates_once`]. Physical
4189/// probing and candidate ordering are identical; only registry snapshot
4190/// acquisition may wait, matching the blocking admission contract.
4191pub(super) fn try_preparation_candidates_once_waiting<T>(
4192    rotation_bias: usize,
4193    affinity_candidates: &[usize],
4194    decide: impl FnMut(PreparationPermit, protocol::ClaimSet) -> Result<PreparationCandidateDecision<T>>,
4195) -> Result<PreparationProbe<T>> {
4196    try_preparation_candidates_once_impl(rotation_bias, affinity_candidates, true, decide)
4197}
4198
4199fn try_preparation_candidates_once_impl<T>(
4200    rotation_bias: usize,
4201    affinity_candidates: &[usize],
4202    wait_for_registry: bool,
4203    mut decide: impl FnMut(
4204        PreparationPermit,
4205        protocol::ClaimSet,
4206    ) -> Result<PreparationCandidateDecision<T>>,
4207) -> Result<PreparationProbe<T>> {
4208    let tokens = preparation_token_range()?;
4209    let count = tokens.len();
4210    let start = (pid_window_offset(std::process::id(), count) + rotation_bias) % count;
4211    let mut first_contention = None;
4212    let mut first_registry_contention = None;
4213    for offset in 0..count {
4214        let index = (start + offset) % count;
4215        match try_acquire_preparation_permit_at(
4216            index,
4217            tokens.start + index,
4218            start.wrapping_add(offset).wrapping_add(rotation_bias),
4219            wait_for_registry,
4220            Some(affinity_candidates),
4221        )? {
4222            PreparationPermitAttempt::Acquired(preparation, claim) => {
4223                match decide(preparation, claim)? {
4224                    PreparationCandidateDecision::Accepted(value) => {
4225                        return Ok(PreparationProbe::Acquired(value));
4226                    }
4227                    PreparationCandidateDecision::Retry => {}
4228                    PreparationCandidateDecision::RegistryContended(generation) => {
4229                        first_registry_contention.get_or_insert(generation);
4230                    }
4231                    PreparationCandidateDecision::Contended => {
4232                        return Ok(PreparationProbe::Unavailable);
4233                    }
4234                }
4235            }
4236            PreparationPermitAttempt::TokenContended(evidence) => {
4237                first_contention.get_or_insert(evidence);
4238            }
4239            PreparationPermitAttempt::ResourceContended(evidence) => {
4240                return Ok(
4241                    evidence.map_or(PreparationProbe::Unavailable, PreparationProbe::Contended)
4242                );
4243            }
4244        }
4245    }
4246    Ok(if let Some(evidence) = first_contention {
4247        PreparationProbe::Contended(evidence)
4248    } else if let Some(generation) = first_registry_contention {
4249        PreparationProbe::RegistryContended(generation)
4250    } else {
4251        PreparationProbe::Unavailable
4252    })
4253}
4254
4255/// Park on one concrete physical blocker selected by the complete candidate
4256/// sweep. The deadline is a recovery bound: after it expires, the caller
4257/// rotates and scans the whole pool again rather than remaining attached to a
4258/// stale token/resource queue.
4259pub(super) fn wait_for_preparation_contention(
4260    evidence: protocol::ContentionEvidence,
4261    timeout: std::time::Duration,
4262) -> Result<()> {
4263    let path = match evidence.blocker {
4264        protocol::ResourceKey::Llc(llc) => llc_lock_path(llc),
4265        protocol::ResourceKey::Cpu(cpu) => cpu_lock_path(cpu),
4266        protocol::ResourceKey::Permit(permit) => permit_lock_path(permit),
4267    };
4268    let mode = evidence.mode;
4269    // The writable witness has served its ordering purpose. Close it before
4270    // entering the real flock wait so no synthetic close remains behind the
4271    // physical availability edge consumed below.
4272    drop(evidence);
4273    #[cfg(test)]
4274    PREPARATION_CONTENTION_WAIT_HOOK.with(|slot| {
4275        if let Some(hook) = slot.borrow_mut().take() {
4276            hook();
4277        }
4278    });
4279    drop(
4280        block_flock_deadline(path, mode, std::time::Instant::now() + timeout)?
4281            .map(protocol::AdmissionFlock::from_acquired),
4282    );
4283    Ok(())
4284}
4285
4286/// Resource envelope used only to filter coordinator inotify events while a
4287/// selected intent is waiting for a physical preparation tuple. It is not a
4288/// registry claim and therefore neither reserves capacity nor inflates the
4289/// intent's fairness weight.
4290/// The token pool alone, as a watch envelope to union into a preparation
4291/// intent's registered watch. Two purposes: (1) it makes the intent wake on
4292/// any token release (the pool release event reaches every waiter, not only a
4293/// pinned one — the property that lets the per-token blocked pin be retired),
4294/// and (2) it is the exact, derivable discriminator the scan uses to identify
4295/// a token-consuming preparation intent (`SCAN_FLAG_PREPARATION_INTENT`). Only
4296/// the token pool is unioned — not the full `preparation_resource_watch`, whose
4297/// `host_allowed_cpus` would broaden CPU event-watch well past the bounded
4298/// pool-sized traffic. Tokens are acquired Exclusive, so the pool is watched
4299/// Exclusive to observe their release serials; the run watch already carries
4300/// `permit_mode` Exclusive, so the union changes no mode.
4301pub(super) fn preparation_token_pool_watch() -> Result<protocol::ClaimSet> {
4302    Ok(protocol::ClaimSet::with_permits(
4303        std::iter::empty(),
4304        std::iter::empty(),
4305        preparation_token_range()?,
4306        FlockMode::Shared,
4307        FlockMode::Shared,
4308        FlockMode::Exclusive,
4309    ))
4310}
4311
4312pub(super) fn preparation_resource_watch() -> Result<protocol::ClaimSet> {
4313    let cpu = AdmissionPermitPool::for_host(possible_cpu_width());
4314    let memory = MemoryPermitPool::for_host()?;
4315    let permits = preparation_token_range()?
4316        .chain(cpu.all())
4317        .chain(memory.permits.iter().copied())
4318        .collect::<std::collections::BTreeSet<_>>();
4319    Ok(protocol::ClaimSet::with_permits(
4320        std::iter::empty(),
4321        host_allowed_cpus(),
4322        permits,
4323        FlockMode::Shared,
4324        FlockMode::Shared,
4325        FlockMode::Exclusive,
4326    ))
4327}
4328
4329pub(super) fn validate_preparation_permit(
4330    index: usize,
4331    permit_fds: Vec<(usize, protocol::AdmissionFlock)>,
4332    affinity_cpu: usize,
4333    affinity_lock: protocol::AdmissionFlock,
4334    original_affinity: Vec<usize>,
4335) -> Result<PreparationPermit> {
4336    let tokens = preparation_token_range()?;
4337    let token_permit = tokens
4338        .clone()
4339        .nth(index)
4340        .ok_or_else(|| anyhow::anyhow!("inherited preparation permit index {index} is invalid"))?;
4341    let cpu = AdmissionPermitPool::for_host(possible_cpu_width());
4342    let memory = MemoryPermitPool::for_host()?;
4343    let mut permits = permit_fds
4344        .iter()
4345        .map(|(permit, _)| *permit)
4346        .collect::<Vec<_>>();
4347    permits.sort_unstable();
4348    anyhow::ensure!(
4349        permits.windows(2).all(|pair| pair[0] != pair[1]),
4350        "inherited preparation permit repeats a resource"
4351    );
4352    anyhow::ensure!(
4353        permits.contains(&token_permit),
4354        "inherited preparation permit {index} omits token resource {token_permit}",
4355    );
4356    let cpu_permits = permits
4357        .iter()
4358        .copied()
4359        .filter(|permit| cpu.general.contains(permit) || cpu.reserved.contains(permit))
4360        .collect::<Vec<_>>();
4361    let memory_permits = permits
4362        .iter()
4363        .copied()
4364        .filter(|permit| memory.permits.binary_search(permit).is_ok())
4365        .collect::<Vec<_>>();
4366    anyhow::ensure!(
4367        cpu_permits.len() == PREPARATION_CPU_PERMITS,
4368        "inherited preparation permit has the wrong CPU weight"
4369    );
4370    anyhow::ensure!(
4371        memory_permits.len() == preparation_memory_chunks(),
4372        "inherited preparation permit has the wrong memory weight"
4373    );
4374    anyhow::ensure!(
4375        1 + cpu_permits.len() + memory_permits.len() == permits.len(),
4376        "inherited preparation permit contains an unknown resource"
4377    );
4378    anyhow::ensure!(
4379        !original_affinity.is_empty() && original_affinity.contains(&affinity_cpu),
4380        "inherited preparation affinity CPU {affinity_cpu} is outside its original mask",
4381    );
4382    for (permit, fd) in &permit_fds {
4383        let actual = rustix::fs::fstat(fd).context("stat inherited preparation permit")?;
4384        let expected_path = permit_lock_path(*permit);
4385        let expected = rustix::fs::stat(&expected_path)
4386            .with_context(|| format!("stat preparation permit {expected_path}"))?;
4387        anyhow::ensure!(
4388            actual.st_dev == expected.st_dev && actual.st_ino == expected.st_ino,
4389            "inherited descriptor does not name preparation permit resource {permit}",
4390        );
4391    }
4392    let actual =
4393        rustix::fs::fstat(&affinity_lock).context("stat inherited preparation CPU lock")?;
4394    let expected_path = cpu_lock_path(affinity_cpu);
4395    let expected = rustix::fs::stat(&expected_path)
4396        .with_context(|| format!("stat preparation CPU lock {expected_path}"))?;
4397    anyhow::ensure!(
4398        actual.st_dev == expected.st_dev && actual.st_ino == expected.st_ino,
4399        "inherited descriptor does not name preparation CPU resource {affinity_cpu}",
4400    );
4401    Ok(PreparationPermit::imported(
4402        index,
4403        token_permit,
4404        cpu_permits,
4405        memory_permits,
4406        permit_fds,
4407        affinity_cpu,
4408        affinity_lock,
4409        original_affinity,
4410    ))
4411}
4412
4413/// Highest compact permit identity a pending wrapper may activate on this
4414/// host. The namespace is derived from host-wide possible CPUs, not the
4415/// caller's cgroup mask, so different runners agree on the memory range.
4416pub(crate) fn admission_resource_capacity_hint() -> Result<usize> {
4417    preparation_token_range()?
4418        .last()
4419        .ok_or_else(|| anyhow::anyhow!("host has no preparation admission resources"))
4420}
4421
4422#[derive(Clone)]
4423struct PermitSelection {
4424    permits: Vec<usize>,
4425    admission_class: protocol::AdmissionClass,
4426}
4427
4428#[derive(Clone)]
4429struct VmPermitSelection {
4430    cpu_permits: Vec<usize>,
4431    memory_permits: Vec<usize>,
4432    admission_class: protocol::AdmissionClass,
4433}
4434
4435impl VmPermitSelection {
4436    fn all_permits(&self) -> Vec<usize> {
4437        let mut permits = Vec::with_capacity(self.cpu_permits.len() + self.memory_permits.len());
4438        permits.extend_from_slice(&self.cpu_permits);
4439        permits.extend_from_slice(&self.memory_permits);
4440        permits
4441    }
4442}
4443
4444fn split_vm_permits(
4445    permits: impl IntoIterator<Item = usize>,
4446    memory_pool: Option<&MemoryPermitPool>,
4447) -> (Vec<usize>, Vec<usize>) {
4448    let mut cpu = Vec::new();
4449    let mut memory = Vec::new();
4450    for permit in permits {
4451        if memory_pool.is_some_and(|pool| pool.permits.binary_search(&permit).is_ok()) {
4452            memory.push(permit);
4453        } else {
4454            cpu.push(permit);
4455        }
4456    }
4457    (cpu, memory)
4458}
4459
4460fn permit_only_claim(selection: &PermitSelection) -> protocol::ClaimSet {
4461    resource_claim_with_permits(
4462        &[],
4463        LlcLockMode::Shared,
4464        &[],
4465        FlockMode::Shared,
4466        &selection.permits,
4467        selection.admission_class,
4468    )
4469}
4470
4471/// Remove permit ownership already carried by this process before consulting
4472/// the cross-process registry. A fully owned candidate has no external
4473/// resource delta and is therefore ready without an empty-claim registry
4474/// query; empty claims are deliberately invalid as queue designations.
4475fn claim_without_owned_permits(
4476    candidate: &protocol::ClaimSet,
4477    owned: &std::collections::BTreeSet<usize>,
4478) -> Option<protocol::ClaimSet> {
4479    let mut external = candidate.clone();
4480    external.permits.retain(|permit| !owned.contains(permit));
4481    (!external.is_empty()).then_some(external)
4482}
4483
4484/// `grant_charged` reports whether an in-flight grant is already counting on
4485/// a candidate permit. It orders permits *inside* one admission class and
4486/// never promotes a class: a charged permit stays a candidate and is taken as
4487/// soon as the grant-free permits of its own class run out. The selected
4488/// width and the class each permit comes from therefore match a grant-blind
4489/// walk of the same pool exactly, which is what keeps the charge a bias
4490/// rather than a fence — treating it as a fence would both livelock the
4491/// permit axis (a senior that never publishes an overlapping claim never
4492/// triggers the scan's ticket-order revoke) and, under
4493/// [`LlcPlanSizing::Elastic`], hand back a short selection that
4494/// [`apply_plan_permit_width`] would then truncate the CPU plan to.
4495#[expect(
4496    clippy::too_many_arguments,
4497    reason = "one complete permit request, plus the grant-charge bias over it"
4498)]
4499fn select_admission_permits(
4500    kind: PermitAdmission,
4501    pool: &AdmissionPermitPool,
4502    maximum: usize,
4503    minimum: usize,
4504    rotation: usize,
4505    preferred: &[usize],
4506    mut ready: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4507    mut grant_charged: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4508) -> Result<Option<PermitSelection>> {
4509    if kind == PermitAdmission::None {
4510        return Ok(Some(PermitSelection {
4511            permits: Vec::new(),
4512            admission_class: protocol::AdmissionClass::Ordinary,
4513        }));
4514    }
4515    if maximum == 0 {
4516        // A zero-width request names no permits. The collection loop below
4517        // only stops on `permits.len() == maximum`, so without this it walks
4518        // the whole pool and hands back every ready permit. An empty selection
4519        // still has to clear the caller's floor.
4520        return Ok((minimum == 0).then(|| PermitSelection {
4521            permits: Vec::new(),
4522            admission_class: match kind {
4523                PermitAdmission::Cooperative => protocol::AdmissionClass::Ordinary,
4524                PermitAdmission::Build => protocol::AdmissionClass::Build,
4525                PermitAdmission::None => unreachable!(),
4526            },
4527        }));
4528    }
4529    let (first, second) = match kind {
4530        PermitAdmission::Cooperative => (&pool.general, &pool.reserved),
4531        PermitAdmission::Build => (&pool.reserved, &pool.general),
4532        PermitAdmission::None => unreachable!(),
4533    };
4534    let mut permits = Vec::with_capacity(maximum);
4535    let mut seen = std::collections::BTreeSet::new();
4536    for group in [first, second] {
4537        if group.is_empty() || permits.len() == maximum {
4538            continue;
4539        }
4540        // Preserve the admission class preference before OFD reuse. In
4541        // particular, cooperative/default work first tries general capacity;
4542        // inherited preparation owners in the reserved suffix are reused only
4543        // after the general class is exhausted.
4544        let mut ordered = Vec::with_capacity(preferred.len() + group.len());
4545        ordered.extend(
4546            preferred
4547                .iter()
4548                .copied()
4549                .filter(|permit| group.contains(permit)),
4550        );
4551        let start = rotation % group.len();
4552        ordered.extend((0..group.len()).map(|offset| group[(start + offset) % group.len()]));
4553        ordered.retain(|permit| seen.insert(*permit));
4554        // Ready permits this class would give up only to a grant-free peer of
4555        // the same class. They are appended below in discovery order, so a
4556        // class whose ready permits are all charged selects exactly what a
4557        // grant-blind walk of it would.
4558        let mut charged = Vec::new();
4559        for permit in ordered {
4560            if permits.len() == maximum {
4561                break;
4562            }
4563            let admission_class = match kind {
4564                PermitAdmission::Cooperative if pool.reserved.contains(&permit) => {
4565                    protocol::AdmissionClass::DefaultBorrow
4566                }
4567                PermitAdmission::Cooperative => protocol::AdmissionClass::Ordinary,
4568                PermitAdmission::Build => protocol::AdmissionClass::Build,
4569                PermitAdmission::None => unreachable!(),
4570            };
4571            let candidate = PermitSelection {
4572                permits: vec![permit],
4573                admission_class,
4574            };
4575            let claim = permit_only_claim(&candidate);
4576            if !ready(&claim)? {
4577                continue;
4578            }
4579            if grant_charged(&claim)? {
4580                if charged.len() < maximum {
4581                    charged.push(permit);
4582                }
4583            } else {
4584                permits.push(permit);
4585            }
4586        }
4587        for permit in charged {
4588            if permits.len() == maximum {
4589                break;
4590            }
4591            permits.push(permit);
4592        }
4593    }
4594    if permits.len() < minimum {
4595        return Ok(None);
4596    }
4597    permits.sort_unstable();
4598    let admission_class = match kind {
4599        PermitAdmission::Cooperative
4600            if permits.iter().any(|permit| pool.reserved.contains(permit)) =>
4601        {
4602            protocol::AdmissionClass::DefaultBorrow
4603        }
4604        PermitAdmission::Cooperative => protocol::AdmissionClass::Ordinary,
4605        PermitAdmission::Build => protocol::AdmissionClass::Build,
4606        PermitAdmission::None => unreachable!(),
4607    };
4608    let selection = PermitSelection {
4609        permits,
4610        admission_class,
4611    };
4612    if ready(&permit_only_claim(&selection))? {
4613        Ok(Some(selection))
4614    } else {
4615        Ok(None)
4616    }
4617}
4618
4619/// `grant_charged` carries the same within-tier bias contract as
4620/// [`select_admission_permits`]: the memory pool is one tier, so
4621/// a charged chunk is taken as soon as the grant-free chunks run out and the
4622/// selected count never falls below a grant-blind walk's.
4623fn select_memory_permits(
4624    pool: &MemoryPermitPool,
4625    required: usize,
4626    admission_class: protocol::AdmissionClass,
4627    rotation: usize,
4628    preferred: &[usize],
4629    mut ready: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4630    mut grant_charged: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4631) -> Result<Option<Vec<usize>>> {
4632    if required == 0 {
4633        return Ok(Some(Vec::new()));
4634    }
4635    let mut selected = Vec::with_capacity(required);
4636    let mut ordered = preferred
4637        .iter()
4638        .copied()
4639        .filter(|permit| pool.permits.binary_search(permit).is_ok())
4640        .collect::<Vec<_>>();
4641    let start = rotation % pool.permits.len();
4642    ordered.extend(
4643        (0..pool.permits.len()).map(|offset| pool.permits[(start + offset) % pool.permits.len()]),
4644    );
4645    let mut seen = std::collections::BTreeSet::new();
4646    ordered.retain(|permit| seen.insert(*permit));
4647    let mut charged = Vec::new();
4648    for permit in ordered {
4649        if selected.len() == required {
4650            break;
4651        }
4652        let candidate = PermitSelection {
4653            permits: vec![permit],
4654            admission_class,
4655        };
4656        let claim = permit_only_claim(&candidate);
4657        if !ready(&claim)? {
4658            continue;
4659        }
4660        if grant_charged(&claim)? {
4661            if charged.len() < required {
4662                charged.push(permit);
4663            }
4664        } else {
4665            selected.push(permit);
4666        }
4667    }
4668    for permit in charged {
4669        if selected.len() == required {
4670            break;
4671        }
4672        selected.push(permit);
4673    }
4674    if selected.len() < required {
4675        return Ok(None);
4676    }
4677    selected.sort_unstable();
4678    let candidate = PermitSelection {
4679        permits: selected.clone(),
4680        admission_class,
4681    };
4682    ready(&permit_only_claim(&candidate)).map(|ready| ready.then_some(selected))
4683}
4684
4685/// `grant_charged` is the within-class bias documented on
4686/// [`select_admission_permits`]. It is deliberately absent from
4687/// the whole-selection readiness check below: that check is validity, not
4688/// selection, and folding the charge into it would turn the bias back into an
4689/// all-or-nothing filter.
4690#[expect(
4691    clippy::too_many_arguments,
4692    reason = "mirrors select_vm_permits, which carries one complete permit request"
4693)]
4694fn select_vm_permits_grant_aware(
4695    kind: PermitAdmission,
4696    cpu_pool: &AdmissionPermitPool,
4697    memory_pool: Option<&MemoryPermitPool>,
4698    maximum_cpus: usize,
4699    minimum_cpus: usize,
4700    required_memory: usize,
4701    cpu_rotation: usize,
4702    memory_rotation: usize,
4703    preferred_cpu: &[usize],
4704    preferred_memory: &[usize],
4705    mut ready: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4706    mut grant_charged: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4707) -> Result<Option<VmPermitSelection>> {
4708    let Some(cpu) = select_admission_permits(
4709        kind,
4710        cpu_pool,
4711        maximum_cpus,
4712        minimum_cpus,
4713        cpu_rotation,
4714        preferred_cpu,
4715        &mut ready,
4716        &mut grant_charged,
4717    )?
4718    else {
4719        return Ok(None);
4720    };
4721    let memory = match memory_pool {
4722        Some(pool) => select_memory_permits(
4723            pool,
4724            required_memory,
4725            cpu.admission_class,
4726            memory_rotation,
4727            preferred_memory,
4728            &mut ready,
4729            &mut grant_charged,
4730        )?,
4731        None => Some(Vec::new()),
4732    };
4733    let Some(memory_permits) = memory else {
4734        return Ok(None);
4735    };
4736    let selection = VmPermitSelection {
4737        cpu_permits: cpu.permits,
4738        memory_permits,
4739        admission_class: cpu.admission_class,
4740    };
4741    let combined = PermitSelection {
4742        permits: selection.all_permits(),
4743        admission_class: selection.admission_class,
4744    };
4745    if combined.permits.is_empty() {
4746        return Ok(Some(selection));
4747    }
4748    ready(&permit_only_claim(&combined)).map(|is_ready| is_ready.then_some(selection))
4749}
4750
4751pub(crate) struct VmPermitPool {
4752    cpu: AdmissionPermitPool,
4753    memory: MemoryPermitPool,
4754    cpu_required: usize,
4755    memory_required: usize,
4756    cpu_rotation: usize,
4757    memory_rotation: usize,
4758    preferred_cpu: Vec<usize>,
4759    preferred_memory: Vec<usize>,
4760}
4761
4762#[derive(Clone)]
4763pub(crate) struct VmPermitReservation {
4764    pub(crate) cpu_permits: Vec<usize>,
4765    pub(crate) memory_permits: Vec<usize>,
4766    pub(crate) admission_class: protocol::AdmissionClass,
4767}
4768
4769impl VmPermitReservation {
4770    pub(crate) fn all_permits(&self) -> Vec<usize> {
4771        let mut permits = Vec::with_capacity(self.cpu_permits.len() + self.memory_permits.len());
4772        permits.extend_from_slice(&self.cpu_permits);
4773        permits.extend_from_slice(&self.memory_permits);
4774        permits
4775    }
4776}
4777
4778impl VmPermitPool {
4779    pub(crate) fn new_with_preparation(
4780        cpu_required: usize,
4781        memory_mib: u32,
4782        pending: Option<&protocol::PendingAdmission>,
4783    ) -> Result<Self> {
4784        let cpu = AdmissionPermitPool::for_host(possible_cpu_width());
4785        Self::with_cpu_pool(cpu, cpu_required, memory_mib, pending)
4786    }
4787
4788    pub(crate) fn new_performance_with_preparation(
4789        cpu_required: usize,
4790        memory_mib: u32,
4791        pending: Option<&protocol::PendingAdmission>,
4792    ) -> Result<Self> {
4793        let cpu = AdmissionPermitPool::for_performance_host(possible_cpu_width());
4794        Self::with_cpu_pool(cpu, cpu_required, memory_mib, pending)
4795    }
4796
4797    fn with_cpu_pool(
4798        cpu: AdmissionPermitPool,
4799        cpu_required: usize,
4800        memory_mib: u32,
4801        pending: Option<&protocol::PendingAdmission>,
4802    ) -> Result<Self> {
4803        let memory = MemoryPermitPool::for_host()?;
4804        let memory_required = memory.required_chunks(memory_mib)?;
4805        Ok(Self {
4806            cpu_rotation: pid_window_offset(std::process::id(), cpu.len().max(1)),
4807            memory_rotation: pid_window_offset(std::process::id(), memory.permits.len().max(1)),
4808            cpu,
4809            memory,
4810            cpu_required,
4811            memory_required,
4812            preferred_cpu: pending.map_or_else(Vec::new, |pending| {
4813                pending.preparation_cpu_permits().to_vec()
4814            }),
4815            preferred_memory: pending.map_or_else(Vec::new, |pending| {
4816                pending.preparation_memory_permits().to_vec()
4817            }),
4818        })
4819    }
4820
4821    pub(crate) fn watch_permits(&self) -> Vec<usize> {
4822        self.cpu
4823            .all()
4824            .chain(self.memory.permits.iter().copied())
4825            .collect()
4826    }
4827
4828    pub(crate) fn select(
4829        &self,
4830        ready: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4831    ) -> Result<Option<VmPermitReservation>> {
4832        self.select_grant_aware(ready, |_| Ok(false))
4833    }
4834
4835    /// `grant_charged` is the within-class bias documented on
4836    /// [`select_admission_permits`]: a charged permit stays a candidate and is
4837    /// taken as soon as the grant-free permits of its class run out, so the
4838    /// selected width and the class each permit comes from match a grant-blind
4839    /// walk of the same pool exactly. This request is sized exactly
4840    /// (`cpu_required` is both the floor and the ceiling), so the bias can only
4841    /// reorder the walk — it can never hand back a short set.
4842    pub(crate) fn select_grant_aware(
4843        &self,
4844        ready: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4845        grant_charged: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4846    ) -> Result<Option<VmPermitReservation>> {
4847        select_vm_permits_grant_aware(
4848            PermitAdmission::Cooperative,
4849            &self.cpu,
4850            Some(&self.memory),
4851            self.cpu_required,
4852            self.cpu_required,
4853            self.memory_required,
4854            self.cpu_rotation,
4855            self.memory_rotation,
4856            &self.preferred_cpu,
4857            &self.preferred_memory,
4858            ready,
4859            grant_charged,
4860        )
4861        .map(|selection| {
4862            selection.map(|selection| VmPermitReservation {
4863                cpu_permits: selection.cpu_permits,
4864                memory_permits: selection.memory_permits,
4865                admission_class: selection.admission_class,
4866            })
4867        })
4868    }
4869
4870    /// Choose an initial exact permit set against the live registry aggregate,
4871    /// subtracting the caller's own PENDING OFDs. General cooperative capacity
4872    /// remains the first choice even when a wrapper owns reusable preparation
4873    /// permits in the reserved suffix; that suffix is a soft fallback, not a
4874    /// hard build/default interoperability fence.
4875    ///
4876    /// The result seeds the exact claim a waiter publishes when it joins the
4877    /// registry — the claim the authoritative scan later hands that ticket as
4878    /// its grant, and the fence every junior behind it must clear once the
4879    /// grant lands. Naming a permit some junior's in-flight grant is already
4880    /// counting on therefore resolves as a ticket-order revocation of that
4881    /// junior, exactly as it does for the queued designation
4882    /// [`select_plan_permits_grant_aware`] already biases. The charge is read
4883    /// from the snapshot this seed already takes: its watch names every pool
4884    /// permit, which is what makes the folded permit indices readable from it.
4885    pub(crate) fn select_registered(&self) -> Result<Option<VmPermitReservation>> {
4886        let watch = resource_claim_with_permits(
4887            &[],
4888            LlcLockMode::Shared,
4889            &[],
4890            FlockMode::Shared,
4891            &self.watch_permits(),
4892            protocol::AdmissionClass::Ordinary,
4893        );
4894        let snapshot = protocol::registered_claim_snapshot(&watch)?;
4895        let owned = self
4896            .preferred_cpu
4897            .iter()
4898            .chain(&self.preferred_memory)
4899            .copied()
4900            .collect::<std::collections::BTreeSet<_>>();
4901        let charged = |candidate: &protocol::ClaimSet| {
4902            let Some(external) = claim_without_owned_permits(candidate, &owned) else {
4903                return Ok(false);
4904            };
4905            snapshot.grant_conflicts(&external)
4906        };
4907        let selected = self.select_grant_aware(
4908            |candidate| {
4909                let Some(external) = claim_without_owned_permits(candidate, &owned) else {
4910                    return Ok(true);
4911                };
4912                snapshot.conflicts(&external).map(|busy| !busy)
4913            },
4914            charged,
4915        )?;
4916        if selected.is_some() {
4917            Ok(selected)
4918        } else {
4919            // A queued exact designation still needs a complete canonical
4920            // shape when every compatible permit is currently occupied. The
4921            // charge stays a bias here too: it orders a walk that now accepts
4922            // every permit rather than fencing any of them off.
4923            self.select_grant_aware(|_| Ok(true), charged)
4924        }
4925    }
4926}
4927
4928#[derive(Clone, Copy, Debug, PartialEq, Eq)]
4929enum LlcPlanSizing {
4930    /// The resolved budget is a fixed resource contract.
4931    Exact,
4932    /// The resolved budget is a ceiling; any non-empty compatible subset can
4933    /// make forward progress.
4934    Elastic,
4935}
4936
4937impl LlcPlanSizing {
4938    fn target_for_capacity(self, maximum: usize, available: usize) -> Option<usize> {
4939        match self {
4940            Self::Exact => (available >= maximum).then_some(maximum),
4941            Self::Elastic => {
4942                let target = maximum.min(available);
4943                (target > 0).then_some(target)
4944            }
4945        }
4946    }
4947
4948    fn queued_target(self, maximum: usize) -> usize {
4949        match self {
4950            Self::Exact => maximum,
4951            Self::Elastic => 1,
4952        }
4953    }
4954}
4955
4956/// Permit selection plus the CPU width that the selected admission capacity
4957/// can fund. Build permits are a preferred parallelism budget for elastic
4958/// scheduler builds, not a second hard ownership fence: when the build-only
4959/// namespace is saturated, one SH-compatible CPU may still run a serial
4960/// build. Performance CPU/LLC EX ownership remains the hard admission fence.
4961struct PlanPermitSelection {
4962    permits: VmPermitSelection,
4963    cpu_width: usize,
4964}
4965
4966/// Grant-aware permit planning: `grant_conflicts` reports whether an
4967/// in-flight grant already counts on a candidate permit, and the selection
4968/// prefers the permits it does not cover.
4969///
4970/// The preference lives inside one admission class and inside one selection
4971/// pass (see [`select_admission_permits`]), never as a filter over the whole
4972/// request. That is what makes it safe on the elastic sizing, whose permit
4973/// floor is one: a filtering tier can satisfy an elastic request from a
4974/// single grant-free permit, and because an elastic selection's permit count
4975/// *is* the CPU width [`apply_plan_permit_width`] truncates the plan to, the
4976/// charge would end up deciding how many CPUs the plan funds. Biasing within
4977/// the pass instead keeps the selected width — and the class each permit is
4978/// drawn from — identical to a grant-blind walk, so a saturated or fully
4979/// charged pool selects exactly what it selects today and a senior still
4980/// publishes the overlapping claim the scan's ticket-order revoke needs.
4981#[expect(
4982    clippy::too_many_arguments,
4983    reason = "one complete permit request, plus the grant-charge bias over it"
4984)]
4985fn select_plan_permits_grant_aware(
4986    kind: PermitAdmission,
4987    sizing: LlcPlanSizing,
4988    cpu_pool: &AdmissionPermitPool,
4989    memory_pool: Option<&MemoryPermitPool>,
4990    maximum_cpus: usize,
4991    required_memory: usize,
4992    cpu_rotation: usize,
4993    memory_rotation: usize,
4994    preferred_cpu: &[usize],
4995    preferred_memory: &[usize],
4996    ready: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4997    grant_conflicts: impl FnMut(&protocol::ClaimSet) -> Result<bool>,
4998) -> Result<Option<PlanPermitSelection>> {
4999    let minimum_cpus = match sizing {
5000        LlcPlanSizing::Exact => maximum_cpus,
5001        LlcPlanSizing::Elastic => 1,
5002    };
5003    if let Some(permits) = select_vm_permits_grant_aware(
5004        kind,
5005        cpu_pool,
5006        memory_pool,
5007        maximum_cpus,
5008        minimum_cpus,
5009        required_memory,
5010        cpu_rotation,
5011        memory_rotation,
5012        preferred_cpu,
5013        preferred_memory,
5014        ready,
5015        grant_conflicts,
5016    )? {
5017        let cpu_width = match (sizing, kind) {
5018            (LlcPlanSizing::Elastic, PermitAdmission::Cooperative | PermitAdmission::Build) => {
5019                permits.cpu_permits.len()
5020            }
5021            (LlcPlanSizing::Exact, _) | (LlcPlanSizing::Elastic, PermitAdmission::None) => {
5022                maximum_cpus
5023            }
5024        };
5025        return Ok(Some(PlanPermitSelection { permits, cpu_width }));
5026    }
5027
5028    if sizing == LlcPlanSizing::Elastic
5029        && kind == PermitAdmission::Build
5030        && memory_pool.is_none()
5031        && maximum_cpus > 0
5032    {
5033        return Ok(Some(PlanPermitSelection {
5034            permits: VmPermitSelection {
5035                cpu_permits: Vec::new(),
5036                memory_permits: Vec::new(),
5037                admission_class: protocol::AdmissionClass::Build,
5038            },
5039            cpu_width: 1,
5040        }));
5041    }
5042
5043    Ok(None)
5044}
5045
5046fn apply_plan_permit_width(
5047    sizing: LlcPlanSizing,
5048    selection: &PlanPermitSelection,
5049    topo: &HostTopology,
5050    selected_llcs: &mut Vec<usize>,
5051    selected_cpus: &mut Vec<usize>,
5052) {
5053    if sizing != LlcPlanSizing::Elastic || selection.cpu_width >= selected_cpus.len() {
5054        return;
5055    }
5056    selected_cpus.truncate(selection.cpu_width);
5057    selected_llcs.retain(|llc| {
5058        topo.llc_groups[*llc]
5059            .cpus
5060            .iter()
5061            .any(|cpu| selected_cpus.contains(cpu))
5062    });
5063}
5064
5065struct LlcPlanAcquireRequest<'a> {
5066    topo: &'a HostTopology,
5067    test_topo: &'a crate::topology::TestTopology,
5068    cpu_cap: Option<CpuCap>,
5069    llc_policy: PlacementPolicy,
5070    cpu_policy: CpuSelectionPolicy,
5071    wait: bool,
5072    sizing: LlcPlanSizing,
5073    permit_admission: PermitAdmission,
5074    cancelled: Option<&'a AtomicBool>,
5075    pending: Option<protocol::PendingAdmission>,
5076    memory_mib: Option<u32>,
5077}
5078
5079fn acquire_llc_plan_impl(request: LlcPlanAcquireRequest<'_>) -> Result<LlcPlan> {
5080    let LlcPlanAcquireRequest {
5081        topo,
5082        test_topo,
5083        cpu_cap,
5084        llc_policy,
5085        cpu_policy,
5086        wait,
5087        sizing,
5088        permit_admission,
5089        cancelled,
5090        pending,
5091        memory_mib,
5092    } = request;
5093    check_acquire_cancelled(cancelled)?;
5094    if crate::cargo_test_mode::cargo_test_mode_active() {
5095        // Bare `cargo test` mode: no peer-coordination contract. Both
5096        // build-time shape planning and run-time acquisition use this exact
5097        // helper so the stamped CPU budget and applied mask cannot diverge.
5098        let _ = test_topo;
5099        let _ = cpu_cap;
5100        let plan = cargo_test_mode_llc_plan(topo)?;
5101        check_acquire_cancelled(cancelled)?;
5102        return Ok(plan);
5103    }
5104    acquire_llc_plan_with_acquire_fn_impl(
5105        LlcPlanAcquireRequest {
5106            topo,
5107            test_topo,
5108            cpu_cap,
5109            llc_policy,
5110            cpu_policy,
5111            wait,
5112            sizing,
5113            permit_admission,
5114            cancelled,
5115            pending,
5116            memory_mib,
5117        },
5118        try_acquire_llc_plan_locks_with_evidence,
5119        || {},
5120    )
5121}
5122
5123/// Ownership-free plan used by both build and run when
5124/// `KTSTR_CARGO_TEST_MODE` is active.
5125///
5126/// Cargo-test mode deliberately ignores CPU caps and names the complete
5127/// allowed cpuset, matching its "no host coordination" contract. Keeping this
5128/// in one helper prevents the build-side budget stamp from describing a
5129/// cap-truncated mask while the run side actually uses the full cpuset.
5130fn cargo_test_mode_llc_plan(topo: &HostTopology) -> Result<LlcPlan> {
5131    let allowed = host_allowed_cpus();
5132    if allowed.is_empty() {
5133        return Err(ResourceContention {
5134            reason: "could not determine allowed CPU set \
5135                     (sched_getaffinity and /proc/self/status both failed)"
5136                .into(),
5137        }
5138        .into());
5139    }
5140    let allowed_set: std::collections::BTreeSet<usize> = allowed.iter().copied().collect();
5141    let locked_llcs: Vec<usize> = topo
5142        .llc_groups
5143        .iter()
5144        .enumerate()
5145        .filter_map(|(idx, group)| {
5146            if group.cpus.iter().any(|c| allowed_set.contains(c)) {
5147                Some(idx)
5148            } else {
5149                None
5150            }
5151        })
5152        .collect();
5153    let mems = plan_mems(&allowed, topo);
5154    Ok(LlcPlan {
5155        locked_llcs,
5156        cpus: allowed,
5157        permits: Vec::new(),
5158        mems,
5159        locks: protocol::Acquired::untracked(Vec::new()),
5160    })
5161}
5162
5163fn check_acquire_cancelled(cancelled: Option<&AtomicBool>) -> Result<()> {
5164    if cancelled.is_some_and(|flag| flag.load(Ordering::Acquire)) {
5165        Err(std::io::Error::new(
5166            std::io::ErrorKind::Interrupted,
5167            "ktstr LLC-plan acquisition interrupted",
5168        )
5169        .into())
5170    } else {
5171        Ok(())
5172    }
5173}
5174
5175/// Parameterized form of [`acquire_llc_plan_interruptible`] that takes the
5176/// ACQUIRE closure as a seam. Production calls this with
5177/// [`try_acquire_llc_plan_locks_with_evidence`] (non-blocking `LOCK_SH` per resource);
5178/// tests can pass a closure that returns `Ok(None)` on attempt 0 and
5179/// forwards on attempt 1 to simulate a peer winning the first race,
5180/// or an attempt-counting closure that always fails to exercise the
5181/// retry-exhausted error path.
5182///
5183/// `acquire_fn` receives `(selected, snapshots)` and returns
5184/// `Ok(Some(locks))` on success, `Ok(None)` to trigger a retry, or
5185/// propagates hard errors unchanged. Production closure is the
5186/// free-standing [`try_acquire_llc_plan_locks_with_evidence`]; the test closure
5187/// can track its own attempt counter via interior mutability
5188/// ([`std::cell::Cell`], `Mutex`, atomic int).
5189///
5190/// The FAST-PHASE loop body — DISCOVER, PLAN, retry budget, final
5191/// holder diagnostics — is shared between both entry points so the
5192/// test seam exercises the exact retry-and-diagnose sequence
5193/// production uses, not a parallel implementation. (`acquire_fn` is
5194/// a fast-phase seam only: the wait phase acquires through the
5195/// protocol coordinator engine against real lockfiles.)
5196///
5197/// `wait` separates the two contention regimes. No-wait callers retain the
5198/// short [`ACQUIRE_MAX_TOCTOU_RETRIES`] race budget. A waiting test run joins
5199/// the admission registry after its first failed all-or-nothing attempt;
5200/// repeating DISCOVER→PLAN against a published claim or real flock cannot beat
5201/// that holder and only multiplies procfs and registry traffic. Once elected
5202/// coordinator, the waiting path re-runs DISCOVER→PLAN against LIVE holder state
5203/// on every lock-dir wake — the re-plan-on-wake contract — and probes the
5204/// freshly selected LLCs and CPUs all-or-nothing. An incomplete probe releases
5205/// its N-1 available resources before sleeping on the blocker. Ordinary tickets
5206/// wait on targeted futexes; the coordinator waits on filtered inotify events.
5207#[cfg(test)]
5208fn acquire_llc_plan_with_acquire_fn<F>(
5209    topo: &HostTopology,
5210    test_topo: &crate::topology::TestTopology,
5211    cpu_cap: Option<CpuCap>,
5212    policy: PlacementPolicy,
5213    wait: bool,
5214    cancelled: Option<&AtomicBool>,
5215    acquire_fn: F,
5216) -> Result<LlcPlan>
5217where
5218    F: FnMut(&[usize], &[usize], &[LlcSnapshot]) -> Result<Option<Vec<protocol::AdmissionFlock>>>,
5219{
5220    acquire_llc_plan_with_acquire_fn_impl(
5221        LlcPlanAcquireRequest {
5222            topo,
5223            test_topo,
5224            cpu_cap,
5225            llc_policy: policy,
5226            cpu_policy: CpuSelectionPolicy::WithinEachLlc(policy),
5227            wait,
5228            sizing: LlcPlanSizing::Exact,
5229            permit_admission: PermitAdmission::None,
5230            cancelled,
5231            pending: None,
5232            memory_mib: None,
5233        },
5234        acquire_fn,
5235        || {},
5236    )
5237}
5238
5239/// Test-only elastic entry point with an event hook at the first coordinator
5240/// replan. This lets lock-release tests drive the real wait path from protocol
5241/// state rather than guessing wall-clock sleeps.
5242#[cfg(test)]
5243fn acquire_elastic_build_llc_plan_with_coordinator_step_hook(
5244    topo: &HostTopology,
5245    test_topo: &crate::topology::TestTopology,
5246    cpu_cap: Option<CpuCap>,
5247    cancelled: Option<&AtomicBool>,
5248    on_coordinator_step: impl FnMut(),
5249) -> Result<LlcPlan> {
5250    acquire_llc_plan_with_acquire_fn_impl(
5251        LlcPlanAcquireRequest {
5252            topo,
5253            test_topo,
5254            cpu_cap,
5255            llc_policy: PlacementPolicy::Consolidate,
5256            cpu_policy: CpuSelectionPolicy::least_held_for_process(),
5257            wait: true,
5258            sizing: LlcPlanSizing::Elastic,
5259            permit_admission: PermitAdmission::Build,
5260            cancelled,
5261            pending: None,
5262            memory_mib: None,
5263        },
5264        try_acquire_llc_plan_locks_with_evidence,
5265        on_coordinator_step,
5266    )
5267}
5268
5269/// Exact (non-elastic, direct kernel build) counterpart of
5270/// [`acquire_elastic_build_llc_plan_with_coordinator_step_hook`], mirroring
5271/// [`acquire_build_llc_plan`]'s policies with `wait: true`. Lets a test drive
5272/// the wait phase deterministically: the hook fires once the contended build
5273/// has registered and is executing its first coordinator replan.
5274#[cfg(test)]
5275fn acquire_build_llc_plan_with_coordinator_step_hook(
5276    topo: &HostTopology,
5277    test_topo: &crate::topology::TestTopology,
5278    cpu_cap: Option<CpuCap>,
5279    cancelled: Option<&AtomicBool>,
5280    on_coordinator_step: impl FnMut(),
5281) -> Result<LlcPlan> {
5282    acquire_llc_plan_with_acquire_fn_impl(
5283        LlcPlanAcquireRequest {
5284            topo,
5285            test_topo,
5286            cpu_cap,
5287            llc_policy: PlacementPolicy::Consolidate,
5288            cpu_policy: CpuSelectionPolicy::WithinEachLlc(PlacementPolicy::Consolidate),
5289            wait: true,
5290            sizing: LlcPlanSizing::Exact,
5291            permit_admission: PermitAdmission::Build,
5292            cancelled,
5293            pending: None,
5294            memory_mib: None,
5295        },
5296        try_acquire_llc_plan_locks_with_evidence,
5297        on_coordinator_step,
5298    )
5299}
5300
5301fn acquire_llc_plan_with_acquire_fn_impl<F, A, C>(
5302    request: LlcPlanAcquireRequest<'_>,
5303    mut acquire_fn: F,
5304    mut on_coordinator_step: C,
5305) -> Result<LlcPlan>
5306where
5307    F: FnMut(&[usize], &[usize], &[LlcSnapshot]) -> Result<A>,
5308    A: IntoLlcLockAttempt,
5309    C: FnMut(),
5310{
5311    let LlcPlanAcquireRequest {
5312        topo,
5313        test_topo,
5314        cpu_cap,
5315        llc_policy,
5316        cpu_policy,
5317        wait,
5318        sizing,
5319        permit_admission,
5320        cancelled,
5321        mut pending,
5322        memory_mib,
5323    } = request;
5324    // Elastic builders preserve peer-held Consolidate ordering and give every
5325    // process a stable tie rotation for the fresh suffix. This fans out both
5326    // a cold-start herd and planners that need capacity beyond the currently
5327    // held LLCs.
5328    let elastic_fresh_rotation =
5329        (sizing == LlcPlanSizing::Elastic).then(|| pid_window_offset(std::process::id(), 1 << 16));
5330    check_acquire_cancelled(cancelled)?;
5331    // Resolve the calling process's allowed cpuset. Plans must fit
5332    // inside this set — sched_setaffinity against a mask outside the
5333    // process's cgroup cpuset either fails outright or produces an
5334    // empty effective set (the vCPU thread then cannot run). Reading
5335    // the syscall ONCE here and threading it through means every
5336    // TOCTOU retry sees the same baseline; a cgroup change mid-plan
5337    // is a host-reconfiguration event the retry budget does not
5338    // attempt to absorb.
5339    let allowed_vec = host_allowed_cpus();
5340    if allowed_vec.is_empty() {
5341        return Err(ResourceContention {
5342            reason: "could not determine allowed CPU set \
5343                     (sched_getaffinity and /proc/self/status both failed)"
5344                .into(),
5345        }
5346        .into());
5347    }
5348    let allowed: std::collections::BTreeSet<usize> = allowed_vec.iter().copied().collect();
5349    let allowed_cpus = allowed.len();
5350    let preferred_cpu_permits = pending.as_ref().map_or_else(Vec::new, |pending| {
5351        pending.preparation_cpu_permits().to_vec()
5352    });
5353    let preferred_memory_permits = pending.as_ref().map_or_else(Vec::new, |pending| {
5354        pending.preparation_memory_permits().to_vec()
5355    });
5356    let permit_pool = match permit_admission {
5357        PermitAdmission::Build => AdmissionPermitPool::for_build_host(possible_cpu_width())?,
5358        PermitAdmission::Cooperative | PermitAdmission::None => {
5359            AdmissionPermitPool::for_host(possible_cpu_width())
5360        }
5361    };
5362    let permit_rotation = pid_window_offset(std::process::id(), permit_pool.len().max(1));
5363    let memory_pool = memory_mib
5364        .map(|_| MemoryPermitPool::for_host())
5365        .transpose()?;
5366    let memory_required = match (memory_pool.as_ref(), memory_mib) {
5367        (Some(pool), Some(memory_mib)) => pool.required_chunks(memory_mib)?,
5368        (None, None) => 0,
5369        _ => unreachable!("memory pool and requested memory are constructed together"),
5370    };
5371    let memory_rotation = memory_pool.as_ref().map_or(0, |pool| {
5372        pid_window_offset(std::process::id(), pool.permits.len().max(1))
5373    });
5374    let target_cpus = match cpu_cap {
5375        Some(cap) => cap.effective_count(allowed_cpus)?,
5376        None => default_cpu_budget(allowed_cpus),
5377    };
5378    if target_cpus == 0 {
5379        // Defense in depth. `default_cpu_budget` has a `.max(1)`
5380        // floor and `effective_count` on a `NonZeroUsize` cap can
5381        // never return 0, but surfacing this as an explicit bail
5382        // catches future regressions (e.g. someone wires a signed
5383        // integer into the budget math) instead of silently
5384        // producing a plan with no locks.
5385        return Err(ResourceContention {
5386            reason: "CPU budget resolved to zero".into(),
5387        }
5388        .into());
5389    }
5390
5391    // ---- FAST PHASE: TOCTOU-bounded, non-blocking, all-or-nothing,
5392    // claim-fenced. Bounded attempts, then either bail (no-wait callers) or
5393    // join the registry.
5394    let mut attempt: u32 = 0;
5395    let mut queue_seed_snapshots = None;
5396    let mut queue_seed_cpu_states = None;
5397    let mut queue_seed_universe = None;
5398    let mut queue_seed_permit_snapshot = None;
5399    let mut contention = protocol::ContentionSet::default();
5400    loop {
5401        check_acquire_cancelled(cancelled)?;
5402        let (snapshots, cpu_states, aggregate) =
5403            discover_registered_placement_states(topo, &allowed).map_err(|e| {
5404                ResourceContention {
5405                    reason: format!("discover registered placement state: {e}"),
5406                }
5407            })?;
5408        // Subtract resources fenced by incompatible exact ticket claims. LLC
5409        // and CPU SH requests coexist with earlier SH reservations; only EX
5410        // claims are removed.
5411        let contention_markers = contention.marker_vec();
5412        let contended_llcs = contention_markers
5413            .iter()
5414            .filter_map(|marker| match marker.blocker {
5415                protocol::ResourceKey::Llc(llc) => Some(llc),
5416                protocol::ResourceKey::Cpu(_) | protocol::ResourceKey::Permit(_) => None,
5417            })
5418            .collect::<std::collections::BTreeSet<_>>();
5419        let contended_cpus = contention_markers
5420            .iter()
5421            .filter_map(|marker| match marker.blocker {
5422                protocol::ResourceKey::Cpu(cpu) => Some(cpu),
5423                protocol::ResourceKey::Llc(_) | protocol::ResourceKey::Permit(_) => None,
5424            })
5425            .collect::<std::collections::BTreeSet<_>>();
5426        let mut eligible: Vec<LlcSnapshot> = Vec::with_capacity(snapshots.len());
5427        let real_llc_filtered = snapshots
5428            .iter()
5429            .any(|snapshot| snapshot.exclusive_held || contended_llcs.contains(&snapshot.llc_idx));
5430        let mut registry_llc_filtered = false;
5431        for snapshot in &snapshots {
5432            if snapshot.exclusive_held || contended_llcs.contains(&snapshot.llc_idx) {
5433                continue;
5434            }
5435            let candidate =
5436                protocol::ClaimSet::new([snapshot.llc_idx], std::iter::empty(), FlockMode::Shared);
5437            if aggregate.conflicts(&candidate)? {
5438                registry_llc_filtered = true;
5439            } else {
5440                eligible.push(snapshot.clone());
5441            }
5442        }
5443        let real_cpu_filtered = allowed.iter().any(|cpu| {
5444            contended_cpus.contains(cpu)
5445                || cpu_states
5446                    .get(cpu)
5447                    .is_some_and(|state| state.exclusive_held)
5448        });
5449        let mut registry_cpu_filtered = false;
5450        let eligible_allowed = cpu_eligible_allowed(&allowed, &cpu_states, |cpu| {
5451            if contended_cpus.contains(&cpu) {
5452                return Ok(true);
5453            }
5454            let conflicts = aggregate.conflicts(&protocol::ClaimSet::with_modes(
5455                std::iter::empty(),
5456                [cpu],
5457                FlockMode::Shared,
5458                FlockMode::Shared,
5459            ))?;
5460            registry_cpu_filtered |= conflicts;
5461            Ok(conflicts)
5462        })?;
5463        let registry_claim_filtered = registry_llc_filtered || registry_cpu_filtered;
5464        let real_holder_filtered = real_llc_filtered || real_cpu_filtered;
5465        let dynamic_filtered = registry_claim_filtered || real_holder_filtered;
5466        let static_capacity = snapshots
5467            .iter()
5468            .flat_map(|snapshot| topo.llc_groups[snapshot.llc_idx].cpus.iter().copied())
5469            .filter(|cpu| allowed.contains(cpu))
5470            .collect::<std::collections::BTreeSet<_>>()
5471            .len();
5472        if sizing == LlcPlanSizing::Elastic && static_capacity < target_cpus {
5473            return Err(ResourceContention {
5474                reason: format!(
5475                    "host LLC topology exposes only {static_capacity} distinct CPUs from the \
5476                     process's allowed set, fewer than the elastic build maximum {target_cpus}"
5477                ),
5478            }
5479            .into());
5480        }
5481        let live_capacity = live_cpu_capacity(
5482            sizing,
5483            target_cpus,
5484            &eligible,
5485            topo,
5486            &eligible_allowed,
5487            &cpu_states,
5488        );
5489        let claim_capacity_insufficient = live_capacity.is_none();
5490        let mut selected = if let Some(live_capacity) = &live_capacity {
5491            plan_from_snapshots_with_fresh_rotation(
5492                &eligible,
5493                live_capacity.target,
5494                topo,
5495                &live_capacity.eligible,
5496                |from, to| test_topo.numa_distance(from, to),
5497                llc_policy,
5498                elastic_fresh_rotation,
5499            )
5500        } else {
5501            Vec::new()
5502        };
5503        if selected.is_empty() && !dynamic_filtered {
5504            // Every LLC's CPU set lies outside the allowed cpuset —
5505            // sysfs disagrees with sched_getaffinity. This is a host
5506            // misconfiguration (stale sysfs after hotplug, cgroup
5507            // pinned to a CPU range the kernel no longer reports in
5508            // llc_groups, etc.). Bail with actionable text rather
5509            // than looping through retries that cannot change the
5510            // outcome.
5511            return Err(ResourceContention {
5512                reason: format!(
5513                    "no host LLC overlaps the process's \
5514                     {allowed_cpus}-CPU allowed set — sysfs LLC groups \
5515                     and sched_getaffinity disagree"
5516                ),
5517            }
5518            .into());
5519        }
5520        let selected_materialized = if selected.is_empty() {
5521            None
5522        } else {
5523            materialize_plan_cpus(
5524                &selected,
5525                topo,
5526                &live_capacity
5527                    .as_ref()
5528                    .expect("a non-empty plan must have live capacity")
5529                    .eligible,
5530                &cpu_states,
5531                live_capacity
5532                    .as_ref()
5533                    .expect("a non-empty plan must have live capacity")
5534                    .target,
5535                cpu_policy,
5536            )
5537        };
5538        if !selected.is_empty() && selected_materialized.is_none() {
5539            return Err(ResourceContention {
5540                reason: format!(
5541                    "selected LLCs did not contain the required {} distinct eligible CPUs",
5542                    live_capacity
5543                        .as_ref()
5544                        .expect("a non-empty plan must have live capacity")
5545                        .target,
5546                ),
5547            }
5548            .into());
5549        }
5550        let (mut selected_cpus, mut selected_mems) = selected_materialized.unwrap_or_default();
5551        // Kept past the selection so a queued designation can reuse this
5552        // attempt's permit-scoped snapshot for its grant bias instead of
5553        // taking a second registry read. `None` whenever this attempt named
5554        // no permits at all.
5555        let mut attempt_permit_snapshot = None;
5556        let plan_permit_selection = if selected_cpus.is_empty() {
5557            // Claim-blocked: there is no plan to fund. Every acquisition arm
5558            // below requires a non-empty selection, so selecting permits for a
5559            // zero-width plan only costs a registry snapshot and a full walk of
5560            // the permit pool whose result this attempt cannot use.
5561            None
5562        } else if permit_admission == PermitAdmission::None {
5563            Some(PlanPermitSelection {
5564                permits: VmPermitSelection {
5565                    cpu_permits: Vec::new(),
5566                    memory_permits: Vec::new(),
5567                    admission_class: protocol::AdmissionClass::Ordinary,
5568                },
5569                cpu_width: selected_cpus.len(),
5570            })
5571        } else {
5572            let watch_class = match permit_admission {
5573                // The envelope spans both general and fallback permits. Each
5574                // concrete selection below carries DefaultBorrow only when it
5575                // actually consumes the fallback suffix.
5576                PermitAdmission::Cooperative => protocol::AdmissionClass::Ordinary,
5577                PermitAdmission::Build => protocol::AdmissionClass::Build,
5578                PermitAdmission::None => unreachable!(),
5579            };
5580            let mut watch_permits = permit_pool.all().collect::<Vec<_>>();
5581            if let Some(memory_pool) = memory_pool.as_ref() {
5582                watch_permits.extend_from_slice(&memory_pool.permits);
5583            }
5584            let watch = resource_claim_with_permits(
5585                &[],
5586                LlcLockMode::Shared,
5587                &[],
5588                FlockMode::Shared,
5589                &watch_permits,
5590                watch_class,
5591            );
5592            let permit_snapshot =
5593                attempt_permit_snapshot.insert(protocol::registered_claim_snapshot(&watch)?);
5594            let preparation_owned = preferred_cpu_permits
5595                .iter()
5596                .chain(&preferred_memory_permits)
5597                .copied()
5598                .collect::<std::collections::BTreeSet<_>>();
5599            select_plan_permits_grant_aware(
5600                permit_admission,
5601                sizing,
5602                &permit_pool,
5603                memory_pool.as_ref(),
5604                selected_cpus.len(),
5605                memory_required,
5606                permit_rotation,
5607                memory_rotation,
5608                &preferred_cpu_permits,
5609                &preferred_memory_permits,
5610                |candidate| {
5611                    // The PENDING record contributes these exact permit bits
5612                    // to the machine aggregate. They are this process's
5613                    // already-held OFDs, not external contention; exact probe
5614                    // reuses them and retains any surplus until HELD.
5615                    let Some(external) = claim_without_owned_permits(candidate, &preparation_owned)
5616                    else {
5617                        return Ok(true);
5618                    };
5619                    permit_snapshot.conflicts(&external).map(|busy| !busy)
5620                },
5621                |candidate| {
5622                    // A fast-path acquirer takes its permits outright, so
5623                    // taking one an in-flight grant is counting on kills that
5624                    // grant in the next scan. This snapshot's watch names
5625                    // every pool permit, which is what makes the folded permit
5626                    // indices readable from it.
5627                    let Some(external) = claim_without_owned_permits(candidate, &preparation_owned)
5628                    else {
5629                        return Ok(false);
5630                    };
5631                    permit_snapshot.grant_conflicts(&external)
5632                },
5633            )?
5634        };
5635        if let Some(selection) = plan_permit_selection.as_ref() {
5636            apply_plan_permit_width(sizing, selection, topo, &mut selected, &mut selected_cpus);
5637            selected_mems = plan_mems(&selected_cpus, topo);
5638        }
5639        let permit_selection = plan_permit_selection.map(|selection| selection.permits);
5640        if !wait && let Some(pending) = pending.take() {
5641            let activated = protocol::try_activate_pending_once(pending, |probe| {
5642                let Some(permit_selection) = permit_selection.as_ref() else {
5643                    return Ok(None);
5644                };
5645                if selected.is_empty() {
5646                    return Ok(None);
5647                }
5648                let all_permits = permit_selection.all_permits();
5649                let exact = resource_claim_with_permits(
5650                    &selected,
5651                    LlcLockMode::Shared,
5652                    &selected_cpus,
5653                    FlockMode::Shared,
5654                    &all_permits,
5655                    permit_selection.admission_class,
5656                );
5657                let reusable = probe.clone_reusable_permits()?;
5658                let locks = probe.try_acquire(&exact, || {
5659                    if permit_admission == PermitAdmission::None {
5660                        Ok(llc_attempt_into_probe(
5661                            acquire_fn(&selected, &selected_cpus, &snapshots)?
5662                                .into_llc_lock_attempt(),
5663                            |locks| locks,
5664                        ))
5665                    } else {
5666                        acquire_resources_with_permits_granted_reusing(
5667                            &selected,
5668                            LlcLockMode::Shared,
5669                            &selected_cpus,
5670                            FlockMode::Shared,
5671                            &all_permits,
5672                            &reusable,
5673                        )
5674                    }
5675                })?;
5676                Ok(locks.map(|locks| {
5677                    (
5678                        exact,
5679                        (
5680                            selected.clone(),
5681                            locks,
5682                            selected_cpus.clone(),
5683                            permit_selection.cpu_permits.clone(),
5684                            selected_mems.clone(),
5685                        ),
5686                    )
5687                }))
5688            })?;
5689            return match activated {
5690                Some(acquired) => {
5691                    let ((selected, cpus, cpu_permits, mems), locks) =
5692                        acquired.split_map(|(selected, locks, cpus, cpu_permits, mems)| {
5693                            ((selected, cpus, cpu_permits, mems), locks)
5694                        });
5695                    Ok(materialize_llc_plan(
5696                        selected,
5697                        locks,
5698                        cpus,
5699                        cpu_permits,
5700                        mems,
5701                    ))
5702                }
5703                None => Err(ResourceContention {
5704                    reason: format!("no {target_cpus}-CPU LLC placement was immediately available"),
5705                }
5706                .into()),
5707            };
5708        }
5709        if pending.is_some() {
5710            // The pre-exec wrapper already owns its bounded CPU/memory/token
5711            // permits and one physical CPU-SH claim. Do not create a second
5712            // fast-path owner: preserve this discovery only as the queue seed,
5713            // then atomically replace that preparation footprint with the
5714            // complete topology + CPU + memory claim in the same record below.
5715            queue_seed_snapshots = Some(snapshots);
5716            queue_seed_cpu_states = Some(cpu_states);
5717            queue_seed_universe = Some(allowed.clone());
5718            queue_seed_permit_snapshot = attempt_permit_snapshot;
5719            break;
5720        }
5721        let mut registry_fenced = false;
5722        let acquired = if let Some(permit_selection) = permit_selection.as_ref()
5723            && !selected.is_empty()
5724        {
5725            let all_permits = permit_selection.all_permits();
5726            let exact = resource_claim_with_permits(
5727                &selected,
5728                LlcLockMode::Shared,
5729                &selected_cpus,
5730                FlockMode::Shared,
5731                &all_permits,
5732                permit_selection.admission_class,
5733            );
5734            match protocol::with_registry_fence(&exact, || -> Result<LlcLockAttempt> {
5735                if permit_admission == PermitAdmission::None {
5736                    Ok(acquire_fn(&selected, &selected_cpus, &snapshots)?.into_llc_lock_attempt())
5737                } else {
5738                    Ok(acquire_resources_with_permits_granted(
5739                        &selected,
5740                        LlcLockMode::Shared,
5741                        &selected_cpus,
5742                        FlockMode::Shared,
5743                        &all_permits,
5744                    )?
5745                    .into_llc_lock_attempt())
5746                }
5747            })
5748            .map_err(|e| ResourceContention {
5749                reason: format!("acquire LLC and CPU locks: {e}"),
5750            })? {
5751                protocol::RegistryFence::Fenced => {
5752                    registry_fenced = true;
5753                    None
5754                }
5755                protocol::RegistryFence::Ran { value: outcome, .. } => match outcome
5756                    .into_llc_lock_attempt()
5757                {
5758                    LlcLockAttempt::Acquired(locks) => {
5759                        Some(protocol::publish_acquired(&exact, locks).map_err(|error| {
5760                            ResourceContention {
5761                                reason: format!("publish acquired LLC reservation state: {error}"),
5762                            }
5763                        })?)
5764                    }
5765                    LlcLockAttempt::Contended(evidence) => {
5766                        contention.insert(evidence);
5767                        None
5768                    }
5769                    #[cfg(test)]
5770                    LlcLockAttempt::Unavailable => None,
5771                },
5772            }
5773        } else {
5774            // Claim-blocked: bounce without touching any lockfile.
5775            None
5776        };
5777        if let Some(locks) = acquired {
5778            let plan = materialize_llc_plan(
5779                selected,
5780                locks,
5781                selected_cpus,
5782                permit_selection
5783                    .expect("successful acquisition has permit selection")
5784                    .cpu_permits,
5785                selected_mems,
5786            );
5787            return Ok(plan);
5788        }
5789        if !wait
5790            && (registry_fenced
5791                || (claim_capacity_insufficient
5792                    && registry_claim_filtered
5793                    && !real_holder_filtered))
5794        {
5795            return Err(anyhow::Error::new(ResourceContention {
5796                reason: format!(
5797                    "registered reservation claims currently cover capacity needed for a {target_cpus}-CPU LLC plan"
5798                ),
5799            }));
5800        }
5801        if wait {
5802            // The registry is the retry mechanism for blocking callers. Join
5803            // immediately instead of multiplying an already-observed
5804            // contention event into four procfs scans and backoff sleeps.
5805            queue_seed_snapshots = Some(snapshots);
5806            queue_seed_cpu_states = Some(cpu_states);
5807            // The queued designation and immutable watch must cover a valid
5808            // full-budget candidate from the static topology. Live
5809            // exclusions are transient contention; seeding from them could
5810            // create an empty/short claim precisely when waiting is needed.
5811            queue_seed_universe = Some(allowed.clone());
5812            queue_seed_permit_snapshot = attempt_permit_snapshot;
5813            break;
5814        }
5815        if attempt >= ACQUIRE_MAX_TOCTOU_RETRIES {
5816            break;
5817        }
5818        // Short backoff between fast-phase attempts so a racing peer
5819        // has time to drop its fds before the next DISCOVER.
5820        std::thread::sleep(TOCTOU_RETRY_DELAYS[attempt as usize]);
5821        check_acquire_cancelled(cancelled)?;
5822        attempt = attempt.saturating_add(1);
5823    }
5824
5825    if !wait {
5826        // Name the contended LLCs WITHOUT a host-global `/proc/locks` walk.
5827        // That seq-file read is O(host-wide flocks): a ~12k-entry `/proc/locks`
5828        // costs ~7ms to read alone but ~180ms+ under concurrent readers because
5829        // it serializes on the kernel lock-table lock, so under a many-lane
5830        // flock storm every such diagnostic read poisons every peer's flock
5831        // ops. Instead probe only the contended LLC lock files with a
5832        // non-blocking flock: `None` means a peer holds it, `Some(fd)` means it
5833        // is free (the transient probe fd is released immediately by RAII, so a
5834        // free LLC is never held open). This is O(contended-LLCs) syscalls with
5835        // no seq-file walk; holder identity moves to the `ktstr locks --json`
5836        // pointer, and exact flock acquisition above stays authoritative.
5837        let diag_timer = crate::vmm::grant_flow::enabled().then(std::time::Instant::now);
5838        let contended_llcs = contention
5839            .marker_vec()
5840            .into_iter()
5841            .filter_map(|marker| match marker.blocker {
5842                protocol::ResourceKey::Llc(llc) => Some(llc),
5843                protocol::ResourceKey::Cpu(_) | protocol::ResourceKey::Permit(_) => None,
5844            })
5845            .collect::<std::collections::BTreeSet<_>>();
5846        let held_llcs = contended_llcs
5847            .into_iter()
5848            .filter(|&llc| {
5849                // A held LLC rejects a non-blocking EX probe (`None`); a free
5850                // one is momentarily acquired and released as the fd drops. A
5851                // probe error is treated as "not observably held".
5852                crate::flock::try_flock(
5853                    std::path::Path::new(&llc_lock_path(llc)),
5854                    FlockMode::Exclusive,
5855                )
5856                .map(|acquired| acquired.is_none())
5857                .unwrap_or(false)
5858            })
5859            .map(|llc| format!("LLC {llc}"))
5860            .collect::<Vec<_>>();
5861        if let Some(timer) = diag_timer {
5862            let elapsed_ns = timer.elapsed().as_nanos().try_into().unwrap_or(u64::MAX);
5863            crate::vmm::grant_flow::note_discover(elapsed_ns);
5864        }
5865        let holder_text = if held_llcs.is_empty() {
5866            "<none currently held>".to_string()
5867        } else {
5868            format!("{} held", held_llcs.join(", "))
5869        };
5870        return Err(anyhow::Error::new(ResourceContention {
5871            reason: format!(
5872                "acquire_llc_plan: could not reserve {target_cpus} \
5873                 CPU(s) after {attempts} attempts; contended: \
5874                 {holder_text}. Run `ktstr locks --json` to see \
5875                 every ktstr lock on this host.",
5876                attempts = ACQUIRE_MAX_TOCTOU_RETRIES + 1,
5877            ),
5878        }));
5879    }
5880
5881    // ---- WAIT PHASE: register, then re-plan on every coordinator wake (see
5882    // `protocol`). Every target probe remains all-or-nothing: the exact claim
5883    // stays published while an incomplete attempt releases its real flocks.
5884    check_acquire_cancelled(cancelled)?;
5885    let queued_snapshots = queue_seed_snapshots
5886        .expect("waiting acquisition must preserve its failed fast-phase snapshot");
5887    let queued_cpu_states = queue_seed_cpu_states
5888        .expect("waiting acquisition must preserve its failed fast-phase CPU snapshot");
5889    let queued_allowed = queue_seed_universe
5890        .expect("waiting acquisition must preserve its full static CPU universe");
5891    let queued_target_cpus = sizing.queued_target(target_cpus);
5892    let queued_capacity = live_cpu_capacity(
5893        sizing,
5894        queued_target_cpus,
5895        &queued_snapshots,
5896        topo,
5897        &queued_allowed,
5898        &queued_cpu_states,
5899    )
5900    .expect("a statically valid queued designation must have CPU capacity");
5901    let mut queued_selected = plan_from_snapshots_with_fresh_rotation(
5902        &queued_snapshots,
5903        queued_capacity.target,
5904        topo,
5905        &queued_capacity.eligible,
5906        |from, to| test_topo.numa_distance(from, to),
5907        llc_policy,
5908        elastic_fresh_rotation,
5909    );
5910    if queued_selected.is_empty() {
5911        return Err(ResourceContention {
5912            reason: format!(
5913                "no host LLC overlaps the process's {allowed_cpus}-CPU \
5914                 allowed set — sysfs LLC groups and sched_getaffinity disagree"
5915            ),
5916        }
5917        .into());
5918    }
5919    let Some((mut queued_cpus, _)) = materialize_plan_cpus(
5920        &queued_selected,
5921        topo,
5922        &queued_capacity.eligible,
5923        &queued_cpu_states,
5924        queued_capacity.target,
5925        cpu_policy,
5926    ) else {
5927        return Err(ResourceContention {
5928            reason: format!(
5929                "host LLC topology contains fewer than the required {queued_target_cpus} distinct allowed CPUs"
5930            ),
5931        }
5932        .into());
5933    };
5934    // Exact queue designations intentionally name a complete canonical permit
5935    // set even while it is busy. Elastic build permits are only a preferred
5936    // parallelism budget, so seed their designation from live registry state
5937    // and use the serial fallback instead of queuing behind a saturated pool.
5938    let queued_permit_snapshot =
5939        if sizing == LlcPlanSizing::Elastic && permit_admission == PermitAdmission::Build {
5940            let watch = resource_claim_with_permits(
5941                &[],
5942                LlcLockMode::Shared,
5943                &[],
5944                FlockMode::Shared,
5945                &permit_pool.all().collect::<Vec<_>>(),
5946                protocol::AdmissionClass::Build,
5947            );
5948            Some(protocol::registered_claim_snapshot(&watch)?)
5949        } else {
5950            None
5951        };
5952    let preparation_owned = preferred_cpu_permits
5953        .iter()
5954        .chain(&preferred_memory_permits)
5955        .copied()
5956        .collect::<std::collections::BTreeSet<_>>();
5957    // This designation is the exact claim the authoritative scan later hands
5958    // this ticket as its grant, and the fence every junior behind it must
5959    // clear once that grant lands. Naming a permit some junior's in-flight
5960    // grant is already counting on therefore resolves as a ticket-order
5961    // revocation of that junior. Bias away from the charged permits, reading
5962    // the charge from the failed fast attempt's permit-scoped snapshot: no
5963    // extra registry read, and a stale bias cannot make a designation
5964    // invalid because the width and admission class do not depend on it.
5965    let queued_plan_permits = select_plan_permits_grant_aware(
5966        permit_admission,
5967        sizing,
5968        &permit_pool,
5969        memory_pool.as_ref(),
5970        queued_cpus.len(),
5971        memory_required,
5972        permit_rotation,
5973        memory_rotation,
5974        &preferred_cpu_permits,
5975        &preferred_memory_permits,
5976        |candidate| {
5977            let Some(snapshot) = queued_permit_snapshot.as_ref() else {
5978                return Ok(true);
5979            };
5980            let Some(external) = claim_without_owned_permits(candidate, &preparation_owned) else {
5981                return Ok(true);
5982            };
5983            snapshot.conflicts(&external).map(|busy| !busy)
5984        },
5985        |candidate| {
5986            let Some(snapshot) = queue_seed_permit_snapshot.as_ref() else {
5987                return Ok(false);
5988            };
5989            let Some(external) = claim_without_owned_permits(candidate, &preparation_owned) else {
5990                return Ok(false);
5991            };
5992            snapshot.grant_conflicts(&external)
5993        },
5994    )?
5995    .expect("a non-empty host permit pool must seed a queued designation");
5996    apply_plan_permit_width(
5997        sizing,
5998        &queued_plan_permits,
5999        topo,
6000        &mut queued_selected,
6001        &mut queued_cpus,
6002    );
6003    let queued_permits = queued_plan_permits.permits;
6004    let queued_all_permits = queued_permits.all_permits();
6005    let queued_claim = resource_claim_with_permits(
6006        &queued_selected,
6007        LlcLockMode::Shared,
6008        &queued_cpus,
6009        FlockMode::Shared,
6010        &queued_all_permits,
6011        queued_permits.admission_class,
6012    );
6013    // Watch the immutable static resource universe for releases, while
6014    // fencing successors with only the exact plan currently designated in
6015    // the registry. A transiently busy resource must remain in the watch or
6016    // its release cannot wake this ticket.
6017    let watch_class = match permit_admission {
6018        PermitAdmission::None => protocol::AdmissionClass::Ordinary,
6019        // Candidate claims, not the broad immutable watch, decide whether the
6020        // selected set actually borrows build-reserved cooperative capacity.
6021        PermitAdmission::Cooperative => protocol::AdmissionClass::Ordinary,
6022        PermitAdmission::Build => protocol::AdmissionClass::Build,
6023    };
6024    let mut watch_permits = if permit_admission == PermitAdmission::None {
6025        Vec::new()
6026    } else {
6027        permit_pool.all().collect::<Vec<_>>()
6028    };
6029    if let Some(memory_pool) = memory_pool.as_ref() {
6030        watch_permits.extend_from_slice(&memory_pool.permits);
6031    }
6032    let queued_watch = resource_claim_with_permits(
6033        &queued_snapshots
6034            .iter()
6035            .map(|snapshot| snapshot.llc_idx)
6036            .collect::<Vec<_>>(),
6037        LlcLockMode::Shared,
6038        &allowed.iter().copied().collect::<Vec<_>>(),
6039        FlockMode::Shared,
6040        &watch_permits,
6041        watch_class,
6042    );
6043    let register = |probe: &mut protocol::GrantedProbe| {
6044        let (mut snapshots, cpu_states, _) = discover_registered_placement_states(topo, &allowed)
6045            .map_err(|e| ResourceContention {
6046            reason: format!("discover registered placement state while queued: {e}"),
6047        })?;
6048        let static_capacity = snapshots
6049            .iter()
6050            .flat_map(|snapshot| topo.llc_groups[snapshot.llc_idx].cpus.iter().copied())
6051            .filter(|cpu| allowed.contains(cpu))
6052            .collect::<std::collections::BTreeSet<_>>()
6053            .len();
6054        if static_capacity < target_cpus {
6055            return Err(ResourceContention {
6056                reason: format!(
6057                    "host LLC topology exposes only {static_capacity} distinct CPUs from the process's allowed set, fewer than the required {target_cpus}"
6058                ),
6059            }
6060            .into());
6061        }
6062        let designated = probe.designated().clone();
6063        let reusable_permits = probe.clone_reusable_permits()?;
6064        let selected: Vec<usize> = designated.llcs.iter().copied().collect();
6065        let cpus: Vec<usize> = designated.cpus.iter().copied().collect();
6066        let permits: Vec<usize> = designated.permits.iter().copied().collect();
6067        let (cpu_permits, _) = split_vm_permits(permits.iter().copied(), memory_pool.as_ref());
6068        let designated_is_live = selected
6069            .iter()
6070            .all(|idx| snapshots.iter().any(|snapshot| snapshot.llc_idx == *idx));
6071        if sizing == LlcPlanSizing::Exact
6072            && designated_is_live
6073            && let Some(acquired) = probe.try_acquire(&designated, || {
6074                Ok(llc_attempt_into_probe(
6075                    if permit_admission == PermitAdmission::None {
6076                        try_acquire_llc_plan_locks_with_evidence(&selected, &cpus, &snapshots)?
6077                    } else {
6078                        acquire_resources_with_permits_granted_reusing(
6079                            &selected,
6080                            LlcLockMode::Shared,
6081                            &cpus,
6082                            FlockMode::Shared,
6083                            &permits,
6084                            &reusable_permits,
6085                        )?
6086                        .into_llc_lock_attempt()
6087                    },
6088                    |locks| (selected.clone(), locks, cpus.clone(), cpu_permits.clone()),
6089                ))
6090            })?
6091        {
6092            return Ok(Some(acquired));
6093        }
6094
6095        // `/proc/locks` shows only real flock holders. An earlier queue
6096        // ticket may reserve an LLC without holding that flock yet, so a
6097        // holder-only replan would repeatedly choose the same unavailable
6098        // LLC while disjoint capacity sits idle. Exclude conflicting prefix
6099        // claims before either policy scores the snapshot when the remaining
6100        // capacity can carry the full budget; otherwise retain them as the
6101        // necessary last resort.
6102        let eligible_allowed = cpu_eligible_allowed(&allowed, &cpu_states, |cpu| {
6103            probe.conflicts_with_predecessors(&physical_candidate_for_watch(
6104                std::iter::empty(),
6105                [cpu],
6106                FlockMode::Shared,
6107                FlockMode::Shared,
6108                watch_class,
6109            ))
6110        })?;
6111        snapshots.retain(|snapshot| !snapshot.exclusive_held);
6112        snapshots = match sizing {
6113            LlcPlanSizing::Exact => avoid_preceding_claims_when_possible(
6114                &snapshots,
6115                target_cpus,
6116                topo,
6117                &eligible_allowed,
6118                watch_class,
6119                |candidate| probe.conflicts_with_predecessors(candidate),
6120            )?,
6121            LlcPlanSizing::Elastic => {
6122                let mut predecessor_free = Vec::with_capacity(snapshots.len());
6123                for snapshot in snapshots {
6124                    let candidate = physical_candidate_for_watch(
6125                        [snapshot.llc_idx],
6126                        std::iter::empty(),
6127                        FlockMode::Shared,
6128                        FlockMode::Shared,
6129                        watch_class,
6130                    );
6131                    if !probe.conflicts_with_predecessors(&candidate)? {
6132                        predecessor_free.push(snapshot);
6133                    }
6134                }
6135                predecessor_free
6136            }
6137        };
6138        let Some(live_capacity) = live_cpu_capacity(
6139            sizing,
6140            target_cpus,
6141            &snapshots,
6142            topo,
6143            &eligible_allowed,
6144            &cpu_states,
6145        ) else {
6146            // The full immutable watch covers every resource that can make
6147            // this elastic ticket runnable; no speculative physical probe is
6148            // needed while the live/registry snapshot exposes zero capacity.
6149            return Ok(None);
6150        };
6151        let mut next_selected = plan_from_snapshots_with_fresh_rotation(
6152            &snapshots,
6153            live_capacity.target,
6154            topo,
6155            &live_capacity.eligible,
6156            |from, to| test_topo.numa_distance(from, to),
6157            llc_policy,
6158            elastic_fresh_rotation,
6159        );
6160        if next_selected.is_empty() {
6161            // Every statically valid alternative is temporarily excluded by
6162            // a real EX holder or an earlier exact claim. Keep the designated
6163            // reservation; the contention evidence recorded by its probe
6164            // routes the relevant release serial back to this ticket.
6165            return Ok(None);
6166        }
6167        let Some((mut next_cpus, _)) = materialize_plan_cpus(
6168            &next_selected,
6169            topo,
6170            &live_capacity.eligible,
6171            &cpu_states,
6172            live_capacity.target,
6173            cpu_policy,
6174        ) else {
6175            // The ready subset lost capacity between planning dimensions.
6176            // This is transient contention, not a malformed static topology.
6177            return Ok(None);
6178        };
6179        let Some(next_plan_permits) = select_plan_permits_grant_aware(
6180            permit_admission,
6181            sizing,
6182            &permit_pool,
6183            memory_pool.as_ref(),
6184            next_cpus.len(),
6185            memory_required,
6186            permit_rotation,
6187            memory_rotation,
6188            &preferred_cpu_permits,
6189            &preferred_memory_permits,
6190            |candidate| probe.candidate_ready(candidate),
6191            |candidate| probe.grant_conflicts(candidate),
6192        )?
6193        else {
6194            return Ok(None);
6195        };
6196        apply_plan_permit_width(
6197            sizing,
6198            &next_plan_permits,
6199            topo,
6200            &mut next_selected,
6201            &mut next_cpus,
6202        );
6203        let next_permits = next_plan_permits.permits;
6204        let next_all_permits = next_permits.all_permits();
6205        let next_claim = resource_claim_with_permits(
6206            &next_selected,
6207            LlcLockMode::Shared,
6208            &next_cpus,
6209            FlockMode::Shared,
6210            &next_all_permits,
6211            next_permits.admission_class,
6212        );
6213        if sizing == LlcPlanSizing::Elastic
6214            && next_claim == designated
6215            && designated_is_live
6216            && let Some(acquired) = probe.try_acquire(&designated, || {
6217                Ok(llc_attempt_into_probe(
6218                    if permit_admission == PermitAdmission::None {
6219                        try_acquire_llc_plan_locks_with_evidence(
6220                            &next_selected,
6221                            &next_cpus,
6222                            &snapshots,
6223                        )?
6224                    } else {
6225                        acquire_resources_with_permits_granted_reusing(
6226                            &next_selected,
6227                            LlcLockMode::Shared,
6228                            &next_cpus,
6229                            FlockMode::Shared,
6230                            &next_all_permits,
6231                            &reusable_permits,
6232                        )?
6233                        .into_llc_lock_attempt()
6234                    },
6235                    |locks| {
6236                        (
6237                            next_selected.clone(),
6238                            locks,
6239                            next_cpus.clone(),
6240                            next_permits.cpu_permits.clone(),
6241                        )
6242                    },
6243                ))
6244            })?
6245        {
6246            return Ok(Some(acquired));
6247        }
6248        probe.reserve(&next_claim)?;
6249        Ok(None)
6250    };
6251    let coordinator_seed_claim = queued_claim.clone();
6252    let ticket = if let Some(pending) = pending.take() {
6253        protocol::activate_pending_ticket(pending, queued_claim, queued_watch, cancelled, register)?
6254    } else if contention.is_empty() {
6255        protocol::register_ticket_or_acquire(queued_claim, queued_watch, cancelled, register)?
6256    } else {
6257        protocol::register_ticket_after_contentions(
6258            queued_claim,
6259            queued_watch,
6260            contention,
6261            cancelled,
6262            register,
6263        )?
6264    };
6265    let coordinator = match ticket {
6266        protocol::TicketWork::Acquired(acquired) => {
6267            let ((selected, cpus, cpu_permits), locks) =
6268                acquired.split_map(|(selected, locks, cpus, cpu_permits)| {
6269                    ((selected, cpus, cpu_permits), locks)
6270                });
6271            let mems = plan_mems(&cpus, topo);
6272            let plan = materialize_llc_plan(selected, locks, cpus, cpu_permits, mems);
6273            return Ok(plan);
6274        }
6275        protocol::TicketWork::Coordinator(coordinator) => coordinator,
6276    };
6277    let mut coordinator_claim = coordinator_seed_claim;
6278    let step = |held: &mut protocol::HeldLocks| {
6279        on_coordinator_step();
6280        // RE-PLAN against live holder state on every wake — plans are
6281        // never cached across waits. The freed capacity may satisfy a
6282        // different selection than the one that was busy last wake.
6283        let (snapshots, cpu_states, _) = discover_registered_placement_states(topo, &allowed)
6284            .map_err(|e| ResourceContention {
6285                reason: format!("discover registered placement state: {e}"),
6286            })?;
6287        let static_capacity = snapshots
6288            .iter()
6289            .flat_map(|snapshot| topo.llc_groups[snapshot.llc_idx].cpus.iter().copied())
6290            .filter(|cpu| allowed.contains(cpu))
6291            .collect::<std::collections::BTreeSet<_>>()
6292            .len();
6293        if static_capacity < target_cpus {
6294            return Ok(protocol::CoordinatorStep::Abort {
6295                reason: format!(
6296                    "host LLC topology exposes only {static_capacity} distinct CPUs from the process's allowed set, fewer than the required {target_cpus}"
6297                ),
6298            });
6299        }
6300        let eligible_allowed = cpu_eligible_allowed(&allowed, &cpu_states, |cpu| match sizing {
6301            LlcPlanSizing::Exact => Ok(false),
6302            LlcPlanSizing::Elastic => held
6303                .candidate_ready(&physical_candidate_for_watch(
6304                    std::iter::empty(),
6305                    [cpu],
6306                    FlockMode::Shared,
6307                    FlockMode::Shared,
6308                    watch_class,
6309                ))
6310                .map(|ready| !ready),
6311        })?;
6312        let mut ready_snapshots: Vec<_> = snapshots
6313            .iter()
6314            .filter(|snapshot| !snapshot.exclusive_held)
6315            .cloned()
6316            .collect();
6317        if sizing == LlcPlanSizing::Elastic {
6318            let mut predecessor_free = Vec::with_capacity(ready_snapshots.len());
6319            for snapshot in ready_snapshots {
6320                let candidate = physical_candidate_for_watch(
6321                    [snapshot.llc_idx],
6322                    std::iter::empty(),
6323                    FlockMode::Shared,
6324                    FlockMode::Shared,
6325                    watch_class,
6326                );
6327                if held.candidate_ready(&candidate)? {
6328                    predecessor_free.push(snapshot);
6329                }
6330            }
6331            ready_snapshots = predecessor_free;
6332        }
6333        if let Some(live_capacity) = live_cpu_capacity(
6334            sizing,
6335            target_cpus,
6336            &ready_snapshots,
6337            topo,
6338            &eligible_allowed,
6339            &cpu_states,
6340        ) {
6341            let mut selected = plan_from_snapshots_with_fresh_rotation(
6342                &ready_snapshots,
6343                live_capacity.target,
6344                topo,
6345                &live_capacity.eligible,
6346                |from, to| test_topo.numa_distance(from, to),
6347                llc_policy,
6348                elastic_fresh_rotation,
6349            );
6350            if let Some((mut cpus, _)) = materialize_plan_cpus(
6351                &selected,
6352                topo,
6353                &live_capacity.eligible,
6354                &cpu_states,
6355                live_capacity.target,
6356                cpu_policy,
6357            ) && let Some(plan_permits) = select_plan_permits_grant_aware(
6358                permit_admission,
6359                sizing,
6360                &permit_pool,
6361                memory_pool.as_ref(),
6362                cpus.len(),
6363                memory_required,
6364                permit_rotation,
6365                memory_rotation,
6366                &preferred_cpu_permits,
6367                &preferred_memory_permits,
6368                |candidate| held.candidate_ready(candidate),
6369                |candidate| held.grant_conflicts(candidate),
6370            )? {
6371                apply_plan_permit_width(sizing, &plan_permits, topo, &mut selected, &mut cpus);
6372                let permits = plan_permits.permits;
6373                let all_permits = permits.all_permits();
6374                coordinator_claim = resource_claim_with_permits(
6375                    &selected,
6376                    LlcLockMode::Shared,
6377                    &cpus,
6378                    FlockMode::Shared,
6379                    &all_permits,
6380                    permits.admission_class,
6381                );
6382            }
6383        }
6384        // If real EX holders leave no full ready alternative, retain the
6385        // previous exact designation and probe it. The resulting contention
6386        // evidence selects the blocker serial that wakes this coordinator;
6387        // temporary scarcity is never a terminal topology error.
6388        let selected: Vec<usize> = coordinator_claim.llcs.iter().copied().collect();
6389        let cpus: Vec<usize> = coordinator_claim.cpus.iter().copied().collect();
6390        let permits: Vec<usize> = coordinator_claim.permits.iter().copied().collect();
6391        let (cpu_permits, _) = split_vm_permits(permits.iter().copied(), memory_pool.as_ref());
6392        match sizing {
6393            LlcPlanSizing::Exact => debug_assert_eq!(cpus.len(), target_cpus),
6394            LlcPlanSizing::Elastic => {
6395                debug_assert!(!cpus.is_empty() && cpus.len() <= target_cpus)
6396            }
6397        }
6398        let mems = plan_mems(&cpus, topo);
6399        let target = protocol::canonical_lock_order_with_permits(
6400            &selected,
6401            FlockMode::Shared,
6402            &cpus,
6403            FlockMode::Shared,
6404            &permits,
6405        );
6406        if let Some(locks) = held.probe_complete_if_ready(&coordinator_claim, &target)? {
6407            Ok(protocol::CoordinatorStep::Complete {
6408                claim: coordinator_claim.clone(),
6409                value: (selected, locks, cpus, cpu_permits, mems),
6410            })
6411        } else {
6412            Ok(protocol::CoordinatorStep::Waiting {
6413                claim: coordinator_claim.clone(),
6414            })
6415        }
6416    };
6417    let acquired = protocol::finish_run_coordinator(coordinator, cancelled, step, "LLC-plan")?;
6418    let ((selected, cpus, cpu_permits, mems), locks) =
6419        acquired.split_map(|(selected, locks, cpus, cpu_permits, mems)| {
6420            ((selected, cpus, cpu_permits, mems), locks)
6421        });
6422    Ok(materialize_llc_plan(
6423        selected,
6424        locks,
6425        cpus,
6426        cpu_permits,
6427        mems,
6428    ))
6429}
6430
6431/// Static, ownership-free shape planner for no-perf builds.
6432///
6433/// This path consults only the cached host topology, the calling process's
6434/// allowed cpuset, and the NUMA distance matrix. It performs no registry read,
6435/// lockfile materialization, `/proc/locks` scan, or flock attempt. Live holder
6436/// state is intentionally irrelevant: the resulting plan sizes diagnostics
6437/// and other build-time metadata, while the run-time replan performs
6438/// authoritative admission after immutable preparation.
6439///
6440/// The returned plan's `locks` is empty by construction.
6441pub fn plan_llc_selection_only(
6442    topo: &HostTopology,
6443    test_topo: &crate::topology::TestTopology,
6444    cpu_cap: Option<CpuCap>,
6445    policy: PlacementPolicy,
6446) -> Result<LlcPlan> {
6447    if crate::cargo_test_mode::cargo_test_mode_active() {
6448        let _ = test_topo;
6449        let _ = cpu_cap;
6450        return cargo_test_mode_llc_plan(topo);
6451    }
6452    let allowed_vec = host_allowed_cpus();
6453    if allowed_vec.is_empty() {
6454        return Err(ResourceContention {
6455            reason: "could not determine allowed CPU set \
6456                     (sched_getaffinity and /proc/self/status both failed)"
6457                .into(),
6458        }
6459        .into());
6460    }
6461    let allowed: std::collections::BTreeSet<usize> = allowed_vec.iter().copied().collect();
6462    let target_cpus = match cpu_cap {
6463        Some(cap) => cap.effective_count(allowed.len())?,
6464        None => default_cpu_budget(allowed.len()),
6465    };
6466    let snapshots: Vec<_> = topo
6467        .llc_groups
6468        .iter()
6469        .enumerate()
6470        .filter(|(_, group)| group.cpus.iter().any(|cpu| allowed.contains(cpu)))
6471        .map(|(llc_idx, _)| LlcSnapshot {
6472            llc_idx,
6473            holder_count: 0,
6474            exclusive_held: false,
6475            granted_count: 0,
6476        })
6477        .collect();
6478    if snapshots.is_empty() {
6479        return Err(ResourceContention {
6480            reason: format!(
6481                "no host LLC overlaps the process's {}-CPU allowed set — sysfs LLC groups and sched_getaffinity disagree",
6482                allowed.len()
6483            ),
6484        }
6485        .into());
6486    }
6487    let cpu_states = allowed
6488        .iter()
6489        .copied()
6490        .map(|cpu| (cpu, CpuPlacementState::default()))
6491        .collect::<std::collections::BTreeMap<_, _>>();
6492    let selected = plan_from_snapshots(
6493        &snapshots,
6494        target_cpus,
6495        topo,
6496        &allowed,
6497        |from, to| test_topo.numa_distance(from, to),
6498        policy,
6499    );
6500    let materialized = materialize_plan_cpus(
6501        &selected,
6502        topo,
6503        &allowed,
6504        &cpu_states,
6505        target_cpus,
6506        CpuSelectionPolicy::WithinEachLlc(policy),
6507    );
6508    let Some((cpus, mems)) = materialized else {
6509        return Err(ResourceContention {
6510            reason: format!(
6511                "host LLC topology contains fewer than the required {target_cpus} distinct CPUs from the process's {}-CPU allowed set",
6512                allowed.len()
6513            ),
6514        }
6515        .into());
6516    };
6517    Ok(materialize_llc_plan(
6518        selected,
6519        protocol::Acquired::untracked(Vec::new()),
6520        cpus,
6521        Vec::new(),
6522        mems,
6523    ))
6524}
6525
6526/// Per-CPU discover state for one allowed host CPU, derived alongside
6527/// [`LlcSnapshot`] from the same registry aggregate.
6528#[derive(Debug, Clone, Copy, Default)]
6529struct CpuPlacementState {
6530    exclusive_held: bool,
6531    other_holders: usize,
6532    /// In-flight grant charge on this CPU. Subordinate rank key only (fixed
6533    /// ASC sign under both policies) — never folded into `other_holders`,
6534    /// the unshared filter, or the eligibility skip.
6535    granted_holders: usize,
6536}
6537
6538/// Resolve one admission turn's CPU width from the current placement image.
6539///
6540/// Exact VM reservations retain their fixed-capacity contract. Elastic build
6541/// reservations first consume the currently unshared capacity visible through
6542/// the selected LLC candidates. That keeps a compile storm's aggregate
6543/// parallelism tied to real idle capacity instead of giving every process the
6544/// full maximum immediately. If no compatible CPU is unshared, the existing
6545/// SH-compatible capacity is deliberately retained as a fallback: default,
6546/// no-perf, and build reservations are cooperative, and must still make
6547/// progress while the host is fully occupied by other cooperative ktstr work.
6548///
6549/// The effective set accompanies the width. While any unshared CPU exists,
6550/// both LLC selection and CPU materialization see only those CPUs, so a
6551/// heavily shared LLC cannot hide a disjoint idle LLC merely because
6552/// Consolidate ranks its LLC holder count first. Once the unshared set is
6553/// empty, the effective set becomes every SH-compatible CPU.
6554struct LiveCpuCapacity {
6555    target: usize,
6556    eligible: std::collections::BTreeSet<usize>,
6557}
6558
6559fn live_cpu_capacity(
6560    sizing: LlcPlanSizing,
6561    maximum: usize,
6562    snapshots: &[LlcSnapshot],
6563    topo: &HostTopology,
6564    compatible: &std::collections::BTreeSet<usize>,
6565    states: &std::collections::BTreeMap<usize, CpuPlacementState>,
6566) -> Option<LiveCpuCapacity> {
6567    let snapshot_cpus = snapshots
6568        .iter()
6569        .flat_map(|snapshot| topo.llc_groups[snapshot.llc_idx].cpus.iter().copied())
6570        .collect::<std::collections::BTreeSet<_>>();
6571    let compatible = compatible
6572        .intersection(&snapshot_cpus)
6573        .copied()
6574        .collect::<std::collections::BTreeSet<_>>();
6575    let compatible_capacity = compatible.len();
6576    if sizing == LlcPlanSizing::Elastic {
6577        let unshared = compatible
6578            .iter()
6579            .copied()
6580            .filter(|cpu| states.get(cpu).is_none_or(|state| state.other_holders == 0))
6581            .collect::<std::collections::BTreeSet<_>>();
6582        let unshared_capacity = unshared.len();
6583        if unshared_capacity > 0 {
6584            return sizing
6585                .target_for_capacity(maximum, unshared_capacity)
6586                .map(|target| LiveCpuCapacity {
6587                    target,
6588                    eligible: unshared,
6589                });
6590        }
6591    }
6592    sizing
6593        .target_for_capacity(maximum, compatible_capacity)
6594        .map(|target| LiveCpuCapacity {
6595            target,
6596            eligible: compatible,
6597        })
6598}
6599
6600fn cpu_eligible_allowed(
6601    allowed: &std::collections::BTreeSet<usize>,
6602    states: &std::collections::BTreeMap<usize, CpuPlacementState>,
6603    mut conflicts: impl FnMut(usize) -> Result<bool>,
6604) -> Result<std::collections::BTreeSet<usize>> {
6605    let mut eligible = std::collections::BTreeSet::new();
6606    for &cpu in allowed {
6607        if states.get(&cpu).is_some_and(|state| state.exclusive_held) {
6608            continue;
6609        }
6610        if !conflicts(cpu)? {
6611            eligible.insert(cpu);
6612        }
6613    }
6614    Ok(eligible)
6615}
6616
6617/// Materialize a plan's CPU list from a selected LLC set: flatten each
6618/// selected LLC's CPUs, keeping only the `eligible` ones so the result never
6619/// contains a CPU this turn may not use, and TRUNCATING at exactly
6620/// `target_cpus` so the last-LLC overshoot contributes only the prefix the
6621/// budget needs. The full LLC is still flocked (the coordination unit is
6622/// per-LLC), but the CPUs beyond `target_cpus` never appear in `plan.cpus` —
6623/// sched_setaffinity masks and cgroup cpuset.cpus writes reflect the exact
6624/// budget. The returned `mems` collects the NUMA nodes of CPUs that actually
6625/// appear in `plan.cpus`; an LLC that contributes a partial slice on a
6626/// cross-node split only registers the nodes of its actually-used CPUs.
6627/// `None` means the eligible CPUs inside the selection cannot fund
6628/// `target_cpus`.
6629fn materialize_plan_cpus(
6630    selected: &[usize],
6631    topo: &HostTopology,
6632    eligible: &std::collections::BTreeSet<usize>,
6633    states: &std::collections::BTreeMap<usize, CpuPlacementState>,
6634    target_cpus: usize,
6635    policy: CpuSelectionPolicy,
6636) -> Option<(Vec<usize>, std::collections::BTreeSet<usize>)> {
6637    let rank = |candidates: &mut Vec<usize>, placement: PlacementPolicy| {
6638        candidates.sort_unstable();
6639        candidates.dedup();
6640        let rotation = match placement {
6641            PlacementPolicy::Consolidate => 0,
6642            PlacementPolicy::Spread { rotation } => rotation,
6643        };
6644        let count = candidates.len();
6645        let start = rotation % count.max(1);
6646        let rotated_pos: std::collections::HashMap<usize, usize> = candidates
6647            .iter()
6648            .enumerate()
6649            .map(|(position, cpu)| (*cpu, (position + count - start) % count.max(1)))
6650            .collect();
6651        candidates.sort_by(|a, b| {
6652            let a_holders = states.get(a).map_or(0, |state| state.other_holders);
6653            let b_holders = states.get(b).map_or(0, |state| state.other_holders);
6654            let occupancy = match placement {
6655                PlacementPolicy::Consolidate => b_holders.cmp(&a_holders),
6656                PlacementPolicy::Spread { .. } => a_holders.cmp(&b_holders),
6657            };
6658            // Grant charge is a fixed-sign (ASC) subordinate key under both
6659            // policies: among CPUs the primary holder key already ranks
6660            // equal, prefer the ones no in-flight grant is counting on. The
6661            // HELD-only primary key keeps its existing sign, so no held-SH
6662            // footprint (e.g. an scx cell's) ever outranks anything it
6663            // beats today.
6664            let a_granted = states.get(a).map_or(0, |state| state.granted_holders);
6665            let b_granted = states.get(b).map_or(0, |state| state.granted_holders);
6666            occupancy.then_with(|| {
6667                a_granted
6668                    .cmp(&b_granted)
6669                    .then_with(|| rotated_pos[a].cmp(&rotated_pos[b]).then(a.cmp(b)))
6670            })
6671        });
6672    };
6673
6674    let mut cpus: Vec<usize> = Vec::new();
6675    match policy {
6676        CpuSelectionPolicy::WithinEachLlc(placement) => {
6677            let mut seen = std::collections::BTreeSet::new();
6678            'outer: for &idx in selected {
6679                let group = &topo.llc_groups[idx];
6680                let mut candidates = group
6681                    .cpus
6682                    .iter()
6683                    .copied()
6684                    .filter(|cpu| eligible.contains(cpu))
6685                    .collect::<Vec<_>>();
6686                rank(&mut candidates, placement);
6687                for cpu in candidates {
6688                    if !seen.insert(cpu) {
6689                        continue;
6690                    }
6691                    if cpus.len() >= target_cpus {
6692                        break 'outer;
6693                    }
6694                    cpus.push(cpu);
6695                }
6696            }
6697        }
6698        CpuSelectionPolicy::LeastHeldAcrossFootprint { rotation } => {
6699            let mut candidates = selected
6700                .iter()
6701                .flat_map(|idx| topo.llc_groups[*idx].cpus.iter().copied())
6702                .filter(|cpu| eligible.contains(cpu))
6703                .collect::<Vec<_>>();
6704            rank(&mut candidates, PlacementPolicy::Spread { rotation });
6705            if candidates.len() < target_cpus {
6706                return None;
6707            }
6708            cpus.extend(candidates.into_iter().take(target_cpus));
6709        }
6710    }
6711    if cpus.len() != target_cpus {
6712        return None;
6713    }
6714    let mems = plan_mems(&cpus, topo);
6715    Some((cpus, mems))
6716}
6717
6718fn plan_mems(cpus: &[usize], topo: &HostTopology) -> std::collections::BTreeSet<usize> {
6719    cpus.iter()
6720        .map(|cpu| topo.cpu_to_node.get(cpu).copied().unwrap_or(0))
6721        .collect()
6722}
6723
6724/// Assemble the returned [`LlcPlan`] from one acquired selection: its LLCs,
6725/// the CPUs and NUMA nodes materialized for them, the CPU permits funding
6726/// that width, and the RAII lock owners. Shared by the fast-phase, ticket,
6727/// coordinator, and ownership-free selection-only paths so the plan they
6728/// return cannot drift apart.
6729fn materialize_llc_plan(
6730    selected: Vec<usize>,
6731    locks: protocol::Acquired<Vec<protocol::AdmissionFlock>>,
6732    cpus: Vec<usize>,
6733    permits: Vec<usize>,
6734    mems: std::collections::BTreeSet<usize>,
6735) -> LlcPlan {
6736    LlcPlan {
6737        locked_llcs: selected,
6738        cpus,
6739        permits,
6740        mems,
6741        locks,
6742    }
6743}
6744
6745/// Parallelism hint for `make -j{N}` when running under an
6746/// [`LlcPlan`] reservation. Returns the flattened host-CPU count
6747/// (`plan.cpus.len()`), clamped to at least 1 so a pathological empty
6748/// plan still produces a runnable command.
6749///
6750/// Rationale: without this hint, `make -j$(nproc)` fans gcc
6751/// children across every online CPU, defeating the --cpu-cap
6752/// reservation — the build escapes the cgroup cpuset in scheduling
6753/// terms even though the kernel enforces CPU membership. Passing
6754/// `plan.cpus.len()` to make keeps gcc's parallel width aligned with
6755/// the reserved capacity.
6756pub fn make_jobs_for_plan(plan: &LlcPlan) -> usize {
6757    if plan.permits.is_empty() {
6758        plan.cpus.len().max(1)
6759    } else {
6760        plan.permits.len().max(1)
6761    }
6762}
6763
6764/// Render selected LLC indices for user-facing warning text.
6765///
6766/// Format is compact and stable: `[0 (node 0), 2 (node 1)]` when the
6767/// host exposes NUMA information, `[0, 2]` on degraded hosts whose
6768/// `cpu_to_node` map is empty. Used by
6769/// [`warn_if_cross_node_spill`] to render the `ktstr: reserving LLCs
6770/// …` message when an `--cpu-cap` plan spills across nodes.
6771pub fn format_llc_list(locked: &[usize], topo: &HostTopology) -> String {
6772    let parts: Vec<String> = locked
6773        .iter()
6774        .map(|&idx| {
6775            if topo.cpu_to_node.is_empty() {
6776                idx.to_string()
6777            } else {
6778                let node = topo.llc_numa_node(idx);
6779                format!("{idx} (node {node})")
6780            }
6781        })
6782        .collect();
6783    format!("[{}]", parts.join(", "))
6784}
6785
6786/// Emit the cross-node spill warning when an `--cpu-cap` plan's
6787/// `mems` set spans more than one NUMA node. No-op for single-node
6788/// plans.
6789///
6790/// `eprintln!`, not `tracing::warn!`: this is user-visible
6791/// UX feedback (the operator picked a cap that couldn't fit in one
6792/// NUMA node), not operational instrumentation. Fires at most once
6793/// per plan — there is nothing in the plan lifecycle that causes a
6794/// re-trigger. Single-node plans (including single-socket hosts and
6795/// caps that fit within a single node) never emit.
6796///
6797/// Placement: called by `kernel_build_pipeline` and friends right
6798/// after [`acquire_llc_plan_interruptible`] returns, before the sandbox mount.
6799/// Extracting this into a helper rather than inlining at the call
6800/// site lets the message body be unit-tested via
6801/// [`cross_node_spill_warning`] without capturing stderr.
6802pub fn warn_if_cross_node_spill(plan: &LlcPlan, topo: &HostTopology) {
6803    if let Some(msg) = cross_node_spill_warning(plan, topo) {
6804        eprintln!("{msg}");
6805    }
6806}
6807
6808/// Build the cross-node spill warning string for `plan`, or `None`
6809/// when the plan fits within a single NUMA node (the suppression
6810/// case). [`warn_if_cross_node_spill`] is a thin wrapper that
6811/// `eprintln!`s the `Some` value; this function holds the actual
6812/// gate-and-format logic so a test can pin both halves — the
6813/// predicate gate AND the rendered message — without a stderr
6814/// capture seam. The returned string is exactly the bytes
6815/// `warn_if_cross_node_spill` would emit (sans the trailing newline
6816/// that `eprintln!` appends).
6817fn cross_node_spill_warning(plan: &LlcPlan, topo: &HostTopology) -> Option<String> {
6818    if !should_warn_cross_node(&plan.mems) {
6819        return None;
6820    }
6821    Some(format!(
6822        "ktstr: reserving LLCs {list} across {n} NUMA nodes \
6823         (preferred single-node contiguous unavailable). Work \
6824         will proceed; memory-access latency may be higher.",
6825        list = format_llc_list(&plan.locked_llcs, topo),
6826        n = plan.mems.len(),
6827    ))
6828}
6829
6830/// Pure predicate backing [`warn_if_cross_node_spill`]. Returns
6831/// `true` when the plan spans more than one NUMA node
6832/// (`mems.len() > 1`); the warning suppression for single-node
6833/// plans follows directly from this.
6834///
6835/// Split out so tests can pin the polarity of the single-node /
6836/// multi-node decision without capturing stderr. A refactor that
6837/// accidentally flipped the comparison (`>= 1` or `== 1`) would
6838/// either warn on every plan (noise) or never warn (silent cost),
6839/// both of which the test suite catches here before the stderr
6840/// capture layer sees it.
6841fn should_warn_cross_node(mems: &std::collections::BTreeSet<usize>) -> bool {
6842    mems.len() > 1
6843}
6844
6845/// Diagnostic text when the effective host-CPU budget is below the guest's
6846/// vCPU count, else `None`.
6847///
6848/// `intentional` splits severity: no-perf / an explicit CPU budget requested
6849/// shared execution, while the default placement fallback only overcommits
6850/// because the host cannot provide a 1:1 mapping. Keep the text factual: this
6851/// is a placement observation, not a performance-model recommendation or a
6852/// claim about the guest scheduler's own watchdog tuning.
6853///
6854/// Pure (returns the text) so a test pins the message + the
6855/// `None`-when-not-oversubscribed polarity without capturing stderr; the
6856/// caller eprintln's it once at build time, mirroring
6857/// [`warn_if_cross_node_spill`].
6858pub(crate) fn overcommit_warning(
6859    effective_host_cpus: usize,
6860    vcpus: usize,
6861    intentional: bool,
6862) -> Option<String> {
6863    if effective_host_cpus >= vcpus {
6864        return None;
6865    }
6866    let oversub = vcpus as f64 / effective_host_cpus.max(1) as f64;
6867    let msg = if intentional {
6868        format!(
6869            "ktstr: {vcpus} guest vCPUs share {effective_host_cpus} host CPUs \
6870             ({oversub:.1}x oversubscribed; no-perf/cpu-budget mode)"
6871        )
6872    } else {
6873        format!(
6874            "ktstr: WARNING: {vcpus} guest vCPUs share {effective_host_cpus} host \
6875             CPUs ({oversub:.1}x oversubscribed; host capacity is below guest width)"
6876        )
6877    };
6878    Some(msg)
6879}
6880
6881/// Whether [`mbind_to_nodes`] must short-circuit before touching `addr`
6882/// or invoking the `mbind(2)` syscall. Returns `true` when there is no
6883/// work to do — an empty node set (no policy target) or a zero-length
6884/// region. This is the exact guard [`mbind_to_nodes`] consults; it is a
6885/// pure predicate so the short-circuit decision can be asserted directly
6886/// instead of inferred from a not-crashing call (whose pass condition the
6887/// syscall's own error-swallowing would satisfy regardless of the guard).
6888fn mbind_should_skip(len: usize, nodes: &[usize]) -> bool {
6889    nodes.is_empty() || len == 0
6890}
6891
6892/// Bind a memory region to specific NUMA nodes using `mbind(MPOL_BIND)`.
6893/// `nodes` is the set of NUMA node IDs. Logs a warning on error
6894/// (single-node systems, missing capabilities).
6895///
6896/// # Safety
6897///
6898/// The caller must ensure that `addr` points to a valid mmap'd region
6899/// of at least `len` bytes. The kernel will read this range via the
6900/// `mbind(2)` syscall to set its NUMA memory policy; passing a stale,
6901/// unmapped, or out-of-bounds pointer is undefined behavior from the
6902/// process's perspective (the syscall itself returns EFAULT, but the
6903/// surrounding Rust contract is violated).
6904///
6905/// When `nodes.is_empty()` or `len == 0`, the function short-circuits
6906/// without dereferencing `addr`, so a null or dangling pointer is
6907/// permitted in those cases.
6908pub unsafe fn mbind_to_nodes(addr: *mut u8, len: usize, nodes: &[usize]) {
6909    if mbind_should_skip(len, nodes) {
6910        return;
6911    }
6912    let node_set: std::collections::BTreeSet<usize> = nodes.iter().copied().collect();
6913    let (nodemask, maxnode) = crate::workload::build_nodemask(&node_set);
6914
6915    let rc = unsafe {
6916        libc::syscall(
6917            libc::SYS_mbind,
6918            addr as *mut libc::c_void,
6919            len,
6920            libc::MPOL_BIND,
6921            nodemask.as_ptr(),
6922            maxnode,
6923            0u32,
6924        )
6925    };
6926    if rc == 0 {
6927        // Success is per-region chatter; debug-gated like the per-vCPU pin
6928        // lines. Failure stays unconditional — it explains degraded locality.
6929        if crate::vmm::debug_logging_enabled() {
6930            eprintln!(
6931                "performance_mode: mbind {} MB to NUMA node(s) {:?}",
6932                len >> 20,
6933                nodes,
6934            );
6935        }
6936    } else {
6937        let err = std::io::Error::last_os_error();
6938        eprintln!(
6939            "performance_mode: WARNING: mbind to node(s) {:?} failed: {err}",
6940            nodes,
6941        );
6942    }
6943}
6944
6945use crate::topology::parse_cpu_list_lenient;
6946
6947/// Number of free 2MB hugepages on the host.
6948pub fn hugepages_free() -> u64 {
6949    hugepages_free_from(std::path::Path::new(
6950        "/sys/kernel/mm/hugepages/hugepages-2048kB/free_hugepages",
6951    ))
6952}
6953
6954/// Path-parameterized core of [`hugepages_free`]. Reads the
6955/// `free_hugepages` sysfs file at `path`, parses the trimmed count, and
6956/// returns 0 when the file is absent, unreadable, or contains a value
6957/// that does not parse as a `u64`. Exposes a path seam so the parse and
6958/// the documented 0-fallback can be tested against fixture files without
6959/// depending on the host's hugetlbfs configuration.
6960fn hugepages_free_from(path: &std::path::Path) -> u64 {
6961    std::fs::read_to_string(path)
6962        .ok()
6963        .and_then(|s| s.trim().parse::<u64>().ok())
6964        .unwrap_or(0)
6965}
6966
6967/// Estimate the number of 2 MiB hugepages needed for a given memory size in MiB.
6968pub fn hugepages_needed(memory_mib: u32) -> u64 {
6969    // 2 MiB per hugepage.
6970    (memory_mib as u64).div_ceil(2)
6971}
6972
6973/// Estimate current host CPU load by checking /proc/stat.
6974/// Returns (busy_cpus, total_cpus) as a rough estimate.
6975pub fn host_load_estimate() -> Option<(usize, usize)> {
6976    // Count processes in R state from /proc/stat.
6977    let stat = std::fs::read_to_string("/proc/stat").ok()?;
6978    let procs_running = stat
6979        .lines()
6980        .find(|l| l.starts_with("procs_running "))?
6981        .split_whitespace()
6982        .nth(1)?
6983        .parse::<usize>()
6984        .ok()?;
6985    let online = std::fs::read_to_string("/sys/devices/system/cpu/online").ok()?;
6986    let total = parse_cpu_list_lenient(&online).len();
6987    Some((procs_running, total))
6988}
6989
6990#[cfg(test)]
6991mod tests;