stdlib.c (4695B)
1 #include <stdlib.h>
2 #include <string.h>
3 #include <stdint.h>
4 #include <stddef.h>
5
6 #define HEAP_ALIGNMENT 8u
7 #define HEADER_SIZE 8u
8 #define MIN_BLOCK 16u
9 #define MAX_REQUEST 0x7FFFFFF0u
10 #define USED_MAGIC 0xA110C8EDu
11
12 typedef struct free_block free_block;
13
14 struct free_block {
15 uint32_t size;
16 uint32_t used;
17 free_block *next;
18 };
19
20 extern uint8_t __heap_start[];
21 extern uint8_t __heap_end[];
22
23 static free_block *free_list;
24 static uint8_t *heap_low;
25 static uint8_t *heap_high;
26 static uint32_t heap_ready;
27
28 static size_t align_up(size_t value) {
29 return (value + (HEAP_ALIGNMENT - 1)) & ~(size_t)(HEAP_ALIGNMENT - 1);
30 }
31
32 static uint32_t request_to_block(size_t size) {
33 uint32_t block = (uint32_t)align_up(size) + HEADER_SIZE;
34
35 return block < MIN_BLOCK ? MIN_BLOCK : block;
36 }
37
38 static void heap_init(void) {
39 size_t start = align_up((size_t)__heap_start);
40 size_t end = (size_t)__heap_end & ~(size_t)(HEAP_ALIGNMENT - 1);
41
42 heap_ready = 1;
43 free_list = NULL;
44 heap_low = (uint8_t *)start;
45 heap_high = (uint8_t *)end;
46
47 if (end < start + MIN_BLOCK) {
48 return;
49 }
50
51 free_block *block = (free_block *)start;
52
53 block->size = (uint32_t)(end - start);
54 block->used = 0;
55 block->next = NULL;
56 free_list = block;
57 }
58
59 static void release(free_block *block) {
60 free_block *previous = NULL;
61 free_block *current = free_list;
62
63 block->used = 0;
64
65 while (current != NULL && current < block) {
66 previous = current;
67 current = current->next;
68 }
69
70 block->next = current;
71
72 if (previous != NULL) {
73 previous->next = block;
74 } else {
75 free_list = block;
76 }
77
78 if (current != NULL && (uint8_t *)block + block->size == (uint8_t *)current) {
79 block->size += current->size;
80 block->next = current->next;
81 }
82
83 if (previous != NULL && (uint8_t *)previous + previous->size == (uint8_t *)block) {
84 previous->size += block->size;
85 previous->next = block->next;
86 }
87 }
88
89 static void unlink_block(free_block *target) {
90 free_block **link = &free_list;
91
92 while (*link != NULL) {
93 if (*link == target) {
94 *link = target->next;
95
96 return;
97 }
98
99 link = &(*link)->next;
100 }
101 }
102
103 static void trim(free_block *block, uint32_t need) {
104 if (block->size - need < MIN_BLOCK) {
105 return;
106 }
107
108 free_block *tail = (free_block *)((uint8_t *)block + need);
109
110 tail->size = block->size - need;
111 block->size = need;
112
113 release(tail);
114 }
115
116 static free_block *block_from_pointer(void *pointer) {
117 if (!heap_ready) {
118 return NULL;
119 }
120
121 uint8_t *address = (uint8_t *)pointer;
122
123 if (address < heap_low + HEADER_SIZE || address >= heap_high) {
124 return NULL;
125 }
126
127 if (((size_t)address & (HEAP_ALIGNMENT - 1)) != 0) {
128 return NULL;
129 }
130
131 free_block *block = (free_block *)(address - HEADER_SIZE);
132
133 if (block->used != USED_MAGIC) {
134 return NULL;
135 }
136
137 return block;
138 }
139
140 void *malloc(size_t size) {
141 if (!heap_ready) {
142 heap_init();
143 }
144
145 if (size == 0 || size > MAX_REQUEST) {
146 return NULL;
147 }
148
149 uint32_t need = request_to_block(size);
150 free_block *best = NULL;
151
152 for (free_block *current = free_list; current != NULL; current = current->next) {
153 if (current->size < need) {
154 continue;
155 }
156
157 if (best == NULL || current->size < best->size) {
158 best = current;
159
160 if (current->size == need) {
161 break;
162 }
163 }
164 }
165
166 if (best == NULL) {
167 return NULL;
168 }
169
170 unlink_block(best);
171 trim(best, need);
172 best->used = USED_MAGIC;
173
174 return (uint8_t *)best + HEADER_SIZE;
175 }
176
177 void free(void *pointer) {
178 if (pointer == NULL) {
179 return;
180 }
181
182 free_block *block = block_from_pointer(pointer);
183
184 if (block == NULL) {
185 return;
186 }
187
188 release(block);
189 }
190
191 void *calloc(size_t count, size_t size) {
192 if (size != 0 && count > MAX_REQUEST / size) {
193 return NULL;
194 }
195
196 size_t total = count * size;
197 void *pointer = malloc(total);
198
199 if (pointer != NULL) {
200 memset(pointer, 0, total);
201 }
202
203 return pointer;
204 }
205
206 void *realloc(void *pointer, size_t size) {
207 if (pointer == NULL) {
208 return malloc(size);
209 }
210
211 free_block *block = block_from_pointer(pointer);
212
213 if (block == NULL) {
214 return NULL;
215 }
216
217 if (size == 0) {
218 free(pointer);
219
220 return NULL;
221 }
222
223 if (size > MAX_REQUEST) {
224 return NULL;
225 }
226
227 uint32_t need = request_to_block(size);
228
229 if (need <= block->size) {
230 trim(block, need);
231
232 return pointer;
233 }
234
235 free_block *neighbor = free_list;
236
237 while (neighbor != NULL && (uint8_t *)neighbor < (uint8_t *)block + block->size) {
238 neighbor = neighbor->next;
239 }
240
241 if (neighbor != NULL && (uint8_t *)neighbor == (uint8_t *)block + block->size && block->size + neighbor->size >= need) {
242 unlink_block(neighbor);
243 block->size += neighbor->size;
244 trim(block, need);
245
246 return pointer;
247 }
248
249 void *grown = malloc(size);
250
251 if (grown == NULL) {
252 return NULL;
253 }
254
255 memcpy(grown, pointer, block->size - HEADER_SIZE);
256 free(pointer);
257
258 return grown;
259 }