src/kernel/alloc.nsc

/*
 * colosseums: nested arena allocator with kernel-driven lazy reclaim.
 * see docs/superpowers/specs/2026-09-30-colosseums-design.md for the
 * full design; this comment covers only what a reader of this file
 * itself needs.
 *
 * one recursive struct, arena, used at every level: the whole heap
 * (heap_colosseum), a subsystem's own carved-out region (fs_colosseum),
 * and every nested arena beneath either of those - "colosseum" names
 * only the root-level instance, a naming convention, not a distinct
 * type. an arena with child_count == 0 is a plain bump allocator,
 * unchanged from before this file existed. an arena with
 * child_count > 0 (a "vector") additionally owns child_count further
 * struct arenas, each child_size bytes of its own bump-allocatable
 * space - both the child bookkeeping array and the child data region
 * are carved out of the parent via the same arena_alloc everything
 * else uses.
 *
 * reclaim is real but deliberately coarse: mark a child "done" when
 * its owner is finished with it (arena_mark_done), and the next
 * request for a slot in that same vector (arena_child) sweeps for
 * anything done, wipes it back to fresh, and hands it out again -
 * only once every never-touched slot is already spoken for. no real
 * free(), no compaction/moving, no background sweep task or registry
 * of colosseums: the sweep is entirely local to arena_child, scoped to
 * the one vector being asked for a slot, at the exact moment its fast
 * path fails.
 */
 
include "klog.nsh";
 
void halt(void);
 
struct arena
{
	u64 start;
	u64 current;
	u64 limit;
	/* issued/done together track a child slot's real lifecycle --
	 * current==start alone can't distinguish "never handed out" from
	 * "handed out and in active use" for a child that's used as a
	 * flat buffer rather than sub-allocated from (fd.nsc's own file-
	 * cache slots: the caller never calls arena_alloc on what
	 * arena_child gives it, so current would stay == start the whole
	 * time it's genuinely in use -- confirmed by tracing fd.nsc's own
	 * real usage before trusting the simpler-looking check). */
	u64 issued;       /* 0 never handed out by arena_child, 1 has been */
	u64 done;         /* 0 in use (or not yet issued), 1 marked done --
	                   * available for reuse regardless of `issued` */
	u64 child_size;   /* 0 if this arena has no children (a leaf) */
	u64 child_count;  /* 0 if no children */
	ptr children;     /* -> child_count structs, 0 if no children */
};
 
global struct arena heap_colosseum;
global struct arena fs_colosseum;
 
/* exec.nsc's single, permanent file-read buffer -- not a vector, see
 * the design doc's own reasoning: a shebang chain already re-execs
 * safely through one shared buffer today (the outer call never
 * touches its content again once it recurses), so this only needs a
 * fixed size chosen once, not reclaim machinery. */
global ptr exec_filebuf;
 
/* fd.nsc's 5 file-cache slots, one real vector instead of 5
 * hand-duplicated globals. */
global ptr fd_cache_vec;
 
void
arena_init(ptr a, u64 start, u64 size)
{
	a->start = start;
	a->current = start;
	a->limit = start + size;
	a->issued = (u64)0;
	a->done = (u64)0;
	a->child_size = (u64)0;
	a->child_count = (u64)0;
	a->children = (ptr)0;
}
 
global ptr
arena_alloc(ptr a, u64 size)
{
	ptr p;
	u64 aligned;
 
	/* round up to 16 bytes -- keeps every allocation safely aligned
	 * for anything this kernel stores, including the 8-byte *ptr
	 * stores everything from vga to idt relies on. */
	aligned = (size + (u64)15) & ~(u64)15;
 
	if(a->current + aligned > a->limit)
	{
		return (ptr)0;
	}
 
	p = (ptr)a->current;
	a->current = a->current + aligned;
	return p;
}
 
