src/user/malloc.nsc

/*
 * a real malloc/free: an explicit doubly-linked free list plus
 * boundary tags (a header AND a footer on every block, free or
 * allocated), first-fit search, splitting on allocation, bidirectional
 * coalescing on free -- the standard textbook design (CS:APP's
 * "explicit free list with boundary tags"), not the bump-only
 * allocator kaboom's kernel-side arena.nsc uses (sys_alloc/sys_free,
 * which this sits ON TOP of: sys_free really is a no-op, see
 * alloc.nsc's own note, so this file is what makes free() actually
 * mean something for a userspace program without needing to change
 * anything kernel-side).
 *
 * block layout (all offsets in bytes from the block's own header):
 *   [0]        header: (payload_size << 1) | alloc_bit, one word
 *   [8]        payload starts here
 *              -- if free: [8]=next free block, [16]=prev free block
 *              -- if allocated: whatever the caller put there
 *   [8+size]   footer: identical encoding to the header
 *
 * every chunk obtained from sys_alloc is bracketed with a permanently
 * -allocated, zero-payload prologue (before the first real block) and
 * epilogue (after the last real block) sentinel -- coalesce() never
 * needs to know a chunk's bounds directly, since a sentinel's alloc
 * bit is always 1, which stops leftward/rightward merging exactly at
 * the edge on its own. multiple chunks (heap_extend can be called
 * more than once) don't need to be contiguous for this to work.
 */
 
include "syscalls.nsh";
 
global ptr heap_free_head;
 
u64
round_up16(u64 n)
{
	return (n + (u64)15) & ~(u64)15;
}
 
u64
block_payload_size(ptr blk)
{
	return (u64)*blk >> (u64)1;
}
 
u64
block_is_alloc(ptr blk)
{
	return (u64)*blk & (u64)1;
}
 
void
block_set_header(ptr blk, u64 payload_size, u64 alloc_bit)
{
	*blk = (i64)((payload_size << (u64)1) | alloc_bit);
}
 
void
block_set_footer(ptr blk, u64 payload_size, u64 alloc_bit)
{
	ptr foot;
 
	foot = blk + (u64)8 + payload_size;
	*foot = (i64)((payload_size << (u64)1) | alloc_bit);
}
 
void
block_set(ptr blk, u64 payload_size, u64 alloc_bit)
{
	block_set_header(blk, payload_size, alloc_bit);
	block_set_footer(blk, payload_size, alloc_bit);
}
 
void
block_mark_alloc(ptr blk)
{
	block_set(blk, block_payload_size(blk), (u64)1);
}
 
void
block_mark_free(ptr blk)
{
	block_set(blk, block_payload_size(blk), (u64)0);
}
 
/* next/prev free-list pointers live IN the payload -- only ever read
 * on a block that's actually free (an allocated block's payload is
 * the caller's data, never touched by these). */
ptr
block_next_free(ptr blk)
{
	return (ptr)(u64)*(blk + (u64)8);
}
 
void
block_set_next_free(ptr blk, ptr next)
{
	*(blk + (u64)8) = (i64)(u64)next;
}
 
ptr
block_prev_free(ptr blk)
{
	return (ptr)(u64)*(blk + (u64)16);
}
 
void
block_set_prev_free(ptr blk, ptr prev)
{
	*(blk + (u64)16) = (i64)(u64)prev;
}
 
void
free_list_push(ptr blk)
{
	block_set_next_free(blk, heap_free_head);
	block_set_prev_free(blk, (ptr)0);
	if(heap_free_head != (ptr)0)
	{
		block_set_prev_free(heap_free_head, blk);
	}
	heap_free_head = blk;
}
 
void
free_list_remove(ptr blk)
{
	ptr p;
	ptr n;
 
	p = block_prev_free(blk);
	n = block_next_free(blk);
	if(p != (ptr)0)
	{
		block_set_next_free(p, n);
	}
	else
	{
		heap_free_head = n;
	}
	if(n != (ptr)0)
	{
		block_set_prev_free(n, p);
	}
}
 
ptr
free_list_find(u64 payload_size)
{
	ptr blk;
 
	blk = heap_free_head;
	while(blk != (ptr)0)
	{
		if(block_payload_size(blk) >= payload_size)
		{
			return blk;
		}
		blk = block_next_free(blk);
	}
	return (ptr)0;
}
 
/* splits blk if the leftover after carving out `need` bytes is big
 * enough to be its own free block (header+footer+minimum 16-byte
 * payload = 32 bytes) -- otherwise the whole block is handed over
 * as-is (a few wasted bytes beats a free block too small to ever
 * satisfy anything). blk's own header/footer are left UNCHANGED here
 * when no split happens -- block_mark_alloc (called right after by
 * every caller) is what actually flips the alloc bit, using whatever
 * size is already there. */
