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