Merge branch 'main' into work/spec

1 files changed, 49 insertions, 9 deletions

diff --git a/src/runtime/rt.zc b/src/runtime/rt.zc
index 7018915..a181387 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.
@@ -1101,6 +1111,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) {
@@ -1316,7 +1347,7 @@ int scrub() {
 
 // dbg bits: 1 header checks and allocation sites, 2 poison the payload on free
 // (the word 57005, which is 0xDEAD), 4 interior pointers keep a quarantined
-// block (the mark walks back at most 64 words to a real header). off unless
+// block (obj_base finds its header from the size classes). off unless
 // a program requests. sites are p ^ MAGIC so the collector does not treat them as pointers.
 
 const int NSITE = 64;
@@ -1325,17 +1356,26 @@ int site_drop;
 word[64] site_p; word[64] site_line;
 // true when p is a freed block still held in quarantine.
 word quar(word p) { return p >= HEAP_LO + HDR && p < hbump && p[-3] == (p ^ MAGIC) && !(p[-4] & 1); }
-// the object whose payload contains w, or 0. exact pointers and interiors.
+// the object whose payload contains w, or 0. exact pointers and interiors, at any
+// depth. every block of class k starts at HEAP_LO plus a multiple of 2^k words, so
+// the block holding w, if any, starts at w rounded down to one of those. the
+// candidates are tried from the largest class down: a header counts only when its
+// check word, size and class agree with k, and the first that holds w in its
+// payload is the block. a merge clears the upper half's header and a split rewrites
+// the header at the same address, so a stale header can only sit inside the
+// payload of the real block, which is found first.
 word obj_base(int w) {
-	int i = 0; word p; int n;
+	int k = 31, off, sz; word b, p;
 	if (w < HEAP_LO + HDR || w >= hbump) return 0;
-	while (i <= 64) {
-		p = w - i;
-		if (p >= HEAP_LO + HDR && p < hbump && p[-3] == (p ^ MAGIC)) {
-			n = p[-5] - HDR;
-			if (w >= p && w < p + n) return p;
+	off = w - HEAP_LO;
+	while (k >= 3) {
+		sz = pow2[k];
+		b = HEAP_LO + off - off % sz;
+		p = b + HDR;
+		if (sz <= hbump - HEAP_LO && p < hbump && b[0] == sz && p[-3] == (p ^ MAGIC) && bclass(b) == k) {
+			if (w >= p && w < b + sz) return p;
 		}
-		i++;
+		k--;
 	}
 	return 0;
 }