Nothing to see here, move along meow
1pub mod context;
2pub mod switch;
3
4use core::sync::atomic::{AtomicBool, Ordering};
5#[cfg(lancer_test)]
6use core::sync::atomic::AtomicU64;
7
8use lancer_core::object_layout::{EndpointObject, SchedContextObject};
9
10use crate::arch::syscall as arch_syscall;
11use crate::cap::pool::{ObjectPool, POOL};
12use crate::mem::phys::BitmapFrameAllocator;
13use crate::proc::BlockedReason;
14use crate::proc::context::CpuContext;
15use crate::proc::{PROCESSES, ProcessManager, ProcessState};
16use crate::static_vec::StaticVec;
17use crate::types::{MAX_PIDS, ObjPhys, Pid, Priority};
18use crate::wcet::tsc;
19
20static SCHEDULER_ACTIVE: AtomicBool = AtomicBool::new(false);
21
22#[cfg(lancer_test)]
23static LAST_TICK_CYCLES: AtomicU64 = AtomicU64::new(0);
24
25#[cfg(lancer_test)]
26pub fn last_tick_cycles() -> u64 {
27 LAST_TICK_CYCLES.load(Ordering::Relaxed)
28}
29
30#[cfg(lancer_test)]
31pub fn advance_timer_wheel_test(ptable: &mut ProcessManager, pool: &mut ObjectPool) {
32 advance_timer_wheel(ptable, pool);
33}
34
35pub fn init() {
36 SCHEDULER_ACTIVE.store(true, Ordering::Release);
37 arch_syscall::set_last_switch_tsc(tsc::read_tsc());
38 crate::kprintln!(" Scheduler initialized (O(1) run queue + timer wheel)");
39}
40
41pub fn seed_timer_wheel() {
42 let now_us = tsc::cycles_to_ns(tsc::read_tsc()) / 1000;
43 PROCESSES.lock().timer_seed(now_us);
44}
45
46pub fn is_active() -> bool {
47 SCHEDULER_ACTIVE.load(Ordering::Acquire)
48}
49
50fn drain_zombies() {
51 let mut ptable = PROCESSES.lock();
52 let mut allocator = BitmapFrameAllocator;
53 let cap = ptable.capacity();
54 let mut batch = StaticVec::<Pid, 32>::new();
55 (0..cap as u32)
56 .filter_map(Pid::try_new)
57 .filter(|&pid| {
58 ptable
59 .get(pid)
60 .is_some_and(|s| s.state() == ProcessState::Zombie)
61 })
62 .for_each(|pid| {
63 let _ = batch.push(pid);
64 });
65 batch
66 .iter()
67 .for_each(|&pid| ptable.reap(pid, &mut allocator));
68}
69
70pub fn current() -> Pid {
71 arch_syscall::current_pid()
72}
73
74pub(crate) fn set_current(pid: Pid) {
75 arch_syscall::set_current_pid(pid);
76}
77
78fn take_elapsed_us() -> (u64, u64) {
79 let now = tsc::read_tsc();
80 let last = arch_syscall::last_switch_tsc();
81 let delta = now.saturating_sub(last);
82 arch_syscall::set_last_switch_tsc(now);
83 let now_us = tsc::cycles_to_ns(now) / 1000;
84 let elapsed_us = tsc::cycles_to_ns(delta) / 1000;
85 (elapsed_us, now_us)
86}
87
88fn update_budget_and_handle_exhaustion(
89 pid: Pid,
90 elapsed_us: u64,
91 now_us: u64,
92 ptable: &mut ProcessManager,
93 pool: &mut ObjectPool,
94) -> bool {
95 let Some((sc_id, sc_gen)) = ptable[pid].sched_context() else {
96 return false;
97 };
98 match pool.write_as::<SchedContextObject>(sc_id, sc_gen) {
99 Ok(sc) => {
100 context::consume(sc, elapsed_us, now_us);
101 match context::is_exhausted(sc) {
102 true => {
103 let period_us = sc.period_us;
104 let replenish_us = match period_us {
105 0 => now_us + 1000,
106 _ => now_us + period_us,
107 };
108 ptable.timer_insert(pid, replenish_us);
109 true
110 }
111 false => false,
112 }
113 }
114 Err(e) => {
115 crate::kprintln!(
116 "[sched] update_budget: sched context lookup failed for pid {}: {:?}",
117 pid.raw(),
118 e
119 );
120 false
121 }
122 }
123}
124
125fn replenish_batch(
126 ptable: &mut ProcessManager,
127 pool: &mut ObjectPool,
128 batch: &StaticVec<u32, 64>,
129 now_us: u64,
130) {
131 batch.iter().for_each(|&pid_raw| {
132 let Some(pid) = Pid::try_new(pid_raw) else {
133 return;
134 };
135 let Some((sc_id, sc_gen)) = ptable.get(pid).and_then(|s| s.sched_context()) else {
136 return;
137 };
138 if let Ok(sc) = pool.write_as::<SchedContextObject>(sc_id, sc_gen) {
139 context::replenish(sc, now_us);
140 }
141 if ptable.get(pid).is_some_and(|s| {
142 s.state() == ProcessState::Ready
143 && s.run_next == lancer_core::header::NONE_SENTINEL
144 && s.run_prev == lancer_core::header::NONE_SENTINEL
145 }) {
146 ptable.enqueue_ready(pid);
147 }
148 });
149}
150
151const MAX_ADVANCE_US: u64 = 10_000;
152
153fn advance_timer_wheel(ptable: &mut ProcessManager, pool: &mut ObjectPool) {
154 let now_us = tsc::cycles_to_ns(tsc::read_tsc()) / 1000;
155
156 let clamped_us = now_us.min(
157 ptable.timer_current_tick().saturating_add(MAX_ADVANCE_US),
158 );
159
160 const MAX_ROUNDS: usize = 8;
161 (0..MAX_ROUNDS)
162 .take_while(|_| {
163 let mut batch = StaticVec::<u32, 64>::new();
164 let mut full = false;
165
166 ptable.timer_advance(clamped_us, |pid_raw| {
167 if batch.push(pid_raw).is_err() {
168 full = true;
169 }
170 });
171
172 let had_work = !batch.is_empty();
173 replenish_batch(ptable, pool, &batch, now_us);
174 had_work && full
175 })
176 .count();
177}
178
179pub fn boost_effective(ptable: &mut ProcessManager, pid: Pid, donor_priority: Priority) {
180 if let Some(sched) = ptable.get_mut(pid) {
181 sched.boost_effective_priority(donor_priority);
182 }
183}
184
185pub fn propagate_priority(
186 ptable: &mut ProcessManager,
187 pool: &ObjectPool,
188 start_pid: Pid,
189 donor_priority: Priority,
190) {
191 let mut current_pid = start_pid;
192 let mut visited = [false; MAX_PIDS];
193 core::iter::repeat_n((), MAX_PIDS)
194 .take_while(|()| {
195 let idx = current_pid.as_usize();
196 if visited[idx] {
197 crate::show!(
198 sched,
199 warn,
200 "priority propagation cycle at pid {}",
201 current_pid.raw()
202 );
203 return false;
204 }
205 visited[idx] = true;
206
207 let Some(sched) = ptable.get_mut(current_pid) else {
208 return false;
209 };
210
211 if donor_priority <= sched.effective_priority() {
212 return false;
213 }
214 sched.boost_effective_priority(donor_priority);
215
216 let reason = match sched.blocked_reason() {
217 Some(r) => r,
218 None => return false,
219 };
220
221 let (ep_obj_id, ep_gen) = match reason {
222 BlockedReason::Sending(id, generation)
223 | BlockedReason::Receiving(id, generation)
224 | BlockedReason::Calling(id, generation) => (id, generation),
225 BlockedReason::WaitingNotification(_, _) => return false,
226 };
227
228 let holder = pool
229 .read_as::<EndpointObject>(ep_obj_id, ep_gen)
230 .ok()
231 .and_then(|ep| Pid::try_new(ep.holder));
232
233 match holder {
234 Some(h) if h != current_pid => {
235 current_pid = h;
236 true
237 }
238 _ => false,
239 }
240 })
241 .count();
242}
243
244pub fn reset_effective(ptable: &mut ProcessManager, pid: Pid) {
245 if let Some(sched) = ptable.get_mut(pid) {
246 sched.reset_effective_priority();
247 }
248}
249
250pub fn recalculate_effective(
251 ptable: &mut ProcessManager,
252 pid: Pid,
253 queue: &crate::cap::object::PidQueue,
254) {
255 let Some(sched) = ptable.get_mut(pid) else {
256 return;
257 };
258 sched.reset_effective_priority();
259
260 let max_donor = core::iter::successors(queue.head, |&cur| ptable[cur].next_ipc)
261 .take(MAX_PIDS)
262 .fold(Priority::IDLE, |best, sender| {
263 let prio = ptable[sender].effective_priority();
264 if prio > best { prio } else { best }
265 });
266
267 if max_donor > Priority::IDLE {
268 ptable[pid].boost_effective_priority(max_donor);
269 }
270}
271
272fn do_reschedule(ctx: &mut CpuContext, advance_timers: bool) {
273 let cur = current();
274 let (elapsed, now_us) = take_elapsed_us();
275
276 let needs_idle = {
277 let mut ptable = PROCESSES.lock();
278 let mut pool = POOL.lock_after(&ptable);
279
280 let exhausted =
281 update_budget_and_handle_exhaustion(cur, elapsed, now_us, &mut ptable, &mut pool);
282 if advance_timers {
283 advance_timer_wheel(&mut ptable, &mut pool);
284 }
285 drop(pool);
286
287 if exhausted
288 && ptable[cur].state() == ProcessState::Running
289 && ptable[cur].transition_to(ProcessState::Ready).is_err()
290 {
291 crate::kprintln!(
292 "[sched] BUG: pid {} failed Running -> Ready",
293 cur.raw()
294 );
295 }
296
297 let cur_must_yield = exhausted || !ptable[cur].is_runnable();
298
299 match ptable.dequeue_highest() {
300 Some(next) if next != cur => {
301 switch::switch_to(&mut ptable, cur, next, ctx);
302 false
303 }
304 Some(next) => {
305 ptable.enqueue_ready(next);
306 false
307 }
308 None if cur_must_yield => {
309 let exec = ptable.exec_mut(cur).unwrap();
310 exec.saved_context = *ctx;
311 exec.seal_context();
312 true
313 }
314 None => false,
315 }
316 };
317
318 if needs_idle {
319 idle_until_runnable(ctx);
320 }
321}
322
323pub fn timer_tick(ctx: &mut CpuContext) {
324 #[cfg(lancer_test)]
325 let tick_start = tsc::read_tsc();
326
327 drain_zombies();
328 if is_active() && !arch_syscall::is_idle() {
329 do_reschedule(ctx, true);
330 }
331
332 #[cfg(lancer_test)]
333 {
334 let tick_end = tsc::read_tsc();
335 LAST_TICK_CYCLES.store(tick_end.saturating_sub(tick_start), Ordering::Relaxed);
336 }
337}
338
339pub fn schedule(ctx: &mut CpuContext) {
340 drain_zombies();
341 if !is_active() {
342 return;
343 }
344
345 do_reschedule(ctx, false);
346}
347
348// WCET EXCEPTION: this loop is intentionally and unfortunately unbounded. The idle loop halts
349// the cpu until an interrupt fires. Each iteration has bounded work, but the *number* of
350// iterations depends on external events like timer, ipc, & irq. This is the only place in the
351// kernel where unbounded iteration is acceptable; the cpu would be halted doing nothing
352// otherwise!! - Lewis
353fn halt_until_runnable(
354) -> (Pid, crate::sync::IrqMutexGuard<'static, ProcessManager, 0>) {
355 arch_syscall::set_idle(true);
356 core::iter::repeat(())
357 .find_map(|()| {
358 x86_64::instructions::interrupts::enable_and_hlt();
359 x86_64::instructions::interrupts::disable();
360
361 drain_zombies();
362
363 let mut ptable = PROCESSES.lock();
364 let mut pool = POOL.lock_after(&ptable);
365 advance_timer_wheel(&mut ptable, &mut pool);
366 drop(pool);
367
368 ptable.dequeue_highest().map(|pid| (pid, ptable))
369 })
370 .expect("unreachable: repeat() is infinite")
371}
372
373struct DispatchPrep {
374 pml4: x86_64::PhysAddr,
375 fs_base: u64,
376 ctx: CpuContext,
377 sc_ctx: Option<(ObjPhys, crate::types::Generation)>,
378}
379
380fn prepare_dispatch(ptable: &mut ProcessManager, pid: Pid) -> DispatchPrep {
381 let sc_ctx = {
382 let sched = &mut ptable[pid];
383 if sched.state() != ProcessState::Running
384 && sched.transition_to(ProcessState::Running).is_err()
385 {
386 crate::kprintln!("[sched] BUG: pid {} failed -> Running", pid.raw());
387 }
388 sched.run_cpu = Some(arch_syscall::cpu_index() as u16);
389 sched.sched_context()
390 };
391
392 let exec = ptable.exec_mut(pid).unwrap();
393 exec.verify_context(pid);
394 let ctx = exec.saved_context;
395 ctx.validate_user(pid.raw());
396 arch_syscall::set_fpu_state_ptr(exec.fpu_state.data.as_mut_ptr());
397
398 DispatchPrep {
399 pml4: exec.pml4_phys.raw(),
400 fs_base: exec.fs_base,
401 ctx,
402 sc_ctx,
403 }
404}
405
406fn finalize_dispatch(pid: Pid, prep: &DispatchPrep) {
407 switch::write_fs_base(prep.fs_base);
408 arch_syscall::set_current_process(pid);
409 set_current(pid);
410 arch_syscall::set_last_switch_tsc(tsc::read_tsc());
411 arch_syscall::set_idle(false);
412
413 unsafe {
414 x86_64::registers::control::Cr3::write(
415 x86_64::structures::paging::PhysFrame::containing_address(prep.pml4),
416 x86_64::registers::control::Cr3Flags::empty(),
417 );
418 }
419}
420
421fn idle_until_runnable(ctx: &mut CpuContext) {
422 let (next, mut ptable) = halt_until_runnable();
423 let prep = prepare_dispatch(&mut ptable, next);
424
425 if let Some((sc_id, sc_gen)) = prep.sc_ctx {
426 let now_us = tsc::cycles_to_ns(tsc::read_tsc()) / 1000;
427 let mut pool = POOL.lock_after(&ptable);
428 if let Ok(sc) = pool.write_as::<SchedContextObject>(sc_id, sc_gen) {
429 context::mark_dispatched(sc, now_us);
430 }
431 }
432
433 drop(ptable);
434 *ctx = prep.ctx;
435 finalize_dispatch(next, &prep);
436}
437
438#[allow(dead_code)]
439pub fn rescue() -> ! {
440 let ptable = PROCESSES.lock();
441 rescue_with_ptable(ptable)
442}
443
444pub fn rescue_with_ptable(ptable: crate::sync::IrqMutexGuard<'_, ProcessManager, 0>) -> ! {
445 let (next, mut ptable) = {
446 let mut pt = ptable;
447 match pt.dequeue_highest() {
448 Some(pid) => (pid, pt),
449 None => {
450 drop(pt);
451 halt_until_runnable()
452 }
453 }
454 };
455
456 let prep = prepare_dispatch(&mut ptable, next);
457 ptable.exec_mut(next).unwrap().fpu_state.restore();
458 drop(ptable);
459
460 finalize_dispatch(next, &prep);
461 switch::enter_context(&prep.ctx)
462}