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). --- src/runtime/rt.zc | 40 +++++++++++++++++++--------------------- 1 file changed, 19 insertions(+), 21 deletions(-) (limited to 'src/runtime') diff --git a/src/runtime/rt.zc b/src/runtime/rt.zc index 44f3570..d6dcfb6 100644 --- a/src/runtime/rt.zc +++ b/src/runtime/rt.zc @@ -95,9 +95,8 @@ enhance outside(i, n) micro "i = ltu i n; i = xor i 1"; // block (its check word p[-3] is p ^ MAGIC) and the byte or word offset i * m is not // inside the block's payload (q units per word: 1 for word elements, 8 for packed // ones), else 0. a load outside memory reads 0, so any p is safe to ask about. the -// payload is paylen (p[-5] - HDR words, at most the size an o3 raw block was asked for, -// which is the complement of its type word p[-1] when that is negative). see bchk. -enhance bnd(p, i, m, q) micro "r6 = sub p 3; r6 = ld r6; r7 = xor p 0x2B7E1516; r6 = eq r6 r7; r7 = sub p 5; r7 = ld r7; r7 = sub r7 5; r8 = sub p 1; r8 = ld r8; r8 = not r8; r7 = minu r7 r8; r7 = mul r7 q; r8 = mul i m; r8 = ltu r8 r7; r8 = xor r8 1; r0 = and r6 r8"; +// payload is paylen: the n words new asked for, kept in bits 32..62 of p[-4]. see bchk. +enhance bnd(p, i, m, q) micro "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"; // ---- bit operations and float conversions ---- // these use single machine instructions where the cpu has them. @@ -403,7 +402,8 @@ int zshl(int a, int b) { return a * pow2[b & 63]; } // free too, so freed space can be reused at any size. every block has a 5 // word header before the pointer the program sees: // p[-5] block size -// p[-4] flags in the low 16 bits, size class in the next 5 +// p[-4] flags in the low 16 bits, size class in the next 5, and in bits 32..62 the +// words new asked for (n, below 2^31; 0 on a free block). paylen, bchk and bnd read it // 0 free (check word cleared) or quarantined (check word still p ^ MAGIC) // 1 live 2 releasing 3 marked 4 quarantined but a word still points at it // bit 8 (value 8) is orthogonal: the object is shared. free is a no-op, @@ -739,8 +739,8 @@ int oom() { // new_oz, which zeroes the words that were asked for. int .u new_raw(int n) { int need = n + HDR, k = 3; word b; int p; - if (n > 0x7FFFFFFF - HDR) { oom(); return 0; } - if (n < 0) need = HDR; + if (n > 0x7FFFFFFF - HDR) { oom(); return 0; } // n must fit bits 32..62 of p[-4]: trap, never truncate + if (n < 0) { need = HDR; n = 0; } while (pow2[k] < need) k++; b = balloc(k); if (!b) { @@ -755,7 +755,7 @@ int .u new_raw(int n) { if (!b) oom(); } p = b + HDR; - b[1] = (k * pow2[16]) | 1; b[2] = p ^ MAGIC; b[3] = 0; b[4] = 0 - n - 1; + b[1] = (k * pow2[16]) | 1 | (n * pow2[32]); b[2] = p ^ MAGIC; b[3] = 0; b[4] = 0 - n - 1; // the words past n are not the object's. zero them so a later walk // doesn't follow garbage. the n words themselves stay uninitialized. if (n > 0 && b[0] - HDR > n) fill_w(p + n, 0, b[0] - HDR - n); @@ -797,15 +797,16 @@ word .u new_k(int n, int t, int k) { freel[k] = nx; if (nx) nx[6] = 0; p = b + HDR; - b[1] = (k * pow2[16]) | 1; b[2] = p ^ MAGIC; b[3] = 0; b[4] = t; + if (n < 0) n = 0; + b[1] = (k * pow2[16]) | 1 | (n * pow2[32]); b[2] = p ^ MAGIC; b[3] = 0; b[4] = t; if (k == 3) { p[0] = 0; p[1] = 0; p[2] = 0; } // the smallest block: three payload words else fill_w(p, 0, pow2[k] - HDR); return p; } -// the size in words of the heap object p, as new asked for it. +// the size in words of the heap object p, as new asked for it (not the block's payload). int osize(word p) { if (!isobj(p)) return 0; - return p[-5] - HDR; + return paylen(p); } // the type record stamped on the heap object p by new(T), or 0 when there is none. int typeof_obj(word p) { @@ -813,13 +814,9 @@ int typeof_obj(word p) { return p[-1]; } -// how many payload words a free walk should follow. a raw object only owns -// the words new asked for; the slack past that was never zeroed. -int paylen(word p) { - int n = p[-5] - HDR, req; - if (p[-1] < 0) { req = 0 - p[-1] - 1; if (req < n) n = req; } - return n; -} +// the words new asked for, from bits 32..62 of p[-4]. a free walk follows these, +// and bchk and bnd check against them; the slack past n is not the object's. +int paylen(word p) { return p[-4] >> 32; } // frees p and, recursively, every object p owns. the block stays quarantined. int release(word p) { word b = p - HDR; int n = paylen(p), i = 0; word w; @@ -830,7 +827,7 @@ int release(word p) { w = p[i]; if (isobj(w) && !(w[-4] & F_SHARE) && w[-2] == p) release(w); i++; } - b[1] = b[1] & ~7; // quarantined. the check word and the bytes stay; the next sweep reclaims it + b[1] = b[1] & 2097144; // quarantined (flags but the state, and the class; n is cleared, so len is 0 and indexing traps). the check word and the bytes stay; the next sweep reclaims it return 0; } // releases a heap object and consumes an owned object automatically. an explicit @@ -1120,11 +1117,12 @@ word dat(word h, int i) { // a heap block does have one: the words the block holds (paylen). for any // other pointer (the middle of a block, a frame, a global, memory managed by hand) // nothing is known and this returns at once. sz is the element size in words, or -// minus the element size in bytes for packed elements. the length is the block's -// payload, which a buddy block rounds up to a power of two; an o3 raw block is exact. +// minus the element size in bytes for packed elements. the length is exactly the +// words new asked for (paylen), not the power-of-two block. int bchk(word p, int i, int sz) { int n; if (p < HEAP_LO + HDR || p >= hbump || p[-3] != (p ^ MAGIC)) return 0; + if ((dbg & 1) && !(p[-4] & 1)) checkptr(p); // a freed block has n = 0: memdebug names it a use after free n = paylen(p); if (sz > 0) { if (i >= 0 && i < n && i * sz < n) return 0; @@ -1436,7 +1434,7 @@ int memreport() { if (site_p[i]) { p = site_p[i] ^ MAGIC; if (isobj(p)) { - put_s("leak: line "); put_n(site_line[i]); put_s(" "); put_n(osize(p)); put_s(" words\n"); + put_s("leak: line "); put_n(site_line[i]); put_s(" "); put_n(paylen(p)); put_s(" words\n"); // n, the words new asked for n++; } } -- cgit v1.2.3