# HG changeset patch
# User John Tsiombikas <nuclear@member.fsf.org>
# Date 1301514136 -10800
# Node ID 8be069e6bb058b55a4adba4467d6d347d7f522de
# Parent  096807345aa28ecda3fe03e36f33a4a034fbcd51
I think I'm done with the physical memory page allocator

diff -r 096807345aa2 -r 8be069e6bb05 src/main.c
--- a/src/main.c	Sun Mar 27 06:28:26 2011 +0300
+++ b/src/main.c	Wed Mar 30 22:42:16 2011 +0300
@@ -53,11 +53,13 @@
 
 	init_segm();
 	init_intr();
-	init_vm(mbinf);
 
 	/* silence the blasted timer interrupt */
 	interrupt(32, do_nothing);
 
+	init_vm(mbinf);
+
+
 	for(;;) {
 		char c, keypress;
 		do {
diff -r 096807345aa2 -r 8be069e6bb05 src/mem.c
--- a/src/mem.c	Sun Mar 27 06:28:26 2011 +0300
+++ b/src/mem.c	Wed Mar 30 22:42:16 2011 +0300
@@ -1,40 +1,181 @@
 #include <stdio.h>
+#include <string.h>
 #include "mem.h"
 #include "panic.h"
 #include "vm.h"
 
+#define FREE		0
+#define USED		1
+
+#define BM_IDX(pg)	((pg) / 32)
+#define BM_BIT(pg)	((pg) & 0x1f)
+
+#define IS_FREE(pg) ((bitmap[BM_IDX(pg)] & (1 << BM_BIT(pg))) == 0)
+
+static void mark_page(int pg, int free);
+static void add_memory(uint32_t start, size_t size);
+
 /* end of kernel image */
 extern int _end;
 
-static uint32_t brk;
+static uint32_t *bitmap;
+static int bmsize, last_alloc_idx;
 
 void init_mem(struct mboot_info *mb)
 {
-	/* start the physical allocated break at the end of
-	 * the kernel image
-	 */
-	brk = (uint32_t)&_end;
+	int i, num_pages, max_pg = 0;
+	uint32_t used_end;
+
+	num_pages = 0;
+	last_alloc_idx = 0;
+
+	bitmap = (uint32_t*)&_end;
+
+	/* start by marking all posible pages as used */
+	memset(bitmap, 0xff, 1024 * 1024 / 8);
+
+	/* build the memory map */
+	if(mb->flags & MB_MMAP) {
+		struct mboot_mmap *mem, *mmap_end;
+
+		mem = mb->mmap;
+		mmap_end = (struct mboot_mmap*)((char*)mb->mmap + mb->mmap_len);
+
+		printf("memory map:\n");
+		while(mem < mmap_end) {
+			char *type;
+			unsigned int end = mem->base_low + mem->length_low;
+
+			if(mem->type == MB_MEM_VALID) {
+				type = "free:";
+				add_memory(mem->base_low, mem->length_low);
+
+				num_pages = ADDR_TO_PAGE(mem->base_low + mem->length_low);
+				if(max_pg < num_pages) {
+					max_pg = num_pages;
+				}
+			} else {
+				type = "hole:";
+			}
+
+			printf("  %s %x - %x (%u bytes)\n", type, mem->base_low, end, mem->length_low);
+			mem = (struct mboot_mmap*)((char*)mem + mem->skip + sizeof mem->skip);
+		}
+	} else if(mb->flags & MB_MEM) {
+		add_memory(0, mb->mem_lower);
+		add_memory(0x100000, mb->mem_upper * 1024);
+		max_pg = mb->mem_upper / 4;
+
+		printf("lower memory: %ukb, upper mem: %ukb\n", mb->mem_lower, mb->mem_upper);
+	} else {
+		panic("didn't get any memory info from the boot loader, I give up\n");
+	}
+
+	bmsize = max_pg / 8;	/* size of the bitmap in bytes */
+
+	/* mark all the used pages as ... well ... used */
+	used_end = ((uint32_t)bitmap + bmsize - 1);
+
+	printf("marking pages up to %x ", used_end);
+	used_end = ADDR_TO_PAGE(used_end);
+	printf("(page: %d) inclusive as used\n", used_end);
+
+	for(i=0; i<=used_end; i++) {
+		mark_page(i, USED);
+	}
+
+	/*for(i=0; i<bmsize / 4; i++) {
+		printf("%3d [%x]\n", i, bitmap[i]);
+		asm("hlt");
+	}
+	putchar('\n');*/
 }
 
 uint32_t alloc_phys_page(void)
 {
-	uint32_t addr, dbg_prev_brk;
+	int i, idx, max;
 
-	if(ADDR_TO_PGOFFS(brk)) {
-		/* brk is not aligned, find the next page-aligned address */
-		addr = (brk + PGSIZE) & ~PGOFFS_MASK;
-	} else {
-		/* brk is aligned, so we can use that address directly */
-		addr = brk;
+	idx = last_alloc_idx;
+	max = bmsize / 4;
+
+	while(idx <= max) {
+		/* if at least one bit is 0 then we have at least
+		 * one free page. find it and allocate it.
+		 */
+		if(bitmap[idx] != 0xffffffff) {
+			for(i=0; i<32; i++) {
+				int pg = idx * 32 + i;
+
+				if(IS_FREE(pg)) {
+					mark_page(pg, USED);
+
+					last_alloc_idx = idx;
+
+					printf("alloc_phys_page() -> %x (page: %d)\n", PAGE_TO_ADDR(pg), pg);
+					return PAGE_TO_ADDR(pg);
+				}
+			}
+			panic("can't happen: alloc_phys_page (mem.c)\n");
+		}
+		idx++;
 	}
 
-	if(addr >= MAX_BRK) {
-		panic("alloc_phys_page() out of early alloc space");
+	panic("alloc_phys_page(): out of memory\n");
+	return 0;
+}
+
+void free_phys_page(uint32_t addr)
+{
+	int pg = ADDR_TO_PAGE(addr);
+	int bmidx = BM_IDX(pg);
+
+	if(!IS_FREE(pg)) {
+		panic("free_phys_page(%d): I thought that was already free!\n", pg);
 	}
 
-	dbg_prev_brk = brk;
-	brk = addr + PGSIZE;	/* move the break to the end of the page */
+	mark_page(pg, FREE);
+	if(bmidx < last_alloc_idx) {
+		last_alloc_idx = bmidx;
+	}
+}
 
-	printf("DBG: alloc_phys_page(): %x  (brk %x -> %x)\n", addr, dbg_prev_brk, brk);
-	return addr;
+void get_kernel_mem_range(uint32_t *start, uint32_t *end)
+{
+	if(start) {
+		*start = 0x100000;
+	}
+	if(end) {
+		uint32_t e = (uint32_t)bitmap + bmsize;
+
+		if(e & PGOFFS_MASK) {
+			*end = (e + 4096) & PGOFFS_MASK;
+		} else {
+			*end = e;
+		}
+	}
 }
+
+static void add_memory(uint32_t start, size_t sz)
+{
+	int i, szpg, pg;
+
+	szpg = ADDR_TO_PAGE(sz);
+	pg = ADDR_TO_PAGE(start);
+
+	for(i=0; i<szpg; i++) {
+		mark_page(pg++, FREE);
+	}
+}
+
+static void mark_page(int pg, int used)
+{
+	int idx = BM_IDX(pg);
+	int bit = BM_BIT(pg);
+
+	if(used) {
+		bitmap[idx] |= 1 << bit;
+	} else {
+		bitmap[idx] &= ~(1 << bit);
+	}
+}
+
diff -r 096807345aa2 -r 8be069e6bb05 src/mem.h
--- a/src/mem.h	Sun Mar 27 06:28:26 2011 +0300
+++ b/src/mem.h	Wed Mar 30 22:42:16 2011 +0300
@@ -3,10 +3,11 @@
 
 #include "mboot.h"
 
-/* maximum break for the early allocator */
-#define MAX_BRK		0x400000
+void init_mem(struct mboot_info *mb);
 
-void init_mem(struct mboot_info *mb);
 uint32_t alloc_phys_page(void);
+void free_phys_page(uint32_t addr);
+
+void get_kernel_mem_range(uint32_t *start, uint32_t *end);
 
 #endif	/* MEM_H_ */
diff -r 096807345aa2 -r 8be069e6bb05 src/vm.c
--- a/src/vm.c	Sun Mar 27 06:28:26 2011 +0300
+++ b/src/vm.c	Wed Mar 30 22:42:16 2011 +0300
@@ -29,13 +29,16 @@
 
 void init_vm(struct mboot_info *mb)
 {
+	uint32_t idmap_end;
+
 	init_mem(mb);
 
 	pgdir = (uint32_t*)alloc_phys_page();
 	memset(pgdir, 0, sizeof pgdir);
 
 	/* map the video memory and kernel code 1-1 */
-	map_mem_range(IDMAP_START, MAX_BRK - IDMAP_START, IDMAP_START, 0);
+	get_kernel_mem_range(0, &idmap_end);
+	map_mem_range(IDMAP_START, idmap_end - IDMAP_START, IDMAP_START, 0);
 
 	interrupt(PAGEFAULT, pgfault);
 
@@ -109,28 +112,6 @@
 	map_page_range(vpg_start, num_pages, ppg_start, attr);
 }
 
-
-/*	if(mb->flags & MB_MMAP) {
-		struct mboot_mmap *mem, *mmap_end;
-
-		mem = mb->mmap;
-		mmap_end = (struct mboot_mmap*)((char*)mb->mmap + mb->mmap_len);
-
-		printf("memory map:\n");
-		while(mem < mmap_end) {
-			unsigned int end = mem->base_low + mem->length_low;
-			char *type = mem->type == MB_MEM_VALID ? "free:" : "hole:";
-
-			printf("  %s %x - %x (%u bytes)\n", type, mem->base_low, end, mem->length_low);
-			mem = (struct mboot_mmap*)((char*)mem + mem->skip + sizeof mem->skip);
-		}
-	}
-
-	if(mb->flags & MB_MEM) {
-		printf("lower memory: %ukb, upper mem: %ukb\n", mb->mem_lower, mb->mem_upper);
-	}
-*/
-
 uint32_t virt_to_phys(uint32_t vaddr)
 {
 	uint32_t pgaddr, *pgtbl;
@@ -166,4 +147,6 @@
 	} else {
 		printf("page not present\n");
 	}
+
+	panic("unhandled page fault\n");
 }