diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/compiler/analyzer.zc | 5 | ||||
| -rw-r--r-- | src/compiler/base.zc | 5 | ||||
| -rw-r--r-- | src/compiler/builtins.zc | 93 | ||||
| -rw-r--r-- | src/compiler/expr.zc | 18 | ||||
| -rw-r--r-- | src/compiler/stmt.zc | 10 | ||||
| -rw-r--r-- | src/runtime/rt.zc | 196 |
6 files changed, 318 insertions, 9 deletions
diff --git a/src/compiler/analyzer.zc b/src/compiler/analyzer.zc index d1f6f3d..34c0a8b 100644 --- a/src/compiler/analyzer.zc +++ b/src/compiler/analyzer.zc @@ -389,6 +389,7 @@ int newloc(int n) { if (if_local) if_local[i] = 0; if (!local_origin_mask) local_origin_mask = chk_resize(0, 0, loccap); local_origin_mask[i] = 0; if (!local_cell) local_cell = chk_resize(0, 0, loccap); local_cell[i] = 0; + if (!local_dropset) local_dropset = chk_resize(0, 0, loccap); local_dropset[i] = 0; if (!local_captured) local_captured = chk_resize(0, 0, loccap); local_captured[i] = 0; if (!local_ended) local_ended = chk_resize(0, 0, loccap); local_ended[i] = 0; if (!local_end_info) local_end_info = chk_resize(0, 0, loccap); local_end_info[i] = 0; @@ -920,6 +921,7 @@ int touch(int i) { // an expression of class c used as a plain value (a lend, an operand). a new // object can't be used that way, since nothing would own it. int plainuse(int c) { + if (c == C_FRESH && drop_tail == here && fchk && infn) { drop_temporary(); return C_PLAIN; } if (c == C_FRESH) cerr("a new object can't be used as a plain value; bind it to a name first"); if (c >= C_VAR) touch(c - C_VAR); return C_PLAIN; @@ -933,6 +935,7 @@ int szclass(int n) { // freeing an owned local. one that holds a typed object with no pointer // fields goes back through recycle_leaf, which knows its class int freevar(int i) { + if (o3on && fchk && ldroppable(i)) cerrn(i, "has drop and can't end inside an o3 region"); if (local_captured && local_captured[i]) { lit(0); laddr(lslot[i]); op(O_ST); return 0; } vaddr(i); op(O_LD); if (lleaf[i] && !o3on && !dry && lookup(s_recycle_leaf) >= 0) { @@ -966,7 +969,7 @@ int exit_vars(int dep, int final) { // block ends. int unused_check(int from) { while (from < nloc) { - if (fchk && lown[from] && !lused[from] && !(lrskind[from] == RS_PARAM && rt.eq_w(lname[from], "_"))) serrn(lname[from], "owned object is never used"); + if (fchk && lown[from] && !lused[from] && !ldroppable(from) && !(lrskind[from] == RS_PARAM && rt.eq_w(lname[from], "_"))) serrn(lname[from], "owned object is never used"); from++; } return 0; diff --git a/src/compiler/base.zc b/src/compiler/base.zc index b326c80..2fcc7f7 100644 --- a/src/compiler/base.zc +++ b/src/compiler/base.zc @@ -255,6 +255,10 @@ int fn_return_type; // a consistent return type inferred from the function body const int EF_READ = 1, EF_WRITE = 2, EF_RETAIN = 4, EF_CONSUME = 8, EF_UNKNOWN = 16, EF_ALIAS = 32, EF_IDENTITY = 64; word effect_symbols, effect_edges, effect_requirements, effect_current; int effect_floor, effect_argument_base; word local_origin, local_origin_mask, local_cell, local_captured, local_ended, local_end_info; word effect_value, argorigin_mask; int capture_enabled; word[1] capture_dummy; +// drops (docs/design/destructors.md): the code position just past a drop form (a fresh +// value with a drop still on the stack there), the type `this` gets in the next closure, +// a local whose drop is set, an actor send whose arguments are checked, and o3 block depth. +int drop_tail = -1, send_check, o3blk; word closure_this, local_dropset; int borrow_pending, borrow_depth, borrow_jump = -1, borrow_entry; word borrow_slots; int argorigin = -1, argtemporary, argowner = -1; word argowner_fact; int stubgen; // 1 while an extern's generated stub is compiled: the stub gets no hints @@ -748,6 +752,7 @@ int reserve_locals(int need) { if (local_origin) local_origin = chk_resize(local_origin, nloc, cap); if (local_origin_mask) local_origin_mask = chk_resize(local_origin_mask, nloc, cap); if (local_cell) local_cell = chk_resize(local_cell, nloc, cap); + if (local_dropset) local_dropset = chk_resize(local_dropset, nloc, cap); if (local_captured) local_captured = chk_resize(local_captured, nloc, cap); if (local_ended) local_ended = chk_resize(local_ended, nloc, cap); if (local_end_info) local_end_info = chk_resize(local_end_info, nloc, cap); diff --git a/src/compiler/builtins.zc b/src/compiler/builtins.zc index 5efe379..8c00636 100644 --- a/src/compiler/builtins.zc +++ b/src/compiler/builtins.zc @@ -838,6 +838,99 @@ int array_member(int c, int n) { if (n == intern("pop")) return array_pop(t); return array_resize(t); } +// ---- drops and heap() (docs/design/destructors.md) ---- + +// a pointer to a struct whose body declares drop: its values drop through the type +int tdroppable(word t) { + word e; + if (!t || !isptr(t)) return 0; + e = t[4]; + return e[0] == TY_STRUCT && e[3] >= 0 && methof(e, intern("drop")) >= 0; +} +// local i holds a value with a drop: one set on it, or one its type declares +int ldroppable(int i) { return (local_dropset && local_dropset[i]) || tdroppable(ltype[i]); } +// entering o3 from normal code: the collector waits until the outermost region is left +int o3_enter_code() { callname(intern("rt.o3_enter")); op(O_DROP); return 0; } +// a fresh value with a drop that nothing holds: it is held in a hidden slot and +// dropped when the full statement ends +int drop_temporary() { + emit_borrow_hold(); + if (hint_begin(tpack(), HINT_SMALL)) { rt.put_s("value with drop is never bound; it drops at the end of this statement"); dg_close(); } + return 0; +} +// the value is on the stack. compile the drop (the next expression, usually fn() { ... } +// with this bound to the value), attach it with rt.set_drop, and leave the value there +// with the class and facts it had. owner is the local that owns the value, or -1. +int drop_attach(word vty, int owner) { + word t = xty, af = xaf, ev = effect_value; int bor = xbor, st = xstr, c; + if (o3on) serr("a drop can't be set inside an o3 region"); + if (owner >= 0 && fchk && local_dropset) { + if (local_dropset[owner]) cerrn(owner, "drop is already set"); + local_dropset[owner] = 1; + } + lit(0); op(O_PICK); + closure_this = vty; c = expr(); rval(); closure_this = 0; + if (c >= C_VAR) touch(c - C_VAR); + callname(intern("rt.set_drop")); op(O_DROP); + xty = t; xaf = af; effect_value = ev; xbor = bor; xstr = st; + lv = 0; lvk = LV_NONE; xzero = 0; xconst = 0; xfloat = 0; + return 0; +} +// drop(v, fn() { ... }): v, with the drop attached +int drop_call() { + int c, prior = 0, i = 0 - 1; + next(); expect(s_lp); + if (tk == T_ID) { peek(); if (pk_tk == T_OP && (pk_tv == s_comma)) { i = findloc(tv); if (i >= 0) prior = ltag[i] & LREAD; } } + c = expr(); rval(); + i = 0 - 1; + if (c >= C_VAR) i = lroot(c - C_VAR); + if (i >= 0 && prior && fchk) cerrn(i, "drop set after the value was used"); + tcneed(isptr(xty) || xty == tword, "drop needs a heap value", xty); + expect(s_comma); + drop_attach(xty, i); + expect(s_rp); + if (c == C_FRESH) drop_tail = here; + return c; +} +// v.drop(fn() { ... }) gives v back; v.drop = fn() { ... }; is a statement +int drop_member(int c, word borrowed) { + int prior = 0, i = 0 - 1, assign = is_op(s_eq); + if (lv && lvk == LV_LOCAL) prior = ltag[lvi] & LREAD; + rval(); + xaf = borrowed; + if (c >= C_VAR) { i = lroot(c - C_VAR); touch(c - C_VAR); } + if (i >= 0 && prior && fchk) cerrn(i, "drop set after the value was used"); + next(); + if (assign && c == C_FRESH && fchk && infn) { drop_temporary(); c = C_PLAIN; } + drop_attach(xty, i); + if (!assign) expect(s_rp); + if (c == C_FRESH) drop_tail = here; + if (assign) { xty = tint; xaf = 0; xbor = 0 - 1; return C_PLAIN; } + return c; +} +// heap(v): v copied into a fresh owned block sized to it +int heap_box() { + int c, place = tpack(), ms; word t; + next(); expect(s_lp); + c = expr(); rval(); plainuse(c); + expect(s_rp); + t = xty; + stamp_site(); + if (isagg(t)) { + lit(tsz(t)); lit(t); callname(intern("rt.heap_copy")); + newsz = tsz(t); xty = tptr(t); + if (t[0] == TY_STRUCT) { ms = methof(t, intern("drop")); if (ms >= 0) { fnref(ms); callname(intern("rt.set_tdrop")); } } + } else if (isptr(t) && t[4][0] == TY_CHAR) { + callname(intern("rt.heap_s")); newsz = -1; xty = t; + } else { + if (xfloat) xfloat = 0; + lit(t); callname(intern("rt.heap_w")); newsz = 1; xty = tptr(t); + } + newleaf = 0; + xaf = af_new(newsz, 2, place); + lv = 0; lvk = LV_NONE; xzero = 0; xconst = 0; xstr = 0; xbor = 0 - 1; effect_value = 0; + return C_FRESH; +} // compile sizeof(T) or sizeof(e): the size of a type or expression in words. int kw_sizeof() { int t; diff --git a/src/compiler/expr.zc b/src/compiler/expr.zc index 8768658..e6acfc8 100644 --- a/src/compiler/expr.zc +++ b/src/compiler/expr.zc @@ -68,6 +68,7 @@ int args(int tags, word ft, int bs, int fat) { freeing = sname[cs] == s_free || sname[cs] == s_recycle; harmless = sname[cs] == s_put_s || rt.eq_w(sname[cs], "rt.put_n") || rt.eq_w(sname[cs], "rt.put_c") || rt.eq_w(sname[cs], "len") || rt.eq_w(sname[cs], "cap"); } + int sending = send_check; send_check = 0; xgive = 0; ifcall = 0 - 1; effect_argument_base = 0; expect(s_lp); if (!is_op(s_rp)) { @@ -76,6 +77,10 @@ int args(int tags, word ft, int bs, int fat) { closure_expected = 0; if (ft && np + parameter_base < ft[3] && is_id(s_fn)) closure_expected = subst(ft[7 + np + parameter_base], bs); place = tpack(); c = expr(); rval(); closure_expected = expected; + if (sending && fchk && ((c >= C_VAR && ldroppable(lroot(c - C_VAR))) || tdroppable(xty) || (c == C_FRESH && drop_tail == here))) { + if (c >= C_VAR) serrn(lname[lroot(c - C_VAR)], "has drop and can't be copied into a message"); else serr("a value with drop can't be copied into a message"); + } + if (freeing && o3on && fchk && c >= C_VAR && ldroppable(lroot(c - C_VAR))) serrn(lname[lroot(c - C_VAR)], "has drop and can't end inside an o3 region"); current = effect_origin(c); current_mask = effect_mask(c); origins = origins | current_mask; effect_args_mask(cs, np + parameter_base, current_mask); if (!np) origin = current; else if (origin != current) origin = -1; tag = (tags >> (np + np)) & 3; @@ -176,6 +181,7 @@ int newtyped() { expect(s_rp); stamp_site(); if (fast) callname(s_new_k); else callname(s_new_t); vf_effect(); + if (t[0] == TY_STRUCT && t[3] >= 0) { int dm = methof(t, intern("drop")); if (dm >= 0) { fnref(dm); callname(intern("rt.set_tdrop")); } } xaf = af_new(length, 2, place); lv = 0; lvk = LV_NONE; xty = tptr(t); xzero = 0; xstamp = 1; return C_FRESH; @@ -462,6 +468,7 @@ int call(int s) { } if (!(sflag[s] & F_DEF) || s == finsym) sflag[s] = sflag[s] | F_EARLY; // called before its body: an owned return is not inferred for it if (sflag[s] & F_EXT) { lit(sval[s][-1]); op(620); } // an extern: the native call opcode, with the block's address + else if (!o3on && (sflag[s] & F_O3)) { o3_enter_code(); fnref(s); op(O_CALL); callname(intern("rt.o3_leave")); op(O_DROP); } // into o3 from normal code: no collection until it returns else { fnref(s); op(O_CALL); } if (!o3on && (sflag[s] & F_O3) && ft) { // non-o3 called o3: fatten the result here, not inside the callee rhs_type = subst(ft[4], bs); @@ -649,14 +656,18 @@ word closure_layout(int closure_index, int count) { int closure() { char* xcf; int np = 0; char*[24] pn; word[24] pty; int hop, entry, i, t, envl, ncap, c, result, declared = 0, tags = 0, tag, lt, lfl = tline; word[24] ptags; - word expected = closure_expected; closure_expected = 0; + word expected = closure_expected, this_type = closure_this; closure_expected = 0; closure_this = 0; reserve_closures(nclo + 1); if (o3on) serr("closures can't be made inside an o3 region"); next(); // fn:type(args) names the result; returns are coerced and checked against it if (accept(s_colon)) declared = ptype0(); expect(s_lp); - if (!is_op(s_rp)) { + if (this_type) { // a drop: fn() { ... } gets the value as this, borrowed + pn[0] = s_this; pty[0] = this_type; ptags[0] = 1; pnoffs[0] = toff; pnplaces[0] = tpack(); np = 1; + if (!is_op(s_rp)) serr("a drop takes no parameters; the value is this"); + } + if (!is_op(s_rp) && !this_type) { while (1) { pty[np] = tword; if (expected && expected[0] == TY_FN && np < expected[3]) pty[np] = expected[7 + np]; @@ -1022,6 +1033,7 @@ int primary() { // wins over a global (a top-level function or constant) of the same name if (mstruct && !ginst) { ms = lookup(methname(mstruct, n)); if (ms >= 0 && (skind[ms] == K_CONST || (skind[ms] == K_FN && (sflag[ms] & F_STATIC)))) s = ms; } if (s < 0 && rt.eq_w(n, "new")) s = source_lookup(s_new); + if (s < 0 && (rt.eq_w(n, "heap") || rt.eq_w(n, "drop"))) { peek(); if (pk_tk == T_OP && pk_tv == s_lp) { if (rt.eq_w(n, "heap")) return heap_box(); return drop_call(); } } if (s >= 0) rs_put(toff, RS_SYM, rs_sym(s), s); if (s >= 0 && skind[s] == K_KW) { if (!(sflag[s] & F_EXPR)) dien(n, "can't be used inside an expression"); @@ -1185,6 +1197,8 @@ word field(int c) { } fieldpos = tpack(); n = name(); fieldoff = nameoff; st = xty; + if (rt.eq_w(n, "drop") && (is_op(s_lp) || is_op(s_eq)) && (isptr(st) || st == tword) && !(isptr(st) && st[4][0] == TY_STRUCT && tfindfield(st[4], n) >= 0)) return drop_member(c, borrowed); + if (rt.eq_w(n, "send") && is_op(s_lp) && isptr(st) && st[4][0] == TY_STRUCT && tfindfield(st[4], intern("__mailbox")) >= 0) send_check = 1; if (st[0] == TY_ARR || st[0] == TY_DYN) { if (pmatch) probe_member(st); if (is_op(s_lp) && array_method(n)) { xaf = borrowed; return array_member(c, n); } diff --git a/src/compiler/stmt.zc b/src/compiler/stmt.zc index 0182728..6d5abe7 100644 --- a/src/compiler/stmt.zc +++ b/src/compiler/stmt.zc @@ -30,7 +30,7 @@ int stmt_inner() { if (tv == s_semi) { next(); return 0; } if (tv == s_lb) { block(); return 0; } } - c = expr(); rval(); op(O_DROP); + c = expr(); rval(); if (c == C_FRESH && drop_tail == here) c = plainuse(c); op(O_DROP); expect(s_semi); discard(c); return 0; @@ -145,7 +145,7 @@ int localdecl(int typed) { if (t && t[0] == TY_DYN && is_op(s_lb)) c = array_dynamic_literal(t); else c = expr(); rval(); nomagic = 0; kc = xconst && !xfloat; if (kc) ltag[i] = ltag[i] | LCONST; - if (c == C_FRESH) { lnsz[i] = newsz; lleaf[i] = newleaf; } + if (c == C_FRESH) { lnsz[i] = newsz; lleaf[i] = newleaf; if (drop_tail == here) local_dropset[i] = 1; } if (t) fcoerce(t); vaddr(i); op(O_ST); @@ -683,6 +683,7 @@ int kw_return() { borrow_cleanup(); defer_run(1, 0); // the value is on the stack; the deferred code is stack neutral exit_vars(1, 0); + if (o3blk) { callname(intern("rt.o3_leave")); op(O_DROP); } // a return leaves the o3 block too epichain = fixnew(here, epichain); lit(rt.MW - 1); op(O_JMP); live = 0; @@ -699,7 +700,9 @@ int kw_o3() { next(); if (!is_op(s_lb)) { o3one = 1; localdecl(1); o3one = 0; return 0; } if (o3on || !infn) return block(); + o3_enter_code(); reserve_code(2); lo = here + 2; lit(lo); op(O_JMP); + o3blk++; o3on = 1; o3reset(); save = nloc; outer = nloc; i = lbase; @@ -713,7 +716,7 @@ int kw_o3() { i++; } block(); - o3on = 0; + o3on = 0; o3blk--; if (no3pend >= o3pendcap) { o3pend = chk_resize(o3pend, no3pend * 67, o3pendcap * 2 * 67); o3pendcap = o3pendcap * 2; } { p = o3pend + no3pend * 67; p[0] = lo; p[1] = here; p[2] = no3sl; @@ -733,6 +736,7 @@ int kw_o3() { } i++; } + callname(intern("rt.o3_leave")); op(O_DROP); return 0; } // unchecked turns the analyzer off for one statement diff --git a/src/runtime/rt.zc b/src/runtime/rt.zc index ad18f85..afff233 100644 --- a/src/runtime/rt.zc +++ b/src/runtime/rt.zc @@ -424,6 +424,11 @@ int zshl(int a, int b) { return a * pow2[b & 63]; } const int HDR = 5; // p[-4] bit, orthogonal to live / mark / releasing. const int F_SHARE = 8; +// p[-4] bits for drops (docs/design/destructors.md): the value has a drop in the side +// table (dtab), its drop has run (it never runs again), and the collector found it +// unreachable and runs its drop once the sweep is over. +const int F_HASDROP = 16, F_DROPPED = 32, F_FINAL = 64; +int o3_depth, gc_pending; // flags live in these bits; the size class is above them. const int F_LOW = 65535; int hbump; word[32] freel; int gc_runs, gc_freed, gc_auto = 1; @@ -822,7 +827,9 @@ int typeof_obj(word p) { 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; + word b = p - HDR; int n, i = 0; word w; + if (b[1] & F_HASDROP) dropnow(p); + n = paylen(p); b[1] = (b[1] & ~7) | 2; // going: not live, and not free yet either, so a child's buddy check can't merge into it while (i < n) { i = i + scan_ptr(p + i, n - i); @@ -830,6 +837,7 @@ int release(word p) { w = p[i]; if (isobj(w) && !(w[-4] & F_SHARE) && w[-2] == p) release(w); i++; } + if (b[1] & F_HASDROP) dclear(p); 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; } @@ -863,6 +871,7 @@ unchecked int recycle(.d p) { } if (!isobj(p) || (p[-4] & F_SHARE)) return 0; b = p - HDR; + if (b[1] & F_HASDROP) dropnow(p); n = paylen(p); b[1] = (b[1] & ~7) | 2; while (i < n) { @@ -871,6 +880,7 @@ unchecked int recycle(.d p) { w = p[i]; if (isobj(w) && !(w[-4] & F_SHARE) && w[-2] == p) recycle(w); i++; } + if (b[1] & F_HASDROP) dclear(p); if (dbg & 2) fill_w(p, 57005, n); bdrop(b); return 0; @@ -892,6 +902,109 @@ unchecked word recycle_leaf(.d p, int t, int k) { freel[k] = b; return 0; } +// ---- drops ---- + +// a value's drop lives in dtab, an open hash keyed by the payload address: +// three words an entry, [key, value drop, type drop]; key 0 is empty, 1 a removed +// entry. the block carries F_HASDROP so the free paths look in the table only then. +// dtab is F_STACK, so the collector keeps it without scanning it: a key in the +// table doesn't keep its value alive. gc marks the drops of live values itself. +word dtab; int dt_cap, dcount, dfill; +int dhash(word p) { return ((p >> 3) ^ (p >> 11)) & (dt_cap - 1); } +// the index of p's entry, or -1 +int dfind(word p) { + int i; + if (!dt_cap) return 0 - 1; + i = dhash(p); + while (dtab[i * 3]) { + if (dtab[i * 3] == p) return i; + i = (i + 1) & (dt_cap - 1); + } + return 0 - 1; +} +// make room for one more entry: rehash into a table twice the size when 3/4 full +int dgrowtab() { + word old = dtab; int oc = dt_cap, i = 0, j, auto = gc_auto; + if ((dfill + 1) * 4 < dt_cap * 3) return 0; + dt_cap = 16; while (dt_cap * 3 <= (dcount + 1) * 8) dt_cap = dt_cap * 2; + gc_auto = 0; dtab = new_oz(dt_cap * 3); gc_auto = auto; + dtab[-4] = dtab[-4] | F_INTERNAL | F_STACK; + dfill = 0; + while (i < oc) { + if (old[i * 3] > 1) { + j = dhash(old[i * 3]); + while (dtab[j * 3]) j = (j + 1) & (dt_cap - 1); + dtab[j * 3] = old[i * 3]; dtab[j * 3 + 1] = old[i * 3 + 1]; dtab[j * 3 + 2] = old[i * 3 + 2]; + dfill++; + } + i++; + } + if (old) recycle(old); + return 0; +} +// the entry for p, made when it has none +int dentry(word p) { + int i = dfind(p); + if (i >= 0) return i; + dgrowtab(); + i = dhash(p); + while (dtab[i * 3] > 1) i = (i + 1) & (dt_cap - 1); + if (!dtab[i * 3]) dfill++; + dtab[i * 3] = p; dtab[i * 3 + 1] = 0; dtab[i * 3 + 2] = 0; + dcount++; + p[-4] = p[-4] | F_HASDROP; + return i; +} +// set the drop of value p to f, and return p. a value has one drop of its own; +// checked code proves that statically, this traps in unchecked code. +word set_drop(word p, word f) { + int i; + if (!isobj(p)) { put_s("zy: drop needs a heap value\n"); trace_at(1); trap(); return p; } + i = dentry(p); + if (dtab[i * 3 + 1] || (p[-4] & F_DROPPED)) { put_s("zy: drop is already set\n"); trace_at(1); trap(); return p; } + dtab[i * 3 + 1] = f + 1; // stored plus one: a function can sit at address 0 + return p; +} +// a value of a type whose struct declares drop: the compiler adds the type's drop at new +word set_tdrop(word p, word f) { + int i; + if (!isobj(p)) return p; + i = dentry(p); + dtab[i * 3 + 2] = f + 1; + return p; +} +// run p's drops, once: the value's own, then its type's. p is still live, so the drop +// sees its fields and children. the entry stays until the block is freed. +int dropnow(word p) { + int i; word f, g; + if (p[-4] & F_DROPPED) return 0; + if (o3_depth) { put_s("zy: a drop can't run inside an o3 region\n"); trace_at(1); trap(); return 0; } + p[-4] = p[-4] | F_DROPPED; + i = dfind(p); + if (i < 0) return 0; + f = dtab[i * 3 + 1]; g = dtab[i * 3 + 2]; + if (f) { f = f - 1; f(p); } + if (g) { g = g - 1; g(p); } + return 0; +} +// p's block is going back: forget its entry and bits, so a reused address has no drop +int dclear(word p) { + int i = dfind(p); + if (i >= 0) { dtab[i * 3] = 1; dtab[i * 3 + 1] = 0; dtab[i * 3 + 2] = 0; dcount--; } + p[-4] = p[-4] & ~(F_HASDROP | F_DROPPED | F_FINAL); + return 0; +} +// a resize copied old into new: the entry moves to new, and freeing old drops nothing +int dmove(word old, word nw) { + int i = dfind(old), j; word f, g; int bits = old[-4] & (F_DROPPED); + if (i < 0) { old[-4] = old[-4] & ~(F_HASDROP | F_DROPPED); return 0; } + f = dtab[i * 3 + 1]; g = dtab[i * 3 + 2]; + dtab[i * 3] = 1; dtab[i * 3 + 1] = 0; dtab[i * 3 + 2] = 0; dcount--; + old[-4] = old[-4] & ~(F_HASDROP | F_DROPPED); + j = dentry(nw); dtab[j * 3 + 1] = f; dtab[j * 3 + 2] = g; + nw[-4] = nw[-4] | bits; + return 0; +} // make p the owner of c, so that freeing p also frees c. it returns c, so the call // composes: h[0] = own(b, h). a shared object has no owner and is left alone. word own(word c, int p) { @@ -1002,6 +1115,7 @@ unchecked int dgrow(word h, int need) { i++; } h[2] = own(it, h); h[1] = c; + if (old[-4] & F_HASDROP) dmove(old, it); free(old); return 0; } @@ -1284,12 +1398,79 @@ int gc_frames() { while (p) { mark(p); markrange(p[0], p[2]); p = p[3]; } return 0; } +// heap(v): a fresh block holding a copy of v. a word, typed t +word .u heap_w(int v, int t) { word p = new_t(1, t); p[0] = v; return p; } +// n words copied from src (a struct or array value), typed t +unchecked word .u heap_copy(word src, int n, int t) { word p = new_t(n, t); copy_w(p, src, n); return p; } +// a zero-terminated character string +unchecked char* .u heap_s(char* s) { int n = len_w(s) + 1; char* p = new(n); copy_w(p, s, n); return p; } +// o3 regions never collect: an allocation that would collect grows the heap instead and +// leaves gc_pending, and leaving the outermost region runs that one collection +int o3_enter() { o3_depth++; return 0; } +int o3_leave() { + if (o3_depth > 0) o3_depth--; + if (!o3_depth && gc_pending) { gc_pending = 0; gc(); } + return 0; +} +// the collector's part, between mark and sweep. the drops of live values are kept; +// an unreachable value with a drop that hasn't run is kept for one more cycle and +// flagged F_FINAL, unless another such value reaches it (its parent drops first and +// it waits for a later collection). nothing runs user code here. +int gc_drops() { + int i, again = 1; word k; + while (again) { + i = 0; + while (i < dt_cap) { + k = dtab[i * 3]; + if (k > 1 && (k[-4] & 7) == 3) { mark(dtab[i * 3 + 1] - 1); mark(dtab[i * 3 + 2] - 1); } + i++; + } + again = ms_top; drain(); + } + // candidates: unmarked live values whose drop is still to run. what they reach is + // marked, so a candidate inside another candidate isn't finalized this time + i = 0; + while (i < dt_cap) { + k = dtab[i * 3]; + if (k > 1 && (k[-4] & 7) == 1 && !(k[-4] & F_DROPPED)) { + k[-4] = k[-4] | F_FINAL; + markrange(k, k + k[-5] - HDR); mark(dtab[i * 3 + 1] - 1); mark(dtab[i * 3 + 2] - 1); + drain(); + } + i++; + } + i = 0; + while (i < dt_cap) { + k = dtab[i * 3]; + if (k > 1 && (k[-4] & F_FINAL)) { + if ((k[-4] & 7) == 1) mark(k); else k[-4] = k[-4] & ~F_FINAL; // reached from another candidate: later + } + i++; + } + drain(); + return 0; +} +// after the sweep: run the drops the collector found. a drop may store its value +// somewhere reachable (it lives on, and its drop never runs again); otherwise a +// later collection frees it. +int gc_finalize() { + int i = 0, found = 1; word k; + while (found) { + found = 0; i = 0; + while (i < dt_cap) { + k = dtab[i * 3]; + if (k > 1 && (k[-4] & F_FINAL)) { k[-4] = k[-4] & ~F_FINAL; dropnow(k); found = 1; } + i++; + } + } + return 0; +} // gc_roots is defined in the compiler half (it identifies the compiler's // own tables live); it calls markrange over every root range int run.gc_roots(); // runs a collection: the blocks nothing points at are reclaimed, quarantined blocks // included, and the number of blocks freed is returned. cycles are reclaimed too. -unchecked int gc() { +unchecked int gc_sweep() { word b = 0; int sz = 0, n = 0; // a leftover pointer here would be a root and pin a block ms_top = 0; ms_over = 0; gc_active = 1; run.gc_roots(); @@ -1303,10 +1484,11 @@ unchecked int gc() { drain(); } } + if (dcount) gc_drops(); b = HEAP_LO; while (b < hstop) { sz = b[0]; - if ((b[1] & 7) == 1) { bfree(b); n++; b = fend; } // unmarked live object, shared or not + if ((b[1] & 7) == 1) { if (b[1] & F_HASDROP) dclear(b + HDR); bfree(b); n++; b = fend; } // unmarked live object, shared or not else if ((b[1] & 7) == 3) { b[1] = (b[1] & ~7) | 1; b = b + sz; } else if ((b[1] & 7) == 4) { b[1] = b[1] & ~7; b = b + sz; } // still pointed at: stays quarantined else if (!(b[1] & 7) && b[2] == ((b + HDR) ^ MAGIC)) { bfree(b); n++; b = fend; } @@ -1317,6 +1499,14 @@ unchecked int gc() { gc_freed = gc_freed + n; return n; } +// a collection, then the drops it found, outside the collector's frame +unchecked int gc() { + int n; + if (o3_depth) { gc_pending = 1; return 0; } + n = gc_sweep(); + if (dcount) gc_finalize(); + return n; +} // the number of live heap objects, for tests and leak checks. int live_objects() { word b = HEAP_LO; int n = 0; |