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.

1 files changed, 21 insertions, 38 deletions

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;