3
#define __attribute_malloc__
8
This is a version (aka dlmalloc) of malloc/free/realloc written by
9
Doug Lea and released to the public domain, as explained at
10
http://creativecommons.org/publicdomain/zero/1.0/ Send questions,
11
comments, complaints, performance data, etc to dl@cs.oswego.edu
13
* Version 2.8.6 Wed Aug 29 06:57:58 2012 Doug Lea
14
Note: There may be an updated version of this malloc obtainable at
15
ftp://gee.cs.oswego.edu/pub/misc/malloc.c
16
Check before installing!
20
This library is all in one file to simplify the most common usage:
21
ftp it, compile it (-O3), and link it into another program. All of
22
the compile-time options default to reasonable values for use on
23
most platforms. You might later want to step through various
24
compile-time and dynamic tuning options.
26
For convenience, an include file for code using this malloc is at:
27
ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.6.h
28
You don't really need this .h file unless you call functions not
29
defined in your system include files. The .h file contains only the
30
excerpts from this file needed for using this malloc on ANSI C/C++
31
systems, so long as you haven't changed compile-time options about
32
naming and tuning parameters. If you do, then you can create your
33
own malloc.h that does include all settings by cutting at the point
34
indicated below. Note that you may already by default be using a C
35
library containing a malloc that is based on some version of this
36
malloc (for example in linux). You might still want to use the one
37
in this file to customize settings or to avoid overheads associated
38
with library versions.
42
Supported pointer/size_t representation: 4 or 8 bytes
43
size_t MUST be an unsigned type of the same width as
44
pointers. (If you are using an ancient system that declares
45
size_t as a signed type, or need it to be a different width
46
than pointers, you can use a previous release of this malloc
47
(e.g. 2.7.2) supporting these.)
49
Alignment: 8 bytes (minimum)
50
This suffices for nearly all current machines and C compilers.
51
However, you can define MALLOC_ALIGNMENT to be wider than this
52
if necessary (up to 128bytes), at the expense of using more space.
54
Minimum overhead per allocated chunk: 4 or 8 bytes (if 4byte sizes)
55
8 or 16 bytes (if 8byte sizes)
56
Each malloced chunk has a hidden word of overhead holding size
57
and status information, and additional cross-check word
58
if FOOTERS is defined.
60
Minimum allocated size: 4-byte ptrs: 16 bytes (including overhead)
61
8-byte ptrs: 32 bytes (including overhead)
63
Even a request for zero bytes (i.e., malloc(0)) returns a
64
pointer to something of the minimum allocatable size.
65
The maximum overhead wastage (i.e., number of extra bytes
66
allocated than were requested in malloc) is less than or equal
67
to the minimum size, except for requests >= mmap_threshold that
68
are serviced via mmap(), where the worst case wastage is about
69
32 bytes plus the remainder from a system page (the minimal
70
mmap unit); typically 4096 or 8192 bytes.
72
Security: static-safe; optionally more or less
73
The "security" of malloc refers to the ability of malicious
74
code to accentuate the effects of errors (for example, freeing
75
space that is not currently malloc'ed or overwriting past the
76
ends of chunks) in code that calls malloc. This malloc
77
guarantees not to modify any memory locations below the base of
78
heap, i.e., static variables, even in the presence of usage
79
errors. The routines additionally detect most improper frees
80
and reallocs. All this holds as long as the static bookkeeping
81
for malloc itself is not corrupted by some other means. This
82
is only one aspect of security -- these checks do not, and
83
cannot, detect all possible programming errors.
85
If FOOTERS is defined nonzero, then each allocated chunk
86
carries an additional check word to verify that it was malloced
87
from its space. These check words are the same within each
88
execution of a program using malloc, but differ across
89
executions, so externally crafted fake chunks cannot be
90
freed. This improves security by rejecting frees/reallocs that
91
could corrupt heap memory, in addition to the checks preventing
92
writes to statics that are always on. This may further improve
93
security at the expense of time and space overhead. (Note that
94
FOOTERS may also be worth using with MSPACES.)
96
By default detected errors cause the program to abort (calling
97
"abort()"). You can override this to instead proceed past
98
errors by defining PROCEED_ON_ERROR. In this case, a bad free
99
has no effect, and a malloc that encounters a bad address
100
caused by user overwrites will ignore the bad address by
101
dropping pointers and indices to all known memory. This may
102
be appropriate for programs that should continue if at all
103
possible in the face of programming errors, although they may
104
run out of memory because dropped memory is never reclaimed.
106
If you don't like either of these options, you can define
107
CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
108
else. And if if you are sure that your program using malloc has
109
no errors or vulnerabilities, you can define INSECURE to 1,
110
which might (or might not) provide a small performance improvement.
112
It is also possible to limit the maximum total allocatable
113
space, using malloc_set_footprint_limit. This is not
114
designed as a security feature in itself (calls to set limits
115
are not screened or privileged), but may be useful as one
116
aspect of a secure implementation.
118
Thread-safety: NOT thread-safe unless USE_LOCKS defined non-zero
119
When USE_LOCKS is defined, each public call to malloc, free,
120
etc is surrounded with a lock. By default, this uses a plain
121
pthread mutex, win32 critical section, or a spin-lock if if
122
available for the platform and not disabled by setting
123
USE_SPIN_LOCKS=0. However, if USE_RECURSIVE_LOCKS is defined,
124
recursive versions are used instead (which are not required for
125
base functionality but may be needed in layered extensions).
126
Using a global lock is not especially fast, and can be a major
127
bottleneck. It is designed only to provide minimal protection
128
in concurrent environments, and to provide a basis for
129
extensions. If you are using malloc in a concurrent program,
130
consider instead using nedmalloc
131
(http://www.nedprod.com/programs/portable/nedmalloc/) or
132
ptmalloc (See http://www.malloc.de), which are derived from
133
versions of this malloc.
135
System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
136
This malloc can use unix sbrk or any emulation (invoked using
137
the CALL_MORECORE macro) and/or mmap/munmap or any emulation
138
(invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
139
memory. On most unix systems, it tends to work best if both
140
MORECORE and MMAP are enabled. On Win32, it uses emulations
141
based on VirtualAlloc. It also uses common C library functions
144
Compliance: I believe it is compliant with the Single Unix Specification
145
(See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
148
* Overview of algorithms
150
This is not the fastest, most space-conserving, most portable, or
151
most tunable malloc ever written. However it is among the fastest
152
while also being among the most space-conserving, portable and
153
tunable. Consistent balance across these factors results in a good
154
general-purpose allocator for malloc-intensive programs.
156
In most ways, this malloc is a best-fit allocator. Generally, it
157
chooses the best-fitting existing chunk for a request, with ties
158
broken in approximately least-recently-used order. (This strategy
159
normally maintains low fragmentation.) However, for requests less
160
than 256bytes, it deviates from best-fit when there is not an
161
exactly fitting available chunk by preferring to use space adjacent
162
to that used for the previous small request, as well as by breaking
163
ties in approximately most-recently-used order. (These enhance
164
locality of series of small allocations.) And for very large requests
165
(>= 256Kb by default), it relies on system memory mapping
166
facilities, if supported. (This helps avoid carrying around and
167
possibly fragmenting memory used only for large chunks.)
169
All operations (except malloc_stats and mallinfo) have execution
170
times that are bounded by a constant factor of the number of bits in
171
a size_t, not counting any clearing in calloc or copying in realloc,
172
or actions surrounding MORECORE and MMAP that have times
173
proportional to the number of non-contiguous regions returned by
174
system allocation routines, which is often just 1. In real-time
175
applications, you can optionally suppress segment traversals using
176
NO_SEGMENT_TRAVERSAL, which assures bounded execution even when
177
system allocators return non-contiguous spaces, at the typical
178
expense of carrying around more memory and increased fragmentation.
180
The implementation is not very modular and seriously overuses
181
macros. Perhaps someday all C compilers will do as good a job
182
inlining modular code as can now be done by brute-force expansion,
183
but now, enough of them seem not to.
185
Some compilers issue a lot of warnings about code that is
186
dead/unreachable only on some platforms, and also about intentional
187
uses of negation on unsigned types. All known cases of each can be
190
For a longer but out of date high-level description, see
191
http://gee.cs.oswego.edu/dl/html/malloc.html
194
If MSPACES is defined, then in addition to malloc, free, etc.,
195
this file also defines mspace_malloc, mspace_free, etc. These
196
are versions of malloc routines that take an "mspace" argument
197
obtained using create_mspace, to control all internal bookkeeping.
198
If ONLY_MSPACES is defined, only these versions are compiled.
199
So if you would like to use this allocator for only some allocations,
200
and your system malloc for others, you can compile with
201
ONLY_MSPACES and then do something like...
202
static mspace mymspace = create_mspace(0,0); // for example
203
#define mymalloc(bytes) mspace_malloc(mymspace, bytes)
205
(Note: If you only need one instance of an mspace, you can instead
206
use "USE_DL_PREFIX" to relabel the global malloc.)
208
You can similarly create thread-local allocators by storing
209
mspaces as thread-locals. For example:
210
static __thread mspace tlms = 0;
211
void* tlmalloc(size_t bytes) {
212
if (tlms == 0) tlms = create_mspace(0, 0);
213
return mspace_malloc(tlms, bytes);
215
void tlfree(void* mem) { mspace_free(tlms, mem); }
217
Unless FOOTERS is defined, each mspace is completely independent.
218
You cannot allocate from one and free to another (although
219
conformance is only weakly checked, so usage errors are not always
220
caught). If FOOTERS is defined, then each chunk carries around a tag
221
indicating its originating mspace, and frees are directed to their
222
originating spaces. Normally, this requires use of locks.
224
------------------------- Compile-time options ---------------------------
226
Be careful in setting #define values for numerical constants of type
227
size_t. On some systems, literal values are not automatically extended
228
to size_t precision unless they are explicitly casted. You can also
229
use the symbolic values MAX_SIZE_T, SIZE_T_ONE, etc below.
231
WIN32 default: defined if _WIN32 defined
232
Defining WIN32 sets up defaults for MS environment and compilers.
233
Otherwise defaults are for unix. Beware that there seem to be some
234
cases where this malloc might not be a pure drop-in replacement for
235
Win32 malloc: Random-looking failures from Win32 GDI API's (eg;
236
SetDIBits()) may be due to bugs in some video driver implementations
237
when pixel buffers are malloc()ed, and the region spans more than
238
one VirtualAlloc()ed region. Because dlmalloc uses a small (64Kb)
239
default granularity, pixel buffers may straddle virtual allocation
240
regions more often than when using the Microsoft allocator. You can
241
avoid this by using VirtualAlloc() and VirtualFree() for all pixel
242
buffers rather than using malloc(). If this is not possible,
243
recompile this malloc with a larger DEFAULT_GRANULARITY. Note:
244
in cases where MSC and gcc (cygwin) are known to differ on WIN32,
245
conditions use _MSC_VER to distinguish them.
247
DLMALLOC_EXPORT default: extern
248
Defines how public APIs are declared. If you want to export via a
249
Windows DLL, you might define this as
250
#define DLMALLOC_EXPORT extern __declspec(dllexport)
251
If you want a POSIX ELF shared object, you might use
252
#define DLMALLOC_EXPORT extern __attribute__((visibility("default")))
254
MALLOC_ALIGNMENT default: (size_t)(2 * sizeof(void *))
255
Controls the minimum alignment for malloc'ed chunks. It must be a
256
power of two and at least 8, even on machines for which smaller
257
alignments would suffice. It may be defined as larger than this
258
though. Note however that code and data structures are optimized for
259
the case of 8-byte alignment.
261
MSPACES default: 0 (false)
262
If true, compile in support for independent allocation spaces.
263
This is only supported if HAVE_MMAP is true.
265
ONLY_MSPACES default: 0 (false)
266
If true, only compile in mspace versions, not regular versions.
268
USE_LOCKS default: 0 (false)
269
Causes each call to each public routine to be surrounded with
270
pthread or WIN32 mutex lock/unlock. (If set true, this can be
271
overridden on a per-mspace basis for mspace versions.) If set to a
272
non-zero value other than 1, locks are used, but their
273
implementation is left out, so lock functions must be supplied manually,
276
USE_SPIN_LOCKS default: 1 iff USE_LOCKS and spin locks available
277
If true, uses custom spin locks for locking. This is currently
278
supported only gcc >= 4.1, older gccs on x86 platforms, and recent
279
MS compilers. Otherwise, posix locks or win32 critical sections are
282
USE_RECURSIVE_LOCKS default: not defined
283
If defined nonzero, uses recursive (aka reentrant) locks, otherwise
284
uses plain mutexes. This is not required for malloc proper, but may
285
be needed for layered allocators such as nedmalloc.
287
LOCK_AT_FORK default: not defined
288
If defined nonzero, performs pthread_atfork upon initialization
289
to initialize child lock while holding parent lock. The implementation
290
assumes that pthread locks (not custom locks) are being used. In other
291
cases, you may need to customize the implementation.
294
If true, provide extra checking and dispatching by placing
295
information in the footers of allocated chunks. This adds
296
space and time overhead.
299
If true, omit checks for usage errors and heap space overwrites.
301
USE_DL_PREFIX default: NOT defined
302
Causes compiler to prefix all public routines with the string 'dl'.
303
This can be useful when you only want to use this malloc in one part
304
of a program, using your regular system malloc elsewhere.
306
MALLOC_INSPECT_ALL default: NOT defined
307
If defined, compiles malloc_inspect_all and mspace_inspect_all, that
308
perform traversal of all heap space. Unless access to these
309
functions is otherwise restricted, you probably do not want to
310
include them in secure implementations.
312
ABORT default: defined as abort()
313
Defines how to abort on failed checks. On most systems, a failed
314
check cannot die with an "assert" or even print an informative
315
message, because the underlying print routines in turn call malloc,
316
which will fail again. Generally, the best policy is to simply call
317
abort(). It's not very useful to do more than this because many
318
errors due to overwriting will show up as address faults (null, odd
319
addresses etc) rather than malloc-triggered checks, so will also
320
abort. Also, most compilers know that abort() does not return, so
321
can better optimize code conditionally calling it.
323
PROCEED_ON_ERROR default: defined as 0 (false)
324
Controls whether detected bad addresses cause them to bypassed
325
rather than aborting. If set, detected bad arguments to free and
326
realloc are ignored. And all bookkeeping information is zeroed out
327
upon a detected overwrite of freed heap space, thus losing the
328
ability to ever return it from malloc again, but enabling the
329
application to proceed. If PROCEED_ON_ERROR is defined, the
330
static variable malloc_corruption_error_count is compiled in
331
and can be examined to see if errors have occurred. This option
332
generates slower code than the default abort policy.
334
DEBUG default: NOT defined
335
The DEBUG setting is mainly intended for people trying to modify
336
this code or diagnose problems when porting to new platforms.
337
However, it may also be able to better isolate user errors than just
338
using runtime checks. The assertions in the check routines spell
339
out in more detail the assumptions and invariants underlying the
340
algorithms. The checking is fairly extensive, and will slow down
341
execution noticeably. Calling malloc_stats or mallinfo with DEBUG
342
set will attempt to check every non-mmapped allocated and free chunk
343
in the course of computing the summaries.
345
ABORT_ON_ASSERT_FAILURE default: defined as 1 (true)
346
Debugging assertion failures can be nearly impossible if your
347
version of the assert macro causes malloc to be called, which will
348
lead to a cascade of further failures, blowing the runtime stack.
349
ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
350
which will usually make debugging easier.
352
MALLOC_FAILURE_ACTION default: sets errno to ENOMEM, or no-op on win32
353
The action to take before "return 0" when malloc fails to be able to
354
return memory because there is none available.
356
HAVE_MORECORE default: 1 (true) unless win32 or ONLY_MSPACES
357
True if this system supports sbrk or an emulation of it.
359
MORECORE default: sbrk
360
The name of the sbrk-style system routine to call to obtain more
361
memory. See below for guidance on writing custom MORECORE
362
functions. The type of the argument to sbrk/MORECORE varies across
363
systems. It cannot be size_t, because it supports negative
364
arguments, so it is normally the signed type of the same width as
365
size_t (sometimes declared as "intptr_t"). It doesn't much matter
366
though. Internally, we only call it with arguments less than half
367
the max value of a size_t, which should work across all reasonable
368
possibilities, although sometimes generating compiler warnings.
370
MORECORE_CONTIGUOUS default: 1 (true) if HAVE_MORECORE
371
If true, take advantage of fact that consecutive calls to MORECORE
372
with positive arguments always return contiguous increasing
373
addresses. This is true of unix sbrk. It does not hurt too much to
374
set it true anyway, since malloc copes with non-contiguities.
375
Setting it false when definitely non-contiguous saves time
376
and possibly wasted space it would take to discover this though.
378
MORECORE_CANNOT_TRIM default: NOT defined
379
True if MORECORE cannot release space back to the system when given
380
negative arguments. This is generally necessary only if you are
381
using a hand-crafted MORECORE function that cannot handle negative
384
NO_SEGMENT_TRAVERSAL default: 0
385
If non-zero, suppresses traversals of memory segments
386
returned by either MORECORE or CALL_MMAP. This disables
387
merging of segments that are contiguous, and selectively
388
releasing them to the OS if unused, but bounds execution times.
390
HAVE_MMAP default: 1 (true)
391
True if this system supports mmap or an emulation of it. If so, and
392
HAVE_MORECORE is not true, MMAP is used for all system
393
allocation. If set and HAVE_MORECORE is true as well, MMAP is
394
primarily used to directly allocate very large blocks. It is also
395
used as a backup strategy in cases where MORECORE fails to provide
396
space from system. Note: A single call to MUNMAP is assumed to be
397
able to unmap memory that may have be allocated using multiple calls
398
to MMAP, so long as they are adjacent.
400
HAVE_MREMAP default: 1 on linux, else 0
401
If true realloc() uses mremap() to re-allocate large blocks and
402
extend or shrink allocation spaces.
404
MMAP_CLEARS default: 1 except on WINCE.
405
True if mmap clears memory so calloc doesn't need to. This is true
406
for standard unix mmap using /dev/zero and on WIN32 except for WINCE.
408
USE_BUILTIN_FFS default: 0 (i.e., not used)
409
Causes malloc to use the builtin ffs() function to compute indices.
410
Some compilers may recognize and intrinsify ffs to be faster than the
411
supplied C version. Also, the case of x86 using gcc is special-cased
412
to an asm instruction, so is already as fast as it can be, and so
413
this setting has no effect. Similarly for Win32 under recent MS compilers.
414
(On most x86s, the asm version is only slightly faster than the C version.)
416
malloc_getpagesize default: derive from system includes, or 4096.
417
The system page size. To the extent possible, this malloc manages
418
memory from the system in page-size units. This may be (and
419
usually is) a function rather than a constant. This is ignored
420
if WIN32, where page size is determined using getSystemInfo during
423
USE_DEV_RANDOM default: 0 (i.e., not used)
424
Causes malloc to use /dev/random to initialize secure magic seed for
425
stamping footers. Otherwise, the current time is used.
427
NO_MALLINFO default: 0
428
If defined, don't compile "mallinfo". This can be a simple way
429
of dealing with mismatches between system declarations and
432
MALLINFO_FIELD_TYPE default: size_t
433
The type of the fields in the mallinfo struct. This was originally
434
defined as "int" in SVID etc, but is more usefully defined as
435
size_t. The value is used only if HAVE_USR_INCLUDE_MALLOC_H is not set
437
NO_MALLOC_STATS default: 0
438
If defined, don't compile "malloc_stats". This avoids calls to
439
fprintf and bringing in stdio dependencies you might not want.
441
REALLOC_ZERO_BYTES_FREES default: not defined
442
This should be set if a call to realloc with zero bytes should
443
be the same as a call to free. Some people think it should. Otherwise,
444
since this malloc returns a unique pointer for malloc(0), so does
447
LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
448
LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H, LACKS_ERRNO_H
449
LACKS_STDLIB_H LACKS_SCHED_H LACKS_TIME_H default: NOT defined unless on WIN32
450
Define these if your system does not have these header files.
451
You might need to manually insert some of the declarations they provide.
453
DEFAULT_GRANULARITY default: page size if MORECORE_CONTIGUOUS,
454
system_info.dwAllocationGranularity in WIN32,
456
Also settable using mallopt(M_GRANULARITY, x)
457
The unit for allocating and deallocating memory from the system. On
458
most systems with contiguous MORECORE, there is no reason to
459
make this more than a page. However, systems with MMAP tend to
460
either require or encourage larger granularities. You can increase
461
this value to prevent system allocation functions to be called so
462
often, especially if they are slow. The value must be at least one
463
page and must be a power of two. Setting to 0 causes initialization
464
to either page size or win32 region size. (Note: In previous
465
versions of malloc, the equivalent of this option was called
468
DEFAULT_TRIM_THRESHOLD default: 2MB
469
Also settable using mallopt(M_TRIM_THRESHOLD, x)
470
The maximum amount of unused top-most memory to keep before
471
releasing via malloc_trim in free(). Automatic trimming is mainly
472
useful in long-lived programs using contiguous MORECORE. Because
473
trimming via sbrk can be slow on some systems, and can sometimes be
474
wasteful (in cases where programs immediately afterward allocate
475
more large chunks) the value should be high enough so that your
476
overall system performance would improve by releasing this much
477
memory. As a rough guide, you might set to a value close to the
478
average size of a process (program) running on your system.
479
Releasing this much memory would allow such a process to run in
480
memory. Generally, it is worth tuning trim thresholds when a
481
program undergoes phases where several large chunks are allocated
482
and released in ways that can reuse each other's storage, perhaps
483
mixed with phases where there are no such chunks at all. The trim
484
value must be greater than page size to have any useful effect. To
485
disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
486
some people use of mallocing a huge space and then freeing it at
487
program startup, in an attempt to reserve system memory, doesn't
488
have the intended effect under automatic trimming, since that memory
489
will immediately be returned to the system.
491
DEFAULT_MMAP_THRESHOLD default: 256K
492
Also settable using mallopt(M_MMAP_THRESHOLD, x)
493
The request size threshold for using MMAP to directly service a
494
request. Requests of at least this size that cannot be allocated
495
using already-existing space will be serviced via mmap. (If enough
496
normal freed space already exists it is used instead.) Using mmap
497
segregates relatively large chunks of memory so that they can be
498
individually obtained and released from the host system. A request
499
serviced through mmap is never reused by any other request (at least
500
not directly; the system may just so happen to remap successive
501
requests to the same locations). Segregating space in this way has
502
the benefits that: Mmapped space can always be individually released
503
back to the system, which helps keep the system level memory demands
504
of a long-lived program low. Also, mapped memory doesn't become
505
`locked' between other chunks, as can happen with normally allocated
506
chunks, which means that even trimming via malloc_trim would not
507
release them. However, it has the disadvantage that the space
508
cannot be reclaimed, consolidated, and then used to service later
509
requests, as happens with normal chunks. The advantages of mmap
510
nearly always outweigh disadvantages for "large" chunks, but the
511
value of "large" may vary across systems. The default is an
512
empirically derived value that works well in most systems. You can
513
disable mmap by setting to MAX_SIZE_T.
515
MAX_RELEASE_CHECK_RATE default: 4095 unless not HAVE_MMAP
516
The number of consolidated frees between checks to release
517
unused segments when freeing. When using non-contiguous segments,
518
especially with multiple mspaces, checking only for topmost space
519
doesn't always suffice to trigger trimming. To compensate for this,
520
free() will, with a period of MAX_RELEASE_CHECK_RATE (or the
521
current number of segments, if greater) try to release unused
522
segments to the OS when freeing chunks that result in
523
consolidation. The best value for this parameter is a compromise
524
between slowing down frees with relatively costly checks that
525
rarely trigger versus holding on to unused memory. To effectively
526
disable, set to MAX_SIZE_T. This may lead to a very slight speed
527
improvement at the expense of carrying around more memory.
530
/* Version identifier to allow people to support multiple versions */
531
#ifndef DLMALLOC_VERSION
532
#define DLMALLOC_VERSION 20806
533
#endif /* DLMALLOC_VERSION */
536
#define DLMALLOC_EXPORT __attribute__((__weak__, __visibility__("default")))
539
#ifndef DLMALLOC_EXPORT
540
#define DLMALLOC_EXPORT extern
548
#define LACKS_FCNTL_H
550
#endif /* _WIN32_WCE */
553
#define WIN32_LEAN_AND_MEAN
557
#define HAVE_MORECORE 0
558
#define LACKS_UNISTD_H
559
#define LACKS_SYS_PARAM_H
560
#define LACKS_SYS_MMAN_H
561
#define LACKS_STRING_H
562
#define LACKS_STRINGS_H
563
#define LACKS_SYS_TYPES_H
564
#define LACKS_ERRNO_H
565
#define LACKS_SCHED_H
566
#ifndef MALLOC_FAILURE_ACTION
567
#define MALLOC_FAILURE_ACTION
568
#endif /* MALLOC_FAILURE_ACTION */
570
#ifdef _WIN32_WCE /* WINCE reportedly does not clear */
571
#define MMAP_CLEARS 0
573
#define MMAP_CLEARS 1
574
#endif /* _WIN32_WCE */
575
#endif /*MMAP_CLEARS */
578
#if defined(DARWIN) || defined(_DARWIN)
579
/* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
580
#ifndef HAVE_MORECORE
581
#define HAVE_MORECORE 0
583
/* OSX allocators provide 16 byte alignment */
584
#ifndef MALLOC_ALIGNMENT
585
#define MALLOC_ALIGNMENT ((size_t)16U)
587
#endif /* HAVE_MORECORE */
590
#ifndef LACKS_SYS_TYPES_H
591
#include <sys/types.h> /* For size_t */
592
#endif /* LACKS_SYS_TYPES_H */
594
/* The maximum possible size_t value has all bits set */
595
#define MAX_SIZE_T (~(size_t)0)
597
#ifndef USE_LOCKS /* ensure true if spin or recursive locks set */
598
#define USE_LOCKS ((defined(USE_SPIN_LOCKS) && USE_SPIN_LOCKS != 0) || \
599
(defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0))
600
#endif /* USE_LOCKS */
602
#if USE_LOCKS /* Spin locks for gcc >= 4.1, older gcc on x86, MSC >= 1310 */
603
#if ((defined(__GNUC__) && \
604
((__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)) || \
605
defined(__i386__) || defined(__x86_64__))) || \
606
(defined(_MSC_VER) && _MSC_VER>=1310))
607
#ifndef USE_SPIN_LOCKS
608
#define USE_SPIN_LOCKS 1
609
#endif /* USE_SPIN_LOCKS */
611
#error "USE_SPIN_LOCKS defined without implementation"
612
#endif /* ... locks available... */
613
#elif !defined(USE_SPIN_LOCKS)
614
#define USE_SPIN_LOCKS 0
615
#endif /* USE_LOCKS */
618
#define ONLY_MSPACES 0
619
#endif /* ONLY_MSPACES */
623
#else /* ONLY_MSPACES */
625
#endif /* ONLY_MSPACES */
627
#ifndef MALLOC_ALIGNMENT
628
#define MALLOC_ALIGNMENT ((size_t)(2 * sizeof(void *)))
629
#endif /* MALLOC_ALIGNMENT */
634
#define ABORT abort()
636
#ifndef ABORT_ON_ASSERT_FAILURE
637
#define ABORT_ON_ASSERT_FAILURE 1
638
#endif /* ABORT_ON_ASSERT_FAILURE */
639
#ifndef PROCEED_ON_ERROR
640
#define PROCEED_ON_ERROR 0
641
#endif /* PROCEED_ON_ERROR */
645
#endif /* INSECURE */
646
#ifndef MALLOC_INSPECT_ALL
647
#define MALLOC_INSPECT_ALL 0
648
#endif /* MALLOC_INSPECT_ALL */
651
* mmap uses malloc, so malloc can't use mmap
659
#endif /* HAVE_MMAP */
661
#define MMAP_CLEARS 1
662
#endif /* MMAP_CLEARS */
665
#define HAVE_MREMAP 1
666
#define _GNU_SOURCE /* Turns on mremap() definition */
668
#define HAVE_MREMAP 0
670
#endif /* HAVE_MREMAP */
671
#ifndef MALLOC_FAILURE_ACTION
672
#define MALLOC_FAILURE_ACTION errno = ENOMEM;
673
#endif /* MALLOC_FAILURE_ACTION */
674
#ifndef HAVE_MORECORE
676
#define HAVE_MORECORE 0
677
#else /* ONLY_MSPACES */
678
#define HAVE_MORECORE 1
679
#endif /* ONLY_MSPACES */
680
#endif /* HAVE_MORECORE */
682
#define MORECORE_CONTIGUOUS 0
683
#else /* !HAVE_MORECORE */
684
#define MORECORE_DEFAULT sbrk
685
#ifndef MORECORE_CONTIGUOUS
686
#define MORECORE_CONTIGUOUS 1
687
#endif /* MORECORE_CONTIGUOUS */
688
#endif /* HAVE_MORECORE */
689
#ifndef DEFAULT_GRANULARITY
690
#if (MORECORE_CONTIGUOUS || defined(WIN32))
691
#define DEFAULT_GRANULARITY (0) /* 0 means to compute in init_mparams */
692
#else /* MORECORE_CONTIGUOUS */
693
#define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
694
#endif /* MORECORE_CONTIGUOUS */
695
#endif /* DEFAULT_GRANULARITY */
696
#ifndef DEFAULT_TRIM_THRESHOLD
697
#ifndef MORECORE_CANNOT_TRIM
698
#define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
699
#else /* MORECORE_CANNOT_TRIM */
700
#define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
701
#endif /* MORECORE_CANNOT_TRIM */
702
#endif /* DEFAULT_TRIM_THRESHOLD */
703
#ifndef DEFAULT_MMAP_THRESHOLD
705
#define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
706
#else /* HAVE_MMAP */
707
#define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
708
#endif /* HAVE_MMAP */
709
#endif /* DEFAULT_MMAP_THRESHOLD */
710
#ifndef MAX_RELEASE_CHECK_RATE
712
#define MAX_RELEASE_CHECK_RATE 4095
714
#define MAX_RELEASE_CHECK_RATE MAX_SIZE_T
715
#endif /* HAVE_MMAP */
716
#endif /* MAX_RELEASE_CHECK_RATE */
717
#ifndef USE_BUILTIN_FFS
718
#define USE_BUILTIN_FFS 0
719
#endif /* USE_BUILTIN_FFS */
720
#ifndef USE_DEV_RANDOM
721
#define USE_DEV_RANDOM 0
722
#endif /* USE_DEV_RANDOM */
724
#define NO_MALLINFO 0
725
#endif /* NO_MALLINFO */
726
#ifndef MALLINFO_FIELD_TYPE
727
#define MALLINFO_FIELD_TYPE size_t
728
#endif /* MALLINFO_FIELD_TYPE */
729
#ifndef NO_MALLOC_STATS
730
#define NO_MALLOC_STATS 0
731
#endif /* NO_MALLOC_STATS */
732
#ifndef NO_SEGMENT_TRAVERSAL
733
#define NO_SEGMENT_TRAVERSAL 0
734
#endif /* NO_SEGMENT_TRAVERSAL */
737
mallopt tuning options. SVID/XPG defines four standard parameter
738
numbers for mallopt, normally defined in malloc.h. None of these
739
are used in this malloc, so setting them has no effect. But this
740
malloc does support the following options.
743
#define M_TRIM_THRESHOLD (-1)
744
#define M_GRANULARITY (-2)
745
#define M_MMAP_THRESHOLD (-3)
747
/* ------------------------ Mallinfo declarations ------------------------ */
751
This version of malloc supports the standard SVID/XPG mallinfo
752
routine that returns a struct containing usage properties and
753
statistics. It should work on any system that has a
754
/usr/include/malloc.h defining struct mallinfo. The main
755
declaration needed is the mallinfo struct that is returned (by-copy)
756
by mallinfo(). The malloinfo struct contains a bunch of fields that
757
are not even meaningful in this version of malloc. These fields are
758
are instead filled by mallinfo() with other numbers that might be of
761
HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
762
/usr/include/malloc.h file that includes a declaration of struct
763
mallinfo. If so, it is included; else a compliant version is
764
declared below. These must be precisely the same for mallinfo() to
765
work. The original SVID version of this struct, defined on most
766
systems with mallinfo, declares all fields as ints. But some others
767
define as unsigned long. If your system defines the fields using a
768
type of different width than listed here, you MUST #include your
769
system version and #define HAVE_USR_INCLUDE_MALLOC_H.
772
/* #define HAVE_USR_INCLUDE_MALLOC_H */
774
#ifdef HAVE_USR_INCLUDE_MALLOC_H
775
#include "/usr/include/malloc.h"
776
#else /* HAVE_USR_INCLUDE_MALLOC_H */
777
#ifndef STRUCT_MALLINFO_DECLARED
778
/* HP-UX (and others?) redefines mallinfo unless _STRUCT_MALLINFO is defined */
779
#define _STRUCT_MALLINFO
780
#define STRUCT_MALLINFO_DECLARED 1
782
MALLINFO_FIELD_TYPE arena; /* non-mmapped space allocated from system */
783
MALLINFO_FIELD_TYPE ordblks; /* number of free chunks */
784
MALLINFO_FIELD_TYPE smblks; /* always 0 */
785
MALLINFO_FIELD_TYPE hblks; /* always 0 */
786
MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */
787
MALLINFO_FIELD_TYPE usmblks; /* maximum total allocated space */
788
MALLINFO_FIELD_TYPE fsmblks; /* always 0 */
789
MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
790
MALLINFO_FIELD_TYPE fordblks; /* total free space */
791
MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
793
#endif /* STRUCT_MALLINFO_DECLARED */
794
#endif /* HAVE_USR_INCLUDE_MALLOC_H */
795
#endif /* NO_MALLINFO */
798
Try to persuade compilers to inline. The most critical functions for
799
inlining are defined as macros, so these aren't used for them.
803
#if defined(__GNUC__)
804
#define FORCEINLINE __inline __attribute__ ((always_inline))
805
#elif defined(_MSC_VER)
806
#define FORCEINLINE __forceinline
810
#if defined(__GNUC__)
811
#define NOINLINE __attribute__ ((noinline))
812
#elif defined(_MSC_VER)
813
#define NOINLINE __declspec(noinline)
822
#define FORCEINLINE inline
824
#endif /* __cplusplus */
831
/* ------------------- Declarations of public routines ------------------- */
833
#ifndef USE_DL_PREFIX
834
#define dlcalloc calloc
836
#define dlmalloc malloc
837
#define dlmemalign memalign
838
#define dlposix_memalign posix_memalign
839
#define dlrealloc realloc
840
#define dlrealloc_in_place realloc_in_place
841
#define dlvalloc valloc
842
#define dlpvalloc pvalloc
843
#define dlmallinfo mallinfo
844
#define dlmallopt mallopt
845
#define dlmalloc_trim malloc_trim
846
#define dlmalloc_stats malloc_stats
847
#define dlmalloc_usable_size malloc_usable_size
848
#define dlmalloc_footprint malloc_footprint
849
#define dlmalloc_max_footprint malloc_max_footprint
850
#define dlmalloc_footprint_limit malloc_footprint_limit
851
#define dlmalloc_set_footprint_limit malloc_set_footprint_limit
852
#define dlmalloc_inspect_all malloc_inspect_all
853
#define dlindependent_calloc independent_calloc
854
#define dlindependent_comalloc independent_comalloc
855
#define dlbulk_free bulk_free
856
#endif /* USE_DL_PREFIX */
860
Returns a pointer to a newly allocated chunk of at least n bytes, or
861
null if no space is available, in which case errno is set to ENOMEM
864
If n is zero, malloc returns a minimum-sized chunk. (The minimum
865
size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
866
systems.) Note that size_t is an unsigned type, so calls with
867
arguments that would be negative if signed are interpreted as
868
requests for huge amounts of space, which will often fail. The
869
maximum supported value of n differs across systems, but is in all
870
cases less than the maximum representable value of a size_t.
872
DLMALLOC_EXPORT void* dlmalloc(size_t);
876
Releases the chunk of memory pointed to by p, that had been previously
877
allocated using malloc or a related routine such as realloc.
878
It has no effect if p is null. If p was not malloced or already
879
freed, free(p) will by default cause the current program to abort.
881
DLMALLOC_EXPORT void dlfree(void*);
884
calloc(size_t n_elements, size_t element_size);
885
Returns a pointer to n_elements * element_size bytes, with all locations
888
DLMALLOC_EXPORT void* dlcalloc(size_t, size_t);
891
realloc(void* p, size_t n)
892
Returns a pointer to a chunk of size n that contains the same data
893
as does chunk p up to the minimum of (n, p's size) bytes, or null
894
if no space is available.
896
The returned pointer may or may not be the same as p. The algorithm
897
prefers extending p in most cases when possible, otherwise it
898
employs the equivalent of a malloc-copy-free sequence.
900
If p is null, realloc is equivalent to malloc.
902
If space is not available, realloc returns null, errno is set (if on
903
ANSI) and p is NOT freed.
905
if n is for fewer bytes than already held by p, the newly unused
906
space is lopped off and freed if possible. realloc with a size
907
argument of zero (re)allocates a minimum-sized chunk.
909
The old unix realloc convention of allowing the last-free'd chunk
910
to be used as an argument to realloc is not supported.
912
DLMALLOC_EXPORT void* dlrealloc(void*, size_t);
915
realloc_in_place(void* p, size_t n)
916
Resizes the space allocated for p to size n, only if this can be
917
done without moving p (i.e., only if there is adjacent space
918
available if n is greater than p's current allocated size, or n is
919
less than or equal to p's size). This may be used instead of plain
920
realloc if an alternative allocation strategy is needed upon failure
921
to expand space; for example, reallocation of a buffer that must be
922
memory-aligned or cleared. You can use realloc_in_place to trigger
923
these alternatives only when needed.
925
Returns p if successful; otherwise null.
927
DLMALLOC_EXPORT void* dlrealloc_in_place(void*, size_t);
930
memalign(size_t alignment, size_t n);
931
Returns a pointer to a newly allocated chunk of n bytes, aligned
932
in accord with the alignment argument.
934
The alignment argument should be a power of two. If the argument is
935
not a power of two, the nearest greater power is used.
936
8-byte alignment is guaranteed by normal malloc calls, so don't
937
bother calling memalign with an argument of 8 or less.
939
Overreliance on memalign is a sure way to fragment space.
941
DLMALLOC_EXPORT void* dlmemalign(size_t, size_t);
944
int posix_memalign(void** pp, size_t alignment, size_t n);
945
Allocates a chunk of n bytes, aligned in accord with the alignment
946
argument. Differs from memalign only in that it (1) assigns the
947
allocated memory to *pp rather than returning it, (2) fails and
948
returns EINVAL if the alignment is not a power of two (3) fails and
949
returns ENOMEM if memory cannot be allocated.
951
DLMALLOC_EXPORT int dlposix_memalign(void**, size_t, size_t);
955
Equivalent to memalign(pagesize, n), where pagesize is the page
956
size of the system. If the pagesize is unknown, 4096 is used.
958
DLMALLOC_EXPORT void* dlvalloc(size_t);
961
mallopt(int parameter_number, int parameter_value)
962
Sets tunable parameters The format is to provide a
963
(parameter-number, parameter-value) pair. mallopt then sets the
964
corresponding parameter to the argument value if it can (i.e., so
965
long as the value is meaningful), and returns 1 if successful else
966
0. To workaround the fact that mallopt is specified to use int,
967
not size_t parameters, the value -1 is specially treated as the
968
maximum unsigned size_t value.
970
SVID/XPG/ANSI defines four standard param numbers for mallopt,
971
normally defined in malloc.h. None of these are use in this malloc,
972
so setting them has no effect. But this malloc also supports other
973
options in mallopt. See below for details. Briefly, supported
974
parameters are as follows (listed defaults are for "typical"
977
Symbol param # default allowed param values
978
M_TRIM_THRESHOLD -1 2*1024*1024 any (-1 disables)
979
M_GRANULARITY -2 page size any power of 2 >= page size
980
M_MMAP_THRESHOLD -3 256*1024 any (or 0 if no MMAP support)
982
DLMALLOC_EXPORT int dlmallopt(int, int);
986
Returns the number of bytes obtained from the system. The total
987
number of bytes allocated by malloc, realloc etc., is less than this
988
value. Unlike mallinfo, this function returns only a precomputed
989
result, so can be called frequently to monitor memory consumption.
990
Even if locks are otherwise defined, this function does not use them,
991
so results might not be up to date.
993
DLMALLOC_EXPORT size_t dlmalloc_footprint(void);
996
malloc_max_footprint();
997
Returns the maximum number of bytes obtained from the system. This
998
value will be greater than current footprint if deallocated space
999
has been reclaimed by the system. The peak number of bytes allocated
1000
by malloc, realloc etc., is less than this value. Unlike mallinfo,
1001
this function returns only a precomputed result, so can be called
1002
frequently to monitor memory consumption. Even if locks are
1003
otherwise defined, this function does not use them, so results might
1006
DLMALLOC_EXPORT size_t dlmalloc_max_footprint(void);
1009
malloc_footprint_limit();
1010
Returns the number of bytes that the heap is allowed to obtain from
1011
the system, returning the last value returned by
1012
malloc_set_footprint_limit, or the maximum size_t value if
1013
never set. The returned value reflects a permission. There is no
1014
guarantee that this number of bytes can actually be obtained from
1017
DLMALLOC_EXPORT size_t dlmalloc_footprint_limit();
1020
malloc_set_footprint_limit();
1021
Sets the maximum number of bytes to obtain from the system, causing
1022
failure returns from malloc and related functions upon attempts to
1023
exceed this value. The argument value may be subject to page
1024
rounding to an enforceable limit; this actual value is returned.
1025
Using an argument of the maximum possible size_t effectively
1026
disables checks. If the argument is less than or equal to the
1027
current malloc_footprint, then all future allocations that require
1028
additional system memory will fail. However, invocation cannot
1029
retroactively deallocate existing used memory.
1031
DLMALLOC_EXPORT size_t dlmalloc_set_footprint_limit(size_t bytes);
1033
#if MALLOC_INSPECT_ALL
1035
malloc_inspect_all(void(*handler)(void *start,
1038
void* callback_arg),
1040
Traverses the heap and calls the given handler for each managed
1041
region, skipping all bytes that are (or may be) used for bookkeeping
1042
purposes. Traversal does not include include chunks that have been
1043
directly memory mapped. Each reported region begins at the start
1044
address, and continues up to but not including the end address. The
1045
first used_bytes of the region contain allocated data. If
1046
used_bytes is zero, the region is unallocated. The handler is
1047
invoked with the given callback argument. If locks are defined, they
1048
are held during the entire traversal. It is a bad idea to invoke
1049
other malloc functions from within the handler.
1051
For example, to count the number of in-use chunks with size greater
1052
than 1000, you could write:
1053
static int count = 0;
1054
void count_chunks(void* start, void* end, size_t used, void* arg) {
1055
if (used >= 1000) ++count;
1058
malloc_inspect_all(count_chunks, NULL);
1060
malloc_inspect_all is compiled only if MALLOC_INSPECT_ALL is defined.
1062
DLMALLOC_EXPORT void dlmalloc_inspect_all(void(*handler)(void*, void *, size_t, void*),
1065
#endif /* MALLOC_INSPECT_ALL */
1070
Returns (by copy) a struct containing various summary statistics:
1072
arena: current total non-mmapped bytes allocated from system
1073
ordblks: the number of free chunks
1074
smblks: always zero.
1075
hblks: current number of mmapped regions
1076
hblkhd: total bytes held in mmapped regions
1077
usmblks: the maximum total allocated space. This will be greater
1078
than current total if trimming has occurred.
1079
fsmblks: always zero
1080
uordblks: current total allocated space (normal or mmapped)
1081
fordblks: total free space
1082
keepcost: the maximum number of bytes that could ideally be released
1083
back to system via malloc_trim. ("ideally" means that
1084
it ignores page restrictions etc.)
1086
Because these fields are ints, but internal bookkeeping may
1087
be kept as longs, the reported values may wrap around zero and
1090
DLMALLOC_EXPORT struct mallinfo dlmallinfo(void);
1091
#endif /* NO_MALLINFO */
1094
independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
1096
independent_calloc is similar to calloc, but instead of returning a
1097
single cleared space, it returns an array of pointers to n_elements
1098
independent elements that can hold contents of size elem_size, each
1099
of which starts out cleared, and can be independently freed,
1100
realloc'ed etc. The elements are guaranteed to be adjacently
1101
allocated (this is not guaranteed to occur with multiple callocs or
1102
mallocs), which may also improve cache locality in some
1105
The "chunks" argument is optional (i.e., may be null, which is
1106
probably the most typical usage). If it is null, the returned array
1107
is itself dynamically allocated and should also be freed when it is
1108
no longer needed. Otherwise, the chunks array must be of at least
1109
n_elements in length. It is filled in with the pointers to the
1112
In either case, independent_calloc returns this pointer array, or
1113
null if the allocation failed. If n_elements is zero and "chunks"
1114
is null, it returns a chunk representing an array with zero elements
1115
(which should be freed if not wanted).
1117
Each element must be freed when it is no longer needed. This can be
1118
done all at once using bulk_free.
1120
independent_calloc simplifies and speeds up implementations of many
1121
kinds of pools. It may also be useful when constructing large data
1122
structures that initially have a fixed number of fixed-sized nodes,
1123
but the number is not known at compile time, and some of the nodes
1124
may later need to be freed. For example:
1126
struct Node { int item; struct Node* next; };
1128
struct Node* build_list() {
1130
int n = read_number_of_nodes_needed();
1131
if (n <= 0) return 0;
1132
pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
1133
if (pool == 0) die();
1134
// organize into a linked list...
1135
struct Node* first = pool[0];
1136
for (i = 0; i < n-1; ++i)
1137
pool[i]->next = pool[i+1];
1138
free(pool); // Can now free the array (or not, if it is needed later)
1142
DLMALLOC_EXPORT void** dlindependent_calloc(size_t, size_t, void**);
1145
independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
1147
independent_comalloc allocates, all at once, a set of n_elements
1148
chunks with sizes indicated in the "sizes" array. It returns
1149
an array of pointers to these elements, each of which can be
1150
independently freed, realloc'ed etc. The elements are guaranteed to
1151
be adjacently allocated (this is not guaranteed to occur with
1152
multiple callocs or mallocs), which may also improve cache locality
1153
in some applications.
1155
The "chunks" argument is optional (i.e., may be null). If it is null
1156
the returned array is itself dynamically allocated and should also
1157
be freed when it is no longer needed. Otherwise, the chunks array
1158
must be of at least n_elements in length. It is filled in with the
1159
pointers to the chunks.
1161
In either case, independent_comalloc returns this pointer array, or
1162
null if the allocation failed. If n_elements is zero and chunks is
1163
null, it returns a chunk representing an array with zero elements
1164
(which should be freed if not wanted).
1166
Each element must be freed when it is no longer needed. This can be
1167
done all at once using bulk_free.
1169
independent_comallac differs from independent_calloc in that each
1170
element may have a different size, and also that it does not
1171
automatically clear elements.
1173
independent_comalloc can be used to speed up allocation in cases
1174
where several structs or objects must always be allocated at the
1175
same time. For example:
1180
void send_message(char* msg) {
1181
int msglen = strlen(msg);
1182
size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1184
if (independent_comalloc(3, sizes, chunks) == 0)
1186
struct Head* head = (struct Head*)(chunks[0]);
1187
char* body = (char*)(chunks[1]);
1188
struct Foot* foot = (struct Foot*)(chunks[2]);
1192
In general though, independent_comalloc is worth using only for
1193
larger values of n_elements. For small values, you probably won't
1194
detect enough difference from series of malloc calls to bother.
1196
Overuse of independent_comalloc can increase overall memory usage,
1197
since it cannot reuse existing noncontiguous small chunks that
1198
might be available for some of the elements.
1200
DLMALLOC_EXPORT void** dlindependent_comalloc(size_t, size_t*, void**);
1203
bulk_free(void* array[], size_t n_elements)
1204
Frees and clears (sets to null) each non-null pointer in the given
1205
array. This is likely to be faster than freeing them one-by-one.
1206
If footers are used, pointers that have been allocated in different
1207
mspaces are not freed or cleared, and the count of all such pointers
1208
is returned. For large arrays of pointers with poor locality, it
1209
may be worthwhile to sort this array before calling bulk_free.
1211
DLMALLOC_EXPORT size_t dlbulk_free(void**, size_t n_elements);
1215
Equivalent to valloc(minimum-page-that-holds(n)), that is,
1216
round up n to nearest pagesize.
1218
DLMALLOC_EXPORT void* dlpvalloc(size_t);
1221
malloc_trim(size_t pad);
1223
If possible, gives memory back to the system (via negative arguments
1224
to sbrk) if there is unused memory at the `high' end of the malloc
1225
pool or in unused MMAP segments. You can call this after freeing
1226
large blocks of memory to potentially reduce the system-level memory
1227
requirements of a program. However, it cannot guarantee to reduce
1228
memory. Under some allocation patterns, some large free blocks of
1229
memory will be locked between two used chunks, so they cannot be
1230
given back to the system.
1232
The `pad' argument to malloc_trim represents the amount of free
1233
trailing space to leave untrimmed. If this argument is zero, only
1234
the minimum amount of memory to maintain internal data structures
1235
will be left. Non-zero arguments can be supplied to maintain enough
1236
trailing space to service future expected allocations without having
1237
to re-obtain memory from the system.
1239
Malloc_trim returns 1 if it actually released any memory, else 0.
1241
DLMALLOC_EXPORT int dlmalloc_trim(size_t);
1245
Prints on stderr the amount of space obtained from the system (both
1246
via sbrk and mmap), the maximum amount (which may be more than
1247
current if malloc_trim and/or munmap got called), and the current
1248
number of bytes allocated via malloc (or realloc, etc) but not yet
1249
freed. Note that this is the number of bytes allocated, not the
1250
number requested. It will be larger than the number requested
1251
because of alignment and bookkeeping overhead. Because it includes
1252
alignment wastage as being in use, this figure may be greater than
1253
zero even when no user-level chunks are allocated.
1255
The reported current and maximum system memory can be inaccurate if
1256
a program makes other calls to system memory allocation functions
1257
(normally sbrk) outside of malloc.
1259
malloc_stats prints only the most commonly interesting statistics.
1260
More information can be obtained by calling mallinfo.
1262
DLMALLOC_EXPORT void dlmalloc_stats(void);
1265
malloc_usable_size(void* p);
1267
Returns the number of bytes you can actually use in
1268
an allocated chunk, which may be more than you requested (although
1269
often not) due to alignment and minimum size constraints.
1270
You can use this many bytes without worrying about
1271
overwriting other allocated objects. This is not a particularly great
1272
programming practice. malloc_usable_size can be more useful in
1273
debugging and assertions, for example:
1276
assert(malloc_usable_size(p) >= 256);
1278
/* XXX EMSCRIPTEN: mark for export (and therefore weak) */
1279
DLMALLOC_EXPORT size_t dlmalloc_usable_size(void*);
1281
#endif /* ONLY_MSPACES */
1286
mspace is an opaque type representing an independent
1287
region of space that supports mspace_malloc, etc.
1289
typedef void* mspace;
1292
create_mspace creates and returns a new independent space with the
1293
given initial capacity, or, if 0, the default granularity size. It
1294
returns null if there is no system memory available to create the
1295
space. If argument locked is non-zero, the space uses a separate
1296
lock to control access. The capacity of the space will grow
1297
dynamically as needed to service mspace_malloc requests. You can
1298
control the sizes of incremental increases of this space by
1299
compiling with a different DEFAULT_GRANULARITY or dynamically
1300
setting with mallopt(M_GRANULARITY, value).
1302
DLMALLOC_EXPORT mspace create_mspace(size_t capacity, int locked);
1305
destroy_mspace destroys the given space, and attempts to return all
1306
of its memory back to the system, returning the total number of
1307
bytes freed. After destruction, the results of access to all memory
1308
used by the space become undefined.
1310
DLMALLOC_EXPORT size_t destroy_mspace(mspace msp);
1313
create_mspace_with_base uses the memory supplied as the initial base
1314
of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
1315
space is used for bookkeeping, so the capacity must be at least this
1316
large. (Otherwise 0 is returned.) When this initial space is
1317
exhausted, additional memory will be obtained from the system.
1318
Destroying this space will deallocate all additionally allocated
1319
space (if possible) but not the initial base.
1321
DLMALLOC_EXPORT mspace create_mspace_with_base(void* base, size_t capacity, int locked);
1324
mspace_track_large_chunks controls whether requests for large chunks
1325
are allocated in their own untracked mmapped regions, separate from
1326
others in this mspace. By default large chunks are not tracked,
1327
which reduces fragmentation. However, such chunks are not
1328
necessarily released to the system upon destroy_mspace. Enabling
1329
tracking by setting to true may increase fragmentation, but avoids
1330
leakage when relying on destroy_mspace to release all memory
1331
allocated using this space. The function returns the previous
1334
DLMALLOC_EXPORT int mspace_track_large_chunks(mspace msp, int enable);
1338
mspace_malloc behaves as malloc, but operates within
1341
DLMALLOC_EXPORT void* mspace_malloc(mspace msp, size_t bytes);
1344
mspace_free behaves as free, but operates within
1347
If compiled with FOOTERS==1, mspace_free is not actually needed.
1348
free may be called instead of mspace_free because freed chunks from
1349
any space are handled by their originating spaces.
1351
DLMALLOC_EXPORT void mspace_free(mspace msp, void* mem);
1354
mspace_realloc behaves as realloc, but operates within
1357
If compiled with FOOTERS==1, mspace_realloc is not actually
1358
needed. realloc may be called instead of mspace_realloc because
1359
realloced chunks from any space are handled by their originating
1362
DLMALLOC_EXPORT void* mspace_realloc(mspace msp, void* mem, size_t newsize);
1365
mspace_calloc behaves as calloc, but operates within
1368
DLMALLOC_EXPORT void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
1371
mspace_memalign behaves as memalign, but operates within
1374
DLMALLOC_EXPORT void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);
1377
mspace_independent_calloc behaves as independent_calloc, but
1378
operates within the given space.
1380
DLMALLOC_EXPORT void** mspace_independent_calloc(mspace msp, size_t n_elements,
1381
size_t elem_size, void* chunks[]);
1384
mspace_independent_comalloc behaves as independent_comalloc, but
1385
operates within the given space.
1387
DLMALLOC_EXPORT void** mspace_independent_comalloc(mspace msp, size_t n_elements,
1388
size_t sizes[], void* chunks[]);
1391
mspace_footprint() returns the number of bytes obtained from the
1392
system for this space.
1394
DLMALLOC_EXPORT size_t mspace_footprint(mspace msp);
1397
mspace_max_footprint() returns the peak number of bytes obtained from the
1398
system for this space.
1400
DLMALLOC_EXPORT size_t mspace_max_footprint(mspace msp);
1405
mspace_mallinfo behaves as mallinfo, but reports properties of
1408
DLMALLOC_EXPORT struct mallinfo mspace_mallinfo(mspace msp);
1409
#endif /* NO_MALLINFO */
1412
malloc_usable_size(void* p) behaves the same as malloc_usable_size;
1414
DLMALLOC_EXPORT size_t mspace_usable_size(const void* mem);
1417
mspace_malloc_stats behaves as malloc_stats, but reports
1418
properties of the given space.
1420
DLMALLOC_EXPORT void mspace_malloc_stats(mspace msp);
1423
mspace_trim behaves as malloc_trim, but
1424
operates within the given space.
1426
DLMALLOC_EXPORT int mspace_trim(mspace msp, size_t pad);
1429
An alias for mallopt.
1431
DLMALLOC_EXPORT int mspace_mallopt(int, int);
1433
#endif /* MSPACES */
1436
} /* end of extern "C" */
1437
#endif /* __cplusplus */
1440
========================================================================
1441
To make a fully customizable malloc.h header file, cut everything
1442
above this line, put into file malloc.h, edit to suit, and #include it
1443
on the next line, as well as in programs that use this malloc.
1444
========================================================================
1447
/* #include "malloc.h" */
1449
/*------------------------------ internal #includes ---------------------- */
1452
#pragma warning( disable : 4146 ) /* no "unsigned" warnings */
1453
#endif /* _MSC_VER */
1454
#if !NO_MALLOC_STATS
1455
#include <stdio.h> /* for printing in malloc_stats */
1456
#endif /* NO_MALLOC_STATS */
1457
#ifndef LACKS_ERRNO_H
1458
#include <errno.h> /* for MALLOC_FAILURE_ACTION */
1459
#endif /* LACKS_ERRNO_H */
1461
#if ABORT_ON_ASSERT_FAILURE
1463
#define assert(x) if(!(x)) ABORT
1464
#else /* ABORT_ON_ASSERT_FAILURE */
1466
#endif /* ABORT_ON_ASSERT_FAILURE */
1473
#if !defined(WIN32) && !defined(LACKS_TIME_H)
1474
#include <time.h> /* for magic initialization */
1476
#ifndef LACKS_STDLIB_H
1477
#include <stdlib.h> /* for abort() */
1478
#endif /* LACKS_STDLIB_H */
1479
#ifndef LACKS_STRING_H
1480
#include <string.h> /* for memset etc */
1481
#endif /* LACKS_STRING_H */
1483
#ifndef LACKS_STRINGS_H
1484
#include <strings.h> /* for ffs */
1485
#endif /* LACKS_STRINGS_H */
1486
#endif /* USE_BUILTIN_FFS */
1488
#ifndef LACKS_SYS_MMAN_H
1489
/* On some versions of linux, mremap decl in mman.h needs __USE_GNU set */
1490
#if (defined(linux) && !defined(__USE_GNU))
1492
#include <sys/mman.h> /* for mmap */
1495
#include <sys/mman.h> /* for mmap */
1497
#endif /* LACKS_SYS_MMAN_H */
1498
#ifndef LACKS_FCNTL_H
1500
#endif /* LACKS_FCNTL_H */
1501
#endif /* HAVE_MMAP */
1502
#ifndef LACKS_UNISTD_H
1503
#include <unistd.h> /* for sbrk, sysconf */
1504
#else /* LACKS_UNISTD_H */
1505
#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
1506
extern void* sbrk(ptrdiff_t);
1507
#endif /* FreeBSD etc */
1508
#endif /* LACKS_UNISTD_H */
1510
/* Declarations for locking */
1513
#if defined (__SVR4) && defined (__sun) /* solaris */
1515
#elif !defined(LACKS_SCHED_H)
1517
#endif /* solaris or LACKS_SCHED_H */
1518
#if (defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0) || !USE_SPIN_LOCKS
1519
#include <pthread.h>
1520
#endif /* USE_RECURSIVE_LOCKS ... */
1521
#elif defined(_MSC_VER)
1523
/* These are already defined on AMD64 builds */
1526
#endif /* __cplusplus */
1527
LONG __cdecl _InterlockedCompareExchange(LONG volatile *Dest, LONG Exchange, LONG Comp);
1528
LONG __cdecl _InterlockedExchange(LONG volatile *Target, LONG Value);
1531
#endif /* __cplusplus */
1532
#endif /* _M_AMD64 */
1533
#pragma intrinsic (_InterlockedCompareExchange)
1534
#pragma intrinsic (_InterlockedExchange)
1535
#define interlockedcompareexchange _InterlockedCompareExchange
1536
#define interlockedexchange _InterlockedExchange
1537
#elif defined(WIN32) && defined(__GNUC__)
1538
#define interlockedcompareexchange(a, b, c) __sync_val_compare_and_swap(a, c, b)
1539
#define interlockedexchange __sync_lock_test_and_set
1541
#else /* USE_LOCKS */
1542
#endif /* USE_LOCKS */
1544
#ifndef LOCK_AT_FORK
1545
#define LOCK_AT_FORK 0
1548
/* Declarations for bit scanning on win32 */
1549
#if defined(_MSC_VER) && _MSC_VER>=1300
1550
#ifndef BitScanForward /* Try to avoid pulling in WinNT.h */
1553
#endif /* __cplusplus */
1554
unsigned char _BitScanForward(unsigned long *index, unsigned long mask);
1555
unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
1558
#endif /* __cplusplus */
1560
#define BitScanForward _BitScanForward
1561
#define BitScanReverse _BitScanReverse
1562
#pragma intrinsic(_BitScanForward)
1563
#pragma intrinsic(_BitScanReverse)
1564
#endif /* BitScanForward */
1565
#endif /* defined(_MSC_VER) && _MSC_VER>=1300 */
1568
#ifndef malloc_getpagesize
1569
# ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
1570
# ifndef _SC_PAGE_SIZE
1571
# define _SC_PAGE_SIZE _SC_PAGESIZE
1574
# ifdef _SC_PAGE_SIZE
1575
# define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
1577
# if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
1578
extern size_t getpagesize();
1579
# define malloc_getpagesize getpagesize()
1581
# ifdef WIN32 /* use supplied emulation of getpagesize */
1582
# define malloc_getpagesize getpagesize()
1584
# ifndef LACKS_SYS_PARAM_H
1585
# include <sys/param.h>
1587
# ifdef EXEC_PAGESIZE
1588
# define malloc_getpagesize EXEC_PAGESIZE
1592
# define malloc_getpagesize NBPG
1594
# define malloc_getpagesize (NBPG * CLSIZE)
1598
# define malloc_getpagesize NBPC
1601
# define malloc_getpagesize PAGESIZE
1602
# else /* just guess */
1603
# define malloc_getpagesize ((size_t)4096U)
1614
/* ------------------- size_t and alignment properties -------------------- */
1616
/* The byte and bit size of a size_t */
1617
#define SIZE_T_SIZE (sizeof(size_t))
1618
#define SIZE_T_BITSIZE (sizeof(size_t) << 3)
1620
/* Some constants coerced to size_t */
1621
/* Annoying but necessary to avoid errors on some platforms */
1622
#define SIZE_T_ZERO ((size_t)0)
1623
#define SIZE_T_ONE ((size_t)1)
1624
#define SIZE_T_TWO ((size_t)2)
1625
#define SIZE_T_FOUR ((size_t)4)
1626
#define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)
1627
#define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)
1628
#define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
1629
#define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
1631
/* The bit mask value corresponding to MALLOC_ALIGNMENT */
1632
#define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)
1634
/* True if address a has acceptable alignment */
1635
#define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
1637
/* the number of bytes to offset an address to align it */
1638
#define align_offset(A)\
1639
((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
1640
((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
1642
/* -------------------------- MMAP preliminaries ------------------------- */
1645
If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
1646
checks to fail so compiler optimizer can delete code rather than
1647
using so many "#if"s.
1651
/* MORECORE and MMAP must return MFAIL on failure */
1652
#define MFAIL ((void*)(MAX_SIZE_T))
1653
#define CMFAIL ((char*)(MFAIL)) /* defined for convenience */
1658
#define MUNMAP_DEFAULT(a, s) munmap((a), (s))
1659
#define MMAP_PROT (PROT_READ|PROT_WRITE)
1660
#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1661
#define MAP_ANONYMOUS MAP_ANON
1662
#endif /* MAP_ANON */
1663
#ifdef MAP_ANONYMOUS
1664
#define MMAP_FLAGS (MAP_PRIVATE|MAP_ANONYMOUS)
1665
#define MMAP_DEFAULT(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
1666
#else /* MAP_ANONYMOUS */
1668
Nearly all versions of mmap support MAP_ANONYMOUS, so the following
1669
is unlikely to be needed, but is supplied just in case.
1671
#define MMAP_FLAGS (MAP_PRIVATE)
1672
static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1673
#define MMAP_DEFAULT(s) ((dev_zero_fd < 0) ? \
1674
(dev_zero_fd = open("/dev/zero", O_RDWR), \
1675
mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
1676
mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
1677
#endif /* MAP_ANONYMOUS */
1679
#define DIRECT_MMAP_DEFAULT(s) MMAP_DEFAULT(s)
1683
/* Win32 MMAP via VirtualAlloc */
1684
static FORCEINLINE void* win32mmap(size_t size) {
1685
void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
1686
return (ptr != 0)? ptr: MFAIL;
1689
/* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
1690
static FORCEINLINE void* win32direct_mmap(size_t size) {
1691
void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
1693
return (ptr != 0)? ptr: MFAIL;
1696
/* This function supports releasing coalesed segments */
1697
static FORCEINLINE int win32munmap(void* ptr, size_t size) {
1698
MEMORY_BASIC_INFORMATION minfo;
1699
char* cptr = (char*)ptr;
1701
if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
1703
if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
1704
minfo.State != MEM_COMMIT || minfo.RegionSize > size)
1706
if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
1708
cptr += minfo.RegionSize;
1709
size -= minfo.RegionSize;
1714
#define MMAP_DEFAULT(s) win32mmap(s)
1715
#define MUNMAP_DEFAULT(a, s) win32munmap((a), (s))
1716
#define DIRECT_MMAP_DEFAULT(s) win32direct_mmap(s)
1718
#endif /* HAVE_MMAP */
1722
#define MREMAP_DEFAULT(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
1724
#endif /* HAVE_MREMAP */
1727
* Define CALL_MORECORE
1731
#define CALL_MORECORE(S) MORECORE(S)
1732
#else /* MORECORE */
1733
#define CALL_MORECORE(S) MORECORE_DEFAULT(S)
1734
#endif /* MORECORE */
1735
#else /* HAVE_MORECORE */
1736
#define CALL_MORECORE(S) MFAIL
1737
#endif /* HAVE_MORECORE */
1740
* Define CALL_MMAP/CALL_MUNMAP/CALL_DIRECT_MMAP
1743
#define USE_MMAP_BIT (SIZE_T_ONE)
1746
#define CALL_MMAP(s) MMAP(s)
1748
#define CALL_MMAP(s) MMAP_DEFAULT(s)
1751
#define CALL_MUNMAP(a, s) MUNMAP((a), (s))
1753
#define CALL_MUNMAP(a, s) MUNMAP_DEFAULT((a), (s))
1756
#define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
1757
#else /* DIRECT_MMAP */
1758
#define CALL_DIRECT_MMAP(s) DIRECT_MMAP_DEFAULT(s)
1759
#endif /* DIRECT_MMAP */
1760
#else /* HAVE_MMAP */
1761
#define USE_MMAP_BIT (SIZE_T_ZERO)
1763
#define MMAP(s) MFAIL
1764
#define MUNMAP(a, s) (-1)
1765
#define DIRECT_MMAP(s) MFAIL
1766
#define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
1767
#define CALL_MMAP(s) MMAP(s)
1768
#define CALL_MUNMAP(a, s) MUNMAP((a), (s))
1769
#endif /* HAVE_MMAP */
1772
* Define CALL_MREMAP
1774
#if HAVE_MMAP && HAVE_MREMAP
1776
#define CALL_MREMAP(addr, osz, nsz, mv) MREMAP((addr), (osz), (nsz), (mv))
1778
#define CALL_MREMAP(addr, osz, nsz, mv) MREMAP_DEFAULT((addr), (osz), (nsz), (mv))
1780
#else /* HAVE_MMAP && HAVE_MREMAP */
1781
#define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
1782
#endif /* HAVE_MMAP && HAVE_MREMAP */
1784
/* mstate bit set if continguous morecore disabled or failed */
1785
#define USE_NONCONTIGUOUS_BIT (4U)
1787
/* segment bit set in create_mspace_with_base */
1788
#define EXTERN_BIT (8U)
1791
/* --------------------------- Lock preliminaries ------------------------ */
1794
When locks are defined, there is one global lock, plus
1795
one per-mspace lock.
1797
The global lock_ensures that mparams.magic and other unique
1798
mparams values are initialized only once. It also protects
1799
sequences of calls to MORECORE. In many cases sys_alloc requires
1800
two calls, that should not be interleaved with calls by other
1801
threads. This does not protect against direct calls to MORECORE
1802
by other threads not using this lock, so there is still code to
1803
cope the best we can on interference.
1805
Per-mspace locks surround calls to malloc, free, etc.
1806
By default, locks are simple non-reentrant mutexes.
1808
Because lock-protected regions generally have bounded times, it is
1809
OK to use the supplied simple spinlocks. Spinlocks are likely to
1810
improve performance for lightly contended applications, but worsen
1811
performance under heavy contention.
1813
If USE_LOCKS is > 1, the definitions of lock routines here are
1814
bypassed, in which case you will need to define the type MLOCK_T,
1815
and at least INITIAL_LOCK, DESTROY_LOCK, ACQUIRE_LOCK, RELEASE_LOCK
1816
and TRY_LOCK. You must also declare a
1817
static MLOCK_T malloc_global_mutex = { initialization values };.
1822
#define USE_LOCK_BIT (0U)
1823
#define INITIAL_LOCK(l) (0)
1824
#define DESTROY_LOCK(l) (0)
1825
#define ACQUIRE_MALLOC_GLOBAL_LOCK()
1826
#define RELEASE_MALLOC_GLOBAL_LOCK()
1830
/* ----------------------- User-defined locks ------------------------ */
1831
/* Define your own lock implementation here */
1832
/* #define INITIAL_LOCK(lk) ... */
1833
/* #define DESTROY_LOCK(lk) ... */
1834
/* #define ACQUIRE_LOCK(lk) ... */
1835
/* #define RELEASE_LOCK(lk) ... */
1836
/* #define TRY_LOCK(lk) ... */
1837
/* static MLOCK_T malloc_global_mutex = ... */
1839
#elif USE_SPIN_LOCKS
1841
/* First, define CAS_LOCK and CLEAR_LOCK on ints */
1842
/* Note CAS_LOCK defined to return 0 on success */
1844
#if defined(__GNUC__)&& (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1))
1845
#define CAS_LOCK(sl) __sync_lock_test_and_set(sl, 1)
1846
#define CLEAR_LOCK(sl) __sync_lock_release(sl)
1848
#elif (defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)))
1849
/* Custom spin locks for older gcc on x86 */
1850
static FORCEINLINE int x86_cas_lock(int *sl) {
1854
__asm__ __volatile__ ("lock; cmpxchgl %1, %2"
1856
: "r" (val), "m" (*(sl)), "0"(cmp)
1861
static FORCEINLINE void x86_clear_lock(int* sl) {
1865
__asm__ __volatile__ ("lock; xchgl %0, %1"
1867
: "m" (*(sl)), "0"(prev)
1871
#define CAS_LOCK(sl) x86_cas_lock(sl)
1872
#define CLEAR_LOCK(sl) x86_clear_lock(sl)
1874
#else /* Win32 MSC */
1875
#define CAS_LOCK(sl) interlockedexchange(sl, (LONG)1)
1876
#define CLEAR_LOCK(sl) interlockedexchange (sl, (LONG)0)
1878
#endif /* ... gcc spins locks ... */
1880
/* How to yield for a spin lock */
1881
#define SPINS_PER_YIELD 63
1882
#if defined(_MSC_VER)
1883
#define SLEEP_EX_DURATION 50 /* delay for yield/sleep */
1884
#define SPIN_LOCK_YIELD SleepEx(SLEEP_EX_DURATION, FALSE)
1885
#elif defined (__SVR4) && defined (__sun) /* solaris */
1886
#define SPIN_LOCK_YIELD thr_yield();
1887
#elif !defined(LACKS_SCHED_H)
1888
#define SPIN_LOCK_YIELD sched_yield();
1890
#define SPIN_LOCK_YIELD
1891
#endif /* ... yield ... */
1893
#if !defined(USE_RECURSIVE_LOCKS) || USE_RECURSIVE_LOCKS == 0
1894
/* Plain spin locks use single word (embedded in malloc_states) */
1895
static int spin_acquire_lock(int *sl) {
1897
while (*(volatile int *)sl != 0 || CAS_LOCK(sl)) {
1898
if ((++spins & SPINS_PER_YIELD) == 0) {
1906
#define TRY_LOCK(sl) !CAS_LOCK(sl)
1907
#define RELEASE_LOCK(sl) CLEAR_LOCK(sl)
1908
#define ACQUIRE_LOCK(sl) (CAS_LOCK(sl)? spin_acquire_lock(sl) : 0)
1909
#define INITIAL_LOCK(sl) (*sl = 0)
1910
#define DESTROY_LOCK(sl) (0)
1911
static MLOCK_T malloc_global_mutex = 0;
1913
#else /* USE_RECURSIVE_LOCKS */
1914
/* types for lock owners */
1916
#define THREAD_ID_T DWORD
1917
#define CURRENT_THREAD GetCurrentThreadId()
1918
#define EQ_OWNER(X,Y) ((X) == (Y))
1921
Note: the following assume that pthread_t is a type that can be
1922
initialized to (casted) zero. If this is not the case, you will need to
1923
somehow redefine these or not use spin locks.
1925
#define THREAD_ID_T pthread_t
1926
#define CURRENT_THREAD pthread_self()
1927
#define EQ_OWNER(X,Y) pthread_equal(X, Y)
1930
struct malloc_recursive_lock {
1933
THREAD_ID_T threadid;
1936
#define MLOCK_T struct malloc_recursive_lock
1937
static MLOCK_T malloc_global_mutex = { 0, 0, (THREAD_ID_T)0};
1939
static FORCEINLINE void recursive_release_lock(MLOCK_T *lk) {
1940
assert(lk->sl != 0);
1942
CLEAR_LOCK(&lk->sl);
1946
static FORCEINLINE int recursive_acquire_lock(MLOCK_T *lk) {
1947
THREAD_ID_T mythreadid = CURRENT_THREAD;
1950
if (*((volatile int *)(&lk->sl)) == 0) {
1951
if (!CAS_LOCK(&lk->sl)) {
1952
lk->threadid = mythreadid;
1957
else if (EQ_OWNER(lk->threadid, mythreadid)) {
1961
if ((++spins & SPINS_PER_YIELD) == 0) {
1967
static FORCEINLINE int recursive_try_lock(MLOCK_T *lk) {
1968
THREAD_ID_T mythreadid = CURRENT_THREAD;
1969
if (*((volatile int *)(&lk->sl)) == 0) {
1970
if (!CAS_LOCK(&lk->sl)) {
1971
lk->threadid = mythreadid;
1976
else if (EQ_OWNER(lk->threadid, mythreadid)) {
1983
#define RELEASE_LOCK(lk) recursive_release_lock(lk)
1984
#define TRY_LOCK(lk) recursive_try_lock(lk)
1985
#define ACQUIRE_LOCK(lk) recursive_acquire_lock(lk)
1986
#define INITIAL_LOCK(lk) ((lk)->threadid = (THREAD_ID_T)0, (lk)->sl = 0, (lk)->c = 0)
1987
#define DESTROY_LOCK(lk) (0)
1988
#endif /* USE_RECURSIVE_LOCKS */
1990
#elif defined(WIN32) /* Win32 critical sections */
1991
#define MLOCK_T CRITICAL_SECTION
1992
#define ACQUIRE_LOCK(lk) (EnterCriticalSection(lk), 0)
1993
#define RELEASE_LOCK(lk) LeaveCriticalSection(lk)
1994
#define TRY_LOCK(lk) TryEnterCriticalSection(lk)
1995
#define INITIAL_LOCK(lk) (!InitializeCriticalSectionAndSpinCount((lk), 0x80000000|4000))
1996
#define DESTROY_LOCK(lk) (DeleteCriticalSection(lk), 0)
1997
#define NEED_GLOBAL_LOCK_INIT
1999
static MLOCK_T malloc_global_mutex;
2000
static volatile LONG malloc_global_mutex_status;
2002
/* Use spin loop to initialize global lock */
2003
static void init_malloc_global_mutex() {
2005
long stat = malloc_global_mutex_status;
2008
/* transition to < 0 while initializing, then to > 0) */
2010
interlockedcompareexchange(&malloc_global_mutex_status, (LONG)-1, (LONG)0) == 0) {
2011
InitializeCriticalSection(&malloc_global_mutex);
2012
interlockedexchange(&malloc_global_mutex_status, (LONG)1);
2019
#else /* pthreads-based locks */
2020
#define MLOCK_T pthread_mutex_t
2021
#define ACQUIRE_LOCK(lk) pthread_mutex_lock(lk)
2022
#define RELEASE_LOCK(lk) pthread_mutex_unlock(lk)
2023
#define TRY_LOCK(lk) (!pthread_mutex_trylock(lk))
2024
#define INITIAL_LOCK(lk) pthread_init_lock(lk)
2025
#define DESTROY_LOCK(lk) pthread_mutex_destroy(lk)
2027
#if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0 && defined(linux) && !defined(PTHREAD_MUTEX_RECURSIVE)
2028
/* Cope with old-style linux recursive lock initialization by adding */
2029
/* skipped internal declaration from pthread.h */
2030
extern int pthread_mutexattr_setkind_np __P ((pthread_mutexattr_t *__attr,
2032
#define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP
2033
#define pthread_mutexattr_settype(x,y) pthread_mutexattr_setkind_np(x,y)
2034
#endif /* USE_RECURSIVE_LOCKS ... */
2036
static MLOCK_T malloc_global_mutex = PTHREAD_MUTEX_INITIALIZER;
2038
static int pthread_init_lock (MLOCK_T *lk) {
2039
pthread_mutexattr_t attr;
2040
if (pthread_mutexattr_init(&attr)) return 1;
2041
#if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0
2042
if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1;
2044
if (pthread_mutex_init(lk, &attr)) return 1;
2045
if (pthread_mutexattr_destroy(&attr)) return 1;
2049
#endif /* ... lock types ... */
2051
/* Common code for all lock types */
2052
#define USE_LOCK_BIT (2U)
2054
#ifndef ACQUIRE_MALLOC_GLOBAL_LOCK
2055
#define ACQUIRE_MALLOC_GLOBAL_LOCK() ACQUIRE_LOCK(&malloc_global_mutex);
2058
#ifndef RELEASE_MALLOC_GLOBAL_LOCK
2059
#define RELEASE_MALLOC_GLOBAL_LOCK() RELEASE_LOCK(&malloc_global_mutex);
2062
#endif /* USE_LOCKS */
2064
/* ----------------------- Chunk representations ------------------------ */
2067
(The following includes lightly edited explanations by Colin Plumb.)
2069
The malloc_chunk declaration below is misleading (but accurate and
2070
necessary). It declares a "view" into memory allowing access to
2071
necessary fields at known offsets from a given base.
2073
Chunks of memory are maintained using a `boundary tag' method as
2074
originally described by Knuth. (See the paper by Paul Wilson
2075
ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
2076
techniques.) Sizes of free chunks are stored both in the front of
2077
each chunk and at the end. This makes consolidating fragmented
2078
chunks into bigger chunks fast. The head fields also hold bits
2079
representing whether chunks are free or in use.
2081
Here are some pictures to make it clearer. They are "exploded" to
2082
show that the state of a chunk can be thought of as extending from
2083
the high 31 bits of the head field of its header through the
2084
prev_foot and PINUSE_BIT bit of the following chunk header.
2086
A chunk that's in use looks like:
2088
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2089
| Size of previous chunk (if P = 0) |
2090
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2091
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
2092
| Size of this chunk 1| +-+
2093
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2099
+- size - sizeof(size_t) available payload bytes -+
2103
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2104
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
2105
| Size of next chunk (may or may not be in use) | +-+
2106
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2108
And if it's free, it looks like this:
2111
| User payload (must be in use, or we would have merged!) |
2112
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2113
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
2114
| Size of this chunk 0| +-+
2115
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2117
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2119
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2121
+- size - sizeof(struct chunk) unused bytes -+
2123
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2124
| Size of this chunk |
2125
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2126
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
2127
| Size of next chunk (must be in use, or we would have merged)| +-+
2128
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2132
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2135
Note that since we always merge adjacent free chunks, the chunks
2136
adjacent to a free chunk must be in use.
2138
Given a pointer to a chunk (which can be derived trivially from the
2139
payload pointer) we can, in O(1) time, find out whether the adjacent
2140
chunks are free, and if so, unlink them from the lists that they
2141
are on and merge them with the current chunk.
2143
Chunks always begin on even word boundaries, so the mem portion
2144
(which is returned to the user) is also on an even word boundary, and
2145
thus at least double-word aligned.
2147
The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
2148
chunk size (which is always a multiple of two words), is an in-use
2149
bit for the *previous* chunk. If that bit is *clear*, then the
2150
word before the current chunk size contains the previous chunk
2151
size, and can be used to find the front of the previous chunk.
2152
The very first chunk allocated always has this bit set, preventing
2153
access to non-existent (or non-owned) memory. If pinuse is set for
2154
any given chunk, then you CANNOT determine the size of the
2155
previous chunk, and might even get a memory addressing fault when
2158
The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
2159
the chunk size redundantly records whether the current chunk is
2160
inuse (unless the chunk is mmapped). This redundancy enables usage
2161
checks within free and realloc, and reduces indirection when freeing
2162
and consolidating chunks.
2164
Each freshly allocated chunk must have both cinuse and pinuse set.
2165
That is, each allocated chunk borders either a previously allocated
2166
and still in-use chunk, or the base of its memory arena. This is
2167
ensured by making all allocations from the `lowest' part of any
2168
found chunk. Further, no free chunk physically borders another one,
2169
so each free chunk is known to be preceded and followed by either
2170
inuse chunks or the ends of memory.
2172
Note that the `foot' of the current chunk is actually represented
2173
as the prev_foot of the NEXT chunk. This makes it easier to
2174
deal with alignments etc but can be very confusing when trying
2175
to extend or adapt this code.
2177
The exceptions to all this are
2179
1. The special chunk `top' is the top-most available chunk (i.e.,
2180
the one bordering the end of available memory). It is treated
2181
specially. Top is never included in any bin, is used only if
2182
no other chunk is available, and is released back to the
2183
system if it is very large (see M_TRIM_THRESHOLD). In effect,
2184
the top chunk is treated as larger (and thus less well
2185
fitting) than any other available chunk. The top chunk
2186
doesn't update its trailing size field since there is no next
2187
contiguous chunk that would have to index off it. However,
2188
space is still allocated for it (TOP_FOOT_SIZE) to enable
2189
separation or merging when space is extended.
2191
3. Chunks allocated via mmap, have both cinuse and pinuse bits
2192
cleared in their head fields. Because they are allocated
2193
one-by-one, each must carry its own prev_foot field, which is
2194
also used to hold the offset this chunk has within its mmapped
2195
region, which is needed to preserve alignment. Each mmapped
2196
chunk is trailed by the first two fields of a fake next-chunk
2197
for sake of usage checks.
2201
struct malloc_chunk {
2202
size_t prev_foot; /* Size of previous chunk (if free). */
2203
size_t head; /* Size and inuse bits. */
2204
struct malloc_chunk* fd; /* double links -- used only if free. */
2205
struct malloc_chunk* bk;
2208
typedef struct malloc_chunk mchunk;
2209
typedef struct malloc_chunk* mchunkptr;
2210
typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */
2211
typedef unsigned int bindex_t; /* Described below */
2212
typedef unsigned int binmap_t; /* Described below */
2213
typedef unsigned int flag_t; /* The type of various bit flag sets */
2215
/* ------------------- Chunks sizes and alignments ----------------------- */
2217
#define MCHUNK_SIZE (sizeof(mchunk))
2220
#define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
2222
#define CHUNK_OVERHEAD (SIZE_T_SIZE)
2223
#endif /* FOOTERS */
2225
/* MMapped chunks need a second word of overhead ... */
2226
#define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
2227
/* ... and additional padding for fake next-chunk at foot */
2228
#define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES)
2230
/* The smallest size we can malloc is an aligned minimal chunk */
2231
#define MIN_CHUNK_SIZE \
2232
((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
2234
/* conversion from malloc headers to user pointers, and back */
2235
#define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))
2236
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
2237
/* chunk associated with aligned address A */
2238
#define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))
2240
/* Bounds on request (not chunk) sizes. */
2241
#define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)
2242
#define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
2244
/* pad request bytes into a usable size */
2245
#define pad_request(req) \
2246
(((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
2248
/* pad request, checking for minimum (but not maximum) */
2249
#define request2size(req) \
2250
(((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
2253
/* ------------------ Operations on head and foot fields ----------------- */
2256
The head field of a chunk is or'ed with PINUSE_BIT when previous
2257
adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
2258
use, unless mmapped, in which case both bits are cleared.
2260
FLAG4_BIT is not used by this malloc, but might be useful in extensions.
2263
#define PINUSE_BIT (SIZE_T_ONE)
2264
#define CINUSE_BIT (SIZE_T_TWO)
2265
#define FLAG4_BIT (SIZE_T_FOUR)
2266
#define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)
2267
#define FLAG_BITS (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT)
2269
/* Head value for fenceposts */
2270
#define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)
2272
/* extraction of fields from head words */
2273
#define cinuse(p) ((p)->head & CINUSE_BIT)
2274
#define pinuse(p) ((p)->head & PINUSE_BIT)
2275
#define flag4inuse(p) ((p)->head & FLAG4_BIT)
2276
#define is_inuse(p) (((p)->head & INUSE_BITS) != PINUSE_BIT)
2277
#define is_mmapped(p) (((p)->head & INUSE_BITS) == 0)
2279
#define chunksize(p) ((p)->head & ~(FLAG_BITS))
2281
#define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)
2282
#define set_flag4(p) ((p)->head |= FLAG4_BIT)
2283
#define clear_flag4(p) ((p)->head &= ~FLAG4_BIT)
2285
/* Treat space at ptr +/- offset as a chunk */
2286
#define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
2287
#define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
2289
/* Ptr to next or previous physical malloc_chunk. */
2290
#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS)))
2291
#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
2293
/* extract next chunk's pinuse bit */
2294
#define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)
2296
/* Get/set size at footer */
2297
#define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)
2298
#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
2300
/* Set size, pinuse bit, and foot */
2301
#define set_size_and_pinuse_of_free_chunk(p, s)\
2302
((p)->head = (s|PINUSE_BIT), set_foot(p, s))
2304
/* Set size, pinuse bit, foot, and clear next pinuse */
2305
#define set_free_with_pinuse(p, s, n)\
2306
(clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
2308
/* Get the internal overhead associated with chunk p */
2309
#define overhead_for(p)\
2310
(is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
2312
/* Return true if malloced space is not necessarily cleared */
2314
#define calloc_must_clear(p) (!is_mmapped(p))
2315
#else /* MMAP_CLEARS */
2316
#define calloc_must_clear(p) (1)
2317
#endif /* MMAP_CLEARS */
2319
/* ---------------------- Overlaid data structures ----------------------- */
2322
When chunks are not in use, they are treated as nodes of either
2325
"Small" chunks are stored in circular doubly-linked lists, and look
2328
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2329
| Size of previous chunk |
2330
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2331
`head:' | Size of chunk, in bytes |P|
2332
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2333
| Forward pointer to next chunk in list |
2334
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2335
| Back pointer to previous chunk in list |
2336
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2337
| Unused space (may be 0 bytes long) .
2340
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2341
`foot:' | Size of chunk, in bytes |
2342
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2344
Larger chunks are kept in a form of bitwise digital trees (aka
2345
tries) keyed on chunksizes. Because malloc_tree_chunks are only for
2346
free chunks greater than 256 bytes, their size doesn't impose any
2347
constraints on user chunk sizes. Each node looks like:
2349
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2350
| Size of previous chunk |
2351
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2352
`head:' | Size of chunk, in bytes |P|
2353
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2354
| Forward pointer to next chunk of same size |
2355
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2356
| Back pointer to previous chunk of same size |
2357
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2358
| Pointer to left child (child[0]) |
2359
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2360
| Pointer to right child (child[1]) |
2361
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2362
| Pointer to parent |
2363
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2364
| bin index of this chunk |
2365
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2368
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2369
`foot:' | Size of chunk, in bytes |
2370
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2372
Each tree holding treenodes is a tree of unique chunk sizes. Chunks
2373
of the same size are arranged in a circularly-linked list, with only
2374
the oldest chunk (the next to be used, in our FIFO ordering)
2375
actually in the tree. (Tree members are distinguished by a non-null
2376
parent pointer.) If a chunk with the same size an an existing node
2377
is inserted, it is linked off the existing node using pointers that
2378
work in the same way as fd/bk pointers of small chunks.
2380
Each tree contains a power of 2 sized range of chunk sizes (the
2381
smallest is 0x100 <= x < 0x180), which is is divided in half at each
2382
tree level, with the chunks in the smaller half of the range (0x100
2383
<= x < 0x140 for the top nose) in the left subtree and the larger
2384
half (0x140 <= x < 0x180) in the right subtree. This is, of course,
2385
done by inspecting individual bits.
2387
Using these rules, each node's left subtree contains all smaller
2388
sizes than its right subtree. However, the node at the root of each
2389
subtree has no particular ordering relationship to either. (The
2390
dividing line between the subtree sizes is based on trie relation.)
2391
If we remove the last chunk of a given size from the interior of the
2392
tree, we need to replace it with a leaf node. The tree ordering
2393
rules permit a node to be replaced by any leaf below it.
2395
The smallest chunk in a tree (a common operation in a best-fit
2396
allocator) can be found by walking a path to the leftmost leaf in
2397
the tree. Unlike a usual binary tree, where we follow left child
2398
pointers until we reach a null, here we follow the right child
2399
pointer any time the left one is null, until we reach a leaf with
2400
both child pointers null. The smallest chunk in the tree will be
2401
somewhere along that path.
2403
The worst case number of steps to add, find, or remove a node is
2404
bounded by the number of bits differentiating chunks within
2405
bins. Under current bin calculations, this ranges from 6 up to 21
2406
(for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
2407
is of course much better.
2410
struct malloc_tree_chunk {
2411
/* The first four fields must be compatible with malloc_chunk */
2414
struct malloc_tree_chunk* fd;
2415
struct malloc_tree_chunk* bk;
2417
struct malloc_tree_chunk* child[2];
2418
struct malloc_tree_chunk* parent;
2422
typedef struct malloc_tree_chunk tchunk;
2423
typedef struct malloc_tree_chunk* tchunkptr;
2424
typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
2426
/* A little helper macro for trees */
2427
#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
2429
/* ----------------------------- Segments -------------------------------- */
2432
Each malloc space may include non-contiguous segments, held in a
2433
list headed by an embedded malloc_segment record representing the
2434
top-most space. Segments also include flags holding properties of
2435
the space. Large chunks that are directly allocated by mmap are not
2436
included in this list. They are instead independently created and
2437
destroyed without otherwise keeping track of them.
2439
Segment management mainly comes into play for spaces allocated by
2440
MMAP. Any call to MMAP might or might not return memory that is
2441
adjacent to an existing segment. MORECORE normally contiguously
2442
extends the current space, so this space is almost always adjacent,
2443
which is simpler and faster to deal with. (This is why MORECORE is
2444
used preferentially to MMAP when both are available -- see
2445
sys_alloc.) When allocating using MMAP, we don't use any of the
2446
hinting mechanisms (inconsistently) supported in various
2447
implementations of unix mmap, or distinguish reserving from
2448
committing memory. Instead, we just ask for space, and exploit
2449
contiguity when we get it. It is probably possible to do
2450
better than this on some systems, but no general scheme seems
2451
to be significantly better.
2453
Management entails a simpler variant of the consolidation scheme
2454
used for chunks to reduce fragmentation -- new adjacent memory is
2455
normally prepended or appended to an existing segment. However,
2456
there are limitations compared to chunk consolidation that mostly
2457
reflect the fact that segment processing is relatively infrequent
2458
(occurring only when getting memory from system) and that we
2459
don't expect to have huge numbers of segments:
2461
* Segments are not indexed, so traversal requires linear scans. (It
2462
would be possible to index these, but is not worth the extra
2463
overhead and complexity for most programs on most platforms.)
2464
* New segments are only appended to old ones when holding top-most
2465
memory; if they cannot be prepended to others, they are held in
2468
Except for the top-most segment of an mstate, each segment record
2469
is kept at the tail of its segment. Segments are added by pushing
2470
segment records onto the list headed by &mstate.seg for the
2473
Segment flags control allocation/merge/deallocation policies:
2474
* If EXTERN_BIT set, then we did not allocate this segment,
2475
and so should not try to deallocate or merge with others.
2476
(This currently holds only for the initial segment passed
2477
into create_mspace_with_base.)
2478
* If USE_MMAP_BIT set, the segment may be merged with
2479
other surrounding mmapped segments and trimmed/de-allocated
2481
* If neither bit is set, then the segment was obtained using
2482
MORECORE so can be merged with surrounding MORECORE'd segments
2483
and deallocated/trimmed using MORECORE with negative arguments.
2486
struct malloc_segment {
2487
char* base; /* base address */
2488
size_t size; /* allocated size */
2489
struct malloc_segment* next; /* ptr to next segment */
2490
flag_t sflags; /* mmap and extern flag */
2493
#define is_mmapped_segment(S) ((S)->sflags & USE_MMAP_BIT)
2494
#define is_extern_segment(S) ((S)->sflags & EXTERN_BIT)
2496
typedef struct malloc_segment msegment;
2497
typedef struct malloc_segment* msegmentptr;
2499
/* ---------------------------- malloc_state ----------------------------- */
2502
A malloc_state holds all of the bookkeeping for a space.
2503
The main fields are:
2506
The topmost chunk of the currently active segment. Its size is
2507
cached in topsize. The actual size of topmost space is
2508
topsize+TOP_FOOT_SIZE, which includes space reserved for adding
2509
fenceposts and segment records if necessary when getting more
2510
space from the system. The size at which to autotrim top is
2511
cached from mparams in trim_check, except that it is disabled if
2514
Designated victim (dv)
2515
This is the preferred chunk for servicing small requests that
2516
don't have exact fits. It is normally the chunk split off most
2517
recently to service another small request. Its size is cached in
2518
dvsize. The link fields of this chunk are not maintained since it
2519
is not kept in a bin.
2522
An array of bin headers for free chunks. These bins hold chunks
2523
with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
2524
chunks of all the same size, spaced 8 bytes apart. To simplify
2525
use in double-linked lists, each bin header acts as a malloc_chunk
2526
pointing to the real first node, if it exists (else pointing to
2527
itself). This avoids special-casing for headers. But to avoid
2528
waste, we allocate only the fd/bk pointers of bins, and then use
2529
repositioning tricks to treat these as the fields of a chunk.
2532
Treebins are pointers to the roots of trees holding a range of
2533
sizes. There are 2 equally spaced treebins for each power of two
2534
from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
2538
There is one bit map for small bins ("smallmap") and one for
2539
treebins ("treemap). Each bin sets its bit when non-empty, and
2540
clears the bit when empty. Bit operations are then used to avoid
2541
bin-by-bin searching -- nearly all "search" is done without ever
2542
looking at bins that won't be selected. The bit maps
2543
conservatively use 32 bits per map word, even if on 64bit system.
2544
For a good description of some of the bit-based techniques used
2545
here, see Henry S. Warren Jr's book "Hacker's Delight" (and
2546
supplement at http://hackersdelight.org/). Many of these are
2547
intended to reduce the branchiness of paths through malloc etc, as
2548
well as to reduce the number of memory locations read or written.
2551
A list of segments headed by an embedded malloc_segment record
2552
representing the initial space.
2554
Address check support
2555
The least_addr field is the least address ever obtained from
2556
MORECORE or MMAP. Attempted frees and reallocs of any address less
2557
than this are trapped (unless INSECURE is defined).
2560
A cross-check field that should always hold same value as mparams.magic.
2562
Max allowed footprint
2563
The maximum allowed bytes to allocate from system (zero means no limit)
2566
Bits recording whether to use MMAP, locks, or contiguous MORECORE
2569
Each space keeps track of current and maximum system memory
2570
obtained via MORECORE or MMAP.
2573
Fields holding the amount of unused topmost memory that should trigger
2574
trimming, and a counter to force periodic scanning to release unused
2575
non-topmost segments.
2578
If USE_LOCKS is defined, the "mutex" lock is acquired and released
2579
around every public call using this mspace.
2582
A void* pointer and a size_t field that can be used to help implement
2583
extensions to this malloc.
2586
/* Bin types, widths and sizes */
2587
#define NSMALLBINS (32U)
2588
#define NTREEBINS (32U)
2589
#define SMALLBIN_SHIFT (3U)
2590
#define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)
2591
#define TREEBIN_SHIFT (8U)
2592
#define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)
2593
#define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)
2594
#define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
2596
struct malloc_state {
2605
size_t release_checks;
2607
mchunkptr smallbins[(NSMALLBINS+1)*2];
2608
tbinptr treebins[NTREEBINS];
2610
size_t max_footprint;
2611
size_t footprint_limit; /* zero means no limit */
2614
MLOCK_T mutex; /* locate lock among fields that rarely change */
2615
#endif /* USE_LOCKS */
2617
void* extp; /* Unused but available for extensions */
2621
typedef struct malloc_state* mstate;
2623
/* ------------- Global malloc_state and malloc_params ------------------- */
2626
malloc_params holds global properties, including those that can be
2627
dynamically set using mallopt. There is a single instance, mparams,
2628
initialized in init_mparams. Note that the non-zeroness of "magic"
2629
also serves as an initialization flag.
2632
struct malloc_params {
2636
size_t mmap_threshold;
2637
size_t trim_threshold;
2638
flag_t default_mflags;
2641
static struct malloc_params mparams;
2643
/* Ensure mparams initialized */
2644
#define ensure_initialization() (void)(mparams.magic != 0 || init_mparams())
2648
/* The global malloc_state used for all non-"mspace" calls */
2649
static struct malloc_state _gm_;
2651
#define is_global(M) ((M) == &_gm_)
2653
#endif /* !ONLY_MSPACES */
2655
#define is_initialized(M) ((M)->top != 0)
2657
/* -------------------------- system alloc setup ------------------------- */
2659
/* Operations on mflags */
2661
#define use_lock(M) ((M)->mflags & USE_LOCK_BIT)
2662
#define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)
2664
#define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)
2666
#define disable_lock(M)
2669
#define use_mmap(M) ((M)->mflags & USE_MMAP_BIT)
2670
#define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT)
2672
#define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT)
2674
#define disable_mmap(M)
2677
#define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT)
2678
#define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT)
2680
#define set_lock(M,L)\
2681
((M)->mflags = (L)?\
2682
((M)->mflags | USE_LOCK_BIT) :\
2683
((M)->mflags & ~USE_LOCK_BIT))
2685
/* page-align a size */
2686
#define page_align(S)\
2687
(((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE))
2689
/* granularity-align a size */
2690
#define granularity_align(S)\
2691
(((S) + (mparams.granularity - SIZE_T_ONE))\
2692
& ~(mparams.granularity - SIZE_T_ONE))
2695
/* For mmap, use granularity alignment on windows, else page-align */
2697
#define mmap_align(S) granularity_align(S)
2699
#define mmap_align(S) page_align(S)
2702
/* For sys_alloc, enough padding to ensure can malloc request on success */
2703
#define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT)
2705
#define is_page_aligned(S)\
2706
(((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
2707
#define is_granularity_aligned(S)\
2708
(((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
2710
/* True if segment S holds address A */
2711
#define segment_holds(S, A)\
2712
((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
2714
/* Return segment holding given address */
2715
static msegmentptr segment_holding(mstate m, char* addr) {
2716
msegmentptr sp = &m->seg;
2718
if (addr >= sp->base && addr < sp->base + sp->size)
2720
if ((sp = sp->next) == 0)
2725
/* Return true if segment contains a segment link */
2726
static int has_segment_link(mstate m, msegmentptr ss) {
2727
msegmentptr sp = &m->seg;
2729
if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
2731
if ((sp = sp->next) == 0)
2736
#ifndef MORECORE_CANNOT_TRIM
2737
#define should_trim(M,s) ((s) > (M)->trim_check)
2738
#else /* MORECORE_CANNOT_TRIM */
2739
#define should_trim(M,s) (0)
2740
#endif /* MORECORE_CANNOT_TRIM */
2743
TOP_FOOT_SIZE is padding at the end of a segment, including space
2744
that may be needed to place segment records and fenceposts when new
2745
noncontiguous segments are added.
2747
#define TOP_FOOT_SIZE \
2748
(align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
2751
/* ------------------------------- Hooks -------------------------------- */
2754
PREACTION should be defined to return 0 on success, and nonzero on
2755
failure. If you are not using locking, you can redefine these to do
2760
#define PREACTION(M) ((use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
2761
#define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
2762
#else /* USE_LOCKS */
2765
#define PREACTION(M) (0)
2766
#endif /* PREACTION */
2769
#define POSTACTION(M)
2770
#endif /* POSTACTION */
2772
#endif /* USE_LOCKS */
2775
CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
2776
USAGE_ERROR_ACTION is triggered on detected bad frees and
2777
reallocs. The argument p is an address that might have triggered the
2778
fault. It is ignored by the two predefined actions, but might be
2779
useful in custom actions that try to help diagnose errors.
2782
#if PROCEED_ON_ERROR
2784
/* A count of the number of corruption errors causing resets */
2785
int malloc_corruption_error_count;
2787
/* default corruption action */
2788
static void reset_on_error(mstate m);
2790
#define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)
2791
#define USAGE_ERROR_ACTION(m, p)
2793
#else /* PROCEED_ON_ERROR */
2795
#ifndef CORRUPTION_ERROR_ACTION
2796
#define CORRUPTION_ERROR_ACTION(m) ABORT
2797
#endif /* CORRUPTION_ERROR_ACTION */
2799
#ifndef USAGE_ERROR_ACTION
2800
#define USAGE_ERROR_ACTION(m,p) ABORT
2801
#endif /* USAGE_ERROR_ACTION */
2803
#endif /* PROCEED_ON_ERROR */
2806
/* -------------------------- Debugging setup ---------------------------- */
2810
#define check_free_chunk(M,P)
2811
#define check_inuse_chunk(M,P)
2812
#define check_malloced_chunk(M,P,N)
2813
#define check_mmapped_chunk(M,P)
2814
#define check_malloc_state(M)
2815
#define check_top_chunk(M,P)
2818
#define check_free_chunk(M,P) do_check_free_chunk(M,P)
2819
#define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)
2820
#define check_top_chunk(M,P) do_check_top_chunk(M,P)
2821
#define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
2822
#define check_mmapped_chunk(M,P) do_check_mmapped_chunk(M,P)
2823
#define check_malloc_state(M) do_check_malloc_state(M)
2825
static void do_check_any_chunk(mstate m, mchunkptr p);
2826
static void do_check_top_chunk(mstate m, mchunkptr p);
2827
static void do_check_mmapped_chunk(mstate m, mchunkptr p);
2828
static void do_check_inuse_chunk(mstate m, mchunkptr p);
2829
static void do_check_free_chunk(mstate m, mchunkptr p);
2830
static void do_check_malloced_chunk(mstate m, void* mem, size_t s);
2831
static void do_check_tree(mstate m, tchunkptr t);
2832
static void do_check_treebin(mstate m, bindex_t i);
2833
static void do_check_smallbin(mstate m, bindex_t i);
2834
static void do_check_malloc_state(mstate m);
2835
static int bin_find(mstate m, mchunkptr x);
2836
static size_t traverse_and_check(mstate m);
2839
/* ---------------------------- Indexing Bins ---------------------------- */
2841
#define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
2842
#define small_index(s) (bindex_t)((s) >> SMALLBIN_SHIFT)
2843
#define small_index2size(i) ((i) << SMALLBIN_SHIFT)
2844
#define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))
2846
/* addressing by index. See above about smallbin repositioning */
2847
#define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
2848
#define treebin_at(M,i) (&((M)->treebins[i]))
2850
/* assign tree index for size S to variable I. Use x86 asm if possible */
2851
#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
2852
#define compute_tree_index(S, I)\
2854
unsigned int X = S >> TREEBIN_SHIFT;\
2857
else if (X > 0xFFFF)\
2860
unsigned int K = (unsigned) sizeof(X)*__CHAR_BIT__ - 1 - (unsigned) __builtin_clz(X); \
2861
I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2865
#elif defined (__INTEL_COMPILER)
2866
#define compute_tree_index(S, I)\
2868
size_t X = S >> TREEBIN_SHIFT;\
2871
else if (X > 0xFFFF)\
2874
unsigned int K = _bit_scan_reverse (X); \
2875
I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2879
#elif defined(_MSC_VER) && _MSC_VER>=1300
2880
#define compute_tree_index(S, I)\
2882
size_t X = S >> TREEBIN_SHIFT;\
2885
else if (X > 0xFFFF)\
2889
_BitScanReverse((DWORD *) &K, (DWORD) X);\
2890
I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2895
#define compute_tree_index(S, I)\
2897
size_t X = S >> TREEBIN_SHIFT;\
2900
else if (X > 0xFFFF)\
2903
unsigned int Y = (unsigned int)X;\
2904
unsigned int N = ((Y - 0x100) >> 16) & 8;\
2905
unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
2907
N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
2908
K = 14 - N + ((Y <<= K) >> 15);\
2909
I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
2914
/* Bit representing maximum resolved size in a treebin at i */
2915
#define bit_for_tree_index(i) \
2916
(i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
2918
/* Shift placing maximum resolved bit in a treebin at i as sign bit */
2919
#define leftshift_for_tree_index(i) \
2920
((i == NTREEBINS-1)? 0 : \
2921
((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
2923
/* The size of the smallest chunk held in bin with index i */
2924
#define minsize_for_tree_index(i) \
2925
((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \
2926
(((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
2929
/* ------------------------ Operations on bin maps ----------------------- */
2931
/* bit corresponding to given index */
2932
#define idx2bit(i) ((binmap_t)(1) << (i))
2934
/* Mark/Clear bits with given index */
2935
#define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))
2936
#define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))
2937
#define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))
2939
#define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))
2940
#define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))
2941
#define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))
2943
/* isolate the least set bit of a bitmap */
2944
#define least_bit(x) ((x) & -(x))
2946
/* mask with all bits to left of least bit of x on */
2947
#define left_bits(x) ((x<<1) | -(x<<1))
2949
/* mask with all bits to left of or equal to least bit of x on */
2950
#define same_or_left_bits(x) ((x) | -(x))
2952
/* index corresponding to given bit. Use x86 asm if possible */
2954
#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
2955
#define compute_bit2idx(X, I)\
2958
J = __builtin_ctz(X); \
2962
#elif defined (__INTEL_COMPILER)
2963
#define compute_bit2idx(X, I)\
2966
J = _bit_scan_forward (X); \
2970
#elif defined(_MSC_VER) && _MSC_VER>=1300
2971
#define compute_bit2idx(X, I)\
2974
_BitScanForward((DWORD *) &J, X);\
2978
#elif USE_BUILTIN_FFS
2979
#define compute_bit2idx(X, I) I = ffs(X)-1
2982
#define compute_bit2idx(X, I)\
2984
unsigned int Y = X - 1;\
2985
unsigned int K = Y >> (16-4) & 16;\
2986
unsigned int N = K; Y >>= K;\
2987
N += K = Y >> (8-3) & 8; Y >>= K;\
2988
N += K = Y >> (4-2) & 4; Y >>= K;\
2989
N += K = Y >> (2-1) & 2; Y >>= K;\
2990
N += K = Y >> (1-0) & 1; Y >>= K;\
2991
I = (bindex_t)(N + Y);\
2996
/* ----------------------- Runtime Check Support ------------------------- */
2999
For security, the main invariant is that malloc/free/etc never
3000
writes to a static address other than malloc_state, unless static
3001
malloc_state itself has been corrupted, which cannot occur via
3002
malloc (because of these checks). In essence this means that we
3003
believe all pointers, sizes, maps etc held in malloc_state, but
3004
check all of those linked or offsetted from other embedded data
3005
structures. These checks are interspersed with main code in a way
3006
that tends to minimize their run-time cost.
3008
When FOOTERS is defined, in addition to range checking, we also
3009
verify footer fields of inuse chunks, which can be used guarantee
3010
that the mstate controlling malloc/free is intact. This is a
3011
streamlined version of the approach described by William Robertson
3012
et al in "Run-time Detection of Heap-based Overflows" LISA'03
3013
http://www.usenix.org/events/lisa03/tech/robertson.html The footer
3014
of an inuse chunk holds the xor of its mstate and a random seed,
3015
that is checked upon calls to free() and realloc(). This is
3016
(probabalistically) unguessable from outside the program, but can be
3017
computed by any code successfully malloc'ing any chunk, so does not
3018
itself provide protection against code that has already broken
3019
security through some other means. Unlike Robertson et al, we
3020
always dynamically check addresses of all offset chunks (previous,
3021
next, etc). This turns out to be cheaper than relying on hashes.
3025
/* Check if address a is at least as high as any from MORECORE or MMAP */
3026
#define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
3027
/* Check if address of next chunk n is higher than base chunk p */
3028
#define ok_next(p, n) ((char*)(p) < (char*)(n))
3029
/* Check if p has inuse status */
3030
#define ok_inuse(p) is_inuse(p)
3031
/* Check if p has its pinuse bit on */
3032
#define ok_pinuse(p) pinuse(p)
3034
#else /* !INSECURE */
3035
#define ok_address(M, a) (1)
3036
#define ok_next(b, n) (1)
3037
#define ok_inuse(p) (1)
3038
#define ok_pinuse(p) (1)
3039
#endif /* !INSECURE */
3041
#if (FOOTERS && !INSECURE)
3042
/* Check if (alleged) mstate m has expected magic field */
3043
#define ok_magic(M) ((M)->magic == mparams.magic)
3044
#else /* (FOOTERS && !INSECURE) */
3045
#define ok_magic(M) (1)
3046
#endif /* (FOOTERS && !INSECURE) */
3048
/* In gcc, use __builtin_expect to minimize impact of checks */
3050
#if defined(__GNUC__) && __GNUC__ >= 3
3051
#define RTCHECK(e) __builtin_expect(e, 1)
3053
#define RTCHECK(e) (e)
3055
#else /* !INSECURE */
3056
#define RTCHECK(e) (1)
3057
#endif /* !INSECURE */
3059
/* macros to set up inuse chunks with or without footers */
3063
#define mark_inuse_foot(M,p,s)
3065
/* Macros for setting head/foot of non-mmapped chunks */
3067
/* Set cinuse bit and pinuse bit of next chunk */
3068
#define set_inuse(M,p,s)\
3069
((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
3070
((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
3072
/* Set cinuse and pinuse of this chunk and pinuse of next chunk */
3073
#define set_inuse_and_pinuse(M,p,s)\
3074
((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
3075
((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
3077
/* Set size, cinuse and pinuse bit of this chunk */
3078
#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
3079
((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
3083
/* Set foot of inuse chunk to be xor of mstate and seed */
3084
#define mark_inuse_foot(M,p,s)\
3085
(((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
3087
#define get_mstate_for(p)\
3088
((mstate)(((mchunkptr)((char*)(p) +\
3089
(chunksize(p))))->prev_foot ^ mparams.magic))
3091
#define set_inuse(M,p,s)\
3092
((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
3093
(((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
3094
mark_inuse_foot(M,p,s))
3096
#define set_inuse_and_pinuse(M,p,s)\
3097
((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
3098
(((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
3099
mark_inuse_foot(M,p,s))
3101
#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
3102
((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
3103
mark_inuse_foot(M, p, s))
3105
#endif /* !FOOTERS */
3107
/* ---------------------------- setting mparams -------------------------- */
3110
static void pre_fork(void) { ACQUIRE_LOCK(&(gm)->mutex); }
3111
static void post_fork_parent(void) { RELEASE_LOCK(&(gm)->mutex); }
3112
static void post_fork_child(void) { INITIAL_LOCK(&(gm)->mutex); }
3113
#endif /* LOCK_AT_FORK */
3115
/* Initialize mparams */
3116
static int init_mparams(void) {
3117
#ifdef NEED_GLOBAL_LOCK_INIT
3118
if (malloc_global_mutex_status <= 0)
3119
init_malloc_global_mutex();
3122
ACQUIRE_MALLOC_GLOBAL_LOCK();
3123
if (mparams.magic == 0) {
3129
psize = malloc_getpagesize;
3130
gsize = ((DEFAULT_GRANULARITY != 0)? DEFAULT_GRANULARITY : psize);
3133
SYSTEM_INFO system_info;
3134
GetSystemInfo(&system_info);
3135
psize = system_info.dwPageSize;
3136
gsize = ((DEFAULT_GRANULARITY != 0)?
3137
DEFAULT_GRANULARITY : system_info.dwAllocationGranularity);
3141
/* Sanity-check configuration:
3142
size_t must be unsigned and as wide as pointer type.
3143
ints must be at least 4 bytes.
3144
alignment must be at least 8.
3145
Alignment, min chunk size, and page size must all be powers of 2.
3147
if ((sizeof(size_t) != sizeof(char*)) ||
3148
(MAX_SIZE_T < MIN_CHUNK_SIZE) ||
3149
(sizeof(int) < 4) ||
3150
(MALLOC_ALIGNMENT < (size_t)8U) ||
3151
((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
3152
((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) ||
3153
((gsize & (gsize-SIZE_T_ONE)) != 0) ||
3154
((psize & (psize-SIZE_T_ONE)) != 0))
3156
mparams.granularity = gsize;
3157
mparams.page_size = psize;
3158
mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
3159
mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
3160
#if MORECORE_CONTIGUOUS
3161
mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
3162
#else /* MORECORE_CONTIGUOUS */
3163
mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
3164
#endif /* MORECORE_CONTIGUOUS */
3167
/* Set up lock for main malloc area */
3168
gm->mflags = mparams.default_mflags;
3169
(void)INITIAL_LOCK(&gm->mutex);
3172
pthread_atfork(&pre_fork, &post_fork_parent, &post_fork_child);
3178
unsigned char buf[sizeof(size_t)];
3179
/* Try to use /dev/urandom, else fall back on using time */
3180
if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
3181
read(fd, buf, sizeof(buf)) == sizeof(buf)) {
3182
magic = *((size_t *) buf);
3186
#endif /* USE_DEV_RANDOM */
3188
magic = (size_t)(GetTickCount() ^ (size_t)0x55555555U);
3189
#elif defined(LACKS_TIME_H)
3190
magic = (size_t)&magic ^ (size_t)0x55555555U;
3192
magic = (size_t)(time(0) ^ (size_t)0x55555555U);
3194
magic |= (size_t)8U; /* ensure nonzero */
3195
magic &= ~(size_t)7U; /* improve chances of fault for bad values */
3196
/* Until memory modes commonly available, use volatile-write */
3197
(*(volatile size_t *)(&(mparams.magic))) = magic;
3201
RELEASE_MALLOC_GLOBAL_LOCK();
3205
/* support for mallopt */
3206
static int change_mparam(int param_number, int value) {
3208
ensure_initialization();
3209
val = (value == -1)? MAX_SIZE_T : (size_t)value;
3210
switch(param_number) {
3211
case M_TRIM_THRESHOLD:
3212
mparams.trim_threshold = val;
3215
if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
3216
mparams.granularity = val;
3221
case M_MMAP_THRESHOLD:
3222
mparams.mmap_threshold = val;
3230
/* ------------------------- Debugging Support --------------------------- */
3232
/* Check properties of any chunk, whether free, inuse, mmapped etc */
3233
static void do_check_any_chunk(mstate m, mchunkptr p) {
3234
assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3235
assert(ok_address(m, p));
3238
/* Check properties of top chunk */
3239
static void do_check_top_chunk(mstate m, mchunkptr p) {
3240
msegmentptr sp = segment_holding(m, (char*)p);
3241
size_t sz = p->head & ~INUSE_BITS; /* third-lowest bit can be set! */
3243
assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3244
assert(ok_address(m, p));
3245
assert(sz == m->topsize);
3247
assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
3249
assert(!pinuse(chunk_plus_offset(p, sz)));
3252
/* Check properties of (inuse) mmapped chunks */
3253
static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
3254
size_t sz = chunksize(p);
3255
size_t len = (sz + (p->prev_foot) + MMAP_FOOT_PAD);
3256
assert(is_mmapped(p));
3257
assert(use_mmap(m));
3258
assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3259
assert(ok_address(m, p));
3260
assert(!is_small(sz));
3261
assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
3262
assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
3263
assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
3266
/* Check properties of inuse chunks */
3267
static void do_check_inuse_chunk(mstate m, mchunkptr p) {
3268
do_check_any_chunk(m, p);
3269
assert(is_inuse(p));
3270
assert(next_pinuse(p));
3271
/* If not pinuse and not mmapped, previous chunk has OK offset */
3272
assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
3274
do_check_mmapped_chunk(m, p);
3277
/* Check properties of free chunks */
3278
static void do_check_free_chunk(mstate m, mchunkptr p) {
3279
size_t sz = chunksize(p);
3280
mchunkptr next = chunk_plus_offset(p, sz);
3281
do_check_any_chunk(m, p);
3282
assert(!is_inuse(p));
3283
assert(!next_pinuse(p));
3284
assert (!is_mmapped(p));
3285
if (p != m->dv && p != m->top) {
3286
if (sz >= MIN_CHUNK_SIZE) {
3287
assert((sz & CHUNK_ALIGN_MASK) == 0);
3288
assert(is_aligned(chunk2mem(p)));
3289
assert(next->prev_foot == sz);
3291
assert (next == m->top || is_inuse(next));
3292
assert(p->fd->bk == p);
3293
assert(p->bk->fd == p);
3295
else /* markers are always of size SIZE_T_SIZE */
3296
assert(sz == SIZE_T_SIZE);
3300
/* Check properties of malloced chunks at the point they are malloced */
3301
static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
3303
mchunkptr p = mem2chunk(mem);
3304
size_t sz = p->head & ~INUSE_BITS;
3305
do_check_inuse_chunk(m, p);
3306
assert((sz & CHUNK_ALIGN_MASK) == 0);
3307
assert(sz >= MIN_CHUNK_SIZE);
3309
/* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
3310
assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
3314
/* Check a tree and its subtrees. */
3315
static void do_check_tree(mstate m, tchunkptr t) {
3318
bindex_t tindex = t->index;
3319
size_t tsize = chunksize(t);
3321
compute_tree_index(tsize, idx);
3322
assert(tindex == idx);
3323
assert(tsize >= MIN_LARGE_SIZE);
3324
assert(tsize >= minsize_for_tree_index(idx));
3325
assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
3327
do { /* traverse through chain of same-sized nodes */
3328
do_check_any_chunk(m, ((mchunkptr)u));
3329
assert(u->index == tindex);
3330
assert(chunksize(u) == tsize);
3331
assert(!is_inuse(u));
3332
assert(!next_pinuse(u));
3333
assert(u->fd->bk == u);
3334
assert(u->bk->fd == u);
3335
if (u->parent == 0) {
3336
assert(u->child[0] == 0);
3337
assert(u->child[1] == 0);
3340
assert(head == 0); /* only one node on chain has parent */
3342
assert(u->parent != u);
3343
assert (u->parent->child[0] == u ||
3344
u->parent->child[1] == u ||
3345
*((tbinptr*)(u->parent)) == u);
3346
if (u->child[0] != 0) {
3347
assert(u->child[0]->parent == u);
3348
assert(u->child[0] != u);
3349
do_check_tree(m, u->child[0]);
3351
if (u->child[1] != 0) {
3352
assert(u->child[1]->parent == u);
3353
assert(u->child[1] != u);
3354
do_check_tree(m, u->child[1]);
3356
if (u->child[0] != 0 && u->child[1] != 0) {
3357
assert(chunksize(u->child[0]) < chunksize(u->child[1]));
3365
/* Check all the chunks in a treebin. */
3366
static void do_check_treebin(mstate m, bindex_t i) {
3367
tbinptr* tb = treebin_at(m, i);
3369
int empty = (m->treemap & (1U << i)) == 0;
3373
do_check_tree(m, t);
3376
/* Check all the chunks in a smallbin. */
3377
static void do_check_smallbin(mstate m, bindex_t i) {
3378
sbinptr b = smallbin_at(m, i);
3379
mchunkptr p = b->bk;
3380
unsigned int empty = (m->smallmap & (1U << i)) == 0;
3384
for (; p != b; p = p->bk) {
3385
size_t size = chunksize(p);
3387
/* each chunk claims to be free */
3388
do_check_free_chunk(m, p);
3389
/* chunk belongs in bin */
3390
assert(small_index(size) == i);
3391
assert(p->bk == b || chunksize(p->bk) == chunksize(p));
3392
/* chunk is followed by an inuse chunk */
3394
if (q->head != FENCEPOST_HEAD)
3395
do_check_inuse_chunk(m, q);
3400
/* Find x in a bin. Used in other check functions. */
3401
static int bin_find(mstate m, mchunkptr x) {
3402
size_t size = chunksize(x);
3403
if (is_small(size)) {
3404
bindex_t sidx = small_index(size);
3405
sbinptr b = smallbin_at(m, sidx);
3406
if (smallmap_is_marked(m, sidx)) {
3411
} while ((p = p->fd) != b);
3416
compute_tree_index(size, tidx);
3417
if (treemap_is_marked(m, tidx)) {
3418
tchunkptr t = *treebin_at(m, tidx);
3419
size_t sizebits = size << leftshift_for_tree_index(tidx);
3420
while (t != 0 && chunksize(t) != size) {
3421
t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
3427
if (u == (tchunkptr)x)
3429
} while ((u = u->fd) != t);
3436
/* Traverse each chunk and check it; return total */
3437
static size_t traverse_and_check(mstate m) {
3439
if (is_initialized(m)) {
3440
msegmentptr s = &m->seg;
3441
sum += m->topsize + TOP_FOOT_SIZE;
3443
mchunkptr q = align_as_chunk(s->base);
3444
mchunkptr lastq = 0;
3446
while (segment_holds(s, q) &&
3447
q != m->top && q->head != FENCEPOST_HEAD) {
3448
sum += chunksize(q);
3450
assert(!bin_find(m, q));
3451
do_check_inuse_chunk(m, q);
3454
assert(q == m->dv || bin_find(m, q));
3455
assert(lastq == 0 || is_inuse(lastq)); /* Not 2 consecutive free */
3456
do_check_free_chunk(m, q);
3468
/* Check all properties of malloc_state. */
3469
static void do_check_malloc_state(mstate m) {
3473
for (i = 0; i < NSMALLBINS; ++i)
3474
do_check_smallbin(m, i);
3475
for (i = 0; i < NTREEBINS; ++i)
3476
do_check_treebin(m, i);
3478
if (m->dvsize != 0) { /* check dv chunk */
3479
do_check_any_chunk(m, m->dv);
3480
assert(m->dvsize == chunksize(m->dv));
3481
assert(m->dvsize >= MIN_CHUNK_SIZE);
3482
assert(bin_find(m, m->dv) == 0);
3485
if (m->top != 0) { /* check top chunk */
3486
do_check_top_chunk(m, m->top);
3487
/*assert(m->topsize == chunksize(m->top)); redundant */
3488
assert(m->topsize > 0);
3489
assert(bin_find(m, m->top) == 0);
3492
total = traverse_and_check(m);
3493
assert(total <= m->footprint);
3494
assert(m->footprint <= m->max_footprint);
3498
/* ----------------------------- statistics ------------------------------ */
3501
static struct mallinfo internal_mallinfo(mstate m) {
3502
struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
3503
ensure_initialization();
3504
if (!PREACTION(m)) {
3505
check_malloc_state(m);
3506
if (is_initialized(m)) {
3507
size_t nfree = SIZE_T_ONE; /* top always free */
3508
size_t mfree = m->topsize + TOP_FOOT_SIZE;
3510
msegmentptr s = &m->seg;
3512
mchunkptr q = align_as_chunk(s->base);
3513
while (segment_holds(s, q) &&
3514
q != m->top && q->head != FENCEPOST_HEAD) {
3515
size_t sz = chunksize(q);
3528
nm.hblkhd = m->footprint - sum;
3529
nm.usmblks = m->max_footprint;
3530
nm.uordblks = m->footprint - mfree;
3531
nm.fordblks = mfree;
3532
nm.keepcost = m->topsize;
3539
#endif /* !NO_MALLINFO */
3541
#if !NO_MALLOC_STATS
3542
static void internal_malloc_stats(mstate m) {
3543
ensure_initialization();
3544
if (!PREACTION(m)) {
3548
check_malloc_state(m);
3549
if (is_initialized(m)) {
3550
msegmentptr s = &m->seg;
3551
maxfp = m->max_footprint;
3553
used = fp - (m->topsize + TOP_FOOT_SIZE);
3556
mchunkptr q = align_as_chunk(s->base);
3557
while (segment_holds(s, q) &&
3558
q != m->top && q->head != FENCEPOST_HEAD) {
3560
used -= chunksize(q);
3566
POSTACTION(m); /* drop lock */
3567
fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
3568
fprintf(stderr, "system bytes = %10lu\n", (unsigned long)(fp));
3569
fprintf(stderr, "in use bytes = %10lu\n", (unsigned long)(used));
3572
#endif /* NO_MALLOC_STATS */
3574
/* ----------------------- Operations on smallbins ----------------------- */
3577
Various forms of linking and unlinking are defined as macros. Even
3578
the ones for trees, which are very long but have very short typical
3579
paths. This is ugly but reduces reliance on inlining support of
3583
/* Link a free chunk into a smallbin */
3584
#define insert_small_chunk(M, P, S) {\
3585
bindex_t I = small_index(S);\
3586
mchunkptr B = smallbin_at(M, I);\
3588
assert(S >= MIN_CHUNK_SIZE);\
3589
if (!smallmap_is_marked(M, I))\
3590
mark_smallmap(M, I);\
3591
else if (RTCHECK(ok_address(M, B->fd)))\
3594
CORRUPTION_ERROR_ACTION(M);\
3602
/* Unlink a chunk from a smallbin */
3603
#define unlink_small_chunk(M, P, S) {\
3604
mchunkptr F = P->fd;\
3605
mchunkptr B = P->bk;\
3606
bindex_t I = small_index(S);\
3609
assert(chunksize(P) == small_index2size(I));\
3610
if (RTCHECK(F == smallbin_at(M,I) || (ok_address(M, F) && F->bk == P))) { \
3612
clear_smallmap(M, I);\
3614
else if (RTCHECK(B == smallbin_at(M,I) ||\
3615
(ok_address(M, B) && B->fd == P))) {\
3620
CORRUPTION_ERROR_ACTION(M);\
3624
CORRUPTION_ERROR_ACTION(M);\
3628
/* Unlink the first chunk from a smallbin */
3629
#define unlink_first_small_chunk(M, B, P, I) {\
3630
mchunkptr F = P->fd;\
3633
assert(chunksize(P) == small_index2size(I));\
3635
clear_smallmap(M, I);\
3637
else if (RTCHECK(ok_address(M, F) && F->bk == P)) {\
3642
CORRUPTION_ERROR_ACTION(M);\
3646
/* Replace dv node, binning the old one */
3647
/* Used only when dvsize known to be small */
3648
#define replace_dv(M, P, S) {\
3649
size_t DVS = M->dvsize;\
3650
assert(is_small(DVS));\
3652
mchunkptr DV = M->dv;\
3653
insert_small_chunk(M, DV, DVS);\
3659
/* ------------------------- Operations on trees ------------------------- */
3661
/* Insert chunk into tree */
3662
#define insert_large_chunk(M, X, S) {\
3665
compute_tree_index(S, I);\
3666
H = treebin_at(M, I);\
3668
X->child[0] = X->child[1] = 0;\
3669
if (!treemap_is_marked(M, I)) {\
3670
mark_treemap(M, I);\
3672
X->parent = (tchunkptr)H;\
3677
size_t K = S << leftshift_for_tree_index(I);\
3679
if (chunksize(T) != S) {\
3680
tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
3684
else if (RTCHECK(ok_address(M, C))) {\
3691
CORRUPTION_ERROR_ACTION(M);\
3696
tchunkptr F = T->fd;\
3697
if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
3705
CORRUPTION_ERROR_ACTION(M);\
3716
1. If x is a chained node, unlink it from its same-sized fd/bk links
3717
and choose its bk node as its replacement.
3718
2. If x was the last node of its size, but not a leaf node, it must
3719
be replaced with a leaf node (not merely one with an open left or
3720
right), to make sure that lefts and rights of descendents
3721
correspond properly to bit masks. We use the rightmost descendent
3722
of x. We could use any other leaf, but this is easy to locate and
3723
tends to counteract removal of leftmosts elsewhere, and so keeps
3724
paths shorter than minimally guaranteed. This doesn't loop much
3725
because on average a node in a tree is near the bottom.
3726
3. If x is the base of a chain (i.e., has parent links) relink
3727
x's parent and children to x's replacement (or null if none).
3730
#define unlink_large_chunk(M, X) { \
3731
tchunkptr XP = X->parent; \
3734
tchunkptr F = X->fd; \
3736
if (RTCHECK(ok_address(M, F) && F->bk == X && R->fd == X)) { \
3741
CORRUPTION_ERROR_ACTION(M); \
3746
if (((R = *(RP = &(X->child[1]))) != 0) || \
3747
((R = *(RP = &(X->child[0]))) != 0)) { \
3749
while ((*(CP = &(R->child[1])) != 0) || \
3750
(*(CP = &(R->child[0])) != 0)) { \
3753
if (RTCHECK(ok_address(M, RP))) \
3756
CORRUPTION_ERROR_ACTION(M); \
3761
tbinptr* H = treebin_at(M, X->index); \
3763
if ((*H = R) == 0) \
3764
clear_treemap(M, X->index); \
3766
else if (RTCHECK(ok_address(M, XP))) { \
3767
if (XP->child[0] == X) \
3773
CORRUPTION_ERROR_ACTION(M); \
3775
if (RTCHECK(ok_address(M, R))) { \
3778
if ((C0 = X->child[0]) != 0) { \
3779
if (RTCHECK(ok_address(M, C0))) { \
3784
CORRUPTION_ERROR_ACTION(M); \
3786
if ((C1 = X->child[1]) != 0) { \
3787
if (RTCHECK(ok_address(M, C1))) { \
3792
CORRUPTION_ERROR_ACTION(M); \
3796
CORRUPTION_ERROR_ACTION(M); \
3801
/* Relays to large vs small bin operations */
3803
#define insert_chunk(M, P, S) \
3804
if (is_small(S)) insert_small_chunk(M, P, S) \
3805
else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
3807
#define unlink_chunk(M, P, S) \
3808
if (is_small(S)) unlink_small_chunk(M, P, S) \
3809
else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
3812
/* Relays to internal calls to malloc/free from realloc, memalign etc */
3815
#define internal_malloc(m, b) mspace_malloc(m, b)
3816
#define internal_free(m, mem) mspace_free(m,mem);
3817
#else /* ONLY_MSPACES */
3819
#define internal_malloc(m, b)\
3820
((m == gm)? dlmalloc(b) : mspace_malloc(m, b))
3821
#define internal_free(m, mem)\
3822
if (m == gm) dlfree(mem); else mspace_free(m,mem);
3824
#define internal_malloc(m, b) dlmalloc(b)
3825
#define internal_free(m, mem) dlfree(mem)
3826
#endif /* MSPACES */
3827
#endif /* ONLY_MSPACES */
3829
/* ----------------------- Direct-mmapping chunks ----------------------- */
3832
Directly mmapped chunks are set up with an offset to the start of
3833
the mmapped region stored in the prev_foot field of the chunk. This
3834
allows reconstruction of the required argument to MUNMAP when freed,
3835
and also allows adjustment of the returned chunk to meet alignment
3836
requirements (especially in memalign).
3839
/* Malloc using mmap */
3840
static void* mmap_alloc(mstate m, size_t nb) {
3841
size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3842
if (m->footprint_limit != 0) {
3843
size_t fp = m->footprint + mmsize;
3844
if (fp <= m->footprint || fp > m->footprint_limit)
3847
if (mmsize > nb) { /* Check for wrap around 0 */
3848
char* mm = (char*)(CALL_DIRECT_MMAP(mmsize));
3850
size_t offset = align_offset(chunk2mem(mm));
3851
size_t psize = mmsize - offset - MMAP_FOOT_PAD;
3852
mchunkptr p = (mchunkptr)(mm + offset);
3853
p->prev_foot = offset;
3855
mark_inuse_foot(m, p, psize);
3856
chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
3857
chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
3859
if (m->least_addr == 0 || mm < m->least_addr)
3861
if ((m->footprint += mmsize) > m->max_footprint)
3862
m->max_footprint = m->footprint;
3863
assert(is_aligned(chunk2mem(p)));
3864
check_mmapped_chunk(m, p);
3865
return chunk2mem(p);
3871
/* Realloc using mmap */
3872
static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb, int flags) {
3873
size_t oldsize = chunksize(oldp);
3874
(void)flags; /* placate people compiling -Wunused */
3875
if (is_small(nb)) /* Can't shrink mmap regions below small size */
3877
/* Keep old chunk if big enough but not too big */
3878
if (oldsize >= nb + SIZE_T_SIZE &&
3879
(oldsize - nb) <= (mparams.granularity << 1))
3882
size_t offset = oldp->prev_foot;
3883
size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
3884
size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3885
char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
3886
oldmmsize, newmmsize, flags);
3888
mchunkptr newp = (mchunkptr)(cp + offset);
3889
size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
3891
mark_inuse_foot(m, newp, psize);
3892
chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
3893
chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
3895
if (cp < m->least_addr)
3897
if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
3898
m->max_footprint = m->footprint;
3899
check_mmapped_chunk(m, newp);
3907
/* -------------------------- mspace management -------------------------- */
3909
/* Initialize top chunk and its size */
3910
static void init_top(mstate m, mchunkptr p, size_t psize) {
3911
/* Ensure alignment */
3912
size_t offset = align_offset(chunk2mem(p));
3913
p = (mchunkptr)((char*)p + offset);
3918
p->head = psize | PINUSE_BIT;
3919
/* set size of fake trailing chunk holding overhead space only once */
3920
chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
3921
m->trim_check = mparams.trim_threshold; /* reset on each update */
3924
/* Initialize bins for a new mstate that is otherwise zeroed out */
3925
static void init_bins(mstate m) {
3926
/* Establish circular links for smallbins */
3928
for (i = 0; i < NSMALLBINS; ++i) {
3929
sbinptr bin = smallbin_at(m,i);
3930
bin->fd = bin->bk = bin;
3934
#if PROCEED_ON_ERROR
3936
/* default corruption action */
3937
static void reset_on_error(mstate m) {
3939
++malloc_corruption_error_count;
3940
/* Reinitialize fields to forget about all memory */
3941
m->smallmap = m->treemap = 0;
3942
m->dvsize = m->topsize = 0;
3947
for (i = 0; i < NTREEBINS; ++i)
3948
*treebin_at(m, i) = 0;
3951
#endif /* PROCEED_ON_ERROR */
3953
/* Allocate chunk and prepend remainder with chunk in successor base. */
3954
static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
3956
mchunkptr p = align_as_chunk(newbase);
3957
mchunkptr oldfirst = align_as_chunk(oldbase);
3958
size_t psize = (char*)oldfirst - (char*)p;
3959
mchunkptr q = chunk_plus_offset(p, nb);
3960
size_t qsize = psize - nb;
3961
set_size_and_pinuse_of_inuse_chunk(m, p, nb);
3963
assert((char*)oldfirst > (char*)q);
3964
assert(pinuse(oldfirst));
3965
assert(qsize >= MIN_CHUNK_SIZE);
3967
/* consolidate remainder with first chunk of old base */
3968
if (oldfirst == m->top) {
3969
size_t tsize = m->topsize += qsize;
3971
q->head = tsize | PINUSE_BIT;
3972
check_top_chunk(m, q);
3974
else if (oldfirst == m->dv) {
3975
size_t dsize = m->dvsize += qsize;
3977
set_size_and_pinuse_of_free_chunk(q, dsize);
3980
if (!is_inuse(oldfirst)) {
3981
size_t nsize = chunksize(oldfirst);
3982
unlink_chunk(m, oldfirst, nsize);
3983
oldfirst = chunk_plus_offset(oldfirst, nsize);
3986
set_free_with_pinuse(q, qsize, oldfirst);
3987
insert_chunk(m, q, qsize);
3988
check_free_chunk(m, q);
3991
check_malloced_chunk(m, chunk2mem(p), nb);
3992
return chunk2mem(p);
3995
/* Add a segment to hold a new noncontiguous region */
3996
static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
3997
/* Determine locations and sizes of segment, fenceposts, old top */
3998
char* old_top = (char*)m->top;
3999
msegmentptr oldsp = segment_holding(m, old_top);
4000
char* old_end = oldsp->base + oldsp->size;
4001
size_t ssize = pad_request(sizeof(struct malloc_segment));
4002
char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
4003
size_t offset = align_offset(chunk2mem(rawsp));
4004
char* asp = rawsp + offset;
4005
char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
4006
mchunkptr sp = (mchunkptr)csp;
4007
msegmentptr ss = (msegmentptr)(chunk2mem(sp));
4008
mchunkptr tnext = chunk_plus_offset(sp, ssize);
4009
mchunkptr p = tnext;
4012
/* reset top to new space */
4013
init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
4015
/* Set up segment record */
4016
assert(is_aligned(ss));
4017
set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
4018
*ss = m->seg; /* Push current record */
4019
m->seg.base = tbase;
4020
m->seg.size = tsize;
4021
m->seg.sflags = mmapped;
4024
/* Insert trailing fenceposts */
4026
mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
4027
p->head = FENCEPOST_HEAD;
4029
if ((char*)(&(nextp->head)) < old_end)
4034
assert(nfences >= 2);
4036
/* Insert the rest of old top into a bin as an ordinary free chunk */
4037
if (csp != old_top) {
4038
mchunkptr q = (mchunkptr)old_top;
4039
size_t psize = csp - old_top;
4040
mchunkptr tn = chunk_plus_offset(q, psize);
4041
set_free_with_pinuse(q, psize, tn);
4042
insert_chunk(m, q, psize);
4045
check_top_chunk(m, m->top);
4048
/* -------------------------- System allocation -------------------------- */
4050
/* Get memory from system using MORECORE or MMAP */
4051
static void* sys_alloc(mstate m, size_t nb) {
4052
char* tbase = CMFAIL;
4054
flag_t mmap_flag = 0;
4055
size_t asize; /* allocation size */
4057
ensure_initialization();
4059
/* Directly map large chunks, but only if already initialized */
4060
if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) {
4061
void* mem = mmap_alloc(m, nb);
4066
asize = granularity_align(nb + SYS_ALLOC_PADDING);
4068
return 0; /* wraparound */
4069
if (m->footprint_limit != 0) {
4070
size_t fp = m->footprint + asize;
4071
if (fp <= m->footprint || fp > m->footprint_limit)
4076
Try getting memory in any of three ways (in most-preferred to
4077
least-preferred order):
4078
1. A call to MORECORE that can normally contiguously extend memory.
4079
(disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
4080
or main space is mmapped or a previous contiguous call failed)
4081
2. A call to MMAP new space (disabled if not HAVE_MMAP).
4082
Note that under the default settings, if MORECORE is unable to
4083
fulfill a request, and HAVE_MMAP is true, then mmap is
4084
used as a noncontiguous system allocator. This is a useful backup
4085
strategy for systems with holes in address spaces -- in this case
4086
sbrk cannot contiguously expand the heap, but mmap may be able to
4088
3. A call to MORECORE that cannot usually contiguously extend memory.
4089
(disabled if not HAVE_MORECORE)
4091
In all cases, we need to request enough bytes from system to ensure
4092
we can malloc nb bytes upon success, so pad with enough space for
4093
top_foot, plus alignment-pad to make sure we don't lose bytes if
4094
not on boundary, and round this up to a granularity unit.
4097
if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
4099
size_t ssize = asize; /* sbrk call size */
4100
msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
4101
ACQUIRE_MALLOC_GLOBAL_LOCK();
4103
if (ss == 0) { /* First time through or recovery */
4104
char* base = (char*)CALL_MORECORE(0);
4105
if (base != CMFAIL) {
4107
/* Adjust to end on a page boundary */
4108
if (!is_page_aligned(base))
4109
ssize += (page_align((size_t)base) - (size_t)base);
4110
fp = m->footprint + ssize; /* recheck limits */
4111
if (ssize > nb && ssize < HALF_MAX_SIZE_T &&
4112
(m->footprint_limit == 0 ||
4113
(fp > m->footprint && fp <= m->footprint_limit)) &&
4114
(br = (char*)(CALL_MORECORE(ssize))) == base) {
4121
/* Subtract out existing available top space from MORECORE request. */
4122
ssize = granularity_align(nb - m->topsize + SYS_ALLOC_PADDING);
4123
/* Use mem here only if it did continuously extend old space */
4124
if (ssize < HALF_MAX_SIZE_T &&
4125
(br = (char*)(CALL_MORECORE(ssize))) == ss->base+ss->size) {
4131
if (tbase == CMFAIL) { /* Cope with partial failure */
4132
if (br != CMFAIL) { /* Try to use/extend the space we did get */
4133
if (ssize < HALF_MAX_SIZE_T &&
4134
ssize < nb + SYS_ALLOC_PADDING) {
4135
size_t esize = granularity_align(nb + SYS_ALLOC_PADDING - ssize);
4136
if (esize < HALF_MAX_SIZE_T) {
4137
char* end = (char*)CALL_MORECORE(esize);
4140
else { /* Can't use; try to release */
4141
(void) CALL_MORECORE(-ssize);
4147
if (br != CMFAIL) { /* Use the space we did get */
4152
disable_contiguous(m); /* Don't try contiguous path in the future */
4155
RELEASE_MALLOC_GLOBAL_LOCK();
4158
if (HAVE_MMAP && tbase == CMFAIL) { /* Try MMAP */
4159
char* mp = (char*)(CALL_MMAP(asize));
4163
mmap_flag = USE_MMAP_BIT;
4167
if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
4168
if (asize < HALF_MAX_SIZE_T) {
4171
ACQUIRE_MALLOC_GLOBAL_LOCK();
4172
br = (char*)(CALL_MORECORE(asize));
4173
end = (char*)(CALL_MORECORE(0));
4174
RELEASE_MALLOC_GLOBAL_LOCK();
4175
if (br != CMFAIL && end != CMFAIL && br < end) {
4176
size_t ssize = end - br;
4177
if (ssize > nb + TOP_FOOT_SIZE) {
4185
if (tbase != CMFAIL) {
4187
if ((m->footprint += tsize) > m->max_footprint)
4188
m->max_footprint = m->footprint;
4190
if (!is_initialized(m)) { /* first-time initialization */
4191
if (m->least_addr == 0 || tbase < m->least_addr)
4192
m->least_addr = tbase;
4193
m->seg.base = tbase;
4194
m->seg.size = tsize;
4195
m->seg.sflags = mmap_flag;
4196
m->magic = mparams.magic;
4197
m->release_checks = MAX_RELEASE_CHECK_RATE;
4201
init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
4205
/* Offset top by embedded malloc_state */
4206
mchunkptr mn = next_chunk(mem2chunk(m));
4207
init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
4212
/* Try to merge with an existing segment */
4213
msegmentptr sp = &m->seg;
4214
/* Only consider most recent segment if traversal suppressed */
4215
while (sp != 0 && tbase != sp->base + sp->size)
4216
sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
4218
!is_extern_segment(sp) &&
4219
(sp->sflags & USE_MMAP_BIT) == mmap_flag &&
4220
segment_holds(sp, m->top)) { /* append */
4222
init_top(m, m->top, m->topsize + tsize);
4225
if (tbase < m->least_addr)
4226
m->least_addr = tbase;
4228
while (sp != 0 && sp->base != tbase + tsize)
4229
sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
4231
!is_extern_segment(sp) &&
4232
(sp->sflags & USE_MMAP_BIT) == mmap_flag) {
4233
char* oldbase = sp->base;
4236
return prepend_alloc(m, tbase, oldbase, nb);
4239
add_segment(m, tbase, tsize, mmap_flag);
4243
if (nb < m->topsize) { /* Allocate from new or extended top space */
4244
size_t rsize = m->topsize -= nb;
4245
mchunkptr p = m->top;
4246
mchunkptr r = m->top = chunk_plus_offset(p, nb);
4247
r->head = rsize | PINUSE_BIT;
4248
set_size_and_pinuse_of_inuse_chunk(m, p, nb);
4249
check_top_chunk(m, m->top);
4250
check_malloced_chunk(m, chunk2mem(p), nb);
4251
return chunk2mem(p);
4255
MALLOC_FAILURE_ACTION;
4259
/* ----------------------- system deallocation -------------------------- */
4261
/* Unmap and unlink any mmapped segments that don't contain used chunks */
4262
static size_t release_unused_segments(mstate m) {
4263
size_t released = 0;
4265
msegmentptr pred = &m->seg;
4266
msegmentptr sp = pred->next;
4268
char* base = sp->base;
4269
size_t size = sp->size;
4270
msegmentptr next = sp->next;
4272
if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
4273
mchunkptr p = align_as_chunk(base);
4274
size_t psize = chunksize(p);
4275
/* Can unmap if first chunk holds entire segment and not pinned */
4276
if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
4277
tchunkptr tp = (tchunkptr)p;
4278
assert(segment_holds(sp, (char*)sp));
4284
unlink_large_chunk(m, tp);
4286
if (CALL_MUNMAP(base, size) == 0) {
4288
m->footprint -= size;
4289
/* unlink obsoleted record */
4293
else { /* back out if cannot unmap */
4294
insert_large_chunk(m, tp, psize);
4298
if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */
4303
/* Reset check counter */
4304
m->release_checks = (((size_t) nsegs > (size_t) MAX_RELEASE_CHECK_RATE)?
4305
(size_t) nsegs : (size_t) MAX_RELEASE_CHECK_RATE);
4309
static int sys_trim(mstate m, size_t pad) {
4310
size_t released = 0;
4311
ensure_initialization();
4312
if (pad < MAX_REQUEST && is_initialized(m)) {
4313
pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
4315
if (m->topsize > pad) {
4316
/* Shrink top space in granularity-size units, keeping at least one */
4317
size_t unit = mparams.granularity;
4318
size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
4320
msegmentptr sp = segment_holding(m, (char*)m->top);
4322
if (!is_extern_segment(sp)) {
4323
if (is_mmapped_segment(sp)) {
4325
sp->size >= extra &&
4326
!has_segment_link(m, sp)) { /* can't shrink if pinned */
4327
size_t newsize = sp->size - extra;
4328
(void)newsize; /* placate people compiling -Wunused-variable */
4329
/* Prefer mremap, fall back to munmap */
4330
if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
4331
(CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
4336
else if (HAVE_MORECORE) {
4337
if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
4338
extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
4339
ACQUIRE_MALLOC_GLOBAL_LOCK();
4341
/* Make sure end of memory is where we last set it. */
4342
char* old_br = (char*)(CALL_MORECORE(0));
4343
if (old_br == sp->base + sp->size) {
4344
char* rel_br = (char*)(CALL_MORECORE(-extra));
4345
char* new_br = (char*)(CALL_MORECORE(0));
4346
if (rel_br != CMFAIL && new_br < old_br)
4347
released = old_br - new_br;
4350
RELEASE_MALLOC_GLOBAL_LOCK();
4354
if (released != 0) {
4355
sp->size -= released;
4356
m->footprint -= released;
4357
init_top(m, m->top, m->topsize - released);
4358
check_top_chunk(m, m->top);
4362
/* Unmap any unused mmapped segments */
4364
released += release_unused_segments(m);
4366
/* On failure, disable autotrim to avoid repeated failed future calls */
4367
if (released == 0 && m->topsize > m->trim_check)
4368
m->trim_check = MAX_SIZE_T;
4371
return (released != 0)? 1 : 0;
4374
/* Consolidate and bin a chunk. Differs from exported versions
4375
of free mainly in that the chunk need not be marked as inuse.
4377
static void dispose_chunk(mstate m, mchunkptr p, size_t psize) {
4378
mchunkptr next = chunk_plus_offset(p, psize);
4381
size_t prevsize = p->prev_foot;
4382
if (is_mmapped(p)) {
4383
psize += prevsize + MMAP_FOOT_PAD;
4384
if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4385
m->footprint -= psize;
4388
prev = chunk_minus_offset(p, prevsize);
4391
if (RTCHECK(ok_address(m, prev))) { /* consolidate backward */
4393
unlink_chunk(m, p, prevsize);
4395
else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4397
set_free_with_pinuse(p, psize, next);
4402
CORRUPTION_ERROR_ACTION(m);
4406
if (RTCHECK(ok_address(m, next))) {
4407
if (!cinuse(next)) { /* consolidate forward */
4408
if (next == m->top) {
4409
size_t tsize = m->topsize += psize;
4411
p->head = tsize | PINUSE_BIT;
4418
else if (next == m->dv) {
4419
size_t dsize = m->dvsize += psize;
4421
set_size_and_pinuse_of_free_chunk(p, dsize);
4425
size_t nsize = chunksize(next);
4427
unlink_chunk(m, next, nsize);
4428
set_size_and_pinuse_of_free_chunk(p, psize);
4436
set_free_with_pinuse(p, psize, next);
4438
insert_chunk(m, p, psize);
4441
CORRUPTION_ERROR_ACTION(m);
4445
/* ---------------------------- malloc --------------------------- */
4447
/* allocate a large request from the best fitting chunk in a treebin */
4448
static void* tmalloc_large(mstate m, size_t nb) {
4450
size_t rsize = -nb; /* Unsigned negation */
4453
compute_tree_index(nb, idx);
4454
if ((t = *treebin_at(m, idx)) != 0) {
4455
/* Traverse tree for this bin looking for node with size == nb */
4456
size_t sizebits = nb << leftshift_for_tree_index(idx);
4457
tchunkptr rst = 0; /* The deepest untaken right subtree */
4460
size_t trem = chunksize(t) - nb;
4463
if ((rsize = trem) == 0)
4467
t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
4468
if (rt != 0 && rt != t)
4471
t = rst; /* set t to least subtree holding sizes > nb */
4477
if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
4478
binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
4479
if (leftbits != 0) {
4481
binmap_t leastbit = least_bit(leftbits);
4482
compute_bit2idx(leastbit, i);
4483
t = *treebin_at(m, i);
4487
while (t != 0) { /* find smallest of tree or subtree */
4488
size_t trem = chunksize(t) - nb;
4493
t = leftmost_child(t);
4496
/* If dv is a better fit, return 0 so malloc will use it */
4497
if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
4498
if (RTCHECK(ok_address(m, v))) { /* split */
4499
mchunkptr r = chunk_plus_offset(v, nb);
4500
assert(chunksize(v) == rsize + nb);
4501
if (RTCHECK(ok_next(v, r))) {
4502
unlink_large_chunk(m, v);
4503
if (rsize < MIN_CHUNK_SIZE)
4504
set_inuse_and_pinuse(m, v, (rsize + nb));
4506
set_size_and_pinuse_of_inuse_chunk(m, v, nb);
4507
set_size_and_pinuse_of_free_chunk(r, rsize);
4508
insert_chunk(m, r, rsize);
4510
return chunk2mem(v);
4513
CORRUPTION_ERROR_ACTION(m);
4518
/* allocate a small request from the best fitting chunk in a treebin */
4519
static void* tmalloc_small(mstate m, size_t nb) {
4523
binmap_t leastbit = least_bit(m->treemap);
4524
compute_bit2idx(leastbit, i);
4525
v = t = *treebin_at(m, i);
4526
rsize = chunksize(t) - nb;
4528
while ((t = leftmost_child(t)) != 0) {
4529
size_t trem = chunksize(t) - nb;
4536
if (RTCHECK(ok_address(m, v))) {
4537
mchunkptr r = chunk_plus_offset(v, nb);
4538
assert(chunksize(v) == rsize + nb);
4539
if (RTCHECK(ok_next(v, r))) {
4540
unlink_large_chunk(m, v);
4541
if (rsize < MIN_CHUNK_SIZE)
4542
set_inuse_and_pinuse(m, v, (rsize + nb));
4544
set_size_and_pinuse_of_inuse_chunk(m, v, nb);
4545
set_size_and_pinuse_of_free_chunk(r, rsize);
4546
replace_dv(m, r, rsize);
4548
return chunk2mem(v);
4552
CORRUPTION_ERROR_ACTION(m);
4558
void* dlmalloc(size_t bytes) {
4561
If a small request (< 256 bytes minus per-chunk overhead):
4562
1. If one exists, use a remainderless chunk in associated smallbin.
4563
(Remainderless means that there are too few excess bytes to
4564
represent as a chunk.)
4565
2. If it is big enough, use the dv chunk, which is normally the
4566
chunk adjacent to the one used for the most recent small request.
4567
3. If one exists, split the smallest available chunk in a bin,
4568
saving remainder in dv.
4569
4. If it is big enough, use the top chunk.
4570
5. If available, get memory from system and use it
4571
Otherwise, for a large request:
4572
1. Find the smallest available binned chunk that fits, and use it
4573
if it is better fitting than dv chunk, splitting if necessary.
4574
2. If better fitting than any binned chunk, use the dv chunk.
4575
3. If it is big enough, use the top chunk.
4576
4. If request size >= mmap threshold, try to directly mmap this chunk.
4577
5. If available, get memory from system and use it
4579
The ugly goto's here ensure that postaction occurs along all paths.
4583
ensure_initialization(); /* initialize in sys_alloc if not using locks */
4586
if (!PREACTION(gm)) {
4589
if (bytes <= MAX_SMALL_REQUEST) {
4592
nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
4593
idx = small_index(nb);
4594
smallbits = gm->smallmap >> idx;
4596
if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
4598
idx += ~smallbits & 1; /* Uses next bin if idx empty */
4599
b = smallbin_at(gm, idx);
4601
assert(chunksize(p) == small_index2size(idx));
4602
unlink_first_small_chunk(gm, b, p, idx);
4603
set_inuse_and_pinuse(gm, p, small_index2size(idx));
4605
check_malloced_chunk(gm, mem, nb);
4609
else if (nb > gm->dvsize) {
4610
if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
4614
binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4615
binmap_t leastbit = least_bit(leftbits);
4616
compute_bit2idx(leastbit, i);
4617
b = smallbin_at(gm, i);
4619
assert(chunksize(p) == small_index2size(i));
4620
unlink_first_small_chunk(gm, b, p, i);
4621
rsize = small_index2size(i) - nb;
4622
/* Fit here cannot be remainderless if 4byte sizes */
4623
if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4624
set_inuse_and_pinuse(gm, p, small_index2size(i));
4626
set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4627
r = chunk_plus_offset(p, nb);
4628
set_size_and_pinuse_of_free_chunk(r, rsize);
4629
replace_dv(gm, r, rsize);
4632
check_malloced_chunk(gm, mem, nb);
4636
else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
4637
check_malloced_chunk(gm, mem, nb);
4642
else if (bytes >= MAX_REQUEST)
4643
nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
4645
nb = pad_request(bytes);
4646
if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
4647
check_malloced_chunk(gm, mem, nb);
4652
if (nb <= gm->dvsize) {
4653
size_t rsize = gm->dvsize - nb;
4654
mchunkptr p = gm->dv;
4655
if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4656
mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
4658
set_size_and_pinuse_of_free_chunk(r, rsize);
4659
set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4661
else { /* exhaust dv */
4662
size_t dvs = gm->dvsize;
4665
set_inuse_and_pinuse(gm, p, dvs);
4668
check_malloced_chunk(gm, mem, nb);
4672
else if (nb < gm->topsize) { /* Split top */
4673
size_t rsize = gm->topsize -= nb;
4674
mchunkptr p = gm->top;
4675
mchunkptr r = gm->top = chunk_plus_offset(p, nb);
4676
r->head = rsize | PINUSE_BIT;
4677
set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4679
check_top_chunk(gm, gm->top);
4680
check_malloced_chunk(gm, mem, nb);
4684
mem = sys_alloc(gm, nb);
4694
/* ---------------------------- free --------------------------- */
4696
void dlfree(void* mem) {
4698
Consolidate freed chunks with preceeding or succeeding bordering
4699
free chunks, if they exist, and then place in a bin. Intermixed
4700
with special cases for top, dv, mmapped chunks, and usage errors.
4704
mchunkptr p = mem2chunk(mem);
4706
mstate fm = get_mstate_for(p);
4707
if (!ok_magic(fm)) {
4708
USAGE_ERROR_ACTION(fm, p);
4713
#endif /* FOOTERS */
4714
if (!PREACTION(fm)) {
4715
check_inuse_chunk(fm, p);
4716
if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
4717
size_t psize = chunksize(p);
4718
mchunkptr next = chunk_plus_offset(p, psize);
4720
size_t prevsize = p->prev_foot;
4721
if (is_mmapped(p)) {
4722
psize += prevsize + MMAP_FOOT_PAD;
4723
if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4724
fm->footprint -= psize;
4728
mchunkptr prev = chunk_minus_offset(p, prevsize);
4731
if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4733
unlink_chunk(fm, p, prevsize);
4735
else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4737
set_free_with_pinuse(p, psize, next);
4746
if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
4747
if (!cinuse(next)) { /* consolidate forward */
4748
if (next == fm->top) {
4749
size_t tsize = fm->topsize += psize;
4751
p->head = tsize | PINUSE_BIT;
4756
if (should_trim(fm, tsize))
4760
else if (next == fm->dv) {
4761
size_t dsize = fm->dvsize += psize;
4763
set_size_and_pinuse_of_free_chunk(p, dsize);
4767
size_t nsize = chunksize(next);
4769
unlink_chunk(fm, next, nsize);
4770
set_size_and_pinuse_of_free_chunk(p, psize);
4778
set_free_with_pinuse(p, psize, next);
4780
if (is_small(psize)) {
4781
insert_small_chunk(fm, p, psize);
4782
check_free_chunk(fm, p);
4785
tchunkptr tp = (tchunkptr)p;
4786
insert_large_chunk(fm, tp, psize);
4787
check_free_chunk(fm, p);
4788
if (--fm->release_checks == 0)
4789
release_unused_segments(fm);
4795
USAGE_ERROR_ACTION(fm, p);
4802
#endif /* FOOTERS */
4805
void* dlcalloc(size_t n_elements, size_t elem_size) {
4808
if (n_elements != 0) {
4809
req = n_elements * elem_size;
4810
if (((n_elements | elem_size) & ~(size_t)0xffff) &&
4811
(req / n_elements != elem_size))
4812
req = MAX_SIZE_T; /* force downstream failure on overflow */
4814
mem = dlmalloc(req);
4815
if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
4816
memset(mem, 0, req);
4820
#endif /* !ONLY_MSPACES */
4822
/* ------------ Internal support for realloc, memalign, etc -------------- */
4824
/* Try to realloc; only in-place unless can_move true */
4825
static mchunkptr try_realloc_chunk(mstate m, mchunkptr p, size_t nb,
4828
size_t oldsize = chunksize(p);
4829
mchunkptr next = chunk_plus_offset(p, oldsize);
4830
if (RTCHECK(ok_address(m, p) && ok_inuse(p) &&
4831
ok_next(p, next) && ok_pinuse(next))) {
4832
if (is_mmapped(p)) {
4833
newp = mmap_resize(m, p, nb, can_move);
4835
else if (oldsize >= nb) { /* already big enough */
4836
size_t rsize = oldsize - nb;
4837
if (rsize >= MIN_CHUNK_SIZE) { /* split off remainder */
4838
mchunkptr r = chunk_plus_offset(p, nb);
4839
set_inuse(m, p, nb);
4840
set_inuse(m, r, rsize);
4841
dispose_chunk(m, r, rsize);
4845
else if (next == m->top) { /* extend into top */
4846
if (oldsize + m->topsize > nb) {
4847
size_t newsize = oldsize + m->topsize;
4848
size_t newtopsize = newsize - nb;
4849
mchunkptr newtop = chunk_plus_offset(p, nb);
4850
set_inuse(m, p, nb);
4851
newtop->head = newtopsize |PINUSE_BIT;
4853
m->topsize = newtopsize;
4857
else if (next == m->dv) { /* extend into dv */
4858
size_t dvs = m->dvsize;
4859
if (oldsize + dvs >= nb) {
4860
size_t dsize = oldsize + dvs - nb;
4861
if (dsize >= MIN_CHUNK_SIZE) {
4862
mchunkptr r = chunk_plus_offset(p, nb);
4863
mchunkptr n = chunk_plus_offset(r, dsize);
4864
set_inuse(m, p, nb);
4865
set_size_and_pinuse_of_free_chunk(r, dsize);
4870
else { /* exhaust dv */
4871
size_t newsize = oldsize + dvs;
4872
set_inuse(m, p, newsize);
4879
else if (!cinuse(next)) { /* extend into next free chunk */
4880
size_t nextsize = chunksize(next);
4881
if (oldsize + nextsize >= nb) {
4882
size_t rsize = oldsize + nextsize - nb;
4883
unlink_chunk(m, next, nextsize);
4884
if (rsize < MIN_CHUNK_SIZE) {
4885
size_t newsize = oldsize + nextsize;
4886
set_inuse(m, p, newsize);
4889
mchunkptr r = chunk_plus_offset(p, nb);
4890
set_inuse(m, p, nb);
4891
set_inuse(m, r, rsize);
4892
dispose_chunk(m, r, rsize);
4899
USAGE_ERROR_ACTION(m, chunk2mem(p));
4904
static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
4906
if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
4907
alignment = MIN_CHUNK_SIZE;
4908
if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
4909
size_t a = MALLOC_ALIGNMENT << 1;
4910
while (a < alignment) a <<= 1;
4913
if (bytes >= MAX_REQUEST - alignment) {
4914
if (m != 0) { /* Test isn't needed but avoids compiler warning */
4915
MALLOC_FAILURE_ACTION;
4919
size_t nb = request2size(bytes);
4920
size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
4921
mem = internal_malloc(m, req);
4923
mchunkptr p = mem2chunk(mem);
4926
if ((((size_t)(mem)) & (alignment - 1)) != 0) { /* misaligned */
4928
Find an aligned spot inside chunk. Since we need to give
4929
back leading space in a chunk of at least MIN_CHUNK_SIZE, if
4930
the first calculation places us at a spot with less than
4931
MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
4932
We've allocated enough total room so that this is always
4935
char* br = (char*)mem2chunk((size_t)(((size_t)((char*)mem + alignment -
4938
char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
4940
mchunkptr newp = (mchunkptr)pos;
4941
size_t leadsize = pos - (char*)(p);
4942
size_t newsize = chunksize(p) - leadsize;
4944
if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */
4945
newp->prev_foot = p->prev_foot + leadsize;
4946
newp->head = newsize;
4948
else { /* Otherwise, give back leader, use the rest */
4949
set_inuse(m, newp, newsize);
4950
set_inuse(m, p, leadsize);
4951
dispose_chunk(m, p, leadsize);
4956
/* Give back spare room at the end */
4957
if (!is_mmapped(p)) {
4958
size_t size = chunksize(p);
4959
if (size > nb + MIN_CHUNK_SIZE) {
4960
size_t remainder_size = size - nb;
4961
mchunkptr remainder = chunk_plus_offset(p, nb);
4962
set_inuse(m, p, nb);
4963
set_inuse(m, remainder, remainder_size);
4964
dispose_chunk(m, remainder, remainder_size);
4969
assert (chunksize(p) >= nb);
4970
assert(((size_t)mem & (alignment - 1)) == 0);
4971
check_inuse_chunk(m, p);
4979
Common support for independent_X routines, handling
4980
all of the combinations that can result.
4982
bit 0 set if all elements are same size (using sizes[0])
4983
bit 1 set if elements should be zeroed
4985
static void** ialloc(mstate m,
4991
size_t element_size; /* chunksize of each element, if all same */
4992
size_t contents_size; /* total size of elements */
4993
size_t array_size; /* request size of pointer array */
4994
void* mem; /* malloced aggregate space */
4995
mchunkptr p; /* corresponding chunk */
4996
size_t remainder_size; /* remaining bytes while splitting */
4997
void** marray; /* either "chunks" or malloced ptr array */
4998
mchunkptr array_chunk; /* chunk for malloced ptr array */
4999
flag_t was_enabled; /* to disable mmap */
5003
ensure_initialization();
5004
/* compute array length, if needed */
5006
if (n_elements == 0)
5007
return chunks; /* nothing to do */
5012
/* if empty req, must still return chunk representing empty array */
5013
if (n_elements == 0)
5014
return (void**)internal_malloc(m, 0);
5016
array_size = request2size(n_elements * (sizeof(void*)));
5019
/* compute total element size */
5020
if (opts & 0x1) { /* all-same-size */
5021
element_size = request2size(*sizes);
5022
contents_size = n_elements * element_size;
5024
else { /* add up all the sizes */
5027
for (i = 0; i != n_elements; ++i)
5028
contents_size += request2size(sizes[i]);
5031
size = contents_size + array_size;
5034
Allocate the aggregate chunk. First disable direct-mmapping so
5035
malloc won't use it, since we would not be able to later
5036
free/realloc space internal to a segregated mmap region.
5038
was_enabled = use_mmap(m);
5040
mem = internal_malloc(m, size - CHUNK_OVERHEAD);
5046
if (PREACTION(m)) return 0;
5048
remainder_size = chunksize(p);
5050
assert(!is_mmapped(p));
5052
if (opts & 0x2) { /* optionally clear the elements */
5053
memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);
5056
/* If not provided, allocate the pointer array as final part of chunk */
5058
size_t array_chunk_size;
5059
array_chunk = chunk_plus_offset(p, contents_size);
5060
array_chunk_size = remainder_size - contents_size;
5061
marray = (void**) (chunk2mem(array_chunk));
5062
set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);
5063
remainder_size = contents_size;
5066
/* split out elements */
5067
for (i = 0; ; ++i) {
5068
marray[i] = chunk2mem(p);
5069
if (i != n_elements-1) {
5070
if (element_size != 0)
5071
size = element_size;
5073
size = request2size(sizes[i]);
5074
remainder_size -= size;
5075
set_size_and_pinuse_of_inuse_chunk(m, p, size);
5076
p = chunk_plus_offset(p, size);
5078
else { /* the final element absorbs any overallocation slop */
5079
set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);
5085
if (marray != chunks) {
5086
/* final element must have exactly exhausted chunk */
5087
if (element_size != 0) {
5088
assert(remainder_size == element_size);
5091
assert(remainder_size == request2size(sizes[i]));
5093
check_inuse_chunk(m, mem2chunk(marray));
5095
for (i = 0; i != n_elements; ++i)
5096
check_inuse_chunk(m, mem2chunk(marray[i]));
5104
/* Try to free all pointers in the given array.
5105
Note: this could be made faster, by delaying consolidation,
5106
at the price of disabling some user integrity checks, We
5107
still optimize some consolidations by combining adjacent
5108
chunks before freeing, which will occur often if allocated
5109
with ialloc or the array is sorted.
5111
static size_t internal_bulk_free(mstate m, void* array[], size_t nelem) {
5113
if (!PREACTION(m)) {
5115
void** fence = &(array[nelem]);
5116
for (a = array; a != fence; ++a) {
5119
mchunkptr p = mem2chunk(mem);
5120
size_t psize = chunksize(p);
5122
if (get_mstate_for(p) != m) {
5127
check_inuse_chunk(m, p);
5129
if (RTCHECK(ok_address(m, p) && ok_inuse(p))) {
5130
void ** b = a + 1; /* try to merge with next chunk */
5131
mchunkptr next = next_chunk(p);
5132
if (b != fence && *b == chunk2mem(next)) {
5133
size_t newsize = chunksize(next) + psize;
5134
set_inuse(m, p, newsize);
5138
dispose_chunk(m, p, psize);
5141
CORRUPTION_ERROR_ACTION(m);
5146
if (should_trim(m, m->topsize))
5154
#if MALLOC_INSPECT_ALL
5155
static void internal_inspect_all(mstate m,
5156
void(*handler)(void *start,
5159
void* callback_arg),
5161
if (is_initialized(m)) {
5162
mchunkptr top = m->top;
5164
for (s = &m->seg; s != 0; s = s->next) {
5165
mchunkptr q = align_as_chunk(s->base);
5166
while (segment_holds(s, q) && q->head != FENCEPOST_HEAD) {
5167
mchunkptr next = next_chunk(q);
5168
size_t sz = chunksize(q);
5172
used = sz - CHUNK_OVERHEAD; /* must not be mmapped */
5173
start = chunk2mem(q);
5177
if (is_small(sz)) { /* offset by possible bookkeeping */
5178
start = (void*)((char*)q + sizeof(struct malloc_chunk));
5181
start = (void*)((char*)q + sizeof(struct malloc_tree_chunk));
5184
if (start < (void*)next) /* skip if all space is bookkeeping */
5185
handler(start, next, used, arg);
5193
#endif /* MALLOC_INSPECT_ALL */
5195
/* ------------------ Exported realloc, memalign, etc -------------------- */
5199
void* dlrealloc(void* oldmem, size_t bytes) {
5202
mem = dlmalloc(bytes);
5204
else if (bytes >= MAX_REQUEST) {
5205
MALLOC_FAILURE_ACTION;
5207
#ifdef REALLOC_ZERO_BYTES_FREES
5208
else if (bytes == 0) {
5211
#endif /* REALLOC_ZERO_BYTES_FREES */
5213
size_t nb = request2size(bytes);
5214
mchunkptr oldp = mem2chunk(oldmem);
5218
mstate m = get_mstate_for(oldp);
5220
USAGE_ERROR_ACTION(m, oldmem);
5223
#endif /* FOOTERS */
5224
if (!PREACTION(m)) {
5225
mchunkptr newp = try_realloc_chunk(m, oldp, nb, 1);
5228
check_inuse_chunk(m, newp);
5229
mem = chunk2mem(newp);
5232
mem = internal_malloc(m, bytes);
5234
size_t oc = chunksize(oldp) - overhead_for(oldp);
5235
memcpy(mem, oldmem, (oc < bytes)? oc : bytes);
5236
internal_free(m, oldmem);
5244
void* dlrealloc_in_place(void* oldmem, size_t bytes) {
5247
if (bytes >= MAX_REQUEST) {
5248
MALLOC_FAILURE_ACTION;
5251
size_t nb = request2size(bytes);
5252
mchunkptr oldp = mem2chunk(oldmem);
5256
mstate m = get_mstate_for(oldp);
5258
USAGE_ERROR_ACTION(m, oldmem);
5261
#endif /* FOOTERS */
5262
if (!PREACTION(m)) {
5263
mchunkptr newp = try_realloc_chunk(m, oldp, nb, 0);
5266
check_inuse_chunk(m, newp);
5275
void* dlmemalign(size_t alignment, size_t bytes) {
5276
if (alignment <= MALLOC_ALIGNMENT) {
5277
return dlmalloc(bytes);
5279
return internal_memalign(gm, alignment, bytes);
5282
int dlposix_memalign(void** pp, size_t alignment, size_t bytes) {
5284
if (alignment == MALLOC_ALIGNMENT)
5285
mem = dlmalloc(bytes);
5287
size_t d = alignment / sizeof(void*);
5288
size_t r = alignment % sizeof(void*);
5289
if (r != 0 || d == 0 || (d & (d-SIZE_T_ONE)) != 0)
5291
else if (bytes <= MAX_REQUEST - alignment) {
5292
if (alignment < MIN_CHUNK_SIZE)
5293
alignment = MIN_CHUNK_SIZE;
5294
mem = internal_memalign(gm, alignment, bytes);
5305
void* dlvalloc(size_t bytes) {
5307
ensure_initialization();
5308
pagesz = mparams.page_size;
5309
return dlmemalign(pagesz, bytes);
5312
void* dlpvalloc(size_t bytes) {
5314
ensure_initialization();
5315
pagesz = mparams.page_size;
5316
return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));
5319
void** dlindependent_calloc(size_t n_elements, size_t elem_size,
5321
size_t sz = elem_size; /* serves as 1-element array */
5322
return ialloc(gm, n_elements, &sz, 3, chunks);
5325
void** dlindependent_comalloc(size_t n_elements, size_t sizes[],
5327
return ialloc(gm, n_elements, sizes, 0, chunks);
5330
size_t dlbulk_free(void* array[], size_t nelem) {
5331
return internal_bulk_free(gm, array, nelem);
5334
#if MALLOC_INSPECT_ALL
5335
void dlmalloc_inspect_all(void(*handler)(void *start,
5338
void* callback_arg),
5340
ensure_initialization();
5341
if (!PREACTION(gm)) {
5342
internal_inspect_all(gm, handler, arg);
5346
#endif /* MALLOC_INSPECT_ALL */
5348
int dlmalloc_trim(size_t pad) {
5350
ensure_initialization();
5351
if (!PREACTION(gm)) {
5352
result = sys_trim(gm, pad);
5358
size_t dlmalloc_footprint(void) {
5359
return gm->footprint;
5362
size_t dlmalloc_max_footprint(void) {
5363
return gm->max_footprint;
5366
size_t dlmalloc_footprint_limit(void) {
5367
size_t maf = gm->footprint_limit;
5368
return maf == 0 ? MAX_SIZE_T : maf;
5371
size_t dlmalloc_set_footprint_limit(size_t bytes) {
5372
size_t result; /* invert sense of 0 */
5374
result = granularity_align(1); /* Use minimal size */
5375
if (bytes == MAX_SIZE_T)
5376
result = 0; /* disable */
5378
result = granularity_align(bytes);
5379
return gm->footprint_limit = result;
5383
struct mallinfo dlmallinfo(void) {
5384
return internal_mallinfo(gm);
5386
#endif /* NO_MALLINFO */
5388
#if !NO_MALLOC_STATS
5389
void dlmalloc_stats() {
5390
internal_malloc_stats(gm);
5392
#endif /* NO_MALLOC_STATS */
5394
int dlmallopt(int param_number, int value) {
5395
return change_mparam(param_number, value);
5398
size_t dlmalloc_usable_size(void* mem) {
5400
mchunkptr p = mem2chunk(mem);
5402
return chunksize(p) - overhead_for(p);
5407
#endif /* !ONLY_MSPACES */
5409
/* ----------------------------- user mspaces ---------------------------- */
5413
static mstate init_user_mstate(char* tbase, size_t tsize) {
5414
size_t msize = pad_request(sizeof(struct malloc_state));
5416
mchunkptr msp = align_as_chunk(tbase);
5417
mstate m = (mstate)(chunk2mem(msp));
5418
memset(m, 0, msize);
5419
(void)INITIAL_LOCK(&m->mutex);
5420
msp->head = (msize|INUSE_BITS);
5421
m->seg.base = m->least_addr = tbase;
5422
m->seg.size = m->footprint = m->max_footprint = tsize;
5423
m->magic = mparams.magic;
5424
m->release_checks = MAX_RELEASE_CHECK_RATE;
5425
m->mflags = mparams.default_mflags;
5428
disable_contiguous(m);
5430
mn = next_chunk(mem2chunk(m));
5431
init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
5432
check_top_chunk(m, m->top);
5436
mspace create_mspace(size_t capacity, int locked) {
5439
ensure_initialization();
5440
msize = pad_request(sizeof(struct malloc_state));
5441
if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
5442
size_t rs = ((capacity == 0)? mparams.granularity :
5443
(capacity + TOP_FOOT_SIZE + msize));
5444
size_t tsize = granularity_align(rs);
5445
char* tbase = (char*)(CALL_MMAP(tsize));
5446
if (tbase != CMFAIL) {
5447
m = init_user_mstate(tbase, tsize);
5448
m->seg.sflags = USE_MMAP_BIT;
5449
set_lock(m, locked);
5455
mspace create_mspace_with_base(void* base, size_t capacity, int locked) {
5458
ensure_initialization();
5459
msize = pad_request(sizeof(struct malloc_state));
5460
if (capacity > msize + TOP_FOOT_SIZE &&
5461
capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
5462
m = init_user_mstate((char*)base, capacity);
5463
m->seg.sflags = EXTERN_BIT;
5464
set_lock(m, locked);
5469
int mspace_track_large_chunks(mspace msp, int enable) {
5471
mstate ms = (mstate)msp;
5472
if (!PREACTION(ms)) {
5473
if (!use_mmap(ms)) {
5486
size_t destroy_mspace(mspace msp) {
5488
mstate ms = (mstate)msp;
5490
msegmentptr sp = &ms->seg;
5491
(void)DESTROY_LOCK(&ms->mutex); /* destroy before unmapped */
5493
char* base = sp->base;
5494
size_t size = sp->size;
5495
flag_t flag = sp->sflags;
5496
(void)base; /* placate people compiling -Wunused-variable */
5498
if ((flag & USE_MMAP_BIT) && !(flag & EXTERN_BIT) &&
5499
CALL_MUNMAP(base, size) == 0)
5504
USAGE_ERROR_ACTION(ms,ms);
5510
mspace versions of routines are near-clones of the global
5511
versions. This is not so nice but better than the alternatives.
5514
void* mspace_malloc(mspace msp, size_t bytes) {
5515
mstate ms = (mstate)msp;
5516
if (!ok_magic(ms)) {
5517
USAGE_ERROR_ACTION(ms,ms);
5520
if (!PREACTION(ms)) {
5523
if (bytes <= MAX_SMALL_REQUEST) {
5526
nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
5527
idx = small_index(nb);
5528
smallbits = ms->smallmap >> idx;
5530
if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
5532
idx += ~smallbits & 1; /* Uses next bin if idx empty */
5533
b = smallbin_at(ms, idx);
5535
assert(chunksize(p) == small_index2size(idx));
5536
unlink_first_small_chunk(ms, b, p, idx);
5537
set_inuse_and_pinuse(ms, p, small_index2size(idx));
5539
check_malloced_chunk(ms, mem, nb);
5543
else if (nb > ms->dvsize) {
5544
if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
5548
binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
5549
binmap_t leastbit = least_bit(leftbits);
5550
compute_bit2idx(leastbit, i);
5551
b = smallbin_at(ms, i);
5553
assert(chunksize(p) == small_index2size(i));
5554
unlink_first_small_chunk(ms, b, p, i);
5555
rsize = small_index2size(i) - nb;
5556
/* Fit here cannot be remainderless if 4byte sizes */
5557
if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
5558
set_inuse_and_pinuse(ms, p, small_index2size(i));
5560
set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
5561
r = chunk_plus_offset(p, nb);
5562
set_size_and_pinuse_of_free_chunk(r, rsize);
5563
replace_dv(ms, r, rsize);
5566
check_malloced_chunk(ms, mem, nb);
5570
else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
5571
check_malloced_chunk(ms, mem, nb);
5576
else if (bytes >= MAX_REQUEST)
5577
nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
5579
nb = pad_request(bytes);
5580
if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
5581
check_malloced_chunk(ms, mem, nb);
5586
if (nb <= ms->dvsize) {
5587
size_t rsize = ms->dvsize - nb;
5588
mchunkptr p = ms->dv;
5589
if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
5590
mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
5592
set_size_and_pinuse_of_free_chunk(r, rsize);
5593
set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
5595
else { /* exhaust dv */
5596
size_t dvs = ms->dvsize;
5599
set_inuse_and_pinuse(ms, p, dvs);
5602
check_malloced_chunk(ms, mem, nb);
5606
else if (nb < ms->topsize) { /* Split top */
5607
size_t rsize = ms->topsize -= nb;
5608
mchunkptr p = ms->top;
5609
mchunkptr r = ms->top = chunk_plus_offset(p, nb);
5610
r->head = rsize | PINUSE_BIT;
5611
set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
5613
check_top_chunk(ms, ms->top);
5614
check_malloced_chunk(ms, mem, nb);
5618
mem = sys_alloc(ms, nb);
5628
void mspace_free(mspace msp, void* mem) {
5630
mchunkptr p = mem2chunk(mem);
5632
mstate fm = get_mstate_for(p);
5633
(void)msp; /* placate people compiling -Wunused */
5635
mstate fm = (mstate)msp;
5636
#endif /* FOOTERS */
5637
if (!ok_magic(fm)) {
5638
USAGE_ERROR_ACTION(fm, p);
5641
if (!PREACTION(fm)) {
5642
check_inuse_chunk(fm, p);
5643
if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
5644
size_t psize = chunksize(p);
5645
mchunkptr next = chunk_plus_offset(p, psize);
5647
size_t prevsize = p->prev_foot;
5648
if (is_mmapped(p)) {
5649
psize += prevsize + MMAP_FOOT_PAD;
5650
if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
5651
fm->footprint -= psize;
5655
mchunkptr prev = chunk_minus_offset(p, prevsize);
5658
if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
5660
unlink_chunk(fm, p, prevsize);
5662
else if ((next->head & INUSE_BITS) == INUSE_BITS) {
5664
set_free_with_pinuse(p, psize, next);
5673
if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
5674
if (!cinuse(next)) { /* consolidate forward */
5675
if (next == fm->top) {
5676
size_t tsize = fm->topsize += psize;
5678
p->head = tsize | PINUSE_BIT;
5683
if (should_trim(fm, tsize))
5687
else if (next == fm->dv) {
5688
size_t dsize = fm->dvsize += psize;
5690
set_size_and_pinuse_of_free_chunk(p, dsize);
5694
size_t nsize = chunksize(next);
5696
unlink_chunk(fm, next, nsize);
5697
set_size_and_pinuse_of_free_chunk(p, psize);
5705
set_free_with_pinuse(p, psize, next);
5707
if (is_small(psize)) {
5708
insert_small_chunk(fm, p, psize);
5709
check_free_chunk(fm, p);
5712
tchunkptr tp = (tchunkptr)p;
5713
insert_large_chunk(fm, tp, psize);
5714
check_free_chunk(fm, p);
5715
if (--fm->release_checks == 0)
5716
release_unused_segments(fm);
5722
USAGE_ERROR_ACTION(fm, p);
5729
void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
5732
mstate ms = (mstate)msp;
5733
if (!ok_magic(ms)) {
5734
USAGE_ERROR_ACTION(ms,ms);
5737
if (n_elements != 0) {
5738
req = n_elements * elem_size;
5739
if (((n_elements | elem_size) & ~(size_t)0xffff) &&
5740
(req / n_elements != elem_size))
5741
req = MAX_SIZE_T; /* force downstream failure on overflow */
5743
mem = internal_malloc(ms, req);
5744
if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
5745
memset(mem, 0, req);
5749
void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
5752
mem = mspace_malloc(msp, bytes);
5754
else if (bytes >= MAX_REQUEST) {
5755
MALLOC_FAILURE_ACTION;
5757
#ifdef REALLOC_ZERO_BYTES_FREES
5758
else if (bytes == 0) {
5759
mspace_free(msp, oldmem);
5761
#endif /* REALLOC_ZERO_BYTES_FREES */
5763
size_t nb = request2size(bytes);
5764
mchunkptr oldp = mem2chunk(oldmem);
5766
mstate m = (mstate)msp;
5768
mstate m = get_mstate_for(oldp);
5770
USAGE_ERROR_ACTION(m, oldmem);
5773
#endif /* FOOTERS */
5774
if (!PREACTION(m)) {
5775
mchunkptr newp = try_realloc_chunk(m, oldp, nb, 1);
5778
check_inuse_chunk(m, newp);
5779
mem = chunk2mem(newp);
5782
mem = mspace_malloc(m, bytes);
5784
size_t oc = chunksize(oldp) - overhead_for(oldp);
5785
memcpy(mem, oldmem, (oc < bytes)? oc : bytes);
5786
mspace_free(m, oldmem);
5794
void* mspace_realloc_in_place(mspace msp, void* oldmem, size_t bytes) {
5797
if (bytes >= MAX_REQUEST) {
5798
MALLOC_FAILURE_ACTION;
5801
size_t nb = request2size(bytes);
5802
mchunkptr oldp = mem2chunk(oldmem);
5804
mstate m = (mstate)msp;
5806
mstate m = get_mstate_for(oldp);
5807
(void)msp; /* placate people compiling -Wunused */
5809
USAGE_ERROR_ACTION(m, oldmem);
5812
#endif /* FOOTERS */
5813
if (!PREACTION(m)) {
5814
mchunkptr newp = try_realloc_chunk(m, oldp, nb, 0);
5817
check_inuse_chunk(m, newp);
5826
void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
5827
mstate ms = (mstate)msp;
5828
if (!ok_magic(ms)) {
5829
USAGE_ERROR_ACTION(ms,ms);
5832
if (alignment <= MALLOC_ALIGNMENT)
5833
return mspace_malloc(msp, bytes);
5834
return internal_memalign(ms, alignment, bytes);
5837
void** mspace_independent_calloc(mspace msp, size_t n_elements,
5838
size_t elem_size, void* chunks[]) {
5839
size_t sz = elem_size; /* serves as 1-element array */
5840
mstate ms = (mstate)msp;
5841
if (!ok_magic(ms)) {
5842
USAGE_ERROR_ACTION(ms,ms);
5845
return ialloc(ms, n_elements, &sz, 3, chunks);
5848
void** mspace_independent_comalloc(mspace msp, size_t n_elements,
5849
size_t sizes[], void* chunks[]) {
5850
mstate ms = (mstate)msp;
5851
if (!ok_magic(ms)) {
5852
USAGE_ERROR_ACTION(ms,ms);
5855
return ialloc(ms, n_elements, sizes, 0, chunks);
5858
size_t mspace_bulk_free(mspace msp, void* array[], size_t nelem) {
5859
return internal_bulk_free((mstate)msp, array, nelem);
5862
#if MALLOC_INSPECT_ALL
5863
void mspace_inspect_all(mspace msp,
5864
void(*handler)(void *start,
5867
void* callback_arg),
5869
mstate ms = (mstate)msp;
5871
if (!PREACTION(ms)) {
5872
internal_inspect_all(ms, handler, arg);
5877
USAGE_ERROR_ACTION(ms,ms);
5880
#endif /* MALLOC_INSPECT_ALL */
5882
int mspace_trim(mspace msp, size_t pad) {
5884
mstate ms = (mstate)msp;
5886
if (!PREACTION(ms)) {
5887
result = sys_trim(ms, pad);
5892
USAGE_ERROR_ACTION(ms,ms);
5897
#if !NO_MALLOC_STATS
5898
void mspace_malloc_stats(mspace msp) {
5899
mstate ms = (mstate)msp;
5901
internal_malloc_stats(ms);
5904
USAGE_ERROR_ACTION(ms,ms);
5907
#endif /* NO_MALLOC_STATS */
5909
size_t mspace_footprint(mspace msp) {
5911
mstate ms = (mstate)msp;
5913
result = ms->footprint;
5916
USAGE_ERROR_ACTION(ms,ms);
5921
size_t mspace_max_footprint(mspace msp) {
5923
mstate ms = (mstate)msp;
5925
result = ms->max_footprint;
5928
USAGE_ERROR_ACTION(ms,ms);
5933
size_t mspace_footprint_limit(mspace msp) {
5935
mstate ms = (mstate)msp;
5937
size_t maf = ms->footprint_limit;
5938
result = (maf == 0) ? MAX_SIZE_T : maf;
5941
USAGE_ERROR_ACTION(ms,ms);
5946
size_t mspace_set_footprint_limit(mspace msp, size_t bytes) {
5948
mstate ms = (mstate)msp;
5951
result = granularity_align(1); /* Use minimal size */
5952
if (bytes == MAX_SIZE_T)
5953
result = 0; /* disable */
5955
result = granularity_align(bytes);
5956
ms->footprint_limit = result;
5959
USAGE_ERROR_ACTION(ms,ms);
5965
struct mallinfo mspace_mallinfo(mspace msp) {
5966
mstate ms = (mstate)msp;
5967
if (!ok_magic(ms)) {
5968
USAGE_ERROR_ACTION(ms,ms);
5970
return internal_mallinfo(ms);
5972
#endif /* NO_MALLINFO */
5974
size_t mspace_usable_size(const void* mem) {
5976
mchunkptr p = mem2chunk(mem);
5978
return chunksize(p) - overhead_for(p);
5983
int mspace_mallopt(int param_number, int value) {
5984
return change_mparam(param_number, value);
5987
#endif /* MSPACES */
5990
/* -------------------- Alternative MORECORE functions ------------------- */
5993
Guidelines for creating a custom version of MORECORE:
5995
* For best performance, MORECORE should allocate in multiples of pagesize.
5996
* MORECORE may allocate more memory than requested. (Or even less,
5997
but this will usually result in a malloc failure.)
5998
* MORECORE must not allocate memory when given argument zero, but
5999
instead return one past the end address of memory from previous
6001
* For best performance, consecutive calls to MORECORE with positive
6002
arguments should return increasing addresses, indicating that
6003
space has been contiguously extended.
6004
* Even though consecutive calls to MORECORE need not return contiguous
6005
addresses, it must be OK for malloc'ed chunks to span multiple
6006
regions in those cases where they do happen to be contiguous.
6007
* MORECORE need not handle negative arguments -- it may instead
6008
just return MFAIL when given negative arguments.
6009
Negative arguments are always multiples of pagesize. MORECORE
6010
must not misinterpret negative args as large positive unsigned
6011
args. You can suppress all such calls from even occurring by defining
6012
MORECORE_CANNOT_TRIM,
6014
As an example alternative MORECORE, here is a custom allocator
6015
kindly contributed for pre-OSX macOS. It uses virtually but not
6016
necessarily physically contiguous non-paged memory (locked in,
6017
present and won't get swapped out). You can use it by uncommenting
6018
this section, adding some #includes, and setting up the appropriate
6021
#define MORECORE osMoreCore
6023
There is also a shutdown routine that should somehow be called for
6024
cleanup upon program exit.
6026
#define MAX_POOL_ENTRIES 100
6027
#define MINIMUM_MORECORE_SIZE (64 * 1024U)
6028
static int next_os_pool;
6029
void *our_os_pools[MAX_POOL_ENTRIES];
6031
void *osMoreCore(int size)
6034
static void *sbrk_top = 0;
6038
if (size < MINIMUM_MORECORE_SIZE)
6039
size = MINIMUM_MORECORE_SIZE;
6040
if (CurrentExecutionLevel() == kTaskLevel)
6041
ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
6044
return (void *) MFAIL;
6046
// save ptrs so they can be freed during cleanup
6047
our_os_pools[next_os_pool] = ptr;
6049
ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
6050
sbrk_top = (char *) ptr + size;
6055
// we don't currently support shrink behavior
6056
return (void *) MFAIL;
6064
// cleanup any allocated memory pools
6065
// called as last thing before shutting down driver
6067
void osCleanupMem(void)
6071
for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
6074
PoolDeallocate(*ptr);
6082
/* -----------------------------------------------------------------------
6084
v2.8.6 Wed Aug 29 06:57:58 2012 Doug Lea
6085
* fix bad comparison in dlposix_memalign
6086
* don't reuse adjusted asize in sys_alloc
6087
* add LOCK_AT_FORK -- thanks to Kirill Artamonov for the suggestion
6088
* reduce compiler warnings -- thanks to all who reported/suggested these
6090
v2.8.5 Sun May 22 10:26:02 2011 Doug Lea (dl at gee)
6091
* Always perform unlink checks unless INSECURE
6092
* Add posix_memalign.
6093
* Improve realloc to expand in more cases; expose realloc_in_place.
6094
Thanks to Peter Buhr for the suggestion.
6095
* Add footprint_limit, inspect_all, bulk_free. Thanks
6096
to Barry Hayes and others for the suggestions.
6097
* Internal refactorings to avoid calls while holding locks
6098
* Use non-reentrant locks by default. Thanks to Roland McGrath
6100
* Small fixes to mspace_destroy, reset_on_error.
6101
* Various configuration extensions/changes. Thanks
6102
to all who contributed these.
6104
V2.8.4a Thu Apr 28 14:39:43 2011 (dl at gee.cs.oswego.edu)
6105
* Update Creative Commons URL
6107
V2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee)
6108
* Use zeros instead of prev foot for is_mmapped
6109
* Add mspace_track_large_chunks; thanks to Jean Brouwers
6110
* Fix set_inuse in internal_realloc; thanks to Jean Brouwers
6111
* Fix insufficient sys_alloc padding when using 16byte alignment
6112
* Fix bad error check in mspace_footprint
6113
* Adaptations for ptmalloc; thanks to Wolfram Gloger.
6114
* Reentrant spin locks; thanks to Earl Chew and others
6115
* Win32 improvements; thanks to Niall Douglas and Earl Chew
6116
* Add NO_SEGMENT_TRAVERSAL and MAX_RELEASE_CHECK_RATE options
6117
* Extension hook in malloc_state
6118
* Various small adjustments to reduce warnings on some compilers
6119
* Various configuration extensions/changes for more platforms. Thanks
6120
to all who contributed these.
6122
V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee)
6123
* Add max_footprint functions
6124
* Ensure all appropriate literals are size_t
6125
* Fix conditional compilation problem for some #define settings
6126
* Avoid concatenating segments with the one provided
6127
in create_mspace_with_base
6128
* Rename some variables to avoid compiler shadowing warnings
6129
* Use explicit lock initialization.
6130
* Better handling of sbrk interference.
6131
* Simplify and fix segment insertion, trimming and mspace_destroy
6132
* Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
6133
* Thanks especially to Dennis Flanagan for help on these.
6135
V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee)
6136
* Fix memalign brace error.
6138
V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee)
6139
* Fix improper #endif nesting in C++
6140
* Add explicit casts needed for C++
6142
V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee)
6143
* Use trees for large bins
6145
* Use segments to unify sbrk-based and mmap-based system allocation,
6146
removing need for emulation on most platforms without sbrk.
6147
* Default safety checks
6148
* Optional footer checks. Thanks to William Robertson for the idea.
6149
* Internal code refactoring
6150
* Incorporate suggestions and platform-specific changes.
6151
Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
6152
Aaron Bachmann, Emery Berger, and others.
6153
* Speed up non-fastbin processing enough to remove fastbins.
6154
* Remove useless cfree() to avoid conflicts with other apps.
6155
* Remove internal memcpy, memset. Compilers handle builtins better.
6156
* Remove some options that no one ever used and rename others.
6158
V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee)
6159
* Fix malloc_state bitmap array misdeclaration
6161
V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
6162
* Allow tuning of FIRST_SORTED_BIN_SIZE
6163
* Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
6164
* Better detection and support for non-contiguousness of MORECORE.
6165
Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
6166
* Bypass most of malloc if no frees. Thanks To Emery Berger.
6167
* Fix freeing of old top non-contiguous chunk im sysmalloc.
6168
* Raised default trim and map thresholds to 256K.
6169
* Fix mmap-related #defines. Thanks to Lubos Lunak.
6170
* Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
6171
* Branch-free bin calculation
6172
* Default trim and mmap thresholds now 256K.
6174
V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
6175
* Introduce independent_comalloc and independent_calloc.
6176
Thanks to Michael Pachos for motivation and help.
6177
* Make optional .h file available
6178
* Allow > 2GB requests on 32bit systems.
6179
* new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
6180
Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
6182
* Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
6184
* memalign: check alignment arg
6185
* realloc: don't try to shift chunks backwards, since this
6186
leads to more fragmentation in some programs and doesn't
6187
seem to help in any others.
6188
* Collect all cases in malloc requiring system memory into sysmalloc
6189
* Use mmap as backup to sbrk
6190
* Place all internal state in malloc_state
6191
* Introduce fastbins (although similar to 2.5.1)
6192
* Many minor tunings and cosmetic improvements
6193
* Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
6194
* Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
6195
Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
6196
* Include errno.h to support default failure action.
6198
V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
6199
* return null for negative arguments
6200
* Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
6201
* Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
6202
(e.g. WIN32 platforms)
6203
* Cleanup header file inclusion for WIN32 platforms
6204
* Cleanup code to avoid Microsoft Visual C++ compiler complaints
6205
* Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
6206
memory allocation routines
6207
* Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
6208
* Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
6209
usage of 'assert' in non-WIN32 code
6210
* Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
6212
* Always call 'fREe()' rather than 'free()'
6214
V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
6215
* Fixed ordering problem with boundary-stamping
6217
V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
6218
* Added pvalloc, as recommended by H.J. Liu
6219
* Added 64bit pointer support mainly from Wolfram Gloger
6220
* Added anonymously donated WIN32 sbrk emulation
6221
* Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
6222
* malloc_extend_top: fix mask error that caused wastage after
6224
* Add linux mremap support code from HJ Liu
6226
V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
6227
* Integrated most documentation with the code.
6228
* Add support for mmap, with help from
6229
Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
6230
* Use last_remainder in more cases.
6231
* Pack bins using idea from colin@nyx10.cs.du.edu
6232
* Use ordered bins instead of best-fit threshhold
6233
* Eliminate block-local decls to simplify tracing and debugging.
6234
* Support another case of realloc via move into top
6235
* Fix error occuring when initial sbrk_base not word-aligned.
6236
* Rely on page size for units instead of SBRK_UNIT to
6237
avoid surprises about sbrk alignment conventions.
6238
* Add mallinfo, mallopt. Thanks to Raymond Nijssen
6239
(raymond@es.ele.tue.nl) for the suggestion.
6240
* Add `pad' argument to malloc_trim and top_pad mallopt parameter.
6241
* More precautions for cases where other routines call sbrk,
6242
courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
6243
* Added macros etc., allowing use in linux libc from
6244
H.J. Lu (hjl@gnu.ai.mit.edu)
6245
* Inverted this history list
6247
V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
6248
* Re-tuned and fixed to behave more nicely with V2.6.0 changes.
6249
* Removed all preallocation code since under current scheme
6250
the work required to undo bad preallocations exceeds
6251
the work saved in good cases for most test programs.
6252
* No longer use return list or unconsolidated bins since
6253
no scheme using them consistently outperforms those that don't
6254
given above changes.
6255
* Use best fit for very large chunks to prevent some worst-cases.
6256
* Added some support for debugging
6258
V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
6259
* Removed footers when chunks are in use. Thanks to
6260
Paul Wilson (wilson@cs.texas.edu) for the suggestion.
6262
V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
6263
* Added malloc_trim, with help from Wolfram Gloger
6264
(wmglo@Dent.MED.Uni-Muenchen.DE).
6266
V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
6268
V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
6269
* realloc: try to expand in both directions
6270
* malloc: swap order of clean-bin strategy;
6271
* realloc: only conditionally expand backwards
6272
* Try not to scavenge used bins
6273
* Use bin counts as a guide to preallocation
6274
* Occasionally bin return list chunks in first scan
6275
* Add a few optimizations from colin@nyx10.cs.du.edu
6277
V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
6278
* faster bin computation & slightly different binning
6279
* merged all consolidations to one part of malloc proper
6280
(eliminating old malloc_find_space & malloc_clean_bin)
6281
* Scan 2 returns chunks (not just 1)
6282
* Propagate failure in realloc if malloc returns 0
6283
* Add stuff to allow compilation on non-ANSI compilers
6284
from kpv@research.att.com
6286
V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
6287
* removed potential for odd address access in prev_chunk
6288
* removed dependency on getpagesize.h
6289
* misc cosmetics and a bit more internal documentation
6290
* anticosmetics: mangled names in macros to evade debugger strangeness
6291
* tested on sparc, hp-700, dec-mips, rs6000
6292
with gcc & native cc (hp, dec only) allowing
6293
Detlefs & Zorn comparison study (in SIGPLAN Notices.)
6295
Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
6296
* Based loosely on libg++-1.2X malloc. (It retains some of the overall
6297
structure of old version, but most details differ.)
added
removed
system/lib/dlmalloc.c
