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