10 #include "pthread_impl.h"
12 uintptr_t __brk(uintptr_t);
13 void *__mmap(void *, size_t, int, int, int, off_t);
14 int __munmap(void *, size_t);
15 void *__mremap(void *, size_t, size_t, int, ...);
16 int __madvise(void *, size_t, int);
20 struct chunk *next, *prev;
39 #define SIZE_ALIGN (4*sizeof(size_t))
40 #define SIZE_MASK (-SIZE_ALIGN)
41 #define OVERHEAD (2*sizeof(size_t))
42 #define MMAP_THRESHOLD (0x1c00*SIZE_ALIGN)
44 #define RECLAIM 163840
46 #define CHUNK_SIZE(c) ((c)->csize & -2)
47 #define CHUNK_PSIZE(c) ((c)->psize & -2)
48 #define PREV_CHUNK(c) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c)))
49 #define NEXT_CHUNK(c) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c)))
50 #define MEM_TO_CHUNK(p) (struct chunk *)((char *)(p) - OVERHEAD)
51 #define CHUNK_TO_MEM(c) (void *)((char *)(c) + OVERHEAD)
52 #define BIN_TO_CHUNK(i) (MEM_TO_CHUNK(&mal.bins[i].head))
54 #define C_INUSE ((size_t)1)
56 #define IS_MMAPPED(c) !((c)->csize & (C_INUSE))
59 /* Synchronization tools */
61 static void lock(volatile int *lk)
63 if (!libc.threads_minus_1) return;
64 while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
67 static void unlock(volatile int *lk)
69 if (!libc.threads_minus_1) return;
71 if (lk[1]) __wake(lk, 1, 1);
74 static void lock_bin(int i)
76 if (libc.threads_minus_1)
77 lock(mal.bins[i].lock);
78 if (!mal.bins[i].head)
79 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
82 static void unlock_bin(int i)
84 if (!libc.threads_minus_1) return;
85 unlock(mal.bins[i].lock);
88 static int first_set(uint64_t x)
93 static const char debruijn64[64] = {
94 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
95 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
96 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
97 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
99 static const char debruijn32[32] = {
100 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
101 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
103 if (sizeof(long) < 8) {
107 return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
109 return debruijn32[(y&-y)*0x076be629 >> 27];
111 return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
115 static int bin_index(size_t x)
117 x = x / SIZE_ALIGN - 1;
118 if (x <= 32) return x;
119 if (x > 0x1c00) return 63;
120 return ((union { float v; uint32_t r; }){(int)x}.r>>21) - 496;
123 static int bin_index_up(size_t x)
125 x = x / SIZE_ALIGN - 1;
126 if (x <= 32) return x;
127 return ((union { float v; uint32_t r; }){(int)x}.r+0x1fffff>>21) - 496;
131 void __dump_heap(int x)
135 for (c = (void *)mal.heap; CHUNK_SIZE(c); c = NEXT_CHUNK(c))
136 fprintf(stderr, "base %p size %zu (%d) flags %d/%d\n",
137 c, CHUNK_SIZE(c), bin_index(CHUNK_SIZE(c)),
139 NEXT_CHUNK(c)->psize & 15);
140 for (i=0; i<64; i++) {
141 if (mal.bins[i].head != BIN_TO_CHUNK(i) && mal.bins[i].head) {
142 fprintf(stderr, "bin %d: %p\n", i, mal.bins[i].head);
143 if (!(mal.binmap & 1ULL<<i))
144 fprintf(stderr, "missing from binmap!\n");
145 } else if (mal.binmap & 1ULL<<i)
146 fprintf(stderr, "binmap wrongly contains %d!\n", i);
151 static struct chunk *expand_heap(size_t n)
158 if (n > SIZE_MAX - mal.brk - 2*PAGE_SIZE) goto fail;
159 new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE;
162 if (__brk(new) != new) goto fail;
164 w = MEM_TO_CHUNK(new);
165 w->psize = n | C_INUSE;
166 w->csize = 0 | C_INUSE;
168 w = MEM_TO_CHUNK(mal.brk);
169 w->csize = n | C_INUSE;
172 unlock(mal.brk_lock);
176 unlock(mal.brk_lock);
180 static int init_malloc(size_t n)
182 static int init, waiters;
186 if (init == 2) return 0;
188 while ((state=a_swap(&init, 1)) == 1)
189 __wait(&init, &waiters, 1, 1);
195 mal.brk = __brk(0) + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
201 if (waiters) __wake(&init, 1, 1);
205 mal.heap = (void *)c;
206 c->psize = 0 | C_INUSE;
207 free(CHUNK_TO_MEM(c));
210 if (waiters) __wake(&init, -1, 1);
214 static int adjust_size(size_t *n)
216 /* Result of pointer difference must fit in ptrdiff_t. */
217 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
226 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
230 static void unbin(struct chunk *c, int i)
232 if (c->prev == c->next)
233 a_and_64(&mal.binmap, ~(1ULL<<i));
234 c->prev->next = c->next;
235 c->next->prev = c->prev;
237 NEXT_CHUNK(c)->psize |= C_INUSE;
240 static int alloc_fwd(struct chunk *c)
244 while (!((k=c->csize) & C_INUSE)) {
257 static int alloc_rev(struct chunk *c)
261 while (!((k=c->psize) & C_INUSE)) {
265 unbin(PREV_CHUNK(c), i);
275 /* pretrim - trims a chunk _prior_ to removing it from its bin.
276 * Must be called with i as the ideal bin for size n, j the bin
277 * for the _free_ chunk self, and bin j locked. */
278 static int pretrim(struct chunk *self, size_t n, int i, int j)
281 struct chunk *next, *split;
283 /* We cannot pretrim if it would require re-binning. */
284 if (j < 40) return 0;
286 if (j != 63) return 0;
287 n1 = CHUNK_SIZE(self);
288 if (n1-n <= MMAP_THRESHOLD) return 0;
290 n1 = CHUNK_SIZE(self);
292 if (bin_index(n1-n) != j) return 0;
294 next = NEXT_CHUNK(self);
295 split = (void *)((char *)self + n);
297 split->prev = self->prev;
298 split->next = self->next;
299 split->prev->next = split;
300 split->next->prev = split;
301 split->psize = n | C_INUSE;
304 self->csize = n | C_INUSE;
308 static void trim(struct chunk *self, size_t n)
310 size_t n1 = CHUNK_SIZE(self);
311 struct chunk *next, *split;
313 if (n >= n1 - DONTCARE) return;
315 next = NEXT_CHUNK(self);
316 split = (void *)((char *)self + n);
318 split->psize = n | C_INUSE;
319 split->csize = n1-n | C_INUSE;
320 next->psize = n1-n | C_INUSE;
321 self->csize = n | C_INUSE;
323 free(CHUNK_TO_MEM(split));
326 void *malloc(size_t n)
331 if (adjust_size(&n) < 0) return 0;
333 if (n > MMAP_THRESHOLD) {
334 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
335 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
336 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
337 if (base == (void *)-1) return 0;
338 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
339 c->csize = len - (SIZE_ALIGN - OVERHEAD);
340 c->psize = SIZE_ALIGN - OVERHEAD;
341 return CHUNK_TO_MEM(c);
346 uint64_t mask = mal.binmap & -(1ULL<<i);
348 if (init_malloc(n) > 0) continue;
354 NEXT_CHUNK(x)->psize = c->csize =
355 x->csize + CHUNK_SIZE(c);
361 c = mal.bins[j].head;
362 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->csize)) {
363 if (!pretrim(c, n, i, j)) unbin(c, j);
370 /* Now patch up in case we over-allocated */
373 return CHUNK_TO_MEM(c);
376 void *realloc(void *p, size_t n)
378 struct chunk *self, *next;
382 if (!p) return malloc(n);
384 if (adjust_size(&n) < 0) return 0;
386 self = MEM_TO_CHUNK(p);
387 n1 = n0 = CHUNK_SIZE(self);
389 if (IS_MMAPPED(self)) {
390 size_t extra = self->psize;
391 char *base = (char *)self - extra;
392 size_t oldlen = n0 + extra;
393 size_t newlen = n + extra;
394 /* Crash on realloc of freed chunk */
395 if (extra & 1) a_crash();
396 if (newlen < PAGE_SIZE && (new = malloc(n))) {
397 memcpy(new, p, n-OVERHEAD);
401 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
402 if (oldlen == newlen) return p;
403 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
404 if (base == (void *)-1)
405 return newlen < oldlen ? p : 0;
406 self = (void *)(base + extra);
407 self->csize = newlen - extra;
408 return CHUNK_TO_MEM(self);
411 next = NEXT_CHUNK(self);
413 /* Merge adjacent chunks if we need more space. This is not
414 * a waste of time even if we fail to get enough space, because our
415 * subsequent call to free would otherwise have to do the merge. */
416 if (n > n1 && alloc_fwd(next)) {
417 n1 += CHUNK_SIZE(next);
418 next = NEXT_CHUNK(next);
420 /* FIXME: find what's wrong here and reenable it..? */
421 if (0 && n > n1 && alloc_rev(self)) {
422 self = PREV_CHUNK(self);
423 n1 += CHUNK_SIZE(self);
425 self->csize = n1 | C_INUSE;
426 next->psize = n1 | C_INUSE;
428 /* If we got enough space, split off the excess and return */
430 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
432 return CHUNK_TO_MEM(self);
435 /* As a last resort, allocate a new chunk and copy to it. */
436 new = malloc(n-OVERHEAD);
438 memcpy(new, p, n0-OVERHEAD);
439 free(CHUNK_TO_MEM(self));
445 struct chunk *self = MEM_TO_CHUNK(p);
447 size_t final_size, new_size, size;
453 if (IS_MMAPPED(self)) {
454 size_t extra = self->psize;
455 char *base = (char *)self - extra;
456 size_t len = CHUNK_SIZE(self) + extra;
457 /* Crash on double free */
458 if (extra & 1) a_crash();
463 final_size = new_size = CHUNK_SIZE(self);
464 next = NEXT_CHUNK(self);
467 /* Replace middle of large chunks with fresh zero pages */
468 if (reclaim && (self->psize & next->csize & C_INUSE)) {
469 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
470 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
472 __madvise((void *)a, b-a, MADV_DONTNEED);
474 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
475 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
479 if (self->psize & next->csize & C_INUSE) {
480 self->csize = final_size | C_INUSE;
481 next->psize = final_size | C_INUSE;
482 i = bin_index(final_size);
485 if (self->psize & next->csize & C_INUSE)
487 unlock(mal.free_lock);
491 if (alloc_rev(self)) {
492 self = PREV_CHUNK(self);
493 size = CHUNK_SIZE(self);
495 if (new_size+size > RECLAIM && (new_size+size^size) > size)
499 if (alloc_fwd(next)) {
500 size = CHUNK_SIZE(next);
502 if (new_size+size > RECLAIM && (new_size+size^size) > size)
504 next = NEXT_CHUNK(next);
508 self->csize = final_size;
509 next->psize = final_size;
510 unlock(mal.free_lock);
512 self->next = BIN_TO_CHUNK(i);
513 self->prev = mal.bins[i].tail;
514 self->next->prev = self;
515 self->prev->next = self;
517 if (!(mal.binmap & 1ULL<<i))
518 a_or_64(&mal.binmap, 1ULL<<i);