1232809Sjmallett/* 2232809SjmallettCopyright (c) 2001 Wolfram Gloger 3232809SjmallettCopyright (c) 2006 Cavium networks 4232809Sjmallett 5232809SjmallettPermission to use, copy, modify, distribute, and sell this software 6232809Sjmallettand its documentation for any purpose is hereby granted without fee, 7232809Sjmallettprovided that (i) the above copyright notices and this permission 8232809Sjmallettnotice appear in all copies of the software and related documentation, 9232809Sjmallettand (ii) the name of Wolfram Gloger may not be used in any advertising 10232809Sjmallettor publicity relating to the software. 11232809Sjmallett 12232809SjmallettTHE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 13232809SjmallettEXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 14232809SjmallettWARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 15232809Sjmallett 16232809SjmallettIN NO EVENT SHALL WOLFRAM GLOGER BE LIABLE FOR ANY SPECIAL, 17232809SjmallettINCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY 18232809SjmallettDAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 19232809SjmallettWHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY 20232809SjmallettOF LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 21232809SjmallettPERFORMANCE OF THIS SOFTWARE. 22232809Sjmallett*/ 23232809Sjmallett 24232809Sjmallett/* 25232809Sjmallett This is a version (aka ptmalloc2) of malloc/free/realloc written by 26232809Sjmallett Doug Lea and adapted to multiple threads/arenas by Wolfram Gloger. 27232809Sjmallett 28232809Sjmallett* Version ptmalloc2-20011215 29232809Sjmallett $Id: malloc.c 30481 2007-12-05 21:46:59Z rfranz $ 30232809Sjmallett based on: 31232809Sjmallett VERSION 2.7.1pre1 Sat May 12 07:41:21 2001 Doug Lea (dl at gee) 32232809Sjmallett 33232809Sjmallett Note: There may be an updated version of this malloc obtainable at 34232809Sjmallett http://www.malloc.de/malloc/ptmalloc2.tar.gz 35232809Sjmallett Check before installing! 36232809Sjmallett 37232809Sjmallett* Quickstart 38232809Sjmallett 39232809Sjmallett In order to compile this implementation, a Makefile is provided with 40232809Sjmallett the ptmalloc2 distribution, which has pre-defined targets for some 41232809Sjmallett popular systems (e.g. "make posix" for Posix threads). All that is 42232809Sjmallett typically required with regard to compiler flags is the selection of 43232809Sjmallett the thread package via defining one out of USE_PTHREADS, USE_THR or 44232809Sjmallett USE_SPROC. Check the thread-m.h file for what effects this has. 45232809Sjmallett Many/most systems will additionally require USE_TSD_DATA_HACK to be 46232809Sjmallett defined, so this is the default for "make posix". 47232809Sjmallett 48232809Sjmallett* Why use this malloc? 49232809Sjmallett 50232809Sjmallett This is not the fastest, most space-conserving, most portable, or 51232809Sjmallett most tunable malloc ever written. However it is among the fastest 52232809Sjmallett while also being among the most space-conserving, portable and tunable. 53232809Sjmallett Consistent balance across these factors results in a good general-purpose 54232809Sjmallett allocator for malloc-intensive programs. 55232809Sjmallett 56232809Sjmallett The main properties of the algorithms are: 57232809Sjmallett * For large (>= 512 bytes) requests, it is a pure best-fit allocator, 58232809Sjmallett with ties normally decided via FIFO (i.e. least recently used). 59232809Sjmallett * For small (<= 64 bytes by default) requests, it is a caching 60232809Sjmallett allocator, that maintains pools of quickly recycled chunks. 61232809Sjmallett * In between, and for combinations of large and small requests, it does 62232809Sjmallett the best it can trying to meet both goals at once. 63232809Sjmallett * For very large requests (>= 128KB by default), it relies on system 64232809Sjmallett memory mapping facilities, if supported. 65232809Sjmallett 66232809Sjmallett For a longer but slightly out of date high-level description, see 67232809Sjmallett http://gee.cs.oswego.edu/dl/html/malloc.html 68232809Sjmallett 69232809Sjmallett You may already by default be using a C library containing a malloc 70232809Sjmallett that is based on some version of this malloc (for example in 71232809Sjmallett linux). You might still want to use the one in this file in order to 72232809Sjmallett customize settings or to avoid overheads associated with library 73232809Sjmallett versions. 74232809Sjmallett 75232809Sjmallett* Contents, described in more detail in "description of public routines" below. 76232809Sjmallett 77232809Sjmallett Standard (ANSI/SVID/...) functions: 78232809Sjmallett malloc(size_t n); 79232809Sjmallett calloc(size_t n_elements, size_t element_size); 80232809Sjmallett free(Void_t* p); 81232809Sjmallett realloc(Void_t* p, size_t n); 82232809Sjmallett memalign(size_t alignment, size_t n); 83232809Sjmallett valloc(size_t n); 84232809Sjmallett mallinfo() 85232809Sjmallett mallopt(int parameter_number, int parameter_value) 86232809Sjmallett 87232809Sjmallett Additional functions: 88232809Sjmallett independent_calloc(size_t n_elements, size_t size, Void_t* chunks[]); 89232809Sjmallett independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]); 90232809Sjmallett pvalloc(size_t n); 91232809Sjmallett cfree(Void_t* p); 92232809Sjmallett malloc_trim(size_t pad); 93232809Sjmallett malloc_usable_size(Void_t* p); 94232809Sjmallett malloc_stats(); 95232809Sjmallett 96232809Sjmallett* Vital statistics: 97232809Sjmallett 98232809Sjmallett Supported pointer representation: 4 or 8 bytes 99232809Sjmallett Supported size_t representation: 4 or 8 bytes 100232809Sjmallett Note that size_t is allowed to be 4 bytes even if pointers are 8. 101232809Sjmallett You can adjust this by defining INTERNAL_SIZE_T 102232809Sjmallett 103232809Sjmallett Alignment: 2 * sizeof(size_t) (default) 104232809Sjmallett (i.e., 8 byte alignment with 4byte size_t). This suffices for 105232809Sjmallett nearly all current machines and C compilers. However, you can 106232809Sjmallett define MALLOC_ALIGNMENT to be wider than this if necessary. 107232809Sjmallett 108232809Sjmallett Minimum overhead per allocated chunk: 4 or 8 bytes 109232809Sjmallett Each malloced chunk has a hidden word of overhead holding size 110232809Sjmallett and status information. 111232809Sjmallett 112232809Sjmallett Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead) 113232809Sjmallett 8-byte ptrs: 24/32 bytes (including, 4/8 overhead) 114232809Sjmallett 115232809Sjmallett When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte 116232809Sjmallett ptrs but 4 byte size) or 24 (for 8/8) additional bytes are 117232809Sjmallett needed; 4 (8) for a trailing size field and 8 (16) bytes for 118232809Sjmallett free list pointers. Thus, the minimum allocatable size is 119232809Sjmallett 16/24/32 bytes. 120232809Sjmallett 121232809Sjmallett Even a request for zero bytes (i.e., malloc(0)) returns a 122232809Sjmallett pointer to something of the minimum allocatable size. 123232809Sjmallett 124232809Sjmallett The maximum overhead wastage (i.e., number of extra bytes 125232809Sjmallett allocated than were requested in malloc) is less than or equal 126232809Sjmallett to the minimum size, except for requests >= mmap_threshold that 127232809Sjmallett are serviced via mmap(), where the worst case wastage is 2 * 128232809Sjmallett sizeof(size_t) bytes plus the remainder from a system page (the 129232809Sjmallett minimal mmap unit); typically 4096 or 8192 bytes. 130232809Sjmallett 131232809Sjmallett Maximum allocated size: 4-byte size_t: 2^32 minus about two pages 132232809Sjmallett 8-byte size_t: 2^64 minus about two pages 133232809Sjmallett 134232809Sjmallett It is assumed that (possibly signed) size_t values suffice to 135232809Sjmallett represent chunk sizes. `Possibly signed' is due to the fact 136232809Sjmallett that `size_t' may be defined on a system as either a signed or 137232809Sjmallett an unsigned type. The ISO C standard says that it must be 138232809Sjmallett unsigned, but a few systems are known not to adhere to this. 139232809Sjmallett Additionally, even when size_t is unsigned, sbrk (which is by 140232809Sjmallett default used to obtain memory from system) accepts signed 141232809Sjmallett arguments, and may not be able to handle size_t-wide arguments 142232809Sjmallett with negative sign bit. Generally, values that would 143232809Sjmallett appear as negative after accounting for overhead and alignment 144232809Sjmallett are supported only via mmap(), which does not have this 145232809Sjmallett limitation. 146232809Sjmallett 147232809Sjmallett Requests for sizes outside the allowed range will perform an optional 148232809Sjmallett failure action and then return null. (Requests may also 149232809Sjmallett also fail because a system is out of memory.) 150232809Sjmallett 151232809Sjmallett Thread-safety: thread-safe unless NO_THREADS is defined 152232809Sjmallett 153232809Sjmallett Compliance: I believe it is compliant with the 1997 Single Unix Specification 154232809Sjmallett (See http://www.opennc.org). Also SVID/XPG, ANSI C, and probably 155232809Sjmallett others as well. 156232809Sjmallett 157232809Sjmallett* Synopsis of compile-time options: 158232809Sjmallett 159232809Sjmallett People have reported using previous versions of this malloc on all 160232809Sjmallett versions of Unix, sometimes by tweaking some of the defines 161232809Sjmallett below. It has been tested most extensively on Solaris and 162232809Sjmallett Linux. It is also reported to work on WIN32 platforms. 163232809Sjmallett People also report using it in stand-alone embedded systems. 164232809Sjmallett 165232809Sjmallett The implementation is in straight, hand-tuned ANSI C. It is not 166232809Sjmallett at all modular. (Sorry!) It uses a lot of macros. To be at all 167232809Sjmallett usable, this code should be compiled using an optimizing compiler 168232809Sjmallett (for example gcc -O3) that can simplify expressions and control 169232809Sjmallett paths. (FAQ: some macros import variables as arguments rather than 170232809Sjmallett declare locals because people reported that some debuggers 171232809Sjmallett otherwise get confused.) 172232809Sjmallett 173232809Sjmallett OPTION DEFAULT VALUE 174232809Sjmallett 175232809Sjmallett Compilation Environment options: 176232809Sjmallett 177232809Sjmallett __STD_C derived from C compiler defines 178232809Sjmallett WIN32 NOT defined 179232809Sjmallett HAVE_MEMCPY defined 180232809Sjmallett USE_MEMCPY 1 if HAVE_MEMCPY is defined 181232809Sjmallett HAVE_MMAP defined as 1 182232809Sjmallett MMAP_CLEARS 1 183232809Sjmallett HAVE_MREMAP 0 unless linux defined 184232809Sjmallett USE_ARENAS the same as HAVE_MMAP 185232809Sjmallett malloc_getpagesize derived from system #includes, or 4096 if not 186232809Sjmallett HAVE_USR_INCLUDE_MALLOC_H NOT defined 187232809Sjmallett LACKS_UNISTD_H NOT defined unless WIN32 188232809Sjmallett LACKS_SYS_PARAM_H NOT defined unless WIN32 189232809Sjmallett LACKS_SYS_MMAN_H NOT defined unless WIN32 190232809Sjmallett 191232809Sjmallett Changing default word sizes: 192232809Sjmallett 193232809Sjmallett INTERNAL_SIZE_T size_t 194232809Sjmallett MALLOC_ALIGNMENT 2 * sizeof(INTERNAL_SIZE_T) 195232809Sjmallett 196232809Sjmallett Configuration and functionality options: 197232809Sjmallett 198232809Sjmallett USE_DL_PREFIX NOT defined 199232809Sjmallett USE_PUBLIC_MALLOC_WRAPPERS NOT defined 200232809Sjmallett USE_MALLOC_LOCK NOT defined 201232809Sjmallett MALLOC_DEBUG NOT defined 202232809Sjmallett REALLOC_ZERO_BYTES_FREES 1 203232809Sjmallett MALLOC_FAILURE_ACTION errno = ENOMEM, if __STD_C defined, else no-op 204232809Sjmallett TRIM_FASTBINS 0 205232809Sjmallett FIRST_SORTED_BIN_SIZE 512 206232809Sjmallett 207232809Sjmallett Options for customizing MORECORE: 208232809Sjmallett 209232809Sjmallett MORECORE sbrk 210232809Sjmallett MORECORE_FAILURE -1 211232809Sjmallett MORECORE_CONTIGUOUS 1 212232809Sjmallett MORECORE_CANNOT_TRIM NOT defined 213232809Sjmallett MORECORE_CLEARS 1 214232809Sjmallett MMAP_AS_MORECORE_SIZE (1024 * 1024) 215232809Sjmallett 216232809Sjmallett Tuning options that are also dynamically changeable via mallopt: 217232809Sjmallett 218232809Sjmallett DEFAULT_MXFAST 64 219232809Sjmallett DEFAULT_TRIM_THRESHOLD 128 * 1024 220232809Sjmallett DEFAULT_TOP_PAD 0 221232809Sjmallett DEFAULT_MMAP_THRESHOLD 128 * 1024 222232809Sjmallett DEFAULT_MMAP_MAX 65536 223232809Sjmallett 224232809Sjmallett There are several other #defined constants and macros that you 225232809Sjmallett probably don't want to touch unless you are extending or adapting malloc. */ 226232809Sjmallett 227232809Sjmallett/* 228232809Sjmallett __STD_C should be nonzero if using ANSI-standard C compiler, a C++ 229232809Sjmallett compiler, or a C compiler sufficiently close to ANSI to get away 230232809Sjmallett with it. 231232809Sjmallett*/ 232232809Sjmallett 233232809Sjmallett#include "cvmx-config.h" 234232809Sjmallett#include "cvmx.h" 235232809Sjmallett#include "cvmx-spinlock.h" 236232809Sjmallett#include "cvmx-malloc.h" 237232809Sjmallett 238232809Sjmallett 239232809Sjmallett#ifndef __STD_C 240232809Sjmallett#if defined(__STDC__) || defined(__cplusplus) 241232809Sjmallett#define __STD_C 1 242232809Sjmallett#else 243232809Sjmallett#define __STD_C 0 244232809Sjmallett#endif 245232809Sjmallett#endif /*__STD_C*/ 246232809Sjmallett 247232809Sjmallett 248232809Sjmallett/* 249232809Sjmallett Void_t* is the pointer type that malloc should say it returns 250232809Sjmallett*/ 251232809Sjmallett 252232809Sjmallett#ifndef Void_t 253232809Sjmallett#if 1 254232809Sjmallett#define Void_t void 255232809Sjmallett#else 256232809Sjmallett#define Void_t char 257232809Sjmallett#endif 258232809Sjmallett#endif /*Void_t*/ 259232809Sjmallett 260232809Sjmallett 261232809Sjmallett#ifdef __cplusplus 262232809Sjmallettextern "C" { 263232809Sjmallett#endif 264232809Sjmallett 265232809Sjmallett/* define LACKS_UNISTD_H if your system does not have a <unistd.h>. */ 266232809Sjmallett 267232809Sjmallett/* #define LACKS_UNISTD_H */ 268232809Sjmallett 269232809Sjmallett#ifndef LACKS_UNISTD_H 270232809Sjmallett#include <unistd.h> 271232809Sjmallett#endif 272232809Sjmallett 273232809Sjmallett/* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. */ 274232809Sjmallett 275232809Sjmallett/* #define LACKS_SYS_PARAM_H */ 276232809Sjmallett 277232809Sjmallett 278232809Sjmallett#include <stdio.h> /* needed for malloc_stats */ 279232809Sjmallett#include <errno.h> /* needed for optional MALLOC_FAILURE_ACTION */ 280232809Sjmallett 281232809Sjmallett 282232809Sjmallett/* 283232809Sjmallett Debugging: 284232809Sjmallett 285232809Sjmallett Because freed chunks may be overwritten with bookkeeping fields, this 286232809Sjmallett malloc will often die when freed memory is overwritten by user 287232809Sjmallett programs. This can be very effective (albeit in an annoying way) 288232809Sjmallett in helping track down dangling pointers. 289232809Sjmallett 290232809Sjmallett If you compile with -DMALLOC_DEBUG, a number of assertion checks are 291232809Sjmallett enabled that will catch more memory errors. You probably won't be 292232809Sjmallett able to make much sense of the actual assertion errors, but they 293232809Sjmallett should help you locate incorrectly overwritten memory. The checking 294232809Sjmallett is fairly extensive, and will slow down execution 295232809Sjmallett noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set 296232809Sjmallett will attempt to check every non-mmapped allocated and free chunk in 297232809Sjmallett the course of computing the summmaries. (By nature, mmapped regions 298232809Sjmallett cannot be checked very much automatically.) 299232809Sjmallett 300232809Sjmallett Setting MALLOC_DEBUG may also be helpful if you are trying to modify 301232809Sjmallett this code. The assertions in the check routines spell out in more 302232809Sjmallett detail the assumptions and invariants underlying the algorithms. 303232809Sjmallett 304232809Sjmallett Setting MALLOC_DEBUG does NOT provide an automated mechanism for 305232809Sjmallett checking that all accesses to malloced memory stay within their 306232809Sjmallett bounds. However, there are several add-ons and adaptations of this 307232809Sjmallett or other mallocs available that do this. 308232809Sjmallett*/ 309232809Sjmallett 310232809Sjmallett#define MALLOC_DEBUG 1 311232809Sjmallett#if MALLOC_DEBUG 312232809Sjmallett#include <assert.h> 313232809Sjmallett#else 314232809Sjmallett#define assert(x) ((void)0) 315232809Sjmallett#endif 316232809Sjmallett 317232809Sjmallett 318232809Sjmallett/* 319232809Sjmallett INTERNAL_SIZE_T is the word-size used for internal bookkeeping 320232809Sjmallett of chunk sizes. 321232809Sjmallett 322232809Sjmallett The default version is the same as size_t. 323232809Sjmallett 324232809Sjmallett While not strictly necessary, it is best to define this as an 325232809Sjmallett unsigned type, even if size_t is a signed type. This may avoid some 326232809Sjmallett artificial size limitations on some systems. 327232809Sjmallett 328232809Sjmallett On a 64-bit machine, you may be able to reduce malloc overhead by 329232809Sjmallett defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the 330232809Sjmallett expense of not being able to handle more than 2^32 of malloced 331232809Sjmallett space. If this limitation is acceptable, you are encouraged to set 332232809Sjmallett this unless you are on a platform requiring 16byte alignments. In 333232809Sjmallett this case the alignment requirements turn out to negate any 334232809Sjmallett potential advantages of decreasing size_t word size. 335232809Sjmallett 336232809Sjmallett Implementors: Beware of the possible combinations of: 337232809Sjmallett - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits, 338232809Sjmallett and might be the same width as int or as long 339232809Sjmallett - size_t might have different width and signedness as INTERNAL_SIZE_T 340232809Sjmallett - int and long might be 32 or 64 bits, and might be the same width 341232809Sjmallett To deal with this, most comparisons and difference computations 342232809Sjmallett among INTERNAL_SIZE_Ts should cast them to unsigned long, being 343232809Sjmallett aware of the fact that casting an unsigned int to a wider long does 344232809Sjmallett not sign-extend. (This also makes checking for negative numbers 345232809Sjmallett awkward.) Some of these casts result in harmless compiler warnings 346232809Sjmallett on some systems. 347232809Sjmallett*/ 348232809Sjmallett 349232809Sjmallett#ifndef INTERNAL_SIZE_T 350232809Sjmallett#define INTERNAL_SIZE_T size_t 351232809Sjmallett#endif 352232809Sjmallett 353232809Sjmallett/* The corresponding word size */ 354232809Sjmallett#define SIZE_SZ (sizeof(INTERNAL_SIZE_T)) 355232809Sjmallett 356232809Sjmallett 357232809Sjmallett/* 358232809Sjmallett MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks. 359232809Sjmallett It must be a power of two at least 2 * SIZE_SZ, even on machines 360232809Sjmallett for which smaller alignments would suffice. It may be defined as 361232809Sjmallett larger than this though. Note however that code and data structures 362232809Sjmallett are optimized for the case of 8-byte alignment. 363232809Sjmallett*/ 364232809Sjmallett 365232809Sjmallett 366232809Sjmallett#ifndef MALLOC_ALIGNMENT 367232809Sjmallett#define MALLOC_ALIGNMENT (2 * SIZE_SZ) 368232809Sjmallett#endif 369232809Sjmallett 370232809Sjmallett/* The corresponding bit mask value */ 371232809Sjmallett#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1) 372232809Sjmallett 373232809Sjmallett 374232809Sjmallett 375232809Sjmallett/* 376232809Sjmallett REALLOC_ZERO_BYTES_FREES should be set if a call to 377232809Sjmallett realloc with zero bytes should be the same as a call to free. 378232809Sjmallett This is required by the C standard. Otherwise, since this malloc 379232809Sjmallett returns a unique pointer for malloc(0), so does realloc(p, 0). 380232809Sjmallett*/ 381232809Sjmallett 382232809Sjmallett#ifndef REALLOC_ZERO_BYTES_FREES 383232809Sjmallett#define REALLOC_ZERO_BYTES_FREES 1 384232809Sjmallett#endif 385232809Sjmallett 386232809Sjmallett/* 387232809Sjmallett TRIM_FASTBINS controls whether free() of a very small chunk can 388232809Sjmallett immediately lead to trimming. Setting to true (1) can reduce memory 389232809Sjmallett footprint, but will almost always slow down programs that use a lot 390232809Sjmallett of small chunks. 391232809Sjmallett 392232809Sjmallett Define this only if you are willing to give up some speed to more 393232809Sjmallett aggressively reduce system-level memory footprint when releasing 394232809Sjmallett memory in programs that use many small chunks. You can get 395232809Sjmallett essentially the same effect by setting MXFAST to 0, but this can 396232809Sjmallett lead to even greater slowdowns in programs using many small chunks. 397232809Sjmallett TRIM_FASTBINS is an in-between compile-time option, that disables 398232809Sjmallett only those chunks bordering topmost memory from being placed in 399232809Sjmallett fastbins. 400232809Sjmallett*/ 401232809Sjmallett 402232809Sjmallett#ifndef TRIM_FASTBINS 403232809Sjmallett#define TRIM_FASTBINS 0 404232809Sjmallett#endif 405232809Sjmallett 406232809Sjmallett 407232809Sjmallett/* 408232809Sjmallett USE_DL_PREFIX will prefix all public routines with the string 'dl'. 409232809Sjmallett This is necessary when you only want to use this malloc in one part 410232809Sjmallett of a program, using your regular system malloc elsewhere. 411232809Sjmallett*/ 412232809Sjmallett 413232809Sjmallett#define USE_DL_PREFIX 414232809Sjmallett 415232809Sjmallett 416232809Sjmallett/* 417232809Sjmallett Two-phase name translation. 418232809Sjmallett All of the actual routines are given mangled names. 419232809Sjmallett When wrappers are used, they become the public callable versions. 420232809Sjmallett When DL_PREFIX is used, the callable names are prefixed. 421232809Sjmallett*/ 422232809Sjmallett 423232809Sjmallett#ifdef USE_DL_PREFIX 424232809Sjmallett#define public_cALLOc cvmx_calloc 425232809Sjmallett#define public_fREe cvmx_free 426232809Sjmallett#define public_cFREe dlcfree 427232809Sjmallett#define public_mALLOc cvmx_malloc 428232809Sjmallett#define public_mEMALIGn cvmx_memalign 429232809Sjmallett#define public_rEALLOc cvmx_realloc 430232809Sjmallett#define public_vALLOc dlvalloc 431232809Sjmallett#define public_pVALLOc dlpvalloc 432232809Sjmallett#define public_mALLINFo dlmallinfo 433232809Sjmallett#define public_mALLOPt dlmallopt 434232809Sjmallett#define public_mTRIm dlmalloc_trim 435232809Sjmallett#define public_mSTATs dlmalloc_stats 436232809Sjmallett#define public_mUSABLe dlmalloc_usable_size 437232809Sjmallett#define public_iCALLOc dlindependent_calloc 438232809Sjmallett#define public_iCOMALLOc dlindependent_comalloc 439232809Sjmallett#define public_gET_STATe dlget_state 440232809Sjmallett#define public_sET_STATe dlset_state 441232809Sjmallett#else /* USE_DL_PREFIX */ 442232809Sjmallett#ifdef _LIBC 443232809Sjmallett#error _LIBC defined and should not be 444232809Sjmallett/* Special defines for the GNU C library. */ 445232809Sjmallett#define public_cALLOc __libc_calloc 446232809Sjmallett#define public_fREe __libc_free 447232809Sjmallett#define public_cFREe __libc_cfree 448232809Sjmallett#define public_mALLOc __libc_malloc 449232809Sjmallett#define public_mEMALIGn __libc_memalign 450232809Sjmallett#define public_rEALLOc __libc_realloc 451232809Sjmallett#define public_vALLOc __libc_valloc 452232809Sjmallett#define public_pVALLOc __libc_pvalloc 453232809Sjmallett#define public_mALLINFo __libc_mallinfo 454232809Sjmallett#define public_mALLOPt __libc_mallopt 455232809Sjmallett#define public_mTRIm __malloc_trim 456232809Sjmallett#define public_mSTATs __malloc_stats 457232809Sjmallett#define public_mUSABLe __malloc_usable_size 458232809Sjmallett#define public_iCALLOc __libc_independent_calloc 459232809Sjmallett#define public_iCOMALLOc __libc_independent_comalloc 460232809Sjmallett#define public_gET_STATe __malloc_get_state 461232809Sjmallett#define public_sET_STATe __malloc_set_state 462232809Sjmallett#define malloc_getpagesize __getpagesize() 463232809Sjmallett#define open __open 464232809Sjmallett#define mmap __mmap 465232809Sjmallett#define munmap __munmap 466232809Sjmallett#define mremap __mremap 467232809Sjmallett#define mprotect __mprotect 468232809Sjmallett#define MORECORE (*__morecore) 469232809Sjmallett#define MORECORE_FAILURE 0 470232809Sjmallett 471232809SjmallettVoid_t * __default_morecore (ptrdiff_t); 472232809SjmallettVoid_t *(*__morecore)(ptrdiff_t) = __default_morecore; 473232809Sjmallett 474232809Sjmallett#else /* !_LIBC */ 475232809Sjmallett#define public_cALLOc calloc 476232809Sjmallett#define public_fREe free 477232809Sjmallett#define public_cFREe cfree 478232809Sjmallett#define public_mALLOc malloc 479232809Sjmallett#define public_mEMALIGn memalign 480232809Sjmallett#define public_rEALLOc realloc 481232809Sjmallett#define public_vALLOc valloc 482232809Sjmallett#define public_pVALLOc pvalloc 483232809Sjmallett#define public_mALLINFo mallinfo 484232809Sjmallett#define public_mALLOPt mallopt 485232809Sjmallett#define public_mTRIm malloc_trim 486232809Sjmallett#define public_mSTATs malloc_stats 487232809Sjmallett#define public_mUSABLe malloc_usable_size 488232809Sjmallett#define public_iCALLOc independent_calloc 489232809Sjmallett#define public_iCOMALLOc independent_comalloc 490232809Sjmallett#define public_gET_STATe malloc_get_state 491232809Sjmallett#define public_sET_STATe malloc_set_state 492232809Sjmallett#endif /* _LIBC */ 493232809Sjmallett#endif /* USE_DL_PREFIX */ 494232809Sjmallett 495232809Sjmallett 496232809Sjmallett/* 497232809Sjmallett HAVE_MEMCPY should be defined if you are not otherwise using 498232809Sjmallett ANSI STD C, but still have memcpy and memset in your C library 499232809Sjmallett and want to use them in calloc and realloc. Otherwise simple 500232809Sjmallett macro versions are defined below. 501232809Sjmallett 502232809Sjmallett USE_MEMCPY should be defined as 1 if you actually want to 503232809Sjmallett have memset and memcpy called. People report that the macro 504232809Sjmallett versions are faster than libc versions on some systems. 505232809Sjmallett 506232809Sjmallett Even if USE_MEMCPY is set to 1, loops to copy/clear small chunks 507232809Sjmallett (of <= 36 bytes) are manually unrolled in realloc and calloc. 508232809Sjmallett*/ 509232809Sjmallett 510232809Sjmallett#define HAVE_MEMCPY 511232809Sjmallett 512232809Sjmallett#ifndef USE_MEMCPY 513232809Sjmallett#ifdef HAVE_MEMCPY 514232809Sjmallett#define USE_MEMCPY 1 515232809Sjmallett#else 516232809Sjmallett#define USE_MEMCPY 0 517232809Sjmallett#endif 518232809Sjmallett#endif 519232809Sjmallett 520232809Sjmallett 521232809Sjmallett#if (__STD_C || defined(HAVE_MEMCPY)) 522232809Sjmallett 523232809Sjmallett#ifdef WIN32 524232809Sjmallett/* On Win32 memset and memcpy are already declared in windows.h */ 525232809Sjmallett#else 526232809Sjmallett#if __STD_C 527232809Sjmallettvoid* memset(void*, int, size_t); 528232809Sjmallettvoid* memcpy(void*, const void*, size_t); 529232809Sjmallett#else 530232809SjmallettVoid_t* memset(); 531232809SjmallettVoid_t* memcpy(); 532232809Sjmallett#endif 533232809Sjmallett#endif 534232809Sjmallett#endif 535232809Sjmallett 536232809Sjmallett/* 537232809Sjmallett MALLOC_FAILURE_ACTION is the action to take before "return 0" when 538232809Sjmallett malloc fails to be able to return memory, either because memory is 539232809Sjmallett exhausted or because of illegal arguments. 540232809Sjmallett 541232809Sjmallett By default, sets errno if running on STD_C platform, else does nothing. 542232809Sjmallett*/ 543232809Sjmallett 544232809Sjmallett#ifndef MALLOC_FAILURE_ACTION 545232809Sjmallett#if __STD_C 546232809Sjmallett#define MALLOC_FAILURE_ACTION \ 547232809Sjmallett errno = ENOMEM; 548232809Sjmallett 549232809Sjmallett#else 550232809Sjmallett#define MALLOC_FAILURE_ACTION 551232809Sjmallett#endif 552232809Sjmallett#endif 553232809Sjmallett 554232809Sjmallett/* 555232809Sjmallett MORECORE-related declarations. By default, rely on sbrk 556232809Sjmallett*/ 557232809Sjmallett 558232809Sjmallett 559232809Sjmallett#ifdef LACKS_UNISTD_H 560232809Sjmallett#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__) 561232809Sjmallett#if __STD_C 562232809Sjmallettextern Void_t* sbrk(ptrdiff_t); 563232809Sjmallett#else 564232809Sjmallettextern Void_t* sbrk(); 565232809Sjmallett#endif 566232809Sjmallett#endif 567232809Sjmallett#endif 568232809Sjmallett 569232809Sjmallett/* 570232809Sjmallett MORECORE is the name of the routine to call to obtain more memory 571232809Sjmallett from the system. See below for general guidance on writing 572232809Sjmallett alternative MORECORE functions, as well as a version for WIN32 and a 573232809Sjmallett sample version for pre-OSX macos. 574232809Sjmallett*/ 575232809Sjmallett#undef MORECORE // not supported 576232809Sjmallett#ifndef MORECORE 577232809Sjmallett#define MORECORE notsupported 578232809Sjmallett#endif 579232809Sjmallett 580232809Sjmallett/* 581232809Sjmallett MORECORE_FAILURE is the value returned upon failure of MORECORE 582232809Sjmallett as well as mmap. Since it cannot be an otherwise valid memory address, 583232809Sjmallett and must reflect values of standard sys calls, you probably ought not 584232809Sjmallett try to redefine it. 585232809Sjmallett*/ 586232809Sjmallett 587232809Sjmallett#ifndef MORECORE_FAILURE 588232809Sjmallett#define MORECORE_FAILURE (-1) 589232809Sjmallett#endif 590232809Sjmallett 591232809Sjmallett/* 592232809Sjmallett If MORECORE_CONTIGUOUS is true, take advantage of fact that 593232809Sjmallett consecutive calls to MORECORE with positive arguments always return 594232809Sjmallett contiguous increasing addresses. This is true of unix sbrk. Even 595232809Sjmallett if not defined, when regions happen to be contiguous, malloc will 596232809Sjmallett permit allocations spanning regions obtained from different 597232809Sjmallett calls. But defining this when applicable enables some stronger 598232809Sjmallett consistency checks and space efficiencies. 599232809Sjmallett*/ 600232809Sjmallett 601232809Sjmallett#ifndef MORECORE_CONTIGUOUS 602232809Sjmallett#define MORECORE_CONTIGUOUS 0 603232809Sjmallett#endif 604232809Sjmallett 605232809Sjmallett/* 606232809Sjmallett Define MORECORE_CANNOT_TRIM if your version of MORECORE 607232809Sjmallett cannot release space back to the system when given negative 608232809Sjmallett arguments. This is generally necessary only if you are using 609232809Sjmallett a hand-crafted MORECORE function that cannot handle negative arguments. 610232809Sjmallett*/ 611232809Sjmallett 612232809Sjmallett#define MORECORE_CANNOT_TRIM 1 613232809Sjmallett 614232809Sjmallett/* MORECORE_CLEARS (default 1) 615232809Sjmallett The degree to which the routine mapped to MORECORE zeroes out 616232809Sjmallett memory: never (0), only for newly allocated space (1) or always 617232809Sjmallett (2). The distinction between (1) and (2) is necessary because on 618232809Sjmallett some systems, if the application first decrements and then 619232809Sjmallett increments the break value, the contents of the reallocated space 620232809Sjmallett are unspecified. 621232809Sjmallett*/ 622232809Sjmallett 623232809Sjmallett#ifndef MORECORE_CLEARS 624232809Sjmallett#define MORECORE_CLEARS 0 625232809Sjmallett#endif 626232809Sjmallett 627232809Sjmallett 628232809Sjmallett/* 629232809Sjmallett Define HAVE_MMAP as true to optionally make malloc() use mmap() to 630232809Sjmallett allocate very large blocks. These will be returned to the 631232809Sjmallett operating system immediately after a free(). Also, if mmap 632232809Sjmallett is available, it is used as a backup strategy in cases where 633232809Sjmallett MORECORE fails to provide space from system. 634232809Sjmallett 635232809Sjmallett This malloc is best tuned to work with mmap for large requests. 636232809Sjmallett If you do not have mmap, operations involving very large chunks (1MB 637232809Sjmallett or so) may be slower than you'd like. 638232809Sjmallett*/ 639232809Sjmallett 640232809Sjmallett#undef HAVE_MMAP 641232809Sjmallett#ifndef HAVE_MMAP 642232809Sjmallett#define HAVE_MMAP 0 643232809Sjmallett 644232809Sjmallett/* 645232809Sjmallett Standard unix mmap using /dev/zero clears memory so calloc doesn't 646232809Sjmallett need to. 647232809Sjmallett*/ 648232809Sjmallett 649232809Sjmallett#ifndef MMAP_CLEARS 650232809Sjmallett#define MMAP_CLEARS 0 651232809Sjmallett#endif 652232809Sjmallett 653232809Sjmallett#else /* no mmap */ 654232809Sjmallett#ifndef MMAP_CLEARS 655232809Sjmallett#define MMAP_CLEARS 0 656232809Sjmallett#endif 657232809Sjmallett#endif 658232809Sjmallett 659232809Sjmallett 660232809Sjmallett/* 661232809Sjmallett MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if 662232809Sjmallett sbrk fails, and mmap is used as a backup (which is done only if 663232809Sjmallett HAVE_MMAP). The value must be a multiple of page size. This 664232809Sjmallett backup strategy generally applies only when systems have "holes" in 665232809Sjmallett address space, so sbrk cannot perform contiguous expansion, but 666232809Sjmallett there is still space available on system. On systems for which 667232809Sjmallett this is known to be useful (i.e. most linux kernels), this occurs 668232809Sjmallett only when programs allocate huge amounts of memory. Between this, 669232809Sjmallett and the fact that mmap regions tend to be limited, the size should 670232809Sjmallett be large, to avoid too many mmap calls and thus avoid running out 671232809Sjmallett of kernel resources. 672232809Sjmallett*/ 673232809Sjmallett 674232809Sjmallett#ifndef MMAP_AS_MORECORE_SIZE 675232809Sjmallett#define MMAP_AS_MORECORE_SIZE (1024 * 1024) 676232809Sjmallett#endif 677232809Sjmallett 678232809Sjmallett/* 679232809Sjmallett Define HAVE_MREMAP to make realloc() use mremap() to re-allocate 680232809Sjmallett large blocks. This is currently only possible on Linux with 681232809Sjmallett kernel versions newer than 1.3.77. 682232809Sjmallett*/ 683232809Sjmallett#undef linux 684232809Sjmallett#ifndef HAVE_MREMAP 685232809Sjmallett#ifdef linux 686232809Sjmallett#define HAVE_MREMAP 1 687232809Sjmallett#else 688232809Sjmallett#define HAVE_MREMAP 0 689232809Sjmallett#endif 690232809Sjmallett 691232809Sjmallett#endif /* HAVE_MMAP */ 692232809Sjmallett 693232809Sjmallett/* Define USE_ARENAS to enable support for multiple `arenas'. These 694232809Sjmallett are allocated using mmap(), are necessary for threads and 695232809Sjmallett occasionally useful to overcome address space limitations affecting 696232809Sjmallett sbrk(). */ 697232809Sjmallett 698232809Sjmallett#ifndef USE_ARENAS 699232809Sjmallett#define USE_ARENAS 1 // we 'manually' mmap the arenas..... 700232809Sjmallett#endif 701232809Sjmallett 702232809Sjmallett 703232809Sjmallett/* 704232809Sjmallett The system page size. To the extent possible, this malloc manages 705232809Sjmallett memory from the system in page-size units. Note that this value is 706232809Sjmallett cached during initialization into a field of malloc_state. So even 707232809Sjmallett if malloc_getpagesize is a function, it is only called once. 708232809Sjmallett 709232809Sjmallett The following mechanics for getpagesize were adapted from bsd/gnu 710232809Sjmallett getpagesize.h. If none of the system-probes here apply, a value of 711232809Sjmallett 4096 is used, which should be OK: If they don't apply, then using 712232809Sjmallett the actual value probably doesn't impact performance. 713232809Sjmallett*/ 714232809Sjmallett 715232809Sjmallett 716232809Sjmallett#define malloc_getpagesize (4096) 717232809Sjmallett#ifndef malloc_getpagesize 718232809Sjmallett 719232809Sjmallett#ifndef LACKS_UNISTD_H 720232809Sjmallett# include <unistd.h> 721232809Sjmallett#endif 722232809Sjmallett 723232809Sjmallett# ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */ 724232809Sjmallett# ifndef _SC_PAGE_SIZE 725232809Sjmallett# define _SC_PAGE_SIZE _SC_PAGESIZE 726232809Sjmallett# endif 727232809Sjmallett# endif 728232809Sjmallett 729232809Sjmallett# ifdef _SC_PAGE_SIZE 730232809Sjmallett# define malloc_getpagesize sysconf(_SC_PAGE_SIZE) 731232809Sjmallett# else 732232809Sjmallett# if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE) 733232809Sjmallett extern size_t getpagesize(); 734232809Sjmallett# define malloc_getpagesize getpagesize() 735232809Sjmallett# else 736232809Sjmallett# ifdef WIN32 /* use supplied emulation of getpagesize */ 737232809Sjmallett# define malloc_getpagesize getpagesize() 738232809Sjmallett# else 739232809Sjmallett# ifndef LACKS_SYS_PARAM_H 740232809Sjmallett# include <sys/param.h> 741232809Sjmallett# endif 742232809Sjmallett# ifdef EXEC_PAGESIZE 743232809Sjmallett# define malloc_getpagesize EXEC_PAGESIZE 744232809Sjmallett# else 745232809Sjmallett# ifdef NBPG 746232809Sjmallett# ifndef CLSIZE 747232809Sjmallett# define malloc_getpagesize NBPG 748232809Sjmallett# else 749232809Sjmallett# define malloc_getpagesize (NBPG * CLSIZE) 750232809Sjmallett# endif 751232809Sjmallett# else 752232809Sjmallett# ifdef NBPC 753232809Sjmallett# define malloc_getpagesize NBPC 754232809Sjmallett# else 755232809Sjmallett# ifdef PAGESIZE 756232809Sjmallett# define malloc_getpagesize PAGESIZE 757232809Sjmallett# else /* just guess */ 758232809Sjmallett# define malloc_getpagesize (4096) 759232809Sjmallett# endif 760232809Sjmallett# endif 761232809Sjmallett# endif 762232809Sjmallett# endif 763232809Sjmallett# endif 764232809Sjmallett# endif 765232809Sjmallett# endif 766232809Sjmallett#endif 767232809Sjmallett 768232809Sjmallett/* 769232809Sjmallett This version of malloc supports the standard SVID/XPG mallinfo 770232809Sjmallett routine that returns a struct containing usage properties and 771232809Sjmallett statistics. It should work on any SVID/XPG compliant system that has 772232809Sjmallett a /usr/include/malloc.h defining struct mallinfo. (If you'd like to 773232809Sjmallett install such a thing yourself, cut out the preliminary declarations 774232809Sjmallett as described above and below and save them in a malloc.h file. But 775232809Sjmallett there's no compelling reason to bother to do this.) 776232809Sjmallett 777232809Sjmallett The main declaration needed is the mallinfo struct that is returned 778232809Sjmallett (by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a 779232809Sjmallett bunch of fields that are not even meaningful in this version of 780232809Sjmallett malloc. These fields are are instead filled by mallinfo() with 781232809Sjmallett other numbers that might be of interest. 782232809Sjmallett 783232809Sjmallett HAVE_USR_INCLUDE_MALLOC_H should be set if you have a 784232809Sjmallett /usr/include/malloc.h file that includes a declaration of struct 785232809Sjmallett mallinfo. If so, it is included; else an SVID2/XPG2 compliant 786232809Sjmallett version is declared below. These must be precisely the same for 787232809Sjmallett mallinfo() to work. The original SVID version of this struct, 788232809Sjmallett defined on most systems with mallinfo, declares all fields as 789232809Sjmallett ints. But some others define as unsigned long. If your system 790232809Sjmallett defines the fields using a type of different width than listed here, 791232809Sjmallett you must #include your system version and #define 792232809Sjmallett HAVE_USR_INCLUDE_MALLOC_H. 793232809Sjmallett*/ 794232809Sjmallett 795232809Sjmallett/* #define HAVE_USR_INCLUDE_MALLOC_H */ 796232809Sjmallett 797232809Sjmallett#ifdef HAVE_USR_INCLUDE_MALLOC_H 798232809Sjmallett#include "/usr/include/malloc.h" 799232809Sjmallett#endif 800232809Sjmallett 801232809Sjmallett 802232809Sjmallett/* ---------- description of public routines ------------ */ 803232809Sjmallett 804232809Sjmallett/* 805232809Sjmallett malloc(size_t n) 806232809Sjmallett Returns a pointer to a newly allocated chunk of at least n bytes, or null 807232809Sjmallett if no space is available. Additionally, on failure, errno is 808232809Sjmallett set to ENOMEM on ANSI C systems. 809232809Sjmallett 810232809Sjmallett If n is zero, malloc returns a minumum-sized chunk. (The minimum 811232809Sjmallett size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit 812232809Sjmallett systems.) On most systems, size_t is an unsigned type, so calls 813232809Sjmallett with negative arguments are interpreted as requests for huge amounts 814232809Sjmallett of space, which will often fail. The maximum supported value of n 815232809Sjmallett differs across systems, but is in all cases less than the maximum 816232809Sjmallett representable value of a size_t. 817232809Sjmallett*/ 818232809Sjmallett#if __STD_C 819232809SjmallettVoid_t* public_mALLOc(cvmx_arena_list_t arena_list, size_t); 820232809Sjmallett#else 821232809SjmallettVoid_t* public_mALLOc(); 822232809Sjmallett#endif 823232809Sjmallett 824232809Sjmallett/* 825232809Sjmallett free(Void_t* p) 826232809Sjmallett Releases the chunk of memory pointed to by p, that had been previously 827232809Sjmallett allocated using malloc or a related routine such as realloc. 828232809Sjmallett It has no effect if p is null. It can have arbitrary (i.e., bad!) 829232809Sjmallett effects if p has already been freed. 830232809Sjmallett 831232809Sjmallett Unless disabled (using mallopt), freeing very large spaces will 832232809Sjmallett when possible, automatically trigger operations that give 833232809Sjmallett back unused memory to the system, thus reducing program footprint. 834232809Sjmallett*/ 835232809Sjmallett#if __STD_C 836232809Sjmallettvoid public_fREe(Void_t*); 837232809Sjmallett#else 838232809Sjmallettvoid public_fREe(); 839232809Sjmallett#endif 840232809Sjmallett 841232809Sjmallett/* 842232809Sjmallett calloc(size_t n_elements, size_t element_size); 843232809Sjmallett Returns a pointer to n_elements * element_size bytes, with all locations 844232809Sjmallett set to zero. 845232809Sjmallett*/ 846232809Sjmallett#if __STD_C 847232809SjmallettVoid_t* public_cALLOc(cvmx_arena_list_t arena_list, size_t, size_t); 848232809Sjmallett#else 849232809SjmallettVoid_t* public_cALLOc(); 850232809Sjmallett#endif 851232809Sjmallett 852232809Sjmallett/* 853232809Sjmallett realloc(Void_t* p, size_t n) 854232809Sjmallett Returns a pointer to a chunk of size n that contains the same data 855232809Sjmallett as does chunk p up to the minimum of (n, p's size) bytes, or null 856232809Sjmallett if no space is available. 857232809Sjmallett 858232809Sjmallett The returned pointer may or may not be the same as p. The algorithm 859232809Sjmallett prefers extending p when possible, otherwise it employs the 860232809Sjmallett equivalent of a malloc-copy-free sequence. 861232809Sjmallett 862232809Sjmallett If p is null, realloc is equivalent to malloc. 863232809Sjmallett 864232809Sjmallett If space is not available, realloc returns null, errno is set (if on 865232809Sjmallett ANSI) and p is NOT freed. 866232809Sjmallett 867232809Sjmallett if n is for fewer bytes than already held by p, the newly unused 868232809Sjmallett space is lopped off and freed if possible. Unless the #define 869232809Sjmallett REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of 870232809Sjmallett zero (re)allocates a minimum-sized chunk. 871232809Sjmallett 872232809Sjmallett Large chunks that were internally obtained via mmap will always 873232809Sjmallett be reallocated using malloc-copy-free sequences unless 874232809Sjmallett the system supports MREMAP (currently only linux). 875232809Sjmallett 876232809Sjmallett The old unix realloc convention of allowing the last-free'd chunk 877232809Sjmallett to be used as an argument to realloc is not supported. 878232809Sjmallett*/ 879232809Sjmallett#if __STD_C 880232809SjmallettVoid_t* public_rEALLOc(cvmx_arena_list_t arena_list, Void_t*, size_t); 881232809Sjmallett#else 882232809SjmallettVoid_t* public_rEALLOc(); 883232809Sjmallett#endif 884232809Sjmallett 885232809Sjmallett/* 886232809Sjmallett memalign(size_t alignment, size_t n); 887232809Sjmallett Returns a pointer to a newly allocated chunk of n bytes, aligned 888232809Sjmallett in accord with the alignment argument. 889232809Sjmallett 890232809Sjmallett The alignment argument should be a power of two. If the argument is 891232809Sjmallett not a power of two, the nearest greater power is used. 892232809Sjmallett 8-byte alignment is guaranteed by normal malloc calls, so don't 893232809Sjmallett bother calling memalign with an argument of 8 or less. 894232809Sjmallett 895232809Sjmallett Overreliance on memalign is a sure way to fragment space. 896232809Sjmallett*/ 897232809Sjmallett#if __STD_C 898232809SjmallettVoid_t* public_mEMALIGn(cvmx_arena_list_t arena_list, size_t, size_t); 899232809Sjmallett#else 900232809SjmallettVoid_t* public_mEMALIGn(); 901232809Sjmallett#endif 902232809Sjmallett 903232809Sjmallett/* 904232809Sjmallett valloc(size_t n); 905232809Sjmallett Equivalent to memalign(pagesize, n), where pagesize is the page 906232809Sjmallett size of the system. If the pagesize is unknown, 4096 is used. 907232809Sjmallett*/ 908232809Sjmallett#if __STD_C 909232809SjmallettVoid_t* public_vALLOc(size_t); 910232809Sjmallett#else 911232809SjmallettVoid_t* public_vALLOc(); 912232809Sjmallett#endif 913232809Sjmallett 914232809Sjmallett 915232809Sjmallett 916232809Sjmallett/* 917232809Sjmallett mallopt(int parameter_number, int parameter_value) 918232809Sjmallett Sets tunable parameters The format is to provide a 919232809Sjmallett (parameter-number, parameter-value) pair. mallopt then sets the 920232809Sjmallett corresponding parameter to the argument value if it can (i.e., so 921232809Sjmallett long as the value is meaningful), and returns 1 if successful else 922232809Sjmallett 0. SVID/XPG/ANSI defines four standard param numbers for mallopt, 923232809Sjmallett normally defined in malloc.h. Only one of these (M_MXFAST) is used 924232809Sjmallett in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply, 925232809Sjmallett so setting them has no effect. But this malloc also supports four 926232809Sjmallett other options in mallopt. See below for details. Briefly, supported 927232809Sjmallett parameters are as follows (listed defaults are for "typical" 928232809Sjmallett configurations). 929232809Sjmallett 930232809Sjmallett Symbol param # default allowed param values 931232809Sjmallett M_MXFAST 1 64 0-80 (0 disables fastbins) 932232809Sjmallett M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming) 933232809Sjmallett M_TOP_PAD -2 0 any 934232809Sjmallett M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support) 935232809Sjmallett M_MMAP_MAX -4 65536 any (0 disables use of mmap) 936232809Sjmallett*/ 937232809Sjmallett#if __STD_C 938232809Sjmallettint public_mALLOPt(int, int); 939232809Sjmallett#else 940232809Sjmallettint public_mALLOPt(); 941232809Sjmallett#endif 942232809Sjmallett 943232809Sjmallett 944232809Sjmallett/* 945232809Sjmallett mallinfo() 946232809Sjmallett Returns (by copy) a struct containing various summary statistics: 947232809Sjmallett 948232809Sjmallett arena: current total non-mmapped bytes allocated from system 949232809Sjmallett ordblks: the number of free chunks 950232809Sjmallett smblks: the number of fastbin blocks (i.e., small chunks that 951232809Sjmallett have been freed but not use resused or consolidated) 952232809Sjmallett hblks: current number of mmapped regions 953232809Sjmallett hblkhd: total bytes held in mmapped regions 954232809Sjmallett usmblks: the maximum total allocated space. This will be greater 955232809Sjmallett than current total if trimming has occurred. 956232809Sjmallett fsmblks: total bytes held in fastbin blocks 957232809Sjmallett uordblks: current total allocated space (normal or mmapped) 958232809Sjmallett fordblks: total free space 959232809Sjmallett keepcost: the maximum number of bytes that could ideally be released 960232809Sjmallett back to system via malloc_trim. ("ideally" means that 961232809Sjmallett it ignores page restrictions etc.) 962232809Sjmallett 963232809Sjmallett Because these fields are ints, but internal bookkeeping may 964232809Sjmallett be kept as longs, the reported values may wrap around zero and 965232809Sjmallett thus be inaccurate. 966232809Sjmallett*/ 967232809Sjmallett#if __STD_C 968232809Sjmallettstruct mallinfo public_mALLINFo(void); 969232809Sjmallett#else 970232809Sjmallettstruct mallinfo public_mALLINFo(); 971232809Sjmallett#endif 972232809Sjmallett 973232809Sjmallett/* 974232809Sjmallett independent_calloc(size_t n_elements, size_t element_size, Void_t* chunks[]); 975232809Sjmallett 976232809Sjmallett independent_calloc is similar to calloc, but instead of returning a 977232809Sjmallett single cleared space, it returns an array of pointers to n_elements 978232809Sjmallett independent elements that can hold contents of size elem_size, each 979232809Sjmallett of which starts out cleared, and can be independently freed, 980232809Sjmallett realloc'ed etc. The elements are guaranteed to be adjacently 981232809Sjmallett allocated (this is not guaranteed to occur with multiple callocs or 982232809Sjmallett mallocs), which may also improve cache locality in some 983232809Sjmallett applications. 984232809Sjmallett 985232809Sjmallett The "chunks" argument is optional (i.e., may be null, which is 986232809Sjmallett probably the most typical usage). If it is null, the returned array 987232809Sjmallett is itself dynamically allocated and should also be freed when it is 988232809Sjmallett no longer needed. Otherwise, the chunks array must be of at least 989232809Sjmallett n_elements in length. It is filled in with the pointers to the 990232809Sjmallett chunks. 991232809Sjmallett 992232809Sjmallett In either case, independent_calloc returns this pointer array, or 993232809Sjmallett null if the allocation failed. If n_elements is zero and "chunks" 994232809Sjmallett is null, it returns a chunk representing an array with zero elements 995232809Sjmallett (which should be freed if not wanted). 996232809Sjmallett 997232809Sjmallett Each element must be individually freed when it is no longer 998232809Sjmallett needed. If you'd like to instead be able to free all at once, you 999232809Sjmallett should instead use regular calloc and assign pointers into this 1000232809Sjmallett space to represent elements. (In this case though, you cannot 1001232809Sjmallett independently free elements.) 1002232809Sjmallett 1003232809Sjmallett independent_calloc simplifies and speeds up implementations of many 1004232809Sjmallett kinds of pools. It may also be useful when constructing large data 1005232809Sjmallett structures that initially have a fixed number of fixed-sized nodes, 1006232809Sjmallett but the number is not known at compile time, and some of the nodes 1007232809Sjmallett may later need to be freed. For example: 1008232809Sjmallett 1009232809Sjmallett struct Node { int item; struct Node* next; }; 1010232809Sjmallett 1011232809Sjmallett struct Node* build_list() { 1012232809Sjmallett struct Node** pool; 1013232809Sjmallett int n = read_number_of_nodes_needed(); 1014232809Sjmallett if (n <= 0) return 0; 1015232809Sjmallett pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0); 1016232809Sjmallett if (pool == 0) die(); 1017232809Sjmallett // organize into a linked list... 1018232809Sjmallett struct Node* first = pool[0]; 1019232809Sjmallett for (i = 0; i < n-1; ++i) 1020232809Sjmallett pool[i]->next = pool[i+1]; 1021232809Sjmallett free(pool); // Can now free the array (or not, if it is needed later) 1022232809Sjmallett return first; 1023232809Sjmallett } 1024232809Sjmallett*/ 1025232809Sjmallett#if __STD_C 1026232809SjmallettVoid_t** public_iCALLOc(size_t, size_t, Void_t**); 1027232809Sjmallett#else 1028232809SjmallettVoid_t** public_iCALLOc(); 1029232809Sjmallett#endif 1030232809Sjmallett 1031232809Sjmallett/* 1032232809Sjmallett independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]); 1033232809Sjmallett 1034232809Sjmallett independent_comalloc allocates, all at once, a set of n_elements 1035232809Sjmallett chunks with sizes indicated in the "sizes" array. It returns 1036232809Sjmallett an array of pointers to these elements, each of which can be 1037232809Sjmallett independently freed, realloc'ed etc. The elements are guaranteed to 1038232809Sjmallett be adjacently allocated (this is not guaranteed to occur with 1039232809Sjmallett multiple callocs or mallocs), which may also improve cache locality 1040232809Sjmallett in some applications. 1041232809Sjmallett 1042232809Sjmallett The "chunks" argument is optional (i.e., may be null). If it is null 1043232809Sjmallett the returned array is itself dynamically allocated and should also 1044232809Sjmallett be freed when it is no longer needed. Otherwise, the chunks array 1045232809Sjmallett must be of at least n_elements in length. It is filled in with the 1046232809Sjmallett pointers to the chunks. 1047232809Sjmallett 1048232809Sjmallett In either case, independent_comalloc returns this pointer array, or 1049232809Sjmallett null if the allocation failed. If n_elements is zero and chunks is 1050232809Sjmallett null, it returns a chunk representing an array with zero elements 1051232809Sjmallett (which should be freed if not wanted). 1052232809Sjmallett 1053232809Sjmallett Each element must be individually freed when it is no longer 1054232809Sjmallett needed. If you'd like to instead be able to free all at once, you 1055232809Sjmallett should instead use a single regular malloc, and assign pointers at 1056232809Sjmallett particular offsets in the aggregate space. (In this case though, you 1057232809Sjmallett cannot independently free elements.) 1058232809Sjmallett 1059232809Sjmallett independent_comallac differs from independent_calloc in that each 1060232809Sjmallett element may have a different size, and also that it does not 1061232809Sjmallett automatically clear elements. 1062232809Sjmallett 1063232809Sjmallett independent_comalloc can be used to speed up allocation in cases 1064232809Sjmallett where several structs or objects must always be allocated at the 1065232809Sjmallett same time. For example: 1066232809Sjmallett 1067232809Sjmallett struct Head { ... } 1068232809Sjmallett struct Foot { ... } 1069232809Sjmallett 1070232809Sjmallett void send_message(char* msg) { 1071232809Sjmallett int msglen = strlen(msg); 1072232809Sjmallett size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) }; 1073232809Sjmallett void* chunks[3]; 1074232809Sjmallett if (independent_comalloc(3, sizes, chunks) == 0) 1075232809Sjmallett die(); 1076232809Sjmallett struct Head* head = (struct Head*)(chunks[0]); 1077232809Sjmallett char* body = (char*)(chunks[1]); 1078232809Sjmallett struct Foot* foot = (struct Foot*)(chunks[2]); 1079232809Sjmallett // ... 1080232809Sjmallett } 1081232809Sjmallett 1082232809Sjmallett In general though, independent_comalloc is worth using only for 1083232809Sjmallett larger values of n_elements. For small values, you probably won't 1084232809Sjmallett detect enough difference from series of malloc calls to bother. 1085232809Sjmallett 1086232809Sjmallett Overuse of independent_comalloc can increase overall memory usage, 1087232809Sjmallett since it cannot reuse existing noncontiguous small chunks that 1088232809Sjmallett might be available for some of the elements. 1089232809Sjmallett*/ 1090232809Sjmallett#if __STD_C 1091232809SjmallettVoid_t** public_iCOMALLOc(size_t, size_t*, Void_t**); 1092232809Sjmallett#else 1093232809SjmallettVoid_t** public_iCOMALLOc(); 1094232809Sjmallett#endif 1095232809Sjmallett 1096232809Sjmallett 1097232809Sjmallett/* 1098232809Sjmallett pvalloc(size_t n); 1099232809Sjmallett Equivalent to valloc(minimum-page-that-holds(n)), that is, 1100232809Sjmallett round up n to nearest pagesize. 1101232809Sjmallett */ 1102232809Sjmallett#if __STD_C 1103232809SjmallettVoid_t* public_pVALLOc(size_t); 1104232809Sjmallett#else 1105232809SjmallettVoid_t* public_pVALLOc(); 1106232809Sjmallett#endif 1107232809Sjmallett 1108232809Sjmallett/* 1109232809Sjmallett cfree(Void_t* p); 1110232809Sjmallett Equivalent to free(p). 1111232809Sjmallett 1112232809Sjmallett cfree is needed/defined on some systems that pair it with calloc, 1113232809Sjmallett for odd historical reasons (such as: cfree is used in example 1114232809Sjmallett code in the first edition of K&R). 1115232809Sjmallett*/ 1116232809Sjmallett#if __STD_C 1117232809Sjmallettvoid public_cFREe(Void_t*); 1118232809Sjmallett#else 1119232809Sjmallettvoid public_cFREe(); 1120232809Sjmallett#endif 1121232809Sjmallett 1122232809Sjmallett/* 1123232809Sjmallett malloc_trim(size_t pad); 1124232809Sjmallett 1125232809Sjmallett If possible, gives memory back to the system (via negative 1126232809Sjmallett arguments to sbrk) if there is unused memory at the `high' end of 1127232809Sjmallett the malloc pool. You can call this after freeing large blocks of 1128232809Sjmallett memory to potentially reduce the system-level memory requirements 1129232809Sjmallett of a program. However, it cannot guarantee to reduce memory. Under 1130232809Sjmallett some allocation patterns, some large free blocks of memory will be 1131232809Sjmallett locked between two used chunks, so they cannot be given back to 1132232809Sjmallett the system. 1133232809Sjmallett 1134232809Sjmallett The `pad' argument to malloc_trim represents the amount of free 1135232809Sjmallett trailing space to leave untrimmed. If this argument is zero, 1136232809Sjmallett only the minimum amount of memory to maintain internal data 1137232809Sjmallett structures will be left (one page or less). Non-zero arguments 1138232809Sjmallett can be supplied to maintain enough trailing space to service 1139232809Sjmallett future expected allocations without having to re-obtain memory 1140232809Sjmallett from the system. 1141232809Sjmallett 1142232809Sjmallett Malloc_trim returns 1 if it actually released any memory, else 0. 1143232809Sjmallett On systems that do not support "negative sbrks", it will always 1144232809Sjmallett rreturn 0. 1145232809Sjmallett*/ 1146232809Sjmallett#if __STD_C 1147232809Sjmallettint public_mTRIm(size_t); 1148232809Sjmallett#else 1149232809Sjmallettint public_mTRIm(); 1150232809Sjmallett#endif 1151232809Sjmallett 1152232809Sjmallett/* 1153232809Sjmallett malloc_usable_size(Void_t* p); 1154232809Sjmallett 1155232809Sjmallett Returns the number of bytes you can actually use in 1156232809Sjmallett an allocated chunk, which may be more than you requested (although 1157232809Sjmallett often not) due to alignment and minimum size constraints. 1158232809Sjmallett You can use this many bytes without worrying about 1159232809Sjmallett overwriting other allocated objects. This is not a particularly great 1160232809Sjmallett programming practice. malloc_usable_size can be more useful in 1161232809Sjmallett debugging and assertions, for example: 1162232809Sjmallett 1163232809Sjmallett p = malloc(n); 1164232809Sjmallett assert(malloc_usable_size(p) >= 256); 1165232809Sjmallett 1166232809Sjmallett*/ 1167232809Sjmallett#if __STD_C 1168232809Sjmallettsize_t public_mUSABLe(Void_t*); 1169232809Sjmallett#else 1170232809Sjmallettsize_t public_mUSABLe(); 1171232809Sjmallett#endif 1172232809Sjmallett 1173232809Sjmallett/* 1174232809Sjmallett malloc_stats(); 1175232809Sjmallett Prints on stderr the amount of space obtained from the system (both 1176232809Sjmallett via sbrk and mmap), the maximum amount (which may be more than 1177232809Sjmallett current if malloc_trim and/or munmap got called), and the current 1178232809Sjmallett number of bytes allocated via malloc (or realloc, etc) but not yet 1179232809Sjmallett freed. Note that this is the number of bytes allocated, not the 1180232809Sjmallett number requested. It will be larger than the number requested 1181232809Sjmallett because of alignment and bookkeeping overhead. Because it includes 1182232809Sjmallett alignment wastage as being in use, this figure may be greater than 1183232809Sjmallett zero even when no user-level chunks are allocated. 1184232809Sjmallett 1185232809Sjmallett The reported current and maximum system memory can be inaccurate if 1186232809Sjmallett a program makes other calls to system memory allocation functions 1187232809Sjmallett (normally sbrk) outside of malloc. 1188232809Sjmallett 1189232809Sjmallett malloc_stats prints only the most commonly interesting statistics. 1190232809Sjmallett More information can be obtained by calling mallinfo. 1191232809Sjmallett 1192232809Sjmallett*/ 1193232809Sjmallett#if __STD_C 1194232809Sjmallettvoid public_mSTATs(void); 1195232809Sjmallett#else 1196232809Sjmallettvoid public_mSTATs(); 1197232809Sjmallett#endif 1198232809Sjmallett 1199232809Sjmallett/* 1200232809Sjmallett malloc_get_state(void); 1201232809Sjmallett 1202232809Sjmallett Returns the state of all malloc variables in an opaque data 1203232809Sjmallett structure. 1204232809Sjmallett*/ 1205232809Sjmallett#if __STD_C 1206232809SjmallettVoid_t* public_gET_STATe(void); 1207232809Sjmallett#else 1208232809SjmallettVoid_t* public_gET_STATe(); 1209232809Sjmallett#endif 1210232809Sjmallett 1211232809Sjmallett/* 1212232809Sjmallett malloc_set_state(Void_t* state); 1213232809Sjmallett 1214232809Sjmallett Restore the state of all malloc variables from data obtained with 1215232809Sjmallett malloc_get_state(). 1216232809Sjmallett*/ 1217232809Sjmallett#if __STD_C 1218232809Sjmallettint public_sET_STATe(Void_t*); 1219232809Sjmallett#else 1220232809Sjmallettint public_sET_STATe(); 1221232809Sjmallett#endif 1222232809Sjmallett 1223232809Sjmallett#ifdef _LIBC 1224232809Sjmallett/* 1225232809Sjmallett posix_memalign(void **memptr, size_t alignment, size_t size); 1226232809Sjmallett 1227232809Sjmallett POSIX wrapper like memalign(), checking for validity of size. 1228232809Sjmallett*/ 1229232809Sjmallettint __posix_memalign(void **, size_t, size_t); 1230232809Sjmallett#endif 1231232809Sjmallett 1232232809Sjmallett/* mallopt tuning options */ 1233232809Sjmallett 1234232809Sjmallett/* 1235232809Sjmallett M_MXFAST is the maximum request size used for "fastbins", special bins 1236232809Sjmallett that hold returned chunks without consolidating their spaces. This 1237232809Sjmallett enables future requests for chunks of the same size to be handled 1238232809Sjmallett very quickly, but can increase fragmentation, and thus increase the 1239232809Sjmallett overall memory footprint of a program. 1240232809Sjmallett 1241232809Sjmallett This malloc manages fastbins very conservatively yet still 1242232809Sjmallett efficiently, so fragmentation is rarely a problem for values less 1243232809Sjmallett than or equal to the default. The maximum supported value of MXFAST 1244232809Sjmallett is 80. You wouldn't want it any higher than this anyway. Fastbins 1245232809Sjmallett are designed especially for use with many small structs, objects or 1246232809Sjmallett strings -- the default handles structs/objects/arrays with sizes up 1247232809Sjmallett to 8 4byte fields, or small strings representing words, tokens, 1248232809Sjmallett etc. Using fastbins for larger objects normally worsens 1249232809Sjmallett fragmentation without improving speed. 1250232809Sjmallett 1251232809Sjmallett M_MXFAST is set in REQUEST size units. It is internally used in 1252232809Sjmallett chunksize units, which adds padding and alignment. You can reduce 1253232809Sjmallett M_MXFAST to 0 to disable all use of fastbins. This causes the malloc 1254232809Sjmallett algorithm to be a closer approximation of fifo-best-fit in all cases, 1255232809Sjmallett not just for larger requests, but will generally cause it to be 1256232809Sjmallett slower. 1257232809Sjmallett*/ 1258232809Sjmallett 1259232809Sjmallett 1260232809Sjmallett/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */ 1261232809Sjmallett#ifndef M_MXFAST 1262232809Sjmallett#define M_MXFAST 1 1263232809Sjmallett#endif 1264232809Sjmallett 1265232809Sjmallett#ifndef DEFAULT_MXFAST 1266232809Sjmallett#define DEFAULT_MXFAST 64 1267232809Sjmallett#endif 1268232809Sjmallett 1269232809Sjmallett 1270232809Sjmallett/* 1271232809Sjmallett M_TRIM_THRESHOLD is the maximum amount of unused top-most memory 1272232809Sjmallett to keep before releasing via malloc_trim in free(). 1273232809Sjmallett 1274232809Sjmallett Automatic trimming is mainly useful in long-lived programs. 1275232809Sjmallett Because trimming via sbrk can be slow on some systems, and can 1276232809Sjmallett sometimes be wasteful (in cases where programs immediately 1277232809Sjmallett afterward allocate more large chunks) the value should be high 1278232809Sjmallett enough so that your overall system performance would improve by 1279232809Sjmallett releasing this much memory. 1280232809Sjmallett 1281232809Sjmallett The trim threshold and the mmap control parameters (see below) 1282232809Sjmallett can be traded off with one another. Trimming and mmapping are 1283232809Sjmallett two different ways of releasing unused memory back to the 1284232809Sjmallett system. Between these two, it is often possible to keep 1285232809Sjmallett system-level demands of a long-lived program down to a bare 1286232809Sjmallett minimum. For example, in one test suite of sessions measuring 1287232809Sjmallett the XF86 X server on Linux, using a trim threshold of 128K and a 1288232809Sjmallett mmap threshold of 192K led to near-minimal long term resource 1289232809Sjmallett consumption. 1290232809Sjmallett 1291232809Sjmallett If you are using this malloc in a long-lived program, it should 1292232809Sjmallett pay to experiment with these values. As a rough guide, you 1293232809Sjmallett might set to a value close to the average size of a process 1294232809Sjmallett (program) running on your system. Releasing this much memory 1295232809Sjmallett would allow such a process to run in memory. Generally, it's 1296232809Sjmallett worth it to tune for trimming rather tham memory mapping when a 1297232809Sjmallett program undergoes phases where several large chunks are 1298232809Sjmallett allocated and released in ways that can reuse each other's 1299232809Sjmallett storage, perhaps mixed with phases where there are no such 1300232809Sjmallett chunks at all. And in well-behaved long-lived programs, 1301232809Sjmallett controlling release of large blocks via trimming versus mapping 1302232809Sjmallett is usually faster. 1303232809Sjmallett 1304232809Sjmallett However, in most programs, these parameters serve mainly as 1305232809Sjmallett protection against the system-level effects of carrying around 1306232809Sjmallett massive amounts of unneeded memory. Since frequent calls to 1307232809Sjmallett sbrk, mmap, and munmap otherwise degrade performance, the default 1308232809Sjmallett parameters are set to relatively high values that serve only as 1309232809Sjmallett safeguards. 1310232809Sjmallett 1311232809Sjmallett The trim value It must be greater than page size to have any useful 1312232809Sjmallett effect. To disable trimming completely, you can set to 1313232809Sjmallett (unsigned long)(-1) 1314232809Sjmallett 1315232809Sjmallett Trim settings interact with fastbin (MXFAST) settings: Unless 1316232809Sjmallett TRIM_FASTBINS is defined, automatic trimming never takes place upon 1317232809Sjmallett freeing a chunk with size less than or equal to MXFAST. Trimming is 1318232809Sjmallett instead delayed until subsequent freeing of larger chunks. However, 1319232809Sjmallett you can still force an attempted trim by calling malloc_trim. 1320232809Sjmallett 1321232809Sjmallett Also, trimming is not generally possible in cases where 1322232809Sjmallett the main arena is obtained via mmap. 1323232809Sjmallett 1324232809Sjmallett Note that the trick some people use of mallocing a huge space and 1325232809Sjmallett then freeing it at program startup, in an attempt to reserve system 1326232809Sjmallett memory, doesn't have the intended effect under automatic trimming, 1327232809Sjmallett since that memory will immediately be returned to the system. 1328232809Sjmallett*/ 1329232809Sjmallett 1330232809Sjmallett#define M_TRIM_THRESHOLD -1 1331232809Sjmallett 1332232809Sjmallett#ifndef DEFAULT_TRIM_THRESHOLD 1333232809Sjmallett#define DEFAULT_TRIM_THRESHOLD (128 * 1024) 1334232809Sjmallett#endif 1335232809Sjmallett 1336232809Sjmallett/* 1337232809Sjmallett M_TOP_PAD is the amount of extra `padding' space to allocate or 1338232809Sjmallett retain whenever sbrk is called. It is used in two ways internally: 1339232809Sjmallett 1340232809Sjmallett * When sbrk is called to extend the top of the arena to satisfy 1341232809Sjmallett a new malloc request, this much padding is added to the sbrk 1342232809Sjmallett request. 1343232809Sjmallett 1344232809Sjmallett * When malloc_trim is called automatically from free(), 1345232809Sjmallett it is used as the `pad' argument. 1346232809Sjmallett 1347232809Sjmallett In both cases, the actual amount of padding is rounded 1348232809Sjmallett so that the end of the arena is always a system page boundary. 1349232809Sjmallett 1350232809Sjmallett The main reason for using padding is to avoid calling sbrk so 1351232809Sjmallett often. Having even a small pad greatly reduces the likelihood 1352232809Sjmallett that nearly every malloc request during program start-up (or 1353232809Sjmallett after trimming) will invoke sbrk, which needlessly wastes 1354232809Sjmallett time. 1355232809Sjmallett 1356232809Sjmallett Automatic rounding-up to page-size units is normally sufficient 1357232809Sjmallett to avoid measurable overhead, so the default is 0. However, in 1358232809Sjmallett systems where sbrk is relatively slow, it can pay to increase 1359232809Sjmallett this value, at the expense of carrying around more memory than 1360232809Sjmallett the program needs. 1361232809Sjmallett*/ 1362232809Sjmallett 1363232809Sjmallett#define M_TOP_PAD -2 1364232809Sjmallett 1365232809Sjmallett#ifndef DEFAULT_TOP_PAD 1366232809Sjmallett#define DEFAULT_TOP_PAD (0) 1367232809Sjmallett#endif 1368232809Sjmallett 1369232809Sjmallett/* 1370232809Sjmallett M_MMAP_THRESHOLD is the request size threshold for using mmap() 1371232809Sjmallett to service a request. Requests of at least this size that cannot 1372232809Sjmallett be allocated using already-existing space will be serviced via mmap. 1373232809Sjmallett (If enough normal freed space already exists it is used instead.) 1374232809Sjmallett 1375232809Sjmallett Using mmap segregates relatively large chunks of memory so that 1376232809Sjmallett they can be individually obtained and released from the host 1377232809Sjmallett system. A request serviced through mmap is never reused by any 1378232809Sjmallett other request (at least not directly; the system may just so 1379232809Sjmallett happen to remap successive requests to the same locations). 1380232809Sjmallett 1381232809Sjmallett Segregating space in this way has the benefits that: 1382232809Sjmallett 1383232809Sjmallett 1. Mmapped space can ALWAYS be individually released back 1384232809Sjmallett to the system, which helps keep the system level memory 1385232809Sjmallett demands of a long-lived program low. 1386232809Sjmallett 2. Mapped memory can never become `locked' between 1387232809Sjmallett other chunks, as can happen with normally allocated chunks, which 1388232809Sjmallett means that even trimming via malloc_trim would not release them. 1389232809Sjmallett 3. On some systems with "holes" in address spaces, mmap can obtain 1390232809Sjmallett memory that sbrk cannot. 1391232809Sjmallett 1392232809Sjmallett However, it has the disadvantages that: 1393232809Sjmallett 1394232809Sjmallett 1. The space cannot be reclaimed, consolidated, and then 1395232809Sjmallett used to service later requests, as happens with normal chunks. 1396232809Sjmallett 2. It can lead to more wastage because of mmap page alignment 1397232809Sjmallett requirements 1398232809Sjmallett 3. It causes malloc performance to be more dependent on host 1399232809Sjmallett system memory management support routines which may vary in 1400232809Sjmallett implementation quality and may impose arbitrary 1401232809Sjmallett limitations. Generally, servicing a request via normal 1402232809Sjmallett malloc steps is faster than going through a system's mmap. 1403232809Sjmallett 1404232809Sjmallett The advantages of mmap nearly always outweigh disadvantages for 1405232809Sjmallett "large" chunks, but the value of "large" varies across systems. The 1406232809Sjmallett default is an empirically derived value that works well in most 1407232809Sjmallett systems. 1408232809Sjmallett*/ 1409232809Sjmallett 1410232809Sjmallett#define M_MMAP_THRESHOLD -3 1411232809Sjmallett 1412232809Sjmallett#ifndef DEFAULT_MMAP_THRESHOLD 1413232809Sjmallett#define DEFAULT_MMAP_THRESHOLD (128 * 1024) 1414232809Sjmallett#endif 1415232809Sjmallett 1416232809Sjmallett/* 1417232809Sjmallett M_MMAP_MAX is the maximum number of requests to simultaneously 1418232809Sjmallett service using mmap. This parameter exists because 1419232809Sjmallett some systems have a limited number of internal tables for 1420232809Sjmallett use by mmap, and using more than a few of them may degrade 1421232809Sjmallett performance. 1422232809Sjmallett 1423232809Sjmallett The default is set to a value that serves only as a safeguard. 1424232809Sjmallett Setting to 0 disables use of mmap for servicing large requests. If 1425232809Sjmallett HAVE_MMAP is not set, the default value is 0, and attempts to set it 1426232809Sjmallett to non-zero values in mallopt will fail. 1427232809Sjmallett*/ 1428232809Sjmallett 1429232809Sjmallett#define M_MMAP_MAX -4 1430232809Sjmallett 1431232809Sjmallett#ifndef DEFAULT_MMAP_MAX 1432232809Sjmallett#if HAVE_MMAP 1433232809Sjmallett#define DEFAULT_MMAP_MAX (65536) 1434232809Sjmallett#else 1435232809Sjmallett#define DEFAULT_MMAP_MAX (0) 1436232809Sjmallett#endif 1437232809Sjmallett#endif 1438232809Sjmallett 1439232809Sjmallett#ifdef __cplusplus 1440232809Sjmallett}; /* end of extern "C" */ 1441232809Sjmallett#endif 1442232809Sjmallett 1443232809Sjmallett#include <cvmx-spinlock.h> 1444232809Sjmallett#include "malloc.h" 1445232809Sjmallett#include "thread-m.h" 1446232809Sjmallett 1447232809Sjmallett#ifdef DEBUG_PRINTS 1448232809Sjmallett#define debug_printf printf 1449232809Sjmallett#else 1450232809Sjmallett#define debug_printf(format, args...) 1451232809Sjmallett#endif 1452232809Sjmallett 1453232809Sjmallett#ifndef BOUNDED_N 1454232809Sjmallett#define BOUNDED_N(ptr, sz) (ptr) 1455232809Sjmallett#endif 1456232809Sjmallett#ifndef RETURN_ADDRESS 1457232809Sjmallett#define RETURN_ADDRESS(X_) (NULL) 1458232809Sjmallett#endif 1459232809Sjmallett 1460232809Sjmallett/* On some platforms we can compile internal, not exported functions better. 1461232809Sjmallett Let the environment provide a macro and define it to be empty if it 1462232809Sjmallett is not available. */ 1463232809Sjmallett#ifndef internal_function 1464232809Sjmallett# define internal_function 1465232809Sjmallett#endif 1466232809Sjmallett 1467232809Sjmallett/* Forward declarations. */ 1468232809Sjmallettstruct malloc_chunk; 1469232809Sjmalletttypedef struct malloc_chunk* mchunkptr; 1470232809Sjmallett 1471232809Sjmallett/* Internal routines. */ 1472232809Sjmallett 1473232809Sjmallett#if __STD_C 1474232809Sjmallett 1475232809Sjmallettstatic Void_t* _int_malloc(mstate, size_t); 1476232809Sjmallettstatic void _int_free(mstate, Void_t*); 1477232809Sjmallettstatic Void_t* _int_realloc(mstate, Void_t*, size_t); 1478232809Sjmallettstatic Void_t* _int_memalign(mstate, size_t, size_t); 1479232809Sjmallettstatic Void_t* _int_valloc(mstate, size_t); 1480232809Sjmallettstatic Void_t* _int_pvalloc(mstate, size_t); 1481232809Sjmallettstatic Void_t* cALLOc(cvmx_arena_list_t arena_list, size_t, size_t); 1482232809Sjmallettstatic Void_t** _int_icalloc(mstate, size_t, size_t, Void_t**); 1483232809Sjmallettstatic Void_t** _int_icomalloc(mstate, size_t, size_t*, Void_t**); 1484232809Sjmallettstatic int mTRIm(size_t); 1485232809Sjmallettstatic size_t mUSABLe(Void_t*); 1486232809Sjmallettstatic void mSTATs(void); 1487232809Sjmallettstatic int mALLOPt(int, int); 1488232809Sjmallettstatic struct mallinfo mALLINFo(mstate); 1489232809Sjmallett 1490232809Sjmallettstatic Void_t* internal_function mem2mem_check(Void_t *p, size_t sz); 1491232809Sjmallettstatic int internal_function top_check(void); 1492232809Sjmallettstatic void internal_function munmap_chunk(mchunkptr p); 1493232809Sjmallett#if HAVE_MREMAP 1494232809Sjmallettstatic mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size); 1495232809Sjmallett#endif 1496232809Sjmallett 1497232809Sjmallettstatic Void_t* malloc_check(size_t sz, const Void_t *caller); 1498232809Sjmallettstatic void free_check(Void_t* mem, const Void_t *caller); 1499232809Sjmallettstatic Void_t* realloc_check(Void_t* oldmem, size_t bytes, 1500232809Sjmallett const Void_t *caller); 1501232809Sjmallettstatic Void_t* memalign_check(size_t alignment, size_t bytes, 1502232809Sjmallett const Void_t *caller); 1503232809Sjmallett#ifndef NO_THREADS 1504232809Sjmallettstatic Void_t* malloc_starter(size_t sz, const Void_t *caller); 1505232809Sjmallettstatic void free_starter(Void_t* mem, const Void_t *caller); 1506232809Sjmallettstatic Void_t* malloc_atfork(size_t sz, const Void_t *caller); 1507232809Sjmallettstatic void free_atfork(Void_t* mem, const Void_t *caller); 1508232809Sjmallett#endif 1509232809Sjmallett 1510232809Sjmallett#else 1511232809Sjmallett 1512232809SjmallettVoid_t* _int_malloc(); 1513232809Sjmallettvoid _int_free(); 1514232809SjmallettVoid_t* _int_realloc(); 1515232809SjmallettVoid_t* _int_memalign(); 1516232809SjmallettVoid_t* _int_valloc(); 1517232809SjmallettVoid_t* _int_pvalloc(); 1518232809Sjmallett/*static Void_t* cALLOc();*/ 1519232809Sjmallettstatic Void_t** _int_icalloc(); 1520232809Sjmallettstatic Void_t** _int_icomalloc(); 1521232809Sjmallettstatic int mTRIm(); 1522232809Sjmallettstatic size_t mUSABLe(); 1523232809Sjmallettstatic void mSTATs(); 1524232809Sjmallettstatic int mALLOPt(); 1525232809Sjmallettstatic struct mallinfo mALLINFo(); 1526232809Sjmallett 1527232809Sjmallett#endif 1528232809Sjmallett 1529232809Sjmallett 1530232809Sjmallett 1531232809Sjmallett 1532232809Sjmallett/* ------------- Optional versions of memcopy ---------------- */ 1533232809Sjmallett 1534232809Sjmallett 1535232809Sjmallett#if USE_MEMCPY 1536232809Sjmallett 1537232809Sjmallett/* 1538232809Sjmallett Note: memcpy is ONLY invoked with non-overlapping regions, 1539232809Sjmallett so the (usually slower) memmove is not needed. 1540232809Sjmallett*/ 1541232809Sjmallett 1542232809Sjmallett#define MALLOC_COPY(dest, src, nbytes) memcpy(dest, src, nbytes) 1543232809Sjmallett#define MALLOC_ZERO(dest, nbytes) memset(dest, 0, nbytes) 1544232809Sjmallett 1545232809Sjmallett#else /* !USE_MEMCPY */ 1546232809Sjmallett 1547232809Sjmallett/* Use Duff's device for good zeroing/copying performance. */ 1548232809Sjmallett 1549232809Sjmallett#define MALLOC_ZERO(charp, nbytes) \ 1550232809Sjmallettdo { \ 1551232809Sjmallett INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \ 1552232809Sjmallett unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \ 1553232809Sjmallett long mcn; \ 1554232809Sjmallett if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \ 1555232809Sjmallett switch (mctmp) { \ 1556232809Sjmallett case 0: for(;;) { *mzp++ = 0; \ 1557232809Sjmallett case 7: *mzp++ = 0; \ 1558232809Sjmallett case 6: *mzp++ = 0; \ 1559232809Sjmallett case 5: *mzp++ = 0; \ 1560232809Sjmallett case 4: *mzp++ = 0; \ 1561232809Sjmallett case 3: *mzp++ = 0; \ 1562232809Sjmallett case 2: *mzp++ = 0; \ 1563232809Sjmallett case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \ 1564232809Sjmallett } \ 1565232809Sjmallett} while(0) 1566232809Sjmallett 1567232809Sjmallett#define MALLOC_COPY(dest,src,nbytes) \ 1568232809Sjmallettdo { \ 1569232809Sjmallett INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \ 1570232809Sjmallett INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \ 1571232809Sjmallett unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \ 1572232809Sjmallett long mcn; \ 1573232809Sjmallett if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \ 1574232809Sjmallett switch (mctmp) { \ 1575232809Sjmallett case 0: for(;;) { *mcdst++ = *mcsrc++; \ 1576232809Sjmallett case 7: *mcdst++ = *mcsrc++; \ 1577232809Sjmallett case 6: *mcdst++ = *mcsrc++; \ 1578232809Sjmallett case 5: *mcdst++ = *mcsrc++; \ 1579232809Sjmallett case 4: *mcdst++ = *mcsrc++; \ 1580232809Sjmallett case 3: *mcdst++ = *mcsrc++; \ 1581232809Sjmallett case 2: *mcdst++ = *mcsrc++; \ 1582232809Sjmallett case 1: *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; } \ 1583232809Sjmallett } \ 1584232809Sjmallett} while(0) 1585232809Sjmallett 1586232809Sjmallett#endif 1587232809Sjmallett 1588232809Sjmallett/* ------------------ MMAP support ------------------ */ 1589232809Sjmallett 1590232809Sjmallett 1591232809Sjmallett#if HAVE_MMAP 1592232809Sjmallett 1593232809Sjmallett#include <fcntl.h> 1594232809Sjmallett#ifndef LACKS_SYS_MMAN_H 1595232809Sjmallett#include <sys/mman.h> 1596232809Sjmallett#endif 1597232809Sjmallett 1598232809Sjmallett#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON) 1599232809Sjmallett# define MAP_ANONYMOUS MAP_ANON 1600232809Sjmallett#endif 1601232809Sjmallett#if !defined(MAP_FAILED) 1602232809Sjmallett# define MAP_FAILED ((char*)-1) 1603232809Sjmallett#endif 1604232809Sjmallett 1605232809Sjmallett#ifndef MAP_NORESERVE 1606232809Sjmallett# ifdef MAP_AUTORESRV 1607232809Sjmallett# define MAP_NORESERVE MAP_AUTORESRV 1608232809Sjmallett# else 1609232809Sjmallett# define MAP_NORESERVE 0 1610232809Sjmallett# endif 1611232809Sjmallett#endif 1612232809Sjmallett 1613232809Sjmallett/* 1614232809Sjmallett Nearly all versions of mmap support MAP_ANONYMOUS, 1615232809Sjmallett so the following is unlikely to be needed, but is 1616232809Sjmallett supplied just in case. 1617232809Sjmallett*/ 1618232809Sjmallett 1619232809Sjmallett#ifndef MAP_ANONYMOUS 1620232809Sjmallett 1621232809Sjmallettstatic int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */ 1622232809Sjmallett 1623232809Sjmallett#define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \ 1624232809Sjmallett (dev_zero_fd = open("/dev/zero", O_RDWR), \ 1625232809Sjmallett mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \ 1626232809Sjmallett mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) 1627232809Sjmallett 1628232809Sjmallett#else 1629232809Sjmallett 1630232809Sjmallett#define MMAP(addr, size, prot, flags) \ 1631232809Sjmallett (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0)) 1632232809Sjmallett 1633232809Sjmallett#endif 1634232809Sjmallett 1635232809Sjmallett 1636232809Sjmallett#endif /* HAVE_MMAP */ 1637232809Sjmallett 1638232809Sjmallett 1639232809Sjmallett/* 1640232809Sjmallett ----------------------- Chunk representations ----------------------- 1641232809Sjmallett*/ 1642232809Sjmallett 1643232809Sjmallett 1644232809Sjmallett/* 1645232809Sjmallett This struct declaration is misleading (but accurate and necessary). 1646232809Sjmallett It declares a "view" into memory allowing access to necessary 1647232809Sjmallett fields at known offsets from a given base. See explanation below. 1648232809Sjmallett*/ 1649232809Sjmallettstruct malloc_chunk { 1650232809Sjmallett 1651232809Sjmallett INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */ 1652232809Sjmallett INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */ 1653232809Sjmallett mstate arena_ptr; /* ptr to arena chunk belongs to */ 1654232809Sjmallett 1655232809Sjmallett struct malloc_chunk* fd; /* double links -- used only if free. */ 1656232809Sjmallett struct malloc_chunk* bk; 1657232809Sjmallett}; 1658232809Sjmallett 1659232809Sjmallett 1660232809Sjmallett/* 1661232809Sjmallett malloc_chunk details: 1662232809Sjmallett 1663232809Sjmallett (The following includes lightly edited explanations by Colin Plumb.) 1664232809Sjmallett 1665232809Sjmallett Chunks of memory are maintained using a `boundary tag' method as 1666232809Sjmallett described in e.g., Knuth or Standish. (See the paper by Paul 1667232809Sjmallett Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a 1668232809Sjmallett survey of such techniques.) Sizes of free chunks are stored both 1669232809Sjmallett in the front of each chunk and at the end. This makes 1670232809Sjmallett consolidating fragmented chunks into bigger chunks very fast. The 1671232809Sjmallett size fields also hold bits representing whether chunks are free or 1672232809Sjmallett in use. 1673232809Sjmallett 1674232809Sjmallett An allocated chunk looks like this: 1675232809Sjmallett 1676232809Sjmallett 1677232809Sjmallett chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1678232809Sjmallett | Size of previous chunk, if allocated | | 1679232809Sjmallett +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1680232809Sjmallett | Size of chunk, in bytes |P| 1681232809Sjmallett mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1682232809Sjmallett | User data starts here... . 1683232809Sjmallett . . 1684232809Sjmallett . (malloc_usable_space() bytes) . 1685232809Sjmallett . | 1686232809Sjmallettnextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1687232809Sjmallett | Size of chunk | 1688232809Sjmallett +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1689232809Sjmallett 1690232809Sjmallett 1691232809Sjmallett Where "chunk" is the front of the chunk for the purpose of most of 1692232809Sjmallett the malloc code, but "mem" is the pointer that is returned to the 1693232809Sjmallett user. "Nextchunk" is the beginning of the next contiguous chunk. 1694232809Sjmallett 1695232809Sjmallett Chunks always begin on even word boundries, so the mem portion 1696232809Sjmallett (which is returned to the user) is also on an even word boundary, and 1697232809Sjmallett thus at least double-word aligned. 1698232809Sjmallett 1699232809Sjmallett Free chunks are stored in circular doubly-linked lists, and look like this: 1700232809Sjmallett 1701232809Sjmallett chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1702232809Sjmallett | Size of previous chunk | 1703232809Sjmallett +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1704232809Sjmallett `head:' | Size of chunk, in bytes |P| 1705232809Sjmallett mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1706232809Sjmallett | Forward pointer to next chunk in list | 1707232809Sjmallett +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1708232809Sjmallett | Back pointer to previous chunk in list | 1709232809Sjmallett +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1710232809Sjmallett | Unused space (may be 0 bytes long) . 1711232809Sjmallett . . 1712232809Sjmallett . | 1713232809Sjmallettnextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1714232809Sjmallett `foot:' | Size of chunk, in bytes | 1715232809Sjmallett +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1716232809Sjmallett 1717232809Sjmallett The P (PREV_INUSE) bit, stored in the unused low-order bit of the 1718232809Sjmallett chunk size (which is always a multiple of two words), is an in-use 1719232809Sjmallett bit for the *previous* chunk. If that bit is *clear*, then the 1720232809Sjmallett word before the current chunk size contains the previous chunk 1721232809Sjmallett size, and can be used to find the front of the previous chunk. 1722232809Sjmallett The very first chunk allocated always has this bit set, 1723232809Sjmallett preventing access to non-existent (or non-owned) memory. If 1724232809Sjmallett prev_inuse is set for any given chunk, then you CANNOT determine 1725232809Sjmallett the size of the previous chunk, and might even get a memory 1726232809Sjmallett addressing fault when trying to do so. 1727232809Sjmallett 1728232809Sjmallett Note that the `foot' of the current chunk is actually represented 1729232809Sjmallett as the prev_size of the NEXT chunk. This makes it easier to 1730232809Sjmallett deal with alignments etc but can be very confusing when trying 1731232809Sjmallett to extend or adapt this code. 1732232809Sjmallett 1733232809Sjmallett The two exceptions to all this are 1734232809Sjmallett 1735232809Sjmallett 1. The special chunk `top' doesn't bother using the 1736232809Sjmallett trailing size field since there is no next contiguous chunk 1737232809Sjmallett that would have to index off it. After initialization, `top' 1738232809Sjmallett is forced to always exist. If it would become less than 1739232809Sjmallett MINSIZE bytes long, it is replenished. 1740232809Sjmallett 1741232809Sjmallett 2. Chunks allocated via mmap, which have the second-lowest-order 1742232809Sjmallett bit (IS_MMAPPED) set in their size fields. Because they are 1743232809Sjmallett allocated one-by-one, each must contain its own trailing size field. 1744232809Sjmallett 1745232809Sjmallett*/ 1746232809Sjmallett 1747232809Sjmallett/* 1748232809Sjmallett ---------- Size and alignment checks and conversions ---------- 1749232809Sjmallett*/ 1750232809Sjmallett 1751232809Sjmallett/* conversion from malloc headers to user pointers, and back */ 1752232809Sjmallett/* Added size for pointer to make room for arena_ptr */ 1753232809Sjmallett#define chunk2mem(p) ((Void_t*)((char*)(p) + 2*SIZE_SZ + sizeof(void *))) 1754232809Sjmallett#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ - sizeof(void *))) 1755232809Sjmallett 1756232809Sjmallett/* The smallest possible chunk */ 1757232809Sjmallett#define MIN_CHUNK_SIZE (sizeof(struct malloc_chunk)) 1758232809Sjmallett 1759232809Sjmallett/* The smallest size we can malloc is an aligned minimal chunk */ 1760232809Sjmallett 1761232809Sjmallett#define MINSIZE \ 1762232809Sjmallett (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)) 1763232809Sjmallett 1764232809Sjmallett/* Check if m has acceptable alignment */ 1765232809Sjmallett 1766232809Sjmallett#define aligned_OK(m) (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0) 1767232809Sjmallett 1768232809Sjmallett 1769232809Sjmallett/* 1770232809Sjmallett Check if a request is so large that it would wrap around zero when 1771232809Sjmallett padded and aligned. To simplify some other code, the bound is made 1772232809Sjmallett low enough so that adding MINSIZE will also not wrap around zero. 1773232809Sjmallett*/ 1774232809Sjmallett 1775232809Sjmallett#define REQUEST_OUT_OF_RANGE(req) \ 1776232809Sjmallett ((unsigned long)(req) >= \ 1777232809Sjmallett (unsigned long)(INTERNAL_SIZE_T)(-2 * MINSIZE)) 1778232809Sjmallett 1779232809Sjmallett/* pad request bytes into a usable size -- internal version */ 1780232809Sjmallett 1781232809Sjmallett 1782232809Sjmallett/* prev_size field of next chunk is overwritten with data 1783232809Sjmallett** when in use. NOTE - last SIZE_SZ of arena must be left 1784232809Sjmallett** unused for last chunk to use 1785232809Sjmallett*/ 1786232809Sjmallett/* Added sizeof(void *) to make room for arena_ptr */ 1787232809Sjmallett#define request2size(req) \ 1788232809Sjmallett (((req) + sizeof(void *) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \ 1789232809Sjmallett MINSIZE : \ 1790232809Sjmallett ((req) + sizeof(void *) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK) 1791232809Sjmallett 1792232809Sjmallett/* Same, except also perform argument check */ 1793232809Sjmallett 1794232809Sjmallett#define checked_request2size(req, sz) \ 1795232809Sjmallett if (REQUEST_OUT_OF_RANGE(req)) { \ 1796232809Sjmallett MALLOC_FAILURE_ACTION; \ 1797232809Sjmallett return 0; \ 1798232809Sjmallett } \ 1799232809Sjmallett (sz) = request2size(req); 1800232809Sjmallett 1801232809Sjmallett/* 1802232809Sjmallett --------------- Physical chunk operations --------------- 1803232809Sjmallett*/ 1804232809Sjmallett 1805232809Sjmallett 1806232809Sjmallett/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */ 1807232809Sjmallett#define PREV_INUSE 0x1 1808232809Sjmallett 1809232809Sjmallett/* extract inuse bit of previous chunk */ 1810232809Sjmallett#define prev_inuse(p) ((p)->size & PREV_INUSE) 1811232809Sjmallett 1812232809Sjmallett 1813232809Sjmallett/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */ 1814232809Sjmallett#define IS_MMAPPED 0x2 1815232809Sjmallett 1816232809Sjmallett/* check for mmap()'ed chunk */ 1817232809Sjmallett#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED) 1818232809Sjmallett 1819232809Sjmallett 1820232809Sjmallett 1821232809Sjmallett/* 1822232809Sjmallett Bits to mask off when extracting size 1823232809Sjmallett 1824232809Sjmallett Note: IS_MMAPPED is intentionally not masked off from size field in 1825232809Sjmallett macros for which mmapped chunks should never be seen. This should 1826232809Sjmallett cause helpful core dumps to occur if it is tried by accident by 1827232809Sjmallett people extending or adapting this malloc. 1828232809Sjmallett*/ 1829232809Sjmallett#define SIZE_BITS (PREV_INUSE|IS_MMAPPED) 1830232809Sjmallett 1831232809Sjmallett/* Get size, ignoring use bits */ 1832232809Sjmallett#define chunksize(p) ((p)->size & ~(SIZE_BITS)) 1833232809Sjmallett 1834232809Sjmallett 1835232809Sjmallett/* Ptr to next physical malloc_chunk. */ 1836232809Sjmallett#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~SIZE_BITS) )) 1837232809Sjmallett 1838232809Sjmallett/* Ptr to previous physical malloc_chunk */ 1839232809Sjmallett#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) )) 1840232809Sjmallett 1841232809Sjmallett/* Treat space at ptr + offset as a chunk */ 1842232809Sjmallett#define chunk_at_offset(p, s) ((mchunkptr)(((char*)(p)) + (s))) 1843232809Sjmallett 1844232809Sjmallett/* extract p's inuse bit */ 1845232809Sjmallett#define inuse(p)\ 1846232809Sjmallett((((mchunkptr)(((char*)(p))+((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE) 1847232809Sjmallett 1848232809Sjmallett/* set/clear chunk as being inuse without otherwise disturbing */ 1849232809Sjmallett#define set_inuse(p)\ 1850232809Sjmallett((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE 1851232809Sjmallett 1852232809Sjmallett#define clear_inuse(p)\ 1853232809Sjmallett((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE) 1854232809Sjmallett 1855232809Sjmallett 1856232809Sjmallett/* check/set/clear inuse bits in known places */ 1857232809Sjmallett#define inuse_bit_at_offset(p, s)\ 1858232809Sjmallett (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE) 1859232809Sjmallett 1860232809Sjmallett#define set_inuse_bit_at_offset(p, s)\ 1861232809Sjmallett (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE) 1862232809Sjmallett 1863232809Sjmallett#define clear_inuse_bit_at_offset(p, s)\ 1864232809Sjmallett (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE)) 1865232809Sjmallett 1866232809Sjmallett 1867232809Sjmallett/* Set size at head, without disturbing its use bit */ 1868232809Sjmallett#define set_head_size(p, s) ((p)->size = (((p)->size & SIZE_BITS) | (s))) 1869232809Sjmallett 1870232809Sjmallett/* Set size/use field */ 1871232809Sjmallett#define set_head(p, s) ((p)->size = (s)) 1872232809Sjmallett 1873232809Sjmallett/* Set size at footer (only when chunk is not in use) */ 1874232809Sjmallett#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_size = (s)) 1875232809Sjmallett 1876232809Sjmallett 1877232809Sjmallett/* 1878232809Sjmallett -------------------- Internal data structures -------------------- 1879232809Sjmallett 1880232809Sjmallett All internal state is held in an instance of malloc_state defined 1881232809Sjmallett below. There are no other static variables, except in two optional 1882232809Sjmallett cases: 1883232809Sjmallett * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above. 1884232809Sjmallett * If HAVE_MMAP is true, but mmap doesn't support 1885232809Sjmallett MAP_ANONYMOUS, a dummy file descriptor for mmap. 1886232809Sjmallett 1887232809Sjmallett Beware of lots of tricks that minimize the total bookkeeping space 1888232809Sjmallett requirements. The result is a little over 1K bytes (for 4byte 1889232809Sjmallett pointers and size_t.) 1890232809Sjmallett*/ 1891232809Sjmallett 1892232809Sjmallett/* 1893232809Sjmallett Bins 1894232809Sjmallett 1895232809Sjmallett An array of bin headers for free chunks. Each bin is doubly 1896232809Sjmallett linked. The bins are approximately proportionally (log) spaced. 1897232809Sjmallett There are a lot of these bins (128). This may look excessive, but 1898232809Sjmallett works very well in practice. Most bins hold sizes that are 1899232809Sjmallett unusual as malloc request sizes, but are more usual for fragments 1900232809Sjmallett and consolidated sets of chunks, which is what these bins hold, so 1901232809Sjmallett they can be found quickly. All procedures maintain the invariant 1902232809Sjmallett that no consolidated chunk physically borders another one, so each 1903232809Sjmallett chunk in a list is known to be preceeded and followed by either 1904232809Sjmallett inuse chunks or the ends of memory. 1905232809Sjmallett 1906232809Sjmallett Chunks in bins are kept in size order, with ties going to the 1907232809Sjmallett approximately least recently used chunk. Ordering isn't needed 1908232809Sjmallett for the small bins, which all contain the same-sized chunks, but 1909232809Sjmallett facilitates best-fit allocation for larger chunks. These lists 1910232809Sjmallett are just sequential. Keeping them in order almost never requires 1911232809Sjmallett enough traversal to warrant using fancier ordered data 1912232809Sjmallett structures. 1913232809Sjmallett 1914232809Sjmallett Chunks of the same size are linked with the most 1915232809Sjmallett recently freed at the front, and allocations are taken from the 1916232809Sjmallett back. This results in LRU (FIFO) allocation order, which tends 1917232809Sjmallett to give each chunk an equal opportunity to be consolidated with 1918232809Sjmallett adjacent freed chunks, resulting in larger free chunks and less 1919232809Sjmallett fragmentation. 1920232809Sjmallett 1921232809Sjmallett To simplify use in double-linked lists, each bin header acts 1922232809Sjmallett as a malloc_chunk. This avoids special-casing for headers. 1923232809Sjmallett But to conserve space and improve locality, we allocate 1924232809Sjmallett only the fd/bk pointers of bins, and then use repositioning tricks 1925232809Sjmallett to treat these as the fields of a malloc_chunk*. 1926232809Sjmallett*/ 1927232809Sjmallett 1928232809Sjmalletttypedef struct malloc_chunk* mbinptr; 1929232809Sjmallett 1930232809Sjmallett/* addressing -- note that bin_at(0) does not exist */ 1931232809Sjmallett#define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - (SIZE_SZ<<1))) 1932232809Sjmallett 1933232809Sjmallett/* analog of ++bin */ 1934232809Sjmallett#define next_bin(b) ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1))) 1935232809Sjmallett 1936232809Sjmallett/* Reminders about list directionality within bins */ 1937232809Sjmallett#define first(b) ((b)->fd) 1938232809Sjmallett#define last(b) ((b)->bk) 1939232809Sjmallett 1940232809Sjmallett/* Take a chunk off a bin list */ 1941232809Sjmallett#define unlink(P, BK, FD) { \ 1942232809Sjmallett FD = P->fd; \ 1943232809Sjmallett BK = P->bk; \ 1944232809Sjmallett FD->bk = BK; \ 1945232809Sjmallett BK->fd = FD; \ 1946232809Sjmallett} 1947232809Sjmallett 1948232809Sjmallett/* 1949232809Sjmallett Indexing 1950232809Sjmallett 1951232809Sjmallett Bins for sizes < 512 bytes contain chunks of all the same size, spaced 1952232809Sjmallett 8 bytes apart. Larger bins are approximately logarithmically spaced: 1953232809Sjmallett 1954232809Sjmallett 64 bins of size 8 1955232809Sjmallett 32 bins of size 64 1956232809Sjmallett 16 bins of size 512 1957232809Sjmallett 8 bins of size 4096 1958232809Sjmallett 4 bins of size 32768 1959232809Sjmallett 2 bins of size 262144 1960232809Sjmallett 1 bin of size what's left 1961232809Sjmallett 1962232809Sjmallett There is actually a little bit of slop in the numbers in bin_index 1963232809Sjmallett for the sake of speed. This makes no difference elsewhere. 1964232809Sjmallett 1965232809Sjmallett The bins top out around 1MB because we expect to service large 1966232809Sjmallett requests via mmap. 1967232809Sjmallett*/ 1968232809Sjmallett 1969232809Sjmallett#define NBINS 128 1970232809Sjmallett#define NSMALLBINS 64 1971232809Sjmallett#define SMALLBIN_WIDTH 8 1972232809Sjmallett#define MIN_LARGE_SIZE 512 1973232809Sjmallett 1974232809Sjmallett#define in_smallbin_range(sz) \ 1975232809Sjmallett ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE) 1976232809Sjmallett 1977232809Sjmallett#define smallbin_index(sz) (((unsigned)(sz)) >> 3) 1978232809Sjmallett 1979232809Sjmallett#define largebin_index(sz) \ 1980232809Sjmallett(((((unsigned long)(sz)) >> 6) <= 32)? 56 + (((unsigned long)(sz)) >> 6): \ 1981232809Sjmallett ((((unsigned long)(sz)) >> 9) <= 20)? 91 + (((unsigned long)(sz)) >> 9): \ 1982232809Sjmallett ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \ 1983232809Sjmallett ((((unsigned long)(sz)) >> 15) <= 4)? 119 + (((unsigned long)(sz)) >> 15): \ 1984232809Sjmallett ((((unsigned long)(sz)) >> 18) <= 2)? 124 + (((unsigned long)(sz)) >> 18): \ 1985232809Sjmallett 126) 1986232809Sjmallett 1987232809Sjmallett#define bin_index(sz) \ 1988232809Sjmallett ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz)) 1989232809Sjmallett 1990232809Sjmallett/* 1991232809Sjmallett FIRST_SORTED_BIN_SIZE is the chunk size corresponding to the 1992232809Sjmallett first bin that is maintained in sorted order. This must 1993232809Sjmallett be the smallest size corresponding to a given bin. 1994232809Sjmallett 1995232809Sjmallett Normally, this should be MIN_LARGE_SIZE. But you can weaken 1996232809Sjmallett best fit guarantees to sometimes speed up malloc by increasing value. 1997232809Sjmallett Doing this means that malloc may choose a chunk that is 1998232809Sjmallett non-best-fitting by up to the width of the bin. 1999232809Sjmallett 2000232809Sjmallett Some useful cutoff values: 2001232809Sjmallett 512 - all bins sorted 2002232809Sjmallett 2560 - leaves bins <= 64 bytes wide unsorted 2003232809Sjmallett 12288 - leaves bins <= 512 bytes wide unsorted 2004232809Sjmallett 65536 - leaves bins <= 4096 bytes wide unsorted 2005232809Sjmallett 262144 - leaves bins <= 32768 bytes wide unsorted 2006232809Sjmallett -1 - no bins sorted (not recommended!) 2007232809Sjmallett*/ 2008232809Sjmallett 2009232809Sjmallett#define FIRST_SORTED_BIN_SIZE MIN_LARGE_SIZE 2010232809Sjmallett/* #define FIRST_SORTED_BIN_SIZE 65536 */ 2011232809Sjmallett 2012232809Sjmallett/* 2013232809Sjmallett Unsorted chunks 2014232809Sjmallett 2015232809Sjmallett All remainders from chunk splits, as well as all returned chunks, 2016232809Sjmallett are first placed in the "unsorted" bin. They are then placed 2017232809Sjmallett in regular bins after malloc gives them ONE chance to be used before 2018232809Sjmallett binning. So, basically, the unsorted_chunks list acts as a queue, 2019232809Sjmallett with chunks being placed on it in free (and malloc_consolidate), 2020232809Sjmallett and taken off (to be either used or placed in bins) in malloc. 2021232809Sjmallett 2022232809Sjmallett The NON_MAIN_ARENA flag is never set for unsorted chunks, so it 2023232809Sjmallett does not have to be taken into account in size comparisons. 2024232809Sjmallett*/ 2025232809Sjmallett 2026232809Sjmallett/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */ 2027232809Sjmallett#define unsorted_chunks(M) (bin_at(M, 1)) 2028232809Sjmallett 2029232809Sjmallett/* 2030232809Sjmallett Top 2031232809Sjmallett 2032232809Sjmallett The top-most available chunk (i.e., the one bordering the end of 2033232809Sjmallett available memory) is treated specially. It is never included in 2034232809Sjmallett any bin, is used only if no other chunk is available, and is 2035232809Sjmallett released back to the system if it is very large (see 2036232809Sjmallett M_TRIM_THRESHOLD). Because top initially 2037232809Sjmallett points to its own bin with initial zero size, thus forcing 2038232809Sjmallett extension on the first malloc request, we avoid having any special 2039232809Sjmallett code in malloc to check whether it even exists yet. But we still 2040232809Sjmallett need to do so when getting memory from system, so we make 2041232809Sjmallett initial_top treat the bin as a legal but unusable chunk during the 2042232809Sjmallett interval between initialization and the first call to 2043232809Sjmallett sYSMALLOc. (This is somewhat delicate, since it relies on 2044232809Sjmallett the 2 preceding words to be zero during this interval as well.) 2045232809Sjmallett*/ 2046232809Sjmallett 2047232809Sjmallett/* Conveniently, the unsorted bin can be used as dummy top on first call */ 2048232809Sjmallett#define initial_top(M) (unsorted_chunks(M)) 2049232809Sjmallett 2050232809Sjmallett/* 2051232809Sjmallett Binmap 2052232809Sjmallett 2053232809Sjmallett To help compensate for the large number of bins, a one-level index 2054232809Sjmallett structure is used for bin-by-bin searching. `binmap' is a 2055232809Sjmallett bitvector recording whether bins are definitely empty so they can 2056232809Sjmallett be skipped over during during traversals. The bits are NOT always 2057232809Sjmallett cleared as soon as bins are empty, but instead only 2058232809Sjmallett when they are noticed to be empty during traversal in malloc. 2059232809Sjmallett*/ 2060232809Sjmallett 2061232809Sjmallett/* Conservatively use 32 bits per map word, even if on 64bit system */ 2062232809Sjmallett#define BINMAPSHIFT 5 2063232809Sjmallett#define BITSPERMAP (1U << BINMAPSHIFT) 2064232809Sjmallett#define BINMAPSIZE (NBINS / BITSPERMAP) 2065232809Sjmallett 2066232809Sjmallett#define idx2block(i) ((i) >> BINMAPSHIFT) 2067232809Sjmallett#define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT)-1)))) 2068232809Sjmallett 2069232809Sjmallett#define mark_bin(m,i) ((m)->binmap[idx2block(i)] |= idx2bit(i)) 2070232809Sjmallett#define unmark_bin(m,i) ((m)->binmap[idx2block(i)] &= ~(idx2bit(i))) 2071232809Sjmallett#define get_binmap(m,i) ((m)->binmap[idx2block(i)] & idx2bit(i)) 2072232809Sjmallett 2073232809Sjmallett/* 2074232809Sjmallett Fastbins 2075232809Sjmallett 2076232809Sjmallett An array of lists holding recently freed small chunks. Fastbins 2077232809Sjmallett are not doubly linked. It is faster to single-link them, and 2078232809Sjmallett since chunks are never removed from the middles of these lists, 2079232809Sjmallett double linking is not necessary. Also, unlike regular bins, they 2080232809Sjmallett are not even processed in FIFO order (they use faster LIFO) since 2081232809Sjmallett ordering doesn't much matter in the transient contexts in which 2082232809Sjmallett fastbins are normally used. 2083232809Sjmallett 2084232809Sjmallett Chunks in fastbins keep their inuse bit set, so they cannot 2085232809Sjmallett be consolidated with other free chunks. malloc_consolidate 2086232809Sjmallett releases all chunks in fastbins and consolidates them with 2087232809Sjmallett other free chunks. 2088232809Sjmallett*/ 2089232809Sjmallett 2090232809Sjmalletttypedef struct malloc_chunk* mfastbinptr; 2091232809Sjmallett 2092232809Sjmallett/* offset 2 to use otherwise unindexable first 2 bins */ 2093232809Sjmallett#define fastbin_index(sz) ((int)((((unsigned int)(sz)) >> 3) - 2)) 2094232809Sjmallett 2095232809Sjmallett/* The maximum fastbin request size we support */ 2096232809Sjmallett#define MAX_FAST_SIZE 80 2097232809Sjmallett 2098232809Sjmallett#define NFASTBINS (fastbin_index(request2size(MAX_FAST_SIZE))+1) 2099232809Sjmallett 2100232809Sjmallett/* 2101232809Sjmallett FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free() 2102232809Sjmallett that triggers automatic consolidation of possibly-surrounding 2103232809Sjmallett fastbin chunks. This is a heuristic, so the exact value should not 2104232809Sjmallett matter too much. It is defined at half the default trim threshold as a 2105232809Sjmallett compromise heuristic to only attempt consolidation if it is likely 2106232809Sjmallett to lead to trimming. However, it is not dynamically tunable, since 2107232809Sjmallett consolidation reduces fragmentation surrounding large chunks even 2108232809Sjmallett if trimming is not used. 2109232809Sjmallett*/ 2110232809Sjmallett 2111232809Sjmallett#define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL) 2112232809Sjmallett 2113232809Sjmallett/* 2114232809Sjmallett Since the lowest 2 bits in max_fast don't matter in size comparisons, 2115232809Sjmallett they are used as flags. 2116232809Sjmallett*/ 2117232809Sjmallett 2118232809Sjmallett/* 2119232809Sjmallett FASTCHUNKS_BIT held in max_fast indicates that there are probably 2120232809Sjmallett some fastbin chunks. It is set true on entering a chunk into any 2121232809Sjmallett fastbin, and cleared only in malloc_consolidate. 2122232809Sjmallett 2123232809Sjmallett The truth value is inverted so that have_fastchunks will be true 2124232809Sjmallett upon startup (since statics are zero-filled), simplifying 2125232809Sjmallett initialization checks. 2126232809Sjmallett*/ 2127232809Sjmallett 2128232809Sjmallett#define FASTCHUNKS_BIT (1U) 2129232809Sjmallett 2130232809Sjmallett#define have_fastchunks(M) (((M)->max_fast & FASTCHUNKS_BIT) == 0) 2131232809Sjmallett#define clear_fastchunks(M) ((M)->max_fast |= FASTCHUNKS_BIT) 2132232809Sjmallett#define set_fastchunks(M) ((M)->max_fast &= ~FASTCHUNKS_BIT) 2133232809Sjmallett 2134232809Sjmallett/* 2135232809Sjmallett NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous 2136232809Sjmallett regions. Otherwise, contiguity is exploited in merging together, 2137232809Sjmallett when possible, results from consecutive MORECORE calls. 2138232809Sjmallett 2139232809Sjmallett The initial value comes from MORECORE_CONTIGUOUS, but is 2140232809Sjmallett changed dynamically if mmap is ever used as an sbrk substitute. 2141232809Sjmallett*/ 2142232809Sjmallett 2143232809Sjmallett#define NONCONTIGUOUS_BIT (2U) 2144232809Sjmallett 2145232809Sjmallett#define contiguous(M) (((M)->max_fast & NONCONTIGUOUS_BIT) == 0) 2146232809Sjmallett#define noncontiguous(M) (((M)->max_fast & NONCONTIGUOUS_BIT) != 0) 2147232809Sjmallett#define set_noncontiguous(M) ((M)->max_fast |= NONCONTIGUOUS_BIT) 2148232809Sjmallett#define set_contiguous(M) ((M)->max_fast &= ~NONCONTIGUOUS_BIT) 2149232809Sjmallett 2150232809Sjmallett/* 2151232809Sjmallett Set value of max_fast. 2152232809Sjmallett Use impossibly small value if 0. 2153232809Sjmallett Precondition: there are no existing fastbin chunks. 2154232809Sjmallett Setting the value clears fastchunk bit but preserves noncontiguous bit. 2155232809Sjmallett*/ 2156232809Sjmallett 2157232809Sjmallett#define set_max_fast(M, s) \ 2158232809Sjmallett (M)->max_fast = (((s) == 0)? SMALLBIN_WIDTH: request2size(s)) | \ 2159232809Sjmallett FASTCHUNKS_BIT | \ 2160232809Sjmallett ((M)->max_fast & NONCONTIGUOUS_BIT) 2161232809Sjmallett 2162232809Sjmallett 2163232809Sjmallett/* 2164232809Sjmallett ----------- Internal state representation and initialization ----------- 2165232809Sjmallett*/ 2166232809Sjmallett 2167232809Sjmallettstruct malloc_state { 2168232809Sjmallett /* Serialize access. */ 2169232809Sjmallett mutex_t mutex; 2170232809Sjmallett 2171232809Sjmallett /* Statistics for locking. Only used if THREAD_STATS is defined. */ 2172232809Sjmallett long stat_lock_direct, stat_lock_loop, stat_lock_wait; 2173232809Sjmallett long pad0_[1]; /* try to give the mutex its own cacheline */ 2174232809Sjmallett 2175232809Sjmallett /* The maximum chunk size to be eligible for fastbin */ 2176232809Sjmallett INTERNAL_SIZE_T max_fast; /* low 2 bits used as flags */ 2177232809Sjmallett 2178232809Sjmallett /* Fastbins */ 2179232809Sjmallett mfastbinptr fastbins[NFASTBINS]; 2180232809Sjmallett 2181232809Sjmallett /* Base of the topmost chunk -- not otherwise kept in a bin */ 2182232809Sjmallett mchunkptr top; 2183232809Sjmallett 2184232809Sjmallett /* The remainder from the most recent split of a small request */ 2185232809Sjmallett mchunkptr last_remainder; 2186232809Sjmallett 2187232809Sjmallett /* Normal bins packed as described above */ 2188232809Sjmallett mchunkptr bins[NBINS * 2]; 2189232809Sjmallett 2190232809Sjmallett /* Bitmap of bins */ 2191232809Sjmallett unsigned int binmap[BINMAPSIZE]; 2192232809Sjmallett 2193232809Sjmallett /* Linked list */ 2194232809Sjmallett struct malloc_state *next; 2195232809Sjmallett 2196232809Sjmallett /* Memory allocated from the system in this arena. */ 2197232809Sjmallett INTERNAL_SIZE_T system_mem; 2198232809Sjmallett INTERNAL_SIZE_T max_system_mem; 2199232809Sjmallett}; 2200232809Sjmallett 2201232809Sjmallettstruct malloc_par { 2202232809Sjmallett /* Tunable parameters */ 2203232809Sjmallett unsigned long trim_threshold; 2204232809Sjmallett INTERNAL_SIZE_T top_pad; 2205232809Sjmallett INTERNAL_SIZE_T mmap_threshold; 2206232809Sjmallett 2207232809Sjmallett /* Memory map support */ 2208232809Sjmallett int n_mmaps; 2209232809Sjmallett int n_mmaps_max; 2210232809Sjmallett int max_n_mmaps; 2211232809Sjmallett 2212232809Sjmallett /* Cache malloc_getpagesize */ 2213232809Sjmallett unsigned int pagesize; 2214232809Sjmallett 2215232809Sjmallett /* Statistics */ 2216232809Sjmallett INTERNAL_SIZE_T mmapped_mem; 2217232809Sjmallett /*INTERNAL_SIZE_T sbrked_mem;*/ 2218232809Sjmallett /*INTERNAL_SIZE_T max_sbrked_mem;*/ 2219232809Sjmallett INTERNAL_SIZE_T max_mmapped_mem; 2220232809Sjmallett INTERNAL_SIZE_T max_total_mem; /* only kept for NO_THREADS */ 2221232809Sjmallett 2222232809Sjmallett /* First address handed out by MORECORE/sbrk. */ 2223232809Sjmallett char* sbrk_base; 2224232809Sjmallett}; 2225232809Sjmallett 2226232809Sjmallett/* There are several instances of this struct ("arenas") in this 2227232809Sjmallett malloc. If you are adapting this malloc in a way that does NOT use 2228232809Sjmallett a static or mmapped malloc_state, you MUST explicitly zero-fill it 2229232809Sjmallett before using. This malloc relies on the property that malloc_state 2230232809Sjmallett is initialized to all zeroes (as is true of C statics). */ 2231232809Sjmallett 2232232809Sjmallett 2233232809Sjmallett 2234232809Sjmallett/* 2235232809Sjmallett Initialize a malloc_state struct. 2236232809Sjmallett 2237232809Sjmallett This is called only from within malloc_consolidate, which needs 2238232809Sjmallett be called in the same contexts anyway. It is never called directly 2239232809Sjmallett outside of malloc_consolidate because some optimizing compilers try 2240232809Sjmallett to inline it at all call points, which turns out not to be an 2241232809Sjmallett optimization at all. (Inlining it in malloc_consolidate is fine though.) 2242232809Sjmallett*/ 2243232809Sjmallett 2244232809Sjmallett#if __STD_C 2245232809Sjmallettstatic void malloc_init_state(mstate av) 2246232809Sjmallett#else 2247232809Sjmallettstatic void malloc_init_state(av) mstate av; 2248232809Sjmallett#endif 2249232809Sjmallett{ 2250232809Sjmallett int i; 2251232809Sjmallett mbinptr bin; 2252232809Sjmallett 2253232809Sjmallett /* Establish circular links for normal bins */ 2254232809Sjmallett for (i = 1; i < NBINS; ++i) { 2255232809Sjmallett bin = bin_at(av,i); 2256232809Sjmallett bin->fd = bin->bk = bin; 2257232809Sjmallett } 2258232809Sjmallett 2259232809Sjmallett set_noncontiguous(av); 2260232809Sjmallett 2261232809Sjmallett set_max_fast(av, DEFAULT_MXFAST); 2262232809Sjmallett 2263232809Sjmallett av->top = initial_top(av); 2264232809Sjmallett} 2265232809Sjmallett 2266232809Sjmallett/* 2267232809Sjmallett Other internal utilities operating on mstates 2268232809Sjmallett*/ 2269232809Sjmallett 2270232809Sjmallett#if __STD_C 2271232809Sjmallettstatic Void_t* sYSMALLOc(INTERNAL_SIZE_T, mstate); 2272232809Sjmallettstatic void malloc_consolidate(mstate); 2273232809Sjmallett//static Void_t** iALLOc(mstate, size_t, size_t*, int, Void_t**); 2274232809Sjmallett#else 2275232809Sjmallettstatic Void_t* sYSMALLOc(); 2276232809Sjmallettstatic void malloc_consolidate(); 2277232809Sjmallettstatic Void_t** iALLOc(); 2278232809Sjmallett#endif 2279232809Sjmallett 2280232809Sjmallett/* ------------------- Support for multiple arenas -------------------- */ 2281232809Sjmallett#include "arena.c" 2282232809Sjmallett 2283232809Sjmallett/* 2284232809Sjmallett Debugging support 2285232809Sjmallett 2286232809Sjmallett These routines make a number of assertions about the states 2287232809Sjmallett of data structures that should be true at all times. If any 2288232809Sjmallett are not true, it's very likely that a user program has somehow 2289232809Sjmallett trashed memory. (It's also possible that there is a coding error 2290232809Sjmallett in malloc. In which case, please report it!) 2291232809Sjmallett*/ 2292232809Sjmallett 2293232809Sjmallett#if ! MALLOC_DEBUG 2294232809Sjmallett 2295232809Sjmallett#define check_chunk(A,P) 2296232809Sjmallett#define check_free_chunk(A,P) 2297232809Sjmallett#define check_inuse_chunk(A,P) 2298232809Sjmallett#define check_remalloced_chunk(A,P,N) 2299232809Sjmallett#define check_malloced_chunk(A,P,N) 2300232809Sjmallett#define check_malloc_state(A) 2301232809Sjmallett 2302232809Sjmallett#else 2303232809Sjmallett 2304232809Sjmallett#define check_chunk(A,P) do_check_chunk(A,P) 2305232809Sjmallett#define check_free_chunk(A,P) do_check_free_chunk(A,P) 2306232809Sjmallett#define check_inuse_chunk(A,P) do_check_inuse_chunk(A,P) 2307232809Sjmallett#define check_remalloced_chunk(A,P,N) do_check_remalloced_chunk(A,P,N) 2308232809Sjmallett#define check_malloced_chunk(A,P,N) do_check_malloced_chunk(A,P,N) 2309232809Sjmallett#define check_malloc_state(A) do_check_malloc_state(A) 2310232809Sjmallett 2311232809Sjmallett/* 2312232809Sjmallett Properties of all chunks 2313232809Sjmallett*/ 2314232809Sjmallett 2315232809Sjmallett#if __STD_C 2316232809Sjmallettstatic void do_check_chunk(mstate av, mchunkptr p) 2317232809Sjmallett#else 2318232809Sjmallettstatic void do_check_chunk(av, p) mstate av; mchunkptr p; 2319232809Sjmallett#endif 2320232809Sjmallett{ 2321232809Sjmallett unsigned long sz = chunksize(p); 2322232809Sjmallett /* min and max possible addresses assuming contiguous allocation */ 2323232809Sjmallett char* max_address = (char*)(av->top) + chunksize(av->top); 2324232809Sjmallett char* min_address = max_address - av->system_mem; 2325232809Sjmallett 2326232809Sjmallett if (!chunk_is_mmapped(p)) { 2327232809Sjmallett 2328232809Sjmallett /* Has legal address ... */ 2329232809Sjmallett if (p != av->top) { 2330232809Sjmallett if (contiguous(av)) { 2331232809Sjmallett assert(((char*)p) >= min_address); 2332232809Sjmallett assert(((char*)p + sz) <= ((char*)(av->top))); 2333232809Sjmallett } 2334232809Sjmallett } 2335232809Sjmallett else { 2336232809Sjmallett /* top size is always at least MINSIZE */ 2337232809Sjmallett assert((unsigned long)(sz) >= MINSIZE); 2338232809Sjmallett /* top predecessor always marked inuse */ 2339232809Sjmallett assert(prev_inuse(p)); 2340232809Sjmallett } 2341232809Sjmallett 2342232809Sjmallett } 2343232809Sjmallett else { 2344232809Sjmallett#if HAVE_MMAP 2345232809Sjmallett /* address is outside main heap */ 2346232809Sjmallett if (contiguous(av) && av->top != initial_top(av)) { 2347232809Sjmallett assert(((char*)p) < min_address || ((char*)p) > max_address); 2348232809Sjmallett } 2349232809Sjmallett /* chunk is page-aligned */ 2350232809Sjmallett assert(((p->prev_size + sz) & (mp_.pagesize-1)) == 0); 2351232809Sjmallett /* mem is aligned */ 2352232809Sjmallett assert(aligned_OK(chunk2mem(p))); 2353232809Sjmallett#else 2354232809Sjmallett /* force an appropriate assert violation if debug set */ 2355232809Sjmallett assert(!chunk_is_mmapped(p)); 2356232809Sjmallett#endif 2357232809Sjmallett } 2358232809Sjmallett} 2359232809Sjmallett 2360232809Sjmallett/* 2361232809Sjmallett Properties of free chunks 2362232809Sjmallett*/ 2363232809Sjmallett 2364232809Sjmallett#if __STD_C 2365232809Sjmallettstatic void do_check_free_chunk(mstate av, mchunkptr p) 2366232809Sjmallett#else 2367232809Sjmallettstatic void do_check_free_chunk(av, p) mstate av; mchunkptr p; 2368232809Sjmallett#endif 2369232809Sjmallett{ 2370232809Sjmallett INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE); 2371232809Sjmallett mchunkptr next = chunk_at_offset(p, sz); 2372232809Sjmallett 2373232809Sjmallett do_check_chunk(av, p); 2374232809Sjmallett 2375232809Sjmallett /* Chunk must claim to be free ... */ 2376232809Sjmallett assert(!inuse(p)); 2377232809Sjmallett assert (!chunk_is_mmapped(p)); 2378232809Sjmallett 2379232809Sjmallett /* Unless a special marker, must have OK fields */ 2380232809Sjmallett if ((unsigned long)(sz) >= MINSIZE) 2381232809Sjmallett { 2382232809Sjmallett assert((sz & MALLOC_ALIGN_MASK) == 0); 2383232809Sjmallett assert(aligned_OK(chunk2mem(p))); 2384232809Sjmallett /* ... matching footer field */ 2385232809Sjmallett assert(next->prev_size == sz); 2386232809Sjmallett /* ... and is fully consolidated */ 2387232809Sjmallett assert(prev_inuse(p)); 2388232809Sjmallett assert (next == av->top || inuse(next)); 2389232809Sjmallett 2390232809Sjmallett /* ... and has minimally sane links */ 2391232809Sjmallett assert(p->fd->bk == p); 2392232809Sjmallett assert(p->bk->fd == p); 2393232809Sjmallett } 2394232809Sjmallett else /* markers are always of size SIZE_SZ */ 2395232809Sjmallett assert(sz == SIZE_SZ); 2396232809Sjmallett} 2397232809Sjmallett 2398232809Sjmallett/* 2399232809Sjmallett Properties of inuse chunks 2400232809Sjmallett*/ 2401232809Sjmallett 2402232809Sjmallett#if __STD_C 2403232809Sjmallettstatic void do_check_inuse_chunk(mstate av, mchunkptr p) 2404232809Sjmallett#else 2405232809Sjmallettstatic void do_check_inuse_chunk(av, p) mstate av; mchunkptr p; 2406232809Sjmallett#endif 2407232809Sjmallett{ 2408232809Sjmallett mchunkptr next; 2409232809Sjmallett 2410232809Sjmallett do_check_chunk(av, p); 2411232809Sjmallett 2412232809Sjmallett assert(av == arena_for_chunk(p)); 2413232809Sjmallett if (chunk_is_mmapped(p)) 2414232809Sjmallett return; /* mmapped chunks have no next/prev */ 2415232809Sjmallett 2416232809Sjmallett /* Check whether it claims to be in use ... */ 2417232809Sjmallett assert(inuse(p)); 2418232809Sjmallett 2419232809Sjmallett next = next_chunk(p); 2420232809Sjmallett 2421232809Sjmallett /* ... and is surrounded by OK chunks. 2422232809Sjmallett Since more things can be checked with free chunks than inuse ones, 2423232809Sjmallett if an inuse chunk borders them and debug is on, it's worth doing them. 2424232809Sjmallett */ 2425232809Sjmallett if (!prev_inuse(p)) { 2426232809Sjmallett /* Note that we cannot even look at prev unless it is not inuse */ 2427232809Sjmallett mchunkptr prv = prev_chunk(p); 2428232809Sjmallett assert(next_chunk(prv) == p); 2429232809Sjmallett do_check_free_chunk(av, prv); 2430232809Sjmallett } 2431232809Sjmallett 2432232809Sjmallett if (next == av->top) { 2433232809Sjmallett assert(prev_inuse(next)); 2434232809Sjmallett assert(chunksize(next) >= MINSIZE); 2435232809Sjmallett } 2436232809Sjmallett else if (!inuse(next)) 2437232809Sjmallett do_check_free_chunk(av, next); 2438232809Sjmallett} 2439232809Sjmallett 2440232809Sjmallett/* 2441232809Sjmallett Properties of chunks recycled from fastbins 2442232809Sjmallett*/ 2443232809Sjmallett 2444232809Sjmallett#if __STD_C 2445232809Sjmallettstatic void do_check_remalloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s) 2446232809Sjmallett#else 2447232809Sjmallettstatic void do_check_remalloced_chunk(av, p, s) 2448232809Sjmallettmstate av; mchunkptr p; INTERNAL_SIZE_T s; 2449232809Sjmallett#endif 2450232809Sjmallett{ 2451232809Sjmallett INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE); 2452232809Sjmallett 2453232809Sjmallett if (!chunk_is_mmapped(p)) { 2454232809Sjmallett assert(av == arena_for_chunk(p)); 2455232809Sjmallett } 2456232809Sjmallett 2457232809Sjmallett do_check_inuse_chunk(av, p); 2458232809Sjmallett 2459232809Sjmallett /* Legal size ... */ 2460232809Sjmallett assert((sz & MALLOC_ALIGN_MASK) == 0); 2461232809Sjmallett assert((unsigned long)(sz) >= MINSIZE); 2462232809Sjmallett /* ... and alignment */ 2463232809Sjmallett assert(aligned_OK(chunk2mem(p))); 2464232809Sjmallett /* chunk is less than MINSIZE more than request */ 2465232809Sjmallett assert((long)(sz) - (long)(s) >= 0); 2466232809Sjmallett assert((long)(sz) - (long)(s + MINSIZE) < 0); 2467232809Sjmallett} 2468232809Sjmallett 2469232809Sjmallett/* 2470232809Sjmallett Properties of nonrecycled chunks at the point they are malloced 2471232809Sjmallett*/ 2472232809Sjmallett 2473232809Sjmallett#if __STD_C 2474232809Sjmallettstatic void do_check_malloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s) 2475232809Sjmallett#else 2476232809Sjmallettstatic void do_check_malloced_chunk(av, p, s) 2477232809Sjmallettmstate av; mchunkptr p; INTERNAL_SIZE_T s; 2478232809Sjmallett#endif 2479232809Sjmallett{ 2480232809Sjmallett /* same as recycled case ... */ 2481232809Sjmallett do_check_remalloced_chunk(av, p, s); 2482232809Sjmallett 2483232809Sjmallett /* 2484232809Sjmallett ... plus, must obey implementation invariant that prev_inuse is 2485232809Sjmallett always true of any allocated chunk; i.e., that each allocated 2486232809Sjmallett chunk borders either a previously allocated and still in-use 2487232809Sjmallett chunk, or the base of its memory arena. This is ensured 2488232809Sjmallett by making all allocations from the the `lowest' part of any found 2489232809Sjmallett chunk. This does not necessarily hold however for chunks 2490232809Sjmallett recycled via fastbins. 2491232809Sjmallett */ 2492232809Sjmallett 2493232809Sjmallett assert(prev_inuse(p)); 2494232809Sjmallett} 2495232809Sjmallett 2496232809Sjmallett 2497232809Sjmallett/* 2498232809Sjmallett Properties of malloc_state. 2499232809Sjmallett 2500232809Sjmallett This may be useful for debugging malloc, as well as detecting user 2501232809Sjmallett programmer errors that somehow write into malloc_state. 2502232809Sjmallett 2503232809Sjmallett If you are extending or experimenting with this malloc, you can 2504232809Sjmallett probably figure out how to hack this routine to print out or 2505232809Sjmallett display chunk addresses, sizes, bins, and other instrumentation. 2506232809Sjmallett*/ 2507232809Sjmallett 2508232809Sjmallettstatic void do_check_malloc_state(mstate av) 2509232809Sjmallett{ 2510232809Sjmallett int i; 2511232809Sjmallett mchunkptr p; 2512232809Sjmallett mchunkptr q; 2513232809Sjmallett mbinptr b; 2514232809Sjmallett unsigned int binbit; 2515232809Sjmallett int empty; 2516232809Sjmallett unsigned int idx; 2517232809Sjmallett INTERNAL_SIZE_T size; 2518232809Sjmallett unsigned long total = 0; 2519232809Sjmallett int max_fast_bin; 2520232809Sjmallett 2521232809Sjmallett /* internal size_t must be no wider than pointer type */ 2522232809Sjmallett assert(sizeof(INTERNAL_SIZE_T) <= sizeof(char*)); 2523232809Sjmallett 2524232809Sjmallett /* alignment is a power of 2 */ 2525232809Sjmallett assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0); 2526232809Sjmallett 2527232809Sjmallett /* cannot run remaining checks until fully initialized */ 2528232809Sjmallett if (av->top == 0 || av->top == initial_top(av)) 2529232809Sjmallett return; 2530232809Sjmallett 2531232809Sjmallett 2532232809Sjmallett /* properties of fastbins */ 2533232809Sjmallett 2534232809Sjmallett /* max_fast is in allowed range */ 2535232809Sjmallett assert((av->max_fast & ~1) <= request2size(MAX_FAST_SIZE)); 2536232809Sjmallett 2537232809Sjmallett max_fast_bin = fastbin_index(av->max_fast); 2538232809Sjmallett 2539232809Sjmallett for (i = 0; i < NFASTBINS; ++i) { 2540232809Sjmallett p = av->fastbins[i]; 2541232809Sjmallett 2542232809Sjmallett /* all bins past max_fast are empty */ 2543232809Sjmallett if (i > max_fast_bin) 2544232809Sjmallett assert(p == 0); 2545232809Sjmallett 2546232809Sjmallett while (p != 0) { 2547232809Sjmallett /* each chunk claims to be inuse */ 2548232809Sjmallett do_check_inuse_chunk(av, p); 2549232809Sjmallett total += chunksize(p); 2550232809Sjmallett /* chunk belongs in this bin */ 2551232809Sjmallett assert(fastbin_index(chunksize(p)) == i); 2552232809Sjmallett p = p->fd; 2553232809Sjmallett } 2554232809Sjmallett } 2555232809Sjmallett 2556232809Sjmallett if (total != 0) 2557232809Sjmallett assert(have_fastchunks(av)); 2558232809Sjmallett else if (!have_fastchunks(av)) 2559232809Sjmallett assert(total == 0); 2560232809Sjmallett 2561232809Sjmallett /* check normal bins */ 2562232809Sjmallett for (i = 1; i < NBINS; ++i) { 2563232809Sjmallett b = bin_at(av,i); 2564232809Sjmallett 2565232809Sjmallett /* binmap is accurate (except for bin 1 == unsorted_chunks) */ 2566232809Sjmallett if (i >= 2) { 2567232809Sjmallett binbit = get_binmap(av,i); 2568232809Sjmallett empty = last(b) == b; 2569232809Sjmallett if (!binbit) 2570232809Sjmallett assert(empty); 2571232809Sjmallett else if (!empty) 2572232809Sjmallett assert(binbit); 2573232809Sjmallett } 2574232809Sjmallett 2575232809Sjmallett for (p = last(b); p != b; p = p->bk) { 2576232809Sjmallett /* each chunk claims to be free */ 2577232809Sjmallett do_check_free_chunk(av, p); 2578232809Sjmallett size = chunksize(p); 2579232809Sjmallett total += size; 2580232809Sjmallett if (i >= 2) { 2581232809Sjmallett /* chunk belongs in bin */ 2582232809Sjmallett idx = bin_index(size); 2583232809Sjmallett assert(idx == (unsigned int)i); 2584232809Sjmallett /* lists are sorted */ 2585232809Sjmallett if ((unsigned long) size >= (unsigned long)(FIRST_SORTED_BIN_SIZE)) { 2586232809Sjmallett assert(p->bk == b || 2587232809Sjmallett (unsigned long)chunksize(p->bk) >= 2588232809Sjmallett (unsigned long)chunksize(p)); 2589232809Sjmallett } 2590232809Sjmallett } 2591232809Sjmallett /* chunk is followed by a legal chain of inuse chunks */ 2592232809Sjmallett for (q = next_chunk(p); 2593232809Sjmallett (q != av->top && inuse(q) && 2594232809Sjmallett (unsigned long)(chunksize(q)) >= MINSIZE); 2595232809Sjmallett q = next_chunk(q)) 2596232809Sjmallett do_check_inuse_chunk(av, q); 2597232809Sjmallett } 2598232809Sjmallett } 2599232809Sjmallett 2600232809Sjmallett /* top chunk is OK */ 2601232809Sjmallett check_chunk(av, av->top); 2602232809Sjmallett 2603232809Sjmallett /* sanity checks for statistics */ 2604232809Sjmallett 2605232809Sjmallett 2606232809Sjmallett assert((unsigned long)(av->system_mem) <= 2607232809Sjmallett (unsigned long)(av->max_system_mem)); 2608232809Sjmallett 2609232809Sjmallett 2610232809Sjmallett} 2611232809Sjmallett#endif 2612232809Sjmallett 2613232809Sjmallett 2614232809Sjmallett 2615232809Sjmallett/* ----------- Routines dealing with system allocation -------------- */ 2616232809Sjmallett 2617232809Sjmallett/* No system allocation routines supported */ 2618232809Sjmallett 2619232809Sjmallett 2620232809Sjmallett/*------------------------ Public wrappers. --------------------------------*/ 2621232809Sjmallett 2622232809Sjmallett 2623232809Sjmallett 2624232809Sjmallett#undef DEBUG_MALLOC 2625232809SjmallettVoid_t* 2626232809Sjmallettpublic_mALLOc(cvmx_arena_list_t arena_list, size_t bytes) 2627232809Sjmallett{ 2628232809Sjmallett mstate ar_ptr, orig_ar_ptr; 2629232809Sjmallett Void_t *victim = NULL; 2630232809Sjmallett static mstate debug_prev_ar; // debug only! 2631232809Sjmallett#ifdef DEBUG_MALLOC 2632232809Sjmallett int arena_cnt=0; 2633232809Sjmallett#endif 2634232809Sjmallett 2635232809Sjmallett ar_ptr = arena_list; 2636232809Sjmallett 2637232809Sjmallett if (!ar_ptr) 2638232809Sjmallett { 2639232809Sjmallett return(NULL); 2640232809Sjmallett } 2641232809Sjmallett 2642232809Sjmallett if (debug_prev_ar != ar_ptr) 2643232809Sjmallett { 2644232809Sjmallett debug_printf("New arena: %p\n", ar_ptr); 2645232809Sjmallett#ifdef CVMX_SPINLOCK_DEBUG 2646232809Sjmallett cvmx_dprintf("lock wait count for arena: %p is %ld\n", ar_ptr, ar_ptr->mutex.wait_cnt); 2647232809Sjmallett#endif 2648232809Sjmallett debug_prev_ar = ar_ptr; 2649232809Sjmallett } 2650232809Sjmallett orig_ar_ptr = ar_ptr; 2651232809Sjmallett 2652232809Sjmallett // try to get an arena without contention 2653232809Sjmallett do 2654232809Sjmallett { 2655232809Sjmallett#ifdef DEBUG_MALLOC 2656232809Sjmallett arena_cnt++; 2657232809Sjmallett#endif 2658232809Sjmallett if (!mutex_trylock(&ar_ptr->mutex)) 2659232809Sjmallett { 2660232809Sjmallett // we locked it 2661232809Sjmallett victim = _int_malloc(ar_ptr, bytes); 2662232809Sjmallett (void)mutex_unlock(&ar_ptr->mutex); 2663232809Sjmallett if(victim) 2664232809Sjmallett { 2665232809Sjmallett break; 2666232809Sjmallett } 2667232809Sjmallett } 2668232809Sjmallett ar_ptr = ar_ptr->next; 2669232809Sjmallett } while (ar_ptr != orig_ar_ptr); 2670232809Sjmallett 2671232809Sjmallett // we couldn't get the memory without contention, so try all 2672232809Sjmallett // arenas. SLOW! 2673232809Sjmallett if (!victim) 2674232809Sjmallett { 2675232809Sjmallett ar_ptr = orig_ar_ptr; 2676232809Sjmallett do 2677232809Sjmallett { 2678232809Sjmallett#ifdef DEBUG_MALLOC 2679232809Sjmallett arena_cnt++; 2680232809Sjmallett#endif 2681232809Sjmallett mutex_lock(&ar_ptr->mutex); 2682232809Sjmallett victim = _int_malloc(ar_ptr, bytes); 2683232809Sjmallett (void)mutex_unlock(&ar_ptr->mutex); 2684232809Sjmallett if(victim) 2685232809Sjmallett { 2686232809Sjmallett break; 2687232809Sjmallett } 2688232809Sjmallett ar_ptr = ar_ptr->next; 2689232809Sjmallett } while (ar_ptr != orig_ar_ptr); 2690232809Sjmallett } 2691232809Sjmallett 2692232809Sjmallett 2693232809Sjmallett assert(!victim || chunk_is_mmapped(mem2chunk(victim)) || 2694232809Sjmallett ar_ptr == arena_for_chunk(mem2chunk(victim))); 2695232809Sjmallett 2696232809Sjmallett#ifdef DEBUG_MALLOC 2697232809Sjmallett if (!victim) 2698232809Sjmallett { 2699232809Sjmallett cvmx_dprintf("Malloc failed: size: %ld, arena_cnt: %d\n", bytes, arena_cnt); 2700232809Sjmallett } 2701232809Sjmallett#endif 2702232809Sjmallett 2703232809Sjmallett debug_printf("cvmx_malloc(%ld) = %p\n", bytes, victim); 2704232809Sjmallett 2705232809Sjmallett // remember which arena we last used..... 2706232809Sjmallett tsd_setspecific(arena_key, (Void_t *)ar_ptr); 2707232809Sjmallett return victim; 2708232809Sjmallett} 2709232809Sjmallett 2710232809Sjmallett 2711232809Sjmallett 2712232809Sjmallettvoid 2713232809Sjmallettpublic_fREe(Void_t* mem) 2714232809Sjmallett{ 2715232809Sjmallett mstate ar_ptr; 2716232809Sjmallett mchunkptr p; /* chunk corresponding to mem */ 2717232809Sjmallett 2718232809Sjmallett debug_printf("cvmx_free(%p)\n", mem); 2719232809Sjmallett 2720232809Sjmallett 2721232809Sjmallett if (mem == 0) /* free(0) has no effect */ 2722232809Sjmallett return; 2723232809Sjmallett 2724232809Sjmallett p = mem2chunk(mem); 2725232809Sjmallett 2726232809Sjmallett 2727232809Sjmallett ar_ptr = arena_for_chunk(p); 2728232809Sjmallett assert(ar_ptr); 2729232809Sjmallett#if THREAD_STATS 2730232809Sjmallett if(!mutex_trylock(&ar_ptr->mutex)) 2731232809Sjmallett ++(ar_ptr->stat_lock_direct); 2732232809Sjmallett else { 2733232809Sjmallett (void)mutex_lock(&ar_ptr->mutex); 2734232809Sjmallett ++(ar_ptr->stat_lock_wait); 2735232809Sjmallett } 2736232809Sjmallett#else 2737232809Sjmallett (void)mutex_lock(&ar_ptr->mutex); 2738232809Sjmallett#endif 2739232809Sjmallett _int_free(ar_ptr, mem); 2740232809Sjmallett (void)mutex_unlock(&ar_ptr->mutex); 2741232809Sjmallett} 2742232809Sjmallett 2743232809SjmallettVoid_t* 2744232809Sjmallettpublic_rEALLOc(cvmx_arena_list_t arena_list, Void_t* oldmem, size_t bytes) 2745232809Sjmallett{ 2746232809Sjmallett mstate ar_ptr; 2747232809Sjmallett INTERNAL_SIZE_T nb; /* padded request size */ 2748232809Sjmallett 2749232809Sjmallett mchunkptr oldp; /* chunk corresponding to oldmem */ 2750232809Sjmallett INTERNAL_SIZE_T oldsize; /* its size */ 2751232809Sjmallett 2752232809Sjmallett Void_t* newp; /* chunk to return */ 2753232809Sjmallett 2754232809Sjmallett 2755232809Sjmallett#if REALLOC_ZERO_BYTES_FREES 2756232809Sjmallett if (bytes == 0 && oldmem != NULL) { public_fREe(oldmem); return 0; } 2757232809Sjmallett#endif 2758232809Sjmallett 2759232809Sjmallett /* realloc of null is supposed to be same as malloc */ 2760232809Sjmallett if (oldmem == 0) return public_mALLOc(arena_list, bytes); 2761232809Sjmallett 2762232809Sjmallett oldp = mem2chunk(oldmem); 2763232809Sjmallett oldsize = chunksize(oldp); 2764232809Sjmallett 2765232809Sjmallett checked_request2size(bytes, nb); 2766232809Sjmallett 2767232809Sjmallett 2768232809Sjmallett ar_ptr = arena_for_chunk(oldp); 2769232809Sjmallett (void)mutex_lock(&ar_ptr->mutex); 2770232809Sjmallett 2771232809Sjmallett 2772232809Sjmallett newp = _int_realloc(ar_ptr, oldmem, bytes); 2773232809Sjmallett 2774232809Sjmallett (void)mutex_unlock(&ar_ptr->mutex); 2775232809Sjmallett assert(!newp || chunk_is_mmapped(mem2chunk(newp)) || 2776232809Sjmallett ar_ptr == arena_for_chunk(mem2chunk(newp))); 2777232809Sjmallett return newp; 2778232809Sjmallett} 2779232809Sjmallett 2780232809Sjmallett#undef DEBUG_MEMALIGN 2781232809SjmallettVoid_t* 2782232809Sjmallettpublic_mEMALIGn(cvmx_arena_list_t arena_list, size_t alignment, size_t bytes) 2783232809Sjmallett{ 2784232809Sjmallett mstate ar_ptr, orig_ar_ptr; 2785232809Sjmallett Void_t *p = NULL; 2786232809Sjmallett#ifdef DEBUG_MEMALIGN 2787232809Sjmallett int arena_cnt=0; 2788232809Sjmallett#endif 2789232809Sjmallett 2790232809Sjmallett 2791232809Sjmallett /* If need less alignment than we give anyway, just relay to malloc */ 2792232809Sjmallett if (alignment <= MALLOC_ALIGNMENT) return public_mALLOc(arena_list, bytes); 2793232809Sjmallett 2794232809Sjmallett /* Otherwise, ensure that it is at least a minimum chunk size */ 2795232809Sjmallett if (alignment < MINSIZE) alignment = MINSIZE; 2796232809Sjmallett 2797232809Sjmallett 2798232809Sjmallett ar_ptr = arena_list; 2799232809Sjmallett 2800232809Sjmallett if (!ar_ptr) 2801232809Sjmallett { 2802232809Sjmallett return(NULL); 2803232809Sjmallett } 2804232809Sjmallett 2805232809Sjmallett orig_ar_ptr = ar_ptr; 2806232809Sjmallett 2807232809Sjmallett 2808232809Sjmallett // try to get an arena without contention 2809232809Sjmallett do 2810232809Sjmallett { 2811232809Sjmallett 2812232809Sjmallett#ifdef DEBUG_MEMALIGN 2813232809Sjmallett arena_cnt++; 2814232809Sjmallett#endif 2815232809Sjmallett if (!mutex_trylock(&ar_ptr->mutex)) 2816232809Sjmallett { 2817232809Sjmallett // we locked it 2818232809Sjmallett p = _int_memalign(ar_ptr, alignment, bytes); 2819232809Sjmallett (void)mutex_unlock(&ar_ptr->mutex); 2820232809Sjmallett if(p) 2821232809Sjmallett { 2822232809Sjmallett break; 2823232809Sjmallett } 2824232809Sjmallett } 2825232809Sjmallett ar_ptr = ar_ptr->next; 2826232809Sjmallett } while (ar_ptr != orig_ar_ptr); 2827232809Sjmallett 2828232809Sjmallett 2829232809Sjmallett // we couldn't get the memory without contention, so try all 2830232809Sjmallett // arenas. SLOW! 2831232809Sjmallett if (!p) 2832232809Sjmallett { 2833232809Sjmallett#ifdef DEBUG_MEMALIGN 2834232809Sjmallett arena_cnt++; 2835232809Sjmallett#endif 2836232809Sjmallett ar_ptr = orig_ar_ptr; 2837232809Sjmallett do 2838232809Sjmallett { 2839232809Sjmallett mutex_lock(&ar_ptr->mutex); 2840232809Sjmallett p = _int_memalign(ar_ptr, alignment, bytes); 2841232809Sjmallett (void)mutex_unlock(&ar_ptr->mutex); 2842232809Sjmallett if(p) 2843232809Sjmallett { 2844232809Sjmallett break; 2845232809Sjmallett } 2846232809Sjmallett ar_ptr = ar_ptr->next; 2847232809Sjmallett } while (ar_ptr != orig_ar_ptr); 2848232809Sjmallett } 2849232809Sjmallett 2850232809Sjmallett 2851232809Sjmallett if (p) 2852232809Sjmallett { 2853232809Sjmallett assert(ar_ptr == arena_for_chunk(mem2chunk(p))); 2854232809Sjmallett } 2855232809Sjmallett else 2856232809Sjmallett { 2857232809Sjmallett#ifdef DEBUG_MEMALIGN 2858232809Sjmallett cvmx_dprintf("Memalign failed: align: 0x%x, size: %ld, arena_cnt: %ld\n", alignment, bytes, arena_cnt); 2859232809Sjmallett#endif 2860232809Sjmallett } 2861232809Sjmallett 2862232809Sjmallett assert(!p || ar_ptr == arena_for_chunk(mem2chunk(p))); 2863232809Sjmallett return p; 2864232809Sjmallett} 2865232809Sjmallett 2866232809Sjmallett 2867232809Sjmallett 2868232809SjmallettVoid_t* 2869232809Sjmallettpublic_cALLOc(cvmx_arena_list_t arena_list, size_t n, size_t elem_size) 2870232809Sjmallett{ 2871232809Sjmallett mstate av; 2872232809Sjmallett mchunkptr oldtop, p; 2873232809Sjmallett INTERNAL_SIZE_T sz, csz, oldtopsize; 2874232809Sjmallett Void_t* mem; 2875232809Sjmallett unsigned long clearsize; 2876232809Sjmallett unsigned long nclears; 2877232809Sjmallett INTERNAL_SIZE_T* d; 2878232809Sjmallett 2879232809Sjmallett 2880232809Sjmallett /* FIXME: check for overflow on multiplication. */ 2881232809Sjmallett sz = n * elem_size; 2882232809Sjmallett 2883232809Sjmallett mem = public_mALLOc(arena_list, sz); 2884232809Sjmallett if (mem) 2885232809Sjmallett { 2886232809Sjmallett memset(mem, 0, sz); 2887232809Sjmallett } 2888232809Sjmallett 2889232809Sjmallett return mem; 2890232809Sjmallett} 2891232809Sjmallett 2892232809Sjmallett 2893232809Sjmallett#ifndef _LIBC 2894232809Sjmallett 2895232809Sjmallettvoid 2896232809Sjmallettpublic_cFREe(Void_t* m) 2897232809Sjmallett{ 2898232809Sjmallett public_fREe(m); 2899232809Sjmallett} 2900232809Sjmallett 2901232809Sjmallett#endif /* _LIBC */ 2902232809Sjmallett 2903232809Sjmallett/* 2904232809Sjmallett ------------------------------ malloc ------------------------------ 2905232809Sjmallett*/ 2906232809Sjmallett 2907232809Sjmallettstatic Void_t* 2908232809Sjmallett_int_malloc(mstate av, size_t bytes) 2909232809Sjmallett{ 2910232809Sjmallett INTERNAL_SIZE_T nb; /* normalized request size */ 2911232809Sjmallett unsigned int idx; /* associated bin index */ 2912232809Sjmallett mbinptr bin; /* associated bin */ 2913232809Sjmallett mfastbinptr* fb; /* associated fastbin */ 2914232809Sjmallett 2915232809Sjmallett mchunkptr victim; /* inspected/selected chunk */ 2916232809Sjmallett INTERNAL_SIZE_T size; /* its size */ 2917232809Sjmallett int victim_index; /* its bin index */ 2918232809Sjmallett 2919232809Sjmallett mchunkptr remainder; /* remainder from a split */ 2920232809Sjmallett unsigned long remainder_size; /* its size */ 2921232809Sjmallett 2922232809Sjmallett unsigned int block; /* bit map traverser */ 2923232809Sjmallett unsigned int bit; /* bit map traverser */ 2924232809Sjmallett unsigned int map; /* current word of binmap */ 2925232809Sjmallett 2926232809Sjmallett mchunkptr fwd; /* misc temp for linking */ 2927232809Sjmallett mchunkptr bck; /* misc temp for linking */ 2928232809Sjmallett 2929232809Sjmallett /* 2930232809Sjmallett Convert request size to internal form by adding SIZE_SZ bytes 2931232809Sjmallett overhead plus possibly more to obtain necessary alignment and/or 2932232809Sjmallett to obtain a size of at least MINSIZE, the smallest allocatable 2933232809Sjmallett size. Also, checked_request2size traps (returning 0) request sizes 2934232809Sjmallett that are so large that they wrap around zero when padded and 2935232809Sjmallett aligned. 2936232809Sjmallett */ 2937232809Sjmallett 2938232809Sjmallett 2939232809Sjmallett checked_request2size(bytes, nb); 2940232809Sjmallett 2941232809Sjmallett /* 2942232809Sjmallett If the size qualifies as a fastbin, first check corresponding bin. 2943232809Sjmallett This code is safe to execute even if av is not yet initialized, so we 2944232809Sjmallett can try it without checking, which saves some time on this fast path. 2945232809Sjmallett */ 2946232809Sjmallett 2947232809Sjmallett if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) { 2948232809Sjmallett fb = &(av->fastbins[(fastbin_index(nb))]); 2949232809Sjmallett if ( (victim = *fb) != 0) { 2950232809Sjmallett *fb = victim->fd; 2951232809Sjmallett check_remalloced_chunk(av, victim, nb); 2952232809Sjmallett set_arena_for_chunk(victim, av); 2953232809Sjmallett return chunk2mem(victim); 2954232809Sjmallett } 2955232809Sjmallett } 2956232809Sjmallett 2957232809Sjmallett /* 2958232809Sjmallett If a small request, check regular bin. Since these "smallbins" 2959232809Sjmallett hold one size each, no searching within bins is necessary. 2960232809Sjmallett (For a large request, we need to wait until unsorted chunks are 2961232809Sjmallett processed to find best fit. But for small ones, fits are exact 2962232809Sjmallett anyway, so we can check now, which is faster.) 2963232809Sjmallett */ 2964232809Sjmallett 2965232809Sjmallett if (in_smallbin_range(nb)) { 2966232809Sjmallett idx = smallbin_index(nb); 2967232809Sjmallett bin = bin_at(av,idx); 2968232809Sjmallett 2969232809Sjmallett if ( (victim = last(bin)) != bin) { 2970232809Sjmallett if (victim == 0) /* initialization check */ 2971232809Sjmallett malloc_consolidate(av); 2972232809Sjmallett else { 2973232809Sjmallett bck = victim->bk; 2974232809Sjmallett set_inuse_bit_at_offset(victim, nb); 2975232809Sjmallett bin->bk = bck; 2976232809Sjmallett bck->fd = bin; 2977232809Sjmallett 2978232809Sjmallett set_arena_for_chunk(victim, av); 2979232809Sjmallett check_malloced_chunk(av, victim, nb); 2980232809Sjmallett return chunk2mem(victim); 2981232809Sjmallett } 2982232809Sjmallett } 2983232809Sjmallett } 2984232809Sjmallett 2985232809Sjmallett /* 2986232809Sjmallett If this is a large request, consolidate fastbins before continuing. 2987232809Sjmallett While it might look excessive to kill all fastbins before 2988232809Sjmallett even seeing if there is space available, this avoids 2989232809Sjmallett fragmentation problems normally associated with fastbins. 2990232809Sjmallett Also, in practice, programs tend to have runs of either small or 2991232809Sjmallett large requests, but less often mixtures, so consolidation is not 2992232809Sjmallett invoked all that often in most programs. And the programs that 2993232809Sjmallett it is called frequently in otherwise tend to fragment. 2994232809Sjmallett */ 2995232809Sjmallett 2996232809Sjmallett else { 2997232809Sjmallett idx = largebin_index(nb); 2998232809Sjmallett if (have_fastchunks(av)) 2999232809Sjmallett malloc_consolidate(av); 3000232809Sjmallett } 3001232809Sjmallett 3002232809Sjmallett /* 3003232809Sjmallett Process recently freed or remaindered chunks, taking one only if 3004232809Sjmallett it is exact fit, or, if this a small request, the chunk is remainder from 3005232809Sjmallett the most recent non-exact fit. Place other traversed chunks in 3006232809Sjmallett bins. Note that this step is the only place in any routine where 3007232809Sjmallett chunks are placed in bins. 3008232809Sjmallett 3009232809Sjmallett The outer loop here is needed because we might not realize until 3010232809Sjmallett near the end of malloc that we should have consolidated, so must 3011232809Sjmallett do so and retry. This happens at most once, and only when we would 3012232809Sjmallett otherwise need to expand memory to service a "small" request. 3013232809Sjmallett */ 3014232809Sjmallett 3015232809Sjmallett for(;;) { 3016232809Sjmallett 3017232809Sjmallett while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) { 3018232809Sjmallett bck = victim->bk; 3019232809Sjmallett size = chunksize(victim); 3020232809Sjmallett 3021232809Sjmallett /* 3022232809Sjmallett If a small request, try to use last remainder if it is the 3023232809Sjmallett only chunk in unsorted bin. This helps promote locality for 3024232809Sjmallett runs of consecutive small requests. This is the only 3025232809Sjmallett exception to best-fit, and applies only when there is 3026232809Sjmallett no exact fit for a small chunk. 3027232809Sjmallett */ 3028232809Sjmallett 3029232809Sjmallett if (in_smallbin_range(nb) && 3030232809Sjmallett bck == unsorted_chunks(av) && 3031232809Sjmallett victim == av->last_remainder && 3032232809Sjmallett (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) { 3033232809Sjmallett 3034232809Sjmallett /* split and reattach remainder */ 3035232809Sjmallett remainder_size = size - nb; 3036232809Sjmallett remainder = chunk_at_offset(victim, nb); 3037232809Sjmallett unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder; 3038232809Sjmallett av->last_remainder = remainder; 3039232809Sjmallett remainder->bk = remainder->fd = unsorted_chunks(av); 3040232809Sjmallett 3041232809Sjmallett set_head(victim, nb | PREV_INUSE); 3042232809Sjmallett set_head(remainder, remainder_size | PREV_INUSE); 3043232809Sjmallett set_foot(remainder, remainder_size); 3044232809Sjmallett 3045232809Sjmallett set_arena_for_chunk(victim, av); 3046232809Sjmallett check_malloced_chunk(av, victim, nb); 3047232809Sjmallett return chunk2mem(victim); 3048232809Sjmallett } 3049232809Sjmallett 3050232809Sjmallett /* remove from unsorted list */ 3051232809Sjmallett unsorted_chunks(av)->bk = bck; 3052232809Sjmallett bck->fd = unsorted_chunks(av); 3053232809Sjmallett 3054232809Sjmallett /* Take now instead of binning if exact fit */ 3055232809Sjmallett 3056232809Sjmallett if (size == nb) { 3057232809Sjmallett set_inuse_bit_at_offset(victim, size); 3058232809Sjmallett set_arena_for_chunk(victim, av); 3059232809Sjmallett check_malloced_chunk(av, victim, nb); 3060232809Sjmallett return chunk2mem(victim); 3061232809Sjmallett } 3062232809Sjmallett 3063232809Sjmallett /* place chunk in bin */ 3064232809Sjmallett 3065232809Sjmallett if (in_smallbin_range(size)) { 3066232809Sjmallett victim_index = smallbin_index(size); 3067232809Sjmallett bck = bin_at(av, victim_index); 3068232809Sjmallett fwd = bck->fd; 3069232809Sjmallett } 3070232809Sjmallett else { 3071232809Sjmallett victim_index = largebin_index(size); 3072232809Sjmallett bck = bin_at(av, victim_index); 3073232809Sjmallett fwd = bck->fd; 3074232809Sjmallett 3075232809Sjmallett if (fwd != bck) { 3076232809Sjmallett /* if smaller than smallest, place first */ 3077232809Sjmallett if ((unsigned long)(size) < (unsigned long)(bck->bk->size)) { 3078232809Sjmallett fwd = bck; 3079232809Sjmallett bck = bck->bk; 3080232809Sjmallett } 3081232809Sjmallett else if ((unsigned long)(size) >= 3082232809Sjmallett (unsigned long)(FIRST_SORTED_BIN_SIZE)) { 3083232809Sjmallett 3084232809Sjmallett /* maintain large bins in sorted order */ 3085232809Sjmallett size |= PREV_INUSE; /* Or with inuse bit to speed comparisons */ 3086232809Sjmallett while ((unsigned long)(size) < (unsigned long)(fwd->size)) { 3087232809Sjmallett fwd = fwd->fd; 3088232809Sjmallett } 3089232809Sjmallett bck = fwd->bk; 3090232809Sjmallett } 3091232809Sjmallett } 3092232809Sjmallett } 3093232809Sjmallett 3094232809Sjmallett mark_bin(av, victim_index); 3095232809Sjmallett victim->bk = bck; 3096232809Sjmallett victim->fd = fwd; 3097232809Sjmallett fwd->bk = victim; 3098232809Sjmallett bck->fd = victim; 3099232809Sjmallett } 3100232809Sjmallett 3101232809Sjmallett /* 3102232809Sjmallett If a large request, scan through the chunks of current bin in 3103232809Sjmallett sorted order to find smallest that fits. This is the only step 3104232809Sjmallett where an unbounded number of chunks might be scanned without doing 3105232809Sjmallett anything useful with them. However the lists tend to be short. 3106232809Sjmallett */ 3107232809Sjmallett 3108232809Sjmallett if (!in_smallbin_range(nb)) { 3109232809Sjmallett bin = bin_at(av, idx); 3110232809Sjmallett 3111232809Sjmallett for (victim = last(bin); victim != bin; victim = victim->bk) { 3112232809Sjmallett size = chunksize(victim); 3113232809Sjmallett 3114232809Sjmallett if ((unsigned long)(size) >= (unsigned long)(nb)) { 3115232809Sjmallett remainder_size = size - nb; 3116232809Sjmallett unlink(victim, bck, fwd); 3117232809Sjmallett 3118232809Sjmallett /* Exhaust */ 3119232809Sjmallett if (remainder_size < MINSIZE) { 3120232809Sjmallett set_inuse_bit_at_offset(victim, size); 3121232809Sjmallett set_arena_for_chunk(victim, av); 3122232809Sjmallett check_malloced_chunk(av, victim, nb); 3123232809Sjmallett return chunk2mem(victim); 3124232809Sjmallett } 3125232809Sjmallett /* Split */ 3126232809Sjmallett else { 3127232809Sjmallett remainder = chunk_at_offset(victim, nb); 3128232809Sjmallett unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder; 3129232809Sjmallett remainder->bk = remainder->fd = unsorted_chunks(av); 3130232809Sjmallett set_head(victim, nb | PREV_INUSE); 3131232809Sjmallett set_head(remainder, remainder_size | PREV_INUSE); 3132232809Sjmallett set_foot(remainder, remainder_size); 3133232809Sjmallett set_arena_for_chunk(victim, av); 3134232809Sjmallett check_malloced_chunk(av, victim, nb); 3135232809Sjmallett return chunk2mem(victim); 3136232809Sjmallett } 3137232809Sjmallett } 3138232809Sjmallett } 3139232809Sjmallett } 3140232809Sjmallett 3141232809Sjmallett /* 3142232809Sjmallett Search for a chunk by scanning bins, starting with next largest 3143232809Sjmallett bin. This search is strictly by best-fit; i.e., the smallest 3144232809Sjmallett (with ties going to approximately the least recently used) chunk 3145232809Sjmallett that fits is selected. 3146232809Sjmallett 3147232809Sjmallett The bitmap avoids needing to check that most blocks are nonempty. 3148232809Sjmallett The particular case of skipping all bins during warm-up phases 3149232809Sjmallett when no chunks have been returned yet is faster than it might look. 3150232809Sjmallett */ 3151232809Sjmallett 3152232809Sjmallett ++idx; 3153232809Sjmallett bin = bin_at(av,idx); 3154232809Sjmallett block = idx2block(idx); 3155232809Sjmallett map = av->binmap[block]; 3156232809Sjmallett bit = idx2bit(idx); 3157232809Sjmallett 3158232809Sjmallett for (;;) { 3159232809Sjmallett 3160232809Sjmallett /* Skip rest of block if there are no more set bits in this block. */ 3161232809Sjmallett if (bit > map || bit == 0) { 3162232809Sjmallett do { 3163232809Sjmallett if (++block >= BINMAPSIZE) /* out of bins */ 3164232809Sjmallett goto use_top; 3165232809Sjmallett } while ( (map = av->binmap[block]) == 0); 3166232809Sjmallett 3167232809Sjmallett bin = bin_at(av, (block << BINMAPSHIFT)); 3168232809Sjmallett bit = 1; 3169232809Sjmallett } 3170232809Sjmallett 3171232809Sjmallett /* Advance to bin with set bit. There must be one. */ 3172232809Sjmallett while ((bit & map) == 0) { 3173232809Sjmallett bin = next_bin(bin); 3174232809Sjmallett bit <<= 1; 3175232809Sjmallett assert(bit != 0); 3176232809Sjmallett } 3177232809Sjmallett 3178232809Sjmallett /* Inspect the bin. It is likely to be non-empty */ 3179232809Sjmallett victim = last(bin); 3180232809Sjmallett 3181232809Sjmallett /* If a false alarm (empty bin), clear the bit. */ 3182232809Sjmallett if (victim == bin) { 3183232809Sjmallett av->binmap[block] = map &= ~bit; /* Write through */ 3184232809Sjmallett bin = next_bin(bin); 3185232809Sjmallett bit <<= 1; 3186232809Sjmallett } 3187232809Sjmallett 3188232809Sjmallett else { 3189232809Sjmallett size = chunksize(victim); 3190232809Sjmallett 3191232809Sjmallett /* We know the first chunk in this bin is big enough to use. */ 3192232809Sjmallett assert((unsigned long)(size) >= (unsigned long)(nb)); 3193232809Sjmallett 3194232809Sjmallett remainder_size = size - nb; 3195232809Sjmallett 3196232809Sjmallett /* unlink */ 3197232809Sjmallett bck = victim->bk; 3198232809Sjmallett bin->bk = bck; 3199232809Sjmallett bck->fd = bin; 3200232809Sjmallett 3201232809Sjmallett /* Exhaust */ 3202232809Sjmallett if (remainder_size < MINSIZE) { 3203232809Sjmallett set_inuse_bit_at_offset(victim, size); 3204232809Sjmallett set_arena_for_chunk(victim, av); 3205232809Sjmallett check_malloced_chunk(av, victim, nb); 3206232809Sjmallett return chunk2mem(victim); 3207232809Sjmallett } 3208232809Sjmallett 3209232809Sjmallett /* Split */ 3210232809Sjmallett else { 3211232809Sjmallett remainder = chunk_at_offset(victim, nb); 3212232809Sjmallett 3213232809Sjmallett unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder; 3214232809Sjmallett remainder->bk = remainder->fd = unsorted_chunks(av); 3215232809Sjmallett /* advertise as last remainder */ 3216232809Sjmallett if (in_smallbin_range(nb)) 3217232809Sjmallett av->last_remainder = remainder; 3218232809Sjmallett 3219232809Sjmallett set_head(victim, nb | PREV_INUSE); 3220232809Sjmallett set_head(remainder, remainder_size | PREV_INUSE); 3221232809Sjmallett set_foot(remainder, remainder_size); 3222232809Sjmallett set_arena_for_chunk(victim, av); 3223232809Sjmallett check_malloced_chunk(av, victim, nb); 3224232809Sjmallett return chunk2mem(victim); 3225232809Sjmallett } 3226232809Sjmallett } 3227232809Sjmallett } 3228232809Sjmallett 3229232809Sjmallett use_top: 3230232809Sjmallett /* 3231232809Sjmallett If large enough, split off the chunk bordering the end of memory 3232232809Sjmallett (held in av->top). Note that this is in accord with the best-fit 3233232809Sjmallett search rule. In effect, av->top is treated as larger (and thus 3234232809Sjmallett less well fitting) than any other available chunk since it can 3235232809Sjmallett be extended to be as large as necessary (up to system 3236232809Sjmallett limitations). 3237232809Sjmallett 3238232809Sjmallett We require that av->top always exists (i.e., has size >= 3239232809Sjmallett MINSIZE) after initialization, so if it would otherwise be 3240232809Sjmallett exhuasted by current request, it is replenished. (The main 3241232809Sjmallett reason for ensuring it exists is that we may need MINSIZE space 3242232809Sjmallett to put in fenceposts in sysmalloc.) 3243232809Sjmallett */ 3244232809Sjmallett 3245232809Sjmallett victim = av->top; 3246232809Sjmallett size = chunksize(victim); 3247232809Sjmallett 3248232809Sjmallett if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) { 3249232809Sjmallett remainder_size = size - nb; 3250232809Sjmallett remainder = chunk_at_offset(victim, nb); 3251232809Sjmallett av->top = remainder; 3252232809Sjmallett set_head(victim, nb | PREV_INUSE); 3253232809Sjmallett set_head(remainder, remainder_size | PREV_INUSE); 3254232809Sjmallett 3255232809Sjmallett set_arena_for_chunk(victim, av); 3256232809Sjmallett check_malloced_chunk(av, victim, nb); 3257232809Sjmallett return chunk2mem(victim); 3258232809Sjmallett } 3259232809Sjmallett 3260232809Sjmallett /* 3261232809Sjmallett If there is space available in fastbins, consolidate and retry, 3262232809Sjmallett to possibly avoid expanding memory. This can occur only if nb is 3263232809Sjmallett in smallbin range so we didn't consolidate upon entry. 3264232809Sjmallett */ 3265232809Sjmallett 3266232809Sjmallett else if (have_fastchunks(av)) { 3267232809Sjmallett assert(in_smallbin_range(nb)); 3268232809Sjmallett malloc_consolidate(av); 3269232809Sjmallett idx = smallbin_index(nb); /* restore original bin index */ 3270232809Sjmallett } 3271232809Sjmallett 3272232809Sjmallett /* 3273232809Sjmallett Otherwise, relay to handle system-dependent cases 3274232809Sjmallett */ 3275232809Sjmallett else 3276232809Sjmallett return(NULL); // sysmalloc not supported 3277232809Sjmallett } 3278232809Sjmallett} 3279232809Sjmallett 3280232809Sjmallett/* 3281232809Sjmallett ------------------------------ free ------------------------------ 3282232809Sjmallett*/ 3283232809Sjmallett 3284232809Sjmallettstatic void 3285232809Sjmallett_int_free(mstate av, Void_t* mem) 3286232809Sjmallett{ 3287232809Sjmallett mchunkptr p; /* chunk corresponding to mem */ 3288232809Sjmallett INTERNAL_SIZE_T size; /* its size */ 3289232809Sjmallett mfastbinptr* fb; /* associated fastbin */ 3290232809Sjmallett mchunkptr nextchunk; /* next contiguous chunk */ 3291232809Sjmallett INTERNAL_SIZE_T nextsize; /* its size */ 3292232809Sjmallett int nextinuse; /* true if nextchunk is used */ 3293232809Sjmallett INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */ 3294232809Sjmallett mchunkptr bck; /* misc temp for linking */ 3295232809Sjmallett mchunkptr fwd; /* misc temp for linking */ 3296232809Sjmallett 3297232809Sjmallett 3298232809Sjmallett /* free(0) has no effect */ 3299232809Sjmallett if (mem != 0) { 3300232809Sjmallett p = mem2chunk(mem); 3301232809Sjmallett size = chunksize(p); 3302232809Sjmallett 3303232809Sjmallett check_inuse_chunk(av, p); 3304232809Sjmallett 3305232809Sjmallett /* 3306232809Sjmallett If eligible, place chunk on a fastbin so it can be found 3307232809Sjmallett and used quickly in malloc. 3308232809Sjmallett */ 3309232809Sjmallett 3310232809Sjmallett if ((unsigned long)(size) <= (unsigned long)(av->max_fast) 3311232809Sjmallett 3312232809Sjmallett#if TRIM_FASTBINS 3313232809Sjmallett /* 3314232809Sjmallett If TRIM_FASTBINS set, don't place chunks 3315232809Sjmallett bordering top into fastbins 3316232809Sjmallett */ 3317232809Sjmallett && (chunk_at_offset(p, size) != av->top) 3318232809Sjmallett#endif 3319232809Sjmallett ) { 3320232809Sjmallett 3321232809Sjmallett set_fastchunks(av); 3322232809Sjmallett fb = &(av->fastbins[fastbin_index(size)]); 3323232809Sjmallett p->fd = *fb; 3324232809Sjmallett *fb = p; 3325232809Sjmallett } 3326232809Sjmallett 3327232809Sjmallett /* 3328232809Sjmallett Consolidate other non-mmapped chunks as they arrive. 3329232809Sjmallett */ 3330232809Sjmallett 3331232809Sjmallett else if (!chunk_is_mmapped(p)) { 3332232809Sjmallett nextchunk = chunk_at_offset(p, size); 3333232809Sjmallett nextsize = chunksize(nextchunk); 3334232809Sjmallett assert(nextsize > 0); 3335232809Sjmallett 3336232809Sjmallett /* consolidate backward */ 3337232809Sjmallett if (!prev_inuse(p)) { 3338232809Sjmallett prevsize = p->prev_size; 3339232809Sjmallett size += prevsize; 3340232809Sjmallett p = chunk_at_offset(p, -((long) prevsize)); 3341232809Sjmallett unlink(p, bck, fwd); 3342232809Sjmallett } 3343232809Sjmallett 3344232809Sjmallett if (nextchunk != av->top) { 3345232809Sjmallett /* get and clear inuse bit */ 3346232809Sjmallett nextinuse = inuse_bit_at_offset(nextchunk, nextsize); 3347232809Sjmallett 3348232809Sjmallett /* consolidate forward */ 3349232809Sjmallett if (!nextinuse) { 3350232809Sjmallett unlink(nextchunk, bck, fwd); 3351232809Sjmallett size += nextsize; 3352232809Sjmallett } else 3353232809Sjmallett clear_inuse_bit_at_offset(nextchunk, 0); 3354232809Sjmallett 3355232809Sjmallett /* 3356232809Sjmallett Place the chunk in unsorted chunk list. Chunks are 3357232809Sjmallett not placed into regular bins until after they have 3358232809Sjmallett been given one chance to be used in malloc. 3359232809Sjmallett */ 3360232809Sjmallett 3361232809Sjmallett bck = unsorted_chunks(av); 3362232809Sjmallett fwd = bck->fd; 3363232809Sjmallett p->bk = bck; 3364232809Sjmallett p->fd = fwd; 3365232809Sjmallett bck->fd = p; 3366232809Sjmallett fwd->bk = p; 3367232809Sjmallett 3368232809Sjmallett set_head(p, size | PREV_INUSE); 3369232809Sjmallett set_foot(p, size); 3370232809Sjmallett 3371232809Sjmallett check_free_chunk(av, p); 3372232809Sjmallett } 3373232809Sjmallett 3374232809Sjmallett /* 3375232809Sjmallett If the chunk borders the current high end of memory, 3376232809Sjmallett consolidate into top 3377232809Sjmallett */ 3378232809Sjmallett 3379232809Sjmallett else { 3380232809Sjmallett size += nextsize; 3381232809Sjmallett set_head(p, size | PREV_INUSE); 3382232809Sjmallett av->top = p; 3383232809Sjmallett check_chunk(av, p); 3384232809Sjmallett } 3385232809Sjmallett 3386232809Sjmallett /* 3387232809Sjmallett If freeing a large space, consolidate possibly-surrounding 3388232809Sjmallett chunks. Then, if the total unused topmost memory exceeds trim 3389232809Sjmallett threshold, ask malloc_trim to reduce top. 3390232809Sjmallett 3391232809Sjmallett Unless max_fast is 0, we don't know if there are fastbins 3392232809Sjmallett bordering top, so we cannot tell for sure whether threshold 3393232809Sjmallett has been reached unless fastbins are consolidated. But we 3394232809Sjmallett don't want to consolidate on each free. As a compromise, 3395232809Sjmallett consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD 3396232809Sjmallett is reached. 3397232809Sjmallett */ 3398232809Sjmallett 3399232809Sjmallett if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) { 3400232809Sjmallett if (have_fastchunks(av)) 3401232809Sjmallett malloc_consolidate(av); 3402232809Sjmallett } 3403232809Sjmallett } 3404232809Sjmallett } 3405232809Sjmallett} 3406232809Sjmallett 3407232809Sjmallett/* 3408232809Sjmallett ------------------------- malloc_consolidate ------------------------- 3409232809Sjmallett 3410232809Sjmallett malloc_consolidate is a specialized version of free() that tears 3411232809Sjmallett down chunks held in fastbins. Free itself cannot be used for this 3412232809Sjmallett purpose since, among other things, it might place chunks back onto 3413232809Sjmallett fastbins. So, instead, we need to use a minor variant of the same 3414232809Sjmallett code. 3415232809Sjmallett 3416232809Sjmallett Also, because this routine needs to be called the first time through 3417232809Sjmallett malloc anyway, it turns out to be the perfect place to trigger 3418232809Sjmallett initialization code. 3419232809Sjmallett*/ 3420232809Sjmallett 3421232809Sjmallett#if __STD_C 3422232809Sjmallettstatic void malloc_consolidate(mstate av) 3423232809Sjmallett#else 3424232809Sjmallettstatic void malloc_consolidate(av) mstate av; 3425232809Sjmallett#endif 3426232809Sjmallett{ 3427232809Sjmallett mfastbinptr* fb; /* current fastbin being consolidated */ 3428232809Sjmallett mfastbinptr* maxfb; /* last fastbin (for loop control) */ 3429232809Sjmallett mchunkptr p; /* current chunk being consolidated */ 3430232809Sjmallett mchunkptr nextp; /* next chunk to consolidate */ 3431232809Sjmallett mchunkptr unsorted_bin; /* bin header */ 3432232809Sjmallett mchunkptr first_unsorted; /* chunk to link to */ 3433232809Sjmallett 3434232809Sjmallett /* These have same use as in free() */ 3435232809Sjmallett mchunkptr nextchunk; 3436232809Sjmallett INTERNAL_SIZE_T size; 3437232809Sjmallett INTERNAL_SIZE_T nextsize; 3438232809Sjmallett INTERNAL_SIZE_T prevsize; 3439232809Sjmallett int nextinuse; 3440232809Sjmallett mchunkptr bck; 3441232809Sjmallett mchunkptr fwd; 3442232809Sjmallett 3443232809Sjmallett /* 3444232809Sjmallett If max_fast is 0, we know that av hasn't 3445232809Sjmallett yet been initialized, in which case do so below 3446232809Sjmallett */ 3447232809Sjmallett 3448232809Sjmallett if (av->max_fast != 0) { 3449232809Sjmallett clear_fastchunks(av); 3450232809Sjmallett 3451232809Sjmallett unsorted_bin = unsorted_chunks(av); 3452232809Sjmallett 3453232809Sjmallett /* 3454232809Sjmallett Remove each chunk from fast bin and consolidate it, placing it 3455232809Sjmallett then in unsorted bin. Among other reasons for doing this, 3456232809Sjmallett placing in unsorted bin avoids needing to calculate actual bins 3457232809Sjmallett until malloc is sure that chunks aren't immediately going to be 3458232809Sjmallett reused anyway. 3459232809Sjmallett */ 3460232809Sjmallett 3461232809Sjmallett maxfb = &(av->fastbins[fastbin_index(av->max_fast)]); 3462232809Sjmallett fb = &(av->fastbins[0]); 3463232809Sjmallett do { 3464232809Sjmallett if ( (p = *fb) != 0) { 3465232809Sjmallett *fb = 0; 3466232809Sjmallett 3467232809Sjmallett do { 3468232809Sjmallett check_inuse_chunk(av, p); 3469232809Sjmallett nextp = p->fd; 3470232809Sjmallett 3471232809Sjmallett /* Slightly streamlined version of consolidation code in free() */ 3472232809Sjmallett size = p->size & ~(PREV_INUSE); 3473232809Sjmallett nextchunk = chunk_at_offset(p, size); 3474232809Sjmallett nextsize = chunksize(nextchunk); 3475232809Sjmallett 3476232809Sjmallett if (!prev_inuse(p)) { 3477232809Sjmallett prevsize = p->prev_size; 3478232809Sjmallett size += prevsize; 3479232809Sjmallett p = chunk_at_offset(p, -((long) prevsize)); 3480232809Sjmallett unlink(p, bck, fwd); 3481232809Sjmallett } 3482232809Sjmallett 3483232809Sjmallett if (nextchunk != av->top) { 3484232809Sjmallett nextinuse = inuse_bit_at_offset(nextchunk, nextsize); 3485232809Sjmallett 3486232809Sjmallett if (!nextinuse) { 3487232809Sjmallett size += nextsize; 3488232809Sjmallett unlink(nextchunk, bck, fwd); 3489232809Sjmallett } else 3490232809Sjmallett clear_inuse_bit_at_offset(nextchunk, 0); 3491232809Sjmallett 3492232809Sjmallett first_unsorted = unsorted_bin->fd; 3493232809Sjmallett unsorted_bin->fd = p; 3494232809Sjmallett first_unsorted->bk = p; 3495232809Sjmallett 3496232809Sjmallett set_head(p, size | PREV_INUSE); 3497232809Sjmallett p->bk = unsorted_bin; 3498232809Sjmallett p->fd = first_unsorted; 3499232809Sjmallett set_foot(p, size); 3500232809Sjmallett } 3501232809Sjmallett 3502232809Sjmallett else { 3503232809Sjmallett size += nextsize; 3504232809Sjmallett set_head(p, size | PREV_INUSE); 3505232809Sjmallett av->top = p; 3506232809Sjmallett } 3507232809Sjmallett 3508232809Sjmallett } while ( (p = nextp) != 0); 3509232809Sjmallett 3510232809Sjmallett } 3511232809Sjmallett } while (fb++ != maxfb); 3512232809Sjmallett } 3513232809Sjmallett else { 3514232809Sjmallett malloc_init_state(av); 3515232809Sjmallett check_malloc_state(av); 3516232809Sjmallett } 3517232809Sjmallett} 3518232809Sjmallett 3519232809Sjmallett/* 3520232809Sjmallett ------------------------------ realloc ------------------------------ 3521232809Sjmallett*/ 3522232809Sjmallett 3523232809Sjmallettstatic Void_t* 3524232809Sjmallett_int_realloc(mstate av, Void_t* oldmem, size_t bytes) 3525232809Sjmallett{ 3526232809Sjmallett INTERNAL_SIZE_T nb; /* padded request size */ 3527232809Sjmallett 3528232809Sjmallett mchunkptr oldp; /* chunk corresponding to oldmem */ 3529232809Sjmallett INTERNAL_SIZE_T oldsize; /* its size */ 3530232809Sjmallett 3531232809Sjmallett mchunkptr newp; /* chunk to return */ 3532232809Sjmallett INTERNAL_SIZE_T newsize; /* its size */ 3533232809Sjmallett Void_t* newmem; /* corresponding user mem */ 3534232809Sjmallett 3535232809Sjmallett mchunkptr next; /* next contiguous chunk after oldp */ 3536232809Sjmallett 3537232809Sjmallett mchunkptr remainder; /* extra space at end of newp */ 3538232809Sjmallett unsigned long remainder_size; /* its size */ 3539232809Sjmallett 3540232809Sjmallett mchunkptr bck; /* misc temp for linking */ 3541232809Sjmallett mchunkptr fwd; /* misc temp for linking */ 3542232809Sjmallett 3543232809Sjmallett unsigned long copysize; /* bytes to copy */ 3544232809Sjmallett unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */ 3545232809Sjmallett INTERNAL_SIZE_T* s; /* copy source */ 3546232809Sjmallett INTERNAL_SIZE_T* d; /* copy destination */ 3547232809Sjmallett 3548232809Sjmallett 3549232809Sjmallett#if REALLOC_ZERO_BYTES_FREES 3550232809Sjmallett if (bytes == 0) { 3551232809Sjmallett _int_free(av, oldmem); 3552232809Sjmallett return 0; 3553232809Sjmallett } 3554232809Sjmallett#endif 3555232809Sjmallett 3556232809Sjmallett /* realloc of null is supposed to be same as malloc */ 3557232809Sjmallett if (oldmem == 0) return _int_malloc(av, bytes); 3558232809Sjmallett 3559232809Sjmallett checked_request2size(bytes, nb); 3560232809Sjmallett 3561232809Sjmallett oldp = mem2chunk(oldmem); 3562232809Sjmallett oldsize = chunksize(oldp); 3563232809Sjmallett 3564232809Sjmallett check_inuse_chunk(av, oldp); 3565232809Sjmallett 3566232809Sjmallett // force to act like not mmapped 3567232809Sjmallett if (1) { 3568232809Sjmallett 3569232809Sjmallett if ((unsigned long)(oldsize) >= (unsigned long)(nb)) { 3570232809Sjmallett /* already big enough; split below */ 3571232809Sjmallett newp = oldp; 3572232809Sjmallett newsize = oldsize; 3573232809Sjmallett } 3574232809Sjmallett 3575232809Sjmallett else { 3576232809Sjmallett next = chunk_at_offset(oldp, oldsize); 3577232809Sjmallett 3578232809Sjmallett /* Try to expand forward into top */ 3579232809Sjmallett if (next == av->top && 3580232809Sjmallett (unsigned long)(newsize = oldsize + chunksize(next)) >= 3581232809Sjmallett (unsigned long)(nb + MINSIZE)) { 3582232809Sjmallett set_head_size(oldp, nb ); 3583232809Sjmallett av->top = chunk_at_offset(oldp, nb); 3584232809Sjmallett set_head(av->top, (newsize - nb) | PREV_INUSE); 3585232809Sjmallett check_inuse_chunk(av, oldp); 3586232809Sjmallett set_arena_for_chunk(oldp, av); 3587232809Sjmallett return chunk2mem(oldp); 3588232809Sjmallett } 3589232809Sjmallett 3590232809Sjmallett /* Try to expand forward into next chunk; split off remainder below */ 3591232809Sjmallett else if (next != av->top && 3592232809Sjmallett !inuse(next) && 3593232809Sjmallett (unsigned long)(newsize = oldsize + chunksize(next)) >= 3594232809Sjmallett (unsigned long)(nb)) { 3595232809Sjmallett newp = oldp; 3596232809Sjmallett unlink(next, bck, fwd); 3597232809Sjmallett } 3598232809Sjmallett 3599232809Sjmallett /* allocate, copy, free */ 3600232809Sjmallett else { 3601232809Sjmallett newmem = _int_malloc(av, nb - MALLOC_ALIGN_MASK); 3602232809Sjmallett if (newmem == 0) 3603232809Sjmallett return 0; /* propagate failure */ 3604232809Sjmallett 3605232809Sjmallett newp = mem2chunk(newmem); 3606232809Sjmallett newsize = chunksize(newp); 3607232809Sjmallett 3608232809Sjmallett /* 3609232809Sjmallett Avoid copy if newp is next chunk after oldp. 3610232809Sjmallett */ 3611232809Sjmallett if (newp == next) { 3612232809Sjmallett newsize += oldsize; 3613232809Sjmallett newp = oldp; 3614232809Sjmallett } 3615232809Sjmallett else { 3616232809Sjmallett /* 3617232809Sjmallett Unroll copy of <= 36 bytes (72 if 8byte sizes) 3618232809Sjmallett We know that contents have an odd number of 3619232809Sjmallett INTERNAL_SIZE_T-sized words; minimally 3. 3620232809Sjmallett */ 3621232809Sjmallett 3622232809Sjmallett copysize = oldsize - SIZE_SZ; 3623232809Sjmallett s = (INTERNAL_SIZE_T*)(oldmem); 3624232809Sjmallett d = (INTERNAL_SIZE_T*)(newmem); 3625232809Sjmallett ncopies = copysize / sizeof(INTERNAL_SIZE_T); 3626232809Sjmallett assert(ncopies >= 3); 3627232809Sjmallett 3628232809Sjmallett if (ncopies > 9) 3629232809Sjmallett MALLOC_COPY(d, s, copysize); 3630232809Sjmallett 3631232809Sjmallett else { 3632232809Sjmallett *(d+0) = *(s+0); 3633232809Sjmallett *(d+1) = *(s+1); 3634232809Sjmallett *(d+2) = *(s+2); 3635232809Sjmallett if (ncopies > 4) { 3636232809Sjmallett *(d+3) = *(s+3); 3637232809Sjmallett *(d+4) = *(s+4); 3638232809Sjmallett if (ncopies > 6) { 3639232809Sjmallett *(d+5) = *(s+5); 3640232809Sjmallett *(d+6) = *(s+6); 3641232809Sjmallett if (ncopies > 8) { 3642232809Sjmallett *(d+7) = *(s+7); 3643232809Sjmallett *(d+8) = *(s+8); 3644232809Sjmallett } 3645232809Sjmallett } 3646232809Sjmallett } 3647232809Sjmallett } 3648232809Sjmallett 3649232809Sjmallett _int_free(av, oldmem); 3650232809Sjmallett set_arena_for_chunk(newp, av); 3651232809Sjmallett check_inuse_chunk(av, newp); 3652232809Sjmallett return chunk2mem(newp); 3653232809Sjmallett } 3654232809Sjmallett } 3655232809Sjmallett } 3656232809Sjmallett 3657232809Sjmallett /* If possible, free extra space in old or extended chunk */ 3658232809Sjmallett 3659232809Sjmallett assert((unsigned long)(newsize) >= (unsigned long)(nb)); 3660232809Sjmallett 3661232809Sjmallett remainder_size = newsize - nb; 3662232809Sjmallett 3663232809Sjmallett if (remainder_size < MINSIZE) { /* not enough extra to split off */ 3664232809Sjmallett set_head_size(newp, newsize); 3665232809Sjmallett set_inuse_bit_at_offset(newp, newsize); 3666232809Sjmallett } 3667232809Sjmallett else { /* split remainder */ 3668232809Sjmallett remainder = chunk_at_offset(newp, nb); 3669232809Sjmallett set_head_size(newp, nb ); 3670232809Sjmallett set_head(remainder, remainder_size | PREV_INUSE ); 3671232809Sjmallett /* Mark remainder as inuse so free() won't complain */ 3672232809Sjmallett set_inuse_bit_at_offset(remainder, remainder_size); 3673232809Sjmallett set_arena_for_chunk(remainder, av); 3674232809Sjmallett _int_free(av, chunk2mem(remainder)); 3675232809Sjmallett } 3676232809Sjmallett 3677232809Sjmallett set_arena_for_chunk(newp, av); 3678232809Sjmallett check_inuse_chunk(av, newp); 3679232809Sjmallett return chunk2mem(newp); 3680232809Sjmallett } 3681232809Sjmallett 3682232809Sjmallett /* 3683232809Sjmallett Handle mmap cases 3684232809Sjmallett */ 3685232809Sjmallett 3686232809Sjmallett else { 3687232809Sjmallett /* If !HAVE_MMAP, but chunk_is_mmapped, user must have overwritten mem */ 3688232809Sjmallett check_malloc_state(av); 3689232809Sjmallett MALLOC_FAILURE_ACTION; 3690232809Sjmallett return 0; 3691232809Sjmallett } 3692232809Sjmallett} 3693232809Sjmallett 3694232809Sjmallett/* 3695232809Sjmallett ------------------------------ memalign ------------------------------ 3696232809Sjmallett*/ 3697232809Sjmallett 3698232809Sjmallettstatic Void_t* 3699232809Sjmallett_int_memalign(mstate av, size_t alignment, size_t bytes) 3700232809Sjmallett{ 3701232809Sjmallett INTERNAL_SIZE_T nb; /* padded request size */ 3702232809Sjmallett char* m; /* memory returned by malloc call */ 3703232809Sjmallett mchunkptr p; /* corresponding chunk */ 3704232809Sjmallett char* brk; /* alignment point within p */ 3705232809Sjmallett mchunkptr newp; /* chunk to return */ 3706232809Sjmallett INTERNAL_SIZE_T newsize; /* its size */ 3707232809Sjmallett INTERNAL_SIZE_T leadsize; /* leading space before alignment point */ 3708232809Sjmallett mchunkptr remainder; /* spare room at end to split off */ 3709232809Sjmallett unsigned long remainder_size; /* its size */ 3710232809Sjmallett INTERNAL_SIZE_T size; 3711232809Sjmallett 3712232809Sjmallett /* If need less alignment than we give anyway, just relay to malloc */ 3713232809Sjmallett 3714232809Sjmallett if (alignment <= MALLOC_ALIGNMENT) return _int_malloc(av, bytes); 3715232809Sjmallett 3716232809Sjmallett /* Otherwise, ensure that it is at least a minimum chunk size */ 3717232809Sjmallett 3718232809Sjmallett if (alignment < MINSIZE) alignment = MINSIZE; 3719232809Sjmallett 3720232809Sjmallett /* Make sure alignment is power of 2 (in case MINSIZE is not). */ 3721232809Sjmallett if ((alignment & (alignment - 1)) != 0) { 3722232809Sjmallett size_t a = MALLOC_ALIGNMENT * 2; 3723232809Sjmallett while ((unsigned long)a < (unsigned long)alignment) a <<= 1; 3724232809Sjmallett alignment = a; 3725232809Sjmallett } 3726232809Sjmallett 3727232809Sjmallett checked_request2size(bytes, nb); 3728232809Sjmallett 3729232809Sjmallett /* 3730232809Sjmallett Strategy: find a spot within that chunk that meets the alignment 3731232809Sjmallett request, and then possibly free the leading and trailing space. 3732232809Sjmallett */ 3733232809Sjmallett 3734232809Sjmallett 3735232809Sjmallett /* Call malloc with worst case padding to hit alignment. */ 3736232809Sjmallett 3737232809Sjmallett m = (char*)(_int_malloc(av, nb + alignment + MINSIZE)); 3738232809Sjmallett 3739232809Sjmallett if (m == 0) return 0; /* propagate failure */ 3740232809Sjmallett 3741232809Sjmallett p = mem2chunk(m); 3742232809Sjmallett 3743232809Sjmallett if ((((unsigned long)(m)) % alignment) != 0) { /* misaligned */ 3744232809Sjmallett 3745232809Sjmallett /* 3746232809Sjmallett Find an aligned spot inside chunk. Since we need to give back 3747232809Sjmallett leading space in a chunk of at least MINSIZE, if the first 3748232809Sjmallett calculation places us at a spot with less than MINSIZE leader, 3749232809Sjmallett we can move to the next aligned spot -- we've allocated enough 3750232809Sjmallett total room so that this is always possible. 3751232809Sjmallett */ 3752232809Sjmallett 3753232809Sjmallett brk = (char*)mem2chunk(((unsigned long)(m + alignment - 1)) & 3754232809Sjmallett -((signed long) alignment)); 3755232809Sjmallett if ((unsigned long)(brk - (char*)(p)) < MINSIZE) 3756232809Sjmallett brk += alignment; 3757232809Sjmallett 3758232809Sjmallett newp = (mchunkptr)brk; 3759232809Sjmallett leadsize = brk - (char*)(p); 3760232809Sjmallett newsize = chunksize(p) - leadsize; 3761232809Sjmallett 3762232809Sjmallett /* For mmapped chunks, just adjust offset */ 3763232809Sjmallett if (chunk_is_mmapped(p)) { 3764232809Sjmallett newp->prev_size = p->prev_size + leadsize; 3765232809Sjmallett set_head(newp, newsize|IS_MMAPPED); 3766232809Sjmallett set_arena_for_chunk(newp, av); 3767232809Sjmallett return chunk2mem(newp); 3768232809Sjmallett } 3769232809Sjmallett 3770232809Sjmallett /* Otherwise, give back leader, use the rest */ 3771232809Sjmallett set_head(newp, newsize | PREV_INUSE ); 3772232809Sjmallett set_inuse_bit_at_offset(newp, newsize); 3773232809Sjmallett set_head_size(p, leadsize); 3774232809Sjmallett set_arena_for_chunk(p, av); 3775232809Sjmallett _int_free(av, chunk2mem(p)); 3776232809Sjmallett p = newp; 3777232809Sjmallett 3778232809Sjmallett assert (newsize >= nb && 3779232809Sjmallett (((unsigned long)(chunk2mem(p))) % alignment) == 0); 3780232809Sjmallett } 3781232809Sjmallett 3782232809Sjmallett /* Also give back spare room at the end */ 3783232809Sjmallett if (!chunk_is_mmapped(p)) { 3784232809Sjmallett size = chunksize(p); 3785232809Sjmallett if ((unsigned long)(size) > (unsigned long)(nb + MINSIZE)) { 3786232809Sjmallett remainder_size = size - nb; 3787232809Sjmallett remainder = chunk_at_offset(p, nb); 3788232809Sjmallett set_head(remainder, remainder_size | PREV_INUSE ); 3789232809Sjmallett set_head_size(p, nb); 3790232809Sjmallett set_arena_for_chunk(remainder, av); 3791232809Sjmallett _int_free(av, chunk2mem(remainder)); 3792232809Sjmallett } 3793232809Sjmallett } 3794232809Sjmallett 3795232809Sjmallett set_arena_for_chunk(p, av); 3796232809Sjmallett check_inuse_chunk(av, p); 3797232809Sjmallett return chunk2mem(p); 3798232809Sjmallett} 3799232809Sjmallett 3800232809Sjmallett#if 1 3801232809Sjmallett/* 3802232809Sjmallett ------------------------------ calloc ------------------------------ 3803232809Sjmallett*/ 3804232809Sjmallett 3805232809Sjmallett#if __STD_C 3806232809SjmallettVoid_t* cALLOc(cvmx_arena_list_t arena_list, size_t n_elements, size_t elem_size) 3807232809Sjmallett#else 3808232809SjmallettVoid_t* cALLOc(n_elements, elem_size) size_t n_elements; size_t elem_size; 3809232809Sjmallett#endif 3810232809Sjmallett{ 3811232809Sjmallett mchunkptr p; 3812232809Sjmallett unsigned long clearsize; 3813232809Sjmallett unsigned long nclears; 3814232809Sjmallett INTERNAL_SIZE_T* d; 3815232809Sjmallett 3816232809Sjmallett Void_t* mem = public_mALLOc(arena_list, n_elements * elem_size); 3817232809Sjmallett 3818232809Sjmallett if (mem != 0) { 3819232809Sjmallett p = mem2chunk(mem); 3820232809Sjmallett 3821232809Sjmallett { 3822232809Sjmallett /* 3823232809Sjmallett Unroll clear of <= 36 bytes (72 if 8byte sizes) 3824232809Sjmallett We know that contents have an odd number of 3825232809Sjmallett INTERNAL_SIZE_T-sized words; minimally 3. 3826232809Sjmallett */ 3827232809Sjmallett 3828232809Sjmallett d = (INTERNAL_SIZE_T*)mem; 3829232809Sjmallett clearsize = chunksize(p) - SIZE_SZ; 3830232809Sjmallett nclears = clearsize / sizeof(INTERNAL_SIZE_T); 3831232809Sjmallett assert(nclears >= 3); 3832232809Sjmallett 3833232809Sjmallett if (nclears > 9) 3834232809Sjmallett MALLOC_ZERO(d, clearsize); 3835232809Sjmallett 3836232809Sjmallett else { 3837232809Sjmallett *(d+0) = 0; 3838232809Sjmallett *(d+1) = 0; 3839232809Sjmallett *(d+2) = 0; 3840232809Sjmallett if (nclears > 4) { 3841232809Sjmallett *(d+3) = 0; 3842232809Sjmallett *(d+4) = 0; 3843232809Sjmallett if (nclears > 6) { 3844232809Sjmallett *(d+5) = 0; 3845232809Sjmallett *(d+6) = 0; 3846232809Sjmallett if (nclears > 8) { 3847232809Sjmallett *(d+7) = 0; 3848232809Sjmallett *(d+8) = 0; 3849232809Sjmallett } 3850232809Sjmallett } 3851232809Sjmallett } 3852232809Sjmallett } 3853232809Sjmallett } 3854232809Sjmallett } 3855232809Sjmallett return mem; 3856232809Sjmallett} 3857232809Sjmallett#endif 3858232809Sjmallett 3859232809Sjmallett 3860232809Sjmallett/* 3861232809Sjmallett ------------------------- malloc_usable_size ------------------------- 3862232809Sjmallett*/ 3863232809Sjmallett 3864232809Sjmallett#if __STD_C 3865232809Sjmallettsize_t mUSABLe(Void_t* mem) 3866232809Sjmallett#else 3867232809Sjmallettsize_t mUSABLe(mem) Void_t* mem; 3868232809Sjmallett#endif 3869232809Sjmallett{ 3870232809Sjmallett mchunkptr p; 3871232809Sjmallett if (mem != 0) { 3872232809Sjmallett p = mem2chunk(mem); 3873232809Sjmallett if (chunk_is_mmapped(p)) 3874232809Sjmallett return chunksize(p) - 3*SIZE_SZ; /* updated size for adding arena_ptr */ 3875232809Sjmallett else if (inuse(p)) 3876232809Sjmallett return chunksize(p) - 2*SIZE_SZ; /* updated size for adding arena_ptr */ 3877232809Sjmallett } 3878232809Sjmallett return 0; 3879232809Sjmallett} 3880232809Sjmallett 3881232809Sjmallett/* 3882232809Sjmallett ------------------------------ mallinfo ------------------------------ 3883232809Sjmallett*/ 3884232809Sjmallett 3885232809Sjmallettstruct mallinfo mALLINFo(mstate av) 3886232809Sjmallett{ 3887232809Sjmallett struct mallinfo mi; 3888232809Sjmallett int i; 3889232809Sjmallett mbinptr b; 3890232809Sjmallett mchunkptr p; 3891232809Sjmallett INTERNAL_SIZE_T avail; 3892232809Sjmallett INTERNAL_SIZE_T fastavail; 3893232809Sjmallett int nblocks; 3894232809Sjmallett int nfastblocks; 3895232809Sjmallett 3896232809Sjmallett /* Ensure initialization */ 3897232809Sjmallett if (av->top == 0) malloc_consolidate(av); 3898232809Sjmallett 3899232809Sjmallett check_malloc_state(av); 3900232809Sjmallett 3901232809Sjmallett /* Account for top */ 3902232809Sjmallett avail = chunksize(av->top); 3903232809Sjmallett nblocks = 1; /* top always exists */ 3904232809Sjmallett 3905232809Sjmallett /* traverse fastbins */ 3906232809Sjmallett nfastblocks = 0; 3907232809Sjmallett fastavail = 0; 3908232809Sjmallett 3909232809Sjmallett for (i = 0; i < NFASTBINS; ++i) { 3910232809Sjmallett for (p = av->fastbins[i]; p != 0; p = p->fd) { 3911232809Sjmallett ++nfastblocks; 3912232809Sjmallett fastavail += chunksize(p); 3913232809Sjmallett } 3914232809Sjmallett } 3915232809Sjmallett 3916232809Sjmallett avail += fastavail; 3917232809Sjmallett 3918232809Sjmallett /* traverse regular bins */ 3919232809Sjmallett for (i = 1; i < NBINS; ++i) { 3920232809Sjmallett b = bin_at(av, i); 3921232809Sjmallett for (p = last(b); p != b; p = p->bk) { 3922232809Sjmallett ++nblocks; 3923232809Sjmallett avail += chunksize(p); 3924232809Sjmallett } 3925232809Sjmallett } 3926232809Sjmallett 3927232809Sjmallett mi.smblks = nfastblocks; 3928232809Sjmallett mi.ordblks = nblocks; 3929232809Sjmallett mi.fordblks = avail; 3930232809Sjmallett mi.uordblks = av->system_mem - avail; 3931232809Sjmallett mi.arena = av->system_mem; 3932232809Sjmallett mi.fsmblks = fastavail; 3933232809Sjmallett mi.keepcost = chunksize(av->top); 3934232809Sjmallett return mi; 3935232809Sjmallett} 3936232809Sjmallett 3937232809Sjmallett/* 3938232809Sjmallett ------------------------------ malloc_stats ------------------------------ 3939232809Sjmallett*/ 3940232809Sjmallett 3941232809Sjmallettvoid mSTATs() 3942232809Sjmallett{ 3943232809Sjmallett} 3944232809Sjmallett 3945232809Sjmallett 3946232809Sjmallett/* 3947232809Sjmallett ------------------------------ mallopt ------------------------------ 3948232809Sjmallett*/ 3949232809Sjmallett 3950232809Sjmallett#if 0 3951232809Sjmallett#if __STD_C 3952232809Sjmallettint mALLOPt(int param_number, int value) 3953232809Sjmallett#else 3954232809Sjmallettint mALLOPt(param_number, value) int param_number; int value; 3955232809Sjmallett#endif 3956232809Sjmallett{ 3957232809Sjmallett} 3958232809Sjmallett#endif 3959232809Sjmallett 3960232809Sjmallett 3961232809Sjmallett/* 3962232809Sjmallett -------------------- Alternative MORECORE functions -------------------- 3963232809Sjmallett*/ 3964232809Sjmallett 3965232809Sjmallett 3966232809Sjmallett/* 3967232809Sjmallett General Requirements for MORECORE. 3968232809Sjmallett 3969232809Sjmallett The MORECORE function must have the following properties: 3970232809Sjmallett 3971232809Sjmallett If MORECORE_CONTIGUOUS is false: 3972232809Sjmallett 3973232809Sjmallett * MORECORE must allocate in multiples of pagesize. It will 3974232809Sjmallett only be called with arguments that are multiples of pagesize. 3975232809Sjmallett 3976232809Sjmallett * MORECORE(0) must return an address that is at least 3977232809Sjmallett MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.) 3978232809Sjmallett 3979232809Sjmallett else (i.e. If MORECORE_CONTIGUOUS is true): 3980232809Sjmallett 3981232809Sjmallett * Consecutive calls to MORECORE with positive arguments 3982232809Sjmallett return increasing addresses, indicating that space has been 3983232809Sjmallett contiguously extended. 3984232809Sjmallett 3985232809Sjmallett * MORECORE need not allocate in multiples of pagesize. 3986232809Sjmallett Calls to MORECORE need not have args of multiples of pagesize. 3987232809Sjmallett 3988232809Sjmallett * MORECORE need not page-align. 3989232809Sjmallett 3990232809Sjmallett In either case: 3991232809Sjmallett 3992232809Sjmallett * MORECORE may allocate more memory than requested. (Or even less, 3993232809Sjmallett but this will generally result in a malloc failure.) 3994232809Sjmallett 3995232809Sjmallett * MORECORE must not allocate memory when given argument zero, but 3996232809Sjmallett instead return one past the end address of memory from previous 3997232809Sjmallett nonzero call. This malloc does NOT call MORECORE(0) 3998232809Sjmallett until at least one call with positive arguments is made, so 3999232809Sjmallett the initial value returned is not important. 4000232809Sjmallett 4001232809Sjmallett * Even though consecutive calls to MORECORE need not return contiguous 4002232809Sjmallett addresses, it must be OK for malloc'ed chunks to span multiple 4003232809Sjmallett regions in those cases where they do happen to be contiguous. 4004232809Sjmallett 4005232809Sjmallett * MORECORE need not handle negative arguments -- it may instead 4006232809Sjmallett just return MORECORE_FAILURE when given negative arguments. 4007232809Sjmallett Negative arguments are always multiples of pagesize. MORECORE 4008232809Sjmallett must not misinterpret negative args as large positive unsigned 4009232809Sjmallett args. You can suppress all such calls from even occurring by defining 4010232809Sjmallett MORECORE_CANNOT_TRIM, 4011232809Sjmallett 4012232809Sjmallett There is some variation across systems about the type of the 4013232809Sjmallett argument to sbrk/MORECORE. If size_t is unsigned, then it cannot 4014232809Sjmallett actually be size_t, because sbrk supports negative args, so it is 4015232809Sjmallett normally the signed type of the same width as size_t (sometimes 4016232809Sjmallett declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much 4017232809Sjmallett matter though. Internally, we use "long" as arguments, which should 4018232809Sjmallett work across all reasonable possibilities. 4019232809Sjmallett 4020232809Sjmallett Additionally, if MORECORE ever returns failure for a positive 4021232809Sjmallett request, and HAVE_MMAP is true, then mmap is used as a noncontiguous 4022232809Sjmallett system allocator. This is a useful backup strategy for systems with 4023232809Sjmallett holes in address spaces -- in this case sbrk cannot contiguously 4024232809Sjmallett expand the heap, but mmap may be able to map noncontiguous space. 4025232809Sjmallett 4026232809Sjmallett If you'd like mmap to ALWAYS be used, you can define MORECORE to be 4027232809Sjmallett a function that always returns MORECORE_FAILURE. 4028232809Sjmallett 4029232809Sjmallett If you are using this malloc with something other than sbrk (or its 4030232809Sjmallett emulation) to supply memory regions, you probably want to set 4031232809Sjmallett MORECORE_CONTIGUOUS as false. As an example, here is a custom 4032232809Sjmallett allocator kindly contributed for pre-OSX macOS. It uses virtually 4033232809Sjmallett but not necessarily physically contiguous non-paged memory (locked 4034232809Sjmallett in, present and won't get swapped out). You can use it by 4035232809Sjmallett uncommenting this section, adding some #includes, and setting up the 4036232809Sjmallett appropriate defines above: 4037232809Sjmallett 4038232809Sjmallett #define MORECORE osMoreCore 4039232809Sjmallett #define MORECORE_CONTIGUOUS 0 4040232809Sjmallett 4041232809Sjmallett There is also a shutdown routine that should somehow be called for 4042232809Sjmallett cleanup upon program exit. 4043232809Sjmallett 4044232809Sjmallett #define MAX_POOL_ENTRIES 100 4045232809Sjmallett #define MINIMUM_MORECORE_SIZE (64 * 1024) 4046232809Sjmallett static int next_os_pool; 4047232809Sjmallett void *our_os_pools[MAX_POOL_ENTRIES]; 4048232809Sjmallett 4049232809Sjmallett void *osMoreCore(int size) 4050232809Sjmallett { 4051232809Sjmallett void *ptr = 0; 4052232809Sjmallett static void *sbrk_top = 0; 4053232809Sjmallett 4054232809Sjmallett if (size > 0) 4055232809Sjmallett { 4056232809Sjmallett if (size < MINIMUM_MORECORE_SIZE) 4057232809Sjmallett size = MINIMUM_MORECORE_SIZE; 4058232809Sjmallett if (CurrentExecutionLevel() == kTaskLevel) 4059232809Sjmallett ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0); 4060232809Sjmallett if (ptr == 0) 4061232809Sjmallett { 4062232809Sjmallett return (void *) MORECORE_FAILURE; 4063232809Sjmallett } 4064232809Sjmallett // save ptrs so they can be freed during cleanup 4065232809Sjmallett our_os_pools[next_os_pool] = ptr; 4066232809Sjmallett next_os_pool++; 4067232809Sjmallett ptr = (void *) ((((unsigned long) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK); 4068232809Sjmallett sbrk_top = (char *) ptr + size; 4069232809Sjmallett return ptr; 4070232809Sjmallett } 4071232809Sjmallett else if (size < 0) 4072232809Sjmallett { 4073232809Sjmallett // we don't currently support shrink behavior 4074232809Sjmallett return (void *) MORECORE_FAILURE; 4075232809Sjmallett } 4076232809Sjmallett else 4077232809Sjmallett { 4078232809Sjmallett return sbrk_top; 4079232809Sjmallett } 4080232809Sjmallett } 4081232809Sjmallett 4082232809Sjmallett // cleanup any allocated memory pools 4083232809Sjmallett // called as last thing before shutting down driver 4084232809Sjmallett 4085232809Sjmallett void osCleanupMem(void) 4086232809Sjmallett { 4087232809Sjmallett void **ptr; 4088232809Sjmallett 4089232809Sjmallett for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++) 4090232809Sjmallett if (*ptr) 4091232809Sjmallett { 4092232809Sjmallett PoolDeallocate(*ptr); 4093232809Sjmallett *ptr = 0; 4094232809Sjmallett } 4095232809Sjmallett } 4096232809Sjmallett 4097232809Sjmallett*/ 4098232809Sjmallett 4099232809Sjmallett 4100232809Sjmallett 4101232809Sjmallett/* ------------------------------------------------------------ 4102232809SjmallettHistory: 4103232809Sjmallett 4104232809Sjmallett[see ftp://g.oswego.edu/pub/misc/malloc.c for the history of dlmalloc] 4105232809Sjmallett 4106232809Sjmallett*/ 4107