simplify source tree; compact def tables

14 files changed, 468 insertions, 10 deletions

diff --git a/.gitmodules b/.gitmodules
deleted file mode 100644
index b281561..0000000
--- a/.gitmodules
+++ /dev/null
@@ -1,3 +0,0 @@
-[submodule "src/arch_x86/64/heap/diheap"]
-	path = src/arch_x86/64/heap/diheap
-	url = https://git.jonsantmyer.com/diheap
diff --git a/include/arch_common/boot.h b/include/arch_common/boot.h
index bdd1b8b..5c2da29 100644
--- a/include/arch_common/boot.h
+++ b/include/arch_common/boot.h
@@ -25,8 +25,6 @@
 #include <stddef.h>
 #include <stdbool.h>
 
-#include "edid.h"
-
 #define MODIT_HIGHER_HALF_X86_64    0xFFFFFFFF80000000
 
 #ifdef ARCH_x86
diff --git a/include/arch_common/modit.h b/include/arch_common/modit.h
index f046191..a573a42 100644
--- a/include/arch_common/modit.h
+++ b/include/arch_common/modit.h
@@ -29,4 +29,6 @@ typedef char symbol_t[];
 #define ALIGNED(n) __attribute__((aligned(n)))
 #define PAGEALIGN ALIGNED(4096)
 
+#define THREAD 
+
 #endif
diff --git a/include/arch_x86/common/list.h b/include/arch_x86/common/list.h
new file mode 100644
index 0000000..923010c
--- /dev/null
+++ b/include/arch_x86/common/list.h
@@ -0,0 +1,25 @@
+#ifndef MODIT_KERNEL_KLIBC_LIST_H
+#define MODIT_KERNEL_KLIBC_LIST_H 1
+
+#include <stddef.h>
+
+//Add struct to top of struct to create sll node object for data type
+struct sllist
+{
+    struct sllist *next;
+};
+
+#define sll_foreach(type, head) for(type * node = head; node != NULL; node = (type*)(((struct sllist*) node)->next))
+
+//Returns count of all elements in sll
+size_t sll_count(void *head);
+
+//Returns data for element at index n, NULL for oob
+void *sll_at(void *head, size_t n);
+
+//Returns new tail
+void *sll_append(void *tail, void *node);
+
+void *sll_appbeg(void *head, void *node);
+
+#endif
diff --git a/src/arch_x86/64/apic/ioapic.c b/src/arch_x86/64/apic/ioapic.c
index 915d4de..eda98d0 100644
--- a/src/arch_x86/64/apic/ioapic.c
+++ b/src/arch_x86/64/apic/ioapic.c
@@ -132,5 +132,5 @@ apic_ioapic_setup(void)
         }
     }
 
-
+    printk(KERNEL_INFO, "Setup IOAPIC\n");
 }
diff --git a/src/arch_x86/64/apic/main.c b/src/arch_x86/64/apic/main.c
index 6805f75..7370343 100644
--- a/src/arch_x86/64/apic/main.c
+++ b/src/arch_x86/64/apic/main.c
@@ -1,5 +1,6 @@
 #include "modit.h"
 #include "apic.h"
+#include "stdio.h"
 #include <stddef.h>
 
 MODULE static void
@@ -10,6 +11,7 @@ apic_constructor(void)
     apic_lapic_setup();
     apic_lapic_enable();
 
+    printk(KERNEL_INFO, "Setup LAPIC\n");
     apic_ioapic_setup();
 
     asm volatile("sti");
