3 files changed, 70 insertions, 20 deletions

diff --git a/src/kernel/malloc.c b/src/kernel/malloc.c
index 7385cf3..44434ed 100644
--- a/src/kernel/malloc.c
+++ b/src/kernel/malloc.c
@@ -27,7 +27,7 @@ page_amt(size_t bytes)
 }
 
 void
-mem_debugprint(void)
+kmalloc_debugprint(void)
 {
 	size_t count = 0, bytes = 0, pages = 0;
 	kprintf("[kern] current allocations:\n");
diff --git a/src/kernel/malloc.h b/src/kernel/malloc.h
index efbd9c8..436d899 100644
--- a/src/kernel/malloc.h
+++ b/src/kernel/malloc.h
@@ -12,6 +12,8 @@ void mem_init(void *memtop);
 void mem_reserve(void *addr, size_t len);
 void mem_debugprint(void);
 
+void kmalloc_debugprint(void); /* internal, called by mem_debugprint */
+
 // allocates `pages` consecutive pages
 void *page_alloc(size_t pages);
 // zeroes the allocated pages
diff --git a/src/kernel/pagealloc.c b/src/kernel/pagealloc.c
index f01c295..ade5b9a 100644
--- a/src/kernel/pagealloc.c
+++ b/src/kernel/pagealloc.c
@@ -6,10 +6,17 @@
 #include <stdbool.h>
 #include <stdint.h>
 
+typedef struct FreePage FreePage;
+struct FreePage {
+	FreePage *next;
+};
+static FreePage *firstfreepage;
+
 extern uint8_t pbitmap[]; /* linker.ld */
 static size_t pbitmap_len; /* in bytes */
-static void *memtop;
-static void *firstfreepage; /* not necessarily actually free */
+static void *watermark; /* first nonallocated page */
+static void *memtop; /* end of physical memory */
+static int curallocs = 0;
 
 static size_t
 toindex(void *p)
@@ -24,7 +31,7 @@ pbitmap_get(void *p)
 	size_t i = toindex(p);
 	size_t b = i / 8;
 	uint8_t m = 1 << (i&7);
-	assert(b < pbitmap_len); // TODO the bitmap should be a tad longer
+	assert(b < pbitmap_len);
 	return (pbitmap[b]&m) != 0;
 }
 
@@ -44,15 +51,33 @@ pbitmap_set(void *p, bool v)
 	return prev;
 }
 
+/* watermark allocator. doesn't mark the page as allocated in the bitmap. */
+static void *
+wmalloc(void)
+{
+	/* skip over reserved pages */
+	while (watermark < memtop && pbitmap_get(watermark)) {
+		watermark += PAGE_SIZE;
+	}
+	if (watermark < memtop) {
+		void *p = watermark;
+		watermark += PAGE_SIZE;
+		return p;
+	} else {
+		return NULL;
+	}
+}
+
 void
 mem_init(void *p)
 {
 	memtop = p;
 	kprintf("memory   %8x -> %8x\n", &_bss_end, memtop);
-	pbitmap_len = toindex(memtop) / 8;
+	pbitmap_len = (toindex(memtop) + 7) / 8; /* rounds up */
 	memset(pbitmap, 0, pbitmap_len);
 	mem_reserve(pbitmap, pbitmap_len);
-	firstfreepage = pbitmap;
+	mem_reserve(memtop, 4096 * 8);
+	watermark = pbitmap;
 }
 
 void
@@ -63,12 +88,14 @@ mem_reserve(void *addr, size_t len)
 	void *top = min(addr + len, memtop);
 	addr = (void*)((uintptr_t)addr & ~PAGE_MASK); /* round down to page */
 	for (void *p = max(addr, (void*)pbitmap); p < top; p += PAGE_SIZE) {
-		/* this doesn't allow overlapping reserved regions, but, more
-		 * importantly, it prevents reserving an already allocated page */
+		/* This doesn't allow overlapping reserved regions, but, more
+		 * importantly, it prevents reserving an already allocated page.
+		 * Note that a reserved page can be freed. */
 		if (pbitmap_get(p)) {
 			panic_invalid_state();
 		}
 		pbitmap_set(p, true);
+		curallocs++;
 	}
 }
 
@@ -83,16 +110,25 @@ page_zalloc(size_t pages)
 void *
 page_alloc(size_t pages)
 {
+	void *ret;
 	assert(pages == 1);
-	for (void *p = firstfreepage; p < memtop; p += PAGE_SIZE) {
-		if (!pbitmap_get(p)) {
-			pbitmap_set(p, true);
-			firstfreepage = p + PAGE_SIZE;
-			return p;
-		}
+	if (firstfreepage != NULL) {
+		ret = firstfreepage;
+		firstfreepage = firstfreepage->next;
+	} else {
+		ret = wmalloc();
+	}
+
+	if (ret == NULL) {
+		mem_debugprint();
+		kprintf("we ran out of memory :(\ngoodbye.\n");
+		panic_unimplemented();
+	} else {
+		assert(pbitmap_get(ret) == false);
+		pbitmap_set(ret, true);
+		curallocs += pages;
+		return ret;
 	}
-	kprintf("we ran out of memory :(\ngoodbye.\n");
-	panic_unimplemented();
 }
 
 void
@@ -100,9 +136,21 @@ page_free(void *addr, size_t pages)
 {
 	assert((void*)pbitmap <= addr);
 	for (size_t i = 0; i < pages; i++) {
-		if (pbitmap_set(addr + i*PAGE_SIZE, false) == false) {
-			panic_invalid_state();
-		}
+		FreePage *fp = addr + i*PAGE_SIZE;
+		assert(pbitmap_get(fp) == true);
+		pbitmap_set(fp, false);
+		fp->next = firstfreepage;
+		firstfreepage = fp;
 	}
-	firstfreepage = min(firstfreepage, addr);
+	curallocs -= pages;
+}
+
+void
+mem_debugprint(void)
+{
+	kprintf(
+		"[kern] %d pages allocated, watermark at %08p / %08p\n",
+		curallocs, watermark, memtop
+	);
+	kmalloc_debugprint();
 }