8 files changed, 584 insertions, 0 deletions

diff --git a/src/stem/mem/gdt.c b/src/stem/mem/gdt.c
new file mode 100644
index 0000000..5aaad41
--- /dev/null
+++ b/src/stem/mem/gdt.c
@@ -0,0 +1,36 @@
+#include "gdt.h"
+#include <stdlib.h>
+#include <core/monitor.h>
+
+extern void gdt_flush(uint32_t);	//ASM (idt_.asm)
+
+#define GDT_ENTRIES 5
+
+static struct gdt_entry gdt_entries[GDT_ENTRIES];
+static struct gdt_ptr gdt_ptr;
+
+static void gdt_setGate(int num, uint32_t base, uint32_t limit, uint8_t access, uint8_t gran) {
+	gdt_entries[num].base_low = (base & 0xFFFF);
+	gdt_entries[num].base_middle = (base >> 16) & 0xFF;
+	gdt_entries[num].base_high = (base >> 24) & 0xFF;
+
+	gdt_entries[num].limit_low = (limit & 0xFFFF);
+	gdt_entries[num].granularity = (limit >> 16) & 0x0F;
+	gdt_entries[num].granularity |= gran & 0xF0;
+	gdt_entries[num].access = access;
+}
+
+void gdt_init() {
+	gdt_ptr.limit = (sizeof(struct gdt_entry) * GDT_ENTRIES) - 1;
+	gdt_ptr.base = (uint32_t)&gdt_entries;
+
+	gdt_setGate(0, 0, 0, 0, 0);					//Null segment
+	gdt_setGate(1, 0, 0xFFFFFFFF, 0x9A, 0xCF);	//Kernel code segment
+	gdt_setGate(2, 0, 0xFFFFFFFF, 0x92, 0xCF);	//Kernel data segment
+	gdt_setGate(3, 0, 0xFFFFFFFF, 0xFA, 0xCF);	//User code segment
+	gdt_setGate(4, 0, 0xFFFFFFFF, 0xF2, 0xCF);	//User data segment
+
+	gdt_flush((uint32_t)&gdt_ptr);
+
+	monitor_write("GDT ok\n");
+}
diff --git a/src/stem/mem/gdt.h b/src/stem/mem/gdt.h
new file mode 100644
index 0000000..aac16bb
--- /dev/null
+++ b/src/stem/mem/gdt.h
@@ -0,0 +1,23 @@
+#ifndef DEF_GDT_H
+#define DEF_GDT_H
+
+#include <types.h>
+
+struct gdt_entry {
+	uint16_t limit_low;
+	uint16_t base_low;
+	uint8_t base_middle;
+	uint8_t access;
+	uint8_t granularity;
+	uint8_t base_high;
+} __attribute__((packed));
+
+struct gdt_ptr {
+	uint16_t limit;
+	uint32_t base;
+} __attribute__((packed));
+
+void gdt_init();
+
+#endif
+
diff --git a/src/stem/mem/heap.c b/src/stem/mem/heap.c
new file mode 100644
index 0000000..b6d2cd4
--- /dev/null
+++ b/src/stem/mem/heap.c
@@ -0,0 +1,224 @@
+#include "heap.h"
+#include "paging.h"
+
+#define HEAP_MAGIC 0xBAD0BEEF
+#define HEAP_MIN_SIZE 0x4000
+
+/* *******************			HEADER    	   ****************** */
+
+static void heapIdx_insert(struct heap *heap, struct heap_header *e) {
+	if ((heap->idxused + sizeof(struct heap_header*) + (size_t)heap->idx) >= heap->start_addr) return;
+
+	uint32_t iterator = 0, pos;
+	while (iterator < heap->idxused && heap->idx[iterator]->size < e->size) {
+		if (heap->idx[iterator] == e) return;
+		iterator++;
+	}
+	if (iterator == heap->idxused) {
+		heap->idx[heap->idxused++] = e;
+	} else {
+		pos = iterator;
+		iterator = heap->idxused;
+		while (iterator > pos) {
+			heap->idx[iterator] = heap->idx[iterator - 1];
+			iterator--;
+		}
+		heap->idxused++;
+		heap->idx[pos] = e;
+	}
+}
+
+static void heapIdx_remove(struct heap *heap, struct heap_header *e) {
+	uint32_t iterator;
+	for (iterator = 0; iterator < heap->idxused; iterator++) {
+		if (heap->idx[iterator] == e) break;
+	}
+	if (iterator == heap->idxused) return;
+	heap->idxused--;
+	while (iterator < heap->idxused) {
+		heap->idx[iterator] = heap->idx[iterator + 1];
+		iterator++;
+	}
+}
+
+/* ********************			CONTENTS		********************* */
+
+void heap_create(struct heap *heap, size_t start, size_t idxsize, size_t datasize, size_t maxdatasize) {
+	uint32_t i;
+
+	if (start & 0x0FFF) start = (start & 0xFFFFF000) + 0x1000;
+
+	heap->start_addr = start + idxsize;
+	heap->end_addr = start + idxsize + datasize;
+	heap->max_end = start + idxsize + maxdatasize;
+
+	for (i = start; i < heap->end_addr; i += 0x1000) {
+		page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0);
+	}
+
+	heap->idx = (struct heap_header**)start;	
+	heap->idxused = 0;
+
+	struct heap_header *hole = (struct heap_header*) heap->start_addr;
+	hole->size = (heap->end_addr - heap->start_addr);
+	hole->magic = HEAP_MAGIC;
+	hole->is_hole = 1;
+
+	struct heap_footer *hole_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer));
+	hole_footer->header = hole;
+	hole_footer->magic = HEAP_MAGIC;
+
+	heapIdx_insert(heap, hole);
+}
+
+static uint32_t heap_expand(struct heap *heap, size_t quantity) {
+	uint32_t i;
+
+	if (quantity & 0x0FFF) {
+		quantity = (quantity & 0xFFFFF000) + 0x1000;
+	}
+
+	if (heap->end_addr + quantity > heap->max_end) return 0;
+
+	size_t newEnd = heap->end_addr + quantity;
+
+	for (i = heap->end_addr; i < newEnd; i += 0x1000) {
+		page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0);
+	}
+
+	struct heap_footer *last_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer));
+	struct heap_header *last_header = last_footer->header;
+	if (last_header->is_hole) {
+		heapIdx_remove(heap, last_header);
+		last_header->size += quantity;
+
+		last_footer = (struct heap_footer*)(newEnd - sizeof(struct heap_footer));
+		last_footer->magic = HEAP_MAGIC;
+		last_footer->header = last_header;
+
+		heapIdx_insert(heap, last_header);
+	} else {
+		last_header = (struct heap_header*)heap->end_addr;
+		last_footer = (struct heap_footer*)(newEnd - sizeof(struct heap_footer));
+
+		last_header->is_hole = 1;
+		last_header->magic = HEAP_MAGIC;
+		last_header->size = quantity;
+
+		last_footer->magic = HEAP_MAGIC;
+		last_footer->header = last_header;
+
+		heapIdx_insert(heap, last_header);
+	}
+
+	heap->end_addr = newEnd;
+
+	return 1;
+}
+
+static void heap_contract(struct heap *heap) {
+	struct heap_footer *last_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer));
+	struct heap_header *last_header = last_footer->header;
+
+	if (last_header->is_hole == 0) return;
+
+	size_t quantity = 0;
+	while ((heap->end_addr - heap->start_addr) - quantity > HEAP_MIN_SIZE &&
+			(last_header->size - quantity) > 0x1000)
+		quantity += 0x1000;
+	if (quantity == 0) return;
+
+	size_t newEnd = heap->end_addr - quantity;
+
+	heapIdx_remove(heap, last_header);
+	last_header->size -= quantity;
+	last_footer = (struct heap_footer*)((size_t)last_footer - quantity);
+	last_footer->magic = HEAP_MAGIC;
+	last_footer->header = last_header;
+	heapIdx_insert(heap, last_header);
+
+	for (heap->end_addr -= 0x1000; heap->end_addr >= newEnd; heap->end_addr -= 0x1000) {
+		page_unmapFree(pagedir_getPage(kernel_pagedir, heap->end_addr, 0));
+	}
+}
+
+void* heap_alloc(struct heap *heap, size_t sz) {
+	size_t newsize = sz + sizeof(struct heap_header) + sizeof(struct heap_footer);
+	uint32_t iterator = 0;
+
+	while (iterator < heap->idxused) {
+		if (heap->idx[iterator]->size >= newsize) break;
+		iterator++;
+	}
+
+	if (iterator == heap->idxused) {	//No hole is big enough
+		if (heap_expand(heap, (sz & 0xFFFFF000) + 0x1000) == 0) return 0;	//FAILED
+		return heap_alloc(heap, sz);
+	}
+
+	struct heap_header *loc = heap->idx[iterator];
+	struct heap_footer *footer = (struct heap_footer*)((size_t)loc + loc->size - sizeof(struct heap_footer));
+	loc->is_hole = 0;
+	heapIdx_remove(heap, loc);
+	
+	//If we have enough space to create a USEFUL new hole next to the allocated block, do it.
+	//If we do not, we might return a block that is a few bytes bigger than neede.
+	if (loc->size > (newsize + sizeof(struct heap_header) + sizeof(struct heap_footer))) {
+		loc->size = newsize;
+
+		//Write footer for block we return
+		struct heap_footer *newfooter = (struct heap_footer*)((size_t)loc + newsize - sizeof(struct heap_footer));
+		newfooter->header = loc;
+		newfooter->magic = HEAP_MAGIC;
+
+		//Write header for new hole we create
+		struct heap_header *nextloc = (struct heap_header*)((size_t)loc + newsize);
+		nextloc->is_hole = 1;
+		nextloc->magic = HEAP_MAGIC;
+		nextloc->size = ((size_t)footer - (size_t)nextloc + sizeof(struct heap_footer));
+		footer->header = nextloc;	//Update footer
+		footer->magic = HEAP_MAGIC;
+
+		heapIdx_insert(heap, nextloc);
+	}
+
+	return (void*)((size_t)loc + sizeof(struct heap_header));
+}
+
+void heap_free(struct heap *heap, void* ptr) {
+	if (ptr == 0) return;
+	if ((size_t)ptr < heap->start_addr || (size_t)ptr > heap->end_addr) return;
+
+	struct heap_header *header = (struct heap_header*)((size_t)ptr - sizeof(struct heap_header));
+	struct heap_footer *footer = (struct heap_footer*)((size_t)header + header->size - sizeof(struct heap_footer));
+	if (header->magic != HEAP_MAGIC || footer->magic != HEAP_MAGIC) return;
+
+	//Unify left
+	struct heap_footer *prev_footer = (struct heap_footer*)((size_t)header - sizeof(struct heap_footer));
+	if (prev_footer->magic == HEAP_MAGIC && prev_footer->header->is_hole) {
+		header = prev_footer->header;
+		heapIdx_remove(heap, header);
+
+		footer->header = header;
+		header->size = ((size_t)footer - (size_t)header + sizeof(struct heap_footer));
+	}
+
+	//Unify right
+	struct heap_header *next_header = (struct heap_header*)((size_t)footer + sizeof(struct heap_footer));
+	if (next_header->magic == HEAP_MAGIC && next_header->is_hole) {
+		heapIdx_remove(heap, next_header);
+		footer = (struct heap_footer*)((size_t)footer + next_header->size);
+
+		footer->header = header;
+		header->size = ((size_t)footer - (size_t)header + sizeof(struct heap_footer));
+	}
+
+	header->is_hole = 1;
+
+	heapIdx_insert(heap, header);
+
+	if ((size_t)footer == (heap->end_addr - sizeof(struct heap_footer)) &&
+			header->size >= 0x2000 && (heap->end_addr - heap->start_addr > HEAP_MIN_SIZE)) {
+		heap_contract(heap);
+	}	
+}
diff --git a/src/stem/mem/heap.h b/src/stem/mem/heap.h
new file mode 100644
index 0000000..39ba37e
--- /dev/null
+++ b/src/stem/mem/heap.h
@@ -0,0 +1,27 @@
+#ifndef DEF_HEAP_H
+#define DEF_HEAP_H
+
+#include "types.h"
+
+struct heap_header {
+	uint32_t magic;
+	uint32_t is_hole;
+	size_t size;
+};
+
+struct heap_footer {
+	uint32_t magic;
+	struct heap_header *header;
+};
+
+struct heap {
+	struct heap_header **idx;
+	uint32_t idxused;
+	size_t start_addr, end_addr, max_end;
+};
+
+void heap_create(struct heap *heap, size_t start, size_t idxsize, size_t datasize, size_t maxdatasize);
+void* heap_alloc(struct heap *heap, size_t sz);
+void heap_free(struct heap *heap, void* ptr);
+
+#endif
diff --git a/src/stem/mem/mem.c b/src/stem/mem/mem.c
new file mode 100644
index 0000000..02b3ac5
--- /dev/null
+++ b/src/stem/mem/mem.c
@@ -0,0 +1,94 @@
+#include "mem.h"
+#include <core/sys.h>
+#include <core/monitor.h>
+#include "paging.h"
+#include "heap.h"
+
+#define FREEPAGESTOKEEP 5
+
+#define KHEAP_IDXSIZE 0x1000
+#define KHEAP_INITSIZE 0x8000
+#define KHEAP_MAXSIZE 0x08000000
+
+size_t mem_placementAddr;
+static uint32_t kheap_working = 0;
+
+
+// ******************************
+// 									PAGE ALLOCATION
+// 															****************************
+static struct freepage {
+   size_t virt, phys;
+} freepages[FREEPAGESTOKEEP];
+uint32_t freepagecount = 0;
+
+static void get_free_pages() {
+	static uint32_t locked = 0;
+	uint32_t i;
+	if (locked) return;
+	locked = 1;
+	while (freepagecount < FREEPAGESTOKEEP) {
+		if (kheap_working) {
+			for (i = 0xFFFFF000; i >= 0xF0000000; i -= 0x1000) {
+				if (pagedir_getPage(kernel_pagedir, i, 1)->frame == 0) break;
+			}
+			freepages[freepagecount].virt = i;
+			freepages[freepagecount].phys = frame_alloc() * 0x1000;
+			page_map(pagedir_getPage(kernel_pagedir, i, 0), i, 0, 0);
+		} else {
+			if (mem_placementAddr & 0xFFFFF000) {
+				mem_placementAddr &= 0xFFFFF000;
+				mem_placementAddr += 0x1000;
+			}
+			freepages[freepagecount].virt = (size_t)kmalloc(0x1000);
+			freepages[freepagecount].phys = freepages[freepagecount].virt - 0xE0000000;
+			freepagecount++;
+		}
+	}
+	locked = 0;
+}
+
+void* kmalloc_page(size_t *phys) {
+	cli();
+	get_free_pages();
+	freepagecount--;
+	*phys = freepages[freepagecount].phys;
+	size_t tmp = freepages[freepagecount].virt;
+	sti();
+	return (void*)tmp;
+}
+
+void kfree_page(void* ptr) {
+	size_t addr = (size_t)ptr;
+	if (kheap_working) {		//With this we can know if paging works
+		page_unmapFree(pagedir_getPage(kernel_pagedir, addr, 0));
+	}
+}
+
+//***********************************
+//										NORMAL MEMORY ALLOCATION
+//																	*************************
+
+static struct heap kheap;
+
+void kheap_init() {
+	heap_create(&kheap, (mem_placementAddr & 0xFFFFF000) + 0x1000, KHEAP_IDXSIZE, KHEAP_INITSIZE, KHEAP_MAXSIZE);
+	kheap_working = 1;
+	monitor_write("Kernel heap ok\n");
+}
+
+void* kmalloc(size_t size) {
+	if (kheap_working) {
+		return heap_alloc(&kheap, size);
+	} else {
+		size_t tmp = mem_placementAddr;
+		mem_placementAddr += size;
+		return (void*)tmp;
+	}
+}
+
+void kfree(void* ptr) {
+	if (kheap_working) {
+		heap_free(&kheap, ptr);
+	}
+}
diff --git a/src/stem/mem/mem.h b/src/stem/mem/mem.h
new file mode 100644
index 0000000..5417d5f
--- /dev/null
+++ b/src/stem/mem/mem.h
@@ -0,0 +1,17 @@
+#ifndef DEF_MEM_H
+#define DEF_MEM_H
+
+#include <types.h>
+
+void* kmalloc_page(size_t *phys);
+void kfree_page(void* page);
+void* kmalloc(size_t size);
+void kfree(void* ptr);
+
+void kheap_init();
+
+extern size_t mem_placementAddr;
+extern void end;	//Symbol defined by linker : end of kernel code
+
+#endif
+
diff --git a/src/stem/mem/paging.c b/src/stem/mem/paging.c
new file mode 100644
index 0000000..5ce3aae
--- /dev/null
+++ b/src/stem/mem/paging.c
@@ -0,0 +1,121 @@
+#include "paging.h"
+#include <bitset.h>
+#include <stdlib.h>
+#include <core/monitor.h>
+#include "mem.h"
+#include <core/sys.h>
+
+static struct bitset frames;
+
+struct page_directory *kernel_pagedir, *current_pagedir;
+
+/* ACCESSOR FUNCTIONS FOR STATIC BITSET */
+uint32_t frame_alloc() {
+	uint32_t free = bitset_firstFree(&frames);
+	bitset_set(&frames, free);
+	return free;
+}
+
+void frame_free(uint32_t id) {
+	bitset_clear(&frames, id);
+}
+
+
+void paging_init(size_t totalRam) {
+	uint32_t i;
+
+	frames.size = totalRam / 0x1000;
+	frames.bits = kmalloc(INDEX_FROM_BIT(frames.size));
+
+	kernel_pagedir = kmalloc(sizeof(struct page_directory));
+	kernel_pagedir->tablesPhysical = kmalloc_page(&kernel_pagedir->physicalAddr);
+	for (i = 0; i < 1024; i++) {
+		kernel_pagedir->tables[i] = 0;
+		kernel_pagedir->tablesPhysical[i] = 0;
+	}
+
+	for (i = 0xE0000000; i < mem_placementAddr; i += 0x1000) {
+		page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0);
+	}
+	for (i = 0; i < (mem_placementAddr - 0xE0000000) / 0x100000; i++) {
+		kernel_pagedir->tablesPhysical[i] = kernel_pagedir->tablesPhysical[i + 896];
+		kernel_pagedir->tables[i] = kernel_pagedir->tables[i + 896];
+	}
+
+	monitor_write("Page dir is at: ");
+	monitor_writeHex(kernel_pagedir->physicalAddr);
+	pagedir_switch(kernel_pagedir);
+	monitor_write("\nPaging started\n");
+}
+
+void paging_cleanup() {
+	uint32_t i;
+	for (i = 0; i < (mem_placementAddr - 0xE0000000) / 0x100000; i++) {
+		kernel_pagedir->tablesPhysical[i] = 9;
+		kernel_pagedir->tables[i] = 0;
+	}
+	monitor_write("Pages cleaned up\n");
+}
+
+void pagedir_switch(struct page_directory *pd) {
+	current_pagedir = pd;
+	asm volatile("mov %0, %%cr3" : : "r"(pd->physicalAddr));
+	uint32_t cr0;
+	asm volatile("mov %%cr0, %0" : "=r"(cr0));
+	cr0 |= 0x80000000;
+	asm volatile("mov %0, %%cr0" : : "r"(cr0));
+}
+
+uint32_t paging_fault(struct registers *regs) {
+	size_t addr;
+	asm volatile("mov %%cr2, %0" : "=r"(addr));
+	monitor_write("PageFault ");
+	if (regs->err_code & 0x1) monitor_write("present ");
+	if (regs->err_code & 0x2) monitor_write("write ");
+	if (regs->err_code & 0x4) monitor_write("user ");
+	if (regs->err_code & 0x8) monitor_write("rsvd ");
+	if (regs->err_code & 0x10) monitor_write("instructionfetch ");
+	monitor_write("@"); monitor_writeHex(addr); monitor_write("\n");
+	PANIC("Page fault");
+	return 0;
+}
+
+struct page *pagedir_getPage(struct page_directory *pd, uint32_t address, int make) {
+	address /= 0x1000;
+	uint32_t table_idx = address / 1024;
+
+	if (pd->tables[table_idx]) {
+		return &pd->tables[table_idx]->pages[address %  1024];
+	} else if (make) {
+		pd->tables[table_idx] = kmalloc_page(pd->tablesPhysical + table_idx);
+		memset((uint8_t*)pd->tables[table_idx], 0, 0x1000);
+		pd->tablesPhysical[table_idx] |= 0x07;
+		return &pd->tables[table_idx]->pages[address %  1024];
+	} else {
+		return 0;
+	}
+}
+
+void page_map(struct page *page, uint32_t frame, uint32_t user, uint32_t rw) {
+	if (page != 0 && page->frame == 0 && page->present == 0) {
+		page->present = 1;
+		page->rw = (rw ? 1 : 0);
+		page->user = (user ? 1 : 0);
+		page->frame = frame;
+	}
+}
+
+void page_unmap(struct page *page) {
+	if (page != 0) {
+		page->frame = 0;
+		page->present = 0;
+	}
+}
+
+void page_unmapFree(struct page *page) {
+	if (page != 0) {
+		if (page->frame != 0) frame_free(page->frame);
+		page->frame = 0;
+		page->present = 0;
+	}
+}
diff --git a/src/stem/mem/paging.h b/src/stem/mem/paging.h
new file mode 100644
index 0000000..72078cf
--- /dev/null
+++ b/src/stem/mem/paging.h
@@ -0,0 +1,42 @@
+#ifndef DEF_PAGING_H
+#define DEF_PAGING_H
+
+#include <types.h>
+#include <task/idt.h>
+
+struct page {
+	uint32_t present	: 1;	//Page mapped to a frame ?
+	uint32_t rw			: 1;	//Page read/write ?
+	uint32_t user		: 1;	//Page user readable ?
+	uint32_t accessed	: 1;	//Was page accessed ?
+	uint32_t dirty		: 1;	//Was page modified ?
+	uint32_t unused		: 7;
+	uint32_t frame		: 20;	//Frame address (physical address)
+};
+
+struct page_table {
+	struct page pages[1024];
+};
+
+struct page_directory {
+	struct page_table *tables[1024];	//Virtual addresses of page tables
+	uint32_t *tablesPhysical;			//Pointer to the virtual address of the page directory (contain phys addr of pt)
+	uint32_t physicalAddr;				//Physical address of info above
+};
+
+extern struct page_directory *kernel_pagedir;
+
+uint32_t frame_alloc();
+void frame_free(uint32_t id);
+
+void paging_init(size_t totalRam);
+void paging_cleanup();
+void pagedir_switch(struct page_directory *pd);
+struct page *pagedir_getPage(struct page_directory *pd, uint32_t address, int make);
+void page_map(struct page *page, uint32_t frame, uint32_t user, uint32_t rw);
+void page_unmap(struct page *page);
+void page_unmapFree(struct page *page);
+
+uint32_t paging_fault(struct registers *regs);	//returns a boolean
+
+#endif