diff --git a/src/arch_x86/64/heap/diheap b/src/arch_x86/64/heap/diheap
deleted file mode 160000
-Subproject cc8beb0a8b6b83b884b2f310b766700816cf368
diff --git a/src/arch_x86/64/heap/diheap.c b/src/arch_x86/64/heap/diheap.c
new file mode 100644
index 0000000..59a257b
--- /dev/null
+++ b/src/arch_x86/64/heap/diheap.c
@@ -0,0 +1,281 @@
+/*
+ * heap.c
+ * Copyright (c) 2021 Jon Santmyer <jon@jonsantmyer.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+/**
+ * File              : heap.c
+ * Author            : Jon Santmyer <jon@jonsantmyer.com>
+ * Date              : 10.12.2021
+ */
+
+#include "heap.h"
+#include <string.h>
+
+int
+heap_create(struct heap *heap, uintptr_t at, size_t len)
+{
+    struct crate *firstcrate = NULL;
+    struct bucket *cratebucket = NULL;
+
+    memset(heap, 0, sizeof(struct heap));
+    
+    heap->start = at;
+    heap->size = len;
+
+    /*check if heap can fit crate*/
+    if(len < HEAP_CRATE_SIZE) return -1;
+
+    /*Populate first crate*/
+    heap->crates_tail = heap->crates_head = firstcrate = (struct crate*)at;
+    cratebucket = &firstcrate->buckets[0];
+
+    heap->used = HEAP_CRATE_SIZE;
+    memset(firstcrate, 0, HEAP_CRATE_SIZE);
+
+    /*Allocate first bucket for crate*/
+    heap->buckets_tail = heap->buckets_head = cratebucket;
+    cratebucket->address = (uintptr_t)firstcrate;
+    cratebucket->sizetaken = HEAP_CRATE_SIZE | 1;
+
+    /*Set buckets after 1 to link to free list*/
+    for(size_t i = 2; i < HEAP_CRATE_BUCKETS; i++) {
+        struct bucket *prev = &firstcrate->buckets[i - 1];
+        struct bucket *bucket = &firstcrate->buckets[i];
+
+        prev->next = bucket;
+        bucket->prev = prev;
+    }
+    heap->buckets_unused_tail = &firstcrate->buckets[1];
+
+    return 0;
+}
+
+void
+heap_resize(struct heap *heap, size_t newsize)
+{
+    heap->size = newsize;
+}
+
+struct bucket*
+__heap_bucket_findbest(struct heap *heap, size_t size)
+{
+    struct bucket *best = NULL;
+    for(struct bucket *bucket = heap->buckets_tail; 
+            bucket != NULL;
+            bucket = bucket->next)
+    {
+        if(HEAP_BUCKET_TAKEN(bucket)) continue;
+        if(bucket->sizetaken < size) continue;
+        if(best == NULL) best = bucket;
+        if(best->sizetaken > bucket->sizetaken) best = bucket;
+    }
+
+    return best;
+}
+
+struct bucket*
+__heap_crate_create(struct heap *heap)
+{
+    size_t remaining = heap->size - heap->used;
+    struct bucket *crate_bucket = NULL;
+    struct crate *crate = NULL;
+
+    /*Check for room in heap*/
+    if(remaining < HEAP_CRATE_SIZE) {
+        return NULL;
+    }
+
+    /*Take crate bucket from crate head*/
+    crate_bucket = &heap->crates_head->reserved;
+
+    /*Populate crate bucket*/
+    crate_bucket->address = heap->start + heap->used;
+    crate_bucket->sizetaken = HEAP_CRATE_SIZE | 1;
+    crate_bucket->prev = heap->buckets_head;
+    heap->buckets_head = crate_bucket;
+
+    /*Populate crate, linking buckets together*/
+    crate = (struct crate*)crate_bucket->address;
+    memset(crate, 0, HEAP_CRATE_SIZE);
+
+    for(size_t i = 0; i < HEAP_CRATE_BUCKETS; i++) {
+        struct bucket *bucket = &crate->buckets[i];
+        struct bucket *prev = &crate->buckets[i-1];
+
+        bucket->prev = prev;
+        prev->next = bucket;
+    }
+
+    /*Set unused tail to first bucket*/
+    heap->buckets_unused_tail = &crate->buckets[0];
+
+    /*Add crate to crate list*/
+    heap->crates_head->next = crate;
+    heap->crates_head = crate;
+
+    /*Add used memory to heap info*/
+    heap->used += HEAP_CRATE_SIZE;
+
+    return heap->buckets_unused_tail;
+}
+
+struct bucket*
+__heap_bucket_append(struct heap *heap, struct bucket *bucket, size_t size)
+{
+    /*Get free bucket from crate*/
+    struct bucket *free = heap->buckets_unused_tail;
+    if(free == NULL) {
+        free = __heap_crate_create(heap);
+        if(free == NULL) return NULL;
+    }
+    heap->buckets_unused_tail = heap->buckets_unused_tail->next;
+
+    /*Append free to bucket chain*/
+    free->prev = bucket;
+    free->next = bucket->next;
+    if(free->next != NULL) free->next->prev = free;
+    bucket->next = free;
+
+    /*Mark up to head used memory*/
+    if(free->next == NULL) {
+        heap->used += size;
+        heap->buckets_head = free;
+    }
+
+    /*Populate free bucket*/
+    free->address = bucket->address + (bucket->sizetaken & ~1);
+    free->sizetaken = size;
+
+    return free;
+}
+
+void
+__heap_bucket_release(struct heap *heap, struct bucket *bucket)
+{
+    /*Disconnect bucket from main chain*/
+    if(bucket->prev != NULL) {
+        bucket->prev->next = bucket->next;
+    }else{
+        heap->buckets_tail = bucket->next;
+    }
+
+    if(bucket->next != NULL) {
+        bucket->next->prev = bucket->prev;
+    }else{
+        heap->buckets_head = bucket->prev;
+    }
+
+    /*Attach bucket to unused list*/
+    bucket->next = heap->buckets_unused_tail;
+    bucket->prev = NULL;
+
+    heap->buckets_unused_tail = bucket;
+}
+
+void
+__heap_bucket_split(struct heap *heap, struct bucket *bucket, size_t size)
+{
+    /*Check if split is required*/
+    intmax_t diff = bucket->sizetaken - size;
+    if(diff <= 0) return;
+
+    /*Shrink bucket to required size*/
+    bucket->sizetaken = size;
+    
+    /*Create new bucket with remainder*/
+    __heap_bucket_append(heap, bucket, diff);
+}
+
+void
+__heap_bucket_merge(struct heap *heap, struct bucket *bucket)
+{
+    struct bucket *prev = bucket->prev;
+    struct bucket *next = bucket->next;
+
+    /*Merge bucket with prev*/
+    if(prev != NULL) {
+        if(!HEAP_BUCKET_TAKEN(prev)) {
+            prev->sizetaken += bucket->sizetaken;
+            __heap_bucket_release(heap, bucket);
+            __heap_bucket_merge(heap, prev);
+            return;
+        }
+    }
+    /*Merge bucket with next*/
+    if(next != NULL) {
+        if(!HEAP_BUCKET_TAKEN(next)) {
+            bucket->sizetaken += next->sizetaken;
+            __heap_bucket_release(heap, next);
+            __heap_bucket_merge(heap, bucket);
+        }
+    }
+}
+
+void*
+heap_alloc(struct heap *heap, size_t size)
+{
+    struct bucket *bestfit = NULL;
+    size_t remaining = heap->size - heap->used;
+    if(size == 0) return NULL;
+
+    /*Check for room in heap*/
+    if(remaining < size) return NULL;
+
+    /*Resize to fit with granularity*/
+    size = ((size + (HEAP_ALLOC_GRAN - 1)) / HEAP_ALLOC_GRAN) * HEAP_ALLOC_GRAN;
+
+    bestfit = __heap_bucket_findbest(heap, size);
+    if(bestfit == NULL) {
+        if(!HEAP_BUCKET_TAKEN(heap->buckets_head)) {
+            /*Expand empty head to fit*/
+            heap->buckets_head->sizetaken = size;
+            bestfit = heap->buckets_head;
+        }else{
+            /*Append new bucket to list*/
+            bestfit = __heap_bucket_append(heap, heap->buckets_head, size);
+        }
+        if(bestfit == NULL) return NULL;    /*Heap ran out of space*/
+    }
+
+    /*Split bucket into perfectly sized piece*/
+    __heap_bucket_split(heap, bestfit, size);
+
+    bestfit->sizetaken |= 1;
+    return (void*)bestfit->address;
+}
+
+int
+heap_free(struct heap *heap, void *ptr)
+{
+    uintptr_t addr = (uintptr_t)ptr;
+    for(struct bucket *bucket = heap->buckets_tail;
+            bucket != NULL;
+            bucket = bucket->next)
+    {
+        if(bucket->address == addr) {
+            bucket->sizetaken &= ~1;
+            __heap_bucket_merge(heap, bucket);
+            return 0;
+        }
+    }
+    return -1;
+}
diff --git a/src/arch_x86/64/heap/heap.h b/src/arch_x86/64/heap/heap.h
new file mode 100644
index 0000000..5eed7e4
--- /dev/null
+++ b/src/arch_x86/64/heap/heap.h
@@ -0,0 +1,149 @@
+/**
+ * heap.h
+ * Copyright (c) 2021 Jon Santmyer <jon@jonsantmyer.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+/**
+ * File              : heap.h
+ * Author            : Jon Santmyer <jon@jonsantmyer.com>
+ * Date              : 10.12.2021
+ *
+ * A simple thread-unsafe double linked-list bucket heap allocator.
+ * Written for moderately fast variable size object allocations without
+ * external memory regions
+ * Heap object is expected to be allocated by the system
+ * Heap members (lists, buckets, crates) are stored in the heap memory region.
+ * Users are expected to write wrapper functions that handles errors and 
+ * provides a locking mechanism for threaded applications.
+ *
+ * Required functions and headers:
+ * stdint.h
+ *  uintptr_t, uintmax_t
+ * stddef.h
+ *  size_t
+ * string.h
+ *  memset 
+ *
+ * Lists are defined by the elements they contain: they are named thusly.
+ * The first element of the list is suffixed by _tail
+ * The last element of the list is suffixed by _head
+ *
+ * Crates are page-sized bucket containers allocated inside of heap memory
+ * designed to allow the heap to dynamically create and destroy buckets.
+ * The amount of buckets each crate can hold depends on the preset size defined
+ * in HEAP_CRATE_SIZE, calculated in HEAP_CRATE_BUCKETS.
+ * Crates are stored in the previous crate's reserved bucket, except for the
+ * initial crate, which stores itself.
+ * Crates are singly linked, with the head and tail stored in the heap
+ * data structure.
+ *
+ * Buckets hold information about which memory region it represents, it's 
+ * neighbors, and if it's been taken by an allocation.
+ * Buckets determine if they are taken by setting the first bit in the
+ * sizetaken field. 0 represents free, 1 represents taken.
+ * Buckets currently in-use by the heap are stored in the general
+ * buckets list, with buckets reserved for future allocations stored in
+ * the buckets_unused list.
+ *
+ * The heap datatype stores information about where allocations can take
+ * place, the buckets allocated, a list of crates, and a list of
+ * unused buckets.
+ * Unused buckets are taken when a bucket is split into two, or a bucket needs
+ * to be appended to the heap.
+ *
+ * When buckets assigned to an allocation are bigger than the needed size, the
+ * bucket is "split". the difference in sizes are stored, the bucket is
+ * resized to the requested size, and a new bucket is appended to the old
+ * bucket with the difference as it's size.
+ * When a bucket is freed, the bucket checks it's neighbors to see if it can be
+ * combined. If two adjacent buckets are not taken, they are "merged".
+ * both buckets' sizes are added into the left-most bucket, and the right-most
+ * bucket is released into the unused list.
+ * These actions are made to ensure that memory allocations are as compact
+ * as possible.
+ *
+ * When the unused list is empty and a bucket needs to be appended, the heap
+ * calls for a new crate to be created. The new crate occupies the reserved
+ * bucket of the head crate, and the bucket is pointed to the last address
+ * in the bucket list. The crates' buckets are initialized to link with
+ * eachother and are set as the head of the unused list.
+ */
+#ifndef JSH_HEAP_H
+#define JSH_HEAP_H 1
+
+#include <stdint.h>
+#include <stddef.h>
+
+//I want the crate to be loaded into the l1 cache
+#define HEAP_CRATE_SIZE       4096
+#define HEAP_BUCKET_SIZE      sizeof(struct bucket)
+#define HEAP_CRATE_BUCKETS    (((HEAP_CRATE_SIZE - sizeof(uintptr_t)) / HEAP_BUCKET_SIZE) - 1)
+
+#define HEAP_BUCKET_TAKEN(b)  (b->sizetaken & 1)
+#define HEAP_ALLOC_GRAN       sizeof(uintptr_t)
+
+struct bucket
+{
+    uintptr_t address;
+    uintmax_t sizetaken;
+    struct bucket *prev;
+    struct bucket *next;
+};
+
+struct crate
+{
+    struct bucket buckets[HEAP_CRATE_BUCKETS];
+    struct bucket reserved;
+    struct crate *next;
+};
+
+struct heap
+{
+    uintptr_t start;
+    size_t size;
+    size_t used;
+
+    struct crate *crates_tail;
+    struct crate *crates_head;
+    struct bucket *buckets_tail;
+    struct bucket *buckets_head;
+    struct bucket *buckets_unused_tail;
+};
+
+/*  Fills a heap datastructure with passed arguments and populates the first crate
+ *  If len is less than MODIT_HEAP_CRATE_SIZE, function fails
+ * */
+int heap_create(struct heap *heap, uintptr_t at, size_t len);
+
+/*  Expands the heap's allocation area. Does not support reallocations
+ * */
+void heap_resize(struct heap *heap, size_t newsize);
+
+/*  Allocates a block of memory atleast [size] bytes long in heap
+ * */
+void *heap_alloc(struct heap *heap, size_t size);
+
+/*  Frees the memory pointed at by [ptr] for later allocations.
+ *  Returns 0 if memory was found and freed
+ * */
+int heap_free(struct heap *heap, void *ptr);
+
+#endif
diff --git a/src/arch_x86/64/tlb/main.c b/src/arch_x86/64/tlb/main.c
index 71c46f1..4b64b2f 100644
--- a/src/arch_x86/64/tlb/main.c
+++ b/src/arch_x86/64/tlb/main.c
@@ -35,7 +35,7 @@ _interrupt_handler_pagefault(struct intregs *regs)
     uint64_t pa;
     asm volatile("movq %%cr2, %0": "=a"(pa));
 
