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()
 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(1);
 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 0;
 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                         init_malloc();
 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                 if (newlen < PAGE_SIZE && (new = malloc(n))) {
 397                         memcpy(new, p, n-OVERHEAD);
 398                         free(p);
 399                         return new;
 400                 }
 401                 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
 402                 if (oldlen == newlen) return p;
 403                 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
 404                 if (base == (void *)-1)
 405                         return newlen < oldlen ? p : 0;
 406                 self = (void *)(base + extra);
 407                 self->data[0] = newlen - extra;
 408                 return CHUNK_TO_MEM(self);
 409         }
 410
 411         next = NEXT_CHUNK(self);
 412
 413         /* Merge adjacent chunks if we need more space. This is not
 414          * a waste of time even if we fail to get enough space, because our
 415          * subsequent call to free would otherwise have to do the merge. */
 416         if (n > n1 && alloc_fwd(next)) {
 417                 n1 += CHUNK_SIZE(next);
 418                 next = NEXT_CHUNK(next);
 419         }
 420         /* FIXME: find what's wrong here and reenable it..? */
 421         if (0 && n > n1 && alloc_rev(self)) {
 422                 self = PREV_CHUNK(self);
 423                 n1 += CHUNK_SIZE(self);
 424         }
 425         self->data[0] = n1 | C_INUSE;
 426         next->data[-1] = n1 | C_INUSE;
 427
 428         /* If we got enough space, split off the excess and return */
 429         if (n <= n1) {
 430                 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
 431                 trim(self, n);
 432                 return CHUNK_TO_MEM(self);
 433         }
 434
 435         /* As a last resort, allocate a new chunk and copy to it. */
 436         new = malloc(n-OVERHEAD);
 437         if (!new) return 0;
 438         memcpy(new, p, n0-OVERHEAD);
 439         free(CHUNK_TO_MEM(self));
 440         return new;
 441 }
 442
 443 void free(void *p)
 444 {
 445         struct chunk *self = MEM_TO_CHUNK(p);
 446         struct chunk *next;
 447         size_t final_size, new_size, size;
 448         int reclaim=0;
 449         int i;
 450
 451         if (!p) return;
 452
 453         if (IS_MMAPPED(self)) {
 454                 size_t extra = self->data[-1];
 455                 char *base = (char *)self - extra;
 456                 size_t len = CHUNK_SIZE(self) + extra;
 457                 __munmap(base, len);
 458                 return;
 459         }
 460
 461         final_size = new_size = CHUNK_SIZE(self);
 462         next = NEXT_CHUNK(self);
 463
 464         for (;;) {
 465                 /* Replace middle of large chunks with fresh zero pages */
 466                 if (reclaim && (self->data[-1] & next->data[0] & C_INUSE)) {
 467                         uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
 468                         uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
 469 #if 1
 470                         __madvise((void *)a, b-a, MADV_DONTNEED);
 471 #else
 472                         __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
 473                                 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
 474 #endif
 475                 }
 476
 477                 if (self->data[-1] & next->data[0] & C_INUSE) {
 478                         self->data[0] = final_size | C_INUSE;
 479                         next->data[-1] = final_size | C_INUSE;
 480                         i = bin_index(final_size);
 481                         lock_bin(i);
 482                         lock(mal.free_lock);
 483                         if (self->data[-1] & next->data[0] & C_INUSE)
 484                                 break;
 485                         unlock(mal.free_lock);
 486                         unlock_bin(i);
 487                 }
 488
 489                 if (alloc_rev(self)) {
 490                         self = PREV_CHUNK(self);
 491                         size = CHUNK_SIZE(self);
 492                         final_size += size;
 493                         if (new_size+size > RECLAIM && (new_size+size^size) > size)
 494                                 reclaim = 1;
 495                 }
 496
 497                 if (alloc_fwd(next)) {
 498                         size = CHUNK_SIZE(next);
 499                         final_size += size;
 500                         if (new_size+size > RECLAIM && (new_size+size^size) > size)
 501                                 reclaim = 1;
 502                         next = NEXT_CHUNK(next);
 503                 }
 504         }
 505
 506         self->data[0] = final_size;
 507         next->data[-1] = final_size;
 508         unlock(mal.free_lock);
 509
 510         self->next = BIN_TO_CHUNK(i);
 511         self->prev = mal.bins[i].tail;
 512         self->next->prev = self;
 513         self->prev->next = self;
 514
 515         if (!(mal.binmap & 1ULL<<i))
 516                 a_or_64(&mal.binmap, 1ULL<<i);
 517
 518         unlock_bin(i);
 519 }