|
0
|
1 /*
|
|
|
2 * Tiny malloc
|
|
33
|
3 *
|
|
0
|
4 * Copyright (c) 2014 Fabrice Bellard
|
|
|
5 *
|
|
|
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
|
|
|
7 * of this software and associated documentation files (the "Software"), to deal
|
|
|
8 * in the Software without restriction, including without limitation the rights
|
|
|
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
|
|
10 * copies of the Software, and to permit persons to whom the Software is
|
|
|
11 * furnished to do so, subject to the following conditions:
|
|
|
12 *
|
|
|
13 * The above copyright notice and this permission notice shall be included in
|
|
|
14 * all copies or substantial portions of the Software.
|
|
|
15 *
|
|
|
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
|
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
|
|
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
|
|
|
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
|
|
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
|
|
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
|
|
|
22 * THE SOFTWARE.
|
|
|
23 */
|
|
|
24 #include <stddef.h>
|
|
|
25 #include <stdlib.h>
|
|
|
26 #include <stdio.h>
|
|
|
27 #include <inttypes.h>
|
|
|
28 #include <string.h>
|
|
|
29 #include <limits.h>
|
|
|
30 #ifndef MALLOC_TEST
|
|
|
31 #define NDEBUG
|
|
|
32 #endif
|
|
|
33 #include <assert.h>
|
|
|
34
|
|
|
35 /*
|
|
|
36 * Note: only works for 32 bit pointers
|
|
|
37 */
|
|
|
38 #define MALLOC_ALIGN 8
|
|
|
39 #define MALLOC_BLOCK_SIZE 32
|
|
|
40
|
|
|
41 #define STATE_FREE 0xaa
|
|
|
42 #define STATE_ALLOCATED 0x55
|
|
|
43
|
|
|
44 struct list_head {
|
|
|
45 struct list_head *prev, *next;
|
|
|
46 };
|
|
|
47
|
|
|
48 #define list_entry(el, type, member) \
|
|
|
49 ((type *)((uint8_t *)(el) - offsetof(type, member)))
|
|
|
50
|
|
|
51 /* Note: the 'state' byte is stored just before the MemBlock header,
|
|
|
52 so at most 23 bytes can be allocated in a single block. */
|
|
|
53 typedef struct MemBlock {
|
|
|
54 struct list_head link;
|
|
|
55 union {
|
|
|
56 uint8_t data[0] __attribute((aligned(MALLOC_ALIGN)));
|
|
|
57 struct list_head free_link;
|
|
|
58 } u;
|
|
|
59 } MemBlock;
|
|
|
60
|
|
|
61 void *sbrk(intptr_t increment);
|
|
|
62
|
|
|
63 /* Invariants: the last block is always a free block. The last free
|
|
|
64 block is always the last block. */
|
|
|
65 static struct list_head free_list;
|
|
|
66 static struct list_head block_list;
|
|
|
67 static uint8_t *mem_top;
|
|
|
68
|
|
|
69 /* insert 'el' after prev */
|
|
|
70 static void list_add(struct list_head *el, struct list_head *prev)
|
|
|
71 {
|
|
|
72 struct list_head *next = prev->next;
|
|
|
73 prev->next = el;
|
|
|
74 el->prev = prev;
|
|
|
75 el->next = next;
|
|
|
76 next->prev = el;
|
|
|
77 }
|
|
|
78
|
|
|
79 static void list_del(struct list_head *el)
|
|
|
80 {
|
|
|
81 struct list_head *prev, *next;
|
|
|
82 prev = el->prev;
|
|
|
83 next = el->next;
|
|
|
84 prev->next = next;
|
|
|
85 next->prev = prev;
|
|
|
86 }
|
|
|
87
|
|
|
88 static size_t get_alloc_size(size_t size)
|
|
|
89 {
|
|
|
90 size = offsetof(MemBlock, u.data) + size;
|
|
|
91 /* one more byte for the state byte from the next block */
|
|
|
92 size = (size + MALLOC_BLOCK_SIZE) & ~(MALLOC_BLOCK_SIZE - 1);
|
|
|
93 return size;
|
|
|
94 }
|
|
|
95
|
|
|
96 /* Note: this size includes the 'state' byte from the next block */
|
|
|
97 static size_t get_block_size(MemBlock *p)
|
|
|
98 {
|
|
|
99 uint8_t *end;
|
|
|
100 struct list_head *el;
|
|
|
101 el = p->link.next;
|
|
|
102 if (el == &block_list)
|
|
|
103 end = mem_top;
|
|
|
104 else
|
|
|
105 end = (uint8_t *)list_entry(el, MemBlock, link);
|
|
|
106 return end - (uint8_t *)p;
|
|
|
107 }
|
|
|
108
|
|
|
109 static inline void set_block_state(MemBlock *p, int state)
|
|
|
110 {
|
|
|
111 ((uint8_t *)p)[-1] = state;
|
|
|
112 }
|
|
|
113
|
|
|
114 static inline int get_block_state(const MemBlock *p)
|
|
|
115 {
|
|
|
116 return ((const uint8_t *)p)[-1];
|
|
|
117 }
|
|
|
118
|
|
|
119 void *malloc(size_t size)
|
|
|
120 {
|
|
|
121 MemBlock *p, *p1;
|
|
|
122 struct list_head *el;
|
|
|
123 size_t block_size;
|
|
|
124
|
|
|
125 if (size == 0 || size > (INT_MAX - 2 * MALLOC_BLOCK_SIZE))
|
|
|
126 return NULL;
|
|
|
127 if (free_list.next == NULL) {
|
|
|
128 /* init */
|
|
|
129 p = sbrk(MALLOC_BLOCK_SIZE * 2);
|
|
|
130 if (p == (void *)-1)
|
|
|
131 return NULL;
|
|
33
|
132
|
|
0
|
133 mem_top = sbrk(0);
|
|
|
134 free_list.prev = free_list.next = &free_list;
|
|
|
135 block_list.prev = block_list.next = &block_list;
|
|
|
136 p++;
|
|
|
137 set_block_state(p, STATE_FREE);
|
|
|
138 list_add(&p->link, &block_list);
|
|
|
139 list_add(&p->u.free_link, &free_list);
|
|
|
140 }
|
|
|
141
|
|
|
142 size = get_alloc_size(size);
|
|
|
143 el = free_list.next;
|
|
|
144 for(;;) {
|
|
|
145 p = list_entry(el, MemBlock, u.free_link);
|
|
|
146 assert(get_block_state(p) == STATE_FREE);
|
|
|
147 block_size = get_block_size(p);
|
|
|
148 if (size < block_size) {
|
|
|
149 goto done1;
|
|
|
150 } else if (el == free_list.prev) {
|
|
|
151 /* last free block: increase its size */
|
|
|
152 if (sbrk(size + MALLOC_BLOCK_SIZE - block_size) == (void *)-1)
|
|
|
153 return NULL;
|
|
|
154 mem_top = sbrk(0);
|
|
|
155 done1:
|
|
|
156 p1 = (MemBlock *)((uint8_t *)p + size);
|
|
|
157 list_add(&p1->link, &p->link);
|
|
|
158 list_add(&p1->u.free_link, &p->u.free_link);
|
|
|
159 set_block_state(p1, STATE_FREE);
|
|
|
160 list_del(&p->u.free_link);
|
|
|
161 done:
|
|
|
162 set_block_state(p, STATE_ALLOCATED);
|
|
|
163 return p->u.data;
|
|
|
164 } else if (size == block_size) {
|
|
|
165 list_del(&p->u.free_link);
|
|
|
166 goto done;
|
|
|
167 }
|
|
|
168 el = el->next;
|
|
|
169 }
|
|
|
170 }
|
|
|
171
|
|
|
172 void free(void *ptr)
|
|
|
173 {
|
|
|
174 MemBlock *p, *p1;
|
|
|
175 struct list_head *el;
|
|
|
176
|
|
|
177 if (!ptr)
|
|
|
178 return;
|
|
|
179 p = (MemBlock *)((uint8_t *)ptr - offsetof(MemBlock, u.data));
|
|
|
180 assert(get_block_state(p) == STATE_ALLOCATED);
|
|
|
181
|
|
|
182 /* mark as free */
|
|
|
183 list_add(&p->u.free_link, &free_list);
|
|
|
184 set_block_state(p, STATE_FREE);
|
|
|
185
|
|
|
186 /* merge with previous free block if possible */
|
|
|
187 el = p->link.prev;
|
|
|
188 if (el != &block_list) {
|
|
|
189 p1 = list_entry(el, MemBlock, link);
|
|
|
190 if (get_block_state(p1) == STATE_FREE) {
|
|
|
191 list_del(&p->link);
|
|
|
192 list_del(&p->u.free_link);
|
|
|
193 p = p1;
|
|
|
194 }
|
|
|
195 }
|
|
|
196 /* merge with next block if possible */
|
|
|
197 el = p->link.next;
|
|
|
198 if (el != &block_list) {
|
|
|
199 p1 = list_entry(el, MemBlock, link);
|
|
|
200 if (get_block_state(p1) == STATE_FREE) {
|
|
|
201 list_del(&p1->link);
|
|
|
202 /* keep p in the same position in free_list as p1 */
|
|
|
203 list_del(&p->u.free_link);
|
|
|
204 list_add(&p->u.free_link, &p1->u.free_link);
|
|
|
205 list_del(&p1->u.free_link);
|
|
|
206 }
|
|
|
207 }
|
|
|
208 }
|
|
|
209
|
|
|
210 void *realloc(void *ptr, size_t size)
|
|
|
211 {
|
|
|
212 MemBlock *p;
|
|
|
213 void *ptr1;
|
|
|
214 size_t size1;
|
|
|
215
|
|
|
216 if (ptr == NULL) {
|
|
|
217 return malloc(size);
|
|
|
218 } else if (size == 0) {
|
|
|
219 free(ptr);
|
|
|
220 return NULL;
|
|
|
221 } else {
|
|
|
222 p = (MemBlock *)((uint8_t *)ptr - offsetof(MemBlock, u.data));
|
|
|
223 assert(get_block_state(p) == STATE_ALLOCATED);
|
|
|
224 ptr1 = malloc(size);
|
|
|
225 if (!ptr1)
|
|
|
226 return NULL;
|
|
|
227 /* Note: never the last block so it is valid */
|
|
33
|
228 size1 = (uint8_t *)list_entry(p->link.next, MemBlock, link) -
|
|
0
|
229 p->u.data - 1;
|
|
|
230 if (size < size1)
|
|
|
231 size1 = size;
|
|
|
232 memcpy(ptr1, ptr, size1);
|
|
|
233 free(ptr);
|
|
|
234 return ptr1;
|
|
|
235 }
|
|
|
236 }
|
|
|
237
|
|
|
238 #ifdef MALLOC_TEST
|
|
|
239 static void malloc_check(void)
|
|
|
240 {
|
|
|
241 MemBlock *p;
|
|
|
242 struct list_head *el;
|
|
|
243 int state;
|
|
|
244
|
|
|
245 for(el = block_list.next; el != &block_list; el = el->next) {
|
|
|
246 p = list_entry(el, MemBlock, link);
|
|
|
247 state = get_block_state(p);
|
|
|
248 assert(state == STATE_FREE || state == STATE_ALLOCATED);
|
|
|
249 if (el->next != &block_list)
|
|
|
250 assert(el->next > el);
|
|
|
251 }
|
|
|
252 for(el = free_list.next; el != &free_list; el = el->next) {
|
|
|
253 p = list_entry(el, MemBlock, u.free_link);
|
|
|
254 assert(get_block_state(p) == STATE_FREE);
|
|
|
255 }
|
|
|
256
|
|
|
257 /* check invariant */
|
|
|
258 el = free_list.prev;
|
|
|
259 if (el != &free_list) {
|
|
|
260 p = list_entry(el, MemBlock, u.free_link);
|
|
|
261 assert(&p->link == block_list.prev);
|
|
|
262 }
|
|
|
263 }
|
|
|
264
|
|
|
265 static void malloc_dump(void)
|
|
|
266 {
|
|
|
267 MemBlock *p;
|
|
|
268 struct list_head *el;
|
|
33
|
269
|
|
0
|
270 printf("blocks:\n");
|
|
|
271 for(el = block_list.next; el != &block_list; el = el->next) {
|
|
|
272 p = list_entry(el, MemBlock, link);
|
|
33
|
273 printf("block: %p next=%p free=%d size=%u\n", p, p->link.next,
|
|
0
|
274 get_block_state(p) == STATE_FREE,
|
|
|
275 (unsigned int)get_block_size(p));
|
|
|
276 }
|
|
|
277 printf("free list:\n");
|
|
|
278 for(el = free_list.next; el != &free_list; el = el->next) {
|
|
|
279 p = list_entry(el, MemBlock, u.free_link);
|
|
|
280 printf("block: %p size=%u\n", p, (unsigned int)get_block_size(p));
|
|
|
281 }
|
|
|
282 }
|
|
|
283
|
|
|
284 int main(int argc, char **argv)
|
|
|
285 {
|
|
|
286 int i, n, j, size;
|
|
|
287 void **tab;
|
|
|
288
|
|
|
289 n = 100;
|
|
|
290 tab = malloc(sizeof(void *) * n);
|
|
|
291 memset(tab, 0, n * sizeof(void *));
|
|
|
292
|
|
|
293 for(i = 0; i < n * 1000; i++) {
|
|
|
294 j = random() % n;
|
|
|
295
|
|
|
296 free(tab[j]);
|
|
|
297
|
|
|
298 malloc_check();
|
|
|
299
|
|
|
300 size = random() % 500;
|
|
|
301 tab[j] = malloc(size);
|
|
|
302 memset(tab[j], 0x11, size);
|
|
|
303
|
|
|
304 malloc_check();
|
|
|
305 }
|
|
|
306
|
|
|
307 malloc_dump();
|
|
|
308
|
|
|
309 for(i = 0; i < n; i++) {
|
|
|
310 free(tab[i]);
|
|
|
311 }
|
|
|
312 return 0;
|
|
|
313 }
|
|
|
314 #endif
|
