add heap to mocksl; flatten app build space; add scheduler to init

20 files changed, 360 insertions, 20 deletions

diff --git a/Makefile b/Makefile
index 778b9ad..f9ee698 100644
--- a/Makefile
+++ b/Makefile
@@ -8,9 +8,7 @@ ARCH	?= x86
 BITS	?= 64
 TARCH	?= $(ARCH)_$(BITS)-pc-modit
 
-APPS	:= $(wildcard $(PWD)/app/$(ARCH)/$(BITS)/*)
-APPS	+= $(wildcard $(PWD)/app/$(ARCH)/common/*)
-APPS	+= $(wildcard $(PWD)/app/common/*)
+APPS	+= $(wildcard $(PWD)/app/*)
 
 DISK1	:= disk1.hdd
 ISO		:= moditslim.iso
diff --git a/app/x86/64/init/Makefile b/app/init/Makefile
index c5afb94..c5afb94 100644
--- a/app/x86/64/init/Makefile
+++ b/app/init/Makefile
diff --git a/app/x86/64/init/main.c b/app/init/main.c
index 141d13f..527a8a3 100644
--- a/app/x86/64/init/main.c
+++ b/app/init/main.c
@@ -1,23 +1,20 @@
+#include "scheduler.h"
 #include "sys/cid.h"
 #include "modit/syscall.h"
 
 DEFN_SYSCALL(print, SYSCALL_PRINT);
-
 void prints(const char *msg) {
     struct syscall_print_data data = { .msg = msg };
     _syscall_print(&data);
 }
 
-int main(int argc, char **argv)
+int 
+main(int argc, char **argv)
 {
     (void)argc;
     (void)argv;
 
-    cid_t forkid = fork();
-    if(forkid != 0) {
-        prints("Swapping to forked context\n");
-        swapto(forkid);
-    }else{
-        prints("Running in forked context\n");
-    }
+    scheduler_setup();
+
+    while(1);
 }
diff --git a/app/init/scheduler.c b/app/init/scheduler.c
new file mode 100644
index 0000000..f4f2f2c
--- /dev/null
+++ b/app/init/scheduler.c
@@ -0,0 +1,63 @@
+#include "scheduler.h"
+#include <stddef.h>
+#include <stdlib.h>
+#include "sys/cid.h"
+
+struct clnode { //Round list
+    struct clnode *next;
+    struct context *ctx;
+};
+
+struct clnode *context_tail = NULL;
+struct clnode *context_current = NULL;
+
+void
+scheduler_addctx(cid_t id, uint8_t p)
+{
+    struct clnode *node = malloc(sizeof(struct clnode));
+    struct context *ctx = malloc(sizeof(struct context));
+
+    ctx->cid = id;
+    ctx->priority = p;
+    ctx->scheduled = true;
+
+    node->ctx = ctx;
+    node->next = context_tail;
+    context_tail = node;
+}
+
+void
+scheduler_loop(void)
+{
+    settimer(20);
+    swapto(1);
+    while(1)
+    {
+        bool ready = false;
+        while(!ready) {
+            struct clnode *next = context_current->next;
+            if(next == 0) next = context_tail;
+            context_current = next;
+            if(context_current->ctx->scheduled == false) continue;
+            ready = true;
+        }
+        settimer(PROC_QUANTUM(context_current->ctx->priority));
+        swapto(context_current->ctx->cid);
+    }
+}
+
+void
+scheduler_setup(void)
+{
+    cid_t forked = fork();
+    if(forked != 0) {
+        swapto(forked);
+        return;
+    }
+
+    //Add init and scheduler to context list
+    scheduler_addctx(1, 1);
+
+    context_current = context_tail;
+    scheduler_loop();
+}
diff --git a/app/init/scheduler.h b/app/init/scheduler.h
new file mode 100644
index 0000000..d028fec
--- /dev/null
+++ b/app/init/scheduler.h
@@ -0,0 +1,24 @@
+#ifndef INIT_SCHEDULER_H
+#define INIT_SCHEDULER_H 1
+
+#define PROC_PRIORITY_MUL   10
+#define PROC_QUANTUM(l) ((l + 1) * PROC_PRIORITY_MUL)
+
+#include <stdbool.h>
+#include <stdint.h>
+#include "sys/cid.h"
+
+struct context
+{
+    cid_t cid;
+    
+    bool scheduled;
+    uint8_t priority;
+};
+
+void scheduler_addctx(cid_t id, uint8_t p);
+
+/* Assumes init is CID 1 */
+void scheduler_setup(void);
+
+#endif
diff --git a/app/x86/64/ld/Makefile b/app/ld/Makefile
index 3a755c2..3a755c2 100644
--- a/app/x86/64/ld/Makefile
+++ b/app/ld/Makefile
diff --git a/app/x86/64/ld/linker.ld b/app/ld/linker.ld
index ff107fb..ff107fb 100644
--- a/app/x86/64/ld/linker.ld
+++ b/app/ld/linker.ld
diff --git a/app/x86/64/ld/main.c b/app/ld/main.c
index 049a121..3cbb49d 100644
--- a/app/x86/64/ld/main.c
+++ b/app/ld/main.c
@@ -35,12 +35,21 @@ memcpy(void *restrict dest, const void *restrict src, size_t n)
     return dest;
 }
 
