1use anyhow::{Context, Result};
7use std::cell::RefCell;
8use std::sync::atomic::{AtomicBool, Ordering};
9
10#[cfg(test)]
17use crate::flock::try_flock;
18use crate::flock::{FlockMode, TryFlockOutcome, block_flock_deadline, try_flock_with_witness};
19
20pub(crate) mod protocol;
24
25const RESERVATION_WAIT_PROGRESS_POLL: std::time::Duration = std::time::Duration::from_secs(1);
26
27thread_local! {
28 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#[derive(Debug, thiserror::Error)]
79#[error("{reason}")]
80pub struct ResourceContention {
81 pub reason: String,
82}
83
84#[derive(Debug, thiserror::Error)]
109#[error("{reason}")]
110pub struct TopologyInsufficient {
111 pub reason: String,
112}
113
114#[derive(Debug, thiserror::Error)]
130#[error("{reason}")]
131pub struct PerfModeUnavailable {
132 pub reason: String,
133}
134
135#[derive(Debug, thiserror::Error)]
147#[error("{reason}")]
148pub struct CpuBudgetUnsatisfiable {
149 pub reason: String,
150}
151
152#[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#[derive(Debug, Clone)]
194pub struct LlcGroup {
195 pub cpus: Vec<usize>,
197}
198
199#[derive(Debug, Clone)]
201pub struct HostTopology {
202 pub llc_groups: Vec<LlcGroup>,
204 pub online_cpus: Vec<usize>,
206 pub cpu_to_node: std::collections::HashMap<usize, usize>,
209 pub(crate) host_node_llcs: std::collections::BTreeMap<usize, Vec<usize>>,
217}
218
219#[derive(Debug)]
222pub struct PinningPlan {
223 pub assignments: Vec<(u32, usize)>,
225 pub service_cpu: Option<usize>,
228 pub llc_indices: Vec<usize>,
230 #[allow(dead_code)] pub(crate) locks: protocol::Acquired<Vec<protocol::AdmissionFlock>>,
234}
235
236#[derive(Debug, Clone, Copy, PartialEq, Eq)]
238pub(crate) enum PinningKind {
239 Default,
244 Performance,
247}
248
249#[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
260pub(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 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
323static 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 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 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 #[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 #[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 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 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 for llcs in node_llcs.values_mut() {
496 llcs.sort_unstable();
497 }
498 node_llcs
499 }
500
501 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 #[cfg(test)]
512 pub fn total_cpus(&self) -> usize {
513 self.online_cpus.len()
514 }
515
516 #[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 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 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 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 #[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 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 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 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 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 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 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 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 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 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 let mut assignments = Vec::new();
1066 let mut occupied = BTreeSet::new();
1067 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 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 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 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 .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 if (0..demands.len()).any(|request| matches_with_service(Some(request), None)) {
1343 return true;
1344 }
1345 (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
1374fn 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
1429fn 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
1474fn 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 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1600pub enum LlcLockMode {
1601 Exclusive,
1604 Shared,
1608}
1609
1610pub(crate) const PERF_GRAIN_LLC_MIN_CPUS: usize = 32;
1636
1637const PERF_GRAIN_MAX_OCCUPANCY_NUM: usize = 1;
1651const PERF_GRAIN_MAX_OCCUPANCY_DEN: usize = 2;
1652
1653pub(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 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 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 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#[derive(Debug)]
1716pub enum LockOutcome {
1717 Acquired {
1719 #[allow(dead_code)]
1721 llc_offset: usize,
1722 locks: protocol::Acquired<Vec<protocol::AdmissionFlock>>,
1723 },
1724 Unavailable(#[allow(dead_code)] String),
1728}
1729
1730pub(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 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 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
1854pub(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
1888const NEXTEST_TEST_GROUP_ENV: &str = "NEXTEST_TEST_GROUP";
1892const NEXTEST_TEST_NAME_ENV: &str = "NEXTEST_TEST_NAME";
1893
1894fn 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
1946fn llc_lock_prefix() -> String {
1949 format!("{}/ktstr-llc-", production_lock_dir().display())
1950}
1951
1952fn cpu_lock_prefix() -> String {
1955 format!("{}/ktstr-cpu-", production_lock_dir().display())
1956}
1957
1958fn permit_lock_prefix() -> String {
1960 format!("{}/ktstr-permit-", production_lock_dir().display())
1961}
1962
1963#[cfg(test)]
1964thread_local! {
1965 pub(crate) static LLC_LOCK_PREFIX_OVERRIDE: std::cell::RefCell<Option<String>> =
1973 const { std::cell::RefCell::new(None) };
1974
1975 pub(crate) static CPU_LOCK_PREFIX_OVERRIDE: std::cell::RefCell<Option<String>> =
1978 const { std::cell::RefCell::new(None) };
1979}
1980
1981pub(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
1995pub(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
2008pub(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
2021pub(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 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 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
2207pub(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
2308pub(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
2340pub(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
2414pub(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 pub(crate) static ALLOWED_CPUS_OVERRIDE: std::cell::RefCell<Option<Vec<usize>>> =
2435 const { std::cell::RefCell::new(None) };
2436}
2437
2438fn default_cpu_budget(allowed_cpus: usize) -> usize {
2446 allowed_cpus.saturating_mul(30).div_ceil(100).max(1)
2447}
2448
2449pub(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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
2509pub struct CpuCap {
2510 n: std::num::NonZeroUsize,
2511}
2512
2513impl CpuCap {
2514 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 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 pub fn effective_count(&self, allowed_cpus: usize) -> Result<usize> {
2571 let n = self.n.get();
2572 if n > allowed_cpus {
2573 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
2623pub enum PlacementPolicy {
2624 Consolidate,
2628 Spread { rotation: usize },
2632}
2633
2634impl PlacementPolicy {
2635 pub fn spread_for_process() -> Self {
2639 PlacementPolicy::Spread {
2640 rotation: pid_window_offset(std::process::id(), 1 << 16),
2641 }
2642 }
2643}
2644
2645#[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#[derive(Debug, Clone)]
2674pub(crate) struct LlcSnapshot {
2675 pub(crate) llc_idx: usize,
2677 pub(crate) holder_count: usize,
2681 pub(crate) exclusive_held: bool,
2688 pub(crate) granted_count: usize,
2694}
2695
2696#[derive(Debug)]
2710pub struct LlcPlan {
2711 pub locked_llcs: Vec<usize>,
2716 pub cpus: Vec<usize>,
2721 pub(crate) permits: Vec<usize>,
2724 pub mems: std::collections::BTreeSet<usize>,
2729 #[allow(dead_code)] pub(crate) locks: protocol::Acquired<Vec<protocol::AdmissionFlock>>,
2733}
2734
2735const ACQUIRE_MAX_TOCTOU_RETRIES: u32 = 3;
2745
2746const 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
2758fn 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 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
2824fn 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
2878fn 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 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 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 let eligible = |s: &&LlcSnapshot| -> bool { llc_allowed_cpus(s.llc_idx) > 0 };
2935 let ranked: Vec<&LlcSnapshot> = match policy {
2936 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 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 fresh.sort_by_key(|s| s.granted_count);
2976 consolidation.into_iter().chain(fresh).collect()
2977 }
2978 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 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 return Vec::new();
3015 }
3016
3017 let seed = ranked[0];
3020 let seed_node = topo.llc_numa_node(seed.llc_idx);
3021
3022 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 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 selected.sort_unstable();
3065 selected
3066}
3067
3068fn 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(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
3198fn 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#[allow(clippy::too_many_arguments)] pub(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
3272pub(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
3331const 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;
3339const 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 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 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 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
3434pub(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 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
3510pub(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 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 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 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 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)] 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 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
3711fn 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 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 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 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 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
3842pub(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
3863pub(super) fn permit_namespace_end() -> Result<usize> {
3869 build_permit_range(possible_cpu_width()).map(|range| range.end)
3870}
3871
3872enum 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
3952fn 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 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
4177pub(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
4188pub(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
4255pub(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 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
4286pub(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
4413pub(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
4471fn 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#[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 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 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 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
4619fn 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#[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 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 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 self.select_grant_aware(|_| Ok(true), charged)
4924 }
4925 }
4926}
4927
4928#[derive(Clone, Copy, Debug, PartialEq, Eq)]
4929enum LlcPlanSizing {
4930 Exact,
4932 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
4956struct PlanPermitSelection {
4962 permits: VmPermitSelection,
4963 cpu_width: usize,
4964}
4965
4966#[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 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
5123fn 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#[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#[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#[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 let elastic_fresh_rotation =
5329 (sizing == LlcPlanSizing::Elastic).then(|| pid_window_offset(std::process::id(), 1 << 16));
5330 check_acquire_cancelled(cancelled)?;
5331 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 return Err(ResourceContention {
5386 reason: "CPU budget resolved to zero".into(),
5387 }
5388 .into());
5389 }
5390
5391 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 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 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 let mut attempt_permit_snapshot = None;
5556 let plan_permit_selection = if selected_cpus.is_empty() {
5557 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 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 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 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 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 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 queue_seed_snapshots = Some(snapshots);
5806 queue_seed_cpu_states = Some(cpu_states);
5807 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 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 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 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 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 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 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 let watch_class = match permit_admission {
6018 PermitAdmission::None => protocol::AdmissionClass::Ordinary,
6019 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 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 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 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 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 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 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
6431pub 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#[derive(Debug, Clone, Copy, Default)]
6529struct CpuPlacementState {
6530 exclusive_held: bool,
6531 other_holders: usize,
6532 granted_holders: usize,
6536}
6537
6538struct 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
6617fn 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 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
6724fn 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
6745pub 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
6764pub 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
6786pub 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
6808fn 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
6830fn should_warn_cross_node(mems: &std::collections::BTreeSet<usize>) -> bool {
6842 mems.len() > 1
6843}
6844
6845pub(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
6881fn mbind_should_skip(len: usize, nodes: &[usize]) -> bool {
6889 nodes.is_empty() || len == 0
6890}
6891
6892pub 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 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
6947pub fn hugepages_free() -> u64 {
6949 hugepages_free_from(std::path::Path::new(
6950 "/sys/kernel/mm/hugepages/hugepages-2048kB/free_hugepages",
6951 ))
6952}
6953
6954fn 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
6967pub fn hugepages_needed(memory_mib: u32) -> u64 {
6969 (memory_mib as u64).div_ceil(2)
6971}
6972
6973pub fn host_load_estimate() -> Option<(usize, usize)> {
6976 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;