arch: i386: kernel: add mostly finished PFA and paging system

Add the mostly finished physical memory allocator and expose its
functions to the paging system.

Signed-off-by: Danny Holman <dholman@gymli.org>

14 files changed, 219 insertions, 90 deletions

diff --git a/Makefile b/Makefile
index a0ce753..874f614 100644
--- a/Makefile
+++ b/Makefile
@@ -29,7 +29,6 @@ KERNEL_OBJS=$(KERNEL_ARCH_OBJS) \
 	    kernel/string.o \
 	    kernel/io.o \
 	    kernel/panic.o \
-	    kernel/mem.o \
 
 OBJS=$(ARCHDIR)/boot/crti.o \
      $(ARCHDIR)/crtbegin.o \
diff --git a/arch/i386/boot/boot.s b/arch/i386/boot/boot.s
index 2d17f6a..e443b08 100644
--- a/arch/i386/boot/boot.s
+++ b/arch/i386/boot/boot.s
@@ -19,14 +19,14 @@ stack_top:
         .align 4096
 boot_page_directory:
         .skip 4096
-boot_page_table0:
-        .skip 4096
+boot_page_tables:
+        .skip 20480
 
 .section .multiboot.text, "a"
 .global _start
 .type _start, @function
 _start:
-        movl $(boot_page_table0 - 0xC0000000), %edi
+        movl $(boot_page_tables - 0xC0000000), %edi
         movl $0, %esi
         movl $1023, %ecx
 
@@ -43,12 +43,16 @@ _start:
         addl $4, %edi
         loop 1b
 
-3:      movl $(0x000B8000 | 0x003), boot_page_table0 - 0xC0000000 + 1023 * 4
+3:      movl $0xB8003, boot_page_tables - 0xC0000000 + 1023 * 4
 
-        movl $(boot_page_table0 - 0xC0000000 + 0x003), boot_page_directory - 0xC0000000
-        movl $(boot_page_table0 - 0xC0000000 + 0x003), boot_page_directory - 0xC0000000 + 768 * 4
+        movl $boot_page_tables, %ecx
+        subl $0xC0000000, %ecx
+        orl $0x003, %ecx
+        movl %ecx, boot_page_directory - 0xC0000000
+        movl %ecx, boot_page_directory - 0xC0000000 + 4 * 768
 
-        movl $(boot_page_directory - 0xC0000000), %ecx
+        movl $boot_page_directory, %ecx
+        subl $0xC0000000, %ecx
         movl %ecx, %cr3
 
         movl %cr0, %ecx
diff --git a/arch/i386/include/kernel/asm.h b/arch/i386/include/kernel/asm.h
index 615da74..cf394e1 100644
--- a/arch/i386/include/kernel/asm.h
+++ b/arch/i386/include/kernel/asm.h
@@ -3,6 +3,23 @@
 
 #include <stdint.h>
 
