4 * GMQCC does a lot of allocations on shortly lived objects all of which
5 * call down to malloc/free internally. The overhead involved with these
6 * allocations makes GMQCC slow. To combat this, a special allocator was
7 * in need. This is an implementation of a user-space buddy allocator
8 * that sits ontop of malloc/free. I'd like to thank Lee Salzman for
9 * guiding me in the right direction for designing this.
11 #define GMQCC_MEM_USED 0xEDCA10A1EDCA10A1
12 #define GMQCC_MEM_FREE 0xEEF8EEF8EEF8EEF8
13 #define GMQCC_MEM_CORE 0x00000000000000AA
14 #define GMQCC_MEM_BSL -1
15 #define GMQCC_MEM_BSR 1
16 #define GMQCC_MEM_DEBUG 1
18 #ifdef GMQCC_MEM_DEBUG
20 # define GMQCC_MEM_TRACE(TAG, ...) \
22 printf("[mem:%s]: %s ", TAG, __func__); \
23 printf(__VA_ARGS__); \
27 # define GMQCC_MEM_TRACE(TAG, ...)
30 typedef unsigned long int mem_addr;
32 static void *mem_heap = NULL;
33 static size_t mem_look = 0; /* lookup table offset */
34 static size_t mem_size = 0; /* heap size */
36 /* read or write to heap */
37 #define GMQCC_MEM_WRITEHEAP(OFFSET, TYPE, VALUE) *((TYPE *) ((unsigned char*)mem_heap + (OFFSET))) = (VALUE)
38 #define GMQCC_MEM_READHEAP(OFFSET, TYPE) ((TYPE)*((TYPE *)(((unsigned char*)mem_heap + (OFFSET)))))
40 /* read of write first block to heap */
41 #define GMQCC_MEM_WRITEFBA(SIZE, ADDR) GMQCC_MEM_WRITEHEAP(mem_look + (SIZE) * sizeof(mem_addr), mem_addr, ADDR)
42 #define GMQCC_MEM_READFBA(SIZE) GMQCC_MEM_READHEAP (mem_look + (SIZE) * sizeof(mem_addr), mem_addr)
44 /* read and write block sizes from heap */
45 #define GMQCC_MEM_WRITEBS(ADDR, SIZE) GMQCC_MEM_WRITEHEAP(ADDR, mem_addr, (SIZE))
46 #define GMQCC_MEM_READBS(ADDR) GMQCC_MEM_READHEAP (ADDR, mem_addr);
49 * Getting address of previous/following siblings, as well as
50 * setting address of previous/following siblings.
52 #define GMQCC_MEM_GETADDROFPS(ADDR) GMQCC_MEM_READHEAP ((ADDR) + 2 * sizeof(mem_addr), mem_addr)
53 #define GMQCC_MEM_GETADDROFFS(ADDR) GMQCC_MEM_READHEAP ((ADDR) + 3 * sizeof(mem_addr), mem_addr)
54 #define GMQCC_MEM_SETADDROFPS(ADDR,V) GMQCC_MEM_WRITEHEAP((ADDR) + 2 * sizeof(mem_addr), mem_addr, V)
55 #define GMQCC_MEM_SETADDROFFS(ADDR,V) GMQCC_MEM_WRITEHEAP((ADDR) + 3 * sizeof(mem_addr), mem_addr, V)
57 /* Marking blocks as used or free */
58 #define GMQCC_MEM_MARKUSED(ADDR) GMQCC_MEM_WRITEHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr, GMQCC_MEM_USED)
59 #define GMQCC_MEM_MARKFREE(ADDR) GMQCC_MEM_WRITEHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr, GMQCC_MEM_FREE)
62 #define GMQCC_MEM_HASBLOCK(SIZE) (GMQCC_MEM_READFBA(size) != 0)
64 static void mem_init_table(size_t size) {
65 GMQCC_MEM_TRACE("flow", "(%lu)", size);
68 mem_look = 8 * ((mem_addr)1 << (size - 1)) + sizeof(mem_addr);
70 GMQCC_MEM_WRITEHEAP(0, mem_addr, mem_look);
71 GMQCC_MEM_WRITEHEAP(mem_look, mem_addr, size);
73 /* write pointers to first free bock of said size */
74 for (i = 1; i < size; i++)
75 GMQCC_MEM_WRITEHEAP(mem_look + sizeof(mem_addr) * i, mem_addr, 0);
77 GMQCC_MEM_WRITEHEAP(mem_look + sizeof(mem_addr) * size, mem_addr, sizeof(mem_addr));
78 GMQCC_MEM_WRITEHEAP(sizeof(mem_addr), mem_addr, size);
79 GMQCC_MEM_MARKFREE (sizeof(mem_addr) * 2);
80 GMQCC_MEM_WRITEHEAP(sizeof(mem_addr) * 3, mem_addr, 0);
81 GMQCC_MEM_WRITEHEAP(sizeof(mem_addr) * 4, mem_addr, 0);
84 /* get needed block size */
85 static size_t mem_getnbs(const size_t need) {
97 static void mem_removeblock(mem_addr a, size_t size) {
98 mem_addr p = GMQCC_MEM_GETADDROFPS(a);
99 mem_addr n = GMQCC_MEM_GETADDROFFS(a);
101 GMQCC_MEM_SETADDROFPS(a, ~((mem_addr)0));
102 GMQCC_MEM_SETADDROFFS(a, ~((mem_addr)0));
104 /* handle singles in list */
105 if ((p == 0) && (n == 0)) {
106 GMQCC_MEM_WRITEFBA(size, 0);
110 /* first in list has different sibling semantics */
112 GMQCC_MEM_WRITEFBA (size, n);
113 GMQCC_MEM_SETADDROFPS(n, 0);
117 /* last item also has special meaning :) */
119 GMQCC_MEM_SETADDROFFS(p, 0);
124 GMQCC_MEM_SETADDROFPS(n, p);
125 GMQCC_MEM_SETADDROFFS(p, n);
128 static int mem_createblock(const size_t size) {
132 GMQCC_MEM_TRACE("flow", "(%lu)", size);
133 if (GMQCC_MEM_HASBLOCK(size))
136 if (size > GMQCC_MEM_READHEAP(mem_look, mem_addr))
140 if ((test = mem_createblock(size + 1)) != 0)
143 /* safe splits assured */
144 parent = GMQCC_MEM_READFBA(size + 1);
145 mem_removeblock(parent, size + 1);
148 GMQCC_MEM_WRITEFBA(size, parent);
150 /* find center and split */
151 mem_addr block = parent + 8 * ((mem_addr)1 << (size - 1));
152 mem_addr left = parent;
153 mem_addr right = block;
157 "block info:\n left addr: %lu\n right addr: %lu\n prev addr: %lu",
162 GMQCC_MEM_WRITEHEAP (left, mem_addr, size);
163 GMQCC_MEM_MARKFREE (left);
164 GMQCC_MEM_SETADDROFPS(left, 0);
165 GMQCC_MEM_SETADDROFFS(left, right);
167 GMQCC_MEM_WRITEHEAP (right, mem_addr, size);
168 GMQCC_MEM_MARKFREE (right);
169 GMQCC_MEM_SETADDROFPS(right, left);
170 GMQCC_MEM_SETADDROFPS(right, 0);
175 static mem_addr mem_allocblock(const size_t size) {
176 GMQCC_MEM_TRACE("flow", "(%lu)", size);
177 int test = mem_createblock(size);
185 first = GMQCC_MEM_READFBA (size);
186 next = GMQCC_MEM_GETADDROFFS(first);
188 mem_removeblock(first, size);
190 GMQCC_MEM_WRITEFBA(next, size);
191 GMQCC_MEM_MARKUSED(first);
196 static int mem_getside(mem_addr addr, const size_t size) {
197 size_t real = addr - sizeof(mem_addr);
198 size_t next = ((mem_addr)1 << (size));
199 assert((real % 8) == 0); /* blow up */
202 return ((real % next) == 0)? GMQCC_MEM_BSL : GMQCC_MEM_BSR;
205 static mem_addr mem_getaddr(mem_addr start, const size_t size) {
206 size_t length = (((mem_addr)1 << (size - 1)) * 8);
208 switch (mem_getside(start, size)) {
209 case GMQCC_MEM_BSL: return start + length;
210 case GMQCC_MEM_BSR: return start - length;
212 /* if reached blow up */
216 static void mem_addblock(mem_addr a, size_t s) {
217 mem_addr first = GMQCC_MEM_READFBA(s);
220 GMQCC_MEM_WRITEFBA (s, a);
221 GMQCC_MEM_SETADDROFPS(a, 0);
222 GMQCC_MEM_SETADDROFFS(a, 0);
225 GMQCC_MEM_WRITEFBA (s, a);
226 GMQCC_MEM_SETADDROFPS(a, 0);
227 GMQCC_MEM_SETADDROFFS(a, first);
228 GMQCC_MEM_SETADDROFPS(first, a);
232 void mem_init(size_t size) {
237 /* blow up if too small */
238 assert (sizeof(void*) == sizeof(mem_addr));
240 if (!(mem_heap = malloc(size)))
243 memset(mem_heap, GMQCC_MEM_CORE, size);
245 alloc -= 2 * sizeof(mem_addr);
247 while (alloc + sizeof(mem_addr) > 8 * block) {
248 alloc -= sizeof(mem_addr);
257 mem_init_table(count);
260 /* doesn't get any simpler :-) */
266 void *mem_alloc(size_t amount) {
267 GMQCC_MEM_TRACE("flow", "(%lu)", amount);
268 size_t need = amount + 4 * sizeof(mem_addr);
269 size_t size = mem_getnbs (need);
270 mem_addr block = mem_allocblock(size);
272 GMQCC_MEM_TRACE("dump", "will allocate %lu size block", size);
273 /* standard behaviour */
276 GMQCC_MEM_TRACE("dump", "returning offset %lu", block);
277 return mem_heap + block + 4 * sizeof(mem_addr);
280 void mem_free(void *ptr) {
281 mem_addr start = (mem_addr)(ptr - mem_heap) - 4 * sizeof(mem_addr);
282 size_t size = GMQCC_MEM_READHEAP(start, mem_addr);
283 mem_addr addr = mem_getaddr(start, size);
284 int side = mem_getside(start, size);
289 "deallocating %s buddy (neighbour at %lu)",
290 (side == GMQCC_MEM_BSL) ? "left" : "right",
293 GMQCC_MEM_MARKFREE(start);
295 /* while free block merge */
296 while ((GMQCC_MEM_READHEAP(addr + 1 * sizeof(mem_addr), mem_addr)) == (mem_addr)GMQCC_MEM_FREE) {
297 GMQCC_MEM_TRACE("dump", "merging ...");
298 mem_removeblock(addr, size);
301 start = addr < start ? addr : start;
304 if (size == GMQCC_MEM_READHEAP(mem_look, mem_addr))
307 addr = mem_getaddr(start, size);
308 GMQCC_MEM_TRACE("dump", "new block start is %lu, buddy at %lu", start, addr);
312 GMQCC_MEM_WRITEBS(start, size);
313 mem_addblock (start, size);
319 char *p = mem_alloc(sizeof(char) * 5);
320 /* blows up on second alloc, why? char *x = mem_alloc(200); */