2 Copyright (c) 2001 Wolfram Gloger
3 Copyright (c) 2006 Cavium networks
5 Permission to use, copy, modify, distribute, and sell this software
6 and its documentation for any purpose is hereby granted without fee,
7 provided that (i) the above copyright notices and this permission
8 notice appear in all copies of the software and related documentation,
9 and (ii) the name of Wolfram Gloger may not be used in any advertising
10 or publicity relating to the software.
12 THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
13 EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
14 WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
16 IN NO EVENT SHALL WOLFRAM GLOGER BE LIABLE FOR ANY SPECIAL,
17 INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY
18 DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
19 WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY
20 OF LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
21 PERFORMANCE OF THIS SOFTWARE.
25 This is a version (aka ptmalloc2) of malloc/free/realloc written by
26 Doug Lea and adapted to multiple threads/arenas by Wolfram Gloger.
28 * Version ptmalloc2-20011215
29 $Id: malloc.c 30481 2007-12-05 21:46:59Z rfranz $
31 VERSION 2.7.1pre1 Sat May 12 07:41:21 2001 Doug Lea (dl at gee)
33 Note: There may be an updated version of this malloc obtainable at
34 http://www.malloc.de/malloc/ptmalloc2.tar.gz
35 Check before installing!
39 In order to compile this implementation, a Makefile is provided with
40 the ptmalloc2 distribution, which has pre-defined targets for some
41 popular systems (e.g. "make posix" for Posix threads). All that is
42 typically required with regard to compiler flags is the selection of
43 the thread package via defining one out of USE_PTHREADS, USE_THR or
44 USE_SPROC. Check the thread-m.h file for what effects this has.
45 Many/most systems will additionally require USE_TSD_DATA_HACK to be
46 defined, so this is the default for "make posix".
48 * Why use this malloc?
50 This is not the fastest, most space-conserving, most portable, or
51 most tunable malloc ever written. However it is among the fastest
52 while also being among the most space-conserving, portable and tunable.
53 Consistent balance across these factors results in a good general-purpose
54 allocator for malloc-intensive programs.
56 The main properties of the algorithms are:
57 * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
58 with ties normally decided via FIFO (i.e. least recently used).
59 * For small (<= 64 bytes by default) requests, it is a caching
60 allocator, that maintains pools of quickly recycled chunks.
61 * In between, and for combinations of large and small requests, it does
62 the best it can trying to meet both goals at once.
63 * For very large requests (>= 128KB by default), it relies on system
64 memory mapping facilities, if supported.
66 For a longer but slightly out of date high-level description, see
67 http://gee.cs.oswego.edu/dl/html/malloc.html
69 You may already by default be using a C library containing a malloc
70 that is based on some version of this malloc (for example in
71 linux). You might still want to use the one in this file in order to
72 customize settings or to avoid overheads associated with library
75 * Contents, described in more detail in "description of public routines" below.
77 Standard (ANSI/SVID/...) functions:
79 calloc(size_t n_elements, size_t element_size);
81 realloc(Void_t* p, size_t n);
82 memalign(size_t alignment, size_t n);
85 mallopt(int parameter_number, int parameter_value)
88 independent_calloc(size_t n_elements, size_t size, Void_t* chunks[]);
89 independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
92 malloc_trim(size_t pad);
93 malloc_usable_size(Void_t* p);
98 Supported pointer representation: 4 or 8 bytes
99 Supported size_t representation: 4 or 8 bytes
100 Note that size_t is allowed to be 4 bytes even if pointers are 8.
101 You can adjust this by defining INTERNAL_SIZE_T
103 Alignment: 2 * sizeof(size_t) (default)
104 (i.e., 8 byte alignment with 4byte size_t). This suffices for
105 nearly all current machines and C compilers. However, you can
106 define MALLOC_ALIGNMENT to be wider than this if necessary.
108 Minimum overhead per allocated chunk: 4 or 8 bytes
109 Each malloced chunk has a hidden word of overhead holding size
110 and status information.
112 Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead)
113 8-byte ptrs: 24/32 bytes (including, 4/8 overhead)
115 When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
116 ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
117 needed; 4 (8) for a trailing size field and 8 (16) bytes for
118 free list pointers. Thus, the minimum allocatable size is
121 Even a request for zero bytes (i.e., malloc(0)) returns a
122 pointer to something of the minimum allocatable size.
124 The maximum overhead wastage (i.e., number of extra bytes
125 allocated than were requested in malloc) is less than or equal
126 to the minimum size, except for requests >= mmap_threshold that
127 are serviced via mmap(), where the worst case wastage is 2 *
128 sizeof(size_t) bytes plus the remainder from a system page (the
129 minimal mmap unit); typically 4096 or 8192 bytes.
131 Maximum allocated size: 4-byte size_t: 2^32 minus about two pages
132 8-byte size_t: 2^64 minus about two pages
134 It is assumed that (possibly signed) size_t values suffice to
135 represent chunk sizes. `Possibly signed' is due to the fact
136 that `size_t' may be defined on a system as either a signed or
137 an unsigned type. The ISO C standard says that it must be
138 unsigned, but a few systems are known not to adhere to this.
139 Additionally, even when size_t is unsigned, sbrk (which is by
140 default used to obtain memory from system) accepts signed
141 arguments, and may not be able to handle size_t-wide arguments
142 with negative sign bit. Generally, values that would
143 appear as negative after accounting for overhead and alignment
144 are supported only via mmap(), which does not have this
147 Requests for sizes outside the allowed range will perform an optional
148 failure action and then return null. (Requests may also
149 also fail because a system is out of memory.)
151 Thread-safety: thread-safe unless NO_THREADS is defined
153 Compliance: I believe it is compliant with the 1997 Single Unix Specification
154 (See http://www.opennc.org). Also SVID/XPG, ANSI C, and probably
157 * Synopsis of compile-time options:
159 People have reported using previous versions of this malloc on all
160 versions of Unix, sometimes by tweaking some of the defines
161 below. It has been tested most extensively on Solaris and
162 Linux. It is also reported to work on WIN32 platforms.
163 People also report using it in stand-alone embedded systems.
165 The implementation is in straight, hand-tuned ANSI C. It is not
166 at all modular. (Sorry!) It uses a lot of macros. To be at all
167 usable, this code should be compiled using an optimizing compiler
168 (for example gcc -O3) that can simplify expressions and control
169 paths. (FAQ: some macros import variables as arguments rather than
170 declare locals because people reported that some debuggers
171 otherwise get confused.)
175 Compilation Environment options:
177 __STD_C derived from C compiler defines
180 USE_MEMCPY 1 if HAVE_MEMCPY is defined
181 HAVE_MMAP defined as 1
183 HAVE_MREMAP 0 unless linux defined
184 USE_ARENAS the same as HAVE_MMAP
185 malloc_getpagesize derived from system #includes, or 4096 if not
186 HAVE_USR_INCLUDE_MALLOC_H NOT defined
187 LACKS_UNISTD_H NOT defined unless WIN32
188 LACKS_SYS_PARAM_H NOT defined unless WIN32
189 LACKS_SYS_MMAN_H NOT defined unless WIN32
191 Changing default word sizes:
193 INTERNAL_SIZE_T size_t
194 MALLOC_ALIGNMENT 2 * sizeof(INTERNAL_SIZE_T)
196 Configuration and functionality options:
198 USE_DL_PREFIX NOT defined
199 USE_PUBLIC_MALLOC_WRAPPERS NOT defined
200 USE_MALLOC_LOCK NOT defined
201 MALLOC_DEBUG NOT defined
202 REALLOC_ZERO_BYTES_FREES 1
203 MALLOC_FAILURE_ACTION errno = ENOMEM, if __STD_C defined, else no-op
205 FIRST_SORTED_BIN_SIZE 512
207 Options for customizing MORECORE:
211 MORECORE_CONTIGUOUS 1
212 MORECORE_CANNOT_TRIM NOT defined
214 MMAP_AS_MORECORE_SIZE (1024 * 1024)
216 Tuning options that are also dynamically changeable via mallopt:
219 DEFAULT_TRIM_THRESHOLD 128 * 1024
221 DEFAULT_MMAP_THRESHOLD 128 * 1024
222 DEFAULT_MMAP_MAX 65536
224 There are several other #defined constants and macros that you
225 probably don't want to touch unless you are extending or adapting malloc. */
228 __STD_C should be nonzero if using ANSI-standard C compiler, a C++
229 compiler, or a C compiler sufficiently close to ANSI to get away
233 #include "cvmx-config.h"
235 #include "cvmx-spinlock.h"
236 #include "cvmx-malloc.h"
240 #if defined(__STDC__) || defined(__cplusplus)
249 Void_t* is the pointer type that malloc should say it returns
265 /* define LACKS_UNISTD_H if your system does not have a <unistd.h>. */
267 /* #define LACKS_UNISTD_H */
269 #ifndef LACKS_UNISTD_H
273 /* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. */
275 /* #define LACKS_SYS_PARAM_H */
278 #include <stdio.h> /* needed for malloc_stats */
279 #include <errno.h> /* needed for optional MALLOC_FAILURE_ACTION */
285 Because freed chunks may be overwritten with bookkeeping fields, this
286 malloc will often die when freed memory is overwritten by user
287 programs. This can be very effective (albeit in an annoying way)
288 in helping track down dangling pointers.
290 If you compile with -DMALLOC_DEBUG, a number of assertion checks are
291 enabled that will catch more memory errors. You probably won't be
292 able to make much sense of the actual assertion errors, but they
293 should help you locate incorrectly overwritten memory. The checking
294 is fairly extensive, and will slow down execution
295 noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set
296 will attempt to check every non-mmapped allocated and free chunk in
297 the course of computing the summmaries. (By nature, mmapped regions
298 cannot be checked very much automatically.)
300 Setting MALLOC_DEBUG may also be helpful if you are trying to modify
301 this code. The assertions in the check routines spell out in more
302 detail the assumptions and invariants underlying the algorithms.
304 Setting MALLOC_DEBUG does NOT provide an automated mechanism for
305 checking that all accesses to malloced memory stay within their
306 bounds. However, there are several add-ons and adaptations of this
307 or other mallocs available that do this.
310 #define MALLOC_DEBUG 1
314 #define assert(x) ((void)0)
319 INTERNAL_SIZE_T is the word-size used for internal bookkeeping
322 The default version is the same as size_t.
324 While not strictly necessary, it is best to define this as an
325 unsigned type, even if size_t is a signed type. This may avoid some
326 artificial size limitations on some systems.
328 On a 64-bit machine, you may be able to reduce malloc overhead by
329 defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
330 expense of not being able to handle more than 2^32 of malloced
331 space. If this limitation is acceptable, you are encouraged to set
332 this unless you are on a platform requiring 16byte alignments. In
333 this case the alignment requirements turn out to negate any
334 potential advantages of decreasing size_t word size.
336 Implementors: Beware of the possible combinations of:
337 - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
338 and might be the same width as int or as long
339 - size_t might have different width and signedness as INTERNAL_SIZE_T
340 - int and long might be 32 or 64 bits, and might be the same width
341 To deal with this, most comparisons and difference computations
342 among INTERNAL_SIZE_Ts should cast them to unsigned long, being
343 aware of the fact that casting an unsigned int to a wider long does
344 not sign-extend. (This also makes checking for negative numbers
345 awkward.) Some of these casts result in harmless compiler warnings
349 #ifndef INTERNAL_SIZE_T
350 #define INTERNAL_SIZE_T size_t
353 /* The corresponding word size */
354 #define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
358 MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
359 It must be a power of two at least 2 * SIZE_SZ, even on machines
360 for which smaller alignments would suffice. It may be defined as
361 larger than this though. Note however that code and data structures
362 are optimized for the case of 8-byte alignment.
366 #ifndef MALLOC_ALIGNMENT
367 #define MALLOC_ALIGNMENT (2 * SIZE_SZ)
370 /* The corresponding bit mask value */
371 #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
376 REALLOC_ZERO_BYTES_FREES should be set if a call to
377 realloc with zero bytes should be the same as a call to free.
378 This is required by the C standard. Otherwise, since this malloc
379 returns a unique pointer for malloc(0), so does realloc(p, 0).
382 #ifndef REALLOC_ZERO_BYTES_FREES
383 #define REALLOC_ZERO_BYTES_FREES 1
387 TRIM_FASTBINS controls whether free() of a very small chunk can
388 immediately lead to trimming. Setting to true (1) can reduce memory
389 footprint, but will almost always slow down programs that use a lot
392 Define this only if you are willing to give up some speed to more
393 aggressively reduce system-level memory footprint when releasing
394 memory in programs that use many small chunks. You can get
395 essentially the same effect by setting MXFAST to 0, but this can
396 lead to even greater slowdowns in programs using many small chunks.
397 TRIM_FASTBINS is an in-between compile-time option, that disables
398 only those chunks bordering topmost memory from being placed in
402 #ifndef TRIM_FASTBINS
403 #define TRIM_FASTBINS 0
408 USE_DL_PREFIX will prefix all public routines with the string 'dl'.
409 This is necessary when you only want to use this malloc in one part
410 of a program, using your regular system malloc elsewhere.
413 #define USE_DL_PREFIX
417 Two-phase name translation.
418 All of the actual routines are given mangled names.
419 When wrappers are used, they become the public callable versions.
420 When DL_PREFIX is used, the callable names are prefixed.
424 #define public_cALLOc cvmx_calloc
425 #define public_fREe cvmx_free
426 #define public_cFREe dlcfree
427 #define public_mALLOc cvmx_malloc
428 #define public_mEMALIGn cvmx_memalign
429 #define public_rEALLOc cvmx_realloc
430 #define public_vALLOc dlvalloc
431 #define public_pVALLOc dlpvalloc
432 #define public_mALLINFo dlmallinfo
433 #define public_mALLOPt dlmallopt
434 #define public_mTRIm dlmalloc_trim
435 #define public_mSTATs dlmalloc_stats
436 #define public_mUSABLe dlmalloc_usable_size
437 #define public_iCALLOc dlindependent_calloc
438 #define public_iCOMALLOc dlindependent_comalloc
439 #define public_gET_STATe dlget_state
440 #define public_sET_STATe dlset_state
441 #else /* USE_DL_PREFIX */
443 #error _LIBC defined and should not be
444 /* Special defines for the GNU C library. */
445 #define public_cALLOc __libc_calloc
446 #define public_fREe __libc_free
447 #define public_cFREe __libc_cfree
448 #define public_mALLOc __libc_malloc
449 #define public_mEMALIGn __libc_memalign
450 #define public_rEALLOc __libc_realloc
451 #define public_vALLOc __libc_valloc
452 #define public_pVALLOc __libc_pvalloc
453 #define public_mALLINFo __libc_mallinfo
454 #define public_mALLOPt __libc_mallopt
455 #define public_mTRIm __malloc_trim
456 #define public_mSTATs __malloc_stats
457 #define public_mUSABLe __malloc_usable_size
458 #define public_iCALLOc __libc_independent_calloc
459 #define public_iCOMALLOc __libc_independent_comalloc
460 #define public_gET_STATe __malloc_get_state
461 #define public_sET_STATe __malloc_set_state
462 #define malloc_getpagesize __getpagesize()
465 #define munmap __munmap
466 #define mremap __mremap
467 #define mprotect __mprotect
468 #define MORECORE (*__morecore)
469 #define MORECORE_FAILURE 0
471 Void_t * __default_morecore (ptrdiff_t);
472 Void_t *(*__morecore)(ptrdiff_t) = __default_morecore;
475 #define public_cALLOc calloc
476 #define public_fREe free
477 #define public_cFREe cfree
478 #define public_mALLOc malloc
479 #define public_mEMALIGn memalign
480 #define public_rEALLOc realloc
481 #define public_vALLOc valloc
482 #define public_pVALLOc pvalloc
483 #define public_mALLINFo mallinfo
484 #define public_mALLOPt mallopt
485 #define public_mTRIm malloc_trim
486 #define public_mSTATs malloc_stats
487 #define public_mUSABLe malloc_usable_size
488 #define public_iCALLOc independent_calloc
489 #define public_iCOMALLOc independent_comalloc
490 #define public_gET_STATe malloc_get_state
491 #define public_sET_STATe malloc_set_state
493 #endif /* USE_DL_PREFIX */
497 HAVE_MEMCPY should be defined if you are not otherwise using
498 ANSI STD C, but still have memcpy and memset in your C library
499 and want to use them in calloc and realloc. Otherwise simple
500 macro versions are defined below.
502 USE_MEMCPY should be defined as 1 if you actually want to
503 have memset and memcpy called. People report that the macro
504 versions are faster than libc versions on some systems.
506 Even if USE_MEMCPY is set to 1, loops to copy/clear small chunks
507 (of <= 36 bytes) are manually unrolled in realloc and calloc.
521 #if (__STD_C || defined(HAVE_MEMCPY))
524 /* On Win32 memset and memcpy are already declared in windows.h */
527 void* memset(void*, int, size_t);
528 void* memcpy(void*, const void*, size_t);
537 MALLOC_FAILURE_ACTION is the action to take before "return 0" when
538 malloc fails to be able to return memory, either because memory is
539 exhausted or because of illegal arguments.
541 By default, sets errno if running on STD_C platform, else does nothing.
544 #ifndef MALLOC_FAILURE_ACTION
546 #define MALLOC_FAILURE_ACTION \
550 #define MALLOC_FAILURE_ACTION
555 MORECORE-related declarations. By default, rely on sbrk
559 #ifdef LACKS_UNISTD_H
560 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
562 extern Void_t* sbrk(ptrdiff_t);
564 extern Void_t* sbrk();
570 MORECORE is the name of the routine to call to obtain more memory
571 from the system. See below for general guidance on writing
572 alternative MORECORE functions, as well as a version for WIN32 and a
573 sample version for pre-OSX macos.
575 #undef MORECORE // not supported
577 #define MORECORE notsupported
581 MORECORE_FAILURE is the value returned upon failure of MORECORE
582 as well as mmap. Since it cannot be an otherwise valid memory address,
583 and must reflect values of standard sys calls, you probably ought not
587 #ifndef MORECORE_FAILURE
588 #define MORECORE_FAILURE (-1)
592 If MORECORE_CONTIGUOUS is true, take advantage of fact that
593 consecutive calls to MORECORE with positive arguments always return
594 contiguous increasing addresses. This is true of unix sbrk. Even
595 if not defined, when regions happen to be contiguous, malloc will
596 permit allocations spanning regions obtained from different
597 calls. But defining this when applicable enables some stronger
598 consistency checks and space efficiencies.
601 #ifndef MORECORE_CONTIGUOUS
602 #define MORECORE_CONTIGUOUS 0
606 Define MORECORE_CANNOT_TRIM if your version of MORECORE
607 cannot release space back to the system when given negative
608 arguments. This is generally necessary only if you are using
609 a hand-crafted MORECORE function that cannot handle negative arguments.
612 #define MORECORE_CANNOT_TRIM 1
614 /* MORECORE_CLEARS (default 1)
615 The degree to which the routine mapped to MORECORE zeroes out
616 memory: never (0), only for newly allocated space (1) or always
617 (2). The distinction between (1) and (2) is necessary because on
618 some systems, if the application first decrements and then
619 increments the break value, the contents of the reallocated space
623 #ifndef MORECORE_CLEARS
624 #define MORECORE_CLEARS 0
629 Define HAVE_MMAP as true to optionally make malloc() use mmap() to
630 allocate very large blocks. These will be returned to the
631 operating system immediately after a free(). Also, if mmap
632 is available, it is used as a backup strategy in cases where
633 MORECORE fails to provide space from system.
635 This malloc is best tuned to work with mmap for large requests.
636 If you do not have mmap, operations involving very large chunks (1MB
637 or so) may be slower than you'd like.
645 Standard unix mmap using /dev/zero clears memory so calloc doesn't
650 #define MMAP_CLEARS 0
655 #define MMAP_CLEARS 0
661 MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
662 sbrk fails, and mmap is used as a backup (which is done only if
663 HAVE_MMAP). The value must be a multiple of page size. This
664 backup strategy generally applies only when systems have "holes" in
665 address space, so sbrk cannot perform contiguous expansion, but
666 there is still space available on system. On systems for which
667 this is known to be useful (i.e. most linux kernels), this occurs
668 only when programs allocate huge amounts of memory. Between this,
669 and the fact that mmap regions tend to be limited, the size should
670 be large, to avoid too many mmap calls and thus avoid running out
674 #ifndef MMAP_AS_MORECORE_SIZE
675 #define MMAP_AS_MORECORE_SIZE (1024 * 1024)
679 Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
680 large blocks. This is currently only possible on Linux with
681 kernel versions newer than 1.3.77.
686 #define HAVE_MREMAP 1
688 #define HAVE_MREMAP 0
691 #endif /* HAVE_MMAP */
693 /* Define USE_ARENAS to enable support for multiple `arenas'. These
694 are allocated using mmap(), are necessary for threads and
695 occasionally useful to overcome address space limitations affecting
699 #define USE_ARENAS 1 // we 'manually' mmap the arenas.....
704 The system page size. To the extent possible, this malloc manages
705 memory from the system in page-size units. Note that this value is
706 cached during initialization into a field of malloc_state. So even
707 if malloc_getpagesize is a function, it is only called once.
709 The following mechanics for getpagesize were adapted from bsd/gnu
710 getpagesize.h. If none of the system-probes here apply, a value of
711 4096 is used, which should be OK: If they don't apply, then using
712 the actual value probably doesn't impact performance.
716 #define malloc_getpagesize (4096)
717 #ifndef malloc_getpagesize
719 #ifndef LACKS_UNISTD_H
723 # ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
724 # ifndef _SC_PAGE_SIZE
725 # define _SC_PAGE_SIZE _SC_PAGESIZE
729 # ifdef _SC_PAGE_SIZE
730 # define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
732 # if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
733 extern size_t getpagesize();
734 # define malloc_getpagesize getpagesize()
736 # ifdef WIN32 /* use supplied emulation of getpagesize */
737 # define malloc_getpagesize getpagesize()
739 # ifndef LACKS_SYS_PARAM_H
740 # include <sys/param.h>
742 # ifdef EXEC_PAGESIZE
743 # define malloc_getpagesize EXEC_PAGESIZE
747 # define malloc_getpagesize NBPG
749 # define malloc_getpagesize (NBPG * CLSIZE)
753 # define malloc_getpagesize NBPC
756 # define malloc_getpagesize PAGESIZE
757 # else /* just guess */
758 # define malloc_getpagesize (4096)
769 This version of malloc supports the standard SVID/XPG mallinfo
770 routine that returns a struct containing usage properties and
771 statistics. It should work on any SVID/XPG compliant system that has
772 a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
773 install such a thing yourself, cut out the preliminary declarations
774 as described above and below and save them in a malloc.h file. But
775 there's no compelling reason to bother to do this.)
777 The main declaration needed is the mallinfo struct that is returned
778 (by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a
779 bunch of fields that are not even meaningful in this version of
780 malloc. These fields are are instead filled by mallinfo() with
781 other numbers that might be of interest.
783 HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
784 /usr/include/malloc.h file that includes a declaration of struct
785 mallinfo. If so, it is included; else an SVID2/XPG2 compliant
786 version is declared below. These must be precisely the same for
787 mallinfo() to work. The original SVID version of this struct,
788 defined on most systems with mallinfo, declares all fields as
789 ints. But some others define as unsigned long. If your system
790 defines the fields using a type of different width than listed here,
791 you must #include your system version and #define
792 HAVE_USR_INCLUDE_MALLOC_H.
795 /* #define HAVE_USR_INCLUDE_MALLOC_H */
797 #ifdef HAVE_USR_INCLUDE_MALLOC_H
798 #include "/usr/include/malloc.h"
802 /* ---------- description of public routines ------------ */
806 Returns a pointer to a newly allocated chunk of at least n bytes, or null
807 if no space is available. Additionally, on failure, errno is
808 set to ENOMEM on ANSI C systems.
810 If n is zero, malloc returns a minumum-sized chunk. (The minimum
811 size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
812 systems.) On most systems, size_t is an unsigned type, so calls
813 with negative arguments are interpreted as requests for huge amounts
814 of space, which will often fail. The maximum supported value of n
815 differs across systems, but is in all cases less than the maximum
816 representable value of a size_t.
819 Void_t* public_mALLOc(cvmx_arena_list_t arena_list, size_t);
821 Void_t* public_mALLOc();
826 Releases the chunk of memory pointed to by p, that had been previously
827 allocated using malloc or a related routine such as realloc.
828 It has no effect if p is null. It can have arbitrary (i.e., bad!)
829 effects if p has already been freed.
831 Unless disabled (using mallopt), freeing very large spaces will
832 when possible, automatically trigger operations that give
833 back unused memory to the system, thus reducing program footprint.
836 void public_fREe(Void_t*);
842 calloc(size_t n_elements, size_t element_size);
843 Returns a pointer to n_elements * element_size bytes, with all locations
847 Void_t* public_cALLOc(cvmx_arena_list_t arena_list, size_t, size_t);
849 Void_t* public_cALLOc();
853 realloc(Void_t* p, size_t n)
854 Returns a pointer to a chunk of size n that contains the same data
855 as does chunk p up to the minimum of (n, p's size) bytes, or null
856 if no space is available.
858 The returned pointer may or may not be the same as p. The algorithm
859 prefers extending p when possible, otherwise it employs the
860 equivalent of a malloc-copy-free sequence.
862 If p is null, realloc is equivalent to malloc.
864 If space is not available, realloc returns null, errno is set (if on
865 ANSI) and p is NOT freed.
867 if n is for fewer bytes than already held by p, the newly unused
868 space is lopped off and freed if possible. Unless the #define
869 REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
870 zero (re)allocates a minimum-sized chunk.
872 Large chunks that were internally obtained via mmap will always
873 be reallocated using malloc-copy-free sequences unless
874 the system supports MREMAP (currently only linux).
876 The old unix realloc convention of allowing the last-free'd chunk
877 to be used as an argument to realloc is not supported.
880 Void_t* public_rEALLOc(cvmx_arena_list_t arena_list, Void_t*, size_t);
882 Void_t* public_rEALLOc();
886 memalign(size_t alignment, size_t n);
887 Returns a pointer to a newly allocated chunk of n bytes, aligned
888 in accord with the alignment argument.
890 The alignment argument should be a power of two. If the argument is
891 not a power of two, the nearest greater power is used.
892 8-byte alignment is guaranteed by normal malloc calls, so don't
893 bother calling memalign with an argument of 8 or less.
895 Overreliance on memalign is a sure way to fragment space.
898 Void_t* public_mEMALIGn(cvmx_arena_list_t arena_list, size_t, size_t);
900 Void_t* public_mEMALIGn();
905 Equivalent to memalign(pagesize, n), where pagesize is the page
906 size of the system. If the pagesize is unknown, 4096 is used.
909 Void_t* public_vALLOc(size_t);
911 Void_t* public_vALLOc();
917 mallopt(int parameter_number, int parameter_value)
918 Sets tunable parameters The format is to provide a
919 (parameter-number, parameter-value) pair. mallopt then sets the
920 corresponding parameter to the argument value if it can (i.e., so
921 long as the value is meaningful), and returns 1 if successful else
922 0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
923 normally defined in malloc.h. Only one of these (M_MXFAST) is used
924 in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
925 so setting them has no effect. But this malloc also supports four
926 other options in mallopt. See below for details. Briefly, supported
927 parameters are as follows (listed defaults are for "typical"
930 Symbol param # default allowed param values
931 M_MXFAST 1 64 0-80 (0 disables fastbins)
932 M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming)
934 M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support)
935 M_MMAP_MAX -4 65536 any (0 disables use of mmap)
938 int public_mALLOPt(int, int);
940 int public_mALLOPt();
946 Returns (by copy) a struct containing various summary statistics:
948 arena: current total non-mmapped bytes allocated from system
949 ordblks: the number of free chunks
950 smblks: the number of fastbin blocks (i.e., small chunks that
951 have been freed but not use resused or consolidated)
952 hblks: current number of mmapped regions
953 hblkhd: total bytes held in mmapped regions
954 usmblks: the maximum total allocated space. This will be greater
955 than current total if trimming has occurred.
956 fsmblks: total bytes held in fastbin blocks
957 uordblks: current total allocated space (normal or mmapped)
958 fordblks: total free space
959 keepcost: the maximum number of bytes that could ideally be released
960 back to system via malloc_trim. ("ideally" means that
961 it ignores page restrictions etc.)
963 Because these fields are ints, but internal bookkeeping may
964 be kept as longs, the reported values may wrap around zero and
968 struct mallinfo public_mALLINFo(void);
970 struct mallinfo public_mALLINFo();
974 independent_calloc(size_t n_elements, size_t element_size, Void_t* chunks[]);
976 independent_calloc is similar to calloc, but instead of returning a
977 single cleared space, it returns an array of pointers to n_elements
978 independent elements that can hold contents of size elem_size, each
979 of which starts out cleared, and can be independently freed,
980 realloc'ed etc. The elements are guaranteed to be adjacently
981 allocated (this is not guaranteed to occur with multiple callocs or
982 mallocs), which may also improve cache locality in some
985 The "chunks" argument is optional (i.e., may be null, which is
986 probably the most typical usage). If it is null, the returned array
987 is itself dynamically allocated and should also be freed when it is
988 no longer needed. Otherwise, the chunks array must be of at least
989 n_elements in length. It is filled in with the pointers to the
992 In either case, independent_calloc returns this pointer array, or
993 null if the allocation failed. If n_elements is zero and "chunks"
994 is null, it returns a chunk representing an array with zero elements
995 (which should be freed if not wanted).
997 Each element must be individually freed when it is no longer
998 needed. If you'd like to instead be able to free all at once, you
999 should instead use regular calloc and assign pointers into this
1000 space to represent elements. (In this case though, you cannot
1001 independently free elements.)
1003 independent_calloc simplifies and speeds up implementations of many
1004 kinds of pools. It may also be useful when constructing large data
1005 structures that initially have a fixed number of fixed-sized nodes,
1006 but the number is not known at compile time, and some of the nodes
1007 may later need to be freed. For example:
1009 struct Node { int item; struct Node* next; };
1011 struct Node* build_list() {
1013 int n = read_number_of_nodes_needed();
1014 if (n <= 0) return 0;
1015 pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
1016 if (pool == 0) die();
1017 // organize into a linked list...
1018 struct Node* first = pool[0];
1019 for (i = 0; i < n-1; ++i)
1020 pool[i]->next = pool[i+1];
1021 free(pool); // Can now free the array (or not, if it is needed later)
1026 Void_t** public_iCALLOc(size_t, size_t, Void_t**);
1028 Void_t** public_iCALLOc();
1032 independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
1034 independent_comalloc allocates, all at once, a set of n_elements
1035 chunks with sizes indicated in the "sizes" array. It returns
1036 an array of pointers to these elements, each of which can be
1037 independently freed, realloc'ed etc. The elements are guaranteed to
1038 be adjacently allocated (this is not guaranteed to occur with
1039 multiple callocs or mallocs), which may also improve cache locality
1040 in some applications.
1042 The "chunks" argument is optional (i.e., may be null). If it is null
1043 the returned array is itself dynamically allocated and should also
1044 be freed when it is no longer needed. Otherwise, the chunks array
1045 must be of at least n_elements in length. It is filled in with the
1046 pointers to the chunks.
1048 In either case, independent_comalloc returns this pointer array, or
1049 null if the allocation failed. If n_elements is zero and chunks is
1050 null, it returns a chunk representing an array with zero elements
1051 (which should be freed if not wanted).
1053 Each element must be individually freed when it is no longer
1054 needed. If you'd like to instead be able to free all at once, you
1055 should instead use a single regular malloc, and assign pointers at
1056 particular offsets in the aggregate space. (In this case though, you
1057 cannot independently free elements.)
1059 independent_comallac differs from independent_calloc in that each
1060 element may have a different size, and also that it does not
1061 automatically clear elements.
1063 independent_comalloc can be used to speed up allocation in cases
1064 where several structs or objects must always be allocated at the
1065 same time. For example:
1070 void send_message(char* msg) {
1071 int msglen = strlen(msg);
1072 size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1074 if (independent_comalloc(3, sizes, chunks) == 0)
1076 struct Head* head = (struct Head*)(chunks[0]);
1077 char* body = (char*)(chunks[1]);
1078 struct Foot* foot = (struct Foot*)(chunks[2]);
1082 In general though, independent_comalloc is worth using only for
1083 larger values of n_elements. For small values, you probably won't
1084 detect enough difference from series of malloc calls to bother.
1086 Overuse of independent_comalloc can increase overall memory usage,
1087 since it cannot reuse existing noncontiguous small chunks that
1088 might be available for some of the elements.
1091 Void_t** public_iCOMALLOc(size_t, size_t*, Void_t**);
1093 Void_t** public_iCOMALLOc();
1099 Equivalent to valloc(minimum-page-that-holds(n)), that is,
1100 round up n to nearest pagesize.
1103 Void_t* public_pVALLOc(size_t);
1105 Void_t* public_pVALLOc();
1110 Equivalent to free(p).
1112 cfree is needed/defined on some systems that pair it with calloc,
1113 for odd historical reasons (such as: cfree is used in example
1114 code in the first edition of K&R).
1117 void public_cFREe(Void_t*);
1119 void public_cFREe();
1123 malloc_trim(size_t pad);
1125 If possible, gives memory back to the system (via negative
1126 arguments to sbrk) if there is unused memory at the `high' end of
1127 the malloc pool. You can call this after freeing large blocks of
1128 memory to potentially reduce the system-level memory requirements
1129 of a program. However, it cannot guarantee to reduce memory. Under
1130 some allocation patterns, some large free blocks of memory will be
1131 locked between two used chunks, so they cannot be given back to
1134 The `pad' argument to malloc_trim represents the amount of free
1135 trailing space to leave untrimmed. If this argument is zero,
1136 only the minimum amount of memory to maintain internal data
1137 structures will be left (one page or less). Non-zero arguments
1138 can be supplied to maintain enough trailing space to service
1139 future expected allocations without having to re-obtain memory
1142 Malloc_trim returns 1 if it actually released any memory, else 0.
1143 On systems that do not support "negative sbrks", it will always
1147 int public_mTRIm(size_t);
1153 malloc_usable_size(Void_t* p);
1155 Returns the number of bytes you can actually use in
1156 an allocated chunk, which may be more than you requested (although
1157 often not) due to alignment and minimum size constraints.
1158 You can use this many bytes without worrying about
1159 overwriting other allocated objects. This is not a particularly great
1160 programming practice. malloc_usable_size can be more useful in
1161 debugging and assertions, for example:
1164 assert(malloc_usable_size(p) >= 256);
1168 size_t public_mUSABLe(Void_t*);
1170 size_t public_mUSABLe();
1175 Prints on stderr the amount of space obtained from the system (both
1176 via sbrk and mmap), the maximum amount (which may be more than
1177 current if malloc_trim and/or munmap got called), and the current
1178 number of bytes allocated via malloc (or realloc, etc) but not yet
1179 freed. Note that this is the number of bytes allocated, not the
1180 number requested. It will be larger than the number requested
1181 because of alignment and bookkeeping overhead. Because it includes
1182 alignment wastage as being in use, this figure may be greater than
1183 zero even when no user-level chunks are allocated.
1185 The reported current and maximum system memory can be inaccurate if
1186 a program makes other calls to system memory allocation functions
1187 (normally sbrk) outside of malloc.
1189 malloc_stats prints only the most commonly interesting statistics.
1190 More information can be obtained by calling mallinfo.
1194 void public_mSTATs(void);
1196 void public_mSTATs();
1200 malloc_get_state(void);
1202 Returns the state of all malloc variables in an opaque data
1206 Void_t* public_gET_STATe(void);
1208 Void_t* public_gET_STATe();
1212 malloc_set_state(Void_t* state);
1214 Restore the state of all malloc variables from data obtained with
1218 int public_sET_STATe(Void_t*);
1220 int public_sET_STATe();
1225 posix_memalign(void **memptr, size_t alignment, size_t size);
1227 POSIX wrapper like memalign(), checking for validity of size.
1229 int __posix_memalign(void **, size_t, size_t);
1232 /* mallopt tuning options */
1235 M_MXFAST is the maximum request size used for "fastbins", special bins
1236 that hold returned chunks without consolidating their spaces. This
1237 enables future requests for chunks of the same size to be handled
1238 very quickly, but can increase fragmentation, and thus increase the
1239 overall memory footprint of a program.
1241 This malloc manages fastbins very conservatively yet still
1242 efficiently, so fragmentation is rarely a problem for values less
1243 than or equal to the default. The maximum supported value of MXFAST
1244 is 80. You wouldn't want it any higher than this anyway. Fastbins
1245 are designed especially for use with many small structs, objects or
1246 strings -- the default handles structs/objects/arrays with sizes up
1247 to 8 4byte fields, or small strings representing words, tokens,
1248 etc. Using fastbins for larger objects normally worsens
1249 fragmentation without improving speed.
1251 M_MXFAST is set in REQUEST size units. It is internally used in
1252 chunksize units, which adds padding and alignment. You can reduce
1253 M_MXFAST to 0 to disable all use of fastbins. This causes the malloc
1254 algorithm to be a closer approximation of fifo-best-fit in all cases,
1255 not just for larger requests, but will generally cause it to be
1260 /* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
1265 #ifndef DEFAULT_MXFAST
1266 #define DEFAULT_MXFAST 64
1271 M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
1272 to keep before releasing via malloc_trim in free().
1274 Automatic trimming is mainly useful in long-lived programs.
1275 Because trimming via sbrk can be slow on some systems, and can
1276 sometimes be wasteful (in cases where programs immediately
1277 afterward allocate more large chunks) the value should be high
1278 enough so that your overall system performance would improve by
1279 releasing this much memory.
1281 The trim threshold and the mmap control parameters (see below)
1282 can be traded off with one another. Trimming and mmapping are
1283 two different ways of releasing unused memory back to the
1284 system. Between these two, it is often possible to keep
1285 system-level demands of a long-lived program down to a bare
1286 minimum. For example, in one test suite of sessions measuring
1287 the XF86 X server on Linux, using a trim threshold of 128K and a
1288 mmap threshold of 192K led to near-minimal long term resource
1291 If you are using this malloc in a long-lived program, it should
1292 pay to experiment with these values. As a rough guide, you
1293 might set to a value close to the average size of a process
1294 (program) running on your system. Releasing this much memory
1295 would allow such a process to run in memory. Generally, it's
1296 worth it to tune for trimming rather tham memory mapping when a
1297 program undergoes phases where several large chunks are
1298 allocated and released in ways that can reuse each other's
1299 storage, perhaps mixed with phases where there are no such
1300 chunks at all. And in well-behaved long-lived programs,
1301 controlling release of large blocks via trimming versus mapping
1304 However, in most programs, these parameters serve mainly as
1305 protection against the system-level effects of carrying around
1306 massive amounts of unneeded memory. Since frequent calls to
1307 sbrk, mmap, and munmap otherwise degrade performance, the default
1308 parameters are set to relatively high values that serve only as
1311 The trim value It must be greater than page size to have any useful
1312 effect. To disable trimming completely, you can set to
1315 Trim settings interact with fastbin (MXFAST) settings: Unless
1316 TRIM_FASTBINS is defined, automatic trimming never takes place upon
1317 freeing a chunk with size less than or equal to MXFAST. Trimming is
1318 instead delayed until subsequent freeing of larger chunks. However,
1319 you can still force an attempted trim by calling malloc_trim.
1321 Also, trimming is not generally possible in cases where
1322 the main arena is obtained via mmap.
1324 Note that the trick some people use of mallocing a huge space and
1325 then freeing it at program startup, in an attempt to reserve system
1326 memory, doesn't have the intended effect under automatic trimming,
1327 since that memory will immediately be returned to the system.
1330 #define M_TRIM_THRESHOLD -1
1332 #ifndef DEFAULT_TRIM_THRESHOLD
1333 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
1337 M_TOP_PAD is the amount of extra `padding' space to allocate or
1338 retain whenever sbrk is called. It is used in two ways internally:
1340 * When sbrk is called to extend the top of the arena to satisfy
1341 a new malloc request, this much padding is added to the sbrk
1344 * When malloc_trim is called automatically from free(),
1345 it is used as the `pad' argument.
1347 In both cases, the actual amount of padding is rounded
1348 so that the end of the arena is always a system page boundary.
1350 The main reason for using padding is to avoid calling sbrk so
1351 often. Having even a small pad greatly reduces the likelihood
1352 that nearly every malloc request during program start-up (or
1353 after trimming) will invoke sbrk, which needlessly wastes
1356 Automatic rounding-up to page-size units is normally sufficient
1357 to avoid measurable overhead, so the default is 0. However, in
1358 systems where sbrk is relatively slow, it can pay to increase
1359 this value, at the expense of carrying around more memory than
1363 #define M_TOP_PAD -2
1365 #ifndef DEFAULT_TOP_PAD
1366 #define DEFAULT_TOP_PAD (0)
1370 M_MMAP_THRESHOLD is the request size threshold for using mmap()
1371 to service a request. Requests of at least this size that cannot
1372 be allocated using already-existing space will be serviced via mmap.
1373 (If enough normal freed space already exists it is used instead.)
1375 Using mmap segregates relatively large chunks of memory so that
1376 they can be individually obtained and released from the host
1377 system. A request serviced through mmap is never reused by any
1378 other request (at least not directly; the system may just so
1379 happen to remap successive requests to the same locations).
1381 Segregating space in this way has the benefits that:
1383 1. Mmapped space can ALWAYS be individually released back
1384 to the system, which helps keep the system level memory
1385 demands of a long-lived program low.
1386 2. Mapped memory can never become `locked' between
1387 other chunks, as can happen with normally allocated chunks, which
1388 means that even trimming via malloc_trim would not release them.
1389 3. On some systems with "holes" in address spaces, mmap can obtain
1390 memory that sbrk cannot.
1392 However, it has the disadvantages that:
1394 1. The space cannot be reclaimed, consolidated, and then
1395 used to service later requests, as happens with normal chunks.
1396 2. It can lead to more wastage because of mmap page alignment
1398 3. It causes malloc performance to be more dependent on host
1399 system memory management support routines which may vary in
1400 implementation quality and may impose arbitrary
1401 limitations. Generally, servicing a request via normal
1402 malloc steps is faster than going through a system's mmap.
1404 The advantages of mmap nearly always outweigh disadvantages for
1405 "large" chunks, but the value of "large" varies across systems. The
1406 default is an empirically derived value that works well in most
1410 #define M_MMAP_THRESHOLD -3
1412 #ifndef DEFAULT_MMAP_THRESHOLD
1413 #define DEFAULT_MMAP_THRESHOLD (128 * 1024)
1417 M_MMAP_MAX is the maximum number of requests to simultaneously
1418 service using mmap. This parameter exists because
1419 some systems have a limited number of internal tables for
1420 use by mmap, and using more than a few of them may degrade
1423 The default is set to a value that serves only as a safeguard.
1424 Setting to 0 disables use of mmap for servicing large requests. If
1425 HAVE_MMAP is not set, the default value is 0, and attempts to set it
1426 to non-zero values in mallopt will fail.
1429 #define M_MMAP_MAX -4
1431 #ifndef DEFAULT_MMAP_MAX
1433 #define DEFAULT_MMAP_MAX (65536)
1435 #define DEFAULT_MMAP_MAX (0)
1440 }; /* end of extern "C" */
1443 #include <cvmx-spinlock.h>
1445 #include "thread-m.h"
1448 #define debug_printf printf
1450 #define debug_printf(format, args...)
1454 #define BOUNDED_N(ptr, sz) (ptr)
1456 #ifndef RETURN_ADDRESS
1457 #define RETURN_ADDRESS(X_) (NULL)
1460 /* On some platforms we can compile internal, not exported functions better.
1461 Let the environment provide a macro and define it to be empty if it
1462 is not available. */
1463 #ifndef internal_function
1464 # define internal_function
1467 /* Forward declarations. */
1468 struct malloc_chunk;
1469 typedef struct malloc_chunk* mchunkptr;
1471 /* Internal routines. */
1475 static Void_t* _int_malloc(mstate, size_t);
1476 static void _int_free(mstate, Void_t*);
1477 static Void_t* _int_realloc(mstate, Void_t*, size_t);
1478 static Void_t* _int_memalign(mstate, size_t, size_t);
1479 static Void_t* _int_valloc(mstate, size_t);
1480 static Void_t* _int_pvalloc(mstate, size_t);
1481 static Void_t* cALLOc(cvmx_arena_list_t arena_list, size_t, size_t);
1482 static Void_t** _int_icalloc(mstate, size_t, size_t, Void_t**);
1483 static Void_t** _int_icomalloc(mstate, size_t, size_t*, Void_t**);
1484 static int mTRIm(size_t);
1485 static size_t mUSABLe(Void_t*);
1486 static void mSTATs(void);
1487 static int mALLOPt(int, int);
1488 static struct mallinfo mALLINFo(mstate);
1490 static Void_t* internal_function mem2mem_check(Void_t *p, size_t sz);
1491 static int internal_function top_check(void);
1492 static void internal_function munmap_chunk(mchunkptr p);
1494 static mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size);
1497 static Void_t* malloc_check(size_t sz, const Void_t *caller);
1498 static void free_check(Void_t* mem, const Void_t *caller);
1499 static Void_t* realloc_check(Void_t* oldmem, size_t bytes,
1500 const Void_t *caller);
1501 static Void_t* memalign_check(size_t alignment, size_t bytes,
1502 const Void_t *caller);
1504 static Void_t* malloc_starter(size_t sz, const Void_t *caller);
1505 static void free_starter(Void_t* mem, const Void_t *caller);
1506 static Void_t* malloc_atfork(size_t sz, const Void_t *caller);
1507 static void free_atfork(Void_t* mem, const Void_t *caller);
1512 Void_t* _int_malloc();
1514 Void_t* _int_realloc();
1515 Void_t* _int_memalign();
1516 Void_t* _int_valloc();
1517 Void_t* _int_pvalloc();
1518 /*static Void_t* cALLOc();*/
1519 static Void_t** _int_icalloc();
1520 static Void_t** _int_icomalloc();
1522 static size_t mUSABLe();
1523 static void mSTATs();
1524 static int mALLOPt();
1525 static struct mallinfo mALLINFo();
1532 /* ------------- Optional versions of memcopy ---------------- */
1538 Note: memcpy is ONLY invoked with non-overlapping regions,
1539 so the (usually slower) memmove is not needed.
1542 #define MALLOC_COPY(dest, src, nbytes) memcpy(dest, src, nbytes)
1543 #define MALLOC_ZERO(dest, nbytes) memset(dest, 0, nbytes)
1545 #else /* !USE_MEMCPY */
1547 /* Use Duff's device for good zeroing/copying performance. */
1549 #define MALLOC_ZERO(charp, nbytes) \
1551 INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \
1552 unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
1554 if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
1556 case 0: for(;;) { *mzp++ = 0; \
1557 case 7: *mzp++ = 0; \
1558 case 6: *mzp++ = 0; \
1559 case 5: *mzp++ = 0; \
1560 case 4: *mzp++ = 0; \
1561 case 3: *mzp++ = 0; \
1562 case 2: *mzp++ = 0; \
1563 case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \
1567 #define MALLOC_COPY(dest,src,nbytes) \
1569 INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \
1570 INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \
1571 unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
1573 if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
1575 case 0: for(;;) { *mcdst++ = *mcsrc++; \
1576 case 7: *mcdst++ = *mcsrc++; \
1577 case 6: *mcdst++ = *mcsrc++; \
1578 case 5: *mcdst++ = *mcsrc++; \
1579 case 4: *mcdst++ = *mcsrc++; \
1580 case 3: *mcdst++ = *mcsrc++; \
1581 case 2: *mcdst++ = *mcsrc++; \
1582 case 1: *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; } \
1588 /* ------------------ MMAP support ------------------ */
1594 #ifndef LACKS_SYS_MMAN_H
1595 #include <sys/mman.h>
1598 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1599 # define MAP_ANONYMOUS MAP_ANON
1601 #if !defined(MAP_FAILED)
1602 # define MAP_FAILED ((char*)-1)
1605 #ifndef MAP_NORESERVE
1606 # ifdef MAP_AUTORESRV
1607 # define MAP_NORESERVE MAP_AUTORESRV
1609 # define MAP_NORESERVE 0
1614 Nearly all versions of mmap support MAP_ANONYMOUS,
1615 so the following is unlikely to be needed, but is
1616 supplied just in case.
1619 #ifndef MAP_ANONYMOUS
1621 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1623 #define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
1624 (dev_zero_fd = open("/dev/zero", O_RDWR), \
1625 mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
1626 mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))
1630 #define MMAP(addr, size, prot, flags) \
1631 (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1636 #endif /* HAVE_MMAP */
1640 ----------------------- Chunk representations -----------------------
1645 This struct declaration is misleading (but accurate and necessary).
1646 It declares a "view" into memory allowing access to necessary
1647 fields at known offsets from a given base. See explanation below.
1649 struct malloc_chunk {
1651 INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
1652 INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
1653 mstate arena_ptr; /* ptr to arena chunk belongs to */
1655 struct malloc_chunk* fd; /* double links -- used only if free. */
1656 struct malloc_chunk* bk;
1661 malloc_chunk details:
1663 (The following includes lightly edited explanations by Colin Plumb.)
1665 Chunks of memory are maintained using a `boundary tag' method as
1666 described in e.g., Knuth or Standish. (See the paper by Paul
1667 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1668 survey of such techniques.) Sizes of free chunks are stored both
1669 in the front of each chunk and at the end. This makes
1670 consolidating fragmented chunks into bigger chunks very fast. The
1671 size fields also hold bits representing whether chunks are free or
1674 An allocated chunk looks like this:
1677 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1678 | Size of previous chunk, if allocated | |
1679 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1680 | Size of chunk, in bytes |P|
1681 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1682 | User data starts here... .
1684 . (malloc_usable_space() bytes) .
1686 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1688 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1691 Where "chunk" is the front of the chunk for the purpose of most of
1692 the malloc code, but "mem" is the pointer that is returned to the
1693 user. "Nextchunk" is the beginning of the next contiguous chunk.
1695 Chunks always begin on even word boundries, so the mem portion
1696 (which is returned to the user) is also on an even word boundary, and
1697 thus at least double-word aligned.
1699 Free chunks are stored in circular doubly-linked lists, and look like this:
1701 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1702 | Size of previous chunk |
1703 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1704 `head:' | Size of chunk, in bytes |P|
1705 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1706 | Forward pointer to next chunk in list |
1707 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1708 | Back pointer to previous chunk in list |
1709 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1710 | Unused space (may be 0 bytes long) .
1713 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1714 `foot:' | Size of chunk, in bytes |
1715 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1717 The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1718 chunk size (which is always a multiple of two words), is an in-use
1719 bit for the *previous* chunk. If that bit is *clear*, then the
1720 word before the current chunk size contains the previous chunk
1721 size, and can be used to find the front of the previous chunk.
1722 The very first chunk allocated always has this bit set,
1723 preventing access to non-existent (or non-owned) memory. If
1724 prev_inuse is set for any given chunk, then you CANNOT determine
1725 the size of the previous chunk, and might even get a memory
1726 addressing fault when trying to do so.
1728 Note that the `foot' of the current chunk is actually represented
1729 as the prev_size of the NEXT chunk. This makes it easier to
1730 deal with alignments etc but can be very confusing when trying
1731 to extend or adapt this code.
1733 The two exceptions to all this are
1735 1. The special chunk `top' doesn't bother using the
1736 trailing size field since there is no next contiguous chunk
1737 that would have to index off it. After initialization, `top'
1738 is forced to always exist. If it would become less than
1739 MINSIZE bytes long, it is replenished.
1741 2. Chunks allocated via mmap, which have the second-lowest-order
1742 bit (IS_MMAPPED) set in their size fields. Because they are
1743 allocated one-by-one, each must contain its own trailing size field.
1748 ---------- Size and alignment checks and conversions ----------
1751 /* conversion from malloc headers to user pointers, and back */
1752 /* Added size for pointer to make room for arena_ptr */
1753 #define chunk2mem(p) ((Void_t*)((char*)(p) + 2*SIZE_SZ + sizeof(void *)))
1754 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ - sizeof(void *)))
1756 /* The smallest possible chunk */
1757 #define MIN_CHUNK_SIZE (sizeof(struct malloc_chunk))
1759 /* The smallest size we can malloc is an aligned minimal chunk */
1762 (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1764 /* Check if m has acceptable alignment */
1766 #define aligned_OK(m) (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1770 Check if a request is so large that it would wrap around zero when
1771 padded and aligned. To simplify some other code, the bound is made
1772 low enough so that adding MINSIZE will also not wrap around zero.
1775 #define REQUEST_OUT_OF_RANGE(req) \
1776 ((unsigned long)(req) >= \
1777 (unsigned long)(INTERNAL_SIZE_T)(-2 * MINSIZE))
1779 /* pad request bytes into a usable size -- internal version */
1782 /* prev_size field of next chunk is overwritten with data
1783 ** when in use. NOTE - last SIZE_SZ of arena must be left
1784 ** unused for last chunk to use
1786 /* Added sizeof(void *) to make room for arena_ptr */
1787 #define request2size(req) \
1788 (((req) + sizeof(void *) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
1790 ((req) + sizeof(void *) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1792 /* Same, except also perform argument check */
1794 #define checked_request2size(req, sz) \
1795 if (REQUEST_OUT_OF_RANGE(req)) { \
1796 MALLOC_FAILURE_ACTION; \
1799 (sz) = request2size(req);
1802 --------------- Physical chunk operations ---------------
1806 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1807 #define PREV_INUSE 0x1
1809 /* extract inuse bit of previous chunk */
1810 #define prev_inuse(p) ((p)->size & PREV_INUSE)
1813 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1814 #define IS_MMAPPED 0x2
1816 /* check for mmap()'ed chunk */
1817 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1822 Bits to mask off when extracting size
1824 Note: IS_MMAPPED is intentionally not masked off from size field in
1825 macros for which mmapped chunks should never be seen. This should
1826 cause helpful core dumps to occur if it is tried by accident by
1827 people extending or adapting this malloc.
1829 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED)
1831 /* Get size, ignoring use bits */
1832 #define chunksize(p) ((p)->size & ~(SIZE_BITS))
1835 /* Ptr to next physical malloc_chunk. */
1836 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~SIZE_BITS) ))
1838 /* Ptr to previous physical malloc_chunk */
1839 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1841 /* Treat space at ptr + offset as a chunk */
1842 #define chunk_at_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
1844 /* extract p's inuse bit */
1846 ((((mchunkptr)(((char*)(p))+((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1848 /* set/clear chunk as being inuse without otherwise disturbing */
1849 #define set_inuse(p)\
1850 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
1852 #define clear_inuse(p)\
1853 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
1856 /* check/set/clear inuse bits in known places */
1857 #define inuse_bit_at_offset(p, s)\
1858 (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
1860 #define set_inuse_bit_at_offset(p, s)\
1861 (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
1863 #define clear_inuse_bit_at_offset(p, s)\
1864 (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
1867 /* Set size at head, without disturbing its use bit */
1868 #define set_head_size(p, s) ((p)->size = (((p)->size & SIZE_BITS) | (s)))
1870 /* Set size/use field */
1871 #define set_head(p, s) ((p)->size = (s))
1873 /* Set size at footer (only when chunk is not in use) */
1874 #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
1878 -------------------- Internal data structures --------------------
1880 All internal state is held in an instance of malloc_state defined
1881 below. There are no other static variables, except in two optional
1883 * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1884 * If HAVE_MMAP is true, but mmap doesn't support
1885 MAP_ANONYMOUS, a dummy file descriptor for mmap.
1887 Beware of lots of tricks that minimize the total bookkeeping space
1888 requirements. The result is a little over 1K bytes (for 4byte
1889 pointers and size_t.)
1895 An array of bin headers for free chunks. Each bin is doubly
1896 linked. The bins are approximately proportionally (log) spaced.
1897 There are a lot of these bins (128). This may look excessive, but
1898 works very well in practice. Most bins hold sizes that are
1899 unusual as malloc request sizes, but are more usual for fragments
1900 and consolidated sets of chunks, which is what these bins hold, so
1901 they can be found quickly. All procedures maintain the invariant
1902 that no consolidated chunk physically borders another one, so each
1903 chunk in a list is known to be preceeded and followed by either
1904 inuse chunks or the ends of memory.
1906 Chunks in bins are kept in size order, with ties going to the
1907 approximately least recently used chunk. Ordering isn't needed
1908 for the small bins, which all contain the same-sized chunks, but
1909 facilitates best-fit allocation for larger chunks. These lists
1910 are just sequential. Keeping them in order almost never requires
1911 enough traversal to warrant using fancier ordered data
1914 Chunks of the same size are linked with the most
1915 recently freed at the front, and allocations are taken from the
1916 back. This results in LRU (FIFO) allocation order, which tends
1917 to give each chunk an equal opportunity to be consolidated with
1918 adjacent freed chunks, resulting in larger free chunks and less
1921 To simplify use in double-linked lists, each bin header acts
1922 as a malloc_chunk. This avoids special-casing for headers.
1923 But to conserve space and improve locality, we allocate
1924 only the fd/bk pointers of bins, and then use repositioning tricks
1925 to treat these as the fields of a malloc_chunk*.
1928 typedef struct malloc_chunk* mbinptr;
1930 /* addressing -- note that bin_at(0) does not exist */
1931 #define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - (SIZE_SZ<<1)))
1933 /* analog of ++bin */
1934 #define next_bin(b) ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
1936 /* Reminders about list directionality within bins */
1937 #define first(b) ((b)->fd)
1938 #define last(b) ((b)->bk)
1940 /* Take a chunk off a bin list */
1941 #define unlink(P, BK, FD) { \
1951 Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1952 8 bytes apart. Larger bins are approximately logarithmically spaced:
1958 4 bins of size 32768
1959 2 bins of size 262144
1960 1 bin of size what's left
1962 There is actually a little bit of slop in the numbers in bin_index
1963 for the sake of speed. This makes no difference elsewhere.
1965 The bins top out around 1MB because we expect to service large
1970 #define NSMALLBINS 64
1971 #define SMALLBIN_WIDTH 8
1972 #define MIN_LARGE_SIZE 512
1974 #define in_smallbin_range(sz) \
1975 ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)
1977 #define smallbin_index(sz) (((unsigned)(sz)) >> 3)
1979 #define largebin_index(sz) \
1980 (((((unsigned long)(sz)) >> 6) <= 32)? 56 + (((unsigned long)(sz)) >> 6): \
1981 ((((unsigned long)(sz)) >> 9) <= 20)? 91 + (((unsigned long)(sz)) >> 9): \
1982 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
1983 ((((unsigned long)(sz)) >> 15) <= 4)? 119 + (((unsigned long)(sz)) >> 15): \
1984 ((((unsigned long)(sz)) >> 18) <= 2)? 124 + (((unsigned long)(sz)) >> 18): \
1987 #define bin_index(sz) \
1988 ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
1991 FIRST_SORTED_BIN_SIZE is the chunk size corresponding to the
1992 first bin that is maintained in sorted order. This must
1993 be the smallest size corresponding to a given bin.
1995 Normally, this should be MIN_LARGE_SIZE. But you can weaken
1996 best fit guarantees to sometimes speed up malloc by increasing value.
1997 Doing this means that malloc may choose a chunk that is
1998 non-best-fitting by up to the width of the bin.
2000 Some useful cutoff values:
2001 512 - all bins sorted
2002 2560 - leaves bins <= 64 bytes wide unsorted
2003 12288 - leaves bins <= 512 bytes wide unsorted
2004 65536 - leaves bins <= 4096 bytes wide unsorted
2005 262144 - leaves bins <= 32768 bytes wide unsorted
2006 -1 - no bins sorted (not recommended!)
2009 #define FIRST_SORTED_BIN_SIZE MIN_LARGE_SIZE
2010 /* #define FIRST_SORTED_BIN_SIZE 65536 */
2015 All remainders from chunk splits, as well as all returned chunks,
2016 are first placed in the "unsorted" bin. They are then placed
2017 in regular bins after malloc gives them ONE chance to be used before
2018 binning. So, basically, the unsorted_chunks list acts as a queue,
2019 with chunks being placed on it in free (and malloc_consolidate),
2020 and taken off (to be either used or placed in bins) in malloc.
2022 The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
2023 does not have to be taken into account in size comparisons.
2026 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
2027 #define unsorted_chunks(M) (bin_at(M, 1))
2032 The top-most available chunk (i.e., the one bordering the end of
2033 available memory) is treated specially. It is never included in
2034 any bin, is used only if no other chunk is available, and is
2035 released back to the system if it is very large (see
2036 M_TRIM_THRESHOLD). Because top initially
2037 points to its own bin with initial zero size, thus forcing
2038 extension on the first malloc request, we avoid having any special
2039 code in malloc to check whether it even exists yet. But we still
2040 need to do so when getting memory from system, so we make
2041 initial_top treat the bin as a legal but unusable chunk during the
2042 interval between initialization and the first call to
2043 sYSMALLOc. (This is somewhat delicate, since it relies on
2044 the 2 preceding words to be zero during this interval as well.)
2047 /* Conveniently, the unsorted bin can be used as dummy top on first call */
2048 #define initial_top(M) (unsorted_chunks(M))
2053 To help compensate for the large number of bins, a one-level index
2054 structure is used for bin-by-bin searching. `binmap' is a
2055 bitvector recording whether bins are definitely empty so they can
2056 be skipped over during during traversals. The bits are NOT always
2057 cleared as soon as bins are empty, but instead only
2058 when they are noticed to be empty during traversal in malloc.
2061 /* Conservatively use 32 bits per map word, even if on 64bit system */
2062 #define BINMAPSHIFT 5
2063 #define BITSPERMAP (1U << BINMAPSHIFT)
2064 #define BINMAPSIZE (NBINS / BITSPERMAP)
2066 #define idx2block(i) ((i) >> BINMAPSHIFT)
2067 #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT)-1))))
2069 #define mark_bin(m,i) ((m)->binmap[idx2block(i)] |= idx2bit(i))
2070 #define unmark_bin(m,i) ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
2071 #define get_binmap(m,i) ((m)->binmap[idx2block(i)] & idx2bit(i))
2076 An array of lists holding recently freed small chunks. Fastbins
2077 are not doubly linked. It is faster to single-link them, and
2078 since chunks are never removed from the middles of these lists,
2079 double linking is not necessary. Also, unlike regular bins, they
2080 are not even processed in FIFO order (they use faster LIFO) since
2081 ordering doesn't much matter in the transient contexts in which
2082 fastbins are normally used.
2084 Chunks in fastbins keep their inuse bit set, so they cannot
2085 be consolidated with other free chunks. malloc_consolidate
2086 releases all chunks in fastbins and consolidates them with
2090 typedef struct malloc_chunk* mfastbinptr;
2092 /* offset 2 to use otherwise unindexable first 2 bins */
2093 #define fastbin_index(sz) ((int)((((unsigned int)(sz)) >> 3) - 2))
2095 /* The maximum fastbin request size we support */
2096 #define MAX_FAST_SIZE 80
2098 #define NFASTBINS (fastbin_index(request2size(MAX_FAST_SIZE))+1)
2101 FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
2102 that triggers automatic consolidation of possibly-surrounding
2103 fastbin chunks. This is a heuristic, so the exact value should not
2104 matter too much. It is defined at half the default trim threshold as a
2105 compromise heuristic to only attempt consolidation if it is likely
2106 to lead to trimming. However, it is not dynamically tunable, since
2107 consolidation reduces fragmentation surrounding large chunks even
2108 if trimming is not used.
2111 #define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)
2114 Since the lowest 2 bits in max_fast don't matter in size comparisons,
2115 they are used as flags.
2119 FASTCHUNKS_BIT held in max_fast indicates that there are probably
2120 some fastbin chunks. It is set true on entering a chunk into any
2121 fastbin, and cleared only in malloc_consolidate.
2123 The truth value is inverted so that have_fastchunks will be true
2124 upon startup (since statics are zero-filled), simplifying
2125 initialization checks.
2128 #define FASTCHUNKS_BIT (1U)
2130 #define have_fastchunks(M) (((M)->max_fast & FASTCHUNKS_BIT) == 0)
2131 #define clear_fastchunks(M) ((M)->max_fast |= FASTCHUNKS_BIT)
2132 #define set_fastchunks(M) ((M)->max_fast &= ~FASTCHUNKS_BIT)
2135 NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
2136 regions. Otherwise, contiguity is exploited in merging together,
2137 when possible, results from consecutive MORECORE calls.
2139 The initial value comes from MORECORE_CONTIGUOUS, but is
2140 changed dynamically if mmap is ever used as an sbrk substitute.
2143 #define NONCONTIGUOUS_BIT (2U)
2145 #define contiguous(M) (((M)->max_fast & NONCONTIGUOUS_BIT) == 0)
2146 #define noncontiguous(M) (((M)->max_fast & NONCONTIGUOUS_BIT) != 0)
2147 #define set_noncontiguous(M) ((M)->max_fast |= NONCONTIGUOUS_BIT)
2148 #define set_contiguous(M) ((M)->max_fast &= ~NONCONTIGUOUS_BIT)
2151 Set value of max_fast.
2152 Use impossibly small value if 0.
2153 Precondition: there are no existing fastbin chunks.
2154 Setting the value clears fastchunk bit but preserves noncontiguous bit.
2157 #define set_max_fast(M, s) \
2158 (M)->max_fast = (((s) == 0)? SMALLBIN_WIDTH: request2size(s)) | \
2160 ((M)->max_fast & NONCONTIGUOUS_BIT)
2164 ----------- Internal state representation and initialization -----------
2167 struct malloc_state {
2168 /* Serialize access. */
2171 /* Statistics for locking. Only used if THREAD_STATS is defined. */
2172 long stat_lock_direct, stat_lock_loop, stat_lock_wait;
2173 long pad0_[1]; /* try to give the mutex its own cacheline */
2175 /* The maximum chunk size to be eligible for fastbin */
2176 INTERNAL_SIZE_T max_fast; /* low 2 bits used as flags */
2179 mfastbinptr fastbins[NFASTBINS];
2181 /* Base of the topmost chunk -- not otherwise kept in a bin */
2184 /* The remainder from the most recent split of a small request */
2185 mchunkptr last_remainder;
2187 /* Normal bins packed as described above */
2188 mchunkptr bins[NBINS * 2];
2190 /* Bitmap of bins */
2191 unsigned int binmap[BINMAPSIZE];
2194 struct malloc_state *next;
2196 /* Memory allocated from the system in this arena. */
2197 INTERNAL_SIZE_T system_mem;
2198 INTERNAL_SIZE_T max_system_mem;
2202 /* Tunable parameters */
2203 unsigned long trim_threshold;
2204 INTERNAL_SIZE_T top_pad;
2205 INTERNAL_SIZE_T mmap_threshold;
2207 /* Memory map support */
2212 /* Cache malloc_getpagesize */
2213 unsigned int pagesize;
2216 INTERNAL_SIZE_T mmapped_mem;
2217 /*INTERNAL_SIZE_T sbrked_mem;*/
2218 /*INTERNAL_SIZE_T max_sbrked_mem;*/
2219 INTERNAL_SIZE_T max_mmapped_mem;
2220 INTERNAL_SIZE_T max_total_mem; /* only kept for NO_THREADS */
2222 /* First address handed out by MORECORE/sbrk. */
2226 /* There are several instances of this struct ("arenas") in this
2227 malloc. If you are adapting this malloc in a way that does NOT use
2228 a static or mmapped malloc_state, you MUST explicitly zero-fill it
2229 before using. This malloc relies on the property that malloc_state
2230 is initialized to all zeroes (as is true of C statics). */
2235 Initialize a malloc_state struct.
2237 This is called only from within malloc_consolidate, which needs
2238 be called in the same contexts anyway. It is never called directly
2239 outside of malloc_consolidate because some optimizing compilers try
2240 to inline it at all call points, which turns out not to be an
2241 optimization at all. (Inlining it in malloc_consolidate is fine though.)
2245 static void malloc_init_state(mstate av)
2247 static void malloc_init_state(av) mstate av;
2253 /* Establish circular links for normal bins */
2254 for (i = 1; i < NBINS; ++i) {
2256 bin->fd = bin->bk = bin;
2259 set_noncontiguous(av);
2261 set_max_fast(av, DEFAULT_MXFAST);
2263 av->top = initial_top(av);
2267 Other internal utilities operating on mstates
2271 static Void_t* sYSMALLOc(INTERNAL_SIZE_T, mstate);
2272 static void malloc_consolidate(mstate);
2273 //static Void_t** iALLOc(mstate, size_t, size_t*, int, Void_t**);
2275 static Void_t* sYSMALLOc();
2276 static void malloc_consolidate();
2277 static Void_t** iALLOc();
2280 /* ------------------- Support for multiple arenas -------------------- */
2286 These routines make a number of assertions about the states
2287 of data structures that should be true at all times. If any
2288 are not true, it's very likely that a user program has somehow
2289 trashed memory. (It's also possible that there is a coding error
2290 in malloc. In which case, please report it!)
2295 #define check_chunk(A,P)
2296 #define check_free_chunk(A,P)
2297 #define check_inuse_chunk(A,P)
2298 #define check_remalloced_chunk(A,P,N)
2299 #define check_malloced_chunk(A,P,N)
2300 #define check_malloc_state(A)
2304 #define check_chunk(A,P) do_check_chunk(A,P)
2305 #define check_free_chunk(A,P) do_check_free_chunk(A,P)
2306 #define check_inuse_chunk(A,P) do_check_inuse_chunk(A,P)
2307 #define check_remalloced_chunk(A,P,N) do_check_remalloced_chunk(A,P,N)
2308 #define check_malloced_chunk(A,P,N) do_check_malloced_chunk(A,P,N)
2309 #define check_malloc_state(A) do_check_malloc_state(A)
2312 Properties of all chunks
2316 static void do_check_chunk(mstate av, mchunkptr p)
2318 static void do_check_chunk(av, p) mstate av; mchunkptr p;
2321 unsigned long sz = chunksize(p);
2322 /* min and max possible addresses assuming contiguous allocation */
2323 char* max_address = (char*)(av->top) + chunksize(av->top);
2324 char* min_address = max_address - av->system_mem;
2326 if (!chunk_is_mmapped(p)) {
2328 /* Has legal address ... */
2330 if (contiguous(av)) {
2331 assert(((char*)p) >= min_address);
2332 assert(((char*)p + sz) <= ((char*)(av->top)));
2336 /* top size is always at least MINSIZE */
2337 assert((unsigned long)(sz) >= MINSIZE);
2338 /* top predecessor always marked inuse */
2339 assert(prev_inuse(p));
2345 /* address is outside main heap */
2346 if (contiguous(av) && av->top != initial_top(av)) {
2347 assert(((char*)p) < min_address || ((char*)p) > max_address);
2349 /* chunk is page-aligned */
2350 assert(((p->prev_size + sz) & (mp_.pagesize-1)) == 0);
2351 /* mem is aligned */
2352 assert(aligned_OK(chunk2mem(p)));
2354 /* force an appropriate assert violation if debug set */
2355 assert(!chunk_is_mmapped(p));
2361 Properties of free chunks
2365 static void do_check_free_chunk(mstate av, mchunkptr p)
2367 static void do_check_free_chunk(av, p) mstate av; mchunkptr p;
2370 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE);
2371 mchunkptr next = chunk_at_offset(p, sz);
2373 do_check_chunk(av, p);
2375 /* Chunk must claim to be free ... */
2377 assert (!chunk_is_mmapped(p));
2379 /* Unless a special marker, must have OK fields */
2380 if ((unsigned long)(sz) >= MINSIZE)
2382 assert((sz & MALLOC_ALIGN_MASK) == 0);
2383 assert(aligned_OK(chunk2mem(p)));
2384 /* ... matching footer field */
2385 assert(next->prev_size == sz);
2386 /* ... and is fully consolidated */
2387 assert(prev_inuse(p));
2388 assert (next == av->top || inuse(next));
2390 /* ... and has minimally sane links */
2391 assert(p->fd->bk == p);
2392 assert(p->bk->fd == p);
2394 else /* markers are always of size SIZE_SZ */
2395 assert(sz == SIZE_SZ);
2399 Properties of inuse chunks
2403 static void do_check_inuse_chunk(mstate av, mchunkptr p)
2405 static void do_check_inuse_chunk(av, p) mstate av; mchunkptr p;
2410 do_check_chunk(av, p);
2412 assert(av == arena_for_chunk(p));
2413 if (chunk_is_mmapped(p))
2414 return; /* mmapped chunks have no next/prev */
2416 /* Check whether it claims to be in use ... */
2419 next = next_chunk(p);
2421 /* ... and is surrounded by OK chunks.
2422 Since more things can be checked with free chunks than inuse ones,
2423 if an inuse chunk borders them and debug is on, it's worth doing them.
2425 if (!prev_inuse(p)) {
2426 /* Note that we cannot even look at prev unless it is not inuse */
2427 mchunkptr prv = prev_chunk(p);
2428 assert(next_chunk(prv) == p);
2429 do_check_free_chunk(av, prv);
2432 if (next == av->top) {
2433 assert(prev_inuse(next));
2434 assert(chunksize(next) >= MINSIZE);
2436 else if (!inuse(next))
2437 do_check_free_chunk(av, next);
2441 Properties of chunks recycled from fastbins
2445 static void do_check_remalloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2447 static void do_check_remalloced_chunk(av, p, s)
2448 mstate av; mchunkptr p; INTERNAL_SIZE_T s;
2451 INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE);
2453 if (!chunk_is_mmapped(p)) {
2454 assert(av == arena_for_chunk(p));
2457 do_check_inuse_chunk(av, p);
2459 /* Legal size ... */
2460 assert((sz & MALLOC_ALIGN_MASK) == 0);
2461 assert((unsigned long)(sz) >= MINSIZE);
2462 /* ... and alignment */
2463 assert(aligned_OK(chunk2mem(p)));
2464 /* chunk is less than MINSIZE more than request */
2465 assert((long)(sz) - (long)(s) >= 0);
2466 assert((long)(sz) - (long)(s + MINSIZE) < 0);
2470 Properties of nonrecycled chunks at the point they are malloced
2474 static void do_check_malloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2476 static void do_check_malloced_chunk(av, p, s)
2477 mstate av; mchunkptr p; INTERNAL_SIZE_T s;
2480 /* same as recycled case ... */
2481 do_check_remalloced_chunk(av, p, s);
2484 ... plus, must obey implementation invariant that prev_inuse is
2485 always true of any allocated chunk; i.e., that each allocated
2486 chunk borders either a previously allocated and still in-use
2487 chunk, or the base of its memory arena. This is ensured
2488 by making all allocations from the the `lowest' part of any found
2489 chunk. This does not necessarily hold however for chunks
2490 recycled via fastbins.
2493 assert(prev_inuse(p));
2498 Properties of malloc_state.
2500 This may be useful for debugging malloc, as well as detecting user
2501 programmer errors that somehow write into malloc_state.
2503 If you are extending or experimenting with this malloc, you can
2504 probably figure out how to hack this routine to print out or
2505 display chunk addresses, sizes, bins, and other instrumentation.
2508 static void do_check_malloc_state(mstate av)
2514 unsigned int binbit;
2517 INTERNAL_SIZE_T size;
2518 unsigned long total = 0;
2521 /* internal size_t must be no wider than pointer type */
2522 assert(sizeof(INTERNAL_SIZE_T) <= sizeof(char*));
2524 /* alignment is a power of 2 */
2525 assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0);
2527 /* cannot run remaining checks until fully initialized */
2528 if (av->top == 0 || av->top == initial_top(av))
2532 /* properties of fastbins */
2534 /* max_fast is in allowed range */
2535 assert((av->max_fast & ~1) <= request2size(MAX_FAST_SIZE));
2537 max_fast_bin = fastbin_index(av->max_fast);
2539 for (i = 0; i < NFASTBINS; ++i) {
2540 p = av->fastbins[i];
2542 /* all bins past max_fast are empty */
2543 if (i > max_fast_bin)
2547 /* each chunk claims to be inuse */
2548 do_check_inuse_chunk(av, p);
2549 total += chunksize(p);
2550 /* chunk belongs in this bin */
2551 assert(fastbin_index(chunksize(p)) == i);
2557 assert(have_fastchunks(av));
2558 else if (!have_fastchunks(av))
2561 /* check normal bins */
2562 for (i = 1; i < NBINS; ++i) {
2565 /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2567 binbit = get_binmap(av,i);
2568 empty = last(b) == b;
2575 for (p = last(b); p != b; p = p->bk) {
2576 /* each chunk claims to be free */
2577 do_check_free_chunk(av, p);
2578 size = chunksize(p);
2581 /* chunk belongs in bin */
2582 idx = bin_index(size);
2583 assert(idx == (unsigned int)i);
2584 /* lists are sorted */
2585 if ((unsigned long) size >= (unsigned long)(FIRST_SORTED_BIN_SIZE)) {
2586 assert(p->bk == b ||
2587 (unsigned long)chunksize(p->bk) >=
2588 (unsigned long)chunksize(p));
2591 /* chunk is followed by a legal chain of inuse chunks */
2592 for (q = next_chunk(p);
2593 (q != av->top && inuse(q) &&
2594 (unsigned long)(chunksize(q)) >= MINSIZE);
2596 do_check_inuse_chunk(av, q);
2600 /* top chunk is OK */
2601 check_chunk(av, av->top);
2603 /* sanity checks for statistics */
2606 assert((unsigned long)(av->system_mem) <=
2607 (unsigned long)(av->max_system_mem));
2615 /* ----------- Routines dealing with system allocation -------------- */
2617 /* No system allocation routines supported */
2620 /*------------------------ Public wrappers. --------------------------------*/
2626 public_mALLOc(cvmx_arena_list_t arena_list, size_t bytes)
2628 mstate ar_ptr, orig_ar_ptr;
2629 Void_t *victim = NULL;
2630 static mstate debug_prev_ar; // debug only!
2635 ar_ptr = arena_list;
2642 if (debug_prev_ar != ar_ptr)
2644 debug_printf("New arena: %p\n", ar_ptr);
2645 #ifdef CVMX_SPINLOCK_DEBUG
2646 cvmx_dprintf("lock wait count for arena: %p is %ld\n", ar_ptr, ar_ptr->mutex.wait_cnt);
2648 debug_prev_ar = ar_ptr;
2650 orig_ar_ptr = ar_ptr;
2652 // try to get an arena without contention
2658 if (!mutex_trylock(&ar_ptr->mutex))
2661 victim = _int_malloc(ar_ptr, bytes);
2662 (void)mutex_unlock(&ar_ptr->mutex);
2668 ar_ptr = ar_ptr->next;
2669 } while (ar_ptr != orig_ar_ptr);
2671 // we couldn't get the memory without contention, so try all
2675 ar_ptr = orig_ar_ptr;
2681 mutex_lock(&ar_ptr->mutex);
2682 victim = _int_malloc(ar_ptr, bytes);
2683 (void)mutex_unlock(&ar_ptr->mutex);
2688 ar_ptr = ar_ptr->next;
2689 } while (ar_ptr != orig_ar_ptr);
2693 assert(!victim || chunk_is_mmapped(mem2chunk(victim)) ||
2694 ar_ptr == arena_for_chunk(mem2chunk(victim)));
2699 cvmx_dprintf("Malloc failed: size: %ld, arena_cnt: %d\n", bytes, arena_cnt);
2703 debug_printf("cvmx_malloc(%ld) = %p\n", bytes, victim);
2705 // remember which arena we last used.....
2706 tsd_setspecific(arena_key, (Void_t *)ar_ptr);
2713 public_fREe(Void_t* mem)
2716 mchunkptr p; /* chunk corresponding to mem */
2718 debug_printf("cvmx_free(%p)\n", mem);
2721 if (mem == 0) /* free(0) has no effect */
2727 ar_ptr = arena_for_chunk(p);
2730 if(!mutex_trylock(&ar_ptr->mutex))
2731 ++(ar_ptr->stat_lock_direct);
2733 (void)mutex_lock(&ar_ptr->mutex);
2734 ++(ar_ptr->stat_lock_wait);
2737 (void)mutex_lock(&ar_ptr->mutex);
2739 _int_free(ar_ptr, mem);
2740 (void)mutex_unlock(&ar_ptr->mutex);
2744 public_rEALLOc(cvmx_arena_list_t arena_list, Void_t* oldmem, size_t bytes)
2747 INTERNAL_SIZE_T nb; /* padded request size */
2749 mchunkptr oldp; /* chunk corresponding to oldmem */
2750 INTERNAL_SIZE_T oldsize; /* its size */
2752 Void_t* newp; /* chunk to return */
2755 #if REALLOC_ZERO_BYTES_FREES
2756 if (bytes == 0 && oldmem != NULL) { public_fREe(oldmem); return 0; }
2759 /* realloc of null is supposed to be same as malloc */
2760 if (oldmem == 0) return public_mALLOc(arena_list, bytes);
2762 oldp = mem2chunk(oldmem);
2763 oldsize = chunksize(oldp);
2765 checked_request2size(bytes, nb);
2768 ar_ptr = arena_for_chunk(oldp);
2769 (void)mutex_lock(&ar_ptr->mutex);
2772 newp = _int_realloc(ar_ptr, oldmem, bytes);
2774 (void)mutex_unlock(&ar_ptr->mutex);
2775 assert(!newp || chunk_is_mmapped(mem2chunk(newp)) ||
2776 ar_ptr == arena_for_chunk(mem2chunk(newp)));
2780 #undef DEBUG_MEMALIGN
2782 public_mEMALIGn(cvmx_arena_list_t arena_list, size_t alignment, size_t bytes)
2784 mstate ar_ptr, orig_ar_ptr;
2786 #ifdef DEBUG_MEMALIGN
2791 /* If need less alignment than we give anyway, just relay to malloc */
2792 if (alignment <= MALLOC_ALIGNMENT) return public_mALLOc(arena_list, bytes);
2794 /* Otherwise, ensure that it is at least a minimum chunk size */
2795 if (alignment < MINSIZE) alignment = MINSIZE;
2798 ar_ptr = arena_list;
2805 orig_ar_ptr = ar_ptr;
2808 // try to get an arena without contention
2812 #ifdef DEBUG_MEMALIGN
2815 if (!mutex_trylock(&ar_ptr->mutex))
2818 p = _int_memalign(ar_ptr, alignment, bytes);
2819 (void)mutex_unlock(&ar_ptr->mutex);
2825 ar_ptr = ar_ptr->next;
2826 } while (ar_ptr != orig_ar_ptr);
2829 // we couldn't get the memory without contention, so try all
2833 #ifdef DEBUG_MEMALIGN
2836 ar_ptr = orig_ar_ptr;
2839 mutex_lock(&ar_ptr->mutex);
2840 p = _int_memalign(ar_ptr, alignment, bytes);
2841 (void)mutex_unlock(&ar_ptr->mutex);
2846 ar_ptr = ar_ptr->next;
2847 } while (ar_ptr != orig_ar_ptr);
2853 assert(ar_ptr == arena_for_chunk(mem2chunk(p)));
2857 #ifdef DEBUG_MEMALIGN
2858 cvmx_dprintf("Memalign failed: align: 0x%x, size: %ld, arena_cnt: %ld\n", alignment, bytes, arena_cnt);
2862 assert(!p || ar_ptr == arena_for_chunk(mem2chunk(p)));
2869 public_cALLOc(cvmx_arena_list_t arena_list, size_t n, size_t elem_size)
2872 mchunkptr oldtop, p;
2873 INTERNAL_SIZE_T sz, csz, oldtopsize;
2875 unsigned long clearsize;
2876 unsigned long nclears;
2880 /* FIXME: check for overflow on multiplication. */
2883 mem = public_mALLOc(arena_list, sz);
2896 public_cFREe(Void_t* m)
2904 ------------------------------ malloc ------------------------------
2908 _int_malloc(mstate av, size_t bytes)
2910 INTERNAL_SIZE_T nb; /* normalized request size */
2911 unsigned int idx; /* associated bin index */
2912 mbinptr bin; /* associated bin */
2913 mfastbinptr* fb; /* associated fastbin */
2915 mchunkptr victim; /* inspected/selected chunk */
2916 INTERNAL_SIZE_T size; /* its size */
2917 int victim_index; /* its bin index */
2919 mchunkptr remainder; /* remainder from a split */
2920 unsigned long remainder_size; /* its size */
2922 unsigned int block; /* bit map traverser */
2923 unsigned int bit; /* bit map traverser */
2924 unsigned int map; /* current word of binmap */
2926 mchunkptr fwd; /* misc temp for linking */
2927 mchunkptr bck; /* misc temp for linking */
2930 Convert request size to internal form by adding SIZE_SZ bytes
2931 overhead plus possibly more to obtain necessary alignment and/or
2932 to obtain a size of at least MINSIZE, the smallest allocatable
2933 size. Also, checked_request2size traps (returning 0) request sizes
2934 that are so large that they wrap around zero when padded and
2939 checked_request2size(bytes, nb);
2942 If the size qualifies as a fastbin, first check corresponding bin.
2943 This code is safe to execute even if av is not yet initialized, so we
2944 can try it without checking, which saves some time on this fast path.
2947 if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) {
2948 fb = &(av->fastbins[(fastbin_index(nb))]);
2949 if ( (victim = *fb) != 0) {
2951 check_remalloced_chunk(av, victim, nb);
2952 set_arena_for_chunk(victim, av);
2953 return chunk2mem(victim);
2958 If a small request, check regular bin. Since these "smallbins"
2959 hold one size each, no searching within bins is necessary.
2960 (For a large request, we need to wait until unsorted chunks are
2961 processed to find best fit. But for small ones, fits are exact
2962 anyway, so we can check now, which is faster.)
2965 if (in_smallbin_range(nb)) {
2966 idx = smallbin_index(nb);
2967 bin = bin_at(av,idx);
2969 if ( (victim = last(bin)) != bin) {
2970 if (victim == 0) /* initialization check */
2971 malloc_consolidate(av);
2974 set_inuse_bit_at_offset(victim, nb);
2978 set_arena_for_chunk(victim, av);
2979 check_malloced_chunk(av, victim, nb);
2980 return chunk2mem(victim);
2986 If this is a large request, consolidate fastbins before continuing.
2987 While it might look excessive to kill all fastbins before
2988 even seeing if there is space available, this avoids
2989 fragmentation problems normally associated with fastbins.
2990 Also, in practice, programs tend to have runs of either small or
2991 large requests, but less often mixtures, so consolidation is not
2992 invoked all that often in most programs. And the programs that
2993 it is called frequently in otherwise tend to fragment.
2997 idx = largebin_index(nb);
2998 if (have_fastchunks(av))
2999 malloc_consolidate(av);
3003 Process recently freed or remaindered chunks, taking one only if
3004 it is exact fit, or, if this a small request, the chunk is remainder from
3005 the most recent non-exact fit. Place other traversed chunks in
3006 bins. Note that this step is the only place in any routine where
3007 chunks are placed in bins.
3009 The outer loop here is needed because we might not realize until
3010 near the end of malloc that we should have consolidated, so must
3011 do so and retry. This happens at most once, and only when we would
3012 otherwise need to expand memory to service a "small" request.
3017 while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
3019 size = chunksize(victim);
3022 If a small request, try to use last remainder if it is the
3023 only chunk in unsorted bin. This helps promote locality for
3024 runs of consecutive small requests. This is the only
3025 exception to best-fit, and applies only when there is
3026 no exact fit for a small chunk.
3029 if (in_smallbin_range(nb) &&
3030 bck == unsorted_chunks(av) &&
3031 victim == av->last_remainder &&
3032 (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {
3034 /* split and reattach remainder */
3035 remainder_size = size - nb;
3036 remainder = chunk_at_offset(victim, nb);
3037 unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
3038 av->last_remainder = remainder;
3039 remainder->bk = remainder->fd = unsorted_chunks(av);
3041 set_head(victim, nb | PREV_INUSE);
3042 set_head(remainder, remainder_size | PREV_INUSE);
3043 set_foot(remainder, remainder_size);
3045 set_arena_for_chunk(victim, av);
3046 check_malloced_chunk(av, victim, nb);
3047 return chunk2mem(victim);
3050 /* remove from unsorted list */
3051 unsorted_chunks(av)->bk = bck;
3052 bck->fd = unsorted_chunks(av);
3054 /* Take now instead of binning if exact fit */
3057 set_inuse_bit_at_offset(victim, size);
3058 set_arena_for_chunk(victim, av);
3059 check_malloced_chunk(av, victim, nb);
3060 return chunk2mem(victim);
3063 /* place chunk in bin */
3065 if (in_smallbin_range(size)) {
3066 victim_index = smallbin_index(size);
3067 bck = bin_at(av, victim_index);
3071 victim_index = largebin_index(size);
3072 bck = bin_at(av, victim_index);
3076 /* if smaller than smallest, place first */
3077 if ((unsigned long)(size) < (unsigned long)(bck->bk->size)) {
3081 else if ((unsigned long)(size) >=
3082 (unsigned long)(FIRST_SORTED_BIN_SIZE)) {
3084 /* maintain large bins in sorted order */
3085 size |= PREV_INUSE; /* Or with inuse bit to speed comparisons */
3086 while ((unsigned long)(size) < (unsigned long)(fwd->size)) {
3094 mark_bin(av, victim_index);
3102 If a large request, scan through the chunks of current bin in
3103 sorted order to find smallest that fits. This is the only step
3104 where an unbounded number of chunks might be scanned without doing
3105 anything useful with them. However the lists tend to be short.
3108 if (!in_smallbin_range(nb)) {
3109 bin = bin_at(av, idx);
3111 for (victim = last(bin); victim != bin; victim = victim->bk) {
3112 size = chunksize(victim);
3114 if ((unsigned long)(size) >= (unsigned long)(nb)) {
3115 remainder_size = size - nb;
3116 unlink(victim, bck, fwd);
3119 if (remainder_size < MINSIZE) {
3120 set_inuse_bit_at_offset(victim, size);
3121 set_arena_for_chunk(victim, av);
3122 check_malloced_chunk(av, victim, nb);
3123 return chunk2mem(victim);
3127 remainder = chunk_at_offset(victim, nb);
3128 unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
3129 remainder->bk = remainder->fd = unsorted_chunks(av);
3130 set_head(victim, nb | PREV_INUSE);
3131 set_head(remainder, remainder_size | PREV_INUSE);
3132 set_foot(remainder, remainder_size);
3133 set_arena_for_chunk(victim, av);
3134 check_malloced_chunk(av, victim, nb);
3135 return chunk2mem(victim);
3142 Search for a chunk by scanning bins, starting with next largest
3143 bin. This search is strictly by best-fit; i.e., the smallest
3144 (with ties going to approximately the least recently used) chunk
3145 that fits is selected.
3147 The bitmap avoids needing to check that most blocks are nonempty.
3148 The particular case of skipping all bins during warm-up phases
3149 when no chunks have been returned yet is faster than it might look.
3153 bin = bin_at(av,idx);
3154 block = idx2block(idx);
3155 map = av->binmap[block];
3160 /* Skip rest of block if there are no more set bits in this block. */
3161 if (bit > map || bit == 0) {
3163 if (++block >= BINMAPSIZE) /* out of bins */
3165 } while ( (map = av->binmap[block]) == 0);
3167 bin = bin_at(av, (block << BINMAPSHIFT));
3171 /* Advance to bin with set bit. There must be one. */
3172 while ((bit & map) == 0) {
3173 bin = next_bin(bin);
3178 /* Inspect the bin. It is likely to be non-empty */
3181 /* If a false alarm (empty bin), clear the bit. */
3182 if (victim == bin) {
3183 av->binmap[block] = map &= ~bit; /* Write through */
3184 bin = next_bin(bin);
3189 size = chunksize(victim);
3191 /* We know the first chunk in this bin is big enough to use. */
3192 assert((unsigned long)(size) >= (unsigned long)(nb));
3194 remainder_size = size - nb;
3202 if (remainder_size < MINSIZE) {
3203 set_inuse_bit_at_offset(victim, size);
3204 set_arena_for_chunk(victim, av);
3205 check_malloced_chunk(av, victim, nb);
3206 return chunk2mem(victim);
3211 remainder = chunk_at_offset(victim, nb);
3213 unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
3214 remainder->bk = remainder->fd = unsorted_chunks(av);
3215 /* advertise as last remainder */
3216 if (in_smallbin_range(nb))
3217 av->last_remainder = remainder;
3219 set_head(victim, nb | PREV_INUSE);
3220 set_head(remainder, remainder_size | PREV_INUSE);
3221 set_foot(remainder, remainder_size);
3222 set_arena_for_chunk(victim, av);
3223 check_malloced_chunk(av, victim, nb);
3224 return chunk2mem(victim);
3231 If large enough, split off the chunk bordering the end of memory
3232 (held in av->top). Note that this is in accord with the best-fit
3233 search rule. In effect, av->top is treated as larger (and thus
3234 less well fitting) than any other available chunk since it can
3235 be extended to be as large as necessary (up to system
3238 We require that av->top always exists (i.e., has size >=
3239 MINSIZE) after initialization, so if it would otherwise be
3240 exhuasted by current request, it is replenished. (The main
3241 reason for ensuring it exists is that we may need MINSIZE space
3242 to put in fenceposts in sysmalloc.)
3246 size = chunksize(victim);
3248 if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {
3249 remainder_size = size - nb;
3250 remainder = chunk_at_offset(victim, nb);
3251 av->top = remainder;
3252 set_head(victim, nb | PREV_INUSE);
3253 set_head(remainder, remainder_size | PREV_INUSE);
3255 set_arena_for_chunk(victim, av);
3256 check_malloced_chunk(av, victim, nb);
3257 return chunk2mem(victim);
3261 If there is space available in fastbins, consolidate and retry,
3262 to possibly avoid expanding memory. This can occur only if nb is
3263 in smallbin range so we didn't consolidate upon entry.
3266 else if (have_fastchunks(av)) {
3267 assert(in_smallbin_range(nb));
3268 malloc_consolidate(av);
3269 idx = smallbin_index(nb); /* restore original bin index */
3273 Otherwise, relay to handle system-dependent cases
3276 return(NULL); // sysmalloc not supported
3281 ------------------------------ free ------------------------------
3285 _int_free(mstate av, Void_t* mem)
3287 mchunkptr p; /* chunk corresponding to mem */
3288 INTERNAL_SIZE_T size; /* its size */
3289 mfastbinptr* fb; /* associated fastbin */
3290 mchunkptr nextchunk; /* next contiguous chunk */
3291 INTERNAL_SIZE_T nextsize; /* its size */
3292 int nextinuse; /* true if nextchunk is used */
3293 INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
3294 mchunkptr bck; /* misc temp for linking */
3295 mchunkptr fwd; /* misc temp for linking */
3298 /* free(0) has no effect */
3301 size = chunksize(p);
3303 check_inuse_chunk(av, p);
3306 If eligible, place chunk on a fastbin so it can be found
3307 and used quickly in malloc.
3310 if ((unsigned long)(size) <= (unsigned long)(av->max_fast)
3314 If TRIM_FASTBINS set, don't place chunks
3315 bordering top into fastbins
3317 && (chunk_at_offset(p, size) != av->top)
3322 fb = &(av->fastbins[fastbin_index(size)]);
3328 Consolidate other non-mmapped chunks as they arrive.
3331 else if (!chunk_is_mmapped(p)) {
3332 nextchunk = chunk_at_offset(p, size);
3333 nextsize = chunksize(nextchunk);
3334 assert(nextsize > 0);
3336 /* consolidate backward */
3337 if (!prev_inuse(p)) {
3338 prevsize = p->prev_size;
3340 p = chunk_at_offset(p, -((long) prevsize));
3341 unlink(p, bck, fwd);
3344 if (nextchunk != av->top) {
3345 /* get and clear inuse bit */
3346 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
3348 /* consolidate forward */
3350 unlink(nextchunk, bck, fwd);
3353 clear_inuse_bit_at_offset(nextchunk, 0);
3356 Place the chunk in unsorted chunk list. Chunks are
3357 not placed into regular bins until after they have
3358 been given one chance to be used in malloc.
3361 bck = unsorted_chunks(av);
3368 set_head(p, size | PREV_INUSE);
3371 check_free_chunk(av, p);
3375 If the chunk borders the current high end of memory,
3376 consolidate into top
3381 set_head(p, size | PREV_INUSE);
3387 If freeing a large space, consolidate possibly-surrounding
3388 chunks. Then, if the total unused topmost memory exceeds trim
3389 threshold, ask malloc_trim to reduce top.
3391 Unless max_fast is 0, we don't know if there are fastbins
3392 bordering top, so we cannot tell for sure whether threshold
3393 has been reached unless fastbins are consolidated. But we
3394 don't want to consolidate on each free. As a compromise,
3395 consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
3399 if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
3400 if (have_fastchunks(av))
3401 malloc_consolidate(av);
3408 ------------------------- malloc_consolidate -------------------------
3410 malloc_consolidate is a specialized version of free() that tears
3411 down chunks held in fastbins. Free itself cannot be used for this
3412 purpose since, among other things, it might place chunks back onto
3413 fastbins. So, instead, we need to use a minor variant of the same
3416 Also, because this routine needs to be called the first time through
3417 malloc anyway, it turns out to be the perfect place to trigger
3418 initialization code.
3422 static void malloc_consolidate(mstate av)
3424 static void malloc_consolidate(av) mstate av;
3427 mfastbinptr* fb; /* current fastbin being consolidated */
3428 mfastbinptr* maxfb; /* last fastbin (for loop control) */
3429 mchunkptr p; /* current chunk being consolidated */
3430 mchunkptr nextp; /* next chunk to consolidate */
3431 mchunkptr unsorted_bin; /* bin header */
3432 mchunkptr first_unsorted; /* chunk to link to */
3434 /* These have same use as in free() */
3435 mchunkptr nextchunk;
3436 INTERNAL_SIZE_T size;
3437 INTERNAL_SIZE_T nextsize;
3438 INTERNAL_SIZE_T prevsize;
3444 If max_fast is 0, we know that av hasn't
3445 yet been initialized, in which case do so below
3448 if (av->max_fast != 0) {
3449 clear_fastchunks(av);
3451 unsorted_bin = unsorted_chunks(av);
3454 Remove each chunk from fast bin and consolidate it, placing it
3455 then in unsorted bin. Among other reasons for doing this,
3456 placing in unsorted bin avoids needing to calculate actual bins
3457 until malloc is sure that chunks aren't immediately going to be
3461 maxfb = &(av->fastbins[fastbin_index(av->max_fast)]);
3462 fb = &(av->fastbins[0]);
3464 if ( (p = *fb) != 0) {
3468 check_inuse_chunk(av, p);
3471 /* Slightly streamlined version of consolidation code in free() */
3472 size = p->size & ~(PREV_INUSE);
3473 nextchunk = chunk_at_offset(p, size);
3474 nextsize = chunksize(nextchunk);
3476 if (!prev_inuse(p)) {
3477 prevsize = p->prev_size;
3479 p = chunk_at_offset(p, -((long) prevsize));
3480 unlink(p, bck, fwd);
3483 if (nextchunk != av->top) {
3484 nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
3488 unlink(nextchunk, bck, fwd);
3490 clear_inuse_bit_at_offset(nextchunk, 0);
3492 first_unsorted = unsorted_bin->fd;
3493 unsorted_bin->fd = p;
3494 first_unsorted->bk = p;
3496 set_head(p, size | PREV_INUSE);
3497 p->bk = unsorted_bin;
3498 p->fd = first_unsorted;
3504 set_head(p, size | PREV_INUSE);
3508 } while ( (p = nextp) != 0);
3511 } while (fb++ != maxfb);
3514 malloc_init_state(av);
3515 check_malloc_state(av);
3520 ------------------------------ realloc ------------------------------
3524 _int_realloc(mstate av, Void_t* oldmem, size_t bytes)
3526 INTERNAL_SIZE_T nb; /* padded request size */
3528 mchunkptr oldp; /* chunk corresponding to oldmem */
3529 INTERNAL_SIZE_T oldsize; /* its size */
3531 mchunkptr newp; /* chunk to return */
3532 INTERNAL_SIZE_T newsize; /* its size */
3533 Void_t* newmem; /* corresponding user mem */
3535 mchunkptr next; /* next contiguous chunk after oldp */
3537 mchunkptr remainder; /* extra space at end of newp */
3538 unsigned long remainder_size; /* its size */
3540 mchunkptr bck; /* misc temp for linking */
3541 mchunkptr fwd; /* misc temp for linking */
3543 unsigned long copysize; /* bytes to copy */
3544 unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */
3545 INTERNAL_SIZE_T* s; /* copy source */
3546 INTERNAL_SIZE_T* d; /* copy destination */
3549 #if REALLOC_ZERO_BYTES_FREES
3551 _int_free(av, oldmem);
3556 /* realloc of null is supposed to be same as malloc */
3557 if (oldmem == 0) return _int_malloc(av, bytes);
3559 checked_request2size(bytes, nb);
3561 oldp = mem2chunk(oldmem);
3562 oldsize = chunksize(oldp);
3564 check_inuse_chunk(av, oldp);
3566 // force to act like not mmapped
3569 if ((unsigned long)(oldsize) >= (unsigned long)(nb)) {
3570 /* already big enough; split below */
3576 next = chunk_at_offset(oldp, oldsize);
3578 /* Try to expand forward into top */
3579 if (next == av->top &&
3580 (unsigned long)(newsize = oldsize + chunksize(next)) >=
3581 (unsigned long)(nb + MINSIZE)) {
3582 set_head_size(oldp, nb );
3583 av->top = chunk_at_offset(oldp, nb);
3584 set_head(av->top, (newsize - nb) | PREV_INUSE);
3585 check_inuse_chunk(av, oldp);
3586 set_arena_for_chunk(oldp, av);
3587 return chunk2mem(oldp);
3590 /* Try to expand forward into next chunk; split off remainder below */
3591 else if (next != av->top &&
3593 (unsigned long)(newsize = oldsize + chunksize(next)) >=
3594 (unsigned long)(nb)) {
3596 unlink(next, bck, fwd);
3599 /* allocate, copy, free */
3601 newmem = _int_malloc(av, nb - MALLOC_ALIGN_MASK);
3603 return 0; /* propagate failure */
3605 newp = mem2chunk(newmem);
3606 newsize = chunksize(newp);
3609 Avoid copy if newp is next chunk after oldp.
3617 Unroll copy of <= 36 bytes (72 if 8byte sizes)
3618 We know that contents have an odd number of
3619 INTERNAL_SIZE_T-sized words; minimally 3.
3622 copysize = oldsize - SIZE_SZ;
3623 s = (INTERNAL_SIZE_T*)(oldmem);
3624 d = (INTERNAL_SIZE_T*)(newmem);
3625 ncopies = copysize / sizeof(INTERNAL_SIZE_T);
3626 assert(ncopies >= 3);
3629 MALLOC_COPY(d, s, copysize);
3649 _int_free(av, oldmem);
3650 set_arena_for_chunk(newp, av);
3651 check_inuse_chunk(av, newp);
3652 return chunk2mem(newp);
3657 /* If possible, free extra space in old or extended chunk */
3659 assert((unsigned long)(newsize) >= (unsigned long)(nb));
3661 remainder_size = newsize - nb;
3663 if (remainder_size < MINSIZE) { /* not enough extra to split off */
3664 set_head_size(newp, newsize);
3665 set_inuse_bit_at_offset(newp, newsize);
3667 else { /* split remainder */
3668 remainder = chunk_at_offset(newp, nb);
3669 set_head_size(newp, nb );
3670 set_head(remainder, remainder_size | PREV_INUSE );
3671 /* Mark remainder as inuse so free() won't complain */
3672 set_inuse_bit_at_offset(remainder, remainder_size);
3673 set_arena_for_chunk(remainder, av);
3674 _int_free(av, chunk2mem(remainder));
3677 set_arena_for_chunk(newp, av);
3678 check_inuse_chunk(av, newp);
3679 return chunk2mem(newp);
3687 /* If !HAVE_MMAP, but chunk_is_mmapped, user must have overwritten mem */
3688 check_malloc_state(av);
3689 MALLOC_FAILURE_ACTION;
3695 ------------------------------ memalign ------------------------------
3699 _int_memalign(mstate av, size_t alignment, size_t bytes)
3701 INTERNAL_SIZE_T nb; /* padded request size */
3702 char* m; /* memory returned by malloc call */
3703 mchunkptr p; /* corresponding chunk */
3704 char* brk; /* alignment point within p */
3705 mchunkptr newp; /* chunk to return */
3706 INTERNAL_SIZE_T newsize; /* its size */
3707 INTERNAL_SIZE_T leadsize; /* leading space before alignment point */
3708 mchunkptr remainder; /* spare room at end to split off */
3709 unsigned long remainder_size; /* its size */
3710 INTERNAL_SIZE_T size;
3712 /* If need less alignment than we give anyway, just relay to malloc */
3714 if (alignment <= MALLOC_ALIGNMENT) return _int_malloc(av, bytes);
3716 /* Otherwise, ensure that it is at least a minimum chunk size */
3718 if (alignment < MINSIZE) alignment = MINSIZE;
3720 /* Make sure alignment is power of 2 (in case MINSIZE is not). */
3721 if ((alignment & (alignment - 1)) != 0) {
3722 size_t a = MALLOC_ALIGNMENT * 2;
3723 while ((unsigned long)a < (unsigned long)alignment) a <<= 1;
3727 checked_request2size(bytes, nb);
3730 Strategy: find a spot within that chunk that meets the alignment
3731 request, and then possibly free the leading and trailing space.
3735 /* Call malloc with worst case padding to hit alignment. */
3737 m = (char*)(_int_malloc(av, nb + alignment + MINSIZE));
3739 if (m == 0) return 0; /* propagate failure */
3743 if ((((unsigned long)(m)) % alignment) != 0) { /* misaligned */
3746 Find an aligned spot inside chunk. Since we need to give back
3747 leading space in a chunk of at least MINSIZE, if the first
3748 calculation places us at a spot with less than MINSIZE leader,
3749 we can move to the next aligned spot -- we've allocated enough
3750 total room so that this is always possible.
3753 brk = (char*)mem2chunk(((unsigned long)(m + alignment - 1)) &
3754 -((signed long) alignment));
3755 if ((unsigned long)(brk - (char*)(p)) < MINSIZE)
3758 newp = (mchunkptr)brk;
3759 leadsize = brk - (char*)(p);
3760 newsize = chunksize(p) - leadsize;
3762 /* For mmapped chunks, just adjust offset */
3763 if (chunk_is_mmapped(p)) {
3764 newp->prev_size = p->prev_size + leadsize;
3765 set_head(newp, newsize|IS_MMAPPED);
3766 set_arena_for_chunk(newp, av);
3767 return chunk2mem(newp);
3770 /* Otherwise, give back leader, use the rest */
3771 set_head(newp, newsize | PREV_INUSE );
3772 set_inuse_bit_at_offset(newp, newsize);
3773 set_head_size(p, leadsize);
3774 set_arena_for_chunk(p, av);
3775 _int_free(av, chunk2mem(p));
3778 assert (newsize >= nb &&
3779 (((unsigned long)(chunk2mem(p))) % alignment) == 0);
3782 /* Also give back spare room at the end */
3783 if (!chunk_is_mmapped(p)) {
3784 size = chunksize(p);
3785 if ((unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {
3786 remainder_size = size - nb;
3787 remainder = chunk_at_offset(p, nb);
3788 set_head(remainder, remainder_size | PREV_INUSE );
3789 set_head_size(p, nb);
3790 set_arena_for_chunk(remainder, av);
3791 _int_free(av, chunk2mem(remainder));
3795 set_arena_for_chunk(p, av);
3796 check_inuse_chunk(av, p);
3797 return chunk2mem(p);
3802 ------------------------------ calloc ------------------------------
3806 Void_t* cALLOc(cvmx_arena_list_t arena_list, size_t n_elements, size_t elem_size)
3808 Void_t* cALLOc(n_elements, elem_size) size_t n_elements; size_t elem_size;
3812 unsigned long clearsize;
3813 unsigned long nclears;
3816 Void_t* mem = public_mALLOc(arena_list, n_elements * elem_size);
3823 Unroll clear of <= 36 bytes (72 if 8byte sizes)
3824 We know that contents have an odd number of
3825 INTERNAL_SIZE_T-sized words; minimally 3.
3828 d = (INTERNAL_SIZE_T*)mem;
3829 clearsize = chunksize(p) - SIZE_SZ;
3830 nclears = clearsize / sizeof(INTERNAL_SIZE_T);
3831 assert(nclears >= 3);
3834 MALLOC_ZERO(d, clearsize);
3861 ------------------------- malloc_usable_size -------------------------
3865 size_t mUSABLe(Void_t* mem)
3867 size_t mUSABLe(mem) Void_t* mem;
3873 if (chunk_is_mmapped(p))
3874 return chunksize(p) - 3*SIZE_SZ; /* updated size for adding arena_ptr */
3876 return chunksize(p) - 2*SIZE_SZ; /* updated size for adding arena_ptr */
3882 ------------------------------ mallinfo ------------------------------
3885 struct mallinfo mALLINFo(mstate av)
3891 INTERNAL_SIZE_T avail;
3892 INTERNAL_SIZE_T fastavail;
3896 /* Ensure initialization */
3897 if (av->top == 0) malloc_consolidate(av);
3899 check_malloc_state(av);
3901 /* Account for top */
3902 avail = chunksize(av->top);
3903 nblocks = 1; /* top always exists */
3905 /* traverse fastbins */
3909 for (i = 0; i < NFASTBINS; ++i) {
3910 for (p = av->fastbins[i]; p != 0; p = p->fd) {
3912 fastavail += chunksize(p);
3918 /* traverse regular bins */
3919 for (i = 1; i < NBINS; ++i) {
3921 for (p = last(b); p != b; p = p->bk) {
3923 avail += chunksize(p);
3927 mi.smblks = nfastblocks;
3928 mi.ordblks = nblocks;
3929 mi.fordblks = avail;
3930 mi.uordblks = av->system_mem - avail;
3931 mi.arena = av->system_mem;
3932 mi.fsmblks = fastavail;
3933 mi.keepcost = chunksize(av->top);
3938 ------------------------------ malloc_stats ------------------------------
3947 ------------------------------ mallopt ------------------------------
3952 int mALLOPt(int param_number, int value)
3954 int mALLOPt(param_number, value) int param_number; int value;
3962 -------------------- Alternative MORECORE functions --------------------
3967 General Requirements for MORECORE.
3969 The MORECORE function must have the following properties:
3971 If MORECORE_CONTIGUOUS is false:
3973 * MORECORE must allocate in multiples of pagesize. It will
3974 only be called with arguments that are multiples of pagesize.
3976 * MORECORE(0) must return an address that is at least
3977 MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
3979 else (i.e. If MORECORE_CONTIGUOUS is true):
3981 * Consecutive calls to MORECORE with positive arguments
3982 return increasing addresses, indicating that space has been
3983 contiguously extended.
3985 * MORECORE need not allocate in multiples of pagesize.
3986 Calls to MORECORE need not have args of multiples of pagesize.
3988 * MORECORE need not page-align.
3992 * MORECORE may allocate more memory than requested. (Or even less,
3993 but this will generally result in a malloc failure.)
3995 * MORECORE must not allocate memory when given argument zero, but
3996 instead return one past the end address of memory from previous
3997 nonzero call. This malloc does NOT call MORECORE(0)
3998 until at least one call with positive arguments is made, so
3999 the initial value returned is not important.
4001 * Even though consecutive calls to MORECORE need not return contiguous
4002 addresses, it must be OK for malloc'ed chunks to span multiple
4003 regions in those cases where they do happen to be contiguous.
4005 * MORECORE need not handle negative arguments -- it may instead
4006 just return MORECORE_FAILURE when given negative arguments.
4007 Negative arguments are always multiples of pagesize. MORECORE
4008 must not misinterpret negative args as large positive unsigned
4009 args. You can suppress all such calls from even occurring by defining
4010 MORECORE_CANNOT_TRIM,
4012 There is some variation across systems about the type of the
4013 argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
4014 actually be size_t, because sbrk supports negative args, so it is
4015 normally the signed type of the same width as size_t (sometimes
4016 declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much
4017 matter though. Internally, we use "long" as arguments, which should
4018 work across all reasonable possibilities.
4020 Additionally, if MORECORE ever returns failure for a positive
4021 request, and HAVE_MMAP is true, then mmap is used as a noncontiguous
4022 system allocator. This is a useful backup strategy for systems with
4023 holes in address spaces -- in this case sbrk cannot contiguously
4024 expand the heap, but mmap may be able to map noncontiguous space.
4026 If you'd like mmap to ALWAYS be used, you can define MORECORE to be
4027 a function that always returns MORECORE_FAILURE.
4029 If you are using this malloc with something other than sbrk (or its
4030 emulation) to supply memory regions, you probably want to set
4031 MORECORE_CONTIGUOUS as false. As an example, here is a custom
4032 allocator kindly contributed for pre-OSX macOS. It uses virtually
4033 but not necessarily physically contiguous non-paged memory (locked
4034 in, present and won't get swapped out). You can use it by
4035 uncommenting this section, adding some #includes, and setting up the
4036 appropriate defines above:
4038 #define MORECORE osMoreCore
4039 #define MORECORE_CONTIGUOUS 0
4041 There is also a shutdown routine that should somehow be called for
4042 cleanup upon program exit.
4044 #define MAX_POOL_ENTRIES 100
4045 #define MINIMUM_MORECORE_SIZE (64 * 1024)
4046 static int next_os_pool;
4047 void *our_os_pools[MAX_POOL_ENTRIES];
4049 void *osMoreCore(int size)
4052 static void *sbrk_top = 0;
4056 if (size < MINIMUM_MORECORE_SIZE)
4057 size = MINIMUM_MORECORE_SIZE;
4058 if (CurrentExecutionLevel() == kTaskLevel)
4059 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4062 return (void *) MORECORE_FAILURE;
4064 // save ptrs so they can be freed during cleanup
4065 our_os_pools[next_os_pool] = ptr;
4067 ptr = (void *) ((((unsigned long) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4068 sbrk_top = (char *) ptr + size;
4073 // we don't currently support shrink behavior
4074 return (void *) MORECORE_FAILURE;
4082 // cleanup any allocated memory pools
4083 // called as last thing before shutting down driver
4085 void osCleanupMem(void)
4089 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4092 PoolDeallocate(*ptr);
4101 /* ------------------------------------------------------------
4104 [see ftp://g.oswego.edu/pub/misc/malloc.c for the history of dlmalloc]
projects / FreeBSD / releng / 10.0.git / blob