mmu: Make certain allocations physical and virtual mapping linear

Previously it was possible for fragmentation to occur and as a result
certain allocations would have a linear virtual address space but not a
linear physical address space. This is bad since a lot of calls to
kmalloc_align rely upon both being linear, it has now been changed such
that all allocations done by kmalloc_align now guarantee this mapping
holds for both virtual and physical addresses.

It was due to oversight and sheer luck that this had been working for so
long.

8 files changed, 67 insertions, 72 deletions

diff --git a/kernel/Makefile b/kernel/Makefile
index 164b41c..7fd8310 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -1,6 +1,6 @@
 CC="i686-sb-gcc"
 AS="i686-sb-as"
-OBJ = arch/i386/boot.o init/kernel.o cpu/gdt.o cpu/reload_gdt.o cpu/idt.o cpu/io.o libc/stdio/print.o drivers/keyboard.o log.o drivers/pit.o libc/string/memcpy.o libc/string/strlen.o libc/string/memcmp.o drivers/ata.o libc/string/memset.o cpu/syscall.o  read_eip.o libc/exit/assert.o process.o libc/string/strcpy.o arch/i386/mmu.o kmalloc.o fs/ext2.o fs/vfs.o fs/devfs.o cpu/spinlock.o random.o libc/string/strcmp.o crypto/ChaCha20/chacha20.o crypto/SHA1/sha1.o fs/tmpfs.o libc/string/isequal.o drivers/pst.o kubsan.o drivers/serial.o socket.o poll.o fs/fifo.o hashmap/hashmap.o fs/shm.o elf.o ksbrk.o sched/scheduler.o libc/string/copy.o drivers/mouse.o libc/string/strlcpy.o libc/string/strcat.o drivers/vbe.o drivers/pci.o drivers/rtl8139.o network/ethernet.o network/arp.o network/bytes.o network/ipv4.o network/udp.o signal.o network/tcp.o drivers/ahci.o crypto/xoshiro256plusplus/xoshiro256plusplus.o arch/i386/interrupts.o cpu/isr.o lib/stack.o lib/buffered_write.o lib/list.o cpu/arch_inst.o cpu/int_syscall.o lib/ringbuffer.o lib/relist.o arch/i386/tsc.o arch/i386/asm_tsc.o drivers/cmos.o timer.o queue.o fonts.o drivers/ac97.o audio.o libc/ctype/isdigit.o
+OBJ = arch/i386/boot.o init/kernel.o cpu/gdt.o cpu/reload_gdt.o cpu/idt.o cpu/io.o libc/stdio/print.o drivers/keyboard.o log.o drivers/pit.o libc/string/memcpy.o libc/string/strlen.o libc/string/memcmp.o drivers/ata.o libc/string/memset.o cpu/syscall.o  read_eip.o libc/exit/assert.o process.o libc/string/strcpy.o arch/i386/mmu.o kmalloc.o fs/ext2.o fs/vfs.o fs/devfs.o cpu/spinlock.o random.o libc/string/strcmp.o crypto/ChaCha20/chacha20.o crypto/SHA1/sha1.o fs/tmpfs.o libc/string/isequal.o drivers/pst.o kubsan.o drivers/serial.o socket.o poll.o fs/fifo.o hashmap/hashmap.o fs/shm.o elf.o sched/scheduler.o libc/string/copy.o drivers/mouse.o libc/string/strlcpy.o libc/string/strcat.o drivers/vbe.o drivers/pci.o drivers/rtl8139.o network/ethernet.o network/arp.o network/bytes.o network/ipv4.o network/udp.o signal.o network/tcp.o drivers/ahci.o crypto/xoshiro256plusplus/xoshiro256plusplus.o arch/i386/interrupts.o cpu/isr.o lib/stack.o lib/buffered_write.o lib/list.o cpu/arch_inst.o cpu/int_syscall.o lib/ringbuffer.o lib/relist.o arch/i386/tsc.o arch/i386/asm_tsc.o drivers/cmos.o timer.o queue.o fonts.o drivers/ac97.o audio.o libc/ctype/isdigit.o
 CFLAGS = -std=c99 -O0 -fsanitize=vla-bound,shift-exponent,pointer-overflow,shift,signed-integer-overflow,bounds -ggdb -ffreestanding -Wall -Wextra -Wno-int-conversion -Wno-unused-parameter -Werror -mgeneral-regs-only -Wimplicit-fallthrough -I./libc/include/ -I. -Wno-pointer-sign -DKERNEL
 LDFLAGS=
 #CFLAGS = -std=c99 -O3 -flto -ggdb -ffreestanding -Wall -Wextra -Wno-int-conversion -Wno-unused-parameter -Werror -mgeneral-regs-only -Wimplicit-fallthrough -I./libc/include/ -I. -Wno-pointer-sign -DKERNEL
