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