From a77b79c1959a134764b88cfe70411d109c6c0354 Mon Sep 17 00:00:00 2001
From: Jake Mannens <jakem_5@hotmail.com>
Date: Sun, 23 Feb 2020 03:35:26 +1100
Subject: Switched the physical memory allocator to a bitmap table. Previously,
 page allocations were recorded by marking entries in the dummy page tables
 'flow' and 'fupp'. This approach was not very memory efficient, since 4-bytes
 were used to record each page.

Now, a bitmap table is used, where every bit represents a page (every
byte therefore representing 8 pages). This approach also shaves some CPU
time during allocation, since 8 pages can be checked at a time by
testing whole bytes.
---
 Makefile                |  4 +---
 include/kernel/memory.h |  2 ++
 kernel/Makefile         |  3 +++
 kernel/memory.c         | 59 ++++++++++++++++++-------------------------------
 4 files changed, 27 insertions(+), 41 deletions(-)

diff --git a/Makefile b/Makefile
index aca4cab..fdd1362 100644
--- a/Makefile
+++ b/Makefile
@@ -21,9 +21,7 @@ clean:
 	rm -f $(TARGET)
 
 run: $(TARGET)
-	#qemu-system-x86_64 -s -kernel $(TARGET) -drive file=hd.img,format=raw -serial stdio
-	#qemu-system-x86_64 -s -kernel $(TARGET) -serial stdio
-	qemu-system-x86_64 -s -kernel $(TARGET) -nographic -curses
+	qemu-system-x86_64 -s -kernel $(TARGET) -serial stdio
 	#qemu-system-x86_64 -s -S -kernel $(TARGET) -drive file=hd.img,format=raw
 
 .FORCE:
diff --git a/include/kernel/memory.h b/include/kernel/memory.h
index 7217427..97073b3 100644
--- a/include/kernel/memory.h
+++ b/include/kernel/memory.h
@@ -1,5 +1,7 @@
 #include <stdint.h>
 
+#define NPAGES 2048
+
 #define PGENT 1024
 
 typedef uint32_t pte_t;
diff --git a/kernel/Makefile b/kernel/Makefile
index f9e14e8..1197636 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -28,3 +28,6 @@ $(TARGET): $(OBJS)
 clean:
 	rm -f $(OBJS)
 	rm -f $(TARGET)
+
+run:
+	make -C .. run
diff --git a/kernel/memory.c b/kernel/memory.c
index b369519..ee20c01 100644
--- a/kernel/memory.c
+++ b/kernel/memory.c
@@ -5,49 +5,43 @@
 
 static char __attribute__((aligned (4096))) mapped_page[4096];
 
+static char map[NPAGES / 8];
+
 static pdir_t kpdir;
 
 ptab_t ktab;
 
-static ptab_t flow;
-static ptab_t fupp;
-
 void *alloc_physical_page(void) {
-  int i;
-  void *ret;
+  int i, j;
 
-  for(i = 0; i < PGENT; i++) {
-    if(flow[i] & 1) {
-      ret = (void*) (flow[i] & ~1);
-      flow[i] = 0;
-      return ret;
-    }
+  for(i = 32; i < sizeof(map); i++) {
+    if(map[i] == -1)
+      continue;
 
-    if(fupp[i] & 1) {
-      ret = (void*) (fupp[i] & ~1);
-      fupp[i] = 0;
-      return ret;
+    for(j = 0; j < 8; j++) {
+      if(!((map[i] >> j) & 1))
+        break;
     }
+
+    map[i] |= 1 << j;
+    return (void*) (((i << 3) + j) << 12);
   }
 
   return NULL;
 }
 
 int free_physical_page(void *page) {
-  int i;
-  page = (void*) ((uint32_t) page & ~0xFFF);
+  char tmp;
+  uint32_t p = (uint32_t) page >> 12;
 
-  for(int i = 0; i < PGENT; i++) {
-    if(!(flow[i] & 1)) {
-      flow[i] = (uint32_t) page | 1;
-      return 0;
-    }
+  if(p > NPAGES)
+    return -1;
 
-    if(!(fupp[i] & 1)) {
-      fupp[i] = (uint32_t) page | 1;
-      return 0;
-    }
-  }
+  tmp = map[p >> 3];
+  map[p >> 3] &= ~(1 << (p & 7));
+
+  if((tmp & (1 << (p & 7))))
+    return 0;
 
   return -1;
 }
@@ -96,17 +90,6 @@ void paging_init(void) {
   for(i = 0; i < PGENT; i++)
     kpdir[i] = 0;
 
-  /* populate the free page tables */
-  for(i = 0; i < PGENT; i++) {
-    /* populate the lower table */
-    flow[i] = (i << 12);
-    /* only pages >1MB can be allocated */
-    if(i >= 0x100)
-      flow[i] |= 0x001;
-    /* populate the upper table */
-    fupp[i] = ((i << 12) + 0x400000) | 0x001;
-  }
-
   /* populate the kernel's page table */
   for(i = 0; i < PGENT; i++) {
     ktab[i] = 0;
-- 
cgit v1.3