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