From 433fb8cb71e98bbfd579fb43dbc0eac0a60bae73 Mon Sep 17 00:00:00 2001 From: zinc Date: Wed, 14 Oct 2026 18:35:03 +0330 Subject: rt: exact-size heap bounds; n, the words new asked for, lives in bits 32..62 of p[-4] the bnd recipe and paylen read n instead of the power-of-two block: bnd: r6 = sub p 3; r6 = ld r6; r7 = xor p 0x2B7E1516; r6 = eq r6 r7; r7 = sub p 4; r7 = ld r7; r7 = shr r7 32; r7 = mul r7 q; r8 = mul i m; r8 = ltu r8 r7; r8 = xor r8 1; r0 = and r6 r8 paylen: return p[-4] >> 32 two loads instead of three; osize, bchk, release, recycle and the memdebug leak report all read n (rt.new(4) has length 4, rt.new(0) has 0). writers: new_raw and new_k set n; stack.h line 87 and tinyvm.ts (BigInt) set it on stack segments. release clears n when a block goes into quarantine (len 0, indexing traps; under memdebug bchk reports a use after free); every free-list path (fpush, mkblock, bdrop, recycle_leaf, balloc hold) rewrites the word as k << 16, and an array that grows gets a fresh block. a request over 2^31-1-HDR words stops in new_raw (oom), and the compiler only takes the new_k fast path for constant sizes that fit, so n is never truncated. bit users checked (all mask or preserve bits 32..62; none compares or copies the whole word): gc mark and sweep; release, free, recycle, recycle_leaf; share and own; isobj, quar, checkptr, obj_base; bclass and the bfree buddy merge; balloc, mkblock, fpush, funlink, heap_grow; frame_grow; stack_allocate in src/core/stack.h and src/js/tinyvm.ts; micro.c and core.c (check word only); the compiler's two p[-4] | F_INTERNAL writes (base.zc, builtins.zc). 32-bit ports: none (baremetal, wasm and micro use int64 Cell). tests: tests/programs/exactsize.zc (n-1/n for non-power-of-two sizes, new(0), packed bytes, recycle, grow, stack growth); 8-runtime: exact_size_bounds, pointer_index_n_minus_1, pointer_index_n_traps, pointer_index_n_traps_memdebug, new_zero_index_traps, new_too_big_traps, stale_index_after_free_traps, stale_index_after_free_memdebug. expectations changed: leak report shows n (tests/test.sh line 169, examples/learn/13-memdebug.out, docs/LEARN.md, 4-statements/memdebug_report_line.zc). programs adjusted to keep test.sh expectations: quarantine.zc (unbounded), bounds_heap.zc (rt.new(11)). spec 3.7.4 and 4.11 updated. fixpoint 402204 words (main 402197). --- tests/conformance/4-statements/memdebug_report.zc | 2 +- .../4-statements/memdebug_report_line.zc | 2 +- tests/conformance/8-runtime/exact_size_bounds.zc | 45 ++++++++++++++++++++++ tests/conformance/8-runtime/new_too_big_traps.zc | 6 +++ .../conformance/8-runtime/new_zero_index_traps.zc | 6 +++ .../8-runtime/pointer_index_n_minus_1.zc | 7 ++++ .../conformance/8-runtime/pointer_index_n_traps.zc | 7 ++++ .../8-runtime/pointer_index_n_traps_memdebug.zc | 8 ++++ .../8-runtime/stale_index_after_free_memdebug.zc | 17 ++++++++ .../8-runtime/stale_index_after_free_traps.zc | 15 ++++++++ 10 files changed, 113 insertions(+), 2 deletions(-) create mode 100644 tests/conformance/8-runtime/exact_size_bounds.zc create mode 100644 tests/conformance/8-runtime/new_too_big_traps.zc create mode 100644 tests/conformance/8-runtime/new_zero_index_traps.zc create mode 100644 tests/conformance/8-runtime/pointer_index_n_minus_1.zc create mode 100644 tests/conformance/8-runtime/pointer_index_n_traps.zc create mode 100644 tests/conformance/8-runtime/pointer_index_n_traps_memdebug.zc create mode 100644 tests/conformance/8-runtime/stale_index_after_free_memdebug.zc create mode 100644 tests/conformance/8-runtime/stale_index_after_free_traps.zc (limited to 'tests/conformance') diff --git a/tests/conformance/4-statements/memdebug_report.zc b/tests/conformance/4-statements/memdebug_report.zc index 406662e..782a85e 100644 --- a/tests/conformance/4-statements/memdebug_report.zc +++ b/tests/conformance/4-statements/memdebug_report.zc @@ -1,5 +1,5 @@ // expect: leak: line 8 3 words/107/ -// spec 4.11: rt.memreport() returns the count of live recorded objects +// spec 4.11: rt.memreport() returns the count of live recorded objects; W is the 3 words new asked for include rt; void pn(int x) { rt.put_n(x); rt.put_c(10); } memdebug on; diff --git a/tests/conformance/4-statements/memdebug_report_line.zc b/tests/conformance/4-statements/memdebug_report_line.zc index 52eecba..8a1b6cf 100644 --- a/tests/conformance/4-statements/memdebug_report_line.zc +++ b/tests/conformance/4-statements/memdebug_report_line.zc @@ -1,4 +1,4 @@ -// expect: leak: line 9 3 words/ +// expect: leak: line 9 2 words/ // spec 4.11: leak: line N W words per live recorded object (N is the allocation line) include rt; void pn(int x) { rt.put_n(x); rt.put_c(10); } diff --git a/tests/conformance/8-runtime/exact_size_bounds.zc b/tests/conformance/8-runtime/exact_size_bounds.zc new file mode 100644 index 0000000..7a8c440 --- /dev/null +++ b/tests/conformance/8-runtime/exact_size_bounds.zc @@ -0,0 +1,45 @@ +// expect: 11 11 11 11 11 11 11 11/10 1/1101/1601/200000 11 11/ +// spec 8.4: exact heap lengths at n-1 and n, new(0), packed bytes, a recycled block, a grown array, after the stacks grow (copy of tests/programs/exactsize.zc) +include rt; +// exact-size bounds: a heap block knows the n words new asked for (bits 32..62 of +// p[-4]), not just its power-of-two block. rt.bnd(p, i, 1, 1) is 1 when p[i] is +// outside: the same recipe every backend inlines in front of p[i]. +struct P { int a; int b; int c; } +struct Q { int a; } +// n-1 inside, n outside, osize is n, and p[n-1] is usable +int edge(int n) { + word* p = rt.new(n); + p[n - 1] = n; + return rt.bnd(p, n - 1, 1, 1) * 100 + rt.bnd(p, n, 1, 1) * 10 + (rt.osize(p) == n) + (p[n - 1] == n) - 1; +} +int zero() { word* p = rt.new(0); return rt.bnd(p, 0, 1, 1) * 10 + rt.osize(p); } +int bytes() { word* p = rt.new(3); return rt.bnd(p, 23, 1, 8) * 10 + rt.bnd(p, 24, 1, 8); } // 3 words are 24 bytes +int where; +int leaf() { P* a = rt.new(P); a.c = 3; where = (&a.a) as int; return a.c; } // a is recycled at the function's end +// recycle: the next 1-word object reuses the 3-word block, with n = 1 +int reuse() { + Q* q = rt.new(Q); int same = where == ((&q.a) as int); + return same * 1000 + rt.osize(q) * 100 + rt.bnd(q, 0, 1, 1) * 10 + rt.bnd(q, 1, 1, 1); +} +// grow: the items block is replaced by one with its own exact n (16 words for 9 ints) +int grow() { + int[?] d = rt.new(int[?], 0); int i = 0; word* h; word* p; + while (i < 9) { d.push(i); i++; } + h = &d[0]; p = h; + return rt.osize(p) * 100 + rt.bnd(p, 15, 1, 1) * 10 + rt.bnd(p, 16, 1, 1); +} +// deep enough to grow the stacks: their segments are heap blocks the core allocates +// (src/core/stack.h, src/js/tinyvm.ts) with n set too. after they go back, blocks reused +// from them carry their own n. +int deep(int k) { if (k == 0) return 0; return deep(k - 1) + 1; } +fn main() { + rt.put_n(edge(1)); rt.put_c(32); rt.put_n(edge(3)); rt.put_c(32); rt.put_n(edge(5)); rt.put_c(32); + rt.put_n(edge(6)); rt.put_c(32); rt.put_n(edge(7)); rt.put_c(32); rt.put_n(edge(11)); rt.put_c(32); + rt.put_n(edge(13)); rt.put_c(32); rt.put_n(edge(100)); rt.put_c(10); + rt.put_n(zero()); rt.put_c(32); rt.put_n(bytes()); rt.put_c(10); + leaf(); rt.put_n(reuse()); rt.put_c(10); + rt.put_n(grow()); rt.put_c(10); + rt.put_n(deep(200000)); rt.put_c(32); rt.put_n(edge(9)); rt.put_c(32); rt.put_n(edge(21)); rt.put_c(10); + return 0; +} +// zc0: skip diff --git a/tests/conformance/8-runtime/new_too_big_traps.zc b/tests/conformance/8-runtime/new_too_big_traps.zc new file mode 100644 index 0000000..b1692f2 --- /dev/null +++ b/tests/conformance/8-runtime/new_too_big_traps.zc @@ -0,0 +1,6 @@ +// expect error: zc: out of heap memory +// spec 8.4: a request over 2^31 - 1 words (less the header) stops at the allocation; the length is never truncated +include rt; +void pn(int x) { rt.put_n(x); rt.put_c(10); } +fn main() { word* p = rt.new(0x80000000); pn(p[0]); return 0; } +// zc0: skip diff --git a/tests/conformance/8-runtime/new_zero_index_traps.zc b/tests/conformance/8-runtime/new_zero_index_traps.zc new file mode 100644 index 0000000..ee77d88 --- /dev/null +++ b/tests/conformance/8-runtime/new_zero_index_traps.zc @@ -0,0 +1,6 @@ +// expect error: zy: index 0 out of range (length 0) +// spec 8.4: rt.new(0) has no words, so p[0] is outside +include rt; +void pn(int x) { rt.put_n(x); rt.put_c(10); } +fn main() { word* p = rt.new(0); int i = 0; pn(p[i]); return 0; } +// zc0: skip diff --git a/tests/conformance/8-runtime/pointer_index_n_minus_1.zc b/tests/conformance/8-runtime/pointer_index_n_minus_1.zc new file mode 100644 index 0000000..2b34e83 --- /dev/null +++ b/tests/conformance/8-runtime/pointer_index_n_minus_1.zc @@ -0,0 +1,7 @@ +// expect: 7/ +// spec 8.4: a heap pointer's length is the n words new asked for; p[n-1] is inside (5 words in a 16-word block) +include rt; +void pn(int x) { rt.put_n(x); rt.put_c(10); } +int at(word* p, int i) { p[i] = 7; return p[i]; } +fn main() { word* p = rt.new(5); pn(at(p, 4)); return 0; } +// zc0: skip diff --git a/tests/conformance/8-runtime/pointer_index_n_traps.zc b/tests/conformance/8-runtime/pointer_index_n_traps.zc new file mode 100644 index 0000000..ccb7e3a --- /dev/null +++ b/tests/conformance/8-runtime/pointer_index_n_traps.zc @@ -0,0 +1,7 @@ +// expect error: zy: index 5 out of range (length 5) +// spec 8.4: p[n] is outside even though the block has slack (5 words in a 16-word block, whose payload is 11) +include rt; +void pn(int x) { rt.put_n(x); rt.put_c(10); } +int at(word* p, int i) { p[i] = 7; return p[i]; } +fn main() { word* p = rt.new(5); pn(at(p, 5)); return 0; } +// zc0: skip diff --git a/tests/conformance/8-runtime/pointer_index_n_traps_memdebug.zc b/tests/conformance/8-runtime/pointer_index_n_traps_memdebug.zc new file mode 100644 index 0000000..49d914a --- /dev/null +++ b/tests/conformance/8-runtime/pointer_index_n_traps_memdebug.zc @@ -0,0 +1,8 @@ +// expect error: zy: index 11 out of range (length 11) +// spec 8.4 and 4.11: the exact length holds under memdebug too (11 words, a 16-word block) +memdebug on; +include rt; +void pn(int x) { rt.put_n(x); rt.put_c(10); } +int at(word* p, int i) { p[i] = 7; return p[i]; } +fn main() { word* p = rt.new(11); pn(at(p, 10)); pn(at(p, 11)); return 0; } +// zc0: skip diff --git a/tests/conformance/8-runtime/stale_index_after_free_memdebug.zc b/tests/conformance/8-runtime/stale_index_after_free_memdebug.zc new file mode 100644 index 0000000..69dc5e3 --- /dev/null +++ b/tests/conformance/8-runtime/stale_index_after_free_memdebug.zc @@ -0,0 +1,17 @@ +// expect error: zy: use after free from line 9 +// spec 3.7.4 and 4.11: under memdebug the same stale index is a use after free +memdebug +on; +include rt; +void pn(int x) { rt.put_n(x); rt.put_c(10); } +int g; +// unchecked: the analyzer stays out, so the block is freed (quarantined, with its check word) rather than recycled +unchecked int make() { let p = rt.new(5); p[4] = 1; g = p; return 0; } +unchecked int drop() { let p = g; rt.free(p); return 0; } +fn main() { + word* q; int i = 4; + make(); q = g as word*; pn(q[i]); + drop(); q = g as word*; pn(q[i]); + return 0; +} +// zc0: skip diff --git a/tests/conformance/8-runtime/stale_index_after_free_traps.zc b/tests/conformance/8-runtime/stale_index_after_free_traps.zc new file mode 100644 index 0000000..bd2a185 --- /dev/null +++ b/tests/conformance/8-runtime/stale_index_after_free_traps.zc @@ -0,0 +1,15 @@ +// expect error: zy: index 4 out of range (length 0) +// spec 3.7.4: a freed block has length 0, so an index through a stale copy of its pointer traps +include rt; +void pn(int x) { rt.put_n(x); rt.put_c(10); } +int g; +// unchecked: the analyzer stays out, so the block is freed (quarantined, with its check word) rather than recycled +unchecked int make() { let p = rt.new(5); p[4] = 1; g = p; return 0; } +unchecked int drop() { let p = g; rt.free(p); return 0; } +fn main() { + word* q; int i = 4; + make(); q = g as word*; pn(q[i]); + drop(); q = g as word*; pn(q[i]); + return 0; +} +// zc0: skip -- cgit v1.2.3