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)
166 mal.brk = mal.brk + PAGE_SIZE-1 & -PAGE_SIZE;
168 mal.brk = mal.brk + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
169 mal.heap = (void *)mal.brk;
173 if (n > SIZE_MAX - mal.brk - 2*PAGE_SIZE) goto fail;
174 new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE;
177 if (__brk(new) != new) {
178 size_t min = (size_t)PAGE_SIZE << mal.mmap_step/2;
179 n += -n & PAGE_SIZE-1;
180 if (n < min) n = min;
181 void *area = __mmap(0, n, PROT_READ|PROT_WRITE,
182 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
183 if (area == MAP_FAILED) goto fail;
186 area = (char *)area + SIZE_ALIGN - OVERHEAD;
189 w->psize = 0 | C_INUSE;
190 w->csize = n | C_INUSE;
192 w->psize = n | C_INUSE;
193 w->csize = 0 | C_INUSE;
195 unlock(mal.brk_lock);
200 w = MEM_TO_CHUNK(mal.heap);
201 w->psize = 0 | C_INUSE;
203 w = MEM_TO_CHUNK(new);
204 w->psize = n | C_INUSE;
205 w->csize = 0 | C_INUSE;
207 w = MEM_TO_CHUNK(mal.brk);
208 w->csize = n | C_INUSE;
211 unlock(mal.brk_lock);
215 unlock(mal.brk_lock);
220 static int adjust_size(size_t *n)
222 /* Result of pointer difference must fit in ptrdiff_t. */
223 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
232 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
236 static void unbin(struct chunk *c, int i)
238 if (c->prev == c->next)
239 a_and_64(&mal.binmap, ~(1ULL<<i));
240 c->prev->next = c->next;
241 c->next->prev = c->prev;
243 NEXT_CHUNK(c)->psize |= C_INUSE;
246 static int alloc_fwd(struct chunk *c)
250 while (!((k=c->csize) & C_INUSE)) {
263 static int alloc_rev(struct chunk *c)
267 while (!((k=c->psize) & C_INUSE)) {
271 unbin(PREV_CHUNK(c), i);
281 /* pretrim - trims a chunk _prior_ to removing it from its bin.
282 * Must be called with i as the ideal bin for size n, j the bin
283 * for the _free_ chunk self, and bin j locked. */
284 static int pretrim(struct chunk *self, size_t n, int i, int j)
287 struct chunk *next, *split;
289 /* We cannot pretrim if it would require re-binning. */
290 if (j < 40) return 0;
292 if (j != 63) return 0;
293 n1 = CHUNK_SIZE(self);
294 if (n1-n <= MMAP_THRESHOLD) return 0;
296 n1 = CHUNK_SIZE(self);
298 if (bin_index(n1-n) != j) return 0;
300 next = NEXT_CHUNK(self);
301 split = (void *)((char *)self + n);
303 split->prev = self->prev;
304 split->next = self->next;
305 split->prev->next = split;
306 split->next->prev = split;
307 split->psize = n | C_INUSE;
310 self->csize = n | C_INUSE;
314 static void trim(struct chunk *self, size_t n)
316 size_t n1 = CHUNK_SIZE(self);
317 struct chunk *next, *split;
319 if (n >= n1 - DONTCARE) return;
321 next = NEXT_CHUNK(self);
322 split = (void *)((char *)self + n);
324 split->psize = n | C_INUSE;
325 split->csize = n1-n | C_INUSE;
326 next->psize = n1-n | C_INUSE;
327 self->csize = n | C_INUSE;
329 free(CHUNK_TO_MEM(split));
332 void *malloc(size_t n)
337 if (adjust_size(&n) < 0) return 0;
339 if (n > MMAP_THRESHOLD) {
340 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
341 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
342 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
343 if (base == (void *)-1) return 0;
344 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
345 c->csize = len - (SIZE_ALIGN - OVERHEAD);
346 c->psize = SIZE_ALIGN - OVERHEAD;
347 return CHUNK_TO_MEM(c);
352 uint64_t mask = mal.binmap & -(1ULL<<i);
359 NEXT_CHUNK(x)->psize = c->csize =
360 x->csize + CHUNK_SIZE(c);
366 c = mal.bins[j].head;
367 if (c != BIN_TO_CHUNK(j)) {
368 if (!pretrim(c, n, i, j)) unbin(c, j);
375 /* Now patch up in case we over-allocated */
378 return CHUNK_TO_MEM(c);
381 void *realloc(void *p, size_t n)
383 struct chunk *self, *next;
387 if (!p) return malloc(n);
389 if (adjust_size(&n) < 0) return 0;
391 self = MEM_TO_CHUNK(p);
392 n1 = n0 = CHUNK_SIZE(self);
394 if (IS_MMAPPED(self)) {
395 size_t extra = self->psize;
396 char *base = (char *)self - extra;
397 size_t oldlen = n0 + extra;
398 size_t newlen = n + extra;
399 /* Crash on realloc of freed chunk */
400 if (extra & 1) a_crash();
401 if (newlen < PAGE_SIZE && (new = malloc(n))) {
402 memcpy(new, p, n-OVERHEAD);
406 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
407 if (oldlen == newlen) return p;
408 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
409 if (base == (void *)-1)
410 return newlen < oldlen ? p : 0;
411 self = (void *)(base + extra);
412 self->csize = newlen - extra;
413 return CHUNK_TO_MEM(self);
416 next = NEXT_CHUNK(self);
418 /* Crash on corrupted footer (likely from buffer overflow) */
419 if (next->psize != self->csize) a_crash();
421 /* Merge adjacent chunks if we need more space. This is not
422 * a waste of time even if we fail to get enough space, because our
423 * subsequent call to free would otherwise have to do the merge. */
424 if (n > n1 && alloc_fwd(next)) {
425 n1 += CHUNK_SIZE(next);
426 next = NEXT_CHUNK(next);
428 /* FIXME: find what's wrong here and reenable it..? */
429 if (0 && n > n1 && alloc_rev(self)) {
430 self = PREV_CHUNK(self);
431 n1 += CHUNK_SIZE(self);
433 self->csize = n1 | C_INUSE;
434 next->psize = n1 | C_INUSE;
436 /* If we got enough space, split off the excess and return */
438 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
440 return CHUNK_TO_MEM(self);
443 /* As a last resort, allocate a new chunk and copy to it. */
444 new = malloc(n-OVERHEAD);
446 memcpy(new, p, n0-OVERHEAD);
447 free(CHUNK_TO_MEM(self));
453 struct chunk *self = MEM_TO_CHUNK(p);
455 size_t final_size, new_size, size;
461 if (IS_MMAPPED(self)) {
462 size_t extra = self->psize;
463 char *base = (char *)self - extra;
464 size_t len = CHUNK_SIZE(self) + extra;
465 /* Crash on double free */
466 if (extra & 1) a_crash();
471 final_size = new_size = CHUNK_SIZE(self);
472 next = NEXT_CHUNK(self);
474 /* Crash on corrupted footer (likely from buffer overflow) */
475 if (next->psize != self->csize) a_crash();
478 /* Replace middle of large chunks with fresh zero pages */
479 if (reclaim && (self->psize & next->csize & C_INUSE)) {
480 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
481 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
483 __madvise((void *)a, b-a, MADV_DONTNEED);
485 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
486 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
490 if (self->psize & next->csize & C_INUSE) {
491 self->csize = final_size | C_INUSE;
492 next->psize = final_size | C_INUSE;
493 i = bin_index(final_size);
496 if (self->psize & next->csize & C_INUSE)
498 unlock(mal.free_lock);
502 if (alloc_rev(self)) {
503 self = PREV_CHUNK(self);
504 size = CHUNK_SIZE(self);
506 if (new_size+size > RECLAIM && (new_size+size^size) > size)
510 if (alloc_fwd(next)) {
511 size = CHUNK_SIZE(next);
513 if (new_size+size > RECLAIM && (new_size+size^size) > size)
515 next = NEXT_CHUNK(next);
519 self->csize = final_size;
520 next->psize = final_size;
521 unlock(mal.free_lock);
523 self->next = BIN_TO_CHUNK(i);
524 self->prev = mal.bins[i].tail;
525 self->next->prev = self;
526 self->prev->next = self;
528 if (!(mal.binmap & 1ULL<<i))
529 a_or_64(&mal.binmap, 1ULL<<i);