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