/* carves a child arena's storage out of the parent's remaining space
 * and initializes it -- for a single, plain (non-vector) child, same
 * shape tape-kernel's own "anew()" used. returns 0 if the parent
 * didn't have SIZE bytes left (arena_alloc's own clean-failure
 * sentinel, base==(ptr)0) and leaves child untouched in that case --
 * without this check, child would silently become a "valid" arena
 * based at physical address 0 (start==current==0), handing out real
 * pointers into low memory (the real-mode ivt/bios data area) instead
 * of failing the way every other arena_alloc caller in this kernel
 * does. returns 1 on success. */
i32
arena_carve(ptr parent, ptr child, u64 size)
{
	ptr base;
 
	base = arena_alloc(parent, size);
	if(base == (ptr)0)
	{
		return 0;
	}
	arena_init(child, (u64)base, size);
	return 1;
}
 
/* turns SIZE bytes of PARENT into COUNT fixed-size child arenas,
 * each CHILD_SIZE bytes -- the vector container itself is also
 * carved from parent (so a vector is nothing but another arena,
 * matching the one-recursive-type design), and its own start/
 * current/limit are left at 0/0/0: nothing ever bump-allocates from
 * a vector node directly, only arena_child ever hands out its
 * children. returns 0 if parent can't fit the bookkeeping array, the
 * data region, or the vector node itself -- same clean-failure
 * contract as arena_alloc. */
global ptr
arena_vector(ptr parent, u64 child_size, u64 child_count)
{
	ptr v;
	ptr childstructs;
	ptr childdata;
	u64 i;
	ptr c;
 
	v = arena_alloc(parent, (u64)sizeof(struct arena));
	if(v == (ptr)0)
	{
		return (ptr)0;
	}
	childstructs = arena_alloc(parent, child_count * (u64)sizeof(struct arena));
	if(childstructs == (ptr)0)
	{
		return (ptr)0;
	}
	childdata = arena_alloc(parent, child_count * child_size);
	if(childdata == (ptr)0)
	{
		return (ptr)0;
	}
 
	i = (u64)0;
	while(i < child_count)
	{
		c = (ptr)((u64)childstructs + i * (u64)sizeof(struct arena));
		arena_init(c, (u64)childdata + i * child_size, child_size);
		i = i + (u64)1;
	}
 
	arena_init(v, (u64)0, (u64)0);
	v->child_size = child_size;
	v->child_count = child_count;
	v->children = childstructs;
	return v;
}
 
/* hands out one child slot from VECTOR: the first one that's either
 * never been issued at all (issued == 0) or was issued once and has
 * since been marked done (done == 1) - either way, "available",
 * re-wiped fresh before being handed back out (a no-op re-init for a
 * genuinely never-issued slot, a real reset for a reclaimed one, same
 * call either way). returns 0 if every slot is currently issued and
 * live (none marked done) - a clean failure, not silent corruption. */
global ptr
arena_child(ptr vector)
{
	u64 i;
	ptr c;
 
	i = (u64)0;
	while(i < vector->child_count)
	{
		c = (ptr)((u64)vector->children + i * (u64)sizeof(struct arena));
		if(c->issued == (u64)0 || c->done == (u64)1)
		{
			arena_init(c, c->start, c->limit - c->start);
			c->issued = (u64)1;
			return c;
		}
		i = i + (u64)1;
	}
 
	return (ptr)0;
}
 
global void
arena_mark_done(ptr a)
{
	a->done = (u64)1;
}
 
