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