1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
#include "memorymanagement.h"
#include "string.h"
#include "kernel.h"
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 - 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, size_t alignment )
{
// 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 + alignment + sizeof( memory_chunk_t ) && !chunk->allocated ) {
result = chunk;
break;
}
}
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 + alignment );
tmp->allocated = false;
tmp->size = result->size - size - alignment - 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 ) );
// align the pointer
if( alignment != 1 && (uint32_t)p % alignment != 0 ) {
p = (void *)( (uint32_t)p + alignment - ( (uint32_t)p % alignment ) );
}
return p;
}
void memory_manager_deallocate( memory_manager_t *memory_manager, void **p )
{
if( *p == NULL ) {
kernel_panic( "Double free of pointer 0x%X in heap", *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;
// 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 );
}
|