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