void
block_split_if_worthwhile(ptr blk, u64 need)
{
	u64 total;
	u64 remain;
	ptr newblk;
 
	total = block_payload_size(blk);
	if(total - need >= (u64)32)
	{
		remain = total - need - (u64)16;
		block_set(blk, need, (u64)0);
		newblk = blk + (u64)8 + need + (u64)8;
		block_set(newblk, remain, (u64)0);
		free_list_push(newblk);
	}
}
 
/* merges blk with a free physical neighbor on either side, using the
 * boundary tags (the word right before blk's header is the previous
 * block's footer; the word right after blk's footer is the next
 * block's header) -- a chunk's prologue/epilogue sentinels always
 * read as allocated, so this never walks past either end of whatever
 * chunk blk actually lives in. removes any merged neighbor from the
 * free list (it's being absorbed, not staying as its own entry) and
 * returns the resulting block's (possibly moved-left) address, still
 * marked free -- the caller is responsible for pushing it onto the
 * free list. */
ptr
coalesce(ptr blk)
{
	u64 sz;
	u64 prev_word;
	u64 next_word;
	ptr prev_blk;
	ptr next_blk;
 
	sz = block_payload_size(blk);
 
	prev_word = (u64)*(blk - (u64)8);
	if((prev_word & (u64)1) == (u64)0)
	{
		prev_blk = blk - (u64)16 - (prev_word >> (u64)1);
		free_list_remove(prev_blk);
		sz = sz + (u64)16 + (prev_word >> (u64)1);
		blk = prev_blk;
	}
 
	next_word = (u64)*(blk + (u64)8 + sz + (u64)8);
	if((next_word & (u64)1) == (u64)0)
	{
		next_blk = blk + (u64)8 + sz + (u64)8;
		free_list_remove(next_blk);
		sz = sz + (u64)16 + (next_word >> (u64)1);
	}
 
	block_set(blk, sz, (u64)0);
	return blk;
}
 
/* grows the heap by at least `need` bytes' worth of usable payload
 * (real malloc's sbrk/mmap growth, done here with sys_alloc since
 * that's the only "give me more memory" primitive kaboom's kernel
 * offers) -- a fresh chunk, bracketed by prologue/epilogue sentinels,
 * one big free block in between, pushed onto the free list. 64kib
 * minimum per chunk so a run of small mallocs doesn't turn into a
 * syscall each. */
i32
heap_extend(u64 need)
{
	u64 chunk_size;
	ptr chunk;
	u64 main_payload;
	ptr main_blk;
	ptr epilogue;
 
	chunk_size = need + (u64)40; /* prologue(16) + main hdr+ftr(16) + epilogue(8) */
	if(chunk_size < (u64)65536)
	{
		chunk_size = (u64)65536;
	}
 
	chunk = sys_alloc(chunk_size);
	if(chunk == (ptr)0)
	{
		return 0;
	}
 
	block_set(chunk, (u64)0, (u64)1); /* prologue sentinel */
 
	main_payload = chunk_size - (u64)40;
	main_blk = chunk + (u64)16;
	block_set(main_blk, main_payload, (u64)0);
	free_list_push(main_blk);
 
	/* epilogue: header only, no footer -- nothing is ever "after" it,
	 * and coalesce()'s right-hand check only ever reads a next
	 * block's HEADER, never a footer. */
	epilogue = main_blk + (u64)8 + main_payload + (u64)8;
	*epilogue = (i64)(u64)1;
	return 1;
}
 
global ptr
malloc(u64 size)
{
	u64 need;
	ptr blk;
 
	if(size == (u64)0)
	{
		return (ptr)0;
	}
 
	need = round_up16(size);
	if(need < (u64)16)
	{
		need = (u64)16;
	}
 
	blk = free_list_find(need);
	if(blk == (ptr)0)
	{
		if(heap_extend(need) == 0)
		{
			return (ptr)0;
		}
		blk = free_list_find(need);
		if(blk == (ptr)0)
		{
			return (ptr)0;
		}
	}
 
	free_list_remove(blk);
	block_split_if_worthwhile(blk, need);
	block_mark_alloc(blk);
	return blk + (u64)8;
}
 
global void
free(ptr p)
{
	ptr blk;
 
	if(p == (ptr)0)
	{
		return;
	}
	blk = p - (u64)8;
	block_mark_free(blk);
	blk = coalesce(blk);
	free_list_push(blk);
}