2
This is a version (aka dlmalloc) of malloc/free/realloc written by
3
Doug Lea and released to the public domain, as explained at
4
http://creativecommons.org/licenses/publicdomain. Send questions,
5
comments, complaints, performance data, etc to dl@cs.oswego.edu
7
* Version 2.8.3 Thu Sep 22 11:16:15 2005 Doug Lea (dl at gee)
9
Note: There may be an updated version of this malloc obtainable at
10
ftp://gee.cs.oswego.edu/pub/misc/malloc.c
11
Check before installing!
15
This library is all in one file to simplify the most common usage:
16
ftp it, compile it (-O3), and link it into another program. All of
17
the compile-time options default to reasonable values for use on
18
most platforms. You might later want to step through various
19
compile-time and dynamic tuning options.
21
For convenience, an include file for code using this malloc is at:
22
ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.3.h
23
You don't really need this .h file unless you call functions not
24
defined in your system include files. The .h file contains only the
25
excerpts from this file needed for using this malloc on ANSI C/C++
26
systems, so long as you haven't changed compile-time options about
27
naming and tuning parameters. If you do, then you can create your
28
own malloc.h that does include all settings by cutting at the point
29
indicated below. Note that you may already by default be using a C
30
library containing a malloc that is based on some version of this
31
malloc (for example in linux). You might still want to use the one
32
in this file to customize settings or to avoid overheads associated
33
with library versions.
37
Supported pointer/size_t representation: 4 or 8 bytes
38
size_t MUST be an unsigned type of the same width as
39
pointers. (If you are using an ancient system that declares
40
size_t as a signed type, or need it to be a different width
41
than pointers, you can use a previous release of this malloc
42
(e.g. 2.7.2) supporting these.)
44
Alignment: 8 bytes (default)
45
This suffices for nearly all current machines and C compilers.
46
However, you can define MALLOC_ALIGNMENT to be wider than this
47
if necessary (up to 128bytes), at the expense of using more space.
49
Minimum overhead per allocated chunk: 4 or 8 bytes (if 4byte sizes)
50
8 or 16 bytes (if 8byte sizes)
51
Each malloced chunk has a hidden word of overhead holding size
52
and status information, and additional cross-check word
53
if FOOTERS is defined.
55
Minimum allocated size: 4-byte ptrs: 16 bytes (including overhead)
56
8-byte ptrs: 32 bytes (including overhead)
58
Even a request for zero bytes (i.e., malloc(0)) returns a
59
pointer to something of the minimum allocatable size.
60
The maximum overhead wastage (i.e., number of extra bytes
61
allocated than were requested in malloc) is less than or equal
62
to the minimum size, except for requests >= mmap_threshold that
63
are serviced via mmap(), where the worst case wastage is about
64
32 bytes plus the remainder from a system page (the minimal
65
mmap unit); typically 4096 or 8192 bytes.
67
Security: static-safe; optionally more or less
68
The "security" of malloc refers to the ability of malicious
69
code to accentuate the effects of errors (for example, freeing
70
space that is not currently malloc'ed or overwriting past the
71
ends of chunks) in code that calls malloc. This malloc
72
guarantees not to modify any memory locations below the base of
73
heap, i.e., static variables, even in the presence of usage
74
errors. The routines additionally detect most improper frees
75
and reallocs. All this holds as long as the static bookkeeping
76
for malloc itself is not corrupted by some other means. This
77
is only one aspect of security -- these checks do not, and
78
cannot, detect all possible programming errors.
80
If FOOTERS is defined nonzero, then each allocated chunk
81
carries an additional check word to verify that it was malloced
82
from its space. These check words are the same within each
83
execution of a program using malloc, but differ across
84
executions, so externally crafted fake chunks cannot be
85
freed. This improves security by rejecting frees/reallocs that
86
could corrupt heap memory, in addition to the checks preventing
87
writes to statics that are always on. This may further improve
88
security at the expense of time and space overhead. (Note that
89
FOOTERS may also be worth using with MSPACES.)
91
By default detected errors cause the program to abort (calling
92
"abort()"). You can override this to instead proceed past
93
errors by defining PROCEED_ON_ERROR. In this case, a bad free
94
has no effect, and a malloc that encounters a bad address
95
caused by user overwrites will ignore the bad address by
96
dropping pointers and indices to all known memory. This may
97
be appropriate for programs that should continue if at all
98
possible in the face of programming errors, although they may
99
run out of memory because dropped memory is never reclaimed.
101
If you don't like either of these options, you can define
102
CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
103
else. And if if you are sure that your program using malloc has
104
no errors or vulnerabilities, you can define INSECURE to 1,
105
which might (or might not) provide a small performance improvement.
107
Thread-safety: NOT thread-safe unless USE_LOCKS defined
108
When USE_LOCKS is defined, each public call to malloc, free,
109
etc is surrounded with either a pthread mutex or a win32
110
spinlock (depending on WIN32). This is not especially fast, and
111
can be a major bottleneck. It is designed only to provide
112
minimal protection in concurrent environments, and to provide a
113
basis for extensions. If you are using malloc in a concurrent
114
program, consider instead using ptmalloc, which is derived from
115
a version of this malloc. (See http://www.malloc.de).
117
System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
118
This malloc can use unix sbrk or any emulation (invoked using
119
the CALL_MORECORE macro) and/or mmap/munmap or any emulation
120
(invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
121
memory. On most unix systems, it tends to work best if both
122
MORECORE and MMAP are enabled. On Win32, it uses emulations
123
based on VirtualAlloc. It also uses common C library functions
126
Compliance: I believe it is compliant with the Single Unix Specification
127
(See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
130
* Overview of algorithms
132
This is not the fastest, most space-conserving, most portable, or
133
most tunable malloc ever written. However it is among the fastest
134
while also being among the most space-conserving, portable and
135
tunable. Consistent balance across these factors results in a good
136
general-purpose allocator for malloc-intensive programs.
138
In most ways, this malloc is a best-fit allocator. Generally, it
139
chooses the best-fitting existing chunk for a request, with ties
140
broken in approximately least-recently-used order. (This strategy
141
normally maintains low fragmentation.) However, for requests less
142
than 256bytes, it deviates from best-fit when there is not an
143
exactly fitting available chunk by preferring to use space adjacent
144
to that used for the previous small request, as well as by breaking
145
ties in approximately most-recently-used order. (These enhance
146
locality of series of small allocations.) And for very large requests
147
(>= 256Kb by default), it relies on system memory mapping
148
facilities, if supported. (This helps avoid carrying around and
149
possibly fragmenting memory used only for large chunks.)
151
All operations (except malloc_stats and mallinfo) have execution
152
times that are bounded by a constant factor of the number of bits in
153
a size_t, not counting any clearing in calloc or copying in realloc,
154
or actions surrounding MORECORE and MMAP that have times
155
proportional to the number of non-contiguous regions returned by
156
system allocation routines, which is often just 1.
158
The implementation is not very modular and seriously overuses
159
macros. Perhaps someday all C compilers will do as good a job
160
inlining modular code as can now be done by brute-force expansion,
161
but now, enough of them seem not to.
163
Some compilers issue a lot of warnings about code that is
164
dead/unreachable only on some platforms, and also about intentional
165
uses of negation on unsigned types. All known cases of each can be
168
For a longer but out of date high-level description, see
169
http://gee.cs.oswego.edu/dl/html/malloc.html
172
If MSPACES is defined, then in addition to malloc, free, etc.,
173
this file also defines mspace_malloc, mspace_free, etc. These
174
are versions of malloc routines that take an "mspace" argument
175
obtained using create_mspace, to control all internal bookkeeping.
176
If ONLY_MSPACES is defined, only these versions are compiled.
177
So if you would like to use this allocator for only some allocations,
178
and your system malloc for others, you can compile with
179
ONLY_MSPACES and then do something like...
180
static mspace mymspace = create_mspace(0,0); // for example
181
#define mymalloc(bytes) mspace_malloc(mymspace, bytes)
183
(Note: If you only need one instance of an mspace, you can instead
184
use "USE_DL_PREFIX" to relabel the global malloc.)
186
You can similarly create thread-local allocators by storing
187
mspaces as thread-locals. For example:
188
static __thread mspace tlms = 0;
189
void* tlmalloc(size_t bytes) {
190
if (tlms == 0) tlms = create_mspace(0, 0);
191
return mspace_malloc(tlms, bytes);
193
void tlfree(void* mem) { mspace_free(tlms, mem); }
195
Unless FOOTERS is defined, each mspace is completely independent.
196
You cannot allocate from one and free to another (although
197
conformance is only weakly checked, so usage errors are not always
198
caught). If FOOTERS is defined, then each chunk carries around a tag
199
indicating its originating mspace, and frees are directed to their
202
------------------------- Compile-time options ---------------------------
204
Be careful in setting #define values for numerical constants of type
205
size_t. On some systems, literal values are not automatically extended
206
to size_t precision unless they are explicitly casted.
208
WIN32 default: defined if _WIN32 defined
209
Defining WIN32 sets up defaults for MS environment and compilers.
210
Otherwise defaults are for unix.
212
MALLOC_ALIGNMENT default: (size_t)8
213
Controls the minimum alignment for malloc'ed chunks. It must be a
214
power of two and at least 8, even on machines for which smaller
215
alignments would suffice. It may be defined as larger than this
216
though. Note however that code and data structures are optimized for
217
the case of 8-byte alignment.
219
MSPACES default: 0 (false)
220
If true, compile in support for independent allocation spaces.
221
This is only supported if HAVE_MMAP is true.
223
ONLY_MSPACES default: 0 (false)
224
If true, only compile in mspace versions, not regular versions.
226
USE_LOCKS default: 0 (false)
227
Causes each call to each public routine to be surrounded with
228
pthread or WIN32 mutex lock/unlock. (If set true, this can be
229
overridden on a per-mspace basis for mspace versions.)
232
If true, provide extra checking and dispatching by placing
233
information in the footers of allocated chunks. This adds
234
space and time overhead.
237
If true, omit checks for usage errors and heap space overwrites.
239
USE_DL_PREFIX default: NOT defined
240
Causes compiler to prefix all public routines with the string 'dl'.
241
This can be useful when you only want to use this malloc in one part
242
of a program, using your regular system malloc elsewhere.
244
ABORT default: defined as abort()
245
Defines how to abort on failed checks. On most systems, a failed
246
check cannot die with an "assert" or even print an informative
247
message, because the underlying print routines in turn call malloc,
248
which will fail again. Generally, the best policy is to simply call
249
abort(). It's not very useful to do more than this because many
250
errors due to overwriting will show up as address faults (null, odd
251
addresses etc) rather than malloc-triggered checks, so will also
252
abort. Also, most compilers know that abort() does not return, so
253
can better optimize code conditionally calling it.
255
PROCEED_ON_ERROR default: defined as 0 (false)
256
Controls whether detected bad addresses cause them to bypassed
257
rather than aborting. If set, detected bad arguments to free and
258
realloc are ignored. And all bookkeeping information is zeroed out
259
upon a detected overwrite of freed heap space, thus losing the
260
ability to ever return it from malloc again, but enabling the
261
application to proceed. If PROCEED_ON_ERROR is defined, the
262
static variable malloc_corruption_error_count is compiled in
263
and can be examined to see if errors have occurred. This option
264
generates slower code than the default abort policy.
266
DEBUG default: NOT defined
267
The DEBUG setting is mainly intended for people trying to modify
268
this code or diagnose problems when porting to new platforms.
269
However, it may also be able to better isolate user errors than just
270
using runtime checks. The assertions in the check routines spell
271
out in more detail the assumptions and invariants underlying the
272
algorithms. The checking is fairly extensive, and will slow down
273
execution noticeably. Calling malloc_stats or mallinfo with DEBUG
274
set will attempt to check every non-mmapped allocated and free chunk
275
in the course of computing the summaries.
277
ABORT_ON_ASSERT_FAILURE default: defined as 1 (true)
278
Debugging assertion failures can be nearly impossible if your
279
version of the assert macro causes malloc to be called, which will
280
lead to a cascade of further failures, blowing the runtime stack.
281
ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
282
which will usually make debugging easier.
284
MALLOC_FAILURE_ACTION default: sets errno to ENOMEM, or no-op on win32
285
The action to take before "return 0" when malloc fails to be able to
286
return memory because there is none available.
288
HAVE_MORECORE default: 1 (true) unless win32 or ONLY_MSPACES
289
True if this system supports sbrk or an emulation of it.
291
MORECORE default: sbrk
292
The name of the sbrk-style system routine to call to obtain more
293
memory. See below for guidance on writing custom MORECORE
294
functions. The type of the argument to sbrk/MORECORE varies across
295
systems. It cannot be size_t, because it supports negative
296
arguments, so it is normally the signed type of the same width as
297
size_t (sometimes declared as "intptr_t"). It doesn't much matter
298
though. Internally, we only call it with arguments less than half
299
the max value of a size_t, which should work across all reasonable
300
possibilities, although sometimes generating compiler warnings. See
301
near the end of this file for guidelines for creating a custom
304
MORECORE_CONTIGUOUS default: 1 (true)
305
If true, take advantage of fact that consecutive calls to MORECORE
306
with positive arguments always return contiguous increasing
307
addresses. This is true of unix sbrk. It does not hurt too much to
308
set it true anyway, since malloc copes with non-contiguities.
309
Setting it false when definitely non-contiguous saves time
310
and possibly wasted space it would take to discover this though.
312
MORECORE_CANNOT_TRIM default: NOT defined
313
True if MORECORE cannot release space back to the system when given
314
negative arguments. This is generally necessary only if you are
315
using a hand-crafted MORECORE function that cannot handle negative
318
HAVE_MMAP default: 1 (true)
319
True if this system supports mmap or an emulation of it. If so, and
320
HAVE_MORECORE is not true, MMAP is used for all system
321
allocation. If set and HAVE_MORECORE is true as well, MMAP is
322
primarily used to directly allocate very large blocks. It is also
323
used as a backup strategy in cases where MORECORE fails to provide
324
space from system. Note: A single call to MUNMAP is assumed to be
325
able to unmap memory that may have be allocated using multiple calls
326
to MMAP, so long as they are adjacent.
328
HAVE_MREMAP default: 1 on linux, else 0
329
If true realloc() uses mremap() to re-allocate large blocks and
330
extend or shrink allocation spaces.
332
MMAP_CLEARS default: 1 on unix
333
True if mmap clears memory so calloc doesn't need to. This is true
334
for standard unix mmap using /dev/zero.
336
USE_BUILTIN_FFS default: 0 (i.e., not used)
337
Causes malloc to use the builtin ffs() function to compute indices.
338
Some compilers may recognize and intrinsify ffs to be faster than the
339
supplied C version. Also, the case of x86 using gcc is special-cased
340
to an asm instruction, so is already as fast as it can be, and so
341
this setting has no effect. (On most x86s, the asm version is only
342
slightly faster than the C version.)
344
malloc_getpagesize default: derive from system includes, or 4096.
345
The system page size. To the extent possible, this malloc manages
346
memory from the system in page-size units. This may be (and
347
usually is) a function rather than a constant. This is ignored
348
if WIN32, where page size is determined using getSystemInfo during
351
USE_DEV_RANDOM default: 0 (i.e., not used)
352
Causes malloc to use /dev/random to initialize secure magic seed for
353
stamping footers. Otherwise, the current time is used.
355
NO_MALLINFO default: 0
356
If defined, don't compile "mallinfo". This can be a simple way
357
of dealing with mismatches between system declarations and
360
MALLINFO_FIELD_TYPE default: size_t
361
The type of the fields in the mallinfo struct. This was originally
362
defined as "int" in SVID etc, but is more usefully defined as
363
size_t. The value is used only if HAVE_USR_INCLUDE_MALLOC_H is not set
365
REALLOC_ZERO_BYTES_FREES default: not defined
366
This should be set if a call to realloc with zero bytes should
367
be the same as a call to free. Some people think it should. Otherwise,
368
since this malloc returns a unique pointer for malloc(0), so does
371
LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
372
LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H, LACKS_ERRNO_H
373
LACKS_STDLIB_H default: NOT defined unless on WIN32
374
Define these if your system does not have these header files.
375
You might need to manually insert some of the declarations they provide.
377
DEFAULT_GRANULARITY default: page size if MORECORE_CONTIGUOUS,
378
system_info.dwAllocationGranularity in WIN32,
380
Also settable using mallopt(M_GRANULARITY, x)
381
The unit for allocating and deallocating memory from the system. On
382
most systems with contiguous MORECORE, there is no reason to
383
make this more than a page. However, systems with MMAP tend to
384
either require or encourage larger granularities. You can increase
385
this value to prevent system allocation functions to be called so
386
often, especially if they are slow. The value must be at least one
387
page and must be a power of two. Setting to 0 causes initialization
388
to either page size or win32 region size. (Note: In previous
389
versions of malloc, the equivalent of this option was called
392
DEFAULT_TRIM_THRESHOLD default: 2MB
393
Also settable using mallopt(M_TRIM_THRESHOLD, x)
394
The maximum amount of unused top-most memory to keep before
395
releasing via malloc_trim in free(). Automatic trimming is mainly
396
useful in long-lived programs using contiguous MORECORE. Because
397
trimming via sbrk can be slow on some systems, and can sometimes be
398
wasteful (in cases where programs immediately afterward allocate
399
more large chunks) the value should be high enough so that your
400
overall system performance would improve by releasing this much
401
memory. As a rough guide, you might set to a value close to the
402
average size of a process (program) running on your system.
403
Releasing this much memory would allow such a process to run in
404
memory. Generally, it is worth tuning trim thresholds when a
405
program undergoes phases where several large chunks are allocated
406
and released in ways that can reuse each other's storage, perhaps
407
mixed with phases where there are no such chunks at all. The trim
408
value must be greater than page size to have any useful effect. To
409
disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
410
some people use of mallocing a huge space and then freeing it at
411
program startup, in an attempt to reserve system memory, doesn't
412
have the intended effect under automatic trimming, since that memory
413
will immediately be returned to the system.
415
DEFAULT_MMAP_THRESHOLD default: 256K
416
Also settable using mallopt(M_MMAP_THRESHOLD, x)
417
The request size threshold for using MMAP to directly service a
418
request. Requests of at least this size that cannot be allocated
419
using already-existing space will be serviced via mmap. (If enough
420
normal freed space already exists it is used instead.) Using mmap
421
segregates relatively large chunks of memory so that they can be
422
individually obtained and released from the host system. A request
423
serviced through mmap is never reused by any other request (at least
424
not directly; the system may just so happen to remap successive
425
requests to the same locations). Segregating space in this way has
426
the benefits that: Mmapped space can always be individually released
427
back to the system, which helps keep the system level memory demands
428
of a long-lived program low. Also, mapped memory doesn't become
429
`locked' between other chunks, as can happen with normally allocated
430
chunks, which means that even trimming via malloc_trim would not
431
release them. However, it has the disadvantage that the space
432
cannot be reclaimed, consolidated, and then used to service later
433
requests, as happens with normal chunks. The advantages of mmap
434
nearly always outweigh disadvantages for "large" chunks, but the
435
value of "large" may vary across systems. The default is an
436
empirically derived value that works well in most systems. You can
437
disable mmap by setting to MAX_SIZE_T.
447
#define WIN32_LEAN_AND_MEAN
450
#define HAVE_MORECORE 0
451
#define LACKS_UNISTD_H
452
#define LACKS_SYS_PARAM_H
453
#define LACKS_SYS_MMAN_H
454
#define LACKS_STRING_H
455
#define LACKS_STRINGS_H
456
#define LACKS_SYS_TYPES_H
457
#define LACKS_ERRNO_H
458
#define MALLOC_FAILURE_ACTION
459
#define MMAP_CLEARS 0 /* WINCE and some others apparently don't clear */
466
#define HAVE_MORECORE 0
467
#define LACKS_SYS_MMAN_H
470
#if defined(DARWIN) || defined(_DARWIN)
471
/* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
472
#ifndef HAVE_MORECORE
473
#define HAVE_MORECORE 0
475
#endif /* HAVE_MORECORE */
478
#ifndef LACKS_SYS_TYPES_H
479
#include <sys/types.h> /* For size_t */
480
#endif /* LACKS_SYS_TYPES_H */
482
/* The maximum possible size_t value has all bits set */
483
#define MAX_SIZE_T (~(size_t)0)
486
#define ONLY_MSPACES 0
487
#endif /* ONLY_MSPACES */
491
#else /* ONLY_MSPACES */
493
#endif /* ONLY_MSPACES */
495
#ifndef MALLOC_ALIGNMENT
496
#define MALLOC_ALIGNMENT ((size_t)8U)
497
#endif /* MALLOC_ALIGNMENT */
502
#define ABORT abort()
504
#ifndef ABORT_ON_ASSERT_FAILURE
505
#define ABORT_ON_ASSERT_FAILURE 1
506
#endif /* ABORT_ON_ASSERT_FAILURE */
507
#ifndef PROCEED_ON_ERROR
508
#define PROCEED_ON_ERROR 0
509
#endif /* PROCEED_ON_ERROR */
512
#endif /* USE_LOCKS */
515
#endif /* INSECURE */
518
#endif /* HAVE_MMAP */
520
#define MMAP_CLEARS 1
521
#endif /* MMAP_CLEARS */
524
#define HAVE_MREMAP 1
526
#define HAVE_MREMAP 0
528
#endif /* HAVE_MREMAP */
529
#ifndef MALLOC_FAILURE_ACTION
530
#define MALLOC_FAILURE_ACTION errno = ENOMEM;
531
#endif /* MALLOC_FAILURE_ACTION */
532
#ifndef HAVE_MORECORE
534
#define HAVE_MORECORE 0
535
#else /* ONLY_MSPACES */
536
#define HAVE_MORECORE 1
537
#endif /* ONLY_MSPACES */
538
#endif /* HAVE_MORECORE */
540
#define MORECORE_CONTIGUOUS 0
541
#else /* !HAVE_MORECORE */
543
#define MORECORE sbrk
544
#endif /* MORECORE */
545
#ifndef MORECORE_CONTIGUOUS
546
#define MORECORE_CONTIGUOUS 1
547
#endif /* MORECORE_CONTIGUOUS */
548
#endif /* HAVE_MORECORE */
549
#ifndef DEFAULT_GRANULARITY
550
#if MORECORE_CONTIGUOUS
551
#define DEFAULT_GRANULARITY (0) /* 0 means to compute in init_mparams */
552
#else /* MORECORE_CONTIGUOUS */
553
#define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
554
#endif /* MORECORE_CONTIGUOUS */
555
#endif /* DEFAULT_GRANULARITY */
556
#ifndef DEFAULT_TRIM_THRESHOLD
557
#ifndef MORECORE_CANNOT_TRIM
558
#define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
559
#else /* MORECORE_CANNOT_TRIM */
560
#define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
561
#endif /* MORECORE_CANNOT_TRIM */
562
#endif /* DEFAULT_TRIM_THRESHOLD */
563
#ifndef DEFAULT_MMAP_THRESHOLD
565
#define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
566
#else /* HAVE_MMAP */
567
#define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
568
#endif /* HAVE_MMAP */
569
#endif /* DEFAULT_MMAP_THRESHOLD */
570
#ifndef USE_BUILTIN_FFS
571
#define USE_BUILTIN_FFS 0
572
#endif /* USE_BUILTIN_FFS */
573
#ifndef USE_DEV_RANDOM
574
#define USE_DEV_RANDOM 0
575
#endif /* USE_DEV_RANDOM */
577
#define NO_MALLINFO 0
578
#endif /* NO_MALLINFO */
579
#ifndef MALLINFO_FIELD_TYPE
580
#define MALLINFO_FIELD_TYPE size_t
581
#endif /* MALLINFO_FIELD_TYPE */
584
mallopt tuning options. SVID/XPG defines four standard parameter
585
numbers for mallopt, normally defined in malloc.h. None of these
586
are used in this malloc, so setting them has no effect. But this
587
malloc does support the following options.
590
#define M_TRIM_THRESHOLD (-1)
591
#define M_GRANULARITY (-2)
592
#define M_MMAP_THRESHOLD (-3)
594
/* ------------------------ Mallinfo declarations ------------------------ */
598
This version of malloc supports the standard SVID/XPG mallinfo
599
routine that returns a struct containing usage properties and
600
statistics. It should work on any system that has a
601
/usr/include/malloc.h defining struct mallinfo. The main
602
declaration needed is the mallinfo struct that is returned (by-copy)
603
by mallinfo(). The malloinfo struct contains a bunch of fields that
604
are not even meaningful in this version of malloc. These fields are
605
are instead filled by mallinfo() with other numbers that might be of
608
HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
609
/usr/include/malloc.h file that includes a declaration of struct
610
mallinfo. If so, it is included; else a compliant version is
611
declared below. These must be precisely the same for mallinfo() to
612
work. The original SVID version of this struct, defined on most
613
systems with mallinfo, declares all fields as ints. But some others
614
define as unsigned long. If your system defines the fields using a
615
type of different width than listed here, you MUST #include your
616
system version and #define HAVE_USR_INCLUDE_MALLOC_H.
619
/* #define HAVE_USR_INCLUDE_MALLOC_H */
621
#ifdef HAVE_USR_INCLUDE_MALLOC_H
622
#include "/usr/include/malloc.h"
623
#else /* HAVE_USR_INCLUDE_MALLOC_H */
626
MALLINFO_FIELD_TYPE arena; /* non-mmapped space allocated from system */
627
MALLINFO_FIELD_TYPE ordblks; /* number of free chunks */
628
MALLINFO_FIELD_TYPE smblks; /* always 0 */
629
MALLINFO_FIELD_TYPE hblks; /* always 0 */
630
MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */
631
MALLINFO_FIELD_TYPE usmblks; /* maximum total allocated space */
632
MALLINFO_FIELD_TYPE fsmblks; /* always 0 */
633
MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
634
MALLINFO_FIELD_TYPE fordblks; /* total free space */
635
MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
638
#endif /* HAVE_USR_INCLUDE_MALLOC_H */
639
#endif /* NO_MALLINFO */
643
#endif /* __cplusplus */
647
/* ------------------- Declarations of public routines ------------------- */
649
#ifndef USE_DL_PREFIX
650
#define dlcalloc calloc
652
#define dlmalloc malloc
653
#define dlmemalign memalign
654
#define dlrealloc realloc
655
#define dlvalloc valloc
656
#define dlpvalloc pvalloc
657
#define dlmallinfo mallinfo
658
#define dlmallopt mallopt
659
#define dlmalloc_trim malloc_trim
660
#define dlmalloc_stats malloc_stats
661
#define dlmalloc_usable_size malloc_usable_size
662
#define dlmalloc_footprint malloc_footprint
663
#define dlmalloc_max_footprint malloc_max_footprint
664
#define dlindependent_calloc independent_calloc
665
#define dlindependent_comalloc independent_comalloc
666
#endif /* USE_DL_PREFIX */
671
Returns a pointer to a newly allocated chunk of at least n bytes, or
672
null if no space is available, in which case errno is set to ENOMEM
675
If n is zero, malloc returns a minimum-sized chunk. (The minimum
676
size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
677
systems.) Note that size_t is an unsigned type, so calls with
678
arguments that would be negative if signed are interpreted as
679
requests for huge amounts of space, which will often fail. The
680
maximum supported value of n differs across systems, but is in all
681
cases less than the maximum representable value of a size_t.
683
void* dlmalloc(size_t);
687
Releases the chunk of memory pointed to by p, that had been previously
688
allocated using malloc or a related routine such as realloc.
689
It has no effect if p is null. If p was not malloced or already
690
freed, free(p) will by default cause the current program to abort.
695
calloc(size_t n_elements, size_t element_size);
696
Returns a pointer to n_elements * element_size bytes, with all locations
699
void* dlcalloc(size_t, size_t);
702
realloc(void* p, size_t n)
703
Returns a pointer to a chunk of size n that contains the same data
704
as does chunk p up to the minimum of (n, p's size) bytes, or null
705
if no space is available.
707
The returned pointer may or may not be the same as p. The algorithm
708
prefers extending p in most cases when possible, otherwise it
709
employs the equivalent of a malloc-copy-free sequence.
711
If p is null, realloc is equivalent to malloc.
713
If space is not available, realloc returns null, errno is set (if on
714
ANSI) and p is NOT freed.
716
if n is for fewer bytes than already held by p, the newly unused
717
space is lopped off and freed if possible. realloc with a size
718
argument of zero (re)allocates a minimum-sized chunk.
720
The old unix realloc convention of allowing the last-free'd chunk
721
to be used as an argument to realloc is not supported.
724
void* dlrealloc(void*, size_t);
727
memalign(size_t alignment, size_t n);
728
Returns a pointer to a newly allocated chunk of n bytes, aligned
729
in accord with the alignment argument.
731
The alignment argument should be a power of two. If the argument is
732
not a power of two, the nearest greater power is used.
733
8-byte alignment is guaranteed by normal malloc calls, so don't
734
bother calling memalign with an argument of 8 or less.
736
Overreliance on memalign is a sure way to fragment space.
738
void* dlmemalign(size_t, size_t);
742
Equivalent to memalign(pagesize, n), where pagesize is the page
743
size of the system. If the pagesize is unknown, 4096 is used.
745
void* dlvalloc(size_t);
748
mallopt(int parameter_number, int parameter_value)
749
Sets tunable parameters The format is to provide a
750
(parameter-number, parameter-value) pair. mallopt then sets the
751
corresponding parameter to the argument value if it can (i.e., so
752
long as the value is meaningful), and returns 1 if successful else
753
0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
754
normally defined in malloc.h. None of these are use in this malloc,
755
so setting them has no effect. But this malloc also supports other
756
options in mallopt. See below for details. Briefly, supported
757
parameters are as follows (listed defaults are for "typical"
760
Symbol param # default allowed param values
761
M_TRIM_THRESHOLD -1 2*1024*1024 any (MAX_SIZE_T disables)
762
M_GRANULARITY -2 page size any power of 2 >= page size
763
M_MMAP_THRESHOLD -3 256*1024 any (or 0 if no MMAP support)
765
int dlmallopt(int, int);
769
Returns the number of bytes obtained from the system. The total
770
number of bytes allocated by malloc, realloc etc., is less than this
771
value. Unlike mallinfo, this function returns only a precomputed
772
result, so can be called frequently to monitor memory consumption.
773
Even if locks are otherwise defined, this function does not use them,
774
so results might not be up to date.
776
size_t dlmalloc_footprint(void);
779
malloc_max_footprint();
780
Returns the maximum number of bytes obtained from the system. This
781
value will be greater than current footprint if deallocated space
782
has been reclaimed by the system. The peak number of bytes allocated
783
by malloc, realloc etc., is less than this value. Unlike mallinfo,
784
this function returns only a precomputed result, so can be called
785
frequently to monitor memory consumption. Even if locks are
786
otherwise defined, this function does not use them, so results might
789
size_t dlmalloc_max_footprint(void);
794
Returns (by copy) a struct containing various summary statistics:
796
arena: current total non-mmapped bytes allocated from system
797
ordblks: the number of free chunks
799
hblks: current number of mmapped regions
800
hblkhd: total bytes held in mmapped regions
801
usmblks: the maximum total allocated space. This will be greater
802
than current total if trimming has occurred.
804
uordblks: current total allocated space (normal or mmapped)
805
fordblks: total free space
806
keepcost: the maximum number of bytes that could ideally be released
807
back to system via malloc_trim. ("ideally" means that
808
it ignores page restrictions etc.)
810
Because these fields are ints, but internal bookkeeping may
811
be kept as longs, the reported values may wrap around zero and
814
struct mallinfo dlmallinfo(void);
815
#endif /* NO_MALLINFO */
818
independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
820
independent_calloc is similar to calloc, but instead of returning a
821
single cleared space, it returns an array of pointers to n_elements
822
independent elements that can hold contents of size elem_size, each
823
of which starts out cleared, and can be independently freed,
824
realloc'ed etc. The elements are guaranteed to be adjacently
825
allocated (this is not guaranteed to occur with multiple callocs or
826
mallocs), which may also improve cache locality in some
829
The "chunks" argument is optional (i.e., may be null, which is
830
probably the most typical usage). If it is null, the returned array
831
is itself dynamically allocated and should also be freed when it is
832
no longer needed. Otherwise, the chunks array must be of at least
833
n_elements in length. It is filled in with the pointers to the
836
In either case, independent_calloc returns this pointer array, or
837
null if the allocation failed. If n_elements is zero and "chunks"
838
is null, it returns a chunk representing an array with zero elements
839
(which should be freed if not wanted).
841
Each element must be individually freed when it is no longer
842
needed. If you'd like to instead be able to free all at once, you
843
should instead use regular calloc and assign pointers into this
844
space to represent elements. (In this case though, you cannot
845
independently free elements.)
847
independent_calloc simplifies and speeds up implementations of many
848
kinds of pools. It may also be useful when constructing large data
849
structures that initially have a fixed number of fixed-sized nodes,
850
but the number is not known at compile time, and some of the nodes
851
may later need to be freed. For example:
853
struct Node { int item; struct Node* next; };
855
struct Node* build_list() {
857
int n = read_number_of_nodes_needed();
858
if (n <= 0) return 0;
859
pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
860
if (pool == 0) die();
861
// organize into a linked list...
862
struct Node* first = pool[0];
863
for (i = 0; i < n-1; ++i)
864
pool[i]->next = pool[i+1];
865
free(pool); // Can now free the array (or not, if it is needed later)
869
void** dlindependent_calloc(size_t, size_t, void**);
872
independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
874
independent_comalloc allocates, all at once, a set of n_elements
875
chunks with sizes indicated in the "sizes" array. It returns
876
an array of pointers to these elements, each of which can be
877
independently freed, realloc'ed etc. The elements are guaranteed to
878
be adjacently allocated (this is not guaranteed to occur with
879
multiple callocs or mallocs), which may also improve cache locality
880
in some applications.
882
The "chunks" argument is optional (i.e., may be null). If it is null
883
the returned array is itself dynamically allocated and should also
884
be freed when it is no longer needed. Otherwise, the chunks array
885
must be of at least n_elements in length. It is filled in with the
886
pointers to the chunks.
888
In either case, independent_comalloc returns this pointer array, or
889
null if the allocation failed. If n_elements is zero and chunks is
890
null, it returns a chunk representing an array with zero elements
891
(which should be freed if not wanted).
893
Each element must be individually freed when it is no longer
894
needed. If you'd like to instead be able to free all at once, you
895
should instead use a single regular malloc, and assign pointers at
896
particular offsets in the aggregate space. (In this case though, you
897
cannot independently free elements.)
899
independent_comallac differs from independent_calloc in that each
900
element may have a different size, and also that it does not
901
automatically clear elements.
903
independent_comalloc can be used to speed up allocation in cases
904
where several structs or objects must always be allocated at the
905
same time. For example:
910
void send_message(char* msg) {
911
int msglen = strlen(msg);
912
size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
914
if (independent_comalloc(3, sizes, chunks) == 0)
916
struct Head* head = (struct Head*)(chunks[0]);
917
char* body = (char*)(chunks[1]);
918
struct Foot* foot = (struct Foot*)(chunks[2]);
922
In general though, independent_comalloc is worth using only for
923
larger values of n_elements. For small values, you probably won't
924
detect enough difference from series of malloc calls to bother.
926
Overuse of independent_comalloc can increase overall memory usage,
927
since it cannot reuse existing noncontiguous small chunks that
928
might be available for some of the elements.
930
void** dlindependent_comalloc(size_t, size_t*, void**);
935
Equivalent to valloc(minimum-page-that-holds(n)), that is,
936
round up n to nearest pagesize.
938
void* dlpvalloc(size_t);
941
malloc_trim(size_t pad);
943
If possible, gives memory back to the system (via negative arguments
944
to sbrk) if there is unused memory at the `high' end of the malloc
945
pool or in unused MMAP segments. You can call this after freeing
946
large blocks of memory to potentially reduce the system-level memory
947
requirements of a program. However, it cannot guarantee to reduce
948
memory. Under some allocation patterns, some large free blocks of
949
memory will be locked between two used chunks, so they cannot be
950
given back to the system.
952
The `pad' argument to malloc_trim represents the amount of free
953
trailing space to leave untrimmed. If this argument is zero, only
954
the minimum amount of memory to maintain internal data structures
955
will be left. Non-zero arguments can be supplied to maintain enough
956
trailing space to service future expected allocations without having
957
to re-obtain memory from the system.
959
Malloc_trim returns 1 if it actually released any memory, else 0.
961
int dlmalloc_trim(size_t);
964
malloc_usable_size(void* p);
966
Returns the number of bytes you can actually use in
967
an allocated chunk, which may be more than you requested (although
968
often not) due to alignment and minimum size constraints.
969
You can use this many bytes without worrying about
970
overwriting other allocated objects. This is not a particularly great
971
programming practice. malloc_usable_size can be more useful in
972
debugging and assertions, for example:
975
assert(malloc_usable_size(p) >= 256);
977
size_t dlmalloc_usable_size(void*);
981
Prints on stderr the amount of space obtained from the system (both
982
via sbrk and mmap), the maximum amount (which may be more than
983
current if malloc_trim and/or munmap got called), and the current
984
number of bytes allocated via malloc (or realloc, etc) but not yet
985
freed. Note that this is the number of bytes allocated, not the
986
number requested. It will be larger than the number requested
987
because of alignment and bookkeeping overhead. Because it includes
988
alignment wastage as being in use, this figure may be greater than
989
zero even when no user-level chunks are allocated.
991
The reported current and maximum system memory can be inaccurate if
992
a program makes other calls to system memory allocation functions
993
(normally sbrk) outside of malloc.
995
malloc_stats prints only the most commonly interesting statistics.
996
More information can be obtained by calling mallinfo.
998
void dlmalloc_stats(void);
1000
#endif /* ONLY_MSPACES */
1005
mspace is an opaque type representing an independent
1006
region of space that supports mspace_malloc, etc.
1008
typedef void* mspace;
1011
create_mspace creates and returns a new independent space with the
1012
given initial capacity, or, if 0, the default granularity size. It
1013
returns null if there is no system memory available to create the
1014
space. If argument locked is non-zero, the space uses a separate
1015
lock to control access. The capacity of the space will grow
1016
dynamically as needed to service mspace_malloc requests. You can
1017
control the sizes of incremental increases of this space by
1018
compiling with a different DEFAULT_GRANULARITY or dynamically
1019
setting with mallopt(M_GRANULARITY, value).
1021
mspace create_mspace(size_t capacity, int locked);
1024
destroy_mspace destroys the given space, and attempts to return all
1025
of its memory back to the system, returning the total number of
1026
bytes freed. After destruction, the results of access to all memory
1027
used by the space become undefined.
1029
size_t destroy_mspace(mspace msp);
1032
create_mspace_with_base uses the memory supplied as the initial base
1033
of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
1034
space is used for bookkeeping, so the capacity must be at least this
1035
large. (Otherwise 0 is returned.) When this initial space is
1036
exhausted, additional memory will be obtained from the system.
1037
Destroying this space will deallocate all additionally allocated
1038
space (if possible) but not the initial base.
1040
mspace create_mspace_with_base(void* base, size_t capacity, int locked);
1043
mspace_malloc behaves as malloc, but operates within
1046
void* mspace_malloc(mspace msp, size_t bytes);
1049
mspace_free behaves as free, but operates within
1052
If compiled with FOOTERS==1, mspace_free is not actually needed.
1053
free may be called instead of mspace_free because freed chunks from
1054
any space are handled by their originating spaces.
1056
void mspace_free(mspace msp, void* mem);
1059
mspace_realloc behaves as realloc, but operates within
1062
If compiled with FOOTERS==1, mspace_realloc is not actually
1063
needed. realloc may be called instead of mspace_realloc because
1064
realloced chunks from any space are handled by their originating
1067
void* mspace_realloc(mspace msp, void* mem, size_t newsize);
1070
mspace_calloc behaves as calloc, but operates within
1073
void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
1076
mspace_memalign behaves as memalign, but operates within
1079
void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);
1082
mspace_independent_calloc behaves as independent_calloc, but
1083
operates within the given space.
1085
void** mspace_independent_calloc(mspace msp, size_t n_elements,
1086
size_t elem_size, void* chunks[]);
1089
mspace_independent_comalloc behaves as independent_comalloc, but
1090
operates within the given space.
1092
void** mspace_independent_comalloc(mspace msp, size_t n_elements,
1093
size_t sizes[], void* chunks[]);
1096
mspace_footprint() returns the number of bytes obtained from the
1097
system for this space.
1099
size_t mspace_footprint(mspace msp);
1102
mspace_max_footprint() returns the peak number of bytes obtained from the
1103
system for this space.
1105
size_t mspace_max_footprint(mspace msp);
1110
mspace_mallinfo behaves as mallinfo, but reports properties of
1113
struct mallinfo mspace_mallinfo(mspace msp);
1114
#endif /* NO_MALLINFO */
1117
mspace_malloc_stats behaves as malloc_stats, but reports
1118
properties of the given space.
1120
void mspace_malloc_stats(mspace msp);
1123
mspace_trim behaves as malloc_trim, but
1124
operates within the given space.
1126
int mspace_trim(mspace msp, size_t pad);
1129
An alias for mallopt.
1131
int mspace_mallopt(int, int);
1133
#endif /* MSPACES */
1136
}; /* end of extern "C" */
1137
#endif /* __cplusplus */
1140
========================================================================
1141
To make a fully customizable malloc.h header file, cut everything
1142
above this line, put into file malloc.h, edit to suit, and #include it
1143
on the next line, as well as in programs that use this malloc.
1144
========================================================================
1147
/* #include "malloc.h" */
1149
/*------------------------------ internal #includes ---------------------- */
1152
#pragma warning( disable : 4146 ) /* no "unsigned" warnings */
1153
#endif /* _MSC_VER */
1155
#include <stdio.h> /* for printing in malloc_stats */
1157
#ifndef LACKS_ERRNO_H
1158
#include <errno.h> /* for MALLOC_FAILURE_ACTION */
1159
#endif /* LACKS_ERRNO_H */
1161
#include <time.h> /* for magic initialization */
1162
#endif /* FOOTERS */
1163
#ifndef LACKS_STDLIB_H
1164
#include <stdlib.h> /* for abort() */
1165
#endif /* LACKS_STDLIB_H */
1167
#if ABORT_ON_ASSERT_FAILURE
1168
#define assert(x) if(!(x)) ABORT
1169
#else /* ABORT_ON_ASSERT_FAILURE */
1171
#endif /* ABORT_ON_ASSERT_FAILURE */
1175
#ifndef LACKS_STRING_H
1176
#include <string.h> /* for memset etc */
1177
#endif /* LACKS_STRING_H */
1179
#ifndef LACKS_STRINGS_H
1180
#include <strings.h> /* for ffs */
1181
#endif /* LACKS_STRINGS_H */
1182
#endif /* USE_BUILTIN_FFS */
1184
#ifndef LACKS_SYS_MMAN_H
1185
#include <sys/mman.h> /* for mmap */
1186
#endif /* LACKS_SYS_MMAN_H */
1187
#ifndef LACKS_FCNTL_H
1189
#endif /* LACKS_FCNTL_H */
1190
#endif /* HAVE_MMAP */
1192
#ifndef LACKS_UNISTD_H
1193
#include <unistd.h> /* for sbrk */
1194
#else /* LACKS_UNISTD_H */
1195
#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
1196
extern void* sbrk(ptrdiff_t);
1197
#endif /* FreeBSD etc */
1198
#endif /* LACKS_UNISTD_H */
1199
#endif /* HAVE_MMAP */
1202
#ifndef malloc_getpagesize
1203
# ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
1204
# ifndef _SC_PAGE_SIZE
1205
# define _SC_PAGE_SIZE _SC_PAGESIZE
1208
# ifdef _SC_PAGE_SIZE
1209
# define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
1211
# if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
1212
extern size_t getpagesize();
1213
# define malloc_getpagesize getpagesize()
1215
# ifdef WIN32 /* use supplied emulation of getpagesize */
1216
# define malloc_getpagesize getpagesize()
1218
# ifndef LACKS_SYS_PARAM_H
1219
# include <sys/param.h>
1221
# ifdef EXEC_PAGESIZE
1222
# define malloc_getpagesize EXEC_PAGESIZE
1226
# define malloc_getpagesize NBPG
1228
# define malloc_getpagesize (NBPG * CLSIZE)
1232
# define malloc_getpagesize NBPC
1235
# define malloc_getpagesize PAGESIZE
1236
# else /* just guess */
1237
# define malloc_getpagesize ((size_t)4096U)
1248
/* ------------------- size_t and alignment properties -------------------- */
1250
/* The byte and bit size of a size_t */
1251
#define SIZE_T_SIZE (sizeof(size_t))
1252
#define SIZE_T_BITSIZE (sizeof(size_t) << 3)
1254
/* Some constants coerced to size_t */
1255
/* Annoying but necessary to avoid errors on some plaftorms */
1256
#define SIZE_T_ZERO ((size_t)0)
1257
#define SIZE_T_ONE ((size_t)1)
1258
#define SIZE_T_TWO ((size_t)2)
1259
#define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)
1260
#define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)
1261
#define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
1262
#define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
1264
/* The bit mask value corresponding to MALLOC_ALIGNMENT */
1265
#define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)
1267
/* True if address a has acceptable alignment */
1268
#define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
1270
/* the number of bytes to offset an address to align it */
1271
#define align_offset(A)\
1272
((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
1273
((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
1275
/* -------------------------- MMAP preliminaries ------------------------- */
1278
If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
1279
checks to fail so compiler optimizer can delete code rather than
1280
using so many "#if"s.
1284
/* MORECORE and MMAP must return MFAIL on failure */
1285
#define MFAIL ((void*)(MAX_SIZE_T))
1286
#define CMFAIL ((char*)(MFAIL)) /* defined for convenience */
1289
#define IS_MMAPPED_BIT (SIZE_T_ZERO)
1290
#define USE_MMAP_BIT (SIZE_T_ZERO)
1291
#define CALL_MMAP(s) MFAIL
1292
#define CALL_MUNMAP(a, s) (-1)
1293
#define DIRECT_MMAP(s) MFAIL
1295
#else /* HAVE_MMAP */
1296
#define IS_MMAPPED_BIT (SIZE_T_ONE)
1297
#define USE_MMAP_BIT (SIZE_T_ONE)
1299
#if !defined(WIN32) && !defined (__OS2__)
1300
#define CALL_MUNMAP(a, s) munmap((a), (s))
1301
#define MMAP_PROT (PROT_READ|PROT_WRITE)
1302
#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1303
#define MAP_ANONYMOUS MAP_ANON
1304
#endif /* MAP_ANON */
1305
#ifdef MAP_ANONYMOUS
1306
#define MMAP_FLAGS (MAP_PRIVATE|MAP_ANONYMOUS)
1307
#define CALL_MMAP(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
1308
#else /* MAP_ANONYMOUS */
1310
Nearly all versions of mmap support MAP_ANONYMOUS, so the following
1311
is unlikely to be needed, but is supplied just in case.
1313
#define MMAP_FLAGS (MAP_PRIVATE)
1314
static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1315
#define CALL_MMAP(s) ((dev_zero_fd < 0) ? \
1316
(dev_zero_fd = open("/dev/zero", O_RDWR), \
1317
mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
1318
mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
1319
#endif /* MAP_ANONYMOUS */
1321
#define DIRECT_MMAP(s) CALL_MMAP(s)
1323
#elif defined(__OS2__)
1325
/* OS/2 MMAP via DosAllocMem */
1326
static void* os2mmap(size_t size) {
1328
if (DosAllocMem(&ptr, size, OBJ_ANY|PAG_COMMIT|PAG_READ|PAG_WRITE) &&
1329
DosAllocMem(&ptr, size, PAG_COMMIT|PAG_READ|PAG_WRITE))
1334
#define os2direct_mmap(n) os2mmap(n)
1336
/* This function supports releasing coalesed segments */
1337
static int os2munmap(void* ptr, size_t size) {
1339
ULONG ulSize = size;
1341
if (DosQueryMem(ptr, &ulSize, &ulFlags) != 0)
1343
if ((ulFlags & PAG_BASE) == 0 ||(ulFlags & PAG_COMMIT) == 0 ||
1346
if (DosFreeMem(ptr) != 0)
1348
ptr = ( void * ) ( ( char * ) ptr + ulSize );
1354
#define CALL_MMAP(s) os2mmap(s)
1355
#define CALL_MUNMAP(a, s) os2munmap((a), (s))
1356
#define DIRECT_MMAP(s) os2direct_mmap(s)
1360
/* Win32 MMAP via VirtualAlloc */
1361
static void* win32mmap(size_t size) {
1362
void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_EXECUTE_READWRITE);
1363
return (ptr != 0)? ptr: MFAIL;
1366
/* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
1367
static void* win32direct_mmap(size_t size) {
1368
void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
1369
PAGE_EXECUTE_READWRITE);
1370
return (ptr != 0)? ptr: MFAIL;
1373
/* This function supports releasing coalesed segments */
1374
static int win32munmap(void* ptr, size_t size) {
1375
MEMORY_BASIC_INFORMATION minfo;
1378
if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
1380
if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
1381
minfo.State != MEM_COMMIT || minfo.RegionSize > size)
1383
if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
1385
cptr += minfo.RegionSize;
1386
size -= minfo.RegionSize;
1391
#define CALL_MMAP(s) win32mmap(s)
1392
#define CALL_MUNMAP(a, s) win32munmap((a), (s))
1393
#define DIRECT_MMAP(s) win32direct_mmap(s)
1395
#endif /* HAVE_MMAP */
1397
#if HAVE_MMAP && HAVE_MREMAP
1398
#define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
1399
#else /* HAVE_MMAP && HAVE_MREMAP */
1400
#define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
1401
#endif /* HAVE_MMAP && HAVE_MREMAP */
1404
#define CALL_MORECORE(S) MORECORE(S)
1405
#else /* HAVE_MORECORE */
1406
#define CALL_MORECORE(S) MFAIL
1407
#endif /* HAVE_MORECORE */
1409
/* mstate bit set if continguous morecore disabled or failed */
1410
#define USE_NONCONTIGUOUS_BIT (4U)
1412
/* segment bit set in create_mspace_with_base */
1413
#define EXTERN_BIT (8U)
1416
/* --------------------------- Lock preliminaries ------------------------ */
1421
When locks are defined, there are up to two global locks:
1423
* If HAVE_MORECORE, morecore_mutex protects sequences of calls to
1424
MORECORE. In many cases sys_alloc requires two calls, that should
1425
not be interleaved with calls by other threads. This does not
1426
protect against direct calls to MORECORE by other threads not
1427
using this lock, so there is still code to cope the best we can on
1430
* magic_init_mutex ensures that mparams.magic and other
1431
unique mparams values are initialized only once.
1434
#if !defined(WIN32) && !defined(__OS2__)
1435
/* By default use posix locks */
1436
#include <pthread.h>
1437
#define MLOCK_T pthread_mutex_t
1438
#define INITIAL_LOCK(l) pthread_mutex_init(l, NULL)
1439
#define ACQUIRE_LOCK(l) pthread_mutex_lock(l)
1440
#define RELEASE_LOCK(l) pthread_mutex_unlock(l)
1443
static MLOCK_T morecore_mutex = PTHREAD_MUTEX_INITIALIZER;
1444
#endif /* HAVE_MORECORE */
1446
static MLOCK_T magic_init_mutex = PTHREAD_MUTEX_INITIALIZER;
1448
#elif defined(__OS2__)
1449
#define MLOCK_T HMTX
1450
#define INITIAL_LOCK(l) DosCreateMutexSem(0, l, 0, FALSE)
1451
#define ACQUIRE_LOCK(l) DosRequestMutexSem(*l, SEM_INDEFINITE_WAIT)
1452
#define RELEASE_LOCK(l) DosReleaseMutexSem(*l)
1454
static MLOCK_T morecore_mutex;
1455
#endif /* HAVE_MORECORE */
1456
static MLOCK_T magic_init_mutex;
1460
Because lock-protected regions have bounded times, and there
1461
are no recursive lock calls, we can use simple spinlocks.
1464
#define MLOCK_T long
1465
static int win32_acquire_lock (MLOCK_T *sl) {
1467
#ifdef InterlockedCompareExchangePointer
1468
if (!InterlockedCompareExchange(sl, 1, 0))
1470
#else /* Use older void* version */
1471
if (!InterlockedCompareExchange((void**)sl, (void*)1, (void*)0))
1473
#endif /* InterlockedCompareExchangePointer */
1478
static void win32_release_lock (MLOCK_T *sl) {
1479
InterlockedExchange (sl, 0);
1482
#define INITIAL_LOCK(l) *(l)=0
1483
#define ACQUIRE_LOCK(l) win32_acquire_lock(l)
1484
#define RELEASE_LOCK(l) win32_release_lock(l)
1486
static MLOCK_T morecore_mutex;
1487
#endif /* HAVE_MORECORE */
1488
static MLOCK_T magic_init_mutex;
1491
#define USE_LOCK_BIT (2U)
1492
#else /* USE_LOCKS */
1493
#define USE_LOCK_BIT (0U)
1494
#define INITIAL_LOCK(l)
1495
#endif /* USE_LOCKS */
1497
#if USE_LOCKS && HAVE_MORECORE
1498
#define ACQUIRE_MORECORE_LOCK() ACQUIRE_LOCK(&morecore_mutex);
1499
#define RELEASE_MORECORE_LOCK() RELEASE_LOCK(&morecore_mutex);
1500
#else /* USE_LOCKS && HAVE_MORECORE */
1501
#define ACQUIRE_MORECORE_LOCK()
1502
#define RELEASE_MORECORE_LOCK()
1503
#endif /* USE_LOCKS && HAVE_MORECORE */
1506
#define ACQUIRE_MAGIC_INIT_LOCK() ACQUIRE_LOCK(&magic_init_mutex);
1507
#define RELEASE_MAGIC_INIT_LOCK() RELEASE_LOCK(&magic_init_mutex);
1508
#else /* USE_LOCKS */
1509
#define ACQUIRE_MAGIC_INIT_LOCK()
1510
#define RELEASE_MAGIC_INIT_LOCK()
1511
#endif /* USE_LOCKS */
1514
/* ----------------------- Chunk representations ------------------------ */
1517
(The following includes lightly edited explanations by Colin Plumb.)
1519
The malloc_chunk declaration below is misleading (but accurate and
1520
necessary). It declares a "view" into memory allowing access to
1521
necessary fields at known offsets from a given base.
1523
Chunks of memory are maintained using a `boundary tag' method as
1524
originally described by Knuth. (See the paper by Paul Wilson
1525
ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
1526
techniques.) Sizes of free chunks are stored both in the front of
1527
each chunk and at the end. This makes consolidating fragmented
1528
chunks into bigger chunks fast. The head fields also hold bits
1529
representing whether chunks are free or in use.
1531
Here are some pictures to make it clearer. They are "exploded" to
1532
show that the state of a chunk can be thought of as extending from
1533
the high 31 bits of the head field of its header through the
1534
prev_foot and PINUSE_BIT bit of the following chunk header.
1536
A chunk that's in use looks like:
1538
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1539
| Size of previous chunk (if P = 1) |
1540
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1541
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1542
| Size of this chunk 1| +-+
1543
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1549
+- size - sizeof(size_t) available payload bytes -+
1553
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1554
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
1555
| Size of next chunk (may or may not be in use) | +-+
1556
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1558
And if it's free, it looks like this:
1561
| User payload (must be in use, or we would have merged!) |
1562
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1563
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1564
| Size of this chunk 0| +-+
1565
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1567
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1569
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1571
+- size - sizeof(struct chunk) unused bytes -+
1573
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1574
| Size of this chunk |
1575
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1576
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
1577
| Size of next chunk (must be in use, or we would have merged)| +-+
1578
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1582
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1585
Note that since we always merge adjacent free chunks, the chunks
1586
adjacent to a free chunk must be in use.
1588
Given a pointer to a chunk (which can be derived trivially from the
1589
payload pointer) we can, in O(1) time, find out whether the adjacent
1590
chunks are free, and if so, unlink them from the lists that they
1591
are on and merge them with the current chunk.
1593
Chunks always begin on even word boundaries, so the mem portion
1594
(which is returned to the user) is also on an even word boundary, and
1595
thus at least double-word aligned.
1597
The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
1598
chunk size (which is always a multiple of two words), is an in-use
1599
bit for the *previous* chunk. If that bit is *clear*, then the
1600
word before the current chunk size contains the previous chunk
1601
size, and can be used to find the front of the previous chunk.
1602
The very first chunk allocated always has this bit set, preventing
1603
access to non-existent (or non-owned) memory. If pinuse is set for
1604
any given chunk, then you CANNOT determine the size of the
1605
previous chunk, and might even get a memory addressing fault when
1608
The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
1609
the chunk size redundantly records whether the current chunk is
1610
inuse. This redundancy enables usage checks within free and realloc,
1611
and reduces indirection when freeing and consolidating chunks.
1613
Each freshly allocated chunk must have both cinuse and pinuse set.
1614
That is, each allocated chunk borders either a previously allocated
1615
and still in-use chunk, or the base of its memory arena. This is
1616
ensured by making all allocations from the the `lowest' part of any
1617
found chunk. Further, no free chunk physically borders another one,
1618
so each free chunk is known to be preceded and followed by either
1619
inuse chunks or the ends of memory.
1621
Note that the `foot' of the current chunk is actually represented
1622
as the prev_foot of the NEXT chunk. This makes it easier to
1623
deal with alignments etc but can be very confusing when trying
1624
to extend or adapt this code.
1626
The exceptions to all this are
1628
1. The special chunk `top' is the top-most available chunk (i.e.,
1629
the one bordering the end of available memory). It is treated
1630
specially. Top is never included in any bin, is used only if
1631
no other chunk is available, and is released back to the
1632
system if it is very large (see M_TRIM_THRESHOLD). In effect,
1633
the top chunk is treated as larger (and thus less well
1634
fitting) than any other available chunk. The top chunk
1635
doesn't update its trailing size field since there is no next
1636
contiguous chunk that would have to index off it. However,
1637
space is still allocated for it (TOP_FOOT_SIZE) to enable
1638
separation or merging when space is extended.
1640
3. Chunks allocated via mmap, which have the lowest-order bit
1641
(IS_MMAPPED_BIT) set in their prev_foot fields, and do not set
1642
PINUSE_BIT in their head fields. Because they are allocated
1643
one-by-one, each must carry its own prev_foot field, which is
1644
also used to hold the offset this chunk has within its mmapped
1645
region, which is needed to preserve alignment. Each mmapped
1646
chunk is trailed by the first two fields of a fake next-chunk
1647
for sake of usage checks.
1651
struct malloc_chunk {
1652
size_t prev_foot; /* Size of previous chunk (if free). */
1653
size_t head; /* Size and inuse bits. */
1654
struct malloc_chunk* fd; /* double links -- used only if free. */
1655
struct malloc_chunk* bk;
1658
typedef struct malloc_chunk mchunk;
1659
typedef struct malloc_chunk* mchunkptr;
1660
typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */
1661
typedef unsigned int bindex_t; /* Described below */
1662
typedef unsigned int binmap_t; /* Described below */
1663
typedef unsigned int flag_t; /* The type of various bit flag sets */
1665
/* ------------------- Chunks sizes and alignments ----------------------- */
1667
#define MCHUNK_SIZE (sizeof(mchunk))
1670
#define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
1672
#define CHUNK_OVERHEAD (SIZE_T_SIZE)
1673
#endif /* FOOTERS */
1675
/* MMapped chunks need a second word of overhead ... */
1676
#define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
1677
/* ... and additional padding for fake next-chunk at foot */
1678
#define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES)
1680
/* The smallest size we can malloc is an aligned minimal chunk */
1681
#define MIN_CHUNK_SIZE\
1682
((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
1684
/* conversion from malloc headers to user pointers, and back */
1685
#define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))
1686
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
1687
/* chunk associated with aligned address A */
1688
#define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))
1690
/* Bounds on request (not chunk) sizes. */
1691
#define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)
1692
#define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
1694
/* pad request bytes into a usable size */
1695
#define pad_request(req) \
1696
(((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
1698
/* pad request, checking for minimum (but not maximum) */
1699
#define request2size(req) \
1700
(((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
1703
/* ------------------ Operations on head and foot fields ----------------- */
1706
The head field of a chunk is or'ed with PINUSE_BIT when previous
1707
adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
1708
use. If the chunk was obtained with mmap, the prev_foot field has
1709
IS_MMAPPED_BIT set, otherwise holding the offset of the base of the
1710
mmapped region to the base of the chunk.
1713
#define PINUSE_BIT (SIZE_T_ONE)
1714
#define CINUSE_BIT (SIZE_T_TWO)
1715
#define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)
1717
/* Head value for fenceposts */
1718
#define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)
1720
/* extraction of fields from head words */
1721
#define cinuse(p) ((p)->head & CINUSE_BIT)
1722
#define pinuse(p) ((p)->head & PINUSE_BIT)
1723
#define chunksize(p) ((p)->head & ~(INUSE_BITS))
1725
#define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)
1726
#define clear_cinuse(p) ((p)->head &= ~CINUSE_BIT)
1728
/* Treat space at ptr +/- offset as a chunk */
1729
#define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
1730
#define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
1732
/* Ptr to next or previous physical malloc_chunk. */
1733
#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~INUSE_BITS)))
1734
#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
1736
/* extract next chunk's pinuse bit */
1737
#define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)
1739
/* Get/set size at footer */
1740
#define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)
1741
#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
1743
/* Set size, pinuse bit, and foot */
1744
#define set_size_and_pinuse_of_free_chunk(p, s)\
1745
((p)->head = (s|PINUSE_BIT), set_foot(p, s))
1747
/* Set size, pinuse bit, foot, and clear next pinuse */
1748
#define set_free_with_pinuse(p, s, n)\
1749
(clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
1751
#define is_mmapped(p)\
1752
(!((p)->head & PINUSE_BIT) && ((p)->prev_foot & IS_MMAPPED_BIT))
1754
/* Get the internal overhead associated with chunk p */
1755
#define overhead_for(p)\
1756
(is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
1758
/* Return true if malloced space is not necessarily cleared */
1760
#define calloc_must_clear(p) (!is_mmapped(p))
1761
#else /* MMAP_CLEARS */
1762
#define calloc_must_clear(p) (1)
1763
#endif /* MMAP_CLEARS */
1765
/* ---------------------- Overlaid data structures ----------------------- */
1768
When chunks are not in use, they are treated as nodes of either
1771
"Small" chunks are stored in circular doubly-linked lists, and look
1774
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1775
| Size of previous chunk |
1776
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1777
`head:' | Size of chunk, in bytes |P|
1778
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1779
| Forward pointer to next chunk in list |
1780
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1781
| Back pointer to previous chunk in list |
1782
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1783
| Unused space (may be 0 bytes long) .
1786
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1787
`foot:' | Size of chunk, in bytes |
1788
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1790
Larger chunks are kept in a form of bitwise digital trees (aka
1791
tries) keyed on chunksizes. Because malloc_tree_chunks are only for
1792
free chunks greater than 256 bytes, their size doesn't impose any
1793
constraints on user chunk sizes. Each node looks like:
1795
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1796
| Size of previous chunk |
1797
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1798
`head:' | Size of chunk, in bytes |P|
1799
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1800
| Forward pointer to next chunk of same size |
1801
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1802
| Back pointer to previous chunk of same size |
1803
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1804
| Pointer to left child (child[0]) |
1805
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1806
| Pointer to right child (child[1]) |
1807
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1808
| Pointer to parent |
1809
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1810
| bin index of this chunk |
1811
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1814
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1815
`foot:' | Size of chunk, in bytes |
1816
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1818
Each tree holding treenodes is a tree of unique chunk sizes. Chunks
1819
of the same size are arranged in a circularly-linked list, with only
1820
the oldest chunk (the next to be used, in our FIFO ordering)
1821
actually in the tree. (Tree members are distinguished by a non-null
1822
parent pointer.) If a chunk with the same size an an existing node
1823
is inserted, it is linked off the existing node using pointers that
1824
work in the same way as fd/bk pointers of small chunks.
1826
Each tree contains a power of 2 sized range of chunk sizes (the
1827
smallest is 0x100 <= x < 0x180), which is is divided in half at each
1828
tree level, with the chunks in the smaller half of the range (0x100
1829
<= x < 0x140 for the top nose) in the left subtree and the larger
1830
half (0x140 <= x < 0x180) in the right subtree. This is, of course,
1831
done by inspecting individual bits.
1833
Using these rules, each node's left subtree contains all smaller
1834
sizes than its right subtree. However, the node at the root of each
1835
subtree has no particular ordering relationship to either. (The
1836
dividing line between the subtree sizes is based on trie relation.)
1837
If we remove the last chunk of a given size from the interior of the
1838
tree, we need to replace it with a leaf node. The tree ordering
1839
rules permit a node to be replaced by any leaf below it.
1841
The smallest chunk in a tree (a common operation in a best-fit
1842
allocator) can be found by walking a path to the leftmost leaf in
1843
the tree. Unlike a usual binary tree, where we follow left child
1844
pointers until we reach a null, here we follow the right child
1845
pointer any time the left one is null, until we reach a leaf with
1846
both child pointers null. The smallest chunk in the tree will be
1847
somewhere along that path.
1849
The worst case number of steps to add, find, or remove a node is
1850
bounded by the number of bits differentiating chunks within
1851
bins. Under current bin calculations, this ranges from 6 up to 21
1852
(for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
1853
is of course much better.
1856
struct malloc_tree_chunk {
1857
/* The first four fields must be compatible with malloc_chunk */
1860
struct malloc_tree_chunk* fd;
1861
struct malloc_tree_chunk* bk;
1863
struct malloc_tree_chunk* child[2];
1864
struct malloc_tree_chunk* parent;
1868
typedef struct malloc_tree_chunk tchunk;
1869
typedef struct malloc_tree_chunk* tchunkptr;
1870
typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
1872
/* A little helper macro for trees */
1873
#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
1875
/* ----------------------------- Segments -------------------------------- */
1878
Each malloc space may include non-contiguous segments, held in a
1879
list headed by an embedded malloc_segment record representing the
1880
top-most space. Segments also include flags holding properties of
1881
the space. Large chunks that are directly allocated by mmap are not
1882
included in this list. They are instead independently created and
1883
destroyed without otherwise keeping track of them.
1885
Segment management mainly comes into play for spaces allocated by
1886
MMAP. Any call to MMAP might or might not return memory that is
1887
adjacent to an existing segment. MORECORE normally contiguously
1888
extends the current space, so this space is almost always adjacent,
1889
which is simpler and faster to deal with. (This is why MORECORE is
1890
used preferentially to MMAP when both are available -- see
1891
sys_alloc.) When allocating using MMAP, we don't use any of the
1892
hinting mechanisms (inconsistently) supported in various
1893
implementations of unix mmap, or distinguish reserving from
1894
committing memory. Instead, we just ask for space, and exploit
1895
contiguity when we get it. It is probably possible to do
1896
better than this on some systems, but no general scheme seems
1897
to be significantly better.
1899
Management entails a simpler variant of the consolidation scheme
1900
used for chunks to reduce fragmentation -- new adjacent memory is
1901
normally prepended or appended to an existing segment. However,
1902
there are limitations compared to chunk consolidation that mostly
1903
reflect the fact that segment processing is relatively infrequent
1904
(occurring only when getting memory from system) and that we
1905
don't expect to have huge numbers of segments:
1907
* Segments are not indexed, so traversal requires linear scans. (It
1908
would be possible to index these, but is not worth the extra
1909
overhead and complexity for most programs on most platforms.)
1910
* New segments are only appended to old ones when holding top-most
1911
memory; if they cannot be prepended to others, they are held in
1914
Except for the top-most segment of an mstate, each segment record
1915
is kept at the tail of its segment. Segments are added by pushing
1916
segment records onto the list headed by &mstate.seg for the
1919
Segment flags control allocation/merge/deallocation policies:
1920
* If EXTERN_BIT set, then we did not allocate this segment,
1921
and so should not try to deallocate or merge with others.
1922
(This currently holds only for the initial segment passed
1923
into create_mspace_with_base.)
1924
* If IS_MMAPPED_BIT set, the segment may be merged with
1925
other surrounding mmapped segments and trimmed/de-allocated
1927
* If neither bit is set, then the segment was obtained using
1928
MORECORE so can be merged with surrounding MORECORE'd segments
1929
and deallocated/trimmed using MORECORE with negative arguments.
1932
struct malloc_segment {
1933
char* base; /* base address */
1934
size_t size; /* allocated size */
1935
struct malloc_segment* next; /* ptr to next segment */
1936
#if FFI_MMAP_EXEC_WRIT
1937
/* The mmap magic is supposed to store the address of the executable
1938
segment at the very end of the requested block. */
1940
# define mmap_exec_offset(b,s) (*(ptrdiff_t*)((b)+(s)-sizeof(ptrdiff_t)))
1942
/* We can only merge segments if their corresponding executable
1943
segments are at identical offsets. */
1944
# define check_segment_merge(S,b,s) \
1945
(mmap_exec_offset((b),(s)) == (S)->exec_offset)
1947
# define add_segment_exec_offset(p,S) ((char*)(p) + (S)->exec_offset)
1948
# define sub_segment_exec_offset(p,S) ((char*)(p) - (S)->exec_offset)
1950
/* The removal of sflags only works with HAVE_MORECORE == 0. */
1952
# define get_segment_flags(S) (IS_MMAPPED_BIT)
1953
# define set_segment_flags(S,v) \
1954
(((v) != IS_MMAPPED_BIT) ? (ABORT, (v)) : \
1955
(((S)->exec_offset = \
1956
mmap_exec_offset((S)->base, (S)->size)), \
1957
(mmap_exec_offset((S)->base + (S)->exec_offset, (S)->size) != \
1958
(S)->exec_offset) ? (ABORT, (v)) : \
1959
(mmap_exec_offset((S)->base, (S)->size) = 0), (v)))
1961
/* We use an offset here, instead of a pointer, because then, when
1962
base changes, we don't have to modify this. On architectures
1963
with segmented addresses, this might not work. */
1964
ptrdiff_t exec_offset;
1967
# define get_segment_flags(S) ((S)->sflags)
1968
# define set_segment_flags(S,v) ((S)->sflags = (v))
1969
# define check_segment_merge(S,b,s) (1)
1971
flag_t sflags; /* mmap and extern flag */
1975
#define is_mmapped_segment(S) (get_segment_flags(S) & IS_MMAPPED_BIT)
1976
#define is_extern_segment(S) (get_segment_flags(S) & EXTERN_BIT)
1978
typedef struct malloc_segment msegment;
1979
typedef struct malloc_segment* msegmentptr;
1981
/* ---------------------------- malloc_state ----------------------------- */
1984
A malloc_state holds all of the bookkeeping for a space.
1985
The main fields are:
1988
The topmost chunk of the currently active segment. Its size is
1989
cached in topsize. The actual size of topmost space is
1990
topsize+TOP_FOOT_SIZE, which includes space reserved for adding
1991
fenceposts and segment records if necessary when getting more
1992
space from the system. The size at which to autotrim top is
1993
cached from mparams in trim_check, except that it is disabled if
1996
Designated victim (dv)
1997
This is the preferred chunk for servicing small requests that
1998
don't have exact fits. It is normally the chunk split off most
1999
recently to service another small request. Its size is cached in
2000
dvsize. The link fields of this chunk are not maintained since it
2001
is not kept in a bin.
2004
An array of bin headers for free chunks. These bins hold chunks
2005
with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
2006
chunks of all the same size, spaced 8 bytes apart. To simplify
2007
use in double-linked lists, each bin header acts as a malloc_chunk
2008
pointing to the real first node, if it exists (else pointing to
2009
itself). This avoids special-casing for headers. But to avoid
2010
waste, we allocate only the fd/bk pointers of bins, and then use
2011
repositioning tricks to treat these as the fields of a chunk.
2014
Treebins are pointers to the roots of trees holding a range of
2015
sizes. There are 2 equally spaced treebins for each power of two
2016
from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
2020
There is one bit map for small bins ("smallmap") and one for
2021
treebins ("treemap). Each bin sets its bit when non-empty, and
2022
clears the bit when empty. Bit operations are then used to avoid
2023
bin-by-bin searching -- nearly all "search" is done without ever
2024
looking at bins that won't be selected. The bit maps
2025
conservatively use 32 bits per map word, even if on 64bit system.
2026
For a good description of some of the bit-based techniques used
2027
here, see Henry S. Warren Jr's book "Hacker's Delight" (and
2028
supplement at http://hackersdelight.org/). Many of these are
2029
intended to reduce the branchiness of paths through malloc etc, as
2030
well as to reduce the number of memory locations read or written.
2033
A list of segments headed by an embedded malloc_segment record
2034
representing the initial space.
2036
Address check support
2037
The least_addr field is the least address ever obtained from
2038
MORECORE or MMAP. Attempted frees and reallocs of any address less
2039
than this are trapped (unless INSECURE is defined).
2042
A cross-check field that should always hold same value as mparams.magic.
2045
Bits recording whether to use MMAP, locks, or contiguous MORECORE
2048
Each space keeps track of current and maximum system memory
2049
obtained via MORECORE or MMAP.
2052
If USE_LOCKS is defined, the "mutex" lock is acquired and released
2053
around every public call using this mspace.
2056
/* Bin types, widths and sizes */
2057
#define NSMALLBINS (32U)
2058
#define NTREEBINS (32U)
2059
#define SMALLBIN_SHIFT (3U)
2060
#define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)
2061
#define TREEBIN_SHIFT (8U)
2062
#define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)
2063
#define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)
2064
#define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
2066
struct malloc_state {
2076
mchunkptr smallbins[(NSMALLBINS+1)*2];
2077
tbinptr treebins[NTREEBINS];
2079
size_t max_footprint;
2082
MLOCK_T mutex; /* locate lock among fields that rarely change */
2083
#endif /* USE_LOCKS */
2087
typedef struct malloc_state* mstate;
2089
/* ------------- Global malloc_state and malloc_params ------------------- */
2092
malloc_params holds global properties, including those that can be
2093
dynamically set using mallopt. There is a single instance, mparams,
2094
initialized in init_mparams.
2097
struct malloc_params {
2101
size_t mmap_threshold;
2102
size_t trim_threshold;
2103
flag_t default_mflags;
2106
static struct malloc_params mparams;
2108
/* The global malloc_state used for all non-"mspace" calls */
2109
static struct malloc_state _gm_;
2111
#define is_global(M) ((M) == &_gm_)
2112
#define is_initialized(M) ((M)->top != 0)
2114
/* -------------------------- system alloc setup ------------------------- */
2116
/* Operations on mflags */
2118
#define use_lock(M) ((M)->mflags & USE_LOCK_BIT)
2119
#define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)
2120
#define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)
2122
#define use_mmap(M) ((M)->mflags & USE_MMAP_BIT)
2123
#define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT)
2124
#define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT)
2126
#define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT)
2127
#define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT)
2129
#define set_lock(M,L)\
2130
((M)->mflags = (L)?\
2131
((M)->mflags | USE_LOCK_BIT) :\
2132
((M)->mflags & ~USE_LOCK_BIT))
2134
/* page-align a size */
2135
#define page_align(S)\
2136
(((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
2138
/* granularity-align a size */
2139
#define granularity_align(S)\
2140
(((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))
2142
#define is_page_aligned(S)\
2143
(((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
2144
#define is_granularity_aligned(S)\
2145
(((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
2147
/* True if segment S holds address A */
2148
#define segment_holds(S, A)\
2149
((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
2151
/* Return segment holding given address */
2152
static msegmentptr segment_holding(mstate m, char* addr) {
2153
msegmentptr sp = &m->seg;
2155
if (addr >= sp->base && addr < sp->base + sp->size)
2157
if ((sp = sp->next) == 0)
2162
/* Return true if segment contains a segment link */
2163
static int has_segment_link(mstate m, msegmentptr ss) {
2164
msegmentptr sp = &m->seg;
2166
if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
2168
if ((sp = sp->next) == 0)
2173
#ifndef MORECORE_CANNOT_TRIM
2174
#define should_trim(M,s) ((s) > (M)->trim_check)
2175
#else /* MORECORE_CANNOT_TRIM */
2176
#define should_trim(M,s) (0)
2177
#endif /* MORECORE_CANNOT_TRIM */
2180
TOP_FOOT_SIZE is padding at the end of a segment, including space
2181
that may be needed to place segment records and fenceposts when new
2182
noncontiguous segments are added.
2184
#define TOP_FOOT_SIZE\
2185
(align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
2188
/* ------------------------------- Hooks -------------------------------- */
2191
PREACTION should be defined to return 0 on success, and nonzero on
2192
failure. If you are not using locking, you can redefine these to do
2198
/* Ensure locks are initialized */
2199
#define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())
2201
#define PREACTION(M) ((GLOBALLY_INITIALIZE() || use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
2202
#define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
2203
#else /* USE_LOCKS */
2206
#define PREACTION(M) (0)
2207
#endif /* PREACTION */
2210
#define POSTACTION(M)
2211
#endif /* POSTACTION */
2213
#endif /* USE_LOCKS */
2216
CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
2217
USAGE_ERROR_ACTION is triggered on detected bad frees and
2218
reallocs. The argument p is an address that might have triggered the
2219
fault. It is ignored by the two predefined actions, but might be
2220
useful in custom actions that try to help diagnose errors.
2223
#if PROCEED_ON_ERROR
2225
/* A count of the number of corruption errors causing resets */
2226
int malloc_corruption_error_count;
2228
/* default corruption action */
2229
static void reset_on_error(mstate m);
2231
#define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)
2232
#define USAGE_ERROR_ACTION(m, p)
2234
#else /* PROCEED_ON_ERROR */
2236
#ifndef CORRUPTION_ERROR_ACTION
2237
#define CORRUPTION_ERROR_ACTION(m) ABORT
2238
#endif /* CORRUPTION_ERROR_ACTION */
2240
#ifndef USAGE_ERROR_ACTION
2241
#define USAGE_ERROR_ACTION(m,p) ABORT
2242
#endif /* USAGE_ERROR_ACTION */
2244
#endif /* PROCEED_ON_ERROR */
2246
/* -------------------------- Debugging setup ---------------------------- */
2250
#define check_free_chunk(M,P)
2251
#define check_inuse_chunk(M,P)
2252
#define check_malloced_chunk(M,P,N)
2253
#define check_mmapped_chunk(M,P)
2254
#define check_malloc_state(M)
2255
#define check_top_chunk(M,P)
2258
#define check_free_chunk(M,P) do_check_free_chunk(M,P)
2259
#define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)
2260
#define check_top_chunk(M,P) do_check_top_chunk(M,P)
2261
#define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
2262
#define check_mmapped_chunk(M,P) do_check_mmapped_chunk(M,P)
2263
#define check_malloc_state(M) do_check_malloc_state(M)
2265
static void do_check_any_chunk(mstate m, mchunkptr p);
2266
static void do_check_top_chunk(mstate m, mchunkptr p);
2267
static void do_check_mmapped_chunk(mstate m, mchunkptr p);
2268
static void do_check_inuse_chunk(mstate m, mchunkptr p);
2269
static void do_check_free_chunk(mstate m, mchunkptr p);
2270
static void do_check_malloced_chunk(mstate m, void* mem, size_t s);
2271
static void do_check_tree(mstate m, tchunkptr t);
2272
static void do_check_treebin(mstate m, bindex_t i);
2273
static void do_check_smallbin(mstate m, bindex_t i);
2274
static void do_check_malloc_state(mstate m);
2275
static int bin_find(mstate m, mchunkptr x);
2276
static size_t traverse_and_check(mstate m);
2279
/* ---------------------------- Indexing Bins ---------------------------- */
2281
#define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
2282
#define small_index(s) ((s) >> SMALLBIN_SHIFT)
2283
#define small_index2size(i) ((i) << SMALLBIN_SHIFT)
2284
#define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))
2286
/* addressing by index. See above about smallbin repositioning */
2287
#define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
2288
#define treebin_at(M,i) (&((M)->treebins[i]))
2290
/* assign tree index for size S to variable I */
2291
#if defined(__GNUC__) && defined(i386)
2292
#define compute_tree_index(S, I)\
2294
size_t X = S >> TREEBIN_SHIFT;\
2297
else if (X > 0xFFFF)\
2301
__asm__("bsrl %1,%0\n\t" : "=r" (K) : "rm" (X));\
2302
I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2306
#define compute_tree_index(S, I)\
2308
size_t X = S >> TREEBIN_SHIFT;\
2311
else if (X > 0xFFFF)\
2314
unsigned int Y = (unsigned int)X;\
2315
unsigned int N = ((Y - 0x100) >> 16) & 8;\
2316
unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
2318
N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
2319
K = 14 - N + ((Y <<= K) >> 15);\
2320
I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
2325
/* Bit representing maximum resolved size in a treebin at i */
2326
#define bit_for_tree_index(i) \
2327
(i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
2329
/* Shift placing maximum resolved bit in a treebin at i as sign bit */
2330
#define leftshift_for_tree_index(i) \
2331
((i == NTREEBINS-1)? 0 : \
2332
((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
2334
/* The size of the smallest chunk held in bin with index i */
2335
#define minsize_for_tree_index(i) \
2336
((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \
2337
(((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
2340
/* ------------------------ Operations on bin maps ----------------------- */
2342
/* bit corresponding to given index */
2343
#define idx2bit(i) ((binmap_t)(1) << (i))
2345
/* Mark/Clear bits with given index */
2346
#define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))
2347
#define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))
2348
#define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))
2350
#define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))
2351
#define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))
2352
#define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))
2354
/* index corresponding to given bit */
2356
#if defined(__GNUC__) && defined(i386)
2357
#define compute_bit2idx(X, I)\
2360
__asm__("bsfl %1,%0\n\t" : "=r" (J) : "rm" (X));\
2366
#define compute_bit2idx(X, I) I = ffs(X)-1
2368
#else /* USE_BUILTIN_FFS */
2369
#define compute_bit2idx(X, I)\
2371
unsigned int Y = X - 1;\
2372
unsigned int K = Y >> (16-4) & 16;\
2373
unsigned int N = K; Y >>= K;\
2374
N += K = Y >> (8-3) & 8; Y >>= K;\
2375
N += K = Y >> (4-2) & 4; Y >>= K;\
2376
N += K = Y >> (2-1) & 2; Y >>= K;\
2377
N += K = Y >> (1-0) & 1; Y >>= K;\
2378
I = (bindex_t)(N + Y);\
2380
#endif /* USE_BUILTIN_FFS */
2383
/* isolate the least set bit of a bitmap */
2384
#define least_bit(x) ((x) & -(x))
2386
/* mask with all bits to left of least bit of x on */
2387
#define left_bits(x) ((x<<1) | -(x<<1))
2389
/* mask with all bits to left of or equal to least bit of x on */
2390
#define same_or_left_bits(x) ((x) | -(x))
2393
/* ----------------------- Runtime Check Support ------------------------- */
2396
For security, the main invariant is that malloc/free/etc never
2397
writes to a static address other than malloc_state, unless static
2398
malloc_state itself has been corrupted, which cannot occur via
2399
malloc (because of these checks). In essence this means that we
2400
believe all pointers, sizes, maps etc held in malloc_state, but
2401
check all of those linked or offsetted from other embedded data
2402
structures. These checks are interspersed with main code in a way
2403
that tends to minimize their run-time cost.
2405
When FOOTERS is defined, in addition to range checking, we also
2406
verify footer fields of inuse chunks, which can be used guarantee
2407
that the mstate controlling malloc/free is intact. This is a
2408
streamlined version of the approach described by William Robertson
2409
et al in "Run-time Detection of Heap-based Overflows" LISA'03
2410
http://www.usenix.org/events/lisa03/tech/robertson.html The footer
2411
of an inuse chunk holds the xor of its mstate and a random seed,
2412
that is checked upon calls to free() and realloc(). This is
2413
(probablistically) unguessable from outside the program, but can be
2414
computed by any code successfully malloc'ing any chunk, so does not
2415
itself provide protection against code that has already broken
2416
security through some other means. Unlike Robertson et al, we
2417
always dynamically check addresses of all offset chunks (previous,
2418
next, etc). This turns out to be cheaper than relying on hashes.
2422
/* Check if address a is at least as high as any from MORECORE or MMAP */
2423
#define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
2424
/* Check if address of next chunk n is higher than base chunk p */
2425
#define ok_next(p, n) ((char*)(p) < (char*)(n))
2426
/* Check if p has its cinuse bit on */
2427
#define ok_cinuse(p) cinuse(p)
2428
/* Check if p has its pinuse bit on */
2429
#define ok_pinuse(p) pinuse(p)
2431
#else /* !INSECURE */
2432
#define ok_address(M, a) (1)
2433
#define ok_next(b, n) (1)
2434
#define ok_cinuse(p) (1)
2435
#define ok_pinuse(p) (1)
2436
#endif /* !INSECURE */
2438
#if (FOOTERS && !INSECURE)
2439
/* Check if (alleged) mstate m has expected magic field */
2440
#define ok_magic(M) ((M)->magic == mparams.magic)
2441
#else /* (FOOTERS && !INSECURE) */
2442
#define ok_magic(M) (1)
2443
#endif /* (FOOTERS && !INSECURE) */
2446
/* In gcc, use __builtin_expect to minimize impact of checks */
2448
#if defined(__GNUC__) && __GNUC__ >= 3
2449
#define RTCHECK(e) __builtin_expect(e, 1)
2451
#define RTCHECK(e) (e)
2453
#else /* !INSECURE */
2454
#define RTCHECK(e) (1)
2455
#endif /* !INSECURE */
2457
/* macros to set up inuse chunks with or without footers */
2461
#define mark_inuse_foot(M,p,s)
2463
/* Set cinuse bit and pinuse bit of next chunk */
2464
#define set_inuse(M,p,s)\
2465
((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2466
((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2468
/* Set cinuse and pinuse of this chunk and pinuse of next chunk */
2469
#define set_inuse_and_pinuse(M,p,s)\
2470
((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2471
((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2473
/* Set size, cinuse and pinuse bit of this chunk */
2474
#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2475
((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
2479
/* Set foot of inuse chunk to be xor of mstate and seed */
2480
#define mark_inuse_foot(M,p,s)\
2481
(((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
2483
#define get_mstate_for(p)\
2484
((mstate)(((mchunkptr)((char*)(p) +\
2485
(chunksize(p))))->prev_foot ^ mparams.magic))
2487
#define set_inuse(M,p,s)\
2488
((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2489
(((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
2490
mark_inuse_foot(M,p,s))
2492
#define set_inuse_and_pinuse(M,p,s)\
2493
((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2494
(((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
2495
mark_inuse_foot(M,p,s))
2497
#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2498
((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2499
mark_inuse_foot(M, p, s))
2501
#endif /* !FOOTERS */
2503
/* ---------------------------- setting mparams -------------------------- */
2505
/* Initialize mparams */
2506
static int init_mparams(void) {
2507
if (mparams.page_size == 0) {
2510
mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
2511
mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
2512
#if MORECORE_CONTIGUOUS
2513
mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
2514
#else /* MORECORE_CONTIGUOUS */
2515
mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
2516
#endif /* MORECORE_CONTIGUOUS */
2518
#if (FOOTERS && !INSECURE)
2522
unsigned char buf[sizeof(size_t)];
2523
/* Try to use /dev/urandom, else fall back on using time */
2524
if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
2525
read(fd, buf, sizeof(buf)) == sizeof(buf)) {
2526
s = *((size_t *) buf);
2530
#endif /* USE_DEV_RANDOM */
2531
s = (size_t)(time(0) ^ (size_t)0x55555555U);
2533
s |= (size_t)8U; /* ensure nonzero */
2534
s &= ~(size_t)7U; /* improve chances of fault for bad values */
2537
#else /* (FOOTERS && !INSECURE) */
2538
s = (size_t)0x58585858U;
2539
#endif /* (FOOTERS && !INSECURE) */
2540
ACQUIRE_MAGIC_INIT_LOCK();
2541
if (mparams.magic == 0) {
2543
/* Set up lock for main malloc area */
2544
INITIAL_LOCK(&gm->mutex);
2545
gm->mflags = mparams.default_mflags;
2547
RELEASE_MAGIC_INIT_LOCK();
2549
#if !defined(WIN32) && !defined(__OS2__)
2550
mparams.page_size = malloc_getpagesize;
2551
mparams.granularity = ((DEFAULT_GRANULARITY != 0)?
2552
DEFAULT_GRANULARITY : mparams.page_size);
2553
#elif defined (__OS2__)
2554
/* if low-memory is used, os2munmap() would break
2555
if it were anything other than 64k */
2556
mparams.page_size = 4096u;
2557
mparams.granularity = 65536u;
2560
SYSTEM_INFO system_info;
2561
GetSystemInfo(&system_info);
2562
mparams.page_size = system_info.dwPageSize;
2563
mparams.granularity = system_info.dwAllocationGranularity;
2567
/* Sanity-check configuration:
2568
size_t must be unsigned and as wide as pointer type.
2569
ints must be at least 4 bytes.
2570
alignment must be at least 8.
2571
Alignment, min chunk size, and page size must all be powers of 2.
2573
if ((sizeof(size_t) != sizeof(char*)) ||
2574
(MAX_SIZE_T < MIN_CHUNK_SIZE) ||
2575
(sizeof(int) < 4) ||
2576
(MALLOC_ALIGNMENT < (size_t)8U) ||
2577
((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
2578
((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) ||
2579
((mparams.granularity & (mparams.granularity-SIZE_T_ONE)) != 0) ||
2580
((mparams.page_size & (mparams.page_size-SIZE_T_ONE)) != 0))
2586
/* support for mallopt */
2587
static int change_mparam(int param_number, int value) {
2588
size_t val = (size_t)value;
2590
switch(param_number) {
2591
case M_TRIM_THRESHOLD:
2592
mparams.trim_threshold = val;
2595
if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
2596
mparams.granularity = val;
2601
case M_MMAP_THRESHOLD:
2602
mparams.mmap_threshold = val;
2610
/* ------------------------- Debugging Support --------------------------- */
2612
/* Check properties of any chunk, whether free, inuse, mmapped etc */
2613
static void do_check_any_chunk(mstate m, mchunkptr p) {
2614
assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
2615
assert(ok_address(m, p));
2618
/* Check properties of top chunk */
2619
static void do_check_top_chunk(mstate m, mchunkptr p) {
2620
msegmentptr sp = segment_holding(m, (char*)p);
2621
size_t sz = chunksize(p);
2623
assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
2624
assert(ok_address(m, p));
2625
assert(sz == m->topsize);
2627
assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
2629
assert(!next_pinuse(p));
2632
/* Check properties of (inuse) mmapped chunks */
2633
static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
2634
size_t sz = chunksize(p);
2635
size_t len = (sz + (p->prev_foot & ~IS_MMAPPED_BIT) + MMAP_FOOT_PAD);
2636
assert(is_mmapped(p));
2637
assert(use_mmap(m));
2638
assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
2639
assert(ok_address(m, p));
2640
assert(!is_small(sz));
2641
assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
2642
assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
2643
assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
2646
/* Check properties of inuse chunks */
2647
static void do_check_inuse_chunk(mstate m, mchunkptr p) {
2648
do_check_any_chunk(m, p);
2650
assert(next_pinuse(p));
2651
/* If not pinuse and not mmapped, previous chunk has OK offset */
2652
assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
2654
do_check_mmapped_chunk(m, p);
2657
/* Check properties of free chunks */
2658
static void do_check_free_chunk(mstate m, mchunkptr p) {
2659
size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
2660
mchunkptr next = chunk_plus_offset(p, sz);
2661
do_check_any_chunk(m, p);
2663
assert(!next_pinuse(p));
2664
assert (!is_mmapped(p));
2665
if (p != m->dv && p != m->top) {
2666
if (sz >= MIN_CHUNK_SIZE) {
2667
assert((sz & CHUNK_ALIGN_MASK) == 0);
2668
assert(is_aligned(chunk2mem(p)));
2669
assert(next->prev_foot == sz);
2671
assert (next == m->top || cinuse(next));
2672
assert(p->fd->bk == p);
2673
assert(p->bk->fd == p);
2675
else /* markers are always of size SIZE_T_SIZE */
2676
assert(sz == SIZE_T_SIZE);
2680
/* Check properties of malloced chunks at the point they are malloced */
2681
static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
2683
mchunkptr p = mem2chunk(mem);
2684
size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
2685
do_check_inuse_chunk(m, p);
2686
assert((sz & CHUNK_ALIGN_MASK) == 0);
2687
assert(sz >= MIN_CHUNK_SIZE);
2689
/* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
2690
assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
2694
/* Check a tree and its subtrees. */
2695
static void do_check_tree(mstate m, tchunkptr t) {
2698
bindex_t tindex = t->index;
2699
size_t tsize = chunksize(t);
2701
compute_tree_index(tsize, idx);
2702
assert(tindex == idx);
2703
assert(tsize >= MIN_LARGE_SIZE);
2704
assert(tsize >= minsize_for_tree_index(idx));
2705
assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
2707
do { /* traverse through chain of same-sized nodes */
2708
do_check_any_chunk(m, ((mchunkptr)u));
2709
assert(u->index == tindex);
2710
assert(chunksize(u) == tsize);
2712
assert(!next_pinuse(u));
2713
assert(u->fd->bk == u);
2714
assert(u->bk->fd == u);
2715
if (u->parent == 0) {
2716
assert(u->child[0] == 0);
2717
assert(u->child[1] == 0);
2720
assert(head == 0); /* only one node on chain has parent */
2722
assert(u->parent != u);
2723
assert (u->parent->child[0] == u ||
2724
u->parent->child[1] == u ||
2725
*((tbinptr*)(u->parent)) == u);
2726
if (u->child[0] != 0) {
2727
assert(u->child[0]->parent == u);
2728
assert(u->child[0] != u);
2729
do_check_tree(m, u->child[0]);
2731
if (u->child[1] != 0) {
2732
assert(u->child[1]->parent == u);
2733
assert(u->child[1] != u);
2734
do_check_tree(m, u->child[1]);
2736
if (u->child[0] != 0 && u->child[1] != 0) {
2737
assert(chunksize(u->child[0]) < chunksize(u->child[1]));
2745
/* Check all the chunks in a treebin. */
2746
static void do_check_treebin(mstate m, bindex_t i) {
2747
tbinptr* tb = treebin_at(m, i);
2749
int empty = (m->treemap & (1U << i)) == 0;
2753
do_check_tree(m, t);
2756
/* Check all the chunks in a smallbin. */
2757
static void do_check_smallbin(mstate m, bindex_t i) {
2758
sbinptr b = smallbin_at(m, i);
2759
mchunkptr p = b->bk;
2760
unsigned int empty = (m->smallmap & (1U << i)) == 0;
2764
for (; p != b; p = p->bk) {
2765
size_t size = chunksize(p);
2767
/* each chunk claims to be free */
2768
do_check_free_chunk(m, p);
2769
/* chunk belongs in bin */
2770
assert(small_index(size) == i);
2771
assert(p->bk == b || chunksize(p->bk) == chunksize(p));
2772
/* chunk is followed by an inuse chunk */
2774
if (q->head != FENCEPOST_HEAD)
2775
do_check_inuse_chunk(m, q);
2780
/* Find x in a bin. Used in other check functions. */
2781
static int bin_find(mstate m, mchunkptr x) {
2782
size_t size = chunksize(x);
2783
if (is_small(size)) {
2784
bindex_t sidx = small_index(size);
2785
sbinptr b = smallbin_at(m, sidx);
2786
if (smallmap_is_marked(m, sidx)) {
2791
} while ((p = p->fd) != b);
2796
compute_tree_index(size, tidx);
2797
if (treemap_is_marked(m, tidx)) {
2798
tchunkptr t = *treebin_at(m, tidx);
2799
size_t sizebits = size << leftshift_for_tree_index(tidx);
2800
while (t != 0 && chunksize(t) != size) {
2801
t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
2807
if (u == (tchunkptr)x)
2809
} while ((u = u->fd) != t);
2816
/* Traverse each chunk and check it; return total */
2817
static size_t traverse_and_check(mstate m) {
2819
if (is_initialized(m)) {
2820
msegmentptr s = &m->seg;
2821
sum += m->topsize + TOP_FOOT_SIZE;
2823
mchunkptr q = align_as_chunk(s->base);
2824
mchunkptr lastq = 0;
2826
while (segment_holds(s, q) &&
2827
q != m->top && q->head != FENCEPOST_HEAD) {
2828
sum += chunksize(q);
2830
assert(!bin_find(m, q));
2831
do_check_inuse_chunk(m, q);
2834
assert(q == m->dv || bin_find(m, q));
2835
assert(lastq == 0 || cinuse(lastq)); /* Not 2 consecutive free */
2836
do_check_free_chunk(m, q);
2847
/* Check all properties of malloc_state. */
2848
static void do_check_malloc_state(mstate m) {
2852
for (i = 0; i < NSMALLBINS; ++i)
2853
do_check_smallbin(m, i);
2854
for (i = 0; i < NTREEBINS; ++i)
2855
do_check_treebin(m, i);
2857
if (m->dvsize != 0) { /* check dv chunk */
2858
do_check_any_chunk(m, m->dv);
2859
assert(m->dvsize == chunksize(m->dv));
2860
assert(m->dvsize >= MIN_CHUNK_SIZE);
2861
assert(bin_find(m, m->dv) == 0);
2864
if (m->top != 0) { /* check top chunk */
2865
do_check_top_chunk(m, m->top);
2866
assert(m->topsize == chunksize(m->top));
2867
assert(m->topsize > 0);
2868
assert(bin_find(m, m->top) == 0);
2871
total = traverse_and_check(m);
2872
assert(total <= m->footprint);
2873
assert(m->footprint <= m->max_footprint);
2877
/* ----------------------------- statistics ------------------------------ */
2880
static struct mallinfo internal_mallinfo(mstate m) {
2881
struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
2882
if (!PREACTION(m)) {
2883
check_malloc_state(m);
2884
if (is_initialized(m)) {
2885
size_t nfree = SIZE_T_ONE; /* top always free */
2886
size_t mfree = m->topsize + TOP_FOOT_SIZE;
2888
msegmentptr s = &m->seg;
2890
mchunkptr q = align_as_chunk(s->base);
2891
while (segment_holds(s, q) &&
2892
q != m->top && q->head != FENCEPOST_HEAD) {
2893
size_t sz = chunksize(q);
2906
nm.hblkhd = m->footprint - sum;
2907
nm.usmblks = m->max_footprint;
2908
nm.uordblks = m->footprint - mfree;
2909
nm.fordblks = mfree;
2910
nm.keepcost = m->topsize;
2917
#endif /* !NO_MALLINFO */
2919
static void internal_malloc_stats(mstate m) {
2920
if (!PREACTION(m)) {
2924
check_malloc_state(m);
2925
if (is_initialized(m)) {
2926
msegmentptr s = &m->seg;
2927
maxfp = m->max_footprint;
2929
used = fp - (m->topsize + TOP_FOOT_SIZE);
2932
mchunkptr q = align_as_chunk(s->base);
2933
while (segment_holds(s, q) &&
2934
q != m->top && q->head != FENCEPOST_HEAD) {
2936
used -= chunksize(q);
2943
fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
2944
fprintf(stderr, "system bytes = %10lu\n", (unsigned long)(fp));
2945
fprintf(stderr, "in use bytes = %10lu\n", (unsigned long)(used));
2951
/* ----------------------- Operations on smallbins ----------------------- */
2954
Various forms of linking and unlinking are defined as macros. Even
2955
the ones for trees, which are very long but have very short typical
2956
paths. This is ugly but reduces reliance on inlining support of
2960
/* Link a free chunk into a smallbin */
2961
#define insert_small_chunk(M, P, S) {\
2962
bindex_t I = small_index(S);\
2963
mchunkptr B = smallbin_at(M, I);\
2965
assert(S >= MIN_CHUNK_SIZE);\
2966
if (!smallmap_is_marked(M, I))\
2967
mark_smallmap(M, I);\
2968
else if (RTCHECK(ok_address(M, B->fd)))\
2971
CORRUPTION_ERROR_ACTION(M);\
2979
/* Unlink a chunk from a smallbin */
2980
#define unlink_small_chunk(M, P, S) {\
2981
mchunkptr F = P->fd;\
2982
mchunkptr B = P->bk;\
2983
bindex_t I = small_index(S);\
2986
assert(chunksize(P) == small_index2size(I));\
2988
clear_smallmap(M, I);\
2989
else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
2990
(B == smallbin_at(M,I) || ok_address(M, B)))) {\
2995
CORRUPTION_ERROR_ACTION(M);\
2999
/* Unlink the first chunk from a smallbin */
3000
#define unlink_first_small_chunk(M, B, P, I) {\
3001
mchunkptr F = P->fd;\
3004
assert(chunksize(P) == small_index2size(I));\
3006
clear_smallmap(M, I);\
3007
else if (RTCHECK(ok_address(M, F))) {\
3012
CORRUPTION_ERROR_ACTION(M);\
3016
/* Replace dv node, binning the old one */
3017
/* Used only when dvsize known to be small */
3018
#define replace_dv(M, P, S) {\
3019
size_t DVS = M->dvsize;\
3021
mchunkptr DV = M->dv;\
3022
assert(is_small(DVS));\
3023
insert_small_chunk(M, DV, DVS);\
3029
/* ------------------------- Operations on trees ------------------------- */
3031
/* Insert chunk into tree */
3032
#define insert_large_chunk(M, X, S) {\
3035
compute_tree_index(S, I);\
3036
H = treebin_at(M, I);\
3038
X->child[0] = X->child[1] = 0;\
3039
if (!treemap_is_marked(M, I)) {\
3040
mark_treemap(M, I);\
3042
X->parent = (tchunkptr)H;\
3047
size_t K = S << leftshift_for_tree_index(I);\
3049
if (chunksize(T) != S) {\
3050
tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
3054
else if (RTCHECK(ok_address(M, C))) {\
3061
CORRUPTION_ERROR_ACTION(M);\
3066
tchunkptr F = T->fd;\
3067
if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
3075
CORRUPTION_ERROR_ACTION(M);\
3086
1. If x is a chained node, unlink it from its same-sized fd/bk links
3087
and choose its bk node as its replacement.
3088
2. If x was the last node of its size, but not a leaf node, it must
3089
be replaced with a leaf node (not merely one with an open left or
3090
right), to make sure that lefts and rights of descendents
3091
correspond properly to bit masks. We use the rightmost descendent
3092
of x. We could use any other leaf, but this is easy to locate and
3093
tends to counteract removal of leftmosts elsewhere, and so keeps
3094
paths shorter than minimally guaranteed. This doesn't loop much
3095
because on average a node in a tree is near the bottom.
3096
3. If x is the base of a chain (i.e., has parent links) relink
3097
x's parent and children to x's replacement (or null if none).
3100
#define unlink_large_chunk(M, X) {\
3101
tchunkptr XP = X->parent;\
3104
tchunkptr F = X->fd;\
3106
if (RTCHECK(ok_address(M, F))) {\
3111
CORRUPTION_ERROR_ACTION(M);\
3116
if (((R = *(RP = &(X->child[1]))) != 0) ||\
3117
((R = *(RP = &(X->child[0]))) != 0)) {\
3119
while ((*(CP = &(R->child[1])) != 0) ||\
3120
(*(CP = &(R->child[0])) != 0)) {\
3123
if (RTCHECK(ok_address(M, RP)))\
3126
CORRUPTION_ERROR_ACTION(M);\
3131
tbinptr* H = treebin_at(M, X->index);\
3133
if ((*H = R) == 0) \
3134
clear_treemap(M, X->index);\
3136
else if (RTCHECK(ok_address(M, XP))) {\
3137
if (XP->child[0] == X) \
3143
CORRUPTION_ERROR_ACTION(M);\
3145
if (RTCHECK(ok_address(M, R))) {\
3148
if ((C0 = X->child[0]) != 0) {\
3149
if (RTCHECK(ok_address(M, C0))) {\
3154
CORRUPTION_ERROR_ACTION(M);\
3156
if ((C1 = X->child[1]) != 0) {\
3157
if (RTCHECK(ok_address(M, C1))) {\
3162
CORRUPTION_ERROR_ACTION(M);\
3166
CORRUPTION_ERROR_ACTION(M);\
3171
/* Relays to large vs small bin operations */
3173
#define insert_chunk(M, P, S)\
3174
if (is_small(S)) insert_small_chunk(M, P, S)\
3175
else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
3177
#define unlink_chunk(M, P, S)\
3178
if (is_small(S)) unlink_small_chunk(M, P, S)\
3179
else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
3182
/* Relays to internal calls to malloc/free from realloc, memalign etc */
3185
#define internal_malloc(m, b) mspace_malloc(m, b)
3186
#define internal_free(m, mem) mspace_free(m,mem);
3187
#else /* ONLY_MSPACES */
3189
#define internal_malloc(m, b)\
3190
(m == gm)? dlmalloc(b) : mspace_malloc(m, b)
3191
#define internal_free(m, mem)\
3192
if (m == gm) dlfree(mem); else mspace_free(m,mem);
3194
#define internal_malloc(m, b) dlmalloc(b)
3195
#define internal_free(m, mem) dlfree(mem)
3196
#endif /* MSPACES */
3197
#endif /* ONLY_MSPACES */
3199
/* ----------------------- Direct-mmapping chunks ----------------------- */
3202
Directly mmapped chunks are set up with an offset to the start of
3203
the mmapped region stored in the prev_foot field of the chunk. This
3204
allows reconstruction of the required argument to MUNMAP when freed,
3205
and also allows adjustment of the returned chunk to meet alignment
3206
requirements (especially in memalign). There is also enough space
3207
allocated to hold a fake next chunk of size SIZE_T_SIZE to maintain
3208
the PINUSE bit so frees can be checked.
3211
/* Malloc using mmap */
3212
static void* mmap_alloc(mstate m, size_t nb) {
3213
size_t mmsize = granularity_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3214
if (mmsize > nb) { /* Check for wrap around 0 */
3215
char* mm = (char*)(DIRECT_MMAP(mmsize));
3217
size_t offset = align_offset(chunk2mem(mm));
3218
size_t psize = mmsize - offset - MMAP_FOOT_PAD;
3219
mchunkptr p = (mchunkptr)(mm + offset);
3220
p->prev_foot = offset | IS_MMAPPED_BIT;
3221
(p)->head = (psize|CINUSE_BIT);
3222
mark_inuse_foot(m, p, psize);
3223
chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
3224
chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
3226
if (mm < m->least_addr)
3228
if ((m->footprint += mmsize) > m->max_footprint)
3229
m->max_footprint = m->footprint;
3230
assert(is_aligned(chunk2mem(p)));
3231
check_mmapped_chunk(m, p);
3232
return chunk2mem(p);
3238
/* Realloc using mmap */
3239
static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) {
3240
size_t oldsize = chunksize(oldp);
3241
if (is_small(nb)) /* Can't shrink mmap regions below small size */
3243
/* Keep old chunk if big enough but not too big */
3244
if (oldsize >= nb + SIZE_T_SIZE &&
3245
(oldsize - nb) <= (mparams.granularity << 1))
3248
size_t offset = oldp->prev_foot & ~IS_MMAPPED_BIT;
3249
size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
3250
size_t newmmsize = granularity_align(nb + SIX_SIZE_T_SIZES +
3252
char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
3253
oldmmsize, newmmsize, 1);
3255
mchunkptr newp = (mchunkptr)(cp + offset);
3256
size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
3257
newp->head = (psize|CINUSE_BIT);
3258
mark_inuse_foot(m, newp, psize);
3259
chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
3260
chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
3262
if (cp < m->least_addr)
3264
if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
3265
m->max_footprint = m->footprint;
3266
check_mmapped_chunk(m, newp);
3273
/* -------------------------- mspace management -------------------------- */
3275
/* Initialize top chunk and its size */
3276
static void init_top(mstate m, mchunkptr p, size_t psize) {
3277
/* Ensure alignment */
3278
size_t offset = align_offset(chunk2mem(p));
3279
p = (mchunkptr)((char*)p + offset);
3284
p->head = psize | PINUSE_BIT;
3285
/* set size of fake trailing chunk holding overhead space only once */
3286
chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
3287
m->trim_check = mparams.trim_threshold; /* reset on each update */
3290
/* Initialize bins for a new mstate that is otherwise zeroed out */
3291
static void init_bins(mstate m) {
3292
/* Establish circular links for smallbins */
3294
for (i = 0; i < NSMALLBINS; ++i) {
3295
sbinptr bin = smallbin_at(m,i);
3296
bin->fd = bin->bk = bin;
3300
#if PROCEED_ON_ERROR
3302
/* default corruption action */
3303
static void reset_on_error(mstate m) {
3305
++malloc_corruption_error_count;
3306
/* Reinitialize fields to forget about all memory */
3307
m->smallbins = m->treebins = 0;
3308
m->dvsize = m->topsize = 0;
3313
for (i = 0; i < NTREEBINS; ++i)
3314
*treebin_at(m, i) = 0;
3317
#endif /* PROCEED_ON_ERROR */
3319
/* Allocate chunk and prepend remainder with chunk in successor base. */
3320
static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
3322
mchunkptr p = align_as_chunk(newbase);
3323
mchunkptr oldfirst = align_as_chunk(oldbase);
3324
size_t psize = (char*)oldfirst - (char*)p;
3325
mchunkptr q = chunk_plus_offset(p, nb);
3326
size_t qsize = psize - nb;
3327
set_size_and_pinuse_of_inuse_chunk(m, p, nb);
3329
assert((char*)oldfirst > (char*)q);
3330
assert(pinuse(oldfirst));
3331
assert(qsize >= MIN_CHUNK_SIZE);
3333
/* consolidate remainder with first chunk of old base */
3334
if (oldfirst == m->top) {
3335
size_t tsize = m->topsize += qsize;
3337
q->head = tsize | PINUSE_BIT;
3338
check_top_chunk(m, q);
3340
else if (oldfirst == m->dv) {
3341
size_t dsize = m->dvsize += qsize;
3343
set_size_and_pinuse_of_free_chunk(q, dsize);
3346
if (!cinuse(oldfirst)) {
3347
size_t nsize = chunksize(oldfirst);
3348
unlink_chunk(m, oldfirst, nsize);
3349
oldfirst = chunk_plus_offset(oldfirst, nsize);
3352
set_free_with_pinuse(q, qsize, oldfirst);
3353
insert_chunk(m, q, qsize);
3354
check_free_chunk(m, q);
3357
check_malloced_chunk(m, chunk2mem(p), nb);
3358
return chunk2mem(p);
3362
/* Add a segment to hold a new noncontiguous region */
3363
static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
3364
/* Determine locations and sizes of segment, fenceposts, old top */
3365
char* old_top = (char*)m->top;
3366
msegmentptr oldsp = segment_holding(m, old_top);
3367
char* old_end = oldsp->base + oldsp->size;
3368
size_t ssize = pad_request(sizeof(struct malloc_segment));
3369
char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3370
size_t offset = align_offset(chunk2mem(rawsp));
3371
char* asp = rawsp + offset;
3372
char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
3373
mchunkptr sp = (mchunkptr)csp;
3374
msegmentptr ss = (msegmentptr)(chunk2mem(sp));
3375
mchunkptr tnext = chunk_plus_offset(sp, ssize);
3376
mchunkptr p = tnext;
3379
/* reset top to new space */
3380
init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
3382
/* Set up segment record */
3383
assert(is_aligned(ss));
3384
set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
3385
*ss = m->seg; /* Push current record */
3386
m->seg.base = tbase;
3387
m->seg.size = tsize;
3388
set_segment_flags(&m->seg, mmapped);
3391
/* Insert trailing fenceposts */
3393
mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
3394
p->head = FENCEPOST_HEAD;
3396
if ((char*)(&(nextp->head)) < old_end)
3401
assert(nfences >= 2);
3403
/* Insert the rest of old top into a bin as an ordinary free chunk */
3404
if (csp != old_top) {
3405
mchunkptr q = (mchunkptr)old_top;
3406
size_t psize = csp - old_top;
3407
mchunkptr tn = chunk_plus_offset(q, psize);
3408
set_free_with_pinuse(q, psize, tn);
3409
insert_chunk(m, q, psize);
3412
check_top_chunk(m, m->top);
3415
/* -------------------------- System allocation -------------------------- */
3417
/* Get memory from system using MORECORE or MMAP */
3418
static void* sys_alloc(mstate m, size_t nb) {
3419
char* tbase = CMFAIL;
3421
flag_t mmap_flag = 0;
3425
/* Directly map large chunks */
3426
if (use_mmap(m) && nb >= mparams.mmap_threshold) {
3427
void* mem = mmap_alloc(m, nb);
3433
Try getting memory in any of three ways (in most-preferred to
3434
least-preferred order):
3435
1. A call to MORECORE that can normally contiguously extend memory.
3436
(disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
3437
or main space is mmapped or a previous contiguous call failed)
3438
2. A call to MMAP new space (disabled if not HAVE_MMAP).
3439
Note that under the default settings, if MORECORE is unable to
3440
fulfill a request, and HAVE_MMAP is true, then mmap is
3441
used as a noncontiguous system allocator. This is a useful backup
3442
strategy for systems with holes in address spaces -- in this case
3443
sbrk cannot contiguously expand the heap, but mmap may be able to
3445
3. A call to MORECORE that cannot usually contiguously extend memory.
3446
(disabled if not HAVE_MORECORE)
3449
if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
3451
msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
3453
ACQUIRE_MORECORE_LOCK();
3455
if (ss == 0) { /* First time through or recovery */
3456
char* base = (char*)CALL_MORECORE(0);
3457
if (base != CMFAIL) {
3458
asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
3459
/* Adjust to end on a page boundary */
3460
if (!is_page_aligned(base))
3461
asize += (page_align((size_t)base) - (size_t)base);
3462
/* Can't call MORECORE if size is negative when treated as signed */
3463
if (asize < HALF_MAX_SIZE_T &&
3464
(br = (char*)(CALL_MORECORE(asize))) == base) {
3471
/* Subtract out existing available top space from MORECORE request. */
3472
asize = granularity_align(nb - m->topsize + TOP_FOOT_SIZE + SIZE_T_ONE);
3473
/* Use mem here only if it did continuously extend old space */
3474
if (asize < HALF_MAX_SIZE_T &&
3475
(br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {
3481
if (tbase == CMFAIL) { /* Cope with partial failure */
3482
if (br != CMFAIL) { /* Try to use/extend the space we did get */
3483
if (asize < HALF_MAX_SIZE_T &&
3484
asize < nb + TOP_FOOT_SIZE + SIZE_T_ONE) {
3485
size_t esize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE - asize);
3486
if (esize < HALF_MAX_SIZE_T) {
3487
char* end = (char*)CALL_MORECORE(esize);
3490
else { /* Can't use; try to release */
3491
(void)CALL_MORECORE(-asize);
3497
if (br != CMFAIL) { /* Use the space we did get */
3502
disable_contiguous(m); /* Don't try contiguous path in the future */
3505
RELEASE_MORECORE_LOCK();
3508
if (HAVE_MMAP && tbase == CMFAIL) { /* Try MMAP */
3509
size_t req = nb + TOP_FOOT_SIZE + SIZE_T_ONE;
3510
size_t rsize = granularity_align(req);
3511
if (rsize > nb) { /* Fail if wraps around zero */
3512
char* mp = (char*)(CALL_MMAP(rsize));
3516
mmap_flag = IS_MMAPPED_BIT;
3521
if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
3522
size_t asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
3523
if (asize < HALF_MAX_SIZE_T) {
3526
ACQUIRE_MORECORE_LOCK();
3527
br = (char*)(CALL_MORECORE(asize));
3528
end = (char*)(CALL_MORECORE(0));
3529
RELEASE_MORECORE_LOCK();
3530
if (br != CMFAIL && end != CMFAIL && br < end) {
3531
size_t ssize = end - br;
3532
if (ssize > nb + TOP_FOOT_SIZE) {
3540
if (tbase != CMFAIL) {
3542
if ((m->footprint += tsize) > m->max_footprint)
3543
m->max_footprint = m->footprint;
3545
if (!is_initialized(m)) { /* first-time initialization */
3546
m->seg.base = m->least_addr = tbase;
3547
m->seg.size = tsize;
3548
set_segment_flags(&m->seg, mmap_flag);
3549
m->magic = mparams.magic;
3552
init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
3554
/* Offset top by embedded malloc_state */
3555
mchunkptr mn = next_chunk(mem2chunk(m));
3556
init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
3561
/* Try to merge with an existing segment */
3562
msegmentptr sp = &m->seg;
3563
while (sp != 0 && tbase != sp->base + sp->size)
3566
!is_extern_segment(sp) &&
3567
check_segment_merge(sp, tbase, tsize) &&
3568
(get_segment_flags(sp) & IS_MMAPPED_BIT) == mmap_flag &&
3569
segment_holds(sp, m->top)) { /* append */
3571
init_top(m, m->top, m->topsize + tsize);
3574
if (tbase < m->least_addr)
3575
m->least_addr = tbase;
3577
while (sp != 0 && sp->base != tbase + tsize)
3580
!is_extern_segment(sp) &&
3581
check_segment_merge(sp, tbase, tsize) &&
3582
(get_segment_flags(sp) & IS_MMAPPED_BIT) == mmap_flag) {
3583
char* oldbase = sp->base;
3586
return prepend_alloc(m, tbase, oldbase, nb);
3589
add_segment(m, tbase, tsize, mmap_flag);
3593
if (nb < m->topsize) { /* Allocate from new or extended top space */
3594
size_t rsize = m->topsize -= nb;
3595
mchunkptr p = m->top;
3596
mchunkptr r = m->top = chunk_plus_offset(p, nb);
3597
r->head = rsize | PINUSE_BIT;
3598
set_size_and_pinuse_of_inuse_chunk(m, p, nb);
3599
check_top_chunk(m, m->top);
3600
check_malloced_chunk(m, chunk2mem(p), nb);
3601
return chunk2mem(p);
3605
MALLOC_FAILURE_ACTION;
3609
/* ----------------------- system deallocation -------------------------- */
3611
/* Unmap and unlink any mmapped segments that don't contain used chunks */
3612
static size_t release_unused_segments(mstate m) {
3613
size_t released = 0;
3614
msegmentptr pred = &m->seg;
3615
msegmentptr sp = pred->next;
3617
char* base = sp->base;
3618
size_t size = sp->size;
3619
msegmentptr next = sp->next;
3620
if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
3621
mchunkptr p = align_as_chunk(base);
3622
size_t psize = chunksize(p);
3623
/* Can unmap if first chunk holds entire segment and not pinned */
3624
if (!cinuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
3625
tchunkptr tp = (tchunkptr)p;
3626
assert(segment_holds(sp, (char*)sp));
3632
unlink_large_chunk(m, tp);
3634
if (CALL_MUNMAP(base, size) == 0) {
3636
m->footprint -= size;
3637
/* unlink obsoleted record */
3641
else { /* back out if cannot unmap */
3642
insert_large_chunk(m, tp, psize);
3652
static int sys_trim(mstate m, size_t pad) {
3653
size_t released = 0;
3654
if (pad < MAX_REQUEST && is_initialized(m)) {
3655
pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
3657
if (m->topsize > pad) {
3658
/* Shrink top space in granularity-size units, keeping at least one */
3659
size_t unit = mparams.granularity;
3660
size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
3662
msegmentptr sp = segment_holding(m, (char*)m->top);
3664
if (!is_extern_segment(sp)) {
3665
if (is_mmapped_segment(sp)) {
3667
sp->size >= extra &&
3668
!has_segment_link(m, sp)) { /* can't shrink if pinned */
3669
size_t newsize = sp->size - extra;
3670
/* Prefer mremap, fall back to munmap */
3671
if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
3672
(CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
3677
else if (HAVE_MORECORE) {
3678
if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
3679
extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
3680
ACQUIRE_MORECORE_LOCK();
3682
/* Make sure end of memory is where we last set it. */
3683
char* old_br = (char*)(CALL_MORECORE(0));
3684
if (old_br == sp->base + sp->size) {
3685
char* rel_br = (char*)(CALL_MORECORE(-extra));
3686
char* new_br = (char*)(CALL_MORECORE(0));
3687
if (rel_br != CMFAIL && new_br < old_br)
3688
released = old_br - new_br;
3691
RELEASE_MORECORE_LOCK();
3695
if (released != 0) {
3696
sp->size -= released;
3697
m->footprint -= released;
3698
init_top(m, m->top, m->topsize - released);
3699
check_top_chunk(m, m->top);
3703
/* Unmap any unused mmapped segments */
3705
released += release_unused_segments(m);
3707
/* On failure, disable autotrim to avoid repeated failed future calls */
3709
m->trim_check = MAX_SIZE_T;
3712
return (released != 0)? 1 : 0;
3715
/* ---------------------------- malloc support --------------------------- */
3717
/* allocate a large request from the best fitting chunk in a treebin */
3718
static void* tmalloc_large(mstate m, size_t nb) {
3720
size_t rsize = -nb; /* Unsigned negation */
3723
compute_tree_index(nb, idx);
3725
if ((t = *treebin_at(m, idx)) != 0) {
3726
/* Traverse tree for this bin looking for node with size == nb */
3727
size_t sizebits = nb << leftshift_for_tree_index(idx);
3728
tchunkptr rst = 0; /* The deepest untaken right subtree */
3731
size_t trem = chunksize(t) - nb;
3734
if ((rsize = trem) == 0)
3738
t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
3739
if (rt != 0 && rt != t)
3742
t = rst; /* set t to least subtree holding sizes > nb */
3749
if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
3750
binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
3751
if (leftbits != 0) {
3753
binmap_t leastbit = least_bit(leftbits);
3754
compute_bit2idx(leastbit, i);
3755
t = *treebin_at(m, i);
3759
while (t != 0) { /* find smallest of tree or subtree */
3760
size_t trem = chunksize(t) - nb;
3765
t = leftmost_child(t);
3768
/* If dv is a better fit, return 0 so malloc will use it */
3769
if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
3770
if (RTCHECK(ok_address(m, v))) { /* split */
3771
mchunkptr r = chunk_plus_offset(v, nb);
3772
assert(chunksize(v) == rsize + nb);
3773
if (RTCHECK(ok_next(v, r))) {
3774
unlink_large_chunk(m, v);
3775
if (rsize < MIN_CHUNK_SIZE)
3776
set_inuse_and_pinuse(m, v, (rsize + nb));
3778
set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3779
set_size_and_pinuse_of_free_chunk(r, rsize);
3780
insert_chunk(m, r, rsize);
3782
return chunk2mem(v);
3785
CORRUPTION_ERROR_ACTION(m);
3790
/* allocate a small request from the best fitting chunk in a treebin */
3791
static void* tmalloc_small(mstate m, size_t nb) {
3795
binmap_t leastbit = least_bit(m->treemap);
3796
compute_bit2idx(leastbit, i);
3798
v = t = *treebin_at(m, i);
3799
rsize = chunksize(t) - nb;
3801
while ((t = leftmost_child(t)) != 0) {
3802
size_t trem = chunksize(t) - nb;
3809
if (RTCHECK(ok_address(m, v))) {
3810
mchunkptr r = chunk_plus_offset(v, nb);
3811
assert(chunksize(v) == rsize + nb);
3812
if (RTCHECK(ok_next(v, r))) {
3813
unlink_large_chunk(m, v);
3814
if (rsize < MIN_CHUNK_SIZE)
3815
set_inuse_and_pinuse(m, v, (rsize + nb));
3817
set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3818
set_size_and_pinuse_of_free_chunk(r, rsize);
3819
replace_dv(m, r, rsize);
3821
return chunk2mem(v);
3825
CORRUPTION_ERROR_ACTION(m);
3829
/* --------------------------- realloc support --------------------------- */
3831
static void* internal_realloc(mstate m, void* oldmem, size_t bytes) {
3832
if (bytes >= MAX_REQUEST) {
3833
MALLOC_FAILURE_ACTION;
3836
if (!PREACTION(m)) {
3837
mchunkptr oldp = mem2chunk(oldmem);
3838
size_t oldsize = chunksize(oldp);
3839
mchunkptr next = chunk_plus_offset(oldp, oldsize);
3843
/* Try to either shrink or extend into top. Else malloc-copy-free */
3845
if (RTCHECK(ok_address(m, oldp) && ok_cinuse(oldp) &&
3846
ok_next(oldp, next) && ok_pinuse(next))) {
3847
size_t nb = request2size(bytes);
3848
if (is_mmapped(oldp))
3849
newp = mmap_resize(m, oldp, nb);
3850
else if (oldsize >= nb) { /* already big enough */
3851
size_t rsize = oldsize - nb;
3853
if (rsize >= MIN_CHUNK_SIZE) {
3854
mchunkptr remainder = chunk_plus_offset(newp, nb);
3855
set_inuse(m, newp, nb);
3856
set_inuse(m, remainder, rsize);
3857
extra = chunk2mem(remainder);
3860
else if (next == m->top && oldsize + m->topsize > nb) {
3861
/* Expand into top */
3862
size_t newsize = oldsize + m->topsize;
3863
size_t newtopsize = newsize - nb;
3864
mchunkptr newtop = chunk_plus_offset(oldp, nb);
3865
set_inuse(m, oldp, nb);
3866
newtop->head = newtopsize |PINUSE_BIT;
3868
m->topsize = newtopsize;
3873
USAGE_ERROR_ACTION(m, oldmem);
3882
internal_free(m, extra);
3884
check_inuse_chunk(m, newp);
3885
return chunk2mem(newp);
3888
void* newmem = internal_malloc(m, bytes);
3890
size_t oc = oldsize - overhead_for(oldp);
3891
memcpy(newmem, oldmem, (oc < bytes)? oc : bytes);
3892
internal_free(m, oldmem);
3900
/* --------------------------- memalign support -------------------------- */
3902
static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
3903
if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */
3904
return internal_malloc(m, bytes);
3905
if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
3906
alignment = MIN_CHUNK_SIZE;
3907
if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
3908
size_t a = MALLOC_ALIGNMENT << 1;
3909
while (a < alignment) a <<= 1;
3913
if (bytes >= MAX_REQUEST - alignment) {
3914
if (m != 0) { /* Test isn't needed but avoids compiler warning */
3915
MALLOC_FAILURE_ACTION;
3919
size_t nb = request2size(bytes);
3920
size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
3921
char* mem = (char*)internal_malloc(m, req);
3925
mchunkptr p = mem2chunk(mem);
3927
if (PREACTION(m)) return 0;
3928
if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */
3930
Find an aligned spot inside chunk. Since we need to give
3931
back leading space in a chunk of at least MIN_CHUNK_SIZE, if
3932
the first calculation places us at a spot with less than
3933
MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
3934
We've allocated enough total room so that this is always
3937
char* br = (char*)mem2chunk((size_t)(((size_t)(mem +
3941
char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
3943
mchunkptr newp = (mchunkptr)pos;
3944
size_t leadsize = pos - (char*)(p);
3945
size_t newsize = chunksize(p) - leadsize;
3947
if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */
3948
newp->prev_foot = p->prev_foot + leadsize;
3949
newp->head = (newsize|CINUSE_BIT);
3951
else { /* Otherwise, give back leader, use the rest */
3952
set_inuse(m, newp, newsize);
3953
set_inuse(m, p, leadsize);
3954
leader = chunk2mem(p);
3959
/* Give back spare room at the end */
3960
if (!is_mmapped(p)) {
3961
size_t size = chunksize(p);
3962
if (size > nb + MIN_CHUNK_SIZE) {
3963
size_t remainder_size = size - nb;
3964
mchunkptr remainder = chunk_plus_offset(p, nb);
3965
set_inuse(m, p, nb);
3966
set_inuse(m, remainder, remainder_size);
3967
trailer = chunk2mem(remainder);
3971
assert (chunksize(p) >= nb);
3972
assert((((size_t)(chunk2mem(p))) % alignment) == 0);
3973
check_inuse_chunk(m, p);
3976
internal_free(m, leader);
3979
internal_free(m, trailer);
3981
return chunk2mem(p);
3987
/* ------------------------ comalloc/coalloc support --------------------- */
3989
static void** ialloc(mstate m,
3995
This provides common support for independent_X routines, handling
3996
all of the combinations that can result.
3999
bit 0 set if all elements are same size (using sizes[0])
4000
bit 1 set if elements should be zeroed
4003
size_t element_size; /* chunksize of each element, if all same */
4004
size_t contents_size; /* total size of elements */
4005
size_t array_size; /* request size of pointer array */
4006
void* mem; /* malloced aggregate space */
4007
mchunkptr p; /* corresponding chunk */
4008
size_t remainder_size; /* remaining bytes while splitting */
4009
void** marray; /* either "chunks" or malloced ptr array */
4010
mchunkptr array_chunk; /* chunk for malloced ptr array */
4011
flag_t was_enabled; /* to disable mmap */
4015
/* compute array length, if needed */
4017
if (n_elements == 0)
4018
return chunks; /* nothing to do */
4023
/* if empty req, must still return chunk representing empty array */
4024
if (n_elements == 0)
4025
return (void**)internal_malloc(m, 0);
4027
array_size = request2size(n_elements * (sizeof(void*)));
4030
/* compute total element size */
4031
if (opts & 0x1) { /* all-same-size */
4032
element_size = request2size(*sizes);
4033
contents_size = n_elements * element_size;
4035
else { /* add up all the sizes */
4038
for (i = 0; i != n_elements; ++i)
4039
contents_size += request2size(sizes[i]);
4042
size = contents_size + array_size;
4045
Allocate the aggregate chunk. First disable direct-mmapping so
4046
malloc won't use it, since we would not be able to later
4047
free/realloc space internal to a segregated mmap region.
4049
was_enabled = use_mmap(m);
4051
mem = internal_malloc(m, size - CHUNK_OVERHEAD);
4057
if (PREACTION(m)) return 0;
4059
remainder_size = chunksize(p);
4061
assert(!is_mmapped(p));
4063
if (opts & 0x2) { /* optionally clear the elements */
4064
memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);
4067
/* If not provided, allocate the pointer array as final part of chunk */
4069
size_t array_chunk_size;
4070
array_chunk = chunk_plus_offset(p, contents_size);
4071
array_chunk_size = remainder_size - contents_size;
4072
marray = (void**) (chunk2mem(array_chunk));
4073
set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);
4074
remainder_size = contents_size;
4077
/* split out elements */
4078
for (i = 0; ; ++i) {
4079
marray[i] = chunk2mem(p);
4080
if (i != n_elements-1) {
4081
if (element_size != 0)
4082
size = element_size;
4084
size = request2size(sizes[i]);
4085
remainder_size -= size;
4086
set_size_and_pinuse_of_inuse_chunk(m, p, size);
4087
p = chunk_plus_offset(p, size);
4089
else { /* the final element absorbs any overallocation slop */
4090
set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);
4096
if (marray != chunks) {
4097
/* final element must have exactly exhausted chunk */
4098
if (element_size != 0) {
4099
assert(remainder_size == element_size);
4102
assert(remainder_size == request2size(sizes[i]));
4104
check_inuse_chunk(m, mem2chunk(marray));
4106
for (i = 0; i != n_elements; ++i)
4107
check_inuse_chunk(m, mem2chunk(marray[i]));
4116
/* -------------------------- public routines ---------------------------- */
4120
void* dlmalloc(size_t bytes) {
4123
If a small request (< 256 bytes minus per-chunk overhead):
4124
1. If one exists, use a remainderless chunk in associated smallbin.
4125
(Remainderless means that there are too few excess bytes to
4126
represent as a chunk.)
4127
2. If it is big enough, use the dv chunk, which is normally the
4128
chunk adjacent to the one used for the most recent small request.
4129
3. If one exists, split the smallest available chunk in a bin,
4130
saving remainder in dv.
4131
4. If it is big enough, use the top chunk.
4132
5. If available, get memory from system and use it
4133
Otherwise, for a large request:
4134
1. Find the smallest available binned chunk that fits, and use it
4135
if it is better fitting than dv chunk, splitting if necessary.
4136
2. If better fitting than any binned chunk, use the dv chunk.
4137
3. If it is big enough, use the top chunk.
4138
4. If request size >= mmap threshold, try to directly mmap this chunk.
4139
5. If available, get memory from system and use it
4141
The ugly goto's here ensure that postaction occurs along all paths.
4144
if (!PREACTION(gm)) {
4147
if (bytes <= MAX_SMALL_REQUEST) {
4150
nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
4151
idx = small_index(nb);
4152
smallbits = gm->smallmap >> idx;
4154
if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
4156
idx += ~smallbits & 1; /* Uses next bin if idx empty */
4157
b = smallbin_at(gm, idx);
4159
assert(chunksize(p) == small_index2size(idx));
4160
unlink_first_small_chunk(gm, b, p, idx);
4161
set_inuse_and_pinuse(gm, p, small_index2size(idx));
4163
check_malloced_chunk(gm, mem, nb);
4167
else if (nb > gm->dvsize) {
4168
if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
4172
binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4173
binmap_t leastbit = least_bit(leftbits);
4174
compute_bit2idx(leastbit, i);
4175
b = smallbin_at(gm, i);
4177
assert(chunksize(p) == small_index2size(i));
4178
unlink_first_small_chunk(gm, b, p, i);
4179
rsize = small_index2size(i) - nb;
4180
/* Fit here cannot be remainderless if 4byte sizes */
4181
if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4182
set_inuse_and_pinuse(gm, p, small_index2size(i));
4184
set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4185
r = chunk_plus_offset(p, nb);
4186
set_size_and_pinuse_of_free_chunk(r, rsize);
4187
replace_dv(gm, r, rsize);
4190
check_malloced_chunk(gm, mem, nb);
4194
else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
4195
check_malloced_chunk(gm, mem, nb);
4200
else if (bytes >= MAX_REQUEST)
4201
nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
4203
nb = pad_request(bytes);
4204
if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
4205
check_malloced_chunk(gm, mem, nb);
4210
if (nb <= gm->dvsize) {
4211
size_t rsize = gm->dvsize - nb;
4212
mchunkptr p = gm->dv;
4213
if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4214
mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
4216
set_size_and_pinuse_of_free_chunk(r, rsize);
4217
set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4219
else { /* exhaust dv */
4220
size_t dvs = gm->dvsize;
4223
set_inuse_and_pinuse(gm, p, dvs);
4226
check_malloced_chunk(gm, mem, nb);
4230
else if (nb < gm->topsize) { /* Split top */
4231
size_t rsize = gm->topsize -= nb;
4232
mchunkptr p = gm->top;
4233
mchunkptr r = gm->top = chunk_plus_offset(p, nb);
4234
r->head = rsize | PINUSE_BIT;
4235
set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4237
check_top_chunk(gm, gm->top);
4238
check_malloced_chunk(gm, mem, nb);
4242
mem = sys_alloc(gm, nb);
4252
void dlfree(void* mem) {
4254
Consolidate freed chunks with preceding or succeeding bordering
4255
free chunks, if they exist, and then place in a bin. Intermixed
4256
with special cases for top, dv, mmapped chunks, and usage errors.
4260
mchunkptr p = mem2chunk(mem);
4262
mstate fm = get_mstate_for(p);
4263
if (!ok_magic(fm)) {
4264
USAGE_ERROR_ACTION(fm, p);
4269
#endif /* FOOTERS */
4270
if (!PREACTION(fm)) {
4271
check_inuse_chunk(fm, p);
4272
if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
4273
size_t psize = chunksize(p);
4274
mchunkptr next = chunk_plus_offset(p, psize);
4276
size_t prevsize = p->prev_foot;
4277
if ((prevsize & IS_MMAPPED_BIT) != 0) {
4278
prevsize &= ~IS_MMAPPED_BIT;
4279
psize += prevsize + MMAP_FOOT_PAD;
4280
if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4281
fm->footprint -= psize;
4285
mchunkptr prev = chunk_minus_offset(p, prevsize);
4288
if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4290
unlink_chunk(fm, p, prevsize);
4292
else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4294
set_free_with_pinuse(p, psize, next);
4303
if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
4304
if (!cinuse(next)) { /* consolidate forward */
4305
if (next == fm->top) {
4306
size_t tsize = fm->topsize += psize;
4308
p->head = tsize | PINUSE_BIT;
4313
if (should_trim(fm, tsize))
4317
else if (next == fm->dv) {
4318
size_t dsize = fm->dvsize += psize;
4320
set_size_and_pinuse_of_free_chunk(p, dsize);
4324
size_t nsize = chunksize(next);
4326
unlink_chunk(fm, next, nsize);
4327
set_size_and_pinuse_of_free_chunk(p, psize);
4335
set_free_with_pinuse(p, psize, next);
4336
insert_chunk(fm, p, psize);
4337
check_free_chunk(fm, p);
4342
USAGE_ERROR_ACTION(fm, p);
4349
#endif /* FOOTERS */
4352
void* dlcalloc(size_t n_elements, size_t elem_size) {
4355
if (n_elements != 0) {
4356
req = n_elements * elem_size;
4357
if (((n_elements | elem_size) & ~(size_t)0xffff) &&
4358
(req / n_elements != elem_size))
4359
req = MAX_SIZE_T; /* force downstream failure on overflow */
4361
mem = dlmalloc(req);
4362
if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
4363
memset(mem, 0, req);
4367
void* dlrealloc(void* oldmem, size_t bytes) {
4369
return dlmalloc(bytes);
4370
#ifdef REALLOC_ZERO_BYTES_FREES
4375
#endif /* REALLOC_ZERO_BYTES_FREES */
4380
mstate m = get_mstate_for(mem2chunk(oldmem));
4382
USAGE_ERROR_ACTION(m, oldmem);
4385
#endif /* FOOTERS */
4386
return internal_realloc(m, oldmem, bytes);
4390
void* dlmemalign(size_t alignment, size_t bytes) {
4391
return internal_memalign(gm, alignment, bytes);
4394
void** dlindependent_calloc(size_t n_elements, size_t elem_size,
4396
size_t sz = elem_size; /* serves as 1-element array */
4397
return ialloc(gm, n_elements, &sz, 3, chunks);
4400
void** dlindependent_comalloc(size_t n_elements, size_t sizes[],
4402
return ialloc(gm, n_elements, sizes, 0, chunks);
4405
void* dlvalloc(size_t bytes) {
4408
pagesz = mparams.page_size;
4409
return dlmemalign(pagesz, bytes);
4412
void* dlpvalloc(size_t bytes) {
4415
pagesz = mparams.page_size;
4416
return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));
4419
int dlmalloc_trim(size_t pad) {
4421
if (!PREACTION(gm)) {
4422
result = sys_trim(gm, pad);
4428
size_t dlmalloc_footprint(void) {
4429
return gm->footprint;
4432
size_t dlmalloc_max_footprint(void) {
4433
return gm->max_footprint;
4437
struct mallinfo dlmallinfo(void) {
4438
return internal_mallinfo(gm);
4440
#endif /* NO_MALLINFO */
4442
void dlmalloc_stats() {
4443
internal_malloc_stats(gm);
4446
size_t dlmalloc_usable_size(void* mem) {
4448
mchunkptr p = mem2chunk(mem);
4450
return chunksize(p) - overhead_for(p);
4455
int dlmallopt(int param_number, int value) {
4456
return change_mparam(param_number, value);
4459
#endif /* !ONLY_MSPACES */
4461
/* ----------------------------- user mspaces ---------------------------- */
4465
static mstate init_user_mstate(char* tbase, size_t tsize) {
4466
size_t msize = pad_request(sizeof(struct malloc_state));
4468
mchunkptr msp = align_as_chunk(tbase);
4469
mstate m = (mstate)(chunk2mem(msp));
4470
memset(m, 0, msize);
4471
INITIAL_LOCK(&m->mutex);
4472
msp->head = (msize|PINUSE_BIT|CINUSE_BIT);
4473
m->seg.base = m->least_addr = tbase;
4474
m->seg.size = m->footprint = m->max_footprint = tsize;
4475
m->magic = mparams.magic;
4476
m->mflags = mparams.default_mflags;
4477
disable_contiguous(m);
4479
mn = next_chunk(mem2chunk(m));
4480
init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
4481
check_top_chunk(m, m->top);
4485
mspace create_mspace(size_t capacity, int locked) {
4487
size_t msize = pad_request(sizeof(struct malloc_state));
4488
init_mparams(); /* Ensure pagesize etc initialized */
4490
if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4491
size_t rs = ((capacity == 0)? mparams.granularity :
4492
(capacity + TOP_FOOT_SIZE + msize));
4493
size_t tsize = granularity_align(rs);
4494
char* tbase = (char*)(CALL_MMAP(tsize));
4495
if (tbase != CMFAIL) {
4496
m = init_user_mstate(tbase, tsize);
4497
set_segment_flags(&m->seg, IS_MMAPPED_BIT);
4498
set_lock(m, locked);
4504
mspace create_mspace_with_base(void* base, size_t capacity, int locked) {
4506
size_t msize = pad_request(sizeof(struct malloc_state));
4507
init_mparams(); /* Ensure pagesize etc initialized */
4509
if (capacity > msize + TOP_FOOT_SIZE &&
4510
capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4511
m = init_user_mstate((char*)base, capacity);
4512
set_segment_flags(&m->seg, EXTERN_BIT);
4513
set_lock(m, locked);
4518
size_t destroy_mspace(mspace msp) {
4520
mstate ms = (mstate)msp;
4522
msegmentptr sp = &ms->seg;
4524
char* base = sp->base;
4525
size_t size = sp->size;
4526
flag_t flag = get_segment_flags(sp);
4528
if ((flag & IS_MMAPPED_BIT) && !(flag & EXTERN_BIT) &&
4529
CALL_MUNMAP(base, size) == 0)
4534
USAGE_ERROR_ACTION(ms,ms);
4540
mspace versions of routines are near-clones of the global
4541
versions. This is not so nice but better than the alternatives.
4545
void* mspace_malloc(mspace msp, size_t bytes) {
4546
mstate ms = (mstate)msp;
4547
if (!ok_magic(ms)) {
4548
USAGE_ERROR_ACTION(ms,ms);
4551
if (!PREACTION(ms)) {
4554
if (bytes <= MAX_SMALL_REQUEST) {
4557
nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
4558
idx = small_index(nb);
4559
smallbits = ms->smallmap >> idx;
4561
if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
4563
idx += ~smallbits & 1; /* Uses next bin if idx empty */
4564
b = smallbin_at(ms, idx);
4566
assert(chunksize(p) == small_index2size(idx));
4567
unlink_first_small_chunk(ms, b, p, idx);
4568
set_inuse_and_pinuse(ms, p, small_index2size(idx));
4570
check_malloced_chunk(ms, mem, nb);
4574
else if (nb > ms->dvsize) {
4575
if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
4579
binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4580
binmap_t leastbit = least_bit(leftbits);
4581
compute_bit2idx(leastbit, i);
4582
b = smallbin_at(ms, i);
4584
assert(chunksize(p) == small_index2size(i));
4585
unlink_first_small_chunk(ms, b, p, i);
4586
rsize = small_index2size(i) - nb;
4587
/* Fit here cannot be remainderless if 4byte sizes */
4588
if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4589
set_inuse_and_pinuse(ms, p, small_index2size(i));
4591
set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4592
r = chunk_plus_offset(p, nb);
4593
set_size_and_pinuse_of_free_chunk(r, rsize);
4594
replace_dv(ms, r, rsize);
4597
check_malloced_chunk(ms, mem, nb);
4601
else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
4602
check_malloced_chunk(ms, mem, nb);
4607
else if (bytes >= MAX_REQUEST)
4608
nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
4610
nb = pad_request(bytes);
4611
if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
4612
check_malloced_chunk(ms, mem, nb);
4617
if (nb <= ms->dvsize) {
4618
size_t rsize = ms->dvsize - nb;
4619
mchunkptr p = ms->dv;
4620
if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4621
mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
4623
set_size_and_pinuse_of_free_chunk(r, rsize);
4624
set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4626
else { /* exhaust dv */
4627
size_t dvs = ms->dvsize;
4630
set_inuse_and_pinuse(ms, p, dvs);
4633
check_malloced_chunk(ms, mem, nb);
4637
else if (nb < ms->topsize) { /* Split top */
4638
size_t rsize = ms->topsize -= nb;
4639
mchunkptr p = ms->top;
4640
mchunkptr r = ms->top = chunk_plus_offset(p, nb);
4641
r->head = rsize | PINUSE_BIT;
4642
set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4644
check_top_chunk(ms, ms->top);
4645
check_malloced_chunk(ms, mem, nb);
4649
mem = sys_alloc(ms, nb);
4659
void mspace_free(mspace msp, void* mem) {
4661
mchunkptr p = mem2chunk(mem);
4663
mstate fm = get_mstate_for(p);
4665
mstate fm = (mstate)msp;
4666
#endif /* FOOTERS */
4667
if (!ok_magic(fm)) {
4668
USAGE_ERROR_ACTION(fm, p);
4671
if (!PREACTION(fm)) {
4672
check_inuse_chunk(fm, p);
4673
if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
4674
size_t psize = chunksize(p);
4675
mchunkptr next = chunk_plus_offset(p, psize);
4677
size_t prevsize = p->prev_foot;
4678
if ((prevsize & IS_MMAPPED_BIT) != 0) {
4679
prevsize &= ~IS_MMAPPED_BIT;
4680
psize += prevsize + MMAP_FOOT_PAD;
4681
if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4682
fm->footprint -= psize;
4686
mchunkptr prev = chunk_minus_offset(p, prevsize);
4689
if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4691
unlink_chunk(fm, p, prevsize);
4693
else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4695
set_free_with_pinuse(p, psize, next);
4704
if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
4705
if (!cinuse(next)) { /* consolidate forward */
4706
if (next == fm->top) {
4707
size_t tsize = fm->topsize += psize;
4709
p->head = tsize | PINUSE_BIT;
4714
if (should_trim(fm, tsize))
4718
else if (next == fm->dv) {
4719
size_t dsize = fm->dvsize += psize;
4721
set_size_and_pinuse_of_free_chunk(p, dsize);
4725
size_t nsize = chunksize(next);
4727
unlink_chunk(fm, next, nsize);
4728
set_size_and_pinuse_of_free_chunk(p, psize);
4736
set_free_with_pinuse(p, psize, next);
4737
insert_chunk(fm, p, psize);
4738
check_free_chunk(fm, p);
4743
USAGE_ERROR_ACTION(fm, p);
4750
void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
4753
mstate ms = (mstate)msp;
4754
if (!ok_magic(ms)) {
4755
USAGE_ERROR_ACTION(ms,ms);
4758
if (n_elements != 0) {
4759
req = n_elements * elem_size;
4760
if (((n_elements | elem_size) & ~(size_t)0xffff) &&
4761
(req / n_elements != elem_size))
4762
req = MAX_SIZE_T; /* force downstream failure on overflow */
4764
mem = internal_malloc(ms, req);
4765
if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
4766
memset(mem, 0, req);
4770
void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
4772
return mspace_malloc(msp, bytes);
4773
#ifdef REALLOC_ZERO_BYTES_FREES
4775
mspace_free(msp, oldmem);
4778
#endif /* REALLOC_ZERO_BYTES_FREES */
4781
mchunkptr p = mem2chunk(oldmem);
4782
mstate ms = get_mstate_for(p);
4784
mstate ms = (mstate)msp;
4785
#endif /* FOOTERS */
4786
if (!ok_magic(ms)) {
4787
USAGE_ERROR_ACTION(ms,ms);
4790
return internal_realloc(ms, oldmem, bytes);
4794
void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
4795
mstate ms = (mstate)msp;
4796
if (!ok_magic(ms)) {
4797
USAGE_ERROR_ACTION(ms,ms);
4800
return internal_memalign(ms, alignment, bytes);
4803
void** mspace_independent_calloc(mspace msp, size_t n_elements,
4804
size_t elem_size, void* chunks[]) {
4805
size_t sz = elem_size; /* serves as 1-element array */
4806
mstate ms = (mstate)msp;
4807
if (!ok_magic(ms)) {
4808
USAGE_ERROR_ACTION(ms,ms);
4811
return ialloc(ms, n_elements, &sz, 3, chunks);
4814
void** mspace_independent_comalloc(mspace msp, size_t n_elements,
4815
size_t sizes[], void* chunks[]) {
4816
mstate ms = (mstate)msp;
4817
if (!ok_magic(ms)) {
4818
USAGE_ERROR_ACTION(ms,ms);
4821
return ialloc(ms, n_elements, sizes, 0, chunks);
4824
int mspace_trim(mspace msp, size_t pad) {
4826
mstate ms = (mstate)msp;
4828
if (!PREACTION(ms)) {
4829
result = sys_trim(ms, pad);
4834
USAGE_ERROR_ACTION(ms,ms);
4839
void mspace_malloc_stats(mspace msp) {
4840
mstate ms = (mstate)msp;
4842
internal_malloc_stats(ms);
4845
USAGE_ERROR_ACTION(ms,ms);
4849
size_t mspace_footprint(mspace msp) {
4851
mstate ms = (mstate)msp;
4853
result = ms->footprint;
4855
USAGE_ERROR_ACTION(ms,ms);
4860
size_t mspace_max_footprint(mspace msp) {
4862
mstate ms = (mstate)msp;
4864
result = ms->max_footprint;
4866
USAGE_ERROR_ACTION(ms,ms);
4872
struct mallinfo mspace_mallinfo(mspace msp) {
4873
mstate ms = (mstate)msp;
4874
if (!ok_magic(ms)) {
4875
USAGE_ERROR_ACTION(ms,ms);
4877
return internal_mallinfo(ms);
4879
#endif /* NO_MALLINFO */
4881
int mspace_mallopt(int param_number, int value) {
4882
return change_mparam(param_number, value);
4885
#endif /* MSPACES */
4887
/* -------------------- Alternative MORECORE functions ------------------- */
4890
Guidelines for creating a custom version of MORECORE:
4892
* For best performance, MORECORE should allocate in multiples of pagesize.
4893
* MORECORE may allocate more memory than requested. (Or even less,
4894
but this will usually result in a malloc failure.)
4895
* MORECORE must not allocate memory when given argument zero, but
4896
instead return one past the end address of memory from previous
4898
* For best performance, consecutive calls to MORECORE with positive
4899
arguments should return increasing addresses, indicating that
4900
space has been contiguously extended.
4901
* Even though consecutive calls to MORECORE need not return contiguous
4902
addresses, it must be OK for malloc'ed chunks to span multiple
4903
regions in those cases where they do happen to be contiguous.
4904
* MORECORE need not handle negative arguments -- it may instead
4905
just return MFAIL when given negative arguments.
4906
Negative arguments are always multiples of pagesize. MORECORE
4907
must not misinterpret negative args as large positive unsigned
4908
args. You can suppress all such calls from even occurring by defining
4909
MORECORE_CANNOT_TRIM,
4911
As an example alternative MORECORE, here is a custom allocator
4912
kindly contributed for pre-OSX macOS. It uses virtually but not
4913
necessarily physically contiguous non-paged memory (locked in,
4914
present and won't get swapped out). You can use it by uncommenting
4915
this section, adding some #includes, and setting up the appropriate
4918
#define MORECORE osMoreCore
4920
There is also a shutdown routine that should somehow be called for
4921
cleanup upon program exit.
4923
#define MAX_POOL_ENTRIES 100
4924
#define MINIMUM_MORECORE_SIZE (64 * 1024U)
4925
static int next_os_pool;
4926
void *our_os_pools[MAX_POOL_ENTRIES];
4928
void *osMoreCore(int size)
4931
static void *sbrk_top = 0;
4935
if (size < MINIMUM_MORECORE_SIZE)
4936
size = MINIMUM_MORECORE_SIZE;
4937
if (CurrentExecutionLevel() == kTaskLevel)
4938
ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4941
return (void *) MFAIL;
4943
// save ptrs so they can be freed during cleanup
4944
our_os_pools[next_os_pool] = ptr;
4946
ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4947
sbrk_top = (char *) ptr + size;
4952
// we don't currently support shrink behavior
4953
return (void *) MFAIL;
4961
// cleanup any allocated memory pools
4962
// called as last thing before shutting down driver
4964
void osCleanupMem(void)
4968
for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4971
PoolDeallocate(*ptr);
4979
/* -----------------------------------------------------------------------
4981
V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee)
4982
* Add max_footprint functions
4983
* Ensure all appropriate literals are size_t
4984
* Fix conditional compilation problem for some #define settings
4985
* Avoid concatenating segments with the one provided
4986
in create_mspace_with_base
4987
* Rename some variables to avoid compiler shadowing warnings
4988
* Use explicit lock initialization.
4989
* Better handling of sbrk interference.
4990
* Simplify and fix segment insertion, trimming and mspace_destroy
4991
* Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
4992
* Thanks especially to Dennis Flanagan for help on these.
4994
V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee)
4995
* Fix memalign brace error.
4997
V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee)
4998
* Fix improper #endif nesting in C++
4999
* Add explicit casts needed for C++
5001
V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee)
5002
* Use trees for large bins
5004
* Use segments to unify sbrk-based and mmap-based system allocation,
5005
removing need for emulation on most platforms without sbrk.
5006
* Default safety checks
5007
* Optional footer checks. Thanks to William Robertson for the idea.
5008
* Internal code refactoring
5009
* Incorporate suggestions and platform-specific changes.
5010
Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
5011
Aaron Bachmann, Emery Berger, and others.
5012
* Speed up non-fastbin processing enough to remove fastbins.
5013
* Remove useless cfree() to avoid conflicts with other apps.
5014
* Remove internal memcpy, memset. Compilers handle builtins better.
5015
* Remove some options that no one ever used and rename others.
5017
V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee)
5018
* Fix malloc_state bitmap array misdeclaration
5020
V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
5021
* Allow tuning of FIRST_SORTED_BIN_SIZE
5022
* Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
5023
* Better detection and support for non-contiguousness of MORECORE.
5024
Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
5025
* Bypass most of malloc if no frees. Thanks To Emery Berger.
5026
* Fix freeing of old top non-contiguous chunk im sysmalloc.
5027
* Raised default trim and map thresholds to 256K.
5028
* Fix mmap-related #defines. Thanks to Lubos Lunak.
5029
* Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
5030
* Branch-free bin calculation
5031
* Default trim and mmap thresholds now 256K.
5033
V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
5034
* Introduce independent_comalloc and independent_calloc.
5035
Thanks to Michael Pachos for motivation and help.
5036
* Make optional .h file available
5037
* Allow > 2GB requests on 32bit systems.
5038
* new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
5039
Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
5041
* Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
5043
* memalign: check alignment arg
5044
* realloc: don't try to shift chunks backwards, since this
5045
leads to more fragmentation in some programs and doesn't
5046
seem to help in any others.
5047
* Collect all cases in malloc requiring system memory into sysmalloc
5048
* Use mmap as backup to sbrk
5049
* Place all internal state in malloc_state
5050
* Introduce fastbins (although similar to 2.5.1)
5051
* Many minor tunings and cosmetic improvements
5052
* Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
5053
* Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
5054
Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
5055
* Include errno.h to support default failure action.
5057
V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
5058
* return null for negative arguments
5059
* Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5060
* Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5061
(e.g. WIN32 platforms)
5062
* Cleanup header file inclusion for WIN32 platforms
5063
* Cleanup code to avoid Microsoft Visual C++ compiler complaints
5064
* Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5065
memory allocation routines
5066
* Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5067
* Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5068
usage of 'assert' in non-WIN32 code
5069
* Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5071
* Always call 'fREe()' rather than 'free()'
5073
V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
5074
* Fixed ordering problem with boundary-stamping
5076
V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
5077
* Added pvalloc, as recommended by H.J. Liu
5078
* Added 64bit pointer support mainly from Wolfram Gloger
5079
* Added anonymously donated WIN32 sbrk emulation
5080
* Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5081
* malloc_extend_top: fix mask error that caused wastage after
5083
* Add linux mremap support code from HJ Liu
5085
V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
5086
* Integrated most documentation with the code.
5087
* Add support for mmap, with help from
5088
Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5089
* Use last_remainder in more cases.
5090
* Pack bins using idea from colin@nyx10.cs.du.edu
5091
* Use ordered bins instead of best-fit threshhold
5092
* Eliminate block-local decls to simplify tracing and debugging.
5093
* Support another case of realloc via move into top
5094
* Fix error occuring when initial sbrk_base not word-aligned.
5095
* Rely on page size for units instead of SBRK_UNIT to
5096
avoid surprises about sbrk alignment conventions.
5097
* Add mallinfo, mallopt. Thanks to Raymond Nijssen
5098
(raymond@es.ele.tue.nl) for the suggestion.
5099
* Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5100
* More precautions for cases where other routines call sbrk,
5101
courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5102
* Added macros etc., allowing use in linux libc from
5103
H.J. Lu (hjl@gnu.ai.mit.edu)
5104
* Inverted this history list
5106
V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
5107
* Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5108
* Removed all preallocation code since under current scheme
5109
the work required to undo bad preallocations exceeds
5110
the work saved in good cases for most test programs.
5111
* No longer use return list or unconsolidated bins since
5112
no scheme using them consistently outperforms those that don't
5113
given above changes.
5114
* Use best fit for very large chunks to prevent some worst-cases.
5115
* Added some support for debugging
5117
V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
5118
* Removed footers when chunks are in use. Thanks to
5119
Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5121
V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
5122
* Added malloc_trim, with help from Wolfram Gloger
5123
(wmglo@Dent.MED.Uni-Muenchen.DE).
5125
V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
5127
V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
5128
* realloc: try to expand in both directions
5129
* malloc: swap order of clean-bin strategy;
5130
* realloc: only conditionally expand backwards
5131
* Try not to scavenge used bins
5132
* Use bin counts as a guide to preallocation
5133
* Occasionally bin return list chunks in first scan
5134
* Add a few optimizations from colin@nyx10.cs.du.edu
5136
V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
5137
* faster bin computation & slightly different binning
5138
* merged all consolidations to one part of malloc proper
5139
(eliminating old malloc_find_space & malloc_clean_bin)
5140
* Scan 2 returns chunks (not just 1)
5141
* Propagate failure in realloc if malloc returns 0
5142
* Add stuff to allow compilation on non-ANSI compilers
5143
from kpv@research.att.com
5145
V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
5146
* removed potential for odd address access in prev_chunk
5147
* removed dependency on getpagesize.h
5148
* misc cosmetics and a bit more internal documentation
5149
* anticosmetics: mangled names in macros to evade debugger strangeness
5150
* tested on sparc, hp-700, dec-mips, rs6000
5151
with gcc & native cc (hp, dec only) allowing
5152
Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5154
Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
5155
* Based loosely on libg++-1.2X malloc. (It retains some of the overall
5156
structure of old version, but most details differ.)
added
removed
js/src/ctypes/libffi/src/dlmalloc.c
