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