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_BSL -1
14 #define GMQCC_MEM_BSR 1
15 #define GMQCC_MEM_DEBUG 1
17 /* debug info for dumping heap contents nicely */
18 #define GMQCC_MEM_DEBUG_BPL 32 /* bytes per line */
19 #define GMQCC_MEM_DEBUG_BIG 8 /* bytes in group */
20 #define GMQCC_MEM_DEBUG_BSG 4 /* bytes split group */
22 #ifdef GMQCC_MEM_DEBUG
24 # define GMQCC_MEM_TRACE(TAG, ...) \
26 printf("[mem:%s]: %s ", TAG, __func__); \
27 printf(__VA_ARGS__); \
31 # define GMQCC_MEM_TRACE(TAG, ...)
34 typedef unsigned long int mem_addr;
36 static void *mem_heap = NULL;
37 static size_t mem_look = 0; /* lookup table offset */
38 static size_t mem_size = 0; /* heap size */
40 /* read or write to heap */
41 #define GMQCC_MEM_WRITEHEAP(OFFSET, TYPE, VALUE) \
43 TYPE *T = (TYPE*)((unsigned char*)mem_heap + (OFFSET)); \
46 #define GMQCC_MEM_READHEAP(OFFSET, TYPE) ((TYPE)*((TYPE *)(((unsigned char*)mem_heap + (OFFSET)))))
48 /* read of write first block to heap */
49 #define GMQCC_MEM_WRITEFBA(SIZE, ADDR) GMQCC_MEM_WRITEHEAP(mem_look + (SIZE) * sizeof(mem_addr), mem_addr, (ADDR))
50 #define GMQCC_MEM_READFBA(SIZE) GMQCC_MEM_READHEAP (mem_look + (SIZE) * sizeof(mem_addr), mem_addr)
52 /* read and write block sizes from heap */
53 #define GMQCC_MEM_WRITEBS(ADDR, SIZE) GMQCC_MEM_WRITEHEAP(ADDR, mem_addr, (SIZE))
54 #define GMQCC_MEM_READBS(ADDR) GMQCC_MEM_READHEAP (ADDR, mem_addr);
57 * Getting address of previous/following siblings, as well as
58 * setting address of previous/following siblings.
60 #define GMQCC_MEM_GETADDROFPS(ADDR) GMQCC_MEM_READHEAP ((ADDR) + 2 * sizeof(mem_addr), mem_addr)
61 #define GMQCC_MEM_GETADDROFFS(ADDR) GMQCC_MEM_READHEAP ((ADDR) + 3 * sizeof(mem_addr), mem_addr)
62 #define GMQCC_MEM_SETADDROFPS(ADDR,V) GMQCC_MEM_WRITEHEAP((ADDR) + 2 * sizeof(mem_addr), mem_addr, V)
63 #define GMQCC_MEM_SETADDROFFS(ADDR,V) GMQCC_MEM_WRITEHEAP((ADDR) + 3 * sizeof(mem_addr), mem_addr, V)
65 /* Marking blocks as used or free */
66 #define GMQCC_MEM_MARKUSED(ADDR) GMQCC_MEM_WRITEHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr, GMQCC_MEM_USED)
67 #define GMQCC_MEM_MARKFREE(ADDR) GMQCC_MEM_WRITEHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr, GMQCC_MEM_FREE)
70 #define GMQCC_MEM_HASBLOCK(SIZE) (GMQCC_MEM_READFBA(SIZE) != 0)
73 #define GMQCC_MEM_BLOCKFREE(ADDR) ((GMQCC_MEM_READHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr)) == GMQCC_MEM_FREE)
76 * Must be first since it's used internally, but also should be exposed
77 * to the outside, statics exist after this.
81 unsigned char *ptr = (unsigned char*)mem_heap;
83 while (addr < mem_size) {
85 printf("% 8X: ", addr);
86 while (offset < GMQCC_MEM_DEBUG_BPL) {
87 if (addr + offset >= mem_size)
94 !(offset%GMQCC_MEM_DEBUG_BSG) &&
95 (offset%GMQCC_MEM_DEBUG_BIG) ? "%02X " :
96 !(offset%GMQCC_MEM_DEBUG_BIG) ? "%02X " : "%02X ",
101 addr += GMQCC_MEM_DEBUG_BPL;
105 static void mem_init_table(size_t size) {
107 GMQCC_MEM_TRACE("flow", "(%lu)", size);
109 mem_look = 8 * ((mem_addr)1 << (size - 1)) + sizeof(mem_addr);
111 GMQCC_MEM_WRITEHEAP(0, mem_addr, mem_look);
112 GMQCC_MEM_WRITEHEAP(mem_look, mem_addr, size);
114 /* write pointers to first free bock of said size */
115 for (i = 1; i < size; i++)
116 GMQCC_MEM_WRITEHEAP(mem_look + sizeof(mem_addr) * i, mem_addr, 0);
118 GMQCC_MEM_WRITEHEAP(mem_look + sizeof(mem_addr) * size, mem_addr, sizeof(mem_addr));
119 GMQCC_MEM_WRITEHEAP(sizeof(mem_addr), mem_addr, size);
120 GMQCC_MEM_MARKFREE (sizeof(mem_addr) * 2);
121 GMQCC_MEM_WRITEHEAP(sizeof(mem_addr) * 3, mem_addr, 0);
122 GMQCC_MEM_WRITEHEAP(sizeof(mem_addr) * 4, mem_addr, 0);
125 /* get needed block size */
126 static size_t mem_getnbs(const size_t need) {
138 static void mem_removeblock(mem_addr a, size_t size) {
139 mem_addr p = GMQCC_MEM_GETADDROFPS(a);
140 mem_addr n = GMQCC_MEM_GETADDROFFS(a);
142 GMQCC_MEM_TRACE("flow", "(%lu, %lu)", a, size);
144 GMQCC_MEM_SETADDROFPS(a, ~((mem_addr)0));
145 GMQCC_MEM_SETADDROFFS(a, ~((mem_addr)0));
147 /* handle singles in list */
148 if ((p == 0) && (n == 0)) {
149 GMQCC_MEM_WRITEFBA(size, 0);
153 /* first in list has different sibling semantics */
155 GMQCC_MEM_WRITEFBA (size, n);
156 GMQCC_MEM_SETADDROFPS(n, 0);
160 /* last item also has special meaning :) */
162 GMQCC_MEM_SETADDROFFS(p, 0);
167 GMQCC_MEM_SETADDROFPS(n, p);
168 GMQCC_MEM_SETADDROFFS(p, n);
171 static int mem_createblock(const size_t size) {
175 GMQCC_MEM_TRACE("flow", "(%lu)", size);
176 if (GMQCC_MEM_HASBLOCK(size))
179 if (size > GMQCC_MEM_READHEAP(mem_look, mem_addr))
183 test = mem_createblock(size + 1);
187 /* safe splits assured */
188 parent = GMQCC_MEM_READFBA(size + 1);
189 mem_removeblock(parent, size + 1);
192 GMQCC_MEM_WRITEFBA(size, parent);
194 /* find center and split */
195 mem_addr block = parent + 8 * ((mem_addr)1 << (size - 1));
196 mem_addr left = parent;
197 mem_addr right = block;
201 "left: %lu right: %lu parent: %lu",
206 GMQCC_MEM_WRITEHEAP (left, mem_addr, size);
207 GMQCC_MEM_MARKFREE (left);
208 GMQCC_MEM_SETADDROFPS(left, 0);
209 GMQCC_MEM_SETADDROFFS(left, right);
211 GMQCC_MEM_WRITEHEAP (right, mem_addr, size);
212 GMQCC_MEM_MARKFREE (right);
213 GMQCC_MEM_SETADDROFPS(right, left);
214 GMQCC_MEM_SETADDROFFS(right, 0);
220 static mem_addr mem_allocblock(const size_t size) {
221 GMQCC_MEM_TRACE("flow", "(%lu)", size);
222 int test = mem_createblock(size);
230 first = GMQCC_MEM_READFBA (size);
231 next = GMQCC_MEM_GETADDROFFS(first);
233 mem_removeblock(first, size);
235 GMQCC_MEM_WRITEFBA(next, size);
236 GMQCC_MEM_MARKUSED(first);
241 static int mem_getside(mem_addr addr, const size_t size) {
242 size_t start = addr - sizeof(mem_addr);
245 test = ((mem_addr)1 << (size));
247 return ((start % test) == 0) ? GMQCC_MEM_BSL : GMQCC_MEM_BSR;
250 static mem_addr mem_getaddr(mem_addr start, const size_t size) {
251 size_t length = ((mem_addr)1 << (size - 1));
254 switch (mem_getside(start, size)) {
255 case GMQCC_MEM_BSL: return start + length;
256 case GMQCC_MEM_BSR: return start - length;
258 /* if reached blow up */
262 static void mem_addblock(mem_addr a, size_t s) {
263 mem_addr first = GMQCC_MEM_READFBA(s);
266 GMQCC_MEM_WRITEFBA (s, a);
267 GMQCC_MEM_SETADDROFPS(a, 0);
268 GMQCC_MEM_SETADDROFFS(a, 0);
271 GMQCC_MEM_WRITEFBA (s, a);
272 GMQCC_MEM_SETADDROFPS(a, 0);
273 GMQCC_MEM_SETADDROFFS(a, first);
274 GMQCC_MEM_SETADDROFPS(first, a);
278 void mem_init(size_t size) {
283 /* blow up if too small */
284 assert (sizeof(void*) == sizeof(mem_addr));
286 if (!(mem_heap = malloc(size)))
289 memset(mem_heap, 170, size);
291 alloc -= 2 * sizeof(mem_addr);
293 while (alloc + sizeof(mem_addr) > 8 * block) {
294 alloc -= sizeof(mem_addr);
303 mem_init_table(count);
306 /* doesn't get any simpler :-) */
312 void *mem_alloc(size_t amount) {
313 GMQCC_MEM_TRACE("flow", "(%lu)", amount);
314 size_t need = amount + 4 * sizeof(mem_addr);
315 size_t size = mem_getnbs (need);
316 mem_addr block = mem_allocblock(size);
318 GMQCC_MEM_TRACE("dump", "will allocate %lu size block", size);
319 /* standard behaviour */
322 GMQCC_MEM_TRACE("dump", "returning offset %lu", block);
323 return mem_heap + block + 4 * sizeof(mem_addr);
326 void mem_free(void *ptr) {
327 mem_addr start = (mem_addr)(ptr - mem_heap) - 4 * sizeof(mem_addr);
328 size_t size = GMQCC_MEM_READHEAP(start, mem_addr);
329 mem_addr addr = mem_getaddr(start, size);
330 int side = mem_getside(start, size);
335 "deallocating %s buddy (neighbour at %lu)",
336 (side == GMQCC_MEM_BSL) ? "left" : "right",
339 GMQCC_MEM_MARKFREE(start);
341 /* while free block merge */
342 while (GMQCC_MEM_BLOCKFREE(addr)) {
343 GMQCC_MEM_TRACE("dump", "merging ...");
344 mem_removeblock(addr, size);
347 start = addr < start ? addr : start;
350 if (size == GMQCC_MEM_READHEAP(mem_look, mem_addr))
353 addr = mem_getaddr(start, size);
354 GMQCC_MEM_TRACE("dump", "new block start is %lu, buddy at %lu", start, addr);
358 GMQCC_MEM_WRITEBS(start, size);
359 mem_addblock (start, size);