2 This is a version (aka dlmalloc) of malloc/free/realloc written by
3 Doug Lea and released to the public domain, as explained at
4 http://creativecommons.org/publicdomain/zero/1.0/ Send questions,
5 comments, complaints, performance data, etc to dl@cs.oswego.edu
8 #include <vppinfra/dlmalloc.h>
9 #include <vppinfra/sanitizer.h>
11 /*------------------------------ internal #includes ---------------------- */
14 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
17 #include <stdio.h> /* for printing in malloc_stats */
18 #endif /* NO_MALLOC_STATS */
20 #include <errno.h> /* for MALLOC_FAILURE_ACTION */
21 #endif /* LACKS_ERRNO_H */
23 #if DLM_ABORT_ON_ASSERT_FAILURE
25 #define assert(x) if(!(x)) DLM_ABORT
26 #else /* DLM_ABORT_ON_ASSERT_FAILURE */
28 #endif /* DLM_ABORT_ON_ASSERT_FAILURE */
35 #if !defined(WIN32) && !defined(LACKS_TIME_H)
36 #include <time.h> /* for magic initialization */
38 #ifndef LACKS_STDLIB_H
39 #include <stdlib.h> /* for abort() */
40 #endif /* LACKS_STDLIB_H */
41 #ifndef LACKS_STRING_H
42 #include <string.h> /* for memset etc */
43 #endif /* LACKS_STRING_H */
45 #ifndef LACKS_STRINGS_H
46 #include <strings.h> /* for ffs */
47 #endif /* LACKS_STRINGS_H */
48 #endif /* USE_BUILTIN_FFS */
50 #ifndef LACKS_SYS_MMAN_H
51 /* On some versions of linux, mremap decl in mman.h needs __USE_GNU set */
52 #if (defined(linux) && !defined(__USE_GNU))
54 #include <sys/mman.h> /* for mmap */
57 #include <sys/mman.h> /* for mmap */
59 #endif /* LACKS_SYS_MMAN_H */
62 #endif /* LACKS_FCNTL_H */
63 #endif /* HAVE_MMAP */
64 #ifndef LACKS_UNISTD_H
65 #include <unistd.h> /* for sbrk, sysconf */
66 #else /* LACKS_UNISTD_H */
67 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
68 extern void* sbrk(ptrdiff_t);
69 #endif /* FreeBSD etc */
70 #endif /* LACKS_UNISTD_H */
72 /* Declarations for locking */
75 #if defined (__SVR4) && defined (__sun) /* solaris */
77 #elif !defined(LACKS_SCHED_H)
79 #endif /* solaris or LACKS_SCHED_H */
80 #if (defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0) || !USE_SPIN_LOCKS
82 #endif /* USE_RECURSIVE_LOCKS ... */
83 #elif defined(_MSC_VER)
85 /* These are already defined on AMD64 builds */
88 #endif /* __cplusplus */
89 LONG __cdecl _InterlockedCompareExchange(LONG volatile *Dest, LONG Exchange, LONG Comp);
90 LONG __cdecl _InterlockedExchange(LONG volatile *Target, LONG Value);
93 #endif /* __cplusplus */
95 #pragma intrinsic (_InterlockedCompareExchange)
96 #pragma intrinsic (_InterlockedExchange)
97 #define interlockedcompareexchange _InterlockedCompareExchange
98 #define interlockedexchange _InterlockedExchange
99 #elif defined(WIN32) && defined(__GNUC__)
100 #define interlockedcompareexchange(a, b, c) __sync_val_compare_and_swap(a, c, b)
101 #define interlockedexchange __sync_lock_test_and_set
103 #else /* USE_LOCKS */
104 #endif /* USE_LOCKS */
107 #define LOCK_AT_FORK 0
110 /* Declarations for bit scanning on win32 */
111 #if defined(_MSC_VER) && _MSC_VER>=1300
112 #ifndef BitScanForward /* Try to avoid pulling in WinNT.h */
115 #endif /* __cplusplus */
116 unsigned char _BitScanForward(unsigned long *index, unsigned long mask);
117 unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
120 #endif /* __cplusplus */
122 #define BitScanForward _BitScanForward
123 #define BitScanReverse _BitScanReverse
124 #pragma intrinsic(_BitScanForward)
125 #pragma intrinsic(_BitScanReverse)
126 #endif /* BitScanForward */
127 #endif /* defined(_MSC_VER) && _MSC_VER>=1300 */
130 #ifndef malloc_getpagesize
131 # ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
132 # ifndef _SC_PAGE_SIZE
133 # define _SC_PAGE_SIZE _SC_PAGESIZE
136 # ifdef _SC_PAGE_SIZE
137 # define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
139 # if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
140 extern size_t getpagesize();
141 # define malloc_getpagesize getpagesize()
143 # ifdef WIN32 /* use supplied emulation of getpagesize */
144 # define malloc_getpagesize getpagesize()
146 # ifndef LACKS_SYS_PARAM_H
147 # include <sys/param.h>
149 # ifdef EXEC_PAGESIZE
150 # define malloc_getpagesize EXEC_PAGESIZE
154 # define malloc_getpagesize NBPG
156 # define malloc_getpagesize (NBPG * CLSIZE)
160 # define malloc_getpagesize NBPC
163 # define malloc_getpagesize PAGESIZE
164 # else /* just guess */
165 # define malloc_getpagesize ((size_t)4096U)
176 /* ------------------- size_t and alignment properties -------------------- */
178 /* The byte and bit size of a size_t */
179 #define SIZE_T_SIZE (sizeof(size_t))
180 #define SIZE_T_BITSIZE (sizeof(size_t) << 3)
182 /* Some constants coerced to size_t */
183 /* Annoying but necessary to avoid errors on some platforms */
184 #define SIZE_T_ZERO ((size_t)0)
185 #define SIZE_T_ONE ((size_t)1)
186 #define SIZE_T_TWO ((size_t)2)
187 #define SIZE_T_FOUR ((size_t)4)
188 #define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)
189 #define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)
190 #define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
191 #define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
193 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
194 #define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)
196 /* True if address a has acceptable alignment */
197 #define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
199 /* the number of bytes to offset an address to align it */
200 #define align_offset(A)\
201 ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
202 ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
204 /* -------------------------- MMAP preliminaries ------------------------- */
207 If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
208 checks to fail so compiler optimizer can delete code rather than
209 using so many "#if"s.
213 /* MORECORE and MMAP must return MFAIL on failure */
214 #define MFAIL ((void*)(MAX_SIZE_T))
215 #define CMFAIL ((char*)(MFAIL)) /* defined for convenience */
220 #define MUNMAP_DEFAULT(a, s) munmap((a), (s))
221 #define MMAP_PROT (PROT_READ|PROT_WRITE)
222 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
223 #define MAP_ANONYMOUS MAP_ANON
224 #endif /* MAP_ANON */
226 #define MMAP_FLAGS (MAP_PRIVATE|MAP_ANONYMOUS)
227 #define MMAP_DEFAULT(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
228 #else /* MAP_ANONYMOUS */
230 Nearly all versions of mmap support MAP_ANONYMOUS, so the following
231 is unlikely to be needed, but is supplied just in case.
233 #define MMAP_FLAGS (MAP_PRIVATE)
234 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
235 #define MMAP_DEFAULT(s) ((dev_zero_fd < 0) ? \
236 (dev_zero_fd = open("/dev/zero", O_RDWR), \
237 mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
238 mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
239 #endif /* MAP_ANONYMOUS */
241 #define DIRECT_MMAP_DEFAULT(s) MMAP_DEFAULT(s)
245 /* Win32 MMAP via VirtualAlloc */
246 static FORCEINLINE void* win32mmap(size_t size) {
247 void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
248 return (ptr != 0)? ptr: MFAIL;
251 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
252 static FORCEINLINE void* win32direct_mmap(size_t size) {
253 void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
255 return (ptr != 0)? ptr: MFAIL;
258 /* This function supports releasing coalesed segments */
259 static FORCEINLINE int win32munmap(void* ptr, size_t size) {
260 MEMORY_BASIC_INFORMATION minfo;
261 char* cptr = (char*)ptr;
263 if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
265 if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
266 minfo.State != MEM_COMMIT || minfo.RegionSize > size)
268 if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
270 cptr += minfo.RegionSize;
271 size -= minfo.RegionSize;
276 #define MMAP_DEFAULT(s) win32mmap(s)
277 #define MUNMAP_DEFAULT(a, s) win32munmap((a), (s))
278 #define DIRECT_MMAP_DEFAULT(s) win32direct_mmap(s)
280 #endif /* HAVE_MMAP */
284 #define MREMAP_DEFAULT(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
286 #endif /* HAVE_MREMAP */
289 * Define CALL_MORECORE
293 #define CALL_MORECORE(S) MORECORE(S)
295 #define CALL_MORECORE(S) MORECORE_DEFAULT(S)
296 #endif /* MORECORE */
297 #else /* HAVE_MORECORE */
298 #define CALL_MORECORE(S) MFAIL
299 #endif /* HAVE_MORECORE */
302 * Define CALL_MMAP/CALL_MUNMAP/CALL_DIRECT_MMAP
305 #define USE_MMAP_BIT (SIZE_T_ONE)
308 #define CALL_MMAP(s) MMAP(s)
310 #define CALL_MMAP(s) MMAP_DEFAULT(s)
313 #define CALL_MUNMAP(a, s) MUNMAP((a), (s))
315 #define CALL_MUNMAP(a, s) MUNMAP_DEFAULT((a), (s))
318 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
319 #else /* DIRECT_MMAP */
320 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP_DEFAULT(s)
321 #endif /* DIRECT_MMAP */
322 #else /* HAVE_MMAP */
323 #define USE_MMAP_BIT (SIZE_T_ZERO)
325 #define MMAP(s) MFAIL
326 #define MUNMAP(a, s) (-1)
327 #define DIRECT_MMAP(s) MFAIL
328 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
329 #define CALL_MMAP(s) MMAP(s)
330 #define CALL_MUNMAP(a, s) MUNMAP((a), (s))
331 #endif /* HAVE_MMAP */
336 #if HAVE_MMAP && HAVE_MREMAP
338 #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP((addr), (osz), (nsz), (mv))
340 #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP_DEFAULT((addr), (osz), (nsz), (mv))
342 #else /* HAVE_MMAP && HAVE_MREMAP */
343 #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
344 #endif /* HAVE_MMAP && HAVE_MREMAP */
346 /* mstate bit set if contiguous morecore disabled or failed */
347 #define USE_NONCONTIGUOUS_BIT (4U)
349 /* mstate bit set if no expansion allowed */
350 #define USE_NOEXPAND_BIT (8U)
352 /* trace allocations if set */
353 #define USE_TRACE_BIT (16U)
355 /* segment bit set in create_mspace_with_base */
356 #define EXTERN_BIT (8U)
359 /* --------------------------- Lock preliminaries ------------------------ */
362 When locks are defined, there is one global lock, plus
365 The global lock_ensures that mparams.magic and other unique
366 mparams values are initialized only once. It also protects
367 sequences of calls to MORECORE. In many cases sys_alloc requires
368 two calls, that should not be interleaved with calls by other
369 threads. This does not protect against direct calls to MORECORE
370 by other threads not using this lock, so there is still code to
371 cope the best we can on interference.
373 Per-mspace locks surround calls to malloc, free, etc.
374 By default, locks are simple non-reentrant mutexes.
376 Because lock-protected regions generally have bounded times, it is
377 OK to use the supplied simple spinlocks. Spinlocks are likely to
378 improve performance for lightly contended applications, but worsen
379 performance under heavy contention.
381 If USE_LOCKS is > 1, the definitions of lock routines here are
382 bypassed, in which case you will need to define the type MLOCK_T,
383 and at least INITIAL_LOCK, DESTROY_LOCK, ACQUIRE_LOCK, RELEASE_LOCK
384 and TRY_LOCK. You must also declare a
385 static MLOCK_T malloc_global_mutex = { initialization values };.
390 #define USE_LOCK_BIT (0U)
391 #define INITIAL_LOCK(l) (0)
392 #define DESTROY_LOCK(l) (0)
393 #define ACQUIRE_MALLOC_GLOBAL_LOCK()
394 #define RELEASE_MALLOC_GLOBAL_LOCK()
398 /* ----------------------- User-defined locks ------------------------ */
399 /* Define your own lock implementation here */
400 /* #define INITIAL_LOCK(lk) ... */
401 /* #define DESTROY_LOCK(lk) ... */
402 /* #define ACQUIRE_LOCK(lk) ... */
403 /* #define RELEASE_LOCK(lk) ... */
404 /* #define TRY_LOCK(lk) ... */
405 /* static MLOCK_T malloc_global_mutex = ... */
409 /* First, define CAS_LOCK and CLEAR_LOCK on ints */
410 /* Note CAS_LOCK defined to return 0 on success */
412 #if defined(__GNUC__)&& (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1))
413 #define CAS_LOCK(sl) __sync_lock_test_and_set(sl, 1)
414 #define CLEAR_LOCK(sl) __sync_lock_release(sl)
416 #elif (defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)))
417 /* Custom spin locks for older gcc on x86 */
418 static FORCEINLINE int x86_cas_lock(int *sl) {
422 __asm__ __volatile__ ("lock; cmpxchgl %1, %2"
424 : "r" (val), "m" (*(sl)), "0"(cmp)
429 static FORCEINLINE void x86_clear_lock(int* sl) {
433 __asm__ __volatile__ ("lock; xchgl %0, %1"
435 : "m" (*(sl)), "0"(prev)
439 #define CAS_LOCK(sl) x86_cas_lock(sl)
440 #define CLEAR_LOCK(sl) x86_clear_lock(sl)
442 #else /* Win32 MSC */
443 #define CAS_LOCK(sl) interlockedexchange(sl, (LONG)1)
444 #define CLEAR_LOCK(sl) interlockedexchange (sl, (LONG)0)
446 #endif /* ... gcc spins locks ... */
448 /* How to yield for a spin lock */
449 #define SPINS_PER_YIELD 63
450 #if defined(_MSC_VER)
451 #define SLEEP_EX_DURATION 50 /* delay for yield/sleep */
452 #define SPIN_LOCK_YIELD SleepEx(SLEEP_EX_DURATION, FALSE)
453 #elif defined (__SVR4) && defined (__sun) /* solaris */
454 #define SPIN_LOCK_YIELD thr_yield();
455 #elif !defined(LACKS_SCHED_H)
456 #define SPIN_LOCK_YIELD sched_yield();
458 #define SPIN_LOCK_YIELD
459 #endif /* ... yield ... */
461 #if !defined(USE_RECURSIVE_LOCKS) || USE_RECURSIVE_LOCKS == 0
462 /* Plain spin locks use single word (embedded in malloc_states) */
464 static int spin_acquire_lock(int *sl) {
466 while (*(volatile int *)sl != 0 || CAS_LOCK(sl)) {
467 if ((++spins & SPINS_PER_YIELD) == 0) {
475 #define TRY_LOCK(sl) !CAS_LOCK(sl)
476 #define RELEASE_LOCK(sl) CLEAR_LOCK(sl)
477 #define ACQUIRE_LOCK(sl) (CAS_LOCK(sl)? spin_acquire_lock(sl) : 0)
478 #define INITIAL_LOCK(sl) (*sl = 0)
479 #define DESTROY_LOCK(sl) (0)
480 static MLOCK_T malloc_global_mutex = 0;
482 #else /* USE_RECURSIVE_LOCKS */
483 /* types for lock owners */
485 #define THREAD_ID_T DWORD
486 #define CURRENT_THREAD GetCurrentThreadId()
487 #define EQ_OWNER(X,Y) ((X) == (Y))
490 Note: the following assume that pthread_t is a type that can be
491 initialized to (casted) zero. If this is not the case, you will need to
492 somehow redefine these or not use spin locks.
494 #define THREAD_ID_T pthread_t
495 #define CURRENT_THREAD pthread_self()
496 #define EQ_OWNER(X,Y) pthread_equal(X, Y)
499 struct malloc_recursive_lock {
502 THREAD_ID_T threadid;
505 #define MLOCK_T struct malloc_recursive_lock
506 static MLOCK_T malloc_global_mutex = { 0, 0, (THREAD_ID_T)0};
508 static FORCEINLINE void recursive_release_lock(MLOCK_T *lk) {
515 static FORCEINLINE int recursive_acquire_lock(MLOCK_T *lk) {
516 THREAD_ID_T mythreadid = CURRENT_THREAD;
519 if (*((volatile int *)(&lk->sl)) == 0) {
520 if (!CAS_LOCK(&lk->sl)) {
521 lk->threadid = mythreadid;
526 else if (EQ_OWNER(lk->threadid, mythreadid)) {
530 if ((++spins & SPINS_PER_YIELD) == 0) {
536 static FORCEINLINE int recursive_try_lock(MLOCK_T *lk) {
537 THREAD_ID_T mythreadid = CURRENT_THREAD;
538 if (*((volatile int *)(&lk->sl)) == 0) {
539 if (!CAS_LOCK(&lk->sl)) {
540 lk->threadid = mythreadid;
545 else if (EQ_OWNER(lk->threadid, mythreadid)) {
552 #define RELEASE_LOCK(lk) recursive_release_lock(lk)
553 #define TRY_LOCK(lk) recursive_try_lock(lk)
554 #define ACQUIRE_LOCK(lk) recursive_acquire_lock(lk)
555 #define INITIAL_LOCK(lk) ((lk)->threadid = (THREAD_ID_T)0, (lk)->sl = 0, (lk)->c = 0)
556 #define DESTROY_LOCK(lk) (0)
557 #endif /* USE_RECURSIVE_LOCKS */
559 #elif defined(WIN32) /* Win32 critical sections */
560 #define MLOCK_T CRITICAL_SECTION
561 #define ACQUIRE_LOCK(lk) (EnterCriticalSection(lk), 0)
562 #define RELEASE_LOCK(lk) LeaveCriticalSection(lk)
563 #define TRY_LOCK(lk) TryEnterCriticalSection(lk)
564 #define INITIAL_LOCK(lk) (!InitializeCriticalSectionAndSpinCount((lk), 0x80000000|4000))
565 #define DESTROY_LOCK(lk) (DeleteCriticalSection(lk), 0)
566 #define NEED_GLOBAL_LOCK_INIT
568 static MLOCK_T malloc_global_mutex;
569 static volatile LONG malloc_global_mutex_status;
571 /* Use spin loop to initialize global lock */
572 static void init_malloc_global_mutex() {
574 long stat = malloc_global_mutex_status;
577 /* transition to < 0 while initializing, then to > 0) */
579 interlockedcompareexchange(&malloc_global_mutex_status, (LONG)-1, (LONG)0) == 0) {
580 InitializeCriticalSection(&malloc_global_mutex);
581 interlockedexchange(&malloc_global_mutex_status, (LONG)1);
588 #else /* pthreads-based locks */
589 #define MLOCK_T pthread_mutex_t
590 #define ACQUIRE_LOCK(lk) pthread_mutex_lock(lk)
591 #define RELEASE_LOCK(lk) pthread_mutex_unlock(lk)
592 #define TRY_LOCK(lk) (!pthread_mutex_trylock(lk))
593 #define INITIAL_LOCK(lk) pthread_init_lock(lk)
594 #define DESTROY_LOCK(lk) pthread_mutex_destroy(lk)
596 #if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0 && defined(linux) && !defined(PTHREAD_MUTEX_RECURSIVE)
597 /* Cope with old-style linux recursive lock initialization by adding */
598 /* skipped internal declaration from pthread.h */
599 extern int pthread_mutexattr_setkind_np __P ((pthread_mutexattr_t *__attr,
601 #define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP
602 #define pthread_mutexattr_settype(x,y) pthread_mutexattr_setkind_np(x,y)
603 #endif /* USE_RECURSIVE_LOCKS ... */
605 static MLOCK_T malloc_global_mutex = PTHREAD_MUTEX_INITIALIZER;
607 static int pthread_init_lock (MLOCK_T *lk) {
608 pthread_mutexattr_t attr;
609 if (pthread_mutexattr_init(&attr)) return 1;
610 #if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0
611 if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1;
613 if (pthread_mutex_init(lk, &attr)) return 1;
614 if (pthread_mutexattr_destroy(&attr)) return 1;
618 #endif /* ... lock types ... */
620 /* Common code for all lock types */
621 #define USE_LOCK_BIT (2U)
623 #ifndef ACQUIRE_MALLOC_GLOBAL_LOCK
624 #define ACQUIRE_MALLOC_GLOBAL_LOCK() ACQUIRE_LOCK(&malloc_global_mutex);
627 #ifndef RELEASE_MALLOC_GLOBAL_LOCK
628 #define RELEASE_MALLOC_GLOBAL_LOCK() RELEASE_LOCK(&malloc_global_mutex);
631 #endif /* USE_LOCKS */
633 /* ----------------------- Chunk representations ------------------------ */
636 (The following includes lightly edited explanations by Colin Plumb.)
638 The malloc_chunk declaration below is misleading (but accurate and
639 necessary). It declares a "view" into memory allowing access to
640 necessary fields at known offsets from a given base.
642 Chunks of memory are maintained using a `boundary tag' method as
643 originally described by Knuth. (See the paper by Paul Wilson
644 ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
645 techniques.) Sizes of free chunks are stored both in the front of
646 each chunk and at the end. This makes consolidating fragmented
647 chunks into bigger chunks fast. The head fields also hold bits
648 representing whether chunks are free or in use.
650 Here are some pictures to make it clearer. They are "exploded" to
651 show that the state of a chunk can be thought of as extending from
652 the high 31 bits of the head field of its header through the
653 prev_foot and PINUSE_BIT bit of the following chunk header.
655 A chunk that's in use looks like:
657 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
658 | Size of previous chunk (if P = 0) |
659 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
660 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
661 | Size of this chunk 1| +-+
662 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
668 +- size - sizeof(size_t) available payload bytes -+
672 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
673 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
674 | Size of next chunk (may or may not be in use) | +-+
675 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
677 And if it's free, it looks like this:
680 | User payload (must be in use, or we would have merged!) |
681 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
682 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
683 | Size of this chunk 0| +-+
684 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
686 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
688 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
690 +- size - sizeof(struct chunk) unused bytes -+
692 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
693 | Size of this chunk |
694 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
695 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
696 | Size of next chunk (must be in use, or we would have merged)| +-+
697 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
701 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
704 Note that since we always merge adjacent free chunks, the chunks
705 adjacent to a free chunk must be in use.
707 Given a pointer to a chunk (which can be derived trivially from the
708 payload pointer) we can, in O(1) time, find out whether the adjacent
709 chunks are free, and if so, unlink them from the lists that they
710 are on and merge them with the current chunk.
712 Chunks always begin on even word boundaries, so the mem portion
713 (which is returned to the user) is also on an even word boundary, and
714 thus at least double-word aligned.
716 The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
717 chunk size (which is always a multiple of two words), is an in-use
718 bit for the *previous* chunk. If that bit is *clear*, then the
719 word before the current chunk size contains the previous chunk
720 size, and can be used to find the front of the previous chunk.
721 The very first chunk allocated always has this bit set, preventing
722 access to non-existent (or non-owned) memory. If pinuse is set for
723 any given chunk, then you CANNOT determine the size of the
724 previous chunk, and might even get a memory addressing fault when
727 The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
728 the chunk size redundantly records whether the current chunk is
729 inuse (unless the chunk is mmapped). This redundancy enables usage
730 checks within free and realloc, and reduces indirection when freeing
731 and consolidating chunks.
733 Each freshly allocated chunk must have both cinuse and pinuse set.
734 That is, each allocated chunk borders either a previously allocated
735 and still in-use chunk, or the base of its memory arena. This is
736 ensured by making all allocations from the `lowest' part of any
737 found chunk. Further, no free chunk physically borders another one,
738 so each free chunk is known to be preceded and followed by either
739 inuse chunks or the ends of memory.
741 Note that the `foot' of the current chunk is actually represented
742 as the prev_foot of the NEXT chunk. This makes it easier to
743 deal with alignments etc but can be very confusing when trying
744 to extend or adapt this code.
746 The exceptions to all this are
748 1. The special chunk `top' is the top-most available chunk (i.e.,
749 the one bordering the end of available memory). It is treated
750 specially. Top is never included in any bin, is used only if
751 no other chunk is available, and is released back to the
752 system if it is very large (see M_TRIM_THRESHOLD). In effect,
753 the top chunk is treated as larger (and thus less well
754 fitting) than any other available chunk. The top chunk
755 doesn't update its trailing size field since there is no next
756 contiguous chunk that would have to index off it. However,
757 space is still allocated for it (TOP_FOOT_SIZE) to enable
758 separation or merging when space is extended.
760 3. Chunks allocated via mmap, have both cinuse and pinuse bits
761 cleared in their head fields. Because they are allocated
762 one-by-one, each must carry its own prev_foot field, which is
763 also used to hold the offset this chunk has within its mmapped
764 region, which is needed to preserve alignment. Each mmapped
765 chunk is trailed by the first two fields of a fake next-chunk
766 for sake of usage checks.
770 struct malloc_chunk {
771 size_t prev_foot; /* Size of previous chunk (if free). */
772 size_t head; /* Size and inuse bits. */
773 struct malloc_chunk* fd; /* double links -- used only if free. */
774 struct malloc_chunk* bk;
777 typedef struct malloc_chunk mchunk;
778 typedef struct malloc_chunk* mchunkptr;
779 typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */
780 typedef unsigned int bindex_t; /* Described below */
781 typedef unsigned int binmap_t; /* Described below */
782 typedef unsigned int flag_t; /* The type of various bit flag sets */
784 /* ------------------- Chunks sizes and alignments ----------------------- */
786 #define MCHUNK_SIZE (sizeof(mchunk))
789 #define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
791 #define CHUNK_OVERHEAD (SIZE_T_SIZE)
794 /* MMapped chunks need a second word of overhead ... */
795 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
796 /* ... and additional padding for fake next-chunk at foot */
797 #define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES)
799 /* The smallest size we can malloc is an aligned minimal chunk */
800 #define MIN_CHUNK_SIZE\
801 ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
803 /* conversion from malloc headers to user pointers, and back */
804 #define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))
805 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
806 /* chunk associated with aligned address A */
807 #define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))
809 /* Bounds on request (not chunk) sizes. */
810 #define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)
811 #define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
813 /* pad request bytes into a usable size */
814 #define pad_request(req) \
815 (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
817 /* pad request, checking for minimum (but not maximum) */
818 #define request2size(req) \
819 (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
822 /* ------------------ Operations on head and foot fields ----------------- */
825 The head field of a chunk is or'ed with PINUSE_BIT when previous
826 adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
827 use, unless mmapped, in which case both bits are cleared.
829 FLAG4_BIT is not used by this malloc, but might be useful in extensions.
832 #define PINUSE_BIT (SIZE_T_ONE)
833 #define CINUSE_BIT (SIZE_T_TWO)
834 #define FLAG4_BIT (SIZE_T_FOUR)
835 #define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)
836 #define FLAG_BITS (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT)
838 /* Head value for fenceposts */
839 #define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)
841 /* extraction of fields from head words */
842 #define cinuse(p) ((p)->head & CINUSE_BIT)
843 #define pinuse(p) ((p)->head & PINUSE_BIT)
844 #define flag4inuse(p) ((p)->head & FLAG4_BIT)
845 #define is_inuse(p) (((p)->head & INUSE_BITS) != PINUSE_BIT)
846 #define is_mmapped(p) (((p)->head & INUSE_BITS) == 0)
848 #define chunksize(p) ((p)->head & ~(FLAG_BITS))
850 #define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)
851 #define set_flag4(p) ((p)->head |= FLAG4_BIT)
852 #define clear_flag4(p) ((p)->head &= ~FLAG4_BIT)
854 /* Treat space at ptr +/- offset as a chunk */
855 #define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
856 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
858 /* Ptr to next or previous physical malloc_chunk. */
859 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS)))
860 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
862 /* extract next chunk's pinuse bit */
863 #define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)
865 /* Get/set size at footer */
866 #define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)
867 #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
869 /* Set size, pinuse bit, and foot */
870 #define set_size_and_pinuse_of_free_chunk(p, s)\
871 ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
873 /* Set size, pinuse bit, foot, and clear next pinuse */
874 #define set_free_with_pinuse(p, s, n)\
875 (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
877 /* Get the internal overhead associated with chunk p */
878 #define overhead_for(p)\
879 (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
881 /* Return true if malloced space is not necessarily cleared */
883 #define calloc_must_clear(p) (!is_mmapped(p))
884 #else /* MMAP_CLEARS */
885 #define calloc_must_clear(p) (1)
886 #endif /* MMAP_CLEARS */
888 /* ---------------------- Overlaid data structures ----------------------- */
891 When chunks are not in use, they are treated as nodes of either
894 "Small" chunks are stored in circular doubly-linked lists, and look
897 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
898 | Size of previous chunk |
899 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
900 `head:' | Size of chunk, in bytes |P|
901 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
902 | Forward pointer to next chunk in list |
903 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
904 | Back pointer to previous chunk in list |
905 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
906 | Unused space (may be 0 bytes long) .
909 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
910 `foot:' | Size of chunk, in bytes |
911 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
913 Larger chunks are kept in a form of bitwise digital trees (aka
914 tries) keyed on chunksizes. Because malloc_tree_chunks are only for
915 free chunks greater than 256 bytes, their size doesn't impose any
916 constraints on user chunk sizes. Each node looks like:
918 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
919 | Size of previous chunk |
920 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
921 `head:' | Size of chunk, in bytes |P|
922 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
923 | Forward pointer to next chunk of same size |
924 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
925 | Back pointer to previous chunk of same size |
926 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
927 | Pointer to left child (child[0]) |
928 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
929 | Pointer to right child (child[1]) |
930 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
931 | Pointer to parent |
932 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
933 | bin index of this chunk |
934 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
937 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
938 `foot:' | Size of chunk, in bytes |
939 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
941 Each tree holding treenodes is a tree of unique chunk sizes. Chunks
942 of the same size are arranged in a circularly-linked list, with only
943 the oldest chunk (the next to be used, in our FIFO ordering)
944 actually in the tree. (Tree members are distinguished by a non-null
945 parent pointer.) If a chunk with the same size an an existing node
946 is inserted, it is linked off the existing node using pointers that
947 work in the same way as fd/bk pointers of small chunks.
949 Each tree contains a power of 2 sized range of chunk sizes (the
950 smallest is 0x100 <= x < 0x180), which is is divided in half at each
951 tree level, with the chunks in the smaller half of the range (0x100
952 <= x < 0x140 for the top nose) in the left subtree and the larger
953 half (0x140 <= x < 0x180) in the right subtree. This is, of course,
954 done by inspecting individual bits.
956 Using these rules, each node's left subtree contains all smaller
957 sizes than its right subtree. However, the node at the root of each
958 subtree has no particular ordering relationship to either. (The
959 dividing line between the subtree sizes is based on trie relation.)
960 If we remove the last chunk of a given size from the interior of the
961 tree, we need to replace it with a leaf node. The tree ordering
962 rules permit a node to be replaced by any leaf below it.
964 The smallest chunk in a tree (a common operation in a best-fit
965 allocator) can be found by walking a path to the leftmost leaf in
966 the tree. Unlike a usual binary tree, where we follow left child
967 pointers until we reach a null, here we follow the right child
968 pointer any time the left one is null, until we reach a leaf with
969 both child pointers null. The smallest chunk in the tree will be
970 somewhere along that path.
972 The worst case number of steps to add, find, or remove a node is
973 bounded by the number of bits differentiating chunks within
974 bins. Under current bin calculations, this ranges from 6 up to 21
975 (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
976 is of course much better.
979 struct malloc_tree_chunk {
980 /* The first four fields must be compatible with malloc_chunk */
983 struct malloc_tree_chunk* fd;
984 struct malloc_tree_chunk* bk;
986 struct malloc_tree_chunk* child[2];
987 struct malloc_tree_chunk* parent;
991 typedef struct malloc_tree_chunk tchunk;
992 typedef struct malloc_tree_chunk* tchunkptr;
993 typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
995 /* A little helper macro for trees */
996 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
998 /* ----------------------------- Segments -------------------------------- */
1001 Each malloc space may include non-contiguous segments, held in a
1002 list headed by an embedded malloc_segment record representing the
1003 top-most space. Segments also include flags holding properties of
1004 the space. Large chunks that are directly allocated by mmap are not
1005 included in this list. They are instead independently created and
1006 destroyed without otherwise keeping track of them.
1008 Segment management mainly comes into play for spaces allocated by
1009 MMAP. Any call to MMAP might or might not return memory that is
1010 adjacent to an existing segment. MORECORE normally contiguously
1011 extends the current space, so this space is almost always adjacent,
1012 which is simpler and faster to deal with. (This is why MORECORE is
1013 used preferentially to MMAP when both are available -- see
1014 sys_alloc.) When allocating using MMAP, we don't use any of the
1015 hinting mechanisms (inconsistently) supported in various
1016 implementations of unix mmap, or distinguish reserving from
1017 committing memory. Instead, we just ask for space, and exploit
1018 contiguity when we get it. It is probably possible to do
1019 better than this on some systems, but no general scheme seems
1020 to be significantly better.
1022 Management entails a simpler variant of the consolidation scheme
1023 used for chunks to reduce fragmentation -- new adjacent memory is
1024 normally prepended or appended to an existing segment. However,
1025 there are limitations compared to chunk consolidation that mostly
1026 reflect the fact that segment processing is relatively infrequent
1027 (occurring only when getting memory from system) and that we
1028 don't expect to have huge numbers of segments:
1030 * Segments are not indexed, so traversal requires linear scans. (It
1031 would be possible to index these, but is not worth the extra
1032 overhead and complexity for most programs on most platforms.)
1033 * New segments are only appended to old ones when holding top-most
1034 memory; if they cannot be prepended to others, they are held in
1037 Except for the top-most segment of an mstate, each segment record
1038 is kept at the tail of its segment. Segments are added by pushing
1039 segment records onto the list headed by &mstate.seg for the
1042 Segment flags control allocation/merge/deallocation policies:
1043 * If EXTERN_BIT set, then we did not allocate this segment,
1044 and so should not try to deallocate or merge with others.
1045 (This currently holds only for the initial segment passed
1046 into create_mspace_with_base.)
1047 * If USE_MMAP_BIT set, the segment may be merged with
1048 other surrounding mmapped segments and trimmed/de-allocated
1050 * If neither bit is set, then the segment was obtained using
1051 MORECORE so can be merged with surrounding MORECORE'd segments
1052 and deallocated/trimmed using MORECORE with negative arguments.
1055 struct malloc_segment {
1056 char* base; /* base address */
1057 size_t size; /* allocated size */
1058 struct malloc_segment* next; /* ptr to next segment */
1059 flag_t sflags; /* mmap and extern flag */
1062 #define is_mmapped_segment(S) ((S)->sflags & USE_MMAP_BIT)
1063 #define is_extern_segment(S) ((S)->sflags & EXTERN_BIT)
1065 typedef struct malloc_segment msegment;
1066 typedef struct malloc_segment* msegmentptr;
1068 /* ---------------------------- malloc_state ----------------------------- */
1071 A malloc_state holds all of the bookkeeping for a space.
1072 The main fields are:
1075 The topmost chunk of the currently active segment. Its size is
1076 cached in topsize. The actual size of topmost space is
1077 topsize+TOP_FOOT_SIZE, which includes space reserved for adding
1078 fenceposts and segment records if necessary when getting more
1079 space from the system. The size at which to autotrim top is
1080 cached from mparams in trim_check, except that it is disabled if
1083 Designated victim (dv)
1084 This is the preferred chunk for servicing small requests that
1085 don't have exact fits. It is normally the chunk split off most
1086 recently to service another small request. Its size is cached in
1087 dvsize. The link fields of this chunk are not maintained since it
1088 is not kept in a bin.
1091 An array of bin headers for free chunks. These bins hold chunks
1092 with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
1093 chunks of all the same size, spaced 8 bytes apart. To simplify
1094 use in double-linked lists, each bin header acts as a malloc_chunk
1095 pointing to the real first node, if it exists (else pointing to
1096 itself). This avoids special-casing for headers. But to avoid
1097 waste, we allocate only the fd/bk pointers of bins, and then use
1098 repositioning tricks to treat these as the fields of a chunk.
1101 Treebins are pointers to the roots of trees holding a range of
1102 sizes. There are 2 equally spaced treebins for each power of two
1103 from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
1107 There is one bit map for small bins ("smallmap") and one for
1108 treebins ("treemap). Each bin sets its bit when non-empty, and
1109 clears the bit when empty. Bit operations are then used to avoid
1110 bin-by-bin searching -- nearly all "search" is done without ever
1111 looking at bins that won't be selected. The bit maps
1112 conservatively use 32 bits per map word, even if on 64bit system.
1113 For a good description of some of the bit-based techniques used
1114 here, see Henry S. Warren Jr's book "Hacker's Delight" (and
1115 supplement at http://hackersdelight.org/). Many of these are
1116 intended to reduce the branchiness of paths through malloc etc, as
1117 well as to reduce the number of memory locations read or written.
1120 A list of segments headed by an embedded malloc_segment record
1121 representing the initial space.
1123 Address check support
1124 The least_addr field is the least address ever obtained from
1125 MORECORE or MMAP. Attempted frees and reallocs of any address less
1126 than this are trapped (unless INSECURE is defined).
1129 A cross-check field that should always hold same value as mparams.magic.
1131 Max allowed footprint
1132 The maximum allowed bytes to allocate from system (zero means no limit)
1135 Bits recording whether to use MMAP, locks, or contiguous MORECORE
1138 Each space keeps track of current and maximum system memory
1139 obtained via MORECORE or MMAP.
1142 Fields holding the amount of unused topmost memory that should trigger
1143 trimming, and a counter to force periodic scanning to release unused
1144 non-topmost segments.
1147 If USE_LOCKS is defined, the "mutex" lock is acquired and released
1148 around every public call using this mspace.
1151 A void* pointer and a size_t field that can be used to help implement
1152 extensions to this malloc.
1155 /* Bin types, widths and sizes */
1156 #define NSMALLBINS (32U)
1157 #define NTREEBINS (32U)
1158 #define SMALLBIN_SHIFT (3U)
1159 #define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)
1160 #define TREEBIN_SHIFT (8U)
1161 #define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)
1162 #define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)
1163 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
1165 struct malloc_state {
1174 size_t release_checks;
1176 mchunkptr smallbins[(NSMALLBINS+1)*2];
1177 tbinptr treebins[NTREEBINS];
1179 size_t max_footprint;
1180 size_t footprint_limit; /* zero means no limit */
1183 MLOCK_T mutex; /* locate lock among fields that rarely change */
1184 #endif /* USE_LOCKS */
1186 void* extp; /* Unused but available for extensions */
1190 typedef struct malloc_state* mstate;
1192 /* ------------- Global malloc_state and malloc_params ------------------- */
1195 malloc_params holds global properties, including those that can be
1196 dynamically set using mallopt. There is a single instance, mparams,
1197 initialized in init_mparams. Note that the non-zeroness of "magic"
1198 also serves as an initialization flag.
1201 struct malloc_params {
1205 size_t mmap_threshold;
1206 size_t trim_threshold;
1207 flag_t default_mflags;
1210 static struct malloc_params mparams;
1212 /* Ensure mparams initialized */
1213 #define ensure_initialization() (void)(mparams.magic != 0 || init_mparams())
1217 /* The global malloc_state used for all non-"mspace" calls */
1218 static struct malloc_state _gm_;
1220 #define is_global(M) ((M) == &_gm_)
1222 #endif /* !ONLY_MSPACES */
1224 #define is_initialized(M) ((M)->top != 0)
1226 /* -------------------------- system alloc setup ------------------------- */
1228 /* Operations on mflags */
1230 #define use_lock(M) ((M)->mflags & USE_LOCK_BIT)
1231 #define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)
1233 #define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)
1235 #define disable_lock(M)
1238 #define use_mmap(M) ((M)->mflags & USE_MMAP_BIT)
1239 #define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT)
1241 #define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT)
1243 #define disable_mmap(M)
1246 #define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT)
1247 #define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT)
1248 #define use_noexpand(M) ((M)->mflags & USE_NOEXPAND_BIT)
1249 #define disable_expand(M) ((M)->mflags |= USE_NOEXPAND_BIT)
1250 #define use_trace(M) ((M)->mflags & USE_TRACE_BIT)
1251 #define enable_trace(M) ((M)->mflags |= USE_TRACE_BIT)
1252 #define disable_trace(M) ((M)->mflags &= ~USE_TRACE_BIT)
1254 #define set_lock(M,L)\
1255 ((M)->mflags = (L)?\
1256 ((M)->mflags | USE_LOCK_BIT) :\
1257 ((M)->mflags & ~USE_LOCK_BIT))
1259 /* page-align a size */
1260 #define page_align(S)\
1261 (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE))
1263 /* granularity-align a size */
1264 #define granularity_align(S)\
1265 (((S) + (mparams.granularity - SIZE_T_ONE))\
1266 & ~(mparams.granularity - SIZE_T_ONE))
1269 /* For mmap, use granularity alignment on windows, else page-align */
1271 #define mmap_align(S) granularity_align(S)
1273 #define mmap_align(S) page_align(S)
1276 /* For sys_alloc, enough padding to ensure can malloc request on success */
1277 #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT)
1279 #define is_page_aligned(S)\
1280 (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
1281 #define is_granularity_aligned(S)\
1282 (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
1284 /* True if segment S holds address A */
1285 #define segment_holds(S, A)\
1286 ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
1288 /* Return segment holding given address */
1289 CLIB_NOSANITIZE_ADDR
1290 static msegmentptr segment_holding(mstate m, char* addr) {
1291 msegmentptr sp = &m->seg;
1293 if (addr >= sp->base && addr < sp->base + sp->size)
1295 if ((sp = sp->next) == 0)
1300 /* Return true if segment contains a segment link */
1301 CLIB_NOSANITIZE_ADDR
1302 static int has_segment_link(mstate m, msegmentptr ss) {
1303 msegmentptr sp = &m->seg;
1305 if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
1307 if ((sp = sp->next) == 0)
1312 #ifndef MORECORE_CANNOT_TRIM
1313 #define should_trim(M,s) ((s) > (M)->trim_check)
1314 #else /* MORECORE_CANNOT_TRIM */
1315 #define should_trim(M,s) (0)
1316 #endif /* MORECORE_CANNOT_TRIM */
1319 TOP_FOOT_SIZE is padding at the end of a segment, including space
1320 that may be needed to place segment records and fenceposts when new
1321 noncontiguous segments are added.
1323 #define TOP_FOOT_SIZE\
1324 (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
1327 /* ------------------------------- Hooks -------------------------------- */
1330 PREACTION should be defined to return 0 on success, and nonzero on
1331 failure. If you are not using locking, you can redefine these to do
1336 #define PREACTION(M) ((use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
1337 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
1338 #else /* USE_LOCKS */
1341 #define PREACTION(M) (0)
1342 #endif /* PREACTION */
1345 #define POSTACTION(M)
1346 #endif /* POSTACTION */
1348 #endif /* USE_LOCKS */
1351 CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
1352 USAGE_ERROR_ACTION is triggered on detected bad frees and
1353 reallocs. The argument p is an address that might have triggered the
1354 fault. It is ignored by the two predefined actions, but might be
1355 useful in custom actions that try to help diagnose errors.
1358 #if PROCEED_ON_ERROR
1360 /* A count of the number of corruption errors causing resets */
1361 int malloc_corruption_error_count;
1363 /* default corruption action */
1364 static void reset_on_error(mstate m);
1366 #define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)
1367 #define USAGE_ERROR_ACTION(m, p)
1369 #else /* PROCEED_ON_ERROR */
1371 #ifndef CORRUPTION_ERROR_ACTION
1372 #define CORRUPTION_ERROR_ACTION(m) DLM_ABORT
1373 #endif /* CORRUPTION_ERROR_ACTION */
1375 #ifndef USAGE_ERROR_ACTION
1376 #define USAGE_ERROR_ACTION(m,p) DLM_ABORT
1377 #endif /* USAGE_ERROR_ACTION */
1379 #endif /* PROCEED_ON_ERROR */
1382 /* -------------------------- Debugging setup ---------------------------- */
1386 #define check_free_chunk(M,P)
1387 #define check_inuse_chunk(M,P)
1388 #define check_malloced_chunk(M,P,N)
1389 #define check_mmapped_chunk(M,P)
1390 #define check_malloc_state(M)
1391 #define check_top_chunk(M,P)
1394 #define check_free_chunk(M,P) do_check_free_chunk(M,P)
1395 #define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)
1396 #define check_top_chunk(M,P) do_check_top_chunk(M,P)
1397 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
1398 #define check_mmapped_chunk(M,P) do_check_mmapped_chunk(M,P)
1399 #define check_malloc_state(M) do_check_malloc_state(M)
1401 static void do_check_any_chunk(mstate m, mchunkptr p);
1402 static void do_check_top_chunk(mstate m, mchunkptr p);
1403 static void do_check_mmapped_chunk(mstate m, mchunkptr p);
1404 static void do_check_inuse_chunk(mstate m, mchunkptr p);
1405 static void do_check_free_chunk(mstate m, mchunkptr p);
1406 static void do_check_malloced_chunk(mstate m, void* mem, size_t s);
1407 static void do_check_tree(mstate m, tchunkptr t);
1408 static void do_check_treebin(mstate m, bindex_t i);
1409 static void do_check_smallbin(mstate m, bindex_t i);
1410 static void do_check_malloc_state(mstate m);
1411 static int bin_find(mstate m, mchunkptr x);
1412 static size_t traverse_and_check(mstate m);
1415 /* ---------------------------- Indexing Bins ---------------------------- */
1417 #define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
1418 #define small_index(s) (bindex_t)((s) >> SMALLBIN_SHIFT)
1419 #define small_index2size(i) ((i) << SMALLBIN_SHIFT)
1420 #define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))
1422 /* addressing by index. See above about smallbin repositioning */
1423 #define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
1424 #define treebin_at(M,i) (&((M)->treebins[i]))
1426 /* assign tree index for size S to variable I. Use x86 asm if possible */
1427 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
1428 #define compute_tree_index(S, I)\
1430 unsigned int X = S >> TREEBIN_SHIFT;\
1433 else if (X > 0xFFFF)\
1436 unsigned int K = (unsigned) sizeof(X)*__CHAR_BIT__ - 1 - (unsigned) __builtin_clz(X); \
1437 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
1441 #elif defined (__INTEL_COMPILER)
1442 #define compute_tree_index(S, I)\
1444 size_t X = S >> TREEBIN_SHIFT;\
1447 else if (X > 0xFFFF)\
1450 unsigned int K = _bit_scan_reverse (X); \
1451 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
1455 #elif defined(_MSC_VER) && _MSC_VER>=1300
1456 #define compute_tree_index(S, I)\
1458 size_t X = S >> TREEBIN_SHIFT;\
1461 else if (X > 0xFFFF)\
1465 _BitScanReverse((DWORD *) &K, (DWORD) X);\
1466 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
1471 #define compute_tree_index(S, I)\
1473 size_t X = S >> TREEBIN_SHIFT;\
1476 else if (X > 0xFFFF)\
1479 unsigned int Y = (unsigned int)X;\
1480 unsigned int N = ((Y - 0x100) >> 16) & 8;\
1481 unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
1483 N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
1484 K = 14 - N + ((Y <<= K) >> 15);\
1485 I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
1490 /* Bit representing maximum resolved size in a treebin at i */
1491 #define bit_for_tree_index(i) \
1492 (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
1494 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
1495 #define leftshift_for_tree_index(i) \
1496 ((i == NTREEBINS-1)? 0 : \
1497 ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
1499 /* The size of the smallest chunk held in bin with index i */
1500 #define minsize_for_tree_index(i) \
1501 ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \
1502 (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
1505 /* ------------------------ Operations on bin maps ----------------------- */
1507 /* bit corresponding to given index */
1508 #define idx2bit(i) ((binmap_t)(1) << (i))
1510 /* Mark/Clear bits with given index */
1511 #define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))
1512 #define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))
1513 #define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))
1515 #define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))
1516 #define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))
1517 #define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))
1519 /* isolate the least set bit of a bitmap */
1520 #define least_bit(x) ((x) & -(x))
1522 /* mask with all bits to left of least bit of x on */
1523 #define left_bits(x) ((x<<1) | -(x<<1))
1525 /* mask with all bits to left of or equal to least bit of x on */
1526 #define same_or_left_bits(x) ((x) | -(x))
1528 /* index corresponding to given bit. Use x86 asm if possible */
1530 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
1531 #define compute_bit2idx(X, I)\
1534 J = __builtin_ctz(X); \
1538 #elif defined (__INTEL_COMPILER)
1539 #define compute_bit2idx(X, I)\
1542 J = _bit_scan_forward (X); \
1546 #elif defined(_MSC_VER) && _MSC_VER>=1300
1547 #define compute_bit2idx(X, I)\
1550 _BitScanForward((DWORD *) &J, X);\
1554 #elif USE_BUILTIN_FFS
1555 #define compute_bit2idx(X, I) I = ffs(X)-1
1558 #define compute_bit2idx(X, I)\
1560 unsigned int Y = X - 1;\
1561 unsigned int K = Y >> (16-4) & 16;\
1562 unsigned int N = K; Y >>= K;\
1563 N += K = Y >> (8-3) & 8; Y >>= K;\
1564 N += K = Y >> (4-2) & 4; Y >>= K;\
1565 N += K = Y >> (2-1) & 2; Y >>= K;\
1566 N += K = Y >> (1-0) & 1; Y >>= K;\
1567 I = (bindex_t)(N + Y);\
1572 /* ----------------------- Runtime Check Support ------------------------- */
1575 For security, the main invariant is that malloc/free/etc never
1576 writes to a static address other than malloc_state, unless static
1577 malloc_state itself has been corrupted, which cannot occur via
1578 malloc (because of these checks). In essence this means that we
1579 believe all pointers, sizes, maps etc held in malloc_state, but
1580 check all of those linked or offsetted from other embedded data
1581 structures. These checks are interspersed with main code in a way
1582 that tends to minimize their run-time cost.
1584 When FOOTERS is defined, in addition to range checking, we also
1585 verify footer fields of inuse chunks, which can be used guarantee
1586 that the mstate controlling malloc/free is intact. This is a
1587 streamlined version of the approach described by William Robertson
1588 et al in "Run-time Detection of Heap-based Overflows" LISA'03
1589 http://www.usenix.org/events/lisa03/tech/robertson.html The footer
1590 of an inuse chunk holds the xor of its mstate and a random seed,
1591 that is checked upon calls to free() and realloc(). This is
1592 (probabilistically) unguessable from outside the program, but can be
1593 computed by any code successfully malloc'ing any chunk, so does not
1594 itself provide protection against code that has already broken
1595 security through some other means. Unlike Robertson et al, we
1596 always dynamically check addresses of all offset chunks (previous,
1597 next, etc). This turns out to be cheaper than relying on hashes.
1601 /* Check if address a is at least as high as any from MORECORE or MMAP */
1602 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
1603 /* Check if address of next chunk n is higher than base chunk p */
1604 #define ok_next(p, n) ((char*)(p) < (char*)(n))
1605 /* Check if p has inuse status */
1606 #define ok_inuse(p) is_inuse(p)
1607 /* Check if p has its pinuse bit on */
1608 #define ok_pinuse(p) pinuse(p)
1610 #else /* !INSECURE */
1611 #define ok_address(M, a) (1)
1612 #define ok_next(b, n) (1)
1613 #define ok_inuse(p) (1)
1614 #define ok_pinuse(p) (1)
1615 #endif /* !INSECURE */
1617 #if (FOOTERS && !INSECURE)
1618 /* Check if (alleged) mstate m has expected magic field */
1619 CLIB_NOSANITIZE_ADDR
1621 ok_magic (const mstate m)
1623 return (m->magic == mparams.magic);
1625 #else /* (FOOTERS && !INSECURE) */
1626 #define ok_magic(M) (1)
1627 #endif /* (FOOTERS && !INSECURE) */
1629 /* In gcc, use __builtin_expect to minimize impact of checks */
1631 #if defined(__GNUC__) && __GNUC__ >= 3
1632 #define RTCHECK(e) __builtin_expect(e, 1)
1634 #define RTCHECK(e) (e)
1636 #else /* !INSECURE */
1637 #define RTCHECK(e) (1)
1638 #endif /* !INSECURE */
1640 /* macros to set up inuse chunks with or without footers */
1644 #define mark_inuse_foot(M,p,s)
1646 /* Macros for setting head/foot of non-mmapped chunks */
1648 /* Set cinuse bit and pinuse bit of next chunk */
1649 #define set_inuse(M,p,s)\
1650 ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
1651 ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
1653 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
1654 #define set_inuse_and_pinuse(M,p,s)\
1655 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
1656 ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
1658 /* Set size, cinuse and pinuse bit of this chunk */
1659 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
1660 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
1664 /* Set foot of inuse chunk to be xor of mstate and seed */
1665 #define mark_inuse_foot(M,p,s)\
1666 (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
1668 #define get_mstate_for(p)\
1669 ((mstate)(((mchunkptr)((char*)(p) +\
1670 (chunksize(p))))->prev_foot ^ mparams.magic))
1672 #define set_inuse(M,p,s)\
1673 ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
1674 (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
1675 mark_inuse_foot(M,p,s))
1677 #define set_inuse_and_pinuse(M,p,s)\
1678 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
1679 (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
1680 mark_inuse_foot(M,p,s))
1682 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
1683 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
1684 mark_inuse_foot(M, p, s))
1686 #endif /* !FOOTERS */
1688 /* ---------------------------- setting mparams -------------------------- */
1691 static void pre_fork(void) { ACQUIRE_LOCK(&(gm)->mutex); }
1692 static void post_fork_parent(void) { RELEASE_LOCK(&(gm)->mutex); }
1693 static void post_fork_child(void) { INITIAL_LOCK(&(gm)->mutex); }
1694 #endif /* LOCK_AT_FORK */
1696 /* Initialize mparams */
1697 static int init_mparams(void) {
1698 #ifdef NEED_GLOBAL_LOCK_INIT
1699 if (malloc_global_mutex_status <= 0)
1700 init_malloc_global_mutex();
1703 ACQUIRE_MALLOC_GLOBAL_LOCK();
1704 if (mparams.magic == 0) {
1710 psize = malloc_getpagesize;
1711 gsize = ((DEFAULT_GRANULARITY != 0)? DEFAULT_GRANULARITY : psize);
1714 SYSTEM_INFO system_info;
1715 GetSystemInfo(&system_info);
1716 psize = system_info.dwPageSize;
1717 gsize = ((DEFAULT_GRANULARITY != 0)?
1718 DEFAULT_GRANULARITY : system_info.dwAllocationGranularity);
1722 /* Sanity-check configuration:
1723 size_t must be unsigned and as wide as pointer type.
1724 ints must be at least 4 bytes.
1725 alignment must be at least 8.
1726 Alignment, min chunk size, and page size must all be powers of 2.
1728 if ((sizeof(size_t) != sizeof(char*)) ||
1729 (MAX_SIZE_T < MIN_CHUNK_SIZE) ||
1730 (sizeof(int) < 4) ||
1731 (MALLOC_ALIGNMENT < (size_t)8U) ||
1732 ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
1733 ((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) ||
1734 ((gsize & (gsize-SIZE_T_ONE)) != 0) ||
1735 ((psize & (psize-SIZE_T_ONE)) != 0))
1737 mparams.granularity = gsize;
1738 mparams.page_size = psize;
1739 mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
1740 mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
1741 #if MORECORE_CONTIGUOUS
1742 mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
1743 #else /* MORECORE_CONTIGUOUS */
1744 mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
1745 #endif /* MORECORE_CONTIGUOUS */
1748 /* Set up lock for main malloc area */
1749 gm->mflags = mparams.default_mflags;
1750 (void)INITIAL_LOCK(&gm->mutex);
1753 pthread_atfork(&pre_fork, &post_fork_parent, &post_fork_child);
1757 #ifndef DLM_MAGIC_CONSTANT
1760 unsigned char buf[sizeof(size_t)];
1761 /* Try to use /dev/urandom, else fall back on using time */
1762 if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
1763 read(fd, buf, sizeof(buf)) == sizeof(buf)) {
1764 magic = *((size_t *) buf);
1768 #endif /* USE_DEV_RANDOM */
1770 magic = (size_t)(GetTickCount() ^ (size_t)0x55555555U);
1771 #elif defined(LACKS_TIME_H)
1772 magic = (size_t)&magic ^ (size_t)0x55555555U;
1774 magic = (size_t)(time(0) ^ (size_t)0x55555555U);
1776 magic |= (size_t)8U; /* ensure nonzero */
1777 magic &= ~(size_t)7U; /* improve chances of fault for bad values */
1779 magic = DLM_MAGIC_CONSTANT;
1781 /* Until memory modes commonly available, use volatile-write */
1782 (*(volatile size_t *)(&(mparams.magic))) = magic;
1786 RELEASE_MALLOC_GLOBAL_LOCK();
1790 /* support for mallopt */
1791 static int change_mparam(int param_number, int value) {
1793 ensure_initialization();
1794 val = (value == -1)? MAX_SIZE_T : (size_t)value;
1795 switch(param_number) {
1796 case M_TRIM_THRESHOLD:
1797 mparams.trim_threshold = val;
1800 if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
1801 mparams.granularity = val;
1806 case M_MMAP_THRESHOLD:
1807 mparams.mmap_threshold = val;
1815 /* ------------------------- Debugging Support --------------------------- */
1817 /* Check properties of any chunk, whether free, inuse, mmapped etc */
1818 static void do_check_any_chunk(mstate m, mchunkptr p) {
1819 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
1820 assert(ok_address(m, p));
1823 /* Check properties of top chunk */
1824 static void do_check_top_chunk(mstate m, mchunkptr p) {
1825 msegmentptr sp = segment_holding(m, (char*)p);
1826 size_t sz = p->head & ~INUSE_BITS; /* third-lowest bit can be set! */
1828 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
1829 assert(ok_address(m, p));
1830 assert(sz == m->topsize);
1832 assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
1834 assert(!pinuse(chunk_plus_offset(p, sz)));
1837 /* Check properties of (inuse) mmapped chunks */
1838 static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
1839 size_t sz = chunksize(p);
1840 size_t len = (sz + (p->prev_foot) + MMAP_FOOT_PAD);
1841 assert(is_mmapped(p));
1842 assert(use_mmap(m));
1843 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
1844 assert(ok_address(m, p));
1845 assert(!is_small(sz));
1846 assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
1847 assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
1848 assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
1851 /* Check properties of inuse chunks */
1852 static void do_check_inuse_chunk(mstate m, mchunkptr p) {
1853 do_check_any_chunk(m, p);
1854 assert(is_inuse(p));
1855 assert(next_pinuse(p));
1856 /* If not pinuse and not mmapped, previous chunk has OK offset */
1857 assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
1859 do_check_mmapped_chunk(m, p);
1862 /* Check properties of free chunks */
1863 static void do_check_free_chunk(mstate m, mchunkptr p) {
1864 size_t sz = chunksize(p);
1865 mchunkptr next = chunk_plus_offset(p, sz);
1866 do_check_any_chunk(m, p);
1867 assert(!is_inuse(p));
1868 assert(!next_pinuse(p));
1869 assert (!is_mmapped(p));
1870 if (p != m->dv && p != m->top) {
1871 if (sz >= MIN_CHUNK_SIZE) {
1872 assert((sz & CHUNK_ALIGN_MASK) == 0);
1873 assert(is_aligned(chunk2mem(p)));
1874 assert(next->prev_foot == sz);
1876 assert (next == m->top || is_inuse(next));
1877 assert(p->fd->bk == p);
1878 assert(p->bk->fd == p);
1880 else /* markers are always of size SIZE_T_SIZE */
1881 assert(sz == SIZE_T_SIZE);
1885 /* Check properties of malloced chunks at the point they are malloced */
1886 static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
1888 mchunkptr p = mem2chunk(mem);
1889 size_t sz = p->head & ~INUSE_BITS;
1890 do_check_inuse_chunk(m, p);
1891 assert((sz & CHUNK_ALIGN_MASK) == 0);
1892 assert(sz >= MIN_CHUNK_SIZE);
1894 /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
1895 assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
1899 /* Check a tree and its subtrees. */
1900 static void do_check_tree(mstate m, tchunkptr t) {
1903 bindex_t tindex = t->index;
1904 size_t tsize = chunksize(t);
1906 compute_tree_index(tsize, idx);
1907 assert(tindex == idx);
1908 assert(tsize >= MIN_LARGE_SIZE);
1909 assert(tsize >= minsize_for_tree_index(idx));
1910 assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
1912 do { /* traverse through chain of same-sized nodes */
1913 do_check_any_chunk(m, ((mchunkptr)u));
1914 assert(u->index == tindex);
1915 assert(chunksize(u) == tsize);
1916 assert(!is_inuse(u));
1917 assert(!next_pinuse(u));
1918 assert(u->fd->bk == u);
1919 assert(u->bk->fd == u);
1920 if (u->parent == 0) {
1921 assert(u->child[0] == 0);
1922 assert(u->child[1] == 0);
1925 assert(head == 0); /* only one node on chain has parent */
1927 assert(u->parent != u);
1928 assert (u->parent->child[0] == u ||
1929 u->parent->child[1] == u ||
1930 *((tbinptr*)(u->parent)) == u);
1931 if (u->child[0] != 0) {
1932 assert(u->child[0]->parent == u);
1933 assert(u->child[0] != u);
1934 do_check_tree(m, u->child[0]);
1936 if (u->child[1] != 0) {
1937 assert(u->child[1]->parent == u);
1938 assert(u->child[1] != u);
1939 do_check_tree(m, u->child[1]);
1941 if (u->child[0] != 0 && u->child[1] != 0) {
1942 assert(chunksize(u->child[0]) < chunksize(u->child[1]));
1950 /* Check all the chunks in a treebin. */
1951 static void do_check_treebin(mstate m, bindex_t i) {
1952 tbinptr* tb = treebin_at(m, i);
1954 int empty = (m->treemap & (1U << i)) == 0;
1958 do_check_tree(m, t);
1961 /* Check all the chunks in a smallbin. */
1962 static void do_check_smallbin(mstate m, bindex_t i) {
1963 sbinptr b = smallbin_at(m, i);
1964 mchunkptr p = b->bk;
1965 unsigned int empty = (m->smallmap & (1U << i)) == 0;
1969 for (; p != b; p = p->bk) {
1970 size_t size = chunksize(p);
1972 /* each chunk claims to be free */
1973 do_check_free_chunk(m, p);
1974 /* chunk belongs in bin */
1975 assert(small_index(size) == i);
1976 assert(p->bk == b || chunksize(p->bk) == chunksize(p));
1977 /* chunk is followed by an inuse chunk */
1979 if (q->head != FENCEPOST_HEAD)
1980 do_check_inuse_chunk(m, q);
1985 /* Find x in a bin. Used in other check functions. */
1986 static int bin_find(mstate m, mchunkptr x) {
1987 size_t size = chunksize(x);
1988 if (is_small(size)) {
1989 bindex_t sidx = small_index(size);
1990 sbinptr b = smallbin_at(m, sidx);
1991 if (smallmap_is_marked(m, sidx)) {
1996 } while ((p = p->fd) != b);
2001 compute_tree_index(size, tidx);
2002 if (treemap_is_marked(m, tidx)) {
2003 tchunkptr t = *treebin_at(m, tidx);
2004 size_t sizebits = size << leftshift_for_tree_index(tidx);
2005 while (t != 0 && chunksize(t) != size) {
2006 t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
2012 if (u == (tchunkptr)x)
2014 } while ((u = u->fd) != t);
2021 /* Traverse each chunk and check it; return total */
2022 static size_t traverse_and_check(mstate m) {
2024 if (is_initialized(m)) {
2025 msegmentptr s = &m->seg;
2026 sum += m->topsize + TOP_FOOT_SIZE;
2028 mchunkptr q = align_as_chunk(s->base);
2029 mchunkptr lastq = 0;
2031 while (segment_holds(s, q) &&
2032 q != m->top && q->head != FENCEPOST_HEAD) {
2033 sum += chunksize(q);
2035 assert(!bin_find(m, q));
2036 do_check_inuse_chunk(m, q);
2039 assert(q == m->dv || bin_find(m, q));
2040 assert(lastq == 0 || is_inuse(lastq)); /* Not 2 consecutive free */
2041 do_check_free_chunk(m, q);
2053 /* Check all properties of malloc_state. */
2054 static void do_check_malloc_state(mstate m) {
2058 for (i = 0; i < NSMALLBINS; ++i)
2059 do_check_smallbin(m, i);
2060 for (i = 0; i < NTREEBINS; ++i)
2061 do_check_treebin(m, i);
2063 if (m->dvsize != 0) { /* check dv chunk */
2064 do_check_any_chunk(m, m->dv);
2065 assert(m->dvsize == chunksize(m->dv));
2066 assert(m->dvsize >= MIN_CHUNK_SIZE);
2067 assert(bin_find(m, m->dv) == 0);
2070 if (m->top != 0) { /* check top chunk */
2071 do_check_top_chunk(m, m->top);
2072 /*assert(m->topsize == chunksize(m->top)); redundant */
2073 assert(m->topsize > 0);
2074 assert(bin_find(m, m->top) == 0);
2077 total = traverse_and_check(m);
2078 assert(total <= m->footprint);
2079 assert(m->footprint <= m->max_footprint);
2083 /* ----------------------------- statistics ------------------------------ */
2086 CLIB_NOSANITIZE_ADDR
2087 static struct dlmallinfo internal_mallinfo(mstate m) {
2088 struct dlmallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
2089 ensure_initialization();
2090 if (!PREACTION(m)) {
2091 check_malloc_state(m);
2092 if (is_initialized(m)) {
2093 size_t nfree = SIZE_T_ONE; /* top always free */
2094 size_t mfree = m->topsize + TOP_FOOT_SIZE;
2096 msegmentptr s = &m->seg;
2098 mchunkptr q = align_as_chunk(s->base);
2099 while (segment_holds(s, q) &&
2100 q != m->top && q->head != FENCEPOST_HEAD) {
2101 size_t sz = chunksize(q);
2114 nm.hblkhd = m->footprint - sum;
2115 nm.usmblks = m->max_footprint;
2116 nm.uordblks = m->footprint - mfree;
2117 nm.fordblks = mfree;
2118 nm.keepcost = m->topsize;
2125 #endif /* !NO_MALLINFO */
2127 #if !NO_MALLOC_STATS
2128 static void internal_malloc_stats(mstate m) {
2129 ensure_initialization();
2130 if (!PREACTION(m)) {
2134 check_malloc_state(m);
2135 if (is_initialized(m)) {
2136 msegmentptr s = &m->seg;
2137 maxfp = m->max_footprint;
2139 used = fp - (m->topsize + TOP_FOOT_SIZE);
2142 mchunkptr q = align_as_chunk(s->base);
2143 while (segment_holds(s, q) &&
2144 q != m->top && q->head != FENCEPOST_HEAD) {
2146 used -= chunksize(q);
2152 POSTACTION(m); /* drop lock */
2153 fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
2154 fprintf(stderr, "system bytes = %10lu\n", (unsigned long)(fp));
2155 fprintf(stderr, "in use bytes = %10lu\n", (unsigned long)(used));
2158 #endif /* NO_MALLOC_STATS */
2160 /* ----------------------- Operations on smallbins ----------------------- */
2163 Various forms of linking and unlinking are defined as macros. Even
2164 the ones for trees, which are very long but have very short typical
2165 paths. This is ugly but reduces reliance on inlining support of
2169 /* Link a free chunk into a smallbin */
2170 #define insert_small_chunk(M, P, S) {\
2171 bindex_t I = small_index(S);\
2172 mchunkptr B = smallbin_at(M, I);\
2174 assert(S >= MIN_CHUNK_SIZE);\
2175 if (!smallmap_is_marked(M, I))\
2176 mark_smallmap(M, I);\
2177 else if (RTCHECK(ok_address(M, B->fd)))\
2180 CORRUPTION_ERROR_ACTION(M);\
2188 /* Unlink a chunk from a smallbin */
2189 #define unlink_small_chunk(M, P, S) {\
2190 mchunkptr F = P->fd;\
2191 mchunkptr B = P->bk;\
2192 bindex_t I = small_index(S);\
2195 assert(chunksize(P) == small_index2size(I));\
2196 if (RTCHECK(F == smallbin_at(M,I) || (ok_address(M, F) && F->bk == P))) { \
2198 clear_smallmap(M, I);\
2200 else if (RTCHECK(B == smallbin_at(M,I) ||\
2201 (ok_address(M, B) && B->fd == P))) {\
2206 CORRUPTION_ERROR_ACTION(M);\
2210 CORRUPTION_ERROR_ACTION(M);\
2214 /* Unlink the first chunk from a smallbin */
2215 #define unlink_first_small_chunk(M, B, P, I) {\
2216 mchunkptr F = P->fd;\
2219 assert(chunksize(P) == small_index2size(I));\
2221 clear_smallmap(M, I);\
2223 else if (RTCHECK(ok_address(M, F) && F->bk == P)) {\
2228 CORRUPTION_ERROR_ACTION(M);\
2232 /* Replace dv node, binning the old one */
2233 /* Used only when dvsize known to be small */
2234 #define replace_dv(M, P, S) {\
2235 size_t DVS = M->dvsize;\
2236 assert(is_small(DVS));\
2238 mchunkptr DV = M->dv;\
2239 insert_small_chunk(M, DV, DVS);\
2245 /* ------------------------- Operations on trees ------------------------- */
2247 /* Insert chunk into tree */
2248 #define insert_large_chunk(M, X, S) {\
2251 compute_tree_index(S, I);\
2252 H = treebin_at(M, I);\
2254 X->child[0] = X->child[1] = 0;\
2255 if (!treemap_is_marked(M, I)) {\
2256 mark_treemap(M, I);\
2258 X->parent = (tchunkptr)H;\
2263 size_t K = S << leftshift_for_tree_index(I);\
2265 if (chunksize(T) != S) {\
2266 tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
2270 else if (RTCHECK(ok_address(M, C))) {\
2277 CORRUPTION_ERROR_ACTION(M);\
2282 tchunkptr F = T->fd;\
2283 if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
2291 CORRUPTION_ERROR_ACTION(M);\
2302 1. If x is a chained node, unlink it from its same-sized fd/bk links
2303 and choose its bk node as its replacement.
2304 2. If x was the last node of its size, but not a leaf node, it must
2305 be replaced with a leaf node (not merely one with an open left or
2306 right), to make sure that lefts and rights of descendents
2307 correspond properly to bit masks. We use the rightmost descendent
2308 of x. We could use any other leaf, but this is easy to locate and
2309 tends to counteract removal of leftmosts elsewhere, and so keeps
2310 paths shorter than minimally guaranteed. This doesn't loop much
2311 because on average a node in a tree is near the bottom.
2312 3. If x is the base of a chain (i.e., has parent links) relink
2313 x's parent and children to x's replacement (or null if none).
2316 #define unlink_large_chunk(M, X) {\
2317 tchunkptr XP = X->parent;\
2320 tchunkptr F = X->fd;\
2322 if (RTCHECK(ok_address(M, F) && F->bk == X && R->fd == X)) {\
2327 CORRUPTION_ERROR_ACTION(M);\
2332 if (((R = *(RP = &(X->child[1]))) != 0) ||\
2333 ((R = *(RP = &(X->child[0]))) != 0)) {\
2335 while ((*(CP = &(R->child[1])) != 0) ||\
2336 (*(CP = &(R->child[0])) != 0)) {\
2339 if (RTCHECK(ok_address(M, RP)))\
2342 CORRUPTION_ERROR_ACTION(M);\
2347 tbinptr* H = treebin_at(M, X->index);\
2349 if ((*H = R) == 0) \
2350 clear_treemap(M, X->index);\
2352 else if (RTCHECK(ok_address(M, XP))) {\
2353 if (XP->child[0] == X) \
2359 CORRUPTION_ERROR_ACTION(M);\
2361 if (RTCHECK(ok_address(M, R))) {\
2364 if ((C0 = X->child[0]) != 0) {\
2365 if (RTCHECK(ok_address(M, C0))) {\
2370 CORRUPTION_ERROR_ACTION(M);\
2372 if ((C1 = X->child[1]) != 0) {\
2373 if (RTCHECK(ok_address(M, C1))) {\
2378 CORRUPTION_ERROR_ACTION(M);\
2382 CORRUPTION_ERROR_ACTION(M);\
2387 /* Relays to large vs small bin operations */
2389 #define insert_chunk(M, P, S)\
2390 if (is_small(S)) insert_small_chunk(M, P, S)\
2391 else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
2393 #define unlink_chunk(M, P, S)\
2394 if (is_small(S)) unlink_small_chunk(M, P, S)\
2395 else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
2398 /* Relays to internal calls to malloc/free from realloc, memalign etc */
2401 #define internal_malloc(m, b) mspace_malloc(m, b)
2402 #define internal_free(m, mem) mspace_free(m,mem);
2403 #else /* ONLY_MSPACES */
2405 #define internal_malloc(m, b)\
2406 ((m == gm)? dlmalloc(b) : mspace_malloc(m, b))
2407 #define internal_free(m, mem)\
2408 if (m == gm) dlfree(mem); else mspace_free(m,mem);
2410 #define internal_malloc(m, b) dlmalloc(b)
2411 #define internal_free(m, mem) dlfree(mem)
2412 #endif /* MSPACES */
2413 #endif /* ONLY_MSPACES */
2415 /* ----------------------- Direct-mmapping chunks ----------------------- */
2418 Directly mmapped chunks are set up with an offset to the start of
2419 the mmapped region stored in the prev_foot field of the chunk. This
2420 allows reconstruction of the required argument to MUNMAP when freed,
2421 and also allows adjustment of the returned chunk to meet alignment
2422 requirements (especially in memalign).
2425 /* Malloc using mmap */
2426 static void* mmap_alloc(mstate m, size_t nb) {
2427 size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
2428 if (m->footprint_limit != 0) {
2429 size_t fp = m->footprint + mmsize;
2430 if (fp <= m->footprint || fp > m->footprint_limit)
2433 if (mmsize > nb) { /* Check for wrap around 0 */
2434 char* mm = (char*)(CALL_DIRECT_MMAP(mmsize));
2436 size_t offset = align_offset(chunk2mem(mm));
2437 size_t psize = mmsize - offset - MMAP_FOOT_PAD;
2438 mchunkptr p = (mchunkptr)(mm + offset);
2439 p->prev_foot = offset;
2441 mark_inuse_foot(m, p, psize);
2442 chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
2443 chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
2445 if (m->least_addr == 0 || mm < m->least_addr)
2447 if ((m->footprint += mmsize) > m->max_footprint)
2448 m->max_footprint = m->footprint;
2449 assert(is_aligned(chunk2mem(p)));
2450 check_mmapped_chunk(m, p);
2451 return chunk2mem(p);
2457 /* Realloc using mmap */
2458 static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb, int flags) {
2459 size_t oldsize = chunksize(oldp);
2460 (void)flags; /* placate people compiling -Wunused */
2461 if (is_small(nb)) /* Can't shrink mmap regions below small size */
2463 /* Keep old chunk if big enough but not too big */
2464 if (oldsize >= nb + SIZE_T_SIZE &&
2465 (oldsize - nb) <= (mparams.granularity << 1))
2468 size_t offset = oldp->prev_foot;
2469 size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
2470 size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
2471 char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
2472 oldmmsize, newmmsize, flags);
2474 mchunkptr newp = (mchunkptr)(cp + offset);
2475 size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
2477 mark_inuse_foot(m, newp, psize);
2478 chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
2479 chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
2481 if (cp < m->least_addr)
2483 if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
2484 m->max_footprint = m->footprint;
2485 check_mmapped_chunk(m, newp);
2493 /* -------------------------- mspace management -------------------------- */
2495 /* Initialize top chunk and its size */
2496 CLIB_NOSANITIZE_ADDR
2497 static void init_top(mstate m, mchunkptr p, size_t psize) {
2498 /* Ensure alignment */
2499 size_t offset = align_offset(chunk2mem(p));
2500 p = (mchunkptr)((char*)p + offset);
2505 p->head = psize | PINUSE_BIT;
2506 /* set size of fake trailing chunk holding overhead space only once */
2507 chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
2508 m->trim_check = mparams.trim_threshold; /* reset on each update */
2511 /* Initialize bins for a new mstate that is otherwise zeroed out */
2512 static void init_bins(mstate m) {
2513 /* Establish circular links for smallbins */
2515 for (i = 0; i < NSMALLBINS; ++i) {
2516 sbinptr bin = smallbin_at(m,i);
2517 bin->fd = bin->bk = bin;
2521 #if PROCEED_ON_ERROR
2523 /* default corruption action */
2524 static void reset_on_error(mstate m) {
2526 ++malloc_corruption_error_count;
2527 /* Reinitialize fields to forget about all memory */
2528 m->smallmap = m->treemap = 0;
2529 m->dvsize = m->topsize = 0;
2534 for (i = 0; i < NTREEBINS; ++i)
2535 *treebin_at(m, i) = 0;
2538 #endif /* PROCEED_ON_ERROR */
2540 /* Allocate chunk and prepend remainder with chunk in successor base. */
2541 CLIB_NOSANITIZE_ADDR
2542 static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
2544 mchunkptr p = align_as_chunk(newbase);
2545 mchunkptr oldfirst = align_as_chunk(oldbase);
2546 size_t psize = (char*)oldfirst - (char*)p;
2547 mchunkptr q = chunk_plus_offset(p, nb);
2548 size_t qsize = psize - nb;
2549 set_size_and_pinuse_of_inuse_chunk(m, p, nb);
2551 assert((char*)oldfirst > (char*)q);
2552 assert(pinuse(oldfirst));
2553 assert(qsize >= MIN_CHUNK_SIZE);
2555 /* consolidate remainder with first chunk of old base */
2556 if (oldfirst == m->top) {
2557 size_t tsize = m->topsize += qsize;
2559 q->head = tsize | PINUSE_BIT;
2560 check_top_chunk(m, q);
2562 else if (oldfirst == m->dv) {
2563 size_t dsize = m->dvsize += qsize;
2565 set_size_and_pinuse_of_free_chunk(q, dsize);
2568 if (!is_inuse(oldfirst)) {
2569 size_t nsize = chunksize(oldfirst);
2570 unlink_chunk(m, oldfirst, nsize);
2571 oldfirst = chunk_plus_offset(oldfirst, nsize);
2574 set_free_with_pinuse(q, qsize, oldfirst);
2575 insert_chunk(m, q, qsize);
2576 check_free_chunk(m, q);
2579 check_malloced_chunk(m, chunk2mem(p), nb);
2580 return chunk2mem(p);
2583 /* Add a segment to hold a new noncontiguous region */
2584 CLIB_NOSANITIZE_ADDR
2585 static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
2586 /* Determine locations and sizes of segment, fenceposts, old top */
2587 char* old_top = (char*)m->top;
2588 msegmentptr oldsp = segment_holding(m, old_top);
2589 char* old_end = oldsp->base + oldsp->size;
2590 size_t ssize = pad_request(sizeof(struct malloc_segment));
2591 char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
2592 size_t offset = align_offset(chunk2mem(rawsp));
2593 char* asp = rawsp + offset;
2594 char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
2595 mchunkptr sp = (mchunkptr)csp;
2596 msegmentptr ss = (msegmentptr)(chunk2mem(sp));
2597 mchunkptr tnext = chunk_plus_offset(sp, ssize);
2598 mchunkptr p = tnext;
2601 /* reset top to new space */
2602 init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
2604 /* Set up segment record */
2605 assert(is_aligned(ss));
2606 set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
2607 *ss = m->seg; /* Push current record */
2608 m->seg.base = tbase;
2609 m->seg.size = tsize;
2610 m->seg.sflags = mmapped;
2613 /* Insert trailing fenceposts */
2615 mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
2616 p->head = FENCEPOST_HEAD;
2618 if ((char*)(&(nextp->head)) < old_end)
2623 assert(nfences >= 2);
2625 /* Insert the rest of old top into a bin as an ordinary free chunk */
2626 if (csp != old_top) {
2627 mchunkptr q = (mchunkptr)old_top;
2628 size_t psize = csp - old_top;
2629 mchunkptr tn = chunk_plus_offset(q, psize);
2630 set_free_with_pinuse(q, psize, tn);
2631 insert_chunk(m, q, psize);
2634 check_top_chunk(m, m->top);
2637 /* -------------------------- System allocation -------------------------- */
2639 /* Get memory from system using MORECORE or MMAP */
2640 CLIB_NOSANITIZE_ADDR
2641 static void* sys_alloc(mstate m, size_t nb) {
2642 char* tbase = CMFAIL;
2644 flag_t mmap_flag = 0;
2645 size_t asize; /* allocation size */
2647 ensure_initialization();
2649 if (use_noexpand(m))
2652 /* Directly map large chunks, but only if already initialized */
2653 if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) {
2654 void* mem = mmap_alloc(m, nb);
2659 asize = granularity_align(nb + SYS_ALLOC_PADDING);
2661 return 0; /* wraparound */
2662 if (m->footprint_limit != 0) {
2663 size_t fp = m->footprint + asize;
2664 if (fp <= m->footprint || fp > m->footprint_limit)
2669 Try getting memory in any of three ways (in most-preferred to
2670 least-preferred order):
2671 1. A call to MORECORE that can normally contiguously extend memory.
2672 (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
2673 or main space is mmapped or a previous contiguous call failed)
2674 2. A call to MMAP new space (disabled if not HAVE_MMAP).
2675 Note that under the default settings, if MORECORE is unable to
2676 fulfill a request, and HAVE_MMAP is true, then mmap is
2677 used as a noncontiguous system allocator. This is a useful backup
2678 strategy for systems with holes in address spaces -- in this case
2679 sbrk cannot contiguously expand the heap, but mmap may be able to
2681 3. A call to MORECORE that cannot usually contiguously extend memory.
2682 (disabled if not HAVE_MORECORE)
2684 In all cases, we need to request enough bytes from system to ensure
2685 we can malloc nb bytes upon success, so pad with enough space for
2686 top_foot, plus alignment-pad to make sure we don't lose bytes if
2687 not on boundary, and round this up to a granularity unit.
2690 if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
2692 size_t ssize = asize; /* sbrk call size */
2693 msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
2694 ACQUIRE_MALLOC_GLOBAL_LOCK();
2696 if (ss == 0) { /* First time through or recovery */
2697 char* base = (char*)CALL_MORECORE(0);
2698 if (base != CMFAIL) {
2700 /* Adjust to end on a page boundary */
2701 if (!is_page_aligned(base))
2702 ssize += (page_align((size_t)base) - (size_t)base);
2703 fp = m->footprint + ssize; /* recheck limits */
2704 if (ssize > nb && ssize < HALF_MAX_SIZE_T &&
2705 (m->footprint_limit == 0 ||
2706 (fp > m->footprint && fp <= m->footprint_limit)) &&
2707 (br = (char*)(CALL_MORECORE(ssize))) == base) {
2714 /* Subtract out existing available top space from MORECORE request. */
2715 ssize = granularity_align(nb - m->topsize + SYS_ALLOC_PADDING);
2716 /* Use mem here only if it did continuously extend old space */
2717 if (ssize < HALF_MAX_SIZE_T &&
2718 (br = (char*)(CALL_MORECORE(ssize))) == ss->base+ss->size) {
2724 if (tbase == CMFAIL) { /* Cope with partial failure */
2725 if (br != CMFAIL) { /* Try to use/extend the space we did get */
2726 if (ssize < HALF_MAX_SIZE_T &&
2727 ssize < nb + SYS_ALLOC_PADDING) {
2728 size_t esize = granularity_align(nb + SYS_ALLOC_PADDING - ssize);
2729 if (esize < HALF_MAX_SIZE_T) {
2730 char* end = (char*)CALL_MORECORE(esize);
2733 else { /* Can't use; try to release */
2734 (void) CALL_MORECORE(-ssize);
2740 if (br != CMFAIL) { /* Use the space we did get */
2745 disable_contiguous(m); /* Don't try contiguous path in the future */
2748 RELEASE_MALLOC_GLOBAL_LOCK();
2751 if (HAVE_MMAP && tbase == CMFAIL) { /* Try MMAP */
2752 char* mp = (char*)(CALL_MMAP(asize));
2756 mmap_flag = USE_MMAP_BIT;
2760 if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
2761 if (asize < HALF_MAX_SIZE_T) {
2764 ACQUIRE_MALLOC_GLOBAL_LOCK();
2765 br = (char*)(CALL_MORECORE(asize));
2766 end = (char*)(CALL_MORECORE(0));
2767 RELEASE_MALLOC_GLOBAL_LOCK();
2768 if (br != CMFAIL && end != CMFAIL && br < end) {
2769 size_t ssize = end - br;
2770 if (ssize > nb + TOP_FOOT_SIZE) {
2778 if (tbase != CMFAIL) {
2780 if ((m->footprint += tsize) > m->max_footprint)
2781 m->max_footprint = m->footprint;
2783 if (!is_initialized(m)) { /* first-time initialization */
2784 if (m->least_addr == 0 || tbase < m->least_addr)
2785 m->least_addr = tbase;
2786 m->seg.base = tbase;
2787 m->seg.size = tsize;
2788 m->seg.sflags = mmap_flag;
2789 m->magic = mparams.magic;
2790 m->release_checks = MAX_RELEASE_CHECK_RATE;
2794 init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
2798 /* Offset top by embedded malloc_state */
2799 mchunkptr mn = next_chunk(mem2chunk(m));
2800 init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
2805 /* Try to merge with an existing segment */
2806 msegmentptr sp = &m->seg;
2807 /* Only consider most recent segment if traversal suppressed */
2808 while (sp != 0 && tbase != sp->base + sp->size)
2809 sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
2811 !is_extern_segment(sp) &&
2812 (sp->sflags & USE_MMAP_BIT) == mmap_flag &&
2813 segment_holds(sp, m->top)) { /* append */
2815 init_top(m, m->top, m->topsize + tsize);
2818 if (tbase < m->least_addr)
2819 m->least_addr = tbase;
2821 while (sp != 0 && sp->base != tbase + tsize)
2822 sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
2824 !is_extern_segment(sp) &&
2825 (sp->sflags & USE_MMAP_BIT) == mmap_flag) {
2826 char* oldbase = sp->base;
2829 return prepend_alloc(m, tbase, oldbase, nb);
2832 add_segment(m, tbase, tsize, mmap_flag);
2836 if (nb < m->topsize) { /* Allocate from new or extended top space */
2837 size_t rsize = m->topsize -= nb;
2838 mchunkptr p = m->top;
2839 mchunkptr r = m->top = chunk_plus_offset(p, nb);
2840 r->head = rsize | PINUSE_BIT;
2841 set_size_and_pinuse_of_inuse_chunk(m, p, nb);
2842 check_top_chunk(m, m->top);
2843 check_malloced_chunk(m, chunk2mem(p), nb);
2844 return chunk2mem(p);
2848 MALLOC_FAILURE_ACTION;
2852 /* ----------------------- system deallocation -------------------------- */
2854 /* Unmap and unlink any mmapped segments that don't contain used chunks */
2855 CLIB_NOSANITIZE_ADDR
2856 static size_t release_unused_segments(mstate m) {
2857 size_t released = 0;
2859 msegmentptr pred = &m->seg;
2860 msegmentptr sp = pred->next;
2862 char* base = sp->base;
2863 size_t size = sp->size;
2864 msegmentptr next = sp->next;
2866 if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
2867 mchunkptr p = align_as_chunk(base);
2868 size_t psize = chunksize(p);
2869 /* Can unmap if first chunk holds entire segment and not pinned */
2870 if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
2871 tchunkptr tp = (tchunkptr)p;
2872 assert(segment_holds(sp, (char*)sp));
2878 unlink_large_chunk(m, tp);
2880 if (CALL_MUNMAP(base, size) == 0) {
2882 m->footprint -= size;
2883 /* unlink obsoleted record */
2887 else { /* back out if cannot unmap */
2888 insert_large_chunk(m, tp, psize);
2892 if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */
2897 /* Reset check counter */
2898 m->release_checks = (((size_t) nsegs > (size_t) MAX_RELEASE_CHECK_RATE)?
2899 (size_t) nsegs : (size_t) MAX_RELEASE_CHECK_RATE);
2903 CLIB_NOSANITIZE_ADDR
2904 static int sys_trim(mstate m, size_t pad) {
2905 size_t released = 0;
2906 ensure_initialization();
2907 if (pad < MAX_REQUEST && is_initialized(m)) {
2908 pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
2910 if (m->topsize > pad) {
2911 /* Shrink top space in granularity-size units, keeping at least one */
2912 size_t unit = mparams.granularity;
2913 size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
2915 msegmentptr sp = segment_holding(m, (char*)m->top);
2917 if (!is_extern_segment(sp)) {
2918 if (is_mmapped_segment(sp)) {
2920 sp->size >= extra &&
2921 !has_segment_link(m, sp)) { /* can't shrink if pinned */
2922 size_t newsize = sp->size - extra;
2923 (void)newsize; /* placate people compiling -Wunused-variable */
2924 /* Prefer mremap, fall back to munmap */
2925 if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
2926 (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
2931 else if (HAVE_MORECORE) {
2932 if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
2933 extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
2934 ACQUIRE_MALLOC_GLOBAL_LOCK();
2936 /* Make sure end of memory is where we last set it. */
2937 char* old_br = (char*)(CALL_MORECORE(0));
2938 if (old_br == sp->base + sp->size) {
2939 char* rel_br = (char*)(CALL_MORECORE(-extra));
2940 char* new_br = (char*)(CALL_MORECORE(0));
2941 if (rel_br != CMFAIL && new_br < old_br)
2942 released = old_br - new_br;
2945 RELEASE_MALLOC_GLOBAL_LOCK();
2949 if (released != 0) {
2950 sp->size -= released;
2951 m->footprint -= released;
2952 init_top(m, m->top, m->topsize - released);
2953 check_top_chunk(m, m->top);
2957 /* Unmap any unused mmapped segments */
2959 released += release_unused_segments(m);
2961 /* On failure, disable autotrim to avoid repeated failed future calls */
2962 if (released == 0 && m->topsize > m->trim_check)
2963 m->trim_check = MAX_SIZE_T;
2966 return (released != 0)? 1 : 0;
2969 /* Consolidate and bin a chunk. Differs from exported versions
2970 of free mainly in that the chunk need not be marked as inuse.
2972 CLIB_NOSANITIZE_ADDR
2973 static void dispose_chunk(mstate m, mchunkptr p, size_t psize) {
2974 mchunkptr next = chunk_plus_offset(p, psize);
2977 size_t prevsize = p->prev_foot;
2978 if (is_mmapped(p)) {
2979 psize += prevsize + MMAP_FOOT_PAD;
2980 if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
2981 m->footprint -= psize;
2984 prev = chunk_minus_offset(p, prevsize);
2987 if (RTCHECK(ok_address(m, prev))) { /* consolidate backward */
2989 unlink_chunk(m, p, prevsize);
2991 else if ((next->head & INUSE_BITS) == INUSE_BITS) {
2993 set_free_with_pinuse(p, psize, next);
2998 CORRUPTION_ERROR_ACTION(m);
3002 if (RTCHECK(ok_address(m, next))) {
3003 if (!cinuse(next)) { /* consolidate forward */
3004 if (next == m->top) {
3005 size_t tsize = m->topsize += psize;
3007 p->head = tsize | PINUSE_BIT;
3014 else if (next == m->dv) {
3015 size_t dsize = m->dvsize += psize;
3017 set_size_and_pinuse_of_free_chunk(p, dsize);
3021 size_t nsize = chunksize(next);
3023 unlink_chunk(m, next, nsize);
3024 set_size_and_pinuse_of_free_chunk(p, psize);
3032 set_free_with_pinuse(p, psize, next);
3034 insert_chunk(m, p, psize);
3037 CORRUPTION_ERROR_ACTION(m);
3041 /* ---------------------------- malloc --------------------------- */
3043 /* allocate a large request from the best fitting chunk in a treebin */
3044 CLIB_NOSANITIZE_ADDR
3045 static void* tmalloc_large(mstate m, size_t nb) {
3047 size_t rsize = -nb; /* Unsigned negation */
3050 compute_tree_index(nb, idx);
3051 if ((t = *treebin_at(m, idx)) != 0) {
3052 /* Traverse tree for this bin looking for node with size == nb */
3053 size_t sizebits = nb << leftshift_for_tree_index(idx);
3054 tchunkptr rst = 0; /* The deepest untaken right subtree */
3057 size_t trem = chunksize(t) - nb;
3060 if ((rsize = trem) == 0)
3064 t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
3065 if (rt != 0 && rt != t)
3068 t = rst; /* set t to least subtree holding sizes > nb */
3074 if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
3075 binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
3076 if (leftbits != 0) {
3078 binmap_t leastbit = least_bit(leftbits);
3079 compute_bit2idx(leastbit, i);
3080 t = *treebin_at(m, i);
3084 while (t != 0) { /* find smallest of tree or subtree */
3085 size_t trem = chunksize(t) - nb;
3090 t = leftmost_child(t);
3093 /* If dv is a better fit, return 0 so malloc will use it */
3094 if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
3095 if (RTCHECK(ok_address(m, v))) { /* split */
3096 mchunkptr r = chunk_plus_offset(v, nb);
3097 assert(chunksize(v) == rsize + nb);
3098 if (RTCHECK(ok_next(v, r))) {
3099 unlink_large_chunk(m, v);
3100 if (rsize < MIN_CHUNK_SIZE)
3101 set_inuse_and_pinuse(m, v, (rsize + nb));
3103 set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3104 set_size_and_pinuse_of_free_chunk(r, rsize);
3105 insert_chunk(m, r, rsize);
3107 return chunk2mem(v);
3110 CORRUPTION_ERROR_ACTION(m);
3115 /* allocate a small request from the best fitting chunk in a treebin */
3116 CLIB_NOSANITIZE_ADDR
3117 static void* tmalloc_small(mstate m, size_t nb) {
3121 binmap_t leastbit = least_bit(m->treemap);
3122 compute_bit2idx(leastbit, i);
3123 v = t = *treebin_at(m, i);
3124 rsize = chunksize(t) - nb;
3126 while ((t = leftmost_child(t)) != 0) {
3127 size_t trem = chunksize(t) - nb;
3134 if (RTCHECK(ok_address(m, v))) {
3135 mchunkptr r = chunk_plus_offset(v, nb);
3136 assert(chunksize(v) == rsize + nb);
3137 if (RTCHECK(ok_next(v, r))) {
3138 unlink_large_chunk(m, v);
3139 if (rsize < MIN_CHUNK_SIZE)
3140 set_inuse_and_pinuse(m, v, (rsize + nb));
3142 set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3143 set_size_and_pinuse_of_free_chunk(r, rsize);
3144 replace_dv(m, r, rsize);
3146 return chunk2mem(v);
3150 CORRUPTION_ERROR_ACTION(m);
3156 void* dlmalloc(size_t bytes) {
3159 If a small request (< 256 bytes minus per-chunk overhead):
3160 1. If one exists, use a remainderless chunk in associated smallbin.
3161 (Remainderless means that there are too few excess bytes to
3162 represent as a chunk.)
3163 2. If it is big enough, use the dv chunk, which is normally the
3164 chunk adjacent to the one used for the most recent small request.
3165 3. If one exists, split the smallest available chunk in a bin,
3166 saving remainder in dv.
3167 4. If it is big enough, use the top chunk.
3168 5. If available, get memory from system and use it
3169 Otherwise, for a large request:
3170 1. Find the smallest available binned chunk that fits, and use it
3171 if it is better fitting than dv chunk, splitting if necessary.
3172 2. If better fitting than any binned chunk, use the dv chunk.
3173 3. If it is big enough, use the top chunk.
3174 4. If request size >= mmap threshold, try to directly mmap this chunk.
3175 5. If available, get memory from system and use it
3177 The ugly goto's here ensure that postaction occurs along all paths.
3181 ensure_initialization(); /* initialize in sys_alloc if not using locks */
3184 if (!PREACTION(gm)) {
3187 if (bytes <= MAX_SMALL_REQUEST) {
3190 nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
3191 idx = small_index(nb);
3192 smallbits = gm->smallmap >> idx;
3194 if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
3196 idx += ~smallbits & 1; /* Uses next bin if idx empty */
3197 b = smallbin_at(gm, idx);
3199 assert(chunksize(p) == small_index2size(idx));
3200 unlink_first_small_chunk(gm, b, p, idx);
3201 set_inuse_and_pinuse(gm, p, small_index2size(idx));
3203 check_malloced_chunk(gm, mem, nb);
3207 else if (nb > gm->dvsize) {
3208 if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
3212 binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
3213 binmap_t leastbit = least_bit(leftbits);
3214 compute_bit2idx(leastbit, i);
3215 b = smallbin_at(gm, i);
3217 assert(chunksize(p) == small_index2size(i));
3218 unlink_first_small_chunk(gm, b, p, i);
3219 rsize = small_index2size(i) - nb;
3220 /* Fit here cannot be remainderless if 4byte sizes */
3221 if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
3222 set_inuse_and_pinuse(gm, p, small_index2size(i));
3224 set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
3225 r = chunk_plus_offset(p, nb);
3226 set_size_and_pinuse_of_free_chunk(r, rsize);
3227 replace_dv(gm, r, rsize);
3230 check_malloced_chunk(gm, mem, nb);
3234 else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
3235 check_malloced_chunk(gm, mem, nb);
3240 else if (bytes >= MAX_REQUEST)
3241 nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
3243 nb = pad_request(bytes);
3244 if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
3245 check_malloced_chunk(gm, mem, nb);
3250 if (nb <= gm->dvsize) {
3251 size_t rsize = gm->dvsize - nb;
3252 mchunkptr p = gm->dv;
3253 if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
3254 mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
3256 set_size_and_pinuse_of_free_chunk(r, rsize);
3257 set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
3259 else { /* exhaust dv */
3260 size_t dvs = gm->dvsize;
3263 set_inuse_and_pinuse(gm, p, dvs);
3266 check_malloced_chunk(gm, mem, nb);
3270 else if (nb < gm->topsize) { /* Split top */
3271 size_t rsize = gm->topsize -= nb;
3272 mchunkptr p = gm->top;
3273 mchunkptr r = gm->top = chunk_plus_offset(p, nb);
3274 r->head = rsize | PINUSE_BIT;
3275 set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
3277 check_top_chunk(gm, gm->top);
3278 check_malloced_chunk(gm, mem, nb);
3282 mem = sys_alloc(gm, nb);
3292 /* ---------------------------- free --------------------------- */
3294 void dlfree(void* mem) {
3296 Consolidate freed chunks with preceding or succeeding bordering
3297 free chunks, if they exist, and then place in a bin. Intermixed
3298 with special cases for top, dv, mmapped chunks, and usage errors.
3302 mchunkptr p = mem2chunk(mem);
3304 mstate fm = get_mstate_for(p);
3305 if (!ok_magic(fm)) {
3306 USAGE_ERROR_ACTION(fm, p);
3311 #endif /* FOOTERS */
3312 if (!PREACTION(fm)) {
3313 check_inuse_chunk(fm, p);
3314 if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
3315 size_t psize = chunksize(p);
3316 mchunkptr next = chunk_plus_offset(p, psize);
3318 size_t prevsize = p->prev_foot;
3319 if (is_mmapped(p)) {
3320 psize += prevsize + MMAP_FOOT_PAD;
3321 if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
3322 fm->footprint -= psize;
3326 mchunkptr prev = chunk_minus_offset(p, prevsize);
3329 if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
3331 unlink_chunk(fm, p, prevsize);
3333 else if ((next->head & INUSE_BITS) == INUSE_BITS) {
3335 set_free_with_pinuse(p, psize, next);
3344 if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
3345 if (!cinuse(next)) { /* consolidate forward */
3346 if (next == fm->top) {
3347 size_t tsize = fm->topsize += psize;
3349 p->head = tsize | PINUSE_BIT;
3354 if (should_trim(fm, tsize))
3358 else if (next == fm->dv) {
3359 size_t dsize = fm->dvsize += psize;
3361 set_size_and_pinuse_of_free_chunk(p, dsize);
3365 size_t nsize = chunksize(next);
3367 unlink_chunk(fm, next, nsize);
3368 set_size_and_pinuse_of_free_chunk(p, psize);
3376 set_free_with_pinuse(p, psize, next);
3378 if (is_small(psize)) {
3379 insert_small_chunk(fm, p, psize);
3380 check_free_chunk(fm, p);
3383 tchunkptr tp = (tchunkptr)p;
3384 insert_large_chunk(fm, tp, psize);
3385 check_free_chunk(fm, p);
3386 if (--fm->release_checks == 0)
3387 release_unused_segments(fm);
3393 USAGE_ERROR_ACTION(fm, p);
3400 #endif /* FOOTERS */
3403 void* dlcalloc(size_t n_elements, size_t elem_size) {
3406 if (n_elements != 0) {
3407 req = n_elements * elem_size;
3408 if (((n_elements | elem_size) & ~(size_t)0xffff) &&
3409 (req / n_elements != elem_size))
3410 req = MAX_SIZE_T; /* force downstream failure on overflow */
3412 mem = dlmalloc(req);
3413 if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
3414 memset(mem, 0, req);
3418 #endif /* !ONLY_MSPACES */
3420 /* ------------ Internal support for realloc, memalign, etc -------------- */
3422 /* Try to realloc; only in-place unless can_move true */
3423 static mchunkptr try_realloc_chunk(mstate m, mchunkptr p, size_t nb,
3426 size_t oldsize = chunksize(p);
3427 mchunkptr next = chunk_plus_offset(p, oldsize);
3428 if (RTCHECK(ok_address(m, p) && ok_inuse(p) &&
3429 ok_next(p, next) && ok_pinuse(next))) {
3430 if (is_mmapped(p)) {
3431 newp = mmap_resize(m, p, nb, can_move);
3433 else if (oldsize >= nb) { /* already big enough */
3434 size_t rsize = oldsize - nb;
3435 if (rsize >= MIN_CHUNK_SIZE) { /* split off remainder */
3436 mchunkptr r = chunk_plus_offset(p, nb);
3437 set_inuse(m, p, nb);
3438 set_inuse(m, r, rsize);
3439 dispose_chunk(m, r, rsize);
3443 else if (next == m->top) { /* extend into top */
3444 if (oldsize + m->topsize > nb) {
3445 size_t newsize = oldsize + m->topsize;
3446 size_t newtopsize = newsize - nb;
3447 mchunkptr newtop = chunk_plus_offset(p, nb);
3448 set_inuse(m, p, nb);
3449 newtop->head = newtopsize |PINUSE_BIT;
3451 m->topsize = newtopsize;
3455 else if (next == m->dv) { /* extend into dv */
3456 size_t dvs = m->dvsize;
3457 if (oldsize + dvs >= nb) {
3458 size_t dsize = oldsize + dvs - nb;
3459 if (dsize >= MIN_CHUNK_SIZE) {
3460 mchunkptr r = chunk_plus_offset(p, nb);
3461 mchunkptr n = chunk_plus_offset(r, dsize);
3462 set_inuse(m, p, nb);
3463 set_size_and_pinuse_of_free_chunk(r, dsize);
3468 else { /* exhaust dv */
3469 size_t newsize = oldsize + dvs;
3470 set_inuse(m, p, newsize);
3477 else if (!cinuse(next)) { /* extend into next free chunk */
3478 size_t nextsize = chunksize(next);
3479 if (oldsize + nextsize >= nb) {
3480 size_t rsize = oldsize + nextsize - nb;
3481 unlink_chunk(m, next, nextsize);
3482 if (rsize < MIN_CHUNK_SIZE) {
3483 size_t newsize = oldsize + nextsize;
3484 set_inuse(m, p, newsize);
3487 mchunkptr r = chunk_plus_offset(p, nb);
3488 set_inuse(m, p, nb);
3489 set_inuse(m, r, rsize);
3490 dispose_chunk(m, r, rsize);
3497 USAGE_ERROR_ACTION(m, chunk2mem(p));
3502 CLIB_NOSANITIZE_ADDR
3503 static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
3505 if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
3506 alignment = MIN_CHUNK_SIZE;
3507 if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
3508 size_t a = MALLOC_ALIGNMENT << 1;
3509 while (a < alignment) a <<= 1;
3512 if (bytes >= MAX_REQUEST - alignment) {
3513 if (m != 0) { /* Test isn't needed but avoids compiler warning */
3514 MALLOC_FAILURE_ACTION;
3518 size_t nb = request2size(bytes);
3519 size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
3520 mem = internal_malloc(m, req);
3522 mchunkptr p = mem2chunk(mem);
3525 if ((((size_t)(mem)) & (alignment - 1)) != 0) { /* misaligned */
3527 Find an aligned spot inside chunk. Since we need to give
3528 back leading space in a chunk of at least MIN_CHUNK_SIZE, if
3529 the first calculation places us at a spot with less than
3530 MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
3531 We've allocated enough total room so that this is always
3534 char* br = (char*)mem2chunk((size_t)(((size_t)((char*)mem + alignment -
3537 char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
3539 mchunkptr newp = (mchunkptr)pos;
3540 size_t leadsize = pos - (char*)(p);
3541 size_t newsize = chunksize(p) - leadsize;
3543 if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */
3544 newp->prev_foot = p->prev_foot + leadsize;
3545 newp->head = newsize;
3547 else { /* Otherwise, give back leader, use the rest */
3548 set_inuse(m, newp, newsize);
3549 set_inuse(m, p, leadsize);
3550 dispose_chunk(m, p, leadsize);
3555 /* Give back spare room at the end */
3556 if (!is_mmapped(p)) {
3557 size_t size = chunksize(p);
3558 if (size > nb + MIN_CHUNK_SIZE) {
3559 size_t remainder_size = size - nb;
3560 mchunkptr remainder = chunk_plus_offset(p, nb);
3561 set_inuse(m, p, nb);
3562 set_inuse(m, remainder, remainder_size);
3563 dispose_chunk(m, remainder, remainder_size);
3568 assert (chunksize(p) >= nb);
3569 assert(((size_t)mem & (alignment - 1)) == 0);
3570 check_inuse_chunk(m, p);
3578 Common support for independent_X routines, handling
3579 all of the combinations that can result.
3581 bit 0 set if all elements are same size (using sizes[0])
3582 bit 1 set if elements should be zeroed
3584 static void** ialloc(mstate m,
3590 size_t element_size; /* chunksize of each element, if all same */
3591 size_t contents_size; /* total size of elements */
3592 size_t array_size; /* request size of pointer array */
3593 void* mem; /* malloced aggregate space */
3594 mchunkptr p; /* corresponding chunk */
3595 size_t remainder_size; /* remaining bytes while splitting */
3596 void** marray; /* either "chunks" or malloced ptr array */
3597 mchunkptr array_chunk; /* chunk for malloced ptr array */
3598 flag_t was_enabled; /* to disable mmap */
3602 ensure_initialization();
3603 /* compute array length, if needed */
3605 if (n_elements == 0)
3606 return chunks; /* nothing to do */
3611 /* if empty req, must still return chunk representing empty array */
3612 if (n_elements == 0)
3613 return (void**)internal_malloc(m, 0);
3615 array_size = request2size(n_elements * (sizeof(void*)));
3618 /* compute total element size */
3619 if (opts & 0x1) { /* all-same-size */
3620 element_size = request2size(*sizes);
3621 contents_size = n_elements * element_size;
3623 else { /* add up all the sizes */
3626 for (i = 0; i != n_elements; ++i)
3627 contents_size += request2size(sizes[i]);
3630 size = contents_size + array_size;
3633 Allocate the aggregate chunk. First disable direct-mmapping so
3634 malloc won't use it, since we would not be able to later
3635 free/realloc space internal to a segregated mmap region.
3637 was_enabled = use_mmap(m);
3639 mem = internal_malloc(m, size - CHUNK_OVERHEAD);
3645 if (PREACTION(m)) return 0;
3647 remainder_size = chunksize(p);
3649 assert(!is_mmapped(p));
3651 if (opts & 0x2) { /* optionally clear the elements */
3652 memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);
3655 /* If not provided, allocate the pointer array as final part of chunk */
3657 size_t array_chunk_size;
3658 array_chunk = chunk_plus_offset(p, contents_size);
3659 array_chunk_size = remainder_size - contents_size;
3660 marray = (void**) (chunk2mem(array_chunk));
3661 set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);
3662 remainder_size = contents_size;
3665 /* split out elements */
3666 for (i = 0; ; ++i) {
3667 marray[i] = chunk2mem(p);
3668 if (i != n_elements-1) {
3669 if (element_size != 0)
3670 size = element_size;
3672 size = request2size(sizes[i]);
3673 remainder_size -= size;
3674 set_size_and_pinuse_of_inuse_chunk(m, p, size);
3675 p = chunk_plus_offset(p, size);
3677 else { /* the final element absorbs any overallocation slop */
3678 set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);
3684 if (marray != chunks) {
3685 /* final element must have exactly exhausted chunk */
3686 if (element_size != 0) {
3687 assert(remainder_size == element_size);
3690 assert(remainder_size == request2size(sizes[i]));
3692 check_inuse_chunk(m, mem2chunk(marray));
3694 for (i = 0; i != n_elements; ++i)
3695 check_inuse_chunk(m, mem2chunk(marray[i]));
3703 /* Try to free all pointers in the given array.
3704 Note: this could be made faster, by delaying consolidation,
3705 at the price of disabling some user integrity checks, We
3706 still optimize some consolidations by combining adjacent
3707 chunks before freeing, which will occur often if allocated
3708 with ialloc or the array is sorted.
3710 static size_t internal_bulk_free(mstate m, void* array[], size_t nelem) {
3712 if (!PREACTION(m)) {
3714 void** fence = &(array[nelem]);
3715 for (a = array; a != fence; ++a) {
3718 mchunkptr p = mem2chunk(mem);
3719 size_t psize = chunksize(p);
3721 if (get_mstate_for(p) != m) {
3726 check_inuse_chunk(m, p);
3728 if (RTCHECK(ok_address(m, p) && ok_inuse(p))) {
3729 void ** b = a + 1; /* try to merge with next chunk */
3730 mchunkptr next = next_chunk(p);
3731 if (b != fence && *b == chunk2mem(next)) {
3732 size_t newsize = chunksize(next) + psize;
3733 set_inuse(m, p, newsize);
3737 dispose_chunk(m, p, psize);
3740 CORRUPTION_ERROR_ACTION(m);
3745 if (should_trim(m, m->topsize))
3753 #if MALLOC_INSPECT_ALL
3754 static void internal_inspect_all(mstate m,
3755 void(*handler)(void *start,
3758 void* callback_arg),
3760 if (is_initialized(m)) {
3761 mchunkptr top = m->top;
3763 for (s = &m->seg; s != 0; s = s->next) {
3764 mchunkptr q = align_as_chunk(s->base);
3765 while (segment_holds(s, q) && q->head != FENCEPOST_HEAD) {
3766 mchunkptr next = next_chunk(q);
3767 size_t sz = chunksize(q);
3771 used = sz - CHUNK_OVERHEAD; /* must not be mmapped */
3772 start = chunk2mem(q);
3776 if (is_small(sz)) { /* offset by possible bookkeeping */
3777 start = (void*)((char*)q + sizeof(struct malloc_chunk));
3780 start = (void*)((char*)q + sizeof(struct malloc_tree_chunk));
3783 if (start < (void*)next) /* skip if all space is bookkeeping */
3784 handler(start, next, used, arg);
3792 #endif /* MALLOC_INSPECT_ALL */
3794 /* ------------------ Exported realloc, memalign, etc -------------------- */
3798 void* dlrealloc(void* oldmem, size_t bytes) {
3801 mem = dlmalloc(bytes);
3803 else if (bytes >= MAX_REQUEST) {
3804 MALLOC_FAILURE_ACTION;
3806 #ifdef REALLOC_ZERO_BYTES_FREES
3807 else if (bytes == 0) {
3810 #endif /* REALLOC_ZERO_BYTES_FREES */
3812 size_t nb = request2size(bytes);
3813 mchunkptr oldp = mem2chunk(oldmem);
3817 mstate m = get_mstate_for(oldp);
3819 USAGE_ERROR_ACTION(m, oldmem);
3822 #endif /* FOOTERS */
3823 if (!PREACTION(m)) {
3824 mchunkptr newp = try_realloc_chunk(m, oldp, nb, 1);
3827 check_inuse_chunk(m, newp);
3828 mem = chunk2mem(newp);
3831 mem = internal_malloc(m, bytes);
3833 size_t oc = chunksize(oldp) - overhead_for(oldp);
3834 memcpy(mem, oldmem, (oc < bytes)? oc : bytes);
3835 internal_free(m, oldmem);
3843 void* dlrealloc_in_place(void* oldmem, size_t bytes) {
3846 if (bytes >= MAX_REQUEST) {
3847 MALLOC_FAILURE_ACTION;
3850 size_t nb = request2size(bytes);
3851 mchunkptr oldp = mem2chunk(oldmem);
3855 mstate m = get_mstate_for(oldp);
3857 USAGE_ERROR_ACTION(m, oldmem);
3860 #endif /* FOOTERS */
3861 if (!PREACTION(m)) {
3862 mchunkptr newp = try_realloc_chunk(m, oldp, nb, 0);
3865 check_inuse_chunk(m, newp);
3874 void* dlmemalign(size_t alignment, size_t bytes) {
3875 if (alignment <= MALLOC_ALIGNMENT) {
3876 return dlmalloc(bytes);
3878 return internal_memalign(gm, alignment, bytes);
3881 int dlposix_memalign(void** pp, size_t alignment, size_t bytes) {
3883 if (alignment == MALLOC_ALIGNMENT)
3884 mem = dlmalloc(bytes);
3886 size_t d = alignment / sizeof(void*);
3887 size_t r = alignment % sizeof(void*);
3888 if (r != 0 || d == 0 || (d & (d-SIZE_T_ONE)) != 0)
3890 else if (bytes <= MAX_REQUEST - alignment) {
3891 if (alignment < MIN_CHUNK_SIZE)
3892 alignment = MIN_CHUNK_SIZE;
3893 mem = internal_memalign(gm, alignment, bytes);
3904 void* dlvalloc(size_t bytes) {
3906 ensure_initialization();
3907 pagesz = mparams.page_size;
3908 return dlmemalign(pagesz, bytes);
3911 void* dlpvalloc(size_t bytes) {
3913 ensure_initialization();
3914 pagesz = mparams.page_size;
3915 return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));
3918 void** dlindependent_calloc(size_t n_elements, size_t elem_size,
3920 size_t sz = elem_size; /* serves as 1-element array */
3921 return ialloc(gm, n_elements, &sz, 3, chunks);
3924 void** dlindependent_comalloc(size_t n_elements, size_t sizes[],
3926 return ialloc(gm, n_elements, sizes, 0, chunks);
3929 size_t dlbulk_free(void* array[], size_t nelem) {
3930 return internal_bulk_free(gm, array, nelem);
3933 #if MALLOC_INSPECT_ALL
3934 void dlmalloc_inspect_all(void(*handler)(void *start,
3937 void* callback_arg),
3939 ensure_initialization();
3940 if (!PREACTION(gm)) {
3941 internal_inspect_all(gm, handler, arg);
3945 #endif /* MALLOC_INSPECT_ALL */
3947 int dlmalloc_trim(size_t pad) {
3949 ensure_initialization();
3950 if (!PREACTION(gm)) {
3951 result = sys_trim(gm, pad);
3957 size_t dlmalloc_footprint(void) {
3958 return gm->footprint;
3961 size_t dlmalloc_max_footprint(void) {
3962 return gm->max_footprint;
3965 size_t dlmalloc_footprint_limit(void) {
3966 size_t maf = gm->footprint_limit;
3967 return maf == 0 ? MAX_SIZE_T : maf;
3970 size_t dlmalloc_set_footprint_limit(size_t bytes) {
3971 size_t result; /* invert sense of 0 */
3973 result = granularity_align(1); /* Use minimal size */
3974 if (bytes == MAX_SIZE_T)
3975 result = 0; /* disable */
3977 result = granularity_align(bytes);
3978 return gm->footprint_limit = result;
3982 struct dlmallinfo dlmallinfo(void) {
3983 return internal_mallinfo(gm);
3985 #endif /* NO_MALLINFO */
3987 #if !NO_MALLOC_STATS
3988 void dlmalloc_stats() {
3989 internal_malloc_stats(gm);
3991 #endif /* NO_MALLOC_STATS */
3993 int dlmallopt(int param_number, int value) {
3994 return change_mparam(param_number, value);
3997 size_t dlmalloc_usable_size(void* mem) {
3999 mchunkptr p = mem2chunk(mem);
4001 return chunksize(p) - overhead_for(p);
4006 #endif /* !ONLY_MSPACES */
4008 /* ----------------------------- user mspaces ---------------------------- */
4012 static mstate init_user_mstate(char* tbase, size_t tsize) {
4013 size_t msize = pad_request(sizeof(struct malloc_state));
4015 mchunkptr msp = align_as_chunk(tbase);
4016 mstate m = (mstate)(chunk2mem(msp));
4017 memset(m, 0, msize);
4018 (void)INITIAL_LOCK(&m->mutex);
4019 msp->head = (msize|INUSE_BITS);
4020 m->seg.base = m->least_addr = tbase;
4021 m->seg.size = m->footprint = m->max_footprint = tsize;
4022 m->magic = mparams.magic;
4023 m->release_checks = MAX_RELEASE_CHECK_RATE;
4024 m->mflags = mparams.default_mflags;
4027 disable_contiguous(m);
4029 mn = next_chunk(mem2chunk(m));
4030 init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
4031 check_top_chunk(m, m->top);
4035 mspace create_mspace(size_t capacity, int locked) {
4038 ensure_initialization();
4039 msize = pad_request(sizeof(struct malloc_state));
4040 if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4041 size_t rs = ((capacity == 0)? mparams.granularity :
4042 (capacity + TOP_FOOT_SIZE + msize));
4043 size_t tsize = granularity_align(rs);
4044 char* tbase = (char*)(CALL_MMAP(tsize));
4045 if (tbase != CMFAIL) {
4046 m = init_user_mstate(tbase, tsize);
4047 m->seg.sflags = USE_MMAP_BIT;
4048 set_lock(m, locked);
4054 mspace create_mspace_with_base(void* base, size_t capacity, int locked) {
4057 ensure_initialization();
4058 msize = pad_request(sizeof(struct malloc_state));
4059 if (capacity > msize + TOP_FOOT_SIZE &&
4060 capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4061 m = init_user_mstate((char*)base, capacity);
4062 m->seg.sflags = EXTERN_BIT;
4063 set_lock(m, locked);
4068 int mspace_track_large_chunks(mspace msp, int enable) {
4070 mstate ms = (mstate)msp;
4071 if (!PREACTION(ms)) {
4072 if (!use_mmap(ms)) {
4085 CLIB_NOSANITIZE_ADDR
4086 size_t destroy_mspace(mspace msp) {
4088 mstate ms = (mstate)msp;
4090 msegmentptr sp = &ms->seg;
4091 (void)DESTROY_LOCK(&ms->mutex); /* destroy before unmapped */
4093 char* base = sp->base;
4094 size_t size = sp->size;
4095 flag_t flag = sp->sflags;
4096 (void)base; /* placate people compiling -Wunused-variable */
4098 if ((flag & USE_MMAP_BIT) && !(flag & EXTERN_BIT) &&
4099 CALL_MUNMAP(base, size) == 0)
4104 USAGE_ERROR_ACTION(ms,ms);
4109 void mspace_get_address_and_size (mspace msp, char **addrp, size_t *sizep)
4115 this_seg = &ms->seg;
4117 *addrp = this_seg->base;
4118 *sizep = this_seg->size;
4121 CLIB_NOSANITIZE_ADDR __clib_export
4122 int mspace_is_heap_object (mspace msp, void *p)
4130 this_seg = &ms->seg;
4135 base = this_seg->base;
4136 if (pp >= base && pp < (base + this_seg->size))
4138 this_seg = this_seg->next;
4141 if (pp > ms->least_addr && pp <= ms->least_addr + ms->footprint)
4147 CLIB_NOSANITIZE_ADDR
4148 void *mspace_least_addr (mspace msp)
4150 mstate ms = (mstate) msp;
4151 return (void *) ms->least_addr;
4154 void mspace_disable_expand (mspace msp)
4156 mstate ms = (mstate)msp;
4158 disable_expand (ms);
4161 CLIB_NOSANITIZE_ADDR
4162 int mspace_enable_disable_trace (mspace msp, int enable)
4164 mstate ms = (mstate)msp;
4165 int was_enabled = 0;
4175 return (was_enabled);
4178 CLIB_NOSANITIZE_ADDR
4179 int mspace_is_traced (mspace msp)
4181 mstate ms = (mstate)msp;
4188 CLIB_NOSANITIZE_ADDR __clib_export
4189 void* mspace_get_aligned (mspace msp,
4190 unsigned long n_user_data_bytes,
4191 unsigned long align,
4192 unsigned long align_offset) {
4194 unsigned long searchp;
4195 unsigned *wwp; /* "where's Waldo" pointer */
4196 mstate ms = (mstate)msp;
4199 * Allocate space for the "Where's Waldo?" pointer
4200 * the base of the dlmalloc object
4202 n_user_data_bytes += sizeof(unsigned);
4205 * Alignment requests less than the size of an mmx vector are ignored
4207 if (align < sizeof (uword)) {
4208 rv = mspace_malloc (msp, n_user_data_bytes);
4212 if (use_trace(ms)) {
4213 mchunkptr p = mem2chunk(rv);
4214 size_t psize = chunksize(p);
4216 mheap_get_trace ((unsigned long)rv + sizeof (unsigned), psize);
4219 wwp = (unsigned *)rv;
4221 rv += sizeof (unsigned);
4227 * Alignment requests greater than 4K must be at offset zero,
4228 * and must be freed using mspace_free_no_offset - or never freed -
4229 * since the "Where's Waldo?" pointer would waste too much space.
4231 * Waldo is the address of the chunk of memory returned by mspace_malloc,
4232 * which we need later to call mspace_free...
4234 if (align > 4<<10 || align_offset == ~0UL) {
4235 n_user_data_bytes -= sizeof(unsigned);
4236 assert(align_offset == 0);
4237 rv = internal_memalign(ms, (size_t)align, n_user_data_bytes);
4239 /* Trace the allocation */
4240 if (rv && use_trace(ms)) {
4241 mchunkptr p = mem2chunk(rv);
4242 size_t psize = chunksize(p);
4243 mheap_get_trace ((unsigned long)rv, psize);
4248 align = clib_max (align, MALLOC_ALIGNMENT);
4249 align = max_pow2 (align);
4251 /* Correct align offset to be smaller than alignment. */
4252 align_offset &= (align - 1);
4254 n_user_data_bytes += align;
4255 rv = mspace_malloc (msp, n_user_data_bytes);
4260 /* Honor the alignment request */
4261 searchp = (unsigned long)(rv + sizeof (unsigned));
4263 #if 0 /* this is the idea... */
4264 while ((searchp + align_offset) % align)
4269 unsigned long where_now, delta;
4271 where_now = (searchp + align_offset) % align;
4272 delta = align - where_now;
4277 wwp = (unsigned *)(searchp - sizeof(unsigned));
4278 *wwp = (searchp - (((unsigned long) rv) + sizeof (*wwp)));
4279 assert (*wwp < align);
4281 if (use_trace(ms)) {
4282 mchunkptr p = mem2chunk(rv);
4283 size_t psize = chunksize(p);
4284 mheap_get_trace (searchp, psize);
4286 return (void *) searchp;
4289 CLIB_NOSANITIZE_ADDR __clib_export
4290 void mspace_put (mspace msp, void *p_arg)
4292 char *object_header;
4294 mstate ms = (mstate)msp;
4296 /* Find the object header delta */
4297 wwp = (unsigned *)p_arg;
4300 /* Recover the dlmalloc object pointer */
4301 object_header = (char *)wwp;
4302 object_header -= *wwp;
4304 /* Tracing (if enabled) */
4307 mchunkptr p = mem2chunk(object_header);
4308 size_t psize = chunksize(p);
4310 mheap_put_trace ((unsigned long)p_arg, psize);
4313 #if CLIB_DEBUG > 0 && !defined(CLIB_SANITIZE_ADDR)
4314 /* Poison the object */
4316 size_t psize = mspace_usable_size (object_header);
4317 memset (object_header, 0x13, psize);
4321 /* And free it... */
4322 mspace_free (msp, object_header);
4325 void mspace_put_no_offset (mspace msp, void *p_arg)
4327 mstate ms = (mstate)msp;
4331 mchunkptr p = mem2chunk(p_arg);
4332 size_t psize = chunksize(p);
4334 mheap_put_trace ((unsigned long)p_arg, psize);
4336 mspace_free (msp, p_arg);
4339 CLIB_NOSANITIZE_ADDR __clib_export
4340 size_t mspace_usable_size_with_delta (const void *p)
4343 char *object_header;
4346 /* Find the object header delta */
4347 wwp = (unsigned *)p;
4350 /* Recover the dlmalloc object pointer */
4351 object_header = (char *)wwp;
4352 object_header -= *wwp;
4354 usable_size = mspace_usable_size (object_header);
4355 /* account for the offset and the size of the offset... */
4356 usable_size -= (*wwp + sizeof (*wwp));
4361 mspace versions of routines are near-clones of the global
4362 versions. This is not so nice but better than the alternatives.
4365 CLIB_NOSANITIZE_ADDR
4366 void* mspace_malloc(mspace msp, size_t bytes) {
4367 mstate ms = (mstate)msp;
4368 if (!ok_magic(ms)) {
4369 USAGE_ERROR_ACTION(ms,ms);
4372 if (!PREACTION(ms)) {
4375 if (bytes <= MAX_SMALL_REQUEST) {
4378 nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
4379 idx = small_index(nb);
4380 smallbits = ms->smallmap >> idx;
4382 if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
4384 idx += ~smallbits & 1; /* Uses next bin if idx empty */
4385 b = smallbin_at(ms, idx);
4387 assert(chunksize(p) == small_index2size(idx));
4388 unlink_first_small_chunk(ms, b, p, idx);
4389 set_inuse_and_pinuse(ms, p, small_index2size(idx));
4391 check_malloced_chunk(ms, mem, nb);
4395 else if (nb > ms->dvsize) {
4396 if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
4400 binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4401 binmap_t leastbit = least_bit(leftbits);
4402 compute_bit2idx(leastbit, i);
4403 b = smallbin_at(ms, i);
4405 assert(chunksize(p) == small_index2size(i));
4406 unlink_first_small_chunk(ms, b, p, i);
4407 rsize = small_index2size(i) - nb;
4408 /* Fit here cannot be remainderless if 4byte sizes */
4409 if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4410 set_inuse_and_pinuse(ms, p, small_index2size(i));
4412 set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4413 r = chunk_plus_offset(p, nb);
4414 set_size_and_pinuse_of_free_chunk(r, rsize);
4415 replace_dv(ms, r, rsize);
4418 check_malloced_chunk(ms, mem, nb);
4422 else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
4423 check_malloced_chunk(ms, mem, nb);
4428 else if (bytes >= MAX_REQUEST)
4429 nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
4431 nb = pad_request(bytes);
4432 if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
4433 check_malloced_chunk(ms, mem, nb);
4438 if (nb <= ms->dvsize) {
4439 size_t rsize = ms->dvsize - nb;
4440 mchunkptr p = ms->dv;
4441 if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4442 mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
4444 set_size_and_pinuse_of_free_chunk(r, rsize);
4445 set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4447 else { /* exhaust dv */
4448 size_t dvs = ms->dvsize;
4451 set_inuse_and_pinuse(ms, p, dvs);
4454 check_malloced_chunk(ms, mem, nb);
4458 else if (nb < ms->topsize) { /* Split top */
4459 size_t rsize = ms->topsize -= nb;
4460 mchunkptr p = ms->top;
4461 mchunkptr r = ms->top = chunk_plus_offset(p, nb);
4462 r->head = rsize | PINUSE_BIT;
4463 set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4465 check_top_chunk(ms, ms->top);
4466 check_malloced_chunk(ms, mem, nb);
4470 mem = sys_alloc(ms, nb);
4480 CLIB_NOSANITIZE_ADDR
4481 void mspace_free(mspace msp, void* mem) {
4483 mchunkptr p = mem2chunk(mem);
4485 mstate fm = get_mstate_for(p);
4486 (void)msp; /* placate people compiling -Wunused */
4488 mstate fm = (mstate)msp;
4489 #endif /* FOOTERS */
4490 if (!ok_magic(fm)) {
4491 USAGE_ERROR_ACTION(fm, p);
4494 if (!PREACTION(fm)) {
4495 check_inuse_chunk(fm, p);
4496 if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
4497 size_t psize = chunksize(p);
4498 mchunkptr next = chunk_plus_offset(p, psize);
4500 size_t prevsize = p->prev_foot;
4501 if (is_mmapped(p)) {
4502 psize += prevsize + MMAP_FOOT_PAD;
4503 if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4504 fm->footprint -= psize;
4508 mchunkptr prev = chunk_minus_offset(p, prevsize);
4511 if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4513 unlink_chunk(fm, p, prevsize);
4515 else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4517 set_free_with_pinuse(p, psize, next);
4526 if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
4527 if (!cinuse(next)) { /* consolidate forward */
4528 if (next == fm->top) {
4529 size_t tsize = fm->topsize += psize;
4531 p->head = tsize | PINUSE_BIT;
4536 if (should_trim(fm, tsize))
4540 else if (next == fm->dv) {
4541 size_t dsize = fm->dvsize += psize;
4543 set_size_and_pinuse_of_free_chunk(p, dsize);
4547 size_t nsize = chunksize(next);
4549 unlink_chunk(fm, next, nsize);
4550 set_size_and_pinuse_of_free_chunk(p, psize);
4558 set_free_with_pinuse(p, psize, next);
4560 if (is_small(psize)) {
4561 insert_small_chunk(fm, p, psize);
4562 check_free_chunk(fm, p);
4565 tchunkptr tp = (tchunkptr)p;
4566 insert_large_chunk(fm, tp, psize);
4567 check_free_chunk(fm, p);
4568 if (--fm->release_checks == 0)
4569 release_unused_segments(fm);
4575 USAGE_ERROR_ACTION(fm, p);
4582 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
4585 mstate ms = (mstate)msp;
4586 if (!ok_magic(ms)) {
4587 USAGE_ERROR_ACTION(ms,ms);
4590 if (n_elements != 0) {
4591 req = n_elements * elem_size;
4592 if (((n_elements | elem_size) & ~(size_t)0xffff) &&
4593 (req / n_elements != elem_size))
4594 req = MAX_SIZE_T; /* force downstream failure on overflow */
4596 mem = internal_malloc(ms, req);
4597 if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
4598 memset(mem, 0, req);
4602 void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
4605 mem = mspace_malloc(msp, bytes);
4607 else if (bytes >= MAX_REQUEST) {
4608 MALLOC_FAILURE_ACTION;
4610 #ifdef REALLOC_ZERO_BYTES_FREES
4611 else if (bytes == 0) {
4612 mspace_free(msp, oldmem);
4614 #endif /* REALLOC_ZERO_BYTES_FREES */
4616 size_t nb = request2size(bytes);
4617 mchunkptr oldp = mem2chunk(oldmem);
4619 mstate m = (mstate)msp;
4621 mstate m = get_mstate_for(oldp);
4623 USAGE_ERROR_ACTION(m, oldmem);
4626 #endif /* FOOTERS */
4627 if (!PREACTION(m)) {
4628 mchunkptr newp = try_realloc_chunk(m, oldp, nb, 1);
4631 check_inuse_chunk(m, newp);
4632 mem = chunk2mem(newp);
4635 mem = mspace_malloc(m, bytes);
4637 size_t oc = chunksize(oldp) - overhead_for(oldp);
4638 memcpy(mem, oldmem, (oc < bytes)? oc : bytes);
4639 mspace_free(m, oldmem);
4647 void* mspace_realloc_in_place(mspace msp, void* oldmem, size_t bytes) {
4650 if (bytes >= MAX_REQUEST) {
4651 MALLOC_FAILURE_ACTION;
4654 size_t nb = request2size(bytes);
4655 mchunkptr oldp = mem2chunk(oldmem);
4657 mstate m = (mstate)msp;
4659 mstate m = get_mstate_for(oldp);
4660 (void)msp; /* placate people compiling -Wunused */
4662 USAGE_ERROR_ACTION(m, oldmem);
4665 #endif /* FOOTERS */
4666 if (!PREACTION(m)) {
4667 mchunkptr newp = try_realloc_chunk(m, oldp, nb, 0);
4670 check_inuse_chunk(m, newp);
4679 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
4680 mstate ms = (mstate)msp;
4681 if (!ok_magic(ms)) {
4682 USAGE_ERROR_ACTION(ms,ms);
4685 if (alignment <= MALLOC_ALIGNMENT)
4686 return mspace_malloc(msp, bytes);
4687 return internal_memalign(ms, alignment, bytes);
4690 void** mspace_independent_calloc(mspace msp, size_t n_elements,
4691 size_t elem_size, void* chunks[]) {
4692 size_t sz = elem_size; /* serves as 1-element array */
4693 mstate ms = (mstate)msp;
4694 if (!ok_magic(ms)) {
4695 USAGE_ERROR_ACTION(ms,ms);
4698 return ialloc(ms, n_elements, &sz, 3, chunks);
4701 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
4702 size_t sizes[], void* chunks[]) {
4703 mstate ms = (mstate)msp;
4704 if (!ok_magic(ms)) {
4705 USAGE_ERROR_ACTION(ms,ms);
4708 return ialloc(ms, n_elements, sizes, 0, chunks);
4711 size_t mspace_bulk_free(mspace msp, void* array[], size_t nelem) {
4712 return internal_bulk_free((mstate)msp, array, nelem);
4715 #if MALLOC_INSPECT_ALL
4716 void mspace_inspect_all(mspace msp,
4717 void(*handler)(void *start,
4720 void* callback_arg),
4722 mstate ms = (mstate)msp;
4724 if (!PREACTION(ms)) {
4725 internal_inspect_all(ms, handler, arg);
4730 USAGE_ERROR_ACTION(ms,ms);
4733 #endif /* MALLOC_INSPECT_ALL */
4735 int mspace_trim(mspace msp, size_t pad) {
4737 mstate ms = (mstate)msp;
4739 if (!PREACTION(ms)) {
4740 result = sys_trim(ms, pad);
4745 USAGE_ERROR_ACTION(ms,ms);
4750 #if !NO_MALLOC_STATS
4751 void mspace_malloc_stats(mspace msp) {
4752 mstate ms = (mstate)msp;
4754 internal_malloc_stats(ms);
4757 USAGE_ERROR_ACTION(ms,ms);
4760 #endif /* NO_MALLOC_STATS */
4762 size_t mspace_footprint(mspace msp) {
4764 mstate ms = (mstate)msp;
4766 result = ms->footprint;
4769 USAGE_ERROR_ACTION(ms,ms);
4774 size_t mspace_max_footprint(mspace msp) {
4776 mstate ms = (mstate)msp;
4778 result = ms->max_footprint;
4781 USAGE_ERROR_ACTION(ms,ms);
4786 size_t mspace_footprint_limit(mspace msp) {
4788 mstate ms = (mstate)msp;
4790 size_t maf = ms->footprint_limit;
4791 result = (maf == 0) ? MAX_SIZE_T : maf;
4794 USAGE_ERROR_ACTION(ms,ms);
4799 size_t mspace_set_footprint_limit(mspace msp, size_t bytes) {
4801 mstate ms = (mstate)msp;
4804 result = granularity_align(1); /* Use minimal size */
4805 if (bytes == MAX_SIZE_T)
4806 result = 0; /* disable */
4808 result = granularity_align(bytes);
4809 ms->footprint_limit = result;
4812 USAGE_ERROR_ACTION(ms,ms);
4818 CLIB_NOSANITIZE_ADDR
4819 struct dlmallinfo mspace_mallinfo(mspace msp) {
4820 mstate ms = (mstate)msp;
4821 if (!ok_magic(ms)) {
4822 USAGE_ERROR_ACTION(ms,ms);
4824 return internal_mallinfo(ms);
4826 #endif /* NO_MALLINFO */
4828 CLIB_NOSANITIZE_ADDR
4829 size_t mspace_usable_size(const void* mem) {
4831 mchunkptr p = mem2chunk(mem);
4833 return chunksize(p) - overhead_for(p);
4838 int mspace_mallopt(int param_number, int value) {
4839 return change_mparam(param_number, value);
4842 #endif /* MSPACES */
4845 /* -------------------- Alternative MORECORE functions ------------------- */
4848 Guidelines for creating a custom version of MORECORE:
4850 * For best performance, MORECORE should allocate in multiples of pagesize.
4851 * MORECORE may allocate more memory than requested. (Or even less,
4852 but this will usually result in a malloc failure.)
4853 * MORECORE must not allocate memory when given argument zero, but
4854 instead return one past the end address of memory from previous
4856 * For best performance, consecutive calls to MORECORE with positive
4857 arguments should return increasing addresses, indicating that
4858 space has been contiguously extended.
4859 * Even though consecutive calls to MORECORE need not return contiguous
4860 addresses, it must be OK for malloc'ed chunks to span multiple
4861 regions in those cases where they do happen to be contiguous.
4862 * MORECORE need not handle negative arguments -- it may instead
4863 just return MFAIL when given negative arguments.
4864 Negative arguments are always multiples of pagesize. MORECORE
4865 must not misinterpret negative args as large positive unsigned
4866 args. You can suppress all such calls from even occurring by defining
4867 MORECORE_CANNOT_TRIM,
4869 As an example alternative MORECORE, here is a custom allocator
4870 kindly contributed for pre-OSX macOS. It uses virtually but not
4871 necessarily physically contiguous non-paged memory (locked in,
4872 present and won't get swapped out). You can use it by uncommenting
4873 this section, adding some #includes, and setting up the appropriate
4876 #define MORECORE osMoreCore
4878 There is also a shutdown routine that should somehow be called for
4879 cleanup upon program exit.
4881 #define MAX_POOL_ENTRIES 100
4882 #define MINIMUM_MORECORE_SIZE (64 * 1024U)
4883 static int next_os_pool;
4884 void *our_os_pools[MAX_POOL_ENTRIES];
4886 void *osMoreCore(int size)
4889 static void *sbrk_top = 0;
4893 if (size < MINIMUM_MORECORE_SIZE)
4894 size = MINIMUM_MORECORE_SIZE;
4895 if (CurrentExecutionLevel() == kTaskLevel)
4896 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4899 return (void *) MFAIL;
4901 // save ptrs so they can be freed during cleanup
4902 our_os_pools[next_os_pool] = ptr;
4904 ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4905 sbrk_top = (char *) ptr + size;
4910 // we don't currently support shrink behavior
4911 return (void *) MFAIL;
4919 // cleanup any allocated memory pools
4920 // called as last thing before shutting down driver
4922 void osCleanupMem(void)
4926 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4929 PoolDeallocate(*ptr);
4937 /* -----------------------------------------------------------------------
4939 v2.8.6 Wed Aug 29 06:57:58 2012 Doug Lea
4940 * fix bad comparison in dlposix_memalign
4941 * don't reuse adjusted asize in sys_alloc
4942 * add LOCK_AT_FORK -- thanks to Kirill Artamonov for the suggestion
4943 * reduce compiler warnings -- thanks to all who reported/suggested these
4945 v2.8.5 Sun May 22 10:26:02 2011 Doug Lea (dl at gee)
4946 * Always perform unlink checks unless INSECURE
4947 * Add posix_memalign.
4948 * Improve realloc to expand in more cases; expose realloc_in_place.
4949 Thanks to Peter Buhr for the suggestion.
4950 * Add footprint_limit, inspect_all, bulk_free. Thanks
4951 to Barry Hayes and others for the suggestions.
4952 * Internal refactorings to avoid calls while holding locks
4953 * Use non-reentrant locks by default. Thanks to Roland McGrath
4955 * Small fixes to mspace_destroy, reset_on_error.
4956 * Various configuration extensions/changes. Thanks
4957 to all who contributed these.
4959 V2.8.4a Thu Apr 28 14:39:43 2011 (dl at gee.cs.oswego.edu)
4960 * Update Creative Commons URL
4962 V2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee)
4963 * Use zeros instead of prev foot for is_mmapped
4964 * Add mspace_track_large_chunks; thanks to Jean Brouwers
4965 * Fix set_inuse in internal_realloc; thanks to Jean Brouwers
4966 * Fix insufficient sys_alloc padding when using 16byte alignment
4967 * Fix bad error check in mspace_footprint
4968 * Adaptations for ptmalloc; thanks to Wolfram Gloger.
4969 * Reentrant spin locks; thanks to Earl Chew and others
4970 * Win32 improvements; thanks to Niall Douglas and Earl Chew
4971 * Add NO_SEGMENT_TRAVERSAL and MAX_RELEASE_CHECK_RATE options
4972 * Extension hook in malloc_state
4973 * Various small adjustments to reduce warnings on some compilers
4974 * Various configuration extensions/changes for more platforms. Thanks
4975 to all who contributed these.
4977 V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee)
4978 * Add max_footprint functions
4979 * Ensure all appropriate literals are size_t
4980 * Fix conditional compilation problem for some #define settings
4981 * Avoid concatenating segments with the one provided
4982 in create_mspace_with_base
4983 * Rename some variables to avoid compiler shadowing warnings
4984 * Use explicit lock initialization.
4985 * Better handling of sbrk interference.
4986 * Simplify and fix segment insertion, trimming and mspace_destroy
4987 * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
4988 * Thanks especially to Dennis Flanagan for help on these.
4990 V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee)
4991 * Fix memalign brace error.
4993 V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee)
4994 * Fix improper #endif nesting in C++
4995 * Add explicit casts needed for C++
4997 V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee)
4998 * Use trees for large bins
5000 * Use segments to unify sbrk-based and mmap-based system allocation,
5001 removing need for emulation on most platforms without sbrk.
5002 * Default safety checks
5003 * Optional footer checks. Thanks to William Robertson for the idea.
5004 * Internal code refactoring
5005 * Incorporate suggestions and platform-specific changes.
5006 Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
5007 Aaron Bachmann, Emery Berger, and others.
5008 * Speed up non-fastbin processing enough to remove fastbins.
5009 * Remove useless cfree() to avoid conflicts with other apps.
5010 * Remove internal memcpy, memset. Compilers handle builtins better.
5011 * Remove some options that no one ever used and rename others.
5013 V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee)
5014 * Fix malloc_state bitmap array misdeclaration
5016 V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
5017 * Allow tuning of FIRST_SORTED_BIN_SIZE
5018 * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
5019 * Better detection and support for non-contiguousness of MORECORE.
5020 Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
5021 * Bypass most of malloc if no frees. Thanks To Emery Berger.
5022 * Fix freeing of old top non-contiguous chunk im sysmalloc.
5023 * Raised default trim and map thresholds to 256K.
5024 * Fix mmap-related #defines. Thanks to Lubos Lunak.
5025 * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
5026 * Branch-free bin calculation
5027 * Default trim and mmap thresholds now 256K.
5029 V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
5030 * Introduce independent_comalloc and independent_calloc.
5031 Thanks to Michael Pachos for motivation and help.
5032 * Make optional .h file available
5033 * Allow > 2GB requests on 32bit systems.
5034 * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
5035 Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
5037 * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
5039 * memalign: check alignment arg
5040 * realloc: don't try to shift chunks backwards, since this
5041 leads to more fragmentation in some programs and doesn't
5042 seem to help in any others.
5043 * Collect all cases in malloc requiring system memory into sysmalloc
5044 * Use mmap as backup to sbrk
5045 * Place all internal state in malloc_state
5046 * Introduce fastbins (although similar to 2.5.1)
5047 * Many minor tunings and cosmetic improvements
5048 * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
5049 * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
5050 Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
5051 * Include errno.h to support default failure action.
5053 V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
5054 * return null for negative arguments
5055 * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5056 * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5057 (e.g. WIN32 platforms)
5058 * Cleanup header file inclusion for WIN32 platforms
5059 * Cleanup code to avoid Microsoft Visual C++ compiler complaints
5060 * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5061 memory allocation routines
5062 * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5063 * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5064 usage of 'assert' in non-WIN32 code
5065 * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5067 * Always call 'fREe()' rather than 'free()'
5069 V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
5070 * Fixed ordering problem with boundary-stamping
5072 V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
5073 * Added pvalloc, as recommended by H.J. Liu
5074 * Added 64bit pointer support mainly from Wolfram Gloger
5075 * Added anonymously donated WIN32 sbrk emulation
5076 * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5077 * malloc_extend_top: fix mask error that caused wastage after
5079 * Add linux mremap support code from HJ Liu
5081 V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
5082 * Integrated most documentation with the code.
5083 * Add support for mmap, with help from
5084 Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5085 * Use last_remainder in more cases.
5086 * Pack bins using idea from colin@nyx10.cs.du.edu
5087 * Use ordered bins instead of best-fit threshold
5088 * Eliminate block-local decls to simplify tracing and debugging.
5089 * Support another case of realloc via move into top
5090 * Fix error occurring when initial sbrk_base not word-aligned.
5091 * Rely on page size for units instead of SBRK_UNIT to
5092 avoid surprises about sbrk alignment conventions.
5093 * Add mallinfo, mallopt. Thanks to Raymond Nijssen
5094 (raymond@es.ele.tue.nl) for the suggestion.
5095 * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5096 * More precautions for cases where other routines call sbrk,
5097 courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5098 * Added macros etc., allowing use in linux libc from
5099 H.J. Lu (hjl@gnu.ai.mit.edu)
5100 * Inverted this history list
5102 V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
5103 * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5104 * Removed all preallocation code since under current scheme
5105 the work required to undo bad preallocations exceeds
5106 the work saved in good cases for most test programs.
5107 * No longer use return list or unconsolidated bins since
5108 no scheme using them consistently outperforms those that don't
5109 given above changes.
5110 * Use best fit for very large chunks to prevent some worst-cases.
5111 * Added some support for debugging
5113 V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
5114 * Removed footers when chunks are in use. Thanks to
5115 Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5117 V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
5118 * Added malloc_trim, with help from Wolfram Gloger
5119 (wmglo@Dent.MED.Uni-Muenchen.DE).
5121 V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
5123 V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
5124 * realloc: try to expand in both directions
5125 * malloc: swap order of clean-bin strategy;
5126 * realloc: only conditionally expand backwards
5127 * Try not to scavenge used bins
5128 * Use bin counts as a guide to preallocation
5129 * Occasionally bin return list chunks in first scan
5130 * Add a few optimizations from colin@nyx10.cs.du.edu
5132 V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
5133 * faster bin computation & slightly different binning
5134 * merged all consolidations to one part of malloc proper
5135 (eliminating old malloc_find_space & malloc_clean_bin)
5136 * Scan 2 returns chunks (not just 1)
5137 * Propagate failure in realloc if malloc returns 0
5138 * Add stuff to allow compilation on non-ANSI compilers
5139 from kpv@research.att.com
5141 V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
5142 * removed potential for odd address access in prev_chunk
5143 * removed dependency on getpagesize.h
5144 * misc cosmetics and a bit more internal documentation
5145 * anticosmetics: mangled names in macros to evade debugger strangeness
5146 * tested on sparc, hp-700, dec-mips, rs6000
5147 with gcc & native cc (hp, dec only) allowing
5148 Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5150 Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
5151 * Based loosely on libg++-1.2X malloc. (It retains some of the overall
5152 structure of old version, but most details differ.)