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);
199 mal.brk = __brk(0) + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
205 if (waiters) __wake(&init, 1, 1);
209 mal.heap = (void *)c;
210 c->psize = 0 | C_INUSE;
211 free(CHUNK_TO_MEM(c));
214 if (waiters) __wake(&init, -1, 1);
218 static int adjust_size(size_t *n)
220 /* Result of pointer difference must fit in ptrdiff_t. */
221 if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
230 *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
234 static void unbin(struct chunk *c, int i)
236 if (c->prev == c->next)
237 a_and_64(&mal.binmap, ~(1ULL<<i));
238 c->prev->next = c->next;
239 c->next->prev = c->prev;
241 NEXT_CHUNK(c)->psize |= C_INUSE;
244 static int alloc_fwd(struct chunk *c)
248 while (!((k=c->csize) & C_INUSE)) {
261 static int alloc_rev(struct chunk *c)
265 while (!((k=c->psize) & C_INUSE)) {
269 unbin(PREV_CHUNK(c), i);
279 /* pretrim - trims a chunk _prior_ to removing it from its bin.
280 * Must be called with i as the ideal bin for size n, j the bin
281 * for the _free_ chunk self, and bin j locked. */
282 static int pretrim(struct chunk *self, size_t n, int i, int j)
285 struct chunk *next, *split;
287 /* We cannot pretrim if it would require re-binning. */
288 if (j < 40) return 0;
290 if (j != 63) return 0;
291 n1 = CHUNK_SIZE(self);
292 if (n1-n <= MMAP_THRESHOLD) return 0;
294 n1 = CHUNK_SIZE(self);
296 if (bin_index(n1-n) != j) return 0;
298 next = NEXT_CHUNK(self);
299 split = (void *)((char *)self + n);
301 split->prev = self->prev;
302 split->next = self->next;
303 split->prev->next = split;
304 split->next->prev = split;
305 split->psize = n | C_INUSE;
308 self->csize = n | C_INUSE;
312 static void trim(struct chunk *self, size_t n)
314 size_t n1 = CHUNK_SIZE(self);
315 struct chunk *next, *split;
317 if (n >= n1 - DONTCARE) return;
319 next = NEXT_CHUNK(self);
320 split = (void *)((char *)self + n);
322 split->psize = n | C_INUSE;
323 split->csize = n1-n | C_INUSE;
324 next->psize = n1-n | C_INUSE;
325 self->csize = n | C_INUSE;
327 free(CHUNK_TO_MEM(split));
330 void *malloc(size_t n)
335 if (adjust_size(&n) < 0) return 0;
337 if (n > MMAP_THRESHOLD) {
338 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
339 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
340 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
341 if (base == (void *)-1) return 0;
342 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
343 c->csize = len - (SIZE_ALIGN - OVERHEAD);
344 c->psize = SIZE_ALIGN - OVERHEAD;
345 return CHUNK_TO_MEM(c);
350 uint64_t mask = mal.binmap & -(1ULL<<i);
352 if (init_malloc(n) > 0) continue;
358 NEXT_CHUNK(x)->psize = c->csize =
359 x->csize + CHUNK_SIZE(c);
365 c = mal.bins[j].head;
366 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->csize)) {
367 if (!pretrim(c, n, i, j)) unbin(c, j);
374 /* Now patch up in case we over-allocated */
377 return CHUNK_TO_MEM(c);
380 void *realloc(void *p, size_t n)
382 struct chunk *self, *next;
386 if (!p) return malloc(n);
388 if (adjust_size(&n) < 0) return 0;
390 self = MEM_TO_CHUNK(p);
391 n1 = n0 = CHUNK_SIZE(self);
393 if (IS_MMAPPED(self)) {
394 size_t extra = self->psize;
395 char *base = (char *)self - extra;
396 size_t oldlen = n0 + extra;
397 size_t newlen = n + extra;
398 /* Crash on realloc of freed chunk */
399 if (extra & 1) a_crash();
400 if (newlen < PAGE_SIZE && (new = malloc(n))) {
401 memcpy(new, p, n-OVERHEAD);
405 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
406 if (oldlen == newlen) return p;
407 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
408 if (base == (void *)-1)
409 return newlen < oldlen ? p : 0;
410 self = (void *)(base + extra);
411 self->csize = newlen - extra;
412 return CHUNK_TO_MEM(self);
415 next = NEXT_CHUNK(self);
417 /* Merge adjacent chunks if we need more space. This is not
418 * a waste of time even if we fail to get enough space, because our
419 * subsequent call to free would otherwise have to do the merge. */
420 if (n > n1 && alloc_fwd(next)) {
421 n1 += CHUNK_SIZE(next);
422 next = NEXT_CHUNK(next);
424 /* FIXME: find what's wrong here and reenable it..? */
425 if (0 && n > n1 && alloc_rev(self)) {
426 self = PREV_CHUNK(self);
427 n1 += CHUNK_SIZE(self);
429 self->csize = n1 | C_INUSE;
430 next->psize = n1 | C_INUSE;
432 /* If we got enough space, split off the excess and return */
434 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
436 return CHUNK_TO_MEM(self);
439 /* As a last resort, allocate a new chunk and copy to it. */
440 new = malloc(n-OVERHEAD);
442 memcpy(new, p, n0-OVERHEAD);
443 free(CHUNK_TO_MEM(self));
449 struct chunk *self = MEM_TO_CHUNK(p);
451 size_t final_size, new_size, size;
457 if (IS_MMAPPED(self)) {
458 size_t extra = self->psize;
459 char *base = (char *)self - extra;
460 size_t len = CHUNK_SIZE(self) + extra;
461 /* Crash on double free */
462 if (extra & 1) a_crash();
467 final_size = new_size = CHUNK_SIZE(self);
468 next = NEXT_CHUNK(self);
471 /* Replace middle of large chunks with fresh zero pages */
472 if (reclaim && (self->psize & next->csize & C_INUSE)) {
473 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
474 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
476 __madvise((void *)a, b-a, MADV_DONTNEED);
478 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
479 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
483 if (self->psize & next->csize & C_INUSE) {
484 self->csize = final_size | C_INUSE;
485 next->psize = final_size | C_INUSE;
486 i = bin_index(final_size);
489 if (self->psize & next->csize & C_INUSE)
491 unlock(mal.free_lock);
495 if (alloc_rev(self)) {
496 self = PREV_CHUNK(self);
497 size = CHUNK_SIZE(self);
499 if (new_size+size > RECLAIM && (new_size+size^size) > size)
503 if (alloc_fwd(next)) {
504 size = CHUNK_SIZE(next);
506 if (new_size+size > RECLAIM && (new_size+size^size) > size)
508 next = NEXT_CHUNK(next);
512 self->csize = final_size;
513 next->psize = final_size;
514 unlock(mal.free_lock);
516 self->next = BIN_TO_CHUNK(i);
517 self->prev = mal.bins[i].tail;
518 self->next->prev = self;
519 self->prev->next = self;
521 if (!(mal.binmap & 1ULL<<i))
522 a_or_64(&mal.binmap, 1ULL<<i);