src/lj_alloc.c

   1 /*
   2 ** Bundled memory allocator.
   3 **
   4 ** Beware: this is a HEAVILY CUSTOMIZED version of dlmalloc.
   5 ** The original bears the following remark:
   6 **
   7 **   This is a version (aka dlmalloc) of malloc/free/realloc written by
   8 **   Doug Lea and released to the public domain, as explained at
   9 **   http://creativecommons.org/licenses/publicdomain.
  10 **
  11 **   * Version pre-2.8.4 Wed Mar 29 19:46:29 2006    (dl at gee)
  12 **
  13 ** No additional copyright is claimed over the customizations.
  14 ** Please do NOT bother the original author about this version here!
  15 **
  16 ** If you want to use dlmalloc in another project, you should get
  17 ** the original from: ftp://gee.cs.oswego.edu/pub/misc/
  18 ** For thread-safe derivatives, take a look at:
  19 ** - ptmalloc: http://www.malloc.de/
  20 ** - nedmalloc: http://www.nedprod.com/programs/portable/nedmalloc/
  21 */
  22
  23 #define lj_alloc_c
  24 #define LUA_CORE
  25
  26 /* To get the mremap prototype. Must be defind before any system includes. */
  27 #if defined(__linux__) && !defined(_GNU_SOURCE)
  28 #define _GNU_SOURCE
  29 #endif
  30
  31 #include "lj_def.h"
  32 #include "lj_arch.h"
  33 #include "lj_alloc.h"
  34
  35 #ifndef LUAJIT_USE_SYSMALLOC
  36
  37 #define MAX_SIZE_T              (~(size_t)0)
  38 #define MALLOC_ALIGNMENT        ((size_t)8U)
  39
  40 #define DEFAULT_GRANULARITY     ((size_t)128U * (size_t)1024U)
  41 #define DEFAULT_TRIM_THRESHOLD  ((size_t)2U * (size_t)1024U * (size_t)1024U)
  42 #define DEFAULT_MMAP_THRESHOLD  ((size_t)128U * (size_t)1024U)
  43 #define MAX_RELEASE_CHECK_RATE  255
  44
  45 /* ------------------- size_t and alignment properties -------------------- */
  46
  47 /* The byte and bit size of a size_t */
  48 #define SIZE_T_SIZE             (sizeof(size_t))
  49 #define SIZE_T_BITSIZE          (sizeof(size_t) << 3)
  50
  51 /* Some constants coerced to size_t */
  52 /* Annoying but necessary to avoid errors on some platforms */
  53 #define SIZE_T_ZERO             ((size_t)0)
  54 #define SIZE_T_ONE              ((size_t)1)
  55 #define SIZE_T_TWO              ((size_t)2)
  56 #define TWO_SIZE_T_SIZES        (SIZE_T_SIZE<<1)
  57 #define FOUR_SIZE_T_SIZES       (SIZE_T_SIZE<<2)
  58 #define SIX_SIZE_T_SIZES        (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
  59
  60 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
  61 #define CHUNK_ALIGN_MASK        (MALLOC_ALIGNMENT - SIZE_T_ONE)
  62
  63 /* the number of bytes to offset an address to align it */
  64 #define align_offset(A)\
  65  ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
  66   ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
  67
  68 /* -------------------------- MMAP support ------------------------------- */
  69
  70 #define MFAIL                   ((void *)(MAX_SIZE_T))
  71 #define CMFAIL                  ((char *)(MFAIL)) /* defined for convenience */
  72
  73 #define IS_DIRECT_BIT           (SIZE_T_ONE)
  74
  75 #ifdef LUA_USE_WIN
  76
  77 #define WIN32_LEAN_AND_MEAN
  78 #include <windows.h>
  79
  80 #if LJ_64
  81
  82 /* Undocumented, but hey, that's what we all love so much about Windows. */
  83 typedef long (*PNTAVM)(HANDLE handle, void **addr, ULONG zbits,
  84                        size_t *size, ULONG alloctype, ULONG prot);
  85 static PNTAVM ntavm;
  86
  87 /* Number of top bits of the lower 32 bits of an address that must be zero.
  88 ** Apparently 0 gives us full 64 bit addresses and 1 gives us the lower 2GB.
  89 */
  90 #define NTAVM_ZEROBITS          1
  91
  92 static void INIT_MMAP(void)
  93 {
  94   ntavm = (PNTAVM)GetProcAddress(GetModuleHandle("ntdll.dll"),
  95                                  "NtAllocateVirtualMemory");
  96 }
  97
  98 /* Win64 32 bit MMAP via NtAllocateVirtualMemory. */
  99 static LJ_AINLINE void *CALL_MMAP(size_t size)
 100 {
 101   void *ptr = NULL;
 102   long st = ntavm(INVALID_HANDLE_VALUE, &ptr, NTAVM_ZEROBITS, &size,
 103                   MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
 104   return st == 0 ? ptr : MFAIL;
 105 }
 106
 107 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
 108 static LJ_AINLINE void *DIRECT_MMAP(size_t size)
 109 {
 110   void *ptr = NULL;
 111   long st = ntavm(INVALID_HANDLE_VALUE, &ptr, NTAVM_ZEROBITS, &size,
 112                   MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN, PAGE_READWRITE);
 113   return st == 0 ? ptr : MFAIL;
 114 }
 115
 116 #else
 117
 118 #define INIT_MMAP()             ((void)0)
 119
 120 /* Win32 MMAP via VirtualAlloc */
 121 static LJ_AINLINE void *CALL_MMAP(size_t size)
 122 {
 123   void *ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
 124   return ptr ? ptr : MFAIL;
 125 }
 126
 127 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
 128 static LJ_AINLINE void *DIRECT_MMAP(size_t size)
 129 {
 130   void *ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
 131                            PAGE_READWRITE);
 132   return ptr ? ptr : MFAIL;
 133 }
 134
 135 #endif
 136
 137 /* This function supports releasing coalesed segments */
 138 static LJ_AINLINE int CALL_MUNMAP(void *ptr, size_t size)
 139 {
 140   MEMORY_BASIC_INFORMATION minfo;
 141   char *cptr = (char *)ptr;
 142   while (size) {
 143     if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
 144       return -1;
 145     if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
 146         minfo.State != MEM_COMMIT || minfo.RegionSize > size)
 147       return -1;
 148     if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
 149       return -1;
 150     cptr += minfo.RegionSize;
 151     size -= minfo.RegionSize;
 152   }
 153   return 0;
 154 }
 155
 156 #else
 157
 158 #include <sys/mman.h>
 159
 160 #define MMAP_PROT               (PROT_READ|PROT_WRITE)
 161 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
 162 #define MAP_ANONYMOUS           MAP_ANON
 163 #endif /* MAP_ANON */
 164
 165 #if LJ_64
 166 #define MMAP_FLAGS              (MAP_PRIVATE|MAP_ANONYMOUS|MAP_32BIT)
 167 #else
 168 #define MMAP_FLAGS              (MAP_PRIVATE|MAP_ANONYMOUS)
 169 #endif
 170
 171 #define INIT_MMAP()             ((void)0)
 172 #define CALL_MMAP(s)            mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
 173 #define DIRECT_MMAP(s)          CALL_MMAP(s)
 174 #define CALL_MUNMAP(a, s)       munmap((a), (s))
 175
 176 #ifdef __linux__
 177 /* Need to define _GNU_SOURCE to get the mremap prototype. */
 178 #define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
 179 #define CALL_MREMAP_NOMOVE      0
 180 #define CALL_MREMAP_MAYMOVE     1
 181 #if LJ_64
 182 #define CALL_MREMAP_MV          CALL_MREMAP_NOMOVE
 183 #else
 184 #define CALL_MREMAP_MV          CALL_MREMAP_MAYMOVE
 185 #endif
 186 #endif
 187
 188 #endif
 189
 190 #ifndef CALL_MREMAP
 191 #define CALL_MREMAP(addr, osz, nsz, mv) ((void)osz, MFAIL)
 192 #endif
 193
 194 /* -----------------------  Chunk representations ------------------------ */
 195
 196 struct malloc_chunk {
 197   size_t               prev_foot;  /* Size of previous chunk (if free).  */
 198   size_t               head;       /* Size and inuse bits. */
 199   struct malloc_chunk *fd;         /* double links -- used only if free. */
 200   struct malloc_chunk *bk;
 201 };
 202
 203 typedef struct malloc_chunk  mchunk;
 204 typedef struct malloc_chunk *mchunkptr;
 205 typedef struct malloc_chunk *sbinptr;  /* The type of bins of chunks */
 206 typedef size_t bindex_t;               /* Described below */
 207 typedef unsigned int binmap_t;         /* Described below */
 208 typedef unsigned int flag_t;           /* The type of various bit flag sets */
 209
 210 /* ------------------- Chunks sizes and alignments ----------------------- */
 211
 212 #define MCHUNK_SIZE             (sizeof(mchunk))
 213
 214 #define CHUNK_OVERHEAD          (SIZE_T_SIZE)
 215
 216 /* Direct chunks need a second word of overhead ... */
 217 #define DIRECT_CHUNK_OVERHEAD   (TWO_SIZE_T_SIZES)
 218 /* ... and additional padding for fake next-chunk at foot */
 219 #define DIRECT_FOOT_PAD         (FOUR_SIZE_T_SIZES)
 220
 221 /* The smallest size we can malloc is an aligned minimal chunk */
 222 #define MIN_CHUNK_SIZE\
 223   ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
 224
 225 /* conversion from malloc headers to user pointers, and back */
 226 #define chunk2mem(p)            ((void *)((char *)(p) + TWO_SIZE_T_SIZES))
 227 #define mem2chunk(mem)          ((mchunkptr)((char *)(mem) - TWO_SIZE_T_SIZES))
 228 /* chunk associated with aligned address A */
 229 #define align_as_chunk(A)       (mchunkptr)((A) + align_offset(chunk2mem(A)))
 230
 231 /* Bounds on request (not chunk) sizes. */
 232 #define MAX_REQUEST             ((~MIN_CHUNK_SIZE+1) << 2)
 233 #define MIN_REQUEST             (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
 234
 235 /* pad request bytes into a usable size */
 236 #define pad_request(req) \
 237    (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
 238
 239 /* pad request, checking for minimum (but not maximum) */
 240 #define request2size(req) \
 241   (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
 242
 243 /* ------------------ Operations on head and foot fields ----------------- */
 244
 245 #define PINUSE_BIT              (SIZE_T_ONE)
 246 #define CINUSE_BIT              (SIZE_T_TWO)
 247 #define INUSE_BITS              (PINUSE_BIT|CINUSE_BIT)
 248
 249 /* Head value for fenceposts */
 250 #define FENCEPOST_HEAD          (INUSE_BITS|SIZE_T_SIZE)
 251
 252 /* extraction of fields from head words */
 253 #define cinuse(p)               ((p)->head & CINUSE_BIT)
 254 #define pinuse(p)               ((p)->head & PINUSE_BIT)
 255 #define chunksize(p)            ((p)->head & ~(INUSE_BITS))
 256
 257 #define clear_pinuse(p)         ((p)->head &= ~PINUSE_BIT)
 258 #define clear_cinuse(p)         ((p)->head &= ~CINUSE_BIT)
 259
 260 /* Treat space at ptr +/- offset as a chunk */
 261 #define chunk_plus_offset(p, s)         ((mchunkptr)(((char *)(p)) + (s)))
 262 #define chunk_minus_offset(p, s)        ((mchunkptr)(((char *)(p)) - (s)))
 263
 264 /* Ptr to next or previous physical malloc_chunk. */
 265 #define next_chunk(p)   ((mchunkptr)(((char *)(p)) + ((p)->head & ~INUSE_BITS)))
 266 #define prev_chunk(p)   ((mchunkptr)(((char *)(p)) - ((p)->prev_foot) ))
 267
 268 /* extract next chunk's pinuse bit */
 269 #define next_pinuse(p)  ((next_chunk(p)->head) & PINUSE_BIT)
 270
 271 /* Get/set size at footer */
 272 #define get_foot(p, s)  (((mchunkptr)((char *)(p) + (s)))->prev_foot)
 273 #define set_foot(p, s)  (((mchunkptr)((char *)(p) + (s)))->prev_foot = (s))
 274
 275 /* Set size, pinuse bit, and foot */
 276 #define set_size_and_pinuse_of_free_chunk(p, s)\
 277   ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
 278
 279 /* Set size, pinuse bit, foot, and clear next pinuse */
 280 #define set_free_with_pinuse(p, s, n)\
 281   (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
 282
 283 #define is_direct(p)\
 284   (!((p)->head & PINUSE_BIT) && ((p)->prev_foot & IS_DIRECT_BIT))
 285
 286 /* Get the internal overhead associated with chunk p */
 287 #define overhead_for(p)\
 288  (is_direct(p)? DIRECT_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
 289
 290 /* ---------------------- Overlaid data structures ----------------------- */
 291
 292 struct malloc_tree_chunk {
 293   /* The first four fields must be compatible with malloc_chunk */
 294   size_t                    prev_foot;
 295   size_t                    head;
 296   struct malloc_tree_chunk *fd;
 297   struct malloc_tree_chunk *bk;
 298
 299   struct malloc_tree_chunk *child[2];
 300   struct malloc_tree_chunk *parent;
 301   bindex_t                  index;
 302 };
 303
 304 typedef struct malloc_tree_chunk  tchunk;
 305 typedef struct malloc_tree_chunk *tchunkptr;
 306 typedef struct malloc_tree_chunk *tbinptr; /* The type of bins of trees */
 307
 308 /* A little helper macro for trees */
 309 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
 310
 311 /* ----------------------------- Segments -------------------------------- */
 312
 313 struct malloc_segment {
 314   char        *base;             /* base address */
 315   size_t       size;             /* allocated size */
 316   struct malloc_segment *next;   /* ptr to next segment */
 317 };
 318
 319 typedef struct malloc_segment  msegment;
 320 typedef struct malloc_segment *msegmentptr;
 321
 322 /* ---------------------------- malloc_state ----------------------------- */
 323
 324 /* Bin types, widths and sizes */
 325 #define NSMALLBINS              (32U)
 326 #define NTREEBINS               (32U)
 327 #define SMALLBIN_SHIFT          (3U)
 328 #define SMALLBIN_WIDTH          (SIZE_T_ONE << SMALLBIN_SHIFT)
 329 #define TREEBIN_SHIFT           (8U)
 330 #define MIN_LARGE_SIZE          (SIZE_T_ONE << TREEBIN_SHIFT)
 331 #define MAX_SMALL_SIZE          (MIN_LARGE_SIZE - SIZE_T_ONE)
 332 #define MAX_SMALL_REQUEST  (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
 333
 334 struct malloc_state {
 335   binmap_t   smallmap;
 336   binmap_t   treemap;
 337   size_t     dvsize;
 338   size_t     topsize;
 339   mchunkptr  dv;
 340   mchunkptr  top;
 341   size_t     trim_check;
 342   size_t     release_checks;
 343   mchunkptr  smallbins[(NSMALLBINS+1)*2];
 344   tbinptr    treebins[NTREEBINS];
 345   msegment   seg;
 346 };
 347
 348 typedef struct malloc_state *mstate;
 349
 350 #define is_initialized(M)       ((M)->top != 0)
 351
 352 /* -------------------------- system alloc setup ------------------------- */
 353
 354 /* page-align a size */
 355 #define page_align(S)\
 356  (((S) + (LJ_PAGESIZE - SIZE_T_ONE)) & ~(LJ_PAGESIZE - SIZE_T_ONE))
 357
 358 /* granularity-align a size */
 359 #define granularity_align(S)\
 360   (((S) + (DEFAULT_GRANULARITY - SIZE_T_ONE))\
 361    & ~(DEFAULT_GRANULARITY - SIZE_T_ONE))
 362
 363 #ifdef LUA_USE_WIN
 364 #define mmap_align(S)   granularity_align(S)
 365 #else
 366 #define mmap_align(S)   page_align(S)
 367 #endif
 368
 369 /*  True if segment S holds address A */
 370 #define segment_holds(S, A)\
 371   ((char *)(A) >= S->base && (char *)(A) < S->base + S->size)
 372
 373 /* Return segment holding given address */
 374 static msegmentptr segment_holding(mstate m, char *addr)
 375 {
 376   msegmentptr sp = &m->seg;
 377   for (;;) {
 378     if (addr >= sp->base && addr < sp->base + sp->size)
 379       return sp;
 380     if ((sp = sp->next) == 0)
 381       return 0;
 382   }
 383 }
 384
 385 /* Return true if segment contains a segment link */
 386 static int has_segment_link(mstate m, msegmentptr ss)
 387 {
 388   msegmentptr sp = &m->seg;
 389   for (;;) {
 390     if ((char *)sp >= ss->base && (char *)sp < ss->base + ss->size)
 391       return 1;
 392     if ((sp = sp->next) == 0)
 393       return 0;
 394   }
 395 }
 396
 397 /*
 398   TOP_FOOT_SIZE is padding at the end of a segment, including space
 399   that may be needed to place segment records and fenceposts when new
 400   noncontiguous segments are added.
 401 */
 402 #define TOP_FOOT_SIZE\
 403   (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
 404
 405 /* ---------------------------- Indexing Bins ---------------------------- */
 406
 407 #define is_small(s)             (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
 408 #define small_index(s)          ((s)  >> SMALLBIN_SHIFT)
 409 #define small_index2size(i)     ((i)  << SMALLBIN_SHIFT)
 410 #define MIN_SMALL_INDEX         (small_index(MIN_CHUNK_SIZE))
 411
 412 /* addressing by index. See above about smallbin repositioning */
 413 #define smallbin_at(M, i)       ((sbinptr)((char *)&((M)->smallbins[(i)<<1])))
 414 #define treebin_at(M,i)         (&((M)->treebins[i]))
 415
 416 /* assign tree index for size S to variable I */
 417 #define compute_tree_index(S, I)\
 418 {\
 419   unsigned int X = (unsigned int)(S >> TREEBIN_SHIFT);\
 420   if (X == 0) {\
 421     I = 0;\
 422   } else if (X > 0xFFFF) {\
 423     I = NTREEBINS-1;\
 424   } else {\
 425     unsigned int K = lj_fls(X);\
 426     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
 427   }\
 428 }
 429
 430 /* Bit representing maximum resolved size in a treebin at i */
 431 #define bit_for_tree_index(i) \
 432    (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
 433
 434 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
 435 #define leftshift_for_tree_index(i) \
 436    ((i == NTREEBINS-1)? 0 : \
 437     ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
 438
 439 /* The size of the smallest chunk held in bin with index i */
 440 #define minsize_for_tree_index(i) \
 441    ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) |  \
 442    (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
 443
 444 /* ------------------------ Operations on bin maps ----------------------- */
 445
 446 /* bit corresponding to given index */
 447 #define idx2bit(i)              ((binmap_t)(1) << (i))
 448
 449 /* Mark/Clear bits with given index */
 450 #define mark_smallmap(M,i)      ((M)->smallmap |=  idx2bit(i))
 451 #define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))
 452 #define smallmap_is_marked(M,i) ((M)->smallmap &   idx2bit(i))
 453
 454 #define mark_treemap(M,i)       ((M)->treemap  |=  idx2bit(i))
 455 #define clear_treemap(M,i)      ((M)->treemap  &= ~idx2bit(i))
 456 #define treemap_is_marked(M,i)  ((M)->treemap  &   idx2bit(i))
 457
 458 /* mask with all bits to left of least bit of x on */
 459 #define left_bits(x)            ((x<<1) | (~(x<<1)+1))
 460
 461 /* Set cinuse bit and pinuse bit of next chunk */
 462 #define set_inuse(M,p,s)\
 463   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
 464   ((mchunkptr)(((char *)(p)) + (s)))->head |= PINUSE_BIT)
 465
 466 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
 467 #define set_inuse_and_pinuse(M,p,s)\
 468   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
 469   ((mchunkptr)(((char *)(p)) + (s)))->head |= PINUSE_BIT)
 470
 471 /* Set size, cinuse and pinuse bit of this chunk */
 472 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
 473   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
 474
 475 /* ----------------------- Operations on smallbins ----------------------- */
 476
 477 /* Link a free chunk into a smallbin  */
 478 #define insert_small_chunk(M, P, S) {\
 479   bindex_t I = small_index(S);\
 480   mchunkptr B = smallbin_at(M, I);\
 481   mchunkptr F = B;\
 482   if (!smallmap_is_marked(M, I))\
 483     mark_smallmap(M, I);\
 484   else\
 485     F = B->fd;\
 486   B->fd = P;\
 487   F->bk = P;\
 488   P->fd = F;\
 489   P->bk = B;\
 490 }
 491
 492 /* Unlink a chunk from a smallbin  */
 493 #define unlink_small_chunk(M, P, S) {\
 494   mchunkptr F = P->fd;\
 495   mchunkptr B = P->bk;\
 496   bindex_t I = small_index(S);\
 497   if (F == B) {\
 498     clear_smallmap(M, I);\
 499   } else {\
 500     F->bk = B;\
 501     B->fd = F;\
 502   }\
 503 }
 504
 505 /* Unlink the first chunk from a smallbin */
 506 #define unlink_first_small_chunk(M, B, P, I) {\
 507   mchunkptr F = P->fd;\
 508   if (B == F) {\
 509     clear_smallmap(M, I);\
 510   } else {\
 511     B->fd = F;\
 512     F->bk = B;\
 513   }\
 514 }
 515
 516 /* Replace dv node, binning the old one */
 517 /* Used only when dvsize known to be small */
 518 #define replace_dv(M, P, S) {\
 519   size_t DVS = M->dvsize;\
 520   if (DVS != 0) {\
 521     mchunkptr DV = M->dv;\
 522     insert_small_chunk(M, DV, DVS);\
 523   }\
 524   M->dvsize = S;\
 525   M->dv = P;\
 526 }
 527
 528 /* ------------------------- Operations on trees ------------------------- */
 529
 530 /* Insert chunk into tree */
 531 #define insert_large_chunk(M, X, S) {\
 532   tbinptr *H;\
 533   bindex_t I;\
 534   compute_tree_index(S, I);\
 535   H = treebin_at(M, I);\
 536   X->index = I;\
 537   X->child[0] = X->child[1] = 0;\
 538   if (!treemap_is_marked(M, I)) {\
 539     mark_treemap(M, I);\
 540     *H = X;\
 541     X->parent = (tchunkptr)H;\
 542     X->fd = X->bk = X;\
 543   } else {\
 544     tchunkptr T = *H;\
 545     size_t K = S << leftshift_for_tree_index(I);\
 546     for (;;) {\
 547       if (chunksize(T) != S) {\
 548         tchunkptr *C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
 549         K <<= 1;\
 550         if (*C != 0) {\
 551           T = *C;\
 552         } else {\
 553           *C = X;\
 554           X->parent = T;\
 555           X->fd = X->bk = X;\
 556           break;\
 557         }\
 558       } else {\
 559         tchunkptr F = T->fd;\
 560         T->fd = F->bk = X;\
 561         X->fd = F;\
 562         X->bk = T;\
 563         X->parent = 0;\
 564         break;\
 565       }\
 566     }\
 567   }\
 568 }
 569
 570 #define unlink_large_chunk(M, X) {\
 571   tchunkptr XP = X->parent;\
 572   tchunkptr R;\
 573   if (X->bk != X) {\
 574     tchunkptr F = X->fd;\
 575     R = X->bk;\
 576     F->bk = R;\
 577     R->fd = F;\
 578   } else {\
 579     tchunkptr *RP;\
 580     if (((R = *(RP = &(X->child[1]))) != 0) ||\
 581         ((R = *(RP = &(X->child[0]))) != 0)) {\
 582       tchunkptr *CP;\
 583       while ((*(CP = &(R->child[1])) != 0) ||\
 584              (*(CP = &(R->child[0])) != 0)) {\
 585         R = *(RP = CP);\
 586       }\
 587       *RP = 0;\
 588     }\
 589   }\
 590   if (XP != 0) {\
 591     tbinptr *H = treebin_at(M, X->index);\
 592     if (X == *H) {\
 593       if ((*H = R) == 0) \
 594         clear_treemap(M, X->index);\
 595     } else {\
 596       if (XP->child[0] == X) \
 597         XP->child[0] = R;\
 598       else \
 599         XP->child[1] = R;\
 600     }\
 601     if (R != 0) {\
 602       tchunkptr C0, C1;\
 603       R->parent = XP;\
 604       if ((C0 = X->child[0]) != 0) {\
 605         R->child[0] = C0;\
 606         C0->parent = R;\
 607       }\
 608       if ((C1 = X->child[1]) != 0) {\
 609         R->child[1] = C1;\
 610         C1->parent = R;\
 611       }\
 612     }\
 613   }\
 614 }
 615
 616 /* Relays to large vs small bin operations */
 617
 618 #define insert_chunk(M, P, S)\
 619   if (is_small(S)) { insert_small_chunk(M, P, S)\
 620   } else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
 621
 622 #define unlink_chunk(M, P, S)\
 623   if (is_small(S)) { unlink_small_chunk(M, P, S)\
 624   } else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
 625
 626 /* -----------------------  Direct-mmapping chunks ----------------------- */
 627
 628 static void *direct_alloc(size_t nb)
 629 {
 630   size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
 631   if (LJ_LIKELY(mmsize > nb)) {     /* Check for wrap around 0 */
 632     char *mm = (char *)(DIRECT_MMAP(mmsize));
 633     if (mm != CMFAIL) {
 634       size_t offset = align_offset(chunk2mem(mm));
 635       size_t psize = mmsize - offset - DIRECT_FOOT_PAD;
 636       mchunkptr p = (mchunkptr)(mm + offset);
 637       p->prev_foot = offset | IS_DIRECT_BIT;
 638       p->head = psize|CINUSE_BIT;
 639       chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
 640       chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
 641       return chunk2mem(p);
 642     }
 643   }
 644   return NULL;
 645 }
 646
 647 static mchunkptr direct_resize(mchunkptr oldp, size_t nb)
 648 {
 649   size_t oldsize = chunksize(oldp);
 650   if (is_small(nb)) /* Can't shrink direct regions below small size */
 651     return NULL;
 652   /* Keep old chunk if big enough but not too big */
 653   if (oldsize >= nb + SIZE_T_SIZE &&
 654       (oldsize - nb) <= (DEFAULT_GRANULARITY << 1)) {
 655     return oldp;
 656   } else {
 657     size_t offset = oldp->prev_foot & ~IS_DIRECT_BIT;
 658     size_t oldmmsize = oldsize + offset + DIRECT_FOOT_PAD;
 659     size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
 660     char *cp = (char *)CALL_MREMAP((char *)oldp - offset,
 661                                    oldmmsize, newmmsize, CALL_MREMAP_MV);
 662     if (cp != CMFAIL) {
 663       mchunkptr newp = (mchunkptr)(cp + offset);
 664       size_t psize = newmmsize - offset - DIRECT_FOOT_PAD;
 665       newp->head = psize|CINUSE_BIT;
 666       chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
 667       chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
 668       return newp;
 669     }
 670   }
 671   return NULL;
 672 }
 673
 674 /* -------------------------- mspace management -------------------------- */
 675
 676 /* Initialize top chunk and its size */
 677 static void init_top(mstate m, mchunkptr p, size_t psize)
 678 {
 679   /* Ensure alignment */
 680   size_t offset = align_offset(chunk2mem(p));
 681   p = (mchunkptr)((char *)p + offset);
 682   psize -= offset;
 683
 684   m->top = p;
 685   m->topsize = psize;
 686   p->head = psize | PINUSE_BIT;
 687   /* set size of fake trailing chunk holding overhead space only once */
 688   chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
 689   m->trim_check = DEFAULT_TRIM_THRESHOLD; /* reset on each update */
 690 }
 691
 692 /* Initialize bins for a new mstate that is otherwise zeroed out */
 693 static void init_bins(mstate m)
 694 {
 695   /* Establish circular links for smallbins */
 696   bindex_t i;
 697   for (i = 0; i < NSMALLBINS; i++) {
 698     sbinptr bin = smallbin_at(m,i);
 699     bin->fd = bin->bk = bin;
 700   }
 701 }
 702
 703 /* Allocate chunk and prepend remainder with chunk in successor base. */
 704 static void *prepend_alloc(mstate m, char *newbase, char *oldbase, size_t nb)
 705 {
 706   mchunkptr p = align_as_chunk(newbase);
 707   mchunkptr oldfirst = align_as_chunk(oldbase);
 708   size_t psize = (size_t)((char *)oldfirst - (char *)p);
 709   mchunkptr q = chunk_plus_offset(p, nb);
 710   size_t qsize = psize - nb;
 711   set_size_and_pinuse_of_inuse_chunk(m, p, nb);
 712
 713   /* consolidate remainder with first chunk of old base */
 714   if (oldfirst == m->top) {
 715     size_t tsize = m->topsize += qsize;
 716     m->top = q;
 717     q->head = tsize | PINUSE_BIT;
 718   } else if (oldfirst == m->dv) {
 719     size_t dsize = m->dvsize += qsize;
 720     m->dv = q;
 721     set_size_and_pinuse_of_free_chunk(q, dsize);
 722   } else {
 723     if (!cinuse(oldfirst)) {
 724       size_t nsize = chunksize(oldfirst);
 725       unlink_chunk(m, oldfirst, nsize);
 726       oldfirst = chunk_plus_offset(oldfirst, nsize);
 727       qsize += nsize;
 728     }
 729     set_free_with_pinuse(q, qsize, oldfirst);
 730     insert_chunk(m, q, qsize);
 731   }
 732
 733   return chunk2mem(p);
 734 }
 735
 736 /* Add a segment to hold a new noncontiguous region */
 737 static void add_segment(mstate m, char *tbase, size_t tsize)
 738 {
 739   /* Determine locations and sizes of segment, fenceposts, old top */
 740   char *old_top = (char *)m->top;
 741   msegmentptr oldsp = segment_holding(m, old_top);
 742   char *old_end = oldsp->base + oldsp->size;
 743   size_t ssize = pad_request(sizeof(struct malloc_segment));
 744   char *rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
 745   size_t offset = align_offset(chunk2mem(rawsp));
 746   char *asp = rawsp + offset;
 747   char *csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
 748   mchunkptr sp = (mchunkptr)csp;
 749   msegmentptr ss = (msegmentptr)(chunk2mem(sp));
 750   mchunkptr tnext = chunk_plus_offset(sp, ssize);
 751   mchunkptr p = tnext;
 752
 753   /* reset top to new space */
 754   init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
 755
 756   /* Set up segment record */
 757   set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
 758   *ss = m->seg; /* Push current record */
 759   m->seg.base = tbase;
 760   m->seg.size = tsize;
 761   m->seg.next = ss;
 762
 763   /* Insert trailing fenceposts */
 764   for (;;) {
 765     mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
 766     p->head = FENCEPOST_HEAD;
 767     if ((char *)(&(nextp->head)) < old_end)
 768       p = nextp;
 769     else
 770       break;
 771   }
 772
 773   /* Insert the rest of old top into a bin as an ordinary free chunk */
 774   if (csp != old_top) {
 775     mchunkptr q = (mchunkptr)old_top;
 776     size_t psize = (size_t)(csp - old_top);
 777     mchunkptr tn = chunk_plus_offset(q, psize);
 778     set_free_with_pinuse(q, psize, tn);
 779     insert_chunk(m, q, psize);
 780   }
 781 }
 782
 783 /* -------------------------- System allocation -------------------------- */
 784
 785 static void *alloc_sys(mstate m, size_t nb)
 786 {
 787   char *tbase = CMFAIL;
 788   size_t tsize = 0;
 789
 790   /* Directly map large chunks */
 791   if (LJ_UNLIKELY(nb >= DEFAULT_MMAP_THRESHOLD)) {
 792     void *mem = direct_alloc(nb);
 793     if (mem != 0)
 794       return mem;
 795   }
 796
 797   {
 798     size_t req = nb + TOP_FOOT_SIZE + SIZE_T_ONE;
 799     size_t rsize = granularity_align(req);
 800     if (LJ_LIKELY(rsize > nb)) { /* Fail if wraps around zero */
 801       char *mp = (char *)(CALL_MMAP(rsize));
 802       if (mp != CMFAIL) {
 803         tbase = mp;
 804         tsize = rsize;
 805       }
 806     }
 807   }
 808
 809   if (tbase != CMFAIL) {
 810     msegmentptr sp = &m->seg;
 811     /* Try to merge with an existing segment */
 812     while (sp != 0 && tbase != sp->base + sp->size)
 813       sp = sp->next;
 814     if (sp != 0 && segment_holds(sp, m->top)) { /* append */
 815       sp->size += tsize;
 816       init_top(m, m->top, m->topsize + tsize);
 817     } else {
 818       sp = &m->seg;
 819       while (sp != 0 && sp->base != tbase + tsize)
 820         sp = sp->next;
 821       if (sp != 0) {
 822         char *oldbase = sp->base;
 823         sp->base = tbase;
 824         sp->size += tsize;
 825         return prepend_alloc(m, tbase, oldbase, nb);
 826       } else {
 827         add_segment(m, tbase, tsize);
 828       }
 829     }
 830
 831     if (nb < m->topsize) { /* Allocate from new or extended top space */
 832       size_t rsize = m->topsize -= nb;
 833       mchunkptr p = m->top;
 834       mchunkptr r = m->top = chunk_plus_offset(p, nb);
 835       r->head = rsize | PINUSE_BIT;
 836       set_size_and_pinuse_of_inuse_chunk(m, p, nb);
 837       return chunk2mem(p);
 838     }
 839   }
 840
 841   return NULL;
 842 }
 843
 844 /* -----------------------  system deallocation -------------------------- */
 845
 846 /* Unmap and unlink any mmapped segments that don't contain used chunks */
 847 static size_t release_unused_segments(mstate m)
 848 {
 849   size_t released = 0;
 850   size_t nsegs = 0;
 851   msegmentptr pred = &m->seg;
 852   msegmentptr sp = pred->next;
 853   while (sp != 0) {
 854     char *base = sp->base;
 855     size_t size = sp->size;
 856     msegmentptr next = sp->next;
 857     nsegs++;
 858     {
 859       mchunkptr p = align_as_chunk(base);
 860       size_t psize = chunksize(p);
 861       /* Can unmap if first chunk holds entire segment and not pinned */
 862       if (!cinuse(p) && (char *)p + psize >= base + size - TOP_FOOT_SIZE) {
 863         tchunkptr tp = (tchunkptr)p;
 864         if (p == m->dv) {
 865           m->dv = 0;
 866           m->dvsize = 0;
 867         } else {
 868           unlink_large_chunk(m, tp);
 869         }
 870         if (CALL_MUNMAP(base, size) == 0) {
 871           released += size;
 872           /* unlink obsoleted record */
 873           sp = pred;
 874           sp->next = next;
 875         } else { /* back out if cannot unmap */
 876           insert_large_chunk(m, tp, psize);
 877         }
 878       }
 879     }
 880     pred = sp;
 881     sp = next;
 882   }
 883   /* Reset check counter */
 884   m->release_checks = nsegs > MAX_RELEASE_CHECK_RATE ?
 885                       nsegs : MAX_RELEASE_CHECK_RATE;
 886   return released;
 887 }
 888
 889 static int alloc_trim(mstate m, size_t pad)
 890 {
 891   size_t released = 0;
 892   if (pad < MAX_REQUEST && is_initialized(m)) {
 893     pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
 894
 895     if (m->topsize > pad) {
 896       /* Shrink top space in granularity-size units, keeping at least one */
 897       size_t unit = DEFAULT_GRANULARITY;
 898       size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
 899                       SIZE_T_ONE) * unit;
 900       msegmentptr sp = segment_holding(m, (char *)m->top);
 901
 902       if (sp->size >= extra &&
 903           !has_segment_link(m, sp)) { /* can't shrink if pinned */
 904         size_t newsize = sp->size - extra;
 905         /* Prefer mremap, fall back to munmap */
 906         if ((CALL_MREMAP(sp->base, sp->size, newsize, CALL_MREMAP_NOMOVE) != MFAIL) ||
 907             (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
 908           released = extra;
 909         }
 910       }
 911
 912       if (released != 0) {
 913         sp->size -= released;
 914         init_top(m, m->top, m->topsize - released);
 915       }
 916     }
 917
 918     /* Unmap any unused mmapped segments */
 919     released += release_unused_segments(m);
 920
 921     /* On failure, disable autotrim to avoid repeated failed future calls */
 922     if (released == 0 && m->topsize > m->trim_check)
 923       m->trim_check = MAX_SIZE_T;
 924   }
 925
 926   return (released != 0)? 1 : 0;
 927 }
 928
 929 /* ---------------------------- malloc support --------------------------- */
 930
 931 /* allocate a large request from the best fitting chunk in a treebin */
 932 static void *tmalloc_large(mstate m, size_t nb)
 933 {
 934   tchunkptr v = 0;
 935   size_t rsize = ~nb+1; /* Unsigned negation */
 936   tchunkptr t;
 937   bindex_t idx;
 938   compute_tree_index(nb, idx);
 939
 940   if ((t = *treebin_at(m, idx)) != 0) {
 941     /* Traverse tree for this bin looking for node with size == nb */
 942     size_t sizebits = nb << leftshift_for_tree_index(idx);
 943     tchunkptr rst = 0;  /* The deepest untaken right subtree */
 944     for (;;) {
 945       tchunkptr rt;
 946       size_t trem = chunksize(t) - nb;
 947       if (trem < rsize) {
 948         v = t;
 949         if ((rsize = trem) == 0)
 950           break;
 951       }
 952       rt = t->child[1];
 953       t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
 954       if (rt != 0 && rt != t)
 955         rst = rt;
 956       if (t == 0) {
 957         t = rst; /* set t to least subtree holding sizes > nb */
 958         break;
 959       }
 960       sizebits <<= 1;
 961     }
 962   }
 963
 964   if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
 965     binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
 966     if (leftbits != 0)
 967       t = *treebin_at(m, lj_ffs(leftbits));
 968   }
 969
 970   while (t != 0) { /* find smallest of tree or subtree */
 971     size_t trem = chunksize(t) - nb;
 972     if (trem < rsize) {
 973       rsize = trem;
 974       v = t;
 975     }
 976     t = leftmost_child(t);
 977   }
 978
 979   /*  If dv is a better fit, return NULL so malloc will use it */
 980   if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
 981     mchunkptr r = chunk_plus_offset(v, nb);
 982     unlink_large_chunk(m, v);
 983     if (rsize < MIN_CHUNK_SIZE) {
 984       set_inuse_and_pinuse(m, v, (rsize + nb));
 985     } else {
 986       set_size_and_pinuse_of_inuse_chunk(m, v, nb);
 987       set_size_and_pinuse_of_free_chunk(r, rsize);
 988       insert_chunk(m, r, rsize);
 989     }
 990     return chunk2mem(v);
 991   }
 992   return NULL;
 993 }
 994
 995 /* allocate a small request from the best fitting chunk in a treebin */
 996 static void *tmalloc_small(mstate m, size_t nb)
 997 {
 998   tchunkptr t, v;
 999   mchunkptr r;
1000   size_t rsize;
1001   bindex_t i = lj_ffs(m->treemap);
1002
1003   v = t = *treebin_at(m, i);
1004   rsize = chunksize(t) - nb;
1005
1006   while ((t = leftmost_child(t)) != 0) {
1007     size_t trem = chunksize(t) - nb;
1008     if (trem < rsize) {
1009       rsize = trem;
1010       v = t;
1011     }
1012   }
1013
1014   r = chunk_plus_offset(v, nb);
1015   unlink_large_chunk(m, v);
1016   if (rsize < MIN_CHUNK_SIZE) {
1017     set_inuse_and_pinuse(m, v, (rsize + nb));
1018   } else {
1019     set_size_and_pinuse_of_inuse_chunk(m, v, nb);
1020     set_size_and_pinuse_of_free_chunk(r, rsize);
1021     replace_dv(m, r, rsize);
1022   }
1023   return chunk2mem(v);
1024 }
1025
1026 /* ----------------------------------------------------------------------- */
1027
1028 void *lj_alloc_create(void)
1029 {
1030   size_t tsize = DEFAULT_GRANULARITY;
1031   char *tbase;
1032   INIT_MMAP();
1033   tbase = (char *)(CALL_MMAP(tsize));
1034   if (tbase != CMFAIL) {
1035     size_t msize = pad_request(sizeof(struct malloc_state));
1036     mchunkptr mn;
1037     mchunkptr msp = align_as_chunk(tbase);
1038     mstate m = (mstate)(chunk2mem(msp));
1039     memset(m, 0, msize);
1040     msp->head = (msize|PINUSE_BIT|CINUSE_BIT);
1041     m->seg.base = tbase;
1042     m->seg.size = tsize;
1043     m->release_checks = MAX_RELEASE_CHECK_RATE;
1044     init_bins(m);
1045     mn = next_chunk(mem2chunk(m));
1046     init_top(m, mn, (size_t)((tbase + tsize) - (char *)mn) - TOP_FOOT_SIZE);
1047     return m;
1048   }
1049   return NULL;
1050 }
1051
1052 void lj_alloc_destroy(void *msp)
1053 {
1054   mstate ms = (mstate)msp;
1055   msegmentptr sp = &ms->seg;
1056   while (sp != 0) {
1057     char *base = sp->base;
1058     size_t size = sp->size;
1059     sp = sp->next;
1060     CALL_MUNMAP(base, size);
1061   }
1062 }
1063
1064 static LJ_NOINLINE void *lj_alloc_malloc(void *msp, size_t nsize)
1065 {
1066   mstate ms = (mstate)msp;
1067   void *mem;
1068   size_t nb;
1069   if (nsize <= MAX_SMALL_REQUEST) {
1070     bindex_t idx;
1071     binmap_t smallbits;
1072     nb = (nsize < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(nsize);
1073     idx = small_index(nb);
1074     smallbits = ms->smallmap >> idx;
1075
1076     if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
1077       mchunkptr b, p;
1078       idx += ~smallbits & 1;       /* Uses next bin if idx empty */
1079       b = smallbin_at(ms, idx);
1080       p = b->fd;
1081       unlink_first_small_chunk(ms, b, p, idx);
1082       set_inuse_and_pinuse(ms, p, small_index2size(idx));
1083       mem = chunk2mem(p);
1084       return mem;
1085     } else if (nb > ms->dvsize) {
1086       if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
1087         mchunkptr b, p, r;
1088         size_t rsize;
1089         binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
1090         bindex_t i = lj_ffs(leftbits);
1091         b = smallbin_at(ms, i);
1092         p = b->fd;
1093         unlink_first_small_chunk(ms, b, p, i);
1094         rsize = small_index2size(i) - nb;
1095         /* Fit here cannot be remainderless if 4byte sizes */
1096         if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE) {
1097           set_inuse_and_pinuse(ms, p, small_index2size(i));
1098         } else {
1099           set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
1100           r = chunk_plus_offset(p, nb);
1101           set_size_and_pinuse_of_free_chunk(r, rsize);
1102           replace_dv(ms, r, rsize);
1103         }
1104         mem = chunk2mem(p);
1105         return mem;
1106       } else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
1107         return mem;
1108       }
1109     }
1110   } else if (nsize >= MAX_REQUEST) {
1111     nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
1112   } else {
1113     nb = pad_request(nsize);
1114     if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
1115       return mem;
1116     }
1117   }
1118
1119   if (nb <= ms->dvsize) {
1120     size_t rsize = ms->dvsize - nb;
1121     mchunkptr p = ms->dv;
1122     if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
1123       mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
1124       ms->dvsize = rsize;
1125       set_size_and_pinuse_of_free_chunk(r, rsize);
1126       set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
1127     } else { /* exhaust dv */
1128       size_t dvs = ms->dvsize;
1129       ms->dvsize = 0;
1130       ms->dv = 0;
1131       set_inuse_and_pinuse(ms, p, dvs);
1132     }
1133     mem = chunk2mem(p);
1134     return mem;
1135   } else if (nb < ms->topsize) { /* Split top */
1136     size_t rsize = ms->topsize -= nb;
1137     mchunkptr p = ms->top;
1138     mchunkptr r = ms->top = chunk_plus_offset(p, nb);
1139     r->head = rsize | PINUSE_BIT;
1140     set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
1141     mem = chunk2mem(p);
1142     return mem;
1143   }
1144   return alloc_sys(ms, nb);
1145 }
1146
1147 static LJ_NOINLINE void *lj_alloc_free(void *msp, void *ptr)
1148 {
1149   if (ptr != 0) {
1150     mchunkptr p = mem2chunk(ptr);
1151     mstate fm = (mstate)msp;
1152     size_t psize = chunksize(p);
1153     mchunkptr next = chunk_plus_offset(p, psize);
1154     if (!pinuse(p)) {
1155       size_t prevsize = p->prev_foot;
1156       if ((prevsize & IS_DIRECT_BIT) != 0) {
1157         prevsize &= ~IS_DIRECT_BIT;
1158         psize += prevsize + DIRECT_FOOT_PAD;
1159         CALL_MUNMAP((char *)p - prevsize, psize);
1160         return NULL;
1161       } else {
1162         mchunkptr prev = chunk_minus_offset(p, prevsize);
1163         psize += prevsize;
1164         p = prev;
1165         /* consolidate backward */
1166         if (p != fm->dv) {
1167           unlink_chunk(fm, p, prevsize);
1168         } else if ((next->head & INUSE_BITS) == INUSE_BITS) {
1169           fm->dvsize = psize;
1170           set_free_with_pinuse(p, psize, next);
1171           return NULL;
1172         }
1173       }
1174     }
1175     if (!cinuse(next)) {  /* consolidate forward */
1176       if (next == fm->top) {
1177         size_t tsize = fm->topsize += psize;
1178         fm->top = p;
1179         p->head = tsize | PINUSE_BIT;
1180         if (p == fm->dv) {
1181           fm->dv = 0;
1182           fm->dvsize = 0;
1183         }
1184         if (tsize > fm->trim_check)
1185           alloc_trim(fm, 0);
1186         return NULL;
1187       } else if (next == fm->dv) {
1188         size_t dsize = fm->dvsize += psize;
1189         fm->dv = p;
1190         set_size_and_pinuse_of_free_chunk(p, dsize);
1191         return NULL;
1192       } else {
1193         size_t nsize = chunksize(next);
1194         psize += nsize;
1195         unlink_chunk(fm, next, nsize);
1196         set_size_and_pinuse_of_free_chunk(p, psize);
1197         if (p == fm->dv) {
1198           fm->dvsize = psize;
1199           return NULL;
1200         }
1201       }
1202     } else {
1203       set_free_with_pinuse(p, psize, next);
1204     }
1205
1206     if (is_small(psize)) {
1207       insert_small_chunk(fm, p, psize);
1208     } else {
1209       tchunkptr tp = (tchunkptr)p;
1210       insert_large_chunk(fm, tp, psize);
1211       if (--fm->release_checks == 0)
1212         release_unused_segments(fm);
1213     }
1214   }
1215   return NULL;
1216 }
1217
1218 static LJ_NOINLINE void *lj_alloc_realloc(void *msp, void *ptr, size_t nsize)
1219 {
1220   if (nsize >= MAX_REQUEST) {
1221     return NULL;
1222   } else {
1223     mstate m = (mstate)msp;
1224     mchunkptr oldp = mem2chunk(ptr);
1225     size_t oldsize = chunksize(oldp);
1226     mchunkptr next = chunk_plus_offset(oldp, oldsize);
1227     mchunkptr newp = 0;
1228     size_t nb = request2size(nsize);
1229
1230     /* Try to either shrink or extend into top. Else malloc-copy-free */
1231     if (is_direct(oldp)) {
1232       newp = direct_resize(oldp, nb);  /* this may return NULL. */
1233     } else if (oldsize >= nb) { /* already big enough */
1234       size_t rsize = oldsize - nb;
1235       newp = oldp;
1236       if (rsize >= MIN_CHUNK_SIZE) {
1237         mchunkptr rem = chunk_plus_offset(newp, nb);
1238         set_inuse(m, newp, nb);
1239         set_inuse(m, rem, rsize);
1240         lj_alloc_free(m, chunk2mem(rem));
1241       }
1242     } else if (next == m->top && oldsize + m->topsize > nb) {
1243       /* Expand into top */
1244       size_t newsize = oldsize + m->topsize;
1245       size_t newtopsize = newsize - nb;
1246       mchunkptr newtop = chunk_plus_offset(oldp, nb);
1247       set_inuse(m, oldp, nb);
1248       newtop->head = newtopsize |PINUSE_BIT;
1249       m->top = newtop;
1250       m->topsize = newtopsize;
1251       newp = oldp;
1252     }
1253
1254     if (newp != 0) {
1255       return chunk2mem(newp);
1256     } else {
1257       void *newmem = lj_alloc_malloc(m, nsize);
1258       if (newmem != 0) {
1259         size_t oc = oldsize - overhead_for(oldp);
1260         memcpy(newmem, ptr, oc < nsize ? oc : nsize);
1261         lj_alloc_free(m, ptr);
1262       }
1263       return newmem;
1264     }
1265   }
1266 }
1267
1268 void *lj_alloc_f(void *msp, void *ptr, size_t osize, size_t nsize)
1269 {
1270   (void)osize;
1271   if (nsize == 0) {
1272     return lj_alloc_free(msp, ptr);
1273   } else if (ptr == NULL) {
1274     return lj_alloc_malloc(msp, nsize);
1275   } else {
1276     return lj_alloc_realloc(msp, ptr, nsize);
1277   }
1278 }
1279
1280 #endif