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;
43 #define SIZE_ALIGN (4*sizeof(size_t))
44 #define SIZE_MASK (-SIZE_ALIGN)
45 #define OVERHEAD (2*sizeof(size_t))
46 #define MMAP_THRESHOLD (0x1c00*SIZE_ALIGN)
48 #define RECLAIM 163840
50 #define CHUNK_SIZE(c) ((c)->csize & -2)
51 #define CHUNK_PSIZE(c) ((c)->psize & -2)
52 #define PREV_CHUNK(c) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c)))
53 #define NEXT_CHUNK(c) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c)))
54 #define MEM_TO_CHUNK(p) (struct chunk *)((char *)(p) - OVERHEAD)
55 #define CHUNK_TO_MEM(c) (void *)((char *)(c) + OVERHEAD)
56 #define BIN_TO_CHUNK(i) (MEM_TO_CHUNK(&mal.bins[i].head))
58 #define C_INUSE ((size_t)1)
60 #define IS_MMAPPED(c) !((c)->csize & (C_INUSE))
63 /* Synchronization tools */
65 static inline void lock(volatile int *lk)
67 if (!libc.threads_minus_1) return;
68 while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
71 static inline void unlock(volatile int *lk)
73 if (!libc.threads_minus_1) return;
75 if (lk[1]) __wake(lk, 1, 1);
78 static inline void lock_bin(int i)
80 if (libc.threads_minus_1)
81 lock(mal.bins[i].lock);
82 if (!mal.bins[i].head)
83 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
86 static inline void unlock_bin(int i)
88 if (!libc.threads_minus_1) return;
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) goto fail;
168 w = MEM_TO_CHUNK(new);
169 w->psize = n | C_INUSE;
170 w->csize = 0 | C_INUSE;
172 w = MEM_TO_CHUNK(mal.brk);
173 w->csize = n | C_INUSE;
176 unlock(mal.brk_lock);
180 unlock(mal.brk_lock);
184 static int init_malloc(size_t n)
186 static int init, waiters;
190 if (init == 2) return 0;
192 while ((state=a_swap(&init, 1)) == 1)
193 __wait(&init, &waiters, 1, 1);
201 mal.brk = mal.brk + PAGE_SIZE-1 & -PAGE_SIZE;
203 mal.brk = mal.brk + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
209 if (waiters) __wake(&init, 1, 1);
213 mal.heap = (void *)c;
214 c->psize = 0 | C_INUSE;
215 free(CHUNK_TO_MEM(c));
218 if (waiters) __wake(&init, -1, 1);
222 static int adjust_size(size_t *n)
224 /* Result of pointer difference must fit in ptrdiff_t. */
225 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
234 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
238 static void unbin(struct chunk *c, int i)
240 if (c->prev == c->next)
241 a_and_64(&mal.binmap, ~(1ULL<<i));
242 c->prev->next = c->next;
243 c->next->prev = c->prev;
245 NEXT_CHUNK(c)->psize |= C_INUSE;
248 static int alloc_fwd(struct chunk *c)
252 while (!((k=c->csize) & C_INUSE)) {
265 static int alloc_rev(struct chunk *c)
269 while (!((k=c->psize) & C_INUSE)) {
273 unbin(PREV_CHUNK(c), i);
283 /* pretrim - trims a chunk _prior_ to removing it from its bin.
284 * Must be called with i as the ideal bin for size n, j the bin
285 * for the _free_ chunk self, and bin j locked. */
286 static int pretrim(struct chunk *self, size_t n, int i, int j)
289 struct chunk *next, *split;
291 /* We cannot pretrim if it would require re-binning. */
292 if (j < 40) return 0;
294 if (j != 63) return 0;
295 n1 = CHUNK_SIZE(self);
296 if (n1-n <= MMAP_THRESHOLD) return 0;
298 n1 = CHUNK_SIZE(self);
300 if (bin_index(n1-n) != j) return 0;
302 next = NEXT_CHUNK(self);
303 split = (void *)((char *)self + n);
305 split->prev = self->prev;
306 split->next = self->next;
307 split->prev->next = split;
308 split->next->prev = split;
309 split->psize = n | C_INUSE;
312 self->csize = n | C_INUSE;
316 static void trim(struct chunk *self, size_t n)
318 size_t n1 = CHUNK_SIZE(self);
319 struct chunk *next, *split;
321 if (n >= n1 - DONTCARE) return;
323 next = NEXT_CHUNK(self);
324 split = (void *)((char *)self + n);
326 split->psize = n | C_INUSE;
327 split->csize = n1-n | C_INUSE;
328 next->psize = n1-n | C_INUSE;
329 self->csize = n | C_INUSE;
331 free(CHUNK_TO_MEM(split));
334 void *malloc(size_t n)
339 if (adjust_size(&n) < 0) return 0;
341 if (n > MMAP_THRESHOLD) {
342 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
343 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
344 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
345 if (base == (void *)-1) return 0;
346 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
347 c->csize = len - (SIZE_ALIGN - OVERHEAD);
348 c->psize = SIZE_ALIGN - OVERHEAD;
349 return CHUNK_TO_MEM(c);
354 uint64_t mask = mal.binmap & -(1ULL<<i);
356 if (init_malloc(n) > 0) continue;
362 NEXT_CHUNK(x)->psize = c->csize =
363 x->csize + CHUNK_SIZE(c);
369 c = mal.bins[j].head;
370 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->csize)) {
371 if (!pretrim(c, n, i, j)) unbin(c, j);
378 /* Now patch up in case we over-allocated */
381 return CHUNK_TO_MEM(c);
384 void *realloc(void *p, size_t n)
386 struct chunk *self, *next;
390 if (!p) return malloc(n);
392 if (adjust_size(&n) < 0) return 0;
394 self = MEM_TO_CHUNK(p);
395 n1 = n0 = CHUNK_SIZE(self);
397 if (IS_MMAPPED(self)) {
398 size_t extra = self->psize;
399 char *base = (char *)self - extra;
400 size_t oldlen = n0 + extra;
401 size_t newlen = n + extra;
402 /* Crash on realloc of freed chunk */
403 if (extra & 1) a_crash();
404 if (newlen < PAGE_SIZE && (new = malloc(n))) {
405 memcpy(new, p, n-OVERHEAD);
409 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
410 if (oldlen == newlen) return p;
411 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
412 if (base == (void *)-1)
413 return newlen < oldlen ? p : 0;
414 self = (void *)(base + extra);
415 self->csize = newlen - extra;
416 return CHUNK_TO_MEM(self);
419 next = NEXT_CHUNK(self);
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);
475 /* Replace middle of large chunks with fresh zero pages */
476 if (reclaim && (self->psize & next->csize & C_INUSE)) {
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);
487 if (self->psize & next->csize & C_INUSE) {
488 self->csize = final_size | C_INUSE;
489 next->psize = final_size | C_INUSE;
490 i = bin_index(final_size);
493 if (self->psize & next->csize & C_INUSE)
495 unlock(mal.free_lock);
499 if (alloc_rev(self)) {
500 self = PREV_CHUNK(self);
501 size = CHUNK_SIZE(self);
503 if (new_size+size > RECLAIM && (new_size+size^size) > size)
507 if (alloc_fwd(next)) {
508 size = CHUNK_SIZE(next);
510 if (new_size+size > RECLAIM && (new_size+size^size) > size)
512 next = NEXT_CHUNK(next);
516 self->csize = final_size;
517 next->psize = final_size;
518 unlock(mal.free_lock);
520 self->next = BIN_TO_CHUNK(i);
521 self->prev = mal.bins[i].tail;
522 self->next->prev = self;
523 self->prev->next = self;
525 if (!(mal.binmap & 1ULL<<i))
526 a_or_64(&mal.binmap, 1ULL<<i);