10 #include "pthread_impl.h"
12 #if defined(__GNUC__) && defined(__PIC__)
13 #define inline inline __attribute__((always_inline))
16 uintptr_t __brk(uintptr_t);
17 void *__mmap(void *, size_t, int, int, int, off_t);
18 int __munmap(void *, size_t);
19 void *__mremap(void *, size_t, size_t, int, ...);
20 int __madvise(void *, size_t, int);
24 struct chunk *next, *prev;
36 volatile uint64_t binmap;
38 volatile int brk_lock[2];
39 volatile int free_lock[2];
44 #define SIZE_ALIGN (4*sizeof(size_t))
45 #define SIZE_MASK (-SIZE_ALIGN)
46 #define OVERHEAD (2*sizeof(size_t))
47 #define MMAP_THRESHOLD (0x1c00*SIZE_ALIGN)
49 #define RECLAIM 163840
51 #define CHUNK_SIZE(c) ((c)->csize & -2)
52 #define CHUNK_PSIZE(c) ((c)->psize & -2)
53 #define PREV_CHUNK(c) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c)))
54 #define NEXT_CHUNK(c) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c)))
55 #define MEM_TO_CHUNK(p) (struct chunk *)((char *)(p) - OVERHEAD)
56 #define CHUNK_TO_MEM(c) (void *)((char *)(c) + OVERHEAD)
57 #define BIN_TO_CHUNK(i) (MEM_TO_CHUNK(&mal.bins[i].head))
59 #define C_INUSE ((size_t)1)
61 #define IS_MMAPPED(c) !((c)->csize & (C_INUSE))
64 /* Synchronization tools */
66 static inline void lock(volatile int *lk)
68 if (libc.threads_minus_1)
69 while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
72 static inline void unlock(volatile int *lk)
76 if (lk[1]) __wake(lk, 1, 1);
80 static inline void lock_bin(int i)
82 lock(mal.bins[i].lock);
83 if (!mal.bins[i].head)
84 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
87 static inline void unlock_bin(int i)
89 unlock(mal.bins[i].lock);
92 static int first_set(uint64_t x)
97 static const char debruijn64[64] = {
98 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
99 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
100 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
101 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
103 static const char debruijn32[32] = {
104 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
105 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
107 if (sizeof(long) < 8) {
111 return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
113 return debruijn32[(y&-y)*0x076be629 >> 27];
115 return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
119 static int bin_index(size_t x)
121 x = x / SIZE_ALIGN - 1;
122 if (x <= 32) return x;
123 if (x > 0x1c00) return 63;
124 return ((union { float v; uint32_t r; }){(int)x}.r>>21) - 496;
127 static int bin_index_up(size_t x)
129 x = x / SIZE_ALIGN - 1;
130 if (x <= 32) return x;
131 return ((union { float v; uint32_t r; }){(int)x}.r+0x1fffff>>21) - 496;
135 void __dump_heap(int x)
139 for (c = (void *)mal.heap; CHUNK_SIZE(c); c = NEXT_CHUNK(c))
140 fprintf(stderr, "base %p size %zu (%d) flags %d/%d\n",
141 c, CHUNK_SIZE(c), bin_index(CHUNK_SIZE(c)),
143 NEXT_CHUNK(c)->psize & 15);
144 for (i=0; i<64; i++) {
145 if (mal.bins[i].head != BIN_TO_CHUNK(i) && mal.bins[i].head) {
146 fprintf(stderr, "bin %d: %p\n", i, mal.bins[i].head);
147 if (!(mal.binmap & 1ULL<<i))
148 fprintf(stderr, "missing from binmap!\n");
149 } else if (mal.binmap & 1ULL<<i)
150 fprintf(stderr, "binmap wrongly contains %d!\n", i);
155 static struct chunk *expand_heap(size_t n)
162 if (n > SIZE_MAX - mal.brk - 2*PAGE_SIZE) goto fail;
163 new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE;
166 if (__brk(new) != new) {
167 size_t min = (size_t)PAGE_SIZE << mal.mmap_step/2;
168 n += -n & PAGE_SIZE-1;
169 if (n < min) n = min;
170 void *area = __mmap(0, n, PROT_READ|PROT_WRITE,
171 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
172 if (area == MAP_FAILED) goto fail;
175 area = (char *)area + SIZE_ALIGN - OVERHEAD;
178 w->psize = 0 | C_INUSE;
179 w->csize = n | C_INUSE;
181 w->psize = n | C_INUSE;
182 w->csize = 0 | C_INUSE;
184 unlock(mal.brk_lock);
189 w = MEM_TO_CHUNK(new);
190 w->psize = n | C_INUSE;
191 w->csize = 0 | C_INUSE;
193 w = MEM_TO_CHUNK(mal.brk);
194 w->csize = n | C_INUSE;
197 unlock(mal.brk_lock);
201 unlock(mal.brk_lock);
206 static int init_malloc(size_t n)
208 static volatile int init, waiters;
212 if (init == 2) return 0;
214 while ((state=a_swap(&init, 1)) == 1)
215 __wait(&init, &waiters, 1, 1);
223 mal.brk = mal.brk + PAGE_SIZE-1 & -PAGE_SIZE;
225 mal.brk = mal.brk + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
231 if (waiters) __wake(&init, 1, 1);
235 mal.heap = (void *)c;
236 c->psize = 0 | C_INUSE;
237 free(CHUNK_TO_MEM(c));
240 if (waiters) __wake(&init, -1, 1);
244 static int adjust_size(size_t *n)
246 /* Result of pointer difference must fit in ptrdiff_t. */
247 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
256 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
260 static void unbin(struct chunk *c, int i)
262 if (c->prev == c->next)
263 a_and_64(&mal.binmap, ~(1ULL<<i));
264 c->prev->next = c->next;
265 c->next->prev = c->prev;
267 NEXT_CHUNK(c)->psize |= C_INUSE;
270 static int alloc_fwd(struct chunk *c)
274 while (!((k=c->csize) & C_INUSE)) {
287 static int alloc_rev(struct chunk *c)
291 while (!((k=c->psize) & C_INUSE)) {
295 unbin(PREV_CHUNK(c), i);
305 /* pretrim - trims a chunk _prior_ to removing it from its bin.
306 * Must be called with i as the ideal bin for size n, j the bin
307 * for the _free_ chunk self, and bin j locked. */
308 static int pretrim(struct chunk *self, size_t n, int i, int j)
311 struct chunk *next, *split;
313 /* We cannot pretrim if it would require re-binning. */
314 if (j < 40) return 0;
316 if (j != 63) return 0;
317 n1 = CHUNK_SIZE(self);
318 if (n1-n <= MMAP_THRESHOLD) return 0;
320 n1 = CHUNK_SIZE(self);
322 if (bin_index(n1-n) != j) return 0;
324 next = NEXT_CHUNK(self);
325 split = (void *)((char *)self + n);
327 split->prev = self->prev;
328 split->next = self->next;
329 split->prev->next = split;
330 split->next->prev = split;
331 split->psize = n | C_INUSE;
334 self->csize = n | C_INUSE;
338 static void trim(struct chunk *self, size_t n)
340 size_t n1 = CHUNK_SIZE(self);
341 struct chunk *next, *split;
343 if (n >= n1 - DONTCARE) return;
345 next = NEXT_CHUNK(self);
346 split = (void *)((char *)self + n);
348 split->psize = n | C_INUSE;
349 split->csize = n1-n | C_INUSE;
350 next->psize = n1-n | C_INUSE;
351 self->csize = n | C_INUSE;
353 free(CHUNK_TO_MEM(split));
356 void *malloc(size_t n)
361 if (adjust_size(&n) < 0) return 0;
363 if (n > MMAP_THRESHOLD) {
364 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
365 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
366 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
367 if (base == (void *)-1) return 0;
368 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
369 c->csize = len - (SIZE_ALIGN - OVERHEAD);
370 c->psize = SIZE_ALIGN - OVERHEAD;
371 return CHUNK_TO_MEM(c);
376 uint64_t mask = mal.binmap & -(1ULL<<i);
378 if (init_malloc(n) > 0) continue;
384 NEXT_CHUNK(x)->psize = c->csize =
385 x->csize + CHUNK_SIZE(c);
391 c = mal.bins[j].head;
392 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->csize)) {
393 if (!pretrim(c, n, i, j)) unbin(c, j);
400 /* Now patch up in case we over-allocated */
403 return CHUNK_TO_MEM(c);
406 void *realloc(void *p, size_t n)
408 struct chunk *self, *next;
412 if (!p) return malloc(n);
414 if (adjust_size(&n) < 0) return 0;
416 self = MEM_TO_CHUNK(p);
417 n1 = n0 = CHUNK_SIZE(self);
419 if (IS_MMAPPED(self)) {
420 size_t extra = self->psize;
421 char *base = (char *)self - extra;
422 size_t oldlen = n0 + extra;
423 size_t newlen = n + extra;
424 /* Crash on realloc of freed chunk */
425 if (extra & 1) a_crash();
426 if (newlen < PAGE_SIZE && (new = malloc(n))) {
427 memcpy(new, p, n-OVERHEAD);
431 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
432 if (oldlen == newlen) return p;
433 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
434 if (base == (void *)-1)
435 return newlen < oldlen ? p : 0;
436 self = (void *)(base + extra);
437 self->csize = newlen - extra;
438 return CHUNK_TO_MEM(self);
441 next = NEXT_CHUNK(self);
443 /* Crash on corrupted footer (likely from buffer overflow) */
444 if (next->psize != self->csize) a_crash();
446 /* Merge adjacent chunks if we need more space. This is not
447 * a waste of time even if we fail to get enough space, because our
448 * subsequent call to free would otherwise have to do the merge. */
449 if (n > n1 && alloc_fwd(next)) {
450 n1 += CHUNK_SIZE(next);
451 next = NEXT_CHUNK(next);
453 /* FIXME: find what's wrong here and reenable it..? */
454 if (0 && n > n1 && alloc_rev(self)) {
455 self = PREV_CHUNK(self);
456 n1 += CHUNK_SIZE(self);
458 self->csize = n1 | C_INUSE;
459 next->psize = n1 | C_INUSE;
461 /* If we got enough space, split off the excess and return */
463 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
465 return CHUNK_TO_MEM(self);
468 /* As a last resort, allocate a new chunk and copy to it. */
469 new = malloc(n-OVERHEAD);
471 memcpy(new, p, n0-OVERHEAD);
472 free(CHUNK_TO_MEM(self));
478 struct chunk *self = MEM_TO_CHUNK(p);
480 size_t final_size, new_size, size;
486 if (IS_MMAPPED(self)) {
487 size_t extra = self->psize;
488 char *base = (char *)self - extra;
489 size_t len = CHUNK_SIZE(self) + extra;
490 /* Crash on double free */
491 if (extra & 1) a_crash();
496 final_size = new_size = CHUNK_SIZE(self);
497 next = NEXT_CHUNK(self);
499 /* Crash on corrupted footer (likely from buffer overflow) */
500 if (next->psize != self->csize) a_crash();
503 /* Replace middle of large chunks with fresh zero pages */
504 if (reclaim && (self->psize & next->csize & C_INUSE)) {
505 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
506 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
508 __madvise((void *)a, b-a, MADV_DONTNEED);
510 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
511 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
515 if (self->psize & next->csize & C_INUSE) {
516 self->csize = final_size | C_INUSE;
517 next->psize = final_size | C_INUSE;
518 i = bin_index(final_size);
521 if (self->psize & next->csize & C_INUSE)
523 unlock(mal.free_lock);
527 if (alloc_rev(self)) {
528 self = PREV_CHUNK(self);
529 size = CHUNK_SIZE(self);
531 if (new_size+size > RECLAIM && (new_size+size^size) > size)
535 if (alloc_fwd(next)) {
536 size = CHUNK_SIZE(next);
538 if (new_size+size > RECLAIM && (new_size+size^size) > size)
540 next = NEXT_CHUNK(next);
544 self->csize = final_size;
545 next->psize = final_size;
546 unlock(mal.free_lock);
548 self->next = BIN_TO_CHUNK(i);
549 self->prev = mal.bins[i].tail;
550 self->next->prev = self;
551 self->prev->next = self;
553 if (!(mal.binmap & 1ULL<<i))
554 a_or_64(&mal.binmap, 1ULL<<i);