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