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