Orion

/*
 * This file handles allocating and freeing of page frames.  It it the core of
 * the physical memory manager.  The Kernel heap and paging systems both sit on
 * top of this.  It keeps track of which frames of physical memory are free and
 * hands them out as needed.  To do this it keeps a simple bitmap of the frames.
 */

#include <stdint.h>
#include "mem.h"
#include "paging.h"
#include "frame.h"
#include "../screen.h"

#define INDEX(a) ((a)/32)
#define OFFSET(a) ((a)%32)

/* Descriptor of a Frame Region */
typedef struct FrameRegion FrameRegion;
struct FrameRegion {
	uint32_t base;
	size_t numFrames;
	size_t usedFrames;
	FrameRegion *next;
	uint32_t bitmap[];
};

size_t numFrames, usedFrames;
FrameRegion *regions;

/* Count the number of pages a number of bytes occupies */
static size_t
page_count(size_t bytes)
{
	size_t pages = bytes/0x1000;
	if (bytes & 0xFFF)
		pages++;
	return pages;
}

/* Set a bit in the frame bitset */
static void
set_frame(FrameRegion *region, uint32_t idx)
{
	region->bitmap[INDEX(idx)] |= (1 << OFFSET(idx));
	region->usedFrames++;
	usedFrames++;
}

/* Clear a bit in the frame bitset */
static void
clear_frame(FrameRegion *region, uint32_t idx)
{
	region->bitmap[INDEX(idx)] &= ~(1 << OFFSET(idx));
	region->usedFrames--;
	usedFrames--;
}

/* Test a bit in the frame bitset */
static uint32_t
test_frame(FrameRegion *region, uint32_t idx)
{
	return (region->bitmap[INDEX(idx)] & (1 << OFFSET(idx)));
}

/* Get n bits from position p */
static inline uint32_t
get_bits(uint32_t x, uint8_t p, uint8_t n)
{
	return (x >> (p+1-n)) & ~(~0 << n);
}

/* Find first free frame */
static uint32_t
find_frames(FrameRegion *region, size_t frames)
{
	/* TODO: best fit */
	/* FIXME: frames can be at most 32 */
	uint32_t i, j;
	for (i = 0; i < INDEX(region->numFrames); i++) {
		if (!~region->bitmap[i])
			continue;
		for (j = 0; j < 32; j++) {
			if (get_bits(~region->bitmap[i], j, frames) == ~(~0 <<
			    frames))
				return (i*32+j)-frames+1;
			/* TODO: check across uint32_t boundaries */
		}
	}
	return (uint32_t) -1;
}

/* Allocate a set of contiguous page frames */
uint32_t
alloc_frames(size_t frames)
{
	uint32_t idx;
	size_t i;
	/* Walk the regions, first fit */
	FrameRegion *region;
	for (region = regions; region; region = region->next) {
		idx = find_frames(region, frames);
		if (idx != -1)
			break;
	}
	if (idx == -1)
		return -1;

	for (i = 0; i < frames; i++)
		set_frame(region, idx + i);

	return (uint32_t) region->base + (idx << 12);
}

/* Free a page frame */
void
free_frame(uint32_t frame)
{
	/* Walk the regions */
	FrameRegion *region = regions;
	while (region) {
		if ((uint32_t) region > frame) {
			frame -= region->base;
			clear_frame(region, frame >> 12);
			break;
		}
		region = region->next;
	}
}

/* Setup the frame allocator */
void
init_frames(uint32_t memMapSize, struct E820Entry *memMap)
{
	/* Relocate the memory map */
	struct E820Entry *top = (void *) 0x20000;
	if (memMap < top) {
		memcpy(top, memMap, memMapSize);
		memMap = (void *) top;
	}

	/*
	 * When the OS starts, the bootloader passes the Kernel a map of memory.
	 * This map must be read, so the memory manager can avoid bad areas of
	 * memory, that as mapped to hardware, ACPI, etc.
	 * The frame allocator should only create a bitmap for frames that it
	 * can actually allocate.  This means setting avoiding bad areas, and
	 * avoiding the Kernel.
	 */
	uint32_t i, j;
	FrameRegion *prev = 0, *head = regions;
	uint32_t bumpAlloc = 0x1000;
	for (i = 0; i < memMapSize / sizeof(struct E820Entry); i++) {
		kprintf("MemMap: base=%#.8x%.8x, length=%#.8x%.8x, type=%d",
		        memMap[i].baseHigh, memMap[i].base,
		        memMap[i].lengthHigh, memMap[i].length,
		        memMap[i].type);
		if (memMap[i].baseHigh > 0
		 || memMap[i].base > 0xFFFFFFFF
		 || memMap[i].type != 1)
			continue;

		/* Usable region - create bitmap */
		size_t frameSize  = memMap[i].length / 0x1000;
		size_t bitmapSize = (frameSize / 8);
		head = (FrameRegion *) bumpAlloc;
		bumpAlloc += bitmapSize + sizeof(FrameRegion);
		head->base = memMap[i].base;
		head->numFrames = frameSize;
		head->usedFrames = 0;
		memset(head->bitmap, 0, bitmapSize);
		/* Set top bits to 1, so they're never allocated */
		for (j = OFFSET(head->numFrames); j < 32; j++)
			set_frame(head, head->numFrames + j);
		if (prev) prev->next = head;
		else regions = head;
		prev = head;
	}

	/* Regions to be remapped */
	struct {uint32_t start, end;} remaps[] = {
		{.start = 0x0000,   .end = bumpAlloc}, /* PMM bitmaps */
		{.start = 0xB0000,  .end = 0xC0000  }, /* VGA memory */
		{.start = 0x100000, .end = 0x180000 }, /* Kernel */
	};

	kprintf("Bump allocator top @ %#.8x", bumpAlloc);

	/* Check bitmaps */
	usedFrames = 0;
	numFrames = 0;
	FrameRegion *region = regions;
	uint32_t regionEnd;
	while (region) {
		numFrames += region->numFrames;
		regionEnd = region->base + (region->numFrames * 0x1000);
		/* Iterate the remaps[] to find overlapping regions */
		for (i = 0; i < sizeof(remaps)/sizeof(remaps[0]); i++)
			for (j = remaps[i].start; j < remaps[i].end
			     && j >= region->base && j < regionEnd;
			     j += 0x1000)
				set_frame(region, (j - region->base) >> 12);
		region = region->next;
	}

	if (numFrames < 1024) /* 4MB */
		panic("Not enough memory");
}