Phase 52

Kernel Architecture Evolution

Phase 52c established the architecture direction for per-core scheduling, growable IPC resources, a unified kernel-side line discipline, O(log n) VMA lookup, and ISR wakeup improvements. In the checked-in tree, the VMA tree, growable endpoint/capability/service tables, `LineDiscipline`, the live `push_raw_input` keyboard path, and the ISR wake queue all landed. Phase 52d then recorded the remaining honest limits: the scheduler hot path still relies on the global `SCHEDULER` lock, and notifications remain fixed-size for ISR safety.

Complete

Learning goal

Understand per-core scheduling with work-stealing (Zircon: WAVL-tree fair scheduler with `StealWork()`)

Why this phase matters

Phase 52c established the architecture direction for per-core scheduling, growable IPC resources, a unified kernel-side line discipline, O(log n) VMA lookup, and ISR wakeup improvements. In the checked-in tree, the VMA tree, growable endpoint/capability/service tables, LineDiscipline, the live push_raw_input keyboard path, and the ISR wake queue all landed. Phase 52d then recorded the remaining honest limits: the scheduler hot path still relies on the global SCHEDULER lock, and notifications remain fixed-size for ISR safety.

How it works in m3OS

Phase 52c addresses five scalability bottlenecks and design limitations that would constrain Phase 53+ work. It introduced per-core run queues and work-stealing, growable endpoint/capability/service tables, a shared kernel line-discipline path, O(log n) VMA lookup, and ISR-delivered wake queues. Phase 52d then closed the live keyboard-path convergence and recorded the two remaining honest limits: dispatch still acquires the global SCHEDULER lock, and notifications remain fixed-size for ISR safety.

How it builds on earlier phases

This phase builds on Kernel Structural Hardening and turns that foundation into Kernel Architecture Evolution.

Implementation outline

Replace SCHEDULER with TaskRegistry + per-core PerCoreScheduler
Implement work-stealing in pick_next
Re-enable load balancing with per-task cooldown
Replace EndpointRegistry fixed array with growable EndpointPool
Replace CapabilityTable fixed array with growable Vec
Replace notification and service registry fixed arrays similarly
Create LineDiscipline in kernel-core/src/tty.rs
Refactor serial_stdin_feeder_task to use LineDiscipline
Add push_raw_input syscall
Simplify stdin_feeder to scancode decode + push_raw_input
Replace Vec<MemoryMapping> with BTreeMap in AddressSpace
Add per-core IsrWakeQueue ring buffer
Modify signal_irq to push to IsrWakeQueue when waiter is registered
Drain IsrWakeQueue on every scheduler loop iteration

Task progress snapshot

46 of 49 tracked tasks are complete.

Documentation targets

Documentation deliverables have not been listed yet.

Deferred follow-on work

Full fair scheduler with virtual runtime (Zircon WAVL / Linux CFS) — current priority + round-robin is sufficient
True per-core scheduling (lock-free dispatch hot path) — per-core run queues and work-stealing landed, but task state transitions still require the global SCHEDULER lock; splitting task ownership per-core is a larger architectural change deferred past Phase 52
Growable notification pool — notifications remain fixed-size (MAX_NOTIFS = 64) because ISR-safe access requires lock-free fixed-size arrays; a two-level design (fixed ISR-visible table + growable overflow) is possible but not needed at current scale
Atomic reply_recv (seL4-style) — nice optimization but not critical
Preemptive scheduling from interrupt context — requires deeper switch_context redesign
Dynamic PTY pool — can grow the fixed array to a larger number as a simpler intermediate step

Source materials

Important code

Code spotlight cards