+void *
+memset(void *restrict dest, char b, size_t n)
+{
+    asm volatile("xchg %bx, %bx");
+    unsigned char *a = (unsigned char*)dest;
+    while(n-- > 0) *a++ = b;
+    return dest;
+}
+
 void
 elf_run(uintptr_t entry)
 {
     size_t argc = 0;
-    if(stack_data->argv != NULL)
-        while(stack_data->argv[argc++] != 0);
+    //if(stack_data->argv != NULL)
+    //    while(stack_data->argv[argc++] != 0);
 
     asm volatile("xchg %%bx, %%bx; \
                   movq %0, %%rdi; \
@@ -62,9 +71,10 @@ elf_parse_exec()
      for(size_t i = 0; i < header->e_phnum; i++) {
         struct elf64_program_header *phdr = &phdrs[i];
         if(phdr->p_type != ELF_PT_LOAD) continue;
-    
+   
         alloc(phdr->p_vaddr, phdr->p_memsz);
-        memcpy(phdr->p_vaddr, (void*)((uintptr_t)stack_data->data + phdr->p_offset), phdr->p_filesz);
+        memset((void*)(phdr->p_vaddr), 0, phdr->p_memsz);
+        memcpy((void*)(phdr->p_vaddr), (void*)((uintptr_t)stack_data->data + phdr->p_offset), phdr->p_filesz);
      }
 
     elf_run(header->e_entry);
@@ -88,6 +98,7 @@ main(struct stkpack *data)
     stack_data = data;
 
     struct elf64_header *header = (struct elf64_header*)stack_data->data;
+
     if(!ELF_HEADER_CHECK(header)) {
         prints("Passed file is not ELF\n");
         return -1;
@@ -108,6 +119,5 @@ main(struct stkpack *data)
         return -4;
     }
 
-    prints("Running ELF\n");
     return elf_parse();
 }
diff --git a/app/x86/64/ld/main.s b/app/ld/main.s
index 4721670..4721670 100644
--- a/app/x86/64/ld/main.s
+++ b/app/ld/main.s
diff --git a/kernel b/kernel
-Subproject 586790c63ad4537b39f849020d4c007e34874f3
+Subproject 216e17bebb84483c33b0de40ab05778eef58560
diff --git a/lib/mocksl/mocksl.c b/lib/mocksl/mocksl.c
index a474bd6..4da0ca1 100644
--- a/lib/mocksl/mocksl.c
+++ b/lib/mocksl/mocksl.c
@@ -1,6 +1,8 @@
 
+extern void __stdlib_heap_init();
+
 void
 __init_mocksl(void)
 {
-    
+    __stdlib_heap_init();   
 }
diff --git a/lib/mocksl/stdlib/heap.c b/lib/mocksl/stdlib/heap.c
new file mode 100644
index 0000000..56de88c
--- /dev/null
+++ b/lib/mocksl/stdlib/heap.c
@@ -0,0 +1,175 @@
+#include <stdlib.h>
+#include "sys/alloc.h"
+
+#include <stdint.h>
+
+struct bucket {
+    struct bucket *prev;
+    struct bucket *next;
+    uintptr_t addr;
+    size_t flags;
+};
+
+#define BUCKET_SIZE sizeof(struct bucket)
+#define BLOCK_SIZE    4096
+#define BLOCK_BUCKETS ((BLOCK_SIZE - sizeof(uintptr_t)) / BUCKET_SIZE)
+
+struct block {
+    struct block *next;
+    struct bucket buckets[BLOCK_BUCKETS];
+};
+
+static struct block *block_tail = NULL;
+static struct block *block_head = NULL;
+
+static struct bucket *bucket_tail = NULL;
+static struct bucket *bucket_head = NULL;
+
+static struct bucket *free_tail = NULL;
+
+static uintptr_t heapend;
+uintptr_t __pbrk;
+
+extern uintptr_t _end[];
+
+static void
+growbrk(size_t by)
+{
+    //Round to nearest granularity address
+    uintptr_t exp = (by + (HEAP_BUCKET_ALLOC_GRANULARITY - 1) / HEAP_BUCKET_ALLOC_GRANULARITY) * HEAP_BUCKET_ALLOC_GRANULARITY;
+    alloc(__pbrk, exp);
+    __pbrk += exp;
+}
+
+static void
+growto(uintptr_t addr) 
+{
+    if(addr > __pbrk) growbrk(addr - __pbrk);
+    heapend = addr;
+}
+
+static void
+growby(size_t by)
+{
+    growto(heapend + by);
+}
+
+static void
+heap_allocbucket(struct bucket *bucket, size_t size)
+{
+    bucket->addr = heapend;
+    bucket->flags = size;
+    growby(size);
+
+    //Add bucket to bucket list
+    if(bucket_head != NULL) {
+        bucket_head->next = bucket;
+        bucket->prev = bucket_head;
+    }
+    bucket->next = NULL;
+    bucket_head = bucket;
+}
+
+static void
+heap_allocblock(struct bucket *bucket)
+{
+    //Set bucket addr to heapend, expand heap to match
+    heap_allocbucket(bucket, BLOCK_SIZE);
+    bucket->flags |= 1;
+
+    //Add block to blocklist
+    block_head->next = (struct block*)bucket->addr;
+    block_head = (struct block*)bucket->addr;
+
+    //Add buckets to freelist
+    for(size_t i = 0; i < BLOCK_BUCKETS - 1; i++) {
+        block_head->buckets[i].next = &block_head->buckets[i+1];
+        block_head->buckets[i+1].prev = &block_head->buckets[i];
+    }
+    free_tail = &block_head->buckets[0];
+}
+
+static struct bucket*
+heap_takebucket(void)
+{
+    //Get free bucket
+    struct bucket *taken = free_tail;
+    
+    //Check if bucket is last in freelist, so there is always room for a new block
+    if(taken->next == NULL) {
+        //Allocate new block with free bucket
+        heap_allocblock(taken);
+    }
+
+    free_tail = taken->next;
+    free_tail->prev = NULL;
+    
+
+    return taken;
+}
+
+static struct bucket*
+heap_search(size_t size)
+{
+    struct bucket *best = NULL;
+    //Search through all allocated heap buckets
+    for(struct bucket *bucket = bucket_tail; bucket; bucket = bucket->next) {
+        if(bucket->flags & 1) continue; //Skip taken
+        if(bucket->flags < size) continue;  //Skip too small
+        if(best == NULL) {  //First best is the first that fits
+            best = bucket;
+        }else if(best->flags > bucket->flags) best = bucket;    //Total best is the smallest fit
+    }
+    return best;
+}
+
+void*
+malloc(size_t size)
+{
+    if(size == 0) return NULL;
+    size += (size % 2);
+    
+    //Search blocks for empty buckets matching size
+    struct bucket *bucket = heap_search(size);
+
+    //Resize top if none matching
+    if(bucket == NULL) {
+        if(!(bucket_head->flags & 1)) {
+            bucket = bucket_head;
+            bucket->flags = size;
+        }else{
+            //Allocate bucket if no valid target
+            bucket = heap_takebucket();
+            heap_allocbucket(bucket, size);
+        }
+    }
+    
+    //Claim bucket
+    bucket->flags |= 1;
+    return (void*)bucket->addr;
+}
+
+void
+__stdlib_heap_init(void)
+{
+    //Match pbrk to page boundary (so it's cleaner for granularity sake)
+    __pbrk = (uintptr_t)_end;
+    __pbrk = ((__pbrk + 0xFFF) / 0x1000) * 0x1000;
+    heapend = __pbrk;
+
+    block_head = block_tail = (struct block*)heapend;
+    growby(BLOCK_SIZE);
+    memset(block_tail, 0, BLOCK_SIZE);
+
+    //Link block buckets in freelist
+    for(size_t i = 1; i < BLOCK_BUCKETS - 1; i++) {
+        block_head->buckets[i].next = &block_head->buckets[i+1];
+        block_head->buckets[i+1].prev = &block_head->buckets[i];
+    }
+    free_tail = &block_head->buckets[1];
+    
+    //Set bucket 1 to root block
+    block_head->buckets[0].addr = (uintptr_t)block_head;
+    block_head->buckets[0].flags = BLOCK_SIZE | 1;
+    bucket_head = bucket_tail = &(block_head->buckets[0]);
+}
diff --git a/lib/mocksl/stdlib/memcpy.c b/lib/mocksl/stdlib/memcpy.c
new file mode 100644
index 0000000..877f51b
--- /dev/null
+++ b/lib/mocksl/stdlib/memcpy.c
@@ -0,0 +1,12 @@
+#include "stdlib.h"
+
+void*
+memcpy(void *d, const void *s, size_t n)
+{
+    unsigned char *a = (unsigned char*)d;
+    const unsigned char *b = (const unsigned char*)s;
+    while(n-- > 0) {
+        *a++ = *b++;
+    }
+    return d;
+}
diff --git a/lib/mocksl/stdlib/memset.c b/lib/mocksl/stdlib/memset.c
new file mode 100644
index 0000000..d0a7b5b
--- /dev/null
+++ b/lib/mocksl/stdlib/memset.c
@@ -0,0 +1,11 @@
+#include "stdlib.h"
+
+void*
+memset(void *s, int c, size_t n)
+{
+    unsigned char *a = (unsigned char*)s;
+    while(n-- > 0) {
+        *a++ = c;
+    }
+    return s;
+}
diff --git a/lib/mocksl/sys/alloc.c b/lib/mocksl/sys/alloc.c
new file mode 100644
index 0000000..4212026
--- /dev/null
+++ b/lib/mocksl/sys/alloc.c
@@ -0,0 +1,11 @@
+#include "sys/alloc.h"
+#include "modit/syscall.h"
+
+DEFN_SYSCALL(alloc, SYSCALL_ALLOC)
+
+void
+alloc(uintptr_t at, size_t size)
+{
+    struct syscall_alloc_data data = { .addr = at, .size = size };
+    _syscall_alloc(&data);
+}
diff --git a/lib/mocksl/sys/fork.c b/lib/mocksl/sys/fork.c
index a080b98..8e68051 100644
--- a/lib/mocksl/sys/fork.c
+++ b/lib/mocksl/sys/fork.c
@@ -1,11 +1,12 @@
 #include "modit/syscall.h"
 #include "sys/cid.h"
 
+#include <stddef.h>
+
 DEFN_SYSCALL(fork, SYSCALL_FORK)
 
 cid_t
 fork(void)
 {
-    struct syscall_fork_data data = { .np = false };
-    return _syscall_fork(&data);
+    return _syscall_fork(NULL);
 }
diff --git a/lib/mocksl/sys/settimer.c b/lib/mocksl/sys/settimer.c
new file mode 100644
index 0000000..5dbb853
--- /dev/null
+++ b/lib/mocksl/sys/settimer.c
@@ -0,0 +1,11 @@
+#include "sys/cid.h"
+#include "modit/syscall.h"
+
+DEFN_SYSCALL(timer, SYSCALL_TICK)
+
+void
+settimer(int ms)
+{
+    struct syscall_tick_data data = { .ms = ms };
+    _syscall_timer(&data);
+}
diff --git a/root/usr/include/stdlib.h b/root/usr/include/stdlib.h
index 9ddd3a3..7a90436 100644
--- a/root/usr/include/stdlib.h
+++ b/root/usr/include/stdlib.h
@@ -1,7 +1,22 @@
 #ifndef STDLIB_H
 #define STDLIB_H 1
 
+#include <stddef.h>
+#include <stdint.h>
 
+#define HEAP_BUCKET_ALLOC_GRANULARITY   0x4000
 
+extern uintptr_t __pbrk;
+
+void *memset(void *s, int c, size_t n);
+void *memcpy(void *d, const void *s, size_t n);
+
+void exit(int s);
+
+void *malloc(size_t size);
+void *calloc(size_t nmemb, size_t size);
+void *realloc(void *ptr, size_t size);
+
+void free(void *ptr);
 
 #endif
diff --git a/root/usr/include/sys/alloc.h b/root/usr/include/sys/alloc.h
new file mode 100644
index 0000000..a674196
--- /dev/null
+++ b/root/usr/include/sys/alloc.h
@@ -0,0 +1,9 @@
+#ifndef MOCKSL_SYS_ALLOC_H
+#define MOCKSL_SYS_ALLOC_H 1
+
+#include <stdint.h>
+#include <stddef.h>
+
+void alloc(uintptr_t at, size_t size);
+
+#endif
diff --git a/root/usr/include/sys/cid.h b/root/usr/include/sys/cid.h
index 954564f..7d45277 100644
--- a/root/usr/include/sys/cid.h
+++ b/root/usr/include/sys/cid.h
@@ -5,6 +5,7 @@ typedef int cid_t;
 
 cid_t fork(void);
 
+void settimer(int ms);
 int swapto(cid_t target);
 
 #endif