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