X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=src%2Fmalloc%2Fmalloc.c;h=2553a62e0d09d0b6e0fec141c439f57a4028535e;hb=f12888e9eb9eed60cc266b899dcafecb4752964a;hp=1a6d1493291c7ed2d816687d92d100b78c972137;hpb=b8ccf8e46bab6ee9d63a6e392c3b33b9aa89255c;p=musl diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c index 1a6d1493..2553a62e 100644 --- a/src/malloc/malloc.c +++ b/src/malloc/malloc.c @@ -8,84 +8,45 @@ #include "libc.h" #include "atomic.h" #include "pthread_impl.h" +#include "malloc_impl.h" #if defined(__GNUC__) && defined(__PIC__) #define inline inline __attribute__((always_inline)) #endif -uintptr_t __brk(uintptr_t); -void *__mmap(void *, size_t, int, int, int, off_t); -int __munmap(void *, size_t); -void *__mremap(void *, size_t, size_t, int, ...); -int __madvise(void *, size_t, int); - -struct chunk { - size_t psize, csize; - struct chunk *next, *prev; -}; - -struct bin { - int lock[2]; - struct chunk *head; - struct chunk *tail; -}; - static struct { - uintptr_t brk; - size_t *heap; - uint64_t binmap; + volatile uint64_t binmap; struct bin bins[64]; - int brk_lock[2]; - int free_lock[2]; + volatile int free_lock[2]; } mal; - -#define SIZE_ALIGN (4*sizeof(size_t)) -#define SIZE_MASK (-SIZE_ALIGN) -#define OVERHEAD (2*sizeof(size_t)) -#define MMAP_THRESHOLD (0x1c00*SIZE_ALIGN) -#define DONTCARE 16 -#define RECLAIM 163840 - -#define CHUNK_SIZE(c) ((c)->csize & -2) -#define CHUNK_PSIZE(c) ((c)->psize & -2) -#define PREV_CHUNK(c) ((struct chunk *)((char *)(c) - CHUNK_PSIZE(c))) -#define NEXT_CHUNK(c) ((struct chunk *)((char *)(c) + CHUNK_SIZE(c))) -#define MEM_TO_CHUNK(p) (struct chunk *)((char *)(p) - OVERHEAD) -#define CHUNK_TO_MEM(c) (void *)((char *)(c) + OVERHEAD) -#define BIN_TO_CHUNK(i) (MEM_TO_CHUNK(&mal.bins[i].head)) - -#define C_INUSE ((size_t)1) - -#define IS_MMAPPED(c) !((c)->csize & (C_INUSE)) - +int __malloc_replaced; /* Synchronization tools */ static inline void lock(volatile int *lk) { - if (!libc.threads_minus_1) return; - while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1); + if (libc.threaded) + while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1); } static inline void unlock(volatile int *lk) { - if (!libc.threads_minus_1) return; - a_store(lk, 0); - if (lk[1]) __wake(lk, 1, 1); + if (lk[0]) { + a_store(lk, 0); + if (lk[1]) __wake(lk, 1, 1); + } } static inline void lock_bin(int i) { - if (libc.threads_minus_1) - lock(mal.bins[i].lock); + lock(mal.bins[i].lock); if (!mal.bins[i].head) mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i); } static inline void unlock_bin(int i) { - if (!libc.threads_minus_1) return; unlock(mal.bins[i].lock); } @@ -116,19 +77,29 @@ static int first_set(uint64_t x) #endif } +static const unsigned char bin_tab[60] = { + 32,33,34,35,36,36,37,37,38,38,39,39, + 40,40,40,40,41,41,41,41,42,42,42,42,43,43,43,43, + 44,44,44,44,44,44,44,44,45,45,45,45,45,45,45,45, + 46,46,46,46,46,46,46,46,47,47,47,47,47,47,47,47, +}; + static int bin_index(size_t x) { x = x / SIZE_ALIGN - 1; if (x <= 32) return x; + if (x < 512) return bin_tab[x/8-4]; if (x > 0x1c00) return 63; - return ((union { float v; uint32_t r; }){(int)x}.r>>21) - 496; + return bin_tab[x/128-4] + 16; } static int bin_index_up(size_t x) { x = x / SIZE_ALIGN - 1; if (x <= 32) return x; - return ((union { float v; uint32_t r; }){(int)x}.r+0x1fffff>>21) - 496; + x--; + if (x < 512) return bin_tab[x/8-4] + 1; + return bin_tab[x/128-4] + 17; } #if 0 @@ -154,69 +125,48 @@ void __dump_heap(int x) static struct chunk *expand_heap(size_t n) { + static int heap_lock[2]; + static void *end; + void *p; struct chunk *w; - uintptr_t new; - - lock(mal.brk_lock); - - if (n > SIZE_MAX - mal.brk - 2*PAGE_SIZE) goto fail; - new = mal.brk + n + SIZE_ALIGN + PAGE_SIZE - 1 & -PAGE_SIZE; - n = new - mal.brk; - - if (__brk(new) != new) goto fail; - - w = MEM_TO_CHUNK(new); - w->psize = n | C_INUSE; - w->csize = 0 | C_INUSE; - w = MEM_TO_CHUNK(mal.brk); - w->csize = n | C_INUSE; - mal.brk = new; - - unlock(mal.brk_lock); + /* The argument n already accounts for the caller's chunk + * overhead needs, but if the heap can't be extended in-place, + * we need room for an extra zero-sized sentinel chunk. */ + n += SIZE_ALIGN; - return w; -fail: - unlock(mal.brk_lock); - return 0; -} + lock(heap_lock); -static int init_malloc(size_t n) -{ - static int init, waiters; - int state; - struct chunk *c; - - if (init == 2) return 0; - - while ((state=a_swap(&init, 1)) == 1) - __wait(&init, &waiters, 1, 1); - if (state) { - a_store(&init, 2); + p = __expand_heap(&n); + if (!p) { + unlock(heap_lock); return 0; } - mal.brk = __brk(0); -#ifdef SHARED - mal.brk = mal.brk + PAGE_SIZE-1 & -PAGE_SIZE; -#endif - mal.brk = mal.brk + 2*SIZE_ALIGN-1 & -SIZE_ALIGN; + /* If not just expanding existing space, we need to make a + * new sentinel chunk below the allocated space. */ + if (p != end) { + /* Valid/safe because of the prologue increment. */ + n -= SIZE_ALIGN; + p = (char *)p + SIZE_ALIGN; + w = MEM_TO_CHUNK(p); + w->psize = 0 | C_INUSE; + } - c = expand_heap(n); + /* Record new heap end and fill in footer. */ + end = (char *)p + n; + w = MEM_TO_CHUNK(end); + w->psize = n | C_INUSE; + w->csize = 0 | C_INUSE; - if (!c) { - a_store(&init, 0); - if (waiters) __wake(&init, 1, 1); - return -1; - } + /* Fill in header, which may be new or may be replacing a + * zero-size sentinel header at the old end-of-heap. */ + w = MEM_TO_CHUNK(p); + w->csize = n | C_INUSE; - mal.heap = (void *)c; - c->psize = 0 | C_INUSE; - free(CHUNK_TO_MEM(c)); + unlock(heap_lock); - a_store(&init, 2); - if (waiters) __wake(&init, -1, 1); - return 1; + return w; } static int adjust_size(size_t *n) @@ -328,7 +278,7 @@ static void trim(struct chunk *self, size_t n) next->psize = n1-n | C_INUSE; self->csize = n | C_INUSE; - free(CHUNK_TO_MEM(split)); + __bin_chunk(split); } void *malloc(size_t n) @@ -353,7 +303,6 @@ void *malloc(size_t n) for (;;) { uint64_t mask = mal.binmap & -(1ULL< 0) continue; c = expand_heap(n); if (!c) return 0; if (alloc_rev(c)) { @@ -367,7 +316,7 @@ void *malloc(size_t n) j = first_set(mask); lock_bin(j); c = mal.bins[j].head; - if (c != BIN_TO_CHUNK(j) && j == bin_index(c->csize)) { + if (c != BIN_TO_CHUNK(j)) { if (!pretrim(c, n, i, j)) unbin(c, j); unlock_bin(j); break; @@ -381,6 +330,42 @@ void *malloc(size_t n) return CHUNK_TO_MEM(c); } +static size_t mal0_clear(char *p, size_t pagesz, size_t n) +{ +#ifdef __GNUC__ + typedef uint64_t __attribute__((__may_alias__)) T; +#else + typedef unsigned char T; +#endif + char *pp = p + n; + size_t i = (uintptr_t)pp & (pagesz - 1); + for (;;) { + pp = memset(pp - i, 0, i); + if (pp - p < pagesz) return pp - p; + for (i = pagesz; i; i -= 2*sizeof(T), pp -= 2*sizeof(T)) + if (((T *)pp)[-1] | ((T *)pp)[-2]) + break; + } +} + +void *calloc(size_t m, size_t n) +{ + if (n && m > (size_t)-1/n) { + errno = ENOMEM; + return 0; + } + n *= m; + void *p = malloc(n); + if (!p) return p; + if (!__malloc_replaced) { + if (IS_MMAPPED(MEM_TO_CHUNK(p))) + return p; + if (n >= PAGE_SIZE) + n = mal0_clear(p, PAGE_SIZE, n); + } + return memset(p, 0, n); +} + void *realloc(void *p, size_t n) { struct chunk *self, *next; @@ -401,16 +386,15 @@ void *realloc(void *p, size_t n) size_t newlen = n + extra; /* Crash on realloc of freed chunk */ if (extra & 1) a_crash(); - if (newlen < PAGE_SIZE && (new = malloc(n))) { - memcpy(new, p, n-OVERHEAD); - free(p); - return new; + if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) { + n0 = n; + goto copy_free_ret; } newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE; if (oldlen == newlen) return p; base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE); if (base == (void *)-1) - return newlen < oldlen ? p : 0; + goto copy_realloc; self = (void *)(base + extra); self->csize = newlen - extra; return CHUNK_TO_MEM(self); @@ -418,6 +402,9 @@ void *realloc(void *p, size_t n) next = NEXT_CHUNK(self); + /* Crash on corrupted footer (likely from buffer overflow) */ + if (next->psize != self->csize) a_crash(); + /* Merge adjacent chunks if we need more space. This is not * a waste of time even if we fail to get enough space, because our * subsequent call to free would otherwise have to do the merge. */ @@ -440,50 +427,29 @@ void *realloc(void *p, size_t n) return CHUNK_TO_MEM(self); } +copy_realloc: /* As a last resort, allocate a new chunk and copy to it. */ new = malloc(n-OVERHEAD); if (!new) return 0; +copy_free_ret: memcpy(new, p, n0-OVERHEAD); free(CHUNK_TO_MEM(self)); return new; } -void free(void *p) +void __bin_chunk(struct chunk *self) { - struct chunk *self = MEM_TO_CHUNK(p); - struct chunk *next; + struct chunk *next = NEXT_CHUNK(self); size_t final_size, new_size, size; int reclaim=0; int i; - if (!p) return; - - if (IS_MMAPPED(self)) { - size_t extra = self->psize; - char *base = (char *)self - extra; - size_t len = CHUNK_SIZE(self) + extra; - /* Crash on double free */ - if (extra & 1) a_crash(); - __munmap(base, len); - return; - } - final_size = new_size = CHUNK_SIZE(self); - next = NEXT_CHUNK(self); - for (;;) { - /* Replace middle of large chunks with fresh zero pages */ - if (reclaim && (self->psize & next->csize & C_INUSE)) { - uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE; - uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE; -#if 1 - __madvise((void *)a, b-a, MADV_DONTNEED); -#else - __mmap((void *)a, b-a, PROT_READ|PROT_WRITE, - MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0); -#endif - } + /* Crash on corrupted footer (likely from buffer overflow) */ + if (next->psize != self->csize) a_crash(); + for (;;) { if (self->psize & next->csize & C_INUSE) { self->csize = final_size | C_INUSE; next->psize = final_size | C_INUSE; @@ -513,6 +479,9 @@ void free(void *p) } } + if (!(mal.binmap & 1ULL<csize = final_size; next->psize = final_size; unlock(mal.free_lock); @@ -522,8 +491,58 @@ void free(void *p) self->next->prev = self; self->prev->next = self; - if (!(mal.binmap & 1ULL<psize; + char *base = (char *)self - extra; + size_t len = CHUNK_SIZE(self) + extra; + /* Crash on double free */ + if (extra & 1) a_crash(); + __munmap(base, len); +} + +void free(void *p) +{ + if (!p) return; + + struct chunk *self = MEM_TO_CHUNK(p); + + if (IS_MMAPPED(self)) + unmap_chunk(self); + else + __bin_chunk(self); +} + +void __malloc_donate(char *start, char *end) +{ + size_t align_start_up = (SIZE_ALIGN-1) & (-(uintptr_t)start - OVERHEAD); + size_t align_end_down = (SIZE_ALIGN-1) & (uintptr_t)end; + + /* Getting past this condition ensures that the padding for alignment + * and header overhead will not overflow and will leave a nonzero + * multiple of SIZE_ALIGN bytes between start and end. */ + if (end - start <= OVERHEAD + align_start_up + align_end_down) + return; + start += align_start_up + OVERHEAD; + end -= align_end_down; + + struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end); + c->psize = n->csize = C_INUSE; + c->csize = n->psize = C_INUSE | (end-start); + __bin_chunk(c); +}