improved in-kernel alloc/dealloc. addded colorless logging and struggling with mouse and kb

11 files changed, 298 insertions, 83 deletions

diff --git a/Makefile b/Makefile
index b92c68f..9d9e40f 100644
--- a/Makefile
+++ b/Makefile
@@ -78,7 +78,7 @@ SOURCES+=$(wildcard ./fs/*.c)
 SOURCES+=$(wildcard ./driver/*.c)
 SOURCES+=$(wildcard ./terminal/*.c)
 SOURCES+=$(wildcard ./lib/*/*.c)
-SOURCES+=$(wildcard ./test/*.c)
+SOURCES+=$(wildcard ./testing/*.c)
 
 #derive kernel object files
 OBJECTS=$(patsubst %.c, %.o, $(SOURCES))
diff --git a/kernel/interrupts.c b/kernel/interrupts.c
index 9e12555..150a784 100644
--- a/kernel/interrupts.c
+++ b/kernel/interrupts.c
@@ -51,43 +51,57 @@ static void int_install_ir(int irq, uint16_t flags, uint16_t sel, void *addr)
  */
 uint32_t interrupt_handler(uint32_t esp, uint32_t irq)
 {
+    // pit timer at 1/25 sec.
     if(irq==INTERRUPT_PIT_TIMER)asm_pit_tick();  
 
-    // mouse and kb
-    if(irq==INTERRUPT_KEYBOARD || irq==INTERRUPT_MOUSE){
+    // kb
+    if(irq==INTERRUPT_KEYBOARD)
+    {
+	uint32_t in=x86_inb(0x60);
+    }
+
+    // mouse
+    if(irq==INTERRUPT_MOUSE)
+    {
 	uint32_t in=x86_inb(0x60);
+
+	/*
 	if(irq==INTERRUPT_KEYBOARD){
 	    keyboard_handle(in); // do this in separate thread via syscalls?
 	    task_wake_all();
 	}
+	*/
 	// TODO: mouse
 	
 	// test ipi
-	apic_ipi(2,0x81); // force cpu16 to autoschedule? just test
+	//apic_ipi(2,0x81); // force cpu16 to autoschedule? just test
 	//klog("0x60 in %d",in);
     }
 
     // 0x80 - a syscall is coming in
-    if(irq==INTERRUPT_SYSCALL){
-
+    if(irq==INTERRUPT_SYSCALL)
+    {
 	uint32_t *stack=esp;
 	uint32_t eax=stack[11];
 	uint32_t ebx=stack[8];
 	uint32_t ecx=stack[10];
 	uint32_t edx=stack[9];
 
-//	klog("syscall: %d (ebx=0x%08X,ecx=0x%08X,edx=0x%08X)",eax,ebx,ecx,edx);
-
 	task_syscall(eax,ebx,ecx,edx);
-	esp=scheduler_run(esp,2); // force scheduling of pid=2 (kernel worker)
+	esp=scheduler_run(esp,2);
     }
 
     // schedules on APIC timer 0x8C and IPI 0x81
-    if(irq==INTERRUPT_APIC_TIMER || irq==INTERRUPT_IPI)esp=scheduler_run(esp,-1); // autoschedule
+    if(irq==INTERRUPT_APIC_TIMER || irq==INTERRUPT_IPI)
+    {
+	esp=scheduler_run(esp,-1);
+    }
 
-    if(irq!=INTERRUPT_SYSCALL)apic_eoi(); // ack all except software syscalls
+    // ack all except software syscalls
+    if(irq!=INTERRUPT_SYSCALL)apic_eoi(); 
 
-    if(irq==255)kpanic("Spurious/Unknown Interrupt!?"); // default and spurious
+    // default and spurious
+    if(irq==255)kpanic("Spurious/Unknown Interrupt!?"); 
 
     return esp;
 }
diff --git a/kernel/kernel.c b/kernel/kernel.c
index 5caed04..ca82a5d 100644
--- a/kernel/kernel.c
+++ b/kernel/kernel.c
@@ -12,6 +12,7 @@
 #include "vmem.h"
 
 //-- clean below headers --//
+#include "testing/testing.h"
 #include "ext2.h"
 #include "apic.h"
 #include "kernel/scheduler.h"
@@ -48,6 +49,9 @@ void kernel_main(uint32_t eax,uint32_t ebx)
     klog("Version: git-commit: %s",GIT_REVISION);
     klog("======================================");
 
+    // -- UNIT TESTING -- //
+    testing_kmalloc();
+
     // -- DISABLE LEGACY PIC -- //
     klog("Remapping & Disabling Programmable Interrupt Controller (PIC) ...");
     fixme("io_wait & spurious interrupts");
diff --git a/kernel/kernel.h b/kernel/kernel.h
index 06f96e1..83d89b8 100644
--- a/kernel/kernel.h
+++ b/kernel/kernel.h
@@ -23,8 +23,10 @@ REFERENCES
 #define FOOLOS_CONFIG_H
 
 #define BIN_INIT "/bin/init"
-//#define FOOLOS_LOG_OFF
-#define FOOLOS_LOG_COLOR true
+
+//#define FOOLOS_UNIT_TESTING // Run Unit Tests
+//#define FOOLOS_LOG_OFF  // Turn off logging
+//#define FOOLOS_COLORLESS  // Turn off colors in log
 
 #define FIFO_MAX_RINGBUFFERS 20
 #define MAX_FIFOS 20
@@ -32,7 +34,9 @@ REFERENCES
 #define MAX_TASKS 10
 #define MEM_PRINT_MEMORYMAP
 
-#define KMALLOC_MEM_SIZE  1024*1024*8  // 8MB for in kernel-memory
+#define KMALLOC_MEM_SIZE    1024*1024*8  // 8MB for in kernel-memory
+#define KMALLOC_BLOCK_SIZE  1024*4     // 4096 per block
+
 #define NUMBER_SPINLOCKS 16
 #define SPINLOCK_LOG 0
 #define SPINLOCK_ALLOC 1
diff --git a/kernel/kmalloc.c b/kernel/kmalloc.c
index eb35a44..356aab0 100644
--- a/kernel/kmalloc.c
+++ b/kernel/kmalloc.c
@@ -1,61 +1,118 @@
 #include "kernel.h"
 #include "kmalloc.h"
+#include "spinlock.h"
 #include "log.h"
 
-#include "spinlock.h"
+#define BLOCKS KMALLOC_MEM_SIZE/KMALLOC_BLOCK_SIZE
 
-static uint8_t    data[KMALLOC_MEM_SIZE]; // bytes
+// this is in .bss so we can assume it was zeroed!
+static uint8_t    data[KMALLOC_MEM_SIZE] __attribute__((aligned (4096))); // bytes
+static uint8_t    map[BLOCKS];
+//
+static uint32_t   data_addr;
 
 static uint32_t   next;
 static uint32_t   first;
 static uint8_t    init=0;
 
+static uint32_t next_free(uint32_t start)
+{
+    for(int i=start;i<BLOCKS;i++)
+    {
+	if(!map[i])return i;
+	return next_free(i+map[i]); 
+    }
+    return BLOCKS; // out of mem
+}
+
+static uint32_t next_used(uint32_t start,uint32_t max)
+{
+    for(int i=start;i<BLOCKS;i++)
+    {
+	if(map[i])return i; 
+	//means i is free
+	if(i-start>=max)return i;
+    }
+    return BLOCKS; // all free
+}
+
+static uint32_t free_cont(uint32_t blocks)
+{
+    uint32_t pos=0;
+
+    while(1)
+    {
+	pos=next_free(pos);
+//	klog("next_free:%d",pos);
+	if(pos==BLOCKS)return BLOCKS; // out of mem
+	uint32_t end=next_used(pos,blocks);
+//	klog("next_used:%d",end);
+	if(end-pos>=blocks)return pos;
+//	klog("here we have only %d blocks but we need at least %d",end-pos+1,blocks);
+	pos=end;
+    }
+}
+
+static void mark_used(uint32_t start,uint32_t blocks)
+{
+    uint32_t b=blocks;
+    for(int i=start;i<start+blocks;i++)
+    {
+	if(map[i]!=0)kpanic("memory map corrupted?");
+	map[i]=b;
+	b--;
+    }
+}
+
+static void mark_free(uint32_t start,uint32_t blocks)
+{
+    if(map[start]!=blocks)
+    {
+	kpanic("mark_free(%d,%d),mem map corrupted at %d (value=%d)?",start,blocks,start,map[start]);
+    }
+
+    if(start!=0&&(map[start-1]!=1&&map[start-1]!=0))
+    {
+	kpanic("mem map corrupted one before %d (value=%d)?",start,map[start-1]);
+    }
+
+    map[start]=0;
+    if(blocks>1)mark_free(start+1,blocks-1);
+}
+
 // will be initialized on first call to kballoc() //
 static void kmallocinit()
 {
-    fixme("implement and USE! kfree");
     next=&(data[0]);
+    data_addr=next;
     first=next;
+    if(next%4096)kpanic("kmalloc data not aligned properly.");
 
-    //TODO: optionally tell gcc to align this itself.
-    if(next%4096) 
-    {
-        next+=4096; 
-        next/=4096;
-        next*=4096;
-    }
-    //
-
-    klog("kmalloc_init: 0x%08X",next);
+    klog("In-Kernel Block Memory Allocation Initialized at: 0x%08X (free: %d x 4096KB BLOCKS)",next,BLOCKS);
     init=1;
 }
 
 // kernel block memory allocation //
 uint32_t kballoc(uint32_t size)
 {
-    size*=4096;
+    if(size>255)kpanic("max supported size 255 blocks");
     
     spinlock_spin(SPINLOCK_ALLOC);
+    if(!init)kmallocinit();
 
-	if(!init)kmallocinit();
-
-	uint32_t old=next;
-	next+=size;
-
+    uint32_t blk=free_cont(size);
+    if(blk==BLOCKS)kpanic("out of mem");
+    mark_used(blk,size);
     spinlock_release(SPINLOCK_ALLOC);
 
-    if(next>=first+KMALLOC_MEM_SIZE)
-    {
-        kpanic("kballoc ran out of memory! maybe increase KMALLOC_MEM_SIZE in kmalloc.c?");
-    }
-
-//    klog("(%d) : 0x%08X (~%dKB left)",size,old,(KMALLOC_MEM_SIZE-next+first)/1024);
-    return old;
+    return data_addr+blk*4096;
 }
 
-//TODO: allow freeing memory!!
-uint32_t kbfree(uint32_t pos)
+void kbfree(uint32_t pos)
 {
-        kpanic("kbfree NOT IMPLEMENTED YET");
+    uint32_t blk=(pos-data_addr)/4096;
+    spinlock_spin(SPINLOCK_ALLOC);
+    klog("freeing %d blocks ad 0x%08X",map[blk],pos);
+    mark_free(blk,map[blk]);
+    spinlock_release(SPINLOCK_ALLOC);
 }
-
diff --git a/kernel/kmalloc.h b/kernel/kmalloc.h
index 6e7157a..c7900c5 100644
--- a/kernel/kmalloc.h
+++ b/kernel/kmalloc.h
@@ -1,14 +1,29 @@
-/* 
- * Kernel Block Memory Allocation
+/**
+ * @file
+ *
+ * In-Kernel Block Memory Allocation
+ * =================================
  *
  * The kernel reserves some memory for internal operation, since  malloc 
  * is not available.
+ *
+ * Threads
+ * -------
+ * kballoc() and kbfree() are protected with spinlocks so you can 
+ * call them simultanously, even from multiple cpus! 
+ *
+ * Todo
+ * ----
+ * zeroalloc, alloc bytes, realloc
+ *
  */
 
 #include <stdint.h>
 
-// Allocate size*4096 bytes and returns a 32-bit pointer
+/** Allocate size*4096 bytes and returns a 32-bit address
+ *  and 0 if fails.
+ * */
 uint32_t kballoc  (uint32_t size);
 
-// Free memory allocated before by supplying the address (TODO)
-uint32_t kbfree   (uint32_t addr);
+/** Free memory allocated before by supplying the address returned by kballoc */
+void kbfree   (uint32_t addr);
diff --git a/kernel/log.h b/kernel/log.h
index ba92788..74f8776 100644
--- a/kernel/log.h
+++ b/kernel/log.h
@@ -15,11 +15,31 @@ void log(bool color,char *module_name, int prio, char *format_string, ...);
 
 // __FUNCTION__ ?
 #ifndef FOOLOS_LOG_OFF
-#define kpanic(...) {log(FOOLOS_LOG_COLOR,__FILE__,0," \033[41;37m [KERNEL PANIC] \033[37;40m " __VA_ARGS__ ); while(1);}
-#define klog(...) log(FOOLOS_LOG_COLOR,__FILE__ ":" S2(__LINE__), 10,  __VA_ARGS__)
-#define fixme(...) log(FOOLOS_LOG_COLOR,__FILE__ ":" S2(__LINE__) , 10, " \033[46;37m [FIXME] \033[37;40m "__VA_ARGS__)
+
+#ifdef FOOLOS_COLORLESS
+#define FOOLOS_LOG_COLOR false
+#define LOG_LABEL_INFO  " [INFO]  "
+#define LOG_LABEL_PANIC " [PANIC] "
+#define LOG_LABEL_FIX   " [FIXME] "
+#define LOG_LABEL_TEST  " [TEST]  "
+#endif
+
+#ifndef FOOLOS_COLORLESS
+#define FOOLOS_LOG_COLOR true
+#define LOG_LABEL_INFO   " \033[46;37m [INFO]  \033[37;40m "
+#define LOG_LABEL_PANIC  " \033[41;37m [PANIC] \033[37;40m "
+#define LOG_LABEL_FIX    " \033[44;37m [FIXME] \033[37;40m "
+#define LOG_LABEL_TEST   " \033[42;37m [TEST]  \033[37;40m "
 #endif
 
+#define klog(...) log(FOOLOS_LOG_COLOR,__FILE__ ":" S2(__LINE__), 10,    LOG_LABEL_INFO  __VA_ARGS__)
+#define kpanic(...) {log(FOOLOS_LOG_COLOR,__FILE__ ":" S2(__LINE__) ,0,  LOG_LABEL_PANIC __VA_ARGS__ ); while(1);}
+#define fixme(...) log(FOOLOS_LOG_COLOR,__FILE__ ":" S2(__LINE__) , 10,  LOG_LABEL_FIX __VA_ARGS__)
+#define testlog(...) log(FOOLOS_LOG_COLOR,__FILE__ ":" S2(__LINE__) , 10,LOG_LABEL_TEST __VA_ARGS__)
+
+#endif
+
+
 #ifdef FOOLOS_LOG_OFF
 #define kpanic(...) {while(1);}
 #define klog(...) {}
diff --git a/kernel/ringbuffer.c b/kernel/ringbuffer.c
index fd87727..6700931 100644
--- a/kernel/ringbuffer.c
+++ b/kernel/ringbuffer.c
@@ -1,12 +1,6 @@
-
 #include "ringbuffer.h"
 #include "kmalloc.h"
 
-// TODO: this is disabled because a kb interrupt can occur anytime
-// and the kernel will need to access the ringbuffer while we are accessing!
-// DO WE need a spinlock in general? do not use a global one anyway!!!!
-//static int sl=9;
-
 ringbuffer ringbuffer_init(uint32_t size)
 {
     ringbuffer f;
@@ -17,13 +11,15 @@ ringbuffer ringbuffer_init(uint32_t size)
     return f;
 }
 
-bool ringbuffer_put(ringbuffer* f,uint8_t c)
+void ringbuffer_free(ringbuffer *f)
 {
-//    x86_cli();
+    kbfree(f->data);
+}
 
+bool ringbuffer_put(ringbuffer* f,uint8_t c)
+{
     if((f->back-1+f->size)%f->size==f->front)
     {
-//	x86_sti();
 	return false;
     }
 
@@ -31,32 +27,25 @@ bool ringbuffer_put(ringbuffer* f,uint8_t c)
     f->back--;
     f->back+=f->size;
     f->back%=f->size;
-
-//    x86_sti();
     return true;
 }
 
 bool ringbuffer_has(ringbuffer* f)
 {
-//    x86_cli();
     bool res=true;
 
     if(f->front==f->back)
 	res=false;
-
-//    x86_sti();
     return res;
 }
 
-uint8_t ringbuffer_get(ringbuffer* f) // non blocking . please check first
+uint8_t ringbuffer_get(ringbuffer* f)
 {
-//    x86_cli();
     char c;
 
     if(f->front==f->back)
     {
-//	x86_sti();
-	return ' ';
+	return 0;
     }
 
     c=f->data[f->front];
@@ -64,7 +53,5 @@ uint8_t ringbuffer_get(ringbuffer* f) // non blocking . please check first
     f->front--;
     f->front+=f->size;
     f->front%=f->size;
-
-  //  x86_sti();
     return c;
 }
diff --git a/kernel/ringbuffer.h b/kernel/ringbuffer.h
index bb2b875..1ec88c8 100644
--- a/kernel/ringbuffer.h
+++ b/kernel/ringbuffer.h
@@ -1,28 +1,56 @@
+/**
+ * @file
+ *
+ * FIFO Buffers
+ * ============
+ *
+ * Simple FIRST IN FIRST OUT
+ *
+ * Requires
+ * --------
+ * Requires kballoc/kbfree - block allocation
+ * 
+ * Thread
+ * ------
+ * This is __not__ threadsafe. It is your job to lock accesses to
+ * reads/writes.
+ *
+ * Todo
+ * ----
+ * provide soemthing to read large blocks faster?
+ */
+
 #ifndef RINGBUFFER_H
 #define RINGBUFFER_H
 
 #include <stdint.h>
 #include <stdbool.h>
 
-// Simple FIRST IN FIRST OUT
-// requires kballoc - block allocation
-
+/** Ringbuffer sturcutre */
 typedef volatile struct ringbuffer_struct
 {
     uint32_t size;
     uint32_t front;
     uint32_t back;
-
-    uint8_t *data;
-
+    uint8_t  *data;
 }ringbuffer;
 
-// create new fifo/ringbuffer of given size (in blocks)
+/** Create a new fifo/ringbuffer of given size (in blocks) */
 ringbuffer ringbuffer_init(uint32_t blocks); 
 
-// true on success
+/** Deallocate buffer */
+void ringbuffer_free(ringbuffer *f);
+
+/** Put one _char_ into buffer. Returns true on success (i.e. buffer not full) */
 bool	ringbuffer_put(ringbuffer*,uint8_t);
-uint8_t ringbuffer_get(ringbuffer*);	    // non-blocking please check first
-bool	ringbuffer_has(ringbuffer*);	    // check if somehting waiting?
+
+/** Get a single _char_ from the buffer,
+ *  Return value __0__ might indicate that the buffer is empty.
+ *  check with _ringbuffer_has()_ to be sure.
+ */
+uint8_t ringbuffer_get(ringbuffer*);
+
+/** Check if buffer is not empty */
+bool	ringbuffer_has(ringbuffer*);
 
 #endif
diff --git a/testing/testing.c b/testing/testing.c
new file mode 100644
index 0000000..fc95054
--- /dev/null
+++ b/testing/testing.c
@@ -0,0 +1,85 @@
+#include <stdint.h>
+#include "log.h"
+#include "kmalloc.h"
+
+void testing_kmalloc_alloc(uint32_t size)
+{
+    uint32_t addr=kballoc(size);
+    testlog("kballoc(%d) returned 0x%08x",size,addr);
+}
+
+void testing_kmalloc_alloc_free(uint32_t size)
+{
+    uint32_t addr=kballoc(size);
+    testlog("kballoc(%d) returned 0x%08x",size,addr);
+    kbfree(addr);
+    testlog("kbfree(0x%08X)",addr);
+}
+
+// only free even
+void testing_kmalloc_alloc_free_even(uint32_t size)
+{
+    uint32_t addr=kballoc(size);
+    testlog("kballoc(%d) returned 0x%08x",size,addr);
+    if(!(size%2))
+    {
+	kbfree(addr);
+	testlog("kbfree(0x%08X)",addr);
+    }
+}
+
+// only free first
+void testing_kmalloc_alloc_two_free_first(uint32_t size)
+{
+    uint32_t addr1=kballoc(size);
+    testlog("kballoc(%d) returned 0x%08x",size,addr1);
+
+    uint32_t addr2=kballoc(size);
+    testlog("kballoc(%d) returned 0x%08x",size,addr2);
+
+    kbfree(addr1);
+    testlog("kbfree(0x%08X)",addr1);
+}
+
+void testing_kmalloc()
+{
+    #ifndef FOOLOS_UNIT_TESTING
+    return;
+    #endif
+    fixme("[TESTING] Create multiple independent tests that start from scratch");
+    fixme("[TESTING] Check the test results automatically!");
+
+    testlog("= UNIT TESTING KMALLOC =");
+
+    testlog("* allocating blocks different sizes (1-10 blocks)");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc(i+1);
+
+    testlog("* allocating and freeing different sizes (1-10 blocks)");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc_free(i+1);
+
+    testlog("* allocating blocks different sizes (1-10 blocks)");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc(i+1);
+
+    testlog("* allocating and freeing odd sizes only (1-10 blocks)");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc_free_even(i+1);
+
+    testlog("* allocating two but freeing first only (1-10 blocks)");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc_two_free_first(i+1);
+
+    testlog("* allocating two but freeing first only (10-1 blocks)");
+    for(int i=9;i>=0;i--)testing_kmalloc_alloc_two_free_first(i+1);
+
+    testlog("* allocating blocks different sizes (1-10 blocks)");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc(i+1);
+
+    testlog("* allocating and freeing mega blocks");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc_two_free_first(255);
+
+    testlog("* allocating two but freeing first only (1-10 blocks)");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc_two_free_first(255-i);
+
+    testlog("* allocating two but freeing first only (1-10 blocks)");
+    for(int i=0;i<10;i++)testing_kmalloc_alloc_two_free_first(255-i);
+
+}
+
diff --git a/testing/testing.h b/testing/testing.h
new file mode 100644
index 0000000..bde0453
--- /dev/null
+++ b/testing/testing.h
@@ -0,0 +1 @@
+void testing_kmalloc();