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 int is_near_stack(uintptr_t b)
157 const uintptr_t c = 8<<20;
158 uintptr_t a = (uintptr_t)libc.auxv;
159 uintptr_t d = (uintptr_t)&b;
160 return a-b<=c || d-b<=c;
163 static struct chunk *expand_heap(size_t n)
174 mal.brk = mal.brk + PAGE_SIZE-1 & -PAGE_SIZE;
176 mal.brk = mal.brk + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
177 mal.heap = (void *)mal.brk;
181 if (n > SIZE_MAX - mal.brk - 2*PAGE_SIZE) goto fail;
182 new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE;
185 if (is_near_stack(mal.brk) || __brk(new) != new) {
186 size_t min = (size_t)PAGE_SIZE << mal.mmap_step/2;
187 n += -n & PAGE_SIZE-1;
188 if (n < min) n = min;
189 void *area = __mmap(0, n, PROT_READ|PROT_WRITE,
190 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
191 if (area == MAP_FAILED) goto fail;
194 area = (char *)area + SIZE_ALIGN - OVERHEAD;
197 w->psize = 0 | C_INUSE;
198 w->csize = n | C_INUSE;
200 w->psize = n | C_INUSE;
201 w->csize = 0 | C_INUSE;
203 unlock(mal.brk_lock);
208 w = MEM_TO_CHUNK(mal.heap);
209 w->psize = 0 | C_INUSE;
211 w = MEM_TO_CHUNK(new);
212 w->psize = n | C_INUSE;
213 w->csize = 0 | C_INUSE;
215 w = MEM_TO_CHUNK(mal.brk);
216 w->csize = n | C_INUSE;
219 unlock(mal.brk_lock);
223 unlock(mal.brk_lock);
228 static int adjust_size(size_t *n)
230 /* Result of pointer difference must fit in ptrdiff_t. */
231 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
240 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
244 static void unbin(struct chunk *c, int i)
246 if (c->prev == c->next)
247 a_and_64(&mal.binmap, ~(1ULL<<i));
248 c->prev->next = c->next;
249 c->next->prev = c->prev;
251 NEXT_CHUNK(c)->psize |= C_INUSE;
254 static int alloc_fwd(struct chunk *c)
258 while (!((k=c->csize) & C_INUSE)) {
271 static int alloc_rev(struct chunk *c)
275 while (!((k=c->psize) & C_INUSE)) {
279 unbin(PREV_CHUNK(c), i);
289 /* pretrim - trims a chunk _prior_ to removing it from its bin.
290 * Must be called with i as the ideal bin for size n, j the bin
291 * for the _free_ chunk self, and bin j locked. */
292 static int pretrim(struct chunk *self, size_t n, int i, int j)
295 struct chunk *next, *split;
297 /* We cannot pretrim if it would require re-binning. */
298 if (j < 40) return 0;
300 if (j != 63) return 0;
301 n1 = CHUNK_SIZE(self);
302 if (n1-n <= MMAP_THRESHOLD) return 0;
304 n1 = CHUNK_SIZE(self);
306 if (bin_index(n1-n) != j) return 0;
308 next = NEXT_CHUNK(self);
309 split = (void *)((char *)self + n);
311 split->prev = self->prev;
312 split->next = self->next;
313 split->prev->next = split;
314 split->next->prev = split;
315 split->psize = n | C_INUSE;
318 self->csize = n | C_INUSE;
322 static void trim(struct chunk *self, size_t n)
324 size_t n1 = CHUNK_SIZE(self);
325 struct chunk *next, *split;
327 if (n >= n1 - DONTCARE) return;
329 next = NEXT_CHUNK(self);
330 split = (void *)((char *)self + n);
332 split->psize = n | C_INUSE;
333 split->csize = n1-n | C_INUSE;
334 next->psize = n1-n | C_INUSE;
335 self->csize = n | C_INUSE;
337 free(CHUNK_TO_MEM(split));
340 void *malloc(size_t n)
345 if (adjust_size(&n) < 0) return 0;
347 if (n > MMAP_THRESHOLD) {
348 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
349 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
350 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
351 if (base == (void *)-1) return 0;
352 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
353 c->csize = len - (SIZE_ALIGN - OVERHEAD);
354 c->psize = SIZE_ALIGN - OVERHEAD;
355 return CHUNK_TO_MEM(c);
360 uint64_t mask = mal.binmap & -(1ULL<<i);
367 NEXT_CHUNK(x)->psize = c->csize =
368 x->csize + CHUNK_SIZE(c);
374 c = mal.bins[j].head;
375 if (c != BIN_TO_CHUNK(j)) {
376 if (!pretrim(c, n, i, j)) unbin(c, j);
383 /* Now patch up in case we over-allocated */
386 return CHUNK_TO_MEM(c);
389 void *realloc(void *p, size_t n)
391 struct chunk *self, *next;
395 if (!p) return malloc(n);
397 if (adjust_size(&n) < 0) return 0;
399 self = MEM_TO_CHUNK(p);
400 n1 = n0 = CHUNK_SIZE(self);
402 if (IS_MMAPPED(self)) {
403 size_t extra = self->psize;
404 char *base = (char *)self - extra;
405 size_t oldlen = n0 + extra;
406 size_t newlen = n + extra;
407 /* Crash on realloc of freed chunk */
408 if (extra & 1) a_crash();
409 if (newlen < PAGE_SIZE && (new = malloc(n))) {
410 memcpy(new, p, n-OVERHEAD);
414 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
415 if (oldlen == newlen) return p;
416 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
417 if (base == (void *)-1)
418 return newlen < oldlen ? p : 0;
419 self = (void *)(base + extra);
420 self->csize = newlen - extra;
421 return CHUNK_TO_MEM(self);
424 next = NEXT_CHUNK(self);
426 /* Crash on corrupted footer (likely from buffer overflow) */
427 if (next->psize != self->csize) a_crash();
429 /* Merge adjacent chunks if we need more space. This is not
430 * a waste of time even if we fail to get enough space, because our
431 * subsequent call to free would otherwise have to do the merge. */
432 if (n > n1 && alloc_fwd(next)) {
433 n1 += CHUNK_SIZE(next);
434 next = NEXT_CHUNK(next);
436 /* FIXME: find what's wrong here and reenable it..? */
437 if (0 && n > n1 && alloc_rev(self)) {
438 self = PREV_CHUNK(self);
439 n1 += CHUNK_SIZE(self);
441 self->csize = n1 | C_INUSE;
442 next->psize = n1 | C_INUSE;
444 /* If we got enough space, split off the excess and return */
446 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
448 return CHUNK_TO_MEM(self);
451 /* As a last resort, allocate a new chunk and copy to it. */
452 new = malloc(n-OVERHEAD);
454 memcpy(new, p, n0-OVERHEAD);
455 free(CHUNK_TO_MEM(self));
461 struct chunk *self = MEM_TO_CHUNK(p);
463 size_t final_size, new_size, size;
469 if (IS_MMAPPED(self)) {
470 size_t extra = self->psize;
471 char *base = (char *)self - extra;
472 size_t len = CHUNK_SIZE(self) + extra;
473 /* Crash on double free */
474 if (extra & 1) a_crash();
479 final_size = new_size = CHUNK_SIZE(self);
480 next = NEXT_CHUNK(self);
482 /* Crash on corrupted footer (likely from buffer overflow) */
483 if (next->psize != self->csize) a_crash();
486 /* Replace middle of large chunks with fresh zero pages */
487 if (reclaim && (self->psize & next->csize & C_INUSE)) {
488 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
489 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
491 __madvise((void *)a, b-a, MADV_DONTNEED);
493 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
494 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
498 if (self->psize & next->csize & C_INUSE) {
499 self->csize = final_size | C_INUSE;
500 next->psize = final_size | C_INUSE;
501 i = bin_index(final_size);
504 if (self->psize & next->csize & C_INUSE)
506 unlock(mal.free_lock);
510 if (alloc_rev(self)) {
511 self = PREV_CHUNK(self);
512 size = CHUNK_SIZE(self);
514 if (new_size+size > RECLAIM && (new_size+size^size) > size)
518 if (alloc_fwd(next)) {
519 size = CHUNK_SIZE(next);
521 if (new_size+size > RECLAIM && (new_size+size^size) > size)
523 next = NEXT_CHUNK(next);
527 self->csize = final_size;
528 next->psize = final_size;
529 unlock(mal.free_lock);
531 self->next = BIN_TO_CHUNK(i);
532 self->prev = mal.bins[i].tail;
533 self->next->prev = self;
534 self->prev->next = self;
536 if (!(mal.binmap & 1ULL<<i))
537 a_or_64(&mal.binmap, 1ULL<<i);