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