1 #define USE_LOCK 1
2
3 /*
4 This is a version (aka dlmalloc) of malloc/free/realloc written by
5 Doug Lea and released to the public domain, as explained at
6 http://creativecommons.org/licenses/publicdomain. Send questions,
7 comments, complaints, performance data, etc to dl@cs.oswego.edu
8
9 * Version 2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee)
10
11 Note: There may be an updated version of this malloc obtainable at
12 ftp://gee.cs.oswego.edu/pub/misc/malloc.c
13 Check before installing!
14
15 * Quickstart
16
17 This library is all in one file to simplify the most common usage:
18 ftp it, compile it (-O3), and link it into another program. All of
19 the compile-time options default to reasonable values for use on
20 most platforms. You might later want to step through various
21 compile-time and dynamic tuning options.
22
23 For convenience, an include file for code using this malloc is at:
24 ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.4.h
25 You don't really need this .h file unless you call functions not
26 defined in your system include files. The .h file contains only the
27 excerpts from this file needed for using this malloc on ANSI C/C++
28 systems, so long as you haven't changed compile-time options about
29 naming and tuning parameters. If you do, then you can create your
30 own malloc.h that does include all settings by cutting at the point
31 indicated below. Note that you may already by default be using a C
32 library containing a malloc that is based on some version of this
33 malloc (for example in linux). You might still want to use the one
34 in this file to customize settings or to avoid overheads associated
35 with library versions.
36
37 * Vital statistics:
38
39 Supported pointer/size_t representation: 4 or 8 bytes
40 size_t MUST be an unsigned type of the same width as
41 pointers. (If you are using an ancient system that declares
42 size_t as a signed type, or need it to be a different width
43 than pointers, you can use a previous release of this malloc
44 (e.g. 2.7.2) supporting these.)
45
46 Alignment: 8 bytes (default)
47 This suffices for nearly all current machines and C compilers.
48 However, you can define MALLOC_ALIGNMENT to be wider than this
49 if necessary (up to 128bytes), at the expense of using more space.
50
51 Minimum overhead per allocated chunk: 4 or 8 bytes (if 4byte sizes)
52 8 or 16 bytes (if 8byte sizes)
53 Each malloced chunk has a hidden word of overhead holding size
54 and status information, and additional cross-check word
55 if FOOTERS is defined.
56
57 Minimum allocated size: 4-byte ptrs: 16 bytes (including overhead)
58 8-byte ptrs: 32 bytes (including overhead)
59
60 Even a request for zero bytes (i.e., malloc(0)) returns a
61 pointer to something of the minimum allocatable size.
62 The maximum overhead wastage (i.e., number of extra bytes
63 allocated than were requested in malloc) is less than or equal
64 to the minimum size, except for requests >= mmap_threshold that
65 are serviced via mmap(), where the worst case wastage is about
66 32 bytes plus the remainder from a system page (the minimal
67 mmap unit); typically 4096 or 8192 bytes.
68
69 Security: static-safe; optionally more or less
70 The "security" of malloc refers to the ability of malicious
71 code to accentuate the effects of errors (for example, freeing
72 space that is not currently malloc'ed or overwriting past the
73 ends of chunks) in code that calls malloc. This malloc
74 guarantees not to modify any memory locations below the base of
75 heap, i.e., static variables, even in the presence of usage
76 errors. The routines additionally detect most improper frees
77 and reallocs. All this holds as long as the static bookkeeping
78 for malloc itself is not corrupted by some other means. This
79 is only one aspect of security -- these checks do not, and
80 cannot, detect all possible programming errors.
81
82 If FOOTERS is defined nonzero, then each allocated chunk
83 carries an additional check word to verify that it was malloced
84 from its space. These check words are the same within each
85 execution of a program using malloc, but differ across
86 executions, so externally crafted fake chunks cannot be
87 freed. This improves security by rejecting frees/reallocs that
88 could corrupt heap memory, in addition to the checks preventing
89 writes to statics that are always on. This may further improve
90 security at the expense of time and space overhead. (Note that
91 FOOTERS may also be worth using with MSPACES.)
92
93 By default detected errors cause the program to abort (calling
94 "abort()"). You can override this to instead proceed past
95 errors by defining PROCEED_ON_ERROR. In this case, a bad free
96 has no effect, and a malloc that encounters a bad address
97 caused by user overwrites will ignore the bad address by
98 dropping pointers and indices to all known memory. This may
99 be appropriate for programs that should continue if at all
100 possible in the face of programming errors, although they may
101 run out of memory because dropped memory is never reclaimed.
102
103 If you don't like either of these options, you can define
104 CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
105 else. And if if you are sure that your program using malloc has
106 no errors or vulnerabilities, you can define INSECURE to 1,
107 which might (or might not) provide a small performance improvement.
108
109 Thread-safety: NOT thread-safe unless USE_LOCKS defined
110 When USE_LOCKS is defined, each public call to malloc, free,
111 etc is surrounded with either a pthread mutex or a win32
112 spinlock (depending on WIN32). This is not especially fast, and
113 can be a major bottleneck. It is designed only to provide
114 minimal protection in concurrent environments, and to provide a
115 basis for extensions. If you are using malloc in a concurrent
116 program, consider instead using nedmalloc
117 (http://www.nedprod.com/programs/portable/nedmalloc/) or
118 ptmalloc (See http://www.malloc.de), which are derived
119 from versions of this malloc.
120
121 System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
122 This malloc can use unix sbrk or any emulation (invoked using
123 the CALL_MORECORE macro) and/or mmap/munmap or any emulation
124 (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
125 memory. On most unix systems, it tends to work best if both
126 MORECORE and MMAP are enabled. On Win32, it uses emulations
127 based on VirtualAlloc. It also uses common C library functions
128 like memset.
129
130 Compliance: I believe it is compliant with the Single Unix Specification
131 (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
132 others as well.
133
134 * Overview of algorithms
135
136 This is not the fastest, most space-conserving, most portable, or
137 most tunable malloc ever written. However it is among the fastest
138 while also being among the most space-conserving, portable and
139 tunable. Consistent balance across these factors results in a good
140 general-purpose allocator for malloc-intensive programs.
141
142 In most ways, this malloc is a best-fit allocator. Generally, it
143 chooses the best-fitting existing chunk for a request, with ties
144 broken in approximately least-recently-used order. (This strategy
145 normally maintains low fragmentation.) However, for requests less
146 than 256bytes, it deviates from best-fit when there is not an
147 exactly fitting available chunk by preferring to use space adjacent
148 to that used for the previous small request, as well as by breaking
149 ties in approximately most-recently-used order. (These enhance
150 locality of series of small allocations.) And for very large requests
151 (>= 256Kb by default), it relies on system memory mapping
152 facilities, if supported. (This helps avoid carrying around and
153 possibly fragmenting memory used only for large chunks.)
154
155 All operations (except malloc_stats and mallinfo) have execution
156 times that are bounded by a constant factor of the number of bits in
157 a size_t, not counting any clearing in calloc or copying in realloc,
158 or actions surrounding MORECORE and MMAP that have times
159 proportional to the number of non-contiguous regions returned by
160 system allocation routines, which is often just 1. In real-time
161 applications, you can optionally suppress segment traversals using
162 NO_SEGMENT_TRAVERSAL, which assures bounded execution even when
163 system allocators return non-contiguous spaces, at the typical
164 expense of carrying around more memory and increased fragmentation.
165
166 The implementation is not very modular and seriously overuses
167 macros. Perhaps someday all C compilers will do as good a job
168 inlining modular code as can now be done by brute-force expansion,
169 but now, enough of them seem not to.
170
171 Some compilers issue a lot of warnings about code that is
172 dead/unreachable only on some platforms, and also about intentional
173 uses of negation on unsigned types. All known cases of each can be
174 ignored.
175
176 For a longer but out of date high-level description, see
177 http://gee.cs.oswego.edu/dl/html/malloc.html
178
179 * MSPACES
180 If MSPACES is defined, then in addition to malloc, free, etc.,
181 this file also defines mspace_malloc, mspace_free, etc. These
182 are versions of malloc routines that take an "mspace" argument
183 obtained using create_mspace, to control all internal bookkeeping.
184 If ONLY_MSPACES is defined, only these versions are compiled.
185 So if you would like to use this allocator for only some allocations,
186 and your system malloc for others, you can compile with
187 ONLY_MSPACES and then do something like...
188 static mspace mymspace = create_mspace(0,0); // for example
189 #define mymalloc(bytes) mspace_malloc(mymspace, bytes)
190
191 (Note: If you only need one instance of an mspace, you can instead
192 use "USE_DL_PREFIX" to relabel the global malloc.)
193
194 You can similarly create thread-local allocators by storing
195 mspaces as thread-locals. For example:
196 static __thread mspace tlms = 0;
197 void* tlmalloc(size_t bytes) {
198 if (tlms == 0) tlms = create_mspace(0, 0);
199 return mspace_malloc(tlms, bytes);
200 }
201 void tlfree(void* mem) { mspace_free(tlms, mem); }
202
203 Unless FOOTERS is defined, each mspace is completely independent.
204 You cannot allocate from one and free to another (although
205 conformance is only weakly checked, so usage errors are not always
206 caught). If FOOTERS is defined, then each chunk carries around a tag
207 indicating its originating mspace, and frees are directed to their
208 originating spaces.
209
210 ------------------------- Compile-time options ---------------------------
211
212 Be careful in setting #define values for numerical constants of type
213 size_t. On some systems, literal values are not automatically extended
214 to size_t precision unless they are explicitly casted. You can also
215 use the symbolic values MAX_SIZE_T, SIZE_T_ONE, etc below.
216
217 WIN32 default: defined if _WIN32 defined
218 Defining WIN32 sets up defaults for MS environment and compilers.
219 Otherwise defaults are for unix. Beware that there seem to be some
220 cases where this malloc might not be a pure drop-in replacement for
221 Win32 malloc: Random-looking failures from Win32 GDI API's (eg;
222 SetDIBits()) may be due to bugs in some video driver implementations
223 when pixel buffers are malloc()ed, and the region spans more than
224 one VirtualAlloc()ed region. Because dlmalloc uses a small (64Kb)
225 default granularity, pixel buffers may straddle virtual allocation
226 regions more often than when using the Microsoft allocator. You can
227 avoid this by using VirtualAlloc() and VirtualFree() for all pixel
228 buffers rather than using malloc(). If this is not possible,
229 recompile this malloc with a larger DEFAULT_GRANULARITY.
230
231 MALLOC_ALIGNMENT default: (size_t)8
232 Controls the minimum alignment for malloc'ed chunks. It must be a
233 power of two and at least 8, even on machines for which smaller
234 alignments would suffice. It may be defined as larger than this
235 though. Note however that code and data structures are optimized for
236 the case of 8-byte alignment.
237
238 MSPACES default: 0 (false)
239 If true, compile in support for independent allocation spaces.
240 This is only supported if HAVE_MMAP is true.
241
242 ONLY_MSPACES default: 0 (false)
243 If true, only compile in mspace versions, not regular versions.
244
245 USE_LOCKS default: 0 (false)
246 Causes each call to each public routine to be surrounded with
247 pthread or WIN32 mutex lock/unlock. (If set true, this can be
248 overridden on a per-mspace basis for mspace versions.) If set to a
249 non-zero value other than 1, locks are used, but their
250 implementation is left out, so lock functions must be supplied manually,
251 as described below.
252
253 USE_SPIN_LOCKS default: 1 iff USE_LOCKS and on x86 using gcc or MSC
254 If true, uses custom spin locks for locking. This is currently
255 supported only for x86 platforms using gcc or recent MS compilers.
256 Otherwise, posix locks or win32 critical sections are used.
257
258 FOOTERS default: 0
259 If true, provide extra checking and dispatching by placing
260 information in the footers of allocated chunks. This adds
261 space and time overhead.
262
263 INSECURE default: 0
264 If true, omit checks for usage errors and heap space overwrites.
265
266 USE_DL_PREFIX default: NOT defined
267 Causes compiler to prefix all public routines with the string 'dl'.
268 This can be useful when you only want to use this malloc in one part
269 of a program, using your regular system malloc elsewhere.
270
271 ABORT default: defined as abort()
272 Defines how to abort on failed checks. On most systems, a failed
273 check cannot die with an "assert" or even print an informative
274 message, because the underlying print routines in turn call malloc,
275 which will fail again. Generally, the best policy is to simply call
276 abort(). It's not very useful to do more than this because many
277 errors due to overwriting will show up as address faults (null, odd
278 addresses etc) rather than malloc-triggered checks, so will also
279 abort. Also, most compilers know that abort() does not return, so
280 can better optimize code conditionally calling it.
281
282 PROCEED_ON_ERROR default: defined as 0 (false)
283 Controls whether detected bad addresses cause them to bypassed
284 rather than aborting. If set, detected bad arguments to free and
285 realloc are ignored. And all bookkeeping information is zeroed out
286 upon a detected overwrite of freed heap space, thus losing the
287 ability to ever return it from malloc again, but enabling the
288 application to proceed. If PROCEED_ON_ERROR is defined, the
289 static variable malloc_corruption_error_count is compiled in
290 and can be examined to see if errors have occurred. This option
291 generates slower code than the default abort policy.
292
293 DEBUG default: NOT defined
294 The DEBUG setting is mainly intended for people trying to modify
295 this code or diagnose problems when porting to new platforms.
296 However, it may also be able to better isolate user errors than just
297 using runtime checks. The assertions in the check routines spell
298 out in more detail the assumptions and invariants underlying the
299 algorithms. The checking is fairly extensive, and will slow down
300 execution noticeably. Calling malloc_stats or mallinfo with DEBUG
301 set will attempt to check every non-mmapped allocated and free chunk
302 in the course of computing the summaries.
303
304 ABORT_ON_ASSERT_FAILURE default: defined as 1 (true)
305 Debugging assertion failures can be nearly impossible if your
306 version of the assert macro causes malloc to be called, which will
307 lead to a cascade of further failures, blowing the runtime stack.
308 ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
309 which will usually make debugging easier.
310
311 MALLOC_FAILURE_ACTION default: sets errno to ENOMEM, or no-op on win32
312 The action to take before "return 0" when malloc fails to be able to
313 return memory because there is none available.
314
315 HAVE_MORECORE default: 1 (true) unless win32 or ONLY_MSPACES
316 True if this system supports sbrk or an emulation of it.
317
318 MORECORE default: sbrk
319 The name of the sbrk-style system routine to call to obtain more
320 memory. See below for guidance on writing custom MORECORE
321 functions. The type of the argument to sbrk/MORECORE varies across
322 systems. It cannot be size_t, because it supports negative
323 arguments, so it is normally the signed type of the same width as
324 size_t (sometimes declared as "intptr_t"). It doesn't much matter
325 though. Internally, we only call it with arguments less than half
326 the max value of a size_t, which should work across all reasonable
327 possibilities, although sometimes generating compiler warnings.
328
329 MORECORE_CONTIGUOUS default: 1 (true) if HAVE_MORECORE
330 If true, take advantage of fact that consecutive calls to MORECORE
331 with positive arguments always return contiguous increasing
332 addresses. This is true of unix sbrk. It does not hurt too much to
333 set it true anyway, since malloc copes with non-contiguities.
334 Setting it false when definitely non-contiguous saves time
335 and possibly wasted space it would take to discover this though.
336
337 MORECORE_CANNOT_TRIM default: NOT defined
338 True if MORECORE cannot release space back to the system when given
339 negative arguments. This is generally necessary only if you are
340 using a hand-crafted MORECORE function that cannot handle negative
341 arguments.
342
343 NO_SEGMENT_TRAVERSAL default: 0
344 If non-zero, suppresses traversals of memory segments
345 returned by either MORECORE or CALL_MMAP. This disables
346 merging of segments that are contiguous, and selectively
347 releasing them to the OS if unused, but bounds execution times.
348
349 HAVE_MMAP default: 1 (true)
350 True if this system supports mmap or an emulation of it. If so, and
351 HAVE_MORECORE is not true, MMAP is used for all system
352 allocation. If set and HAVE_MORECORE is true as well, MMAP is
353 primarily used to directly allocate very large blocks. It is also
354 used as a backup strategy in cases where MORECORE fails to provide
355 space from system. Note: A single call to MUNMAP is assumed to be
356 able to unmap memory that may have be allocated using multiple calls
357 to MMAP, so long as they are adjacent.
358
359 HAVE_MREMAP default: 1 on linux, else 0
360 If true realloc() uses mremap() to re-allocate large blocks and
361 extend or shrink allocation spaces.
362
363 MMAP_CLEARS default: 1 except on WINCE.
364 True if mmap clears memory so calloc doesn't need to. This is true
365 for standard unix mmap using /dev/zero and on WIN32 except for WINCE.
366
367 USE_BUILTIN_FFS default: 0 (i.e., not used)
368 Causes malloc to use the builtin ffs() function to compute indices.
369 Some compilers may recognize and intrinsify ffs to be faster than the
370 supplied C version. Also, the case of x86 using gcc is special-cased
371 to an asm instruction, so is already as fast as it can be, and so
372 this setting has no effect. Similarly for Win32 under recent MS compilers.
373 (On most x86s, the asm version is only slightly faster than the C version.)
374
375 malloc_getpagesize default: derive from system includes, or 4096.
376 The system page size. To the extent possible, this malloc manages
377 memory from the system in page-size units. This may be (and
378 usually is) a function rather than a constant. This is ignored
379 if WIN32, where page size is determined using getSystemInfo during
380 initialization.
381
382 USE_DEV_RANDOM default: 0 (i.e., not used)
383 Causes malloc to use /dev/random to initialize secure magic seed for
384 stamping footers. Otherwise, the current time is used.
385
386 NO_MALLINFO default: 0
387 If defined, don't compile "mallinfo". This can be a simple way
388 of dealing with mismatches between system declarations and
389 those in this file.
390
391 MALLINFO_FIELD_TYPE default: size_t
392 The type of the fields in the mallinfo struct. This was originally
393 defined as "int" in SVID etc, but is more usefully defined as
394 size_t. The value is used only if HAVE_USR_INCLUDE_MALLOC_H is not set
395
396 REALLOC_ZERO_BYTES_FREES default: not defined
397 This should be set if a call to realloc with zero bytes should
398 be the same as a call to free. Some people think it should. Otherwise,
399 since this malloc returns a unique pointer for malloc(0), so does
400 realloc(p, 0).
401
402 LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
403 LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H, LACKS_ERRNO_H
404 LACKS_STDLIB_H default: NOT defined unless on WIN32
405 Define these if your system does not have these header files.
406 You might need to manually insert some of the declarations they provide.
407
408 DEFAULT_GRANULARITY default: page size if MORECORE_CONTIGUOUS,
409 system_info.dwAllocationGranularity in WIN32,
410 otherwise 64K.
411 Also settable using mallopt(M_GRANULARITY, x)
412 The unit for allocating and deallocating memory from the system. On
413 most systems with contiguous MORECORE, there is no reason to
414 make this more than a page. However, systems with MMAP tend to
415 either require or encourage larger granularities. You can increase
416 this value to prevent system allocation functions to be called so
417 often, especially if they are slow. The value must be at least one
418 page and must be a power of two. Setting to 0 causes initialization
419 to either page size or win32 region size. (Note: In previous
420 versions of malloc, the equivalent of this option was called
421 "TOP_PAD")
422
423 DEFAULT_TRIM_THRESHOLD default: 2MB
424 Also settable using mallopt(M_TRIM_THRESHOLD, x)
425 The maximum amount of unused top-most memory to keep before
426 releasing via malloc_trim in free(). Automatic trimming is mainly
427 useful in long-lived programs using contiguous MORECORE. Because
428 trimming via sbrk can be slow on some systems, and can sometimes be
429 wasteful (in cases where programs immediately afterward allocate
430 more large chunks) the value should be high enough so that your
431 overall system performance would improve by releasing this much
432 memory. As a rough guide, you might set to a value close to the
433 average size of a process (program) running on your system.
434 Releasing this much memory would allow such a process to run in
435 memory. Generally, it is worth tuning trim thresholds when a
436 program undergoes phases where several large chunks are allocated
437 and released in ways that can reuse each other's storage, perhaps
438 mixed with phases where there are no such chunks at all. The trim
439 value must be greater than page size to have any useful effect. To
440 disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
441 some people use of mallocing a huge space and then freeing it at
442 program startup, in an attempt to reserve system memory, doesn't
443 have the intended effect under automatic trimming, since that memory
444 will immediately be returned to the system.
445
446 DEFAULT_MMAP_THRESHOLD default: 256K
447 Also settable using mallopt(M_MMAP_THRESHOLD, x)
448 The request size threshold for using MMAP to directly service a
449 request. Requests of at least this size that cannot be allocated
450 using already-existing space will be serviced via mmap. (If enough
451 normal freed space already exists it is used instead.) Using mmap
452 segregates relatively large chunks of memory so that they can be
453 individually obtained and released from the host system. A request
454 serviced through mmap is never reused by any other request (at least
455 not directly; the system may just so happen to remap successive
456 requests to the same locations). Segregating space in this way has
457 the benefits that: Mmapped space can always be individually released
458 back to the system, which helps keep the system level memory demands
459 of a long-lived program low. Also, mapped memory doesn't become
460 `locked' between other chunks, as can happen with normally allocated
461 chunks, which means that even trimming via malloc_trim would not
462 release them. However, it has the disadvantage that the space
463 cannot be reclaimed, consolidated, and then used to service later
464 requests, as happens with normal chunks. The advantages of mmap
465 nearly always outweigh disadvantages for "large" chunks, but the
466 value of "large" may vary across systems. The default is an
467 empirically derived value that works well in most systems. You can
468 disable mmap by setting to MAX_SIZE_T.
469
470 MAX_RELEASE_CHECK_RATE default: 4095 unless not HAVE_MMAP
471 The number of consolidated frees between checks to release
472 unused segments when freeing. When using non-contiguous segments,
473 especially with multiple mspaces, checking only for topmost space
474 doesn't always suffice to trigger trimming. To compensate for this,
475 free() will, with a period of MAX_RELEASE_CHECK_RATE (or the
476 current number of segments, if greater) try to release unused
477 segments to the OS when freeing chunks that result in
478 consolidation. The best value for this parameter is a compromise
479 between slowing down frees with relatively costly checks that
480 rarely trigger versus holding on to unused memory. To effectively
481 disable, set to MAX_SIZE_T. This may lead to a very slight speed
482 improvement at the expense of carrying around more memory.
483 */
484
485 #if 0
486 #include <config.h>
487 #include <base/commandlineflags.h>
488 #include <google/malloc_extension.h>
489 #endif
490
491 /* Version identifier to allow people to support multiple versions */
492 #ifndef DLMALLOC_VERSION
493 #define DLMALLOC_VERSION 20804
494 #endif /* DLMALLOC_VERSION */
495
496 #ifndef WIN32
497 #ifdef _WIN32
498 #define WIN32 1
499 #endif /* _WIN32 */
500 #ifdef _WIN32_WCE
501 #define LACKS_FCNTL_H
502 #define WIN32 1
503 #endif /* _WIN32_WCE */
504 #endif /* WIN32 */
505 #ifdef WIN32
506 #define WIN32_LEAN_AND_MEAN
507 #include <windows.h>
508 #define HAVE_MMAP 1
509 #define HAVE_MORECORE 0
510 #define LACKS_UNISTD_H
511 #define LACKS_SYS_PARAM_H
512 #define LACKS_SYS_MMAN_H
513 #define LACKS_STRING_H
514 #define LACKS_STRINGS_H
515 #define LACKS_SYS_TYPES_H
516 #define LACKS_ERRNO_H
517 #ifndef MALLOC_FAILURE_ACTION
518 #define MALLOC_FAILURE_ACTION
519 #endif /* MALLOC_FAILURE_ACTION */
520 #ifdef _WIN32_WCE /* WINCE reportedly does not clear */
521 #define MMAP_CLEARS 0
522 #else
523 #define MMAP_CLEARS 1
524 #endif /* _WIN32_WCE */
525 #endif /* WIN32 */
526
527 #if defined(DARWIN) || defined(_DARWIN)
528 /* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
529 #ifndef HAVE_MORECORE
530 #define HAVE_MORECORE 0
531 #define HAVE_MMAP 1
532 /* OSX allocators provide 16 byte alignment */
533 #ifndef MALLOC_ALIGNMENT
534 #define MALLOC_ALIGNMENT ((size_t)16U)
535 #endif
536 #endif /* HAVE_MORECORE */
537 #endif /* DARWIN */
538
539 #ifndef LACKS_SYS_TYPES_H
540 #include <sys/types.h> /* For size_t */
541 #endif /* LACKS_SYS_TYPES_H */
542
543 #if (defined(__GNUC__) && ((defined(__i386__) || defined(__x86_64__)))) || (defined(_MSC_VER) && _MSC_VER>=1310)
544 #define SPIN_LOCKS_AVAILABLE 1
545 #else
546 #define SPIN_LOCKS_AVAILABLE 0
547 #endif
548
549 /* The maximum possible size_t value has all bits set */
550 #define MAX_SIZE_T (~(size_t)0)
551
552 #ifndef ONLY_MSPACES
553 #define ONLY_MSPACES 0 /* define to a value */
554 #else
555 #define ONLY_MSPACES 1
556 #endif /* ONLY_MSPACES */
557 #ifndef MSPACES
558 #if ONLY_MSPACES
559 #define MSPACES 1
560 #else /* ONLY_MSPACES */
561 #define MSPACES 0
562 #endif /* ONLY_MSPACES */
563 #endif /* MSPACES */
564 #ifndef MALLOC_ALIGNMENT
565 #define MALLOC_ALIGNMENT ((size_t)8U)
566 #endif /* MALLOC_ALIGNMENT */
567 #ifndef FOOTERS
568 #define FOOTERS 0
569 #endif /* FOOTERS */
570 #ifndef ABORT
571 #define ABORT abort()
572 #endif /* ABORT */
573 #ifndef ABORT_ON_ASSERT_FAILURE
574 #define ABORT_ON_ASSERT_FAILURE 1
575 #endif /* ABORT_ON_ASSERT_FAILURE */
576 #ifndef PROCEED_ON_ERROR
577 #define PROCEED_ON_ERROR 0
578 #endif /* PROCEED_ON_ERROR */
579 #ifndef USE_LOCKS
580 #define USE_LOCKS 0
581 #endif /* USE_LOCKS */
582 #ifndef USE_SPIN_LOCKS
583 #if USE_LOCKS && SPIN_LOCKS_AVAILABLE
584 #define USE_SPIN_LOCKS 1
585 #else
586 #define USE_SPIN_LOCKS 0
587 #endif /* USE_LOCKS && SPIN_LOCKS_AVAILABLE. */
588 #endif /* USE_SPIN_LOCKS */
589 #ifndef INSECURE
590 #define INSECURE 0
591 #endif /* INSECURE */
592 #ifndef HAVE_MMAP
593 #define HAVE_MMAP 1
594 #endif /* HAVE_MMAP */
595 #ifndef MMAP_CLEARS
596 #define MMAP_CLEARS 1
597 #endif /* MMAP_CLEARS */
598 #ifndef HAVE_MREMAP
599 #ifdef linux
600 #define HAVE_MREMAP 1
601 #else /* linux */
602 #define HAVE_MREMAP 0
603 #endif /* linux */
604 #endif /* HAVE_MREMAP */
605 #ifndef MALLOC_FAILURE_ACTION
606 #define MALLOC_FAILURE_ACTION errno = ENOMEM;
607 #endif /* MALLOC_FAILURE_ACTION */
608 #ifndef HAVE_MORECORE
609 #if ONLY_MSPACES
610 #define HAVE_MORECORE 0
611 #else /* ONLY_MSPACES */
612 #define HAVE_MORECORE 1
613 #endif /* ONLY_MSPACES */
614 #endif /* HAVE_MORECORE */
615 #if !HAVE_MORECORE
616 #define MORECORE_CONTIGUOUS 0
617 #else /* !HAVE_MORECORE */
618 #define MORECORE_DEFAULT sbrk
619 #ifndef MORECORE_CONTIGUOUS
620 #define MORECORE_CONTIGUOUS 1
621 #endif /* MORECORE_CONTIGUOUS */
622 #endif /* HAVE_MORECORE */
623 #ifndef DEFAULT_GRANULARITY
624 #if (MORECORE_CONTIGUOUS || defined(WIN32))
625 #define DEFAULT_GRANULARITY (0) /* 0 means to compute in init_mparams */
626 #else /* MORECORE_CONTIGUOUS */
627 #define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
628 #endif /* MORECORE_CONTIGUOUS */
629 #endif /* DEFAULT_GRANULARITY */
630 #ifndef DEFAULT_TRIM_THRESHOLD
631 #ifndef MORECORE_CANNOT_TRIM
632 #define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
633 #else /* MORECORE_CANNOT_TRIM */
634 #define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
635 #endif /* MORECORE_CANNOT_TRIM */
636 #endif /* DEFAULT_TRIM_THRESHOLD */
637 #ifndef DEFAULT_MMAP_THRESHOLD
638 #if HAVE_MMAP
639 #define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
640 #else /* HAVE_MMAP */
641 #define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
642 #endif /* HAVE_MMAP */
643 #endif /* DEFAULT_MMAP_THRESHOLD */
644 #ifndef MAX_RELEASE_CHECK_RATE
645 #if HAVE_MMAP
646 #define MAX_RELEASE_CHECK_RATE 4095
647 #else
648 #define MAX_RELEASE_CHECK_RATE MAX_SIZE_T
649 #endif /* HAVE_MMAP */
650 #endif /* MAX_RELEASE_CHECK_RATE */
651 #ifndef USE_BUILTIN_FFS
652 #define USE_BUILTIN_FFS 0
653 #endif /* USE_BUILTIN_FFS */
654 #ifndef USE_DEV_RANDOM
655 #define USE_DEV_RANDOM 0
656 #endif /* USE_DEV_RANDOM */
657 #ifndef NO_MALLINFO
658 #define NO_MALLINFO 0
659 #endif /* NO_MALLINFO */
660 #ifndef MALLINFO_FIELD_TYPE
661 #define MALLINFO_FIELD_TYPE size_t
662 #endif /* MALLINFO_FIELD_TYPE */
663 #ifndef NO_SEGMENT_TRAVERSAL
664 #define NO_SEGMENT_TRAVERSAL 0
665 #endif /* NO_SEGMENT_TRAVERSAL */
666
667 /*
668 mallopt tuning options. SVID/XPG defines four standard parameter
669 numbers for mallopt, normally defined in malloc.h. None of these
670 are used in this malloc, so setting them has no effect. But this
671 malloc does support the following options.
672 */
673
674 #define M_TRIM_THRESHOLD (-1)
675 #define M_GRANULARITY (-2)
676 #define M_MMAP_THRESHOLD (-3)
677
678 /* ------------------------ Mallinfo declarations ------------------------ */
679
680 #if !NO_MALLINFO
681 /*
682 This version of malloc supports the standard SVID/XPG mallinfo
683 routine that returns a struct containing usage properties and
684 statistics. It should work on any system that has a
685 /usr/include/malloc.h defining struct mallinfo. The main
686 declaration needed is the mallinfo struct that is returned (by-copy)
687 by mallinfo(). The malloinfo struct contains a bunch of fields that
688 are not even meaningful in this version of malloc. These fields are
689 are instead filled by mallinfo() with other numbers that might be of
690 interest.
691
692 HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
693 /usr/include/malloc.h file that includes a declaration of struct
694 mallinfo. If so, it is included; else a compliant version is
695 declared below. These must be precisely the same for mallinfo() to
696 work. The original SVID version of this struct, defined on most
697 systems with mallinfo, declares all fields as ints. But some others
698 define as unsigned long. If your system defines the fields using a
699 type of different width than listed here, you MUST #include your
700 system version and #define HAVE_USR_INCLUDE_MALLOC_H.
701 */
702
703 /* #define HAVE_USR_INCLUDE_MALLOC_H */
704
705 #ifdef HAVE_USR_INCLUDE_MALLOC_H
706 #include "/usr/include/malloc.h"
707 #else /* HAVE_USR_INCLUDE_MALLOC_H */
708 #ifndef STRUCT_MALLINFO_DECLARED
709 #define STRUCT_MALLINFO_DECLARED 1
710 struct mallinfo {
711 MALLINFO_FIELD_TYPE arena; /* non-mmapped space allocated from system */
712 MALLINFO_FIELD_TYPE ordblks; /* number of free chunks */
713 MALLINFO_FIELD_TYPE smblks; /* always 0 */
714 MALLINFO_FIELD_TYPE hblks; /* always 0 */
715 MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */
716 MALLINFO_FIELD_TYPE usmblks; /* maximum total allocated space */
717 MALLINFO_FIELD_TYPE fsmblks; /* always 0 */
718 MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
719 MALLINFO_FIELD_TYPE fordblks; /* total free space */
720 MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
721 };
722 #endif /* STRUCT_MALLINFO_DECLARED */
723 #endif /* HAVE_USR_INCLUDE_MALLOC_H */
724 #endif /* NO_MALLINFO */
725
726 /*
727 Try to persuade compilers to inline. The most critical functions for
728 inlining are defined as macros, so these aren't used for them.
729 */
730
731 #ifdef WIN64
732 #undef FORCEINLINE
733 #endif
734
735 #ifndef FORCEINLINE
736 #if defined(__GNUC__)
737 #define FORCEINLINE __inline __attribute__ ((always_inline))
738 #elif defined(_MSC_VER)
739 #define FORCEINLINE __forceinline
740 #endif
741 #endif
742 #ifndef NOINLINE
743 #if defined(__GNUC__)
744 #define NOINLINE __attribute__ ((noinline))
745 #elif defined(_MSC_VER)
746 #define NOINLINE __declspec(noinline)
747 #else
748 #define NOINLINE
749 #endif
750 #endif
751
752 #ifdef __cplusplus
753 extern "C" {
754 #ifndef FORCEINLINE
755 #define FORCEINLINE inline
756 #endif
757 #endif /* __cplusplus */
758 #ifndef FORCEINLINE
759 #define FORCEINLINE
760 #endif
761
762
763 #define USE_DL_PREFIX
764
765 #if !ONLY_MSPACES
766
767 /* ------------------- Declarations of public routines ------------------- */
768
769 #ifndef USE_DL_PREFIX
770 #define dlcalloc calloc
771 #define dlfree free
772 #define dlmalloc malloc
773 #define dlmemalign memalign
774 #define dlrealloc realloc
775 #define dlvalloc valloc
776 #define dlpvalloc pvalloc
777 #define dlmallinfo mallinfo
778 #define dlmallopt mallopt
779 #define dlmalloc_trim malloc_trim
780 #define dlmalloc_stats malloc_stats
781 #define dlmalloc_usable_size malloc_usable_size
782 #define dlmalloc_footprint malloc_footprint
783 #define dlmalloc_max_footprint malloc_max_footprint
784 #define dlindependent_calloc independent_calloc
785 #define dlindependent_comalloc independent_comalloc
786 #endif /* USE_DL_PREFIX */
787
788
789 /*
790 malloc(size_t n)
791 Returns a pointer to a newly allocated chunk of at least n bytes, or
792 null if no space is available, in which case errno is set to ENOMEM
793 on ANSI C systems.
794
795 If n is zero, malloc returns a minimum-sized chunk. (The minimum
796 size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
797 systems.) Note that size_t is an unsigned type, so calls with
798 arguments that would be negative if signed are interpreted as
799 requests for huge amounts of space, which will often fail. The
800 maximum supported value of n differs across systems, but is in all
801 cases less than the maximum representable value of a size_t.
802 */
803 void* dlmalloc(size_t);
804
805 /*
806 free(void* p)
807 Releases the chunk of memory pointed to by p, that had been previously
808 allocated using malloc or a related routine such as realloc.
809 It has no effect if p is null. If p was not malloced or already
810 freed, free(p) will by default cause the current program to abort.
811 */
812 void dlfree(void*);
813
814 /*
815 calloc(size_t n_elements, size_t element_size);
816 Returns a pointer to n_elements * element_size bytes, with all locations
817 set to zero.
818 */
819 void* dlcalloc(size_t, size_t);
820
821 /*
822 realloc(void* p, size_t n)
823 Returns a pointer to a chunk of size n that contains the same data
824 as does chunk p up to the minimum of (n, p's size) bytes, or null
825 if no space is available.
826
827 The returned pointer may or may not be the same as p. The algorithm
828 prefers extending p in most cases when possible, otherwise it
829 employs the equivalent of a malloc-copy-free sequence.
830
831 If p is null, realloc is equivalent to malloc.
832
833 If space is not available, realloc returns null, errno is set (if on
834 ANSI) and p is NOT freed.
835
836 if n is for fewer bytes than already held by p, the newly unused
837 space is lopped off and freed if possible. realloc with a size
838 argument of zero (re)allocates a minimum-sized chunk.
839
840 The old unix realloc convention of allowing the last-free'd chunk
841 to be used as an argument to realloc is not supported.
842 */
843
844 void* dlrealloc(void*, size_t);
845
846 /*
847 memalign(size_t alignment, size_t n);
848 Returns a pointer to a newly allocated chunk of n bytes, aligned
849 in accord with the alignment argument.
850
851 The alignment argument should be a power of two. If the argument is
852 not a power of two, the nearest greater power is used.
853 8-byte alignment is guaranteed by normal malloc calls, so don't
854 bother calling memalign with an argument of 8 or less.
855
856 Overreliance on memalign is a sure way to fragment space.
857 */
858 void* dlmemalign(size_t, size_t);
859
860 /*
861 valloc(size_t n);
862 Equivalent to memalign(pagesize, n), where pagesize is the page
863 size of the system. If the pagesize is unknown, 4096 is used.
864 */
865 void* dlvalloc(size_t);
866
867 /*
868 mallopt(int parameter_number, int parameter_value)
869 Sets tunable parameters The format is to provide a
870 (parameter-number, parameter-value) pair. mallopt then sets the
871 corresponding parameter to the argument value if it can (i.e., so
872 long as the value is meaningful), and returns 1 if successful else
873 0. To workaround the fact that mallopt is specified to use int,
874 not size_t parameters, the value -1 is specially treated as the
875 maximum unsigned size_t value.
876
877 SVID/XPG/ANSI defines four standard param numbers for mallopt,
878 normally defined in malloc.h. None of these are use in this malloc,
879 so setting them has no effect. But this malloc also supports other
880 options in mallopt. See below for details. Briefly, supported
881 parameters are as follows (listed defaults are for "typical"
882 configurations).
883
884 Symbol param # default allowed param values
885 M_TRIM_THRESHOLD -1 2*1024*1024 any (-1 disables)
886 M_GRANULARITY -2 page size any power of 2 >= page size
887 M_MMAP_THRESHOLD -3 256*1024 any (or 0 if no MMAP support)
888 */
889 int dlmallopt(int, int);
890
891 /*
892 malloc_footprint();
893 Returns the number of bytes obtained from the system. The total
894 number of bytes allocated by malloc, realloc etc., is less than this
895 value. Unlike mallinfo, this function returns only a precomputed
896 result, so can be called frequently to monitor memory consumption.
897 Even if locks are otherwise defined, this function does not use them,
898 so results might not be up to date.
899 */
900 size_t dlmalloc_footprint(void);
901
902 /*
903 malloc_max_footprint();
904 Returns the maximum number of bytes obtained from the system. This
905 value will be greater than current footprint if deallocated space
906 has been reclaimed by the system. The peak number of bytes allocated
907 by malloc, realloc etc., is less than this value. Unlike mallinfo,
908 this function returns only a precomputed result, so can be called
909 frequently to monitor memory consumption. Even if locks are
910 otherwise defined, this function does not use them, so results might
911 not be up to date.
912 */
913 size_t dlmalloc_max_footprint(void);
914
915 #if !NO_MALLINFO
916 /*
917 mallinfo()
918 Returns (by copy) a struct containing various summary statistics:
919
920 arena: current total non-mmapped bytes allocated from system
921 ordblks: the number of free chunks
922 smblks: always zero.
923 hblks: current number of mmapped regions
924 hblkhd: total bytes held in mmapped regions
925 usmblks: the maximum total allocated space. This will be greater
926 than current total if trimming has occurred.
927 fsmblks: always zero
928 uordblks: current total allocated space (normal or mmapped)
929 fordblks: total free space
930 keepcost: the maximum number of bytes that could ideally be released
931 back to system via malloc_trim. ("ideally" means that
932 it ignores page restrictions etc.)
933
934 Because these fields are ints, but internal bookkeeping may
935 be kept as longs, the reported values may wrap around zero and
936 thus be inaccurate.
937 */
938 struct mallinfo dlmallinfo(void);
939 #endif /* NO_MALLINFO */
940
941 /*
942 independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
943
944 independent_calloc is similar to calloc, but instead of returning a
945 single cleared space, it returns an array of pointers to n_elements
946 independent elements that can hold contents of size elem_size, each
947 of which starts out cleared, and can be independently freed,
948 realloc'ed etc. The elements are guaranteed to be adjacently
949 allocated (this is not guaranteed to occur with multiple callocs or
950 mallocs), which may also improve cache locality in some
951 applications.
952
953 The "chunks" argument is optional (i.e., may be null, which is
954 probably the most typical usage). If it is null, the returned array
955 is itself dynamically allocated and should also be freed when it is
956 no longer needed. Otherwise, the chunks array must be of at least
957 n_elements in length. It is filled in with the pointers to the
958 chunks.
959
960 In either case, independent_calloc returns this pointer array, or
961 null if the allocation failed. If n_elements is zero and "chunks"
962 is null, it returns a chunk representing an array with zero elements
963 (which should be freed if not wanted).
964
965 Each element must be individually freed when it is no longer
966 needed. If you'd like to instead be able to free all at once, you
967 should instead use regular calloc and assign pointers into this
968 space to represent elements. (In this case though, you cannot
969 independently free elements.)
970
971 independent_calloc simplifies and speeds up implementations of many
972 kinds of pools. It may also be useful when constructing large data
973 structures that initially have a fixed number of fixed-sized nodes,
974 but the number is not known at compile time, and some of the nodes
975 may later need to be freed. For example:
976
977 struct Node { int item; struct Node* next; };
978
979 struct Node* build_list() {
980 struct Node** pool;
981 int n = read_number_of_nodes_needed();
982 if (n <= 0) return 0;
983 pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
984 if (pool == 0) die();
985 // organize into a linked list...
986 struct Node* first = pool[0];
987 for (i = 0; i < n-1; ++i)
988 pool[i]->next = pool[i+1];
989 free(pool); // Can now free the array (or not, if it is needed later)
990 return first;
991 }
992 */
993 void** dlindependent_calloc(size_t, size_t, void**);
994
995 /*
996 independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
997
998 independent_comalloc allocates, all at once, a set of n_elements
999 chunks with sizes indicated in the "sizes" array. It returns
1000 an array of pointers to these elements, each of which can be
1001 independently freed, realloc'ed etc. The elements are guaranteed to
1002 be adjacently allocated (this is not guaranteed to occur with
1003 multiple callocs or mallocs), which may also improve cache locality
1004 in some applications.
1005
1006 The "chunks" argument is optional (i.e., may be null). If it is null
1007 the returned array is itself dynamically allocated and should also
1008 be freed when it is no longer needed. Otherwise, the chunks array
1009 must be of at least n_elements in length. It is filled in with the
1010 pointers to the chunks.
1011
1012 In either case, independent_comalloc returns this pointer array, or
1013 null if the allocation failed. If n_elements is zero and chunks is
1014 null, it returns a chunk representing an array with zero elements
1015 (which should be freed if not wanted).
1016
1017 Each element must be individually freed when it is no longer
1018 needed. If you'd like to instead be able to free all at once, you
1019 should instead use a single regular malloc, and assign pointers at
1020 particular offsets in the aggregate space. (In this case though, you
1021 cannot independently free elements.)
1022
1023 independent_comallac differs from independent_calloc in that each
1024 element may have a different size, and also that it does not
1025 automatically clear elements.
1026
1027 independent_comalloc can be used to speed up allocation in cases
1028 where several structs or objects must always be allocated at the
1029 same time. For example:
1030
1031 struct Head { ... }
1032 struct Foot { ... }
1033
1034 void send_message(char* msg) {
1035 int msglen = strlen(msg);
1036 size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1037 void* chunks[3];
1038 if (independent_comalloc(3, sizes, chunks) == 0)
1039 die();
1040 struct Head* head = (struct Head*)(chunks[0]);
1041 char* body = (char*)(chunks[1]);
1042 struct Foot* foot = (struct Foot*)(chunks[2]);
1043 // ...
1044 }
1045
1046 In general though, independent_comalloc is worth using only for
1047 larger values of n_elements. For small values, you probably won't
1048 detect enough difference from series of malloc calls to bother.
1049
1050 Overuse of independent_comalloc can increase overall memory usage,
1051 since it cannot reuse existing noncontiguous small chunks that
1052 might be available for some of the elements.
1053 */
1054 void** dlindependent_comalloc(size_t, size_t*, void**);
1055
1056
1057 /*
1058 pvalloc(size_t n);
1059 Equivalent to valloc(minimum-page-that-holds(n)), that is,
1060 round up n to nearest pagesize.
1061 */
1062 void* dlpvalloc(size_t);
1063
1064 /*
1065 malloc_trim(size_t pad);
1066
1067 If possible, gives memory back to the system (via negative arguments
1068 to sbrk) if there is unused memory at the `high' end of the malloc
1069 pool or in unused MMAP segments. You can call this after freeing
1070 large blocks of memory to potentially reduce the system-level memory
1071 requirements of a program. However, it cannot guarantee to reduce
1072 memory. Under some allocation patterns, some large free blocks of
1073 memory will be locked between two used chunks, so they cannot be
1074 given back to the system.
1075
1076 The `pad' argument to malloc_trim represents the amount of free
1077 trailing space to leave untrimmed. If this argument is zero, only
1078 the minimum amount of memory to maintain internal data structures
1079 will be left. Non-zero arguments can be supplied to maintain enough
1080 trailing space to service future expected allocations without having
1081 to re-obtain memory from the system.
1082
1083 Malloc_trim returns 1 if it actually released any memory, else 0.
1084 */
1085 int dlmalloc_trim(size_t);
1086
1087 /*
1088 malloc_stats();
1089 Prints on stderr the amount of space obtained from the system (both
1090 via sbrk and mmap), the maximum amount (which may be more than
1091 current if malloc_trim and/or munmap got called), and the current
1092 number of bytes allocated via malloc (or realloc, etc) but not yet
1093 freed. Note that this is the number of bytes allocated, not the
1094 number requested. It will be larger than the number requested
1095 because of alignment and bookkeeping overhead. Because it includes
1096 alignment wastage as being in use, this figure may be greater than
1097 zero even when no user-level chunks are allocated.
1098
1099 The reported current and maximum system memory can be inaccurate if
1100 a program makes other calls to system memory allocation functions
1101 (normally sbrk) outside of malloc.
1102
1103 malloc_stats prints only the most commonly interesting statistics.
1104 More information can be obtained by calling mallinfo.
1105 */
1106 void dlmalloc_stats(void);
1107
1108 #endif /* ONLY_MSPACES */
1109
1110 /*
1111 malloc_usable_size(void* p);
1112
1113 Returns the number of bytes you can actually use in
1114 an allocated chunk, which may be more than you requested (although
1115 often not) due to alignment and minimum size constraints.
1116 You can use this many bytes without worrying about
1117 overwriting other allocated objects. This is not a particularly great
1118 programming practice. malloc_usable_size can be more useful in
1119 debugging and assertions, for example:
1120
1121 p = malloc(n);
1122 assert(malloc_usable_size(p) >= 256);
1123 */
1124 size_t dlmalloc_usable_size(void*);
1125
1126
1127 #if MSPACES
1128
1129 /*
1130 mspace is an opaque type representing an independent
1131 region of space that supports mspace_malloc, etc.
1132 */
1133 typedef void* mspace;
1134
1135 /*
1136 create_mspace creates and returns a new independent space with the
1137 given initial capacity, or, if 0, the default granularity size. It
1138 returns null if there is no system memory available to create the
1139 space. If argument locked is non-zero, the space uses a separate
1140 lock to control access. The capacity of the space will grow
1141 dynamically as needed to service mspace_malloc requests. You can
1142 control the sizes of incremental increases of this space by
1143 compiling with a different DEFAULT_GRANULARITY or dynamically
1144 setting with mallopt(M_GRANULARITY, value).
1145 */
1146 mspace create_mspace(size_t capacity, int locked);
1147
1148 /*
1149 destroy_mspace destroys the given space, and attempts to return all
1150 of its memory back to the system, returning the total number of
1151 bytes freed. After destruction, the results of access to all memory
1152 used by the space become undefined.
1153 */
1154 size_t destroy_mspace(mspace msp);
1155
1156 /*
1157 create_mspace_with_base uses the memory supplied as the initial base
1158 of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
1159 space is used for bookkeeping, so the capacity must be at least this
1160 large. (Otherwise 0 is returned.) When this initial space is
1161 exhausted, additional memory will be obtained from the system.
1162 Destroying this space will deallocate all additionally allocated
1163 space (if possible) but not the initial base.
1164 */
1165 mspace create_mspace_with_base(void* base, size_t capacity, int locked);
1166
1167 /*
1168 mspace_track_large_chunks controls whether requests for large chunks
1169 are allocated in their own untracked mmapped regions, separate from
1170 others in this mspace. By default large chunks are not tracked,
1171 which reduces fragmentation. However, such chunks are not
1172 necessarily released to the system upon destroy_mspace. Enabling
1173 tracking by setting to true may increase fragmentation, but avoids
1174 leakage when relying on destroy_mspace to release all memory
1175 allocated using this space. The function returns the previous
1176 setting.
1177 */
1178 int mspace_track_large_chunks(mspace msp, int enable);
1179
1180
1181 /*
1182 mspace_malloc behaves as malloc, but operates within
1183 the given space.
1184 */
1185 void* mspace_malloc(mspace msp, size_t bytes);
1186
1187 /*
1188 mspace_free behaves as free, but operates within
1189 the given space.
1190
1191 If compiled with FOOTERS==1, mspace_free is not actually needed.
1192 free may be called instead of mspace_free because freed chunks from
1193 any space are handled by their originating spaces.
1194 */
1195 void mspace_free(mspace msp, void* mem);
1196
1197 /*
1198 mspace_realloc behaves as realloc, but operates within
1199 the given space.
1200
1201 If compiled with FOOTERS==1, mspace_realloc is not actually
1202 needed. realloc may be called instead of mspace_realloc because
1203 realloced chunks from any space are handled by their originating
1204 spaces.
1205 */
1206 void* mspace_realloc(mspace msp, void* mem, size_t newsize);
1207
1208 /*
1209 mspace_calloc behaves as calloc, but operates within
1210 the given space.
1211 */
1212 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
1213
1214 /*
1215 mspace_memalign behaves as memalign, but operates within
1216 the given space.
1217 */
1218 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);
1219
1220 /*
1221 mspace_independent_calloc behaves as independent_calloc, but
1222 operates within the given space.
1223 */
1224 void** mspace_independent_calloc(mspace msp, size_t n_elements,
1225 size_t elem_size, void* chunks[]);
1226
1227 /*
1228 mspace_independent_comalloc behaves as independent_comalloc, but
1229 operates within the given space.
1230 */
1231 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
1232 size_t sizes[], void* chunks[]);
1233
1234 /*
1235 mspace_footprint() returns the number of bytes obtained from the
1236 system for this space.
1237 */
1238 size_t mspace_footprint(mspace msp);
1239
1240 /*
1241 mspace_max_footprint() returns the peak number of bytes obtained from the
1242 system for this space.
1243 */
1244 size_t mspace_max_footprint(mspace msp);
1245
1246
1247 #if !NO_MALLINFO
1248 /*
1249 mspace_mallinfo behaves as mallinfo, but reports properties of
1250 the given space.
1251 */
1252 struct mallinfo mspace_mallinfo(mspace msp);
1253 #endif /* NO_MALLINFO */
1254
1255 /*
1256 malloc_usable_size(void* p) behaves the same as malloc_usable_size;
1257 */
1258 size_t mspace_usable_size(void* mem);
1259
1260 /*
1261 mspace_malloc_stats behaves as malloc_stats, but reports
1262 properties of the given space.
1263 */
1264 void mspace_malloc_stats(mspace msp);
1265
1266 /*
1267 mspace_trim behaves as malloc_trim, but
1268 operates within the given space.
1269 */
1270 int mspace_trim(mspace msp, size_t pad);
1271
1272 /*
1273 An alias for mallopt.
1274 */
1275 int mspace_mallopt(int, int);
1276
1277 #endif /* MSPACES */
1278
1279 #ifdef __cplusplus
1280 }; /* end of extern "C" */
1281 #endif /* __cplusplus */
1282
1283 /*
1284 ========================================================================
1285 To make a fully customizable malloc.h header file, cut everything
1286 above this line, put into file malloc.h, edit to suit, and #include it
1287 on the next line, as well as in programs that use this malloc.
1288 ========================================================================
1289 */
1290
1291 /* #include "malloc.h" */
1292
1293 /*------------------------------ internal #includes ---------------------- */
1294
1295 #ifdef WIN32
1296 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
1297 #endif /* WIN32 */
1298
1299 #include <stdio.h> /* for printing in malloc_stats */
1300
1301 #ifndef LACKS_ERRNO_H
1302 #include <errno.h> /* for MALLOC_FAILURE_ACTION */
1303 #endif /* LACKS_ERRNO_H */
1304
1305 #include <time.h> /* for magic initialization */
1306
1307 #ifndef LACKS_STDLIB_H
1308 #include <stdlib.h> /* for abort() */
1309 #endif /* LACKS_STDLIB_H */
1310 #ifdef DEBUG
1311 #if ABORT_ON_ASSERT_FAILURE
1312 #undef assert
1313 #define assert(x) if(!(x)) ABORT
1314 #else /* ABORT_ON_ASSERT_FAILURE */
1315 #include <assert.h>
1316 #endif /* ABORT_ON_ASSERT_FAILURE */
1317 #else /* DEBUG */
1318 #ifndef assert
1319 #define assert(x)
1320 #endif
1321 #define DEBUG 0
1322 #endif /* DEBUG */
1323 #ifndef LACKS_STRING_H
1324 #include <string.h> /* for memset etc */
1325 #endif /* LACKS_STRING_H */
1326 #if USE_BUILTIN_FFS
1327 #ifndef LACKS_STRINGS_H
1328 #include <strings.h> /* for ffs */
1329 #endif /* LACKS_STRINGS_H */
1330 #endif /* USE_BUILTIN_FFS */
1331 #if HAVE_MMAP
1332 #ifndef LACKS_SYS_MMAN_H
1333 /* On some versions of linux, mremap decl in mman.h needs __USE_GNU set */
1334 #if (defined(linux) && !defined(__USE_GNU))
1335 #define __USE_GNU 1
1336 #include <sys/mman.h> /* for mmap */
1337 #undef __USE_GNU
1338 #else
1339 #include <sys/mman.h> /* for mmap */
1340 #endif /* linux */
1341 #endif /* LACKS_SYS_MMAN_H */
1342 #ifndef LACKS_FCNTL_H
1343 #include <fcntl.h>
1344 #endif /* LACKS_FCNTL_H */
1345 #endif /* HAVE_MMAP */
1346 #ifndef LACKS_UNISTD_H
1347 #include <unistd.h> /* for sbrk, sysconf */
1348 #else /* LACKS_UNISTD_H */
1349 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
1350 //extern "C" { void* sbrk(ptrdiff_t); };
1351 #endif /* FreeBSD etc */
1352 #endif /* LACKS_UNISTD_H */
1353
1354 /* Declarations for locking */
1355 #if USE_LOCKS
1356 #ifndef WIN32
1357 #include <pthread.h>
1358 #if defined (__SVR4) && defined (__sun) /* solaris */
1359 #include <thread.h>
1360 #endif /* solaris */
1361 #else
1362 #ifndef _M_AMD64
1363 /* These are already defined on AMD64 builds */
1364 #ifdef __cplusplus
1365 extern "C" {
1366 #endif /* __cplusplus */
1367 LONG __cdecl _InterlockedCompareExchange(LONG volatile *Dest, LONG Exchange, LONG Comp);
1368 LONG __cdecl _InterlockedExchange(LONG volatile *Target, LONG Value);
1369 #ifdef __cplusplus
1370 }
1371 #endif /* __cplusplus */
1372 #endif /* _M_AMD64 */
1373 #pragma intrinsic (_InterlockedCompareExchange)
1374 #pragma intrinsic (_InterlockedExchange)
1375 #define interlockedcompareexchange _InterlockedCompareExchange
1376 #define interlockedexchange _InterlockedExchange
1377 #endif /* Win32 */
1378 #endif /* USE_LOCKS */
1379
1380 /* Declarations for bit scanning on win32 */
1381 #if defined(_MSC_VER) && _MSC_VER>=1300
1382 #ifndef BitScanForward /* Try to avoid pulling in WinNT.h */
1383 #ifdef __cplusplus
1384 extern "C" {
1385 #endif /* __cplusplus */
1386 unsigned char _BitScanForward(unsigned long *index, unsigned long mask);
1387 unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
1388 #ifdef __cplusplus
1389 }
1390 #endif /* __cplusplus */
1391
1392 #define BitScanForward _BitScanForward
1393 #define BitScanReverse _BitScanReverse
1394 #pragma intrinsic(_BitScanForward)
1395 #pragma intrinsic(_BitScanReverse)
1396 #endif /* BitScanForward */
1397 #endif /* defined(_MSC_VER) && _MSC_VER>=1300 */
1398
1399 #ifndef WIN32
1400 #ifndef malloc_getpagesize
1401 # ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
1402 # ifndef _SC_PAGE_SIZE
1403 # define _SC_PAGE_SIZE _SC_PAGESIZE
1404 # endif
1405 # endif
1406 # ifdef _SC_PAGE_SIZE
1407 # define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
1408 # else
1409 # if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
1410 extern size_t getpagesize();
1411 # define malloc_getpagesize getpagesize()
1412 # else
1413 # ifdef WIN32 /* use supplied emulation of getpagesize */
1414 # define malloc_getpagesize getpagesize()
1415 # else
1416 # ifndef LACKS_SYS_PARAM_H
1417 # include <sys/param.h>
1418 # endif
1419 # ifdef EXEC_PAGESIZE
1420 # define malloc_getpagesize EXEC_PAGESIZE
1421 # else
1422 # ifdef NBPG
1423 # ifndef CLSIZE
1424 # define malloc_getpagesize NBPG
1425 # else
1426 # define malloc_getpagesize (NBPG * CLSIZE)
1427 # endif
1428 # else
1429 # ifdef NBPC
1430 # define malloc_getpagesize NBPC
1431 # else
1432 # ifdef PAGESIZE
1433 # define malloc_getpagesize PAGESIZE
1434 # else /* just guess */
1435 # define malloc_getpagesize ((size_t)4096U)
1436 # endif
1437 # endif
1438 # endif
1439 # endif
1440 # endif
1441 # endif
1442 # endif
1443 #endif
1444 #endif
1445
1446
1447
1448 /* ------------------- size_t and alignment properties -------------------- */
1449
1450 /* The byte and bit size of a size_t */
1451 #define SIZE_T_SIZE (sizeof(size_t))
1452 #define SIZE_T_BITSIZE (sizeof(size_t) << 3)
1453
1454 /* Some constants coerced to size_t */
1455 /* Annoying but necessary to avoid errors on some platforms */
1456 #define SIZE_T_ZERO ((size_t)0)
1457 #define SIZE_T_ONE ((size_t)1)
1458 #define SIZE_T_TWO ((size_t)2)
1459 #define SIZE_T_FOUR ((size_t)4)
1460 #define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)
1461 #define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)
1462 #define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
1463 #define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
1464
1465 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
1466 #define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)
1467
1468 /* True if address a has acceptable alignment */
1469 #define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
1470
1471 /* the number of bytes to offset an address to align it */
1472 #define align_offset(A)\
1473 ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
1474 ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
1475
1476 /* -------------------------- MMAP preliminaries ------------------------- */
1477
1478 /*
1479 If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
1480 checks to fail so compiler optimizer can delete code rather than
1481 using so many "#if"s.
1482 */
1483
1484
1485 /* MORECORE and MMAP must return MFAIL on failure */
1486 #define MFAIL ((void*)(MAX_SIZE_T))
1487 #define CMFAIL ((char*)(MFAIL)) /* defined for convenience */
1488
1489 #if HAVE_MMAP
1490
1491 #ifndef WIN32
1492 #define MUNMAP_DEFAULT(a, s) munmap((a), (s))
1493 #define MMAP_PROT (PROT_READ|PROT_WRITE)
1494 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1495 #define MAP_ANONYMOUS MAP_ANON
1496 #endif /* MAP_ANON */
1497 #ifdef MAP_ANONYMOUS
1498 #define MMAP_FLAGS (MAP_PRIVATE|MAP_ANONYMOUS)
1499 #define MMAP_DEFAULT(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
1500 #else /* MAP_ANONYMOUS */
1501 /*
1502 Nearly all versions of mmap support MAP_ANONYMOUS, so the following
1503 is unlikely to be needed, but is supplied just in case.
1504 */
1505 #define MMAP_FLAGS (MAP_PRIVATE)
1506 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1507 #define MMAP_DEFAULT(s) ((dev_zero_fd < 0) ? \
1508 (dev_zero_fd = open("/dev/zero", O_RDWR), \
1509 mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
1510 mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
1511 #endif /* MAP_ANONYMOUS */
1512
1513 #define DIRECT_MMAP_DEFAULT(s) MMAP_DEFAULT(s)
1514
1515 #else /* WIN32 */
1516
1517 /* Win32 MMAP via VirtualAlloc */
win32mmap(size_t size)1518 static FORCEINLINE void* win32mmap(size_t size) {
1519 void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
1520 return (ptr != 0)? ptr: MFAIL;
1521 }
1522
1523 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
win32direct_mmap(size_t size)1524 static FORCEINLINE void* win32direct_mmap(size_t size) {
1525 void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
1526 PAGE_READWRITE);
1527 return (ptr != 0)? ptr: MFAIL;
1528 }
1529
1530 /* This function supports releasing coalesed segments */
win32munmap(void * ptr,size_t size)1531 static FORCEINLINE int win32munmap(void* ptr, size_t size) {
1532 MEMORY_BASIC_INFORMATION minfo;
1533 char* cptr = (char*)ptr;
1534 while (size) {
1535 if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
1536 return -1;
1537 if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
1538 minfo.State != MEM_COMMIT || minfo.RegionSize > size)
1539 return -1;
1540 if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
1541 return -1;
1542 cptr += minfo.RegionSize;
1543 size -= minfo.RegionSize;
1544 }
1545 return 0;
1546 }
1547
1548 #define MMAP_DEFAULT(s) win32mmap(s)
1549 #define MUNMAP_DEFAULT(a, s) win32munmap((a), (s))
1550 #define DIRECT_MMAP_DEFAULT(s) win32direct_mmap(s)
1551 #endif /* WIN32 */
1552 #endif /* HAVE_MMAP */
1553
1554 #if HAVE_MREMAP
1555 #ifndef WIN32
1556 #define MREMAP_DEFAULT(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
1557 #endif /* WIN32 */
1558 #endif /* HAVE_MREMAP */
1559
1560
1561 /**
1562 * Define CALL_MORECORE
1563 */
1564 #if HAVE_MORECORE
1565 #ifdef MORECORE
1566 #define CALL_MORECORE(S) MORECORE(S)
1567 #else /* MORECORE */
1568 #define CALL_MORECORE(S) MORECORE_DEFAULT(S)
1569 #endif /* MORECORE */
1570 #else /* HAVE_MORECORE */
1571 #define CALL_MORECORE(S) MFAIL
1572 #endif /* HAVE_MORECORE */
1573
1574 /**
1575 * Define CALL_MMAP/CALL_MUNMAP/CALL_DIRECT_MMAP
1576 */
1577 #if HAVE_MMAP
1578 #define USE_MMAP_BIT (SIZE_T_ONE)
1579
1580 #ifdef MMAP
1581 #define CALL_MMAP(s) MMAP(s)
1582 #else /* MMAP */
1583 #define CALL_MMAP(s) MMAP_DEFAULT(s)
1584 #endif /* MMAP */
1585 #ifdef MUNMAP
1586 #define CALL_MUNMAP(a, s) MUNMAP((a), (s))
1587 #else /* MUNMAP */
1588 #define CALL_MUNMAP(a, s) MUNMAP_DEFAULT((a), (s))
1589 #endif /* MUNMAP */
1590 #ifdef DIRECT_MMAP
1591 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
1592 #else /* DIRECT_MMAP */
1593 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP_DEFAULT(s)
1594 #endif /* DIRECT_MMAP */
1595 #else /* HAVE_MMAP */
1596 #define USE_MMAP_BIT (SIZE_T_ZERO)
1597
1598 #define MMAP(s) MFAIL
1599 #define MUNMAP(a, s) (-1)
1600 #define DIRECT_MMAP(s) MFAIL
1601 #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
1602 #define CALL_MMAP(s) MMAP(s)
1603 #define CALL_MUNMAP(a, s) MUNMAP((a), (s))
1604 #endif /* HAVE_MMAP */
1605
1606 /**
1607 * Define CALL_MREMAP
1608 */
1609 #if HAVE_MMAP && HAVE_MREMAP
1610 #ifdef MREMAP
1611 #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP((addr), (osz), (nsz), (mv))
1612 #else /* MREMAP */
1613 #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP_DEFAULT((addr), (osz), (nsz), (mv))
1614 #endif /* MREMAP */
1615 #else /* HAVE_MMAP && HAVE_MREMAP */
1616 #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
1617 #endif /* HAVE_MMAP && HAVE_MREMAP */
1618
1619 /* mstate bit set if continguous morecore disabled or failed */
1620 #define USE_NONCONTIGUOUS_BIT (4U)
1621
1622 /* segment bit set in create_mspace_with_base */
1623 #define EXTERN_BIT (8U)
1624
1625
1626 /* --------------------------- Lock preliminaries ------------------------ */
1627
1628 /*
1629 When locks are defined, there is one global lock, plus
1630 one per-mspace lock.
1631
1632 The global lock_ensures that mparams.magic and other unique
1633 mparams values are initialized only once. It also protects
1634 sequences of calls to MORECORE. In many cases sys_alloc requires
1635 two calls, that should not be interleaved with calls by other
1636 threads. This does not protect against direct calls to MORECORE
1637 by other threads not using this lock, so there is still code to
1638 cope the best we can on interference.
1639
1640 Per-mspace locks surround calls to malloc, free, etc. To enable use
1641 in layered extensions, per-mspace locks are reentrant.
1642
1643 Because lock-protected regions generally have bounded times, it is
1644 OK to use the supplied simple spinlocks in the custom versions for
1645 x86. Spinlocks are likely to improve performance for lightly
1646 contended applications, but worsen performance under heavy
1647 contention.
1648
1649 If USE_LOCKS is > 1, the definitions of lock routines here are
1650 bypassed, in which case you will need to define the type MLOCK_T,
1651 and at least INITIAL_LOCK, ACQUIRE_LOCK, RELEASE_LOCK and possibly
1652 TRY_LOCK (which is not used in this malloc, but commonly needed in
1653 extensions.) You must also declare a
1654 static MLOCK_T malloc_global_mutex = { initialization values };.
1655
1656 */
1657
1658 #if USE_LOCKS == 1
1659
1660 #if USE_SPIN_LOCKS && SPIN_LOCKS_AVAILABLE
1661 #ifndef WIN32
1662
1663 /* Custom pthread-style spin locks on x86 and x64 for gcc */
1664 struct pthread_mlock_t {
1665 volatile unsigned int l;
1666 unsigned int c;
1667 pthread_t threadid;
1668 };
1669 #define MLOCK_T struct pthread_mlock_t
1670 #define CURRENT_THREAD pthread_self()
1671 #define INITIAL_LOCK(sl) ((sl)->threadid = 0, (sl)->l = (sl)->c = 0, 0)
1672 #define ACQUIRE_LOCK(sl) pthread_acquire_lock(sl)
1673 #define RELEASE_LOCK(sl) pthread_release_lock(sl)
1674 #define TRY_LOCK(sl) pthread_try_lock(sl)
1675 #define SPINS_PER_YIELD 63
1676
1677 static MLOCK_T malloc_global_mutex = { 0, 0, 0};
1678
pthread_acquire_lock(MLOCK_T * sl)1679 static FORCEINLINE int pthread_acquire_lock (MLOCK_T *sl) {
1680 int spins = 0;
1681 volatile unsigned int* lp = &sl->l;
1682 for (;;) {
1683 if (*lp != 0) {
1684 if (sl->threadid == CURRENT_THREAD) {
1685 ++sl->c;
1686 return 0;
1687 }
1688 }
1689 else {
1690 /* place args to cmpxchgl in locals to evade oddities in some gccs */
1691 int cmp = 0;
1692 int val = 1;
1693 int ret;
1694 __asm__ __volatile__ ("lock; cmpxchgl %1, %2"
1695 : "=a" (ret)
1696 : "r" (val), "m" (*(lp)), "0"(cmp)
1697 : "memory", "cc");
1698 if (!ret) {
1699 assert(!sl->threadid);
1700 sl->threadid = CURRENT_THREAD;
1701 sl->c = 1;
1702 return 0;
1703 }
1704 }
1705 if ((++spins & SPINS_PER_YIELD) == 0) {
1706 #if defined (__SVR4) && defined (__sun) /* solaris */
1707 thr_yield();
1708 #else
1709 #if defined(__linux__) || defined(__FreeBSD__) || defined(__APPLE__) || defined(__DragonFly__)
1710 sched_yield();
1711 #else /* no-op yield on unknown systems */
1712 ;
1713 #endif /* __linux__ || __FreeBSD__ || __APPLE__ */
1714 #endif /* solaris */
1715 }
1716 }
1717 }
1718
pthread_release_lock(MLOCK_T * sl)1719 static FORCEINLINE void pthread_release_lock (MLOCK_T *sl) {
1720 volatile unsigned int* lp = &sl->l;
1721 assert(*lp != 0);
1722 assert(sl->threadid == CURRENT_THREAD);
1723 if (--sl->c == 0) {
1724 sl->threadid = 0;
1725 int prev = 0;
1726 int ret;
1727 __asm__ __volatile__ ("lock; xchgl %0, %1"
1728 : "=r" (ret)
1729 : "m" (*(lp)), "0"(prev)
1730 : "memory");
1731 }
1732 }
1733
pthread_try_lock(MLOCK_T * sl)1734 static FORCEINLINE int pthread_try_lock (MLOCK_T *sl) {
1735 volatile unsigned int* lp = &sl->l;
1736 if (*lp != 0) {
1737 if (sl->threadid == CURRENT_THREAD) {
1738 ++sl->c;
1739 return 1;
1740 }
1741 }
1742 else {
1743 int cmp = 0;
1744 int val = 1;
1745 int ret;
1746 __asm__ __volatile__ ("lock; cmpxchgl %1, %2"
1747 : "=a" (ret)
1748 : "r" (val), "m" (*(lp)), "0"(cmp)
1749 : "memory", "cc");
1750 if (!ret) {
1751 assert(!sl->threadid);
1752 sl->threadid = CURRENT_THREAD;
1753 sl->c = 1;
1754 return 1;
1755 }
1756 }
1757 return 0;
1758 }
1759
1760
1761 #else /* WIN32 */
1762 /* Custom win32-style spin locks on x86 and x64 for MSC */
1763 struct win32_mlock_t {
1764 volatile long l;
1765 unsigned int c;
1766 long threadid;
1767 };
1768
1769 #define MLOCK_T struct win32_mlock_t
1770 #define CURRENT_THREAD GetCurrentThreadId()
1771 #define INITIAL_LOCK(sl) ((sl)->threadid = 0, (sl)->l = (sl)->c = 0, 0)
1772 #define ACQUIRE_LOCK(sl) win32_acquire_lock(sl)
1773 #define RELEASE_LOCK(sl) win32_release_lock(sl)
1774 #define TRY_LOCK(sl) win32_try_lock(sl)
1775 #define SPINS_PER_YIELD 63
1776
1777 static MLOCK_T malloc_global_mutex = { 0, 0, 0};
1778
win32_acquire_lock(MLOCK_T * sl)1779 static FORCEINLINE int win32_acquire_lock (MLOCK_T *sl) {
1780 int spins = 0;
1781 for (;;) {
1782 if (sl->l != 0) {
1783 if (sl->threadid == CURRENT_THREAD) {
1784 ++sl->c;
1785 return 0;
1786 }
1787 }
1788 else {
1789 if (!interlockedexchange(&sl->l, 1)) {
1790 assert(!sl->threadid);
1791 sl->threadid = CURRENT_THREAD;
1792 sl->c = 1;
1793 return 0;
1794 }
1795 }
1796 if ((++spins & SPINS_PER_YIELD) == 0)
1797 SleepEx(0, FALSE);
1798 }
1799 }
1800
win32_release_lock(MLOCK_T * sl)1801 static FORCEINLINE void win32_release_lock (MLOCK_T *sl) {
1802 assert(sl->threadid == CURRENT_THREAD);
1803 assert(sl->l != 0);
1804 if (--sl->c == 0) {
1805 sl->threadid = 0;
1806 interlockedexchange (&sl->l, 0);
1807 }
1808 }
1809
win32_try_lock(MLOCK_T * sl)1810 static FORCEINLINE int win32_try_lock (MLOCK_T *sl) {
1811 if (sl->l != 0) {
1812 if (sl->threadid == CURRENT_THREAD) {
1813 ++sl->c;
1814 return 1;
1815 }
1816 }
1817 else {
1818 if (!interlockedexchange(&sl->l, 1)) {
1819 assert(!sl->threadid);
1820 sl->threadid = CURRENT_THREAD;
1821 sl->c = 1;
1822 return 1;
1823 }
1824 }
1825 return 0;
1826 }
1827
1828 #endif /* WIN32 */
1829 #else /* USE_SPIN_LOCKS */
1830
1831 #ifndef WIN32
1832 /* pthreads-based locks */
1833
1834 #define MLOCK_T pthread_mutex_t
1835 #define CURRENT_THREAD pthread_self()
1836 #define INITIAL_LOCK(sl) pthread_init_lock(sl)
1837 #define ACQUIRE_LOCK(sl) pthread_mutex_lock(sl)
1838 #define RELEASE_LOCK(sl) pthread_mutex_unlock(sl)
1839 #define TRY_LOCK(sl) (!pthread_mutex_trylock(sl))
1840
1841 static MLOCK_T malloc_global_mutex = PTHREAD_MUTEX_INITIALIZER;
1842
1843 /* Cope with old-style linux recursive lock initialization by adding */
1844 /* skipped internal declaration from pthread.h */
1845 #ifdef linux
1846 #ifndef PTHREAD_MUTEX_RECURSIVE
1847 extern int pthread_mutexattr_setkind_np __P ((pthread_mutexattr_t *__attr,
1848 int __kind));
1849 #define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP
1850 #define pthread_mutexattr_settype(x,y) pthread_mutexattr_setkind_np(x,y)
1851 #endif
1852 #endif
1853
pthread_init_lock(MLOCK_T * sl)1854 static int pthread_init_lock (MLOCK_T *sl) {
1855 pthread_mutexattr_t attr;
1856 if (pthread_mutexattr_init(&attr)) return 1;
1857 if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1;
1858 if (pthread_mutex_init(sl, &attr)) return 1;
1859 if (pthread_mutexattr_destroy(&attr)) return 1;
1860 return 0;
1861 }
1862
1863 #else /* WIN32 */
1864 /* Win32 critical sections */
1865 #define MLOCK_T CRITICAL_SECTION
1866 #define CURRENT_THREAD GetCurrentThreadId()
1867 #define INITIAL_LOCK(s) (!InitializeCriticalSectionAndSpinCount((s), 0x80000000|4000))
1868 #define ACQUIRE_LOCK(s) (EnterCriticalSection(sl), 0)
1869 #define RELEASE_LOCK(s) LeaveCriticalSection(sl)
1870 #define TRY_LOCK(s) TryEnterCriticalSection(sl)
1871 #define NEED_GLOBAL_LOCK_INIT
1872
1873 static MLOCK_T malloc_global_mutex;
1874 static volatile long malloc_global_mutex_status;
1875
1876 /* Use spin loop to initialize global lock */
init_malloc_global_mutex()1877 static void init_malloc_global_mutex() {
1878 for (;;) {
1879 long stat = malloc_global_mutex_status;
1880 if (stat > 0)
1881 return;
1882 /* transition to < 0 while initializing, then to > 0) */
1883 if (stat == 0 &&
1884 interlockedcompareexchange(&malloc_global_mutex_status, -1, 0) == 0) {
1885 InitializeCriticalSection(&malloc_global_mutex);
1886 interlockedexchange(&malloc_global_mutex_status,1);
1887 return;
1888 }
1889 SleepEx(0, FALSE);
1890 }
1891 }
1892
1893 #endif /* WIN32 */
1894 #endif /* USE_SPIN_LOCKS */
1895 #endif /* USE_LOCKS == 1 */
1896
1897 /* ----------------------- User-defined locks ------------------------ */
1898
1899 #if USE_LOCKS > 1
1900 /* Define your own lock implementation here */
1901 /* #define INITIAL_LOCK(sl) ... */
1902 /* #define ACQUIRE_LOCK(sl) ... */
1903 /* #define RELEASE_LOCK(sl) ... */
1904 /* #define TRY_LOCK(sl) ... */
1905 /* static MLOCK_T malloc_global_mutex = ... */
1906 #endif /* USE_LOCKS > 1 */
1907
1908 /* ----------------------- Lock-based state ------------------------ */
1909
1910 #if USE_LOCKS
1911 #define USE_LOCK_BIT (2U)
1912 #else /* USE_LOCKS */
1913 #define USE_LOCK_BIT (0U)
1914 #define INITIAL_LOCK(l)
1915 #endif /* USE_LOCKS */
1916
1917 #if USE_LOCKS
1918 #ifndef ACQUIRE_MALLOC_GLOBAL_LOCK
1919 #define ACQUIRE_MALLOC_GLOBAL_LOCK() ACQUIRE_LOCK(&malloc_global_mutex);
1920 #endif
1921 #ifndef RELEASE_MALLOC_GLOBAL_LOCK
1922 #define RELEASE_MALLOC_GLOBAL_LOCK() RELEASE_LOCK(&malloc_global_mutex);
1923 #endif
1924 #else /* USE_LOCKS */
1925 #define ACQUIRE_MALLOC_GLOBAL_LOCK()
1926 #define RELEASE_MALLOC_GLOBAL_LOCK()
1927 #endif /* USE_LOCKS */
1928
1929
1930 /* ----------------------- Chunk representations ------------------------ */
1931
1932 /*
1933 (The following includes lightly edited explanations by Colin Plumb.)
1934
1935 The malloc_chunk declaration below is misleading (but accurate and
1936 necessary). It declares a "view" into memory allowing access to
1937 necessary fields at known offsets from a given base.
1938
1939 Chunks of memory are maintained using a `boundary tag' method as
1940 originally described by Knuth. (See the paper by Paul Wilson
1941 ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
1942 techniques.) Sizes of free chunks are stored both in the front of
1943 each chunk and at the end. This makes consolidating fragmented
1944 chunks into bigger chunks fast. The head fields also hold bits
1945 representing whether chunks are free or in use.
1946
1947 Here are some pictures to make it clearer. They are "exploded" to
1948 show that the state of a chunk can be thought of as extending from
1949 the high 31 bits of the head field of its header through the
1950 prev_foot and PINUSE_BIT bit of the following chunk header.
1951
1952 A chunk that's in use looks like:
1953
1954 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1955 | Size of previous chunk (if P = 0) |
1956 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1957 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1958 | Size of this chunk 1| +-+
1959 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1960 | |
1961 +- -+
1962 | |
1963 +- -+
1964 | :
1965 +- size - sizeof(size_t) available payload bytes -+
1966 : |
1967 chunk-> +- -+
1968 | |
1969 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1970 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
1971 | Size of next chunk (may or may not be in use) | +-+
1972 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1973
1974 And if it's free, it looks like this:
1975
1976 chunk-> +- -+
1977 | User payload (must be in use, or we would have merged!) |
1978 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1979 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1980 | Size of this chunk 0| +-+
1981 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1982 | Next pointer |
1983 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1984 | Prev pointer |
1985 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1986 | :
1987 +- size - sizeof(struct chunk) unused bytes -+
1988 : |
1989 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1990 | Size of this chunk |
1991 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1992 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
1993 | Size of next chunk (must be in use, or we would have merged)| +-+
1994 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1995 | :
1996 +- User payload -+
1997 : |
1998 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1999 |0|
2000 +-+
2001 Note that since we always merge adjacent free chunks, the chunks
2002 adjacent to a free chunk must be in use.
2003
2004 Given a pointer to a chunk (which can be derived trivially from the
2005 payload pointer) we can, in O(1) time, find out whether the adjacent
2006 chunks are free, and if so, unlink them from the lists that they
2007 are on and merge them with the current chunk.
2008
2009 Chunks always begin on even word boundaries, so the mem portion
2010 (which is returned to the user) is also on an even word boundary, and
2011 thus at least double-word aligned.
2012
2013 The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
2014 chunk size (which is always a multiple of two words), is an in-use
2015 bit for the *previous* chunk. If that bit is *clear*, then the
2016 word before the current chunk size contains the previous chunk
2017 size, and can be used to find the front of the previous chunk.
2018 The very first chunk allocated always has this bit set, preventing
2019 access to non-existent (or non-owned) memory. If pinuse is set for
2020 any given chunk, then you CANNOT determine the size of the
2021 previous chunk, and might even get a memory addressing fault when
2022 trying to do so.
2023
2024 The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
2025 the chunk size redundantly records whether the current chunk is
2026 inuse (unless the chunk is mmapped). This redundancy enables usage
2027 checks within free and realloc, and reduces indirection when freeing
2028 and consolidating chunks.
2029
2030 Each freshly allocated chunk must have both cinuse and pinuse set.
2031 That is, each allocated chunk borders either a previously allocated
2032 and still in-use chunk, or the base of its memory arena. This is
2033 ensured by making all allocations from the the `lowest' part of any
2034 found chunk. Further, no free chunk physically borders another one,
2035 so each free chunk is known to be preceded and followed by either
2036 inuse chunks or the ends of memory.
2037
2038 Note that the `foot' of the current chunk is actually represented
2039 as the prev_foot of the NEXT chunk. This makes it easier to
2040 deal with alignments etc but can be very confusing when trying
2041 to extend or adapt this code.
2042
2043 The exceptions to all this are
2044
2045 1. The special chunk `top' is the top-most available chunk (i.e.,
2046 the one bordering the end of available memory). It is treated
2047 specially. Top is never included in any bin, is used only if
2048 no other chunk is available, and is released back to the
2049 system if it is very large (see M_TRIM_THRESHOLD). In effect,
2050 the top chunk is treated as larger (and thus less well
2051 fitting) than any other available chunk. The top chunk
2052 doesn't update its trailing size field since there is no next
2053 contiguous chunk that would have to index off it. However,
2054 space is still allocated for it (TOP_FOOT_SIZE) to enable
2055 separation or merging when space is extended.
2056
2057 3. Chunks allocated via mmap, have both cinuse and pinuse bits
2058 cleared in their head fields. Because they are allocated
2059 one-by-one, each must carry its own prev_foot field, which is
2060 also used to hold the offset this chunk has within its mmapped
2061 region, which is needed to preserve alignment. Each mmapped
2062 chunk is trailed by the first two fields of a fake next-chunk
2063 for sake of usage checks.
2064
2065 */
2066
2067 struct malloc_chunk {
2068 size_t prev_foot; /* Size of previous chunk (if free). */
2069 size_t head; /* Size and inuse bits. */
2070 struct malloc_chunk* fd; /* double links -- used only if free. */
2071 struct malloc_chunk* bk;
2072 };
2073
2074 typedef struct malloc_chunk mchunk;
2075 typedef struct malloc_chunk* mchunkptr;
2076 typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */
2077 typedef unsigned int bindex_t; /* Described below */
2078 typedef unsigned int binmap_t; /* Described below */
2079 typedef unsigned int flag_t; /* The type of various bit flag sets */
2080
2081 /* ------------------- Chunks sizes and alignments ----------------------- */
2082
2083 #define MCHUNK_SIZE (sizeof(mchunk))
2084
2085 #if FOOTERS
2086 #define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
2087 #else /* FOOTERS */
2088 #define CHUNK_OVERHEAD (SIZE_T_SIZE)
2089 #endif /* FOOTERS */
2090
2091 /* MMapped chunks need a second word of overhead ... */
2092 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
2093 /* ... and additional padding for fake next-chunk at foot */
2094 #define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES)
2095
2096 /* The smallest size we can malloc is an aligned minimal chunk */
2097 #define MIN_CHUNK_SIZE\
2098 ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
2099
2100 /* conversion from malloc headers to user pointers, and back */
2101 #define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))
2102 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
2103 /* chunk associated with aligned address A */
2104 #define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))
2105
2106 /* Bounds on request (not chunk) sizes. */
2107 #define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)
2108 #define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
2109
2110 /* pad request bytes into a usable size */
2111 #define pad_request(req) \
2112 (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
2113
2114 /* pad request, checking for minimum (but not maximum) */
2115 #define request2size(req) \
2116 (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
2117
2118
2119 /* ------------------ Operations on head and foot fields ----------------- */
2120
2121 /*
2122 The head field of a chunk is or'ed with PINUSE_BIT when previous
2123 adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
2124 use, unless mmapped, in which case both bits are cleared.
2125
2126 FLAG4_BIT is not used by this malloc, but might be useful in extensions.
2127 */
2128
2129 #define PINUSE_BIT (SIZE_T_ONE)
2130 #define CINUSE_BIT (SIZE_T_TWO)
2131 #define FLAG4_BIT (SIZE_T_FOUR)
2132 #define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)
2133 #define FLAG_BITS (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT)
2134
2135 /* Head value for fenceposts */
2136 #define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)
2137
2138 /* extraction of fields from head words */
2139 #define cinuse(p) ((p)->head & CINUSE_BIT)
2140 #define pinuse(p) ((p)->head & PINUSE_BIT)
2141 #define is_inuse(p) (((p)->head & INUSE_BITS) != PINUSE_BIT)
2142 #define is_mmapped(p) (((p)->head & INUSE_BITS) == 0)
2143
2144 #define chunksize(p) ((p)->head & ~(FLAG_BITS))
2145
2146 #define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)
2147
2148 /* Treat space at ptr +/- offset as a chunk */
2149 #define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
2150 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
2151
2152 /* Ptr to next or previous physical malloc_chunk. */
2153 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS)))
2154 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
2155
2156 /* extract next chunk's pinuse bit */
2157 #define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)
2158
2159 /* Get/set size at footer */
2160 #define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)
2161 #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
2162
2163 /* Set size, pinuse bit, and foot */
2164 #define set_size_and_pinuse_of_free_chunk(p, s)\
2165 ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
2166
2167 /* Set size, pinuse bit, foot, and clear next pinuse */
2168 #define set_free_with_pinuse(p, s, n)\
2169 (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
2170
2171 /* Get the internal overhead associated with chunk p */
2172 #define overhead_for(p)\
2173 (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
2174
2175 /* Return true if malloced space is not necessarily cleared */
2176 #if MMAP_CLEARS
2177 #define calloc_must_clear(p) (!is_mmapped(p))
2178 #else /* MMAP_CLEARS */
2179 #define calloc_must_clear(p) (1)
2180 #endif /* MMAP_CLEARS */
2181
2182 /* ---------------------- Overlaid data structures ----------------------- */
2183
2184 /*
2185 When chunks are not in use, they are treated as nodes of either
2186 lists or trees.
2187
2188 "Small" chunks are stored in circular doubly-linked lists, and look
2189 like this:
2190
2191 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2192 | Size of previous chunk |
2193 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2194 `head:' | Size of chunk, in bytes |P|
2195 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2196 | Forward pointer to next chunk in list |
2197 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2198 | Back pointer to previous chunk in list |
2199 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2200 | Unused space (may be 0 bytes long) .
2201 . .
2202 . |
2203 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2204 `foot:' | Size of chunk, in bytes |
2205 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2206
2207 Larger chunks are kept in a form of bitwise digital trees (aka
2208 tries) keyed on chunksizes. Because malloc_tree_chunks are only for
2209 free chunks greater than 256 bytes, their size doesn't impose any
2210 constraints on user chunk sizes. Each node looks like:
2211
2212 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2213 | Size of previous chunk |
2214 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2215 `head:' | Size of chunk, in bytes |P|
2216 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2217 | Forward pointer to next chunk of same size |
2218 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2219 | Back pointer to previous chunk of same size |
2220 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2221 | Pointer to left child (child[0]) |
2222 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2223 | Pointer to right child (child[1]) |
2224 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2225 | Pointer to parent |
2226 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2227 | bin index of this chunk |
2228 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2229 | Unused space .
2230 . |
2231 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2232 `foot:' | Size of chunk, in bytes |
2233 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2234
2235 Each tree holding treenodes is a tree of unique chunk sizes. Chunks
2236 of the same size are arranged in a circularly-linked list, with only
2237 the oldest chunk (the next to be used, in our FIFO ordering)
2238 actually in the tree. (Tree members are distinguished by a non-null
2239 parent pointer.) If a chunk with the same size an an existing node
2240 is inserted, it is linked off the existing node using pointers that
2241 work in the same way as fd/bk pointers of small chunks.
2242
2243 Each tree contains a power of 2 sized range of chunk sizes (the
2244 smallest is 0x100 <= x < 0x180), which is is divided in half at each
2245 tree level, with the chunks in the smaller half of the range (0x100
2246 <= x < 0x140 for the top nose) in the left subtree and the larger
2247 half (0x140 <= x < 0x180) in the right subtree. This is, of course,
2248 done by inspecting individual bits.
2249
2250 Using these rules, each node's left subtree contains all smaller
2251 sizes than its right subtree. However, the node at the root of each
2252 subtree has no particular ordering relationship to either. (The
2253 dividing line between the subtree sizes is based on trie relation.)
2254 If we remove the last chunk of a given size from the interior of the
2255 tree, we need to replace it with a leaf node. The tree ordering
2256 rules permit a node to be replaced by any leaf below it.
2257
2258 The smallest chunk in a tree (a common operation in a best-fit
2259 allocator) can be found by walking a path to the leftmost leaf in
2260 the tree. Unlike a usual binary tree, where we follow left child
2261 pointers until we reach a null, here we follow the right child
2262 pointer any time the left one is null, until we reach a leaf with
2263 both child pointers null. The smallest chunk in the tree will be
2264 somewhere along that path.
2265
2266 The worst case number of steps to add, find, or remove a node is
2267 bounded by the number of bits differentiating chunks within
2268 bins. Under current bin calculations, this ranges from 6 up to 21
2269 (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
2270 is of course much better.
2271 */
2272
2273 struct malloc_tree_chunk {
2274 /* The first four fields must be compatible with malloc_chunk */
2275 size_t prev_foot;
2276 size_t head;
2277 struct malloc_tree_chunk* fd;
2278 struct malloc_tree_chunk* bk;
2279
2280 struct malloc_tree_chunk* child[2];
2281 struct malloc_tree_chunk* parent;
2282 bindex_t index;
2283 };
2284
2285 typedef struct malloc_tree_chunk tchunk;
2286 typedef struct malloc_tree_chunk* tchunkptr;
2287 typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
2288
2289 /* A little helper macro for trees */
2290 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
2291
2292 /* ----------------------------- Segments -------------------------------- */
2293
2294 /*
2295 Each malloc space may include non-contiguous segments, held in a
2296 list headed by an embedded malloc_segment record representing the
2297 top-most space. Segments also include flags holding properties of
2298 the space. Large chunks that are directly allocated by mmap are not
2299 included in this list. They are instead independently created and
2300 destroyed without otherwise keeping track of them.
2301
2302 Segment management mainly comes into play for spaces allocated by
2303 MMAP. Any call to MMAP might or might not return memory that is
2304 adjacent to an existing segment. MORECORE normally contiguously
2305 extends the current space, so this space is almost always adjacent,
2306 which is simpler and faster to deal with. (This is why MORECORE is
2307 used preferentially to MMAP when both are available -- see
2308 sys_alloc.) When allocating using MMAP, we don't use any of the
2309 hinting mechanisms (inconsistently) supported in various
2310 implementations of unix mmap, or distinguish reserving from
2311 committing memory. Instead, we just ask for space, and exploit
2312 contiguity when we get it. It is probably possible to do
2313 better than this on some systems, but no general scheme seems
2314 to be significantly better.
2315
2316 Management entails a simpler variant of the consolidation scheme
2317 used for chunks to reduce fragmentation -- new adjacent memory is
2318 normally prepended or appended to an existing segment. However,
2319 there are limitations compared to chunk consolidation that mostly
2320 reflect the fact that segment processing is relatively infrequent
2321 (occurring only when getting memory from system) and that we
2322 don't expect to have huge numbers of segments:
2323
2324 * Segments are not indexed, so traversal requires linear scans. (It
2325 would be possible to index these, but is not worth the extra
2326 overhead and complexity for most programs on most platforms.)
2327 * New segments are only appended to old ones when holding top-most
2328 memory; if they cannot be prepended to others, they are held in
2329 different segments.
2330
2331 Except for the top-most segment of an mstate, each segment record
2332 is kept at the tail of its segment. Segments are added by pushing
2333 segment records onto the list headed by &mstate.seg for the
2334 containing mstate.
2335
2336 Segment flags control allocation/merge/deallocation policies:
2337 * If EXTERN_BIT set, then we did not allocate this segment,
2338 and so should not try to deallocate or merge with others.
2339 (This currently holds only for the initial segment passed
2340 into create_mspace_with_base.)
2341 * If USE_MMAP_BIT set, the segment may be merged with
2342 other surrounding mmapped segments and trimmed/de-allocated
2343 using munmap.
2344 * If neither bit is set, then the segment was obtained using
2345 MORECORE so can be merged with surrounding MORECORE'd segments
2346 and deallocated/trimmed using MORECORE with negative arguments.
2347 */
2348
2349 struct malloc_segment {
2350 char* base; /* base address */
2351 size_t size; /* allocated size */
2352 struct malloc_segment* next; /* ptr to next segment */
2353 flag_t sflags; /* mmap and extern flag */
2354 };
2355
2356 #define is_mmapped_segment(S) ((S)->sflags & USE_MMAP_BIT)
2357 #define is_extern_segment(S) ((S)->sflags & EXTERN_BIT)
2358
2359 typedef struct malloc_segment msegment;
2360 typedef struct malloc_segment* msegmentptr;
2361
2362 /* ---------------------------- malloc_state ----------------------------- */
2363
2364 /*
2365 A malloc_state holds all of the bookkeeping for a space.
2366 The main fields are:
2367
2368 Top
2369 The topmost chunk of the currently active segment. Its size is
2370 cached in topsize. The actual size of topmost space is
2371 topsize+TOP_FOOT_SIZE, which includes space reserved for adding
2372 fenceposts and segment records if necessary when getting more
2373 space from the system. The size at which to autotrim top is
2374 cached from mparams in trim_check, except that it is disabled if
2375 an autotrim fails.
2376
2377 Designated victim (dv)
2378 This is the preferred chunk for servicing small requests that
2379 don't have exact fits. It is normally the chunk split off most
2380 recently to service another small request. Its size is cached in
2381 dvsize. The link fields of this chunk are not maintained since it
2382 is not kept in a bin.
2383
2384 SmallBins
2385 An array of bin headers for free chunks. These bins hold chunks
2386 with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
2387 chunks of all the same size, spaced 8 bytes apart. To simplify
2388 use in double-linked lists, each bin header acts as a malloc_chunk
2389 pointing to the real first node, if it exists (else pointing to
2390 itself). This avoids special-casing for headers. But to avoid
2391 waste, we allocate only the fd/bk pointers of bins, and then use
2392 repositioning tricks to treat these as the fields of a chunk.
2393
2394 TreeBins
2395 Treebins are pointers to the roots of trees holding a range of
2396 sizes. There are 2 equally spaced treebins for each power of two
2397 from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
2398 larger.
2399
2400 Bin maps
2401 There is one bit map for small bins ("smallmap") and one for
2402 treebins ("treemap). Each bin sets its bit when non-empty, and
2403 clears the bit when empty. Bit operations are then used to avoid
2404 bin-by-bin searching -- nearly all "search" is done without ever
2405 looking at bins that won't be selected. The bit maps
2406 conservatively use 32 bits per map word, even if on 64bit system.
2407 For a good description of some of the bit-based techniques used
2408 here, see Henry S. Warren Jr's book "Hacker's Delight" (and
2409 supplement at http://hackersdelight.org/). Many of these are
2410 intended to reduce the branchiness of paths through malloc etc, as
2411 well as to reduce the number of memory locations read or written.
2412
2413 Segments
2414 A list of segments headed by an embedded malloc_segment record
2415 representing the initial space.
2416
2417 Address check support
2418 The least_addr field is the least address ever obtained from
2419 MORECORE or MMAP. Attempted frees and reallocs of any address less
2420 than this are trapped (unless INSECURE is defined).
2421
2422 Magic tag
2423 A cross-check field that should always hold same value as mparams.magic.
2424
2425 Flags
2426 Bits recording whether to use MMAP, locks, or contiguous MORECORE
2427
2428 Statistics
2429 Each space keeps track of current and maximum system memory
2430 obtained via MORECORE or MMAP.
2431
2432 Trim support
2433 Fields holding the amount of unused topmost memory that should trigger
2434 timming, and a counter to force periodic scanning to release unused
2435 non-topmost segments.
2436
2437 Locking
2438 If USE_LOCKS is defined, the "mutex" lock is acquired and released
2439 around every public call using this mspace.
2440
2441 Extension support
2442 A void* pointer and a size_t field that can be used to help implement
2443 extensions to this malloc.
2444 */
2445
2446 /* Bin types, widths and sizes */
2447 #define NSMALLBINS (32U)
2448 #define NTREEBINS (32U)
2449 #define SMALLBIN_SHIFT (3U)
2450 #define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)
2451 #define TREEBIN_SHIFT (8U)
2452 #define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)
2453 #define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)
2454 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
2455
2456 struct malloc_state {
2457 binmap_t smallmap;
2458 binmap_t treemap;
2459 size_t dvsize;
2460 size_t topsize;
2461 char* least_addr;
2462 mchunkptr dv;
2463 mchunkptr top;
2464 size_t trim_check;
2465 size_t release_checks;
2466 size_t magic;
2467 mchunkptr smallbins[(NSMALLBINS+1)*2];
2468 tbinptr treebins[NTREEBINS];
2469 size_t footprint;
2470 size_t max_footprint;
2471 flag_t mflags;
2472 #if USE_LOCKS
2473 MLOCK_T mutex; /* locate lock among fields that rarely change */
2474 #endif /* USE_LOCKS */
2475 msegment seg;
2476 void* extp; /* Unused but available for extensions */
2477 size_t exts;
2478 };
2479
2480 typedef struct malloc_state* mstate;
2481
2482 /* ------------- Global malloc_state and malloc_params ------------------- */
2483
2484 /*
2485 malloc_params holds global properties, including those that can be
2486 dynamically set using mallopt. There is a single instance, mparams,
2487 initialized in init_mparams. Note that the non-zeroness of "magic"
2488 also serves as an initialization flag.
2489 */
2490
2491 struct malloc_params {
2492 volatile size_t magic;
2493 size_t page_size;
2494 size_t granularity;
2495 size_t mmap_threshold;
2496 size_t trim_threshold;
2497 flag_t default_mflags;
2498 };
2499
2500 static struct malloc_params mparams;
2501
2502 /* Ensure mparams initialized */
2503 #define ensure_initialization() (void)(mparams.magic != 0 || init_mparams())
2504
2505 #if !ONLY_MSPACES
2506
2507 /* The global malloc_state used for all non-"mspace" calls */
2508 static struct malloc_state _gm_;
2509 #define gm (&_gm_)
2510 #define is_global(M) ((M) == &_gm_)
2511
2512 #endif /* !ONLY_MSPACES */
2513
2514 #define is_initialized(M) ((M)->top != 0)
2515
2516 /* -------------------------- system alloc setup ------------------------- */
2517
2518 /* Operations on mflags */
2519
2520 #define use_lock(M) ((M)->mflags & USE_LOCK_BIT)
2521 #define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)
2522 #define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)
2523
2524 #define use_mmap(M) ((M)->mflags & USE_MMAP_BIT)
2525 #define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT)
2526 #define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT)
2527
2528 #define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT)
2529 #define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT)
2530
2531 #define set_lock(M,L)\
2532 ((M)->mflags = (L)?\
2533 ((M)->mflags | USE_LOCK_BIT) :\
2534 ((M)->mflags & ~USE_LOCK_BIT))
2535
2536 /* page-align a size */
2537 #define page_align(S)\
2538 (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE))
2539
2540 /* granularity-align a size */
2541 #define granularity_align(S)\
2542 (((S) + (mparams.granularity - SIZE_T_ONE))\
2543 & ~(mparams.granularity - SIZE_T_ONE))
2544
2545
2546 /* For mmap, use granularity alignment on windows, else page-align */
2547 #ifdef WIN32
2548 #define mmap_align(S) granularity_align(S)
2549 #else
2550 #define mmap_align(S) page_align(S)
2551 #endif
2552
2553 /* For sys_alloc, enough padding to ensure can malloc request on success */
2554 #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT)
2555
2556 #define is_page_aligned(S)\
2557 (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
2558 #define is_granularity_aligned(S)\
2559 (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
2560
2561 /* True if segment S holds address A */
2562 #define segment_holds(S, A)\
2563 ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
2564
2565 /* Return segment holding given address */
segment_holding(mstate m,char * addr)2566 static msegmentptr segment_holding(mstate m, char* addr) {
2567 msegmentptr sp = &m->seg;
2568 for (;;) {
2569 if (addr >= sp->base && addr < sp->base + sp->size)
2570 return sp;
2571 if ((sp = sp->next) == 0)
2572 return 0;
2573 }
2574 }
2575
2576 /* Return true if segment contains a segment link */
has_segment_link(mstate m,msegmentptr ss)2577 static int has_segment_link(mstate m, msegmentptr ss) {
2578 msegmentptr sp = &m->seg;
2579 for (;;) {
2580 if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
2581 return 1;
2582 if ((sp = sp->next) == 0)
2583 return 0;
2584 }
2585 }
2586
2587 #ifndef MORECORE_CANNOT_TRIM
2588 #define should_trim(M,s) ((s) > (M)->trim_check)
2589 #else /* MORECORE_CANNOT_TRIM */
2590 #define should_trim(M,s) (0)
2591 #endif /* MORECORE_CANNOT_TRIM */
2592
2593 /*
2594 TOP_FOOT_SIZE is padding at the end of a segment, including space
2595 that may be needed to place segment records and fenceposts when new
2596 noncontiguous segments are added.
2597 */
2598 #define TOP_FOOT_SIZE\
2599 (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
2600
2601
2602 /* ------------------------------- Hooks -------------------------------- */
2603
2604 /*
2605 PREACTION should be defined to return 0 on success, and nonzero on
2606 failure. If you are not using locking, you can redefine these to do
2607 anything you like.
2608 */
2609
2610 #if USE_LOCKS
2611
2612 #define PREACTION(M) ((use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
2613 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
2614 #else /* USE_LOCKS */
2615
2616 #ifndef PREACTION
2617 #define PREACTION(M) (0)
2618 #endif /* PREACTION */
2619
2620 #ifndef POSTACTION
2621 #define POSTACTION(M)
2622 #endif /* POSTACTION */
2623
2624 #endif /* USE_LOCKS */
2625
2626 /*
2627 CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
2628 USAGE_ERROR_ACTION is triggered on detected bad frees and
2629 reallocs. The argument p is an address that might have triggered the
2630 fault. It is ignored by the two predefined actions, but might be
2631 useful in custom actions that try to help diagnose errors.
2632 */
2633
2634 #if PROCEED_ON_ERROR
2635
2636 /* A count of the number of corruption errors causing resets */
2637 int malloc_corruption_error_count;
2638
2639 /* default corruption action */
2640 static void reset_on_error(mstate m);
2641
2642 #define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)
2643 #define USAGE_ERROR_ACTION(m, p)
2644
2645 #else /* PROCEED_ON_ERROR */
2646
2647 #ifndef CORRUPTION_ERROR_ACTION
2648 #define CORRUPTION_ERROR_ACTION(m) ABORT
2649 #endif /* CORRUPTION_ERROR_ACTION */
2650
2651 #ifndef USAGE_ERROR_ACTION
2652 #define USAGE_ERROR_ACTION(m,p) ABORT
2653 #endif /* USAGE_ERROR_ACTION */
2654
2655 #endif /* PROCEED_ON_ERROR */
2656
2657 /* -------------------------- Debugging setup ---------------------------- */
2658
2659 #if ! DEBUG
2660
2661 #define check_free_chunk(M,P)
2662 #define check_inuse_chunk(M,P)
2663 #define check_malloced_chunk(M,P,N)
2664 #define check_mmapped_chunk(M,P)
2665 #define check_malloc_state(M)
2666 #define check_top_chunk(M,P)
2667
2668 #else /* DEBUG */
2669 #define check_free_chunk(M,P) do_check_free_chunk(M,P)
2670 #define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)
2671 #define check_top_chunk(M,P) do_check_top_chunk(M,P)
2672 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
2673 #define check_mmapped_chunk(M,P) do_check_mmapped_chunk(M,P)
2674 #define check_malloc_state(M) do_check_malloc_state(M)
2675
2676 static void do_check_any_chunk(mstate m, mchunkptr p);
2677 static void do_check_top_chunk(mstate m, mchunkptr p);
2678 static void do_check_mmapped_chunk(mstate m, mchunkptr p);
2679 static void do_check_inuse_chunk(mstate m, mchunkptr p);
2680 static void do_check_free_chunk(mstate m, mchunkptr p);
2681 static void do_check_malloced_chunk(mstate m, void* mem, size_t s);
2682 static void do_check_tree(mstate m, tchunkptr t);
2683 static void do_check_treebin(mstate m, bindex_t i);
2684 static void do_check_smallbin(mstate m, bindex_t i);
2685 static void do_check_malloc_state(mstate m);
2686 static int bin_find(mstate m, mchunkptr x);
2687 static size_t traverse_and_check(mstate m);
2688 #endif /* DEBUG */
2689
2690 /* ---------------------------- Indexing Bins ---------------------------- */
2691
2692 #define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
2693 #define small_index(s) ((s) >> SMALLBIN_SHIFT)
2694 #define small_index2size(i) ((i) << SMALLBIN_SHIFT)
2695 #define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))
2696
2697 /* addressing by index. See above about smallbin repositioning */
2698 #define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
2699 #define treebin_at(M,i) (&((M)->treebins[i]))
2700
2701 /* assign tree index for size S to variable I. Use x86 asm if possible */
2702 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
2703 #define compute_tree_index(S, I)\
2704 {\
2705 unsigned int X = S >> TREEBIN_SHIFT;\
2706 if (X == 0)\
2707 I = 0;\
2708 else if (X > 0xFFFF)\
2709 I = NTREEBINS-1;\
2710 else {\
2711 unsigned int K;\
2712 __asm__("bsrl\t%1, %0\n\t" : "=r" (K) : "g" (X));\
2713 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2714 }\
2715 }
2716
2717 #elif defined (__INTEL_COMPILER)
2718 #define compute_tree_index(S, I)\
2719 {\
2720 size_t X = S >> TREEBIN_SHIFT;\
2721 if (X == 0)\
2722 I = 0;\
2723 else if (X > 0xFFFF)\
2724 I = NTREEBINS-1;\
2725 else {\
2726 unsigned int K = _bit_scan_reverse (X); \
2727 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2728 }\
2729 }
2730
2731 #elif defined(_MSC_VER) && _MSC_VER>=1300
2732 #define compute_tree_index(S, I)\
2733 {\
2734 size_t X = S >> TREEBIN_SHIFT;\
2735 if (X == 0)\
2736 I = 0;\
2737 else if (X > 0xFFFF)\
2738 I = NTREEBINS-1;\
2739 else {\
2740 unsigned int K;\
2741 _BitScanReverse((DWORD *) &K, (DWORD)X);\
2742 I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2743 }\
2744 }
2745
2746 #else /* GNUC */
2747 #define compute_tree_index(S, I)\
2748 {\
2749 size_t X = S >> TREEBIN_SHIFT;\
2750 if (X == 0)\
2751 I = 0;\
2752 else if (X > 0xFFFF)\
2753 I = NTREEBINS-1;\
2754 else {\
2755 unsigned int Y = (unsigned int)X;\
2756 unsigned int N = ((Y - 0x100) >> 16) & 8;\
2757 unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
2758 N += K;\
2759 N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
2760 K = 14 - N + ((Y <<= K) >> 15);\
2761 I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
2762 }\
2763 }
2764 #endif /* GNUC */
2765
2766 /* Bit representing maximum resolved size in a treebin at i */
2767 #define bit_for_tree_index(i) \
2768 (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
2769
2770 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
2771 #define leftshift_for_tree_index(i) \
2772 ((i == NTREEBINS-1)? 0 : \
2773 ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
2774
2775 /* The size of the smallest chunk held in bin with index i */
2776 #define minsize_for_tree_index(i) \
2777 ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \
2778 (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
2779
2780
2781 /* ------------------------ Operations on bin maps ----------------------- */
2782
2783 /* bit corresponding to given index */
2784 #define idx2bit(i) ((binmap_t)(1) << (i))
2785
2786 /* Mark/Clear bits with given index */
2787 #define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))
2788 #define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))
2789 #define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))
2790
2791 #define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))
2792 #define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))
2793 #define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))
2794
2795 /* isolate the least set bit of a bitmap */
2796 #define least_bit(x) ((x) & (-(x)))
2797
2798 /* mask with all bits to left of least bit of x on */
2799 #define left_bits(x) ((x<<1) | -(x<<1))
2800
2801 /* mask with all bits to left of or equal to least bit of x on */
2802 #define same_or_left_bits(x) ((x) | -(x))
2803
2804 /* index corresponding to given bit. Use x86 asm if possible */
2805
2806 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
2807 #define compute_bit2idx(X, I)\
2808 {\
2809 unsigned int J;\
2810 __asm__("bsfl\t%1, %0\n\t" : "=r" (J) : "g" (X));\
2811 I = (bindex_t)J;\
2812 }
2813
2814 #elif defined (__INTEL_COMPILER)
2815 #define compute_bit2idx(X, I)\
2816 {\
2817 unsigned int J;\
2818 J = _bit_scan_forward (X); \
2819 I = (bindex_t)J;\
2820 }
2821
2822 #elif defined(_MSC_VER) && _MSC_VER>=1300
2823 #define compute_bit2idx(X, I)\
2824 {\
2825 unsigned int J;\
2826 _BitScanForward((DWORD *) &J, X);\
2827 I = (bindex_t)J;\
2828 }
2829
2830 #elif USE_BUILTIN_FFS
2831 #define compute_bit2idx(X, I) I = ffs(X)-1
2832
2833 #else
2834 #define compute_bit2idx(X, I)\
2835 {\
2836 unsigned int Y = X - 1;\
2837 unsigned int K = Y >> (16-4) & 16;\
2838 unsigned int N = K; Y >>= K;\
2839 N += K = Y >> (8-3) & 8; Y >>= K;\
2840 N += K = Y >> (4-2) & 4; Y >>= K;\
2841 N += K = Y >> (2-1) & 2; Y >>= K;\
2842 N += K = Y >> (1-0) & 1; Y >>= K;\
2843 I = (bindex_t)(N + Y);\
2844 }
2845 #endif /* GNUC */
2846
2847
2848 /* ----------------------- Runtime Check Support ------------------------- */
2849
2850 /*
2851 For security, the main invariant is that malloc/free/etc never
2852 writes to a static address other than malloc_state, unless static
2853 malloc_state itself has been corrupted, which cannot occur via
2854 malloc (because of these checks). In essence this means that we
2855 believe all pointers, sizes, maps etc held in malloc_state, but
2856 check all of those linked or offsetted from other embedded data
2857 structures. These checks are interspersed with main code in a way
2858 that tends to minimize their run-time cost.
2859
2860 When FOOTERS is defined, in addition to range checking, we also
2861 verify footer fields of inuse chunks, which can be used guarantee
2862 that the mstate controlling malloc/free is intact. This is a
2863 streamlined version of the approach described by William Robertson
2864 et al in "Run-time Detection of Heap-based Overflows" LISA'03
2865 http://www.usenix.org/events/lisa03/tech/robertson.html The footer
2866 of an inuse chunk holds the xor of its mstate and a random seed,
2867 that is checked upon calls to free() and realloc(). This is
2868 (probablistically) unguessable from outside the program, but can be
2869 computed by any code successfully malloc'ing any chunk, so does not
2870 itself provide protection against code that has already broken
2871 security through some other means. Unlike Robertson et al, we
2872 always dynamically check addresses of all offset chunks (previous,
2873 next, etc). This turns out to be cheaper than relying on hashes.
2874 */
2875
2876 #if !INSECURE
2877 /* Check if address a is at least as high as any from MORECORE or MMAP */
2878 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
2879 /* Check if address of next chunk n is higher than base chunk p */
2880 #define ok_next(p, n) ((char*)(p) < (char*)(n))
2881 /* Check if p has inuse status */
2882 #define ok_inuse(p) is_inuse(p)
2883 /* Check if p has its pinuse bit on */
2884 #define ok_pinuse(p) pinuse(p)
2885
2886 #else /* !INSECURE */
2887 #define ok_address(M, a) (1)
2888 #define ok_next(b, n) (1)
2889 #define ok_inuse(p) (1)
2890 #define ok_pinuse(p) (1)
2891 #endif /* !INSECURE */
2892
2893 #if (FOOTERS && !INSECURE)
2894 /* Check if (alleged) mstate m has expected magic field */
2895 #define ok_magic(M) ((M)->magic == mparams.magic)
2896 #else /* (FOOTERS && !INSECURE) */
2897 #define ok_magic(M) (1)
2898 #endif /* (FOOTERS && !INSECURE) */
2899
2900
2901 /* In gcc, use __builtin_expect to minimize impact of checks */
2902 #if !INSECURE
2903 #if defined(__GNUC__) && __GNUC__ >= 3
2904 #define RTCHECK(e) __builtin_expect(e, 1)
2905 #else /* GNUC */
2906 #define RTCHECK(e) (e)
2907 #endif /* GNUC */
2908 #else /* !INSECURE */
2909 #define RTCHECK(e) (1)
2910 #endif /* !INSECURE */
2911
2912 /* macros to set up inuse chunks with or without footers */
2913
2914 #if !FOOTERS
2915
2916 #define mark_inuse_foot(M,p,s)
2917
2918 /* Macros for setting head/foot of non-mmapped chunks */
2919
2920 /* Set cinuse bit and pinuse bit of next chunk */
2921 #define set_inuse(M,p,s)\
2922 ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2923 ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2924
2925 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
2926 #define set_inuse_and_pinuse(M,p,s)\
2927 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2928 ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2929
2930 /* Set size, cinuse and pinuse bit of this chunk */
2931 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2932 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
2933
2934 #else /* FOOTERS */
2935
2936 /* Set foot of inuse chunk to be xor of mstate and seed */
2937 #define mark_inuse_foot(M,p,s)\
2938 (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
2939
2940 #define get_mstate_for(p)\
2941 ((mstate)(((mchunkptr)((char*)(p) +\
2942 (chunksize(p))))->prev_foot ^ mparams.magic))
2943
2944 #define set_inuse(M,p,s)\
2945 ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2946 (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
2947 mark_inuse_foot(M,p,s))
2948
2949 #define set_inuse_and_pinuse(M,p,s)\
2950 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2951 (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
2952 mark_inuse_foot(M,p,s))
2953
2954 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2955 ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2956 mark_inuse_foot(M, p, s))
2957
2958 #endif /* !FOOTERS */
2959
2960 /* ---------------------------- setting mparams -------------------------- */
2961
2962 /* Initialize mparams */
init_mparams(void)2963 static int init_mparams(void) {
2964 #ifdef NEED_GLOBAL_LOCK_INIT
2965 if (malloc_global_mutex_status <= 0)
2966 init_malloc_global_mutex();
2967 #endif
2968
2969 ACQUIRE_MALLOC_GLOBAL_LOCK();
2970 if (mparams.magic == 0) {
2971 size_t psize;
2972 size_t gsize;
2973
2974 #ifndef WIN32
2975 psize = malloc_getpagesize;
2976 gsize = ((DEFAULT_GRANULARITY != 0)? DEFAULT_GRANULARITY : psize);
2977 #else /* WIN32 */
2978 {
2979 SYSTEM_INFO system_info;
2980 GetSystemInfo(&system_info);
2981 psize = system_info.dwPageSize;
2982 gsize = ((DEFAULT_GRANULARITY != 0)?
2983 DEFAULT_GRANULARITY : system_info.dwAllocationGranularity);
2984 }
2985 #endif /* WIN32 */
2986
2987 /* Sanity-check configuration:
2988 size_t must be unsigned and as wide as pointer type.
2989 ints must be at least 4 bytes.
2990 alignment must be at least 8.
2991 Alignment, min chunk size, and page size must all be powers of 2.
2992 */
2993 if ((sizeof(size_t) != sizeof(char*)) ||
2994 (MAX_SIZE_T < MIN_CHUNK_SIZE) ||
2995 (sizeof(int) < 4) ||
2996 (MALLOC_ALIGNMENT < (size_t)8U) ||
2997 ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
2998 ((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) ||
2999 ((gsize & (gsize-SIZE_T_ONE)) != 0) ||
3000 ((psize & (psize-SIZE_T_ONE)) != 0))
3001 ABORT;
3002
3003 mparams.granularity = gsize;
3004 mparams.page_size = psize;
3005 mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
3006 mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
3007 #if MORECORE_CONTIGUOUS
3008 mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
3009 #else /* MORECORE_CONTIGUOUS */
3010 mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
3011 #endif /* MORECORE_CONTIGUOUS */
3012
3013 #if !ONLY_MSPACES
3014 /* Set up lock for main malloc area */
3015 gm->mflags = mparams.default_mflags;
3016 INITIAL_LOCK(&gm->mutex);
3017 #endif
3018
3019 {
3020 size_t magic;
3021 #if USE_DEV_RANDOM
3022 int fd;
3023 unsigned char buf[sizeof(size_t)];
3024 /* Try to use /dev/urandom, else fall back on using time */
3025 if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
3026 read(fd, buf, sizeof(buf)) == sizeof(buf)) {
3027 magic = *((size_t *) buf);
3028 close(fd);
3029 }
3030 else
3031 #endif /* USE_DEV_RANDOM */
3032 #ifdef WIN32
3033 magic = (size_t)(GetTickCount() ^ (size_t)0x55555555U);
3034 #else
3035 magic = (size_t)(time(0) ^ (size_t)0x55555555U);
3036 #endif
3037 magic |= (size_t)8U; /* ensure nonzero */
3038 magic &= ~(size_t)7U; /* improve chances of fault for bad values */
3039 mparams.magic = magic;
3040 }
3041 }
3042
3043 RELEASE_MALLOC_GLOBAL_LOCK();
3044 return 1;
3045 }
3046
3047 /* support for mallopt */
change_mparam(int param_number,int value)3048 static int change_mparam(int param_number, int value) {
3049 size_t val;
3050 ensure_initialization();
3051 val = (value == -1)? MAX_SIZE_T : (size_t)value;
3052 switch(param_number) {
3053 case M_TRIM_THRESHOLD:
3054 mparams.trim_threshold = val;
3055 return 1;
3056 case M_GRANULARITY:
3057 if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
3058 mparams.granularity = val;
3059 return 1;
3060 }
3061 else
3062 return 0;
3063 case M_MMAP_THRESHOLD:
3064 mparams.mmap_threshold = val;
3065 return 1;
3066 default:
3067 return 0;
3068 }
3069 }
3070
3071 #if DEBUG
3072 /* ------------------------- Debugging Support --------------------------- */
3073
3074 /* Check properties of any chunk, whether free, inuse, mmapped etc */
do_check_any_chunk(mstate m,mchunkptr p)3075 static void do_check_any_chunk(mstate m, mchunkptr p) {
3076 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3077 assert(ok_address(m, p));
3078 }
3079
3080 /* Check properties of top chunk */
do_check_top_chunk(mstate m,mchunkptr p)3081 static void do_check_top_chunk(mstate m, mchunkptr p) {
3082 msegmentptr sp = segment_holding(m, (char*)p);
3083 size_t sz = p->head & ~INUSE_BITS; /* third-lowest bit can be set! */
3084 assert(sp != 0);
3085 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3086 assert(ok_address(m, p));
3087 assert(sz == m->topsize);
3088 assert(sz > 0);
3089 assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
3090 assert(pinuse(p));
3091 assert(!pinuse(chunk_plus_offset(p, sz)));
3092 }
3093
3094 /* Check properties of (inuse) mmapped chunks */
do_check_mmapped_chunk(mstate m,mchunkptr p)3095 static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
3096 size_t sz = chunksize(p);
3097 size_t len = (sz + (p->prev_foot) + MMAP_FOOT_PAD);
3098 assert(is_mmapped(p));
3099 assert(use_mmap(m));
3100 assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3101 assert(ok_address(m, p));
3102 assert(!is_small(sz));
3103 assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
3104 assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
3105 assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
3106 }
3107
3108 /* Check properties of inuse chunks */
do_check_inuse_chunk(mstate m,mchunkptr p)3109 static void do_check_inuse_chunk(mstate m, mchunkptr p) {
3110 do_check_any_chunk(m, p);
3111 assert(is_inuse(p));
3112 assert(next_pinuse(p));
3113 /* If not pinuse and not mmapped, previous chunk has OK offset */
3114 assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
3115 if (is_mmapped(p))
3116 do_check_mmapped_chunk(m, p);
3117 }
3118
3119 /* Check properties of free chunks */
do_check_free_chunk(mstate m,mchunkptr p)3120 static void do_check_free_chunk(mstate m, mchunkptr p) {
3121 size_t sz = chunksize(p);
3122 mchunkptr next = chunk_plus_offset(p, sz);
3123 do_check_any_chunk(m, p);
3124 assert(!is_inuse(p));
3125 assert(!next_pinuse(p));
3126 assert (!is_mmapped(p));
3127 if (p != m->dv && p != m->top) {
3128 if (sz >= MIN_CHUNK_SIZE) {
3129 assert((sz & CHUNK_ALIGN_MASK) == 0);
3130 assert(is_aligned(chunk2mem(p)));
3131 assert(next->prev_foot == sz);
3132 assert(pinuse(p));
3133 assert (next == m->top || is_inuse(next));
3134 assert(p->fd->bk == p);
3135 assert(p->bk->fd == p);
3136 }
3137 else /* markers are always of size SIZE_T_SIZE */
3138 assert(sz == SIZE_T_SIZE);
3139 }
3140 }
3141
3142 /* Check properties of malloced chunks at the point they are malloced */
do_check_malloced_chunk(mstate m,void * mem,size_t s)3143 static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
3144 if (mem != 0) {
3145 mchunkptr p = mem2chunk(mem);
3146 size_t sz = p->head & ~INUSE_BITS;
3147 do_check_inuse_chunk(m, p);
3148 assert((sz & CHUNK_ALIGN_MASK) == 0);
3149 assert(sz >= MIN_CHUNK_SIZE);
3150 assert(sz >= s);
3151 /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
3152 assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
3153 }
3154 }
3155
3156 /* Check a tree and its subtrees. */
do_check_tree(mstate m,tchunkptr t)3157 static void do_check_tree(mstate m, tchunkptr t) {
3158 tchunkptr head = 0;
3159 tchunkptr u = t;
3160 bindex_t tindex = t->index;
3161 size_t tsize = chunksize(t);
3162 bindex_t idx;
3163 compute_tree_index(tsize, idx);
3164 assert(tindex == idx);
3165 assert(tsize >= MIN_LARGE_SIZE);
3166 assert(tsize >= minsize_for_tree_index(idx));
3167 assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
3168
3169 do { /* traverse through chain of same-sized nodes */
3170 do_check_any_chunk(m, ((mchunkptr)u));
3171 assert(u->index == tindex);
3172 assert(chunksize(u) == tsize);
3173 assert(!is_inuse(u));
3174 assert(!next_pinuse(u));
3175 assert(u->fd->bk == u);
3176 assert(u->bk->fd == u);
3177 if (u->parent == 0) {
3178 assert(u->child[0] == 0);
3179 assert(u->child[1] == 0);
3180 }
3181 else {
3182 assert(head == 0); /* only one node on chain has parent */
3183 head = u;
3184 assert(u->parent != u);
3185 assert (u->parent->child[0] == u ||
3186 u->parent->child[1] == u ||
3187 *((tbinptr*)(u->parent)) == u);
3188 if (u->child[0] != 0) {
3189 assert(u->child[0]->parent == u);
3190 assert(u->child[0] != u);
3191 do_check_tree(m, u->child[0]);
3192 }
3193 if (u->child[1] != 0) {
3194 assert(u->child[1]->parent == u);
3195 assert(u->child[1] != u);
3196 do_check_tree(m, u->child[1]);
3197 }
3198 if (u->child[0] != 0 && u->child[1] != 0) {
3199 assert(chunksize(u->child[0]) < chunksize(u->child[1]));
3200 }
3201 }
3202 u = u->fd;
3203 } while (u != t);
3204 assert(head != 0);
3205 }
3206
3207 /* Check all the chunks in a treebin. */
do_check_treebin(mstate m,bindex_t i)3208 static void do_check_treebin(mstate m, bindex_t i) {
3209 tbinptr* tb = treebin_at(m, i);
3210 tchunkptr t = *tb;
3211 int empty = (m->treemap & (1U << i)) == 0;
3212 if (t == 0)
3213 assert(empty);
3214 if (!empty)
3215 do_check_tree(m, t);
3216 }
3217
3218 /* Check all the chunks in a smallbin. */
do_check_smallbin(mstate m,bindex_t i)3219 static void do_check_smallbin(mstate m, bindex_t i) {
3220 sbinptr b = smallbin_at(m, i);
3221 mchunkptr p = b->bk;
3222 unsigned int empty = (m->smallmap & (1U << i)) == 0;
3223 if (p == b)
3224 assert(empty);
3225 if (!empty) {
3226 for (; p != b; p = p->bk) {
3227 size_t size = chunksize(p);
3228 mchunkptr q;
3229 /* each chunk claims to be free */
3230 do_check_free_chunk(m, p);
3231 /* chunk belongs in bin */
3232 assert(small_index(size) == i);
3233 assert(p->bk == b || chunksize(p->bk) == chunksize(p));
3234 /* chunk is followed by an inuse chunk */
3235 q = next_chunk(p);
3236 if (q->head != FENCEPOST_HEAD)
3237 do_check_inuse_chunk(m, q);
3238 }
3239 }
3240 }
3241
3242 /* Find x in a bin. Used in other check functions. */
bin_find(mstate m,mchunkptr x)3243 static int bin_find(mstate m, mchunkptr x) {
3244 size_t size = chunksize(x);
3245 if (is_small(size)) {
3246 bindex_t sidx = small_index(size);
3247 sbinptr b = smallbin_at(m, sidx);
3248 if (smallmap_is_marked(m, sidx)) {
3249 mchunkptr p = b;
3250 do {
3251 if (p == x)
3252 return 1;
3253 } while ((p = p->fd) != b);
3254 }
3255 }
3256 else {
3257 bindex_t tidx;
3258 compute_tree_index(size, tidx);
3259 if (treemap_is_marked(m, tidx)) {
3260 tchunkptr t = *treebin_at(m, tidx);
3261 size_t sizebits = size << leftshift_for_tree_index(tidx);
3262 while (t != 0 && chunksize(t) != size) {
3263 t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
3264 sizebits <<= 1;
3265 }
3266 if (t != 0) {
3267 tchunkptr u = t;
3268 do {
3269 if (u == (tchunkptr)x)
3270 return 1;
3271 } while ((u = u->fd) != t);
3272 }
3273 }
3274 }
3275 return 0;
3276 }
3277
3278 /* Traverse each chunk and check it; return total */
traverse_and_check(mstate m)3279 static size_t traverse_and_check(mstate m) {
3280 size_t sum = 0;
3281 if (is_initialized(m)) {
3282 msegmentptr s = &m->seg;
3283 sum += m->topsize + TOP_FOOT_SIZE;
3284 while (s != 0) {
3285 mchunkptr q = align_as_chunk(s->base);
3286 mchunkptr lastq = 0;
3287 assert(pinuse(q));
3288 while (segment_holds(s, q) &&
3289 q != m->top && q->head != FENCEPOST_HEAD) {
3290 sum += chunksize(q);
3291 if (is_inuse(q)) {
3292 assert(!bin_find(m, q));
3293 do_check_inuse_chunk(m, q);
3294 }
3295 else {
3296 assert(q == m->dv || bin_find(m, q));
3297 assert(lastq == 0 || is_inuse(lastq)); /* Not 2 consecutive free */
3298 do_check_free_chunk(m, q);
3299 }
3300 lastq = q;
3301 q = next_chunk(q);
3302 }
3303 s = s->next;
3304 }
3305 }
3306 return sum;
3307 }
3308
3309 /* Check all properties of malloc_state. */
do_check_malloc_state(mstate m)3310 static void do_check_malloc_state(mstate m) {
3311 bindex_t i;
3312 size_t total;
3313 /* check bins */
3314 for (i = 0; i < NSMALLBINS; ++i)
3315 do_check_smallbin(m, i);
3316 for (i = 0; i < NTREEBINS; ++i)
3317 do_check_treebin(m, i);
3318
3319 if (m->dvsize != 0) { /* check dv chunk */
3320 do_check_any_chunk(m, m->dv);
3321 assert(m->dvsize == chunksize(m->dv));
3322 assert(m->dvsize >= MIN_CHUNK_SIZE);
3323 assert(bin_find(m, m->dv) == 0);
3324 }
3325
3326 if (m->top != 0) { /* check top chunk */
3327 do_check_top_chunk(m, m->top);
3328 /*assert(m->topsize == chunksize(m->top)); redundant */
3329 assert(m->topsize > 0);
3330 assert(bin_find(m, m->top) == 0);
3331 }
3332
3333 total = traverse_and_check(m);
3334 assert(total <= m->footprint);
3335 assert(m->footprint <= m->max_footprint);
3336 }
3337 #endif /* DEBUG */
3338
3339 /* ----------------------------- statistics ------------------------------ */
3340
3341 #if !NO_MALLINFO
internal_mallinfo(mstate m)3342 static struct mallinfo internal_mallinfo(mstate m) {
3343 struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
3344 ensure_initialization();
3345 if (!PREACTION(m)) {
3346 check_malloc_state(m);
3347 if (is_initialized(m)) {
3348 size_t nfree = SIZE_T_ONE; /* top always free */
3349 size_t mfree = m->topsize + TOP_FOOT_SIZE;
3350 size_t sum = mfree;
3351 msegmentptr s = &m->seg;
3352 while (s != 0) {
3353 mchunkptr q = align_as_chunk(s->base);
3354 while (segment_holds(s, q) &&
3355 q != m->top && q->head != FENCEPOST_HEAD) {
3356 size_t sz = chunksize(q);
3357 sum += sz;
3358 if (!is_inuse(q)) {
3359 mfree += sz;
3360 ++nfree;
3361 }
3362 q = next_chunk(q);
3363 }
3364 s = s->next;
3365 }
3366
3367 nm.arena = sum;
3368 nm.ordblks = nfree;
3369 nm.hblkhd = m->footprint - sum;
3370 nm.usmblks = m->max_footprint;
3371 nm.uordblks = m->footprint - mfree;
3372 nm.fordblks = mfree;
3373 nm.keepcost = m->topsize;
3374 }
3375
3376 POSTACTION(m);
3377 }
3378 return nm;
3379 }
3380 #endif /* !NO_MALLINFO */
3381
internal_malloc_stats(mstate m)3382 static void internal_malloc_stats(mstate m) {
3383 ensure_initialization();
3384 if (!PREACTION(m)) {
3385 size_t maxfp = 0;
3386 size_t fp = 0;
3387 size_t used = 0;
3388 check_malloc_state(m);
3389 if (is_initialized(m)) {
3390 msegmentptr s = &m->seg;
3391 maxfp = m->max_footprint;
3392 fp = m->footprint;
3393 used = fp - (m->topsize + TOP_FOOT_SIZE);
3394
3395 while (s != 0) {
3396 mchunkptr q = align_as_chunk(s->base);
3397 while (segment_holds(s, q) &&
3398 q != m->top && q->head != FENCEPOST_HEAD) {
3399 if (!is_inuse(q))
3400 used -= chunksize(q);
3401 q = next_chunk(q);
3402 }
3403 s = s->next;
3404 }
3405 }
3406
3407 fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
3408 fprintf(stderr, "system bytes = %10lu\n", (unsigned long)(fp));
3409 fprintf(stderr, "in use bytes = %10lu\n", (unsigned long)(used));
3410
3411 POSTACTION(m);
3412 }
3413 }
3414
3415 /* ----------------------- Operations on smallbins ----------------------- */
3416
3417 /*
3418 Various forms of linking and unlinking are defined as macros. Even
3419 the ones for trees, which are very long but have very short typical
3420 paths. This is ugly but reduces reliance on inlining support of
3421 compilers.
3422 */
3423
3424 /* Link a free chunk into a smallbin */
3425 #define insert_small_chunk(M, P, S) {\
3426 bindex_t I = (bindex_t)small_index(S);\
3427 mchunkptr B = smallbin_at(M, I);\
3428 mchunkptr F = B;\
3429 assert(S >= MIN_CHUNK_SIZE);\
3430 if (!smallmap_is_marked(M, I))\
3431 mark_smallmap(M, I);\
3432 else if (RTCHECK(ok_address(M, B->fd)))\
3433 F = B->fd;\
3434 else {\
3435 CORRUPTION_ERROR_ACTION(M);\
3436 }\
3437 B->fd = P;\
3438 F->bk = P;\
3439 P->fd = F;\
3440 P->bk = B;\
3441 }
3442
3443 /* Unlink a chunk from a smallbin */
3444 #define unlink_small_chunk(M, P, S) {\
3445 mchunkptr F = P->fd;\
3446 mchunkptr B = P->bk;\
3447 bindex_t I = small_index(S);\
3448 assert(P != B);\
3449 assert(P != F);\
3450 assert(chunksize(P) == small_index2size(I));\
3451 if (F == B)\
3452 clear_smallmap(M, I);\
3453 else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
3454 (B == smallbin_at(M,I) || ok_address(M, B)))) {\
3455 F->bk = B;\
3456 B->fd = F;\
3457 }\
3458 else {\
3459 CORRUPTION_ERROR_ACTION(M);\
3460 }\
3461 }
3462
3463 /* Unlink the first chunk from a smallbin */
3464 #define unlink_first_small_chunk(M, B, P, I) {\
3465 mchunkptr F = P->fd;\
3466 assert(P != B);\
3467 assert(P != F);\
3468 assert(chunksize(P) == small_index2size(I));\
3469 if (B == F)\
3470 clear_smallmap(M, I);\
3471 else if (RTCHECK(ok_address(M, F))) {\
3472 B->fd = F;\
3473 F->bk = B;\
3474 }\
3475 else {\
3476 CORRUPTION_ERROR_ACTION(M);\
3477 }\
3478 }
3479
3480
3481
3482 /* Replace dv node, binning the old one */
3483 /* Used only when dvsize known to be small */
3484 #define replace_dv(M, P, S) {\
3485 size_t DVS = M->dvsize;\
3486 if (DVS != 0) {\
3487 mchunkptr DV = M->dv;\
3488 assert(is_small(DVS));\
3489 insert_small_chunk(M, DV, DVS);\
3490 }\
3491 M->dvsize = S;\
3492 M->dv = P;\
3493 }
3494
3495 /* ------------------------- Operations on trees ------------------------- */
3496
3497 /* Insert chunk into tree */
3498 #define insert_large_chunk(M, X, S) {\
3499 tbinptr* H;\
3500 bindex_t I;\
3501 compute_tree_index(S, I);\
3502 H = treebin_at(M, I);\
3503 X->index = I;\
3504 X->child[0] = X->child[1] = 0;\
3505 if (!treemap_is_marked(M, I)) {\
3506 mark_treemap(M, I);\
3507 *H = X;\
3508 X->parent = (tchunkptr)H;\
3509 X->fd = X->bk = X;\
3510 }\
3511 else {\
3512 tchunkptr T = *H;\
3513 size_t K = S << leftshift_for_tree_index(I);\
3514 for (;;) {\
3515 if (chunksize(T) != S) {\
3516 tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
3517 K <<= 1;\
3518 if (*C != 0)\
3519 T = *C;\
3520 else if (RTCHECK(ok_address(M, C))) {\
3521 *C = X;\
3522 X->parent = T;\
3523 X->fd = X->bk = X;\
3524 break;\
3525 }\
3526 else {\
3527 CORRUPTION_ERROR_ACTION(M);\
3528 break;\
3529 }\
3530 }\
3531 else {\
3532 tchunkptr F = T->fd;\
3533 if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
3534 T->fd = F->bk = X;\
3535 X->fd = F;\
3536 X->bk = T;\
3537 X->parent = 0;\
3538 break;\
3539 }\
3540 else {\
3541 CORRUPTION_ERROR_ACTION(M);\
3542 break;\
3543 }\
3544 }\
3545 }\
3546 }\
3547 }
3548
3549 /*
3550 Unlink steps:
3551
3552 1. If x is a chained node, unlink it from its same-sized fd/bk links
3553 and choose its bk node as its replacement.
3554 2. If x was the last node of its size, but not a leaf node, it must
3555 be replaced with a leaf node (not merely one with an open left or
3556 right), to make sure that lefts and rights of descendents
3557 correspond properly to bit masks. We use the rightmost descendent
3558 of x. We could use any other leaf, but this is easy to locate and
3559 tends to counteract removal of leftmosts elsewhere, and so keeps
3560 paths shorter than minimally guaranteed. This doesn't loop much
3561 because on average a node in a tree is near the bottom.
3562 3. If x is the base of a chain (i.e., has parent links) relink
3563 x's parent and children to x's replacement (or null if none).
3564 */
3565
3566 #define unlink_large_chunk(M, X) {\
3567 tchunkptr XP = X->parent;\
3568 tchunkptr R;\
3569 if (X->bk != X) {\
3570 tchunkptr F = X->fd;\
3571 R = X->bk;\
3572 if (RTCHECK(ok_address(M, F))) {\
3573 F->bk = R;\
3574 R->fd = F;\
3575 }\
3576 else {\
3577 CORRUPTION_ERROR_ACTION(M);\
3578 }\
3579 }\
3580 else {\
3581 tchunkptr* RP;\
3582 if (((R = *(RP = &(X->child[1]))) != 0) ||\
3583 ((R = *(RP = &(X->child[0]))) != 0)) {\
3584 tchunkptr* CP;\
3585 while ((*(CP = &(R->child[1])) != 0) ||\
3586 (*(CP = &(R->child[0])) != 0)) {\
3587 R = *(RP = CP);\
3588 }\
3589 if (RTCHECK(ok_address(M, RP)))\
3590 *RP = 0;\
3591 else {\
3592 CORRUPTION_ERROR_ACTION(M);\
3593 }\
3594 }\
3595 }\
3596 if (XP != 0) {\
3597 tbinptr* H = treebin_at(M, X->index);\
3598 if (X == *H) {\
3599 if ((*H = R) == 0) \
3600 clear_treemap(M, X->index);\
3601 }\
3602 else if (RTCHECK(ok_address(M, XP))) {\
3603 if (XP->child[0] == X) \
3604 XP->child[0] = R;\
3605 else \
3606 XP->child[1] = R;\
3607 }\
3608 else\
3609 CORRUPTION_ERROR_ACTION(M);\
3610 if (R != 0) {\
3611 if (RTCHECK(ok_address(M, R))) {\
3612 tchunkptr C0, C1;\
3613 R->parent = XP;\
3614 if ((C0 = X->child[0]) != 0) {\
3615 if (RTCHECK(ok_address(M, C0))) {\
3616 R->child[0] = C0;\
3617 C0->parent = R;\
3618 }\
3619 else\
3620 CORRUPTION_ERROR_ACTION(M);\
3621 }\
3622 if ((C1 = X->child[1]) != 0) {\
3623 if (RTCHECK(ok_address(M, C1))) {\
3624 R->child[1] = C1;\
3625 C1->parent = R;\
3626 }\
3627 else\
3628 CORRUPTION_ERROR_ACTION(M);\
3629 }\
3630 }\
3631 else\
3632 CORRUPTION_ERROR_ACTION(M);\
3633 }\
3634 }\
3635 }
3636
3637 /* Relays to large vs small bin operations */
3638
3639 #define insert_chunk(M, P, S)\
3640 if (is_small(S)) insert_small_chunk(M, P, S)\
3641 else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
3642
3643
3644 #define unlink_chunk(M, P, S)\
3645 if (is_small(S)) unlink_small_chunk(M, P, S)\
3646 else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
3647
3648
3649 /* Relays to internal calls to malloc/free from realloc, memalign etc */
3650
3651 #if ONLY_MSPACES
3652 #define internal_malloc(m, b) mspace_malloc(m, b)
3653 #define internal_free(m, mem) mspace_free(m,mem);
3654 #else /* ONLY_MSPACES */
3655 #if MSPACES
3656 #define internal_malloc(m, b)\
3657 (m == gm)? dlmalloc(b) : mspace_malloc(m, b)
3658 #define internal_free(m, mem)\
3659 if (m == gm) dlfree(mem); else mspace_free(m,mem);
3660 #else /* MSPACES */
3661 #define internal_malloc(m, b) dlmalloc(b)
3662 #define internal_free(m, mem) dlfree(mem)
3663 #endif /* MSPACES */
3664 #endif /* ONLY_MSPACES */
3665
3666 /* ----------------------- Direct-mmapping chunks ----------------------- */
3667
3668 /*
3669 Directly mmapped chunks are set up with an offset to the start of
3670 the mmapped region stored in the prev_foot field of the chunk. This
3671 allows reconstruction of the required argument to MUNMAP when freed,
3672 and also allows adjustment of the returned chunk to meet alignment
3673 requirements (especially in memalign).
3674 */
3675
3676 /* Malloc using mmap */
mmap_alloc(mstate m,size_t nb)3677 static void* mmap_alloc(mstate m, size_t nb) {
3678 size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3679 if (mmsize > nb) { /* Check for wrap around 0 */
3680 char* mm = (char*)(CALL_DIRECT_MMAP(mmsize));
3681 if (mm != CMFAIL) {
3682 size_t offset = align_offset(chunk2mem(mm));
3683 size_t psize = mmsize - offset - MMAP_FOOT_PAD;
3684 mchunkptr p = (mchunkptr)(mm + offset);
3685 p->prev_foot = offset;
3686 p->head = psize;
3687 mark_inuse_foot(m, p, psize);
3688 chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
3689 chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
3690
3691 if (m->least_addr == 0 || mm < m->least_addr)
3692 m->least_addr = mm;
3693 if ((m->footprint += mmsize) > m->max_footprint)
3694 m->max_footprint = m->footprint;
3695 assert(is_aligned(chunk2mem(p)));
3696 check_mmapped_chunk(m, p);
3697 return chunk2mem(p);
3698 }
3699 }
3700 return 0;
3701 }
3702
3703 /* Realloc using mmap */
mmap_resize(mstate m,mchunkptr oldp,size_t nb)3704 static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) {
3705 size_t oldsize = chunksize(oldp);
3706 if (is_small(nb)) /* Can't shrink mmap regions below small size */
3707 return 0;
3708 /* Keep old chunk if big enough but not too big */
3709 if (oldsize >= nb + SIZE_T_SIZE &&
3710 (oldsize - nb) <= (mparams.granularity << 1))
3711 return oldp;
3712 else {
3713 size_t offset = oldp->prev_foot;
3714 size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
3715 size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3716 char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
3717 oldmmsize, newmmsize, 1);
3718 if (cp != CMFAIL) {
3719 mchunkptr newp = (mchunkptr)(cp + offset);
3720 size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
3721 newp->head = psize;
3722 mark_inuse_foot(m, newp, psize);
3723 chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
3724 chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
3725
3726 if (cp < m->least_addr)
3727 m->least_addr = cp;
3728 if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
3729 m->max_footprint = m->footprint;
3730 check_mmapped_chunk(m, newp);
3731 return newp;
3732 }
3733 }
3734 return 0;
3735 }
3736
3737 /* -------------------------- mspace management -------------------------- */
3738
3739 /* Initialize top chunk and its size */
init_top(mstate m,mchunkptr p,size_t psize)3740 static void init_top(mstate m, mchunkptr p, size_t psize) {
3741 /* Ensure alignment */
3742 size_t offset = align_offset(chunk2mem(p));
3743 p = (mchunkptr)((char*)p + offset);
3744 psize -= offset;
3745
3746 m->top = p;
3747 m->topsize = psize;
3748 p->head = psize | PINUSE_BIT;
3749 /* set size of fake trailing chunk holding overhead space only once */
3750 chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
3751 m->trim_check = mparams.trim_threshold; /* reset on each update */
3752 }
3753
3754 /* Initialize bins for a new mstate that is otherwise zeroed out */
init_bins(mstate m)3755 static void init_bins(mstate m) {
3756 /* Establish circular links for smallbins */
3757 bindex_t i;
3758 for (i = 0; i < NSMALLBINS; ++i) {
3759 sbinptr bin = smallbin_at(m,i);
3760 bin->fd = bin->bk = bin;
3761 }
3762 }
3763
3764 #if PROCEED_ON_ERROR
3765
3766 /* default corruption action */
reset_on_error(mstate m)3767 static void reset_on_error(mstate m) {
3768 int i;
3769 ++malloc_corruption_error_count;
3770 /* Reinitialize fields to forget about all memory */
3771 m->smallbins = m->treebins = 0;
3772 m->dvsize = m->topsize = 0;
3773 m->seg.base = 0;
3774 m->seg.size = 0;
3775 m->seg.next = 0;
3776 m->top = m->dv = 0;
3777 for (i = 0; i < NTREEBINS; ++i)
3778 *treebin_at(m, i) = 0;
3779 init_bins(m);
3780 }
3781 #endif /* PROCEED_ON_ERROR */
3782
3783 /* Allocate chunk and prepend remainder with chunk in successor base. */
prepend_alloc(mstate m,char * newbase,char * oldbase,size_t nb)3784 static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
3785 size_t nb) {
3786 mchunkptr p = align_as_chunk(newbase);
3787 mchunkptr oldfirst = align_as_chunk(oldbase);
3788 bindex_t psize = (bindex_t)((char*)oldfirst - (char*)p);
3789 mchunkptr q = chunk_plus_offset(p, nb);
3790 bindex_t qsize = psize - (bindex_t)nb;
3791 set_size_and_pinuse_of_inuse_chunk(m, p, nb);
3792
3793 assert((char*)oldfirst > (char*)q);
3794 assert(pinuse(oldfirst));
3795 assert(qsize >= MIN_CHUNK_SIZE);
3796
3797 /* consolidate remainder with first chunk of old base */
3798 if (oldfirst == m->top) {
3799 size_t tsize = m->topsize += qsize;
3800 m->top = q;
3801 q->head = tsize | PINUSE_BIT;
3802 check_top_chunk(m, q);
3803 }
3804 else if (oldfirst == m->dv) {
3805 size_t dsize = m->dvsize += qsize;
3806 m->dv = q;
3807 set_size_and_pinuse_of_free_chunk(q, dsize);
3808 }
3809 else {
3810 if (!is_inuse(oldfirst)) {
3811 bindex_t nsize = chunksize(oldfirst);
3812 unlink_chunk(m, oldfirst, nsize);
3813 oldfirst = chunk_plus_offset(oldfirst, nsize);
3814 qsize += nsize;
3815 }
3816 set_free_with_pinuse(q, qsize, oldfirst);
3817 insert_chunk(m, q, qsize);
3818 check_free_chunk(m, q);
3819 }
3820
3821 check_malloced_chunk(m, chunk2mem(p), nb);
3822 return chunk2mem(p);
3823 }
3824
3825 /* Add a segment to hold a new noncontiguous region */
add_segment(mstate m,char * tbase,size_t tsize,flag_t mmapped)3826 static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
3827 /* Determine locations and sizes of segment, fenceposts, old top */
3828 char* old_top = (char*)m->top;
3829 msegmentptr oldsp = segment_holding(m, old_top);
3830 char* old_end = oldsp->base + oldsp->size;
3831 size_t ssize = pad_request(sizeof(struct malloc_segment));
3832 char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3833 size_t offset = align_offset(chunk2mem(rawsp));
3834 char* asp = rawsp + offset;
3835 char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
3836 mchunkptr sp = (mchunkptr)csp;
3837 msegmentptr ss = (msegmentptr)(chunk2mem(sp));
3838 mchunkptr tnext = chunk_plus_offset(sp, ssize);
3839 mchunkptr p = tnext;
3840 int nfences = 0;
3841
3842 /* reset top to new space */
3843 init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
3844
3845 /* Set up segment record */
3846 assert(is_aligned(ss));
3847 set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
3848 *ss = m->seg; /* Push current record */
3849 m->seg.base = tbase;
3850 m->seg.size = tsize;
3851 m->seg.sflags = mmapped;
3852 m->seg.next = ss;
3853
3854 /* Insert trailing fenceposts */
3855 for (;;) {
3856 mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
3857 p->head = FENCEPOST_HEAD;
3858 ++nfences;
3859 if ((char*)(&(nextp->head)) < old_end)
3860 p = nextp;
3861 else
3862 break;
3863 }
3864 assert(nfences >= 2);
3865
3866 /* Insert the rest of old top into a bin as an ordinary free chunk */
3867 if (csp != old_top) {
3868 mchunkptr q = (mchunkptr)old_top;
3869 bindex_t psize = (bindex_t)(csp - old_top);
3870 mchunkptr tn = chunk_plus_offset(q, psize);
3871 set_free_with_pinuse(q, psize, tn);
3872 insert_chunk(m, q, psize);
3873 }
3874
3875 check_top_chunk(m, m->top);
3876 }
3877
3878 /* -------------------------- System allocation -------------------------- */
3879
3880 /* Get memory from system using MORECORE or MMAP */
sys_alloc(mstate m,size_t nb)3881 static void* sys_alloc(mstate m, size_t nb) {
3882 char* tbase = CMFAIL;
3883 size_t tsize = 0;
3884 flag_t mmap_flag = 0;
3885
3886 ensure_initialization();
3887
3888 /* Directly map large chunks, but only if already initialized */
3889 if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) {
3890 void* mem = mmap_alloc(m, nb);
3891 if (mem != 0)
3892 return mem;
3893 }
3894
3895 /*
3896 Try getting memory in any of three ways (in most-preferred to
3897 least-preferred order):
3898 1. A call to MORECORE that can normally contiguously extend memory.
3899 (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
3900 or main space is mmapped or a previous contiguous call failed)
3901 2. A call to MMAP new space (disabled if not HAVE_MMAP).
3902 Note that under the default settings, if MORECORE is unable to
3903 fulfill a request, and HAVE_MMAP is true, then mmap is
3904 used as a noncontiguous system allocator. This is a useful backup
3905 strategy for systems with holes in address spaces -- in this case
3906 sbrk cannot contiguously expand the heap, but mmap may be able to
3907 find space.
3908 3. A call to MORECORE that cannot usually contiguously extend memory.
3909 (disabled if not HAVE_MORECORE)
3910
3911 In all cases, we need to request enough bytes from system to ensure
3912 we can malloc nb bytes upon success, so pad with enough space for
3913 top_foot, plus alignment-pad to make sure we don't lose bytes if
3914 not on boundary, and round this up to a granularity unit.
3915 */
3916
3917 if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
3918 char* br = CMFAIL;
3919 msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
3920 size_t asize = 0;
3921 ACQUIRE_MALLOC_GLOBAL_LOCK();
3922
3923 if (ss == 0) { /* First time through or recovery */
3924 char* base = (char*)CALL_MORECORE(0);
3925 if (base != CMFAIL) {
3926 asize = granularity_align(nb + SYS_ALLOC_PADDING);
3927 /* Adjust to end on a page boundary */
3928 if (!is_page_aligned(base))
3929 asize += (page_align((size_t)base) - (size_t)base);
3930 /* Can't call MORECORE if size is negative when treated as signed */
3931 if (asize < HALF_MAX_SIZE_T &&
3932 (br = (char*)(CALL_MORECORE(asize))) == base) {
3933 tbase = base;
3934 tsize = asize;
3935 }
3936 }
3937 }
3938 else {
3939 /* Subtract out existing available top space from MORECORE request. */
3940 asize = granularity_align(nb - m->topsize + SYS_ALLOC_PADDING);
3941 /* Use mem here only if it did continuously extend old space */
3942 if (asize < HALF_MAX_SIZE_T &&
3943 (br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {
3944 tbase = br;
3945 tsize = asize;
3946 }
3947 }
3948
3949 if (tbase == CMFAIL) { /* Cope with partial failure */
3950 if (br != CMFAIL) { /* Try to use/extend the space we did get */
3951 if (asize < HALF_MAX_SIZE_T &&
3952 asize < nb + SYS_ALLOC_PADDING) {
3953 size_t esize = granularity_align(nb + SYS_ALLOC_PADDING - asize);
3954 if (esize < HALF_MAX_SIZE_T) {
3955 char* end = (char*)CALL_MORECORE(esize);
3956 if (end != CMFAIL)
3957 asize += esize;
3958 else { /* Can't use; try to release */
3959 (void) CALL_MORECORE(-asize);
3960 br = CMFAIL;
3961 }
3962 }
3963 }
3964 }
3965 if (br != CMFAIL) { /* Use the space we did get */
3966 tbase = br;
3967 tsize = asize;
3968 }
3969 else
3970 disable_contiguous(m); /* Don't try contiguous path in the future */
3971 }
3972
3973 RELEASE_MALLOC_GLOBAL_LOCK();
3974 }
3975
3976 if (HAVE_MMAP && tbase == CMFAIL) { /* Try MMAP */
3977 size_t rsize = granularity_align(nb + SYS_ALLOC_PADDING);
3978 if (rsize > nb) { /* Fail if wraps around zero */
3979 char* mp = (char*)(CALL_MMAP(rsize));
3980 if (mp != CMFAIL) {
3981 tbase = mp;
3982 tsize = rsize;
3983 mmap_flag = USE_MMAP_BIT;
3984 }
3985 }
3986 }
3987
3988 if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
3989 size_t asize = granularity_align(nb + SYS_ALLOC_PADDING);
3990 if (asize < HALF_MAX_SIZE_T) {
3991 char* br = CMFAIL;
3992 char* end = CMFAIL;
3993 ACQUIRE_MALLOC_GLOBAL_LOCK();
3994 br = (char*)(CALL_MORECORE(asize));
3995 end = (char*)(CALL_MORECORE(0));
3996 RELEASE_MALLOC_GLOBAL_LOCK();
3997 if (br != CMFAIL && end != CMFAIL && br < end) {
3998 size_t ssize = end - br;
3999 if (ssize > nb + TOP_FOOT_SIZE) {
4000 tbase = br;
4001 tsize = ssize;
4002 }
4003 }
4004 }
4005 }
4006
4007 if (tbase != CMFAIL) {
4008
4009 if ((m->footprint += tsize) > m->max_footprint)
4010 m->max_footprint = m->footprint;
4011
4012 if (!is_initialized(m)) { /* first-time initialization */
4013 if (m->least_addr == 0 || tbase < m->least_addr)
4014 m->least_addr = tbase;
4015 m->seg.base = tbase;
4016 m->seg.size = tsize;
4017 m->seg.sflags = mmap_flag;
4018 m->magic = mparams.magic;
4019 m->release_checks = MAX_RELEASE_CHECK_RATE;
4020 init_bins(m);
4021 #if !ONLY_MSPACES
4022 if (is_global(m))
4023 init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
4024 else
4025 #endif
4026 {
4027 /* Offset top by embedded malloc_state */
4028 mchunkptr mn = next_chunk(mem2chunk(m));
4029 init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
4030 }
4031 }
4032
4033 else {
4034 /* Try to merge with an existing segment */
4035 msegmentptr sp = &m->seg;
4036 /* Only consider most recent segment if traversal suppressed */
4037 while (sp != 0 && tbase != sp->base + sp->size)
4038 sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
4039 if (sp != 0 &&
4040 !is_extern_segment(sp) &&
4041 (sp->sflags & USE_MMAP_BIT) == mmap_flag &&
4042 segment_holds(sp, m->top)) { /* append */
4043 sp->size += tsize;
4044 init_top(m, m->top, m->topsize + tsize);
4045 }
4046 else {
4047 if (tbase < m->least_addr)
4048 m->least_addr = tbase;
4049 sp = &m->seg;
4050 while (sp != 0 && sp->base != tbase + tsize)
4051 sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
4052 if (sp != 0 &&
4053 !is_extern_segment(sp) &&
4054 (sp->sflags & USE_MMAP_BIT) == mmap_flag) {
4055 char* oldbase = sp->base;
4056 sp->base = tbase;
4057 sp->size += tsize;
4058 return prepend_alloc(m, tbase, oldbase, nb);
4059 }
4060 else
4061 add_segment(m, tbase, tsize, mmap_flag);
4062 }
4063 }
4064
4065 if (nb < m->topsize) { /* Allocate from new or extended top space */
4066 size_t rsize = m->topsize -= nb;
4067 mchunkptr p = m->top;
4068 mchunkptr r = m->top = chunk_plus_offset(p, nb);
4069 r->head = rsize | PINUSE_BIT;
4070 set_size_and_pinuse_of_inuse_chunk(m, p, nb);
4071 check_top_chunk(m, m->top);
4072 check_malloced_chunk(m, chunk2mem(p), nb);
4073 return chunk2mem(p);
4074 }
4075 }
4076
4077 MALLOC_FAILURE_ACTION;
4078 return 0;
4079 }
4080
4081 /* ----------------------- system deallocation -------------------------- */
4082
4083 /* Unmap and unlink any mmapped segments that don't contain used chunks */
release_unused_segments(mstate m)4084 static size_t release_unused_segments(mstate m) {
4085 size_t released = 0;
4086 int nsegs = 0;
4087 msegmentptr pred = &m->seg;
4088 msegmentptr sp = pred->next;
4089 while (sp != 0) {
4090 char* base = sp->base;
4091 size_t size = sp->size;
4092 msegmentptr next = sp->next;
4093 ++nsegs;
4094 if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
4095 mchunkptr p = align_as_chunk(base);
4096 size_t psize = chunksize(p);
4097 /* Can unmap if first chunk holds entire segment and not pinned */
4098 if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
4099 tchunkptr tp = (tchunkptr)p;
4100 assert(segment_holds(sp, (char*)sp));
4101 if (p == m->dv) {
4102 m->dv = 0;
4103 m->dvsize = 0;
4104 }
4105 else {
4106 unlink_large_chunk(m, tp);
4107 }
4108 if (CALL_MUNMAP(base, size) == 0) {
4109 released += size;
4110 m->footprint -= size;
4111 /* unlink obsoleted record */
4112 sp = pred;
4113 sp->next = next;
4114 }
4115 else { /* back out if cannot unmap */
4116 insert_large_chunk(m, tp, psize);
4117 }
4118 }
4119 }
4120 if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */
4121 break;
4122 pred = sp;
4123 sp = next;
4124 }
4125 /* Reset check counter */
4126 m->release_checks = ((nsegs > MAX_RELEASE_CHECK_RATE)?
4127 nsegs : MAX_RELEASE_CHECK_RATE);
4128 return released;
4129 }
4130
sys_trim(mstate m,size_t pad)4131 static int sys_trim(mstate m, size_t pad) {
4132 size_t released = 0;
4133 ensure_initialization();
4134 if (pad < MAX_REQUEST && is_initialized(m)) {
4135 pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
4136
4137 if (m->topsize > pad) {
4138 /* Shrink top space in granularity-size units, keeping at least one */
4139 size_t unit = mparams.granularity;
4140 size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
4141 SIZE_T_ONE) * unit;
4142 msegmentptr sp = segment_holding(m, (char*)m->top);
4143
4144 if (!is_extern_segment(sp)) {
4145 if (is_mmapped_segment(sp)) {
4146 if (HAVE_MMAP &&
4147 sp->size >= extra &&
4148 !has_segment_link(m, sp)) { /* can't shrink if pinned */
4149 size_t newsize = sp->size - extra;
4150 /* Prefer mremap, fall back to munmap */
4151 if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
4152 (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
4153 released = extra;
4154 }
4155 }
4156 }
4157 else if (HAVE_MORECORE) {
4158 if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
4159 extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
4160 ACQUIRE_MALLOC_GLOBAL_LOCK();
4161 {
4162 /* Make sure end of memory is where we last set it. */
4163 char* old_br = (char*)(CALL_MORECORE(0));
4164 if (old_br == sp->base + sp->size) {
4165 char* rel_br = (char*)(CALL_MORECORE(-extra));
4166 char* new_br = (char*)(CALL_MORECORE(0));
4167 if (rel_br != CMFAIL && new_br < old_br)
4168 released = old_br - new_br;
4169 }
4170 }
4171 RELEASE_MALLOC_GLOBAL_LOCK();
4172 }
4173 }
4174
4175 if (released != 0) {
4176 sp->size -= released;
4177 m->footprint -= released;
4178 init_top(m, m->top, m->topsize - released);
4179 check_top_chunk(m, m->top);
4180 }
4181 }
4182
4183 /* Unmap any unused mmapped segments */
4184 if (HAVE_MMAP)
4185 released += release_unused_segments(m);
4186
4187 /* On failure, disable autotrim to avoid repeated failed future calls */
4188 if (released == 0 && m->topsize > m->trim_check)
4189 m->trim_check = MAX_SIZE_T;
4190 }
4191
4192 return (released != 0)? 1 : 0;
4193 }
4194
4195
4196 /* ---------------------------- malloc support --------------------------- */
4197
4198 /* allocate a large request from the best fitting chunk in a treebin */
tmalloc_large(mstate m,size_t nb)4199 static void* tmalloc_large(mstate m, size_t nb) {
4200 tchunkptr v = 0;
4201 size_t rsize = -nb; /* Unsigned negation */
4202 tchunkptr t;
4203 bindex_t idx;
4204 compute_tree_index(nb, idx);
4205 if ((t = *treebin_at(m, idx)) != 0) {
4206 /* Traverse tree for this bin looking for node with size == nb */
4207 size_t sizebits = nb << leftshift_for_tree_index(idx);
4208 tchunkptr rst = 0; /* The deepest untaken right subtree */
4209 for (;;) {
4210 tchunkptr rt;
4211 size_t trem = chunksize(t) - nb;
4212 if (trem < rsize) {
4213 v = t;
4214 if ((rsize = trem) == 0)
4215 break;
4216 }
4217 rt = t->child[1];
4218 t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
4219 if (rt != 0 && rt != t)
4220 rst = rt;
4221 if (t == 0) {
4222 t = rst; /* set t to least subtree holding sizes > nb */
4223 break;
4224 }
4225 sizebits <<= 1;
4226 }
4227 }
4228 if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
4229 binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
4230 if (leftbits != 0) {
4231 bindex_t i;
4232 binmap_t leastbit = least_bit(leftbits);
4233 compute_bit2idx(leastbit, i);
4234 t = *treebin_at(m, i);
4235 }
4236 }
4237
4238 while (t != 0) { /* find smallest of tree or subtree */
4239 size_t trem = chunksize(t) - nb;
4240 if (trem < rsize) {
4241 rsize = trem;
4242 v = t;
4243 }
4244 t = leftmost_child(t);
4245 }
4246
4247 /* If dv is a better fit, return 0 so malloc will use it */
4248 if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
4249 if (RTCHECK(ok_address(m, v))) { /* split */
4250 mchunkptr r = chunk_plus_offset(v, nb);
4251 assert(chunksize(v) == rsize + nb);
4252 if (RTCHECK(ok_next(v, r))) {
4253 unlink_large_chunk(m, v);
4254 if (rsize < MIN_CHUNK_SIZE)
4255 set_inuse_and_pinuse(m, v, (rsize + nb));
4256 else {
4257 set_size_and_pinuse_of_inuse_chunk(m, v, nb);
4258 set_size_and_pinuse_of_free_chunk(r, rsize);
4259 insert_chunk(m, r, rsize);
4260 }
4261 return chunk2mem(v);
4262 }
4263 }
4264 CORRUPTION_ERROR_ACTION(m);
4265 }
4266 return 0;
4267 }
4268
4269 /* allocate a small request from the best fitting chunk in a treebin */
tmalloc_small(mstate m,size_t nb)4270 static void* tmalloc_small(mstate m, size_t nb) {
4271 tchunkptr t, v;
4272 bindex_t rsize;
4273 bindex_t i;
4274 binmap_t leastbit = least_bit(m->treemap);
4275 compute_bit2idx(leastbit, i);
4276 v = t = *treebin_at(m, i);
4277 rsize = (bindex_t)(chunksize(t) - nb);
4278
4279 while ((t = leftmost_child(t)) != 0) {
4280 bindex_t trem = chunksize(t) - (bindex_t)nb;
4281 if (trem < rsize) {
4282 rsize = trem;
4283 v = t;
4284 }
4285 }
4286
4287 if (RTCHECK(ok_address(m, v))) {
4288 mchunkptr r = chunk_plus_offset(v, nb);
4289 assert(chunksize(v) == rsize + nb);
4290 if (RTCHECK(ok_next(v, r))) {
4291 unlink_large_chunk(m, v);
4292 if (rsize < MIN_CHUNK_SIZE)
4293 set_inuse_and_pinuse(m, v, (rsize + nb));
4294 else {
4295 set_size_and_pinuse_of_inuse_chunk(m, v, nb);
4296 set_size_and_pinuse_of_free_chunk(r, rsize);
4297 replace_dv(m, r, rsize);
4298 }
4299 return chunk2mem(v);
4300 }
4301 }
4302
4303 CORRUPTION_ERROR_ACTION(m);
4304 return 0;
4305 }
4306
4307 /* --------------------------- realloc support --------------------------- */
4308
internal_realloc(mstate m,void * oldmem,size_t bytes)4309 static void* internal_realloc(mstate m, void* oldmem, size_t bytes) {
4310 if (bytes >= MAX_REQUEST) {
4311 MALLOC_FAILURE_ACTION;
4312 return 0;
4313 }
4314 if (!PREACTION(m)) {
4315 mchunkptr oldp = mem2chunk(oldmem);
4316 size_t oldsize = chunksize(oldp);
4317 mchunkptr next = chunk_plus_offset(oldp, oldsize);
4318 mchunkptr newp = 0;
4319 void* extra = 0;
4320
4321 /* Try to either shrink or extend into top. Else malloc-copy-free */
4322
4323 if (RTCHECK(ok_address(m, oldp) && ok_inuse(oldp) &&
4324 ok_next(oldp, next) && ok_pinuse(next))) {
4325 size_t nb = request2size(bytes);
4326 if (is_mmapped(oldp))
4327 newp = mmap_resize(m, oldp, nb);
4328 else if (oldsize >= nb) { /* already big enough */
4329 size_t rsize = oldsize - nb;
4330 newp = oldp;
4331 if (rsize >= MIN_CHUNK_SIZE) {
4332 mchunkptr remainder = chunk_plus_offset(newp, nb);
4333 set_inuse(m, newp, nb);
4334 set_inuse_and_pinuse(m, remainder, rsize);
4335 extra = chunk2mem(remainder);
4336 }
4337 }
4338 else if (next == m->top && oldsize + m->topsize > nb) {
4339 /* Expand into top */
4340 size_t newsize = oldsize + m->topsize;
4341 size_t newtopsize = newsize - nb;
4342 mchunkptr newtop = chunk_plus_offset(oldp, nb);
4343 set_inuse(m, oldp, nb);
4344 newtop->head = newtopsize |PINUSE_BIT;
4345 m->top = newtop;
4346 m->topsize = newtopsize;
4347 newp = oldp;
4348 }
4349 }
4350 else {
4351 USAGE_ERROR_ACTION(m, oldmem);
4352 POSTACTION(m);
4353 return 0;
4354 }
4355 #if DEBUG
4356 if (newp != 0) {
4357 check_inuse_chunk(m, newp); /* Check requires lock */
4358 }
4359 #endif
4360
4361 POSTACTION(m);
4362
4363 if (newp != 0) {
4364 if (extra != 0) {
4365 internal_free(m, extra);
4366 }
4367 return chunk2mem(newp);
4368 }
4369 else {
4370 void* newmem = internal_malloc(m, bytes);
4371 if (newmem != 0) {
4372 size_t oc = oldsize - overhead_for(oldp);
4373 memcpy(newmem, oldmem, (oc < bytes)? oc : bytes);
4374 internal_free(m, oldmem);
4375 }
4376 return newmem;
4377 }
4378 }
4379 return 0;
4380 }
4381
4382 /* --------------------------- memalign support -------------------------- */
4383
internal_memalign(mstate m,size_t alignment,size_t bytes)4384 static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
4385 if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */
4386 return internal_malloc(m, bytes);
4387 if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
4388 alignment = MIN_CHUNK_SIZE;
4389 if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
4390 size_t a = MALLOC_ALIGNMENT << 1;
4391 while (a < alignment) a <<= 1;
4392 alignment = a;
4393 }
4394
4395 if (bytes >= MAX_REQUEST - alignment) {
4396 if (m != 0) { /* Test isn't needed but avoids compiler warning */
4397 MALLOC_FAILURE_ACTION;
4398 }
4399 }
4400 else {
4401 size_t nb = request2size(bytes);
4402 size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
4403 char* mem = (char*)internal_malloc(m, req);
4404 if (mem != 0) {
4405 void* leader = 0;
4406 void* trailer = 0;
4407 mchunkptr p = mem2chunk(mem);
4408
4409 if (PREACTION(m)) return 0;
4410 if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */
4411 /*
4412 Find an aligned spot inside chunk. Since we need to give
4413 back leading space in a chunk of at least MIN_CHUNK_SIZE, if
4414 the first calculation places us at a spot with less than
4415 MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
4416 We've allocated enough total room so that this is always
4417 possible.
4418 */
4419 char* br = (char*)mem2chunk((size_t)(((size_t)(mem +
4420 alignment -
4421 SIZE_T_ONE)) &
4422 -alignment));
4423 char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
4424 br : br+alignment;
4425 mchunkptr newp = (mchunkptr)pos;
4426 size_t leadsize = pos - (char*)(p);
4427 size_t newsize = chunksize(p) - leadsize;
4428
4429 if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */
4430 newp->prev_foot = p->prev_foot + leadsize;
4431 newp->head = newsize;
4432 }
4433 else { /* Otherwise, give back leader, use the rest */
4434 set_inuse(m, newp, newsize);
4435 set_inuse(m, p, leadsize);
4436 leader = chunk2mem(p);
4437 }
4438 p = newp;
4439 }
4440
4441 /* Give back spare room at the end */
4442 if (!is_mmapped(p)) {
4443 size_t size = chunksize(p);
4444 if (size > nb + MIN_CHUNK_SIZE) {
4445 size_t remainder_size = size - nb;
4446 mchunkptr remainder = chunk_plus_offset(p, nb);
4447 set_inuse(m, p, nb);
4448 set_inuse(m, remainder, remainder_size);
4449 trailer = chunk2mem(remainder);
4450 }
4451 }
4452
4453 assert (chunksize(p) >= nb);
4454 assert((((size_t)(chunk2mem(p))) % alignment) == 0);
4455 check_inuse_chunk(m, p);
4456 POSTACTION(m);
4457 if (leader != 0) {
4458 internal_free(m, leader);
4459 }
4460 if (trailer != 0) {
4461 internal_free(m, trailer);
4462 }
4463 return chunk2mem(p);
4464 }
4465 }
4466 return 0;
4467 }
4468
4469 /* ------------------------ comalloc/coalloc support --------------------- */
4470
ialloc(mstate m,size_t n_elements,size_t * sizes,int opts,void * chunks[])4471 static void** ialloc(mstate m,
4472 size_t n_elements,
4473 size_t* sizes,
4474 int opts,
4475 void* chunks[]) {
4476 /*
4477 This provides common support for independent_X routines, handling
4478 all of the combinations that can result.
4479
4480 The opts arg has:
4481 bit 0 set if all elements are same size (using sizes[0])
4482 bit 1 set if elements should be zeroed
4483 */
4484
4485 size_t element_size; /* chunksize of each element, if all same */
4486 size_t contents_size; /* total size of elements */
4487 size_t array_size; /* request size of pointer array */
4488 void* mem; /* malloced aggregate space */
4489 mchunkptr p; /* corresponding chunk */
4490 size_t remainder_size; /* remaining bytes while splitting */
4491 void** marray; /* either "chunks" or malloced ptr array */
4492 flag_t was_enabled; /* to disable mmap */
4493 size_t size;
4494 size_t i;
4495
4496 ensure_initialization();
4497 /* compute array length, if needed */
4498 if (chunks != 0) {
4499 if (n_elements == 0)
4500 return chunks; /* nothing to do */
4501 marray = chunks;
4502 array_size = 0;
4503 }
4504 else {
4505 /* if empty req, must still return chunk representing empty array */
4506 if (n_elements == 0)
4507 return (void**)internal_malloc(m, 0);
4508 marray = 0;
4509 array_size = request2size(n_elements * (sizeof(void*)));
4510 }
4511
4512 /* compute total element size */
4513 if (opts & 0x1) { /* all-same-size */
4514 element_size = request2size(*sizes);
4515 contents_size = n_elements * element_size;
4516 }
4517 else { /* add up all the sizes */
4518 element_size = 0;
4519 contents_size = 0;
4520 for (i = 0; i != n_elements; ++i)
4521 contents_size += request2size(sizes[i]);
4522 }
4523
4524 size = contents_size + array_size;
4525
4526 /*
4527 Allocate the aggregate chunk. First disable direct-mmapping so
4528 malloc won't use it, since we would not be able to later
4529 free/realloc space internal to a segregated mmap region.
4530 */
4531 was_enabled = use_mmap(m);
4532 disable_mmap(m);
4533 mem = internal_malloc(m, size - CHUNK_OVERHEAD);
4534 if (was_enabled)
4535 enable_mmap(m);
4536 if (mem == 0)
4537 return 0;
4538
4539 if (PREACTION(m)) return 0;
4540 p = mem2chunk(mem);
4541 remainder_size = chunksize(p);
4542
4543 assert(!is_mmapped(p));
4544
4545 if (opts & 0x2) { /* optionally clear the elements */
4546 memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);
4547 }
4548
4549 /* If not provided, allocate the pointer array as final part of chunk */
4550 if (marray == 0) {
4551 mchunkptr array_chunk; /* chunk for malloced ptr array */
4552 size_t array_chunk_size;
4553 array_chunk = chunk_plus_offset(p, contents_size);
4554 array_chunk_size = remainder_size - contents_size;
4555 marray = (void**) (chunk2mem(array_chunk));
4556 set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);
4557 remainder_size = contents_size;
4558 }
4559
4560 /* split out elements */
4561 for (i = 0; ; ++i) {
4562 marray[i] = chunk2mem(p);
4563 if (i != n_elements-1) {
4564 if (element_size != 0)
4565 size = element_size;
4566 else
4567 size = request2size(sizes[i]);
4568 remainder_size -= size;
4569 set_size_and_pinuse_of_inuse_chunk(m, p, size);
4570 p = chunk_plus_offset(p, size);
4571 }
4572 else { /* the final element absorbs any overallocation slop */
4573 set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);
4574 break;
4575 }
4576 }
4577
4578 #if DEBUG
4579 if (marray != chunks) {
4580 /* final element must have exactly exhausted chunk */
4581 if (element_size != 0) {
4582 assert(remainder_size == element_size);
4583 }
4584 else {
4585 assert(remainder_size == request2size(sizes[i]));
4586 }
4587 check_inuse_chunk(m, mem2chunk(marray));
4588 }
4589 for (i = 0; i != n_elements; ++i)
4590 check_inuse_chunk(m, mem2chunk(marray[i]));
4591
4592 #endif /* DEBUG */
4593
4594 POSTACTION(m);
4595 return marray;
4596 }
4597
4598
4599 /* -------------------------- public routines ---------------------------- */
4600
4601 #if !ONLY_MSPACES
4602
dlmalloc(size_t bytes)4603 void* dlmalloc(size_t bytes) {
4604 /*
4605 Basic algorithm:
4606 If a small request (< 256 bytes minus per-chunk overhead):
4607 1. If one exists, use a remainderless chunk in associated smallbin.
4608 (Remainderless means that there are too few excess bytes to
4609 represent as a chunk.)
4610 2. If it is big enough, use the dv chunk, which is normally the
4611 chunk adjacent to the one used for the most recent small request.
4612 3. If one exists, split the smallest available chunk in a bin,
4613 saving remainder in dv.
4614 4. If it is big enough, use the top chunk.
4615 5. If available, get memory from system and use it
4616 Otherwise, for a large request:
4617 1. Find the smallest available binned chunk that fits, and use it
4618 if it is better fitting than dv chunk, splitting if necessary.
4619 2. If better fitting than any binned chunk, use the dv chunk.
4620 3. If it is big enough, use the top chunk.
4621 4. If request size >= mmap threshold, try to directly mmap this chunk.
4622 5. If available, get memory from system and use it
4623
4624 The ugly goto's here ensure that postaction occurs along all paths.
4625 */
4626
4627 #if USE_LOCKS
4628 ensure_initialization(); /* initialize in sys_alloc if not using locks */
4629 #endif
4630
4631 if (!PREACTION(gm)) {
4632 void* mem;
4633 bindex_t nb;
4634 if (bytes <= MAX_SMALL_REQUEST) {
4635 bindex_t idx;
4636 binmap_t smallbits;
4637 nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
4638 idx = small_index(nb);
4639 smallbits = gm->smallmap >> idx;
4640
4641 if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
4642 mchunkptr b, p;
4643 idx += ~smallbits & 1; /* Uses next bin if idx empty */
4644 b = smallbin_at(gm, idx);
4645 p = b->fd;
4646 assert(chunksize(p) == small_index2size(idx));
4647 unlink_first_small_chunk(gm, b, p, idx);
4648 set_inuse_and_pinuse(gm, p, small_index2size(idx));
4649 mem = chunk2mem(p);
4650 check_malloced_chunk(gm, mem, nb);
4651 goto postaction;
4652 }
4653
4654 else if (nb > gm->dvsize) {
4655 if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
4656 mchunkptr b, p, r;
4657 bindex_t rsize;
4658 bindex_t i;
4659 binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4660 binmap_t leastbit = least_bit(leftbits);
4661 compute_bit2idx(leastbit, i);
4662 b = smallbin_at(gm, i);
4663 p = b->fd;
4664 assert(chunksize(p) == small_index2size(i));
4665 unlink_first_small_chunk(gm, b, p, i);
4666 rsize = small_index2size(i) - nb;
4667 /* Fit here cannot be remainderless if 4byte sizes */
4668 if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4669 set_inuse_and_pinuse(gm, p, small_index2size(i));
4670 else {
4671 set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4672 r = chunk_plus_offset(p, nb);
4673 set_size_and_pinuse_of_free_chunk(r, rsize);
4674 replace_dv(gm, r, rsize);
4675 }
4676 mem = chunk2mem(p);
4677 check_malloced_chunk(gm, mem, nb);
4678 goto postaction;
4679 }
4680
4681 else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
4682 check_malloced_chunk(gm, mem, nb);
4683 goto postaction;
4684 }
4685 }
4686 }
4687 else if (bytes >= MAX_REQUEST)
4688 nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
4689 else {
4690 nb = pad_request(bytes);
4691 if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
4692 check_malloced_chunk(gm, mem, nb);
4693 goto postaction;
4694 }
4695 }
4696
4697 if (nb <= gm->dvsize) {
4698 size_t rsize = gm->dvsize - nb;
4699 mchunkptr p = gm->dv;
4700 if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4701 mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
4702 gm->dvsize = rsize;
4703 set_size_and_pinuse_of_free_chunk(r, rsize);
4704 set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4705 }
4706 else { /* exhaust dv */
4707 size_t dvs = gm->dvsize;
4708 gm->dvsize = 0;
4709 gm->dv = 0;
4710 set_inuse_and_pinuse(gm, p, dvs);
4711 }
4712 mem = chunk2mem(p);
4713 check_malloced_chunk(gm, mem, nb);
4714 goto postaction;
4715 }
4716
4717 else if (nb < gm->topsize) { /* Split top */
4718 size_t rsize = gm->topsize -= nb;
4719 mchunkptr p = gm->top;
4720 mchunkptr r = gm->top = chunk_plus_offset(p, nb);
4721 r->head = rsize | PINUSE_BIT;
4722 set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4723 mem = chunk2mem(p);
4724 check_top_chunk(gm, gm->top);
4725 check_malloced_chunk(gm, mem, nb);
4726 goto postaction;
4727 }
4728
4729 mem = sys_alloc(gm, nb);
4730
4731 postaction:
4732 POSTACTION(gm);
4733 return mem;
4734 }
4735
4736 return 0;
4737 }
4738
dlfree(void * mem)4739 void dlfree(void* mem) {
4740 /*
4741 Consolidate freed chunks with preceeding or succeeding bordering
4742 free chunks, if they exist, and then place in a bin. Intermixed
4743 with special cases for top, dv, mmapped chunks, and usage errors.
4744 */
4745
4746 if (mem != 0) {
4747 mchunkptr p = mem2chunk(mem);
4748 #if FOOTERS
4749 mstate fm = get_mstate_for(p);
4750 if (!ok_magic(fm)) {
4751 USAGE_ERROR_ACTION(fm, p);
4752 return;
4753 }
4754 #else /* FOOTERS */
4755 #define fm gm
4756 #endif /* FOOTERS */
4757 if (!PREACTION(fm)) {
4758 check_inuse_chunk(fm, p);
4759 if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
4760 bindex_t psize = chunksize(p);
4761 mchunkptr next = chunk_plus_offset(p, psize);
4762 if (!pinuse(p)) {
4763 bindex_t prevsize = (bindex_t)p->prev_foot;
4764 if (is_mmapped(p)) {
4765 psize += prevsize + MMAP_FOOT_PAD;
4766 if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4767 fm->footprint -= psize;
4768 goto postaction;
4769 }
4770 else {
4771 mchunkptr prev = chunk_minus_offset(p, prevsize);
4772 psize += prevsize;
4773 p = prev;
4774 if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4775 if (p != fm->dv) {
4776 unlink_chunk(fm, p, prevsize);
4777 }
4778 else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4779 fm->dvsize = psize;
4780 set_free_with_pinuse(p, psize, next);
4781 goto postaction;
4782 }
4783 }
4784 else
4785 goto erroraction;
4786 }
4787 }
4788
4789 if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
4790 if (!cinuse(next)) { /* consolidate forward */
4791 if (next == fm->top) {
4792 size_t tsize = fm->topsize += psize;
4793 fm->top = p;
4794 p->head = tsize | PINUSE_BIT;
4795 if (p == fm->dv) {
4796 fm->dv = 0;
4797 fm->dvsize = 0;
4798 }
4799 if (should_trim(fm, tsize))
4800 sys_trim(fm, 0);
4801 goto postaction;
4802 }
4803 else if (next == fm->dv) {
4804 size_t dsize = fm->dvsize += psize;
4805 fm->dv = p;
4806 set_size_and_pinuse_of_free_chunk(p, dsize);
4807 goto postaction;
4808 }
4809 else {
4810 bindex_t nsize = chunksize(next);
4811 psize += nsize;
4812 unlink_chunk(fm, next, nsize);
4813 set_size_and_pinuse_of_free_chunk(p, psize);
4814 if (p == fm->dv) {
4815 fm->dvsize = psize;
4816 goto postaction;
4817 }
4818 }
4819 }
4820 else
4821 set_free_with_pinuse(p, psize, next);
4822
4823 if (is_small(psize)) {
4824 insert_small_chunk(fm, p, psize);
4825 check_free_chunk(fm, p);
4826 }
4827 else {
4828 tchunkptr tp = (tchunkptr)p;
4829 insert_large_chunk(fm, tp, psize);
4830 check_free_chunk(fm, p);
4831 if (--fm->release_checks == 0)
4832 release_unused_segments(fm);
4833 }
4834 goto postaction;
4835 }
4836 }
4837 erroraction:
4838 USAGE_ERROR_ACTION(fm, p);
4839 postaction:
4840 POSTACTION(fm);
4841 }
4842 }
4843 #if !FOOTERS
4844 #undef fm
4845 #endif /* FOOTERS */
4846 }
4847
dlcalloc(size_t n_elements,size_t elem_size)4848 void* dlcalloc(size_t n_elements, size_t elem_size) {
4849 void* mem;
4850 size_t req = 0;
4851 if (n_elements != 0) {
4852 req = n_elements * elem_size;
4853 if (((n_elements | elem_size) & ~(size_t)0xffff) &&
4854 (req / n_elements != elem_size))
4855 req = MAX_SIZE_T; /* force downstream failure on overflow */
4856 }
4857 mem = dlmalloc(req);
4858 if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
4859 memset(mem, 0, req);
4860 return mem;
4861 }
4862
dlrealloc(void * oldmem,size_t bytes)4863 void* dlrealloc(void* oldmem, size_t bytes) {
4864 if (oldmem == 0)
4865 return dlmalloc(bytes);
4866 #ifdef REALLOC_ZERO_BYTES_FREES
4867 if (bytes == 0) {
4868 dlfree(oldmem);
4869 return 0;
4870 }
4871 #endif /* REALLOC_ZERO_BYTES_FREES */
4872 else {
4873 #if ! FOOTERS
4874 mstate m = gm;
4875 #else /* FOOTERS */
4876 mstate m = get_mstate_for(mem2chunk(oldmem));
4877 if (!ok_magic(m)) {
4878 USAGE_ERROR_ACTION(m, oldmem);
4879 return 0;
4880 }
4881 #endif /* FOOTERS */
4882 return internal_realloc(m, oldmem, bytes);
4883 }
4884 }
4885
dlmemalign(size_t alignment,size_t bytes)4886 void* dlmemalign(size_t alignment, size_t bytes) {
4887 return internal_memalign(gm, alignment, bytes);
4888 }
4889
dlindependent_calloc(size_t n_elements,size_t elem_size,void * chunks[])4890 void** dlindependent_calloc(size_t n_elements, size_t elem_size,
4891 void* chunks[]) {
4892 size_t sz = elem_size; /* serves as 1-element array */
4893 return ialloc(gm, n_elements, &sz, 3, chunks);
4894 }
4895
dlindependent_comalloc(size_t n_elements,size_t sizes[],void * chunks[])4896 void** dlindependent_comalloc(size_t n_elements, size_t sizes[],
4897 void* chunks[]) {
4898 return ialloc(gm, n_elements, sizes, 0, chunks);
4899 }
4900
dlvalloc(size_t bytes)4901 void* dlvalloc(size_t bytes) {
4902 size_t pagesz;
4903 ensure_initialization();
4904 pagesz = mparams.page_size;
4905 return dlmemalign(pagesz, bytes);
4906 }
4907
dlpvalloc(size_t bytes)4908 void* dlpvalloc(size_t bytes) {
4909 size_t pagesz;
4910 ensure_initialization();
4911 pagesz = mparams.page_size;
4912 return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));
4913 }
4914
dlmalloc_trim(size_t pad)4915 int dlmalloc_trim(size_t pad) {
4916 int result = 0;
4917 ensure_initialization();
4918 if (!PREACTION(gm)) {
4919 result = sys_trim(gm, pad);
4920 POSTACTION(gm);
4921 }
4922 return result;
4923 }
4924
dlmalloc_footprint(void)4925 size_t dlmalloc_footprint(void) {
4926 return gm->footprint;
4927 }
4928
dlmalloc_max_footprint(void)4929 size_t dlmalloc_max_footprint(void) {
4930 return gm->max_footprint;
4931 }
4932
4933 #if !NO_MALLINFO
dlmallinfo(void)4934 struct mallinfo dlmallinfo(void) {
4935 return internal_mallinfo(gm);
4936 }
4937 #endif /* NO_MALLINFO */
4938
dlmalloc_stats()4939 void dlmalloc_stats() {
4940 internal_malloc_stats(gm);
4941 }
4942
dlmallopt(int param_number,int value)4943 int dlmallopt(int param_number, int value) {
4944 return change_mparam(param_number, value);
4945 }
4946
4947 #endif /* !ONLY_MSPACES */
4948
dlmalloc_usable_size(void * mem)4949 size_t dlmalloc_usable_size(void* mem) {
4950 if (mem != 0) {
4951 mchunkptr p = mem2chunk(mem);
4952 if (is_inuse(p))
4953 return chunksize(p) - overhead_for(p);
4954 }
4955 return 0;
4956 }
4957
4958 /* ----------------------------- user mspaces ---------------------------- */
4959
4960 #if MSPACES
4961
init_user_mstate(char * tbase,size_t tsize)4962 static mstate init_user_mstate(char* tbase, size_t tsize) {
4963 size_t msize = pad_request(sizeof(struct malloc_state));
4964 mchunkptr mn;
4965 mchunkptr msp = align_as_chunk(tbase);
4966 mstate m = (mstate)(chunk2mem(msp));
4967 memset(m, 0, msize);
4968 INITIAL_LOCK(&m->mutex);
4969 msp->head = (msize|INUSE_BITS);
4970 m->seg.base = m->least_addr = tbase;
4971 m->seg.size = m->footprint = m->max_footprint = tsize;
4972 m->magic = mparams.magic;
4973 m->release_checks = MAX_RELEASE_CHECK_RATE;
4974 m->mflags = mparams.default_mflags;
4975 m->extp = 0;
4976 m->exts = 0;
4977 disable_contiguous(m);
4978 init_bins(m);
4979 mn = next_chunk(mem2chunk(m));
4980 init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
4981 check_top_chunk(m, m->top);
4982 return m;
4983 }
4984
create_mspace(size_t capacity,int locked)4985 mspace create_mspace(size_t capacity, int locked) {
4986 mstate m = 0;
4987 size_t msize;
4988 ensure_initialization();
4989 msize = pad_request(sizeof(struct malloc_state));
4990 if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4991 size_t rs = ((capacity == 0)? mparams.granularity :
4992 (capacity + TOP_FOOT_SIZE + msize));
4993 size_t tsize = granularity_align(rs);
4994 char* tbase = (char*)(CALL_MMAP(tsize));
4995 if (tbase != CMFAIL) {
4996 m = init_user_mstate(tbase, tsize);
4997 m->seg.sflags = USE_MMAP_BIT;
4998 set_lock(m, locked);
4999 }
5000 }
5001 return (mspace)m;
5002 }
5003
create_mspace_with_base(void * base,size_t capacity,int locked)5004 mspace create_mspace_with_base(void* base, size_t capacity, int locked) {
5005 mstate m = 0;
5006 size_t msize;
5007 ensure_initialization();
5008 msize = pad_request(sizeof(struct malloc_state));
5009 if (capacity > msize + TOP_FOOT_SIZE &&
5010 capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
5011 m = init_user_mstate((char*)base, capacity);
5012 m->seg.sflags = EXTERN_BIT;
5013 set_lock(m, locked);
5014 }
5015 return (mspace)m;
5016 }
5017
mspace_track_large_chunks(mspace msp,int enable)5018 int mspace_track_large_chunks(mspace msp, int enable) {
5019 int ret = 0;
5020 mstate ms = (mstate)msp;
5021 if (!PREACTION(ms)) {
5022 if (!use_mmap(ms))
5023 ret = 1;
5024 if (!enable)
5025 enable_mmap(ms);
5026 else
5027 disable_mmap(ms);
5028 POSTACTION(ms);
5029 }
5030 return ret;
5031 }
5032
destroy_mspace(mspace msp)5033 size_t destroy_mspace(mspace msp) {
5034 size_t freed = 0;
5035 mstate ms = (mstate)msp;
5036 if (ok_magic(ms)) {
5037 msegmentptr sp = &ms->seg;
5038 while (sp != 0) {
5039 char* base = sp->base;
5040 size_t size = sp->size;
5041 flag_t flag = sp->sflags;
5042 sp = sp->next;
5043 if ((flag & USE_MMAP_BIT) && !(flag & EXTERN_BIT) &&
5044 CALL_MUNMAP(base, size) == 0)
5045 freed += size;
5046 }
5047 }
5048 else {
5049 USAGE_ERROR_ACTION(ms,ms);
5050 }
5051 return freed;
5052 }
5053
5054 /*
5055 mspace versions of routines are near-clones of the global
5056 versions. This is not so nice but better than the alternatives.
5057 */
5058
5059
mspace_malloc(mspace msp,size_t bytes)5060 void* mspace_malloc(mspace msp, size_t bytes) {
5061 mstate ms = (mstate)msp;
5062 if (!ok_magic(ms)) {
5063 USAGE_ERROR_ACTION(ms,ms);
5064 return 0;
5065 }
5066 if (!PREACTION(ms)) {
5067 void* mem;
5068 size_t nb;
5069 if (bytes <= MAX_SMALL_REQUEST) {
5070 bindex_t idx;
5071 binmap_t smallbits;
5072 nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
5073 idx = small_index(nb);
5074 smallbits = ms->smallmap >> idx;
5075
5076 if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
5077 mchunkptr b, p;
5078 idx += ~smallbits & 1; /* Uses next bin if idx empty */
5079 b = smallbin_at(ms, idx);
5080 p = b->fd;
5081 assert(chunksize(p) == small_index2size(idx));
5082 unlink_first_small_chunk(ms, b, p, idx);
5083 set_inuse_and_pinuse(ms, p, small_index2size(idx));
5084 mem = chunk2mem(p);
5085 check_malloced_chunk(ms, mem, nb);
5086 goto postaction;
5087 }
5088
5089 else if (nb > ms->dvsize) {
5090 if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
5091 mchunkptr b, p, r;
5092 size_t rsize;
5093 bindex_t i;
5094 binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
5095 binmap_t leastbit = least_bit(leftbits);
5096 compute_bit2idx(leastbit, i);
5097 b = smallbin_at(ms, i);
5098 p = b->fd;
5099 assert(chunksize(p) == small_index2size(i));
5100 unlink_first_small_chunk(ms, b, p, i);
5101 rsize = small_index2size(i) - nb;
5102 /* Fit here cannot be remainderless if 4byte sizes */
5103 if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
5104 set_inuse_and_pinuse(ms, p, small_index2size(i));
5105 else {
5106 set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
5107 r = chunk_plus_offset(p, nb);
5108 set_size_and_pinuse_of_free_chunk(r, rsize);
5109 replace_dv(ms, r, rsize);
5110 }
5111 mem = chunk2mem(p);
5112 check_malloced_chunk(ms, mem, nb);
5113 goto postaction;
5114 }
5115
5116 else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
5117 check_malloced_chunk(ms, mem, nb);
5118 goto postaction;
5119 }
5120 }
5121 }
5122 else if (bytes >= MAX_REQUEST)
5123 nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
5124 else {
5125 nb = pad_request(bytes);
5126 if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
5127 check_malloced_chunk(ms, mem, nb);
5128 goto postaction;
5129 }
5130 }
5131
5132 if (nb <= ms->dvsize) {
5133 size_t rsize = ms->dvsize - nb;
5134 mchunkptr p = ms->dv;
5135 if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
5136 mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
5137 ms->dvsize = rsize;
5138 set_size_and_pinuse_of_free_chunk(r, rsize);
5139 set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
5140 }
5141 else { /* exhaust dv */
5142 size_t dvs = ms->dvsize;
5143 ms->dvsize = 0;
5144 ms->dv = 0;
5145 set_inuse_and_pinuse(ms, p, dvs);
5146 }
5147 mem = chunk2mem(p);
5148 check_malloced_chunk(ms, mem, nb);
5149 goto postaction;
5150 }
5151
5152 else if (nb < ms->topsize) { /* Split top */
5153 size_t rsize = ms->topsize -= nb;
5154 mchunkptr p = ms->top;
5155 mchunkptr r = ms->top = chunk_plus_offset(p, nb);
5156 r->head = rsize | PINUSE_BIT;
5157 set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
5158 mem = chunk2mem(p);
5159 check_top_chunk(ms, ms->top);
5160 check_malloced_chunk(ms, mem, nb);
5161 goto postaction;
5162 }
5163
5164 mem = sys_alloc(ms, nb);
5165
5166 postaction:
5167 POSTACTION(ms);
5168 return mem;
5169 }
5170
5171 return 0;
5172 }
5173
mspace_free(mspace msp,void * mem)5174 void mspace_free(mspace msp, void* mem) {
5175 if (mem != 0) {
5176 mchunkptr p = mem2chunk(mem);
5177 #if FOOTERS
5178 mstate fm = get_mstate_for(p);
5179 msp = msp; /* placate people compiling -Wunused */
5180 #else /* FOOTERS */
5181 mstate fm = (mstate)msp;
5182 #endif /* FOOTERS */
5183 if (!ok_magic(fm)) {
5184 USAGE_ERROR_ACTION(fm, p);
5185 return;
5186 }
5187 if (!PREACTION(fm)) {
5188 check_inuse_chunk(fm, p);
5189 if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
5190 size_t psize = chunksize(p);
5191 mchunkptr next = chunk_plus_offset(p, psize);
5192 if (!pinuse(p)) {
5193 size_t prevsize = p->prev_foot;
5194 if (is_mmapped(p)) {
5195 psize += prevsize + MMAP_FOOT_PAD;
5196 if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
5197 fm->footprint -= psize;
5198 goto postaction;
5199 }
5200 else {
5201 mchunkptr prev = chunk_minus_offset(p, prevsize);
5202 psize += prevsize;
5203 p = prev;
5204 if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
5205 if (p != fm->dv) {
5206 unlink_chunk(fm, p, prevsize);
5207 }
5208 else if ((next->head & INUSE_BITS) == INUSE_BITS) {
5209 fm->dvsize = psize;
5210 set_free_with_pinuse(p, psize, next);
5211 goto postaction;
5212 }
5213 }
5214 else
5215 goto erroraction;
5216 }
5217 }
5218
5219 if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
5220 if (!cinuse(next)) { /* consolidate forward */
5221 if (next == fm->top) {
5222 size_t tsize = fm->topsize += psize;
5223 fm->top = p;
5224 p->head = tsize | PINUSE_BIT;
5225 if (p == fm->dv) {
5226 fm->dv = 0;
5227 fm->dvsize = 0;
5228 }
5229 if (should_trim(fm, tsize))
5230 sys_trim(fm, 0);
5231 goto postaction;
5232 }
5233 else if (next == fm->dv) {
5234 size_t dsize = fm->dvsize += psize;
5235 fm->dv = p;
5236 set_size_and_pinuse_of_free_chunk(p, dsize);
5237 goto postaction;
5238 }
5239 else {
5240 size_t nsize = chunksize(next);
5241 psize += nsize;
5242 unlink_chunk(fm, next, nsize);
5243 set_size_and_pinuse_of_free_chunk(p, psize);
5244 if (p == fm->dv) {
5245 fm->dvsize = psize;
5246 goto postaction;
5247 }
5248 }
5249 }
5250 else
5251 set_free_with_pinuse(p, psize, next);
5252
5253 if (is_small(psize)) {
5254 insert_small_chunk(fm, p, psize);
5255 check_free_chunk(fm, p);
5256 }
5257 else {
5258 tchunkptr tp = (tchunkptr)p;
5259 insert_large_chunk(fm, tp, psize);
5260 check_free_chunk(fm, p);
5261 if (--fm->release_checks == 0)
5262 release_unused_segments(fm);
5263 }
5264 goto postaction;
5265 }
5266 }
5267 erroraction:
5268 USAGE_ERROR_ACTION(fm, p);
5269 postaction:
5270 POSTACTION(fm);
5271 }
5272 }
5273 }
5274
mspace_calloc(mspace msp,size_t n_elements,size_t elem_size)5275 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
5276 void* mem;
5277 size_t req = 0;
5278 mstate ms = (mstate)msp;
5279 if (!ok_magic(ms)) {
5280 USAGE_ERROR_ACTION(ms,ms);
5281 return 0;
5282 }
5283 if (n_elements != 0) {
5284 req = n_elements * elem_size;
5285 if (((n_elements | elem_size) & ~(size_t)0xffff) &&
5286 (req / n_elements != elem_size))
5287 req = MAX_SIZE_T; /* force downstream failure on overflow */
5288 }
5289 mem = internal_malloc(ms, req);
5290 if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
5291 memset(mem, 0, req);
5292 return mem;
5293 }
5294
mspace_realloc(mspace msp,void * oldmem,size_t bytes)5295 void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
5296 if (oldmem == 0)
5297 return mspace_malloc(msp, bytes);
5298 #ifdef REALLOC_ZERO_BYTES_FREES
5299 if (bytes == 0) {
5300 mspace_free(msp, oldmem);
5301 return 0;
5302 }
5303 #endif /* REALLOC_ZERO_BYTES_FREES */
5304 else {
5305 #if FOOTERS
5306 mchunkptr p = mem2chunk(oldmem);
5307 mstate ms = get_mstate_for(p);
5308 #else /* FOOTERS */
5309 mstate ms = (mstate)msp;
5310 #endif /* FOOTERS */
5311 if (!ok_magic(ms)) {
5312 USAGE_ERROR_ACTION(ms,ms);
5313 return 0;
5314 }
5315 return internal_realloc(ms, oldmem, bytes);
5316 }
5317 }
5318
mspace_memalign(mspace msp,size_t alignment,size_t bytes)5319 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
5320 mstate ms = (mstate)msp;
5321 if (!ok_magic(ms)) {
5322 USAGE_ERROR_ACTION(ms,ms);
5323 return 0;
5324 }
5325 return internal_memalign(ms, alignment, bytes);
5326 }
5327
mspace_independent_calloc(mspace msp,size_t n_elements,size_t elem_size,void * chunks[])5328 void** mspace_independent_calloc(mspace msp, size_t n_elements,
5329 size_t elem_size, void* chunks[]) {
5330 size_t sz = elem_size; /* serves as 1-element array */
5331 mstate ms = (mstate)msp;
5332 if (!ok_magic(ms)) {
5333 USAGE_ERROR_ACTION(ms,ms);
5334 return 0;
5335 }
5336 return ialloc(ms, n_elements, &sz, 3, chunks);
5337 }
5338
mspace_independent_comalloc(mspace msp,size_t n_elements,size_t sizes[],void * chunks[])5339 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
5340 size_t sizes[], void* chunks[]) {
5341 mstate ms = (mstate)msp;
5342 if (!ok_magic(ms)) {
5343 USAGE_ERROR_ACTION(ms,ms);
5344 return 0;
5345 }
5346 return ialloc(ms, n_elements, sizes, 0, chunks);
5347 }
5348
mspace_trim(mspace msp,size_t pad)5349 int mspace_trim(mspace msp, size_t pad) {
5350 int result = 0;
5351 mstate ms = (mstate)msp;
5352 if (ok_magic(ms)) {
5353 if (!PREACTION(ms)) {
5354 result = sys_trim(ms, pad);
5355 POSTACTION(ms);
5356 }
5357 }
5358 else {
5359 USAGE_ERROR_ACTION(ms,ms);
5360 }
5361 return result;
5362 }
5363
mspace_malloc_stats(mspace msp)5364 void mspace_malloc_stats(mspace msp) {
5365 mstate ms = (mstate)msp;
5366 if (ok_magic(ms)) {
5367 internal_malloc_stats(ms);
5368 }
5369 else {
5370 USAGE_ERROR_ACTION(ms,ms);
5371 }
5372 }
5373
mspace_footprint(mspace msp)5374 size_t mspace_footprint(mspace msp) {
5375 size_t result = 0;
5376 mstate ms = (mstate)msp;
5377 if (ok_magic(ms)) {
5378 result = ms->footprint;
5379 }
5380 else {
5381 USAGE_ERROR_ACTION(ms,ms);
5382 }
5383 return result;
5384 }
5385
5386
mspace_max_footprint(mspace msp)5387 size_t mspace_max_footprint(mspace msp) {
5388 size_t result = 0;
5389 mstate ms = (mstate)msp;
5390 if (ok_magic(ms)) {
5391 result = ms->max_footprint;
5392 }
5393 else {
5394 USAGE_ERROR_ACTION(ms,ms);
5395 }
5396 return result;
5397 }
5398
5399
5400 #if !NO_MALLINFO
mspace_mallinfo(mspace msp)5401 struct mallinfo mspace_mallinfo(mspace msp) {
5402 mstate ms = (mstate)msp;
5403 if (!ok_magic(ms)) {
5404 USAGE_ERROR_ACTION(ms,ms);
5405 }
5406 return internal_mallinfo(ms);
5407 }
5408 #endif /* NO_MALLINFO */
5409
mspace_usable_size(void * mem)5410 size_t mspace_usable_size(void* mem) {
5411 if (mem != 0) {
5412 mchunkptr p = mem2chunk(mem);
5413 if (is_inuse(p))
5414 return chunksize(p) - overhead_for(p);
5415 }
5416 return 0;
5417 }
5418
mspace_mallopt(int param_number,int value)5419 int mspace_mallopt(int param_number, int value) {
5420 return change_mparam(param_number, value);
5421 }
5422
5423 #endif /* MSPACES */
5424
5425
5426 /* -------------------- Alternative MORECORE functions ------------------- */
5427
5428 /*
5429 Guidelines for creating a custom version of MORECORE:
5430
5431 * For best performance, MORECORE should allocate in multiples of pagesize.
5432 * MORECORE may allocate more memory than requested. (Or even less,
5433 but this will usually result in a malloc failure.)
5434 * MORECORE must not allocate memory when given argument zero, but
5435 instead return one past the end address of memory from previous
5436 nonzero call.
5437 * For best performance, consecutive calls to MORECORE with positive
5438 arguments should return increasing addresses, indicating that
5439 space has been contiguously extended.
5440 * Even though consecutive calls to MORECORE need not return contiguous
5441 addresses, it must be OK for malloc'ed chunks to span multiple
5442 regions in those cases where they do happen to be contiguous.
5443 * MORECORE need not handle negative arguments -- it may instead
5444 just return MFAIL when given negative arguments.
5445 Negative arguments are always multiples of pagesize. MORECORE
5446 must not misinterpret negative args as large positive unsigned
5447 args. You can suppress all such calls from even occurring by defining
5448 MORECORE_CANNOT_TRIM,
5449
5450 As an example alternative MORECORE, here is a custom allocator
5451 kindly contributed for pre-OSX macOS. It uses virtually but not
5452 necessarily physically contiguous non-paged memory (locked in,
5453 present and won't get swapped out). You can use it by uncommenting
5454 this section, adding some #includes, and setting up the appropriate
5455 defines above:
5456
5457 #define MORECORE osMoreCore
5458
5459 There is also a shutdown routine that should somehow be called for
5460 cleanup upon program exit.
5461
5462 #define MAX_POOL_ENTRIES 100
5463 #define MINIMUM_MORECORE_SIZE (64 * 1024U)
5464 static int next_os_pool;
5465 void *our_os_pools[MAX_POOL_ENTRIES];
5466
5467 void *osMoreCore(int size)
5468 {
5469 void *ptr = 0;
5470 static void *sbrk_top = 0;
5471
5472 if (size > 0)
5473 {
5474 if (size < MINIMUM_MORECORE_SIZE)
5475 size = MINIMUM_MORECORE_SIZE;
5476 if (CurrentExecutionLevel() == kTaskLevel)
5477 ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
5478 if (ptr == 0)
5479 {
5480 return (void *) MFAIL;
5481 }
5482 // save ptrs so they can be freed during cleanup
5483 our_os_pools[next_os_pool] = ptr;
5484 next_os_pool++;
5485 ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
5486 sbrk_top = (char *) ptr + size;
5487 return ptr;
5488 }
5489 else if (size < 0)
5490 {
5491 // we don't currently support shrink behavior
5492 return (void *) MFAIL;
5493 }
5494 else
5495 {
5496 return sbrk_top;
5497 }
5498 }
5499
5500 // cleanup any allocated memory pools
5501 // called as last thing before shutting down driver
5502
5503 void osCleanupMem(void)
5504 {
5505 void **ptr;
5506
5507 for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
5508 if (*ptr)
5509 {
5510 PoolDeallocate(*ptr);
5511 *ptr = 0;
5512 }
5513 }
5514
5515 */
5516
5517
5518 /* -----------------------------------------------------------------------
5519 History:
5520 V2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee)
5521 * Use zeros instead of prev foot for is_mmapped
5522 * Add mspace_track_large_chunks; thanks to Jean Brouwers
5523 * Fix set_inuse in internal_realloc; thanks to Jean Brouwers
5524 * Fix insufficient sys_alloc padding when using 16byte alignment
5525 * Fix bad error check in mspace_footprint
5526 * Adaptations for ptmalloc; thanks to Wolfram Gloger.
5527 * Reentrant spin locks; thanks to Earl Chew and others
5528 * Win32 improvements; thanks to Niall Douglas and Earl Chew
5529 * Add NO_SEGMENT_TRAVERSAL and MAX_RELEASE_CHECK_RATE options
5530 * Extension hook in malloc_state
5531 * Various small adjustments to reduce warnings on some compilers
5532 * Various configuration extensions/changes for more platforms. Thanks
5533 to all who contributed these.
5534
5535 V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee)
5536 * Add max_footprint functions
5537 * Ensure all appropriate literals are size_t
5538 * Fix conditional compilation problem for some #define settings
5539 * Avoid concatenating segments with the one provided
5540 in create_mspace_with_base
5541 * Rename some variables to avoid compiler shadowing warnings
5542 * Use explicit lock initialization.
5543 * Better handling of sbrk interference.
5544 * Simplify and fix segment insertion, trimming and mspace_destroy
5545 * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
5546 * Thanks especially to Dennis Flanagan for help on these.
5547
5548 V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee)
5549 * Fix memalign brace error.
5550
5551 V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee)
5552 * Fix improper #endif nesting in C++
5553 * Add explicit casts needed for C++
5554
5555 V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee)
5556 * Use trees for large bins
5557 * Support mspaces
5558 * Use segments to unify sbrk-based and mmap-based system allocation,
5559 removing need for emulation on most platforms without sbrk.
5560 * Default safety checks
5561 * Optional footer checks. Thanks to William Robertson for the idea.
5562 * Internal code refactoring
5563 * Incorporate suggestions and platform-specific changes.
5564 Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
5565 Aaron Bachmann, Emery Berger, and others.
5566 * Speed up non-fastbin processing enough to remove fastbins.
5567 * Remove useless cfree() to avoid conflicts with other apps.
5568 * Remove internal memcpy, memset. Compilers handle builtins better.
5569 * Remove some options that no one ever used and rename others.
5570
5571 V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee)
5572 * Fix malloc_state bitmap array misdeclaration
5573
5574 V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
5575 * Allow tuning of FIRST_SORTED_BIN_SIZE
5576 * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
5577 * Better detection and support for non-contiguousness of MORECORE.
5578 Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
5579 * Bypass most of malloc if no frees. Thanks To Emery Berger.
5580 * Fix freeing of old top non-contiguous chunk im sysmalloc.
5581 * Raised default trim and map thresholds to 256K.
5582 * Fix mmap-related #defines. Thanks to Lubos Lunak.
5583 * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
5584 * Branch-free bin calculation
5585 * Default trim and mmap thresholds now 256K.
5586
5587 V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
5588 * Introduce independent_comalloc and independent_calloc.
5589 Thanks to Michael Pachos for motivation and help.
5590 * Make optional .h file available
5591 * Allow > 2GB requests on 32bit systems.
5592 * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
5593 Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
5594 and Anonymous.
5595 * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
5596 helping test this.)
5597 * memalign: check alignment arg
5598 * realloc: don't try to shift chunks backwards, since this
5599 leads to more fragmentation in some programs and doesn't
5600 seem to help in any others.
5601 * Collect all cases in malloc requiring system memory into sysmalloc
5602 * Use mmap as backup to sbrk
5603 * Place all internal state in malloc_state
5604 * Introduce fastbins (although similar to 2.5.1)
5605 * Many minor tunings and cosmetic improvements
5606 * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
5607 * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
5608 Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
5609 * Include errno.h to support default failure action.
5610
5611 V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
5612 * return null for negative arguments
5613 * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5614 * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5615 (e.g. WIN32 platforms)
5616 * Cleanup header file inclusion for WIN32 platforms
5617 * Cleanup code to avoid Microsoft Visual C++ compiler complaints
5618 * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5619 memory allocation routines
5620 * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5621 * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5622 usage of 'assert' in non-WIN32 code
5623 * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5624 avoid infinite loop
5625 * Always call 'fREe()' rather than 'free()'
5626
5627 V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
5628 * Fixed ordering problem with boundary-stamping
5629
5630 V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
5631 * Added pvalloc, as recommended by H.J. Liu
5632 * Added 64bit pointer support mainly from Wolfram Gloger
5633 * Added anonymously donated WIN32 sbrk emulation
5634 * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5635 * malloc_extend_top: fix mask error that caused wastage after
5636 foreign sbrks
5637 * Add linux mremap support code from HJ Liu
5638
5639 V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
5640 * Integrated most documentation with the code.
5641 * Add support for mmap, with help from
5642 Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5643 * Use last_remainder in more cases.
5644 * Pack bins using idea from colin@nyx10.cs.du.edu
5645 * Use ordered bins instead of best-fit threshhold
5646 * Eliminate block-local decls to simplify tracing and debugging.
5647 * Support another case of realloc via move into top
5648 * Fix error occuring when initial sbrk_base not word-aligned.
5649 * Rely on page size for units instead of SBRK_UNIT to
5650 avoid surprises about sbrk alignment conventions.
5651 * Add mallinfo, mallopt. Thanks to Raymond Nijssen
5652 (raymond@es.ele.tue.nl) for the suggestion.
5653 * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5654 * More precautions for cases where other routines call sbrk,
5655 courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5656 * Added macros etc., allowing use in linux libc from
5657 H.J. Lu (hjl@gnu.ai.mit.edu)
5658 * Inverted this history list
5659
5660 V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
5661 * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5662 * Removed all preallocation code since under current scheme
5663 the work required to undo bad preallocations exceeds
5664 the work saved in good cases for most test programs.
5665 * No longer use return list or unconsolidated bins since
5666 no scheme using them consistently outperforms those that don't
5667 given above changes.
5668 * Use best fit for very large chunks to prevent some worst-cases.
5669 * Added some support for debugging
5670
5671 V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
5672 * Removed footers when chunks are in use. Thanks to
5673 Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5674
5675 V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
5676 * Added malloc_trim, with help from Wolfram Gloger
5677 (wmglo@Dent.MED.Uni-Muenchen.DE).
5678
5679 V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
5680
5681 V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
5682 * realloc: try to expand in both directions
5683 * malloc: swap order of clean-bin strategy;
5684 * realloc: only conditionally expand backwards
5685 * Try not to scavenge used bins
5686 * Use bin counts as a guide to preallocation
5687 * Occasionally bin return list chunks in first scan
5688 * Add a few optimizations from colin@nyx10.cs.du.edu
5689
5690 V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
5691 * faster bin computation & slightly different binning
5692 * merged all consolidations to one part of malloc proper
5693 (eliminating old malloc_find_space & malloc_clean_bin)
5694 * Scan 2 returns chunks (not just 1)
5695 * Propagate failure in realloc if malloc returns 0
5696 * Add stuff to allow compilation on non-ANSI compilers
5697 from kpv@research.att.com
5698
5699 V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
5700 * removed potential for odd address access in prev_chunk
5701 * removed dependency on getpagesize.h
5702 * misc cosmetics and a bit more internal documentation
5703 * anticosmetics: mangled names in macros to evade debugger strangeness
5704 * tested on sparc, hp-700, dec-mips, rs6000
5705 with gcc & native cc (hp, dec only) allowing
5706 Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5707
5708 Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
5709 * Based loosely on libg++-1.2X malloc. (It retains some of the overall
5710 structure of old version, but most details differ.)
5711
5712 */
5713
5714