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) return;
  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 (!libc.threads_minus_1) return;
  74         a_store(lk, 0);
  75         if (lk[1]) __wake(lk, 1, 1);
  76 }
  77
  78 static inline void lock_bin(int i)
  79 {
  80         if (libc.threads_minus_1)
  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         if (!libc.threads_minus_1) return;
  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) goto fail;
 167
 168         w = MEM_TO_CHUNK(new);
 169         w->psize = n | C_INUSE;
 170         w->csize = 0 | C_INUSE;
 171
 172         w = MEM_TO_CHUNK(mal.brk);
 173         w->csize = n | C_INUSE;
 174         mal.brk = new;
 175
 176         unlock(mal.brk_lock);
 177
 178         return w;
 179 fail:
 180         unlock(mal.brk_lock);
 181         return 0;
 182 }
 183
 184 static int init_malloc(size_t n)
 185 {
 186         static int init, waiters;
 187         int state;
 188         struct chunk *c;
 189
 190         if (init == 2) return 0;
 191
 192         while ((state=a_swap(&init, 1)) == 1)
 193                 __wait(&init, &waiters, 1, 1);
 194         if (state) {
 195                 a_store(&init, 2);
 196                 return 0;
 197         }
 198
 199         mal.brk = __brk(0);
 200 #ifdef SHARED
 201         mal.brk = mal.brk + PAGE_SIZE-1 & -PAGE_SIZE;
 202 #endif
 203         mal.brk = mal.brk + 2*SIZE_ALIGN-1 & -SIZE_ALIGN;
 204
 205         c = expand_heap(n);
 206
 207         if (!c) {
 208                 a_store(&init, 0);
 209                 if (waiters) __wake(&init, 1, 1);
 210                 return -1;
 211         }
 212
 213         mal.heap = (void *)c;
 214         c->psize = 0 | C_INUSE;
 215         free(CHUNK_TO_MEM(c));
 216
 217         a_store(&init, 2);
 218         if (waiters) __wake(&init, -1, 1);
 219         return 1;
 220 }
 221
 222 static int adjust_size(size_t *n)
 223 {
 224         /* Result of pointer difference must fit in ptrdiff_t. */
 225         if (*n-1 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
 226                 if (*n) {
 227                         errno = ENOMEM;
 228                         return -1;
 229                 } else {
 230                         *n = SIZE_ALIGN;
 231                         return 0;
 232                 }
 233         }
 234         *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
 235         return 0;
 236 }
 237
 238 static void unbin(struct chunk *c, int i)
 239 {
 240         if (c->prev == c->next)
 241                 a_and_64(&mal.binmap, ~(1ULL<<i));
 242         c->prev->next = c->next;
 243         c->next->prev = c->prev;
 244         c->csize |= C_INUSE;
 245         NEXT_CHUNK(c)->psize |= C_INUSE;
 246 }
 247
 248 static int alloc_fwd(struct chunk *c)
 249 {
 250         int i;
 251         size_t k;
 252         while (!((k=c->csize) & C_INUSE)) {
 253                 i = bin_index(k);
 254                 lock_bin(i);
 255                 if (c->csize == k) {
 256                         unbin(c, i);
 257                         unlock_bin(i);
 258                         return 1;
 259                 }
 260                 unlock_bin(i);
 261         }
 262         return 0;
 263 }
 264
 265 static int alloc_rev(struct chunk *c)
 266 {
 267         int i;
 268         size_t k;
 269         while (!((k=c->psize) & C_INUSE)) {
 270                 i = bin_index(k);
 271                 lock_bin(i);
 272                 if (c->psize == k) {
 273                         unbin(PREV_CHUNK(c), i);
 274                         unlock_bin(i);
 275                         return 1;
 276                 }
 277                 unlock_bin(i);
 278         }
 279         return 0;
 280 }
 281
 282
 283 /* pretrim - trims a chunk _prior_ to removing it from its bin.
 284  * Must be called with i as the ideal bin for size n, j the bin
 285  * for the _free_ chunk self, and bin j locked. */
 286 static int pretrim(struct chunk *self, size_t n, int i, int j)
 287 {
 288         size_t n1;
 289         struct chunk *next, *split;
 290
 291         /* We cannot pretrim if it would require re-binning. */
 292         if (j < 40) return 0;
 293         if (j < i+3) {
 294                 if (j != 63) return 0;
 295                 n1 = CHUNK_SIZE(self);
 296                 if (n1-n <= MMAP_THRESHOLD) return 0;
 297         } else {
 298                 n1 = CHUNK_SIZE(self);
 299         }
 300         if (bin_index(n1-n) != j) return 0;
 301
 302         next = NEXT_CHUNK(self);
 303         split = (void *)((char *)self + n);
 304
 305         split->prev = self->prev;
 306         split->next = self->next;
 307         split->prev->next = split;
 308         split->next->prev = split;
 309         split->psize = n | C_INUSE;
 310         split->csize = n1-n;
 311         next->psize = n1-n;
 312         self->csize = n | C_INUSE;
 313         return 1;
 314 }
 315
 316 static void trim(struct chunk *self, size_t n)
 317 {
 318         size_t n1 = CHUNK_SIZE(self);
 319         struct chunk *next, *split;
 320
 321         if (n >= n1 - DONTCARE) return;
 322
 323         next = NEXT_CHUNK(self);
 324         split = (void *)((char *)self + n);
 325
 326         split->psize = n | C_INUSE;
 327         split->csize = n1-n | C_INUSE;
 328         next->psize = n1-n | C_INUSE;
 329         self->csize = n | C_INUSE;
 330
 331         free(CHUNK_TO_MEM(split));
 332 }
 333
 334 void *malloc(size_t n)
 335 {
 336         struct chunk *c;
 337         int i, j;
 338
 339         if (adjust_size(&n) < 0) return 0;
 340
 341         if (n > MMAP_THRESHOLD) {
 342                 size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
 343                 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
 344                         MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
 345                 if (base == (void *)-1) return 0;
 346                 c = (void *)(base + SIZE_ALIGN - OVERHEAD);
 347                 c->csize = len - (SIZE_ALIGN - OVERHEAD);
 348                 c->psize = SIZE_ALIGN - OVERHEAD;
 349                 return CHUNK_TO_MEM(c);
 350         }
 351
 352         i = bin_index_up(n);
 353         for (;;) {
 354                 uint64_t mask = mal.binmap & -(1ULL<<i);
 355                 if (!mask) {
 356                         if (init_malloc(n) > 0) continue;
 357                         c = expand_heap(n);
 358                         if (!c) return 0;
 359                         if (alloc_rev(c)) {
 360                                 struct chunk *x = c;
 361                                 c = PREV_CHUNK(c);
 362                                 NEXT_CHUNK(x)->psize = c->csize =
 363                                         x->csize + CHUNK_SIZE(c);
 364                         }
 365                         break;
 366                 }
 367                 j = first_set(mask);
 368                 lock_bin(j);
 369                 c = mal.bins[j].head;
 370                 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->csize)) {
 371                         if (!pretrim(c, n, i, j)) unbin(c, j);
 372                         unlock_bin(j);
 373                         break;
 374                 }
 375                 unlock_bin(j);
 376         }
 377
 378         /* Now patch up in case we over-allocated */
 379         trim(c, n);
 380
 381         return CHUNK_TO_MEM(c);
 382 }
 383
 384 void *realloc(void *p, size_t n)
 385 {
 386         struct chunk *self, *next;
 387         size_t n0, n1;
 388         void *new;
 389
 390         if (!p) return malloc(n);
 391
 392         if (adjust_size(&n) < 0) return 0;
 393
 394         self = MEM_TO_CHUNK(p);
 395         n1 = n0 = CHUNK_SIZE(self);
 396
 397         if (IS_MMAPPED(self)) {
 398                 size_t extra = self->psize;
 399                 char *base = (char *)self - extra;
 400                 size_t oldlen = n0 + extra;
 401                 size_t newlen = n + extra;
 402                 /* Crash on realloc of freed chunk */
 403                 if (extra & 1) a_crash();
 404                 if (newlen < PAGE_SIZE && (new = malloc(n))) {
 405                         memcpy(new, p, n-OVERHEAD);
 406                         free(p);
 407                         return new;
 408                 }
 409                 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
 410                 if (oldlen == newlen) return p;
 411                 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
 412                 if (base == (void *)-1)
 413                         return newlen < oldlen ? p : 0;
 414                 self = (void *)(base + extra);
 415                 self->csize = newlen - extra;
 416                 return CHUNK_TO_MEM(self);
 417         }
 418
 419         next = NEXT_CHUNK(self);
 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         for (;;) {
 475                 /* Replace middle of large chunks with fresh zero pages */
 476                 if (reclaim && (self->psize & next->csize & C_INUSE)) {
 477                         uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
 478                         uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
 479 #if 1
 480                         __madvise((void *)a, b-a, MADV_DONTNEED);
 481 #else
 482                         __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
 483                                 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
 484 #endif
 485                 }
 486
 487                 if (self->psize & next->csize & C_INUSE) {
 488                         self->csize = final_size | C_INUSE;
 489                         next->psize = final_size | C_INUSE;
 490                         i = bin_index(final_size);
 491                         lock_bin(i);
 492                         lock(mal.free_lock);
 493                         if (self->psize & next->csize & C_INUSE)
 494                                 break;
 495                         unlock(mal.free_lock);
 496                         unlock_bin(i);
 497                 }
 498
 499                 if (alloc_rev(self)) {
 500                         self = PREV_CHUNK(self);
 501                         size = CHUNK_SIZE(self);
 502                         final_size += size;
 503                         if (new_size+size > RECLAIM && (new_size+size^size) > size)
 504                                 reclaim = 1;
 505                 }
 506
 507                 if (alloc_fwd(next)) {
 508                         size = CHUNK_SIZE(next);
 509                         final_size += size;
 510                         if (new_size+size > RECLAIM && (new_size+size^size) > size)
 511                                 reclaim = 1;
 512                         next = NEXT_CHUNK(next);
 513                 }
 514         }
 515
 516         self->csize = final_size;
 517         next->psize = final_size;
 518         unlock(mal.free_lock);
 519
 520         self->next = BIN_TO_CHUNK(i);
 521         self->prev = mal.bins[i].tail;
 522         self->next->prev = self;
 523         self->prev->next = self;
 524
 525         if (!(mal.binmap & 1ULL<<i))
 526                 a_or_64(&mal.binmap, 1ULL<<i);
 527
 528         unlock_bin(i);
 529 }