Fix apparent bug...
[satcheck.git] / malloc.c
1 /*
2   This is a version (aka dlmalloc) of malloc/free/realloc written by
3   Doug Lea and released to the public domain, as explained at
4   http://creativecommons.org/publicdomain/zero/1.0/ Send questions,
5   comments, complaints, performance data, etc to dl@cs.oswego.edu
6
7 * Version 2.8.5 Sun May 22 10:26:02 2011  Doug Lea  (dl at gee)
8
9    Note: There may be an updated version of this malloc obtainable at
10            ftp://gee.cs.oswego.edu/pub/misc/malloc.c
11          Check before installing!
12
13 * Quickstart
14
15   This library is all in one file to simplify the most common usage:
16   ftp it, compile it (-O3), and link it into another program. All of
17   the compile-time options default to reasonable values for use on
18   most platforms.  You might later want to step through various
19   compile-time and dynamic tuning options.
20
21   For convenience, an include file for code using this malloc is at:
22      ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.5.h
23   You don't really need this .h file unless you call functions not
24   defined in your system include files.  The .h file contains only the
25   excerpts from this file needed for using this malloc on ANSI C/C++
26   systems, so long as you haven't changed compile-time options about
27   naming and tuning parameters.  If you do, then you can create your
28   own malloc.h that does include all settings by cutting at the point
29   indicated below. Note that you may already by default be using a C
30   library containing a malloc that is based on some version of this
31   malloc (for example in linux). You might still want to use the one
32   in this file to customize settings or to avoid overheads associated
33   with library versions.
34
35 * Vital statistics:
36
37   Supported pointer/size_t representation:       4 or 8 bytes
38        size_t MUST be an unsigned type of the same width as
39        pointers. (If you are using an ancient system that declares
40        size_t as a signed type, or need it to be a different width
41        than pointers, you can use a previous release of this malloc
42        (e.g. 2.7.2) supporting these.)
43
44   Alignment:                                     8 bytes (default)
45        This suffices for nearly all current machines and C compilers.
46        However, you can define MALLOC_ALIGNMENT to be wider than this
47        if necessary (up to 128bytes), at the expense of using more space.
48
49   Minimum overhead per allocated chunk:   4 or  8 bytes (if 4byte sizes)
50                                           8 or 16 bytes (if 8byte sizes)
51        Each malloced chunk has a hidden word of overhead holding size
52        and status information, and additional cross-check word
53        if FOOTERS is defined.
54
55   Minimum allocated size: 4-byte ptrs:  16 bytes    (including overhead)
56                           8-byte ptrs:  32 bytes    (including overhead)
57
58        Even a request for zero bytes (i.e., malloc(0)) returns a
59        pointer to something of the minimum allocatable size.
60        The maximum overhead wastage (i.e., number of extra bytes
61        allocated than were requested in malloc) is less than or equal
62        to the minimum size, except for requests >= mmap_threshold that
63        are serviced via mmap(), where the worst case wastage is about
64        32 bytes plus the remainder from a system page (the minimal
65        mmap unit); typically 4096 or 8192 bytes.
66
67   Security: static-safe; optionally more or less
68        The "security" of malloc refers to the ability of malicious
69        code to accentuate the effects of errors (for example, freeing
70        space that is not currently malloc'ed or overwriting past the
71        ends of chunks) in code that calls malloc.  This malloc
72        guarantees not to modify any memory locations below the base of
73        heap, i.e., static variables, even in the presence of usage
74        errors.  The routines additionally detect most improper frees
75        and reallocs.  All this holds as long as the static bookkeeping
76        for malloc itself is not corrupted by some other means.  This
77        is only one aspect of security -- these checks do not, and
78        cannot, detect all possible programming errors.
79
80        If FOOTERS is defined nonzero, then each allocated chunk
81        carries an additional check word to verify that it was malloced
82        from its space.  These check words are the same within each
83        execution of a program using malloc, but differ across
84        executions, so externally crafted fake chunks cannot be
85        freed. This improves security by rejecting frees/reallocs that
86        could corrupt heap memory, in addition to the checks preventing
87        writes to statics that are always on.  This may further improve
88        security at the expense of time and space overhead.  (Note that
89        FOOTERS may also be worth using with MSPACES.)
90
91        By default detected errors cause the program to abort (calling
92        "abort()"). You can override this to instead proceed past
93        errors by defining PROCEED_ON_ERROR.  In this case, a bad free
94        has no effect, and a malloc that encounters a bad address
95        caused by user overwrites will ignore the bad address by
96        dropping pointers and indices to all known memory. This may
97        be appropriate for programs that should continue if at all
98        possible in the face of programming errors, although they may
99        run out of memory because dropped memory is never reclaimed.
100
101        If you don't like either of these options, you can define
102        CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
103        else. And if if you are sure that your program using malloc has
104        no errors or vulnerabilities, you can define INSECURE to 1,
105        which might (or might not) provide a small performance improvement.
106
107        It is also possible to limit the maximum total allocatable
108        space, using malloc_set_footprint_limit. This is not
109        designed as a security feature in itself (calls to set limits
110        are not screened or privileged), but may be useful as one
111        aspect of a secure implementation.
112
113   Thread-safety: NOT thread-safe unless USE_LOCKS defined non-zero
114        When USE_LOCKS is defined, each public call to malloc, free,
115        etc is surrounded with a lock. By default, this uses a plain
116        pthread mutex, win32 critical section, or a spin-lock if if
117        available for the platform and not disabled by setting
118        USE_SPIN_LOCKS=0.  However, if USE_RECURSIVE_LOCKS is defined,
119        recursive versions are used instead (which are not required for
120        base functionality but may be needed in layered extensions).
121        Using a global lock is not especially fast, and can be a major
122        bottleneck.  It is designed only to provide minimal protection
123        in concurrent environments, and to provide a basis for
124        extensions.  If you are using malloc in a concurrent program,
125        consider instead using nedmalloc
126        (http://www.nedprod.com/programs/portable/nedmalloc/) or
127        ptmalloc (See http://www.malloc.de), which are derived from
128        versions of this malloc.
129
130   System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
131        This malloc can use unix sbrk or any emulation (invoked using
132        the CALL_MORECORE macro) and/or mmap/munmap or any emulation
133        (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
134        memory.  On most unix systems, it tends to work best if both
135        MORECORE and MMAP are enabled.  On Win32, it uses emulations
136        based on VirtualAlloc. It also uses common C library functions
137        like memset.
138
139   Compliance: I believe it is compliant with the Single Unix Specification
140        (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
141        others as well.
142
143 * Overview of algorithms
144
145   This is not the fastest, most space-conserving, most portable, or
146   most tunable malloc ever written. However it is among the fastest
147   while also being among the most space-conserving, portable and
148   tunable.  Consistent balance across these factors results in a good
149   general-purpose allocator for malloc-intensive programs.
150
151   In most ways, this malloc is a best-fit allocator. Generally, it
152   chooses the best-fitting existing chunk for a request, with ties
153   broken in approximately least-recently-used order. (This strategy
154   normally maintains low fragmentation.) However, for requests less
155   than 256bytes, it deviates from best-fit when there is not an
156   exactly fitting available chunk by preferring to use space adjacent
157   to that used for the previous small request, as well as by breaking
158   ties in approximately most-recently-used order. (These enhance
159   locality of series of small allocations.)  And for very large requests
160   (>= 256Kb by default), it relies on system memory mapping
161   facilities, if supported.  (This helps avoid carrying around and
162   possibly fragmenting memory used only for large chunks.)
163
164   All operations (except malloc_stats and mallinfo) have execution
165   times that are bounded by a constant factor of the number of bits in
166   a size_t, not counting any clearing in calloc or copying in realloc,
167   or actions surrounding MORECORE and MMAP that have times
168   proportional to the number of non-contiguous regions returned by
169   system allocation routines, which is often just 1. In real-time
170   applications, you can optionally suppress segment traversals using
171   NO_SEGMENT_TRAVERSAL, which assures bounded execution even when
172   system allocators return non-contiguous spaces, at the typical
173   expense of carrying around more memory and increased fragmentation.
174
175   The implementation is not very modular and seriously overuses
176   macros. Perhaps someday all C compilers will do as good a job
177   inlining modular code as can now be done by brute-force expansion,
178   but now, enough of them seem not to.
179
180   Some compilers issue a lot of warnings about code that is
181   dead/unreachable only on some platforms, and also about intentional
182   uses of negation on unsigned types. All known cases of each can be
183   ignored.
184
185   For a longer but out of date high-level description, see
186      http://gee.cs.oswego.edu/dl/html/malloc.html
187
188 * MSPACES
189   If MSPACES is defined, then in addition to malloc, free, etc.,
190   this file also defines mspace_malloc, mspace_free, etc. These
191   are versions of malloc routines that take an "mspace" argument
192   obtained using create_mspace, to control all internal bookkeeping.
193   If ONLY_MSPACES is defined, only these versions are compiled.
194   So if you would like to use this allocator for only some allocations,
195   and your system malloc for others, you can compile with
196   ONLY_MSPACES and then do something like...
197     static mspace mymspace = create_mspace(0,0); // for example
198     #define mymalloc(bytes)  mspace_malloc(mymspace, bytes)
199
200   (Note: If you only need one instance of an mspace, you can instead
201   use "USE_DL_PREFIX" to relabel the global malloc.)
202
203   You can similarly create thread-local allocators by storing
204   mspaces as thread-locals. For example:
205     static __thread mspace tlms = 0;
206     void*  tlmalloc(size_t bytes) {
207       if (tlms == 0) tlms = create_mspace(0, 0);
208       return mspace_malloc(tlms, bytes);
209     }
210     void  tlfree(void* mem) { mspace_free(tlms, mem); }
211
212   Unless FOOTERS is defined, each mspace is completely independent.
213   You cannot allocate from one and free to another (although
214   conformance is only weakly checked, so usage errors are not always
215   caught). If FOOTERS is defined, then each chunk carries around a tag
216   indicating its originating mspace, and frees are directed to their
217   originating spaces. Normally, this requires use of locks.
218
219  -------------------------  Compile-time options ---------------------------
220
221 Be careful in setting #define values for numerical constants of type
222 size_t. On some systems, literal values are not automatically extended
223 to size_t precision unless they are explicitly casted. You can also
224 use the symbolic values MAX_SIZE_T, SIZE_T_ONE, etc below.
225
226 WIN32                    default: defined if _WIN32 defined
227   Defining WIN32 sets up defaults for MS environment and compilers.
228   Otherwise defaults are for unix. Beware that there seem to be some
229   cases where this malloc might not be a pure drop-in replacement for
230   Win32 malloc: Random-looking failures from Win32 GDI API's (eg;
231   SetDIBits()) may be due to bugs in some video driver implementations
232   when pixel buffers are malloc()ed, and the region spans more than
233   one VirtualAlloc()ed region. Because dlmalloc uses a small (64Kb)
234   default granularity, pixel buffers may straddle virtual allocation
235   regions more often than when using the Microsoft allocator.  You can
236   avoid this by using VirtualAlloc() and VirtualFree() for all pixel
237   buffers rather than using malloc().  If this is not possible,
238   recompile this malloc with a larger DEFAULT_GRANULARITY. Note:
239   in cases where MSC and gcc (cygwin) are known to differ on WIN32,
240   conditions use _MSC_VER to distinguish them.
241
242 DLMALLOC_EXPORT       default: extern
243   Defines how public APIs are declared. If you want to export via a
244   Windows DLL, you might define this as
245     #define DLMALLOC_EXPORT extern  __declspace(dllexport)
246   If you want a POSIX ELF shared object, you might use
247     #define DLMALLOC_EXPORT extern __attribute__((visibility("default")))
248
249 MALLOC_ALIGNMENT         default: (size_t)8
250   Controls the minimum alignment for malloc'ed chunks.  It must be a
251   power of two and at least 8, even on machines for which smaller
252   alignments would suffice. It may be defined as larger than this
253   though. Note however that code and data structures are optimized for
254   the case of 8-byte alignment.
255
256 MSPACES                  default: 0 (false)
257   If true, compile in support for independent allocation spaces.
258   This is only supported if HAVE_MMAP is true.
259
260 ONLY_MSPACES             default: 0 (false)
261   If true, only compile in mspace versions, not regular versions.
262
263 USE_LOCKS                default: 0 (false)
264   Causes each call to each public routine to be surrounded with
265   pthread or WIN32 mutex lock/unlock. (If set true, this can be
266   overridden on a per-mspace basis for mspace versions.) If set to a
267   non-zero value other than 1, locks are used, but their
268   implementation is left out, so lock functions must be supplied manually,
269   as described below.
270
271 USE_SPIN_LOCKS           default: 1 iff USE_LOCKS and spin locks available
272   If true, uses custom spin locks for locking. This is currently
273   supported only gcc >= 4.1, older gccs on x86 platforms, and recent
274   MS compilers.  Otherwise, posix locks or win32 critical sections are
275   used.
276
277 USE_RECURSIVE_LOCKS      default: not defined
278   If defined nonzero, uses recursive (aka reentrant) locks, otherwise
279   uses plain mutexes. This is not required for malloc proper, but may
280   be needed for layered allocators such as nedmalloc.
281
282 FOOTERS                  default: 0
283   If true, provide extra checking and dispatching by placing
284   information in the footers of allocated chunks. This adds
285   space and time overhead.
286
287 INSECURE                 default: 0
288   If true, omit checks for usage errors and heap space overwrites.
289
290 USE_DL_PREFIX            default: NOT defined
291   Causes compiler to prefix all public routines with the string 'dl'.
292   This can be useful when you only want to use this malloc in one part
293   of a program, using your regular system malloc elsewhere.
294
295 MALLOC_INSPECT_ALL       default: NOT defined
296   If defined, compiles malloc_inspect_all and mspace_inspect_all, that
297   perform traversal of all heap space.  Unless access to these
298   functions is otherwise restricted, you probably do not want to
299   include them in secure implementations.
300
301 ABORT                    default: defined as abort()
302   Defines how to abort on failed checks.  On most systems, a failed
303   check cannot die with an "assert" or even print an informative
304   message, because the underlying print routines in turn call malloc,
305   which will fail again.  Generally, the best policy is to simply call
306   abort(). It's not very useful to do more than this because many
307   errors due to overwriting will show up as address faults (null, odd
308   addresses etc) rather than malloc-triggered checks, so will also
309   abort.  Also, most compilers know that abort() does not return, so
310   can better optimize code conditionally calling it.
311
312 PROCEED_ON_ERROR           default: defined as 0 (false)
313   Controls whether detected bad addresses cause them to bypassed
314   rather than aborting. If set, detected bad arguments to free and
315   realloc are ignored. And all bookkeeping information is zeroed out
316   upon a detected overwrite of freed heap space, thus losing the
317   ability to ever return it from malloc again, but enabling the
318   application to proceed. If PROCEED_ON_ERROR is defined, the
319   static variable malloc_corruption_error_count is compiled in
320   and can be examined to see if errors have occurred. This option
321   generates slower code than the default abort policy.
322
323 DEBUG                    default: NOT defined
324   The DEBUG setting is mainly intended for people trying to modify
325   this code or diagnose problems when porting to new platforms.
326   However, it may also be able to better isolate user errors than just
327   using runtime checks.  The assertions in the check routines spell
328   out in more detail the assumptions and invariants underlying the
329   algorithms.  The checking is fairly extensive, and will slow down
330   execution noticeably. Calling malloc_stats or mallinfo with DEBUG
331   set will attempt to check every non-mmapped allocated and free chunk
332   in the course of computing the summaries.
333
334 ABORT_ON_ASSERT_FAILURE   default: defined as 1 (true)
335   Debugging assertion failures can be nearly impossible if your
336   version of the assert macro causes malloc to be called, which will
337   lead to a cascade of further failures, blowing the runtime stack.
338   ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
339   which will usually make debugging easier.
340
341 MALLOC_FAILURE_ACTION     default: sets errno to ENOMEM, or no-op on win32
342   The action to take before "return 0" when malloc fails to be able to
343   return memory because there is none available.
344
345 HAVE_MORECORE             default: 1 (true) unless win32 or ONLY_MSPACES
346   True if this system supports sbrk or an emulation of it.
347
348 MORECORE                  default: sbrk
349   The name of the sbrk-style system routine to call to obtain more
350   memory.  See below for guidance on writing custom MORECORE
351   functions. The type of the argument to sbrk/MORECORE varies across
352   systems.  It cannot be size_t, because it supports negative
353   arguments, so it is normally the signed type of the same width as
354   size_t (sometimes declared as "intptr_t").  It doesn't much matter
355   though. Internally, we only call it with arguments less than half
356   the max value of a size_t, which should work across all reasonable
357   possibilities, although sometimes generating compiler warnings.
358
359 MORECORE_CONTIGUOUS       default: 1 (true) if HAVE_MORECORE
360   If true, take advantage of fact that consecutive calls to MORECORE
361   with positive arguments always return contiguous increasing
362   addresses.  This is true of unix sbrk. It does not hurt too much to
363   set it true anyway, since malloc copes with non-contiguities.
364   Setting it false when definitely non-contiguous saves time
365   and possibly wasted space it would take to discover this though.
366
367 MORECORE_CANNOT_TRIM      default: NOT defined
368   True if MORECORE cannot release space back to the system when given
369   negative arguments. This is generally necessary only if you are
370   using a hand-crafted MORECORE function that cannot handle negative
371   arguments.
372
373 NO_SEGMENT_TRAVERSAL       default: 0
374   If non-zero, suppresses traversals of memory segments
375   returned by either MORECORE or CALL_MMAP. This disables
376   merging of segments that are contiguous, and selectively
377   releasing them to the OS if unused, but bounds execution times.
378
379 HAVE_MMAP                 default: 1 (true)
380   True if this system supports mmap or an emulation of it.  If so, and
381   HAVE_MORECORE is not true, MMAP is used for all system
382   allocation. If set and HAVE_MORECORE is true as well, MMAP is
383   primarily used to directly allocate very large blocks. It is also
384   used as a backup strategy in cases where MORECORE fails to provide
385   space from system. Note: A single call to MUNMAP is assumed to be
386   able to unmap memory that may have be allocated using multiple calls
387   to MMAP, so long as they are adjacent.
388
389 HAVE_MREMAP               default: 1 on linux, else 0
390   If true realloc() uses mremap() to re-allocate large blocks and
391   extend or shrink allocation spaces.
392
393 MMAP_CLEARS               default: 1 except on WINCE.
394   True if mmap clears memory so calloc doesn't need to. This is true
395   for standard unix mmap using /dev/zero and on WIN32 except for WINCE.
396
397 USE_BUILTIN_FFS            default: 0 (i.e., not used)
398   Causes malloc to use the builtin ffs() function to compute indices.
399   Some compilers may recognize and intrinsify ffs to be faster than the
400   supplied C version. Also, the case of x86 using gcc is special-cased
401   to an asm instruction, so is already as fast as it can be, and so
402   this setting has no effect. Similarly for Win32 under recent MS compilers.
403   (On most x86s, the asm version is only slightly faster than the C version.)
404
405 malloc_getpagesize         default: derive from system includes, or 4096.
406   The system page size. To the extent possible, this malloc manages
407   memory from the system in page-size units.  This may be (and
408   usually is) a function rather than a constant. This is ignored
409   if WIN32, where page size is determined using getSystemInfo during
410   initialization.
411
412 USE_DEV_RANDOM             default: 0 (i.e., not used)
413   Causes malloc to use /dev/random to initialize secure magic seed for
414   stamping footers. Otherwise, the current time is used.
415
416 NO_MALLINFO                default: 0
417   If defined, don't compile "mallinfo". This can be a simple way
418   of dealing with mismatches between system declarations and
419   those in this file.
420
421 MALLINFO_FIELD_TYPE        default: size_t
422   The type of the fields in the mallinfo struct. This was originally
423   defined as "int" in SVID etc, but is more usefully defined as
424   size_t. The value is used only if  HAVE_USR_INCLUDE_MALLOC_H is not set
425
426 NO_MALLOC_STATS            default: 0
427   If defined, don't compile "malloc_stats". This avoids calls to
428   fprintf and bringing in stdio dependencies you might not want.
429
430 REALLOC_ZERO_BYTES_FREES    default: not defined
431   This should be set if a call to realloc with zero bytes should
432   be the same as a call to free. Some people think it should. Otherwise,
433   since this malloc returns a unique pointer for malloc(0), so does
434   realloc(p, 0).
435
436 LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
437 LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H,  LACKS_ERRNO_H
438 LACKS_STDLIB_H LACKS_SCHED_H LACKS_TIME_H  default: NOT defined unless on WIN32
439   Define these if your system does not have these header files.
440   You might need to manually insert some of the declarations they provide.
441
442 DEFAULT_GRANULARITY        default: page size if MORECORE_CONTIGUOUS,
443                                 system_info.dwAllocationGranularity in WIN32,
444                                 otherwise 64K.
445       Also settable using mallopt(M_GRANULARITY, x)
446   The unit for allocating and deallocating memory from the system.  On
447   most systems with contiguous MORECORE, there is no reason to
448   make this more than a page. However, systems with MMAP tend to
449   either require or encourage larger granularities.  You can increase
450   this value to prevent system allocation functions to be called so
451   often, especially if they are slow.  The value must be at least one
452   page and must be a power of two.  Setting to 0 causes initialization
453   to either page size or win32 region size.  (Note: In previous
454   versions of malloc, the equivalent of this option was called
455   "TOP_PAD")
456
457 DEFAULT_TRIM_THRESHOLD    default: 2MB
458       Also settable using mallopt(M_TRIM_THRESHOLD, x)
459   The maximum amount of unused top-most memory to keep before
460   releasing via malloc_trim in free().  Automatic trimming is mainly
461   useful in long-lived programs using contiguous MORECORE.  Because
462   trimming via sbrk can be slow on some systems, and can sometimes be
463   wasteful (in cases where programs immediately afterward allocate
464   more large chunks) the value should be high enough so that your
465   overall system performance would improve by releasing this much
466   memory.  As a rough guide, you might set to a value close to the
467   average size of a process (program) running on your system.
468   Releasing this much memory would allow such a process to run in
469   memory.  Generally, it is worth tuning trim thresholds when a
470   program undergoes phases where several large chunks are allocated
471   and released in ways that can reuse each other's storage, perhaps
472   mixed with phases where there are no such chunks at all. The trim
473   value must be greater than page size to have any useful effect.  To
474   disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
475   some people use of mallocing a huge space and then freeing it at
476   program startup, in an attempt to reserve system memory, doesn't
477   have the intended effect under automatic trimming, since that memory
478   will immediately be returned to the system.
479
480 DEFAULT_MMAP_THRESHOLD       default: 256K
481       Also settable using mallopt(M_MMAP_THRESHOLD, x)
482   The request size threshold for using MMAP to directly service a
483   request. Requests of at least this size that cannot be allocated
484   using already-existing space will be serviced via mmap.  (If enough
485   normal freed space already exists it is used instead.)  Using mmap
486   segregates relatively large chunks of memory so that they can be
487   individually obtained and released from the host system. A request
488   serviced through mmap is never reused by any other request (at least
489   not directly; the system may just so happen to remap successive
490   requests to the same locations).  Segregating space in this way has
491   the benefits that: Mmapped space can always be individually released
492   back to the system, which helps keep the system level memory demands
493   of a long-lived program low.  Also, mapped memory doesn't become
494   `locked' between other chunks, as can happen with normally allocated
495   chunks, which means that even trimming via malloc_trim would not
496   release them.  However, it has the disadvantage that the space
497   cannot be reclaimed, consolidated, and then used to service later
498   requests, as happens with normal chunks.  The advantages of mmap
499   nearly always outweigh disadvantages for "large" chunks, but the
500   value of "large" may vary across systems.  The default is an
501   empirically derived value that works well in most systems. You can
502   disable mmap by setting to MAX_SIZE_T.
503
504 MAX_RELEASE_CHECK_RATE   default: 4095 unless not HAVE_MMAP
505   The number of consolidated frees between checks to release
506   unused segments when freeing. When using non-contiguous segments,
507   especially with multiple mspaces, checking only for topmost space
508   doesn't always suffice to trigger trimming. To compensate for this,
509   free() will, with a period of MAX_RELEASE_CHECK_RATE (or the
510   current number of segments, if greater) try to release unused
511   segments to the OS when freeing chunks that result in
512   consolidation. The best value for this parameter is a compromise
513   between slowing down frees with relatively costly checks that
514   rarely trigger versus holding on to unused memory. To effectively
515   disable, set to MAX_SIZE_T. This may lead to a very slight speed
516   improvement at the expense of carrying around more memory.
517 */
518
519 /* Version identifier to allow people to support multiple versions */
520 #ifndef DLMALLOC_VERSION
521 #define DLMALLOC_VERSION 20805
522 #endif /* DLMALLOC_VERSION */
523
524 #ifndef DLMALLOC_EXPORT
525 #define DLMALLOC_EXPORT extern
526 #endif
527
528 #ifndef WIN32
529 #ifdef _WIN32
530 #define WIN32 1
531 #endif  /* _WIN32 */
532 #ifdef _WIN32_WCE
533 #define LACKS_FCNTL_H
534 #define WIN32 1
535 #endif /* _WIN32_WCE */
536 #endif  /* WIN32 */
537 #ifdef WIN32
538 #define WIN32_LEAN_AND_MEAN
539 #include <windows.h>
540 #include <tchar.h>
541 #define HAVE_MMAP 1
542 #define HAVE_MORECORE 0
543 #define LACKS_UNISTD_H
544 #define LACKS_SYS_PARAM_H
545 #define LACKS_SYS_MMAN_H
546 #define LACKS_STRING_H
547 #define LACKS_STRINGS_H
548 #define LACKS_SYS_TYPES_H
549 #define LACKS_ERRNO_H
550 #define LACKS_SCHED_H
551 #ifndef MALLOC_FAILURE_ACTION
552 #define MALLOC_FAILURE_ACTION
553 #endif /* MALLOC_FAILURE_ACTION */
554 #ifndef MMAP_CLEARS
555 #ifdef _WIN32_WCE /* WINCE reportedly does not clear */
556 #define MMAP_CLEARS 0
557 #else
558 #define MMAP_CLEARS 1
559 #endif /* _WIN32_WCE */
560 #endif /*MMAP_CLEARS */
561 #endif  /* WIN32 */
562
563 #if defined(DARWIN) || defined(_DARWIN)
564 /* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
565 #ifndef HAVE_MORECORE
566 #define HAVE_MORECORE 0
567 #define HAVE_MMAP 1
568 /* OSX allocators provide 16 byte alignment */
569 #ifndef MALLOC_ALIGNMENT
570 #define MALLOC_ALIGNMENT ((size_t)16U)
571 #endif
572 #endif  /* HAVE_MORECORE */
573 #endif  /* DARWIN */
574
575 #ifndef LACKS_SYS_TYPES_H
576 #include <sys/types.h>  /* For size_t */
577 #endif  /* LACKS_SYS_TYPES_H */
578
579 /* The maximum possible size_t value has all bits set */
580 #define MAX_SIZE_T           (~(size_t)0)
581
582 #ifndef USE_LOCKS /* ensure true if spin or recursive locks set */
583 #define USE_LOCKS  ((defined(USE_SPIN_LOCKS) && USE_SPIN_LOCKS != 0) || \
584                     (defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0))
585 #endif /* USE_LOCKS */
586
587 #if USE_LOCKS /* Spin locks for gcc >= 4.1, older gcc on x86, MSC >= 1310 */
588 #if ((defined(__GNUC__) &&                                              \
589       ((__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)) ||      \
590        defined(__i386__) || defined(__x86_64__))) ||                    \
591      (defined(_MSC_VER) && _MSC_VER>=1310))
592 #ifndef USE_SPIN_LOCKS
593 #define USE_SPIN_LOCKS 1
594 #endif /* USE_SPIN_LOCKS */
595 #elif USE_SPIN_LOCKS
596 #error "USE_SPIN_LOCKS defined without implementation"
597 #endif /* ... locks available... */
598 #elif !defined(USE_SPIN_LOCKS)
599 #define USE_SPIN_LOCKS 0
600 #endif /* USE_LOCKS */
601
602 #ifndef ONLY_MSPACES
603 #define ONLY_MSPACES 0
604 #endif  /* ONLY_MSPACES */
605 #ifndef MSPACES
606 #if ONLY_MSPACES
607 #define MSPACES 1
608 #else   /* ONLY_MSPACES */
609 #define MSPACES 0
610 #endif  /* ONLY_MSPACES */
611 #endif  /* MSPACES */
612 #ifndef MALLOC_ALIGNMENT
613 #define MALLOC_ALIGNMENT ((size_t)8U)
614 #endif  /* MALLOC_ALIGNMENT */
615 #ifndef FOOTERS
616 #define FOOTERS 0
617 #endif  /* FOOTERS */
618 #ifndef ABORT
619 #define ABORT  abort()
620 #endif  /* ABORT */
621 #ifndef ABORT_ON_ASSERT_FAILURE
622 #define ABORT_ON_ASSERT_FAILURE 1
623 #endif  /* ABORT_ON_ASSERT_FAILURE */
624 #ifndef PROCEED_ON_ERROR
625 #define PROCEED_ON_ERROR 0
626 #endif  /* PROCEED_ON_ERROR */
627
628 #ifndef INSECURE
629 #define INSECURE 0
630 #endif  /* INSECURE */
631 #ifndef MALLOC_INSPECT_ALL
632 #define MALLOC_INSPECT_ALL 0
633 #endif  /* MALLOC_INSPECT_ALL */
634 #ifndef HAVE_MMAP
635 #define HAVE_MMAP 1
636 #endif  /* HAVE_MMAP */
637 #ifndef MMAP_CLEARS
638 #define MMAP_CLEARS 1
639 #endif  /* MMAP_CLEARS */
640 #ifndef HAVE_MREMAP
641 #ifdef linux
642 #define HAVE_MREMAP 1
643 #define _GNU_SOURCE /* Turns on mremap() definition */
644 #else   /* linux */
645 #define HAVE_MREMAP 0
646 #endif  /* linux */
647 #endif  /* HAVE_MREMAP */
648 #ifndef MALLOC_FAILURE_ACTION
649 #define MALLOC_FAILURE_ACTION  errno = ENOMEM;
650 #endif  /* MALLOC_FAILURE_ACTION */
651 #ifndef HAVE_MORECORE
652 #if ONLY_MSPACES
653 #define HAVE_MORECORE 0
654 #else   /* ONLY_MSPACES */
655 #define HAVE_MORECORE 1
656 #endif  /* ONLY_MSPACES */
657 #endif  /* HAVE_MORECORE */
658 #if !HAVE_MORECORE
659 #define MORECORE_CONTIGUOUS 0
660 #else   /* !HAVE_MORECORE */
661 #define MORECORE_DEFAULT sbrk
662 #ifndef MORECORE_CONTIGUOUS
663 #define MORECORE_CONTIGUOUS 1
664 #endif  /* MORECORE_CONTIGUOUS */
665 #endif  /* HAVE_MORECORE */
666 #ifndef DEFAULT_GRANULARITY
667 #if (MORECORE_CONTIGUOUS || defined(WIN32))
668 #define DEFAULT_GRANULARITY (0)  /* 0 means to compute in init_mparams */
669 #else   /* MORECORE_CONTIGUOUS */
670 #define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
671 #endif  /* MORECORE_CONTIGUOUS */
672 #endif  /* DEFAULT_GRANULARITY */
673 #ifndef DEFAULT_TRIM_THRESHOLD
674 #ifndef MORECORE_CANNOT_TRIM
675 #define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
676 #else   /* MORECORE_CANNOT_TRIM */
677 #define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
678 #endif  /* MORECORE_CANNOT_TRIM */
679 #endif  /* DEFAULT_TRIM_THRESHOLD */
680 #ifndef DEFAULT_MMAP_THRESHOLD
681 #if HAVE_MMAP
682 #define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
683 #else   /* HAVE_MMAP */
684 #define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
685 #endif  /* HAVE_MMAP */
686 #endif  /* DEFAULT_MMAP_THRESHOLD */
687 #ifndef MAX_RELEASE_CHECK_RATE
688 #if HAVE_MMAP
689 #define MAX_RELEASE_CHECK_RATE 4095
690 #else
691 #define MAX_RELEASE_CHECK_RATE MAX_SIZE_T
692 #endif /* HAVE_MMAP */
693 #endif /* MAX_RELEASE_CHECK_RATE */
694 #ifndef USE_BUILTIN_FFS
695 #define USE_BUILTIN_FFS 0
696 #endif  /* USE_BUILTIN_FFS */
697 #ifndef USE_DEV_RANDOM
698 #define USE_DEV_RANDOM 0
699 #endif  /* USE_DEV_RANDOM */
700 #ifndef NO_MALLINFO
701 #define NO_MALLINFO 0
702 #endif  /* NO_MALLINFO */
703 #ifndef MALLINFO_FIELD_TYPE
704 #define MALLINFO_FIELD_TYPE size_t
705 #endif  /* MALLINFO_FIELD_TYPE */
706 #ifndef NO_MALLOC_STATS
707 #define NO_MALLOC_STATS 0
708 #endif  /* NO_MALLOC_STATS */
709 #ifndef NO_SEGMENT_TRAVERSAL
710 #define NO_SEGMENT_TRAVERSAL 0
711 #endif /* NO_SEGMENT_TRAVERSAL */
712
713 /*
714   mallopt tuning options.  SVID/XPG defines four standard parameter
715   numbers for mallopt, normally defined in malloc.h.  None of these
716   are used in this malloc, so setting them has no effect. But this
717   malloc does support the following options.
718 */
719
720 #define M_TRIM_THRESHOLD     (-1)
721 #define M_GRANULARITY        (-2)
722 #define M_MMAP_THRESHOLD     (-3)
723
724 /* ------------------------ Mallinfo declarations ------------------------ */
725
726 #if !NO_MALLINFO
727 /*
728   This version of malloc supports the standard SVID/XPG mallinfo
729   routine that returns a struct containing usage properties and
730   statistics. It should work on any system that has a
731   /usr/include/malloc.h defining struct mallinfo.  The main
732   declaration needed is the mallinfo struct that is returned (by-copy)
733   by mallinfo().  The malloinfo struct contains a bunch of fields that
734   are not even meaningful in this version of malloc.  These fields are
735   are instead filled by mallinfo() with other numbers that might be of
736   interest.
737
738   HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
739   /usr/include/malloc.h file that includes a declaration of struct
740   mallinfo.  If so, it is included; else a compliant version is
741   declared below.  These must be precisely the same for mallinfo() to
742   work.  The original SVID version of this struct, defined on most
743   systems with mallinfo, declares all fields as ints. But some others
744   define as unsigned long. If your system defines the fields using a
745   type of different width than listed here, you MUST #include your
746   system version and #define HAVE_USR_INCLUDE_MALLOC_H.
747 */
748
749 /* #define HAVE_USR_INCLUDE_MALLOC_H */
750
751 #ifdef HAVE_USR_INCLUDE_MALLOC_H
752 #include "/usr/include/malloc.h"
753 #else /* HAVE_USR_INCLUDE_MALLOC_H */
754 #ifndef STRUCT_MALLINFO_DECLARED
755 /* HP-UX (and others?) redefines mallinfo unless _STRUCT_MALLINFO is defined */
756 #define _STRUCT_MALLINFO
757 #define STRUCT_MALLINFO_DECLARED 1
758 struct mallinfo {
759   MALLINFO_FIELD_TYPE arena;    /* non-mmapped space allocated from system */
760   MALLINFO_FIELD_TYPE ordblks;  /* number of free chunks */
761   MALLINFO_FIELD_TYPE smblks;   /* always 0 */
762   MALLINFO_FIELD_TYPE hblks;    /* always 0 */
763   MALLINFO_FIELD_TYPE hblkhd;   /* space in mmapped regions */
764   MALLINFO_FIELD_TYPE usmblks;  /* maximum total allocated space */
765   MALLINFO_FIELD_TYPE fsmblks;  /* always 0 */
766   MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
767   MALLINFO_FIELD_TYPE fordblks; /* total free space */
768   MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
769 };
770 #endif /* STRUCT_MALLINFO_DECLARED */
771 #endif /* HAVE_USR_INCLUDE_MALLOC_H */
772 #endif /* NO_MALLINFO */
773
774 /*
775   Try to persuade compilers to inline. The most critical functions for
776   inlining are defined as macros, so these aren't used for them.
777 */
778
779 #ifndef FORCEINLINE
780   #if defined(__GNUC__)
781 #define FORCEINLINE __inline __attribute__ ((always_inline))
782   #elif defined(_MSC_VER)
783     #define FORCEINLINE __forceinline
784   #endif
785 #endif
786 #ifndef NOINLINE
787   #if defined(__GNUC__)
788     #define NOINLINE __attribute__ ((noinline))
789   #elif defined(_MSC_VER)
790     #define NOINLINE __declspec(noinline)
791   #else
792     #define NOINLINE
793   #endif
794 #endif
795
796 #ifdef __cplusplus
797 extern "C" {
798 #ifndef FORCEINLINE
799  #define FORCEINLINE inline
800 #endif
801 #endif /* __cplusplus */
802 #ifndef FORCEINLINE
803  #define FORCEINLINE
804 #endif
805
806 #if !ONLY_MSPACES
807
808 /* ------------------- Declarations of public routines ------------------- */
809
810 #ifndef USE_DL_PREFIX
811 #define dlcalloc               calloc
812 #define dlfree                 free
813 #define dlmalloc               malloc
814 #define dlmemalign             memalign
815 #define dlposix_memalign       posix_memalign
816 #define dlrealloc              realloc
817 #define dlrealloc_in_place     realloc_in_place
818 #define dlvalloc               valloc
819 #define dlpvalloc              pvalloc
820 #define dlmallinfo             mallinfo
821 #define dlmallopt              mallopt
822 #define dlmalloc_trim          malloc_trim
823 #define dlmalloc_stats         malloc_stats
824 #define dlmalloc_usable_size   malloc_usable_size
825 #define dlmalloc_footprint     malloc_footprint
826 #define dlmalloc_max_footprint malloc_max_footprint
827 #define dlmalloc_footprint_limit malloc_footprint_limit
828 #define dlmalloc_set_footprint_limit malloc_set_footprint_limit
829 #define dlmalloc_inspect_all   malloc_inspect_all
830 #define dlindependent_calloc   independent_calloc
831 #define dlindependent_comalloc independent_comalloc
832 #define dlbulk_free            bulk_free
833 #endif /* USE_DL_PREFIX */
834
835 /*
836   malloc(size_t n)
837   Returns a pointer to a newly allocated chunk of at least n bytes, or
838   null if no space is available, in which case errno is set to ENOMEM
839   on ANSI C systems.
840
841   If n is zero, malloc returns a minimum-sized chunk. (The minimum
842   size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
843   systems.)  Note that size_t is an unsigned type, so calls with
844   arguments that would be negative if signed are interpreted as
845   requests for huge amounts of space, which will often fail. The
846   maximum supported value of n differs across systems, but is in all
847   cases less than the maximum representable value of a size_t.
848 */
849 DLMALLOC_EXPORT void* dlmalloc(size_t);
850
851 /*
852   free(void* p)
853   Releases the chunk of memory pointed to by p, that had been previously
854   allocated using malloc or a related routine such as realloc.
855   It has no effect if p is null. If p was not malloced or already
856   freed, free(p) will by default cause the current program to abort.
857 */
858 DLMALLOC_EXPORT void  dlfree(void*);
859
860 /*
861   calloc(size_t n_elements, size_t element_size);
862   Returns a pointer to n_elements * element_size bytes, with all locations
863   set to zero.
864 */
865 DLMALLOC_EXPORT void* dlcalloc(size_t, size_t);
866
867 /*
868   realloc(void* p, size_t n)
869   Returns a pointer to a chunk of size n that contains the same data
870   as does chunk p up to the minimum of (n, p's size) bytes, or null
871   if no space is available.
872
873   The returned pointer may or may not be the same as p. The algorithm
874   prefers extending p in most cases when possible, otherwise it
875   employs the equivalent of a malloc-copy-free sequence.
876
877   If p is null, realloc is equivalent to malloc.
878
879   If space is not available, realloc returns null, errno is set (if on
880   ANSI) and p is NOT freed.
881
882   if n is for fewer bytes than already held by p, the newly unused
883   space is lopped off and freed if possible.  realloc with a size
884   argument of zero (re)allocates a minimum-sized chunk.
885
886   The old unix realloc convention of allowing the last-free'd chunk
887   to be used as an argument to realloc is not supported.
888 */
889 DLMALLOC_EXPORT void* dlrealloc(void*, size_t);
890
891 /*
892   realloc_in_place(void* p, size_t n)
893   Resizes the space allocated for p to size n, only if this can be
894   done without moving p (i.e., only if there is adjacent space
895   available if n is greater than p's current allocated size, or n is
896   less than or equal to p's size). This may be used instead of plain
897   realloc if an alternative allocation strategy is needed upon failure
898   to expand space; for example, reallocation of a buffer that must be
899   memory-aligned or cleared. You can use realloc_in_place to trigger
900   these alternatives only when needed.
901
902   Returns p if successful; otherwise null.
903 */
904 DLMALLOC_EXPORT void* dlrealloc_in_place(void*, size_t);
905
906 /*
907   memalign(size_t alignment, size_t n);
908   Returns a pointer to a newly allocated chunk of n bytes, aligned
909   in accord with the alignment argument.
910
911   The alignment argument should be a power of two. If the argument is
912   not a power of two, the nearest greater power is used.
913   8-byte alignment is guaranteed by normal malloc calls, so don't
914   bother calling memalign with an argument of 8 or less.
915
916   Overreliance on memalign is a sure way to fragment space.
917 */
918 DLMALLOC_EXPORT void* dlmemalign(size_t, size_t);
919
920 /*
921   int posix_memalign(void** pp, size_t alignment, size_t n);
922   Allocates a chunk of n bytes, aligned in accord with the alignment
923   argument. Differs from memalign only in that it (1) assigns the
924   allocated memory to *pp rather than returning it, (2) fails and
925   returns EINVAL if the alignment is not a power of two (3) fails and
926   returns ENOMEM if memory cannot be allocated.
927 */
928 DLMALLOC_EXPORT int dlposix_memalign(void**, size_t, size_t);
929
930 /*
931   valloc(size_t n);
932   Equivalent to memalign(pagesize, n), where pagesize is the page
933   size of the system. If the pagesize is unknown, 4096 is used.
934 */
935 DLMALLOC_EXPORT void* dlvalloc(size_t);
936
937 /*
938   mallopt(int parameter_number, int parameter_value)
939   Sets tunable parameters The format is to provide a
940   (parameter-number, parameter-value) pair.  mallopt then sets the
941   corresponding parameter to the argument value if it can (i.e., so
942   long as the value is meaningful), and returns 1 if successful else
943   0.  To workaround the fact that mallopt is specified to use int,
944   not size_t parameters, the value -1 is specially treated as the
945   maximum unsigned size_t value.
946
947   SVID/XPG/ANSI defines four standard param numbers for mallopt,
948   normally defined in malloc.h.  None of these are use in this malloc,
949   so setting them has no effect. But this malloc also supports other
950   options in mallopt. See below for details.  Briefly, supported
951   parameters are as follows (listed defaults are for "typical"
952   configurations).
953
954   Symbol            param #  default    allowed param values
955   M_TRIM_THRESHOLD     -1   2*1024*1024   any   (-1 disables)
956   M_GRANULARITY        -2     page size   any power of 2 >= page size
957   M_MMAP_THRESHOLD     -3      256*1024   any   (or 0 if no MMAP support)
958 */
959 DLMALLOC_EXPORT int dlmallopt(int, int);
960
961 /*
962   malloc_footprint();
963   Returns the number of bytes obtained from the system.  The total
964   number of bytes allocated by malloc, realloc etc., is less than this
965   value. Unlike mallinfo, this function returns only a precomputed
966   result, so can be called frequently to monitor memory consumption.
967   Even if locks are otherwise defined, this function does not use them,
968   so results might not be up to date.
969 */
970 DLMALLOC_EXPORT size_t dlmalloc_footprint(void);
971
972 /*
973   malloc_max_footprint();
974   Returns the maximum number of bytes obtained from the system. This
975   value will be greater than current footprint if deallocated space
976   has been reclaimed by the system. The peak number of bytes allocated
977   by malloc, realloc etc., is less than this value. Unlike mallinfo,
978   this function returns only a precomputed result, so can be called
979   frequently to monitor memory consumption.  Even if locks are
980   otherwise defined, this function does not use them, so results might
981   not be up to date.
982 */
983 DLMALLOC_EXPORT size_t dlmalloc_max_footprint(void);
984
985 /*
986   malloc_footprint_limit();
987   Returns the number of bytes that the heap is allowed to obtain from
988   the system, returning the last value returned by
989   malloc_set_footprint_limit, or the maximum size_t value if
990   never set. The returned value reflects a permission. There is no
991   guarantee that this number of bytes can actually be obtained from
992   the system.
993 */
994 DLMALLOC_EXPORT size_t dlmalloc_footprint_limit();
995
996 /*
997   malloc_set_footprint_limit();
998   Sets the maximum number of bytes to obtain from the system, causing
999   failure returns from malloc and related functions upon attempts to
1000   exceed this value. The argument value may be subject to page
1001   rounding to an enforceable limit; this actual value is returned.
1002   Using an argument of the maximum possible size_t effectively
1003   disables checks. If the argument is less than or equal to the
1004   current malloc_footprint, then all future allocations that require
1005   additional system memory will fail. However, invocation cannot
1006   retroactively deallocate existing used memory.
1007 */
1008 DLMALLOC_EXPORT size_t dlmalloc_set_footprint_limit(size_t bytes);
1009
1010 #if MALLOC_INSPECT_ALL
1011 /*
1012   malloc_inspect_all(void(*handler)(void *start,
1013                                     void *end,
1014                                     size_t used_bytes,
1015                                     void* callback_arg),
1016                       void* arg);
1017   Traverses the heap and calls the given handler for each managed
1018   region, skipping all bytes that are (or may be) used for bookkeeping
1019   purposes.  Traversal does not include include chunks that have been
1020   directly memory mapped. Each reported region begins at the start
1021   address, and continues up to but not including the end address.  The
1022   first used_bytes of the region contain allocated data. If
1023   used_bytes is zero, the region is unallocated. The handler is
1024   invoked with the given callback argument. If locks are defined, they
1025   are held during the entire traversal. It is a bad idea to invoke
1026   other malloc functions from within the handler.
1027
1028   For example, to count the number of in-use chunks with size greater
1029   than 1000, you could write:
1030   static int count = 0;
1031   void count_chunks(void* start, void* end, size_t used, void* arg) {
1032     if (used >= 1000) ++count;
1033   }
1034   then:
1035     malloc_inspect_all(count_chunks, NULL);
1036
1037   malloc_inspect_all is compiled only if MALLOC_INSPECT_ALL is defined.
1038 */
1039 DLMALLOC_EXPORT void dlmalloc_inspect_all(void(*handler)(void*, void *, size_t, void*),
1040                            void* arg);
1041
1042 #endif /* MALLOC_INSPECT_ALL */
1043
1044 #if !NO_MALLINFO
1045 /*
1046   mallinfo()
1047   Returns (by copy) a struct containing various summary statistics:
1048
1049   arena:     current total non-mmapped bytes allocated from system
1050   ordblks:   the number of free chunks
1051   smblks:    always zero.
1052   hblks:     current number of mmapped regions
1053   hblkhd:    total bytes held in mmapped regions
1054   usmblks:   the maximum total allocated space. This will be greater
1055                 than current total if trimming has occurred.
1056   fsmblks:   always zero
1057   uordblks:  current total allocated space (normal or mmapped)
1058   fordblks:  total free space
1059   keepcost:  the maximum number of bytes that could ideally be released
1060                back to system via malloc_trim. ("ideally" means that
1061                it ignores page restrictions etc.)
1062
1063   Because these fields are ints, but internal bookkeeping may
1064   be kept as longs, the reported values may wrap around zero and
1065   thus be inaccurate.
1066 */
1067 DLMALLOC_EXPORT struct mallinfo dlmallinfo(void);
1068 #endif /* NO_MALLINFO */
1069
1070 /*
1071   independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
1072
1073   independent_calloc is similar to calloc, but instead of returning a
1074   single cleared space, it returns an array of pointers to n_elements
1075   independent elements that can hold contents of size elem_size, each
1076   of which starts out cleared, and can be independently freed,
1077   realloc'ed etc. The elements are guaranteed to be adjacently
1078   allocated (this is not guaranteed to occur with multiple callocs or
1079   mallocs), which may also improve cache locality in some
1080   applications.
1081
1082   The "chunks" argument is optional (i.e., may be null, which is
1083   probably the most typical usage). If it is null, the returned array
1084   is itself dynamically allocated and should also be freed when it is
1085   no longer needed. Otherwise, the chunks array must be of at least
1086   n_elements in length. It is filled in with the pointers to the
1087   chunks.
1088
1089   In either case, independent_calloc returns this pointer array, or
1090   null if the allocation failed.  If n_elements is zero and "chunks"
1091   is null, it returns a chunk representing an array with zero elements
1092   (which should be freed if not wanted).
1093
1094   Each element must be freed when it is no longer needed. This can be
1095   done all at once using bulk_free.
1096
1097   independent_calloc simplifies and speeds up implementations of many
1098   kinds of pools.  It may also be useful when constructing large data
1099   structures that initially have a fixed number of fixed-sized nodes,
1100   but the number is not known at compile time, and some of the nodes
1101   may later need to be freed. For example:
1102
1103   struct Node { int item; struct Node* next; };
1104
1105   struct Node* build_list() {
1106     struct Node** pool;
1107     int n = read_number_of_nodes_needed();
1108     if (n <= 0) return 0;
1109     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
1110     if (pool == 0) die();
1111     // organize into a linked list...
1112     struct Node* first = pool[0];
1113     for (i = 0; i < n-1; ++i)
1114       pool[i]->next = pool[i+1];
1115     free(pool);     // Can now free the array (or not, if it is needed later)
1116     return first;
1117   }
1118 */
1119 DLMALLOC_EXPORT void** dlindependent_calloc(size_t, size_t, void**);
1120
1121 /*
1122   independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
1123
1124   independent_comalloc allocates, all at once, a set of n_elements
1125   chunks with sizes indicated in the "sizes" array.    It returns
1126   an array of pointers to these elements, each of which can be
1127   independently freed, realloc'ed etc. The elements are guaranteed to
1128   be adjacently allocated (this is not guaranteed to occur with
1129   multiple callocs or mallocs), which may also improve cache locality
1130   in some applications.
1131
1132   The "chunks" argument is optional (i.e., may be null). If it is null
1133   the returned array is itself dynamically allocated and should also
1134   be freed when it is no longer needed. Otherwise, the chunks array
1135   must be of at least n_elements in length. It is filled in with the
1136   pointers to the chunks.
1137
1138   In either case, independent_comalloc returns this pointer array, or
1139   null if the allocation failed.  If n_elements is zero and chunks is
1140   null, it returns a chunk representing an array with zero elements
1141   (which should be freed if not wanted).
1142
1143   Each element must be freed when it is no longer needed. This can be
1144   done all at once using bulk_free.
1145
1146   independent_comallac differs from independent_calloc in that each
1147   element may have a different size, and also that it does not
1148   automatically clear elements.
1149
1150   independent_comalloc can be used to speed up allocation in cases
1151   where several structs or objects must always be allocated at the
1152   same time.  For example:
1153
1154   struct Head { ... }
1155   struct Foot { ... }
1156
1157   void send_message(char* msg) {
1158     int msglen = strlen(msg);
1159     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1160     void* chunks[3];
1161     if (independent_comalloc(3, sizes, chunks) == 0)
1162       die();
1163     struct Head* head = (struct Head*)(chunks[0]);
1164     char*        body = (char*)(chunks[1]);
1165     struct Foot* foot = (struct Foot*)(chunks[2]);
1166     // ...
1167   }
1168
1169   In general though, independent_comalloc is worth using only for
1170   larger values of n_elements. For small values, you probably won't
1171   detect enough difference from series of malloc calls to bother.
1172
1173   Overuse of independent_comalloc can increase overall memory usage,
1174   since it cannot reuse existing noncontiguous small chunks that
1175   might be available for some of the elements.
1176 */
1177 DLMALLOC_EXPORT void** dlindependent_comalloc(size_t, size_t*, void**);
1178
1179 /*
1180   bulk_free(void* array[], size_t n_elements)
1181   Frees and clears (sets to null) each non-null pointer in the given
1182   array.  This is likely to be faster than freeing them one-by-one.
1183   If footers are used, pointers that have been allocated in different
1184   mspaces are not freed or cleared, and the count of all such pointers
1185   is returned.  For large arrays of pointers with poor locality, it
1186   may be worthwhile to sort this array before calling bulk_free.
1187 */
1188 DLMALLOC_EXPORT size_t  dlbulk_free(void**, size_t n_elements);
1189
1190 /*
1191   pvalloc(size_t n);
1192   Equivalent to valloc(minimum-page-that-holds(n)), that is,
1193   round up n to nearest pagesize.
1194  */
1195 DLMALLOC_EXPORT void*  dlpvalloc(size_t);
1196
1197 /*
1198   malloc_trim(size_t pad);
1199
1200   If possible, gives memory back to the system (via negative arguments
1201   to sbrk) if there is unused memory at the `high' end of the malloc
1202   pool or in unused MMAP segments. You can call this after freeing
1203   large blocks of memory to potentially reduce the system-level memory
1204   requirements of a program. However, it cannot guarantee to reduce
1205   memory. Under some allocation patterns, some large free blocks of
1206   memory will be locked between two used chunks, so they cannot be
1207   given back to the system.
1208
1209   The `pad' argument to malloc_trim represents the amount of free
1210   trailing space to leave untrimmed. If this argument is zero, only
1211   the minimum amount of memory to maintain internal data structures
1212   will be left. Non-zero arguments can be supplied to maintain enough
1213   trailing space to service future expected allocations without having
1214   to re-obtain memory from the system.
1215
1216   Malloc_trim returns 1 if it actually released any memory, else 0.
1217 */
1218 DLMALLOC_EXPORT int  dlmalloc_trim(size_t);
1219
1220 /*
1221   malloc_stats();
1222   Prints on stderr the amount of space obtained from the system (both
1223   via sbrk and mmap), the maximum amount (which may be more than
1224   current if malloc_trim and/or munmap got called), and the current
1225   number of bytes allocated via malloc (or realloc, etc) but not yet
1226   freed. Note that this is the number of bytes allocated, not the
1227   number requested. It will be larger than the number requested
1228   because of alignment and bookkeeping overhead. Because it includes
1229   alignment wastage as being in use, this figure may be greater than
1230   zero even when no user-level chunks are allocated.
1231
1232   The reported current and maximum system memory can be inaccurate if
1233   a program makes other calls to system memory allocation functions
1234   (normally sbrk) outside of malloc.
1235
1236   malloc_stats prints only the most commonly interesting statistics.
1237   More information can be obtained by calling mallinfo.
1238 */
1239 DLMALLOC_EXPORT void  dlmalloc_stats(void);
1240
1241 #endif /* ONLY_MSPACES */
1242
1243 /*
1244   malloc_usable_size(void* p);
1245
1246   Returns the number of bytes you can actually use in
1247   an allocated chunk, which may be more than you requested (although
1248   often not) due to alignment and minimum size constraints.
1249   You can use this many bytes without worrying about
1250   overwriting other allocated objects. This is not a particularly great
1251   programming practice. malloc_usable_size can be more useful in
1252   debugging and assertions, for example:
1253
1254   p = malloc(n);
1255   assert(malloc_usable_size(p) >= 256);
1256 */
1257 size_t dlmalloc_usable_size(void*);
1258
1259 #if MSPACES
1260
1261 /*
1262   mspace is an opaque type representing an independent
1263   region of space that supports mspace_malloc, etc.
1264 */
1265 typedef void* mspace;
1266
1267 /*
1268   create_mspace creates and returns a new independent space with the
1269   given initial capacity, or, if 0, the default granularity size.  It
1270   returns null if there is no system memory available to create the
1271   space.  If argument locked is non-zero, the space uses a separate
1272   lock to control access. The capacity of the space will grow
1273   dynamically as needed to service mspace_malloc requests.  You can
1274   control the sizes of incremental increases of this space by
1275   compiling with a different DEFAULT_GRANULARITY or dynamically
1276   setting with mallopt(M_GRANULARITY, value).
1277 */
1278 DLMALLOC_EXPORT mspace create_mspace(size_t capacity, int locked);
1279
1280 /*
1281   destroy_mspace destroys the given space, and attempts to return all
1282   of its memory back to the system, returning the total number of
1283   bytes freed. After destruction, the results of access to all memory
1284   used by the space become undefined.
1285 */
1286 DLMALLOC_EXPORT size_t destroy_mspace(mspace msp);
1287
1288 /*
1289   create_mspace_with_base uses the memory supplied as the initial base
1290   of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
1291   space is used for bookkeeping, so the capacity must be at least this
1292   large. (Otherwise 0 is returned.) When this initial space is
1293   exhausted, additional memory will be obtained from the system.
1294   Destroying this space will deallocate all additionally allocated
1295   space (if possible) but not the initial base.
1296 */
1297 DLMALLOC_EXPORT mspace create_mspace_with_base(void* base, size_t capacity, int locked);
1298
1299 /*
1300   mspace_track_large_chunks controls whether requests for large chunks
1301   are allocated in their own untracked mmapped regions, separate from
1302   others in this mspace. By default large chunks are not tracked,
1303   which reduces fragmentation. However, such chunks are not
1304   necessarily released to the system upon destroy_mspace.  Enabling
1305   tracking by setting to true may increase fragmentation, but avoids
1306   leakage when relying on destroy_mspace to release all memory
1307   allocated using this space.  The function returns the previous
1308   setting.
1309 */
1310 DLMALLOC_EXPORT int mspace_track_large_chunks(mspace msp, int enable);
1311
1312
1313 /*
1314   mspace_malloc behaves as malloc, but operates within
1315   the given space.
1316 */
1317 DLMALLOC_EXPORT void* mspace_malloc(mspace msp, size_t bytes);
1318
1319 /*
1320   mspace_free behaves as free, but operates within
1321   the given space.
1322
1323   If compiled with FOOTERS==1, mspace_free is not actually needed.
1324   free may be called instead of mspace_free because freed chunks from
1325   any space are handled by their originating spaces.
1326 */
1327 DLMALLOC_EXPORT void mspace_free(mspace msp, void* mem);
1328
1329 /*
1330   mspace_realloc behaves as realloc, but operates within
1331   the given space.
1332
1333   If compiled with FOOTERS==1, mspace_realloc is not actually
1334   needed.  realloc may be called instead of mspace_realloc because
1335   realloced chunks from any space are handled by their originating
1336   spaces.
1337 */
1338 DLMALLOC_EXPORT void* mspace_realloc(mspace msp, void* mem, size_t newsize);
1339
1340 /*
1341   mspace_calloc behaves as calloc, but operates within
1342   the given space.
1343 */
1344 DLMALLOC_EXPORT void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
1345
1346 /*
1347   mspace_memalign behaves as memalign, but operates within
1348   the given space.
1349 */
1350 DLMALLOC_EXPORT void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);
1351
1352 /*
1353   mspace_independent_calloc behaves as independent_calloc, but
1354   operates within the given space.
1355 */
1356 DLMALLOC_EXPORT void** mspace_independent_calloc(mspace msp, size_t n_elements,
1357                                  size_t elem_size, void* chunks[]);
1358
1359 /*
1360   mspace_independent_comalloc behaves as independent_comalloc, but
1361   operates within the given space.
1362 */
1363 DLMALLOC_EXPORT void** mspace_independent_comalloc(mspace msp, size_t n_elements,
1364                                    size_t sizes[], void* chunks[]);
1365
1366 /*
1367   mspace_footprint() returns the number of bytes obtained from the
1368   system for this space.
1369 */
1370 DLMALLOC_EXPORT size_t mspace_footprint(mspace msp);
1371
1372 /*
1373   mspace_max_footprint() returns the peak number of bytes obtained from the
1374   system for this space.
1375 */
1376 DLMALLOC_EXPORT size_t mspace_max_footprint(mspace msp);
1377
1378
1379 #if !NO_MALLINFO
1380 /*
1381   mspace_mallinfo behaves as mallinfo, but reports properties of
1382   the given space.
1383 */
1384 DLMALLOC_EXPORT struct mallinfo mspace_mallinfo(mspace msp);
1385 #endif /* NO_MALLINFO */
1386
1387 /*
1388   malloc_usable_size(void* p) behaves the same as malloc_usable_size;
1389 */
1390 DLMALLOC_EXPORT size_t mspace_usable_size(void* mem);
1391
1392 /*
1393   mspace_malloc_stats behaves as malloc_stats, but reports
1394   properties of the given space.
1395 */
1396 DLMALLOC_EXPORT void mspace_malloc_stats(mspace msp);
1397
1398 /*
1399   mspace_trim behaves as malloc_trim, but
1400   operates within the given space.
1401 */
1402 DLMALLOC_EXPORT int mspace_trim(mspace msp, size_t pad);
1403
1404 /*
1405   An alias for mallopt.
1406 */
1407 DLMALLOC_EXPORT int mspace_mallopt(int, int);
1408
1409 #endif /* MSPACES */
1410
1411 #ifdef __cplusplus
1412 }  /* end of extern "C" */
1413 #endif /* __cplusplus */
1414
1415 /*
1416   ========================================================================
1417   To make a fully customizable malloc.h header file, cut everything
1418   above this line, put into file malloc.h, edit to suit, and #include it
1419   on the next line, as well as in programs that use this malloc.
1420   ========================================================================
1421 */
1422
1423 /* #include "malloc.h" */
1424
1425 /*------------------------------ internal #includes ---------------------- */
1426
1427 #ifdef _MSC_VER
1428 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
1429 #endif /* _MSC_VER */
1430 #if !NO_MALLOC_STATS
1431 #include <stdio.h>       /* for printing in malloc_stats */
1432 #endif /* NO_MALLOC_STATS */
1433 #ifndef LACKS_ERRNO_H
1434 #include <errno.h>       /* for MALLOC_FAILURE_ACTION */
1435 #endif /* LACKS_ERRNO_H */
1436 #ifdef DEBUG
1437 #if ABORT_ON_ASSERT_FAILURE
1438 #undef assert
1439 #define assert(x) if(!(x)) ABORT
1440 #else /* ABORT_ON_ASSERT_FAILURE */
1441 #include <assert.h>
1442 #endif /* ABORT_ON_ASSERT_FAILURE */
1443 #else  /* DEBUG */
1444 #ifndef assert
1445 #define assert(x)
1446 #endif
1447 #define DEBUG 0
1448 #endif /* DEBUG */
1449 #if !defined(WIN32) && !defined(LACKS_TIME_H)
1450 #include <time.h>        /* for magic initialization */
1451 #endif /* WIN32 */
1452 #ifndef LACKS_STDLIB_H
1453 #include <stdlib.h>      /* for abort() */
1454 #endif /* LACKS_STDLIB_H */
1455 #ifndef LACKS_STRING_H
1456 #include <string.h>      /* for memset etc */
1457 #endif  /* LACKS_STRING_H */
1458 #if USE_BUILTIN_FFS
1459 #ifndef LACKS_STRINGS_H
1460 #include <strings.h>     /* for ffs */
1461 #endif /* LACKS_STRINGS_H */
1462 #endif /* USE_BUILTIN_FFS */
1463 #if HAVE_MMAP
1464 #ifndef LACKS_SYS_MMAN_H
1465 /* On some versions of linux, mremap decl in mman.h needs __USE_GNU set */
1466 #if (defined(linux) && !defined(__USE_GNU))
1467 #define __USE_GNU 1
1468 #include <sys/mman.h>    /* for mmap */
1469 #undef __USE_GNU
1470 #else
1471 #include <sys/mman.h>    /* for mmap */
1472 #endif /* linux */
1473 #endif /* LACKS_SYS_MMAN_H */
1474 #ifndef LACKS_FCNTL_H
1475 #include <fcntl.h>
1476 #endif /* LACKS_FCNTL_H */
1477 #endif /* HAVE_MMAP */
1478 #ifndef LACKS_UNISTD_H
1479 #include <unistd.h>     /* for sbrk, sysconf */
1480 #else /* LACKS_UNISTD_H */
1481 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
1482 extern void*     sbrk(ptrdiff_t);
1483 #endif /* FreeBSD etc */
1484 #endif /* LACKS_UNISTD_H */
1485
1486 /* Declarations for locking */
1487 #if USE_LOCKS
1488 #ifndef WIN32
1489 #if defined (__SVR4) && defined (__sun)  /* solaris */
1490 #include <thread.h>
1491 #elif !defined(LACKS_SCHED_H)
1492 #include <sched.h>
1493 #endif /* solaris or LACKS_SCHED_H */
1494 #if (defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0) || !USE_SPIN_LOCKS
1495 #include <pthread.h>
1496 #endif /* USE_RECURSIVE_LOCKS ... */
1497 #elif defined(_MSC_VER)
1498 #ifndef _M_AMD64
1499 /* These are already defined on AMD64 builds */
1500 #ifdef __cplusplus
1501 extern "C" {
1502 #endif /* __cplusplus */
1503 LONG __cdecl _InterlockedCompareExchange(LONG volatile *Dest, LONG Exchange, LONG Comp);
1504 LONG __cdecl _InterlockedExchange(LONG volatile *Target, LONG Value);
1505 #ifdef __cplusplus
1506 }
1507 #endif /* __cplusplus */
1508 #endif /* _M_AMD64 */
1509 #pragma intrinsic (_InterlockedCompareExchange)
1510 #pragma intrinsic (_InterlockedExchange)
1511 #define interlockedcompareexchange _InterlockedCompareExchange
1512 #define interlockedexchange _InterlockedExchange
1513 #elif defined(WIN32) && defined(__GNUC__)
1514 #define interlockedcompareexchange(a, b, c) __sync_val_compare_and_swap(a, c, b)
1515 #define interlockedexchange __sync_lock_test_and_set
1516 #endif /* Win32 */
1517 #endif /* USE_LOCKS */
1518
1519 /* Declarations for bit scanning on win32 */
1520 #if defined(_MSC_VER) && _MSC_VER>=1300
1521 #ifndef BitScanForward  /* Try to avoid pulling in WinNT.h */
1522 #ifdef __cplusplus
1523 extern "C" {
1524 #endif /* __cplusplus */
1525 unsigned char _BitScanForward(unsigned long *index, unsigned long mask);
1526 unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
1527 #ifdef __cplusplus
1528 }
1529 #endif /* __cplusplus */
1530
1531 #define BitScanForward _BitScanForward
1532 #define BitScanReverse _BitScanReverse
1533 #pragma intrinsic(_BitScanForward)
1534 #pragma intrinsic(_BitScanReverse)
1535 #endif /* BitScanForward */
1536 #endif /* defined(_MSC_VER) && _MSC_VER>=1300 */
1537
1538 #ifndef WIN32
1539 #ifndef malloc_getpagesize
1540 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
1541 #    ifndef _SC_PAGE_SIZE
1542 #      define _SC_PAGE_SIZE _SC_PAGESIZE
1543 #    endif
1544 #  endif
1545 #  ifdef _SC_PAGE_SIZE
1546 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
1547 #  else
1548 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
1549        extern size_t getpagesize();
1550 #      define malloc_getpagesize getpagesize()
1551 #    else
1552 #      ifdef WIN32 /* use supplied emulation of getpagesize */
1553 #        define malloc_getpagesize getpagesize()
1554 #      else
1555 #        ifndef LACKS_SYS_PARAM_H
1556 #          include <sys/param.h>
1557 #        endif
1558 #        ifdef EXEC_PAGESIZE
1559 #          define malloc_getpagesize EXEC_PAGESIZE
1560 #        else
1561 #          ifdef NBPG
1562 #            ifndef CLSIZE
1563 #              define malloc_getpagesize NBPG
1564 #            else
1565 #              define malloc_getpagesize (NBPG * CLSIZE)
1566 #            endif
1567 #          else
1568 #            ifdef NBPC
1569 #              define malloc_getpagesize NBPC
1570 #            else
1571 #              ifdef PAGESIZE
1572 #                define malloc_getpagesize PAGESIZE
1573 #              else /* just guess */
1574 #                define malloc_getpagesize ((size_t)4096U)
1575 #              endif
1576 #            endif
1577 #          endif
1578 #        endif
1579 #      endif
1580 #    endif
1581 #  endif
1582 #endif
1583 #endif
1584
1585 /* ------------------- size_t and alignment properties -------------------- */
1586
1587 /* The byte and bit size of a size_t */
1588 #define SIZE_T_SIZE         (sizeof(size_t))
1589 #define SIZE_T_BITSIZE      (sizeof(size_t) << 3)
1590
1591 /* Some constants coerced to size_t */
1592 /* Annoying but necessary to avoid errors on some platforms */
1593 #define SIZE_T_ZERO         ((size_t)0)
1594 #define SIZE_T_ONE          ((size_t)1)
1595 #define SIZE_T_TWO          ((size_t)2)
1596 #define SIZE_T_FOUR         ((size_t)4)
1597 #define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)
1598 #define FOUR_SIZE_T_SIZES   (SIZE_T_SIZE<<2)
1599 #define SIX_SIZE_T_SIZES    (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
1600 #define HALF_MAX_SIZE_T     (MAX_SIZE_T / 2U)
1601
1602 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
1603 #define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)
1604
1605 /* True if address a has acceptable alignment */
1606 #define is_aligned(A)       (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
1607
1608 /* the number of bytes to offset an address to align it */
1609 #define align_offset(A)\
1610  ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
1611   ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
1612
1613 /* -------------------------- MMAP preliminaries ------------------------- */
1614
1615 /*
1616    If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
1617    checks to fail so compiler optimizer can delete code rather than
1618    using so many "#if"s.
1619 */
1620
1621
1622 /* MORECORE and MMAP must return MFAIL on failure */
1623 #define MFAIL                ((void*)(MAX_SIZE_T))
1624 #define CMFAIL               ((char*)(MFAIL)) /* defined for convenience */
1625
1626 #if HAVE_MMAP
1627
1628 #ifndef WIN32
1629 #define MUNMAP_DEFAULT(a, s)  munmap((a), (s))
1630 #define MMAP_PROT            (PROT_READ|PROT_WRITE)
1631 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1632 #define MAP_ANONYMOUS        MAP_ANON
1633 #endif /* MAP_ANON */
1634 #ifdef MAP_ANONYMOUS
1635 #define MMAP_FLAGS           (MAP_PRIVATE|MAP_ANONYMOUS)
1636 #define MMAP_DEFAULT(s)       mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
1637 #else /* MAP_ANONYMOUS */
1638 /*
1639    Nearly all versions of mmap support MAP_ANONYMOUS, so the following
1640    is unlikely to be needed, but is supplied just in case.
1641 */
1642 #define MMAP_FLAGS           (MAP_PRIVATE)
1643 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1644 #define MMAP_DEFAULT(s) ((dev_zero_fd < 0) ? \
1645            (dev_zero_fd = open("/dev/zero", O_RDWR), \
1646             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
1647             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
1648 #endif /* MAP_ANONYMOUS */
1649
1650 #define DIRECT_MMAP_DEFAULT(s) MMAP_DEFAULT(s)
1651
1652 #else /* WIN32 */
1653
1654 /* Win32 MMAP via VirtualAlloc */
1655 static FORCEINLINE void* win32mmap(size_t size) {
1656   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
1657   return (ptr != 0)? ptr: MFAIL;
1658 }
1659
1660 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
1661 static FORCEINLINE void* win32direct_mmap(size_t size) {
1662   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
1663                            PAGE_READWRITE);
1664   return (ptr != 0)? ptr: MFAIL;
1665 }
1666
1667 /* This function supports releasing coalesed segments */
1668 static FORCEINLINE int win32munmap(void* ptr, size_t size) {
1669   MEMORY_BASIC_INFORMATION minfo;
1670   char* cptr = (char*)ptr;
1671   while (size) {
1672     if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
1673       return -1;
1674     if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
1675         minfo.State != MEM_COMMIT || minfo.RegionSize > size)
1676       return -1;
1677     if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
1678       return -1;
1679     cptr += minfo.RegionSize;
1680     size -= minfo.RegionSize;
1681   }
1682   return 0;
1683 }
1684
1685 #define MMAP_DEFAULT(s)             win32mmap(s)
1686 #define MUNMAP_DEFAULT(a, s)        win32munmap((a), (s))
1687 #define DIRECT_MMAP_DEFAULT(s)      win32direct_mmap(s)
1688 #endif /* WIN32 */
1689 #endif /* HAVE_MMAP */
1690
1691 #if HAVE_MREMAP
1692 #ifndef WIN32
1693 #define MREMAP_DEFAULT(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
1694 #endif /* WIN32 */
1695 #endif /* HAVE_MREMAP */
1696
1697 /**
1698  * Define CALL_MORECORE
1699  */
1700 #if HAVE_MORECORE
1701     #ifdef MORECORE
1702         #define CALL_MORECORE(S)    MORECORE(S)
1703     #else  /* MORECORE */
1704         #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
1705     #endif /* MORECORE */
1706 #else  /* HAVE_MORECORE */
1707     #define CALL_MORECORE(S)        MFAIL
1708 #endif /* HAVE_MORECORE */
1709
1710 /**
1711  * Define CALL_MMAP/CALL_MUNMAP/CALL_DIRECT_MMAP
1712  */
1713 #if HAVE_MMAP
1714     #define USE_MMAP_BIT            (SIZE_T_ONE)
1715
1716     #ifdef MMAP
1717         #define CALL_MMAP(s)        MMAP(s)
1718     #else /* MMAP */
1719         #define CALL_MMAP(s)        MMAP_DEFAULT(s)
1720     #endif /* MMAP */
1721     #ifdef MUNMAP
1722         #define CALL_MUNMAP(a, s)   MUNMAP((a), (s))
1723     #else /* MUNMAP */
1724         #define CALL_MUNMAP(a, s)   MUNMAP_DEFAULT((a), (s))
1725     #endif /* MUNMAP */
1726     #ifdef DIRECT_MMAP
1727         #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
1728     #else /* DIRECT_MMAP */
1729         #define CALL_DIRECT_MMAP(s) DIRECT_MMAP_DEFAULT(s)
1730     #endif /* DIRECT_MMAP */
1731 #else  /* HAVE_MMAP */
1732     #define USE_MMAP_BIT            (SIZE_T_ZERO)
1733
1734     #define MMAP(s)                 MFAIL
1735     #define MUNMAP(a, s)            (-1)
1736     #define DIRECT_MMAP(s)          MFAIL
1737     #define CALL_DIRECT_MMAP(s)     DIRECT_MMAP(s)
1738     #define CALL_MMAP(s)            MMAP(s)
1739     #define CALL_MUNMAP(a, s)       MUNMAP((a), (s))
1740 #endif /* HAVE_MMAP */
1741
1742 /**
1743  * Define CALL_MREMAP
1744  */
1745 #if HAVE_MMAP && HAVE_MREMAP
1746     #ifdef MREMAP
1747         #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP((addr), (osz), (nsz), (mv))
1748     #else /* MREMAP */
1749         #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP_DEFAULT((addr), (osz), (nsz), (mv))
1750     #endif /* MREMAP */
1751 #else  /* HAVE_MMAP && HAVE_MREMAP */
1752     #define CALL_MREMAP(addr, osz, nsz, mv)     MFAIL
1753 #endif /* HAVE_MMAP && HAVE_MREMAP */
1754
1755 /* mstate bit set if continguous morecore disabled or failed */
1756 #define USE_NONCONTIGUOUS_BIT (4U)
1757
1758 /* segment bit set in create_mspace_with_base */
1759 #define EXTERN_BIT            (8U)
1760
1761
1762 /* --------------------------- Lock preliminaries ------------------------ */
1763
1764 /*
1765   When locks are defined, there is one global lock, plus
1766   one per-mspace lock.
1767
1768   The global lock_ensures that mparams.magic and other unique
1769   mparams values are initialized only once. It also protects
1770   sequences of calls to MORECORE.  In many cases sys_alloc requires
1771   two calls, that should not be interleaved with calls by other
1772   threads.  This does not protect against direct calls to MORECORE
1773   by other threads not using this lock, so there is still code to
1774   cope the best we can on interference.
1775
1776   Per-mspace locks surround calls to malloc, free, etc.
1777   By default, locks are simple non-reentrant mutexes.
1778
1779   Because lock-protected regions generally have bounded times, it is
1780   OK to use the supplied simple spinlocks. Spinlocks are likely to
1781   improve performance for lightly contended applications, but worsen
1782   performance under heavy contention.
1783
1784   If USE_LOCKS is > 1, the definitions of lock routines here are
1785   bypassed, in which case you will need to define the type MLOCK_T,
1786   and at least INITIAL_LOCK, DESTROY_LOCK, ACQUIRE_LOCK, RELEASE_LOCK
1787   and TRY_LOCK.  You must also declare a
1788     static MLOCK_T malloc_global_mutex = { initialization values };.
1789
1790 */
1791
1792 #if !USE_LOCKS
1793 #define USE_LOCK_BIT               (0U)
1794 #define INITIAL_LOCK(l)            (0)
1795 #define DESTROY_LOCK(l)            (0)
1796 #define ACQUIRE_MALLOC_GLOBAL_LOCK()
1797 #define RELEASE_MALLOC_GLOBAL_LOCK()
1798
1799 #else
1800 #if USE_LOCKS > 1
1801 /* -----------------------  User-defined locks ------------------------ */
1802 /* Define your own lock implementation here */
1803 /* #define INITIAL_LOCK(lk)  ... */
1804 /* #define DESTROY_LOCK(lk)  ... */
1805 /* #define ACQUIRE_LOCK(lk)  ... */
1806 /* #define RELEASE_LOCK(lk)  ... */
1807 /* #define TRY_LOCK(lk) ... */
1808 /* static MLOCK_T malloc_global_mutex = ... */
1809
1810 #elif USE_SPIN_LOCKS
1811
1812 /* First, define CAS_LOCK and CLEAR_LOCK on ints */
1813 /* Note CAS_LOCK defined to return 0 on success */
1814
1815 #if defined(__GNUC__)&& (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1))
1816 #define CAS_LOCK(sl)     __sync_lock_test_and_set(sl, 1)
1817 #define CLEAR_LOCK(sl)   __sync_lock_release(sl)
1818
1819 #elif (defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)))
1820 /* Custom spin locks for older gcc on x86 */
1821 static FORCEINLINE int x86_cas_lock(int *sl) {
1822   int ret;
1823   int val = 1;
1824   int cmp = 0;
1825   __asm__ __volatile__  ("lock; cmpxchgl %1, %2"
1826                          : "=a" (ret)
1827                          : "r" (val), "m" (*(sl)), "0"(cmp)
1828                          : "memory", "cc");
1829   return ret;
1830 }
1831
1832 static FORCEINLINE void x86_clear_lock(int* sl) {
1833   assert(*sl != 0);
1834   int prev = 0;
1835   int ret;
1836   __asm__ __volatile__ ("lock; xchgl %0, %1"
1837                         : "=r" (ret)
1838                         : "m" (*(sl)), "0"(prev)
1839                         : "memory");
1840 }
1841
1842 #define CAS_LOCK(sl)     x86_cas_lock(sl)
1843 #define CLEAR_LOCK(sl)   x86_clear_lock(sl)
1844
1845 #else /* Win32 MSC */
1846 #define CAS_LOCK(sl)     interlockedexchange(sl, 1)
1847 #define CLEAR_LOCK(sl)   interlockedexchange (sl, 0)
1848
1849 #endif /* ... gcc spins locks ... */
1850
1851 /* How to yield for a spin lock */
1852 #define SPINS_PER_YIELD       63
1853 #if defined(_MSC_VER)
1854 #define SLEEP_EX_DURATION     50 /* delay for yield/sleep */
1855 #define SPIN_LOCK_YIELD  SleepEx(SLEEP_EX_DURATION, FALSE)
1856 #elif defined (__SVR4) && defined (__sun) /* solaris */
1857 #define SPIN_LOCK_YIELD   thr_yield();
1858 #elif !defined(LACKS_SCHED_H)
1859 #define SPIN_LOCK_YIELD   sched_yield();
1860 #else
1861 #define SPIN_LOCK_YIELD
1862 #endif /* ... yield ... */
1863
1864 #if !defined(USE_RECURSIVE_LOCKS) || USE_RECURSIVE_LOCKS == 0
1865 /* Plain spin locks use single word (embedded in malloc_states) */
1866 static int spin_acquire_lock(int *sl) {
1867   int spins = 0;
1868   while (*(volatile int *)sl != 0 || CAS_LOCK(sl)) {
1869     if ((++spins & SPINS_PER_YIELD) == 0) {
1870       SPIN_LOCK_YIELD;
1871     }
1872   }
1873   return 0;
1874 }
1875
1876 #define MLOCK_T               int
1877 #define TRY_LOCK(sl)          !CAS_LOCK(sl)
1878 #define RELEASE_LOCK(sl)      CLEAR_LOCK(sl)
1879 #define ACQUIRE_LOCK(sl)      (CAS_LOCK(sl)? spin_acquire_lock(sl) : 0)
1880 #define INITIAL_LOCK(sl)      (*sl = 0)
1881 #define DESTROY_LOCK(sl)      (0)
1882 static MLOCK_T malloc_global_mutex = 0;
1883
1884 #else /* USE_RECURSIVE_LOCKS */
1885 /* types for lock owners */
1886 #ifdef WIN32
1887 #define THREAD_ID_T           DWORD
1888 #define CURRENT_THREAD        GetCurrentThreadId()
1889 #define EQ_OWNER(X,Y)         ((X) == (Y))
1890 #else
1891 /*
1892   Note: the following assume that pthread_t is a type that can be
1893   initialized to (casted) zero. If this is not the case, you will need to
1894   somehow redefine these or not use spin locks.
1895 */
1896 #define THREAD_ID_T           pthread_t
1897 #define CURRENT_THREAD        pthread_self()
1898 #define EQ_OWNER(X,Y)         pthread_equal(X, Y)
1899 #endif
1900
1901 struct malloc_recursive_lock {
1902   int sl;
1903   unsigned int c;
1904   THREAD_ID_T threadid;
1905 };
1906
1907 #define MLOCK_T  struct malloc_recursive_lock
1908 static MLOCK_T malloc_global_mutex = { 0, 0, (THREAD_ID_T)0};
1909
1910 static FORCEINLINE void recursive_release_lock(MLOCK_T *lk) {
1911   assert(lk->sl != 0);
1912   if (--lk->c == 0) {
1913     CLEAR_LOCK(&lk->sl);
1914   }
1915 }
1916
1917 static FORCEINLINE int recursive_acquire_lock(MLOCK_T *lk) {
1918   THREAD_ID_T mythreadid = CURRENT_THREAD;
1919   int spins = 0;
1920   for (;;) {
1921     if (*((volatile int *)(&lk->sl)) == 0) {
1922       if (!CAS_LOCK(&lk->sl)) {
1923         lk->threadid = mythreadid;
1924         lk->c = 1;
1925         return 0;
1926       }
1927     }
1928     else if (EQ_OWNER(lk->threadid, mythreadid)) {
1929       ++lk->c;
1930       return 0;
1931     }
1932     if ((++spins & SPINS_PER_YIELD) == 0) {
1933       SPIN_LOCK_YIELD;
1934     }
1935   }
1936 }
1937
1938 static FORCEINLINE int recursive_try_lock(MLOCK_T *lk) {
1939   THREAD_ID_T mythreadid = CURRENT_THREAD;
1940   if (*((volatile int *)(&lk->sl)) == 0) {
1941     if (!CAS_LOCK(&lk->sl)) {
1942       lk->threadid = mythreadid;
1943       lk->c = 1;
1944       return 1;
1945     }
1946   }
1947   else if (EQ_OWNER(lk->threadid, mythreadid)) {
1948     ++lk->c;
1949     return 1;
1950   }
1951   return 0;
1952 }
1953
1954 #define RELEASE_LOCK(lk)      recursive_release_lock(lk)
1955 #define TRY_LOCK(lk)          recursive_try_lock(lk)
1956 #define ACQUIRE_LOCK(lk)      recursive_acquire_lock(lk)
1957 #define INITIAL_LOCK(lk)      ((lk)->threadid = (THREAD_ID_T)0, (lk)->sl = 0, (lk)->c = 0)
1958 #define DESTROY_LOCK(lk)      (0)
1959 #endif /* USE_RECURSIVE_LOCKS */
1960
1961 #elif defined(WIN32) /* Win32 critical sections */
1962 #define MLOCK_T               CRITICAL_SECTION
1963 #define ACQUIRE_LOCK(lk)      (EnterCriticalSection(lk), 0)
1964 #define RELEASE_LOCK(lk)      LeaveCriticalSection(lk)
1965 #define TRY_LOCK(lk)          TryEnterCriticalSection(lk)
1966 #define INITIAL_LOCK(lk)      (!InitializeCriticalSectionAndSpinCount((lk), 0x80000000|4000))
1967 #define DESTROY_LOCK(lk)      (DeleteCriticalSection(lk), 0)
1968 #define NEED_GLOBAL_LOCK_INIT
1969
1970 static MLOCK_T malloc_global_mutex;
1971 static volatile long malloc_global_mutex_status;
1972
1973 /* Use spin loop to initialize global lock */
1974 static void init_malloc_global_mutex() {
1975   for (;;) {
1976     long stat = malloc_global_mutex_status;
1977     if (stat > 0)
1978       return;
1979     /* transition to < 0 while initializing, then to > 0) */
1980     if (stat == 0 &&
1981         interlockedcompareexchange(&malloc_global_mutex_status, -1, 0) == 0) {
1982       InitializeCriticalSection(&malloc_global_mutex);
1983       interlockedexchange(&malloc_global_mutex_status,1);
1984       return;
1985     }
1986     SleepEx(0, FALSE);
1987   }
1988 }
1989
1990 #else /* pthreads-based locks */
1991 #define MLOCK_T               pthread_mutex_t
1992 #define ACQUIRE_LOCK(lk)      pthread_mutex_lock(lk)
1993 #define RELEASE_LOCK(lk)      pthread_mutex_unlock(lk)
1994 #define TRY_LOCK(lk)          (!pthread_mutex_trylock(lk))
1995 #define INITIAL_LOCK(lk)      pthread_init_lock(lk)
1996 #define DESTROY_LOCK(lk)      pthread_mutex_destroy(lk)
1997
1998 #if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0 && defined(linux) && !defined(PTHREAD_MUTEX_RECURSIVE)
1999 /* Cope with old-style linux recursive lock initialization by adding */
2000 /* skipped internal declaration from pthread.h */
2001 extern int pthread_mutexattr_setkind_np __P ((pthread_mutexattr_t *__attr,
2002                                            int __kind));
2003 #define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP
2004 #define pthread_mutexattr_settype(x,y) pthread_mutexattr_setkind_np(x,y)
2005 #endif /* USE_RECURSIVE_LOCKS ... */
2006
2007 static MLOCK_T malloc_global_mutex = PTHREAD_MUTEX_INITIALIZER;
2008
2009 static int pthread_init_lock (MLOCK_T *lk) {
2010   pthread_mutexattr_t attr;
2011   if (pthread_mutexattr_init(&attr)) return 1;
2012 #if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0
2013   if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1;
2014 #endif
2015   if (pthread_mutex_init(lk, &attr)) return 1;
2016   if (pthread_mutexattr_destroy(&attr)) return 1;
2017   return 0;
2018 }
2019
2020 #endif /* ... lock types ... */
2021
2022 /* Common code for all lock types */
2023 #define USE_LOCK_BIT               (2U)
2024
2025 #ifndef ACQUIRE_MALLOC_GLOBAL_LOCK
2026 #define ACQUIRE_MALLOC_GLOBAL_LOCK()  ACQUIRE_LOCK(&malloc_global_mutex);
2027 #endif
2028
2029 #ifndef RELEASE_MALLOC_GLOBAL_LOCK
2030 #define RELEASE_MALLOC_GLOBAL_LOCK()  RELEASE_LOCK(&malloc_global_mutex);
2031 #endif
2032
2033 #endif /* USE_LOCKS */
2034
2035 /* -----------------------  Chunk representations ------------------------ */
2036
2037 /*
2038   (The following includes lightly edited explanations by Colin Plumb.)
2039
2040   The malloc_chunk declaration below is misleading (but accurate and
2041   necessary).  It declares a "view" into memory allowing access to
2042   necessary fields at known offsets from a given base.
2043
2044   Chunks of memory are maintained using a `boundary tag' method as
2045   originally described by Knuth.  (See the paper by Paul Wilson
2046   ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
2047   techniques.)  Sizes of free chunks are stored both in the front of
2048   each chunk and at the end.  This makes consolidating fragmented
2049   chunks into bigger chunks fast.  The head fields also hold bits
2050   representing whether chunks are free or in use.
2051
2052   Here are some pictures to make it clearer.  They are "exploded" to
2053   show that the state of a chunk can be thought of as extending from
2054   the high 31 bits of the head field of its header through the
2055   prev_foot and PINUSE_BIT bit of the following chunk header.
2056
2057   A chunk that's in use looks like:
2058
2059    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2060            | Size of previous chunk (if P = 0)                             |
2061            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2062          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
2063          | Size of this chunk                                         1| +-+
2064    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2065          |                                                               |
2066          +-                                                             -+
2067          |                                                               |
2068          +-                                                             -+
2069          |                                                               :
2070          +-      size - sizeof(size_t) available payload bytes          -+
2071          :                                                               |
2072  chunk-> +-                                                             -+
2073          |                                                               |
2074          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2075        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
2076        | Size of next chunk (may or may not be in use)               | +-+
2077  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2078
2079     And if it's free, it looks like this:
2080
2081    chunk-> +-                                                             -+
2082            | User payload (must be in use, or we would have merged!)       |
2083            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2084          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
2085          | Size of this chunk                                         0| +-+
2086    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2087          | Next pointer                                                  |
2088          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2089          | Prev pointer                                                  |
2090          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2091          |                                                               :
2092          +-      size - sizeof(struct chunk) unused bytes               -+
2093          :                                                               |
2094  chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2095          | Size of this chunk                                            |
2096          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2097        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
2098        | Size of next chunk (must be in use, or we would have merged)| +-+
2099  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2100        |                                                               :
2101        +- User payload                                                -+
2102        :                                                               |
2103        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2104                                                                      |0|
2105                                                                      +-+
2106   Note that since we always merge adjacent free chunks, the chunks
2107   adjacent to a free chunk must be in use.
2108
2109   Given a pointer to a chunk (which can be derived trivially from the
2110   payload pointer) we can, in O(1) time, find out whether the adjacent
2111   chunks are free, and if so, unlink them from the lists that they
2112   are on and merge them with the current chunk.
2113
2114   Chunks always begin on even word boundaries, so the mem portion
2115   (which is returned to the user) is also on an even word boundary, and
2116   thus at least double-word aligned.
2117
2118   The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
2119   chunk size (which is always a multiple of two words), is an in-use
2120   bit for the *previous* chunk.  If that bit is *clear*, then the
2121   word before the current chunk size contains the previous chunk
2122   size, and can be used to find the front of the previous chunk.
2123   The very first chunk allocated always has this bit set, preventing
2124   access to non-existent (or non-owned) memory. If pinuse is set for
2125   any given chunk, then you CANNOT determine the size of the
2126   previous chunk, and might even get a memory addressing fault when
2127   trying to do so.
2128
2129   The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
2130   the chunk size redundantly records whether the current chunk is
2131   inuse (unless the chunk is mmapped). This redundancy enables usage
2132   checks within free and realloc, and reduces indirection when freeing
2133   and consolidating chunks.
2134
2135   Each freshly allocated chunk must have both cinuse and pinuse set.
2136   That is, each allocated chunk borders either a previously allocated
2137   and still in-use chunk, or the base of its memory arena. This is
2138   ensured by making all allocations from the `lowest' part of any
2139   found chunk.  Further, no free chunk physically borders another one,
2140   so each free chunk is known to be preceded and followed by either
2141   inuse chunks or the ends of memory.
2142
2143   Note that the `foot' of the current chunk is actually represented
2144   as the prev_foot of the NEXT chunk. This makes it easier to
2145   deal with alignments etc but can be very confusing when trying
2146   to extend or adapt this code.
2147
2148   The exceptions to all this are
2149
2150      1. The special chunk `top' is the top-most available chunk (i.e.,
2151         the one bordering the end of available memory). It is treated
2152         specially.  Top is never included in any bin, is used only if
2153         no other chunk is available, and is released back to the
2154         system if it is very large (see M_TRIM_THRESHOLD).  In effect,
2155         the top chunk is treated as larger (and thus less well
2156         fitting) than any other available chunk.  The top chunk
2157         doesn't update its trailing size field since there is no next
2158         contiguous chunk that would have to index off it. However,
2159         space is still allocated for it (TOP_FOOT_SIZE) to enable
2160         separation or merging when space is extended.
2161
2162      3. Chunks allocated via mmap, have both cinuse and pinuse bits
2163         cleared in their head fields.  Because they are allocated
2164         one-by-one, each must carry its own prev_foot field, which is
2165         also used to hold the offset this chunk has within its mmapped
2166         region, which is needed to preserve alignment. Each mmapped
2167         chunk is trailed by the first two fields of a fake next-chunk
2168         for sake of usage checks.
2169
2170 */
2171
2172 struct malloc_chunk {
2173   size_t               prev_foot;  /* Size of previous chunk (if free).  */
2174   size_t               head;       /* Size and inuse bits. */
2175   struct malloc_chunk* fd;         /* double links -- used only if free. */
2176   struct malloc_chunk* bk;
2177 };
2178
2179 typedef struct malloc_chunk  mchunk;
2180 typedef struct malloc_chunk* mchunkptr;
2181 typedef struct malloc_chunk* sbinptr;  /* The type of bins of chunks */
2182 typedef unsigned int bindex_t;         /* Described below */
2183 typedef unsigned int binmap_t;         /* Described below */
2184 typedef unsigned int flag_t;           /* The type of various bit flag sets */
2185
2186 /* ------------------- Chunks sizes and alignments ----------------------- */
2187
2188 #define MCHUNK_SIZE         (sizeof(mchunk))
2189
2190 #if FOOTERS
2191 #define CHUNK_OVERHEAD      (TWO_SIZE_T_SIZES)
2192 #else /* FOOTERS */
2193 #define CHUNK_OVERHEAD      (SIZE_T_SIZE)
2194 #endif /* FOOTERS */
2195
2196 /* MMapped chunks need a second word of overhead ... */
2197 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
2198 /* ... and additional padding for fake next-chunk at foot */
2199 #define MMAP_FOOT_PAD       (FOUR_SIZE_T_SIZES)
2200
2201 /* The smallest size we can malloc is an aligned minimal chunk */
2202 #define MIN_CHUNK_SIZE\
2203   ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
2204
2205 /* conversion from malloc headers to user pointers, and back */
2206 #define chunk2mem(p)        ((void*)((char*)(p)       + TWO_SIZE_T_SIZES))
2207 #define mem2chunk(mem)      ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
2208 /* chunk associated with aligned address A */
2209 #define align_as_chunk(A)   (mchunkptr)((A) + align_offset(chunk2mem(A)))
2210
2211 /* Bounds on request (not chunk) sizes. */
2212 #define MAX_REQUEST         ((-MIN_CHUNK_SIZE) << 2)
2213 #define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
2214
2215 /* pad request bytes into a usable size */
2216 #define pad_request(req) \
2217    (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
2218
2219 /* pad request, checking for minimum (but not maximum) */
2220 #define request2size(req) \
2221   (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
2222
2223
2224 /* ------------------ Operations on head and foot fields ----------------- */
2225
2226 /*
2227   The head field of a chunk is or'ed with PINUSE_BIT when previous
2228   adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
2229   use, unless mmapped, in which case both bits are cleared.
2230
2231   FLAG4_BIT is not used by this malloc, but might be useful in extensions.
2232 */
2233
2234 #define PINUSE_BIT          (SIZE_T_ONE)
2235 #define CINUSE_BIT          (SIZE_T_TWO)
2236 #define FLAG4_BIT           (SIZE_T_FOUR)
2237 #define INUSE_BITS          (PINUSE_BIT|CINUSE_BIT)
2238 #define FLAG_BITS           (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT)
2239
2240 /* Head value for fenceposts */
2241 #define FENCEPOST_HEAD      (INUSE_BITS|SIZE_T_SIZE)
2242
2243 /* extraction of fields from head words */
2244 #define cinuse(p)           ((p)->head & CINUSE_BIT)
2245 #define pinuse(p)           ((p)->head & PINUSE_BIT)
2246 #define flag4inuse(p)       ((p)->head & FLAG4_BIT)
2247 #define is_inuse(p)         (((p)->head & INUSE_BITS) != PINUSE_BIT)
2248 #define is_mmapped(p)       (((p)->head & INUSE_BITS) == 0)
2249
2250 #define chunksize(p)        ((p)->head & ~(FLAG_BITS))
2251
2252 #define clear_pinuse(p)     ((p)->head &= ~PINUSE_BIT)
2253 #define set_flag4(p)        ((p)->head |= FLAG4_BIT)
2254 #define clear_flag4(p)      ((p)->head &= ~FLAG4_BIT)
2255
2256 /* Treat space at ptr +/- offset as a chunk */
2257 #define chunk_plus_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
2258 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
2259
2260 /* Ptr to next or previous physical malloc_chunk. */
2261 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS)))
2262 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
2263
2264 /* extract next chunk's pinuse bit */
2265 #define next_pinuse(p)  ((next_chunk(p)->head) & PINUSE_BIT)
2266
2267 /* Get/set size at footer */
2268 #define get_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot)
2269 #define set_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
2270
2271 /* Set size, pinuse bit, and foot */
2272 #define set_size_and_pinuse_of_free_chunk(p, s)\
2273   ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
2274
2275 /* Set size, pinuse bit, foot, and clear next pinuse */
2276 #define set_free_with_pinuse(p, s, n)\
2277   (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
2278
2279 /* Get the internal overhead associated with chunk p */
2280 #define overhead_for(p)\
2281  (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
2282
2283 /* Return true if malloced space is not necessarily cleared */
2284 #if MMAP_CLEARS
2285 #define calloc_must_clear(p) (!is_mmapped(p))
2286 #else /* MMAP_CLEARS */
2287 #define calloc_must_clear(p) (1)
2288 #endif /* MMAP_CLEARS */
2289
2290 /* ---------------------- Overlaid data structures ----------------------- */
2291
2292 /*
2293   When chunks are not in use, they are treated as nodes of either
2294   lists or trees.
2295
2296   "Small"  chunks are stored in circular doubly-linked lists, and look
2297   like this:
2298
2299     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2300             |             Size of previous chunk                            |
2301             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2302     `head:' |             Size of chunk, in bytes                         |P|
2303       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2304             |             Forward pointer to next chunk in list             |
2305             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2306             |             Back pointer to previous chunk in list            |
2307             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2308             |             Unused space (may be 0 bytes long)                .
2309             .                                                               .
2310             .                                                               |
2311 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2312     `foot:' |             Size of chunk, in bytes                           |
2313             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2314
2315   Larger chunks are kept in a form of bitwise digital trees (aka
2316   tries) keyed on chunksizes.  Because malloc_tree_chunks are only for
2317   free chunks greater than 256 bytes, their size doesn't impose any
2318   constraints on user chunk sizes.  Each node looks like:
2319
2320     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2321             |             Size of previous chunk                            |
2322             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2323     `head:' |             Size of chunk, in bytes                         |P|
2324       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2325             |             Forward pointer to next chunk of same size        |
2326             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2327             |             Back pointer to previous chunk of same size       |
2328             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2329             |             Pointer to left child (child[0])                  |
2330             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2331             |             Pointer to right child (child[1])                 |
2332             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2333             |             Pointer to parent                                 |
2334             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2335             |             bin index of this chunk                           |
2336             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2337             |             Unused space                                      .
2338             .                                                               |
2339 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2340     `foot:' |             Size of chunk, in bytes                           |
2341             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2342
2343   Each tree holding treenodes is a tree of unique chunk sizes.  Chunks
2344   of the same size are arranged in a circularly-linked list, with only
2345   the oldest chunk (the next to be used, in our FIFO ordering)
2346   actually in the tree.  (Tree members are distinguished by a non-null
2347   parent pointer.)  If a chunk with the same size an an existing node
2348   is inserted, it is linked off the existing node using pointers that
2349   work in the same way as fd/bk pointers of small chunks.
2350
2351   Each tree contains a power of 2 sized range of chunk sizes (the
2352   smallest is 0x100 <= x < 0x180), which is is divided in half at each
2353   tree level, with the chunks in the smaller half of the range (0x100
2354   <= x < 0x140 for the top nose) in the left subtree and the larger
2355   half (0x140 <= x < 0x180) in the right subtree.  This is, of course,
2356   done by inspecting individual bits.
2357
2358   Using these rules, each node's left subtree contains all smaller
2359   sizes than its right subtree.  However, the node at the root of each
2360   subtree has no particular ordering relationship to either.  (The
2361   dividing line between the subtree sizes is based on trie relation.)
2362   If we remove the last chunk of a given size from the interior of the
2363   tree, we need to replace it with a leaf node.  The tree ordering
2364   rules permit a node to be replaced by any leaf below it.
2365
2366   The smallest chunk in a tree (a common operation in a best-fit
2367   allocator) can be found by walking a path to the leftmost leaf in
2368   the tree.  Unlike a usual binary tree, where we follow left child
2369   pointers until we reach a null, here we follow the right child
2370   pointer any time the left one is null, until we reach a leaf with
2371   both child pointers null. The smallest chunk in the tree will be
2372   somewhere along that path.
2373
2374   The worst case number of steps to add, find, or remove a node is
2375   bounded by the number of bits differentiating chunks within
2376   bins. Under current bin calculations, this ranges from 6 up to 21
2377   (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
2378   is of course much better.
2379 */
2380
2381 struct malloc_tree_chunk {
2382   /* The first four fields must be compatible with malloc_chunk */
2383   size_t                    prev_foot;
2384   size_t                    head;
2385   struct malloc_tree_chunk* fd;
2386   struct malloc_tree_chunk* bk;
2387
2388   struct malloc_tree_chunk* child[2];
2389   struct malloc_tree_chunk* parent;
2390   bindex_t                  index;
2391 };
2392
2393 typedef struct malloc_tree_chunk  tchunk;
2394 typedef struct malloc_tree_chunk* tchunkptr;
2395 typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
2396
2397 /* A little helper macro for trees */
2398 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
2399
2400 /* ----------------------------- Segments -------------------------------- */
2401
2402 /*
2403   Each malloc space may include non-contiguous segments, held in a
2404   list headed by an embedded malloc_segment record representing the
2405   top-most space. Segments also include flags holding properties of
2406   the space. Large chunks that are directly allocated by mmap are not
2407   included in this list. They are instead independently created and
2408   destroyed without otherwise keeping track of them.
2409
2410   Segment management mainly comes into play for spaces allocated by
2411   MMAP.  Any call to MMAP might or might not return memory that is
2412   adjacent to an existing segment.  MORECORE normally contiguously
2413   extends the current space, so this space is almost always adjacent,
2414   which is simpler and faster to deal with. (This is why MORECORE is
2415   used preferentially to MMAP when both are available -- see
2416   sys_alloc.)  When allocating using MMAP, we don't use any of the
2417   hinting mechanisms (inconsistently) supported in various
2418   implementations of unix mmap, or distinguish reserving from
2419   committing memory. Instead, we just ask for space, and exploit
2420   contiguity when we get it.  It is probably possible to do
2421   better than this on some systems, but no general scheme seems
2422   to be significantly better.
2423
2424   Management entails a simpler variant of the consolidation scheme
2425   used for chunks to reduce fragmentation -- new adjacent memory is
2426   normally prepended or appended to an existing segment. However,
2427   there are limitations compared to chunk consolidation that mostly
2428   reflect the fact that segment processing is relatively infrequent
2429   (occurring only when getting memory from system) and that we
2430   don't expect to have huge numbers of segments:
2431
2432   * Segments are not indexed, so traversal requires linear scans.  (It
2433     would be possible to index these, but is not worth the extra
2434     overhead and complexity for most programs on most platforms.)
2435   * New segments are only appended to old ones when holding top-most
2436     memory; if they cannot be prepended to others, they are held in
2437     different segments.
2438
2439   Except for the top-most segment of an mstate, each segment record
2440   is kept at the tail of its segment. Segments are added by pushing
2441   segment records onto the list headed by &mstate.seg for the
2442   containing mstate.
2443
2444   Segment flags control allocation/merge/deallocation policies:
2445   * If EXTERN_BIT set, then we did not allocate this segment,
2446     and so should not try to deallocate or merge with others.
2447     (This currently holds only for the initial segment passed
2448     into create_mspace_with_base.)
2449   * If USE_MMAP_BIT set, the segment may be merged with
2450     other surrounding mmapped segments and trimmed/de-allocated
2451     using munmap.
2452   * If neither bit is set, then the segment was obtained using
2453     MORECORE so can be merged with surrounding MORECORE'd segments
2454     and deallocated/trimmed using MORECORE with negative arguments.
2455 */
2456
2457 struct malloc_segment {
2458   char*        base;             /* base address */
2459   size_t       size;             /* allocated size */
2460   struct malloc_segment* next;   /* ptr to next segment */
2461   flag_t       sflags;           /* mmap and extern flag */
2462 };
2463
2464 #define is_mmapped_segment(S)  ((S)->sflags & USE_MMAP_BIT)
2465 #define is_extern_segment(S)   ((S)->sflags & EXTERN_BIT)
2466
2467 typedef struct malloc_segment  msegment;
2468 typedef struct malloc_segment* msegmentptr;
2469
2470 /* ---------------------------- malloc_state ----------------------------- */
2471
2472 /*
2473    A malloc_state holds all of the bookkeeping for a space.
2474    The main fields are:
2475
2476   Top
2477     The topmost chunk of the currently active segment. Its size is
2478     cached in topsize.  The actual size of topmost space is
2479     topsize+TOP_FOOT_SIZE, which includes space reserved for adding
2480     fenceposts and segment records if necessary when getting more
2481     space from the system.  The size at which to autotrim top is
2482     cached from mparams in trim_check, except that it is disabled if
2483     an autotrim fails.
2484
2485   Designated victim (dv)
2486     This is the preferred chunk for servicing small requests that
2487     don't have exact fits.  It is normally the chunk split off most
2488     recently to service another small request.  Its size is cached in
2489     dvsize. The link fields of this chunk are not maintained since it
2490     is not kept in a bin.
2491
2492   SmallBins
2493     An array of bin headers for free chunks.  These bins hold chunks
2494     with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
2495     chunks of all the same size, spaced 8 bytes apart.  To simplify
2496     use in double-linked lists, each bin header acts as a malloc_chunk
2497     pointing to the real first node, if it exists (else pointing to
2498     itself).  This avoids special-casing for headers.  But to avoid
2499     waste, we allocate only the fd/bk pointers of bins, and then use
2500     repositioning tricks to treat these as the fields of a chunk.
2501
2502   TreeBins
2503     Treebins are pointers to the roots of trees holding a range of
2504     sizes. There are 2 equally spaced treebins for each power of two
2505     from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
2506     larger.
2507
2508   Bin maps
2509     There is one bit map for small bins ("smallmap") and one for
2510     treebins ("treemap).  Each bin sets its bit when non-empty, and
2511     clears the bit when empty.  Bit operations are then used to avoid
2512     bin-by-bin searching -- nearly all "search" is done without ever
2513     looking at bins that won't be selected.  The bit maps
2514     conservatively use 32 bits per map word, even if on 64bit system.
2515     For a good description of some of the bit-based techniques used
2516     here, see Henry S. Warren Jr's book "Hacker's Delight" (and
2517     supplement at http://hackersdelight.org/). Many of these are
2518     intended to reduce the branchiness of paths through malloc etc, as
2519     well as to reduce the number of memory locations read or written.
2520
2521   Segments
2522     A list of segments headed by an embedded malloc_segment record
2523     representing the initial space.
2524
2525   Address check support
2526     The least_addr field is the least address ever obtained from
2527     MORECORE or MMAP. Attempted frees and reallocs of any address less
2528     than this are trapped (unless INSECURE is defined).
2529
2530   Magic tag
2531     A cross-check field that should always hold same value as mparams.magic.
2532
2533   Max allowed footprint
2534     The maximum allowed bytes to allocate from system (zero means no limit)
2535
2536   Flags
2537     Bits recording whether to use MMAP, locks, or contiguous MORECORE
2538
2539   Statistics
2540     Each space keeps track of current and maximum system memory
2541     obtained via MORECORE or MMAP.
2542
2543   Trim support
2544     Fields holding the amount of unused topmost memory that should trigger
2545     trimming, and a counter to force periodic scanning to release unused
2546     non-topmost segments.
2547
2548   Locking
2549     If USE_LOCKS is defined, the "mutex" lock is acquired and released
2550     around every public call using this mspace.
2551
2552   Extension support
2553     A void* pointer and a size_t field that can be used to help implement
2554     extensions to this malloc.
2555 */
2556
2557 /* Bin types, widths and sizes */
2558 #define NSMALLBINS        (32U)
2559 #define NTREEBINS         (32U)
2560 #define SMALLBIN_SHIFT    (3U)
2561 #define SMALLBIN_WIDTH    (SIZE_T_ONE << SMALLBIN_SHIFT)
2562 #define TREEBIN_SHIFT     (8U)
2563 #define MIN_LARGE_SIZE    (SIZE_T_ONE << TREEBIN_SHIFT)
2564 #define MAX_SMALL_SIZE    (MIN_LARGE_SIZE - SIZE_T_ONE)
2565 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
2566
2567 struct malloc_state {
2568   binmap_t   smallmap;
2569   binmap_t   treemap;
2570   size_t     dvsize;
2571   size_t     topsize;
2572   char*      least_addr;
2573   mchunkptr  dv;
2574   mchunkptr  top;
2575   size_t     trim_check;
2576   size_t     release_checks;
2577   size_t     magic;
2578   mchunkptr  smallbins[(NSMALLBINS+1)*2];
2579   tbinptr    treebins[NTREEBINS];
2580   size_t     footprint;
2581   size_t     max_footprint;
2582   size_t     footprint_limit; /* zero means no limit */
2583   flag_t     mflags;
2584 #if USE_LOCKS
2585   MLOCK_T    mutex;     /* locate lock among fields that rarely change */
2586 #endif /* USE_LOCKS */
2587   msegment   seg;
2588   void*      extp;      /* Unused but available for extensions */
2589   size_t     exts;
2590 };
2591
2592 typedef struct malloc_state*    mstate;
2593
2594 /* ------------- Global malloc_state and malloc_params ------------------- */
2595
2596 /*
2597   malloc_params holds global properties, including those that can be
2598   dynamically set using mallopt. There is a single instance, mparams,
2599   initialized in init_mparams. Note that the non-zeroness of "magic"
2600   also serves as an initialization flag.
2601 */
2602
2603 struct malloc_params {
2604   size_t magic;
2605   size_t page_size;
2606   size_t granularity;
2607   size_t mmap_threshold;
2608   size_t trim_threshold;
2609   flag_t default_mflags;
2610 };
2611
2612 static struct malloc_params mparams;
2613
2614 /* Ensure mparams initialized */
2615 #define ensure_initialization() (void)(mparams.magic != 0 || init_mparams())
2616
2617 #if !ONLY_MSPACES
2618
2619 /* The global malloc_state used for all non-"mspace" calls */
2620 static struct malloc_state _gm_;
2621 #define gm                 (&_gm_)
2622 #define is_global(M)       ((M) == &_gm_)
2623
2624 #endif /* !ONLY_MSPACES */
2625
2626 #define is_initialized(M)  ((M)->top != 0)
2627
2628 /* -------------------------- system alloc setup ------------------------- */
2629
2630 /* Operations on mflags */
2631
2632 #define use_lock(M)           ((M)->mflags &   USE_LOCK_BIT)
2633 #define enable_lock(M)        ((M)->mflags |=  USE_LOCK_BIT)
2634 #if USE_LOCKS
2635 #define disable_lock(M)       ((M)->mflags &= ~USE_LOCK_BIT)
2636 #else
2637 #define disable_lock(M)
2638 #endif
2639
2640 #define use_mmap(M)           ((M)->mflags &   USE_MMAP_BIT)
2641 #define enable_mmap(M)        ((M)->mflags |=  USE_MMAP_BIT)
2642 #if HAVE_MMAP
2643 #define disable_mmap(M)       ((M)->mflags &= ~USE_MMAP_BIT)
2644 #else
2645 #define disable_mmap(M)
2646 #endif
2647
2648 #define use_noncontiguous(M)  ((M)->mflags &   USE_NONCONTIGUOUS_BIT)
2649 #define disable_contiguous(M) ((M)->mflags |=  USE_NONCONTIGUOUS_BIT)
2650
2651 #define set_lock(M,L)\
2652  ((M)->mflags = (L)?\
2653   ((M)->mflags | USE_LOCK_BIT) :\
2654   ((M)->mflags & ~USE_LOCK_BIT))
2655
2656 /* page-align a size */
2657 #define page_align(S)\
2658  (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE))
2659
2660 /* granularity-align a size */
2661 #define granularity_align(S)\
2662   (((S) + (mparams.granularity - SIZE_T_ONE))\
2663    & ~(mparams.granularity - SIZE_T_ONE))
2664
2665
2666 /* For mmap, use granularity alignment on windows, else page-align */
2667 #ifdef WIN32
2668 #define mmap_align(S) granularity_align(S)
2669 #else
2670 #define mmap_align(S) page_align(S)
2671 #endif
2672
2673 /* For sys_alloc, enough padding to ensure can malloc request on success */
2674 #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT)
2675
2676 #define is_page_aligned(S)\
2677    (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
2678 #define is_granularity_aligned(S)\
2679    (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
2680
2681 /*  True if segment S holds address A */
2682 #define segment_holds(S, A)\
2683   ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
2684
2685 /* Return segment holding given address */
2686 static msegmentptr segment_holding(mstate m, char* addr) {
2687   msegmentptr sp = &m->seg;
2688   for (;;) {
2689     if (addr >= sp->base && addr < sp->base + sp->size)
2690       return sp;
2691     if ((sp = sp->next) == 0)
2692       return 0;
2693   }
2694 }
2695
2696 /* Return true if segment contains a segment link */
2697 static int has_segment_link(mstate m, msegmentptr ss) {
2698   msegmentptr sp = &m->seg;
2699   for (;;) {
2700     if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
2701       return 1;
2702     if ((sp = sp->next) == 0)
2703       return 0;
2704   }
2705 }
2706
2707 #ifndef MORECORE_CANNOT_TRIM
2708 #define should_trim(M,s)  ((s) > (M)->trim_check)
2709 #else  /* MORECORE_CANNOT_TRIM */
2710 #define should_trim(M,s)  (0)
2711 #endif /* MORECORE_CANNOT_TRIM */
2712
2713 /*
2714   TOP_FOOT_SIZE is padding at the end of a segment, including space
2715   that may be needed to place segment records and fenceposts when new
2716   noncontiguous segments are added.
2717 */
2718 #define TOP_FOOT_SIZE\
2719   (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
2720
2721
2722 /* -------------------------------  Hooks -------------------------------- */
2723
2724 /*
2725   PREACTION should be defined to return 0 on success, and nonzero on
2726   failure. If you are not using locking, you can redefine these to do
2727   anything you like.
2728 */
2729
2730 #if USE_LOCKS
2731 #define PREACTION(M)  ((use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
2732 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
2733 #else /* USE_LOCKS */
2734
2735 #ifndef PREACTION
2736 #define PREACTION(M) (0)
2737 #endif  /* PREACTION */
2738
2739 #ifndef POSTACTION
2740 #define POSTACTION(M)
2741 #endif  /* POSTACTION */
2742
2743 #endif /* USE_LOCKS */
2744
2745 /*
2746   CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
2747   USAGE_ERROR_ACTION is triggered on detected bad frees and
2748   reallocs. The argument p is an address that might have triggered the
2749   fault. It is ignored by the two predefined actions, but might be
2750   useful in custom actions that try to help diagnose errors.
2751 */
2752
2753 #if PROCEED_ON_ERROR
2754
2755 /* A count of the number of corruption errors causing resets */
2756 int malloc_corruption_error_count;
2757
2758 /* default corruption action */
2759 static void reset_on_error(mstate m);
2760
2761 #define CORRUPTION_ERROR_ACTION(m)  reset_on_error(m)
2762 #define USAGE_ERROR_ACTION(m, p)
2763
2764 #else /* PROCEED_ON_ERROR */
2765
2766 #ifndef CORRUPTION_ERROR_ACTION
2767 #define CORRUPTION_ERROR_ACTION(m) ABORT
2768 #endif /* CORRUPTION_ERROR_ACTION */
2769
2770 #ifndef USAGE_ERROR_ACTION
2771 #define USAGE_ERROR_ACTION(m,p) ABORT
2772 #endif /* USAGE_ERROR_ACTION */
2773
2774 #endif /* PROCEED_ON_ERROR */
2775
2776
2777 /* -------------------------- Debugging setup ---------------------------- */
2778
2779 #if ! DEBUG
2780
2781 #define check_free_chunk(M,P)
2782 #define check_inuse_chunk(M,P)
2783 #define check_malloced_chunk(M,P,N)
2784 #define check_mmapped_chunk(M,P)
2785 #define check_malloc_state(M)
2786 #define check_top_chunk(M,P)
2787
2788 #else /* DEBUG */
2789 #define check_free_chunk(M,P)       do_check_free_chunk(M,P)
2790 #define check_inuse_chunk(M,P)      do_check_inuse_chunk(M,P)
2791 #define check_top_chunk(M,P)        do_check_top_chunk(M,P)
2792 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
2793 #define check_mmapped_chunk(M,P)    do_check_mmapped_chunk(M,P)
2794 #define check_malloc_state(M)       do_check_malloc_state(M)
2795
2796 static void   do_check_any_chunk(mstate m, mchunkptr p);
2797 static void   do_check_top_chunk(mstate m, mchunkptr p);
2798 static void   do_check_mmapped_chunk(mstate m, mchunkptr p);
2799 static void   do_check_inuse_chunk(mstate m, mchunkptr p);
2800 static void   do_check_free_chunk(mstate m, mchunkptr p);
2801 static void   do_check_malloced_chunk(mstate m, void* mem, size_t s);
2802 static void   do_check_tree(mstate m, tchunkptr t);
2803 static void   do_check_treebin(mstate m, bindex_t i);
2804 static void   do_check_smallbin(mstate m, bindex_t i);
2805 static void   do_check_malloc_state(mstate m);
2806 static int    bin_find(mstate m, mchunkptr x);
2807 static size_t traverse_and_check(mstate m);
2808 #endif /* DEBUG */
2809
2810 /* ---------------------------- Indexing Bins ---------------------------- */
2811
2812 #define is_small(s)         (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
2813 #define small_index(s)      (bindex_t)((s)  >> SMALLBIN_SHIFT)
2814 #define small_index2size(i) ((i)  << SMALLBIN_SHIFT)
2815 #define MIN_SMALL_INDEX     (small_index(MIN_CHUNK_SIZE))
2816
2817 /* addressing by index. See above about smallbin repositioning */
2818 #define smallbin_at(M, i)   ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
2819 #define treebin_at(M,i)     (&((M)->treebins[i]))
2820
2821 /* assign tree index for size S to variable I. Use x86 asm if possible  */
2822 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
2823 #define compute_tree_index(S, I)\
2824 {\
2825   unsigned int X = S >> TREEBIN_SHIFT;\
2826   if (X == 0)\
2827     I = 0;\
2828   else if (X > 0xFFFF)\
2829     I = NTREEBINS-1;\
2830   else {\
2831     unsigned int K = (unsigned) sizeof(X)*__CHAR_BIT__ - 1 - (unsigned) __builtin_clz(X); \
2832     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2833   }\
2834 }
2835
2836 #elif defined (__INTEL_COMPILER)
2837 #define compute_tree_index(S, I)\
2838 {\
2839   size_t X = S >> TREEBIN_SHIFT;\
2840   if (X == 0)\
2841     I = 0;\
2842   else if (X > 0xFFFF)\
2843     I = NTREEBINS-1;\
2844   else {\
2845     unsigned int K = _bit_scan_reverse (X); \
2846     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2847   }\
2848 }
2849
2850 #elif defined(_MSC_VER) && _MSC_VER>=1300
2851 #define compute_tree_index(S, I)\
2852 {\
2853   size_t X = S >> TREEBIN_SHIFT;\
2854   if (X == 0)\
2855     I = 0;\
2856   else if (X > 0xFFFF)\
2857     I = NTREEBINS-1;\
2858   else {\
2859     unsigned int K;\
2860     _BitScanReverse((DWORD *) &K, (DWORD) X);\
2861     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2862   }\
2863 }
2864
2865 #else /* GNUC */
2866 #define compute_tree_index(S, I)\
2867 {\
2868   size_t X = S >> TREEBIN_SHIFT;\
2869   if (X == 0)\
2870     I = 0;\
2871   else if (X > 0xFFFF)\
2872     I = NTREEBINS-1;\
2873   else {\
2874     unsigned int Y = (unsigned int)X;\
2875     unsigned int N = ((Y - 0x100) >> 16) & 8;\
2876     unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
2877     N += K;\
2878     N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
2879     K = 14 - N + ((Y <<= K) >> 15);\
2880     I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
2881   }\
2882 }
2883 #endif /* GNUC */
2884
2885 /* Bit representing maximum resolved size in a treebin at i */
2886 #define bit_for_tree_index(i) \
2887    (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
2888
2889 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
2890 #define leftshift_for_tree_index(i) \
2891    ((i == NTREEBINS-1)? 0 : \
2892     ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
2893
2894 /* The size of the smallest chunk held in bin with index i */
2895 #define minsize_for_tree_index(i) \
2896    ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) |  \
2897    (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
2898
2899
2900 /* ------------------------ Operations on bin maps ----------------------- */
2901
2902 /* bit corresponding to given index */
2903 #define idx2bit(i)              ((binmap_t)(1) << (i))
2904
2905 /* Mark/Clear bits with given index */
2906 #define mark_smallmap(M,i)      ((M)->smallmap |=  idx2bit(i))
2907 #define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))
2908 #define smallmap_is_marked(M,i) ((M)->smallmap &   idx2bit(i))
2909
2910 #define mark_treemap(M,i)       ((M)->treemap  |=  idx2bit(i))
2911 #define clear_treemap(M,i)      ((M)->treemap  &= ~idx2bit(i))
2912 #define treemap_is_marked(M,i)  ((M)->treemap  &   idx2bit(i))
2913
2914 /* isolate the least set bit of a bitmap */
2915 #define least_bit(x)         ((x) & -(x))
2916
2917 /* mask with all bits to left of least bit of x on */
2918 #define left_bits(x)         ((x<<1) | -(x<<1))
2919
2920 /* mask with all bits to left of or equal to least bit of x on */
2921 #define same_or_left_bits(x) ((x) | -(x))
2922
2923 /* index corresponding to given bit. Use x86 asm if possible */
2924
2925 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
2926 #define compute_bit2idx(X, I)\
2927 {\
2928   unsigned int J;\
2929   J = __builtin_ctz(X); \
2930   I = (bindex_t)J;\
2931 }
2932
2933 #elif defined (__INTEL_COMPILER)
2934 #define compute_bit2idx(X, I)\
2935 {\
2936   unsigned int J;\
2937   J = _bit_scan_forward (X); \
2938   I = (bindex_t)J;\
2939 }
2940
2941 #elif defined(_MSC_VER) && _MSC_VER>=1300
2942 #define compute_bit2idx(X, I)\
2943 {\
2944   unsigned int J;\
2945   _BitScanForward((DWORD *) &J, X);\
2946   I = (bindex_t)J;\
2947 }
2948
2949 #elif USE_BUILTIN_FFS
2950 #define compute_bit2idx(X, I) I = ffs(X)-1
2951
2952 #else
2953 #define compute_bit2idx(X, I)\
2954 {\
2955   unsigned int Y = X - 1;\
2956   unsigned int K = Y >> (16-4) & 16;\
2957   unsigned int N = K;        Y >>= K;\
2958   N += K = Y >> (8-3) &  8;  Y >>= K;\
2959   N += K = Y >> (4-2) &  4;  Y >>= K;\
2960   N += K = Y >> (2-1) &  2;  Y >>= K;\
2961   N += K = Y >> (1-0) &  1;  Y >>= K;\
2962   I = (bindex_t)(N + Y);\
2963 }
2964 #endif /* GNUC */
2965
2966
2967 /* ----------------------- Runtime Check Support ------------------------- */
2968
2969 /*
2970   For security, the main invariant is that malloc/free/etc never
2971   writes to a static address other than malloc_state, unless static
2972   malloc_state itself has been corrupted, which cannot occur via
2973   malloc (because of these checks). In essence this means that we
2974   believe all pointers, sizes, maps etc held in malloc_state, but
2975   check all of those linked or offsetted from other embedded data
2976   structures.  These checks are interspersed with main code in a way
2977   that tends to minimize their run-time cost.
2978
2979   When FOOTERS is defined, in addition to range checking, we also
2980   verify footer fields of inuse chunks, which can be used guarantee
2981   that the mstate controlling malloc/free is intact.  This is a
2982   streamlined version of the approach described by William Robertson
2983   et al in "Run-time Detection of Heap-based Overflows" LISA'03
2984   http://www.usenix.org/events/lisa03/tech/robertson.html The footer
2985   of an inuse chunk holds the xor of its mstate and a random seed,
2986   that is checked upon calls to free() and realloc().  This is
2987   (probabalistically) unguessable from outside the program, but can be
2988   computed by any code successfully malloc'ing any chunk, so does not
2989   itself provide protection against code that has already broken
2990   security through some other means.  Unlike Robertson et al, we
2991   always dynamically check addresses of all offset chunks (previous,
2992   next, etc). This turns out to be cheaper than relying on hashes.
2993 */
2994
2995 #if !INSECURE
2996 /* Check if address a is at least as high as any from MORECORE or MMAP */
2997 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
2998 /* Check if address of next chunk n is higher than base chunk p */
2999 #define ok_next(p, n)    ((char*)(p) < (char*)(n))
3000 /* Check if p has inuse status */
3001 #define ok_inuse(p)     is_inuse(p)
3002 /* Check if p has its pinuse bit on */
3003 #define ok_pinuse(p)     pinuse(p)
3004
3005 #else /* !INSECURE */
3006 #define ok_address(M, a) (1)
3007 #define ok_next(b, n)    (1)
3008 #define ok_inuse(p)      (1)
3009 #define ok_pinuse(p)     (1)
3010 #endif /* !INSECURE */
3011
3012 #if (FOOTERS && !INSECURE)
3013 /* Check if (alleged) mstate m has expected magic field */
3014 #define ok_magic(M)      ((M)->magic == mparams.magic)
3015 #else  /* (FOOTERS && !INSECURE) */
3016 #define ok_magic(M)      (1)
3017 #endif /* (FOOTERS && !INSECURE) */
3018
3019 /* In gcc, use __builtin_expect to minimize impact of checks */
3020 #if !INSECURE
3021 #if defined(__GNUC__) && __GNUC__ >= 3
3022 #define RTCHECK(e)  __builtin_expect(e, 1)
3023 #else /* GNUC */
3024 #define RTCHECK(e)  (e)
3025 #endif /* GNUC */
3026 #else /* !INSECURE */
3027 #define RTCHECK(e)  (1)
3028 #endif /* !INSECURE */
3029
3030 /* macros to set up inuse chunks with or without footers */
3031
3032 #if !FOOTERS
3033
3034 #define mark_inuse_foot(M,p,s)
3035
3036 /* Macros for setting head/foot of non-mmapped chunks */
3037
3038 /* Set cinuse bit and pinuse bit of next chunk */
3039 #define set_inuse(M,p,s)\
3040   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
3041   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
3042
3043 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
3044 #define set_inuse_and_pinuse(M,p,s)\
3045   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
3046   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
3047
3048 /* Set size, cinuse and pinuse bit of this chunk */
3049 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
3050   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
3051
3052 #else /* FOOTERS */
3053
3054 /* Set foot of inuse chunk to be xor of mstate and seed */
3055 #define mark_inuse_foot(M,p,s)\
3056   (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
3057
3058 #define get_mstate_for(p)\
3059   ((mstate)(((mchunkptr)((char*)(p) +\
3060     (chunksize(p))))->prev_foot ^ mparams.magic))
3061
3062 #define set_inuse(M,p,s)\
3063   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
3064   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
3065   mark_inuse_foot(M,p,s))
3066
3067 #define set_inuse_and_pinuse(M,p,s)\
3068   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
3069   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
3070  mark_inuse_foot(M,p,s))
3071
3072 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
3073   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
3074   mark_inuse_foot(M, p, s))
3075
3076 #endif /* !FOOTERS */
3077
3078 /* ---------------------------- setting mparams -------------------------- */
3079
3080 /* Initialize mparams */
3081 static int init_mparams(void) {
3082 #ifdef NEED_GLOBAL_LOCK_INIT
3083   if (malloc_global_mutex_status <= 0)
3084     init_malloc_global_mutex();
3085 #endif
3086
3087   ACQUIRE_MALLOC_GLOBAL_LOCK();
3088   if (mparams.magic == 0) {
3089     size_t magic;
3090     size_t psize;
3091     size_t gsize;
3092
3093 #ifndef WIN32
3094     psize = malloc_getpagesize;
3095     gsize = ((DEFAULT_GRANULARITY != 0)? DEFAULT_GRANULARITY : psize);
3096 #else /* WIN32 */
3097     {
3098       SYSTEM_INFO system_info;
3099       GetSystemInfo(&system_info);
3100       psize = system_info.dwPageSize;
3101       gsize = ((DEFAULT_GRANULARITY != 0)?
3102                DEFAULT_GRANULARITY : system_info.dwAllocationGranularity);
3103     }
3104 #endif /* WIN32 */
3105
3106     /* Sanity-check configuration:
3107        size_t must be unsigned and as wide as pointer type.
3108        ints must be at least 4 bytes.
3109        alignment must be at least 8.
3110        Alignment, min chunk size, and page size must all be powers of 2.
3111     */
3112     if ((sizeof(size_t) != sizeof(char*)) ||
3113         (MAX_SIZE_T < MIN_CHUNK_SIZE)  ||
3114         (sizeof(int) < 4)  ||
3115         (MALLOC_ALIGNMENT < (size_t)8U) ||
3116         ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
3117         ((MCHUNK_SIZE      & (MCHUNK_SIZE-SIZE_T_ONE))      != 0) ||
3118         ((gsize            & (gsize-SIZE_T_ONE))            != 0) ||
3119         ((psize            & (psize-SIZE_T_ONE))            != 0))
3120       ABORT;
3121
3122     mparams.granularity = gsize;
3123     mparams.page_size = psize;
3124     mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
3125     mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
3126 #if MORECORE_CONTIGUOUS
3127     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
3128 #else  /* MORECORE_CONTIGUOUS */
3129     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
3130 #endif /* MORECORE_CONTIGUOUS */
3131
3132 #if !ONLY_MSPACES
3133     /* Set up lock for main malloc area */
3134     gm->mflags = mparams.default_mflags;
3135     (void)INITIAL_LOCK(&gm->mutex);
3136 #endif
3137
3138     {
3139 #if USE_DEV_RANDOM
3140       int fd;
3141       unsigned char buf[sizeof(size_t)];
3142       /* Try to use /dev/urandom, else fall back on using time */
3143       if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
3144           read(fd, buf, sizeof(buf)) == sizeof(buf)) {
3145         magic = *((size_t *) buf);
3146         close(fd);
3147       }
3148       else
3149 #endif /* USE_DEV_RANDOM */
3150 #ifdef WIN32
3151         magic = (size_t)(GetTickCount() ^ (size_t)0x55555555U);
3152 #elif defined(LACKS_TIME_H)
3153       magic = (size_t)&magic ^ (size_t)0x55555555U;
3154 #else
3155         magic = (size_t)(time(0) ^ (size_t)0x55555555U);
3156 #endif
3157       magic |= (size_t)8U;    /* ensure nonzero */
3158       magic &= ~(size_t)7U;   /* improve chances of fault for bad values */
3159       /* Until memory modes commonly available, use volatile-write */
3160       (*(volatile size_t *)(&(mparams.magic))) = magic;
3161     }
3162   }
3163
3164   RELEASE_MALLOC_GLOBAL_LOCK();
3165   return 1;
3166 }
3167
3168 /* support for mallopt */
3169 static int change_mparam(int param_number, int value) {
3170   size_t val;
3171   ensure_initialization();
3172   val = (value == -1)? MAX_SIZE_T : (size_t)value;
3173   switch(param_number) {
3174   case M_TRIM_THRESHOLD:
3175     mparams.trim_threshold = val;
3176     return 1;
3177   case M_GRANULARITY:
3178     if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
3179       mparams.granularity = val;
3180       return 1;
3181     }
3182     else
3183       return 0;
3184   case M_MMAP_THRESHOLD:
3185     mparams.mmap_threshold = val;
3186     return 1;
3187   default:
3188     return 0;
3189   }
3190 }
3191
3192 #if DEBUG
3193 /* ------------------------- Debugging Support --------------------------- */
3194
3195 /* Check properties of any chunk, whether free, inuse, mmapped etc  */
3196 static void do_check_any_chunk(mstate m, mchunkptr p) {
3197   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3198   assert(ok_address(m, p));
3199 }
3200
3201 /* Check properties of top chunk */
3202 static void do_check_top_chunk(mstate m, mchunkptr p) {
3203   msegmentptr sp = segment_holding(m, (char*)p);
3204   size_t  sz = p->head & ~INUSE_BITS; /* third-lowest bit can be set! */
3205   assert(sp != 0);
3206   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3207   assert(ok_address(m, p));
3208   assert(sz == m->topsize);
3209   assert(sz > 0);
3210   assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
3211   assert(pinuse(p));
3212   assert(!pinuse(chunk_plus_offset(p, sz)));
3213 }
3214
3215 /* Check properties of (inuse) mmapped chunks */
3216 static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
3217   size_t  sz = chunksize(p);
3218   size_t len = (sz + (p->prev_foot) + MMAP_FOOT_PAD);
3219   assert(is_mmapped(p));
3220   assert(use_mmap(m));
3221   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3222   assert(ok_address(m, p));
3223   assert(!is_small(sz));
3224   assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
3225   assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
3226   assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
3227 }
3228
3229 /* Check properties of inuse chunks */
3230 static void do_check_inuse_chunk(mstate m, mchunkptr p) {
3231   do_check_any_chunk(m, p);
3232   assert(is_inuse(p));
3233   assert(next_pinuse(p));
3234   /* If not pinuse and not mmapped, previous chunk has OK offset */
3235   assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
3236   if (is_mmapped(p))
3237     do_check_mmapped_chunk(m, p);
3238 }
3239
3240 /* Check properties of free chunks */
3241 static void do_check_free_chunk(mstate m, mchunkptr p) {
3242   size_t sz = chunksize(p);
3243   mchunkptr next = chunk_plus_offset(p, sz);
3244   do_check_any_chunk(m, p);
3245   assert(!is_inuse(p));
3246   assert(!next_pinuse(p));
3247   assert (!is_mmapped(p));
3248   if (p != m->dv && p != m->top) {
3249     if (sz >= MIN_CHUNK_SIZE) {
3250       assert((sz & CHUNK_ALIGN_MASK) == 0);
3251       assert(is_aligned(chunk2mem(p)));
3252       assert(next->prev_foot == sz);
3253       assert(pinuse(p));
3254       assert (next == m->top || is_inuse(next));
3255       assert(p->fd->bk == p);
3256       assert(p->bk->fd == p);
3257     }
3258     else  /* markers are always of size SIZE_T_SIZE */
3259       assert(sz == SIZE_T_SIZE);
3260   }
3261 }
3262
3263 /* Check properties of malloced chunks at the point they are malloced */
3264 static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
3265   if (mem != 0) {
3266     mchunkptr p = mem2chunk(mem);
3267     size_t sz = p->head & ~INUSE_BITS;
3268     do_check_inuse_chunk(m, p);
3269     assert((sz & CHUNK_ALIGN_MASK) == 0);
3270     assert(sz >= MIN_CHUNK_SIZE);
3271     assert(sz >= s);
3272     /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
3273     assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
3274   }
3275 }
3276
3277 /* Check a tree and its subtrees.  */
3278 static void do_check_tree(mstate m, tchunkptr t) {
3279   tchunkptr head = 0;
3280   tchunkptr u = t;
3281   bindex_t tindex = t->index;
3282   size_t tsize = chunksize(t);
3283   bindex_t idx;
3284   compute_tree_index(tsize, idx);
3285   assert(tindex == idx);
3286   assert(tsize >= MIN_LARGE_SIZE);
3287   assert(tsize >= minsize_for_tree_index(idx));
3288   assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
3289
3290   do { /* traverse through chain of same-sized nodes */
3291     do_check_any_chunk(m, ((mchunkptr)u));
3292     assert(u->index == tindex);
3293     assert(chunksize(u) == tsize);
3294     assert(!is_inuse(u));
3295     assert(!next_pinuse(u));
3296     assert(u->fd->bk == u);
3297     assert(u->bk->fd == u);
3298     if (u->parent == 0) {
3299       assert(u->child[0] == 0);
3300       assert(u->child[1] == 0);
3301     }
3302     else {
3303       assert(head == 0); /* only one node on chain has parent */
3304       head = u;
3305       assert(u->parent != u);
3306       assert (u->parent->child[0] == u ||
3307               u->parent->child[1] == u ||
3308               *((tbinptr*)(u->parent)) == u);
3309       if (u->child[0] != 0) {
3310         assert(u->child[0]->parent == u);
3311         assert(u->child[0] != u);
3312         do_check_tree(m, u->child[0]);
3313       }
3314       if (u->child[1] != 0) {
3315         assert(u->child[1]->parent == u);
3316         assert(u->child[1] != u);
3317         do_check_tree(m, u->child[1]);
3318       }
3319       if (u->child[0] != 0 && u->child[1] != 0) {
3320         assert(chunksize(u->child[0]) < chunksize(u->child[1]));
3321       }
3322     }
3323     u = u->fd;
3324   } while (u != t);
3325   assert(head != 0);
3326 }
3327
3328 /*  Check all the chunks in a treebin.  */
3329 static void do_check_treebin(mstate m, bindex_t i) {
3330   tbinptr* tb = treebin_at(m, i);
3331   tchunkptr t = *tb;
3332   int empty = (m->treemap & (1U << i)) == 0;
3333   if (t == 0)
3334     assert(empty);
3335   if (!empty)
3336     do_check_tree(m, t);
3337 }
3338
3339 /*  Check all the chunks in a smallbin.  */
3340 static void do_check_smallbin(mstate m, bindex_t i) {
3341   sbinptr b = smallbin_at(m, i);
3342   mchunkptr p = b->bk;
3343   unsigned int empty = (m->smallmap & (1U << i)) == 0;
3344   if (p == b)
3345     assert(empty);
3346   if (!empty) {
3347     for (; p != b; p = p->bk) {
3348       size_t size = chunksize(p);
3349       mchunkptr q;
3350       /* each chunk claims to be free */
3351       do_check_free_chunk(m, p);
3352       /* chunk belongs in bin */
3353       assert(small_index(size) == i);
3354       assert(p->bk == b || chunksize(p->bk) == chunksize(p));
3355       /* chunk is followed by an inuse chunk */
3356       q = next_chunk(p);
3357       if (q->head != FENCEPOST_HEAD)
3358         do_check_inuse_chunk(m, q);
3359     }
3360   }
3361 }
3362
3363 /* Find x in a bin. Used in other check functions. */
3364 static int bin_find(mstate m, mchunkptr x) {
3365   size_t size = chunksize(x);
3366   if (is_small(size)) {
3367     bindex_t sidx = small_index(size);
3368     sbinptr b = smallbin_at(m, sidx);
3369     if (smallmap_is_marked(m, sidx)) {
3370       mchunkptr p = b;
3371       do {
3372         if (p == x)
3373           return 1;
3374       } while ((p = p->fd) != b);
3375     }
3376   }
3377   else {
3378     bindex_t tidx;
3379     compute_tree_index(size, tidx);
3380     if (treemap_is_marked(m, tidx)) {
3381       tchunkptr t = *treebin_at(m, tidx);
3382       size_t sizebits = size << leftshift_for_tree_index(tidx);
3383       while (t != 0 && chunksize(t) != size) {
3384         t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
3385         sizebits <<= 1;
3386       }
3387       if (t != 0) {
3388         tchunkptr u = t;
3389         do {
3390           if (u == (tchunkptr)x)
3391             return 1;
3392         } while ((u = u->fd) != t);
3393       }
3394     }
3395   }
3396   return 0;
3397 }
3398
3399 /* Traverse each chunk and check it; return total */
3400 static size_t traverse_and_check(mstate m) {
3401   size_t sum = 0;
3402   if (is_initialized(m)) {
3403     msegmentptr s = &m->seg;
3404     sum += m->topsize + TOP_FOOT_SIZE;
3405     while (s != 0) {
3406       mchunkptr q = align_as_chunk(s->base);
3407       mchunkptr lastq = 0;
3408       assert(pinuse(q));
3409       while (segment_holds(s, q) &&
3410              q != m->top && q->head != FENCEPOST_HEAD) {
3411         sum += chunksize(q);
3412         if (is_inuse(q)) {
3413           assert(!bin_find(m, q));
3414           do_check_inuse_chunk(m, q);
3415         }
3416         else {
3417           assert(q == m->dv || bin_find(m, q));
3418           assert(lastq == 0 || is_inuse(lastq)); /* Not 2 consecutive free */
3419           do_check_free_chunk(m, q);
3420         }
3421         lastq = q;
3422         q = next_chunk(q);
3423       }
3424       s = s->next;
3425     }
3426   }
3427   return sum;
3428 }
3429
3430
3431 /* Check all properties of malloc_state. */
3432 static void do_check_malloc_state(mstate m) {
3433   bindex_t i;
3434   size_t total;
3435   /* check bins */
3436   for (i = 0; i < NSMALLBINS; ++i)
3437     do_check_smallbin(m, i);
3438   for (i = 0; i < NTREEBINS; ++i)
3439     do_check_treebin(m, i);
3440
3441   if (m->dvsize != 0) { /* check dv chunk */
3442     do_check_any_chunk(m, m->dv);
3443     assert(m->dvsize == chunksize(m->dv));
3444     assert(m->dvsize >= MIN_CHUNK_SIZE);
3445     assert(bin_find(m, m->dv) == 0);
3446   }
3447
3448   if (m->top != 0) {   /* check top chunk */
3449     do_check_top_chunk(m, m->top);
3450     /*assert(m->topsize == chunksize(m->top)); redundant */
3451     assert(m->topsize > 0);
3452     assert(bin_find(m, m->top) == 0);
3453   }
3454
3455   total = traverse_and_check(m);
3456   assert(total <= m->footprint);
3457   assert(m->footprint <= m->max_footprint);
3458 }
3459 #endif /* DEBUG */
3460
3461 /* ----------------------------- statistics ------------------------------ */
3462
3463 #if !NO_MALLINFO
3464 static struct mallinfo internal_mallinfo(mstate m) {
3465   struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
3466   ensure_initialization();
3467   if (!PREACTION(m)) {
3468     check_malloc_state(m);
3469     if (is_initialized(m)) {
3470       size_t nfree = SIZE_T_ONE; /* top always free */
3471       size_t mfree = m->topsize + TOP_FOOT_SIZE;
3472       size_t sum = mfree;
3473       msegmentptr s = &m->seg;
3474       while (s != 0) {
3475         mchunkptr q = align_as_chunk(s->base);
3476         while (segment_holds(s, q) &&
3477                q != m->top && q->head != FENCEPOST_HEAD) {
3478           size_t sz = chunksize(q);
3479           sum += sz;
3480           if (!is_inuse(q)) {
3481             mfree += sz;
3482             ++nfree;
3483           }
3484           q = next_chunk(q);
3485         }
3486         s = s->next;
3487       }
3488
3489       nm.arena    = sum;
3490       nm.ordblks  = nfree;
3491       nm.hblkhd   = m->footprint - sum;
3492       nm.usmblks  = m->max_footprint;
3493       nm.uordblks = m->footprint - mfree;
3494       nm.fordblks = mfree;
3495       nm.keepcost = m->topsize;
3496     }
3497
3498     POSTACTION(m);
3499   }
3500   return nm;
3501 }
3502 #endif /* !NO_MALLINFO */
3503
3504 #if !NO_MALLOC_STATS
3505 static void internal_malloc_stats(mstate m) {
3506   ensure_initialization();
3507   if (!PREACTION(m)) {
3508     size_t maxfp = 0;
3509     size_t fp = 0;
3510     size_t used = 0;
3511     check_malloc_state(m);
3512     if (is_initialized(m)) {
3513       msegmentptr s = &m->seg;
3514       maxfp = m->max_footprint;
3515       fp = m->footprint;
3516       used = fp - (m->topsize + TOP_FOOT_SIZE);
3517
3518       while (s != 0) {
3519         mchunkptr q = align_as_chunk(s->base);
3520         while (segment_holds(s, q) &&
3521                q != m->top && q->head != FENCEPOST_HEAD) {
3522           if (!is_inuse(q))
3523             used -= chunksize(q);
3524           q = next_chunk(q);
3525         }
3526         s = s->next;
3527       }
3528     }
3529     POSTACTION(m); /* drop lock */
3530     fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
3531     fprintf(stderr, "system bytes     = %10lu\n", (unsigned long)(fp));
3532     fprintf(stderr, "in use bytes     = %10lu\n", (unsigned long)(used));
3533   }
3534 }
3535 #endif /* NO_MALLOC_STATS */
3536
3537 /* ----------------------- Operations on smallbins ----------------------- */
3538
3539 /*
3540   Various forms of linking and unlinking are defined as macros.  Even
3541   the ones for trees, which are very long but have very short typical
3542   paths.  This is ugly but reduces reliance on inlining support of
3543   compilers.
3544 */
3545
3546 /* Link a free chunk into a smallbin  */
3547 #define insert_small_chunk(M, P, S) {\
3548   bindex_t I  = small_index(S);\
3549   mchunkptr B = smallbin_at(M, I);\
3550   mchunkptr F = B;\
3551   assert(S >= MIN_CHUNK_SIZE);\
3552   if (!smallmap_is_marked(M, I))\
3553     mark_smallmap(M, I);\
3554   else if (RTCHECK(ok_address(M, B->fd)))\
3555     F = B->fd;\
3556   else {\
3557     CORRUPTION_ERROR_ACTION(M);\
3558   }\
3559   B->fd = P;\
3560   F->bk = P;\
3561   P->fd = F;\
3562   P->bk = B;\
3563 }
3564
3565 /* Unlink a chunk from a smallbin  */
3566 #define unlink_small_chunk(M, P, S) {\
3567   mchunkptr F = P->fd;\
3568   mchunkptr B = P->bk;\
3569   bindex_t I = small_index(S);\
3570   assert(P != B);\
3571   assert(P != F);\
3572   assert(chunksize(P) == small_index2size(I));\
3573   if (RTCHECK(F == smallbin_at(M,I) || (ok_address(M, F) && F->bk == P))) { \
3574     if (B == F) {\
3575       clear_smallmap(M, I);\
3576     }\
3577     else if (RTCHECK(B == smallbin_at(M,I) ||\
3578                      (ok_address(M, B) && B->fd == P))) {\
3579       F->bk = B;\
3580       B->fd = F;\
3581     }\
3582     else {\
3583       CORRUPTION_ERROR_ACTION(M);\
3584     }\
3585   }\
3586   else {\
3587     CORRUPTION_ERROR_ACTION(M);\
3588   }\
3589 }
3590
3591 /* Unlink the first chunk from a smallbin */
3592 #define unlink_first_small_chunk(M, B, P, I) {\
3593   mchunkptr F = P->fd;\
3594   assert(P != B);\
3595   assert(P != F);\
3596   assert(chunksize(P) == small_index2size(I));\
3597   if (B == F) {\
3598     clear_smallmap(M, I);\
3599   }\
3600   else if (RTCHECK(ok_address(M, F) && F->bk == P)) {\
3601     F->bk = B;\
3602     B->fd = F;\
3603   }\
3604   else {\
3605     CORRUPTION_ERROR_ACTION(M);\
3606   }\
3607 }
3608
3609 /* Replace dv node, binning the old one */
3610 /* Used only when dvsize known to be small */
3611 #define replace_dv(M, P, S) {\
3612   size_t DVS = M->dvsize;\
3613   assert(is_small(DVS));\
3614   if (DVS != 0) {\
3615     mchunkptr DV = M->dv;\
3616     insert_small_chunk(M, DV, DVS);\
3617   }\
3618   M->dvsize = S;\
3619   M->dv = P;\
3620 }
3621
3622 /* ------------------------- Operations on trees ------------------------- */
3623
3624 /* Insert chunk into tree */
3625 #define insert_large_chunk(M, X, S) {\
3626   tbinptr* H;\
3627   bindex_t I;\
3628   compute_tree_index(S, I);\
3629   H = treebin_at(M, I);\
3630   X->index = I;\
3631   X->child[0] = X->child[1] = 0;\
3632   if (!treemap_is_marked(M, I)) {\
3633     mark_treemap(M, I);\
3634     *H = X;\
3635     X->parent = (tchunkptr)H;\
3636     X->fd = X->bk = X;\
3637   }\
3638   else {\
3639     tchunkptr T = *H;\
3640     size_t K = S << leftshift_for_tree_index(I);\
3641     for (;;) {\
3642       if (chunksize(T) != S) {\
3643         tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
3644         K <<= 1;\
3645         if (*C != 0)\
3646           T = *C;\
3647         else if (RTCHECK(ok_address(M, C))) {\
3648           *C = X;\
3649           X->parent = T;\
3650           X->fd = X->bk = X;\
3651           break;\
3652         }\
3653         else {\
3654           CORRUPTION_ERROR_ACTION(M);\
3655           break;\
3656         }\
3657       }\
3658       else {\
3659         tchunkptr F = T->fd;\
3660         if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
3661           T->fd = F->bk = X;\
3662           X->fd = F;\
3663           X->bk = T;\
3664           X->parent = 0;\
3665           break;\
3666         }\
3667         else {\
3668           CORRUPTION_ERROR_ACTION(M);\
3669           break;\
3670         }\
3671       }\
3672     }\
3673   }\
3674 }
3675
3676 /*
3677   Unlink steps:
3678
3679   1. If x is a chained node, unlink it from its same-sized fd/bk links
3680      and choose its bk node as its replacement.
3681   2. If x was the last node of its size, but not a leaf node, it must
3682      be replaced with a leaf node (not merely one with an open left or
3683      right), to make sure that lefts and rights of descendents
3684      correspond properly to bit masks.  We use the rightmost descendent
3685      of x.  We could use any other leaf, but this is easy to locate and
3686      tends to counteract removal of leftmosts elsewhere, and so keeps
3687      paths shorter than minimally guaranteed.  This doesn't loop much
3688      because on average a node in a tree is near the bottom.
3689   3. If x is the base of a chain (i.e., has parent links) relink
3690      x's parent and children to x's replacement (or null if none).
3691 */
3692
3693 #define unlink_large_chunk(M, X) {\
3694   tchunkptr XP = X->parent;\
3695   tchunkptr R;\
3696   if (X->bk != X) {\
3697     tchunkptr F = X->fd;\
3698     R = X->bk;\
3699     if (RTCHECK(ok_address(M, F) && F->bk == X && R->fd == X)) {\
3700       F->bk = R;\
3701       R->fd = F;\
3702     }\
3703     else {\
3704       CORRUPTION_ERROR_ACTION(M);\
3705     }\
3706   }\
3707   else {\
3708     tchunkptr* RP;\
3709     if (((R = *(RP = &(X->child[1]))) != 0) ||\
3710         ((R = *(RP = &(X->child[0]))) != 0)) {\
3711       tchunkptr* CP;\
3712       while ((*(CP = &(R->child[1])) != 0) ||\
3713              (*(CP = &(R->child[0])) != 0)) {\
3714         R = *(RP = CP);\
3715       }\
3716       if (RTCHECK(ok_address(M, RP)))\
3717         *RP = 0;\
3718       else {\
3719         CORRUPTION_ERROR_ACTION(M);\
3720       }\
3721     }\
3722   }\
3723   if (XP != 0) {\
3724     tbinptr* H = treebin_at(M, X->index);\
3725     if (X == *H) {\
3726       if ((*H = R) == 0) \
3727         clear_treemap(M, X->index);\
3728     }\
3729     else if (RTCHECK(ok_address(M, XP))) {\
3730       if (XP->child[0] == X) \
3731         XP->child[0] = R;\
3732       else \
3733         XP->child[1] = R;\
3734     }\
3735     else\
3736       CORRUPTION_ERROR_ACTION(M);\
3737     if (R != 0) {\
3738       if (RTCHECK(ok_address(M, R))) {\
3739         tchunkptr C0, C1;\
3740         R->parent = XP;\
3741         if ((C0 = X->child[0]) != 0) {\
3742           if (RTCHECK(ok_address(M, C0))) {\
3743             R->child[0] = C0;\
3744             C0->parent = R;\
3745           }\
3746           else\
3747             CORRUPTION_ERROR_ACTION(M);\
3748         }\
3749         if ((C1 = X->child[1]) != 0) {\
3750           if (RTCHECK(ok_address(M, C1))) {\
3751             R->child[1] = C1;\
3752             C1->parent = R;\
3753           }\
3754           else\
3755             CORRUPTION_ERROR_ACTION(M);\
3756         }\
3757       }\
3758       else\
3759         CORRUPTION_ERROR_ACTION(M);\
3760     }\
3761   }\
3762 }
3763
3764 /* Relays to large vs small bin operations */
3765
3766 #define insert_chunk(M, P, S)\
3767   if (is_small(S)) insert_small_chunk(M, P, S)\
3768   else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
3769
3770 #define unlink_chunk(M, P, S)\
3771   if (is_small(S)) unlink_small_chunk(M, P, S)\
3772   else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
3773
3774
3775 /* Relays to internal calls to malloc/free from realloc, memalign etc */
3776
3777 #if ONLY_MSPACES
3778 #define internal_malloc(m, b) mspace_malloc(m, b)
3779 #define internal_free(m, mem) mspace_free(m,mem);
3780 #else /* ONLY_MSPACES */
3781 #if MSPACES
3782 #define internal_malloc(m, b)\
3783   ((m == gm)? dlmalloc(b) : mspace_malloc(m, b))
3784 #define internal_free(m, mem)\
3785    if (m == gm) dlfree(mem); else mspace_free(m,mem);
3786 #else /* MSPACES */
3787 #define internal_malloc(m, b) dlmalloc(b)
3788 #define internal_free(m, mem) dlfree(mem)
3789 #endif /* MSPACES */
3790 #endif /* ONLY_MSPACES */
3791
3792 /* -----------------------  Direct-mmapping chunks ----------------------- */
3793
3794 /*
3795   Directly mmapped chunks are set up with an offset to the start of
3796   the mmapped region stored in the prev_foot field of the chunk. This
3797   allows reconstruction of the required argument to MUNMAP when freed,
3798   and also allows adjustment of the returned chunk to meet alignment
3799   requirements (especially in memalign).
3800 */
3801
3802 /* Malloc using mmap */
3803 static void* mmap_alloc(mstate m, size_t nb) {
3804   size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3805   if (m->footprint_limit != 0) {
3806     size_t fp = m->footprint + mmsize;
3807     if (fp <= m->footprint || fp > m->footprint_limit)
3808       return 0;
3809   }
3810   if (mmsize > nb) {     /* Check for wrap around 0 */
3811     char* mm = (char*)(CALL_DIRECT_MMAP(mmsize));
3812     if (mm != CMFAIL) {
3813       size_t offset = align_offset(chunk2mem(mm));
3814       size_t psize = mmsize - offset - MMAP_FOOT_PAD;
3815       mchunkptr p = (mchunkptr)(mm + offset);
3816       p->prev_foot = offset;
3817       p->head = psize;
3818       mark_inuse_foot(m, p, psize);
3819       chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
3820       chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
3821
3822       if (m->least_addr == 0 || mm < m->least_addr)
3823         m->least_addr = mm;
3824       if ((m->footprint += mmsize) > m->max_footprint)
3825         m->max_footprint = m->footprint;
3826       assert(is_aligned(chunk2mem(p)));
3827       check_mmapped_chunk(m, p);
3828       return chunk2mem(p);
3829     }
3830   }
3831   return 0;
3832 }
3833
3834 /* Realloc using mmap */
3835 static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb, int flags) {
3836   size_t oldsize = chunksize(oldp);
3837   (void)flags; /* placate people compiling -Wunused */
3838   if (is_small(nb)) /* Can't shrink mmap regions below small size */
3839     return 0;
3840   /* Keep old chunk if big enough but not too big */
3841   if (oldsize >= nb + SIZE_T_SIZE &&
3842       (oldsize - nb) <= (mparams.granularity << 1))
3843     return oldp;
3844   else {
3845     size_t offset = oldp->prev_foot;
3846     size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
3847     size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3848     char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
3849                                   oldmmsize, newmmsize, flags);
3850     if (cp != CMFAIL) {
3851       mchunkptr newp = (mchunkptr)(cp + offset);
3852       size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
3853       newp->head = psize;
3854       mark_inuse_foot(m, newp, psize);
3855       chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
3856       chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
3857
3858       if (cp < m->least_addr)
3859         m->least_addr = cp;
3860       if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
3861         m->max_footprint = m->footprint;
3862       check_mmapped_chunk(m, newp);
3863       return newp;
3864     }
3865   }
3866   return 0;
3867 }
3868
3869
3870 /* -------------------------- mspace management -------------------------- */
3871
3872 /* Initialize top chunk and its size */
3873 static void init_top(mstate m, mchunkptr p, size_t psize) {
3874   /* Ensure alignment */
3875   size_t offset = align_offset(chunk2mem(p));
3876   p = (mchunkptr)((char*)p + offset);
3877   psize -= offset;
3878
3879   m->top = p;
3880   m->topsize = psize;
3881   p->head = psize | PINUSE_BIT;
3882   /* set size of fake trailing chunk holding overhead space only once */
3883   chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
3884   m->trim_check = mparams.trim_threshold; /* reset on each update */
3885 }
3886
3887 /* Initialize bins for a new mstate that is otherwise zeroed out */
3888 static void init_bins(mstate m) {
3889   /* Establish circular links for smallbins */
3890   bindex_t i;
3891   for (i = 0; i < NSMALLBINS; ++i) {
3892     sbinptr bin = smallbin_at(m,i);
3893     bin->fd = bin->bk = bin;
3894   }
3895 }
3896
3897 #if PROCEED_ON_ERROR
3898
3899 /* default corruption action */
3900 static void reset_on_error(mstate m) {
3901   int i;
3902   ++malloc_corruption_error_count;
3903   /* Reinitialize fields to forget about all memory */
3904   m->smallmap = m->treemap = 0;
3905   m->dvsize = m->topsize = 0;
3906   m->seg.base = 0;
3907   m->seg.size = 0;
3908   m->seg.next = 0;
3909   m->top = m->dv = 0;
3910   for (i = 0; i < NTREEBINS; ++i)
3911     *treebin_at(m, i) = 0;
3912   init_bins(m);
3913 }
3914 #endif /* PROCEED_ON_ERROR */
3915
3916 /* Allocate chunk and prepend remainder with chunk in successor base. */
3917 static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
3918                            size_t nb) {
3919   mchunkptr p = align_as_chunk(newbase);
3920   mchunkptr oldfirst = align_as_chunk(oldbase);
3921   size_t psize = (char*)oldfirst - (char*)p;
3922   mchunkptr q = chunk_plus_offset(p, nb);
3923   size_t qsize = psize - nb;
3924   set_size_and_pinuse_of_inuse_chunk(m, p, nb);
3925
3926   assert((char*)oldfirst > (char*)q);
3927   assert(pinuse(oldfirst));
3928   assert(qsize >= MIN_CHUNK_SIZE);
3929
3930   /* consolidate remainder with first chunk of old base */
3931   if (oldfirst == m->top) {
3932     size_t tsize = m->topsize += qsize;
3933     m->top = q;
3934     q->head = tsize | PINUSE_BIT;
3935     check_top_chunk(m, q);
3936   }
3937   else if (oldfirst == m->dv) {
3938     size_t dsize = m->dvsize += qsize;
3939     m->dv = q;
3940     set_size_and_pinuse_of_free_chunk(q, dsize);
3941   }
3942   else {
3943     if (!is_inuse(oldfirst)) {
3944       size_t nsize = chunksize(oldfirst);
3945       unlink_chunk(m, oldfirst, nsize);
3946       oldfirst = chunk_plus_offset(oldfirst, nsize);
3947       qsize += nsize;
3948     }
3949     set_free_with_pinuse(q, qsize, oldfirst);
3950     insert_chunk(m, q, qsize);
3951     check_free_chunk(m, q);
3952   }
3953
3954   check_malloced_chunk(m, chunk2mem(p), nb);
3955   return chunk2mem(p);
3956 }
3957
3958 /* Add a segment to hold a new noncontiguous region */
3959 static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
3960   /* Determine locations and sizes of segment, fenceposts, old top */
3961   char* old_top = (char*)m->top;
3962   msegmentptr oldsp = segment_holding(m, old_top);
3963   char* old_end = oldsp->base + oldsp->size;
3964   size_t ssize = pad_request(sizeof(struct malloc_segment));
3965   char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3966   size_t offset = align_offset(chunk2mem(rawsp));
3967   char* asp = rawsp + offset;
3968   char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
3969   mchunkptr sp = (mchunkptr)csp;
3970   msegmentptr ss = (msegmentptr)(chunk2mem(sp));
3971   mchunkptr tnext = chunk_plus_offset(sp, ssize);
3972   mchunkptr p = tnext;
3973   int nfences = 0;
3974
3975   /* reset top to new space */
3976   init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
3977
3978   /* Set up segment record */
3979   assert(is_aligned(ss));
3980   set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
3981   *ss = m->seg; /* Push current record */
3982   m->seg.base = tbase;
3983   m->seg.size = tsize;
3984   m->seg.sflags = mmapped;
3985   m->seg.next = ss;
3986
3987   /* Insert trailing fenceposts */
3988   for (;;) {
3989     mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
3990     p->head = FENCEPOST_HEAD;
3991     ++nfences;
3992     if ((char*)(&(nextp->head)) < old_end)
3993       p = nextp;
3994     else
3995       break;
3996   }
3997   assert(nfences >= 2);
3998
3999   /* Insert the rest of old top into a bin as an ordinary free chunk */
4000   if (csp != old_top) {
4001     mchunkptr q = (mchunkptr)old_top;
4002     size_t psize = csp - old_top;
4003     mchunkptr tn = chunk_plus_offset(q, psize);
4004     set_free_with_pinuse(q, psize, tn);
4005     insert_chunk(m, q, psize);
4006   }
4007
4008   check_top_chunk(m, m->top);
4009 }
4010
4011 /* -------------------------- System allocation -------------------------- */
4012
4013 /* Get memory from system using MORECORE or MMAP */
4014 static void* sys_alloc(mstate m, size_t nb) {
4015   char* tbase = CMFAIL;
4016   size_t tsize = 0;
4017   flag_t mmap_flag = 0;
4018   size_t asize; /* allocation size */
4019
4020   ensure_initialization();
4021
4022   /* Directly map large chunks, but only if already initialized */
4023   if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) {
4024     void* mem = mmap_alloc(m, nb);
4025     if (mem != 0)
4026       return mem;
4027   }
4028
4029   asize = granularity_align(nb + SYS_ALLOC_PADDING);
4030   if (asize <= nb)
4031     return 0; /* wraparound */
4032   if (m->footprint_limit != 0) {
4033     size_t fp = m->footprint + asize;
4034     if (fp <= m->footprint || fp > m->footprint_limit)
4035       return 0;
4036   }
4037
4038   /*
4039     Try getting memory in any of three ways (in most-preferred to
4040     least-preferred order):
4041     1. A call to MORECORE that can normally contiguously extend memory.
4042        (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
4043        or main space is mmapped or a previous contiguous call failed)
4044     2. A call to MMAP new space (disabled if not HAVE_MMAP).
4045        Note that under the default settings, if MORECORE is unable to
4046        fulfill a request, and HAVE_MMAP is true, then mmap is
4047        used as a noncontiguous system allocator. This is a useful backup
4048        strategy for systems with holes in address spaces -- in this case
4049        sbrk cannot contiguously expand the heap, but mmap may be able to
4050        find space.
4051     3. A call to MORECORE that cannot usually contiguously extend memory.
4052        (disabled if not HAVE_MORECORE)
4053
4054    In all cases, we need to request enough bytes from system to ensure
4055    we can malloc nb bytes upon success, so pad with enough space for
4056    top_foot, plus alignment-pad to make sure we don't lose bytes if
4057    not on boundary, and round this up to a granularity unit.
4058   */
4059
4060   if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
4061     char* br = CMFAIL;
4062     msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
4063     ACQUIRE_MALLOC_GLOBAL_LOCK();
4064
4065     if (ss == 0) {  /* First time through or recovery */
4066       char* base = (char*)CALL_MORECORE(0);
4067       if (base != CMFAIL) {
4068         size_t fp;
4069         /* Adjust to end on a page boundary */
4070         if (!is_page_aligned(base))
4071           asize += (page_align((size_t)base) - (size_t)base);
4072         fp = m->footprint + asize; /* recheck limits */
4073         if (asize > nb && asize < HALF_MAX_SIZE_T &&
4074             (m->footprint_limit == 0 ||
4075              (fp > m->footprint && fp <= m->footprint_limit)) &&
4076             (br = (char*)(CALL_MORECORE(asize))) == base) {
4077           tbase = base;
4078           tsize = asize;
4079         }
4080       }
4081     }
4082     else {
4083       /* Subtract out existing available top space from MORECORE request. */
4084       asize = granularity_align(nb - m->topsize + SYS_ALLOC_PADDING);
4085       /* Use mem here only if it did continuously extend old space */
4086       if (asize < HALF_MAX_SIZE_T &&
4087           (br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {
4088         tbase = br;
4089         tsize = asize;
4090       }
4091     }
4092
4093     if (tbase == CMFAIL) {    /* Cope with partial failure */
4094       if (br != CMFAIL) {    /* Try to use/extend the space we did get */
4095         if (asize < HALF_MAX_SIZE_T &&
4096             asize < nb + SYS_ALLOC_PADDING) {
4097           size_t esize = granularity_align(nb + SYS_ALLOC_PADDING - asize);
4098           if (esize < HALF_MAX_SIZE_T) {
4099             char* end = (char*)CALL_MORECORE(esize);
4100             if (end != CMFAIL)
4101               asize += esize;
4102             else {            /* Can't use; try to release */
4103               (void) CALL_MORECORE(-asize);
4104               br = CMFAIL;
4105             }
4106           }
4107         }
4108       }
4109       if (br != CMFAIL) {    /* Use the space we did get */
4110         tbase = br;
4111         tsize = asize;
4112       }
4113       else
4114         disable_contiguous(m); /* Don't try contiguous path in the future */
4115     }
4116
4117     RELEASE_MALLOC_GLOBAL_LOCK();
4118   }
4119
4120   if (HAVE_MMAP && tbase == CMFAIL) {  /* Try MMAP */
4121     char* mp = (char*)(CALL_MMAP(asize));
4122     if (mp != CMFAIL) {
4123       tbase = mp;
4124       tsize = asize;
4125       mmap_flag = USE_MMAP_BIT;
4126     }
4127   }
4128
4129   if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
4130     if (asize < HALF_MAX_SIZE_T) {
4131       char* br = CMFAIL;
4132       char* end = CMFAIL;
4133       ACQUIRE_MALLOC_GLOBAL_LOCK();
4134       br = (char*)(CALL_MORECORE(asize));
4135       end = (char*)(CALL_MORECORE(0));
4136       RELEASE_MALLOC_GLOBAL_LOCK();
4137       if (br != CMFAIL && end != CMFAIL && br < end) {
4138         size_t ssize = end - br;
4139         if (ssize > nb + TOP_FOOT_SIZE) {
4140           tbase = br;
4141           tsize = ssize;
4142         }
4143       }
4144     }
4145   }
4146
4147   if (tbase != CMFAIL) {
4148
4149     if ((m->footprint += tsize) > m->max_footprint)
4150       m->max_footprint = m->footprint;
4151
4152     if (!is_initialized(m)) { /* first-time initialization */
4153       if (m->least_addr == 0 || tbase < m->least_addr)
4154         m->least_addr = tbase;
4155       m->seg.base = tbase;
4156       m->seg.size = tsize;
4157       m->seg.sflags = mmap_flag;
4158       m->magic = mparams.magic;
4159       m->release_checks = MAX_RELEASE_CHECK_RATE;
4160       init_bins(m);
4161 #if !ONLY_MSPACES
4162       if (is_global(m))
4163         init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
4164       else
4165 #endif
4166       {
4167         /* Offset top by embedded malloc_state */
4168         mchunkptr mn = next_chunk(mem2chunk(m));
4169         init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
4170       }
4171     }
4172
4173     else {
4174       /* Try to merge with an existing segment */
4175       msegmentptr sp = &m->seg;
4176       /* Only consider most recent segment if traversal suppressed */
4177       while (sp != 0 && tbase != sp->base + sp->size)
4178         sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
4179       if (sp != 0 &&
4180           !is_extern_segment(sp) &&
4181           (sp->sflags & USE_MMAP_BIT) == mmap_flag &&
4182           segment_holds(sp, m->top)) { /* append */
4183         sp->size += tsize;
4184         init_top(m, m->top, m->topsize + tsize);
4185       }
4186       else {
4187         if (tbase < m->least_addr)
4188           m->least_addr = tbase;
4189         sp = &m->seg;
4190         while (sp != 0 && sp->base != tbase + tsize)
4191           sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
4192         if (sp != 0 &&
4193             !is_extern_segment(sp) &&
4194             (sp->sflags & USE_MMAP_BIT) == mmap_flag) {
4195           char* oldbase = sp->base;
4196           sp->base = tbase;
4197           sp->size += tsize;
4198           return prepend_alloc(m, tbase, oldbase, nb);
4199         }
4200         else
4201           add_segment(m, tbase, tsize, mmap_flag);
4202       }
4203     }
4204
4205     if (nb < m->topsize) { /* Allocate from new or extended top space */
4206       size_t rsize = m->topsize -= nb;
4207       mchunkptr p = m->top;
4208       mchunkptr r = m->top = chunk_plus_offset(p, nb);
4209       r->head = rsize | PINUSE_BIT;
4210       set_size_and_pinuse_of_inuse_chunk(m, p, nb);
4211       check_top_chunk(m, m->top);
4212       check_malloced_chunk(m, chunk2mem(p), nb);
4213       return chunk2mem(p);
4214     }
4215   }
4216
4217   MALLOC_FAILURE_ACTION;
4218   return 0;
4219 }
4220
4221 /* -----------------------  system deallocation -------------------------- */
4222
4223 /* Unmap and unlink any mmapped segments that don't contain used chunks */
4224 static size_t release_unused_segments(mstate m) {
4225   size_t released = 0;
4226   int nsegs = 0;
4227   msegmentptr pred = &m->seg;
4228   msegmentptr sp = pred->next;
4229   while (sp != 0) {
4230     char* base = sp->base;
4231     size_t size = sp->size;
4232     msegmentptr next = sp->next;
4233     ++nsegs;
4234     if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
4235       mchunkptr p = align_as_chunk(base);
4236       size_t psize = chunksize(p);
4237       /* Can unmap if first chunk holds entire segment and not pinned */
4238       if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
4239         tchunkptr tp = (tchunkptr)p;
4240         assert(segment_holds(sp, (char*)sp));
4241         if (p == m->dv) {
4242           m->dv = 0;
4243           m->dvsize = 0;
4244         }
4245         else {
4246           unlink_large_chunk(m, tp);
4247         }
4248         if (CALL_MUNMAP(base, size) == 0) {
4249           released += size;
4250           m->footprint -= size;
4251           /* unlink obsoleted record */
4252           sp = pred;
4253           sp->next = next;
4254         }
4255         else { /* back out if cannot unmap */
4256           insert_large_chunk(m, tp, psize);
4257         }
4258       }
4259     }
4260     if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */
4261       break;
4262     pred = sp;
4263     sp = next;
4264   }
4265   /* Reset check counter */
4266   m->release_checks = ((nsegs > MAX_RELEASE_CHECK_RATE)?
4267                        nsegs : MAX_RELEASE_CHECK_RATE);
4268   return released;
4269 }
4270
4271 static int sys_trim(mstate m, size_t pad) {
4272   size_t released = 0;
4273   ensure_initialization();
4274   if (pad < MAX_REQUEST && is_initialized(m)) {
4275     pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
4276
4277     if (m->topsize > pad) {
4278       /* Shrink top space in granularity-size units, keeping at least one */
4279       size_t unit = mparams.granularity;
4280       size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
4281                       SIZE_T_ONE) * unit;
4282       msegmentptr sp = segment_holding(m, (char*)m->top);
4283
4284       if (!is_extern_segment(sp)) {
4285         if (is_mmapped_segment(sp)) {
4286           if (HAVE_MMAP &&
4287               sp->size >= extra &&
4288               !has_segment_link(m, sp)) { /* can't shrink if pinned */
4289             size_t newsize = sp->size - extra;
4290             /* Prefer mremap, fall back to munmap */
4291             if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
4292                 (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
4293               released = extra;
4294             }
4295           }
4296         }
4297         else if (HAVE_MORECORE) {
4298           if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
4299             extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
4300           ACQUIRE_MALLOC_GLOBAL_LOCK();
4301           {
4302             /* Make sure end of memory is where we last set it. */
4303             char* old_br = (char*)(CALL_MORECORE(0));
4304             if (old_br == sp->base + sp->size) {
4305               char* rel_br = (char*)(CALL_MORECORE(-extra));
4306               char* new_br = (char*)(CALL_MORECORE(0));
4307               if (rel_br != CMFAIL && new_br < old_br)
4308                 released = old_br - new_br;
4309             }
4310           }
4311           RELEASE_MALLOC_GLOBAL_LOCK();
4312         }
4313       }
4314
4315       if (released != 0) {
4316         sp->size -= released;
4317         m->footprint -= released;
4318         init_top(m, m->top, m->topsize - released);
4319         check_top_chunk(m, m->top);
4320       }
4321     }
4322
4323     /* Unmap any unused mmapped segments */
4324     if (HAVE_MMAP)
4325       released += release_unused_segments(m);
4326
4327     /* On failure, disable autotrim to avoid repeated failed future calls */
4328     if (released == 0 && m->topsize > m->trim_check)
4329       m->trim_check = MAX_SIZE_T;
4330   }
4331
4332   return (released != 0)? 1 : 0;
4333 }
4334
4335 /* Consolidate and bin a chunk. Differs from exported versions
4336    of free mainly in that the chunk need not be marked as inuse.
4337 */
4338 static void dispose_chunk(mstate m, mchunkptr p, size_t psize) {
4339   mchunkptr next = chunk_plus_offset(p, psize);
4340   if (!pinuse(p)) {
4341     mchunkptr prev;
4342     size_t prevsize = p->prev_foot;
4343     if (is_mmapped(p)) {
4344       psize += prevsize + MMAP_FOOT_PAD;
4345       if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4346         m->footprint -= psize;
4347       return;
4348     }
4349     prev = chunk_minus_offset(p, prevsize);
4350     psize += prevsize;
4351     p = prev;
4352     if (RTCHECK(ok_address(m, prev))) { /* consolidate backward */
4353       if (p != m->dv) {
4354         unlink_chunk(m, p, prevsize);
4355       }
4356       else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4357         m->dvsize = psize;
4358         set_free_with_pinuse(p, psize, next);
4359         return;
4360       }
4361     }
4362     else {
4363       CORRUPTION_ERROR_ACTION(m);
4364       return;
4365     }
4366   }
4367   if (RTCHECK(ok_address(m, next))) {
4368     if (!cinuse(next)) {  /* consolidate forward */
4369       if (next == m->top) {
4370         size_t tsize = m->topsize += psize;
4371         m->top = p;
4372         p->head = tsize | PINUSE_BIT;
4373         if (p == m->dv) {
4374           m->dv = 0;
4375           m->dvsize = 0;
4376         }
4377         return;
4378       }
4379       else if (next == m->dv) {
4380