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