+extern uintptr_t _kernel_start;
+extern uintptr_t _kernel_end;
+#define KSTART          ((uintptr_t)&_kernel_start)
+#define KEND            ((uintptr_t)&_kernel_end - 0xC0000000)
+
+#define HIMEM_START     0x00100000
+#define PAGE_SIZE       4096
+
+struct thread_block {
+        uint32_t esp;
+        uint32_t cr3;
+        unsigned int tid;
+        unsigned int tgid;
+        unsigned int state;
+        struct thread_block *next;
+};
+
 struct regs {
         uint32_t cr4;
         uint32_t cr3;
@@ -87,17 +104,18 @@ static inline uint8_t inb(uint16_t port) {
 
 static inline void enable_ints(void) {
         __asm__ volatile("sti");
-        return;
 }
 
 static inline void disable_ints(void) {
         __asm__ volatile("cli");
-        return;
 }
 
 static inline void flush_tss(void) {
         __asm__ volatile("movw $0x28, %ax; ltr %ax");
-        return;
+}
+
+static inline void invlpg(void *addr) {
+        __asm__ volatile("invlpg (%0)" : : "b"(addr) : "memory");
 }
 
 #endif
diff --git a/arch/i386/include/kernel/paging.h b/arch/i386/include/kernel/paging.h
index 7f820e8..e949e32 100644
--- a/arch/i386/include/kernel/paging.h
+++ b/arch/i386/include/kernel/paging.h
@@ -23,9 +23,10 @@
 #define ERR_RESERVED    0x8
 #define ERR_INST        0x10
 
-#define PAGE_SIZE       4096
+#define PGROUNDUP(size) (((size)+PAGE_SIZE-1) & ~(PAGE_SIZE-1))
+#define PGROUNDDN(size) (((size)) & ~(PAGE_SIZE-1))
 
-uint32_t* init_page_table(uint32_t flags);
+int init_page_directory(uintptr_t *pd, int user);
 void enable_paging(uintptr_t pd_addr);
 
 void paging_init(void);
diff --git a/arch/i386/include/kernel/pmem.h b/arch/i386/include/kernel/pmem.h
new file mode 100644
index 0000000..ddd9c8b
--- /dev/null
+++ b/arch/i386/include/kernel/pmem.h
@@ -0,0 +1,28 @@
+#ifndef I386_PMEM_H
+#define I386_PMEM_H
+
+#include <kernel/multiboot.h>
+#include <stdint.h>
+
+#define PFA_BLOCK_FREE  1
+#define PFA_BLOCK_ALLOC 3
+
+#define PFA_ALLOC_ERR   0xFFFFFFFF
+
+struct pfa_page {
+        struct pfa_page *next;
+};
+
+struct pfa_zone {
+        uintptr_t start;
+        uintptr_t size;
+        struct pfa_page *freelist;
+};
+
+int pfa_init(struct mboot_info *header);
+
+uintptr_t pfa_alloc(void);
+void pfa_free(struct pfa_zone *zone, uintptr_t paddr);
+void pfa_free_range(struct pfa_zone *zone, uintptr_t pstart, uintptr_t pend);
+
+#endif
diff --git a/arch/i386/kernel/jump_userspace.s b/arch/i386/kernel/jump_userspace.s
index fe69880..add144a 100644
--- a/arch/i386/kernel/jump_userspace.s
+++ b/arch/i386/kernel/jump_userspace.s
@@ -18,12 +18,4 @@ jump_userspace:
         call set_kernel_esp
         addl $4, %esp
 
-        movl $0x0004, %eax
-        orl $0x0002, %eax
-        pushl %eax
-        call init_page_dir
-        addl $4, %esp
-
-        movl %eax, %cr3
-
         iret
diff --git a/arch/i386/kernel/multiboot.c b/arch/i386/kernel/multiboot.c
index 87876f0..720866b 100644
--- a/arch/i386/kernel/multiboot.c
+++ b/arch/i386/kernel/multiboot.c
@@ -4,7 +4,7 @@
 #include <kernel/idt.h>
 #include <kernel/pic.h>
 #include <kernel/paging.h>
-#include <kernel/mem.h>
+#include <kernel/pmem.h>
 #include <kernel/keyboard.h>
 #include <kernel/framebuffer.h>
 #include <kernel/timer.h>
@@ -22,7 +22,6 @@ void i386_entry(uint32_t mboot_magic, struct mboot_info *header) {
         timer_init();
 
         register_irq_handler(1, keyboard_handler);
-        enable_ints();
 
         if (mboot_magic != MBOOT_LOADER_MAGIC) {
                 fb_write("NOT BOOTED WITH MULTIBOOT BOOTLOADER\n", 37);
@@ -30,6 +29,7 @@ void i386_entry(uint32_t mboot_magic, struct mboot_info *header) {
                 disable_ints();
                 while (1);
         }
+        map_page(NULL, (uintptr_t)header, (uintptr_t)header, PD_PRES);
         if (!(header->flags >> 6 & 0x1)) {
                 fb_write("NO MEMORY MAP FROM BOOTLOADER\n", 30);
                 fb_write("RESET PC!\n", 10);
@@ -37,6 +37,8 @@ void i386_entry(uint32_t mboot_magic, struct mboot_info *header) {
                 while (1);
         }
 
+        pfa_init(header);
+        enable_ints();
         kernel_main((char*)header->cmdline);
 
         while (1);
diff --git a/arch/i386/kernel/paging.c b/arch/i386/kernel/paging.c
index b2a1392..64afcf7 100644
--- a/arch/i386/kernel/paging.c
+++ b/arch/i386/kernel/paging.c
@@ -1,46 +1,80 @@
 #include <kernel/paging.h>
+#include <kernel/asm.h>
+#include <kernel/pmem.h>
+#include <kernel/panic.h>
+#include <kernel/errno.h>
 #include <kernel/io.h>
 #include <kernel/syscall.h>
 #include <kernel/string.h>
 
-extern uintptr_t _kernel_start;
-extern uintptr_t _kernel_end;
-static uintptr_t kstart = (uintptr_t)&_kernel_start;
-static uintptr_t kend = (uintptr_t)&_kernel_end - 0xC0000000;
-
 static uintptr_t page_directory[1024] __attribute__((aligned(PAGE_SIZE)));
 static uintptr_t first_page_table[1024] __attribute__((aligned(PAGE_SIZE)));
-static uintptr_t second_page_table[1024] __attribute__((aligned(PAGE_SIZE)));
 
 static int paging_enabled = 0;
 
-uint32_t* init_page_table(uint32_t flags) {
-        uint32_t *ret = kmalloc(sizeof(uint32_t)*1024);
-        for (int i = 0; i < 1024; i++)
-                ret[i] = flags;
+int init_page_table(uintptr_t *pd, int index, int user) {
+        if (pd == NULL)
+                return 0;
+
+        uintptr_t paddr = pfa_alloc();
+        if (paddr == PFA_ALLOC_ERR)
+                return -ENOMEM;
+
+        map_page(NULL, paddr, paddr, PD_PRES | PD_RW);
+        if (user)
+                pd[index] = paddr | PD_USR;
+        else
+                pd[index] = paddr;
+}
+
+int init_page_directory(uintptr_t *pd, int user) {
+        uintptr_t paddr = pfa_alloc();
+        if (paddr == PFA_ALLOC_ERR)
+                return -ENOMEM;
+
+        map_page(NULL, paddr, pd, PD_PRES | PD_RW);
+        for (int i = 0; i < 1023; i++)
+                init_page_table(pd, i, 0);
+        pd[1023] = paddr | 3;
+        return paddr;
 }
 
-uint32_t* init_page_dir(uint32_t flags) {
-        uint32_t *ret = init_page_table(flags);
-        ret[0] = ((uintptr_t)&first_page_table - 0xC0000000) | 3;
-        ret[768] = ((uintptr_t)&second_page_table - 0xC0000000) | 3;
+static void _alloc_new_page(uint32_t *cr3, uintptr_t vaddr, int user, int rw) {
+        uintptr_t paddr = pfa_alloc();
+        if (paddr == PFA_ALLOC_ERR)
+                panic("Cannot allocate physical page");
+
+        uint32_t flags = PD_PRES;
+        if (rw == 1)
+                flags |= PD_RW;
+        if (user == 1)
+                flags |= PD_USR;
+        map_page(cr3, paddr, vaddr, flags);
 }
 
 void paging_init(void) {
+        if (paging_enabled == 1)
+                return;
+
         for (int i = 0; i < 1024; i++) {
                 page_directory[i] = PD_RW;
                 first_page_table[i] = PD_RW;
-                second_page_table[i] = PD_RW;
         }
 
         page_directory[1023] = ((uintptr_t)&page_directory - 0xC0000000) | 3;
         page_directory[0] = ((uintptr_t)&first_page_table - 0xC0000000) | 3;
-        page_directory[768] = ((uintptr_t)&second_page_table - 0xC0000000) | 3;
-        for (uintptr_t i = kstart; i < kend; i += PAGE_SIZE)
-                map_page(page_directory, i, i + 0xC0000000, 0x003);
+        page_directory[768] = ((uintptr_t)&first_page_table - 0xC0000000) | 3;
+        for (uintptr_t i = KSTART; i < KEND; i += PAGE_SIZE)
+                map_page(page_directory, i, i + 0xC0000000, PD_PRES);
 
         enable_paging(((uintptr_t)&page_directory) - 0xC0000000);
         paging_enabled = 1;
+
+        for (int i = 0; i < 1023; i++) {
+                if (i == 0 || i == 768)
+                        continue;
+                init_page_table(page_directory, i, 0);
+        }
         return;
 }
 
@@ -55,17 +89,21 @@ void page_fault_handler(struct regs *regs) {
         int reserved = errno & ERR_RESERVED;
         int ifetch = errno & ERR_INST;
 
-        uintptr_t first_free;
-        if (!present)
-                map_page(regs->cr3, fault_addr, fault_addr, PD_PRES | PD_RW | PD_USR);
-        if (user)
-                panic("Usermode attempted to read supervisor page");
+        if (reserved || ifetch)
+                panic("Unknown error in page fault");
+        if (present && user)
+                panic("User process generated protection fault"); // TODO: this shouldn't panic
+        if (present && !user)
+                panic("Kernel process generated protection fault");
+
+        if (user && rw)
+                _alloc_new_page((uint32_t*)regs->cr3, fault_addr, 1, 1);
+        if (user && !rw)
+                _alloc_new_page((uint32_t*)regs->cr3, fault_addr, 1, 0);
         if (rw)
-                panic("Task wrote to read only page");
-        if (reserved)
-                panic("Task overwrote reserved page bits");
-        if (ifetch)
-                panic("Task paging instruction fetch failure");
+                _alloc_new_page((uint32_t*)regs->cr3, fault_addr, 0, 1);
+        if (!rw)
+                _alloc_new_page((uint32_t*)regs->cr3, fault_addr, 0, 0);
 }
 
 uintptr_t get_paddr(uintptr_t vaddr) {
@@ -73,11 +111,11 @@ uintptr_t get_paddr(uintptr_t vaddr) {
         uint32_t ptindex = (uint32_t)vaddr >> 12 & 0x03FF;
 
         uint32_t *pd = (uint32_t*)0xFFFFF000;
-        if (*pd & PD_PRES != 1)
-                return NULL;
+        if ((*pd & PD_PRES) != 1)
+                return 0;
         uint32_t *pt = ((uint32_t*)0xFFC00000) + (0x400 * pdindex);
-        if (*pt & PD_PRES != 1)
-                return NULL;
+        if ((*pt & PD_PRES) != 1)
+                return 0;
         return (uintptr_t)((pt[ptindex] & ~0xFFF) + ((uint32_t)vaddr & 0xFFF));
 }
 
@@ -85,15 +123,15 @@ void map_page(uint32_t *pd, uintptr_t paddr, uintptr_t vaddr, uint32_t flags) {
         if (pd == NULL)
                 pd = page_directory;
 
-        uintptr_t paddr_aligned = paddr & 0xFFFFF000;
-        uintptr_t vaddr_aligned = vaddr & 0xFFFFF000;
+        paddr = PGROUNDDN(paddr);
+        vaddr = PGROUNDDN(vaddr);
 
-        uintptr_t pdindex = vaddr_aligned >> 22;
-        uintptr_t ptindex = vaddr_aligned >> 12 & 0x03FF;
+        uintptr_t pdindex = vaddr >> 22;
+        uintptr_t ptindex = vaddr >> 12 & 0x03FF;
 
-        uintptr_t *pt = (pd[pdindex] + 0xC0000000 & 0xFFFFF000);
+        uintptr_t *pt = (uintptr_t*)((pd[pdindex] + 0xC0000000) & 0xFFFFF000);
         uintptr_t *pte = (uintptr_t*)(&pt[ptindex]);
-        *pte |= paddr_aligned | (flags & 0xFFF) | 0x01;
+        *pte |= paddr | (flags & 0xFFF) | 0x01;
 }
 
 void unmap_page(uint32_t *pd, uintptr_t vaddr) {
@@ -103,7 +141,7 @@ void unmap_page(uint32_t *pd, uintptr_t vaddr) {
         uintptr_t pdindex = vaddr >> 22;
         uintptr_t ptindex = vaddr >> 12 & 0x03FF;
 
-        uintptr_t *pt = (pd[pdindex] + 0xC0000000 & 0xFFFFF000);
+        uintptr_t *pt = (uintptr_t*)((pd[pdindex] + 0xC0000000) & 0xFFFFF000);
         uintptr_t *pte = (uintptr_t*)(&pt[ptindex]);
         *pte &= 0;
 }
diff --git a/arch/i386/kernel/pmem.c b/arch/i386/kernel/pmem.c
new file mode 100644
index 0000000..851b085
--- /dev/null
+++ b/arch/i386/kernel/pmem.c
@@ -0,0 +1,71 @@
+#include <kernel/pmem.h>
+#include <kernel/asm.h>
+#include <kernel/panic.h>
+#include <kernel/paging.h>
+#include <kernel/string.h>
+
+static struct pfa_zone bios_area;
+static struct pfa_zone himem;
+
+int pfa_init(struct mboot_info *header) {
+        bios_area.start = 0;
+        bios_area.size = 0;
+        bios_area.freelist = NULL;
+
+        himem.start = HIMEM_START;
+        himem.size = 0;
+        himem.freelist = NULL;
+
+        struct mboot_mmap_entry *mme = (struct mboot_mmap_entry*)(header->mmap_addr);
+        map_page(NULL, (uintptr_t)mme, (uintptr_t)mme, PD_PRES);
+        while ((uintptr_t)mme < (header->mmap_addr + header->mmap_length)) {
+                if (mme->addr_low >= KSTART && mme->addr_low <= KEND)
+                        continue;
+                if (mme->type == MBOOT_MEM_AVAILABLE) {
+                        if (mme->addr_low < HIMEM_START)
+                                pfa_free_range(&bios_area, (uintptr_t)mme->addr_low, (uintptr_t)(mme->addr_low+mme->len_low));
+                        else
+                                pfa_free_range(&himem, (uintptr_t)mme->addr_low, (uintptr_t)(mme->addr_low+mme->len_low));
+                }
+                unmap_page(NULL, (uintptr_t)mme);
+                mme += sizeof(struct mboot_mmap_entry);
+                map_page(NULL, (uintptr_t)mme, (uintptr_t)mme, PD_PRES);
+        }
+        unmap_page(NULL, (uintptr_t)mme);
+        return 0;
+}
+
+uintptr_t pfa_alloc(void) {
+        struct pfa_page *temp = bios_area.freelist;
+        map_page(NULL, (uintptr_t)temp, (uintptr_t)temp, PD_RW | PD_PRES);
+        if (temp == NULL)
+                return PFA_ALLOC_ERR;
+
+        bios_area.freelist = temp->next;
+        memset(temp, PFA_BLOCK_ALLOC, 32);
+        unmap_page(NULL, (uintptr_t)temp);
+        return (uintptr_t)temp;
+}
+
+void pfa_free(struct pfa_zone *zone, uintptr_t paddr) {
+        if (paddr % PAGE_SIZE != 0)
+                panic("Task attempted to free non-aligned memory");
+        if (paddr >= KSTART && paddr < KEND)
+                panic("Task attempted to free kernel memory");
+
+        map_page(NULL, paddr, paddr, PD_PRES | PD_RW);
+        memset((void*)paddr, PFA_BLOCK_FREE, 32);
+        struct pfa_page *temp = (struct pfa_page*)paddr;
+        temp->next = zone->freelist;
+        zone->freelist = temp;
+        unmap_page(NULL, paddr);
+        zone->size += PAGE_SIZE;
+}
+
+void pfa_free_range(struct pfa_zone *zone, uintptr_t pstart, uintptr_t pend) {
+        uintptr_t p = PGROUNDUP(pstart);
+        while (p <= pend) {
+                pfa_free(zone, p);
+                p += PAGE_SIZE;
+        }
+}
diff --git a/arch/i386/linker.ld b/arch/i386/linker.ld
index 7eb9d99..734310f 100644
--- a/arch/i386/linker.ld
+++ b/arch/i386/linker.ld
@@ -26,9 +26,5 @@ SECTIONS {
                 *(.bootstrap_stack)
         }
 
-        .usertext ALIGN(4K) : AT(ADDR(.usertext) - 0xC0000000) {
-                *(.usertext)
-        }
-
         _kernel_end = .;
 }
diff --git a/arch/i386/make.config b/arch/i386/make.config
index 91b665d..1ffe8be 100644
--- a/arch/i386/make.config
+++ b/arch/i386/make.config
@@ -15,3 +15,4 @@ KERNEL_ARCH_OBJS=$(ARCHDIR)/boot/boot.o \
                  $(ARCHDIR)/kernel/timer.o \
                  $(ARCHDIR)/kernel/syscall.o \
                  $(ARCHDIR)/kernel/paging.o \
+                 $(ARCHDIR)/kernel/pmem.o \
diff --git a/include/kernel/mem.h b/include/kernel/mem.h
deleted file mode 100644
index aae3091..0000000
--- a/include/kernel/mem.h
+++ /dev/null
@@ -1,8 +0,0 @@
-#ifndef KERNEL_MEM_H
-
-#include <stddef.h>
-
-int init_kmalloc(void);
-void* kmalloc(size_t sz);
-
-#endif
diff --git a/kernel/init.c b/kernel/init.c
index 86567a4..8512988 100644
--- a/kernel/init.c
+++ b/kernel/init.c
@@ -1,5 +1,5 @@
 #include <kernel/io.h>
-#include <kernel/mem.h>
+#include <kernel/kmalloc.h>
 #include <kernel/string.h>
 #include <kernel/serial.h>
 
@@ -8,6 +8,7 @@ void jump_userspace(void);
 char rootfs[1024];
 
 int start_init(int argc, char* argv[]) {
+        while (1);
         return 0;
 }
 
@@ -22,4 +23,5 @@ void process_cmd(char *cmdline) {
 void kernel_main(char *cmdline) {
         kprintf("Box Kernel version %s\n", VERSION);
         serial_init();
+        kmalloc_init();
 }
diff --git a/kernel/mem.c b/kernel/mem.c
deleted file mode 100644
index e977f6a..0000000
--- a/kernel/mem.c
+++ /dev/null
@@ -1,15 +0,0 @@
-#include <kernel/mem.h>
-#include <kernel/paging.h>
-
-extern uintptr_t _kernel_end;
-static uintptr_t heap_start = (uintptr_t)&_kernel_end;
-static uintptr_t heap_end = (uintptr_t)&_kernel_end;
-
-void* kmalloc(size_t sz) {
-        void *tmp = heap_end;
-        heap_end += sz;
-        return tmp;
-}
-
-void kfree(void *ptr) {
-}