1/* 2 This is a version (aka dlmalloc) of malloc/free/realloc written by 3 Doug Lea and released to the public domain, as explained at 4 http://creativecommons.org/licenses/publicdomain. Send questions, 5 comments, complaints, performance data, etc to dl@cs.oswego.edu 6 7* Version 2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee) 8 9 Note: There may be an updated version of this malloc obtainable at 10 ftp://gee.cs.oswego.edu/pub/misc/malloc.c 11 Check before installing! 12 13* Quickstart 14 15 This library is all in one file to simplify the most common usage: 16 ftp it, compile it (-O3), and link it into another program. All of 17 the compile-time options default to reasonable values for use on 18 most platforms. You might later want to step through various 19 compile-time and dynamic tuning options. 20 21 For convenience, an include file for code using this malloc is at: 22 ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.4.h 23 You don't really need this .h file unless you call functions not 24 defined in your system include files. The .h file contains only the 25 excerpts from this file needed for using this malloc on ANSI C/C++ 26 systems, so long as you haven't changed compile-time options about 27 naming and tuning parameters. If you do, then you can create your 28 own malloc.h that does include all settings by cutting at the point 29 indicated below. Note that you may already by default be using a C 30 library containing a malloc that is based on some version of this 31 malloc (for example in linux). You might still want to use the one 32 in this file to customize settings or to avoid overheads associated 33 with library versions. 34 35* Vital statistics: 36 37 Supported pointer/size_t representation: 4 or 8 bytes 38 size_t MUST be an unsigned type of the same width as 39 pointers. (If you are using an ancient system that declares 40 size_t as a signed type, or need it to be a different width 41 than pointers, you can use a previous release of this malloc 42 (e.g. 2.7.2) supporting these.) 43 44 Alignment: 8 bytes (default) 45 This suffices for nearly all current machines and C compilers. 46 However, you can define MALLOC_ALIGNMENT to be wider than this 47 if necessary (up to 128bytes), at the expense of using more space. 48 49 Minimum overhead per allocated chunk: 4 or 8 bytes (if 4byte sizes) 50 8 or 16 bytes (if 8byte sizes) 51 Each malloced chunk has a hidden word of overhead holding size 52 and status information, and additional cross-check word 53 if FOOTERS is defined. 54 55 Minimum allocated size: 4-byte ptrs: 16 bytes (including overhead) 56 8-byte ptrs: 32 bytes (including overhead) 57 58 Even a request for zero bytes (i.e., malloc(0)) returns a 59 pointer to something of the minimum allocatable size. 60 The maximum overhead wastage (i.e., number of extra bytes 61 allocated than were requested in malloc) is less than or equal 62 to the minimum size, except for requests >= mmap_threshold that 63 are serviced via mmap(), where the worst case wastage is about 64 32 bytes plus the remainder from a system page (the minimal 65 mmap unit); typically 4096 or 8192 bytes. 66 67 Security: static-safe; optionally more or less 68 The "security" of malloc refers to the ability of malicious 69 code to accentuate the effects of errors (for example, freeing 70 space that is not currently malloc'ed or overwriting past the 71 ends of chunks) in code that calls malloc. This malloc 72 guarantees not to modify any memory locations below the base of 73 heap, i.e., static variables, even in the presence of usage 74 errors. The routines additionally detect most improper frees 75 and reallocs. All this holds as long as the static bookkeeping 76 for malloc itself is not corrupted by some other means. This 77 is only one aspect of security -- these checks do not, and 78 cannot, detect all possible programming errors. 79 80 If FOOTERS is defined nonzero, then each allocated chunk 81 carries an additional check word to verify that it was malloced 82 from its space. These check words are the same within each 83 execution of a program using malloc, but differ across 84 executions, so externally crafted fake chunks cannot be 85 freed. This improves security by rejecting frees/reallocs that 86 could corrupt heap memory, in addition to the checks preventing 87 writes to statics that are always on. This may further improve 88 security at the expense of time and space overhead. (Note that 89 FOOTERS may also be worth using with MSPACES.) 90 91 By default detected errors cause the program to abort (calling 92 "abort()"). You can override this to instead proceed past 93 errors by defining PROCEED_ON_ERROR. In this case, a bad free 94 has no effect, and a malloc that encounters a bad address 95 caused by user overwrites will ignore the bad address by 96 dropping pointers and indices to all known memory. This may 97 be appropriate for programs that should continue if at all 98 possible in the face of programming errors, although they may 99 run out of memory because dropped memory is never reclaimed. 100 101 If you don't like either of these options, you can define 102 CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything 103 else. And if if you are sure that your program using malloc has 104 no errors or vulnerabilities, you can define INSECURE to 1, 105 which might (or might not) provide a small performance improvement. 106 107 Thread-safety: NOT thread-safe unless USE_LOCKS defined 108 When USE_LOCKS is defined, each public call to malloc, free, 109 etc is surrounded with either a pthread mutex or a win32 110 spinlock (depending on WIN32). This is not especially fast, and 111 can be a major bottleneck. It is designed only to provide 112 minimal protection in concurrent environments, and to provide a 113 basis for extensions. If you are using malloc in a concurrent 114 program, consider instead using nedmalloc 115 (http://www.nedprod.com/programs/portable/nedmalloc/) or 116 ptmalloc (See http://www.malloc.de), which are derived 117 from versions of this malloc. 118 119 System requirements: Any combination of MORECORE and/or MMAP/MUNMAP 120 This malloc can use unix sbrk or any emulation (invoked using 121 the CALL_MORECORE macro) and/or mmap/munmap or any emulation 122 (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system 123 memory. On most unix systems, it tends to work best if both 124 MORECORE and MMAP are enabled. On Win32, it uses emulations 125 based on VirtualAlloc. It also uses common C library functions 126 like memset. 127 128 Compliance: I believe it is compliant with the Single Unix Specification 129 (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably 130 others as well. 131 132* Overview of algorithms 133 134 This is not the fastest, most space-conserving, most portable, or 135 most tunable malloc ever written. However it is among the fastest 136 while also being among the most space-conserving, portable and 137 tunable. Consistent balance across these factors results in a good 138 general-purpose allocator for malloc-intensive programs. 139 140 In most ways, this malloc is a best-fit allocator. Generally, it 141 chooses the best-fitting existing chunk for a request, with ties 142 broken in approximately least-recently-used order. (This strategy 143 normally maintains low fragmentation.) However, for requests less 144 than 256bytes, it deviates from best-fit when there is not an 145 exactly fitting available chunk by preferring to use space adjacent 146 to that used for the previous small request, as well as by breaking 147 ties in approximately most-recently-used order. (These enhance 148 locality of series of small allocations.) And for very large requests 149 (>= 256Kb by default), it relies on system memory mapping 150 facilities, if supported. (This helps avoid carrying around and 151 possibly fragmenting memory used only for large chunks.) 152 153 All operations (except malloc_stats and mallinfo) have execution 154 times that are bounded by a constant factor of the number of bits in 155 a size_t, not counting any clearing in calloc or copying in realloc, 156 or actions surrounding MORECORE and MMAP that have times 157 proportional to the number of non-contiguous regions returned by 158 system allocation routines, which is often just 1. In real-time 159 applications, you can optionally suppress segment traversals using 160 NO_SEGMENT_TRAVERSAL, which assures bounded execution even when 161 system allocators return non-contiguous spaces, at the typical 162 expense of carrying around more memory and increased fragmentation. 163 164 The implementation is not very modular and seriously overuses 165 macros. Perhaps someday all C compilers will do as good a job 166 inlining modular code as can now be done by brute-force expansion, 167 but now, enough of them seem not to. 168 169 Some compilers issue a lot of warnings about code that is 170 dead/unreachable only on some platforms, and also about intentional 171 uses of negation on unsigned types. All known cases of each can be 172 ignored. 173 174 For a longer but out of date high-level description, see 175 http://gee.cs.oswego.edu/dl/html/malloc.html 176 177* MSPACES 178 If MSPACES is defined, then in addition to malloc, free, etc., 179 this file also defines mspace_malloc, mspace_free, etc. These 180 are versions of malloc routines that take an "mspace" argument 181 obtained using create_mspace, to control all internal bookkeeping. 182 If ONLY_MSPACES is defined, only these versions are compiled. 183 So if you would like to use this allocator for only some allocations, 184 and your system malloc for others, you can compile with 185 ONLY_MSPACES and then do something like... 186 static mspace mymspace = create_mspace(0,0); // for example 187 #define mymalloc(bytes) mspace_malloc(mymspace, bytes) 188 189 (Note: If you only need one instance of an mspace, you can instead 190 use "USE_DL_PREFIX" to relabel the global malloc.) 191 192 You can similarly create thread-local allocators by storing 193 mspaces as thread-locals. For example: 194 static __thread mspace tlms = 0; 195 void* tlmalloc(size_t bytes) { 196 if (tlms == 0) tlms = create_mspace(0, 0); 197 return mspace_malloc(tlms, bytes); 198 } 199 void tlfree(void* mem) { mspace_free(tlms, mem); } 200 201 Unless FOOTERS is defined, each mspace is completely independent. 202 You cannot allocate from one and free to another (although 203 conformance is only weakly checked, so usage errors are not always 204 caught). If FOOTERS is defined, then each chunk carries around a tag 205 indicating its originating mspace, and frees are directed to their 206 originating spaces. 207 208 ------------------------- Compile-time options --------------------------- 209 210Be careful in setting #define values for numerical constants of type 211size_t. On some systems, literal values are not automatically extended 212to size_t precision unless they are explicitly casted. You can also 213use the symbolic values MAX_SIZE_T, SIZE_T_ONE, etc below. 214 215WIN32 default: defined if _WIN32 defined 216 Defining WIN32 sets up defaults for MS environment and compilers. 217 Otherwise defaults are for unix. Beware that there seem to be some 218 cases where this malloc might not be a pure drop-in replacement for 219 Win32 malloc: Random-looking failures from Win32 GDI API's (eg; 220 SetDIBits()) may be due to bugs in some video driver implementations 221 when pixel buffers are malloc()ed, and the region spans more than 222 one VirtualAlloc()ed region. Because dlmalloc uses a small (64Kb) 223 default granularity, pixel buffers may straddle virtual allocation 224 regions more often than when using the Microsoft allocator. You can 225 avoid this by using VirtualAlloc() and VirtualFree() for all pixel 226 buffers rather than using malloc(). If this is not possible, 227 recompile this malloc with a larger DEFAULT_GRANULARITY. 228 229MALLOC_ALIGNMENT default: (size_t)8 230 Controls the minimum alignment for malloc'ed chunks. It must be a 231 power of two and at least 8, even on machines for which smaller 232 alignments would suffice. It may be defined as larger than this 233 though. Note however that code and data structures are optimized for 234 the case of 8-byte alignment. 235 236MSPACES default: 0 (false) 237 If true, compile in support for independent allocation spaces. 238 This is only supported if HAVE_MMAP is true. 239 240ONLY_MSPACES default: 0 (false) 241 If true, only compile in mspace versions, not regular versions. 242 243USE_LOCKS default: 0 (false) 244 Causes each call to each public routine to be surrounded with 245 pthread or WIN32 mutex lock/unlock. (If set true, this can be 246 overridden on a per-mspace basis for mspace versions.) If set to a 247 non-zero value other than 1, locks are used, but their 248 implementation is left out, so lock functions must be supplied manually, 249 as described below. 250 251USE_SPIN_LOCKS default: 1 iff USE_LOCKS and on x86 using gcc or MSC 252 If true, uses custom spin locks for locking. This is currently 253 supported only for x86 platforms using gcc or recent MS compilers. 254 Otherwise, posix locks or win32 critical sections are used. 255 256FOOTERS default: 0 257 If true, provide extra checking and dispatching by placing 258 information in the footers of allocated chunks. This adds 259 space and time overhead. 260 261INSECURE default: 0 262 If true, omit checks for usage errors and heap space overwrites. 263 264USE_DL_PREFIX default: NOT defined 265 Causes compiler to prefix all public routines with the string 'dl'. 266 This can be useful when you only want to use this malloc in one part 267 of a program, using your regular system malloc elsewhere. 268 269ABORT default: defined as abort() 270 Defines how to abort on failed checks. On most systems, a failed 271 check cannot die with an "assert" or even print an informative 272 message, because the underlying print routines in turn call malloc, 273 which will fail again. Generally, the best policy is to simply call 274 abort(). It's not very useful to do more than this because many 275 errors due to overwriting will show up as address faults (null, odd 276 addresses etc) rather than malloc-triggered checks, so will also 277 abort. Also, most compilers know that abort() does not return, so 278 can better optimize code conditionally calling it. 279 280PROCEED_ON_ERROR default: defined as 0 (false) 281 Controls whether detected bad addresses cause them to bypassed 282 rather than aborting. If set, detected bad arguments to free and 283 realloc are ignored. And all bookkeeping information is zeroed out 284 upon a detected overwrite of freed heap space, thus losing the 285 ability to ever return it from malloc again, but enabling the 286 application to proceed. If PROCEED_ON_ERROR is defined, the 287 static variable malloc_corruption_error_count is compiled in 288 and can be examined to see if errors have occurred. This option 289 generates slower code than the default abort policy. 290 291DEBUG default: NOT defined 292 The DEBUG setting is mainly intended for people trying to modify 293 this code or diagnose problems when porting to new platforms. 294 However, it may also be able to better isolate user errors than just 295 using runtime checks. The assertions in the check routines spell 296 out in more detail the assumptions and invariants underlying the 297 algorithms. The checking is fairly extensive, and will slow down 298 execution noticeably. Calling malloc_stats or mallinfo with DEBUG 299 set will attempt to check every non-mmapped allocated and free chunk 300 in the course of computing the summaries. 301 302ABORT_ON_ASSERT_FAILURE default: defined as 1 (true) 303 Debugging assertion failures can be nearly impossible if your 304 version of the assert macro causes malloc to be called, which will 305 lead to a cascade of further failures, blowing the runtime stack. 306 ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(), 307 which will usually make debugging easier. 308 309MALLOC_FAILURE_ACTION default: sets errno to ENOMEM, or no-op on win32 310 The action to take before "return 0" when malloc fails to be able to 311 return memory because there is none available. 312 313HAVE_MORECORE default: 1 (true) unless win32 or ONLY_MSPACES 314 True if this system supports sbrk or an emulation of it. 315 316MORECORE default: sbrk 317 The name of the sbrk-style system routine to call to obtain more 318 memory. See below for guidance on writing custom MORECORE 319 functions. The type of the argument to sbrk/MORECORE varies across 320 systems. It cannot be size_t, because it supports negative 321 arguments, so it is normally the signed type of the same width as 322 size_t (sometimes declared as "intptr_t"). It doesn't much matter 323 though. Internally, we only call it with arguments less than half 324 the max value of a size_t, which should work across all reasonable 325 possibilities, although sometimes generating compiler warnings. 326 327MORECORE_CONTIGUOUS default: 1 (true) if HAVE_MORECORE 328 If true, take advantage of fact that consecutive calls to MORECORE 329 with positive arguments always return contiguous increasing 330 addresses. This is true of unix sbrk. It does not hurt too much to 331 set it true anyway, since malloc copes with non-contiguities. 332 Setting it false when definitely non-contiguous saves time 333 and possibly wasted space it would take to discover this though. 334 335MORECORE_CANNOT_TRIM default: NOT defined 336 True if MORECORE cannot release space back to the system when given 337 negative arguments. This is generally necessary only if you are 338 using a hand-crafted MORECORE function that cannot handle negative 339 arguments. 340 341NO_SEGMENT_TRAVERSAL default: 0 342 If non-zero, suppresses traversals of memory segments 343 returned by either MORECORE or CALL_MMAP. This disables 344 merging of segments that are contiguous, and selectively 345 releasing them to the OS if unused, but bounds execution times. 346 347HAVE_MMAP default: 1 (true) 348 True if this system supports mmap or an emulation of it. If so, and 349 HAVE_MORECORE is not true, MMAP is used for all system 350 allocation. If set and HAVE_MORECORE is true as well, MMAP is 351 primarily used to directly allocate very large blocks. It is also 352 used as a backup strategy in cases where MORECORE fails to provide 353 space from system. Note: A single call to MUNMAP is assumed to be 354 able to unmap memory that may have be allocated using multiple calls 355 to MMAP, so long as they are adjacent. 356 357HAVE_MREMAP default: 1 on linux, else 0 358 If true realloc() uses mremap() to re-allocate large blocks and 359 extend or shrink allocation spaces. 360 361MMAP_CLEARS default: 1 except on WINCE. 362 True if mmap clears memory so calloc doesn't need to. This is true 363 for standard unix mmap using /dev/zero and on WIN32 except for WINCE. 364 365USE_BUILTIN_FFS default: 0 (i.e., not used) 366 Causes malloc to use the builtin ffs() function to compute indices. 367 Some compilers may recognize and intrinsify ffs to be faster than the 368 supplied C version. Also, the case of x86 using gcc is special-cased 369 to an asm instruction, so is already as fast as it can be, and so 370 this setting has no effect. Similarly for Win32 under recent MS compilers. 371 (On most x86s, the asm version is only slightly faster than the C version.) 372 373malloc_getpagesize default: derive from system includes, or 4096. 374 The system page size. To the extent possible, this malloc manages 375 memory from the system in page-size units. This may be (and 376 usually is) a function rather than a constant. This is ignored 377 if WIN32, where page size is determined using getSystemInfo during 378 initialization. 379 380USE_DEV_RANDOM default: 0 (i.e., not used) 381 Causes malloc to use /dev/random to initialize secure magic seed for 382 stamping footers. Otherwise, the current time is used. 383 384NO_MALLINFO default: 0 385 If defined, don't compile "mallinfo". This can be a simple way 386 of dealing with mismatches between system declarations and 387 those in this file. 388 389MALLINFO_FIELD_TYPE default: size_t 390 The type of the fields in the mallinfo struct. This was originally 391 defined as "int" in SVID etc, but is more usefully defined as 392 size_t. The value is used only if HAVE_USR_INCLUDE_MALLOC_H is not set 393 394REALLOC_ZERO_BYTES_FREES default: not defined 395 This should be set if a call to realloc with zero bytes should 396 be the same as a call to free. Some people think it should. Otherwise, 397 since this malloc returns a unique pointer for malloc(0), so does 398 realloc(p, 0). 399 400LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H 401LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H, LACKS_ERRNO_H 402LACKS_STDLIB_H default: NOT defined unless on WIN32 403 Define these if your system does not have these header files. 404 You might need to manually insert some of the declarations they provide. 405 406DEFAULT_GRANULARITY default: page size if MORECORE_CONTIGUOUS, 407 system_info.dwAllocationGranularity in WIN32, 408 otherwise 64K. 409 Also settable using mallopt(M_GRANULARITY, x) 410 The unit for allocating and deallocating memory from the system. On 411 most systems with contiguous MORECORE, there is no reason to 412 make this more than a page. However, systems with MMAP tend to 413 either require or encourage larger granularities. You can increase 414 this value to prevent system allocation functions to be called so 415 often, especially if they are slow. The value must be at least one 416 page and must be a power of two. Setting to 0 causes initialization 417 to either page size or win32 region size. (Note: In previous 418 versions of malloc, the equivalent of this option was called 419 "TOP_PAD") 420 421DEFAULT_TRIM_THRESHOLD default: 2MB 422 Also settable using mallopt(M_TRIM_THRESHOLD, x) 423 The maximum amount of unused top-most memory to keep before 424 releasing via malloc_trim in free(). Automatic trimming is mainly 425 useful in long-lived programs using contiguous MORECORE. Because 426 trimming via sbrk can be slow on some systems, and can sometimes be 427 wasteful (in cases where programs immediately afterward allocate 428 more large chunks) the value should be high enough so that your 429 overall system performance would improve by releasing this much 430 memory. As a rough guide, you might set to a value close to the 431 average size of a process (program) running on your system. 432 Releasing this much memory would allow such a process to run in 433 memory. Generally, it is worth tuning trim thresholds when a 434 program undergoes phases where several large chunks are allocated 435 and released in ways that can reuse each other's storage, perhaps 436 mixed with phases where there are no such chunks at all. The trim 437 value must be greater than page size to have any useful effect. To 438 disable trimming completely, you can set to MAX_SIZE_T. Note that the trick 439 some people use of mallocing a huge space and then freeing it at 440 program startup, in an attempt to reserve system memory, doesn't 441 have the intended effect under automatic trimming, since that memory 442 will immediately be returned to the system. 443 444DEFAULT_MMAP_THRESHOLD default: 256K 445 Also settable using mallopt(M_MMAP_THRESHOLD, x) 446 The request size threshold for using MMAP to directly service a 447 request. Requests of at least this size that cannot be allocated 448 using already-existing space will be serviced via mmap. (If enough 449 normal freed space already exists it is used instead.) Using mmap 450 segregates relatively large chunks of memory so that they can be 451 individually obtained and released from the host system. A request 452 serviced through mmap is never reused by any other request (at least 453 not directly; the system may just so happen to remap successive 454 requests to the same locations). Segregating space in this way has 455 the benefits that: Mmapped space can always be individually released 456 back to the system, which helps keep the system level memory demands 457 of a long-lived program low. Also, mapped memory doesn't become 458 `locked' between other chunks, as can happen with normally allocated 459 chunks, which means that even trimming via malloc_trim would not 460 release them. However, it has the disadvantage that the space 461 cannot be reclaimed, consolidated, and then used to service later 462 requests, as happens with normal chunks. The advantages of mmap 463 nearly always outweigh disadvantages for "large" chunks, but the 464 value of "large" may vary across systems. The default is an 465 empirically derived value that works well in most systems. You can 466 disable mmap by setting to MAX_SIZE_T. 467 468MAX_RELEASE_CHECK_RATE default: 4095 unless not HAVE_MMAP 469 The number of consolidated frees between checks to release 470 unused segments when freeing. When using non-contiguous segments, 471 especially with multiple mspaces, checking only for topmost space 472 doesn't always suffice to trigger trimming. To compensate for this, 473 free() will, with a period of MAX_RELEASE_CHECK_RATE (or the 474 current number of segments, if greater) try to release unused 475 segments to the OS when freeing chunks that result in 476 consolidation. The best value for this parameter is a compromise 477 between slowing down frees with relatively costly checks that 478 rarely trigger versus holding on to unused memory. To effectively 479 disable, set to MAX_SIZE_T. This may lead to a very slight speed 480 improvement at the expense of carrying around more memory. 481*/ 482 483#define USE_DL_PREFIX 484//#define HAVE_USR_INCLUDE_MALLOC_H 485//#define MSPACES 1 486#define NO_SEGMENT_TRAVERSAL 1 487 488/* Version identifier to allow people to support multiple versions */ 489#ifndef DLMALLOC_VERSION 490#define DLMALLOC_VERSION 20804 491#endif /* DLMALLOC_VERSION */ 492 493#ifndef WIN32 494#ifdef _WIN32 495#define WIN32 1 496#endif /* _WIN32 */ 497#ifdef _WIN32_WCE 498#define LACKS_FCNTL_H 499#define WIN32 1 500#endif /* _WIN32_WCE */ 501#endif /* WIN32 */ 502#ifdef WIN32 503#define WIN32_LEAN_AND_MEAN 504#include <windows.h> 505#define HAVE_MMAP 1 506#define HAVE_MORECORE 0 507#define LACKS_UNISTD_H 508#define LACKS_SYS_PARAM_H 509#define LACKS_SYS_MMAN_H 510#define LACKS_STRING_H 511#define LACKS_STRINGS_H 512#define LACKS_SYS_TYPES_H 513#define LACKS_ERRNO_H 514#ifndef MALLOC_FAILURE_ACTION 515#define MALLOC_FAILURE_ACTION 516#endif /* MALLOC_FAILURE_ACTION */ 517#ifdef _WIN32_WCE /* WINCE reportedly does not clear */ 518#define MMAP_CLEARS 0 519#else 520#define MMAP_CLEARS 1 521#endif /* _WIN32_WCE */ 522#endif /* WIN32 */ 523 524#if defined(DARWIN) || defined(_DARWIN) 525/* Mac OSX docs advise not to use sbrk; it seems better to use mmap */ 526#ifndef HAVE_MORECORE 527#define HAVE_MORECORE 0 528#define HAVE_MMAP 1 529/* OSX allocators provide 16 byte alignment */ 530#ifndef MALLOC_ALIGNMENT 531#define MALLOC_ALIGNMENT ((size_t)16U) 532#endif 533#endif /* HAVE_MORECORE */ 534#endif /* DARWIN */ 535 536#ifndef LACKS_SYS_TYPES_H 537#include <sys/types.h> /* For size_t */ 538#endif /* LACKS_SYS_TYPES_H */ 539 540#if (defined(__GNUC__) && ((defined(__i386__) || defined(__x86_64__)))) || (defined(_MSC_VER) && _MSC_VER>=1310) 541#define SPIN_LOCKS_AVAILABLE 1 542#else 543#define SPIN_LOCKS_AVAILABLE 0 544#endif 545 546/* The maximum possible size_t value has all bits set */ 547#define MAX_SIZE_T (~(size_t)0) 548 549#ifndef ONLY_MSPACES 550#define ONLY_MSPACES 0 /* define to a value */ 551#else 552#define ONLY_MSPACES 1 553#endif /* ONLY_MSPACES */ 554#ifndef MSPACES 555#if ONLY_MSPACES 556#define MSPACES 1 557#else /* ONLY_MSPACES */ 558#define MSPACES 0 559#endif /* ONLY_MSPACES */ 560#endif /* MSPACES */ 561#ifndef MALLOC_ALIGNMENT 562#define MALLOC_ALIGNMENT ((size_t)8U) 563#endif /* MALLOC_ALIGNMENT */ 564#ifndef FOOTERS 565#define FOOTERS 0 566#endif /* FOOTERS */ 567#ifndef ABORT 568#define ABORT abort() 569#endif /* ABORT */ 570#ifndef ABORT_ON_ASSERT_FAILURE 571#define ABORT_ON_ASSERT_FAILURE 1 572#endif /* ABORT_ON_ASSERT_FAILURE */ 573#ifndef PROCEED_ON_ERROR 574#define PROCEED_ON_ERROR 0 575#endif /* PROCEED_ON_ERROR */ 576#ifndef USE_LOCKS 577#define USE_LOCKS 0 578#endif /* USE_LOCKS */ 579#ifndef USE_SPIN_LOCKS 580#if USE_LOCKS && SPIN_LOCKS_AVAILABLE 581#define USE_SPIN_LOCKS 1 582#else 583#define USE_SPIN_LOCKS 0 584#endif /* USE_LOCKS && SPIN_LOCKS_AVAILABLE. */ 585#endif /* USE_SPIN_LOCKS */ 586#ifndef INSECURE 587#define INSECURE 0 588#endif /* INSECURE */ 589#ifndef HAVE_MMAP 590#define HAVE_MMAP 1 591#endif /* HAVE_MMAP */ 592#ifndef MMAP_CLEARS 593#define MMAP_CLEARS 1 594#endif /* MMAP_CLEARS */ 595#ifndef HAVE_MREMAP 596#ifdef linux 597#define HAVE_MREMAP 1 598#else /* linux */ 599#define HAVE_MREMAP 0 600#endif /* linux */ 601#endif /* HAVE_MREMAP */ 602#ifndef MALLOC_FAILURE_ACTION 603#define MALLOC_FAILURE_ACTION errno = ENOMEM; 604#endif /* MALLOC_FAILURE_ACTION */ 605#ifndef HAVE_MORECORE 606#if ONLY_MSPACES 607#define HAVE_MORECORE 0 608#else /* ONLY_MSPACES */ 609#define HAVE_MORECORE 1 610#endif /* ONLY_MSPACES */ 611#endif /* HAVE_MORECORE */ 612#if !HAVE_MORECORE 613#define MORECORE_CONTIGUOUS 0 614#else /* !HAVE_MORECORE */ 615#define MORECORE_DEFAULT sbrk 616#ifndef MORECORE_CONTIGUOUS 617#define MORECORE_CONTIGUOUS 1 618#endif /* MORECORE_CONTIGUOUS */ 619#endif /* HAVE_MORECORE */ 620#ifndef DEFAULT_GRANULARITY 621#if (MORECORE_CONTIGUOUS || defined(WIN32)) 622#define DEFAULT_GRANULARITY (0) /* 0 means to compute in init_mparams */ 623#else /* MORECORE_CONTIGUOUS */ 624#define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U) 625#endif /* MORECORE_CONTIGUOUS */ 626#endif /* DEFAULT_GRANULARITY */ 627#ifndef DEFAULT_TRIM_THRESHOLD 628#ifndef MORECORE_CANNOT_TRIM 629#define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U) 630#else /* MORECORE_CANNOT_TRIM */ 631#define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T 632#endif /* MORECORE_CANNOT_TRIM */ 633#endif /* DEFAULT_TRIM_THRESHOLD */ 634#ifndef DEFAULT_MMAP_THRESHOLD 635#if HAVE_MMAP 636#define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U) 637#else /* HAVE_MMAP */ 638#define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T 639#endif /* HAVE_MMAP */ 640#endif /* DEFAULT_MMAP_THRESHOLD */ 641#ifndef MAX_RELEASE_CHECK_RATE 642#if HAVE_MMAP 643#define MAX_RELEASE_CHECK_RATE 4095 644#else 645#define MAX_RELEASE_CHECK_RATE MAX_SIZE_T 646#endif /* HAVE_MMAP */ 647#endif /* MAX_RELEASE_CHECK_RATE */ 648#ifndef USE_BUILTIN_FFS 649#define USE_BUILTIN_FFS 0 650#endif /* USE_BUILTIN_FFS */ 651#ifndef USE_DEV_RANDOM 652#define USE_DEV_RANDOM 0 653#endif /* USE_DEV_RANDOM */ 654#ifndef NO_MALLINFO 655#define NO_MALLINFO 0 656#endif /* NO_MALLINFO */ 657#ifndef MALLINFO_FIELD_TYPE 658#define MALLINFO_FIELD_TYPE size_t 659#endif /* MALLINFO_FIELD_TYPE */ 660#ifndef NO_SEGMENT_TRAVERSAL 661#define NO_SEGMENT_TRAVERSAL 0 662#endif /* NO_SEGMENT_TRAVERSAL */ 663 664/* 665 mallopt tuning options. SVID/XPG defines four standard parameter 666 numbers for mallopt, normally defined in malloc.h. None of these 667 are used in this malloc, so setting them has no effect. But this 668 malloc does support the following options. 669*/ 670 671#define M_TRIM_THRESHOLD (-1) 672#define M_GRANULARITY (-2) 673#define M_MMAP_THRESHOLD (-3) 674 675/* ------------------------ Mallinfo declarations ------------------------ */ 676 677#if !NO_MALLINFO 678/* 679 This version of malloc supports the standard SVID/XPG mallinfo 680 routine that returns a struct containing usage properties and 681 statistics. It should work on any system that has a 682 /usr/include/malloc.h defining struct mallinfo. The main 683 declaration needed is the mallinfo struct that is returned (by-copy) 684 by mallinfo(). The malloinfo struct contains a bunch of fields that 685 are not even meaningful in this version of malloc. These fields are 686 are instead filled by mallinfo() with other numbers that might be of 687 interest. 688 689 HAVE_USR_INCLUDE_MALLOC_H should be set if you have a 690 /usr/include/malloc.h file that includes a declaration of struct 691 mallinfo. If so, it is included; else a compliant version is 692 declared below. These must be precisely the same for mallinfo() to 693 work. The original SVID version of this struct, defined on most 694 systems with mallinfo, declares all fields as ints. But some others 695 define as unsigned long. If your system defines the fields using a 696 type of different width than listed here, you MUST #include your 697 system version and #define HAVE_USR_INCLUDE_MALLOC_H. 698*/ 699 700/* #define HAVE_USR_INCLUDE_MALLOC_H */ 701 702#ifdef HAVE_USR_INCLUDE_MALLOC_H 703#include "/usr/include/malloc.h" 704#else /* HAVE_USR_INCLUDE_MALLOC_H */ 705#ifndef STRUCT_MALLINFO_DECLARED 706#define STRUCT_MALLINFO_DECLARED 1 707struct mallinfo { 708 MALLINFO_FIELD_TYPE arena; /* non-mmapped space allocated from system */ 709 MALLINFO_FIELD_TYPE ordblks; /* number of free chunks */ 710 MALLINFO_FIELD_TYPE smblks; /* always 0 */ 711 MALLINFO_FIELD_TYPE hblks; /* always 0 */ 712 MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */ 713 MALLINFO_FIELD_TYPE usmblks; /* maximum total allocated space */ 714 MALLINFO_FIELD_TYPE fsmblks; /* always 0 */ 715 MALLINFO_FIELD_TYPE uordblks; /* total allocated space */ 716 MALLINFO_FIELD_TYPE fordblks; /* total free space */ 717 MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */ 718}; 719#endif /* STRUCT_MALLINFO_DECLARED */ 720#endif /* HAVE_USR_INCLUDE_MALLOC_H */ 721#endif /* NO_MALLINFO */ 722 723/* 724 Try to persuade compilers to inline. The most critical functions for 725 inlining are defined as macros, so these aren't used for them. 726*/ 727 728#ifndef FORCEINLINE 729 #if defined(__GNUC__) 730#define FORCEINLINE __inline __attribute__ ((always_inline)) 731 #elif defined(_MSC_VER) 732 #define FORCEINLINE __forceinline 733 #endif 734#endif 735#ifndef NOINLINE 736 #if defined(__GNUC__) 737 #define NOINLINE __attribute__ ((noinline)) 738 #elif defined(_MSC_VER) 739 #define NOINLINE __declspec(noinline) 740 #else 741 #define NOINLINE 742 #endif 743#endif 744 745#ifdef __cplusplus 746extern "C" { 747#ifndef FORCEINLINE 748 #define FORCEINLINE inline 749#endif 750#endif /* __cplusplus */ 751#ifndef FORCEINLINE 752 #define FORCEINLINE 753#endif 754 755#if !ONLY_MSPACES 756 757/* ------------------- Declarations of public routines ------------------- */ 758 759#ifndef USE_DL_PREFIX 760#define dlcalloc calloc 761#define dlfree free 762#define dlmalloc malloc 763#define dlmemalign memalign 764#define dlrealloc realloc 765#define dlvalloc valloc 766#define dlpvalloc pvalloc 767#define dlmallinfo mallinfo 768#define dlmallopt mallopt 769#define dlmalloc_trim malloc_trim 770#define dlmalloc_stats malloc_stats 771#define dlmalloc_usable_size malloc_usable_size 772#define dlmalloc_footprint malloc_footprint 773#define dlmalloc_max_footprint malloc_max_footprint 774#define dlindependent_calloc independent_calloc 775#define dlindependent_comalloc independent_comalloc 776#endif /* USE_DL_PREFIX */ 777 778 779/* 780 malloc(size_t n) 781 Returns a pointer to a newly allocated chunk of at least n bytes, or 782 null if no space is available, in which case errno is set to ENOMEM 783 on ANSI C systems. 784 785 If n is zero, malloc returns a minimum-sized chunk. (The minimum 786 size is 16 bytes on most 32bit systems, and 32 bytes on 64bit 787 systems.) Note that size_t is an unsigned type, so calls with 788 arguments that would be negative if signed are interpreted as 789 requests for huge amounts of space, which will often fail. The 790 maximum supported value of n differs across systems, but is in all 791 cases less than the maximum representable value of a size_t. 792*/ 793void* dlmalloc(size_t); 794 795/* 796 free(void* p) 797 Releases the chunk of memory pointed to by p, that had been previously 798 allocated using malloc or a related routine such as realloc. 799 It has no effect if p is null. If p was not malloced or already 800 freed, free(p) will by default cause the current program to abort. 801*/ 802void dlfree(void*); 803 804/* 805 calloc(size_t n_elements, size_t element_size); 806 Returns a pointer to n_elements * element_size bytes, with all locations 807 set to zero. 808*/ 809void* dlcalloc(size_t, size_t); 810 811/* 812 realloc(void* p, size_t n) 813 Returns a pointer to a chunk of size n that contains the same data 814 as does chunk p up to the minimum of (n, p's size) bytes, or null 815 if no space is available. 816 817 The returned pointer may or may not be the same as p. The algorithm 818 prefers extending p in most cases when possible, otherwise it 819 employs the equivalent of a malloc-copy-free sequence. 820 821 If p is null, realloc is equivalent to malloc. 822 823 If space is not available, realloc returns null, errno is set (if on 824 ANSI) and p is NOT freed. 825 826 if n is for fewer bytes than already held by p, the newly unused 827 space is lopped off and freed if possible. realloc with a size 828 argument of zero (re)allocates a minimum-sized chunk. 829 830 The old unix realloc convention of allowing the last-free'd chunk 831 to be used as an argument to realloc is not supported. 832*/ 833 834void* dlrealloc(void*, size_t); 835 836/* 837 memalign(size_t alignment, size_t n); 838 Returns a pointer to a newly allocated chunk of n bytes, aligned 839 in accord with the alignment argument. 840 841 The alignment argument should be a power of two. If the argument is 842 not a power of two, the nearest greater power is used. 843 8-byte alignment is guaranteed by normal malloc calls, so don't 844 bother calling memalign with an argument of 8 or less. 845 846 Overreliance on memalign is a sure way to fragment space. 847*/ 848void* dlmemalign(size_t, size_t); 849 850/* 851 valloc(size_t n); 852 Equivalent to memalign(pagesize, n), where pagesize is the page 853 size of the system. If the pagesize is unknown, 4096 is used. 854*/ 855void* dlvalloc(size_t); 856 857/* 858 mallopt(int parameter_number, int parameter_value) 859 Sets tunable parameters The format is to provide a 860 (parameter-number, parameter-value) pair. mallopt then sets the 861 corresponding parameter to the argument value if it can (i.e., so 862 long as the value is meaningful), and returns 1 if successful else 863 0. To workaround the fact that mallopt is specified to use int, 864 not size_t parameters, the value -1 is specially treated as the 865 maximum unsigned size_t value. 866 867 SVID/XPG/ANSI defines four standard param numbers for mallopt, 868 normally defined in malloc.h. None of these are use in this malloc, 869 so setting them has no effect. But this malloc also supports other 870 options in mallopt. See below for details. Briefly, supported 871 parameters are as follows (listed defaults are for "typical" 872 configurations). 873 874 Symbol param # default allowed param values 875 M_TRIM_THRESHOLD -1 2*1024*1024 any (-1 disables) 876 M_GRANULARITY -2 page size any power of 2 >= page size 877 M_MMAP_THRESHOLD -3 256*1024 any (or 0 if no MMAP support) 878*/ 879int dlmallopt(int, int); 880 881/* 882 malloc_footprint(); 883 Returns the number of bytes obtained from the system. The total 884 number of bytes allocated by malloc, realloc etc., is less than this 885 value. Unlike mallinfo, this function returns only a precomputed 886 result, so can be called frequently to monitor memory consumption. 887 Even if locks are otherwise defined, this function does not use them, 888 so results might not be up to date. 889*/ 890size_t dlmalloc_footprint(void); 891 892/* 893 malloc_max_footprint(); 894 Returns the maximum number of bytes obtained from the system. This 895 value will be greater than current footprint if deallocated space 896 has been reclaimed by the system. The peak number of bytes allocated 897 by malloc, realloc etc., is less than this value. Unlike mallinfo, 898 this function returns only a precomputed result, so can be called 899 frequently to monitor memory consumption. Even if locks are 900 otherwise defined, this function does not use them, so results might 901 not be up to date. 902*/ 903size_t dlmalloc_max_footprint(void); 904 905#if !NO_MALLINFO 906/* 907 mallinfo() 908 Returns (by copy) a struct containing various summary statistics: 909 910 arena: current total non-mmapped bytes allocated from system 911 ordblks: the number of free chunks 912 smblks: always zero. 913 hblks: current number of mmapped regions 914 hblkhd: total bytes held in mmapped regions 915 usmblks: the maximum total allocated space. This will be greater 916 than current total if trimming has occurred. 917 fsmblks: always zero 918 uordblks: current total allocated space (normal or mmapped) 919 fordblks: total free space 920 keepcost: the maximum number of bytes that could ideally be released 921 back to system via malloc_trim. ("ideally" means that 922 it ignores page restrictions etc.) 923 924 Because these fields are ints, but internal bookkeeping may 925 be kept as longs, the reported values may wrap around zero and 926 thus be inaccurate. 927*/ 928struct mallinfo dlmallinfo(void); 929#endif /* NO_MALLINFO */ 930 931/* 932 independent_calloc(size_t n_elements, size_t element_size, void* chunks[]); 933 934 independent_calloc is similar to calloc, but instead of returning a 935 single cleared space, it returns an array of pointers to n_elements 936 independent elements that can hold contents of size elem_size, each 937 of which starts out cleared, and can be independently freed, 938 realloc'ed etc. The elements are guaranteed to be adjacently 939 allocated (this is not guaranteed to occur with multiple callocs or 940 mallocs), which may also improve cache locality in some 941 applications. 942 943 The "chunks" argument is optional (i.e., may be null, which is 944 probably the most typical usage). If it is null, the returned array 945 is itself dynamically allocated and should also be freed when it is 946 no longer needed. Otherwise, the chunks array must be of at least 947 n_elements in length. It is filled in with the pointers to the 948 chunks. 949 950 In either case, independent_calloc returns this pointer array, or 951 null if the allocation failed. If n_elements is zero and "chunks" 952 is null, it returns a chunk representing an array with zero elements 953 (which should be freed if not wanted). 954 955 Each element must be individually freed when it is no longer 956 needed. If you'd like to instead be able to free all at once, you 957 should instead use regular calloc and assign pointers into this 958 space to represent elements. (In this case though, you cannot 959 independently free elements.) 960 961 independent_calloc simplifies and speeds up implementations of many 962 kinds of pools. It may also be useful when constructing large data 963 structures that initially have a fixed number of fixed-sized nodes, 964 but the number is not known at compile time, and some of the nodes 965 may later need to be freed. For example: 966 967 struct Node { int item; struct Node* next; }; 968 969 struct Node* build_list() { 970 struct Node** pool; 971 int n = read_number_of_nodes_needed(); 972 if (n <= 0) return 0; 973 pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0); 974 if (pool == 0) die(); 975 // organize into a linked list... 976 struct Node* first = pool[0]; 977 for (i = 0; i < n-1; ++i) 978 pool[i]->next = pool[i+1]; 979 free(pool); // Can now free the array (or not, if it is needed later) 980 return first; 981 } 982*/ 983void** dlindependent_calloc(size_t, size_t, void**); 984 985/* 986 independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]); 987 988 independent_comalloc allocates, all at once, a set of n_elements 989 chunks with sizes indicated in the "sizes" array. It returns 990 an array of pointers to these elements, each of which can be 991 independently freed, realloc'ed etc. The elements are guaranteed to 992 be adjacently allocated (this is not guaranteed to occur with 993 multiple callocs or mallocs), which may also improve cache locality 994 in some applications. 995 996 The "chunks" argument is optional (i.e., may be null). If it is null 997 the returned array is itself dynamically allocated and should also 998 be freed when it is no longer needed. Otherwise, the chunks array 999 must be of at least n_elements in length. It is filled in with the 1000 pointers to the chunks. 1001 1002 In either case, independent_comalloc returns this pointer array, or 1003 null if the allocation failed. If n_elements is zero and chunks is 1004 null, it returns a chunk representing an array with zero elements 1005 (which should be freed if not wanted). 1006 1007 Each element must be individually freed when it is no longer 1008 needed. If you'd like to instead be able to free all at once, you 1009 should instead use a single regular malloc, and assign pointers at 1010 particular offsets in the aggregate space. (In this case though, you 1011 cannot independently free elements.) 1012 1013 independent_comallac differs from independent_calloc in that each 1014 element may have a different size, and also that it does not 1015 automatically clear elements. 1016 1017 independent_comalloc can be used to speed up allocation in cases 1018 where several structs or objects must always be allocated at the 1019 same time. For example: 1020 1021 struct Head { ... } 1022 struct Foot { ... } 1023 1024 void send_message(char* msg) { 1025 int msglen = strlen(msg); 1026 size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) }; 1027 void* chunks[3]; 1028 if (independent_comalloc(3, sizes, chunks) == 0) 1029 die(); 1030 struct Head* head = (struct Head*)(chunks[0]); 1031 char* body = (char*)(chunks[1]); 1032 struct Foot* foot = (struct Foot*)(chunks[2]); 1033 // ... 1034 } 1035 1036 In general though, independent_comalloc is worth using only for 1037 larger values of n_elements. For small values, you probably won't 1038 detect enough difference from series of malloc calls to bother. 1039 1040 Overuse of independent_comalloc can increase overall memory usage, 1041 since it cannot reuse existing noncontiguous small chunks that 1042 might be available for some of the elements. 1043*/ 1044void** dlindependent_comalloc(size_t, size_t*, void**); 1045 1046 1047/* 1048 pvalloc(size_t n); 1049 Equivalent to valloc(minimum-page-that-holds(n)), that is, 1050 round up n to nearest pagesize. 1051 */ 1052void* dlpvalloc(size_t); 1053 1054/* 1055 malloc_trim(size_t pad); 1056 1057 If possible, gives memory back to the system (via negative arguments 1058 to sbrk) if there is unused memory at the `high' end of the malloc 1059 pool or in unused MMAP segments. You can call this after freeing 1060 large blocks of memory to potentially reduce the system-level memory 1061 requirements of a program. However, it cannot guarantee to reduce 1062 memory. Under some allocation patterns, some large free blocks of 1063 memory will be locked between two used chunks, so they cannot be 1064 given back to the system. 1065 1066 The `pad' argument to malloc_trim represents the amount of free 1067 trailing space to leave untrimmed. If this argument is zero, only 1068 the minimum amount of memory to maintain internal data structures 1069 will be left. Non-zero arguments can be supplied to maintain enough 1070 trailing space to service future expected allocations without having 1071 to re-obtain memory from the system. 1072 1073 Malloc_trim returns 1 if it actually released any memory, else 0. 1074*/ 1075int dlmalloc_trim(size_t); 1076 1077/* 1078 malloc_stats(); 1079 Prints on stderr the amount of space obtained from the system (both 1080 via sbrk and mmap), the maximum amount (which may be more than 1081 current if malloc_trim and/or munmap got called), and the current 1082 number of bytes allocated via malloc (or realloc, etc) but not yet 1083 freed. Note that this is the number of bytes allocated, not the 1084 number requested. It will be larger than the number requested 1085 because of alignment and bookkeeping overhead. Because it includes 1086 alignment wastage as being in use, this figure may be greater than 1087 zero even when no user-level chunks are allocated. 1088 1089 The reported current and maximum system memory can be inaccurate if 1090 a program makes other calls to system memory allocation functions 1091 (normally sbrk) outside of malloc. 1092 1093 malloc_stats prints only the most commonly interesting statistics. 1094 More information can be obtained by calling mallinfo. 1095*/ 1096void dlmalloc_stats(void); 1097 1098#endif /* ONLY_MSPACES */ 1099 1100/* 1101 malloc_usable_size(void* p); 1102 1103 Returns the number of bytes you can actually use in 1104 an allocated chunk, which may be more than you requested (although 1105 often not) due to alignment and minimum size constraints. 1106 You can use this many bytes without worrying about 1107 overwriting other allocated objects. This is not a particularly great 1108 programming practice. malloc_usable_size can be more useful in 1109 debugging and assertions, for example: 1110 1111 p = malloc(n); 1112 assert(malloc_usable_size(p) >= 256); 1113*/ 1114size_t dlmalloc_usable_size(void*); 1115 1116 1117#if MSPACES 1118 1119/* 1120 mspace is an opaque type representing an independent 1121 region of space that supports mspace_malloc, etc. 1122*/ 1123typedef void* mspace; 1124 1125/* 1126 create_mspace creates and returns a new independent space with the 1127 given initial capacity, or, if 0, the default granularity size. It 1128 returns null if there is no system memory available to create the 1129 space. If argument locked is non-zero, the space uses a separate 1130 lock to control access. The capacity of the space will grow 1131 dynamically as needed to service mspace_malloc requests. You can 1132 control the sizes of incremental increases of this space by 1133 compiling with a different DEFAULT_GRANULARITY or dynamically 1134 setting with mallopt(M_GRANULARITY, value). 1135*/ 1136mspace create_mspace(size_t capacity, int locked); 1137 1138/* 1139 destroy_mspace destroys the given space, and attempts to return all 1140 of its memory back to the system, returning the total number of 1141 bytes freed. After destruction, the results of access to all memory 1142 used by the space become undefined. 1143*/ 1144size_t destroy_mspace(mspace msp); 1145 1146/* 1147 create_mspace_with_base uses the memory supplied as the initial base 1148 of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this 1149 space is used for bookkeeping, so the capacity must be at least this 1150 large. (Otherwise 0 is returned.) When this initial space is 1151 exhausted, additional memory will be obtained from the system. 1152 Destroying this space will deallocate all additionally allocated 1153 space (if possible) but not the initial base. 1154*/ 1155mspace create_mspace_with_base(void* base, size_t capacity, int locked); 1156 1157/* 1158 mspace_track_large_chunks controls whether requests for large chunks 1159 are allocated in their own untracked mmapped regions, separate from 1160 others in this mspace. By default large chunks are not tracked, 1161 which reduces fragmentation. However, such chunks are not 1162 necessarily released to the system upon destroy_mspace. Enabling 1163 tracking by setting to true may increase fragmentation, but avoids 1164 leakage when relying on destroy_mspace to release all memory 1165 allocated using this space. The function returns the previous 1166 setting. 1167*/ 1168int mspace_track_large_chunks(mspace msp, int enable); 1169 1170 1171/* 1172 mspace_malloc behaves as malloc, but operates within 1173 the given space. 1174*/ 1175void* mspace_malloc(mspace msp, size_t bytes); 1176 1177/* 1178 mspace_free behaves as free, but operates within 1179 the given space. 1180 1181 If compiled with FOOTERS==1, mspace_free is not actually needed. 1182 free may be called instead of mspace_free because freed chunks from 1183 any space are handled by their originating spaces. 1184*/ 1185void mspace_free(mspace msp, void* mem); 1186 1187/* 1188 mspace_realloc behaves as realloc, but operates within 1189 the given space. 1190 1191 If compiled with FOOTERS==1, mspace_realloc is not actually 1192 needed. realloc may be called instead of mspace_realloc because 1193 realloced chunks from any space are handled by their originating 1194 spaces. 1195*/ 1196void* mspace_realloc(mspace msp, void* mem, size_t newsize); 1197 1198/* 1199 mspace_calloc behaves as calloc, but operates within 1200 the given space. 1201*/ 1202void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size); 1203 1204/* 1205 mspace_memalign behaves as memalign, but operates within 1206 the given space. 1207*/ 1208void* mspace_memalign(mspace msp, size_t alignment, size_t bytes); 1209 1210/* 1211 mspace_independent_calloc behaves as independent_calloc, but 1212 operates within the given space. 1213*/ 1214void** mspace_independent_calloc(mspace msp, size_t n_elements, 1215 size_t elem_size, void* chunks[]); 1216 1217/* 1218 mspace_independent_comalloc behaves as independent_comalloc, but 1219 operates within the given space. 1220*/ 1221void** mspace_independent_comalloc(mspace msp, size_t n_elements, 1222 size_t sizes[], void* chunks[]); 1223 1224/* 1225 mspace_footprint() returns the number of bytes obtained from the 1226 system for this space. 1227*/ 1228size_t mspace_footprint(mspace msp); 1229 1230/* 1231 mspace_max_footprint() returns the peak number of bytes obtained from the 1232 system for this space. 1233*/ 1234size_t mspace_max_footprint(mspace msp); 1235 1236 1237#if !NO_MALLINFO 1238/* 1239 mspace_mallinfo behaves as mallinfo, but reports properties of 1240 the given space. 1241*/ 1242struct mallinfo mspace_mallinfo(mspace msp); 1243#endif /* NO_MALLINFO */ 1244 1245/* 1246 malloc_usable_size(void* p) behaves the same as malloc_usable_size; 1247*/ 1248 size_t mspace_usable_size(void* mem); 1249 1250/* 1251 mspace_malloc_stats behaves as malloc_stats, but reports 1252 properties of the given space. 1253*/ 1254void mspace_malloc_stats(mspace msp); 1255 1256/* 1257 mspace_trim behaves as malloc_trim, but 1258 operates within the given space. 1259*/ 1260int mspace_trim(mspace msp, size_t pad); 1261 1262/* 1263 An alias for mallopt. 1264*/ 1265int mspace_mallopt(int, int); 1266 1267#endif /* MSPACES */ 1268 1269#ifdef __cplusplus 1270} /* end of extern "C" */ 1271#endif /* __cplusplus */ 1272 1273/* 1274 ======================================================================== 1275 To make a fully customizable malloc.h header file, cut everything 1276 above this line, put into file malloc.h, edit to suit, and #include it 1277 on the next line, as well as in programs that use this malloc. 1278 ======================================================================== 1279*/ 1280 1281/* #include "malloc.h" */ 1282 1283/*------------------------------ internal #includes ---------------------- */ 1284 1285#ifdef WIN32 1286#pragma warning( disable : 4146 ) /* no "unsigned" warnings */ 1287#endif /* WIN32 */ 1288 1289#include <stdio.h> /* for printing in malloc_stats */ 1290 1291#ifndef LACKS_ERRNO_H 1292#include <errno.h> /* for MALLOC_FAILURE_ACTION */ 1293#endif /* LACKS_ERRNO_H */ 1294/*#if FOOTERS || DEBUG 1295*/ 1296#include <time.h> /* for magic initialization */ 1297/*#endif*/ /* FOOTERS */ 1298#ifndef LACKS_STDLIB_H 1299#include <stdlib.h> /* for abort() */ 1300#endif /* LACKS_STDLIB_H */ 1301#ifdef DEBUG 1302#if ABORT_ON_ASSERT_FAILURE 1303#undef assert 1304#define assert(x) if(!(x)) ABORT 1305#else /* ABORT_ON_ASSERT_FAILURE */ 1306#include <assert.h> 1307#endif /* ABORT_ON_ASSERT_FAILURE */ 1308#else /* DEBUG */ 1309#ifndef assert 1310#define assert(x) 1311#endif 1312#define DEBUG 0 1313#endif /* DEBUG */ 1314#ifndef LACKS_STRING_H 1315#include <string.h> /* for memset etc */ 1316#endif /* LACKS_STRING_H */ 1317#if USE_BUILTIN_FFS 1318#ifndef LACKS_STRINGS_H 1319#include <strings.h> /* for ffs */ 1320#endif /* LACKS_STRINGS_H */ 1321#endif /* USE_BUILTIN_FFS */ 1322#if HAVE_MMAP 1323#ifndef LACKS_SYS_MMAN_H 1324/* On some versions of linux, mremap decl in mman.h needs __USE_GNU set */ 1325#if (defined(linux) && !defined(__USE_GNU)) 1326#define __USE_GNU 1 1327#include <sys/mman.h> /* for mmap */ 1328#undef __USE_GNU 1329#else 1330#include <sys/mman.h> /* for mmap */ 1331#endif /* linux */ 1332#endif /* LACKS_SYS_MMAN_H */ 1333#ifndef LACKS_FCNTL_H 1334#include <fcntl.h> 1335#endif /* LACKS_FCNTL_H */ 1336#endif /* HAVE_MMAP */ 1337#ifndef LACKS_UNISTD_H 1338#include <unistd.h> /* for sbrk, sysconf */ 1339#else /* LACKS_UNISTD_H */ 1340#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__) 1341extern void* sbrk(ptrdiff_t); 1342#endif /* FreeBSD etc */ 1343#endif /* LACKS_UNISTD_H */ 1344 1345/* Declarations for locking */ 1346#if USE_LOCKS 1347#ifndef WIN32 1348#include <pthread.h> 1349#if defined (__SVR4) && defined (__sun) /* solaris */ 1350#include <thread.h> 1351#endif /* solaris */ 1352#else 1353#ifndef _M_AMD64 1354/* These are already defined on AMD64 builds */ 1355#ifdef __cplusplus 1356extern "C" { 1357#endif /* __cplusplus */ 1358LONG __cdecl _InterlockedCompareExchange(LONG volatile *Dest, LONG Exchange, LONG Comp); 1359LONG __cdecl _InterlockedExchange(LONG volatile *Target, LONG Value); 1360#ifdef __cplusplus 1361} 1362#endif /* __cplusplus */ 1363#endif /* _M_AMD64 */ 1364#pragma intrinsic (_InterlockedCompareExchange) 1365#pragma intrinsic (_InterlockedExchange) 1366#define interlockedcompareexchange _InterlockedCompareExchange 1367#define interlockedexchange _InterlockedExchange 1368#endif /* Win32 */ 1369#endif /* USE_LOCKS */ 1370 1371/* Declarations for bit scanning on win32 */ 1372#if defined(_MSC_VER) && _MSC_VER>=1300 1373#ifndef BitScanForward /* Try to avoid pulling in WinNT.h */ 1374#ifdef __cplusplus 1375extern "C" { 1376#endif /* __cplusplus */ 1377unsigned char _BitScanForward(unsigned long *index, unsigned long mask); 1378unsigned char _BitScanReverse(unsigned long *index, unsigned long mask); 1379#ifdef __cplusplus 1380} 1381#endif /* __cplusplus */ 1382 1383#define BitScanForward _BitScanForward 1384#define BitScanReverse _BitScanReverse 1385#pragma intrinsic(_BitScanForward) 1386#pragma intrinsic(_BitScanReverse) 1387#endif /* BitScanForward */ 1388#endif /* defined(_MSC_VER) && _MSC_VER>=1300 */ 1389 1390#ifndef WIN32 1391#ifndef malloc_getpagesize 1392# ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */ 1393# ifndef _SC_PAGE_SIZE 1394# define _SC_PAGE_SIZE _SC_PAGESIZE 1395# endif 1396# endif 1397# ifdef _SC_PAGE_SIZE 1398# define malloc_getpagesize sysconf(_SC_PAGE_SIZE) 1399# else 1400# if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE) 1401 extern size_t getpagesize(); 1402# define malloc_getpagesize getpagesize() 1403# else 1404# ifdef WIN32 /* use supplied emulation of getpagesize */ 1405# define malloc_getpagesize getpagesize() 1406# else 1407# ifndef LACKS_SYS_PARAM_H 1408# include <sys/param.h> 1409# endif 1410# ifdef EXEC_PAGESIZE 1411# define malloc_getpagesize EXEC_PAGESIZE 1412# else 1413# ifdef NBPG 1414# ifndef CLSIZE 1415# define malloc_getpagesize NBPG 1416# else 1417# define malloc_getpagesize (NBPG * CLSIZE) 1418# endif 1419# else 1420# ifdef NBPC 1421# define malloc_getpagesize NBPC 1422# else 1423# ifdef PAGESIZE 1424# define malloc_getpagesize PAGESIZE 1425# else /* just guess */ 1426# define malloc_getpagesize ((size_t)4096U) 1427# endif 1428# endif 1429# endif 1430# endif 1431# endif 1432# endif 1433# endif 1434#endif 1435#endif 1436 1437 1438 1439/* ------------------- size_t and alignment properties -------------------- */ 1440 1441/* The byte and bit size of a size_t */ 1442#define SIZE_T_SIZE (sizeof(size_t)) 1443#define SIZE_T_BITSIZE (sizeof(size_t) << 3) 1444 1445/* Some constants coerced to size_t */ 1446/* Annoying but necessary to avoid errors on some platforms */ 1447#define SIZE_T_ZERO ((size_t)0) 1448#define SIZE_T_ONE ((size_t)1) 1449#define SIZE_T_TWO ((size_t)2) 1450#define SIZE_T_FOUR ((size_t)4) 1451#define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1) 1452#define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2) 1453#define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES) 1454#define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U) 1455 1456/* The bit mask value corresponding to MALLOC_ALIGNMENT */ 1457#define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE) 1458 1459/* True if address a has acceptable alignment */ 1460#define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0) 1461 1462/* the number of bytes to offset an address to align it */ 1463#define align_offset(A)\ 1464 ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\ 1465 ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK)) 1466 1467/* -------------------------- MMAP preliminaries ------------------------- */ 1468 1469/* 1470 If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and 1471 checks to fail so compiler optimizer can delete code rather than 1472 using so many "#if"s. 1473*/ 1474 1475 1476/* MORECORE and MMAP must return MFAIL on failure */ 1477#define MFAIL ((void*)(MAX_SIZE_T)) 1478#define CMFAIL ((char*)(MFAIL)) /* defined for convenience */ 1479 1480#if HAVE_MMAP 1481 1482#ifndef WIN32 1483#define MUNMAP_DEFAULT(a, s) munmap((a), (s)) 1484#define MMAP_PROT (PROT_READ|PROT_WRITE) 1485#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON) 1486#define MAP_ANONYMOUS MAP_ANON 1487#endif /* MAP_ANON */ 1488#ifdef MAP_ANONYMOUS 1489#define MMAP_FLAGS (MAP_PRIVATE|MAP_ANONYMOUS) 1490#define MMAP_DEFAULT(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0) 1491#else /* MAP_ANONYMOUS */ 1492/* 1493 Nearly all versions of mmap support MAP_ANONYMOUS, so the following 1494 is unlikely to be needed, but is supplied just in case. 1495*/ 1496#define MMAP_FLAGS (MAP_PRIVATE) 1497static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */ 1498#define MMAP_DEFAULT(s) ((dev_zero_fd < 0) ? \ 1499 (dev_zero_fd = open("/dev/zero", O_RDWR), \ 1500 mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \ 1501 mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) 1502#endif /* MAP_ANONYMOUS */ 1503 1504#define DIRECT_MMAP_DEFAULT(s) MMAP_DEFAULT(s) 1505 1506#else /* WIN32 */ 1507 1508/* Win32 MMAP via VirtualAlloc */ 1509static FORCEINLINE void* win32mmap(size_t size) { 1510 void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE); 1511 return (ptr != 0)? ptr: MFAIL; 1512} 1513 1514/* For direct MMAP, use MEM_TOP_DOWN to minimize interference */ 1515static FORCEINLINE void* win32direct_mmap(size_t size) { 1516 void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN, 1517 PAGE_READWRITE); 1518 return (ptr != 0)? ptr: MFAIL; 1519} 1520 1521/* This function supports releasing coalesed segments */ 1522static FORCEINLINE int win32munmap(void* ptr, size_t size) { 1523 MEMORY_BASIC_INFORMATION minfo; 1524 char* cptr = (char*)ptr; 1525 while (size) { 1526 if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0) 1527 return -1; 1528 if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr || 1529 minfo.State != MEM_COMMIT || minfo.RegionSize > size) 1530 return -1; 1531 if (VirtualFree(cptr, 0, MEM_RELEASE) == 0) 1532 return -1; 1533 cptr += minfo.RegionSize; 1534 size -= minfo.RegionSize; 1535 } 1536 return 0; 1537} 1538 1539#define MMAP_DEFAULT(s) win32mmap(s) 1540#define MUNMAP_DEFAULT(a, s) win32munmap((a), (s)) 1541#define DIRECT_MMAP_DEFAULT(s) win32direct_mmap(s) 1542#endif /* WIN32 */ 1543#endif /* HAVE_MMAP */ 1544 1545#if HAVE_MREMAP 1546#ifndef WIN32 1547#define MREMAP_DEFAULT(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv)) 1548#endif /* WIN32 */ 1549#endif /* HAVE_MREMAP */ 1550 1551 1552/** 1553 * Define CALL_MORECORE 1554 */ 1555#if HAVE_MORECORE 1556 #ifdef MORECORE 1557 #define CALL_MORECORE(S) MORECORE(S) 1558 #else /* MORECORE */ 1559 #define CALL_MORECORE(S) MORECORE_DEFAULT(S) 1560 #endif /* MORECORE */ 1561#else /* HAVE_MORECORE */ 1562 #define CALL_MORECORE(S) MFAIL 1563#endif /* HAVE_MORECORE */ 1564 1565/** 1566 * Define CALL_MMAP/CALL_MUNMAP/CALL_DIRECT_MMAP 1567 */ 1568#if HAVE_MMAP 1569 #define USE_MMAP_BIT (SIZE_T_ONE) 1570 1571 #ifdef MMAP 1572 #define CALL_MMAP(s) MMAP(s) 1573 #else /* MMAP */ 1574 #define CALL_MMAP(s) MMAP_DEFAULT(s) 1575 #endif /* MMAP */ 1576 #ifdef MUNMAP 1577 #define CALL_MUNMAP(a, s) MUNMAP((a), (s)) 1578 #else /* MUNMAP */ 1579 #define CALL_MUNMAP(a, s) MUNMAP_DEFAULT((a), (s)) 1580 #endif /* MUNMAP */ 1581 #ifdef DIRECT_MMAP 1582 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s) 1583 #else /* DIRECT_MMAP */ 1584 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP_DEFAULT(s) 1585 #endif /* DIRECT_MMAP */ 1586#else /* HAVE_MMAP */ 1587 #define USE_MMAP_BIT (SIZE_T_ZERO) 1588 1589 #define MMAP(s) MFAIL 1590 #define MUNMAP(a, s) (-1) 1591 #define DIRECT_MMAP(s) MFAIL 1592 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s) 1593 #define CALL_MMAP(s) MMAP(s) 1594 #define CALL_MUNMAP(a, s) MUNMAP((a), (s)) 1595#endif /* HAVE_MMAP */ 1596 1597/** 1598 * Define CALL_MREMAP 1599 */ 1600#if HAVE_MMAP && HAVE_MREMAP 1601 #ifdef MREMAP 1602 #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP((addr), (osz), (nsz), (mv)) 1603 #else /* MREMAP */ 1604 #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP_DEFAULT((addr), (osz), (nsz), (mv)) 1605 #endif /* MREMAP */ 1606#else /* HAVE_MMAP && HAVE_MREMAP */ 1607 #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL 1608#endif /* HAVE_MMAP && HAVE_MREMAP */ 1609 1610/* mstate bit set if continguous morecore disabled or failed */ 1611#define USE_NONCONTIGUOUS_BIT (4U) 1612 1613/* segment bit set in create_mspace_with_base */ 1614#define EXTERN_BIT (8U) 1615 1616 1617/* --------------------------- Lock preliminaries ------------------------ */ 1618 1619/* 1620 When locks are defined, there is one global lock, plus 1621 one per-mspace lock. 1622 1623 The global lock_ensures that mparams.magic and other unique 1624 mparams values are initialized only once. It also protects 1625 sequences of calls to MORECORE. In many cases sys_alloc requires 1626 two calls, that should not be interleaved with calls by other 1627 threads. This does not protect against direct calls to MORECORE 1628 by other threads not using this lock, so there is still code to 1629 cope the best we can on interference. 1630 1631 Per-mspace locks surround calls to malloc, free, etc. To enable use 1632 in layered extensions, per-mspace locks are reentrant. 1633 1634 Because lock-protected regions generally have bounded times, it is 1635 OK to use the supplied simple spinlocks in the custom versions for 1636 x86. Spinlocks are likely to improve performance for lightly 1637 contended applications, but worsen performance under heavy 1638 contention. 1639 1640 If USE_LOCKS is > 1, the definitions of lock routines here are 1641 bypassed, in which case you will need to define the type MLOCK_T, 1642 and at least INITIAL_LOCK, ACQUIRE_LOCK, RELEASE_LOCK and possibly 1643 TRY_LOCK (which is not used in this malloc, but commonly needed in 1644 extensions.) You must also declare a 1645 static MLOCK_T malloc_global_mutex = { initialization values };. 1646 1647*/ 1648 1649#if USE_LOCKS == 1 1650 1651#if USE_SPIN_LOCKS && SPIN_LOCKS_AVAILABLE 1652#ifndef WIN32 1653 1654/* Custom pthread-style spin locks on x86 and x64 for gcc */ 1655struct pthread_mlock_t { 1656 volatile unsigned int l; 1657 unsigned int c; 1658 pthread_t threadid; 1659}; 1660#define MLOCK_T struct pthread_mlock_t 1661#define CURRENT_THREAD pthread_self() 1662#define INITIAL_LOCK(sl) ((sl)->threadid = 0, (sl)->l = (sl)->c = 0, 0) 1663#define ACQUIRE_LOCK(sl) pthread_acquire_lock(sl) 1664#define RELEASE_LOCK(sl) pthread_release_lock(sl) 1665#define TRY_LOCK(sl) pthread_try_lock(sl) 1666#define SPINS_PER_YIELD 63 1667 1668static MLOCK_T malloc_global_mutex = { 0, 0, 0}; 1669 1670static FORCEINLINE int pthread_acquire_lock (MLOCK_T *sl) { 1671 int spins = 0; 1672 volatile unsigned int* lp = &sl->l; 1673 for (;;) { 1674 if (*lp != 0) { 1675 if (sl->threadid == CURRENT_THREAD) { 1676 ++sl->c; 1677 return 0; 1678 } 1679 } 1680 else { 1681 /* place args to cmpxchgl in locals to evade oddities in some gccs */ 1682 int cmp = 0; 1683 int val = 1; 1684 int ret; 1685 __asm__ __volatile__ ("lock; cmpxchgl %1, %2" 1686 : "=a" (ret) 1687 : "r" (val), "m" (*(lp)), "0"(cmp) 1688 : "memory", "cc"); 1689 if (!ret) { 1690 assert(!sl->threadid); 1691 sl->threadid = CURRENT_THREAD; 1692 sl->c = 1; 1693 return 0; 1694 } 1695 } 1696 if ((++spins & SPINS_PER_YIELD) == 0) { 1697#if defined (__SVR4) && defined (__sun) /* solaris */ 1698 thr_yield(); 1699#else 1700#if defined(__linux__) || defined(__FreeBSD__) || defined(__APPLE__) 1701 sched_yield(); 1702#else /* no-op yield on unknown systems */ 1703 ; 1704#endif /* __linux__ || __FreeBSD__ || __APPLE__ */ 1705#endif /* solaris */ 1706 } 1707 } 1708} 1709 1710static FORCEINLINE void pthread_release_lock (MLOCK_T *sl) { 1711 volatile unsigned int* lp = &sl->l; 1712 assert(*lp != 0); 1713 assert(sl->threadid == CURRENT_THREAD); 1714 if (--sl->c == 0) { 1715 sl->threadid = 0; 1716 int prev = 0; 1717 int ret; 1718 __asm__ __volatile__ ("lock; xchgl %0, %1" 1719 : "=r" (ret) 1720 : "m" (*(lp)), "0"(prev) 1721 : "memory"); 1722 } 1723} 1724 1725static FORCEINLINE int pthread_try_lock (MLOCK_T *sl) { 1726 volatile unsigned int* lp = &sl->l; 1727 if (*lp != 0) { 1728 if (sl->threadid == CURRENT_THREAD) { 1729 ++sl->c; 1730 return 1; 1731 } 1732 } 1733 else { 1734 int cmp = 0; 1735 int val = 1; 1736 int ret; 1737 __asm__ __volatile__ ("lock; cmpxchgl %1, %2" 1738 : "=a" (ret) 1739 : "r" (val), "m" (*(lp)), "0"(cmp) 1740 : "memory", "cc"); 1741 if (!ret) { 1742 assert(!sl->threadid); 1743 sl->threadid = CURRENT_THREAD; 1744 sl->c = 1; 1745 return 1; 1746 } 1747 } 1748 return 0; 1749} 1750 1751 1752#else /* WIN32 */ 1753/* Custom win32-style spin locks on x86 and x64 for MSC */ 1754struct win32_mlock_t { 1755 volatile long l; 1756 unsigned int c; 1757 long threadid; 1758}; 1759 1760#define MLOCK_T struct win32_mlock_t 1761#define CURRENT_THREAD GetCurrentThreadId() 1762#define INITIAL_LOCK(sl) ((sl)->threadid = 0, (sl)->l = (sl)->c = 0, 0) 1763#define ACQUIRE_LOCK(sl) win32_acquire_lock(sl) 1764#define RELEASE_LOCK(sl) win32_release_lock(sl) 1765#define TRY_LOCK(sl) win32_try_lock(sl) 1766#define SPINS_PER_YIELD 63 1767 1768static MLOCK_T malloc_global_mutex = { 0, 0, 0}; 1769 1770static FORCEINLINE int win32_acquire_lock (MLOCK_T *sl) { 1771 int spins = 0; 1772 for (;;) { 1773 if (sl->l != 0) { 1774 if (sl->threadid == CURRENT_THREAD) { 1775 ++sl->c; 1776 return 0; 1777 } 1778 } 1779 else { 1780 if (!interlockedexchange(&sl->l, 1)) { 1781 assert(!sl->threadid); 1782 sl->threadid = CURRENT_THREAD; 1783 sl->c = 1; 1784 return 0; 1785 } 1786 } 1787 if ((++spins & SPINS_PER_YIELD) == 0) 1788 SleepEx(0, FALSE); 1789 } 1790} 1791 1792static FORCEINLINE void win32_release_lock (MLOCK_T *sl) { 1793 assert(sl->threadid == CURRENT_THREAD); 1794 assert(sl->l != 0); 1795 if (--sl->c == 0) { 1796 sl->threadid = 0; 1797 interlockedexchange (&sl->l, 0); 1798 } 1799} 1800 1801static FORCEINLINE int win32_try_lock (MLOCK_T *sl) { 1802 if (sl->l != 0) { 1803 if (sl->threadid == CURRENT_THREAD) { 1804 ++sl->c; 1805 return 1; 1806 } 1807 } 1808 else { 1809 if (!interlockedexchange(&sl->l, 1)){ 1810 assert(!sl->threadid); 1811 sl->threadid = CURRENT_THREAD; 1812 sl->c = 1; 1813 return 1; 1814 } 1815 } 1816 return 0; 1817} 1818 1819#endif /* WIN32 */ 1820#else /* USE_SPIN_LOCKS */ 1821 1822#ifndef WIN32 1823/* pthreads-based locks */ 1824 1825#define MLOCK_T pthread_mutex_t 1826#define CURRENT_THREAD pthread_self() 1827#define INITIAL_LOCK(sl) pthread_init_lock(sl) 1828#define ACQUIRE_LOCK(sl) pthread_mutex_lock(sl) 1829#define RELEASE_LOCK(sl) pthread_mutex_unlock(sl) 1830#define TRY_LOCK(sl) (!pthread_mutex_trylock(sl)) 1831 1832static MLOCK_T malloc_global_mutex = PTHREAD_MUTEX_INITIALIZER; 1833 1834/* Cope with old-style linux recursive lock initialization by adding */ 1835/* skipped internal declaration from pthread.h */ 1836#ifdef linux 1837#ifndef PTHREAD_MUTEX_RECURSIVE 1838extern int pthread_mutexattr_setkind_np __P ((pthread_mutexattr_t *__attr, 1839 int __kind)); 1840#define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP 1841#define pthread_mutexattr_settype(x,y) pthread_mutexattr_setkind_np(x,y) 1842#endif 1843#endif 1844 1845static int pthread_init_lock (MLOCK_T *sl) { 1846 pthread_mutexattr_t attr; 1847 if (pthread_mutexattr_init(&attr)) return 1; 1848 if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1; 1849 if (pthread_mutex_init(sl, &attr)) return 1; 1850 if (pthread_mutexattr_destroy(&attr)) return 1; 1851 return 0; 1852} 1853 1854#else /* WIN32 */ 1855/* Win32 critical sections */ 1856#define MLOCK_T CRITICAL_SECTION 1857#define CURRENT_THREAD GetCurrentThreadId() 1858#define INITIAL_LOCK(s) (!InitializeCriticalSectionAndSpinCount((s), 0x80000000|4000)) 1859#define ACQUIRE_LOCK(s) (EnterCriticalSection(sl), 0) 1860#define RELEASE_LOCK(s) LeaveCriticalSection(sl) 1861#define TRY_LOCK(s) TryEnterCriticalSection(sl) 1862#define NEED_GLOBAL_LOCK_INIT 1863 1864static MLOCK_T malloc_global_mutex; 1865static volatile long malloc_global_mutex_status; 1866 1867/* Use spin loop to initialize global lock */ 1868static void init_malloc_global_mutex() { 1869 for (;;) { 1870 long stat = malloc_global_mutex_status; 1871 if (stat > 0) 1872 return; 1873 /* transition to < 0 while initializing, then to > 0) */ 1874 if (stat == 0 && 1875 interlockedcompareexchange(&malloc_global_mutex_status, -1, 0) == 0) { 1876 InitializeCriticalSection(&malloc_global_mutex); 1877 interlockedexchange(&malloc_global_mutex_status,1); 1878 return; 1879 } 1880 SleepEx(0, FALSE); 1881 } 1882} 1883 1884#endif /* WIN32 */ 1885#endif /* USE_SPIN_LOCKS */ 1886#endif /* USE_LOCKS == 1 */ 1887 1888/* ----------------------- User-defined locks ------------------------ */ 1889 1890#if USE_LOCKS > 1 1891/* Define your own lock implementation here */ 1892/* #define INITIAL_LOCK(sl) ... */ 1893/* #define ACQUIRE_LOCK(sl) ... */ 1894/* #define RELEASE_LOCK(sl) ... */ 1895/* #define TRY_LOCK(sl) ... */ 1896/* static MLOCK_T malloc_global_mutex = ... */ 1897#endif /* USE_LOCKS > 1 */ 1898 1899/* ----------------------- Lock-based state ------------------------ */ 1900 1901#if USE_LOCKS 1902#define USE_LOCK_BIT (2U) 1903#else /* USE_LOCKS */ 1904#define USE_LOCK_BIT (0U) 1905#define INITIAL_LOCK(l) 1906#endif /* USE_LOCKS */ 1907 1908#if USE_LOCKS 1909#ifndef ACQUIRE_MALLOC_GLOBAL_LOCK 1910#define ACQUIRE_MALLOC_GLOBAL_LOCK() ACQUIRE_LOCK(&malloc_global_mutex); 1911#endif 1912#ifndef RELEASE_MALLOC_GLOBAL_LOCK 1913#define RELEASE_MALLOC_GLOBAL_LOCK() RELEASE_LOCK(&malloc_global_mutex); 1914#endif 1915#else /* USE_LOCKS */ 1916#define ACQUIRE_MALLOC_GLOBAL_LOCK() 1917#define RELEASE_MALLOC_GLOBAL_LOCK() 1918#endif /* USE_LOCKS */ 1919 1920 1921/* ----------------------- Chunk representations ------------------------ */ 1922 1923/* 1924 (The following includes lightly edited explanations by Colin Plumb.) 1925 1926 The malloc_chunk declaration below is misleading (but accurate and 1927 necessary). It declares a "view" into memory allowing access to 1928 necessary fields at known offsets from a given base. 1929 1930 Chunks of memory are maintained using a `boundary tag' method as 1931 originally described by Knuth. (See the paper by Paul Wilson 1932 ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such 1933 techniques.) Sizes of free chunks are stored both in the front of 1934 each chunk and at the end. This makes consolidating fragmented 1935 chunks into bigger chunks fast. The head fields also hold bits 1936 representing whether chunks are free or in use. 1937 1938 Here are some pictures to make it clearer. They are "exploded" to 1939 show that the state of a chunk can be thought of as extending from 1940 the high 31 bits of the head field of its header through the 1941 prev_foot and PINUSE_BIT bit of the following chunk header. 1942 1943 A chunk that's in use looks like: 1944 1945 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1946 | Size of previous chunk (if P = 0) | 1947 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1948 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P| 1949 | Size of this chunk 1| +-+ 1950 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1951 | | 1952 +- -+ 1953 | | 1954 +- -+ 1955 | : 1956 +- size - sizeof(size_t) available payload bytes -+ 1957 : | 1958 chunk-> +- -+ 1959 | | 1960 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1961 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1| 1962 | Size of next chunk (may or may not be in use) | +-+ 1963 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1964 1965 And if it's free, it looks like this: 1966 1967 chunk-> +- -+ 1968 | User payload (must be in use, or we would have merged!) | 1969 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1970 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P| 1971 | Size of this chunk 0| +-+ 1972 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1973 | Next pointer | 1974 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1975 | Prev pointer | 1976 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1977 | : 1978 +- size - sizeof(struct chunk) unused bytes -+ 1979 : | 1980 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1981 | Size of this chunk | 1982 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1983 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| 1984 | Size of next chunk (must be in use, or we would have merged)| +-+ 1985 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1986 | : 1987 +- User payload -+ 1988 : | 1989 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1990 |0| 1991 +-+ 1992 Note that since we always merge adjacent free chunks, the chunks 1993 adjacent to a free chunk must be in use. 1994 1995 Given a pointer to a chunk (which can be derived trivially from the 1996 payload pointer) we can, in O(1) time, find out whether the adjacent 1997 chunks are free, and if so, unlink them from the lists that they 1998 are on and merge them with the current chunk. 1999 2000 Chunks always begin on even word boundaries, so the mem portion 2001 (which is returned to the user) is also on an even word boundary, and 2002 thus at least double-word aligned. 2003 2004 The P (PINUSE_BIT) bit, stored in the unused low-order bit of the 2005 chunk size (which is always a multiple of two words), is an in-use 2006 bit for the *previous* chunk. If that bit is *clear*, then the 2007 word before the current chunk size contains the previous chunk 2008 size, and can be used to find the front of the previous chunk. 2009 The very first chunk allocated always has this bit set, preventing 2010 access to non-existent (or non-owned) memory. If pinuse is set for 2011 any given chunk, then you CANNOT determine the size of the 2012 previous chunk, and might even get a memory addressing fault when 2013 trying to do so. 2014 2015 The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of 2016 the chunk size redundantly records whether the current chunk is 2017 inuse (unless the chunk is mmapped). This redundancy enables usage 2018 checks within free and realloc, and reduces indirection when freeing 2019 and consolidating chunks. 2020 2021 Each freshly allocated chunk must have both cinuse and pinuse set. 2022 That is, each allocated chunk borders either a previously allocated 2023 and still in-use chunk, or the base of its memory arena. This is 2024 ensured by making all allocations from the the `lowest' part of any 2025 found chunk. Further, no free chunk physically borders another one, 2026 so each free chunk is known to be preceded and followed by either 2027 inuse chunks or the ends of memory. 2028 2029 Note that the `foot' of the current chunk is actually represented 2030 as the prev_foot of the NEXT chunk. This makes it easier to 2031 deal with alignments etc but can be very confusing when trying 2032 to extend or adapt this code. 2033 2034 The exceptions to all this are 2035 2036 1. The special chunk `top' is the top-most available chunk (i.e., 2037 the one bordering the end of available memory). It is treated 2038 specially. Top is never included in any bin, is used only if 2039 no other chunk is available, and is released back to the 2040 system if it is very large (see M_TRIM_THRESHOLD). In effect, 2041 the top chunk is treated as larger (and thus less well 2042 fitting) than any other available chunk. The top chunk 2043 doesn't update its trailing size field since there is no next 2044 contiguous chunk that would have to index off it. However, 2045 space is still allocated for it (TOP_FOOT_SIZE) to enable 2046 separation or merging when space is extended. 2047 2048 3. Chunks allocated via mmap, have both cinuse and pinuse bits 2049 cleared in their head fields. Because they are allocated 2050 one-by-one, each must carry its own prev_foot field, which is 2051 also used to hold the offset this chunk has within its mmapped 2052 region, which is needed to preserve alignment. Each mmapped 2053 chunk is trailed by the first two fields of a fake next-chunk 2054 for sake of usage checks. 2055 2056*/ 2057 2058struct malloc_chunk { 2059 size_t prev_foot; /* Size of previous chunk (if free). */ 2060 size_t head; /* Size and inuse bits. */ 2061 struct malloc_chunk* fd; /* double links -- used only if free. */ 2062 struct malloc_chunk* bk; 2063}; 2064 2065typedef struct malloc_chunk mchunk; 2066typedef struct malloc_chunk* mchunkptr; 2067typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */ 2068typedef unsigned int bindex_t; /* Described below */ 2069typedef unsigned int binmap_t; /* Described below */ 2070typedef unsigned int flag_t; /* The type of various bit flag sets */ 2071 2072/* ------------------- Chunks sizes and alignments ----------------------- */ 2073 2074#define MCHUNK_SIZE (sizeof(mchunk)) 2075 2076#if FOOTERS 2077#define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES) 2078#else /* FOOTERS */ 2079#define CHUNK_OVERHEAD (SIZE_T_SIZE) 2080#endif /* FOOTERS */ 2081 2082/* MMapped chunks need a second word of overhead ... */ 2083#define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES) 2084/* ... and additional padding for fake next-chunk at foot */ 2085#define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES) 2086 2087/* The smallest size we can malloc is an aligned minimal chunk */ 2088#define MIN_CHUNK_SIZE\ 2089 ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK) 2090 2091/* conversion from malloc headers to user pointers, and back */ 2092#define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES)) 2093#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES)) 2094/* chunk associated with aligned address A */ 2095#define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A))) 2096 2097/* Bounds on request (not chunk) sizes. */ 2098#define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2) 2099#define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE) 2100 2101/* pad request bytes into a usable size */ 2102#define pad_request(req) \ 2103 (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK) 2104 2105/* pad request, checking for minimum (but not maximum) */ 2106#define request2size(req) \ 2107 (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req)) 2108 2109 2110/* ------------------ Operations on head and foot fields ----------------- */ 2111 2112/* 2113 The head field of a chunk is or'ed with PINUSE_BIT when previous 2114 adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in 2115 use, unless mmapped, in which case both bits are cleared. 2116 2117 FLAG4_BIT is not used by this malloc, but might be useful in extensions. 2118*/ 2119 2120#define PINUSE_BIT (SIZE_T_ONE) 2121#define CINUSE_BIT (SIZE_T_TWO) 2122#define FLAG4_BIT (SIZE_T_FOUR) 2123#define INUSE_BITS (PINUSE_BIT|CINUSE_BIT) 2124#define FLAG_BITS (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT) 2125 2126/* Head value for fenceposts */ 2127#define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE) 2128 2129/* extraction of fields from head words */ 2130#define cinuse(p) ((p)->head & CINUSE_BIT) 2131#define pinuse(p) ((p)->head & PINUSE_BIT) 2132#define is_inuse(p) (((p)->head & INUSE_BITS) != PINUSE_BIT) 2133#define is_mmapped(p) (((p)->head & INUSE_BITS) == 0) 2134 2135#define chunksize(p) ((p)->head & ~(FLAG_BITS)) 2136 2137#define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT) 2138 2139/* Treat space at ptr +/- offset as a chunk */ 2140#define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s))) 2141#define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s))) 2142 2143/* Ptr to next or previous physical malloc_chunk. */ 2144#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS))) 2145#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) )) 2146 2147/* extract next chunk's pinuse bit */ 2148#define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT) 2149 2150/* Get/set size at footer */ 2151#define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot) 2152#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s)) 2153 2154/* Set size, pinuse bit, and foot */ 2155#define set_size_and_pinuse_of_free_chunk(p, s)\ 2156 ((p)->head = (s|PINUSE_BIT), set_foot(p, s)) 2157 2158/* Set size, pinuse bit, foot, and clear next pinuse */ 2159#define set_free_with_pinuse(p, s, n)\ 2160 (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s)) 2161 2162/* Get the internal overhead associated with chunk p */ 2163#define overhead_for(p)\ 2164 (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD) 2165 2166/* Return true if malloced space is not necessarily cleared */ 2167#if MMAP_CLEARS 2168#define calloc_must_clear(p) (!is_mmapped(p)) 2169#else /* MMAP_CLEARS */ 2170#define calloc_must_clear(p) (1) 2171#endif /* MMAP_CLEARS */ 2172 2173/* ---------------------- Overlaid data structures ----------------------- */ 2174 2175/* 2176 When chunks are not in use, they are treated as nodes of either 2177 lists or trees. 2178 2179 "Small" chunks are stored in circular doubly-linked lists, and look 2180 like this: 2181 2182 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2183 | Size of previous chunk | 2184 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2185 `head:' | Size of chunk, in bytes |P| 2186 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2187 | Forward pointer to next chunk in list | 2188 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2189 | Back pointer to previous chunk in list | 2190 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2191 | Unused space (may be 0 bytes long) . 2192 . . 2193 . | 2194nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2195 `foot:' | Size of chunk, in bytes | 2196 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2197 2198 Larger chunks are kept in a form of bitwise digital trees (aka 2199 tries) keyed on chunksizes. Because malloc_tree_chunks are only for 2200 free chunks greater than 256 bytes, their size doesn't impose any 2201 constraints on user chunk sizes. Each node looks like: 2202 2203 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2204 | Size of previous chunk | 2205 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2206 `head:' | Size of chunk, in bytes |P| 2207 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2208 | Forward pointer to next chunk of same size | 2209 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2210 | Back pointer to previous chunk of same size | 2211 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2212 | Pointer to left child (child[0]) | 2213 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2214 | Pointer to right child (child[1]) | 2215 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2216 | Pointer to parent | 2217 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2218 | bin index of this chunk | 2219 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2220 | Unused space . 2221 . | 2222nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2223 `foot:' | Size of chunk, in bytes | 2224 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2225 2226 Each tree holding treenodes is a tree of unique chunk sizes. Chunks 2227 of the same size are arranged in a circularly-linked list, with only 2228 the oldest chunk (the next to be used, in our FIFO ordering) 2229 actually in the tree. (Tree members are distinguished by a non-null 2230 parent pointer.) If a chunk with the same size an an existing node 2231 is inserted, it is linked off the existing node using pointers that 2232 work in the same way as fd/bk pointers of small chunks. 2233 2234 Each tree contains a power of 2 sized range of chunk sizes (the 2235 smallest is 0x100 <= x < 0x180), which is is divided in half at each 2236 tree level, with the chunks in the smaller half of the range (0x100 2237 <= x < 0x140 for the top nose) in the left subtree and the larger 2238 half (0x140 <= x < 0x180) in the right subtree. This is, of course, 2239 done by inspecting individual bits. 2240 2241 Using these rules, each node's left subtree contains all smaller 2242 sizes than its right subtree. However, the node at the root of each 2243 subtree has no particular ordering relationship to either. (The 2244 dividing line between the subtree sizes is based on trie relation.) 2245 If we remove the last chunk of a given size from the interior of the 2246 tree, we need to replace it with a leaf node. The tree ordering 2247 rules permit a node to be replaced by any leaf below it. 2248 2249 The smallest chunk in a tree (a common operation in a best-fit 2250 allocator) can be found by walking a path to the leftmost leaf in 2251 the tree. Unlike a usual binary tree, where we follow left child 2252 pointers until we reach a null, here we follow the right child 2253 pointer any time the left one is null, until we reach a leaf with 2254 both child pointers null. The smallest chunk in the tree will be 2255 somewhere along that path. 2256 2257 The worst case number of steps to add, find, or remove a node is 2258 bounded by the number of bits differentiating chunks within 2259 bins. Under current bin calculations, this ranges from 6 up to 21 2260 (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case 2261 is of course much better. 2262*/ 2263 2264struct malloc_tree_chunk { 2265 /* The first four fields must be compatible with malloc_chunk */ 2266 size_t prev_foot; 2267 size_t head; 2268 struct malloc_tree_chunk* fd; 2269 struct malloc_tree_chunk* bk; 2270 2271 struct malloc_tree_chunk* child[2]; 2272 struct malloc_tree_chunk* parent; 2273 bindex_t index; 2274}; 2275 2276typedef struct malloc_tree_chunk tchunk; 2277typedef struct malloc_tree_chunk* tchunkptr; 2278typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */ 2279 2280/* A little helper macro for trees */ 2281#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1]) 2282 2283/* ----------------------------- Segments -------------------------------- */ 2284 2285/* 2286 Each malloc space may include non-contiguous segments, held in a 2287 list headed by an embedded malloc_segment record representing the 2288 top-most space. Segments also include flags holding properties of 2289 the space. Large chunks that are directly allocated by mmap are not 2290 included in this list. They are instead independently created and 2291 destroyed without otherwise keeping track of them. 2292 2293 Segment management mainly comes into play for spaces allocated by 2294 MMAP. Any call to MMAP might or might not return memory that is 2295 adjacent to an existing segment. MORECORE normally contiguously 2296 extends the current space, so this space is almost always adjacent, 2297 which is simpler and faster to deal with. (This is why MORECORE is 2298 used preferentially to MMAP when both are available -- see 2299 sys_alloc.) When allocating using MMAP, we don't use any of the 2300 hinting mechanisms (inconsistently) supported in various 2301 implementations of unix mmap, or distinguish reserving from 2302 committing memory. Instead, we just ask for space, and exploit 2303 contiguity when we get it. It is probably possible to do 2304 better than this on some systems, but no general scheme seems 2305 to be significantly better. 2306 2307 Management entails a simpler variant of the consolidation scheme 2308 used for chunks to reduce fragmentation -- new adjacent memory is 2309 normally prepended or appended to an existing segment. However, 2310 there are limitations compared to chunk consolidation that mostly 2311 reflect the fact that segment processing is relatively infrequent 2312 (occurring only when getting memory from system) and that we 2313 don't expect to have huge numbers of segments: 2314 2315 * Segments are not indexed, so traversal requires linear scans. (It 2316 would be possible to index these, but is not worth the extra 2317 overhead and complexity for most programs on most platforms.) 2318 * New segments are only appended to old ones when holding top-most 2319 memory; if they cannot be prepended to others, they are held in 2320 different segments. 2321 2322 Except for the top-most segment of an mstate, each segment record 2323 is kept at the tail of its segment. Segments are added by pushing 2324 segment records onto the list headed by &mstate.seg for the 2325 containing mstate. 2326 2327 Segment flags control allocation/merge/deallocation policies: 2328 * If EXTERN_BIT set, then we did not allocate this segment, 2329 and so should not try to deallocate or merge with others. 2330 (This currently holds only for the initial segment passed 2331 into create_mspace_with_base.) 2332 * If USE_MMAP_BIT set, the segment may be merged with 2333 other surrounding mmapped segments and trimmed/de-allocated 2334 using munmap. 2335 * If neither bit is set, then the segment was obtained using 2336 MORECORE so can be merged with surrounding MORECORE'd segments 2337 and deallocated/trimmed using MORECORE with negative arguments. 2338*/ 2339 2340struct malloc_segment { 2341 char* base; /* base address */ 2342 size_t size; /* allocated size */ 2343 struct malloc_segment* next; /* ptr to next segment */ 2344 flag_t sflags; /* mmap and extern flag */ 2345}; 2346 2347#define is_mmapped_segment(S) ((S)->sflags & USE_MMAP_BIT) 2348#define is_extern_segment(S) ((S)->sflags & EXTERN_BIT) 2349 2350typedef struct malloc_segment msegment; 2351typedef struct malloc_segment* msegmentptr; 2352 2353/* ---------------------------- malloc_state ----------------------------- */ 2354 2355/* 2356 A malloc_state holds all of the bookkeeping for a space. 2357 The main fields are: 2358 2359 Top 2360 The topmost chunk of the currently active segment. Its size is 2361 cached in topsize. The actual size of topmost space is 2362 topsize+TOP_FOOT_SIZE, which includes space reserved for adding 2363 fenceposts and segment records if necessary when getting more 2364 space from the system. The size at which to autotrim top is 2365 cached from mparams in trim_check, except that it is disabled if 2366 an autotrim fails. 2367 2368 Designated victim (dv) 2369 This is the preferred chunk for servicing small requests that 2370 don't have exact fits. It is normally the chunk split off most 2371 recently to service another small request. Its size is cached in 2372 dvsize. The link fields of this chunk are not maintained since it 2373 is not kept in a bin. 2374 2375 SmallBins 2376 An array of bin headers for free chunks. These bins hold chunks 2377 with sizes less than MIN_LARGE_SIZE bytes. Each bin contains 2378 chunks of all the same size, spaced 8 bytes apart. To simplify 2379 use in double-linked lists, each bin header acts as a malloc_chunk 2380 pointing to the real first node, if it exists (else pointing to 2381 itself). This avoids special-casing for headers. But to avoid 2382 waste, we allocate only the fd/bk pointers of bins, and then use 2383 repositioning tricks to treat these as the fields of a chunk. 2384 2385 TreeBins 2386 Treebins are pointers to the roots of trees holding a range of 2387 sizes. There are 2 equally spaced treebins for each power of two 2388 from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything 2389 larger. 2390 2391 Bin maps 2392 There is one bit map for small bins ("smallmap") and one for 2393 treebins ("treemap). Each bin sets its bit when non-empty, and 2394 clears the bit when empty. Bit operations are then used to avoid 2395 bin-by-bin searching -- nearly all "search" is done without ever 2396 looking at bins that won't be selected. The bit maps 2397 conservatively use 32 bits per map word, even if on 64bit system. 2398 For a good description of some of the bit-based techniques used 2399 here, see Henry S. Warren Jr's book "Hacker's Delight" (and 2400 supplement at http://hackersdelight.org/). Many of these are 2401 intended to reduce the branchiness of paths through malloc etc, as 2402 well as to reduce the number of memory locations read or written. 2403 2404 Segments 2405 A list of segments headed by an embedded malloc_segment record 2406 representing the initial space. 2407 2408 Address check support 2409 The least_addr field is the least address ever obtained from 2410 MORECORE or MMAP. Attempted frees and reallocs of any address less 2411 than this are trapped (unless INSECURE is defined). 2412 2413 Magic tag 2414 A cross-check field that should always hold same value as mparams.magic. 2415 2416 Flags 2417 Bits recording whether to use MMAP, locks, or contiguous MORECORE 2418 2419 Statistics 2420 Each space keeps track of current and maximum system memory 2421 obtained via MORECORE or MMAP. 2422 2423 Trim support 2424 Fields holding the amount of unused topmost memory that should trigger 2425 timming, and a counter to force periodic scanning to release unused 2426 non-topmost segments. 2427 2428 Locking 2429 If USE_LOCKS is defined, the "mutex" lock is acquired and released 2430 around every public call using this mspace. 2431 2432 Extension support 2433 A void* pointer and a size_t field that can be used to help implement 2434 extensions to this malloc. 2435*/ 2436 2437/* Bin types, widths and sizes */ 2438#define NSMALLBINS (32U) 2439#define NTREEBINS (32U) 2440#define SMALLBIN_SHIFT (3U) 2441#define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT) 2442#define TREEBIN_SHIFT (8U) 2443#define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT) 2444#define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE) 2445#define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD) 2446 2447struct malloc_state { 2448 binmap_t smallmap; 2449 binmap_t treemap; 2450 size_t dvsize; 2451 size_t topsize; 2452 char* least_addr; 2453 mchunkptr dv; 2454 mchunkptr top; 2455 size_t trim_check; 2456 size_t release_checks; 2457 size_t magic; 2458 mchunkptr smallbins[(NSMALLBINS+1)*2]; 2459 tbinptr treebins[NTREEBINS]; 2460 size_t footprint; 2461 size_t max_footprint; 2462 flag_t mflags; 2463#if USE_LOCKS 2464 MLOCK_T mutex; /* locate lock among fields that rarely change */ 2465#endif /* USE_LOCKS */ 2466 msegment seg; 2467 void* extp; /* Unused but available for extensions */ 2468 size_t exts; 2469}; 2470 2471typedef struct malloc_state* mstate; 2472 2473/* ------------- Global malloc_state and malloc_params ------------------- */ 2474 2475/* 2476 malloc_params holds global properties, including those that can be 2477 dynamically set using mallopt. There is a single instance, mparams, 2478 initialized in init_mparams. Note that the non-zeroness of "magic" 2479 also serves as an initialization flag. 2480*/ 2481 2482struct malloc_params { 2483 volatile size_t magic; 2484 size_t page_size; 2485 size_t granularity; 2486 size_t mmap_threshold; 2487 size_t trim_threshold; 2488 flag_t default_mflags; 2489}; 2490 2491static struct malloc_params mparams; 2492 2493/* Ensure mparams initialized */ 2494#define ensure_initialization() (void)(mparams.magic != 0 || init_mparams()) 2495 2496#if !ONLY_MSPACES 2497 2498/* The global malloc_state used for all non-"mspace" calls */ 2499static struct malloc_state _gm_; 2500#define gm (&_gm_) 2501#define is_global(M) ((M) == &_gm_) 2502 2503#endif /* !ONLY_MSPACES */ 2504 2505#define is_initialized(M) ((M)->top != 0) 2506 2507/* -------------------------- system alloc setup ------------------------- */ 2508 2509/* Operations on mflags */ 2510 2511#define use_lock(M) ((M)->mflags & USE_LOCK_BIT) 2512#define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT) 2513#define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT) 2514 2515#define use_mmap(M) ((M)->mflags & USE_MMAP_BIT) 2516#define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT) 2517#define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT) 2518 2519#define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT) 2520#define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT) 2521 2522#define set_lock(M,L)\ 2523 ((M)->mflags = (L)?\ 2524 ((M)->mflags | USE_LOCK_BIT) :\ 2525 ((M)->mflags & ~USE_LOCK_BIT)) 2526 2527/* page-align a size */ 2528#define page_align(S)\ 2529 (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE)) 2530 2531/* granularity-align a size */ 2532#define granularity_align(S)\ 2533 (((S) + (mparams.granularity - SIZE_T_ONE))\ 2534 & ~(mparams.granularity - SIZE_T_ONE)) 2535 2536 2537/* For mmap, use granularity alignment on windows, else page-align */ 2538#ifdef WIN32 2539#define mmap_align(S) granularity_align(S) 2540#else 2541#define mmap_align(S) page_align(S) 2542#endif 2543 2544/* For sys_alloc, enough padding to ensure can malloc request on success */ 2545#define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT) 2546 2547#define is_page_aligned(S)\ 2548 (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0) 2549#define is_granularity_aligned(S)\ 2550 (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0) 2551 2552/* True if segment S holds address A */ 2553#define segment_holds(S, A)\ 2554 ((char*)(A) >= S->base && (char*)(A) < S->base + S->size) 2555 2556/* Return segment holding given address */ 2557static msegmentptr segment_holding(mstate m, char* addr) { 2558 msegmentptr sp = &m->seg; 2559 for (;;) { 2560 if (addr >= sp->base && addr < sp->base + sp->size) 2561 return sp; 2562 if ((sp = sp->next) == 0) 2563 return 0; 2564 } 2565} 2566 2567/* Return true if segment contains a segment link */ 2568static int has_segment_link(mstate m, msegmentptr ss) { 2569 msegmentptr sp = &m->seg; 2570 for (;;) { 2571 if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size) 2572 return 1; 2573 if ((sp = sp->next) == 0) 2574 return 0; 2575 } 2576} 2577 2578#ifndef MORECORE_CANNOT_TRIM 2579#define should_trim(M,s) ((s) > (M)->trim_check) 2580#else /* MORECORE_CANNOT_TRIM */ 2581#define should_trim(M,s) (0) 2582#endif /* MORECORE_CANNOT_TRIM */ 2583 2584/* 2585 TOP_FOOT_SIZE is padding at the end of a segment, including space 2586 that may be needed to place segment records and fenceposts when new 2587 noncontiguous segments are added. 2588*/ 2589#define TOP_FOOT_SIZE\ 2590 (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE) 2591 2592 2593/* ------------------------------- Hooks -------------------------------- */ 2594 2595/* 2596 PREACTION should be defined to return 0 on success, and nonzero on 2597 failure. If you are not using locking, you can redefine these to do 2598 anything you like. 2599*/ 2600 2601#if USE_LOCKS 2602 2603#define PREACTION(M) ((use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0) 2604#define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); } 2605#else /* USE_LOCKS */ 2606 2607#ifndef PREACTION 2608#define PREACTION(M) (0) 2609#endif /* PREACTION */ 2610 2611#ifndef POSTACTION 2612#define POSTACTION(M) 2613#endif /* POSTACTION */ 2614 2615#endif /* USE_LOCKS */ 2616 2617/* 2618 CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses. 2619 USAGE_ERROR_ACTION is triggered on detected bad frees and 2620 reallocs. The argument p is an address that might have triggered the 2621 fault. It is ignored by the two predefined actions, but might be 2622 useful in custom actions that try to help diagnose errors. 2623*/ 2624 2625#if PROCEED_ON_ERROR 2626 2627/* A count of the number of corruption errors causing resets */ 2628int malloc_corruption_error_count; 2629 2630/* default corruption action */ 2631static void reset_on_error(mstate m); 2632 2633#define CORRUPTION_ERROR_ACTION(m) reset_on_error(m) 2634#define USAGE_ERROR_ACTION(m, p) 2635 2636#else /* PROCEED_ON_ERROR */ 2637 2638#ifndef CORRUPTION_ERROR_ACTION 2639#define CORRUPTION_ERROR_ACTION(m) ABORT 2640#endif /* CORRUPTION_ERROR_ACTION */ 2641 2642#ifndef USAGE_ERROR_ACTION 2643#define USAGE_ERROR_ACTION(m,p) ABORT 2644#endif /* USAGE_ERROR_ACTION */ 2645 2646#endif /* PROCEED_ON_ERROR */ 2647 2648/* -------------------------- Debugging setup ---------------------------- */ 2649 2650#if ! DEBUG 2651 2652#define check_free_chunk(M,P) 2653#define check_inuse_chunk(M,P) 2654#define check_malloced_chunk(M,P,N) 2655#define check_mmapped_chunk(M,P) 2656#define check_malloc_state(M) 2657#define check_top_chunk(M,P) 2658 2659#else /* DEBUG */ 2660#define check_free_chunk(M,P) do_check_free_chunk(M,P) 2661#define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P) 2662#define check_top_chunk(M,P) do_check_top_chunk(M,P) 2663#define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N) 2664#define check_mmapped_chunk(M,P) do_check_mmapped_chunk(M,P) 2665#define check_malloc_state(M) do_check_malloc_state(M) 2666 2667static void do_check_any_chunk(mstate m, mchunkptr p); 2668static void do_check_top_chunk(mstate m, mchunkptr p); 2669static void do_check_mmapped_chunk(mstate m, mchunkptr p); 2670static void do_check_inuse_chunk(mstate m, mchunkptr p); 2671static void do_check_free_chunk(mstate m, mchunkptr p); 2672static void do_check_malloced_chunk(mstate m, void* mem, size_t s); 2673static void do_check_tree(mstate m, tchunkptr t); 2674static void do_check_treebin(mstate m, bindex_t i); 2675static void do_check_smallbin(mstate m, bindex_t i); 2676static void do_check_malloc_state(mstate m); 2677static int bin_find(mstate m, mchunkptr x); 2678static size_t traverse_and_check(mstate m); 2679#endif /* DEBUG */ 2680 2681/* ---------------------------- Indexing Bins ---------------------------- */ 2682 2683#define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS) 2684#define small_index(s) ((s) >> SMALLBIN_SHIFT) 2685#define small_index2size(i) ((i) << SMALLBIN_SHIFT) 2686#define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE)) 2687 2688/* addressing by index. See above about smallbin repositioning */ 2689#define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1]))) 2690#define treebin_at(M,i) (&((M)->treebins[i])) 2691 2692/* assign tree index for size S to variable I. Use x86 asm if possible */ 2693#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)) 2694#define compute_tree_index(S, I)\ 2695{\ 2696 unsigned int X = S >> TREEBIN_SHIFT;\ 2697 if (X == 0)\ 2698 I = 0;\ 2699 else if (X > 0xFFFF)\ 2700 I = NTREEBINS-1;\ 2701 else {\ 2702 unsigned int K;\ 2703 __asm__("bsrl\t%1, %0\n\t" : "=r" (K) : "g" (X));\ 2704 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\ 2705 }\ 2706} 2707 2708#elif defined (__INTEL_COMPILER) 2709#define compute_tree_index(S, I)\ 2710{\ 2711 size_t X = S >> TREEBIN_SHIFT;\ 2712 if (X == 0)\ 2713 I = 0;\ 2714 else if (X > 0xFFFF)\ 2715 I = NTREEBINS-1;\ 2716 else {\ 2717 unsigned int K = _bit_scan_reverse (X); \ 2718 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\ 2719 }\ 2720} 2721 2722#elif defined(_MSC_VER) && _MSC_VER>=1300 2723#define compute_tree_index(S, I)\ 2724{\ 2725 size_t X = S >> TREEBIN_SHIFT;\ 2726 if (X == 0)\ 2727 I = 0;\ 2728 else if (X > 0xFFFF)\ 2729 I = NTREEBINS-1;\ 2730 else {\ 2731 unsigned int K;\ 2732 _BitScanReverse((DWORD *) &K, X);\ 2733 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\ 2734 }\ 2735} 2736 2737#else /* GNUC */ 2738#define compute_tree_index(S, I)\ 2739{\ 2740 size_t X = S >> TREEBIN_SHIFT;\ 2741 if (X == 0)\ 2742 I = 0;\ 2743 else if (X > 0xFFFF)\ 2744 I = NTREEBINS-1;\ 2745 else {\ 2746 unsigned int Y = (unsigned int)X;\ 2747 unsigned int N = ((Y - 0x100) >> 16) & 8;\ 2748 unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\ 2749 N += K;\ 2750 N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\ 2751 K = 14 - N + ((Y <<= K) >> 15);\ 2752 I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\ 2753 }\ 2754} 2755#endif /* GNUC */ 2756 2757/* Bit representing maximum resolved size in a treebin at i */ 2758#define bit_for_tree_index(i) \ 2759 (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2) 2760 2761/* Shift placing maximum resolved bit in a treebin at i as sign bit */ 2762#define leftshift_for_tree_index(i) \ 2763 ((i == NTREEBINS-1)? 0 : \ 2764 ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2))) 2765 2766/* The size of the smallest chunk held in bin with index i */ 2767#define minsize_for_tree_index(i) \ 2768 ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \ 2769 (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1))) 2770 2771 2772/* ------------------------ Operations on bin maps ----------------------- */ 2773 2774/* bit corresponding to given index */ 2775#define idx2bit(i) ((binmap_t)(1) << (i)) 2776 2777/* Mark/Clear bits with given index */ 2778#define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i)) 2779#define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i)) 2780#define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i)) 2781 2782#define mark_treemap(M,i) ((M)->treemap |= idx2bit(i)) 2783#define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i)) 2784#define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i)) 2785 2786/* isolate the least set bit of a bitmap */ 2787#define least_bit(x) ((x) & -(x)) 2788 2789/* mask with all bits to left of least bit of x on */ 2790#define left_bits(x) ((x<<1) | -(x<<1)) 2791 2792/* mask with all bits to left of or equal to least bit of x on */ 2793#define same_or_left_bits(x) ((x) | -(x)) 2794 2795/* index corresponding to given bit. Use x86 asm if possible */ 2796 2797#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)) 2798#define compute_bit2idx(X, I)\ 2799{\ 2800 unsigned int J;\ 2801 __asm__("bsfl\t%1, %0\n\t" : "=r" (J) : "g" (X));\ 2802 I = (bindex_t)J;\ 2803} 2804 2805#elif defined (__INTEL_COMPILER) 2806#define compute_bit2idx(X, I)\ 2807{\ 2808 unsigned int J;\ 2809 J = _bit_scan_forward (X); \ 2810 I = (bindex_t)J;\ 2811} 2812 2813#elif defined(_MSC_VER) && _MSC_VER>=1300 2814#define compute_bit2idx(X, I)\ 2815{\ 2816 unsigned int J;\ 2817 _BitScanForward((DWORD *) &J, X);\ 2818 I = (bindex_t)J;\ 2819} 2820 2821#elif USE_BUILTIN_FFS 2822#define compute_bit2idx(X, I) I = ffs(X)-1 2823 2824#else 2825#define compute_bit2idx(X, I)\ 2826{\ 2827 unsigned int Y = X - 1;\ 2828 unsigned int K = Y >> (16-4) & 16;\ 2829 unsigned int N = K; Y >>= K;\ 2830 N += K = Y >> (8-3) & 8; Y >>= K;\ 2831 N += K = Y >> (4-2) & 4; Y >>= K;\ 2832 N += K = Y >> (2-1) & 2; Y >>= K;\ 2833 N += K = Y >> (1-0) & 1; Y >>= K;\ 2834 I = (bindex_t)(N + Y);\ 2835} 2836#endif /* GNUC */ 2837 2838 2839/* ----------------------- Runtime Check Support ------------------------- */ 2840 2841/* 2842 For security, the main invariant is that malloc/free/etc never 2843 writes to a static address other than malloc_state, unless static 2844 malloc_state itself has been corrupted, which cannot occur via 2845 malloc (because of these checks). In essence this means that we 2846 believe all pointers, sizes, maps etc held in malloc_state, but 2847 check all of those linked or offsetted from other embedded data 2848 structures. These checks are interspersed with main code in a way 2849 that tends to minimize their run-time cost. 2850 2851 When FOOTERS is defined, in addition to range checking, we also 2852 verify footer fields of inuse chunks, which can be used guarantee 2853 that the mstate controlling malloc/free is intact. This is a 2854 streamlined version of the approach described by William Robertson 2855 et al in "Run-time Detection of Heap-based Overflows" LISA'03 2856 http://www.usenix.org/events/lisa03/tech/robertson.html The footer 2857 of an inuse chunk holds the xor of its mstate and a random seed, 2858 that is checked upon calls to free() and realloc(). This is 2859 (probablistically) unguessable from outside the program, but can be 2860 computed by any code successfully malloc'ing any chunk, so does not 2861 itself provide protection against code that has already broken 2862 security through some other means. Unlike Robertson et al, we 2863 always dynamically check addresses of all offset chunks (previous, 2864 next, etc). This turns out to be cheaper than relying on hashes. 2865*/ 2866 2867#if !INSECURE 2868/* Check if address a is at least as high as any from MORECORE or MMAP */ 2869#define ok_address(M, a) ((char*)(a) >= (M)->least_addr) 2870/* Check if address of next chunk n is higher than base chunk p */ 2871#define ok_next(p, n) ((char*)(p) < (char*)(n)) 2872/* Check if p has inuse status */ 2873#define ok_inuse(p) is_inuse(p) 2874/* Check if p has its pinuse bit on */ 2875#define ok_pinuse(p) pinuse(p) 2876 2877#else /* !INSECURE */ 2878#define ok_address(M, a) (1) 2879#define ok_next(b, n) (1) 2880#define ok_inuse(p) (1) 2881#define ok_pinuse(p) (1) 2882#endif /* !INSECURE */ 2883 2884#if (FOOTERS && !INSECURE) 2885/* Check if (alleged) mstate m has expected magic field */ 2886#define ok_magic(M) ((M)->magic == mparams.magic) 2887#else /* (FOOTERS && !INSECURE) */ 2888#define ok_magic(M) (1) 2889#endif /* (FOOTERS && !INSECURE) */ 2890 2891 2892/* In gcc, use __builtin_expect to minimize impact of checks */ 2893#if !INSECURE 2894#if defined(__GNUC__) && __GNUC__ >= 3 2895#define RTCHECK(e) __builtin_expect(e, 1) 2896#else /* GNUC */ 2897#define RTCHECK(e) (e) 2898#endif /* GNUC */ 2899#else /* !INSECURE */ 2900#define RTCHECK(e) (1) 2901#endif /* !INSECURE */ 2902 2903/* macros to set up inuse chunks with or without footers */ 2904 2905#if !FOOTERS 2906 2907#define mark_inuse_foot(M,p,s) 2908 2909/* Macros for setting head/foot of non-mmapped chunks */ 2910 2911/* Set cinuse bit and pinuse bit of next chunk */ 2912#define set_inuse(M,p,s)\ 2913 ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\ 2914 ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT) 2915 2916/* Set cinuse and pinuse of this chunk and pinuse of next chunk */ 2917#define set_inuse_and_pinuse(M,p,s)\ 2918 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\ 2919 ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT) 2920 2921/* Set size, cinuse and pinuse bit of this chunk */ 2922#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\ 2923 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT)) 2924 2925#else /* FOOTERS */ 2926 2927/* Set foot of inuse chunk to be xor of mstate and seed */ 2928#define mark_inuse_foot(M,p,s)\ 2929 (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic)) 2930 2931#define get_mstate_for(p)\ 2932 ((mstate)(((mchunkptr)((char*)(p) +\ 2933 (chunksize(p))))->prev_foot ^ mparams.magic)) 2934 2935#define set_inuse(M,p,s)\ 2936 ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\ 2937 (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \ 2938 mark_inuse_foot(M,p,s)) 2939 2940#define set_inuse_and_pinuse(M,p,s)\ 2941 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\ 2942 (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\ 2943 mark_inuse_foot(M,p,s)) 2944 2945#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\ 2946 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\ 2947 mark_inuse_foot(M, p, s)) 2948 2949#endif /* !FOOTERS */ 2950 2951/* ---------------------------- setting mparams -------------------------- */ 2952 2953/* Initialize mparams */ 2954static int init_mparams(void) { 2955#ifdef NEED_GLOBAL_LOCK_INIT 2956 if (malloc_global_mutex_status <= 0) 2957 init_malloc_global_mutex(); 2958#endif 2959 2960 ACQUIRE_MALLOC_GLOBAL_LOCK(); 2961 if (mparams.magic == 0) { 2962 size_t magic; 2963 size_t psize; 2964 size_t gsize; 2965 2966#ifndef WIN32 2967 psize = malloc_getpagesize; 2968 gsize = ((DEFAULT_GRANULARITY != 0)? DEFAULT_GRANULARITY : psize); 2969#else /* WIN32 */ 2970 { 2971 SYSTEM_INFO system_info; 2972 GetSystemInfo(&system_info); 2973 psize = system_info.dwPageSize; 2974 gsize = ((DEFAULT_GRANULARITY != 0)? 2975 DEFAULT_GRANULARITY : system_info.dwAllocationGranularity); 2976 } 2977#endif /* WIN32 */ 2978 2979 /* Sanity-check configuration: 2980 size_t must be unsigned and as wide as pointer type. 2981 ints must be at least 4 bytes. 2982 alignment must be at least 8. 2983 Alignment, min chunk size, and page size must all be powers of 2. 2984 */ 2985 if ((sizeof(size_t) != sizeof(char*)) || 2986 (MAX_SIZE_T < MIN_CHUNK_SIZE) || 2987 (sizeof(int) < 4) || 2988 (MALLOC_ALIGNMENT < (size_t)8U) || 2989 ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) || 2990 ((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) || 2991 ((gsize & (gsize-SIZE_T_ONE)) != 0) || 2992 ((psize & (psize-SIZE_T_ONE)) != 0)) 2993 ABORT; 2994 2995 mparams.granularity = gsize; 2996 mparams.page_size = psize; 2997 mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD; 2998 mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD; 2999#if MORECORE_CONTIGUOUS 3000 mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT; 3001#else /* MORECORE_CONTIGUOUS */ 3002 mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT; 3003#endif /* MORECORE_CONTIGUOUS */ 3004 3005#if !ONLY_MSPACES 3006 /* Set up lock for main malloc area */ 3007 gm->mflags = mparams.default_mflags; 3008 INITIAL_LOCK(&gm->mutex); 3009#endif 3010 3011 { 3012#if USE_DEV_RANDOM 3013 int fd; 3014 unsigned char buf[sizeof(size_t)]; 3015 /* Try to use /dev/urandom, else fall back on using time */ 3016 if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 && 3017 read(fd, buf, sizeof(buf)) == sizeof(buf)) { 3018 magic = *((size_t *) buf); 3019 close(fd); 3020 } 3021 else 3022#endif /* USE_DEV_RANDOM */ 3023#ifdef WIN32 3024 magic = (size_t)(GetTickCount() ^ (size_t)0x55555555U); 3025#else 3026 magic = (size_t)(time(0) ^ (size_t)0x55555555U); 3027#endif 3028 magic |= (size_t)8U; /* ensure nonzero */ 3029 magic &= ~(size_t)7U; /* improve chances of fault for bad values */ 3030 mparams.magic = magic; 3031 } 3032 } 3033 3034 RELEASE_MALLOC_GLOBAL_LOCK(); 3035 return 1; 3036} 3037 3038/* support for mallopt */ 3039static int change_mparam(int param_number, int value) { 3040 size_t val; 3041 ensure_initialization(); 3042 val = (value == -1)? MAX_SIZE_T : (size_t)value; 3043 switch(param_number) { 3044 case M_TRIM_THRESHOLD: 3045 mparams.trim_threshold = val; 3046 return 1; 3047 case M_GRANULARITY: 3048 if (val >= mparams.page_size && ((val & (val-1)) == 0)) { 3049 mparams.granularity = val; 3050 return 1; 3051 } 3052 else 3053 return 0; 3054 case M_MMAP_THRESHOLD: 3055 mparams.mmap_threshold = val; 3056 return 1; 3057 default: 3058 return 0; 3059 } 3060} 3061 3062#if DEBUG 3063/* ------------------------- Debugging Support --------------------------- */ 3064 3065/* Check properties of any chunk, whether free, inuse, mmapped etc */ 3066static void do_check_any_chunk(mstate m, mchunkptr p) { 3067 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD)); 3068 assert(ok_address(m, p)); 3069} 3070 3071/* Check properties of top chunk */ 3072static void do_check_top_chunk(mstate m, mchunkptr p) { 3073 msegmentptr sp = segment_holding(m, (char*)p); 3074 size_t sz = p->head & ~INUSE_BITS; /* third-lowest bit can be set! */ 3075 assert(sp != 0); 3076 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD)); 3077 assert(ok_address(m, p)); 3078 assert(sz == m->topsize); 3079 assert(sz > 0); 3080 assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE); 3081 assert(pinuse(p)); 3082 assert(!pinuse(chunk_plus_offset(p, sz))); 3083} 3084 3085/* Check properties of (inuse) mmapped chunks */ 3086static void do_check_mmapped_chunk(mstate m, mchunkptr p) { 3087 size_t sz = chunksize(p); 3088 size_t len = (sz + (p->prev_foot) + MMAP_FOOT_PAD); 3089 assert(is_mmapped(p)); 3090 assert(use_mmap(m)); 3091 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD)); 3092 assert(ok_address(m, p)); 3093 assert(!is_small(sz)); 3094 assert((len & (mparams.page_size-SIZE_T_ONE)) == 0); 3095 assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD); 3096 assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0); 3097} 3098 3099/* Check properties of inuse chunks */ 3100static void do_check_inuse_chunk(mstate m, mchunkptr p) { 3101 do_check_any_chunk(m, p); 3102 assert(is_inuse(p)); 3103 assert(next_pinuse(p)); 3104 /* If not pinuse and not mmapped, previous chunk has OK offset */ 3105 assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p); 3106 if (is_mmapped(p)) 3107 do_check_mmapped_chunk(m, p); 3108} 3109 3110/* Check properties of free chunks */ 3111static void do_check_free_chunk(mstate m, mchunkptr p) { 3112 size_t sz = chunksize(p); 3113 mchunkptr next = chunk_plus_offset(p, sz); 3114 do_check_any_chunk(m, p); 3115 assert(!is_inuse(p)); 3116 assert(!next_pinuse(p)); 3117 assert (!is_mmapped(p)); 3118 if (p != m->dv && p != m->top) { 3119 if (sz >= MIN_CHUNK_SIZE) { 3120 assert((sz & CHUNK_ALIGN_MASK) == 0); 3121 assert(is_aligned(chunk2mem(p))); 3122 assert(next->prev_foot == sz); 3123 assert(pinuse(p)); 3124 assert (next == m->top || is_inuse(next)); 3125 assert(p->fd->bk == p); 3126 assert(p->bk->fd == p); 3127 } 3128 else /* markers are always of size SIZE_T_SIZE */ 3129 assert(sz == SIZE_T_SIZE); 3130 } 3131} 3132 3133/* Check properties of malloced chunks at the point they are malloced */ 3134static void do_check_malloced_chunk(mstate m, void* mem, size_t s) { 3135 if (mem != 0) { 3136 mchunkptr p = mem2chunk(mem); 3137 size_t sz = p->head & ~INUSE_BITS; 3138 do_check_inuse_chunk(m, p); 3139 assert((sz & CHUNK_ALIGN_MASK) == 0); 3140 assert(sz >= MIN_CHUNK_SIZE); 3141 assert(sz >= s); 3142 /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */ 3143 assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE)); 3144 } 3145} 3146 3147/* Check a tree and its subtrees. */ 3148static void do_check_tree(mstate m, tchunkptr t) { 3149 tchunkptr head = 0; 3150 tchunkptr u = t; 3151 bindex_t tindex = t->index; 3152 size_t tsize = chunksize(t); 3153 bindex_t idx; 3154 compute_tree_index(tsize, idx); 3155 assert(tindex == idx); 3156 assert(tsize >= MIN_LARGE_SIZE); 3157 assert(tsize >= minsize_for_tree_index(idx)); 3158 assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1)))); 3159 3160 do { /* traverse through chain of same-sized nodes */ 3161 do_check_any_chunk(m, ((mchunkptr)u)); 3162 assert(u->index == tindex); 3163 assert(chunksize(u) == tsize); 3164 assert(!is_inuse(u)); 3165 assert(!next_pinuse(u)); 3166 assert(u->fd->bk == u); 3167 assert(u->bk->fd == u); 3168 if (u->parent == 0) { 3169 assert(u->child[0] == 0); 3170 assert(u->child[1] == 0); 3171 } 3172 else { 3173 assert(head == 0); /* only one node on chain has parent */ 3174 head = u; 3175 assert(u->parent != u); 3176 assert (u->parent->child[0] == u || 3177 u->parent->child[1] == u || 3178 *((tbinptr*)(u->parent)) == u); 3179 if (u->child[0] != 0) { 3180 assert(u->child[0]->parent == u); 3181 assert(u->child[0] != u); 3182 do_check_tree(m, u->child[0]); 3183 } 3184 if (u->child[1] != 0) { 3185 assert(u->child[1]->parent == u); 3186 assert(u->child[1] != u); 3187 do_check_tree(m, u->child[1]); 3188 } 3189 if (u->child[0] != 0 && u->child[1] != 0) { 3190 assert(chunksize(u->child[0]) < chunksize(u->child[1])); 3191 } 3192 } 3193 u = u->fd; 3194 } while (u != t); 3195 assert(head != 0); 3196} 3197 3198/* Check all the chunks in a treebin. */ 3199static void do_check_treebin(mstate m, bindex_t i) { 3200 tbinptr* tb = treebin_at(m, i); 3201 tchunkptr t = *tb; 3202 int empty = (m->treemap & (1U << i)) == 0; 3203 if (t == 0) 3204 assert(empty); 3205 if (!empty) 3206 do_check_tree(m, t); 3207} 3208 3209/* Check all the chunks in a smallbin. */ 3210static void do_check_smallbin(mstate m, bindex_t i) { 3211 sbinptr b = smallbin_at(m, i); 3212 mchunkptr p = b->bk; 3213 unsigned int empty = (m->smallmap & (1U << i)) == 0; 3214 if (p == b) 3215 assert(empty); 3216 if (!empty) { 3217 for (; p != b; p = p->bk) { 3218 size_t size = chunksize(p); 3219 mchunkptr q; 3220 /* each chunk claims to be free */ 3221 do_check_free_chunk(m, p); 3222 /* chunk belongs in bin */ 3223 assert(small_index(size) == i); 3224 assert(p->bk == b || chunksize(p->bk) == chunksize(p)); 3225 /* chunk is followed by an inuse chunk */ 3226 q = next_chunk(p); 3227 if (q->head != FENCEPOST_HEAD) 3228 do_check_inuse_chunk(m, q); 3229 } 3230 } 3231} 3232 3233/* Find x in a bin. Used in other check functions. */ 3234static int bin_find(mstate m, mchunkptr x) { 3235 size_t size = chunksize(x); 3236 if (is_small(size)) { 3237 bindex_t sidx = small_index(size); 3238 sbinptr b = smallbin_at(m, sidx); 3239 if (smallmap_is_marked(m, sidx)) { 3240 mchunkptr p = b; 3241 do { 3242 if (p == x) 3243 return 1; 3244 } while ((p = p->fd) != b); 3245 } 3246 } 3247 else { 3248 bindex_t tidx; 3249 compute_tree_index(size, tidx); 3250 if (treemap_is_marked(m, tidx)) { 3251 tchunkptr t = *treebin_at(m, tidx); 3252 size_t sizebits = size << leftshift_for_tree_index(tidx); 3253 while (t != 0 && chunksize(t) != size) { 3254 t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]; 3255 sizebits <<= 1; 3256 } 3257 if (t != 0) { 3258 tchunkptr u = t; 3259 do { 3260 if (u == (tchunkptr)x) 3261 return 1; 3262 } while ((u = u->fd) != t); 3263 } 3264 } 3265 } 3266 return 0; 3267} 3268 3269/* Traverse each chunk and check it; return total */ 3270static size_t traverse_and_check(mstate m) { 3271 size_t sum = 0; 3272 if (is_initialized(m)) { 3273 msegmentptr s = &m->seg; 3274 sum += m->topsize + TOP_FOOT_SIZE; 3275 while (s != 0) { 3276 mchunkptr q = align_as_chunk(s->base); 3277 mchunkptr lastq = 0; 3278 assert(pinuse(q)); 3279 while (segment_holds(s, q) && 3280 q != m->top && q->head != FENCEPOST_HEAD) { 3281 sum += chunksize(q); 3282 if (is_inuse(q)) { 3283 assert(!bin_find(m, q)); 3284 do_check_inuse_chunk(m, q); 3285 } 3286 else { 3287 assert(q == m->dv || bin_find(m, q)); 3288 assert(lastq == 0 || is_inuse(lastq)); /* Not 2 consecutive free */ 3289 do_check_free_chunk(m, q); 3290 } 3291 lastq = q; 3292 q = next_chunk(q); 3293 } 3294 s = s->next; 3295 } 3296 } 3297 return sum; 3298} 3299 3300/* Check all properties of malloc_state. */ 3301static void do_check_malloc_state(mstate m) { 3302 bindex_t i; 3303 size_t total; 3304 /* check bins */ 3305 for (i = 0; i < NSMALLBINS; ++i) 3306 do_check_smallbin(m, i); 3307 for (i = 0; i < NTREEBINS; ++i) 3308 do_check_treebin(m, i); 3309 3310 if (m->dvsize != 0) { /* check dv chunk */ 3311 do_check_any_chunk(m, m->dv); 3312 assert(m->dvsize == chunksize(m->dv)); 3313 assert(m->dvsize >= MIN_CHUNK_SIZE); 3314 assert(bin_find(m, m->dv) == 0); 3315 } 3316 3317 if (m->top != 0) { /* check top chunk */ 3318 do_check_top_chunk(m, m->top); 3319 /*assert(m->topsize == chunksize(m->top)); redundant */ 3320 assert(m->topsize > 0); 3321 assert(bin_find(m, m->top) == 0); 3322 } 3323 3324 total = traverse_and_check(m); 3325 assert(total <= m->footprint); 3326 assert(m->footprint <= m->max_footprint); 3327} 3328#endif /* DEBUG */ 3329 3330/* ----------------------------- statistics ------------------------------ */ 3331 3332#if !NO_MALLINFO 3333static struct mallinfo internal_mallinfo(mstate m) { 3334 struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 3335 ensure_initialization(); 3336 if (!PREACTION(m)) { 3337 check_malloc_state(m); 3338 if (is_initialized(m)) { 3339 size_t nfree = SIZE_T_ONE; /* top always free */ 3340 size_t mfree = m->topsize + TOP_FOOT_SIZE; 3341 size_t sum = mfree; 3342 msegmentptr s = &m->seg; 3343 while (s != 0) { 3344 mchunkptr q = align_as_chunk(s->base); 3345 while (segment_holds(s, q) && 3346 q != m->top && q->head != FENCEPOST_HEAD) { 3347 size_t sz = chunksize(q); 3348 sum += sz; 3349 if (!is_inuse(q)) { 3350 mfree += sz; 3351 ++nfree; 3352 } 3353 q = next_chunk(q); 3354 } 3355 s = s->next; 3356 } 3357 3358 nm.arena = sum; 3359 nm.ordblks = nfree; 3360 nm.hblkhd = m->footprint - sum; 3361 nm.usmblks = m->max_footprint; 3362 nm.uordblks = m->footprint - mfree; 3363 nm.fordblks = mfree; 3364 nm.keepcost = m->topsize; 3365 } 3366 3367 POSTACTION(m); 3368 } 3369 return nm; 3370} 3371#endif /* !NO_MALLINFO */ 3372 3373static void internal_malloc_stats(mstate m) { 3374 ensure_initialization(); 3375 if (!PREACTION(m)) { 3376 size_t maxfp = 0; 3377 size_t fp = 0; 3378 size_t used = 0; 3379 check_malloc_state(m); 3380 if (is_initialized(m)) { 3381 msegmentptr s = &m->seg; 3382 maxfp = m->max_footprint; 3383 fp = m->footprint; 3384 used = fp - (m->topsize + TOP_FOOT_SIZE); 3385 3386 while (s != 0) { 3387 mchunkptr q = align_as_chunk(s->base); 3388 while (segment_holds(s, q) && 3389 q != m->top && q->head != FENCEPOST_HEAD) { 3390 if (!is_inuse(q)) 3391 used -= chunksize(q); 3392 q = next_chunk(q); 3393 } 3394 s = s->next; 3395 } 3396 } 3397 3398 fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp)); 3399 fprintf(stderr, "system bytes = %10lu\n", (unsigned long)(fp)); 3400 fprintf(stderr, "in use bytes = %10lu\n", (unsigned long)(used)); 3401 3402 POSTACTION(m); 3403 } 3404} 3405 3406/* ----------------------- Operations on smallbins ----------------------- */ 3407 3408/* 3409 Various forms of linking and unlinking are defined as macros. Even 3410 the ones for trees, which are very long but have very short typical 3411 paths. This is ugly but reduces reliance on inlining support of 3412 compilers. 3413*/ 3414 3415/* Link a free chunk into a smallbin */ 3416#define insert_small_chunk(M, P, S) {\ 3417 bindex_t I = small_index(S);\ 3418 mchunkptr B = smallbin_at(M, I);\ 3419 mchunkptr F = B;\ 3420 assert(S >= MIN_CHUNK_SIZE);\ 3421 if (!smallmap_is_marked(M, I))\ 3422 mark_smallmap(M, I);\ 3423 else if (RTCHECK(ok_address(M, B->fd)))\ 3424 F = B->fd;\ 3425 else {\ 3426 CORRUPTION_ERROR_ACTION(M);\ 3427 }\ 3428 B->fd = P;\ 3429 F->bk = P;\ 3430 P->fd = F;\ 3431 P->bk = B;\ 3432} 3433 3434/* Unlink a chunk from a smallbin */ 3435#define unlink_small_chunk(M, P, S) {\ 3436 mchunkptr F = P->fd;\ 3437 mchunkptr B = P->bk;\ 3438 bindex_t I = small_index(S);\ 3439 assert(P != B);\ 3440 assert(P != F);\ 3441 assert(chunksize(P) == small_index2size(I));\ 3442 if (F == B)\ 3443 clear_smallmap(M, I);\ 3444 else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\ 3445 (B == smallbin_at(M,I) || ok_address(M, B)))) {\ 3446 F->bk = B;\ 3447 B->fd = F;\ 3448 }\ 3449 else {\ 3450 CORRUPTION_ERROR_ACTION(M);\ 3451 }\ 3452} 3453 3454/* Unlink the first chunk from a smallbin */ 3455#define unlink_first_small_chunk(M, B, P, I) {\ 3456 mchunkptr F = P->fd;\ 3457 assert(P != B);\ 3458 assert(P != F);\ 3459 assert(chunksize(P) == small_index2size(I));\ 3460 if (B == F)\ 3461 clear_smallmap(M, I);\ 3462 else if (RTCHECK(ok_address(M, F))) {\ 3463 B->fd = F;\ 3464 F->bk = B;\ 3465 }\ 3466 else {\ 3467 CORRUPTION_ERROR_ACTION(M);\ 3468 }\ 3469} 3470 3471 3472 3473/* Replace dv node, binning the old one */ 3474/* Used only when dvsize known to be small */ 3475#define replace_dv(M, P, S) {\ 3476 size_t DVS = M->dvsize;\ 3477 if (DVS != 0) {\ 3478 mchunkptr DV = M->dv;\ 3479 assert(is_small(DVS));\ 3480 insert_small_chunk(M, DV, DVS);\ 3481 }\ 3482 M->dvsize = S;\ 3483 M->dv = P;\ 3484} 3485 3486/* ------------------------- Operations on trees ------------------------- */ 3487 3488/* Insert chunk into tree */ 3489#define insert_large_chunk(M, X, S) {\ 3490 tbinptr* H;\ 3491 bindex_t I;\ 3492 compute_tree_index(S, I);\ 3493 H = treebin_at(M, I);\ 3494 X->index = I;\ 3495 X->child[0] = X->child[1] = 0;\ 3496 if (!treemap_is_marked(M, I)) {\ 3497 mark_treemap(M, I);\ 3498 *H = X;\ 3499 X->parent = (tchunkptr)H;\ 3500 X->fd = X->bk = X;\ 3501 }\ 3502 else {\ 3503 tchunkptr T = *H;\ 3504 size_t K = S << leftshift_for_tree_index(I);\ 3505 for (;;) {\ 3506 if (chunksize(T) != S) {\ 3507 tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\ 3508 K <<= 1;\ 3509 if (*C != 0)\ 3510 T = *C;\ 3511 else if (RTCHECK(ok_address(M, C))) {\ 3512 *C = X;\ 3513 X->parent = T;\ 3514 X->fd = X->bk = X;\ 3515 break;\ 3516 }\ 3517 else {\ 3518 CORRUPTION_ERROR_ACTION(M);\ 3519 break;\ 3520 }\ 3521 }\ 3522 else {\ 3523 tchunkptr F = T->fd;\ 3524 if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\ 3525 T->fd = F->bk = X;\ 3526 X->fd = F;\ 3527 X->bk = T;\ 3528 X->parent = 0;\ 3529 break;\ 3530 }\ 3531 else {\ 3532 CORRUPTION_ERROR_ACTION(M);\ 3533 break;\ 3534 }\ 3535 }\ 3536 }\ 3537 }\ 3538} 3539 3540/* 3541 Unlink steps: 3542 3543 1. If x is a chained node, unlink it from its same-sized fd/bk links 3544 and choose its bk node as its replacement. 3545 2. If x was the last node of its size, but not a leaf node, it must 3546 be replaced with a leaf node (not merely one with an open left or 3547 right), to make sure that lefts and rights of descendents 3548 correspond properly to bit masks. We use the rightmost descendent 3549 of x. We could use any other leaf, but this is easy to locate and 3550 tends to counteract removal of leftmosts elsewhere, and so keeps 3551 paths shorter than minimally guaranteed. This doesn't loop much 3552 because on average a node in a tree is near the bottom. 3553 3. If x is the base of a chain (i.e., has parent links) relink 3554 x's parent and children to x's replacement (or null if none). 3555*/ 3556 3557#define unlink_large_chunk(M, X) {\ 3558 tchunkptr XP = X->parent;\ 3559 tchunkptr R;\ 3560 if (X->bk != X) {\ 3561 tchunkptr F = X->fd;\ 3562 R = X->bk;\ 3563 if (RTCHECK(ok_address(M, F))) {\ 3564 F->bk = R;\ 3565 R->fd = F;\ 3566 }\ 3567 else {\ 3568 CORRUPTION_ERROR_ACTION(M);\ 3569 }\ 3570 }\ 3571 else {\ 3572 tchunkptr* RP;\ 3573 if (((R = *(RP = &(X->child[1]))) != 0) ||\ 3574 ((R = *(RP = &(X->child[0]))) != 0)) {\ 3575 tchunkptr* CP;\ 3576 while ((*(CP = &(R->child[1])) != 0) ||\ 3577 (*(CP = &(R->child[0])) != 0)) {\ 3578 R = *(RP = CP);\ 3579 }\ 3580 if (RTCHECK(ok_address(M, RP)))\ 3581 *RP = 0;\ 3582 else {\ 3583 CORRUPTION_ERROR_ACTION(M);\ 3584 }\ 3585 }\ 3586 }\ 3587 if (XP != 0) {\ 3588 tbinptr* H = treebin_at(M, X->index);\ 3589 if (X == *H) {\ 3590 if ((*H = R) == 0) \ 3591 clear_treemap(M, X->index);\ 3592 }\ 3593 else if (RTCHECK(ok_address(M, XP))) {\ 3594 if (XP->child[0] == X) \ 3595 XP->child[0] = R;\ 3596 else \ 3597 XP->child[1] = R;\ 3598 }\ 3599 else\ 3600 CORRUPTION_ERROR_ACTION(M);\ 3601 if (R != 0) {\ 3602 if (RTCHECK(ok_address(M, R))) {\ 3603 tchunkptr C0, C1;\ 3604 R->parent = XP;\ 3605 if ((C0 = X->child[0]) != 0) {\ 3606 if (RTCHECK(ok_address(M, C0))) {\ 3607 R->child[0] = C0;\ 3608 C0->parent = R;\ 3609 }\ 3610 else\ 3611 CORRUPTION_ERROR_ACTION(M);\ 3612 }\ 3613 if ((C1 = X->child[1]) != 0) {\ 3614 if (RTCHECK(ok_address(M, C1))) {\ 3615 R->child[1] = C1;\ 3616 C1->parent = R;\ 3617 }\ 3618 else\ 3619 CORRUPTION_ERROR_ACTION(M);\ 3620 }\ 3621 }\ 3622 else\ 3623 CORRUPTION_ERROR_ACTION(M);\ 3624 }\ 3625 }\ 3626} 3627 3628/* Relays to large vs small bin operations */ 3629 3630#define insert_chunk(M, P, S)\ 3631 if (is_small(S)) insert_small_chunk(M, P, S)\ 3632 else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); } 3633 3634#define unlink_chunk(M, P, S)\ 3635 if (is_small(S)) unlink_small_chunk(M, P, S)\ 3636 else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); } 3637 3638 3639/* Relays to internal calls to malloc/free from realloc, memalign etc */ 3640 3641#if ONLY_MSPACES 3642#define internal_malloc(m, b) mspace_malloc(m, b) 3643#define internal_free(m, mem) mspace_free(m,mem); 3644#else /* ONLY_MSPACES */ 3645#if MSPACES 3646#define internal_malloc(m, b)\ 3647 (m == gm)? dlmalloc(b) : mspace_malloc(m, b) 3648#define internal_free(m, mem)\ 3649 if (m == gm) dlfree(mem); else mspace_free(m,mem); 3650#else /* MSPACES */ 3651#define internal_malloc(m, b) dlmalloc(b) 3652#define internal_free(m, mem) dlfree(mem) 3653#endif /* MSPACES */ 3654#endif /* ONLY_MSPACES */ 3655 3656/* ----------------------- Direct-mmapping chunks ----------------------- */ 3657 3658/* 3659 Directly mmapped chunks are set up with an offset to the start of 3660 the mmapped region stored in the prev_foot field of the chunk. This 3661 allows reconstruction of the required argument to MUNMAP when freed, 3662 and also allows adjustment of the returned chunk to meet alignment 3663 requirements (especially in memalign). 3664*/ 3665 3666/* Malloc using mmap */ 3667static void* mmap_alloc(mstate m, size_t nb) { 3668 size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK); 3669 if (mmsize > nb) { /* Check for wrap around 0 */ 3670 char* mm = (char*)(CALL_DIRECT_MMAP(mmsize)); 3671 if (mm != CMFAIL) { 3672 size_t offset = align_offset(chunk2mem(mm)); 3673 size_t psize = mmsize - offset - MMAP_FOOT_PAD; 3674 mchunkptr p = (mchunkptr)(mm + offset); 3675 p->prev_foot = offset; 3676 p->head = psize; 3677 mark_inuse_foot(m, p, psize); 3678 chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD; 3679 chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0; 3680 3681 if (m->least_addr == 0 || mm < m->least_addr) 3682 m->least_addr = mm; 3683 if ((m->footprint += mmsize) > m->max_footprint) 3684 m->max_footprint = m->footprint; 3685 assert(is_aligned(chunk2mem(p))); 3686 check_mmapped_chunk(m, p); 3687 return chunk2mem(p); 3688 } 3689 } 3690 return 0; 3691} 3692 3693/* Realloc using mmap */ 3694static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) { 3695 size_t oldsize = chunksize(oldp); 3696 if (is_small(nb)) /* Can't shrink mmap regions below small size */ 3697 return 0; 3698 /* Keep old chunk if big enough but not too big */ 3699 if (oldsize >= nb + SIZE_T_SIZE && 3700 (oldsize - nb) <= (mparams.granularity << 1)) 3701 return oldp; 3702 else { 3703 size_t offset = oldp->prev_foot; 3704 size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD; 3705 size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK); 3706 char* cp = (char*)CALL_MREMAP((char*)oldp - offset, 3707 oldmmsize, newmmsize, 1); 3708 if (cp != CMFAIL) { 3709 mchunkptr newp = (mchunkptr)(cp + offset); 3710 size_t psize = newmmsize - offset - MMAP_FOOT_PAD; 3711 newp->head = psize; 3712 mark_inuse_foot(m, newp, psize); 3713 chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD; 3714 chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0; 3715 3716 if (cp < m->least_addr) 3717 m->least_addr = cp; 3718 if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint) 3719 m->max_footprint = m->footprint; 3720 check_mmapped_chunk(m, newp); 3721 return newp; 3722 } 3723 } 3724 return 0; 3725} 3726 3727/* -------------------------- mspace management -------------------------- */ 3728 3729/* Initialize top chunk and its size */ 3730static void init_top(mstate m, mchunkptr p, size_t psize) { 3731 /* Ensure alignment */ 3732 size_t offset = align_offset(chunk2mem(p)); 3733 p = (mchunkptr)((char*)p + offset); 3734 psize -= offset; 3735 3736 m->top = p; 3737 m->topsize = psize; 3738 p->head = psize | PINUSE_BIT; 3739 /* set size of fake trailing chunk holding overhead space only once */ 3740 chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE; 3741 m->trim_check = mparams.trim_threshold; /* reset on each update */ 3742} 3743 3744/* Initialize bins for a new mstate that is otherwise zeroed out */ 3745static void init_bins(mstate m) { 3746 /* Establish circular links for smallbins */ 3747 bindex_t i; 3748 for (i = 0; i < NSMALLBINS; ++i) { 3749 sbinptr bin = smallbin_at(m,i); 3750 bin->fd = bin->bk = bin; 3751 } 3752} 3753 3754#if PROCEED_ON_ERROR 3755 3756/* default corruption action */ 3757static void reset_on_error(mstate m) { 3758 int i; 3759 ++malloc_corruption_error_count; 3760 /* Reinitialize fields to forget about all memory */ 3761 m->smallbins = m->treebins = 0; 3762 m->dvsize = m->topsize = 0; 3763 m->seg.base = 0; 3764 m->seg.size = 0; 3765 m->seg.next = 0; 3766 m->top = m->dv = 0; 3767 for (i = 0; i < NTREEBINS; ++i) 3768 *treebin_at(m, i) = 0; 3769 init_bins(m); 3770} 3771#endif /* PROCEED_ON_ERROR */ 3772 3773/* Allocate chunk and prepend remainder with chunk in successor base. */ 3774static void* prepend_alloc(mstate m, char* newbase, char* oldbase, 3775 size_t nb) { 3776 mchunkptr p = align_as_chunk(newbase); 3777 mchunkptr oldfirst = align_as_chunk(oldbase); 3778 size_t psize = (char*)oldfirst - (char*)p; 3779 mchunkptr q = chunk_plus_offset(p, nb); 3780 size_t qsize = psize - nb; 3781 set_size_and_pinuse_of_inuse_chunk(m, p, nb); 3782 3783 assert((char*)oldfirst > (char*)q); 3784 assert(pinuse(oldfirst)); 3785 assert(qsize >= MIN_CHUNK_SIZE); 3786 3787 /* consolidate remainder with first chunk of old base */ 3788 if (oldfirst == m->top) { 3789 size_t tsize = m->topsize += qsize; 3790 m->top = q; 3791 q->head = tsize | PINUSE_BIT; 3792 check_top_chunk(m, q); 3793 } 3794 else if (oldfirst == m->dv) { 3795 size_t dsize = m->dvsize += qsize; 3796 m->dv = q; 3797 set_size_and_pinuse_of_free_chunk(q, dsize); 3798 } 3799 else { 3800 if (!is_inuse(oldfirst)) { 3801 size_t nsize = chunksize(oldfirst); 3802 unlink_chunk(m, oldfirst, nsize); 3803 oldfirst = chunk_plus_offset(oldfirst, nsize); 3804 qsize += nsize; 3805 } 3806 set_free_with_pinuse(q, qsize, oldfirst); 3807 insert_chunk(m, q, qsize); 3808 check_free_chunk(m, q); 3809 } 3810 3811 check_malloced_chunk(m, chunk2mem(p), nb); 3812 return chunk2mem(p); 3813} 3814 3815/* Add a segment to hold a new noncontiguous region */ 3816static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) { 3817 /* Determine locations and sizes of segment, fenceposts, old top */ 3818 char* old_top = (char*)m->top; 3819 msegmentptr oldsp = segment_holding(m, old_top); 3820 char* old_end = oldsp->base + oldsp->size; 3821 size_t ssize = pad_request(sizeof(struct malloc_segment)); 3822 char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK); 3823 size_t offset = align_offset(chunk2mem(rawsp)); 3824 char* asp = rawsp + offset; 3825 char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp; 3826 mchunkptr sp = (mchunkptr)csp; 3827 msegmentptr ss = (msegmentptr)(chunk2mem(sp)); 3828 mchunkptr tnext = chunk_plus_offset(sp, ssize); 3829 mchunkptr p = tnext; 3830 int nfences = 0; 3831 3832 /* reset top to new space */ 3833 init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE); 3834 3835 /* Set up segment record */ 3836 assert(is_aligned(ss)); 3837 set_size_and_pinuse_of_inuse_chunk(m, sp, ssize); 3838 *ss = m->seg; /* Push current record */ 3839 m->seg.base = tbase; 3840 m->seg.size = tsize; 3841 m->seg.sflags = mmapped; 3842 m->seg.next = ss; 3843 3844 /* Insert trailing fenceposts */ 3845 for (;;) { 3846 mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE); 3847 p->head = FENCEPOST_HEAD; 3848 ++nfences; 3849 if ((char*)(&(nextp->head)) < old_end) 3850 p = nextp; 3851 else 3852 break; 3853 } 3854 assert(nfences >= 2); 3855 3856 /* Insert the rest of old top into a bin as an ordinary free chunk */ 3857 if (csp != old_top) { 3858 mchunkptr q = (mchunkptr)old_top; 3859 size_t psize = csp - old_top; 3860 mchunkptr tn = chunk_plus_offset(q, psize); 3861 set_free_with_pinuse(q, psize, tn); 3862 insert_chunk(m, q, psize); 3863 } 3864 3865 check_top_chunk(m, m->top); 3866} 3867 3868/* -------------------------- System allocation -------------------------- */ 3869 3870/* Get memory from system using MORECORE or MMAP */ 3871static void* sys_alloc(mstate m, size_t nb) { 3872 char* tbase = CMFAIL; 3873 size_t tsize = 0; 3874 flag_t mmap_flag = 0; 3875 3876 ensure_initialization(); 3877 3878 /* Directly map large chunks, but only if already initialized */ 3879 if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) { 3880 void* mem = mmap_alloc(m, nb); 3881 if (mem != 0) 3882 return mem; 3883 } 3884 3885 /* 3886 Try getting memory in any of three ways (in most-preferred to 3887 least-preferred order): 3888 1. A call to MORECORE that can normally contiguously extend memory. 3889 (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or 3890 or main space is mmapped or a previous contiguous call failed) 3891 2. A call to MMAP new space (disabled if not HAVE_MMAP). 3892 Note that under the default settings, if MORECORE is unable to 3893 fulfill a request, and HAVE_MMAP is true, then mmap is 3894 used as a noncontiguous system allocator. This is a useful backup 3895 strategy for systems with holes in address spaces -- in this case 3896 sbrk cannot contiguously expand the heap, but mmap may be able to 3897 find space. 3898 3. A call to MORECORE that cannot usually contiguously extend memory. 3899 (disabled if not HAVE_MORECORE) 3900 3901 In all cases, we need to request enough bytes from system to ensure 3902 we can malloc nb bytes upon success, so pad with enough space for 3903 top_foot, plus alignment-pad to make sure we don't lose bytes if 3904 not on boundary, and round this up to a granularity unit. 3905 */ 3906 3907 if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) { 3908 char* br = CMFAIL; 3909 msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top); 3910 size_t asize = 0; 3911 ACQUIRE_MALLOC_GLOBAL_LOCK(); 3912 3913 if (ss == 0) { /* First time through or recovery */ 3914 char* base = (char*)CALL_MORECORE(0); 3915 if (base != CMFAIL) { 3916 asize = granularity_align(nb + SYS_ALLOC_PADDING); 3917 /* Adjust to end on a page boundary */ 3918 if (!is_page_aligned(base)) 3919 asize += (page_align((size_t)base) - (size_t)base); 3920 /* Can't call MORECORE if size is negative when treated as signed */ 3921 if (asize < HALF_MAX_SIZE_T && 3922 (br = (char*)(CALL_MORECORE(asize))) == base) { 3923 tbase = base; 3924 tsize = asize; 3925 } 3926 } 3927 } 3928 else { 3929 /* Subtract out existing available top space from MORECORE request. */ 3930 asize = granularity_align(nb - m->topsize + SYS_ALLOC_PADDING); 3931 /* Use mem here only if it did continuously extend old space */ 3932 if (asize < HALF_MAX_SIZE_T && 3933 (br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) { 3934 tbase = br; 3935 tsize = asize; 3936 } 3937 } 3938 3939 if (tbase == CMFAIL) { /* Cope with partial failure */ 3940 if (br != CMFAIL) { /* Try to use/extend the space we did get */ 3941 if (asize < HALF_MAX_SIZE_T && 3942 asize < nb + SYS_ALLOC_PADDING) { 3943 size_t esize = granularity_align(nb + SYS_ALLOC_PADDING - asize); 3944 if (esize < HALF_MAX_SIZE_T) { 3945 char* end = (char*)CALL_MORECORE(esize); 3946 if (end != CMFAIL) 3947 asize += esize; 3948 else { /* Can't use; try to release */ 3949 (void) CALL_MORECORE(-asize); 3950 br = CMFAIL; 3951 } 3952 } 3953 } 3954 } 3955 if (br != CMFAIL) { /* Use the space we did get */ 3956 tbase = br; 3957 tsize = asize; 3958 } 3959 else 3960 disable_contiguous(m); /* Don't try contiguous path in the future */ 3961 } 3962 3963 RELEASE_MALLOC_GLOBAL_LOCK(); 3964 } 3965 3966 if (HAVE_MMAP && tbase == CMFAIL) { /* Try MMAP */ 3967 size_t rsize = granularity_align(nb + SYS_ALLOC_PADDING); 3968 if (rsize > nb) { /* Fail if wraps around zero */ 3969 char* mp = (char*)(CALL_MMAP(rsize)); 3970 if (mp != CMFAIL) { 3971 tbase = mp; 3972 tsize = rsize; 3973 mmap_flag = USE_MMAP_BIT; 3974 } 3975 } 3976 } 3977 3978 if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */ 3979 size_t asize = granularity_align(nb + SYS_ALLOC_PADDING); 3980 if (asize < HALF_MAX_SIZE_T) { 3981 char* br = CMFAIL; 3982 char* end = CMFAIL; 3983 ACQUIRE_MALLOC_GLOBAL_LOCK(); 3984 br = (char*)(CALL_MORECORE(asize)); 3985 end = (char*)(CALL_MORECORE(0)); 3986 RELEASE_MALLOC_GLOBAL_LOCK(); 3987 if (br != CMFAIL && end != CMFAIL && br < end) { 3988 size_t ssize = end - br; 3989 if (ssize > nb + TOP_FOOT_SIZE) { 3990 tbase = br; 3991 tsize = ssize; 3992 } 3993 } 3994 } 3995 } 3996 3997 if (tbase != CMFAIL) { 3998 3999 if ((m->footprint += tsize) > m->max_footprint) 4000 m->max_footprint = m->footprint; 4001 4002 if (!is_initialized(m)) { /* first-time initialization */ 4003 if (m->least_addr == 0 || tbase < m->least_addr) 4004 m->least_addr = tbase; 4005 m->seg.base = tbase; 4006 m->seg.size = tsize; 4007 m->seg.sflags = mmap_flag; 4008 m->magic = mparams.magic; 4009 m->release_checks = MAX_RELEASE_CHECK_RATE; 4010 init_bins(m); 4011#if !ONLY_MSPACES 4012 if (is_global(m)) 4013 init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE); 4014 else 4015#endif 4016 { 4017 /* Offset top by embedded malloc_state */ 4018 mchunkptr mn = next_chunk(mem2chunk(m)); 4019 init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE); 4020 } 4021 } 4022 4023 else { 4024 /* Try to merge with an existing segment */ 4025 msegmentptr sp = &m->seg; 4026 /* Only consider most recent segment if traversal suppressed */ 4027 while (sp != 0 && tbase != sp->base + sp->size) 4028 sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next; 4029 if (sp != 0 && 4030 !is_extern_segment(sp) && 4031 (sp->sflags & USE_MMAP_BIT) == mmap_flag && 4032 segment_holds(sp, m->top)) { /* append */ 4033 sp->size += tsize; 4034 init_top(m, m->top, m->topsize + tsize); 4035 } 4036 else { 4037 if (tbase < m->least_addr) 4038 m->least_addr = tbase; 4039 sp = &m->seg; 4040 while (sp != 0 && sp->base != tbase + tsize) 4041 sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next; 4042 if (sp != 0 && 4043 !is_extern_segment(sp) && 4044 (sp->sflags & USE_MMAP_BIT) == mmap_flag) { 4045 char* oldbase = sp->base; 4046 sp->base = tbase; 4047 sp->size += tsize; 4048 return prepend_alloc(m, tbase, oldbase, nb); 4049 } 4050 else 4051 add_segment(m, tbase, tsize, mmap_flag); 4052 } 4053 } 4054 4055 if (nb < m->topsize) { /* Allocate from new or extended top space */ 4056 size_t rsize = m->topsize -= nb; 4057 mchunkptr p = m->top; 4058 mchunkptr r = m->top = chunk_plus_offset(p, nb); 4059 r->head = rsize | PINUSE_BIT; 4060 set_size_and_pinuse_of_inuse_chunk(m, p, nb); 4061 check_top_chunk(m, m->top); 4062 check_malloced_chunk(m, chunk2mem(p), nb); 4063 return chunk2mem(p); 4064 } 4065 } 4066 4067 MALLOC_FAILURE_ACTION; 4068 return 0; 4069} 4070 4071/* ----------------------- system deallocation -------------------------- */ 4072 4073/* Unmap and unlink any mmapped segments that don't contain used chunks */ 4074static size_t release_unused_segments(mstate m) { 4075 size_t released = 0; 4076 int nsegs = 0; 4077 msegmentptr pred = &m->seg; 4078 msegmentptr sp = pred->next; 4079 while (sp != 0) { 4080 char* base = sp->base; 4081 size_t size = sp->size; 4082 msegmentptr next = sp->next; 4083 ++nsegs; 4084 if (is_mmapped_segment(sp) && !is_extern_segment(sp)) { 4085 mchunkptr p = align_as_chunk(base); 4086 size_t psize = chunksize(p); 4087 /* Can unmap if first chunk holds entire segment and not pinned */ 4088 if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) { 4089 tchunkptr tp = (tchunkptr)p; 4090 assert(segment_holds(sp, (char*)sp)); 4091 if (p == m->dv) { 4092 m->dv = 0; 4093 m->dvsize = 0; 4094 } 4095 else { 4096 unlink_large_chunk(m, tp); 4097 } 4098 if (CALL_MUNMAP(base, size) == 0) { 4099 released += size; 4100 m->footprint -= size; 4101 /* unlink obsoleted record */ 4102 sp = pred; 4103 sp->next = next; 4104 } 4105 else { /* back out if cannot unmap */ 4106 insert_large_chunk(m, tp, psize); 4107 } 4108 } 4109 } 4110 if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */ 4111 break; 4112 pred = sp; 4113 sp = next; 4114 } 4115 /* Reset check counter */ 4116 m->release_checks = ((nsegs > MAX_RELEASE_CHECK_RATE)? 4117 nsegs : MAX_RELEASE_CHECK_RATE); 4118 return released; 4119} 4120 4121static int sys_trim(mstate m, size_t pad) { 4122 size_t released = 0; 4123 ensure_initialization(); 4124 if (pad < MAX_REQUEST && is_initialized(m)) { 4125 pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */ 4126 4127 if (m->topsize > pad) { 4128 /* Shrink top space in granularity-size units, keeping at least one */ 4129 size_t unit = mparams.granularity; 4130 size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit - 4131 SIZE_T_ONE) * unit; 4132 msegmentptr sp = segment_holding(m, (char*)m->top); 4133 4134 if (!is_extern_segment(sp)) { 4135 if (is_mmapped_segment(sp)) { 4136 if (HAVE_MMAP && 4137 sp->size >= extra && 4138 !has_segment_link(m, sp)) { /* can't shrink if pinned */ 4139 size_t newsize = sp->size - extra; 4140 /* Prefer mremap, fall back to munmap */ 4141 if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) || 4142 (CALL_MUNMAP(sp->base + newsize, extra) == 0)) { 4143 released = extra; 4144 } 4145 } 4146 } 4147 else if (HAVE_MORECORE) { 4148 if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */ 4149 extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit; 4150 ACQUIRE_MALLOC_GLOBAL_LOCK(); 4151 { 4152 /* Make sure end of memory is where we last set it. */ 4153 char* old_br = (char*)(CALL_MORECORE(0)); 4154 if (old_br == sp->base + sp->size) { 4155 char* rel_br = (char*)(CALL_MORECORE(-extra)); 4156 char* new_br = (char*)(CALL_MORECORE(0)); 4157 if (rel_br != CMFAIL && new_br < old_br) 4158 released = old_br - new_br; 4159 } 4160 } 4161 RELEASE_MALLOC_GLOBAL_LOCK(); 4162 } 4163 } 4164 4165 if (released != 0) { 4166 sp->size -= released; 4167 m->footprint -= released; 4168 init_top(m, m->top, m->topsize - released); 4169 check_top_chunk(m, m->top); 4170 } 4171 } 4172 4173 /* Unmap any unused mmapped segments */ 4174 if (HAVE_MMAP) 4175 released += release_unused_segments(m); 4176 4177 /* On failure, disable autotrim to avoid repeated failed future calls */ 4178 if (released == 0 && m->topsize > m->trim_check) 4179 m->trim_check = MAX_SIZE_T; 4180 } 4181 4182 return (released != 0)? 1 : 0; 4183} 4184 4185 4186/* ---------------------------- malloc support --------------------------- */ 4187 4188/* allocate a large request from the best fitting chunk in a treebin */ 4189static void* tmalloc_large(mstate m, size_t nb) { 4190 tchunkptr v = 0; 4191 size_t rsize = -nb; /* Unsigned negation */ 4192 tchunkptr t; 4193 bindex_t idx; 4194 compute_tree_index(nb, idx); 4195 if ((t = *treebin_at(m, idx)) != 0) { 4196 /* Traverse tree for this bin looking for node with size == nb */ 4197 size_t sizebits = nb << leftshift_for_tree_index(idx); 4198 tchunkptr rst = 0; /* The deepest untaken right subtree */ 4199 for (;;) { 4200 tchunkptr rt; 4201 size_t trem = chunksize(t) - nb; 4202 if (trem < rsize) { 4203 v = t; 4204 if ((rsize = trem) == 0) 4205 break; 4206 } 4207 rt = t->child[1]; 4208 t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]; 4209 if (rt != 0 && rt != t) 4210 rst = rt; 4211 if (t == 0) { 4212 t = rst; /* set t to least subtree holding sizes > nb */ 4213 break; 4214 } 4215 sizebits <<= 1; 4216 } 4217 } 4218 if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */ 4219 binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap; 4220 if (leftbits != 0) { 4221 bindex_t i; 4222 binmap_t leastbit = least_bit(leftbits); 4223 compute_bit2idx(leastbit, i); 4224 t = *treebin_at(m, i); 4225 } 4226 } 4227 4228 while (t != 0) { /* find smallest of tree or subtree */ 4229 size_t trem = chunksize(t) - nb; 4230 if (trem < rsize) { 4231 rsize = trem; 4232 v = t; 4233 } 4234 t = leftmost_child(t); 4235 } 4236 4237 /* If dv is a better fit, return 0 so malloc will use it */ 4238 if (v != 0 && rsize < (size_t)(m->dvsize - nb)) { 4239 if (RTCHECK(ok_address(m, v))) { /* split */ 4240 mchunkptr r = chunk_plus_offset(v, nb); 4241 assert(chunksize(v) == rsize + nb); 4242 if (RTCHECK(ok_next(v, r))) { 4243 unlink_large_chunk(m, v); 4244 if (rsize < MIN_CHUNK_SIZE) 4245 set_inuse_and_pinuse(m, v, (rsize + nb)); 4246 else { 4247 set_size_and_pinuse_of_inuse_chunk(m, v, nb); 4248 set_size_and_pinuse_of_free_chunk(r, rsize); 4249 insert_chunk(m, r, rsize); 4250 } 4251 return chunk2mem(v); 4252 } 4253 } 4254 CORRUPTION_ERROR_ACTION(m); 4255 } 4256 return 0; 4257} 4258 4259/* allocate a small request from the best fitting chunk in a treebin */ 4260static void* tmalloc_small(mstate m, size_t nb) { 4261 tchunkptr t, v; 4262 size_t rsize; 4263 bindex_t i; 4264 binmap_t leastbit = least_bit(m->treemap); 4265 compute_bit2idx(leastbit, i); 4266 v = t = *treebin_at(m, i); 4267 rsize = chunksize(t) - nb; 4268 4269 while ((t = leftmost_child(t)) != 0) { 4270 size_t trem = chunksize(t) - nb; 4271 if (trem < rsize) { 4272 rsize = trem; 4273 v = t; 4274 } 4275 } 4276 4277 if (RTCHECK(ok_address(m, v))) { 4278 mchunkptr r = chunk_plus_offset(v, nb); 4279 assert(chunksize(v) == rsize + nb); 4280 if (RTCHECK(ok_next(v, r))) { 4281 unlink_large_chunk(m, v); 4282 if (rsize < MIN_CHUNK_SIZE) 4283 set_inuse_and_pinuse(m, v, (rsize + nb)); 4284 else { 4285 set_size_and_pinuse_of_inuse_chunk(m, v, nb); 4286 set_size_and_pinuse_of_free_chunk(r, rsize); 4287 replace_dv(m, r, rsize); 4288 } 4289 return chunk2mem(v); 4290 } 4291 } 4292 4293 CORRUPTION_ERROR_ACTION(m); 4294 return 0; 4295} 4296 4297/* --------------------------- realloc support --------------------------- */ 4298 4299static void* internal_realloc(mstate m, void* oldmem, size_t bytes) { 4300 if (bytes >= MAX_REQUEST) { 4301 MALLOC_FAILURE_ACTION; 4302 return 0; 4303 } 4304 if (!PREACTION(m)) { 4305 mchunkptr oldp = mem2chunk(oldmem); 4306 size_t oldsize = chunksize(oldp); 4307 mchunkptr next = chunk_plus_offset(oldp, oldsize); 4308 mchunkptr newp = 0; 4309 void* extra = 0; 4310 4311 /* Try to either shrink or extend into top. Else malloc-copy-free */ 4312 4313 if (RTCHECK(ok_address(m, oldp) && ok_inuse(oldp) && 4314 ok_next(oldp, next) && ok_pinuse(next))) { 4315 size_t nb = request2size(bytes); 4316 if (is_mmapped(oldp)) 4317 newp = mmap_resize(m, oldp, nb); 4318 else if (oldsize >= nb) { /* already big enough */ 4319 size_t rsize = oldsize - nb; 4320 newp = oldp; 4321 if (rsize >= MIN_CHUNK_SIZE) { 4322 mchunkptr remainder = chunk_plus_offset(newp, nb); 4323 set_inuse(m, newp, nb); 4324 set_inuse_and_pinuse(m, remainder, rsize); 4325 extra = chunk2mem(remainder); 4326 } 4327 } 4328 else if (next == m->top && oldsize + m->topsize > nb) { 4329 /* Expand into top */ 4330 size_t newsize = oldsize + m->topsize; 4331 size_t newtopsize = newsize - nb; 4332 mchunkptr newtop = chunk_plus_offset(oldp, nb); 4333 set_inuse(m, oldp, nb); 4334 newtop->head = newtopsize |PINUSE_BIT; 4335 m->top = newtop; 4336 m->topsize = newtopsize; 4337 newp = oldp; 4338 } 4339 } 4340 else { 4341 USAGE_ERROR_ACTION(m, oldmem); 4342 POSTACTION(m); 4343 return 0; 4344 } 4345#if DEBUG 4346 if (newp != 0) { 4347 check_inuse_chunk(m, newp); /* Check requires lock */ 4348 } 4349#endif 4350 4351 POSTACTION(m); 4352 4353 if (newp != 0) { 4354 if (extra != 0) { 4355 internal_free(m, extra); 4356 } 4357 return chunk2mem(newp); 4358 } 4359 else { 4360 void* newmem = internal_malloc(m, bytes); 4361 if (newmem != 0) { 4362 size_t oc = oldsize - overhead_for(oldp); 4363 memcpy(newmem, oldmem, (oc < bytes)? oc : bytes); 4364 internal_free(m, oldmem); 4365 } 4366 return newmem; 4367 } 4368 } 4369 return 0; 4370} 4371 4372/* --------------------------- memalign support -------------------------- */ 4373 4374static void* internal_memalign(mstate m, size_t alignment, size_t bytes) { 4375 if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */ 4376 return internal_malloc(m, bytes); 4377 if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */ 4378 alignment = MIN_CHUNK_SIZE; 4379 if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */ 4380 size_t a = MALLOC_ALIGNMENT << 1; 4381 while (a < alignment) a <<= 1; 4382 alignment = a; 4383 } 4384 4385 if (bytes >= MAX_REQUEST - alignment) { 4386 if (m != 0) { /* Test isn't needed but avoids compiler warning */ 4387 MALLOC_FAILURE_ACTION; 4388 } 4389 } 4390 else { 4391 size_t nb = request2size(bytes); 4392 size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD; 4393 char* mem = (char*)internal_malloc(m, req); 4394 if (mem != 0) { 4395 void* leader = 0; 4396 void* trailer = 0; 4397 mchunkptr p = mem2chunk(mem); 4398 4399 if (PREACTION(m)) return 0; 4400 if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */ 4401 /* 4402 Find an aligned spot inside chunk. Since we need to give 4403 back leading space in a chunk of at least MIN_CHUNK_SIZE, if 4404 the first calculation places us at a spot with less than 4405 MIN_CHUNK_SIZE leader, we can move to the next aligned spot. 4406 We've allocated enough total room so that this is always 4407 possible. 4408 */ 4409 char* br = (char*)mem2chunk((size_t)(((size_t)(mem + 4410 alignment - 4411 SIZE_T_ONE)) & 4412 -alignment)); 4413 char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)? 4414 br : br+alignment; 4415 mchunkptr newp = (mchunkptr)pos; 4416 size_t leadsize = pos - (char*)(p); 4417 size_t newsize = chunksize(p) - leadsize; 4418 4419 if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */ 4420 newp->prev_foot = p->prev_foot + leadsize; 4421 newp->head = newsize; 4422 } 4423 else { /* Otherwise, give back leader, use the rest */ 4424 set_inuse(m, newp, newsize); 4425 set_inuse(m, p, leadsize); 4426 leader = chunk2mem(p); 4427 } 4428 p = newp; 4429 } 4430 4431 /* Give back spare room at the end */ 4432 if (!is_mmapped(p)) { 4433 size_t size = chunksize(p); 4434 if (size > nb + MIN_CHUNK_SIZE) { 4435 size_t remainder_size = size - nb; 4436 mchunkptr remainder = chunk_plus_offset(p, nb); 4437 set_inuse(m, p, nb); 4438 set_inuse(m, remainder, remainder_size); 4439 trailer = chunk2mem(remainder); 4440 } 4441 } 4442 4443 assert (chunksize(p) >= nb); 4444 assert((((size_t)(chunk2mem(p))) % alignment) == 0); 4445 check_inuse_chunk(m, p); 4446 POSTACTION(m); 4447 if (leader != 0) { 4448 internal_free(m, leader); 4449 } 4450 if (trailer != 0) { 4451 internal_free(m, trailer); 4452 } 4453 return chunk2mem(p); 4454 } 4455 } 4456 return 0; 4457} 4458 4459/* ------------------------ comalloc/coalloc support --------------------- */ 4460 4461static void** ialloc(mstate m, 4462 size_t n_elements, 4463 size_t* sizes, 4464 int opts, 4465 void* chunks[]) { 4466 /* 4467 This provides common support for independent_X routines, handling 4468 all of the combinations that can result. 4469 4470 The opts arg has: 4471 bit 0 set if all elements are same size (using sizes[0]) 4472 bit 1 set if elements should be zeroed 4473 */ 4474 4475 size_t element_size; /* chunksize of each element, if all same */ 4476 size_t contents_size; /* total size of elements */ 4477 size_t array_size; /* request size of pointer array */ 4478 void* mem; /* malloced aggregate space */ 4479 mchunkptr p; /* corresponding chunk */ 4480 size_t remainder_size; /* remaining bytes while splitting */ 4481 void** marray; /* either "chunks" or malloced ptr array */ 4482 mchunkptr array_chunk; /* chunk for malloced ptr array */ 4483 flag_t was_enabled; /* to disable mmap */ 4484 size_t size; 4485 size_t i; 4486 4487 ensure_initialization(); 4488 /* compute array length, if needed */ 4489 if (chunks != 0) { 4490 if (n_elements == 0) 4491 return chunks; /* nothing to do */ 4492 marray = chunks; 4493 array_size = 0; 4494 } 4495 else { 4496 /* if empty req, must still return chunk representing empty array */ 4497 if (n_elements == 0) 4498 return (void**)internal_malloc(m, 0); 4499 marray = 0; 4500 array_size = request2size(n_elements * (sizeof(void*))); 4501 } 4502 4503 /* compute total element size */ 4504 if (opts & 0x1) { /* all-same-size */ 4505 element_size = request2size(*sizes); 4506 contents_size = n_elements * element_size; 4507 } 4508 else { /* add up all the sizes */ 4509 element_size = 0; 4510 contents_size = 0; 4511 for (i = 0; i != n_elements; ++i) 4512 contents_size += request2size(sizes[i]); 4513 } 4514 4515 size = contents_size + array_size; 4516 4517 /* 4518 Allocate the aggregate chunk. First disable direct-mmapping so 4519 malloc won't use it, since we would not be able to later 4520 free/realloc space internal to a segregated mmap region. 4521 */ 4522 was_enabled = use_mmap(m); 4523 disable_mmap(m); 4524 mem = internal_malloc(m, size - CHUNK_OVERHEAD); 4525 if (was_enabled) 4526 enable_mmap(m); 4527 if (mem == 0) 4528 return 0; 4529 4530 if (PREACTION(m)) return 0; 4531 p = mem2chunk(mem); 4532 remainder_size = chunksize(p); 4533 4534 assert(!is_mmapped(p)); 4535 4536 if (opts & 0x2) { /* optionally clear the elements */ 4537 memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size); 4538 } 4539 4540 /* If not provided, allocate the pointer array as final part of chunk */ 4541 if (marray == 0) { 4542 size_t array_chunk_size; 4543 array_chunk = chunk_plus_offset(p, contents_size); 4544 array_chunk_size = remainder_size - contents_size; 4545 marray = (void**) (chunk2mem(array_chunk)); 4546 set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size); 4547 remainder_size = contents_size; 4548 } 4549 4550 /* split out elements */ 4551 for (i = 0; ; ++i) { 4552 marray[i] = chunk2mem(p); 4553 if (i != n_elements-1) { 4554 if (element_size != 0) 4555 size = element_size; 4556 else 4557 size = request2size(sizes[i]); 4558 remainder_size -= size; 4559 set_size_and_pinuse_of_inuse_chunk(m, p, size); 4560 p = chunk_plus_offset(p, size); 4561 } 4562 else { /* the final element absorbs any overallocation slop */ 4563 set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size); 4564 break; 4565 } 4566 } 4567 4568#if DEBUG 4569 if (marray != chunks) { 4570 /* final element must have exactly exhausted chunk */ 4571 if (element_size != 0) { 4572 assert(remainder_size == element_size); 4573 } 4574 else { 4575 assert(remainder_size == request2size(sizes[i])); 4576 } 4577 check_inuse_chunk(m, mem2chunk(marray)); 4578 } 4579 for (i = 0; i != n_elements; ++i) 4580 check_inuse_chunk(m, mem2chunk(marray[i])); 4581 4582#endif /* DEBUG */ 4583 4584 POSTACTION(m); 4585 return marray; 4586} 4587 4588 4589/* -------------------------- public routines ---------------------------- */ 4590 4591#if !ONLY_MSPACES 4592 4593void* dlmalloc(size_t bytes) { 4594 /* 4595 Basic algorithm: 4596 If a small request (< 256 bytes minus per-chunk overhead): 4597 1. If one exists, use a remainderless chunk in associated smallbin. 4598 (Remainderless means that there are too few excess bytes to 4599 represent as a chunk.) 4600 2. If it is big enough, use the dv chunk, which is normally the 4601 chunk adjacent to the one used for the most recent small request. 4602 3. If one exists, split the smallest available chunk in a bin, 4603 saving remainder in dv. 4604 4. If it is big enough, use the top chunk. 4605 5. If available, get memory from system and use it 4606 Otherwise, for a large request: 4607 1. Find the smallest available binned chunk that fits, and use it 4608 if it is better fitting than dv chunk, splitting if necessary. 4609 2. If better fitting than any binned chunk, use the dv chunk. 4610 3. If it is big enough, use the top chunk. 4611 4. If request size >= mmap threshold, try to directly mmap this chunk. 4612 5. If available, get memory from system and use it 4613 4614 The ugly goto's here ensure that postaction occurs along all paths. 4615 */ 4616 4617#if USE_LOCKS 4618 ensure_initialization(); /* initialize in sys_alloc if not using locks */ 4619#endif 4620 4621 if (!PREACTION(gm)) { 4622 void* mem; 4623 size_t nb; 4624 if (bytes <= MAX_SMALL_REQUEST) { 4625 bindex_t idx; 4626 binmap_t smallbits; 4627 nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes); 4628 idx = small_index(nb); 4629 smallbits = gm->smallmap >> idx; 4630 4631 if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */ 4632 mchunkptr b, p; 4633 idx += ~smallbits & 1; /* Uses next bin if idx empty */ 4634 b = smallbin_at(gm, idx); 4635 p = b->fd; 4636 assert(chunksize(p) == small_index2size(idx)); 4637 unlink_first_small_chunk(gm, b, p, idx); 4638 set_inuse_and_pinuse(gm, p, small_index2size(idx)); 4639 mem = chunk2mem(p); 4640 check_malloced_chunk(gm, mem, nb); 4641 goto postaction; 4642 } 4643 4644 else if (nb > gm->dvsize) { 4645 if (smallbits != 0) { /* Use chunk in next nonempty smallbin */ 4646 mchunkptr b, p, r; 4647 size_t rsize; 4648 bindex_t i; 4649 binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx)); 4650 binmap_t leastbit = least_bit(leftbits); 4651 compute_bit2idx(leastbit, i); 4652 b = smallbin_at(gm, i); 4653 p = b->fd; 4654 assert(chunksize(p) == small_index2size(i)); 4655 unlink_first_small_chunk(gm, b, p, i); 4656 rsize = small_index2size(i) - nb; 4657 /* Fit here cannot be remainderless if 4byte sizes */ 4658 if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE) 4659 set_inuse_and_pinuse(gm, p, small_index2size(i)); 4660 else { 4661 set_size_and_pinuse_of_inuse_chunk(gm, p, nb); 4662 r = chunk_plus_offset(p, nb); 4663 set_size_and_pinuse_of_free_chunk(r, rsize); 4664 replace_dv(gm, r, rsize); 4665 } 4666 mem = chunk2mem(p); 4667 check_malloced_chunk(gm, mem, nb); 4668 goto postaction; 4669 } 4670 4671 else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) { 4672 check_malloced_chunk(gm, mem, nb); 4673 goto postaction; 4674 } 4675 } 4676 } 4677 else if (bytes >= MAX_REQUEST) 4678 nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */ 4679 else { 4680 nb = pad_request(bytes); 4681 if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) { 4682 check_malloced_chunk(gm, mem, nb); 4683 goto postaction; 4684 } 4685 } 4686 4687 if (nb <= gm->dvsize) { 4688 size_t rsize = gm->dvsize - nb; 4689 mchunkptr p = gm->dv; 4690 if (rsize >= MIN_CHUNK_SIZE) { /* split dv */ 4691 mchunkptr r = gm->dv = chunk_plus_offset(p, nb); 4692 gm->dvsize = rsize; 4693 set_size_and_pinuse_of_free_chunk(r, rsize); 4694 set_size_and_pinuse_of_inuse_chunk(gm, p, nb); 4695 } 4696 else { /* exhaust dv */ 4697 size_t dvs = gm->dvsize; 4698 gm->dvsize = 0; 4699 gm->dv = 0; 4700 set_inuse_and_pinuse(gm, p, dvs); 4701 } 4702 mem = chunk2mem(p); 4703 check_malloced_chunk(gm, mem, nb); 4704 goto postaction; 4705 } 4706 4707 else if (nb < gm->topsize) { /* Split top */ 4708 size_t rsize = gm->topsize -= nb; 4709 mchunkptr p = gm->top; 4710 mchunkptr r = gm->top = chunk_plus_offset(p, nb); 4711 r->head = rsize | PINUSE_BIT; 4712 set_size_and_pinuse_of_inuse_chunk(gm, p, nb); 4713 mem = chunk2mem(p); 4714 check_top_chunk(gm, gm->top); 4715 check_malloced_chunk(gm, mem, nb); 4716 goto postaction; 4717 } 4718 4719 mem = sys_alloc(gm, nb); 4720 4721 postaction: 4722 POSTACTION(gm); 4723 return mem; 4724 } 4725 4726 return 0; 4727} 4728 4729void dlfree(void* mem) { 4730 /* 4731 Consolidate freed chunks with preceeding or succeeding bordering 4732 free chunks, if they exist, and then place in a bin. Intermixed 4733 with special cases for top, dv, mmapped chunks, and usage errors. 4734 */ 4735 4736 if (mem != 0) { 4737 mchunkptr p = mem2chunk(mem); 4738#if FOOTERS 4739 mstate fm = get_mstate_for(p); 4740 if (!ok_magic(fm)) { 4741 USAGE_ERROR_ACTION(fm, p); 4742 return; 4743 } 4744#else /* FOOTERS */ 4745#define fm gm 4746#endif /* FOOTERS */ 4747 if (!PREACTION(fm)) { 4748 check_inuse_chunk(fm, p); 4749 if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) { 4750 size_t psize = chunksize(p); 4751 mchunkptr next = chunk_plus_offset(p, psize); 4752 if (!pinuse(p)) { 4753 size_t prevsize = p->prev_foot; 4754 if (is_mmapped(p)) { 4755 psize += prevsize + MMAP_FOOT_PAD; 4756 if (CALL_MUNMAP((char*)p - prevsize, psize) == 0) 4757 fm->footprint -= psize; 4758 goto postaction; 4759 } 4760 else { 4761 mchunkptr prev = chunk_minus_offset(p, prevsize); 4762 psize += prevsize; 4763 p = prev; 4764 if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */ 4765 if (p != fm->dv) { 4766 unlink_chunk(fm, p, prevsize); 4767 } 4768 else if ((next->head & INUSE_BITS) == INUSE_BITS) { 4769 fm->dvsize = psize; 4770 set_free_with_pinuse(p, psize, next); 4771 goto postaction; 4772 } 4773 } 4774 else 4775 goto erroraction; 4776 } 4777 } 4778 4779 if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) { 4780 if (!cinuse(next)) { /* consolidate forward */ 4781 if (next == fm->top) { 4782 size_t tsize = fm->topsize += psize; 4783 fm->top = p; 4784 p->head = tsize | PINUSE_BIT; 4785 if (p == fm->dv) { 4786 fm->dv = 0; 4787 fm->dvsize = 0; 4788 } 4789 if (should_trim(fm, tsize)) 4790 sys_trim(fm, 0); 4791 goto postaction; 4792 } 4793 else if (next == fm->dv) { 4794 size_t dsize = fm->dvsize += psize; 4795 fm->dv = p; 4796 set_size_and_pinuse_of_free_chunk(p, dsize); 4797 goto postaction; 4798 } 4799 else { 4800 size_t nsize = chunksize(next); 4801 psize += nsize; 4802 unlink_chunk(fm, next, nsize); 4803 set_size_and_pinuse_of_free_chunk(p, psize); 4804 if (p == fm->dv) { 4805 fm->dvsize = psize; 4806 goto postaction; 4807 } 4808 } 4809 } 4810 else 4811 set_free_with_pinuse(p, psize, next); 4812 4813 if (is_small(psize)) { 4814 insert_small_chunk(fm, p, psize); 4815 check_free_chunk(fm, p); 4816 } 4817 else { 4818 tchunkptr tp = (tchunkptr)p; 4819 insert_large_chunk(fm, tp, psize); 4820 check_free_chunk(fm, p); 4821 if (--fm->release_checks == 0) 4822 release_unused_segments(fm); 4823 } 4824 goto postaction; 4825 } 4826 } 4827 erroraction: 4828 USAGE_ERROR_ACTION(fm, p); 4829 postaction: 4830 POSTACTION(fm); 4831 } 4832 } 4833#if !FOOTERS 4834#undef fm 4835#endif /* FOOTERS */ 4836} 4837 4838void* dlcalloc(size_t n_elements, size_t elem_size) { 4839 void* mem; 4840 size_t req = 0; 4841 if (n_elements != 0) { 4842 req = n_elements * elem_size; 4843 if (((n_elements | elem_size) & ~(size_t)0xffff) && 4844 (req / n_elements != elem_size)) 4845 req = MAX_SIZE_T; /* force downstream failure on overflow */ 4846 } 4847 mem = dlmalloc(req); 4848 if (mem != 0 && calloc_must_clear(mem2chunk(mem))) 4849 memset(mem, 0, req); 4850 return mem; 4851} 4852 4853void* dlrealloc(void* oldmem, size_t bytes) { 4854 if (oldmem == 0) 4855 return dlmalloc(bytes); 4856#ifdef REALLOC_ZERO_BYTES_FREES 4857 if (bytes == 0) { 4858 dlfree(oldmem); 4859 return 0; 4860 } 4861#endif /* REALLOC_ZERO_BYTES_FREES */ 4862 else { 4863#if ! FOOTERS 4864 mstate m = gm; 4865#else /* FOOTERS */ 4866 mstate m = get_mstate_for(mem2chunk(oldmem)); 4867 if (!ok_magic(m)) { 4868 USAGE_ERROR_ACTION(m, oldmem); 4869 return 0; 4870 } 4871#endif /* FOOTERS */ 4872 return internal_realloc(m, oldmem, bytes); 4873 } 4874} 4875 4876void* dlmemalign(size_t alignment, size_t bytes) { 4877 return internal_memalign(gm, alignment, bytes); 4878} 4879 4880void** dlindependent_calloc(size_t n_elements, size_t elem_size, 4881 void* chunks[]) { 4882 size_t sz = elem_size; /* serves as 1-element array */ 4883 return ialloc(gm, n_elements, &sz, 3, chunks); 4884} 4885 4886void** dlindependent_comalloc(size_t n_elements, size_t sizes[], 4887 void* chunks[]) { 4888 return ialloc(gm, n_elements, sizes, 0, chunks); 4889} 4890 4891void* dlvalloc(size_t bytes) { 4892 size_t pagesz; 4893 ensure_initialization(); 4894 pagesz = mparams.page_size; 4895 return dlmemalign(pagesz, bytes); 4896} 4897 4898void* dlpvalloc(size_t bytes) { 4899 size_t pagesz; 4900 ensure_initialization(); 4901 pagesz = mparams.page_size; 4902 return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE)); 4903} 4904 4905int dlmalloc_trim(size_t pad) { 4906 int result = 0; 4907 ensure_initialization(); 4908 if (!PREACTION(gm)) { 4909 result = sys_trim(gm, pad); 4910 POSTACTION(gm); 4911 } 4912 return result; 4913} 4914 4915size_t dlmalloc_footprint(void) { 4916 return gm->footprint; 4917} 4918 4919size_t dlmalloc_max_footprint(void) { 4920 return gm->max_footprint; 4921} 4922 4923#if !NO_MALLINFO 4924struct mallinfo dlmallinfo(void) { 4925 return internal_mallinfo(gm); 4926} 4927#endif /* NO_MALLINFO */ 4928 4929void dlmalloc_stats() { 4930 internal_malloc_stats(gm); 4931} 4932 4933int dlmallopt(int param_number, int value) { 4934 return change_mparam(param_number, value); 4935} 4936 4937#endif /* !ONLY_MSPACES */ 4938 4939size_t dlmalloc_usable_size(void* mem) { 4940 if (mem != 0) { 4941 mchunkptr p = mem2chunk(mem); 4942 if (is_inuse(p)) 4943 return chunksize(p) - overhead_for(p); 4944 } 4945 return 0; 4946} 4947 4948/* ----------------------------- user mspaces ---------------------------- */ 4949 4950#if MSPACES 4951 4952static mstate init_user_mstate(char* tbase, size_t tsize) { 4953 size_t msize = pad_request(sizeof(struct malloc_state)); 4954 mchunkptr mn; 4955 mchunkptr msp = align_as_chunk(tbase); 4956 mstate m = (mstate)(chunk2mem(msp)); 4957 memset(m, 0, msize); 4958 INITIAL_LOCK(&m->mutex); 4959 msp->head = (msize|INUSE_BITS); 4960 m->seg.base = m->least_addr = tbase; 4961 m->seg.size = m->footprint = m->max_footprint = tsize; 4962 m->magic = mparams.magic; 4963 m->release_checks = MAX_RELEASE_CHECK_RATE; 4964 m->mflags = mparams.default_mflags; 4965 m->extp = 0; 4966 m->exts = 0; 4967 disable_contiguous(m); 4968 init_bins(m); 4969 mn = next_chunk(mem2chunk(m)); 4970 init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE); 4971 check_top_chunk(m, m->top); 4972 return m; 4973} 4974 4975mspace create_mspace(size_t capacity, int locked) { 4976 mstate m = 0; 4977 size_t msize; 4978 ensure_initialization(); 4979 msize = pad_request(sizeof(struct malloc_state)); 4980 if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) { 4981 size_t rs = ((capacity == 0)? mparams.granularity : 4982 (capacity + TOP_FOOT_SIZE + msize)); 4983 size_t tsize = granularity_align(rs); 4984 char* tbase = (char*)(CALL_MMAP(tsize)); 4985 if (tbase != CMFAIL) { 4986 m = init_user_mstate(tbase, tsize); 4987 m->seg.sflags = USE_MMAP_BIT; 4988 set_lock(m, locked); 4989 } 4990 } 4991 return (mspace)m; 4992} 4993 4994mspace create_mspace_with_base(void* base, size_t capacity, int locked) { 4995 mstate m = 0; 4996 size_t msize; 4997 ensure_initialization(); 4998 msize = pad_request(sizeof(struct malloc_state)); 4999 if (capacity > msize + TOP_FOOT_SIZE && 5000 capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) { 5001 m = init_user_mstate((char*)base, capacity); 5002 m->seg.sflags = EXTERN_BIT; 5003 set_lock(m, locked); 5004 } 5005 return (mspace)m; 5006} 5007 5008int mspace_track_large_chunks(mspace msp, int enable) { 5009 int ret = 0; 5010 mstate ms = (mstate)msp; 5011 if (!PREACTION(ms)) { 5012 if (!use_mmap(ms)) 5013 ret = 1; 5014 if (!enable) 5015 enable_mmap(ms); 5016 else 5017 disable_mmap(ms); 5018 POSTACTION(ms); 5019 } 5020 return ret; 5021} 5022 5023size_t destroy_mspace(mspace msp) { 5024 size_t freed = 0; 5025 mstate ms = (mstate)msp; 5026 if (ok_magic(ms)) { 5027 msegmentptr sp = &ms->seg; 5028 while (sp != 0) { 5029 char* base = sp->base; 5030 size_t size = sp->size; 5031 flag_t flag = sp->sflags; 5032 sp = sp->next; 5033 if ((flag & USE_MMAP_BIT) && !(flag & EXTERN_BIT) && 5034 CALL_MUNMAP(base, size) == 0) 5035 freed += size; 5036 } 5037 } 5038 else { 5039 USAGE_ERROR_ACTION(ms,ms); 5040 } 5041 return freed; 5042} 5043 5044/* 5045 mspace versions of routines are near-clones of the global 5046 versions. This is not so nice but better than the alternatives. 5047*/ 5048 5049 5050void* mspace_malloc(mspace msp, size_t bytes) { 5051 mstate ms = (mstate)msp; 5052 if (!ok_magic(ms)) { 5053 USAGE_ERROR_ACTION(ms,ms); 5054 return 0; 5055 } 5056 if (!PREACTION(ms)) { 5057 void* mem; 5058 size_t nb; 5059 if (bytes <= MAX_SMALL_REQUEST) { 5060 bindex_t idx; 5061 binmap_t smallbits; 5062 nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes); 5063 idx = small_index(nb); 5064 smallbits = ms->smallmap >> idx; 5065 5066 if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */ 5067 mchunkptr b, p; 5068 idx += ~smallbits & 1; /* Uses next bin if idx empty */ 5069 b = smallbin_at(ms, idx); 5070 p = b->fd; 5071 assert(chunksize(p) == small_index2size(idx)); 5072 unlink_first_small_chunk(ms, b, p, idx); 5073 set_inuse_and_pinuse(ms, p, small_index2size(idx)); 5074 mem = chunk2mem(p); 5075 check_malloced_chunk(ms, mem, nb); 5076 goto postaction; 5077 } 5078 5079 else if (nb > ms->dvsize) { 5080 if (smallbits != 0) { /* Use chunk in next nonempty smallbin */ 5081 mchunkptr b, p, r; 5082 size_t rsize; 5083 bindex_t i; 5084 binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx)); 5085 binmap_t leastbit = least_bit(leftbits); 5086 compute_bit2idx(leastbit, i); 5087 b = smallbin_at(ms, i); 5088 p = b->fd; 5089 assert(chunksize(p) == small_index2size(i)); 5090 unlink_first_small_chunk(ms, b, p, i); 5091 rsize = small_index2size(i) - nb; 5092 /* Fit here cannot be remainderless if 4byte sizes */ 5093 if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE) 5094 set_inuse_and_pinuse(ms, p, small_index2size(i)); 5095 else { 5096 set_size_and_pinuse_of_inuse_chunk(ms, p, nb); 5097 r = chunk_plus_offset(p, nb); 5098 set_size_and_pinuse_of_free_chunk(r, rsize); 5099 replace_dv(ms, r, rsize); 5100 } 5101 mem = chunk2mem(p); 5102 check_malloced_chunk(ms, mem, nb); 5103 goto postaction; 5104 } 5105 5106 else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) { 5107 check_malloced_chunk(ms, mem, nb); 5108 goto postaction; 5109 } 5110 } 5111 } 5112 else if (bytes >= MAX_REQUEST) 5113 nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */ 5114 else { 5115 nb = pad_request(bytes); 5116 if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) { 5117 check_malloced_chunk(ms, mem, nb); 5118 goto postaction; 5119 } 5120 } 5121 5122 if (nb <= ms->dvsize) { 5123 size_t rsize = ms->dvsize - nb; 5124 mchunkptr p = ms->dv; 5125 if (rsize >= MIN_CHUNK_SIZE) { /* split dv */ 5126 mchunkptr r = ms->dv = chunk_plus_offset(p, nb); 5127 ms->dvsize = rsize; 5128 set_size_and_pinuse_of_free_chunk(r, rsize); 5129 set_size_and_pinuse_of_inuse_chunk(ms, p, nb); 5130 } 5131 else { /* exhaust dv */ 5132 size_t dvs = ms->dvsize; 5133 ms->dvsize = 0; 5134 ms->dv = 0; 5135 set_inuse_and_pinuse(ms, p, dvs); 5136 } 5137 mem = chunk2mem(p); 5138 check_malloced_chunk(ms, mem, nb); 5139 goto postaction; 5140 } 5141 5142 else if (nb < ms->topsize) { /* Split top */ 5143 size_t rsize = ms->topsize -= nb; 5144 mchunkptr p = ms->top; 5145 mchunkptr r = ms->top = chunk_plus_offset(p, nb); 5146 r->head = rsize | PINUSE_BIT; 5147 set_size_and_pinuse_of_inuse_chunk(ms, p, nb); 5148 mem = chunk2mem(p); 5149 check_top_chunk(ms, ms->top); 5150 check_malloced_chunk(ms, mem, nb); 5151 goto postaction; 5152 } 5153 5154 mem = sys_alloc(ms, nb); 5155 5156 postaction: 5157 POSTACTION(ms); 5158 return mem; 5159 } 5160 5161 return 0; 5162} 5163 5164void mspace_free(mspace msp, void* mem) { 5165 if (mem != 0) { 5166 mchunkptr p = mem2chunk(mem); 5167#if FOOTERS 5168 mstate fm = get_mstate_for(p); 5169 msp = msp; /* placate people compiling -Wunused */ 5170#else /* FOOTERS */ 5171 mstate fm = (mstate)msp; 5172#endif /* FOOTERS */ 5173 if (!ok_magic(fm)) { 5174 USAGE_ERROR_ACTION(fm, p); 5175 return; 5176 } 5177 if (!PREACTION(fm)) { 5178 check_inuse_chunk(fm, p); 5179 if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) { 5180 size_t psize = chunksize(p); 5181 mchunkptr next = chunk_plus_offset(p, psize); 5182 if (!pinuse(p)) { 5183 size_t prevsize = p->prev_foot; 5184 if (is_mmapped(p)) { 5185 psize += prevsize + MMAP_FOOT_PAD; 5186 if (CALL_MUNMAP((char*)p - prevsize, psize) == 0) 5187 fm->footprint -= psize; 5188 goto postaction; 5189 } 5190 else { 5191 mchunkptr prev = chunk_minus_offset(p, prevsize); 5192 psize += prevsize; 5193 p = prev; 5194 if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */ 5195 if (p != fm->dv) { 5196 unlink_chunk(fm, p, prevsize); 5197 } 5198 else if ((next->head & INUSE_BITS) == INUSE_BITS) { 5199 fm->dvsize = psize; 5200 set_free_with_pinuse(p, psize, next); 5201 goto postaction; 5202 } 5203 } 5204 else 5205 goto erroraction; 5206 } 5207 } 5208 5209 if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) { 5210 if (!cinuse(next)) { /* consolidate forward */ 5211 if (next == fm->top) { 5212 size_t tsize = fm->topsize += psize; 5213 fm->top = p; 5214 p->head = tsize | PINUSE_BIT; 5215 if (p == fm->dv) { 5216 fm->dv = 0; 5217 fm->dvsize = 0; 5218 } 5219 if (should_trim(fm, tsize)) 5220 sys_trim(fm, 0); 5221 goto postaction; 5222 } 5223 else if (next == fm->dv) { 5224 size_t dsize = fm->dvsize += psize; 5225 fm->dv = p; 5226 set_size_and_pinuse_of_free_chunk(p, dsize); 5227 goto postaction; 5228 } 5229 else { 5230 size_t nsize = chunksize(next); 5231 psize += nsize; 5232 unlink_chunk(fm, next, nsize); 5233 set_size_and_pinuse_of_free_chunk(p, psize); 5234 if (p == fm->dv) { 5235 fm->dvsize = psize; 5236 goto postaction; 5237 } 5238 } 5239 } 5240 else 5241 set_free_with_pinuse(p, psize, next); 5242 5243 if (is_small(psize)) { 5244 insert_small_chunk(fm, p, psize); 5245 check_free_chunk(fm, p); 5246 } 5247 else { 5248 tchunkptr tp = (tchunkptr)p; 5249 insert_large_chunk(fm, tp, psize); 5250 check_free_chunk(fm, p); 5251 if (--fm->release_checks == 0) 5252 release_unused_segments(fm); 5253 } 5254 goto postaction; 5255 } 5256 } 5257 erroraction: 5258 USAGE_ERROR_ACTION(fm, p); 5259 postaction: 5260 POSTACTION(fm); 5261 } 5262 } 5263} 5264 5265void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) { 5266 void* mem; 5267 size_t req = 0; 5268 mstate ms = (mstate)msp; 5269 if (!ok_magic(ms)) { 5270 USAGE_ERROR_ACTION(ms,ms); 5271 return 0; 5272 } 5273 if (n_elements != 0) { 5274 req = n_elements * elem_size; 5275 if (((n_elements | elem_size) & ~(size_t)0xffff) && 5276 (req / n_elements != elem_size)) 5277 req = MAX_SIZE_T; /* force downstream failure on overflow */ 5278 } 5279 mem = internal_malloc(ms, req); 5280 if (mem != 0 && calloc_must_clear(mem2chunk(mem))) 5281 memset(mem, 0, req); 5282 return mem; 5283} 5284 5285void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) { 5286 if (oldmem == 0) 5287 return mspace_malloc(msp, bytes); 5288#ifdef REALLOC_ZERO_BYTES_FREES 5289 if (bytes == 0) { 5290 mspace_free(msp, oldmem); 5291 return 0; 5292 } 5293#endif /* REALLOC_ZERO_BYTES_FREES */ 5294 else { 5295#if FOOTERS 5296 mchunkptr p = mem2chunk(oldmem); 5297 mstate ms = get_mstate_for(p); 5298#else /* FOOTERS */ 5299 mstate ms = (mstate)msp; 5300#endif /* FOOTERS */ 5301 if (!ok_magic(ms)) { 5302 USAGE_ERROR_ACTION(ms,ms); 5303 return 0; 5304 } 5305 return internal_realloc(ms, oldmem, bytes); 5306 } 5307} 5308 5309void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) { 5310 mstate ms = (mstate)msp; 5311 if (!ok_magic(ms)) { 5312 USAGE_ERROR_ACTION(ms,ms); 5313 return 0; 5314 } 5315 return internal_memalign(ms, alignment, bytes); 5316} 5317 5318void** mspace_independent_calloc(mspace msp, size_t n_elements, 5319 size_t elem_size, void* chunks[]) { 5320 size_t sz = elem_size; /* serves as 1-element array */ 5321 mstate ms = (mstate)msp; 5322 if (!ok_magic(ms)) { 5323 USAGE_ERROR_ACTION(ms,ms); 5324 return 0; 5325 } 5326 return ialloc(ms, n_elements, &sz, 3, chunks); 5327} 5328 5329void** mspace_independent_comalloc(mspace msp, size_t n_elements, 5330 size_t sizes[], void* chunks[]) { 5331 mstate ms = (mstate)msp; 5332 if (!ok_magic(ms)) { 5333 USAGE_ERROR_ACTION(ms,ms); 5334 return 0; 5335 } 5336 return ialloc(ms, n_elements, sizes, 0, chunks); 5337} 5338 5339int mspace_trim(mspace msp, size_t pad) { 5340 int result = 0; 5341 mstate ms = (mstate)msp; 5342 if (ok_magic(ms)) { 5343 if (!PREACTION(ms)) { 5344 result = sys_trim(ms, pad); 5345 POSTACTION(ms); 5346 } 5347 } 5348 else { 5349 USAGE_ERROR_ACTION(ms,ms); 5350 } 5351 return result; 5352} 5353 5354void mspace_malloc_stats(mspace msp) { 5355 mstate ms = (mstate)msp; 5356 if (ok_magic(ms)) { 5357 internal_malloc_stats(ms); 5358 } 5359 else { 5360 USAGE_ERROR_ACTION(ms,ms); 5361 } 5362} 5363 5364size_t mspace_footprint(mspace msp) { 5365 size_t result = 0; 5366 mstate ms = (mstate)msp; 5367 if (ok_magic(ms)) { 5368 result = ms->footprint; 5369 } 5370 else { 5371 USAGE_ERROR_ACTION(ms,ms); 5372 } 5373 return result; 5374} 5375 5376 5377size_t mspace_max_footprint(mspace msp) { 5378 size_t result = 0; 5379 mstate ms = (mstate)msp; 5380 if (ok_magic(ms)) { 5381 result = ms->max_footprint; 5382 } 5383 else { 5384 USAGE_ERROR_ACTION(ms,ms); 5385 } 5386 return result; 5387} 5388 5389 5390#if !NO_MALLINFO 5391struct mallinfo mspace_mallinfo(mspace msp) { 5392 mstate ms = (mstate)msp; 5393 if (!ok_magic(ms)) { 5394 USAGE_ERROR_ACTION(ms,ms); 5395 } 5396 return internal_mallinfo(ms); 5397} 5398#endif /* NO_MALLINFO */ 5399 5400size_t mspace_usable_size(void* mem) { 5401 if (mem != 0) { 5402 mchunkptr p = mem2chunk(mem); 5403 if (is_inuse(p)) 5404 return chunksize(p) - overhead_for(p); 5405 } 5406 return 0; 5407} 5408 5409int mspace_mallopt(int param_number, int value) { 5410 return change_mparam(param_number, value); 5411} 5412 5413#endif /* MSPACES */ 5414 5415 5416/* -------------------- Alternative MORECORE functions ------------------- */ 5417 5418/* 5419 Guidelines for creating a custom version of MORECORE: 5420 5421 * For best performance, MORECORE should allocate in multiples of pagesize. 5422 * MORECORE may allocate more memory than requested. (Or even less, 5423 but this will usually result in a malloc failure.) 5424 * MORECORE must not allocate memory when given argument zero, but 5425 instead return one past the end address of memory from previous 5426 nonzero call. 5427 * For best performance, consecutive calls to MORECORE with positive 5428 arguments should return increasing addresses, indicating that 5429 space has been contiguously extended. 5430 * Even though consecutive calls to MORECORE need not return contiguous 5431 addresses, it must be OK for malloc'ed chunks to span multiple 5432 regions in those cases where they do happen to be contiguous. 5433 * MORECORE need not handle negative arguments -- it may instead 5434 just return MFAIL when given negative arguments. 5435 Negative arguments are always multiples of pagesize. MORECORE 5436 must not misinterpret negative args as large positive unsigned 5437 args. You can suppress all such calls from even occurring by defining 5438 MORECORE_CANNOT_TRIM, 5439 5440 As an example alternative MORECORE, here is a custom allocator 5441 kindly contributed for pre-OSX macOS. It uses virtually but not 5442 necessarily physically contiguous non-paged memory (locked in, 5443 present and won't get swapped out). You can use it by uncommenting 5444 this section, adding some #includes, and setting up the appropriate 5445 defines above: 5446 5447 #define MORECORE osMoreCore 5448 5449 There is also a shutdown routine that should somehow be called for 5450 cleanup upon program exit. 5451 5452 #define MAX_POOL_ENTRIES 100 5453 #define MINIMUM_MORECORE_SIZE (64 * 1024U) 5454 static int next_os_pool; 5455 void *our_os_pools[MAX_POOL_ENTRIES]; 5456 5457 void *osMoreCore(int size) 5458 { 5459 void *ptr = 0; 5460 static void *sbrk_top = 0; 5461 5462 if (size > 0) 5463 { 5464 if (size < MINIMUM_MORECORE_SIZE) 5465 size = MINIMUM_MORECORE_SIZE; 5466 if (CurrentExecutionLevel() == kTaskLevel) 5467 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0); 5468 if (ptr == 0) 5469 { 5470 return (void *) MFAIL; 5471 } 5472 // save ptrs so they can be freed during cleanup 5473 our_os_pools[next_os_pool] = ptr; 5474 next_os_pool++; 5475 ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK); 5476 sbrk_top = (char *) ptr + size; 5477 return ptr; 5478 } 5479 else if (size < 0) 5480 { 5481 // we don't currently support shrink behavior 5482 return (void *) MFAIL; 5483 } 5484 else 5485 { 5486 return sbrk_top; 5487 } 5488 } 5489 5490 // cleanup any allocated memory pools 5491 // called as last thing before shutting down driver 5492 5493 void osCleanupMem(void) 5494 { 5495 void **ptr; 5496 5497 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++) 5498 if (*ptr) 5499 { 5500 PoolDeallocate(*ptr); 5501 *ptr = 0; 5502 } 5503 } 5504 5505*/ 5506 5507 5508/* ----------------------------------------------------------------------- 5509History: 5510 V2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee) 5511 * Use zeros instead of prev foot for is_mmapped 5512 * Add mspace_track_large_chunks; thanks to Jean Brouwers 5513 * Fix set_inuse in internal_realloc; thanks to Jean Brouwers 5514 * Fix insufficient sys_alloc padding when using 16byte alignment 5515 * Fix bad error check in mspace_footprint 5516 * Adaptations for ptmalloc; thanks to Wolfram Gloger. 5517 * Reentrant spin locks; thanks to Earl Chew and others 5518 * Win32 improvements; thanks to Niall Douglas and Earl Chew 5519 * Add NO_SEGMENT_TRAVERSAL and MAX_RELEASE_CHECK_RATE options 5520 * Extension hook in malloc_state 5521 * Various small adjustments to reduce warnings on some compilers 5522 * Various configuration extensions/changes for more platforms. Thanks 5523 to all who contributed these. 5524 5525 V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee) 5526 * Add max_footprint functions 5527 * Ensure all appropriate literals are size_t 5528 * Fix conditional compilation problem for some #define settings 5529 * Avoid concatenating segments with the one provided 5530 in create_mspace_with_base 5531 * Rename some variables to avoid compiler shadowing warnings 5532 * Use explicit lock initialization. 5533 * Better handling of sbrk interference. 5534 * Simplify and fix segment insertion, trimming and mspace_destroy 5535 * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x 5536 * Thanks especially to Dennis Flanagan for help on these. 5537 5538 V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee) 5539 * Fix memalign brace error. 5540 5541 V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee) 5542 * Fix improper #endif nesting in C++ 5543 * Add explicit casts needed for C++ 5544 5545 V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee) 5546 * Use trees for large bins 5547 * Support mspaces 5548 * Use segments to unify sbrk-based and mmap-based system allocation, 5549 removing need for emulation on most platforms without sbrk. 5550 * Default safety checks 5551 * Optional footer checks. Thanks to William Robertson for the idea. 5552 * Internal code refactoring 5553 * Incorporate suggestions and platform-specific changes. 5554 Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas, 5555 Aaron Bachmann, Emery Berger, and others. 5556 * Speed up non-fastbin processing enough to remove fastbins. 5557 * Remove useless cfree() to avoid conflicts with other apps. 5558 * Remove internal memcpy, memset. Compilers handle builtins better. 5559 * Remove some options that no one ever used and rename others. 5560 5561 V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee) 5562 * Fix malloc_state bitmap array misdeclaration 5563 5564 V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee) 5565 * Allow tuning of FIRST_SORTED_BIN_SIZE 5566 * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte. 5567 * Better detection and support for non-contiguousness of MORECORE. 5568 Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger 5569 * Bypass most of malloc if no frees. Thanks To Emery Berger. 5570 * Fix freeing of old top non-contiguous chunk im sysmalloc. 5571 * Raised default trim and map thresholds to 256K. 5572 * Fix mmap-related #defines. Thanks to Lubos Lunak. 5573 * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield. 5574 * Branch-free bin calculation 5575 * Default trim and mmap thresholds now 256K. 5576 5577 V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee) 5578 * Introduce independent_comalloc and independent_calloc. 5579 Thanks to Michael Pachos for motivation and help. 5580 * Make optional .h file available 5581 * Allow > 2GB requests on 32bit systems. 5582 * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>. 5583 Thanks also to Andreas Mueller <a.mueller at paradatec.de>, 5584 and Anonymous. 5585 * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for 5586 helping test this.) 5587 * memalign: check alignment arg 5588 * realloc: don't try to shift chunks backwards, since this 5589 leads to more fragmentation in some programs and doesn't 5590 seem to help in any others. 5591 * Collect all cases in malloc requiring system memory into sysmalloc 5592 * Use mmap as backup to sbrk 5593 * Place all internal state in malloc_state 5594 * Introduce fastbins (although similar to 2.5.1) 5595 * Many minor tunings and cosmetic improvements 5596 * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK 5597 * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS 5598 Thanks to Tony E. Bennett <tbennett@nvidia.com> and others. 5599 * Include errno.h to support default failure action. 5600 5601 V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee) 5602 * return null for negative arguments 5603 * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com> 5604 * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h' 5605 (e.g. WIN32 platforms) 5606 * Cleanup header file inclusion for WIN32 platforms 5607 * Cleanup code to avoid Microsoft Visual C++ compiler complaints 5608 * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing 5609 memory allocation routines 5610 * Set 'malloc_getpagesize' for WIN32 platforms (needs more work) 5611 * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to 5612 usage of 'assert' in non-WIN32 code 5613 * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to 5614 avoid infinite loop 5615 * Always call 'fREe()' rather than 'free()' 5616 5617 V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee) 5618 * Fixed ordering problem with boundary-stamping 5619 5620 V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee) 5621 * Added pvalloc, as recommended by H.J. Liu 5622 * Added 64bit pointer support mainly from Wolfram Gloger 5623 * Added anonymously donated WIN32 sbrk emulation 5624 * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen 5625 * malloc_extend_top: fix mask error that caused wastage after 5626 foreign sbrks 5627 * Add linux mremap support code from HJ Liu 5628 5629 V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee) 5630 * Integrated most documentation with the code. 5631 * Add support for mmap, with help from 5632 Wolfram Gloger (Gloger@lrz.uni-muenchen.de). 5633 * Use last_remainder in more cases. 5634 * Pack bins using idea from colin@nyx10.cs.du.edu 5635 * Use ordered bins instead of best-fit threshhold 5636 * Eliminate block-local decls to simplify tracing and debugging. 5637 * Support another case of realloc via move into top 5638 * Fix error occuring when initial sbrk_base not word-aligned. 5639 * Rely on page size for units instead of SBRK_UNIT to 5640 avoid surprises about sbrk alignment conventions. 5641 * Add mallinfo, mallopt. Thanks to Raymond Nijssen 5642 (raymond@es.ele.tue.nl) for the suggestion. 5643 * Add `pad' argument to malloc_trim and top_pad mallopt parameter. 5644 * More precautions for cases where other routines call sbrk, 5645 courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de). 5646 * Added macros etc., allowing use in linux libc from 5647 H.J. Lu (hjl@gnu.ai.mit.edu) 5648 * Inverted this history list 5649 5650 V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee) 5651 * Re-tuned and fixed to behave more nicely with V2.6.0 changes. 5652 * Removed all preallocation code since under current scheme 5653 the work required to undo bad preallocations exceeds 5654 the work saved in good cases for most test programs. 5655 * No longer use return list or unconsolidated bins since 5656 no scheme using them consistently outperforms those that don't 5657 given above changes. 5658 * Use best fit for very large chunks to prevent some worst-cases. 5659 * Added some support for debugging 5660 5661 V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee) 5662 * Removed footers when chunks are in use. Thanks to 5663 Paul Wilson (wilson@cs.texas.edu) for the suggestion. 5664 5665 V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee) 5666 * Added malloc_trim, with help from Wolfram Gloger 5667 (wmglo@Dent.MED.Uni-Muenchen.DE). 5668 5669 V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g) 5670 5671 V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g) 5672 * realloc: try to expand in both directions 5673 * malloc: swap order of clean-bin strategy; 5674 * realloc: only conditionally expand backwards 5675 * Try not to scavenge used bins 5676 * Use bin counts as a guide to preallocation 5677 * Occasionally bin return list chunks in first scan 5678 * Add a few optimizations from colin@nyx10.cs.du.edu 5679 5680 V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g) 5681 * faster bin computation & slightly different binning 5682 * merged all consolidations to one part of malloc proper 5683 (eliminating old malloc_find_space & malloc_clean_bin) 5684 * Scan 2 returns chunks (not just 1) 5685 * Propagate failure in realloc if malloc returns 0 5686 * Add stuff to allow compilation on non-ANSI compilers 5687 from kpv@research.att.com 5688 5689 V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu) 5690 * removed potential for odd address access in prev_chunk 5691 * removed dependency on getpagesize.h 5692 * misc cosmetics and a bit more internal documentation 5693 * anticosmetics: mangled names in macros to evade debugger strangeness 5694 * tested on sparc, hp-700, dec-mips, rs6000 5695 with gcc & native cc (hp, dec only) allowing 5696 Detlefs & Zorn comparison study (in SIGPLAN Notices.) 5697 5698 Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu) 5699 * Based loosely on libg++-1.2X malloc. (It retains some of the overall 5700 structure of old version, but most details differ.) 5701 5702*/ 5703 5704