-    //printk(KERNEL_INFO, "%X PF %X @ %X (%i)\n", vcr3, pa, regs->rip, regs->err);
+    printk(KERNEL_INFO, "%X PF %X @ %X (%i)\n", vcr3, pa, regs->rip, regs->err);
     uintptr_t l1 = VMM_PML1_INDEX(pa);
     uint64_t pg = pml1[l1];
     if(pg & (PAGE_OS_LAZY << 9)) {
diff --git a/src/arch_x86/common/acpi/madt.c b/src/arch_x86/common/acpi/madt.c
index 6f58990..abaf706 100644
--- a/src/arch_x86/common/acpi/madt.c
+++ b/src/arch_x86/common/acpi/madt.c
@@ -109,4 +109,6 @@ madt_parse(struct acpisdthdr *madthdr)
     lapic_registers = (uintptr_t)malloc(PAGE_SIZE);
     vmm_mappg(lapic_addr, lapic_registers, 0, 3);
     lapic_registers += (lapic_addr % 0x1000);
+
+    printk(KERNEL_INFO, "LAPIC %lX\n", lapic_registers);
 }
diff --git a/src/arch_x86/common/acpi/main.c b/src/arch_x86/common/acpi/main.c
index 0f4fce7..d221dbc 100644
--- a/src/arch_x86/common/acpi/main.c
+++ b/src/arch_x86/common/acpi/main.c
@@ -36,6 +36,8 @@ rsdp_find_rsdt(struct rsdp1 *rsdp)
 
     vmm_mappg(rsdtphys, rsdtaddr, 0, 3);
     rsdtaddr += (rsdtphys % PAGE_SIZE);
