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