Mercurial > hg > forks > libbpg

comparison tmalloc.c @ 0:772086c29cc7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import.
author Matti Hamalainen <ccr@tnsp.org>
date Wed, 16 Nov 2016 11:16:33 +0200
parents
children 33594243ce31
comparison
equal deleted inserted replaced
-1:000000000000 0:772086c29cc7
1 /*
2 * Tiny malloc
3 *
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;
132
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 */
228 size1 = (uint8_t *)list_entry(p->link.next, MemBlock, link) -
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;
269
270 printf("blocks:\n");
271 for(el = block_list.next; el != &block_list; el = el->next) {
272 p = list_entry(el, MemBlock, link);
273 printf("block: %p next=%p free=%d size=%u\n", p, p->link.next,
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