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 > PTRDIFF_MAX - SIZE_ALIGN - PAGE_SIZE) {
 220                 errno = ENOMEM;
 221                 return -1;
 222         }
 223         *n = (*n + OVERHEAD + SIZE_ALIGN - 1) & SIZE_MASK;
 224         return 0;
 225 }
 226
 227 static void unbin(struct chunk *c, int i)
 228 {
 229         if (c->prev == c->next)
 230                 a_and_64(&mal.binmap, ~(1ULL<<i));
 231         c->prev->next = c->next;
 232         c->next->prev = c->prev;
 233         c->data[0] |= C_INUSE;
 234         NEXT_CHUNK(c)->data[-1] |= C_INUSE;
 235 }
 236
 237 static int alloc_fwd(struct chunk *c)
 238 {
 239         int i;
 240         size_t k;
 241         while (!((k=c->data[0]) & C_INUSE)) {
 242                 i = bin_index(k);
 243                 lock_bin(i);
 244                 if (c->data[0] == k) {
 245                         unbin(c, i);
 246                         unlock_bin(i);
 247                         return 1;
 248                 }
 249                 unlock_bin(i);
 250         }
 251         return 0;
 252 }
 253
 254 static int alloc_rev(struct chunk *c)
 255 {
 256         int i;
 257         size_t k;
 258         while (!((k=c->data[-1]) & C_INUSE)) {
 259                 i = bin_index(k);
 260                 lock_bin(i);
 261                 if (c->data[-1] == k) {
 262                         unbin(PREV_CHUNK(c), i);
 263                         unlock_bin(i);
 264                         return 1;
 265                 }
 266                 unlock_bin(i);
 267         }
 268         return 0;
 269 }
 270
 271
 272 /* pretrim - trims a chunk _prior_ to removing it from its bin.
 273  * Must be called with i as the ideal bin for size n, j the bin
 274  * for the _free_ chunk self, and bin j locked. */
 275 static int pretrim(struct chunk *self, size_t n, int i, int j)
 276 {
 277         size_t n1;
 278         struct chunk *next, *split;
 279
 280         /* We cannot pretrim if it would require re-binning. */
 281         if (j < 40) return 0;
 282         if (j < i+3) {
 283                 if (j != 63) return 0;
 284                 n1 = CHUNK_SIZE(self);
 285                 if (n1-n <= MMAP_THRESHOLD) return 0;
 286         } else {
 287                 n1 = CHUNK_SIZE(self);
 288         }
 289         if (bin_index(n1-n) != j) return 0;
 290
 291         next = NEXT_CHUNK(self);
 292         split = (void *)((char *)self + n);
 293
 294         split->prev = self->prev;
 295         split->next = self->next;
 296         split->prev->next = split;
 297         split->next->prev = split;
 298         split->data[-1] = n | C_INUSE;
 299         split->data[0] = n1-n;
 300         next->data[-1] = n1-n;
 301         self->data[0] = n | C_INUSE;
 302         return 1;
 303 }
 304
 305 static void trim(struct chunk *self, size_t n)
 306 {
 307         size_t n1 = CHUNK_SIZE(self);
 308         struct chunk *next, *split;
 309
 310         if (n >= n1 - DONTCARE) return;
 311
 312         next = NEXT_CHUNK(self);
 313         split = (void *)((char *)self + n);
 314
 315         split->data[-1] = n | C_INUSE;
 316         split->data[0] = n1-n | C_INUSE;
 317         next->data[-1] = n1-n | C_INUSE;
 318         self->data[0] = n | C_INUSE;
 319
 320         free(CHUNK_TO_MEM(split));
 321 }
 322
 323 void *malloc(size_t n)
 324 {
 325         struct chunk *c;
 326         int i, j;
 327
 328         if (!n || adjust_size(&n) < 0) return 0;
 329
 330         if (n > MMAP_THRESHOLD) {
 331                 size_t len = n + PAGE_SIZE - 1 & -PAGE_SIZE;
 332                 char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
 333                         MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
 334                 if (base == (void *)-1) return 0;
 335                 c = (void *)(base + SIZE_ALIGN - sizeof(size_t));
 336                 c->data[0] = len - (SIZE_ALIGN - sizeof(size_t));
 337                 c->data[-1] = SIZE_ALIGN - sizeof(size_t);
 338                 return CHUNK_TO_MEM(c);
 339         }
 340
 341         i = bin_index_up(n);
 342         for (;;) {
 343                 uint64_t mask = mal.binmap & -(1ULL<<i);
 344                 if (!mask) {
 345                         init_malloc();
 346                         c = expand_heap(n);
 347                         if (!c) return 0;
 348                         if (alloc_rev(c)) {
 349                                 struct chunk *x = c;
 350                                 c = PREV_CHUNK(c);
 351                                 NEXT_CHUNK(x)->data[-1] = c->data[0] =
 352                                         x->data[0] + CHUNK_SIZE(c);
 353                         }
 354                         break;
 355                 }
 356                 j = first_set(mask);
 357                 lock_bin(j);
 358                 c = mal.bins[j].head;
 359                 if (c != BIN_TO_CHUNK(j) && j == bin_index(c->data[0])) {
 360                         if (!pretrim(c, n, i, j)) unbin(c, j);
 361                         unlock_bin(j);
 362                         break;
 363                 }
 364                 unlock_bin(j);
 365         }
 366
 367         /* Now patch up in case we over-allocated */
 368         trim(c, n);
 369
 370         return CHUNK_TO_MEM(c);
 371 }
 372
 373 void *realloc(void *p, size_t n)
 374 {
 375         struct chunk *self, *next;
 376         size_t n0, n1;
 377         void *new;
 378
 379         if (!p) return malloc(n);
 380         else if (!n) return free(p), (void *)0;
 381
 382         if (adjust_size(&n) < 0) return 0;
 383
 384         self = MEM_TO_CHUNK(p);
 385         n1 = n0 = CHUNK_SIZE(self);
 386
 387         if (IS_MMAPPED(self)) {
 388                 size_t extra = self->data[-1];
 389                 char *base = (char *)self - extra;
 390                 size_t oldlen = n0 + extra;
 391                 size_t newlen = n + extra;
 392                 if (newlen < PAGE_SIZE && (new = malloc(n))) {
 393                         memcpy(new, p, n-OVERHEAD);
 394                         free(p);
 395                         return new;
 396                 }
 397                 newlen = (newlen + PAGE_SIZE-1) & -PAGE_SIZE;
 398                 if (oldlen == newlen) return p;
 399                 base = __mremap(base, oldlen, newlen, MREMAP_MAYMOVE);
 400                 if (base == (void *)-1)
 401                         return newlen < oldlen ? p : 0;
 402                 self = (void *)(base + extra);
 403                 self->data[0] = newlen - extra;
 404                 return CHUNK_TO_MEM(self);
 405         }
 406
 407         next = NEXT_CHUNK(self);
 408
 409         /* Merge adjacent chunks if we need more space. This is not
 410          * a waste of time even if we fail to get enough space, because our
 411          * subsequent call to free would otherwise have to do the merge. */
 412         if (n > n1 && alloc_fwd(next)) {
 413                 n1 += CHUNK_SIZE(next);
 414                 next = NEXT_CHUNK(next);
 415         }
 416         /* FIXME: find what's wrong here and reenable it..? */
 417         if (0 && n > n1 && alloc_rev(self)) {
 418                 self = PREV_CHUNK(self);
 419                 n1 += CHUNK_SIZE(self);
 420         }
 421         self->data[0] = n1 | C_INUSE;
 422         next->data[-1] = n1 | C_INUSE;
 423
 424         /* If we got enough space, split off the excess and return */
 425         if (n <= n1) {
 426                 //memmove(CHUNK_TO_MEM(self), p, n0-OVERHEAD);
 427                 trim(self, n);
 428                 return CHUNK_TO_MEM(self);
 429         }
 430
 431         /* As a last resort, allocate a new chunk and copy to it. */
 432         new = malloc(n-OVERHEAD);
 433         if (!new) return 0;
 434         memcpy(new, p, n0-OVERHEAD);
 435         free(CHUNK_TO_MEM(self));
 436         return new;
 437 }
 438
 439 void free(void *p)
 440 {
 441         struct chunk *self = MEM_TO_CHUNK(p);
 442         struct chunk *next;
 443         size_t final_size, new_size, size;
 444         int reclaim=0;
 445         int i;
 446
 447         if (!p) return;
 448
 449         if (IS_MMAPPED(self)) {
 450                 size_t extra = self->data[-1];
 451                 char *base = (char *)self - extra;
 452                 size_t len = CHUNK_SIZE(self) + extra;
 453                 __munmap(base, len);
 454                 return;
 455         }
 456
 457         final_size = new_size = CHUNK_SIZE(self);
 458         next = NEXT_CHUNK(self);
 459
 460         for (;;) {
 461                 /* Replace middle of large chunks with fresh zero pages */
 462                 if (reclaim && (self->data[-1] & next->data[0] & C_INUSE)) {
 463                         uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
 464                         uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
 465 #if 1
 466                         __madvise((void *)a, b-a, MADV_DONTNEED);
 467 #else
 468                         __mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
 469                                 MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
 470 #endif
 471                 }
 472
 473                 if (self->data[-1] & next->data[0] & C_INUSE) {
 474                         self->data[0] = final_size | C_INUSE;
 475                         next->data[-1] = final_size | C_INUSE;
 476                         i = bin_index(final_size);
 477                         lock_bin(i);
 478                         lock(mal.free_lock);
 479                         if (self->data[-1] & next->data[0] & C_INUSE)
 480                                 break;
 481                         unlock(mal.free_lock);
 482                         unlock_bin(i);
 483                 }
 484
 485                 if (alloc_rev(self)) {
 486                         self = PREV_CHUNK(self);
 487                         size = CHUNK_SIZE(self);
 488                         final_size += size;
 489                         if (new_size+size > RECLAIM && (new_size+size^size) > size)
 490                                 reclaim = 1;
 491                 }
 492
 493                 if (alloc_fwd(next)) {
 494                         size = CHUNK_SIZE(next);
 495                         final_size += size;
 496                         if (new_size+size > RECLAIM && (new_size+size^size) > size)
 497                                 reclaim = 1;
 498                         next = NEXT_CHUNK(next);
 499                 }
 500         }
 501
 502         self->data[0] = final_size;
 503         next->data[-1] = final_size;
 504         unlock(mal.free_lock);
 505
 506         self->next = BIN_TO_CHUNK(i);
 507         self->prev = mal.bins[i].tail;
 508         self->next->prev = self;
 509         self->prev->next = self;
 510
 511         if (!(mal.binmap & 1ULL<<i))
 512                 a_or_64(&mal.binmap, 1ULL<<i);
 513
 514         unlock_bin(i);
 515 }