nsz Git - musl/blob - src/malloc/oldmalloc/malloc.c

   1 #define _GNU_SOURCE
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <limits.h>
   5 #include <stdint.h>
   6 #include <errno.h>
   7 #include <sys/mman.h>
   8 #include "libc.h"
   9 #include "atomic.h"
  10 #include "pthread_impl.h"
  11 #include "malloc_impl.h"
  12
  13 #define malloc __libc_malloc
  14 #define realloc __libc_realloc
  15 #define free __libc_free
  16
  17 #if defined(__GNUC__) && defined(__PIC__)
  18 #define inline inline __attribute__((always_inline))
  19 #endif
  20
  21 static struct {
  22         volatile uint64_t binmap;
  23         struct bin bins[64];
  24         volatile int split_merge_lock[2];
  25 } mal;
  26
  27 /* Synchronization tools */
  28
  29 static inline void lock(volatile int *lk)
  30 {
  31         int need_locks = libc.need_locks;
  32         if (need_locks) {
  33                 while(a_swap(lk, 1)) __wait(lk, lk+1, 1, 1);
  34                 if (need_locks < 0) libc.need_locks = 0;
  35         }
  36 }
  37
  38 static inline void unlock(volatile int *lk)
  39 {
  40         if (lk[0]) {
  41                 a_store(lk, 0);
  42                 if (lk[1]) __wake(lk, 1, 1);
  43         }
  44 }
  45
  46 static inline void lock_bin(int i)
  47 {
  48         lock(mal.bins[i].lock);
  49         if (!mal.bins[i].head)
  50                 mal.bins[i].head = mal.bins[i].tail = BIN_TO_CHUNK(i);
  51 }
  52
  53 static inline void unlock_bin(int i)
  54 {
  55         unlock(mal.bins[i].lock);
  56 }
  57
  58 static int first_set(uint64_t x)
  59 {
  60 #if 1
  61         return a_ctz_64(x);
  62 #else
  63         static const char debruijn64[64] = {
  64                 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
  65                 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
  66                 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
  67                 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
  68         };
  69         static const char debruijn32[32] = {
  70                 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
  71                 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
  72         };
  73         if (sizeof(long) < 8) {
  74                 uint32_t y = x;
  75                 if (!y) {
  76                         y = x>>32;
  77                         return 32 + debruijn32[(y&-y)*0x076be629 >> 27];
  78                 }
  79                 return debruijn32[(y&-y)*0x076be629 >> 27];
  80         }
  81         return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58];
  82 #endif
  83 }
  84
  85 static const unsigned char bin_tab[60] = {
  86                     32,33,34,35,36,36,37,37,38,38,39,39,
  87         40,40,40,40,41,41,41,41,42,42,42,42,43,43,43,43,
  88         44,44,44,44,44,44,44,44,45,45,45,45,45,45,45,45,
  89         46,46,46,46,46,46,46,46,47,47,47,47,47,47,47,47,
  90 };
  91
  92 static int bin_index(size_t x)
  93 {
  94         x = x / SIZE_ALIGN - 1;
  95         if (x <= 32) return x;
  96         if (x < 512) return bin_tab[x/8-4];
  97         if (x > 0x1c00) return 63;
  98         return bin_tab[x/128-4] + 16;
  99 }
 100
 101 static int bin_index_up(size_t x)
 102 {
 103         x = x / SIZE_ALIGN - 1;
 104         if (x <= 32) return x;
 105         x--;
 106         if (x < 512) return bin_tab[x/8-4] + 1;
 107         return bin_tab[x/128-4] + 17;
 108 }
 109
 110 #if 0
 111 void __dump_heap(int x)
 112 {
 113         struct chunk *c;
 114         int i;
 115         for (c = (void *)mal.heap; CHUNK_SIZE(c); c = NEXT_CHUNK(c))
 116                 fprintf(stderr, "base %p size %zu (%d) flags %d/%d\n",
 117                         c, CHUNK_SIZE(c), bin_index(CHUNK_SIZE(c)),
 118                         c->csize & 15,
 119                         NEXT_CHUNK(c)->psize & 15);
 120         for (i=0; i<64; i++) {
 121                 if (mal.bins[i].head != BIN_TO_CHUNK(i) && mal.bins[i].head) {
 122                         fprintf(stderr, "bin %d: %p\n", i, mal.bins[i].head);
 123                         if (!(mal.binmap & 1ULL<<i))
 124                                 fprintf(stderr, "missing from binmap!\n");
 125                 } else if (mal.binmap & 1ULL<<i)
 126                         fprintf(stderr, "binmap wrongly contains %d!\n", i);
 127         }
 128 }
 129 #endif
 130
 131 /* This function returns true if the interval [old,new]
 132  * intersects the 'len'-sized interval below &libc.auxv
 133  * (interpreted as the main-thread stack) or below &b
 134  * (the current stack). It is used to defend against
 135  * buggy brk implementations that can cross the stack. */
 136
 137 static int traverses_stack_p(uintptr_t old, uintptr_t new)
 138 {
 139         const uintptr_t len = 8<<20;
 140         uintptr_t a, b;
 141
 142         b = (uintptr_t)libc.auxv;
 143         a = b > len ? b-len : 0;
 144         if (new>a && old<b) return 1;
 145
 146         b = (uintptr_t)&b;
 147         a = b > len ? b-len : 0;
 148         if (new>a && old<b) return 1;
 149
 150         return 0;
 151 }
 152
 153 /* Expand the heap in-place if brk can be used, or otherwise via mmap,
 154  * using an exponential lower bound on growth by mmap to make
 155  * fragmentation asymptotically irrelevant. The size argument is both
 156  * an input and an output, since the caller needs to know the size
 157  * allocated, which will be larger than requested due to page alignment
 158  * and mmap minimum size rules. The caller is responsible for locking
 159  * to prevent concurrent calls. */
 160
 161 static void *__expand_heap(size_t *pn)
 162 {
 163         static uintptr_t brk;
 164         static unsigned mmap_step;
 165         size_t n = *pn;
 166
 167         if (n > SIZE_MAX/2 - PAGE_SIZE) {
 168                 errno = ENOMEM;
 169                 return 0;
 170         }
 171         n += -n & PAGE_SIZE-1;
 172
 173         if (!brk) {
 174                 brk = __syscall(SYS_brk, 0);
 175                 brk += -brk & PAGE_SIZE-1;
 176         }
 177
 178         if (n < SIZE_MAX-brk && !traverses_stack_p(brk, brk+n)
 179             && __syscall(SYS_brk, brk+n)==brk+n) {
 180                 *pn = n;
 181                 brk += n;
 182                 return (void *)(brk-n);
 183         }
 184
 185         size_t min = (size_t)PAGE_SIZE << mmap_step/2;
 186         if (n < min) n = min;
 187         void *area = __mmap(0, n, PROT_READ|PROT_WRITE,
 188                 MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
 189         if (area == MAP_FAILED) return 0;
 190         *pn = n;
 191         mmap_step++;
 192         return area;
 193 }
 194
 195 static struct chunk *expand_heap(size_t n)
 196 {
 197         static void *end;
 198         void *p;
 199         struct chunk *w;
 200
 201         /* The argument n already accounts for the caller's chunk
 202          * overhead needs, but if the heap can't be extended in-place,
 203          * we need room for an extra zero-sized sentinel chunk. */
 204         n += SIZE_ALIGN;
 205
 206         p = __expand_heap(&n);
 207         if (!p) return 0;
 208
 209         /* If not just expanding existing space, we need to make a
 210          * new sentinel chunk below the allocated space. */
 211         if (p != end) {
 212                 /* Valid/safe because of the prologue increment. */
 213                 n -= SIZE_ALIGN;
 214                 p = (char *)p + SIZE_ALIGN;
 215                 w = MEM_TO_CHUNK(p);
 216                 w->psize = 0 | C_INUSE;
 217         }
 218
 219         /* Record new heap end and fill in footer. */
 220         end = (char *)p + n;
 221         w = MEM_TO_CHUNK(end);
 222         w->psize = n | C_INUSE;
 223         w->csize = 0 | C_INUSE;
 224
 225         /* Fill in header, which may be new or may be replacing a
 226          * zero-size sentinel header at the old end-of-heap. */
 227         w = MEM_TO_CHUNK(p);
 228         w->csize = n | C_INUSE;
 229
 230         return w;
 231 }
 232
 233 static int adjust_size(size_t *n)
 234 {
 235         /* Result of pointer difference must fit in ptrdiff_t. */
 236         if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
 237                 if (*n) {
 238                         errno = ENOMEM;
 239                         return -1;
 240                 } else {
 241                         *n = SIZE_ALIGN;
 242                         return 0;
 243                 }
 244         }
 245         *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
 246         return 0;
 247 }
 248
 249 static void unbin(struct chunk *c, int i)
 250 {
 251         if (c->prev == c->next)
 252                 a_and_64(&mal.binmap, ~(1ULL<<i));
 253         c->prev->next = c->next;
 254         c->next->prev = c->prev;
 255         c->csize |= C_INUSE;
 256         NEXT_CHUNK(c)->psize |= C_INUSE;
 257 }
 258
 259 static void bin_chunk(struct chunk *self, int i)
 260 {
 261         self->next = BIN_TO_CHUNK(i);
 262         self->prev = mal.bins[i].tail;
 263         self->next->prev = self;
 264         self->prev->next = self;
 265         if (self->prev == BIN_TO_CHUNK(i))
 266                 a_or_64(&mal.binmap, 1ULL<<i);
 267 }
 268
 269 static void trim(struct chunk *self, size_t n)
 270 {
 271         size_t n1 = CHUNK_SIZE(self);
 272         struct chunk *next, *split;
 273
 274         if (n >= n1 - DONTCARE) return;
 275
 276         next = NEXT_CHUNK(self);
 277         split = (void *)((char *)self + n);
 278
 279         split->psize = n | C_INUSE;
 280         split->csize = n1-n;
 281         next->psize = n1-n;
 282         self->csize = n | C_INUSE;
 283
 284         int i = bin_index(n1-n);
 285         lock_bin(i);
 286
 287         bin_chunk(split, i);
 288
 289         unlock_bin(i);
 290 }
 291
 292 void *malloc(size_t n)
 293 {
 294         struct chunk *c;
 295         int i, j;
 296         uint64_t mask;
 297
 298         if (adjust_size(&n) < 0) return 0;
 299
 300         if (n > MMAP_THRESHOLD) {
 301                 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
 302                 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
 303                         MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
 304                 if (base == (void *)-1) return 0;
 305                 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
 306                 c->csize = len - (SIZE_ALIGN - OVERHEAD);
 307                 c->psize = SIZE_ALIGN - OVERHEAD;
 308                 return CHUNK_TO_MEM(c);
 309         }
 310
 311         i = bin_index_up(n);
 312         if (i<63 && (mal.binmap & (1ULL<<i))) {
 313                 lock_bin(i);
 314                 c = mal.bins[i].head;
 315                 if (c != BIN_TO_CHUNK(i) && CHUNK_SIZE(c)-n <= DONTCARE) {
 316                         unbin(c, i);
 317                         unlock_bin(i);
 318                         return CHUNK_TO_MEM(c);
 319                 }
 320                 unlock_bin(i);
 321         }
 322         lock(mal.split_merge_lock);
 323         for (mask = mal.binmap & -(1ULL<<i); mask; mask -= (mask&-mask)) {
 324                 j = first_set(mask);
 325                 lock_bin(j);
 326                 c = mal.bins[j].head;
 327                 if (c != BIN_TO_CHUNK(j)) {
 328                         unbin(c, j);
 329                         unlock_bin(j);
 330                         break;
 331                 }
 332                 unlock_bin(j);
 333         }
 334         if (!mask) {
 335                 c = expand_heap(n);
 336                 if (!c) {
 337                         unlock(mal.split_merge_lock);
 338                         return 0;
 339                 }
 340         }
 341         trim(c, n);
 342         unlock(mal.split_merge_lock);
 343         return CHUNK_TO_MEM(c);
 344 }
 345
 346 int __malloc_allzerop(void *p)
 347 {
 348         return IS_MMAPPED(MEM_TO_CHUNK(p));
 349 }
 350
 351 void *realloc(void *p, size_t n)
 352 {
 353         struct chunk *self, *next;
 354         size_t n0, n1;
 355         void *new;
 356
 357         if (!p) return malloc(n);
 358
 359         if (adjust_size(&n) < 0) return 0;
 360
 361         self = MEM_TO_CHUNK(p);
 362         n1 = n0 = CHUNK_SIZE(self);
 363
 364         if (n<=n0 && n0-n<=DONTCARE) return p;
 365
 366         if (IS_MMAPPED(self)) {
 367                 size_t extra = self->psize;
 368                 char *base = (char *)self - extra;
 369                 size_t oldlen = n0 + extra;
 370                 size_t newlen = n + extra;
 371                 /* Crash on realloc of freed chunk */
 372                 if (extra & 1) a_crash();
 373                 if (newlen < PAGE_SIZE && (new = malloc(n-OVERHEAD))) {
 374                         n0 = n;
 375                         goto copy_free_ret;
 376                 }
 377                 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
 378                 if (oldlen == newlen) return p;
 379                 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
 380                 if (base == (void *)-1)
 381                         goto copy_realloc;
 382                 self = (void *)(base + extra);
 383                 self->csize = newlen - extra;
 384                 return CHUNK_TO_MEM(self);
 385         }
 386
 387         next = NEXT_CHUNK(self);
 388
 389         /* Crash on corrupted footer (likely from buffer overflow) */
 390         if (next->psize != self->csize) a_crash();
 391
 392         if (n < n0) {
 393                 int i = bin_index_up(n);
 394                 int j = bin_index(n0);
 395                 if (i<j && (mal.binmap & (1ULL << i)))
 396                         goto copy_realloc;
 397                 struct chunk *split = (void *)((char *)self + n);
 398                 self->csize = split->psize = n | C_INUSE;
 399                 split->csize = next->psize = n0-n | C_INUSE;
 400                 __bin_chunk(split);
 401                 return CHUNK_TO_MEM(self);
 402         }
 403
 404         lock(mal.split_merge_lock);
 405
 406         size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);
 407         if (n0+nsize >= n) {
 408                 int i = bin_index(nsize);
 409                 lock_bin(i);
 410                 if (!(next->csize & C_INUSE)) {
 411                         unbin(next, i);
 412                         unlock_bin(i);
 413                         next = NEXT_CHUNK(next);
 414                         self->csize = next->psize = n0+nsize | C_INUSE;
 415                         trim(self, n);
 416                         unlock(mal.split_merge_lock);
 417                         return CHUNK_TO_MEM(self);
 418                 }
 419                 unlock_bin(i);
 420         }
 421         unlock(mal.split_merge_lock);
 422
 423 copy_realloc:
 424         /* As a last resort, allocate a new chunk and copy to it. */
 425         new = malloc(n-OVERHEAD);
 426         if (!new) return 0;
 427 copy_free_ret:
 428         memcpy(new, p, (n<n0 ? n : n0) - OVERHEAD);
 429         free(CHUNK_TO_MEM(self));
 430         return new;
 431 }
 432
 433 void __bin_chunk(struct chunk *self)
 434 {
 435         struct chunk *next = NEXT_CHUNK(self);
 436
 437         /* Crash on corrupted footer (likely from buffer overflow) */
 438         if (next->psize != self->csize) a_crash();
 439
 440         lock(mal.split_merge_lock);
 441
 442         size_t osize = CHUNK_SIZE(self), size = osize;
 443
 444         /* Since we hold split_merge_lock, only transition from free to
 445          * in-use can race; in-use to free is impossible */
 446         size_t psize = self->psize & C_INUSE ? 0 : CHUNK_PSIZE(self);
 447         size_t nsize = next->csize & C_INUSE ? 0 : CHUNK_SIZE(next);
 448
 449         if (psize) {
 450                 int i = bin_index(psize);
 451                 lock_bin(i);
 452                 if (!(self->psize & C_INUSE)) {
 453                         struct chunk *prev = PREV_CHUNK(self);
 454                         unbin(prev, i);
 455                         self = prev;
 456                         size += psize;
 457                 }
 458                 unlock_bin(i);
 459         }
 460         if (nsize) {
 461                 int i = bin_index(nsize);
 462                 lock_bin(i);
 463                 if (!(next->csize & C_INUSE)) {
 464                         unbin(next, i);
 465                         next = NEXT_CHUNK(next);
 466                         size += nsize;
 467                 }
 468                 unlock_bin(i);
 469         }
 470
 471         int i = bin_index(size);
 472         lock_bin(i);
 473
 474         self->csize = size;
 475         next->psize = size;
 476         bin_chunk(self, i);
 477         unlock(mal.split_merge_lock);
 478
 479         /* Replace middle of large chunks with fresh zero pages */
 480         if (size > RECLAIM && (size^(size-osize)) > size-osize) {
 481                 uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
 482                 uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
 483 #if 1
 484                 __madvise((void *)a, b-a, MADV_DONTNEED);
 485 #else
 486                 __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
 487                         MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
 488 #endif
 489         }
 490
 491         unlock_bin(i);
 492 }
 493
 494 static void unmap_chunk(struct chunk *self)
 495 {
 496         size_t extra = self->psize;
 497         char *base = (char *)self - extra;
 498         size_t len = CHUNK_SIZE(self) + extra;
 499         /* Crash on double free */
 500         if (extra & 1) a_crash();
 501         __munmap(base, len);
 502 }
 503
 504 void free(void *p)
 505 {
 506         if (!p) return;
 507
 508         struct chunk *self = MEM_TO_CHUNK(p);
 509
 510         if (IS_MMAPPED(self))
 511                 unmap_chunk(self);
 512         else
 513                 __bin_chunk(self);
 514 }
 515
 516 void __malloc_donate(char *start, char *end)
 517 {
 518         size_t align_start_up = (SIZE_ALIGN-1) & (-(uintptr_t)start - OVERHEAD);
 519         size_t align_end_down = (SIZE_ALIGN-1) & (uintptr_t)end;
 520
 521         /* Getting past this condition ensures that the padding for alignment
 522          * and header overhead will not overflow and will leave a nonzero
 523          * multiple of SIZE_ALIGN bytes between start and end. */
 524         if (end - start <= OVERHEAD + align_start_up + align_end_down)
 525                 return;
 526         start += align_start_up + OVERHEAD;
 527         end   -= align_end_down;
 528
 529         struct chunk *c = MEM_TO_CHUNK(start), *n = MEM_TO_CHUNK(end);
 530         c->psize = n->csize = C_INUSE;
 531         c->csize = n->psize = C_INUSE | (end-start);
 532         __bin_chunk(c);
 533 }