10 #include "pthread_impl.h"
11 #include "malloc_impl.h"
13 #if defined(__GNUC__) && defined(__PIC__)
14 #define inline inline __attribute__((always_inline))
18 volatile uint64_t binmap;
20 volatile int split_merge_lock[2];
23 /* Synchronization tools */
25 static inline void lock(volatile int *lk)
27 int need_locks = libc.need_locks;
29 while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
30 if (need_locks < 0) libc.need_locks = 0;
34 static inline void unlock(volatile int *lk)
38 if (lk[1]) __wake(lk, 1, 1);
42 static inline void lock_bin(int i)
44 lock(mal.bins[i].lock);
45 if (!mal.bins[i].head)
46 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
49 static inline void unlock_bin(int i)
51 unlock(mal.bins[i].lock);
54 static int first_set(uint64_t x)
59 static const char debruijn64[64] = {
60 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
61 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
62 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
63 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
65 static const char debruijn32[32] = {
66 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
67 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
69 if (sizeof(long) < 8) {
73 return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
75 return debruijn32[(y&-y)*0x076be629 >> 27];
77 return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
81 static const unsigned char bin_tab[60] = {
82 32,33,34,35,36,36,37,37,38,38,39,39,
83 40,40,40,40,41,41,41,41,42,42,42,42,43,43,43,43,
84 44,44,44,44,44,44,44,44,45,45,45,45,45,45,45,45,
85 46,46,46,46,46,46,46,46,47,47,47,47,47,47,47,47,
88 static int bin_index(size_t x)
90 x = x / SIZE_ALIGN - 1;
91 if (x <= 32) return x;
92 if (x < 512) return bin_tab[x/8-4];
93 if (x > 0x1c00) return 63;
94 return bin_tab[x/128-4] + 16;
97 static int bin_index_up(size_t x)
99 x = x / SIZE_ALIGN - 1;
100 if (x <= 32) return x;
102 if (x < 512) return bin_tab[x/8-4] + 1;
103 return bin_tab[x/128-4] + 17;
107 void __dump_heap(int x)
111 for (c = (void *)mal.heap; CHUNK_SIZE(c); c = NEXT_CHUNK(c))
112 fprintf(stderr, "base %p size %zu (%d) flags %d/%d\n",
113 c, CHUNK_SIZE(c), bin_index(CHUNK_SIZE(c)),
115 NEXT_CHUNK(c)->psize & 15);
116 for (i=0; i<64; i++) {
117 if (mal.bins[i].head != BIN_TO_CHUNK(i) && mal.bins[i].head) {
118 fprintf(stderr, "bin %d: %p\n", i, mal.bins[i].head);
119 if (!(mal.binmap & 1ULL<<i))
120 fprintf(stderr, "missing from binmap!\n");
121 } else if (mal.binmap & 1ULL<<i)
122 fprintf(stderr, "binmap wrongly contains %d!\n", i);
127 /* This function returns true if the interval [old,new]
128 * intersects the 'len'-sized interval below &libc.auxv
129 * (interpreted as the main-thread stack) or below &b
130 * (the current stack). It is used to defend against
131 * buggy brk implementations that can cross the stack. */
133 static int traverses_stack_p(uintptr_t old, uintptr_t new)
135 const uintptr_t len = 8<<20;
138 b = (uintptr_t)libc.auxv;
139 a = b > len ? b-len : 0;
140 if (new>a && old<b) return 1;
143 a = b > len ? b-len : 0;
144 if (new>a && old<b) return 1;
149 /* Expand the heap in-place if brk can be used, or otherwise via mmap,
150 * using an exponential lower bound on growth by mmap to make
151 * fragmentation asymptotically irrelevant. The size argument is both
152 * an input and an output, since the caller needs to know the size
153 * allocated, which will be larger than requested due to page alignment
154 * and mmap minimum size rules. The caller is responsible for locking
155 * to prevent concurrent calls. */
157 static void *__expand_heap(size_t *pn)
159 static uintptr_t brk;
160 static unsigned mmap_step;
163 if (n > SIZE_MAX/2 - PAGE_SIZE) {
167 n += -n & PAGE_SIZE-1;
170 brk = __syscall(SYS_brk, 0);
171 brk += -brk & PAGE_SIZE-1;
174 if (n < SIZE_MAX-brk && !traverses_stack_p(brk, brk+n)
175 && __syscall(SYS_brk, brk+n)==brk+n) {
178 return (void *)(brk-n);
181 size_t min = (size_t)PAGE_SIZE << mmap_step/2;
182 if (n < min) n = min;
183 void *area = __mmap(0, n, PROT_READ|PROT_WRITE,
184 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
185 if (area == MAP_FAILED) return 0;
191 static struct chunk *expand_heap(size_t n)
197 /* The argument n already accounts for the caller's chunk
198 * overhead needs, but if the heap can't be extended in-place,
199 * we need room for an extra zero-sized sentinel chunk. */
202 p = __expand_heap(&n);
205 /* If not just expanding existing space, we need to make a
206 * new sentinel chunk below the allocated space. */
208 /* Valid/safe because of the prologue increment. */
210 p = (char *)p + SIZE_ALIGN;
212 w->psize = 0 | C_INUSE;
215 /* Record new heap end and fill in footer. */
217 w = MEM_TO_CHUNK(end);
218 w->psize = n | C_INUSE;
219 w->csize = 0 | C_INUSE;
221 /* Fill in header, which may be new or may be replacing a
222 * zero-size sentinel header at the old end-of-heap. */
224 w->csize = n | C_INUSE;
229 static int adjust_size(size_t *n)
231 /* Result of pointer difference must fit in ptrdiff_t. */
232 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
241 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
245 static void unbin(struct chunk *c, int i)
247 if (c->prev == c->next)
248 a_and_64(&mal.binmap, ~(1ULL<<i));
249 c->prev->next = c->next;
250 c->next->prev = c->prev;
252 NEXT_CHUNK(c)->psize |= C_INUSE;
255 static void bin_chunk(struct chunk *self, int i)
257 self->next = BIN_TO_CHUNK(i);
258 self->prev = mal.bins[i].tail;
259 self->next->prev = self;
260 self->prev->next = self;
261 if (self->prev == BIN_TO_CHUNK(i))
262 a_or_64(&mal.binmap, 1ULL<<i);
265 static void trim(struct chunk *self, size_t n)
267 size_t n1 = CHUNK_SIZE(self);
268 struct chunk *next, *split;
270 if (n >= n1 - DONTCARE) return;
272 next = NEXT_CHUNK(self);
273 split = (void *)((char *)self + n);
275 split->psize = n | C_INUSE;
278 self->csize = n | C_INUSE;
280 int i = bin_index(n1-n);
288 void *malloc(size_t n)
294 if (adjust_size(&n) < 0) return 0;
296 if (n > MMAP_THRESHOLD) {
297 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
298 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
299 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
300 if (base == (void *)-1) return 0;
301 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
302 c->csize = len - (SIZE_ALIGN - OVERHEAD);
303 c->psize = SIZE_ALIGN - OVERHEAD;
304 return CHUNK_TO_MEM(c);
308 if (i<63 && (mal.binmap & (1ULL<<i))) {
310 c = mal.bins[i].head;
311 if (c != BIN_TO_CHUNK(i) && CHUNK_SIZE(c)-n <= DONTCARE) {
314 return CHUNK_TO_MEM(c);
318 lock(mal.split_merge_lock);
319 for (mask = mal.binmap & -(1ULL<<i); mask; mask -= (mask&-mask)) {
322 c = mal.bins[j].head;
323 if (c != BIN_TO_CHUNK(j)) {
333 unlock(mal.split_merge_lock);
338 unlock(mal.split_merge_lock);
339 return CHUNK_TO_MEM(c);
342 int __malloc_allzerop(void *p)
344 return IS_MMAPPED(MEM_TO_CHUNK(p));
347 void *realloc(void *p, size_t n)
349 struct chunk *self, *next;
353 if (!p) return malloc(n);
355 if (adjust_size(&n) < 0) return 0;
357 self = MEM_TO_CHUNK(p);
358 n1 = n0 = CHUNK_SIZE(self);
360 if (n<=n0 && n0-n<=DONTCARE) return p;
362 if (IS_MMAPPED(self)) {
363 size_t extra = self->psize;
364 char *base = (char *)self - extra;
365 size_t oldlen = n0 + extra;
366 size_t newlen = n + extra;
367 /* Crash on realloc of freed chunk */
368 if (extra & 1) a_crash();
369 if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) {
373 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
374 if (oldlen == newlen) return p;
375 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
376 if (base == (void *)-1)
378 self = (void *)(base + extra);
379 self->csize = newlen - extra;
380 return CHUNK_TO_MEM(self);
383 next = NEXT_CHUNK(self);
385 /* Crash on corrupted footer (likely from buffer overflow) */
386 if (next->psize != self->csize) a_crash();
389 int i = bin_index_up(n);
390 int j = bin_index(n0);
391 if (i<j && (mal.binmap & (1ULL << i)))
393 struct chunk *split = (void *)((char *)self + n);
394 self->csize = split->psize = n | C_INUSE;
395 split->csize = next->psize = n0-n | C_INUSE;
397 return CHUNK_TO_MEM(self);
400 lock(mal.split_merge_lock);
402 size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);
404 int i = bin_index(nsize);
406 if (!(next->csize & C_INUSE)) {
409 next = NEXT_CHUNK(next);
410 self->csize = next->psize = n0+nsize | C_INUSE;
412 unlock(mal.split_merge_lock);
413 return CHUNK_TO_MEM(self);
417 unlock(mal.split_merge_lock);
420 /* As a last resort, allocate a new chunk and copy to it. */
421 new = malloc(n-OVERHEAD);
424 memcpy(new, p, (n<n0 ? n : n0) - OVERHEAD);
425 free(CHUNK_TO_MEM(self));
429 void __bin_chunk(struct chunk *self)
431 struct chunk *next = NEXT_CHUNK(self);
433 /* Crash on corrupted footer (likely from buffer overflow) */
434 if (next->psize != self->csize) a_crash();
436 lock(mal.split_merge_lock);
438 size_t osize = CHUNK_SIZE(self), size = osize;
440 /* Since we hold split_merge_lock, only transition from free to
441 * in-use can race; in-use to free is impossible */
442 size_t psize = self->psize & C_INUSE ? 0 : CHUNK_PSIZE(self);
443 size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);
446 int i = bin_index(psize);
448 if (!(self->psize & C_INUSE)) {
449 struct chunk *prev = PREV_CHUNK(self);
457 int i = bin_index(nsize);
459 if (!(next->csize & C_INUSE)) {
461 next = NEXT_CHUNK(next);
467 int i = bin_index(size);
473 unlock(mal.split_merge_lock);
475 /* Replace middle of large chunks with fresh zero pages */
476 if (size > RECLAIM && (size^(size-osize)) > size-osize) {
477 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
478 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
480 __madvise((void *)a, b-a, MADV_DONTNEED);
482 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
483 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
490 static void unmap_chunk(struct chunk *self)
492 size_t extra = self->psize;
493 char *base = (char *)self - extra;
494 size_t len = CHUNK_SIZE(self) + extra;
495 /* Crash on double free */
496 if (extra & 1) a_crash();
504 struct chunk *self = MEM_TO_CHUNK(p);
506 if (IS_MMAPPED(self))
512 void __malloc_donate(char *start, char *end)
514 size_t align_start_up = (SIZE_ALIGN-1) & (-(uintptr_t)start - OVERHEAD);
515 size_t align_end_down = (SIZE_ALIGN-1) & (uintptr_t)end;
517 /* Getting past this condition ensures that the padding for alignment
518 * and header overhead will not overflow and will leave a nonzero
519 * multiple of SIZE_ALIGN bytes between start and end. */
520 if (end - start <= OVERHEAD + align_start_up + align_end_down)
522 start += align_start_up + OVERHEAD;
523 end -= align_end_down;
525 struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end);
526 c->psize = n->csize = C_INUSE;
527 c->csize = n->psize = C_INUSE | (end-start);