merge work/exactsize: exact-size heap bounds

1 files changed, 19 insertions, 21 deletions

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++;
 			}
 		}