Define PerCoreScheduler and TaskRegistry. Why it matters: The current global SCHEDULER: Mutex<Scheduler> is a contention bottleneck on multi-core systems. All scheduler operations (spawn, wake, pick_next, block) acquire this lock. Focus on `PerCoreScheduler` and `TaskRegistry` in `kernel/src/task/scheduler.rs` while you trace the snippet.

    /// Pick the next task to run on the given core.
    ///
    /// Selects from the per-core run queue (highest priority first), then
    /// attempts work-stealing from other cores, then falls back to the
    /// idle task.
    ///
    /// NOTE: this method is called while the caller holds `SCHEDULER.lock()`,
    /// so it has access to the full `tasks` vec for state validation. True
    /// lock-free per-core dispatch is deferred (see module-level doc).
    fn pick_next(&mut self, core_id: u8) -> Option<(u64, usize)> {
        let core_bit = 1u64 << core_id;

        // Phase 1: Scan local run queue — highest-priority (lowest numeric)
        // Ready task in a single pass.
        if let Some(idx) = self.dequeue_local(core_id, core_bit) {
            self.last_run = idx;
            return Some((self.tasks[idx].saved_rsp, idx));
        }

        // Phase 2: Work-stealing — try to steal one task from another core
        // (Phase 52c A.2).
        if let Some(idx) = self.try_steal(core_id, core_bit) {
            self.tasks[idx].assigned_core = core_id;
            self.tasks[idx].last_migrated_tick = crate::arch::x86_64::interrupts::tick_count();

View on GitHub

Generation-based task slot reuse. Why it matters: The current SCHEDULER.tasks vec only grows. Dead tasks keep their index. Over time, the vec becomes large. Generation-based reuse prevents ABA races on recycled slots. Focus on `TaskHandle` and `TaskRegistry` in `kernel/src/task/mod.rs` while you trace the snippet.

View on GitHub

Growable endpoint pool. Why it matters: MAX_ENDPOINTS = 16 limits the number of concurrent services. Phase 54 (Deep Serverization) will need many more endpoints. Focus on `EndpointPool` in `kernel/src/ipc/endpoint.rs` while you trace the snippet.

View on GitHub

Key files

userspace/stdin_feeder — Completed. userspace/stdin_feeder now forwards raw
kernel/src/ipc/notification.rs — MAX_NOTIFS=64, ISR_WAITERS mirror, signal_irq enhancement
kernel-core/src/tty.rs — LineDiscipline, SmallVec, LdiscResult (20 unit tests)
kernel/src/task/scheduler.rs — Per-core dispatch, work-stealing, task slot reuse, load balancing
kernel/src/task/mod.rs — Task struct with last_migrated_tick for cooldown
kernel/src/ipc/endpoint.rs — Growable endpoint pool with Vec
kernel-core/src/ipc/capability.rs — Growable capability table with Vec
kernel-core/src/ipc/registry.rs — Growable service registry with Vec
kernel/src/tty.rs — TtyState wraps LineDiscipline
kernel/src/arch/x86_64/syscall/mod.rs — push_raw_input syscall (0x1010)
kernel-core/src/mm.rs — VmaTree with BTreeMap (23 unit tests)
kernel/src/process/mod.rs — Process uses VmaTree instead of Vec
kernel/src/smp/mod.rs — IsrWakeQueue, try_per_core()
userspace/syscall-lib/src/lib.rs — push_raw_input wrapper

How real OSes differ

Zircon uses a hybrid WAVL-tree fair scheduler with per-CPU queues, deadline scheduling, and cluster-aware work-stealing. m3OS's simpler VecDeque-based approach is sufficient for its scale.
Linux's CFS uses a red-black tree of virtual runtime values. The EEVDF extension adds virtual deadline ordering.
seL4 uses a two-level bitmap for O(1) priority selection — much simpler than tree-based fair schedulers, but appropriate for a formally verified kernel.
MINIX3 uses a 16-queue multilevel feedback scheduler with a userspace SCHED server. The userspace scheduler concept is interesting but beyond m3OS's current scope.
Linux's N_TTY line discipline handles all terminal processing in kernel space. This is the model m3OS should follow for its unified ldisc.

Success criteria

Scheduler dispatch path does not acquire a global lock *(deferred — see Post-Phase Audit Note; global lock still acquired in HEAD; per-core run queues and work-stealing provide dispatch locality but task state transitions require the global SCHEDULER lock; true lock-free per-core dispatch deferred to a future phase)*
IPC can create more than 16 endpoints without exhaustion
A process can hold more than 64 capabilities
Only one line discipline implementation exists in the codebase (kernel-side) *(partial — see Post-Phase Audit Note; stdin_feeder still duplicates ldisc logic)*
`stdin_feeder` does not contain any canonical editing, echo, or ISIG logic *(partial — see Post-Phase Audit Note)*
VMA lookup for a process with 100 mappings is measurably faster than current
Keyboard IRQ → kbd_server wakeup latency is under 1ms (not 10ms)
`cargo xtask check` and `cargo xtask test` pass

Related phases

Keep exploring the roadmap

Kernel Structural Hardening

The kernel's memory management, context management, and TLB coherence subsystems move onto the structurally hardened path defined by this phase. In the checked-in tree, the AddressSpace object, typed user buffers, batched TLB work, and frame zeroing landed, and Phase 52d completed the remaining closure work so the task-owned return-state and generation-tracking story now matches the shipped implementation end to end.

Kernel Completion And Roadmap Alignment

The Phase 52 follow-on work now matches reality: the roadmap truthfully describes what landed, syscall return state is task-owned end-to-end, keyboard input uses the kernel line discipline instead of a ring-3 clone, the integrated boot/login path survives the former `rt_sigaction` stall, generated initrd payloads no longer dirty the source tree, and the smoke/regression gates for login, fork, ion, and PTY flows are trustworthy again.