Heap included as well in userland library

12 files changed, 18 insertions, 405 deletions

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 <Devices/Device.proto.h>
-#include <TaskManager/Mutex.class.h>
+#include <Mutex.class.h>
 
 #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 <MemoryManager/PageDirectory.class.h>
-
-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 <common.h>
-#include <TaskManager/Mutex.class.h>
-
-//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 <common.h>
 #include <MemoryManager/PhysMem.ns.h>
-#include <MemoryManager/Heap.class.h>
+#include <Heap.class.h>
 
 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 <TaskManager/Task.ns.h>
-
-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 <common.h>
-
-#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 <Vector.class.h>
 #include <SimpleList.class.h>
 #include <MemoryManager/PageDirectory.class.h>
-#include <MemoryManager/Heap.class.h>
+#include <Heap.class.h>
 #include <VTManager/VirtualTerminal.proto.h>
 #include <VFS/File.class.h>
 
@@ -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 <common.h>
 #include <String.class.h>
-#include <TaskManager/Mutex.class.h>
+#include <Mutex.class.h>
 #include <DeviceManager/Kbd.ns.h>
 #include <Vector.class.h>