kata (processes) and sensei (scheduler) using CFS lite system

6 files changed, 491 insertions, 40 deletions

diff --git a/mirai/boot/sequence.zig b/mirai/boot/sequence.zig
index b876d57..6242440 100644
--- a/mirai/boot/sequence.zig
+++ b/mirai/boot/sequence.zig
@@ -7,12 +7,15 @@ const gdt = @import("gdt.zig");
 const gpt = @import("../fs/gpt.zig");
 const heap = @import("../memory/heap.zig");
 const idt = @import("../interrupts/idt.zig");
+const kata = @import("../kata/kata.zig");
 const keyboard = @import("../drivers/keyboard.zig");
 const multiboot = @import("multiboot2.zig");
 const paging = @import("../memory/paging.zig");
 const pci = @import("../drivers/pci.zig");
 const pmm = @import("../memory/pmm.zig");
+const sensei = @import("../kata/sensei.zig");
 const serial = @import("../drivers/serial.zig");
+const shift = @import("../kata/shift.zig");
 const terminal = @import("../terminal.zig");
 const tss = @import("tss.zig");
 
@@ -79,6 +82,18 @@ pub fn run(multiboot_info_addr: u64) void {
     heap.init();
     boot_ok();
 
+    boot_print("Initializing Kata management... ");
+    kata.init();
+    boot_ok();
+
+    boot_print("Initializing Sensei scheduler... ");
+    sensei.init();
+    boot_ok();
+
+    boot_print("Initializing context shifting... ");
+    shift.init();
+    boot_ok();
+
     boot_print("Setting up task state segment... ");
     tss.init();
     boot_ok();
diff --git a/mirai/interrupts/idt.zig b/mirai/interrupts/idt.zig
index 106a129..733fec6 100644
--- a/mirai/interrupts/idt.zig
+++ b/mirai/interrupts/idt.zig
@@ -1,7 +1,8 @@
 //! Interrupt Descriptor Table - IDT setup and IRQ routing
 
-const serial = @import("../drivers/serial.zig");
 const exceptions = @import("../crimson/exceptions.zig");
+const sensei = @import("../kata/sensei.zig");
+const serial = @import("../drivers/serial.zig");
 
 const IDTEntry = packed struct {
     offset_low: u16,
@@ -103,53 +104,18 @@ comptime {
         \\  pop %rax
         \\  iretq
     );
-
-    asm (
-        \\.global int80_handler
-        \\int80_handler:
-        \\  push %rax
-        \\  push %rbx
-        \\  push %rcx
-        \\  push %rdx
-        \\  push %rsi
-        \\  push %rdi
-        \\  push %rbp
-        \\  push %r8
-        \\  push %r9
-        \\  push %r10
-        \\  push %r11
-        \\  push %r12
-        \\  push %r13
-        \\  push %r14
-        \\  push %r15
-        \\  call test_interrupt_handler
-        \\  pop %r15
-        \\  pop %r14
-        \\  pop %r13
-        \\  pop %r12
-        \\  pop %r11
-        \\  pop %r10
-        \\  pop %r9
-        \\  pop %r8
-        \\  pop %rbp
-        \\  pop %rdi
-        \\  pop %rsi
-        \\  pop %rdx
-        \\  pop %rcx
-        \\  pop %rbx
-        \\  pop %rax
-        \\  iretq
-    );
 }
 
 extern fn irq0_handler() void;
 extern fn irq1_handler() void;
-extern fn int80_handler() void;
 extern fn keyboard_handler() void;
 
 export fn timer_handler() void {
     tick_count += 1;
 
+    // Let Sensei schedule Kata on each tick
+    sensei.on_tick();
+
     // Send EOI to PIC
     outb(0x20, 0x20);
 }
diff --git a/mirai/kata/kata.zig b/mirai/kata/kata.zig
new file mode 100644
index 0000000..a7097fd
--- /dev/null
+++ b/mirai/kata/kata.zig
@@ -0,0 +1,163 @@
+//! Kata Control Block - Kernel's representation of a running persona program
+//! Kata (形) = Form/pattern - a program's execution form
+
+const paging = @import("../memory/paging.zig");
+const serial = @import("../drivers/serial.zig");
+
+pub const KataState = enum {
+    Ready, // Ready to execute
+    Running, // Currently executing
+    Waiting, // Waiting for I/O or event
+    Dissolved, // Terminated
+};
+
+pub const Kata = struct {
+    // Kata identification
+    id: u32, // Kata ID (like PID)
+
+    // Execution state
+    state: KataState,
+
+    // Saved registers (for context shifting)
+    context: Context,
+
+    // Memory management
+    page_table: u64, // CR3 value (physical address of PML4)
+    stack_top: u64, // Top of kernel stack
+    user_stack_top: u64, // Top of user stack
+
+    // Location tracking (current stack/cluster in AFS)
+    current_location: [256]u8,
+    current_location_len: usize,
+    current_cluster: u32,
+
+    // Lineage
+    parent_id: u32, // Parent Kata ID
+
+    // CFS-lite scheduling
+    vruntime: u64, // Virtual runtime (nanoseconds)
+    weight: u32, // Priority weight (default 1024)
+    last_run: u64, // Last time this Kata ran
+
+    // Linked list for sorted vruntime queue (simple CFS-lite)
+    next: ?*Kata,
+};
+
+// Saved CPU context for context shifting
+pub const Context = struct {
+    // General purpose registers
+    rax: u64 = 0,
+    rbx: u64 = 0,
+    rcx: u64 = 0,
+    rdx: u64 = 0,
+    rsi: u64 = 0,
+    rdi: u64 = 0,
+    rbp: u64 = 0,
+    rsp: u64 = 0,
+    r8: u64 = 0,
+    r9: u64 = 0,
+    r10: u64 = 0,
+    r11: u64 = 0,
+    r12: u64 = 0,
+    r13: u64 = 0,
+    r14: u64 = 0,
+    r15: u64 = 0,
+
+    // Instruction pointer and flags
+    rip: u64 = 0,
+    rflags: u64 = 0x202, // Interrupts enabled by default
+
+    // Segment selectors
+    cs: u64 = 0,
+    ss: u64 = 0,
+};
+
+// Kata table (pool of all Kata slots)
+const MAX_KATA: usize = 256;
+var kata_pool: [MAX_KATA]Kata = undefined;
+var kata_used: [MAX_KATA]bool = [_]bool{false} ** MAX_KATA;
+var next_kata_id: u32 = 1;
+
+pub fn init() void {
+    serial.print("\n=== Kata Management ===\n");
+
+    // Initialize all Kata slots
+    for (&kata_pool, 0..) |*kata, i| {
+        kata.* = Kata{
+            .id = 0,
+            .state = .Dissolved,
+            .context = Context{},
+            .page_table = 0,
+            .stack_top = 0,
+            .user_stack_top = 0,
+            .current_location = undefined,
+            .current_location_len = 1,
+            .current_cluster = 0,
+            .parent_id = 0,
+            .vruntime = 0,
+            .weight = 1024,
+            .last_run = 0,
+            .next = null,
+        };
+        kata_used[i] = false;
+    }
+
+    serial.print("Kata pool initialized (");
+    serial.print_hex(MAX_KATA);
+    serial.print(" slots)\n");
+}
+
+pub fn create_kata() !*Kata {
+    // Find free slot in pool
+    for (&kata_pool, 0..) |*kata, i| {
+        if (!kata_used[i]) {
+            kata_used[i] = true;
+
+            const kata_id = next_kata_id;
+            next_kata_id += 1;
+
+            kata.* = Kata{
+                .id = kata_id,
+                .state = .Ready,
+                .context = Context{},
+                .page_table = 0,
+                .stack_top = 0,
+                .user_stack_top = 0,
+                .current_location = undefined,
+                .current_location_len = 1,
+                .current_cluster = 0,
+                .parent_id = 0,
+                .vruntime = 0,
+                .weight = 1024,
+                .last_run = 0,
+                .next = null,
+            };
+
+            // Initialize location to root
+            kata.current_location[0] = '/';
+
+            return kata;
+        }
+    }
+
+    return error.TooManyKata;
+}
+
+pub fn get_kata(kata_id: u32) ?*Kata {
+    for (&kata_pool, 0..) |*kata, i| {
+        if (kata_used[i] and kata.id == kata_id) {
+            return kata;
+        }
+    }
+    return null;
+}
+
+pub fn dissolve_kata(kata_id: u32) void {
+    for (&kata_pool, 0..) |*kata, i| {
+        if (kata_used[i] and kata.id == kata_id) {
+            kata.state = .Dissolved;
+            kata_used[i] = false;
+            return;
+        }
+    }
+}
diff --git a/mirai/kata/sensei.zig b/mirai/kata/sensei.zig
new file mode 100644
index 0000000..1d72e06
--- /dev/null
+++ b/mirai/kata/sensei.zig
@@ -0,0 +1,159 @@
+//! Sensei - The Kata scheduler using CFS-lite algorithm
+//! Sensei (先生) = Teacher/master who guides all Kata
+
+const kata_mod = @import("kata.zig");
+const idt = @import("../interrupts/idt.zig");
+const serial = @import("../drivers/serial.zig");
+const shift = @import("shift.zig");
+
+const Kata = kata_mod.Kata;
+
+// Sorted run queue (by vruntime)
+var run_queue_head: ?*Kata = null;
+var current_kata: ?*Kata = null;
+
+// Minimum vruntime in system (for new Kata fairness)
+var min_vruntime: u64 = 0;
+
+// Timer tick counter
+var tick_count: u64 = 0;
+
+const TICK_NANOSECONDS: u64 = 1_000_000; // 1ms per tick
+
+pub fn init() void {
+    serial.print("\n=== Sensei Scheduler ===\n");
+    serial.print("CFS-lite algorithm initialized\n");
+    serial.print("Tick interval: 1ms\n");
+}
+
+// Add Kata to run queue (sorted by vruntime)
+pub fn enqueue_kata(new_kata: *Kata) void {
+    new_kata.state = .Ready;
+
+    // If queue is empty
+    if (run_queue_head == null) {
+        run_queue_head = new_kata;
+        new_kata.next = null;
+        return;
+    }
+
+    // Insert sorted by vruntime (lowest first)
+    var prev: ?*Kata = null;
+    var current = run_queue_head;
+
+    while (current) |curr| {
+        if (new_kata.vruntime < curr.vruntime) {
+            // Insert before current
+            new_kata.next = curr;
+            if (prev) |p| {
+                p.next = new_kata;
+            } else {
+                run_queue_head = new_kata;
+            }
+            return;
+        }
+        prev = curr;
+        current = curr.next;
+    }
+
+    // Insert at end
+    if (prev) |p| {
+        p.next = new_kata;
+        new_kata.next = null;
+    }
+}
+
+// Remove Kata from run queue
+pub fn dequeue_kata(target_kata: *Kata) void {
+    if (run_queue_head == null) return;
+
+    // Check head
+    if (run_queue_head == target_kata) {
+        run_queue_head = target_kata.next;
+        target_kata.next = null;
+        return;
+    }
+
+    // Search list
+    var prev = run_queue_head;
+    while (prev) |p| {
+        if (p.next == target_kata) {
+            p.next = target_kata.next;
+            target_kata.next = null;
+            return;
+        }
+        prev = p.next;
+    }
+}
+
+// Pick next Kata to run (lowest vruntime)
+pub fn pick_next_kata() ?*Kata {
+    return run_queue_head;
+}
+
+// Called on timer tick
+// Called on timer tick
+pub fn on_tick() void {
+    tick_count += 1;
+
+    if (current_kata) |kata| {
+        // Update vruntime based on weight
+        // vruntime += (real_time * 1024) / weight
+        const delta = (TICK_NANOSECONDS * 1024) / kata.weight;
+        kata.vruntime += delta;
+
+        // Update min_vruntime
+        if (run_queue_head) |head| {
+            min_vruntime = head.vruntime;
+        } else {
+            min_vruntime = kata.vruntime;
+        }
+
+        // Check if we should shift (every 10ms)
+        if (tick_count % 10 == 0) {
+            schedule();
+        }
+    }
+}
+
+// Main scheduling decision
+pub fn schedule() void {
+    const next = pick_next_kata();
+
+    if (next == null and current_kata == null) {
+        // Nothing to run
+        return;
+    }
+
+    // If same Kata, keep running
+    if (next == current_kata) {
+        return;
+    }
+
+    // Save current Kata and shift to next
+    if (current_kata) |curr| {
+        if (curr.state == .Running) {
+            curr.state = .Ready;
+            enqueue_kata(curr);
+        }
+    }
+
+    if (next) |n| {
+        dequeue_kata(n);
+        n.state = .Running;
+        current_kata = n;
+
+        serial.print("Sensei: Shifting to Kata ");
+        serial.print_hex(n.id);
+        serial.print(" (vruntime: ");
+        serial.print_hex(n.vruntime);
+        serial.print(")\n");
+
+        // Perform context shift
+        shift.shift_to_kata(n);
+    }
+}
+
+pub fn get_current_kata() ?*Kata {
+    return current_kata;
+}
diff --git a/mirai/kata/shift.zig b/mirai/kata/shift.zig
new file mode 100644
index 0000000..81c57aa
--- /dev/null
+++ b/mirai/kata/shift.zig
@@ -0,0 +1,148 @@
+//! Context Shifting - Save and restore Kata execution state
+//! Shifts between different Kata, preserving their execution context
+
+const kata_mod = @import("kata.zig");
+const gdt = @import("../boot/gdt.zig");
+const tss = @import("../boot/tss.zig");
+const serial = @import("../drivers/serial.zig");
+
+const Kata = kata_mod.Kata;
+const Context = kata_mod.Context;
+
+// Current executing Kata (for saving context on interrupts)
+var current_context: ?*Context = null;
+
+pub fn init() void {
+    serial.print("\n=== Context Shifting ===\n");
+    serial.print("Shift mechanism initialized\n");
+}
+
+// Shift to a new Kata
+pub fn shift_to_kata(target_kata: *Kata) void {
+    // Update TSS kernel stack for this Kata
+    tss.set_kernel_stack(target_kata.stack_top);
+
+    // Switch to Kata's page table
+    set_page_table(target_kata.page_table);
+
+    // Set current context pointer (for saving on interrupts)
+    current_context = &target_kata.context;
+
+    // Perform the actual context shift
+    shift_context(&target_kata.context);
+}
+
+// Save current context (called from interrupt handlers)
+pub fn save_current_context(int_context: *const InterruptContext) void {
+    if (current_context) |ctx| {
+        ctx.rax = int_context.rax;
+        ctx.rbx = int_context.rbx;
+        ctx.rcx = int_context.rcx;
+        ctx.rdx = int_context.rdx;
+        ctx.rsi = int_context.rsi;
+        ctx.rdi = int_context.rdi;
+        ctx.rbp = int_context.rbp;
+        ctx.rsp = int_context.rsp;
+        ctx.r8 = int_context.r8;
+        ctx.r9 = int_context.r9;
+        ctx.r10 = int_context.r10;
+        ctx.r11 = int_context.r11;
+        ctx.r12 = int_context.r12;
+        ctx.r13 = int_context.r13;
+        ctx.r14 = int_context.r14;
+        ctx.r15 = int_context.r15;
+        ctx.rip = int_context.rip;
+        ctx.rflags = int_context.rflags;
+        ctx.cs = int_context.cs;
+        ctx.ss = int_context.ss;
+    }
+}
+
+// Interrupt context (matches interrupt stack frame)
+pub const InterruptContext = packed struct {
+    r15: u64,
+    r14: u64,
+    r13: u64,
+    r12: u64,
+    r11: u64,
+    r10: u64,
+    r9: u64,
+    r8: u64,
+    rbp: u64,
+    rdi: u64,
+    rsi: u64,
+    rdx: u64,
+    rcx: u64,
+    rbx: u64,
+    rax: u64,
+    int_num: u64,
+    error_code: u64,
+    rip: u64,
+    cs: u64,
+    rflags: u64,
+    rsp: u64,
+    ss: u64,
+};
+
+// Low-level context shift (assembly)
+fn shift_context(ctx: *const Context) void {
+    asm volatile (
+        \\# Restore general purpose registers
+        \\mov %[rax], %%rax
+        \\mov %[rbx], %%rbx
+        \\mov %[rcx], %%rcx
+        \\mov %[rdx], %%rdx
+        \\mov %[rsi], %%rsi
+        \\mov %[rdi], %%rdi
+        \\mov %[r8], %%r8
+        \\mov %[r9], %%r9
+        \\mov %[r10], %%r10
+        \\mov %[r11], %%r11
+        \\mov %[r12], %%r12
+        \\mov %[r13], %%r13
+        \\mov %[r14], %%r14
+        \\mov %[r15], %%r15
+        \\
+        \\# Restore RBP last (after using it to access context)
+        \\mov %[rbp], %%rbp
+        \\
+        \\# Build iretq frame on stack
+        \\pushq %[ss]
+        \\pushq %[rsp]
+        \\pushq %[rflags]
+        \\pushq %[cs]
+        \\pushq %[rip]
+        \\
+        \\# Jump to Kata
+        \\iretq
+        :
+        : [rax] "m" (ctx.rax),
+          [rbx] "m" (ctx.rbx),
+          [rcx] "m" (ctx.rcx),
+          [rdx] "m" (ctx.rdx),
+          [rsi] "m" (ctx.rsi),
+          [rdi] "m" (ctx.rdi),
+          [rbp] "m" (ctx.rbp),
+          [rsp] "m" (ctx.rsp),
+          [r8] "m" (ctx.r8),
+          [r9] "m" (ctx.r9),
+          [r10] "m" (ctx.r10),
+          [r11] "m" (ctx.r11),
+          [r12] "m" (ctx.r12),
+          [r13] "m" (ctx.r13),
+          [r14] "m" (ctx.r14),
+          [r15] "m" (ctx.r15),
+          [rip] "m" (ctx.rip),
+          [rflags] "m" (ctx.rflags),
+          [cs] "m" (ctx.cs),
+          [ss] "m" (ctx.ss),
+        : .{ .memory = true });
+    unreachable;
+}
+
+fn set_page_table(page_table_phys: u64) void {
+    asm volatile ("mov %[pt], %%cr3"
+        :
+        : [pt] "r" (page_table_phys),
+        : .{ .memory = true });
+}
diff --git a/mirai/mirai.zig b/mirai/mirai.zig
index efb382a..9280485 100644
--- a/mirai/mirai.zig
+++ b/mirai/mirai.zig
@@ -1,4 +1,5 @@
 const ash = @import("ash/ash.zig");
+const crimson = @import("crimson/panic.zig");
 const serial = @import("drivers/serial.zig");
 const sequence = @import("boot/sequence.zig");
 
@@ -23,7 +24,6 @@ export fn mirai(multiboot_info_addr: u64) noreturn {
 }
 
 pub fn panic(message: []const u8, _: ?*@import("std").builtin.StackTrace, _: ?usize) noreturn {
-    const crimson = @import("crimson/panic.zig");
     crimson.collapse(message, null);
 }