2 This is a version (aka dlmalloc) of malloc/free/realloc written by
3 Doug Lea and released to the public domain, as explained at
4 http://creativecommons.org/licenses/publicdomain. Send questions,
5 comments, complaints, performance data, etc to dl@cs.oswego.edu
7 * Version 2.8.3 Thu Sep 22 11:16:15 2005 Doug Lea (dl at gee)
9 Note: There may be an updated version of this malloc obtainable at
10 ftp://gee.cs.oswego.edu/pub/misc/malloc.c
11 Check before installing!
15 * Modifications made to the original version for mono:
16 * - added PROT_EXEC to MMAP_PROT
17 * - added PAGE_EXECUTE_READWRITE to the win32mmap and win32direct_mmap
18 * - a large portion of functions is #ifdef'ed out to make the native code smaller
22 #include "mono-mmap.h"
24 #define USE_DL_PREFIX 1
26 /* Use mmap for allocating memory */
27 #define HAVE_MORECORE 0
29 #include <mono/utils/dlmalloc.h>
34 This library is all in one file to simplify the most common usage:
35 ftp it, compile it (-O3), and link it into another program. All of
36 the compile-time options default to reasonable values for use on
37 most platforms. You might later want to step through various
38 compile-time and dynamic tuning options.
40 For convenience, an include file for code using this malloc is at:
41 ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.3.h
42 You don't really need this .h file unless you call functions not
43 defined in your system include files. The .h file contains only the
44 excerpts from this file needed for using this malloc on ANSI C/C++
45 systems, so long as you haven't changed compile-time options about
46 naming and tuning parameters. If you do, then you can create your
47 own malloc.h that does include all settings by cutting at the point
48 indicated below. Note that you may already by default be using a C
49 library containing a malloc that is based on some version of this
50 malloc (for example in linux). You might still want to use the one
51 in this file to customize settings or to avoid overheads associated
52 with library versions.
56 Supported pointer/size_t representation: 4 or 8 bytes
57 size_t MUST be an unsigned type of the same width as
58 pointers. (If you are using an ancient system that declares
59 size_t as a signed type, or need it to be a different width
60 than pointers, you can use a previous release of this malloc
61 (e.g. 2.7.2) supporting these.)
63 Alignment: 8 bytes (default)
64 This suffices for nearly all current machines and C compilers.
65 However, you can define MALLOC_ALIGNMENT to be wider than this
66 if necessary (up to 128bytes), at the expense of using more space.
68 Minimum overhead per allocated chunk: 4 or 8 bytes (if 4byte sizes)
69 8 or 16 bytes (if 8byte sizes)
70 Each malloced chunk has a hidden word of overhead holding size
71 and status information, and additional cross-check word
72 if FOOTERS is defined.
74 Minimum allocated size: 4-byte ptrs: 16 bytes (including overhead)
75 8-byte ptrs: 32 bytes (including overhead)
77 Even a request for zero bytes (i.e., malloc(0)) returns a
78 pointer to something of the minimum allocatable size.
79 The maximum overhead wastage (i.e., number of extra bytes
80 allocated than were requested in malloc) is less than or equal
81 to the minimum size, except for requests >= mmap_threshold that
82 are serviced via mmap(), where the worst case wastage is about
83 32 bytes plus the remainder from a system page (the minimal
84 mmap unit); typically 4096 or 8192 bytes.
86 Security: static-safe; optionally more or less
87 The "security" of malloc refers to the ability of malicious
88 code to accentuate the effects of errors (for example, freeing
89 space that is not currently malloc'ed or overwriting past the
90 ends of chunks) in code that calls malloc. This malloc
91 guarantees not to modify any memory locations below the base of
92 heap, i.e., static variables, even in the presence of usage
93 errors. The routines additionally detect most improper frees
94 and reallocs. All this holds as long as the static bookkeeping
95 for malloc itself is not corrupted by some other means. This
96 is only one aspect of security -- these checks do not, and
97 cannot, detect all possible programming errors.
99 If FOOTERS is defined nonzero, then each allocated chunk
100 carries an additional check word to verify that it was malloced
101 from its space. These check words are the same within each
102 execution of a program using malloc, but differ across
103 executions, so externally crafted fake chunks cannot be
104 freed. This improves security by rejecting frees/reallocs that
105 could corrupt heap memory, in addition to the checks preventing
106 writes to statics that are always on. This may further improve
107 security at the expense of time and space overhead. (Note that
108 FOOTERS may also be worth using with MSPACES.)
110 By default detected errors cause the program to abort (calling
111 "abort()"). You can override this to instead proceed past
112 errors by defining PROCEED_ON_ERROR. In this case, a bad free
113 has no effect, and a malloc that encounters a bad address
114 caused by user overwrites will ignore the bad address by
115 dropping pointers and indices to all known memory. This may
116 be appropriate for programs that should continue if at all
117 possible in the face of programming errors, although they may
118 run out of memory because dropped memory is never reclaimed.
120 If you don't like either of these options, you can define
121 CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
122 else. And if if you are sure that your program using malloc has
123 no errors or vulnerabilities, you can define INSECURE to 1,
124 which might (or might not) provide a small performance improvement.
126 Thread-safety: NOT thread-safe unless USE_LOCKS defined
127 When USE_LOCKS is defined, each public call to malloc, free,
128 etc is surrounded with either a pthread mutex or a win32
129 spinlock (depending on WIN32). This is not especially fast, and
130 can be a major bottleneck. It is designed only to provide
131 minimal protection in concurrent environments, and to provide a
132 basis for extensions. If you are using malloc in a concurrent
133 program, consider instead using ptmalloc, which is derived from
134 a version of this malloc. (See http://www.malloc.de).
136 System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
137 This malloc can use unix sbrk or any emulation (invoked using
138 the CALL_MORECORE macro) and/or mmap/munmap or any emulation
139 (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
140 memory. On most unix systems, it tends to work best if both
141 MORECORE and MMAP are enabled. On Win32, it uses emulations
142 based on VirtualAlloc. It also uses common C library functions
145 Compliance: I believe it is compliant with the Single Unix Specification
146 (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
149 * Overview of algorithms
151 This is not the fastest, most space-conserving, most portable, or
152 most tunable malloc ever written. However it is among the fastest
153 while also being among the most space-conserving, portable and
154 tunable. Consistent balance across these factors results in a good
155 general-purpose allocator for malloc-intensive programs.
157 In most ways, this malloc is a best-fit allocator. Generally, it
158 chooses the best-fitting existing chunk for a request, with ties
159 broken in approximately least-recently-used order. (This strategy
160 normally maintains low fragmentation.) However, for requests less
161 than 256bytes, it deviates from best-fit when there is not an
162 exactly fitting available chunk by preferring to use space adjacent
163 to that used for the previous small request, as well as by breaking
164 ties in approximately most-recently-used order. (These enhance
165 locality of series of small allocations.) And for very large requests
166 (>= 256Kb by default), it relies on system memory mapping
167 facilities, if supported. (This helps avoid carrying around and
168 possibly fragmenting memory used only for large chunks.)
170 All operations (except malloc_stats and mallinfo) have execution
171 times that are bounded by a constant factor of the number of bits in
172 a size_t, not counting any clearing in calloc or copying in realloc,
173 or actions surrounding MORECORE and MMAP that have times
174 proportional to the number of non-contiguous regions returned by
175 system allocation routines, which is often just 1.
177 The implementation is not very modular and seriously overuses
178 macros. Perhaps someday all C compilers will do as good a job
179 inlining modular code as can now be done by brute-force expansion,
180 but now, enough of them seem not to.
182 Some compilers issue a lot of warnings about code that is
183 dead/unreachable only on some platforms, and also about intentional
184 uses of negation on unsigned types. All known cases of each can be
187 For a longer but out of date high-level description, see
188 http://gee.cs.oswego.edu/dl/html/malloc.html
191 If MSPACES is defined, then in addition to malloc, free, etc.,
192 this file also defines mspace_malloc, mspace_free, etc. These
193 are versions of malloc routines that take an "mspace" argument
194 obtained using create_mspace, to control all internal bookkeeping.
195 If ONLY_MSPACES is defined, only these versions are compiled.
196 So if you would like to use this allocator for only some allocations,
197 and your system malloc for others, you can compile with
198 ONLY_MSPACES and then do something like...
199 static mspace mymspace = create_mspace(0,0); // for example
200 #define mymalloc(bytes) mspace_malloc(mymspace, bytes)
202 (Note: If you only need one instance of an mspace, you can instead
203 use "USE_DL_PREFIX" to relabel the global malloc.)
205 You can similarly create thread-local allocators by storing
206 mspaces as thread-locals. For example:
207 static __thread mspace tlms = 0;
208 void* tlmalloc(size_t bytes) {
209 if (tlms == 0) tlms = create_mspace(0, 0);
210 return mspace_malloc(tlms, bytes);
212 void tlfree(void* mem) { mspace_free(tlms, mem); }
214 Unless FOOTERS is defined, each mspace is completely independent.
215 You cannot allocate from one and free to another (although
216 conformance is only weakly checked, so usage errors are not always
217 caught). If FOOTERS is defined, then each chunk carries around a tag
218 indicating its originating mspace, and frees are directed to their
221 ------------------------- Compile-time options ---------------------------
223 Be careful in setting #define values for numerical constants of type
224 size_t. On some systems, literal values are not automatically extended
225 to size_t precision unless they are explicitly casted.
227 WIN32 default: defined if _WIN32 defined
228 Defining WIN32 sets up defaults for MS environment and compilers.
229 Otherwise defaults are for unix.
231 MALLOC_ALIGNMENT default: (size_t)8
232 Controls the minimum alignment for malloc'ed chunks. It must be a
233 power of two and at least 8, even on machines for which smaller
234 alignments would suffice. It may be defined as larger than this
235 though. Note however that code and data structures are optimized for
236 the case of 8-byte alignment.
238 MSPACES default: 0 (false)
239 If true, compile in support for independent allocation spaces.
240 This is only supported if HAVE_MMAP is true.
242 ONLY_MSPACES default: 0 (false)
243 If true, only compile in mspace versions, not regular versions.
245 USE_LOCKS default: 0 (false)
246 Causes each call to each public routine to be surrounded with
247 pthread or WIN32 mutex lock/unlock. (If set true, this can be
248 overridden on a per-mspace basis for mspace versions.)
251 If true, provide extra checking and dispatching by placing
252 information in the footers of allocated chunks. This adds
253 space and time overhead.
256 If true, omit checks for usage errors and heap space overwrites.
258 USE_DL_PREFIX default: NOT defined
259 Causes compiler to prefix all public routines with the string 'dl'.
260 This can be useful when you only want to use this malloc in one part
261 of a program, using your regular system malloc elsewhere.
263 ABORT default: defined as abort()
264 Defines how to abort on failed checks. On most systems, a failed
265 check cannot die with an "assert" or even print an informative
266 message, because the underlying print routines in turn call malloc,
267 which will fail again. Generally, the best policy is to simply call
268 abort(). It's not very useful to do more than this because many
269 errors due to overwriting will show up as address faults (null, odd
270 addresses etc) rather than malloc-triggered checks, so will also
271 abort. Also, most compilers know that abort() does not return, so
272 can better optimize code conditionally calling it.
274 PROCEED_ON_ERROR default: defined as 0 (false)
275 Controls whether detected bad addresses cause them to bypassed
276 rather than aborting. If set, detected bad arguments to free and
277 realloc are ignored. And all bookkeeping information is zeroed out
278 upon a detected overwrite of freed heap space, thus losing the
279 ability to ever return it from malloc again, but enabling the
280 application to proceed. If PROCEED_ON_ERROR is defined, the
281 static variable malloc_corruption_error_count is compiled in
282 and can be examined to see if errors have occurred. This option
283 generates slower code than the default abort policy.
285 DEBUG default: NOT defined
286 The DEBUG setting is mainly intended for people trying to modify
287 this code or diagnose problems when porting to new platforms.
288 However, it may also be able to better isolate user errors than just
289 using runtime checks. The assertions in the check routines spell
290 out in more detail the assumptions and invariants underlying the
291 algorithms. The checking is fairly extensive, and will slow down
292 execution noticeably. Calling malloc_stats or mallinfo with DEBUG
293 set will attempt to check every non-mmapped allocated and free chunk
294 in the course of computing the summaries.
296 ABORT_ON_ASSERT_FAILURE default: defined as 1 (true)
297 Debugging assertion failures can be nearly impossible if your
298 version of the assert macro causes malloc to be called, which will
299 lead to a cascade of further failures, blowing the runtime stack.
300 ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
301 which will usually make debugging easier.
303 MALLOC_FAILURE_ACTION default: sets errno to ENOMEM, or no-op on win32
304 The action to take before "return 0" when malloc fails to be able to
305 return memory because there is none available.
307 HAVE_MORECORE default: 1 (true) unless win32 or ONLY_MSPACES
308 True if this system supports sbrk or an emulation of it.
310 MORECORE default: sbrk
311 The name of the sbrk-style system routine to call to obtain more
312 memory. See below for guidance on writing custom MORECORE
313 functions. The type of the argument to sbrk/MORECORE varies across
314 systems. It cannot be size_t, because it supports negative
315 arguments, so it is normally the signed type of the same width as
316 size_t (sometimes declared as "intptr_t"). It doesn't much matter
317 though. Internally, we only call it with arguments less than half
318 the max value of a size_t, which should work across all reasonable
319 possibilities, although sometimes generating compiler warnings. See
320 near the end of this file for guidelines for creating a custom
323 MORECORE_CONTIGUOUS default: 1 (true)
324 If true, take advantage of fact that consecutive calls to MORECORE
325 with positive arguments always return contiguous increasing
326 addresses. This is true of unix sbrk. It does not hurt too much to
327 set it true anyway, since malloc copes with non-contiguities.
328 Setting it false when definitely non-contiguous saves time
329 and possibly wasted space it would take to discover this though.
331 MORECORE_CANNOT_TRIM default: NOT defined
332 True if MORECORE cannot release space back to the system when given
333 negative arguments. This is generally necessary only if you are
334 using a hand-crafted MORECORE function that cannot handle negative
337 HAVE_MMAP default: 1 (true)
338 True if this system supports mmap or an emulation of it. If so, and
339 HAVE_MORECORE is not true, MMAP is used for all system
340 allocation. If set and HAVE_MORECORE is true as well, MMAP is
341 primarily used to directly allocate very large blocks. It is also
342 used as a backup strategy in cases where MORECORE fails to provide
343 space from system. Note: A single call to MUNMAP is assumed to be
344 able to unmap memory that may have be allocated using multiple calls
345 to MMAP, so long as they are adjacent.
347 HAVE_MREMAP default: 1 on linux and NetBSD, else 0
348 If true realloc() uses mremap() to re-allocate large blocks and
349 extend or shrink allocation spaces.
351 MMAP_CLEARS default: 1 on unix
352 True if mmap clears memory so calloc doesn't need to. This is true
353 for standard unix mmap using /dev/zero.
355 USE_BUILTIN_FFS default: 0 (i.e., not used)
356 Causes malloc to use the builtin ffs() function to compute indices.
357 Some compilers may recognize and intrinsify ffs to be faster than the
358 supplied C version. Also, the case of x86 using gcc is special-cased
359 to an asm instruction, so is already as fast as it can be, and so
360 this setting has no effect. (On most x86s, the asm version is only
361 slightly faster than the C version.)
363 malloc_getpagesize default: derive from system includes, or 4096.
364 The system page size. To the extent possible, this malloc manages
365 memory from the system in page-size units. This may be (and
366 usually is) a function rather than a constant. This is ignored
367 if WIN32, where page size is determined using getSystemInfo during
370 USE_DEV_RANDOM default: 0 (i.e., not used)
371 Causes malloc to use /dev/random to initialize secure magic seed for
372 stamping footers. Otherwise, the current time is used.
374 NO_MALLINFO default: 0
375 If defined, don't compile "mallinfo". This can be a simple way
376 of dealing with mismatches between system declarations and
379 MALLINFO_FIELD_TYPE default: size_t
380 The type of the fields in the mallinfo struct. This was originally
381 defined as "int" in SVID etc, but is more usefully defined as
382 size_t. The value is used only if HAVE_USR_INCLUDE_MALLOC_H is not set
384 REALLOC_ZERO_BYTES_FREES default: not defined
385 This should be set if a call to realloc with zero bytes should
386 be the same as a call to free. Some people think it should. Otherwise,
387 since this malloc returns a unique pointer for malloc(0), so does
390 LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
391 LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H, LACKS_ERRNO_H
392 LACKS_STDLIB_H default: NOT defined unless on WIN32
393 Define these if your system does not have these header files.
394 You might need to manually insert some of the declarations they provide.
396 DEFAULT_GRANULARITY default: page size if MORECORE_CONTIGUOUS,
397 system_info.dwAllocationGranularity in WIN32,
399 Also settable using mallopt(M_GRANULARITY, x)
400 The unit for allocating and deallocating memory from the system. On
401 most systems with contiguous MORECORE, there is no reason to
402 make this more than a page. However, systems with MMAP tend to
403 either require or encourage larger granularities. You can increase
404 this value to prevent system allocation functions to be called so
405 often, especially if they are slow. The value must be at least one
406 page and must be a power of two. Setting to 0 causes initialization
407 to either page size or win32 region size. (Note: In previous
408 versions of malloc, the equivalent of this option was called
411 DEFAULT_TRIM_THRESHOLD default: 2MB
412 Also settable using mallopt(M_TRIM_THRESHOLD, x)
413 The maximum amount of unused top-most memory to keep before
414 releasing via malloc_trim in free(). Automatic trimming is mainly
415 useful in long-lived programs using contiguous MORECORE. Because
416 trimming via sbrk can be slow on some systems, and can sometimes be
417 wasteful (in cases where programs immediately afterward allocate
418 more large chunks) the value should be high enough so that your
419 overall system performance would improve by releasing this much
420 memory. As a rough guide, you might set to a value close to the
421 average size of a process (program) running on your system.
422 Releasing this much memory would allow such a process to run in
423 memory. Generally, it is worth tuning trim thresholds when a
424 program undergoes phases where several large chunks are allocated
425 and released in ways that can reuse each other's storage, perhaps
426 mixed with phases where there are no such chunks at all. The trim
427 value must be greater than page size to have any useful effect. To
428 disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
429 some people use of mallocing a huge space and then freeing it at
430 program startup, in an attempt to reserve system memory, doesn't
431 have the intended effect under automatic trimming, since that memory
432 will immediately be returned to the system.
434 DEFAULT_MMAP_THRESHOLD default: 256K
435 Also settable using mallopt(M_MMAP_THRESHOLD, x)
436 The request size threshold for using MMAP to directly service a
437 request. Requests of at least this size that cannot be allocated
438 using already-existing space will be serviced via mmap. (If enough
439 normal freed space already exists it is used instead.) Using mmap
440 segregates relatively large chunks of memory so that they can be
441 individually obtained and released from the host system. A request
442 serviced through mmap is never reused by any other request (at least
443 not directly; the system may just so happen to remap successive
444 requests to the same locations). Segregating space in this way has
445 the benefits that: Mmapped space can always be individually released
446 back to the system, which helps keep the system level memory demands
447 of a long-lived program low. Also, mapped memory doesn't become
448 `locked' between other chunks, as can happen with normally allocated
449 chunks, which means that even trimming via malloc_trim would not
450 release them. However, it has the disadvantage that the space
451 cannot be reclaimed, consolidated, and then used to service later
452 requests, as happens with normal chunks. The advantages of mmap
453 nearly always outweigh disadvantages for "large" chunks, but the
454 value of "large" may vary across systems. The default is an
455 empirically derived value that works well in most systems. You can
456 disable mmap by setting to MAX_SIZE_T.
466 #ifndef WIN32_LEAN_AND_MEAN
467 #define WIN32_LEAN_AND_MEAN
471 #define HAVE_MORECORE 0
472 #define LACKS_UNISTD_H
473 #define LACKS_SYS_PARAM_H
474 #define LACKS_SYS_MMAN_H
475 #define LACKS_STRING_H
476 #define LACKS_STRINGS_H
477 #define LACKS_SYS_TYPES_H
478 #define LACKS_ERRNO_H
479 #define MALLOC_FAILURE_ACTION
480 #define MMAP_CLEARS 0 /* WINCE and some others apparently don't clear */
483 #if defined(DARWIN) || defined(_DARWIN)
484 /* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
485 #ifndef HAVE_MORECORE
486 #define HAVE_MORECORE 0
488 #endif /* HAVE_MORECORE */
491 #ifndef LACKS_SYS_TYPES_H
492 #include <sys/types.h> /* For size_t */
493 #endif /* LACKS_SYS_TYPES_H */
495 /* The maximum possible size_t value has all bits set */
496 #define MAX_SIZE_T (~(size_t)0)
499 #define ONLY_MSPACES 0
500 #endif /* ONLY_MSPACES */
504 #else /* ONLY_MSPACES */
506 #endif /* ONLY_MSPACES */
508 #ifndef MALLOC_ALIGNMENT
509 #define MALLOC_ALIGNMENT ((size_t)8U)
510 #endif /* MALLOC_ALIGNMENT */
515 #define ABORT abort()
517 #ifndef ABORT_ON_ASSERT_FAILURE
518 #define ABORT_ON_ASSERT_FAILURE 1
519 #endif /* ABORT_ON_ASSERT_FAILURE */
520 #ifndef PROCEED_ON_ERROR
521 #define PROCEED_ON_ERROR 0
522 #endif /* PROCEED_ON_ERROR */
525 #endif /* USE_LOCKS */
528 #endif /* INSECURE */
531 #endif /* HAVE_MMAP */
533 #define MMAP_CLEARS 1
534 #endif /* MMAP_CLEARS */
536 #if defined(linux) || defined(__NetBSD__)
537 #define HAVE_MREMAP 1
538 #else /* linux || __NetBSD__ */
539 #define HAVE_MREMAP 0
540 #endif /* linux || __NetBSD__ */
541 #endif /* HAVE_MREMAP */
542 #ifndef MALLOC_FAILURE_ACTION
543 #include <mono/utils/mono-errno.h>
544 #define MALLOC_FAILURE_ACTION mono_set_errno (ENOMEM);
545 #endif /* MALLOC_FAILURE_ACTION */
546 #ifndef HAVE_MORECORE
548 #define HAVE_MORECORE 0
549 #else /* ONLY_MSPACES */
550 #define HAVE_MORECORE 1
551 #endif /* ONLY_MSPACES */
552 #endif /* HAVE_MORECORE */
554 #define MORECORE_CONTIGUOUS 0
555 #else /* !HAVE_MORECORE */
557 #define MORECORE sbrk
558 #endif /* MORECORE */
559 #ifndef MORECORE_CONTIGUOUS
560 #define MORECORE_CONTIGUOUS 1
561 #endif /* MORECORE_CONTIGUOUS */
562 #endif /* HAVE_MORECORE */
563 #ifndef DEFAULT_GRANULARITY
564 #if MORECORE_CONTIGUOUS
565 #define DEFAULT_GRANULARITY (0) /* 0 means to compute in init_mparams */
566 #else /* MORECORE_CONTIGUOUS */
567 #define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
568 #endif /* MORECORE_CONTIGUOUS */
569 #endif /* DEFAULT_GRANULARITY */
570 #ifndef DEFAULT_TRIM_THRESHOLD
571 #ifndef MORECORE_CANNOT_TRIM
572 #define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
573 #else /* MORECORE_CANNOT_TRIM */
574 #define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
575 #endif /* MORECORE_CANNOT_TRIM */
576 #endif /* DEFAULT_TRIM_THRESHOLD */
577 #ifndef DEFAULT_MMAP_THRESHOLD
579 #define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
580 #else /* HAVE_MMAP */
581 #define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
582 #endif /* HAVE_MMAP */
583 #endif /* DEFAULT_MMAP_THRESHOLD */
584 #ifndef USE_BUILTIN_FFS
585 #define USE_BUILTIN_FFS 0
586 #endif /* USE_BUILTIN_FFS */
587 #ifndef USE_DEV_RANDOM
588 #define USE_DEV_RANDOM 0
589 #endif /* USE_DEV_RANDOM */
591 #define NO_MALLINFO 0
592 #endif /* NO_MALLINFO */
593 #ifndef MALLINFO_FIELD_TYPE
594 #define MALLINFO_FIELD_TYPE size_t
595 #endif /* MALLINFO_FIELD_TYPE */
598 mallopt tuning options. SVID/XPG defines four standard parameter
599 numbers for mallopt, normally defined in malloc.h. None of these
600 are used in this malloc, so setting them has no effect. But this
601 malloc does support the following options.
604 #define M_TRIM_THRESHOLD (-1)
605 #define M_GRANULARITY (-2)
606 #define M_MMAP_THRESHOLD (-3)
608 /* ------------------------ Mallinfo declarations ------------------------ */
612 This version of malloc supports the standard SVID/XPG mallinfo
613 routine that returns a struct containing usage properties and
614 statistics. It should work on any system that has a
615 /usr/include/malloc.h defining struct mallinfo. The main
616 declaration needed is the mallinfo struct that is returned (by-copy)
617 by mallinfo(). The malloinfo struct contains a bunch of fields that
618 are not even meaningful in this version of malloc. These fields are
619 are instead filled by mallinfo() with other numbers that might be of
622 HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
623 /usr/include/malloc.h file that includes a declaration of struct
624 mallinfo. If so, it is included; else a compliant version is
625 declared below. These must be precisely the same for mallinfo() to
626 work. The original SVID version of this struct, defined on most
627 systems with mallinfo, declares all fields as ints. But some others
628 define as unsigned long. If your system defines the fields using a
629 type of different width than listed here, you MUST #include your
630 system version and #define HAVE_USR_INCLUDE_MALLOC_H.
633 /* #define HAVE_USR_INCLUDE_MALLOC_H */
635 #ifdef HAVE_USR_INCLUDE_MALLOC_H
636 #include "/usr/include/malloc.h"
637 #else /* HAVE_USR_INCLUDE_MALLOC_H */
640 MALLINFO_FIELD_TYPE arena
; /* non-mmapped space allocated from system */
641 MALLINFO_FIELD_TYPE ordblks
; /* number of free chunks */
642 MALLINFO_FIELD_TYPE smblks
; /* always 0 */
643 MALLINFO_FIELD_TYPE hblks
; /* always 0 */
644 MALLINFO_FIELD_TYPE hblkhd
; /* space in mmapped regions */
645 MALLINFO_FIELD_TYPE usmblks
; /* maximum total allocated space */
646 MALLINFO_FIELD_TYPE fsmblks
; /* always 0 */
647 MALLINFO_FIELD_TYPE uordblks
; /* total allocated space */
648 MALLINFO_FIELD_TYPE fordblks
; /* total free space */
649 MALLINFO_FIELD_TYPE keepcost
; /* releasable (via malloc_trim) space */
652 #endif /* HAVE_USR_INCLUDE_MALLOC_H */
653 #endif /* NO_MALLINFO */
657 #endif /* __cplusplus */
661 /* ------------------- Declarations of public routines ------------------- */
663 #ifndef USE_DL_PREFIX
664 #define dlcalloc calloc
666 #define dlmalloc malloc
667 #define dlmemalign memalign
668 #define dlrealloc realloc
669 #define dlvalloc valloc
670 #define dlpvalloc pvalloc
671 #define dlmallinfo mallinfo
672 #define dlmallopt mallopt
673 #define dlmalloc_trim malloc_trim
674 #define dlmalloc_stats malloc_stats
675 #define dlmalloc_usable_size malloc_usable_size
676 #define dlmalloc_footprint malloc_footprint
677 #define dlmalloc_max_footprint malloc_max_footprint
678 #define dlindependent_calloc independent_calloc
679 #define dlindependent_comalloc independent_comalloc
680 #endif /* USE_DL_PREFIX */
685 Returns a pointer to a newly allocated chunk of at least n bytes, or
686 null if no space is available, in which case errno is set to ENOMEM
689 If n is zero, malloc returns a minimum-sized chunk. (The minimum
690 size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
691 systems.) Note that size_t is an unsigned type, so calls with
692 arguments that would be negative if signed are interpreted as
693 requests for huge amounts of space, which will often fail. The
694 maximum supported value of n differs across systems, but is in all
695 cases less than the maximum representable value of a size_t.
697 void* dlmalloc(size_t);
701 Releases the chunk of memory pointed to by p, that had been previously
702 allocated using malloc or a related routine such as realloc.
703 It has no effect if p is null. If p was not malloced or already
704 freed, free(p) will by default cause the current program to abort.
709 calloc(size_t n_elements, size_t element_size);
710 Returns a pointer to n_elements * element_size bytes, with all locations
713 void* dlcalloc(size_t, size_t);
716 realloc(void* p, size_t n)
717 Returns a pointer to a chunk of size n that contains the same data
718 as does chunk p up to the minimum of (n, p's size) bytes, or null
719 if no space is available.
721 The returned pointer may or may not be the same as p. The algorithm
722 prefers extending p in most cases when possible, otherwise it
723 employs the equivalent of a malloc-copy-free sequence.
725 If p is null, realloc is equivalent to malloc.
727 If space is not available, realloc returns null, errno is set (if on
728 ANSI) and p is NOT freed.
730 if n is for fewer bytes than already held by p, the newly unused
731 space is lopped off and freed if possible. realloc with a size
732 argument of zero (re)allocates a minimum-sized chunk.
734 The old unix realloc convention of allowing the last-free'd chunk
735 to be used as an argument to realloc is not supported.
738 void* dlrealloc(void*, size_t);
741 memalign(size_t alignment, size_t n);
742 Returns a pointer to a newly allocated chunk of n bytes, aligned
743 in accord with the alignment argument.
745 The alignment argument should be a power of two. If the argument is
746 not a power of two, the nearest greater power is used.
747 8-byte alignment is guaranteed by normal malloc calls, so don't
748 bother calling memalign with an argument of 8 or less.
750 Overreliance on memalign is a sure way to fragment space.
752 void* dlmemalign(size_t, size_t);
756 Equivalent to memalign(pagesize, n), where pagesize is the page
757 size of the system. If the pagesize is unknown, 4096 is used.
759 void* dlvalloc(size_t);
762 mallopt(int parameter_number, int parameter_value)
763 Sets tunable parameters The format is to provide a
764 (parameter-number, parameter-value) pair. mallopt then sets the
765 corresponding parameter to the argument value if it can (i.e., so
766 long as the value is meaningful), and returns 1 if successful else
767 0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
768 normally defined in malloc.h. None of these are use in this malloc,
769 so setting them has no effect. But this malloc also supports other
770 options in mallopt. See below for details. Briefly, supported
771 parameters are as follows (listed defaults are for "typical"
774 Symbol param # default allowed param values
775 M_TRIM_THRESHOLD -1 2*1024*1024 any (MAX_SIZE_T disables)
776 M_GRANULARITY -2 page size any power of 2 >= page size
777 M_MMAP_THRESHOLD -3 256*1024 any (or 0 if no MMAP support)
779 int dlmallopt(int, int);
783 Returns the number of bytes obtained from the system. The total
784 number of bytes allocated by malloc, realloc etc., is less than this
785 value. Unlike mallinfo, this function returns only a precomputed
786 result, so can be called frequently to monitor memory consumption.
787 Even if locks are otherwise defined, this function does not use them,
788 so results might not be up to date.
790 size_t dlmalloc_footprint(void);
793 malloc_max_footprint();
794 Returns the maximum number of bytes obtained from the system. This
795 value will be greater than current footprint if deallocated space
796 has been reclaimed by the system. The peak number of bytes allocated
797 by malloc, realloc etc., is less than this value. Unlike mallinfo,
798 this function returns only a precomputed result, so can be called
799 frequently to monitor memory consumption. Even if locks are
800 otherwise defined, this function does not use them, so results might
803 size_t dlmalloc_max_footprint(void);
808 Returns (by copy) a struct containing various summary statistics:
810 arena: current total non-mmapped bytes allocated from system
811 ordblks: the number of free chunks
813 hblks: current number of mmapped regions
814 hblkhd: total bytes held in mmapped regions
815 usmblks: the maximum total allocated space. This will be greater
816 than current total if trimming has occurred.
818 uordblks: current total allocated space (normal or mmapped)
819 fordblks: total free space
820 keepcost: the maximum number of bytes that could ideally be released
821 back to system via malloc_trim. ("ideally" means that
822 it ignores page restrictions etc.)
824 Because these fields are ints, but internal bookkeeping may
825 be kept as longs, the reported values may wrap around zero and
828 struct mallinfo
dlmallinfo(void);
829 #endif /* NO_MALLINFO */
832 independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
834 independent_calloc is similar to calloc, but instead of returning a
835 single cleared space, it returns an array of pointers to n_elements
836 independent elements that can hold contents of size elem_size, each
837 of which starts out cleared, and can be independently freed,
838 realloc'ed etc. The elements are guaranteed to be adjacently
839 allocated (this is not guaranteed to occur with multiple callocs or
840 mallocs), which may also improve cache locality in some
843 The "chunks" argument is optional (i.e., may be null, which is
844 probably the most typical usage). If it is null, the returned array
845 is itself dynamically allocated and should also be freed when it is
846 no longer needed. Otherwise, the chunks array must be of at least
847 n_elements in length. It is filled in with the pointers to the
850 In either case, independent_calloc returns this pointer array, or
851 null if the allocation failed. If n_elements is zero and "chunks"
852 is null, it returns a chunk representing an array with zero elements
853 (which should be freed if not wanted).
855 Each element must be individually freed when it is no longer
856 needed. If you'd like to instead be able to free all at once, you
857 should instead use regular calloc and assign pointers into this
858 space to represent elements. (In this case though, you cannot
859 independently free elements.)
861 independent_calloc simplifies and speeds up implementations of many
862 kinds of pools. It may also be useful when constructing large data
863 structures that initially have a fixed number of fixed-sized nodes,
864 but the number is not known at compile time, and some of the nodes
865 may later need to be freed. For example:
867 struct Node { int item; struct Node* next; };
869 struct Node* build_list() {
871 int n = read_number_of_nodes_needed();
872 if (n <= 0) return 0;
873 pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
874 if (pool == 0) die();
875 // organize into a linked list...
876 struct Node* first = pool[0];
877 for (i = 0; i < n-1; ++i)
878 pool[i]->next = pool[i+1];
879 free(pool); // Can now free the array (or not, if it is needed later)
883 void** dlindependent_calloc(size_t, size_t, void**);
886 independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
888 independent_comalloc allocates, all at once, a set of n_elements
889 chunks with sizes indicated in the "sizes" array. It returns
890 an array of pointers to these elements, each of which can be
891 independently freed, realloc'ed etc. The elements are guaranteed to
892 be adjacently allocated (this is not guaranteed to occur with
893 multiple callocs or mallocs), which may also improve cache locality
894 in some applications.
896 The "chunks" argument is optional (i.e., may be null). If it is null
897 the returned array is itself dynamically allocated and should also
898 be freed when it is no longer needed. Otherwise, the chunks array
899 must be of at least n_elements in length. It is filled in with the
900 pointers to the chunks.
902 In either case, independent_comalloc returns this pointer array, or
903 null if the allocation failed. If n_elements is zero and chunks is
904 null, it returns a chunk representing an array with zero elements
905 (which should be freed if not wanted).
907 Each element must be individually freed when it is no longer
908 needed. If you'd like to instead be able to free all at once, you
909 should instead use a single regular malloc, and assign pointers at
910 particular offsets in the aggregate space. (In this case though, you
911 cannot independently free elements.)
913 independent_comallac differs from independent_calloc in that each
914 element may have a different size, and also that it does not
915 automatically clear elements.
917 independent_comalloc can be used to speed up allocation in cases
918 where several structs or objects must always be allocated at the
919 same time. For example:
924 void send_message(char* msg) {
925 int msglen = strlen(msg);
926 size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
928 if (independent_comalloc(3, sizes, chunks) == 0)
930 struct Head* head = (struct Head*)(chunks[0]);
931 char* body = (char*)(chunks[1]);
932 struct Foot* foot = (struct Foot*)(chunks[2]);
936 In general though, independent_comalloc is worth using only for
937 larger values of n_elements. For small values, you probably won't
938 detect enough difference from series of malloc calls to bother.
940 Overuse of independent_comalloc can increase overall memory usage,
941 since it cannot reuse existing noncontiguous small chunks that
942 might be available for some of the elements.
944 void** dlindependent_comalloc(size_t, size_t*, void**);
949 Equivalent to valloc(minimum-page-that-holds(n)), that is,
950 round up n to nearest pagesize.
952 void* dlpvalloc(size_t);
955 malloc_trim(size_t pad);
957 If possible, gives memory back to the system (via negative arguments
958 to sbrk) if there is unused memory at the `high' end of the malloc
959 pool or in unused MMAP segments. You can call this after freeing
960 large blocks of memory to potentially reduce the system-level memory
961 requirements of a program. However, it cannot guarantee to reduce
962 memory. Under some allocation patterns, some large free blocks of
963 memory will be locked between two used chunks, so they cannot be
964 given back to the system.
966 The `pad' argument to malloc_trim represents the amount of free
967 trailing space to leave untrimmed. If this argument is zero, only
968 the minimum amount of memory to maintain internal data structures
969 will be left. Non-zero arguments can be supplied to maintain enough
970 trailing space to service future expected allocations without having
971 to re-obtain memory from the system.
973 Malloc_trim returns 1 if it actually released any memory, else 0.
975 int dlmalloc_trim(size_t);
978 malloc_usable_size(void* p);
980 Returns the number of bytes you can actually use in
981 an allocated chunk, which may be more than you requested (although
982 often not) due to alignment and minimum size constraints.
983 You can use this many bytes without worrying about
984 overwriting other allocated objects. This is not a particularly great
985 programming practice. malloc_usable_size can be more useful in
986 debugging and assertions, for example:
989 assert(malloc_usable_size(p) >= 256);
991 size_t dlmalloc_usable_size(void*);
995 Prints on stderr the amount of space obtained from the system (both
996 via sbrk and mmap), the maximum amount (which may be more than
997 current if malloc_trim and/or munmap got called), and the current
998 number of bytes allocated via malloc (or realloc, etc) but not yet
999 freed. Note that this is the number of bytes allocated, not the
1000 number requested. It will be larger than the number requested
1001 because of alignment and bookkeeping overhead. Because it includes
1002 alignment wastage as being in use, this figure may be greater than
1003 zero even when no user-level chunks are allocated.
1005 The reported current and maximum system memory can be inaccurate if
1006 a program makes other calls to system memory allocation functions
1007 (normally sbrk) outside of malloc.
1009 malloc_stats prints only the most commonly interesting statistics.
1010 More information can be obtained by calling mallinfo.
1012 void dlmalloc_stats(void);
1014 #endif /* ONLY_MSPACES */
1019 mspace is an opaque type representing an independent
1020 region of space that supports mspace_malloc, etc.
1022 typedef void* mspace
;
1025 create_mspace creates and returns a new independent space with the
1026 given initial capacity, or, if 0, the default granularity size. It
1027 returns null if there is no system memory available to create the
1028 space. If argument locked is non-zero, the space uses a separate
1029 lock to control access. The capacity of the space will grow
1030 dynamically as needed to service mspace_malloc requests. You can
1031 control the sizes of incremental increases of this space by
1032 compiling with a different DEFAULT_GRANULARITY or dynamically
1033 setting with mallopt(M_GRANULARITY, value).
1035 mspace
create_mspace(size_t capacity
, int locked
);
1038 destroy_mspace destroys the given space, and attempts to return all
1039 of its memory back to the system, returning the total number of
1040 bytes freed. After destruction, the results of access to all memory
1041 used by the space become undefined.
1043 size_t destroy_mspace(mspace msp
);
1046 create_mspace_with_base uses the memory supplied as the initial base
1047 of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
1048 space is used for bookkeeping, so the capacity must be at least this
1049 large. (Otherwise 0 is returned.) When this initial space is
1050 exhausted, additional memory will be obtained from the system.
1051 Destroying this space will deallocate all additionally allocated
1052 space (if possible) but not the initial base.
1054 mspace
create_mspace_with_base(void* base
, size_t capacity
, int locked
);
1057 mspace_malloc behaves as malloc, but operates within
1060 void* mspace_malloc(mspace msp
, size_t bytes
);
1063 mspace_free behaves as free, but operates within
1066 If compiled with FOOTERS==1, mspace_free is not actually needed.
1067 free may be called instead of mspace_free because freed chunks from
1068 any space are handled by their originating spaces.
1070 void mspace_free(mspace msp
, void* mem
);
1073 mspace_realloc behaves as realloc, but operates within
1076 If compiled with FOOTERS==1, mspace_realloc is not actually
1077 needed. realloc may be called instead of mspace_realloc because
1078 realloced chunks from any space are handled by their originating
1081 void* mspace_realloc(mspace msp
, void* mem
, size_t newsize
);
1084 mspace_calloc behaves as calloc, but operates within
1087 void* mspace_calloc(mspace msp
, size_t n_elements
, size_t elem_size
);
1090 mspace_memalign behaves as memalign, but operates within
1093 void* mspace_memalign(mspace msp
, size_t alignment
, size_t bytes
);
1096 mspace_independent_calloc behaves as independent_calloc, but
1097 operates within the given space.
1099 void** mspace_independent_calloc(mspace msp
, size_t n_elements
,
1100 size_t elem_size
, void* chunks
[]);
1103 mspace_independent_comalloc behaves as independent_comalloc, but
1104 operates within the given space.
1106 void** mspace_independent_comalloc(mspace msp
, size_t n_elements
,
1107 size_t sizes
[], void* chunks
[]);
1110 mspace_footprint() returns the number of bytes obtained from the
1111 system for this space.
1113 size_t mspace_footprint(mspace msp
);
1116 mspace_max_footprint() returns the peak number of bytes obtained from the
1117 system for this space.
1119 size_t mspace_max_footprint(mspace msp
);
1124 mspace_mallinfo behaves as mallinfo, but reports properties of
1127 struct mallinfo
mspace_mallinfo(mspace msp
);
1128 #endif /* NO_MALLINFO */
1131 mspace_malloc_stats behaves as malloc_stats, but reports
1132 properties of the given space.
1134 void mspace_malloc_stats(mspace msp
);
1137 mspace_trim behaves as malloc_trim, but
1138 operates within the given space.
1140 int mspace_trim(mspace msp
, size_t pad
);
1143 An alias for mallopt.
1145 int mspace_mallopt(int, int);
1147 #endif /* MSPACES */
1150 }; /* end of extern "C" */
1151 #endif /* __cplusplus */
1154 ========================================================================
1155 To make a fully customizable malloc.h header file, cut everything
1156 above this line, put into file malloc.h, edit to suit, and #include it
1157 on the next line, as well as in programs that use this malloc.
1158 ========================================================================
1161 /* #include "malloc.h" */
1163 /*------------------------------ internal #includes ---------------------- */
1166 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
1169 #include <stdio.h> /* for printing in malloc_stats */
1171 #ifndef LACKS_ERRNO_H
1172 #include <errno.h> /* for MALLOC_FAILURE_ACTION */
1173 #endif /* LACKS_ERRNO_H */
1175 #include <time.h> /* for magic initialization */
1176 #endif /* FOOTERS */
1177 #ifndef LACKS_STDLIB_H
1178 #include <stdlib.h> /* for abort() */
1179 #endif /* LACKS_STDLIB_H */
1181 #if ABORT_ON_ASSERT_FAILURE
1182 #define assert(x) if(!(x)) ABORT
1183 #else /* ABORT_ON_ASSERT_FAILURE */
1185 #endif /* ABORT_ON_ASSERT_FAILURE */
1189 #ifndef LACKS_STRING_H
1190 #include <string.h> /* for memset etc */
1191 #endif /* LACKS_STRING_H */
1193 #if !defined(LACKS_STRINGS_H) && defined(HAVE_STRINGS_H)
1194 #include <strings.h> /* for ffs */
1195 #endif /* LACKS_STRINGS_H */
1196 #endif /* USE_BUILTIN_FFS */
1198 #ifndef LACKS_SYS_MMAN_H
1199 #include <sys/mman.h> /* for mmap */
1200 #endif /* LACKS_SYS_MMAN_H */
1201 #ifndef LACKS_FCNTL_H
1203 #endif /* LACKS_FCNTL_H */
1204 #endif /* HAVE_MMAP */
1206 #ifndef LACKS_UNISTD_H
1207 #include <unistd.h> /* for sbrk */
1208 #else /* LACKS_UNISTD_H */
1209 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
1210 extern void* sbrk(ptrdiff_t);
1211 #endif /* FreeBSD etc */
1212 #endif /* LACKS_UNISTD_H */
1213 #endif /* HAVE_MMAP */
1216 #ifndef malloc_getpagesize
1217 # ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
1218 # ifndef _SC_PAGE_SIZE
1219 # define _SC_PAGE_SIZE _SC_PAGESIZE
1222 # if defined (HAVE_SYSCONF) && defined (_SC_PAGESIZE)
1223 # define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
1225 # if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
1226 extern size_t getpagesize();
1227 # define malloc_getpagesize getpagesize()
1229 # ifdef WIN32 /* use supplied emulation of getpagesize */
1230 # define malloc_getpagesize getpagesize()
1232 # ifndef LACKS_SYS_PARAM_H
1233 # include <sys/param.h>
1235 # ifdef EXEC_PAGESIZE
1236 # define malloc_getpagesize EXEC_PAGESIZE
1240 # define malloc_getpagesize NBPG
1242 # define malloc_getpagesize (NBPG * CLSIZE)
1246 # define malloc_getpagesize NBPC
1249 # define malloc_getpagesize PAGESIZE
1250 # else /* just guess */
1251 # define malloc_getpagesize ((size_t)4096U)
1262 /* ------------------- size_t and alignment properties -------------------- */
1264 /* The byte and bit size of a size_t */
1265 #define SIZE_T_SIZE (sizeof(size_t))
1266 #define SIZE_T_BITSIZE (sizeof(size_t) << 3)
1268 /* Some constants coerced to size_t */
1269 /* Annoying but necessary to avoid errors on some plaftorms */
1270 #define SIZE_T_ZERO ((size_t)0)
1271 #define SIZE_T_ONE ((size_t)1)
1272 #define SIZE_T_TWO ((size_t)2)
1273 #define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)
1274 #define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)
1275 #define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
1276 #define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
1278 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
1279 #define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)
1281 /* True if address a has acceptable alignment */
1282 #define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
1284 /* the number of bytes to offset an address to align it */
1285 #define align_offset(A)\
1286 ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
1287 ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
1289 /* -------------------------- MMAP preliminaries ------------------------- */
1292 If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
1293 checks to fail so compiler optimizer can delete code rather than
1294 using so many "#if"s.
1298 /* MORECORE and MMAP must return MFAIL on failure */
1299 #define MFAIL ((void*)(MAX_SIZE_T))
1300 #define CMFAIL ((char*)(MFAIL)) /* defined for convenience */
1303 #define IS_MMAPPED_BIT (SIZE_T_ZERO)
1304 #define USE_MMAP_BIT (SIZE_T_ZERO)
1305 #define CALL_MMAP(s) MFAIL
1306 #define CALL_MUNMAP(a, s) (-1)
1307 #define DIRECT_MMAP(s) MFAIL
1309 #else /* HAVE_MMAP */
1310 #define IS_MMAPPED_BIT (SIZE_T_ONE)
1311 #define USE_MMAP_BIT (SIZE_T_ONE)
1314 //#define CALL_MUNMAP(a, s) munmap((a), (s))
1315 #define CALL_MUNMAP(a, s) mono_vfree((a), (s), MONO_MEM_ACCOUNT_CODE)
1316 #define MMAP_PROT (PROT_READ|PROT_WRITE|PROT_EXEC)
1317 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1318 #define MAP_ANONYMOUS MAP_ANON
1319 #endif /* MAP_ANON */
1320 #ifdef MAP_ANONYMOUS
1321 #define MMAP_FLAGS (MAP_PRIVATE|MAP_ANONYMOUS)
1323 //#define CALL_MMAP(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
1324 #define CALL_MMAP(s) mono_valloc(NULL, (s), MONO_MMAP_READ|MONO_MMAP_WRITE|MONO_MMAP_EXEC|MONO_MMAP_JIT, MONO_MEM_ACCOUNT_CODE)
1326 #else /* MAP_ANONYMOUS */
1328 Nearly all versions of mmap support MAP_ANONYMOUS, so the following
1329 is unlikely to be needed, but is supplied just in case.
1331 #define MMAP_FLAGS (MAP_PRIVATE)
1332 static int dev_zero_fd
= -1; /* Cached file descriptor for /dev/zero. */
1333 #define CALL_MMAP(s) ((dev_zero_fd < 0) ? \
1334 (dev_zero_fd = open("/dev/zero", O_RDWR), \
1335 mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
1336 mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
1337 #endif /* MAP_ANONYMOUS */
1339 #define DIRECT_MMAP(s) CALL_MMAP(s)
1342 /* Win32 MMAP via VirtualAlloc */
1343 static void* win32mmap(size_t size
) {
1344 void* ptr
= VirtualAlloc(0, size
, MEM_RESERVE
|MEM_COMMIT
, PAGE_EXECUTE_READWRITE
);
1345 return (ptr
!= 0)? ptr
: MFAIL
;
1348 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
1349 static void* win32direct_mmap(size_t size
) {
1350 void* ptr
= VirtualAlloc(0, size
, MEM_RESERVE
|MEM_COMMIT
|MEM_TOP_DOWN
,
1351 PAGE_EXECUTE_READWRITE
);
1352 return (ptr
!= 0)? ptr
: MFAIL
;
1355 /* This function supports releasing coalesed segments */
1356 static int win32munmap(void* ptr
, size_t size
) {
1357 MEMORY_BASIC_INFORMATION minfo
;
1358 char* cptr
= (char*)ptr
;
1360 if (VirtualQuery(cptr
, &minfo
, sizeof(minfo
)) == 0)
1362 if (minfo
.BaseAddress
!= cptr
|| minfo
.AllocationBase
!= cptr
||
1363 minfo
.State
!= MEM_COMMIT
|| minfo
.RegionSize
> size
)
1365 if (VirtualFree(cptr
, 0, MEM_RELEASE
) == 0)
1367 cptr
+= minfo
.RegionSize
;
1368 size
-= minfo
.RegionSize
;
1373 #define CALL_MMAP(s) win32mmap(s)
1374 #define CALL_MUNMAP(a, s) win32munmap((a), (s))
1375 #define DIRECT_MMAP(s) win32direct_mmap(s)
1377 #endif /* HAVE_MMAP */
1379 #if HAVE_MMAP && HAVE_MREMAP
1381 #define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
1382 #elif defined(__NetBSD__)
1383 #define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (addr), (nsz), (mv))
1385 #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
1387 #else /* HAVE_MMAP && HAVE_MREMAP */
1388 #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
1389 #endif /* HAVE_MMAP && HAVE_MREMAP */
1392 #define CALL_MORECORE(S) MORECORE(S)
1393 #else /* HAVE_MORECORE */
1394 #define CALL_MORECORE(S) MFAIL
1395 #endif /* HAVE_MORECORE */
1397 /* mstate bit set if continguous morecore disabled or failed */
1398 #define USE_NONCONTIGUOUS_BIT (4U)
1400 /* segment bit set in create_mspace_with_base */
1401 #define EXTERN_BIT (8U)
1404 /* --------------------------- Lock preliminaries ------------------------ */
1409 When locks are defined, there are up to two global locks:
1411 * If HAVE_MORECORE, morecore_mutex protects sequences of calls to
1412 MORECORE. In many cases sys_alloc requires two calls, that should
1413 not be interleaved with calls by other threads. This does not
1414 protect against direct calls to MORECORE by other threads not
1415 using this lock, so there is still code to cope the best we can on
1418 * magic_init_mutex ensures that mparams.magic and other
1419 unique mparams values are initialized only once.
1423 /* By default use posix locks */
1424 #include <pthread.h>
1425 #define MLOCK_T pthread_mutex_t
1426 #define INITIAL_LOCK(l) pthread_mutex_init(l, NULL)
1427 #define ACQUIRE_LOCK(l) pthread_mutex_lock(l)
1428 #define RELEASE_LOCK(l) pthread_mutex_unlock(l)
1431 static MLOCK_T morecore_mutex
= PTHREAD_MUTEX_INITIALIZER
;
1432 #endif /* HAVE_MORECORE */
1434 static MLOCK_T magic_init_mutex
= PTHREAD_MUTEX_INITIALIZER
;
1438 Because lock-protected regions have bounded times, and there
1439 are no recursive lock calls, we can use simple spinlocks.
1442 #define MLOCK_T long
1443 static int win32_acquire_lock (MLOCK_T
*sl
) {
1445 #ifdef InterlockedCompareExchangePointer
1446 if (!InterlockedCompareExchange(sl
, 1, 0))
1448 #else /* Use older void* version */
1449 if (!InterlockedCompareExchange((void**)sl
, (void*)1, (void*)0))
1451 #endif /* InterlockedCompareExchangePointer */
1456 static void win32_release_lock (MLOCK_T
*sl
) {
1457 InterlockedExchange (sl
, 0);
1460 #define INITIAL_LOCK(l) *(l)=0
1461 #define ACQUIRE_LOCK(l) win32_acquire_lock(l)
1462 #define RELEASE_LOCK(l) win32_release_lock(l)
1464 static MLOCK_T morecore_mutex
;
1465 #endif /* HAVE_MORECORE */
1466 static MLOCK_T magic_init_mutex
;
1469 #define USE_LOCK_BIT (2U)
1470 #else /* USE_LOCKS */
1471 #define USE_LOCK_BIT (0U)
1472 #define INITIAL_LOCK(l)
1473 #endif /* USE_LOCKS */
1475 #if USE_LOCKS && HAVE_MORECORE
1476 #define ACQUIRE_MORECORE_LOCK() ACQUIRE_LOCK(&morecore_mutex);
1477 #define RELEASE_MORECORE_LOCK() RELEASE_LOCK(&morecore_mutex);
1478 #else /* USE_LOCKS && HAVE_MORECORE */
1479 #define ACQUIRE_MORECORE_LOCK()
1480 #define RELEASE_MORECORE_LOCK()
1481 #endif /* USE_LOCKS && HAVE_MORECORE */
1484 #define ACQUIRE_MAGIC_INIT_LOCK() ACQUIRE_LOCK(&magic_init_mutex);
1485 #define RELEASE_MAGIC_INIT_LOCK() RELEASE_LOCK(&magic_init_mutex);
1486 #else /* USE_LOCKS */
1487 #define ACQUIRE_MAGIC_INIT_LOCK()
1488 #define RELEASE_MAGIC_INIT_LOCK()
1489 #endif /* USE_LOCKS */
1492 /* ----------------------- Chunk representations ------------------------ */
1495 (The following includes lightly edited explanations by Colin Plumb.)
1497 The malloc_chunk declaration below is misleading (but accurate and
1498 necessary). It declares a "view" into memory allowing access to
1499 necessary fields at known offsets from a given base.
1501 Chunks of memory are maintained using a `boundary tag' method as
1502 originally described by Knuth. (See the paper by Paul Wilson
1503 ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
1504 techniques.) Sizes of free chunks are stored both in the front of
1505 each chunk and at the end. This makes consolidating fragmented
1506 chunks into bigger chunks fast. The head fields also hold bits
1507 representing whether chunks are free or in use.
1509 Here are some pictures to make it clearer. They are "exploded" to
1510 show that the state of a chunk can be thought of as extending from
1511 the high 31 bits of the head field of its header through the
1512 prev_foot and PINUSE_BIT bit of the following chunk header.
1514 A chunk that's in use looks like:
1516 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1517 | Size of previous chunk (if P = 1) |
1518 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1520 | Size of this chunk 1| +-+
1521 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1527 +- size - sizeof(size_t) available payload bytes -+
1531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1532 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
1533 | Size of next chunk (may or may not be in use) | +-+
1534 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1536 And if it's free, it looks like this:
1539 | User payload (must be in use, or we would have merged!) |
1540 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1541 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1542 | Size of this chunk 0| +-+
1543 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1549 +- size - sizeof(struct chunk) unused bytes -+
1551 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1552 | Size of this chunk |
1553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
1555 | Size of next chunk (must be in use, or we would have merged)| +-+
1556 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1560 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1563 Note that since we always merge adjacent free chunks, the chunks
1564 adjacent to a free chunk must be in use.
1566 Given a pointer to a chunk (which can be derived trivially from the
1567 payload pointer) we can, in O(1) time, find out whether the adjacent
1568 chunks are free, and if so, unlink them from the lists that they
1569 are on and merge them with the current chunk.
1571 Chunks always begin on even word boundaries, so the mem portion
1572 (which is returned to the user) is also on an even word boundary, and
1573 thus at least double-word aligned.
1575 The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
1576 chunk size (which is always a multiple of two words), is an in-use
1577 bit for the *previous* chunk. If that bit is *clear*, then the
1578 word before the current chunk size contains the previous chunk
1579 size, and can be used to find the front of the previous chunk.
1580 The very first chunk allocated always has this bit set, preventing
1581 access to non-existent (or non-owned) memory. If pinuse is set for
1582 any given chunk, then you CANNOT determine the size of the
1583 previous chunk, and might even get a memory addressing fault when
1586 The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
1587 the chunk size redundantly records whether the current chunk is
1588 inuse. This redundancy enables usage checks within free and realloc,
1589 and reduces indirection when freeing and consolidating chunks.
1591 Each freshly allocated chunk must have both cinuse and pinuse set.
1592 That is, each allocated chunk borders either a previously allocated
1593 and still in-use chunk, or the base of its memory arena. This is
1594 ensured by making all allocations from the the `lowest' part of any
1595 found chunk. Further, no free chunk physically borders another one,
1596 so each free chunk is known to be preceded and followed by either
1597 inuse chunks or the ends of memory.
1599 Note that the `foot' of the current chunk is actually represented
1600 as the prev_foot of the NEXT chunk. This makes it easier to
1601 deal with alignments etc but can be very confusing when trying
1602 to extend or adapt this code.
1604 The exceptions to all this are
1606 1. The special chunk `top' is the top-most available chunk (i.e.,
1607 the one bordering the end of available memory). It is treated
1608 specially. Top is never included in any bin, is used only if
1609 no other chunk is available, and is released back to the
1610 system if it is very large (see M_TRIM_THRESHOLD). In effect,
1611 the top chunk is treated as larger (and thus less well
1612 fitting) than any other available chunk. The top chunk
1613 doesn't update its trailing size field since there is no next
1614 contiguous chunk that would have to index off it. However,
1615 space is still allocated for it (TOP_FOOT_SIZE) to enable
1616 separation or merging when space is extended.
1618 3. Chunks allocated via mmap, which have the lowest-order bit
1619 (IS_MMAPPED_BIT) set in their prev_foot fields, and do not set
1620 PINUSE_BIT in their head fields. Because they are allocated
1621 one-by-one, each must carry its own prev_foot field, which is
1622 also used to hold the offset this chunk has within its mmapped
1623 region, which is needed to preserve alignment. Each mmapped
1624 chunk is trailed by the first two fields of a fake next-chunk
1625 for sake of usage checks.
1629 struct malloc_chunk
{
1630 size_t prev_foot
; /* Size of previous chunk (if free). */
1631 size_t head
; /* Size and inuse bits. */
1632 struct malloc_chunk
* fd
; /* double links -- used only if free. */
1633 struct malloc_chunk
* bk
;
1636 typedef struct malloc_chunk mchunk
;
1637 typedef struct malloc_chunk
* mchunkptr
;
1638 typedef struct malloc_chunk
* sbinptr
; /* The type of bins of chunks */
1639 typedef unsigned int bindex_t
; /* Described below */
1640 typedef unsigned int binmap_t
; /* Described below */
1641 typedef unsigned int flag_t
; /* The type of various bit flag sets */
1643 /* ------------------- Chunks sizes and alignments ----------------------- */
1645 #define MCHUNK_SIZE (sizeof(mchunk))
1648 #define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
1650 #define CHUNK_OVERHEAD (SIZE_T_SIZE)
1651 #endif /* FOOTERS */
1653 /* MMapped chunks need a second word of overhead ... */
1654 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
1655 /* ... and additional padding for fake next-chunk at foot */
1656 #define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES)
1658 /* The smallest size we can malloc is an aligned minimal chunk */
1659 #define MIN_CHUNK_SIZE\
1660 ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
1662 /* conversion from malloc headers to user pointers, and back */
1663 #define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))
1664 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
1665 /* chunk associated with aligned address A */
1666 #define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))
1668 /* Bounds on request (not chunk) sizes. */
1669 #define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)
1670 #define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
1672 /* pad request bytes into a usable size */
1673 #define pad_request(req) \
1674 (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
1676 /* pad request, checking for minimum (but not maximum) */
1677 #define request2size(req) \
1678 (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
1681 /* ------------------ Operations on head and foot fields ----------------- */
1684 The head field of a chunk is or'ed with PINUSE_BIT when previous
1685 adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
1686 use. If the chunk was obtained with mmap, the prev_foot field has
1687 IS_MMAPPED_BIT set, otherwise holding the offset of the base of the
1688 mmapped region to the base of the chunk.
1691 #define PINUSE_BIT (SIZE_T_ONE)
1692 #define CINUSE_BIT (SIZE_T_TWO)
1693 #define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)
1695 /* Head value for fenceposts */
1696 #define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)
1698 /* extraction of fields from head words */
1699 #define cinuse(p) ((p)->head & CINUSE_BIT)
1700 #define pinuse(p) ((p)->head & PINUSE_BIT)
1701 #define chunksize(p) ((p)->head & ~(INUSE_BITS))
1703 #define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)
1704 #define clear_cinuse(p) ((p)->head &= ~CINUSE_BIT)
1706 /* Treat space at ptr +/- offset as a chunk */
1707 #define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
1708 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
1710 /* Ptr to next or previous physical malloc_chunk. */
1711 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~INUSE_BITS)))
1712 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
1714 /* extract next chunk's pinuse bit */
1715 #define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)
1717 /* Get/set size at footer */
1718 #define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)
1719 #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
1721 /* Set size, pinuse bit, and foot */
1722 #define set_size_and_pinuse_of_free_chunk(p, s)\
1723 ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
1725 /* Set size, pinuse bit, foot, and clear next pinuse */
1726 #define set_free_with_pinuse(p, s, n)\
1727 (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
1729 #define is_mmapped(p)\
1730 (!((p)->head & PINUSE_BIT) && ((p)->prev_foot & IS_MMAPPED_BIT))
1732 /* Get the internal overhead associated with chunk p */
1733 #define overhead_for(p)\
1734 (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
1736 /* Return true if malloced space is not necessarily cleared */
1738 #define calloc_must_clear(p) (!is_mmapped(p))
1739 #else /* MMAP_CLEARS */
1740 #define calloc_must_clear(p) (1)
1741 #endif /* MMAP_CLEARS */
1743 /* ---------------------- Overlaid data structures ----------------------- */
1746 When chunks are not in use, they are treated as nodes of either
1749 "Small" chunks are stored in circular doubly-linked lists, and look
1752 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1753 | Size of previous chunk |
1754 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1755 `head:' | Size of chunk, in bytes |P|
1756 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1757 | Forward pointer to next chunk in list |
1758 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1759 | Back pointer to previous chunk in list |
1760 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1761 | Unused space (may be 0 bytes long) .
1764 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1765 `foot:' | Size of chunk, in bytes |
1766 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1768 Larger chunks are kept in a form of bitwise digital trees (aka
1769 tries) keyed on chunksizes. Because malloc_tree_chunks are only for
1770 free chunks greater than 256 bytes, their size doesn't impose any
1771 constraints on user chunk sizes. Each node looks like:
1773 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1774 | Size of previous chunk |
1775 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1776 `head:' | Size of chunk, in bytes |P|
1777 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1778 | Forward pointer to next chunk of same size |
1779 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1780 | Back pointer to previous chunk of same size |
1781 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1782 | Pointer to left child (child[0]) |
1783 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1784 | Pointer to right child (child[1]) |
1785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1786 | Pointer to parent |
1787 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1788 | bin index of this chunk |
1789 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1792 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1793 `foot:' | Size of chunk, in bytes |
1794 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1796 Each tree holding treenodes is a tree of unique chunk sizes. Chunks
1797 of the same size are arranged in a circularly-linked list, with only
1798 the oldest chunk (the next to be used, in our FIFO ordering)
1799 actually in the tree. (Tree members are distinguished by a non-null
1800 parent pointer.) If a chunk with the same size an an existing node
1801 is inserted, it is linked off the existing node using pointers that
1802 work in the same way as fd/bk pointers of small chunks.
1804 Each tree contains a power of 2 sized range of chunk sizes (the
1805 smallest is 0x100 <= x < 0x180), which is is divided in half at each
1806 tree level, with the chunks in the smaller half of the range (0x100
1807 <= x < 0x140 for the top nose) in the left subtree and the larger
1808 half (0x140 <= x < 0x180) in the right subtree. This is, of course,
1809 done by inspecting individual bits.
1811 Using these rules, each node's left subtree contains all smaller
1812 sizes than its right subtree. However, the node at the root of each
1813 subtree has no particular ordering relationship to either. (The
1814 dividing line between the subtree sizes is based on trie relation.)
1815 If we remove the last chunk of a given size from the interior of the
1816 tree, we need to replace it with a leaf node. The tree ordering
1817 rules permit a node to be replaced by any leaf below it.
1819 The smallest chunk in a tree (a common operation in a best-fit
1820 allocator) can be found by walking a path to the leftmost leaf in
1821 the tree. Unlike a usual binary tree, where we follow left child
1822 pointers until we reach a null, here we follow the right child
1823 pointer any time the left one is null, until we reach a leaf with
1824 both child pointers null. The smallest chunk in the tree will be
1825 somewhere along that path.
1827 The worst case number of steps to add, find, or remove a node is
1828 bounded by the number of bits differentiating chunks within
1829 bins. Under current bin calculations, this ranges from 6 up to 21
1830 (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
1831 is of course much better.
1834 struct malloc_tree_chunk
{
1835 /* The first four fields must be compatible with malloc_chunk */
1838 struct malloc_tree_chunk
* fd
;
1839 struct malloc_tree_chunk
* bk
;
1841 struct malloc_tree_chunk
* child
[2];
1842 struct malloc_tree_chunk
* parent
;
1846 typedef struct malloc_tree_chunk tchunk
;
1847 typedef struct malloc_tree_chunk
* tchunkptr
;
1848 typedef struct malloc_tree_chunk
* tbinptr
; /* The type of bins of trees */
1850 /* A little helper macro for trees */
1851 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
1853 /* ----------------------------- Segments -------------------------------- */
1856 Each malloc space may include non-contiguous segments, held in a
1857 list headed by an embedded malloc_segment record representing the
1858 top-most space. Segments also include flags holding properties of
1859 the space. Large chunks that are directly allocated by mmap are not
1860 included in this list. They are instead independently created and
1861 destroyed without otherwise keeping track of them.
1863 Segment management mainly comes into play for spaces allocated by
1864 MMAP. Any call to MMAP might or might not return memory that is
1865 adjacent to an existing segment. MORECORE normally contiguously
1866 extends the current space, so this space is almost always adjacent,
1867 which is simpler and faster to deal with. (This is why MORECORE is
1868 used preferentially to MMAP when both are available -- see
1869 sys_alloc.) When allocating using MMAP, we don't use any of the
1870 hinting mechanisms (inconsistently) supported in various
1871 implementations of unix mmap, or distinguish reserving from
1872 committing memory. Instead, we just ask for space, and exploit
1873 contiguity when we get it. It is probably possible to do
1874 better than this on some systems, but no general scheme seems
1875 to be significantly better.
1877 Management entails a simpler variant of the consolidation scheme
1878 used for chunks to reduce fragmentation -- new adjacent memory is
1879 normally prepended or appended to an existing segment. However,
1880 there are limitations compared to chunk consolidation that mostly
1881 reflect the fact that segment processing is relatively infrequent
1882 (occurring only when getting memory from system) and that we
1883 don't expect to have huge numbers of segments:
1885 * Segments are not indexed, so traversal requires linear scans. (It
1886 would be possible to index these, but is not worth the extra
1887 overhead and complexity for most programs on most platforms.)
1888 * New segments are only appended to old ones when holding top-most
1889 memory; if they cannot be prepended to others, they are held in
1892 Except for the top-most segment of an mstate, each segment record
1893 is kept at the tail of its segment. Segments are added by pushing
1894 segment records onto the list headed by &mstate.seg for the
1897 Segment flags control allocation/merge/deallocation policies:
1898 * If EXTERN_BIT set, then we did not allocate this segment,
1899 and so should not try to deallocate or merge with others.
1900 (This currently holds only for the initial segment passed
1901 into create_mspace_with_base.)
1902 * If IS_MMAPPED_BIT set, the segment may be merged with
1903 other surrounding mmapped segments and trimmed/de-allocated
1905 * If neither bit is set, then the segment was obtained using
1906 MORECORE so can be merged with surrounding MORECORE'd segments
1907 and deallocated/trimmed using MORECORE with negative arguments.
1910 struct malloc_segment
{
1911 char* base
; /* base address */
1912 size_t size
; /* allocated size */
1913 struct malloc_segment
* next
; /* ptr to next segment */
1914 flag_t sflags
; /* mmap and extern flag */
1917 #define is_mmapped_segment(S) ((S)->sflags & IS_MMAPPED_BIT)
1918 #define is_extern_segment(S) ((S)->sflags & EXTERN_BIT)
1920 typedef struct malloc_segment msegment
;
1921 typedef struct malloc_segment
* msegmentptr
;
1923 /* ---------------------------- malloc_state ----------------------------- */
1926 A malloc_state holds all of the bookkeeping for a space.
1927 The main fields are:
1930 The topmost chunk of the currently active segment. Its size is
1931 cached in topsize. The actual size of topmost space is
1932 topsize+TOP_FOOT_SIZE, which includes space reserved for adding
1933 fenceposts and segment records if necessary when getting more
1934 space from the system. The size at which to autotrim top is
1935 cached from mparams in trim_check, except that it is disabled if
1938 Designated victim (dv)
1939 This is the preferred chunk for servicing small requests that
1940 don't have exact fits. It is normally the chunk split off most
1941 recently to service another small request. Its size is cached in
1942 dvsize. The link fields of this chunk are not maintained since it
1943 is not kept in a bin.
1946 An array of bin headers for free chunks. These bins hold chunks
1947 with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
1948 chunks of all the same size, spaced 8 bytes apart. To simplify
1949 use in double-linked lists, each bin header acts as a malloc_chunk
1950 pointing to the real first node, if it exists (else pointing to
1951 itself). This avoids special-casing for headers. But to avoid
1952 waste, we allocate only the fd/bk pointers of bins, and then use
1953 repositioning tricks to treat these as the fields of a chunk.
1956 Treebins are pointers to the roots of trees holding a range of
1957 sizes. There are 2 equally spaced treebins for each power of two
1958 from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
1962 There is one bit map for small bins ("smallmap") and one for
1963 treebins ("treemap). Each bin sets its bit when non-empty, and
1964 clears the bit when empty. Bit operations are then used to avoid
1965 bin-by-bin searching -- nearly all "search" is done without ever
1966 looking at bins that won't be selected. The bit maps
1967 conservatively use 32 bits per map word, even if on 64bit system.
1968 For a good description of some of the bit-based techniques used
1969 here, see Henry S. Warren Jr's book "Hacker's Delight" (and
1970 supplement at http://hackersdelight.org/). Many of these are
1971 intended to reduce the branchiness of paths through malloc etc, as
1972 well as to reduce the number of memory locations read or written.
1975 A list of segments headed by an embedded malloc_segment record
1976 representing the initial space.
1978 Address check support
1979 The least_addr field is the least address ever obtained from
1980 MORECORE or MMAP. Attempted frees and reallocs of any address less
1981 than this are trapped (unless INSECURE is defined).
1984 A cross-check field that should always hold same value as mparams.magic.
1987 Bits recording whether to use MMAP, locks, or contiguous MORECORE
1990 Each space keeps track of current and maximum system memory
1991 obtained via MORECORE or MMAP.
1994 If USE_LOCKS is defined, the "mutex" lock is acquired and released
1995 around every public call using this mspace.
1998 /* Bin types, widths and sizes */
1999 #define NSMALLBINS (32U)
2000 #define NTREEBINS (32U)
2001 #define SMALLBIN_SHIFT (3U)
2002 #define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)
2003 #define TREEBIN_SHIFT (8U)
2004 #define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)
2005 #define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)
2006 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
2008 struct malloc_state
{
2018 mchunkptr smallbins
[(NSMALLBINS
+1)*2];
2019 tbinptr treebins
[NTREEBINS
];
2021 size_t max_footprint
;
2024 MLOCK_T mutex
; /* locate lock among fields that rarely change */
2025 #endif /* USE_LOCKS */
2029 typedef struct malloc_state
* mstate
;
2031 /* ------------- Global malloc_state and malloc_params ------------------- */
2034 malloc_params holds global properties, including those that can be
2035 dynamically set using mallopt. There is a single instance, mparams,
2036 initialized in init_mparams.
2039 struct malloc_params
{
2043 size_t mmap_threshold
;
2044 size_t trim_threshold
;
2045 flag_t default_mflags
;
2048 static struct malloc_params mparams
;
2050 /* The global malloc_state used for all non-"mspace" calls */
2051 static struct malloc_state _gm_
;
2053 #define is_global(M) ((M) == &_gm_)
2054 #define is_initialized(M) ((M)->top != 0)
2056 /* -------------------------- system alloc setup ------------------------- */
2058 /* Operations on mflags */
2060 #define use_lock(M) ((M)->mflags & USE_LOCK_BIT)
2061 #define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)
2062 #define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)
2064 #define use_mmap(M) ((M)->mflags & USE_MMAP_BIT)
2065 #define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT)
2066 #define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT)
2068 #define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT)
2069 #define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT)
2071 #define set_lock(M,L)\
2072 ((M)->mflags = (L)?\
2073 ((M)->mflags | USE_LOCK_BIT) :\
2074 ((M)->mflags & ~USE_LOCK_BIT))
2076 /* page-align a size */
2077 #define page_align(S)\
2078 (((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
2080 /* granularity-align a size */
2081 #define granularity_align(S)\
2082 (((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))
2084 #define is_page_aligned(S)\
2085 (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
2086 #define is_granularity_aligned(S)\
2087 (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
2089 /* True if segment S holds address A */
2090 #define segment_holds(S, A)\
2091 ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
2093 /* Return segment holding given address */
2094 static msegmentptr
segment_holding(mstate m
, char* addr
) {
2095 msegmentptr sp
= &m
->seg
;
2097 if (addr
>= sp
->base
&& addr
< sp
->base
+ sp
->size
)
2099 if ((sp
= sp
->next
) == 0)
2104 /* Return true if segment contains a segment link */
2105 static int has_segment_link(mstate m
, msegmentptr ss
) {
2106 msegmentptr sp
= &m
->seg
;
2108 if ((char*)sp
>= ss
->base
&& (char*)sp
< ss
->base
+ ss
->size
)
2110 if ((sp
= sp
->next
) == 0)
2115 #ifndef MORECORE_CANNOT_TRIM
2116 #define should_trim(M,s) ((s) > (M)->trim_check)
2117 #else /* MORECORE_CANNOT_TRIM */
2118 #define should_trim(M,s) (0)
2119 #endif /* MORECORE_CANNOT_TRIM */
2122 TOP_FOOT_SIZE is padding at the end of a segment, including space
2123 that may be needed to place segment records and fenceposts when new
2124 noncontiguous segments are added.
2126 #define TOP_FOOT_SIZE\
2127 (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
2130 /* ------------------------------- Hooks -------------------------------- */
2133 PREACTION should be defined to return 0 on success, and nonzero on
2134 failure. If you are not using locking, you can redefine these to do
2140 /* Ensure locks are initialized */
2141 #define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())
2143 #define PREACTION(M) ((GLOBALLY_INITIALIZE() || use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
2144 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
2145 #else /* USE_LOCKS */
2148 #define PREACTION(M) (0)
2149 #endif /* PREACTION */
2152 #define POSTACTION(M)
2153 #endif /* POSTACTION */
2155 #endif /* USE_LOCKS */
2158 CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
2159 USAGE_ERROR_ACTION is triggered on detected bad frees and
2160 reallocs. The argument p is an address that might have triggered the
2161 fault. It is ignored by the two predefined actions, but might be
2162 useful in custom actions that try to help diagnose errors.
2165 #if PROCEED_ON_ERROR
2167 /* A count of the number of corruption errors causing resets */
2168 int malloc_corruption_error_count
;
2170 /* default corruption action */
2171 static void reset_on_error(mstate m
);
2173 #define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)
2174 #define USAGE_ERROR_ACTION(m, p)
2176 #else /* PROCEED_ON_ERROR */
2178 #ifndef CORRUPTION_ERROR_ACTION
2179 #define CORRUPTION_ERROR_ACTION(m) ABORT
2180 #endif /* CORRUPTION_ERROR_ACTION */
2182 #ifndef USAGE_ERROR_ACTION
2183 #define USAGE_ERROR_ACTION(m,p) ABORT
2184 #endif /* USAGE_ERROR_ACTION */
2186 #endif /* PROCEED_ON_ERROR */
2188 /* -------------------------- Debugging setup ---------------------------- */
2192 #define check_free_chunk(M,P)
2193 #define check_inuse_chunk(M,P)
2194 #define check_malloced_chunk(M,P,N)
2195 #define check_mmapped_chunk(M,P)
2196 #define check_malloc_state(M)
2197 #define check_top_chunk(M,P)
2200 #define check_free_chunk(M,P) do_check_free_chunk(M,P)
2201 #define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)
2202 #define check_top_chunk(M,P) do_check_top_chunk(M,P)
2203 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
2204 #define check_mmapped_chunk(M,P) do_check_mmapped_chunk(M,P)
2205 #define check_malloc_state(M) do_check_malloc_state(M)
2207 static void do_check_any_chunk(mstate m
, mchunkptr p
);
2208 static void do_check_top_chunk(mstate m
, mchunkptr p
);
2209 static void do_check_mmapped_chunk(mstate m
, mchunkptr p
);
2210 static void do_check_inuse_chunk(mstate m
, mchunkptr p
);
2211 static void do_check_free_chunk(mstate m
, mchunkptr p
);
2212 static void do_check_malloced_chunk(mstate m
, void* mem
, size_t s
);
2213 static void do_check_tree(mstate m
, tchunkptr t
);
2214 static void do_check_treebin(mstate m
, bindex_t i
);
2215 static void do_check_smallbin(mstate m
, bindex_t i
);
2216 static void do_check_malloc_state(mstate m
);
2217 static int bin_find(mstate m
, mchunkptr x
);
2218 static size_t traverse_and_check(mstate m
);
2221 /* ---------------------------- Indexing Bins ---------------------------- */
2223 #define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
2224 #define small_index(s) ((s) >> SMALLBIN_SHIFT)
2225 #define small_index2size(i) ((i) << SMALLBIN_SHIFT)
2226 #define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))
2228 /* addressing by index. See above about smallbin repositioning */
2229 #define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
2230 #define treebin_at(M,i) (&((M)->treebins[i]))
2232 /* assign tree index for size S to variable I */
2233 #if defined(__GNUC__) && defined(i386)
2234 #define compute_tree_index(S, I)\
2236 size_t X = S >> TREEBIN_SHIFT;\
2239 else if (X > 0xFFFF)\
2243 __asm__("bsrl %1,%0\n\t" : "=r" (K) : "rm" (X));\
2244 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2248 #define compute_tree_index(S, I)\
2250 size_t X = S >> TREEBIN_SHIFT;\
2253 else if (X > 0xFFFF)\
2256 unsigned int Y = (unsigned int)X;\
2257 unsigned int N = ((Y - 0x100) >> 16) & 8;\
2258 unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
2260 N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
2261 K = 14 - N + ((Y <<= K) >> 15);\
2262 I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
2267 /* Bit representing maximum resolved size in a treebin at i */
2268 #define bit_for_tree_index(i) \
2269 (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
2271 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
2272 #define leftshift_for_tree_index(i) \
2273 ((i == NTREEBINS-1)? 0 : \
2274 ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
2276 /* The size of the smallest chunk held in bin with index i */
2277 #define minsize_for_tree_index(i) \
2278 ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \
2279 (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
2282 /* ------------------------ Operations on bin maps ----------------------- */
2284 /* bit corresponding to given index */
2285 #define idx2bit(i) ((binmap_t)(1) << (i))
2287 /* Mark/Clear bits with given index */
2288 #define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))
2289 #define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))
2290 #define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))
2292 #define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))
2293 #define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))
2294 #define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))
2296 /* index corresponding to given bit */
2298 #if defined(__GNUC__) && defined(i386)
2299 #define compute_bit2idx(X, I)\
2302 __asm__("bsfl %1,%0\n\t" : "=r" (J) : "rm" (X));\
2308 #define compute_bit2idx(X, I) I = ffs(X)-1
2310 #else /* USE_BUILTIN_FFS */
2311 #define compute_bit2idx(X, I)\
2313 unsigned int Y = X - 1;\
2314 unsigned int K = Y >> (16-4) & 16;\
2315 unsigned int N = K; Y >>= K;\
2316 N += K = Y >> (8-3) & 8; Y >>= K;\
2317 N += K = Y >> (4-2) & 4; Y >>= K;\
2318 N += K = Y >> (2-1) & 2; Y >>= K;\
2319 N += K = Y >> (1-0) & 1; Y >>= K;\
2320 I = (bindex_t)(N + Y);\
2322 #endif /* USE_BUILTIN_FFS */
2325 /* isolate the least set bit of a bitmap */
2326 #define least_bit(x) ((x) & -(x))
2328 /* mask with all bits to left of least bit of x on */
2329 #define left_bits(x) ((x<<1) | -(x<<1))
2331 /* mask with all bits to left of or equal to least bit of x on */
2332 #define same_or_left_bits(x) ((x) | -(x))
2335 /* ----------------------- Runtime Check Support ------------------------- */
2338 For security, the main invariant is that malloc/free/etc never
2339 writes to a static address other than malloc_state, unless static
2340 malloc_state itself has been corrupted, which cannot occur via
2341 malloc (because of these checks). In essence this means that we
2342 believe all pointers, sizes, maps etc held in malloc_state, but
2343 check all of those linked or offsetted from other embedded data
2344 structures. These checks are interspersed with main code in a way
2345 that tends to minimize their run-time cost.
2347 When FOOTERS is defined, in addition to range checking, we also
2348 verify footer fields of inuse chunks, which can be used guarantee
2349 that the mstate controlling malloc/free is intact. This is a
2350 streamlined version of the approach described by William Robertson
2351 et al in "Run-time Detection of Heap-based Overflows" LISA'03
2352 http://www.usenix.org/events/lisa03/tech/robertson.html The footer
2353 of an inuse chunk holds the xor of its mstate and a random seed,
2354 that is checked upon calls to free() and realloc(). This is
2355 (probablistically) unguessable from outside the program, but can be
2356 computed by any code successfully malloc'ing any chunk, so does not
2357 itself provide protection against code that has already broken
2358 security through some other means. Unlike Robertson et al, we
2359 always dynamically check addresses of all offset chunks (previous,
2360 next, etc). This turns out to be cheaper than relying on hashes.
2364 /* Check if address a is at least as high as any from MORECORE or MMAP */
2365 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
2366 /* Check if address of next chunk n is higher than base chunk p */
2367 #define ok_next(p, n) ((char*)(p) < (char*)(n))
2368 /* Check if p has its cinuse bit on */
2369 #define ok_cinuse(p) cinuse(p)
2370 /* Check if p has its pinuse bit on */
2371 #define ok_pinuse(p) pinuse(p)
2373 #else /* !INSECURE */
2374 #define ok_address(M, a) (1)
2375 #define ok_next(b, n) (1)
2376 #define ok_cinuse(p) (1)
2377 #define ok_pinuse(p) (1)
2378 #endif /* !INSECURE */
2380 #if (FOOTERS && !INSECURE)
2381 /* Check if (alleged) mstate m has expected magic field */
2382 #define ok_magic(M) ((M)->magic == mparams.magic)
2383 #else /* (FOOTERS && !INSECURE) */
2384 #define ok_magic(M) (1)
2385 #endif /* (FOOTERS && !INSECURE) */
2388 /* In gcc, use __builtin_expect to minimize impact of checks */
2390 #if defined(__GNUC__) && __GNUC__ >= 3
2391 #define RTCHECK(e) __builtin_expect(e, 1)
2393 #define RTCHECK(e) (e)
2395 #else /* !INSECURE */
2396 #define RTCHECK(e) (1)
2397 #endif /* !INSECURE */
2399 /* macros to set up inuse chunks with or without footers */
2403 #define mark_inuse_foot(M,p,s)
2405 /* Set cinuse bit and pinuse bit of next chunk */
2406 #define set_inuse(M,p,s)\
2407 ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2408 ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2410 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
2411 #define set_inuse_and_pinuse(M,p,s)\
2412 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2413 ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2415 /* Set size, cinuse and pinuse bit of this chunk */
2416 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2417 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
2421 /* Set foot of inuse chunk to be xor of mstate and seed */
2422 #define mark_inuse_foot(M,p,s)\
2423 (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
2425 #define get_mstate_for(p)\
2426 ((mstate)(((mchunkptr)((char*)(p) +\
2427 (chunksize(p))))->prev_foot ^ mparams.magic))
2429 #define set_inuse(M,p,s)\
2430 ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2431 (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
2432 mark_inuse_foot(M,p,s))
2434 #define set_inuse_and_pinuse(M,p,s)\
2435 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2436 (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
2437 mark_inuse_foot(M,p,s))
2439 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2440 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2441 mark_inuse_foot(M, p, s))
2443 #endif /* !FOOTERS */
2445 /* ---------------------------- setting mparams -------------------------- */
2447 /* Initialize mparams */
2448 static int init_mparams(void) {
2449 if (mparams
.page_size
== 0) {
2452 mparams
.mmap_threshold
= DEFAULT_MMAP_THRESHOLD
;
2453 mparams
.trim_threshold
= DEFAULT_TRIM_THRESHOLD
;
2454 #if MORECORE_CONTIGUOUS
2455 mparams
.default_mflags
= USE_LOCK_BIT
|USE_MMAP_BIT
;
2456 #else /* MORECORE_CONTIGUOUS */
2457 mparams
.default_mflags
= USE_LOCK_BIT
|USE_MMAP_BIT
|USE_NONCONTIGUOUS_BIT
;
2458 #endif /* MORECORE_CONTIGUOUS */
2460 #if (FOOTERS && !INSECURE)
2464 unsigned char buf
[sizeof(size_t)];
2465 /* Try to use /dev/urandom, else fall back on using time */
2466 if ((fd
= open("/dev/urandom", O_RDONLY
)) >= 0 &&
2467 read(fd
, buf
, sizeof(buf
)) == sizeof(buf
)) {
2468 s
= *((size_t *) buf
);
2472 #endif /* USE_DEV_RANDOM */
2473 s
= (size_t)(time(0) ^ (size_t)0x55555555U
);
2475 s
|= (size_t)8U; /* ensure nonzero */
2476 s
&= ~(size_t)7U; /* improve chances of fault for bad values */
2479 #else /* (FOOTERS && !INSECURE) */
2480 s
= (size_t)0x58585858U
;
2481 #endif /* (FOOTERS && !INSECURE) */
2482 ACQUIRE_MAGIC_INIT_LOCK();
2483 if (mparams
.magic
== 0) {
2485 /* Set up lock for main malloc area */
2486 INITIAL_LOCK(&gm
->mutex
);
2487 gm
->mflags
= mparams
.default_mflags
;
2489 RELEASE_MAGIC_INIT_LOCK();
2492 mparams
.page_size
= malloc_getpagesize
;
2493 mparams
.granularity
= ((DEFAULT_GRANULARITY
!= 0)?
2494 DEFAULT_GRANULARITY
: mparams
.page_size
);
2497 SYSTEM_INFO system_info
;
2498 GetSystemInfo(&system_info
);
2499 mparams
.page_size
= system_info
.dwPageSize
;
2500 mparams
.granularity
= system_info
.dwAllocationGranularity
;
2504 /* Sanity-check configuration:
2505 size_t must be unsigned and as wide as pointer type.
2506 ints must be at least 4 bytes.
2507 alignment must be at least 8.
2508 Alignment, min chunk size, and page size must all be powers of 2.
2510 if ((sizeof(size_t) != sizeof(char*)) ||
2511 (MAX_SIZE_T
< MIN_CHUNK_SIZE
) ||
2512 (sizeof(int) < 4) ||
2513 (MALLOC_ALIGNMENT
< (size_t)8U) ||
2514 ((MALLOC_ALIGNMENT
& (MALLOC_ALIGNMENT
-SIZE_T_ONE
)) != 0) ||
2515 ((MCHUNK_SIZE
& (MCHUNK_SIZE
-SIZE_T_ONE
)) != 0) ||
2516 ((mparams
.granularity
& (mparams
.granularity
-SIZE_T_ONE
)) != 0) ||
2517 ((mparams
.page_size
& (mparams
.page_size
-SIZE_T_ONE
)) != 0))
2524 /* support for mallopt */
2525 static int change_mparam(int param_number
, int value
) {
2526 size_t val
= (size_t)value
;
2528 switch(param_number
) {
2529 case M_TRIM_THRESHOLD
:
2530 mparams
.trim_threshold
= val
;
2533 if (val
>= mparams
.page_size
&& ((val
& (val
-1)) == 0)) {
2534 mparams
.granularity
= val
;
2539 case M_MMAP_THRESHOLD
:
2540 mparams
.mmap_threshold
= val
;
2549 /* ------------------------- Debugging Support --------------------------- */
2551 /* Check properties of any chunk, whether free, inuse, mmapped etc */
2552 static void do_check_any_chunk(mstate m
, mchunkptr p
) {
2553 assert((is_aligned(chunk2mem(p
))) || (p
->head
== FENCEPOST_HEAD
));
2554 assert(ok_address(m
, p
));
2557 /* Check properties of top chunk */
2558 static void do_check_top_chunk(mstate m
, mchunkptr p
) {
2559 msegmentptr sp
= segment_holding(m
, (char*)p
);
2560 size_t sz
= chunksize(p
);
2562 assert((is_aligned(chunk2mem(p
))) || (p
->head
== FENCEPOST_HEAD
));
2563 assert(ok_address(m
, p
));
2564 assert(sz
== m
->topsize
);
2566 assert(sz
== ((sp
->base
+ sp
->size
) - (char*)p
) - TOP_FOOT_SIZE
);
2568 assert(!next_pinuse(p
));
2571 /* Check properties of (inuse) mmapped chunks */
2572 static void do_check_mmapped_chunk(mstate m
, mchunkptr p
) {
2573 size_t sz
= chunksize(p
);
2574 size_t len
= (sz
+ (p
->prev_foot
& ~IS_MMAPPED_BIT
) + MMAP_FOOT_PAD
);
2575 assert(is_mmapped(p
));
2576 assert(use_mmap(m
));
2577 assert((is_aligned(chunk2mem(p
))) || (p
->head
== FENCEPOST_HEAD
));
2578 assert(ok_address(m
, p
));
2579 assert(!is_small(sz
));
2580 assert((len
& (mparams
.page_size
-SIZE_T_ONE
)) == 0);
2581 assert(chunk_plus_offset(p
, sz
)->head
== FENCEPOST_HEAD
);
2582 assert(chunk_plus_offset(p
, sz
+SIZE_T_SIZE
)->head
== 0);
2585 /* Check properties of inuse chunks */
2586 static void do_check_inuse_chunk(mstate m
, mchunkptr p
) {
2587 do_check_any_chunk(m
, p
);
2589 assert(next_pinuse(p
));
2590 /* If not pinuse and not mmapped, previous chunk has OK offset */
2591 assert(is_mmapped(p
) || pinuse(p
) || next_chunk(prev_chunk(p
)) == p
);
2593 do_check_mmapped_chunk(m
, p
);
2596 /* Check properties of free chunks */
2597 static void do_check_free_chunk(mstate m
, mchunkptr p
) {
2598 size_t sz
= p
->head
& ~(PINUSE_BIT
|CINUSE_BIT
);
2599 mchunkptr next
= chunk_plus_offset(p
, sz
);
2600 do_check_any_chunk(m
, p
);
2602 assert(!next_pinuse(p
));
2603 assert (!is_mmapped(p
));
2604 if (p
!= m
->dv
&& p
!= m
->top
) {
2605 if (sz
>= MIN_CHUNK_SIZE
) {
2606 assert((sz
& CHUNK_ALIGN_MASK
) == 0);
2607 assert(is_aligned(chunk2mem(p
)));
2608 assert(next
->prev_foot
== sz
);
2610 assert (next
== m
->top
|| cinuse(next
));
2611 assert(p
->fd
->bk
== p
);
2612 assert(p
->bk
->fd
== p
);
2614 else /* markers are always of size SIZE_T_SIZE */
2615 assert(sz
== SIZE_T_SIZE
);
2619 /* Check properties of malloced chunks at the point they are malloced */
2620 static void do_check_malloced_chunk(mstate m
, void* mem
, size_t s
) {
2622 mchunkptr p
= mem2chunk(mem
);
2623 size_t sz
= p
->head
& ~(PINUSE_BIT
|CINUSE_BIT
);
2624 do_check_inuse_chunk(m
, p
);
2625 assert((sz
& CHUNK_ALIGN_MASK
) == 0);
2626 assert(sz
>= MIN_CHUNK_SIZE
);
2628 /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
2629 assert(is_mmapped(p
) || sz
< (s
+ MIN_CHUNK_SIZE
));
2633 /* Check a tree and its subtrees. */
2634 static void do_check_tree(mstate m
, tchunkptr t
) {
2637 bindex_t tindex
= t
->index
;
2638 size_t tsize
= chunksize(t
);
2640 compute_tree_index(tsize
, idx
);
2641 assert(tindex
== idx
);
2642 assert(tsize
>= MIN_LARGE_SIZE
);
2643 assert(tsize
>= minsize_for_tree_index(idx
));
2644 assert((idx
== NTREEBINS
-1) || (tsize
< minsize_for_tree_index((idx
+1))));
2646 do { /* traverse through chain of same-sized nodes */
2647 do_check_any_chunk(m
, ((mchunkptr
)u
));
2648 assert(u
->index
== tindex
);
2649 assert(chunksize(u
) == tsize
);
2651 assert(!next_pinuse(u
));
2652 assert(u
->fd
->bk
== u
);
2653 assert(u
->bk
->fd
== u
);
2654 if (u
->parent
== 0) {
2655 assert(u
->child
[0] == 0);
2656 assert(u
->child
[1] == 0);
2659 assert(head
== 0); /* only one node on chain has parent */
2661 assert(u
->parent
!= u
);
2662 assert (u
->parent
->child
[0] == u
||
2663 u
->parent
->child
[1] == u
||
2664 *((tbinptr
*)(u
->parent
)) == u
);
2665 if (u
->child
[0] != 0) {
2666 assert(u
->child
[0]->parent
== u
);
2667 assert(u
->child
[0] != u
);
2668 do_check_tree(m
, u
->child
[0]);
2670 if (u
->child
[1] != 0) {
2671 assert(u
->child
[1]->parent
== u
);
2672 assert(u
->child
[1] != u
);
2673 do_check_tree(m
, u
->child
[1]);
2675 if (u
->child
[0] != 0 && u
->child
[1] != 0) {
2676 assert(chunksize(u
->child
[0]) < chunksize(u
->child
[1]));
2684 /* Check all the chunks in a treebin. */
2685 static void do_check_treebin(mstate m
, bindex_t i
) {
2686 tbinptr
* tb
= treebin_at(m
, i
);
2688 int empty
= (m
->treemap
& (1U << i
)) == 0;
2692 do_check_tree(m
, t
);
2695 /* Check all the chunks in a smallbin. */
2696 static void do_check_smallbin(mstate m
, bindex_t i
) {
2697 sbinptr b
= smallbin_at(m
, i
);
2698 mchunkptr p
= b
->bk
;
2699 unsigned int empty
= (m
->smallmap
& (1U << i
)) == 0;
2703 for (; p
!= b
; p
= p
->bk
) {
2704 size_t size
= chunksize(p
);
2706 /* each chunk claims to be free */
2707 do_check_free_chunk(m
, p
);
2708 /* chunk belongs in bin */
2709 assert(small_index(size
) == i
);
2710 assert(p
->bk
== b
|| chunksize(p
->bk
) == chunksize(p
));
2711 /* chunk is followed by an inuse chunk */
2713 if (q
->head
!= FENCEPOST_HEAD
)
2714 do_check_inuse_chunk(m
, q
);
2719 /* Find x in a bin. Used in other check functions. */
2720 static int bin_find(mstate m
, mchunkptr x
) {
2721 size_t size
= chunksize(x
);
2722 if (is_small(size
)) {
2723 bindex_t sidx
= small_index(size
);
2724 sbinptr b
= smallbin_at(m
, sidx
);
2725 if (smallmap_is_marked(m
, sidx
)) {
2730 } while ((p
= p
->fd
) != b
);
2735 compute_tree_index(size
, tidx
);
2736 if (treemap_is_marked(m
, tidx
)) {
2737 tchunkptr t
= *treebin_at(m
, tidx
);
2738 size_t sizebits
= size
<< leftshift_for_tree_index(tidx
);
2739 while (t
!= 0 && chunksize(t
) != size
) {
2740 t
= t
->child
[(sizebits
>> (SIZE_T_BITSIZE
-SIZE_T_ONE
)) & 1];
2746 if (u
== (tchunkptr
)x
)
2748 } while ((u
= u
->fd
) != t
);
2755 /* Traverse each chunk and check it; return total */
2756 static size_t traverse_and_check(mstate m
) {
2758 if (is_initialized(m
)) {
2759 msegmentptr s
= &m
->seg
;
2760 sum
+= m
->topsize
+ TOP_FOOT_SIZE
;
2762 mchunkptr q
= align_as_chunk(s
->base
);
2763 mchunkptr lastq
= 0;
2765 while (segment_holds(s
, q
) &&
2766 q
!= m
->top
&& q
->head
!= FENCEPOST_HEAD
) {
2767 sum
+= chunksize(q
);
2769 assert(!bin_find(m
, q
));
2770 do_check_inuse_chunk(m
, q
);
2773 assert(q
== m
->dv
|| bin_find(m
, q
));
2774 assert(lastq
== 0 || cinuse(lastq
)); /* Not 2 consecutive free */
2775 do_check_free_chunk(m
, q
);
2786 /* Check all properties of malloc_state. */
2787 static void do_check_malloc_state(mstate m
) {
2791 for (i
= 0; i
< NSMALLBINS
; ++i
)
2792 do_check_smallbin(m
, i
);
2793 for (i
= 0; i
< NTREEBINS
; ++i
)
2794 do_check_treebin(m
, i
);
2796 if (m
->dvsize
!= 0) { /* check dv chunk */
2797 do_check_any_chunk(m
, m
->dv
);
2798 assert(m
->dvsize
== chunksize(m
->dv
));
2799 assert(m
->dvsize
>= MIN_CHUNK_SIZE
);
2800 assert(bin_find(m
, m
->dv
) == 0);
2803 if (m
->top
!= 0) { /* check top chunk */
2804 do_check_top_chunk(m
, m
->top
);
2805 assert(m
->topsize
== chunksize(m
->top
));
2806 assert(m
->topsize
> 0);
2807 assert(bin_find(m
, m
->top
) == 0);
2810 total
= traverse_and_check(m
);
2811 assert(total
<= m
->footprint
);
2812 assert(m
->footprint
<= m
->max_footprint
);
2816 /* ----------------------------- statistics ------------------------------ */
2819 static struct mallinfo
internal_mallinfo(mstate m
) {
2820 struct mallinfo nm
= { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
2821 if (!PREACTION(m
)) {
2822 check_malloc_state(m
);
2823 if (is_initialized(m
)) {
2824 size_t nfree
= SIZE_T_ONE
; /* top always free */
2825 size_t mfree
= m
->topsize
+ TOP_FOOT_SIZE
;
2827 msegmentptr s
= &m
->seg
;
2829 mchunkptr q
= align_as_chunk(s
->base
);
2830 while (segment_holds(s
, q
) &&
2831 q
!= m
->top
&& q
->head
!= FENCEPOST_HEAD
) {
2832 size_t sz
= chunksize(q
);
2845 nm
.hblkhd
= m
->footprint
- sum
;
2846 nm
.usmblks
= m
->max_footprint
;
2847 nm
.uordblks
= m
->footprint
- mfree
;
2848 nm
.fordblks
= mfree
;
2849 nm
.keepcost
= m
->topsize
;
2856 #endif /* !NO_MALLINFO */
2859 static void internal_malloc_stats(mstate m
) {
2860 if (!PREACTION(m
)) {
2864 check_malloc_state(m
);
2865 if (is_initialized(m
)) {
2866 msegmentptr s
= &m
->seg
;
2867 maxfp
= m
->max_footprint
;
2869 used
= fp
- (m
->topsize
+ TOP_FOOT_SIZE
);
2872 mchunkptr q
= align_as_chunk(s
->base
);
2873 while (segment_holds(s
, q
) &&
2874 q
!= m
->top
&& q
->head
!= FENCEPOST_HEAD
) {
2876 used
-= chunksize(q
);
2883 fprintf(stderr
, "max system bytes = %10lu\n", (unsigned long)(maxfp
));
2884 fprintf(stderr
, "system bytes = %10lu\n", (unsigned long)(fp
));
2885 fprintf(stderr
, "in use bytes = %10lu\n", (unsigned long)(used
));
2892 /* ----------------------- Operations on smallbins ----------------------- */
2895 Various forms of linking and unlinking are defined as macros. Even
2896 the ones for trees, which are very long but have very short typical
2897 paths. This is ugly but reduces reliance on inlining support of
2901 /* Link a free chunk into a smallbin */
2902 #define insert_small_chunk(M, P, S) {\
2903 bindex_t I = small_index(S);\
2904 mchunkptr B = smallbin_at(M, I);\
2906 assert(S >= MIN_CHUNK_SIZE);\
2907 if (!smallmap_is_marked(M, I))\
2908 mark_smallmap(M, I);\
2909 else if (RTCHECK(ok_address(M, B->fd)))\
2912 CORRUPTION_ERROR_ACTION(M);\
2920 /* Unlink a chunk from a smallbin */
2921 #define unlink_small_chunk(M, P, S) {\
2922 mchunkptr F = P->fd;\
2923 mchunkptr B = P->bk;\
2924 bindex_t I = small_index(S);\
2927 assert(chunksize(P) == small_index2size(I));\
2929 clear_smallmap(M, I);\
2930 else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
2931 (B == smallbin_at(M,I) || ok_address(M, B)))) {\
2936 CORRUPTION_ERROR_ACTION(M);\
2940 /* Unlink the first chunk from a smallbin */
2941 #define unlink_first_small_chunk(M, B, P, I) {\
2942 mchunkptr F = P->fd;\
2945 assert(chunksize(P) == small_index2size(I));\
2947 clear_smallmap(M, I);\
2948 else if (RTCHECK(ok_address(M, F))) {\
2953 CORRUPTION_ERROR_ACTION(M);\
2957 /* Replace dv node, binning the old one */
2958 /* Used only when dvsize known to be small */
2959 #define replace_dv(M, P, S) {\
2960 size_t DVS = M->dvsize;\
2962 mchunkptr DV = M->dv;\
2963 assert(is_small(DVS));\
2964 insert_small_chunk(M, DV, DVS);\
2970 /* ------------------------- Operations on trees ------------------------- */
2972 /* Insert chunk into tree */
2973 #define insert_large_chunk(M, X, S) {\
2976 compute_tree_index(S, I);\
2977 H = treebin_at(M, I);\
2979 X->child[0] = X->child[1] = 0;\
2980 if (!treemap_is_marked(M, I)) {\
2981 mark_treemap(M, I);\
2983 X->parent = (tchunkptr)H;\
2988 size_t K = S << leftshift_for_tree_index(I);\
2990 if (chunksize(T) != S) {\
2991 tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
2995 else if (RTCHECK(ok_address(M, C))) {\
3002 CORRUPTION_ERROR_ACTION(M);\
3007 tchunkptr F = T->fd;\
3008 if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
3016 CORRUPTION_ERROR_ACTION(M);\
3027 1. If x is a chained node, unlink it from its same-sized fd/bk links
3028 and choose its bk node as its replacement.
3029 2. If x was the last node of its size, but not a leaf node, it must
3030 be replaced with a leaf node (not merely one with an open left or
3031 right), to make sure that lefts and rights of descendents
3032 correspond properly to bit masks. We use the rightmost descendent
3033 of x. We could use any other leaf, but this is easy to locate and
3034 tends to counteract removal of leftmosts elsewhere, and so keeps
3035 paths shorter than minimally guaranteed. This doesn't loop much
3036 because on average a node in a tree is near the bottom.
3037 3. If x is the base of a chain (i.e., has parent links) relink
3038 x's parent and children to x's replacement (or null if none).
3041 #define unlink_large_chunk(M, X) {\
3042 tchunkptr XP = X->parent;\
3045 tchunkptr F = X->fd;\
3047 if (RTCHECK(ok_address(M, F))) {\
3052 CORRUPTION_ERROR_ACTION(M);\
3057 if (((R = *(RP = &(X->child[1]))) != 0) ||\
3058 ((R = *(RP = &(X->child[0]))) != 0)) {\
3060 while ((*(CP = &(R->child[1])) != 0) ||\
3061 (*(CP = &(R->child[0])) != 0)) {\
3064 if (RTCHECK(ok_address(M, RP)))\
3067 CORRUPTION_ERROR_ACTION(M);\
3072 tbinptr* H = treebin_at(M, X->index);\
3074 if ((*H = R) == 0) \
3075 clear_treemap(M, X->index);\
3077 else if (RTCHECK(ok_address(M, XP))) {\
3078 if (XP->child[0] == X) \
3084 CORRUPTION_ERROR_ACTION(M);\
3086 if (RTCHECK(ok_address(M, R))) {\
3089 if ((C0 = X->child[0]) != 0) {\
3090 if (RTCHECK(ok_address(M, C0))) {\
3095 CORRUPTION_ERROR_ACTION(M);\
3097 if ((C1 = X->child[1]) != 0) {\
3098 if (RTCHECK(ok_address(M, C1))) {\
3103 CORRUPTION_ERROR_ACTION(M);\
3107 CORRUPTION_ERROR_ACTION(M);\
3112 /* Relays to large vs small bin operations */
3114 #define insert_chunk(M, P, S)\
3115 if (is_small(S)) insert_small_chunk(M, P, S)\
3116 else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
3118 #define unlink_chunk(M, P, S)\
3119 if (is_small(S)) unlink_small_chunk(M, P, S)\
3120 else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
3123 /* Relays to internal calls to malloc/free from realloc, memalign etc */
3126 #define internal_malloc(m, b) mspace_malloc(m, b)
3127 #define internal_free(m, mem) mspace_free(m,mem);
3128 #else /* ONLY_MSPACES */
3130 #define internal_malloc(m, b)\
3131 (m == gm)? dlmalloc(b) : mspace_malloc(m, b)
3132 #define internal_free(m, mem)\
3133 if (m == gm) dlfree(mem); else mspace_free(m,mem);
3135 #define internal_malloc(m, b) dlmalloc(b)
3136 #define internal_free(m, mem) dlfree(mem)
3137 #endif /* MSPACES */
3138 #endif /* ONLY_MSPACES */
3140 /* ----------------------- Direct-mmapping chunks ----------------------- */
3143 Directly mmapped chunks are set up with an offset to the start of
3144 the mmapped region stored in the prev_foot field of the chunk. This
3145 allows reconstruction of the required argument to MUNMAP when freed,
3146 and also allows adjustment of the returned chunk to meet alignment
3147 requirements (especially in memalign). There is also enough space
3148 allocated to hold a fake next chunk of size SIZE_T_SIZE to maintain
3149 the PINUSE bit so frees can be checked.
3152 /* Malloc using mmap */
3153 static void* mmap_alloc(mstate m
, size_t nb
) {
3154 size_t mmsize
= granularity_align(nb
+ SIX_SIZE_T_SIZES
+ CHUNK_ALIGN_MASK
);
3155 if (mmsize
> nb
) { /* Check for wrap around 0 */
3156 char* mm
= (char*)(DIRECT_MMAP(mmsize
));
3158 size_t offset
= align_offset(chunk2mem(mm
));
3159 size_t psize
= mmsize
- offset
- MMAP_FOOT_PAD
;
3160 mchunkptr p
= (mchunkptr
)(mm
+ offset
);
3161 p
->prev_foot
= offset
| IS_MMAPPED_BIT
;
3162 (p
)->head
= (psize
|CINUSE_BIT
);
3163 mark_inuse_foot(m
, p
, psize
);
3164 chunk_plus_offset(p
, psize
)->head
= FENCEPOST_HEAD
;
3165 chunk_plus_offset(p
, psize
+SIZE_T_SIZE
)->head
= 0;
3167 if (mm
< m
->least_addr
)
3169 if ((m
->footprint
+= mmsize
) > m
->max_footprint
)
3170 m
->max_footprint
= m
->footprint
;
3171 assert(is_aligned(chunk2mem(p
)));
3172 check_mmapped_chunk(m
, p
);
3173 return chunk2mem(p
);
3181 /* Realloc using mmap */
3182 static mchunkptr
mmap_resize(mstate m
, mchunkptr oldp
, size_t nb
) {
3183 size_t oldsize
= chunksize(oldp
);
3184 if (is_small(nb
)) /* Can't shrink mmap regions below small size */
3186 /* Keep old chunk if big enough but not too big */
3187 if (oldsize
>= nb
+ SIZE_T_SIZE
&&
3188 (oldsize
- nb
) <= (mparams
.granularity
<< 1))
3191 size_t offset
= oldp
->prev_foot
& ~IS_MMAPPED_BIT
;
3192 size_t oldmmsize
= oldsize
+ offset
+ MMAP_FOOT_PAD
;
3193 size_t newmmsize
= granularity_align(nb
+ SIX_SIZE_T_SIZES
+
3195 char* cp
= (char*)CALL_MREMAP((char*)oldp
- offset
,
3196 oldmmsize
, newmmsize
, 1);
3198 mchunkptr newp
= (mchunkptr
)(cp
+ offset
);
3199 size_t psize
= newmmsize
- offset
- MMAP_FOOT_PAD
;
3200 newp
->head
= (psize
|CINUSE_BIT
);
3201 mark_inuse_foot(m
, newp
, psize
);
3202 chunk_plus_offset(newp
, psize
)->head
= FENCEPOST_HEAD
;
3203 chunk_plus_offset(newp
, psize
+SIZE_T_SIZE
)->head
= 0;
3205 if (cp
< m
->least_addr
)
3207 if ((m
->footprint
+= newmmsize
- oldmmsize
) > m
->max_footprint
)
3208 m
->max_footprint
= m
->footprint
;
3209 check_mmapped_chunk(m
, newp
);
3218 /* -------------------------- mspace management -------------------------- */
3220 /* Initialize top chunk and its size */
3221 static void init_top(mstate m
, mchunkptr p
, size_t psize
) {
3222 /* Ensure alignment */
3223 size_t offset
= align_offset(chunk2mem(p
));
3224 p
= (mchunkptr
)((char*)p
+ offset
);
3229 p
->head
= psize
| PINUSE_BIT
;
3230 /* set size of fake trailing chunk holding overhead space only once */
3231 chunk_plus_offset(p
, psize
)->head
= TOP_FOOT_SIZE
;
3232 m
->trim_check
= mparams
.trim_threshold
; /* reset on each update */
3235 /* Initialize bins for a new mstate that is otherwise zeroed out */
3236 static void init_bins(mstate m
) {
3237 /* Establish circular links for smallbins */
3239 for (i
= 0; i
< NSMALLBINS
; ++i
) {
3240 sbinptr bin
= smallbin_at(m
,i
);
3241 bin
->fd
= bin
->bk
= bin
;
3245 #if PROCEED_ON_ERROR
3247 /* default corruption action */
3248 static void reset_on_error(mstate m
) {
3250 ++malloc_corruption_error_count
;
3251 /* Reinitialize fields to forget about all memory */
3252 m
->smallbins
= m
->treebins
= 0;
3253 m
->dvsize
= m
->topsize
= 0;
3258 for (i
= 0; i
< NTREEBINS
; ++i
)
3259 *treebin_at(m
, i
) = 0;
3262 #endif /* PROCEED_ON_ERROR */
3264 /* Allocate chunk and prepend remainder with chunk in successor base. */
3265 static void* prepend_alloc(mstate m
, char* newbase
, char* oldbase
,
3267 mchunkptr p
= align_as_chunk(newbase
);
3268 mchunkptr oldfirst
= align_as_chunk(oldbase
);
3269 size_t psize
= (char*)oldfirst
- (char*)p
;
3270 mchunkptr q
= chunk_plus_offset(p
, nb
);
3271 size_t qsize
= psize
- nb
;
3272 set_size_and_pinuse_of_inuse_chunk(m
, p
, nb
);
3274 assert((char*)oldfirst
> (char*)q
);
3275 assert(pinuse(oldfirst
));
3276 assert(qsize
>= MIN_CHUNK_SIZE
);
3278 /* consolidate remainder with first chunk of old base */
3279 if (oldfirst
== m
->top
) {
3280 size_t tsize
= m
->topsize
+= qsize
;
3282 q
->head
= tsize
| PINUSE_BIT
;
3283 check_top_chunk(m
, q
);
3285 else if (oldfirst
== m
->dv
) {
3286 size_t dsize
= m
->dvsize
+= qsize
;
3288 set_size_and_pinuse_of_free_chunk(q
, dsize
);
3291 if (!cinuse(oldfirst
)) {
3292 size_t nsize
= chunksize(oldfirst
);
3293 unlink_chunk(m
, oldfirst
, nsize
);
3294 oldfirst
= chunk_plus_offset(oldfirst
, nsize
);
3297 set_free_with_pinuse(q
, qsize
, oldfirst
);
3298 insert_chunk(m
, q
, qsize
);
3299 check_free_chunk(m
, q
);
3302 check_malloced_chunk(m
, chunk2mem(p
), nb
);
3303 return chunk2mem(p
);
3307 /* Add a segment to hold a new noncontiguous region */
3308 static void add_segment(mstate m
, char* tbase
, size_t tsize
, flag_t mmapped
) {
3309 /* Determine locations and sizes of segment, fenceposts, old top */
3310 char* old_top
= (char*)m
->top
;
3311 msegmentptr oldsp
= segment_holding(m
, old_top
);
3312 char* old_end
= oldsp
->base
+ oldsp
->size
;
3313 size_t ssize
= pad_request(sizeof(struct malloc_segment
));
3314 char* rawsp
= old_end
- (ssize
+ FOUR_SIZE_T_SIZES
+ CHUNK_ALIGN_MASK
);
3315 size_t offset
= align_offset(chunk2mem(rawsp
));
3316 char* asp
= rawsp
+ offset
;
3317 char* csp
= (asp
< (old_top
+ MIN_CHUNK_SIZE
))? old_top
: asp
;
3318 mchunkptr sp
= (mchunkptr
)csp
;
3319 msegmentptr ss
= (msegmentptr
)(chunk2mem(sp
));
3320 mchunkptr tnext
= chunk_plus_offset(sp
, ssize
);
3321 mchunkptr p
= tnext
;
3324 /* reset top to new space */
3325 init_top(m
, (mchunkptr
)tbase
, tsize
- TOP_FOOT_SIZE
);
3327 /* Set up segment record */
3328 assert(is_aligned(ss
));
3329 set_size_and_pinuse_of_inuse_chunk(m
, sp
, ssize
);
3330 *ss
= m
->seg
; /* Push current record */
3331 m
->seg
.base
= tbase
;
3332 m
->seg
.size
= tsize
;
3333 m
->seg
.sflags
= mmapped
;
3336 /* Insert trailing fenceposts */
3338 mchunkptr nextp
= chunk_plus_offset(p
, SIZE_T_SIZE
);
3339 p
->head
= FENCEPOST_HEAD
;
3341 if ((char*)(&(nextp
->head
)) < old_end
)
3346 assert(nfences
>= 2);
3348 /* Insert the rest of old top into a bin as an ordinary free chunk */
3349 if (csp
!= old_top
) {
3350 mchunkptr q
= (mchunkptr
)old_top
;
3351 size_t psize
= csp
- old_top
;
3352 mchunkptr tn
= chunk_plus_offset(q
, psize
);
3353 set_free_with_pinuse(q
, psize
, tn
);
3354 insert_chunk(m
, q
, psize
);
3357 check_top_chunk(m
, m
->top
);
3360 /* -------------------------- System allocation -------------------------- */
3362 /* Get memory from system using MORECORE or MMAP */
3363 static void* sys_alloc(mstate m
, size_t nb
) {
3364 char* tbase
= CMFAIL
;
3366 flag_t mmap_flag
= 0;
3370 /* Directly map large chunks */
3371 if (use_mmap(m
) && nb
>= mparams
.mmap_threshold
) {
3372 void* mem
= mmap_alloc(m
, nb
);
3378 Try getting memory in any of three ways (in most-preferred to
3379 least-preferred order):
3380 1. A call to MORECORE that can normally contiguously extend memory.
3381 (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
3382 or main space is mmapped or a previous contiguous call failed)
3383 2. A call to MMAP new space (disabled if not HAVE_MMAP).
3384 Note that under the default settings, if MORECORE is unable to
3385 fulfill a request, and HAVE_MMAP is true, then mmap is
3386 used as a noncontiguous system allocator. This is a useful backup
3387 strategy for systems with holes in address spaces -- in this case
3388 sbrk cannot contiguously expand the heap, but mmap may be able to
3390 3. A call to MORECORE that cannot usually contiguously extend memory.
3391 (disabled if not HAVE_MORECORE)
3394 if (MORECORE_CONTIGUOUS
&& !use_noncontiguous(m
)) {
3396 msegmentptr ss
= (m
->top
== 0)? 0 : segment_holding(m
, (char*)m
->top
);
3398 ACQUIRE_MORECORE_LOCK();
3400 if (ss
== 0) { /* First time through or recovery */
3401 char* base
= (char*)CALL_MORECORE(0);
3402 if (base
!= CMFAIL
) {
3403 asize
= granularity_align(nb
+ TOP_FOOT_SIZE
+ SIZE_T_ONE
);
3404 /* Adjust to end on a page boundary */
3405 if (!is_page_aligned(base
))
3406 asize
+= (page_align((size_t)base
) - (size_t)base
);
3407 /* Can't call MORECORE if size is negative when treated as signed */
3408 if (asize
< HALF_MAX_SIZE_T
&&
3409 (br
= (char*)(CALL_MORECORE(asize
))) == base
) {
3416 /* Subtract out existing available top space from MORECORE request. */
3417 asize
= granularity_align(nb
- m
->topsize
+ TOP_FOOT_SIZE
+ SIZE_T_ONE
);
3418 /* Use mem here only if it did continuously extend old space */
3419 if (asize
< HALF_MAX_SIZE_T
&&
3420 (br
= (char*)(CALL_MORECORE(asize
))) == ss
->base
+ss
->size
) {
3426 if (tbase
== CMFAIL
) { /* Cope with partial failure */
3427 if (br
!= CMFAIL
) { /* Try to use/extend the space we did get */
3428 if (asize
< HALF_MAX_SIZE_T
&&
3429 asize
< nb
+ TOP_FOOT_SIZE
+ SIZE_T_ONE
) {
3430 size_t esize
= granularity_align(nb
+ TOP_FOOT_SIZE
+ SIZE_T_ONE
- asize
);
3431 if (esize
< HALF_MAX_SIZE_T
) {
3432 char* end
= (char*)CALL_MORECORE(esize
);
3435 else { /* Can't use; try to release */
3436 CALL_MORECORE(-asize
);
3442 if (br
!= CMFAIL
) { /* Use the space we did get */
3447 disable_contiguous(m
); /* Don't try contiguous path in the future */
3450 RELEASE_MORECORE_LOCK();
3453 if (HAVE_MMAP
&& tbase
== CMFAIL
) { /* Try MMAP */
3454 size_t req
= nb
+ TOP_FOOT_SIZE
+ SIZE_T_ONE
;
3455 size_t rsize
= granularity_align(req
);
3456 if (rsize
> nb
) { /* Fail if wraps around zero */
3457 char* mp
= (char*)(CALL_MMAP(rsize
));
3461 mmap_flag
= IS_MMAPPED_BIT
;
3466 if (HAVE_MORECORE
&& tbase
== CMFAIL
) { /* Try noncontiguous MORECORE */
3467 size_t asize
= granularity_align(nb
+ TOP_FOOT_SIZE
+ SIZE_T_ONE
);
3468 if (asize
< HALF_MAX_SIZE_T
) {
3471 ACQUIRE_MORECORE_LOCK();
3472 br
= (char*)(CALL_MORECORE(asize
));
3473 end
= (char*)(CALL_MORECORE(0));
3474 RELEASE_MORECORE_LOCK();
3475 if (br
!= CMFAIL
&& end
!= CMFAIL
&& br
< end
) {
3476 size_t ssize
= end
- br
;
3477 if (ssize
> nb
+ TOP_FOOT_SIZE
) {
3485 if (tbase
!= CMFAIL
) {
3487 if ((m
->footprint
+= tsize
) > m
->max_footprint
)
3488 m
->max_footprint
= m
->footprint
;
3490 if (!is_initialized(m
)) { /* first-time initialization */
3491 m
->seg
.base
= m
->least_addr
= tbase
;
3492 m
->seg
.size
= tsize
;
3493 m
->seg
.sflags
= mmap_flag
;
3494 m
->magic
= mparams
.magic
;
3497 init_top(m
, (mchunkptr
)tbase
, tsize
- TOP_FOOT_SIZE
);
3499 /* Offset top by embedded malloc_state */
3500 mchunkptr mn
= next_chunk(mem2chunk(m
));
3501 init_top(m
, mn
, (size_t)((tbase
+ tsize
) - (char*)mn
) -TOP_FOOT_SIZE
);
3506 /* Try to merge with an existing segment */
3507 msegmentptr sp
= &m
->seg
;
3508 while (sp
!= 0 && tbase
!= sp
->base
+ sp
->size
)
3511 !is_extern_segment(sp
) &&
3512 (sp
->sflags
& IS_MMAPPED_BIT
) == mmap_flag
&&
3513 segment_holds(sp
, m
->top
)) { /* append */
3515 init_top(m
, m
->top
, m
->topsize
+ tsize
);
3518 if (tbase
< m
->least_addr
)
3519 m
->least_addr
= tbase
;
3521 while (sp
!= 0 && sp
->base
!= tbase
+ tsize
)
3524 !is_extern_segment(sp
) &&
3525 (sp
->sflags
& IS_MMAPPED_BIT
) == mmap_flag
) {
3526 char* oldbase
= sp
->base
;
3529 return prepend_alloc(m
, tbase
, oldbase
, nb
);
3532 add_segment(m
, tbase
, tsize
, mmap_flag
);
3536 if (nb
< m
->topsize
) { /* Allocate from new or extended top space */
3537 size_t rsize
= m
->topsize
-= nb
;
3538 mchunkptr p
= m
->top
;
3539 mchunkptr r
= m
->top
= chunk_plus_offset(p
, nb
);
3540 r
->head
= rsize
| PINUSE_BIT
;
3541 set_size_and_pinuse_of_inuse_chunk(m
, p
, nb
);
3542 check_top_chunk(m
, m
->top
);
3543 check_malloced_chunk(m
, chunk2mem(p
), nb
);
3544 return chunk2mem(p
);
3548 MALLOC_FAILURE_ACTION
;
3552 /* ----------------------- system deallocation -------------------------- */
3554 /* Unmap and unlink any mmapped segments that don't contain used chunks */
3555 static size_t release_unused_segments(mstate m
) {
3556 size_t released
= 0;
3557 msegmentptr pred
= &m
->seg
;
3558 msegmentptr sp
= pred
->next
;
3560 char* base
= sp
->base
;
3561 size_t size
= sp
->size
;
3562 msegmentptr next
= sp
->next
;
3563 if (is_mmapped_segment(sp
) && !is_extern_segment(sp
)) {
3564 mchunkptr p
= align_as_chunk(base
);
3565 size_t psize
= chunksize(p
);
3566 /* Can unmap if first chunk holds entire segment and not pinned */
3567 if (!cinuse(p
) && (char*)p
+ psize
>= base
+ size
- TOP_FOOT_SIZE
) {
3568 tchunkptr tp
= (tchunkptr
)p
;
3569 assert(segment_holds(sp
, (char*)sp
));
3575 unlink_large_chunk(m
, tp
);
3577 if (CALL_MUNMAP(base
, size
) == 0) {
3579 m
->footprint
-= size
;
3580 /* unlink obsoleted record */
3584 else { /* back out if cannot unmap */
3585 insert_large_chunk(m
, tp
, psize
);
3595 static int sys_trim(mstate m
, size_t pad
) {
3596 size_t released
= 0;
3597 if (pad
< MAX_REQUEST
&& is_initialized(m
)) {
3598 pad
+= TOP_FOOT_SIZE
; /* ensure enough room for segment overhead */
3600 if (m
->topsize
> pad
) {
3601 /* Shrink top space in granularity-size units, keeping at least one */
3602 size_t unit
= mparams
.granularity
;
3603 size_t extra
= ((m
->topsize
- pad
+ (unit
- SIZE_T_ONE
)) / unit
-
3605 msegmentptr sp
= segment_holding(m
, (char*)m
->top
);
3607 if (!is_extern_segment(sp
)) {
3608 if (is_mmapped_segment(sp
)) {
3610 sp
->size
>= extra
&&
3611 !has_segment_link(m
, sp
)) { /* can't shrink if pinned */
3612 size_t newsize
= sp
->size
- extra
;
3613 /* Prefer mremap, fall back to munmap */
3614 if ((CALL_MREMAP(sp
->base
, sp
->size
, newsize
, 0) != MFAIL
) ||
3615 (CALL_MUNMAP(sp
->base
+ newsize
, extra
) == 0)) {
3620 else if (HAVE_MORECORE
) {
3621 if (extra
>= HALF_MAX_SIZE_T
) /* Avoid wrapping negative */
3622 extra
= (HALF_MAX_SIZE_T
) + SIZE_T_ONE
- unit
;
3623 ACQUIRE_MORECORE_LOCK();
3625 /* Make sure end of memory is where we last set it. */
3626 char* old_br
= (char*)(CALL_MORECORE(0));
3627 if (old_br
== sp
->base
+ sp
->size
) {
3628 char* rel_br
= (char*)(CALL_MORECORE(-extra
));
3629 char* new_br
= (char*)(CALL_MORECORE(0));
3630 if (rel_br
!= CMFAIL
&& new_br
< old_br
)
3631 released
= old_br
- new_br
;
3634 RELEASE_MORECORE_LOCK();
3638 if (released
!= 0) {
3639 sp
->size
-= released
;
3640 m
->footprint
-= released
;
3641 init_top(m
, m
->top
, m
->topsize
- released
);
3642 check_top_chunk(m
, m
->top
);
3646 /* Unmap any unused mmapped segments */
3648 released
+= release_unused_segments(m
);
3650 /* On failure, disable autotrim to avoid repeated failed future calls */
3652 m
->trim_check
= MAX_SIZE_T
;
3655 return (released
!= 0)? 1 : 0;
3658 /* ---------------------------- malloc support --------------------------- */
3660 /* allocate a large request from the best fitting chunk in a treebin */
3661 static void* tmalloc_large(mstate m
, size_t nb
) {
3663 size_t rsize
= -nb
; /* Unsigned negation */
3666 compute_tree_index(nb
, idx
);
3668 if ((t
= *treebin_at(m
, idx
)) != 0) {
3669 /* Traverse tree for this bin looking for node with size == nb */
3670 size_t sizebits
= nb
<< leftshift_for_tree_index(idx
);
3671 tchunkptr rst
= 0; /* The deepest untaken right subtree */
3674 size_t trem
= chunksize(t
) - nb
;
3677 if ((rsize
= trem
) == 0)
3681 t
= t
->child
[(sizebits
>> (SIZE_T_BITSIZE
-SIZE_T_ONE
)) & 1];
3682 if (rt
!= 0 && rt
!= t
)
3685 t
= rst
; /* set t to least subtree holding sizes > nb */
3692 if (t
== 0 && v
== 0) { /* set t to root of next non-empty treebin */
3693 binmap_t leftbits
= left_bits(idx2bit(idx
)) & m
->treemap
;
3694 if (leftbits
!= 0) {
3696 binmap_t leastbit
= least_bit(leftbits
);
3697 compute_bit2idx(leastbit
, i
);
3698 t
= *treebin_at(m
, i
);
3702 while (t
!= 0) { /* find smallest of tree or subtree */
3703 size_t trem
= chunksize(t
) - nb
;
3708 t
= leftmost_child(t
);
3711 /* If dv is a better fit, return 0 so malloc will use it */
3712 if (v
!= 0 && rsize
< (size_t)(m
->dvsize
- nb
)) {
3713 if (RTCHECK(ok_address(m
, v
))) { /* split */
3714 mchunkptr r
= chunk_plus_offset(v
, nb
);
3715 assert(chunksize(v
) == rsize
+ nb
);
3716 if (RTCHECK(ok_next(v
, r
))) {
3717 unlink_large_chunk(m
, v
);
3718 if (rsize
< MIN_CHUNK_SIZE
)
3719 set_inuse_and_pinuse(m
, v
, (rsize
+ nb
));
3721 set_size_and_pinuse_of_inuse_chunk(m
, v
, nb
);
3722 set_size_and_pinuse_of_free_chunk(r
, rsize
);
3723 insert_chunk(m
, r
, rsize
);
3725 return chunk2mem(v
);
3728 CORRUPTION_ERROR_ACTION(m
);
3733 /* allocate a small request from the best fitting chunk in a treebin */
3734 static void* tmalloc_small(mstate m
, size_t nb
) {
3738 binmap_t leastbit
= least_bit(m
->treemap
);
3739 compute_bit2idx(leastbit
, i
);
3741 v
= t
= *treebin_at(m
, i
);
3742 rsize
= chunksize(t
) - nb
;
3744 while ((t
= leftmost_child(t
)) != 0) {
3745 size_t trem
= chunksize(t
) - nb
;
3752 if (RTCHECK(ok_address(m
, v
))) {
3753 mchunkptr r
= chunk_plus_offset(v
, nb
);
3754 assert(chunksize(v
) == rsize
+ nb
);
3755 if (RTCHECK(ok_next(v
, r
))) {
3756 unlink_large_chunk(m
, v
);
3757 if (rsize
< MIN_CHUNK_SIZE
)
3758 set_inuse_and_pinuse(m
, v
, (rsize
+ nb
));
3760 set_size_and_pinuse_of_inuse_chunk(m
, v
, nb
);
3761 set_size_and_pinuse_of_free_chunk(r
, rsize
);
3762 replace_dv(m
, r
, rsize
);
3764 return chunk2mem(v
);
3768 CORRUPTION_ERROR_ACTION(m
);
3772 /* --------------------------- realloc support --------------------------- */
3776 static void* internal_realloc(mstate m
, void* oldmem
, size_t bytes
) {
3777 if (bytes
>= MAX_REQUEST
) {
3778 MALLOC_FAILURE_ACTION
;
3781 if (!PREACTION(m
)) {
3782 mchunkptr oldp
= mem2chunk(oldmem
);
3783 size_t oldsize
= chunksize(oldp
);
3784 mchunkptr next
= chunk_plus_offset(oldp
, oldsize
);
3788 /* Try to either shrink or extend into top. Else malloc-copy-free */
3790 if (RTCHECK(ok_address(m
, oldp
) && ok_cinuse(oldp
) &&
3791 ok_next(oldp
, next
) && ok_pinuse(next
))) {
3792 size_t nb
= request2size(bytes
);
3793 if (is_mmapped(oldp
))
3794 newp
= mmap_resize(m
, oldp
, nb
);
3795 else if (oldsize
>= nb
) { /* already big enough */
3796 size_t rsize
= oldsize
- nb
;
3798 if (rsize
>= MIN_CHUNK_SIZE
) {
3799 mchunkptr remainder
= chunk_plus_offset(newp
, nb
);
3800 set_inuse(m
, newp
, nb
);
3801 set_inuse(m
, remainder
, rsize
);
3802 extra
= chunk2mem(remainder
);
3805 else if (next
== m
->top
&& oldsize
+ m
->topsize
> nb
) {
3806 /* Expand into top */
3807 size_t newsize
= oldsize
+ m
->topsize
;
3808 size_t newtopsize
= newsize
- nb
;
3809 mchunkptr newtop
= chunk_plus_offset(oldp
, nb
);
3810 set_inuse(m
, oldp
, nb
);
3811 newtop
->head
= newtopsize
|PINUSE_BIT
;
3813 m
->topsize
= newtopsize
;
3818 USAGE_ERROR_ACTION(m
, oldmem
);
3827 internal_free(m
, extra
);
3829 check_inuse_chunk(m
, newp
);
3830 return chunk2mem(newp
);
3833 void* newmem
= internal_malloc(m
, bytes
);
3835 size_t oc
= oldsize
- overhead_for(oldp
);
3836 memcpy(newmem
, oldmem
, (oc
< bytes
)? oc
: bytes
);
3837 internal_free(m
, oldmem
);
3847 /* --------------------------- memalign support -------------------------- */
3849 static void* internal_memalign(mstate m
, size_t alignment
, size_t bytes
) {
3850 if (alignment
<= MALLOC_ALIGNMENT
) /* Can just use malloc */
3851 return internal_malloc(m
, bytes
);
3852 if (alignment
< MIN_CHUNK_SIZE
) /* must be at least a minimum chunk size */
3853 alignment
= MIN_CHUNK_SIZE
;
3854 if ((alignment
& (alignment
-SIZE_T_ONE
)) != 0) {/* Ensure a power of 2 */
3855 size_t a
= MALLOC_ALIGNMENT
<< 1;
3856 while (a
< alignment
) a
<<= 1;
3860 if (bytes
>= MAX_REQUEST
- alignment
) {
3861 if (m
!= 0) { /* Test isn't needed but avoids compiler warning */
3862 MALLOC_FAILURE_ACTION
;
3866 size_t nb
= request2size(bytes
);
3867 size_t req
= nb
+ alignment
+ MIN_CHUNK_SIZE
- CHUNK_OVERHEAD
;
3868 char* mem
= (char*)internal_malloc(m
, req
);
3872 mchunkptr p
= mem2chunk(mem
);
3874 if (PREACTION(m
)) return 0;
3875 if ((((size_t)(mem
)) % alignment
) != 0) { /* misaligned */
3877 Find an aligned spot inside chunk. Since we need to give
3878 back leading space in a chunk of at least MIN_CHUNK_SIZE, if
3879 the first calculation places us at a spot with less than
3880 MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
3881 We've allocated enough total room so that this is always
3884 char* br
= (char*)mem2chunk((size_t)(((size_t)(mem
+
3888 char* pos
= ((size_t)(br
- (char*)(p
)) >= MIN_CHUNK_SIZE
)?
3890 mchunkptr newp
= (mchunkptr
)pos
;
3891 size_t leadsize
= pos
- (char*)(p
);
3892 size_t newsize
= chunksize(p
) - leadsize
;
3894 if (is_mmapped(p
)) { /* For mmapped chunks, just adjust offset */
3895 newp
->prev_foot
= p
->prev_foot
+ leadsize
;
3896 newp
->head
= (newsize
|CINUSE_BIT
);
3898 else { /* Otherwise, give back leader, use the rest */
3899 set_inuse(m
, newp
, newsize
);
3900 set_inuse(m
, p
, leadsize
);
3901 leader
= chunk2mem(p
);
3906 /* Give back spare room at the end */
3907 if (!is_mmapped(p
)) {
3908 size_t size
= chunksize(p
);
3909 if (size
> nb
+ MIN_CHUNK_SIZE
) {
3910 size_t remainder_size
= size
- nb
;
3911 mchunkptr remainder
= chunk_plus_offset(p
, nb
);
3912 set_inuse(m
, p
, nb
);
3913 set_inuse(m
, remainder
, remainder_size
);
3914 trailer
= chunk2mem(remainder
);
3918 assert (chunksize(p
) >= nb
);
3919 assert((((size_t)(chunk2mem(p
))) % alignment
) == 0);
3920 check_inuse_chunk(m
, p
);
3923 internal_free(m
, leader
);
3926 internal_free(m
, trailer
);
3928 return chunk2mem(p
);
3936 /* ------------------------ comalloc/coalloc support --------------------- */
3938 static void** ialloc(mstate m
,
3944 This provides common support for independent_X routines, handling
3945 all of the combinations that can result.
3948 bit 0 set if all elements are same size (using sizes[0])
3949 bit 1 set if elements should be zeroed
3952 size_t element_size
; /* chunksize of each element, if all same */
3953 size_t contents_size
; /* total size of elements */
3954 size_t array_size
; /* request size of pointer array */
3955 void* mem
; /* malloced aggregate space */
3956 mchunkptr p
; /* corresponding chunk */
3957 size_t remainder_size
; /* remaining bytes while splitting */
3958 void** marray
; /* either "chunks" or malloced ptr array */
3959 mchunkptr array_chunk
; /* chunk for malloced ptr array */
3960 flag_t was_enabled
; /* to disable mmap */
3964 /* compute array length, if needed */
3966 if (n_elements
== 0)
3967 return chunks
; /* nothing to do */
3972 /* if empty req, must still return chunk representing empty array */
3973 if (n_elements
== 0)
3974 return (void**)internal_malloc(m
, 0);
3976 array_size
= request2size(n_elements
* (sizeof(void*)));
3979 /* compute total element size */
3980 if (opts
& 0x1) { /* all-same-size */
3981 element_size
= request2size(*sizes
);
3982 contents_size
= n_elements
* element_size
;
3984 else { /* add up all the sizes */
3987 for (i
= 0; i
!= n_elements
; ++i
)
3988 contents_size
+= request2size(sizes
[i
]);
3991 size
= contents_size
+ array_size
;
3994 Allocate the aggregate chunk. First disable direct-mmapping so
3995 malloc won't use it, since we would not be able to later
3996 free/realloc space internal to a segregated mmap region.
3998 was_enabled
= use_mmap(m
);
4000 mem
= internal_malloc(m
, size
- CHUNK_OVERHEAD
);
4006 if (PREACTION(m
)) return 0;
4008 remainder_size
= chunksize(p
);
4010 assert(!is_mmapped(p
));
4012 if (opts
& 0x2) { /* optionally clear the elements */
4013 memset((size_t*)mem
, 0, remainder_size
- SIZE_T_SIZE
- array_size
);
4016 /* If not provided, allocate the pointer array as final part of chunk */
4018 size_t array_chunk_size
;
4019 array_chunk
= chunk_plus_offset(p
, contents_size
);
4020 array_chunk_size
= remainder_size
- contents_size
;
4021 marray
= (void**) (chunk2mem(array_chunk
));
4022 set_size_and_pinuse_of_inuse_chunk(m
, array_chunk
, array_chunk_size
);
4023 remainder_size
= contents_size
;
4026 /* split out elements */
4027 for (i
= 0; ; ++i
) {
4028 marray
[i
] = chunk2mem(p
);
4029 if (i
!= n_elements
-1) {
4030 if (element_size
!= 0)
4031 size
= element_size
;
4033 size
= request2size(sizes
[i
]);
4034 remainder_size
-= size
;
4035 set_size_and_pinuse_of_inuse_chunk(m
, p
, size
);
4036 p
= chunk_plus_offset(p
, size
);
4038 else { /* the final element absorbs any overallocation slop */
4039 set_size_and_pinuse_of_inuse_chunk(m
, p
, remainder_size
);
4045 if (marray
!= chunks
) {
4046 /* final element must have exactly exhausted chunk */
4047 if (element_size
!= 0) {
4048 assert(remainder_size
== element_size
);
4051 assert(remainder_size
== request2size(sizes
[i
]));
4053 check_inuse_chunk(m
, mem2chunk(marray
));
4055 for (i
= 0; i
!= n_elements
; ++i
)
4056 check_inuse_chunk(m
, mem2chunk(marray
[i
]));
4066 /* -------------------------- public routines ---------------------------- */
4070 void* dlmalloc(size_t bytes
) {
4073 If a small request (< 256 bytes minus per-chunk overhead):
4074 1. If one exists, use a remainderless chunk in associated smallbin.
4075 (Remainderless means that there are too few excess bytes to
4076 represent as a chunk.)
4077 2. If it is big enough, use the dv chunk, which is normally the
4078 chunk adjacent to the one used for the most recent small request.
4079 3. If one exists, split the smallest available chunk in a bin,
4080 saving remainder in dv.
4081 4. If it is big enough, use the top chunk.
4082 5. If available, get memory from system and use it
4083 Otherwise, for a large request:
4084 1. Find the smallest available binned chunk that fits, and use it
4085 if it is better fitting than dv chunk, splitting if necessary.
4086 2. If better fitting than any binned chunk, use the dv chunk.
4087 3. If it is big enough, use the top chunk.
4088 4. If request size >= mmap threshold, try to directly mmap this chunk.
4089 5. If available, get memory from system and use it
4091 The ugly goto's here ensure that postaction occurs along all paths.
4094 if (!PREACTION(gm
)) {
4097 if (bytes
<= MAX_SMALL_REQUEST
) {
4100 nb
= (bytes
< MIN_REQUEST
)? MIN_CHUNK_SIZE
: pad_request(bytes
);
4101 idx
= small_index(nb
);
4102 smallbits
= gm
->smallmap
>> idx
;
4104 if ((smallbits
& 0x3U
) != 0) { /* Remainderless fit to a smallbin. */
4106 idx
+= ~smallbits
& 1; /* Uses next bin if idx empty */
4107 b
= smallbin_at(gm
, idx
);
4109 assert(chunksize(p
) == small_index2size(idx
));
4110 unlink_first_small_chunk(gm
, b
, p
, idx
);
4111 set_inuse_and_pinuse(gm
, p
, small_index2size(idx
));
4113 check_malloced_chunk(gm
, mem
, nb
);
4117 else if (nb
> gm
->dvsize
) {
4118 if (smallbits
!= 0) { /* Use chunk in next nonempty smallbin */
4122 binmap_t leftbits
= (smallbits
<< idx
) & left_bits(idx2bit(idx
));
4123 binmap_t leastbit
= least_bit(leftbits
);
4124 compute_bit2idx(leastbit
, i
);
4125 b
= smallbin_at(gm
, i
);
4127 assert(chunksize(p
) == small_index2size(i
));
4128 unlink_first_small_chunk(gm
, b
, p
, i
);
4129 rsize
= small_index2size(i
) - nb
;
4130 /* Fit here cannot be remainderless if 4byte sizes */
4131 if (SIZE_T_SIZE
!= 4 && rsize
< MIN_CHUNK_SIZE
)
4132 set_inuse_and_pinuse(gm
, p
, small_index2size(i
));
4134 set_size_and_pinuse_of_inuse_chunk(gm
, p
, nb
);
4135 r
= chunk_plus_offset(p
, nb
);
4136 set_size_and_pinuse_of_free_chunk(r
, rsize
);
4137 replace_dv(gm
, r
, rsize
);
4140 check_malloced_chunk(gm
, mem
, nb
);
4144 else if (gm
->treemap
!= 0 && (mem
= tmalloc_small(gm
, nb
)) != 0) {
4145 check_malloced_chunk(gm
, mem
, nb
);
4150 else if (bytes
>= MAX_REQUEST
)
4151 nb
= MAX_SIZE_T
; /* Too big to allocate. Force failure (in sys alloc) */
4153 nb
= pad_request(bytes
);
4154 if (gm
->treemap
!= 0 && (mem
= tmalloc_large(gm
, nb
)) != 0) {
4155 check_malloced_chunk(gm
, mem
, nb
);
4160 if (nb
<= gm
->dvsize
) {
4161 size_t rsize
= gm
->dvsize
- nb
;
4162 mchunkptr p
= gm
->dv
;
4163 if (rsize
>= MIN_CHUNK_SIZE
) { /* split dv */
4164 mchunkptr r
= gm
->dv
= chunk_plus_offset(p
, nb
);
4166 set_size_and_pinuse_of_free_chunk(r
, rsize
);
4167 set_size_and_pinuse_of_inuse_chunk(gm
, p
, nb
);
4169 else { /* exhaust dv */
4170 size_t dvs
= gm
->dvsize
;
4173 set_inuse_and_pinuse(gm
, p
, dvs
);
4176 check_malloced_chunk(gm
, mem
, nb
);
4180 else if (nb
< gm
->topsize
) { /* Split top */
4181 size_t rsize
= gm
->topsize
-= nb
;
4182 mchunkptr p
= gm
->top
;
4183 mchunkptr r
= gm
->top
= chunk_plus_offset(p
, nb
);
4184 r
->head
= rsize
| PINUSE_BIT
;
4185 set_size_and_pinuse_of_inuse_chunk(gm
, p
, nb
);
4187 check_top_chunk(gm
, gm
->top
);
4188 check_malloced_chunk(gm
, mem
, nb
);
4192 mem
= sys_alloc(gm
, nb
);
4202 void dlfree(void* mem
) {
4204 Consolidate freed chunks with preceeding or succeeding bordering
4205 free chunks, if they exist, and then place in a bin. Intermixed
4206 with special cases for top, dv, mmapped chunks, and usage errors.
4210 mchunkptr p
= mem2chunk(mem
);
4212 mstate fm
= get_mstate_for(p
);
4213 if (!ok_magic(fm
)) {
4214 USAGE_ERROR_ACTION(fm
, p
);
4219 #endif /* FOOTERS */
4220 if (!PREACTION(fm
)) {
4221 check_inuse_chunk(fm
, p
);
4222 if (RTCHECK(ok_address(fm
, p
) && ok_cinuse(p
))) {
4223 size_t psize
= chunksize(p
);
4224 mchunkptr next
= chunk_plus_offset(p
, psize
);
4226 size_t prevsize
= p
->prev_foot
;
4227 if ((prevsize
& IS_MMAPPED_BIT
) != 0) {
4228 prevsize
&= ~IS_MMAPPED_BIT
;
4229 psize
+= prevsize
+ MMAP_FOOT_PAD
;
4230 if (CALL_MUNMAP((char*)p
- prevsize
, psize
) == 0)
4231 fm
->footprint
-= psize
;
4235 mchunkptr prev
= chunk_minus_offset(p
, prevsize
);
4238 if (RTCHECK(ok_address(fm
, prev
))) { /* consolidate backward */
4240 unlink_chunk(fm
, p
, prevsize
);
4242 else if ((next
->head
& INUSE_BITS
) == INUSE_BITS
) {
4244 set_free_with_pinuse(p
, psize
, next
);
4253 if (RTCHECK(ok_next(p
, next
) && ok_pinuse(next
))) {
4254 if (!cinuse(next
)) { /* consolidate forward */
4255 if (next
== fm
->top
) {
4256 size_t tsize
= fm
->topsize
+= psize
;
4258 p
->head
= tsize
| PINUSE_BIT
;
4263 if (should_trim(fm
, tsize
))
4267 else if (next
== fm
->dv
) {
4268 size_t dsize
= fm
->dvsize
+= psize
;
4270 set_size_and_pinuse_of_free_chunk(p
, dsize
);
4274 size_t nsize
= chunksize(next
);
4276 unlink_chunk(fm
, next
, nsize
);
4277 set_size_and_pinuse_of_free_chunk(p
, psize
);
4285 set_free_with_pinuse(p
, psize
, next
);
4286 insert_chunk(fm
, p
, psize
);
4287 check_free_chunk(fm
, p
);
4292 USAGE_ERROR_ACTION(fm
, p
);
4299 #endif /* FOOTERS */
4304 void* dlcalloc(size_t n_elements
, size_t elem_size
) {
4307 if (n_elements
!= 0) {
4308 req
= n_elements
* elem_size
;
4309 if (((n_elements
| elem_size
) & ~(size_t)0xffff) &&
4310 (req
/ n_elements
!= elem_size
))
4311 req
= MAX_SIZE_T
; /* force downstream failure on overflow */
4313 mem
= dlmalloc(req
);
4314 if (mem
!= 0 && calloc_must_clear(mem2chunk(mem
)))
4315 memset(mem
, 0, req
);
4319 void* dlrealloc(void* oldmem
, size_t bytes
) {
4321 return dlmalloc(bytes
);
4322 #ifdef REALLOC_ZERO_BYTES_FREES
4327 #endif /* REALLOC_ZERO_BYTES_FREES */
4332 mstate m
= get_mstate_for(mem2chunk(oldmem
));
4334 USAGE_ERROR_ACTION(m
, oldmem
);
4337 #endif /* FOOTERS */
4338 return internal_realloc(m
, oldmem
, bytes
);
4344 void* dlmemalign(size_t alignment
, size_t bytes
) {
4345 return internal_memalign(gm
, alignment
, bytes
);
4350 void** dlindependent_calloc(size_t n_elements
, size_t elem_size
,
4352 size_t sz
= elem_size
; /* serves as 1-element array */
4353 return ialloc(gm
, n_elements
, &sz
, 3, chunks
);
4356 void** dlindependent_comalloc(size_t n_elements
, size_t sizes
[],
4358 return ialloc(gm
, n_elements
, sizes
, 0, chunks
);
4361 void* dlvalloc(size_t bytes
) {
4364 pagesz
= mparams
.page_size
;
4365 return dlmemalign(pagesz
, bytes
);
4368 void* dlpvalloc(size_t bytes
) {
4371 pagesz
= mparams
.page_size
;
4372 return dlmemalign(pagesz
, (bytes
+ pagesz
- SIZE_T_ONE
) & ~(pagesz
- SIZE_T_ONE
));
4375 int dlmalloc_trim(size_t pad
) {
4377 if (!PREACTION(gm
)) {
4378 result
= sys_trim(gm
, pad
);
4384 size_t dlmalloc_footprint(void) {
4385 return gm
->footprint
;
4388 size_t dlmalloc_max_footprint(void) {
4389 return gm
->max_footprint
;
4393 struct mallinfo
dlmallinfo(void) {
4394 return internal_mallinfo(gm
);
4396 #endif /* NO_MALLINFO */
4398 void dlmalloc_stats() {
4399 internal_malloc_stats(gm
);
4402 size_t dlmalloc_usable_size(void* mem
) {
4404 mchunkptr p
= mem2chunk(mem
);
4406 return chunksize(p
) - overhead_for(p
);
4411 int dlmallopt(int param_number
, int value
) {
4412 return change_mparam(param_number
, value
);
4417 #endif /* !ONLY_MSPACES */
4419 /* ----------------------------- user mspaces ---------------------------- */
4423 static mstate
init_user_mstate(char* tbase
, size_t tsize
) {
4424 size_t msize
= pad_request(sizeof(struct malloc_state
));
4426 mchunkptr msp
= align_as_chunk(tbase
);
4427 mstate m
= (mstate
)(chunk2mem(msp
));
4428 memset(m
, 0, msize
);
4429 INITIAL_LOCK(&m
->mutex
);
4430 msp
->head
= (msize
|PINUSE_BIT
|CINUSE_BIT
);
4431 m
->seg
.base
= m
->least_addr
= tbase
;
4432 m
->seg
.size
= m
->footprint
= m
->max_footprint
= tsize
;
4433 m
->magic
= mparams
.magic
;
4434 m
->mflags
= mparams
.default_mflags
;
4435 disable_contiguous(m
);
4437 mn
= next_chunk(mem2chunk(m
));
4438 init_top(m
, mn
, (size_t)((tbase
+ tsize
) - (char*)mn
) - TOP_FOOT_SIZE
);
4439 check_top_chunk(m
, m
->top
);
4443 mspace
create_mspace(size_t capacity
, int locked
) {
4445 size_t msize
= pad_request(sizeof(struct malloc_state
));
4446 init_mparams(); /* Ensure pagesize etc initialized */
4448 if (capacity
< (size_t) -(msize
+ TOP_FOOT_SIZE
+ mparams
.page_size
)) {
4449 size_t rs
= ((capacity
== 0)? mparams
.granularity
:
4450 (capacity
+ TOP_FOOT_SIZE
+ msize
));
4451 size_t tsize
= granularity_align(rs
);
4452 char* tbase
= (char*)(CALL_MMAP(tsize
));
4453 if (tbase
!= CMFAIL
) {
4454 m
= init_user_mstate(tbase
, tsize
);
4455 m
->seg
.sflags
= IS_MMAPPED_BIT
;
4456 set_lock(m
, locked
);
4462 mspace
create_mspace_with_base(void* base
, size_t capacity
, int locked
) {
4464 size_t msize
= pad_request(sizeof(struct malloc_state
));
4465 init_mparams(); /* Ensure pagesize etc initialized */
4467 if (capacity
> msize
+ TOP_FOOT_SIZE
&&
4468 capacity
< (size_t) -(msize
+ TOP_FOOT_SIZE
+ mparams
.page_size
)) {
4469 m
= init_user_mstate((char*)base
, capacity
);
4470 m
->seg
.sflags
= EXTERN_BIT
;
4471 set_lock(m
, locked
);
4476 size_t destroy_mspace(mspace msp
) {
4478 mstate ms
= (mstate
)msp
;
4480 msegmentptr sp
= &ms
->seg
;
4482 char* base
= sp
->base
;
4483 size_t size
= sp
->size
;
4484 flag_t flag
= sp
->sflags
;
4486 if ((flag
& IS_MMAPPED_BIT
) && !(flag
& EXTERN_BIT
) &&
4487 CALL_MUNMAP(base
, size
) == 0)
4492 USAGE_ERROR_ACTION(ms
,ms
);
4498 mspace versions of routines are near-clones of the global
4499 versions. This is not so nice but better than the alternatives.
4502 void* mspace_malloc(mspace msp
, size_t bytes
) {
4503 mstate ms
= (mstate
)msp
;
4504 if (!ok_magic(ms
)) {
4505 USAGE_ERROR_ACTION(ms
,ms
);
4508 if (!PREACTION(ms
)) {
4511 if (bytes
<= MAX_SMALL_REQUEST
) {
4514 nb
= (bytes
< MIN_REQUEST
)? MIN_CHUNK_SIZE
: pad_request(bytes
);
4515 idx
= small_index(nb
);
4516 smallbits
= ms
->smallmap
>> idx
;
4518 if ((smallbits
& 0x3U
) != 0) { /* Remainderless fit to a smallbin. */
4520 idx
+= ~smallbits
& 1; /* Uses next bin if idx empty */
4521 b
= smallbin_at(ms
, idx
);
4523 assert(chunksize(p
) == small_index2size(idx
));
4524 unlink_first_small_chunk(ms
, b
, p
, idx
);
4525 set_inuse_and_pinuse(ms
, p
, small_index2size(idx
));
4527 check_malloced_chunk(ms
, mem
, nb
);
4531 else if (nb
> ms
->dvsize
) {
4532 if (smallbits
!= 0) { /* Use chunk in next nonempty smallbin */
4536 binmap_t leftbits
= (smallbits
<< idx
) & left_bits(idx2bit(idx
));
4537 binmap_t leastbit
= least_bit(leftbits
);
4538 compute_bit2idx(leastbit
, i
);
4539 b
= smallbin_at(ms
, i
);
4541 assert(chunksize(p
) == small_index2size(i
));
4542 unlink_first_small_chunk(ms
, b
, p
, i
);
4543 rsize
= small_index2size(i
) - nb
;
4544 /* Fit here cannot be remainderless if 4byte sizes */
4545 if (SIZE_T_SIZE
!= 4 && rsize
< MIN_CHUNK_SIZE
)
4546 set_inuse_and_pinuse(ms
, p
, small_index2size(i
));
4548 set_size_and_pinuse_of_inuse_chunk(ms
, p
, nb
);
4549 r
= chunk_plus_offset(p
, nb
);
4550 set_size_and_pinuse_of_free_chunk(r
, rsize
);
4551 replace_dv(ms
, r
, rsize
);
4554 check_malloced_chunk(ms
, mem
, nb
);
4558 else if (ms
->treemap
!= 0 && (mem
= tmalloc_small(ms
, nb
)) != 0) {
4559 check_malloced_chunk(ms
, mem
, nb
);
4564 else if (bytes
>= MAX_REQUEST
)
4565 nb
= MAX_SIZE_T
; /* Too big to allocate. Force failure (in sys alloc) */
4567 nb
= pad_request(bytes
);
4568 if (ms
->treemap
!= 0 && (mem
= tmalloc_large(ms
, nb
)) != 0) {
4569 check_malloced_chunk(ms
, mem
, nb
);
4574 if (nb
<= ms
->dvsize
) {
4575 size_t rsize
= ms
->dvsize
- nb
;
4576 mchunkptr p
= ms
->dv
;
4577 if (rsize
>= MIN_CHUNK_SIZE
) { /* split dv */
4578 mchunkptr r
= ms
->dv
= chunk_plus_offset(p
, nb
);
4580 set_size_and_pinuse_of_free_chunk(r
, rsize
);
4581 set_size_and_pinuse_of_inuse_chunk(ms
, p
, nb
);
4583 else { /* exhaust dv */
4584 size_t dvs
= ms
->dvsize
;
4587 set_inuse_and_pinuse(ms
, p
, dvs
);
4590 check_malloced_chunk(ms
, mem
, nb
);
4594 else if (nb
< ms
->topsize
) { /* Split top */
4595 size_t rsize
= ms
->topsize
-= nb
;
4596 mchunkptr p
= ms
->top
;
4597 mchunkptr r
= ms
->top
= chunk_plus_offset(p
, nb
);
4598 r
->head
= rsize
| PINUSE_BIT
;
4599 set_size_and_pinuse_of_inuse_chunk(ms
, p
, nb
);
4601 check_top_chunk(ms
, ms
->top
);
4602 check_malloced_chunk(ms
, mem
, nb
);
4606 mem
= sys_alloc(ms
, nb
);
4616 void mspace_free(mspace msp
, void* mem
) {
4618 mchunkptr p
= mem2chunk(mem
);
4620 mstate fm
= get_mstate_for(p
);
4622 mstate fm
= (mstate
)msp
;
4623 #endif /* FOOTERS */
4624 if (!ok_magic(fm
)) {
4625 USAGE_ERROR_ACTION(fm
, p
);
4628 if (!PREACTION(fm
)) {
4629 check_inuse_chunk(fm
, p
);
4630 if (RTCHECK(ok_address(fm
, p
) && ok_cinuse(p
))) {
4631 size_t psize
= chunksize(p
);
4632 mchunkptr next
= chunk_plus_offset(p
, psize
);
4634 size_t prevsize
= p
->prev_foot
;
4635 if ((prevsize
& IS_MMAPPED_BIT
) != 0) {
4636 prevsize
&= ~IS_MMAPPED_BIT
;
4637 psize
+= prevsize
+ MMAP_FOOT_PAD
;
4638 if (CALL_MUNMAP((char*)p
- prevsize
, psize
) == 0)
4639 fm
->footprint
-= psize
;
4643 mchunkptr prev
= chunk_minus_offset(p
, prevsize
);
4646 if (RTCHECK(ok_address(fm
, prev
))) { /* consolidate backward */
4648 unlink_chunk(fm
, p
, prevsize
);
4650 else if ((next
->head
& INUSE_BITS
) == INUSE_BITS
) {
4652 set_free_with_pinuse(p
, psize
, next
);
4661 if (RTCHECK(ok_next(p
, next
) && ok_pinuse(next
))) {
4662 if (!cinuse(next
)) { /* consolidate forward */
4663 if (next
== fm
->top
) {
4664 size_t tsize
= fm
->topsize
+= psize
;
4666 p
->head
= tsize
| PINUSE_BIT
;
4671 if (should_trim(fm
, tsize
))
4675 else if (next
== fm
->dv
) {
4676 size_t dsize
= fm
->dvsize
+= psize
;
4678 set_size_and_pinuse_of_free_chunk(p
, dsize
);
4682 size_t nsize
= chunksize(next
);
4684 unlink_chunk(fm
, next
, nsize
);
4685 set_size_and_pinuse_of_free_chunk(p
, psize
);
4693 set_free_with_pinuse(p
, psize
, next
);
4694 insert_chunk(fm
, p
, psize
);
4695 check_free_chunk(fm
, p
);
4700 USAGE_ERROR_ACTION(fm
, p
);
4707 void* mspace_calloc(mspace msp
, size_t n_elements
, size_t elem_size
) {
4710 mstate ms
= (mstate
)msp
;
4711 if (!ok_magic(ms
)) {
4712 USAGE_ERROR_ACTION(ms
,ms
);
4715 if (n_elements
!= 0) {
4716 req
= n_elements
* elem_size
;
4717 if (((n_elements
| elem_size
) & ~(size_t)0xffff) &&
4718 (req
/ n_elements
!= elem_size
))
4719 req
= MAX_SIZE_T
; /* force downstream failure on overflow */
4721 mem
= internal_malloc(ms
, req
);
4722 if (mem
!= 0 && calloc_must_clear(mem2chunk(mem
)))
4723 memset(mem
, 0, req
);
4727 void* mspace_realloc(mspace msp
, void* oldmem
, size_t bytes
) {
4729 return mspace_malloc(msp
, bytes
);
4730 #ifdef REALLOC_ZERO_BYTES_FREES
4732 mspace_free(msp
, oldmem
);
4735 #endif /* REALLOC_ZERO_BYTES_FREES */
4738 mchunkptr p
= mem2chunk(oldmem
);
4739 mstate ms
= get_mstate_for(p
);
4741 mstate ms
= (mstate
)msp
;
4742 #endif /* FOOTERS */
4743 if (!ok_magic(ms
)) {
4744 USAGE_ERROR_ACTION(ms
,ms
);
4747 return internal_realloc(ms
, oldmem
, bytes
);
4751 void* mspace_memalign(mspace msp
, size_t alignment
, size_t bytes
) {
4752 mstate ms
= (mstate
)msp
;
4753 if (!ok_magic(ms
)) {
4754 USAGE_ERROR_ACTION(ms
,ms
);
4757 return internal_memalign(ms
, alignment
, bytes
);
4760 void** mspace_independent_calloc(mspace msp
, size_t n_elements
,
4761 size_t elem_size
, void* chunks
[]) {
4762 size_t sz
= elem_size
; /* serves as 1-element array */
4763 mstate ms
= (mstate
)msp
;
4764 if (!ok_magic(ms
)) {
4765 USAGE_ERROR_ACTION(ms
,ms
);
4768 return ialloc(ms
, n_elements
, &sz
, 3, chunks
);
4771 void** mspace_independent_comalloc(mspace msp
, size_t n_elements
,
4772 size_t sizes
[], void* chunks
[]) {
4773 mstate ms
= (mstate
)msp
;
4774 if (!ok_magic(ms
)) {
4775 USAGE_ERROR_ACTION(ms
,ms
);
4778 return ialloc(ms
, n_elements
, sizes
, 0, chunks
);
4781 int mspace_trim(mspace msp
, size_t pad
) {
4783 mstate ms
= (mstate
)msp
;
4785 if (!PREACTION(ms
)) {
4786 result
= sys_trim(ms
, pad
);
4791 USAGE_ERROR_ACTION(ms
,ms
);
4796 void mspace_malloc_stats(mspace msp
) {
4797 mstate ms
= (mstate
)msp
;
4799 internal_malloc_stats(ms
);
4802 USAGE_ERROR_ACTION(ms
,ms
);
4806 size_t mspace_footprint(mspace msp
) {
4808 mstate ms
= (mstate
)msp
;
4810 result
= ms
->footprint
;
4812 USAGE_ERROR_ACTION(ms
,ms
);
4817 size_t mspace_max_footprint(mspace msp
) {
4819 mstate ms
= (mstate
)msp
;
4821 result
= ms
->max_footprint
;
4823 USAGE_ERROR_ACTION(ms
,ms
);
4829 struct mallinfo
mspace_mallinfo(mspace msp
) {
4830 mstate ms
= (mstate
)msp
;
4831 if (!ok_magic(ms
)) {
4832 USAGE_ERROR_ACTION(ms
,ms
);
4834 return internal_mallinfo(ms
);
4836 #endif /* NO_MALLINFO */
4838 int mspace_mallopt(int param_number
, int value
) {
4839 return change_mparam(param_number
, value
);
4842 #endif /* MSPACES */
4844 /* -------------------- Alternative MORECORE functions ------------------- */
4847 Guidelines for creating a custom version of MORECORE:
4849 * For best performance, MORECORE should allocate in multiples of pagesize.
4850 * MORECORE may allocate more memory than requested. (Or even less,
4851 but this will usually result in a malloc failure.)
4852 * MORECORE must not allocate memory when given argument zero, but
4853 instead return one past the end address of memory from previous
4855 * For best performance, consecutive calls to MORECORE with positive
4856 arguments should return increasing addresses, indicating that
4857 space has been contiguously extended.
4858 * Even though consecutive calls to MORECORE need not return contiguous
4859 addresses, it must be OK for malloc'ed chunks to span multiple
4860 regions in those cases where they do happen to be contiguous.
4861 * MORECORE need not handle negative arguments -- it may instead
4862 just return MFAIL when given negative arguments.
4863 Negative arguments are always multiples of pagesize. MORECORE
4864 must not misinterpret negative args as large positive unsigned
4865 args. You can suppress all such calls from even occurring by defining
4866 MORECORE_CANNOT_TRIM,
4868 As an example alternative MORECORE, here is a custom allocator
4869 kindly contributed for pre-OSX macOS. It uses virtually but not
4870 necessarily physically contiguous non-paged memory (locked in,
4871 present and won't get swapped out). You can use it by uncommenting
4872 this section, adding some #includes, and setting up the appropriate
4875 #define MORECORE osMoreCore
4877 There is also a shutdown routine that should somehow be called for
4878 cleanup upon program exit.
4880 #define MAX_POOL_ENTRIES 100
4881 #define MINIMUM_MORECORE_SIZE (64 * 1024U)
4882 static int next_os_pool;
4883 void *our_os_pools[MAX_POOL_ENTRIES];
4885 void *osMoreCore(int size)
4888 static void *sbrk_top = 0;
4892 if (size < MINIMUM_MORECORE_SIZE)
4893 size = MINIMUM_MORECORE_SIZE;
4894 if (CurrentExecutionLevel() == kTaskLevel)
4895 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4898 return (void *) MFAIL;
4900 // save ptrs so they can be freed during cleanup
4901 our_os_pools[next_os_pool] = ptr;
4903 ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4904 sbrk_top = (char *) ptr + size;
4909 // we don't currently support shrink behavior
4910 return (void *) MFAIL;
4918 // cleanup any allocated memory pools
4919 // called as last thing before shutting down driver
4921 void osCleanupMem(void)
4925 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4928 PoolDeallocate(*ptr);
4936 /* -----------------------------------------------------------------------
4938 V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee)
4939 * Add max_footprint functions
4940 * Ensure all appropriate literals are size_t
4941 * Fix conditional compilation problem for some #define settings
4942 * Avoid concatenating segments with the one provided
4943 in create_mspace_with_base
4944 * Rename some variables to avoid compiler shadowing warnings
4945 * Use explicit lock initialization.
4946 * Better handling of sbrk interference.
4947 * Simplify and fix segment insertion, trimming and mspace_destroy
4948 * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
4949 * Thanks especially to Dennis Flanagan for help on these.
4951 V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee)
4952 * Fix memalign brace error.
4954 V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee)
4955 * Fix improper #endif nesting in C++
4956 * Add explicit casts needed for C++
4958 V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee)
4959 * Use trees for large bins
4961 * Use segments to unify sbrk-based and mmap-based system allocation,
4962 removing need for emulation on most platforms without sbrk.
4963 * Default safety checks
4964 * Optional footer checks. Thanks to William Robertson for the idea.
4965 * Internal code refactoring
4966 * Incorporate suggestions and platform-specific changes.
4967 Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
4968 Aaron Bachmann, Emery Berger, and others.
4969 * Speed up non-fastbin processing enough to remove fastbins.
4970 * Remove useless cfree() to avoid conflicts with other apps.
4971 * Remove internal memcpy, memset. Compilers handle builtins better.
4972 * Remove some options that no one ever used and rename others.
4974 V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee)
4975 * Fix malloc_state bitmap array misdeclaration
4977 V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
4978 * Allow tuning of FIRST_SORTED_BIN_SIZE
4979 * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
4980 * Better detection and support for non-contiguousness of MORECORE.
4981 Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
4982 * Bypass most of malloc if no frees. Thanks To Emery Berger.
4983 * Fix freeing of old top non-contiguous chunk im sysmalloc.
4984 * Raised default trim and map thresholds to 256K.
4985 * Fix mmap-related #defines. Thanks to Lubos Lunak.
4986 * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
4987 * Branch-free bin calculation
4988 * Default trim and mmap thresholds now 256K.
4990 V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
4991 * Introduce independent_comalloc and independent_calloc.
4992 Thanks to Michael Pachos for motivation and help.
4993 * Make optional .h file available
4994 * Allow > 2GB requests on 32bit systems.
4995 * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
4996 Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
4998 * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
5000 * memalign: check alignment arg
5001 * realloc: don't try to shift chunks backwards, since this
5002 leads to more fragmentation in some programs and doesn't
5003 seem to help in any others.
5004 * Collect all cases in malloc requiring system memory into sysmalloc
5005 * Use mmap as backup to sbrk
5006 * Place all internal state in malloc_state
5007 * Introduce fastbins (although similar to 2.5.1)
5008 * Many minor tunings and cosmetic improvements
5009 * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
5010 * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
5011 Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
5012 * Include errno.h to support default failure action.
5014 V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
5015 * return null for negative arguments
5016 * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5017 * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5018 (e.g. WIN32 platforms)
5019 * Cleanup header file inclusion for WIN32 platforms
5020 * Cleanup code to avoid Microsoft Visual C++ compiler complaints
5021 * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5022 memory allocation routines
5023 * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5024 * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5025 usage of 'assert' in non-WIN32 code
5026 * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5028 * Always call 'fREe()' rather than 'free()'
5030 V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
5031 * Fixed ordering problem with boundary-stamping
5033 V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
5034 * Added pvalloc, as recommended by H.J. Liu
5035 * Added 64bit pointer support mainly from Wolfram Gloger
5036 * Added anonymously donated WIN32 sbrk emulation
5037 * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5038 * malloc_extend_top: fix mask error that caused wastage after
5040 * Add linux mremap support code from HJ Liu
5042 V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
5043 * Integrated most documentation with the code.
5044 * Add support for mmap, with help from
5045 Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5046 * Use last_remainder in more cases.
5047 * Pack bins using idea from colin@nyx10.cs.du.edu
5048 * Use ordered bins instead of best-fit threshhold
5049 * Eliminate block-local decls to simplify tracing and debugging.
5050 * Support another case of realloc via move into top
5051 * Fix error occuring when initial sbrk_base not word-aligned.
5052 * Rely on page size for units instead of SBRK_UNIT to
5053 avoid surprises about sbrk alignment conventions.
5054 * Add mallinfo, mallopt. Thanks to Raymond Nijssen
5055 (raymond@es.ele.tue.nl) for the suggestion.
5056 * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5057 * More precautions for cases where other routines call sbrk,
5058 courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5059 * Added macros etc., allowing use in linux libc from
5060 H.J. Lu (hjl@gnu.ai.mit.edu)
5061 * Inverted this history list
5063 V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
5064 * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5065 * Removed all preallocation code since under current scheme
5066 the work required to undo bad preallocations exceeds
5067 the work saved in good cases for most test programs.
5068 * No longer use return list or unconsolidated bins since
5069 no scheme using them consistently outperforms those that don't
5070 given above changes.
5071 * Use best fit for very large chunks to prevent some worst-cases.
5072 * Added some support for debugging
5074 V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
5075 * Removed footers when chunks are in use. Thanks to
5076 Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5078 V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
5079 * Added malloc_trim, with help from Wolfram Gloger
5080 (wmglo@Dent.MED.Uni-Muenchen.DE).
5082 V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
5084 V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
5085 * realloc: try to expand in both directions
5086 * malloc: swap order of clean-bin strategy;
5087 * realloc: only conditionally expand backwards
5088 * Try not to scavenge used bins
5089 * Use bin counts as a guide to preallocation
5090 * Occasionally bin return list chunks in first scan
5091 * Add a few optimizations from colin@nyx10.cs.du.edu
5093 V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
5094 * faster bin computation & slightly different binning
5095 * merged all consolidations to one part of malloc proper
5096 (eliminating old malloc_find_space & malloc_clean_bin)
5097 * Scan 2 returns chunks (not just 1)
5098 * Propagate failure in realloc if malloc returns 0
5099 * Add stuff to allow compilation on non-ANSI compilers
5100 from kpv@research.att.com
5102 V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
5103 * removed potential for odd address access in prev_chunk
5104 * removed dependency on getpagesize.h
5105 * misc cosmetics and a bit more internal documentation
5106 * anticosmetics: mangled names in macros to evade debugger strangeness
5107 * tested on sparc, hp-700, dec-mips, rs6000
5108 with gcc & native cc (hp, dec only) allowing
5109 Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5111 Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
5112 * Based loosely on libg++-1.2X malloc. (It retains some of the overall
5113 structure of old version, but most details differ.)