Clean up dlmalloc.
[wincetools.git] / loader / dlmalloc.c
1 /* Use simple spinlock protection.  */
2 #define USE_LOCKS 1
3 /* Prefix exported symbols with "dl", ie dlmalloc etc.  */
4 #define USE_DL_PREFIX 1
5 /* On Windows CE, minimum allocation is 2MB if you want to use the
6    high memory area.  */
7 #define DEFAULT_GRANULARITY (2 * 1024 * 1024)
8 #define DEFAULT_MMAP_THRESHOLD (2* 1024 * 1024)
9 /* Maybe replace this with something more appropriate.  */
10 #define ABORT exit(1)
11
12 /*
13   This is a version (aka dlmalloc) of malloc/free/realloc written by
14   Doug Lea and released to the public domain, as explained at
15   http://creativecommons.org/licenses/publicdomain.  Send questions,
16   comments, complaints, performance data, etc to dl@cs.oswego.edu
17
18 * Version 2.8.4 Wed May 27 09:56:23 2009  Doug Lea  (dl at gee)
19
20    Note: There may be an updated version of this malloc obtainable at
21            ftp://gee.cs.oswego.edu/pub/misc/malloc.c
22          Check before installing!
23
24 * Quickstart
25
26   This library is all in one file to simplify the most common usage:
27   ftp it, compile it (-O3), and link it into another program. All of
28   the compile-time options default to reasonable values for use on
29   most platforms.  You might later want to step through various
30   compile-time and dynamic tuning options.
31
32   For convenience, an include file for code using this malloc is at:
33      ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.4.h
34   You don't really need this .h file unless you call functions not
35   defined in your system include files.  The .h file contains only the
36   excerpts from this file needed for using this malloc on ANSI C/C++
37   systems, so long as you haven't changed compile-time options about
38   naming and tuning parameters.  If you do, then you can create your
39   own malloc.h that does include all settings by cutting at the point
40   indicated below. Note that you may already by default be using a C
41   library containing a malloc that is based on some version of this
42   malloc (for example in linux). You might still want to use the one
43   in this file to customize settings or to avoid overheads associated
44   with library versions.
45
46 * Vital statistics:
47
48   Supported pointer/size_t representation:       4 or 8 bytes
49        size_t MUST be an unsigned type of the same width as
50        pointers. (If you are using an ancient system that declares
51        size_t as a signed type, or need it to be a different width
52        than pointers, you can use a previous release of this malloc
53        (e.g. 2.7.2) supporting these.)
54
55   Alignment:                                     8 bytes (default)
56        This suffices for nearly all current machines and C compilers.
57        However, you can define MALLOC_ALIGNMENT to be wider than this
58        if necessary (up to 128bytes), at the expense of using more space.
59
60   Minimum overhead per allocated chunk:   4 or  8 bytes (if 4byte sizes)
61                                           8 or 16 bytes (if 8byte sizes)
62        Each malloced chunk has a hidden word of overhead holding size
63        and status information, and additional cross-check word
64        if FOOTERS is defined.
65
66   Minimum allocated size: 4-byte ptrs:  16 bytes    (including overhead)
67                           8-byte ptrs:  32 bytes    (including overhead)
68
69        Even a request for zero bytes (i.e., malloc(0)) returns a
70        pointer to something of the minimum allocatable size.
71        The maximum overhead wastage (i.e., number of extra bytes
72        allocated than were requested in malloc) is less than or equal
73        to the minimum size, except for requests >= mmap_threshold that
74        are serviced via mmap(), where the worst case wastage is about
75        32 bytes plus the remainder from a system page (the minimal
76        mmap unit); typically 4096 or 8192 bytes.
77
78   Security: static-safe; optionally more or less
79        The "security" of malloc refers to the ability of malicious
80        code to accentuate the effects of errors (for example, freeing
81        space that is not currently malloc'ed or overwriting past the
82        ends of chunks) in code that calls malloc.  This malloc
83        guarantees not to modify any memory locations below the base of
84        heap, i.e., static variables, even in the presence of usage
85        errors.  The routines additionally detect most improper frees
86        and reallocs.  All this holds as long as the static bookkeeping
87        for malloc itself is not corrupted by some other means.  This
88        is only one aspect of security -- these checks do not, and
89        cannot, detect all possible programming errors.
90
91        If FOOTERS is defined nonzero, then each allocated chunk
92        carries an additional check word to verify that it was malloced
93        from its space.  These check words are the same within each
94        execution of a program using malloc, but differ across
95        executions, so externally crafted fake chunks cannot be
96        freed. This improves security by rejecting frees/reallocs that
97        could corrupt heap memory, in addition to the checks preventing
98        writes to statics that are always on.  This may further improve
99        security at the expense of time and space overhead.  (Note that
100        FOOTERS may also be worth using with MSPACES.)
101
102        By default detected errors cause the program to abort (calling
103        "abort()"). You can override this to instead proceed past
104        errors by defining PROCEED_ON_ERROR.  In this case, a bad free
105        has no effect, and a malloc that encounters a bad address
106        caused by user overwrites will ignore the bad address by
107        dropping pointers and indices to all known memory. This may
108        be appropriate for programs that should continue if at all
109        possible in the face of programming errors, although they may
110        run out of memory because dropped memory is never reclaimed.
111
112        If you don't like either of these options, you can define
113        CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
114        else. And if if you are sure that your program using malloc has
115        no errors or vulnerabilities, you can define INSECURE to 1,
116        which might (or might not) provide a small performance improvement.
117
118   Thread-safety: NOT thread-safe unless USE_LOCKS defined
119        When USE_LOCKS is defined, each public call to malloc, free,
120        etc is surrounded with either a pthread mutex or a win32
121        spinlock (depending on WIN32). This is not especially fast, and
122        can be a major bottleneck.  It is designed only to provide
123        minimal protection in concurrent environments, and to provide a
124        basis for extensions.  If you are using malloc in a concurrent
125        program, consider instead using nedmalloc
126        (http://www.nedprod.com/programs/portable/nedmalloc/) or
127        ptmalloc (See http://www.malloc.de), which are derived
128        from 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.
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.
239
240 MALLOC_ALIGNMENT         default: (size_t)8
241   Controls the minimum alignment for malloc'ed chunks.  It must be a
242   power of two and at least 8, even on machines for which smaller
243   alignments would suffice. It may be defined as larger than this
244   though. Note however that code and data structures are optimized for
245   the case of 8-byte alignment.
246
247 MSPACES                  default: 0 (false)
248   If true, compile in support for independent allocation spaces.
249   This is only supported if HAVE_MMAP is true.
250
251 ONLY_MSPACES             default: 0 (false)
252   If true, only compile in mspace versions, not regular versions.
253
254 USE_LOCKS                default: 0 (false)
255   Causes each call to each public routine to be surrounded with
256   pthread or WIN32 mutex lock/unlock. (If set true, this can be
257   overridden on a per-mspace basis for mspace versions.) If set to a
258   non-zero value other than 1, locks are used, but their
259   implementation is left out, so lock functions must be supplied manually,
260   as described below.
261
262 USE_SPIN_LOCKS           default: 1 iff USE_LOCKS and on x86 using gcc or MSC
263   If true, uses custom spin locks for locking. This is currently
264   supported only for x86 platforms using gcc or recent MS compilers.
265   Otherwise, posix locks or win32 critical sections are used.
266
267 FOOTERS                  default: 0
268   If true, provide extra checking and dispatching by placing
269   information in the footers of allocated chunks. This adds
270   space and time overhead.
271
272 INSECURE                 default: 0
273   If true, omit checks for usage errors and heap space overwrites.
274
275 USE_DL_PREFIX            default: NOT defined
276   Causes compiler to prefix all public routines with the string 'dl'.
277   This can be useful when you only want to use this malloc in one part
278   of a program, using your regular system malloc elsewhere.
279
280 ABORT                    default: defined as abort()
281   Defines how to abort on failed checks.  On most systems, a failed
282   check cannot die with an "assert" or even print an informative
283   message, because the underlying print routines in turn call malloc,
284   which will fail again.  Generally, the best policy is to simply call
285   abort(). It's not very useful to do more than this because many
286   errors due to overwriting will show up as address faults (null, odd
287   addresses etc) rather than malloc-triggered checks, so will also
288   abort.  Also, most compilers know that abort() does not return, so
289   can better optimize code conditionally calling it.
290
291 PROCEED_ON_ERROR           default: defined as 0 (false)
292   Controls whether detected bad addresses cause them to bypassed
293   rather than aborting. If set, detected bad arguments to free and
294   realloc are ignored. And all bookkeeping information is zeroed out
295   upon a detected overwrite of freed heap space, thus losing the
296   ability to ever return it from malloc again, but enabling the
297   application to proceed. If PROCEED_ON_ERROR is defined, the
298   static variable malloc_corruption_error_count is compiled in
299   and can be examined to see if errors have occurred. This option
300   generates slower code than the default abort policy.
301
302 DEBUG                    default: NOT defined
303   The DEBUG setting is mainly intended for people trying to modify
304   this code or diagnose problems when porting to new platforms.
305   However, it may also be able to better isolate user errors than just
306   using runtime checks.  The assertions in the check routines spell
307   out in more detail the assumptions and invariants underlying the
308   algorithms.  The checking is fairly extensive, and will slow down
309   execution noticeably. Calling malloc_stats or mallinfo with DEBUG
310   set will attempt to check every non-mmapped allocated and free chunk
311   in the course of computing the summaries.
312
313 ABORT_ON_ASSERT_FAILURE   default: defined as 1 (true)
314   Debugging assertion failures can be nearly impossible if your
315   version of the assert macro causes malloc to be called, which will
316   lead to a cascade of further failures, blowing the runtime stack.
317   ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
318   which will usually make debugging easier.
319
320 MALLOC_FAILURE_ACTION     default: sets errno to ENOMEM, or no-op on win32
321   The action to take before "return 0" when malloc fails to be able to
322   return memory because there is none available.
323
324 HAVE_MORECORE             default: 1 (true) unless win32 or ONLY_MSPACES
325   True if this system supports sbrk or an emulation of it.
326
327 MORECORE                  default: sbrk
328   The name of the sbrk-style system routine to call to obtain more
329   memory.  See below for guidance on writing custom MORECORE
330   functions. The type of the argument to sbrk/MORECORE varies across
331   systems.  It cannot be size_t, because it supports negative
332   arguments, so it is normally the signed type of the same width as
333   size_t (sometimes declared as "intptr_t").  It doesn't much matter
334   though. Internally, we only call it with arguments less than half
335   the max value of a size_t, which should work across all reasonable
336   possibilities, although sometimes generating compiler warnings.
337
338 MORECORE_CONTIGUOUS       default: 1 (true) if HAVE_MORECORE
339   If true, take advantage of fact that consecutive calls to MORECORE
340   with positive arguments always return contiguous increasing
341   addresses.  This is true of unix sbrk. It does not hurt too much to
342   set it true anyway, since malloc copes with non-contiguities.
343   Setting it false when definitely non-contiguous saves time
344   and possibly wasted space it would take to discover this though.
345
346 MORECORE_CANNOT_TRIM      default: NOT defined
347   True if MORECORE cannot release space back to the system when given
348   negative arguments. This is generally necessary only if you are
349   using a hand-crafted MORECORE function that cannot handle negative
350   arguments.
351
352 NO_SEGMENT_TRAVERSAL       default: 0
353   If non-zero, suppresses traversals of memory segments
354   returned by either MORECORE or CALL_MMAP. This disables
355   merging of segments that are contiguous, and selectively
356   releasing them to the OS if unused, but bounds execution times.
357
358 HAVE_MMAP                 default: 1 (true)
359   True if this system supports mmap or an emulation of it.  If so, and
360   HAVE_MORECORE is not true, MMAP is used for all system
361   allocation. If set and HAVE_MORECORE is true as well, MMAP is
362   primarily used to directly allocate very large blocks. It is also
363   used as a backup strategy in cases where MORECORE fails to provide
364   space from system. Note: A single call to MUNMAP is assumed to be
365   able to unmap memory that may have be allocated using multiple calls
366   to MMAP, so long as they are adjacent.
367
368 HAVE_MREMAP               default: 1 on linux, else 0
369   If true realloc() uses mremap() to re-allocate large blocks and
370   extend or shrink allocation spaces.
371
372 MMAP_CLEARS               default: 1 except on WINCE.
373   True if mmap clears memory so calloc doesn't need to. This is true
374   for standard unix mmap using /dev/zero and on WIN32 except for WINCE.
375
376 USE_BUILTIN_FFS            default: 0 (i.e., not used)
377   Causes malloc to use the builtin ffs() function to compute indices.
378   Some compilers may recognize and intrinsify ffs to be faster than the
379   supplied C version. Also, the case of x86 using gcc is special-cased
380   to an asm instruction, so is already as fast as it can be, and so
381   this setting has no effect. Similarly for Win32 under recent MS compilers.
382   (On most x86s, the asm version is only slightly faster than the C version.)
383
384 malloc_getpagesize         default: derive from system includes, or 4096.
385   The system page size. To the extent possible, this malloc manages
386   memory from the system in page-size units.  This may be (and
387   usually is) a function rather than a constant. This is ignored
388   if WIN32, where page size is determined using getSystemInfo during
389   initialization.
390
391 USE_DEV_RANDOM             default: 0 (i.e., not used)
392   Causes malloc to use /dev/random to initialize secure magic seed for
393   stamping footers. Otherwise, the current time is used.
394
395 NO_MALLINFO                default: 0
396   If defined, don't compile "mallinfo". This can be a simple way
397   of dealing with mismatches between system declarations and
398   those in this file.
399
400 MALLINFO_FIELD_TYPE        default: size_t
401   The type of the fields in the mallinfo struct. This was originally
402   defined as "int" in SVID etc, but is more usefully defined as
403   size_t. The value is used only if  HAVE_USR_INCLUDE_MALLOC_H is not set
404
405 REALLOC_ZERO_BYTES_FREES    default: not defined
406   This should be set if a call to realloc with zero bytes should
407   be the same as a call to free. Some people think it should. Otherwise,
408   since this malloc returns a unique pointer for malloc(0), so does
409   realloc(p, 0).
410
411 LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
412 LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H,  LACKS_ERRNO_H
413 LACKS_STDLIB_H                default: NOT defined unless on WIN32
414   Define these if your system does not have these header files.
415   You might need to manually insert some of the declarations they provide.
416
417 DEFAULT_GRANULARITY        default: page size if MORECORE_CONTIGUOUS,
418                                 system_info.dwAllocationGranularity in WIN32,
419                                 otherwise 64K.
420       Also settable using mallopt(M_GRANULARITY, x)
421   The unit for allocating and deallocating memory from the system.  On
422   most systems with contiguous MORECORE, there is no reason to
423   make this more than a page. However, systems with MMAP tend to
424   either require or encourage larger granularities.  You can increase
425   this value to prevent system allocation functions to be called so
426   often, especially if they are slow.  The value must be at least one
427   page and must be a power of two.  Setting to 0 causes initialization
428   to either page size or win32 region size.  (Note: In previous
429   versions of malloc, the equivalent of this option was called
430   "TOP_PAD")
431
432 DEFAULT_TRIM_THRESHOLD    default: 2MB
433       Also settable using mallopt(M_TRIM_THRESHOLD, x)
434   The maximum amount of unused top-most memory to keep before
435   releasing via malloc_trim in free().  Automatic trimming is mainly
436   useful in long-lived programs using contiguous MORECORE.  Because
437   trimming via sbrk can be slow on some systems, and can sometimes be
438   wasteful (in cases where programs immediately afterward allocate
439   more large chunks) the value should be high enough so that your
440   overall system performance would improve by releasing this much
441   memory.  As a rough guide, you might set to a value close to the
442   average size of a process (program) running on your system.
443   Releasing this much memory would allow such a process to run in
444   memory.  Generally, it is worth tuning trim thresholds when a
445   program undergoes phases where several large chunks are allocated
446   and released in ways that can reuse each other's storage, perhaps
447   mixed with phases where there are no such chunks at all. The trim
448   value must be greater than page size to have any useful effect.  To
449   disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
450   some people use of mallocing a huge space and then freeing it at
451   program startup, in an attempt to reserve system memory, doesn't
452   have the intended effect under automatic trimming, since that memory
453   will immediately be returned to the system.
454
455 DEFAULT_MMAP_THRESHOLD       default: 256K
456       Also settable using mallopt(M_MMAP_THRESHOLD, x)
457   The request size threshold for using MMAP to directly service a
458   request. Requests of at least this size that cannot be allocated
459   using already-existing space will be serviced via mmap.  (If enough
460   normal freed space already exists it is used instead.)  Using mmap
461   segregates relatively large chunks of memory so that they can be
462   individually obtained and released from the host system. A request
463   serviced through mmap is never reused by any other request (at least
464   not directly; the system may just so happen to remap successive
465   requests to the same locations).  Segregating space in this way has
466   the benefits that: Mmapped space can always be individually released
467   back to the system, which helps keep the system level memory demands
468   of a long-lived program low.  Also, mapped memory doesn't become
469   `locked' between other chunks, as can happen with normally allocated
470   chunks, which means that even trimming via malloc_trim would not
471   release them.  However, it has the disadvantage that the space
472   cannot be reclaimed, consolidated, and then used to service later
473   requests, as happens with normal chunks.  The advantages of mmap
474   nearly always outweigh disadvantages for "large" chunks, but the
475   value of "large" may vary across systems.  The default is an
476   empirically derived value that works well in most systems. You can
477   disable mmap by setting to MAX_SIZE_T.
478
479 MAX_RELEASE_CHECK_RATE   default: 4095 unless not HAVE_MMAP
480   The number of consolidated frees between checks to release
481   unused segments when freeing. When using non-contiguous segments,
482   especially with multiple mspaces, checking only for topmost space
483   doesn't always suffice to trigger trimming. To compensate for this,
484   free() will, with a period of MAX_RELEASE_CHECK_RATE (or the
485   current number of segments, if greater) try to release unused
486   segments to the OS when freeing chunks that result in
487   consolidation. The best value for this parameter is a compromise
488   between slowing down frees with relatively costly checks that
489   rarely trigger versus holding on to unused memory. To effectively
490   disable, set to MAX_SIZE_T. This may lead to a very slight speed
491   improvement at the expense of carrying around more memory.
492 */
493
494 /* Version identifier to allow people to support multiple versions */
495 #ifndef DLMALLOC_VERSION
496 #define DLMALLOC_VERSION 20804
497 #endif /* DLMALLOC_VERSION */
498
499 //#ifndef WIN32
500 #ifdef _WIN32
501 #define WIN32 1
502 #endif  /* _WIN32 */
503 #ifdef _WIN32_WCE
504 #define LACKS_FCNTL_H
505 #define WIN32 1
506 #endif /* _WIN32_WCE */
507 //#endif  /* WIN32 */
508 #ifdef WIN32
509 #define WIN32_LEAN_AND_MEAN
510 #include <windows.h>
511 #define HAVE_MMAP 1
512 #define HAVE_MORECORE 0
513 #define LACKS_UNISTD_H
514 #define LACKS_SYS_PARAM_H
515 #define LACKS_SYS_MMAN_H
516 #define LACKS_STRING_H
517 #define LACKS_STRINGS_H
518 #define LACKS_SYS_TYPES_H
519 #define LACKS_ERRNO_H
520 #ifndef MALLOC_FAILURE_ACTION
521 #define MALLOC_FAILURE_ACTION
522 #endif /* MALLOC_FAILURE_ACTION */
523 #ifdef _WIN32_WCE /* WINCE reportedly does not clear */
524 #define MMAP_CLEARS 0
525 #else
526 #define MMAP_CLEARS 1
527 #endif /* _WIN32_WCE */
528 #endif  /* WIN32 */
529
530 #if defined(DARWIN) || defined(_DARWIN)
531 /* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
532 #ifndef HAVE_MORECORE
533 #define HAVE_MORECORE 0
534 #define HAVE_MMAP 1
535 /* OSX allocators provide 16 byte alignment */
536 #ifndef MALLOC_ALIGNMENT
537 #define MALLOC_ALIGNMENT ((size_t)16U)
538 #endif
539 #endif  /* HAVE_MORECORE */
540 #endif  /* DARWIN */
541
542 #ifndef LACKS_SYS_TYPES_H
543 #include <sys/types.h>  /* For size_t */
544 #endif  /* LACKS_SYS_TYPES_H */
545
546 #if (defined(__GNUC__) && ((defined(__i386__) || defined(__x86_64__)))) || (defined(_MSC_VER) && _MSC_VER>=1310)
547 #define SPIN_LOCKS_AVAILABLE 1
548 #else
549 #define SPIN_LOCKS_AVAILABLE 0
550 #endif
551
552 /* The maximum possible size_t value has all bits set */
553 #define MAX_SIZE_T           (~(size_t)0)
554
555 #ifndef ONLY_MSPACES
556 #define ONLY_MSPACES 0     /* define to a value */
557 #else
558 #define ONLY_MSPACES 1
559 #endif  /* ONLY_MSPACES */
560 #ifndef MSPACES
561 #if ONLY_MSPACES
562 #define MSPACES 1
563 #else   /* ONLY_MSPACES */
564 #define MSPACES 0
565 #endif  /* ONLY_MSPACES */
566 #endif  /* MSPACES */
567 #ifndef MALLOC_ALIGNMENT
568 #define MALLOC_ALIGNMENT ((size_t)8U)
569 #endif  /* MALLOC_ALIGNMENT */
570 #ifndef FOOTERS
571 #define FOOTERS 0
572 #endif  /* FOOTERS */
573 #ifndef ABORT
574 #define ABORT  abort()
575 #endif  /* ABORT */
576 #ifndef ABORT_ON_ASSERT_FAILURE
577 #define ABORT_ON_ASSERT_FAILURE 1
578 #endif  /* ABORT_ON_ASSERT_FAILURE */
579 #ifndef PROCEED_ON_ERROR
580 #define PROCEED_ON_ERROR 0
581 #endif  /* PROCEED_ON_ERROR */
582 #ifndef USE_LOCKS
583 #define USE_LOCKS 0
584 #endif  /* USE_LOCKS */
585 #ifndef USE_SPIN_LOCKS
586 #if USE_LOCKS && SPIN_LOCKS_AVAILABLE
587 #define USE_SPIN_LOCKS 1
588 #else
589 #define USE_SPIN_LOCKS 0
590 #endif /* USE_LOCKS && SPIN_LOCKS_AVAILABLE. */
591 #endif /* USE_SPIN_LOCKS */
592 #ifndef INSECURE
593 #define INSECURE 0
594 #endif  /* INSECURE */
595 #ifndef HAVE_MMAP
596 #define HAVE_MMAP 1
597 #endif  /* HAVE_MMAP */
598 #ifndef MMAP_CLEARS
599 #define MMAP_CLEARS 1
600 #endif  /* MMAP_CLEARS */
601 #ifndef HAVE_MREMAP
602 #ifdef linux
603 #define HAVE_MREMAP 1
604 #else   /* linux */
605 #define HAVE_MREMAP 0
606 #endif  /* linux */
607 #endif  /* HAVE_MREMAP */
608 #ifndef MALLOC_FAILURE_ACTION
609 #define MALLOC_FAILURE_ACTION  errno = ENOMEM;
610 #endif  /* MALLOC_FAILURE_ACTION */
611 #ifndef HAVE_MORECORE
612 #if ONLY_MSPACES
613 #define HAVE_MORECORE 0
614 #else   /* ONLY_MSPACES */
615 #define HAVE_MORECORE 1
616 #endif  /* ONLY_MSPACES */
617 #endif  /* HAVE_MORECORE */
618 #if !HAVE_MORECORE
619 #define MORECORE_CONTIGUOUS 0
620 #else   /* !HAVE_MORECORE */
621 #define MORECORE_DEFAULT sbrk
622 #ifndef MORECORE_CONTIGUOUS
623 #define MORECORE_CONTIGUOUS 1
624 #endif  /* MORECORE_CONTIGUOUS */
625 #endif  /* HAVE_MORECORE */
626 #ifndef DEFAULT_GRANULARITY
627 #if (MORECORE_CONTIGUOUS || defined(WIN32))
628 #define DEFAULT_GRANULARITY (0)  /* 0 means to compute in init_mparams */
629 #else   /* MORECORE_CONTIGUOUS */
630 #define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
631 #endif  /* MORECORE_CONTIGUOUS */
632 #endif  /* DEFAULT_GRANULARITY */
633 #ifndef DEFAULT_TRIM_THRESHOLD
634 #ifndef MORECORE_CANNOT_TRIM
635 #define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
636 #else   /* MORECORE_CANNOT_TRIM */
637 #define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
638 #endif  /* MORECORE_CANNOT_TRIM */
639 #endif  /* DEFAULT_TRIM_THRESHOLD */
640 #ifndef DEFAULT_MMAP_THRESHOLD
641 #if HAVE_MMAP
642 #define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
643 #else   /* HAVE_MMAP */
644 #define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
645 #endif  /* HAVE_MMAP */
646 #endif  /* DEFAULT_MMAP_THRESHOLD */
647 #ifndef MAX_RELEASE_CHECK_RATE
648 #if HAVE_MMAP
649 #define MAX_RELEASE_CHECK_RATE 4095
650 #else
651 #define MAX_RELEASE_CHECK_RATE MAX_SIZE_T
652 #endif /* HAVE_MMAP */
653 #endif /* MAX_RELEASE_CHECK_RATE */
654 #ifndef USE_BUILTIN_FFS
655 #define USE_BUILTIN_FFS 0
656 #endif  /* USE_BUILTIN_FFS */
657 #ifndef USE_DEV_RANDOM
658 #define USE_DEV_RANDOM 0
659 #endif  /* USE_DEV_RANDOM */
660 #ifndef NO_MALLINFO
661 #define NO_MALLINFO 0
662 #endif  /* NO_MALLINFO */
663 #ifndef MALLINFO_FIELD_TYPE
664 #define MALLINFO_FIELD_TYPE size_t
665 #endif  /* MALLINFO_FIELD_TYPE */
666 #ifndef NO_SEGMENT_TRAVERSAL
667 #define NO_SEGMENT_TRAVERSAL 0
668 #endif /* NO_SEGMENT_TRAVERSAL */
669
670 /*
671   mallopt tuning options.  SVID/XPG defines four standard parameter
672   numbers for mallopt, normally defined in malloc.h.  None of these
673   are used in this malloc, so setting them has no effect. But this
674   malloc does support the following options.
675 */
676
677 #define M_TRIM_THRESHOLD     (-1)
678 #define M_GRANULARITY        (-2)
679 #define M_MMAP_THRESHOLD     (-3)
680
681 /* ------------------------ Mallinfo declarations ------------------------ */
682
683 #if !NO_MALLINFO
684 /*
685   This version of malloc supports the standard SVID/XPG mallinfo
686   routine that returns a struct containing usage properties and
687   statistics. It should work on any system that has a
688   /usr/include/malloc.h defining struct mallinfo.  The main
689   declaration needed is the mallinfo struct that is returned (by-copy)
690   by mallinfo().  The malloinfo struct contains a bunch of fields that
691   are not even meaningful in this version of malloc.  These fields are
692   are instead filled by mallinfo() with other numbers that might be of
693   interest.
694
695   HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
696   /usr/include/malloc.h file that includes a declaration of struct
697   mallinfo.  If so, it is included; else a compliant version is
698   declared below.  These must be precisely the same for mallinfo() to
699   work.  The original SVID version of this struct, defined on most
700   systems with mallinfo, declares all fields as ints. But some others
701   define as unsigned long. If your system defines the fields using a
702   type of different width than listed here, you MUST #include your
703   system version and #define HAVE_USR_INCLUDE_MALLOC_H.
704 */
705
706 /* #define HAVE_USR_INCLUDE_MALLOC_H */
707
708 #ifdef HAVE_USR_INCLUDE_MALLOC_H
709 #include "/usr/include/malloc.h"
710 #else /* HAVE_USR_INCLUDE_MALLOC_H */
711 #ifndef STRUCT_MALLINFO_DECLARED
712 #define STRUCT_MALLINFO_DECLARED 1
713 struct mallinfo {
714   MALLINFO_FIELD_TYPE arena;    /* non-mmapped space allocated from system */
715   MALLINFO_FIELD_TYPE ordblks;  /* number of free chunks */
716   MALLINFO_FIELD_TYPE smblks;   /* always 0 */
717   MALLINFO_FIELD_TYPE hblks;    /* always 0 */
718   MALLINFO_FIELD_TYPE hblkhd;   /* space in mmapped regions */
719   MALLINFO_FIELD_TYPE usmblks;  /* maximum total allocated space */
720   MALLINFO_FIELD_TYPE fsmblks;  /* always 0 */
721   MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
722   MALLINFO_FIELD_TYPE fordblks; /* total free space */
723   MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
724 };
725 #endif /* STRUCT_MALLINFO_DECLARED */
726 #endif /* HAVE_USR_INCLUDE_MALLOC_H */
727 #endif /* NO_MALLINFO */
728
729 /*
730   Try to persuade compilers to inline. The most critical functions for
731   inlining are defined as macros, so these aren't used for them.
732 */
733
734 #ifndef FORCEINLINE
735   #if defined(__GNUC__)
736 #define FORCEINLINE __inline __attribute__ ((always_inline))
737   #elif defined(_MSC_VER)
738     #define FORCEINLINE __forceinline
739   #endif
740 #endif
741 #ifndef NOINLINE
742   #if defined(__GNUC__)
743     #define NOINLINE __attribute__ ((noinline))
744   #elif defined(_MSC_VER)
745     #define NOINLINE __declspec(noinline)
746   #else
747     #define NOINLINE
748   #endif
749 #endif
750
751 #ifdef __cplusplus
752 extern "C" {
753 #ifndef FORCEINLINE
754  #define FORCEINLINE inline
755 #endif
756 #endif /* __cplusplus */
757 #ifndef FORCEINLINE
758  #define FORCEINLINE
759 #endif
760
761 #if !ONLY_MSPACES
762
763 /* ------------------- Declarations of public routines ------------------- */
764
765 #ifndef USE_DL_PREFIX
766 #define dlcalloc               calloc
767 #define dlfree                 free
768 #define dlmalloc               malloc
769 #define dlmemalign             memalign
770 #define dlrealloc              realloc
771 #define dlvalloc               valloc
772 #define dlpvalloc              pvalloc
773 #define dlmallinfo             mallinfo
774 #define dlmallopt              mallopt
775 #define dlmalloc_trim          malloc_trim
776 #define dlmalloc_stats         malloc_stats
777 #define dlmalloc_usable_size   malloc_usable_size
778 #define dlmalloc_footprint     malloc_footprint
779 #define dlmalloc_max_footprint malloc_max_footprint
780 #define dlindependent_calloc   independent_calloc
781 #define dlindependent_comalloc independent_comalloc
782 #endif /* USE_DL_PREFIX */
783
784
785 /*
786   malloc(size_t n)
787   Returns a pointer to a newly allocated chunk of at least n bytes, or
788   null if no space is available, in which case errno is set to ENOMEM
789   on ANSI C systems.
790
791   If n is zero, malloc returns a minimum-sized chunk. (The minimum
792   size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
793   systems.)  Note that size_t is an unsigned type, so calls with
794   arguments that would be negative if signed are interpreted as
795   requests for huge amounts of space, which will often fail. The
796   maximum supported value of n differs across systems, but is in all
797   cases less than the maximum representable value of a size_t.
798 */
799 void* dlmalloc(size_t);
800
801 /*
802   free(void* p)
803   Releases the chunk of memory pointed to by p, that had been previously
804   allocated using malloc or a related routine such as realloc.
805   It has no effect if p is null. If p was not malloced or already
806   freed, free(p) will by default cause the current program to abort.
807 */
808 void  dlfree(void*);
809
810 /*
811   calloc(size_t n_elements, size_t element_size);
812   Returns a pointer to n_elements * element_size bytes, with all locations
813   set to zero.
814 */
815 void* dlcalloc(size_t, size_t);
816
817 /*
818   realloc(void* p, size_t n)
819   Returns a pointer to a chunk of size n that contains the same data
820   as does chunk p up to the minimum of (n, p's size) bytes, or null
821   if no space is available.
822
823   The returned pointer may or may not be the same as p. The algorithm
824   prefers extending p in most cases when possible, otherwise it
825   employs the equivalent of a malloc-copy-free sequence.
826
827   If p is null, realloc is equivalent to malloc.
828
829   If space is not available, realloc returns null, errno is set (if on
830   ANSI) and p is NOT freed.
831
832   if n is for fewer bytes than already held by p, the newly unused
833   space is lopped off and freed if possible.  realloc with a size
834   argument of zero (re)allocates a minimum-sized chunk.
835
836   The old unix realloc convention of allowing the last-free'd chunk
837   to be used as an argument to realloc is not supported.
838 */
839
840 void* dlrealloc(void*, size_t);
841
842 /*
843   memalign(size_t alignment, size_t n);
844   Returns a pointer to a newly allocated chunk of n bytes, aligned
845   in accord with the alignment argument.
846
847   The alignment argument should be a power of two. If the argument is
848   not a power of two, the nearest greater power is used.
849   8-byte alignment is guaranteed by normal malloc calls, so don't
850   bother calling memalign with an argument of 8 or less.
851
852   Overreliance on memalign is a sure way to fragment space.
853 */
854 void* dlmemalign(size_t, size_t);
855
856 /*
857   valloc(size_t n);
858   Equivalent to memalign(pagesize, n), where pagesize is the page
859   size of the system. If the pagesize is unknown, 4096 is used.
860 */
861 void* dlvalloc(size_t);
862
863 /*
864   mallopt(int parameter_number, int parameter_value)
865   Sets tunable parameters The format is to provide a
866   (parameter-number, parameter-value) pair.  mallopt then sets the
867   corresponding parameter to the argument value if it can (i.e., so
868   long as the value is meaningful), and returns 1 if successful else
869   0.  To workaround the fact that mallopt is specified to use int,
870   not size_t parameters, the value -1 is specially treated as the
871   maximum unsigned size_t value.
872
873   SVID/XPG/ANSI defines four standard param numbers for mallopt,
874   normally defined in malloc.h.  None of these are use in this malloc,
875   so setting them has no effect. But this malloc also supports other
876   options in mallopt. See below for details.  Briefly, supported
877   parameters are as follows (listed defaults are for "typical"
878   configurations).
879
880   Symbol            param #  default    allowed param values
881   M_TRIM_THRESHOLD     -1   2*1024*1024   any   (-1 disables)
882   M_GRANULARITY        -2     page size   any power of 2 >= page size
883   M_MMAP_THRESHOLD     -3      256*1024   any   (or 0 if no MMAP support)
884 */
885 int dlmallopt(int, int);
886
887 /*
888   malloc_footprint();
889   Returns the number of bytes obtained from the system.  The total
890   number of bytes allocated by malloc, realloc etc., is less than this
891   value. Unlike mallinfo, this function returns only a precomputed
892   result, so can be called frequently to monitor memory consumption.
893   Even if locks are otherwise defined, this function does not use them,
894   so results might not be up to date.
895 */
896 size_t dlmalloc_footprint(void);
897
898 /*
899   malloc_max_footprint();
900   Returns the maximum number of bytes obtained from the system. This
901   value will be greater than current footprint if deallocated space
902   has been reclaimed by the system. The peak number of bytes allocated
903   by malloc, realloc etc., is less than this value. Unlike mallinfo,
904   this function returns only a precomputed result, so can be called
905   frequently to monitor memory consumption.  Even if locks are
906   otherwise defined, this function does not use them, so results might
907   not be up to date.
908 */
909 size_t dlmalloc_max_footprint(void);
910
911 #if !NO_MALLINFO
912 /*
913   mallinfo()
914   Returns (by copy) a struct containing various summary statistics:
915
916   arena:     current total non-mmapped bytes allocated from system
917   ordblks:   the number of free chunks
918   smblks:    always zero.
919   hblks:     current number of mmapped regions
920   hblkhd:    total bytes held in mmapped regions
921   usmblks:   the maximum total allocated space. This will be greater
922                 than current total if trimming has occurred.
923   fsmblks:   always zero
924   uordblks:  current total allocated space (normal or mmapped)
925   fordblks:  total free space
926   keepcost:  the maximum number of bytes that could ideally be released
927                back to system via malloc_trim. ("ideally" means that
928                it ignores page restrictions etc.)
929
930   Because these fields are ints, but internal bookkeeping may
931   be kept as longs, the reported values may wrap around zero and
932   thus be inaccurate.
933 */
934 struct mallinfo dlmallinfo(void);
935 #endif /* NO_MALLINFO */
936
937 /*
938   independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
939
940   independent_calloc is similar to calloc, but instead of returning a
941   single cleared space, it returns an array of pointers to n_elements
942   independent elements that can hold contents of size elem_size, each
943   of which starts out cleared, and can be independently freed,
944   realloc'ed etc. The elements are guaranteed to be adjacently
945   allocated (this is not guaranteed to occur with multiple callocs or
946   mallocs), which may also improve cache locality in some
947   applications.
948
949   The "chunks" argument is optional (i.e., may be null, which is
950   probably the most typical usage). If it is null, the returned array
951   is itself dynamically allocated and should also be freed when it is
952   no longer needed. Otherwise, the chunks array must be of at least
953   n_elements in length. It is filled in with the pointers to the
954   chunks.
955
956   In either case, independent_calloc returns this pointer array, or
957   null if the allocation failed.  If n_elements is zero and "chunks"
958   is null, it returns a chunk representing an array with zero elements
959   (which should be freed if not wanted).
960
961   Each element must be individually freed when it is no longer
962   needed. If you'd like to instead be able to free all at once, you
963   should instead use regular calloc and assign pointers into this
964   space to represent elements.  (In this case though, you cannot
965   independently free elements.)
966
967   independent_calloc simplifies and speeds up implementations of many
968   kinds of pools.  It may also be useful when constructing large data
969   structures that initially have a fixed number of fixed-sized nodes,
970   but the number is not known at compile time, and some of the nodes
971   may later need to be freed. For example:
972
973   struct Node { int item; struct Node* next; };
974
975   struct Node* build_list() {
976     struct Node** pool;
977     int n = read_number_of_nodes_needed();
978     if (n <= 0) return 0;
979     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
980     if (pool == 0) die();
981     // organize into a linked list...
982     struct Node* first = pool[0];
983     for (i = 0; i < n-1; ++i)
984       pool[i]->next = pool[i+1];
985     free(pool);     // Can now free the array (or not, if it is needed later)
986     return first;
987   }
988 */
989 void** dlindependent_calloc(size_t, size_t, void**);
990
991 /*
992   independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
993
994   independent_comalloc allocates, all at once, a set of n_elements
995   chunks with sizes indicated in the "sizes" array.    It returns
996   an array of pointers to these elements, each of which can be
997   independently freed, realloc'ed etc. The elements are guaranteed to
998   be adjacently allocated (this is not guaranteed to occur with
999   multiple callocs or mallocs), which may also improve cache locality
1000   in some applications.
1001
1002   The "chunks" argument is optional (i.e., may be null). If it is null
1003   the returned array is itself dynamically allocated and should also
1004   be freed when it is no longer needed. Otherwise, the chunks array
1005   must be of at least n_elements in length. It is filled in with the
1006   pointers to the chunks.
1007
1008   In either case, independent_comalloc returns this pointer array, or
1009   null if the allocation failed.  If n_elements is zero and chunks is
1010   null, it returns a chunk representing an array with zero elements
1011   (which should be freed if not wanted).
1012
1013   Each element must be individually freed when it is no longer
1014   needed. If you'd like to instead be able to free all at once, you
1015   should instead use a single regular malloc, and assign pointers at
1016   particular offsets in the aggregate space. (In this case though, you
1017   cannot independently free elements.)
1018
1019   independent_comallac differs from independent_calloc in that each
1020   element may have a different size, and also that it does not
1021   automatically clear elements.
1022
1023   independent_comalloc can be used to speed up allocation in cases
1024   where several structs or objects must always be allocated at the
1025   same time.  For example:
1026
1027   struct Head { ... }
1028   struct Foot { ... }
1029
1030   void send_message(char* msg) {
1031     int msglen = strlen(msg);
1032     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1033     void* chunks[3];
1034     if (independent_comalloc(3, sizes, chunks) == 0)
1035       die();
1036     struct Head* head = (struct Head*)(chunks[0]);
1037     char*        body = (char*)(chunks[1]);
1038     struct Foot* foot = (struct Foot*)(chunks[2]);
1039     // ...
1040   }
1041
1042   In general though, independent_comalloc is worth using only for
1043   larger values of n_elements. For small values, you probably won't
1044   detect enough difference from series of malloc calls to bother.
1045
1046   Overuse of independent_comalloc can increase overall memory usage,
1047   since it cannot reuse existing noncontiguous small chunks that
1048   might be available for some of the elements.
1049 */
1050 void** dlindependent_comalloc(size_t, size_t*, void**);
1051
1052
1053 /*
1054   pvalloc(size_t n);
1055   Equivalent to valloc(minimum-page-that-holds(n)), that is,
1056   round up n to nearest pagesize.
1057  */
1058 void*  dlpvalloc(size_t);
1059
1060 /*
1061   malloc_trim(size_t pad);
1062
1063   If possible, gives memory back to the system (via negative arguments
1064   to sbrk) if there is unused memory at the `high' end of the malloc
1065   pool or in unused MMAP segments. You can call this after freeing
1066   large blocks of memory to potentially reduce the system-level memory
1067   requirements of a program. However, it cannot guarantee to reduce
1068   memory. Under some allocation patterns, some large free blocks of
1069   memory will be locked between two used chunks, so they cannot be
1070   given back to the system.
1071
1072   The `pad' argument to malloc_trim represents the amount of free
1073   trailing space to leave untrimmed. If this argument is zero, only
1074   the minimum amount of memory to maintain internal data structures
1075   will be left. Non-zero arguments can be supplied to maintain enough
1076   trailing space to service future expected allocations without having
1077   to re-obtain memory from the system.
1078
1079   Malloc_trim returns 1 if it actually released any memory, else 0.
1080 */
1081 int  dlmalloc_trim(size_t);
1082
1083 /*
1084   malloc_stats();
1085   Prints on stderr the amount of space obtained from the system (both
1086   via sbrk and mmap), the maximum amount (which may be more than
1087   current if malloc_trim and/or munmap got called), and the current
1088   number of bytes allocated via malloc (or realloc, etc) but not yet
1089   freed. Note that this is the number of bytes allocated, not the
1090   number requested. It will be larger than the number requested
1091   because of alignment and bookkeeping overhead. Because it includes
1092   alignment wastage as being in use, this figure may be greater than
1093   zero even when no user-level chunks are allocated.
1094
1095   The reported current and maximum system memory can be inaccurate if
1096   a program makes other calls to system memory allocation functions
1097   (normally sbrk) outside of malloc.
1098
1099   malloc_stats prints only the most commonly interesting statistics.
1100   More information can be obtained by calling mallinfo.
1101 */
1102 void  dlmalloc_stats(void);
1103
1104 #endif /* ONLY_MSPACES */
1105
1106 /*
1107   malloc_usable_size(void* p);
1108
1109   Returns the number of bytes you can actually use in
1110   an allocated chunk, which may be more than you requested (although
1111   often not) due to alignment and minimum size constraints.
1112   You can use this many bytes without worrying about
1113   overwriting other allocated objects. This is not a particularly great
1114   programming practice. malloc_usable_size can be more useful in
1115   debugging and assertions, for example:
1116
1117   p = malloc(n);
1118   assert(malloc_usable_size(p) >= 256);
1119 */
1120 size_t dlmalloc_usable_size(void*);
1121
1122
1123 #if MSPACES
1124
1125 /*
1126   mspace is an opaque type representing an independent
1127   region of space that supports mspace_malloc, etc.
1128 */
1129 typedef void* mspace;
1130
1131 /*
1132   create_mspace creates and returns a new independent space with the
1133   given initial capacity, or, if 0, the default granularity size.  It
1134   returns null if there is no system memory available to create the
1135   space.  If argument locked is non-zero, the space uses a separate
1136   lock to control access. The capacity of the space will grow
1137   dynamically as needed to service mspace_malloc requests.  You can
1138   control the sizes of incremental increases of this space by
1139   compiling with a different DEFAULT_GRANULARITY or dynamically
1140   setting with mallopt(M_GRANULARITY, value).
1141 */
1142 mspace create_mspace(size_t capacity, int locked);
1143
1144 /*
1145   destroy_mspace destroys the given space, and attempts to return all
1146   of its memory back to the system, returning the total number of
1147   bytes freed. After destruction, the results of access to all memory
1148   used by the space become undefined.
1149 */
1150 size_t destroy_mspace(mspace msp);
1151
1152 /*
1153   create_mspace_with_base uses the memory supplied as the initial base
1154   of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
1155   space is used for bookkeeping, so the capacity must be at least this
1156   large. (Otherwise 0 is returned.) When this initial space is
1157   exhausted, additional memory will be obtained from the system.
1158   Destroying this space will deallocate all additionally allocated
1159   space (if possible) but not the initial base.
1160 */
1161 mspace create_mspace_with_base(void* base, size_t capacity, int locked);
1162
1163 /*
1164   mspace_track_large_chunks controls whether requests for large chunks
1165   are allocated in their own untracked mmapped regions, separate from
1166   others in this mspace. By default large chunks are not tracked,
1167   which reduces fragmentation. However, such chunks are not
1168   necessarily released to the system upon destroy_mspace.  Enabling
1169   tracking by setting to true may increase fragmentation, but avoids
1170   leakage when relying on destroy_mspace to release all memory
1171   allocated using this space.  The function returns the previous
1172   setting.
1173 */
1174 int mspace_track_large_chunks(mspace msp, int enable);
1175
1176
1177 /*
1178   mspace_malloc behaves as malloc, but operates within
1179   the given space.
1180 */
1181 void* mspace_malloc(mspace msp, size_t bytes);
1182
1183 /*
1184   mspace_free behaves as free, but operates within
1185   the given space.
1186
1187   If compiled with FOOTERS==1, mspace_free is not actually needed.
1188   free may be called instead of mspace_free because freed chunks from
1189   any space are handled by their originating spaces.
1190 */
1191 void mspace_free(mspace msp, void* mem);
1192
1193 /*
1194   mspace_realloc behaves as realloc, but operates within
1195   the given space.
1196
1197   If compiled with FOOTERS==1, mspace_realloc is not actually
1198   needed.  realloc may be called instead of mspace_realloc because
1199   realloced chunks from any space are handled by their originating
1200   spaces.
1201 */
1202 void* mspace_realloc(mspace msp, void* mem, size_t newsize);
1203
1204 /*
1205   mspace_calloc behaves as calloc, but operates within
1206   the given space.
1207 */
1208 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
1209
1210 /*
1211   mspace_memalign behaves as memalign, but operates within
1212   the given space.
1213 */
1214 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);
1215
1216 /*
1217   mspace_independent_calloc behaves as independent_calloc, but
1218   operates within the given space.
1219 */
1220 void** mspace_independent_calloc(mspace msp, size_t n_elements,
1221                                  size_t elem_size, void* chunks[]);
1222
1223 /*
1224   mspace_independent_comalloc behaves as independent_comalloc, but
1225   operates within the given space.
1226 */
1227 void** mspace_independent_comalloc(mspace msp, size_t n_elements,
1228                                    size_t sizes[], void* chunks[]);
1229
1230 /*
1231   mspace_footprint() returns the number of bytes obtained from the
1232   system for this space.
1233 */
1234 size_t mspace_footprint(mspace msp);
1235
1236 /*
1237   mspace_max_footprint() returns the peak number of bytes obtained from the
1238   system for this space.
1239 */
1240 size_t mspace_max_footprint(mspace msp);
1241
1242
1243 #if !NO_MALLINFO
1244 /*
1245   mspace_mallinfo behaves as mallinfo, but reports properties of
1246   the given space.
1247 */
1248 struct mallinfo mspace_mallinfo(mspace msp);
1249 #endif /* NO_MALLINFO */
1250
1251 /*
1252   malloc_usable_size(void* p) behaves the same as malloc_usable_size;
1253 */
1254   size_t mspace_usable_size(void* mem);
1255
1256 /*
1257   mspace_malloc_stats behaves as malloc_stats, but reports
1258   properties of the given space.
1259 */
1260 void mspace_malloc_stats(mspace msp);
1261
1262 /*
1263   mspace_trim behaves as malloc_trim, but
1264   operates within the given space.
1265 */
1266 int mspace_trim(mspace msp, size_t pad);
1267
1268 /*
1269   An alias for mallopt.
1270 */
1271 int mspace_mallopt(int, int);
1272
1273 #endif /* MSPACES */
1274
1275 #ifdef __cplusplus
1276 };  /* end of extern "C" */
1277 #endif /* __cplusplus */
1278
1279 /*
1280   ========================================================================
1281   To make a fully customizable malloc.h header file, cut everything
1282   above this line, put into file malloc.h, edit to suit, and #include it
1283   on the next line, as well as in programs that use this malloc.
1284   ========================================================================
1285 */
1286
1287 /* #include "malloc.h" */
1288
1289 /*------------------------------ internal #includes ---------------------- */
1290
1291 #ifdef WIN32
1292 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
1293 #endif /* WIN32 */
1294
1295 #include <stdio.h>       /* for printing in malloc_stats */
1296
1297 #ifndef LACKS_ERRNO_H
1298 #include <errno.h>       /* for MALLOC_FAILURE_ACTION */
1299 #endif /* LACKS_ERRNO_H */
1300 #if FOOTERS || DEBUG
1301 #include <time.h>        /* for magic initialization */
1302 #endif /* FOOTERS */
1303 #ifndef LACKS_STDLIB_H
1304 #include <stdlib.h>      /* for abort() */
1305 #endif /* LACKS_STDLIB_H */
1306 #ifdef DEBUG
1307 #if ABORT_ON_ASSERT_FAILURE
1308 #undef assert
1309 #define assert(x) if(!(x)) ABORT
1310 #else /* ABORT_ON_ASSERT_FAILURE */
1311 #include <assert.h>
1312 #endif /* ABORT_ON_ASSERT_FAILURE */
1313 #else  /* DEBUG */
1314 #ifndef assert
1315 #define assert(x)
1316 #endif
1317 #define DEBUG 0
1318 #endif /* DEBUG */
1319 #ifndef LACKS_STRING_H
1320 #include <string.h>      /* for memset etc */
1321 #endif  /* LACKS_STRING_H */
1322 #if USE_BUILTIN_FFS
1323 #ifndef LACKS_STRINGS_H
1324 #include <strings.h>     /* for ffs */
1325 #endif /* LACKS_STRINGS_H */
1326 #endif /* USE_BUILTIN_FFS */
1327 #if HAVE_MMAP
1328 #ifndef LACKS_SYS_MMAN_H
1329 /* On some versions of linux, mremap decl in mman.h needs __USE_GNU set */
1330 #if (defined(linux) && !defined(__USE_GNU))
1331 #define __USE_GNU 1
1332 #include <sys/mman.h>    /* for mmap */
1333 #undef __USE_GNU
1334 #else
1335 #include <sys/mman.h>    /* for mmap */
1336 #endif /* linux */
1337 #endif /* LACKS_SYS_MMAN_H */
1338 #ifndef LACKS_FCNTL_H
1339 #include <fcntl.h>
1340 #endif /* LACKS_FCNTL_H */
1341 #endif /* HAVE_MMAP */
1342 #ifndef LACKS_UNISTD_H
1343 #include <unistd.h>     /* for sbrk, sysconf */
1344 #else /* LACKS_UNISTD_H */
1345 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
1346 extern void*     sbrk(ptrdiff_t);
1347 #endif /* FreeBSD etc */
1348 #endif /* LACKS_UNISTD_H */
1349
1350 /* Declarations for locking */
1351 #if USE_LOCKS
1352 #ifndef WIN32
1353 #include <pthread.h>
1354 #if defined (__SVR4) && defined (__sun)  /* solaris */
1355 #include <thread.h>
1356 #endif /* solaris */
1357 #else
1358 #ifndef _M_AMD64
1359 /* These are already defined on AMD64 builds */
1360 #ifdef __cplusplus
1361 extern "C" {
1362 #endif /* __cplusplus */
1363 LONG __cdecl _InterlockedCompareExchange(LONG volatile *Dest, LONG Exchange, LONG Comp);
1364 LONG __cdecl _InterlockedExchange(LONG volatile *Target, LONG Value);
1365 #ifdef __cplusplus
1366 }
1367 #endif /* __cplusplus */
1368 #endif /* _M_AMD64 */
1369 #pragma intrinsic (_InterlockedCompareExchange)
1370 #pragma intrinsic (_InterlockedExchange)
1371 #define interlockedcompareexchange _InterlockedCompareExchange
1372 #define interlockedexchange _InterlockedExchange
1373 #endif /* Win32 */
1374 #endif /* USE_LOCKS */
1375
1376 /* Declarations for bit scanning on win32 */
1377 #if defined(_MSC_VER) && _MSC_VER>=1300
1378 #ifndef BitScanForward  /* Try to avoid pulling in WinNT.h */
1379 #ifdef __cplusplus
1380 extern "C" {
1381 #endif /* __cplusplus */
1382 unsigned char _BitScanForward(unsigned long *index, unsigned long mask);
1383 unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
1384 #ifdef __cplusplus
1385 }
1386 #endif /* __cplusplus */
1387
1388 #define BitScanForward _BitScanForward
1389 #define BitScanReverse _BitScanReverse
1390 #pragma intrinsic(_BitScanForward)
1391 #pragma intrinsic(_BitScanReverse)
1392 #endif /* BitScanForward */
1393 #endif /* defined(_MSC_VER) && _MSC_VER>=1300 */
1394
1395 #ifndef WIN32
1396 #ifndef malloc_getpagesize
1397 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
1398 #    ifndef _SC_PAGE_SIZE
1399 #      define _SC_PAGE_SIZE _SC_PAGESIZE
1400 #    endif
1401 #  endif
1402 #  ifdef _SC_PAGE_SIZE
1403 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
1404 #  else
1405 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
1406        extern size_t getpagesize();
1407 #      define malloc_getpagesize getpagesize()
1408 #    else
1409 #      ifdef WIN32 /* use supplied emulation of getpagesize */
1410 #        define malloc_getpagesize getpagesize()
1411 #      else
1412 #        ifndef LACKS_SYS_PARAM_H
1413 #          include <sys/param.h>
1414 #        endif
1415 #        ifdef EXEC_PAGESIZE
1416 #          define malloc_getpagesize EXEC_PAGESIZE
1417 #        else
1418 #          ifdef NBPG
1419 #            ifndef CLSIZE
1420 #              define malloc_getpagesize NBPG
1421 #            else
1422 #              define malloc_getpagesize (NBPG * CLSIZE)
1423 #            endif
1424 #          else
1425 #            ifdef NBPC
1426 #              define malloc_getpagesize NBPC
1427 #            else
1428 #              ifdef PAGESIZE
1429 #                define malloc_getpagesize PAGESIZE
1430 #              else /* just guess */
1431 #                define malloc_getpagesize ((size_t)4096U)
1432 #              endif
1433 #            endif
1434 #          endif
1435 #        endif
1436 #      endif
1437 #    endif
1438 #  endif
1439 #endif
1440 #endif
1441
1442
1443
1444 /* ------------------- size_t and alignment properties -------------------- */
1445
1446 /* The byte and bit size of a size_t */
1447 #define SIZE_T_SIZE         (sizeof(size_t))
1448 #define SIZE_T_BITSIZE      (sizeof(size_t) << 3)
1449
1450 /* Some constants coerced to size_t */
1451 /* Annoying but necessary to avoid errors on some platforms */
1452 #define SIZE_T_ZERO         ((size_t)0)
1453 #define SIZE_T_ONE          ((size_t)1)
1454 #define SIZE_T_TWO          ((size_t)2)
1455 #define SIZE_T_FOUR         ((size_t)4)
1456 #define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)
1457 #define FOUR_SIZE_T_SIZES   (SIZE_T_SIZE<<2)
1458 #define SIX_SIZE_T_SIZES    (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
1459 #define HALF_MAX_SIZE_T     (MAX_SIZE_T / 2U)
1460
1461 /* The bit mask value corresponding to MALLOC_ALIGNMENT */
1462 #define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)
1463
1464 /* True if address a has acceptable alignment */
1465 #define is_aligned(A)       (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
1466
1467 /* the number of bytes to offset an address to align it */
1468 #define align_offset(A)\
1469  ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
1470   ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
1471
1472 /* -------------------------- MMAP preliminaries ------------------------- */
1473
1474 /*
1475    If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
1476    checks to fail so compiler optimizer can delete code rather than
1477    using so many "#if"s.
1478 */
1479
1480
1481 /* MORECORE and MMAP must return MFAIL on failure */
1482 #define MFAIL                ((void*)(MAX_SIZE_T))
1483 #define CMFAIL               ((char*)(MFAIL)) /* defined for convenience */
1484
1485 #if HAVE_MMAP
1486
1487 #ifndef WIN32
1488 #define MUNMAP_DEFAULT(a, s)  munmap((a), (s))
1489 #define MMAP_PROT            (PROT_READ|PROT_WRITE)
1490 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1491 #define MAP_ANONYMOUS        MAP_ANON
1492 #endif /* MAP_ANON */
1493 #ifdef MAP_ANONYMOUS
1494 #define MMAP_FLAGS           (MAP_PRIVATE|MAP_ANONYMOUS)
1495 #define MMAP_DEFAULT(s)       mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
1496 #else /* MAP_ANONYMOUS */
1497 /*
1498    Nearly all versions of mmap support MAP_ANONYMOUS, so the following
1499    is unlikely to be needed, but is supplied just in case.
1500 */
1501 #define MMAP_FLAGS           (MAP_PRIVATE)
1502 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1503 #define MMAP_DEFAULT(s) ((dev_zero_fd < 0) ? \
1504            (dev_zero_fd = open("/dev/zero", O_RDWR), \
1505             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
1506             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
1507 #endif /* MAP_ANONYMOUS */
1508
1509 #define DIRECT_MMAP_DEFAULT(s) MMAP_DEFAULT(s)
1510
1511 #else /* WIN32 */
1512
1513 /* Win32 MMAP via VirtualAlloc */
1514 static FORCEINLINE void* win32mmap(size_t size) {
1515 #if 0
1516   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
1517   return (ptr != 0)? ptr: MFAIL;
1518 #else
1519   void* ptr = VirtualAlloc(0, size, MEM_RESERVE, PAGE_NOACCESS);
1520   if (ptr == 0)
1521     return MFAIL;
1522   VirtualAlloc(ptr, size, MEM_COMMIT, PAGE_READWRITE);
1523   return ptr;
1524 #endif
1525 }
1526
1527 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
1528 static FORCEINLINE void* win32direct_mmap(size_t size) {
1529 #if 0
1530   void* ptr = VirtualAlloc(0, size, MEM_RESERVE, PAGE_NOACCESS);
1531   if (ptr == 0)
1532     return MFAIL;
1533   VirtualAlloc(ptr, size, MEM_COMMIT, PAGE_READWRITE);
1534   return ptr;
1535 #else
1536   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
1537                            PAGE_READWRITE);
1538   return (ptr != 0)? ptr: MFAIL;
1539 #endif
1540 }
1541
1542 /* This function supports releasing coalesed segments */
1543 static FORCEINLINE int win32munmap(void* ptr, size_t size) {
1544   MEMORY_BASIC_INFORMATION minfo;
1545   char* cptr = (char*)ptr;
1546   while (size) {
1547     if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
1548       return -1;
1549     if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
1550         minfo.State != MEM_COMMIT || minfo.RegionSize > size)
1551       return -1;
1552     if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
1553       return -1;
1554     cptr += minfo.RegionSize;
1555     size -= minfo.RegionSize;
1556   }
1557   return 0;
1558 }
1559
1560 #define MMAP_DEFAULT(s)             win32mmap(s)
1561 #define MUNMAP_DEFAULT(a, s)        win32munmap((a), (s))
1562 #define DIRECT_MMAP_DEFAULT(s)      win32direct_mmap(s)
1563 #endif /* WIN32 */
1564 #endif /* HAVE_MMAP */
1565
1566 #if HAVE_MREMAP
1567 #ifndef WIN32
1568 #define MREMAP_DEFAULT(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
1569 #endif /* WIN32 */
1570 #endif /* HAVE_MREMAP */
1571
1572
1573 /**
1574  * Define CALL_MORECORE
1575  */
1576 #if HAVE_MORECORE
1577     #ifdef MORECORE
1578         #define CALL_MORECORE(S)    MORECORE(S)
1579     #else  /* MORECORE */
1580         #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
1581     #endif /* MORECORE */
1582 #else  /* HAVE_MORECORE */
1583     #define CALL_MORECORE(S)        MFAIL
1584 #endif /* HAVE_MORECORE */
1585
1586 /**
1587  * Define CALL_MMAP/CALL_MUNMAP/CALL_DIRECT_MMAP
1588  */
1589 #if HAVE_MMAP
1590     #define USE_MMAP_BIT            (SIZE_T_ONE)
1591
1592     #ifdef MMAP
1593         #define CALL_MMAP(s)        MMAP(s)
1594     #else /* MMAP */
1595         #define CALL_MMAP(s)        MMAP_DEFAULT(s)
1596     #endif /* MMAP */
1597     #ifdef MUNMAP
1598         #define CALL_MUNMAP(a, s)   MUNMAP((a), (s))
1599     #else /* MUNMAP */
1600         #define CALL_MUNMAP(a, s)   MUNMAP_DEFAULT((a), (s))
1601     #endif /* MUNMAP */
1602     #ifdef DIRECT_MMAP
1603         #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)
1604     #else /* DIRECT_MMAP */
1605         #define CALL_DIRECT_MMAP(s) DIRECT_MMAP_DEFAULT(s)
1606     #endif /* DIRECT_MMAP */
1607 #else  /* HAVE_MMAP */
1608     #define USE_MMAP_BIT            (SIZE_T_ZERO)
1609
1610     #define MMAP(s)                 MFAIL
1611     #define MUNMAP(a, s)            (-1)
1612     #define DIRECT_MMAP(s)          MFAIL
1613     #define CALL_DIRECT_MMAP(s)     DIRECT_MMAP(s)
1614     #define CALL_MMAP(s)            MMAP(s)
1615     #define CALL_MUNMAP(a, s)       MUNMAP((a), (s))
1616 #endif /* HAVE_MMAP */
1617
1618 /**
1619  * Define CALL_MREMAP
1620  */
1621 #if HAVE_MMAP && HAVE_MREMAP
1622     #ifdef MREMAP
1623         #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP((addr), (osz), (nsz), (mv))
1624     #else /* MREMAP */
1625         #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP_DEFAULT((addr), (osz), (nsz), (mv))
1626     #endif /* MREMAP */
1627 #else  /* HAVE_MMAP && HAVE_MREMAP */
1628     #define CALL_MREMAP(addr, osz, nsz, mv)     MFAIL
1629 #endif /* HAVE_MMAP && HAVE_MREMAP */
1630
1631 /* mstate bit set if continguous morecore disabled or failed */
1632 #define USE_NONCONTIGUOUS_BIT (4U)
1633
1634 /* segment bit set in create_mspace_with_base */
1635 #define EXTERN_BIT            (8U)
1636
1637
1638 /* --------------------------- Lock preliminaries ------------------------ */
1639
1640 /*
1641   When locks are defined, there is one global lock, plus
1642   one per-mspace lock.
1643
1644   The global lock_ensures that mparams.magic and other unique
1645   mparams values are initialized only once. It also protects
1646   sequences of calls to MORECORE.  In many cases sys_alloc requires
1647   two calls, that should not be interleaved with calls by other
1648   threads.  This does not protect against direct calls to MORECORE
1649   by other threads not using this lock, so there is still code to
1650   cope the best we can on interference.
1651
1652   Per-mspace locks surround calls to malloc, free, etc.  To enable use
1653   in layered extensions, per-mspace locks are reentrant.
1654
1655   Because lock-protected regions generally have bounded times, it is
1656   OK to use the supplied simple spinlocks in the custom versions for
1657   x86. Spinlocks are likely to improve performance for lightly
1658   contended applications, but worsen performance under heavy
1659   contention.
1660
1661   If USE_LOCKS is > 1, the definitions of lock routines here are
1662   bypassed, in which case you will need to define the type MLOCK_T,
1663   and at least INITIAL_LOCK, ACQUIRE_LOCK, RELEASE_LOCK and possibly
1664   TRY_LOCK (which is not used in this malloc, but commonly needed in
1665   extensions.)  You must also declare a
1666     static MLOCK_T malloc_global_mutex = { initialization values };.
1667
1668 */
1669
1670 #if USE_LOCKS == 1
1671
1672 #if USE_SPIN_LOCKS && SPIN_LOCKS_AVAILABLE
1673 #ifndef WIN32
1674
1675 /* Custom pthread-style spin locks on x86 and x64 for gcc */
1676 struct pthread_mlock_t {
1677   volatile unsigned int l;
1678   unsigned int c;
1679   pthread_t threadid;
1680 };
1681 #define MLOCK_T               struct pthread_mlock_t
1682 #define CURRENT_THREAD        pthread_self()
1683 #define INITIAL_LOCK(sl)      ((sl)->threadid = 0, (sl)->l = (sl)->c = 0, 0)
1684 #define ACQUIRE_LOCK(sl)      pthread_acquire_lock(sl)
1685 #define RELEASE_LOCK(sl)      pthread_release_lock(sl)
1686 #define TRY_LOCK(sl)          pthread_try_lock(sl)
1687 #define SPINS_PER_YIELD       63
1688
1689 static MLOCK_T malloc_global_mutex = { 0, 0, 0};
1690
1691 static FORCEINLINE int pthread_acquire_lock (MLOCK_T *sl) {
1692   int spins = 0;
1693   volatile unsigned int* lp = &sl->l;
1694   for (;;) {
1695     if (*lp != 0) {
1696       if (sl->threadid == CURRENT_THREAD) {
1697         ++sl->c;
1698         return 0;
1699       }
1700     }
1701     else {
1702       /* place args to cmpxchgl in locals to evade oddities in some gccs */
1703       int cmp = 0;
1704       int val = 1;
1705       int ret;
1706       __asm__ __volatile__  ("lock; cmpxchgl %1, %2"
1707                              : "=a" (ret)
1708                              : "r" (val), "m" (*(lp)), "0"(cmp)
1709                              : "memory", "cc");
1710       if (!ret) {
1711         assert(!sl->threadid);
1712         sl->threadid = CURRENT_THREAD;
1713         sl->c = 1;
1714         return 0;
1715       }
1716     }
1717     if ((++spins & SPINS_PER_YIELD) == 0) {
1718 #if defined (__SVR4) && defined (__sun) /* solaris */
1719       thr_yield();
1720 #else
1721 #if defined(__linux__) || defined(__FreeBSD__) || defined(__APPLE__)
1722       sched_yield();
1723 #else  /* no-op yield on unknown systems */
1724       ;
1725 #endif /* __linux__ || __FreeBSD__ || __APPLE__ */
1726 #endif /* solaris */
1727     }
1728   }
1729 }
1730
1731 static FORCEINLINE void pthread_release_lock (MLOCK_T *sl) {
1732   volatile unsigned int* lp = &sl->l;
1733   assert(*lp != 0);
1734   assert(sl->threadid == CURRENT_THREAD);
1735   if (--sl->c == 0) {
1736     sl->threadid = 0;
1737     int prev = 0;
1738     int ret;
1739     __asm__ __volatile__ ("lock; xchgl %0, %1"
1740                           : "=r" (ret)
1741                           : "m" (*(lp)), "0"(prev)
1742                           : "memory");
1743   }
1744 }
1745
1746 static FORCEINLINE int pthread_try_lock (MLOCK_T *sl) {
1747   volatile unsigned int* lp = &sl->l;
1748   if (*lp != 0) {
1749     if (sl->threadid == CURRENT_THREAD) {
1750       ++sl->c;
1751       return 1;
1752     }
1753   }
1754   else {
1755     int cmp = 0;
1756     int val = 1;
1757     int ret;
1758     __asm__ __volatile__  ("lock; cmpxchgl %1, %2"
1759                            : "=a" (ret)
1760                            : "r" (val), "m" (*(lp)), "0"(cmp)
1761                            : "memory", "cc");
1762     if (!ret) {
1763       assert(!sl->threadid);
1764       sl->threadid = CURRENT_THREAD;
1765       sl->c = 1;
1766       return 1;
1767     }
1768   }
1769   return 0;
1770 }
1771
1772
1773 #else /* WIN32 */
1774 /* Custom win32-style spin locks on x86 and x64 for MSC */
1775 struct win32_mlock_t {
1776   volatile long l;
1777   unsigned int c;
1778   long threadid;
1779 };
1780
1781 #define MLOCK_T               struct win32_mlock_t
1782 #define CURRENT_THREAD        GetCurrentThreadId()
1783 #define INITIAL_LOCK(sl)      ((sl)->threadid = 0, (sl)->l = (sl)->c = 0, 0)
1784 #define ACQUIRE_LOCK(sl)      win32_acquire_lock(sl)
1785 #define RELEASE_LOCK(sl)      win32_release_lock(sl)
1786 #define TRY_LOCK(sl)          win32_try_lock(sl)
1787 #define SPINS_PER_YIELD       63
1788
1789 static MLOCK_T malloc_global_mutex = { 0, 0, 0};
1790
1791 static FORCEINLINE int win32_acquire_lock (MLOCK_T *sl) {
1792   int spins = 0;
1793   for (;;) {
1794     if (sl->l != 0) {
1795       if (sl->threadid == CURRENT_THREAD) {
1796         ++sl->c;
1797         return 0;
1798       }
1799     }
1800     else {
1801       if (!interlockedexchange(&sl->l, 1)) {
1802         assert(!sl->threadid);
1803         sl->threadid = CURRENT_THREAD;
1804         sl->c = 1;
1805         return 0;
1806       }
1807     }
1808     //    if ((++spins & SPINS_PER_YIELD) == 0)
1809     //      SleepEx(0, FALSE);
1810   }
1811 }
1812
1813 static FORCEINLINE void win32_release_lock (MLOCK_T *sl) {
1814   assert(sl->threadid == CURRENT_THREAD);
1815   assert(sl->l != 0);
1816   if (--sl->c == 0) {
1817     sl->threadid = 0;
1818     interlockedexchange (&sl->l, 0);
1819   }
1820 }
1821
1822 static FORCEINLINE int win32_try_lock (MLOCK_T *sl) {
1823   if (sl->l != 0) {
1824     if (sl->threadid == CURRENT_THREAD) {
1825       ++sl->c;
1826       return 1;
1827     }
1828   }
1829   else {
1830     if (!interlockedexchange(&sl->l, 1)){
1831       assert(!sl->threadid);
1832       sl->threadid = CURRENT_THREAD;
1833       sl->c = 1;
1834       return 1;
1835     }
1836   }
1837   return 0;
1838 }
1839
1840 #endif /* WIN32 */
1841 #else /* USE_SPIN_LOCKS */
1842
1843 #ifndef WIN32
1844 /* pthreads-based locks */
1845
1846 #define MLOCK_T               pthread_mutex_t
1847 #define CURRENT_THREAD        pthread_self()
1848 #define INITIAL_LOCK(sl)      pthread_init_lock(sl)
1849 #define ACQUIRE_LOCK(sl)      pthread_mutex_lock(sl)
1850 #define RELEASE_LOCK(sl)      pthread_mutex_unlock(sl)
1851 #define TRY_LOCK(sl)          (!pthread_mutex_trylock(sl))
1852
1853 static MLOCK_T malloc_global_mutex = PTHREAD_MUTEX_INITIALIZER;
1854
1855 /* Cope with old-style linux recursive lock initialization by adding */
1856 /* skipped internal declaration from pthread.h */
1857 #ifdef linux
1858 #ifndef PTHREAD_MUTEX_RECURSIVE
1859 extern int pthread_mutexattr_setkind_np __P ((pthread_mutexattr_t *__attr,
1860                                            int __kind));
1861 #define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP
1862 #define pthread_mutexattr_settype(x,y) pthread_mutexattr_setkind_np(x,y)
1863 #endif
1864 #endif
1865
1866 static int pthread_init_lock (MLOCK_T *sl) {
1867   pthread_mutexattr_t attr;
1868   if (pthread_mutexattr_init(&attr)) return 1;
1869   if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1;
1870   if (pthread_mutex_init(sl, &attr)) return 1;
1871   if (pthread_mutexattr_destroy(&attr)) return 1;
1872   return 0;
1873 }
1874
1875 #else /* WIN32 */
1876 /* Win32 critical sections */
1877 #define MLOCK_T               CRITICAL_SECTION
1878 #define CURRENT_THREAD        GetCurrentThreadId()
1879 #define INITIAL_LOCK(s)       (!InitializeCriticalSectionAndSpinCount((s), 0x80000000|4000))
1880 #define ACQUIRE_LOCK(s)       (EnterCriticalSection(sl), 0)
1881 #define RELEASE_LOCK(s)       LeaveCriticalSection(sl)
1882 #define TRY_LOCK(s)           TryEnterCriticalSection(sl)
1883 #define NEED_GLOBAL_LOCK_INIT
1884
1885 static MLOCK_T malloc_global_mutex;
1886 static volatile long malloc_global_mutex_status;
1887
1888 /* Use spin loop to initialize global lock */
1889 static void init_malloc_global_mutex() {
1890   for (;;) {
1891     long stat = malloc_global_mutex_status;
1892     if (stat > 0)
1893       return;
1894     /* transition to < 0 while initializing, then to > 0) */
1895     if (stat == 0 &&
1896         interlockedcompareexchange(&malloc_global_mutex_status, -1, 0) == 0) {
1897       InitializeCriticalSection(&malloc_global_mutex);
1898       interlockedexchange(&malloc_global_mutex_status,1);
1899       return;
1900     }
1901     //    SleepEx(0, FALSE);
1902   }
1903 }
1904
1905 #endif /* WIN32 */
1906 #endif /* USE_SPIN_LOCKS */
1907 #endif /* USE_LOCKS == 1 */
1908
1909 /* -----------------------  User-defined locks ------------------------ */
1910
1911 #if USE_LOCKS > 1
1912 /* Define your own lock implementation here */
1913 /* #define INITIAL_LOCK(sl)  ... */
1914 /* #define ACQUIRE_LOCK(sl)  ... */
1915 /* #define RELEASE_LOCK(sl)  ... */
1916 /* #define TRY_LOCK(sl) ... */
1917 /* static MLOCK_T malloc_global_mutex = ... */
1918 #endif /* USE_LOCKS > 1 */
1919
1920 /* -----------------------  Lock-based state ------------------------ */
1921
1922 #if USE_LOCKS
1923 #define USE_LOCK_BIT               (2U)
1924 #else  /* USE_LOCKS */
1925 #define USE_LOCK_BIT               (0U)
1926 #define INITIAL_LOCK(l)
1927 #endif /* USE_LOCKS */
1928
1929 #if USE_LOCKS
1930 #ifndef ACQUIRE_MALLOC_GLOBAL_LOCK
1931 #define ACQUIRE_MALLOC_GLOBAL_LOCK()  ACQUIRE_LOCK(&malloc_global_mutex);
1932 #endif
1933 #ifndef RELEASE_MALLOC_GLOBAL_LOCK
1934 #define RELEASE_MALLOC_GLOBAL_LOCK()  RELEASE_LOCK(&malloc_global_mutex);
1935 #endif
1936 #else  /* USE_LOCKS */
1937 #define ACQUIRE_MALLOC_GLOBAL_LOCK()
1938 #define RELEASE_MALLOC_GLOBAL_LOCK()
1939 #endif /* USE_LOCKS */
1940
1941
1942 /* -----------------------  Chunk representations ------------------------ */
1943
1944 /*
1945   (The following includes lightly edited explanations by Colin Plumb.)
1946
1947   The malloc_chunk declaration below is misleading (but accurate and
1948   necessary).  It declares a "view" into memory allowing access to
1949   necessary fields at known offsets from a given base.
1950
1951   Chunks of memory are maintained using a `boundary tag' method as
1952   originally described by Knuth.  (See the paper by Paul Wilson
1953   ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
1954   techniques.)  Sizes of free chunks are stored both in the front of
1955   each chunk and at the end.  This makes consolidating fragmented
1956   chunks into bigger chunks fast.  The head fields also hold bits
1957   representing whether chunks are free or in use.
1958
1959   Here are some pictures to make it clearer.  They are "exploded" to
1960   show that the state of a chunk can be thought of as extending from
1961   the high 31 bits of the head field of its header through the
1962   prev_foot and PINUSE_BIT bit of the following chunk header.
1963
1964   A chunk that's in use looks like:
1965
1966    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1967            | Size of previous chunk (if P = 0)                             |
1968            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1969          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1970          | Size of this chunk                                         1| +-+
1971    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1972          |                                                               |
1973          +-                                                             -+
1974          |                                                               |
1975          +-                                                             -+
1976          |                                                               :
1977          +-      size - sizeof(size_t) available payload bytes          -+
1978          :                                                               |
1979  chunk-> +-                                                             -+
1980          |                                                               |
1981          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1982        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
1983        | Size of next chunk (may or may not be in use)               | +-+
1984  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1985
1986     And if it's free, it looks like this:
1987
1988    chunk-> +-                                                             -+
1989            | User payload (must be in use, or we would have merged!)       |
1990            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1991          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1992          | Size of this chunk                                         0| +-+
1993    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1994          | Next pointer                                                  |
1995          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1996          | Prev pointer                                                  |
1997          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1998          |                                                               :
1999          +-      size - sizeof(struct chunk) unused bytes               -+
2000          :                                                               |
2001  chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2002          | Size of this chunk                                            |
2003          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2004        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
2005        | Size of next chunk (must be in use, or we would have merged)| +-+
2006  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2007        |                                                               :
2008        +- User payload                                                -+
2009        :                                                               |
2010        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2011                                                                      |0|
2012                                                                      +-+
2013   Note that since we always merge adjacent free chunks, the chunks
2014   adjacent to a free chunk must be in use.
2015
2016   Given a pointer to a chunk (which can be derived trivially from the
2017   payload pointer) we can, in O(1) time, find out whether the adjacent
2018   chunks are free, and if so, unlink them from the lists that they
2019   are on and merge them with the current chunk.
2020
2021   Chunks always begin on even word boundaries, so the mem portion
2022   (which is returned to the user) is also on an even word boundary, and
2023   thus at least double-word aligned.
2024
2025   The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
2026   chunk size (which is always a multiple of two words), is an in-use
2027   bit for the *previous* chunk.  If that bit is *clear*, then the
2028   word before the current chunk size contains the previous chunk
2029   size, and can be used to find the front of the previous chunk.
2030   The very first chunk allocated always has this bit set, preventing
2031   access to non-existent (or non-owned) memory. If pinuse is set for
2032   any given chunk, then you CANNOT determine the size of the
2033   previous chunk, and might even get a memory addressing fault when
2034   trying to do so.
2035
2036   The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
2037   the chunk size redundantly records whether the current chunk is
2038   inuse (unless the chunk is mmapped). This redundancy enables usage
2039   checks within free and realloc, and reduces indirection when freeing
2040   and consolidating chunks.
2041
2042   Each freshly allocated chunk must have both cinuse and pinuse set.
2043   That is, each allocated chunk borders either a previously allocated
2044   and still in-use chunk, or the base of its memory arena. This is
2045   ensured by making all allocations from the the `lowest' part of any
2046   found chunk.  Further, no free chunk physically borders another one,
2047   so each free chunk is known to be preceded and followed by either
2048   inuse chunks or the ends of memory.
2049
2050   Note that the `foot' of the current chunk is actually represented
2051   as the prev_foot of the NEXT chunk. This makes it easier to
2052   deal with alignments etc but can be very confusing when trying
2053   to extend or adapt this code.
2054
2055   The exceptions to all this are
2056
2057      1. The special chunk `top' is the top-most available chunk (i.e.,
2058         the one bordering the end of available memory). It is treated
2059         specially.  Top is never included in any bin, is used only if
2060         no other chunk is available, and is released back to the
2061         system if it is very large (see M_TRIM_THRESHOLD).  In effect,
2062         the top chunk is treated as larger (and thus less well
2063         fitting) than any other available chunk.  The top chunk
2064         doesn't update its trailing size field since there is no next
2065         contiguous chunk that would have to index off it. However,
2066         space is still allocated for it (TOP_FOOT_SIZE) to enable
2067         separation or merging when space is extended.
2068
2069      3. Chunks allocated via mmap, have both cinuse and pinuse bits
2070         cleared in their head fields.  Because they are allocated
2071         one-by-one, each must carry its own prev_foot field, which is
2072         also used to hold the offset this chunk has within its mmapped
2073         region, which is needed to preserve alignment. Each mmapped
2074         chunk is trailed by the first two fields of a fake next-chunk
2075         for sake of usage checks.
2076
2077 */
2078
2079 struct malloc_chunk {
2080   size_t               prev_foot;  /* Size of previous chunk (if free).  */
2081   size_t               head;       /* Size and inuse bits. */
2082   struct malloc_chunk* fd;         /* double links -- used only if free. */
2083   struct malloc_chunk* bk;
2084 };
2085
2086 typedef struct malloc_chunk  mchunk;
2087 typedef struct malloc_chunk* mchunkptr;
2088 typedef struct malloc_chunk* sbinptr;  /* The type of bins of chunks */
2089 typedef unsigned int bindex_t;         /* Described below */
2090 typedef unsigned int binmap_t;         /* Described below */
2091 typedef unsigned int flag_t;           /* The type of various bit flag sets */
2092
2093 /* ------------------- Chunks sizes and alignments ----------------------- */
2094
2095 #define MCHUNK_SIZE         (sizeof(mchunk))
2096
2097 #if FOOTERS
2098 #define CHUNK_OVERHEAD      (TWO_SIZE_T_SIZES)
2099 #else /* FOOTERS */
2100 #define CHUNK_OVERHEAD      (SIZE_T_SIZE)
2101 #endif /* FOOTERS */
2102
2103 /* MMapped chunks need a second word of overhead ... */
2104 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
2105 /* ... and additional padding for fake next-chunk at foot */
2106 #define MMAP_FOOT_PAD       (FOUR_SIZE_T_SIZES)
2107
2108 /* The smallest size we can malloc is an aligned minimal chunk */
2109 #define MIN_CHUNK_SIZE\
2110   ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
2111
2112 /* conversion from malloc headers to user pointers, and back */
2113 #define chunk2mem(p)        ((void*)((char*)(p)       + TWO_SIZE_T_SIZES))
2114 #define mem2chunk(mem)      ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
2115 /* chunk associated with aligned address A */
2116 #define align_as_chunk(A)   (mchunkptr)((A) + align_offset(chunk2mem(A)))
2117
2118 /* Bounds on request (not chunk) sizes. */
2119 #define MAX_REQUEST         ((-MIN_CHUNK_SIZE) << 2)
2120 #define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
2121
2122 /* pad request bytes into a usable size */
2123 #define pad_request(req) \
2124    (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
2125
2126 /* pad request, checking for minimum (but not maximum) */
2127 #define request2size(req) \
2128   (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
2129
2130
2131 /* ------------------ Operations on head and foot fields ----------------- */
2132
2133 /*
2134   The head field of a chunk is or'ed with PINUSE_BIT when previous
2135   adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
2136   use, unless mmapped, in which case both bits are cleared.
2137
2138   FLAG4_BIT is not used by this malloc, but might be useful in extensions.
2139 */
2140
2141 #define PINUSE_BIT          (SIZE_T_ONE)
2142 #define CINUSE_BIT          (SIZE_T_TWO)
2143 #define FLAG4_BIT           (SIZE_T_FOUR)
2144 #define INUSE_BITS          (PINUSE_BIT|CINUSE_BIT)
2145 #define FLAG_BITS           (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT)
2146
2147 /* Head value for fenceposts */
2148 #define FENCEPOST_HEAD      (INUSE_BITS|SIZE_T_SIZE)
2149
2150 /* extraction of fields from head words */
2151 #define cinuse(p)           ((p)->head & CINUSE_BIT)
2152 #define pinuse(p)           ((p)->head & PINUSE_BIT)
2153 #define is_inuse(p)         (((p)->head & INUSE_BITS) != PINUSE_BIT)
2154 #define is_mmapped(p)       (((p)->head & INUSE_BITS) == 0)
2155
2156 #define chunksize(p)        ((p)->head & ~(FLAG_BITS))
2157
2158 #define clear_pinuse(p)     ((p)->head &= ~PINUSE_BIT)
2159
2160 /* Treat space at ptr +/- offset as a chunk */
2161 #define chunk_plus_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
2162 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
2163
2164 /* Ptr to next or previous physical malloc_chunk. */
2165 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS)))
2166 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
2167
2168 /* extract next chunk's pinuse bit */
2169 #define next_pinuse(p)  ((next_chunk(p)->head) & PINUSE_BIT)
2170
2171 /* Get/set size at footer */
2172 #define get_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot)
2173 #define set_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
2174
2175 /* Set size, pinuse bit, and foot */
2176 #define set_size_and_pinuse_of_free_chunk(p, s)\
2177   ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
2178
2179 /* Set size, pinuse bit, foot, and clear next pinuse */
2180 #define set_free_with_pinuse(p, s, n)\
2181   (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
2182
2183 /* Get the internal overhead associated with chunk p */
2184 #define overhead_for(p)\
2185  (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
2186
2187 /* Return true if malloced space is not necessarily cleared */
2188 #if MMAP_CLEARS
2189 #define calloc_must_clear(p) (!is_mmapped(p))
2190 #else /* MMAP_CLEARS */
2191 #define calloc_must_clear(p) (1)
2192 #endif /* MMAP_CLEARS */
2193
2194 /* ---------------------- Overlaid data structures ----------------------- */
2195
2196 /*
2197   When chunks are not in use, they are treated as nodes of either
2198   lists or trees.
2199
2200   "Small"  chunks are stored in circular doubly-linked lists, and look
2201   like this:
2202
2203     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2204             |             Size of previous chunk                            |
2205             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2206     `head:' |             Size of chunk, in bytes                         |P|
2207       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2208             |             Forward pointer to next chunk in list             |
2209             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2210             |             Back pointer to previous chunk in list            |
2211             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2212             |             Unused space (may be 0 bytes long)                .
2213             .                                                               .
2214             .                                                               |
2215 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2216     `foot:' |             Size of chunk, in bytes                           |
2217             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2218
2219   Larger chunks are kept in a form of bitwise digital trees (aka
2220   tries) keyed on chunksizes.  Because malloc_tree_chunks are only for
2221   free chunks greater than 256 bytes, their size doesn't impose any
2222   constraints on user chunk sizes.  Each node looks like:
2223
2224     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2225             |             Size of previous chunk                            |
2226             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2227     `head:' |             Size of chunk, in bytes                         |P|
2228       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2229             |             Forward pointer to next chunk of same size        |
2230             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2231             |             Back pointer to previous chunk of same size       |
2232             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2233             |             Pointer to left child (child[0])                  |
2234             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2235             |             Pointer to right child (child[1])                 |
2236             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2237             |             Pointer to parent                                 |
2238             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2239             |             bin index of this chunk                           |
2240             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2241             |             Unused space                                      .
2242             .                                                               |
2243 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2244     `foot:' |             Size of chunk, in bytes                           |
2245             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2246
2247   Each tree holding treenodes is a tree of unique chunk sizes.  Chunks
2248   of the same size are arranged in a circularly-linked list, with only
2249   the oldest chunk (the next to be used, in our FIFO ordering)
2250   actually in the tree.  (Tree members are distinguished by a non-null
2251   parent pointer.)  If a chunk with the same size an an existing node
2252   is inserted, it is linked off the existing node using pointers that
2253   work in the same way as fd/bk pointers of small chunks.
2254
2255   Each tree contains a power of 2 sized range of chunk sizes (the
2256   smallest is 0x100 <= x < 0x180), which is is divided in half at each
2257   tree level, with the chunks in the smaller half of the range (0x100
2258   <= x < 0x140 for the top nose) in the left subtree and the larger
2259   half (0x140 <= x < 0x180) in the right subtree.  This is, of course,
2260   done by inspecting individual bits.
2261
2262   Using these rules, each node's left subtree contains all smaller
2263   sizes than its right subtree.  However, the node at the root of each
2264   subtree has no particular ordering relationship to either.  (The
2265   dividing line between the subtree sizes is based on trie relation.)
2266   If we remove the last chunk of a given size from the interior of the
2267   tree, we need to replace it with a leaf node.  The tree ordering
2268   rules permit a node to be replaced by any leaf below it.
2269
2270   The smallest chunk in a tree (a common operation in a best-fit
2271   allocator) can be found by walking a path to the leftmost leaf in
2272   the tree.  Unlike a usual binary tree, where we follow left child
2273   pointers until we reach a null, here we follow the right child
2274   pointer any time the left one is null, until we reach a leaf with
2275   both child pointers null. The smallest chunk in the tree will be
2276   somewhere along that path.
2277
2278   The worst case number of steps to add, find, or remove a node is
2279   bounded by the number of bits differentiating chunks within
2280   bins. Under current bin calculations, this ranges from 6 up to 21
2281   (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
2282   is of course much better.
2283 */
2284
2285 struct malloc_tree_chunk {
2286   /* The first four fields must be compatible with malloc_chunk */
2287   size_t                    prev_foot;
2288   size_t                    head;
2289   struct malloc_tree_chunk* fd;
2290   struct malloc_tree_chunk* bk;
2291
2292   struct malloc_tree_chunk* child[2];
2293   struct malloc_tree_chunk* parent;
2294   bindex_t                  index;
2295 };
2296
2297 typedef struct malloc_tree_chunk  tchunk;
2298 typedef struct malloc_tree_chunk* tchunkptr;
2299 typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
2300
2301 /* A little helper macro for trees */
2302 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
2303
2304 /* ----------------------------- Segments -------------------------------- */
2305
2306 /*
2307   Each malloc space may include non-contiguous segments, held in a
2308   list headed by an embedded malloc_segment record representing the
2309   top-most space. Segments also include flags holding properties of
2310   the space. Large chunks that are directly allocated by mmap are not
2311   included in this list. They are instead independently created and
2312   destroyed without otherwise keeping track of them.
2313
2314   Segment management mainly comes into play for spaces allocated by
2315   MMAP.  Any call to MMAP might or might not return memory that is
2316   adjacent to an existing segment.  MORECORE normally contiguously
2317   extends the current space, so this space is almost always adjacent,
2318   which is simpler and faster to deal with. (This is why MORECORE is
2319   used preferentially to MMAP when both are available -- see
2320   sys_alloc.)  When allocating using MMAP, we don't use any of the
2321   hinting mechanisms (inconsistently) supported in various
2322   implementations of unix mmap, or distinguish reserving from
2323   committing memory. Instead, we just ask for space, and exploit
2324   contiguity when we get it.  It is probably possible to do
2325   better than this on some systems, but no general scheme seems
2326   to be significantly better.
2327
2328   Management entails a simpler variant of the consolidation scheme
2329   used for chunks to reduce fragmentation -- new adjacent memory is
2330   normally prepended or appended to an existing segment. However,
2331   there are limitations compared to chunk consolidation that mostly
2332   reflect the fact that segment processing is relatively infrequent
2333   (occurring only when getting memory from system) and that we
2334   don't expect to have huge numbers of segments:
2335
2336   * Segments are not indexed, so traversal requires linear scans.  (It
2337     would be possible to index these, but is not worth the extra
2338     overhead and complexity for most programs on most platforms.)
2339   * New segments are only appended to old ones when holding top-most
2340     memory; if they cannot be prepended to others, they are held in
2341     different segments.
2342
2343   Except for the top-most segment of an mstate, each segment record
2344   is kept at the tail of its segment. Segments are added by pushing
2345   segment records onto the list headed by &mstate.seg for the
2346   containing mstate.
2347
2348   Segment flags control allocation/merge/deallocation policies:
2349   * If EXTERN_BIT set, then we did not allocate this segment,
2350     and so should not try to deallocate or merge with others.
2351     (This currently holds only for the initial segment passed
2352     into create_mspace_with_base.)
2353   * If USE_MMAP_BIT set, the segment may be merged with
2354     other surrounding mmapped segments and trimmed/de-allocated
2355     using munmap.
2356   * If neither bit is set, then the segment was obtained using
2357     MORECORE so can be merged with surrounding MORECORE'd segments
2358     and deallocated/trimmed using MORECORE with negative arguments.
2359 */
2360
2361 struct malloc_segment {
2362   char*        base;             /* base address */
2363   size_t       size;             /* allocated size */
2364   struct malloc_segment* next;   /* ptr to next segment */
2365   flag_t       sflags;           /* mmap and extern flag */
2366 };
2367
2368 #define is_mmapped_segment(S)  ((S)->sflags & USE_MMAP_BIT)
2369 #define is_extern_segment(S)   ((S)->sflags & EXTERN_BIT)
2370
2371 typedef struct malloc_segment  msegment;
2372 typedef struct malloc_segment* msegmentptr;
2373
2374 /* ---------------------------- malloc_state ----------------------------- */
2375
2376 /*
2377    A malloc_state holds all of the bookkeeping for a space.
2378    The main fields are:
2379
2380   Top
2381     The topmost chunk of the currently active segment. Its size is
2382     cached in topsize.  The actual size of topmost space is
2383     topsize+TOP_FOOT_SIZE, which includes space reserved for adding
2384     fenceposts and segment records if necessary when getting more
2385     space from the system.  The size at which to autotrim top is
2386     cached from mparams in trim_check, except that it is disabled if
2387     an autotrim fails.
2388
2389   Designated victim (dv)
2390     This is the preferred chunk for servicing small requests that
2391     don't have exact fits.  It is normally the chunk split off most
2392     recently to service another small request.  Its size is cached in
2393     dvsize. The link fields of this chunk are not maintained since it
2394     is not kept in a bin.
2395
2396   SmallBins
2397     An array of bin headers for free chunks.  These bins hold chunks
2398     with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
2399     chunks of all the same size, spaced 8 bytes apart.  To simplify
2400     use in double-linked lists, each bin header acts as a malloc_chunk
2401     pointing to the real first node, if it exists (else pointing to
2402     itself).  This avoids special-casing for headers.  But to avoid
2403     waste, we allocate only the fd/bk pointers of bins, and then use
2404     repositioning tricks to treat these as the fields of a chunk.
2405
2406   TreeBins
2407     Treebins are pointers to the roots of trees holding a range of
2408     sizes. There are 2 equally spaced treebins for each power of two
2409     from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
2410     larger.
2411
2412   Bin maps
2413     There is one bit map for small bins ("smallmap") and one for
2414     treebins ("treemap).  Each bin sets its bit when non-empty, and
2415     clears the bit when empty.  Bit operations are then used to avoid
2416     bin-by-bin searching -- nearly all "search" is done without ever
2417     looking at bins that won't be selected.  The bit maps
2418     conservatively use 32 bits per map word, even if on 64bit system.
2419     For a good description of some of the bit-based techniques used
2420     here, see Henry S. Warren Jr's book "Hacker's Delight" (and
2421     supplement at http://hackersdelight.org/). Many of these are
2422     intended to reduce the branchiness of paths through malloc etc, as
2423     well as to reduce the number of memory locations read or written.
2424
2425   Segments
2426     A list of segments headed by an embedded malloc_segment record
2427     representing the initial space.
2428
2429   Address check support
2430     The least_addr field is the least address ever obtained from
2431     MORECORE or MMAP. Attempted frees and reallocs of any address less
2432     than this are trapped (unless INSECURE is defined).
2433
2434   Magic tag
2435     A cross-check field that should always hold same value as mparams.magic.
2436
2437   Flags
2438     Bits recording whether to use MMAP, locks, or contiguous MORECORE
2439
2440   Statistics
2441     Each space keeps track of current and maximum system memory
2442     obtained via MORECORE or MMAP.
2443
2444   Trim support
2445     Fields holding the amount of unused topmost memory that should trigger
2446     timming, and a counter to force periodic scanning to release unused
2447     non-topmost segments.
2448
2449   Locking
2450     If USE_LOCKS is defined, the "mutex" lock is acquired and released
2451     around every public call using this mspace.
2452
2453   Extension support
2454     A void* pointer and a size_t field that can be used to help implement
2455     extensions to this malloc.
2456 */
2457
2458 /* Bin types, widths and sizes */
2459 #define NSMALLBINS        (32U)
2460 #define NTREEBINS         (32U)
2461 #define SMALLBIN_SHIFT    (3U)
2462 #define SMALLBIN_WIDTH    (SIZE_T_ONE << SMALLBIN_SHIFT)
2463 #define TREEBIN_SHIFT     (8U)
2464 #define MIN_LARGE_SIZE    (SIZE_T_ONE << TREEBIN_SHIFT)
2465 #define MAX_SMALL_SIZE    (MIN_LARGE_SIZE - SIZE_T_ONE)
2466 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
2467
2468 struct malloc_state {
2469   binmap_t   smallmap;
2470   binmap_t   treemap;
2471   size_t     dvsize;
2472   size_t     topsize;
2473   char*      least_addr;
2474   mchunkptr  dv;
2475   mchunkptr  top;
2476   size_t     trim_check;
2477   size_t     release_checks;
2478   size_t     magic;
2479   mchunkptr  smallbins[(NSMALLBINS+1)*2];
2480   tbinptr    treebins[NTREEBINS];
2481   size_t     footprint;
2482   size_t     max_footprint;
2483   flag_t     mflags;
2484 #if USE_LOCKS
2485   MLOCK_T    mutex;     /* locate lock among fields that rarely change */
2486 #endif /* USE_LOCKS */
2487   msegment   seg;
2488   void*      extp;      /* Unused but available for extensions */
2489   size_t     exts;
2490 };
2491
2492 typedef struct malloc_state*    mstate;
2493
2494 /* ------------- Global malloc_state and malloc_params ------------------- */
2495
2496 /*
2497   malloc_params holds global properties, including those that can be
2498   dynamically set using mallopt. There is a single instance, mparams,
2499   initialized in init_mparams. Note that the non-zeroness of "magic"
2500   also serves as an initialization flag.
2501 */
2502
2503 struct malloc_params {
2504   volatile size_t magic;
2505   size_t page_size;
2506   size_t granularity;
2507   size_t mmap_threshold;
2508   size_t trim_threshold;
2509   flag_t default_mflags;
2510 };
2511
2512 static struct malloc_params mparams;
2513
2514 /* Ensure mparams initialized */
2515 #define ensure_initialization() (void)(mparams.magic != 0 || init_mparams())
2516
2517 #if !ONLY_MSPACES
2518
2519 /* The global malloc_state used for all non-"mspace" calls */
2520 static struct malloc_state _gm_;
2521 #define gm                 (&_gm_)
2522 #define is_global(M)       ((M) == &_gm_)
2523
2524 #endif /* !ONLY_MSPACES */
2525
2526 #define is_initialized(M)  ((M)->top != 0)
2527
2528 /* -------------------------- system alloc setup ------------------------- */
2529
2530 /* Operations on mflags */
2531
2532 #define use_lock(M)           ((M)->mflags &   USE_LOCK_BIT)
2533 #define enable_lock(M)        ((M)->mflags |=  USE_LOCK_BIT)
2534 #define disable_lock(M)       ((M)->mflags &= ~USE_LOCK_BIT)
2535
2536 #define use_mmap(M)           ((M)->mflags &   USE_MMAP_BIT)
2537 #define enable_mmap(M)        ((M)->mflags |=  USE_MMAP_BIT)
2538 #define disable_mmap(M)       ((M)->mflags &= ~USE_MMAP_BIT)
2539
2540 #define use_noncontiguous(M)  ((M)->mflags &   USE_NONCONTIGUOUS_BIT)
2541 #define disable_contiguous(M) ((M)->mflags |=  USE_NONCONTIGUOUS_BIT)
2542
2543 #define set_lock(M,L)\
2544  ((M)->mflags = (L)?\
2545   ((M)->mflags | USE_LOCK_BIT) :\
2546   ((M)->mflags & ~USE_LOCK_BIT))
2547
2548 /* page-align a size */
2549 #define page_align(S)\
2550  (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE))
2551
2552 /* granularity-align a size */
2553 #define granularity_align(S)\
2554   (((S) + (mparams.granularity - SIZE_T_ONE))\
2555    & ~(mparams.granularity - SIZE_T_ONE))
2556
2557
2558 /* For mmap, use granularity alignment on windows, else page-align */
2559 #ifdef WIN32
2560 #define mmap_align(S) granularity_align(S)
2561 #else
2562 #define mmap_align(S) page_align(S)
2563 #endif
2564
2565 /* For sys_alloc, enough padding to ensure can malloc request on success */
2566 #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT)
2567
2568 #define is_page_aligned(S)\
2569    (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
2570 #define is_granularity_aligned(S)\
2571    (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
2572
2573 /*  True if segment S holds address A */
2574 #define segment_holds(S, A)\
2575   ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
2576
2577 /* Return segment holding given address */
2578 static msegmentptr segment_holding(mstate m, char* addr) {
2579   msegmentptr sp = &m->seg;
2580   for (;;) {
2581     if (addr >= sp->base && addr < sp->base + sp->size)
2582       return sp;
2583     if ((sp = sp->next) == 0)
2584       return 0;
2585   }
2586 }
2587
2588 /* Return true if segment contains a segment link */
2589 static int has_segment_link(mstate m, msegmentptr ss) {
2590   msegmentptr sp = &m->seg;
2591   for (;;) {
2592     if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
2593       return 1;
2594     if ((sp = sp->next) == 0)
2595       return 0;
2596   }
2597 }
2598
2599 #ifndef MORECORE_CANNOT_TRIM
2600 #define should_trim(M,s)  ((s) > (M)->trim_check)
2601 #else  /* MORECORE_CANNOT_TRIM */
2602 #define should_trim(M,s)  (0)
2603 #endif /* MORECORE_CANNOT_TRIM */
2604
2605 /*
2606   TOP_FOOT_SIZE is padding at the end of a segment, including space
2607   that may be needed to place segment records and fenceposts when new
2608   noncontiguous segments are added.
2609 */
2610 #define TOP_FOOT_SIZE\
2611   (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
2612
2613
2614 /* -------------------------------  Hooks -------------------------------- */
2615
2616 /*
2617   PREACTION should be defined to return 0 on success, and nonzero on
2618   failure. If you are not using locking, you can redefine these to do
2619   anything you like.
2620 */
2621
2622 #if USE_LOCKS
2623
2624 #define PREACTION(M)  ((use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
2625 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
2626 #else /* USE_LOCKS */
2627
2628 #ifndef PREACTION
2629 #define PREACTION(M) (0)
2630 #endif  /* PREACTION */
2631
2632 #ifndef POSTACTION
2633 #define POSTACTION(M)
2634 #endif  /* POSTACTION */
2635
2636 #endif /* USE_LOCKS */
2637
2638 /*
2639   CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
2640   USAGE_ERROR_ACTION is triggered on detected bad frees and
2641   reallocs. The argument p is an address that might have triggered the
2642   fault. It is ignored by the two predefined actions, but might be
2643   useful in custom actions that try to help diagnose errors.
2644 */
2645
2646 #if PROCEED_ON_ERROR
2647
2648 /* A count of the number of corruption errors causing resets */
2649 int malloc_corruption_error_count;
2650
2651 /* default corruption action */
2652 static void reset_on_error(mstate m);
2653
2654 #define CORRUPTION_ERROR_ACTION(m)  reset_on_error(m)
2655 #define USAGE_ERROR_ACTION(m, p)
2656
2657 #else /* PROCEED_ON_ERROR */
2658
2659 #ifndef CORRUPTION_ERROR_ACTION
2660 #define CORRUPTION_ERROR_ACTION(m) ABORT
2661 #endif /* CORRUPTION_ERROR_ACTION */
2662
2663 #ifndef USAGE_ERROR_ACTION
2664 #define USAGE_ERROR_ACTION(m,p) ABORT
2665 #endif /* USAGE_ERROR_ACTION */
2666
2667 #endif /* PROCEED_ON_ERROR */
2668
2669 /* -------------------------- Debugging setup ---------------------------- */
2670
2671 #if ! DEBUG
2672
2673 #define check_free_chunk(M,P)
2674 #define check_inuse_chunk(M,P)
2675 #define check_malloced_chunk(M,P,N)
2676 #define check_mmapped_chunk(M,P)
2677 #define check_malloc_state(M)
2678 #define check_top_chunk(M,P)
2679
2680 #else /* DEBUG */
2681 #define check_free_chunk(M,P)       do_check_free_chunk(M,P)
2682 #define check_inuse_chunk(M,P)      do_check_inuse_chunk(M,P)
2683 #define check_top_chunk(M,P)        do_check_top_chunk(M,P)
2684 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
2685 #define check_mmapped_chunk(M,P)    do_check_mmapped_chunk(M,P)
2686 #define check_malloc_state(M)       do_check_malloc_state(M)
2687
2688 static void   do_check_any_chunk(mstate m, mchunkptr p);
2689 static void   do_check_top_chunk(mstate m, mchunkptr p);
2690 static void   do_check_mmapped_chunk(mstate m, mchunkptr p);
2691 static void   do_check_inuse_chunk(mstate m, mchunkptr p);
2692 static void   do_check_free_chunk(mstate m, mchunkptr p);
2693 static void   do_check_malloced_chunk(mstate m, void* mem, size_t s);
2694 static void   do_check_tree(mstate m, tchunkptr t);
2695 static void   do_check_treebin(mstate m, bindex_t i);
2696 static void   do_check_smallbin(mstate m, bindex_t i);
2697 static void   do_check_malloc_state(mstate m);
2698 static int    bin_find(mstate m, mchunkptr x);
2699 static size_t traverse_and_check(mstate m);
2700 #endif /* DEBUG */
2701
2702 /* ---------------------------- Indexing Bins ---------------------------- */
2703
2704 #define is_small(s)         (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
2705 #define small_index(s)      ((s)  >> SMALLBIN_SHIFT)
2706 #define small_index2size(i) ((i)  << SMALLBIN_SHIFT)
2707 #define MIN_SMALL_INDEX     (small_index(MIN_CHUNK_SIZE))
2708
2709 /* addressing by index. See above about smallbin repositioning */
2710 #define smallbin_at(M, i)   ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
2711 #define treebin_at(M,i)     (&((M)->treebins[i]))
2712
2713 /* assign tree index for size S to variable I. Use x86 asm if possible  */
2714 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
2715 #define compute_tree_index(S, I)\
2716 {\
2717   unsigned int X = S >> TREEBIN_SHIFT;\
2718   if (X == 0)\
2719     I = 0;\
2720   else if (X > 0xFFFF)\
2721     I = NTREEBINS-1;\
2722   else {\
2723     unsigned int K;\
2724     __asm__("bsrl\t%1, %0\n\t" : "=r" (K) : "g"  (X));\
2725     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2726   }\
2727 }
2728
2729 #elif defined (__INTEL_COMPILER)
2730 #define compute_tree_index(S, I)\
2731 {\
2732   size_t X = S >> TREEBIN_SHIFT;\
2733   if (X == 0)\
2734     I = 0;\
2735   else if (X > 0xFFFF)\
2736     I = NTREEBINS-1;\
2737   else {\
2738     unsigned int K = _bit_scan_reverse (X); \
2739     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2740   }\
2741 }
2742
2743 #elif defined(_MSC_VER) && _MSC_VER>=1300 && !defined(_WIN32_WCE)
2744 #define compute_tree_index(S, I)\
2745 {\
2746   size_t X = S >> TREEBIN_SHIFT;\
2747   if (X == 0)\
2748     I = 0;\
2749   else if (X > 0xFFFF)\
2750     I = NTREEBINS-1;\
2751   else {\
2752     unsigned int K;\
2753     _BitScanReverse((DWORD *) &K, X);\
2754     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2755   }\
2756 }
2757
2758 #else /* GNUC */
2759 #define compute_tree_index(S, I)\
2760 {\
2761   size_t X = S >> TREEBIN_SHIFT;\
2762   if (X == 0)\
2763     I = 0;\
2764   else if (X > 0xFFFF)\
2765     I = NTREEBINS-1;\
2766   else {\
2767     unsigned int Y = (unsigned int)X;\
2768     unsigned int N = ((Y - 0x100) >> 16) & 8;\
2769     unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
2770     N += K;\
2771     N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
2772     K = 14 - N + ((Y <<= K) >> 15);\
2773     I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
2774   }\
2775 }
2776 #endif /* GNUC */
2777
2778 /* Bit representing maximum resolved size in a treebin at i */
2779 #define bit_for_tree_index(i) \
2780    (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
2781
2782 /* Shift placing maximum resolved bit in a treebin at i as sign bit */
2783 #define leftshift_for_tree_index(i) \
2784    ((i == NTREEBINS-1)? 0 : \
2785     ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
2786
2787 /* The size of the smallest chunk held in bin with index i */
2788 #define minsize_for_tree_index(i) \
2789    ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) |  \
2790    (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
2791
2792
2793 /* ------------------------ Operations on bin maps ----------------------- */
2794
2795 /* bit corresponding to given index */
2796 #define idx2bit(i)              ((binmap_t)(1) << (i))
2797
2798 /* Mark/Clear bits with given index */
2799 #define mark_smallmap(M,i)      ((M)->smallmap |=  idx2bit(i))
2800 #define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))
2801 #define smallmap_is_marked(M,i) ((M)->smallmap &   idx2bit(i))
2802
2803 #define mark_treemap(M,i)       ((M)->treemap  |=  idx2bit(i))
2804 #define clear_treemap(M,i)      ((M)->treemap  &= ~idx2bit(i))
2805 #define treemap_is_marked(M,i)  ((M)->treemap  &   idx2bit(i))
2806
2807 /* isolate the least set bit of a bitmap */
2808 #define least_bit(x)         ((x) & -(x))
2809
2810 /* mask with all bits to left of least bit of x on */
2811 #define left_bits(x)         ((x<<1) | -(x<<1))
2812
2813 /* mask with all bits to left of or equal to least bit of x on */
2814 #define same_or_left_bits(x) ((x) | -(x))
2815
2816 /* index corresponding to given bit. Use x86 asm if possible */
2817
2818 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
2819 #define compute_bit2idx(X, I)\
2820 {\
2821   unsigned int J;\
2822   __asm__("bsfl\t%1, %0\n\t" : "=r" (J) : "g" (X));\
2823   I = (bindex_t)J;\
2824 }
2825
2826 #elif defined (__INTEL_COMPILER)
2827 #define compute_bit2idx(X, I)\
2828 {\
2829   unsigned int J;\
2830   J = _bit_scan_forward (X); \
2831   I = (bindex_t)J;\
2832 }
2833
2834 #elif defined(_MSC_VER) && _MSC_VER>=1300 && !defined(_WIN32_WCE)
2835 #define compute_bit2idx(X, I)\
2836 {\
2837   unsigned int J;\
2838   _BitScanForward((DWORD *) &J, X);\
2839   I = (bindex_t)J;\
2840 }
2841
2842 #elif USE_BUILTIN_FFS
2843 #define compute_bit2idx(X, I) I = ffs(X)-1
2844
2845 #else
2846 #define compute_bit2idx(X, I)\
2847 {\
2848   unsigned int Y = X - 1;\
2849   unsigned int K = Y >> (16-4) & 16;\
2850   unsigned int N = K;        Y >>= K;\
2851   N += K = Y >> (8-3) &  8;  Y >>= K;\
2852   N += K = Y >> (4-2) &  4;  Y >>= K;\
2853   N += K = Y >> (2-1) &  2;  Y >>= K;\
2854   N += K = Y >> (1-0) &  1;  Y >>= K;\
2855   I = (bindex_t)(N + Y);\
2856 }
2857 #endif /* GNUC */
2858
2859
2860 /* ----------------------- Runtime Check Support ------------------------- */
2861
2862 /*
2863   For security, the main invariant is that malloc/free/etc never
2864   writes to a static address other than malloc_state, unless static
2865   malloc_state itself has been corrupted, which cannot occur via
2866   malloc (because of these checks). In essence this means that we
2867   believe all pointers, sizes, maps etc held in malloc_state, but
2868   check all of those linked or offsetted from other embedded data
2869   structures.  These checks are interspersed with main code in a way
2870   that tends to minimize their run-time cost.
2871
2872   When FOOTERS is defined, in addition to range checking, we also
2873   verify footer fields of inuse chunks, which can be used guarantee
2874   that the mstate controlling malloc/free is intact.  This is a
2875   streamlined version of the approach described by William Robertson
2876   et al in "Run-time Detection of Heap-based Overflows" LISA'03
2877   http://www.usenix.org/events/lisa03/tech/robertson.html The footer
2878   of an inuse chunk holds the xor of its mstate and a random seed,
2879   that is checked upon calls to free() and realloc().  This is
2880   (probablistically) unguessable from outside the program, but can be
2881   computed by any code successfully malloc'ing any chunk, so does not
2882   itself provide protection against code that has already broken
2883   security through some other means.  Unlike Robertson et al, we
2884   always dynamically check addresses of all offset chunks (previous,
2885   next, etc). This turns out to be cheaper than relying on hashes.
2886 */
2887
2888 #if !INSECURE
2889 /* Check if address a is at least as high as any from MORECORE or MMAP */
2890 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
2891 /* Check if address of next chunk n is higher than base chunk p */
2892 #define ok_next(p, n)    ((char*)(p) < (char*)(n))
2893 /* Check if p has inuse status */
2894 #define ok_inuse(p)     is_inuse(p)
2895 /* Check if p has its pinuse bit on */
2896 #define ok_pinuse(p)     pinuse(p)
2897
2898 #else /* !INSECURE */
2899 #define ok_address(M, a) (1)
2900 #define ok_next(b, n)    (1)
2901 #define ok_inuse(p)      (1)
2902 #define ok_pinuse(p)     (1)
2903 #endif /* !INSECURE */
2904
2905 #if (FOOTERS && !INSECURE)
2906 /* Check if (alleged) mstate m has expected magic field */
2907 #define ok_magic(M)      ((M)->magic == mparams.magic)
2908 #else  /* (FOOTERS && !INSECURE) */
2909 #define ok_magic(M)      (1)
2910 #endif /* (FOOTERS && !INSECURE) */
2911
2912
2913 /* In gcc, use __builtin_expect to minimize impact of checks */
2914 #if !INSECURE
2915 #if defined(__GNUC__) && __GNUC__ >= 3
2916 #define RTCHECK(e)  __builtin_expect(e, 1)
2917 #else /* GNUC */
2918 #define RTCHECK(e)  (e)
2919 #endif /* GNUC */
2920 #else /* !INSECURE */
2921 #define RTCHECK(e)  (1)
2922 #endif /* !INSECURE */
2923
2924 /* macros to set up inuse chunks with or without footers */
2925
2926 #if !FOOTERS
2927
2928 #define mark_inuse_foot(M,p,s)
2929
2930 /* Macros for setting head/foot of non-mmapped chunks */
2931
2932 /* Set cinuse bit and pinuse bit of next chunk */
2933 #define set_inuse(M,p,s)\
2934   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2935   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2936
2937 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
2938 #define set_inuse_and_pinuse(M,p,s)\
2939   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2940   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2941
2942 /* Set size, cinuse and pinuse bit of this chunk */
2943 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2944   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
2945
2946 #else /* FOOTERS */
2947
2948 /* Set foot of inuse chunk to be xor of mstate and seed */
2949 #define mark_inuse_foot(M,p,s)\
2950   (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
2951
2952 #define get_mstate_for(p)\
2953   ((mstate)(((mchunkptr)((char*)(p) +\
2954     (chunksize(p))))->prev_foot ^ mparams.magic))
2955
2956 #define set_inuse(M,p,s)\
2957   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2958   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
2959   mark_inuse_foot(M,p,s))
2960
2961 #define set_inuse_and_pinuse(M,p,s)\
2962   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2963   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
2964  mark_inuse_foot(M,p,s))
2965
2966 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2967   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2968   mark_inuse_foot(M, p, s))
2969
2970 #endif /* !FOOTERS */
2971
2972 /* ---------------------------- setting mparams -------------------------- */
2973
2974 /* Initialize mparams */
2975 static int init_mparams(void) {
2976 #ifdef NEED_GLOBAL_LOCK_INIT
2977   if (malloc_global_mutex_status <= 0)
2978     init_malloc_global_mutex();
2979 #endif
2980
2981   ACQUIRE_MALLOC_GLOBAL_LOCK();
2982   if (mparams.magic == 0) {
2983     size_t magic;
2984     size_t psize;
2985     size_t gsize;
2986
2987 #ifndef WIN32
2988     psize = malloc_getpagesize;
2989     gsize = ((DEFAULT_GRANULARITY != 0)? DEFAULT_GRANULARITY : psize);
2990 #else /* WIN32 */
2991     {
2992       SYSTEM_INFO system_info;
2993       GetSystemInfo(&system_info);
2994       psize = system_info.dwPageSize;
2995       gsize = ((DEFAULT_GRANULARITY != 0)?
2996                DEFAULT_GRANULARITY : system_info.dwAllocationGranularity);
2997     }
2998 #endif /* WIN32 */
2999
3000     /* Sanity-check configuration:
3001        size_t must be unsigned and as wide as pointer type.
3002        ints must be at least 4 bytes.
3003        alignment must be at least 8.
3004        Alignment, min chunk size, and page size must all be powers of 2.
3005     */
3006     if ((sizeof(size_t) != sizeof(char*)) ||
3007         (MAX_SIZE_T < MIN_CHUNK_SIZE)  ||
3008         (sizeof(int) < 4)  ||
3009         (MALLOC_ALIGNMENT < (size_t)8U) ||
3010         ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
3011         ((MCHUNK_SIZE      & (MCHUNK_SIZE-SIZE_T_ONE))      != 0) ||
3012         ((gsize            & (gsize-SIZE_T_ONE))            != 0) ||
3013         ((psize            & (psize-SIZE_T_ONE))            != 0))
3014       ABORT;
3015
3016     mparams.granularity = gsize;
3017     mparams.page_size = psize;
3018     mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
3019     mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
3020 #if MORECORE_CONTIGUOUS
3021     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
3022 #else  /* MORECORE_CONTIGUOUS */
3023     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
3024 #endif /* MORECORE_CONTIGUOUS */
3025
3026 #if !ONLY_MSPACES
3027     /* Set up lock for main malloc area */
3028     gm->mflags = mparams.default_mflags;
3029     INITIAL_LOCK(&gm->mutex);
3030 #endif
3031
3032     {
3033 #if USE_DEV_RANDOM
3034       int fd;
3035       unsigned char buf[sizeof(size_t)];
3036       /* Try to use /dev/urandom, else fall back on using time */
3037       if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
3038           read(fd, buf, sizeof(buf)) == sizeof(buf)) {
3039         magic = *((size_t *) buf);
3040         close(fd);
3041       }
3042       else
3043 #endif /* USE_DEV_RANDOM */
3044 #ifdef WIN32
3045         magic = (size_t)(GetTickCount() ^ (size_t)0x55555555U);
3046 #else
3047         magic = (size_t)(time(0) ^ (size_t)0x55555555U);
3048 #endif
3049       magic |= (size_t)8U;    /* ensure nonzero */
3050       magic &= ~(size_t)7U;   /* improve chances of fault for bad values */
3051       mparams.magic = magic;
3052     }
3053   }
3054
3055   RELEASE_MALLOC_GLOBAL_LOCK();
3056   return 1;
3057 }
3058
3059 /* support for mallopt */
3060 static int change_mparam(int param_number, int value) {
3061   size_t val;
3062   ensure_initialization();
3063   val = (value == -1)? MAX_SIZE_T : (size_t)value;
3064   switch(param_number) {
3065   case M_TRIM_THRESHOLD:
3066     mparams.trim_threshold = val;
3067     return 1;
3068   case M_GRANULARITY:
3069     if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
3070       mparams.granularity = val;
3071       return 1;
3072     }
3073     else
3074       return 0;
3075   case M_MMAP_THRESHOLD:
3076     mparams.mmap_threshold = val;
3077     return 1;
3078   default:
3079     return 0;
3080   }
3081 }
3082
3083 #if DEBUG
3084 /* ------------------------- Debugging Support --------------------------- */
3085
3086 /* Check properties of any chunk, whether free, inuse, mmapped etc  */
3087 static void do_check_any_chunk(mstate m, mchunkptr p) {
3088   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3089   assert(ok_address(m, p));
3090 }
3091
3092 /* Check properties of top chunk */
3093 static void do_check_top_chunk(mstate m, mchunkptr p) {
3094   msegmentptr sp = segment_holding(m, (char*)p);
3095   size_t  sz = p->head & ~INUSE_BITS; /* third-lowest bit can be set! */
3096   assert(sp != 0);
3097   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3098   assert(ok_address(m, p));
3099   assert(sz == m->topsize);
3100   assert(sz > 0);
3101   assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
3102   assert(pinuse(p));
3103   assert(!pinuse(chunk_plus_offset(p, sz)));
3104 }
3105
3106 /* Check properties of (inuse) mmapped chunks */
3107 static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
3108   size_t  sz = chunksize(p);
3109   size_t len = (sz + (p->prev_foot) + MMAP_FOOT_PAD);
3110   assert(is_mmapped(p));
3111   assert(use_mmap(m));
3112   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
3113   assert(ok_address(m, p));
3114   assert(!is_small(sz));
3115   assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
3116   assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
3117   assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
3118 }
3119
3120 /* Check properties of inuse chunks */
3121 static void do_check_inuse_chunk(mstate m, mchunkptr p) {
3122   do_check_any_chunk(m, p);
3123   assert(is_inuse(p));
3124   assert(next_pinuse(p));
3125   /* If not pinuse and not mmapped, previous chunk has OK offset */
3126   assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
3127   if (is_mmapped(p))
3128     do_check_mmapped_chunk(m, p);
3129 }
3130
3131 /* Check properties of free chunks */
3132 static void do_check_free_chunk(mstate m, mchunkptr p) {
3133   size_t sz = chunksize(p);
3134   mchunkptr next = chunk_plus_offset(p, sz);
3135   do_check_any_chunk(m, p);
3136   assert(!is_inuse(p));
3137   assert(!next_pinuse(p));
3138   assert (!is_mmapped(p));
3139   if (p != m->dv && p != m->top) {
3140     if (sz >= MIN_CHUNK_SIZE) {
3141       assert((sz & CHUNK_ALIGN_MASK) == 0);
3142       assert(is_aligned(chunk2mem(p)));
3143       assert(next->prev_foot == sz);
3144       assert(pinuse(p));
3145       assert (next == m->top || is_inuse(next));
3146       assert(p->fd->bk == p);
3147       assert(p->bk->fd == p);
3148     }
3149     else  /* markers are always of size SIZE_T_SIZE */
3150       assert(sz == SIZE_T_SIZE);
3151   }
3152 }
3153
3154 /* Check properties of malloced chunks at the point they are malloced */
3155 static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
3156   if (mem != 0) {
3157     mchunkptr p = mem2chunk(mem);
3158     size_t sz = p->head & ~INUSE_BITS;
3159     do_check_inuse_chunk(m, p);
3160     assert((sz & CHUNK_ALIGN_MASK) == 0);
3161     assert(sz >= MIN_CHUNK_SIZE);
3162     assert(sz >= s);
3163     /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
3164     assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
3165   }
3166 }
3167
3168 /* Check a tree and its subtrees.  */
3169 static void do_check_tree(mstate m, tchunkptr t) {
3170   tchunkptr head = 0;
3171   tchunkptr u = t;
3172   bindex_t tindex = t->index;
3173   size_t tsize = chunksize(t);
3174   bindex_t idx;
3175   compute_tree_index(tsize, idx);
3176   assert(tindex == idx);
3177   assert(tsize >= MIN_LARGE_SIZE);
3178   assert(tsize >= minsize_for_tree_index(idx));
3179   assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
3180
3181   do { /* traverse through chain of same-sized nodes */
3182     do_check_any_chunk(m, ((mchunkptr)u));
3183     assert(u->index == tindex);
3184     assert(chunksize(u) == tsize);
3185     assert(!is_inuse(u));
3186     assert(!next_pinuse(u));
3187     assert(u->fd->bk == u);
3188     assert(u->bk->fd == u);
3189     if (u->parent == 0) {
3190       assert(u->child[0] == 0);
3191       assert(u->child[1] == 0);
3192     }
3193     else {
3194       assert(head == 0); /* only one node on chain has parent */
3195       head = u;
3196       assert(u->parent != u);
3197       assert (u->parent->child[0] == u ||
3198               u->parent->child[1] == u ||
3199               *((tbinptr*)(u->parent)) == u);
3200       if (u->child[0] != 0) {
3201         assert(u->child[0]->parent == u);
3202         assert(u->child[0] != u);
3203         do_check_tree(m, u->child[0]);
3204       }
3205       if (u->child[1] != 0) {
3206         assert(u->child[1]->parent == u);
3207         assert(u->child[1] != u);
3208         do_check_tree(m, u->child[1]);
3209       }
3210       if (u->child[0] != 0 && u->child[1] != 0) {
3211         assert(chunksize(u->child[0]) < chunksize(u->child[1]));
3212       }
3213     }
3214     u = u->fd;
3215   } while (u != t);
3216   assert(head != 0);
3217 }
3218
3219 /*  Check all the chunks in a treebin.  */
3220 static void do_check_treebin(mstate m, bindex_t i) {
3221   tbinptr* tb = treebin_at(m, i);
3222   tchunkptr t = *tb;
3223   int empty = (m->treemap & (1U << i)) == 0;
3224   if (t == 0)
3225     assert(empty);
3226   if (!empty)
3227     do_check_tree(m, t);
3228 }
3229
3230 /*  Check all the chunks in a smallbin.  */
3231 static void do_check_smallbin(mstate m, bindex_t i) {
3232   sbinptr b = smallbin_at(m, i);
3233   mchunkptr p = b->bk;
3234   unsigned int empty = (m->smallmap & (1U << i)) == 0;
3235   if (p == b)
3236     assert(empty);
3237   if (!empty) {
3238     for (; p != b; p = p->bk) {
3239       size_t size = chunksize(p);
3240       mchunkptr q;
3241       /* each chunk claims to be free */
3242       do_check_free_chunk(m, p);
3243       /* chunk belongs in bin */
3244       assert(small_index(size) == i);
3245       assert(p->bk == b || chunksize(p->bk) == chunksize(p));
3246       /* chunk is followed by an inuse chunk */
3247       q = next_chunk(p);
3248       if (q->head != FENCEPOST_HEAD)
3249         do_check_inuse_chunk(m, q);
3250     }
3251   }
3252 }
3253
3254 /* Find x in a bin. Used in other check functions. */
3255 static int bin_find(mstate m, mchunkptr x) {
3256   size_t size = chunksize(x);
3257   if (is_small(size)) {
3258     bindex_t sidx = small_index(size);
3259     sbinptr b = smallbin_at(m, sidx);
3260     if (smallmap_is_marked(m, sidx)) {
3261       mchunkptr p = b;
3262       do {
3263         if (p == x)
3264           return 1;
3265       } while ((p = p->fd) != b);
3266     }
3267   }
3268   else {
3269     bindex_t tidx;
3270     compute_tree_index(size, tidx);
3271     if (treemap_is_marked(m, tidx)) {
3272       tchunkptr t = *treebin_at(m, tidx);
3273       size_t sizebits = size << leftshift_for_tree_index(tidx);
3274       while (t != 0 && chunksize(t) != size) {
3275         t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
3276         sizebits <<= 1;
3277       }
3278       if (t != 0) {
3279         tchunkptr u = t;
3280         do {
3281           if (u == (tchunkptr)x)
3282             return 1;
3283         } while ((u = u->fd) != t);
3284       }
3285     }
3286   }
3287   return 0;
3288 }
3289
3290 /* Traverse each chunk and check it; return total */
3291 static size_t traverse_and_check(mstate m) {
3292   size_t sum = 0;
3293   if (is_initialized(m)) {
3294     msegmentptr s = &m->seg;
3295     sum += m->topsize + TOP_FOOT_SIZE;
3296     while (s != 0) {
3297       mchunkptr q = align_as_chunk(s->base);
3298       mchunkptr lastq = 0;
3299       assert(pinuse(q));
3300       while (segment_holds(s, q) &&
3301              q != m->top && q->head != FENCEPOST_HEAD) {
3302         sum += chunksize(q);
3303         if (is_inuse(q)) {
3304           assert(!bin_find(m, q));
3305           do_check_inuse_chunk(m, q);
3306         }
3307         else {
3308           assert(q == m->dv || bin_find(m, q));
3309           assert(lastq == 0 || is_inuse(lastq)); /* Not 2 consecutive free */
3310           do_check_free_chunk(m, q);
3311         }
3312         lastq = q;
3313         q = next_chunk(q);
3314       }
3315       s = s->next;
3316     }
3317   }
3318   return sum;
3319 }
3320
3321 /* Check all properties of malloc_state. */
3322 static void do_check_malloc_state(mstate m) {
3323   bindex_t i;
3324   size_t total;
3325   /* check bins */
3326   for (i = 0; i < NSMALLBINS; ++i)
3327     do_check_smallbin(m, i);
3328   for (i = 0; i < NTREEBINS; ++i)
3329     do_check_treebin(m, i);
3330
3331   if (m->dvsize != 0) { /* check dv chunk */
3332     do_check_any_chunk(m, m->dv);
3333     assert(m->dvsize == chunksize(m->dv));
3334     assert(m->dvsize >= MIN_CHUNK_SIZE);
3335     assert(bin_find(m, m->dv) == 0);
3336   }
3337
3338   if (m->top != 0) {   /* check top chunk */
3339     do_check_top_chunk(m, m->top);
3340     /*assert(m->topsize == chunksize(m->top)); redundant */
3341     assert(m->topsize > 0);
3342     assert(bin_find(m, m->top) == 0);
3343   }
3344
3345   total = traverse_and_check(m);
3346   assert(total <= m->footprint);
3347   assert(m->footprint <= m->max_footprint);
3348 }
3349 #endif /* DEBUG */
3350
3351 /* ----------------------------- statistics ------------------------------ */
3352
3353 #if !NO_MALLINFO
3354 static struct mallinfo internal_mallinfo(mstate m) {
3355   struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
3356   ensure_initialization();
3357   if (!PREACTION(m)) {
3358     check_malloc_state(m);
3359     if (is_initialized(m)) {
3360       size_t nfree = SIZE_T_ONE; /* top always free */
3361       size_t mfree = m->topsize + TOP_FOOT_SIZE;
3362       size_t sum = mfree;
3363       msegmentptr s = &m->seg;
3364       while (s != 0) {
3365         mchunkptr q = align_as_chunk(s->base);
3366         while (segment_holds(s, q) &&
3367                q != m->top && q->head != FENCEPOST_HEAD) {
3368           size_t sz = chunksize(q);
3369           sum += sz;
3370           if (!is_inuse(q)) {
3371             mfree += sz;
3372             ++nfree;
3373           }
3374           q = next_chunk(q);
3375         }
3376         s = s->next;
3377       }
3378
3379       nm.arena    = sum;
3380       nm.ordblks  = nfree;
3381       nm.hblkhd   = m->footprint - sum;
3382       nm.usmblks  = m->max_footprint;
3383       nm.uordblks = m->footprint - mfree;
3384       nm.fordblks = mfree;
3385       nm.keepcost = m->topsize;
3386     }
3387
3388     POSTACTION(m);
3389   }
3390   return nm;
3391 }
3392 #endif /* !NO_MALLINFO */
3393
3394 static void internal_malloc_stats(mstate m) {
3395   ensure_initialization();
3396   if (!PREACTION(m)) {
3397     size_t maxfp = 0;
3398     size_t fp = 0;
3399     size_t used = 0;
3400     check_malloc_state(m);
3401     if (is_initialized(m)) {
3402       msegmentptr s = &m->seg;
3403       maxfp = m->max_footprint;
3404       fp = m->footprint;
3405       used = fp - (m->topsize + TOP_FOOT_SIZE);
3406
3407       while (s != 0) {
3408         mchunkptr q = align_as_chunk(s->base);
3409         while (segment_holds(s, q) &&
3410                q != m->top && q->head != FENCEPOST_HEAD) {
3411           if (!is_inuse(q))
3412             used -= chunksize(q);
3413           q = next_chunk(q);
3414         }
3415         s = s->next;
3416       }
3417     }
3418
3419     fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
3420     fprintf(stderr, "system bytes     = %10lu\n", (unsigned long)(fp));
3421     fprintf(stderr, "in use bytes     = %10lu\n", (unsigned long)(used));
3422
3423     POSTACTION(m);
3424   }
3425 }
3426
3427 /* ----------------------- Operations on smallbins ----------------------- */
3428
3429 /*
3430   Various forms of linking and unlinking are defined as macros.  Even
3431   the ones for trees, which are very long but have very short typical
3432   paths.  This is ugly but reduces reliance on inlining support of
3433   compilers.
3434 */
3435
3436 /* Link a free chunk into a smallbin  */
3437 #define insert_small_chunk(M, P, S) {\
3438   bindex_t I  = small_index(S);\
3439   mchunkptr B = smallbin_at(M, I);\
3440   mchunkptr F = B;\
3441   assert(S >= MIN_CHUNK_SIZE);\
3442   if (!smallmap_is_marked(M, I))\
3443     mark_smallmap(M, I);\
3444   else if (RTCHECK(ok_address(M, B->fd)))\
3445     F = B->fd;\
3446   else {\
3447     CORRUPTION_ERROR_ACTION(M);\
3448   }\
3449   B->fd = P;\
3450   F->bk = P;\
3451   P->fd = F;\
3452   P->bk = B;\
3453 }
3454
3455 /* Unlink a chunk from a smallbin  */
3456 #define unlink_small_chunk(M, P, S) {\
3457   mchunkptr F = P->fd;\
3458   mchunkptr B = P->bk;\
3459   bindex_t I = small_index(S);\
3460   assert(P != B);\
3461   assert(P != F);\
3462   assert(chunksize(P) == small_index2size(I));\
3463   if (F == B)\
3464     clear_smallmap(M, I);\
3465   else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
3466                    (B == smallbin_at(M,I) || ok_address(M, B)))) {\
3467     F->bk = B;\
3468     B->fd = F;\
3469   }\
3470   else {\
3471     CORRUPTION_ERROR_ACTION(M);\
3472   }\
3473 }
3474
3475 /* Unlink the first chunk from a smallbin */
3476 #define unlink_first_small_chunk(M, B, P, I) {\
3477   mchunkptr F = P->fd;\
3478   assert(P != B);\
3479   assert(P != F);\
3480   assert(chunksize(P) == small_index2size(I));\
3481   if (B == F)\
3482     clear_smallmap(M, I);\
3483   else if (RTCHECK(ok_address(M, F))) {\
3484     B->fd = F;\
3485     F->bk = B;\
3486   }\
3487   else {\
3488     CORRUPTION_ERROR_ACTION(M);\
3489   }\
3490 }
3491
3492