« back to all changes in this revision
Viewing changes to test/manual/mymalloc.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Theodore Y. Ts'o
- Date: 2004-01-17 00:04:53 UTC
- Revision ID: james.westby@ubuntu.com-20040117000453-d5sj6uoon2v1g4gf
Tags: upstream-0.0.4
Import upstream version 0.0.4
- files added:
- doc
- doc/ext
- doc/int
- make_includes
- src
- src/Judy1
- src/JudyCommon
- src/JudyL
- src/JudySL
- src/apps
- src/apps/demo
- test
- test/manual
- tool
added
removed
test/manual/mymalloc.c
1
/*
2
[insert usage description etc here]
3
4
Last update: Sun Aug 11 17:57:59 2002 Doug Lea (dl at gee)
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_t* malloc_consolidate(mstate, CHUNK_SIZE_T, CHUNK_SIZE_T);
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
2940
/*
2941
------------------------------ malloc ------------------------------
2942
*/
2943
2944
Void_t* mALLOc(size_t bytes) {
2945
mstate av = get_malloc_state();
2946
CHUNK_SIZE_T nb;
2947
2948
checked_request2size(bytes, nb);
2949
2950
if (nb <= (CHUNK_SIZE_T)(av->max_fast)) {
2951
mfastbinptr* fb = &(av->fastbins[(fastbin_index(nb))]);
2952
mchunkptr fp = *fb;
2953
if (fp != 0) {
2954
*fb = fp->fd;
2955
check_remalloced_chunk(fp, nb);
2956
return chunk2mem(fp);
2957
}
2958
}
2959
2960
if (in_smallbin_range(nb)) {
2961
bin_index_t sidx = smallbin_index(nb);
2962
bitmap_t sbit = idx2bit(sidx);
2963
2964
if (sbit <= av->smallbits) {
2965
mchunkptr p;
2966
if ((sbit & av->smallbits) != 0) {
2967
p = take_from_smallbin(av, bin_at(av,sidx), sbit);
2968
set_inuse_bit_at_offset(p, nb);
2969
}
2970
else {
2971
bitmap_t nbit = least_bit(left_bits(sbit) & av->smallbits);
2972
bin_index_t nidx = bit2idx(nbit);
2973
CHUNK_SIZE_T psize = size_for_smallindex(nidx);
2974
CHUNK_SIZE_T qsize = psize - nb;
2975
p = take_from_smallbin(av, bin_at(av, nidx), nbit);
2976
if (qsize < MINSIZE) {
2977
set_inuse_bit_at_offset(p, psize);
2978
}
2979
else {
2980
mchunkptr q = chunk_at_offset(p, nb);
2981
set_head(p, nb | PREV_INUSE);
2982
set_head(q, qsize | PREV_INUSE);
2983
set_foot(q, qsize);
2984
insert_small_chunk(av, q, qsize);
2985
}
2986
}
2987
check_malloced_chunk(p, nb);
2988
return chunk2mem(p);
2989
}
2990
2991
if (av->treebits != 0) {
2992
bitmap_t vbit = least_bit(av->treebits);
2993
bin_index_t vidx = bit2idx(vbit);
2994
tbinptr* vbin = tbin_at(av, vidx);
2995
tchunkptr bestchunk = *vbin;
2996
tchunkptr c = leftmost_child(bestchunk);
2997
CHUNK_SIZE_T bestsize = chunksize(bestchunk);
2998
tchunkptr leaf;
2999
CHUNK_SIZE_T rsize;
3000
3001
/* Fast path if remainder will replace bestchunk */
3002
if (c == 0) {
3003
rsize = bestsize - nb;
3004
leaf = bestchunk;
3005
3006
if (rsize >= minsize_for_treeindex(vidx) &&
3007
bestchunk->bk == bestchunk) {
3008
tchunkptr r = (tchunkptr)(chunk_at_offset(bestchunk, nb));
3009
3010
set_head(bestchunk, nb | PREV_INUSE);
3011
set_head(r, rsize | PREV_INUSE);
3012
set_foot(r, rsize);
3013
*vbin = r;
3014
r->fd = r;
3015
r->bk = r;
3016
r->child[0] = 0;
3017
r->child[1] = 0;
3018
r->parent = (tchunkptr)vbin;
3019
r->index = vidx;
3020
check_malloced_chunk((mchunkptr)bestchunk, nb);
3021
return chunk2mem(bestchunk);
3022
}
3023
}
3024
else {
3025
do {
3026
CHUNK_SIZE_T csize = chunksize(c);
3027
if (csize < bestsize) {
3028
bestchunk = c;
3029
bestsize = csize;
3030
}
3031
leaf = c;
3032
c = leftmost_child(c);
3033
} while (c != 0);
3034
}
3035
3036
if (bestchunk->bk != bestchunk)
3037
unlink_chained_node(bestchunk);
3038
else {
3039
unlink_leaf_node(av, leaf);
3040
if (leaf != bestchunk)
3041
transfer_tree_links(bestchunk, leaf);
3042
}
3043
3044
rsize = bestsize - nb;
3045
if (rsize >= MINSIZE) {
3046
mchunkptr rem = chunk_at_offset(bestchunk, nb);
3047
set_head(bestchunk, nb | PREV_INUSE);
3048
set_head(rem, rsize | PREV_INUSE);
3049
set_foot(rem, rsize);
3050
insert_chunk(av, rem, rsize);
3051
}
3052
else {
3053
set_inuse_bit_at_offset(bestchunk, bestsize);
3054
}
3055
check_malloced_chunk((mchunkptr)(bestchunk), nb);
3056
return chunk2mem(bestchunk);
3057
}
3058
}
3059
3060
else {
3061
bin_index_t tidx = treebin_index(nb);
3062
bitmap_t tbit = idx2bit(tidx);
3063
3064
if (tbit <= av->treebits) {
3065
tchunkptr bestchunk = 0;
3066
CHUNK_SIZE_T bestsize = MAX_CHUNK_SIZE;
3067
tchunkptr leaf;
3068
3069
if ((tbit & av->treebits) != 0) {
3070
tchunkptr t = *tbin_at(av, tidx);
3071
bin_index_t shift = bitshift_for_index(tidx);
3072
for (;;) {
3073
int dir;
3074
CHUNK_SIZE_T tsize = chunksize(t);
3075
leaf = t;
3076
if (tsize >= nb && tsize < bestsize) {
3077
bestchunk = t;
3078
bestsize = tsize;
3079
if (tsize == nb && t->bk != t)
3080
break;
3081
}
3082
3083
dir = (shift == 0)? 0 : (nb >> shift--) & 1;
3084
t = leaf->child[dir];
3085
if (t == 0) {
3086
shift = 0; /* if forced right, go leftmost from now on */
3087
t = leaf->child[1-dir];
3088
if (t == 0)
3089
break;
3090
}
3091
}
3092
}
3093
3094
3095
if (bestchunk == 0) {
3096
bitmap_t vbit;
3097
3098
if (have_fastchunks(av)) {
3099
Void_t* cp = malloc_consolidate(av, nb, nb+nb);
3100
if (cp != 0)
3101
return cp;
3102
}
3103
3104
vbit = least_bit(left_bits(tbit) & av->treebits);
3105
if (vbit != 0) {
3106
bin_index_t vidx = bit2idx(vbit);
3107
tbinptr* vbin = tbin_at(av, vidx);
3108
tchunkptr c = *vbin;
3109
do {
3110
CHUNK_SIZE_T csize = chunksize(c);
3111
leaf = c;
3112
if (csize < bestsize) {
3113
bestchunk = c;
3114
bestsize = csize;
3115
}
3116
c = leftmost_child(c);
3117
} while (c != 0);
3118
}
3119
3120
}
3121
3122
if (bestchunk != 0) {
3123
CHUNK_SIZE_T rsize;
3124
3125
if (bestchunk->bk != bestchunk)
3126
unlink_chained_node(bestchunk);
3127
else {
3128
unlink_leaf_node(av, leaf);
3129
if (leaf != bestchunk)
3130
transfer_tree_links(bestchunk, leaf);
3131
}
3132
3133
rsize = bestsize - nb;
3134
if (rsize >= MINSIZE) {
3135
mchunkptr rem = chunk_at_offset(bestchunk, nb);
3136
set_head(bestchunk, nb | PREV_INUSE);
3137
set_head(rem, rsize | PREV_INUSE);
3138
set_foot(rem, rsize);
3139
insert_chunk(av, rem, rsize);
3140
}
3141
else {
3142
set_inuse_bit_at_offset(bestchunk, bestsize);
3143
}
3144
check_malloced_chunk((mchunkptr)(bestchunk), nb);
3145
return chunk2mem(bestchunk);
3146
}
3147
}
3148
}
3149
3150
/*
3151
If large enough, split off the chunk bordering the end of memory
3152
(held in av->top). This is called in accord with the best-fit
3153
search rule. In effect, av->top is treated as larger (and thus
3154
less well fitting) than any other available chunk since it can
3155
be extended to be as large as necessary (up to system
3156
limitations).
3157
3158
We require that av->top always exists (i.e., has size >=
3159
MINSIZE) after initialization, so if it would otherwise be
3160
exhuasted by current request, it is replenished. (The main
3161
reason for ensuring it exists is that we may need MINSIZE space
3162
to put in fenceposts in sysmalloc.)
3163
*/
3164
3165
if (av->top != 0) {
3166
mchunkptr topchunk = av->top;
3167
CHUNK_SIZE_T topsize = chunksize(topchunk);
3168
3169
if (topsize < nb + MINSIZE) {
3170
if (have_fastchunks(av)) {
3171
Void_t* cp = malloc_consolidate(av, nb, MAX_CHUNK_SIZE);
3172
if (cp != 0)
3173
return cp;
3174
else {
3175
topchunk = av->top;
3176
topsize = chunksize(topchunk);
3177
}
3178
}
3179
}
3180
3181
if (topsize >= nb + MINSIZE) {
3182
CHUNK_SIZE_T remainder_size = topsize - nb;
3183
mchunkptr remainder = chunk_at_offset(topchunk, nb);
3184
3185
av->top = remainder;
3186
set_head(topchunk, nb | PREV_INUSE);
3187
set_head(remainder, remainder_size | PREV_INUSE);
3188
3189
check_malloced_chunk(topchunk, nb);
3190
return chunk2mem(topchunk);
3191
}
3192
3193
}
3194
3195
return sysmalloc(av, nb);
3196
}
3197
3198
/*
3199
------------------------------ free ------------------------------
3200
*/
3201
3202
3203
void fREe(Void_t* mem) {
3204
mstate av = get_malloc_state();
3205
3206
mchunkptr p = mem2chunk(mem);
3207
3208
if (mem != 0) {
3209
INTERNAL_SIZE_T rawsize = p->size;
3210
CHUNK_SIZE_T size = chunksize(p);
3211
check_inuse_chunk(p);
3212
3213
/*
3214
If eligible, place chunk on a fastbin so it can be found
3215
and used quickly in malloc.
3216
*/
3217
3218
if ((CHUNK_SIZE_T)(size) <= (CHUNK_SIZE_T)(av->max_fast)
3219
3220
#if TRIM_FASTBINS
3221
/*
3222
If TRIM_FASTBINS set, don't place chunks
3223
bordering top into fastbins
3224
*/
3225
&& (chunk_at_offset(p, size) != av->top)
3226
#endif
3227
) {
3228
3229
mfastbinptr* fb;
3230
set_fastchunks(av);
3231
fb = &(av->fastbins[fastbin_index(size)]);
3232
p->fd = *fb;
3233
*fb = p;
3234
}
3235
3236
else if ((rawsize & IS_MMAPPED) == 0) {
3237
mchunkptr nextchunk = chunk_at_offset(p, size);
3238
CHUNK_SIZE_T nextsize;
3239
3240
if ((rawsize & PREV_INUSE) == 0) {
3241
CHUNK_SIZE_T prevsize = p->prev_size;
3242
size += prevsize;
3243
p = chunk_at_offset(p, -((long) prevsize));
3244
unlink_chunk(av, p, prevsize);
3245
}
3246
3247
nextsize = chunksize(nextchunk);
3248
if (nextchunk == av->top) {
3249
size += nextsize;
3250
set_head(p, size | PREV_INUSE);
3251
av->top = p;
3252
if (size >= av->trim_threshold) {
3253
systrim(av, av->top_pad);
3254
}
3255
}
3256
else {
3257
if (!inuse_bit_at_offset(nextchunk, nextsize)) {
3258
size += nextsize;
3259
unlink_chunk(av, nextchunk, nextsize);
3260
}
3261
else
3262
set_head(nextchunk, nextsize);
3263
3264
set_head(p, size | PREV_INUSE);
3265
set_foot(p, size);
3266
insert_chunk(av, p, size);
3267
}
3268
}
3269
else {
3270
#if HAVE_MMAP
3271
int ret;
3272
INTERNAL_SIZE_T offset = p->prev_size;
3273
av->n_mmaps--;
3274
av->mmapped_mem -= (size + offset);
3275
ret = munmap((char*)p - offset, size + offset);
3276
/* munmap returns non-zero on failure */
3277
assert(ret == 0);
3278
#endif
3279
}
3280
}
3281
}
3282
3283
/*
3284
------------------------- malloc_consolidate -------------------------
3285
3286
malloc_consolidate tears down chunks held in fastbins, returning
3287
one if withing bounds.
3288
*/
3289
3290
static Void_t* malloc_consolidate(mstate av, CHUNK_SIZE_T nb, CHUNK_SIZE_T maxnb) {
3291
int i;
3292
for (i = 0; i < NFASTBINS; ++i) {
3293
mfastbinptr* fb = &(av->fastbins[i]);
3294
mchunkptr p = *fb;
3295
3296
if (p != 0) {
3297
*fb = 0;
3298
3299
do {
3300
mchunkptr nextp = p->fd;
3301
INTERNAL_SIZE_T rawsize = p->size;
3302
CHUNK_SIZE_T size = chunksize(p);
3303
mchunkptr nextchunk = chunk_at_offset(p, size);
3304
CHUNK_SIZE_T nextsize;
3305
3306
if ((rawsize & PREV_INUSE) == 0) {
3307
CHUNK_SIZE_T prevsize = p->prev_size;
3308
size += prevsize;
3309
p = chunk_at_offset(p, -((long) prevsize));
3310
unlink_chunk(av, p, prevsize);
3311
}
3312
3313
nextsize = chunksize(nextchunk);
3314
if (nextchunk == av->top) {
3315
size += nextsize;
3316
set_head(p, size | PREV_INUSE);
3317
av->top = p;
3318
}
3319
else {
3320
if (!inuse_bit_at_offset(nextchunk, nextsize)) {
3321
size += nextsize;
3322
unlink_chunk(av, nextchunk, nextsize);
3323
}
3324
else
3325
set_head(nextchunk, nextsize);
3326
3327
set_head(p, size | PREV_INUSE);
3328
set_foot(p, size);
3329
3330
if (size < nb || size >= maxnb) {
3331
insert_chunk(av, p, size);
3332
}
3333
else {
3334
CHUNK_SIZE_T remainder_size = size - nb;
3335
3336
*fb = nextp;
3337
/* Exhaust */
3338
if (remainder_size < MINSIZE) {
3339
set_inuse_bit_at_offset(p, size);
3340
check_malloced_chunk(p, nb);
3341
return chunk2mem(p);
3342
}
3343
/* Split */
3344
else {
3345
mchunkptr remainder = chunk_at_offset(p, nb);
3346
set_head(p, nb | PREV_INUSE);
3347
set_head(remainder, remainder_size | PREV_INUSE);
3348
set_foot(remainder, remainder_size);
3349
insert_chunk(av, remainder, remainder_size);
3350
check_malloced_chunk(p, nb);
3351
return chunk2mem(p);
3352
}
3353
}
3354
}
3355
p = nextp;
3356
} while (p != 0);
3357
}
3358
}
3359
3360
clear_fastchunks(av);
3361
return 0;
3362
}
3363
3364
3365
/*
3366
------------------------------ realloc ------------------------------
3367
*/
3368
3369
3370
Void_t* rEALLOc(Void_t* oldmem, size_t bytes) {
3371
mstate av = get_malloc_state();
3372
3373
INTERNAL_SIZE_T nb; /* padded request size */
3374
3375
mchunkptr oldp; /* chunk corresponding to oldmem */
3376
CHUNK_SIZE_T oldsize; /* its size */
3377
3378
mchunkptr newp; /* chunk to return */
3379
CHUNK_SIZE_T newsize; /* its size */
3380
Void_t* newmem; /* corresponding user mem */
3381
3382
mchunkptr next; /* next contiguous chunk after oldp */
3383
3384
mchunkptr remainder; /* extra space at end of newp */
3385
CHUNK_SIZE_T remainder_size; /* its size */
3386
3387
CHUNK_SIZE_T copysize; /* bytes to copy */
3388
unsigned int ncopies; /* INTERNAL_SIZE_T words to copy */
3389
INTERNAL_SIZE_T* s; /* copy source */
3390
INTERNAL_SIZE_T* d; /* copy destination */
3391
3392
3393
#ifdef REALLOC_ZERO_BYTES_FREES
3394
if (bytes == 0) {
3395
fREe(oldmem);
3396
return 0;
3397
}
3398
#endif
3399
3400
/* realloc of null is supposed to be same as malloc */
3401
if (oldmem == 0) return mALLOc(bytes);
3402
3403
checked_request2size(bytes, nb);
3404
3405
oldp = mem2chunk(oldmem);
3406
oldsize = chunksize(oldp);
3407
3408
check_inuse_chunk(oldp);
3409
3410
if (!chunk_is_mmapped(oldp)) {
3411
3412
if ((CHUNK_SIZE_T)(oldsize) >= (CHUNK_SIZE_T)(nb)) {
3413
/* already big enough; split below */
3414
newp = oldp;
3415
newsize = oldsize;
3416
}
3417
3418
else {
3419
next = chunk_at_offset(oldp, oldsize);
3420
3421
/* Try to expand forward into top */
3422
if (next == av->top &&
3423
(CHUNK_SIZE_T)(newsize = oldsize + chunksize(next)) >=
3424
(CHUNK_SIZE_T)(nb + MINSIZE)) {
3425
set_head_size(oldp, nb);
3426
av->top = chunk_at_offset(oldp, nb);
3427
set_head(av->top, (newsize - nb) | PREV_INUSE);
3428
return chunk2mem(oldp);
3429
}
3430
3431
/* Try to expand forward into next chunk; split off remainder below */
3432
else if (next != av->top &&
3433
!inuse(next) &&
3434
(CHUNK_SIZE_T)(newsize = oldsize + chunksize(next)) >=
3435
(CHUNK_SIZE_T)(nb)) {
3436
newp = oldp;
3437
unlink_chunk(av, next, chunksize(next));
3438
}
3439
3440
/* allocate, copy, free */
3441
else {
3442
newmem = mALLOc(nb - MALLOC_ALIGN_MASK);
3443
if (newmem == 0)
3444
return 0; /* propagate failure */
3445
3446
newp = mem2chunk(newmem);
3447
newsize = chunksize(newp);
3448
3449
/*
3450
Avoid copy if newp is next chunk after oldp.
3451
*/
3452
if (newp == next) {
3453
newsize += oldsize;
3454
newp = oldp;
3455
}
3456
else {
3457
/*
3458
Unroll copy of <= 36 bytes (72 if 8byte sizes)
3459
We know that contents have an odd number of
3460
INTERNAL_SIZE_T-sized words; minimally 3.
3461
*/
3462
3463
copysize = oldsize - SIZE_SZ;
3464
s = (INTERNAL_SIZE_T*)(oldmem);
3465
d = (INTERNAL_SIZE_T*)(newmem);
3466
ncopies = copysize / sizeof(INTERNAL_SIZE_T);
3467
assert(ncopies >= 3);
3468
3469
if (ncopies > 9)
3470
MALLOC_COPY(d, s, copysize);
3471
3472
else {
3473
*(d+0) = *(s+0);
3474
*(d+1) = *(s+1);
3475
*(d+2) = *(s+2);
3476
if (ncopies > 4) {
3477
*(d+3) = *(s+3);
3478
*(d+4) = *(s+4);
3479
if (ncopies > 6) {
3480
*(d+5) = *(s+5);
3481
*(d+6) = *(s+6);
3482
if (ncopies > 8) {
3483
*(d+7) = *(s+7);
3484
*(d+8) = *(s+8);
3485
}
3486
}
3487
}
3488
}
3489
3490
fREe(oldmem);
3491
check_inuse_chunk(newp);
3492
return chunk2mem(newp);
3493
}
3494
}
3495
}
3496
3497
/* If possible, free extra space in old or extended chunk */
3498
3499
assert((CHUNK_SIZE_T)(newsize) >= (CHUNK_SIZE_T)(nb));
3500
3501
remainder_size = newsize - nb;
3502
3503
if (remainder_size < MINSIZE) { /* not enough extra to split off */
3504
set_head_size(newp, newsize);
3505
set_inuse_bit_at_offset(newp, newsize);
3506
}
3507
else { /* split remainder */
3508
remainder = chunk_at_offset(newp, nb);
3509
set_head_size(newp, nb);
3510
set_head(remainder, remainder_size | PREV_INUSE);
3511
/* Mark remainder as inuse so free() won't complain */
3512
set_inuse_bit_at_offset(remainder, remainder_size);
3513
fREe(chunk2mem(remainder));
3514
}
3515
3516
check_inuse_chunk(newp);
3517
return chunk2mem(newp);
3518
}
3519
3520
/*
3521
Handle mmap cases
3522
*/
3523
3524
else {
3525
#if HAVE_MMAP
3526
3527
#if HAVE_MREMAP
3528
INTERNAL_SIZE_T offset = oldp->prev_size;
3529
size_t pagemask = av->pagesize - 1;
3530
char *cp;
3531
CHUNK_SIZE_T sum;
3532
3533
/* Note the extra SIZE_SZ overhead */
3534
newsize = (nb + offset + SIZE_SZ + pagemask) & ~pagemask;
3535
3536
/* don't need to remap if still within same page */
3537
if (oldsize == newsize - offset)
3538
return oldmem;
3539
3540
cp = (char*)mremap((char*)oldp - offset, oldsize + offset, newsize, 1);
3541
3542
if (cp != (char*)MORECORE_FAILURE) {
3543
3544
newp = (mchunkptr)(cp + offset);
3545
set_head(newp, (newsize - offset)|IS_MMAPPED);
3546
3547
assert(aligned_OK(chunk2mem(newp)));
3548
assert((newp->prev_size == offset));
3549
3550
/* update statistics */
3551
sum = av->mmapped_mem += newsize - oldsize;
3552
if (sum > (CHUNK_SIZE_T)(av->max_mmapped_mem))
3553
av->max_mmapped_mem = sum;
3554
sum += av->sbrked_mem;
3555
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
3556
av->max_total_mem = sum;
3557
3558
return chunk2mem(newp);
3559
}
3560
#endif
3561
3562
/* Note the extra SIZE_SZ overhead. */
3563
if ((CHUNK_SIZE_T)(oldsize) >= (CHUNK_SIZE_T)(nb + SIZE_SZ))
3564
newmem = oldmem; /* do nothing */
3565
else {
3566
/* Must alloc, copy, free. */
3567
newmem = mALLOc(nb - MALLOC_ALIGN_MASK);
3568
if (newmem != 0) {
3569
MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
3570
fREe(oldmem);
3571
}
3572
}
3573
return newmem;
3574
3575
#else
3576
/* If !HAVE_MMAP, but chunk_is_mmapped, user must have overwritten mem */
3577
check_malloc_state(av);
3578
MALLOC_FAILURE_ACTION;
3579
return 0;
3580
#endif
3581
}
3582
}
3583
3584
/*
3585
------------------------------ memalign ------------------------------
3586
*/
3587
3588
Void_t* mEMALIGn(size_t alignment, size_t bytes) {
3589
INTERNAL_SIZE_T nb; /* padded request size */
3590
char* m; /* memory returned by malloc call */
3591
mchunkptr p; /* corresponding chunk */
3592
char* brk; /* alignment point within p */
3593
mchunkptr newp; /* chunk to return */
3594
INTERNAL_SIZE_T newsize; /* its size */
3595
INTERNAL_SIZE_T leadsize; /* leading space before alignment point */
3596
mchunkptr remainder; /* spare room at end to split off */
3597
CHUNK_SIZE_T remainder_size; /* its size */
3598
INTERNAL_SIZE_T size;
3599
3600
/* If need less alignment than we give anyway, just relay to malloc */
3601
3602
if (alignment <= MALLOC_ALIGNMENT) return mALLOc(bytes);
3603
3604
/* Otherwise, ensure that it is at least a minimum chunk size */
3605
3606
if (alignment < MINSIZE) alignment = MINSIZE;
3607
3608
/* Make sure alignment is power of 2 (in case MINSIZE is not). */
3609
if ((alignment & (alignment - 1)) != 0) {
3610
size_t a = MALLOC_ALIGNMENT * 2;
3611
while ((CHUNK_SIZE_T)a < (CHUNK_SIZE_T)alignment) a <<= 1;
3612
alignment = a;
3613
}
3614
3615
checked_request2size(bytes, nb);
3616
3617
/*
3618
Strategy: find a spot within that chunk that meets the alignment
3619
request, and then possibly free the leading and trailing space.
3620
*/
3621
3622
3623
/* Call malloc with worst case padding to hit alignment. */
3624
3625
m = (char*)(mALLOc(nb + alignment + MINSIZE));
3626
3627
if (m == 0) return 0; /* propagate failure */
3628
3629
p = mem2chunk(m);
3630
3631
if ((((PTR_UINT)(m)) % alignment) != 0) { /* misaligned */
3632
3633
/*
3634
Find an aligned spot inside chunk. Since we need to give back
3635
leading space in a chunk of at least MINSIZE, if the first
3636
calculation places us at a spot with less than MINSIZE leader,
3637
we can move to the next aligned spot -- we've allocated enough
3638
total room so that this is always possible.
3639
*/
3640
3641
brk = (char*)mem2chunk((PTR_UINT)(((PTR_UINT)(m + alignment - 1)) &
3642
-((signed long) alignment)));
3643
if ((CHUNK_SIZE_T)(brk - (char*)(p)) < MINSIZE)
3644
brk += alignment;
3645
3646
newp = (mchunkptr)brk;
3647
leadsize = brk - (char*)(p);
3648
newsize = chunksize(p) - leadsize;
3649
3650
/* For mmapped chunks, just adjust offset */
3651
if (chunk_is_mmapped(p)) {
3652
newp->prev_size = p->prev_size + leadsize;
3653
set_head(newp, newsize|IS_MMAPPED);
3654
return chunk2mem(newp);
3655
}
3656
3657
/* Otherwise, give back leader, use the rest */
3658
set_head(newp, newsize | PREV_INUSE);
3659
set_inuse_bit_at_offset(newp, newsize);
3660
set_head_size(p, leadsize);
3661
fREe(chunk2mem(p));
3662
p = newp;
3663
3664
assert (newsize >= nb &&
3665
(((PTR_UINT)(chunk2mem(p))) % alignment) == 0);
3666
}
3667
3668
/* Also give back spare room at the end */
3669
if (!chunk_is_mmapped(p)) {
3670
size = chunksize(p);
3671
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb + MINSIZE)) {
3672
remainder_size = size - nb;
3673
remainder = chunk_at_offset(p, nb);
3674
set_head(remainder, remainder_size | PREV_INUSE);
3675
set_head_size(p, nb);
3676
fREe(chunk2mem(remainder));
3677
}
3678
}
3679
3680
check_inuse_chunk(p);
3681
return chunk2mem(p);
3682
}
3683
3684
/*
3685
------------------------------ calloc ------------------------------
3686
*/
3687
3688
Void_t* cALLOc(size_t n_elements, size_t elem_size) {
3689
Void_t* mem = mALLOc(n_elements * elem_size);
3690
3691
if (mem != 0) {
3692
mchunkptr p = mem2chunk(mem);
3693
INTERNAL_SIZE_T* d = (INTERNAL_SIZE_T*)mem;
3694
3695
if (!chunk_is_mmapped(p))
3696
{
3697
/*
3698
Unroll clear of <= 36 bytes (72 if 8byte sizes)
3699
We know that contents have an odd number of
3700
INTERNAL_SIZE_T-sized words; minimally 3.
3701
*/
3702
3703
CHUNK_SIZE_T clearsize = chunksize(p) - SIZE_SZ;
3704
CHUNK_SIZE_T nclears = clearsize / sizeof(INTERNAL_SIZE_T);
3705
assert(nclears >= 3);
3706
3707
if (nclears > 9)
3708
MALLOC_ZERO(d, clearsize);
3709
3710
else {
3711
*(d+0) = 0;
3712
*(d+1) = 0;
3713
*(d+2) = 0;
3714
if (nclears > 4) {
3715
*(d+3) = 0;
3716
*(d+4) = 0;
3717
if (nclears > 6) {
3718
*(d+5) = 0;
3719
*(d+6) = 0;
3720
if (nclears > 8) {
3721
*(d+7) = 0;
3722
*(d+8) = 0;
3723
}
3724
}
3725
}
3726
}
3727
}
3728
#if ! MMAP_CLEARS
3729
else
3730
{
3731
/*
3732
Note the additional SIZE_SZ
3733
*/
3734
CHUNK_SIZE_T clearsize = chunksize(p) - 2*SIZE_SZ;
3735
MALLOC_ZERO(d, clearsize);
3736
}
3737
#endif
3738
}
3739
return mem;
3740
}
3741
3742
/*
3743
------------------------------ cfree ------------------------------
3744
*/
3745
3746
void cFREe(Void_t *mem) {
3747
fREe(mem);
3748
}
3749
3750
/*
3751
------------------------- independent_calloc -------------------------
3752
*/
3753
3754
3755
Void_t** iCALLOc(size_t n_elements, size_t elem_size, Void_t* chunks[]) {
3756
size_t sz = elem_size; /* serves as 1-element array */
3757
/* opts arg of 3 means all elements are same size, and should be cleared */
3758
return iALLOc(n_elements, &sz, 3, chunks);
3759
}
3760
3761
/*
3762
------------------------- independent_comalloc -------------------------
3763
*/
3764
3765
Void_t** iCOMALLOc(size_t n_elements, size_t sizes[], Void_t* chunks[]) {
3766
return iALLOc(n_elements, sizes, 0, chunks);
3767
}
3768
3769
3770
/*
3771
------------------------------ ialloc ------------------------------
3772
ialloc provides common support for independent_X routines, handling all of
3773
the combinations that can result.
3774
3775
The opts arg has:
3776
bit 0 set if all elements are same size (using sizes[0])
3777
bit 1 set if elements should be zeroed
3778
*/
3779
3780
3781
static Void_t** iALLOc(size_t n_elements,
3782
size_t* sizes,
3783
int opts,
3784
Void_t* chunks[]) {
3785
mstate av = get_malloc_state();
3786
INTERNAL_SIZE_T element_size; /* chunksize of each element, if all same */
3787
INTERNAL_SIZE_T contents_size; /* total size of elements */
3788
INTERNAL_SIZE_T array_size; /* request size of pointer array */
3789
Void_t* mem; /* malloced aggregate space */
3790
mchunkptr p; /* corresponding chunk */
3791
CHUNK_SIZE_T remainder_size; /* remaining bytes while splitting */
3792
Void_t** marray; /* either "chunks" or malloced ptr array */
3793
mchunkptr array_chunk; /* chunk for malloced ptr array */
3794
unsigned int mprops; /* to disable mmap */
3795
CHUNK_SIZE_T size;
3796
size_t i;
3797
3798
ensure_initialization(av);
3799
3800
/* compute array length, if needed */
3801
if (chunks != 0) {
3802
if (n_elements == 0)
3803
return chunks; /* nothing to do */
3804
marray = chunks;
3805
array_size = 0;
3806
}
3807
else {
3808
/* if empty req, must still return chunk representing empty array */
3809
if (n_elements == 0)
3810
return (Void_t**) mALLOc(0);
3811
marray = 0;
3812
array_size = request2size(n_elements * (sizeof(Void_t*)));
3813
}
3814
3815
/* compute total element size */
3816
if (opts & 0x1) { /* all-same-size */
3817
element_size = request2size(*sizes);
3818
contents_size = n_elements * element_size;
3819
}
3820
else { /* add up all the sizes */
3821
element_size = 0;
3822
contents_size = 0;
3823
for (i = 0; i != n_elements; ++i)
3824
contents_size += request2size(sizes[i]);
3825
}
3826
3827
/* subtract out alignment bytes from total to minimize overallocation */
3828
size = contents_size + array_size - MALLOC_ALIGN_MASK;
3829
3830
/*
3831
Allocate the aggregate chunk.
3832
But first disable mmap so malloc won't use it, since
3833
we would not be able to later free/realloc space internal
3834
to a segregated mmap region.
3835
*/
3836
3837
mprops = av->sysctl; /* disable mmap */
3838
disable_mmap(av);
3839
mem = mALLOc(size);
3840
av->sysctl = mprops; /* reset mmap */
3841
if (mem == 0)
3842
return 0;
3843
3844
p = mem2chunk(mem);
3845
assert(!chunk_is_mmapped(p));
3846
remainder_size = chunksize(p);
3847
3848
3849
if (opts & 0x2) { /* optionally clear the elements */
3850
MALLOC_ZERO(mem, remainder_size - SIZE_SZ - array_size);
3851
}
3852
3853
/* If not provided, allocate the pointer array as final part of chunk */
3854
if (marray == 0) {
3855
array_chunk = chunk_at_offset(p, contents_size);
3856
marray = (Void_t**) (chunk2mem(array_chunk));
3857
set_head(array_chunk, (remainder_size - contents_size) | PREV_INUSE);
3858
remainder_size = contents_size;
3859
}
3860
3861
/* split out elements */
3862
for (i = 0; ; ++i) {
3863
marray[i] = chunk2mem(p);
3864
if (i != n_elements-1) {
3865
if (element_size != 0)
3866
size = element_size;
3867
else
3868
size = request2size(sizes[i]);
3869
remainder_size -= size;
3870
set_head(p, size | PREV_INUSE);
3871
p = chunk_at_offset(p, size);
3872
}
3873
else { /* the final element absorbs any overallocation slop */
3874
set_head(p, remainder_size | PREV_INUSE);
3875
break;
3876
}
3877
}
3878
3879
#if DEBUG
3880
if (marray != chunks) {
3881
/* final element must have exactly exhausted chunk */
3882
if (element_size != 0)
3883
assert(remainder_size == element_size);
3884
else
3885
assert(remainder_size == request2size(sizes[i]));
3886
check_inuse_chunk(mem2chunk(marray));
3887
}
3888
3889
for (i = 0; i != n_elements; ++i)
3890
check_inuse_chunk(mem2chunk(marray[i]));
3891
#endif
3892
3893
return marray;
3894
}
3895
3896
3897
/*
3898
------------------------------ valloc ------------------------------
3899
*/
3900
3901
Void_t* vALLOc(size_t bytes) {
3902
mstate av = get_malloc_state();
3903
ensure_initialization(av);
3904
return mEMALIGn(av->pagesize, bytes);
3905
}
3906
3907
/*
3908
------------------------------ pvalloc ------------------------------
3909
*/
3910
3911
3912
Void_t* pVALLOc(size_t bytes) {
3913
mstate av = get_malloc_state();
3914
size_t pagesz;
3915
3916
ensure_initialization(av);
3917
pagesz = av->pagesize;
3918
return mEMALIGn(pagesz, (bytes + pagesz - 1) & ~(pagesz - 1));
3919
}
3920
3921
3922
/*
3923
------------------------------ malloc_trim ------------------------------
3924
*/
3925
3926
int mTRIm(size_t pad) {
3927
mstate av = get_malloc_state();
3928
return systrim(av, pad);
3929
}
3930
3931
3932
/*
3933
------------------------- malloc_usable_size -------------------------
3934
*/
3935
3936
size_t mUSABLe(Void_t* mem) {
3937
mchunkptr p;
3938
if (mem != 0) {
3939
p = mem2chunk(mem);
3940
if (chunk_is_mmapped(p))
3941
return chunksize(p) - 2*SIZE_SZ;
3942
else if (inuse(p))
3943
return chunksize(p) - SIZE_SZ;
3944
}
3945
return 0;
3946
}
3947
3948
/*
3949
------------------------------ mallinfo ------------------------------
3950
*/
3951
3952
/*
3953
Recursive helper function for mallinfo
3954
*/
3955
3956
static void count_tree_blocks(tchunkptr t, int* pcount, INTERNAL_SIZE_T* pavail) {
3957
while (t != 0) {
3958
tchunkptr p = t->bk;
3959
do {
3960
(*pcount)++;
3961
*pavail += chunksize(p);
3962
p = p->bk;
3963
} while (p != t);
3964
if (t->child[0] != 0)
3965
count_tree_blocks(t->child[0], pcount, pavail);
3966
t = t->child[1];
3967
}
3968
}
3969
3970
3971
3972
struct mallinfo mALLINFo()
3973
{
3974
mstate av = get_malloc_state();
3975
struct mallinfo mi;
3976
INTERNAL_SIZE_T avail;
3977
INTERNAL_SIZE_T topsize;
3978
int nblocks;
3979
INTERNAL_SIZE_T fastavail;
3980
int nfastblocks;
3981
mchunkptr p;
3982
3983
if (av->top == 0) {
3984
avail = 0;
3985
topsize = 0;
3986
nblocks = 0;
3987
}
3988
else {
3989
int i;
3990
check_malloc_state(av);
3991
3992
topsize = chunksize(av->top);
3993
avail = topsize;
3994
nblocks = 1; /* top always exists */
3995
3996
/* traverse fastbins */
3997
nfastblocks = 0;
3998
fastavail = 0;
3999
4000
for (i = 0; i < NFASTBINS; ++i) {
4001
for (p = av->fastbins[i]; p != 0; p = p->fd) {
4002
++nfastblocks;
4003
fastavail += chunksize(p);
4004
}
4005
}
4006
4007
avail += fastavail;
4008
4009
/* traverse small bins */
4010
for (i = 2; i < NBINS; ++i) {
4011
mbinptr b = bin_at(av, i);
4012
mchunkptr p;
4013
for (p = b->bk; p != b; p = p->bk) {
4014
++nblocks;
4015
avail += chunksize(p);
4016
}
4017
}
4018
4019
/* traverse tree bins */
4020
for (i = 0; i < NBINS; ++i) {
4021
tchunkptr t = *(tbin_at(av, i));
4022
if (t != 0)
4023
count_tree_blocks(t, &nblocks, &avail);
4024
}
4025
}
4026
4027
mi.smblks = nfastblocks;
4028
mi.smblks = 0;
4029
mi.ordblks = nblocks;
4030
mi.fordblks = avail;
4031
mi.uordblks = av->sbrked_mem - avail;
4032
mi.arena = av->sbrked_mem;
4033
mi.hblks = av->n_mmaps;
4034
mi.hblkhd = av->mmapped_mem;
4035
mi.fsmblks = 0;
4036
mi.keepcost = topsize;
4037
mi.usmblks = av->max_total_mem;
4038
return mi;
4039
}
4040
4041
/*
4042
------------------------------ malloc_stats ------------------------------
4043
*/
4044
4045
void mSTATs() {
4046
struct mallinfo mi = mALLINFo();
4047
4048
#ifdef WIN32
4049
{
4050
CHUNK_SIZE_T free, reserved, committed;
4051
vminfo (&free, &reserved, &committed);
4052
fprintf(stderr, "free bytes = %10lu\n",
4053
free);
4054
fprintf(stderr, "reserved bytes = %10lu\n",
4055
reserved);
4056
fprintf(stderr, "committed bytes = %10lu\n",
4057
committed);
4058
}
4059
#endif
4060
4061
4062
fprintf(stderr, "max system bytes = %10lu\n",
4063
(CHUNK_SIZE_T)(mi.usmblks));
4064
fprintf(stderr, "system bytes = %10lu\n",
4065
(CHUNK_SIZE_T)(mi.arena + mi.hblkhd));
4066
fprintf(stderr, "in use bytes = %10lu\n",
4067
(CHUNK_SIZE_T)(mi.uordblks + mi.hblkhd));
4068
4069
#if 0
4070
fprintf(stderr, "n0 = %10u\n", n0);
4071
fprintf(stderr, "n1 = %10u\n", n1);
4072
fprintf(stderr, "n2 = %10u\n", n2);
4073
fprintf(stderr, "n3 = %10u\n", n3);
4074
fprintf(stderr, "n4 = %10u\n", n4);
4075
fprintf(stderr, "n5 = %10u\n", n5);
4076
fprintf(stderr, "n6 = %10u\n", n6);
4077
fprintf(stderr, "n7 = %10u\n", n7);
4078
fprintf(stderr, "n8 = %10u\n", n8);
4079
#endif
4080
4081
4082
#ifdef WIN32
4083
{
4084
CHUNK_SIZE_T kernel, user;
4085
if (cpuinfo (TRUE, &kernel, &user)) {
4086
fprintf(stderr, "kernel ms = %10lu\n",
4087
kernel);
4088
fprintf(stderr, "user ms = %10lu\n",
4089
user);
4090
}
4091
}
4092
#endif
4093
}
4094
4095
4096
/*
4097
------------------------------ mallopt ------------------------------
4098
*/
4099
4100
int mALLOPt(int param_number, int value) {
4101
mstate av = get_malloc_state();
4102
4103
ensure_initialization(av);
4104
4105
switch(param_number) {
4106
case M_MXFAST:
4107
malloc_consolidate(av, MAX_CHUNK_SIZE, MAX_CHUNK_SIZE);
4108
if (value >= 0 && value <= MAX_FAST_SIZE) {
4109
set_max_fast(av, value);
4110
return 1;
4111
}
4112
else
4113
return 0;
4114
4115
case M_TRIM_THRESHOLD:
4116
av->trim_threshold = value;
4117
return 1;
4118
4119
case M_TOP_PAD:
4120
av->top_pad = value;
4121
return 1;
4122
4123
case M_MMAP_THRESHOLD:
4124
av->mmap_threshold = value;
4125
return 1;
4126
4127
case M_MMAP_MAX:
4128
#if !HAVE_MMAP
4129
if (value != 0)
4130
return 0;
4131
#endif
4132
av->n_mmaps_max = value;
4133
return 1;
4134
4135
default:
4136
return 0;
4137
}
4138
}
4139
4140
/* ----------- Routines dealing with system allocation -------------- */
4141
4142
#if HAVE_MMAP
4143
static mchunkptr mmap_malloc(mstate av, INTERNAL_SIZE_T nb) {
4144
char* mm; /* return value from mmap call*/
4145
CHUNK_SIZE_T sum; /* for updating stats */
4146
mchunkptr p; /* the allocated/returned chunk */
4147
long size;
4148
INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
4149
long correction;
4150
size_t pagemask = av->pagesize - 1;
4151
4152
/*
4153
Round up size to nearest page. For mmapped chunks, the overhead
4154
is one SIZE_SZ unit larger than for normal chunks, because there
4155
is no following chunk whose prev_size field could be used.
4156
*/
4157
size = (nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
4158
4159
/* Don't try if size wraps around 0 */
4160
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb)) {
4161
4162
mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
4163
4164
if (mm != (char*)(MORECORE_FAILURE)) {
4165
4166
/*
4167
The offset to the start of the mmapped region is stored
4168
in the prev_size field of the chunk. This allows us to adjust
4169
returned start address to meet alignment requirements here
4170
and in memalign(), and still be able to compute proper
4171
address argument for later munmap in free() and realloc().
4172
*/
4173
4174
front_misalign = (INTERNAL_SIZE_T)chunk2mem(mm) & MALLOC_ALIGN_MASK;
4175
if (front_misalign > 0) {
4176
correction = MALLOC_ALIGNMENT - front_misalign;
4177
p = (mchunkptr)(mm + correction);
4178
p->prev_size = correction;
4179
set_head(p, (size - correction) |IS_MMAPPED);
4180
}
4181
else {
4182
p = (mchunkptr)mm;
4183
p->prev_size = 0;
4184
set_head(p, size|IS_MMAPPED);
4185
}
4186
4187
/* update statistics */
4188
4189
if (++av->n_mmaps > av->max_n_mmaps)
4190
av->max_n_mmaps = av->n_mmaps;
4191
4192
sum = av->mmapped_mem += size;
4193
if (sum > (CHUNK_SIZE_T)(av->max_mmapped_mem))
4194
av->max_mmapped_mem = sum;
4195
sum += av->sbrked_mem;
4196
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
4197
av->max_total_mem = sum;
4198
4199
check_chunk(p);
4200
4201
return p;
4202
}
4203
}
4204
return 0;
4205
}
4206
#endif
4207
4208
4209
/*
4210
sysmalloc handles malloc cases requiring more memory from the system.
4211
On entry, it is assumed that av->top does not have enough
4212
space to service request for nb bytes, thus requiring that av->top
4213
be extended or replaced.
4214
*/
4215
4216
static Void_t* sysmalloc(mstate av, CHUNK_SIZE_T nb) {
4217
mchunkptr old_top; /* incoming value of av->top */
4218
INTERNAL_SIZE_T old_size; /* its size */
4219
char* old_end; /* its end address */
4220
4221
long size; /* arg to first MORECORE or mmap call */
4222
char* brk; /* return value from MORECORE */
4223
4224
long correction; /* arg to 2nd MORECORE call */
4225
char* snd_brk; /* 2nd return val */
4226
4227
INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
4228
INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */
4229
char* aligned_brk; /* aligned offset into brk */
4230
4231
mchunkptr p; /* the allocated/returned chunk */
4232
mchunkptr remainder; /* remainder from allocation */
4233
CHUNK_SIZE_T remainder_size; /* its size */
4234
4235
CHUNK_SIZE_T sum; /* for updating stats */
4236
4237
size_t pagemask;
4238
4239
/*
4240
Initialize av if necessary
4241
*/
4242
if (av->top == 0) {
4243
malloc_init_state(av);
4244
/* to allow call solely for initialization */
4245
if (nb == 0)
4246
return 0;
4247
}
4248
4249
4250
#if HAVE_MMAP
4251
/*
4252
If have mmap, and the request size meets the mmap threshold, and
4253
the system supports mmap, and there are few enough currently
4254
allocated mmapped regions, try to directly map this request
4255
rather than expanding top.
4256
*/
4257
4258
if ((CHUNK_SIZE_T)(nb) >= (CHUNK_SIZE_T)(av->mmap_threshold) &&
4259
(av->n_mmaps < av->n_mmaps_max) &&
4260
!mmap_disabled(av)) {
4261
Void_t* mp = mmap_malloc(av, nb);
4262
if (mp != 0)
4263
return chunk2mem(mp);
4264
}
4265
#endif
4266
4267
4268
pagemask = av->pagesize - 1;
4269
4270
/* Record incoming configuration of top */
4271
4272
old_top = av->top;
4273
old_size = chunksize(old_top);
4274
old_end = (char*)(chunk_at_offset(old_top, old_size));
4275
4276
brk = snd_brk = (char*)(MORECORE_FAILURE);
4277
4278
/*
4279
If not the first time through, we require old_size to be
4280
at least MINSIZE and to have prev_inuse set.
4281
*/
4282
4283
assert((old_top == (mchunkptr)(&(av->initial_top)) && old_size == 0) ||
4284
((CHUNK_SIZE_T) (old_size) >= MINSIZE &&
4285
prev_inuse(old_top)));
4286
4287
/* Precondition: not enough current space to satisfy nb request */
4288
assert((CHUNK_SIZE_T)(old_size) < (CHUNK_SIZE_T)(nb + MINSIZE));
4289
4290
/* Request enough space for nb + pad + overhead */
4291
4292
size = nb + av->top_pad + MINSIZE;
4293
4294
/*
4295
If contiguous, we can subtract out existing space that we hope to
4296
combine with new space. We add it back later only if
4297
we don't actually get contiguous space.
4298
*/
4299
4300
if (contiguous(av))
4301
size -= old_size;
4302
4303
/*
4304
Round to a multiple of page size.
4305
If MORECORE is not contiguous, this ensures that we only call it
4306
with whole-page arguments. And if MORECORE is contiguous and
4307
this is not first time through, this preserves page-alignment of
4308
previous calls. Otherwise, we correct to page-align below.
4309
*/
4310
4311
size = (size + pagemask) & ~pagemask;
4312
4313
/*
4314
Don't try to call MORECORE if argument is so big as to appear
4315
negative. Note that since mmap takes size_t arg, it may succeed
4316
below even if we cannot call MORECORE.
4317
*/
4318
4319
if (size > 0)
4320
brk = (char*)(MORECORE(size));
4321
4322
/*
4323
If have mmap, try using it as a backup when MORECORE fails or
4324
cannot be used. This is worth doing on systems that have "holes" in
4325
address space, so sbrk cannot extend to give contiguous space, but
4326
space is available elsewhere. Note that we ignore mmap max count
4327
and threshold limits, since the space will not be used as a
4328
segregated mmap region.
4329
*/
4330
4331
#if HAVE_MMAP
4332
if (brk == (char*)(MORECORE_FAILURE)) {
4333
4334
/* Cannot merge with old top, so add its size back in */
4335
if (contiguous(av))
4336
size = (size + old_size + pagemask) & ~pagemask;
4337
4338
/* If we are relying on mmap as backup, then use larger units */
4339
if ((CHUNK_SIZE_T)(size) < (CHUNK_SIZE_T)(MMAP_AS_MORECORE_SIZE))
4340
size = MMAP_AS_MORECORE_SIZE;
4341
4342
/* Don't try if size wraps around 0 */
4343
if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb)) {
4344
4345
brk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
4346
4347
if (brk != (char*)(MORECORE_FAILURE)) {
4348
4349
/* We do not need, and cannot use, another sbrk call to find end */
4350
snd_brk = brk + size;
4351
4352
/*
4353
Record that we no longer have a contiguous sbrk region.
4354
After the first time mmap is used as backup, we do not
4355
ever rely on contiguous space since this could incorrectly
4356
bridge regions.
4357
*/
4358
set_noncontiguous(av);
4359
}
4360
}
4361
}
4362
#endif
4363
4364
if (brk != (char*)(MORECORE_FAILURE)) {
4365
av->sbrked_mem += size;
4366
4367
/*
4368
If MORECORE extends previous space, we can likewise extend top size.
4369
*/
4370
4371
if (brk == old_end && snd_brk == (char*)(MORECORE_FAILURE)) {
4372
set_head(old_top, (size + old_size) | PREV_INUSE);
4373
}
4374
4375
/*
4376
Otherwise, make adjustments:
4377
4378
* If the first time through or noncontiguous, we need to call sbrk
4379
just to find out where the end of memory lies.
4380
4381
* We need to ensure that all returned chunks from malloc will meet
4382
MALLOC_ALIGNMENT
4383
4384
* If there was an intervening foreign sbrk, we need to adjust sbrk
4385
request size to account for fact that we will not be able to
4386
combine new space with existing space in old_top.
4387
4388
* Almost all systems internally allocate whole pages at a time, in
4389
which case we might as well use the whole last page of request.
4390
So we allocate enough more memory to hit a page boundary now,
4391
which in turn causes future contiguous calls to page-align.
4392
*/
4393
4394
else {
4395
front_misalign = 0;
4396
end_misalign = 0;
4397
correction = 0;
4398
aligned_brk = brk;
4399
4400
/*
4401
If MORECORE returns an address lower than we have seen before,
4402
we know it isn't really contiguous. This and some subsequent
4403
checks help cope with non-conforming MORECORE functions and
4404
the presence of "foreign" calls to MORECORE from outside of
4405
malloc or by other threads. We cannot guarantee to detect
4406
these in all cases, but cope with the ones we do detect.
4407
*/
4408
if (contiguous(av) && old_size != 0 && brk < old_end) {
4409
set_noncontiguous(av);
4410
}
4411
4412
/* handle contiguous cases */
4413
if (contiguous(av)) {
4414
4415
/*
4416
We can tolerate forward non-contiguities here (usually due
4417
to foreign calls) but treat them as part of our space for
4418
stats reporting.
4419
*/
4420
if (old_size != 0)
4421
av->sbrked_mem += brk - old_end;
4422
4423
/* Guarantee alignment of first new chunk made from this space */
4424
4425
front_misalign = (INTERNAL_SIZE_T)chunk2mem(brk) & MALLOC_ALIGN_MASK;
4426
if (front_misalign > 0) {
4427
4428
/*
4429
Skip over some bytes to arrive at an aligned position.
4430
We don't need to specially mark these wasted front bytes.
4431
They will never be accessed anyway because
4432
prev_inuse of av->top (and any chunk created from its start)
4433
is always true after initialization.
4434
*/
4435
4436
correction = MALLOC_ALIGNMENT - front_misalign;
4437
aligned_brk += correction;
4438
}
4439
4440
/*
4441
If this isn't adjacent to existing space, then we will not
4442
be able to merge with old_top space, so must add to 2nd request.
4443
*/
4444
4445
correction += old_size;
4446
4447
/* Extend the end address to hit a page boundary */
4448
end_misalign = (INTERNAL_SIZE_T)(brk + size + correction);
4449
correction += ((end_misalign + pagemask) & ~pagemask) - end_misalign;
4450
4451
assert(correction >= 0);
4452
snd_brk = (char*)(MORECORE(correction));
4453
4454
if (snd_brk == (char*)(MORECORE_FAILURE)) {
4455
/*
4456
If can't allocate correction, try to at least find out current
4457
brk. It might be enough to proceed without failing.
4458
*/
4459
correction = 0;
4460
snd_brk = (char*)(MORECORE(0));
4461
}
4462
else if (snd_brk < brk) {
4463
/*
4464
If the second call gives noncontiguous space even though
4465
it says it won't, the only course of action is to ignore
4466
results of second call, and conservatively estimate where
4467
the first call left us. Also set noncontiguous, so this
4468
won't happen again, leaving at most one hole.
4469
4470
Note that this check is intrinsically incomplete. Because
4471
MORECORE is allowed to give more space than we ask for,
4472
there is no reliable way to detect a noncontiguity
4473
producing a forward gap for the second call.
4474
*/
4475
snd_brk = brk + size;
4476
correction = 0;
4477
set_noncontiguous(av);
4478
}
4479
4480
}
4481
4482
/* handle non-contiguous cases */
4483
else {
4484
/* MORECORE/mmap must correctly align */
4485
assert(aligned_OK(chunk2mem(brk)));
4486
4487
/* Find out current end of memory */
4488
if (snd_brk == (char*)(MORECORE_FAILURE)) {
4489
snd_brk = (char*)(MORECORE(0));
4490
av->sbrked_mem += snd_brk - brk - size;
4491
}
4492
}
4493
4494
/* Adjust top based on results of second sbrk */
4495
if (snd_brk != (char*)(MORECORE_FAILURE)) {
4496
av->top = (mchunkptr)aligned_brk;
4497
set_head(av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
4498
av->sbrked_mem += correction;
4499
4500
/*
4501
If not the first time through, we either have a
4502
gap due to foreign sbrk or a non-contiguous region. Insert a
4503
double fencepost at old_top to prevent consolidation with space
4504
we don't own. These fenceposts are artificial chunks that are
4505
marked as inuse and are in any case too small to use. We need
4506
two to make sizes and alignments work out.
4507
*/
4508
4509
if (old_size != 0) {
4510
/*
4511
Shrink old_top to insert fenceposts, keeping size a
4512
multiple of MALLOC_ALIGNMENT. We know there is at least
4513
enough space in old_top to do this.
4514
*/
4515
old_size = (old_size - 3*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
4516
set_head(old_top, old_size | PREV_INUSE);
4517
4518
/*
4519
Note that the following assignments completely overwrite
4520
old_top when old_size was previously MINSIZE. This is
4521
intentional. We need the fencepost, even if old_top
4522
otherwise gets lost.
4523
*/
4524
chunk_at_offset(old_top, old_size )->size =
4525
SIZE_SZ|PREV_INUSE;
4526
4527
chunk_at_offset(old_top, old_size + SIZE_SZ)->size =
4528
SIZE_SZ|PREV_INUSE;
4529
4530
/*
4531
If possible, release the rest, suppressing trimming.
4532
*/
4533
if (old_size >= MINSIZE) {
4534
unsigned int mprops = av->sysctl;
4535
disable_trim(av);
4536
fREe(chunk2mem(old_top));
4537
av->sysctl = mprops;
4538
}
4539
}
4540
}
4541
}
4542
4543
/* Update statistics */
4544
sum = av->sbrked_mem;
4545
if (sum > (CHUNK_SIZE_T)(av->max_sbrked_mem))
4546
av->max_sbrked_mem = sum;
4547
4548
sum += av->mmapped_mem;
4549
if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
4550
av->max_total_mem = sum;
4551
4552
4553
/* finally, do the allocation */
4554
4555
p = av->top;
4556
size = chunksize(p);
4557
4558
/* check that one of the above allocation paths succeeded */
4559
if ((CHUNK_SIZE_T)(size) >= (CHUNK_SIZE_T)(nb + MINSIZE)) {
4560
remainder_size = size - nb;
4561
remainder = chunk_at_offset(p, nb);
4562
av->top = remainder;
4563
set_head(p, nb | PREV_INUSE);
4564
set_head(remainder, remainder_size | PREV_INUSE);
4565
check_malloced_chunk(p, nb);
4566
check_malloc_state(av);
4567
return chunk2mem(p);
4568
}
4569
4570
}
4571
4572
/* catch all failure paths */
4573
check_malloc_state(av);
4574
MALLOC_FAILURE_ACTION;
4575
return 0;
4576
}
4577
4578
4579
/*
4580
systrim is an inverse of sorts to sysmalloc. It gives memory back
4581
to the system (via negative arguments to sbrk) if there is unused
4582
memory at the `high' end of the malloc pool. It is called
4583
automatically by free() when top space exceeds the trim
4584
threshold. It is also called by the public malloc_trim routine. It
4585
returns 1 if it actually released any memory, else 0.
4586
*/
4587
4588
static int systrim(mstate av, size_t pad) {
4589
long top_size; /* Amount of top-most memory */
4590
long extra; /* Amount to release */
4591
long released; /* Amount actually released */
4592
char* current_brk; /* address returned by pre-check sbrk call */
4593
char* new_brk; /* address returned by post-check sbrk call */
4594
size_t pagesz;
4595
4596
ensure_initialization(av);
4597
4598
if (have_fastchunks(av))
4599
malloc_consolidate(av, MAX_CHUNK_SIZE, MAX_CHUNK_SIZE);
4600
4601
if (!trim_disabled(av)) {
4602
4603
#ifndef MORECORE_CANNOT_TRIM
4604
4605
pagesz = av->pagesize;
4606
top_size = chunksize(av->top);
4607
4608
/* Release in pagesize units, keeping at least one page */
4609
extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
4610
4611
if (extra > 0) {
4612
4613
/*
4614
Only proceed if end of memory is where we last set it.
4615
This avoids problems if there were foreign sbrk calls.
4616
*/
4617
current_brk = (char*)(MORECORE(0));
4618
if (current_brk == (char*)(av->top) + top_size) {
4619
4620
/*
4621
Attempt to release memory. We ignore MORECORE return value,
4622
and instead call again to find out where new end of memory is.
4623
This avoids problems if first call releases less than we asked,
4624
of if failure somehow altered brk value. (We could still
4625
encounter problems if it altered brk in some very bad way,
4626
but the only thing we can do is adjust anyway, which will cause
4627
some downstream failure.)
4628
*/
4629
4630
MORECORE(-extra);
4631
new_brk = (char*)(MORECORE(0));
4632
4633
if (new_brk != (char*)MORECORE_FAILURE) {
4634
released = (long)(current_brk - new_brk);
4635
4636
if (released != 0) {
4637
/* Success. Adjust top. */
4638
av->sbrked_mem -= released;
4639
set_head(av->top, (top_size - released) | PREV_INUSE);
4640
check_malloc_state(av);
4641
return 1;
4642
}
4643
}
4644
}
4645
}
4646
}
4647
#endif
4648
return 0;
4649
}
4650
4651
4652
/*
4653
-------------------- Alternative MORECORE functions --------------------
4654
*/
4655
4656
4657
/*
4658
General Requirements for MORECORE.
4659
4660
The MORECORE function must have the following properties:
4661
4662
If MORECORE_CONTIGUOUS is false:
4663
4664
* MORECORE must allocate in multiples of pagesize. It will
4665
only be called with arguments that are multiples of pagesize.
4666
4667
* MORECORE(0) must return an address that is at least
4668
MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
4669
4670
else (i.e. If MORECORE_CONTIGUOUS is true):
4671
4672
* Consecutive calls to MORECORE with positive arguments
4673
return increasing addresses, indicating that space has been
4674
contiguously extended.
4675
4676
* MORECORE need not allocate in multiples of pagesize.
4677
Calls to MORECORE need not have args of multiples of pagesize.
4678
4679
* MORECORE need not page-align.
4680
4681
In either case:
4682
4683
* MORECORE may allocate more memory than requested. (Or even less,
4684
but this will generally result in a malloc failure.)
4685
4686
* MORECORE must not allocate memory when given argument zero, but
4687
instead return one past the end address of memory from previous
4688
nonzero call. This malloc does NOT call MORECORE(0)
4689
until at least one call with positive arguments is made, so
4690
the initial value returned is not important.
4691
4692
* Even though consecutive calls to MORECORE need not return contiguous
4693
addresses, it must be OK for malloc'ed chunks to span multiple
4694
regions in those cases where they do happen to be contiguous.
4695
4696
* MORECORE need not handle negative arguments -- it may instead
4697
just return MORECORE_FAILURE when given negative arguments.
4698
Negative arguments are always multiples of pagesize. MORECORE
4699
must not misinterpret negative args as large positive unsigned
4700
args. You can suppress all such calls from even occurring by defining
4701
MORECORE_CANNOT_TRIM,
4702
4703
There is some variation across systems about the type of the
4704
argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
4705
actually be size_t, because sbrk supports negative args, so it is
4706
normally the signed type of the same width as size_t (sometimes
4707
declared as "intptr_t", and sometimes "ptrdiff_t"). It doesn't much
4708
matter though. Internally, we use "long" as arguments, which should
4709
work across all reasonable possibilities.
4710
4711
Additionally, if MORECORE ever returns failure for a positive
4712
request, and HAVE_MMAP is true, then mmap is used as a noncontiguous
4713
system allocator. This is a useful backup strategy for systems with
4714
holes in address spaces -- in this case sbrk cannot contiguously
4715
expand the heap, but mmap may be able to map noncontiguous space.
4716
4717
If you'd like mmap to ALWAYS be used, you can define MORECORE to be
4718
a function that always returns MORECORE_FAILURE.
4719
4720
Malloc only has limited ability to detect failures of MORECORE
4721
to supply contiguous space when it says it can. In particular,
4722
multithreaded programs that do not use locks may result in
4723
rece conditions across calls to MORECORE that result in gaps
4724
that cannot be detected as such, and subsequent corruption.
4725
4726
If you are using this malloc with something other than sbrk (or its
4727
emulation) to supply memory regions, you probably want to set
4728
MORECORE_CONTIGUOUS as false. As an example, here is a custom
4729
allocator kindly contributed for pre-OSX macOS. It uses virtually
4730
but not necessarily physically contiguous non-paged memory (locked
4731
in, present and won't get swapped out). You can use it by
4732
uncommenting this section, adding some #includes, and setting up the
4733
appropriate defines above:
4734
4735
#define MORECORE osMoreCore
4736
#define MORECORE_CONTIGUOUS 0
4737
4738
There is also a shutdown routine that should somehow be called for
4739
cleanup upon program exit.
4740
4741
#define MAX_POOL_ENTRIES 100
4742
#define MINIMUM_MORECORE_SIZE (64 * 1024)
4743
static int next_os_pool;
4744
void *our_os_pools[MAX_POOL_ENTRIES];
4745
4746
void *osMoreCore(int size)
4747
{
4748
void *ptr = 0;
4749
static void *sbrk_top = 0;
4750
4751
if (size > 0)
4752
{
4753
if (size < MINIMUM_MORECORE_SIZE)
4754
size = MINIMUM_MORECORE_SIZE;
4755
if (CurrentExecutionLevel() == kTaskLevel)
4756
ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4757
if (ptr == 0)
4758
{
4759
return (void *) MORECORE_FAILURE;
4760
}
4761
// save ptrs so they can be freed during cleanup
4762
our_os_pools[next_os_pool] = ptr;
4763
next_os_pool++;
4764
ptr = (void *) ((((CHUNK_SIZE_T) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4765
sbrk_top = (char *) ptr + size;
4766
return ptr;
4767
}
4768
else if (size < 0)
4769
{
4770
// we don't currently support shrink behavior
4771
return (void *) MORECORE_FAILURE;
4772
}
4773
else
4774
{
4775
return sbrk_top;
4776
}
4777
}
4778
4779
// cleanup any allocated memory pools
4780
// called as last thing before shutting down driver
4781
4782
void osCleanupMem(void)
4783
{
4784
void **ptr;
4785
4786
for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4787
if (*ptr)
4788
{
4789
PoolDeallocate(*ptr);
4790
*ptr = 0;
4791
}
4792
}
4793
4794
*/
4795
4796
4797
/*
4798
--------------------------------------------------------------
4799
4800
Emulation of sbrk for win32.
4801
Donated by J. Walter <Walter@GeNeSys-e.de>.
4802
For additional information about this code, and malloc on Win32, see
4803
http://www.genesys-e.de/jwalter/
4804
*/
4805
4806
4807
#ifdef WIN32
4808
4809
#ifdef _DEBUG
4810
/* #define TRACE */
4811
#endif
4812
4813
/* Support for USE_MALLOC_LOCK */
4814
#ifdef USE_MALLOC_LOCK
4815
4816
/* Wait for spin lock */
4817
static int slwait (int *sl) {
4818
while (InterlockedCompareExchange ((void **) sl, (void *) 1, (void *) 0) != 0)
4819
Sleep (0);
4820
return 0;
4821
}
4822
4823
/* Release spin lock */
4824
static int slrelease (int *sl) {
4825
InterlockedExchange (sl, 0);
4826
return 0;
4827
}
4828
4829
#ifdef NEEDED
4830
/* Spin lock for emulation code */
4831
static int g_sl;
4832
#endif
4833
4834
#endif /* USE_MALLOC_LOCK */
4835
4836
/* getpagesize for windows */
4837
static long getpagesize (void) {
4838
static long g_pagesize = 0;
4839
if (! g_pagesize) {
4840
SYSTEM_INFO system_info;
4841
GetSystemInfo (&system_info);
4842
g_pagesize = system_info.dwPageSize;
4843
}
4844
return g_pagesize;
4845
}
4846
static long getregionsize (void) {
4847
static long g_regionsize = 0;
4848
if (! g_regionsize) {
4849
SYSTEM_INFO system_info;
4850
GetSystemInfo (&system_info);
4851
g_regionsize = system_info.dwAllocationGranularity;
4852
}
4853
return g_regionsize;
4854
}
4855
4856
/* A region list entry */
4857
typedef struct _region_list_entry {
4858
void *top_allocated;
4859
void *top_committed;
4860
void *top_reserved;
4861
long reserve_size;
4862
struct _region_list_entry *previous;
4863
} region_list_entry;
4864
4865
/* Allocate and link a region entry in the region list */
4866
static int region_list_append (region_list_entry **last, void *base_reserved, long reserve_size) {
4867
region_list_entry *next = HeapAlloc (GetProcessHeap (), 0, sizeof (region_list_entry));
4868
if (! next)
4869
return FALSE;
4870
next->top_allocated = (char *) base_reserved;
4871
next->top_committed = (char *) base_reserved;
4872
next->top_reserved = (char *) base_reserved + reserve_size;
4873
next->reserve_size = reserve_size;
4874
next->previous = *last;
4875
*last = next;
4876
return TRUE;
4877
}
4878
/* Free and unlink the last region entry from the region list */
4879
static int region_list_remove (region_list_entry **last) {
4880
region_list_entry *previous = (*last)->previous;
4881
if (! HeapFree (GetProcessHeap (), sizeof (region_list_entry), *last))
4882
return FALSE;
4883
*last = previous;
4884
return TRUE;
4885
}
4886
4887
#define CEIL(size,to) (((size)+(to)-1)&~((to)-1))
4888
#define FLOOR(size,to) ((size)&~((to)-1))
4889
4890
#define SBRK_SCALE 0
4891
/* #define SBRK_SCALE 1 */
4892
/* #define SBRK_SCALE 2 */
4893
/* #define SBRK_SCALE 4 */
4894
4895
/* sbrk for windows */
4896
static void *sbrk (long size) {
4897
static long g_pagesize, g_my_pagesize;
4898
static long g_regionsize, g_my_regionsize;
4899
static region_list_entry *g_last;
4900
void *result = (void *) MORECORE_FAILURE;
4901
#ifdef TRACE
4902
printf ("sbrk %d\n", size);
4903
#endif
4904
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
4905
/* Wait for spin lock */
4906
slwait (&g_sl);
4907
#endif
4908
/* First time initialization */
4909
if (! g_pagesize) {
4910
g_pagesize = getpagesize ();
4911
g_my_pagesize = g_pagesize << SBRK_SCALE;
4912
}
4913
if (! g_regionsize) {
4914
g_regionsize = getregionsize ();
4915
g_my_regionsize = g_regionsize << SBRK_SCALE;
4916
}
4917
if (! g_last) {
4918
if (! region_list_append (&g_last, 0, 0))
4919
goto sbrk_exit;
4920
}
4921
/* Assert invariants */
4922
assert (g_last);
4923
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_allocated &&
4924
g_last->top_allocated <= g_last->top_committed);
4925
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_committed &&
4926
g_last->top_committed <= g_last->top_reserved &&
4927
(unsigned) g_last->top_committed % g_pagesize == 0);
4928
assert ((unsigned) g_last->top_reserved % g_regionsize == 0);
4929
assert ((unsigned) g_last->reserve_size % g_regionsize == 0);
4930
/* Allocation requested? */
4931
if (size >= 0) {
4932
/* Allocation size is the requested size */
4933
long allocate_size = size;
4934
/* Compute the size to commit */
4935
long to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
4936
/* Do we reach the commit limit? */
4937
if (to_commit > 0) {
4938
/* Round size to commit */
4939
long commit_size = CEIL (to_commit, g_my_pagesize);
4940
/* Compute the size to reserve */
4941
long to_reserve = (char *) g_last->top_committed + commit_size - (char *) g_last->top_reserved;
4942
/* Do we reach the reserve limit? */
4943
if (to_reserve > 0) {
4944
/* Compute the remaining size to commit in the current region */
4945
long remaining_commit_size = (char *) g_last->top_reserved - (char *) g_last->top_committed;
4946
if (remaining_commit_size > 0) {
4947
/* Assert preconditions */
4948
assert ((unsigned) g_last->top_committed % g_pagesize == 0);
4949
assert (0 < remaining_commit_size && remaining_commit_size % g_pagesize == 0); {
4950
/* Commit this */
4951
void *base_committed = VirtualAlloc (g_last->top_committed, remaining_commit_size,
4952
MEM_COMMIT, PAGE_READWRITE);
4953
/* Check returned pointer for consistency */
4954
if (base_committed != g_last->top_committed)
4955
goto sbrk_exit;
4956
/* Assert postconditions */
4957
assert ((unsigned) base_committed % g_pagesize == 0);
4958
#ifdef TRACE
4959
printf ("Commit %p %d\n", base_committed, remaining_commit_size);
4960
#endif
4961
/* Adjust the regions commit top */
4962
g_last->top_committed = (char *) base_committed + remaining_commit_size;
4963
}
4964
} {
4965
/* Now we are going to search and reserve. */
4966
int contiguous = -1;
4967
int found = FALSE;
4968
MEMORY_BASIC_INFORMATION memory_info;
4969
void *base_reserved;
4970
long reserve_size;
4971
do {
4972
/* Assume contiguous memory */
4973
contiguous = TRUE;
4974
/* Round size to reserve */
4975
reserve_size = CEIL (to_reserve, g_my_regionsize);
4976
/* Start with the current region's top */
4977
memory_info.BaseAddress = g_last->top_reserved;
4978
/* Assert preconditions */
4979
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
4980
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
4981
while (VirtualQuery (memory_info.BaseAddress, &memory_info, sizeof (memory_info))) {
4982
/* Assert postconditions */
4983
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
4984
#ifdef TRACE
4985
printf ("Query %p %d %s\n", memory_info.BaseAddress, memory_info.RegionSize,
4986
memory_info.State == MEM_FREE ? "FREE":
4987
(memory_info.State == MEM_RESERVE ? "RESERVED":
4988
(memory_info.State == MEM_COMMIT ? "COMMITTED": "?")));
4989
#endif
4990
/* Region is free, well aligned and big enough: we are done */
4991
if (memory_info.State == MEM_FREE &&
4992
(unsigned) memory_info.BaseAddress % g_regionsize == 0 &&
4993
memory_info.RegionSize >= (unsigned) reserve_size) {
4994
found = TRUE;
4995
break;
4996
}
4997
/* From now on we can't get contiguous memory! */
4998
contiguous = FALSE;
4999
/* Recompute size to reserve */
5000
reserve_size = CEIL (allocate_size, g_my_regionsize);
5001
memory_info.BaseAddress = (char *) memory_info.BaseAddress + memory_info.RegionSize;
5002
/* Assert preconditions */
5003
assert ((unsigned) memory_info.BaseAddress % g_pagesize == 0);
5004
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
5005
}
5006
/* Search failed? */
5007
if (! found)
5008
goto sbrk_exit;
5009
/* Assert preconditions */
5010
assert ((unsigned) memory_info.BaseAddress % g_regionsize == 0);
5011
assert (0 < reserve_size && reserve_size % g_regionsize == 0);
5012
/* Try to reserve this */
5013
base_reserved = VirtualAlloc (memory_info.BaseAddress, reserve_size,
5014
MEM_RESERVE, PAGE_NOACCESS);
5015
if (! base_reserved) {
5016
int rc = GetLastError ();
5017
if (rc != ERROR_INVALID_ADDRESS)
5018
goto sbrk_exit;
5019
}
5020
/* A null pointer signals (hopefully) a race condition with another thread. */
5021
/* In this case, we try again. */
5022
} while (! base_reserved);
5023
/* Check returned pointer for consistency */
5024
if (memory_info.BaseAddress && base_reserved != memory_info.BaseAddress)
5025
goto sbrk_exit;
5026
/* Assert postconditions */
5027
assert ((unsigned) base_reserved % g_regionsize == 0);
5028
#ifdef TRACE
5029
printf ("Reserve %p %d\n", base_reserved, reserve_size);
5030
#endif
5031
/* Did we get contiguous memory? */
5032
if (contiguous) {
5033
long start_size = (char *) g_last->top_committed - (char *) g_last->top_allocated;
5034
/* Adjust allocation size */
5035
allocate_size -= start_size;
5036
/* Adjust the regions allocation top */
5037
g_last->top_allocated = g_last->top_committed;
5038
/* Recompute the size to commit */
5039
to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
5040
/* Round size to commit */
5041
commit_size = CEIL (to_commit, g_my_pagesize);
5042
}
5043
/* Append the new region to the list */
5044
if (! region_list_append (&g_last, base_reserved, reserve_size))
5045
goto sbrk_exit;
5046
/* Didn't we get contiguous memory? */
5047
if (! contiguous) {
5048
/* Recompute the size to commit */
5049
to_commit = (char *) g_last->top_allocated + allocate_size - (char *) g_last->top_committed;
5050
/* Round size to commit */
5051
commit_size = CEIL (to_commit, g_my_pagesize);
5052
}
5053
}
5054
}
5055
/* Assert preconditions */
5056
assert ((unsigned) g_last->top_committed % g_pagesize == 0);
5057
assert (0 < commit_size && commit_size % g_pagesize == 0); {
5058
/* Commit this */
5059
void *base_committed = VirtualAlloc (g_last->top_committed, commit_size,
5060
MEM_COMMIT, PAGE_READWRITE);
5061
/* Check returned pointer for consistency */
5062
if (base_committed != g_last->top_committed)
5063
goto sbrk_exit;
5064
/* Assert postconditions */
5065
assert ((unsigned) base_committed % g_pagesize == 0);
5066
#ifdef TRACE
5067
printf ("Commit %p %d\n", base_committed, commit_size);
5068
#endif
5069
/* Adjust the regions commit top */
5070
g_last->top_committed = (char *) base_committed + commit_size;
5071
}
5072
}
5073
/* Adjust the regions allocation top */
5074
g_last->top_allocated = (char *) g_last->top_allocated + allocate_size;
5075
result = (char *) g_last->top_allocated - size;
5076
/* Deallocation requested? */
5077
} else if (size < 0) {
5078
long deallocate_size = - size;
5079
/* As long as we have a region to release */
5080
while ((char *) g_last->top_allocated - deallocate_size < (char *) g_last->top_reserved - g_last->reserve_size) {
5081
/* Get the size to release */
5082
long release_size = g_last->reserve_size;
5083
/* Get the base address */
5084
void *base_reserved = (char *) g_last->top_reserved - release_size;
5085
/* Assert preconditions */
5086
assert ((unsigned) base_reserved % g_regionsize == 0);
5087
assert (0 < release_size && release_size % g_regionsize == 0); {
5088
/* Release this */
5089
int rc = VirtualFree (base_reserved, 0,
5090
MEM_RELEASE);
5091
/* Check returned code for consistency */
5092
if (! rc)
5093
goto sbrk_exit;
5094
#ifdef TRACE
5095
printf ("Release %p %d\n", base_reserved, release_size);
5096
#endif
5097
}
5098
/* Adjust deallocation size */
5099
deallocate_size -= (char *) g_last->top_allocated - (char *) base_reserved;
5100
/* Remove the old region from the list */
5101
if (! region_list_remove (&g_last))
5102
goto sbrk_exit;
5103
} {
5104
/* Compute the size to decommit */
5105
long to_decommit = (char *) g_last->top_committed - ((char *) g_last->top_allocated - deallocate_size);
5106
if (to_decommit >= g_my_pagesize) {
5107
/* Compute the size to decommit */
5108
long decommit_size = FLOOR (to_decommit, g_my_pagesize);
5109
/* Compute the base address */
5110
void *base_committed = (char *) g_last->top_committed - decommit_size;
5111
/* Assert preconditions */
5112
assert ((unsigned) base_committed % g_pagesize == 0);
5113
assert (0 < decommit_size && decommit_size % g_pagesize == 0); {
5114
/* Decommit this */
5115
int rc = VirtualFree ((char *) base_committed, decommit_size,
5116
MEM_DECOMMIT);
5117
/* Check returned code for consistency */
5118
if (! rc)
5119
goto sbrk_exit;
5120
#ifdef TRACE
5121
printf ("Decommit %p %d\n", base_committed, decommit_size);
5122
#endif
5123
}
5124
/* Adjust deallocation size and regions commit and allocate top */
5125
deallocate_size -= (char *) g_last->top_allocated - (char *) base_committed;
5126
g_last->top_committed = base_committed;
5127
g_last->top_allocated = base_committed;
5128
}
5129
}
5130
/* Adjust regions allocate top */
5131
g_last->top_allocated = (char *) g_last->top_allocated - deallocate_size;
5132
/* Check for underflow */
5133
if ((char *) g_last->top_reserved - g_last->reserve_size > (char *) g_last->top_allocated ||
5134
g_last->top_allocated > g_last->top_committed) {
5135
/* Adjust regions allocate top */
5136
g_last->top_allocated = (char *) g_last->top_reserved - g_last->reserve_size;
5137
goto sbrk_exit;
5138
}
5139
result = g_last->top_allocated;
5140
}
5141
/* Assert invariants */
5142
assert (g_last);
5143
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_allocated &&
5144
g_last->top_allocated <= g_last->top_committed);
5145
assert ((char *) g_last->top_reserved - g_last->reserve_size <= (char *) g_last->top_committed &&
5146
g_last->top_committed <= g_last->top_reserved &&
5147
(unsigned) g_last->top_committed % g_pagesize == 0);
5148
assert ((unsigned) g_last->top_reserved % g_regionsize == 0);
5149
assert ((unsigned) g_last->reserve_size % g_regionsize == 0);
5150
5151
sbrk_exit:
5152
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5153
/* Release spin lock */
5154
slrelease (&g_sl);
5155
#endif
5156
return result;
5157
}
5158
5159
/* mmap for windows */
5160
static void *mmap (void *ptr, long size, long prot, long type, long handle, long arg) {
5161
static long g_pagesize;
5162
static long g_regionsize;
5163
#ifdef TRACE
5164
printf ("mmap %d\n", size);
5165
#endif
5166
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5167
/* Wait for spin lock */
5168
slwait (&g_sl);
5169
#endif
5170
/* First time initialization */
5171
if (! g_pagesize)
5172
g_pagesize = getpagesize ();
5173
if (! g_regionsize)
5174
g_regionsize = getregionsize ();
5175
/* Assert preconditions */
5176
assert ((unsigned) ptr % g_regionsize == 0);
5177
assert (size % g_pagesize == 0);
5178
/* Allocate this */
5179
ptr = VirtualAlloc (ptr, size,
5180
MEM_RESERVE | MEM_COMMIT | MEM_TOP_DOWN, PAGE_READWRITE);
5181
if (! ptr) {
5182
ptr = (void *) MORECORE_FAILURE;
5183
goto mmap_exit;
5184
}
5185
/* Assert postconditions */
5186
assert ((unsigned) ptr % g_regionsize == 0);
5187
#ifdef TRACE
5188
printf ("Commit %p %d\n", ptr, size);
5189
#endif
5190
mmap_exit:
5191
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5192
/* Release spin lock */
5193
slrelease (&g_sl);
5194
#endif
5195
return ptr;
5196
}
5197
5198
/* munmap for windows */
5199
static long munmap (void *ptr, long size) {
5200
static long g_pagesize;
5201
static long g_regionsize;
5202
int rc = MUNMAP_FAILURE;
5203
#ifdef TRACE
5204
printf ("munmap %p %d\n", ptr, size);
5205
#endif
5206
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5207
/* Wait for spin lock */
5208
slwait (&g_sl);
5209
#endif
5210
/* First time initialization */
5211
if (! g_pagesize)
5212
g_pagesize = getpagesize ();
5213
if (! g_regionsize)
5214
g_regionsize = getregionsize ();
5215
/* Assert preconditions */
5216
assert ((unsigned) ptr % g_regionsize == 0);
5217
assert (size % g_pagesize == 0);
5218
/* Free this */
5219
if (! VirtualFree (ptr, 0,
5220
MEM_RELEASE))
5221
goto munmap_exit;
5222
rc = 0;
5223
#ifdef TRACE
5224
printf ("Release %p %d\n", ptr, size);
5225
#endif
5226
munmap_exit:
5227
#if defined (USE_MALLOC_LOCK) && defined (NEEDED)
5228
/* Release spin lock */
5229
slrelease (&g_sl);
5230
#endif
5231
return rc;
5232
}
5233
5234
static void vminfo (CHUNK_SIZE_T *free, CHUNK_SIZE_T *reserved, CHUNK_SIZE_T *committed) {
5235
MEMORY_BASIC_INFORMATION memory_info;
5236
memory_info.BaseAddress = 0;
5237
*free = *reserved = *committed = 0;
5238
while (VirtualQuery (memory_info.BaseAddress, &memory_info, sizeof (memory_info))) {
5239
switch (memory_info.State) {
5240
case MEM_FREE:
5241
*free += memory_info.RegionSize;
5242
break;
5243
case MEM_RESERVE:
5244
*reserved += memory_info.RegionSize;
5245
break;
5246
case MEM_COMMIT:
5247
*committed += memory_info.RegionSize;
5248
break;
5249
}
5250
memory_info.BaseAddress = (char *) memory_info.BaseAddress + memory_info.RegionSize;
5251
}
5252
}
5253
5254
static int cpuinfo (int whole, CHUNK_SIZE_T *kernel, CHUNK_SIZE_T *user) {
5255
if (whole) {
5256
__int64 creation64, exit64, kernel64, user64;
5257
int rc = GetProcessTimes (GetCurrentProcess (),
5258
(FILETIME *) &creation64,
5259
(FILETIME *) &exit64,
5260
(FILETIME *) &kernel64,
5261
(FILETIME *) &user64);
5262
if (! rc) {
5263
*kernel = 0;
5264
*user = 0;
5265
return FALSE;
5266
}
5267
*kernel = (CHUNK_SIZE_T) (kernel64 / 10000);
5268
*user = (CHUNK_SIZE_T) (user64 / 10000);
5269
return TRUE;
5270
} else {
5271
__int64 creation64, exit64, kernel64, user64;
5272
int rc = GetThreadTimes (GetCurrentThread (),
5273
(FILETIME *) &creation64,
5274
(FILETIME *) &exit64,
5275
(FILETIME *) &kernel64,
5276
(FILETIME *) &user64);
5277
if (! rc) {
5278
*kernel = 0;
5279
*user = 0;
5280
return FALSE;
5281
}
5282
*kernel = (CHUNK_SIZE_T) (kernel64 / 10000);
5283
*user = (CHUNK_SIZE_T) (user64 / 10000);
5284
return TRUE;
5285
}
5286
}
5287
5288
#endif /* WIN32 */
5289
5290
/* ------------------------------------------------------------
5291
History:
5292
V2.8.0 (not yet released)
5293
* Use trees for non-small bins
5294
Also requiring different size->bin algorithm
5295
5296
V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
5297
* Allow tuning of FIRST_SORTED_BIN_SIZE
5298
* Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
5299
* Better detection and support for non-contiguousness of MORECORE.
5300
Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
5301
* Bypass most of malloc if no frees. Thanks To Emery Berger.
5302
* Fix freeing of old top non-contiguous chunk im sysmalloc.
5303
* Raised default trim and map thresholds to 256K.
5304
* Fix mmap-related #defines. Thanks to Lubos Lunak.
5305
* Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
5306
* Branch-free bin calculation
5307
* Default trim and mmap thresholds now 256K.
5308
5309
V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
5310
* Introduce independent_comalloc and independent_calloc.
5311
Thanks to Michael Pachos for motivation and help.
5312
* Make optional .h file available
5313
* Allow > 2GB requests on 32bit systems.
5314
* new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
5315
Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
5316
and Anonymous.
5317
* Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
5318
helping test this.)
5319
* memalign: check alignment arg
5320
* realloc: don't try to shift chunks backwards, since this
5321
leads to more fragmentation in some programs and doesn't
5322
seem to help in any others.
5323
* Collect all cases in malloc requiring system memory into sysmalloc
5324
* Use mmap as backup to sbrk
5325
* Place all internal state in malloc_state
5326
* Introduce fastbins (although similar to 2.5.1)
5327
* Many minor tunings and cosmetic improvements
5328
* Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
5329
* Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
5330
Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
5331
* Include errno.h to support default failure action.
5332
5333
V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
5334
* return null for negative arguments
5335
* Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5336
* Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5337
(e.g. WIN32 platforms)
5338
* Cleanup header file inclusion for WIN32 platforms
5339
* Cleanup code to avoid Microsoft Visual C++ compiler complaints
5340
* Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5341
memory allocation routines
5342
* Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5343
* Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5344
usage of 'assert' in non-WIN32 code
5345
* Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5346
avoid infinite loop
5347
* Always call 'fREe()' rather than 'free()'
5348
5349
V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
5350
* Fixed ordering problem with boundary-stamping
5351
5352
V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
5353
* Added pvalloc, as recommended by H.J. Liu
5354
* Added 64bit pointer support mainly from Wolfram Gloger
5355
* Added anonymously donated WIN32 sbrk emulation
5356
* Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5357
* malloc_extend_top: fix mask error that caused wastage after
5358
foreign sbrks
5359
* Add linux mremap support code from HJ Liu
5360
5361
V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
5362
* Integrated most documentation with the code.
5363
* Add support for mmap, with help from
5364
Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5365
* Use last_remainder in more cases.
5366
* Pack bins using idea from colin@nyx10.cs.du.edu
5367
* Use ordered bins instead of best-fit threshhold
5368
* Eliminate block-local decls to simplify tracing and debugging.
5369
* Support another case of realloc via move into top
5370
* Fix error occuring when initial sbrk_base not word-aligned.
5371
* Rely on page size for units instead of SBRK_UNIT to
5372
avoid surprises about sbrk alignment conventions.
5373
* Add mallinfo, mallopt. Thanks to Raymond Nijssen
5374
(raymond@es.ele.tue.nl) for the suggestion.
5375
* Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5376
* More precautions for cases where other routines call sbrk,
5377
courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5378
* Added macros etc., allowing use in linux libc from
5379
H.J. Lu (hjl@gnu.ai.mit.edu)
5380
* Inverted this history list
5381
5382
V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
5383
* Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5384
* Removed all preallocation code since under current scheme
5385
the work required to undo bad preallocations exceeds
5386
the work saved in good cases for most test programs.
5387
* No longer use return list or unconsolidated bins since
5388
no scheme using them consistently outperforms those that don't
5389
given above changes.
5390
* Use best fit for very large chunks to prevent some worst-cases.
5391
* Added some support for debugging
5392
5393
V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
5394
* Removed footers when chunks are in use. Thanks to
5395
Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5396
5397
V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
5398
* Added malloc_trim, with help from Wolfram Gloger
5399
(wmglo@Dent.MED.Uni-Muenchen.DE).
5400
5401
V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
5402
5403
V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
5404
* realloc: try to expand in both directions
5405
* malloc: swap order of clean-bin strategy;
5406
* realloc: only conditionally expand backwards
5407
* Try not to scavenge used bins
5408
* Use bin counts as a guide to preallocation
5409
* Occasionally bin return list chunks in first scan
5410
* Add a few optimizations from colin@nyx10.cs.du.edu
5411
5412
V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
5413
* faster bin computation & slightly different binning
5414
* merged all consolidations to one part of malloc proper
5415
(eliminating old malloc_find_space & malloc_clean_bin)
5416
* Scan 2 returns chunks (not just 1)
5417
* Propagate failure in realloc if malloc returns 0
5418
* Add stuff to allow compilation on non-ANSI compilers
5419
from kpv@research.att.com
5420
5421
V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
5422
* removed potential for odd address access in prev_chunk
5423
* removed dependency on getpagesize.h
5424
* misc cosmetics and a bit more internal documentation
5425
* anticosmetics: mangled names in macros to evade debugger strangeness
5426
* tested on sparc, hp-700, dec-mips, rs6000
5427
with gcc & native cc (hp, dec only) allowing
5428
Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5429
5430
Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
5431
* Based loosely on libg++-1.2X malloc. (It retains some of the overall
5432
structure of old version, but most details differ.)
5433
5434
*/
5435
Loggerhead is a web-based interface for Breezy
Version: 2.0.1