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