`nx_alloc.nx` source

↩ module page · 100 lines · 5669 B
1// nx_alloc.nx -- SOVEREIGN MEMORY ALLOCATOR (OS gap: MEMORY-MGMT). A heap (malloc/free) over one mmap'd arena:
2// inline block headers [size(incl hdr) | free], first-fit allocate with split, free + coalesce adjacent free blocks.
3// No libc malloc -- our own, deterministic + auditable. NEVER-BRICK: operates on userspace RAM, writes 0 firmware.
4// Grounded: os_mem.raw (Memory_management).
5//   T1 alloc 3 blocks, write distinct patterns, read back == no overlap.
6//   T2 free the middle, re-malloc reuses that region (first-fit).
7//   T3 free all + coalesce -> a single free block == whole arena (no fragmentation creep).
8//   T4 teeth: an over-arena malloc fails (returns -1).
9// expect_exit: 0   Sovereign: nx_syscalls.
10import "nx_syscalls.nx"
11import "nx_itoa_lib.nx"   // shared MSB-first emitter (zero-alloc)
12import "nx_g_puts_lib.nx"
13const K_MAGIC_65536: i64 = 65536
14const K_MAGIC_100000: i64 = 100000
15
16// MIGRATED to the shared emitter (debt 1785563586). The old body mmapped a scratch buffer
17// per call and never freed it. At PAGE granularity that is 4096B leaked PER CALL -- the
18// defect that took 28.5GB of a 36GB host in nx_ts_lumadiff (2MB input, ~3.66M calls).
19// nxi_* is MSB-first, allocates NOTHING, and emits identical bytes including the sign.
20func g_pn(v: i64) -> i64 { nxi_out(v); return 0 }
21func ck(name: *u8, c: i64) -> i64 { if c==1 { g_puts("  PASS " as *u8) } else { g_puts("  FAIL " as *u8) } g_puts(name); g_puts("\n" as *u8); return c }
22
23const HDR: i64 = 16   // 8 bytes size + 8 bytes free-flag
24func ar_rd(a: *u8, o: i64) -> i64 { var v: i64=0; var i: i64=0; while i<8 { v=v|((a[o+i] as i64)<<(i*8)); i=i+1 } return v }
25func ar_wr(a: *u8, o: i64, v: i64) -> i64 { var i: i64=0; while i<8 { a[o+i]=((v>>(i*8))&255) as u8; i=i+1 } return 0 }
26
27func na_init(a: *u8, total: i64) -> i64 { ar_wr(a,0,total); ar_wr(a,8,1); return 0 }   // one big free block
28// first-fit allocate `req` data bytes; split if leftover >= HDR+8; returns DATA byte-offset, or -1 on no fit.
29func na_malloc(a: *u8, total: i64, req: i64) -> i64 {
30    var o: i64=0
31    while o<total {
32        let sz: i64=ar_rd(a,o); let fr: i64=ar_rd(a,o+8)
33        if sz<=0 { return 0-1 }
34        if fr==1 { if sz-HDR>=req {
35            if sz-HDR-req >= HDR+8 { let no: i64=o+req+HDR; ar_wr(a,no,sz-(req+HDR)); ar_wr(a,no+8,1); ar_wr(a,o,req+HDR); ar_wr(a,o+8,0) }
36            else { ar_wr(a,o+8,0) }
37            return o+HDR
38        } }
39        o=o+sz
40    }
41    return 0-1
42}
43func na_free(a: *u8, dataoff: i64) -> i64 { ar_wr(a, dataoff-HDR+8, 1); return 0 }   // mark block free
44// merge every run of adjacent free blocks into one.
45func na_coalesce(a: *u8, total: i64) -> i64 {
46    var o: i64=0
47    while o<total {
48        let sz: i64=ar_rd(a,o); if sz<=0 { o=total }
49        else { let fr: i64=ar_rd(a,o+8)
50            if fr==1 { let no: i64=o+sz
51                if no<total { let nfr: i64=ar_rd(a,no+8); if nfr==1 { ar_wr(a,o,sz+ar_rd(a,no)) } else { o=no } } else { o=no } }
52            else { o=o+sz } }
53    }
54    return 0
55}
56
57func main() -> i64 {
58    g_puts("nx_alloc (SOVEREIGN memory allocator: malloc/free/coalesce over an arena; no libc)\n" as *u8)
59    var pass: i64=0; var total: i64=0
60    let A: i64=K_MAGIC_65536
61    let a: *u8 = sys_mmap(A)
62    na_init(a, A)
63
64    // T1: alloc 3 blocks, write distinct first-byte patterns, read back (no overlap)
65    let m1: i64=na_malloc(a,A,100); let m2: i64=na_malloc(a,A,200); let m3: i64=na_malloc(a,A,300)
66    a[m1]=0xA1 as u8; a[m2]=0xB2 as u8; a[m3]=0xC3 as u8
67    var t1: i64=0
68    if m1>=0 { if m2>=0 { if m3>=0 { if a[m1]==(0xA1 as u8) { if a[m2]==(0xB2 as u8) { if a[m3]==(0xC3 as u8) { if m1!=m2 { if m2!=m3 { t1=1 } } } } } } } }
69    g_puts("  T1 m1="); g_pn(m1); g_puts(" m2="); g_pn(m2); g_puts(" m3="); g_pn(m3); g_puts("\n" as *u8)
70    pass=pass+ck("T1: 3 mallocs, distinct non-overlapping regions, write/read intact" as *u8, t1); total=total+1
71
72    // T2: free the middle, re-malloc 150 -> first-fit reuses m2's region
73    na_free(a, m2)
74    let m4: i64=na_malloc(a,A,150)
75    var t2: i64=0; if m4==m2 { t2=1 }
76    g_puts("  T2 freed m2="); g_pn(m2); g_puts(", re-malloc(150)="); g_pn(m4); g_puts(" (first-fit reuse)\n" as *u8)
77    pass=pass+ck("T2: free + re-malloc reuses the freed region (first-fit)" as *u8, t2); total=total+1
78
79    // T3: free everything + coalesce -> one block == whole arena
80    na_free(a,m1); na_free(a,m3); na_free(a,m4)
81    na_coalesce(a, A)
82    let first: i64=ar_rd(a,0)
83    var t3: i64=0; if first==A { t3=1 }
84    g_puts("  T3 after free-all + coalesce, first block size="); g_pn(first); g_puts(" (expect "); g_pn(A); g_puts(")\n" as *u8)
85    pass=pass+ck("T3: free-all + coalesce reconstitutes one arena-sized free block (no fragmentation creep)" as *u8, t3); total=total+1
86
87    // T4 teeth: over-arena malloc fails
88    let big: i64=na_malloc(a,A,K_MAGIC_100000)
89    var t4: i64=0; if big==(0-1) { t4=1 }
90    pass=pass+ck("T4 (teeth): an over-arena malloc returns -1 (fails safely)" as *u8, t4); total=total+1
91
92    var okall: i64=0; if pass==total { okall=1 }
93    g_puts("---- nx_alloc: passed "); g_pn(pass); g_puts(" / "); g_pn(total); g_puts(" ----\n" as *u8)
94    if okall==1 {
95        let logf: i64=sys_openat_append("knowledge/status/alloc.log" as *u8, 420)
96        if logf>=0 { let z: i64=sys_write(logf,"NXALLOC GREEN: sovereign malloc/free/coalesce over arena; first-fit reuse + coalesce reconstitutes arena\n" as *u8,99); sys_close(logf) }
97        g_puts("verdict=GREEN (sovereign memory allocator: malloc/free/first-fit-reuse/coalesce; deterministic, no libc; the MEMORY-MGMT gap)\n" as *u8); sys_exit(0); return 0
98    }
99    g_puts("verdict=RED\n" as *u8); sys_exit(1); return 1
100}
nx_alloc.nx source

`nx_alloc.nx` source
