boot: build the compiler from a pinned wasm seed (seed/zc.wasm, WASI) under wasmtime or node, proven by the fixpoint; seed/MANIFEST hashes; make seed; legacy c bootstrap kept as make genome-c

6 files changed, 286 insertions, 0 deletions

diff --git a/src/boot/boot.sh b/src/boot/boot.sh
new file mode 100755
index 0000000..c7eb2ed
--- /dev/null
+++ b/src/boot/boot.sh
@@ -0,0 +1,50 @@
+#!/bin/sh
+# bootstraps the compiler from the pinned wasm seed. usage: src/boot/boot.sh OUTDIR
+# checks seed/zc.wasm against seed/MANIFEST, then under a wasm runtime (wasmtime, or
+# node) the seed compiles the compiler sources to g1 and g1 compiles them to g2; when
+# they differ g2 compiles them to g3 and g2 = g3 is required (the fixpoint). the result is
+# OUTDIR/genome.bin. the seed is proven by the fixpoint, not trusted. nothing here
+# uses the c core.
+set -e
+cd "$(dirname "$0")/../.."
+OUT=${1:?outdir}; SEED=${SEED:-seed/zc.wasm}; MAN=${MAN:-seed/MANIFEST}
+mkdir -p "$OUT"
+sha() { if command -v sha256sum >/dev/null 2>&1; then sha256sum "$1" | cut -d' ' -f1; else shasum -a 256 "$1" | cut -d' ' -f1; fi; }
+want=$(sed -n 's/^seed-sha256 //p' "$MAN"); got=$(sha "$SEED")
+if [ -z "$BOOT_NOCHECK" ] && [ "$want" != "$got" ]; then
+	echo "boot: $SEED does not match $MAN" >&2
+	echo "boot:   manifest sha256 $want" >&2
+	echo "boot:   file     sha256 $got" >&2
+	echo "boot: the seed was changed or damaged; restore it from git, or run make seed to rebuild it on purpose" >&2
+	exit 1
+fi
+if [ -n "$WASM_RUNTIME" ]; then RT=$WASM_RUNTIME
+elif command -v wasmtime >/dev/null 2>&1; then RT=wasmtime
+elif command -v node >/dev/null 2>&1 && node -e 'process.exit(+process.versions.node.split(".")[0] < 18 ? 1 : 0)' 2>/dev/null; then RT=node
+else
+	echo "boot: no WebAssembly runtime found. the compiler is built from seed/zc.wasm under one of:" >&2
+	echo "boot:   node 18 or later   (macOS: brew install node;     debian/ubuntu: apt install nodejs)" >&2
+	echo "boot:   wasmtime           (macOS: brew install wasmtime; elsewhere: curl https://wasmtime.dev/install.sh -sSf | bash)" >&2
+	exit 1
+fi
+run() { case "$RT" in node) node src/boot/run.mjs "$1" ;; wasmtime) wasmtime run --dir=. "$1" ;; *) $RT "$1" ;; esac; }
+le64() { n=$1 i=0; while [ $i -lt 8 ]; do printf "\\$(printf %03o $(( (n >> (8 * i)) & 255 )))"; i=$((i + 1)); done; }
+SRC="src/runtime/rt.zc src/core/core.zc $(sed 's#^#src/compiler/#' src/compiler/parts | tr '\n' ' ')"
+input() { cat src/tools/build.zc; printf '`'; cat $SRC; }
+stage() { # stage IMAGE OUT: IMAGE empty means the seed's own genome
+	{ if [ -n "$1" ]; then printf 'ZCIMAGE\n'; le64 $(wc -c < "$1"); cat "$1"; fi; input; } | run "$SEED" > "$2.tmp"
+	mv "$2.tmp" "$2"
+}
+echo "boot: seed $got ok, runtime $RT"
+stage "" "$OUT/g1.bin"; echo "boot: g1 (seed -> sources): $(sha "$OUT/g1.bin")"
+[ "${BOOT_STAGES:-}" = 1 ] && exit 0
+img=$(sed -n 's/^image-sha256 //p' "$MAN")
+[ -n "$img" ] && { [ "$img" = "$(sha "$OUT/g1.bin")" ] && echo "boot: g1 is the image the manifest records" || echo "boot: g1 differs from the manifest's image (the sources changed since the seed was made)"; }
+stage "$OUT/g1.bin" "$OUT/g2.bin"; echo "boot: g2 (g1 -> sources): $(sha "$OUT/g2.bin")"
+if cmp -s "$OUT/g1.bin" "$OUT/g2.bin"; then
+	# g1 rebuilt itself unchanged, so it is the fixpoint: a third stage would only repeat it
+	cp "$OUT/g2.bin" "$OUT/genome.bin"; echo "boot: fixpoint (g1 = g2)"; exit 0
+fi
+stage "$OUT/g2.bin" "$OUT/g3.bin"; echo "boot: g3 (g2 -> sources): $(sha "$OUT/g3.bin")"
+cmp "$OUT/g2.bin" "$OUT/g3.bin" || { echo "boot: no fixpoint: g2 and g3 differ" >&2; exit 1; }
+cp "$OUT/g2.bin" "$OUT/genome.bin"; echo "boot: fixpoint (g2 = g3)"
diff --git a/src/boot/mkseed.sh b/src/boot/mkseed.sh
new file mode 100755
index 0000000..297a853
--- /dev/null
+++ b/src/boot/mkseed.sh
@@ -0,0 +1,44 @@
+#!/bin/sh
+# builds the bootstrap seed: the microcore with a compiler genome inside, as a WASI
+# module, sized down (-Oz, lto, gc-sections, no debug info or names, then wasm-opt -Oz
+# when it is on PATH).
+#   src/boot/mkseed.sh GENOME_DIR OUT.wasm               build only
+#   src/boot/mkseed.sh --manifest GENOME_DIR OUT.wasm    build, prove, write MANIFEST beside OUT
+# with --manifest the unoptimized and the optimized module must both compile the
+# compiler sources to the same image, and the optimized one must reach the fixpoint
+# from it; the manifest records both hashes and sizes.
+# needs clang with the wasm32 target and wasm-ld.
+set -e
+cd "$(dirname "$0")/../.."
+MANIFEST=; [ "$1" = --manifest ] && { MANIFEST=1; shift; }
+G=${1:?genome dir}; OUT=${2:?out}
+CC=${WASM_CC:-$(sh src/tools/findcc.sh --wasm)}
+sha() { if command -v sha256sum >/dev/null 2>&1; then sha256sum "$1" | cut -d' ' -f1; else shasum -a 256 "$1" | cut -d' ' -f1; fi; }
+"$CC" --target=wasm32 -Oz -flto -w -fwrapv -nostdlib -fno-builtin -mbulk-memory -DJTYPE=int -DMICRO_PORT_IMAGE \
+	-ffunction-sections -fdata-sections -g0 \
+	-Isrc/core -Ibuild/core/map --embed-dir="$G" -Isrc/micro src/micro/micro.c src/boot/port_wasi.c \
+	-Wl,--gc-sections -Wl,--strip-all -Wl,--initial-memory=134217728 -Wl,-z,stack-size=1048576 -o "$OUT.raw"
+OPT=none
+if command -v wasm-opt >/dev/null 2>&1; then
+	wasm-opt -Oz --strip-debug --strip-producers --enable-bulk-memory "$OUT.raw" -o "$OUT.tmp"; OPT="$(wasm-opt --version)"
+else cp "$OUT.raw" "$OUT.tmp"; echo "mkseed: no wasm-opt on PATH; the seed is not run through it" >&2; fi
+mv "$OUT.tmp" "$OUT"
+if [ -n "$MANIFEST" ]; then
+	M=$(dirname "$OUT")/MANIFEST; T=$(mktemp -d)
+	printf 'seed-sha256 %s\n' "$(sha "$OUT")" > "$M"
+	SEED="$OUT" MAN="$M" sh src/boot/boot.sh "$T"
+	SEED="$OUT.raw" MAN=/dev/null BOOT_NOCHECK=1 BOOT_STAGES=1 sh src/boot/boot.sh "$T/raw"
+	cmp "$T/g1.bin" "$T/raw/g1.bin" || { echo "mkseed: the size-optimized seed compiles differently from the unoptimized one" >&2; exit 1; }
+	{
+		echo "# the pinned bootstrap seed. make checks seed-sha256 before it runs the seed."
+		echo "# regenerate with: make seed"
+		printf 'seed-sha256 %s\n' "$(sha "$OUT")"
+		printf 'seed-size %s\n' "$(wc -c < "$OUT" | tr -d ' ')"
+		printf 'seed-size-unoptimized %s\n' "$(wc -c < "$OUT.raw" | tr -d ' ')"
+		printf 'wasm-opt %s\n' "$OPT"
+		printf 'image-sha256 %s\n' "$(sha "$T/genome.bin")"
+		printf 'image-size %s\n' "$(wc -c < "$T/genome.bin" | tr -d ' ')"
+	} > "$M"
+	rm -rf "$T"; cat "$M"
+fi
+rm -f "$OUT.raw"
diff --git a/src/boot/port_wasi.c b/src/boot/port_wasi.c
new file mode 100644
index 0000000..ba8da8c
--- /dev/null
+++ b/src/boot/port_wasi.c
@@ -0,0 +1,136 @@
+/* WASI port of the microcore, for the bootstrap seed (seed/zc.wasm). reads the
+   whole of stdin, runs the genome inside, writes stdout. needs no libc: the only
+   imports are wasi_snapshot_preview1 fd_read, fd_write and proc_exit, so the same
+   module runs under node (src/boot/run.mjs) and wasmtime. build with
+   src/boot/mkseed.sh. */
+#include "micro_port.h"
+
+#define IMPORT(n) __attribute__((import_module("wasi_snapshot_preview1"), import_name(n)))
+typedef struct { void *buf; unsigned long len; } Iov;
+IMPORT("fd_read") int wasi_fd_read(int fd, Iov *iov, int n, unsigned long *got);
+IMPORT("fd_write") int wasi_fd_write(int fd, Iov *iov, int n, unsigned long *put);
+IMPORT("path_open") int wasi_path_open(int dir, int dirflags, const char *path, unsigned long len, int oflags, unsigned long long rights, unsigned long long inherit, int fdflags, int *fd);
+IMPORT("fd_close") int wasi_fd_close(int fd);
+IMPORT("proc_exit") _Noreturn void wasi_proc_exit(int code);
+
+static unsigned char ibuf[65536], obuf[65536];
+static int in_n, in_p, in_end, on;
+
+static void fill(void)
+{
+	Iov v = { ibuf, sizeof ibuf }; unsigned long got = 0;
+	in_p = 0; in_n = 0;
+	if (in_end) return;
+	if (wasi_fd_read(0, &v, 1, &got) || got == 0) { in_end = 1; return; }
+	in_n = (int)got;
+}
+static void flush_fd(int fd, unsigned char *b, int n)
+{
+	while (n > 0) {
+		Iov v = { b, (unsigned long)n }; unsigned long put = 0;
+		if (wasi_fd_write(fd, &v, 1, &put) || put == 0) return;
+		b += put; n -= (int)put;
+	}
+}
+
+static unsigned char *mbase;
+static UCell mcap;
+Cell *micro_mem_alloc(UCell words)
+{
+	UCell need, pages;
+	if (words > ((UCell)-1) / sizeof(Cell)) return 0;
+	if (!mbase) mbase = (unsigned char *)((UCell)__builtin_wasm_memory_size(0) * 65536u);
+	need = words * sizeof(Cell);
+	if (need <= mcap) return (Cell *)mbase;
+	pages = (need - mcap + 65535u) / 65536u;
+	/* grow in large steps: some node releases crash in a gc that many small grows provoke; the module
+	   starts with 128 MB, more than a compiler build needs, so a build never grows */
+	if (pages < 1024) pages = 1024;
+	if (__builtin_wasm_memory_grow(0, (int)pages) < 0) return 0;
+	mcap += pages * 65536u;
+	return (Cell *)mbase;
+}
+
+int micro_eof(void) { if (in_p >= in_n) fill(); return in_p >= in_n; }
+int micro_getc(void) { return micro_eof() ? -1 : ibuf[in_p++]; }
+void micro_putc(int c) { if (on == sizeof obuf) { flush_fd(1, obuf, on); on = 0; } obuf[on++] = (unsigned char)c; }
+void micro_msg(const char *s) { int n = 0; while (s[n]) n++; flush_fd(2, (unsigned char *)s, n); }
+
+Cell micro_syscall(Cell *mem, Cell op, Cell a, Cell b, Cell c)
+{
+	switch (op) {
+	case 9:
+		if (a == 0) return micro_mem_words();
+		if (a == 1) return HEAP_LO;
+		if (a == 2) return HEAP_HI;
+		if (a == 3) return (Cell)micro_mem_words() * 8;
+		return -1;
+	case 1: {	/* open for reading, relative to the directory preopened as fd 3 (embed reads the library this way) */
+		char path[1024]; int n = 0, fd = -1;
+		if (b != 0) return -1;
+		while (n < 1023 && a + n < (Cell)micro_mem_words() && mem[a + n]) { path[n] = (char)mem[a + n]; n++; }
+		path[n] = 0;
+		if (wasi_path_open(3, 1, path, (unsigned long)n, 0, 2 /* fd_read */, 0, 0, &fd)) return -1;
+		return fd;
+	}
+	case 2: return a > 2 ? (wasi_fd_close((int)a) ? -1 : 0) : -1;
+	case 3: {
+		unsigned char t[512]; Cell n = 0; int i;
+		if (c < 0 || b < 0 || b + c > (Cell)micro_mem_words()) return -1;
+		while (n < c) {
+			Iov v = { t, (unsigned long)(c - n > 512 ? 512 : c - n) }; unsigned long got = 0;
+			if (a == 0) { while (n < c && !micro_eof()) mem[b + n++] = micro_getc(); break; }
+			if (wasi_fd_read((int)a, &v, 1, &got) || got == 0) break;
+			for (i = 0; i < (int)got; i++) mem[b + n + i] = t[i];
+			n += (Cell)got;
+		}
+		return n;
+	}
+	case 4: {
+		unsigned char t[512]; Cell n = 0; int i, k;
+		if (c < 0 || b < 0 || b + c > (Cell)micro_mem_words() || (a != 1 && a != 2)) return -1;
+		if (a == 1) { flush_fd(1, obuf, on); on = 0; }
+		while (n < c) { k = c - n > 512 ? 512 : (int)(c - n); for (i = 0; i < k; i++) t[i] = (unsigned char)mem[b + n + i]; flush_fd((int)a, t, k); n += k; }
+		return n;
+	}
+	case 21: return 1;
+	case 23: return 0;
+	}
+	return -1;
+}
+
+void __multi3(unsigned long long *r, unsigned long long al, unsigned long long ah, unsigned long long bl, unsigned long long bh)
+{
+	unsigned long long a0 = al & 0xffffffffu, a1 = al >> 32, b0 = bl & 0xffffffffu, b1 = bl >> 32;
+	unsigned long long p00 = a0 * b0, p01 = a0 * b1, p10 = a1 * b0, p11 = a1 * b1;
+	unsigned long long mid = (p00 >> 32) + (p01 & 0xffffffffu) + (p10 & 0xffffffffu);
+	r[0] = (p00 & 0xffffffffu) | (mid << 32);
+	r[1] = p11 + (p01 >> 32) + (p10 >> 32) + (mid >> 32) + al * bh + ah * bl;
+}
+
+/* an input that starts with "ZCIMAGE\n" and a little-endian 64-bit byte count carries
+   the image to boot ahead of the program: the bootstrap uses it to run each stage's
+   compiler in this same module. any other input boots the embedded seed genome. */
+int micro_port_image(Cell *mem, UCell org, UCell end)
+{
+	static const char tag[] = "ZCIMAGE\n";
+	UCell n = 0, i, w; int k;
+	if (micro_eof() || in_n - in_p < 16) return 0;
+	for (k = 0; k < 8; k++) if (ibuf[in_p + k] != (unsigned char)tag[k]) return 0;
+	in_p += 8;
+	for (k = 0; k < 8; k++) n |= (UCell)micro_getc() << (8 * k);
+	if (n % 8 || org + n / 8 > end) return -1;
+	for (i = 0; i < n / 8; i++) {
+		w = 0;
+		for (k = 0; k < 8; k++) { int c = micro_getc(); if (c < 0) return -1; w |= (UCell)c << (8 * k); }
+		mem[org + i] = (Cell)w;
+	}
+	return 1;
+}
+
+void _start(void)
+{
+	int r = micro_run();
+	flush_fd(1, obuf, on); on = 0;
+	if (r) wasi_proc_exit(r);
+}
diff --git a/src/boot/run.mjs b/src/boot/run.mjs
new file mode 100644
index 0000000..f96c3f4
--- /dev/null
+++ b/src/boot/run.mjs
@@ -0,0 +1,46 @@
+// runs the bootstrap seed (a WASI preview1 module) under node: stdin in, stdout out,
+// exit code back. usage: node src/boot/run.mjs MODULE.wasm < in > out
+// the seed imports only fd_read, fd_write, path_open (read-only, relative to the
+// current directory, preopened as fd 3), fd_close and proc_exit, so they are here
+// directly, without node:wasi.
+import { readFileSync, readSync, writeSync, openSync, closeSync } from 'node:fs';
+const EXIT = Symbol('exit');
+let mem;
+const u8 = () => new Uint8Array(mem.buffer), dv = () => new DataView(mem.buffer);
+const fds = new Map([[0, 0], [1, 1], [2, 2]]);
+let nextFd = 4;
+function iovs(p, n, f) {
+	let total = 0;
+	for (let i = 0; i < n; i++) {
+		const b = dv().getUint32(p + 8 * i, true), l = dv().getUint32(p + 8 * i + 4, true);
+		const k = f(b, l); total += k; if (k < l) break;
+	}
+	return total;
+}
+const wasi = {
+	fd_read(fd, p, n, out) {
+		if (!fds.has(fd)) return 8;
+		let k;
+		try { k = iovs(p, n, (b, l) => { try { return readSync(fds.get(fd), u8(), b, l, null); } catch (e) { if (e.code === 'EAGAIN') return 0; if (e.code === 'EOF') return 0; throw e; } }); }
+		catch (e) { return 29; }
+		dv().setUint32(out, k, true); return 0;
+	},
+	fd_write(fd, p, n, out) {
+		if (!fds.has(fd)) return 8;
+		const k = iovs(p, n, (b, l) => { let d = 0; while (d < l) d += writeSync(fds.get(fd), u8(), b + d, l - d); return l; });
+		dv().setUint32(out, k, true); return 0;
+	},
+	path_open(dir, dirflags, path, len, oflags, rights, inherit, fdflags, out) {
+		if (dir !== 3 || oflags !== 0) return 76;
+		const name = Buffer.from(u8().subarray(path, path + len)).toString();
+		if (name.startsWith('/') || name.split('/').includes('..')) return 76;
+		let h; try { h = openSync(name, 'r'); } catch (e) { return 44; }
+		const fd = nextFd++; fds.set(fd, h); dv().setUint32(out, fd, true); return 0;
+	},
+	fd_close(fd) { if (fd < 3 || !fds.has(fd)) return 8; closeSync(fds.get(fd)); fds.delete(fd); return 0; },
+	proc_exit(code) { throw { [EXIT]: code }; },
+};
+const { instance } = await WebAssembly.instantiate(readFileSync(process.argv[2]), { wasi_snapshot_preview1: wasi });
+mem = instance.exports.memory;
+try { instance.exports._start(); process.exitCode = 0; }
+catch (e) { if (e && EXIT in e) process.exitCode = e[EXIT]; else throw e; }
diff --git a/src/micro/micro.c b/src/micro/micro.c
index 23994dd..39a22b2 100644
--- a/src/micro/micro.c
+++ b/src/micro/micro.c
@@ -776,6 +776,13 @@ int micro_run(void)
 		micro_msg("zy: genome does not fit\n");
 		return 1;
 	}
+#ifdef MICRO_PORT_IMAGE
+	/* the port may hand over an image of its own in place of the embedded one
+	   (the wasm bootstrap seed does, to run a freshly built compiler) */
+	i = micro_port_image(m, (UCell)GORG, (UCell)FBOT);
+	if (i < 0) { micro_msg("zy: bad image\n"); return 1; }
+	if (i == 0)
+#endif
 	for (i = 0; i < GLEN; i++) m[GORG + i] = genome_word(i);
 	jknown = 0;
 	return run(GORG);
diff --git a/src/micro/micro_port.h b/src/micro/micro_port.h
index 9f77987..1653250 100644
--- a/src/micro/micro_port.h
+++ b/src/micro/micro_port.h
@@ -56,6 +56,9 @@ int micro_eof(void);
 #define MICRO_WAIT (-2)
 #define MICRO_SUSPENDED 3
 int micro_run(void);
+/* with MICRO_PORT_IMAGE defined, the port's micro_port_image(mem, org, end) may load an
+   image of its own at mem[org..end): 1 when it did, 0 to use the embedded genome, -1 on error. */
+int micro_port_image(Cell *mem, UCell org, UCell end);
 int micro_resume(void);
 
 /* write the low 8 bits. */