From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from gate001.proxmox.com (gate001.proxmox.com [IPv6:2a0f:8001:1:32::40]) by lore.proxmox.com (Postfix) with ESMTPS id A57271FF0C0 for ; Wed, 21 Oct 2026 11:01:15 +0200 (CEST) Received: from gate001.proxmox.com (localhost.localdomain [127.0.0.1]) by gate001.proxmox.com (Proxmox) with ESMTP id 7C35B2178C; Wed, 21 Oct 2026 11:00:15 +0200 (CEST) From: Dominik Rusovac To: pve-devel@lists.proxmox.com Subject: [PATCH proxmox 05/15] resource-scheduling: scheduler: proptest weights Date: Wed, 21 Oct 2026 10:59:22 +0200 Message-ID: <20261021085932.1196302-6-d.rusovac@proxmox.com> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20261021085932.1196302-1-d.rusovac@proxmox.com> References: <20261021085932.1196302-1-d.rusovac@proxmox.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Bm-Milter-Handled: 55990f41-d878-4baa-be0a-ee34c49e34d2 X-Bm-Transport-Timestamp: 1792573177309 X-SPAM-LEVEL: Spam detection results: 0 AWL 0.072 Adjusted score from AWL reputation of From: address DMARC_MISSING 0.1 Missing DMARC policy KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment (newer systems) RCVD_IN_DNSWL_MED -2.3 Sender listed at https://www.dnswl.org/, medium trust SPF_HELO_NONE 0.001 SPF: HELO does not publish an SPF Record SPF_PASS -0.001 SPF: sender matches SPF record Message-ID-Hash: CI7C6RFDEKZV7EWHPKQKFWG5R75N247B X-Message-ID-Hash: CI7C6RFDEKZV7EWHPKQKFWG5R75N247B X-MailFrom: d.rusovac@proxmox.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; loop; banned-address; emergency; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header X-Mailman-Version: 3.3.10 Precedence: list List-Id: Proxmox VE development discussion List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: Introduce proptests with constants to control scheduler proptests and functions implementing useful proptest strategies. Use per-method `mod`s to make deliberate testing easier, e.g., executing `cargo test bruteforce` to run bruteforce (prop)tests only. For each method (bruteforce, TOPSIS), respectively, add proptests: - test_weight_scale_invariance: test that only weight ratio matters, not their absolute magnitudes; and - test_zero_cpu_weight_discards_cpu_load: cpu weight of 0 discards CPU load (symmetric test discarding memory usage is omitted). Signed-off-by: Dominik Rusovac --- proxmox-resource-scheduling/src/scheduler.rs | 343 +++++++++++++++++++ 1 file changed, 343 insertions(+) diff --git a/proxmox-resource-scheduling/src/scheduler.rs b/proxmox-resource-scheduling/src/scheduler.rs index 0690385d..3c4c8d87 100644 --- a/proxmox-resource-scheduling/src/scheduler.rs +++ b/proxmox-resource-scheduling/src/scheduler.rs @@ -429,6 +429,27 @@ impl Scheduler { mod tests { use super::*; + use proptest::prelude::*; + use std::ops::Range; + + const MIN_NODES: usize = 3; + const MAX_NODES: usize = 36; + + const MIN_CPU: usize = 2; + const MIN_MEM: usize = 2; + const MAX_CPU: usize = 128; + const MAX_MEM: usize = 256; + + const MIN_WEIGHT: usize = 1; + const MAX_WEIGHT: usize = 1_000; + + const MIN_CONSTANT: usize = 1; + const MAX_CONSTANT: usize = 1_000; + + const REPEAT_PROPTEST_N_TIMES: u32 = 256; // proptest's default + + const EPSILON: f64 = 1e-9; + #[test] fn test_scored_migration_order() { let migration1 = ScoredMigration::new( @@ -528,4 +549,326 @@ mod tests { assert_eq!(heap.pop(), Some(Reverse(migration2))); assert_eq!(heap.pop(), Some(Reverse(migration3))); } + + /// Strategy to generate `n` random nodes with stats bound by `max_cpu` and `max_mem`. + pub fn nodes_strategy( + n: usize, + max_cpu: usize, + max_mem: usize, + ) -> impl Strategy> { + prop::collection::vec((0..max_cpu + 1, 0..max_mem + 1), n).prop_map( + move |computational_resources| { + computational_resources + .into_iter() + .enumerate() + .map(|(i, (cpu, mem))| NodeUsage { + name: format!("node{i}"), + stats: NodeStats { + cpu: cpu as f64, + maxcpu: max_cpu, + mem, + maxmem: max_mem, + }, + }) + .collect() + }, + ) + } + + /// Strategy to generate a random number in `n_range` of migration candidates between `nodes`. + /// Resource stats are bound by `max_cpu` and `max_mem`. + fn candidates_strategy( + n_range: impl Into, + max_cpu: usize, + max_mem: usize, + nodes: Vec, + ) -> impl Strategy> { + let k = nodes.len(); + + prop::collection::vec((0..max_cpu, 0..max_mem, 0..k, 0..k), n_range).prop_map( + move |computational_resources| { + computational_resources + .into_iter() + .enumerate() + .map( + |(i, (cpu, mem, source_idx, target_idx))| MigrationCandidate { + migration: Migration { + sid: format!("vm:10{i}"), + source_node: nodes[source_idx].name.clone(), + target_node: nodes[target_idx].name.clone(), + }, + stats: ResourceStats { + cpu: cpu as f64, + maxcpu: max_cpu as f64, + mem, + maxmem: max_mem, + }, + }, + ) + .filter(|candidate| { + candidate.migration.source_node != candidate.migration.target_node + }) + .collect() + }, + ) + } + + /// Strategy to generate: + /// - a random number n in `n_nodes_range` of nodes + /// - a random number between 1 and n * (n - 1) of migration candidates between the generated + /// nodes + /// + /// The stats of nodes and migration candidates are bound by random numbers in `cpu_range` and + /// `mem_range`, respectively. + fn scenario_strategy( + cpu_range: Range, + mem_range: Range, + n_nodes_range: Range, + ) -> impl Strategy, Vec)> { + (cpu_range, mem_range).prop_flat_map(move |(max_cpu, max_mem)| { + n_nodes_range + .clone() + .prop_filter("cluster size must be odd", |n| n % 2 == 1) + .prop_flat_map(move |n_nodes| { + nodes_strategy(n_nodes, max_cpu, max_mem).prop_flat_map(move |nodes| { + let max_candidates = n_nodes * (n_nodes - 1); + + candidates_strategy(1..=max_candidates, max_cpu, max_mem, nodes.clone()) + .prop_map(move |candidates| (nodes.clone(), candidates)) + }) + }) + }) + } + + mod bruteforce { + use super::*; + + mod weights { + use super::*; + + proptest! { + #![proptest_config(ProptestConfig { + cases: REPEAT_PROPTEST_N_TIMES, + ..ProptestConfig::default() + })] + + /// Test that the achievable scores are completely unaffected by uniformly scaling + /// both weights; only the weights' ratio matters. + #[test] + fn test_weight_scale_invariance( + cpu_weight in MIN_WEIGHT..MAX_WEIGHT, + mem_weight in MIN_WEIGHT..MAX_WEIGHT, + k in MIN_CONSTANT..MAX_CONSTANT, + (nodes, candidates) in + scenario_strategy(MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES) + ) { + let scheduler = Scheduler::from_nodes(nodes); + let n = candidates.len(); + + scheduler + .score_best_balancing_migration_candidates( + candidates.clone(), + n, + cpu_weight, + mem_weight, + ) + .iter() + .zip( + scheduler + .score_best_balancing_migration_candidates( + candidates.clone(), + n, + k * cpu_weight, + k * mem_weight, + ) + .iter(), + ) + .for_each(|(lhs, rhs)| { + assert!( + (lhs.score - rhs.score).abs() < EPSILON, + "equally ranked migrations {:?} and {:?} must have the same score", + lhs, + rhs, + ); + }); + } + + /// Test that with a `cpu_weight` of 0 the score for each scored migration should + /// match an imbalance computed directly from [`NodeStats::mem_load()`] alone. + #[test] + fn test_zero_cpu_weight_discards_cpu_load( + mem_weight in MIN_WEIGHT..MAX_WEIGHT, + (nodes, candidates) in + scenario_strategy(MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES) + ) { + let cpu_weight = 0; + + Scheduler::from_nodes(nodes.clone()) + .score_best_balancing_migration_candidates( + candidates.clone(), + candidates.len(), + cpu_weight, + mem_weight, + ) + .iter() + .filter_map(|scored_migration| { + candidates + .iter() + .find(|c| c.migration.sid == scored_migration.migration.sid) + .map(|c| (scored_migration, c)) + }) + .for_each(|(scored_migration, candidate)| { + let reference_imbalance = calculate_node_imbalance(&nodes, |node| { + node_stats_after_migration(candidate, node).mem_load() + }); + + assert!( + (scored_migration.score - reference_imbalance).abs() < EPSILON + ); + }) + } + } + } + } + + mod topsis { + use super::*; + + /// Strategy producing two scenarios using [`super::scenario_strategy`] that are identical + /// in every memory-related field and in topology but have varying CPU fields. + #[allow(clippy::type_complexity)] + fn two_scenarios_with_varying_cpu_stats_strategy( + cpu_range: Range, + mem_range: Range, + n_nodes_range: Range, + ) -> impl Strategy< + Value = ( + (Vec, Vec), + (Vec, Vec), + ), + > { + let max_possible_nodes = n_nodes_range.end - 1; // Range is exclusive + let max_possible_candidates = max_possible_nodes * (max_possible_nodes - 1); + let cpu_pool_bound = cpu_range.end; + + ( + scenario_strategy(cpu_range, mem_range, n_nodes_range), + prop::collection::vec(0usize..cpu_pool_bound + 1, max_possible_nodes), + prop::collection::vec(0usize..cpu_pool_bound, max_possible_candidates), + ) + .prop_map( + move |((nodes, candidates), alt_node_cpu_pool, alt_candidate_cpu_pool)| { + let mut alt_nodes = nodes.clone(); + alt_nodes.iter_mut().zip(alt_node_cpu_pool.iter()).for_each( + |(node, &cpu)| { + node.stats.cpu = cpu as f64; + }, + ); + + let mut alt_candidates = candidates.clone(); + alt_candidates + .iter_mut() + .zip(alt_candidate_cpu_pool.iter()) + .for_each(|(candidate, &cpu)| { + candidate.stats.cpu = cpu as f64; + }); + + ((nodes, candidates), (alt_nodes, alt_candidates)) + }, + ) + } + + proptest! { + #![proptest_config(ProptestConfig { + cases: REPEAT_PROPTEST_N_TIMES, + ..ProptestConfig::default() + })] + + /// Test that the achievable scores are completely unaffected by uniformly scaling both + /// weights; only the weights' ratio matters. + #[test] + fn test_weight_scale_invariance( + cpu_weight in MIN_WEIGHT..MAX_WEIGHT, + mem_weight in MIN_WEIGHT..MAX_WEIGHT, + k in MIN_CONSTANT..MAX_CONSTANT, + (nodes, candidates) in + scenario_strategy(MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES) + ) { + let scheduler = Scheduler::from_nodes(nodes); + let n = candidates.len(); + + scheduler + .score_best_balancing_migration_candidates_topsis( + &candidates, + n, + cpu_weight, + mem_weight, + ) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")) + .iter() + .zip( + scheduler + .score_best_balancing_migration_candidates_topsis( + &candidates, + n, + k * cpu_weight, + k * mem_weight, + ) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")) + .iter(), + ) + .for_each(|(lhs, rhs)| { + assert!( + (lhs.score - rhs.score).abs() < EPSILON, + "equally ranked migrations {:?} and {:?} must have the same score", + lhs, + rhs, + ); + }); + } + + /// Test that varying CPU stats between two otherwise identical scenarios do not change + /// the achievable scores if CPU weight is 0. + #[test] + fn test_zero_cpu_weight_discards_cpu_load( + mem_weight in MIN_WEIGHT..MAX_WEIGHT, + ((nodes_a, candidates_a), (nodes_b, candidates_b)) in + two_scenarios_with_varying_cpu_stats_strategy( + MIN_CPU..MAX_CPU, MIN_MEM..MAX_MEM, MIN_NODES..MAX_NODES + ), + ) { + let cpu_weight = 0; + let n = candidates_a.len(); + + Scheduler::from_nodes(nodes_a) + .score_best_balancing_migration_candidates_topsis( + &candidates_a, + n, + cpu_weight, + mem_weight, + ) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")) + .iter() + .zip( + Scheduler::from_nodes(nodes_b) + .score_best_balancing_migration_candidates_topsis( + &candidates_b, + n, + cpu_weight, + mem_weight, + ) + .unwrap_or_else(|err| panic!("topsis failed with: {err}")) + .iter(), + ) + .for_each(|(a, b)| { + assert!( + (a.score - b.score).abs() < EPSILON, + "equally ranked migrations {:?} and {:?} must have the same score", + a, + b, + ); + }); + } + } + } } -- 2.47.3