9 #include "pthread_impl.h"
11 uintptr_t __brk(uintptr_t);
12 void *__mmap(void *, size_t, int, int, int, off_t);
13 int __munmap(void *, size_t);
14 void *__mremap(void *, size_t, size_t, int, ...);
15 int __madvise(void *, size_t, int);
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)->data[0] & SIZE_MASK)
47 #define CHUNK_PSIZE(c) ((c)->data[-1] & 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 *)((size_t *)p - 1)
51 #define CHUNK_TO_MEM(c) (void *)((c)->data+1)
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)->data[0] & (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; }){ 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; }){ 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)->data[-1] & 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->data[-1] = n | C_INUSE;
168 w->data[0] = 0 | C_INUSE;
170 w = MEM_TO_CHUNK(mal.brk);
171 w->data[0] = n | C_INUSE;
174 unlock(mal.brk_lock);
178 unlock(mal.brk_lock);
182 static int init_malloc()
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->data[-1] = 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;
238 c->data[0] |= C_INUSE;
239 NEXT_CHUNK(c)->data[-1] |= C_INUSE;
242 static int alloc_fwd(struct chunk *c)
246 while (!((k=c->data[0]) & C_INUSE)) {
249 if (c->data[0] == k) {
259 static int alloc_rev(struct chunk *c)
263 while (!((k=c->data[-1]) & C_INUSE)) {
266 if (c->data[-1] == k) {
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->data[-1] = n | C_INUSE;
304 split->data[0] = n1-n;
305 next->data[-1] = n1-n;
306 self->data[0] = 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->data[-1] = n | C_INUSE;
321 split->data[0] = n1-n | C_INUSE;
322 next->data[-1] = n1-n | C_INUSE;
323 self->data[0] = 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 + 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 - sizeof(size_t));
341 c->data[0] = len - (SIZE_ALIGN - sizeof(size_t));
342 c->data[-1] = SIZE_ALIGN - sizeof(size_t);
343 return CHUNK_TO_MEM(c);
348 uint64_t mask = mal.binmap & -(1ULL<<i);
356 NEXT_CHUNK(x)->data[-1] = c->data[0] =
357 x->data[0] + CHUNK_SIZE(c);
363 c = mal.bins[j].head;
364 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->data[0])) {
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->data[-1];
393 char *base = (char *)self - extra;
394 size_t oldlen = n0 + extra;
395 size_t newlen = n + extra;
396 if (newlen < PAGE_SIZE && (new = malloc(n))) {
397 memcpy(new, p, n-OVERHEAD);
401 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
402 if (oldlen == newlen) return p;
403 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
404 if (base == (void *)-1)
405 return newlen < oldlen ? p : 0;
406 self = (void *)(base + extra);
407 self->data[0] = newlen - extra;
408 return CHUNK_TO_MEM(self);
411 next = NEXT_CHUNK(self);
413 /* Merge adjacent chunks if we need more space. This is not
414 * a waste of time even if we fail to get enough space, because our
415 * subsequent call to free would otherwise have to do the merge. */
416 if (n > n1 && alloc_fwd(next)) {
417 n1 += CHUNK_SIZE(next);
418 next = NEXT_CHUNK(next);
420 /* FIXME: find what's wrong here and reenable it..? */
421 if (0 && n > n1 && alloc_rev(self)) {
422 self = PREV_CHUNK(self);
423 n1 += CHUNK_SIZE(self);
425 self->data[0] = n1 | C_INUSE;
426 next->data[-1] = n1 | C_INUSE;
428 /* If we got enough space, split off the excess and return */
430 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
432 return CHUNK_TO_MEM(self);
435 /* As a last resort, allocate a new chunk and copy to it. */
436 new = malloc(n-OVERHEAD);
438 memcpy(new, p, n0-OVERHEAD);
439 free(CHUNK_TO_MEM(self));
445 struct chunk *self = MEM_TO_CHUNK(p);
447 size_t final_size, new_size, size;
453 if (IS_MMAPPED(self)) {
454 size_t extra = self->data[-1];
455 char *base = (char *)self - extra;
456 size_t len = CHUNK_SIZE(self) + extra;
461 final_size = new_size = CHUNK_SIZE(self);
462 next = NEXT_CHUNK(self);
465 /* Replace middle of large chunks with fresh zero pages */
466 if (reclaim && (self->data[-1] & next->data[0] & C_INUSE)) {
467 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
468 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
470 __madvise((void *)a, b-a, MADV_DONTNEED);
472 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
473 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
477 if (self->data[-1] & next->data[0] & C_INUSE) {
478 self->data[0] = final_size | C_INUSE;
479 next->data[-1] = final_size | C_INUSE;
480 i = bin_index(final_size);
483 if (self->data[-1] & next->data[0] & C_INUSE)
485 unlock(mal.free_lock);
489 if (alloc_rev(self)) {
490 self = PREV_CHUNK(self);
491 size = CHUNK_SIZE(self);
493 if (new_size+size > RECLAIM && (new_size+size^size) > size)
497 if (alloc_fwd(next)) {
498 size = CHUNK_SIZE(next);
500 if (new_size+size > RECLAIM && (new_size+size^size) > size)
502 next = NEXT_CHUNK(next);
506 self->data[0] = final_size;
507 next->data[-1] = final_size;
508 unlock(mal.free_lock);
510 self->next = BIN_TO_CHUNK(i);
511 self->prev = mal.bins[i].tail;
512 self->next->prev = self;
513 self->prev->next = self;
515 if (!(mal.binmap & 1ULL<<i))
516 a_or_64(&mal.binmap, 1ULL<<i);