global void
alloc_init(void)
{
	/* 16mib heap at a FIXED 32mib (0x2000000), not right after the
	 * kernel image (_end, ~0x142000) where it used to start. there is
	 * no virtual memory here: user programs load at fixed physical
	 * addresses -- sh at 0x400000 (user_shell.ld), everything else at
	 * 0x600000 (user_prog.ld) -- and a 16mib heap starting at _end
	 * covered BOTH. nothing is ever freed from heap_colosseum itself
	 * (only its fs_colosseum child grows real reclaim), so once about
	 * 2.7mb had been handed out in one boot, arena_alloc (and so
	 * sys_alloc) started returning sh's own memory, then the running
	 * program's:
	 * found for real once whole-file reads (cat/cp/mv of the ~170kb
	 * /kaboom) made large allocations routine -- ~11 `cat /kaboom`s
	 * in one boot panicked the kernel (sh's code overwritten, invalid
	 * opcode), and one run overwrote the kfs superblock on disk.
	 * 0x2000000 is well clear of both program windows (and of the
	 * kernel image, which can't outgrow dynamite's 1024-sector raw
	 * region anyway), inside boot.s's 1gib identity map, and the
	 * heap plus vmm.nsc's frame pool right after it (from
	 * heap_colosseum_limit(), 0x3000000 up) fit in the 128mib mk.conf
	 * gives qemu. still no relation to how much memory is actually
	 * installed -- that needs the e820 map, which nothing reads yet;
	 * this layout needs roughly 64mib to be real. once heap_colosseum
	 * is genuinely full, arena_alloc returns (ptr)0 -- a clean
	 * failure every caller can see, instead of silently handing out
	 * live memory. */
	arena_init(&heap_colosseum, (u64)0x2000000, (u64)0x1000000);
 
	/* fs_colosseum: 4mib carved out for filesystem buffers, same
	 * size this region has always been. holds one single, permanent
	 * arena (exec_filebuf) and one real vector (fd_cache_vec) instead
	 * of being one flat bump region callers used to arena_alloc
	 * anything they wanted out of directly -- see this session's design doc
	 * for why each is shaped the way it is. */
	if(arena_carve(&heap_colosseum, &fs_colosseum, (u64)0x400000) == 0)
	{
		/* heap_colosseum's 16mib couldn't cover fs_colosseum's 4mib
		 * carve -- can't happen at today's fixed sizes (see the note
		 * above), but a silent fs_colosseum based at physical address
		 * 0 would hand out real pointers into the ivt/bios data area
		 * instead, so this halts the same way kfs_mount's own missing-
		 * filesystem check does rather than limp on. serial/vga aren't
		 * initialized yet this early in boot -- klog_write is the only
		 * way to record it. */
		klog_write("kaboom: fs_colosseum carve failed -- halting\n");
		while(1)
		{
			halt();
		}
	}
 
	/* 65536 bytes: the same "minimum 63488, rounded" floor exec.nsc
	 * and fd.nsc's own fd_buf_need already enforced before this file
	 * existed, checked against every real binary this disk ships
	 * today (the largest, 4c.elf, is 31391 bytes) -- comfortably
	 * covers every realistic file either of these ever sees. anything
	 * genuinely bigger (the dynamite bootloader blob is the one
	 * documented real case) falls through to a direct, uncounted
	 * arena_alloc against fs_colosseum at the call site, same as this
	 * region's own behavior before colosseums existed at all. */
	exec_filebuf = arena_alloc(&fs_colosseum, (u64)65536);
	fd_cache_vec = arena_vector(&fs_colosseum, (u64)65536, (u64)5);
}
 
/* live usage/capacity accessors -- for /int/mem (virtfs.nsc), which
 * wants these as plain numbers without needing to know struct arena's
 * own layout. */
global u64
heap_colosseum_used(void)
{
	return heap_colosseum.current - heap_colosseum.start;
}
 
global u64
heap_colosseum_total(void)
{
	return heap_colosseum.limit - heap_colosseum.start;
}
 
global u64
fs_colosseum_used(void)
{
	return fs_colosseum.current - fs_colosseum.start;
}
 
global u64
fs_colosseum_total(void)
{
	return fs_colosseum.limit - fs_colosseum.start;
}
 
/* the absolute address just past everything heap_colosseum could ever
 * hand out (fs_colosseum is carved OUT OF heap_colosseum's own space,
 * near its start -- not appended after it -- so fs_colosseum.limit
 * alone is NOT "the end of everything," heap_colosseum.limit is) --
 * vmm.nsc's own general-purpose physical-frame pool starts right after
 * this, the same "one more thing carved past what came before"
 * pattern arena_carve itself already uses. */
global u64
heap_colosseum_limit(void)
{
	return heap_colosseum.limit;
}