diff options
21 files changed, 191 insertions, 37 deletions
diff --git a/docs/LEARN.md b/docs/LEARN.md index d514d85..e9cdbcf 100644 --- a/docs/LEARN.md +++ b/docs/LEARN.md @@ -477,7 +477,7 @@ fn main() { output: ```text -leak: line 6 3 words +leak: line 6 1 words 1 ``` diff --git a/docs/SPEC.md b/docs/SPEC.md index dd04cde..f422166 100644 --- a/docs/SPEC.md +++ b/docs/SPEC.md @@ -427,7 +427,7 @@ pn((int)(p + 1) - (int)p); // 1: p + 1 moves one word 3.7.3 `&x` is the address of a variable, field or element. it applies to a local (which then lives in memory and cannot be an o3 variable), a global, a field and an element of a non-packed array. an element of a packed array has no address (2.3.3). -3.7.4 indexing a new object (`rt.new(int)[0]`) is error: index a new object only after binding it to a name. indexing is bounds checked at run time unless the function, block, statement or unit is unbounded or the code is o3 (4.15). a `T[?]` is checked against its length (3.13), a `T[n]` against `n`, and a pointer only when it points at the first word of a live heap block, against that block's payload (a buddy block rounds the payload up: `rt.new(4)` has 11 words). a pointer into the middle of a block, a frame array, a global or memory managed by hand is not checked. a constant index 0, and an index a loop test `i < k` with constant `k` (or `i < len(a)`) has already proved, are not checked again. a failed check prints `zy: index I out of range (length N)` and stops, as in 3.13.4. +3.7.4 indexing a new object (`rt.new(int)[0]`) is error: index a new object only after binding it to a name. indexing is bounds checked at run time unless the function, block, statement or unit is unbounded or the code is o3 (4.15). a `T[?]` is checked against its length (3.13), a `T[n]` against `n`, and a pointer only when it points at the first word of a live heap block, against exactly the words new asked for (`rt.new(4)` has 4 words, though its block holds more; `rt.new(0)` has none). a freed block has none either: an index through a stale pointer to it is out of range (length 0), and under memdebug it is reported as a use after free. the runtime keeps that length in the block header, so a request over 2^31 - 6 words stops at the allocation with `zc: out of heap memory`. a pointer into the middle of a block, a frame array, a global or memory managed by hand is not checked. a constant index 0, and an index a loop test `i < k` with constant `k` (or `i < len(a)`) has already proved, are not checked again. a failed check prints `zy: index I out of range (length N)` and stops, as in 3.13.4. 3.7.5 an index must be a number (typecheck on). @@ -624,7 +624,7 @@ o3 int sum(fixed int[?] a) { int s = 0; for (int i = 0; i < len(a); i++) s += a[ ### 4.11 memdebug -`memdebug on;` turns on heap header checks and allocation-site tracking from this point in the file (top level) or from this point in the function (statement); the runtime enables the checks before `main` for the top-level form. `memdebug scrub;` additionally fills freed payloads with 57005; `memdebug off;` stops. with checks on, a use after free prints `zy: use after free from line N`, a double free prints `zy: double free from line N` and returns, a stray address prints `zy: bad heap pointer`. `rt.memreport()` prints a line `leak: line N W words` per live recorded object and returns the count. +`memdebug on;` turns on heap header checks and allocation-site tracking from this point in the file (top level) or from this point in the function (statement); the runtime enables the checks before `main` for the top-level form. `memdebug scrub;` additionally fills freed payloads with 57005; `memdebug off;` stops. with checks on, a use after free prints `zy: use after free from line N`, a double free prints `zy: double free from line N` and returns, a stray address prints `zy: bad heap pointer`. `rt.memreport()` prints a line `leak: line N W words` per live recorded object (W is the n words new asked for, not the block's payload) and returns the count. ### 4.12 hints diff --git a/examples/learn/13-memdebug.out b/examples/learn/13-memdebug.out index f788938..356a57c 100644 --- a/examples/learn/13-memdebug.out +++ b/examples/learn/13-memdebug.out @@ -1,2 +1,2 @@ -leak: line 6 3 words +leak: line 6 1 words 1 diff --git a/src/compiler/expr.zc b/src/compiler/expr.zc index e449508..a548f8d 100644 --- a/src/compiler/expr.zc +++ b/src/compiler/expr.zc @@ -171,7 +171,7 @@ int newtyped() { lit(tsz(t)); lit(t); newsz = tsz(t); newleaf = 0; if (isleaf(t)) newleaf = t; - if (!o3on && !dry && lookup(s_new_k) >= 0) { lit(szclass(newsz)); fast = 1; } + if (newsz <= 0x7FFFFFFF - rt.HDR && !o3on && !dry && lookup(s_new_k) >= 0) { lit(szclass(newsz)); fast = 1; } } expect(s_rp); stamp_site(); @@ -450,7 +450,7 @@ int call(int s) { xaf = af_new(newsz, 2, cp); if (lsp > 0) newloop(cp); // a constant size: the class is known now, so use the allocator's direct path - if (newsz >= 0 && !o3on && !dry && lookup(s_new_k) >= 0) { + if (newsz >= 0 && newsz <= 0x7FFFFFFF - rt.HDR && !o3on && !dry && lookup(s_new_k) >= 0) { // (a bigger size has no class: new_t stops it) lit(0); lit(szclass(newsz)); s = lookup(s_new_k); diff --git a/src/core/stack.h b/src/core/stack.h index f699b52..8c7f7a2 100644 --- a/src/core/stack.h +++ b/src/core/stack.h @@ -84,7 +84,7 @@ static Cell stack_allocate(Cell words) m[b + 2] = 0; m[b + 5] = 0; m[b + 6] = 0; continue; } p = b + 5; - m[b] = (Cell)1 << k; m[b + 1] = ((Cell)k << 16) | 1 | 512 | 1024 | (stack_get(SC_GC_ACTIVE) ? 2 : 0); + m[b] = (Cell)1 << k; m[b + 1] = ((Cell)k << 16) | 1 | 512 | 1024 | (stack_get(SC_GC_ACTIVE) ? 2 : 0) | ((Cell)words << 32); /* n, as rt.zc's new_raw */ m[b + 2] = p ^ 0x2B7E1516; m[b + 3] = 0; m[b + 4] = -words - 1; for (i = p; i < b + ((Cell)1 << k); i++) m[i] = 0; return p; diff --git a/src/js/tinyvm.ts b/src/js/tinyvm.ts index f52d4af..51b390b 100644 --- a/src/js/tinyvm.ts +++ b/src/js/tinyvm.ts @@ -344,7 +344,7 @@ export class TinyVM { this.mem[block + 2] = this.mem[block + 5] = this.mem[block + 6] = 0n; continue; } const pointer = block + 5; - this.mem[block] = BigInt(2 ** k); this.mem[block + 1] = BigInt(k * 65536 + 1537 + (this.stackGet(16) ? 2 : 0)); + this.mem[block] = BigInt(2 ** k); this.mem[block + 1] = BigInt(k * 65536 + 1537 + (this.stackGet(16) ? 2 : 0)) + (BigInt(words) << 32n); // n, as rt.zc's new_raw this.mem[block + 2] = BigInt(pointer) ^ 0x2B7E1516n; this.mem[block + 3] = 0n; this.mem[block + 4] = -BigInt(words) - 1n; this.mem.fill(0n, pointer, block + 2 ** k); return pointer; 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++; } } 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 diff --git a/tests/programs/bounds_heap.zc b/tests/programs/bounds_heap.zc index d0bd318..719757e 100644 --- a/tests/programs/bounds_heap.zc +++ b/tests/programs/bounds_heap.zc @@ -1,12 +1,13 @@ namespace; include rt; -// a pointer to the start of a live heap block is checked against the block's -// payload, which a buddy block rounds up: rt.new(4) holds 11 words. a pointer +// a pointer to the start of a live heap block is checked against exactly the +// words new asked for: rt.new(11) holds 11 words (its block holds 11 too, but +// rt.new(4) would hold 4, not the 11 its 16-word block has room for). a pointer // into the middle of a block, or to memory that is not a heap block, is not // checked. a char is a word, so a char* counts words. int main() { - int* p = rt.new(4); int* q; char* c = rt.new(2); int i = 10; + int* p = rt.new(11); int* q; char* c = rt.new(3); int i = 10; p[i] = 3; rt.put_n(p[i]); rt.put_c(10); q = p + 1; i = 10; rt.put_n(q[i - 1] - 3); rt.put_c(10); i = 2; c[i] = 'x'; rt.put_c(c[i]); rt.put_c(10); diff --git a/tests/programs/exactsize.zc b/tests/programs/exactsize.zc new file mode 100644 index 0000000..c3b22cc --- /dev/null +++ b/tests/programs/exactsize.zc @@ -0,0 +1,42 @@ +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; +} diff --git a/tests/programs/quarantine.zc b/tests/programs/quarantine.zc index 061c4da..5697400 100644 --- a/tests/programs/quarantine.zc +++ b/tests/programs/quarantine.zc @@ -3,8 +3,10 @@ include rt; // free quarantines the block. a stale alias still reads it, and freeing // through the alias does nothing because the header already says free. -// unchecked so the analyzer doesn't reject the use after free. -unchecked fn main() { +// unchecked so the analyzer doesn't reject the use after free, and unbounded +// because a freed block has length 0 (a checked stale index traps, see +// tests/conformance/8-runtime/stale_index_after_free_traps.zc). +unchecked unbounded fn main() { let p = rt.new(4), q, r, i = 0, t, bad = 0; p[0] = 111; p[1] = 222; p[2] = 333; p[3] = 444; q = p; diff --git a/tests/test.sh b/tests/test.sh index 9dd04a8..78b1f77 100755 --- a/tests/test.sh +++ b/tests/test.sh @@ -166,7 +166,7 @@ hello world!42 256 v" "$l a full capture is still terminated inside its buffer" chk "$($vm < tests/programs/sys.zc)" "2 zy time" "$l syscalls: write, read, time" - chk "$($vm < tests/programs/memleak.zc)" $'leak: line 8 3 words\n1' "$l memdebug names a live allocation" + chk "$($vm < tests/programs/memleak.zc)" $'leak: line 8 1 words\n1' "$l memdebug names a live allocation" chk "$($vm < tests/programs/uaf.zc)" $'zc: line 10: warning: use after free: this storage\'s lifetime ended on line 9\nzy: use after free from line 7\n at <stdin>:10 in main' "$l memdebug: use after free" chk "$($vm < tests/programs/uaf_in.zc)" $'zy: use after free from line 7\n at <stdin>:11 in main' "$l memdebug: use after free through an interior pointer" chk "$($vm < tests/programs/doublefree.zc)" $'zy: double free from line 7\n at <stdin>:9 in main\nok' "$l memdebug: double free is reported and does nothing" |