2
[insert usage description etc here]
4
Last update: Sun Aug 11 17:57:59 2002 Doug Lea (dl at gee)
8
WIN32 sets up defaults for MS environment and compilers.
9
Otherwise defaults are for unix.
16
#define WIN32_LEAN_AND_MEAN
19
/* No-op failure action */
20
#define MALLOC_FAILURE_ACTION
22
/* Win32 doesn't supply or need the following headers */
23
#define LACKS_UNISTD_H
24
#define LACKS_SYS_PARAM_H
25
#define LACKS_SYS_MMAN_H
27
/* Use the supplied emulation of sbrk */
29
#define MORECORE_CONTIGUOUS 1
30
#define MORECORE_FAILURE ((void*)(-1))
32
/* Use the supplied emulation of mmap and munmap */
34
#define MUNMAP_FAILURE (-1)
37
/* These values don't really matter in windows mmap emulation */
39
#define MAP_ANONYMOUS 2
43
/* Emulation functions defined at the end of this file */
45
/* If USE_MALLOC_LOCK, use supplied critical-section-based lock functions */
46
#ifdef USE_MALLOC_LOCK
47
static int slwait(int *sl);
48
static int slrelease(int *sl);
51
static long getpagesize(void);
52
static long getregionsize(void);
53
static void *sbrk(long size);
54
static void *mmap(void *ptr, long size, long prot, long type, long handle, long arg);
55
static long munmap(void *ptr, long size);
57
static void vminfo (unsigned long*free, unsigned long*reserved, unsigned long*committed);
58
static int cpuinfo (int whole, unsigned long*kernel, unsigned long*user);
66
Void_t* is the pointer type that malloc should say it returns
73
#include <stddef.h> /* for size_t */
79
/* define LACKS_UNISTD_H if your system does not have a <unistd.h>. */
81
/* #define LACKS_UNISTD_H */
83
#ifndef LACKS_UNISTD_H
87
/* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. */
89
/* #define LACKS_SYS_PARAM_H */
92
#include <stdio.h> /* needed for malloc_stats */
93
#include <errno.h> /* needed for optional MALLOC_FAILURE_ACTION */
99
Because freed chunks may be overwritten with bookkeeping fields, this
100
malloc will often die when freed memory is overwritten by user
101
programs. This can be very effective (albeit in an annoying way)
102
in helping track down dangling pointers.
104
If you compile with -DDEBUG, a number of assertion checks are
105
enabled that will catch more memory errors. You probably won't be
106
able to make much sense of the actual assertion errors, but they
107
should help you locate incorrectly overwritten memory. The
108
checking is fairly extensive, and will slow down execution
109
noticeably. Calling malloc_stats or mallinfo with DEBUG set will
110
attempt to check every non-mmapped allocated and free chunk in the
111
course of computing the summmaries. (By nature, mmapped regions
112
cannot be checked very much automatically.)
114
Setting DEBUG may also be helpful if you are trying to modify
115
this code. The assertions in the check routines spell out in more
116
detail the assumptions and invariants underlying the algorithms.
118
Setting DEBUG does NOT provide an automated mechanism for checking
119
that all accesses to malloced memory stay within their
120
bounds. However, there are several add-ons and adaptations of this
121
or other mallocs available that do this.
126
/* #define assert(x) if(!(x)) abort() */
129
#define assert(x) ((void)0)
133
The unsigned integer type used for comparing any two chunk sizes.
134
This should be at least as wide as size_t, but should not be signed.
138
#define CHUNK_SIZE_T unsigned long
141
#define MAX_CHUNK_SIZE ((CHUNK_SIZE_T)(-1UL))
144
The unsigned integer type used to hold addresses when they are are
145
manipulated as integers. Except that it is not defined on all
146
systems, intptr_t would suffice.
149
#define PTR_UINT unsigned long
154
INTERNAL_SIZE_T is the word-size used for internal bookkeeping
157
The default version is the same as size_t.
159
While not strictly necessary, it is best to define this as an
160
unsigned type, even if size_t is a signed type. This may avoid some
161
artificial size limitations on some systems.
163
On a 64-bit machine, you may be able to reduce malloc overhead by
164
defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
165
expense of not being able to handle more than 2^32 of malloced
166
space. If this limitation is acceptable, you are encouraged to set
167
this unless you are on a platform requiring 16byte alignments. In
168
this case the alignment requirements turn out to negate any
169
potential advantages of decreasing size_t word size.
171
Implementors: Beware of the possible combinations of:
172
- INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
173
and might be the same width as int or as long
174
- size_t might have different width and signedness as INTERNAL_SIZE_T
175
- int and long might be 32 or 64 bits, and might be the same width
176
To deal with this, most comparisons and difference computations
177
among INTERNAL_SIZE_Ts should cast them to CHUNK_SIZE_T, being
178
aware of the fact that casting an unsigned int to a wider long does
179
not sign-extend. (This also makes checking for negative numbers
180
awkward.) Some of these casts result in harmless compiler warnings
184
#ifndef INTERNAL_SIZE_T
185
#define INTERNAL_SIZE_T size_t
188
/* The corresponding word size */
189
#define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
194
MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
195
It must be a power of two at least 2 * SIZE_SZ, even on machines
196
for which smaller alignments would suffice. It may be defined as
197
larger than this though. Note however that code and data structures
198
are optimized for the case of 8-byte alignment.
202
#ifndef MALLOC_ALIGNMENT
203
#define MALLOC_ALIGNMENT (2 * SIZE_SZ)
206
/* The corresponding bit mask value */
207
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
212
REALLOC_ZERO_BYTES_FREES should be set if a call to
213
realloc with zero bytes should be the same as a call to free.
214
Some people think it should. Otherwise, since this malloc
215
returns a unique pointer for malloc(0), so does realloc(p, 0).
218
/* #define REALLOC_ZERO_BYTES_FREES */
221
TRIM_FASTBINS controls whether free() of a very small chunk can
222
immediately lead to trimming. Setting to true (1) can reduce memory
223
footprint, but will almost always slow down programs that use a lot
226
Define this only if you are willing to give up some speed to more
227
aggressively reduce system-level memory footprint when releasing
228
memory in programs that use many small chunks. You can get
229
essentially the same effect by setting MXFAST to 0, but this can
230
lead to even greater slowdowns in programs using many small chunks.
231
TRIM_FASTBINS is an in-between compile-time option, that disables
232
only those chunks bordering topmost memory from being placed in
236
#ifndef TRIM_FASTBINS
237
#define TRIM_FASTBINS 0
242
USE_DL_PREFIX will prefix all public routines with the string 'dl'.
243
This is necessary when you only want to use this malloc in one part
244
of a program, using your regular system malloc elsewhere.
247
/* #define USE_DL_PREFIX */
251
USE_MALLOC_LOCK causes wrapper functions to surround each
252
callable routine with pthread mutex lock/unlock.
254
USE_MALLOC_LOCK forces USE_PUBLIC_MALLOC_WRAPPERS to be defined
257
/* #define USE_MALLOC_LOCK */
261
If USE_PUBLIC_MALLOC_WRAPPERS is defined, every public routine is
262
actually a wrapper function that first calls MALLOC_PREACTION, then
263
calls the internal routine, and follows it with
264
MALLOC_POSTACTION. This is needed for locking, but you can also use
265
this, without USE_MALLOC_LOCK, for purposes of interception,
266
instrumentation, etc. It is a sad fact that using wrappers often
267
noticeably degrades performance of malloc-intensive programs.
270
#ifdef USE_MALLOC_LOCK
271
#define USE_PUBLIC_MALLOC_WRAPPERS
273
/* #define USE_PUBLIC_MALLOC_WRAPPERS */
278
Two-phase name translation.
279
All of the actual routines are given mangled names.
280
When wrappers are used, they become the public callable versions.
281
When DL_PREFIX is used, the callable names are prefixed.
284
#ifndef USE_PUBLIC_MALLOC_WRAPPERS
285
#define cALLOc public_cALLOc
286
#define fREe public_fREe
287
#define cFREe public_cFREe
288
#define mALLOc public_mALLOc
289
#define mEMALIGn public_mEMALIGn
290
#define rEALLOc public_rEALLOc
291
#define vALLOc public_vALLOc
292
#define pVALLOc public_pVALLOc
293
#define mALLINFo public_mALLINFo
294
#define mALLOPt public_mALLOPt
295
#define mTRIm public_mTRIm
296
#define mSTATs public_mSTATs
297
#define mUSABLe public_mUSABLe
298
#define iCALLOc public_iCALLOc
299
#define iCOMALLOc public_iCOMALLOc
303
#define public_cALLOc dlcalloc
304
#define public_fREe dlfree
305
#define public_cFREe dlcfree
306
#define public_mALLOc dlmalloc
307
#define public_mEMALIGn dlmemalign
308
#define public_rEALLOc dlrealloc
309
#define public_vALLOc dlvalloc
310
#define public_pVALLOc dlpvalloc
311
#define public_mALLINFo dlmallinfo
312
#define public_mALLOPt dlmallopt
313
#define public_mTRIm dlmalloc_trim
314
#define public_mSTATs dlmalloc_stats
315
#define public_mUSABLe dlmalloc_usable_size
316
#define public_iCALLOc dlindependent_calloc
317
#define public_iCOMALLOc dlindependent_comalloc
318
#else /* USE_DL_PREFIX */
319
#define public_cALLOc calloc
320
#define public_fREe free
321
#define public_cFREe cfree
322
#define public_mALLOc malloc
323
#define public_mEMALIGn memalign
324
#define public_rEALLOc realloc
325
#define public_vALLOc valloc
326
#define public_pVALLOc pvalloc
327
#define public_mALLINFo mallinfo
328
#define public_mALLOPt mallopt
329
#define public_mTRIm malloc_trim
330
#define public_mSTATs malloc_stats
331
#define public_mUSABLe malloc_usable_size
332
#define public_iCALLOc independent_calloc
333
#define public_iCOMALLOc independent_comalloc
334
#endif /* USE_DL_PREFIX */
338
HAVE_MEMCPY should be defined if you are not otherwise using
339
ANSI STD C, but still have memcpy and memset in your C library
340
and want to use them in calloc and realloc. Otherwise simple
341
macro versions are defined below.
343
USE_MEMCPY should be defined as 1 if you actually want to
344
have memset and memcpy called. People report that the macro
345
versions are faster than libc versions on some systems.
347
Even if USE_MEMCPY is set to 1, loops to copy/clear small chunks
348
(of <= 36 bytes) are manually unrolled in realloc and calloc.
362
#if (defined(HAVE_MEMCPY))
364
/* On Win32 memset and memcpy are already declared in windows.h */
366
void* memset(void*, int, size_t);
367
void* memcpy(void*, const void*, size_t);
372
MALLOC_FAILURE_ACTION is the action to take before "return 0" when
373
malloc fails to be able to return memory, either because memory is
374
exhausted or because of illegal arguments.
376
By default, sets errno if running on STD_C platform, else does nothing.
379
#ifndef MALLOC_FAILURE_ACTION
380
#define MALLOC_FAILURE_ACTION \
385
MORECORE-related declarations. By default, rely on sbrk
389
#ifdef LACKS_UNISTD_H
390
#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
391
extern Void_t* sbrk(ptrdiff_t);
396
MORECORE is the name of the routine to call to obtain more memory
397
from the system. See below for general guidance on writing
398
alternative MORECORE functions, as well as a version for WIN32 and a
399
sample version for pre-OSX macos.
403
#define MORECORE sbrk
407
MORECORE_FAILURE is the value returned upon failure of MORECORE
408
as well as mmap. Since it cannot be an otherwise valid memory address,
409
and must reflect values of standard sys calls, you probably ought not
413
#ifndef MORECORE_FAILURE
414
#define MORECORE_FAILURE (-1)
418
If MORECORE_CONTIGUOUS is true, take advantage of fact that
419
consecutive calls to MORECORE with positive arguments always return
420
contiguous increasing addresses. This is true of unix sbrk. Even
421
if not defined, when regions happen to be contiguous, malloc will
422
permit allocations spanning regions obtained from different
423
calls. But defining this when applicable enables some stronger
424
consistency checks and space efficiencies.
427
#ifndef MORECORE_CONTIGUOUS
428
#define MORECORE_CONTIGUOUS 1
432
Define MORECORE_CANNOT_TRIM if your version of MORECORE
433
cannot release space back to the system when given negative
434
arguments. This is generally necessary only if you are using
435
a hand-crafted MORECORE function that cannot handle negative arguments.
438
/* #define MORECORE_CANNOT_TRIM */
442
Define HAVE_MMAP as true to optionally make malloc() use mmap() to
443
allocate very large blocks. These will be returned to the
444
operating system immediately after a free(). Also, if mmap
445
is available, it is used as a backup strategy in cases where
446
MORECORE fails to provide space from system.
448
This malloc is best tuned to work with mmap for large requests.
449
If you do not have mmap, operations involving very large chunks (1MB
450
or so) may be slower than you'd like.
461
Standard unix mmap using /dev/zero clears memory so calloc doesn't
466
#define MMAP_CLEARS 1
471
#define MMAP_CLEARS 0
477
MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
478
sbrk fails, and mmap is used as a backup (which is done only if
479
HAVE_MMAP). The value must be a multiple of page size. This
480
backup strategy generally applies only when systems have "holes" in
481
address space, so sbrk cannot perform contiguous expansion, but
482
there is still space available on system. On systems for which
483
this is known to be useful (i.e. most linux kernels), this occurs
484
only when programs allocate huge amounts of memory. Between this,
485
and the fact that mmap regions tend to be limited, the size should
486
be large, to avoid too many mmap calls and thus avoid running out
490
#ifndef MMAP_AS_MORECORE_SIZE
491
#define MMAP_AS_MORECORE_SIZE (1024 * 1024)
495
Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
496
large blocks. This is currently only possible on Linux with
497
kernel versions newer than 1.3.77.
502
#define HAVE_MREMAP 1
504
#define HAVE_MREMAP 0
507
#endif /* HAVE_MMAP */
511
The system page size. To the extent possible, this malloc manages
512
memory from the system in page-size units. Note that this value is
513
cached during initialization into a field of malloc_state. So even
514
if malloc_getpagesize is a function, it is only called once.
516
The following mechanics for getpagesize were adapted from bsd/gnu
517
getpagesize.h. If none of the system-probes here apply, a value of
518
4096 is used, which should be OK: If they don't apply, then using
519
the actual value probably doesn't impact performance.
522
#ifndef malloc_getpagesize
524
#ifndef LACKS_UNISTD_H
528
# ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
529
# ifndef _SC_PAGE_SIZE
530
# define _SC_PAGE_SIZE _SC_PAGESIZE
534
# ifdef _SC_PAGE_SIZE
535
# define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
537
# if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
538
extern size_t getpagesize();
539
# define malloc_getpagesize getpagesize()
541
# ifdef WIN32 /* use supplied emulation of getpagesize */
542
# define malloc_getpagesize getpagesize()
544
# ifndef LACKS_SYS_PARAM_H
545
# include <sys/param.h>
547
# ifdef EXEC_PAGESIZE
548
# define malloc_getpagesize EXEC_PAGESIZE
552
# define malloc_getpagesize NBPG
554
# define malloc_getpagesize (NBPG * CLSIZE)
558
# define malloc_getpagesize NBPC
561
# define malloc_getpagesize PAGESIZE
562
# else /* just guess */
563
# define malloc_getpagesize (4096)
574
This version of malloc supports the standard SVID/XPG mallinfo
575
routine that returns a struct containing usage properties and
576
statistics. It should work on any SVID/XPG compliant system that has
577
a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
578
install such a thing yourself, cut out the preliminary declarations
579
as described above and below and save them in a malloc.h file. But
580
there's no compelling reason to bother to do this.)
582
The main declaration needed is the mallinfo struct that is returned
583
(by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a
584
bunch of fields that are not even meaningful in this version of
585
malloc. These fields are are instead filled by mallinfo() with
586
other numbers that might be of interest.
588
HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
589
/usr/include/malloc.h file that includes a declaration of struct
590
mallinfo. If so, it is included; else an SVID2/XPG2 compliant
591
version is declared below. These must be precisely the same for
592
mallinfo() to work. The original SVID version of this struct,
593
defined on most systems with mallinfo, declares all fields as
594
ints. But some others define as unsigned long. If your system
595
defines the fields using a type of different width than listed here,
596
you must #include your system version and #define
597
HAVE_USR_INCLUDE_MALLOC_H.
600
/* #define HAVE_USR_INCLUDE_MALLOC_H */
602
#ifdef HAVE_USR_INCLUDE_MALLOC_H
603
#include "/usr/include/malloc.h"
606
/* SVID2/XPG mallinfo structure */
609
int arena; /* non-mmapped space allocated from system */
610
int ordblks; /* number of free chunks */
611
int smblks; /* number of fastbin blocks */
612
int hblks; /* number of mmapped regions */
613
int hblkhd; /* space in mmapped regions */
614
int usmblks; /* maximum total allocated space */
615
int fsmblks; /* space available in freed fastbin blocks */
616
int uordblks; /* total allocated space */
617
int fordblks; /* total free space */
618
int keepcost; /* top-most, releasable (via malloc_trim) space */
622
SVID/XPG defines four standard parameter numbers for mallopt,
623
normally defined in malloc.h. Only one of these (M_MXFAST) is used
624
in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
625
so setting them has no effect. But this malloc also supports other
626
options in mallopt described below.
631
/* ---------- description of public routines ------------ */
635
Returns a pointer to a newly allocated chunk of at least n bytes, or null
636
if no space is available. Additionally, on failure, errno is
637
set to ENOMEM on ANSI C systems.
639
If n is zero, malloc returns a minumum-sized chunk. (The minimum
640
size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
641
systems.) On most systems, size_t is an unsigned type, so calls
642
with negative arguments are interpreted as requests for huge amounts
643
of space, which will often fail. The maximum supported value of n
644
differs across systems, but is in all cases less than the maximum
645
representable value of a size_t.
647
Void_t* public_mALLOc(size_t);
651
Releases the chunk of memory pointed to by p, that had been previously
652
allocated using malloc or a related routine such as realloc.
653
It has no effect if p is null. It can have arbitrary (i.e., bad!)
654
effects if p has already been freed.
656
Unless disabled (using mallopt), freeing very large spaces will
657
when possible, automatically trigger operations that give
658
back unused memory to the system, thus reducing program footprint.
660
void public_fREe(Void_t*);
663
calloc(size_t n_elements, size_t element_size);
664
Returns a pointer to n_elements * element_size bytes, with all locations
667
Void_t* public_cALLOc(size_t, size_t);
670
realloc(Void_t* p, size_t n)
671
Returns a pointer to a chunk of size n that contains the same data
672
as does chunk p up to the minimum of (n, p's size) bytes, or null
673
if no space is available.
675
The returned pointer may or may not be the same as p. The algorithm
676
prefers extending p when possible, otherwise it employs the
677
equivalent of a malloc-copy-free sequence.
679
If p is null, realloc is equivalent to malloc.
681
If space is not available, realloc returns null, errno is set (if on
682
ANSI) and p is NOT freed.
684
if n is for fewer bytes than already held by p, the newly unused
685
space is lopped off and freed if possible. Unless the #define
686
REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
687
zero (re)allocates a minimum-sized chunk.
689
Large chunks that were internally obtained via mmap will always
690
be reallocated using malloc-copy-free sequences unless
691
the system supports MREMAP (currently only linux).
693
The old unix realloc convention of allowing the last-free'd chunk
694
to be used as an argument to realloc is not supported.
697
Void_t* public_rEALLOc(Void_t*, size_t);
700
memalign(size_t alignment, size_t n);
701
Returns a pointer to a newly allocated chunk of n bytes, aligned
702
in accord with the alignment argument.
704
The alignment argument should be a power of two. If the argument is
705
not a power of two, the nearest greater power is used.
706
8-byte alignment is guaranteed by normal malloc calls, so don't
707
bother calling memalign with an argument of 8 or less.
709
Overreliance on memalign is a sure way to fragment space.
711
Void_t* public_mEMALIGn(size_t, size_t);
715
Equivalent to memalign(pagesize, n), where pagesize is the page
716
size of the system. If the pagesize is unknown, 4096 is used.
718
Void_t* public_vALLOc(size_t);
722
mallopt(int parameter_number, int parameter_value)
723
Sets tunable parameters The format is to provide a
724
(parameter-number, parameter-value) pair. mallopt then sets the
725
corresponding parameter to the argument value if it can (i.e., so
726
long as the value is meaningful), and returns 1 if successful else
727
0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
728
normally defined in malloc.h. Only one of these (M_MXFAST) is used
729
in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
730
so setting them has no effect. But this malloc also supports four
731
other options in mallopt. See below for details. Briefly, supported
732
parameters are as follows (listed defaults are for "typical"
735
Symbol param # default allowed param values
736
M_MXFAST 1 64 0-64 (0 disables fastbins)
737
M_TRIM_THRESHOLD -1 256*1024 any (-1U disables trimming)
739
M_MMAP_THRESHOLD -3 256*1024 any (or 0 if no MMAP support)
740
M_MMAP_MAX -4 65536 any (0 disables use of mmap)
742
int public_mALLOPt(int, int);
747
Returns (by copy) a struct containing various summary statistics:
749
arena: current total non-mmapped bytes allocated from system
750
ordblks: the number of free chunks
751
smblks: the number of fastbin blocks (i.e., small chunks that
752
have been freed but not use resused or consolidated)
753
hblks: current number of mmapped regions
754
hblkhd: total bytes held in mmapped regions
755
usmblks: the maximum total allocated space. This will be greater
756
than current total if trimming has occurred.
757
fsmblks: total bytes held in fastbin blocks
758
uordblks: current total allocated space (normal or mmapped)
759
fordblks: total free space
760
keepcost: the maximum number of bytes that could ideally be released
761
back to system via malloc_trim. ("ideally" means that
762
it ignores page restrictions etc.)
764
Because these fields are ints, but internal bookkeeping may
765
be kept as longs, the reported values may wrap around zero and
768
struct mallinfo public_mALLINFo(void);
771
independent_calloc(size_t n_elements, size_t element_size, Void_t* chunks[]);
773
independent_calloc is similar to calloc, but instead of returning a
774
single cleared space, it returns an array of pointers to n_elements
775
independent elements that can hold contents of size elem_size, each
776
of which starts out cleared, and can be independently freed,
777
realloc'ed etc. The elements are guaranteed to be adjacently
778
allocated (this is not guaranteed to occur with multiple callocs or
779
mallocs), which may also improve cache locality in some
782
The "chunks" argument is optional (i.e., may be null, which is
783
probably the most typical usage). If it is null, the returned array
784
is itself dynamically allocated and should also be freed when it is
785
no longer needed. Otherwise, the chunks array must be of at least
786
n_elements in length. It is filled in with the pointers to the
789
In either case, independent_calloc returns this pointer array, or
790
null if the allocation failed. If n_elements is zero and "chunks"
791
is null, it returns a chunk representing an array with zero elements
792
(which should be freed if not wanted).
794
Each element must be individually freed when it is no longer
795
needed. If you'd like to instead be able to free all at once, you
796
should instead use regular calloc and assign pointers into this
797
space to represent elements. (In this case though, you cannot
798
independently free elements.)
800
independent_calloc simplifies and speeds up implementations of many
801
kinds of pools. It may also be useful when constructing large data
802
structures that initially have a fixed number of fixed-sized nodes,
803
but the number is not known at compile time, and some of the nodes
804
may later need to be freed. For example:
806
struct Node { int item; struct Node* next; };
808
struct Node* build_list() {
810
int n = read_number_of_nodes_needed();
811
if (n <= 0) return 0;
812
pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
813
if (pool == 0) die();
814
// organize into a linked list...
815
struct Node* first = pool[0];
816
for (i = 0; i < n-1; ++i)
817
pool[i]->next = pool[i+1];
818
free(pool); // Can now free the array (or not, if it is needed later)
822
Void_t** public_iCALLOc(size_t, size_t, Void_t**);
825
independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
827
independent_comalloc allocates, all at once, a set of n_elements
828
chunks with sizes indicated in the "sizes" array. It returns
829
an array of pointers to these elements, each of which can be
830
independently freed, realloc'ed etc. The elements are guaranteed to
831
be adjacently allocated (this is not guaranteed to occur with
832
multiple callocs or mallocs), which may also improve cache locality
833
in some applications.
835
The "chunks" argument is optional (i.e., may be null). If it is null
836
the returned array is itself dynamically allocated and should also
837
be freed when it is no longer needed. Otherwise, the chunks array
838
must be of at least n_elements in length. It is filled in with the
839
pointers to the chunks.
841
In either case, independent_comalloc returns this pointer array, or
842
null if the allocation failed. If n_elements is zero and chunks is
843
null, it returns a chunk representing an array with zero elements
844
(which should be freed if not wanted).
846
Each element must be individually freed when it is no longer
847
needed. If you'd like to instead be able to free all at once, you
848
should instead use a single regular malloc, and assign pointers at
849
particular offsets in the aggregate space. (In this case though, you
850
cannot independently free elements.)
852
independent_comallac differs from independent_calloc in that each
853
element may have a different size, and also that it does not
854
automatically clear elements.
856
independent_comalloc can be used to speed up allocation in cases
857
where several structs or objects must always be allocated at the
858
same time. For example:
863
void send_message(char* msg) {
864
int msglen = strlen(msg);
865
size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
867
if (independent_comalloc(3, sizes, chunks) == 0)
869
struct Head* head = (struct Head*)(chunks[0]);
870
char* body = (char*)(chunks[1]);
871
struct Foot* foot = (struct Foot*)(chunks[2]);
875
In general though, independent_comalloc is worth using only for
876
larger values of n_elements. For small values, you probably won't
877
detect enough difference from series of malloc calls to bother.
879
Overuse of independent_comalloc can increase overall memory usage,
880
since it cannot reuse existing noncontiguous small chunks that
881
might be available for some of the elements.
883
Void_t** public_iCOMALLOc(size_t, size_t*, Void_t**);
888
Equivalent to valloc(minimum-page-that-holds(n)), that is,
889
round up n to nearest pagesize.
891
Void_t* public_pVALLOc(size_t);
895
Equivalent to free(p).
897
cfree is needed/defined on some systems that pair it with calloc,
898
for odd historical reasons (such as: cfree is used in example
899
code in the first edition of K&R).
901
void public_cFREe(Void_t*);
904
malloc_trim(size_t pad);
906
If possible, gives memory back to the system (via negative
907
arguments to sbrk) if there is unused memory at the `high' end of
908
the malloc pool. You can call this after freeing large blocks of
909
memory to potentially reduce the system-level memory requirements
910
of a program. However, it cannot guarantee to reduce memory. Under
911
some allocation patterns, some large free blocks of memory will be
912
locked between two used chunks, so they cannot be given back to
915
The `pad' argument to malloc_trim represents the amount of free
916
trailing space to leave untrimmed. If this argument is zero,
917
only the minimum amount of memory to maintain internal data
918
structures will be left (one page or less). Non-zero arguments
919
can be supplied to maintain enough trailing space to service
920
future expected allocations without having to re-obtain memory
923
Malloc_trim returns 1 if it actually released any memory, else 0.
924
On systems that do not support "negative sbrks", it will always
927
int public_mTRIm(size_t);
930
malloc_usable_size(Void_t* p);
932
Returns the number of bytes you can actually use in
933
an allocated chunk, which may be more than you requested (although
934
often not) due to alignment and minimum size constraints.
935
You can use this many bytes without worrying about
936
overwriting other allocated objects. This is not a particularly great
937
programming practice. malloc_usable_size can be more useful in
938
debugging and assertions, for example:
941
assert(malloc_usable_size(p) >= 256);
944
size_t public_mUSABLe(Void_t*);
948
Prints on stderr the amount of space obtained from the system (both
949
via sbrk and mmap), the maximum amount (which may be more than
950
current if malloc_trim and/or munmap got called), and the current
951
number of bytes allocated via malloc (or realloc, etc) but not yet
952
freed. Note that this is the number of bytes allocated, not the
953
number requested. It will be larger than the number requested
954
because of alignment and bookkeeping overhead. Because it includes
955
alignment wastage as being in use, this figure may be greater than
956
zero even when no user-level chunks are allocated.
958
The reported current and maximum system memory can be inaccurate if
959
a program makes other calls to system memory allocation functions
960
(normally sbrk) outside of malloc.
962
malloc_stats prints only the most commonly interesting statistics.
963
More information can be obtained by calling mallinfo.
966
void public_mSTATs();
968
/* mallopt tuning options */
971
M_MXFAST is the maximum request size used for "fastbins", special bins
972
that hold returned chunks without consolidating their spaces. This
973
enables future requests for chunks of the same size to be handled
974
very quickly, but can increase fragmentation, and thus increase the
975
overall memory footprint of a program.
977
This malloc manages fastbins very conservatively yet still
978
efficiently, so fragmentation is rarely a problem for values less
979
than or equal to the default. The maximum supported value of MXFAST
980
is 64 (also the default). You wouldn't want it any higher than this
981
anyway. Fastbins are designed especially for use with many small
982
structs, objects or strings -- the default handles
983
structs/objects/arrays with sizes up to 16 4byte fields, or small
984
strings representing words, tokens, etc. Using fastbins for larger
985
objects normally worsens fragmentation without improving speed.
987
M_MXFAST is set in REQUEST size units. It is internally used in
988
chunksize units, which adds padding and alignment. You can reduce
989
M_MXFAST to 0 to disable all use of fastbins. This causes the malloc
990
algorithm to be a closer approximation of fifo-best-fit in all cases,
991
not just for larger requests, but will generally cause it to be
996
/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
1001
#ifndef DEFAULT_MXFAST
1002
#define DEFAULT_MXFAST 64
1007
M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
1008
to keep before releasing via malloc_trim in free().
1010
Automatic trimming is mainly useful in long-lived programs.
1011
Because trimming via sbrk can be slow on some systems, and can
1012
sometimes be wasteful (in cases where programs immediately
1013
afterward allocate more large chunks) the value should be high
1014
enough so that your overall system performance would improve by
1015
releasing this much memory.
1017
The trim threshold and the mmap control parameters (see below)
1018
can be traded off with one another. Trimming and mmapping are
1019
two different ways of releasing unused memory back to the
1020
system. Between these two, it is often possible to keep
1021
system-level demands of a long-lived program down to a bare
1022
minimum. For example, in one test suite of sessions measuring
1023
the XF86 X server on Linux, using a trim threshold of 128K and a
1024
mmap threshold of 192K led to near-minimal long term resource
1027
If you are using this malloc in a long-lived program, it should
1028
pay to experiment with these values. As a rough guide, you
1029
might set to a value close to the average size of a process
1030
(program) running on your system. Releasing this much memory
1031
would allow such a process to run in memory. Generally, it's
1032
worth it to tune for trimming rather tham memory mapping when a
1033
program undergoes phases where several large chunks are
1034
allocated and released in ways that can reuse each other's
1035
storage, perhaps mixed with phases where there are no such
1036
chunks at all. And in well-behaved long-lived programs,
1037
controlling release of large blocks via trimming versus mapping
1040
However, in most programs, these parameters serve mainly as
1041
protection against the system-level effects of carrying around
1042
massive amounts of unneeded memory. Since frequent calls to
1043
sbrk, mmap, and munmap otherwise degrade performance, the default
1044
parameters are set to relatively high values that serve only as
1047
The trim value must be greater than page size to have any useful
1048
effect. To disable trimming completely, you can set to
1051
Trim settings interact with fastbin (MXFAST) settings: Unless
1052
TRIM_FASTBINS is defined, automatic trimming never takes place upon
1053
freeing a chunk with size less than or equal to MXFAST. Trimming is
1054
instead delayed until subsequent freeing of larger chunks. However,
1055
you can still force an attempted trim by calling malloc_trim.
1057
Also, trimming is not generally possible in cases where
1058
the main arena is obtained via mmap.
1060
Note that the trick some people use of mallocing a huge space and
1061
then freeing it at program startup, in an attempt to reserve system
1062
memory, doesn't have the intended effect under automatic trimming,
1063
since that memory will immediately be returned to the system.
1066
#define M_TRIM_THRESHOLD -1
1068
#ifndef DEFAULT_TRIM_THRESHOLD
1070
#define DEFAULT_TRIM_THRESHOLD (-1U)
1071
/* #define DEFAULT_TRIM_THRESHOLD (256 * 1024) */
1075
M_TOP_PAD is the amount of extra `padding' space to allocate or
1076
retain whenever sbrk is called. It is used in two ways internally:
1078
* When sbrk is called to extend the top of the arena to satisfy
1079
a new malloc request, this much padding is added to the sbrk
1082
* When malloc_trim is called automatically from free(),
1083
it is used as the `pad' argument.
1085
In both cases, the actual amount of padding is rounded
1086
so that the end of the arena is always a system page boundary.
1088
The main reason for using padding is to avoid calling sbrk so
1089
often. Having even a small pad greatly reduces the likelihood
1090
that nearly every malloc request during program start-up (or
1091
after trimming) will invoke sbrk, which needlessly wastes
1094
Automatic rounding-up to page-size units is normally sufficient
1095
to avoid measurable overhead, so the default is 0. However, in
1096
systems where sbrk is relatively slow, it can pay to increase
1097
this value, at the expense of carrying around more memory than
1101
#define M_TOP_PAD -2
1103
#ifndef DEFAULT_TOP_PAD
1104
#define DEFAULT_TOP_PAD (0)
1108
M_MMAP_THRESHOLD is the request size threshold for using mmap()
1109
to service a request. Requests of at least this size that cannot
1110
be allocated using already-existing space will be serviced via mmap.
1111
(If enough normal freed space already exists it is used instead.)
1113
Using mmap segregates relatively large chunks of memory so that
1114
they can be individually obtained and released from the host
1115
system. A request serviced through mmap is never reused by any
1116
other request (at least not directly; the system may just so
1117
happen to remap successive requests to the same locations).
1119
Segregating space in this way has the benefits that:
1121
1. Mmapped space can ALWAYS be individually released back
1122
to the system, which helps keep the system level memory
1123
demands of a long-lived program low.
1124
2. Mapped memory can never become `locked' between
1125
other chunks, as can happen with normally allocated chunks, which
1126
means that even trimming via malloc_trim would not release them.
1127
3. On some systems with "holes" in address spaces, mmap can obtain
1128
memory that sbrk cannot.
1130
However, it has the disadvantages that:
1132
1. The space cannot be reclaimed, consolidated, and then
1133
used to service later requests, as happens with normal chunks.
1134
2. It can lead to more wastage because of mmap page alignment
1136
3. It causes malloc performance to be more dependent on host
1137
system memory management support routines which may vary in
1138
implementation quality and may impose arbitrary
1139
limitations. Generally, servicing a request via normal
1140
malloc steps is faster than going through a system's mmap.
1142
The advantages of mmap nearly always outweigh disadvantages for
1143
"large" chunks, but the value of "large" varies across systems. The
1144
default is an empirically derived value that works well in most
1148
#define M_MMAP_THRESHOLD -3
1150
#ifndef DEFAULT_MMAP_THRESHOLD
1151
#define DEFAULT_MMAP_THRESHOLD (-1U)
1152
/*#define DEFAULT_MMAP_THRESHOLD (128 * 1024) */
1156
M_MMAP_MAX is the maximum number of requests to simultaneously
1157
service using mmap. This parameter exists because
1158
. Some systems have a limited number of internal tables for
1159
use by mmap, and using more than a few of them may degrade
1162
The default is set to a value that serves only as a safeguard.
1163
Setting to 0 disables use of mmap for servicing large requests. If
1164
HAVE_MMAP is not set, the default value is 0, and attempts to set it
1165
to non-zero values in mallopt will fail.
1168
#define M_MMAP_MAX -4
1170
#ifndef DEFAULT_MMAP_MAX
1172
#define DEFAULT_MMAP_MAX (65536)
1174
#define DEFAULT_MMAP_MAX (0)
1179
}; /* end of extern "C" */
1183
========================================================================
1184
To make a fully customizable malloc.h header file, cut everything
1185
above this line, put into file malloc.h, edit to suit, and #include it
1186
on the next line, as well as in programs that use this malloc.
1187
========================================================================
1190
/* #include "malloc.h" */
1192
/* --------------------- public wrappers ---------------------- */
1194
#ifdef USE_PUBLIC_MALLOC_WRAPPERS
1196
/* Declare all routines as internal */
1197
static Void_t* mALLOc(size_t);
1198
static void fREe(Void_t*);
1199
static Void_t* rEALLOc(Void_t*, size_t);
1200
static Void_t* mEMALIGn(size_t, size_t);
1201
static Void_t* vALLOc(size_t);
1202
static Void_t* pVALLOc(size_t);
1203
static Void_t* cALLOc(size_t, size_t);
1204
static Void_t** iCALLOc(size_t, size_t, Void_t**);
1205
static Void_t** iCOMALLOc(size_t, size_t*, Void_t**);
1206
static void cFREe(Void_t*);
1207
static int mTRIm(size_t);
1208
static size_t mUSABLe(Void_t*);
1209
static void mSTATs();
1210
static int mALLOPt(int, int);
1211
static struct mallinfo mALLINFo(void);
1214
MALLOC_PREACTION and MALLOC_POSTACTION should be
1215
defined to return 0 on success, and nonzero on failure.
1216
The return value of MALLOC_POSTACTION is currently ignored
1217
in wrapper functions since there is no reasonable default
1218
action to take on failure.
1222
#ifdef USE_MALLOC_LOCK
1226
static int mALLOC_MUTEx;
1227
#define MALLOC_PREACTION slwait(&mALLOC_MUTEx)
1228
#define MALLOC_POSTACTION slrelease(&mALLOC_MUTEx)
1232
#include <pthread.h>
1234
static pthread_mutex_t mALLOC_MUTEx = PTHREAD_MUTEX_INITIALIZER;
1236
#define MALLOC_PREACTION pthread_mutex_lock(&mALLOC_MUTEx)
1237
#define MALLOC_POSTACTION pthread_mutex_unlock(&mALLOC_MUTEx)
1239
#endif /* USE_MALLOC_LOCK */
1243
/* Substitute anything you like for these */
1245
#define MALLOC_PREACTION (0)
1246
#define MALLOC_POSTACTION (0)
1250
Void_t* public_mALLOc(size_t bytes) {
1252
if (MALLOC_PREACTION != 0) {
1256
if (MALLOC_POSTACTION != 0) {
1261
void public_fREe(Void_t* m) {
1262
if (MALLOC_PREACTION != 0) {
1266
if (MALLOC_POSTACTION != 0) {
1270
Void_t* public_rEALLOc(Void_t* m, size_t bytes) {
1271
if (MALLOC_PREACTION != 0) {
1274
m = rEALLOc(m, bytes);
1275
if (MALLOC_POSTACTION != 0) {
1280
Void_t* public_mEMALIGn(size_t alignment, size_t bytes) {
1282
if (MALLOC_PREACTION != 0) {
1285
m = mEMALIGn(alignment, bytes);
1286
if (MALLOC_POSTACTION != 0) {
1291
Void_t* public_vALLOc(size_t bytes) {
1293
if (MALLOC_PREACTION != 0) {
1297
if (MALLOC_POSTACTION != 0) {
1302
Void_t* public_pVALLOc(size_t bytes) {
1304
if (MALLOC_PREACTION != 0) {
1308
if (MALLOC_POSTACTION != 0) {
1313
Void_t* public_cALLOc(size_t n, size_t elem_size) {
1315
if (MALLOC_PREACTION != 0) {
1318
m = cALLOc(n, elem_size);
1319
if (MALLOC_POSTACTION != 0) {
1325
Void_t** public_iCALLOc(size_t n, size_t elem_size, Void_t** chunks) {
1327
if (MALLOC_PREACTION != 0) {
1330
m = iCALLOc(n, elem_size, chunks);
1331
if (MALLOC_POSTACTION != 0) {
1336
Void_t** public_iCOMALLOc(size_t n, size_t sizes[], Void_t** chunks) {
1338
if (MALLOC_PREACTION != 0) {
1341
m = iCOMALLOc(n, sizes, chunks);
1342
if (MALLOC_POSTACTION != 0) {
1347
void public_cFREe(Void_t* m) {
1348
if (MALLOC_PREACTION != 0) {
1352
if (MALLOC_POSTACTION != 0) {
1356
int public_mTRIm(size_t s) {
1358
if (MALLOC_PREACTION != 0) {
1362
if (MALLOC_POSTACTION != 0) {
1367
size_t public_mUSABLe(Void_t* m) {
1369
if (MALLOC_PREACTION != 0) {
1372
result = mUSABLe(m);
1373
if (MALLOC_POSTACTION != 0) {
1378
void public_mSTATs() {
1379
if (MALLOC_PREACTION != 0) {
1383
if (MALLOC_POSTACTION != 0) {
1387
struct mallinfo public_mALLINFo() {
1389
if (MALLOC_PREACTION != 0) {
1390
struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
1394
if (MALLOC_POSTACTION != 0) {
1399
int public_mALLOPt(int p, int v) {
1401
if (MALLOC_PREACTION != 0) {
1404
result = mALLOPt(p, v);
1405
if (MALLOC_POSTACTION != 0) {
1414
/* ------------- Optional versions of memcopy ---------------- */
1420
Note: memcpy is ONLY invoked with non-overlapping regions,
1421
so the (usually slower) memmove is not needed.
1424
#define MALLOC_COPY(dest, src, nbytes) memcpy(dest, src, nbytes)
1425
#define MALLOC_ZERO(dest, nbytes) memset(dest, 0, nbytes)
1427
#else /* !USE_MEMCPY */
1429
/* Use Duff's device for good zeroing/copying performance. */
1431
#define MALLOC_ZERO(charp, nbytes) \
1433
INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \
1434
CHUNK_SIZE_T mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
1436
if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
1438
case 0: for(;;) { *mzp++ = 0; \
1439
case 7: *mzp++ = 0; \
1440
case 6: *mzp++ = 0; \
1441
case 5: *mzp++ = 0; \
1442
case 4: *mzp++ = 0; \
1443
case 3: *mzp++ = 0; \
1444
case 2: *mzp++ = 0; \
1445
case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \
1449
#define MALLOC_COPY(dest,src,nbytes) \
1451
INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \
1452
INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \
1453
CHUNK_SIZE_T mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
1455
if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
1457
case 0: for(;;) { *mcdst++ = *mcsrc++; \
1458
case 7: *mcdst++ = *mcsrc++; \
1459
case 6: *mcdst++ = *mcsrc++; \
1460
case 5: *mcdst++ = *mcsrc++; \
1461
case 4: *mcdst++ = *mcsrc++; \
1462
case 3: *mcdst++ = *mcsrc++; \
1463
case 2: *mcdst++ = *mcsrc++; \
1464
case 1: *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; } \
1470
/* ------------------ MMAP support ------------------ */
1476
#ifndef LACKS_SYS_MMAN_H
1477
#include <sys/mman.h>
1480
#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1481
#define MAP_ANONYMOUS MAP_ANON
1485
Nearly all versions of mmap support MAP_ANONYMOUS,
1486
so the following is unlikely to be needed, but is
1487
supplied just in case.
1490
#ifndef MAP_ANONYMOUS
1492
static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1494
#define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
1495
(dev_zero_fd = open("/dev/zero", O_RDWR), \
1496
mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
1497
mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))
1501
#define MMAP(addr, size, prot, flags) \
1502
(mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1507
#endif /* HAVE_MMAP */
1511
----------------------- Chunk representations -----------------------
1516
This struct declaration is misleading (but accurate and necessary).
1517
It declares a "view" into memory allowing access to necessary
1518
fields at known offsets from a given base. See explanation below.
1521
struct malloc_chunk {
1523
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
1524
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
1526
struct malloc_chunk* fd; /* double links -- used only if free. */
1527
struct malloc_chunk* bk;
1531
typedef struct malloc_chunk* mchunkptr;
1533
/* conversion from malloc headers to user pointers, and back */
1534
#define chunk2mem(p) ((Void_t*)((char*)(p) + 2*SIZE_SZ))
1535
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1538
malloc_chunk details:
1540
(The following includes lightly edited explanations by Colin Plumb.)
1542
Chunks of memory are maintained using a `boundary tag' method as
1543
described in e.g., Knuth or Standish. (See the paper by Paul
1544
Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1545
survey of such techniques.) Sizes of free chunks are stored both
1546
in the front of each chunk and at the end. This makes
1547
consolidating fragmented chunks into bigger chunks very fast. The
1548
size fields also hold bits representing whether chunks are free or
1551
An allocated chunk looks like this:
1554
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1555
| Size of previous chunk, if allocated | |
1556
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1557
| Size of chunk, in bytes |P|
1558
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1559
| User data starts here... .
1561
. (malloc_usable_space() bytes) .
1563
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1564
`foot:' | Size of chunk |
1565
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1568
Where "chunk" is the front of the chunk for the purpose of most of
1569
the malloc code, but "mem" is the pointer that is returned to the
1570
user. "Nextchunk" is the beginning of the next contiguous chunk.
1572
Chunks always begin on even word boundries, so the mem portion
1573
(which is returned to the user) is also on an even word boundary, and
1574
thus at least double-word aligned.
1577
The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1578
chunk size (which is always a multiple of two words), is an in-use
1579
bit for the *previous* chunk. If that bit is *clear*, then the
1580
word before the current chunk size contains the previous chunk
1581
size, and can be used to find the front of the previous chunk.
1582
The very first chunk allocated always has this bit set,
1583
preventing access to non-existent (or non-owned) memory. If
1584
prev_inuse is set for any given chunk, then you CANNOT determine
1585
the size of the previous chunk, and might even get a memory
1586
addressing fault when trying to do so.
1588
Note that the `foot' of the current chunk is actually represented
1589
as the prev_size of the NEXT chunk. This makes it easier to
1590
deal with alignments etc but can be very confusing when trying
1591
to extend or adapt this code.
1593
The two exceptions to all this are
1595
1. The special chunk `top' doesn't bother using the
1596
trailing size field since there is no next contiguous chunk
1597
that would have to index off it. After initialization, `top'
1598
is forced to always exist. If it would become less than
1599
MINSIZE bytes long, it is replenished.
1601
2. Chunks allocated via mmap, which have the second-lowest-order
1602
bit (IS_MMAPPED) set in their size fields. Because they are
1603
allocated one-by-one, each must contain its own trailing size field.
1610
--------------- Operations on size fields ---------------
1614
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1615
#define PREV_INUSE 0x1
1618
/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap */
1619
#define IS_MMAPPED 0x2
1621
#define IS_MMAPPED 0
1624
/* extract inuse bit of previous chunk */
1625
#define prev_inuse(p) ((p)->size & PREV_INUSE)
1627
/* check for mmap()'ed chunk */
1628
#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1631
Bits to mask off when extracting size
1633
Note: IS_MMAPPED is intentionally not masked off from size field in
1634
macros for which mmapped chunks should never be seen. This should
1635
cause helpful core dumps to occur if it is tried by accident by
1636
people extending or adapting this malloc.
1638
#define SIZE_BITS (PREV_INUSE|IS_MMAPPED)
1640
/* Get size, ignoring use bits */
1641
#define chunksize(p) ((CHUNK_SIZE_T)((p)->size & ~(SIZE_BITS)))
1644
/* Ptr to next physical malloc_chunk. */
1645
#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE)))
1647
/* Ptr to previous physical malloc_chunk */
1648
#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1650
/* Treat space at ptr + offset as a chunk */
1651
#define chunk_at_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
1653
/* extract p's inuse bit */
1655
((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE)
1657
/* set/clear chunk as being inuse without otherwise disturbing */
1658
#define set_inuse(p)\
1659
((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size |= PREV_INUSE
1661
#define clear_inuse(p)\
1662
((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size &= ~(PREV_INUSE)
1665
/* check/set/clear inuse bits in known places */
1666
#define inuse_bit_at_offset(p, s)\
1667
(((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
1669
#define inuse_addr_at_offset(p, s)\
1670
(INTERNAL_SIZE_T*)(&(((mchunkptr)(((char*)(p)) + (s)))->size))
1672
#define set_inuse_bit_at_offset(p, s)\
1673
(((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
1675
#define clear_inuse_bit_at_offset(p, s)\
1676
(((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
1679
/* Set size at head, without disturbing its use bit */
1680
#define set_head_size(p, s) ((p)->size = (((p)->size & PREV_INUSE) | (s)))
1682
/* Set size/use field */
1683
#define set_head(p, s) ((p)->size = (s))
1685
/* Set size at footer (only when chunk is not in use) */
1686
#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
1690
---------- Size and alignment checks and conversions ----------
1694
/* The smallest possible chunk */
1695
#define MIN_CHUNK_SIZE (sizeof(struct malloc_chunk))
1697
/* The smallest size we can malloc is an aligned minimal chunk */
1700
(CHUNK_SIZE_T)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1702
/* Check if m has acceptable alignment */
1704
#define aligned_OK(m) (((PTR_UINT)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1708
Check if a request is so large that it would wrap around zero when
1709
padded and aligned. To simplify some other code, the bound is made
1710
low enough so that adding MINSIZE will also not wrap around sero.
1713
#define MAX_REQUEST_SIZE ((CHUNK_SIZE_T)(INTERNAL_SIZE_T)(-2 * MINSIZE))
1715
#define request_out_of_range(req) \
1716
((CHUNK_SIZE_T)(req) >= MAX_REQUEST_SIZE)
1718
/* pad request bytes into a usable size -- internal version */
1720
#define request2size(req) \
1721
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
1723
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1726
#define pad_request(req) \
1727
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1729
/* Same, except also perform argument check */
1731
#define checked_request2size(req, sz) \
1732
if (request_out_of_range(req)) { \
1733
MALLOC_FAILURE_ACTION; \
1736
(sz) = request2size(req);
1739
typedef CHUNK_SIZE_T bin_index_t;
1740
typedef unsigned int bitmap_t;
1744
---------- Overlaid Data types ----------
1749
"Small" chunks are stored in circular doubly-linked lists, and look
1752
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1753
| Size of previous chunk |
1754
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1755
`head:' | Size of chunk, in bytes |P|
1756
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1757
| Forward pointer to next chunk in list |
1758
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1759
| Back pointer to previous chunk in list |
1760
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1761
| Unused space (may be 0 bytes long) .
1764
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1765
`foot:' | Size of chunk, in bytes |
1766
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1768
Larger chunks are kept in a form of bitwise digital trees (aka tries)
1769
keyed on chunksizes, in which
1771
* As seen as trees, they contains no duplicates (i.e., no
1772
duplicate sizes). If a chunk with the same size an an existing
1773
node is inserted, it is linked off the existing node using
1774
pointers that work in the same way as fd/bk pointers
1777
* The decision to go left or right when searching is based on a
1778
sliding bit, starting at the most significant bit distinguishing
1779
sizes in the tree, and sliding right each level. All left
1780
children of a node are smaller than all right children, but not
1781
necessarily smaller than the node.
1783
The worst case number of steps to add or remove a node is thus
1784
bounded by the number of bits differentiating chunks within
1785
bins. Under current bin calculations, this ranges from 6 up to 21
1786
(for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
1787
is of course much better.
1789
Tree chunks are overlaid in the same way as small chunks. Because
1790
malloc_tree_chunks are only for free chunks greater than 256 bytes, their
1791
zie doesn;t impose any constraints on user chunk sizes.
1793
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1794
| Size of previous chunk |
1795
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1796
`head:' | Size of chunk, in bytes |P|
1797
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1798
| Forward pointer to next chunk of same size |
1799
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1800
| Back pointer to previous chunk of same size |
1801
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1802
| Pointer to left child (child[0]) |
1803
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1804
| Pointer to right child (child[1]) |
1805
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1806
| Pointer to parent |
1807
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1808
| bin index of this chunk |
1809
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1812
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1813
`foot:' | Size of chunk, in bytes |
1814
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1819
struct malloc_tree_chunk {
1820
INTERNAL_SIZE_T prev_size; /* same as in malloc_chunk */
1821
INTERNAL_SIZE_T size;
1823
struct malloc_tree_chunk* fd; /* double links -- used only if free. */
1824
struct malloc_tree_chunk* bk;
1826
struct malloc_tree_chunk* child[2];
1827
struct malloc_tree_chunk* parent;
1832
typedef struct malloc_tree_chunk* tchunkptr;
1834
typedef struct malloc_tree_chunk* tbinptr;
1840
-------------------- Internal data structures --------------------
1842
All internal state is held in an instance of malloc_state defined
1843
below. There are no other static variables, except in two optional
1845
* If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1846
* If HAVE_MMAP is true, but mmap doesn't support
1847
MAP_ANONYMOUS, a dummy file descriptor for mmap.
1849
Beware of lots of tricks that minimize the total bookkeeping space
1850
requirements. The result is a little under 1K bytes (for 4byte
1851
pointers and size_t.)
1857
An array of bin headers for free chunks. Most bins hold sizes that are
1858
unusual as malloc request sizes, but are more usual for fragments
1859
and consolidated sets of chunks, which is what these bins hold, so
1860
they can be found quickly. All procedures maintain the invariant
1861
that no consolidated chunk physically borders another one, so each
1862
chunk in a list is known to be preceeded and followed by either
1863
inuse chunks or the ends of memory.
1865
To simplify use in double-linked lists, each bin header acts as a
1866
malloc_chunk pointing to the real first node, if it exists (else
1867
juct pointing to itself). This avoids special-casing for headers.
1868
But to conserve space and improve locality, we allocate only the
1869
fd/bk pointers of bins, and then use repositioning tricks to treat
1870
these as the fields of a malloc_chunk*.
1874
typedef struct malloc_chunk* mbinptr;
1877
#define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - (SIZE_SZ<<1)))
1879
/* analog of ++bin */
1880
#define next_bin(b) ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
1882
/* inverse of bin_at */
1883
#define bin2idx(m, b) \
1884
( ((int) (((char*)(b)) - (char*)(bin_at(m,0)))) / (2 * sizeof(mchunkptr)))
1889
Bins for sizes < MIN_TREEBIN_SIZE bytes contain chunks of all the
1890
same size, spaced 8 bytes apart. Larger bins are approximately
1891
logarithmically spaced.
1895
#define SMALLBIN_WIDTH 8
1896
#define MIN_TREEBIN_SIZE 256
1897
/* bit-shift corresponding to MIN_TREEBIN_SIZE */
1898
#define TREE_BIN_SHIFT 8
1900
#define in_smallbin_range(sz) \
1901
((CHUNK_SIZE_T)(sz) <= (CHUNK_SIZE_T)(MIN_TREEBIN_SIZE-1))
1904
#define MAX_SMALL_REQUEST (MIN_TREEBIN_SIZE-(SIZE_SZ+MALLOC_ALIGNMENT))
1906
#define smallbin_index(sz) (bin_index_t)((sz) >> 3)
1908
#define size_for_smallindex(i) ((CHUNK_SIZE_T)(i) << 3)
1910
#define MIN_SMALLBIN_INDEX (smallbin_index(MINSIZE))
1912
#define MIN_SMALLBIN_BIT (idx2bit(smallbin_index(MINSIZE)))
1916
There are 2 equally spaced treebins for each power of two from
1917
TREE_BIN_SHIFT to TREE_BIN_SHIFT+16. The last bin holds anything
1922
static bin_index_t treebin_index(CHUNK_SIZE_T sz) {
1924
unsigned int x = sz >> TREE_BIN_SHIFT;
1930
/* On intel, use BSRL instruction to find highest bit */
1931
#if defined(__GNUC__) && defined(i386)
1933
__asm__("bsrl %1,%0\n\t"
1936
return (m << 1) + ((sz >> (m + (TREE_BIN_SHIFT-1)) & 1));
1941
Based on branch-free nlz algorithm in chapter 5 of Henry
1942
S. Warren Jr's book "Hacker's Delight".
1945
unsigned int n = ((x - 0x100) >> 16) & 8;
1947
m = ((x - 0x1000) >> 16) & 4;
1950
m = ((x - 0x4000) >> 16) & 2;
1953
m = 13 - n + (x & ~(x>>1));
1954
/* shift up n and use the next bit to make finer-granularity bins. */
1955
return (m << 1) + ((sz >> (m + (TREE_BIN_SHIFT-1)) & 1));
1960
static bin_index_t bit2idx(bitmap_t x) {
1961
#if defined(__GNUC__) && defined(i386)
1963
__asm__("bsfl %1,%0\n\t"
1964
: "=r" (r) : "g" (x));
1965
return (bin_index_t)r;
1967
return (bin_index_t)(ffs(x)-1);
1973
#define bin_index(sz) \
1974
((in_smallbin_range(sz)) ? smallbin_index(sz) : treebin_index(sz))
1977
The most significant bit distinguishing nodes in the tree
1978
associated with a given bin
1981
#define CHUNK_SIZE_BITS (sizeof(CHUNK_SIZE_T) * 8)
1983
#define bitshift_for_index(idx) \
1985
CHUNK_SIZE_BITS-1 : \
1986
(((idx) >> 1) + TREE_BIN_SHIFT-2)
1988
#define tbin_at(m,i) (&((m)->treebins[i]))
1990
#define minsize_for_treeindex(i) \
1991
(((CHUNK_SIZE_T)(1) << (((i) >> 1) + TREE_BIN_SHIFT)) | \
1992
(((CHUNK_SIZE_T)((i) & 1)) << \
1993
( ( (i) >> 1) + TREE_BIN_SHIFT - 1)))
1997
#define is_tbin(M, P) ((tbinptr*)(P) >= &((M)->treebins[0]) && \
1998
(tbinptr*)(P) < &((M)->treebins[NBINS]))
2000
#define leftmost_child(t) \
2001
(((t)->child[0] != 0)? ((t)->child[0]) : ((t)->child[1]))
2007
An array of lists holding recently freed small chunks. Fastbins
2008
are not doubly linked. It is faster to single-link them, and
2009
since chunks are never removed from the middles of these lists,
2010
double linking is not necessary. Also, unlike regular bins, they
2011
are not even processed in FIFO order (they use faster LIFO) since
2012
ordering doesn't much matter in the transient contexts in which
2013
fastbins are normally used.
2015
Chunks in fastbins keep their inuse bit set, so they cannot
2016
be consolidated with other free chunks. malloc_consolidate
2017
releases all chunks in fastbins and consolidates them with
2021
typedef struct malloc_chunk* mfastbinptr;
2023
#define fastbin_at(m,i) (&((m)->fastbins[i]))
2025
/* offset 2 to use otherwise unindexable first 2 bins */
2026
#define fastbin_index(sz) ((((unsigned int)(sz)) >> 3) - 2)
2029
/* The maximum fastbin request size we support */
2030
#define MAX_FAST_REQUEST 64
2032
#define MAX_FAST_SIZE (request2size(MAX_FAST_REQUEST))
2034
#define NFASTBINS (fastbin_index(MAX_FAST_SIZE)+1)
2037
FASTCHUNKS_BIT held in max_fast indicates that there are probably
2038
some fastbin chunks. It is set true on entering a chunk into any
2039
fastbin, and cleared only in malloc_consolidate.
2042
#define FASTCHUNKS_BIT (2U)
2044
#define have_fastchunks(M) (((M)->max_fast & FASTCHUNKS_BIT))
2045
#define set_fastchunks(M) ((M)->max_fast |= (FASTCHUNKS_BIT))
2046
#define clear_fastchunks(M) ((M)->max_fast &= ~(FASTCHUNKS_BIT))
2049
Set value of max_fast.
2050
Use impossibly small value if 0.
2053
#define set_max_fast(M, s) \
2054
(M)->max_fast = (((s) == 0)? SMALLBIN_WIDTH: request2size(s)) | \
2055
((M)->max_fast & (FASTCHUNKS_BIT))
2057
#define get_max_fast(M) \
2058
((M)->max_fast & ~(FASTCHUNKS_BIT))
2064
The top-most available chunk (i.e., the one bordering the end of
2065
available memory) is treated specially. It is never included in
2066
any bin, is used only if no other chunk is available, and is
2067
released back to the system if it is very large (see
2070
Top initially points to a dummy bin with zero size, thus forcing
2071
extension on the first malloc request, so we avoid having any
2072
special code in malloc to check whether it even exists yet.
2079
To help compensate for the large number of bins, a one-level index
2080
structure is used for bin-by-bin searching. `binmap' is a
2081
bitvector recording whether bins are definitely empty so they can
2082
be skipped over during during traversals.
2085
/* Conservatively use 32 bits per map word, even if on 64bit system */
2087
#define idx2bit(i) ((bitmap_t)(1) << (i))
2089
#define mark_smallbin(m,i) ((m)->smallbits |= idx2bit(i))
2090
#define mark_treebin(m,i) ((m)->treebits |= idx2bit(i))
2092
#define clear_smallbin(m,i) ((m)->smallbits &= ~idx2bit(i))
2093
#define clear_treebin(m,i) ((m)->treebits &= ~idx2bit(i))
2096
/* isolate the least set bit of a bitmap */
2098
#define least_bit(x) ((x) & -(x))
2100
/* create mask with all bits to left of least bit of x on */
2102
#define left_bits(x) ((x<<1) | -(x<<1))
2104
/* create mask with all bits to left of or equal to least bit of x on */
2106
#define same_or_left_bits(x) ((x) | -(x))
2110
sysctl is a status word holding dynamically discovered
2111
or controlled properties of the morecore function
2114
#define MORECORE_CONTIGUOUS_BIT (1U)
2115
#define TRIM_DISABLE_BIT (2U)
2116
#define MMAP_DISABLE_BIT (4U)
2118
#define contiguous(M) \
2119
(((M)->sysctl & MORECORE_CONTIGUOUS_BIT))
2120
#define set_contiguous(M) \
2121
((M)->sysctl |= MORECORE_CONTIGUOUS_BIT)
2122
#define set_noncontiguous(M) \
2123
((M)->sysctl &= ~MORECORE_CONTIGUOUS_BIT)
2125
#define disable_trim(M) \
2126
((M)->sysctl |= TRIM_DISABLE_BIT)
2127
#define enable_trim(M) \
2128
((M)->sysctl &= ~TRIM_DISABLE_BIT)
2129
#define trim_disabled(M) \
2130
((M)->sysctl & TRIM_DISABLE_BIT)
2132
#define enable_mmap(M) \
2133
((M)->sysctl &= ~MMAP_DISABLE_BIT)
2134
#define disable_mmap(M) \
2135
((M)->sysctl |= MMAP_DISABLE_BIT)
2136
#define mmap_disabled(M) \
2137
((M)->sysctl & MMAP_DISABLE_BIT)
2143
----------- Internal state representation and initialization -----------
2146
struct malloc_state {
2147
/* The maximum chunk size to be eligible for fastbin */
2148
CHUNK_SIZE_T max_fast;
2150
/* Bitmap of bins */
2154
/* Base of the topmost chunk -- not otherwise kept in a bin */
2158
mfastbinptr fastbins[NFASTBINS];
2160
/* Smallbins packed as described above */
2161
mchunkptr bins[NBINS * 2];
2164
tbinptr treebins[NBINS];
2166
/* Padding to allow addressing past end of treebin array */
2167
struct malloc_tree_chunk initial_top;
2169
/* Tunable parameters */
2170
CHUNK_SIZE_T trim_threshold;
2171
INTERNAL_SIZE_T top_pad;
2172
INTERNAL_SIZE_T mmap_threshold;
2174
/* Memory map support */
2179
/* Cache malloc_getpagesize */
2180
unsigned int pagesize;
2182
/* Track properties of MORECORE */
2183
unsigned int sysctl;
2186
INTERNAL_SIZE_T mmapped_mem;
2187
INTERNAL_SIZE_T sbrked_mem;
2188
INTERNAL_SIZE_T max_sbrked_mem;
2189
INTERNAL_SIZE_T max_mmapped_mem;
2190
INTERNAL_SIZE_T max_total_mem;
2193
typedef struct malloc_state *mstate;
2196
There is exactly one instance of this struct in this malloc.
2197
If you are adapting this malloc in a way that does NOT use a static
2198
malloc_state, you MUST explicitly zero-fill it before using. This
2199
malloc relies on the property that malloc_state is initialized to
2200
all zeroes (as is true of C statics).
2203
static struct malloc_state av_; /* never directly referenced */
2206
All uses of av_ are via get_malloc_state().
2207
At most one "call" to get_malloc_state is made per invocation of
2208
the public versions of malloc and free, but other routines
2209
that in turn invoke malloc and/or free may call more then once.
2210
Also, it is called in check* routines if DEBUG is set.
2213
#define get_malloc_state() (&(av_))
2216
Initialize a malloc_state struct. This is called only
2217
in sysmalloc, to avoid it being inlined everywhere else,
2218
which causes useless code bloat.
2221
static void malloc_init_state(mstate av) {
2225
/* Establish circular links for bins */
2226
for (i = 0; i < NBINS; ++i) {
2228
bin->fd = bin->bk = bin;
2231
av->top_pad = DEFAULT_TOP_PAD;
2232
av->n_mmaps_max = DEFAULT_MMAP_MAX;
2233
av->mmap_threshold = DEFAULT_MMAP_THRESHOLD;
2234
av->trim_threshold = DEFAULT_TRIM_THRESHOLD;
2236
#if MORECORE_CONTIGUOUS
2239
set_noncontiguous(av);
2242
set_max_fast(av, DEFAULT_MXFAST);
2244
av->top = (mchunkptr)(&(av->initial_top));
2245
av->pagesize = malloc_getpagesize;
2248
#define ensure_initialization(M) \
2249
if ((M)->top == 0) sysmalloc(M, 0);
2253
Other internal utilities
2256
static Void_t* sysmalloc(mstate, CHUNK_SIZE_T);
2257
static int systrim(mstate, size_t);
2258
static Void_t** iALLOc(size_t, size_t*, int, Void_t**);
2259
static void insert_treenode(mstate, tchunkptr, CHUNK_SIZE_T);
2261
static void unlink_treenode(mstate, tchunkptr);
2262
static void unlink_small_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T size);
2264
static void transfer_tree_links(tchunkptr oldt, tchunkptr newt);
2265
static tchunkptr find_replacement(tchunkptr t);
2266
static void unlink_chained_node(tchunkptr t);
2267
static void insert_small_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T nb);
2268
static void insert_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T nb);
2269
static mchunkptr take_from_smallbin(mstate av, mchunkptr bin, bitmap_t bit);
2270
static void unlink_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T size);
2271
static Void_t* malloc_consolidate(mstate, CHUNK_SIZE_T, CHUNK_SIZE_T);
2274
#pragma no_inline(systrim)
2278
static mchunkptr mmap_malloc(mstate, INTERNAL_SIZE_T);
2284
These routines make a number of assertions about the states
2285
of data structures that should be true at all times. If any
2286
are not true, it's very likely that a user program has somehow
2287
trashed memory. (It's also possible that there is a coding error
2288
in malloc. In which case, please report it!)
2294
#define check_chunk(P)
2295
#define check_free_chunk(P)
2296
#define check_inuse_chunk(P)
2297
#define check_remalloced_chunk(P,N)
2298
#define check_malloced_chunk(P,N)
2299
#define check_malloc_state(M)
2300
#define check_tree(P)
2303
#define check_chunk(P) do_check_chunk(P)
2304
#define check_free_chunk(P) do_check_free_chunk(P)
2305
#define check_inuse_chunk(P) do_check_inuse_chunk(P)
2306
#define check_remalloced_chunk(P,N) do_check_remalloced_chunk(P,N)
2307
#define check_malloced_chunk(P,N) do_check_malloced_chunk(P,N)
2308
#define check_tree(P) do_check_tree(P)
2309
#define check_malloc_state(M) do_check_malloc_state(M)
2311
static void do_check_malloc_state(mstate);
2314
Find x in a treebin. Used in other check functions.
2317
static tchunkptr tree_find(tchunkptr x) {
2318
mstate av = get_malloc_state();
2319
CHUNK_SIZE_T nb = chunksize(x);
2320
bin_index_t idx = treebin_index(nb);
2321
tbinptr* bin = tbin_at(av, idx);
2323
bin_index_t shift = bitshift_for_index(idx);
2324
CHUNK_SIZE_T allbits = 0;
2333
size = chunksize(t);
2334
assert((size & allbits) == allbits);
2336
tchunkptr p = t->bk;
2346
if (((nb >> shift) & 1) == 0) {
2351
allbits |= 1U << shift;
2360
Properties of all chunks
2363
static void do_check_chunk(mchunkptr p) {
2364
mstate av = get_malloc_state();
2365
CHUNK_SIZE_T sz = chunksize(p);
2366
/* min and max possible addresses assuming contiguous allocation */
2367
char* max_address = (char*)(av->top) + chunksize(av->top);
2368
char* min_address = max_address - av->sbrked_mem;
2370
if (!chunk_is_mmapped(p)) {
2372
/* Has legal address ... */
2374
if (contiguous(av)) {
2375
assert(((char*)p) >= min_address);
2376
assert(((char*)p + sz) <= ((char*)(av->top)));
2380
/* top size is always at least MINSIZE */
2381
assert((CHUNK_SIZE_T)(sz) >= MINSIZE);
2382
/* top predecessor always marked inuse */
2383
assert(prev_inuse(p));
2389
/* address is outside main heap */
2390
if (contiguous(av) && av->top != (mchunkptr)(&(av->initial_top))) {
2391
assert(((char*)p) < min_address || ((char*)p) > max_address);
2393
/* chunk is page-aligned */
2394
assert(((p->prev_size + sz) & (av->pagesize-1)) == 0);
2395
/* mem is aligned */
2396
assert(aligned_OK(chunk2mem(p)));
2398
/* force an appropriate assert violation if debug set */
2399
assert(!chunk_is_mmapped(p));
2404
static void check_all_less(tchunkptr t, CHUNK_SIZE_T nb) {
2407
assert(chunksize(t) < nb);
2408
check_all_less(t->child[0], nb);
2409
check_all_less(t->child[1], nb);
2412
static void check_all_greater(tchunkptr t, CHUNK_SIZE_T nb) {
2415
assert(chunksize(t) >= nb);
2416
check_all_greater(t->child[0], nb);
2417
check_all_greater(t->child[1], nb);
2421
static INTERNAL_SIZE_T check_tree_fields(tchunkptr t) {
2422
INTERNAL_SIZE_T size = chunksize(t);
2423
assert(size >= MIN_TREEBIN_SIZE);
2424
do_check_chunk(((mchunkptr)t));
2426
assert(t->fd->bk == t);
2427
assert(t->bk->fd == t);
2428
assert(t->parent != t);
2429
assert(t->child[0] != t);
2430
assert(t->child[1] != t);
2431
if (t->child[0] != 0 && t->child[1] != 0) {
2432
check_all_less(t->child[0], chunksize(t->child[1]));
2433
check_all_greater(t->child[1], chunksize(t->child[0]));
2438
static INTERNAL_SIZE_T do_check_tree(tchunkptr t) {
2441
INTERNAL_SIZE_T total = check_tree_fields(t);
2443
/* If t is on a same-sized list, another node on list must have a parent */
2444
if (t->parent == 0) {
2446
while (h != t && h->parent == 0)
2453
assert (h->parent->child[0] == h ||
2454
h->parent->child[1] == h ||
2455
*((tbinptr*)(h->parent)) == h);
2458
/* only one node on a same-sized list has parent or children */
2461
assert(p->child[0] == 0);
2462
assert(p->child[1] == 0);
2463
assert(p->parent == 0);
2464
assert(chunksize(p) == chunksize(h));
2465
total += check_tree_fields(p);
2469
if (h->child[0] != 0) {
2470
assert(h->child[0]->parent == h);
2471
total += do_check_tree(h->child[0]);
2474
if (h->child[1] != 0) {
2475
assert(h->child[1]->parent == h);
2476
total += do_check_tree(h->child[1]);
2482
static void do_check_links(mchunkptr p) {
2483
if (in_smallbin_range(chunksize(p))) {
2484
assert(p->fd->bk == p);
2485
assert(p->bk->fd == p);
2488
do_check_tree((tchunkptr)p);
2493
Properties of free chunks
2496
static void do_check_free_chunk(mchunkptr p) {
2497
mstate av = get_malloc_state();
2499
INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2500
mchunkptr next = chunk_at_offset(p, sz);
2504
/* Chunk must claim to be free ... */
2506
assert (!chunk_is_mmapped(p));
2508
/* Unless a special marker, must have OK fields */
2509
if ((CHUNK_SIZE_T)(sz) >= MINSIZE)
2511
assert((sz & MALLOC_ALIGN_MASK) == 0);
2512
assert(aligned_OK(chunk2mem(p)));
2513
/* ... matching footer field */
2514
assert(next->prev_size == sz);
2515
/* ... and is fully consolidated */
2516
assert(prev_inuse(p));
2517
assert (next == av->top || inuse(next));
2521
else /* markers are always of size SIZE_SZ */
2522
assert(sz == SIZE_SZ);
2526
Properties of inuse chunks
2529
static void do_check_inuse_chunk(mchunkptr p) {
2530
mstate av = get_malloc_state();
2534
if (chunk_is_mmapped(p))
2535
return; /* mmapped chunks have no next/prev */
2537
/* Check whether it claims to be in use ... */
2540
next = next_chunk(p);
2542
/* ... and is surrounded by OK chunks.
2543
Since more things can be checked with free chunks than inuse ones,
2544
if an inuse chunk borders them and debug is on, it's worth doing them.
2546
if (!prev_inuse(p)) {
2547
/* Note that we cannot even look at prev unless it is not inuse */
2548
mchunkptr prv = prev_chunk(p);
2549
assert(next_chunk(prv) == p);
2550
do_check_free_chunk(prv);
2553
if (next == av->top) {
2554
assert(prev_inuse(next));
2555
assert(chunksize(next) >= MINSIZE);
2557
else if (!inuse(next))
2558
do_check_free_chunk(next);
2562
static void do_check_remalloced_chunk(mchunkptr p, INTERNAL_SIZE_T s) {
2563
INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2565
do_check_inuse_chunk(p);
2567
/* Legal size ... */
2568
assert((sz & MALLOC_ALIGN_MASK) == 0);
2569
assert((CHUNK_SIZE_T)(sz) >= MINSIZE);
2570
/* ... and alignment */
2571
assert(aligned_OK(chunk2mem(p)));
2572
/* chunk is less than MINSIZE more than request */
2573
assert((long)(sz) - (long)(s) >= 0);
2574
assert((long)(sz) - (long)(s + MINSIZE) < 0);
2578
Properties of nonrecycled chunks at the point they are malloced
2581
static void do_check_malloced_chunk(mchunkptr p, INTERNAL_SIZE_T s) {
2582
/* same as recycled case ... */
2583
do_check_remalloced_chunk(p, s);
2585
do_check_malloc_state(get_malloc_state());
2589
... plus, must obey implementation invariant that prev_inuse is
2590
always true of any allocated chunk; i.e., that each allocated
2591
chunk borders either a previously allocated and still in-use
2592
chunk, or the base of its memory arena. This is ensured
2593
by making all allocations from the the `lowest' part of any found
2597
assert(prev_inuse(p));
2601
static CHUNK_SIZE_T do_check_smallbin(mstate av, int i, mbinptr b) {
2602
mchunkptr p = b->bk;
2605
INTERNAL_SIZE_T size;
2606
CHUNK_SIZE_T total = 0;
2607
unsigned int empty = (av->smallbits & (1 << i)) == 0;
2619
for (; p != b; p = p->bk) {
2620
/* each chunk claims to be free */
2621
do_check_free_chunk(p);
2622
size = chunksize(p);
2625
/* chunk belongs in bin */
2626
idx = smallbin_index(size);
2628
assert(p->bk == b ||
2629
(CHUNK_SIZE_T)chunksize(p->bk) ==
2630
(CHUNK_SIZE_T)chunksize(p));
2632
/* chunk is followed by a legal chain of inuse chunks */
2633
for (q = next_chunk(p);
2634
(q != av->top && inuse(q) &&
2635
(CHUNK_SIZE_T)(chunksize(q)) >= MINSIZE);
2637
do_check_inuse_chunk(q);
2644
Properties of malloc_state.
2646
This may be useful for debugging malloc, as well as detecting user
2647
programmer errors that somehow write into malloc_state.
2649
If you are extending or experimenting with this malloc, you can
2650
probably figure out how to hack this routine to print out or
2651
display chunk addresses, sizes, bins, and other instrumentation.
2654
static void do_check_malloc_state(mstate av) {
2657
CHUNK_SIZE_T total = 0;
2664
/* internal size_t must be no wider than pointer type */
2665
assert(sizeof(INTERNAL_SIZE_T) <= sizeof(char*));
2667
/* alignment is a power of 2 */
2668
assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0);
2670
/* cannot run remaining checks until fully initialized */
2671
if (av->top == 0 || av->top == (mchunkptr)(&(av->initial_top)))
2674
/* pagesize is a power of 2 */
2675
assert((av->pagesize & (av->pagesize-1)) == 0);
2677
/* check smallbins */
2678
for (i = 1; i < NBINS; ++i) {
2680
total += do_check_smallbin(av, i, b);
2683
/* check treebins */
2684
for (i = 0; i < NBINS; ++i) {
2685
tb = tbin_at(av, i);
2687
empty = (av->treebits & (1 << i)) == 0;
2692
total += do_check_tree(t);
2697
/* top chunk is OK */
2698
check_chunk(av->top);
2699
/* top not in tree */
2700
if (!in_smallbin_range(chunksize(av->top)))
2701
assert(tree_find((tchunkptr)(av->top)) == 0);
2703
/* max_fast is in allowed range */
2704
assert(get_max_fast(av) <= request2size(MAX_FAST_SIZE));
2706
max_fast_bin = fastbin_index(av->max_fast);
2708
for (i = 0; i < NFASTBINS; ++i) {
2709
p = av->fastbins[i];
2711
/* all bins past max_fast are empty */
2712
if (i > max_fast_bin)
2716
/* each chunk claims to be inuse */
2717
do_check_inuse_chunk(p);
2718
total += chunksize(p);
2719
/* chunk belongs in this bin */
2720
assert(fastbin_index(chunksize(p)) == i);
2725
/* sanity checks for statistics */
2727
assert(total <= (CHUNK_SIZE_T)(av->max_total_mem));
2729
assert(av->n_mmaps >= 0);
2730
assert(av->n_mmaps <= av->n_mmaps_max);
2731
assert(av->n_mmaps <= av->max_n_mmaps);
2733
assert((CHUNK_SIZE_T)(av->sbrked_mem) <=
2734
(CHUNK_SIZE_T)(av->max_sbrked_mem));
2736
assert((CHUNK_SIZE_T)(av->mmapped_mem) <=
2737
(CHUNK_SIZE_T)(av->max_mmapped_mem));
2739
assert((CHUNK_SIZE_T)(av->max_total_mem) >=
2740
(CHUNK_SIZE_T)(av->mmapped_mem) + (CHUNK_SIZE_T)(av->sbrked_mem));
2747
----------- Operations on trees -----------
2751
Insert chunk into corresponding list or tree
2754
static void insert_treenode(mstate av, tchunkptr x,
2756
bin_index_t idx = treebin_index(nb);
2757
tbinptr* bin = tbin_at(av, idx);
2765
av->treebits |= idx2bit(idx);
2767
x->parent = (tchunkptr)bin;
2772
bin_index_t shift = bitshift_for_index(idx);
2776
while (chunksize(t) != nb) {
2777
tchunkptr* pchild = &(t->child[(nb >> shift--) & 1]);
2789
/* Link in same-sized node */
2798
static void transfer_tree_links(tchunkptr oldt, tchunkptr newt) {
2799
tchunkptr p = oldt->parent;
2802
if (p->child[0] == oldt)
2804
else if (p->child[1] == oldt)
2807
*((tbinptr*)p) = newt;
2809
if ( (newt->child[0] = oldt->child[0]) != 0)
2810
newt->child[0]->parent = newt;
2812
if ( (newt->child[1] = oldt->child[1]) != 0)
2813
newt->child[1]->parent = newt;
2816
static tchunkptr find_replacement(tchunkptr t) {
2818
Unless t is itself a leaf node, we must replace t with a leaf
2819
node (not merely one with an open left or right, as with binary
2820
search trees), to make sure that lefts and rights of descendents
2821
correspond properly to bit masks. We use the leftmost leaf of
2822
right child, or, if there is no right child, the rightmost leaf
2823
of left child. We could use any other leaf, but these choices
2824
will tend to maintain nicer trees.
2828
if ((c = *(cp = &(t->child[1]))) == 0)
2829
if ((c = *(cp = &(t->child[0]->child[1]))) == 0)
2830
c = *(cp = &(t->child[0]));
2834
if (c->child[0] != 0)
2835
c = *(cp = &(c->child[0]));
2836
else if (c->child[1] != 0)
2837
c = *(cp = &(c->child[1]));
2839
*cp = 0; /* unlink from parent */
2845
static void unlink_leaf_node(mstate av, tchunkptr t) {
2846
tchunkptr p = t->parent;
2847
if (p->child[0] == t)
2849
else if (p->child[1] == t)
2852
assert(is_tbin(av, p));
2854
av->treebits &= ~idx2bit(t->index);
2858
static void unlink_chained_node(tchunkptr t) {
2859
tchunkptr bck = t->bk;
2860
tchunkptr fwd = t->fd;
2863
/* t's parent is nonnull if t was head of chain */
2865
transfer_tree_links(t, fwd);
2872
----------- other helper functions -----------
2873
We expect these to be inlined
2877
static void insert_small_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T nb) {
2878
bin_index_t idx = smallbin_index(nb);
2879
mchunkptr bck = bin_at(av, idx);
2880
mchunkptr fwd = bck->fd;
2881
mark_smallbin(av, idx);
2884
fwd->bk = bck->fd = p;
2886
assert(in_smallbin_range(nb));
2889
static void insert_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T nb) {
2890
if (in_smallbin_range(nb))
2891
insert_small_chunk(av, p, nb);
2893
insert_treenode(av, (tchunkptr)p, nb);
2897
static mchunkptr take_from_smallbin(mstate av, mchunkptr bin, bitmap_t bit) {
2898
mchunkptr p = bin->bk;
2899
mchunkptr bck = p->bk;
2904
av->smallbits &= ~bit;
2908
static void unlink_chunk(mstate av, mchunkptr q, CHUNK_SIZE_T size) {
2909
mchunkptr fwd = q->fd;
2910
mchunkptr bck = q->bk;
2913
if (fwd == bck && in_smallbin_range(size)) {
2914
clear_smallbin(av, smallbin_index(size));
2916
else if (!in_smallbin_range(size)) {
2917
tchunkptr t = (tchunkptr)q;
2918
tchunkptr c = (tchunkptr)fwd;
2920
if (t->child[0] == t->child[1]) {
2921
unlink_leaf_node(av, t);
2925
c = find_replacement(t);
2929
if (t->parent == 0) {
2934
transfer_tree_links(t, c);
2941
------------------------------ malloc ------------------------------
2944
Void_t* mALLOc(size_t bytes) {
2945
mstate av = get_malloc_state();
2948
checked_request2size(bytes, nb);
2950
if (nb <= (CHUNK_SIZE_T)(av->max_fast)) {
2951
mfastbinptr* fb = &(av->fastbins[(fastbin_index(nb))]);
2955
check_remalloced_chunk(fp, nb);
2956
return chunk2mem(fp);
2960
if (in_smallbin_range(nb)) {
2961
bin_index_t sidx = smallbin_index(nb);
2962
bitmap_t sbit = idx2bit(sidx);
2964
if (sbit <= av->smallbits) {
2966
if ((sbit & av->smallbits) != 0) {
2967
p = take_from_smallbin(av, bin_at(av,sidx), sbit);
2968
set_inuse_bit_at_offset(p, nb);
2971
bitmap_t nbit = least_bit(left_bits(sbit) & av->smallbits);
2972
bin_index_t nidx = bit2idx(nbit);
2973
CHUNK_SIZE_T psize = size_for_smallindex(nidx);
2974
CHUNK_SIZE_T qsize = psize - nb;
2975
p = take_from_smallbin(av, bin_at(av, nidx), nbit);
2976
if (qsize < MINSIZE) {
2977
set_inuse_bit_at_offset(p, psize);
2980
mchunkptr q = chunk_at_offset(p, nb);
2981
set_head(p, nb | PREV_INUSE);
2982
set_head(q, qsize | PREV_INUSE);
2984
insert_small_chunk(av, q, qsize);
2987
check_malloced_chunk(p, nb);
2988
return chunk2mem(p);
2991
if (av->treebits != 0) {
2992
bitmap_t vbit = least_bit(av->treebits);
2993
bin_index_t vidx = bit2idx(vbit);
2994
tbinptr* vbin = tbin_at(av, vidx);
2995
tchunkptr bestchunk = *vbin;
2996
tchunkptr c = leftmost_child(bestchunk);
2997
CHUNK_SIZE_T bestsize = chunksize(bestchunk);
3001
/* Fast path if remainder will replace bestchunk */
3003
rsize = bestsize - nb;
3006
if (rsize >= minsize_for_treeindex(vidx) &&
3007
bestchunk->bk == bestchunk) {
3008
tchunkptr r = (tchunkptr)(chunk_at_offset(bestchunk, nb));
3010
set_head(bestchunk, nb | PREV_INUSE);
3011
set_head(r, rsize | PREV_INUSE);
3018
r->parent = (tchunkptr)vbin;
3020
check_malloced_chunk((mchunkptr)bestchunk, nb);
3021
return chunk2mem(bestchunk);
3026
CHUNK_SIZE_T csize = chunksize(c);
3027
if (csize < bestsize) {
3032
c = leftmost_child(c);
3036
if (bestchunk->bk != bestchunk)
3037
unlink_chained_node(bestchunk);
3039
unlink_leaf_node(av, leaf);
3040
if (leaf != bestchunk)
3041
transfer_tree_links(bestchunk, leaf);
3044
rsize = bestsize - nb;
3045
if (rsize >= MINSIZE) {
3046
mchunkptr rem = chunk_at_offset(bestchunk, nb);
3047
set_head(bestchunk, nb | PREV_INUSE);
3048
set_head(rem, rsize | PREV_INUSE);
3049
set_foot(rem, rsize);
3050
insert_chunk(av, rem, rsize);
3053
set_inuse_bit_at_offset(bestchunk, bestsize);
3055
check_malloced_chunk((mchunkptr)(bestchunk), nb);
3056
return chunk2mem(bestchunk);
3061
bin_index_t tidx = treebin_index(nb);
3062
bitmap_t tbit = idx2bit(tidx);
3064
if (tbit <= av->treebits) {
3065
tchunkptr bestchunk = 0;
3066
CHUNK_SIZE_T bestsize = MAX_CHUNK_SIZE;
3069
if ((tbit & av->treebits) != 0) {
3070
tchunkptr t = *tbin_at(av, tidx);
3071
bin_index_t shift = bitshift_for_index(tidx);
3074
CHUNK_SIZE_T tsize = chunksize(t);
3076
if (tsize >= nb && tsize < bestsize) {
3079
if (tsize == nb && t->bk != t)
3083
dir = (shift == 0)? 0 : (nb >> shift--) & 1;
3084
t = leaf->child[dir];
3086
shift = 0; /* if forced right, go leftmost from now on */
3087
t = leaf->child[1-dir];
3095
if (bestchunk == 0) {
3098
if (have_fastchunks(av)) {
3099
Void_t* cp = malloc_consolidate(av, nb, nb+nb);
3104
vbit = least_bit(left_bits(tbit) & av->treebits);
3106
bin_index_t vidx = bit2idx(vbit);
3107
tbinptr* vbin = tbin_at(av, vidx);
3108
tchunkptr c = *vbin;
3110
CHUNK_SIZE_T csize = chunksize(c);
3112
if (csize < bestsize) {
3116
c = leftmost_child(c);
3122
if (bestchunk != 0) {
3125
if (bestchunk->bk != bestchunk)
3126
unlink_chained_node(bestchunk);
3128
unlink_leaf_node(av, leaf);
3129
if (leaf != bestchunk)
3130
transfer_tree_links(bestchunk, leaf);
3133
rsize = bestsize - nb;
3134
if (rsize >= MINSIZE) {
3135
mchunkptr rem = chunk_at_offset(bestchunk, nb);
3136
set_head(bestchunk, nb | PREV_INUSE);
3137
set_head(rem, rsize | PREV_INUSE);
3138
set_foot(rem, rsize);
3139
insert_chunk(av, rem, rsize);
3142
set_inuse_bit_at_offset(bestchunk, bestsize);
3144
check_malloced_chunk((mchunkptr)(bestchunk), nb);
3145
return chunk2mem(bestchunk);
3151
If large enough, split off the chunk bordering the end of memory
3152
(held in av->top). This is called in accord with the best-fit
3153
search rule. In effect, av->top is treated as larger (and thus
3154
less well fitting) than any other available chunk since it can
3155
be extended to be as large as necessary (up to system
3158
We require that av->top always exists (i.e., has size >=
3159
MINSIZE) after initialization, so if it would otherwise be
3160
exhuasted by current request, it is replenished. (The main
3161
reason for ensuring it exists is that we may need MINSIZE space
3162
to put in fenceposts in sysmalloc.)
3166
mchunkptr topchunk = av->top;
3167
CHUNK_SIZE_T topsize = chunksize(topchunk);
3169
if (topsize < nb + MINSIZE) {
3170
if (have_fastchunks(av)) {
3171
Void_t* cp = malloc_consolidate(av, nb, MAX_CHUNK_SIZE);
3176
topsize = chunksize(topchunk);
3181
if (topsize >= nb + MINSIZE) {
3182
CHUNK_SIZE_T remainder_size = topsize - nb;
3183
mchunkptr remainder = chunk_at_offset(topchunk, nb);
3185
av->top = remainder;
3186
set_head(topchunk, nb | PREV_INUSE);
3187
set_head(remainder, remainder_size | PREV_INUSE);
3189
check_malloced_chunk(topchunk, nb);
3190
return chunk2mem(topchunk);
3195
return sysmalloc(av, nb);
3199
------------------------------ free ------------------------------
3203
void fREe(Void_t* mem) {
3204
mstate av = get_malloc_state();
3206
mchunkptr p = mem2chunk(mem);
3209
INTERNAL_SIZE_T rawsize = p->size;
3210
CHUNK_SIZE_T size = chunksize(p);
3211
check_inuse_chunk(p);
3214
If eligible, place chunk on a fastbin so it can be found
3215
and used quickly in malloc.
3218
if ((CHUNK_SIZE_T)(size) <= (CHUNK_SIZE_T)(av->max_fast)
3222
If TRIM_FASTBINS set, don't place chunks
3223
bordering top into fastbins
3225
&& (chunk_at_offset(p, size) != av->top)
3231
fb = &(av->fastbins[fastbin_index(size)]);
3236
else if ((rawsize & IS_MMAPPED) == 0) {
3237
mchunkptr nextchunk = chunk_at_offset(p, size);
3238
CHUNK_SIZE_T nextsize;
3240
if ((rawsize & PREV_INUSE) == 0) {
3241
CHUNK_SIZE_T prevsize = p->prev_size;
3243
p = chunk_at_offset(p, -((long) prevsize));
3244
unlink_chunk(av, p, prevsize);
3247
nextsize = chunksize(nextchunk);
3248
if (nextchunk == av->top) {
3250
set_head(p, size | PREV_INUSE);
3252
if (size >= av->trim_threshold) {
3253
systrim(av, av->top_pad);
3257
if (!inuse_bit_at_offset(nextchunk, nextsize)) {
3259
unlink_chunk(av, nextchunk, nextsize);
3262
set_head(nextchunk, nextsize);
3264
set_head(p, size | PREV_INUSE);
3266
insert_chunk(av, p, size);
3272
INTERNAL_SIZE_T offset = p->prev_size;
3274
av->mmapped_mem -= (size + offset);
3275
ret = munmap((char*)p - offset, size + offset);
3276
/* munmap returns non-zero on failure */
3284
------------------------- malloc_consolidate -------------------------
3286
malloc_consolidate tears down chunks held in fastbins, returning
3287
one if withing bounds.
3290
static Void_t* malloc_consolidate(mstate av, CHUNK_SIZE_T nb, CHUNK_SIZE_T maxnb) {
3292
for (i = 0; i < NFASTBINS; ++i) {
3293
mfastbinptr* fb = &(av->fastbins[i]);
3300
mchunkptr nextp = p->fd;
3301
INTERNAL_SIZE_T rawsize = p->size;
3302
CHUNK_SIZE_T size = chunksize(p);
3303
mchunkptr nextchunk = chunk_at_offset(p, size);
3304
CHUNK_SIZE_T nextsize;
3306
if ((rawsize & PREV_INUSE) == 0) {
3307
CHUNK_SIZE_T prevsize = p->prev_size;
3309
p = chunk_at_offset(p, -((long) prevsize));
3310
unlink_chunk(av, p, prevsize);
3313
nextsize = chunksize(nextchunk);
3314
if (nextchunk == av->top) {
3316
set_head(p, size | PREV_INUSE);
3320
if (!inuse_bit_at_offset(nextchunk, nextsize)) {
3322
unlink_chunk(av, nextchunk, nextsize);
3325
set_head(nextchunk, nextsize);
3327
set_head(p, size | PREV_INUSE);
3330
if (size < nb || size >= maxnb) {
3331
insert_chunk(av, p, size);
3334
CHUNK_SIZE_T remainder_size = size - nb;
3338
if (remainder_size < MINSIZE) {
3339
set_inuse_bit_at_offset(p, size);
3340
check_malloced_chunk(p, nb);
3341
return chunk2mem(p);
3345
mchunkptr remainder = chunk_at_offset(p, nb);
3346
set_head(p, nb | PREV_INUSE);
3347
set_head(remainder, remainder_size | PREV_INUSE);
3348
set_foot(remainder, remainder_size);
3349
insert_chunk(av, remainder, remainder_size);
3350
check_malloced_chunk(p, nb);
3351
return chunk2mem(p);
3360
clear_fastchunks(av);
3366
------------------------------ realloc ------------------------------
3370
Void_t* rEALLOc(Void_t* oldmem, size_t bytes) {
3371
mstate av = get_malloc_state();
3373
INTERNAL_SIZE_T nb; /* padded request size */
3375
mchunkptr oldp; /* chunk corresponding to oldmem */
3376
CHUNK_SIZE_T oldsize; /* its size */
3378
mchunkptr newp; /* chunk to return */
3379
CHUNK_SIZE_T newsize; /* its size */
3380
Void_t* newmem; /* corresponding user mem */
3382
mchunkptr next; /* next contiguous chunk after oldp */
3384
mchunkptr remainder; /* extra space at end of newp */
3385
CHUNK_SIZE_T remainder_size; /* its size */
3387
CHUNK_SIZE_T copysize; /* bytes to copy */
3388
unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */
3389
INTERNAL_SIZE_T* s; /* copy source */
3390
INTERNAL_SIZE_T* d; /* copy destination */
3393
#ifdef REALLOC_ZERO_BYTES_FREES
3400
/* realloc of null is supposed to be same as malloc */
3401
if (oldmem == 0) return mALLOc(bytes);
3403
checked_request2size(bytes, nb);
3405
oldp = mem2chunk(oldmem);
3406
oldsize = chunksize(oldp);
3408
check_inuse_chunk(oldp);
3410
if (!chunk_is_mmapped(oldp)) {
3412
if ((CHUNK_SIZE_T)(oldsize) >= (CHUNK_SIZE_T)(nb)) {
3413
/* already big enough; split below */
3419
next = chunk_at_offset(oldp, oldsize);
3421
/* Try to expand forward into top */
3422
if (next == av->top &&
3423
(CHUNK_SIZE_T)(newsize = oldsize + chunksize(next)) >=
3424
(CHUNK_SIZE_T)(nb + MINSIZE)) {
3425
set_head_size(oldp, nb);
3426
av->top = chunk_at_offset(oldp, nb);
3427
set_head(av->top, (newsize - nb) | PREV_INUSE);
3428
return chunk2mem(oldp);
3431
/* Try to expand forward into next chunk; split off remainder below */
3432
else if (next != av->top &&
3434
(CHUNK_SIZE_T)(newsize = oldsize + chunksize(next)) >=
3435
(CHUNK_SIZE_T)(nb)) {
3437
unlink_chunk(av, next, chunksize(next));
3440
/* allocate, copy, free */
3442
newmem = mALLOc(nb - MALLOC_ALIGN_MASK);
3444
return 0; /* propagate failure */
3446
newp = mem2chunk(newmem);
3447
newsize = chunksize(newp);
3450
Avoid copy if newp is next chunk after oldp.
3458
Unroll copy of <= 36 bytes (72 if 8byte sizes)
3459
We know that contents have an odd number of
3460
INTERNAL_SIZE_T-sized words; minimally 3.
3463
copysize = oldsize - SIZE_SZ;
3464
s = (INTERNAL_SIZE_T*)(oldmem);
3465
d = (INTERNAL_SIZE_T*)(newmem);
3466
ncopies = copysize / sizeof(INTERNAL_SIZE_T);
3467
assert(ncopies >= 3);
3470
MALLOC_COPY(d, s, copysize);
3491
check_inuse_chunk(newp);
3492
return chunk2mem(newp);
3497
/* If possible, free extra space in old or extended chunk */
3499
assert((CHUNK_SIZE_T)(newsize) >= (CHUNK_SIZE_T)(nb));
3501
remainder_size = newsize - nb;
3503
if (remainder_size < MINSIZE) { /* not enough extra to split off */
3504
set_head_size(newp, newsize);
3505
set_inuse_bit_at_offset(newp, newsize);
3507
else { /* split remainder */
3508
remainder = chunk_at_offset(newp, nb);
3509
set_head_size(newp, nb);
3510
set_head(remainder, remainder_size | PREV_INUSE);
3511
/* Mark remainder as inuse so free() won't complain */
3512
set_inuse_bit_at_offset(remainder, remainder_size);
3513
fREe(chunk2mem(remainder));
3516
check_inuse_chunk(newp);
3517
return chunk2mem(newp);
3528
INTERNAL_SIZE_T offset = oldp->prev_size;
3529
size_t pagemask = av->pagesize - 1;
3533
/* Note the extra SIZE_SZ overhead */
3534
newsize = (nb + offset + SIZE_SZ + pagemask) & ~pagemask;
3536
/* don't need to remap if still within same page */
3537
if (oldsize == newsize - offset)
3540
cp = (char*)mremap((char*)oldp - offset, oldsize + offset, newsize, 1);
3542
if (cp != (char*)MORECORE_FAILURE) {
3544
newp = (mchunkptr)(cp + offset);
3545
set_head(newp, (newsize - offset)|IS_MMAPPED);
3547
assert(aligned_OK(chunk2mem(newp)));
3548
assert((newp->prev_size == offset));
3550
/* update statistics */
3551
sum = av->mmapped_mem += newsize - oldsize;
3552
if (sum > (CHUNK_SIZE_T)(av->max_mmapped_mem))
3553
av->max_mmapped_mem = sum;
3554
sum += av->sbrked_mem;
3555
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
3556
av->max_total_mem = sum;
3558
return chunk2mem(newp);
3562
/* Note the extra SIZE_SZ overhead. */
3563
if ((CHUNK_SIZE_T)(oldsize) >= (CHUNK_SIZE_T)(nb + SIZE_SZ))
3564
newmem = oldmem; /* do nothing */
3566
/* Must alloc, copy, free. */
3567
newmem = mALLOc(nb - MALLOC_ALIGN_MASK);
3569
MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
3576
/* If !HAVE_MMAP, but chunk_is_mmapped, user must have overwritten mem */
3577
check_malloc_state(av);
3578
MALLOC_FAILURE_ACTION;
3585
------------------------------ memalign ------------------------------
3588
Void_t* mEMALIGn(size_t alignment, size_t bytes) {
3589
INTERNAL_SIZE_T nb; /* padded request size */
3590
char* m; /* memory returned by malloc call */
3591
mchunkptr p; /* corresponding chunk */
3592
char* brk; /* alignment point within p */
3593
mchunkptr newp; /* chunk to return */
3594
INTERNAL_SIZE_T newsize; /* its size */
3595
INTERNAL_SIZE_T leadsize; /* leading space before alignment point */
3596
mchunkptr remainder; /* spare room at end to split off */
3597
CHUNK_SIZE_T remainder_size; /* its size */
3598
INTERNAL_SIZE_T size;
3600
/* If need less alignment than we give anyway, just relay to malloc */
3602
if (alignment <= MALLOC_ALIGNMENT) return mALLOc(bytes);
3604
/* Otherwise, ensure that it is at least a minimum chunk size */
3606
if (alignment < MINSIZE) alignment = MINSIZE;
3608
/* Make sure alignment is power of 2 (in case MINSIZE is not). */
3609
if ((alignment & (alignment - 1)) != 0) {
3610
size_t a = MALLOC_ALIGNMENT * 2;
3611
while ((CHUNK_SIZE_T)a < (CHUNK_SIZE_T)alignment) a <<= 1;
3615
checked_request2size(bytes, nb);
3618
Strategy: find a spot within that chunk that meets the alignment
3619
request, and then possibly free the leading and trailing space.
3623
/* Call malloc with worst case padding to hit alignment. */
3625
m = (char*)(mALLOc(nb + alignment + MINSIZE));
3627
if (m == 0) return 0; /* propagate failure */
3631
if ((((PTR_UINT)(m)) % alignment) != 0) { /* misaligned */
3634
Find an aligned spot inside chunk. Since we need to give back
3635
leading space in a chunk of at least MINSIZE, if the first
3636
calculation places us at a spot with less than MINSIZE leader,
3637
we can move to the next aligned spot -- we've allocated enough
3638
total room so that this is always possible.
3641
brk = (char*)mem2chunk((PTR_UINT)(((PTR_UINT)(m + alignment - 1)) &
3642
-((signed long) alignment)));
3643
if ((CHUNK_SIZE_T)(brk - (char*)(p)) < MINSIZE)
3646
newp = (mchunkptr)brk;
3647
leadsize = brk - (char*)(p);
3648
newsize = chunksize(p) - leadsize;
3650
/* For mmapped chunks, just adjust offset */
3651
if (chunk_is_mmapped(p)) {
3652
newp->prev_size = p->prev_size + leadsize;
3653
set_head(newp, newsize|IS_MMAPPED);
3654
return chunk2mem(newp);
3657
/* Otherwise, give back leader, use the rest */
3658
set_head(newp, newsize | PREV_INUSE);
3659
set_inuse_bit_at_offset(newp, newsize);
3660
set_head_size(p, leadsize);
3664
assert (newsize >= nb &&
3665
(((PTR_UINT)(chunk2mem(p))) % alignment) == 0);
3668
/* Also give back spare room at the end */
3669
if (!chunk_is_mmapped(p)) {
3670
size = chunksize(p);
3671
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb + MINSIZE)) {
3672
remainder_size = size - nb;
3673
remainder = chunk_at_offset(p, nb);
3674
set_head(remainder, remainder_size | PREV_INUSE);
3675
set_head_size(p, nb);
3676
fREe(chunk2mem(remainder));
3680
check_inuse_chunk(p);
3681
return chunk2mem(p);
3685
------------------------------ calloc ------------------------------
3688
Void_t* cALLOc(size_t n_elements, size_t elem_size) {
3689
Void_t* mem = mALLOc(n_elements * elem_size);
3692
mchunkptr p = mem2chunk(mem);
3693
INTERNAL_SIZE_T* d = (INTERNAL_SIZE_T*)mem;
3695
if (!chunk_is_mmapped(p))
3698
Unroll clear of <= 36 bytes (72 if 8byte sizes)
3699
We know that contents have an odd number of
3700
INTERNAL_SIZE_T-sized words; minimally 3.
3703
CHUNK_SIZE_T clearsize = chunksize(p) - SIZE_SZ;
3704
CHUNK_SIZE_T nclears = clearsize / sizeof(INTERNAL_SIZE_T);
3705
assert(nclears >= 3);
3708
MALLOC_ZERO(d, clearsize);
3732
Note the additional SIZE_SZ
3734
CHUNK_SIZE_T clearsize = chunksize(p) - 2*SIZE_SZ;
3735
MALLOC_ZERO(d, clearsize);
3743
------------------------------ cfree ------------------------------
3746
void cFREe(Void_t *mem) {
3751
------------------------- independent_calloc -------------------------
3755
Void_t** iCALLOc(size_t n_elements, size_t elem_size, Void_t* chunks[]) {
3756
size_t sz = elem_size; /* serves as 1-element array */
3757
/* opts arg of 3 means all elements are same size, and should be cleared */
3758
return iALLOc(n_elements, &sz, 3, chunks);
3762
------------------------- independent_comalloc -------------------------
3765
Void_t** iCOMALLOc(size_t n_elements, size_t sizes[], Void_t* chunks[]) {
3766
return iALLOc(n_elements, sizes, 0, chunks);
3771
------------------------------ ialloc ------------------------------
3772
ialloc provides common support for independent_X routines, handling all of
3773
the combinations that can result.
3776
bit 0 set if all elements are same size (using sizes[0])
3777
bit 1 set if elements should be zeroed
3781
static Void_t** iALLOc(size_t n_elements,
3785
mstate av = get_malloc_state();
3786
INTERNAL_SIZE_T element_size; /* chunksize of each element, if all same */
3787
INTERNAL_SIZE_T contents_size; /* total size of elements */
3788
INTERNAL_SIZE_T array_size; /* request size of pointer array */
3789
Void_t* mem; /* malloced aggregate space */
3790
mchunkptr p; /* corresponding chunk */
3791
CHUNK_SIZE_T remainder_size; /* remaining bytes while splitting */
3792
Void_t** marray; /* either "chunks" or malloced ptr array */
3793
mchunkptr array_chunk; /* chunk for malloced ptr array */
3794
unsigned int mprops; /* to disable mmap */
3798
ensure_initialization(av);
3800
/* compute array length, if needed */
3802
if (n_elements == 0)
3803
return chunks; /* nothing to do */
3808
/* if empty req, must still return chunk representing empty array */
3809
if (n_elements == 0)
3810
return (Void_t**) mALLOc(0);
3812
array_size = request2size(n_elements * (sizeof(Void_t*)));
3815
/* compute total element size */
3816
if (opts & 0x1) { /* all-same-size */
3817
element_size = request2size(*sizes);
3818
contents_size = n_elements * element_size;
3820
else { /* add up all the sizes */
3823
for (i = 0; i != n_elements; ++i)
3824
contents_size += request2size(sizes[i]);
3827
/* subtract out alignment bytes from total to minimize overallocation */
3828
size = contents_size + array_size - MALLOC_ALIGN_MASK;
3831
Allocate the aggregate chunk.
3832
But first disable mmap so malloc won't use it, since
3833
we would not be able to later free/realloc space internal
3834
to a segregated mmap region.
3837
mprops = av->sysctl; /* disable mmap */
3840
av->sysctl = mprops; /* reset mmap */
3845
assert(!chunk_is_mmapped(p));
3846
remainder_size = chunksize(p);
3849
if (opts & 0x2) { /* optionally clear the elements */
3850
MALLOC_ZERO(mem, remainder_size - SIZE_SZ - array_size);
3853
/* If not provided, allocate the pointer array as final part of chunk */
3855
array_chunk = chunk_at_offset(p, contents_size);
3856
marray = (Void_t**) (chunk2mem(array_chunk));
3857
set_head(array_chunk, (remainder_size - contents_size) | PREV_INUSE);
3858
remainder_size = contents_size;
3861
/* split out elements */
3862
for (i = 0; ; ++i) {
3863
marray[i] = chunk2mem(p);
3864
if (i != n_elements-1) {
3865
if (element_size != 0)
3866
size = element_size;
3868
size = request2size(sizes[i]);
3869
remainder_size -= size;
3870
set_head(p, size | PREV_INUSE);
3871
p = chunk_at_offset(p, size);
3873
else { /* the final element absorbs any overallocation slop */
3874
set_head(p, remainder_size | PREV_INUSE);
3880
if (marray != chunks) {
3881
/* final element must have exactly exhausted chunk */
3882
if (element_size != 0)
3883
assert(remainder_size == element_size);
3885
assert(remainder_size == request2size(sizes[i]));
3886
check_inuse_chunk(mem2chunk(marray));
3889
for (i = 0; i != n_elements; ++i)
3890
check_inuse_chunk(mem2chunk(marray[i]));
3898
------------------------------ valloc ------------------------------
3901
Void_t* vALLOc(size_t bytes) {
3902
mstate av = get_malloc_state();
3903
ensure_initialization(av);
3904
return mEMALIGn(av->pagesize, bytes);
3908
------------------------------ pvalloc ------------------------------
3912
Void_t* pVALLOc(size_t bytes) {
3913
mstate av = get_malloc_state();
3916
ensure_initialization(av);
3917
pagesz = av->pagesize;
3918
return mEMALIGn(pagesz, (bytes + pagesz - 1) & ~(pagesz - 1));
3923
------------------------------ malloc_trim ------------------------------
3926
int mTRIm(size_t pad) {
3927
mstate av = get_malloc_state();
3928
return systrim(av, pad);
3933
------------------------- malloc_usable_size -------------------------
3936
size_t mUSABLe(Void_t* mem) {
3940
if (chunk_is_mmapped(p))
3941
return chunksize(p) - 2*SIZE_SZ;
3943
return chunksize(p) - SIZE_SZ;
3949
------------------------------ mallinfo ------------------------------
3953
Recursive helper function for mallinfo
3956
static void count_tree_blocks(tchunkptr t, int* pcount, INTERNAL_SIZE_T* pavail) {
3958
tchunkptr p = t->bk;
3961
*pavail += chunksize(p);
3964
if (t->child[0] != 0)
3965
count_tree_blocks(t->child[0], pcount, pavail);
3972
struct mallinfo mALLINFo()
3974
mstate av = get_malloc_state();
3976
INTERNAL_SIZE_T avail;
3977
INTERNAL_SIZE_T topsize;
3979
INTERNAL_SIZE_T fastavail;
3990
check_malloc_state(av);
3992
topsize = chunksize(av->top);
3994
nblocks = 1; /* top always exists */
3996
/* traverse fastbins */
4000
for (i = 0; i < NFASTBINS; ++i) {
4001
for (p = av->fastbins[i]; p != 0; p = p->fd) {
4003
fastavail += chunksize(p);
4009
/* traverse small bins */
4010
for (i = 2; i < NBINS; ++i) {
4011
mbinptr b = bin_at(av, i);
4013
for (p = b->bk; p != b; p = p->bk) {
4015
avail += chunksize(p);
4019
/* traverse tree bins */
4020
for (i = 0; i < NBINS; ++i) {
4021
tchunkptr t = *(tbin_at(av, i));
4023
count_tree_blocks(t, &nblocks, &avail);
4027
mi.smblks = nfastblocks;
4029
mi.ordblks = nblocks;
4030
mi.fordblks = avail;
4031
mi.uordblks = av->sbrked_mem - avail;
4032
mi.arena = av->sbrked_mem;
4033
mi.hblks = av->n_mmaps;
4034
mi.hblkhd = av->mmapped_mem;
4036
mi.keepcost = topsize;
4037
mi.usmblks = av->max_total_mem;
4042
------------------------------ malloc_stats ------------------------------
4046
struct mallinfo mi = mALLINFo();
4050
CHUNK_SIZE_T free, reserved, committed;
4051
vminfo (&free, &reserved, &committed);
4052
fprintf(stderr, "free bytes = %10lu\n",
4054
fprintf(stderr, "reserved bytes = %10lu\n",
4056
fprintf(stderr, "committed bytes = %10lu\n",
4062
fprintf(stderr, "max system bytes = %10lu\n",
4063
(CHUNK_SIZE_T)(mi.usmblks));
4064
fprintf(stderr, "system bytes = %10lu\n",
4065
(CHUNK_SIZE_T)(mi.arena + mi.hblkhd));
4066
fprintf(stderr, "in use bytes = %10lu\n",
4067
(CHUNK_SIZE_T)(mi.uordblks + mi.hblkhd));
4070
fprintf(stderr, "n0 = %10u\n", n0);
4071
fprintf(stderr, "n1 = %10u\n", n1);
4072
fprintf(stderr, "n2 = %10u\n", n2);
4073
fprintf(stderr, "n3 = %10u\n", n3);
4074
fprintf(stderr, "n4 = %10u\n", n4);
4075
fprintf(stderr, "n5 = %10u\n", n5);
4076
fprintf(stderr, "n6 = %10u\n", n6);
4077
fprintf(stderr, "n7 = %10u\n", n7);
4078
fprintf(stderr, "n8 = %10u\n", n8);
4084
CHUNK_SIZE_T kernel, user;
4085
if (cpuinfo (TRUE, &kernel, &user)) {
4086
fprintf(stderr, "kernel ms = %10lu\n",
4088
fprintf(stderr, "user ms = %10lu\n",
4097
------------------------------ mallopt ------------------------------
4100
int mALLOPt(int param_number, int value) {
4101
mstate av = get_malloc_state();
4103
ensure_initialization(av);
4105
switch(param_number) {
4107
malloc_consolidate(av, MAX_CHUNK_SIZE, MAX_CHUNK_SIZE);
4108
if (value >= 0 && value <= MAX_FAST_SIZE) {
4109
set_max_fast(av, value);
4115
case M_TRIM_THRESHOLD:
4116
av->trim_threshold = value;
4120
av->top_pad = value;
4123
case M_MMAP_THRESHOLD:
4124
av->mmap_threshold = value;
4132
av->n_mmaps_max = value;
4140
/* ----------- Routines dealing with system allocation -------------- */
4143
static mchunkptr mmap_malloc(mstate av, INTERNAL_SIZE_T nb) {
4144
char* mm; /* return value from mmap call*/
4145
CHUNK_SIZE_T sum; /* for updating stats */
4146
mchunkptr p; /* the allocated/returned chunk */
4148
INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
4150
size_t pagemask = av->pagesize - 1;
4153
Round up size to nearest page. For mmapped chunks, the overhead
4154
is one SIZE_SZ unit larger than for normal chunks, because there
4155
is no following chunk whose prev_size field could be used.
4157
size = (nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
4159
/* Don't try if size wraps around 0 */
4160
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb)) {
4162
mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
4164
if (mm != (char*)(MORECORE_FAILURE)) {
4167
The offset to the start of the mmapped region is stored
4168
in the prev_size field of the chunk. This allows us to adjust
4169
returned start address to meet alignment requirements here
4170
and in memalign(), and still be able to compute proper
4171
address argument for later munmap in free() and realloc().
4174
front_misalign = (INTERNAL_SIZE_T)chunk2mem(mm) & MALLOC_ALIGN_MASK;
4175
if (front_misalign > 0) {
4176
correction = MALLOC_ALIGNMENT - front_misalign;
4177
p = (mchunkptr)(mm + correction);
4178
p->prev_size = correction;
4179
set_head(p, (size - correction) |IS_MMAPPED);
4184
set_head(p, size|IS_MMAPPED);
4187
/* update statistics */
4189
if (++av->n_mmaps > av->max_n_mmaps)
4190
av->max_n_mmaps = av->n_mmaps;
4192
sum = av->mmapped_mem += size;
4193
if (sum > (CHUNK_SIZE_T)(av->max_mmapped_mem))
4194
av->max_mmapped_mem = sum;
4195
sum += av->sbrked_mem;
4196
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
4197
av->max_total_mem = sum;
4210
sysmalloc handles malloc cases requiring more memory from the system.
4211
On entry, it is assumed that av->top does not have enough
4212
space to service request for nb bytes, thus requiring that av->top
4213
be extended or replaced.
4216
static Void_t* sysmalloc(mstate av, CHUNK_SIZE_T nb) {
4217
mchunkptr old_top; /* incoming value of av->top */
4218
INTERNAL_SIZE_T old_size; /* its size */
4219
char* old_end; /* its end address */
4221
long size; /* arg to first MORECORE or mmap call */
4222
char* brk; /* return value from MORECORE */
4224
long correction; /* arg to 2nd MORECORE call */
4225
char* snd_brk; /* 2nd return val */
4227
INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
4228
INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */
4229
char* aligned_brk; /* aligned offset into brk */
4231
mchunkptr p; /* the allocated/returned chunk */
4232
mchunkptr remainder; /* remainder from allocation */
4233
CHUNK_SIZE_T remainder_size; /* its size */
4235
CHUNK_SIZE_T sum; /* for updating stats */
4240
Initialize av if necessary
4243
malloc_init_state(av);
4244
/* to allow call solely for initialization */
4252
If have mmap, and the request size meets the mmap threshold, and
4253
the system supports mmap, and there are few enough currently
4254
allocated mmapped regions, try to directly map this request
4255
rather than expanding top.
4258
if ((CHUNK_SIZE_T)(nb) >= (CHUNK_SIZE_T)(av->mmap_threshold) &&
4259
(av->n_mmaps < av->n_mmaps_max) &&
4260
!mmap_disabled(av)) {
4261
Void_t* mp = mmap_malloc(av, nb);
4263
return chunk2mem(mp);
4268
pagemask = av->pagesize - 1;
4270
/* Record incoming configuration of top */
4273
old_size = chunksize(old_top);
4274
old_end = (char*)(chunk_at_offset(old_top, old_size));
4276
brk = snd_brk = (char*)(MORECORE_FAILURE);
4279
If not the first time through, we require old_size to be
4280
at least MINSIZE and to have prev_inuse set.
4283
assert((old_top == (mchunkptr)(&(av->initial_top)) && old_size == 0) ||
4284
((CHUNK_SIZE_T) (old_size) >= MINSIZE &&
4285
prev_inuse(old_top)));
4287
/* Precondition: not enough current space to satisfy nb request */
4288
assert((CHUNK_SIZE_T)(old_size) < (CHUNK_SIZE_T)(nb + MINSIZE));
4290
/* Request enough space for nb + pad + overhead */
4292
size = nb + av->top_pad + MINSIZE;
4295
If contiguous, we can subtract out existing space that we hope to
4296
combine with new space. We add it back later only if
4297
we don't actually get contiguous space.
4304
Round to a multiple of page size.
4305
If MORECORE is not contiguous, this ensures that we only call it
4306
with whole-page arguments. And if MORECORE is contiguous and
4307
this is not first time through, this preserves page-alignment of
4308
previous calls. Otherwise, we correct to page-align below.
4311
size = (size + pagemask) & ~pagemask;
4314
Don't try to call MORECORE if argument is so big as to appear
4315
negative. Note that since mmap takes size_t arg, it may succeed
4316
below even if we cannot call MORECORE.
4320
brk = (char*)(MORECORE(size));
4323
If have mmap, try using it as a backup when MORECORE fails or
4324
cannot be used. This is worth doing on systems that have "holes" in
4325
address space, so sbrk cannot extend to give contiguous space, but
4326
space is available elsewhere. Note that we ignore mmap max count
4327
and threshold limits, since the space will not be used as a
4328
segregated mmap region.
4332
if (brk == (char*)(MORECORE_FAILURE)) {
4334
/* Cannot merge with old top, so add its size back in */
4336
size = (size + old_size + pagemask) & ~pagemask;
4338
/* If we are relying on mmap as backup, then use larger units */
4339
if ((CHUNK_SIZE_T)(size) < (CHUNK_SIZE_T)(MMAP_AS_MORECORE_SIZE))
4340
size = MMAP_AS_MORECORE_SIZE;
4342
/* Don't try if size wraps around 0 */
4343
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb)) {
4345
brk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
4347
if (brk != (char*)(MORECORE_FAILURE)) {
4349
/* We do not need, and cannot use, another sbrk call to find end */
4350
snd_brk = brk + size;
4353
Record that we no longer have a contiguous sbrk region.
4354
After the first time mmap is used as backup, we do not
4355
ever rely on contiguous space since this could incorrectly
4358
set_noncontiguous(av);
4364
if (brk != (char*)(MORECORE_FAILURE)) {
4365
av->sbrked_mem += size;
4368
If MORECORE extends previous space, we can likewise extend top size.
4371
if (brk == old_end && snd_brk == (char*)(MORECORE_FAILURE)) {
4372
set_head(old_top, (size + old_size) | PREV_INUSE);
4376
Otherwise, make adjustments:
4378
* If the first time through or noncontiguous, we need to call sbrk
4379
just to find out where the end of memory lies.
4381
* We need to ensure that all returned chunks from malloc will meet
4384
* If there was an intervening foreign sbrk, we need to adjust sbrk
4385
request size to account for fact that we will not be able to
4386
combine new space with existing space in old_top.
4388
* Almost all systems internally allocate whole pages at a time, in
4389
which case we might as well use the whole last page of request.
4390
So we allocate enough more memory to hit a page boundary now,
4391
which in turn causes future contiguous calls to page-align.
4401
If MORECORE returns an address lower than we have seen before,
4402
we know it isn't really contiguous. This and some subsequent
4403
checks help cope with non-conforming MORECORE functions and
4404
the presence of "foreign" calls to MORECORE from outside of
4405
malloc or by other threads. We cannot guarantee to detect
4406
these in all cases, but cope with the ones we do detect.
4408
if (contiguous(av) && old_size != 0 && brk < old_end) {
4409
set_noncontiguous(av);
4412
/* handle contiguous cases */
4413
if (contiguous(av)) {
4416
We can tolerate forward non-contiguities here (usually due
4417
to foreign calls) but treat them as part of our space for
4421
av->sbrked_mem += brk - old_end;
4423
/* Guarantee alignment of first new chunk made from this space */
4425
front_misalign = (INTERNAL_SIZE_T)chunk2mem(brk) & MALLOC_ALIGN_MASK;
4426
if (front_misalign > 0) {
4429
Skip over some bytes to arrive at an aligned position.
4430
We don't need to specially mark these wasted front bytes.
4431
They will never be accessed anyway because
4432
prev_inuse of av->top (and any chunk created from its start)
4433
is always true after initialization.
4436
correction = MALLOC_ALIGNMENT - front_misalign;
4437
aligned_brk += correction;
4441
If this isn't adjacent to existing space, then we will not
4442
be able to merge with old_top space, so must add to 2nd request.
4445
correction += old_size;
4447
/* Extend the end address to hit a page boundary */
4448
end_misalign = (INTERNAL_SIZE_T)(brk + size + correction);
4449
correction += ((end_misalign + pagemask) & ~pagemask) - end_misalign;
4451
assert(correction >= 0);
4452
snd_brk = (char*)(MORECORE(correction));
4454
if (snd_brk == (char*)(MORECORE_FAILURE)) {
4456
If can't allocate correction, try to at least find out current
4457
brk. It might be enough to proceed without failing.
4460
snd_brk = (char*)(MORECORE(0));
4462
else if (snd_brk < brk) {
4464
If the second call gives noncontiguous space even though
4465
it says it won't, the only course of action is to ignore
4466
results of second call, and conservatively estimate where
4467
the first call left us. Also set noncontiguous, so this
4468
won't happen again, leaving at most one hole.
4470
Note that this check is intrinsically incomplete. Because
4471
MORECORE is allowed to give more space than we ask for,
4472
there is no reliable way to detect a noncontiguity
4473
producing a forward gap for the second call.
4475
snd_brk = brk + size;
4477
set_noncontiguous(av);
4482
/* handle non-contiguous cases */
4484
/* MORECORE/mmap must correctly align */
4485
assert(aligned_OK(chunk2mem(brk)));
4487
/* Find out current end of memory */
4488
if (snd_brk == (char*)(MORECORE_FAILURE)) {
4489
snd_brk = (char*)(MORECORE(0));
4490
av->sbrked_mem += snd_brk - brk - size;
4494
/* Adjust top based on results of second sbrk */
4495
if (snd_brk != (char*)(MORECORE_FAILURE)) {
4496
av->top = (mchunkptr)aligned_brk;
4497
set_head(av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
4498
av->sbrked_mem += correction;
4501
If not the first time through, we either have a
4502
gap due to foreign sbrk or a non-contiguous region. Insert a
4503
double fencepost at old_top to prevent consolidation with space
4504
we don't own. These fenceposts are artificial chunks that are
4505
marked as inuse and are in any case too small to use. We need
4506
two to make sizes and alignments work out.
4509
if (old_size != 0) {
4511
Shrink old_top to insert fenceposts, keeping size a
4512
multiple of MALLOC_ALIGNMENT. We know there is at least
4513
enough space in old_top to do this.
4515
old_size = (old_size - 3*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
4516
set_head(old_top, old_size | PREV_INUSE);
4519
Note that the following assignments completely overwrite
4520
old_top when old_size was previously MINSIZE. This is
4521
intentional. We need the fencepost, even if old_top
4522
otherwise gets lost.
4524
chunk_at_offset(old_top, old_size )->size =
4527
chunk_at_offset(old_top, old_size + SIZE_SZ)->size =
4531
If possible, release the rest, suppressing trimming.
4533
if (old_size >= MINSIZE) {
4534
unsigned int mprops = av->sysctl;
4536
fREe(chunk2mem(old_top));
4537
av->sysctl = mprops;
4543
/* Update statistics */
4544
sum = av->sbrked_mem;
4545
if (sum > (CHUNK_SIZE_T)(av->max_sbrked_mem))
4546
av->max_sbrked_mem = sum;
4548
sum += av->mmapped_mem;
4549
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
4550
av->max_total_mem = sum;
4553
/* finally, do the allocation */
4556
size = chunksize(p);
4558
/* check that one of the above allocation paths succeeded */
4559
if ((CHUNK_SIZE_T)(size) >= (CHUNK_SIZE_T)(nb + MINSIZE)) {
4560
remainder_size = size - nb;
4561
remainder = chunk_at_offset(p, nb);
4562
av->top = remainder;
4563
set_head(p, nb | PREV_INUSE);
4564
set_head(remainder, remainder_size | PREV_INUSE);
4565
check_malloced_chunk(p, nb);
4566
check_malloc_state(av);
4567
return chunk2mem(p);
4572
/* catch all failure paths */
4573
check_malloc_state(av);
4574
MALLOC_FAILURE_ACTION;
4580
systrim is an inverse of sorts to sysmalloc. It gives memory back
4581
to the system (via negative arguments to sbrk) if there is unused
4582
memory at the `high' end of the malloc pool. It is called
4583
automatically by free() when top space exceeds the trim
4584
threshold. It is also called by the public malloc_trim routine. It
4585
returns 1 if it actually released any memory, else 0.
4588
static int systrim(mstate av, size_t pad) {
4589
long top_size; /* Amount of top-most memory */
4590
long extra; /* Amount to release */
4591
long released; /* Amount actually released */
4592
char* current_brk; /* address returned by pre-check sbrk call */
4593
char* new_brk; /* address returned by post-check sbrk call */
4596
ensure_initialization(av);
4598
if (have_fastchunks(av))
4599
malloc_consolidate(av, MAX_CHUNK_SIZE, MAX_CHUNK_SIZE);
4601
if (!trim_disabled(av)) {
4603
#ifndef MORECORE_CANNOT_TRIM
4605
pagesz = av->pagesize;
4606
top_size = chunksize(av->top);
4608
/* Release in pagesize units, keeping at least one page */
4609
extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
4614
Only proceed if end of memory is where we last set it.
4615
This avoids problems if there were foreign sbrk calls.
4617
current_brk = (char*)(MORECORE(0));
4618
if (current_brk == (char*)(av->top) + top_size) {
4621
Attempt to release memory. We ignore MORECORE return value,
4622
and instead call again to find out where new end of memory is.
4623
This avoids problems if first call releases less than we asked,
4624
of if failure somehow altered brk value. (We could still
4625
encounter problems if it altered brk in some very bad way,
4626
but the only thing we can do is adjust anyway, which will cause
4627
some downstream failure.)
4631
new_brk = (char*)(MORECORE(0));
4633
if (new_brk != (char*)MORECORE_FAILURE) {
4634
released = (long)(current_brk - new_brk);
4636
if (released != 0) {
4637
/* Success. Adjust top. */
4638
av->sbrked_mem -= released;
4639
set_head(av->top, (top_size - released) | PREV_INUSE);
4640
check_malloc_state(av);
4653
-------------------- Alternative MORECORE functions --------------------
4658
General Requirements for MORECORE.
4660
The MORECORE function must have the following properties:
4662
If MORECORE_CONTIGUOUS is false:
4664
* MORECORE must allocate in multiples of pagesize. It will
4665
only be called with arguments that are multiples of pagesize.
4667
* MORECORE(0) must return an address that is at least
4668
MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
4670
else (i.e. If MORECORE_CONTIGUOUS is true):
4672
* Consecutive calls to MORECORE with positive arguments
4673
return increasing addresses, indicating that space has been
4674
contiguously extended.
4676
* MORECORE need not allocate in multiples of pagesize.
4677
Calls to MORECORE need not have args of multiples of pagesize.
4679
* MORECORE need not page-align.
4683
* MORECORE may allocate more memory than requested. (Or even less,
4684
but this will generally result in a malloc failure.)
4686
* MORECORE must not allocate memory when given argument zero, but
4687
instead return one past the end address of memory from previous
4688
nonzero call. This malloc does NOT call MORECORE(0)
4689
until at least one call with positive arguments is made, so
4690
the initial value returned is not important.
4692
* Even though consecutive calls to MORECORE need not return contiguous
4693
addresses, it must be OK for malloc'ed chunks to span multiple
4694
regions in those cases where they do happen to be contiguous.
4696
* MORECORE need not handle negative arguments -- it may instead
4697
just return MORECORE_FAILURE when given negative arguments.
4698
Negative arguments are always multiples of pagesize. MORECORE
4699
must not misinterpret negative args as large positive unsigned
4700
args. You can suppress all such calls from even occurring by defining
4701
MORECORE_CANNOT_TRIM,
4703
There is some variation across systems about the type of the
4704
argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
4705
actually be size_t, because sbrk supports negative args, so it is
4706
normally the signed type of the same width as size_t (sometimes
4707
declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much
4708
matter though. Internally, we use "long" as arguments, which should
4709
work across all reasonable possibilities.
4711
Additionally, if MORECORE ever returns failure for a positive
4712
request, and HAVE_MMAP is true, then mmap is used as a noncontiguous
4713
system allocator. This is a useful backup strategy for systems with
4714
holes in address spaces -- in this case sbrk cannot contiguously
4715
expand the heap, but mmap may be able to map noncontiguous space.
4717
If you'd like mmap to ALWAYS be used, you can define MORECORE to be
4718
a function that always returns MORECORE_FAILURE.
4720
Malloc only has limited ability to detect failures of MORECORE
4721
to supply contiguous space when it says it can. In particular,
4722
multithreaded programs that do not use locks may result in
4723
rece conditions across calls to MORECORE that result in gaps
4724
that cannot be detected as such, and subsequent corruption.
4726
If you are using this malloc with something other than sbrk (or its
4727
emulation) to supply memory regions, you probably want to set
4728
MORECORE_CONTIGUOUS as false. As an example, here is a custom
4729
allocator kindly contributed for pre-OSX macOS. It uses virtually
4730
but not necessarily physically contiguous non-paged memory (locked
4731
in, present and won't get swapped out). You can use it by
4732
uncommenting this section, adding some #includes, and setting up the
4733
appropriate defines above:
4735
#define MORECORE osMoreCore
4736
#define MORECORE_CONTIGUOUS 0
4738
There is also a shutdown routine that should somehow be called for
4739
cleanup upon program exit.
4741
#define MAX_POOL_ENTRIES 100
4742
#define MINIMUM_MORECORE_SIZE (64 * 1024)
4743
static int next_os_pool;
4744
void *our_os_pools[MAX_POOL_ENTRIES];
4746
void *osMoreCore(int size)
4749
static void *sbrk_top = 0;
4753
if (size < MINIMUM_MORECORE_SIZE)
4754
size = MINIMUM_MORECORE_SIZE;
4755
if (CurrentExecutionLevel() == kTaskLevel)
4756
ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4759
return (void *) MORECORE_FAILURE;
4761
// save ptrs so they can be freed during cleanup
4762
our_os_pools[next_os_pool] = ptr;
4764
ptr = (void *) ((((CHUNK_SIZE_T) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4765
sbrk_top = (char *) ptr + size;
4770
// we don't currently support shrink behavior
4771
return (void *) MORECORE_FAILURE;
4779
// cleanup any allocated memory pools
4780
// called as last thing before shutting down driver
4782
void osCleanupMem(void)
4786
for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4789
PoolDeallocate(*ptr);
4798
--------------------------------------------------------------
4800
Emulation of sbrk for win32.
4801
Donated by J. Walter <Walter@GeNeSys-e.de>.
4802
For additional information about this code, and malloc on Win32, see
4803
http://www.genesys-e.de/jwalter/
4813
/* Support for USE_MALLOC_LOCK */
4814
#ifdef USE_MALLOC_LOCK
4816
/* Wait for spin lock */
4817
static int slwait (int *sl) {
4818
while (InterlockedCompareExchange ((void **) sl, (void *) 1, (void *) 0) != 0)
4823
/* Release spin lock */
4824
static int slrelease (int *sl) {
4825
InterlockedExchange (sl, 0);
4830
/* Spin lock for emulation code */
4834
#endif /* USE_MALLOC_LOCK */
4836
/* getpagesize for windows */
4837
static long getpagesize (void) {
4838
static long g_pagesize = 0;
4840
SYSTEM_INFO system_info;
4841
GetSystemInfo (&system_info);
4842
g_pagesize = system_info.dwPageSize;
4846
static long getregionsize (void) {
4847
static long g_regionsize = 0;
4848
if (! g_regionsize) {
4849
SYSTEM_INFO system_info;
4850
GetSystemInfo (&system_info);
4851
g_regionsize = system_info.dwAllocationGranularity;
4853
return g_regionsize;
4856
/* A region list entry */
4857
typedef struct _region_list_entry {
4858
void *top_allocated;
4859
void *top_committed;
4862
struct _region_list_entry *previous;
4863
} region_list_entry;
4865
/* Allocate and link a region entry in the region list */
4866
static int region_list_append (region_list_entry **last, void *base_reserved, long reserve_size) {
4867
region_list_entry *next = HeapAlloc (GetProcessHeap (), 0, sizeof (region_list_entry));
4870
next->top_allocated = (char *) base_reserved;
4871
next->top_committed = (char *) base_reserved;
4872
next->top_reserved = (char *) base_reserved + reserve_size;
4873
next->reserve_size = reserve_size;
4874
next->previous = *last;
4878
/* Free and unlink the last region entry from the region list */
4879
static int region_list_remove (region_list_entry **last) {
4880
region_list_entry *previous = (*last)->previous;
4881
if (! HeapFree (GetProcessHeap (), sizeof (region_list_entry), *last))
4887
#define CEIL(size,to) (((size)+(to)-1)&~((to)-1))
4888
#define FLOOR(size,to) ((size)&~((to)-1))
4890
#define SBRK_SCALE 0
4891
/* #define SBRK_SCALE 1 */
4892
/* #define SBRK_SCALE 2 */
4893
/* #define SBRK_SCALE 4 */
4895
/* sbrk for windows */
4896
static void *sbrk (long size) {
4897
static long g_pagesize, g_my_pagesize;
4898
static long g_regionsize, g_my_regionsize;
4899
static region_list_entry *g_last;
4900
void *result = (void *) MORECORE_FAILURE;
4902
printf ("sbrk %d\n", size);
4904
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
4905
/* Wait for spin lock */
4908
/* First time initialization */
4910
g_pagesize = getpagesize ();
4911
g_my_pagesize = g_pagesize << SBRK_SCALE;
4913
if (! g_regionsize) {
4914
g_regionsize = getregionsize ();
4915
g_my_regionsize = g_regionsize << SBRK_SCALE;
4918
if (! region_list_append (&g_last, 0, 0))
4921
/* Assert invariants */
4923
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_allocated &&
4924
g_last->top_allocated <= g_last->top_committed);
4925
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_committed &&
4926
g_last->top_committed <= g_last->top_reserved &&
4927
(unsigned) g_last->top_committed % g_pagesize == 0);
4928
assert ((unsigned) g_last->top_reserved % g_regionsize == 0);
4929
assert ((unsigned) g_last->reserve_size % g_regionsize == 0);
4930
/* Allocation requested? */
4932
/* Allocation size is the requested size */
4933
long allocate_size = size;
4934
/* Compute the size to commit */
4935
long to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
4936
/* Do we reach the commit limit? */
4937
if (to_commit > 0) {
4938
/* Round size to commit */
4939
long commit_size = CEIL (to_commit, g_my_pagesize);
4940
/* Compute the size to reserve */
4941
long to_reserve = (char *) g_last->top_committed + commit_size - (char *) g_last->top_reserved;
4942
/* Do we reach the reserve limit? */
4943
if (to_reserve > 0) {
4944
/* Compute the remaining size to commit in the current region */
4945
long remaining_commit_size = (char *) g_last->top_reserved - (char *) g_last->top_committed;
4946
if (remaining_commit_size > 0) {
4947
/* Assert preconditions */
4948
assert ((unsigned) g_last->top_committed % g_pagesize == 0);
4949
assert (0 < remaining_commit_size && remaining_commit_size % g_pagesize == 0); {
4951
void *base_committed = VirtualAlloc (g_last->top_committed, remaining_commit_size,
4952
MEM_COMMIT, PAGE_READWRITE);
4953
/* Check returned pointer for consistency */
4954
if (base_committed != g_last->top_committed)
4956
/* Assert postconditions */
4957
assert ((unsigned) base_committed % g_pagesize == 0);
4959
printf ("Commit %p %d\n", base_committed, remaining_commit_size);
4961
/* Adjust the regions commit top */
4962
g_last->top_committed = (char *) base_committed + remaining_commit_size;
4965
/* Now we are going to search and reserve. */
4966
int contiguous = -1;
4968
MEMORY_BASIC_INFORMATION memory_info;
4969
void *base_reserved;
4972
/* Assume contiguous memory */
4974
/* Round size to reserve */
4975
reserve_size = CEIL (to_reserve, g_my_regionsize);
4976
/* Start with the current region's top */
4977
memory_info.BaseAddress = g_last->top_reserved;
4978
/* Assert preconditions */
4979
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
4980
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
4981
while (VirtualQuery (memory_info.BaseAddress, &memory_info, sizeof (memory_info))) {
4982
/* Assert postconditions */
4983
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
4985
printf ("Query %p %d %s\n", memory_info.BaseAddress, memory_info.RegionSize,
4986
memory_info.State == MEM_FREE ? "FREE":
4987
(memory_info.State == MEM_RESERVE ? "RESERVED":
4988
(memory_info.State == MEM_COMMIT ? "COMMITTED": "?")));
4990
/* Region is free, well aligned and big enough: we are done */
4991
if (memory_info.State == MEM_FREE &&
4992
(unsigned) memory_info.BaseAddress % g_regionsize == 0 &&
4993
memory_info.RegionSize >= (unsigned) reserve_size) {
4997
/* From now on we can't get contiguous memory! */
4999
/* Recompute size to reserve */
5000
reserve_size = CEIL (allocate_size, g_my_regionsize);
5001
memory_info.BaseAddress = (char *) memory_info.BaseAddress + memory_info.RegionSize;
5002
/* Assert preconditions */
5003
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
5004
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
5006
/* Search failed? */
5009
/* Assert preconditions */
5010
assert ((unsigned) memory_info.BaseAddress % g_regionsize == 0);
5011
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
5012
/* Try to reserve this */
5013
base_reserved = VirtualAlloc (memory_info.BaseAddress, reserve_size,
5014
MEM_RESERVE, PAGE_NOACCESS);
5015
if (! base_reserved) {
5016
int rc = GetLastError ();
5017
if (rc != ERROR_INVALID_ADDRESS)
5020
/* A null pointer signals (hopefully) a race condition with another thread. */
5021
/* In this case, we try again. */
5022
} while (! base_reserved);
5023
/* Check returned pointer for consistency */
5024
if (memory_info.BaseAddress && base_reserved != memory_info.BaseAddress)
5026
/* Assert postconditions */
5027
assert ((unsigned) base_reserved % g_regionsize == 0);
5029
printf ("Reserve %p %d\n", base_reserved, reserve_size);
5031
/* Did we get contiguous memory? */
5033
long start_size = (char *) g_last->top_committed - (char *) g_last->top_allocated;
5034
/* Adjust allocation size */
5035
allocate_size -= start_size;
5036
/* Adjust the regions allocation top */
5037
g_last->top_allocated = g_last->top_committed;
5038
/* Recompute the size to commit */
5039
to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
5040
/* Round size to commit */
5041
commit_size = CEIL (to_commit, g_my_pagesize);
5043
/* Append the new region to the list */
5044
if (! region_list_append (&g_last, base_reserved, reserve_size))
5046
/* Didn't we get contiguous memory? */
5048
/* Recompute the size to commit */
5049
to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
5050
/* Round size to commit */
5051
commit_size = CEIL (to_commit, g_my_pagesize);
5055
/* Assert preconditions */
5056
assert ((unsigned) g_last->top_committed % g_pagesize == 0);
5057
assert (0 < commit_size && commit_size % g_pagesize == 0); {
5059
void *base_committed = VirtualAlloc (g_last->top_committed, commit_size,
5060
MEM_COMMIT, PAGE_READWRITE);
5061
/* Check returned pointer for consistency */
5062
if (base_committed != g_last->top_committed)
5064
/* Assert postconditions */
5065
assert ((unsigned) base_committed % g_pagesize == 0);
5067
printf ("Commit %p %d\n", base_committed, commit_size);
5069
/* Adjust the regions commit top */
5070
g_last->top_committed = (char *) base_committed + commit_size;
5073
/* Adjust the regions allocation top */
5074
g_last->top_allocated = (char *) g_last->top_allocated + allocate_size;
5075
result = (char *) g_last->top_allocated - size;
5076
/* Deallocation requested? */
5077
} else if (size < 0) {
5078
long deallocate_size = - size;
5079
/* As long as we have a region to release */
5080
while ((char *) g_last->top_allocated - deallocate_size < (char *) g_last->top_reserved - g_last->reserve_size) {
5081
/* Get the size to release */
5082
long release_size = g_last->reserve_size;
5083
/* Get the base address */
5084
void *base_reserved = (char *) g_last->top_reserved - release_size;
5085
/* Assert preconditions */
5086
assert ((unsigned) base_reserved % g_regionsize == 0);
5087
assert (0 < release_size && release_size % g_regionsize == 0); {
5089
int rc = VirtualFree (base_reserved, 0,
5091
/* Check returned code for consistency */
5095
printf ("Release %p %d\n", base_reserved, release_size);
5098
/* Adjust deallocation size */
5099
deallocate_size -= (char *) g_last->top_allocated - (char *) base_reserved;
5100
/* Remove the old region from the list */
5101
if (! region_list_remove (&g_last))
5104
/* Compute the size to decommit */
5105
long to_decommit = (char *) g_last->top_committed - ((char *) g_last->top_allocated - deallocate_size);
5106
if (to_decommit >= g_my_pagesize) {
5107
/* Compute the size to decommit */
5108
long decommit_size = FLOOR (to_decommit, g_my_pagesize);
5109
/* Compute the base address */
5110
void *base_committed = (char *) g_last->top_committed - decommit_size;
5111
/* Assert preconditions */
5112
assert ((unsigned) base_committed % g_pagesize == 0);
5113
assert (0 < decommit_size && decommit_size % g_pagesize == 0); {
5115
int rc = VirtualFree ((char *) base_committed, decommit_size,
5117
/* Check returned code for consistency */
5121
printf ("Decommit %p %d\n", base_committed, decommit_size);
5124
/* Adjust deallocation size and regions commit and allocate top */
5125
deallocate_size -= (char *) g_last->top_allocated - (char *) base_committed;
5126
g_last->top_committed = base_committed;
5127
g_last->top_allocated = base_committed;
5130
/* Adjust regions allocate top */
5131
g_last->top_allocated = (char *) g_last->top_allocated - deallocate_size;
5132
/* Check for underflow */
5133
if ((char *) g_last->top_reserved - g_last->reserve_size > (char *) g_last->top_allocated ||
5134
g_last->top_allocated > g_last->top_committed) {
5135
/* Adjust regions allocate top */
5136
g_last->top_allocated = (char *) g_last->top_reserved - g_last->reserve_size;
5139
result = g_last->top_allocated;
5141
/* Assert invariants */
5143
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_allocated &&
5144
g_last->top_allocated <= g_last->top_committed);
5145
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_committed &&
5146
g_last->top_committed <= g_last->top_reserved &&
5147
(unsigned) g_last->top_committed % g_pagesize == 0);
5148
assert ((unsigned) g_last->top_reserved % g_regionsize == 0);
5149
assert ((unsigned) g_last->reserve_size % g_regionsize == 0);
5152
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5153
/* Release spin lock */
5159
/* mmap for windows */
5160
static void *mmap (void *ptr, long size, long prot, long type, long handle, long arg) {
5161
static long g_pagesize;
5162
static long g_regionsize;
5164
printf ("mmap %d\n", size);
5166
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5167
/* Wait for spin lock */
5170
/* First time initialization */
5172
g_pagesize = getpagesize ();
5174
g_regionsize = getregionsize ();
5175
/* Assert preconditions */
5176
assert ((unsigned) ptr % g_regionsize == 0);
5177
assert (size % g_pagesize == 0);
5179
ptr = VirtualAlloc (ptr, size,
5180
MEM_RESERVE | MEM_COMMIT | MEM_TOP_DOWN, PAGE_READWRITE);
5182
ptr = (void *) MORECORE_FAILURE;
5185
/* Assert postconditions */
5186
assert ((unsigned) ptr % g_regionsize == 0);
5188
printf ("Commit %p %d\n", ptr, size);
5191
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5192
/* Release spin lock */
5198
/* munmap for windows */
5199
static long munmap (void *ptr, long size) {
5200
static long g_pagesize;
5201
static long g_regionsize;
5202
int rc = MUNMAP_FAILURE;
5204
printf ("munmap %p %d\n", ptr, size);
5206
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5207
/* Wait for spin lock */
5210
/* First time initialization */
5212
g_pagesize = getpagesize ();
5214
g_regionsize = getregionsize ();
5215
/* Assert preconditions */
5216
assert ((unsigned) ptr % g_regionsize == 0);
5217
assert (size % g_pagesize == 0);
5219
if (! VirtualFree (ptr, 0,
5224
printf ("Release %p %d\n", ptr, size);
5227
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5228
/* Release spin lock */
5234
static void vminfo (CHUNK_SIZE_T *free, CHUNK_SIZE_T *reserved, CHUNK_SIZE_T *committed) {
5235
MEMORY_BASIC_INFORMATION memory_info;
5236
memory_info.BaseAddress = 0;
5237
*free = *reserved = *committed = 0;
5238
while (VirtualQuery (memory_info.BaseAddress, &memory_info, sizeof (memory_info))) {
5239
switch (memory_info.State) {
5241
*free += memory_info.RegionSize;
5244
*reserved += memory_info.RegionSize;
5247
*committed += memory_info.RegionSize;
5250
memory_info.BaseAddress = (char *) memory_info.BaseAddress + memory_info.RegionSize;
5254
static int cpuinfo (int whole, CHUNK_SIZE_T *kernel, CHUNK_SIZE_T *user) {
5256
__int64 creation64, exit64, kernel64, user64;
5257
int rc = GetProcessTimes (GetCurrentProcess (),
5258
(FILETIME *) &creation64,
5259
(FILETIME *) &exit64,
5260
(FILETIME *) &kernel64,
5261
(FILETIME *) &user64);
5267
*kernel = (CHUNK_SIZE_T) (kernel64 / 10000);
5268
*user = (CHUNK_SIZE_T) (user64 / 10000);
5271
__int64 creation64, exit64, kernel64, user64;
5272
int rc = GetThreadTimes (GetCurrentThread (),
5273
(FILETIME *) &creation64,
5274
(FILETIME *) &exit64,
5275
(FILETIME *) &kernel64,
5276
(FILETIME *) &user64);
5282
*kernel = (CHUNK_SIZE_T) (kernel64 / 10000);
5283
*user = (CHUNK_SIZE_T) (user64 / 10000);
5290
/* ------------------------------------------------------------
5292
V2.8.0 (not yet released)
5293
* Use trees for non-small bins
5294
Also requiring different size->bin algorithm
5296
V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
5297
* Allow tuning of FIRST_SORTED_BIN_SIZE
5298
* Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
5299
* Better detection and support for non-contiguousness of MORECORE.
5300
Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
5301
* Bypass most of malloc if no frees. Thanks To Emery Berger.
5302
* Fix freeing of old top non-contiguous chunk im sysmalloc.
5303
* Raised default trim and map thresholds to 256K.
5304
* Fix mmap-related #defines. Thanks to Lubos Lunak.
5305
* Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
5306
* Branch-free bin calculation
5307
* Default trim and mmap thresholds now 256K.
5309
V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
5310
* Introduce independent_comalloc and independent_calloc.
5311
Thanks to Michael Pachos for motivation and help.
5312
* Make optional .h file available
5313
* Allow > 2GB requests on 32bit systems.
5314
* new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
5315
Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
5317
* Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
5319
* memalign: check alignment arg
5320
* realloc: don't try to shift chunks backwards, since this
5321
leads to more fragmentation in some programs and doesn't
5322
seem to help in any others.
5323
* Collect all cases in malloc requiring system memory into sysmalloc
5324
* Use mmap as backup to sbrk
5325
* Place all internal state in malloc_state
5326
* Introduce fastbins (although similar to 2.5.1)
5327
* Many minor tunings and cosmetic improvements
5328
* Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
5329
* Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
5330
Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
5331
* Include errno.h to support default failure action.
5333
V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
5334
* return null for negative arguments
5335
* Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5336
* Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5337
(e.g. WIN32 platforms)
5338
* Cleanup header file inclusion for WIN32 platforms
5339
* Cleanup code to avoid Microsoft Visual C++ compiler complaints
5340
* Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5341
memory allocation routines
5342
* Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5343
* Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5344
usage of 'assert' in non-WIN32 code
5345
* Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5347
* Always call 'fREe()' rather than 'free()'
5349
V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
5350
* Fixed ordering problem with boundary-stamping
5352
V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
5353
* Added pvalloc, as recommended by H.J. Liu
5354
* Added 64bit pointer support mainly from Wolfram Gloger
5355
* Added anonymously donated WIN32 sbrk emulation
5356
* Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5357
* malloc_extend_top: fix mask error that caused wastage after
5359
* Add linux mremap support code from HJ Liu
5361
V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
5362
* Integrated most documentation with the code.
5363
* Add support for mmap, with help from
5364
Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5365
* Use last_remainder in more cases.
5366
* Pack bins using idea from colin@nyx10.cs.du.edu
5367
* Use ordered bins instead of best-fit threshhold
5368
* Eliminate block-local decls to simplify tracing and debugging.
5369
* Support another case of realloc via move into top
5370
* Fix error occuring when initial sbrk_base not word-aligned.
5371
* Rely on page size for units instead of SBRK_UNIT to
5372
avoid surprises about sbrk alignment conventions.
5373
* Add mallinfo, mallopt. Thanks to Raymond Nijssen
5374
(raymond@es.ele.tue.nl) for the suggestion.
5375
* Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5376
* More precautions for cases where other routines call sbrk,
5377
courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5378
* Added macros etc., allowing use in linux libc from
5379
H.J. Lu (hjl@gnu.ai.mit.edu)
5380
* Inverted this history list
5382
V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
5383
* Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5384
* Removed all preallocation code since under current scheme
5385
the work required to undo bad preallocations exceeds
5386
the work saved in good cases for most test programs.
5387
* No longer use return list or unconsolidated bins since
5388
no scheme using them consistently outperforms those that don't
5389
given above changes.
5390
* Use best fit for very large chunks to prevent some worst-cases.
5391
* Added some support for debugging
5393
V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
5394
* Removed footers when chunks are in use. Thanks to
5395
Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5397
V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
5398
* Added malloc_trim, with help from Wolfram Gloger
5399
(wmglo@Dent.MED.Uni-Muenchen.DE).
5401
V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
5403
V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
5404
* realloc: try to expand in both directions
5405
* malloc: swap order of clean-bin strategy;
5406
* realloc: only conditionally expand backwards
5407
* Try not to scavenge used bins
5408
* Use bin counts as a guide to preallocation
5409
* Occasionally bin return list chunks in first scan
5410
* Add a few optimizations from colin@nyx10.cs.du.edu
5412
V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
5413
* faster bin computation & slightly different binning
5414
* merged all consolidations to one part of malloc proper
5415
(eliminating old malloc_find_space & malloc_clean_bin)
5416
* Scan 2 returns chunks (not just 1)
5417
* Propagate failure in realloc if malloc returns 0
5418
* Add stuff to allow compilation on non-ANSI compilers
5419
from kpv@research.att.com
5421
V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
5422
* removed potential for odd address access in prev_chunk
5423
* removed dependency on getpagesize.h
5424
* misc cosmetics and a bit more internal documentation
5425
* anticosmetics: mangled names in macros to evade debugger strangeness
5426
* tested on sparc, hp-700, dec-mips, rs6000
5427
with gcc & native cc (hp, dec only) allowing
5428
Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5430
Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
5431
* Based loosely on libg++-1.2X malloc. (It retains some of the overall
5432
structure of old version, but most details differ.)