+    printk(KERNEL_INFO, "RSDT %lX\n", rsdtaddr);
+
     rsdt_parse(rsdp, (struct acpisdthdr*)rsdtaddr);
 }
 
diff --git a/src/arch_x86/common/acpi/rsdt.c b/src/arch_x86/common/acpi/rsdt.c
index 26ec2e3..6c918b3 100644
--- a/src/arch_x86/common/acpi/rsdt.c
+++ b/src/arch_x86/common/acpi/rsdt.c
@@ -13,7 +13,7 @@ rsdt_parse_table(struct acpisdthdr *table)
         madt_parse(table);
         return;
     }
-    //printk(KERNEL_WARN, "Unrecognized table %4s\n", table->sig);
+    printk(KERNEL_WARN, "Unrecognized table %4s\n", table->sig);
 }
 
 void
@@ -36,6 +36,7 @@ rsdt_parse(struct rsdp1 *rsdp, struct acpisdthdr *rsdthdr)
         for(size_t i = 0; i < (rsdt->header.len - sizeof(struct acpisdthdr)) / sizeof(uint32_t); i++) {
             pmptr_t table_phys = (pmptr_t)rsdt->sdtptrs[i];
             vmptr_t table_virt = (vmptr_t)malloc(PAGE_SIZE);
+            printk(KERNEL_INFO, "TAB %lX %lX\n", table_phys, table_virt);
             if(table_phys == 0) break;
             struct acpisdthdr *table = NULL;
             vmm_mappg(table_phys, table_virt, 0, 3);
diff --git a/src/arch_x86/common/panic/main.c b/src/arch_x86/common/panic/main.c
index de804b6..b0f5ff9 100644
--- a/src/arch_x86/common/panic/main.c
+++ b/src/arch_x86/common/panic/main.c
@@ -55,13 +55,12 @@ panic_except(struct intregs *regs, const char *exceptstr)
 #if defined(BITS_64)
     if(regs != NULL) {
         printf("ERR %i\n", regs->err);
-        printf("IP %l016X CTX %i\n", regs->rip, current_excontext->id);
+        printf("IP %l016X\n", regs->rip);
         printf("RAX %l016X RBX %l016X RCX %l016X\nRDX %l016X", regs->rax, regs->rbx, regs->rcx, regs->rdx);
         printf("RSI %l016X RDI %l016X\nRSP %l016X RBP %l016X", regs->rsi, regs->rdi, regs->sp, regs->rbp);
     }
 #else
 
 #endif
-    heap_print();
     panic_end();
 }