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