]> pd.if.org Git - pdclib/blob - functions/_dlmalloc/dlmalloc.c
33e393bbfdd311be1aa2ee4108d354483b77d2b2
[pdclib] / functions / _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             aligned_alloc\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 #if 0 // Redeclaration warnings as PDCLib already declares these in <stdio.h>\r
839 \r
840 /*\r
841   malloc(size_t n)\r
842   Returns a pointer to a newly allocated chunk of at least n bytes, or\r
843   null if no space is available, in which case errno is set to ENOMEM\r
844   on ANSI C systems.\r
845 \r
846   If n is zero, malloc returns a minimum-sized chunk. (The minimum\r
847   size is 16 bytes on most 32bit systems, and 32 bytes on 64bit\r
848   systems.)  Note that size_t is an unsigned type, so calls with\r
849   arguments that would be negative if signed are interpreted as\r
850   requests for huge amounts of space, which will often fail. The\r
851   maximum supported value of n differs across systems, but is in all\r
852   cases less than the maximum representable value of a size_t.\r
853 */\r
854 DLMALLOC_EXPORT void* dlmalloc(size_t);\r
855 \r
856 /*\r
857   free(void* p)\r
858   Releases the chunk of memory pointed to by p, that had been previously\r
859   allocated using malloc or a related routine such as realloc.\r
860   It has no effect if p is null. If p was not malloced or already\r
861   freed, free(p) will by default cause the current program to abort.\r
862 */\r
863 DLMALLOC_EXPORT void  dlfree(void*);\r
864 \r
865 /*\r
866   calloc(size_t n_elements, size_t element_size);\r
867   Returns a pointer to n_elements * element_size bytes, with all locations\r
868   set to zero.\r
869 */\r
870 DLMALLOC_EXPORT void* dlcalloc(size_t, size_t);\r
871 \r
872 /*\r
873   realloc(void* p, size_t n)\r
874   Returns a pointer to a chunk of size n that contains the same data\r
875   as does chunk p up to the minimum of (n, p's size) bytes, or null\r
876   if no space is available.\r
877 \r
878   The returned pointer may or may not be the same as p. The algorithm\r
879   prefers extending p in most cases when possible, otherwise it\r
880   employs the equivalent of a malloc-copy-free sequence.\r
881 \r
882   If p is null, realloc is equivalent to malloc.\r
883 \r
884   If space is not available, realloc returns null, errno is set (if on\r
885   ANSI) and p is NOT freed.\r
886 \r
887   if n is for fewer bytes than already held by p, the newly unused\r
888   space is lopped off and freed if possible.  realloc with a size\r
889   argument of zero (re)allocates a minimum-sized chunk.\r
890 \r
891   The old unix realloc convention of allowing the last-free'd chunk\r
892   to be used as an argument to realloc is not supported.\r
893 */\r
894 DLMALLOC_EXPORT void* dlrealloc(void*, size_t);\r
895 \r
896 #endif\r
897 \r
898 /*\r
899   realloc_in_place(void* p, size_t n)\r
900   Resizes the space allocated for p to size n, only if this can be\r
901   done without moving p (i.e., only if there is adjacent space\r
902   available if n is greater than p's current allocated size, or n is\r
903   less than or equal to p's size). This may be used instead of plain\r
904   realloc if an alternative allocation strategy is needed upon failure\r
905   to expand space; for example, reallocation of a buffer that must be\r
906   memory-aligned or cleared. You can use realloc_in_place to trigger\r
907   these alternatives only when needed.\r
908 \r
909   Returns p if successful; otherwise null.\r
910 */\r
911 DLMALLOC_EXPORT void* dlrealloc_in_place(void*, size_t);\r
912 \r
913 #if 0 // Redeclaration warnings as PDCLib already declares these in <stdio.h>\r
914 \r
915 /*\r
916   memalign(size_t alignment, size_t n);\r
917   Returns a pointer to a newly allocated chunk of n bytes, aligned\r
918   in accord with the alignment argument.\r
919 \r
920   The alignment argument should be a power of two. If the argument is\r
921   not a power of two, the nearest greater power is used.\r
922   8-byte alignment is guaranteed by normal malloc calls, so don't\r
923   bother calling memalign with an argument of 8 or less.\r
924 \r
925   Overreliance on memalign is a sure way to fragment space.\r
926 */\r
927 DLMALLOC_EXPORT void* dlmemalign(size_t, size_t);\r
928 \r
929 #endif\r
930 \r
931 /*\r
932   int posix_memalign(void** pp, size_t alignment, size_t n);\r
933   Allocates a chunk of n bytes, aligned in accord with the alignment\r
934   argument. Differs from memalign only in that it (1) assigns the\r
935   allocated memory to *pp rather than returning it, (2) fails and\r
936   returns EINVAL if the alignment is not a power of two (3) fails and\r
937   returns ENOMEM if memory cannot be allocated.\r
938 */\r
939 DLMALLOC_EXPORT int dlposix_memalign(void**, size_t, size_t);\r
940 \r
941 /*\r
942   valloc(size_t n);\r
943   Equivalent to memalign(pagesize, n), where pagesize is the page\r
944   size of the system. If the pagesize is unknown, 4096 is used.\r
945 */\r
946 DLMALLOC_EXPORT void* dlvalloc(size_t);\r
947 \r
948 /*\r
949   mallopt(int parameter_number, int parameter_value)\r
950   Sets tunable parameters The format is to provide a\r
951   (parameter-number, parameter-value) pair.  mallopt then sets the\r
952   corresponding parameter to the argument value if it can (i.e., so\r
953   long as the value is meaningful), and returns 1 if successful else\r
954   0.  To workaround the fact that mallopt is specified to use int,\r
955   not size_t parameters, the value -1 is specially treated as the\r
956   maximum unsigned size_t value.\r
957 \r
958   SVID/XPG/ANSI defines four standard param numbers for mallopt,\r
959   normally defined in malloc.h.  None of these are use in this malloc,\r
960   so setting them has no effect. But this malloc also supports other\r
961   options in mallopt. See below for details.  Briefly, supported\r
962   parameters are as follows (listed defaults are for "typical"\r
963   configurations).\r
964 \r
965   Symbol            param #  default    allowed param values\r
966   M_TRIM_THRESHOLD     -1   2*1024*1024   any   (-1 disables)\r
967   M_GRANULARITY        -2     page size   any power of 2 >= page size\r
968   M_MMAP_THRESHOLD     -3      256*1024   any   (or 0 if no MMAP support)\r
969 */\r
970 DLMALLOC_EXPORT int dlmallopt(int, int);\r
971 \r
972 /*\r
973   malloc_footprint();\r
974   Returns the number of bytes obtained from the system.  The total\r
975   number of bytes allocated by malloc, realloc etc., is less than this\r
976   value. Unlike mallinfo, this function returns only a precomputed\r
977   result, so can be called frequently to monitor memory consumption.\r
978   Even if locks are otherwise defined, this function does not use them,\r
979   so results might not be up to date.\r
980 */\r
981 DLMALLOC_EXPORT size_t dlmalloc_footprint(void);\r
982 \r
983 /*\r
984   malloc_max_footprint();\r
985   Returns the maximum number of bytes obtained from the system. This\r
986   value will be greater than current footprint if deallocated space\r
987   has been reclaimed by the system. The peak number of bytes allocated\r
988   by malloc, realloc etc., is less than this value. Unlike mallinfo,\r
989   this function returns only a precomputed result, so can be called\r
990   frequently to monitor memory consumption.  Even if locks are\r
991   otherwise defined, this function does not use them, so results might\r
992   not be up to date.\r
993 */\r
994 DLMALLOC_EXPORT size_t dlmalloc_max_footprint(void);\r
995 \r
996 /*\r
997   malloc_footprint_limit();\r
998   Returns the number of bytes that the heap is allowed to obtain from\r
999   the system, returning the last value returned by\r
1000   malloc_set_footprint_limit, or the maximum size_t value if\r
1001   never set. The returned value reflects a permission. There is no\r
1002   guarantee that this number of bytes can actually be obtained from\r
1003   the system.\r
1004 */\r
1005 DLMALLOC_EXPORT size_t dlmalloc_footprint_limit(void);\r
1006 \r
1007 /*\r
1008   malloc_set_footprint_limit();\r
1009   Sets the maximum number of bytes to obtain from the system, causing\r
1010   failure returns from malloc and related functions upon attempts to\r
1011   exceed this value. The argument value may be subject to page\r
1012   rounding to an enforceable limit; this actual value is returned.\r
1013   Using an argument of the maximum possible size_t effectively\r
1014   disables checks. If the argument is less than or equal to the\r
1015   current malloc_footprint, then all future allocations that require\r
1016   additional system memory will fail. However, invocation cannot\r
1017   retroactively deallocate existing used memory.\r
1018 */\r
1019 DLMALLOC_EXPORT size_t dlmalloc_set_footprint_limit(size_t bytes);\r
1020 \r
1021 #if MALLOC_INSPECT_ALL\r
1022 /*\r
1023   malloc_inspect_all(void(*handler)(void *start,\r
1024                                     void *end,\r
1025                                     size_t used_bytes,\r
1026                                     void* callback_arg),\r
1027                       void* arg);\r
1028   Traverses the heap and calls the given handler for each managed\r
1029   region, skipping all bytes that are (or may be) used for bookkeeping\r
1030   purposes.  Traversal does not include include chunks that have been\r
1031   directly memory mapped. Each reported region begins at the start\r
1032   address, and continues up to but not including the end address.  The\r
1033   first used_bytes of the region contain allocated data. If\r
1034   used_bytes is zero, the region is unallocated. The handler is\r
1035   invoked with the given callback argument. If locks are defined, they\r
1036   are held during the entire traversal. It is a bad idea to invoke\r
1037   other malloc functions from within the handler.\r
1038 \r
1039   For example, to count the number of in-use chunks with size greater\r
1040   than 1000, you could write:\r
1041   static int count = 0;\r
1042   void count_chunks(void* start, void* end, size_t used, void* arg) {\r
1043     if (used >= 1000) ++count;\r
1044   }\r
1045   then:\r
1046     malloc_inspect_all(count_chunks, NULL);\r
1047 \r
1048   malloc_inspect_all is compiled only if MALLOC_INSPECT_ALL is defined.\r
1049 */\r
1050 DLMALLOC_EXPORT void dlmalloc_inspect_all(void(*handler)(void*, void *, size_t, void*),\r
1051                            void* arg);\r
1052 \r
1053 #endif /* MALLOC_INSPECT_ALL */\r
1054 \r
1055 #if !NO_MALLINFO\r
1056 /*\r
1057   mallinfo()\r
1058   Returns (by copy) a struct containing various summary statistics:\r
1059 \r
1060   arena:     current total non-mmapped bytes allocated from system\r
1061   ordblks:   the number of free chunks\r
1062   smblks:    always zero.\r
1063   hblks:     current number of mmapped regions\r
1064   hblkhd:    total bytes held in mmapped regions\r
1065   usmblks:   the maximum total allocated space. This will be greater\r
1066                 than current total if trimming has occurred.\r
1067   fsmblks:   always zero\r
1068   uordblks:  current total allocated space (normal or mmapped)\r
1069   fordblks:  total free space\r
1070   keepcost:  the maximum number of bytes that could ideally be released\r
1071                back to system via malloc_trim. ("ideally" means that\r
1072                it ignores page restrictions etc.)\r
1073 \r
1074   Because these fields are ints, but internal bookkeeping may\r
1075   be kept as longs, the reported values may wrap around zero and\r
1076   thus be inaccurate.\r
1077 */\r
1078 DLMALLOC_EXPORT struct mallinfo dlmallinfo(void);\r
1079 #endif /* NO_MALLINFO */\r
1080 \r
1081 /*\r
1082   independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);\r
1083 \r
1084   independent_calloc is similar to calloc, but instead of returning a\r
1085   single cleared space, it returns an array of pointers to n_elements\r
1086   independent elements that can hold contents of size elem_size, each\r
1087   of which starts out cleared, and can be independently freed,\r
1088   realloc'ed etc. The elements are guaranteed to be adjacently\r
1089   allocated (this is not guaranteed to occur with multiple callocs or\r
1090   mallocs), which may also improve cache locality in some\r
1091   applications.\r
1092 \r
1093   The "chunks" argument is optional (i.e., may be null, which is\r
1094   probably the most typical usage). If it is null, the returned array\r
1095   is itself dynamically allocated and should also be freed when it is\r
1096   no longer needed. Otherwise, the chunks array must be of at least\r
1097   n_elements in length. It is filled in with the pointers to the\r
1098   chunks.\r
1099 \r
1100   In either case, independent_calloc returns this pointer array, or\r
1101   null if the allocation failed.  If n_elements is zero and "chunks"\r
1102   is null, it returns a chunk representing an array with zero elements\r
1103   (which should be freed if not wanted).\r
1104 \r
1105   Each element must be freed when it is no longer needed. This can be\r
1106   done all at once using bulk_free.\r
1107 \r
1108   independent_calloc simplifies and speeds up implementations of many\r
1109   kinds of pools.  It may also be useful when constructing large data\r
1110   structures that initially have a fixed number of fixed-sized nodes,\r
1111   but the number is not known at compile time, and some of the nodes\r
1112   may later need to be freed. For example:\r
1113 \r
1114   struct Node { int item; struct Node* next; };\r
1115 \r
1116   struct Node* build_list() {\r
1117     struct Node** pool;\r
1118     int n = read_number_of_nodes_needed();\r
1119     if (n <= 0) return 0;\r
1120     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);\r
1121     if (pool == 0) die();\r
1122     // organize into a linked list...\r
1123     struct Node* first = pool[0];\r
1124     for (i = 0; i < n-1; ++i)\r
1125       pool[i]->next = pool[i+1];\r
1126     free(pool);     // Can now free the array (or not, if it is needed later)\r
1127     return first;\r
1128   }\r
1129 */\r
1130 DLMALLOC_EXPORT void** dlindependent_calloc(size_t, size_t, void**);\r
1131 \r
1132 /*\r
1133   independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);\r
1134 \r
1135   independent_comalloc allocates, all at once, a set of n_elements\r
1136   chunks with sizes indicated in the "sizes" array.    It returns\r
1137   an array of pointers to these elements, each of which can be\r
1138   independently freed, realloc'ed etc. The elements are guaranteed to\r
1139   be adjacently allocated (this is not guaranteed to occur with\r
1140   multiple callocs or mallocs), which may also improve cache locality\r
1141   in some applications.\r
1142 \r
1143   The "chunks" argument is optional (i.e., may be null). If it is null\r
1144   the returned array is itself dynamically allocated and should also\r
1145   be freed when it is no longer needed. Otherwise, the chunks array\r
1146   must be of at least n_elements in length. It is filled in with the\r
1147   pointers to the chunks.\r
1148 \r
1149   In either case, independent_comalloc returns this pointer array, or\r
1150   null if the allocation failed.  If n_elements is zero and chunks is\r
1151   null, it returns a chunk representing an array with zero elements\r
1152   (which should be freed if not wanted).\r
1153 \r
1154   Each element must be freed when it is no longer needed. This can be\r
1155   done all at once using bulk_free.\r
1156 \r
1157   independent_comallac differs from independent_calloc in that each\r
1158   element may have a different size, and also that it does not\r
1159   automatically clear elements.\r
1160 \r
1161   independent_comalloc can be used to speed up allocation in cases\r
1162   where several structs or objects must always be allocated at the\r
1163   same time.  For example:\r
1164 \r
1165   struct Head { ... }\r
1166   struct Foot { ... }\r
1167 \r
1168   void send_message(char* msg) {\r
1169     int msglen = strlen(msg);\r
1170     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };\r
1171     void* chunks[3];\r
1172     if (independent_comalloc(3, sizes, chunks) == 0)\r
1173       die();\r
1174     struct Head* head = (struct Head*)(chunks[0]);\r
1175     char*        body = (char*)(chunks[1]);\r
1176     struct Foot* foot = (struct Foot*)(chunks[2]);\r
1177     // ...\r
1178   }\r
1179 \r
1180   In general though, independent_comalloc is worth using only for\r
1181   larger values of n_elements. For small values, you probably won't\r
1182   detect enough difference from series of malloc calls to bother.\r
1183 \r
1184   Overuse of independent_comalloc can increase overall memory usage,\r
1185   since it cannot reuse existing noncontiguous small chunks that\r
1186   might be available for some of the elements.\r
1187 */\r
1188 DLMALLOC_EXPORT void** dlindependent_comalloc(size_t, size_t*, void**);\r
1189 \r
1190 /*\r
1191   bulk_free(void* array[], size_t n_elements)\r
1192   Frees and clears (sets to null) each non-null pointer in the given\r
1193   array.  This is likely to be faster than freeing them one-by-one.\r
1194   If footers are used, pointers that have been allocated in different\r
1195   mspaces are not freed or cleared, and the count of all such pointers\r
1196   is returned.  For large arrays of pointers with poor locality, it\r
1197   may be worthwhile to sort this array before calling bulk_free.\r
1198 */\r
1199 DLMALLOC_EXPORT size_t  dlbulk_free(void**, size_t n_elements);\r
1200 \r
1201 /*\r
1202   pvalloc(size_t n);\r
1203   Equivalent to valloc(minimum-page-that-holds(n)), that is,\r
1204   round up n to nearest pagesize.\r
1205  */\r
1206 DLMALLOC_EXPORT void*  dlpvalloc(size_t);\r
1207 \r
1208 /*\r
1209   malloc_trim(size_t pad);\r
1210 \r
1211   If possible, gives memory back to the system (via negative arguments\r
1212   to sbrk) if there is unused memory at the `high' end of the malloc\r
1213   pool or in unused MMAP segments. You can call this after freeing\r
1214   large blocks of memory to potentially reduce the system-level memory\r
1215   requirements of a program. However, it cannot guarantee to reduce\r
1216   memory. Under some allocation patterns, some large free blocks of\r
1217   memory will be locked between two used chunks, so they cannot be\r
1218   given back to the system.\r
1219 \r
1220   The `pad' argument to malloc_trim represents the amount of free\r
1221   trailing space to leave untrimmed. If this argument is zero, only\r
1222   the minimum amount of memory to maintain internal data structures\r
1223   will be left. Non-zero arguments can be supplied to maintain enough\r
1224   trailing space to service future expected allocations without having\r
1225   to re-obtain memory from the system.\r
1226 \r
1227   Malloc_trim returns 1 if it actually released any memory, else 0.\r
1228 */\r
1229 DLMALLOC_EXPORT int  dlmalloc_trim(size_t);\r
1230 \r
1231 /*\r
1232   malloc_stats();\r
1233   Prints on stderr the amount of space obtained from the system (both\r
1234   via sbrk and mmap), the maximum amount (which may be more than\r
1235   current if malloc_trim and/or munmap got called), and the current\r
1236   number of bytes allocated via malloc (or realloc, etc) but not yet\r
1237   freed. Note that this is the number of bytes allocated, not the\r
1238   number requested. It will be larger than the number requested\r
1239   because of alignment and bookkeeping overhead. Because it includes\r
1240   alignment wastage as being in use, this figure may be greater than\r
1241   zero even when no user-level chunks are allocated.\r
1242 \r
1243   The reported current and maximum system memory can be inaccurate if\r
1244   a program makes other calls to system memory allocation functions\r
1245   (normally sbrk) outside of malloc.\r
1246 \r
1247   malloc_stats prints only the most commonly interesting statistics.\r
1248   More information can be obtained by calling mallinfo.\r
1249 */\r
1250 DLMALLOC_EXPORT void  dlmalloc_stats(void);\r
1251 \r
1252 #endif /* ONLY_MSPACES */\r
1253 \r
1254 /*\r
1255   malloc_usable_size(void* p);\r
1256 \r
1257   Returns the number of bytes you can actually use in\r
1258   an allocated chunk, which may be more than you requested (although\r
1259   often not) due to alignment and minimum size constraints.\r
1260   You can use this many bytes without worrying about\r
1261   overwriting other allocated objects. This is not a particularly great\r
1262   programming practice. malloc_usable_size can be more useful in\r
1263   debugging and assertions, for example:\r
1264 \r
1265   p = malloc(n);\r
1266   assert(malloc_usable_size(p) >= 256);\r
1267 */\r
1268 size_t dlmalloc_usable_size(void*);\r
1269 \r
1270 #if MSPACES\r
1271 \r
1272 /*\r
1273   mspace is an opaque type representing an independent\r
1274   region of space that supports mspace_malloc, etc.\r
1275 */\r
1276 typedef void* mspace;\r
1277 \r
1278 /*\r
1279   create_mspace creates and returns a new independent space with the\r
1280   given initial capacity, or, if 0, the default granularity size.  It\r
1281   returns null if there is no system memory available to create the\r
1282   space.  If argument locked is non-zero, the space uses a separate\r
1283   lock to control access. The capacity of the space will grow\r
1284   dynamically as needed to service mspace_malloc requests.  You can\r
1285   control the sizes of incremental increases of this space by\r
1286   compiling with a different DEFAULT_GRANULARITY or dynamically\r
1287   setting with mallopt(M_GRANULARITY, value).\r
1288 */\r
1289 DLMALLOC_EXPORT mspace create_mspace(size_t capacity, int locked);\r
1290 \r
1291 /*\r
1292   destroy_mspace destroys the given space, and attempts to return all\r
1293   of its memory back to the system, returning the total number of\r
1294   bytes freed. After destruction, the results of access to all memory\r
1295   used by the space become undefined.\r
1296 */\r
1297 DLMALLOC_EXPORT size_t destroy_mspace(mspace msp);\r
1298 \r
1299 /*\r
1300   create_mspace_with_base uses the memory supplied as the initial base\r
1301   of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this\r
1302   space is used for bookkeeping, so the capacity must be at least this\r
1303   large. (Otherwise 0 is returned.) When this initial space is\r
1304   exhausted, additional memory will be obtained from the system.\r
1305   Destroying this space will deallocate all additionally allocated\r
1306   space (if possible) but not the initial base.\r
1307 */\r
1308 DLMALLOC_EXPORT mspace create_mspace_with_base(void* base, size_t capacity, int locked);\r
1309 \r
1310 /*\r
1311   mspace_track_large_chunks controls whether requests for large chunks\r
1312   are allocated in their own untracked mmapped regions, separate from\r
1313   others in this mspace. By default large chunks are not tracked,\r
1314   which reduces fragmentation. However, such chunks are not\r
1315   necessarily released to the system upon destroy_mspace.  Enabling\r
1316   tracking by setting to true may increase fragmentation, but avoids\r
1317   leakage when relying on destroy_mspace to release all memory\r
1318   allocated using this space.  The function returns the previous\r
1319   setting.\r
1320 */\r
1321 DLMALLOC_EXPORT int mspace_track_large_chunks(mspace msp, int enable);\r
1322 \r
1323 \r
1324 /*\r
1325   mspace_malloc behaves as malloc, but operates within\r
1326   the given space.\r
1327 */\r
1328 DLMALLOC_EXPORT void* mspace_malloc(mspace msp, size_t bytes);\r
1329 \r
1330 /*\r
1331   mspace_free behaves as free, but operates within\r
1332   the given space.\r
1333 \r
1334   If compiled with FOOTERS==1, mspace_free is not actually needed.\r
1335   free may be called instead of mspace_free because freed chunks from\r
1336   any space are handled by their originating spaces.\r
1337 */\r
1338 DLMALLOC_EXPORT void mspace_free(mspace msp, void* mem);\r
1339 \r
1340 /*\r
1341   mspace_realloc behaves as realloc, but operates within\r
1342   the given space.\r
1343 \r
1344   If compiled with FOOTERS==1, mspace_realloc is not actually\r
1345   needed.  realloc may be called instead of mspace_realloc because\r
1346   realloced chunks from any space are handled by their originating\r
1347   spaces.\r
1348 */\r
1349 DLMALLOC_EXPORT void* mspace_realloc(mspace msp, void* mem, size_t newsize);\r
1350 \r
1351 /*\r
1352   mspace_calloc behaves as calloc, but operates within\r
1353   the given space.\r
1354 */\r
1355 DLMALLOC_EXPORT void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);\r
1356 \r
1357 /*\r
1358   mspace_memalign behaves as memalign, but operates within\r
1359   the given space.\r
1360 */\r
1361 DLMALLOC_EXPORT void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);\r
1362 \r
1363 /*\r
1364   mspace_independent_calloc behaves as independent_calloc, but\r
1365   operates within the given space.\r
1366 */\r
1367 DLMALLOC_EXPORT void** mspace_independent_calloc(mspace msp, size_t n_elements,\r
1368                                  size_t elem_size, void* chunks[]);\r
1369 \r
1370 /*\r
1371   mspace_independent_comalloc behaves as independent_comalloc, but\r
1372   operates within the given space.\r
1373 */\r
1374 DLMALLOC_EXPORT void** mspace_independent_comalloc(mspace msp, size_t n_elements,\r
1375                                    size_t sizes[], void* chunks[]);\r
1376 \r
1377 /*\r
1378   mspace_footprint() returns the number of bytes obtained from the\r
1379   system for this space.\r
1380 */\r
1381 DLMALLOC_EXPORT size_t mspace_footprint(mspace msp);\r
1382 \r
1383 /*\r
1384   mspace_max_footprint() returns the peak number of bytes obtained from the\r
1385   system for this space.\r
1386 */\r
1387 DLMALLOC_EXPORT size_t mspace_max_footprint(mspace msp);\r
1388 \r
1389 \r
1390 #if !NO_MALLINFO\r
1391 /*\r
1392   mspace_mallinfo behaves as mallinfo, but reports properties of\r
1393   the given space.\r
1394 */\r
1395 DLMALLOC_EXPORT struct mallinfo mspace_mallinfo(mspace msp);\r
1396 #endif /* NO_MALLINFO */\r
1397 \r
1398 /*\r
1399   malloc_usable_size(void* p) behaves the same as malloc_usable_size;\r
1400 */\r
1401 DLMALLOC_EXPORT size_t mspace_usable_size(void* mem);\r
1402 \r
1403 /*\r
1404   mspace_malloc_stats behaves as malloc_stats, but reports\r
1405   properties of the given space.\r
1406 */\r
1407 DLMALLOC_EXPORT void mspace_malloc_stats(mspace msp);\r
1408 \r
1409 /*\r
1410   mspace_trim behaves as malloc_trim, but\r
1411   operates within the given space.\r
1412 */\r
1413 DLMALLOC_EXPORT int mspace_trim(mspace msp, size_t pad);\r
1414 \r
1415 /*\r
1416   An alias for mallopt.\r
1417 */\r
1418 DLMALLOC_EXPORT int mspace_mallopt(int, int);\r
1419 \r
1420 #endif /* MSPACES */\r
1421 \r
1422 #ifdef __cplusplus\r
1423 }  /* end of extern "C" */\r
1424 #endif /* __cplusplus */\r
1425 \r
1426 /*\r
1427   ========================================================================\r
1428   To make a fully customizable malloc.h header file, cut everything\r
1429   above this line, put into file malloc.h, edit to suit, and #include it\r
1430   on the next line, as well as in programs that use this malloc.\r
1431   ========================================================================\r
1432 */\r
1433 \r
1434 /* #include "malloc.h" */\r
1435 \r
1436 /*------------------------------ internal #includes ---------------------- */\r
1437 \r
1438 #ifdef _MSC_VER\r
1439 #pragma warning( disable : 4146 ) /* no "unsigned" warnings */\r
1440 #endif /* _MSC_VER */\r
1441 #if !NO_MALLOC_STATS\r
1442 #include <stdio.h>       /* for printing in malloc_stats */\r
1443 #endif /* NO_MALLOC_STATS */\r
1444 #ifndef LACKS_ERRNO_H\r
1445 #include <errno.h>       /* for MALLOC_FAILURE_ACTION */\r
1446 #endif /* LACKS_ERRNO_H */\r
1447 #ifdef DEBUG\r
1448 #if ABORT_ON_ASSERT_FAILURE\r
1449 #undef assert\r
1450 #define assert(x) if(!(x)) ABORT\r
1451 #else /* ABORT_ON_ASSERT_FAILURE */\r
1452 #include <assert.h>\r
1453 #endif /* ABORT_ON_ASSERT_FAILURE */\r
1454 #else  /* DEBUG */\r
1455 #ifndef assert\r
1456 #define assert(x)\r
1457 #endif\r
1458 #define DEBUG 0\r
1459 #endif /* DEBUG */\r
1460 #if !defined(WIN32) && !defined(LACKS_TIME_H)\r
1461 #include <time.h>        /* for magic initialization */\r
1462 #endif /* WIN32 */\r
1463 #ifndef LACKS_STDLIB_H\r
1464 #include <stdlib.h>      /* for abort() */\r
1465 #endif /* LACKS_STDLIB_H */\r
1466 #ifndef LACKS_STRING_H\r
1467 #include <string.h>      /* for memset etc */\r
1468 #endif  /* LACKS_STRING_H */\r
1469 #if USE_BUILTIN_FFS\r
1470 #ifndef LACKS_STRINGS_H\r
1471 #include <strings.h>     /* for ffs */\r
1472 #endif /* LACKS_STRINGS_H */\r
1473 #endif /* USE_BUILTIN_FFS */\r
1474 #if HAVE_MMAP\r
1475 #ifndef LACKS_SYS_MMAN_H\r
1476 /* On some versions of linux, mremap decl in mman.h needs __USE_GNU set */\r
1477 #if (defined(linux) && !defined(__USE_GNU))\r
1478 #define __USE_GNU 1\r
1479 #include <sys/mman.h>    /* for mmap */\r
1480 #undef __USE_GNU\r
1481 #else\r
1482 #include <sys/mman.h>    /* for mmap */\r
1483 #endif /* linux */\r
1484 #endif /* LACKS_SYS_MMAN_H */\r
1485 #ifndef LACKS_FCNTL_H\r
1486 #include <fcntl.h>\r
1487 #endif /* LACKS_FCNTL_H */\r
1488 #endif /* HAVE_MMAP */\r
1489 #ifndef LACKS_UNISTD_H\r
1490 #include <unistd.h>     /* for sbrk, sysconf */\r
1491 #else /* LACKS_UNISTD_H */\r
1492 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)\r
1493 /*extern void*     sbrk(ptrdiff_t);*/\r
1494 #endif /* FreeBSD etc */\r
1495 #endif /* LACKS_UNISTD_H */\r
1496 \r
1497 /* Declarations for locking */\r
1498 #if USE_LOCKS\r
1499 #ifndef WIN32\r
1500 #if defined (__SVR4) && defined (__sun)  /* solaris */\r
1501 #include <thread.h>\r
1502 #elif !defined(LACKS_SCHED_H)\r
1503 #include <sched.h>\r
1504 #endif /* solaris or LACKS_SCHED_H */\r
1505 #if (defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0) || !USE_SPIN_LOCKS\r
1506 /*#include <pthread.h>*/\r
1507 #endif /* USE_RECURSIVE_LOCKS ... */\r
1508 #elif defined(_MSC_VER)\r
1509 #ifndef _M_AMD64\r
1510 /* These are already defined on AMD64 builds */\r
1511 #ifdef __cplusplus\r
1512 extern "C" {\r
1513 #endif /* __cplusplus */\r
1514 LONG __cdecl _InterlockedCompareExchange(LONG volatile *Dest, LONG Exchange, LONG Comp);\r
1515 LONG __cdecl _InterlockedExchange(LONG volatile *Target, LONG Value);\r
1516 #ifdef __cplusplus\r
1517 }\r
1518 #endif /* __cplusplus */\r
1519 #endif /* _M_AMD64 */\r
1520 #pragma intrinsic (_InterlockedCompareExchange)\r
1521 #pragma intrinsic (_InterlockedExchange)\r
1522 #define interlockedcompareexchange _InterlockedCompareExchange\r
1523 #define interlockedexchange _InterlockedExchange\r
1524 #elif defined(WIN32) && defined(__GNUC__)\r
1525 #define interlockedcompareexchange(a, b, c) __sync_val_compare_and_swap(a, c, b)\r
1526 #define interlockedexchange __sync_lock_test_and_set\r
1527 #endif /* Win32 */\r
1528 #endif /* USE_LOCKS */\r
1529 \r
1530 /* Declarations for bit scanning on win32 */\r
1531 #if defined(_MSC_VER) && _MSC_VER>=1300\r
1532 #ifndef BitScanForward  /* Try to avoid pulling in WinNT.h */\r
1533 #ifdef __cplusplus\r
1534 extern "C" {\r
1535 #endif /* __cplusplus */\r
1536 unsigned char _BitScanForward(unsigned long *index, unsigned long mask);\r
1537 unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);\r
1538 #ifdef __cplusplus\r
1539 }\r
1540 #endif /* __cplusplus */\r
1541 \r
1542 #define BitScanForward _BitScanForward\r
1543 #define BitScanReverse _BitScanReverse\r
1544 #pragma intrinsic(_BitScanForward)\r
1545 #pragma intrinsic(_BitScanReverse)\r
1546 #endif /* BitScanForward */\r
1547 #endif /* defined(_MSC_VER) && _MSC_VER>=1300 */\r
1548 \r
1549 #ifndef WIN32\r
1550 #ifndef malloc_getpagesize\r
1551 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */\r
1552 #    ifndef _SC_PAGE_SIZE\r
1553 #      define _SC_PAGE_SIZE _SC_PAGESIZE\r
1554 #    endif\r
1555 #  endif\r
1556 #  ifdef _SC_PAGE_SIZE\r
1557 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)\r
1558 #  else\r
1559 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)\r
1560        extern size_t getpagesize();\r
1561 #      define malloc_getpagesize getpagesize()\r
1562 #    else\r
1563 #      ifdef WIN32 /* use supplied emulation of getpagesize */\r
1564 #        define malloc_getpagesize getpagesize()\r
1565 #      else\r
1566 #        ifndef LACKS_SYS_PARAM_H\r
1567 #          include <sys/param.h>\r
1568 #        endif\r
1569 #        ifdef EXEC_PAGESIZE\r
1570 #          define malloc_getpagesize EXEC_PAGESIZE\r
1571 #        else\r
1572 #          ifdef NBPG\r
1573 #            ifndef CLSIZE\r
1574 #              define malloc_getpagesize NBPG\r
1575 #            else\r
1576 #              define malloc_getpagesize (NBPG * CLSIZE)\r
1577 #            endif\r
1578 #          else\r
1579 #            ifdef NBPC\r
1580 #              define malloc_getpagesize NBPC\r
1581 #            else\r
1582 #              ifdef PAGESIZE\r
1583 #                define malloc_getpagesize PAGESIZE\r
1584 #              else /* just guess */\r
1585 #                define malloc_getpagesize ((size_t)4096U)\r
1586 #              endif\r
1587 #            endif\r
1588 #          endif\r
1589 #        endif\r
1590 #      endif\r
1591 #    endif\r
1592 #  endif\r
1593 #endif\r
1594 #endif\r
1595 \r
1596 /* ------------------- size_t and alignment properties -------------------- */\r
1597 \r
1598 /* The byte and bit size of a size_t */\r
1599 #define SIZE_T_SIZE         (sizeof(size_t))\r
1600 #define SIZE_T_BITSIZE      (sizeof(size_t) << 3)\r
1601 \r
1602 /* Some constants coerced to size_t */\r
1603 /* Annoying but necessary to avoid errors on some platforms */\r
1604 #define SIZE_T_ZERO         ((size_t)0)\r
1605 #define SIZE_T_ONE          ((size_t)1)\r
1606 #define SIZE_T_TWO          ((size_t)2)\r
1607 #define SIZE_T_FOUR         ((size_t)4)\r
1608 #define TWO_SIZE_T_SIZES    (SIZE_T_SIZE<<1)\r
1609 #define FOUR_SIZE_T_SIZES   (SIZE_T_SIZE<<2)\r
1610 #define SIX_SIZE_T_SIZES    (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)\r
1611 #define HALF_MAX_SIZE_T     (MAX_SIZE_T / 2U)\r
1612 \r
1613 /* The bit mask value corresponding to MALLOC_ALIGNMENT */\r
1614 #define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)\r
1615 \r
1616 /* True if address a has acceptable alignment */\r
1617 #define is_aligned(A)       (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)\r
1618 \r
1619 /* the number of bytes to offset an address to align it */\r
1620 #define align_offset(A)\\r
1621  ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\\r
1622   ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))\r
1623 \r
1624 /* -------------------------- MMAP preliminaries ------------------------- */\r
1625 \r
1626 /*\r
1627    If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and\r
1628    checks to fail so compiler optimizer can delete code rather than\r
1629    using so many "#if"s.\r
1630 */\r
1631 \r
1632 \r
1633 /* MORECORE and MMAP must return MFAIL on failure */\r
1634 #define MFAIL                ((void*)(MAX_SIZE_T))\r
1635 #define CMFAIL               ((char*)(MFAIL)) /* defined for convenience */\r
1636 \r
1637 #if HAVE_MMAP\r
1638 \r
1639 #ifdef MMAP_DEFAULT\r
1640 #elif !defined(WIN32)\r
1641 #define MUNMAP_DEFAULT(a, s)  munmap((a), (s))\r
1642 #define MMAP_PROT            (PROT_READ|PROT_WRITE)\r
1643 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)\r
1644 #define MAP_ANONYMOUS        MAP_ANON\r
1645 #endif /* MAP_ANON */\r
1646 #ifdef MAP_ANONYMOUS\r
1647 #define MMAP_FLAGS           (MAP_PRIVATE|MAP_ANONYMOUS)\r
1648 #define MMAP_DEFAULT(s)       mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)\r
1649 #else /* MAP_ANONYMOUS */\r
1650 /*\r
1651    Nearly all versions of mmap support MAP_ANONYMOUS, so the following\r
1652    is unlikely to be needed, but is supplied just in case.\r
1653 */\r
1654 #define MMAP_FLAGS           (MAP_PRIVATE)\r
1655 #define MMAP_DEFAULT(s) ((dev_zero_fd < 0) ? \\r
1656            (dev_zero_fd = open("/dev/zero", O_RDWR), \\r
1657             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \\r
1658             mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))\r
1659 #endif /* MAP_ANONYMOUS */\r
1660 \r
1661 #define DIRECT_MMAP_DEFAULT(s) MMAP_DEFAULT(s)\r
1662 \r
1663 #else /* WIN32 */\r
1664 \r
1665 /* Win32 MMAP via VirtualAlloc */\r
1666 static FORCEINLINE void* win32mmap(size_t size) {\r
1667   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);\r
1668   return (ptr != 0)? ptr: MFAIL;\r
1669 }\r
1670 \r
1671 /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */\r
1672 static FORCEINLINE void* win32direct_mmap(size_t size) {\r
1673   void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,\r
1674                            PAGE_READWRITE);\r
1675   return (ptr != 0)? ptr: MFAIL;\r
1676 }\r
1677 \r
1678 /* This function supports releasing coalesed segments */\r
1679 static FORCEINLINE int win32munmap(void* ptr, size_t size) {\r
1680   MEMORY_BASIC_INFORMATION minfo;\r
1681   char* cptr = (char*)ptr;\r
1682   while (size) {\r
1683     if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)\r
1684       return -1;\r
1685     if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||\r
1686         minfo.State != MEM_COMMIT || minfo.RegionSize > size)\r
1687       return -1;\r
1688     if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)\r
1689       return -1;\r
1690     cptr += minfo.RegionSize;\r
1691     size -= minfo.RegionSize;\r
1692   }\r
1693   return 0;\r
1694 }\r
1695 \r
1696 #define MMAP_DEFAULT(s)             win32mmap(s)\r
1697 #define MUNMAP_DEFAULT(a, s)        win32munmap((a), (s))\r
1698 #define DIRECT_MMAP_DEFAULT(s)      win32direct_mmap(s)\r
1699 #endif /* WIN32 */\r
1700 #endif /* HAVE_MMAP */\r
1701 \r
1702 #if HAVE_MREMAP && !defined(MREMAP_DEFAULT)\r
1703 #ifndef WIN32\r
1704 #define MREMAP_DEFAULT(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))\r
1705 #endif /* WIN32 */\r
1706 #endif /* HAVE_MREMAP */\r
1707 \r
1708 /**\r
1709  * Define CALL_MORECORE\r
1710  */\r
1711 #if HAVE_MORECORE\r
1712     #ifdef MORECORE\r
1713         #define CALL_MORECORE(S)    MORECORE(S)\r
1714     #else  /* MORECORE */\r
1715         #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)\r
1716     #endif /* MORECORE */\r
1717 #else  /* HAVE_MORECORE */\r
1718     #define CALL_MORECORE(S)        MFAIL\r
1719 #endif /* HAVE_MORECORE */\r
1720 \r
1721 /**\r
1722  * Define CALL_MMAP/CALL_MUNMAP/CALL_DIRECT_MMAP\r
1723  */\r
1724 #if HAVE_MMAP\r
1725     #define USE_MMAP_BIT            (SIZE_T_ONE)\r
1726 \r
1727     #ifdef MMAP\r
1728         #define CALL_MMAP(s)        MMAP(s)\r
1729     #else /* MMAP */\r
1730         #define CALL_MMAP(s)        MMAP_DEFAULT(s)\r
1731     #endif /* MMAP */\r
1732     #ifdef MUNMAP\r
1733         #define CALL_MUNMAP(a, s)   MUNMAP((a), (s))\r
1734     #else /* MUNMAP */\r
1735         #define CALL_MUNMAP(a, s)   MUNMAP_DEFAULT((a), (s))\r
1736     #endif /* MUNMAP */\r
1737     #ifdef DIRECT_MMAP\r
1738         #define CALL_DIRECT_MMAP(s) DIRECT_MMAP(s)\r
1739     #else /* DIRECT_MMAP */\r
1740         #define CALL_DIRECT_MMAP(s) DIRECT_MMAP_DEFAULT(s)\r
1741     #endif /* DIRECT_MMAP */\r
1742 #else  /* HAVE_MMAP */\r
1743     #define USE_MMAP_BIT            (SIZE_T_ZERO)\r
1744 \r
1745     #define MMAP(s)                 MFAIL\r
1746     #define MUNMAP(a, s)            (-1)\r
1747     #define DIRECT_MMAP(s)          MFAIL\r
1748     #define CALL_DIRECT_MMAP(s)     DIRECT_MMAP(s)\r
1749     #define CALL_MMAP(s)            MMAP(s)\r
1750     #define CALL_MUNMAP(a, s)       MUNMAP((a), (s))\r
1751 #endif /* HAVE_MMAP */\r
1752 \r
1753 /**\r
1754  * Define CALL_MREMAP\r
1755  */\r
1756 #if HAVE_MMAP && HAVE_MREMAP\r
1757     #ifdef MREMAP\r
1758         #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP((addr), (osz), (nsz), (mv))\r
1759     #else /* MREMAP */\r
1760         #define CALL_MREMAP(addr, osz, nsz, mv) MREMAP_DEFAULT((addr), (osz), (nsz), (mv))\r
1761     #endif /* MREMAP */\r
1762 #else  /* HAVE_MMAP && HAVE_MREMAP */\r
1763     #define CALL_MREMAP(addr, osz, nsz, mv)     MFAIL\r
1764 #endif /* HAVE_MMAP && HAVE_MREMAP */\r
1765 \r
1766 /* mstate bit set if continguous morecore disabled or failed */\r
1767 #define USE_NONCONTIGUOUS_BIT (4U)\r
1768 \r
1769 /* segment bit set in create_mspace_with_base */\r
1770 #define EXTERN_BIT            (8U)\r
1771 \r
1772 \r
1773 /* --------------------------- Lock preliminaries ------------------------ */\r
1774 \r
1775 /*\r
1776   When locks are defined, there is one global lock, plus\r
1777   one per-mspace lock.\r
1778 \r
1779   The global lock_ensures that mparams.magic and other unique\r
1780   mparams values are initialized only once. It also protects\r
1781   sequences of calls to MORECORE.  In many cases sys_alloc requires\r
1782   two calls, that should not be interleaved with calls by other\r
1783   threads.  This does not protect against direct calls to MORECORE\r
1784   by other threads not using this lock, so there is still code to\r
1785   cope the best we can on interference.\r
1786 \r
1787   Per-mspace locks surround calls to malloc, free, etc.\r
1788   By default, locks are simple non-reentrant mutexes.\r
1789 \r
1790   Because lock-protected regions generally have bounded times, it is\r
1791   OK to use the supplied simple spinlocks. Spinlocks are likely to\r
1792   improve performance for lightly contended applications, but worsen\r
1793   performance under heavy contention.\r
1794 \r
1795   If USE_LOCKS is > 1, the definitions of lock routines here are\r
1796   bypassed, in which case you will need to define the type MLOCK_T,\r
1797   and at least INITIAL_LOCK, DESTROY_LOCK, ACQUIRE_LOCK, RELEASE_LOCK\r
1798   and TRY_LOCK.  You must also declare a\r
1799     static MLOCK_T malloc_global_mutex = { initialization values };.\r
1800 \r
1801 */\r
1802 \r
1803 #if !USE_LOCKS\r
1804 #define USE_LOCK_BIT               (0U)\r
1805 #define INITIAL_LOCK(l)            (0)\r
1806 #define DESTROY_LOCK(l)            (0)\r
1807 #define ACQUIRE_MALLOC_GLOBAL_LOCK()\r
1808 #define RELEASE_MALLOC_GLOBAL_LOCK()\r
1809 \r
1810 #else\r
1811 #if USE_LOCKS > 1\r
1812 /* -----------------------  User-defined locks ------------------------ */\r
1813 /* Define your own lock implementation here */\r
1814 /* #define INITIAL_LOCK(lk)  ... */\r
1815 /* #define DESTROY_LOCK(lk)  ... */\r
1816 /* #define ACQUIRE_LOCK(lk)  ... */\r
1817 /* #define RELEASE_LOCK(lk)  ... */\r
1818 /* #define TRY_LOCK(lk) ... */\r
1819 /* static MLOCK_T malloc_global_mutex = ... */\r
1820 \r
1821 #elif USE_SPIN_LOCKS\r
1822 \r
1823 /* First, define CAS_LOCK and CLEAR_LOCK on ints */\r
1824 /* Note CAS_LOCK defined to return 0 on success */\r
1825 \r
1826 #if defined(__GNUC__)&& (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1))\r
1827 #define CAS_LOCK(sl)     __sync_lock_test_and_set(sl, 1)\r
1828 #define CLEAR_LOCK(sl)   __sync_lock_release(sl)\r
1829 \r
1830 #elif (defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__)))\r
1831 /* Custom spin locks for older gcc on x86 */\r
1832 static FORCEINLINE int x86_cas_lock(int *sl) {\r
1833   int ret;\r
1834   int val = 1;\r
1835   int cmp = 0;\r
1836   __asm__ __volatile__  ("lock; cmpxchgl %1, %2"\r
1837                          : "=a" (ret)\r
1838                          : "r" (val), "m" (*(sl)), "0"(cmp)\r
1839                          : "memory", "cc");\r
1840   return ret;\r
1841 }\r
1842 \r
1843 static FORCEINLINE void x86_clear_lock(int* sl) {\r
1844   assert(*sl != 0);\r
1845   int prev = 0;\r
1846   int ret;\r
1847   __asm__ __volatile__ ("lock; xchgl %0, %1"\r
1848                         : "=r" (ret)\r
1849                         : "m" (*(sl)), "0"(prev)\r
1850                         : "memory");\r
1851 }\r
1852 \r
1853 #define CAS_LOCK(sl)     x86_cas_lock(sl)\r
1854 #define CLEAR_LOCK(sl)   x86_clear_lock(sl)\r
1855 \r
1856 #else /* Win32 MSC */\r
1857 #define CAS_LOCK(sl)     interlockedexchange(sl, 1)\r
1858 #define CLEAR_LOCK(sl)   interlockedexchange (sl, 0)\r
1859 \r
1860 #endif /* ... gcc spins locks ... */\r
1861 \r
1862 /* How to yield for a spin lock */\r
1863 #define SPINS_PER_YIELD       63\r
1864 #if defined(_MSC_VER)\r
1865 #define SLEEP_EX_DURATION     50 /* delay for yield/sleep */\r
1866 #define SPIN_LOCK_YIELD  SleepEx(SLEEP_EX_DURATION, FALSE)\r
1867 #elif defined (__SVR4) && defined (__sun) /* solaris */\r
1868 #define SPIN_LOCK_YIELD   thr_yield();\r
1869 #elif !defined(LACKS_SCHED_H)\r
1870 #define SPIN_LOCK_YIELD   sched_yield();\r
1871 #else\r
1872 #define SPIN_LOCK_YIELD\r
1873 #endif /* ... yield ... */\r
1874 \r
1875 #if !defined(USE_RECURSIVE_LOCKS) || USE_RECURSIVE_LOCKS == 0\r
1876 /* Plain spin locks use single word (embedded in malloc_states) */\r
1877 static int spin_acquire_lock(int *sl) {\r
1878   int spins = 0;\r
1879   while (*(volatile int *)sl != 0 || CAS_LOCK(sl)) {\r
1880     if ((++spins & SPINS_PER_YIELD) == 0) {\r
1881       SPIN_LOCK_YIELD;\r
1882     }\r
1883   }\r
1884   return 0;\r
1885 }\r
1886 \r
1887 #define MLOCK_T               int\r
1888 #define TRY_LOCK(sl)          !CAS_LOCK(sl)\r
1889 #define RELEASE_LOCK(sl)      CLEAR_LOCK(sl)\r
1890 #define ACQUIRE_LOCK(sl)      (CAS_LOCK(sl)? spin_acquire_lock(sl) : 0)\r
1891 #define INITIAL_LOCK(sl)      (*sl = 0)\r
1892 #define DESTROY_LOCK(sl)      (0)\r
1893 static MLOCK_T malloc_global_mutex = 0;\r
1894 \r
1895 #else /* USE_RECURSIVE_LOCKS */\r
1896 /* types for lock owners */\r
1897 #ifdef WIN32\r
1898 #define THREAD_ID_T           DWORD\r
1899 #define CURRENT_THREAD        GetCurrentThreadId()\r
1900 #define EQ_OWNER(X,Y)         ((X) == (Y))\r
1901 #else\r
1902 /*\r
1903   Note: the following assume that pthread_t is a type that can be\r
1904   initialized to (casted) zero. If this is not the case, you will need to\r
1905   somehow redefine these or not use spin locks.\r
1906 */\r
1907 #define THREAD_ID_T           pthread_t\r
1908 #define CURRENT_THREAD        pthread_self()\r
1909 #define EQ_OWNER(X,Y)         pthread_equal(X, Y)\r
1910 #endif\r
1911 \r
1912 struct malloc_recursive_lock {\r
1913   int sl;\r
1914   unsigned int c;\r
1915   THREAD_ID_T threadid;\r
1916 };\r
1917 \r
1918 #define MLOCK_T  struct malloc_recursive_lock\r
1919 static MLOCK_T malloc_global_mutex = { 0, 0, (THREAD_ID_T)0};\r
1920 \r
1921 static FORCEINLINE void recursive_release_lock(MLOCK_T *lk) {\r
1922   assert(lk->sl != 0);\r
1923   if (--lk->c == 0) {\r
1924     CLEAR_LOCK(&lk->sl);\r
1925   }\r
1926 }\r
1927 \r
1928 static FORCEINLINE int recursive_acquire_lock(MLOCK_T *lk) {\r
1929   THREAD_ID_T mythreadid = CURRENT_THREAD;\r
1930   int spins = 0;\r
1931   for (;;) {\r
1932     if (*((volatile int *)(&lk->sl)) == 0) {\r
1933       if (!CAS_LOCK(&lk->sl)) {\r
1934         lk->threadid = mythreadid;\r
1935         lk->c = 1;\r
1936         return 0;\r
1937       }\r
1938     }\r
1939     else if (EQ_OWNER(lk->threadid, mythreadid)) {\r
1940       ++lk->c;\r
1941       return 0;\r
1942     }\r
1943     if ((++spins & SPINS_PER_YIELD) == 0) {\r
1944       SPIN_LOCK_YIELD;\r
1945     }\r
1946   }\r
1947 }\r
1948 \r
1949 static FORCEINLINE int recursive_try_lock(MLOCK_T *lk) {\r
1950   THREAD_ID_T mythreadid = CURRENT_THREAD;\r
1951   if (*((volatile int *)(&lk->sl)) == 0) {\r
1952     if (!CAS_LOCK(&lk->sl)) {\r
1953       lk->threadid = mythreadid;\r
1954       lk->c = 1;\r
1955       return 1;\r
1956     }\r
1957   }\r
1958   else if (EQ_OWNER(lk->threadid, mythreadid)) {\r
1959     ++lk->c;\r
1960     return 1;\r
1961   }\r
1962   return 0;\r
1963 }\r
1964 \r
1965 #define RELEASE_LOCK(lk)      recursive_release_lock(lk)\r
1966 #define TRY_LOCK(lk)          recursive_try_lock(lk)\r
1967 #define ACQUIRE_LOCK(lk)      recursive_acquire_lock(lk)\r
1968 #define INITIAL_LOCK(lk)      ((lk)->threadid = (THREAD_ID_T)0, (lk)->sl = 0, (lk)->c = 0)\r
1969 #define DESTROY_LOCK(lk)      (0)\r
1970 #endif /* USE_RECURSIVE_LOCKS */\r
1971 \r
1972 #elif defined(WIN32) /* Win32 critical sections */\r
1973 #define MLOCK_T               CRITICAL_SECTION\r
1974 #define ACQUIRE_LOCK(lk)      (EnterCriticalSection(lk), 0)\r
1975 #define RELEASE_LOCK(lk)      LeaveCriticalSection(lk)\r
1976 #define TRY_LOCK(lk)          TryEnterCriticalSection(lk)\r
1977 #define INITIAL_LOCK(lk)      (!InitializeCriticalSectionAndSpinCount((lk), 0x80000000|4000))\r
1978 #define DESTROY_LOCK(lk)      (DeleteCriticalSection(lk), 0)\r
1979 #define NEED_GLOBAL_LOCK_INIT\r
1980 \r
1981 static MLOCK_T malloc_global_mutex;\r
1982 static volatile long malloc_global_mutex_status;\r
1983 \r
1984 /* Use spin loop to initialize global lock */\r
1985 static void init_malloc_global_mutex() {\r
1986   for (;;) {\r
1987     long stat = malloc_global_mutex_status;\r
1988     if (stat > 0)\r
1989       return;\r
1990     /* transition to < 0 while initializing, then to > 0) */\r
1991     if (stat == 0 &&\r
1992         interlockedcompareexchange(&malloc_global_mutex_status, -1, 0) == 0) {\r
1993       InitializeCriticalSection(&malloc_global_mutex);\r
1994       interlockedexchange(&malloc_global_mutex_status,1);\r
1995       return;\r
1996     }\r
1997     SleepEx(0, FALSE);\r
1998   }\r
1999 }\r
2000 \r
2001 #else /* pthreads-based locks */\r
2002 #define MLOCK_T               pthread_mutex_t\r
2003 #define ACQUIRE_LOCK(lk)      pthread_mutex_lock(lk)\r
2004 #define RELEASE_LOCK(lk)      pthread_mutex_unlock(lk)\r
2005 #define TRY_LOCK(lk)          (!pthread_mutex_trylock(lk))\r
2006 #define INITIAL_LOCK(lk)      pthread_init_lock(lk)\r
2007 #define DESTROY_LOCK(lk)      pthread_mutex_destroy(lk)\r
2008 \r
2009 #if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0 && defined(linux) && !defined(PTHREAD_MUTEX_RECURSIVE)\r
2010 /* Cope with old-style linux recursive lock initialization by adding */\r
2011 /* skipped internal declaration from pthread.h */\r
2012 extern int pthread_mutexattr_setkind_np __P ((pthread_mutexattr_t *__attr,\r
2013                                            int __kind));\r
2014 #define PTHREAD_MUTEX_RECURSIVE PTHREAD_MUTEX_RECURSIVE_NP\r
2015 #define pthread_mutexattr_settype(x,y) pthread_mutexattr_setkind_np(x,y)\r
2016 #endif /* USE_RECURSIVE_LOCKS ... */\r
2017 \r
2018 static MLOCK_T malloc_global_mutex = PTHREAD_MUTEX_INITIALIZER;\r
2019 \r
2020 static int pthread_init_lock (MLOCK_T *lk) {\r
2021   pthread_mutexattr_t attr;\r
2022   if (pthread_mutexattr_init(&attr)) return 1;\r
2023 #if defined(USE_RECURSIVE_LOCKS) && USE_RECURSIVE_LOCKS != 0\r
2024   if (pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1;\r
2025 #endif\r
2026   if (pthread_mutex_init(lk, &attr)) return 1;\r
2027   if (pthread_mutexattr_destroy(&attr)) return 1;\r
2028   return 0;\r
2029 }\r
2030 \r
2031 #endif /* ... lock types ... */\r
2032 \r
2033 /* Common code for all lock types */\r
2034 #define USE_LOCK_BIT               (2U)\r
2035 \r
2036 #ifndef ACQUIRE_MALLOC_GLOBAL_LOCK\r
2037 #define ACQUIRE_MALLOC_GLOBAL_LOCK()  ACQUIRE_LOCK(&malloc_global_mutex);\r
2038 #endif\r
2039 \r
2040 #ifndef RELEASE_MALLOC_GLOBAL_LOCK\r
2041 #define RELEASE_MALLOC_GLOBAL_LOCK()  RELEASE_LOCK(&malloc_global_mutex);\r
2042 #endif\r
2043 \r
2044 #endif /* USE_LOCKS */\r
2045 \r
2046 /* -----------------------  Chunk representations ------------------------ */\r
2047 \r
2048 /*\r
2049   (The following includes lightly edited explanations by Colin Plumb.)\r
2050 \r
2051   The malloc_chunk declaration below is misleading (but accurate and\r
2052   necessary).  It declares a "view" into memory allowing access to\r
2053   necessary fields at known offsets from a given base.\r
2054 \r
2055   Chunks of memory are maintained using a `boundary tag' method as\r
2056   originally described by Knuth.  (See the paper by Paul Wilson\r
2057   ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such\r
2058   techniques.)  Sizes of free chunks are stored both in the front of\r
2059   each chunk and at the end.  This makes consolidating fragmented\r
2060   chunks into bigger chunks fast.  The head fields also hold bits\r
2061   representing whether chunks are free or in use.\r
2062 \r
2063   Here are some pictures to make it clearer.  They are "exploded" to\r
2064   show that the state of a chunk can be thought of as extending from\r
2065   the high 31 bits of the head field of its header through the\r
2066   prev_foot and PINUSE_BIT bit of the following chunk header.\r
2067 \r
2068   A chunk that's in use looks like:\r
2069 \r
2070    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2071            | Size of previous chunk (if P = 0)                             |\r
2072            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2073          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|\r
2074          | Size of this chunk                                         1| +-+\r
2075    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2076          |                                                               |\r
2077          +-                                                             -+\r
2078          |                                                               |\r
2079          +-                                                             -+\r
2080          |                                                               :\r
2081          +-      size - sizeof(size_t) available payload bytes          -+\r
2082          :                                                               |\r
2083  chunk-> +-                                                             -+\r
2084          |                                                               |\r
2085          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2086        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|\r
2087        | Size of next chunk (may or may not be in use)               | +-+\r
2088  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2089 \r
2090     And if it's free, it looks like this:\r
2091 \r
2092    chunk-> +-                                                             -+\r
2093            | User payload (must be in use, or we would have merged!)       |\r
2094            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2095          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|\r
2096          | Size of this chunk                                         0| +-+\r
2097    mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2098          | Next pointer                                                  |\r
2099          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2100          | Prev pointer                                                  |\r
2101          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2102          |                                                               :\r
2103          +-      size - sizeof(struct chunk) unused bytes               -+\r
2104          :                                                               |\r
2105  chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2106          | Size of this chunk                                            |\r
2107          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2108        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|\r
2109        | Size of next chunk (must be in use, or we would have merged)| +-+\r
2110  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2111        |                                                               :\r
2112        +- User payload                                                -+\r
2113        :                                                               |\r
2114        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2115                                                                      |0|\r
2116                                                                      +-+\r
2117   Note that since we always merge adjacent free chunks, the chunks\r
2118   adjacent to a free chunk must be in use.\r
2119 \r
2120   Given a pointer to a chunk (which can be derived trivially from the\r
2121   payload pointer) we can, in O(1) time, find out whether the adjacent\r
2122   chunks are free, and if so, unlink them from the lists that they\r
2123   are on and merge them with the current chunk.\r
2124 \r
2125   Chunks always begin on even word boundaries, so the mem portion\r
2126   (which is returned to the user) is also on an even word boundary, and\r
2127   thus at least double-word aligned.\r
2128 \r
2129   The P (PINUSE_BIT) bit, stored in the unused low-order bit of the\r
2130   chunk size (which is always a multiple of two words), is an in-use\r
2131   bit for the *previous* chunk.  If that bit is *clear*, then the\r
2132   word before the current chunk size contains the previous chunk\r
2133   size, and can be used to find the front of the previous chunk.\r
2134   The very first chunk allocated always has this bit set, preventing\r
2135   access to non-existent (or non-owned) memory. If pinuse is set for\r
2136   any given chunk, then you CANNOT determine the size of the\r
2137   previous chunk, and might even get a memory addressing fault when\r
2138   trying to do so.\r
2139 \r
2140   The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of\r
2141   the chunk size redundantly records whether the current chunk is\r
2142   inuse (unless the chunk is mmapped). This redundancy enables usage\r
2143   checks within free and realloc, and reduces indirection when freeing\r
2144   and consolidating chunks.\r
2145 \r
2146   Each freshly allocated chunk must have both cinuse and pinuse set.\r
2147   That is, each allocated chunk borders either a previously allocated\r
2148   and still in-use chunk, or the base of its memory arena. This is\r
2149   ensured by making all allocations from the `lowest' part of any\r
2150   found chunk.  Further, no free chunk physically borders another one,\r
2151   so each free chunk is known to be preceded and followed by either\r
2152   inuse chunks or the ends of memory.\r
2153 \r
2154   Note that the `foot' of the current chunk is actually represented\r
2155   as the prev_foot of the NEXT chunk. This makes it easier to\r
2156   deal with alignments etc but can be very confusing when trying\r
2157   to extend or adapt this code.\r
2158 \r
2159   The exceptions to all this are\r
2160 \r
2161      1. The special chunk `top' is the top-most available chunk (i.e.,\r
2162         the one bordering the end of available memory). It is treated\r
2163         specially.  Top is never included in any bin, is used only if\r
2164         no other chunk is available, and is released back to the\r
2165         system if it is very large (see M_TRIM_THRESHOLD).  In effect,\r
2166         the top chunk is treated as larger (and thus less well\r
2167         fitting) than any other available chunk.  The top chunk\r
2168         doesn't update its trailing size field since there is no next\r
2169         contiguous chunk that would have to index off it. However,\r
2170         space is still allocated for it (TOP_FOOT_SIZE) to enable\r
2171         separation or merging when space is extended.\r
2172 \r
2173      3. Chunks allocated via mmap, have both cinuse and pinuse bits\r
2174         cleared in their head fields.  Because they are allocated\r
2175         one-by-one, each must carry its own prev_foot field, which is\r
2176         also used to hold the offset this chunk has within its mmapped\r
2177         region, which is needed to preserve alignment. Each mmapped\r
2178         chunk is trailed by the first two fields of a fake next-chunk\r
2179         for sake of usage checks.\r
2180 \r
2181 */\r
2182 \r
2183 struct malloc_chunk {\r
2184   size_t               prev_foot;  /* Size of previous chunk (if free).  */\r
2185   size_t               head;       /* Size and inuse bits. */\r
2186   struct malloc_chunk* fd;         /* double links -- used only if free. */\r
2187   struct malloc_chunk* bk;\r
2188 };\r
2189 \r
2190 typedef struct malloc_chunk  mchunk;\r
2191 typedef struct malloc_chunk* mchunkptr;\r
2192 typedef struct malloc_chunk* sbinptr;  /* The type of bins of chunks */\r
2193 typedef unsigned int bindex_t;         /* Described below */\r
2194 typedef unsigned int binmap_t;         /* Described below */\r
2195 typedef unsigned int flag_t;           /* The type of various bit flag sets */\r
2196 \r
2197 /* ------------------- Chunks sizes and alignments ----------------------- */\r
2198 \r
2199 #define MCHUNK_SIZE         (sizeof(mchunk))\r
2200 \r
2201 #if FOOTERS\r
2202 #define CHUNK_OVERHEAD      (TWO_SIZE_T_SIZES)\r
2203 #else /* FOOTERS */\r
2204 #define CHUNK_OVERHEAD      (SIZE_T_SIZE)\r
2205 #endif /* FOOTERS */\r
2206 \r
2207 /* MMapped chunks need a second word of overhead ... */\r
2208 #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)\r
2209 /* ... and additional padding for fake next-chunk at foot */\r
2210 #define MMAP_FOOT_PAD       (FOUR_SIZE_T_SIZES)\r
2211 \r
2212 /* The smallest size we can malloc is an aligned minimal chunk */\r
2213 #define MIN_CHUNK_SIZE\\r
2214   ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)\r
2215 \r
2216 /* conversion from malloc headers to user pointers, and back */\r
2217 #define chunk2mem(p)        ((void*)((char*)(p)       + TWO_SIZE_T_SIZES))\r
2218 #define mem2chunk(mem)      ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))\r
2219 /* chunk associated with aligned address A */\r
2220 #define align_as_chunk(A)   (mchunkptr)((A) + align_offset(chunk2mem(A)))\r
2221 \r
2222 /* Bounds on request (not chunk) sizes. */\r
2223 #define MAX_REQUEST         ((-MIN_CHUNK_SIZE) << 2)\r
2224 #define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)\r
2225 \r
2226 /* pad request bytes into a usable size */\r
2227 #define pad_request(req) \\r
2228    (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)\r
2229 \r
2230 /* pad request, checking for minimum (but not maximum) */\r
2231 #define request2size(req) \\r
2232   (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))\r
2233 \r
2234 \r
2235 /* ------------------ Operations on head and foot fields ----------------- */\r
2236 \r
2237 /*\r
2238   The head field of a chunk is or'ed with PINUSE_BIT when previous\r
2239   adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in\r
2240   use, unless mmapped, in which case both bits are cleared.\r
2241 \r
2242   FLAG4_BIT is not used by this malloc, but might be useful in extensions.\r
2243 */\r
2244 \r
2245 #define PINUSE_BIT          (SIZE_T_ONE)\r
2246 #define CINUSE_BIT          (SIZE_T_TWO)\r
2247 #define FLAG4_BIT           (SIZE_T_FOUR)\r
2248 #define INUSE_BITS          (PINUSE_BIT|CINUSE_BIT)\r
2249 #define FLAG_BITS           (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT)\r
2250 \r
2251 /* Head value for fenceposts */\r
2252 #define FENCEPOST_HEAD      (INUSE_BITS|SIZE_T_SIZE)\r
2253 \r
2254 /* extraction of fields from head words */\r
2255 #define cinuse(p)           ((p)->head & CINUSE_BIT)\r
2256 #define pinuse(p)           ((p)->head & PINUSE_BIT)\r
2257 #define flag4inuse(p)       ((p)->head & FLAG4_BIT)\r
2258 #define is_inuse(p)         (((p)->head & INUSE_BITS) != PINUSE_BIT)\r
2259 #define is_mmapped(p)       (((p)->head & INUSE_BITS) == 0)\r
2260 \r
2261 #define chunksize(p)        ((p)->head & ~(FLAG_BITS))\r
2262 \r
2263 #define clear_pinuse(p)     ((p)->head &= ~PINUSE_BIT)\r
2264 #define set_flag4(p)        ((p)->head |= FLAG4_BIT)\r
2265 #define clear_flag4(p)      ((p)->head &= ~FLAG4_BIT)\r
2266 \r
2267 /* Treat space at ptr +/- offset as a chunk */\r
2268 #define chunk_plus_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))\r
2269 #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))\r
2270 \r
2271 /* Ptr to next or previous physical malloc_chunk. */\r
2272 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS)))\r
2273 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))\r
2274 \r
2275 /* extract next chunk's pinuse bit */\r
2276 #define next_pinuse(p)  ((next_chunk(p)->head) & PINUSE_BIT)\r
2277 \r
2278 /* Get/set size at footer */\r
2279 #define get_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot)\r
2280 #define set_foot(p, s)  (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))\r
2281 \r
2282 /* Set size, pinuse bit, and foot */\r
2283 #define set_size_and_pinuse_of_free_chunk(p, s)\\r
2284   ((p)->head = (s|PINUSE_BIT), set_foot(p, s))\r
2285 \r
2286 /* Set size, pinuse bit, foot, and clear next pinuse */\r
2287 #define set_free_with_pinuse(p, s, n)\\r
2288   (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))\r
2289 \r
2290 /* Get the internal overhead associated with chunk p */\r
2291 #define overhead_for(p)\\r
2292  (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)\r
2293 \r
2294 /* Return true if malloced space is not necessarily cleared */\r
2295 #if MMAP_CLEARS\r
2296 #define calloc_must_clear(p) (!is_mmapped(p))\r
2297 #else /* MMAP_CLEARS */\r
2298 #define calloc_must_clear(p) (1)\r
2299 #endif /* MMAP_CLEARS */\r
2300 \r
2301 /* ---------------------- Overlaid data structures ----------------------- */\r
2302 \r
2303 /*\r
2304   When chunks are not in use, they are treated as nodes of either\r
2305   lists or trees.\r
2306 \r
2307   "Small"  chunks are stored in circular doubly-linked lists, and look\r
2308   like this:\r
2309 \r
2310     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2311             |             Size of previous chunk                            |\r
2312             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2313     `head:' |             Size of chunk, in bytes                         |P|\r
2314       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2315             |             Forward pointer to next chunk in list             |\r
2316             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2317             |             Back pointer to previous chunk in list            |\r
2318             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2319             |             Unused space (may be 0 bytes long)                .\r
2320             .                                                               .\r
2321             .                                                               |\r
2322 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2323     `foot:' |             Size of chunk, in bytes                           |\r
2324             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2325 \r
2326   Larger chunks are kept in a form of bitwise digital trees (aka\r
2327   tries) keyed on chunksizes.  Because malloc_tree_chunks are only for\r
2328   free chunks greater than 256 bytes, their size doesn't impose any\r
2329   constraints on user chunk sizes.  Each node looks like:\r
2330 \r
2331     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2332             |             Size of previous chunk                            |\r
2333             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2334     `head:' |             Size of chunk, in bytes                         |P|\r
2335       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2336             |             Forward pointer to next chunk of same size        |\r
2337             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2338             |             Back pointer to previous chunk of same size       |\r
2339             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2340             |             Pointer to left child (child[0])                  |\r
2341             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2342             |             Pointer to right child (child[1])                 |\r
2343             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2344             |             Pointer to parent                                 |\r
2345             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2346             |             bin index of this chunk                           |\r
2347             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2348             |             Unused space                                      .\r
2349             .                                                               |\r
2350 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2351     `foot:' |             Size of chunk, in bytes                           |\r
2352             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r
2353 \r
2354   Each tree holding treenodes is a tree of unique chunk sizes.  Chunks\r
2355   of the same size are arranged in a circularly-linked list, with only\r
2356   the oldest chunk (the next to be used, in our FIFO ordering)\r
2357   actually in the tree.  (Tree members are distinguished by a non-null\r
2358   parent pointer.)  If a chunk with the same size an an existing node\r
2359   is inserted, it is linked off the existing node using pointers that\r
2360   work in the same way as fd/bk pointers of small chunks.\r
2361 \r
2362   Each tree contains a power of 2 sized range of chunk sizes (the\r
2363   smallest is 0x100 <= x < 0x180), which is is divided in half at each\r
2364   tree level, with the chunks in the smaller half of the range (0x100\r
2365   <= x < 0x140 for the top nose) in the left subtree and the larger\r
2366   half (0x140 <= x < 0x180) in the right subtree.  This is, of course,\r
2367   done by inspecting individual bits.\r
2368 \r
2369   Using these rules, each node's left subtree contains all smaller\r
2370   sizes than its right subtree.  However, the node at the root of each\r
2371   subtree has no particular ordering relationship to either.  (The\r
2372   dividing line between the subtree sizes is based on trie relation.)\r
2373   If we remove the last chunk of a given size from the interior of the\r
2374   tree, we need to replace it with a leaf node.  The tree ordering\r
2375   rules permit a node to be replaced by any leaf below it.\r
2376 \r
2377   The smallest chunk in a tree (a common operation in a best-fit\r
2378   allocator) can be found by walking a path to the leftmost leaf in\r
2379   the tree.  Unlike a usual binary tree, where we follow left child\r
2380   pointers until we reach a null, here we follow the right child\r
2381   pointer any time the left one is null, until we reach a leaf with\r
2382   both child pointers null. The smallest chunk in the tree will be\r
2383   somewhere along that path.\r
2384 \r
2385   The worst case number of steps to add, find, or remove a node is\r
2386   bounded by the number of bits differentiating chunks within\r
2387   bins. Under current bin calculations, this ranges from 6 up to 21\r
2388   (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case\r
2389   is of course much better.\r
2390 */\r
2391 \r
2392 struct malloc_tree_chunk {\r
2393   /* The first four fields must be compatible with malloc_chunk */\r
2394   size_t                    prev_foot;\r
2395   size_t                    head;\r
2396   struct malloc_tree_chunk* fd;\r
2397   struct malloc_tree_chunk* bk;\r
2398 \r
2399   struct malloc_tree_chunk* child[2];\r
2400   struct malloc_tree_chunk* parent;\r
2401   bindex_t                  index;\r
2402 };\r
2403 \r
2404 typedef struct malloc_tree_chunk  tchunk;\r
2405 typedef struct malloc_tree_chunk* tchunkptr;\r
2406 typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */\r
2407 \r
2408 /* A little helper macro for trees */\r
2409 #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])\r
2410 \r
2411 /* ----------------------------- Segments -------------------------------- */\r
2412 \r
2413 /*\r
2414   Each malloc space may include non-contiguous segments, held in a\r
2415   list headed by an embedded malloc_segment record representing the\r
2416   top-most space. Segments also include flags holding properties of\r
2417   the space. Large chunks that are directly allocated by mmap are not\r
2418   included in this list. They are instead independently created and\r
2419   destroyed without otherwise keeping track of them.\r
2420 \r
2421   Segment management mainly comes into play for spaces allocated by\r
2422   MMAP.  Any call to MMAP might or might not return memory that is\r
2423   adjacent to an existing segment.  MORECORE normally contiguously\r
2424   extends the current space, so this space is almost always adjacent,\r
2425   which is simpler and faster to deal with. (This is why MORECORE is\r
2426   used preferentially to MMAP when both are available -- see\r
2427   sys_alloc.)  When allocating using MMAP, we don't use any of the\r
2428   hinting mechanisms (inconsistently) supported in various\r
2429   implementations of unix mmap, or distinguish reserving from\r
2430   committing memory. Instead, we just ask for space, and exploit\r
2431   contiguity when we get it.  It is probably possible to do\r
2432   better than this on some systems, but no general scheme seems\r
2433   to be significantly better.\r
2434 \r
2435   Management entails a simpler variant of the consolidation scheme\r
2436   used for chunks to reduce fragmentation -- new adjacent memory is\r
2437   normally prepended or appended to an existing segment. However,\r
2438   there are limitations compared to chunk consolidation that mostly\r
2439   reflect the fact that segment processing is relatively infrequent\r
2440   (occurring only when getting memory from system) and that we\r
2441   don't expect to have huge numbers of segments:\r
2442 \r
2443   * Segments are not indexed, so traversal requires linear scans.  (It\r
2444     would be possible to index these, but is not worth the extra\r
2445     overhead and complexity for most programs on most platforms.)\r
2446   * New segments are only appended to old ones when holding top-most\r
2447     memory; if they cannot be prepended to others, they are held in\r
2448     different segments.\r
2449 \r
2450   Except for the top-most segment of an mstate, each segment record\r
2451   is kept at the tail of its segment. Segments are added by pushing\r
2452   segment records onto the list headed by &mstate.seg for the\r
2453   containing mstate.\r
2454 \r
2455   Segment flags control allocation/merge/deallocation policies:\r
2456   * If EXTERN_BIT set, then we did not allocate this segment,\r
2457     and so should not try to deallocate or merge with others.\r
2458     (This currently holds only for the initial segment passed\r
2459     into create_mspace_with_base.)\r
2460   * If USE_MMAP_BIT set, the segment may be merged with\r
2461     other surrounding mmapped segments and trimmed/de-allocated\r
2462     using munmap.\r
2463   * If neither bit is set, then the segment was obtained using\r
2464     MORECORE so can be merged with surrounding MORECORE'd segments\r
2465     and deallocated/trimmed using MORECORE with negative arguments.\r
2466 */\r
2467 \r
2468 struct malloc_segment {\r
2469   char*        base;             /* base address */\r
2470   size_t       size;             /* allocated size */\r
2471   struct malloc_segment* next;   /* ptr to next segment */\r
2472   flag_t       sflags;           /* mmap and extern flag */\r
2473 };\r
2474 \r
2475 #define is_mmapped_segment(S)  ((S)->sflags & USE_MMAP_BIT)\r
2476 #define is_extern_segment(S)   ((S)->sflags & EXTERN_BIT)\r
2477 \r
2478 typedef struct malloc_segment  msegment;\r
2479 typedef struct malloc_segment* msegmentptr;\r
2480 \r
2481 /* ---------------------------- malloc_state ----------------------------- */\r
2482 \r
2483 /*\r
2484    A malloc_state holds all of the bookkeeping for a space.\r
2485    The main fields are:\r
2486 \r
2487   Top\r
2488     The topmost chunk of the currently active segment. Its size is\r
2489     cached in topsize.  The actual size of topmost space is\r
2490     topsize+TOP_FOOT_SIZE, which includes space reserved for adding\r
2491     fenceposts and segment records if necessary when getting more\r
2492     space from the system.  The size at which to autotrim top is\r
2493     cached from mparams in trim_check, except that it is disabled if\r
2494     an autotrim fails.\r
2495 \r
2496   Designated victim (dv)\r
2497     This is the preferred chunk for servicing small requests that\r
2498     don't have exact fits.  It is normally the chunk split off most\r
2499     recently to service another small request.  Its size is cached in\r
2500     dvsize. The link fields of this chunk are not maintained since it\r
2501     is not kept in a bin.\r
2502 \r
2503   SmallBins\r
2504     An array of bin headers for free chunks.  These bins hold chunks\r
2505     with sizes less than MIN_LARGE_SIZE bytes. Each bin contains\r
2506     chunks of all the same size, spaced 8 bytes apart.  To simplify\r
2507     use in double-linked lists, each bin header acts as a malloc_chunk\r
2508     pointing to the real first node, if it exists (else pointing to\r
2509     itself).  This avoids special-casing for headers.  But to avoid\r
2510     waste, we allocate only the fd/bk pointers of bins, and then use\r
2511     repositioning tricks to treat these as the fields of a chunk.\r
2512 \r
2513   TreeBins\r
2514     Treebins are pointers to the roots of trees holding a range of\r
2515     sizes. There are 2 equally spaced treebins for each power of two\r
2516     from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything\r
2517     larger.\r
2518 \r
2519   Bin maps\r
2520     There is one bit map for small bins ("smallmap") and one for\r
2521     treebins ("treemap).  Each bin sets its bit when non-empty, and\r
2522     clears the bit when empty.  Bit operations are then used to avoid\r
2523     bin-by-bin searching -- nearly all "search" is done without ever\r
2524     looking at bins that won't be selected.  The bit maps\r
2525     conservatively use 32 bits per map word, even if on 64bit system.\r
2526     For a good description of some of the bit-based techniques used\r
2527     here, see Henry S. Warren Jr's book "Hacker's Delight" (and\r
2528     supplement at http://hackersdelight.org/). Many of these are\r
2529     intended to reduce the branchiness of paths through malloc etc, as\r
2530     well as to reduce the number of memory locations read or written.\r
2531 \r
2532   Segments\r
2533     A list of segments headed by an embedded malloc_segment record\r
2534     representing the initial space.\r
2535 \r
2536   Address check support\r
2537     The least_addr field is the least address ever obtained from\r
2538     MORECORE or MMAP. Attempted frees and reallocs of any address less\r
2539     than this are trapped (unless INSECURE is defined).\r
2540 \r
2541   Magic tag\r
2542     A cross-check field that should always hold same value as mparams.magic.\r
2543 \r
2544   Max allowed footprint\r
2545     The maximum allowed bytes to allocate from system (zero means no limit)\r
2546 \r
2547   Flags\r
2548     Bits recording whether to use MMAP, locks, or contiguous MORECORE\r
2549 \r
2550   Statistics\r
2551     Each space keeps track of current and maximum system memory\r
2552     obtained via MORECORE or MMAP.\r
2553 \r
2554   Trim support\r
2555     Fields holding the amount of unused topmost memory that should trigger\r
2556     trimming, and a counter to force periodic scanning to release unused\r
2557     non-topmost segments.\r
2558 \r
2559   Locking\r
2560     If USE_LOCKS is defined, the "mutex" lock is acquired and released\r
2561     around every public call using this mspace.\r
2562 \r
2563   Extension support\r
2564     A void* pointer and a size_t field that can be used to help implement\r
2565     extensions to this malloc.\r
2566 */\r
2567 \r
2568 /* Bin types, widths and sizes */\r
2569 #define NSMALLBINS        (32U)\r
2570 #define NTREEBINS         (32U)\r
2571 #define SMALLBIN_SHIFT    (3U)\r
2572 #define SMALLBIN_WIDTH    (SIZE_T_ONE << SMALLBIN_SHIFT)\r
2573 #define TREEBIN_SHIFT     (8U)\r
2574 #define MIN_LARGE_SIZE    (SIZE_T_ONE << TREEBIN_SHIFT)\r
2575 #define MAX_SMALL_SIZE    (MIN_LARGE_SIZE - SIZE_T_ONE)\r
2576 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)\r
2577 \r
2578 struct malloc_state {\r
2579   binmap_t   smallmap;\r
2580   binmap_t   treemap;\r
2581   size_t     dvsize;\r
2582   size_t     topsize;\r
2583   char*      least_addr;\r
2584   mchunkptr  dv;\r
2585   mchunkptr  top;\r
2586   size_t     trim_check;\r
2587   size_t     release_checks;\r
2588   size_t     magic;\r
2589   mchunkptr  smallbins[(NSMALLBINS+1)*2];\r
2590   tbinptr    treebins[NTREEBINS];\r
2591   size_t     footprint;\r
2592   size_t     max_footprint;\r
2593   size_t     footprint_limit; /* zero means no limit */\r
2594   flag_t     mflags;\r
2595 #if USE_LOCKS\r
2596   MLOCK_T    mutex;     /* locate lock among fields that rarely change */\r
2597 #endif /* USE_LOCKS */\r
2598   msegment   seg;\r
2599   void*      extp;      /* Unused but available for extensions */\r
2600   size_t     exts;\r
2601 };\r
2602 \r
2603 typedef struct malloc_state*    mstate;\r
2604 \r
2605 /* ------------- Global malloc_state and malloc_params ------------------- */\r
2606 \r
2607 /*\r
2608   malloc_params holds global properties, including those that can be\r
2609   dynamically set using mallopt. There is a single instance, mparams,\r
2610   initialized in init_mparams. Note that the non-zeroness of "magic"\r
2611   also serves as an initialization flag.\r
2612 */\r
2613 \r
2614 struct malloc_params {\r
2615   size_t magic;\r
2616   size_t page_size;\r
2617   size_t granularity;\r
2618   size_t mmap_threshold;\r
2619   size_t trim_threshold;\r
2620   flag_t default_mflags;\r
2621 };\r
2622 \r
2623 static struct malloc_params mparams;\r
2624 \r
2625 /* Ensure mparams initialized */\r
2626 #define ensure_initialization() (void)(mparams.magic != 0 || init_mparams())\r
2627 \r
2628 #if !ONLY_MSPACES\r
2629 \r
2630 /* The global malloc_state used for all non-"mspace" calls */\r
2631 static struct malloc_state _gm_;\r
2632 #define gm                 (&_gm_)\r
2633 #define is_global(M)       ((M) == &_gm_)\r
2634 \r
2635 #endif /* !ONLY_MSPACES */\r
2636 \r
2637 #define is_initialized(M)  ((M)->top != 0)\r
2638 \r
2639 /* -------------------------- system alloc setup ------------------------- */\r
2640 \r
2641 /* Operations on mflags */\r
2642 \r
2643 #define use_lock(M)           ((M)->mflags &   USE_LOCK_BIT)\r
2644 #define enable_lock(M)        ((M)->mflags |=  USE_LOCK_BIT)\r
2645 #if USE_LOCKS\r
2646 #define disable_lock(M)       ((M)->mflags &= ~USE_LOCK_BIT)\r
2647 #else\r
2648 #define disable_lock(M)\r
2649 #endif\r
2650 \r
2651 #define use_mmap(M)           ((M)->mflags &   USE_MMAP_BIT)\r
2652 #define enable_mmap(M)        ((M)->mflags |=  USE_MMAP_BIT)\r
2653 #if HAVE_MMAP\r
2654 #define disable_mmap(M)       ((M)->mflags &= ~USE_MMAP_BIT)\r
2655 #else\r
2656 #define disable_mmap(M)\r
2657 #endif\r
2658 \r
2659 #define use_noncontiguous(M)  ((M)->mflags &   USE_NONCONTIGUOUS_BIT)\r
2660 #define disable_contiguous(M) ((M)->mflags |=  USE_NONCONTIGUOUS_BIT)\r
2661 \r
2662 #define set_lock(M,L)\\r
2663  ((M)->mflags = (L)?\\r
2664   ((M)->mflags | USE_LOCK_BIT) :\\r
2665   ((M)->mflags & ~USE_LOCK_BIT))\r
2666 \r
2667 /* page-align a size */\r
2668 #define page_align(S)\\r
2669  (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE))\r
2670 \r
2671 /* granularity-align a size */\r
2672 #define granularity_align(S)\\r
2673   (((S) + (mparams.granularity - SIZE_T_ONE))\\r
2674    & ~(mparams.granularity - SIZE_T_ONE))\r
2675 \r
2676 \r
2677 /* For mmap, use granularity alignment on windows, else page-align */\r
2678 #ifdef WIN32\r
2679 #define mmap_align(S) granularity_align(S)\r
2680 #else\r
2681 #define mmap_align(S) page_align(S)\r
2682 #endif\r
2683 \r
2684 /* For sys_alloc, enough padding to ensure can malloc request on success */\r
2685 #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT)\r
2686 \r
2687 #define is_page_aligned(S)\\r
2688    (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)\r
2689 #define is_granularity_aligned(S)\\r
2690    (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)\r
2691 \r
2692 /*  True if segment S holds address A */\r
2693 #define segment_holds(S, A)\\r
2694   ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)\r
2695 \r
2696 /* Return segment holding given address */\r
2697 static msegmentptr segment_holding(mstate m, char* addr) {\r
2698   msegmentptr sp = &m->seg;\r
2699   for (;;) {\r
2700     if (addr >= sp->base && addr < sp->base + sp->size)\r
2701       return sp;\r
2702     if ((sp = sp->next) == 0)\r
2703       return 0;\r
2704   }\r
2705 }\r
2706 \r
2707 /* Return true if segment contains a segment link */\r
2708 static int has_segment_link(mstate m, msegmentptr ss) {\r
2709   msegmentptr sp = &m->seg;\r
2710   for (;;) {\r
2711     if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)\r
2712       return 1;\r
2713     if ((sp = sp->next) == 0)\r
2714       return 0;\r
2715   }\r
2716 }\r
2717 \r
2718 #ifndef MORECORE_CANNOT_TRIM\r
2719 #define should_trim(M,s)  ((s) > (M)->trim_check)\r
2720 #else  /* MORECORE_CANNOT_TRIM */\r
2721 #define should_trim(M,s)  (0)\r
2722 #endif /* MORECORE_CANNOT_TRIM */\r
2723 \r
2724 /*\r
2725   TOP_FOOT_SIZE is padding at the end of a segment, including space\r
2726   that may be needed to place segment records and fenceposts when new\r
2727   noncontiguous segments are added.\r
2728 */\r
2729 #define TOP_FOOT_SIZE\\r
2730   (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)\r
2731 \r
2732 \r
2733 /* -------------------------------  Hooks -------------------------------- */\r
2734 \r
2735 /*\r
2736   PREACTION should be defined to return 0 on success, and nonzero on\r
2737   failure. If you are not using locking, you can redefine these to do\r
2738   anything you like.\r
2739 */\r
2740 \r
2741 #if USE_LOCKS\r
2742 #define PREACTION(M)  ((use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)\r
2743 #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }\r
2744 #else /* USE_LOCKS */\r
2745 \r
2746 #ifndef PREACTION\r
2747 #define PREACTION(M) (0)\r
2748 #endif  /* PREACTION */\r
2749 \r
2750 #ifndef POSTACTION\r
2751 #define POSTACTION(M)\r
2752 #endif  /* POSTACTION */\r
2753 \r
2754 #endif /* USE_LOCKS */\r
2755 \r
2756 /*\r
2757   CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.\r
2758   USAGE_ERROR_ACTION is triggered on detected bad frees and\r
2759   reallocs. The argument p is an address that might have triggered the\r
2760   fault. It is ignored by the two predefined actions, but might be\r
2761   useful in custom actions that try to help diagnose errors.\r
2762 */\r
2763 \r
2764 #if PROCEED_ON_ERROR\r
2765 \r
2766 /* A count of the number of corruption errors causing resets */\r
2767 int malloc_corruption_error_count;\r
2768 \r
2769 /* default corruption action */\r
2770 static void reset_on_error(mstate m);\r
2771 \r
2772 #define CORRUPTION_ERROR_ACTION(m)  reset_on_error(m)\r
2773 #define USAGE_ERROR_ACTION(m, p)\r
2774 \r
2775 #else /* PROCEED_ON_ERROR */\r
2776 \r
2777 #ifndef CORRUPTION_ERROR_ACTION\r
2778 #define CORRUPTION_ERROR_ACTION(m) ABORT\r
2779 #endif /* CORRUPTION_ERROR_ACTION */\r
2780 \r
2781 #ifndef USAGE_ERROR_ACTION\r
2782 #define USAGE_ERROR_ACTION(m,p) ABORT\r
2783 #endif /* USAGE_ERROR_ACTION */\r
2784 \r
2785 #endif /* PROCEED_ON_ERROR */\r
2786 \r
2787 \r
2788 /* -------------------------- Debugging setup ---------------------------- */\r
2789 \r
2790 #if ! DEBUG\r
2791 \r
2792 #define check_free_chunk(M,P)\r
2793 #define check_inuse_chunk(M,P)\r
2794 #define check_malloced_chunk(M,P,N)\r
2795 #define check_mmapped_chunk(M,P)\r
2796 #define check_malloc_state(M)\r
2797 #define check_top_chunk(M,P)\r
2798 \r
2799 #else /* DEBUG */\r
2800 #define check_free_chunk(M,P)       do_check_free_chunk(M,P)\r
2801 #define check_inuse_chunk(M,P)      do_check_inuse_chunk(M,P)\r
2802 #define check_top_chunk(M,P)        do_check_top_chunk(M,P)\r
2803 #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)\r
2804 #define check_mmapped_chunk(M,P)    do_check_mmapped_chunk(M,P)\r
2805 #define check_malloc_state(M)       do_check_malloc_state(M)\r
2806 \r
2807 static void   do_check_any_chunk(mstate m, mchunkptr p);\r
2808 static void   do_check_top_chunk(mstate m, mchunkptr p);\r
2809 static void   do_check_mmapped_chunk(mstate m, mchunkptr p);\r
2810 static void   do_check_inuse_chunk(mstate m, mchunkptr p);\r
2811 static void   do_check_free_chunk(mstate m, mchunkptr p);\r
2812 static void   do_check_malloced_chunk(mstate m, void* mem, size_t s);\r
2813 static void   do_check_tree(mstate m, tchunkptr t);\r
2814 static void   do_check_treebin(mstate m, bindex_t i);\r
2815 static void   do_check_smallbin(mstate m, bindex_t i);\r
2816 static void   do_check_malloc_state(mstate m);\r
2817 static int    bin_find(mstate m, mchunkptr x);\r
2818 static size_t traverse_and_check(mstate m);\r
2819 #endif /* DEBUG */\r
2820 \r
2821 /* ---------------------------- Indexing Bins ---------------------------- */\r
2822 \r
2823 #define is_small(s)         (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)\r
2824 #define small_index(s)      (bindex_t)((s)  >> SMALLBIN_SHIFT)\r
2825 #define small_index2size(i) ((i)  << SMALLBIN_SHIFT)\r
2826 #define MIN_SMALL_INDEX     (small_index(MIN_CHUNK_SIZE))\r
2827 \r
2828 /* addressing by index. See above about smallbin repositioning */\r
2829 #define smallbin_at(M, i)   ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))\r
2830 #define treebin_at(M,i)     (&((M)->treebins[i]))\r
2831 \r
2832 /* assign tree index for size S to variable I. Use x86 asm if possible  */\r
2833 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))\r
2834 #define compute_tree_index(S, I)\\r
2835 {\\r
2836   unsigned int X = S >> TREEBIN_SHIFT;\\r
2837   if (X == 0)\\r
2838     I = 0;\\r
2839   else if (X > 0xFFFF)\\r
2840     I = NTREEBINS-1;\\r
2841   else {\\r
2842     unsigned int K = (unsigned) sizeof(X)*__CHAR_BIT__ - 1 - (unsigned) __builtin_clz(X); \\r
2843     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\\r
2844   }\\r
2845 }\r
2846 \r
2847 #elif defined (__INTEL_COMPILER)\r
2848 #define compute_tree_index(S, I)\\r
2849 {\\r
2850   size_t X = S >> TREEBIN_SHIFT;\\r
2851   if (X == 0)\\r
2852     I = 0;\\r
2853   else if (X > 0xFFFF)\\r
2854     I = NTREEBINS-1;\\r
2855   else {\\r
2856     unsigned int K = _bit_scan_reverse (X); \\r
2857     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\\r
2858   }\\r
2859 }\r
2860 \r
2861 #elif defined(_MSC_VER) && _MSC_VER>=1300\r
2862 #define compute_tree_index(S, I)\\r
2863 {\\r
2864   size_t X = S >> TREEBIN_SHIFT;\\r
2865   if (X == 0)\\r
2866     I = 0;\\r
2867   else if (X > 0xFFFF)\\r
2868     I = NTREEBINS-1;\\r
2869   else {\\r
2870     unsigned int K;\\r
2871     _BitScanReverse((DWORD *) &K, (DWORD) X);\\r
2872     I =  (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\\r
2873   }\\r
2874 }\r
2875 \r
2876 #else /* GNUC */\r
2877 #define compute_tree_index(S, I)\\r
2878 {\\r
2879   size_t X = S >> TREEBIN_SHIFT;\\r
2880   if (X == 0)\\r
2881     I = 0;\\r
2882   else if (X > 0xFFFF)\\r
2883     I = NTREEBINS-1;\\r
2884   else {\\r
2885     unsigned int Y = (unsigned int)X;\\r
2886     unsigned int N = ((Y - 0x100) >> 16) & 8;\\r
2887     unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\\r
2888     N += K;\\r
2889     N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\\r
2890     K = 14 - N + ((Y <<= K) >> 15);\\r
2891     I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\\r
2892   }\\r
2893 }\r
2894 #endif /* GNUC */\r
2895 \r
2896 /* Bit representing maximum resolved size in a treebin at i */\r
2897 #define bit_for_tree_index(i) \\r
2898    (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)\r
2899 \r
2900 /* Shift placing maximum resolved bit in a treebin at i as sign bit */\r
2901 #define leftshift_for_tree_index(i) \\r
2902    ((i == NTREEBINS-1)? 0 : \\r
2903     ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))\r
2904 \r
2905 /* The size of the smallest chunk held in bin with index i */\r
2906 #define minsize_for_tree_index(i) \\r
2907    ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) |  \\r
2908    (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))\r
2909 \r
2910 \r
2911 /* ------------------------ Operations on bin maps ----------------------- */\r
2912 \r
2913 /* bit corresponding to given index */\r
2914 #define idx2bit(i)              ((binmap_t)(1) << (i))\r
2915 \r
2916 /* Mark/Clear bits with given index */\r
2917 #define mark_smallmap(M,i)      ((M)->smallmap |=  idx2bit(i))\r
2918 #define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))\r
2919 #define smallmap_is_marked(M,i) ((M)->smallmap &   idx2bit(i))\r
2920 \r
2921 #define mark_treemap(M,i)       ((M)->treemap  |=  idx2bit(i))\r
2922 #define clear_treemap(M,i)      ((M)->treemap  &= ~idx2bit(i))\r
2923 #define treemap_is_marked(M,i)  ((M)->treemap  &   idx2bit(i))\r
2924 \r
2925 /* isolate the least set bit of a bitmap */\r
2926 #define least_bit(x)         ((x) & -(x))\r
2927 \r
2928 /* mask with all bits to left of least bit of x on */\r
2929 #define left_bits(x)         ((x<<1) | -(x<<1))\r
2930 \r
2931 /* mask with all bits to left of or equal to least bit of x on */\r
2932 #define same_or_left_bits(x) ((x) | -(x))\r
2933 \r
2934 /* index corresponding to given bit. Use x86 asm if possible */\r
2935 \r
2936 #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))\r
2937 #define compute_bit2idx(X, I)\\r
2938 {\\r
2939   unsigned int J;\\r
2940   J = __builtin_ctz(X); \\r
2941   I = (bindex_t)J;\\r
2942 }\r
2943 \r
2944 #elif defined (__INTEL_COMPILER)\r
2945 #define compute_bit2idx(X, I)\\r
2946 {\\r
2947   unsigned int J;\\r
2948   J = _bit_scan_forward (X); \\r
2949   I = (bindex_t)J;\\r
2950 }\r
2951 \r
2952 #elif defined(_MSC_VER) && _MSC_VER>=1300\r
2953 #define compute_bit2idx(X, I)\\r
2954 {\\r
2955   unsigned int J;\\r
2956   _BitScanForward((DWORD *) &J, X);\\r
2957   I = (bindex_t)J;\\r
2958 }\r
2959 \r
2960 #elif USE_BUILTIN_FFS\r
2961 #define compute_bit2idx(X, I) I = ffs(X)-1\r
2962 \r
2963 #else\r
2964 #define compute_bit2idx(X, I)\\r
2965 {\\r
2966   unsigned int Y = X - 1;\\r
2967   unsigned int K = Y >> (16-4) & 16;\\r
2968   unsigned int N = K;        Y >>= K;\\r
2969   N += K = Y >> (8-3) &  8;  Y >>= K;\\r
2970   N += K = Y >> (4-2) &  4;  Y >>= K;\\r
2971   N += K = Y >> (2-1) &  2;  Y >>= K;\\r
2972   N += K = Y >> (1-0) &  1;  Y >>= K;\\r
2973   I = (bindex_t)(N + Y);\\r
2974 }\r
2975 #endif /* GNUC */\r
2976 \r
2977 \r
2978 /* ----------------------- Runtime Check Support ------------------------- */\r
2979 \r
2980 /*\r
2981   For security, the main invariant is that malloc/free/etc never\r
2982   writes to a static address other than malloc_state, unless static\r
2983   malloc_state itself has been corrupted, which cannot occur via\r
2984   malloc (because of these checks). In essence this means that we\r
2985   believe all pointers, sizes, maps etc held in malloc_state, but\r
2986   check all of those linked or offsetted from other embedded data\r
2987   structures.  These checks are interspersed with main code in a way\r
2988   that tends to minimize their run-time cost.\r
2989 \r
2990   When FOOTERS is defined, in addition to range checking, we also\r
2991   verify footer fields of inuse chunks, which can be used guarantee\r
2992   that the mstate controlling malloc/free is intact.  This is a\r
2993   streamlined version of the approach described by William Robertson\r
2994   et al in "Run-time Detection of Heap-based Overflows" LISA'03\r
2995   http://www.usenix.org/events/lisa03/tech/robertson.html The footer\r
2996   of an inuse chunk holds the xor of its mstate and a random seed,\r
2997   that is checked upon calls to free() and realloc().  This is\r
2998   (probabalistically) unguessable from outside the program, but can be\r
2999   computed by any code successfully malloc'ing any chunk, so does not\r
3000   itself provide protection against code that has already broken\r
3001   security through some other means.  Unlike Robertson et al, we\r
3002   always dynamically check addresses of all offset chunks (previous,\r
3003   next, etc). This turns out to be cheaper than relying on hashes.\r
3004 */\r
3005 \r
3006 #if !INSECURE\r
3007 /* Check if address a is at least as high as any from MORECORE or MMAP */\r
3008 #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)\r
3009 /* Check if address of next chunk n is higher than base chunk p */\r
3010 #define ok_next(p, n)    ((char*)(p) < (char*)(n))\r
3011 /* Check if p has inuse status */\r
3012 #define ok_inuse(p)     is_inuse(p)\r
3013 /* Check if p has its pinuse bit on */\r
3014 #define ok_pinuse(p)     pinuse(p)\r
3015 \r
3016 #else /* !INSECURE */\r
3017 #define ok_address(M, a) (1)\r
3018 #define ok_next(b, n)    (1)\r
3019 #define ok_inuse(p)      (1)\r
3020 #define ok_pinuse(p)     (1)\r
3021 #endif /* !INSECURE */\r
3022 \r
3023 #if (FOOTERS && !INSECURE)\r
3024 /* Check if (alleged) mstate m has expected magic field */\r
3025 #define ok_magic(M)      ((M)->magic == mparams.magic)\r
3026 #else  /* (FOOTERS && !INSECURE) */\r
3027 #define ok_magic(M)      (1)\r
3028 #endif /* (FOOTERS && !INSECURE) */\r
3029 \r
3030 /* In gcc, use __builtin_expect to minimize impact of checks */\r
3031 #if !INSECURE\r
3032 #if defined(__GNUC__) && __GNUC__ >= 3\r
3033 #define RTCHECK(e)  __builtin_expect(e, 1)\r
3034 #else /* GNUC */\r
3035 #define RTCHECK(e)  (e)\r
3036 #endif /* GNUC */\r
3037 #else /* !INSECURE */\r
3038 #define RTCHECK(e)  (1)\r
3039 #endif /* !INSECURE */\r
3040 \r
3041 /* macros to set up inuse chunks with or without footers */\r
3042 \r
3043 #if !FOOTERS\r
3044 \r
3045 #define mark_inuse_foot(M,p,s)\r
3046 \r
3047 /* Macros for setting head/foot of non-mmapped chunks */\r
3048 \r
3049 /* Set cinuse bit and pinuse bit of next chunk */\r
3050 #define set_inuse(M,p,s)\\r
3051   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\\r
3052   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)\r
3053 \r
3054 /* Set cinuse and pinuse of this chunk and pinuse of next chunk */\r
3055 #define set_inuse_and_pinuse(M,p,s)\\r
3056   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\\r
3057   ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)\r
3058 \r
3059 /* Set size, cinuse and pinuse bit of this chunk */\r
3060 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\\r
3061   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))\r
3062 \r
3063 #else /* FOOTERS */\r
3064 \r
3065 /* Set foot of inuse chunk to be xor of mstate and seed */\r
3066 #define mark_inuse_foot(M,p,s)\\r
3067   (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))\r
3068 \r
3069 #define get_mstate_for(p)\\r
3070   ((mstate)(((mchunkptr)((char*)(p) +\\r
3071     (chunksize(p))))->prev_foot ^ mparams.magic))\r
3072 \r
3073 #define set_inuse(M,p,s)\\r
3074   ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\\r
3075   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \\r
3076   mark_inuse_foot(M,p,s))\r
3077 \r
3078 #define set_inuse_and_pinuse(M,p,s)\\r
3079   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\\r
3080   (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\\r
3081  mark_inuse_foot(M,p,s))\r
3082 \r
3083 #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\\r
3084   ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\\r
3085   mark_inuse_foot(M, p, s))\r
3086 \r
3087 #endif /* !FOOTERS */\r
3088 \r
3089 /* ---------------------------- setting mparams -------------------------- */\r
3090 \r
3091 /* Initialize mparams */\r
3092 static int init_mparams(void) {\r
3093 #ifdef NEED_GLOBAL_LOCK_INIT\r
3094     call_once(&malloc_global_mutex_init_once, init_malloc_global_mutex);\r
3095 #endif\r
3096 \r
3097   ACQUIRE_MALLOC_GLOBAL_LOCK();\r
3098   if (mparams.magic == 0) {\r
3099     size_t magic;\r
3100     size_t psize;\r
3101     size_t gsize;\r
3102 \r
3103 #ifndef WIN32\r
3104     psize = malloc_getpagesize;\r
3105     gsize = ((DEFAULT_GRANULARITY != 0)? DEFAULT_GRANULARITY : psize);\r
3106 #else /* WIN32 */\r
3107     {\r
3108       SYSTEM_INFO system_info;\r
3109       GetSystemInfo(&system_info);\r
3110       psize = system_info.dwPageSize;\r
3111       gsize = ((DEFAULT_GRANULARITY != 0)?\r
3112                DEFAULT_GRANULARITY : system_info.dwAllocationGranularity);\r
3113     }\r
3114 #endif /* WIN32 */\r
3115 \r
3116     /* Sanity-check configuration:\r
3117        size_t must be unsigned and as wide as pointer type.\r
3118        ints must be at least 4 bytes.\r
3119        alignment must be at least 8.\r
3120        Alignment, min chunk size, and page size must all be powers of 2.\r
3121     */\r
3122     if ((sizeof(size_t) != sizeof(char*)) ||\r
3123         (MAX_SIZE_T < MIN_CHUNK_SIZE)  ||\r
3124         (sizeof(int) < 4)  ||\r
3125         (MALLOC_ALIGNMENT < (size_t)8U) ||\r
3126         ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||\r
3127         ((MCHUNK_SIZE      & (MCHUNK_SIZE-SIZE_T_ONE))      != 0) ||\r
3128         ((gsize            & (gsize-SIZE_T_ONE))            != 0) ||\r
3129         ((psize            & (psize-SIZE_T_ONE))            != 0))\r
3130       ABORT;\r
3131 \r
3132     mparams.granularity = gsize;\r
3133     mparams.page_size = psize;\r
3134     mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;\r
3135     mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;\r
3136 #if MORECORE_CONTIGUOUS\r
3137     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;\r
3138 #else  /* MORECORE_CONTIGUOUS */\r
3139     mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;\r
3140 #endif /* MORECORE_CONTIGUOUS */\r
3141 \r
3142 #if !ONLY_MSPACES\r
3143     /* Set up lock for main malloc area */\r
3144     gm->mflags = mparams.default_mflags;\r
3145     (void)INITIAL_LOCK(&gm->mutex);\r
3146 #endif\r
3147 \r
3148     {\r
3149 #if USE_DEV_RANDOM\r
3150       int fd;\r
3151       unsigned char buf[sizeof(size_t)];\r
3152       /* Try to use /dev/urandom, else fall back on using time */\r
3153       if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&\r
3154           read(fd, buf, sizeof(buf)) == sizeof(buf)) {\r
3155         magic = *((size_t *) buf);\r
3156         close(fd);\r
3157       }\r
3158       else\r
3159 #endif /* USE_DEV_RANDOM */\r
3160 #ifdef WIN32\r
3161         magic = (size_t)(GetTickCount() ^ (size_t)0x55555555U);\r
3162 #elif defined(LACKS_TIME_H)\r
3163       magic = (size_t)&magic ^ (size_t)0x55555555U;\r
3164 #else\r
3165         magic = (size_t)(time(0) ^ (size_t)0x55555555U);\r
3166 #endif\r
3167       magic |= (size_t)8U;    /* ensure nonzero */\r
3168       magic &= ~(size_t)7U;   /* improve chances of fault for bad values */\r
3169       /* Until memory modes commonly available, use volatile-write */\r
3170       (*(volatile size_t *)(&(mparams.magic))) = magic;\r
3171     }\r
3172   }\r
3173 \r
3174   RELEASE_MALLOC_GLOBAL_LOCK();\r
3175   return 1;\r
3176 }\r
3177 \r
3178 /* support for mallopt */\r
3179 static int change_mparam(int param_number, int value) {\r
3180   size_t val;\r
3181   ensure_initialization();\r
3182   val = (value == -1)? MAX_SIZE_T : (size_t)value;\r
3183   switch(param_number) {\r
3184   case M_TRIM_THRESHOLD:\r
3185     mparams.trim_threshold = val;\r
3186     return 1;\r
3187   case M_GRANULARITY:\r
3188     if (val >= mparams.page_size && ((val & (val-1)) == 0)) {\r
3189       mparams.granularity = val;\r
3190       return 1;\r
3191     }\r
3192     else\r
3193       return 0;\r
3194   case M_MMAP_THRESHOLD:\r
3195     mparams.mmap_threshold = val;\r
3196     return 1;\r
3197   default:\r
3198     return 0;\r
3199   }\r
3200 }\r
3201 \r
3202 #if DEBUG\r
3203 /* ------------------------- Debugging Support --------------------------- */\r
3204 \r
3205 /* Check properties of any chunk, whether free, inuse, mmapped etc  */\r
3206 static void do_check_any_chunk(mstate m, mchunkptr p) {\r
3207   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));\r
3208   assert(ok_address(m, p));\r
3209 }\r
3210 \r
3211 /* Check properties of top chunk */\r
3212 static void do_check_top_chunk(mstate m, mchunkptr p) {\r
3213   msegmentptr sp = segment_holding(m, (char*)p);\r
3214   size_t  sz = p->head & ~INUSE_BITS; /* third-lowest bit can be set! */\r
3215   assert(sp != 0);\r
3216   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));\r
3217   assert(ok_address(m, p));\r
3218   assert(sz == m->topsize);\r
3219   assert(sz > 0);\r
3220   assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);\r
3221   assert(pinuse(p));\r
3222   assert(!pinuse(chunk_plus_offset(p, sz)));\r
3223 }\r
3224 \r
3225 /* Check properties of (inuse) mmapped chunks */\r
3226 static void do_check_mmapped_chunk(mstate m, mchunkptr p) {\r
3227   size_t  sz = chunksize(p);\r
3228   size_t len = (sz + (p->prev_foot) + MMAP_FOOT_PAD);\r
3229   assert(is_mmapped(p));\r
3230   assert(use_mmap(m));\r
3231   assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));\r
3232   assert(ok_address(m, p));\r
3233   assert(!is_small(sz));\r
3234   assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);\r
3235   assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);\r
3236   assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);\r
3237 }\r
3238 \r
3239 /* Check properties of inuse chunks */\r
3240 static void do_check_inuse_chunk(mstate m, mchunkptr p) {\r
3241   do_check_any_chunk(m, p);\r
3242   assert(is_inuse(p));\r
3243   assert(next_pinuse(p));\r
3244   /* If not pinuse and not mmapped, previous chunk has OK offset */\r
3245   assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);\r
3246   if (is_mmapped(p))\r
3247     do_check_mmapped_chunk(m, p);\r
3248 }\r
3249 \r
3250 /* Check properties of free chunks */\r
3251 static void do_check_free_chunk(mstate m, mchunkptr p) {\r
3252   size_t sz = chunksize(p);\r
3253   mchunkptr next = chunk_plus_offset(p, sz);\r
3254   do_check_any_chunk(m, p);\r
3255   assert(!is_inuse(p));\r
3256   assert(!next_pinuse(p));\r
3257   assert (!is_mmapped(p));\r
3258   if (p != m->dv && p != m->top) {\r
3259     if (sz >= MIN_CHUNK_SIZE) {\r
3260       assert((sz & CHUNK_ALIGN_MASK) == 0);\r
3261       assert(is_aligned(chunk2mem(p)));\r
3262       assert(next->prev_foot == sz);\r
3263       assert(pinuse(p));\r
3264       assert (next == m->top || is_inuse(next));\r
3265       assert(p->fd->bk == p);\r
3266       assert(p->bk->fd == p);\r
3267     }\r
3268     else  /* markers are always of size SIZE_T_SIZE */\r
3269       assert(sz == SIZE_T_SIZE);\r
3270   }\r
3271 }\r
3272 \r
3273 /* Check properties of malloced chunks at the point they are malloced */\r
3274 static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {\r
3275   if (mem != 0) {\r
3276     mchunkptr p = mem2chunk(mem);\r
3277     size_t sz = p->head & ~INUSE_BITS;\r
3278     do_check_inuse_chunk(m, p);\r
3279     assert((sz & CHUNK_ALIGN_MASK) == 0);\r
3280     assert(sz >= MIN_CHUNK_SIZE);\r
3281     assert(sz >= s);\r
3282     /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */\r
3283     assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));\r
3284   }\r
3285 }\r
3286 \r
3287 /* Check a tree and its subtrees.  */\r
3288 static void do_check_tree(mstate m, tchunkptr t) {\r
3289   tchunkptr head = 0;\r
3290   tchunkptr u = t;\r
3291   bindex_t tindex = t->index;\r
3292   size_t tsize = chunksize(t);\r
3293   bindex_t idx;\r
3294   compute_tree_index(tsize, idx);\r
3295   assert(tindex == idx);\r
3296   assert(tsize >= MIN_LARGE_SIZE);\r
3297   assert(tsize >= minsize_for_tree_index(idx));\r
3298   assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));\r
3299 \r
3300   do { /* traverse through chain of same-sized nodes */\r
3301     do_check_any_chunk(m, ((mchunkptr)u));\r
3302     assert(u->index == tindex);\r
3303     assert(chunksize(u) == tsize);\r
3304     assert(!is_inuse(u));\r
3305     assert(!next_pinuse(u));\r
3306     assert(u->fd->bk == u);\r
3307     assert(u->bk->fd == u);\r
3308     if (u->parent == 0) {\r
3309       assert(u->child[0] == 0);\r
3310       assert(u->child[1] == 0);\r
3311     }\r
3312     else {\r
3313       assert(head == 0); /* only one node on chain has parent */\r
3314       head = u;\r
3315       assert(u->parent != u);\r
3316       assert (u->parent->child[0] == u ||\r
3317               u->parent->child[1] == u ||\r
3318               *((tbinptr*)(u->parent)) == u);\r
3319       if (u->child[0] != 0) {\r
3320         assert(u->child[0]->parent == u);\r
3321         assert(u->child[0] != u);\r
3322         do_check_tree(m, u->child[0]);\r
3323       }\r
3324       if (u->child[1] != 0) {\r
3325         assert(u->child[1]->parent == u);\r
3326         assert(u->child[1] != u);\r
3327         do_check_tree(m, u->child[1]);\r
3328       }\r
3329       if (u->child[0] != 0 && u->child[1] != 0) {\r
3330         assert(chunksize(u->child[0]) < chunksize(u->child[1]));\r
3331       }\r
3332     }\r
3333     u = u->fd;\r
3334   } while (u != t);\r
3335   assert(head != 0);\r
3336 }\r
3337 \r
3338 /*  Check all the chunks in a treebin.  */\r
3339 static void do_check_treebin(mstate m, bindex_t i) {\r
3340   tbinptr* tb = treebin_at(m, i);\r
3341   tchunkptr t = *tb;\r
3342   int empty = (m->treemap & (1U << i)) == 0;\r
3343   if (t == 0)\r
3344     assert(empty);\r
3345   if (!empty)\r
3346     do_check_tree(m, t);\r
3347 }\r
3348 \r
3349 /*  Check all the chunks in a smallbin.  */\r
3350 static void do_check_smallbin(mstate m, bindex_t i) {\r
3351   sbinptr b = smallbin_at(m, i);\r
3352   mchunkptr p = b->bk;\r
3353   unsigned int empty = (m->smallmap & (1U << i)) == 0;\r
3354   if (p == b)\r
3355     assert(empty);\r
3356   if (!empty) {\r
3357     for (; p != b; p = p->bk) {\r
3358       size_t size = chunksize(p);\r
3359       mchunkptr q;\r
3360       /* each chunk claims to be free */\r
3361       do_check_free_chunk(m, p);\r
3362       /* chunk belongs in bin */\r
3363       assert(small_index(size) == i);\r
3364       assert(p->bk == b || chunksize(p->bk) == chunksize(p));\r
3365       /* chunk is followed by an inuse chunk */\r
3366       q = next_chunk(p);\r
3367       if (q->head != FENCEPOST_HEAD)\r
3368         do_check_inuse_chunk(m, q);\r
3369     }\r
3370   }\r
3371 }\r
3372 \r
3373 /* Find x in a bin. Used in other check functions. */\r
3374 static int bin_find(mstate m, mchunkptr x) {\r
3375   size_t size = chunksize(x);\r
3376   if (is_small(size)) {\r
3377     bindex_t sidx = small_index(size);\r
3378     sbinptr b = smallbin_at(m, sidx);\r
3379     if (smallmap_is_marked(m, sidx)) {\r
3380       mchunkptr p = b;\r
3381       do {\r
3382         if (p == x)\r
3383           return 1;\r
3384       } while ((p = p->fd) != b);\r
3385     }\r
3386   }\r
3387   else {\r
3388     bindex_t tidx;\r
3389     compute_tree_index(size, tidx);\r
3390     if (treemap_is_marked(m, tidx)) {\r
3391       tchunkptr t = *treebin_at(m, tidx);\r
3392       size_t sizebits = size << leftshift_for_tree_index(tidx);\r
3393       while (t != 0 && chunksize(t) != size) {\r
3394         t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];\r
3395         sizebits <<= 1;\r
3396       }\r
3397       if (t != 0) {\r
3398         tchunkptr u = t;\r
3399         do {\r
3400           if (u == (tchunkptr)x)\r
3401             return 1;\r
3402         } while ((u = u->fd) != t);\r
3403       }\r
3404     }\r
3405   }\r
3406   return 0;\r
3407 }\r
3408 \r
3409 /* Traverse each chunk and check it; return total */\r
3410 static size_t traverse_and_check(mstate m) {\r
3411   size_t sum = 0;\r
3412   if (is_initialized(m)) {\r
3413     msegmentptr s = &m->seg;\r
3414     sum += m->topsize + TOP_FOOT_SIZE;\r
3415     while (s != 0) {\r
3416       mchunkptr q = align_as_chunk(s->base);\r
3417       mchunkptr lastq = 0;\r
3418       assert(pinuse(q));\r
3419       while (segment_holds(s, q) &&\r
3420              q != m->top && q->head != FENCEPOST_HEAD) {\r
3421         sum += chunksize(q);\r
3422         if (is_inuse(q)) {\r
3423           assert(!bin_find(m, q));\r
3424           do_check_inuse_chunk(m, q);\r
3425         }\r
3426         else {\r
3427           assert(q == m->dv || bin_find(m, q));\r
3428           assert(lastq == 0 || is_inuse(lastq)); /* Not 2 consecutive free */\r
3429           do_check_free_chunk(m, q);\r
3430         }\r
3431         lastq = q;\r
3432         q = next_chunk(q);\r
3433       }\r
3434       s = s->next;\r
3435     }\r
3436   }\r
3437   return sum;\r
3438 }\r
3439 \r
3440 \r
3441 /* Check all properties of malloc_state. */\r
3442 static void do_check_malloc_state(mstate m) {\r
3443   bindex_t i;\r
3444   size_t total;\r
3445   /* check bins */\r
3446   for (i = 0; i < NSMALLBINS; ++i)\r
3447     do_check_smallbin(m, i);\r
3448   for (i = 0; i < NTREEBINS; ++i)\r
3449     do_check_treebin(m, i);\r
3450 \r
3451   if (m->dvsize != 0) { /* check dv chunk */\r
3452     do_check_any_chunk(m, m->dv);\r
3453     assert(m->dvsize == chunksize(m->dv));\r
3454     assert(m->dvsize >= MIN_CHUNK_SIZE);\r
3455     assert(bin_find(m, m->dv) == 0);\r
3456   }\r
3457 \r
3458   if (m->top != 0) {   /* check top chunk */\r
3459     do_check_top_chunk(m, m->top);\r
3460     /*assert(m->topsize == chunksize(m->top)); redundant */\r
3461     assert(m->topsize > 0);\r
3462     assert(bin_find(m, m->top) == 0);\r
3463   }\r
3464 \r
3465   total = traverse_and_check(m);\r
3466   assert(total <= m->footprint);\r
3467   assert(m->footprint <= m->max_footprint);\r
3468 }\r
3469 #endif /* DEBUG */\r
3470 \r
3471 /* ----------------------------- statistics ------------------------------ */\r
3472 \r
3473 #if !NO_MALLINFO\r
3474 static struct mallinfo internal_mallinfo(mstate m) {\r
3475   struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };\r
3476   ensure_initialization();\r
3477   if (!PREACTION(m)) {\r
3478     check_malloc_state(m);\r
3479     if (is_initialized(m)) {\r
3480       size_t nfree = SIZE_T_ONE; /* top always free */\r
3481       size_t mfree = m->topsize + TOP_FOOT_SIZE;\r
3482       size_t sum = mfree;\r
3483       msegmentptr s = &m->seg;\r
3484       while (s != 0) {\r
3485         mchunkptr q = align_as_chunk(s->base);\r
3486         while (segment_holds(s, q) &&\r
3487                q != m->top && q->head != FENCEPOST_HEAD) {\r
3488           size_t sz = chunksize(q);\r
3489           sum += sz;\r
3490           if (!is_inuse(q)) {\r
3491             mfree += sz;\r
3492             ++nfree;\r
3493           }\r
3494           q = next_chunk(q);\r
3495         }\r
3496         s = s->next;\r
3497       }\r
3498 \r
3499       nm.arena    = sum;\r
3500       nm.ordblks  = nfree;\r
3501       nm.hblkhd   = m->footprint - sum;\r
3502       nm.usmblks  = m->max_footprint;\r
3503       nm.uordblks = m->footprint - mfree;\r
3504       nm.fordblks = mfree;\r
3505       nm.keepcost = m->topsize;\r
3506     }\r
3507 \r
3508     POSTACTION(m);\r
3509   }\r
3510   return nm;\r
3511 }\r
3512 #endif /* !NO_MALLINFO */\r
3513 \r
3514 #if !NO_MALLOC_STATS\r
3515 static void internal_malloc_stats(mstate m) {\r
3516   ensure_initialization();\r
3517   if (!PREACTION(m)) {\r
3518     size_t maxfp = 0;\r
3519     size_t fp = 0;\r
3520     size_t used = 0;\r
3521     check_malloc_state(m);\r
3522     if (is_initialized(m)) {\r
3523       msegmentptr s = &m->seg;\r
3524       maxfp = m->max_footprint;\r
3525       fp = m->footprint;\r
3526       used = fp - (m->topsize + TOP_FOOT_SIZE);\r
3527 \r
3528       while (s != 0) {\r
3529         mchunkptr q = align_as_chunk(s->base);\r
3530         while (segment_holds(s, q) &&\r
3531                q != m->top && q->head != FENCEPOST_HEAD) {\r
3532           if (!is_inuse(q))\r
3533             used -= chunksize(q);\r
3534           q = next_chunk(q);\r
3535         }\r
3536         s = s->next;\r
3537       }\r
3538     }\r
3539     POSTACTION(m); /* drop lock */\r
3540     fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));\r
3541     fprintf(stderr, "system bytes     = %10lu\n", (unsigned long)(fp));\r
3542     fprintf(stderr, "in use bytes     = %10lu\n", (unsigned long)(used));\r
3543   }\r
3544 }\r
3545 #endif /* NO_MALLOC_STATS */\r
3546 \r
3547 /* ----------------------- Operations on smallbins ----------------------- */\r
3548 \r
3549 /*\r
3550   Various forms of linking and unlinking are defined as macros.  Even\r
3551   the ones for trees, which are very long but have very short typical\r
3552   paths.  This is ugly but reduces reliance on inlining support of\r
3553   compilers.\r
3554 */\r
3555 \r
3556 /* Link a free chunk into a smallbin  */\r
3557 #define insert_small_chunk(M, P, S) {\\r
3558   bindex_t I  = small_index(S);\\r
3559   mchunkptr B = smallbin_at(M, I);\\r
3560   mchunkptr F = B;\\r
3561   assert(S >= MIN_CHUNK_SIZE);\\r
3562   if (!smallmap_is_marked(M, I))\\r
3563     mark_smallmap(M, I);\\r
3564   else if (RTCHECK(ok_address(M, B->fd)))\\r
3565     F = B->fd;\\r
3566   else {\\r
3567     CORRUPTION_ERROR_ACTION(M);\\r
3568   }\\r
3569   B->fd = P;\\r
3570   F->bk = P;\\r
3571   P->fd = F;\\r
3572   P->bk = B;\\r
3573 }\r
3574 \r
3575 /* Unlink a chunk from a smallbin  */\r
3576 #define unlink_small_chunk(M, P, S) {\\r
3577   mchunkptr F = P->fd;\\r
3578   mchunkptr B = P->bk;\\r
3579   bindex_t I = small_index(S);\\r
3580   assert(P != B);\\r
3581   assert(P != F);\\r
3582   assert(chunksize(P) == small_index2size(I));\\r
3583   if (RTCHECK(F == smallbin_at(M,I) || (ok_address(M, F) && F->bk == P))) { \\r
3584     if (B == F) {\\r
3585       clear_smallmap(M, I);\\r
3586     }\\r
3587     else if (RTCHECK(B == smallbin_at(M,I) ||\\r
3588                      (ok_address(M, B) && B->fd == P))) {\\r
3589       F->bk = B;\\r
3590       B->fd = F;\\r
3591     }\\r
3592     else {\\r
3593       CORRUPTION_ERROR_ACTION(M);\\r
3594     }\\r
3595   }\\r
3596   else {\\r
3597     CORRUPTION_ERROR_ACTION(M);\\r
3598   }\\r
3599 }\r
3600 \r
3601 /* Unlink the first chunk from a smallbin */\r
3602 #define unlink_first_small_chunk(M, B, P, I) {\\r
3603   mchunkptr F = P->fd;\\r
3604   assert(P != B);\\r
3605   assert(P != F);\\r
3606   assert(chunksize(P) == small_index2size(I));\\r
3607   if (B == F) {\\r
3608     clear_smallmap(M, I);\\r
3609   }\\r
3610   else if (RTCHECK(ok_address(M, F) && F->bk == P)) {\\r
3611     F->bk = B;\\r
3612     B->fd = F;\\r
3613   }\\r
3614   else {\\r
3615     CORRUPTION_ERROR_ACTION(M);\\r
3616   }\\r
3617 }\r
3618 \r
3619 /* Replace dv node, binning the old one */\r
3620 /* Used only when dvsize known to be small */\r
3621 #define replace_dv(M, P, S) {\\r
3622   size_t DVS = M->dvsize;\\r
3623   assert(is_small(DVS));\\r
3624   if (DVS != 0) {\\r
3625     mchunkptr DV = M->dv;\\r
3626     insert_small_chunk(M, DV, DVS);\\r
3627   }\\r
3628   M->dvsize = S;\\r
3629   M->dv = P;\\r
3630 }\r
3631 \r
3632 /* ------------------------- Operations on trees ------------------------- */\r
3633 \r
3634 /* Insert chunk into tree */\r
3635 #define insert_large_chunk(M, X, S) {\\r
3636   tbinptr* H;\\r
3637   bindex_t I;\\r
3638   compute_tree_index(S, I);\\r
3639   H = treebin_at(M, I);\\r
3640   X->index = I;\\r
3641   X->child[0] = X->child[1] = 0;\\r
3642   if (!treemap_is_marked(M, I)) {\\r
3643     mark_treemap(M, I);\\r
3644     *H = X;\\r
3645     X->parent = (tchunkptr)H;\\r
3646     X->fd = X->bk = X;\\r
3647   }\\r
3648   else {\\r
3649     tchunkptr T = *H;\\r
3650     size_t K = S << leftshift_for_tree_index(I);\\r
3651     for (;;) {\\r
3652       if (chunksize(T) != S) {\\r
3653         tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\\r
3654         K <<= 1;\\r
3655         if (*C != 0)\\r
3656           T = *C;\\r
3657         else if (RTCHECK(ok_address(M, C))) {\\r
3658           *C = X;\\r
3659           X->parent = T;\\r
3660           X->fd = X->bk = X;\\r
3661           break;\\r
3662         }\\r
3663         else {\\r
3664           CORRUPTION_ERROR_ACTION(M);\\r
3665           break;\\r
3666         }\\r
3667       }\\r
3668       else {\\r
3669         tchunkptr F = T->fd;\\r
3670         if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\\r
3671           T->fd = F->bk = X;\\r
3672           X->fd = F;\\r
3673           X->bk = T;\\r
3674           X->parent = 0;\\r
3675           break;\\r
3676         }\\r
3677         else {\\r
3678           CORRUPTION_ERROR_ACTION(M);\\r
3679           break;\\r
3680         }\\r
3681       }\\r
3682     }\\r
3683   }\\r
3684 }\r
3685 \r
3686 /*\r
3687   Unlink steps:\r
3688 \r
3689   1. If x is a chained node, unlink it from its same-sized fd/bk links\r
3690      and choose its bk node as its replacement.\r
3691   2. If x was the last node of its size, but not a leaf node, it must\r
3692      be replaced with a leaf node (not merely one with an open left or\r
3693      right), to make sure that lefts and rights of descendents\r
3694      correspond properly to bit masks.  We use the rightmost descendent\r
3695      of x.  We could use any other leaf, but this is easy to locate and\r
3696      tends to counteract removal of leftmosts elsewhere, and so keeps\r
3697      paths shorter than minimally guaranteed.  This doesn't loop much\r
3698      because on average a node in a tree is near the bottom.\r
3699   3. If x is the base of a chain (i.e., has parent links) relink\r
3700      x's parent and children to x's replacement (or null if none).\r
3701 */\r
3702 \r
3703 #define unlink_large_chunk(M, X) {\\r
3704   tchunkptr XP = X->parent;\\r
3705   tchunkptr R;\\r
3706   if (X->bk != X) {\\r
3707     tchunkptr F = X->fd;\\r
3708     R = X->bk;\\r
3709     if (RTCHECK(ok_address(M, F) && F->bk == X && R->fd == X)) {\\r
3710       F->bk = R;\\r
3711       R->fd = F;\\r
3712     }\\r
3713     else {\\r
3714       CORRUPTION_ERROR_ACTION(M);\\r
3715     }\\r
3716   }\\r
3717   else {\\r
3718     tchunkptr* RP;\\r
3719     if (((R = *(RP = &(X->child[1]))) != 0) ||\\r
3720         ((R = *(RP = &(X->child[0]))) != 0)) {\\r
3721       tchunkptr* CP;\\r
3722       while ((*(CP = &(R->child[1])) != 0) ||\\r
3723              (*(CP = &(R->child[0])) != 0)) {\\r
3724         R = *(RP = CP);\\r
3725       }\\r
3726       if (RTCHECK(ok_address(M, RP)))\\r
3727         *RP = 0;\\r
3728       else {\\r
3729         CORRUPTION_ERROR_ACTION(M);\\r
3730       }\\r
3731     }\\r
3732   }\\r
3733   if (XP != 0) {\\r
3734     tbinptr* H = treebin_at(M, X->index);\\r
3735     if (X == *H) {\\r
3736       if ((*H = R) == 0) \\r
3737         clear_treemap(M, X->index);\\r
3738     }\\r
3739     else if (RTCHECK(ok_address(M, XP))) {\\r
3740       if (XP->child[0] == X) \\r
3741         XP->child[0] = R;\\r
3742       else \\r
3743         XP->child[1] = R;\\r
3744     }\\r
3745     else\\r
3746       CORRUPTION_ERROR_ACTION(M);\\r
3747     if (R != 0) {\\r
3748       if (RTCHECK(ok_address(M, R))) {\\r
3749         tchunkptr C0, C1;\\r
3750         R->parent = XP;\\r
3751         if ((C0 = X->child[0]) != 0) {\\r
3752           if (RTCHECK(ok_address(M, C0))) {\\r
3753             R->child[0] = C0;\\r
3754             C0->parent = R;\\r
3755           }\\r
3756           else\\r
3757             CORRUPTION_ERROR_ACTION(M);\\r
3758         }\\r
3759         if ((C1 = X->child[1]) != 0) {\\r
3760           if (RTCHECK(ok_address(M, C1))) {\\r
3761             R->child[1] = C1;\\r
3762             C1->parent = R;\\r
3763           }\\r
3764           else\\r
3765             CORRUPTION_ERROR_ACTION(M);\\r
3766         }\\r
3767       }\\r
3768       else\\r
3769         CORRUPTION_ERROR_ACTION(M);\\r
3770     }\\r
3771   }\\r
3772 }\r
3773 \r
3774 /* Relays to large vs small bin operations */\r
3775 \r
3776 #define insert_chunk(M, P, S)\\r
3777   if (is_small(S)) insert_small_chunk(M, P, S)\\r
3778   else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }\r
3779 \r
3780 #define unlink_chunk(M, P, S)\\r
3781   if (is_small(S)) unlink_small_chunk(M, P, S)\\r
3782   else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }\r
3783 \r
3784 \r
3785 /* Relays to internal calls to malloc/free from realloc, memalign etc */\r
3786 \r
3787 #if ONLY_MSPACES\r
3788 #define internal_malloc(m, b) mspace_malloc(m, b)\r
3789 #define internal_free(m, mem) mspace_free(m,mem);\r
3790 #else /* ONLY_MSPACES */\r
3791 #if MSPACES\r
3792 #define internal_malloc(m, b)\\r
3793   ((m == gm)? dlmalloc(b) : mspace_malloc(m, b))\r
3794 #define internal_free(m, mem)\\r
3795    if (m == gm) dlfree(mem); else mspace_free(m,mem);\r
3796 #else /* MSPACES */\r
3797 #define internal_malloc(m, b) dlmalloc(b)\r
3798 #define internal_free(m, mem) dlfree(mem)\r
3799 #endif /* MSPACES */\r
3800 #endif /* ONLY_MSPACES */\r
3801 \r
3802 /* -----------------------  Direct-mmapping chunks ----------------------- */\r
3803 \r
3804 /*\r
3805   Directly mmapped chunks are set up with an offset to the start of\r
3806   the mmapped region stored in the prev_foot field of the chunk. This\r
3807   allows reconstruction of the required argument to MUNMAP when freed,\r
3808   and also allows adjustment of the returned chunk to meet alignment\r
3809   requirements (especially in memalign).\r
3810 */\r
3811 \r
3812 /* Malloc using mmap */\r
3813 static void* mmap_alloc(mstate m, size_t nb) {\r
3814   size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);\r
3815   if (m->footprint_limit != 0) {\r
3816     size_t fp = m->footprint + mmsize;\r
3817     if (fp <= m->footprint || fp > m->footprint_limit)\r
3818       return 0;\r
3819   }\r
3820   if (mmsize > nb) {     /* Check for wrap around 0 */\r
3821     char* mm = (char*)(CALL_DIRECT_MMAP(mmsize));\r
3822     if (mm != CMFAIL) {\r
3823       size_t offset = align_offset(chunk2mem(mm));\r
3824       size_t psize = mmsize - offset - MMAP_FOOT_PAD;\r
3825       mchunkptr p = (mchunkptr)(mm + offset);\r
3826       p->prev_foot = offset;\r
3827       p->head = psize;\r
3828       mark_inuse_foot(m, p, psize);\r
3829       chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;\r
3830       chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;\r
3831 \r
3832       if (m->least_addr == 0 || mm < m->least_addr)\r
3833         m->least_addr = mm;\r
3834       if ((m->footprint += mmsize) > m->max_footprint)\r
3835         m->max_footprint = m->footprint;\r
3836       assert(is_aligned(chunk2mem(p)));\r
3837       check_mmapped_chunk(m, p);\r
3838       return chunk2mem(p);\r
3839     }\r
3840   }\r
3841   return 0;\r
3842 }\r
3843 \r
3844 /* Realloc using mmap */\r
3845 static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb, int flags) {\r
3846   size_t oldsize = chunksize(oldp);\r
3847   (void) flags;\r
3848   if (is_small(nb)) /* Can't shrink mmap regions below small size */\r
3849     return 0;\r
3850   /* Keep old chunk if big enough but not too big */\r
3851   if (oldsize >= nb + SIZE_T_SIZE &&\r
3852       (oldsize - nb) <= (mparams.granularity << 1))\r
3853     return oldp;\r
3854   else {\r
3855     size_t offset = oldp->prev_foot;\r
3856     size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;\r
3857     size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);\r
3858     char* cp = (char*)CALL_MREMAP((char*)oldp - offset,\r
3859                                   oldmmsize, newmmsize, flags);\r
3860     if (cp != CMFAIL) {\r
3861       mchunkptr newp = (mchunkptr)(cp + offset);\r
3862       size_t psize = newmmsize - offset - MMAP_FOOT_PAD;\r
3863       newp->head = psize;\r
3864       mark_inuse_foot(m, newp, psize);\r
3865       chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;\r
3866       chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;\r
3867 \r
3868       if (cp < m->least_addr)\r
3869         m->least_addr = cp;\r
3870       if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)\r
3871         m->max_footprint = m->footprint;\r
3872       check_mmapped_chunk(m, newp);\r
3873       return newp;\r
3874     }\r
3875   }\r
3876   return 0;\r
3877 }\r
3878 \r
3879 \r
3880 /* -------------------------- mspace management -------------------------- */\r
3881 \r
3882 /* Initialize top chunk and its size */\r
3883 static void init_top(mstate m, mchunkptr p, size_t psize) {\r
3884   /* Ensure alignment */\r
3885   size_t offset = align_offset(chunk2mem(p));\r
3886   p = (mchunkptr)((char*)p + offset);\r
3887   psize -= offset;\r
3888 \r
3889   m->top = p;\r
3890   m->topsize = psize;\r
3891   p->head = psize | PINUSE_BIT;\r
3892   /* set size of fake trailing chunk holding overhead space only once */\r
3893   chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;\r
3894   m->trim_check = mparams.trim_threshold; /* reset on each update */\r
3895 }\r
3896 \r
3897 /* Initialize bins for a new mstate that is otherwise zeroed out */\r
3898 static void init_bins(mstate m) {\r
3899   /* Establish circular links for smallbins */\r
3900   bindex_t i;\r
3901   for (i = 0; i < NSMALLBINS; ++i) {\r
3902     sbinptr bin = smallbin_at(m,i);\r
3903     bin->fd = bin->bk = bin;\r
3904   }\r
3905 }\r
3906 \r
3907 #if PROCEED_ON_ERROR\r
3908 \r
3909 /* default corruption action */\r
3910 static void reset_on_error(mstate m) {\r
3911   int i;\r
3912   ++malloc_corruption_error_count;\r
3913   /* Reinitialize fields to forget about all memory */\r
3914   m->smallmap = m->treemap = 0;\r
3915   m->dvsize = m->topsize = 0;\r
3916   m->seg.base = 0;\r
3917   m->seg.size = 0;\r
3918   m->seg.next = 0;\r
3919   m->top = m->dv = 0;\r
3920   for (i = 0; i < NTREEBINS; ++i)\r
3921     *treebin_at(m, i) = 0;\r
3922   init_bins(m);\r
3923 }\r
3924 #endif /* PROCEED_ON_ERROR */\r
3925 \r
3926 /* Allocate chunk and prepend remainder with chunk in successor base. */\r
3927 static void* prepend_alloc(mstate m, char* newbase, char* oldbase,\r
3928                            size_t nb) {\r
3929   mchunkptr p = align_as_chunk(newbase);\r
3930   mchunkptr oldfirst = align_as_chunk(oldbase);\r
3931   size_t psize = (char*)oldfirst - (char*)p;\r
3932   mchunkptr q = chunk_plus_offset(p, nb);\r
3933   size_t qsize = psize - nb;\r
3934   set_size_and_pinuse_of_inuse_chunk(m, p, nb);\r
3935 \r
3936   assert((char*)oldfirst > (char*)q);\r
3937   assert(pinuse(oldfirst));\r
3938   assert(qsize >= MIN_CHUNK_SIZE);\r
3939 \r
3940   /* consolidate remainder with first chunk of old base */\r
3941   if (oldfirst == m->top) {\r
3942     size_t tsize = m->topsize += qsize;\r
3943     m->top = q;\r
3944     q->head = tsize | PINUSE_BIT;\r
3945     check_top_chunk(m, q);\r
3946   }\r
3947   else if (oldfirst == m->dv) {\r
3948     size_t dsize = m->dvsize += qsize;\r
3949     m->dv = q;\r
3950     set_size_and_pinuse_of_free_chunk(q, dsize);\r
3951   }\r
3952   else {\r
3953     if (!is_inuse(oldfirst)) {\r
3954       size_t nsize = chunksize(oldfirst);\r
3955       unlink_chunk(m, oldfirst, nsize);\r
3956       oldfirst = chunk_plus_offset(oldfirst, nsize);\r
3957       qsize += nsize;\r
3958     }\r
3959     set_free_with_pinuse(q, qsize, oldfirst);\r
3960     insert_chunk(m, q, qsize);\r
3961     check_free_chunk(m, q);\r
3962   }\r
3963 \r
3964   check_malloced_chunk(m, chunk2mem(p), nb);\r
3965   return chunk2mem(p);\r
3966 }\r
3967 \r
3968 /* Add a segment to hold a new noncontiguous region */\r
3969 static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {\r
3970   /* Determine locations and sizes of segment, fenceposts, old top */\r
3971   char* old_top = (char*)m->top;\r
3972   msegmentptr oldsp = segment_holding(m, old_top);\r
3973   char* old_end = oldsp->base + oldsp->size;\r
3974   size_t ssize = pad_request(sizeof(struct malloc_segment));\r
3975   char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);\r
3976   size_t offset = align_offset(chunk2mem(rawsp));\r
3977   char* asp = rawsp + offset;\r
3978   char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;\r
3979   mchunkptr sp = (mchunkptr)csp;\r
3980   msegmentptr ss = (msegmentptr)(chunk2mem(sp));\r
3981   mchunkptr tnext = chunk_plus_offset(sp, ssize);\r
3982   mchunkptr p = tnext;\r
3983   int nfences = 0;\r
3984 \r
3985   /* reset top to new space */\r
3986   init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);\r
3987 \r
3988   /* Set up segment record */\r
3989   assert(is_aligned(ss));\r
3990   set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);\r
3991   *ss = m->seg; /* Push current record */\r
3992   m->seg.base = tbase;\r
3993   m->seg.size = tsize;\r
3994   m->seg.sflags = mmapped;\r
3995   m->seg.next = ss;\r
3996 \r
3997   /* Insert trailing fenceposts */\r
3998   for (;;) {\r
3999     mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);\r
4000     p->head = FENCEPOST_HEAD;\r
4001     ++nfences;\r
4002     if ((char*)(&(nextp->head)) < old_end)\r
4003       p = nextp;\r
4004     else\r
4005       break;\r
4006   }\r
4007   assert(nfences >= 2);\r
4008 \r
4009   /* Insert the rest of old top into a bin as an ordinary free chunk */\r
4010   if (csp != old_top) {\r
4011     mchunkptr q = (mchunkptr)old_top;\r
4012     size_t psize = csp - old_top;\r
4013     mchunkptr tn = chunk_plus_offset(q, psize);\r
4014     set_free_with_pinuse(q, psize, tn);\r
4015     insert_chunk(m, q, psize);\r
4016   }\r
4017 \r
4018   check_top_chunk(m, m->top);\r
4019 }\r
4020 \r
4021 /* -------------------------- System allocation -------------------------- */\r
4022 \r
4023 /* Get memory from system using MORECORE or MMAP */\r
4024 static void* sys_alloc(mstate m, size_t nb) {\r
4025   char* tbase = CMFAIL;\r
4026   size_t tsize = 0;\r
4027   flag_t mmap_flag = 0;\r
4028   size_t asize; /* allocation size */\r
4029 \r
4030   ensure_initialization();\r
4031 \r
4032   /* Directly map large chunks, but only if already initialized */\r
4033   if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) {\r
4034     void* mem = mmap_alloc(m, nb);\r
4035     if (mem != 0)\r
4036       return mem;\r
4037   }\r
4038 \r
4039   asize = granularity_align(nb + SYS_ALLOC_PADDING);\r
4040   if (asize <= nb)\r
4041     return 0; /* wraparound */\r
4042   if (m->footprint_limit != 0) {\r
4043     size_t fp = m->footprint + asize;\r
4044     if (fp <= m->footprint || fp > m->footprint_limit)\r
4045       return 0;\r
4046   }\r
4047 \r
4048   /*\r
4049     Try getting memory in any of three ways (in most-preferred to\r
4050     least-preferred order):\r
4051     1. A call to MORECORE that can normally contiguously extend memory.\r
4052        (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or\r
4053        or main space is mmapped or a previous contiguous call failed)\r
4054     2. A call to MMAP new space (disabled if not HAVE_MMAP).\r
4055        Note that under the default settings, if MORECORE is unable to\r
4056        fulfill a request, and HAVE_MMAP is true, then mmap is\r
4057        used as a noncontiguous system allocator. This is a useful backup\r
4058        strategy for systems with holes in address spaces -- in this case\r
4059        sbrk cannot contiguously expand the heap, but mmap may be able to\r
4060        find space.\r
4061     3. A call to MORECORE that cannot usually contiguously extend memory.\r
4062        (disabled if not HAVE_MORECORE)\r
4063 \r
4064    In all cases, we need to request enough bytes from system to ensure\r
4065    we can malloc nb bytes upon success, so pad with enough space for\r
4066    top_foot, plus alignment-pad to make sure we don't lose bytes if\r
4067    not on boundary, and round this up to a granularity unit.\r
4068   */\r
4069 \r
4070   if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {\r
4071     char* br = CMFAIL;\r
4072     msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);\r
4073     ACQUIRE_MALLOC_GLOBAL_LOCK();\r
4074 \r
4075     if (ss == 0) {  /* First time through or recovery */\r
4076       char* base = (char*)CALL_MORECORE(0);\r
4077       if (base != CMFAIL) {\r
4078         size_t fp;\r
4079         /* Adjust to end on a page boundary */\r
4080         if (!is_page_aligned(base))\r
4081           asize += (page_align((size_t)base) - (size_t)base);\r
4082         fp = m->footprint + asize; /* recheck limits */\r
4083         if (asize > nb && asize < HALF_MAX_SIZE_T &&\r
4084             (m->footprint_limit == 0 ||\r
4085              (fp > m->footprint && fp <= m->footprint_limit)) &&\r
4086             (br = (char*)(CALL_MORECORE(asize))) == base) {\r
4087           tbase = base;\r
4088           tsize = asize;\r
4089         }\r
4090       }\r
4091     }\r
4092     else {\r
4093       /* Subtract out existing available top space from MORECORE request. */\r
4094       asize = granularity_align(nb - m->topsize + SYS_ALLOC_PADDING);\r
4095       /* Use mem here only if it did continuously extend old space */\r
4096       if (asize < HALF_MAX_SIZE_T &&\r
4097           (br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {\r
4098         tbase = br;\r
4099         tsize = asize;\r
4100       }\r
4101     }\r
4102 \r
4103     if (tbase == CMFAIL) {    /* Cope with partial failure */\r
4104       if (br != CMFAIL) {    /* Try to use/extend the space we did get */\r
4105         if (asize < HALF_MAX_SIZE_T &&\r
4106             asize < nb + SYS_ALLOC_PADDING) {\r
4107           size_t esize = granularity_align(nb + SYS_ALLOC_PADDING - asize);\r
4108           if (esize < HALF_MAX_SIZE_T) {\r
4109             char* end = (char*)CALL_MORECORE(esize);\r
4110             if (end != CMFAIL)\r
4111               asize += esize;\r
4112             else {            /* Can't use; try to release */\r
4113               (void) CALL_MORECORE(-asize);\r
4114               br = CMFAIL;\r
4115             }\r
4116           }\r
4117         }\r
4118       }\r
4119       if (br != CMFAIL) {    /* Use the space we did get */\r
4120         tbase = br;\r
4121         tsize = asize;\r
4122       }\r
4123       else\r
4124         disable_contiguous(m); /* Don't try contiguous path in the future */\r
4125     }\r
4126 \r
4127     RELEASE_MALLOC_GLOBAL_LOCK();\r
4128   }\r
4129 \r
4130   if (HAVE_MMAP && tbase == CMFAIL) {  /* Try MMAP */\r
4131     char* mp = (char*)(CALL_MMAP(asize));\r
4132     if (mp != CMFAIL) {\r
4133       tbase = mp;\r
4134       tsize = asize;\r
4135       mmap_flag = USE_MMAP_BIT;\r
4136     }\r
4137   }\r
4138 \r
4139   if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */\r
4140     if (asize < HALF_MAX_SIZE_T) {\r
4141       char* br = CMFAIL;\r
4142       char* end = CMFAIL;\r
4143       ACQUIRE_MALLOC_GLOBAL_LOCK();\r
4144       br = (char*)(CALL_MORECORE(asize));\r
4145       end = (char*)(CALL_MORECORE(0));\r
4146       RELEASE_MALLOC_GLOBAL_LOCK();\r
4147       if (br != CMFAIL && end != CMFAIL && br < end) {\r
4148         size_t ssize = end - br;\r
4149         if (ssize > nb + TOP_FOOT_SIZE) {\r
4150           tbase = br;\r
4151           tsize = ssize;\r
4152         }\r
4153       }\r
4154     }\r
4155   }\r
4156 \r
4157   if (tbase != CMFAIL) {\r
4158 \r
4159     if ((m->footprint += tsize) > m->max_footprint)\r
4160       m->max_footprint = m->footprint;\r
4161 \r
4162     if (!is_initialized(m)) { /* first-time initialization */\r
4163       if (m->least_addr == 0 || tbase < m->least_addr)\r
4164         m->least_addr = tbase;\r
4165       m->seg.base = tbase;\r
4166       m->seg.size = tsize;\r
4167       m->seg.sflags = mmap_flag;\r
4168       m->magic = mparams.magic;\r
4169       m->release_checks = MAX_RELEASE_CHECK_RATE;\r
4170       init_bins(m);\r
4171 #if !ONLY_MSPACES\r
4172       if (is_global(m))\r
4173         init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);\r
4174       else\r
4175 #endif\r
4176       {\r
4177         /* Offset top by embedded malloc_state */\r
4178         mchunkptr mn = next_chunk(mem2chunk(m));\r
4179         init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);\r
4180       }\r
4181     }\r
4182 \r
4183     else {\r
4184       /* Try to merge with an existing segment */\r
4185       msegmentptr sp = &m->seg;\r
4186       /* Only consider most recent segment if traversal suppressed */\r
4187       while (sp != 0 && tbase != sp->base + sp->size)\r
4188         sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;\r
4189       if (sp != 0 &&\r
4190           !is_extern_segment(sp) &&\r
4191           (sp->sflags & USE_MMAP_BIT) == mmap_flag &&\r
4192           segment_holds(sp, m->top)) { /* append */\r
4193         sp->size += tsize;\r
4194         init_top(m, m->top, m->topsize + tsize);\r
4195       }\r
4196       else {\r
4197         if (tbase < m->least_addr)\r
4198           m->least_addr = tbase;\r
4199         sp = &m->seg;\r
4200         while (sp != 0 && sp->base != tbase + tsize)\r
4201           sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;\r
4202         if (sp != 0 &&\r
4203             !is_extern_segment(sp) &&\r
4204             (sp->sflags & USE_MMAP_BIT) == mmap_flag) {\r
4205           char* oldbase = sp->base;\r
4206           sp->base = tbase;\r
4207           sp->size += tsize;\r
4208           return prepend_alloc(m, tbase, oldbase, nb);\r
4209         }\r
4210         else\r
4211           add_segment(m, tbase, tsize, mmap_flag);\r
4212       }\r
4213     }\r
4214 \r
4215     if (nb < m->topsize) { /* Allocate from new or extended top space */\r
4216       size_t rsize = m->topsize -= nb;\r
4217       mchunkptr p = m->top;\r
4218       mchunkptr r = m->top = chunk_plus_offset(p, nb);\r
4219       r->head = rsize | PINUSE_BIT;\r
4220       set_size_and_pinuse_of_inuse_chunk(m, p, nb);\r
4221       check_top_chunk(m, m->top);\r
4222       check_malloced_chunk(m, chunk2mem(p), nb);\r
4223       return chunk2mem(p);\r
4224     }\r
4225   }\r
4226 \r
4227   MALLOC_FAILURE_ACTION;\r
4228   return 0;\r
4229 }\r
4230 \r
4231 /* -----------------------  system deallocation -------------------------- */\r
4232 \r
4233 /* Unmap and unlink any mmapped segments that don't contain used chunks */\r
4234 static size_t release_unused_segments(mstate m) {\r
4235   size_t released = 0;\r
4236   int nsegs = 0;\r
4237   msegmentptr pred = &m->seg;\r
4238   msegmentptr sp = pred->next;\r
4239   while (sp != 0) {\r
4240     char* base = sp->base;\r
4241     size_t size = sp->size;\r
4242     msegmentptr next = sp->next;\r
4243     ++nsegs;\r
4244     if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {\r
4245       mchunkptr p = align_as_chunk(base);\r
4246       size_t psize = chunksize(p);\r
4247       /* Can unmap if first chunk holds entire segment and not pinned */\r
4248       if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {\r
4249         tchunkptr tp = (tchunkptr)p;\r
4250         assert(segment_holds(sp, (char*)sp));\r
4251         if (p == m->dv) {\r
4252           m->dv = 0;\r
4253           m->dvsize = 0;\r
4254         }\r
4255         else {\r
4256           unlink_large_chunk(m, tp);\r
4257         }\r
4258         if (CALL_MUNMAP(base, size) == 0) {\r
4259           released += size;\r
4260           m->footprint -= size;\r
4261           /* unlink obsoleted record */\r
4262           sp = pred;\r
4263           sp->next = next;\r
4264         }\r
4265         else { /* back out if cannot unmap */\r
4266           insert_large_chunk(m, tp, psize);\r
4267         }\r
4268       }\r
4269     }\r
4270     if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */\r
4271       break;\r
4272     pred = sp;\r
4273     sp = next;\r
4274   }\r
4275   /* Reset check counter */\r
4276   m->release_checks = ((nsegs > MAX_RELEASE_CHECK_RATE)?\r
4277                        nsegs : MAX_RELEASE_CHECK_RATE);\r
4278   return released;\r
4279 }\r
4280 \r
4281 static int sys_trim(mstate m, size_t pad) {\r
4282   size_t released = 0;\r
4283   ensure_initialization();\r
4284   if (pad < MAX_REQUEST && is_initialized(m)) {\r
4285     pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */\r
4286 \r
4287     if (m->topsize > pad) {\r
4288       /* Shrink top space in granularity-size units, keeping at least one */\r
4289       size_t unit = mparams.granularity;\r
4290       size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -\r
4291                       SIZE_T_ONE) * unit;\r
4292       msegmentptr sp = segment_holding(m, (char*)m->top);\r
4293 \r
4294       if (!is_extern_segment(sp)) {\r
4295         if (is_mmapped_segment(sp)) {\r
4296           if (HAVE_MMAP &&\r
4297               sp->size >= extra &&\r
4298               !has_segment_link(m, sp)) { /* can't shrink if pinned */\r
4299             size_t newsize = sp->size - extra;\r
4300             /* Prefer mremap, fall back to munmap */\r
4301             if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||\r
4302                 (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {\r
4303               released = extra;\r
4304             }\r
4305           }\r
4306         }\r
4307         else if (HAVE_MORECORE) {\r
4308           if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */\r
4309             extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;\r
4310           ACQUIRE_MALLOC_GLOBAL_LOCK();\r
4311           {\r
4312             /* Make sure end of memory is where we last set it. */\r
4313             char* old_br = (char*)(CALL_MORECORE(0));\r
4314             if (old_br == sp->base + sp->size) {\r
4315               char* rel_br = (char*)(CALL_MORECORE(-extra));\r
4316               char* new_br = (char*)(CALL_MORECORE(0));\r
4317               if (rel_br != CMFAIL && new_br < old_br)\r
4318                 released = old_br - new_br;\r
4319             }\r
4320           }\r
4321           RELEASE_MALLOC_GLOBAL_LOCK();\r
4322         }\r
4323       }\r
4324 \r
4325       if (released != 0) {\r
4326         sp->size -= released;\r
4327         m->footprint -= released;\r
4328         init_top(m, m->top, m->topsize - released);\r
4329         check_top_chunk(m, m->top);\r
4330       }\r
4331     }\r
4332 \r
4333     /* Unmap any unused mmapped segments */\r
4334     if (HAVE_MMAP)\r
4335       released += release_unused_segments(m);\r
4336 \r
4337     /* On failure, disable autotrim to avoid repeated failed future calls */\r
4338     if (released == 0 && m->topsize > m->trim_check)\r
4339       m->trim_check = MAX_SIZE_T;\r
4340   }\r
4341 \r
4342   return (released != 0)? 1 : 0;\r
4343 }\r
4344 \r
4345 /* Consolidate and bin a chunk. Differs from exported versions\r
4346    of free mainly in that the chunk need not be marked as inuse.\r
4347 */\r
4348 static void dispose_chunk(mstate m, mchunkptr p, size_t psize) {\r
4349   mchunkptr next = chunk_plus_offset(p, psize);\r
4350   if (!pinuse(p)) {\r
4351     mchunkptr prev;\r
4352     size_t prevsize = p->prev_foot;\r
4353     if (is_mmapped(p)) {\r
4354       psize += prevsize + MMAP_FOOT_PAD;\r
4355       if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)\r
4356         m->footprint -= psize;\r
4357       return;\r
4358     }\r
4359     prev = chunk_minus_offset(p, prevsize);\r
4360     psize += prevsize;\r
4361     p = prev;\r
4362     if (RTCHECK(ok_address(m, prev))) { /* consolidate backward */\r
4363       if (p != m->dv) {\r
4364         unlink_chunk(m, p, prevsize);\r
4365       }\r
4366       else if ((next->head & INUSE_BITS) == INUSE_BITS) {\r
4367         m->dvsize = psize;\r
4368         set_free_with_pinuse(p, psize, next);\r
4369         return;\r
4370       }\r
4371     }\r
4372     else {\r
4373       CORRUPTION_ERROR_ACTION(m);\r
4374       return;\r
4375     }\r
4376   }\r
4377   if (RTCHECK(ok_address(m, next))) {\r
4378     if (!cinuse(next)) {  /* consolidate forward */\r
4379       if (next == m->top) {\r
4380         size_t tsize = m->topsize += psize;\r
4381         m->top = p;\r
4382         p->head = tsize | PINUSE_BIT;\r
4383         if (p == m->dv) {\r
4384           m->dv = 0;\r
4385           m->dvsize = 0;\r
4386         }\r
4387         return;\r
4388       }\r
4389       else if (next == m->dv) {\r
4390         size_t dsize = m->dvsize += psize;\r
4391         m->dv = p;\r
4392         set_size_and_pinuse_of_free_chunk(p, dsize);\r
4393         return;\r
4394       }\r
4395       else {\r
4396         size_t nsize = chunksize(next);\r
4397         psize += nsize;\r
4398         unlink_chunk(m, next, nsize);\r
4399         set_size_and_pinuse_of_free_chunk(p, psize);\r
4400         if (p == m->dv) {\r
4401           m->dvsize = psize;\r
4402           return;\r
4403         }\r
4404       }\r
4405     }\r
4406     else {\r
4407       set_free_with_pinuse(p, psize, next);\r
4408     }\r
4409     insert_chunk(m, p, psize);\r
4410   }\r
4411   else {\r
4412     CORRUPTION_ERROR_ACTION(m);\r
4413   }\r
4414 }\r
4415 \r
4416 /* ---------------------------- malloc --------------------------- */\r
4417 \r
4418 /* allocate a large request from the best fitting chunk in a treebin */\r
4419 static void* tmalloc_large(mstate m, size_t nb) {\r
4420   tchunkptr v = 0;\r
4421   size_t rsize = -nb; /* Unsigned negation */\r
4422   tchunkptr t;\r
4423   bindex_t idx;\r
4424   compute_tree_index(nb, idx);\r
4425   if ((t = *treebin_at(m, idx)) != 0) {\r
4426     /* Traverse tree for this bin looking for node with size == nb */\r
4427     size_t sizebits = nb << leftshift_for_tree_index(idx);\r
4428     tchunkptr rst = 0;  /* The deepest untaken right subtree */\r
4429     for (;;) {\r
4430       tchunkptr rt;\r
4431       size_t trem = chunksize(t) - nb;\r
4432       if (trem < rsize) {\r
4433         v = t;\r
4434         if ((rsize = trem) == 0)\r
4435           break;\r
4436       }\r
4437       rt = t->child[1];\r
4438       t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];\r
4439       if (rt != 0 && rt != t)\r
4440         rst = rt;\r
4441       if (t == 0) {\r
4442         t = rst; /* set t to least subtree holding sizes > nb */\r
4443         break;\r
4444       }\r
4445       sizebits <<= 1;\r
4446     }\r
4447   }\r
4448   if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */\r
4449     binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;\r
4450     if (leftbits != 0) {\r
4451       bindex_t i;\r
4452       binmap_t leastbit = least_bit(leftbits);\r
4453       compute_bit2idx(leastbit, i);\r
4454       t = *treebin_at(m, i);\r
4455     }\r
4456   }\r
4457 \r
4458   while (t != 0) { /* find smallest of tree or subtree */\r
4459     size_t trem = chunksize(t) - nb;\r
4460     if (trem < rsize) {\r
4461       rsize = trem;\r
4462       v = t;\r
4463     }\r
4464     t = leftmost_child(t);\r
4465   }\r
4466 \r
4467   /*  If dv is a better fit, return 0 so malloc will use it */\r
4468   if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {\r
4469     if (RTCHECK(ok_address(m, v))) { /* split */\r
4470       mchunkptr r = chunk_plus_offset(v, nb);\r
4471       assert(chunksize(v) == rsize + nb);\r
4472       if (RTCHECK(ok_next(v, r))) {\r
4473         unlink_large_chunk(m, v);\r
4474         if (rsize < MIN_CHUNK_SIZE)\r
4475           set_inuse_and_pinuse(m, v, (rsize + nb));\r
4476         else {\r
4477           set_size_and_pinuse_of_inuse_chunk(m, v, nb);\r
4478           set_size_and_pinuse_of_free_chunk(r, rsize);\r
4479           insert_chunk(m, r, rsize);\r
4480         }\r
4481         return chunk2mem(v);\r
4482       }\r
4483     }\r
4484     CORRUPTION_ERROR_ACTION(m);\r
4485   }\r
4486   return 0;\r
4487 }\r
4488 \r
4489 /* allocate a small request from the best fitting chunk in a treebin */\r
4490 static void* tmalloc_small(mstate m, size_t nb) {\r
4491   tchunkptr t, v;\r
4492   size_t rsize;\r
4493   bindex_t i;\r
4494   binmap_t leastbit = least_bit(m->treemap);\r
4495   compute_bit2idx(leastbit, i);\r
4496   v = t = *treebin_at(m, i);\r
4497   rsize = chunksize(t) - nb;\r
4498 \r
4499   while ((t = leftmost_child(t)) != 0) {\r
4500     size_t trem = chunksize(t) - nb;\r
4501     if (trem < rsize) {\r
4502       rsize = trem;\r
4503       v = t;\r
4504     }\r
4505   }\r
4506 \r
4507   if (RTCHECK(ok_address(m, v))) {\r
4508     mchunkptr r = chunk_plus_offset(v, nb);\r
4509     assert(chunksize(v) == rsize + nb);\r
4510     if (RTCHECK(ok_next(v, r))) {\r
4511       unlink_large_chunk(m, v);\r
4512       if (rsize < MIN_CHUNK_SIZE)\r
4513         set_inuse_and_pinuse(m, v, (rsize + nb));\r
4514       else {\r
4515         set_size_and_pinuse_of_inuse_chunk(m, v, nb);\r
4516         set_size_and_pinuse_of_free_chunk(r, rsize);\r
4517         replace_dv(m, r, rsize);\r
4518       }\r
4519       return chunk2mem(v);\r
4520     }\r
4521   }\r
4522 \r
4523   CORRUPTION_ERROR_ACTION(m);\r
4524   return 0;\r
4525 }\r
4526 \r
4527 #if !ONLY_MSPACES\r
4528 \r
4529 void* dlmalloc(size_t bytes) {\r
4530   /*\r
4531      Basic algorithm:\r
4532      If a small request (< 256 bytes minus per-chunk overhead):\r
4533        1. If one exists, use a remainderless chunk in associated smallbin.\r
4534           (Remainderless means that there are too few excess bytes to\r
4535           represent as a chunk.)\r
4536        2. If it is big enough, use the dv chunk, which is normally the\r
4537           chunk adjacent to the one used for the most recent small request.\r
4538        3. If one exists, split the smallest available chunk in a bin,\r
4539           saving remainder in dv.\r
4540        4. If it is big enough, use the top chunk.\r
4541        5. If available, get memory from system and use it\r
4542      Otherwise, for a large request:\r
4543        1. Find the smallest available binned chunk that fits, and use it\r
4544           if it is better fitting than dv chunk, splitting if necessary.\r
4545        2. If better fitting than any binned chunk, use the dv chunk.\r
4546        3. If it is big enough, use the top chunk.\r
4547        4. If request size >= mmap threshold, try to directly mmap this chunk.\r
4548        5. If available, get memory from system and use it\r
4549 \r
4550      The ugly goto's here ensure that postaction occurs along all paths.\r
4551   */\r
4552 \r
4553 #if USE_LOCKS\r
4554   ensure_initialization(); /* initialize in sys_alloc if not using locks */\r
4555 #endif\r
4556 \r
4557   if (!PREACTION(gm)) {\r
4558     void* mem;\r
4559     size_t nb;\r
4560     if (bytes <= MAX_SMALL_REQUEST) {\r
4561       bindex_t idx;\r
4562       binmap_t smallbits;\r
4563       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);\r
4564       idx = small_index(nb);\r
4565       smallbits = gm->smallmap >> idx;\r
4566 \r
4567       if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */\r
4568         mchunkptr b, p;\r
4569         idx += ~smallbits & 1;       /* Uses next bin if idx empty */\r
4570         b = smallbin_at(gm, idx);\r
4571         p = b->fd;\r
4572         assert(chunksize(p) == small_index2size(idx));\r
4573         unlink_first_small_chunk(gm, b, p, idx);\r
4574         set_inuse_and_pinuse(gm, p, small_index2size(idx));\r
4575         mem = chunk2mem(p);\r
4576         check_malloced_chunk(gm, mem, nb);\r
4577         goto postaction;\r
4578       }\r
4579 \r
4580       else if (nb > gm->dvsize) {\r
4581         if (smallbits != 0) { /* Use chunk in next nonempty smallbin */\r
4582           mchunkptr b, p, r;\r
4583           size_t rsize;\r
4584           bindex_t i;\r
4585           binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));\r
4586           binmap_t leastbit = least_bit(leftbits);\r
4587           compute_bit2idx(leastbit, i);\r
4588           b = smallbin_at(gm, i);\r
4589           p = b->fd;\r
4590           assert(chunksize(p) == small_index2size(i));\r
4591           unlink_first_small_chunk(gm, b, p, i);\r
4592           rsize = small_index2size(i) - nb;\r
4593           /* Fit here cannot be remainderless if 4byte sizes */\r
4594           if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)\r
4595             set_inuse_and_pinuse(gm, p, small_index2size(i));\r
4596           else {\r
4597             set_size_and_pinuse_of_inuse_chunk(gm, p, nb);\r
4598             r = chunk_plus_offset(p, nb);\r
4599             set_size_and_pinuse_of_free_chunk(r, rsize);\r
4600             replace_dv(gm, r, rsize);\r
4601           }\r
4602           mem = chunk2mem(p);\r
4603           check_malloced_chunk(gm, mem, nb);\r
4604           goto postaction;\r
4605         }\r
4606 \r
4607         else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {\r
4608           check_malloced_chunk(gm, mem, nb);\r
4609           goto postaction;\r
4610         }\r
4611       }\r
4612     }\r
4613     else if (bytes >= MAX_REQUEST)\r
4614       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */\r
4615     else {\r
4616       nb = pad_request(bytes);\r
4617       if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {\r
4618         check_malloced_chunk(gm, mem, nb);\r
4619         goto postaction;\r
4620       }\r
4621     }\r
4622 \r
4623     if (nb <= gm->dvsize) {\r
4624       size_t rsize = gm->dvsize - nb;\r
4625       mchunkptr p = gm->dv;\r
4626       if (rsize >= MIN_CHUNK_SIZE) { /* split dv */\r
4627         mchunkptr r = gm->dv = chunk_plus_offset(p, nb);\r
4628         gm->dvsize = rsize;\r
4629         set_size_and_pinuse_of_free_chunk(r, rsize);\r
4630         set_size_and_pinuse_of_inuse_chunk(gm, p, nb);\r
4631       }\r
4632       else { /* exhaust dv */\r
4633         size_t dvs = gm->dvsize;\r
4634         gm->dvsize = 0;\r
4635         gm->dv = 0;\r
4636         set_inuse_and_pinuse(gm, p, dvs);\r
4637       }\r
4638       mem = chunk2mem(p);\r
4639       check_malloced_chunk(gm, mem, nb);\r
4640       goto postaction;\r
4641     }\r
4642 \r
4643     else if (nb < gm->topsize) { /* Split top */\r
4644       size_t rsize = gm->topsize -= nb;\r
4645       mchunkptr p = gm->top;\r
4646       mchunkptr r = gm->top = chunk_plus_offset(p, nb);\r
4647       r->head = rsize | PINUSE_BIT;\r
4648       set_size_and_pinuse_of_inuse_chunk(gm, p, nb);\r
4649       mem = chunk2mem(p);\r
4650       check_top_chunk(gm, gm->top);\r
4651       check_malloced_chunk(gm, mem, nb);\r
4652       goto postaction;\r
4653     }\r
4654 \r
4655     mem = sys_alloc(gm, nb);\r
4656 \r
4657   postaction:\r
4658     POSTACTION(gm);\r
4659     return mem;\r
4660   }\r
4661 \r
4662   return 0;\r
4663 }\r
4664 \r
4665 /* ---------------------------- free --------------------------- */\r
4666 \r
4667 void dlfree(void* mem) {\r
4668   /*\r
4669      Consolidate freed chunks with preceeding or succeeding bordering\r
4670      free chunks, if they exist, and then place in a bin.  Intermixed\r
4671      with special cases for top, dv, mmapped chunks, and usage errors.\r
4672   */\r
4673 \r
4674   if (mem != 0) {\r
4675     mchunkptr p  = mem2chunk(mem);\r
4676 #if FOOTERS\r
4677     mstate fm = get_mstate_for(p);\r
4678     if (!ok_magic(fm)) {\r
4679       USAGE_ERROR_ACTION(fm, p);\r
4680       return;\r
4681     }\r
4682 #else /* FOOTERS */\r
4683 #define fm gm\r
4684 #endif /* FOOTERS */\r
4685     if (!PREACTION(fm)) {\r
4686       check_inuse_chunk(fm, p);\r
4687       if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {\r
4688         size_t psize = chunksize(p);\r
4689         mchunkptr next = chunk_plus_offset(p, psize);\r
4690         if (!pinuse(p)) {\r
4691           size_t prevsize = p->prev_foot;\r
4692           if (is_mmapped(p)) {\r
4693             psize += prevsize + MMAP_FOOT_PAD;\r
4694             if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)\r
4695               fm->footprint -= psize;\r
4696             goto postaction;\r
4697           }\r
4698           else {\r
4699             mchunkptr prev = chunk_minus_offset(p, prevsize);\r
4700             psize += prevsize;\r
4701             p = prev;\r
4702             if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */\r
4703               if (p != fm->dv) {\r
4704                 unlink_chunk(fm, p, prevsize);\r
4705               }\r
4706               else if ((next->head & INUSE_BITS) == INUSE_BITS) {\r
4707                 fm->dvsize = psize;\r
4708                 set_free_with_pinuse(p, psize, next);\r
4709                 goto postaction;\r
4710               }\r
4711             }\r
4712             else\r
4713               goto erroraction;\r
4714           }\r
4715         }\r
4716 \r
4717         if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {\r
4718           if (!cinuse(next)) {  /* consolidate forward */\r
4719             if (next == fm->top) {\r
4720               size_t tsize = fm->topsize += psize;\r
4721               fm->top = p;\r
4722               p->head = tsize | PINUSE_BIT;\r
4723               if (p == fm->dv) {\r
4724                 fm->dv = 0;\r
4725                 fm->dvsize = 0;\r
4726               }\r
4727               if (should_trim(fm, tsize))\r
4728                 sys_trim(fm, 0);\r
4729               goto postaction;\r
4730             }\r
4731             else if (next == fm->dv) {\r
4732               size_t dsize = fm->dvsize += psize;\r
4733               fm->dv = p;\r
4734               set_size_and_pinuse_of_free_chunk(p, dsize);\r
4735               goto postaction;\r
4736             }\r
4737             else {\r
4738               size_t nsize = chunksize(next);\r
4739               psize += nsize;\r
4740               unlink_chunk(fm, next, nsize);\r
4741               set_size_and_pinuse_of_free_chunk(p, psize);\r
4742               if (p == fm->dv) {\r
4743                 fm->dvsize = psize;\r
4744                 goto postaction;\r
4745               }\r
4746             }\r
4747           }\r
4748           else\r
4749             set_free_with_pinuse(p, psize, next);\r
4750 \r
4751           if (is_small(psize)) {\r
4752             insert_small_chunk(fm, p, psize);\r
4753             check_free_chunk(fm, p);\r
4754           }\r
4755           else {\r
4756             tchunkptr tp = (tchunkptr)p;\r
4757             insert_large_chunk(fm, tp, psize);\r
4758             check_free_chunk(fm, p);\r
4759             if (--fm->release_checks == 0)\r
4760               release_unused_segments(fm);\r
4761           }\r
4762           goto postaction;\r
4763         }\r
4764       }\r
4765     erroraction:\r
4766       USAGE_ERROR_ACTION(fm, p);\r
4767     postaction:\r
4768       POSTACTION(fm);\r
4769     }\r
4770   }\r
4771 #if !FOOTERS\r
4772 #undef fm\r
4773 #endif /* FOOTERS */\r
4774 }\r
4775 \r
4776 void* dlcalloc(size_t n_elements, size_t elem_size) {\r
4777   void* mem;\r
4778   size_t req = 0;\r
4779   if (n_elements != 0) {\r
4780     req = n_elements * elem_size;\r
4781     if (((n_elements | elem_size) & ~(size_t)0xffff) &&\r
4782         (req / n_elements != elem_size))\r
4783       req = MAX_SIZE_T; /* force downstream failure on overflow */\r
4784   }\r
4785   mem = dlmalloc(req);\r
4786   if (mem != 0 && calloc_must_clear(mem2chunk(mem)))\r
4787     memset(mem, 0, req);\r
4788   return mem;\r
4789 }\r
4790 \r
4791 #endif /* !ONLY_MSPACES */\r
4792 \r
4793 /* ------------ Internal support for realloc, memalign, etc -------------- */\r
4794 \r
4795 /* Try to realloc; only in-place unless can_move true */\r
4796 static mchunkptr try_realloc_chunk(mstate m, mchunkptr p, size_t nb,\r
4797                                    int can_move) {\r
4798   mchunkptr newp = 0;\r
4799   size_t oldsize = chunksize(p);\r
4800   mchunkptr next = chunk_plus_offset(p, oldsize);\r
4801   if (RTCHECK(ok_address(m, p) && ok_inuse(p) &&\r
4802               ok_next(p, next) && ok_pinuse(next))) {\r
4803     if (is_mmapped(p)) {\r
4804       newp = mmap_resize(m, p, nb, can_move);\r
4805     }\r
4806     else if (oldsize >= nb) {             /* already big enough */\r
4807       size_t rsize = oldsize - nb;\r
4808       if (rsize >= MIN_CHUNK_SIZE) {      /* split off remainder */\r
4809         mchunkptr r = chunk_plus_offset(p, nb);\r
4810         set_inuse(m, p, nb);\r
4811         set_inuse(m, r, rsize);\r
4812         dispose_chunk(m, r, rsize);\r
4813       }\r
4814       newp = p;\r
4815     }\r
4816     else if (next == m->top) {  /* extend into top */\r
4817       if (oldsize + m->topsize > nb) {\r
4818         size_t newsize = oldsize + m->topsize;\r
4819         size_t newtopsize = newsize - nb;\r
4820         mchunkptr newtop = chunk_plus_offset(p, nb);\r
4821         set_inuse(m, p, nb);\r
4822         newtop->head = newtopsize |PINUSE_BIT;\r
4823         m->top = newtop;\r
4824         m->topsize = newtopsize;\r
4825         newp = p;\r
4826       }\r
4827     }\r
4828     else if (next == m->dv) { /* extend into dv */\r
4829       size_t dvs = m->dvsize;\r
4830       if (oldsize + dvs >= nb) {\r
4831         size_t dsize = oldsize + dvs - nb;\r
4832         if (dsize >= MIN_CHUNK_SIZE) {\r
4833           mchunkptr r = chunk_plus_offset(p, nb);\r
4834           mchunkptr n = chunk_plus_offset(r, dsize);\r
4835           set_inuse(m, p, nb);\r
4836           set_size_and_pinuse_of_free_chunk(r, dsize);\r
4837           clear_pinuse(n);\r
4838           m->dvsize = dsize;\r
4839           m->dv = r;\r
4840         }\r
4841         else { /* exhaust dv */\r
4842           size_t newsize = oldsize + dvs;\r
4843           set_inuse(m, p, newsize);\r
4844           m->dvsize = 0;\r
4845           m->dv = 0;\r
4846         }\r
4847         newp = p;\r
4848       }\r
4849     }\r
4850     else if (!cinuse(next)) { /* extend into next free chunk */\r
4851       size_t nextsize = chunksize(next);\r
4852       if (oldsize + nextsize >= nb) {\r
4853         size_t rsize = oldsize + nextsize - nb;\r
4854         unlink_chunk(m, next, nextsize);\r
4855         if (rsize < MIN_CHUNK_SIZE) {\r
4856           size_t newsize = oldsize + nextsize;\r
4857           set_inuse(m, p, newsize);\r
4858         }\r
4859         else {\r
4860           mchunkptr r = chunk_plus_offset(p, nb);\r
4861           set_inuse(m, p, nb);\r
4862           set_inuse(m, r, rsize);\r
4863           dispose_chunk(m, r, rsize);\r
4864         }\r
4865         newp = p;\r
4866       }\r
4867     }\r
4868   }\r
4869   else {\r
4870     USAGE_ERROR_ACTION(m, oldmem);\r
4871   }\r
4872   return newp;\r
4873 }\r
4874 \r
4875 static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {\r
4876   void* mem = 0;\r
4877   if (alignment <  MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */\r
4878     alignment = MIN_CHUNK_SIZE;\r
4879   if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */\r
4880     size_t a = MALLOC_ALIGNMENT << 1;\r
4881     while (a < alignment) a <<= 1;\r
4882     alignment = a;\r
4883   }\r
4884   if (bytes >= MAX_REQUEST - alignment) {\r
4885     if (m != 0)  { /* Test isn't needed but avoids compiler warning */\r
4886       MALLOC_FAILURE_ACTION;\r
4887     }\r
4888   }\r
4889   else {\r
4890     size_t nb = request2size(bytes);\r
4891     size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;\r
4892     mem = internal_malloc(m, req);\r
4893     if (mem != 0) {\r
4894       mchunkptr p = mem2chunk(mem);\r
4895       if (PREACTION(m))\r
4896         return 0;\r
4897       if ((((size_t)(mem)) & (alignment - 1)) != 0) { /* misaligned */\r
4898         /*\r
4899           Find an aligned spot inside chunk.  Since we need to give\r
4900           back leading space in a chunk of at least MIN_CHUNK_SIZE, if\r
4901           the first calculation places us at a spot with less than\r
4902           MIN_CHUNK_SIZE leader, we can move to the next aligned spot.\r
4903           We've allocated enough total room so that this is always\r
4904           possible.\r
4905         */\r
4906         char* br = (char*)mem2chunk((size_t)(((size_t)((char*)mem + alignment -\r
4907                                                        SIZE_T_ONE)) &\r
4908                                              -alignment));\r
4909         char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?\r
4910           br : br+alignment;\r
4911         mchunkptr newp = (mchunkptr)pos;\r
4912         size_t leadsize = pos - (char*)(p);\r
4913         size_t newsize = chunksize(p) - leadsize;\r
4914 \r
4915         if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */\r
4916           newp->prev_foot = p->prev_foot + leadsize;\r
4917           newp->head = newsize;\r
4918         }\r
4919         else { /* Otherwise, give back leader, use the rest */\r
4920           set_inuse(m, newp, newsize);\r
4921           set_inuse(m, p, leadsize);\r
4922           dispose_chunk(m, p, leadsize);\r
4923         }\r
4924         p = newp;\r
4925       }\r
4926 \r
4927       /* Give back spare room at the end */\r
4928       if (!is_mmapped(p)) {\r
4929         size_t size = chunksize(p);\r
4930         if (size > nb + MIN_CHUNK_SIZE) {\r
4931           size_t remainder_size = size - nb;\r
4932           mchunkptr remainder = chunk_plus_offset(p, nb);\r
4933           set_inuse(m, p, nb);\r
4934           set_inuse(m, remainder, remainder_size);\r
4935           dispose_chunk(m, remainder, remainder_size);\r
4936         }\r
4937       }\r
4938 \r
4939       mem = chunk2mem(p);\r
4940       assert (chunksize(p) >= nb);\r
4941       assert(((size_t)mem & (alignment - 1)) == 0);\r
4942       check_inuse_chunk(m, p);\r
4943       POSTACTION(m);\r
4944     }\r
4945   }\r
4946   return mem;\r
4947 }\r
4948 \r
4949 /*\r
4950   Common support for independent_X routines, handling\r
4951     all of the combinations that can result.\r
4952   The opts arg has:\r
4953     bit 0 set if all elements are same size (using sizes[0])\r
4954     bit 1 set if elements should be zeroed\r
4955 */\r
4956 static void** ialloc(mstate m,\r
4957                      size_t n_elements,\r
4958                      size_t* sizes,\r
4959                      int opts,\r
4960                      void* chunks[]) {\r
4961 \r
4962   size_t    element_size;   /* chunksize of each element, if all same */\r
4963   size_t    contents_size;  /* total size of elements */\r
4964   size_t    array_size;     /* request size of pointer array */\r
4965   void*     mem;            /* malloced aggregate space */\r
4966   mchunkptr p;              /* corresponding chunk */\r
4967   size_t    remainder_size; /* remaining bytes while splitting */\r
4968   void**    marray;         /* either "chunks" or malloced ptr array */\r
4969   mchunkptr array_chunk;    /* chunk for malloced ptr array */\r
4970   flag_t    was_enabled;    /* to disable mmap */\r
4971   size_t    size;\r
4972   size_t    i;\r
4973 \r
4974   ensure_initialization();\r
4975   /* compute array length, if needed */\r
4976   if (chunks != 0) {\r
4977     if (n_elements == 0)\r
4978       return chunks; /* nothing to do */\r
4979     marray = chunks;\r
4980     array_size = 0;\r
4981   }\r
4982   else {\r
4983     /* if empty req, must still return chunk representing empty array */\r
4984     if (n_elements == 0)\r
4985       return (void**)internal_malloc(m, 0);\r
4986     marray = 0;\r
4987     array_size = request2size(n_elements * (sizeof(void*)));\r
4988   }\r
4989 \r
4990   /* compute total element size */\r
4991   if (opts & 0x1) { /* all-same-size */\r
4992     element_size = request2size(*sizes);\r
4993     contents_size = n_elements * element_size;\r
4994   }\r
4995   else { /* add up all the sizes */\r
4996     element_size = 0;\r
4997     contents_size = 0;\r
4998     for (i = 0; i != n_elements; ++i)\r
4999       contents_size += request2size(sizes[i]);\r
5000   }\r
5001 \r
5002   size = contents_size + array_size;\r
5003 \r
5004   /*\r
5005      Allocate the aggregate chunk.  First disable direct-mmapping so\r
5006      malloc won't use it, since we would not be able to later\r
5007      free/realloc space internal to a segregated mmap region.\r
5008   */\r
5009   was_enabled = use_mmap(m);\r
5010   disable_mmap(m);\r
5011   mem = internal_malloc(m, size - CHUNK_OVERHEAD);\r
5012   if (was_enabled)\r
5013     enable_mmap(m);\r
5014   if (mem == 0)\r
5015     return 0;\r
5016 \r
5017   if (PREACTION(m)) return 0;\r
5018   p = mem2chunk(mem);\r
5019   remainder_size = chunksize(p);\r
5020 \r
5021   assert(!is_mmapped(p));\r
5022 \r
5023   if (opts & 0x2) {       /* optionally clear the elements */\r
5024     memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);\r
5025   }\r
5026 \r
5027   /* If not provided, allocate the pointer array as final part of chunk */\r
5028   if (marray == 0) {\r
5029     size_t  array_chunk_size;\r
5030     array_chunk = chunk_plus_offset(p, contents_size);\r
5031     array_chunk_size = remainder_size - contents_size;\r
5032     marray = (void**) (chunk2mem(array_chunk));\r
5033     set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);\r
5034     remainder_size = contents_size;\r
5035   }\r
5036 \r
5037   /* split out elements */\r
5038   for (i = 0; ; ++i) {\r
5039     marray[i] = chunk2mem(p);\r
5040     if (i != n_elements-1) {\r
5041       if (element_size != 0)\r
5042         size = element_size;\r
5043       else\r
5044         size = request2size(sizes[i]);\r
5045       remainder_size -= size;\r
5046       set_size_and_pinuse_of_inuse_chunk(m, p, size);\r
5047       p = chunk_plus_offset(p, size);\r
5048     }\r
5049     else { /* the final element absorbs any overallocation slop */\r
5050       set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);\r
5051       break;\r
5052     }\r
5053   }\r
5054 \r
5055 #if DEBUG\r
5056   if (marray != chunks) {\r
5057     /* final element must have exactly exhausted chunk */\r
5058     if (element_size != 0) {\r
5059       assert(remainder_size == element_size);\r
5060     }\r
5061     else {\r
5062       assert(remainder_size == request2size(sizes[i]));\r
5063     }\r
5064     check_inuse_chunk(m, mem2chunk(marray));\r
5065   }\r
5066   for (i = 0; i != n_elements; ++i)\r
5067     check_inuse_chunk(m, mem2chunk(marray[i]));\r
5068 \r
5069 #endif /* DEBUG */\r
5070 \r
5071   POSTACTION(m);\r
5072   return marray;\r
5073 }\r
5074 \r
5075 /* Try to free all pointers in the given array.\r
5076    Note: this could be made faster, by delaying consolidation,\r
5077    at the price of disabling some user integrity checks, We\r
5078    still optimize some consolidations by combining adjacent\r
5079    chunks before freeing, which will occur often if allocated\r
5080    with ialloc or the array is sorted.\r
5081 */\r
5082 static size_t internal_bulk_free(mstate m, void* array[], size_t nelem) {\r
5083   size_t unfreed = 0;\r
5084   if (!PREACTION(m)) {\r
5085     void** a;\r
5086     void** fence = &(array[nelem]);\r
5087     for (a = array; a != fence; ++a) {\r
5088       void* mem = *a;\r
5089       if (mem != 0) {\r
5090         mchunkptr p = mem2chunk(mem);\r
5091         size_t psize = chunksize(p);\r
5092 #if FOOTERS\r
5093         if (get_mstate_for(p) != m) {\r
5094           ++unfreed;\r
5095           continue;\r
5096         }\r
5097 #endif\r
5098         check_inuse_chunk(m, p);\r
5099         *a = 0;\r
5100         if (RTCHECK(ok_address(m, p) && ok_inuse(p))) {\r
5101           void ** b = a + 1; /* try to merge with next chunk */\r
5102           mchunkptr next = next_chunk(p);\r
5103           if (b != fence && *b == chunk2mem(next)) {\r
5104             size_t newsize = chunksize(next) + psize;\r
5105             set_inuse(m, p, newsize);\r
5106             *b = chunk2mem(p);\r
5107           }\r
5108           else\r
5109             dispose_chunk(m, p, psize);\r
5110         }\r
5111         else {\r
5112           CORRUPTION_ERROR_ACTION(m);\r
5113           break;\r
5114         }\r
5115       }\r
5116     }\r
5117     if (should_trim(m, m->topsize))\r
5118       sys_trim(m, 0);\r
5119     POSTACTION(m);\r
5120   }\r
5121   return unfreed;\r
5122 }\r
5123 \r
5124 /* Traversal */\r
5125 #if MALLOC_INSPECT_ALL\r
5126 static void internal_inspect_all(mstate m,\r
5127                                  void(*handler)(void *start,\r
5128                                                 void *end,\r
5129                                                 size_t used_bytes,\r
5130                                                 void* callback_arg),\r
5131                                  void* arg) {\r
5132   if (is_initialized(m)) {\r
5133     mchunkptr top = m->top;\r
5134     msegmentptr s;\r
5135     for (s = &m->seg; s != 0; s = s->next) {\r
5136       mchunkptr q = align_as_chunk(s->base);\r
5137       while (segment_holds(s, q) && q->head != FENCEPOST_HEAD) {\r
5138         mchunkptr next = next_chunk(q);\r
5139         size_t sz = chunksize(q);\r
5140         size_t used;\r
5141         void* start;\r
5142         if (is_inuse(q)) {\r
5143           used = sz - CHUNK_OVERHEAD; /* must not be mmapped */\r
5144           start = chunk2mem(q);\r
5145         }\r
5146         else {\r
5147           used = 0;\r
5148           if (is_small(sz)) {     /* offset by possible bookkeeping */\r
5149             start = (void*)((char*)q + sizeof(malloc_chunk));\r
5150           }\r
5151           else {\r
5152             start = (void*)((char*)q + sizeof(malloc_tree_chunk));\r
5153           }\r
5154         }\r
5155         if (start < (void*)next)  /* skip if all space is bookkeeping */\r
5156           handler(start, next, used, arg);\r
5157         if (q == top)\r
5158           break;\r
5159         q = next;\r
5160       }\r
5161     }\r
5162   }\r
5163 }\r
5164 #endif /* MALLOC_INSPECT_ALL */\r
5165 \r
5166 /* ------------------ Exported realloc, memalign, etc -------------------- */\r
5167 \r
5168 #if !ONLY_MSPACES\r
5169 \r
5170 void* dlrealloc(void* oldmem, size_t bytes) {\r
5171   void* mem = 0;\r
5172   if (oldmem == 0) {\r
5173     mem = dlmalloc(bytes);\r
5174   }\r
5175   else if (bytes >= MAX_REQUEST) {\r
5176     MALLOC_FAILURE_ACTION;\r
5177   }\r
5178 #ifdef REALLOC_ZERO_BYTES_FREES\r
5179   else if (bytes == 0) {\r
5180     dlfree(oldmem);\r
5181   }\r
5182 #endif /* REALLOC_ZERO_BYTES_FREES */\r
5183   else {\r
5184     size_t nb = request2size(bytes);\r
5185     mchunkptr oldp = mem2chunk(oldmem);\r
5186 #if ! FOOTERS\r
5187     mstate m = gm;\r
5188 #else /* FOOTERS */\r
5189     mstate m = get_mstate_for(oldp);\r
5190     if (!ok_magic(m)) {\r
5191       USAGE_ERROR_ACTION(m, oldmem);\r
5192       return 0;\r
5193     }\r
5194 #endif /* FOOTERS */\r
5195     if (!PREACTION(m)) {\r
5196       mchunkptr newp = try_realloc_chunk(m, oldp, nb, 1);\r
5197       POSTACTION(m);\r
5198       if (newp != 0) {\r
5199         check_inuse_chunk(m, newp);\r
5200         mem = chunk2mem(newp);\r
5201       }\r
5202       else {\r
5203         mem = internal_malloc(m, bytes);\r
5204         if (mem != 0) {\r
5205           size_t oc = chunksize(oldp) - overhead_for(oldp);\r
5206           memcpy(mem, oldmem, (oc < bytes)? oc : bytes);\r
5207           internal_free(m, oldmem);\r
5208         }\r
5209       }\r
5210     }\r
5211   }\r
5212   return mem;\r
5213 }\r
5214 \r
5215 void* dlrealloc_in_place(void* oldmem, size_t bytes) {\r
5216   void* mem = 0;\r
5217   if (oldmem != 0) {\r
5218     if (bytes >= MAX_REQUEST) {\r
5219       MALLOC_FAILURE_ACTION;\r
5220     }\r
5221     else {\r
5222       size_t nb = request2size(bytes);\r
5223       mchunkptr oldp = mem2chunk(oldmem);\r
5224 #if ! FOOTERS\r
5225       mstate m = gm;\r
5226 #else /* FOOTERS */\r
5227       mstate m = get_mstate_for(oldp);\r
5228       if (!ok_magic(m)) {\r
5229         USAGE_ERROR_ACTION(m, oldmem);\r
5230         return 0;\r
5231       }\r
5232 #endif /* FOOTERS */\r
5233       if (!PREACTION(m)) {\r
5234         mchunkptr newp = try_realloc_chunk(m, oldp, nb, 0);\r
5235         POSTACTION(m);\r
5236         if (newp == oldp) {\r
5237           check_inuse_chunk(m, newp);\r
5238           mem = oldmem;\r
5239         }\r
5240       }\r
5241     }\r
5242   }\r
5243   return mem;\r
5244 }\r
5245 \r
5246 void* dlmemalign(size_t alignment, size_t bytes) {\r
5247   if (alignment <= MALLOC_ALIGNMENT) {\r
5248     return dlmalloc(bytes);\r
5249   }\r
5250   return internal_memalign(gm, alignment, bytes);\r
5251 }\r
5252 \r
5253 int dlposix_memalign(void** pp, size_t alignment, size_t bytes) {\r
5254   void* mem = 0;\r
5255   if (alignment == MALLOC_ALIGNMENT)\r
5256     mem = dlmalloc(bytes);\r
5257   else {\r
5258     size_t d = alignment / sizeof(void*);\r
5259     size_t r = alignment % sizeof(void*);\r
5260     if (r != 0 || d == 0 || (d & (d-SIZE_T_ONE)) != 0)\r
5261       return EINVAL;\r
5262     else if (bytes >= MAX_REQUEST - alignment) {\r
5263       if (alignment <  MIN_CHUNK_SIZE)\r
5264         alignment = MIN_CHUNK_SIZE;\r
5265       mem = internal_memalign(gm, alignment, bytes);\r
5266     }\r
5267   }\r
5268   if (mem == 0)\r
5269     return ENOMEM;\r
5270   else {\r
5271     *pp = mem;\r
5272     return 0;\r
5273   }\r
5274 }\r
5275 \r
5276 void* dlvalloc(size_t bytes) {\r
5277   size_t pagesz;\r
5278   ensure_initialization();\r
5279   pagesz = mparams.page_size;\r
5280   return dlmemalign(pagesz, bytes);\r
5281 }\r
5282 \r
5283 void* dlpvalloc(size_t bytes) {\r
5284   size_t pagesz;\r
5285   ensure_initialization();\r
5286   pagesz = mparams.page_size;\r
5287   return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));\r
5288 }\r
5289 \r
5290 void** dlindependent_calloc(size_t n_elements, size_t elem_size,\r
5291                             void* chunks[]) {\r
5292   size_t sz = elem_size; /* serves as 1-element array */\r
5293   return ialloc(gm, n_elements, &sz, 3, chunks);\r
5294 }\r
5295 \r
5296 void** dlindependent_comalloc(size_t n_elements, size_t sizes[],\r
5297                               void* chunks[]) {\r
5298   return ialloc(gm, n_elements, sizes, 0, chunks);\r
5299 }\r
5300 \r
5301 size_t dlbulk_free(void* array[], size_t nelem) {\r
5302   return internal_bulk_free(gm, array, nelem);\r
5303 }\r
5304 \r
5305 #if MALLOC_INSPECT_ALL\r
5306 void dlmalloc_inspect_all(void(*handler)(void *start,\r
5307                                          void *end,\r
5308                                          size_t used_bytes,\r
5309                                          void* callback_arg),\r
5310                           void* arg) {\r
5311   ensure_initialization();\r
5312   if (!PREACTION(gm)) {\r
5313     internal_inspect_all(gm, handler, arg);\r
5314     POSTACTION(gm);\r
5315   }\r
5316 }\r
5317 #endif /* MALLOC_INSPECT_ALL */\r
5318 \r
5319 int dlmalloc_trim(size_t pad) {\r
5320   int result = 0;\r
5321   ensure_initialization();\r
5322   if (!PREACTION(gm)) {\r
5323     result = sys_trim(gm, pad);\r
5324     POSTACTION(gm);\r
5325   }\r
5326   return result;\r
5327 }\r
5328 \r
5329 size_t dlmalloc_footprint(void) {\r
5330   return gm->footprint;\r
5331 }\r
5332 \r
5333 size_t dlmalloc_max_footprint(void) {\r
5334   return gm->max_footprint;\r
5335 }\r
5336 \r
5337 size_t dlmalloc_footprint_limit(void) {\r
5338   size_t maf = gm->footprint_limit;\r
5339   return maf == 0 ? MAX_SIZE_T : maf;\r
5340 }\r
5341 \r
5342 size_t dlmalloc_set_footprint_limit(size_t bytes) {\r
5343   size_t result;  /* invert sense of 0 */\r
5344   if (bytes == 0)\r
5345     result = granularity_align(1); /* Use minimal size */\r
5346   if (bytes == MAX_SIZE_T)\r
5347     result = 0;                    /* disable */\r
5348   else\r
5349     result = granularity_align(bytes);\r
5350   return gm->footprint_limit = result;\r
5351 }\r
5352 \r
5353 #if !NO_MALLINFO\r
5354 struct mallinfo dlmallinfo(void) {\r
5355   return internal_mallinfo(gm);\r
5356 }\r
5357 #endif /* NO_MALLINFO */\r
5358 \r
5359 #if !NO_MALLOC_STATS\r
5360 void dlmalloc_stats() {\r
5361   internal_malloc_stats(gm);\r
5362 }\r
5363 #endif /* NO_MALLOC_STATS */\r
5364 \r
5365 int dlmallopt(int param_number, int value) {\r
5366   return change_mparam(param_number, value);\r
5367 }\r
5368 \r
5369 size_t dlmalloc_usable_size(void* mem) {\r
5370   if (mem != 0) {\r
5371     mchunkptr p = mem2chunk(mem);\r
5372     if (is_inuse(p))\r
5373       return chunksize(p) - overhead_for(p);\r
5374   }\r
5375   return 0;\r
5376 }\r
5377 \r
5378 #endif /* !ONLY_MSPACES */\r
5379 \r
5380 /* ----------------------------- user mspaces ---------------------------- */\r
5381 \r
5382 #if MSPACES\r
5383 \r
5384 static mstate init_user_mstate(char* tbase, size_t tsize) {\r
5385   size_t msize = pad_request(sizeof(struct malloc_state));\r
5386   mchunkptr mn;\r
5387   mchunkptr msp = align_as_chunk(tbase);\r
5388   mstate m = (mstate)(chunk2mem(msp));\r
5389   memset(m, 0, msize);\r
5390   (void)INITIAL_LOCK(&m->mutex);\r
5391   msp->head = (msize|INUSE_BITS);\r
5392   m->seg.base = m->least_addr = tbase;\r
5393   m->seg.size = m->footprint = m->max_footprint = tsize;\r
5394   m->magic = mparams.magic;\r
5395   m->release_checks = MAX_RELEASE_CHECK_RATE;\r
5396   m->mflags = mparams.default_mflags;\r
5397   m->extp = 0;\r
5398   m->exts = 0;\r
5399   disable_contiguous(m);\r
5400   init_bins(m);\r
5401   mn = next_chunk(mem2chunk(m));\r
5402   init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);\r
5403   check_top_chunk(m, m->top);\r
5404   return m;\r
5405 }\r
5406 \r
5407 mspace create_mspace(size_t capacity, int locked) {\r
5408   mstate m = 0;\r
5409   size_t msize;\r
5410   ensure_initialization();\r
5411   msize = pad_request(sizeof(struct malloc_state));\r
5412   if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {\r
5413     size_t rs = ((capacity == 0)? mparams.granularity :\r
5414                  (capacity + TOP_FOOT_SIZE + msize));\r
5415     size_t tsize = granularity_align(rs);\r
5416     char* tbase = (char*)(CALL_MMAP(tsize));\r
5417     if (tbase != CMFAIL) {\r
5418       m = init_user_mstate(tbase, tsize);\r
5419       m->seg.sflags = USE_MMAP_BIT;\r
5420       set_lock(m, locked);\r
5421     }\r
5422   }\r
5423   return (mspace)m;\r
5424 }\r
5425 \r
5426 mspace create_mspace_with_base(void* base, size_t capacity, int locked) {\r
5427   mstate m = 0;\r
5428   size_t msize;\r
5429   ensure_initialization();\r
5430   msize = pad_request(sizeof(struct malloc_state));\r
5431   if (capacity > msize + TOP_FOOT_SIZE &&\r
5432       capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {\r
5433     m = init_user_mstate((char*)base, capacity);\r
5434     m->seg.sflags = EXTERN_BIT;\r
5435     set_lock(m, locked);\r
5436   }\r
5437   return (mspace)m;\r
5438 }\r
5439 \r
5440 int mspace_track_large_chunks(mspace msp, int enable) {\r
5441   int ret = 0;\r
5442   mstate ms = (mstate)msp;\r
5443   if (!PREACTION(ms)) {\r
5444     if (!use_mmap(ms))\r
5445       ret = 1;\r
5446     if (!enable)\r
5447       enable_mmap(ms);\r
5448     else\r
5449       disable_mmap(ms);\r
5450     POSTACTION(ms);\r
5451   }\r
5452   return ret;\r
5453 }\r
5454 \r
5455 size_t destroy_mspace(mspace msp) {\r
5456   size_t freed = 0;\r
5457   mstate ms = (mstate)msp;\r
5458   if (ok_magic(ms)) {\r
5459     msegmentptr sp = &ms->seg;\r
5460     (void)DESTROY_LOCK(&ms->mutex); /* destroy before unmapped */\r
5461     while (sp != 0) {\r
5462       char* base = sp->base;\r
5463       size_t size = sp->size;\r
5464       flag_t flag = sp->sflags;\r
5465       sp = sp->next;\r
5466       if ((flag & USE_MMAP_BIT) && !(flag & EXTERN_BIT) &&\r
5467           CALL_MUNMAP(base, size) == 0)\r
5468         freed += size;\r
5469     }\r
5470   }\r
5471   else {\r
5472     USAGE_ERROR_ACTION(ms,ms);\r
5473   }\r
5474   return freed;\r
5475 }\r
5476 \r
5477 /*\r
5478   mspace versions of routines are near-clones of the global\r
5479   versions. This is not so nice but better than the alternatives.\r
5480 */\r
5481 \r
5482 void* mspace_malloc(mspace msp, size_t bytes) {\r
5483   mstate ms = (mstate)msp;\r
5484   if (!ok_magic(ms)) {\r
5485     USAGE_ERROR_ACTION(ms,ms);\r
5486     return 0;\r
5487   }\r
5488   if (!PREACTION(ms)) {\r
5489     void* mem;\r
5490     size_t nb;\r
5491     if (bytes <= MAX_SMALL_REQUEST) {\r
5492       bindex_t idx;\r
5493       binmap_t smallbits;\r
5494       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);\r
5495       idx = small_index(nb);\r
5496       smallbits = ms->smallmap >> idx;\r
5497 \r
5498       if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */\r
5499         mchunkptr b, p;\r
5500         idx += ~smallbits & 1;       /* Uses next bin if idx empty */\r
5501         b = smallbin_at(ms, idx);\r
5502         p = b->fd;\r
5503         assert(chunksize(p) == small_index2size(idx));\r
5504         unlink_first_small_chunk(ms, b, p, idx);\r
5505         set_inuse_and_pinuse(ms, p, small_index2size(idx));\r
5506         mem = chunk2mem(p);\r
5507         check_malloced_chunk(ms, mem, nb);\r
5508         goto postaction;\r
5509       }\r
5510 \r
5511       else if (nb > ms->dvsize) {\r
5512         if (smallbits != 0) { /* Use chunk in next nonempty smallbin */\r
5513           mchunkptr b, p, r;\r
5514           size_t rsize;\r
5515           bindex_t i;\r
5516           binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));\r
5517           binmap_t leastbit = least_bit(leftbits);\r
5518           compute_bit2idx(leastbit, i);\r
5519           b = smallbin_at(ms, i);\r
5520           p = b->fd;\r
5521           assert(chunksize(p) == small_index2size(i));\r
5522           unlink_first_small_chunk(ms, b, p, i);\r
5523           rsize = small_index2size(i) - nb;\r
5524           /* Fit here cannot be remainderless if 4byte sizes */\r
5525           if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)\r
5526             set_inuse_and_pinuse(ms, p, small_index2size(i));\r
5527           else {\r
5528             set_size_and_pinuse_of_inuse_chunk(ms, p, nb);\r
5529             r = chunk_plus_offset(p, nb);\r
5530             set_size_and_pinuse_of_free_chunk(r, rsize);\r
5531             replace_dv(ms, r, rsize);\r
5532           }\r
5533           mem = chunk2mem(p);\r
5534           check_malloced_chunk(ms, mem, nb);\r
5535           goto postaction;\r
5536         }\r
5537 \r
5538         else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {\r
5539           check_malloced_chunk(ms, mem, nb);\r
5540           goto postaction;\r
5541         }\r
5542       }\r
5543     }\r
5544     else if (bytes >= MAX_REQUEST)\r
5545       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */\r
5546     else {\r
5547       nb = pad_request(bytes);\r
5548       if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {\r
5549         check_malloced_chunk(ms, mem, nb);\r
5550         goto postaction;\r
5551       }\r
5552     }\r
5553 \r
5554     if (nb <= ms->dvsize) {\r
5555       size_t rsize = ms->dvsize - nb;\r
5556       mchunkptr p = ms->dv;\r
5557       if (rsize >= MIN_CHUNK_SIZE) { /* split dv */\r
5558         mchunkptr r = ms->dv = chunk_plus_offset(p, nb);\r
5559         ms->dvsize = rsize;\r
5560         set_size_and_pinuse_of_free_chunk(r, rsize);\r
5561         set_size_and_pinuse_of_inuse_chunk(ms, p, nb);\r
5562       }\r
5563       else { /* exhaust dv */\r
5564         size_t dvs = ms->dvsize;\r
5565         ms->dvsize = 0;\r
5566         ms->dv = 0;\r
5567         set_inuse_and_pinuse(ms, p, dvs);\r
5568       }\r
5569       mem = chunk2mem(p);\r
5570       check_malloced_chunk(ms, mem, nb);\r
5571       goto postaction;\r
5572     }\r
5573 \r
5574     else if (nb < ms->topsize) { /* Split top */\r
5575       size_t rsize = ms->topsize -= nb;\r
5576       mchunkptr p = ms->top;\r
5577       mchunkptr r = ms->top = chunk_plus_offset(p, nb);\r
5578       r->head = rsize | PINUSE_BIT;\r
5579       set_size_and_pinuse_of_inuse_chunk(ms, p, nb);\r
5580       mem = chunk2mem(p);\r
5581       check_top_chunk(ms, ms->top);\r
5582       check_malloced_chunk(ms, mem, nb);\r
5583       goto postaction;\r
5584     }\r
5585 \r
5586     mem = sys_alloc(ms, nb);\r
5587 \r
5588   postaction:\r
5589     POSTACTION(ms);\r
5590     return mem;\r
5591   }\r
5592 \r
5593   return 0;\r
5594 }\r
5595 \r
5596 void mspace_free(mspace msp, void* mem) {\r
5597   if (mem != 0) {\r
5598     mchunkptr p  = mem2chunk(mem);\r
5599 #if FOOTERS\r
5600     mstate fm = get_mstate_for(p);\r
5601     msp = msp; /* placate people compiling -Wunused */\r
5602 #else /* FOOTERS */\r
5603     mstate fm = (mstate)msp;\r
5604 #endif /* FOOTERS */\r
5605     if (!ok_magic(fm)) {\r
5606       USAGE_ERROR_ACTION(fm, p);\r
5607       return;\r
5608     }\r
5609     if (!PREACTION(fm)) {\r
5610       check_inuse_chunk(fm, p);\r
5611       if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {\r
5612         size_t psize = chunksize(p);\r
5613         mchunkptr next = chunk_plus_offset(p, psize);\r
5614         if (!pinuse(p)) {\r
5615           size_t prevsize = p->prev_foot;\r
5616           if (is_mmapped(p)) {\r
5617             psize += prevsize + MMAP_FOOT_PAD;\r
5618             if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)\r
5619               fm->footprint -= psize;\r
5620             goto postaction;\r
5621           }\r
5622           else {\r
5623             mchunkptr prev = chunk_minus_offset(p, prevsize);\r
5624             psize += prevsize;\r
5625             p = prev;\r
5626             if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */\r
5627               if (p != fm->dv) {\r
5628                 unlink_chunk(fm, p, prevsize);\r
5629               }\r
5630               else if ((next->head & INUSE_BITS) == INUSE_BITS) {\r
5631                 fm->dvsize = psize;\r
5632                 set_free_with_pinuse(p, psize, next);\r
5633                 goto postaction;\r
5634               }\r
5635             }\r
5636             else\r
5637               goto erroraction;\r
5638           }\r
5639         }\r
5640 \r
5641         if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {\r
5642           if (!cinuse(next)) {  /* consolidate forward */\r
5643             if (next == fm->top) {\r
5644               size_t tsize = fm->topsize += psize;\r
5645               fm->top = p;\r
5646               p->head = tsize | PINUSE_BIT;\r
5647               if (p == fm->dv) {\r
5648                 fm->dv = 0;\r
5649                 fm->dvsize = 0;\r
5650               }\r
5651               if (should_trim(fm, tsize))\r
5652                 sys_trim(fm, 0);\r
5653               goto postaction;\r
5654             }\r
5655             else if (next == fm->dv) {\r
5656               size_t dsize = fm->dvsize += psize;\r
5657               fm->dv = p;\r
5658               set_size_and_pinuse_of_free_chunk(p, dsize);\r
5659               goto postaction;\r
5660             }\r
5661             else {\r
5662               size_t nsize = chunksize(next);\r
5663               psize += nsize;\r
5664               unlink_chunk(fm, next, nsize);\r
5665               set_size_and_pinuse_of_free_chunk(p, psize);\r
5666               if (p == fm->dv) {\r
5667                 fm->dvsize = psize;\r
5668                 goto postaction;\r
5669               }\r
5670             }\r
5671           }\r
5672           else\r
5673             set_free_with_pinuse(p, psize, next);\r
5674 \r
5675           if (is_small(psize)) {\r
5676             insert_small_chunk(fm, p, psize);\r
5677             check_free_chunk(fm, p);\r
5678           }\r
5679           else {\r
5680             tchunkptr tp = (tchunkptr)p;\r
5681             insert_large_chunk(fm, tp, psize);\r
5682             check_free_chunk(fm, p);\r
5683             if (--fm->release_checks == 0)\r
5684               release_unused_segments(fm);\r
5685           }\r
5686           goto postaction;\r
5687         }\r
5688       }\r
5689     erroraction:\r
5690       USAGE_ERROR_ACTION(fm, p);\r
5691     postaction:\r
5692       POSTACTION(fm);\r
5693     }\r
5694   }\r
5695 }\r
5696 \r
5697 void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {\r
5698   void* mem;\r
5699   size_t req = 0;\r
5700   mstate ms = (mstate)msp;\r
5701   if (!ok_magic(ms)) {\r
5702     USAGE_ERROR_ACTION(ms,ms);\r
5703     return 0;\r
5704   }\r
5705   if (n_elements != 0) {\r
5706     req = n_elements * elem_size;\r
5707     if (((n_elements | elem_size) & ~(size_t)0xffff) &&\r
5708         (req / n_elements != elem_size))\r
5709       req = MAX_SIZE_T; /* force downstream failure on overflow */\r
5710   }\r
5711   mem = internal_malloc(ms, req);\r
5712   if (mem != 0 && calloc_must_clear(mem2chunk(mem)))\r
5713     memset(mem, 0, req);\r
5714   return mem;\r
5715 }\r
5716 \r
5717 void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {\r
5718   void* mem = 0;\r
5719   if (oldmem == 0) {\r
5720     mem = mspace_malloc(msp, bytes);\r
5721   }\r
5722   else if (bytes >= MAX_REQUEST) {\r
5723     MALLOC_FAILURE_ACTION;\r
5724   }\r
5725 #ifdef REALLOC_ZERO_BYTES_FREES\r
5726   else if (bytes == 0) {\r
5727     mspace_free(msp, oldmem);\r
5728   }\r
5729 #endif /* REALLOC_ZERO_BYTES_FREES */\r
5730   else {\r
5731     size_t nb = request2size(bytes);\r
5732     mchunkptr oldp = mem2chunk(oldmem);\r
5733 #if ! FOOTERS\r
5734     mstate m = (mstate)msp;\r
5735 #else /* FOOTERS */\r
5736     mstate m = get_mstate_for(oldp);\r
5737     if (!ok_magic(m)) {\r
5738       USAGE_ERROR_ACTION(m, oldmem);\r
5739       return 0;\r
5740     }\r
5741 #endif /* FOOTERS */\r
5742     if (!PREACTION(m)) {\r
5743       mchunkptr newp = try_realloc_chunk(m, oldp, nb, 1);\r
5744       POSTACTION(m);\r
5745       if (newp != 0) {\r
5746         check_inuse_chunk(m, newp);\r
5747         mem = chunk2mem(newp);\r
5748       }\r
5749       else {\r
5750         mem = mspace_malloc(m, bytes);\r
5751         if (mem != 0) {\r
5752           size_t oc = chunksize(oldp) - overhead_for(oldp);\r
5753           memcpy(mem, oldmem, (oc < bytes)? oc : bytes);\r
5754           mspace_free(m, oldmem);\r
5755         }\r
5756       }\r
5757     }\r
5758   }\r
5759   return mem;\r
5760 }\r
5761 \r
5762 void* mspace_realloc_in_place(mspace msp, void* oldmem, size_t bytes) {\r
5763   void* mem = 0;\r
5764   if (oldmem != 0) {\r
5765     if (bytes >= MAX_REQUEST) {\r
5766       MALLOC_FAILURE_ACTION;\r
5767     }\r
5768     else {\r
5769       size_t nb = request2size(bytes);\r
5770       mchunkptr oldp = mem2chunk(oldmem);\r
5771 #if ! FOOTERS\r
5772       mstate m = (mstate)msp;\r
5773 #else /* FOOTERS */\r
5774       mstate m = get_mstate_for(oldp);\r
5775       msp = msp; /* placate people compiling -Wunused */\r
5776       if (!ok_magic(m)) {\r
5777         USAGE_ERROR_ACTION(m, oldmem);\r
5778         return 0;\r
5779       }\r
5780 #endif /* FOOTERS */\r
5781       if (!PREACTION(m)) {\r
5782         mchunkptr newp = try_realloc_chunk(m, oldp, nb, 0);\r
5783         POSTACTION(m);\r
5784         if (newp == oldp) {\r
5785           check_inuse_chunk(m, newp);\r
5786           mem = oldmem;\r
5787         }\r
5788       }\r
5789     }\r
5790   }\r
5791   return mem;\r
5792 }\r
5793 \r
5794 void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {\r
5795   mstate ms = (mstate)msp;\r
5796   if (!ok_magic(ms)) {\r
5797     USAGE_ERROR_ACTION(ms,ms);\r
5798     return 0;\r
5799   }\r
5800   if (alignment <= MALLOC_ALIGNMENT)\r
5801     return mspace_malloc(msp, bytes);\r
5802   return internal_memalign(ms, alignment, bytes);\r
5803 }\r
5804 \r
5805 void** mspace_independent_calloc(mspace msp, size_t n_elements,\r
5806                                  size_t elem_size, void* chunks[]) {\r
5807   size_t sz = elem_size; /* serves as 1-element array */\r
5808   mstate ms = (mstate)msp;\r
5809   if (!ok_magic(ms)) {\r
5810     USAGE_ERROR_ACTION(ms,ms);\r
5811     return 0;\r
5812   }\r
5813   return ialloc(ms, n_elements, &sz, 3, chunks);\r
5814 }\r
5815 \r
5816 void** mspace_independent_comalloc(mspace msp, size_t n_elements,\r
5817                                    size_t sizes[], void* chunks[]) {\r
5818   mstate ms = (mstate)msp;\r
5819   if (!ok_magic(ms)) {\r
5820     USAGE_ERROR_ACTION(ms,ms);\r
5821     return 0;\r
5822   }\r
5823   return ialloc(ms, n_elements, sizes, 0, chunks);\r
5824 }\r
5825 \r
5826 size_t mspace_bulk_free(mspace msp, void* array[], size_t nelem) {\r
5827   return internal_bulk_free((mstate)msp, array, nelem);\r
5828 }\r
5829 \r
5830 #if MALLOC_INSPECT_ALL\r
5831 void mspace_inspect_all(mspace msp,\r
5832                         void(*handler)(void *start,\r
5833                                        void *end,\r
5834                                        size_t used_bytes,\r
5835                                        void* callback_arg),\r
5836                         void* arg) {\r
5837   mstate ms = (mstate)msp;\r
5838   if (ok_magic(ms)) {\r
5839     if (!PREACTION(ms)) {\r
5840       internal_inspect_all(ms, handler, arg);\r
5841       POSTACTION(ms);\r
5842     }\r
5843   }\r
5844   else {\r
5845     USAGE_ERROR_ACTION(ms,ms);\r
5846   }\r
5847 }\r
5848 #endif /* MALLOC_INSPECT_ALL */\r
5849 \r
5850 int mspace_trim(mspace msp, size_t pad) {\r
5851   int result = 0;\r
5852   mstate ms = (mstate)msp;\r
5853   if (ok_magic(ms)) {\r
5854     if (!PREACTION(ms)) {\r
5855       result = sys_trim(ms, pad);\r
5856       POSTACTION(ms);\r
5857     }\r
5858   }\r
5859   else {\r
5860     USAGE_ERROR_ACTION(ms,ms);\r
5861   }\r
5862   return result;\r
5863 }\r
5864 \r
5865 #if !NO_MALLOC_STATS\r
5866 void mspace_malloc_stats(mspace msp) {\r
5867   mstate ms = (mstate)msp;\r
5868   if (ok_magic(ms)) {\r
5869     internal_malloc_stats(ms);\r
5870   }\r
5871   else {\r
5872     USAGE_ERROR_ACTION(ms,ms);\r
5873   }\r
5874 }\r
5875 #endif /* NO_MALLOC_STATS */\r
5876 \r
5877 size_t mspace_footprint(mspace msp) {\r
5878   size_t result = 0;\r
5879   mstate ms = (mstate)msp;\r
5880   if (ok_magic(ms)) {\r
5881     result = ms->footprint;\r
5882   }\r
5883   else {\r
5884     USAGE_ERROR_ACTION(ms,ms);\r
5885   }\r
5886   return result;\r
5887 }\r
5888 \r
5889 size_t mspace_max_footprint(mspace msp) {\r
5890   size_t result = 0;\r
5891   mstate ms = (mstate)msp;\r
5892   if (ok_magic(ms)) {\r
5893     result = ms->max_footprint;\r
5894   }\r
5895   else {\r
5896     USAGE_ERROR_ACTION(ms,ms);\r
5897   }\r
5898   return result;\r
5899 }\r
5900 \r
5901 size_t mspace_footprint_limit(mspace msp) {\r
5902   size_t result = 0;\r
5903   mstate ms = (mstate)msp;\r
5904   if (ok_magic(ms)) {\r
5905     size_t maf = ms->footprint_limit;\r
5906     result = (maf == 0) ? MAX_SIZE_T : maf;\r
5907   }\r
5908   else {\r
5909     USAGE_ERROR_ACTION(ms,ms);\r
5910   }\r
5911   return result;\r
5912 }\r
5913 \r
5914 size_t mspace_set_footprint_limit(mspace msp, size_t bytes) {\r
5915   size_t result = 0;\r
5916   mstate ms = (mstate)msp;\r
5917   if (ok_magic(ms)) {\r
5918     if (bytes == 0)\r
5919       result = granularity_align(1); /* Use minimal size */\r
5920     if (bytes == MAX_SIZE_T)\r
5921       result = 0;                    /* disable */\r
5922     else\r
5923       result = granularity_align(bytes);\r
5924     ms->footprint_limit = result;\r
5925   }\r
5926   else {\r
5927     USAGE_ERROR_ACTION(ms,ms);\r
5928   }\r
5929   return result;\r
5930 }\r
5931 \r
5932 #if !NO_MALLINFO\r
5933 struct mallinfo mspace_mallinfo(mspace msp) {\r
5934   mstate ms = (mstate)msp;\r
5935   if (!ok_magic(ms)) {\r
5936     USAGE_ERROR_ACTION(ms,ms);\r
5937   }\r
5938   return internal_mallinfo(ms);\r
5939 }\r
5940 #endif /* NO_MALLINFO */\r
5941 \r
5942 size_t mspace_usable_size(void* mem) {\r
5943   if (mem != 0) {\r
5944     mchunkptr p = mem2chunk(mem);\r
5945     if (is_inuse(p))\r
5946       return chunksize(p) - overhead_for(p);\r
5947   }\r
5948   return 0;\r
5949 }\r
5950 \r
5951 int mspace_mallopt(int param_number, int value) {\r
5952   return change_mparam(param_number, value);\r
5953 }\r
5954 \r
5955 #endif /* MSPACES */\r
5956 \r
5957 \r
5958 /* -------------------- Alternative MORECORE functions ------------------- */\r
5959 \r
5960 /*\r
5961   Guidelines for creating a custom version of MORECORE:\r
5962 \r
5963   * For best performance, MORECORE should allocate in multiples of pagesize.\r
5964   * MORECORE may allocate more memory than requested. (Or even less,\r
5965       but this will usually result in a malloc failure.)\r
5966   * MORECORE must not allocate memory when given argument zero, but\r
5967       instead return one past the end address of memory from previous\r
5968       nonzero call.\r
5969   * For best performance, consecutive calls to MORECORE with positive\r
5970       arguments should return increasing addresses, indicating that\r
5971       space has been contiguously extended.\r
5972   * Even though consecutive calls to MORECORE need not return contiguous\r
5973       addresses, it must be OK for malloc'ed chunks to span multiple\r
5974       regions in those cases where they do happen to be contiguous.\r
5975   * MORECORE need not handle negative arguments -- it may instead\r
5976       just return MFAIL when given negative arguments.\r
5977       Negative arguments are always multiples of pagesize. MORECORE\r
5978       must not misinterpret negative args as large positive unsigned\r
5979       args. You can suppress all such calls from even occurring by defining\r
5980       MORECORE_CANNOT_TRIM,\r
5981 \r
5982   As an example alternative MORECORE, here is a custom allocator\r
5983   kindly contributed for pre-OSX macOS.  It uses virtually but not\r
5984   necessarily physically contiguous non-paged memory (locked in,\r
5985   present and won't get swapped out).  You can use it by uncommenting\r
5986   this section, adding some #includes, and setting up the appropriate\r
5987   defines above:\r
5988 \r
5989       #define MORECORE osMoreCore\r
5990 \r
5991   There is also a shutdown routine that should somehow be called for\r
5992   cleanup upon program exit.\r
5993 \r
5994   #define MAX_POOL_ENTRIES 100\r
5995   #define MINIMUM_MORECORE_SIZE  (64 * 1024U)\r
5996   static int next_os_pool;\r
5997   void *our_os_pools[MAX_POOL_ENTRIES];\r
5998 \r
5999   void *osMoreCore(int size)\r
6000   {\r
6001     void *ptr = 0;\r
6002     static void *sbrk_top = 0;\r
6003 \r
6004     if (size > 0)\r
6005     {\r
6006       if (size < MINIMUM_MORECORE_SIZE)\r
6007          size = MINIMUM_MORECORE_SIZE;\r
6008       if (CurrentExecutionLevel() == kTaskLevel)\r
6009          ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);\r
6010       if (ptr == 0)\r
6011       {\r
6012         return (void *) MFAIL;\r
6013       }\r
6014       // save ptrs so they can be freed during cleanup\r
6015       our_os_pools[next_os_pool] = ptr;\r
6016       next_os_pool++;\r
6017       ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);\r
6018       sbrk_top = (char *) ptr + size;\r
6019       return ptr;\r
6020     }\r
6021     else if (size < 0)\r
6022     {\r
6023       // we don't currently support shrink behavior\r
6024       return (void *) MFAIL;\r
6025     }\r
6026     else\r
6027     {\r
6028       return sbrk_top;\r
6029     }\r
6030   }\r
6031 \r
6032   // cleanup any allocated memory pools\r
6033   // called as last thing before shutting down driver\r
6034 \r
6035   void osCleanupMem(void)\r
6036   {\r
6037     void **ptr;\r
6038 \r
6039     for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)\r
6040       if (*ptr)\r
6041       {\r
6042          PoolDeallocate(*ptr);\r
6043          *ptr = 0;\r
6044       }\r
6045   }\r
6046 \r
6047 */\r
6048 \r
6049 \r
6050 /* -----------------------------------------------------------------------\r
6051 History:\r
6052     v2.8.5 Sun May 22 10:26:02 2011  Doug Lea  (dl at gee)\r
6053       * Always perform unlink checks unless INSECURE\r
6054       * Add posix_memalign.\r
6055       * Improve realloc to expand in more cases; expose realloc_in_place.\r
6056         Thanks to Peter Buhr for the suggestion.\r
6057       * Add footprint_limit, inspect_all, bulk_free. Thanks\r
6058         to Barry Hayes and others for the suggestions.\r
6059       * Internal refactorings to avoid calls while holding locks\r
6060       * Use non-reentrant locks by default. Thanks to Roland McGrath\r
6061         for the suggestion.\r
6062       * Small fixes to mspace_destroy, reset_on_error.\r
6063       * Various configuration extensions/changes. Thanks\r
6064          to all who contributed these.\r
6065 \r
6066     V2.8.4a Thu Apr 28 14:39:43 2011 (dl at gee.cs.oswego.edu)\r
6067       * Update Creative Commons URL\r
6068 \r
6069     V2.8.4 Wed May 27 09:56:23 2009  Doug Lea  (dl at gee)\r
6070       * Use zeros instead of prev foot for is_mmapped\r
6071       * Add mspace_track_large_chunks; thanks to Jean Brouwers\r
6072       * Fix set_inuse in internal_realloc; thanks to Jean Brouwers\r
6073       * Fix insufficient sys_alloc padding when using 16byte alignment\r
6074       * Fix bad error check in mspace_footprint\r
6075       * Adaptations for ptmalloc; thanks to Wolfram Gloger.\r
6076       * Reentrant spin locks; thanks to Earl Chew and others\r
6077       * Win32 improvements; thanks to Niall Douglas and Earl Chew\r
6078       * Add NO_SEGMENT_TRAVERSAL and MAX_RELEASE_CHECK_RATE options\r
6079       * Extension hook in malloc_state\r
6080       * Various small adjustments to reduce warnings on some compilers\r
6081       * Various configuration extensions/changes for more platforms. Thanks\r
6082          to all who contributed these.\r
6083 \r
6084     V2.8.3 Thu Sep 22 11:16:32 2005  Doug Lea  (dl at gee)\r
6085       * Add max_footprint functions\r
6086       * Ensure all appropriate literals are size_t\r
6087       * Fix conditional compilation problem for some #define settings\r
6088       * Avoid concatenating segments with the one provided\r
6089         in create_mspace_with_base\r
6090       * Rename some variables to avoid compiler shadowing warnings\r
6091       * Use explicit lock initialization.\r
6092       * Better handling of sbrk interference.\r
6093       * Simplify and fix segment insertion, trimming and mspace_destroy\r
6094       * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x\r
6095       * Thanks especially to Dennis Flanagan for help on these.\r
6096 \r
6097     V2.8.2 Sun Jun 12 16:01:10 2005  Doug Lea  (dl at gee)\r
6098       * Fix memalign brace error.\r
6099 \r
6100     V2.8.1 Wed Jun  8 16:11:46 2005  Doug Lea  (dl at gee)\r
6101       * Fix improper #endif nesting in C++\r
6102       * Add explicit casts needed for C++\r
6103 \r
6104     V2.8.0 Mon May 30 14:09:02 2005  Doug Lea  (dl at gee)\r
6105       * Use trees for large bins\r
6106       * Support mspaces\r
6107       * Use segments to unify sbrk-based and mmap-based system allocation,\r
6108         removing need for emulation on most platforms without sbrk.\r
6109       * Default safety checks\r
6110       * Optional footer checks. Thanks to William Robertson for the idea.\r
6111       * Internal code refactoring\r
6112       * Incorporate suggestions and platform-specific changes.\r
6113         Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,\r
6114         Aaron Bachmann,  Emery Berger, and others.\r
6115       * Speed up non-fastbin processing enough to remove fastbins.\r
6116       * Remove useless cfree() to avoid conflicts with other apps.\r
6117       * Remove internal memcpy, memset. Compilers handle builtins better.\r
6118       * Remove some options that no one ever used and rename others.\r
6119 \r
6120     V2.7.2 Sat Aug 17 09:07:30 2002  Doug Lea  (dl at gee)\r
6121       * Fix malloc_state bitmap array misdeclaration\r
6122 \r
6123     V2.7.1 Thu Jul 25 10:58:03 2002  Doug Lea  (dl at gee)\r
6124       * Allow tuning of FIRST_SORTED_BIN_SIZE\r
6125       * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.\r
6126       * Better detection and support for non-contiguousness of MORECORE.\r
6127         Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger\r
6128       * Bypass most of malloc if no frees. Thanks To Emery Berger.\r
6129       * Fix freeing of old top non-contiguous chunk im sysmalloc.\r
6130       * Raised default trim and map thresholds to 256K.\r
6131       * Fix mmap-related #defines. Thanks to Lubos Lunak.\r
6132       * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.\r
6133       * Branch-free bin calculation\r
6134       * Default trim and mmap thresholds now 256K.\r
6135 \r
6136     V2.7.0 Sun Mar 11 14:14:06 2001  Doug Lea  (dl at gee)\r
6137       * Introduce independent_comalloc and independent_calloc.\r
6138         Thanks to Michael Pachos for motivation and help.\r
6139       * Make optional .h file available\r
6140       * Allow > 2GB requests on 32bit systems.\r
6141       * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.\r
6142         Thanks also to Andreas Mueller <a.mueller at paradatec.de>,\r
6143         and Anonymous.\r
6144       * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for\r
6145         helping test this.)\r
6146       * memalign: check alignment arg\r
6147       * realloc: don't try to shift chunks backwards, since this\r
6148         leads to  more fragmentation in some programs and doesn't\r
6149         seem to help in any others.\r
6150       * Collect all cases in malloc requiring system memory into sysmalloc\r
6151       * Use mmap as backup to sbrk\r
6152       * Place all internal state in malloc_state\r
6153       * Introduce fastbins (although similar to 2.5.1)\r
6154       * Many minor tunings and cosmetic improvements\r
6155       * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK\r
6156       * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS\r
6157         Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.\r
6158       * Include errno.h to support default failure action.\r
6159 \r
6160     V2.6.6 Sun Dec  5 07:42:19 1999  Doug Lea  (dl at gee)\r
6161       * return null for negative arguments\r
6162       * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>\r
6163          * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'\r
6164           (e.g. WIN32 platforms)\r
6165          * Cleanup header file inclusion for WIN32 platforms\r
6166          * Cleanup code to avoid Microsoft Visual C++ compiler complaints\r
6167          * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing\r
6168            memory allocation routines\r
6169          * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)\r
6170          * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to\r
6171            usage of 'assert' in non-WIN32 code\r
6172          * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to\r
6173            avoid infinite loop\r
6174       * Always call 'fREe()' rather than 'free()'\r
6175 \r
6176     V2.6.5 Wed Jun 17 15:57:31 1998  Doug Lea  (dl at gee)\r
6177       * Fixed ordering problem with boundary-stamping\r
6178 \r
6179     V2.6.3 Sun May 19 08:17:58 1996  Doug Lea  (dl at gee)\r
6180       * Added pvalloc, as recommended by H.J. Liu\r
6181       * Added 64bit pointer support mainly from Wolfram Gloger\r
6182       * Added anonymously donated WIN32 sbrk emulation\r
6183       * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen\r
6184       * malloc_extend_top: fix mask error that caused wastage after\r
6185         foreign sbrks\r
6186       * Add linux mremap support code from HJ Liu\r
6187 \r
6188     V2.6.2 Tue Dec  5 06:52:55 1995  Doug Lea  (dl at gee)\r
6189       * Integrated most documentation with the code.\r
6190       * Add support for mmap, with help from\r
6191         Wolfram Gloger (Gloger@lrz.uni-muenchen.de).\r
6192       * Use last_remainder in more cases.\r
6193       * Pack bins using idea from  colin@nyx10.cs.du.edu\r
6194       * Use ordered bins instead of best-fit threshhold\r
6195       * Eliminate block-local decls to simplify tracing and debugging.\r
6196       * Support another case of realloc via move into top\r
6197       * Fix error occuring when initial sbrk_base not word-aligned.\r
6198       * Rely on page size for units instead of SBRK_UNIT to\r
6199         avoid surprises about sbrk alignment conventions.\r
6200       * Add mallinfo, mallopt. Thanks to Raymond Nijssen\r
6201         (raymond@es.ele.tue.nl) for the suggestion.\r
6202       * Add `pad' argument to malloc_trim and top_pad mallopt parameter.\r
6203       * More precautions for cases where other routines call sbrk,\r
6204         courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).\r
6205       * Added macros etc., allowing use in linux libc from\r
6206         H.J. Lu (hjl@gnu.ai.mit.edu)\r
6207       * Inverted this history list\r
6208 \r
6209     V2.6.1 Sat Dec  2 14:10:57 1995  Doug Lea  (dl at gee)\r
6210       * Re-tuned and fixed to behave more nicely with V2.6.0 changes.\r
6211       * Removed all preallocation code since under current scheme\r
6212         the work required to undo bad preallocations exceeds\r
6213         the work saved in good cases for most test programs.\r
6214       * No longer use return list or unconsolidated bins since\r
6215         no scheme using them consistently outperforms those that don't\r
6216         given above changes.\r
6217       * Use best fit for very large chunks to prevent some worst-cases.\r
6218       * Added some support for debugging\r
6219 \r
6220     V2.6.0 Sat Nov  4 07:05:23 1995  Doug Lea  (dl at gee)\r
6221       * Removed footers when chunks are in use. Thanks to\r
6222         Paul Wilson (wilson@cs.texas.edu) for the suggestion.\r
6223 \r
6224     V2.5.4 Wed Nov  1 07:54:51 1995  Doug Lea  (dl at gee)\r
6225       * Added malloc_trim, with help from Wolfram Gloger\r
6226         (wmglo@Dent.MED.Uni-Muenchen.DE).\r
6227 \r
6228     V2.5.3 Tue Apr 26 10:16:01 1994  Doug Lea  (dl at g)\r
6229 \r
6230     V2.5.2 Tue Apr  5 16:20:40 1994  Doug Lea  (dl at g)\r
6231       * realloc: try to expand in both directions\r
6232       * malloc: swap order of clean-bin strategy;\r
6233       * realloc: only conditionally expand backwards\r
6234       * Try not to scavenge used bins\r
6235       * Use bin counts as a guide to preallocation\r
6236       * Occasionally bin return list chunks in first scan\r
6237       * Add a few optimizations from colin@nyx10.cs.du.edu\r
6238 \r
6239     V2.5.1 Sat Aug 14 15:40:43 1993  Doug Lea  (dl at g)\r
6240       * faster bin computation & slightly different binning\r
6241       * merged all consolidations to one part of malloc proper\r
6242          (eliminating old malloc_find_space & malloc_clean_bin)\r
6243       * Scan 2 returns chunks (not just 1)\r
6244       * Propagate failure in realloc if malloc returns 0\r
6245       * Add stuff to allow compilation on non-ANSI compilers\r
6246           from kpv@research.att.com\r
6247 \r
6248     V2.5 Sat Aug  7 07:41:59 1993  Doug Lea  (dl at g.oswego.edu)\r
6249       * removed potential for odd address access in prev_chunk\r
6250       * removed dependency on getpagesize.h\r
6251       * misc cosmetics and a bit more internal documentation\r
6252       * anticosmetics: mangled names in macros to evade debugger strangeness\r
6253       * tested on sparc, hp-700, dec-mips, rs6000\r
6254           with gcc & native cc (hp, dec only) allowing\r
6255           Detlefs & Zorn comparison study (in SIGPLAN Notices.)\r
6256 \r
6257     Trial version Fri Aug 28 13:14:29 1992  Doug Lea  (dl at g.oswego.edu)\r
6258       * Based loosely on libg++-1.2X malloc. (It retains some of the overall\r
6259          structure of old version,  but most details differ.)\r
6260 \r
6261 */\r
6262 #endif\r
6263 \r
6264 #ifdef TEST\r
6265 #include "_PDCLIB_test.h"\r
6266 \r
6267 /* TODO: TEST ME */\r
6268 int main( void )\r
6269 {\r
6270     return TEST_RESULTS;\r
6271 }\r
6272 \r
6273 #endif\r