Orion

/*
 * This file contains the functions related to the Kernel's heap.  It uses a
 * simple method of allocating and freeing blocks from a pool in the Kernel's
 * memory space.  This heap will be present in every Page Directory, so can be
 * used to store any Kernel data structures.
 */

#include <stdint.h>
#include <stddef.h>
#include "mem.h"
#include "heap.h"
#include "frame.h"
#include "../vfs/cache.h"
#include "../screen.h"
#include "../spinlock.h"

#define KHEAP_START 0x200000 /* 2 MB */
#define KHEAP_END   0x800000 /* 8 MB */
#define BLOCK_SIZE  16

/* Structure for a Memory Header */
typedef struct Header {
	struct Header *next, *prev;
	size_t size;
	char magic[4];
} Header; /* 16 bytes */

size_t objectsAllocated = 0;
size_t freeSpace = KHEAP_END - KHEAP_START;

/* Allocate a region of the heap */
void *
kmalloc(size_t size)
{
	size_t blockSize, gapSize;
	uintptr_t blockEnd;
	Header *prev, *head, *next;
	head = prev = (void *) KHEAP_START;
	next = NULL;
	objectsAllocated++;

	/* Minimum allocation */
	if (size % BLOCK_SIZE)
		size += BLOCK_SIZE - (size % BLOCK_SIZE);
	freeSpace -= size + sizeof(Header);

	/* Low-memory VFS cache reaper */
	if (freeSpace < 0x10000) /* 64 KB */
		cache_reaper();

	/* Block does not exist, create heap */
	if (head->prev != head) {
		head->prev = head;
		head->next = NULL;
		head->size = size;
		memcpy(head->magic, "HEAP", 4);
		memset((void *) (head + 1), 0, size);
		return (void *) (head + 1);
	}

	/* Find gap */
	while (head->next) {
		next = head->next;
		blockSize = sizeof(Header) + head->size;
		blockEnd = (uintptr_t) head + blockSize;
		gapSize = (size_t) next - blockEnd;
		prev = head;

		/* Fit in gap */
		if (gapSize >= size + sizeof(Header)) {
			head = (void *) blockEnd;
			head->next = next;
			head->prev = prev;
			prev->next = head;
			next->prev = head;
			head->size = size;
			memcpy(head->magic, "HEAP", 4);
			memset((void *) (head + 1), 0, size);
			return (void *) (head + 1);
		}

		head = head->next;
	}

	/* Add to end */
	blockSize = sizeof(Header) + head->size;
	blockEnd = (uintptr_t) head + blockSize;
	gapSize = (size_t) KHEAP_END - blockEnd;
	/* Fit in gap */
	if (gapSize >= size + sizeof(Header)) {
		prev = head;
		head = (void *) blockEnd;
		head->next = NULL;
		head->prev = prev;
		prev->next = head;
		head->size = size;
		memcpy(head->magic, "HEAP", 4);
		memset((void *) (head + 1), 0, size);
		return (void *) (head + 1);
	}

	panic("Kernel heap exhausted");
}

/* Free an allocated region of the heap */
void
_kfree(void *addr, char *file, int line)
{
	Header *prev, *head, *next;
	head = (Header *) addr - 1;
	objectsAllocated--;
	freeSpace += head->size + sizeof(Header);

	if (memcmp(head->magic, "HEAP", 4))
		panic("Bad Kernel heap reference\n"
		      "Invalid target @ %#.8x (%s:%d)", addr, file, line);
	prev = head->prev;
	next = head->next;
	memset(head, 0, sizeof(Header));

	if (prev != head)
		prev->next = next;
	if (next)
		next->prev = prev;
}