diff options
Diffstat (limited to 'src/runtime')
| -rw-r--r-- | src/runtime/rt.zc | 512 | ||||
| -rw-r--r-- | src/runtime/run.zc | 41 |
2 files changed, 316 insertions, 237 deletions
diff --git a/src/runtime/rt.zc b/src/runtime/rt.zc index 3badcc2..ee3594d 100644 --- a/src/runtime/rt.zc +++ b/src/runtime/rt.zc @@ -1,71 +1,77 @@ -// ============================================================================ -// 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. -// ============================================================================ +namespace rt; +include run; + +//: ============================================================================ +//: 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. +//: ============================================================================ + +//: how the runtime is laid out, for a reader coming in cold: +//: +//: memory map generated constants name the regions used by a build. the +//: compiler and runtime use the same names and values. +//: i/o, strings thin wrappers over the cpu's i/o opcodes, plus the two +//: string forms (char* strings and packed byte strings). +//: heap a buddy allocator with a 5 word header on every block. +//: new/free/recycle are built on it. every heap object has at +//: most one owner (the container that holds it), and freeing +//: an owner frees what it owns. +//: growable arrays T[?] handles, built on the heap. +//: mark-sweep a conservative collector. it is the safety net behind +//: free: anything the compiler's ownership analysis could not +//: free gets reclaimed here. +//: memory debug optional checks (use after free, double free, leaks). +//: syscalls file and environment access through one gate word. +//: +//: everything is a 64-bit word, and an address is a word index, not a byte +//: index. the cpu is a stack machine, so "asm { a @ . }" pushes a, fetches the +//: word at that address with @, then outputs it with . (see the vm reference). +//: +//: ---- memory map (words) ---- -// how the runtime is laid out, for a reader coming in cold: -// -// memory map generated constants name the regions used by a build. the -// compiler and runtime use the same names and values. -// i/o, strings thin wrappers over the cpu's i/o opcodes, plus the two -// string forms (word strings and packed byte strings). -// heap a buddy allocator with a 5 word header on every block. -// new/free/recycle are built on it. every heap object has at -// most one owner (the container that holds it), and freeing -// an owner frees what it owns. -// growable arrays []T handles, built on the heap. -// mark-sweep a conservative collector. it is the safety net behind -// free: anything the compiler's ownership analysis could not -// free gets reclaimed here. -// memory debug optional checks (use after free, double free, leaks). -// syscalls file and environment access through one gate word. -// -// everything is a 64-bit word, and an address is a word index, not a byte -// index. the cpu is a stack machine, so "asm { a @ . }" pushes a, fetches the -// word at that address with @, then outputs it with . (see the vm reference). -// -// ---- memory map (words) ---- // src/tools/genmap writes the map values for each build between these markers. // keep the names and order stable so programs can use the same map interface // across targets and image sizes. // @map-rt - -const word MW = 0x1C5000; -const word CODE_END = 0x80000; -const word HEAP_LO = 0x1C5000; -const word HEAP_HI = 0x225000; -const int HEAP_GROW = 0x1; -const word ZFP = 0x90000; -const word GORG = 0x114100; -const word FBOT = 0x164100; -const word FTOP = 0x1A4100; -const word RS0 = 0x1A4100; -const word MARK0 = 0x1B4100; -const int MARKN = 0x8000; -const word DSLO = 0x1BC100; -const word DSHI = 0x1C4FF0; -const int MAGIC = 0x2B7E1516; +const MW = 0x1D5000; +const CODE_END = 0x80000; +const HEAP_LO = 0x1D5000; +const HEAP_HI = 0x235000; +const HEAP_GROW = 0x1; +const ZFP = 0x90000; +const GORG = 0x114100; +const FBOT = 0x174100; +const FTOP = 0x1B4100; +const RS0 = 0x1B4100; +const MARK0 = 0x1C4100; +const MARKN = 0x8000; +const DSLO = 0x1CC100; +const DSHI = 0x1D4FF0; +const MAGIC = 0x2B7E1516; // @end-map -// frames grow in stable segments so pointers to a caller's locals stay valid. +//: frames grow in stable segments so pointers to a caller's locals stay valid. + word frame_floor = FBOT, frame_top = FTOP, frame_node; int frame_chunk = FTOP - FBOT, frame_guard = (FTOP - FBOT) >> 2, frame_busy, gc_active; -[17]word frame_control; +word[17] frame_control; word data_low = DSLO, data_top = DSHI, data_node; word return_low = RS0, return_top = MARK0 - 8, return_node; const int F_STACK = 1024; const int F_INTERNAL = 512; -// ---- virtual enhancements ---- -// install(desc) hands the core a descriptor through the % opcode. the core reads -// it and wires the region it describes into the cpu, so the compiler can replace +//: ---- virtual enhancements ---- + +// install(desc) passes a descriptor to the core through the % opcode. the core +// reads it and installs the region it describes in the cpu, so the compiler can replace // a run of vm code with native code. the descriptor is laid out by the compiler // for each enhance and o3 region (see install in compiler.zc). the enhance lines // below are the micro forms of the same thing: a single machine instruction each. // zdiv, zmod and zshl further down do the same arithmetic in software. this block // comes first, since the compiler resolves / % and << to these names. + // install the descriptor for an optimized region. int install(int desc) { return asm { desc @ % }; } // signed division of a by b, as one machine instruction. @@ -78,9 +84,11 @@ 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"; -// ---- bit operations and float conversions ---- +//: ---- bit operations and float conversions ---- + // these use single machine instructions where the cpu has them. + // the number of leading zero bits in a. enhance clz(a) micro "a = clz a"; // the number of trailing zero bits of a. @@ -106,7 +114,7 @@ enhance zf2s(a) micro "a = f2s a"; // s2f, the software form used where the cpu has none. enhance zs2f(a) micro "a = s2f a"; -// runtime code segments retain the addresses of earlier functions and globals. +//: runtime code segments retain the addresses of earlier functions and globals. word code_blocks; // distinguish a raw function address from a heap closure's environment block. int callable_code(word f) { @@ -116,13 +124,15 @@ int callable_code(word f) { return 0; } -// ---- i/o ---- -// output can be redirected. mode 1 drops what is written and mode 2 appends -// it to a buffer; mode 3 counts characters without storing them (the server -// uses these modes while it checks a document, -// so a parse word that prints can't write into the protocol stream). -// raw_c always reaches the terminal. -int outmode; word outbuf; int outn, outcap; word outgrow; +//: ---- i/o ---- + +//: output can be redirected. mode 1 drops what is written and mode 2 appends +//: it to a buffer; mode 3 counts characters without storing them (the server +//: uses these modes while it checks a document, +//: so a parse word that prints can't write into the protocol stream). +//: raw_c always reaches the terminal. + +int outmode; char* outbuf; int outn, outcap; word outgrow; // write one character to the terminal with no translation. int raw_c(int ch) { asm { ch @ . } return 0; } // write one character. normally it goes to the terminal; while a capture is @@ -156,34 +166,35 @@ int put_s(char* s) { // write the decimal form of a number, with a minus sign for a negative one. // the smallest integer is handled as its own case. int put_n(int n) { - [24]word b; int i = 0; + char[24] b; int i = 0; if (n < 0) { put_c('-'); n = 0 - n; } if (n < 0) { put_s("9223372036854775808"); return 0; } while (1) { b[i++] = '0' + n % 10; n = n / 10; if (!n) break; } while (i) put_c(b[--i]); return 0; } -// the length of a word string, not counting its 0. +// the length of a zero-terminated character string, not counting its 0. int len_w(char* s) { int n = 0; while (s[n]) n++; return n; } -// true when two word strings hold the same characters. +// true when two zero-terminated character strings hold the same characters. int eq_w(char* a, char* b) { int i = 0; while (a[i] && a[i] == b[i]) i++; return a[i] == b[i]; } -// ---- word helpers ---- -// copy and fill by word. copy_w copies forward, so overlapping ranges are only -// safe when dst is below src. a long run above the program area goes to the -// host in one call (ops 18 and 19 of the syscall gate); a host that answers -1 -// (a board, the js vm, a range that overlaps itself) gets the plain loop. +//: ---- word helpers ---- -const int SYS_FILL = 18, /* wowie! */ SYS_COPY = 19; +//: copy and fill by word. copy_w copies forward, so overlapping ranges are only +//: valid when dst is below src. a long run above the program area goes to the +//: host in one call (ops 18 and 19 of the syscall gate); a host that answers -1 +//: (a board, the js vm, a range that overlaps itself) gets the plain loop. + +const int SYS_FILL = 18, SYS_COPY = 19; // copy n words from src to dst. -int copy_w(word* dst, word* src, int n) { +unchecked int copy_w(word*.m dst, word*.m src, int n) { int i = 0; word g = ZFP + 2; if (n >= 16 && dst >= MW) { g[1] = dst; g[2] = src; g[3] = n; g[0] = SYS_COPY; @@ -193,7 +204,7 @@ int copy_w(word* dst, word* src, int n) { return 0; } // set n words at dst to v. -int fill_w(word* dst, int v, int n) { +unchecked int fill_w(word*.m dst, int v, int n) { int i = 0; word g = ZFP + 2; if (n >= 16 && dst >= MW) { g[1] = dst; g[2] = v; g[3] = n; g[0] = SYS_FILL; @@ -210,6 +221,7 @@ int fill_w(word* dst, int v, int n) { // and may cross a word. an access that runs off the end of memory loads 0 and // stores nothing. a byte store never fires the syscall gate; that is a word // store at SYSGATE. opcodes 612..617, words 1224..1234. + int addr_b(int w) { return w << 3; } // the word address of a byte address b. int addr_w(int b) { return b >> 3; } @@ -230,36 +242,42 @@ int st32(int a, int v) { asm { v @ a @ #1234 }; return 0; } // starting at the next word, and a 0 byte after the last character. literals // b"..." live in the code and are not heap objects. cat_s, slice_s, n_to_s and // new_s return a shared heap object with the same layout: many pointers may -// hold it, free does nothing, and the collector reclaims it. word strings +// hold it, free does nothing, and the collector reclaims it. char* strings // (one character per word) are unchanged. -int len_s(word s) { return s[0]; } + +// exposes the length header and packed storage for low-level runtime operations. +word* bstr_storage(bstr s) { return asm { s @ }; } +// forms a packed-string handle from storage with a valid length header. +bstr bstr_handle(word* p) { return asm { p @ }; } +// the number of bytes in a packed byte string. +int len_s(bstr s) { return bstr_storage(s)[0]; } // byte i of a packed byte string. -int at_s(word s, int i) { - if (i < 0 || i >= s[0]) return 0; - return ld8(addr_b(s + 1) + i); +int at_s(bstr s, int i) { + if (i < 0 || i >= len_s(s)) return 0; + return ld8(addr_b(bstr_storage(s) + 1) + i); } -// a new packed byte string of n bytes, owned by the caller. -unchecked word new_s(int n) { - word p = new(1 + ((n + 8) >> 3)); +// a new packed byte string of n bytes, managed by the collector. +bstr new_s(int n) { + word* p = new(1 + ((n + 8) >> 3)); p[0] = n; - return share(p); -} -// store byte v at position i of a word string. -int sput(word s, int i, int v) { st8(addr_b(s + 1) + i, v); return 0; } -// a new string with a followed by b, owned by the caller. -unchecked word cat_s(word a, word b) { - int n = a[0] + b[0]; word p = new_s(n); int i = 0; - while (i < a[0]) { sput(p, i, at_s(a, i)); i++; } + return bstr_handle(share(p)); +} +// store byte v at position i of a packed byte string. +int sput(bstr s, int i, int v) { st8(addr_b(bstr_storage(s) + 1) + i, v); return 0; } +// a new string with a followed by b, managed by the collector. +bstr cat_s(bstr a, bstr b) { + int n = len_s(a) + len_s(b); bstr p = new_s(n); int i = 0; + while (i < len_s(a)) { sput(p, i, at_s(a, i)); i++; } i = 0; - while (i < b[0]) { sput(p, a[0] + i, at_s(b, i)); i++; } + while (i < len_s(b)) { sput(p, len_s(a) + i, at_s(b, i)); i++; } sput(p, n, 0); return p; } -// a new string with the characters from i to j of s, owned by the caller. -unchecked word slice_s(word s, int i, int j) { - int n; word p; int k = 0; +// a new string with the characters from i to j of s, managed by the collector. +bstr slice_s(bstr s, int i, int j) { + int n; bstr p; int k = 0; if (i < 0) i = 0; - if (j > s[0]) j = s[0]; + if (j > len_s(s)) j = len_s(s); if (j < i) j = i; n = j - i; p = new_s(n); @@ -267,36 +285,36 @@ unchecked word slice_s(word s, int i, int j) { sput(p, n, 0); return p; } -// compare two word strings: negative, 0 or positive, like strcmp. -int cmp_s(word a, word b) { - int i = 0, n = a[0], ca, cb; - if (b[0] < n) n = b[0]; +// compare two packed byte strings: negative, 0 or positive, like strcmp. +int cmp_s(bstr a, bstr b) { + int i = 0, n = len_s(a), ca, cb; + if (len_s(b) < n) n = len_s(b); while (i < n) { ca = at_s(a, i); cb = at_s(b, i); if (ca != cb) { if (ca < cb) return 0 - 1; return 1; } i++; } - if (a[0] == b[0]) return 0; - if (a[0] < b[0]) return 0 - 1; + if (len_s(a) == len_s(b)) return 0; + if (len_s(a) < len_s(b)) return 0 - 1; return 1; } -// true when two word strings are equal. -int eq_s(word a, word b) { return cmp_s(a, b) == 0; } -// true when word string a sorts before b. -int lt_s(word a, word b) { return cmp_s(a, b) < 0; } -// true when word string a sorts before b or equals it. -int le_s(word a, word b) { return cmp_s(a, b) <= 0; } +// true when two packed byte strings are equal. +int eq_s(bstr a, bstr b) { return cmp_s(a, b) == 0; } +// true when packed byte string a sorts before b. +int lt_s(bstr a, bstr b) { return cmp_s(a, b) < 0; } +// true when packed byte string a sorts before b or equals it. +int le_s(bstr a, bstr b) { return cmp_s(a, b) <= 0; } // write a packed byte string. -int put_bs(word s) { +int put_bs(bstr s) { int i = 0; - while (i < s[0]) { put_c(at_s(s, i)); i++; } + while (i < len_s(s)) { put_c(at_s(s, i)); i++; } return 0; } // the decimal number at the start of a packed byte string. -int s_to_n(word s) { +int s_to_n(bstr s) { int n = 0, i = 0, sign = 1; word c; - if (s[0] && at_s(s, 0) == '-') { sign = 0 - 1; i = 1; } - while (i < s[0]) { + if (len_s(s) && at_s(s, 0) == '-') { sign = 0 - 1; i = 1; } + while (i < len_s(s)) { c = at_s(s, i); if (c < '0' || c > '9') break; n = n * 10 + c - '0'; @@ -305,8 +323,8 @@ int s_to_n(word s) { return n * sign; } // a new packed byte string holding the decimal form of n. -unchecked word n_to_s(int n) { - [24]word b; int i = 0, j = 0, neg = 0; word p, t; +bstr n_to_s(int n) { + word[24] b; int i = 0, j = 0, neg = 0; bstr p; char* t; if (!n) { p = new_s(1); sput(p, 0, '0'); sput(p, 1, 0); return p; } if (n < 0) { neg = 1; n = 0 - n; } if (n < 0) { @@ -324,8 +342,9 @@ unchecked word n_to_s(int n) { return p; } -// ---- arithmetic the hardware doesn't have ---- -[64]word pow2; +//: ---- arithmetic the hardware doesn't have ---- + +word[64] pow2; int zrem; // unsigned division of a by dv. int zudiv(int n, int dv) { @@ -361,35 +380,43 @@ int zmod(int a, int b) { // a shifted left by b bits, for b under 64. int zshl(int a, int b) { return a * pow2[b & 63]; } -// ---- heap ---- -// a buddy allocator. the heap is cut into aligned power-of-two chunks, every -// block is a power of two words, and a freed block merges with its buddy -// (the other half of the block they were split from) whenever that one is -// 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 -// 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, -// own and release do not follow it, and the sweep still collects it when -// nothing points at it. bits 0..2 keep the meanings above. -// p[-3] p ^ MAGIC p[-2] owner (the container that owns it, or 0) -// p[-1] its type (a type record from new(T), 0 from new(n), -(n + 1) from o3's new_raw) -// free blocks sit on a doubly linked list per class, linked through p[0], p[1]. -// free quarantines: the block stays intact until a sweep finds nothing pointing -// at it. recycle is the fast path for a pointer the program has already -// dropped: it pushes the block onto its size-class list and does not walk the -// heap. a two-word node is still 8 words (the smallest block); a three-word -// node fits in 8 instead of 16. +//: ---- heap ---- + +//: a buddy allocator. the heap is cut into aligned power-of-two chunks, every +//: block is a power of two words, and a freed block merges with its buddy +//: (the other half of the block they were split from) whenever that one is +//: 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 +//: 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, +//: own and release do not follow it, and the sweep still collects it when +//: nothing points at it. bits 0..2 keep the meanings above. +//: p[-3] p ^ MAGIC p[-2] owner (the container that owns it, or 0) +//: p[-1] its type (a type record from new(T), 0 from new(n), -(n + 1) from o3's new_raw) +//: free blocks sit on a doubly linked list per class, linked through p[0], p[1]. +//: free quarantines: the block stays intact until a sweep finds nothing pointing +//: at it. recycle is the fast path for a pointer the program has already +//: dropped: it pushes the block onto its size-class list and does not walk the +//: heap. a two-word node is still 8 words (the smallest block); a three-word +//: node fits in 8 instead of 16. + const int HDR = 5; -const int F_SHARE = 8; // p[-4] bit, orthogonal to live / mark / releasing -const int F_LOW = 65535; // flags live in these bits; the size class is above them -int hbump; [32]word freel; int gc_runs, gc_freed, gc_auto = 1; -int hstop; // block walks and new chunks stop here -int hold_lo, hold_hi; // while nonzero, balloc will not return a block overlapping this range -int hmax, hcut; // words of memory the host has (0: the heap cannot grow); hcut: the heap was cut, so it must not grow -int dbg, alloc_line; // memdebug bits, and the line the compiler stamps before new +//: p[-4] bit, orthogonal to live / mark / releasing. +const int F_SHARE = 8; +//: 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; +//: block walks and new chunks stop here. +int hstop; +//: while nonzero, balloc will not return a block overlapping this range. +int hold_lo, hold_hi; +//: words of memory the host has (0: the heap cannot grow); hcut: the heap was cut, so it must not grow. +int hmax, hcut; +//: memdebug bits, and the line the compiler stamps before new. +int dbg, alloc_line; // the size of the top-level chunk holding heap offset off, within [0, hstop) int topsize(int off) { @@ -462,7 +489,7 @@ int heap_init() { hold_hi = 0; hcut = 0; hmax = 0; - // a map with a growing heap asks the host how much memory there is. a host + // a map with a growing heap queries the host for available memory. a host // that does not answer (-1) or has no more than the initial heap gets a // fixed heap if (HEAP_GROW) { hmax = syscall(9, 0, 0, 0); if (hmax <= HEAP_LO) hmax = 0; } @@ -513,7 +540,7 @@ int heap_uncut(int addr, int k) { // take a block of 2^k words. find the smallest non-empty class at or above k, // unlink its first block and split it down: each half that is not kept goes // back on its own list. a block that overlaps the held range is marked -// "releasing" and dropped from the lists for good (the loop then tries again), +// "releasing" and dropped from the lists permanently (the loop retries), // so the compiler's type area is never handed out as heap. word balloc(int k) { int j; word b; int h, ok; @@ -536,7 +563,8 @@ word balloc(int k) { } return 0; } -// ---- a heap that grows ---- +//: ---- a heap that grows ---- + // the heap is [HEAP_LO, hstop). on a map with HEAP_GROW the memory above // HEAP_HI belongs to the host (a big zeroed array nobody has touched yet), and // when the free lists cannot satisfy a request the heap takes more of it. the @@ -544,6 +572,7 @@ word balloc(int k) { // chunks (topsize) are right: extending hstop re-cuts them, and every new // piece goes through bfree, which merges it with a free buddy below it. a // block that is in use stays where it is, so no pointer moves. + // grow so that a block of 2^k words fits: double the heap, or less when the // host runs out. returns 0 when it cannot. int heap_grow(int k) { @@ -553,7 +582,7 @@ int heap_grow(int k) { need = (h + pow2[k] - 1) / pow2[k] * pow2[k] + pow2[k]; h2 = h + h; if (h2 < need) h2 = need; - if (h2 > room) { // the machine is smaller than the heap wants: the host grows it (syscall 9, 4) + if (h2 > room) { // the machine is smaller than the requested heap: the host grows it (syscall 9, 4) hmax = syscall(9, 4, HEAP_LO + h2, 0); if (hmax <= HEAP_LO) hmax = 0; room = hmax - HEAP_LO; @@ -584,7 +613,8 @@ int hfree() { } return n; } -int fend; // end of the block bfree last made, for the sweep +//: end of the block bfree last made, for the sweep. +int fend; // put block b back, merging it with its buddy as long as it can int bfree(word b) { int k = bclass(b), sz = pow2[k], off; word bud; @@ -617,13 +647,13 @@ int bdrop(word b) { return 0; } // is x the payload address of a block that has been allocated (live or -// quarantined)? the check word p[-3] == p ^ MAGIC is what makes this safe to -// ask about any integer: a random value would have to match by chance. +// quarantined)? the check word p[-3] == p ^ MAGIC validates the pointer before +// checking it against block metadata; a random value would have to match by chance. word isobj(word x) { return x >= HEAP_LO + HDR && x < hbump && x[-3] == (x ^ MAGIC) && (x[-4] & 1); } -// the number of words to skip in p[0..n) before one that could be a pointer -// to a block (see op 20 in core.c); n when none can be. a long payload of -// plain numbers costs one host call instead of an isobj per word. a host that -// does not have the op (-1) is asked once and then never again. +//: the number of words to skip in p[0..n) before one that could be a pointer +//: to a block (see op 20 in core.c); n when none can be. a long payload of +//: plain numbers costs one host call instead of an isobj per word. a host that +//: does not have the op (-1) is asked once and then never again. const int SYS_SCAN = 20; int scan_off; // walk the n words at p and mark every heap object they point to. @@ -650,10 +680,11 @@ int reserve_frames(int words) { } // reserve stack words without invalidating locals or their borrowed addresses. int reserve_data(int words) { return syscall(9, 7, words, 0); } +// grow the return-address stack to hold at least words entries. int reserve_returns(int words) { return syscall(9, 8, words, 0); } // the prologue restores oldfp before calling this helper. its own calls use // the guard space below oldfp; they must not try to grow another segment. -unchecked word frame_grow(int oldfp, int attempted) { +word frame_grow(int oldfp, int attempted) { int size = frame_chunk, slots = oldfp - attempted; word p; frame_busy = 1; if (!hstop || slots < 0 || slots > 0x7FFFFFFF - frame_guard - 4) { @@ -671,7 +702,7 @@ unchecked word frame_grow(int oldfp, int attempted) { } // only the final frame in a segment calls this helper. the helper's own // epilogue still uses that segment; the caller stores the restored pointer. -unchecked word frame_leave() { +word frame_leave() { word p = frame_node; int oldfp = p[0]; frame_busy = 1; frame_floor = p[1]; frame_top = p[2]; frame_node = p[3]; @@ -689,7 +720,7 @@ int oom() { // n words, untyped and not zeroed. the type word keeps -(n + 1), so fatten // can type it later. typed new goes through new_t. o3 new(n) goes through // new_oz, which zeroes the words that were asked for. -unchecked int .u new_raw(int n) { +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; @@ -716,29 +747,30 @@ unchecked int .u new_raw(int n) { } // n words, untyped, zeroed. the type word stays -(n + 1). new_raw does not // zero the words that were asked for, so typed new does not zero them twice. -unchecked int .u new_oz(int n) { +int .u new_oz(int n) { int p = new_raw(n); if (n > 0) fill_w(p, 0, n); return p; } // n words typed t, zeroed. memdebug records the line the compiler stored in alloc_line -unchecked word .u new_t(int n, int t) { +word .u new_t(int n, int t) { word p = new_raw(n); p[-1] = t; fill_w(p, 0, p[-5] - HDR); if (dbg & 1) note_alloc(p, alloc_line); return p; } -unchecked word .u new(int n) { return new_t(n, 0); } +// allocate n words without a type stamp; the caller owns the fresh object. +word .u new(int n) { return new_t(n, 0); } // the compiler works out the size class of a constant-size new at compile // time (k is the class of n + HDR words), so a repeated allocation of the same // shape pays for no class search. when the class list has a block, pop it // directly; a free block already has the right size and an empty payload to // refill. in a loop that frees its object every pass (an m local) this is the -// block that was just recycled, so the pair costs about a dozen steps. +// recycled block, so the pair costs about a dozen steps. // memdebug, an empty list, or a block inside the held range (balloc's rule // for the compiler's type area) fall back to the general path. -unchecked word .u new_k(int n, int t, int k) { +word .u new_k(int n, int t, int k) { word b = freel[k], p, nx; if (!b || dbg || (hold_hi && b < hold_hi && b + pow2[k] > hold_lo)) return new_t(n, t); nx = b[5]; @@ -781,10 +813,10 @@ int release(word p) { b[1] = b[1] & ~7; // quarantined. the check word and the bytes stay; the next sweep reclaims it return 0; } -// frees a heap object: p has to be tagged d, so a call is free(d*p). the object is -// not reused at once. it is kept in quarantine (a stale pointer still reads the old -// contents), and the next collection reclaims it when nothing points at it. a second -// free does nothing. a shared object is left alone. +// releases a heap object and consumes an owned object automatically. an explicit +// d* recast is also accepted; a borrowed reference cannot be consumed. +// storage remains quarantined until collection finds no references to it. +// releasing an already released or shared object has no effect. unchecked int free(.d p) { int n; if (isobj(p) && (p[-4] & F_SHARE)) return 0; @@ -821,7 +853,7 @@ unchecked int recycle(.d p) { bdrop(b); return 0; } -// the matching free for an object the compiler knows has no pointer fields +// the matching free for an object whose type has no pointer fields // (a typed new of a struct of numbers). it checks the type word and the size // class still match what the compiler assumed, since the variable may have been // reassigned; if not, or under memdebug, it takes the general route. @@ -845,9 +877,9 @@ word own(word c, int p) { return c; } // an opt-in bump arena of n words, made as one block. the handle owns that block. -// arena_alloc hands out interior pointers into it and never asks the buddy lists, +// arena_alloc returns interior pointers into it and does not use the buddy lists, // and arena_reset gives all of it back at once. -unchecked word .u arena_new(int n) { +word .u arena_new(int n) { word h = new(3), b; int cap = n; if (cap < 1) cap = 1; b = new(cap); @@ -858,7 +890,7 @@ unchecked word .u arena_new(int n) { } // take n zeroed words from arena a. it returns the address, or 0 when the arena // does not have n words left. -unchecked int arena_alloc(word a, int n) { +int arena_alloc(word a, int n) { int p, at; if (!a || n < 0) return 0; at = a[2]; @@ -877,7 +909,7 @@ int arena_reset(word a) { // publish p. a shared object has no owner: free does nothing to it, copies of its // pointer are ordinary words, and the collector reclaims it once every copy is gone. // returns p. -unchecked word share(word p) { +word share(word p) { if (!isobj(p)) return p; p[-4] = (p[-4] & ~7) | 1 | F_SHARE; p[-2] = 0; @@ -906,24 +938,26 @@ unchecked word triple(int a, int b, int c) { return share(p); } // the first word of a pair made by cons. -unchecked word car(word p) { +word car(word p) { if (dbg & 1) checkptr(p); return p[0]; } // the second word of a pair made by cons. -unchecked word cdr(word p) { +word cdr(word p) { if (dbg & 1) checkptr(p); return p[1]; } // word i (0, 1 or 2) of a triple made by triple. -unchecked word tget(word p, int i) { +word tget(word p, int i) { if (dbg & 1) checkptr(p); return p[i]; } -// ---- growable arrays ---- -// a []T is a handle: [len, cap, items, element size]. items is an object the +//: ---- growable arrays ---- + +// a T[?] is a handle: [len, cap, items, element size]. items is an object the // handle owns; growing swaps it for a bigger one and moves its children over. + unchecked word .u dnew(int es, int n, int t) { word h = new_t(4, t); int c = n; word it; if (c < 4) c = 4; @@ -949,7 +983,7 @@ unchecked int dgrow(word h, int need) { free(old); return 0; } -// the out-of-range report for []T indexing (dat, dpop) +// the out-of-range report for T[?] indexing (dat, dpop) int oob(int i, int n) { put_s("zy: index "); put_n(i); @@ -961,7 +995,7 @@ int oob(int i, int n) { } // element i of a growable array h. indexing with [] does the same, with the bounds // check. the bounds check is what oob reports when i is outside the array. -unchecked word dat(word h, int i) { +word dat(word h, int i) { if (i < 0 || i >= h[0]) oob(i, h[0]); return h[2] + i * h[3]; } @@ -976,28 +1010,40 @@ unchecked int dpush(word h, .d x) { } // remove the last element of a growable array h and give it back. the array // must not be empty. -unchecked word dpop(word h) { +word dpop(word h) { + word value; if (!h[0]) oob(-1, 0); h[0] = h[0] - 1; - return h[2][h[0]]; + value = h[2][h[0]]; h[2][h[0]] = 0; + if (isobj(value) && value[-2] == h[2]) own(value, 0); + return value; } // set the length of a growable array h to n. growing it fills the new elements with // zero, and shrinking it drops the elements past n. -unchecked int dresize(word h, int n) { - int old = h[0] * h[3]; +int dresize(word h, int n) { + int old = h[0] * h[3], end, i; word value; if (n < 0) n = 0; dgrow(h, n); - if (n * h[3] > old) fill_w(h[2] + old, 0, n * h[3] - old); + end = n * h[3]; + if (end > old) fill_w(h[2] + old, 0, end - old); + else { + i = end; + while (i < old) { + value = h[2][i]; h[2][i] = 0; + if (isobj(value) && value[-2] == h[2]) free(value); + i++; + } + } h[0] = n; return 0; } // packed elements (h[3] is minus their size in bytes): the address is a byte address -unchecked word datb(word h, int i) { +word datb(word h, int i) { if (i < 0 || i >= h[0]) oob(i, h[0]); return addr_b(h[2]) + i * (0 - h[3]); } // add the byte x to the end of a growable byte array h. -unchecked int dpushb(word h, int x) { +int dpushb(word h, int x) { int b = 0 - h[3], a; dgrow(h, h[0] + 1); a = addr_b(h[2]) + h[0] * b; @@ -1006,7 +1052,7 @@ unchecked int dpushb(word h, int x) { return 0; } // remove and return the last byte of a growable byte array h. -unchecked int dpopb(word h) { +int dpopb(word h) { int b = 0 - h[3], a; if (!h[0]) oob(-1, 0); h[0] = h[0] - 1; @@ -1016,7 +1062,7 @@ unchecked int dpopb(word h) { return ld32(a); } // growing zeroes the new elements, including the unused tail of the last word -unchecked int dresizeb(word h, int n) { +int dresizeb(word h, int n) { int b = 0 - h[3], a, e, old = (h[0] * b + 7) >> 3, nw; if (n < 0) n = 0; if (n > h[0]) { @@ -1036,15 +1082,17 @@ int dlen(word h) { return h[0]; } // the capacity of a growable array: how many elements it can hold before it grows. int dcap(word h) { return h[1]; } -// ---- mark-sweep ---- -// conservative and non-moving. roots: the program area (globals live -// between functions), the genome's globals, the compiler's input stack, -// the live part of the frame stack and the live part of the data stack. -// opcode 619 pushes that index. a word below it is not a root. +//: ---- mark-sweep ---- + +//: conservative and non-moving. roots: the program area (globals live +//: between functions), the genome's globals, the compiler's input stack, +//: the live part of the frame stack and the live part of the data stack. +//: opcode 619 pushes that index. a word below it is not a root. + int ms_top, ms_over, gc_lo, gc_hi; word ms_buf = MARK0; int markcap = MARKN; // mark work must grow without starting another collection inside this one. -unchecked int reserve_mark(int need) { +int reserve_mark(int need) { int cap = markcap, auto = gc_auto; word p; if (need <= cap) return cap; while (cap < need) cap = cap * 2; @@ -1098,15 +1146,15 @@ int gc_frames() { while (p) { mark(p); markrange(p[0], p[2]); p = p[3]; } return 0; } -// gc_roots is defined in the compiler half (it knows where the compiler's +// gc_roots is defined in the compiler half (it identifies the compiler's // own tables live); it calls markrange over every root range -int gc_roots(); +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() { 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; - gc_roots(); + run.gc_roots(); drain(); while (ms_over) { // the mark stack overflowed: rescan marked objects ms_over = 0; @@ -1162,15 +1210,17 @@ int scrub() { return 0; } -// ---- memory debug ---- -// 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 -// a program asks. sites are p ^ MAGIC so the collector doesn't see them. +//: ---- memory debug ---- + +//: 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 +//: a program requests. sites are p ^ MAGIC so the collector does not treat them as pointers. + const int NSITE = 64; const int POISON = 57005; int site_drop; -[64]word site_p; [64]word site_line; +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. @@ -1248,48 +1298,54 @@ int memreport() { return n; } -// ---- host syscalls ---- -// a store of the op number to SYSGATE runs it. the three words after the gate -// are the arguments, and the store leaves the result in the gate. -// 1 open(path, 0 read | 1 write-create) 2 close(fd) -// 3 read(fd, buf, n) 4 write(fd, buf, n) bytes, one per word -// 5 getenv(name, buf, cap) 6 time() unix seconds -// 21 argc() 22 argv(i, buf, cap) 23 envc() 24 envp(i, buf, cap) -// 40 raw(block) any linux syscall: the block holds the number and six arguments. -// the result is the kernel's, or -errno. see Host.raw in src/lib/std.zc +//: ---- host syscalls ---- + +//: a store of the op number to SYSGATE runs it. the three words after the gate +//: are the arguments, and the store leaves the result in the gate. +//: 1 open(path, 0 read | 1 write-create) 2 close(fd) +//: 3 read(fd, buf, n) 4 write(fd, buf, n) bytes, one per word +//: 5 getenv(name, buf, cap) 6 time() unix seconds +//: 21 argc() 22 argv(i, buf, cap) 23 envc() 24 envp(i, buf, cap) +//: 40 raw(block) any linux syscall: the block holds the number and six arguments. +//: the result is the kernel's, or -errno. see Host.raw in src/lib/std.zc + const int SYSGATE = ZFP + 2; const int SYS_OPEN = 1, SYS_CLOSE = 2, SYS_READ = 3, SYS_WRITE = 4, SYS_GETENV = 5, SYS_TIME = 6; +/* terminates the host process with the exit status supplied in argument a. */ +const int SYS_EXIT = 7; const int SYS_BOPEN = 10, SYS_BREAD = 11, SYS_BWRITE = 12, SYS_BGETENV = 13; const int SYS_RAW = 40; -// the command line and the environment. argv holds the program path, which is -// <eval> when the source came from stdin, so argc is 1 even with no arguments. -// the string ops take an index and copy one entry across, one character per -// word like SYS_GETENV: a zero buffer asks for the length alone, so the caller -// can size the string before it fetches it. src/lib/std.zc builds the arrays. +//: the command line and the environment. argv holds the program path, which is +//: <eval> when the source came from stdin, so argc is 1 even with no arguments. +//: the string ops take an index and copy one entry across, one character per +//: word like SYS_GETENV: a zero buffer requests the length alone, so the caller +//: can size the string before it fetches it. src/lib/std.zc builds the arrays. const int SYS_ARGC = 21, SYS_ARG = 22, SYS_ENVC = 23, SYS_ENV = 24; // byte-string paths. the address is the first byte (addr_b of the word after -// the length), not the string object. word-string syscalls are unchanged. -int bopen(word path, int mode) { return syscall(SYS_BOPEN, addr_b(path + 1), mode, 0); } +// the length), not the string object. char* string syscalls are unchanged. +int bopen(bstr path, int mode) { return syscall(SYS_BOPEN, addr_b(bstr_storage(path) + 1), mode, 0); } // read up to n bytes from fd into the packed byte string s. -int bread(int fd, word s, int n) { return syscall(SYS_BREAD, fd, addr_b(s + 1), n); } +int bread(int fd, bstr s, int n) { return syscall(SYS_BREAD, fd, addr_b(bstr_storage(s) + 1), n); } // write the first n bytes of the packed byte string s to fd. -int bwrite(int fd, word s, int n) { return syscall(SYS_BWRITE, fd, addr_b(s + 1), n); } +int bwrite(int fd, bstr s, int n) { return syscall(SYS_BWRITE, fd, addr_b(bstr_storage(s) + 1), n); } // copy the value of the environment variable name into dst, returning its length. -int bgetenv(word name, word dst, int n) { return syscall(SYS_BGETENV, addr_b(name + 1), addr_b(dst + 1), n); } -// ---- c abi ---- -// ops 14..17 reach native code (see the c abi section of core.c and extern in -// compiler.zc). cfind(name) is 1 if a native symbol resolves (name is a byte -// string), cload(path) opens a library so its symbols resolve, and -// cbmake(entry, sig) is a native function pointer that runs the zc function at -// entry (cfunc(f) in the compiler builds the signature). a native pointer -// from cbmake only works while a native call is in progress, and not on the -// arm64 jit, where it is 0. +int bgetenv(bstr name, bstr dst, int n) { return syscall(SYS_BGETENV, addr_b(bstr_storage(name) + 1), addr_b(bstr_storage(dst) + 1), n); } +//: ---- c abi ---- + +//: ops 14..17 reach native code (see the c abi section of core.c and extern in +//: compiler.zc). cfind(name) is 1 if a native symbol resolves (name is a byte +//: string), cload(path) opens a library so its symbols resolve, and +//: cbmake(entry, sig) is a native function pointer that runs the zc function at +//: entry (cfunc(f) in the compiler builds the signature). a native pointer +//: from cbmake only works while a native call is in progress, and not on the +//: arm64 jit, where it is 0. + const int SYS_CCALL = 14, SYS_CFIND = 15, SYS_CBMAKE = 16, SYS_CLOAD = 17; // the address of the native symbol name in the loaded libraries, or 0 when it is not // loaded. see cload. -int cfind(word name) { return syscall(SYS_CFIND, addr_b(name + 1), 0, 0); } +int cfind(bstr name) { return syscall(SYS_CFIND, addr_b(bstr_storage(name) + 1), 0, 0); } // loads the shared library at path, so the symbols it defines can be found with cfind. -int cload(word path) { return syscall(SYS_CLOAD, addr_b(path + 1), 0, 0); } +int cload(bstr path) { return syscall(SYS_CLOAD, addr_b(bstr_storage(path) + 1), 0, 0); } // makes a native function pointer that runs the vm entry with the signature sig, // so c code can call a zc function through it. int cbmake(int entry, int sig) { return syscall(SYS_CBMAKE, entry, sig, 0); } @@ -1301,9 +1357,9 @@ int syscall(int op, word a, word b, word c) { g[1] = a; g[2] = b; g[3] = c; g[0] = op; return g[0]; } -// the whole file as a fresh string, or 0 if it can't be opened -unchecked word .u readfile(int path) { - int fd; word buf; int n = 0, got, cap; word nb; +// reads a file into an owned character string; returns null if opening fails. +char* .u readfile(char* path) { + int fd; char* buf; int n = 0, got, cap; char* nb; fd = syscall(SYS_OPEN, path, 0, 0); if (fd < 0) return 0; cap = 256; diff --git a/src/runtime/run.zc b/src/runtime/run.zc index 60193a7..a8f82e2 100644 --- a/src/runtime/run.zc +++ b/src/runtime/run.zc @@ -1,27 +1,50 @@ +namespace run; +include rt; + // 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, and compile with zc0 (the program has to stay in -// the stage-0 subset: no types, no quote, no parse words). +// program that defines main. zc0 accepts the bootstrap subset; build.zc uses +// the self-hosted compiler for typed programs and library receiver methods. // // cat build/run/rt.zc src/runtime/run.zc examples/hello.zc | ./zc0 >build/run/genome.h // the program's entry point, written by the program (see start). +namespace; int main(); +namespace run; +include rt; // the collector's roots: the code and globals, the program's frames and the // operand stack. the collector marks from these before it frees anything. int gc_roots() { - markrange(0, CODE_END); - markrange(GORG, GORG[6]); - gc_frames(); - markrange(dsp(), data_top); + rt.markrange(0, rt.CODE_END); + rt.markrange(rt.GORG, rt.GORG[6]); + rt.gc_frames(); + rt.markrange(rt.dsp(), rt.data_top); + return 0; +} + +// install enhancement descriptors from the image's symbol table before any +// runtime arithmetic uses their opcodes. kind 6 is an enhancement record. +int install_enhancements() { + word p = rt.GORG[5], name; + while (*p) { + if (p[0] == 6 && rt.install(p[2] >> 8) < 0) { + rt.put_s("run: cannot install image enhancement\n"); + rt.syscall(rt.SYS_EXIT, 2, 0, 0); + } + name = p + 3; + while (*name) name++; + p = name + 1; + } return 0; } -// the first code a run-only image executes: it sets up the heap, runs main and halts. +// the first code a run-only image executes: initialize the runtime, run main and halt. int start() { - heap_init(); + install_enhancements(); + rt.heap_init(); main(); - halt(); + rt.halt(); return 0; } |