« back to all changes in this revision
Viewing changes to test/malloc-pre2.8a.c
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Bazaar Package Importer
- Author(s): Troy Heber
- Date: 2005-03-22 06:55:53 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20050322065553-syjpkd48r4re18dn
Tags: 1.0.1-5
* Moving LGPL link in copyright back to LGPL-2.1
* Cleanup of debian/rules: removed explicit refs to 32-bit archs, removed
unnecessary nostrip, using --man dir to install man pages, moving from
dh_movefiles to dh_install.
- files added:
- AUTHORS
- autom4te.cache
- doc/man
- doc/man/man3
- src/JudyHS
- src/obj
- test/Centrino_1.3Mhz_Plots
- files removed:
- Makefile.multi
- make_includes
- test/manual
- files modified:
- COPYING
added
removed
test/malloc-pre2.8a.c
1
/*
2
[insert usage description etc here]
3
4
preliminary version 2.8.x
5
*/
6
7
/*
8
WIN32 sets up defaults for MS environment and compilers.
9
Otherwise defaults are for unix.
10
*/
11
12
/* #define WIN32 */
13
14
#ifdef WIN32
15
16
#define WIN32_LEAN_AND_MEAN
17
#include <windows.h>
18
19
/* No-op failure action */
20
#define MALLOC_FAILURE_ACTION
21
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
26
27
/* Use the supplied emulation of sbrk */
28
#define MORECORE sbrk
29
#define MORECORE_CONTIGUOUS 1
30
#define MORECORE_FAILURE ((void*)(-1))
31
32
/* Use the supplied emulation of mmap and munmap */
33
#define HAVE_MMAP 1
34
#define MUNMAP_FAILURE (-1)
35
#define MMAP_CLEARS 1
36
37
/* These values don't really matter in windows mmap emulation */
38
#define MAP_PRIVATE 1
39
#define MAP_ANONYMOUS 2
40
#define PROT_READ 1
41
#define PROT_WRITE 2
42
43
/* Emulation functions defined at the end of this file */
44
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);
49
#endif
50
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);
56
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);
59
60
#endif
61
62
63
#include <strings.h>
64
65
/*
66
Void_t* is the pointer type that malloc should say it returns
67
*/
68
69
#ifndef Void_t
70
#define Void_t void
71
#endif /*Void_t*/
72
73
#include <stddef.h> /* for size_t */
74
75
#ifdef __cplusplus
76
extern "C" {
77
#endif
78
79
/* define LACKS_UNISTD_H if your system does not have a <unistd.h>. */
80
81
/* #define LACKS_UNISTD_H */
82
83
#ifndef LACKS_UNISTD_H
84
#include <unistd.h>
85
#endif
86
87
/* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. */
88
89
/* #define LACKS_SYS_PARAM_H */
90
91
92
#include <stdio.h> /* needed for malloc_stats */
93
#include <errno.h> /* needed for optional MALLOC_FAILURE_ACTION */
94
95
96
/*
97
Debugging:
98
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.
103
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.)
113
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.
117
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.
122
*/
123
124
#if DEBUG
125
#include <assert.h>
126
/* #define assert(x) if(!(x)) abort() */
127
128
#else
129
#define assert(x) ((void)0)
130
#endif
131
132
/*
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.
135
*/
136
137
#ifndef CHUNK_SIZE_T
138
#define CHUNK_SIZE_T unsigned long
139
#endif
140
141
#define MAX_CHUNK_SIZE ((CHUNK_SIZE_T)(-1UL))
142
143
/*
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.
147
*/
148
#ifndef PTR_UINT
149
#define PTR_UINT unsigned long
150
#endif
151
152
153
/*
154
INTERNAL_SIZE_T is the word-size used for internal bookkeeping
155
of chunk sizes.
156
157
The default version is the same as size_t.
158
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.
162
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.
170
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
181
on some systems.
182
*/
183
184
#ifndef INTERNAL_SIZE_T
185
#define INTERNAL_SIZE_T size_t
186
#endif
187
188
/* The corresponding word size */
189
#define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
190
191
192
193
/*
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.
199
*/
200
201
202
#ifndef MALLOC_ALIGNMENT
203
#define MALLOC_ALIGNMENT (2 * SIZE_SZ)
204
#endif
205
206
/* The corresponding bit mask value */
207
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
208
209
210
211
/*
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).
216
*/
217
218
/* #define REALLOC_ZERO_BYTES_FREES */
219
220
/*
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
224
of small chunks.
225
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
233
fastbins.
234
*/
235
236
#ifndef TRIM_FASTBINS
237
#define TRIM_FASTBINS 0
238
#endif
239
240
241
/*
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.
245
*/
246
247
/* #define USE_DL_PREFIX */
248
249
250
/*
251
USE_MALLOC_LOCK causes wrapper functions to surround each
252
callable routine with pthread mutex lock/unlock.
253
254
USE_MALLOC_LOCK forces USE_PUBLIC_MALLOC_WRAPPERS to be defined
255
*/
256
257
/* #define USE_MALLOC_LOCK */
258
259
260
/*
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.
268
*/
269
270
#ifdef USE_MALLOC_LOCK
271
#define USE_PUBLIC_MALLOC_WRAPPERS
272
#else
273
/* #define USE_PUBLIC_MALLOC_WRAPPERS */
274
#endif
275
276
277
/*
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.
282
*/
283
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
300
#endif
301
302
#ifdef USE_DL_PREFIX
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 */
335
336
337
/*
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.
342
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.
346
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.
349
*/
350
351
#define HAVE_MEMCPY
352
353
#ifndef USE_MEMCPY
354
#ifdef HAVE_MEMCPY
355
#define USE_MEMCPY 1
356
#else
357
#define USE_MEMCPY 0
358
#endif
359
#endif
360
361
362
#if (defined(HAVE_MEMCPY))
363
#ifdef WIN32
364
/* On Win32 memset and memcpy are already declared in windows.h */
365
#else
366
void* memset(void*, int, size_t);
367
void* memcpy(void*, const void*, size_t);
368
#endif
369
#endif
370
371
/*
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.
375
376
By default, sets errno if running on STD_C platform, else does nothing.
377
*/
378
379
#ifndef MALLOC_FAILURE_ACTION
380
#define MALLOC_FAILURE_ACTION \
381
errno = ENOMEM;
382
#endif
383
384
/*
385
MORECORE-related declarations. By default, rely on sbrk
386
*/
387
388
389
#ifdef LACKS_UNISTD_H
390
#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
391
extern Void_t* sbrk(ptrdiff_t);
392
#endif
393
#endif
394
395
/*
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.
400
*/
401
402
#ifndef MORECORE
403
#define MORECORE sbrk
404
#endif
405
406
/*
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
410
try to redefine it.
411
*/
412
413
#ifndef MORECORE_FAILURE
414
#define MORECORE_FAILURE (-1)
415
#endif
416
417
/*
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.
425
*/
426
427
#ifndef MORECORE_CONTIGUOUS
428
#define MORECORE_CONTIGUOUS 1
429
#endif
430
431
/*
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.
436
*/
437
438
/* #define MORECORE_CANNOT_TRIM */
439
440
441
/*
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.
447
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.
451
*/
452
453
#define HAVE_MMAP 0
454
455
#ifndef HAVE_MMAP
456
#define HAVE_MMAP 1
457
#endif
458
459
#if HAVE_MMAP
460
/*
461
Standard unix mmap using /dev/zero clears memory so calloc doesn't
462
need to.
463
*/
464
465
#ifndef MMAP_CLEARS
466
#define MMAP_CLEARS 1
467
#endif
468
469
#else /* no mmap */
470
#ifndef MMAP_CLEARS
471
#define MMAP_CLEARS 0
472
#endif
473
#endif
474
475
476
/*
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
487
of kernel resources.
488
*/
489
490
#ifndef MMAP_AS_MORECORE_SIZE
491
#define MMAP_AS_MORECORE_SIZE (1024 * 1024)
492
#endif
493
494
/*
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.
498
*/
499
500
#ifndef HAVE_MREMAP
501
#ifdef linux
502
#define HAVE_MREMAP 1
503
#else
504
#define HAVE_MREMAP 0
505
#endif
506
507
#endif /* HAVE_MMAP */
508
509
510
/*
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.
515
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.
520
*/
521
522
#ifndef malloc_getpagesize
523
524
#ifndef LACKS_UNISTD_H
525
# include <unistd.h>
526
#endif
527
528
# ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
529
# ifndef _SC_PAGE_SIZE
530
# define _SC_PAGE_SIZE _SC_PAGESIZE
531
# endif
532
# endif
533
534
# ifdef _SC_PAGE_SIZE
535
# define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
536
# else
537
# if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
538
extern size_t getpagesize();
539
# define malloc_getpagesize getpagesize()
540
# else
541
# ifdef WIN32 /* use supplied emulation of getpagesize */
542
# define malloc_getpagesize getpagesize()
543
# else
544
# ifndef LACKS_SYS_PARAM_H
545
# include <sys/param.h>
546
# endif
547
# ifdef EXEC_PAGESIZE
548
# define malloc_getpagesize EXEC_PAGESIZE
549
# else
550
# ifdef NBPG
551
# ifndef CLSIZE
552
# define malloc_getpagesize NBPG
553
# else
554
# define malloc_getpagesize (NBPG * CLSIZE)
555
# endif
556
# else
557
# ifdef NBPC
558
# define malloc_getpagesize NBPC
559
# else
560
# ifdef PAGESIZE
561
# define malloc_getpagesize PAGESIZE
562
# else /* just guess */
563
# define malloc_getpagesize (4096)
564
# endif
565
# endif
566
# endif
567
# endif
568
# endif
569
# endif
570
# endif
571
#endif
572
573
/*
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.)
581
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.
587
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.
598
*/
599
600
/* #define HAVE_USR_INCLUDE_MALLOC_H */
601
602
#ifdef HAVE_USR_INCLUDE_MALLOC_H
603
#include "/usr/include/malloc.h"
604
#else
605
606
/* SVID2/XPG mallinfo structure */
607
608
struct mallinfo {
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 */
619
};
620
621
/*
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.
627
*/
628
#endif
629
630
631
/* ---------- description of public routines ------------ */
632
633
/*
634
malloc(size_t n)
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.
638
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.
646
*/
647
Void_t* public_mALLOc(size_t);
648
649
/*
650
free(Void_t* p)
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.
655
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.
659
*/
660
void public_fREe(Void_t*);
661
662
/*
663
calloc(size_t n_elements, size_t element_size);
664
Returns a pointer to n_elements * element_size bytes, with all locations
665
set to zero.
666
*/
667
Void_t* public_cALLOc(size_t, size_t);
668
669
/*
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.
674
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.
678
679
If p is null, realloc is equivalent to malloc.
680
681
If space is not available, realloc returns null, errno is set (if on
682
ANSI) and p is NOT freed.
683
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.
688
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).
692
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.
695
*/
696
697
Void_t* public_rEALLOc(Void_t*, size_t);
698
699
/*
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.
703
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.
708
709
Overreliance on memalign is a sure way to fragment space.
710
*/
711
Void_t* public_mEMALIGn(size_t, size_t);
712
713
/*
714
valloc(size_t n);
715
Equivalent to memalign(pagesize, n), where pagesize is the page
716
size of the system. If the pagesize is unknown, 4096 is used.
717
*/
718
Void_t* public_vALLOc(size_t);
719
720
721
/*
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"
733
configurations).
734
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)
738
M_TOP_PAD -2 0 any
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)
741
*/
742
int public_mALLOPt(int, int);
743
744
745
/*
746
mallinfo()
747
Returns (by copy) a struct containing various summary statistics:
748
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.)
763
764
Because these fields are ints, but internal bookkeeping may
765
be kept as longs, the reported values may wrap around zero and
766
thus be inaccurate.
767
*/
768
struct mallinfo public_mALLINFo(void);
769
770
/*
771
independent_calloc(size_t n_elements, size_t element_size, Void_t* chunks[]);
772
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
780
applications.
781
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
787
chunks.
788
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).
793
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.)
799
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:
805
806
struct Node { int item; struct Node* next; };
807
808
struct Node* build_list() {
809
struct Node** pool;
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)
819
return first;
820
}
821
*/
822
Void_t** public_iCALLOc(size_t, size_t, Void_t**);
823
824
/*
825
independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
826
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.
834
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.
840
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).
845
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.)
851
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.
855
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:
859
860
struct Head { ... }
861
struct Foot { ... }
862
863
void send_message(char* msg) {
864
int msglen = strlen(msg);
865
size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
866
void* chunks[3];
867
if (independent_comalloc(3, sizes, chunks) == 0)
868
die();
869
struct Head* head = (struct Head*)(chunks[0]);
870
char* body = (char*)(chunks[1]);
871
struct Foot* foot = (struct Foot*)(chunks[2]);
872
// ...
873
}
874
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.
878
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.
882
*/
883
Void_t** public_iCOMALLOc(size_t, size_t*, Void_t**);
884
885
886
/*
887
pvalloc(size_t n);
888
Equivalent to valloc(minimum-page-that-holds(n)), that is,
889
round up n to nearest pagesize.
890
*/
891
Void_t* public_pVALLOc(size_t);
892
893
/*
894
cfree(Void_t* p);
895
Equivalent to free(p).
896
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).
900
*/
901
void public_cFREe(Void_t*);
902
903
/*
904
malloc_trim(size_t pad);
905
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
913
the system.
914
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
921
from the system.
922
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
925
rreturn 0.
926
*/
927
int public_mTRIm(size_t);
928
929
/*
930
malloc_usable_size(Void_t* p);
931
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:
939
940
p = malloc(n);
941
assert(malloc_usable_size(p) >= 256);
942
943
*/
944
size_t public_mUSABLe(Void_t*);
945
946
/*
947
malloc_stats();
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.
957
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.
961
962
malloc_stats prints only the most commonly interesting statistics.
963
More information can be obtained by calling mallinfo.
964
965
*/
966
void public_mSTATs();
967
968
/* mallopt tuning options */
969
970
/*
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.
976
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.
986
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
992
slower.
993
*/
994
995
996
/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
997
#ifndef M_MXFAST
998
#define M_MXFAST 1
999
#endif
1000
1001
#ifndef DEFAULT_MXFAST
1002
#define DEFAULT_MXFAST 64
1003
#endif
1004
1005
1006
/*
1007
M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
1008
to keep before releasing via malloc_trim in free().
1009
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.
1016
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
1025
consumption.
1026
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
1038
is usually faster.
1039
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
1045
safeguards.
1046
1047
The trim value must be greater than page size to have any useful
1048
effect. To disable trimming completely, you can set to
1049
(unsigned long)(-1)
1050
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.
1056
1057
Also, trimming is not generally possible in cases where
1058
the main arena is obtained via mmap.
1059
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.
1064
*/
1065
1066
#define M_TRIM_THRESHOLD -1
1067
1068
#ifndef DEFAULT_TRIM_THRESHOLD
1069
1070
#define DEFAULT_TRIM_THRESHOLD (-1U)
1071
/* #define DEFAULT_TRIM_THRESHOLD (256 * 1024) */
1072
#endif
1073
1074
/*
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:
1077
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
1080
request.
1081
1082
* When malloc_trim is called automatically from free(),
1083
it is used as the `pad' argument.
1084
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.
1087
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
1092
time.
1093
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
1098
the program needs.
1099
*/
1100
1101
#define M_TOP_PAD -2
1102
1103
#ifndef DEFAULT_TOP_PAD
1104
#define DEFAULT_TOP_PAD (0)
1105
#endif
1106
1107
/*
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.)
1112
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).
1118
1119
Segregating space in this way has the benefits that:
1120
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.
1129
1130
However, it has the disadvantages that:
1131
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
1135
requirements
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.
1141
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
1145
systems.
1146
*/
1147
1148
#define M_MMAP_THRESHOLD -3
1149
1150
#ifndef DEFAULT_MMAP_THRESHOLD
1151
#define DEFAULT_MMAP_THRESHOLD (-1U)
1152
/*#define DEFAULT_MMAP_THRESHOLD (128 * 1024) */
1153
#endif
1154
1155
/*
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
1160
performance.
1161
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.
1166
*/
1167
1168
#define M_MMAP_MAX -4
1169
1170
#ifndef DEFAULT_MMAP_MAX
1171
#if HAVE_MMAP
1172
#define DEFAULT_MMAP_MAX (65536)
1173
#else
1174
#define DEFAULT_MMAP_MAX (0)
1175
#endif
1176
#endif
1177
1178
#ifdef __cplusplus
1179
}; /* end of extern "C" */
1180
#endif
1181
1182
/*
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
========================================================================
1188
*/
1189
1190
/* #include "malloc.h" */
1191
1192
/* --------------------- public wrappers ---------------------- */
1193
1194
#ifdef USE_PUBLIC_MALLOC_WRAPPERS
1195
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);
1212
1213
/*
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.
1219
*/
1220
1221
1222
#ifdef USE_MALLOC_LOCK
1223
1224
#ifdef WIN32
1225
1226
static int mALLOC_MUTEx;
1227
#define MALLOC_PREACTION slwait(&mALLOC_MUTEx)
1228
#define MALLOC_POSTACTION slrelease(&mALLOC_MUTEx)
1229
1230
#else
1231
1232
#include <pthread.h>
1233
1234
static pthread_mutex_t mALLOC_MUTEx = PTHREAD_MUTEX_INITIALIZER;
1235
1236
#define MALLOC_PREACTION pthread_mutex_lock(&mALLOC_MUTEx)
1237
#define MALLOC_POSTACTION pthread_mutex_unlock(&mALLOC_MUTEx)
1238
1239
#endif /* USE_MALLOC_LOCK */
1240
1241
#else
1242
1243
/* Substitute anything you like for these */
1244
1245
#define MALLOC_PREACTION (0)
1246
#define MALLOC_POSTACTION (0)
1247
1248
#endif
1249
1250
Void_t* public_mALLOc(size_t bytes) {
1251
Void_t* m;
1252
if (MALLOC_PREACTION != 0) {
1253
return 0;
1254
}
1255
m = mALLOc(bytes);
1256
if (MALLOC_POSTACTION != 0) {
1257
}
1258
return m;
1259
}
1260
1261
void public_fREe(Void_t* m) {
1262
if (MALLOC_PREACTION != 0) {
1263
return;
1264
}
1265
fREe(m);
1266
if (MALLOC_POSTACTION != 0) {
1267
}
1268
}
1269
1270
Void_t* public_rEALLOc(Void_t* m, size_t bytes) {
1271
if (MALLOC_PREACTION != 0) {
1272
return 0;
1273
}
1274
m = rEALLOc(m, bytes);
1275
if (MALLOC_POSTACTION != 0) {
1276
}
1277
return m;
1278
}
1279
1280
Void_t* public_mEMALIGn(size_t alignment, size_t bytes) {
1281
Void_t* m;
1282
if (MALLOC_PREACTION != 0) {
1283
return 0;
1284
}
1285
m = mEMALIGn(alignment, bytes);
1286
if (MALLOC_POSTACTION != 0) {
1287
}
1288
return m;
1289
}
1290
1291
Void_t* public_vALLOc(size_t bytes) {
1292
Void_t* m;
1293
if (MALLOC_PREACTION != 0) {
1294
return 0;
1295
}
1296
m = vALLOc(bytes);
1297
if (MALLOC_POSTACTION != 0) {
1298
}
1299
return m;
1300
}
1301
1302
Void_t* public_pVALLOc(size_t bytes) {
1303
Void_t* m;
1304
if (MALLOC_PREACTION != 0) {
1305
return 0;
1306
}
1307
m = pVALLOc(bytes);
1308
if (MALLOC_POSTACTION != 0) {
1309
}
1310
return m;
1311
}
1312
1313
Void_t* public_cALLOc(size_t n, size_t elem_size) {
1314
Void_t* m;
1315
if (MALLOC_PREACTION != 0) {
1316
return 0;
1317
}
1318
m = cALLOc(n, elem_size);
1319
if (MALLOC_POSTACTION != 0) {
1320
}
1321
return m;
1322
}
1323
1324
1325
Void_t** public_iCALLOc(size_t n, size_t elem_size, Void_t** chunks) {
1326
Void_t** m;
1327
if (MALLOC_PREACTION != 0) {
1328
return 0;
1329
}
1330
m = iCALLOc(n, elem_size, chunks);
1331
if (MALLOC_POSTACTION != 0) {
1332
}
1333
return m;
1334
}
1335
1336
Void_t** public_iCOMALLOc(size_t n, size_t sizes[], Void_t** chunks) {
1337
Void_t** m;
1338
if (MALLOC_PREACTION != 0) {
1339
return 0;
1340
}
1341
m = iCOMALLOc(n, sizes, chunks);
1342
if (MALLOC_POSTACTION != 0) {
1343
}
1344
return m;
1345
}
1346
1347
void public_cFREe(Void_t* m) {
1348
if (MALLOC_PREACTION != 0) {
1349
return;
1350
}
1351
cFREe(m);
1352
if (MALLOC_POSTACTION != 0) {
1353
}
1354
}
1355
1356
int public_mTRIm(size_t s) {
1357
int result;
1358
if (MALLOC_PREACTION != 0) {
1359
return 0;
1360
}
1361
result = mTRIm(s);
1362
if (MALLOC_POSTACTION != 0) {
1363
}
1364
return result;
1365
}
1366
1367
size_t public_mUSABLe(Void_t* m) {
1368
size_t result;
1369
if (MALLOC_PREACTION != 0) {
1370
return 0;
1371
}
1372
result = mUSABLe(m);
1373
if (MALLOC_POSTACTION != 0) {
1374
}
1375
return result;
1376
}
1377
1378
void public_mSTATs() {
1379
if (MALLOC_PREACTION != 0) {
1380
return;
1381
}
1382
mSTATs();
1383
if (MALLOC_POSTACTION != 0) {
1384
}
1385
}
1386
1387
struct mallinfo public_mALLINFo() {
1388
struct mallinfo m;
1389
if (MALLOC_PREACTION != 0) {
1390
struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
1391
return nm;
1392
}
1393
m = mALLINFo();
1394
if (MALLOC_POSTACTION != 0) {
1395
}
1396
return m;
1397
}
1398
1399
int public_mALLOPt(int p, int v) {
1400
int result;
1401
if (MALLOC_PREACTION != 0) {
1402
return 0;
1403
}
1404
result = mALLOPt(p, v);
1405
if (MALLOC_POSTACTION != 0) {
1406
}
1407
return result;
1408
}
1409
1410
#endif
1411
1412
1413
1414
/* ------------- Optional versions of memcopy ---------------- */
1415
1416
1417
#if USE_MEMCPY
1418
1419
/*
1420
Note: memcpy is ONLY invoked with non-overlapping regions,
1421
so the (usually slower) memmove is not needed.
1422
*/
1423
1424
#define MALLOC_COPY(dest, src, nbytes) memcpy(dest, src, nbytes)
1425
#define MALLOC_ZERO(dest, nbytes) memset(dest, 0, nbytes)
1426
1427
#else /* !USE_MEMCPY */
1428
1429
/* Use Duff's device for good zeroing/copying performance. */
1430
1431
#define MALLOC_ZERO(charp, nbytes) \
1432
do { \
1433
INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \
1434
CHUNK_SIZE_T mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T); \
1435
long mcn; \
1436
if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
1437
switch (mctmp) { \
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--; } \
1446
} \
1447
} while(0)
1448
1449
#define MALLOC_COPY(dest,src,nbytes) \
1450
do { \
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); \
1454
long mcn; \
1455
if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
1456
switch (mctmp) { \
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--; } \
1465
} \
1466
} while(0)
1467
1468
#endif
1469
1470
/* ------------------ MMAP support ------------------ */
1471
1472
1473
#if HAVE_MMAP
1474
1475
#include <fcntl.h>
1476
#ifndef LACKS_SYS_MMAN_H
1477
#include <sys/mman.h>
1478
#endif
1479
1480
#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1481
#define MAP_ANONYMOUS MAP_ANON
1482
#endif
1483
1484
/*
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.
1488
*/
1489
1490
#ifndef MAP_ANONYMOUS
1491
1492
static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1493
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))
1498
1499
#else
1500
1501
#define MMAP(addr, size, prot, flags) \
1502
(mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1503
1504
#endif
1505
1506
1507
#endif /* HAVE_MMAP */
1508
1509
1510
/*
1511
----------------------- Chunk representations -----------------------
1512
*/
1513
1514
1515
/*
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.
1519
*/
1520
1521
struct malloc_chunk {
1522
1523
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
1524
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
1525
1526
struct malloc_chunk* fd; /* double links -- used only if free. */
1527
struct malloc_chunk* bk;
1528
};
1529
1530
1531
typedef struct malloc_chunk* mchunkptr;
1532
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))
1536
1537
/*
1538
malloc_chunk details:
1539
1540
(The following includes lightly edited explanations by Colin Plumb.)
1541
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
1549
in use.
1550
1551
An allocated chunk looks like this:
1552
1553
1554
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1555
| Size of previous chunk, if allocated | |
1556
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1557
| Size of chunk, in bytes |P|
1558
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1559
| User data starts here... .
1560
. .
1561
. (malloc_usable_space() bytes) .
1562
. |
1563
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1564
`foot:' | Size of chunk |
1565
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1566
1567
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.
1571
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.
1575
1576
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.
1587
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.
1592
1593
The two exceptions to all this are
1594
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.
1600
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.
1604
1605
*/
1606
1607
1608
1609
/*
1610
--------------- Operations on size fields ---------------
1611
*/
1612
1613
1614
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1615
#define PREV_INUSE 0x1
1616
1617
#if HAVE_MMAP
1618
/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap */
1619
#define IS_MMAPPED 0x2
1620
#else
1621
#define IS_MMAPPED 0
1622
#endif
1623
1624
/* extract inuse bit of previous chunk */
1625
#define prev_inuse(p) ((p)->size & PREV_INUSE)
1626
1627
/* check for mmap()'ed chunk */
1628
#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1629
1630
/*
1631
Bits to mask off when extracting size
1632
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.
1637
*/
1638
#define SIZE_BITS (PREV_INUSE|IS_MMAPPED)
1639
1640
/* Get size, ignoring use bits */
1641
#define chunksize(p) ((CHUNK_SIZE_T)((p)->size & ~(SIZE_BITS)))
1642
1643
1644
/* Ptr to next physical malloc_chunk. */
1645
#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE)))
1646
1647
/* Ptr to previous physical malloc_chunk */
1648
#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1649
1650
/* Treat space at ptr + offset as a chunk */
1651
#define chunk_at_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
1652
1653
/* extract p's inuse bit */
1654
#define inuse(p)\
1655
((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE)
1656
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
1660
1661
#define clear_inuse(p)\
1662
((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size &= ~(PREV_INUSE)
1663
1664
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)
1668
1669
#define inuse_addr_at_offset(p, s)\
1670
(INTERNAL_SIZE_T*)(&(((mchunkptr)(((char*)(p)) + (s)))->size))
1671
1672
#define set_inuse_bit_at_offset(p, s)\
1673
(((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
1674
1675
#define clear_inuse_bit_at_offset(p, s)\
1676
(((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
1677
1678
1679
/* Set size at head, without disturbing its use bit */
1680
#define set_head_size(p, s) ((p)->size = (((p)->size & PREV_INUSE) | (s)))
1681
1682
/* Set size/use field */
1683
#define set_head(p, s) ((p)->size = (s))
1684
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))
1687
1688
1689
/*
1690
---------- Size and alignment checks and conversions ----------
1691
*/
1692
1693
1694
/* The smallest possible chunk */
1695
#define MIN_CHUNK_SIZE (sizeof(struct malloc_chunk))
1696
1697
/* The smallest size we can malloc is an aligned minimal chunk */
1698
1699
#define MINSIZE \
1700
(CHUNK_SIZE_T)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1701
1702
/* Check if m has acceptable alignment */
1703
1704
#define aligned_OK(m) (((PTR_UINT)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1705
1706
1707
/*
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.
1711
*/
1712
1713
#define MAX_REQUEST_SIZE ((CHUNK_SIZE_T)(INTERNAL_SIZE_T)(-2 * MINSIZE))
1714
1715
#define request_out_of_range(req) \
1716
((CHUNK_SIZE_T)(req) >= MAX_REQUEST_SIZE)
1717
1718
/* pad request bytes into a usable size -- internal version */
1719
1720
#define request2size(req) \
1721
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
1722
MINSIZE : \
1723
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1724
1725
1726
#define pad_request(req) \
1727
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1728
1729
/* Same, except also perform argument check */
1730
1731
#define checked_request2size(req, sz) \
1732
if (request_out_of_range(req)) { \
1733
MALLOC_FAILURE_ACTION; \
1734
return 0; \
1735
} \
1736
(sz) = request2size(req);
1737
1738
1739
typedef CHUNK_SIZE_T bin_index_t;
1740
typedef unsigned int bitmap_t;
1741
1742
1743
/*
1744
---------- Overlaid Data types ----------
1745
*/
1746
1747
1748
/*
1749
"Small" chunks are stored in circular doubly-linked lists, and look
1750
like this:
1751
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) .
1762
. .
1763
. |
1764
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1765
`foot:' | Size of chunk, in bytes |
1766
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1767
1768
Larger chunks are kept in a form of bitwise digital trees (aka tries)
1769
keyed on chunksizes, in which
1770
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
1775
of small chunks
1776
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.
1782
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.
1788
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.
1792
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1810
| Unused space .
1811
. |
1812
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1813
`foot:' | Size of chunk, in bytes |
1814
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1815
1816
*/
1817
1818
1819
struct malloc_tree_chunk {
1820
INTERNAL_SIZE_T prev_size; /* same as in malloc_chunk */
1821
INTERNAL_SIZE_T size;
1822
1823
struct malloc_tree_chunk* fd; /* double links -- used only if free. */
1824
struct malloc_tree_chunk* bk;
1825
1826
struct malloc_tree_chunk* child[2];
1827
struct malloc_tree_chunk* parent;
1828
1829
bin_index_t index;
1830
};
1831
1832
typedef struct malloc_tree_chunk* tchunkptr;
1833
1834
typedef struct malloc_tree_chunk* tbinptr;
1835
1836
1837
1838
1839
/*
1840
-------------------- Internal data structures --------------------
1841
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
1844
cases:
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.
1848
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.)
1852
*/
1853
1854
/*
1855
SmallBins
1856
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.
1864
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*.
1871
1872
*/
1873
1874
typedef struct malloc_chunk* mbinptr;
1875
1876
/* addressing */
1877
#define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - (SIZE_SZ<<1)))
1878
1879
/* analog of ++bin */
1880
#define next_bin(b) ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
1881
1882
/* inverse of bin_at */
1883
#define bin2idx(m, b) \
1884
( ((int) (((char*)(b)) - (char*)(bin_at(m,0)))) / (2 * sizeof(mchunkptr)))
1885
1886
/*
1887
Indexing
1888
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.
1892
*/
1893
1894
#define NBINS 32
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
1899
1900
#define in_smallbin_range(sz) \
1901
((CHUNK_SIZE_T)(sz) <= (CHUNK_SIZE_T)(MIN_TREEBIN_SIZE-1))
1902
1903
1904
#define MAX_SMALL_REQUEST (MIN_TREEBIN_SIZE-(SIZE_SZ+MALLOC_ALIGNMENT))
1905
1906
#define smallbin_index(sz) (bin_index_t)((sz) >> 3)
1907
1908
#define size_for_smallindex(i) ((CHUNK_SIZE_T)(i) << 3)
1909
1910
#define MIN_SMALLBIN_INDEX (smallbin_index(MINSIZE))
1911
1912
#define MIN_SMALLBIN_BIT (idx2bit(smallbin_index(MINSIZE)))
1913
1914
1915
/*
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
1918
larger.
1919
*/
1920
1921
1922
static bin_index_t treebin_index(CHUNK_SIZE_T sz) {
1923
unsigned int m;
1924
unsigned int x = sz >> TREE_BIN_SHIFT;
1925
if (x == 0)
1926
return 0;
1927
if (x > 0xFFFF)
1928
return NBINS-1;
1929
1930
/* On intel, use BSRL instruction to find highest bit */
1931
#if defined(__GNUC__) && defined(i386)
1932
1933
__asm__("bsrl %1,%0\n\t"
1934
: "=r" (m)
1935
: "g" (x));
1936
return (m << 1) + ((sz >> (m + (TREE_BIN_SHIFT-1)) & 1));
1937
1938
#else
1939
{
1940
/*
1941
Based on branch-free nlz algorithm in chapter 5 of Henry
1942
S. Warren Jr's book "Hacker's Delight".
1943
*/
1944
1945
unsigned int n = ((x - 0x100) >> 16) & 8;
1946
x <<= n;
1947
m = ((x - 0x1000) >> 16) & 4;
1948
n += m;
1949
x <<= m;
1950
m = ((x - 0x4000) >> 16) & 2;
1951
n += m;
1952
x = (x << m) >> 14;
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));
1956
}
1957
#endif
1958
}
1959
1960
static bin_index_t bit2idx(bitmap_t x) {
1961
#if defined(__GNUC__) && defined(i386)
1962
int r;
1963
__asm__("bsfl %1,%0\n\t"
1964
: "=r" (r) : "g" (x));
1965
return (bin_index_t)r;
1966
#else
1967
return (bin_index_t)(ffs(x)-1);
1968
#endif
1969
}
1970
1971
1972
1973
#define bin_index(sz) \
1974
((in_smallbin_range(sz)) ? smallbin_index(sz) : treebin_index(sz))
1975
1976
/*
1977
The most significant bit distinguishing nodes in the tree
1978
associated with a given bin
1979
*/
1980
1981
#define CHUNK_SIZE_BITS (sizeof(CHUNK_SIZE_T) * 8)
1982
1983
#define bitshift_for_index(idx) \
1984
(idx == NBINS-1)? \
1985
CHUNK_SIZE_BITS-1 : \
1986
(((idx) >> 1) + TREE_BIN_SHIFT-2)
1987
1988
#define tbin_at(m,i) (&((m)->treebins[i]))
1989
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)))
1994
1995
1996
1997
#define is_tbin(M, P) ((tbinptr*)(P) >= &((M)->treebins[0]) && \
1998
(tbinptr*)(P) < &((M)->treebins[NBINS]))
1999
2000
#define leftmost_child(t) \
2001
(((t)->child[0] != 0)? ((t)->child[0]) : ((t)->child[1]))
2002
2003
2004
/*
2005
Fastbins
2006
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.
2014
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
2018
other free chunks.
2019
*/
2020
2021
typedef struct malloc_chunk* mfastbinptr;
2022
2023
#define fastbin_at(m,i) (&((m)->fastbins[i]))
2024
2025
/* offset 2 to use otherwise unindexable first 2 bins */
2026
#define fastbin_index(sz) ((((unsigned int)(sz)) >> 3) - 2)
2027
2028
2029
/* The maximum fastbin request size we support */
2030
#define MAX_FAST_REQUEST 64
2031
2032
#define MAX_FAST_SIZE (request2size(MAX_FAST_REQUEST))
2033
2034
#define NFASTBINS (fastbin_index(MAX_FAST_SIZE)+1)
2035
2036
/*
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.
2040
*/
2041
2042
#define FASTCHUNKS_BIT (2U)
2043
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))
2047
2048
/*
2049
Set value of max_fast.
2050
Use impossibly small value if 0.
2051
*/
2052
2053
#define set_max_fast(M, s) \
2054
(M)->max_fast = (((s) == 0)? SMALLBIN_WIDTH: request2size(s)) | \
2055
((M)->max_fast & (FASTCHUNKS_BIT))
2056
2057
#define get_max_fast(M) \
2058
((M)->max_fast & ~(FASTCHUNKS_BIT))
2059
2060
2061
/*
2062
Top
2063
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
2068
M_TRIM_THRESHOLD).
2069
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.
2073
*/
2074
2075
2076
/*
2077
Binmap
2078
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.
2083
*/
2084
2085
/* Conservatively use 32 bits per map word, even if on 64bit system */
2086
2087
#define idx2bit(i) ((bitmap_t)(1) << (i))
2088
2089
#define mark_smallbin(m,i) ((m)->smallbits |= idx2bit(i))
2090
#define mark_treebin(m,i) ((m)->treebits |= idx2bit(i))
2091
2092
#define clear_smallbin(m,i) ((m)->smallbits &= ~idx2bit(i))
2093
#define clear_treebin(m,i) ((m)->treebits &= ~idx2bit(i))
2094
2095
2096
/* isolate the least set bit of a bitmap */
2097
2098
#define least_bit(x) ((x) & -(x))
2099
2100
/* create mask with all bits to left of least bit of x on */
2101
2102
#define left_bits(x) ((x<<1) | -(x<<1))
2103
2104
/* create mask with all bits to left of or equal to least bit of x on */
2105
2106
#define same_or_left_bits(x) ((x) | -(x))
2107
2108
2109
/*
2110
sysctl is a status word holding dynamically discovered
2111
or controlled properties of the morecore function
2112
*/
2113
2114
#define MORECORE_CONTIGUOUS_BIT (1U)
2115
#define TRIM_DISABLE_BIT (2U)
2116
#define MMAP_DISABLE_BIT (4U)
2117
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)
2124
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)
2131
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)
2138
2139
2140
2141
2142
/*
2143
----------- Internal state representation and initialization -----------
2144
*/
2145
2146
struct malloc_state {
2147
/* The maximum chunk size to be eligible for fastbin */
2148
CHUNK_SIZE_T max_fast;
2149
2150
/* Bitmap of bins */
2151
bitmap_t smallbits;
2152
bitmap_t treebits;
2153
2154
/* Base of the topmost chunk -- not otherwise kept in a bin */
2155
mchunkptr top;
2156
2157
/* Fastbins */
2158
mfastbinptr fastbins[NFASTBINS];
2159
2160
/* Smallbins packed as described above */
2161
mchunkptr bins[NBINS * 2];
2162
2163
/* Treebins */
2164
tbinptr treebins[NBINS];
2165
2166
/* Padding to allow addressing past end of treebin array */
2167
struct malloc_tree_chunk initial_top;
2168
2169
/* Tunable parameters */
2170
CHUNK_SIZE_T trim_threshold;
2171
INTERNAL_SIZE_T top_pad;
2172
INTERNAL_SIZE_T mmap_threshold;
2173
2174
/* Memory map support */
2175
int n_mmaps;
2176
int n_mmaps_max;
2177
int max_n_mmaps;
2178
2179
/* Cache malloc_getpagesize */
2180
unsigned int pagesize;
2181
2182
/* Track properties of MORECORE */
2183
unsigned int sysctl;
2184
2185
/* Statistics */
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;
2191
};
2192
2193
typedef struct malloc_state *mstate;
2194
2195
/*
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).
2201
*/
2202
2203
static struct malloc_state av_; /* never directly referenced */
2204
2205
/*
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.
2211
*/
2212
2213
#define get_malloc_state() (&(av_))
2214
2215
/*
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.
2219
*/
2220
2221
static void malloc_init_state(mstate av) {
2222
int i;
2223
mbinptr bin;
2224
2225
/* Establish circular links for bins */
2226
for (i = 0; i < NBINS; ++i) {
2227
bin = bin_at(av,i);
2228
bin->fd = bin->bk = bin;
2229
}
2230
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;
2235
2236
#if MORECORE_CONTIGUOUS
2237
set_contiguous(av);
2238
#else
2239
set_noncontiguous(av);
2240
#endif
2241
2242
set_max_fast(av, DEFAULT_MXFAST);
2243
2244
av->top = (mchunkptr)(&(av->initial_top));
2245
av->pagesize = malloc_getpagesize;
2246
}
2247
2248
#define ensure_initialization(M) \
2249
if ((M)->top == 0) sysmalloc(M, 0);
2250
2251
2252
/*
2253
Other internal utilities
2254
*/
2255
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);
2260
#if 0
2261
static void unlink_treenode(mstate, tchunkptr);
2262
static void unlink_small_chunk(mstate av, mchunkptr p, CHUNK_SIZE_T size);
2263
#endif
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 malloc_consolidate(mstate);
2272
2273
2274
#pragma no_inline(systrim)
2275
2276
2277
#if HAVE_MMAP
2278
static mchunkptr mmap_malloc(mstate, INTERNAL_SIZE_T);
2279
#endif
2280
2281
/*
2282
Debugging support
2283
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!)
2289
*/
2290
2291
2292
#if ! DEBUG
2293
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)
2301
2302
#else
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)
2310
2311
static void do_check_malloc_state(mstate);
2312
2313
/*
2314
Find x in a treebin. Used in other check functions.
2315
*/
2316
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);
2322
tchunkptr t = *bin;
2323
bin_index_t shift = bitshift_for_index(idx);
2324
CHUNK_SIZE_T allbits = 0;
2325
2326
if (t == 0)
2327
return 0;
2328
2329
while (t != 0) {
2330
CHUNK_SIZE_T size;
2331
if (t == x)
2332
return t;
2333
size = chunksize(t);
2334
assert((size & allbits) == allbits);
2335
if (size == nb) {
2336
tchunkptr p = t->bk;
2337
for (;;) {
2338
if (p == x)
2339
return p;
2340
else if (p == t)
2341
return 0;
2342
else
2343
p = p->bk;
2344
}
2345
}
2346
if (((nb >> shift) & 1) == 0) {
2347
t = t->child[0];
2348
}
2349
else {
2350
t = t->child[1];
2351
allbits |= 1U << shift;
2352
}
2353
2354
--shift;
2355
}
2356
return 0;
2357
}
2358
2359
/*
2360
Properties of all chunks
2361
*/
2362
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;
2369
2370
if (!chunk_is_mmapped(p)) {
2371
2372
/* Has legal address ... */
2373
if (p != av->top) {
2374
if (contiguous(av)) {
2375
assert(((char*)p) >= min_address);
2376
assert(((char*)p + sz) <= ((char*)(av->top)));
2377
}
2378
}
2379
else {
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));
2384
}
2385
2386
}
2387
else {
2388
#if HAVE_MMAP
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);
2392
}
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)));
2397
#else
2398
/* force an appropriate assert violation if debug set */
2399
assert(!chunk_is_mmapped(p));
2400
#endif
2401
}
2402
}
2403
2404
static void check_all_less(tchunkptr t, CHUNK_SIZE_T nb) {
2405
if (t == 0)
2406
return;
2407
assert(chunksize(t) < nb);
2408
check_all_less(t->child[0], nb);
2409
check_all_less(t->child[1], nb);
2410
}
2411
2412
static void check_all_greater(tchunkptr t, CHUNK_SIZE_T nb) {
2413
if (t == 0)
2414
return;
2415
assert(chunksize(t) >= nb);
2416
check_all_greater(t->child[0], nb);
2417
check_all_greater(t->child[1], nb);
2418
}
2419
2420
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));
2425
assert(!inuse(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]));
2434
}
2435
return size;
2436
}
2437
2438
static INTERNAL_SIZE_T do_check_tree(tchunkptr t) {
2439
tchunkptr p;
2440
tchunkptr h;
2441
INTERNAL_SIZE_T total = check_tree_fields(t);
2442
2443
/* If t is on a same-sized list, another node on list must have a parent */
2444
if (t->parent == 0) {
2445
h = t->bk;
2446
while (h != t && h->parent == 0)
2447
h = h->bk;
2448
assert(h != t);
2449
}
2450
else
2451
h = t;
2452
2453
assert (h->parent->child[0] == h ||
2454
h->parent->child[1] == h ||
2455
*((tbinptr*)(h->parent)) == h);
2456
2457
2458
/* only one node on a same-sized list has parent or children */
2459
p = h->bk;
2460
while (p != h) {
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);
2466
p = p->bk;
2467
}
2468
2469
if (h->child[0] != 0) {
2470
assert(h->child[0]->parent == h);
2471
total += do_check_tree(h->child[0]);
2472
}
2473
2474
if (h->child[1] != 0) {
2475
assert(h->child[1]->parent == h);
2476
total += do_check_tree(h->child[1]);
2477
}
2478
2479
return total;
2480
}
2481
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);
2486
}
2487
else {
2488
do_check_tree((tchunkptr)p);
2489
}
2490
}
2491
2492
/*
2493
Properties of free chunks
2494
*/
2495
2496
static void do_check_free_chunk(mchunkptr p) {
2497
mstate av = get_malloc_state();
2498
2499
INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2500
mchunkptr next = chunk_at_offset(p, sz);
2501
2502
do_check_chunk(p);
2503
2504
/* Chunk must claim to be free ... */
2505
assert(!inuse(p));
2506
assert (!chunk_is_mmapped(p));
2507
2508
/* Unless a special marker, must have OK fields */
2509
if ((CHUNK_SIZE_T)(sz) >= MINSIZE)
2510
{
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));
2518
2519
do_check_links(p);
2520
}
2521
else /* markers are always of size SIZE_SZ */
2522
assert(sz == SIZE_SZ);
2523
}
2524
2525
/*
2526
Properties of inuse chunks
2527
*/
2528
2529
static void do_check_inuse_chunk(mchunkptr p) {
2530
mstate av = get_malloc_state();
2531
mchunkptr next;
2532
do_check_chunk(p);
2533
2534
if (chunk_is_mmapped(p))
2535
return; /* mmapped chunks have no next/prev */
2536
2537
/* Check whether it claims to be in use ... */
2538
assert(inuse(p));
2539
2540
next = next_chunk(p);
2541
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.
2545
*/
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);
2551
}
2552
2553
if (next == av->top) {
2554
assert(prev_inuse(next));
2555
assert(chunksize(next) >= MINSIZE);
2556
}
2557
else if (!inuse(next))
2558
do_check_free_chunk(next);
2559
}
2560
2561
2562
static void do_check_remalloced_chunk(mchunkptr p, INTERNAL_SIZE_T s) {
2563
INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2564
2565
do_check_inuse_chunk(p);
2566
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);
2575
}
2576
2577
/*
2578
Properties of nonrecycled chunks at the point they are malloced
2579
*/
2580
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);
2584
#if 0
2585
do_check_malloc_state(get_malloc_state());
2586
#endif
2587
2588
/*
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
2594
chunk.
2595
*/
2596
2597
assert(prev_inuse(p));
2598
}
2599
2600
2601
static CHUNK_SIZE_T do_check_smallbin(mstate av, int i, mbinptr b) {
2602
mchunkptr p = b->bk;
2603
mchunkptr q;
2604
bin_index_t idx;
2605
INTERNAL_SIZE_T size;
2606
CHUNK_SIZE_T total = 0;
2607
unsigned int empty = (av->smallbits & (1 << i)) == 0;
2608
2609
if (i >= 2) {
2610
if (empty)
2611
assert(p == b);
2612
if (p == b)
2613
assert(empty);
2614
2615
if (p != b)
2616
assert(!empty);
2617
}
2618
2619
for (; p != b; p = p->bk) {
2620
/* each chunk claims to be free */
2621
do_check_free_chunk(p);
2622
size = chunksize(p);
2623
total += size;
2624
if (i >= 2) {
2625
/* chunk belongs in bin */
2626
idx = smallbin_index(size);
2627
assert(idx == i);
2628
assert(p->bk == b ||
2629
(CHUNK_SIZE_T)chunksize(p->bk) ==
2630
(CHUNK_SIZE_T)chunksize(p));
2631
}
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);
2636
q = next_chunk(q))
2637
do_check_inuse_chunk(q);
2638
}
2639
2640
return total;
2641
}
2642
2643
/*
2644
Properties of malloc_state.
2645
2646
This may be useful for debugging malloc, as well as detecting user
2647
programmer errors that somehow write into malloc_state.
2648
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.
2652
*/
2653
2654
static void do_check_malloc_state(mstate av) {
2655
int i;
2656
mbinptr b;
2657
CHUNK_SIZE_T total = 0;
2658
tchunkptr t;
2659
unsigned int empty;
2660
tbinptr* tb;
2661
int max_fast_bin;
2662
mchunkptr p;
2663
2664
/* internal size_t must be no wider than pointer type */
2665
assert(sizeof(INTERNAL_SIZE_T) <= sizeof(char*));
2666
2667
/* alignment is a power of 2 */
2668
assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0);
2669
2670
/* cannot run remaining checks until fully initialized */
2671
if (av->top == 0 || av->top == (mchunkptr)(&(av->initial_top)))
2672
return;
2673
2674
/* pagesize is a power of 2 */
2675
assert((av->pagesize & (av->pagesize-1)) == 0);
2676
2677
/* check smallbins */
2678
for (i = 1; i < NBINS; ++i) {
2679
b = bin_at(av, i);
2680
total += do_check_smallbin(av, i, b);
2681
}
2682
2683
/* check treebins */
2684
for (i = 0; i < NBINS; ++i) {
2685
tb = tbin_at(av, i);
2686
t = *tb;
2687
empty = (av->treebits & (1 << i)) == 0;
2688
if (t == 0)
2689
assert(empty);
2690
else if (t != 0) {
2691
assert(!empty);
2692
total += do_check_tree(t);
2693
}
2694
}
2695
2696
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);
2702
2703
/* max_fast is in allowed range */
2704
assert(get_max_fast(av) <= request2size(MAX_FAST_SIZE));
2705
2706
max_fast_bin = fastbin_index(av->max_fast);
2707
2708
for (i = 0; i < NFASTBINS; ++i) {
2709
p = av->fastbins[i];
2710
2711
/* all bins past max_fast are empty */
2712
if (i > max_fast_bin)
2713
assert(p == 0);
2714
2715
while (p != 0) {
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);
2721
p = p->fd;
2722
}
2723
}
2724
2725
/* sanity checks for statistics */
2726
2727
assert(total <= (CHUNK_SIZE_T)(av->max_total_mem));
2728
2729
assert(av->n_mmaps >= 0);
2730
assert(av->n_mmaps <= av->n_mmaps_max);
2731
assert(av->n_mmaps <= av->max_n_mmaps);
2732
2733
assert((CHUNK_SIZE_T)(av->sbrked_mem) <=
2734
(CHUNK_SIZE_T)(av->max_sbrked_mem));
2735
2736
assert((CHUNK_SIZE_T)(av->mmapped_mem) <=
2737
(CHUNK_SIZE_T)(av->max_mmapped_mem));
2738
2739
assert((CHUNK_SIZE_T)(av->max_total_mem) >=
2740
(CHUNK_SIZE_T)(av->mmapped_mem) + (CHUNK_SIZE_T)(av->sbrked_mem));
2741
}
2742
#endif
2743
2744
2745
2746
/*
2747
----------- Operations on trees -----------
2748
*/
2749
2750
/*
2751
Insert chunk into corresponding list or tree
2752
*/
2753
2754
static void insert_treenode(mstate av, tchunkptr x,
2755
CHUNK_SIZE_T nb) {
2756
bin_index_t idx = treebin_index(nb);
2757
tbinptr* bin = tbin_at(av, idx);
2758
tchunkptr t = *bin;
2759
2760
x->child[0] = 0;
2761
x->child[1] = 0;
2762
x->index = idx;
2763
2764
if (t == 0) {
2765
av->treebits |= idx2bit(idx);
2766
*bin = x;
2767
x->parent = (tchunkptr)bin;
2768
x->fd = x;
2769
x->bk = x;
2770
}
2771
else {
2772
bin_index_t shift = bitshift_for_index(idx);
2773
tchunkptr b;
2774
check_tree(t);
2775
2776
while (chunksize(t) != nb) {
2777
tchunkptr* pchild = &(t->child[(nb >> shift--) & 1]);
2778
if (*pchild != 0) {
2779
t = *pchild;
2780
}
2781
else {
2782
*pchild = x;
2783
x->parent = t;
2784
x->fd = x;
2785
x->bk = x;
2786
return;
2787
}
2788
}
2789
/* Link in same-sized node */
2790
b = t->bk;
2791
x->parent = 0;
2792
x->fd = t;
2793
x->bk = b;
2794
b->fd = t->bk = x;
2795
}
2796
}
2797
2798
static void transfer_tree_links(tchunkptr oldt, tchunkptr newt) {
2799
tchunkptr p = oldt->parent;
2800
newt->parent = p;
2801
2802
if (p->child[0] == oldt)
2803
p->child[0] = newt;
2804
else if (p->child[1] == oldt)
2805
p->child[1] = newt;
2806
else
2807
*((tbinptr*)p) = newt;
2808
2809
if ( (newt->child[0] = oldt->child[0]) != 0)
2810
newt->child[0]->parent = newt;
2811
2812
if ( (newt->child[1] = oldt->child[1]) != 0)
2813
newt->child[1]->parent = newt;
2814
}
2815
2816
static tchunkptr find_replacement(tchunkptr t) {
2817
/*
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.
2825
*/
2826
tchunkptr* cp;
2827
tchunkptr c;
2828
if ((c = *(cp = &(t->child[1]))) == 0)
2829
if ((c = *(cp = &(t->child[0]->child[1]))) == 0)
2830
c = *(cp = &(t->child[0]));
2831
2832
assert(c != 0);
2833
for (;;) {
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]));
2838
else {
2839
*cp = 0; /* unlink from parent */
2840
return c;
2841
}
2842
}
2843
}
2844
2845
static void unlink_leaf_node(mstate av, tchunkptr t) {
2846
tchunkptr p = t->parent;
2847
if (p->child[0] == t)
2848
p->child[0] = 0;
2849
else if (p->child[1] == t)
2850
p->child[1] = 0;
2851
else {
2852
assert(is_tbin(av, p));
2853
*((tbinptr*)p) = 0;
2854
av->treebits &= ~idx2bit(t->index);
2855
}
2856
}
2857
2858
static void unlink_chained_node(tchunkptr t) {
2859
tchunkptr bck = t->bk;
2860
tchunkptr fwd = t->fd;
2861
fwd->bk = bck;
2862
bck->fd = fwd;
2863
/* t's parent is nonnull if t was head of chain */
2864
if (t->parent != 0)
2865
transfer_tree_links(t, fwd);
2866
check_tree(fwd);
2867
}
2868
2869
2870
2871
/*
2872
----------- other helper functions -----------
2873
We expect these to be inlined
2874
*/
2875
2876
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);
2882
p->fd = fwd;
2883
p->bk = bck;
2884
fwd->bk = bck->fd = p;
2885
2886
assert(in_smallbin_range(nb));
2887
}
2888
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);
2892
else
2893
insert_treenode(av, (tchunkptr)p, nb);
2894
}
2895
2896
2897
static mchunkptr take_from_smallbin(mstate av, mchunkptr bin, bitmap_t bit) {
2898
mchunkptr p = bin->bk;
2899
mchunkptr bck = p->bk;
2900
assert(p != bin);
2901
bin->bk = bck;
2902
bck->fd = bin;
2903
if (bck == bin)
2904
av->smallbits &= ~bit;
2905
return p;
2906
}
2907
2908
static void unlink_chunk(mstate av, mchunkptr q, CHUNK_SIZE_T size) {
2909
mchunkptr fwd = q->fd;
2910
mchunkptr bck = q->bk;
2911
fwd->bk = bck;
2912
bck->fd = fwd;
2913
if (fwd == bck && in_smallbin_range(size)) {
2914
clear_smallbin(av, smallbin_index(size));
2915
}
2916
else if (!in_smallbin_range(size)) {
2917
tchunkptr t = (tchunkptr)q;
2918
tchunkptr c = (tchunkptr)fwd;
2919
if (c == t) {
2920
if (t->child[0] == t->child[1]) {
2921
unlink_leaf_node(av, t);
2922
return;
2923
}
2924
else {
2925
c = find_replacement(t);
2926
}
2927
}
2928
else {
2929
if (t->parent == 0) {
2930
return;
2931
}
2932
}
2933
2934
transfer_tree_links(t, c);
2935
check_tree(c);
2936
}
2937
}
2938
2939
static Void_t* use_treechunk(mstate av,
2940
CHUNK_SIZE_T nb,
2941
tchunkptr bestchunk,
2942
CHUNK_SIZE_T bestsize,
2943
tchunkptr leaf) {
2944
2945
CHUNK_SIZE_T rsize;
2946
2947
if (bestchunk->bk != bestchunk)
2948
unlink_chained_node(bestchunk);
2949
else {
2950
unlink_leaf_node(av, leaf);
2951
if (leaf != bestchunk)
2952
transfer_tree_links(bestchunk, leaf);
2953
}
2954
2955
rsize = bestsize - nb;
2956
if (rsize >= MINSIZE) {
2957
mchunkptr rem = chunk_at_offset(bestchunk, nb);
2958
set_head(bestchunk, nb | PREV_INUSE);
2959
set_head(rem, rsize | PREV_INUSE);
2960
set_foot(rem, rsize);
2961
insert_chunk(av, rem, rsize);
2962
}
2963
else {
2964
set_inuse_bit_at_offset(bestchunk, bestsize);
2965
}
2966
check_malloced_chunk((mchunkptr)(bestchunk), nb);
2967
return chunk2mem(bestchunk);
2968
}
2969
2970
2971
/*
2972
------------------------------ malloc ------------------------------
2973
*/
2974
2975
Void_t* mALLOc(size_t bytes) {
2976
mstate av = get_malloc_state();
2977
CHUNK_SIZE_T nb;
2978
2979
checked_request2size(bytes, nb);
2980
2981
if (nb <= (CHUNK_SIZE_T)(av->max_fast)) {
2982
mfastbinptr* fb = &(av->fastbins[(fastbin_index(nb))]);
2983
mchunkptr fp = *fb;
2984
if (fp != 0) {
2985
*fb = fp->fd;
2986
check_remalloced_chunk(fp, nb);
2987
return chunk2mem(fp);
2988
}
2989
}
2990
2991
2992
for (;;) {
2993
if (in_smallbin_range(nb)) {
2994
bin_index_t sidx = smallbin_index(nb);
2995
bitmap_t sbit = idx2bit(sidx);
2996
2997
if (sbit <= av->smallbits) {
2998
mchunkptr p;
2999
if ((sbit & av->smallbits) != 0) {
3000
p = take_from_smallbin(av, bin_at(av,sidx), sbit);
3001
set_inuse_bit_at_offset(p, nb);
3002
}
3003
else {
3004
bitmap_t nbit = least_bit(left_bits(sbit) & av->smallbits);
3005
bin_index_t nidx = bit2idx(nbit);
3006
CHUNK_SIZE_T psize = size_for_smallindex(nidx);
3007
CHUNK_SIZE_T qsize = psize - nb;
3008
p = take_from_smallbin(av, bin_at(av, nidx), nbit);
3009
if (qsize < MINSIZE) {
3010
set_inuse_bit_at_offset(p, psize);
3011
}
3012
else {
3013
mchunkptr q = chunk_at_offset(p, nb);
3014
set_head(p, nb | PREV_INUSE);
3015
set_head(q, qsize | PREV_INUSE);
3016
set_foot(q, qsize);
3017
insert_small_chunk(av, q, qsize);
3018
}
3019
}
3020
check_malloced_chunk(p, nb);
3021
return chunk2mem(p);
3022
}
3023
3024
if (av->treebits != 0) {
3025
bitmap_t vbit = least_bit(av->treebits);
3026
bin_index_t vidx = bit2idx(vbit);
3027
tbinptr* vbin = tbin_at(av, vidx);
3028
tchunkptr bestchunk = *vbin;
3029
tchunkptr c = leftmost_child(bestchunk);
3030
CHUNK_SIZE_T bestsize = chunksize(bestchunk);
3031
tchunkptr leaf;
3032
CHUNK_SIZE_T rsize;
3033
3034
/* Fast path if remainder will replace bestchunk */
3035
if (c == 0) {
3036
rsize = bestsize - nb;
3037
leaf = bestchunk;
3038
3039
if (rsize >= minsize_for_treeindex(vidx) &&
3040
bestchunk->bk == bestchunk) {
3041
tchunkptr r = (tchunkptr)(chunk_at_offset(bestchunk, nb));
3042
3043
set_head(bestchunk, nb | PREV_INUSE);
3044
set_head(r, rsize | PREV_INUSE);
3045
set_foot(r, rsize);
3046
*vbin = r;
3047
r->fd = r;
3048
r->bk = r;
3049
r->child[0] = 0;
3050
r->child[1] = 0;
3051
r->parent = (tchunkptr)vbin;
3052
r->index = vidx;
3053
check_malloced_chunk((mchunkptr)bestchunk, nb);
3054
return chunk2mem(bestchunk);
3055
}
3056
}
3057
else {
3058
do {
3059
CHUNK_SIZE_T csize = chunksize(c);
3060
if (csize < bestsize) {
3061
bestchunk = c;
3062
bestsize = csize;
3063
}
3064
leaf = c;
3065
c = leftmost_child(c);
3066
} while (c != 0);
3067
}
3068
return use_treechunk(av, nb, bestchunk, bestsize, leaf);
3069
}
3070
}
3071
else {
3072
bin_index_t tidx = treebin_index(nb);
3073
bitmap_t tbit = idx2bit(tidx);
3074
3075
if (tbit <= av->treebits) {
3076
tchunkptr bestchunk = 0;
3077
CHUNK_SIZE_T bestsize = MAX_CHUNK_SIZE;
3078
tchunkptr leaf;
3079
bitmap_t vbit;
3080
3081
for (;;) {
3082
if ((tbit & av->treebits) != 0) {
3083
tchunkptr t = *tbin_at(av, tidx);
3084
bin_index_t shift = bitshift_for_index(tidx);
3085
for (;;) {
3086
int dir;
3087
CHUNK_SIZE_T tsize = chunksize(t);
3088
leaf = t;
3089
if (tsize >= nb && tsize < bestsize) {
3090
bestchunk = t;
3091
bestsize = tsize;
3092
if (tsize == nb && t->bk != t)
3093
break;
3094
}
3095
3096
dir = (shift == 0)? 0 : (nb >> shift--) & 1;
3097
t = leaf->child[dir];
3098
if (t == 0) {
3099
shift = 0; /* if forced right, go leftmost from now on */
3100
t = leaf->child[1-dir];
3101
if (t == 0)
3102
break;
3103
}
3104
}
3105
if (bestchunk != 0)
3106
return use_treechunk(av, nb, bestchunk, bestsize, leaf);
3107
}
3108
if (have_fastchunks(av))
3109
malloc_consolidate(av);
3110
else
3111
break;
3112
}
3113
3114
vbit = least_bit(left_bits(tbit) & av->treebits);
3115
if (vbit != 0) {
3116
bin_index_t vidx = bit2idx(vbit);
3117
tbinptr* vbin = tbin_at(av, vidx);
3118
tchunkptr c = *vbin;
3119
do {
3120
CHUNK_SIZE_T csize = chunksize(c);
3121
leaf = c;
3122
if (csize < bestsize) {
3123
bestchunk = c;
3124
bestsize = csize;
3125
}
3126
c = leftmost_child(c);
3127
} while (c != 0);
3128
return use_treechunk(av, nb, bestchunk, bestsize, leaf);
3129
}
3130
}
3131
}
3132
3133
/*
3134
If large enough, split off the chunk bordering the end of memory
3135
(held in av->top). This is called in accord with the best-fit
3136
search rule. In effect, av->top is treated as larger (and thus
3137
less well fitting) than any other available chunk since it can
3138
be extended to be as large as necessary (up to system
3139
limitations).
3140
3141
We require that av->top always exists (i.e., has size >=
3142
MINSIZE) after initialization, so if it would otherwise be
3143
exhuasted by current request, it is replenished. (The main
3144
reason for ensuring it exists is that we may need MINSIZE space
3145
to put in fenceposts in sysmalloc.)
3146
*/
3147
3148
if (av->top != 0) {
3149
mchunkptr topchunk = av->top;
3150
CHUNK_SIZE_T topsize = chunksize(topchunk);
3151
3152
if (topsize >= nb + MINSIZE) {
3153
CHUNK_SIZE_T remainder_size = topsize - nb;
3154
mchunkptr remainder = chunk_at_offset(topchunk, nb);
3155
3156
av->top = remainder;
3157
set_head(topchunk, nb | PREV_INUSE);
3158
set_head(remainder, remainder_size | PREV_INUSE);
3159
3160
check_malloced_chunk(topchunk, nb);
3161
return chunk2mem(topchunk);
3162
}
3163
else if (have_fastchunks(av)) {
3164
malloc_consolidate(av);
3165
}
3166
else
3167
break;
3168
}
3169
else
3170
break;
3171
}
3172
return sysmalloc(av, nb);
3173
}
3174
3175
/*
3176
------------------------------ free ------------------------------
3177
*/
3178
3179
3180
void fREe(Void_t* mem) {
3181
mstate av = get_malloc_state();
3182
3183
mchunkptr p = mem2chunk(mem);
3184
3185
if (mem != 0) {
3186
INTERNAL_SIZE_T rawsize = p->size;
3187
CHUNK_SIZE_T size = chunksize(p);
3188
check_inuse_chunk(p);
3189
3190
/*
3191
If eligible, place chunk on a fastbin so it can be found
3192
and used quickly in malloc.
3193
*/
3194
3195
if ((CHUNK_SIZE_T)(size) <= (CHUNK_SIZE_T)(av->max_fast)
3196
3197
#if TRIM_FASTBINS
3198
/*
3199
If TRIM_FASTBINS set, don't place chunks
3200
bordering top into fastbins
3201
*/
3202
&& (chunk_at_offset(p, size) != av->top)
3203
#endif
3204
) {
3205
3206
mfastbinptr* fb;
3207
set_fastchunks(av);
3208
fb = &(av->fastbins[fastbin_index(size)]);
3209
p->fd = *fb;
3210
*fb = p;
3211
}
3212
3213
else if ((rawsize & IS_MMAPPED) == 0) {
3214
mchunkptr nextchunk = chunk_at_offset(p, size);
3215
CHUNK_SIZE_T nextsize;
3216
3217
if ((rawsize & PREV_INUSE) == 0) {
3218
CHUNK_SIZE_T prevsize = p->prev_size;
3219
size += prevsize;
3220
p = chunk_at_offset(p, -((long) prevsize));
3221
unlink_chunk(av, p, prevsize);
3222
}
3223
3224
nextsize = chunksize(nextchunk);
3225
if (nextchunk == av->top) {
3226
size += nextsize;
3227
set_head(p, size | PREV_INUSE);
3228
av->top = p;
3229
if (size >= av->trim_threshold) {
3230
systrim(av, av->top_pad);
3231
}
3232
}
3233
else {
3234
if (!inuse_bit_at_offset(nextchunk, nextsize)) {
3235
size += nextsize;
3236
unlink_chunk(av, nextchunk, nextsize);
3237
}
3238
else
3239
set_head(nextchunk, nextsize);
3240
3241
set_head(p, size | PREV_INUSE);
3242
set_foot(p, size);
3243
insert_chunk(av, p, size);
3244
}
3245
}
3246
else {
3247
#if HAVE_MMAP
3248
int ret;
3249
INTERNAL_SIZE_T offset = p->prev_size;
3250
av->n_mmaps--;
3251
av->mmapped_mem -= (size + offset);
3252
ret = munmap((char*)p - offset, size + offset);
3253
/* munmap returns non-zero on failure */
3254
assert(ret == 0);
3255
#endif
3256
}
3257
}
3258
}
3259
3260
/*
3261
------------------------- malloc_consolidate -------------------------
3262
3263
malloc_consolidate tears down chunks held in fastbins.
3264
*/
3265
3266
static void malloc_consolidate(mstate av) {
3267
int i;
3268
clear_fastchunks(av);
3269
3270
for (i = 0; i < NFASTBINS; ++i) {
3271
mfastbinptr* fb = &(av->fastbins[i]);
3272
mchunkptr p = *fb;
3273
3274
if (p != 0) {
3275
*fb = 0;
3276
do {
3277
mchunkptr nextp = p->fd;
3278
INTERNAL_SIZE_T rawsize = p->size;
3279
CHUNK_SIZE_T size = chunksize(p);
3280
mchunkptr nextchunk = chunk_at_offset(p, size);
3281
CHUNK_SIZE_T nextsize;
3282
3283
if ((rawsize & PREV_INUSE) == 0) {
3284
CHUNK_SIZE_T prevsize = p->prev_size;
3285
size += prevsize;
3286
p = chunk_at_offset(p, -((long) prevsize));
3287
unlink_chunk(av, p, prevsize);
3288
}
3289
3290
nextsize = chunksize(nextchunk);
3291
if (nextchunk == av->top) {
3292
size += nextsize;
3293
set_head(p, size | PREV_INUSE);
3294
av->top = p;
3295
}
3296
else {
3297
if (!inuse_bit_at_offset(nextchunk, nextsize)) {
3298
size += nextsize;
3299
unlink_chunk(av, nextchunk, nextsize);
3300
}
3301
else
3302
set_head(nextchunk, nextsize);
3303
3304
set_head(p, size | PREV_INUSE);
3305
set_foot(p, size);
3306
3307
insert_chunk(av, p, size);
3308
}
3309
p = nextp;
3310
} while (p != 0);
3311
}
3312
}
3313
}
3314
3315
3316
/*
3317
------------------------------ realloc ------------------------------
3318
*/
3319
3320
3321
Void_t* rEALLOc(Void_t* oldmem, size_t bytes) {
3322
mstate av = get_malloc_state();
3323
3324
INTERNAL_SIZE_T nb; /* padded request size */
3325
3326
mchunkptr oldp; /* chunk corresponding to oldmem */
3327
CHUNK_SIZE_T oldsize; /* its size */
3328
3329
mchunkptr newp; /* chunk to return */
3330
CHUNK_SIZE_T newsize; /* its size */
3331
Void_t* newmem; /* corresponding user mem */
3332
3333
mchunkptr next; /* next contiguous chunk after oldp */
3334
3335
mchunkptr remainder; /* extra space at end of newp */
3336
CHUNK_SIZE_T remainder_size; /* its size */
3337
3338
CHUNK_SIZE_T copysize; /* bytes to copy */
3339
unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */
3340
INTERNAL_SIZE_T* s; /* copy source */
3341
INTERNAL_SIZE_T* d; /* copy destination */
3342
3343
3344
#ifdef REALLOC_ZERO_BYTES_FREES
3345
if (bytes == 0) {
3346
fREe(oldmem);
3347
return 0;
3348
}
3349
#endif
3350
3351
/* realloc of null is supposed to be same as malloc */
3352
if (oldmem == 0) return mALLOc(bytes);
3353
3354
checked_request2size(bytes, nb);
3355
3356
oldp = mem2chunk(oldmem);
3357
oldsize = chunksize(oldp);
3358
3359
check_inuse_chunk(oldp);
3360
3361
if (!chunk_is_mmapped(oldp)) {
3362
3363
if ((CHUNK_SIZE_T)(oldsize) >= (CHUNK_SIZE_T)(nb)) {
3364
/* already big enough; split below */
3365
newp = oldp;
3366
newsize = oldsize;
3367
}
3368
3369
else {
3370
next = chunk_at_offset(oldp, oldsize);
3371
3372
/* Try to expand forward into top */
3373
if (next == av->top &&
3374
(CHUNK_SIZE_T)(newsize = oldsize + chunksize(next)) >=
3375
(CHUNK_SIZE_T)(nb + MINSIZE)) {
3376
set_head_size(oldp, nb);
3377
av->top = chunk_at_offset(oldp, nb);
3378
set_head(av->top, (newsize - nb) | PREV_INUSE);
3379
return chunk2mem(oldp);
3380
}
3381
3382
/* Try to expand forward into next chunk; split off remainder below */
3383
else if (next != av->top &&
3384
!inuse(next) &&
3385
(CHUNK_SIZE_T)(newsize = oldsize + chunksize(next)) >=
3386
(CHUNK_SIZE_T)(nb)) {
3387
newp = oldp;
3388
unlink_chunk(av, next, chunksize(next));
3389
}
3390
3391
/* allocate, copy, free */
3392
else {
3393
newmem = mALLOc(nb - MALLOC_ALIGN_MASK);
3394
if (newmem == 0)
3395
return 0; /* propagate failure */
3396
3397
newp = mem2chunk(newmem);
3398
newsize = chunksize(newp);
3399
3400
/*
3401
Avoid copy if newp is next chunk after oldp.
3402
*/
3403
if (newp == next) {
3404
newsize += oldsize;
3405
newp = oldp;
3406
}
3407
else {
3408
/*
3409
Unroll copy of <= 36 bytes (72 if 8byte sizes)
3410
We know that contents have an odd number of
3411
INTERNAL_SIZE_T-sized words; minimally 3.
3412
*/
3413
3414
copysize = oldsize - SIZE_SZ;
3415
s = (INTERNAL_SIZE_T*)(oldmem);
3416
d = (INTERNAL_SIZE_T*)(newmem);
3417
ncopies = copysize / sizeof(INTERNAL_SIZE_T);
3418
assert(ncopies >= 3);
3419
3420
if (ncopies > 9)
3421
MALLOC_COPY(d, s, copysize);
3422
3423
else {
3424
*(d+0) = *(s+0);
3425
*(d+1) = *(s+1);
3426
*(d+2) = *(s+2);
3427
if (ncopies > 4) {
3428
*(d+3) = *(s+3);
3429
*(d+4) = *(s+4);
3430
if (ncopies > 6) {
3431
*(d+5) = *(s+5);
3432
*(d+6) = *(s+6);
3433
if (ncopies > 8) {
3434
*(d+7) = *(s+7);
3435
*(d+8) = *(s+8);
3436
}
3437
}
3438
}
3439
}
3440
3441
fREe(oldmem);
3442
check_inuse_chunk(newp);
3443
return chunk2mem(newp);
3444
}
3445
}
3446
}
3447
3448
/* If possible, free extra space in old or extended chunk */
3449
3450
assert((CHUNK_SIZE_T)(newsize) >= (CHUNK_SIZE_T)(nb));
3451
3452
remainder_size = newsize - nb;
3453
3454
if (remainder_size < MINSIZE) { /* not enough extra to split off */
3455
set_head_size(newp, newsize);
3456
set_inuse_bit_at_offset(newp, newsize);
3457
}
3458
else { /* split remainder */
3459
remainder = chunk_at_offset(newp, nb);
3460
set_head_size(newp, nb);
3461
set_head(remainder, remainder_size | PREV_INUSE);
3462
/* Mark remainder as inuse so free() won't complain */
3463
set_inuse_bit_at_offset(remainder, remainder_size);
3464
fREe(chunk2mem(remainder));
3465
}
3466
3467
check_inuse_chunk(newp);
3468
return chunk2mem(newp);
3469
}
3470
3471
/*
3472
Handle mmap cases
3473
*/
3474
3475
else {
3476
#if HAVE_MMAP
3477
3478
#if HAVE_MREMAP
3479
INTERNAL_SIZE_T offset = oldp->prev_size;
3480
size_t pagemask = av->pagesize - 1;
3481
char *cp;
3482
CHUNK_SIZE_T sum;
3483
3484
/* Note the extra SIZE_SZ overhead */
3485
newsize = (nb + offset + SIZE_SZ + pagemask) & ~pagemask;
3486
3487
/* don't need to remap if still within same page */
3488
if (oldsize == newsize - offset)
3489
return oldmem;
3490
3491
cp = (char*)mremap((char*)oldp - offset, oldsize + offset, newsize, 1);
3492
3493
if (cp != (char*)MORECORE_FAILURE) {
3494
3495
newp = (mchunkptr)(cp + offset);
3496
set_head(newp, (newsize - offset)|IS_MMAPPED);
3497
3498
assert(aligned_OK(chunk2mem(newp)));
3499
assert((newp->prev_size == offset));
3500
3501
/* update statistics */
3502
sum = av->mmapped_mem += newsize - oldsize;
3503
if (sum > (CHUNK_SIZE_T)(av->max_mmapped_mem))
3504
av->max_mmapped_mem = sum;
3505
sum += av->sbrked_mem;
3506
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
3507
av->max_total_mem = sum;
3508
3509
return chunk2mem(newp);
3510
}
3511
#endif
3512
3513
/* Note the extra SIZE_SZ overhead. */
3514
if ((CHUNK_SIZE_T)(oldsize) >= (CHUNK_SIZE_T)(nb + SIZE_SZ))
3515
newmem = oldmem; /* do nothing */
3516
else {
3517
/* Must alloc, copy, free. */
3518
newmem = mALLOc(nb - MALLOC_ALIGN_MASK);
3519
if (newmem != 0) {
3520
MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
3521
fREe(oldmem);
3522
}
3523
}
3524
return newmem;
3525
3526
#else
3527
/* If !HAVE_MMAP, but chunk_is_mmapped, user must have overwritten mem */
3528
check_malloc_state(av);
3529
MALLOC_FAILURE_ACTION;
3530
return 0;
3531
#endif
3532
}
3533
}
3534
3535
/*
3536
------------------------------ memalign ------------------------------
3537
*/
3538
3539
Void_t* mEMALIGn(size_t alignment, size_t bytes) {
3540
INTERNAL_SIZE_T nb; /* padded request size */
3541
char* m; /* memory returned by malloc call */
3542
mchunkptr p; /* corresponding chunk */
3543
char* brk; /* alignment point within p */
3544
mchunkptr newp; /* chunk to return */
3545
INTERNAL_SIZE_T newsize; /* its size */
3546
INTERNAL_SIZE_T leadsize; /* leading space before alignment point */
3547
mchunkptr remainder; /* spare room at end to split off */
3548
CHUNK_SIZE_T remainder_size; /* its size */
3549
INTERNAL_SIZE_T size;
3550
3551
/* If need less alignment than we give anyway, just relay to malloc */
3552
3553
if (alignment <= MALLOC_ALIGNMENT) return mALLOc(bytes);
3554
3555
/* Otherwise, ensure that it is at least a minimum chunk size */
3556
3557
if (alignment < MINSIZE) alignment = MINSIZE;
3558
3559
/* Make sure alignment is power of 2 (in case MINSIZE is not). */
3560
if ((alignment & (alignment - 1)) != 0) {
3561
size_t a = MALLOC_ALIGNMENT * 2;
3562
while ((CHUNK_SIZE_T)a < (CHUNK_SIZE_T)alignment) a <<= 1;
3563
alignment = a;
3564
}
3565
3566
checked_request2size(bytes, nb);
3567
3568
/*
3569
Strategy: find a spot within that chunk that meets the alignment
3570
request, and then possibly free the leading and trailing space.
3571
*/
3572
3573
3574
/* Call malloc with worst case padding to hit alignment. */
3575
3576
m = (char*)(mALLOc(nb + alignment + MINSIZE));
3577
3578
if (m == 0) return 0; /* propagate failure */
3579
3580
p = mem2chunk(m);
3581
3582
if ((((PTR_UINT)(m)) % alignment) != 0) { /* misaligned */
3583
3584
/*
3585
Find an aligned spot inside chunk. Since we need to give back
3586
leading space in a chunk of at least MINSIZE, if the first
3587
calculation places us at a spot with less than MINSIZE leader,
3588
we can move to the next aligned spot -- we've allocated enough
3589
total room so that this is always possible.
3590
*/
3591
3592
brk = (char*)mem2chunk((PTR_UINT)(((PTR_UINT)(m + alignment - 1)) &
3593
-((signed long) alignment)));
3594
if ((CHUNK_SIZE_T)(brk - (char*)(p)) < MINSIZE)
3595
brk += alignment;
3596
3597
newp = (mchunkptr)brk;
3598
leadsize = brk - (char*)(p);
3599
newsize = chunksize(p) - leadsize;
3600
3601
/* For mmapped chunks, just adjust offset */
3602
if (chunk_is_mmapped(p)) {
3603
newp->prev_size = p->prev_size + leadsize;
3604
set_head(newp, newsize|IS_MMAPPED);
3605
return chunk2mem(newp);
3606
}
3607
3608
/* Otherwise, give back leader, use the rest */
3609
set_head(newp, newsize | PREV_INUSE);
3610
set_inuse_bit_at_offset(newp, newsize);
3611
set_head_size(p, leadsize);
3612
fREe(chunk2mem(p));
3613
p = newp;
3614
3615
assert (newsize >= nb &&
3616
(((PTR_UINT)(chunk2mem(p))) % alignment) == 0);
3617
}
3618
3619
/* Also give back spare room at the end */
3620
if (!chunk_is_mmapped(p)) {
3621
size = chunksize(p);
3622
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb + MINSIZE)) {
3623
remainder_size = size - nb;
3624
remainder = chunk_at_offset(p, nb);
3625
set_head(remainder, remainder_size | PREV_INUSE);
3626
set_head_size(p, nb);
3627
fREe(chunk2mem(remainder));
3628
}
3629
}
3630
3631
check_inuse_chunk(p);
3632
return chunk2mem(p);
3633
}
3634
3635
/*
3636
------------------------------ calloc ------------------------------
3637
*/
3638
3639
Void_t* cALLOc(size_t n_elements, size_t elem_size) {
3640
Void_t* mem = mALLOc(n_elements * elem_size);
3641
3642
if (mem != 0) {
3643
mchunkptr p = mem2chunk(mem);
3644
INTERNAL_SIZE_T* d = (INTERNAL_SIZE_T*)mem;
3645
3646
if (!chunk_is_mmapped(p))
3647
{
3648
/*
3649
Unroll clear of <= 36 bytes (72 if 8byte sizes)
3650
We know that contents have an odd number of
3651
INTERNAL_SIZE_T-sized words; minimally 3.
3652
*/
3653
3654
CHUNK_SIZE_T clearsize = chunksize(p) - SIZE_SZ;
3655
CHUNK_SIZE_T nclears = clearsize / sizeof(INTERNAL_SIZE_T);
3656
assert(nclears >= 3);
3657
3658
if (nclears > 9)
3659
MALLOC_ZERO(d, clearsize);
3660
3661
else {
3662
*(d+0) = 0;
3663
*(d+1) = 0;
3664
*(d+2) = 0;
3665
if (nclears > 4) {
3666
*(d+3) = 0;
3667
*(d+4) = 0;
3668
if (nclears > 6) {
3669
*(d+5) = 0;
3670
*(d+6) = 0;
3671
if (nclears > 8) {
3672
*(d+7) = 0;
3673
*(d+8) = 0;
3674
}
3675
}
3676
}
3677
}
3678
}
3679
#if ! MMAP_CLEARS
3680
else
3681
{
3682
/*
3683
Note the additional SIZE_SZ
3684
*/
3685
CHUNK_SIZE_T clearsize = chunksize(p) - 2*SIZE_SZ;
3686
MALLOC_ZERO(d, clearsize);
3687
}
3688
#endif
3689
}
3690
return mem;
3691
}
3692
3693
/*
3694
------------------------------ cfree ------------------------------
3695
*/
3696
3697
void cFREe(Void_t *mem) {
3698
fREe(mem);
3699
}
3700
3701
/*
3702
------------------------- independent_calloc -------------------------
3703
*/
3704
3705
3706
Void_t** iCALLOc(size_t n_elements, size_t elem_size, Void_t* chunks[]) {
3707
size_t sz = elem_size; /* serves as 1-element array */
3708
/* opts arg of 3 means all elements are same size, and should be cleared */
3709
return iALLOc(n_elements, &sz, 3, chunks);
3710
}
3711
3712
/*
3713
------------------------- independent_comalloc -------------------------
3714
*/
3715
3716
Void_t** iCOMALLOc(size_t n_elements, size_t sizes[], Void_t* chunks[]) {
3717
return iALLOc(n_elements, sizes, 0, chunks);
3718
}
3719
3720
3721
/*
3722
------------------------------ ialloc ------------------------------
3723
ialloc provides common support for independent_X routines, handling all of
3724
the combinations that can result.
3725
3726
The opts arg has:
3727
bit 0 set if all elements are same size (using sizes[0])
3728
bit 1 set if elements should be zeroed
3729
*/
3730
3731
3732
static Void_t** iALLOc(size_t n_elements,
3733
size_t* sizes,
3734
int opts,
3735
Void_t* chunks[]) {
3736
mstate av = get_malloc_state();
3737
INTERNAL_SIZE_T element_size; /* chunksize of each element, if all same */
3738
INTERNAL_SIZE_T contents_size; /* total size of elements */
3739
INTERNAL_SIZE_T array_size; /* request size of pointer array */
3740
Void_t* mem; /* malloced aggregate space */
3741
mchunkptr p; /* corresponding chunk */
3742
CHUNK_SIZE_T remainder_size; /* remaining bytes while splitting */
3743
Void_t** marray; /* either "chunks" or malloced ptr array */
3744
mchunkptr array_chunk; /* chunk for malloced ptr array */
3745
unsigned int mprops; /* to disable mmap */
3746
CHUNK_SIZE_T size;
3747
size_t i;
3748
3749
ensure_initialization(av);
3750
3751
/* compute array length, if needed */
3752
if (chunks != 0) {
3753
if (n_elements == 0)
3754
return chunks; /* nothing to do */
3755
marray = chunks;
3756
array_size = 0;
3757
}
3758
else {
3759
/* if empty req, must still return chunk representing empty array */
3760
if (n_elements == 0)
3761
return (Void_t**) mALLOc(0);
3762
marray = 0;
3763
array_size = request2size(n_elements * (sizeof(Void_t*)));
3764
}
3765
3766
/* compute total element size */
3767
if (opts & 0x1) { /* all-same-size */
3768
element_size = request2size(*sizes);
3769
contents_size = n_elements * element_size;
3770
}
3771
else { /* add up all the sizes */
3772
element_size = 0;
3773
contents_size = 0;
3774
for (i = 0; i != n_elements; ++i)
3775
contents_size += request2size(sizes[i]);
3776
}
3777
3778
/* subtract out alignment bytes from total to minimize overallocation */
3779
size = contents_size + array_size - MALLOC_ALIGN_MASK;
3780
3781
/*
3782
Allocate the aggregate chunk.
3783
But first disable mmap so malloc won't use it, since
3784
we would not be able to later free/realloc space internal
3785
to a segregated mmap region.
3786
*/
3787
3788
mprops = av->sysctl; /* disable mmap */
3789
disable_mmap(av);
3790
mem = mALLOc(size);
3791
av->sysctl = mprops; /* reset mmap */
3792
if (mem == 0)
3793
return 0;
3794
3795
p = mem2chunk(mem);
3796
assert(!chunk_is_mmapped(p));
3797
remainder_size = chunksize(p);
3798
3799
3800
if (opts & 0x2) { /* optionally clear the elements */
3801
MALLOC_ZERO(mem, remainder_size - SIZE_SZ - array_size);
3802
}
3803
3804
/* If not provided, allocate the pointer array as final part of chunk */
3805
if (marray == 0) {
3806
array_chunk = chunk_at_offset(p, contents_size);
3807
marray = (Void_t**) (chunk2mem(array_chunk));
3808
set_head(array_chunk, (remainder_size - contents_size) | PREV_INUSE);
3809
remainder_size = contents_size;
3810
}
3811
3812
/* split out elements */
3813
for (i = 0; ; ++i) {
3814
marray[i] = chunk2mem(p);
3815
if (i != n_elements-1) {
3816
if (element_size != 0)
3817
size = element_size;
3818
else
3819
size = request2size(sizes[i]);
3820
remainder_size -= size;
3821
set_head(p, size | PREV_INUSE);
3822
p = chunk_at_offset(p, size);
3823
}
3824
else { /* the final element absorbs any overallocation slop */
3825
set_head(p, remainder_size | PREV_INUSE);
3826
break;
3827
}
3828
}
3829
3830
#if DEBUG
3831
if (marray != chunks) {
3832
/* final element must have exactly exhausted chunk */
3833
if (element_size != 0)
3834
assert(remainder_size == element_size);
3835
else
3836
assert(remainder_size == request2size(sizes[i]));
3837
check_inuse_chunk(mem2chunk(marray));
3838
}
3839
3840
for (i = 0; i != n_elements; ++i)
3841
check_inuse_chunk(mem2chunk(marray[i]));
3842
#endif
3843
3844
return marray;
3845
}
3846
3847
3848
/*
3849
------------------------------ valloc ------------------------------
3850
*/
3851
3852
Void_t* vALLOc(size_t bytes) {
3853
mstate av = get_malloc_state();
3854
ensure_initialization(av);
3855
return mEMALIGn(av->pagesize, bytes);
3856
}
3857
3858
/*
3859
------------------------------ pvalloc ------------------------------
3860
*/
3861
3862
3863
Void_t* pVALLOc(size_t bytes) {
3864
mstate av = get_malloc_state();
3865
size_t pagesz;
3866
3867
ensure_initialization(av);
3868
pagesz = av->pagesize;
3869
return mEMALIGn(pagesz, (bytes + pagesz - 1) & ~(pagesz - 1));
3870
}
3871
3872
3873
/*
3874
------------------------------ malloc_trim ------------------------------
3875
*/
3876
3877
int mTRIm(size_t pad) {
3878
mstate av = get_malloc_state();
3879
return systrim(av, pad);
3880
}
3881
3882
3883
/*
3884
------------------------- malloc_usable_size -------------------------
3885
*/
3886
3887
size_t mUSABLe(Void_t* mem) {
3888
mchunkptr p;
3889
if (mem != 0) {
3890
p = mem2chunk(mem);
3891
if (chunk_is_mmapped(p))
3892
return chunksize(p) - 2*SIZE_SZ;
3893
else if (inuse(p))
3894
return chunksize(p) - SIZE_SZ;
3895
}
3896
return 0;
3897
}
3898
3899
/*
3900
------------------------------ mallinfo ------------------------------
3901
*/
3902
3903
/*
3904
Recursive helper function for mallinfo
3905
*/
3906
3907
static void count_tree_blocks(tchunkptr t, int* pcount, INTERNAL_SIZE_T* pavail) {
3908
while (t != 0) {
3909
tchunkptr p = t->bk;
3910
do {
3911
(*pcount)++;
3912
*pavail += chunksize(p);
3913
p = p->bk;
3914
} while (p != t);
3915
if (t->child[0] != 0)
3916
count_tree_blocks(t->child[0], pcount, pavail);
3917
t = t->child[1];
3918
}
3919
}
3920
3921
3922
3923
struct mallinfo mALLINFo()
3924
{
3925
mstate av = get_malloc_state();
3926
struct mallinfo mi;
3927
INTERNAL_SIZE_T avail;
3928
INTERNAL_SIZE_T topsize;
3929
int nblocks;
3930
INTERNAL_SIZE_T fastavail;
3931
int nfastblocks;
3932
mchunkptr p;
3933
3934
if (av->top == 0) {
3935
avail = 0;
3936
topsize = 0;
3937
nblocks = 0;
3938
}
3939
else {
3940
int i;
3941
check_malloc_state(av);
3942
3943
topsize = chunksize(av->top);
3944
avail = topsize;
3945
nblocks = 1; /* top always exists */
3946
3947
/* traverse fastbins */
3948
nfastblocks = 0;
3949
fastavail = 0;
3950
3951
for (i = 0; i < NFASTBINS; ++i) {
3952
for (p = av->fastbins[i]; p != 0; p = p->fd) {
3953
++nfastblocks;
3954
fastavail += chunksize(p);
3955
}
3956
}
3957
3958
avail += fastavail;
3959
3960
/* traverse small bins */
3961
for (i = 2; i < NBINS; ++i) {
3962
mbinptr b = bin_at(av, i);
3963
mchunkptr p;
3964
for (p = b->bk; p != b; p = p->bk) {
3965
++nblocks;
3966
avail += chunksize(p);
3967
}
3968
}
3969
3970
/* traverse tree bins */
3971
for (i = 0; i < NBINS; ++i) {
3972
tchunkptr t = *(tbin_at(av, i));
3973
if (t != 0)
3974
count_tree_blocks(t, &nblocks, &avail);
3975
}
3976
}
3977
3978
mi.smblks = nfastblocks;
3979
mi.smblks = 0;
3980
mi.ordblks = nblocks;
3981
mi.fordblks = avail;
3982
mi.uordblks = av->sbrked_mem - avail;
3983
mi.arena = av->sbrked_mem;
3984
mi.hblks = av->n_mmaps;
3985
mi.hblkhd = av->mmapped_mem;
3986
mi.fsmblks = 0;
3987
mi.keepcost = topsize;
3988
mi.usmblks = av->max_total_mem;
3989
return mi;
3990
}
3991
3992
/*
3993
------------------------------ malloc_stats ------------------------------
3994
*/
3995
3996
void mSTATs() {
3997
struct mallinfo mi = mALLINFo();
3998
3999
#ifdef WIN32
4000
{
4001
CHUNK_SIZE_T free, reserved, committed;
4002
vminfo (&free, &reserved, &committed);
4003
fprintf(stderr, "free bytes = %10lu\n",
4004
free);
4005
fprintf(stderr, "reserved bytes = %10lu\n",
4006
reserved);
4007
fprintf(stderr, "committed bytes = %10lu\n",
4008
committed);
4009
}
4010
#endif
4011
4012
4013
fprintf(stderr, "max system bytes = %10lu\n",
4014
(CHUNK_SIZE_T)(mi.usmblks));
4015
fprintf(stderr, "system bytes = %10lu\n",
4016
(CHUNK_SIZE_T)(mi.arena + mi.hblkhd));
4017
fprintf(stderr, "in use bytes = %10lu\n",
4018
(CHUNK_SIZE_T)(mi.uordblks + mi.hblkhd));
4019
4020
#if 0
4021
fprintf(stderr, "n0 = %10u\n", n0);
4022
fprintf(stderr, "n1 = %10u\n", n1);
4023
fprintf(stderr, "n2 = %10u\n", n2);
4024
fprintf(stderr, "n3 = %10u\n", n3);
4025
fprintf(stderr, "n4 = %10u\n", n4);
4026
fprintf(stderr, "n5 = %10u\n", n5);
4027
fprintf(stderr, "n6 = %10u\n", n6);
4028
fprintf(stderr, "n7 = %10u\n", n7);
4029
fprintf(stderr, "n8 = %10u\n", n8);
4030
#endif
4031
4032
4033
#ifdef WIN32
4034
{
4035
CHUNK_SIZE_T kernel, user;
4036
if (cpuinfo (TRUE, &kernel, &user)) {
4037
fprintf(stderr, "kernel ms = %10lu\n",
4038
kernel);
4039
fprintf(stderr, "user ms = %10lu\n",
4040
user);
4041
}
4042
}
4043
#endif
4044
}
4045
4046
4047
/*
4048
------------------------------ mallopt ------------------------------
4049
*/
4050
4051
int mALLOPt(int param_number, int value) {
4052
mstate av = get_malloc_state();
4053
4054
ensure_initialization(av);
4055
4056
switch(param_number) {
4057
case M_MXFAST:
4058
malloc_consolidate(av);
4059
if (value >= 0 && value <= MAX_FAST_SIZE) {
4060
set_max_fast(av, value);
4061
return 1;
4062
}
4063
else
4064
return 0;
4065
4066
case M_TRIM_THRESHOLD:
4067
av->trim_threshold = value;
4068
return 1;
4069
4070
case M_TOP_PAD:
4071
av->top_pad = value;
4072
return 1;
4073
4074
case M_MMAP_THRESHOLD:
4075
av->mmap_threshold = value;
4076
return 1;
4077
4078
case M_MMAP_MAX:
4079
#if !HAVE_MMAP
4080
if (value != 0)
4081
return 0;
4082
#endif
4083
av->n_mmaps_max = value;
4084
return 1;
4085
4086
default:
4087
return 0;
4088
}
4089
}
4090
4091
/* ----------- Routines dealing with system allocation -------------- */
4092
4093
#if HAVE_MMAP
4094
static mchunkptr mmap_malloc(mstate av, INTERNAL_SIZE_T nb) {
4095
char* mm; /* return value from mmap call*/
4096
CHUNK_SIZE_T sum; /* for updating stats */
4097
mchunkptr p; /* the allocated/returned chunk */
4098
long size;
4099
INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
4100
long correction;
4101
size_t pagemask = av->pagesize - 1;
4102
4103
/*
4104
Round up size to nearest page. For mmapped chunks, the overhead
4105
is one SIZE_SZ unit larger than for normal chunks, because there
4106
is no following chunk whose prev_size field could be used.
4107
*/
4108
size = (nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
4109
4110
/* Don't try if size wraps around 0 */
4111
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb)) {
4112
4113
mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
4114
4115
if (mm != (char*)(MORECORE_FAILURE)) {
4116
4117
/*
4118
The offset to the start of the mmapped region is stored
4119
in the prev_size field of the chunk. This allows us to adjust
4120
returned start address to meet alignment requirements here
4121
and in memalign(), and still be able to compute proper
4122
address argument for later munmap in free() and realloc().
4123
*/
4124
4125
front_misalign = (INTERNAL_SIZE_T)chunk2mem(mm) & MALLOC_ALIGN_MASK;
4126
if (front_misalign > 0) {
4127
correction = MALLOC_ALIGNMENT - front_misalign;
4128
p = (mchunkptr)(mm + correction);
4129
p->prev_size = correction;
4130
set_head(p, (size - correction) |IS_MMAPPED);
4131
}
4132
else {
4133
p = (mchunkptr)mm;
4134
p->prev_size = 0;
4135
set_head(p, size|IS_MMAPPED);
4136
}
4137
4138
/* update statistics */
4139
4140
if (++av->n_mmaps > av->max_n_mmaps)
4141
av->max_n_mmaps = av->n_mmaps;
4142
4143
sum = av->mmapped_mem += size;
4144
if (sum > (CHUNK_SIZE_T)(av->max_mmapped_mem))
4145
av->max_mmapped_mem = sum;
4146
sum += av->sbrked_mem;
4147
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
4148
av->max_total_mem = sum;
4149
4150
check_chunk(p);
4151
4152
return p;
4153
}
4154
}
4155
return 0;
4156
}
4157
#endif
4158
4159
4160
/*
4161
sysmalloc handles malloc cases requiring more memory from the system.
4162
On entry, it is assumed that av->top does not have enough
4163
space to service request for nb bytes, thus requiring that av->top
4164
be extended or replaced.
4165
*/
4166
4167
static Void_t* sysmalloc(mstate av, CHUNK_SIZE_T nb) {
4168
mchunkptr old_top; /* incoming value of av->top */
4169
INTERNAL_SIZE_T old_size; /* its size */
4170
char* old_end; /* its end address */
4171
4172
long size; /* arg to first MORECORE or mmap call */
4173
char* brk; /* return value from MORECORE */
4174
4175
long correction; /* arg to 2nd MORECORE call */
4176
char* snd_brk; /* 2nd return val */
4177
4178
INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
4179
INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */
4180
char* aligned_brk; /* aligned offset into brk */
4181
4182
mchunkptr p; /* the allocated/returned chunk */
4183
mchunkptr remainder; /* remainder from allocation */
4184
CHUNK_SIZE_T remainder_size; /* its size */
4185
4186
CHUNK_SIZE_T sum; /* for updating stats */
4187
4188
size_t pagemask;
4189
4190
/*
4191
Initialize av if necessary
4192
*/
4193
if (av->top == 0) {
4194
malloc_init_state(av);
4195
/* to allow call solely for initialization */
4196
if (nb == 0)
4197
return 0;
4198
}
4199
4200
4201
#if HAVE_MMAP
4202
/*
4203
If have mmap, and the request size meets the mmap threshold, and
4204
the system supports mmap, and there are few enough currently
4205
allocated mmapped regions, try to directly map this request
4206
rather than expanding top.
4207
*/
4208
4209
if ((CHUNK_SIZE_T)(nb) >= (CHUNK_SIZE_T)(av->mmap_threshold) &&
4210
(av->n_mmaps < av->n_mmaps_max) &&
4211
!mmap_disabled(av)) {
4212
Void_t* mp = mmap_malloc(av, nb);
4213
if (mp != 0)
4214
return chunk2mem(mp);
4215
}
4216
#endif
4217
4218
4219
pagemask = av->pagesize - 1;
4220
4221
/* Record incoming configuration of top */
4222
4223
old_top = av->top;
4224
old_size = chunksize(old_top);
4225
old_end = (char*)(chunk_at_offset(old_top, old_size));
4226
4227
brk = snd_brk = (char*)(MORECORE_FAILURE);
4228
4229
/*
4230
If not the first time through, we require old_size to be
4231
at least MINSIZE and to have prev_inuse set.
4232
*/
4233
4234
assert((old_top == (mchunkptr)(&(av->initial_top)) && old_size == 0) ||
4235
((CHUNK_SIZE_T) (old_size) >= MINSIZE &&
4236
prev_inuse(old_top)));
4237
4238
/* Precondition: not enough current space to satisfy nb request */
4239
assert((CHUNK_SIZE_T)(old_size) < (CHUNK_SIZE_T)(nb + MINSIZE));
4240
4241
/* Request enough space for nb + pad + overhead */
4242
4243
size = nb + av->top_pad + MINSIZE;
4244
4245
/*
4246
If contiguous, we can subtract out existing space that we hope to
4247
combine with new space. We add it back later only if
4248
we don't actually get contiguous space.
4249
*/
4250
4251
if (contiguous(av))
4252
size -= old_size;
4253
4254
/*
4255
Round to a multiple of page size.
4256
If MORECORE is not contiguous, this ensures that we only call it
4257
with whole-page arguments. And if MORECORE is contiguous and
4258
this is not first time through, this preserves page-alignment of
4259
previous calls. Otherwise, we correct to page-align below.
4260
*/
4261
4262
size = (size + pagemask) & ~pagemask;
4263
4264
/*
4265
Don't try to call MORECORE if argument is so big as to appear
4266
negative. Note that since mmap takes size_t arg, it may succeed
4267
below even if we cannot call MORECORE.
4268
*/
4269
4270
if (size > 0)
4271
brk = (char*)(MORECORE(size));
4272
4273
/*
4274
If have mmap, try using it as a backup when MORECORE fails or
4275
cannot be used. This is worth doing on systems that have "holes" in
4276
address space, so sbrk cannot extend to give contiguous space, but
4277
space is available elsewhere. Note that we ignore mmap max count
4278
and threshold limits, since the space will not be used as a
4279
segregated mmap region.
4280
*/
4281
4282
#if HAVE_MMAP
4283
if (brk == (char*)(MORECORE_FAILURE)) {
4284
4285
/* Cannot merge with old top, so add its size back in */
4286
if (contiguous(av))
4287
size = (size + old_size + pagemask) & ~pagemask;
4288
4289
/* If we are relying on mmap as backup, then use larger units */
4290
if ((CHUNK_SIZE_T)(size) < (CHUNK_SIZE_T)(MMAP_AS_MORECORE_SIZE))
4291
size = MMAP_AS_MORECORE_SIZE;
4292
4293
/* Don't try if size wraps around 0 */
4294
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb)) {
4295
4296
brk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
4297
4298
if (brk != (char*)(MORECORE_FAILURE)) {
4299
4300
/* We do not need, and cannot use, another sbrk call to find end */
4301
snd_brk = brk + size;
4302
4303
/*
4304
Record that we no longer have a contiguous sbrk region.
4305
After the first time mmap is used as backup, we do not
4306
ever rely on contiguous space since this could incorrectly
4307
bridge regions.
4308
*/
4309
set_noncontiguous(av);
4310
}
4311
}
4312
}
4313
#endif
4314
4315
if (brk != (char*)(MORECORE_FAILURE)) {
4316
av->sbrked_mem += size;
4317
4318
/*
4319
If MORECORE extends previous space, we can likewise extend top size.
4320
*/
4321
4322
if (brk == old_end && snd_brk == (char*)(MORECORE_FAILURE)) {
4323
set_head(old_top, (size + old_size) | PREV_INUSE);
4324
}
4325
4326
/*
4327
Otherwise, make adjustments:
4328
4329
* If the first time through or noncontiguous, we need to call sbrk
4330
just to find out where the end of memory lies.
4331
4332
* We need to ensure that all returned chunks from malloc will meet
4333
MALLOC_ALIGNMENT
4334
4335
* If there was an intervening foreign sbrk, we need to adjust sbrk
4336
request size to account for fact that we will not be able to
4337
combine new space with existing space in old_top.
4338
4339
* Almost all systems internally allocate whole pages at a time, in
4340
which case we might as well use the whole last page of request.
4341
So we allocate enough more memory to hit a page boundary now,
4342
which in turn causes future contiguous calls to page-align.
4343
*/
4344
4345
else {
4346
front_misalign = 0;
4347
end_misalign = 0;
4348
correction = 0;
4349
aligned_brk = brk;
4350
4351
/*
4352
If MORECORE returns an address lower than we have seen before,
4353
we know it isn't really contiguous. This and some subsequent
4354
checks help cope with non-conforming MORECORE functions and
4355
the presence of "foreign" calls to MORECORE from outside of
4356
malloc or by other threads. We cannot guarantee to detect
4357
these in all cases, but cope with the ones we do detect.
4358
*/
4359
if (contiguous(av) && old_size != 0 && brk < old_end) {
4360
set_noncontiguous(av);
4361
}
4362
4363
/* handle contiguous cases */
4364
if (contiguous(av)) {
4365
4366
/*
4367
We can tolerate forward non-contiguities here (usually due
4368
to foreign calls) but treat them as part of our space for
4369
stats reporting.
4370
*/
4371
if (old_size != 0)
4372
av->sbrked_mem += brk - old_end;
4373
4374
/* Guarantee alignment of first new chunk made from this space */
4375
4376
front_misalign = (INTERNAL_SIZE_T)chunk2mem(brk) & MALLOC_ALIGN_MASK;
4377
if (front_misalign > 0) {
4378
4379
/*
4380
Skip over some bytes to arrive at an aligned position.
4381
We don't need to specially mark these wasted front bytes.
4382
They will never be accessed anyway because
4383
prev_inuse of av->top (and any chunk created from its start)
4384
is always true after initialization.
4385
*/
4386
4387
correction = MALLOC_ALIGNMENT - front_misalign;
4388
aligned_brk += correction;
4389
}
4390
4391
/*
4392
If this isn't adjacent to existing space, then we will not
4393
be able to merge with old_top space, so must add to 2nd request.
4394
*/
4395
4396
correction += old_size;
4397
4398
/* Extend the end address to hit a page boundary */
4399
end_misalign = (INTERNAL_SIZE_T)(brk + size + correction);
4400
correction += ((end_misalign + pagemask) & ~pagemask) - end_misalign;
4401
4402
assert(correction >= 0);
4403
snd_brk = (char*)(MORECORE(correction));
4404
4405
if (snd_brk == (char*)(MORECORE_FAILURE)) {
4406
/*
4407
If can't allocate correction, try to at least find out current
4408
brk. It might be enough to proceed without failing.
4409
*/
4410
correction = 0;
4411
snd_brk = (char*)(MORECORE(0));
4412
}
4413
else if (snd_brk < brk) {
4414
/*
4415
If the second call gives noncontiguous space even though
4416
it says it won't, the only course of action is to ignore
4417
results of second call, and conservatively estimate where
4418
the first call left us. Also set noncontiguous, so this
4419
won't happen again, leaving at most one hole.
4420
4421
Note that this check is intrinsically incomplete. Because
4422
MORECORE is allowed to give more space than we ask for,
4423
there is no reliable way to detect a noncontiguity
4424
producing a forward gap for the second call.
4425
*/
4426
snd_brk = brk + size;
4427
correction = 0;
4428
set_noncontiguous(av);
4429
}
4430
4431
}
4432
4433
/* handle non-contiguous cases */
4434
else {
4435
/* MORECORE/mmap must correctly align */
4436
assert(aligned_OK(chunk2mem(brk)));
4437
4438
/* Find out current end of memory */
4439
if (snd_brk == (char*)(MORECORE_FAILURE)) {
4440
snd_brk = (char*)(MORECORE(0));
4441
av->sbrked_mem += snd_brk - brk - size;
4442
}
4443
}
4444
4445
/* Adjust top based on results of second sbrk */
4446
if (snd_brk != (char*)(MORECORE_FAILURE)) {
4447
av->top = (mchunkptr)aligned_brk;
4448
set_head(av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
4449
av->sbrked_mem += correction;
4450
4451
/*
4452
If not the first time through, we either have a
4453
gap due to foreign sbrk or a non-contiguous region. Insert a
4454
double fencepost at old_top to prevent consolidation with space
4455
we don't own. These fenceposts are artificial chunks that are
4456
marked as inuse and are in any case too small to use. We need
4457
two to make sizes and alignments work out.
4458
*/
4459
4460
if (old_size != 0) {
4461
/*
4462
Shrink old_top to insert fenceposts, keeping size a
4463
multiple of MALLOC_ALIGNMENT. We know there is at least
4464
enough space in old_top to do this.
4465
*/
4466
old_size = (old_size - 3*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
4467
set_head(old_top, old_size | PREV_INUSE);
4468
4469
/*
4470
Note that the following assignments completely overwrite
4471
old_top when old_size was previously MINSIZE. This is
4472
intentional. We need the fencepost, even if old_top
4473
otherwise gets lost.
4474
*/
4475
chunk_at_offset(old_top, old_size )->size =
4476
SIZE_SZ|PREV_INUSE;
4477
4478
chunk_at_offset(old_top, old_size + SIZE_SZ)->size =
4479
SIZE_SZ|PREV_INUSE;
4480
4481
/*
4482
If possible, release the rest, suppressing trimming.
4483
*/
4484
if (old_size >= MINSIZE) {
4485
unsigned int mprops = av->sysctl;
4486
disable_trim(av);
4487
fREe(chunk2mem(old_top));
4488
av->sysctl = mprops;
4489
}
4490
}
4491
}
4492
}
4493
4494
/* Update statistics */
4495
sum = av->sbrked_mem;
4496
if (sum > (CHUNK_SIZE_T)(av->max_sbrked_mem))
4497
av->max_sbrked_mem = sum;
4498
4499
sum += av->mmapped_mem;
4500
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
4501
av->max_total_mem = sum;
4502
4503
4504
/* finally, do the allocation */
4505
4506
p = av->top;
4507
size = chunksize(p);
4508
4509
/* check that one of the above allocation paths succeeded */
4510
if ((CHUNK_SIZE_T)(size) >= (CHUNK_SIZE_T)(nb + MINSIZE)) {
4511
remainder_size = size - nb;
4512
remainder = chunk_at_offset(p, nb);
4513
av->top = remainder;
4514
set_head(p, nb | PREV_INUSE);
4515
set_head(remainder, remainder_size | PREV_INUSE);
4516
check_malloced_chunk(p, nb);
4517
check_malloc_state(av);
4518
return chunk2mem(p);
4519
}
4520
4521
}
4522
4523
/* catch all failure paths */
4524
check_malloc_state(av);
4525
MALLOC_FAILURE_ACTION;
4526
return 0;
4527
}
4528
4529
4530
/*
4531
systrim is an inverse of sorts to sysmalloc. It gives memory back
4532
to the system (via negative arguments to sbrk) if there is unused
4533
memory at the `high' end of the malloc pool. It is called
4534
automatically by free() when top space exceeds the trim
4535
threshold. It is also called by the public malloc_trim routine. It
4536
returns 1 if it actually released any memory, else 0.
4537
*/
4538
4539
static int systrim(mstate av, size_t pad) {
4540
long top_size; /* Amount of top-most memory */
4541
long extra; /* Amount to release */
4542
long released; /* Amount actually released */
4543
char* current_brk; /* address returned by pre-check sbrk call */
4544
char* new_brk; /* address returned by post-check sbrk call */
4545
size_t pagesz;
4546
4547
ensure_initialization(av);
4548
4549
if (have_fastchunks(av))
4550
malloc_consolidate(av);
4551
4552
if (!trim_disabled(av)) {
4553
4554
#ifndef MORECORE_CANNOT_TRIM
4555
4556
pagesz = av->pagesize;
4557
top_size = chunksize(av->top);
4558
4559
/* Release in pagesize units, keeping at least one page */
4560
extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
4561
4562
if (extra > 0) {
4563
4564
/*
4565
Only proceed if end of memory is where we last set it.
4566
This avoids problems if there were foreign sbrk calls.
4567
*/
4568
current_brk = (char*)(MORECORE(0));
4569
if (current_brk == (char*)(av->top) + top_size) {
4570
4571
/*
4572
Attempt to release memory. We ignore MORECORE return value,
4573
and instead call again to find out where new end of memory is.
4574
This avoids problems if first call releases less than we asked,
4575
of if failure somehow altered brk value. (We could still
4576
encounter problems if it altered brk in some very bad way,
4577
but the only thing we can do is adjust anyway, which will cause
4578
some downstream failure.)
4579
*/
4580
4581
MORECORE(-extra);
4582
new_brk = (char*)(MORECORE(0));
4583
4584
if (new_brk != (char*)MORECORE_FAILURE) {
4585
released = (long)(current_brk - new_brk);
4586
4587
if (released != 0) {
4588
/* Success. Adjust top. */
4589
av->sbrked_mem -= released;
4590
set_head(av->top, (top_size - released) | PREV_INUSE);
4591
check_malloc_state(av);
4592
return 1;
4593
}
4594
}
4595
}
4596
}
4597
}
4598
#endif
4599
return 0;
4600
}
4601
4602
4603
/*
4604
-------------------- Alternative MORECORE functions --------------------
4605
*/
4606
4607
4608
/*
4609
General Requirements for MORECORE.
4610
4611
The MORECORE function must have the following properties:
4612
4613
If MORECORE_CONTIGUOUS is false:
4614
4615
* MORECORE must allocate in multiples of pagesize. It will
4616
only be called with arguments that are multiples of pagesize.
4617
4618
* MORECORE(0) must return an address that is at least
4619
MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
4620
4621
else (i.e. If MORECORE_CONTIGUOUS is true):
4622
4623
* Consecutive calls to MORECORE with positive arguments
4624
return increasing addresses, indicating that space has been
4625
contiguously extended.
4626
4627
* MORECORE need not allocate in multiples of pagesize.
4628
Calls to MORECORE need not have args of multiples of pagesize.
4629
4630
* MORECORE need not page-align.
4631
4632
In either case:
4633
4634
* MORECORE may allocate more memory than requested. (Or even less,
4635
but this will generally result in a malloc failure.)
4636
4637
* MORECORE must not allocate memory when given argument zero, but
4638
instead return one past the end address of memory from previous
4639
nonzero call. This malloc does NOT call MORECORE(0)
4640
until at least one call with positive arguments is made, so
4641
the initial value returned is not important.
4642
4643
* Even though consecutive calls to MORECORE need not return contiguous
4644
addresses, it must be OK for malloc'ed chunks to span multiple
4645
regions in those cases where they do happen to be contiguous.
4646
4647
* MORECORE need not handle negative arguments -- it may instead
4648
just return MORECORE_FAILURE when given negative arguments.
4649
Negative arguments are always multiples of pagesize. MORECORE
4650
must not misinterpret negative args as large positive unsigned
4651
args. You can suppress all such calls from even occurring by defining
4652
MORECORE_CANNOT_TRIM,
4653
4654
There is some variation across systems about the type of the
4655
argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
4656
actually be size_t, because sbrk supports negative args, so it is
4657
normally the signed type of the same width as size_t (sometimes
4658
declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much
4659
matter though. Internally, we use "long" as arguments, which should
4660
work across all reasonable possibilities.
4661
4662
Additionally, if MORECORE ever returns failure for a positive
4663
request, and HAVE_MMAP is true, then mmap is used as a noncontiguous
4664
system allocator. This is a useful backup strategy for systems with
4665
holes in address spaces -- in this case sbrk cannot contiguously
4666
expand the heap, but mmap may be able to map noncontiguous space.
4667
4668
If you'd like mmap to ALWAYS be used, you can define MORECORE to be
4669
a function that always returns MORECORE_FAILURE.
4670
4671
Malloc only has limited ability to detect failures of MORECORE
4672
to supply contiguous space when it says it can. In particular,
4673
multithreaded programs that do not use locks may result in
4674
rece conditions across calls to MORECORE that result in gaps
4675
that cannot be detected as such, and subsequent corruption.
4676
4677
If you are using this malloc with something other than sbrk (or its
4678
emulation) to supply memory regions, you probably want to set
4679
MORECORE_CONTIGUOUS as false. As an example, here is a custom
4680
allocator kindly contributed for pre-OSX macOS. It uses virtually
4681
but not necessarily physically contiguous non-paged memory (locked
4682
in, present and won't get swapped out). You can use it by
4683
uncommenting this section, adding some #includes, and setting up the
4684
appropriate defines above:
4685
4686
#define MORECORE osMoreCore
4687
#define MORECORE_CONTIGUOUS 0
4688
4689
There is also a shutdown routine that should somehow be called for
4690
cleanup upon program exit.
4691
4692
#define MAX_POOL_ENTRIES 100
4693
#define MINIMUM_MORECORE_SIZE (64 * 1024)
4694
static int next_os_pool;
4695
void *our_os_pools[MAX_POOL_ENTRIES];
4696
4697
void *osMoreCore(int size)
4698
{
4699
void *ptr = 0;
4700
static void *sbrk_top = 0;
4701
4702
if (size > 0)
4703
{
4704
if (size < MINIMUM_MORECORE_SIZE)
4705
size = MINIMUM_MORECORE_SIZE;
4706
if (CurrentExecutionLevel() == kTaskLevel)
4707
ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4708
if (ptr == 0)
4709
{
4710
return (void *) MORECORE_FAILURE;
4711
}
4712
// save ptrs so they can be freed during cleanup
4713
our_os_pools[next_os_pool] = ptr;
4714
next_os_pool++;
4715
ptr = (void *) ((((CHUNK_SIZE_T) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4716
sbrk_top = (char *) ptr + size;
4717
return ptr;
4718
}
4719
else if (size < 0)
4720
{
4721
// we don't currently support shrink behavior
4722
return (void *) MORECORE_FAILURE;
4723
}
4724
else
4725
{
4726
return sbrk_top;
4727
}
4728
}
4729
4730
// cleanup any allocated memory pools
4731
// called as last thing before shutting down driver
4732
4733
void osCleanupMem(void)
4734
{
4735
void **ptr;
4736
4737
for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4738
if (*ptr)
4739
{
4740
PoolDeallocate(*ptr);
4741
*ptr = 0;
4742
}
4743
}
4744
4745
*/
4746
4747
4748
/*
4749
--------------------------------------------------------------
4750
4751
Emulation of sbrk for win32.
4752
Donated by J. Walter <Walter@GeNeSys-e.de>.
4753
For additional information about this code, and malloc on Win32, see
4754
http://www.genesys-e.de/jwalter/
4755
*/
4756
4757
4758
#ifdef WIN32
4759
4760
#ifdef _DEBUG
4761
/* #define TRACE */
4762
#endif
4763
4764
/* Support for USE_MALLOC_LOCK */
4765
#ifdef USE_MALLOC_LOCK
4766
4767
/* Wait for spin lock */
4768
static int slwait (int *sl) {
4769
while (InterlockedCompareExchange ((void **) sl, (void *) 1, (void *) 0) != 0)
4770
Sleep (0);
4771
return 0;
4772
}
4773
4774
/* Release spin lock */
4775
static int slrelease (int *sl) {
4776
InterlockedExchange (sl, 0);
4777
return 0;
4778
}
4779
4780
#ifdef NEEDED
4781
/* Spin lock for emulation code */
4782
static int g_sl;
4783
#endif
4784
4785
#endif /* USE_MALLOC_LOCK */
4786
4787
/* getpagesize for windows */
4788
static long getpagesize (void) {
4789
static long g_pagesize = 0;
4790
if (! g_pagesize) {
4791
SYSTEM_INFO system_info;
4792
GetSystemInfo (&system_info);
4793
g_pagesize = system_info.dwPageSize;
4794
}
4795
return g_pagesize;
4796
}
4797
static long getregionsize (void) {
4798
static long g_regionsize = 0;
4799
if (! g_regionsize) {
4800
SYSTEM_INFO system_info;
4801
GetSystemInfo (&system_info);
4802
g_regionsize = system_info.dwAllocationGranularity;
4803
}
4804
return g_regionsize;
4805
}
4806
4807
/* A region list entry */
4808
typedef struct _region_list_entry {
4809
void *top_allocated;
4810
void *top_committed;
4811
void *top_reserved;
4812
long reserve_size;
4813
struct _region_list_entry *previous;
4814
} region_list_entry;
4815
4816
/* Allocate and link a region entry in the region list */
4817
static int region_list_append (region_list_entry **last, void *base_reserved, long reserve_size) {
4818
region_list_entry *next = HeapAlloc (GetProcessHeap (), 0, sizeof (region_list_entry));
4819
if (! next)
4820
return FALSE;
4821
next->top_allocated = (char *) base_reserved;
4822
next->top_committed = (char *) base_reserved;
4823
next->top_reserved = (char *) base_reserved + reserve_size;
4824
next->reserve_size = reserve_size;
4825
next->previous = *last;
4826
*last = next;
4827
return TRUE;
4828
}
4829
/* Free and unlink the last region entry from the region list */
4830
static int region_list_remove (region_list_entry **last) {
4831
region_list_entry *previous = (*last)->previous;
4832
if (! HeapFree (GetProcessHeap (), sizeof (region_list_entry), *last))
4833
return FALSE;
4834
*last = previous;
4835
return TRUE;
4836
}
4837
4838
#define CEIL(size,to) (((size)+(to)-1)&~((to)-1))
4839
#define FLOOR(size,to) ((size)&~((to)-1))
4840
4841
#define SBRK_SCALE 0
4842
/* #define SBRK_SCALE 1 */
4843
/* #define SBRK_SCALE 2 */
4844
/* #define SBRK_SCALE 4 */
4845
4846
/* sbrk for windows */
4847
static void *sbrk (long size) {
4848
static long g_pagesize, g_my_pagesize;
4849
static long g_regionsize, g_my_regionsize;
4850
static region_list_entry *g_last;
4851
void *result = (void *) MORECORE_FAILURE;
4852
#ifdef TRACE
4853
printf ("sbrk %d\n", size);
4854
#endif
4855
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
4856
/* Wait for spin lock */
4857
slwait (&g_sl);
4858
#endif
4859
/* First time initialization */
4860
if (! g_pagesize) {
4861
g_pagesize = getpagesize ();
4862
g_my_pagesize = g_pagesize << SBRK_SCALE;
4863
}
4864
if (! g_regionsize) {
4865
g_regionsize = getregionsize ();
4866
g_my_regionsize = g_regionsize << SBRK_SCALE;
4867
}
4868
if (! g_last) {
4869
if (! region_list_append (&g_last, 0, 0))
4870
goto sbrk_exit;
4871
}
4872
/* Assert invariants */
4873
assert (g_last);
4874
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_allocated &&
4875
g_last->top_allocated <= g_last->top_committed);
4876
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_committed &&
4877
g_last->top_committed <= g_last->top_reserved &&
4878
(unsigned) g_last->top_committed % g_pagesize == 0);
4879
assert ((unsigned) g_last->top_reserved % g_regionsize == 0);
4880
assert ((unsigned) g_last->reserve_size % g_regionsize == 0);
4881
/* Allocation requested? */
4882
if (size >= 0) {
4883
/* Allocation size is the requested size */
4884
long allocate_size = size;
4885
/* Compute the size to commit */
4886
long to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
4887
/* Do we reach the commit limit? */
4888
if (to_commit > 0) {
4889
/* Round size to commit */
4890
long commit_size = CEIL (to_commit, g_my_pagesize);
4891
/* Compute the size to reserve */
4892
long to_reserve = (char *) g_last->top_committed + commit_size - (char *) g_last->top_reserved;
4893
/* Do we reach the reserve limit? */
4894
if (to_reserve > 0) {
4895
/* Compute the remaining size to commit in the current region */
4896
long remaining_commit_size = (char *) g_last->top_reserved - (char *) g_last->top_committed;
4897
if (remaining_commit_size > 0) {
4898
/* Assert preconditions */
4899
assert ((unsigned) g_last->top_committed % g_pagesize == 0);
4900
assert (0 < remaining_commit_size && remaining_commit_size % g_pagesize == 0); {
4901
/* Commit this */
4902
void *base_committed = VirtualAlloc (g_last->top_committed, remaining_commit_size,
4903
MEM_COMMIT, PAGE_READWRITE);
4904
/* Check returned pointer for consistency */
4905
if (base_committed != g_last->top_committed)
4906
goto sbrk_exit;
4907
/* Assert postconditions */
4908
assert ((unsigned) base_committed % g_pagesize == 0);
4909
#ifdef TRACE
4910
printf ("Commit %p %d\n", base_committed, remaining_commit_size);
4911
#endif
4912
/* Adjust the regions commit top */
4913
g_last->top_committed = (char *) base_committed + remaining_commit_size;
4914
}
4915
} {
4916
/* Now we are going to search and reserve. */
4917
int contiguous = -1;
4918
int found = FALSE;
4919
MEMORY_BASIC_INFORMATION memory_info;
4920
void *base_reserved;
4921
long reserve_size;
4922
do {
4923
/* Assume contiguous memory */
4924
contiguous = TRUE;
4925
/* Round size to reserve */
4926
reserve_size = CEIL (to_reserve, g_my_regionsize);
4927
/* Start with the current region's top */
4928
memory_info.BaseAddress = g_last->top_reserved;
4929
/* Assert preconditions */
4930
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
4931
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
4932
while (VirtualQuery (memory_info.BaseAddress, &memory_info, sizeof (memory_info))) {
4933
/* Assert postconditions */
4934
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
4935
#ifdef TRACE
4936
printf ("Query %p %d %s\n", memory_info.BaseAddress, memory_info.RegionSize,
4937
memory_info.State == MEM_FREE ? "FREE":
4938
(memory_info.State == MEM_RESERVE ? "RESERVED":
4939
(memory_info.State == MEM_COMMIT ? "COMMITTED": "?")));
4940
#endif
4941
/* Region is free, well aligned and big enough: we are done */
4942
if (memory_info.State == MEM_FREE &&
4943
(unsigned) memory_info.BaseAddress % g_regionsize == 0 &&
4944
memory_info.RegionSize >= (unsigned) reserve_size) {
4945
found = TRUE;
4946
break;
4947
}
4948
/* From now on we can't get contiguous memory! */
4949
contiguous = FALSE;
4950
/* Recompute size to reserve */
4951
reserve_size = CEIL (allocate_size, g_my_regionsize);
4952
memory_info.BaseAddress = (char *) memory_info.BaseAddress + memory_info.RegionSize;
4953
/* Assert preconditions */
4954
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
4955
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
4956
}
4957
/* Search failed? */
4958
if (! found)
4959
goto sbrk_exit;
4960
/* Assert preconditions */
4961
assert ((unsigned) memory_info.BaseAddress % g_regionsize == 0);
4962
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
4963
/* Try to reserve this */
4964
base_reserved = VirtualAlloc (memory_info.BaseAddress, reserve_size,
4965
MEM_RESERVE, PAGE_NOACCESS);
4966
if (! base_reserved) {
4967
int rc = GetLastError ();
4968
if (rc != ERROR_INVALID_ADDRESS)
4969
goto sbrk_exit;
4970
}
4971
/* A null pointer signals (hopefully) a race condition with another thread. */
4972
/* In this case, we try again. */
4973
} while (! base_reserved);
4974
/* Check returned pointer for consistency */
4975
if (memory_info.BaseAddress && base_reserved != memory_info.BaseAddress)
4976
goto sbrk_exit;
4977
/* Assert postconditions */
4978
assert ((unsigned) base_reserved % g_regionsize == 0);
4979
#ifdef TRACE
4980
printf ("Reserve %p %d\n", base_reserved, reserve_size);
4981
#endif
4982
/* Did we get contiguous memory? */
4983
if (contiguous) {
4984
long start_size = (char *) g_last->top_committed - (char *) g_last->top_allocated;
4985
/* Adjust allocation size */
4986
allocate_size -= start_size;
4987
/* Adjust the regions allocation top */
4988
g_last->top_allocated = g_last->top_committed;
4989
/* Recompute the size to commit */
4990
to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
4991
/* Round size to commit */
4992
commit_size = CEIL (to_commit, g_my_pagesize);
4993
}
4994
/* Append the new region to the list */
4995
if (! region_list_append (&g_last, base_reserved, reserve_size))
4996
goto sbrk_exit;
4997
/* Didn't we get contiguous memory? */
4998
if (! contiguous) {
4999
/* Recompute the size to commit */
5000
to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
5001
/* Round size to commit */
5002
commit_size = CEIL (to_commit, g_my_pagesize);
5003
}
5004
}
5005
}
5006
/* Assert preconditions */
5007
assert ((unsigned) g_last->top_committed % g_pagesize == 0);
5008
assert (0 < commit_size && commit_size % g_pagesize == 0); {
5009
/* Commit this */
5010
void *base_committed = VirtualAlloc (g_last->top_committed, commit_size,
5011
MEM_COMMIT, PAGE_READWRITE);
5012
/* Check returned pointer for consistency */
5013
if (base_committed != g_last->top_committed)
5014
goto sbrk_exit;
5015
/* Assert postconditions */
5016
assert ((unsigned) base_committed % g_pagesize == 0);
5017
#ifdef TRACE
5018
printf ("Commit %p %d\n", base_committed, commit_size);
5019
#endif
5020
/* Adjust the regions commit top */
5021
g_last->top_committed = (char *) base_committed + commit_size;
5022
}
5023
}
5024
/* Adjust the regions allocation top */
5025
g_last->top_allocated = (char *) g_last->top_allocated + allocate_size;
5026
result = (char *) g_last->top_allocated - size;
5027
/* Deallocation requested? */
5028
} else if (size < 0) {
5029
long deallocate_size = - size;
5030
/* As long as we have a region to release */
5031
while ((char *) g_last->top_allocated - deallocate_size < (char *) g_last->top_reserved - g_last->reserve_size) {
5032
/* Get the size to release */
5033
long release_size = g_last->reserve_size;
5034
/* Get the base address */
5035
void *base_reserved = (char *) g_last->top_reserved - release_size;
5036
/* Assert preconditions */
5037
assert ((unsigned) base_reserved % g_regionsize == 0);
5038
assert (0 < release_size && release_size % g_regionsize == 0); {
5039
/* Release this */
5040
int rc = VirtualFree (base_reserved, 0,
5041
MEM_RELEASE);
5042
/* Check returned code for consistency */
5043
if (! rc)
5044
goto sbrk_exit;
5045
#ifdef TRACE
5046
printf ("Release %p %d\n", base_reserved, release_size);
5047
#endif
5048
}
5049
/* Adjust deallocation size */
5050
deallocate_size -= (char *) g_last->top_allocated - (char *) base_reserved;
5051
/* Remove the old region from the list */
5052
if (! region_list_remove (&g_last))
5053
goto sbrk_exit;
5054
} {
5055
/* Compute the size to decommit */
5056
long to_decommit = (char *) g_last->top_committed - ((char *) g_last->top_allocated - deallocate_size);
5057
if (to_decommit >= g_my_pagesize) {
5058
/* Compute the size to decommit */
5059
long decommit_size = FLOOR (to_decommit, g_my_pagesize);
5060
/* Compute the base address */
5061
void *base_committed = (char *) g_last->top_committed - decommit_size;
5062
/* Assert preconditions */
5063
assert ((unsigned) base_committed % g_pagesize == 0);
5064
assert (0 < decommit_size && decommit_size % g_pagesize == 0); {
5065
/* Decommit this */
5066
int rc = VirtualFree ((char *) base_committed, decommit_size,
5067
MEM_DECOMMIT);
5068
/* Check returned code for consistency */
5069
if (! rc)
5070
goto sbrk_exit;
5071
#ifdef TRACE
5072
printf ("Decommit %p %d\n", base_committed, decommit_size);
5073
#endif
5074
}
5075
/* Adjust deallocation size and regions commit and allocate top */
5076
deallocate_size -= (char *) g_last->top_allocated - (char *) base_committed;
5077
g_last->top_committed = base_committed;
5078
g_last->top_allocated = base_committed;
5079
}
5080
}
5081
/* Adjust regions allocate top */
5082
g_last->top_allocated = (char *) g_last->top_allocated - deallocate_size;
5083
/* Check for underflow */
5084
if ((char *) g_last->top_reserved - g_last->reserve_size > (char *) g_last->top_allocated ||
5085
g_last->top_allocated > g_last->top_committed) {
5086
/* Adjust regions allocate top */
5087
g_last->top_allocated = (char *) g_last->top_reserved - g_last->reserve_size;
5088
goto sbrk_exit;
5089
}
5090
result = g_last->top_allocated;
5091
}
5092
/* Assert invariants */
5093
assert (g_last);
5094
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_allocated &&
5095
g_last->top_allocated <= g_last->top_committed);
5096
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_committed &&
5097
g_last->top_committed <= g_last->top_reserved &&
5098
(unsigned) g_last->top_committed % g_pagesize == 0);
5099
assert ((unsigned) g_last->top_reserved % g_regionsize == 0);
5100
assert ((unsigned) g_last->reserve_size % g_regionsize == 0);
5101
5102
sbrk_exit:
5103
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5104
/* Release spin lock */
5105
slrelease (&g_sl);
5106
#endif
5107
return result;
5108
}
5109
5110
/* mmap for windows */
5111
static void *mmap (void *ptr, long size, long prot, long type, long handle, long arg) {
5112
static long g_pagesize;
5113
static long g_regionsize;
5114
#ifdef TRACE
5115
printf ("mmap %d\n", size);
5116
#endif
5117
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5118
/* Wait for spin lock */
5119
slwait (&g_sl);
5120
#endif
5121
/* First time initialization */
5122
if (! g_pagesize)
5123
g_pagesize = getpagesize ();
5124
if (! g_regionsize)
5125
g_regionsize = getregionsize ();
5126
/* Assert preconditions */
5127
assert ((unsigned) ptr % g_regionsize == 0);
5128
assert (size % g_pagesize == 0);
5129
/* Allocate this */
5130
ptr = VirtualAlloc (ptr, size,
5131
MEM_RESERVE | MEM_COMMIT | MEM_TOP_DOWN, PAGE_READWRITE);
5132
if (! ptr) {
5133
ptr = (void *) MORECORE_FAILURE;
5134
goto mmap_exit;
5135
}
5136
/* Assert postconditions */
5137
assert ((unsigned) ptr % g_regionsize == 0);
5138
#ifdef TRACE
5139
printf ("Commit %p %d\n", ptr, size);
5140
#endif
5141
mmap_exit:
5142
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5143
/* Release spin lock */
5144
slrelease (&g_sl);
5145
#endif
5146
return ptr;
5147
}
5148
5149
/* munmap for windows */
5150
static long munmap (void *ptr, long size) {
5151
static long g_pagesize;
5152
static long g_regionsize;
5153
int rc = MUNMAP_FAILURE;
5154
#ifdef TRACE
5155
printf ("munmap %p %d\n", ptr, size);
5156
#endif
5157
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5158
/* Wait for spin lock */
5159
slwait (&g_sl);
5160
#endif
5161
/* First time initialization */
5162
if (! g_pagesize)
5163
g_pagesize = getpagesize ();
5164
if (! g_regionsize)
5165
g_regionsize = getregionsize ();
5166
/* Assert preconditions */
5167
assert ((unsigned) ptr % g_regionsize == 0);
5168
assert (size % g_pagesize == 0);
5169
/* Free this */
5170
if (! VirtualFree (ptr, 0,
5171
MEM_RELEASE))
5172
goto munmap_exit;
5173
rc = 0;
5174
#ifdef TRACE
5175
printf ("Release %p %d\n", ptr, size);
5176
#endif
5177
munmap_exit:
5178
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5179
/* Release spin lock */
5180
slrelease (&g_sl);
5181
#endif
5182
return rc;
5183
}
5184
5185
static void vminfo (CHUNK_SIZE_T *free, CHUNK_SIZE_T *reserved, CHUNK_SIZE_T *committed) {
5186
MEMORY_BASIC_INFORMATION memory_info;
5187
memory_info.BaseAddress = 0;
5188
*free = *reserved = *committed = 0;
5189
while (VirtualQuery (memory_info.BaseAddress, &memory_info, sizeof (memory_info))) {
5190
switch (memory_info.State) {
5191
case MEM_FREE:
5192
*free += memory_info.RegionSize;
5193
break;
5194
case MEM_RESERVE:
5195
*reserved += memory_info.RegionSize;
5196
break;
5197
case MEM_COMMIT:
5198
*committed += memory_info.RegionSize;
5199
break;
5200
}
5201
memory_info.BaseAddress = (char *) memory_info.BaseAddress + memory_info.RegionSize;
5202
}
5203
}
5204
5205
static int cpuinfo (int whole, CHUNK_SIZE_T *kernel, CHUNK_SIZE_T *user) {
5206
if (whole) {
5207
__int64 creation64, exit64, kernel64, user64;
5208
int rc = GetProcessTimes (GetCurrentProcess (),
5209
(FILETIME *) &creation64,
5210
(FILETIME *) &exit64,
5211
(FILETIME *) &kernel64,
5212
(FILETIME *) &user64);
5213
if (! rc) {
5214
*kernel = 0;
5215
*user = 0;
5216
return FALSE;
5217
}
5218
*kernel = (CHUNK_SIZE_T) (kernel64 / 10000);
5219
*user = (CHUNK_SIZE_T) (user64 / 10000);
5220
return TRUE;
5221
} else {
5222
__int64 creation64, exit64, kernel64, user64;
5223
int rc = GetThreadTimes (GetCurrentThread (),
5224
(FILETIME *) &creation64,
5225
(FILETIME *) &exit64,
5226
(FILETIME *) &kernel64,
5227
(FILETIME *) &user64);
5228
if (! rc) {
5229
*kernel = 0;
5230
*user = 0;
5231
return FALSE;
5232
}
5233
*kernel = (CHUNK_SIZE_T) (kernel64 / 10000);
5234
*user = (CHUNK_SIZE_T) (user64 / 10000);
5235
return TRUE;
5236
}
5237
}
5238
5239
#endif /* WIN32 */
5240
5241
/* ------------------------------------------------------------
5242
History:
5243
V2.8.0 (not yet released)
5244
* Use trees for non-small bins
5245
Also requiring different size->bin algorithm
5246
5247
V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
5248
* Allow tuning of FIRST_SORTED_BIN_SIZE
5249
* Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
5250
* Better detection and support for non-contiguousness of MORECORE.
5251
Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
5252
* Bypass most of malloc if no frees. Thanks To Emery Berger.
5253
* Fix freeing of old top non-contiguous chunk im sysmalloc.
5254
* Raised default trim and map thresholds to 256K.
5255
* Fix mmap-related #defines. Thanks to Lubos Lunak.
5256
* Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
5257
* Branch-free bin calculation
5258
* Default trim and mmap thresholds now 256K.
5259
5260
V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
5261
* Introduce independent_comalloc and independent_calloc.
5262
Thanks to Michael Pachos for motivation and help.
5263
* Make optional .h file available
5264
* Allow > 2GB requests on 32bit systems.
5265
* new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
5266
Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
5267
and Anonymous.
5268
* Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
5269
helping test this.)
5270
* memalign: check alignment arg
5271
* realloc: don't try to shift chunks backwards, since this
5272
leads to more fragmentation in some programs and doesn't
5273
seem to help in any others.
5274
* Collect all cases in malloc requiring system memory into sysmalloc
5275
* Use mmap as backup to sbrk
5276
* Place all internal state in malloc_state
5277
* Introduce fastbins (although similar to 2.5.1)
5278
* Many minor tunings and cosmetic improvements
5279
* Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
5280
* Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
5281
Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
5282
* Include errno.h to support default failure action.
5283
5284
V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
5285
* return null for negative arguments
5286
* Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5287
* Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5288
(e.g. WIN32 platforms)
5289
* Cleanup header file inclusion for WIN32 platforms
5290
* Cleanup code to avoid Microsoft Visual C++ compiler complaints
5291
* Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5292
memory allocation routines
5293
* Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5294
* Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5295
usage of 'assert' in non-WIN32 code
5296
* Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5297
avoid infinite loop
5298
* Always call 'fREe()' rather than 'free()'
5299
5300
V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
5301
* Fixed ordering problem with boundary-stamping
5302
5303
V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
5304
* Added pvalloc, as recommended by H.J. Liu
5305
* Added 64bit pointer support mainly from Wolfram Gloger
5306
* Added anonymously donated WIN32 sbrk emulation
5307
* Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5308
* malloc_extend_top: fix mask error that caused wastage after
5309
foreign sbrks
5310
* Add linux mremap support code from HJ Liu
5311
5312
V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
5313
* Integrated most documentation with the code.
5314
* Add support for mmap, with help from
5315
Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5316
* Use last_remainder in more cases.
5317
* Pack bins using idea from colin@nyx10.cs.du.edu
5318
* Use ordered bins instead of best-fit threshhold
5319
* Eliminate block-local decls to simplify tracing and debugging.
5320
* Support another case of realloc via move into top
5321
* Fix error occuring when initial sbrk_base not word-aligned.
5322
* Rely on page size for units instead of SBRK_UNIT to
5323
avoid surprises about sbrk alignment conventions.
5324
* Add mallinfo, mallopt. Thanks to Raymond Nijssen
5325
(raymond@es.ele.tue.nl) for the suggestion.
5326
* Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5327
* More precautions for cases where other routines call sbrk,
5328
courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5329
* Added macros etc., allowing use in linux libc from
5330
H.J. Lu (hjl@gnu.ai.mit.edu)
5331
* Inverted this history list
5332
5333
V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
5334
* Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5335
* Removed all preallocation code since under current scheme
5336
the work required to undo bad preallocations exceeds
5337
the work saved in good cases for most test programs.
5338
* No longer use return list or unconsolidated bins since
5339
no scheme using them consistently outperforms those that don't
5340
given above changes.
5341
* Use best fit for very large chunks to prevent some worst-cases.
5342
* Added some support for debugging
5343
5344
V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
5345
* Removed footers when chunks are in use. Thanks to
5346
Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5347
5348
V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
5349
* Added malloc_trim, with help from Wolfram Gloger
5350
(wmglo@Dent.MED.Uni-Muenchen.DE).
5351
5352
V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
5353
5354
V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
5355
* realloc: try to expand in both directions
5356
* malloc: swap order of clean-bin strategy;
5357
* realloc: only conditionally expand backwards
5358
* Try not to scavenge used bins
5359
* Use bin counts as a guide to preallocation
5360
* Occasionally bin return list chunks in first scan
5361
* Add a few optimizations from colin@nyx10.cs.du.edu
5362
5363
V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
5364
* faster bin computation & slightly different binning
5365
* merged all consolidations to one part of malloc proper
5366
(eliminating old malloc_find_space & malloc_clean_bin)
5367
* Scan 2 returns chunks (not just 1)
5368
* Propagate failure in realloc if malloc returns 0
5369
* Add stuff to allow compilation on non-ANSI compilers
5370
from kpv@research.att.com
5371
5372
V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
5373
* removed potential for odd address access in prev_chunk
5374
* removed dependency on getpagesize.h
5375
* misc cosmetics and a bit more internal documentation
5376
* anticosmetics: mangled names in macros to evade debugger strangeness
5377
* tested on sparc, hp-700, dec-mips, rs6000
5378
with gcc & native cc (hp, dec only) allowing
5379
Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5380
5381
Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
5382
* Based loosely on libg++-1.2X malloc. (It retains some of the overall
5383
structure of old version, but most details differ.)
5384
5385
*/
5386
5387
Loggerhead is a web-based interface for Breezy
Version: 2.0.1