1 files changed, 85 insertions, 19 deletions

diff --git a/src/kernel/memorymanagement.c b/src/kernel/memorymanagement.c
index c56d2b9..49c825c 100644
--- a/src/kernel/memorymanagement.c
+++ b/src/kernel/memorymanagement.c
@@ -7,26 +7,56 @@
 void memory_manager_init( memory_manager_t *memory_manager, size_t offset, size_t size )
 {
 	memset( memory_manager, 0, sizeof( memory_manager_t ) );
+	
+	if( size < sizeof( memory_chunk_t ) ) {
+		kernel_panic( "Size parameter must be bigger than %d", sizeof( memory_chunk_t ) );
+	}
 
 	memory_manager->offset = offset;
-	memory_manager->size = size;
-	memory_manager->free_ptr = memory_manager->offset;
-	memory_manager->prev_ptr = 0xFFFFFFFF;
+	memory_manager->size = size - sizeof( memory_chunk_t );
+	
+	// initially we have one big chunk, un-allocated
+	memory_chunk_t *first = (memory_chunk_t *)offset;	
+	first->allocated = false;
+	first->prev = NULL;
+	first->next = NULL;
+	first->size = size - sizeof( memory_chunk_t );
+	memory_manager->first = first;
 }
 
 void *memory_manager_allocate( memory_manager_t *memory_manager, size_t size )
-{
-	void *p = NULL;
-
-	if( memory_manager->free_ptr - memory_manager->offset + size > memory_manager->size ) {
-		kernel_panic( "Heap allocation out of memory (requested %d bytes, available %d)",
-			size, size - ( memory_manager->free_ptr - memory_manager->offset ) );
+{	
+	// find next free chunk with a proper size
+	memory_chunk_t *result = NULL;
+	for( memory_chunk_t *chunk = memory_manager->first; chunk != NULL; chunk = chunk->next ) {
+		if( chunk->size > size + sizeof( memory_chunk_t ) && !chunk->allocated ) {
+			result = chunk;
+			break;
+		}
 	}
-
-	p = (void *)memory_manager->free_ptr;
-	memory_manager->prev_ptr = memory_manager->free_ptr;
-	memory_manager->free_ptr += size;
-
+	
+	if( result == NULL ) {
+		kernel_panic( "Heap allocation out of memory (requested %d bytes)", size );
+	}
+	
+	// split of a new unallocated chunk at the end of the retrieved
+	// chunk, put in into the right place in the list of chunks
+	memory_chunk_t *tmp = (memory_chunk_t *)(( (uint32_t)result) + sizeof( memory_chunk_t ) + size );
+	tmp->allocated = false;
+	tmp->size = result->size - size - sizeof( memory_chunk_t );
+	tmp->prev = result;
+	tmp->next = result->next;
+	if( tmp->next != NULL ) {
+		tmp->next->prev = tmp;
+	}
+	result->allocated = true;
+	result->next = tmp;
+	result->size = size;
+	
+	// return a pointer after the internal data structure as pointer
+	// for the user, mark the chunk as used	
+	void *p = (void *)(( (uint32_t)result) + sizeof( memory_chunk_t ) );
+	
 	return p;
 }
 
@@ -39,13 +69,49 @@ void memory_manager_deallocate( memory_manager_t *memory_manager, void **p )
 	// This actually doesn't work and we do it outside after free, when
 	// a buffer has an optional semantic
 	//*p = NULL;
+
+	// mark chunk containing the pointer as unused
+	memory_chunk_t *chunk = (memory_chunk_t *)( (uint32_t)( *p ) - sizeof( memory_chunk_t ) );
+	chunk->allocated = false;
 	
-	// are we freeing the previously allocated block, if yes, we can
-	// adjust the free pointer
-	if( (uint32_t)*p == memory_manager->prev_ptr ) {
-		memory_manager->free_ptr = memory_manager->prev_ptr;
-		memory_manager->prev_ptr = 0xFFFFFFFF;
+	// join free chunks before the freed chunk
+	if( chunk->prev != NULL && !chunk->prev->allocated ) {
+		chunk->prev->next = chunk->next;
+		chunk->prev->size += chunk->size + sizeof( memory_chunk_t );
+		if( chunk->next != NULL ) {
+			chunk->next->prev = chunk->prev;
+		}
+	}
+
+	// join free chunks after the freed chunk
+	if( chunk->next != NULL && !chunk->next->allocated ) {
+		chunk->size += chunk->next->size + sizeof( memory_chunk_t );
+		chunk->next = chunk->next->next;
+		if( chunk->next != NULL ) {
+			chunk->next->prev = chunk;
+		}
 	}
 }
 
+static size_t count_chunks( memory_chunk_t *chunk, bool allocated )
+{
+	size_t result = 0;
+	
+	for( ; chunk != NULL; chunk = chunk->next ) {
+		if( chunk->allocated == allocated ) {
+			result += chunk->size;
+		}
+	}
+	
+	return result;
+}
+
+size_t memory_manager_stats_used( memory_manager_t *memory_manager )
+{
+	return count_chunks( memory_manager->first, true );
+}
 
+size_t memory_manager_stats_free( memory_manager_t *memory_manager )
+{
+	return count_chunks( memory_manager->first, false );
+}