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