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