Page Allocator

page-alloc-algorithm.c

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

typedef struct {
	union {
		uint8_t zero: 1;
		uint8_t fault: 1;
		uint8_t present: 1;
		uint8_t virtual: 1;
		uint8_t sequence: 1;
		uint8_t hardware: 1;
		uint8_t readonly: 1;
		uint8_t shareable: 1;
	};
	
	uint8_t kernel: 1;
	uint8_t active: 1;
	
	uint8_t unused[2];
} __attribute__((packed)) Page;

static struct {
	uint16_t canary_id;
	
	uint32_t last_index,
			 next_alloc;
} allocator;

// 4MB of RAM needs 1024 entries.
static Page memmap[1024];

static bool MmPageValid(int32_t index) {
	return (index >= 0 && 
			index < sizeof(memmap) / sizeof(memmap[0]));
}

// Find free sequence of pages of n size.
int32_t MmFindFirst(int32_t size) {
	uint32_t index = -1;
	
	for ( uint32_t position = allocator.last_index, pages = 0
		; position < (sizeof(memmap)/sizeof(memmap[0]))
		; position++)
	{	
		if (memmap[position].active == 0) {
			if (pages < size) {
				pages += 1;
			}
			else {
				return position - size;
			}
		}
	}
	
finished:
	return index;
}

uint32_t MmPhysAlloc(uint32_t pages) {
	uint32_t start = MmFindFirst(pages);
	
	if (MmPageValid(start)) {
		for ( uint32_t index = 0
			; index < pages 
			; index ++)
		{
			memmap[index].active = 1;
			memmap[index].present = 1;
			memmap[index].zero = 1;
			
			if (pages > 1 && index < (pages - 1)) {
				memmap[index].sequence = 1;
			}
		}
		
		allocator.last_index = (start + pages) + 1;
		allocator.next_alloc = allocator.last_index + 1;
		
		return start;
	}
	
	return sizeof(memmap) / sizeof(memmap[0]);
}



void hexdump(const void * data, size_t len)
{
	unsigned int i, r, c;
	uint8_t ch = 0;
	
	for (r=0,i=0; r<(len/16+(len%16!=0)); r++,i+=16)
	{
		// location of first byte in line
		printf( "%04X:    ",i); 
	
		for (c=i; c<i+8; c++) {
			// left half of hex dump
			if (c<len)
				printf("%02X ",((unsigned char const *)data)[c]);
			else
				// pad if short line
				printf("   "); 
		}
		printf("  ");
		
		// right half of hex dump
		for (c=i+8; c<i+16; c++) {
			const char* format = c<len? "%02X ": "   ";
			
			ch = (uint8_t)((const uint8_t *) data)[c];
			printf(format, ch);
		}
		
		printf("   | ");
		
		for (c=i; c<i+16; c++) {
			// ASCII dump
			if (c < len) {
				ch = (uint8_t)((const uint8_t *) data)[c];
				
				if ((ch >= 32) && 
					(ch < 127))
				{
					printf("%c", ch);
				}
				else {
					// put this for non-printables
					printf(".");
				}
			}
			else {
				// pad if short line
				printf(" ");
			}
		}
		
		printf(" |\n");
	}
}

int main(int args, char *arg[])
{	
	printf("First page_id is 0x%04x, second page_id is 0x%04x.\n", MmPhysAlloc(5), 
																   MmPhysAlloc(6));
	
	hexdump(memmap, sizeof(memmap) / sizeof(memmap[0]));
	return 0;
}