Buddy Allocator

alloc.ptrs.js

import "printf", "malloc", "free" from "libc.so.6";
var cfree = free;

var minfactor = 3;
var maxfactor = 7;
var maxsize = 1 << maxfactor;

var startBlock = 1 << maxfactor;

var used = null;
var unused{maxfactor - minfactor + 1};

struct MemBlock
{
	ptr;
	factor;
	next = null;

	constructor(ptr, factor = maxfactor)
	{
		this.ptr = ptr;
		this.factor = factor;
	}
};

for(var i = 0; i < maxfactor - minfactor; i++)
{
	unused[i] = null;
}

unused[maxfactor - minfactor] = new MemBlock(startBlock);

function factor_alloc(factor)
{
	var block;
	var size = 1 << factor;
	var index = factor - minfactor;

	if(unused[index] != null)
	{
		var old = unused[index];
		block = old.ptr;
		unused[index] = old.next;
		cfree(old);

		printf("\tFound free block of size %5d (2^%d) at ", size, factor);
		printAsBinary(block);
		printf("\n");
	}
	else if(factor < maxfactor)
	{
		block = factor_alloc(factor + 1);
		unused[index] = new MemBlock(block + size, factor);

		printf("\tFound no block of size %7d (2^%d) => got bigger one - returning ", size, factor);
		printAsBinary(block);
		printf(", storing ");
		printAsBinary(block + size);
		printf("\n");
	}
	else
	{
		printf("\t/!\\ No block of size %d (2^%d) and cannot get a bigger one\n", size, factor);
		return NULL;
	}

	return block;
}

function alloc(size)
{
	if(size > maxsize)
	{
		printf("/!\\ Cannot alloc %d bytes, maximum size is %d\n", size, maxsize);
		return NULL;
	}

	var factor;
	for(factor = minfactor; factor < maxfactor; factor++)
	{
		if(1 << factor >= size)
			break;
	}

	printf("You want: %d, You get %d (2^%d)\n", size, 1 << factor, factor);
	var ptr = factor_alloc(factor);

	if(ptr != null)
	{
		var usedBlock = new MemBlock(ptr, factor);
		usedBlock.next = used;
		used = usedBlock;
	}
	return ptr;
}

function free(ptr)
{
	var prev = null;
	var curr = used;
	while(curr != null)
	{
		if(curr.ptr == ptr)
		{
			if(prev == null)
				used = curr.next;
			else
				prev.next = curr.next;

			var index = curr.factor - minfactor;
			curr.next = unused[index];
			unused[index] = curr;

			printf("Free'd memory at ");
			printAsBinary(ptr);
			printf("\n");
			return;
		}

		prev = curr;
		curr = curr.next;
	}

	printf("/!\\ Tried to free not allocated memory at ");
	printAsBinary(ptr);
	printf("\n");
}

function recombine()
{
	for(var i = 0; i < maxfactor - minfactor; i++)
	{
		var prev = null;
		var curr = unused[i];
		while(curr != null)
		{
			var prev2 = curr;
			var curr2 = curr.next;
			while(curr2 != null)
			{
				var prefix = curr.ptr >> curr.factor;
				var prefix2 = curr2.ptr >> curr2.factor;
				if((prefix | 1) == prefix2 || (prefix2 | 1) == prefix)
				{
					var lower = prefix < prefix2 ? curr : curr2;
					var higher = prefix < prefix2 ? curr2 : curr;

					printf("Combining buddies (size 2^%d): ", curr.factor);
					printAsBinary(lower.ptr);
					printf(" and ");
					printAsBinary(higher.ptr);
					printf("\n");

					prev2.next = curr2.next;

					if(prev == null)
						unused[i] = curr.next;
					else
						prev.next = curr.next;

					cfree(higher);
					lower.factor++;
					lower.next = unused[i + 1];
					unused[i + 1] = lower;

					recombine();
					return;
				}
				prev2 = curr2;
				curr2 = curr2.next;
			}
			prev = curr;
			curr = curr.next;
		}
	}
}

function dumpBlocks()
{
	printf("Unused:\n");
	for(var i = maxfactor - minfactor; i >= 0; i--)
	{
		printf("%3d | ", i + minfactor);
		var curr = unused[i];
		while(curr != null)
		{
			printAsBinary(curr.ptr);
			printf(" ");
			curr = curr.next;
		}
		printf("\n");
	}

	printf("Used: ");
	var curr = used;
	while(curr != null)
	{
		printf("(");
		printAsBinary(curr.ptr);
		printf(", %d)", curr.factor);

		if(curr.next != null)
			printf(", ");
		curr = curr.next;
	}
	printf("\n");
}

function printAsBinary(val)
{
	if(val == 0)
	{
		printf("NULL");
		return;
	}
	else if(val < 0)
	{
		printf("-");
		val = -val;
	}

	var buff[64];
	var i;
	for(i = 0; val > 0; i++)
	{
		buff[i] = val & 1 ? '1' : '0';
		val = val >> 1;
	}

	for(i--; i >= 0; i--)
		printf("%c", buff[i]);
}