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 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
223 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
227 static void unbin(struct chunk *c, int i)
229 if (c->prev == c->next)
230 a_and_64(&mal.binmap, ~(1ULL<<i));
231 c->prev->next = c->next;
232 c->next->prev = c->prev;
233 c->data[0] |= C_INUSE;
234 NEXT_CHUNK(c)->data[-1] |= C_INUSE;
237 static int alloc_fwd(struct chunk *c)
241 while (!((k=c->data[0]) & C_INUSE)) {
244 if (c->data[0] == k) {
254 static int alloc_rev(struct chunk *c)
258 while (!((k=c->data[-1]) & C_INUSE)) {
261 if (c->data[-1] == k) {
262 unbin(PREV_CHUNK(c), i);
272 /* pretrim - trims a chunk _prior_ to removing it from its bin.
273 * Must be called with i as the ideal bin for size n, j the bin
274 * for the _free_ chunk self, and bin j locked. */
275 static int pretrim(struct chunk *self, size_t n, int i, int j)
278 struct chunk *next, *split;
280 /* We cannot pretrim if it would require re-binning. */
281 if (j < 40) return 0;
283 if (j != 63) return 0;
284 n1 = CHUNK_SIZE(self);
285 if (n1-n <= MMAP_THRESHOLD) return 0;
287 n1 = CHUNK_SIZE(self);
289 if (bin_index(n1-n) != j) return 0;
291 next = NEXT_CHUNK(self);
292 split = (void *)((char *)self + n);
294 split->prev = self->prev;
295 split->next = self->next;
296 split->prev->next = split;
297 split->next->prev = split;
298 split->data[-1] = n | C_INUSE;
299 split->data[0] = n1-n;
300 next->data[-1] = n1-n;
301 self->data[0] = n | C_INUSE;
305 static void trim(struct chunk *self, size_t n)
307 size_t n1 = CHUNK_SIZE(self);
308 struct chunk *next, *split;
310 if (n >= n1 - DONTCARE) return;
312 next = NEXT_CHUNK(self);
313 split = (void *)((char *)self + n);
315 split->data[-1] = n | C_INUSE;
316 split->data[0] = n1-n | C_INUSE;
317 next->data[-1] = n1-n | C_INUSE;
318 self->data[0] = n | C_INUSE;
320 free(CHUNK_TO_MEM(split));
323 void *malloc(size_t n)
328 if (!n || adjust_size(&n) < 0) return 0;
330 if (n > MMAP_THRESHOLD) {
331 size_t len = n + PAGE_SIZE - 1 & -PAGE_SIZE;
332 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
333 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
334 if (base == (void *)-1) return 0;
335 c = (void *)(base + SIZE_ALIGN - sizeof(size_t));
336 c->data[0] = len - (SIZE_ALIGN - sizeof(size_t));
337 c->data[-1] = SIZE_ALIGN - sizeof(size_t);
338 return CHUNK_TO_MEM(c);
343 uint64_t mask = mal.binmap & -(1ULL<<i);
351 NEXT_CHUNK(x)->data[-1] = c->data[0] =
352 x->data[0] + CHUNK_SIZE(c);
358 c = mal.bins[j].head;
359 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->data[0])) {
360 if (!pretrim(c, n, i, j)) unbin(c, j);
367 /* Now patch up in case we over-allocated */
370 return CHUNK_TO_MEM(c);
373 void *realloc(void *p, size_t n)
375 struct chunk *self, *next;
379 if (!p) return malloc(n);
380 else if (!n) return free(p), (void *)0;
382 if (adjust_size(&n) < 0) return 0;
384 self = MEM_TO_CHUNK(p);
385 n1 = n0 = CHUNK_SIZE(self);
387 if (IS_MMAPPED(self)) {
388 size_t extra = self->data[-1];
389 char *base = (char *)self - extra;
390 size_t oldlen = n0 + extra;
391 size_t newlen = n + extra;
392 if (newlen < PAGE_SIZE && (new = malloc(n))) {
393 memcpy(new, p, n-OVERHEAD);
397 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
398 if (oldlen == newlen) return p;
399 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
400 if (base == (void *)-1)
401 return newlen < oldlen ? p : 0;
402 self = (void *)(base + extra);
403 self->data[0] = newlen - extra;
404 return CHUNK_TO_MEM(self);
407 next = NEXT_CHUNK(self);
409 /* Merge adjacent chunks if we need more space. This is not
410 * a waste of time even if we fail to get enough space, because our
411 * subsequent call to free would otherwise have to do the merge. */
412 if (n > n1 && alloc_fwd(next)) {
413 n1 += CHUNK_SIZE(next);
414 next = NEXT_CHUNK(next);
416 /* FIXME: find what's wrong here and reenable it..? */
417 if (0 && n > n1 && alloc_rev(self)) {
418 self = PREV_CHUNK(self);
419 n1 += CHUNK_SIZE(self);
421 self->data[0] = n1 | C_INUSE;
422 next->data[-1] = n1 | C_INUSE;
424 /* If we got enough space, split off the excess and return */
426 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
428 return CHUNK_TO_MEM(self);
431 /* As a last resort, allocate a new chunk and copy to it. */
432 new = malloc(n-OVERHEAD);
434 memcpy(new, p, n0-OVERHEAD);
435 free(CHUNK_TO_MEM(self));
441 struct chunk *self = MEM_TO_CHUNK(p);
443 size_t final_size, new_size, size;
449 if (IS_MMAPPED(self)) {
450 size_t extra = self->data[-1];
451 char *base = (char *)self - extra;
452 size_t len = CHUNK_SIZE(self) + extra;
457 final_size = new_size = CHUNK_SIZE(self);
458 next = NEXT_CHUNK(self);
461 /* Replace middle of large chunks with fresh zero pages */
462 if (reclaim && (self->data[-1] & next->data[0] & C_INUSE)) {
463 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
464 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
466 __madvise((void *)a, b-a, MADV_DONTNEED);
468 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
469 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
473 if (self->data[-1] & next->data[0] & C_INUSE) {
474 self->data[0] = final_size | C_INUSE;
475 next->data[-1] = final_size | C_INUSE;
476 i = bin_index(final_size);
479 if (self->data[-1] & next->data[0] & C_INUSE)
481 unlock(mal.free_lock);
485 if (alloc_rev(self)) {
486 self = PREV_CHUNK(self);
487 size = CHUNK_SIZE(self);
489 if (new_size+size > RECLAIM && (new_size+size^size) > size)
493 if (alloc_fwd(next)) {
494 size = CHUNK_SIZE(next);
496 if (new_size+size > RECLAIM && (new_size+size^size) > size)
498 next = NEXT_CHUNK(next);
502 self->data[0] = final_size;
503 next->data[-1] = final_size;
504 unlock(mal.free_lock);
506 self->next = BIN_TO_CHUNK(i);
507 self->prev = mal.bins[i].tail;
508 self->next->prev = self;
509 self->prev->next = self;
511 if (!(mal.binmap & 1ULL<<i))
512 a_or_64(&mal.binmap, 1ULL<<i);