ADR-0001: Runtime Scheduling, Preemption, Interrupts and Lock Ordering

Relevant source files

• docs/decisions/0001-runtime-scheduling-locking.md 
• kernel/crates/kernel_run_queue/src 
• kernel/src/mcore/mtask/scheduler 

Status: Accepted with implementation gap (reschedule IPI pending). Date: 2026-07-14.

Context

An engineering audit found one global runnable queue, polling waits for process lifecycle and pipes, raw bring-up markers in production paths, and inconsistent interrupt/preemption rules. The runtime moved to per-CPU queues and one generation-checked wait protocol for timer, child-exit and pipe events; this ADR fixes those choices as required design rather than incidental implementation.

Decision

1. Each online CPU owns its current task and one runnable queue. New and woken tasks prefer their last CPU unless affinity or availability requires another.
2. Draft target, not implemented: remote producers may enqueue to a CPU and notify an idle target with a reschedule IPI; no runnable task may be in more than one queue. Today a wakeup enqueues to last_cpu() and runs when that CPU next reschedules.
3. Work stealing is best-effort, bounded by a victim-attempt limit and a maximum batch. A failed try_steal never spins.
4. Context-switch preparation runs with local interrupts masked and an exclusive, non-escaping scheduler borrow that ends before the assembly switch. No blocking, allocation, filesystem work or unbounded retry.
5. Interrupt handlers never sleep, allocate, take blocking locks, do filesystem I/O or log synchronously.
6. Task-context waits register under the producer’s condition lock, transition to waiting, release the lock, then reschedule. Wake, cancellation and exit are generation-checked.
7. Preemption-disabled sections are CPU-local and nest through a counter; they do not imply IRQ masking, but IRQ masking implies preemption is disabled.
8. Locks have explicit ranks with strictly increasing acquisition (plus a documented same-rank shard rule). Debug/test builds assert the held-rank stack.
9. Release builds compile out all log macros. audit-diagnostics and bringup-diagnostics are never part of a shipped profile.

Rank classes, outermost to innermost: 10 process tree / global registries; 20 process lifecycle and fd tables; 30 address-space and memory-region state; 40 VFS; 50 file, pipe and device objects; 60 BPF manager mutation; 70 BPF map and execution leases; 80 per-CPU scheduler / run queue; 90 per-CPU trace and interrupt bookkeeping. The scheduler accepts owned task/event values rather than callbacks so it never reaches back into lower ranks.

Future IPI contract

Scheduler owns destination policy; the APIC/GIC layer only transports a bounded request_reschedule(cpu). A per-target pending bit coalesces notifications (only clear-to-set sends), publication happens-before notification, the handler only latches a CPU-local request, the target clears the bit only at a scheduler boundary and rechecks its queue afterwards, and masking delays delivery but not publication.

The IPI may be implemented only after (a) a required SMP-4 regression (qemu-smp4-scheduler-smoke, planned, not landed) shows workers on all four CPUs exiting successfully, and (b) a repeatable measurement shows the no-IPI behavior misses an accepted wakeup-latency objective. SMP distribution alone does not justify it.

Required evidence

• Host/model tests for no duplicate/lost tasks and no lost wakeups (the kernel_run_queue crate carries a Loom model).
• SMP QEMU tests for local scheduling, remote wakeups, bounded stealing, affinity, cancellation, interruption and task-exit cleanup.
• Static release-gate checks rejecting allocation, synchronous logging, manager locking and unbounded loops in scheduler and interrupt hot paths.