458d96a2417deebfdb8a28848978d7cf942e9081
[kopensolaris-gnu/glibc.git] / malloc / malloc.c
1 /* Malloc implementation for multiple threads without lock contention.
2    Copyright (C) 1996-2002, 2003 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Contributed by Wolfram Gloger <wg@malloc.de>
5    and Doug Lea <dl@cs.oswego.edu>, 2001.
6
7    The GNU C Library is free software; you can redistribute it and/or
8    modify it under the terms of the GNU Lesser General Public License as
9    published by the Free Software Foundation; either version 2.1 of the
10    License, or (at your option) any later version.
11
12    The GNU C Library is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15    Lesser General Public License for more details.
16
17    You should have received a copy of the GNU Lesser General Public
18    License along with the GNU C Library; see the file COPYING.LIB.  If not,
19    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20    Boston, MA 02111-1307, USA.  */
21
22 /*
23   This is a version (aka ptmalloc2) of malloc/free/realloc written by
24   Doug Lea and adapted to multiple threads/arenas by Wolfram Gloger.
25
26 * Version ptmalloc2-20011215
27   $Id$
28   based on:
29   VERSION 2.7.0 Sun Mar 11 14:14:06 2001  Doug Lea  (dl at gee)
30
31    Note: There may be an updated version of this malloc obtainable at
32            http://www.malloc.de/malloc/ptmalloc2.tar.gz
33          Check before installing!
34
35 * Quickstart
36
37   In order to compile this implementation, a Makefile is provided with
38   the ptmalloc2 distribution, which has pre-defined targets for some
39   popular systems (e.g. "make posix" for Posix threads).  All that is
40   typically required with regard to compiler flags is the selection of
41   the thread package via defining one out of USE_PTHREADS, USE_THR or
42   USE_SPROC.  Check the thread-m.h file for what effects this has.
43   Many/most systems will additionally require USE_TSD_DATA_HACK to be
44   defined, so this is the default for "make posix".
45
46 * Why use this malloc?
47
48   This is not the fastest, most space-conserving, most portable, or
49   most tunable malloc ever written. However it is among the fastest
50   while also being among the most space-conserving, portable and tunable.
51   Consistent balance across these factors results in a good general-purpose
52   allocator for malloc-intensive programs.
53
54   The main properties of the algorithms are:
55   * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
56     with ties normally decided via FIFO (i.e. least recently used).
57   * For small (<= 64 bytes by default) requests, it is a caching
58     allocator, that maintains pools of quickly recycled chunks.
59   * In between, and for combinations of large and small requests, it does
60     the best it can trying to meet both goals at once.
61   * For very large requests (>= 128KB by default), it relies on system
62     memory mapping facilities, if supported.
63
64   For a longer but slightly out of date high-level description, see
65      http://gee.cs.oswego.edu/dl/html/malloc.html
66
67   You may already by default be using a C library containing a malloc
68   that is  based on some version of this malloc (for example in
69   linux). You might still want to use the one in this file in order to
70   customize settings or to avoid overheads associated with library
71   versions.
72
73 * Contents, described in more detail in "description of public routines" below.
74
75   Standard (ANSI/SVID/...)  functions:
76     malloc(size_t n);
77     calloc(size_t n_elements, size_t element_size);
78     free(Void_t* p);
79     realloc(Void_t* p, size_t n);
80     memalign(size_t alignment, size_t n);
81     valloc(size_t n);
82     mallinfo()
83     mallopt(int parameter_number, int parameter_value)
84
85   Additional functions:
86     independent_calloc(size_t n_elements, size_t size, Void_t* chunks[]);
87     independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
88     pvalloc(size_t n);
89     cfree(Void_t* p);
90     malloc_trim(size_t pad);
91     malloc_usable_size(Void_t* p);
92     malloc_stats();
93
94 * Vital statistics:
95
96   Supported pointer representation:       4 or 8 bytes
97   Supported size_t  representation:       4 or 8 bytes
98        Note that size_t is allowed to be 4 bytes even if pointers are 8.
99        You can adjust this by defining INTERNAL_SIZE_T
100
101   Alignment:                              2 * sizeof(size_t) (default)
102        (i.e., 8 byte alignment with 4byte size_t). This suffices for
103        nearly all current machines and C compilers. However, you can
104        define MALLOC_ALIGNMENT to be wider than this if necessary.
105
106   Minimum overhead per allocated chunk:   4 or 8 bytes
107        Each malloced chunk has a hidden word of overhead holding size
108        and status information.
109
110   Minimum allocated size: 4-byte ptrs:  16 bytes    (including 4 overhead)
111                           8-byte ptrs:  24/32 bytes (including, 4/8 overhead)
112
113        When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
114        ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
115        needed; 4 (8) for a trailing size field and 8 (16) bytes for
116        free list pointers. Thus, the minimum allocatable size is
117        16/24/32 bytes.
118
119        Even a request for zero bytes (i.e., malloc(0)) returns a
120        pointer to something of the minimum allocatable size.
121
122        The maximum overhead wastage (i.e., number of extra bytes
123        allocated than were requested in malloc) is less than or equal
124        to the minimum size, except for requests >= mmap_threshold that
125        are serviced via mmap(), where the worst case wastage is 2 *
126        sizeof(size_t) bytes plus the remainder from a system page (the
127        minimal mmap unit); typically 4096 or 8192 bytes.
128
129   Maximum allocated size:  4-byte size_t: 2^32 minus about two pages
130                            8-byte size_t: 2^64 minus about two pages
131
132        It is assumed that (possibly signed) size_t values suffice to
133        represent chunk sizes. `Possibly signed' is due to the fact
134        that `size_t' may be defined on a system as either a signed or
135        an unsigned type. The ISO C standard says that it must be
136        unsigned, but a few systems are known not to adhere to this.
137        Additionally, even when size_t is unsigned, sbrk (which is by
138        default used to obtain memory from system) accepts signed
139        arguments, and may not be able to handle size_t-wide arguments
140        with negative sign bit.  Generally, values that would
141        appear as negative after accounting for overhead and alignment
142        are supported only via mmap(), which does not have this
143        limitation.
144
145        Requests for sizes outside the allowed range will perform an optional
146        failure action and then return null. (Requests may also
147        also fail because a system is out of memory.)
148
149   Thread-safety: thread-safe unless NO_THREADS is defined
150
151   Compliance: I believe it is compliant with the 1997 Single Unix Specification
152        (See http://www.opennc.org). Also SVID/XPG, ANSI C, and probably
153        others as well.
154
155 * Synopsis of compile-time options:
156
157     People have reported using previous versions of this malloc on all
158     versions of Unix, sometimes by tweaking some of the defines
159     below. It has been tested most extensively on Solaris and
160     Linux. It is also reported to work on WIN32 platforms.
161     People also report using it in stand-alone embedded systems.
162
163     The implementation is in straight, hand-tuned ANSI C.  It is not
164     at all modular. (Sorry!)  It uses a lot of macros.  To be at all
165     usable, this code should be compiled using an optimizing compiler
166     (for example gcc -O3) that can simplify expressions and control
167     paths. (FAQ: some macros import variables as arguments rather than
168     declare locals because people reported that some debuggers
169     otherwise get confused.)
170
171     OPTION                     DEFAULT VALUE
172
173     Compilation Environment options:
174
175     __STD_C                    derived from C compiler defines
176     WIN32                      NOT defined
177     HAVE_MEMCPY                defined
178     USE_MEMCPY                 1 if HAVE_MEMCPY is defined
179     HAVE_MMAP                  defined as 1
180     MMAP_CLEARS                1
181     HAVE_MREMAP                0 unless linux defined
182     USE_ARENAS                 the same as HAVE_MMAP
183     malloc_getpagesize         derived from system #includes, or 4096 if not
184     HAVE_USR_INCLUDE_MALLOC_H  NOT defined
185     LACKS_UNISTD_H             NOT defined unless WIN32
186     LACKS_SYS_PARAM_H          NOT defined unless WIN32
187     LACKS_SYS_MMAN_H           NOT defined unless WIN32
188
189     Changing default word sizes:
190
191     INTERNAL_SIZE_T            size_t
192     MALLOC_ALIGNMENT           2 * sizeof(INTERNAL_SIZE_T)
193
194     Configuration and functionality options:
195
196     USE_DL_PREFIX              NOT defined
197     USE_PUBLIC_MALLOC_WRAPPERS NOT defined
198     USE_MALLOC_LOCK            NOT defined
199     MALLOC_DEBUG               NOT defined
200     REALLOC_ZERO_BYTES_FREES   1
201     MALLOC_FAILURE_ACTION      errno = ENOMEM, if __STD_C defined, else no-op
202     TRIM_FASTBINS              0
203
204     Options for customizing MORECORE:
205
206     MORECORE                   sbrk
207     MORECORE_FAILURE           -1
208     MORECORE_CONTIGUOUS        1
209     MORECORE_CANNOT_TRIM       NOT defined
210     MORECORE_CLEARS            1
211     MMAP_AS_MORECORE_SIZE      (1024 * 1024)
212
213     Tuning options that are also dynamically changeable via mallopt:
214
215     DEFAULT_MXFAST             64
216     DEFAULT_TRIM_THRESHOLD     128 * 1024
217     DEFAULT_TOP_PAD            0
218     DEFAULT_MMAP_THRESHOLD     128 * 1024
219     DEFAULT_MMAP_MAX           65536
220
221     There are several other #defined constants and macros that you
222     probably don't want to touch unless you are extending or adapting malloc.  */
223
224 /*
225   __STD_C should be nonzero if using ANSI-standard C compiler, a C++
226   compiler, or a C compiler sufficiently close to ANSI to get away
227   with it.
228 */
229
230 #ifndef __STD_C
231 #if defined(__STDC__) || defined(__cplusplus)
232 #define __STD_C     1
233 #else
234 #define __STD_C     0
235 #endif
236 #endif /*__STD_C*/
237
238
239 /*
240   Void_t* is the pointer type that malloc should say it returns
241 */
242
243 #ifndef Void_t
244 #if (__STD_C || defined(WIN32))
245 #define Void_t      void
246 #else
247 #define Void_t      char
248 #endif
249 #endif /*Void_t*/
250
251 #if __STD_C
252 #include <stddef.h>   /* for size_t */
253 #include <stdlib.h>   /* for getenv(), abort() */
254 #else
255 #include <sys/types.h>
256 #endif
257
258 #ifdef __cplusplus
259 extern "C" {
260 #endif
261
262 /* define LACKS_UNISTD_H if your system does not have a <unistd.h>. */
263
264 /* #define  LACKS_UNISTD_H */
265
266 #ifndef LACKS_UNISTD_H
267 #include <unistd.h>
268 #endif
269
270 /* define LACKS_SYS_PARAM_H if your system does not have a <sys/param.h>. */
271
272 /* #define  LACKS_SYS_PARAM_H */
273
274
275 #include <stdio.h>    /* needed for malloc_stats */
276 #include <errno.h>    /* needed for optional MALLOC_FAILURE_ACTION */
277
278
279 /*
280   Debugging:
281
282   Because freed chunks may be overwritten with bookkeeping fields, this
283   malloc will often die when freed memory is overwritten by user
284   programs.  This can be very effective (albeit in an annoying way)
285   in helping track down dangling pointers.
286
287   If you compile with -DMALLOC_DEBUG, a number of assertion checks are
288   enabled that will catch more memory errors. You probably won't be
289   able to make much sense of the actual assertion errors, but they
290   should help you locate incorrectly overwritten memory.  The checking
291   is fairly extensive, and will slow down execution
292   noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set
293   will attempt to check every non-mmapped allocated and free chunk in
294   the course of computing the summmaries. (By nature, mmapped regions
295   cannot be checked very much automatically.)
296
297   Setting MALLOC_DEBUG may also be helpful if you are trying to modify
298   this code. The assertions in the check routines spell out in more
299   detail the assumptions and invariants underlying the algorithms.
300
301   Setting MALLOC_DEBUG does NOT provide an automated mechanism for
302   checking that all accesses to malloced memory stay within their
303   bounds. However, there are several add-ons and adaptations of this
304   or other mallocs available that do this.
305 */
306
307 #if MALLOC_DEBUG
308 #include <assert.h>
309 #else
310 #undef  assert
311 #define assert(x) ((void)0)
312 #endif
313
314
315 /*
316   INTERNAL_SIZE_T is the word-size used for internal bookkeeping
317   of chunk sizes.
318
319   The default version is the same as size_t.
320
321   While not strictly necessary, it is best to define this as an
322   unsigned type, even if size_t is a signed type. This may avoid some
323   artificial size limitations on some systems.
324
325   On a 64-bit machine, you may be able to reduce malloc overhead by
326   defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
327   expense of not being able to handle more than 2^32 of malloced
328   space. If this limitation is acceptable, you are encouraged to set
329   this unless you are on a platform requiring 16byte alignments. In
330   this case the alignment requirements turn out to negate any
331   potential advantages of decreasing size_t word size.
332
333   Implementors: Beware of the possible combinations of:
334      - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
335        and might be the same width as int or as long
336      - size_t might have different width and signedness as INTERNAL_SIZE_T
337      - int and long might be 32 or 64 bits, and might be the same width
338   To deal with this, most comparisons and difference computations
339   among INTERNAL_SIZE_Ts should cast them to unsigned long, being
340   aware of the fact that casting an unsigned int to a wider long does
341   not sign-extend. (This also makes checking for negative numbers
342   awkward.) Some of these casts result in harmless compiler warnings
343   on some systems.
344 */
345
346 #ifndef INTERNAL_SIZE_T
347 #define INTERNAL_SIZE_T size_t
348 #endif
349
350 /* The corresponding word size */
351 #define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
352
353
354 /*
355   MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
356   It must be a power of two at least 2 * SIZE_SZ, even on machines
357   for which smaller alignments would suffice. It may be defined as
358   larger than this though. Note however that code and data structures
359   are optimized for the case of 8-byte alignment.
360 */
361
362
363 #ifndef MALLOC_ALIGNMENT
364 #define MALLOC_ALIGNMENT       (2 * SIZE_SZ)
365 #endif
366
367 /* The corresponding bit mask value */
368 #define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
369
370
371
372 /*
373   REALLOC_ZERO_BYTES_FREES should be set if a call to
374   realloc with zero bytes should be the same as a call to free.
375   This is required by the C standard. Otherwise, since this malloc
376   returns a unique pointer for malloc(0), so does realloc(p, 0).
377 */
378
379 #ifndef REALLOC_ZERO_BYTES_FREES
380 #define REALLOC_ZERO_BYTES_FREES 1
381 #endif
382
383 /*
384   TRIM_FASTBINS controls whether free() of a very small chunk can
385   immediately lead to trimming. Setting to true (1) can reduce memory
386   footprint, but will almost always slow down programs that use a lot
387   of small chunks.
388
389   Define this only if you are willing to give up some speed to more
390   aggressively reduce system-level memory footprint when releasing
391   memory in programs that use many small chunks.  You can get
392   essentially the same effect by setting MXFAST to 0, but this can
393   lead to even greater slowdowns in programs using many small chunks.
394   TRIM_FASTBINS is an in-between compile-time option, that disables
395   only those chunks bordering topmost memory from being placed in
396   fastbins.
397 */
398
399 #ifndef TRIM_FASTBINS
400 #define TRIM_FASTBINS  0
401 #endif
402
403
404 /*
405   USE_DL_PREFIX will prefix all public routines with the string 'dl'.
406   This is necessary when you only want to use this malloc in one part
407   of a program, using your regular system malloc elsewhere.
408 */
409
410 /* #define USE_DL_PREFIX */
411
412
413 /*
414    Two-phase name translation.
415    All of the actual routines are given mangled names.
416    When wrappers are used, they become the public callable versions.
417    When DL_PREFIX is used, the callable names are prefixed.
418 */
419
420 #ifdef USE_DL_PREFIX
421 #define public_cALLOc    dlcalloc
422 #define public_fREe      dlfree
423 #define public_cFREe     dlcfree
424 #define public_mALLOc    dlmalloc
425 #define public_mEMALIGn  dlmemalign
426 #define public_rEALLOc   dlrealloc
427 #define public_vALLOc    dlvalloc
428 #define public_pVALLOc   dlpvalloc
429 #define public_mALLINFo  dlmallinfo
430 #define public_mALLOPt   dlmallopt
431 #define public_mTRIm     dlmalloc_trim
432 #define public_mSTATs    dlmalloc_stats
433 #define public_mUSABLe   dlmalloc_usable_size
434 #define public_iCALLOc   dlindependent_calloc
435 #define public_iCOMALLOc dlindependent_comalloc
436 #define public_gET_STATe dlget_state
437 #define public_sET_STATe dlset_state
438 #else /* USE_DL_PREFIX */
439 #ifdef _LIBC
440
441 /* Special defines for the GNU C library.  */
442 #define public_cALLOc    __libc_calloc
443 #define public_fREe      __libc_free
444 #define public_cFREe     __libc_cfree
445 #define public_mALLOc    __libc_malloc
446 #define public_mEMALIGn  __libc_memalign
447 #define public_rEALLOc   __libc_realloc
448 #define public_vALLOc    __libc_valloc
449 #define public_pVALLOc   __libc_pvalloc
450 #define public_mALLINFo  __libc_mallinfo
451 #define public_mALLOPt   __libc_mallopt
452 #define public_mTRIm     __malloc_trim
453 #define public_mSTATs    __malloc_stats
454 #define public_mUSABLe   __malloc_usable_size
455 #define public_iCALLOc   __libc_independent_calloc
456 #define public_iCOMALLOc __libc_independent_comalloc
457 #define public_gET_STATe __malloc_get_state
458 #define public_sET_STATe __malloc_set_state
459 #define malloc_getpagesize __getpagesize()
460 #define open             __open
461 #define mmap             __mmap
462 #define munmap           __munmap
463 #define mremap           __mremap
464 #define mprotect         __mprotect
465 #define MORECORE         (*__morecore)
466 #define MORECORE_FAILURE 0
467
468 Void_t * __default_morecore (ptrdiff_t);
469 Void_t *(*__morecore)(ptrdiff_t) = __default_morecore;
470
471 #else /* !_LIBC */
472 #define public_cALLOc    calloc
473 #define public_fREe      free
474 #define public_cFREe     cfree
475 #define public_mALLOc    malloc
476 #define public_mEMALIGn  memalign
477 #define public_rEALLOc   realloc
478 #define public_vALLOc    valloc
479 #define public_pVALLOc   pvalloc
480 #define public_mALLINFo  mallinfo
481 #define public_mALLOPt   mallopt
482 #define public_mTRIm     malloc_trim
483 #define public_mSTATs    malloc_stats
484 #define public_mUSABLe   malloc_usable_size
485 #define public_iCALLOc   independent_calloc
486 #define public_iCOMALLOc independent_comalloc
487 #define public_gET_STATe malloc_get_state
488 #define public_sET_STATe malloc_set_state
489 #endif /* _LIBC */
490 #endif /* USE_DL_PREFIX */
491
492 #ifndef _LIBC
493 #define __builtin_expect(expr, val)     (expr)
494
495 #define fwrite(buf, size, count, fp) _IO_fwrite (buf, size, count, fp)
496 #endif
497
498 /*
499   HAVE_MEMCPY should be defined if you are not otherwise using
500   ANSI STD C, but still have memcpy and memset in your C library
501   and want to use them in calloc and realloc. Otherwise simple
502   macro versions are defined below.
503
504   USE_MEMCPY should be defined as 1 if you actually want to
505   have memset and memcpy called. People report that the macro
506   versions are faster than libc versions on some systems.
507
508   Even if USE_MEMCPY is set to 1, loops to copy/clear small chunks
509   (of <= 36 bytes) are manually unrolled in realloc and calloc.
510 */
511
512 #define HAVE_MEMCPY
513
514 #ifndef USE_MEMCPY
515 #ifdef HAVE_MEMCPY
516 #define USE_MEMCPY 1
517 #else
518 #define USE_MEMCPY 0
519 #endif
520 #endif
521
522
523 #if (__STD_C || defined(HAVE_MEMCPY))
524
525 #ifdef _LIBC
526 # include <string.h>
527 #else
528 #ifdef WIN32
529 /* On Win32 memset and memcpy are already declared in windows.h */
530 #else
531 #if __STD_C
532 void* memset(void*, int, size_t);
533 void* memcpy(void*, const void*, size_t);
534 #else
535 Void_t* memset();
536 Void_t* memcpy();
537 #endif
538 #endif
539 #endif
540 #endif
541
542 /*
543   MALLOC_FAILURE_ACTION is the action to take before "return 0" when
544   malloc fails to be able to return memory, either because memory is
545   exhausted or because of illegal arguments.
546
547   By default, sets errno if running on STD_C platform, else does nothing.
548 */
549
550 #ifndef MALLOC_FAILURE_ACTION
551 #if __STD_C
552 #define MALLOC_FAILURE_ACTION \
553    errno = ENOMEM;
554
555 #else
556 #define MALLOC_FAILURE_ACTION
557 #endif
558 #endif
559
560 /*
561   MORECORE-related declarations. By default, rely on sbrk
562 */
563
564
565 #ifdef LACKS_UNISTD_H
566 #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
567 #if __STD_C
568 extern Void_t*     sbrk(ptrdiff_t);
569 #else
570 extern Void_t*     sbrk();
571 #endif
572 #endif
573 #endif
574
575 /*
576   MORECORE is the name of the routine to call to obtain more memory
577   from the system.  See below for general guidance on writing
578   alternative MORECORE functions, as well as a version for WIN32 and a
579   sample version for pre-OSX macos.
580 */
581
582 #ifndef MORECORE
583 #define MORECORE sbrk
584 #endif
585
586 /*
587   MORECORE_FAILURE is the value returned upon failure of MORECORE
588   as well as mmap. Since it cannot be an otherwise valid memory address,
589   and must reflect values of standard sys calls, you probably ought not
590   try to redefine it.
591 */
592
593 #ifndef MORECORE_FAILURE
594 #define MORECORE_FAILURE (-1)
595 #endif
596
597 /*
598   If MORECORE_CONTIGUOUS is true, take advantage of fact that
599   consecutive calls to MORECORE with positive arguments always return
600   contiguous increasing addresses.  This is true of unix sbrk.  Even
601   if not defined, when regions happen to be contiguous, malloc will
602   permit allocations spanning regions obtained from different
603   calls. But defining this when applicable enables some stronger
604   consistency checks and space efficiencies.
605 */
606
607 #ifndef MORECORE_CONTIGUOUS
608 #define MORECORE_CONTIGUOUS 1
609 #endif
610
611 /*
612   Define MORECORE_CANNOT_TRIM if your version of MORECORE
613   cannot release space back to the system when given negative
614   arguments. This is generally necessary only if you are using
615   a hand-crafted MORECORE function that cannot handle negative arguments.
616 */
617
618 /* #define MORECORE_CANNOT_TRIM */
619
620 /*  MORECORE_CLEARS           (default 1)
621      The degree to which the routine mapped to MORECORE zeroes out
622      memory: never (0), only for newly allocated space (1) or always
623      (2).  The distinction between (1) and (2) is necessary because on
624      some systems, if the application first decrements and then
625      increments the break value, the contents of the reallocated space
626      are unspecified.
627 */
628
629 #ifndef MORECORE_CLEARS
630 #define MORECORE_CLEARS 1
631 #endif
632
633
634 /*
635   Define HAVE_MMAP as true to optionally make malloc() use mmap() to
636   allocate very large blocks.  These will be returned to the
637   operating system immediately after a free(). Also, if mmap
638   is available, it is used as a backup strategy in cases where
639   MORECORE fails to provide space from system.
640
641   This malloc is best tuned to work with mmap for large requests.
642   If you do not have mmap, operations involving very large chunks (1MB
643   or so) may be slower than you'd like.
644 */
645
646 #ifndef HAVE_MMAP
647 #define HAVE_MMAP 1
648
649 /*
650    Standard unix mmap using /dev/zero clears memory so calloc doesn't
651    need to.
652 */
653
654 #ifndef MMAP_CLEARS
655 #define MMAP_CLEARS 1
656 #endif
657
658 #else /* no mmap */
659 #ifndef MMAP_CLEARS
660 #define MMAP_CLEARS 0
661 #endif
662 #endif
663
664
665 /*
666    MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
667    sbrk fails, and mmap is used as a backup (which is done only if
668    HAVE_MMAP).  The value must be a multiple of page size.  This
669    backup strategy generally applies only when systems have "holes" in
670    address space, so sbrk cannot perform contiguous expansion, but
671    there is still space available on system.  On systems for which
672    this is known to be useful (i.e. most linux kernels), this occurs
673    only when programs allocate huge amounts of memory.  Between this,
674    and the fact that mmap regions tend to be limited, the size should
675    be large, to avoid too many mmap calls and thus avoid running out
676    of kernel resources.
677 */
678
679 #ifndef MMAP_AS_MORECORE_SIZE
680 #define MMAP_AS_MORECORE_SIZE (1024 * 1024)
681 #endif
682
683 /*
684   Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
685   large blocks.  This is currently only possible on Linux with
686   kernel versions newer than 1.3.77.
687 */
688
689 #ifndef HAVE_MREMAP
690 #ifdef linux
691 #define HAVE_MREMAP 1
692 #else
693 #define HAVE_MREMAP 0
694 #endif
695
696 #endif /* HAVE_MMAP */
697
698 /* Define USE_ARENAS to enable support for multiple `arenas'.  These
699    are allocated using mmap(), are necessary for threads and
700    occasionally useful to overcome address space limitations affecting
701    sbrk(). */
702
703 #ifndef USE_ARENAS
704 #define USE_ARENAS HAVE_MMAP
705 #endif
706
707
708 /*
709   The system page size. To the extent possible, this malloc manages
710   memory from the system in page-size units.  Note that this value is
711   cached during initialization into a field of malloc_state. So even
712   if malloc_getpagesize is a function, it is only called once.
713
714   The following mechanics for getpagesize were adapted from bsd/gnu
715   getpagesize.h. If none of the system-probes here apply, a value of
716   4096 is used, which should be OK: If they don't apply, then using
717   the actual value probably doesn't impact performance.
718 */
719
720
721 #ifndef malloc_getpagesize
722
723 #ifndef LACKS_UNISTD_H
724 #  include <unistd.h>
725 #endif
726
727 #  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
728 #    ifndef _SC_PAGE_SIZE
729 #      define _SC_PAGE_SIZE _SC_PAGESIZE
730 #    endif
731 #  endif
732
733 #  ifdef _SC_PAGE_SIZE
734 #    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
735 #  else
736 #    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
737        extern size_t getpagesize();
738 #      define malloc_getpagesize getpagesize()
739 #    else
740 #      ifdef WIN32 /* use supplied emulation of getpagesize */
741 #        define malloc_getpagesize getpagesize()
742 #      else
743 #        ifndef LACKS_SYS_PARAM_H
744 #          include <sys/param.h>
745 #        endif
746 #        ifdef EXEC_PAGESIZE
747 #          define malloc_getpagesize EXEC_PAGESIZE
748 #        else
749 #          ifdef NBPG
750 #            ifndef CLSIZE
751 #              define malloc_getpagesize NBPG
752 #            else
753 #              define malloc_getpagesize (NBPG * CLSIZE)
754 #            endif
755 #          else
756 #            ifdef NBPC
757 #              define malloc_getpagesize NBPC
758 #            else
759 #              ifdef PAGESIZE
760 #                define malloc_getpagesize PAGESIZE
761 #              else /* just guess */
762 #                define malloc_getpagesize (4096)
763 #              endif
764 #            endif
765 #          endif
766 #        endif
767 #      endif
768 #    endif
769 #  endif
770 #endif
771
772 /*
773   This version of malloc supports the standard SVID/XPG mallinfo
774   routine that returns a struct containing usage properties and
775   statistics. It should work on any SVID/XPG compliant system that has
776   a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
777   install such a thing yourself, cut out the preliminary declarations
778   as described above and below and save them in a malloc.h file. But
779   there's no compelling reason to bother to do this.)
780
781   The main declaration needed is the mallinfo struct that is returned
782   (by-copy) by mallinfo().  The SVID/XPG malloinfo struct contains a
783   bunch of fields that are not even meaningful in this version of
784   malloc.  These fields are are instead filled by mallinfo() with
785   other numbers that might be of interest.
786
787   HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
788   /usr/include/malloc.h file that includes a declaration of struct
789   mallinfo.  If so, it is included; else an SVID2/XPG2 compliant
790   version is declared below.  These must be precisely the same for
791   mallinfo() to work.  The original SVID version of this struct,
792   defined on most systems with mallinfo, declares all fields as
793   ints. But some others define as unsigned long. If your system
794   defines the fields using a type of different width than listed here,
795   you must #include your system version and #define
796   HAVE_USR_INCLUDE_MALLOC_H.
797 */
798
799 /* #define HAVE_USR_INCLUDE_MALLOC_H */
800
801 #ifdef HAVE_USR_INCLUDE_MALLOC_H
802 #include "/usr/include/malloc.h"
803 #endif
804
805
806 /* ---------- description of public routines ------------ */
807
808 /*
809   malloc(size_t n)
810   Returns a pointer to a newly allocated chunk of at least n bytes, or null
811   if no space is available. Additionally, on failure, errno is
812   set to ENOMEM on ANSI C systems.
813
814   If n is zero, malloc returns a minumum-sized chunk. (The minimum
815   size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
816   systems.)  On most systems, size_t is an unsigned type, so calls
817   with negative arguments are interpreted as requests for huge amounts
818   of space, which will often fail. The maximum supported value of n
819   differs across systems, but is in all cases less than the maximum
820   representable value of a size_t.
821 */
822 #if __STD_C
823 Void_t*  public_mALLOc(size_t);
824 #else
825 Void_t*  public_mALLOc();
826 #endif
827
828 /*
829   free(Void_t* p)
830   Releases the chunk of memory pointed to by p, that had been previously
831   allocated using malloc or a related routine such as realloc.
832   It has no effect if p is null. It can have arbitrary (i.e., bad!)
833   effects if p has already been freed.
834
835   Unless disabled (using mallopt), freeing very large spaces will
836   when possible, automatically trigger operations that give
837   back unused memory to the system, thus reducing program footprint.
838 */
839 #if __STD_C
840 void     public_fREe(Void_t*);
841 #else
842 void     public_fREe();
843 #endif
844
845 /*
846   calloc(size_t n_elements, size_t element_size);
847   Returns a pointer to n_elements * element_size bytes, with all locations
848   set to zero.
849 */
850 #if __STD_C
851 Void_t*  public_cALLOc(size_t, size_t);
852 #else
853 Void_t*  public_cALLOc();
854 #endif
855
856 /*
857   realloc(Void_t* p, size_t n)
858   Returns a pointer to a chunk of size n that contains the same data
859   as does chunk p up to the minimum of (n, p's size) bytes, or null
860   if no space is available.
861
862   The returned pointer may or may not be the same as p. The algorithm
863   prefers extending p when possible, otherwise it employs the
864   equivalent of a malloc-copy-free sequence.
865
866   If p is null, realloc is equivalent to malloc.
867
868   If space is not available, realloc returns null, errno is set (if on
869   ANSI) and p is NOT freed.
870
871   if n is for fewer bytes than already held by p, the newly unused
872   space is lopped off and freed if possible.  Unless the #define
873   REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
874   zero (re)allocates a minimum-sized chunk.
875
876   Large chunks that were internally obtained via mmap will always
877   be reallocated using malloc-copy-free sequences unless
878   the system supports MREMAP (currently only linux).
879
880   The old unix realloc convention of allowing the last-free'd chunk
881   to be used as an argument to realloc is not supported.
882 */
883 #if __STD_C
884 Void_t*  public_rEALLOc(Void_t*, size_t);
885 #else
886 Void_t*  public_rEALLOc();
887 #endif
888
889 /*
890   memalign(size_t alignment, size_t n);
891   Returns a pointer to a newly allocated chunk of n bytes, aligned
892   in accord with the alignment argument.
893
894   The alignment argument should be a power of two. If the argument is
895   not a power of two, the nearest greater power is used.
896   8-byte alignment is guaranteed by normal malloc calls, so don't
897   bother calling memalign with an argument of 8 or less.
898
899   Overreliance on memalign is a sure way to fragment space.
900 */
901 #if __STD_C
902 Void_t*  public_mEMALIGn(size_t, size_t);
903 #else
904 Void_t*  public_mEMALIGn();
905 #endif
906
907 /*
908   valloc(size_t n);
909   Equivalent to memalign(pagesize, n), where pagesize is the page
910   size of the system. If the pagesize is unknown, 4096 is used.
911 */
912 #if __STD_C
913 Void_t*  public_vALLOc(size_t);
914 #else
915 Void_t*  public_vALLOc();
916 #endif
917
918
919
920 /*
921   mallopt(int parameter_number, int parameter_value)
922   Sets tunable parameters The format is to provide a
923   (parameter-number, parameter-value) pair.  mallopt then sets the
924   corresponding parameter to the argument value if it can (i.e., so
925   long as the value is meaningful), and returns 1 if successful else
926   0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,
927   normally defined in malloc.h.  Only one of these (M_MXFAST) is used
928   in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
929   so setting them has no effect. But this malloc also supports four
930   other options in mallopt. See below for details.  Briefly, supported
931   parameters are as follows (listed defaults are for "typical"
932   configurations).
933
934   Symbol            param #   default    allowed param values
935   M_MXFAST          1         64         0-80  (0 disables fastbins)
936   M_TRIM_THRESHOLD -1         128*1024   any   (-1U disables trimming)
937   M_TOP_PAD        -2         0          any
938   M_MMAP_THRESHOLD -3         128*1024   any   (or 0 if no MMAP support)
939   M_MMAP_MAX       -4         65536      any   (0 disables use of mmap)
940 */
941 #if __STD_C
942 int      public_mALLOPt(int, int);
943 #else
944 int      public_mALLOPt();
945 #endif
946
947
948 /*
949   mallinfo()
950   Returns (by copy) a struct containing various summary statistics:
951
952   arena:     current total non-mmapped bytes allocated from system
953   ordblks:   the number of free chunks
954   smblks:    the number of fastbin blocks (i.e., small chunks that
955                have been freed but not use resused or consolidated)
956   hblks:     current number of mmapped regions
957   hblkhd:    total bytes held in mmapped regions
958   usmblks:   the maximum total allocated space. This will be greater
959                 than current total if trimming has occurred.
960   fsmblks:   total bytes held in fastbin blocks
961   uordblks:  current total allocated space (normal or mmapped)
962   fordblks:  total free space
963   keepcost:  the maximum number of bytes that could ideally be released
964                back to system via malloc_trim. ("ideally" means that
965                it ignores page restrictions etc.)
966
967   Because these fields are ints, but internal bookkeeping may
968   be kept as longs, the reported values may wrap around zero and
969   thus be inaccurate.
970 */
971 #if __STD_C
972 struct mallinfo public_mALLINFo(void);
973 #else
974 struct mallinfo public_mALLINFo();
975 #endif
976
977 /*
978   independent_calloc(size_t n_elements, size_t element_size, Void_t* chunks[]);
979
980   independent_calloc is similar to calloc, but instead of returning a
981   single cleared space, it returns an array of pointers to n_elements
982   independent elements that can hold contents of size elem_size, each
983   of which starts out cleared, and can be independently freed,
984   realloc'ed etc. The elements are guaranteed to be adjacently
985   allocated (this is not guaranteed to occur with multiple callocs or
986   mallocs), which may also improve cache locality in some
987   applications.
988
989   The "chunks" argument is optional (i.e., may be null, which is
990   probably the most typical usage). If it is null, the returned array
991   is itself dynamically allocated and should also be freed when it is
992   no longer needed. Otherwise, the chunks array must be of at least
993   n_elements in length. It is filled in with the pointers to the
994   chunks.
995
996   In either case, independent_calloc returns this pointer array, or
997   null if the allocation failed.  If n_elements is zero and "chunks"
998   is null, it returns a chunk representing an array with zero elements
999   (which should be freed if not wanted).
1000
1001   Each element must be individually freed when it is no longer
1002   needed. If you'd like to instead be able to free all at once, you
1003   should instead use regular calloc and assign pointers into this
1004   space to represent elements.  (In this case though, you cannot
1005   independently free elements.)
1006
1007   independent_calloc simplifies and speeds up implementations of many
1008   kinds of pools.  It may also be useful when constructing large data
1009   structures that initially have a fixed number of fixed-sized nodes,
1010   but the number is not known at compile time, and some of the nodes
1011   may later need to be freed. For example:
1012
1013   struct Node { int item; struct Node* next; };
1014
1015   struct Node* build_list() {
1016     struct Node** pool;
1017     int n = read_number_of_nodes_needed();
1018     if (n <= 0) return 0;
1019     pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
1020     if (pool == 0) die();
1021     // organize into a linked list...
1022     struct Node* first = pool[0];
1023     for (i = 0; i < n-1; ++i)
1024       pool[i]->next = pool[i+1];
1025     free(pool);     // Can now free the array (or not, if it is needed later)
1026     return first;
1027   }
1028 */
1029 #if __STD_C
1030 Void_t** public_iCALLOc(size_t, size_t, Void_t**);
1031 #else
1032 Void_t** public_iCALLOc();
1033 #endif
1034
1035 /*
1036   independent_comalloc(size_t n_elements, size_t sizes[], Void_t* chunks[]);
1037
1038   independent_comalloc allocates, all at once, a set of n_elements
1039   chunks with sizes indicated in the "sizes" array.    It returns
1040   an array of pointers to these elements, each of which can be
1041   independently freed, realloc'ed etc. The elements are guaranteed to
1042   be adjacently allocated (this is not guaranteed to occur with
1043   multiple callocs or mallocs), which may also improve cache locality
1044   in some applications.
1045
1046   The "chunks" argument is optional (i.e., may be null). If it is null
1047   the returned array is itself dynamically allocated and should also
1048   be freed when it is no longer needed. Otherwise, the chunks array
1049   must be of at least n_elements in length. It is filled in with the
1050   pointers to the chunks.
1051
1052   In either case, independent_comalloc returns this pointer array, or
1053   null if the allocation failed.  If n_elements is zero and chunks is
1054   null, it returns a chunk representing an array with zero elements
1055   (which should be freed if not wanted).
1056
1057   Each element must be individually freed when it is no longer
1058   needed. If you'd like to instead be able to free all at once, you
1059   should instead use a single regular malloc, and assign pointers at
1060   particular offsets in the aggregate space. (In this case though, you
1061   cannot independently free elements.)
1062
1063   independent_comallac differs from independent_calloc in that each
1064   element may have a different size, and also that it does not
1065   automatically clear elements.
1066
1067   independent_comalloc can be used to speed up allocation in cases
1068   where several structs or objects must always be allocated at the
1069   same time.  For example:
1070
1071   struct Head { ... }
1072   struct Foot { ... }
1073
1074   void send_message(char* msg) {
1075     int msglen = strlen(msg);
1076     size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
1077     void* chunks[3];
1078     if (independent_comalloc(3, sizes, chunks) == 0)
1079       die();
1080     struct Head* head = (struct Head*)(chunks[0]);
1081     char*        body = (char*)(chunks[1]);
1082     struct Foot* foot = (struct Foot*)(chunks[2]);
1083     // ...
1084   }
1085
1086   In general though, independent_comalloc is worth using only for
1087   larger values of n_elements. For small values, you probably won't
1088   detect enough difference from series of malloc calls to bother.
1089
1090   Overuse of independent_comalloc can increase overall memory usage,
1091   since it cannot reuse existing noncontiguous small chunks that
1092   might be available for some of the elements.
1093 */
1094 #if __STD_C
1095 Void_t** public_iCOMALLOc(size_t, size_t*, Void_t**);
1096 #else
1097 Void_t** public_iCOMALLOc();
1098 #endif
1099
1100
1101 /*
1102   pvalloc(size_t n);
1103   Equivalent to valloc(minimum-page-that-holds(n)), that is,
1104   round up n to nearest pagesize.
1105  */
1106 #if __STD_C
1107 Void_t*  public_pVALLOc(size_t);
1108 #else
1109 Void_t*  public_pVALLOc();
1110 #endif
1111
1112 /*
1113   cfree(Void_t* p);
1114   Equivalent to free(p).
1115
1116   cfree is needed/defined on some systems that pair it with calloc,
1117   for odd historical reasons (such as: cfree is used in example
1118   code in the first edition of K&R).
1119 */
1120 #if __STD_C
1121 void     public_cFREe(Void_t*);
1122 #else
1123 void     public_cFREe();
1124 #endif
1125
1126 /*
1127   malloc_trim(size_t pad);
1128
1129   If possible, gives memory back to the system (via negative
1130   arguments to sbrk) if there is unused memory at the `high' end of
1131   the malloc pool. You can call this after freeing large blocks of
1132   memory to potentially reduce the system-level memory requirements
1133   of a program. However, it cannot guarantee to reduce memory. Under
1134   some allocation patterns, some large free blocks of memory will be
1135   locked between two used chunks, so they cannot be given back to
1136   the system.
1137
1138   The `pad' argument to malloc_trim represents the amount of free
1139   trailing space to leave untrimmed. If this argument is zero,
1140   only the minimum amount of memory to maintain internal data
1141   structures will be left (one page or less). Non-zero arguments
1142   can be supplied to maintain enough trailing space to service
1143   future expected allocations without having to re-obtain memory
1144   from the system.
1145
1146   Malloc_trim returns 1 if it actually released any memory, else 0.
1147   On systems that do not support "negative sbrks", it will always
1148   rreturn 0.
1149 */
1150 #if __STD_C
1151 int      public_mTRIm(size_t);
1152 #else
1153 int      public_mTRIm();
1154 #endif
1155
1156 /*
1157   malloc_usable_size(Void_t* p);
1158
1159   Returns the number of bytes you can actually use in
1160   an allocated chunk, which may be more than you requested (although
1161   often not) due to alignment and minimum size constraints.
1162   You can use this many bytes without worrying about
1163   overwriting other allocated objects. This is not a particularly great
1164   programming practice. malloc_usable_size can be more useful in
1165   debugging and assertions, for example:
1166
1167   p = malloc(n);
1168   assert(malloc_usable_size(p) >= 256);
1169
1170 */
1171 #if __STD_C
1172 size_t   public_mUSABLe(Void_t*);
1173 #else
1174 size_t   public_mUSABLe();
1175 #endif
1176
1177 /*
1178   malloc_stats();
1179   Prints on stderr the amount of space obtained from the system (both
1180   via sbrk and mmap), the maximum amount (which may be more than
1181   current if malloc_trim and/or munmap got called), and the current
1182   number of bytes allocated via malloc (or realloc, etc) but not yet
1183   freed. Note that this is the number of bytes allocated, not the
1184   number requested. It will be larger than the number requested
1185   because of alignment and bookkeeping overhead. Because it includes
1186   alignment wastage as being in use, this figure may be greater than
1187   zero even when no user-level chunks are allocated.
1188
1189   The reported current and maximum system memory can be inaccurate if
1190   a program makes other calls to system memory allocation functions
1191   (normally sbrk) outside of malloc.
1192
1193   malloc_stats prints only the most commonly interesting statistics.
1194   More information can be obtained by calling mallinfo.
1195
1196 */
1197 #if __STD_C
1198 void     public_mSTATs(void);
1199 #else
1200 void     public_mSTATs();
1201 #endif
1202
1203 /*
1204   malloc_get_state(void);
1205
1206   Returns the state of all malloc variables in an opaque data
1207   structure.
1208 */
1209 #if __STD_C
1210 Void_t*  public_gET_STATe(void);
1211 #else
1212 Void_t*  public_gET_STATe();
1213 #endif
1214
1215 /*
1216   malloc_set_state(Void_t* state);
1217
1218   Restore the state of all malloc variables from data obtained with
1219   malloc_get_state().
1220 */
1221 #if __STD_C
1222 int      public_sET_STATe(Void_t*);
1223 #else
1224 int      public_sET_STATe();
1225 #endif
1226
1227 #ifdef _LIBC
1228 /*
1229   posix_memalign(void **memptr, size_t alignment, size_t size);
1230
1231   POSIX wrapper like memalign(), checking for validity of size.
1232 */
1233 int      __posix_memalign(void **, size_t, size_t);
1234 #endif
1235
1236 /* mallopt tuning options */
1237
1238 /*
1239   M_MXFAST is the maximum request size used for "fastbins", special bins
1240   that hold returned chunks without consolidating their spaces. This
1241   enables future requests for chunks of the same size to be handled
1242   very quickly, but can increase fragmentation, and thus increase the
1243   overall memory footprint of a program.
1244
1245   This malloc manages fastbins very conservatively yet still
1246   efficiently, so fragmentation is rarely a problem for values less
1247   than or equal to the default.  The maximum supported value of MXFAST
1248   is 80. You wouldn't want it any higher than this anyway.  Fastbins
1249   are designed especially for use with many small structs, objects or
1250   strings -- the default handles structs/objects/arrays with sizes up
1251   to 8 4byte fields, or small strings representing words, tokens,
1252   etc. Using fastbins for larger objects normally worsens
1253   fragmentation without improving speed.
1254
1255   M_MXFAST is set in REQUEST size units. It is internally used in
1256   chunksize units, which adds padding and alignment.  You can reduce
1257   M_MXFAST to 0 to disable all use of fastbins.  This causes the malloc
1258   algorithm to be a closer approximation of fifo-best-fit in all cases,
1259   not just for larger requests, but will generally cause it to be
1260   slower.
1261 */
1262
1263
1264 /* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
1265 #ifndef M_MXFAST
1266 #define M_MXFAST            1
1267 #endif
1268
1269 #ifndef DEFAULT_MXFAST
1270 #define DEFAULT_MXFAST     64
1271 #endif
1272
1273
1274 /*
1275   M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
1276   to keep before releasing via malloc_trim in free().
1277
1278   Automatic trimming is mainly useful in long-lived programs.
1279   Because trimming via sbrk can be slow on some systems, and can
1280   sometimes be wasteful (in cases where programs immediately
1281   afterward allocate more large chunks) the value should be high
1282   enough so that your overall system performance would improve by
1283   releasing this much memory.
1284
1285   The trim threshold and the mmap control parameters (see below)
1286   can be traded off with one another. Trimming and mmapping are
1287   two different ways of releasing unused memory back to the
1288   system. Between these two, it is often possible to keep
1289   system-level demands of a long-lived program down to a bare
1290   minimum. For example, in one test suite of sessions measuring
1291   the XF86 X server on Linux, using a trim threshold of 128K and a
1292   mmap threshold of 192K led to near-minimal long term resource
1293   consumption.
1294
1295   If you are using this malloc in a long-lived program, it should
1296   pay to experiment with these values.  As a rough guide, you
1297   might set to a value close to the average size of a process
1298   (program) running on your system.  Releasing this much memory
1299   would allow such a process to run in memory.  Generally, it's
1300   worth it to tune for trimming rather tham memory mapping when a
1301   program undergoes phases where several large chunks are
1302   allocated and released in ways that can reuse each other's
1303   storage, perhaps mixed with phases where there are no such
1304   chunks at all.  And in well-behaved long-lived programs,
1305   controlling release of large blocks via trimming versus mapping
1306   is usually faster.
1307
1308   However, in most programs, these parameters serve mainly as
1309   protection against the system-level effects of carrying around
1310   massive amounts of unneeded memory. Since frequent calls to
1311   sbrk, mmap, and munmap otherwise degrade performance, the default
1312   parameters are set to relatively high values that serve only as
1313   safeguards.
1314
1315   The trim value It must be greater than page size to have any useful
1316   effect.  To disable trimming completely, you can set to
1317   (unsigned long)(-1)
1318
1319   Trim settings interact with fastbin (MXFAST) settings: Unless
1320   TRIM_FASTBINS is defined, automatic trimming never takes place upon
1321   freeing a chunk with size less than or equal to MXFAST. Trimming is
1322   instead delayed until subsequent freeing of larger chunks. However,
1323   you can still force an attempted trim by calling malloc_trim.
1324
1325   Also, trimming is not generally possible in cases where
1326   the main arena is obtained via mmap.
1327
1328   Note that the trick some people use of mallocing a huge space and
1329   then freeing it at program startup, in an attempt to reserve system
1330   memory, doesn't have the intended effect under automatic trimming,
1331   since that memory will immediately be returned to the system.
1332 */
1333
1334 #define M_TRIM_THRESHOLD       -1
1335
1336 #ifndef DEFAULT_TRIM_THRESHOLD
1337 #define DEFAULT_TRIM_THRESHOLD (128 * 1024)
1338 #endif
1339
1340 /*
1341   M_TOP_PAD is the amount of extra `padding' space to allocate or
1342   retain whenever sbrk is called. It is used in two ways internally:
1343
1344   * When sbrk is called to extend the top of the arena to satisfy
1345   a new malloc request, this much padding is added to the sbrk
1346   request.
1347
1348   * When malloc_trim is called automatically from free(),
1349   it is used as the `pad' argument.
1350
1351   In both cases, the actual amount of padding is rounded
1352   so that the end of the arena is always a system page boundary.
1353
1354   The main reason for using padding is to avoid calling sbrk so
1355   often. Having even a small pad greatly reduces the likelihood
1356   that nearly every malloc request during program start-up (or
1357   after trimming) will invoke sbrk, which needlessly wastes
1358   time.
1359
1360   Automatic rounding-up to page-size units is normally sufficient
1361   to avoid measurable overhead, so the default is 0.  However, in
1362   systems where sbrk is relatively slow, it can pay to increase
1363   this value, at the expense of carrying around more memory than
1364   the program needs.
1365 */
1366
1367 #define M_TOP_PAD              -2
1368
1369 #ifndef DEFAULT_TOP_PAD
1370 #define DEFAULT_TOP_PAD        (0)
1371 #endif
1372
1373 /*
1374   M_MMAP_THRESHOLD is the request size threshold for using mmap()
1375   to service a request. Requests of at least this size that cannot
1376   be allocated using already-existing space will be serviced via mmap.
1377   (If enough normal freed space already exists it is used instead.)
1378
1379   Using mmap segregates relatively large chunks of memory so that
1380   they can be individually obtained and released from the host
1381   system. A request serviced through mmap is never reused by any
1382   other request (at least not directly; the system may just so
1383   happen to remap successive requests to the same locations).
1384
1385   Segregating space in this way has the benefits that:
1386
1387    1. Mmapped space can ALWAYS be individually released back
1388       to the system, which helps keep the system level memory
1389       demands of a long-lived program low.
1390    2. Mapped memory can never become `locked' between
1391       other chunks, as can happen with normally allocated chunks, which
1392       means that even trimming via malloc_trim would not release them.
1393    3. On some systems with "holes" in address spaces, mmap can obtain
1394       memory that sbrk cannot.
1395
1396   However, it has the disadvantages that:
1397
1398    1. The space cannot be reclaimed, consolidated, and then
1399       used to service later requests, as happens with normal chunks.
1400    2. It can lead to more wastage because of mmap page alignment
1401       requirements
1402    3. It causes malloc performance to be more dependent on host
1403       system memory management support routines which may vary in
1404       implementation quality and may impose arbitrary
1405       limitations. Generally, servicing a request via normal
1406       malloc steps is faster than going through a system's mmap.
1407
1408   The advantages of mmap nearly always outweigh disadvantages for
1409   "large" chunks, but the value of "large" varies across systems.  The
1410   default is an empirically derived value that works well in most
1411   systems.
1412 */
1413
1414 #define M_MMAP_THRESHOLD      -3
1415
1416 #ifndef DEFAULT_MMAP_THRESHOLD
1417 #define DEFAULT_MMAP_THRESHOLD (128 * 1024)
1418 #endif
1419
1420 /*
1421   M_MMAP_MAX is the maximum number of requests to simultaneously
1422   service using mmap. This parameter exists because
1423   some systems have a limited number of internal tables for
1424   use by mmap, and using more than a few of them may degrade
1425   performance.
1426
1427   The default is set to a value that serves only as a safeguard.
1428   Setting to 0 disables use of mmap for servicing large requests.  If
1429   HAVE_MMAP is not set, the default value is 0, and attempts to set it
1430   to non-zero values in mallopt will fail.
1431 */
1432
1433 #define M_MMAP_MAX             -4
1434
1435 #ifndef DEFAULT_MMAP_MAX
1436 #if HAVE_MMAP
1437 #define DEFAULT_MMAP_MAX       (65536)
1438 #else
1439 #define DEFAULT_MMAP_MAX       (0)
1440 #endif
1441 #endif
1442
1443 #ifdef __cplusplus
1444 };  /* end of extern "C" */
1445 #endif
1446
1447 #include <malloc.h>
1448 #include "thread-m.h"
1449
1450 #ifndef BOUNDED_N
1451 #define BOUNDED_N(ptr, sz) (ptr)
1452 #endif
1453 #ifndef RETURN_ADDRESS
1454 #define RETURN_ADDRESS(X_) (NULL)
1455 #endif
1456
1457 /* On some platforms we can compile internal, not exported functions better.
1458    Let the environment provide a macro and define it to be empty if it
1459    is not available.  */
1460 #ifndef internal_function
1461 # define internal_function
1462 #endif
1463
1464 /* Forward declarations.  */
1465 struct malloc_chunk;
1466 typedef struct malloc_chunk* mchunkptr;
1467
1468 /* Internal routines.  */
1469
1470 #if __STD_C
1471
1472 static Void_t*  _int_malloc(mstate, size_t);
1473 static void     _int_free(mstate, Void_t*);
1474 static Void_t*  _int_realloc(mstate, Void_t*, size_t);
1475 static Void_t*  _int_memalign(mstate, size_t, size_t);
1476 static Void_t*  _int_valloc(mstate, size_t);
1477 static Void_t*  _int_pvalloc(mstate, size_t);
1478 /*static Void_t*  cALLOc(size_t, size_t);*/
1479 static Void_t** _int_icalloc(mstate, size_t, size_t, Void_t**);
1480 static Void_t** _int_icomalloc(mstate, size_t, size_t*, Void_t**);
1481 static int      mTRIm(size_t);
1482 static size_t   mUSABLe(Void_t*);
1483 static void     mSTATs(void);
1484 static int      mALLOPt(int, int);
1485 static struct mallinfo mALLINFo(mstate);
1486
1487 static Void_t* internal_function mem2mem_check(Void_t *p, size_t sz);
1488 static int internal_function top_check(void);
1489 static void internal_function munmap_chunk(mchunkptr p);
1490 #if HAVE_MREMAP
1491 static mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size);
1492 #endif
1493
1494 static Void_t*   malloc_check(size_t sz, const Void_t *caller);
1495 static void      free_check(Void_t* mem, const Void_t *caller);
1496 static Void_t*   realloc_check(Void_t* oldmem, size_t bytes,
1497                                const Void_t *caller);
1498 static Void_t*   memalign_check(size_t alignment, size_t bytes,
1499                                 const Void_t *caller);
1500 #ifndef NO_THREADS
1501 # ifdef _LIBC
1502 #  if USE___THREAD || (defined USE_TLS && !defined SHARED)
1503     /* These routines are never needed in this configuration.  */
1504 #   define NO_STARTER
1505 #  endif
1506 # endif
1507 # ifdef NO_STARTER
1508 #  undef NO_STARTER
1509 # else
1510 static Void_t*   malloc_starter(size_t sz, const Void_t *caller);
1511 static Void_t*   memalign_starter(size_t aln, size_t sz, const Void_t *caller);
1512 static void      free_starter(Void_t* mem, const Void_t *caller);
1513 # endif
1514 static Void_t*   malloc_atfork(size_t sz, const Void_t *caller);
1515 static void      free_atfork(Void_t* mem, const Void_t *caller);
1516 #endif
1517
1518 #else
1519
1520 Void_t*         _int_malloc();
1521 void            _int_free();
1522 Void_t*         _int_realloc();
1523 Void_t*         _int_memalign();
1524 Void_t*         _int_valloc();
1525 Void_t*         _int_pvalloc();
1526 /*static Void_t*  cALLOc();*/
1527 static Void_t** _int_icalloc();
1528 static Void_t** _int_icomalloc();
1529 static int      mTRIm();
1530 static size_t   mUSABLe();
1531 static void     mSTATs();
1532 static int      mALLOPt();
1533 static struct mallinfo mALLINFo();
1534
1535 #endif
1536
1537
1538
1539
1540 /* ------------- Optional versions of memcopy ---------------- */
1541
1542
1543 #if USE_MEMCPY
1544
1545 /*
1546   Note: memcpy is ONLY invoked with non-overlapping regions,
1547   so the (usually slower) memmove is not needed.
1548 */
1549
1550 #define MALLOC_COPY(dest, src, nbytes)  memcpy(dest, src, nbytes)
1551 #define MALLOC_ZERO(dest, nbytes)       memset(dest, 0,   nbytes)
1552
1553 #else /* !USE_MEMCPY */
1554
1555 /* Use Duff's device for good zeroing/copying performance. */
1556
1557 #define MALLOC_ZERO(charp, nbytes)                                            \
1558 do {                                                                          \
1559   INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp);                           \
1560   unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T);                     \
1561   long mcn;                                                                   \
1562   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
1563   switch (mctmp) {                                                            \
1564     case 0: for(;;) { *mzp++ = 0;                                             \
1565     case 7:           *mzp++ = 0;                                             \
1566     case 6:           *mzp++ = 0;                                             \
1567     case 5:           *mzp++ = 0;                                             \
1568     case 4:           *mzp++ = 0;                                             \
1569     case 3:           *mzp++ = 0;                                             \
1570     case 2:           *mzp++ = 0;                                             \
1571     case 1:           *mzp++ = 0; if(mcn <= 0) break; mcn--; }                \
1572   }                                                                           \
1573 } while(0)
1574
1575 #define MALLOC_COPY(dest,src,nbytes)                                          \
1576 do {                                                                          \
1577   INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src;                            \
1578   INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest;                           \
1579   unsigned long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T);                     \
1580   long mcn;                                                                   \
1581   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
1582   switch (mctmp) {                                                            \
1583     case 0: for(;;) { *mcdst++ = *mcsrc++;                                    \
1584     case 7:           *mcdst++ = *mcsrc++;                                    \
1585     case 6:           *mcdst++ = *mcsrc++;                                    \
1586     case 5:           *mcdst++ = *mcsrc++;                                    \
1587     case 4:           *mcdst++ = *mcsrc++;                                    \
1588     case 3:           *mcdst++ = *mcsrc++;                                    \
1589     case 2:           *mcdst++ = *mcsrc++;                                    \
1590     case 1:           *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; }       \
1591   }                                                                           \
1592 } while(0)
1593
1594 #endif
1595
1596 /* ------------------ MMAP support ------------------  */
1597
1598
1599 #if HAVE_MMAP
1600
1601 #include <fcntl.h>
1602 #ifndef LACKS_SYS_MMAN_H
1603 #include <sys/mman.h>
1604 #endif
1605
1606 #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1607 # define MAP_ANONYMOUS MAP_ANON
1608 #endif
1609 #if !defined(MAP_FAILED)
1610 # define MAP_FAILED ((char*)-1)
1611 #endif
1612
1613 #ifndef MAP_NORESERVE
1614 # ifdef MAP_AUTORESRV
1615 #  define MAP_NORESERVE MAP_AUTORESRV
1616 # else
1617 #  define MAP_NORESERVE 0
1618 # endif
1619 #endif
1620
1621 /*
1622    Nearly all versions of mmap support MAP_ANONYMOUS,
1623    so the following is unlikely to be needed, but is
1624    supplied just in case.
1625 */
1626
1627 #ifndef MAP_ANONYMOUS
1628
1629 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1630
1631 #define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
1632  (dev_zero_fd = open("/dev/zero", O_RDWR), \
1633   mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
1634    mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))
1635
1636 #else
1637
1638 #define MMAP(addr, size, prot, flags) \
1639  (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1640
1641 #endif
1642
1643
1644 #endif /* HAVE_MMAP */
1645
1646
1647 /*
1648   -----------------------  Chunk representations -----------------------
1649 */
1650
1651
1652 /*
1653   This struct declaration is misleading (but accurate and necessary).
1654   It declares a "view" into memory allowing access to necessary
1655   fields at known offsets from a given base. See explanation below.
1656 */
1657
1658 struct malloc_chunk {
1659
1660   INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
1661   INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
1662
1663   struct malloc_chunk* fd;         /* double links -- used only if free. */
1664   struct malloc_chunk* bk;
1665 };
1666
1667
1668 /*
1669    malloc_chunk details:
1670
1671     (The following includes lightly edited explanations by Colin Plumb.)
1672
1673     Chunks of memory are maintained using a `boundary tag' method as
1674     described in e.g., Knuth or Standish.  (See the paper by Paul
1675     Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1676     survey of such techniques.)  Sizes of free chunks are stored both
1677     in the front of each chunk and at the end.  This makes
1678     consolidating fragmented chunks into bigger chunks very fast.  The
1679     size fields also hold bits representing whether chunks are free or
1680     in use.
1681
1682     An allocated chunk looks like this:
1683
1684
1685     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1686             |             Size of previous chunk, if allocated            | |
1687             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1688             |             Size of chunk, in bytes                         |P|
1689       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1690             |             User data starts here...                          .
1691             .                                                               .
1692             .             (malloc_usable_space() bytes)                     .
1693             .                                                               |
1694 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1695             |             Size of chunk                                     |
1696             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1697
1698
1699     Where "chunk" is the front of the chunk for the purpose of most of
1700     the malloc code, but "mem" is the pointer that is returned to the
1701     user.  "Nextchunk" is the beginning of the next contiguous chunk.
1702
1703     Chunks always begin on even word boundries, so the mem portion
1704     (which is returned to the user) is also on an even word boundary, and
1705     thus at least double-word aligned.
1706
1707     Free chunks are stored in circular doubly-linked lists, and look like this:
1708
1709     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1710             |             Size of previous chunk                            |
1711             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1712     `head:' |             Size of chunk, in bytes                         |P|
1713       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1714             |             Forward pointer to next chunk in list             |
1715             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1716             |             Back pointer to previous chunk in list            |
1717             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1718             |             Unused space (may be 0 bytes long)                .
1719             .                                                               .
1720             .                                                               |
1721 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1722     `foot:' |             Size of chunk, in bytes                           |
1723             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1724
1725     The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1726     chunk size (which is always a multiple of two words), is an in-use
1727     bit for the *previous* chunk.  If that bit is *clear*, then the
1728     word before the current chunk size contains the previous chunk
1729     size, and can be used to find the front of the previous chunk.
1730     The very first chunk allocated always has this bit set,
1731     preventing access to non-existent (or non-owned) memory. If
1732     prev_inuse is set for any given chunk, then you CANNOT determine
1733     the size of the previous chunk, and might even get a memory
1734     addressing fault when trying to do so.
1735
1736     Note that the `foot' of the current chunk is actually represented
1737     as the prev_size of the NEXT chunk. This makes it easier to
1738     deal with alignments etc but can be very confusing when trying
1739     to extend or adapt this code.
1740
1741     The two exceptions to all this are
1742
1743      1. The special chunk `top' doesn't bother using the
1744         trailing size field since there is no next contiguous chunk
1745         that would have to index off it. After initialization, `top'
1746         is forced to always exist.  If it would become less than
1747         MINSIZE bytes long, it is replenished.
1748
1749      2. Chunks allocated via mmap, which have the second-lowest-order
1750         bit (IS_MMAPPED) set in their size fields.  Because they are
1751         allocated one-by-one, each must contain its own trailing size field.
1752
1753 */
1754
1755 /*
1756   ---------- Size and alignment checks and conversions ----------
1757 */
1758
1759 /* conversion from malloc headers to user pointers, and back */
1760
1761 #define chunk2mem(p)   ((Void_t*)((char*)(p) + 2*SIZE_SZ))
1762 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1763
1764 /* The smallest possible chunk */
1765 #define MIN_CHUNK_SIZE        (sizeof(struct malloc_chunk))
1766
1767 /* The smallest size we can malloc is an aligned minimal chunk */
1768
1769 #define MINSIZE  \
1770   (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1771
1772 /* Check if m has acceptable alignment */
1773
1774 #define aligned_OK(m)  (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1775
1776
1777 /*
1778    Check if a request is so large that it would wrap around zero when
1779    padded and aligned. To simplify some other code, the bound is made
1780    low enough so that adding MINSIZE will also not wrap around zero.
1781 */
1782
1783 #define REQUEST_OUT_OF_RANGE(req)                                 \
1784   ((unsigned long)(req) >=                                        \
1785    (unsigned long)(INTERNAL_SIZE_T)(-2 * MINSIZE))
1786
1787 /* pad request bytes into a usable size -- internal version */
1788
1789 #define request2size(req)                                         \
1790   (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
1791    MINSIZE :                                                      \
1792    ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1793
1794 /*  Same, except also perform argument check */
1795
1796 #define checked_request2size(req, sz)                             \
1797   if (REQUEST_OUT_OF_RANGE(req)) {                                \
1798     MALLOC_FAILURE_ACTION;                                        \
1799     return 0;                                                     \
1800   }                                                               \
1801   (sz) = request2size(req);
1802
1803 /*
1804   --------------- Physical chunk operations ---------------
1805 */
1806
1807
1808 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1809 #define PREV_INUSE 0x1
1810
1811 /* extract inuse bit of previous chunk */
1812 #define prev_inuse(p)       ((p)->size & PREV_INUSE)
1813
1814
1815 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1816 #define IS_MMAPPED 0x2
1817
1818 /* check for mmap()'ed chunk */
1819 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1820
1821
1822 /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1823    from a non-main arena.  This is only set immediately before handing
1824    the chunk to the user, if necessary.  */
1825 #define NON_MAIN_ARENA 0x4
1826
1827 /* check for chunk from non-main arena */
1828 #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
1829
1830
1831 /*
1832   Bits to mask off when extracting size
1833
1834   Note: IS_MMAPPED is intentionally not masked off from size field in
1835   macros for which mmapped chunks should never be seen. This should
1836   cause helpful core dumps to occur if it is tried by accident by
1837   people extending or adapting this malloc.
1838 */
1839 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)
1840
1841 /* Get size, ignoring use bits */
1842 #define chunksize(p)         ((p)->size & ~(SIZE_BITS))
1843
1844
1845 /* Ptr to next physical malloc_chunk. */
1846 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~SIZE_BITS) ))
1847
1848 /* Ptr to previous physical malloc_chunk */
1849 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1850
1851 /* Treat space at ptr + offset as a chunk */
1852 #define chunk_at_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
1853
1854 /* extract p's inuse bit */
1855 #define inuse(p)\
1856 ((((mchunkptr)(((char*)(p))+((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1857
1858 /* set/clear chunk as being inuse without otherwise disturbing */
1859 #define set_inuse(p)\
1860 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
1861
1862 #define clear_inuse(p)\
1863 ((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
1864
1865
1866 /* check/set/clear inuse bits in known places */
1867 #define inuse_bit_at_offset(p, s)\
1868  (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
1869
1870 #define set_inuse_bit_at_offset(p, s)\
1871  (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
1872
1873 #define clear_inuse_bit_at_offset(p, s)\
1874  (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
1875
1876
1877 /* Set size at head, without disturbing its use bit */
1878 #define set_head_size(p, s)  ((p)->size = (((p)->size & SIZE_BITS) | (s)))
1879
1880 /* Set size/use field */
1881 #define set_head(p, s)       ((p)->size = (s))
1882
1883 /* Set size at footer (only when chunk is not in use) */
1884 #define set_foot(p, s)       (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
1885
1886
1887 /*
1888   -------------------- Internal data structures --------------------
1889
1890    All internal state is held in an instance of malloc_state defined
1891    below. There are no other static variables, except in two optional
1892    cases:
1893    * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1894    * If HAVE_MMAP is true, but mmap doesn't support
1895      MAP_ANONYMOUS, a dummy file descriptor for mmap.
1896
1897    Beware of lots of tricks that minimize the total bookkeeping space
1898    requirements. The result is a little over 1K bytes (for 4byte
1899    pointers and size_t.)
1900 */
1901
1902 /*
1903   Bins
1904
1905     An array of bin headers for free chunks. Each bin is doubly
1906     linked.  The bins are approximately proportionally (log) spaced.
1907     There are a lot of these bins (128). This may look excessive, but
1908     works very well in practice.  Most bins hold sizes that are
1909     unusual as malloc request sizes, but are more usual for fragments
1910     and consolidated sets of chunks, which is what these bins hold, so
1911     they can be found quickly.  All procedures maintain the invariant
1912     that no consolidated chunk physically borders another one, so each
1913     chunk in a list is known to be preceeded and followed by either
1914     inuse chunks or the ends of memory.
1915
1916     Chunks in bins are kept in size order, with ties going to the
1917     approximately least recently used chunk. Ordering isn't needed
1918     for the small bins, which all contain the same-sized chunks, but
1919     facilitates best-fit allocation for larger chunks. These lists
1920     are just sequential. Keeping them in order almost never requires
1921     enough traversal to warrant using fancier ordered data
1922     structures.
1923
1924     Chunks of the same size are linked with the most
1925     recently freed at the front, and allocations are taken from the
1926     back.  This results in LRU (FIFO) allocation order, which tends
1927     to give each chunk an equal opportunity to be consolidated with
1928     adjacent freed chunks, resulting in larger free chunks and less
1929     fragmentation.
1930
1931     To simplify use in double-linked lists, each bin header acts
1932     as a malloc_chunk. This avoids special-casing for headers.
1933     But to conserve space and improve locality, we allocate
1934     only the fd/bk pointers of bins, and then use repositioning tricks
1935     to treat these as the fields of a malloc_chunk*.
1936 */
1937
1938 typedef struct malloc_chunk* mbinptr;
1939
1940 /* addressing -- note that bin_at(0) does not exist */
1941 #define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - (SIZE_SZ<<1)))
1942
1943 /* analog of ++bin */
1944 #define next_bin(b)  ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
1945
1946 /* Reminders about list directionality within bins */
1947 #define first(b)     ((b)->fd)
1948 #define last(b)      ((b)->bk)
1949
1950 /* Take a chunk off a bin list */
1951 #define unlink(P, BK, FD) {                                            \
1952   FD = P->fd;                                                          \
1953   BK = P->bk;                                                          \
1954   FD->bk = BK;                                                         \
1955   BK->fd = FD;                                                         \
1956 }
1957
1958 /*
1959   Indexing
1960
1961     Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1962     8 bytes apart. Larger bins are approximately logarithmically spaced:
1963
1964     64 bins of size       8
1965     32 bins of size      64
1966     16 bins of size     512
1967      8 bins of size    4096
1968      4 bins of size   32768
1969      2 bins of size  262144
1970      1 bin  of size what's left
1971
1972     There is actually a little bit of slop in the numbers in bin_index
1973     for the sake of speed. This makes no difference elsewhere.
1974
1975     The bins top out around 1MB because we expect to service large
1976     requests via mmap.
1977 */
1978
1979 #define NBINS             128
1980 #define NSMALLBINS         64
1981 #define SMALLBIN_WIDTH      8
1982 #define MIN_LARGE_SIZE    512
1983
1984 #define in_smallbin_range(sz)  \
1985   ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)
1986
1987 #define smallbin_index(sz)     (((unsigned)(sz)) >> 3)
1988
1989 #define largebin_index(sz)                                                   \
1990 (((((unsigned long)(sz)) >>  6) <= 32)?  56 + (((unsigned long)(sz)) >>  6): \
1991  ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
1992  ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
1993  ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
1994  ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
1995                                         126)
1996
1997 #define bin_index(sz) \
1998  ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
1999
2000
2001 /*
2002   Unsorted chunks
2003
2004     All remainders from chunk splits, as well as all returned chunks,
2005     are first placed in the "unsorted" bin. They are then placed
2006     in regular bins after malloc gives them ONE chance to be used before
2007     binning. So, basically, the unsorted_chunks list acts as a queue,
2008     with chunks being placed on it in free (and malloc_consolidate),
2009     and taken off (to be either used or placed in bins) in malloc.
2010
2011     The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
2012     does not have to be taken into account in size comparisons.
2013 */
2014
2015 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
2016 #define unsorted_chunks(M)          (bin_at(M, 1))
2017
2018 /*
2019   Top
2020
2021     The top-most available chunk (i.e., the one bordering the end of
2022     available memory) is treated specially. It is never included in
2023     any bin, is used only if no other chunk is available, and is
2024     released back to the system if it is very large (see
2025     M_TRIM_THRESHOLD).  Because top initially
2026     points to its own bin with initial zero size, thus forcing
2027     extension on the first malloc request, we avoid having any special
2028     code in malloc to check whether it even exists yet. But we still
2029     need to do so when getting memory from system, so we make
2030     initial_top treat the bin as a legal but unusable chunk during the
2031     interval between initialization and the first call to
2032     sYSMALLOc. (This is somewhat delicate, since it relies on
2033     the 2 preceding words to be zero during this interval as well.)
2034 */
2035
2036 /* Conveniently, the unsorted bin can be used as dummy top on first call */
2037 #define initial_top(M)              (unsorted_chunks(M))
2038
2039 /*
2040   Binmap
2041
2042     To help compensate for the large number of bins, a one-level index
2043     structure is used for bin-by-bin searching.  `binmap' is a
2044     bitvector recording whether bins are definitely empty so they can
2045     be skipped over during during traversals.  The bits are NOT always
2046     cleared as soon as bins are empty, but instead only
2047     when they are noticed to be empty during traversal in malloc.
2048 */
2049
2050 /* Conservatively use 32 bits per map word, even if on 64bit system */
2051 #define BINMAPSHIFT      5
2052 #define BITSPERMAP       (1U << BINMAPSHIFT)
2053 #define BINMAPSIZE       (NBINS / BITSPERMAP)
2054
2055 #define idx2block(i)     ((i) >> BINMAPSHIFT)
2056 #define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT)-1))))
2057
2058 #define mark_bin(m,i)    ((m)->binmap[idx2block(i)] |=  idx2bit(i))
2059 #define unmark_bin(m,i)  ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
2060 #define get_binmap(m,i)  ((m)->binmap[idx2block(i)] &   idx2bit(i))
2061
2062 /*
2063   Fastbins
2064
2065     An array of lists holding recently freed small chunks.  Fastbins
2066     are not doubly linked.  It is faster to single-link them, and
2067     since chunks are never removed from the middles of these lists,
2068     double linking is not necessary. Also, unlike regular bins, they
2069     are not even processed in FIFO order (they use faster LIFO) since
2070     ordering doesn't much matter in the transient contexts in which
2071     fastbins are normally used.
2072
2073     Chunks in fastbins keep their inuse bit set, so they cannot
2074     be consolidated with other free chunks. malloc_consolidate
2075     releases all chunks in fastbins and consolidates them with
2076     other free chunks.
2077 */
2078
2079 typedef struct malloc_chunk* mfastbinptr;
2080
2081 /* offset 2 to use otherwise unindexable first 2 bins */
2082 #define fastbin_index(sz)        ((((unsigned int)(sz)) >> 3) - 2)
2083
2084 /* The maximum fastbin request size we support */
2085 #define MAX_FAST_SIZE     80
2086
2087 #define NFASTBINS  (fastbin_index(request2size(MAX_FAST_SIZE))+1)
2088
2089 /*
2090   FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
2091   that triggers automatic consolidation of possibly-surrounding
2092   fastbin chunks. This is a heuristic, so the exact value should not
2093   matter too much. It is defined at half the default trim threshold as a
2094   compromise heuristic to only attempt consolidation if it is likely
2095   to lead to trimming. However, it is not dynamically tunable, since
2096   consolidation reduces fragmentation surrounding large chunks even
2097   if trimming is not used.
2098 */
2099
2100 #define FASTBIN_CONSOLIDATION_THRESHOLD  (65536UL)
2101
2102 /*
2103   Since the lowest 2 bits in max_fast don't matter in size comparisons,
2104   they are used as flags.
2105 */
2106
2107 /*
2108   FASTCHUNKS_BIT held in max_fast indicates that there are probably
2109   some fastbin chunks. It is set true on entering a chunk into any
2110   fastbin, and cleared only in malloc_consolidate.
2111
2112   The truth value is inverted so that have_fastchunks will be true
2113   upon startup (since statics are zero-filled), simplifying
2114   initialization checks.
2115 */
2116
2117 #define FASTCHUNKS_BIT        (1U)
2118
2119 #define have_fastchunks(M)     (((M)->max_fast &  FASTCHUNKS_BIT) == 0)
2120 #define clear_fastchunks(M)    ((M)->max_fast |=  FASTCHUNKS_BIT)
2121 #define set_fastchunks(M)      ((M)->max_fast &= ~FASTCHUNKS_BIT)
2122
2123 /*
2124   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
2125   regions.  Otherwise, contiguity is exploited in merging together,
2126   when possible, results from consecutive MORECORE calls.
2127
2128   The initial value comes from MORECORE_CONTIGUOUS, but is
2129   changed dynamically if mmap is ever used as an sbrk substitute.
2130 */
2131
2132 #define NONCONTIGUOUS_BIT     (2U)
2133
2134 #define contiguous(M)          (((M)->max_fast &  NONCONTIGUOUS_BIT) == 0)
2135 #define noncontiguous(M)       (((M)->max_fast &  NONCONTIGUOUS_BIT) != 0)
2136 #define set_noncontiguous(M)   ((M)->max_fast |=  NONCONTIGUOUS_BIT)
2137 #define set_contiguous(M)      ((M)->max_fast &= ~NONCONTIGUOUS_BIT)
2138
2139 /*
2140    Set value of max_fast.
2141    Use impossibly small value if 0.
2142    Precondition: there are no existing fastbin chunks.
2143    Setting the value clears fastchunk bit but preserves noncontiguous bit.
2144 */
2145
2146 #define set_max_fast(M, s) \
2147   (M)->max_fast = (((s) == 0)? SMALLBIN_WIDTH: request2size(s)) | \
2148   FASTCHUNKS_BIT | \
2149   ((M)->max_fast &  NONCONTIGUOUS_BIT)
2150
2151
2152 /*
2153    ----------- Internal state representation and initialization -----------
2154 */
2155
2156 struct malloc_state {
2157   /* Serialize access.  */
2158   mutex_t mutex;
2159
2160   /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
2161   long stat_lock_direct, stat_lock_loop, stat_lock_wait;
2162   long pad0_[1]; /* try to give the mutex its own cacheline */
2163
2164   /* The maximum chunk size to be eligible for fastbin */
2165   INTERNAL_SIZE_T  max_fast;   /* low 2 bits used as flags */
2166
2167   /* Fastbins */
2168   mfastbinptr      fastbins[NFASTBINS];
2169
2170   /* Base of the topmost chunk -- not otherwise kept in a bin */
2171   mchunkptr        top;
2172
2173   /* The remainder from the most recent split of a small request */
2174   mchunkptr        last_remainder;
2175
2176   /* Normal bins packed as described above */
2177   mchunkptr        bins[NBINS * 2];
2178
2179   /* Bitmap of bins */
2180   unsigned int     binmap[BINMAPSIZE];
2181
2182   /* Linked list */
2183   struct malloc_state *next;
2184
2185   /* Memory allocated from the system in this arena.  */
2186   INTERNAL_SIZE_T system_mem;
2187   INTERNAL_SIZE_T max_system_mem;
2188 };
2189
2190 struct malloc_par {
2191   /* Tunable parameters */
2192   unsigned long    trim_threshold;
2193   INTERNAL_SIZE_T  top_pad;
2194   INTERNAL_SIZE_T  mmap_threshold;
2195
2196   /* Memory map support */
2197   int              n_mmaps;
2198   int              n_mmaps_max;
2199   int              max_n_mmaps;
2200
2201   /* Cache malloc_getpagesize */
2202   unsigned int     pagesize;
2203
2204   /* Statistics */
2205   INTERNAL_SIZE_T  mmapped_mem;
2206   /*INTERNAL_SIZE_T  sbrked_mem;*/
2207   /*INTERNAL_SIZE_T  max_sbrked_mem;*/
2208   INTERNAL_SIZE_T  max_mmapped_mem;
2209   INTERNAL_SIZE_T  max_total_mem; /* only kept for NO_THREADS */
2210
2211   /* First address handed out by MORECORE/sbrk.  */
2212   char*            sbrk_base;
2213 };
2214
2215 /* There are several instances of this struct ("arenas") in this
2216    malloc.  If you are adapting this malloc in a way that does NOT use
2217    a static or mmapped malloc_state, you MUST explicitly zero-fill it
2218    before using. This malloc relies on the property that malloc_state
2219    is initialized to all zeroes (as is true of C statics).  */
2220
2221 static struct malloc_state main_arena;
2222
2223 /* There is only one instance of the malloc parameters.  */
2224
2225 static struct malloc_par mp_;
2226
2227 /*
2228   Initialize a malloc_state struct.
2229
2230   This is called only from within malloc_consolidate, which needs
2231   be called in the same contexts anyway.  It is never called directly
2232   outside of malloc_consolidate because some optimizing compilers try
2233   to inline it at all call points, which turns out not to be an
2234   optimization at all. (Inlining it in malloc_consolidate is fine though.)
2235 */
2236
2237 #if __STD_C
2238 static void malloc_init_state(mstate av)
2239 #else
2240 static void malloc_init_state(av) mstate av;
2241 #endif
2242 {
2243   int     i;
2244   mbinptr bin;
2245
2246   /* Establish circular links for normal bins */
2247   for (i = 1; i < NBINS; ++i) {
2248     bin = bin_at(av,i);
2249     bin->fd = bin->bk = bin;
2250   }
2251
2252 #if MORECORE_CONTIGUOUS
2253   if (av != &main_arena)
2254 #endif
2255     set_noncontiguous(av);
2256
2257   set_max_fast(av, DEFAULT_MXFAST);
2258
2259   av->top            = initial_top(av);
2260 }
2261
2262 /*
2263    Other internal utilities operating on mstates
2264 */
2265
2266 #if __STD_C
2267 static Void_t*  sYSMALLOc(INTERNAL_SIZE_T, mstate);
2268 static int      sYSTRIm(size_t, mstate);
2269 static void     malloc_consolidate(mstate);
2270 static Void_t** iALLOc(mstate, size_t, size_t*, int, Void_t**);
2271 #else
2272 static Void_t*  sYSMALLOc();
2273 static int      sYSTRIm();
2274 static void     malloc_consolidate();
2275 static Void_t** iALLOc();
2276 #endif
2277
2278
2279 /* -------------- Early definitions for debugging hooks ---------------- */
2280
2281 /* Define and initialize the hook variables.  These weak definitions must
2282    appear before any use of the variables in a function (arena.c uses one).  */
2283 #ifndef weak_variable
2284 #ifndef _LIBC
2285 #define weak_variable /**/
2286 #else
2287 /* In GNU libc we want the hook variables to be weak definitions to
2288    avoid a problem with Emacs.  */
2289 #define weak_variable weak_function
2290 #endif
2291 #endif
2292
2293 /* Forward declarations.  */
2294 static Void_t* malloc_hook_ini __MALLOC_P ((size_t sz,
2295                                             const __malloc_ptr_t caller));
2296 static Void_t* realloc_hook_ini __MALLOC_P ((Void_t* ptr, size_t sz,
2297                                              const __malloc_ptr_t caller));
2298 static Void_t* memalign_hook_ini __MALLOC_P ((size_t alignment, size_t sz,
2299                                               const __malloc_ptr_t caller));
2300
2301 void weak_variable (*__malloc_initialize_hook) __MALLOC_P ((void)) = NULL;
2302 void weak_variable (*__free_hook) __MALLOC_P ((__malloc_ptr_t __ptr,
2303                                                const __malloc_ptr_t)) = NULL;
2304 __malloc_ptr_t weak_variable (*__malloc_hook)
2305  __MALLOC_P ((size_t __size, const __malloc_ptr_t)) = malloc_hook_ini;
2306 __malloc_ptr_t weak_variable (*__realloc_hook)
2307  __MALLOC_P ((__malloc_ptr_t __ptr, size_t __size, const __malloc_ptr_t))
2308      = realloc_hook_ini;
2309 __malloc_ptr_t weak_variable (*__memalign_hook)
2310  __MALLOC_P ((size_t __alignment, size_t __size, const __malloc_ptr_t))
2311      = memalign_hook_ini;
2312 void weak_variable (*__after_morecore_hook) __MALLOC_P ((void)) = NULL;
2313
2314
2315 /* ------------------- Support for multiple arenas -------------------- */
2316 #include "arena.c"
2317
2318 /*
2319   Debugging support
2320
2321   These routines make a number of assertions about the states
2322   of data structures that should be true at all times. If any
2323   are not true, it's very likely that a user program has somehow
2324   trashed memory. (It's also possible that there is a coding error
2325   in malloc. In which case, please report it!)
2326 */
2327
2328 #if ! MALLOC_DEBUG
2329
2330 #define check_chunk(A,P)
2331 #define check_free_chunk(A,P)
2332 #define check_inuse_chunk(A,P)
2333 #define check_remalloced_chunk(A,P,N)
2334 #define check_malloced_chunk(A,P,N)
2335 #define check_malloc_state(A)
2336
2337 #else
2338
2339 #define check_chunk(A,P)              do_check_chunk(A,P)
2340 #define check_free_chunk(A,P)         do_check_free_chunk(A,P)
2341 #define check_inuse_chunk(A,P)        do_check_inuse_chunk(A,P)
2342 #define check_remalloced_chunk(A,P,N) do_check_remalloced_chunk(A,P,N)
2343 #define check_malloced_chunk(A,P,N)   do_check_malloced_chunk(A,P,N)
2344 #define check_malloc_state(A)         do_check_malloc_state(A)
2345
2346 /*
2347   Properties of all chunks
2348 */
2349
2350 #if __STD_C
2351 static void do_check_chunk(mstate av, mchunkptr p)
2352 #else
2353 static void do_check_chunk(av, p) mstate av; mchunkptr p;
2354 #endif
2355 {
2356   unsigned long sz = chunksize(p);
2357   /* min and max possible addresses assuming contiguous allocation */
2358   char* max_address = (char*)(av->top) + chunksize(av->top);
2359   char* min_address = max_address - av->system_mem;
2360
2361   if (!chunk_is_mmapped(p)) {
2362
2363     /* Has legal address ... */
2364     if (p != av->top) {
2365       if (contiguous(av)) {
2366         assert(((char*)p) >= min_address);
2367         assert(((char*)p + sz) <= ((char*)(av->top)));
2368       }
2369     }
2370     else {
2371       /* top size is always at least MINSIZE */
2372       assert((unsigned long)(sz) >= MINSIZE);
2373       /* top predecessor always marked inuse */
2374       assert(prev_inuse(p));
2375     }
2376
2377   }
2378   else {
2379 #if HAVE_MMAP
2380     /* address is outside main heap  */
2381     if (contiguous(av) && av->top != initial_top(av)) {
2382       assert(((char*)p) < min_address || ((char*)p) > max_address);
2383     }
2384     /* chunk is page-aligned */
2385     assert(((p->prev_size + sz) & (mp_.pagesize-1)) == 0);
2386     /* mem is aligned */
2387     assert(aligned_OK(chunk2mem(p)));
2388 #else
2389     /* force an appropriate assert violation if debug set */
2390     assert(!chunk_is_mmapped(p));
2391 #endif
2392   }
2393 }
2394
2395 /*
2396   Properties of free chunks
2397 */
2398
2399 #if __STD_C
2400 static void do_check_free_chunk(mstate av, mchunkptr p)
2401 #else
2402 static void do_check_free_chunk(av, p) mstate av; mchunkptr p;
2403 #endif
2404 {
2405   INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
2406   mchunkptr next = chunk_at_offset(p, sz);
2407
2408   do_check_chunk(av, p);
2409
2410   /* Chunk must claim to be free ... */
2411   assert(!inuse(p));
2412   assert (!chunk_is_mmapped(p));
2413
2414   /* Unless a special marker, must have OK fields */
2415   if ((unsigned long)(sz) >= MINSIZE)
2416   {
2417     assert((sz & MALLOC_ALIGN_MASK) == 0);
2418     assert(aligned_OK(chunk2mem(p)));
2419     /* ... matching footer field */
2420     assert(next->prev_size == sz);
2421     /* ... and is fully consolidated */
2422     assert(prev_inuse(p));
2423     assert (next == av->top || inuse(next));
2424
2425     /* ... and has minimally sane links */
2426     assert(p->fd->bk == p);
2427     assert(p->bk->fd == p);
2428   }
2429   else /* markers are always of size SIZE_SZ */
2430     assert(sz == SIZE_SZ);
2431 }
2432
2433 /*
2434   Properties of inuse chunks
2435 */
2436
2437 #if __STD_C
2438 static void do_check_inuse_chunk(mstate av, mchunkptr p)
2439 #else
2440 static void do_check_inuse_chunk(av, p) mstate av; mchunkptr p;
2441 #endif
2442 {
2443   mchunkptr next;
2444
2445   do_check_chunk(av, p);
2446
2447   if (chunk_is_mmapped(p))
2448     return; /* mmapped chunks have no next/prev */
2449
2450   /* Check whether it claims to be in use ... */
2451   assert(inuse(p));
2452
2453   next = next_chunk(p);
2454
2455   /* ... and is surrounded by OK chunks.
2456     Since more things can be checked with free chunks than inuse ones,
2457     if an inuse chunk borders them and debug is on, it's worth doing them.
2458   */
2459   if (!prev_inuse(p))  {
2460     /* Note that we cannot even look at prev unless it is not inuse */
2461     mchunkptr prv = prev_chunk(p);
2462     assert(next_chunk(prv) == p);
2463     do_check_free_chunk(av, prv);
2464   }
2465
2466   if (next == av->top) {
2467     assert(prev_inuse(next));
2468     assert(chunksize(next) >= MINSIZE);
2469   }
2470   else if (!inuse(next))
2471     do_check_free_chunk(av, next);
2472 }
2473
2474 /*
2475   Properties of chunks recycled from fastbins
2476 */
2477
2478 #if __STD_C
2479 static void do_check_remalloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2480 #else
2481 static void do_check_remalloced_chunk(av, p, s)
2482 mstate av; mchunkptr p; INTERNAL_SIZE_T s;
2483 #endif
2484 {
2485   INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
2486
2487   if (!chunk_is_mmapped(p)) {
2488     assert(av == arena_for_chunk(p));
2489     if (chunk_non_main_arena(p))
2490       assert(av != &main_arena);
2491     else
2492       assert(av == &main_arena);
2493   }
2494
2495   do_check_inuse_chunk(av, p);
2496
2497   /* Legal size ... */
2498   assert((sz & MALLOC_ALIGN_MASK) == 0);
2499   assert((unsigned long)(sz) >= MINSIZE);
2500   /* ... and alignment */
2501   assert(aligned_OK(chunk2mem(p)));
2502   /* chunk is less than MINSIZE more than request */
2503   assert((long)(sz) - (long)(s) >= 0);
2504   assert((long)(sz) - (long)(s + MINSIZE) < 0);
2505 }
2506
2507 /*
2508   Properties of nonrecycled chunks at the point they are malloced
2509 */
2510
2511 #if __STD_C
2512 static void do_check_malloced_chunk(mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2513 #else
2514 static void do_check_malloced_chunk(av, p, s)
2515 mstate av; mchunkptr p; INTERNAL_SIZE_T s;
2516 #endif
2517 {
2518   /* same as recycled case ... */
2519   do_check_remalloced_chunk(av, p, s);
2520
2521   /*
2522     ... plus,  must obey implementation invariant that prev_inuse is
2523     always true of any allocated chunk; i.e., that each allocated
2524     chunk borders either a previously allocated and still in-use
2525     chunk, or the base of its memory arena. This is ensured
2526     by making all allocations from the the `lowest' part of any found
2527     chunk.  This does not necessarily hold however for chunks
2528     recycled via fastbins.
2529   */
2530
2531   assert(prev_inuse(p));
2532 }
2533
2534
2535 /*
2536   Properties of malloc_state.
2537
2538   This may be useful for debugging malloc, as well as detecting user
2539   programmer errors that somehow write into malloc_state.
2540
2541   If you are extending or experimenting with this malloc, you can
2542   probably figure out how to hack this routine to print out or
2543   display chunk addresses, sizes, bins, and other instrumentation.
2544 */
2545
2546 static void do_check_malloc_state(mstate av)
2547 {
2548   int i;
2549   mchunkptr p;
2550   mchunkptr q;
2551   mbinptr b;
2552   unsigned int binbit;
2553   int empty;
2554   unsigned int idx;
2555   INTERNAL_SIZE_T size;
2556   unsigned long total = 0;
2557   int max_fast_bin;
2558
2559   /* internal size_t must be no wider than pointer type */
2560   assert(sizeof(INTERNAL_SIZE_T) <= sizeof(char*));
2561
2562   /* alignment is a power of 2 */
2563   assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0);
2564
2565   /* cannot run remaining checks until fully initialized */
2566   if (av->top == 0 || av->top == initial_top(av))
2567     return;
2568
2569   /* pagesize is a power of 2 */
2570   assert((mp_.pagesize & (mp_.pagesize-1)) == 0);
2571
2572   /* A contiguous main_arena is consistent with sbrk_base.  */
2573   if (av == &main_arena && contiguous(av))
2574     assert((char*)mp_.sbrk_base + av->system_mem ==
2575            (char*)av->top + chunksize(av->top));
2576
2577   /* properties of fastbins */
2578
2579   /* max_fast is in allowed range */
2580   assert((av->max_fast & ~1) <= request2size(MAX_FAST_SIZE));
2581
2582   max_fast_bin = fastbin_index(av->max_fast);
2583
2584   for (i = 0; i < NFASTBINS; ++i) {
2585     p = av->fastbins[i];
2586
2587     /* all bins past max_fast are empty */
2588     if (i > max_fast_bin)
2589       assert(p == 0);
2590
2591     while (p != 0) {
2592       /* each chunk claims to be inuse */
2593       do_check_inuse_chunk(av, p);
2594       total += chunksize(p);
2595       /* chunk belongs in this bin */
2596       assert(fastbin_index(chunksize(p)) == i);
2597       p = p->fd;
2598     }
2599   }
2600
2601   if (total != 0)
2602     assert(have_fastchunks(av));
2603   else if (!have_fastchunks(av))
2604     assert(total == 0);
2605
2606   /* check normal bins */
2607   for (i = 1; i < NBINS; ++i) {
2608     b = bin_at(av,i);
2609
2610     /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2611     if (i >= 2) {
2612       binbit = get_binmap(av,i);
2613       empty = last(b) == b;
2614       if (!binbit)
2615         assert(empty);
2616       else if (!empty)
2617         assert(binbit);
2618     }
2619
2620     for (p = last(b); p != b; p = p->bk) {
2621       /* each chunk claims to be free */
2622       do_check_free_chunk(av, p);
2623       size = chunksize(p);
2624       total += size;
2625       if (i >= 2) {
2626         /* chunk belongs in bin */
2627         idx = bin_index(size);
2628         assert(idx == i);
2629         /* lists are sorted */
2630         assert(p->bk == b ||
2631                (unsigned long)chunksize(p->bk) >= (unsigned long)chunksize(p));
2632       }
2633       /* chunk is followed by a legal chain of inuse chunks */
2634       for (q = next_chunk(p);
2635            (q != av->top && inuse(q) &&
2636              (unsigned long)(chunksize(q)) >= MINSIZE);
2637            q = next_chunk(q))
2638         do_check_inuse_chunk(av, q);
2639     }
2640   }
2641
2642   /* top chunk is OK */
2643   check_chunk(av, av->top);
2644
2645   /* sanity checks for statistics */
2646
2647 #ifdef NO_THREADS
2648   assert(total <= (unsigned long)(mp_.max_total_mem));
2649   assert(mp_.n_mmaps >= 0);
2650 #endif
2651   assert(mp_.n_mmaps <= mp_.n_mmaps_max);
2652   assert(mp_.n_mmaps <= mp_.max_n_mmaps);
2653
2654   assert((unsigned long)(av->system_mem) <=
2655          (unsigned long)(av->max_system_mem));
2656
2657   assert((unsigned long)(mp_.mmapped_mem) <=
2658          (unsigned long)(mp_.max_mmapped_mem));
2659
2660 #ifdef NO_THREADS
2661   assert((unsigned long)(mp_.max_total_mem) >=
2662          (unsigned long)(mp_.mmapped_mem) + (unsigned long)(av->system_mem));
2663 #endif
2664 }
2665 #endif
2666
2667
2668 /* ----------------- Support for debugging hooks -------------------- */
2669 #include "hooks.c"
2670
2671
2672 /* ----------- Routines dealing with system allocation -------------- */
2673
2674 /*
2675   sysmalloc handles malloc cases requiring more memory from the system.
2676   On entry, it is assumed that av->top does not have enough
2677   space to service request for nb bytes, thus requiring that av->top
2678   be extended or replaced.
2679 */
2680
2681 #if __STD_C
2682 static Void_t* sYSMALLOc(INTERNAL_SIZE_T nb, mstate av)
2683 #else
2684 static Void_t* sYSMALLOc(nb, av) INTERNAL_SIZE_T nb; mstate av;
2685 #endif
2686 {
2687   mchunkptr       old_top;        /* incoming value of av->top */
2688   INTERNAL_SIZE_T old_size;       /* its size */
2689   char*           old_end;        /* its end address */
2690
2691   long            size;           /* arg to first MORECORE or mmap call */
2692   char*           brk;            /* return value from MORECORE */
2693
2694   long            correction;     /* arg to 2nd MORECORE call */
2695   char*           snd_brk;        /* 2nd return val */
2696
2697   INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
2698   INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
2699   char*           aligned_brk;    /* aligned offset into brk */
2700
2701   mchunkptr       p;              /* the allocated/returned chunk */
2702   mchunkptr       remainder;      /* remainder from allocation */
2703   unsigned long   remainder_size; /* its size */
2704
2705   unsigned long   sum;            /* for updating stats */
2706
2707   size_t          pagemask  = mp_.pagesize - 1;
2708
2709
2710 #if HAVE_MMAP
2711
2712   /*
2713     If have mmap, and the request size meets the mmap threshold, and
2714     the system supports mmap, and there are few enough currently
2715     allocated mmapped regions, try to directly map this request
2716     rather than expanding top.
2717   */
2718
2719   if ((unsigned long)(nb) >= (unsigned long)(mp_.mmap_threshold) &&
2720       (mp_.n_mmaps < mp_.n_mmaps_max)) {
2721
2722     char* mm;             /* return value from mmap call*/
2723
2724     /*
2725       Round up size to nearest page.  For mmapped chunks, the overhead
2726       is one SIZE_SZ unit larger than for normal chunks, because there
2727       is no following chunk whose prev_size field could be used.
2728     */
2729     size = (nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
2730
2731     /* Don't try if size wraps around 0 */
2732     if ((unsigned long)(size) > (unsigned long)(nb)) {
2733
2734       mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
2735
2736       if (mm != MAP_FAILED) {
2737
2738         /*
2739           The offset to the start of the mmapped region is stored
2740           in the prev_size field of the chunk. This allows us to adjust
2741           returned start address to meet alignment requirements here
2742           and in memalign(), and still be able to compute proper
2743           address argument for later munmap in free() and realloc().
2744         */
2745
2746         front_misalign = (INTERNAL_SIZE_T)chunk2mem(mm) & MALLOC_ALIGN_MASK;
2747         if (front_misalign > 0) {
2748           correction = MALLOC_ALIGNMENT - front_misalign;
2749           p = (mchunkptr)(mm + correction);
2750           p->prev_size = correction;
2751           set_head(p, (size - correction) |IS_MMAPPED);
2752         }
2753         else {
2754           p = (mchunkptr)mm;
2755           set_head(p, size|IS_MMAPPED);
2756         }
2757
2758         /* update statistics */
2759
2760         if (++mp_.n_mmaps > mp_.max_n_mmaps)
2761           mp_.max_n_mmaps = mp_.n_mmaps;
2762
2763         sum = mp_.mmapped_mem += size;
2764         if (sum > (unsigned long)(mp_.max_mmapped_mem))
2765           mp_.max_mmapped_mem = sum;
2766 #ifdef NO_THREADS
2767         sum += av->system_mem;
2768         if (sum > (unsigned long)(mp_.max_total_mem))
2769           mp_.max_total_mem = sum;
2770 #endif
2771
2772         check_chunk(av, p);
2773
2774         return chunk2mem(p);
2775       }
2776     }
2777   }
2778 #endif
2779
2780   /* Record incoming configuration of top */
2781
2782   old_top  = av->top;
2783   old_size = chunksize(old_top);
2784   old_end  = (char*)(chunk_at_offset(old_top, old_size));
2785
2786   brk = snd_brk = (char*)(MORECORE_FAILURE);
2787
2788   /*
2789      If not the first time through, we require old_size to be
2790      at least MINSIZE and to have prev_inuse set.
2791   */
2792
2793   assert((old_top == initial_top(av) && old_size == 0) ||
2794          ((unsigned long) (old_size) >= MINSIZE &&
2795           prev_inuse(old_top) &&
2796           ((unsigned long)old_end & pagemask) == 0));
2797
2798   /* Precondition: not enough current space to satisfy nb request */
2799   assert((unsigned long)(old_size) < (unsigned long)(nb + MINSIZE));
2800
2801   /* Precondition: all fastbins are consolidated */
2802   assert(!have_fastchunks(av));
2803
2804
2805   if (av != &main_arena) {
2806
2807     heap_info *old_heap, *heap;
2808     size_t old_heap_size;
2809
2810     /* First try to extend the current heap. */
2811     old_heap = heap_for_ptr(old_top);
2812     old_heap_size = old_heap->size;
2813     if (grow_heap(old_heap, MINSIZE + nb - old_size) == 0) {
2814       av->system_mem += old_heap->size - old_heap_size;
2815       arena_mem += old_heap->size - old_heap_size;
2816 #if 0
2817       if(mmapped_mem + arena_mem + sbrked_mem > max_total_mem)
2818         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
2819 #endif
2820       set_head(old_top, (((char *)old_heap + old_heap->size) - (char *)old_top)
2821                | PREV_INUSE);
2822     }
2823     else if ((heap = new_heap(nb + (MINSIZE + sizeof(*heap)), mp_.top_pad))) {
2824       /* Use a newly allocated heap.  */
2825       heap->ar_ptr = av;
2826       heap->prev = old_heap;
2827       av->system_mem += heap->size;
2828       arena_mem += heap->size;
2829 #if 0
2830       if((unsigned long)(mmapped_mem + arena_mem + sbrked_mem) > max_total_mem)
2831         max_total_mem = mmapped_mem + arena_mem + sbrked_mem;
2832 #endif
2833       /* Set up the new top.  */
2834       top(av) = chunk_at_offset(heap, sizeof(*heap));
2835       set_head(top(av), (heap->size - sizeof(*heap)) | PREV_INUSE);
2836
2837       /* Setup fencepost and free the old top chunk. */
2838       /* The fencepost takes at least MINSIZE bytes, because it might
2839          become the top chunk again later.  Note that a footer is set
2840          up, too, although the chunk is marked in use. */
2841       old_size -= MINSIZE;
2842       set_head(chunk_at_offset(old_top, old_size + 2*SIZE_SZ), 0|PREV_INUSE);
2843       if (old_size >= MINSIZE) {
2844         set_head(chunk_at_offset(old_top, old_size), (2*SIZE_SZ)|PREV_INUSE);
2845         set_foot(chunk_at_offset(old_top, old_size), (2*SIZE_SZ));
2846         set_head(old_top, old_size|PREV_INUSE|NON_MAIN_ARENA);
2847         _int_free(av, chunk2mem(old_top));
2848       } else {
2849         set_head(old_top, (old_size + 2*SIZE_SZ)|PREV_INUSE);
2850         set_foot(old_top, (old_size + 2*SIZE_SZ));
2851       }
2852     }
2853
2854   } else { /* av == main_arena */
2855
2856
2857   /* Request enough space for nb + pad + overhead */
2858
2859   size = nb + mp_.top_pad + MINSIZE;
2860
2861   /*
2862     If contiguous, we can subtract out existing space that we hope to
2863     combine with new space. We add it back later only if
2864     we don't actually get contiguous space.
2865   */
2866
2867   if (contiguous(av))
2868     size -= old_size;
2869
2870   /*
2871     Round to a multiple of page size.
2872     If MORECORE is not contiguous, this ensures that we only call it
2873     with whole-page arguments.  And if MORECORE is contiguous and
2874     this is not first time through, this preserves page-alignment of
2875     previous calls. Otherwise, we correct to page-align below.
2876   */
2877
2878   size = (size + pagemask) & ~pagemask;
2879
2880   /*
2881     Don't try to call MORECORE if argument is so big as to appear
2882     negative. Note that since mmap takes size_t arg, it may succeed
2883     below even if we cannot call MORECORE.
2884   */
2885
2886   if (size > 0)
2887     brk = (char*)(MORECORE(size));
2888
2889   if (brk != (char*)(MORECORE_FAILURE)) {
2890     /* Call the `morecore' hook if necessary.  */
2891     if (__after_morecore_hook)
2892       (*__after_morecore_hook) ();
2893   } else {
2894   /*
2895     If have mmap, try using it as a backup when MORECORE fails or
2896     cannot be used. This is worth doing on systems that have "holes" in
2897     address space, so sbrk cannot extend to give contiguous space, but
2898     space is available elsewhere.  Note that we ignore mmap max count
2899     and threshold limits, since the space will not be used as a
2900     segregated mmap region.
2901   */
2902
2903 #if HAVE_MMAP
2904     /* Cannot merge with old top, so add its size back in */
2905     if (contiguous(av))
2906       size = (size + old_size + pagemask) & ~pagemask;
2907
2908     /* If we are relying on mmap as backup, then use larger units */
2909     if ((unsigned long)(size) < (unsigned long)(MMAP_AS_MORECORE_SIZE))
2910       size = MMAP_AS_MORECORE_SIZE;
2911
2912     /* Don't try if size wraps around 0 */
2913     if ((unsigned long)(size) > (unsigned long)(nb)) {
2914
2915       char *mbrk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
2916
2917       if (mbrk != MAP_FAILED) {
2918
2919         /* We do not need, and cannot use, another sbrk call to find end */
2920         brk = mbrk;
2921         snd_brk = brk + size;
2922
2923         /*
2924            Record that we no longer have a contiguous sbrk region.
2925            After the first time mmap is used as backup, we do not
2926            ever rely on contiguous space since this could incorrectly
2927            bridge regions.
2928         */
2929         set_noncontiguous(av);
2930       }
2931     }
2932 #endif
2933   }
2934
2935   if (brk != (char*)(MORECORE_FAILURE)) {
2936     if (mp_.sbrk_base == 0)
2937       mp_.sbrk_base = brk;
2938     av->system_mem += size;
2939
2940     /*
2941       If MORECORE extends previous space, we can likewise extend top size.
2942     */
2943
2944     if (brk == old_end && snd_brk == (char*)(MORECORE_FAILURE))
2945       set_head(old_top, (size + old_size) | PREV_INUSE);
2946
2947     else if (old_size && brk < old_end) {
2948       /* Oops!  Someone else killed our space..  Can't touch anything.  */
2949       assert(0);
2950     }
2951
2952     /*
2953       Otherwise, make adjustments:
2954
2955       * If the first time through or noncontiguous, we need to call sbrk
2956         just to find out where the end of memory lies.
2957
2958       * We need to ensure that all returned chunks from malloc will meet
2959         MALLOC_ALIGNMENT
2960
2961       * If there was an intervening foreign sbrk, we need to adjust sbrk
2962         request size to account for fact that we will not be able to
2963         combine new space with existing space in old_top.
2964
2965       * Almost all systems internally allocate whole pages at a time, in
2966         which case we might as well use the whole last page of request.
2967         So we allocate enough more memory to hit a page boundary now,
2968         which in turn causes future contiguous calls to page-align.
2969     */
2970
2971     else {
2972       /* Count foreign sbrk as system_mem.  */
2973       if (old_size)
2974         av->system_mem += brk - old_end;
2975       front_misalign = 0;
2976       end_misalign = 0;
2977       correction = 0;
2978       aligned_brk = brk;
2979
2980       /* handle contiguous cases */
2981       if (contiguous(av)) {
2982
2983         /* Guarantee alignment of first new chunk made from this space */
2984
2985         front_misalign = (INTERNAL_SIZE_T)chunk2mem(brk) & MALLOC_ALIGN_MASK;
2986         if (front_misalign > 0) {
2987
2988           /*
2989             Skip over some bytes to arrive at an aligned position.
2990             We don't need to specially mark these wasted front bytes.
2991             They will never be accessed anyway because
2992             prev_inuse of av->top (and any chunk created from its start)
2993             is always true after initialization.
2994           */
2995
2996           correction = MALLOC_ALIGNMENT - front_misalign;
2997           aligned_brk += correction;
2998         }
2999
3000         /*
3001           If this isn't adjacent to existing space, then we will not
3002           be able to merge with old_top space, so must add to 2nd request.
3003         */
3004
3005         correction += old_size;
3006
3007         /* Extend the end address to hit a page boundary */
3008         end_misalign = (INTERNAL_SIZE_T)(brk + size + correction);
3009         correction += ((end_misalign + pagemask) & ~pagemask) - end_misalign;
3010
3011         assert(correction >= 0);
3012         snd_brk = (char*)(MORECORE(correction));
3013
3014         /*
3015           If can't allocate correction, try to at least find out current
3016           brk.  It might be enough to proceed without failing.
3017
3018           Note that if second sbrk did NOT fail, we assume that space
3019           is contiguous with first sbrk. This is a safe assumption unless
3020           program is multithreaded but doesn't use locks and a foreign sbrk
3021           occurred between our first and second calls.
3022         */
3023
3024         if (snd_brk == (char*)(MORECORE_FAILURE)) {
3025           correction = 0;
3026           snd_brk = (char*)(MORECORE(0));
3027         } else
3028           /* Call the `morecore' hook if necessary.  */
3029           if (__after_morecore_hook)
3030             (*__after_morecore_hook) ();
3031       }
3032
3033       /* handle non-contiguous cases */
3034       else {
3035         /* MORECORE/mmap must correctly align */
3036         assert(((unsigned long)chunk2mem(brk) & MALLOC_ALIGN_MASK) == 0);
3037
3038         /* Find out current end of memory */
3039         if (snd_brk == (char*)(MORECORE_FAILURE)) {
3040           snd_brk = (char*)(MORECORE(0));
3041         }
3042       }
3043
3044       /* Adjust top based on results of second sbrk */
3045       if (snd_brk != (char*)(MORECORE_FAILURE)) {
3046         av->top = (mchunkptr)aligned_brk;
3047         set_head(av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
3048         av->system_mem += correction;
3049
3050         /*
3051           If not the first time through, we either have a
3052           gap due to foreign sbrk or a non-contiguous region.  Insert a
3053           double fencepost at old_top to prevent consolidation with space
3054           we don't own. These fenceposts are artificial chunks that are
3055           marked as inuse and are in any case too small to use.  We need
3056           two to make sizes and alignments work out.
3057         */
3058
3059         if (old_size != 0) {
3060           /*
3061              Shrink old_top to insert fenceposts, keeping size a
3062              multiple of MALLOC_ALIGNMENT. We know there is at least
3063              enough space in old_top to do this.
3064           */
3065           old_size = (old_size - 4*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
3066           set_head(old_top, old_size | PREV_INUSE);
3067
3068           /*
3069             Note that the following assignments completely overwrite
3070             old_top when old_size was previously MINSIZE.  This is
3071             intentional. We need the fencepost, even if old_top otherwise gets
3072             lost.
3073           */
3074           chunk_at_offset(old_top, old_size            )->size =
3075             (2*SIZE_SZ)|PREV_INUSE;
3076
3077           chunk_at_offset(old_top, old_size + 2*SIZE_SZ)->size =
3078             (2*SIZE_SZ)|PREV_INUSE;
3079
3080           /* If possible, release the rest. */
3081           if (old_size >= MINSIZE) {
3082             _int_free(av, chunk2mem(old_top));
3083           }
3084
3085         }
3086       }
3087     }
3088
3089     /* Update statistics */
3090 #ifdef NO_THREADS
3091     sum = av->system_mem + mp_.mmapped_mem;
3092     if (sum > (unsigned long)(mp_.max_total_mem))
3093       mp_.max_total_mem = sum;
3094 #endif
3095
3096   }
3097
3098   } /* if (av !=  &main_arena) */
3099
3100   if ((unsigned long)av->system_mem > (unsigned long)(av->max_system_mem))
3101     av->max_system_mem = av->system_mem;
3102   check_malloc_state(av);
3103
3104   /* finally, do the allocation */
3105   p = av->top;
3106   size = chunksize(p);
3107
3108   /* check that one of the above allocation paths succeeded */
3109   if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {
3110     remainder_size = size - nb;
3111     remainder = chunk_at_offset(p, nb);
3112     av->top = remainder;
3113     set_head(p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
3114     set_head(remainder, remainder_size | PREV_INUSE);
3115     check_malloced_chunk(av, p, nb);
3116     return chunk2mem(p);
3117   }
3118
3119   /* catch all failure paths */
3120   MALLOC_FAILURE_ACTION;
3121   return 0;
3122 }
3123
3124
3125 /*
3126   sYSTRIm is an inverse of sorts to sYSMALLOc.  It gives memory back
3127   to the system (via negative arguments to sbrk) if there is unused
3128   memory at the `high' end of the malloc pool. It is called
3129   automatically by free() when top space exceeds the trim
3130   threshold. It is also called by the public malloc_trim routine.  It
3131   returns 1 if it actually released any memory, else 0.
3132 */
3133
3134 #if __STD_C
3135 static int sYSTRIm(size_t pad, mstate av)
3136 #else
3137 static int sYSTRIm(pad, av) size_t pad; mstate av;
3138 #endif
3139 {
3140   long  top_size;        /* Amount of top-most memory */
3141   long  extra;           /* Amount to release */
3142   long  released;        /* Amount actually released */
3143   char* current_brk;     /* address returned by pre-check sbrk call */
3144   char* new_brk;         /* address returned by post-check sbrk call */
3145   size_t pagesz;
3146
3147   pagesz = mp_.pagesize;
3148   top_size = chunksize(av->top);
3149
3150   /* Release in pagesize units, keeping at least one page */
3151   extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
3152
3153   if (extra > 0) {
3154
3155     /*
3156       Only proceed if end of memory is where we last set it.
3157       This avoids problems if there were foreign sbrk calls.
3158     */
3159     current_brk = (char*)(MORECORE(0));
3160     if (current_brk == (char*)(av->top) + top_size) {
3161
3162       /*
3163         Attempt to release memory. We ignore MORECORE return value,
3164         and instead call again to find out where new end of memory is.
3165         This avoids problems if first call releases less than we asked,
3166         of if failure somehow altered brk value. (We could still
3167         encounter problems if it altered brk in some very bad way,
3168         but the only thing we can do is adjust anyway, which will cause
3169         some downstream failure.)
3170       */
3171
3172       MORECORE(-extra);
3173       /* Call the `morecore' hook if necessary.  */
3174       if (__after_morecore_hook)
3175         (*__after_morecore_hook) ();
3176       new_brk = (char*)(MORECORE(0));
3177
3178       if (new_brk != (char*)MORECORE_FAILURE) {
3179         released = (long)(current_brk - new_brk);
3180
3181         if (released != 0) {
3182           /* Success. Adjust top. */
3183           av->system_mem -= released;
3184           set_head(av->top, (top_size - released) | PREV_INUSE);
3185           check_malloc_state(av);
3186           return 1;
3187         }
3188       }
3189     }
3190   }
3191   return 0;
3192 }
3193
3194 #ifdef HAVE_MMAP
3195
3196 static void
3197 internal_function
3198 #if __STD_C
3199 munmap_chunk(mchunkptr p)
3200 #else
3201 munmap_chunk(p) mchunkptr p;
3202 #endif
3203 {
3204   INTERNAL_SIZE_T size = chunksize(p);
3205   int ret;
3206
3207   assert (chunk_is_mmapped(p));
3208 #if 0
3209   assert(! ((char*)p >= mp_.sbrk_base && (char*)p < mp_.sbrk_base + mp_.sbrked_mem));
3210   assert((mp_.n_mmaps > 0));
3211 #endif
3212   assert(((p->prev_size + size) & (mp_.pagesize-1)) == 0);
3213
3214   mp_.n_mmaps--;
3215   mp_.mmapped_mem -= (size + p->prev_size);
3216
3217   ret = munmap((char *)p - p->prev_size, size + p->prev_size);
3218
3219   /* munmap returns non-zero on failure */
3220   assert(ret == 0);
3221 }
3222
3223 #if HAVE_MREMAP
3224
3225 static mchunkptr
3226 internal_function
3227 #if __STD_C
3228 mremap_chunk(mchunkptr p, size_t new_size)
3229 #else
3230 mremap_chunk(p, new_size) mchunkptr p; size_t new_size;
3231 #endif
3232 {
3233   size_t page_mask = mp_.pagesize - 1;
3234   INTERNAL_SIZE_T offset = p->prev_size;
3235   INTERNAL_SIZE_T size = chunksize(p);
3236   char *cp;
3237
3238   assert (chunk_is_mmapped(p));
3239 #if 0
3240   assert(! ((char*)p >= mp_.sbrk_base && (char*)p < mp_.sbrk_base + mp_.sbrked_mem));
3241   assert((mp_.n_mmaps > 0));
3242 #endif
3243   assert(((size + offset) & (mp_.pagesize-1)) == 0);
3244
3245   /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
3246   new_size = (new_size + offset + SIZE_SZ + page_mask) & ~page_mask;
3247
3248   cp = (char *)mremap((char *)p - offset, size + offset, new_size,
3249                       MREMAP_MAYMOVE);
3250
3251   if (cp == MAP_FAILED) return 0;
3252
3253   p = (mchunkptr)(cp + offset);
3254
3255   assert(aligned_OK(chunk2mem(p)));
3256
3257   assert((p->prev_size == offset));
3258   set_head(p, (new_size - offset)|IS_MMAPPED);
3259
3260   mp_.mmapped_mem -= size + offset;
3261   mp_.mmapped_mem += new_size;
3262   if ((unsigned long)mp_.mmapped_mem > (unsigned long)mp_.max_mmapped_mem)
3263     mp_.max_mmapped_mem = mp_.mmapped_mem;
3264 #ifdef NO_THREADS
3265   if ((unsigned long)(mp_.mmapped_mem + arena_mem + main_arena.system_mem) >
3266       mp_.max_total_mem)
3267     mp_.max_total_mem = mp_.mmapped_mem + arena_mem + main_arena.system_mem;
3268 #endif
3269   return p;
3270 }
3271
3272 #endif /* HAVE_MREMAP */
3273
3274 #endif /* HAVE_MMAP */
3275
3276 /*------------------------ Public wrappers. --------------------------------*/
3277
3278 Void_t*
3279 public_mALLOc(size_t bytes)
3280 {
3281   mstate ar_ptr;
3282   Void_t *victim;
3283
3284   __malloc_ptr_t (*hook) __MALLOC_P ((size_t, __const __malloc_ptr_t)) =
3285     __malloc_hook;
3286   if (hook != NULL)
3287     return (*hook)(bytes, RETURN_ADDRESS (0));
3288
3289   arena_get(ar_ptr, bytes);
3290   if(!ar_ptr)
3291     return 0;
3292   victim = _int_malloc(ar_ptr, bytes);
3293   if(!victim) {
3294     /* Maybe the failure is due to running out of mmapped areas. */
3295     if(ar_ptr != &main_arena) {
3296       (void)mutex_unlock(&ar_ptr->mutex);
3297       (void)mutex_lock(&main_arena.mutex);
3298       victim = _int_malloc(&main_arena, bytes);
3299       (void)mutex_unlock(&main_arena.mutex);
3300     } else {
3301 #if USE_ARENAS
3302       /* ... or sbrk() has failed and there is still a chance to mmap() */
3303       ar_ptr = arena_get2(ar_ptr->next ? ar_ptr : 0, bytes);
3304       (void)mutex_unlock(&main_arena.mutex);
3305       if(ar_ptr) {
3306         victim = _int_malloc(ar_ptr, bytes);
3307         (void)mutex_unlock(&ar_ptr->mutex);
3308       }
3309 #endif
3310     }
3311   } else
3312     (void)mutex_unlock(&ar_ptr->mutex);
3313   assert(!victim || chunk_is_mmapped(mem2chunk(victim)) ||
3314          ar_ptr == arena_for_chunk(mem2chunk(victim)));
3315   return victim;
3316 }
3317
3318 void
3319 public_fREe(Void_t* mem)
3320 {
3321   mstate ar_ptr;
3322   mchunkptr p;                          /* chunk corresponding to mem */
3323
3324   void (*hook) __MALLOC_P ((__malloc_ptr_t, __const __malloc_ptr_t)) =
3325     __free_hook;
3326   if (hook != NULL) {
3327     (*hook)(mem, RETURN_ADDRESS (0));
3328     return;
3329   }
3330
3331   if (mem == 0)                              /* free(0) has no effect */
3332     return;
3333
3334   p = mem2chunk(mem);
3335
3336 #if HAVE_MMAP
3337   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
3338   {
3339     munmap_chunk(p);
3340     return;
3341   }
3342 #endif
3343
3344   ar_ptr = arena_for_chunk(p);
3345 #if THREAD_STATS
3346   if(!mutex_trylock(&ar_ptr->mutex))
3347     ++(ar_ptr->stat_lock_direct);
3348   else {
3349     (void)mutex_lock(&ar_ptr->mutex);
3350     ++(ar_ptr->stat_lock_wait);
3351   }
3352 #else
3353   (void)mutex_lock(&ar_ptr->mutex);
3354 #endif
3355   _int_free(ar_ptr, mem);
3356   (void)mutex_unlock(&ar_ptr->mutex);
3357 }
3358
3359 Void_t*
3360 public_rEALLOc(Void_t* oldmem, size_t bytes)
3361 {
3362   mstate ar_ptr;
3363   INTERNAL_SIZE_T    nb;      /* padded request size */
3364
3365   mchunkptr oldp;             /* chunk corresponding to oldmem */
3366   INTERNAL_SIZE_T    oldsize; /* its size */
3367
3368   Void_t* newp;             /* chunk to return */
3369
3370   __malloc_ptr_t (*hook) __MALLOC_P ((__malloc_ptr_t, size_t,
3371                                       __const __malloc_ptr_t)) =
3372     __realloc_hook;
3373   if (hook != NULL)
3374     return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));
3375
3376 #if REALLOC_ZERO_BYTES_FREES
3377   if (bytes == 0 && oldmem != NULL) { public_fREe(oldmem); return 0; }
3378 #endif
3379
3380   /* realloc of null is supposed to be same as malloc */
3381   if (oldmem == 0) return public_mALLOc(bytes);
3382
3383   oldp    = mem2chunk(oldmem);
3384   oldsize = chunksize(oldp);
3385
3386   checked_request2size(bytes, nb);
3387
3388 #if HAVE_MMAP
3389   if (chunk_is_mmapped(oldp))
3390   {
3391     Void_t* newmem;
3392
3393 #if HAVE_MREMAP
3394     newp = mremap_chunk(oldp, nb);
3395     if(newp) return chunk2mem(newp);
3396 #endif
3397     /* Note the extra SIZE_SZ overhead. */
3398     if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */
3399     /* Must alloc, copy, free. */
3400     newmem = public_mALLOc(bytes);
3401     if (newmem == 0) return 0; /* propagate failure */
3402     MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
3403     munmap_chunk(oldp);
3404     return newmem;
3405   }
3406 #endif
3407
3408   ar_ptr = arena_for_chunk(oldp);
3409 #if THREAD_STATS
3410   if(!mutex_trylock(&ar_ptr->mutex))
3411     ++(ar_ptr->stat_lock_direct);
3412   else {
3413     (void)mutex_lock(&ar_ptr->mutex);
3414     ++(ar_ptr->stat_lock_wait);
3415   }
3416 #else
3417   (void)mutex_lock(&ar_ptr->mutex);
3418 #endif
3419
3420 #ifndef NO_THREADS
3421   /* As in malloc(), remember this arena for the next allocation. */
3422   tsd_setspecific(arena_key, (Void_t *)ar_ptr);
3423 #endif
3424
3425   newp = _int_realloc(ar_ptr, oldmem, bytes);
3426
3427   (void)mutex_unlock(&ar_ptr->mutex);
3428   assert(!newp || chunk_is_mmapped(mem2chunk(newp)) ||
3429          ar_ptr == arena_for_chunk(mem2chunk(newp)));
3430   return newp;
3431 }
3432
3433 Void_t*
3434 public_mEMALIGn(size_t alignment, size_t bytes)
3435 {
3436   mstate ar_ptr;
3437   Void_t *p;
3438
3439   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, size_t,
3440                                         __const __malloc_ptr_t)) =
3441     __memalign_hook;
3442   if (hook != NULL)
3443     return (*hook)(alignment, bytes, RETURN_ADDRESS (0));
3444
3445   /* If need less alignment than we give anyway, just relay to malloc */
3446   if (alignment <= MALLOC_ALIGNMENT) return public_mALLOc(bytes);
3447
3448   /* Otherwise, ensure that it is at least a minimum chunk size */
3449   if (alignment <  MINSIZE) alignment = MINSIZE;
3450
3451   arena_get(ar_ptr, bytes + alignment + MINSIZE);
3452   if(!ar_ptr)
3453     return 0;
3454   p = _int_memalign(ar_ptr, alignment, bytes);
3455   (void)mutex_unlock(&ar_ptr->mutex);
3456   if(!p) {
3457     /* Maybe the failure is due to running out of mmapped areas. */
3458     if(ar_ptr != &main_arena) {
3459       (void)mutex_lock(&main_arena.mutex);
3460       p = _int_memalign(&main_arena, alignment, bytes);
3461       (void)mutex_unlock(&main_arena.mutex);
3462     } else {
3463 #if USE_ARENAS
3464       /* ... or sbrk() has failed and there is still a chance to mmap() */
3465       ar_ptr = arena_get2(ar_ptr->next ? ar_ptr : 0, bytes);
3466       if(ar_ptr) {
3467         p = _int_memalign(ar_ptr, alignment, bytes);
3468         (void)mutex_unlock(&ar_ptr->mutex);
3469       }
3470 #endif
3471     }
3472   }
3473   assert(!p || chunk_is_mmapped(mem2chunk(p)) ||
3474          ar_ptr == arena_for_chunk(mem2chunk(p)));
3475   return p;
3476 }
3477
3478 Void_t*
3479 public_vALLOc(size_t bytes)
3480 {
3481   mstate ar_ptr;
3482   Void_t *p;
3483
3484   if(__malloc_initialized < 0)
3485     ptmalloc_init ();
3486   arena_get(ar_ptr, bytes + mp_.pagesize + MINSIZE);
3487   if(!ar_ptr)
3488     return 0;
3489   p = _int_valloc(ar_ptr, bytes);
3490   (void)mutex_unlock(&ar_ptr->mutex);
3491   return p;
3492 }
3493
3494 Void_t*
3495 public_pVALLOc(size_t bytes)
3496 {
3497   mstate ar_ptr;
3498   Void_t *p;
3499
3500   if(__malloc_initialized < 0)
3501     ptmalloc_init ();
3502   arena_get(ar_ptr, bytes + 2*mp_.pagesize + MINSIZE);
3503   p = _int_pvalloc(ar_ptr, bytes);
3504   (void)mutex_unlock(&ar_ptr->mutex);
3505   return p;
3506 }
3507
3508 Void_t*
3509 public_cALLOc(size_t n, size_t elem_size)
3510 {
3511   mstate av;
3512   mchunkptr oldtop, p;
3513   INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
3514   Void_t* mem;
3515   unsigned long clearsize;
3516   unsigned long nclears;
3517   INTERNAL_SIZE_T* d;
3518   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, __const __malloc_ptr_t)) =
3519     __malloc_hook;
3520
3521   /* size_t is unsigned so the behavior on overflow is defined.  */
3522   bytes = n * elem_size;
3523 #define HALF_INTERNAL_SIZE_T \
3524   (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3525   if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0)) {
3526     if (elem_size != 0 && bytes / elem_size != n) {
3527       MALLOC_FAILURE_ACTION;
3528       return 0;
3529     }
3530   }
3531
3532   if (hook != NULL) {
3533     sz = bytes;
3534     mem = (*hook)(sz, RETURN_ADDRESS (0));
3535     if(mem == 0)
3536       return 0;
3537 #ifdef HAVE_MEMCPY
3538     return memset(mem, 0, sz);
3539 #else
3540     while(sz > 0) ((char*)mem)[--sz] = 0; /* rather inefficient */
3541     return mem;
3542 #endif
3543   }
3544
3545   sz = bytes;
3546
3547   arena_get(av, sz);
3548   if(!av)
3549     return 0;
3550
3551   /* Check if we hand out the top chunk, in which case there may be no
3552      need to clear. */
3553 #if MORECORE_CLEARS
3554   oldtop = top(av);
3555   oldtopsize = chunksize(top(av));
3556 #if MORECORE_CLEARS < 2
3557   /* Only newly allocated memory is guaranteed to be cleared.  */
3558   if (av == &main_arena &&
3559       oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *)oldtop)
3560     oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *)oldtop);
3561 #endif
3562 #endif
3563   mem = _int_malloc(av, sz);
3564
3565   /* Only clearing follows, so we can unlock early. */
3566   (void)mutex_unlock(&av->mutex);
3567
3568   assert(!mem || chunk_is_mmapped(mem2chunk(mem)) ||
3569          av == arena_for_chunk(mem2chunk(mem)));
3570
3571   if (mem == 0) {
3572     /* Maybe the failure is due to running out of mmapped areas. */
3573     if(av != &main_arena) {
3574       (void)mutex_lock(&main_arena.mutex);
3575       mem = _int_malloc(&main_arena, sz);
3576       (void)mutex_unlock(&main_arena.mutex);
3577     } else {
3578 #if USE_ARENAS
3579       /* ... or sbrk() has failed and there is still a chance to mmap() */
3580       (void)mutex_lock(&main_arena.mutex);
3581       av = arena_get2(av->next ? av : 0, sz);
3582       (void)mutex_unlock(&main_arena.mutex);
3583       if(av) {
3584         mem = _int_malloc(av, sz);
3585         (void)mutex_unlock(&av->mutex);
3586       }
3587 #endif
3588     }
3589     if (mem == 0) return 0;
3590   }
3591   p = mem2chunk(mem);
3592
3593   /* Two optional cases in which clearing not necessary */
3594 #if HAVE_MMAP
3595   if (chunk_is_mmapped(p))
3596     return mem;
3597 #endif
3598
3599   csz = chunksize(p);
3600
3601 #if MORECORE_CLEARS
3602   if (p == oldtop && csz > oldtopsize) {
3603     /* clear only the bytes from non-freshly-sbrked memory */
3604     csz = oldtopsize;
3605   }
3606 #endif
3607
3608   /* Unroll clear of <= 36 bytes (72 if 8byte sizes).  We know that
3609      contents have an odd number of INTERNAL_SIZE_T-sized words;
3610      minimally 3.  */
3611   d = (INTERNAL_SIZE_T*)mem;
3612   clearsize = csz - SIZE_SZ;
3613   nclears = clearsize / sizeof(INTERNAL_SIZE_T);
3614   assert(nclears >= 3);
3615
3616   if (nclears > 9)
3617     MALLOC_ZERO(d, clearsize);
3618
3619   else {
3620     *(d+0) = 0;
3621     *(d+1) = 0;
3622     *(d+2) = 0;
3623     if (nclears > 4) {
3624       *(d+3) = 0;
3625       *(d+4) = 0;
3626       if (nclears > 6) {
3627         *(d+5) = 0;
3628         *(d+6) = 0;
3629         if (nclears > 8) {
3630           *(d+7) = 0;
3631           *(d+8) = 0;
3632         }
3633       }
3634     }
3635   }
3636
3637   return mem;
3638 }
3639
3640 Void_t**
3641 public_iCALLOc(size_t n, size_t elem_size, Void_t** chunks)
3642 {
3643   mstate ar_ptr;
3644   Void_t** m;
3645
3646   arena_get(ar_ptr, n*elem_size);
3647   if(!ar_ptr)
3648     return 0;
3649
3650   m = _int_icalloc(ar_ptr, n, elem_size, chunks);
3651   (void)mutex_unlock(&ar_ptr->mutex);
3652   return m;
3653 }
3654
3655 Void_t**
3656 public_iCOMALLOc(size_t n, size_t sizes[], Void_t** chunks)
3657 {
3658   mstate ar_ptr;
3659   Void_t** m;
3660
3661   arena_get(ar_ptr, 0);
3662   if(!ar_ptr)
3663     return 0;
3664
3665   m = _int_icomalloc(ar_ptr, n, sizes, chunks);
3666   (void)mutex_unlock(&ar_ptr->mutex);
3667   return m;
3668 }
3669
3670 #ifndef _LIBC
3671
3672 void
3673 public_cFREe(Void_t* m)
3674 {
3675   public_fREe(m);
3676 }
3677
3678 #endif /* _LIBC */
3679
3680 int
3681 public_mTRIm(size_t s)
3682 {
3683   int result;
3684
3685   (void)mutex_lock(&main_arena.mutex);
3686   result = mTRIm(s);
3687   (void)mutex_unlock(&main_arena.mutex);
3688   return result;
3689 }
3690
3691 size_t
3692 public_mUSABLe(Void_t* m)
3693 {
3694   size_t result;
3695
3696   result = mUSABLe(m);
3697   return result;
3698 }
3699
3700 void
3701 public_mSTATs()
3702 {
3703   mSTATs();
3704 }
3705
3706 struct mallinfo public_mALLINFo()
3707 {
3708   struct mallinfo m;
3709
3710   (void)mutex_lock(&main_arena.mutex);
3711   m = mALLINFo(&main_arena);
3712   (void)mutex_unlock(&main_arena.mutex);
3713   return m;
3714 }
3715
3716 int
3717 public_mALLOPt(int p, int v)
3718 {
3719   int result;
3720   result = mALLOPt(p, v);
3721   return result;
3722 }
3723
3724 /*
3725   ------------------------------ malloc ------------------------------
3726 */
3727
3728 static Void_t*
3729 _int_malloc(mstate av, size_t bytes)
3730 {
3731   INTERNAL_SIZE_T nb;               /* normalized request size */
3732   unsigned int    idx;              /* associated bin index */
3733   mbinptr         bin;              /* associated bin */
3734   mfastbinptr*    fb;               /* associated fastbin */
3735
3736   mchunkptr       victim;           /* inspected/selected chunk */
3737   INTERNAL_SIZE_T size;             /* its size */
3738   int             victim_index;     /* its bin index */
3739
3740   mchunkptr       remainder;        /* remainder from a split */
3741   unsigned long   remainder_size;   /* its size */
3742
3743   unsigned int    block;            /* bit map traverser */
3744   unsigned int    bit;              /* bit map traverser */
3745   unsigned int    map;              /* current word of binmap */
3746
3747   mchunkptr       fwd;              /* misc temp for linking */
3748   mchunkptr       bck;              /* misc temp for linking */
3749
3750   /*
3751     Convert request size to internal form by adding SIZE_SZ bytes
3752     overhead plus possibly more to obtain necessary alignment and/or
3753     to obtain a size of at least MINSIZE, the smallest allocatable
3754     size. Also, checked_request2size traps (returning 0) request sizes
3755     that are so large that they wrap around zero when padded and
3756     aligned.
3757   */
3758
3759   checked_request2size(bytes, nb);
3760
3761   /*
3762     If the size qualifies as a fastbin, first check corresponding bin.
3763     This code is safe to execute even if av is not yet initialized, so we
3764     can try it without checking, which saves some time on this fast path.
3765   */
3766
3767   if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) {
3768     fb = &(av->fastbins[(fastbin_index(nb))]);
3769     if ( (victim = *fb) != 0) {
3770       *fb = victim->fd;
3771       check_remalloced_chunk(av, victim, nb);
3772       return chunk2mem(victim);
3773     }
3774   }
3775
3776   /*
3777     If a small request, check regular bin.  Since these "smallbins"
3778     hold one size each, no searching within bins is necessary.
3779     (For a large request, we need to wait until unsorted chunks are
3780     processed to find best fit. But for small ones, fits are exact
3781     anyway, so we can check now, which is faster.)
3782   */
3783
3784   if (in_smallbin_range(nb)) {
3785     idx = smallbin_index(nb);
3786     bin = bin_at(av,idx);
3787
3788     if ( (victim = last(bin)) != bin) {
3789       if (victim == 0) /* initialization check */
3790         malloc_consolidate(av);
3791       else {
3792         bck = victim->bk;
3793         set_inuse_bit_at_offset(victim, nb);
3794         bin->bk = bck;
3795         bck->fd = bin;
3796
3797         if (av != &main_arena)
3798           victim->size |= NON_MAIN_ARENA;
3799         check_malloced_chunk(av, victim, nb);
3800         return chunk2mem(victim);
3801       }
3802     }
3803   }
3804
3805   /*
3806      If this is a large request, consolidate fastbins before continuing.
3807      While it might look excessive to kill all fastbins before
3808      even seeing if there is space available, this avoids
3809      fragmentation problems normally associated with fastbins.
3810      Also, in practice, programs tend to have runs of either small or
3811      large requests, but less often mixtures, so consolidation is not
3812      invoked all that often in most programs. And the programs that
3813      it is called frequently in otherwise tend to fragment.
3814   */
3815
3816   else {
3817     idx = largebin_index(nb);
3818     if (have_fastchunks(av))
3819       malloc_consolidate(av);
3820   }
3821
3822   /*
3823     Process recently freed or remaindered chunks, taking one only if
3824     it is exact fit, or, if this a small request, the chunk is remainder from
3825     the most recent non-exact fit.  Place other traversed chunks in
3826     bins.  Note that this step is the only place in any routine where
3827     chunks are placed in bins.
3828
3829     The outer loop here is needed because we might not realize until
3830     near the end of malloc that we should have consolidated, so must
3831     do so and retry. This happens at most once, and only when we would
3832     otherwise need to expand memory to service a "small" request.
3833   */
3834
3835   for(;;) {
3836
3837     while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
3838       bck = victim->bk;
3839       size = chunksize(victim);
3840
3841       /*
3842          If a small request, try to use last remainder if it is the
3843          only chunk in unsorted bin.  This helps promote locality for
3844          runs of consecutive small requests. This is the only
3845          exception to best-fit, and applies only when there is
3846          no exact fit for a small chunk.
3847       */
3848
3849       if (in_smallbin_range(nb) &&
3850           bck == unsorted_chunks(av) &&
3851           victim == av->last_remainder &&
3852           (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {
3853
3854         /* split and reattach remainder */
3855         remainder_size = size - nb;
3856         remainder = chunk_at_offset(victim, nb);
3857         unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
3858         av->last_remainder = remainder;
3859         remainder->bk = remainder->fd = unsorted_chunks(av);
3860
3861         set_head(victim, nb | PREV_INUSE |
3862                  (av != &main_arena ? NON_MAIN_ARENA : 0));
3863         set_head(remainder, remainder_size | PREV_INUSE);
3864         set_foot(remainder, remainder_size);
3865
3866         check_malloced_chunk(av, victim, nb);
3867         return chunk2mem(victim);
3868       }
3869
3870       /* remove from unsorted list */
3871       unsorted_chunks(av)->bk = bck;
3872       bck->fd = unsorted_chunks(av);
3873
3874       /* Take now instead of binning if exact fit */
3875
3876       if (size == nb) {
3877         set_inuse_bit_at_offset(victim, size);
3878         if (av != &main_arena)
3879           victim->size |= NON_MAIN_ARENA;
3880         check_malloced_chunk(av, victim, nb);
3881         return chunk2mem(victim);
3882       }
3883
3884       /* place chunk in bin */
3885
3886       if (in_smallbin_range(size)) {
3887         victim_index = smallbin_index(size);
3888         bck = bin_at(av, victim_index);
3889         fwd = bck->fd;
3890       }
3891       else {
3892         victim_index = largebin_index(size);
3893         bck = bin_at(av, victim_index);
3894         fwd = bck->fd;
3895
3896         /* maintain large bins in sorted order */
3897         if (fwd != bck) {
3898           /* Or with inuse bit to speed comparisons */
3899           size |= PREV_INUSE;
3900           /* if smaller than smallest, bypass loop below */
3901           assert((bck->bk->size & NON_MAIN_ARENA) == 0);
3902           if ((unsigned long)(size) <= (unsigned long)(bck->bk->size)) {
3903             fwd = bck;
3904             bck = bck->bk;
3905           }
3906           else {
3907             assert((fwd->size & NON_MAIN_ARENA) == 0);
3908             while ((unsigned long)(size) < (unsigned long)(fwd->size)) {
3909               fwd = fwd->fd;
3910               assert((fwd->size & NON_MAIN_ARENA) == 0);
3911             }
3912             bck = fwd->bk;
3913           }
3914         }
3915       }
3916
3917       mark_bin(av, victim_index);
3918       victim->bk = bck;
3919       victim->fd = fwd;
3920       fwd->bk = victim;
3921       bck->fd = victim;
3922     }
3923
3924     /*
3925       If a large request, scan through the chunks of current bin in
3926       sorted order to find smallest that fits.  This is the only step
3927       where an unbounded number of chunks might be scanned without doing
3928       anything useful with them. However the lists tend to be short.
3929     */
3930
3931     if (!in_smallbin_range(nb)) {
3932       bin = bin_at(av, idx);
3933
3934       /* skip scan if empty or largest chunk is too small */
3935       if ((victim = last(bin)) != bin &&
3936           (unsigned long)(first(bin)->size) >= (unsigned long)(nb)) {
3937
3938         while (((unsigned long)(size = chunksize(victim)) <
3939                 (unsigned long)(nb)))
3940           victim = victim->bk;
3941
3942         remainder_size = size - nb;
3943         unlink(victim, bck, fwd);
3944
3945         /* Exhaust */
3946         if (remainder_size < MINSIZE)  {
3947           set_inuse_bit_at_offset(victim, size);
3948           if (av != &main_arena)
3949             victim->size |= NON_MAIN_ARENA;
3950           check_malloced_chunk(av, victim, nb);
3951           return chunk2mem(victim);
3952         }
3953         /* Split */
3954         else {
3955           remainder = chunk_at_offset(victim, nb);
3956           unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
3957           remainder->bk = remainder->fd = unsorted_chunks(av);
3958           set_head(victim, nb | PREV_INUSE |
3959                    (av != &main_arena ? NON_MAIN_ARENA : 0));
3960           set_head(remainder, remainder_size | PREV_INUSE);
3961           set_foot(remainder, remainder_size);
3962           check_malloced_chunk(av, victim, nb);
3963           return chunk2mem(victim);
3964         }
3965       }
3966     }
3967
3968     /*
3969       Search for a chunk by scanning bins, starting with next largest
3970       bin. This search is strictly by best-fit; i.e., the smallest
3971       (with ties going to approximately the least recently used) chunk
3972       that fits is selected.
3973
3974       The bitmap avoids needing to check that most blocks are nonempty.
3975       The particular case of skipping all bins during warm-up phases
3976       when no chunks have been returned yet is faster than it might look.
3977     */
3978
3979     ++idx;
3980     bin = bin_at(av,idx);
3981     block = idx2block(idx);
3982     map = av->binmap[block];
3983     bit = idx2bit(idx);
3984
3985     for (;;) {
3986
3987       /* Skip rest of block if there are no more set bits in this block.  */
3988       if (bit > map || bit == 0) {
3989         do {
3990           if (++block >= BINMAPSIZE)  /* out of bins */
3991             goto use_top;
3992         } while ( (map = av->binmap[block]) == 0);
3993
3994         bin = bin_at(av, (block << BINMAPSHIFT));
3995         bit = 1;
3996       }
3997
3998       /* Advance to bin with set bit. There must be one. */
3999       while ((bit & map) == 0) {
4000         bin = next_bin(bin);
4001         bit <<= 1;
4002         assert(bit != 0);
4003       }
4004
4005       /* Inspect the bin. It is likely to be non-empty */
4006       victim = last(bin);
4007
4008       /*  If a false alarm (empty bin), clear the bit. */
4009       if (victim == bin) {
4010         av->binmap[block] = map &= ~bit; /* Write through */
4011         bin = next_bin(bin);
4012         bit <<= 1;
4013       }
4014
4015       else {
4016         size = chunksize(victim);
4017
4018         /*  We know the first chunk in this bin is big enough to use. */
4019         assert((unsigned long)(size) >= (unsigned long)(nb));
4020
4021         remainder_size = size - nb;
4022
4023         /* unlink */
4024         bck = victim->bk;
4025         bin->bk = bck;
4026         bck->fd = bin;
4027
4028         /* Exhaust */
4029         if (remainder_size < MINSIZE) {
4030           set_inuse_bit_at_offset(victim, size);
4031           if (av != &main_arena)
4032             victim->size |= NON_MAIN_ARENA;
4033           check_malloced_chunk(av, victim, nb);
4034           return chunk2mem(victim);
4035         }
4036
4037         /* Split */
4038         else {
4039           remainder = chunk_at_offset(victim, nb);
4040
4041           unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
4042           remainder->bk = remainder->fd = unsorted_chunks(av);
4043           /* advertise as last remainder */
4044           if (in_smallbin_range(nb))
4045             av->last_remainder = remainder;
4046
4047           set_head(victim, nb | PREV_INUSE |
4048                    (av != &main_arena ? NON_MAIN_ARENA : 0));
4049           set_head(remainder, remainder_size | PREV_INUSE);
4050           set_foot(remainder, remainder_size);
4051           check_malloced_chunk(av, victim, nb);
4052           return chunk2mem(victim);
4053         }
4054       }
4055     }
4056
4057   use_top:
4058     /*
4059       If large enough, split off the chunk bordering the end of memory
4060       (held in av->top). Note that this is in accord with the best-fit
4061       search rule.  In effect, av->top is treated as larger (and thus
4062       less well fitting) than any other available chunk since it can
4063       be extended to be as large as necessary (up to system
4064       limitations).
4065
4066       We require that av->top always exists (i.e., has size >=
4067       MINSIZE) after initialization, so if it would otherwise be
4068       exhuasted by current request, it is replenished. (The main
4069       reason for ensuring it exists is that we may need MINSIZE space
4070       to put in fenceposts in sysmalloc.)
4071     */
4072
4073     victim = av->top;
4074     size = chunksize(victim);
4075
4076     if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {
4077       remainder_size = size - nb;
4078       remainder = chunk_at_offset(victim, nb);
4079       av->top = remainder;
4080       set_head(victim, nb | PREV_INUSE |
4081                (av != &main_arena ? NON_MAIN_ARENA : 0));
4082       set_head(remainder, remainder_size | PREV_INUSE);
4083
4084       check_malloced_chunk(av, victim, nb);
4085       return chunk2mem(victim);
4086     }
4087
4088     /*
4089       If there is space available in fastbins, consolidate and retry,
4090       to possibly avoid expanding memory. This can occur only if nb is
4091       in smallbin range so we didn't consolidate upon entry.
4092     */
4093
4094     else if (have_fastchunks(av)) {
4095       assert(in_smallbin_range(nb));
4096       malloc_consolidate(av);
4097       idx = smallbin_index(nb); /* restore original bin index */
4098     }
4099
4100     /*
4101        Otherwise, relay to handle system-dependent cases
4102     */
4103     else
4104       return sYSMALLOc(nb, av);
4105   }
4106 }
4107
4108 /*
4109   ------------------------------ free ------------------------------
4110 */
4111
4112 static void
4113 _int_free(mstate av, Void_t* mem)
4114 {
4115   mchunkptr       p;           /* chunk corresponding to mem */
4116   INTERNAL_SIZE_T size;        /* its size */
4117   mfastbinptr*    fb;          /* associated fastbin */
4118   mchunkptr       nextchunk;   /* next contiguous chunk */
4119   INTERNAL_SIZE_T nextsize;    /* its size */
4120   int             nextinuse;   /* true if nextchunk is used */
4121   INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
4122   mchunkptr       bck;         /* misc temp for linking */
4123   mchunkptr       fwd;         /* misc temp for linking */
4124
4125
4126   /* free(0) has no effect */
4127   if (mem != 0) {
4128     p = mem2chunk(mem);
4129     size = chunksize(p);
4130
4131     check_inuse_chunk(av, p);
4132
4133     /*
4134       If eligible, place chunk on a fastbin so it can be found
4135       and used quickly in malloc.
4136     */
4137
4138     if ((unsigned long)(size) <= (unsigned long)(av->max_fast)
4139
4140 #if TRIM_FASTBINS
4141         /*
4142            If TRIM_FASTBINS set, don't place chunks
4143            bordering top into fastbins
4144         */
4145         && (chunk_at_offset(p, size) != av->top)
4146 #endif
4147         ) {
4148
4149       set_fastchunks(av);
4150       fb = &(av->fastbins[fastbin_index(size)]);
4151       p->fd = *fb;
4152       *fb = p;
4153     }
4154
4155     /*
4156        Consolidate other non-mmapped chunks as they arrive.
4157     */
4158
4159     else if (!chunk_is_mmapped(p)) {
4160       nextchunk = chunk_at_offset(p, size);
4161       nextsize = chunksize(nextchunk);
4162       assert(nextsize > 0);
4163
4164       /* consolidate backward */
4165       if (!prev_inuse(p)) {
4166         prevsize = p->prev_size;
4167         size += prevsize;
4168         p = chunk_at_offset(p, -((long) prevsize));
4169         unlink(p, bck, fwd);
4170       }
4171
4172       if (nextchunk != av->top) {
4173         /* get and clear inuse bit */
4174         nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4175
4176         /* consolidate forward */
4177         if (!nextinuse) {
4178           unlink(nextchunk, bck, fwd);
4179           size += nextsize;
4180         } else
4181           clear_inuse_bit_at_offset(nextchunk, 0);
4182
4183         /*
4184           Place the chunk in unsorted chunk list. Chunks are
4185           not placed into regular bins until after they have
4186           been given one chance to be used in malloc.
4187         */
4188
4189         bck = unsorted_chunks(av);
4190         fwd = bck->fd;
4191         p->bk = bck;
4192         p->fd = fwd;
4193         bck->fd = p;
4194         fwd->bk = p;
4195
4196         set_head(p, size | PREV_INUSE);
4197         set_foot(p, size);
4198
4199         check_free_chunk(av, p);
4200       }
4201
4202       /*
4203          If the chunk borders the current high end of memory,
4204          consolidate into top
4205       */
4206
4207       else {
4208         size += nextsize;
4209         set_head(p, size | PREV_INUSE);
4210         av->top = p;
4211         check_chunk(av, p);
4212       }
4213
4214       /*
4215         If freeing a large space, consolidate possibly-surrounding
4216         chunks. Then, if the total unused topmost memory exceeds trim
4217         threshold, ask malloc_trim to reduce top.
4218
4219         Unless max_fast is 0, we don't know if there are fastbins
4220         bordering top, so we cannot tell for sure whether threshold
4221         has been reached unless fastbins are consolidated.  But we
4222         don't want to consolidate on each free.  As a compromise,
4223         consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4224         is reached.
4225       */
4226
4227       if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
4228         if (have_fastchunks(av))
4229           malloc_consolidate(av);
4230
4231         if (av == &main_arena) {
4232 #ifndef MORECORE_CANNOT_TRIM
4233           if ((unsigned long)(chunksize(av->top)) >=
4234               (unsigned long)(mp_.trim_threshold))
4235             sYSTRIm(mp_.top_pad, av);
4236 #endif
4237         } else {
4238           /* Always try heap_trim(), even if the top chunk is not
4239              large, because the corresponding heap might go away.  */
4240           heap_info *heap = heap_for_ptr(top(av));
4241
4242           assert(heap->ar_ptr == av);
4243           heap_trim(heap, mp_.top_pad);
4244         }
4245       }
4246
4247     }
4248     /*
4249       If the chunk was allocated via mmap, release via munmap(). Note
4250       that if HAVE_MMAP is false but chunk_is_mmapped is true, then
4251       user must have overwritten memory. There's nothing we can do to
4252       catch this error unless MALLOC_DEBUG is set, in which case
4253       check_inuse_chunk (above) will have triggered error.
4254     */
4255
4256     else {
4257 #if HAVE_MMAP
4258       int ret;
4259       INTERNAL_SIZE_T offset = p->prev_size;
4260       mp_.n_mmaps--;
4261       mp_.mmapped_mem -= (size + offset);
4262       ret = munmap((char*)p - offset, size + offset);
4263       /* munmap returns non-zero on failure */
4264       assert(ret == 0);
4265 #endif
4266     }
4267   }
4268 }
4269
4270 /*
4271   ------------------------- malloc_consolidate -------------------------
4272
4273   malloc_consolidate is a specialized version of free() that tears
4274   down chunks held in fastbins.  Free itself cannot be used for this
4275   purpose since, among other things, it might place chunks back onto
4276   fastbins.  So, instead, we need to use a minor variant of the same
4277   code.
4278
4279   Also, because this routine needs to be called the first time through
4280   malloc anyway, it turns out to be the perfect place to trigger
4281   initialization code.
4282 */
4283
4284 #if __STD_C
4285 static void malloc_consolidate(mstate av)
4286 #else
4287 static void malloc_consolidate(av) mstate av;
4288 #endif
4289 {
4290   mfastbinptr*    fb;                 /* current fastbin being consolidated */
4291   mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
4292   mchunkptr       p;                  /* current chunk being consolidated */
4293   mchunkptr       nextp;              /* next chunk to consolidate */
4294   mchunkptr       unsorted_bin;       /* bin header */
4295   mchunkptr       first_unsorted;     /* chunk to link to */
4296
4297   /* These have same use as in free() */
4298   mchunkptr       nextchunk;
4299   INTERNAL_SIZE_T size;
4300   INTERNAL_SIZE_T nextsize;
4301   INTERNAL_SIZE_T prevsize;
4302   int             nextinuse;
4303   mchunkptr       bck;
4304   mchunkptr       fwd;
4305
4306   /*
4307     If max_fast is 0, we know that av hasn't
4308     yet been initialized, in which case do so below
4309   */
4310
4311   if (av->max_fast != 0) {
4312     clear_fastchunks(av);
4313
4314     unsorted_bin = unsorted_chunks(av);
4315
4316     /*
4317       Remove each chunk from fast bin and consolidate it, placing it
4318       then in unsorted bin. Among other reasons for doing this,
4319       placing in unsorted bin avoids needing to calculate actual bins
4320       until malloc is sure that chunks aren't immediately going to be
4321       reused anyway.
4322     */
4323