nsz Git - musl/blob - src/malloc/malloc.c

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