diff options
author | Alexis211 <alexis211@gmail.com> | 2009-08-22 21:44:32 +0200 |
---|---|---|
committer | Alexis211 <alexis211@gmail.com> | 2009-08-22 21:44:32 +0200 |
commit | 2582a11c37ccc22d64974b20b0793e5ba873fe1f (patch) | |
tree | 485565c0950f0355290690d3396bcb4c22774fd0 /Source/Kernel/MemoryManager | |
parent | 74e721676ddd5d996ccf2e1d35da57320f658609 (diff) | |
download | Melon-2582a11c37ccc22d64974b20b0793e5ba873fe1f.tar.gz Melon-2582a11c37ccc22d64974b20b0793e5ba873fe1f.zip |
Lots of stuff added : heap, timer, device managment, ...
Diffstat (limited to 'Source/Kernel/MemoryManager')
-rw-r--r-- | Source/Kernel/MemoryManager/GDT.ns.cpp | 34 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/GDT.ns.h | 24 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/GDT.wtf.asm | 17 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/Mem.ns.cpp | 240 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/Mem.ns.h | 24 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/PageAlloc.ns.cpp | 68 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/PageAlloc.ns.h | 12 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/PageDirectory.class.cpp | 53 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/PageDirectory.class.h | 35 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/PhysMem.ns.cpp | 79 | ||||
-rw-r--r-- | Source/Kernel/MemoryManager/PhysMem.ns.h | 19 |
11 files changed, 602 insertions, 3 deletions
diff --git a/Source/Kernel/MemoryManager/GDT.ns.cpp b/Source/Kernel/MemoryManager/GDT.ns.cpp new file mode 100644 index 0000000..4fb9803 --- /dev/null +++ b/Source/Kernel/MemoryManager/GDT.ns.cpp @@ -0,0 +1,34 @@ +#include "GDT.ns.h" + +extern "C" void gdt_flush(u32int); + +namespace GDT { + +gdt_entry_t gdt_entries[5]; +gdt_ptr_t gdt_ptr; + +void setGate(s32int num, u32int base, u32int limit, u8int access, u8int 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 init() { + gdt_ptr.limit = (sizeof(gdt_entry_t) * 5) - 1; + gdt_ptr.base = (u32int)&gdt_entries; + + setGate(0, 0, 0, 0, 0); //Null segment + setGate(1, 0, 0xFFFFFFFF, 0x9A, 0xCF); //Kernel code segment + setGate(2, 0, 0xFFFFFFFF, 0x92, 0xCF); //Kernel data segment + setGate(3, 0, 0xFFFFFFFF, 0xFA, 0xCF); //User code segment + setGate(4, 0, 0xFFFFFFFF, 0xF2, 0xCF); //User data segment + + gdt_flush((u32int)&gdt_ptr); +} + +} diff --git a/Source/Kernel/MemoryManager/GDT.ns.h b/Source/Kernel/MemoryManager/GDT.ns.h new file mode 100644 index 0000000..7a9f95f --- /dev/null +++ b/Source/Kernel/MemoryManager/GDT.ns.h @@ -0,0 +1,24 @@ +#ifndef DEF_GDT_NS_H +#define DEF_GDT_NS_H + +#include <Core/common.wtf.h> + +namespace GDT { + struct gdt_entry_t { + u16int limit_low; + u16int base_low; + u8int base_middle; + u8int access; + u8int granularity; + u8int base_high; + } __attribute__((packed)); + + struct gdt_ptr_t { + u16int limit; + u32int base; + } __attribute__((packed)); + + void init(); +} + +#endif diff --git a/Source/Kernel/MemoryManager/GDT.wtf.asm b/Source/Kernel/MemoryManager/GDT.wtf.asm new file mode 100644 index 0000000..eb216ed --- /dev/null +++ b/Source/Kernel/MemoryManager/GDT.wtf.asm @@ -0,0 +1,17 @@ +[GLOBAL gdt_flush] + +gdt_flush: + mov eax, [esp+4] + lgdt [eax] + + mov ax, 0x10 + mov ds, ax + mov es, ax + mov fs, ax + mov gs, ax + mov ss, ax + jmp 0x08:.flush + +.flush: + ret + diff --git a/Source/Kernel/MemoryManager/Mem.ns.cpp b/Source/Kernel/MemoryManager/Mem.ns.cpp index d8bfc4f..832bd99 100644 --- a/Source/Kernel/MemoryManager/Mem.ns.cpp +++ b/Source/Kernel/MemoryManager/Mem.ns.cpp @@ -1,23 +1,259 @@ #include <Core/common.wtf.h> +#include <MemoryManager/PhysMem.ns.h> namespace Mem { -bool kheapUsable = false; +bool kheapUsable = false, pagingEnabled = false; u32int placementAddress, kheapFree; +heap_index_t heapIndex; +u32int heapStart, heapEnd; + +//Placement malloc, used while heap is not initialized void *kallocInternal(u32int sz, bool align) { + if (kheapUsable) return 0; if (align && (placementAddress & 0xFFFFF000)) { placementAddress &= 0xFFFFF000; placementAddress += 0x1000; } u32int temp = placementAddress; placementAddress += sz; + for (u32int i = temp; i < placementAddress; i += 0x1000) { + if (pagingEnabled) kernelPageDirectory->allocFrame(i, true, false); + } return (void*)temp; } +//*************************************************************************** +//*** HEAP INDEX FUNCTIONS *** +//*************************************************************************** +void insertIntoHeapIndex(heap_header_t *e) { + //If index is full, return + if ((heapIndex.size * sizeof(heap_header_t*) + (u32int)heapIndex.data) >= heapStart) return; + + u32int iterator = 0; + while (iterator < heapIndex.size && heapIndex.data[iterator]->size < e->size) { + if (heapIndex.data[iterator] == e) return; + iterator++; + } + if (iterator == heapIndex.size) { + heapIndex.data[heapIndex.size++] = e; + } else { + u32int pos = iterator; + iterator = heapIndex.size; + while (iterator > pos) { + heapIndex.data[iterator] = heapIndex.data[iterator - 1]; + iterator--; + } + heapIndex.size++; + heapIndex.data[pos] = e; + } +} + +u32int heapIndexFindEntry(heap_header_t *e) { + for (u32int i = 0; i < heapIndex.size; i++) { + if (heapIndex.data[i] == e) + return i; + } + return (u32int) - 1; +} + +void removeFromHeapIndex(u32int idx) { + heapIndex.size--; + while (idx < heapIndex.size) { + heapIndex.data[idx] = heapIndex.data[idx + 1]; + idx++; + } +} + +void removeFromHeapIndex(heap_header_t *e) { + u32int i = heapIndexFindEntry(e); + if (i != (u32int) - 1) { + removeFromHeapIndex(i); + } +} + +//*************************************************************************** +//*** MEMORY MANAGMENT FUNCTIONS *** +//*************************************************************************** +void createHeap() { + u32int heapIndexSize = PhysMem::total() * 64 + 0x10000; + heapStart = placementAddress + 0x10000; //Set initial heap start + heapEnd = heapStart + HEAP_MIN_SIZE + heapIndexSize; //Set heap end + + //Alocate frames for the heap + for (u32int i = placementAddress; i < heapEnd; i += 0x1000) { + kernelPageDirectory->allocFrame(i, true, false); + } + + heapIndex.data = (heap_header_t **)heapStart; //Set index start + heapIndex.size = 0; + heapStart += heapIndexSize; //Set some of available memory to be the index + + heap_header_t *hole = (heap_header_t*) heapStart; + hole->size = (heapEnd - heapStart); + hole->magic = HEAP_MAGIC; + hole->is_hole = true; + + heap_footer_t *hole_footer = (heap_footer_t*) (heapEnd - sizeof(heap_footer_t)); + hole_footer->header = hole; + hole_footer->magic = HEAP_MAGIC; + + insertIntoHeapIndex(hole); + + kheapUsable = true; + kheapFree = (heapEnd - heapStart); +} + +void expandHeap(u32int quantity) { + if (quantity & 0x00000FFF) + quantity = (quantity & 0xFFFFF000) + 0x1000; + + u32int newEnd = heapEnd + quantity; + + for (u32int i = heapEnd; i < newEnd; i++) { + kernelPageDirectory->allocFrame(i, true, false); + } + + heap_footer_t *last_footer = (heap_footer_t*) (heapEnd - sizeof(heap_footer_t)); + heap_header_t *last_header = last_footer->header; + if (last_header->is_hole) { //Last block of heap is a hole, update its size + removeFromHeapIndex(last_header); + last_header->size += quantity; + + last_footer = (heap_footer_t*) (newEnd - sizeof(heap_footer_t)); + + last_footer->magic = HEAP_MAGIC; + last_footer->header = last_header; + + insertIntoHeapIndex(last_header); + } else { //Last block is not a hole. Just add a new hole at the end + last_header = (heap_header_t*)heapEnd; + last_footer = (heap_footer_t*) (newEnd - sizeof(heap_footer_t)); + + last_header->is_hole = true; + last_header->magic = HEAP_MAGIC; + last_header->size = quantity; + + last_footer->magic = HEAP_MAGIC; + last_footer->header = last_header; + + insertIntoHeapIndex(last_header); + } + + heapEnd = newEnd; +} + +void contractHeap() { //Automatically work out how much we can contract + heap_footer_t *last_footer = (heap_footer_t*) (heapEnd - sizeof(heap_footer_t)); + heap_header_t *last_header = last_footer->header; + if (last_header->is_hole == false) return; //We need a hole at end of heap + + u32int quantity = 0; + while ((heapEnd - heapStart) - quantity > HEAP_MIN_SIZE and + (last_header->size - quantity) > 0x1000) //Always keep at least 0x1000 free at end + quantity += 0x1000; + if (quantity == 0) return; + + u32int newEnd = heapEnd - quantity; + + removeFromHeapIndex(last_header); + last_header->size -= quantity; + last_footer = (heap_footer_t*)((u32int)last_footer - quantity); + last_footer->magic = HEAP_MAGIC; + last_footer->header = last_header; + insertIntoHeapIndex(last_header); + + for (u32int i = newEnd; i < heapEnd; i += 0x1000) { + kernelPageDirectory->freeFrame(i); + } + + heapEnd = newEnd; +} + void *kalloc(u32int sz, bool align) { if (!kheapUsable) return kallocInternal(sz, align); - return 0; + if (align) return 0; + + u32int newsize = sz + sizeof(heap_header_t) + sizeof(heap_footer_t); + u32int iterator = 0; + while (iterator < heapIndex.size) { + if (heapIndex.data[iterator]->size >= newsize) break; + iterator++; + } + if (iterator == heapIndex.size) { //TODO : expand heap + expandHeap((sz & 0xFFFFF000) + 0x1000); + return kalloc(sz); //Recurse call + } + + heap_header_t *loc = heapIndex.data[iterator]; + heap_footer_t *footer = (heap_footer_t*)((u32int)loc + loc->size - sizeof(heap_footer_t)); + loc->is_hole = false; //Update current header + + removeFromHeapIndex(loc); + + + //Here we create a new hole after currently allocated block, but only if we have enough space. If we don't, we simply allocate a bigger block so that we don't loose space + if (loc->size > (newsize + sizeof(heap_header_t) + sizeof(heap_footer_t))) { + loc->size = newsize; //Update header for return block + + heap_footer_t *newfooter = (heap_footer_t*)((u32int)loc + newsize - sizeof(heap_footer_t)); //Write footer for return block + newfooter->header = loc; + newfooter->magic = HEAP_MAGIC; + + heap_header_t *nextloc = (heap_header_t*)((u32int)loc + newsize); //Write header for new hole + nextloc->is_hole = true; + nextloc->magic = HEAP_MAGIC; + nextloc->size = ((u32int)footer - (u32int)nextloc + sizeof(heap_footer_t)); + + footer->header = nextloc; //Write footer for new hole + footer->magic = HEAP_MAGIC; + + insertIntoHeapIndex(nextloc); + } + + kheapFree -= loc->size; + + return (void*)((u32int)loc + sizeof(heap_header_t)); +} + +void kfree(void *ptr) { //TODO + if (ptr == 0) return; + + heap_header_t *header = (heap_header_t*) ((u32int)ptr - sizeof(heap_header_t)); + heap_footer_t *footer = (heap_footer_t*)((u32int)header + header->size - sizeof(heap_footer_t)); + if (header->magic != HEAP_MAGIC or footer->magic != HEAP_MAGIC) return; + + kheapFree += header->size; + + //Unify left + heap_footer_t *prev_footer = (heap_footer_t*)((u32int)header - sizeof(heap_footer_t)); + if (prev_footer->magic == HEAP_MAGIC && prev_footer->header->is_hole) { + header = prev_footer->header; + removeFromHeapIndex(header); + + footer->header = header; + header->size = ((u32int)footer - (u32int)header + sizeof(heap_footer_t)); + } + + //Unify right + heap_header_t *next_header = (heap_header_t*)((u32int)footer + sizeof(heap_footer_t)); + if (next_header->magic == HEAP_MAGIC && next_header->is_hole) { + removeFromHeapIndex(next_header); + footer = (heap_footer_t*)((u32int)footer + next_header->size); + + footer->header = header; + header->size = ((u32int)footer - (u32int)header + sizeof(heap_footer_t)); + } + + header->is_hole = true; + + insertIntoHeapIndex(header); + + if ((u32int)footer == (heapEnd - sizeof(heap_footer_t)) and + header->size >= 0x2000 and (heapEnd - heapStart > HEAP_MIN_SIZE)) { + contractHeap(); + } } } diff --git a/Source/Kernel/MemoryManager/Mem.ns.h b/Source/Kernel/MemoryManager/Mem.ns.h index b3177a4..e208d65 100644 --- a/Source/Kernel/MemoryManager/Mem.ns.h +++ b/Source/Kernel/MemoryManager/Mem.ns.h @@ -3,12 +3,34 @@ #ifndef DEF_MEM_NS_H #define DEF_MEM_NS_H +//Heap minimum size : 2M +#define HEAP_MIN_SIZE 0x00200000 +//Heap magic number, for verifications +#define HEAP_MAGIC 0xBEEF1337 + namespace Mem { + extern bool pagingEnabled; extern u32int placementAddress, kheapFree; + struct heap_header_t { + u32int magic; + bool is_hole; + u32int size; + }; + + struct heap_footer_t { + u32int magic; + heap_header_t *header; + }; + + struct heap_index_t { + heap_header_t **data; + u32int size; + }; + + void createHeap(); void *kalloc(u32int sz, bool align = false); void kfree(void *ptr); - } #endif diff --git a/Source/Kernel/MemoryManager/PageAlloc.ns.cpp b/Source/Kernel/MemoryManager/PageAlloc.ns.cpp new file mode 100644 index 0000000..ac2969e --- /dev/null +++ b/Source/Kernel/MemoryManager/PageAlloc.ns.cpp @@ -0,0 +1,68 @@ +#include "PageAlloc.ns.h" +#include <MemoryManager/PhysMem.ns.h> + +#define CACHED_PAGES 3 + +// This mechanism is supposed to make it impossible to run out of free pages to use as a page table + +namespace PageAlloc { + +void* freePage[CACHED_PAGES]; +int freec = 0; +bool usable = false, locked = false; + +void init() { + freec = CACHED_PAGES; + for (u32int i = 0; i < CACHED_PAGES; i++) { + freePage[i] = Mem::kalloc(0x1000, true); + } + usable = true; +} + +void* alloc(u32int* phys) { + if (!usable) init(); + + while (freec < CACHED_PAGES && (!locked)) { + locked = true; + void* next = 0; + if (!Mem::pagingEnabled) { + next = Mem::kalloc(0x1000, true); + } else { + u32int i = 0xFFFFF000; + page_t *p; + while (1) { + p = kernelPageDirectory->getPage(i, true); + if (p->frame == 0) break; + i -= 0x1000; + } + PhysMem::allocFrame(p, true, false); + next = (void*)i; + } + freePage[freec] = next; + freec++; + locked = false; + } + + freec--; + void* ret = freePage[freec]; + if (!Mem::pagingEnabled) { + *phys = (u32int)ret - 0xC0000000; + } else { + page_t* p = kernelPageDirectory->getPage((u32int)ret, false); + if (p == 0) { //THIS SHOULD NEVER HAPPEN + PANIC("Cached free page does not exist."); + } else if (p->frame == 0) { + PANIC("Cached free page is not mapped to a frame."); + } else { + *phys = (p->frame * 0x1000); + } + } + return ret; +} + +void free(void *ptr) { + kernelPageDirectory->freeFrame((u32int)ptr); + return; +} + +} diff --git a/Source/Kernel/MemoryManager/PageAlloc.ns.h b/Source/Kernel/MemoryManager/PageAlloc.ns.h new file mode 100644 index 0000000..894defa --- /dev/null +++ b/Source/Kernel/MemoryManager/PageAlloc.ns.h @@ -0,0 +1,12 @@ +#ifndef DEF_PAGEALLOC_NS_H +#define DEF_PAGEALLOC_NS_H + +#include <Core/common.wtf.h> + +namespace PageAlloc { + void init(); + void* alloc(u32int* phys); + void free(void *ptr); +} + +#endif diff --git a/Source/Kernel/MemoryManager/PageDirectory.class.cpp b/Source/Kernel/MemoryManager/PageDirectory.class.cpp new file mode 100644 index 0000000..f48b0be --- /dev/null +++ b/Source/Kernel/MemoryManager/PageDirectory.class.cpp @@ -0,0 +1,53 @@ +#include "PageDirectory.class.h" +#include <MemoryManager/PhysMem.ns.h> +#include <MemoryManager/PageAlloc.ns.h> + +PageDirectory::PageDirectory() { + tablesPhysical = (u32int*)PageAlloc::alloc(&physicalAddr); + for (u32int i = 0; i < 1024; i++) { + tables[i] = 0; + tablesPhysical[i] = 0; + } +} + +PageDirectory::~PageDirectory() { + PageAlloc::free((void*)tablesPhysical); + for (int i = 0; i < 1024; i++) { + if (tables[i] != 0) PageAlloc::free((void*)tables[i]); + } +} + +page_t *PageDirectory::getPage(u32int address, bool make) { + address /= 0x1000; + u32int tableIdx = address / 1024; + if (tables[tableIdx] != 0) { + return &(tables[tableIdx]->pages[address % 1024]); + } else if (make) { + u32int tmp; + tables[tableIdx] = (page_table_t*)PageAlloc::alloc(&tmp); + CMem::memset((u8int*)tables[tableIdx], 0, 0x1000); + tablesPhysical[tableIdx] = tmp | 0x07; + return &(tables[tableIdx]->pages[address % 1024]); + } else { + return 0; + } +} + +void PageDirectory::allocFrame(u32int address, bool is_user, bool is_writable) { + page_t *p = getPage(address, true); + if (p != 0) PhysMem::allocFrame(p, is_user, is_writable); +} + +void PageDirectory::freeFrame(u32int address) { + page_t *p = getPage(address, false); + if (p == 0) return; + PhysMem::freeFrame(p); +} + +void PageDirectory::switchTo() { + asm volatile("mov %0, %%cr3" :: "r"(physicalAddr)); + u32int cr0; + asm volatile("mov %%cr0, %0" : "=r"(cr0)); + cr0 |= 0x80000000; + asm volatile("mov %0, %%cr0" :: "r"(cr0)); +} diff --git a/Source/Kernel/MemoryManager/PageDirectory.class.h b/Source/Kernel/MemoryManager/PageDirectory.class.h new file mode 100644 index 0000000..4591324 --- /dev/null +++ b/Source/Kernel/MemoryManager/PageDirectory.class.h @@ -0,0 +1,35 @@ +#ifndef DEF_PAGEDIRECTORY_CLASS_H +#define DEF_PAGEDIRECTORY_CLASS_H + +#include <Core/common.wtf.h> + +struct page_t { + u32int present : 1; + u32int rw : 1; + u32int user : 1; + u32int accessed : 1; + u32int dirty : 1; + u32int unused : 7; + u32int frame : 20; +}; + +struct page_table_t { + page_t pages[1024]; +}; + +struct PageDirectory { + page_table_t *tables[1024]; + u32int *tablesPhysical; + u32int physicalAddr; + + PageDirectory(); + ~PageDirectory(); + page_t *getPage(u32int address, bool make); + void allocFrame(u32int address, bool is_user, bool is_writable); + void freeFrame(u32int address); + void switchTo(); +}; + + + +#endif diff --git a/Source/Kernel/MemoryManager/PhysMem.ns.cpp b/Source/Kernel/MemoryManager/PhysMem.ns.cpp new file mode 100644 index 0000000..a9bfd35 --- /dev/null +++ b/Source/Kernel/MemoryManager/PhysMem.ns.cpp @@ -0,0 +1,79 @@ +#include "PhysMem.ns.h" +#include <Library/Bitset.class.h> +#include <VTManager/VirtualTerminal.class.h> + +PageDirectory* kernelPageDirectory; + +namespace PhysMem { + +u32int nframes; +Bitset *frames; + +void initPaging(u32int mem_size) { + nframes = mem_size / 0x1000; + + frames = new Bitset(nframes); + + kernelPageDirectory = new (Mem::kalloc(sizeof(PageDirectory), true)) PageDirectory(); + + u32int i = 0xC0000000; + while (i < Mem::placementAddress) { + page_t *p2 = kernelPageDirectory->getPage(i, true); + allocFrame(p2, true, false); + /* /DEBUG_HEX(i); DEBUG(" =>"); + DEBUG_HEX(p2->frame); DEBUG("."); */ + i += 0x1000; + } + //Also map thoses pages at begning of virtual memory + for (u32int i = 0; i < (Mem::placementAddress - 0xC0000000) / 0x100000; i++) { + kernelPageDirectory->tablesPhysical[i] = kernelPageDirectory->tablesPhysical[768 + i]; + kernelPageDirectory->tables[i] = kernelPageDirectory->tables[768 + i]; + } + DEBUG_HEX((u32int)kernelPageDirectory->physicalAddr); DEBUG(" is page dir phys addr."); + //asm volatile("hlt"); + + kernelPageDirectory->switchTo(); + DEBUG("Paging enabled !"); + + Mem::pagingEnabled = true; +} + +void removeTemporaryPages() { + for (u32int i = 0; i < (Mem::placementAddress - 0xC0000000) / 0x100000; i++) { + kernelPageDirectory->tablesPhysical[i] = 0; + kernelPageDirectory->tables[i] = 0; + } +} + +void allocFrame(page_t *page, bool is_user, bool is_writable) { + if (page->frame != 0) { + return; + } else { + u32int idx = frames->firstFreeBit(); + if (idx == (u32int) - 1) PANIC("No more free frames !"); + frames->setBit(idx); + page->present = 1; + page->user = (is_user ? 1 : 0); + page->rw = (is_writable ? 1 : 0); + page->frame = idx; + } +} + +void freeFrame(page_t *page) { + if (page->frame == 0) { + return; + } else { + frames->clearBit(page->frame / 0x1000); + page->frame = 0; + } +} + +u32int free() { + return nframes - frames->usedBits(); +} + +u32int total() { + return nframes; +} + +} diff --git a/Source/Kernel/MemoryManager/PhysMem.ns.h b/Source/Kernel/MemoryManager/PhysMem.ns.h new file mode 100644 index 0000000..258591a --- /dev/null +++ b/Source/Kernel/MemoryManager/PhysMem.ns.h @@ -0,0 +1,19 @@ +#ifndef DEF_PHYSMEM_NS_H +#define DEF_PHYSMEM_NS_H + +#include <MemoryManager/PageDirectory.class.h> + +extern PageDirectory* kernelPageDirectory; + +namespace PhysMem { + void initPaging(u32int mem_size); + void removeTemporaryPages(); + + void allocFrame(page_t *page, bool is_user, bool is_writable); + void freeFrame(page_t *page); + + u32int free(); + u32int total(); +} + +#endif |