From ccf807eb4ff541bb849c4f370d34123cb23d7d76 Mon Sep 17 00:00:00 2001 From: Alexis211 Date: Sun, 18 Oct 2009 18:39:52 +0200 Subject: Heap included as well in userland library --- Source/Applications/SampleApps/Makefile | 2 +- .../Kernel/Devices/Floppy/FloppyController.class.h | 2 +- Source/Kernel/Makefile | 7 +- Source/Kernel/MemoryManager/Heap-index.class.cpp | 51 ----- Source/Kernel/MemoryManager/Heap.class.cpp | 212 ------------------- Source/Kernel/MemoryManager/Heap.class.h | 79 ------- Source/Kernel/MemoryManager/Mem.ns.cpp | 2 +- Source/Kernel/TaskManager/Mutex.class.cpp | 28 --- Source/Kernel/TaskManager/Mutex.class.h | 21 -- Source/Kernel/TaskManager/Process.class.cpp | 9 + Source/Kernel/TaskManager/Process.class.h | 3 +- Source/Kernel/TaskManager/Task.wtf.asm | 7 - Source/Kernel/VTManager/VirtualTerminal.proto.h | 2 +- Source/Library/Common/Heap-index.class.cpp | 51 +++++ Source/Library/Common/Heap.class.cpp | 232 +++++++++++++++++++++ Source/Library/Common/Heap.class.h | 92 ++++++++ Source/Library/Common/Mutex.class.cpp | 45 ++++ Source/Library/Common/Mutex.class.h | 21 ++ Source/Library/Interface/Process.iface.h | 1 + Source/Library/Link.ld | 32 +++ Source/Library/Makefile | 12 +- Source/Library/Userland/Binding/Process.class.h | 3 + Source/Library/Userland/Start.cpp | 27 +++ Source/Library/Userland/common.h | 16 ++ 24 files changed, 550 insertions(+), 407 deletions(-) delete mode 100644 Source/Kernel/MemoryManager/Heap-index.class.cpp delete mode 100644 Source/Kernel/MemoryManager/Heap.class.cpp delete mode 100644 Source/Kernel/MemoryManager/Heap.class.h delete mode 100644 Source/Kernel/TaskManager/Mutex.class.cpp delete mode 100644 Source/Kernel/TaskManager/Mutex.class.h create mode 100644 Source/Library/Common/Heap-index.class.cpp create mode 100644 Source/Library/Common/Heap.class.cpp create mode 100644 Source/Library/Common/Heap.class.h create mode 100644 Source/Library/Common/Mutex.class.cpp create mode 100644 Source/Library/Common/Mutex.class.h create mode 100644 Source/Library/Link.ld (limited to 'Source') diff --git a/Source/Applications/SampleApps/Makefile b/Source/Applications/SampleApps/Makefile index d45011e..a632f87 100644 --- a/Source/Applications/SampleApps/Makefile +++ b/Source/Applications/SampleApps/Makefile @@ -7,7 +7,7 @@ CXX = g++ CXXFLAGS = -nostartfiles -nostdlib -fno-exceptions -fno-rtti -I ../../Library/Common -I ../../Library/Interface -I ../../Library/Userland -D THIS_IS_MELON_USERLAND LD = ld -LDFLAGS = --entry=start -Ttext=40000000 +LDFLAGS = -T ../../Library/Link.ld Applications = asmdemo cxxdemo diff --git a/Source/Kernel/Devices/Floppy/FloppyController.class.h b/Source/Kernel/Devices/Floppy/FloppyController.class.h index 2d0104b..a27d853 100644 --- a/Source/Kernel/Devices/Floppy/FloppyController.class.h +++ b/Source/Kernel/Devices/Floppy/FloppyController.class.h @@ -2,7 +2,7 @@ #define DEF_FLOPPYCONTROLLER_CLASS_H #include -#include +#include #define FLOPPY_DMALEN 0x4800 //This is one cylinder diff --git a/Source/Kernel/Makefile b/Source/Kernel/Makefile index a090ac6..1c83e5a 100644 --- a/Source/Kernel/Makefile +++ b/Source/Kernel/Makefile @@ -16,8 +16,6 @@ Objects = Core/loader.wtf.o \ Core/Sys.ns.o \ Core/Log.ns.o \ MemoryManager/Mem.ns.o \ - MemoryManager/Heap.class.o \ - MemoryManager/Heap-index.class.o \ MemoryManager/PhysMem.ns.o \ MemoryManager/GDT.wtf.o \ MemoryManager/GDT.ns.o \ @@ -31,7 +29,6 @@ Objects = Core/loader.wtf.o \ TaskManager/Thread.class.o \ TaskManager/Task.ns.o \ TaskManager/Task.wtf.o \ - TaskManager/Mutex.class.o \ VTManager/VirtualTerminal.proto.o \ VTManager/SimpleVT.class.o \ VTManager/ScrollableVT.class.o \ @@ -52,6 +49,9 @@ Objects = Core/loader.wtf.o \ ../Library/Common/WChar.class.o \ ../Library/Common/Rand.ns.o \ ../Library/Common/CMem.ns.o \ + ../Library/Common/Heap.class.o \ + ../Library/Common/Heap-index.class.o \ + ../Library/Common/Mutex.class.o \ VFS/Partition.class.o \ VFS/Part.ns.o \ VFS/VFS.ns.o \ @@ -95,6 +95,7 @@ clean: rm -rf *.o rm -rf */*.o rm -rf */*/*.o + rm -rf ../Library/Common/*.o mrproper: clean echo "* Removing executable : $(OutFile)" diff --git a/Source/Kernel/MemoryManager/Heap-index.class.cpp b/Source/Kernel/MemoryManager/Heap-index.class.cpp deleted file mode 100644 index 3280736..0000000 --- a/Source/Kernel/MemoryManager/Heap-index.class.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include "Heap.class.h" - -/* - * Implementation of the functions for managing heap index - */ - -void Heap::insertIntoIndex(heap_header_t *e) { - //If index is full, return - if ((m_index.size * sizeof(heap_header_t*) + (u32int)m_index.data) >= m_start) return; - - u32int iterator = 0; - while (iterator < m_index.size && m_index.data[iterator]->size < e->size) { - if (m_index.data[iterator] == e) return; - iterator++; - } - if (iterator == m_index.size) { - m_index.data[m_index.size++] = e; - } else { - u32int pos = iterator; - iterator = m_index.size; - while (iterator > pos) { - m_index.data[iterator] = m_index.data[iterator - 1]; - iterator--; - } - m_index.size++; - m_index.data[pos] = e; - } -} - -u32int Heap::findIndexEntry(heap_header_t *e) { - for (u32int i = 0; i < m_index.size; i++) { - if (m_index.data[i] == e) - return i; - } - return (u32int) - 1; -} - -void Heap::removeFromIndex(u32int idx) { - m_index.size--; - while (idx < m_index.size) { - m_index.data[idx] = m_index.data[idx + 1]; - idx++; - } -} - -void Heap::removeFromIndex(heap_header_t *e) { - u32int i = findIndexEntry(e); - if (i != (u32int) - 1) { - removeFromIndex(i); - } -} diff --git a/Source/Kernel/MemoryManager/Heap.class.cpp b/Source/Kernel/MemoryManager/Heap.class.cpp deleted file mode 100644 index 365b4f0..0000000 --- a/Source/Kernel/MemoryManager/Heap.class.cpp +++ /dev/null @@ -1,212 +0,0 @@ -#include "Heap.class.h" -#include - -Heap::Heap() : m_mutex(MUTEX_FALSE) { - m_usable = false; - m_index.data = 0; - m_index.size = 0; -} - -Heap::~Heap() { - //TODO (optionnal) : free pages. -} - -void Heap::create(u32int start, u32int size, u32int idxsize, PageDirectory* pagedir, bool user, bool rw) { - if (m_usable) return; - - if (start & 0x0FFF) start = (start & 0xFFFFF000) + 0x1000; - if (size & 0x0FFF) size = (size & 0xFFFFF000) + 0x1000; - m_start = start + idxsize; //m_start is start of real data, start is start of index. - m_end = start + size; - - m_pagedir = pagedir; - m_user = user; - m_rw = rw; - - //Allocate frames for heap - for (u32int i = start ; i < m_end; i += 0x1000) { - m_pagedir->allocFrame(i, m_user, m_rw); - } - m_pagedir->switchTo(); - - m_index.data = (heap_header_t **)start; //Set index start. start == start of all heap - m_index.size = 0; - - heap_header_t *hole = (heap_header_t*) m_start; //m_start == start of data - hole->size = (m_end - m_start); - hole->magic = HEAP_MAGIC; - hole->is_hole = true; - - heap_footer_t *hole_footer = (heap_footer_t*) (m_end - sizeof(heap_footer_t)); - hole_footer->header = hole; - hole_footer->magic = HEAP_MAGIC; - - insertIntoIndex(hole); - - m_usable = true; - m_free = (m_end - m_start); - - m_mutex.unlock(); -} - -void Heap::expand(u32int quantity) { - if (quantity & 0x00000FFF) - quantity = (quantity & 0xFFFFF000) + 0x1000; - - u32int newEnd = m_end + quantity; - - for (u32int i = m_end; i < newEnd; i++) { - m_pagedir->allocFrame(i, m_user, m_rw); - } - - heap_footer_t *last_footer = (heap_footer_t*) (m_end - 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 - removeFromIndex(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; - - insertIntoIndex(last_header); - } else { //Last block is not a hole. Just add a new hole at the end - last_header = (heap_header_t*)m_end; - 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; - - insertIntoIndex(last_header); - } - - m_end = newEnd; - m_free += quantity; -} - -void Heap::contract() { //Automatically work out how much we can contract - heap_footer_t *last_footer = (heap_footer_t*) (m_end - 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 ((m_end - m_start) - 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 = m_end - quantity; - m_free -= quantity; - - removeFromIndex(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; - insertIntoIndex(last_header); - - for (u32int i = newEnd; i < m_end; i += 0x1000) { - m_pagedir->freeFrame(i); - } - - m_end = newEnd; -} - -void *Heap::alloc(u32int sz, bool no_expand) { - m_mutex.waitLock(); - - u32int newsize = sz + sizeof(heap_header_t) + sizeof(heap_footer_t); - u32int iterator = 0; - while (iterator < m_index.size) { - if (m_index.data[iterator]->size >= newsize) break; - iterator++; - } - if (iterator == m_index.size) { //No hole is big enough - if (no_expand) { - m_mutex.unlock(); - return 0; - } - expand((sz & 0xFFFFF000) + 0x1000); - m_mutex.unlock(); - return alloc(sz, true); //Recurse call - } - - heap_header_t *loc = m_index.data[iterator]; - heap_footer_t *footer = (heap_footer_t*)((u32int)loc + loc->size - sizeof(heap_footer_t)); - loc->is_hole = false; //Update current header - - removeFromIndex(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; - - insertIntoIndex(nextloc); - } - - m_free -= loc->size; - - m_mutex.unlock(); - - return (void*)((u32int)loc + sizeof(heap_header_t)); -} - -void Heap::free(void *ptr) { - 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; - - m_mutex.waitLock(); - - m_free += 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; - removeFromIndex(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) { - removeFromIndex(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; - - insertIntoIndex(header); - - if ((u32int)footer == (m_end - sizeof(heap_footer_t)) and - header->size >= 0x2000 and (m_end - m_start > HEAP_MIN_SIZE)) { - contract(); - } - - m_mutex.unlock(); -} diff --git a/Source/Kernel/MemoryManager/Heap.class.h b/Source/Kernel/MemoryManager/Heap.class.h deleted file mode 100644 index 291c9ce..0000000 --- a/Source/Kernel/MemoryManager/Heap.class.h +++ /dev/null @@ -1,79 +0,0 @@ -#ifndef DEF_HEAP_CLASS_H -#define DEF_HEAP_CLASS_H - -#include -#include - -//Heap minimum size : 2M -#define HEAP_MIN_SIZE 0x00200000 -//Heap magic number, for verifications -#define HEAP_MAGIC 0xBEEF1337 - -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; -}; - -class PageDirectory; - -class Heap { - private: - bool m_usable, m_user, m_rw; - u32int m_free, m_start, m_end; - heap_index_t m_index; - PageDirectory* m_pagedir; - - Mutex m_mutex; - - void insertIntoIndex(heap_header_t *e); - u32int findIndexEntry(heap_header_t *e); - void removeFromIndex(u32int idx); - void removeFromIndex(heap_header_t *e); - - void expand(u32int quantity); - void contract(); //Quantity is automatically calculated - - public: - Heap(); - ~Heap(); - - void create(u32int start, u32int size, u32int idxsize, PageDirectory* pagedir, bool user, bool rw); - - void* alloc(u32int sz, bool no_expand = false); - void free(void* ptr); - - bool usable() { - m_mutex.waitLock(); - bool ret = m_usable; - m_mutex.unlock(); - return ret; - } - - u32int size() { - m_mutex.waitLock(); - u32int ret = m_end - m_start; - m_mutex.unlock(); - return ret; - } - - u32int free() { - m_mutex.waitLock(); - u32int ret = m_free; - m_mutex.unlock(); - return ret; - } -}; - - -#endif diff --git a/Source/Kernel/MemoryManager/Mem.ns.cpp b/Source/Kernel/MemoryManager/Mem.ns.cpp index 6c64a53..c705b3b 100644 --- a/Source/Kernel/MemoryManager/Mem.ns.cpp +++ b/Source/Kernel/MemoryManager/Mem.ns.cpp @@ -1,6 +1,6 @@ #include #include -#include +#include namespace Mem { diff --git a/Source/Kernel/TaskManager/Mutex.class.cpp b/Source/Kernel/TaskManager/Mutex.class.cpp deleted file mode 100644 index 8ba274f..0000000 --- a/Source/Kernel/TaskManager/Mutex.class.cpp +++ /dev/null @@ -1,28 +0,0 @@ -#include "Mutex.class.h" -#include - -extern "C" u32int atomic_exchange(u32int* ptr, u32int newval); - -Mutex::Mutex(u32int locked) { - m_locked = locked; -} - -bool Mutex::lock() { - if (atomic_exchange(&m_locked, MUTEX_TRUE) == MUTEX_TRUE) return false; //The lock was already locked - return true; -} - -void Mutex::waitLock() { - while (atomic_exchange(&m_locked, MUTEX_TRUE) == MUTEX_TRUE) { - if (Task::currThread() != 0) Task::currThread()->sleep(10); //Wait 10ms - else return; - } -} - -void Mutex::unlock() { - m_locked = MUTEX_FALSE; -} - -bool Mutex::locked() { - return m_locked; -} diff --git a/Source/Kernel/TaskManager/Mutex.class.h b/Source/Kernel/TaskManager/Mutex.class.h deleted file mode 100644 index 1e3f63d..0000000 --- a/Source/Kernel/TaskManager/Mutex.class.h +++ /dev/null @@ -1,21 +0,0 @@ -#ifndef DEF_MUTEX_CLASS_H -#define DEF_MUTEX_CLASS_H - -#include - -#define MUTEX_FALSE 0 -#define MUTEX_TRUE 1 - -class Mutex { - private: - u32int m_locked; - - public: - Mutex(u32int locked = MUTEX_FALSE); - bool lock(); //Locks the mutex if it is not locked. Returns true if mutex could be locked, false if already locked - void waitLock(); //Locks the mutex, waiting for it to be unlocked before if necessary - void unlock(); - bool locked(); -}; - -#endif diff --git a/Source/Kernel/TaskManager/Process.class.cpp b/Source/Kernel/TaskManager/Process.class.cpp index 39428b4..aae8fce 100644 --- a/Source/Kernel/TaskManager/Process.class.cpp +++ b/Source/Kernel/TaskManager/Process.class.cpp @@ -57,6 +57,7 @@ Process* Process::run(String filename, FSNode* cwd, u32int uid) { Process::Process(String cmdline, u32int uid) : Ressource(PR_IFACE_OBJTYPE) { addCall0(PR_IFACE_EXIT, (call0)&Process::exitSC); addCall1(PR_IFACE_ALLOCPAGE, (call1)&Process::allocPageSC); + addCall1(PR_IFACE_FREEPAGE, (call1)&Process::freePageSC); m_pid = Task::nextPid(); m_cmdline = cmdline; m_retval = 0; @@ -150,3 +151,11 @@ u32int Process::allocPageSC(u32int pos) { m_pagedir->allocFrame(pos, true, true); return 0; } + +u32int Process::freePageSC(u32int pos) { + if (Task::currProcess() != this) return 1; + if ((pos & 0x00000FFF) != 0) pos = (pos & 0xFFFFF000) + 0x1000; + if (pos >= 0xC0000000) return 1; + m_pagedir->freeFrame(pos); + return 0; +} diff --git a/Source/Kernel/TaskManager/Process.class.h b/Source/Kernel/TaskManager/Process.class.h index 1b614b7..afdfe20 100644 --- a/Source/Kernel/TaskManager/Process.class.h +++ b/Source/Kernel/TaskManager/Process.class.h @@ -5,7 +5,7 @@ #include #include #include -#include +#include #include #include @@ -72,6 +72,7 @@ class Process : public Ressource { //System calls u32int exitSC(); u32int allocPageSC(u32int); + u32int freePageSC(u32int); }; #endif diff --git a/Source/Kernel/TaskManager/Task.wtf.asm b/Source/Kernel/TaskManager/Task.wtf.asm index 36c1ade..9f27bec 100644 --- a/Source/Kernel/TaskManager/Task.wtf.asm +++ b/Source/Kernel/TaskManager/Task.wtf.asm @@ -9,13 +9,6 @@ idle_task: hlt jmp idle_task -[GLOBAL atomic_exchange] -atomic_exchange: - mov ecx, [esp+4] ; Get lock address - mov eax, [esp+8] ; Get new value - xchg eax, [ecx] ; Old value goes in eax - ret - [GLOBAL copy_page_physical] copy_page_physical: push ebx ; According to __cdecl, we must preserve the contents of EBX. diff --git a/Source/Kernel/VTManager/VirtualTerminal.proto.h b/Source/Kernel/VTManager/VirtualTerminal.proto.h index 487233d..b9d0eb8 100644 --- a/Source/Kernel/VTManager/VirtualTerminal.proto.h +++ b/Source/Kernel/VTManager/VirtualTerminal.proto.h @@ -3,7 +3,7 @@ #include #include -#include +#include #include #include diff --git a/Source/Library/Common/Heap-index.class.cpp b/Source/Library/Common/Heap-index.class.cpp new file mode 100644 index 0000000..3280736 --- /dev/null +++ b/Source/Library/Common/Heap-index.class.cpp @@ -0,0 +1,51 @@ +#include "Heap.class.h" + +/* + * Implementation of the functions for managing heap index + */ + +void Heap::insertIntoIndex(heap_header_t *e) { + //If index is full, return + if ((m_index.size * sizeof(heap_header_t*) + (u32int)m_index.data) >= m_start) return; + + u32int iterator = 0; + while (iterator < m_index.size && m_index.data[iterator]->size < e->size) { + if (m_index.data[iterator] == e) return; + iterator++; + } + if (iterator == m_index.size) { + m_index.data[m_index.size++] = e; + } else { + u32int pos = iterator; + iterator = m_index.size; + while (iterator > pos) { + m_index.data[iterator] = m_index.data[iterator - 1]; + iterator--; + } + m_index.size++; + m_index.data[pos] = e; + } +} + +u32int Heap::findIndexEntry(heap_header_t *e) { + for (u32int i = 0; i < m_index.size; i++) { + if (m_index.data[i] == e) + return i; + } + return (u32int) - 1; +} + +void Heap::removeFromIndex(u32int idx) { + m_index.size--; + while (idx < m_index.size) { + m_index.data[idx] = m_index.data[idx + 1]; + idx++; + } +} + +void Heap::removeFromIndex(heap_header_t *e) { + u32int i = findIndexEntry(e); + if (i != (u32int) - 1) { + removeFromIndex(i); + } +} diff --git a/Source/Library/Common/Heap.class.cpp b/Source/Library/Common/Heap.class.cpp new file mode 100644 index 0000000..34e4dc4 --- /dev/null +++ b/Source/Library/Common/Heap.class.cpp @@ -0,0 +1,232 @@ +#include "Heap.class.h" + +#ifdef THIS_IS_MELON_KERNEL +#include +#define ALLOC(x) m_pagedir->allocFrame(x, m_user, m_rw) +#define FREE(x) m_pagedir->freeFrame(x) +#else +#define ALLOC(x) m_process.allocPage(x) +#define FREE(x) m_process.freePage(x) +#endif + +#ifdef THIS_IS_MELON_KERNEL +Heap::Heap() : m_mutex(MUTEX_FALSE) { +#else +Heap::Heap() : m_mutex(MUTEX_FALSE), m_process(Process::get()) { +#endif + m_usable = false; + m_index.data = 0; + m_index.size = 0; +} + +Heap::~Heap() { + //TODO (optionnal) : free pages. +} + +#ifdef THIS_IS_MELON_KERNEL +void Heap::create(u32int start, u32int size, u32int idxsize, PageDirectory* pagedir, bool user, bool rw) { +#else +void Heap::create(u32int start, u32int size, u32int idxsize) { +#endif + if (m_usable) return; + + if (start & 0x0FFF) start = (start & 0xFFFFF000) + 0x1000; + if (size & 0x0FFF) size = (size & 0xFFFFF000) + 0x1000; + m_start = start + idxsize; //m_start is start of real data, start is start of index. + m_end = start + size; + +#ifdef THIS_IS_MELON_KERNEL + m_pagedir = pagedir; + m_user = user; + m_rw = rw; +#endif + + //Allocate frames for heap + for (u32int i = start ; i < m_end; i += 0x1000) { + ALLOC(i); + } +#ifdef THIS_IS_MELON_KERNEL + m_pagedir->switchTo(); +#endif + + m_index.data = (heap_header_t **)start; //Set index start. start == start of all heap + m_index.size = 0; + + heap_header_t *hole = (heap_header_t*) m_start; //m_start == start of data + hole->size = (m_end - m_start); + hole->magic = HEAP_MAGIC; + hole->is_hole = true; + + heap_footer_t *hole_footer = (heap_footer_t*) (m_end - sizeof(heap_footer_t)); + hole_footer->header = hole; + hole_footer->magic = HEAP_MAGIC; + + insertIntoIndex(hole); + + m_usable = true; + m_free = (m_end - m_start); + + m_mutex.unlock(); +} + +void Heap::expand(u32int quantity) { + if (quantity & 0x00000FFF) + quantity = (quantity & 0xFFFFF000) + 0x1000; + + u32int newEnd = m_end + quantity; + + for (u32int i = m_end; i < newEnd; i++) { + ALLOC(i); + } + + heap_footer_t *last_footer = (heap_footer_t*) (m_end - 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 + removeFromIndex(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; + + insertIntoIndex(last_header); + } else { //Last block is not a hole. Just add a new hole at the end + last_header = (heap_header_t*)m_end; + 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; + + insertIntoIndex(last_header); + } + + m_end = newEnd; + m_free += quantity; +} + +void Heap::contract() { //Automatically work out how much we can contract + heap_footer_t *last_footer = (heap_footer_t*) (m_end - 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 ((m_end - m_start) - 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 = m_end - quantity; + m_free -= quantity; + + removeFromIndex(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; + insertIntoIndex(last_header); + + for (u32int i = newEnd; i < m_end; i += 0x1000) { + FREE(i); + } + + m_end = newEnd; +} + +void *Heap::alloc(u32int sz, bool no_expand) { + m_mutex.waitLock(); + + u32int newsize = sz + sizeof(heap_header_t) + sizeof(heap_footer_t); + u32int iterator = 0; + while (iterator < m_index.size) { + if (m_index.data[iterator]->size >= newsize) break; + iterator++; + } + if (iterator == m_index.size) { //No hole is big enough + if (no_expand) { + m_mutex.unlock(); + return 0; + } + expand((sz & 0xFFFFF000) + 0x1000); + m_mutex.unlock(); + return alloc(sz, true); //Recurse call + } + + heap_header_t *loc = m_index.data[iterator]; + heap_footer_t *footer = (heap_footer_t*)((u32int)loc + loc->size - sizeof(heap_footer_t)); + loc->is_hole = false; //Update current header + + removeFromIndex(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; + + insertIntoIndex(nextloc); + } + + m_free -= loc->size; + + m_mutex.unlock(); + + return (void*)((u32int)loc + sizeof(heap_header_t)); +} + +void Heap::free(void *ptr) { + 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; + + m_mutex.waitLock(); + + m_free += 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; + removeFromIndex(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) { + removeFromIndex(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; + + insertIntoIndex(header); + + if ((u32int)footer == (m_end - sizeof(heap_footer_t)) and + header->size >= 0x2000 and (m_end - m_start > HEAP_MIN_SIZE)) { + contract(); + } + + m_mutex.unlock(); +} diff --git a/Source/Library/Common/Heap.class.h b/Source/Library/Common/Heap.class.h new file mode 100644 index 0000000..f5895c7 --- /dev/null +++ b/Source/Library/Common/Heap.class.h @@ -0,0 +1,92 @@ +#ifndef DEF_HEAP_CLASS_H +#define DEF_HEAP_CLASS_H + +#include +#include + +//Heap minimum size : 2M +#define HEAP_MIN_SIZE 0x00200000 +//Heap magic number, for verifications +#define HEAP_MAGIC 0xBEEF1337 + +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; +}; + +#ifdef THIS_IS_MELON_KERNEL +class PageDirectory; +#else +#include +#endif + +class Heap { + private: + u32int m_free, m_start, m_end; + bool m_usable; + heap_index_t m_index; +#ifdef THIS_IS_MELON_KERNEL + bool m_user, m_rw; + PageDirectory* m_pagedir; +#else + Process m_process; +#endif + + Mutex m_mutex; + + void insertIntoIndex(heap_header_t *e); + u32int findIndexEntry(heap_header_t *e); + void removeFromIndex(u32int idx); + void removeFromIndex(heap_header_t *e); + + void expand(u32int quantity); + void contract(); //Quantity is automatically calculated + + public: + Heap(); + ~Heap(); + +#ifdef THIS_IS_MELON_KERNEL + void create(u32int start, u32int size, u32int idxsize, PageDirectory* pagedir, bool user, bool rw); +#else + void create(u32int start, u32int size, u32int idxsize); +#endif + + void* alloc(u32int sz, bool no_expand = false); + void free(void* ptr); + + bool usable() { + m_mutex.waitLock(); + bool ret = m_usable; + m_mutex.unlock(); + return ret; + } + + u32int size() { + m_mutex.waitLock(); + u32int ret = m_end - m_start; + m_mutex.unlock(); + return ret; + } + + u32int free() { + m_mutex.waitLock(); + u32int ret = m_free; + m_mutex.unlock(); + return ret; + } +}; + + +#endif diff --git a/Source/Library/Common/Mutex.class.cpp b/Source/Library/Common/Mutex.class.cpp new file mode 100644 index 0000000..2e9a63c --- /dev/null +++ b/Source/Library/Common/Mutex.class.cpp @@ -0,0 +1,45 @@ +#include "Mutex.class.h" + +#ifdef THIS_IS_MELON_KERNEL +#include +#endif + +#ifdef THIS_IS_MELON_USERLAND +#include +#endif + +u32int atomic_exchange(u32int* ptr, u32int newval) { + u32int r; + asm volatile("xchg (%%ecx), %%eax" : "=a"(r) : "c"(ptr), "a"(newval)); + return r; +} + +Mutex::Mutex(u32int locked) { + m_locked = locked; +} + +bool Mutex::lock() { + if (atomic_exchange(&m_locked, MUTEX_TRUE) == MUTEX_TRUE) return false; //The lock was already locked + return true; +} + +void Mutex::waitLock() { + while (atomic_exchange(&m_locked, MUTEX_TRUE) == MUTEX_TRUE) { +#ifdef THIS_IS_MELON_KERNEL + if (Task::currThread() != 0) Task::currThread()->sleep(10); //Wait 10ms + else return; +#endif + +#ifdef THIS_IS_MELON_USERLAND + Thread::get().sleep(10); +#endif + } +} + +void Mutex::unlock() { + m_locked = MUTEX_FALSE; +} + +bool Mutex::locked() { + return m_locked; +} diff --git a/Source/Library/Common/Mutex.class.h b/Source/Library/Common/Mutex.class.h new file mode 100644 index 0000000..1e3f63d --- /dev/null +++ b/Source/Library/Common/Mutex.class.h @@ -0,0 +1,21 @@ +#ifndef DEF_MUTEX_CLASS_H +#define DEF_MUTEX_CLASS_H + +#include + +#define MUTEX_FALSE 0 +#define MUTEX_TRUE 1 + +class Mutex { + private: + u32int m_locked; + + public: + Mutex(u32int locked = MUTEX_FALSE); + bool lock(); //Locks the mutex if it is not locked. Returns true if mutex could be locked, false if already locked + void waitLock(); //Locks the mutex, waiting for it to be unlocked before if necessary + void unlock(); + bool locked(); +}; + +#endif diff --git a/Source/Library/Interface/Process.iface.h b/Source/Library/Interface/Process.iface.h index d639725..0956679 100644 --- a/Source/Library/Interface/Process.iface.h +++ b/Source/Library/Interface/Process.iface.h @@ -4,5 +4,6 @@ #define PR_IFACE_OBJTYPE 0x20 #define PR_IFACE_EXIT 0x01 #define PR_IFACE_ALLOCPAGE 0x02 +#define PR_IFACE_FREEPAGE 0x03 #endif diff --git a/Source/Library/Link.ld b/Source/Library/Link.ld new file mode 100644 index 0000000..f06f568 --- /dev/null +++ b/Source/Library/Link.ld @@ -0,0 +1,32 @@ +ENTRY (start) + +SECTIONS{ + . = 0x10000000; + + .text : { + *(.text) + } + + .rodata ALIGN (0x1000) :{ + *(.rodata) + } + + .data ALIGN (0x1000) : { + start_ctors = .; + *(.ctor*) + end_ctors = .; + start_dtors = .; + *(.dtor*) + end_dtors = .; + *(.data) + } + + .bss : { + sbss = .; + *(COMMON) + *(.bss) + ebss = .; + } + + end = .; _end = .; __end = .; +} diff --git a/Source/Library/Makefile b/Source/Library/Makefile index b9be0a0..028e7a4 100644 --- a/Source/Library/Makefile +++ b/Source/Library/Makefile @@ -1,7 +1,10 @@ .PHONY: clean, mrproper CXX = g++ -CXXFLAGS = -nostartfiles -nostdlib -fno-exceptions -fno-rtti -I Common -I Userland -D THIS_IS_MELON_USERLAND +CXXFLAGS = -nostartfiles -nostdlib -fno-exceptions -fno-rtti -I Common -I Userland -I Interface -D THIS_IS_MELON_USERLAND + +ASM = nasm +ASMFLAGS = -f elf LDFLAGS = -r LD = ld @@ -9,6 +12,9 @@ LD = ld Library = Melon.o Objects = Common/WChar.class.uo \ Common/CMem.ns.uo \ + Common/Mutex.class.uo \ + Common/Heap.class.uo \ + Common/Heap-index.class.uo \ Userland/Syscall/Syscall.wtf.uo \ Userland/Syscall/RessourceCaller.class.uo \ Userland/Start.uo @@ -26,6 +32,10 @@ $(Library): $(Objects) echo "* Compiling $<..." $(CXX) $(CXXFLAGS) -c $< -o $@ +%.uo: %.asm + echo "* Compiling $<..." + $(ASM) $(ASMFLAGS) $< -o $@ + clean: echo "* Removing object files..." rm -rf $(Objects) diff --git a/Source/Library/Userland/Binding/Process.class.h b/Source/Library/Userland/Binding/Process.class.h index c484e19..88af9d6 100644 --- a/Source/Library/Userland/Binding/Process.class.h +++ b/Source/Library/Userland/Binding/Process.class.h @@ -16,4 +16,7 @@ class Process : public RessourceCaller { void allocPage(u32int pos) { doCall(PR_IFACE_ALLOCPAGE, pos); } + void freePage(u32int pos) { + doCall(PR_IFACE_FREEPAGE, pos); + } }; diff --git a/Source/Library/Userland/Start.cpp b/Source/Library/Userland/Start.cpp index 02eb951..e185189 100644 --- a/Source/Library/Userland/Start.cpp +++ b/Source/Library/Userland/Start.cpp @@ -1,8 +1,35 @@ #include +#include + +extern "C" void __cxa_pure_virtual() {} //Required when using abstract classes +void *__dso_handle; //Required when using global objects +extern "C" int __cxa_atexit(void (*f)(void*), void *p, void *d) { return 0; } + +extern u32int start_ctors, end_ctors, start_dtors, end_dtors; + +Heap heap; + int main(); extern "C" void start() { + //Call static constructors + for(u32int * call = &start_ctors; call < &end_ctors; call++) { + ((void (*)(void))*call)(); + } + + heap.create(0x40000000, 0x00100000, 0x00003000); //Initially create a 1M heap with 12ko index u32int r = main(); + + //Call static destructors + for(u32int * call = &start_dtors; call < &end_dtors; call++) { + ((void (*)(void))*call)(); + } + asm volatile("int $66" : : "a"(r)); } + +namespace Mem { + void* alloc (u32int sz) { return heap.alloc(sz); } + void free(void* ptr) { heap.free(ptr); } +} diff --git a/Source/Library/Userland/common.h b/Source/Library/Userland/common.h index 27218f7..3508513 100644 --- a/Source/Library/Userland/common.h +++ b/Source/Library/Userland/common.h @@ -7,4 +7,20 @@ #include +namespace Mem { + void* alloc(u32int); + void free(void*); +} + +//Standard implemenations of operator new/delete +inline void* operator new(u32int, void *p) { return p; } +inline void* operator new[](u32int, void *p) { return p; } +inline void operator delete(void*, void*) { } +inline void operator delete[](void*, void*) { } + +inline void* operator new(u32int sz) { return Mem::alloc(sz); } +inline void* operator new[](u32int sz) { return Mem::alloc(sz); } +inline void operator delete(void *ptr) { Mem::free(ptr); } +inline void operator delete[](void *ptr) { Mem::free(ptr); } + #endif -- cgit v1.2.3