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