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);
40 #define SIZE_ALIGN (4*sizeof(size_t))
41 #define SIZE_MASK (-SIZE_ALIGN)
42 #define OVERHEAD (2*sizeof(size_t))
43 #define MMAP_THRESHOLD (0x1c00*SIZE_ALIGN)
45 #define RECLAIM 163840
47 #define CHUNK_SIZE(c) ((c)->data[0] & SIZE_MASK)
48 #define CHUNK_PSIZE(c) ((c)->data[-1] & SIZE_MASK)
49 #define PREV_CHUNK(c) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c)))
50 #define NEXT_CHUNK(c) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c)))
51 #define MEM_TO_CHUNK(p) (struct chunk *)((size_t *)p - 1)
52 #define CHUNK_TO_MEM(c) (void *)((c)->data+1)
53 #define BIN_TO_CHUNK(i) (MEM_TO_CHUNK(&mal.bins[i].head))
55 #define C_INUSE ((size_t)1)
56 #define C_FLAGS ((size_t)3)
57 #define C_SIZE SIZE_MASK
59 #define IS_MMAPPED(c) !((c)->data[0] & (C_INUSE))
62 /* Synchronization tools */
64 static void lock(volatile int *lk)
66 if (!libc.threads_minus_1) return;
67 while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
70 static void unlock(volatile int *lk)
72 if (!libc.threads_minus_1) return;
74 if (lk[1]) __wake(lk, 1, 1);
77 static void lock_bin(int i)
79 if (libc.threads_minus_1)
80 lock(mal.bins[i].lock);
81 if (!mal.bins[i].head)
82 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
85 static void unlock_bin(int i)
87 if (!libc.threads_minus_1) return;
88 unlock(mal.bins[i].lock);
91 static int first_set(uint64_t x)
96 static const char debruijn64[64] = {
97 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
98 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
99 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
100 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
102 static const char debruijn32[32] = {
103 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
104 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
106 if (sizeof(long) < 8) {
110 return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
112 return debruijn32[(y&-y)*0x076be629 >> 27];
114 return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
118 static int bin_index(size_t x)
120 x = x / SIZE_ALIGN - 1;
121 if (x <= 32) return x;
122 if (x > 0x1c00) return 63;
123 return ((union { float v; uint32_t r; }){ x }.r>>21) - 496;
126 static int bin_index_up(size_t x)
128 x = x / SIZE_ALIGN - 1;
129 if (x <= 32) return x;
130 return ((union { float v; uint32_t r; }){ x }.r+0x1fffff>>21) - 496;
134 void __dump_heap(int x)
138 for (c = (void *)mal.heap; CHUNK_SIZE(c); c = NEXT_CHUNK(c))
139 fprintf(stderr, "base %p size %zu (%d) flags %d/%d\n",
140 c, CHUNK_SIZE(c), bin_index(CHUNK_SIZE(c)),
142 NEXT_CHUNK(c)->data[-1] & 15);
143 for (i=0; i<64; i++) {
144 if (mal.bins[i].head != BIN_TO_CHUNK(i) && mal.bins[i].head) {
145 fprintf(stderr, "bin %d: %p\n", i, mal.bins[i].head);
146 if (!(mal.binmap & 1ULL<<i))
147 fprintf(stderr, "missing from binmap!\n");
148 } else if (mal.binmap & 1ULL<<i)
149 fprintf(stderr, "binmap wrongly contains %d!\n", i);
154 static struct chunk *expand_heap(size_t n)
161 if (n > SIZE_MAX - mal.brk - 2*PAGE_SIZE) goto fail;
162 new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE;
165 if (__brk(new) != new) goto fail;
167 w = MEM_TO_CHUNK(new);
168 w->data[-1] = n | C_INUSE;
169 w->data[0] = 0 | C_INUSE;
171 w = MEM_TO_CHUNK(mal.brk);
172 w->data[0] = n | C_INUSE;
175 unlock(mal.brk_lock);
179 unlock(mal.brk_lock);
183 static int init_malloc(size_t n)
185 static int init, waiters;
189 if (init == 2) return 0;
191 while ((state=a_swap(&init, 1)) == 1)
192 __wait(&init, &waiters, 1, 1);
198 mal.brk = __brk(0) + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
204 if (waiters) __wake(&init, 1, 1);
208 mal.heap = (void *)c;
209 c->data[-1] = 0 | C_INUSE;
210 free(CHUNK_TO_MEM(c));
213 if (waiters) __wake(&init, -1, 1);
217 static int adjust_size(size_t *n)
219 /* Result of pointer difference must fit in ptrdiff_t. */
220 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
229 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
233 static void unbin(struct chunk *c, int i)
235 if (c->prev == c->next)
236 a_and_64(&mal.binmap, ~(1ULL<<i));
237 c->prev->next = c->next;
238 c->next->prev = c->prev;
239 c->data[0] |= C_INUSE;
240 NEXT_CHUNK(c)->data[-1] |= C_INUSE;
243 static int alloc_fwd(struct chunk *c)
247 while (!((k=c->data[0]) & C_INUSE)) {
250 if (c->data[0] == k) {
260 static int alloc_rev(struct chunk *c)
264 while (!((k=c->data[-1]) & C_INUSE)) {
267 if (c->data[-1] == k) {
268 unbin(PREV_CHUNK(c), i);
278 /* pretrim - trims a chunk _prior_ to removing it from its bin.
279 * Must be called with i as the ideal bin for size n, j the bin
280 * for the _free_ chunk self, and bin j locked. */
281 static int pretrim(struct chunk *self, size_t n, int i, int j)
284 struct chunk *next, *split;
286 /* We cannot pretrim if it would require re-binning. */
287 if (j < 40) return 0;
289 if (j != 63) return 0;
290 n1 = CHUNK_SIZE(self);
291 if (n1-n <= MMAP_THRESHOLD) return 0;
293 n1 = CHUNK_SIZE(self);
295 if (bin_index(n1-n) != j) return 0;
297 next = NEXT_CHUNK(self);
298 split = (void *)((char *)self + n);
300 split->prev = self->prev;
301 split->next = self->next;
302 split->prev->next = split;
303 split->next->prev = split;
304 split->data[-1] = n | C_INUSE;
305 split->data[0] = n1-n;
306 next->data[-1] = n1-n;
307 self->data[0] = n | C_INUSE;
311 static void trim(struct chunk *self, size_t n)
313 size_t n1 = CHUNK_SIZE(self);
314 struct chunk *next, *split;
316 if (n >= n1 - DONTCARE) return;
318 next = NEXT_CHUNK(self);
319 split = (void *)((char *)self + n);
321 split->data[-1] = n | C_INUSE;
322 split->data[0] = n1-n | C_INUSE;
323 next->data[-1] = n1-n | C_INUSE;
324 self->data[0] = n | C_INUSE;
326 free(CHUNK_TO_MEM(split));
329 void *malloc(size_t n)
334 if (adjust_size(&n) < 0) return 0;
336 if (n > MMAP_THRESHOLD) {
337 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
338 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
339 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
340 if (base == (void *)-1) return 0;
341 c = (void *)(base + SIZE_ALIGN - sizeof(size_t));
342 c->data[0] = len - (SIZE_ALIGN - sizeof(size_t));
343 c->data[-1] = SIZE_ALIGN - sizeof(size_t);
344 return CHUNK_TO_MEM(c);
349 uint64_t mask = mal.binmap & -(1ULL<<i);
351 if (init_malloc(n) > 0) continue;
357 NEXT_CHUNK(x)->data[-1] = c->data[0] =
358 x->data[0] + CHUNK_SIZE(c);
364 c = mal.bins[j].head;
365 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->data[0])) {
366 if (!pretrim(c, n, i, j)) unbin(c, j);
373 /* Now patch up in case we over-allocated */
376 return CHUNK_TO_MEM(c);
379 void *realloc(void *p, size_t n)
381 struct chunk *self, *next;
385 if (!p) return malloc(n);
387 if (adjust_size(&n) < 0) return 0;
389 self = MEM_TO_CHUNK(p);
390 n1 = n0 = CHUNK_SIZE(self);
392 if (IS_MMAPPED(self)) {
393 size_t extra = self->data[-1];
394 char *base = (char *)self - extra;
395 size_t oldlen = n0 + extra;
396 size_t newlen = n + extra;
397 /* Crash on realloc of freed chunk */
398 if ((uintptr_t)base < mal.brk) *(volatile char *)0=0;
399 if (newlen < PAGE_SIZE && (new = malloc(n))) {
400 memcpy(new, p, n-OVERHEAD);
404 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
405 if (oldlen == newlen) return p;
406 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
407 if (base == (void *)-1)
408 return newlen < oldlen ? p : 0;
409 self = (void *)(base + extra);
410 self->data[0] = newlen - extra;
411 return CHUNK_TO_MEM(self);
414 next = NEXT_CHUNK(self);
416 /* Merge adjacent chunks if we need more space. This is not
417 * a waste of time even if we fail to get enough space, because our
418 * subsequent call to free would otherwise have to do the merge. */
419 if (n > n1 && alloc_fwd(next)) {
420 n1 += CHUNK_SIZE(next);
421 next = NEXT_CHUNK(next);
423 /* FIXME: find what's wrong here and reenable it..? */
424 if (0 && n > n1 && alloc_rev(self)) {
425 self = PREV_CHUNK(self);
426 n1 += CHUNK_SIZE(self);
428 self->data[0] = n1 | C_INUSE;
429 next->data[-1] = n1 | C_INUSE;
431 /* If we got enough space, split off the excess and return */
433 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
435 return CHUNK_TO_MEM(self);
438 /* As a last resort, allocate a new chunk and copy to it. */
439 new = malloc(n-OVERHEAD);
441 memcpy(new, p, n0-OVERHEAD);
442 free(CHUNK_TO_MEM(self));
448 struct chunk *self = MEM_TO_CHUNK(p);
450 size_t final_size, new_size, size;
456 if (IS_MMAPPED(self)) {
457 size_t extra = self->data[-1];
458 char *base = (char *)self - extra;
459 size_t len = CHUNK_SIZE(self) + extra;
460 /* Crash on double free */
461 if ((uintptr_t)base < mal.brk) *(volatile char *)0=0;
466 final_size = new_size = CHUNK_SIZE(self);
467 next = NEXT_CHUNK(self);
470 /* Replace middle of large chunks with fresh zero pages */
471 if (reclaim && (self->data[-1] & next->data[0] & C_INUSE)) {
472 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
473 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
475 __madvise((void *)a, b-a, MADV_DONTNEED);
477 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
478 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
482 if (self->data[-1] & next->data[0] & C_INUSE) {
483 self->data[0] = final_size | C_INUSE;
484 next->data[-1] = final_size | C_INUSE;
485 i = bin_index(final_size);
488 if (self->data[-1] & next->data[0] & C_INUSE)
490 unlock(mal.free_lock);
494 if (alloc_rev(self)) {
495 self = PREV_CHUNK(self);
496 size = CHUNK_SIZE(self);
498 if (new_size+size > RECLAIM && (new_size+size^size) > size)
502 if (alloc_fwd(next)) {
503 size = CHUNK_SIZE(next);
505 if (new_size+size > RECLAIM && (new_size+size^size) > size)
507 next = NEXT_CHUNK(next);
511 self->data[0] = final_size;
512 next->data[-1] = final_size;
513 unlock(mal.free_lock);
515 self->next = BIN_TO_CHUNK(i);
516 self->prev = mal.bins[i].tail;
517 self->next->prev = self;
518 self->prev->next = self;
520 if (!(mal.binmap & 1ULL<<i))
521 a_or_64(&mal.binmap, 1ULL<<i);