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