10 #include "pthread_impl.h"
12 uintptr_t __brk(uintptr_t);
13 void *__mmap(void *, size_t, int, int, int, off_t);
14 int __munmap(void *, size_t);
15 void *__mremap(void *, size_t, size_t, int, ...);
16 int __madvise(void *, size_t, int);
20 struct chunk *next, *prev;
39 #define SIZE_ALIGN (4*sizeof(size_t))
40 #define SIZE_MASK (-SIZE_ALIGN)
41 #define OVERHEAD (2*sizeof(size_t))
42 #define MMAP_THRESHOLD (0x1c00*SIZE_ALIGN)
44 #define RECLAIM 163840
46 #define CHUNK_SIZE(c) ((c)->csize & SIZE_MASK)
47 #define CHUNK_PSIZE(c) ((c)->psize & SIZE_MASK)
48 #define PREV_CHUNK(c) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c)))
49 #define NEXT_CHUNK(c) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c)))
50 #define MEM_TO_CHUNK(p) (struct chunk *)((char *)(p) - OVERHEAD)
51 #define CHUNK_TO_MEM(c) (void *)((char *)(c) + OVERHEAD)
52 #define BIN_TO_CHUNK(i) (MEM_TO_CHUNK(&mal.bins[i].head))
54 #define C_INUSE ((size_t)1)
55 #define C_FLAGS ((size_t)3)
56 #define C_SIZE SIZE_MASK
58 #define IS_MMAPPED(c) !((c)->csize & (C_INUSE))
61 /* Synchronization tools */
63 static void lock(volatile int *lk)
65 if (!libc.threads_minus_1) return;
66 while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
69 static void unlock(volatile int *lk)
71 if (!libc.threads_minus_1) return;
73 if (lk[1]) __wake(lk, 1, 1);
76 static void lock_bin(int i)
78 if (libc.threads_minus_1)
79 lock(mal.bins[i].lock);
80 if (!mal.bins[i].head)
81 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
84 static void unlock_bin(int i)
86 if (!libc.threads_minus_1) return;
87 unlock(mal.bins[i].lock);
90 static int first_set(uint64_t x)
95 static const char debruijn64[64] = {
96 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
97 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
98 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
99 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
101 static const char debruijn32[32] = {
102 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
103 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
105 if (sizeof(long) < 8) {
109 return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
111 return debruijn32[(y&-y)*0x076be629 >> 27];
113 return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
117 static int bin_index(size_t x)
119 x = x / SIZE_ALIGN - 1;
120 if (x <= 32) return x;
121 if (x > 0x1c00) return 63;
122 return ((union { float v; uint32_t r; }){(int)x}.r>>21) - 496;
125 static int bin_index_up(size_t x)
127 x = x / SIZE_ALIGN - 1;
128 if (x <= 32) return x;
129 return ((union { float v; uint32_t r; }){(int)x}.r+0x1fffff>>21) - 496;
133 void __dump_heap(int x)
137 for (c = (void *)mal.heap; CHUNK_SIZE(c); c = NEXT_CHUNK(c))
138 fprintf(stderr, "base %p size %zu (%d) flags %d/%d\n",
139 c, CHUNK_SIZE(c), bin_index(CHUNK_SIZE(c)),
141 NEXT_CHUNK(c)->psize & 15);
142 for (i=0; i<64; i++) {
143 if (mal.bins[i].head != BIN_TO_CHUNK(i) && mal.bins[i].head) {
144 fprintf(stderr, "bin %d: %p\n", i, mal.bins[i].head);
145 if (!(mal.binmap & 1ULL<<i))
146 fprintf(stderr, "missing from binmap!\n");
147 } else if (mal.binmap & 1ULL<<i)
148 fprintf(stderr, "binmap wrongly contains %d!\n", i);
153 static struct chunk *expand_heap(size_t n)
160 if (n > SIZE_MAX - mal.brk - 2*PAGE_SIZE) goto fail;
161 new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE;
164 if (__brk(new) != new) goto fail;
166 w = MEM_TO_CHUNK(new);
167 w->psize = n | C_INUSE;
168 w->csize = 0 | C_INUSE;
170 w = MEM_TO_CHUNK(mal.brk);
171 w->csize = n | C_INUSE;
174 unlock(mal.brk_lock);
178 unlock(mal.brk_lock);
182 static int init_malloc(size_t n)
184 static int init, waiters;
188 if (init == 2) return 0;
190 while ((state=a_swap(&init, 1)) == 1)
191 __wait(&init, &waiters, 1, 1);
197 mal.brk = __brk(0) + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
203 if (waiters) __wake(&init, 1, 1);
207 mal.heap = (void *)c;
208 c->psize = 0 | C_INUSE;
209 free(CHUNK_TO_MEM(c));
212 if (waiters) __wake(&init, -1, 1);
216 static int adjust_size(size_t *n)
218 /* Result of pointer difference must fit in ptrdiff_t. */
219 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
228 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
232 static void unbin(struct chunk *c, int i)
234 if (c->prev == c->next)
235 a_and_64(&mal.binmap, ~(1ULL<<i));
236 c->prev->next = c->next;
237 c->next->prev = c->prev;
239 NEXT_CHUNK(c)->psize |= C_INUSE;
242 static int alloc_fwd(struct chunk *c)
246 while (!((k=c->csize) & C_INUSE)) {
259 static int alloc_rev(struct chunk *c)
263 while (!((k=c->psize) & C_INUSE)) {
267 unbin(PREV_CHUNK(c), i);
277 /* pretrim - trims a chunk _prior_ to removing it from its bin.
278 * Must be called with i as the ideal bin for size n, j the bin
279 * for the _free_ chunk self, and bin j locked. */
280 static int pretrim(struct chunk *self, size_t n, int i, int j)
283 struct chunk *next, *split;
285 /* We cannot pretrim if it would require re-binning. */
286 if (j < 40) return 0;
288 if (j != 63) return 0;
289 n1 = CHUNK_SIZE(self);
290 if (n1-n <= MMAP_THRESHOLD) return 0;
292 n1 = CHUNK_SIZE(self);
294 if (bin_index(n1-n) != j) return 0;
296 next = NEXT_CHUNK(self);
297 split = (void *)((char *)self + n);
299 split->prev = self->prev;
300 split->next = self->next;
301 split->prev->next = split;
302 split->next->prev = split;
303 split->psize = n | C_INUSE;
306 self->csize = n | C_INUSE;
310 static void trim(struct chunk *self, size_t n)
312 size_t n1 = CHUNK_SIZE(self);
313 struct chunk *next, *split;
315 if (n >= n1 - DONTCARE) return;
317 next = NEXT_CHUNK(self);
318 split = (void *)((char *)self + n);
320 split->psize = n | C_INUSE;
321 split->csize = n1-n | C_INUSE;
322 next->psize = n1-n | C_INUSE;
323 self->csize = n | C_INUSE;
325 free(CHUNK_TO_MEM(split));
328 void *malloc(size_t n)
333 if (adjust_size(&n) < 0) return 0;
335 if (n > MMAP_THRESHOLD) {
336 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
337 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
338 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
339 if (base == (void *)-1) return 0;
340 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
341 c->csize = len - (SIZE_ALIGN - OVERHEAD);
342 c->psize = SIZE_ALIGN - OVERHEAD;
343 return CHUNK_TO_MEM(c);
348 uint64_t mask = mal.binmap & -(1ULL<<i);
350 if (init_malloc(n) > 0) continue;
356 NEXT_CHUNK(x)->psize = c->csize =
357 x->csize + CHUNK_SIZE(c);
363 c = mal.bins[j].head;
364 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->csize)) {
365 if (!pretrim(c, n, i, j)) unbin(c, j);
372 /* Now patch up in case we over-allocated */
375 return CHUNK_TO_MEM(c);
378 void *realloc(void *p, size_t n)
380 struct chunk *self, *next;
384 if (!p) return malloc(n);
386 if (adjust_size(&n) < 0) return 0;
388 self = MEM_TO_CHUNK(p);
389 n1 = n0 = CHUNK_SIZE(self);
391 if (IS_MMAPPED(self)) {
392 size_t extra = self->psize;
393 char *base = (char *)self - extra;
394 size_t oldlen = n0 + extra;
395 size_t newlen = n + extra;
396 /* Crash on realloc of freed chunk */
397 if (extra & 1) a_crash();
398 if (newlen < PAGE_SIZE && (new = malloc(n))) {
399 memcpy(new, p, n-OVERHEAD);
403 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
404 if (oldlen == newlen) return p;
405 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
406 if (base == (void *)-1)
407 return newlen < oldlen ? p : 0;
408 self = (void *)(base + extra);
409 self->csize = newlen - extra;
410 return CHUNK_TO_MEM(self);
413 next = NEXT_CHUNK(self);
415 /* Merge adjacent chunks if we need more space. This is not
416 * a waste of time even if we fail to get enough space, because our
417 * subsequent call to free would otherwise have to do the merge. */
418 if (n > n1 && alloc_fwd(next)) {
419 n1 += CHUNK_SIZE(next);
420 next = NEXT_CHUNK(next);
422 /* FIXME: find what's wrong here and reenable it..? */
423 if (0 && n > n1 && alloc_rev(self)) {
424 self = PREV_CHUNK(self);
425 n1 += CHUNK_SIZE(self);
427 self->csize = n1 | C_INUSE;
428 next->psize = n1 | C_INUSE;
430 /* If we got enough space, split off the excess and return */
432 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
434 return CHUNK_TO_MEM(self);
437 /* As a last resort, allocate a new chunk and copy to it. */
438 new = malloc(n-OVERHEAD);
440 memcpy(new, p, n0-OVERHEAD);
441 free(CHUNK_TO_MEM(self));
447 struct chunk *self = MEM_TO_CHUNK(p);
449 size_t final_size, new_size, size;
455 if (IS_MMAPPED(self)) {
456 size_t extra = self->psize;
457 char *base = (char *)self - extra;
458 size_t len = CHUNK_SIZE(self) + extra;
459 /* Crash on double free */
460 if (extra & 1) a_crash();
465 final_size = new_size = CHUNK_SIZE(self);
466 next = NEXT_CHUNK(self);
469 /* Replace middle of large chunks with fresh zero pages */
470 if (reclaim && (self->psize & next->csize & C_INUSE)) {
471 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
472 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
474 __madvise((void *)a, b-a, MADV_DONTNEED);
476 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
477 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
481 if (self->psize & next->csize & C_INUSE) {
482 self->csize = final_size | C_INUSE;
483 next->psize = final_size | C_INUSE;
484 i = bin_index(final_size);
487 if (self->psize & next->csize & C_INUSE)
489 unlock(mal.free_lock);
493 if (alloc_rev(self)) {
494 self = PREV_CHUNK(self);
495 size = CHUNK_SIZE(self);
497 if (new_size+size > RECLAIM && (new_size+size^size) > size)
501 if (alloc_fwd(next)) {
502 size = CHUNK_SIZE(next);
504 if (new_size+size > RECLAIM && (new_size+size^size) > size)
506 next = NEXT_CHUNK(next);
510 self->csize = final_size;
511 next->psize = final_size;
512 unlock(mal.free_lock);
514 self->next = BIN_TO_CHUNK(i);
515 self->prev = mal.bins[i].tail;
516 self->next->prev = self;
517 self->prev->next = self;
519 if (!(mal.binmap & 1ULL<<i))
520 a_or_64(&mal.binmap, 1ULL<<i);