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