Nothing to see here, move along meow
1use crate::cap::pool::POOL;
2use crate::mem::phys::BitmapFrameAllocator;
3use crate::proc::PROCESSES;
4use crate::tests::helpers::{destroy_batch_and_verify, spawn_batch_with_sched};
5use crate::types::Pid;
6use crate::wcet::tsc;
7
8fn spread_priority(i: usize) -> u8 {
9 (i % 256) as u8
10}
11
12fn measure_dispatch_ns(warmup: usize, measured: usize) -> u64 {
13 let mut ptable = PROCESSES.lock();
14
15 (0..warmup).for_each(|_| {
16 if let Some(pid) = ptable.dequeue_highest() {
17 ptable.enqueue_ready(pid);
18 }
19 });
20
21 let start = tsc::read_tsc_fenced();
22 (0..measured).for_each(|_| {
23 if let Some(pid) = ptable.dequeue_highest() {
24 ptable.enqueue_ready(pid);
25 }
26 });
27 let end = tsc::read_tsc_fenced();
28 tsc::cycles_to_ns(end.saturating_sub(start)) / measured as u64
29}
30
31crate::kernel_test!(
32 fn dispatch_is_constant_time() {
33 let baseline = BitmapFrameAllocator::free_frames();
34 let small = spawn_batch_with_sched(100, 10_000, 100_000, spread_priority);
35 let ns_100 = measure_dispatch_ns(100, 1000);
36 destroy_batch_and_verify(&small, baseline);
37
38 let baseline = BitmapFrameAllocator::free_frames();
39 let medium = spawn_batch_with_sched(500, 10_000, 100_000, spread_priority);
40 let ns_500 = measure_dispatch_ns(100, 1000);
41 destroy_batch_and_verify(&medium, baseline);
42
43 let baseline = BitmapFrameAllocator::free_frames();
44 let large = spawn_batch_with_sched(2000, 10_000, 100_000, spread_priority);
45 let ns_2000 = measure_dispatch_ns(100, 1000);
46 destroy_batch_and_verify(&large, baseline);
47
48 crate::kprintln!(
49 "[sched_latency] dispatch: 100t={}ns 500t={}ns 2000t={}ns",
50 ns_100,
51 ns_500,
52 ns_2000,
53 );
54
55 let max_ns = ns_100.max(ns_500).max(ns_2000);
56 let min_ns = ns_100.min(ns_500).min(ns_2000).max(1);
57
58 assert!(
59 max_ns < min_ns * 3,
60 "not O(1): spread {}x ({}ns..{}ns) across 100/500/2000 threads",
61 max_ns / min_ns,
62 min_ns,
63 max_ns,
64 );
65
66 assert!(
67 max_ns < 5_000,
68 "dispatch latency {}ns exceeds 5us target at worst scale",
69 max_ns,
70 );
71 }
72);
73
74crate::kernel_test!(
75 fn dispatch_selects_highest_priority() {
76 let baseline = BitmapFrameAllocator::free_frames();
77 let batch = spawn_batch_with_sched(256, 10_000, 100_000, spread_priority);
78
79 let mut ptable = PROCESSES.lock();
80
81 let mut all_dequeued = crate::static_vec::StaticVec::<Pid, 512>::new();
82 core::iter::from_fn(|| ptable.dequeue_highest()).for_each(|pid| {
83 all_dequeued
84 .push(pid)
85 .expect("too many pids in run queue");
86 });
87
88 all_dequeued.as_slice().windows(2).for_each(|pair| {
89 let prio_a = ptable[pair[0]].effective_priority().raw();
90 let prio_b = ptable[pair[1]].effective_priority().raw();
91 assert!(
92 prio_a >= prio_b,
93 "priority ordering violated: {} followed by {}",
94 prio_a,
95 prio_b,
96 );
97 });
98
99 let ours_seen = all_dequeued
100 .iter()
101 .filter(|pid| batch.pids.iter().any(|&p| p == **pid))
102 .count();
103 assert!(
104 ours_seen == 256,
105 "expected 256 of our threads dequeued, got {}",
106 ours_seen,
107 );
108
109 all_dequeued.iter().for_each(|&pid| {
110 ptable.enqueue_ready(pid);
111 });
112 drop(ptable);
113
114 destroy_batch_and_verify(&batch, baseline);
115 }
116);
117
118crate::kernel_test!(
119 fn timer_wheel_fires_all_no_lost_entries() {
120 let baseline = BitmapFrameAllocator::free_frames();
121 let batch = spawn_batch_with_sched(500, 10_000, 100_000, spread_priority);
122
123 let mut ptable = PROCESSES.lock();
124 let base_us = tsc::cycles_to_ns(tsc::read_tsc()) / 1000;
125 ptable.timer_seed(base_us);
126
127 batch.pids.iter().enumerate().for_each(|(i, &pid)| {
128 ptable.simulate_dispatch(pid);
129 let deadline = base_us + (i as u64 + 1) * 50;
130 ptable.timer_insert(pid, deadline);
131 });
132
133 let mut total_fired = 0u32;
134 let ticks = 100usize;
135 let tick_step = 500u64;
136
137 let mut per_tick_ns = crate::static_vec::StaticVec::<u64, 128>::new();
138
139 (0..ticks).for_each(|t| {
140 let now = base_us + (t as u64 + 1) * tick_step;
141 let start = tsc::read_tsc_fenced();
142 ptable.timer_advance(now, |_| {
143 total_fired += 1;
144 });
145 let end = tsc::read_tsc_fenced();
146 let _ = per_tick_ns.push(tsc::cycles_to_ns(end.saturating_sub(start)));
147 });
148
149 let max_tick_ns = per_tick_ns.iter().copied().fold(0u64, u64::max);
150 let avg_tick_ns = per_tick_ns.iter().sum::<u64>() / ticks as u64;
151
152 crate::kprintln!(
153 "[sched_latency] timer_wheel: {} entries, {} fired, avg_tick={}ns, max_tick={}ns",
154 batch.pids.len(),
155 total_fired,
156 avg_tick_ns,
157 max_tick_ns,
158 );
159
160 assert!(
161 total_fired == batch.pids.len() as u32,
162 "lost timers: inserted {}, fired {}",
163 batch.pids.len(),
164 total_fired,
165 );
166
167 assert!(
168 max_tick_ns < 500_000,
169 "worst-case single tick {}ns exceeds 500us",
170 max_tick_ns,
171 );
172
173 drop(ptable);
174 destroy_batch_and_verify(&batch, baseline);
175 }
176);
177
178crate::kernel_test!(
179 fn timer_wheel_per_tick_cost_bounded() {
180 let baseline = BitmapFrameAllocator::free_frames();
181 let batch = spawn_batch_with_sched(1000, 10_000, 100_000, spread_priority);
182
183 let mut ptable = PROCESSES.lock();
184 let base_us = tsc::cycles_to_ns(tsc::read_tsc()) / 1000;
185 ptable.timer_seed(base_us);
186
187 batch.pids.iter().enumerate().for_each(|(i, &pid)| {
188 ptable.simulate_dispatch(pid);
189 let deadline = base_us + 1000 + (i as u64) * 10;
190 ptable.timer_insert(pid, deadline);
191 });
192
193 let warmup_target = base_us + 500;
194 ptable.timer_advance(warmup_target, |_| {});
195
196 let ticks = 200usize;
197 let tick_step = 100u64;
198 let mut max_ns = 0u64;
199 let mut total_ns = 0u64;
200
201 (0..ticks).for_each(|t| {
202 let now = warmup_target + (t as u64 + 1) * tick_step;
203 let start = tsc::read_tsc_fenced();
204 ptable.timer_advance(now, |_| {});
205 let end = tsc::read_tsc_fenced();
206 let ns = tsc::cycles_to_ns(end.saturating_sub(start));
207 total_ns += ns;
208 max_ns = max_ns.max(ns);
209 });
210
211 let avg_ns = total_ns / ticks as u64;
212
213 crate::kprintln!(
214 "[sched_latency] timer_tick cost (1000 entries): avg={}ns, max={}ns",
215 avg_ns,
216 max_ns,
217 );
218
219 assert!(
220 avg_ns < 50_000,
221 "avg per-tick cost {}ns exceeds 50us",
222 avg_ns,
223 );
224 assert!(
225 max_ns < 200_000,
226 "worst-case per-tick cost {}ns exceeds 200us",
227 max_ns,
228 );
229
230 drop(ptable);
231 destroy_batch_and_verify(&batch, baseline);
232 }
233);
234
235crate::kernel_test!(
236 fn integrated_tick_latency() {
237 let baseline = BitmapFrameAllocator::free_frames();
238 let batch = spawn_batch_with_sched(1000, 10_000, 100_000, spread_priority);
239
240 let runnable = 100usize;
241 {
242 let mut ptable = PROCESSES.lock();
243 let base_us = tsc::cycles_to_ns(tsc::read_tsc()) / 1000;
244 ptable.timer_seed(base_us);
245
246 batch.pids.iter().skip(runnable).enumerate().for_each(|(i, &pid)| {
247 ptable.simulate_dispatch(pid);
248 let deadline = base_us + 100_000 + (i as u64) * 100;
249 ptable.timer_insert(pid, deadline);
250 });
251 }
252
253 {
254 let mut ptable = PROCESSES.lock();
255 (0..50).for_each(|_| {
256 if let Some(pid) = ptable.dequeue_highest() {
257 ptable.enqueue_ready(pid);
258 }
259 });
260 }
261
262 let iterations = 100usize;
263 let mut max_ns = 0u64;
264 let mut total_ns = 0u64;
265
266 (0..iterations).for_each(|_| {
267 let start = tsc::read_tsc_fenced();
268 let mut ptable = PROCESSES.lock();
269 let mut pool = POOL.lock_after(&ptable);
270 crate::sched::advance_timer_wheel_test(&mut ptable, &mut pool);
271 drop(pool);
272 if let Some(pid) = ptable.dequeue_highest() {
273 ptable.enqueue_ready(pid);
274 }
275 drop(ptable);
276 let end = tsc::read_tsc_fenced();
277
278 let ns = tsc::cycles_to_ns(end.saturating_sub(start));
279 total_ns += ns;
280 max_ns = max_ns.max(ns);
281 });
282
283 let avg_ns = total_ns / iterations as u64;
284
285 crate::kprintln!(
286 "[sched_latency] integrated tick (1000t, {}r): avg={}ns, max={}ns",
287 runnable,
288 avg_ns,
289 max_ns,
290 );
291
292 assert!(
293 max_ns < 50_000,
294 "worst-case tick {}ns exceeds 50us",
295 max_ns,
296 );
297 assert!(
298 avg_ns < 25_000,
299 "avg tick {}ns exceeds 25us",
300 avg_ns,
301 );
302
303 destroy_batch_and_verify(&batch, baseline);
304 }
305);