destructors: heap(v), drop(v, f) / v.drop(f) / v.drop = f, struct drop methods, collector drops after the sweep (once, resurrection), freed blocks forget their drop, temporaries drop at statement end with a hint, actor send check; o3: no collection inside a region (pending until the outermost exit), no drops set or ended inside o3; spec 3.11.6, 4.10.3-4, 6.15

1 files changed, 193 insertions, 3 deletions

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;