From d55b5fdf92a674a6495878f97a09e95bafdcba3f Mon Sep 17 00:00:00 2001 From: zinc Date: Wed, 14 Oct 2026 15:58:58 +0330 Subject: bounds checking: port agent/bounds-checking onto main 0879d0a; unbounded main in o3call, o3 tests expect no check, boundsrules, bounds_fixed, bounds_heap and zc0unbounded tests --- src/compiler/analyzer.zc | 20 +++++++++++ src/compiler/base.zc | 12 ++++--- src/compiler/builtins.zc | 1 + src/compiler/check.zc | 4 +-- src/compiler/decl.zc | 34 +++++++++++-------- src/compiler/expr.zc | 75 +++++++++++++++++++++++++++++++++++------- src/compiler/setup.zc | 3 +- src/compiler/stmt.zc | 15 ++++++++- src/compiler/types.zc | 9 ++--- src/core/core.zc | 3 ++ src/lib/actor.zc | 4 +-- src/lsp/server.zc | 3 ++ src/runtime/rt.zc | 31 +++++++++++++++++ src/runtime/run.zc | 3 ++ src/tools/build.zc | 3 ++ src/tools/zc0.c | 5 +-- tests/parity.known | 3 ++ tests/programs/bounds_fixed.zc | 17 ++++++++++ tests/programs/bounds_heap.zc | 16 +++++++++ tests/programs/bounds_hi.zc | 3 +- tests/programs/boundsrules.zc | 24 ++++++++++++++ tests/programs/o3_bounds.zc | 3 +- tests/programs/o3call.zc | 2 +- tests/programs/zc0unbounded.zc | 16 +++++++++ tests/test.sh | 11 +++++-- 25 files changed, 274 insertions(+), 46 deletions(-) create mode 100644 tests/programs/bounds_fixed.zc create mode 100644 tests/programs/bounds_heap.zc create mode 100644 tests/programs/boundsrules.zc create mode 100644 tests/programs/zc0unbounded.zc diff --git a/src/compiler/analyzer.zc b/src/compiler/analyzer.zc index 8c63bdf..89713ff 100644 --- a/src/compiler/analyzer.zc +++ b/src/compiler/analyzer.zc @@ -500,6 +500,26 @@ int proven(int a, int ix) { } return 0; } +// i >= 0 and i < n for a fixed array of n elements, proved by a loop test +// against a constant of at most n and a step of +1 (kw_for records the +// constant as the array field, minus two, with -1 for the bound local) +int proven_n(int ix, int n) { + int k = lsp, w; + while (k > loopbase) { + k--; + w = lpfact[k]; + if (w >= 0 && p_iv(w) == ix && p_bd(w) == -1 && 0 - p_ar(w) - 2 <= n) return 1; + } + return 0; +} +// is the constant index xcval known to be inside the allocation f? the same +// facts af_index warns from, so a possible failure is never called definite. +int af_inrange(word f) { + int lower = 0; word base; + if (!f || !xconst || f[1] == 2 || f[0] < 0) return 0; + if (f[6]) { base = af_base(f); if (base[1] == 0 || base[10] < 0) return 0; if (f[14]) lower = f[13]; } + return xcval >= lower && xcval < f[0]; +} // follow child links up to the local that really owns the object int lroot(int i) { while (lstate[i] == S_CHILD) i = lowner[i]; diff --git a/src/compiler/base.zc b/src/compiler/base.zc index 2f802b9..8c13201 100644 --- a/src/compiler/base.zc +++ b/src/compiler/base.zc @@ -1,6 +1,9 @@ namespace run; include rt; +// the compiler pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // ============================================================================ // compiler.zc: the resident zc compiler. it lives in the genome next to the // runtime, compiles source straight to vm words in memory, and is visible to @@ -213,6 +216,7 @@ char* module_name; word module_imports; int nbin, nun, nasg, nkop, seqtop; char* mnem = "q@!$_~cjzr,?.+-*&|^><%"; int check_on = 1; // set to 0 to switch the analyzer off for what follows +int bound_on = 1; // set to 0 by unbounded; to switch index bounds checks off for what follows int tk; word tv; int tglue, tline, line = 1, ch, chkind; word chptr, chbase; int qdone, isp = -1, pendot; // where the current token sits in its source (chars from the start, -1 for a token list), how long it is, and where the one before it ended int toff = -1, toklen, tpend = -1, tpline; @@ -240,7 +244,7 @@ int pk_tk, pk_tv, pq_n; word[4] pq_tk; word[4] pq_tv; word[4] pq_gl; word[4] pq_ int here, hdelta, hlimit, ptop; int code_chunk = rt.CODE_END; word image_buffer, image_words; int image_active, image_org, image_capacity, image_size; -int nloc, lbase, fdepth, fslots, fchk, fret, live, bxdepth, epichain, fframe, infn; +int nloc, lbase, fdepth, fslots, fchk, fbnd, bnxt, fret, live, bxdepth, epichain, fframe, infn; // a global that borrows a local owner through g = m*x. each entry is the global's // symbol, the local, and the block depth of the store; the lend ends when the same // global is assigned again in that block, and is an error if the block can end first. @@ -271,7 +275,7 @@ int lv, lvk, lvi, kw_expr, xcls, fty; int s_lp, s_rp, s_lb, s_rb, s_lk, s_rk, s_comma, s_semi, s_eq, s_arrow, s_inc, s_dec; int s_star, s_slash, s_amp, s_colon, s_hash, s_minus, s_andand, s_oror; -int s_dot, s_fn, s_var, s_const, s_else, s_as, s_unchecked, s_immediate, s_m, s_d, s_u; +int s_dot, s_fn, s_var, s_const, s_else, s_as, s_unchecked, s_unbounded, s_immediate, s_m, s_d, s_u; int s_q, s_case, s_default, s_fovf, s_start, s_main, s_free, s_recycle, s_own, s_qnew, s_enhance, s_micro, s_vm; int s_frame_floor, s_frame_top, s_frame_node, s_frame_busy, s_frame_guard, s_frame_grow, s_frame_leave; int s_copy_w; @@ -310,7 +314,7 @@ word readonly_types; int dty, dtag; // result of dtype() int s_typedef; int s_lt, s_gt, s_shr, s_le, s_ge, s_eqeq, s_ne, s_plus, s_struct, s_type, s_typecheck, s_docs, s_lines, s_small, s_std, s_icon, s_on, s_off, s_new, s_new_t; -int s_o3, s_lfa, s_outside, s_new_raw, s_new_oz, s_oob; +int s_o3, s_lfa, s_outside, s_new_raw, s_new_oz, s_oob, s_bchk, s_bnd; int s_ld8, s_st8, s_ld16, s_st16, s_ld32, s_st32; // ---- o3 region state ---- @@ -320,7 +324,7 @@ int o3on, o3nxt, o3one; word[32] o3sl; word[32] o3rg; int no3sl; word[O3_REGIONS word[8] o3free; int no3free, o3nreg; word[NL] o3cache_initial; word o3cache = o3cache_initial; int argloc, s_hitems, s_hlen, s_fatten; // operator names used by numeric type checks. word[12] numops; int nnumops, s_fixed, s_dlen, s_dcap, s_dnew, s_dat, s_dpush, s_dpop, s_dresize, xconst, xcval; -int xlenloc, arrloc, fortest, forstep, ft_iv, ft_bd, ft_ir, ft_nops, fs_ok, xstamp; +int xlenloc, arrloc, fortest, forstep, ft_iv, ft_bd, ft_ir, ft_ck, ft_nops, fs_ok, xstamp; // local lower bound / len(array); one proof record per live loop int nfact, factcap = RANGE_FACTS; word[RANGE_FACTS] floc_initial, flo_initial, flen_initial; word floc = floc_initial, flo = flo_initial, flen = flen_initial; int s_len_s, s_at_s, s_slice_s, s_cat_s, s_eq_s, s_lt_s, s_le_s, s_put_bs, s_put_s, s_n_to_s, s_new_s; diff --git a/src/compiler/builtins.zc b/src/compiler/builtins.zc index 5d7bc9c..dd01bd8 100644 --- a/src/compiler/builtins.zc +++ b/src/compiler/builtins.zc @@ -1190,6 +1190,7 @@ int types_init() { s_outside = intern("rt.outside"); s_new_raw = intern("rt.new_raw"); s_oob = intern("rt.oob"); + s_bchk = intern("rt.bchk"); s_bnd = intern("rt.bnd"); s_new_oz = intern("rt.new_oz"); s_ld8 = intern("rt.ld8"); s_st8 = intern("rt.st8"); s_ld16 = intern("rt.ld16"); s_st16 = intern("rt.st16"); s_ld32 = intern("rt.ld32"); s_st32 = intern("rt.st32"); diff --git a/src/compiler/check.zc b/src/compiler/check.zc index f3374b1..945b800 100644 --- a/src/compiler/check.zc +++ b/src/compiler/check.zc @@ -32,7 +32,7 @@ int chk_reset() { defer_drop(0); dfr_base = 0; dfr_on = 0; fdepth = 0; fslots = 0; - fchk = 0; + fchk = 0; fbnd = 0; bnxt = 0; fret = 0; live = 0; bxdepth = 0; @@ -41,7 +41,7 @@ int chk_reset() { xbor = 0 - 1; xaf = 0; argfact = 0; xvk = 0; if (svkind) rt.fill_w(svkind, 0, symcap); mdbg = 0; mdbg_flags = 0; lv = 0; lvk = 0; lvi = 0; kw_expr = 0; xcls = 0; fty = 0; - check_on = 1; tc_on = ifstrict; dry = 0; ntp = 0; tvauto = 0; ngbind = 0; xgive = 0; xconst = 0; + check_on = 1; bound_on = 1; tc_on = ifstrict; dry = 0; ntp = 0; tvauto = 0; ngbind = 0; xgive = 0; xconst = 0; o3on = 0; o3nxt = 0; no3pend = 0; no3sl = 0; no3free = 0; o3nreg = 0; o3na = 0; o3fn0 = 0; nfact = 0; fortest = 0; forstep = 0; argloc = 0; arrloc = 0; njps = 0; extop = 0; nnumops = 0; nenh = 0; panic = 0; nerr = 0; dgprev = 0; nclo = 0; newsz = 0 - 1; nomagic = 0; callpos = 0; diff --git a/src/compiler/decl.zc b/src/compiler/decl.zc index cc84603..36a307d 100644 --- a/src/compiler/decl.zc +++ b/src/compiler/decl.zc @@ -153,7 +153,7 @@ int unit_stdin() { // that a nested compile would otherwise clobber (locals, depth, frame size, // loop stack position, the expression-state globals). closures use the same // pair. -const int CTX_WORDS = 49; +const int CTX_WORDS = 50; int ctx_push() { af_forget(); word f; @@ -164,7 +164,7 @@ int ctx_push() { f[13] = lv; f[14] = lvk; f[15] = lvi; f[16] = kw_expr; f[17] = xcls; f[18] = snaptop; f[19] = fty; f[20] = ntp; f[21] = xty; rt.copy_w(f + 22, tpn, 8); f[30] = finsym; f[31] = finfer; f[32] = ifcur; f[33] = ifcall; f[34] = effect_current; f[35] = borrow_slots; f[36] = borrow_pending; f[37] = borrow_depth; f[38] = borrow_jump; f[39] = borrow_entry; f[40] = capture_enabled; f[41] = effect_value; f[42] = xprojection; f[43] = effect_floor; f[44] = module_name; f[45] = module_imports; - f[46] = fn_return_type; f[47] = if_value; f[48] = dfr_base; + f[46] = fn_return_type; f[47] = if_value; f[48] = dfr_base; f[49] = fbnd; return 0; } // pop the innermost function context. @@ -186,7 +186,7 @@ int ctx_pop() { lv = f[13]; lvk = f[14]; lvi = f[15]; kw_expr = f[16]; xcls = f[17]; snaptop = f[18]; fty = f[19]; ntp = f[20]; xty = f[21]; rt.copy_w(tpn, f + 22, 8); finsym = f[30]; finfer = f[31]; ifcur = f[32]; ifcall = f[33]; effect_current = f[34]; borrow_slots = f[35]; borrow_pending = f[36]; borrow_depth = f[37]; borrow_jump = f[38]; borrow_entry = f[39]; capture_enabled = f[40]; effect_value = f[41]; xprojection = f[42]; effect_floor = f[43]; module_name = f[44]; module_imports = f[45]; xvk = 0; - fn_return_type = f[46]; if_value = f[47]; + fn_return_type = f[46]; if_value = f[47]; fbnd = f[49]; return 0; } @@ -206,10 +206,12 @@ int fn_begin(int chk, int ret) { if (cmode && svkind && !dry) rt.fill_w(svkind, 0, nsym); xvk = 0; lend_drop(1 << 30, nloc); dfr_base = ndfr; - lbase = nloc; fdepth = 1; fslots = 0; fchk = chk && check_on; fret = ret; fty = 0; finfer = 0; fn_return_type = 0; + lbase = nloc; fdepth = 1; fslots = 0; fchk = chk && check_on; fbnd = !bnxt && bound_on; bnxt = 0; fret = ret; fty = 0; finfer = 0; fn_return_type = 0; live = 1; bxdepth = 0; epichain = 0; infn = 1; loopbase = lsp; lv = 0; lvk = LV_NONE; xbor = -1; return 0; } +// the bounds flag of the function that was being compiled when the innermost context was pushed +int ctx_bnd() { return R_CTX[(ctxsp - 1) * CTX_WORDS + 49]; } // allocate the frame, retaining the caller's pointer until any growth finishes. int prologue() { int k, busy, done, helper = !nclo && (sname[finsym] == s_frame_grow || sname[finsym] == s_frame_leave); @@ -570,7 +572,7 @@ int topsync() { if (is_op(s_lb)) depth++; else if (is_op(s_rb)) { depth--; if (depth < 0) depth = 0; } else if (!depth && tk == T_ID && (tv == s_fn || tv == s_var || tv == s_const || tv == s_struct || tv == s_type || tv == s_typedef - || tv == s_enhance || tv == s_typecheck || tv == s_docs || tv == s_lines || tv == s_unchecked || tv == s_immediate || tv == s_o3 + || tv == s_enhance || tv == s_typecheck || tv == s_docs || tv == s_lines || tv == s_unchecked || tv == s_unbounded || tv == s_immediate || tv == s_o3 || tv == s_memdebug || tv == s_enum || tv == s_include)) break; next(); } @@ -647,14 +649,20 @@ int topitem0() { int topitem1() { int chk = 1, imm = 0, s, k, n; if (panic) return topsync(); - if (is_id(s_unchecked)) { - next(); - if (accept(s_semi)) { check_on = 0; return 0; } // unchecked; switches the analyzer off from here on - chk = 0; + o3nxt = 0; bnxt = 0; + while (1) { // the prefixes, in any order + if (is_id(s_unchecked)) { + next(); + if (accept(s_semi)) { check_on = 0; return 0; } // unchecked; switches the analyzer off from here on + chk = 0; + } else if (is_id(s_unbounded)) { + next(); + if (accept(s_semi)) { bound_on = 0; return 0; } // unbounded; switches the index bounds checks off from here on + bnxt = 1; + } else if (is_id(s_immediate)) { next(); imm = 1; } + else if (is_id(s_o3)) { next(); o3nxt = 1; } + else break; } - if (is_id(s_immediate)) { next(); imm = 1; } - o3nxt = 0; - if (is_id(s_o3)) { next(); o3nxt = 1; } ntp = 0; ifkk = 0; if (is_id(s_fn)) { peek(); @@ -669,7 +677,7 @@ int topitem1() { return fndone(fndef(chk, 0, 0, n), imm); } } - if (!chk || imm || o3nxt) { // has to be a function, with a return type + if (!chk || imm || o3nxt || bnxt) { // has to be a function, with a return type ifkp = tpack(); ifkk = 0 - 1; if (is_op(s_dot)) ifkk = 2; if (isp != 0) ifkk = 0; rettype(); n = name(); if (ginst) n = ginsn; genparams(); diff --git a/src/compiler/expr.zc b/src/compiler/expr.zc index f41109e..c76b74c 100644 --- a/src/compiler/expr.zc +++ b/src/compiler/expr.zc @@ -678,7 +678,7 @@ int closure() { nclo++; hop = hole(); op(O_JMP); entry = here; - fn_begin(1, 0); + fn_begin(1, 0); fbnd = ctx_bnd(); lt = lt_begin(entry, "", lfl); if (declared) fty = declared; prologue(); borrow_prologue(); @@ -1321,17 +1321,47 @@ int range_jz(int ix, int src, int fld) { setlit(k, here); return 0; } +// the inline check of a fixed array T[n]: the index is on top of the stack and +// stays there. one "outside" enhancement against the constant length and a +// branch to the oob report, the same shape as range_jz. +int fixed_chk(int n) { + int k = lookup(s_outside), j; + if (k < 0 || skind[k] != K_ENH) return 0; + lit(0); op(O_PICK); lit(n); op(XOP0 + sval[k]); + j = hole(); op(O_JZ); + lit(n); callname(s_oob); + setlit(j, here); + return 0; +} +// the check of a pointer index: base and index are on the stack and stay there. +// the runtime knows a size only for a pointer to the start of a live heap block +// and returns at once for any other pointer. sz is the element size in words, or +// minus the element size in bytes for packed elements. +int ptr_chk(int sz) { + int k = lookup(s_bnd), j; + if (k >= 0 && skind[k] == K_ENH) { // the test is one enhancement; the call only runs to report + lit(1); op(O_PICK); lit(1); op(O_PICK); + if (sz > 0) { lit(sz); lit(1); } else { lit(0 - sz); lit(8); } + op(XOP0 + sval[k]); + j = hole(); op(O_JZ); + } + lit(1); op(O_PICK); lit(1); op(O_PICK); lit(sz); callname(s_bchk); op(O_DROP); + if (k >= 0 && skind[k] == K_ENH) setlit(j, here); + return 0; +} // suffixes after a primary, in a loop: e as T, [index], .field, ->field, // (call through a value), ++ and --. the index case is the long one. a byte -// string takes an index or a slice. a growable array is checked: through dat() -// normally, but inline when the compiler can prove or cheaply test the bound -// (o3 code with the cache variables, or an index the loop test already -// compared with the length). a plain pointer or fixed array is just base + -// index * size, and a constant index against a known length is checked at -// compile time. +// string takes an index or a slice. every index is bounds checked unless the +// function, block or unit is unbounded or the code is o3. a growable array is +// checked through dat() normally, but inline when the compiler can prove or +// cheaply test the bound (o3 code with the cache variables, or an index the +// loop test already compared with the length). a fixed array T[n] is checked +// inline against n (at compile time for a constant index, not at all when a +// loop test against a constant already proved it). a plain pointer goes +// through rt.bchk, which only knows the size of a heap block's first word. int postfix() { return postfix_tail(primary()); } int postfix_tail(int c) { - int b, n, t, et; word ft; word[8] bs; int k, ci, was, al, ix, enh, cz, cj, place, offset, temporary, call_owner, readonly; word storage, storage_mask, call_origins; + int b, n, t, et; word ft; word[8] bs; int k, ci, was, al, ix, enh, cz, cj, place, offset, temporary, call_owner, readonly, ub, bl, ic, inr; word storage, storage_mask, call_origins; while (1) { if (tk == T_ID && tv == s_as) { // e as T: same bits, another type next(); t = ptype(); rval(); if (!xaf || xaf[2] != 5) xaf = 0; vf_coerce(t, 0); @@ -1350,6 +1380,8 @@ int postfix_tail(int c) { ci = 0; if (lv && lvk == LV_LOCAL) lptr[lvi] = 1; if (o3on && lv && lvk == LV_LOCAL && o3cache[lvi]) ci = o3cache[lvi]; + ub = !fbnd || o3on || (lv && lvk == LV_LOCAL && (ltag[lvi] & 16)); // unbounded, or o3 code + bl = -1; if (lv && lvk == LV_LOCAL) bl = lvi; next(); rval(); if (was) { @@ -1377,7 +1409,11 @@ int postfix_tail(int c) { if (xconst) offset = xcval; af_index(storage, place); tcneed(isnum(xty) || xty == tword, "an index has to be a number", xty); expect(s_rk); - callname(intern("datb")); + if (ub) { // the byte address of the element, with no check + op(O_SWAP); lit(2); op(O_ADD); op(O_LD); lit(8); op(15); op(O_SWAP); + if (tbytes(et) != 1) { lit(tbytes(et)); op(15); } + op(O_ADD); + } else callname(intern("datb")); et = tpk(et); } else if (xty[0] == TY_DYN) { // a growable array: bounds-checked, through the runtime et = xty[4]; @@ -1393,7 +1429,10 @@ int postfix_tail(int c) { expect(s_rk); k = lookup(s_outside); enh = k >= 0 && skind[k] == K_ENH; - if (!mdbg && ix >= 0 && al >= 0 && proven(al, ix)) { // the loop test already compared this index with the length + if (ub) { // unbounded, or o3: just the address + if (ci && !mdbg && lookup(s_outside) >= 0) { vaddr(ci); op(O_LD); op(O_SWAP); mulsz(et); op(O_ADD); } + else addr_stk(et); + } else if (!mdbg && ix >= 0 && al >= 0 && proven(al, ix)) { // the loop test already compared this index with the length if (ci) { vaddr(ci); op(O_LD); op(O_SWAP); mulsz(et); op(O_ADD); } else addr_stk(et); } else if (ci && !mdbg && enh && ix >= 0) { @@ -1433,13 +1472,26 @@ int postfix_tail(int c) { et = telem(xty); n = 0 - 1; if (xty[0] == TY_ARR && xty[3] > 0) n = xty[3]; xconst = 0; - c = expr(); rval(); plainuse(c); + c = expr(); + ix = -1; + if (lv && lvk == LV_LOCAL) ix = lvi; + rval(); plainuse(c); + ic = xconst; if (xconst) offset = xcval; if (n < 0) af_index(storage, place); if (n >= 0 && xconst && (xcval < 0 || xcval >= n)) { serr("the index is out of range for this array"); } + inr = 0; // no check needed: the index is 0, or the analyzer knows it is inside the allocation + if (ic && xcval == 0) inr = 1; + if (ic && n < 0 && !tbytes(et) && tsz(et) == 1 && af_inrange(storage)) inr = 1; + if (bl >= 0 && n < 0 && larr[bl]) inr = 1; // an array in a frame has no heap header to read tcneed(isnum(xty) || xty == tword, "an index has to be a number", xty); expect(s_rk); + if (!ub && !inr) { + if (n >= 0) { if (!ic && !(ix >= 0 && proven_n(ix, n))) fixed_chk(n); } + else if (tbytes(et)) ptr_chk(0 - tbytes(et)); + else ptr_chk(tsz(et)); + } if (tbytes(et)) { // packed: byte address = base * 8 + index * bytes if (tbytes(et) != 1) { lit(tbytes(et)); op(15); } op(O_SWAP); lit(8); op(15); op(O_ADD); @@ -1665,6 +1717,7 @@ int bin(int minp) { if (c >= C_VAR && tracked(c - C_VAR)) rb = lroot(c - C_VAR); else rb = xbor; if (top) { ft_ir = -1; if (lv && lvk == LV_LOCAL) ft_ir = lvi; } rval(); plainuse(c); + if (top) { ft_ck = -1; if (xconst && xcval >= 0) ft_ck = xcval; } if (cmode && bname[b] == s_star && xconst && xcval >= 2 && !(xcval & (xcval - 1)) && !lf) { shifthint(opp, xcval); } diff --git a/src/compiler/setup.zc b/src/compiler/setup.zc index 9ed938b..26a18e0 100644 --- a/src/compiler/setup.zc +++ b/src/compiler/setup.zc @@ -46,7 +46,7 @@ int zc_init() { s_andand = intern("&&"); s_oror = intern("||"); s_fn = intern("fn"); s_var = intern("let"); s_const = intern("const"); s_else = intern("else"); - s_as = intern("as"); s_unchecked = intern("unchecked"); s_immediate = intern("immediate"); + s_as = intern("as"); s_unchecked = intern("unchecked"); s_unbounded = intern("unbounded"); s_immediate = intern("immediate"); s_m = intern("m"); s_d = intern("d"); s_u = intern("u"); s_static = intern("static"); s_start = intern("run.start"); s_main = intern("main"); @@ -113,6 +113,7 @@ int zc_tables() { add_kw("defer", kw_defer, F_STMT); add_kw("return", kw_return, F_STMT); add_kw("unchecked", kw_unchecked, F_STMT); + add_kw("unbounded", kw_unbounded, F_STMT); add_kw("asm", kw_asm, F_STMT | F_EXPR); add_kw("quote", kw_quote, F_EXPR); add_kw("sizeof", kw_sizeof, F_EXPR); diff --git a/src/compiler/stmt.zc b/src/compiler/stmt.zc index 4dafe4f..505e466 100644 --- a/src/compiler/stmt.zc +++ b/src/compiler/stmt.zc @@ -323,7 +323,7 @@ int kw_for() { borrow_cleanup_since(borrow_mark); s0 = snap_push(); c0 = here; - ft_iv = -1; fs_ok = 0; fortest = 1; + ft_iv = -1; ft_ck = -1; fs_ok = 0; fortest = 1; if (!is_op(s_semi)) { if (tk == T_NUM && tv) { peek(); if (pk_tk == T_OP && pk_tv == s_semi) inf = 1; } c = borrow_condition(); @@ -344,6 +344,8 @@ int kw_for() { loop_push(st, s0); if (ft_iv >= 0 && ft_bd >= 0 && fs_ok && getlo(ft_iv) >= 0 && getln(ft_bd) >= 0) { lpfact[lsp - 1] = pfact(ft_iv, ft_bd, getln(ft_bd)); + } else if (ft_iv >= 0 && ft_ck >= 0 && fs_ok && getlo(ft_iv) >= 0) { // i < constant: proves a fixed array that long + lpfact[lsp - 1] = pfact(ft_iv, -1, 0 - ft_ck - 2); } substmt(); backedge(s0); @@ -724,6 +726,17 @@ int kw_unchecked() { return 0; } +// unbounded turns the index bounds checks off for one statement +int kw_unbounded() { + int old = fbnd; + stmtonly(); + next(); + fbnd = 0; + substmt(); + fbnd = old; + return 0; +} + // ---- asm blocks: raw vm words, one per token ---- // numbers push, -n pushes a negative number, #n emits a raw word, one-char diff --git a/src/compiler/types.zc b/src/compiler/types.zc index 6dda110..ca31248 100644 --- a/src/compiler/types.zc +++ b/src/compiler/types.zc @@ -567,7 +567,7 @@ int kw_struct() { if (tk == T_EOF) { die("missing }"); break; } stat = 0; if (struct_const_start()) { struct_const(n); continue; } - if (is_id(s_unchecked)) { next(); stat = 2; } + while (is_id(s_unchecked) || is_id(s_unbounded)) { if (is_id(s_unchecked)) stat = stat | 2; else stat = stat | 4; next(); } if (is_id(s_static)) { // static fn name(params) { body }, or static T name(params) { body }: a function of the struct, called as Struct.name(args), with no this next(); stat = stat | 1; @@ -746,7 +746,7 @@ int tkput(word r, int k, int kind, int val, int pl) { } // compile a struct method once the struct is complete. int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) { - int n = q[0]; word r; int i, k = 0, lnp, unchecked_method = stat & 2; + int n = q[0]; word r; int i, k = 0, lnp, unchecked_method = stat & 2, unbounded_method = stat & 4, pc = (stat & 2) / 2 + (stat & 4) / 4; stat = stat & 1; if (!n) { rt.free(q); return 0; } if (!stat) { @@ -759,6 +759,7 @@ int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) r = rt.new((n + 8 + mdg * 4) * 3 + 1); lnp = q[3]; if (unchecked_method) k = tkput(r, k, T_ID, s_unchecked, lnp); + if (unbounded_method) k = tkput(r, k, T_ID, s_unbounded, lnp); k = tkput(r, k, T_ID, s_fn, lnp); r[1 + k * 3] = T_ID; r[2 + k * 3] = methname(sn, mn); r[3 + k * 3] = lnp; k++; if (mdg) { // a method of a generic struct is a generic function over the struct's parameters: fn S.m(S* this, ...) @@ -806,7 +807,7 @@ int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) rt.free(q); if (typed && mdg) { // retain a typed generic method as ordinary typed function tokens. - int mode = rt.outmode, length = rt.outn, capacity = rt.outcap, prefix = unchecked_method != 0; + int mode = rt.outmode, length = rt.outn, capacity = rt.outcap, prefix = pc; word output = rt.outbuf, grow = rt.outgrow, buffer = rt.new(4096), return_tokens, joined; rt.outmode = 2; rt.outbuf = m*buffer; rt.outn = 0; rt.outcap = 4095; rt.outgrow = 0; tprint(rty); if (rtag) rt.put_s(".u"); buffer[rt.outn] = 0; @@ -824,7 +825,7 @@ int methdef(char* sn, char* mn, word q, int stat, int typed, int rty, int rtag) } joined = rt.new((r[0] + return_tokens[0]) * 3 + 1); joined[0] = r[0] - 1 + return_tokens[0]; - if (prefix) rt.copy_w(joined + 1, r + 1, 3); + if (prefix) rt.copy_w(joined + 1, r + 1, prefix * 3); rt.copy_w(joined + 1 + prefix * 3, return_tokens + 1, return_tokens[0] * 3); rt.copy_w(joined + 1 + (prefix + return_tokens[0]) * 3, r + 1 + (prefix + 1) * 3, (r[0] - prefix - 1) * 3); rt.free(r); r = joined; rt.free(return_tokens); rt.free(buffer); diff --git a/src/core/core.zc b/src/core/core.zc index 61ecd1c..e730946 100644 --- a/src/core/core.zc +++ b/src/core/core.zc @@ -1,6 +1,9 @@ namespace core; include rt; +// the core pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // calls the host gate with an operation and three machine-word arguments. // returns the host result; negative values indicate a failed operation. int syscall(int operation, word a, word b, word c) { diff --git a/src/lib/actor.zc b/src/lib/actor.zc index 29fd600..a129f7f 100644 --- a/src/lib/actor.zc +++ b/src/lib/actor.zc @@ -53,11 +53,11 @@ unchecked int encode(word data, word refs, word address, word type) { } if (kind == 13) { n = rt.len_s(pointer); append(data, n); while (i < n) { append(data, rt.at_s(pointer, i)); i++; } return 0; } if (kind == 7) { - element = pointer[-1]; n = pointer[-5] - rt.HDR; + unbounded { element = pointer[-1]; n = pointer[-5] - rt.HDR; } // the object's header, on purpose append(data, n); append(data, element); encode(data, refs, pointer, element); return 0; } element = type[4]; bytes = packed(element); - if (rt.isobj(pointer)) n = pointer[-5] - rt.HDR; + if (rt.isobj(pointer)) { unbounded n = pointer[-5] - rt.HDR; } else if (element[0] == 2) n = rt.len_w(pointer) + 1; else n = size(element); append(data, n); diff --git a/src/lsp/server.zc b/src/lsp/server.zc index c3f9f4f..9a903f0 100644 --- a/src/lsp/server.zc +++ b/src/lsp/server.zc @@ -1,6 +1,9 @@ namespace lsp; include rt, run; +// the server pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // ============================================================================ // server.zc: the language server. it is appended to the genome after the // compiler (the files of src/compiler/parts in order, then this one, read as one stream), so it does not diff --git a/src/runtime/rt.zc b/src/runtime/rt.zc index 4e52cb5..8c26161 100644 --- a/src/runtime/rt.zc +++ b/src/runtime/rt.zc @@ -1,6 +1,9 @@ namespace rt; include run; +// the runtime pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // ============================================================================ // rt.zc: the runtime half of the genome. memory map, i/o, arithmetic helpers, // the heap (size-class free lists) and the mark-sweep collector. @@ -84,6 +87,13 @@ enhance ishl(a, b) micro "a = shl a b"; enhance lfa(k) micro "r1 = ld 589824; k = add r1 k"; // 1 when i is outside 0..n-1 (the unsigned compare also catches negative i), else 0. enhance outside(i, n) micro "i = ltu i n; i = xor i 1"; +// the index check of a pointer, as one instruction: 1 when p is the start of a heap +// 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"; // ---- bit operations and float conversions ---- // these use single machine instructions where the cpu has them. @@ -1100,6 +1110,27 @@ word dat(word h, int i) { if (i < 0 || i >= h[0]) oob(i, h[0]); return h[2] + i * h[3]; } +// the bounds check of p[i] on a pointer (or an untyped word), emitted by the compiler +// in front of the access. a pointer has no length, but a pointer to the start of +// 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. +int bchk(word p, int i, int sz) { + int n; + if (p < HEAP_LO + HDR || p >= hbump || p[-3] != (p ^ MAGIC)) return 0; + n = paylen(p); + if (sz > 0) { + if (i >= 0 && i < n && i * sz < n) return 0; + oob(i, (n + sz - 1) / sz); + return 0; + } + sz = 0 - sz; n = n * 8; + if (i >= 0 && i < n && i * sz < n) return 0; + oob(i, (n + sz - 1) / sz); + return 0; +} // add x to the end of a growable array h, growing its items when they are full. the // array owns the items, so x is handed to it (tagged d). unchecked int dpush(word h, .d x) { diff --git a/src/runtime/run.zc b/src/runtime/run.zc index 19a5234..69fc30c 100644 --- a/src/runtime/run.zc +++ b/src/runtime/run.zc @@ -1,6 +1,9 @@ namespace run; include rt; +// the run-only runtime pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // run-only image: the runtime, a collector root set, and start. there is no // resident compiler and none of its tables. put this between rt.zc and a // program that defines main. zc0 accepts the bootstrap subset; build.zc uses diff --git a/src/tools/build.zc b/src/tools/build.zc index b628a33..b2f838f 100644 --- a/src/tools/build.zc +++ b/src/tools/build.zc @@ -1,6 +1,9 @@ namespace; include rt, run; +// the build tool pokes at headers and raw memory on purpose and runs at full speed: no index bounds checks +unbounded; + // compiles the rest of stdin (after the backtick) as a genome image at GORG // and writes it to stdout as little-endian 64-bit words. diff --git a/src/tools/zc0.c b/src/tools/zc0.c index 5846e22..af85ff8 100644 --- a/src/tools/zc0.c +++ b/src/tools/zc0.c @@ -463,7 +463,7 @@ static int notatype(void) static const char *w[] = { "return", "if", "else", "while", "for", "do", "break", "continue", "let", "var", "fn", "const", "enhance", "struct", "enum", "asm", "switch", "case", "default", "immediate", "type", "include", "as", "in", "new", "sizeof", "typeof", - "o3", "unchecked", 0 }; + "o3", "unchecked", "unbounded", 0 }; int i; if (tk != T_ID) return 0; for (i = 0; w[i]; i++) if (!strcmp(ts, w[i])) return 1; @@ -769,7 +769,7 @@ static void stmt(void) expect(";"); return; } } - if (accept("unchecked")) { stmt(); return; } + if (accept("unchecked") || accept("unbounded")) { stmt(); return; } if (accept("if")) { expect("("); expr(); rval(); ftest(); expect(")"); a = here; lit(0); op(O_JZ); stmt(); @@ -1014,6 +1014,7 @@ static void top1(void) } if (accept("embed")) { embeddecl(0); return; } { + if (accept("unbounded")) { if (accept(";")) return; top1(); return; } if (accept("unchecked")) { top1(); return; } if (accept("fn")) { fndef(0, 0); return; } if (accept("const")) { optype(); do { char *n = ident(); if (dsn && !dnm[0]) strcpy(dnm, n); expect("="); add(n, K_CONST, cexpr()); } while (accept(",")); expect(";"); return; } diff --git a/tests/parity.known b/tests/parity.known index 0a73eb3..6892499 100644 --- a/tests/parity.known +++ b/tests/parity.known @@ -13,3 +13,6 @@ tests/programs/uaf_in.zc # memdebug on: only the self-hosted compiler emits the examples/lists.zc # ownership: the block's owner frees at its end, zc0 never frees # the next program reads a local it never sets when stdin is empty, so it prints stack garbage tests/programs/bench_strings.zc # reads the repeat count from stdin; with none, acc is uninitialized +# zc0 reads unbounded and ignores it, and emits no index checks at all +tests/programs/bounds_fixed.zc # bounds checks: only the self-hosted compiler checks a fixed array index +tests/programs/bounds_heap.zc # bounds checks: only the self-hosted compiler checks a pointer into a heap block diff --git a/tests/programs/bounds_fixed.zc b/tests/programs/bounds_fixed.zc new file mode 100644 index 0000000..0b3f476 --- /dev/null +++ b/tests/programs/bounds_fixed.zc @@ -0,0 +1,17 @@ +namespace; +include rt; + +// a fixed array T[n] with a variable index is checked against n. a loop whose +// test is the constant n proves the index and drops the check; a constant +// index is checked when it is compiled. +int main() { + int[6] t; int i, s = 0, k = 6; + for (i = 0; i < 6; i++) t[i] = i * i; + for (i = 0; i < 6; i++) s = s + t[i]; + rt.put_n(s); rt.put_c(10); + i = 2; rt.put_n(t[i] + t[5]); rt.put_c(10); + i = 0; + while (i <= k) { s = t[i]; i++; } + rt.put_s("not reached\n"); + return 0; +} diff --git a/tests/programs/bounds_heap.zc b/tests/programs/bounds_heap.zc new file mode 100644 index 0000000..d0bd318 --- /dev/null +++ b/tests/programs/bounds_heap.zc @@ -0,0 +1,16 @@ +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 +// 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; + 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); + i = 11; + rt.put_n(p[i]); rt.put_c(10); + return 0; +} diff --git a/tests/programs/bounds_hi.zc b/tests/programs/bounds_hi.zc index 49639c5..5475764 100644 --- a/tests/programs/bounds_hi.zc +++ b/tests/programs/bounds_hi.zc @@ -1,7 +1,8 @@ namespace; include rt; -// the index is not the induction variable. i + 1 walks off the end. +// the index is not the induction variable. i + 1 walks off the end, but o3 +// implies unbounded: nothing checks it, and the write lands in the block's slack o3 fn main() { fixed int[?] f = rt.new(fixed int[?], 4); int n = len(f), i; diff --git a/tests/programs/boundsrules.zc b/tests/programs/boundsrules.zc new file mode 100644 index 0000000..1ae6a56 --- /dev/null +++ b/tests/programs/boundsrules.zc @@ -0,0 +1,24 @@ +namespace; +include rt; + +// unbounded turns the checks off: as a function prefix (in any order with +// unchecked), as a block, for one statement. o3 implies it. the last read is +// checked and stops the program. +int[8] pad; +int[4] a; + +unbounded int pre(int i) { return a[i] * 0 + 1; } +unchecked unbounded int both(int i) { return a[i] * 0 + 1; } +o3 int fast(int i) { return a[i] * 0 + 1; } +int blk(int i) { int r = 0; unbounded { r = a[i] * 0 + 1; } return r; } +int one(int i) { int r = 0; unbounded r = a[i] * 0 + 1; return r; } +int checked(int i) { return a[i]; } + +int main() { + int i = 5; + a[3] = 7; + rt.put_n(pre(i) + both(i) + fast(i) + blk(i) + one(i)); rt.put_c(10); + rt.put_n(checked(3)); rt.put_c(10); + rt.put_n(checked(i)); rt.put_c(10); + return 0; +} diff --git a/tests/programs/o3_bounds.zc b/tests/programs/o3_bounds.zc index eaf92eb..cd65548 100644 --- a/tests/programs/o3_bounds.zc +++ b/tests/programs/o3_bounds.zc @@ -1,5 +1,6 @@ namespace; include rt; -// an index outside a T[?] inside o3 code: caught by the inline check +// an index outside a T[?] inside o3 code: o3 implies unbounded, so nothing checks it +// (the write lands in the slack of the buddy block) and the program ends normally fn main() { int[?] a = rt.new(int[?], 5); o3 { int i = 7; a[i] = 1; } rt.free(d*a); return 0; } diff --git a/tests/programs/o3call.zc b/tests/programs/o3call.zc index d2292ad..3ad977b 100644 --- a/tests/programs/o3call.zc +++ b/tests/programs/o3call.zc @@ -19,7 +19,7 @@ unchecked o3 int nest(int n) { if (n == 0) return 0; return n + nest(n - 1); } -unchecked fn main() { +unchecked unbounded fn main() { // reads p[-1], the type word, on purpose node* n = leaf(4); int* p = n; rt.put_n(p[-1] < 0); rt.put_c(' '); diff --git a/tests/programs/zc0unbounded.zc b/tests/programs/zc0unbounded.zc new file mode 100644 index 0000000..67c3ae0 --- /dev/null +++ b/tests/programs/zc0unbounded.zc @@ -0,0 +1,16 @@ +namespace; +include rt; + +// unbounded in all three places zc0 accepts it (and ignores): the unit, a +// function prefix and a statement. both compilers print the same. +unbounded; +int[4] a; +unbounded int get(int i) { return a[i]; } +int main() { + int i = 2, r = 0; + a[2] = 40; + unbounded r = get(i) + 2; + unbounded { r = r + a[i - 2]; } + rt.put_n(r); rt.put_c(10); + return 0; +} diff --git a/tests/test.sh b/tests/test.sh index a1a5453..253f668 100755 --- a/tests/test.sh +++ b/tests/test.sh @@ -219,10 +219,14 @@ ABC" "$l o3 lifts byte loads and stores" chk "$($vm < tests/programs/o3licm.zc)" "3184200 7950 315 50 260 -56" "$l o3 hoists loop invariants and shares values between blocks" chk "$($vm < tests/programs/o3deep.zc)" "30000" "$l o3 recursion thirty thousand deep" chk "$($vm < tests/programs/o3deep_over.zc 2>&1)" "100000" "$l o3 recursion grows past the original stack" - chk "$($vm < tests/programs/o3_bounds.zc 2>&1 | head -1)" "zy: index 7 out of range (length 5)" "$l o3 bounds check" + chk "$($vm < tests/programs/o3_bounds.zc 2>&1; echo "rc=$?")" "rc=0" "$l o3 implies unbounded: no check on a T[?] index" chk "$($vm < tests/programs/bounds.zc)" "55 55 8" "$l a proved +1 loop skips the bounds check" chk "$($vm < tests/programs/bounds_lo.zc 2>&1 | head -1)" "zy: index -1 out of range (length 4)" "$l a negative loop index is still checked" - chk "$($vm < tests/programs/bounds_hi.zc 2>&1 | head -1)" "zy: index 4 out of range (length 4)" "$l an index that is not the induction variable is still checked" + chk "$($vm < tests/programs/bounds_hi.zc 2>&1; echo "rc=$?")" "rc=0" "$l o3 implies unbounded: an index that is not the induction variable is not checked" + chk "$($vm < tests/programs/boundsrules.zc 2>&1 | head -3)" $'5\n7\nzy: index 5 out of range (length 4)' "$l unbounded as prefix, block and statement, o3 implies it; checked code reports" + chk "$($vm < tests/programs/bounds_fixed.zc 2>&1 | head -3)" $'55\n29\nzy: index 6 out of range (length 6)' "$l a fixed array with a variable index is checked against its length" + chk "$($vm < tests/programs/bounds_heap.zc 2>&1 | head -4)" $'3\n0\nx\nzy: index 11 out of range (length 11)' "$l a pointer to a heap block is checked against its payload" + chk "$($vm < tests/programs/zc0unbounded.zc)" "42" "$l unbounded in the unit, a prefix and a statement" local r; r=$(bash tests/runerr.sh "$vm" tests/errors | tail -1) chk "$r" "rejected: $(ls tests/errors/*.zc | wc -l | tr -d ' ') passed, 0 failed" "$l analyzer rejects every bad program" r=$(bash tests/runerr.sh "$vm" tests/typeerrors | tail -1) @@ -353,7 +357,7 @@ s_runonly() { runonly() { # $1 label, $2 source. the program is already in the image, so it reads no source. # the map is sized to the program: src/tools/automap.sh lays it out for the image's own length local a b d=$T/run-$1 input=$2 - if [ "$1" = gc ]; then input=$T/collector-progress.zc; sed 's/f >= 990/f > 0/' "$2" > "$input"; fi + if [ "$1" = gc ]; then input=$T/collector-progress.zc; sed 's/f >= 950/f > 0/' "$2" > "$input"; fi GENMAP=$T/genmap bash src/tools/automap.sh run $d src/runtime/run.zc "$input" >/dev/null || { chk 0 1 "run $1 builds"; return; } cp src/micro/micro.c src/micro/micro_port.h src/micro/port_linux.c src/micro/port_stub.c src/core/fops.h src/core/bops.h src/core/stack.h src/core/genome.h $d/ $CC -pthread -DZY_THREADS -O2 -w -fwrapv $d/micro.c $d/port_linux.c -o $T/zymr || { chk 0 1 "run $1 links"; return; } @@ -366,6 +370,7 @@ s_runonly() { runonly wide tests/programs/wide.zc runonly selfpatch examples/selfpatch.zc runonly gc tests/programs/gc.zc + runonly zc0unbounded tests/programs/zc0unbounded.zc # zc0 accepts unbounded in all three places and ignores it runonly voidmain tests/programs/void_main.zc runonly trace tests/programs/trace_run.zc # the image carries line tables: a fault and rt.trace() print the same backtrace as the resident compiler's runonly float tests/programs/float.zc -- cgit v1.2.3