From 9c4310651a91e64c10a17f3190c895a49096aeb1 Mon Sep 17 00:00:00 2001 From: Alexis211 Date: Wed, 3 Feb 2010 15:22:30 +0100 Subject: Reogranization --- src/stem/mem/gdt.c | 36 ++++++++ src/stem/mem/gdt.h | 23 ++++++ src/stem/mem/heap.c | 224 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/stem/mem/heap.h | 27 ++++++ src/stem/mem/mem.c | 94 +++++++++++++++++++++ src/stem/mem/mem.h | 17 ++++ src/stem/mem/paging.c | 121 +++++++++++++++++++++++++++ src/stem/mem/paging.h | 42 ++++++++++ 8 files changed, 584 insertions(+) create mode 100644 src/stem/mem/gdt.c create mode 100644 src/stem/mem/gdt.h create mode 100644 src/stem/mem/heap.c create mode 100644 src/stem/mem/heap.h create mode 100644 src/stem/mem/mem.c create mode 100644 src/stem/mem/mem.h create mode 100644 src/stem/mem/paging.c create mode 100644 src/stem/mem/paging.h (limited to 'src/stem/mem') 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 +#include + +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 + +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 +#include +#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 + +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 +#include +#include +#include "mem.h" +#include + +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 +#include + +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 -- cgit v1.2.3