nx_nishi_usb_preempt.nx source

1// nx_nishi_usb_preempt.nx -- x86 ladder R-KERN-3: PREEMPTIVE multitasking (timer IRQ0 preempts tasks). 2// 3// The capstone of the kernel-internals thread: "a kernel that runs tasks". nx_kernel_sched proved a 4// COOPERATIVE scheduler (tasks yield). This proves a PREEMPTIVE one: a timer (IRQ0, IF-gated like the 5// real PIC/PIT, delivered between instructions) forces a context switch between two tasks that NEVER 6// yield -- each runs an infinite increment loop, and the timer alone makes both progress, round-robin. 7// It composes onto R-KERN-1's IDT: the timer handler is the IDT[0x20] vector; here the scheduler's 8// context switch + the IF-gated timer delivery are modeled (same level as nx_kernel_sched's emu_resume), 9// the tasks are real x86 the emu executes. 10// 11// The proof that the context switch is REAL (registers preserved across preemption): each task sets its 12// counter pointer rbx ONCE at entry, then loops reading/writing [rbx] without re-setting it. The timer 13// preempts mid-loop repeatedly; both counters keep advancing correctly ONLY if each task's rbx (and 14// rax/rcx) survive every switch -- i.e. a genuine per-task context, not shared state. 15// 16// KAT: (T1) BOTH tasks made real progress (both counters > 0) = preemptive multitasking; (T2) round-robin 17// fairness (the two counters are close, neither starved); (T3) the timer actually drove the switching 18// (>= ~the requested number of ticks occurred). NEG/liar-kill (T4): with the timer MASKED (the kernel's 19// STI is a no-op), task B NEVER runs (counter B == 0) -- proving progress is driven by real IF-gated timer 20// preemption, not by the tasks cooperating. 21// 22// HONEST SCOPE: the context-switch mechanism + the IF-gated periodic timer are modeled (as in 23// nx_kernel_sched / nx_nishios_irq); a real 8259 PIC + 8254 PIT + a full x86 context-switch handler that 24// saves/restores via the stack are the hardware refinements. No /dev, no hardware writes (Rule 26). 25// expect_exit: 0 license_tier: ORIGINAL 26import "nx_syscalls.nx" 27const CTR_MAGIC_5000000: i64 = 5000000 28const CTR_MAGIC_65536: i64 = 65536 29 30func pe_puts(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 } 31func pe_num(v: i64) -> i64 { let b: *u8=sys_mmap(28); var m: i64=v; if m<0{m=0-m;sys_write(1,"-" as *u8,1)} let t: *u8=sys_mmap(28); var k: i64=0; if m==0{t[0]=48 as u8;k=1} while m>0{t[k]=(48+(m%10)) as u8;m=m/10;k=k+1} var i: i64=0; while i<k{b[i]=t[k-1-i];i=i+1} sys_write(1,b,k); return 0 } 32func pe_st64(mem: *u8, a: i64, v: i64) -> i64 { var i: i64=0; while i<8 { mem[a+i]=((v>>(i*8))&0xff) as u8; i=i+1 } return 0 } 33func pe_ld64(mem: *u8, a: i64) -> i64 { var v: i64=0; var i: i64=0; while i<8 { v=v|((mem[a+i] as i64)<<(i*8)); i=i+1 } return v } 34func pe_b(c: *u8, o: i64, b: i64) -> i64 { c[o]=(b & 0xff) as u8; return o+1 } 35func pe_mov(c: *u8, o: i64, modrm: i64, imm: i64) -> i64 { 36 c[o]=0x48 as u8; c[o+1]=0xC7 as u8; c[o+2]=(modrm&0xff) as u8 37 c[o+3]=(imm&0xff) as u8; c[o+4]=((imm>>8)&0xff) as u8; c[o+5]=((imm>>16)&0xff) as u8; c[o+6]=((imm>>24)&0xff) as u8 38 return o+7 39} 40 41// PREEMPTIVE 2-task emu. reg2[cur*16+i] = task cur's register i; pc2[cur] = task cur's pc. Between 42// instructions the timer ticks; every `thresh` instructions, if IF is set, it PREEMPTS (switches cur). 43// sti_en models the PIC/PIT being enabled (the kernel's STI). out[0]=ticks delivered. 44func emu_preempt(code: *u8, mem: *u8, thresh: i64, maxticks: i64, sti_en: i64, pcA: i64, pcB: i64, out: *i64) -> i64 { 45 let reg2: *i64 = sys_mmap(2 * 16 * 8) as *i64 46 let pc2: *i64 = sys_mmap(2 * 8) as *i64 47 pc2[0]=pcA; pc2[1]=pcB 48 var cur: i64=0 49 var timer: i64=0 50 var ticks: i64=0 51 var iflag: i64=0 52 var guard: i64=0 53 while guard < CTR_MAGIC_5000000 { 54 guard = guard + 1 55 if ticks >= maxticks { out[0]=ticks; return 0 } 56 timer = timer + 1 57 if timer >= thresh { timer=0; if iflag==1 { if cur==0 { cur=1 } else { cur=0 } ticks=ticks+1 } } // TIMER PREEMPT 58 let base: i64 = cur*16 59 let p: i64 = pc2[cur] 60 let b: i64 = code[p] as i64 61 var h: i64 = 0 62 if b==0xFB { if sti_en==1 { iflag=1 } pc2[cur]=p+1; h=1 } // sti 63 if h==0 { if b==0xFA { iflag=0; pc2[cur]=p+1; h=1 } } // cli 64 if h==0 { if b==0xEB { var r: i64=code[p+1] as i64; if r>127 { r=r-256 } pc2[cur]=p+2+r; h=1 } } // jmp rel8 65 if h==0 { if b==0x48 { 66 let o2: i64 = code[p+1] as i64 67 if o2==0xC7 { let m: i64=code[p+2] as i64; let imm: i64=(code[p+3] as i64)|((code[p+4] as i64)<<8)|((code[p+5] as i64)<<16)|((code[p+6] as i64)<<24); reg2[base+(m&7)]=imm; pc2[cur]=p+7; h=1 } 68 if h==0 { if o2==0x8B { let m: i64=code[p+2] as i64; if ((m>>6)&3)==3 { reg2[base+((m>>3)&7)]=reg2[base+(m&7)] } else { reg2[base+((m>>3)&7)]=pe_ld64(mem, reg2[base+(m&7)]) } pc2[cur]=p+3; h=1 } } 69 if h==0 { if o2==0x89 { let m: i64=code[p+2] as i64; if ((m>>6)&3)==3 { reg2[base+(m&7)]=reg2[base+((m>>3)&7)] } else { pe_st64(mem, reg2[base+(m&7)], reg2[base+((m>>3)&7)]) } pc2[cur]=p+3; h=1 } } 70 if h==0 { if o2==0x01 { let m: i64=code[p+2] as i64; reg2[base+(m&7)]=reg2[base+(m&7)]+reg2[base+((m>>3)&7)]; pc2[cur]=p+3; h=1 } } 71 if h==0 { out[0]=ticks; return 0 - 1 } 72 } } 73 if h==0 { out[0]=ticks; return 0 - 3 } 74 } 75 out[0]=ticks 76 return 0 77} 78 79const CTR_A: i64 = 0xA000 80const CTR_B: i64 = 0xB000 81 82func main() -> i64 { 83 pe_puts("x86 ladder R-KERN-3: PREEMPTIVE multitasking -- a timer IRQ preempts two non-yielding tasks\n" as *u8) 84 85 // author two tasks; each sets its counter pointer ONCE, enables nothing else, then loops forever 86 // incrementing [rbx]. (taskA also issues STI to enable the timer; taskB inherits IF.) 87 let code: *u8 = sys_mmap(256) 88 var o: i64 = 0 89 let taskA: i64 = o 90 o = pe_mov(code, o, 0xC3, CTR_A) // mov rbx, CTR_A 91 o = pe_mov(code, o, 0xC1, 1) // mov rcx, 1 92 o = pe_b(code, o, 0xFB) // sti (enable the timer) 93 let loopA: i64 = o 94 code[o]=0x48 as u8; code[o+1]=0x8B as u8; code[o+2]=0x03 as u8; o=o+3 // mov rax, [rbx] 95 code[o]=0x48 as u8; code[o+1]=0x01 as u8; code[o+2]=0xC8 as u8; o=o+3 // add rax, rcx 96 code[o]=0x48 as u8; code[o+1]=0x89 as u8; code[o+2]=0x03 as u8; o=o+3 // mov [rbx], rax 97 code[o]=0xEB as u8; code[o+1]=((loopA-(o+2)) & 0xff) as u8; o=o+2 // jmp loopA 98 let taskB: i64 = o 99 o = pe_mov(code, o, 0xC3, CTR_B) // mov rbx, CTR_B 100 o = pe_mov(code, o, 0xC1, 1) // mov rcx, 1 101 let loopB: i64 = o 102 code[o]=0x48 as u8; code[o+1]=0x8B as u8; code[o+2]=0x03 as u8; o=o+3 // mov rax, [rbx] 103 code[o]=0x48 as u8; code[o+1]=0x01 as u8; code[o+2]=0xC8 as u8; o=o+3 // add rax, rcx 104 code[o]=0x48 as u8; code[o+1]=0x89 as u8; code[o+2]=0x03 as u8; o=o+3 // mov [rbx], rax 105 code[o]=0xEB as u8; code[o+1]=((loopB-(o+2)) & 0xff) as u8; o=o+2 // jmp loopB 106 107 let THRESH: i64 = 6 108 let MAXTICKS: i64 = 60 109 110 // RUN 1: timer enabled -> preemptive round-robin 111 let mem: *u8 = sys_mmap(CTR_MAGIC_65536) 112 var z: i64=0 113 while z<CTR_MAGIC_65536 { mem[z]=0 as u8; z=z+1 } 114 let out: *i64 = sys_mmap(16) as *i64 115 emu_preempt(code, mem, THRESH, MAXTICKS, 1, taskA, taskB, out) 116 let cA: i64 = pe_ld64(mem, CTR_A) 117 let cB: i64 = pe_ld64(mem, CTR_B) 118 let ticks: i64 = out[0] 119 120 // RUN 2 (NEG CONTROL): timer masked (STI is a no-op) -> task B starves 121 let mem2: *u8 = sys_mmap(CTR_MAGIC_65536) 122 var z2: i64=0 123 while z2<CTR_MAGIC_65536 { mem2[z2]=0 as u8; z2=z2+1 } 124 let out2: *i64 = sys_mmap(16) as *i64 125 emu_preempt(code, mem2, THRESH, MAXTICKS, 0, taskA, taskB, out2) 126 let cA2: i64 = pe_ld64(mem2, CTR_A) 127 let cB2: i64 = pe_ld64(mem2, CTR_B) 128 129 pe_puts(" timer ENABLED: task A ran "); pe_num(cA); pe_puts(" times, task B ran "); pe_num(cB); pe_puts(" times ("); pe_num(ticks); pe_puts(" preemptions)\n" as *u8) 130 pe_puts(" timer MASKED: task A ran "); pe_num(cA2); pe_puts(" times, task B ran "); pe_num(cB2); pe_puts(" times (B starved => no preemption)\n" as *u8) 131 132 // fairness: closeness = smaller/larger * 100 (>=50 means within 2x) 133 var lo: i64 = cA; var hi: i64 = cB 134 if cA > cB { lo=cB; hi=cA } 135 var fair: i64 = 0 136 if hi > 0 { fair = (lo*100)/hi } 137 138 var pass: i64=0 139 var ttl: i64=0 140 ttl=ttl+1; pe_puts(" T1 BOTH tasks made real progress (preemptive multitasking, A>5 & B>5): " as *u8); if cA>5 { if cB>5 { pass=pass+1; pe_puts("PASS\n" as *u8) } else { pe_puts("FAIL\n" as *u8) } } else { pe_puts("FAIL\n" as *u8) } 141 ttl=ttl+1; pe_puts(" T2 round-robin fairness (counters within 2x, closeness="); pe_num(fair); pe_puts("%): " as *u8); if fair>=50 { pass=pass+1; pe_puts("PASS\n" as *u8) } else { pe_puts("FAIL\n" as *u8) } 142 ttl=ttl+1; pe_puts(" T3 the timer drove the switching (ticks=="); pe_num(ticks); pe_puts(", want 60): " as *u8); if ticks==60 { pass=pass+1; pe_puts("PASS\n" as *u8) } else { pe_puts("FAIL\n" as *u8) } 143 ttl=ttl+1; pe_puts(" T4 NEG: masked timer -> task B starves (B==0) while A runs (A>0) (liar-kill): " as *u8); if cB2==0 { if cA2>0 { pass=pass+1; pe_puts("PASS\n" as *u8) } else { pe_puts("FAIL\n" as *u8) } } else { pe_puts("FAIL\n" as *u8) } 144 145 pe_puts("X86-USB-PREEMPT-GATE passed "); pe_num(pass); pe_puts("/"); pe_num(ttl) 146 if pass==ttl { pe_puts(" verdict=GREEN (a timer IRQ preempts two non-yielding tasks round-robin -- preemptive multitasking, the kernel runs tasks)\n" as *u8); sys_exit(0); return 0 } 147 pe_puts(" verdict=RED\n" as *u8); sys_exit(1); return 1 148}