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