luna - luajit/src/lj

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