diff --git a/kernel/arch/i386/mmu.c b/kernel/arch/i386/mmu.c
index 1e00f17..d46b077 100644
--- a/kernel/arch/i386/mmu.c
+++ b/kernel/arch/i386/mmu.c
@@ -1,6 +1,5 @@
 #include <assert.h>
 #include <cpu/arch_inst.h>
-#include <ksbrk.h>
 #include <log.h>
 #include <math.h>
 #include <mmu.h>
@@ -26,8 +25,9 @@ u32 *tmp_small_frames = tmp_array;
 extern uintptr_t data_end;
 
 void change_frame(u32 frame, int on);
-int get_free_frame(u32 *frame);
+int get_free_frames(u32 *frame, size_t num_frames);
 int allocate_frame(Page *page, int rw, int is_kernel);
+int mmu_allocate_kernel_linear_virtual_to_physical_mapping(void *rc, size_t n);
 
 static int create_kernel_table(int table_index) {
   u32 physical;
@@ -53,7 +53,7 @@ static int create_kernel_table(int table_index) {
   return 1;
 }
 
-void *ksbrk(size_t s) {
+void *ksbrk(size_t s, int enforce_linear) {
   uintptr_t rc = (uintptr_t)align_page((void *)data_end);
   data_end += s;
   data_end = (uintptr_t)align_page((void *)data_end);
@@ -70,11 +70,18 @@ void *ksbrk(size_t s) {
     if (!create_kernel_table(table_index)) {
       return NULL;
     }
-    return ksbrk(s);
+    return ksbrk(s, enforce_linear);
   }
-  if (!mmu_allocate_shared_kernel_region((void *)rc,
-                                         (data_end - (uintptr_t)rc))) {
-    return NULL;
+  if (enforce_linear) {
+    if (!mmu_allocate_kernel_linear_virtual_to_physical_mapping(
+            (void *)rc, (data_end - (uintptr_t)rc))) {
+      return NULL;
+    }
+  } else {
+    if (!mmu_allocate_shared_kernel_region((void *)rc,
+                                           (data_end - (uintptr_t)rc))) {
+      return NULL;
+    }
   }
   get_fast_insecure_random(rc, s);
   assert(((uintptr_t)rc % PAGE_SIZE) == 0);
@@ -82,7 +89,7 @@ void *ksbrk(size_t s) {
 }
 
 void *ksbrk_physical(size_t s, void **physical) {
-  void *r = ksbrk(s);
+  void *r = ksbrk(s, 1);
   if (!r) {
     return NULL;
   }
@@ -147,7 +154,8 @@ void mmu_free_pages(void *a, u32 n) {
 }
 
 u32 start_frame_search = 1;
-int get_free_frame(u32 *frame) {
+int get_free_frames(u32 *frame, size_t num_frames) {
+  size_t counter = num_frames;
   u32 i = start_frame_search;
   for (; i < INDEX_FROM_BIT(num_array_frames * 32); i++) {
     if (tmp_small_frames[i] == 0xFFFFFFFF) {
@@ -155,9 +163,15 @@ int get_free_frame(u32 *frame) {
     }
 
     for (u32 c = 0; c < 32; c++) {
-      if (!(tmp_small_frames[i] & ((u32)1 << c))) {
-        start_frame_search = i;
-        *frame = i * 32 + c;
+      if ((tmp_small_frames[i] & ((u32)1 << c))) {
+        counter = num_frames;
+        continue;
+      }
+      start_frame_search = min(start_frame_search, i);
+
+      counter--;
+      if (0 == counter) {
+        *frame = i * 32 + c - (num_frames - 1);
         return 1;
       }
     }
@@ -211,7 +225,7 @@ PageTable *clone_table(u32 src_index, PageDirectory *src_directory,
       continue;
     }
     u32 frame_address;
-    if (!get_free_frame(&frame_address)) {
+    if (!get_free_frames(&frame_address, 1)) {
       kmalloc_align_free(new_table, sizeof(PageTable));
       return NULL;
     }
@@ -277,6 +291,9 @@ PageDirectory *clone_directory(PageDirectory *original) {
   }
   u32 offset = (u32)new_directory->physical_tables - (u32)new_directory;
   new_directory->physical_address = physical_address + offset;
+  assert(
+      new_directory->physical_address ==
+      (uintptr_t)virtual_to_physical((uintptr_t)new_directory + offset, NULL));
 
   for (int i = 0; i < 1024; i++) {
     if (!original->tables[i] && !kernel_directory->tables[i]) {
@@ -320,6 +337,33 @@ PageDirectory *clone_directory(PageDirectory *original) {
   return new_directory;
 }
 
+int mmu_allocate_kernel_linear_virtual_to_physical_mapping(void *rc, size_t n) {
+  size_t num_pages = align_page(n) / PAGE_SIZE;
+
+  u32 start_frame;
+  if (!get_free_frames(&start_frame, num_pages)) {
+    goto mmu_allocate_shared_kernel_region_error;
+  }
+
+  for (size_t i = 0; i < num_pages; i++) {
+    Page *p = get_page((void *)(rc + i * 0x1000), NULL, PAGE_ALLOCATE, 0);
+    if (!p) {
+      goto mmu_allocate_shared_kernel_region_error;
+    }
+    assert(!p->present);
+    p->present = 1;
+    p->rw = 1;
+    p->user = 0;
+    p->frame = start_frame + i;
+    assert(write_to_frame(p->frame * 0x1000, 1));
+  }
+  flush_tlb();
+  return 1;
+mmu_allocate_shared_kernel_region_error:
+  mmu_free_address_range(rc, n, NULL);
+  return 0;
+}
+
 int mmu_allocate_shared_kernel_region(void *rc, size_t n) {
   size_t num_pages = n / PAGE_SIZE;
   for (size_t i = 0; i <= num_pages; i++) {
@@ -436,7 +480,7 @@ int allocate_frame(Page *page, int rw, int is_kernel) {
     return 0;
   }
   u32 frame_address;
-  if (!get_free_frame(&frame_address)) {
+  if (!get_free_frames(&frame_address, 1)) {
     return 0;
   }
   assert(write_to_frame(frame_address * 0x1000, 1));
diff --git a/kernel/drivers/ahci.c b/kernel/drivers/ahci.c
index 1f3dcf4..9018df1 100644
--- a/kernel/drivers/ahci.c
+++ b/kernel/drivers/ahci.c
@@ -267,9 +267,9 @@ void ahci_sata_setup(volatile struct HBA_PORT *port) {
   // clb_address: size has to be 1024 and byte aligned to 1024
   // fb_address: size has to be 256 and byte aligned to 256
   // command_table_array: size has to be 256*32
-  u32 clb_address = (u32)ksbrk(1024);
-  u32 fb_address = (u32)ksbrk(256);
-  u32 command_table_array = (u32)ksbrk(256 * 32);
+  u32 clb_address = (u32)kmalloc_align(1024, 0);
+  u32 fb_address = (u32)kmalloc_align(256, 0);
+  u32 command_table_array = (u32)kmalloc_align(256 * 32, 0);
   create_physical_to_virtual_mapping(
       virtual_to_physical((void *)clb_address, NULL), (void *)clb_address,
       1024);
diff --git a/kernel/fs/ext2.c b/kernel/fs/ext2.c
index 948b0af..fe09834 100644
--- a/kernel/fs/ext2.c
+++ b/kernel/fs/ext2.c
@@ -382,7 +382,6 @@ int get_free_blocks(int allocate, int entries[], u32 num_entries) {
   u32 current_entry = 0;
   bgdt_t block_group;
   if (num_entries > superblock->num_blocks_unallocated) {
-    kprintf("greater than\n");
     return 0;
   }
   assert(0 == superblock->num_blocks_in_group % 8);
@@ -975,7 +974,7 @@ ext2_mount_error:
 }
 
 void parse_superblock(void) {
-  superblock = ksbrk(2 * SECTOR_SIZE);
+  superblock = kmalloc(2 * SECTOR_SIZE);
   raw_vfs_pread(mount_fd, superblock, 2 * SECTOR_SIZE,
                 EXT2_SUPERBLOCK_SECTOR * SECTOR_SIZE);
 
diff --git a/kernel/includes/mmu.h b/kernel/includes/mmu.h
index 319169f..580b40e 100644
--- a/kernel/includes/mmu.h
+++ b/kernel/includes/mmu.h
@@ -42,6 +42,7 @@ int mmu_allocate_region(void *ptr, size_t n, mmu_flags flags,
                         PageDirectory *pd);
 void mmu_free_pagedirectory(PageDirectory *pd);
 int mmu_allocate_shared_kernel_region(void *rc, size_t n);
+int mmu_allocate_kernel_linear_virtual_to_physical_mapping(void *rc, size_t n);
 void *mmu_find_unallocated_virtual_range(void *addr, size_t length);
 void mmu_remove_virtual_physical_address_mapping(void *ptr, size_t length);
 void mmu_free_address_range(void *ptr, size_t length, PageDirectory *pd);
@@ -60,7 +61,7 @@ PageDirectory *get_active_pagedirectory(void);
 void switch_page_directory(PageDirectory *directory);
 PageDirectory *clone_directory(PageDirectory *original);
 void *virtual_to_physical(void *address, PageDirectory *directory);
-void *ksbrk(size_t s);
+void *ksbrk(size_t s, int enforce_linear);
 void *ksbrk_physical(size_t s, void **physical);
 int write_to_frame(u32 frame_address, u8 on);
 
diff --git a/kernel/kmalloc.c b/kernel/kmalloc.c
index bea9431..e5c95af 100644
--- a/kernel/kmalloc.c
+++ b/kernel/kmalloc.c
@@ -1,7 +1,6 @@
 #include <assert.h>
 #include <interrupts.h>
 #include <kmalloc.h>
-#include <ksbrk.h>
 #include <log.h>
 #include <math.h>
 #include <mmu.h>
@@ -62,7 +61,7 @@ MallocHeader *final = NULL;
 u32 total_heap_size = 0;
 
 int init_heap(void) {
-  head = (MallocHeader *)ksbrk(NEW_ALLOC_SIZE);
+  head = (MallocHeader *)ksbrk(NEW_ALLOC_SIZE, 0);
   if (!head) {
     return 0;
   }
@@ -80,7 +79,7 @@ int add_heap_memory(size_t min_desired) {
   size_t allocation_size = max(min_desired, NEW_ALLOC_SIZE);
   allocation_size += delta_page(allocation_size);
   void *p;
-  if (!(p = (void *)ksbrk(allocation_size))) {
+  if (!(p = (void *)ksbrk(allocation_size, 0))) {
     return 0;
   }
   total_heap_size += allocation_size - sizeof(MallocHeader);
diff --git a/kernel/ksbrk.c b/kernel/ksbrk.c
deleted file mode 100644
index 82fc5ed..0000000
--- a/kernel/ksbrk.c
+++ /dev/null
@@ -1,40 +0,0 @@
-#include <assert.h>
-#include <ksbrk.h>
-#include <mmu.h>
-#include <stddef.h>
-#include <typedefs.h>
-
-/*
-extern uintptr_t data_end;
-extern PageDirectory *kernel_directory;
-
-#define HEAP 0x00E00000
-#define PHYS 0x403000
-#define PAGE_SIZE ((uintptr_t)0x1000)
-void *ksbrk(size_t s) {
-  uintptr_t rc = (uintptr_t)align_page((void *)data_end);
-  data_end += s;
-  data_end = (uintptr_t)align_page((void *)data_end);
-
-  if (!get_active_pagedirectory()) {
-    // If there is no active pagedirectory we
-    // just assume that the memory is
-    // already mapped.
-    return (void *)rc;
-  }
-  mmu_allocate_shared_kernel_region((void *)rc, (data_end - (uintptr_t)rc));
-  assert(((uintptr_t)rc % PAGE_SIZE) == 0);
-  memset((void *)rc, 0xFF, s);
-  return (void *)rc;
-}
-
-void *ksbrk_physical(size_t s, void **physical) {
-  void *r = ksbrk(s);
-  if (physical) {
-    //    if (0 == get_active_pagedirectory())
-    //      *physical = (void *)((uintptr_t)r - (0xC0000000 + PHYS) + HEAP);
-    //    else
-    *physical = (void *)virtual_to_physical(r, 0);
-  }
-  return r;
-}*/
diff --git a/kernel/ksbrk.h b/kernel/ksbrk.h
deleted file mode 100644
index fba060e..0000000
--- a/kernel/ksbrk.h
+++ /dev/null
@@ -1,8 +0,0 @@
-#ifndef KSBRK_H
-#define KSBRK_H
-#include <stddef.h>
-#include <typedefs.h>
-
-void *ksbrk(size_t s);
-void *ksbrk_physical(size_t s, void **physical);
-#endif