From 5956699139b783c13869a1097bfb5dba8e867b0f Mon Sep 17 00:00:00 2001 From: Andreas Baumann Date: Fri, 14 Jul 2017 20:11:00 +0200 Subject: added stats functions to memory manager, don't use internal members added simple chunk-based allocation/deallocation strategy (leads to framgentation) --- src/kernel/kernel.c | 7 +-- src/kernel/memorymanagement.c | 104 ++++++++++++++++++++++++++++++++++-------- src/kernel/memorymanagement.h | 14 +++++- 3 files changed, 99 insertions(+), 26 deletions(-) diff --git a/src/kernel/kernel.c b/src/kernel/kernel.c index be5da7c..734572c 100644 --- a/src/kernel/kernel.c +++ b/src/kernel/kernel.c @@ -412,11 +412,8 @@ static void print_memory_status( global_context_t *global_context ) printf( "heap memory size: %d\n", memory_manager->size ); printf( "heap memory offset: 0x%X\n", memory_manager->offset ); - printf( "heap memory in use: %d\n", - memory_manager->free_ptr - memory_manager->offset ); - printf( "heap memory free: %d\n", - memory_manager->size - ( memory_manager->free_ptr - memory_manager->offset ) - 1 ); - + printf( "heap memory in use: %d\n", memory_manager_stats_used( memory_manager ) ); + printf( "heap memory free: %d\n", memory_manager_stats_free( memory_manager ) ); } uintptr_t __stack_chk_guard = STACK_CHK_GUARD; 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 ); +} diff --git a/src/kernel/memorymanagement.h b/src/kernel/memorymanagement.h index 299fa4c..6dee417 100644 --- a/src/kernel/memorymanagement.h +++ b/src/kernel/memorymanagement.h @@ -2,17 +2,27 @@ #define MEMORYMANAGEMENT_H #include +#include + #include "stdint.h" +typedef struct memory_chunk_t { + struct memory_chunk_t *next; + struct memory_chunk_t *prev; + bool allocated; + size_t size; +} memory_chunk_t; + typedef struct { size_t offset; size_t size; - uint32_t prev_ptr; - uint32_t free_ptr; + memory_chunk_t *first; } memory_manager_t; void memory_manager_init( memory_manager_t *memory_manager, size_t offset, size_t size ); void *memory_manager_allocate( memory_manager_t *memory_manager, size_t size ); void memory_manager_deallocate( memory_manager_t *memory_manager, void **p ); +size_t memory_manager_stats_used( memory_manager_t *memory_manager ); +size_t memory_manager_stats_free( memory_manager_t *memory_manager ); #endif // MEMORYMANAGEMENT_H -- cgit v1.2.3-54-g00ecf