(get_myaddress): Avoid loopback interfaces, return loopback address
[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-pt3 Thu Feb 20 1997
23
24   This work is mainly derived from malloc-2.6.4 by Doug Lea
25   <dl@cs.oswego.edu>, which is available from:
26
27                  ftp://g.oswego.edu/pub/misc/malloc.c
28
29   Most of the original comments are reproduced in the code below.
30
31 * Why use this malloc?
32
33   This is not the fastest, most space-conserving, most portable, or
34   most tunable malloc ever written. However it is among the fastest
35   while also being among the most space-conserving, portable and tunable.
36   Consistent balance across these factors results in a good general-purpose
37   allocator. For a high-level description, see
38      http://g.oswego.edu/dl/html/malloc.html
39
40   On many systems, the standard malloc implementation is by itself not
41   thread-safe, and therefore wrapped with a single global lock around
42   all malloc-related functions.  In some applications, especially with
43   multiple available processors, this can lead to contention problems
44   and bad performance.  This malloc version was designed with the goal
45   to avoid waiting for locks as much as possible.  Statistics indicate
46   that this goal is achieved in many cases.
47
48 * Synopsis of public routines
49
50   (Much fuller descriptions are contained in the program documentation below.)
51
52   ptmalloc_init();
53      Initialize global configuration.  When compiled for multiple threads,
54      this function must be called once before any other function in the
55      package.  It is not required otherwise.  It is called automatically
56      in the Linux/GNU C libray or when compiling with MALLOC_HOOKS.
57   malloc(size_t n);
58      Return a pointer to a newly allocated chunk of at least n bytes, or null
59      if no space is available.
60   free(Void_t* p);
61      Release the chunk of memory pointed to by p, or no effect if p is null.
62   realloc(Void_t* p, size_t n);
63      Return a pointer to a chunk of size n that contains the same data
64      as does chunk p up to the minimum of (n, p's size) bytes, or null
65      if no space is available. The returned pointer may or may not be
66      the same as p. If p is null, equivalent to malloc.  Unless the
67      #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a
68      size argument of zero (re)allocates a minimum-sized chunk.
69   memalign(size_t alignment, size_t n);
70      Return a pointer to a newly allocated chunk of n bytes, aligned
71      in accord with the alignment argument, which must be a power of
72      two.
73   valloc(size_t n);
74      Equivalent to memalign(pagesize, n), where pagesize is the page
75      size of the system (or as near to this as can be figured out from
76      all the includes/defines below.)
77   pvalloc(size_t n);
78      Equivalent to valloc(minimum-page-that-holds(n)), that is,
79      round up n to nearest pagesize.
80   calloc(size_t unit, size_t quantity);
81      Returns a pointer to quantity * unit bytes, with all locations
82      set to zero.
83   cfree(Void_t* p);
84      Equivalent to free(p).
85   malloc_trim(size_t pad);
86      Release all but pad bytes of freed top-most memory back
87      to the system. Return 1 if successful, else 0.
88   malloc_usable_size(Void_t* p);
89      Report the number usable allocated bytes associated with allocated
90      chunk p. This may or may not report more bytes than were requested,
91      due to alignment and minimum size constraints.
92   malloc_stats();
93      Prints brief summary statistics on stderr.
94   mallinfo()
95      Returns (by copy) a struct containing various summary statistics.
96   mallopt(int parameter_number, int parameter_value)
97      Changes one of the tunable parameters described below. Returns
98      1 if successful in changing the parameter, else 0.
99
100 * Vital statistics:
101
102   Alignment:                            8-byte
103        8 byte alignment is currently hardwired into the design.  This
104        seems to suffice for all current machines and C compilers.
105
106   Assumed pointer representation:       4 or 8 bytes
107        Code for 8-byte pointers is untested by me but has worked
108        reliably by Wolfram Gloger, who contributed most of the
109        changes supporting this.
110
111   Assumed size_t  representation:       4 or 8 bytes
112        Note that size_t is allowed to be 4 bytes even if pointers are 8.
113
114   Minimum overhead per allocated chunk: 4 or 8 bytes
115        Each malloced chunk has a hidden overhead of 4 bytes holding size
116        and status information.
117
118   Minimum allocated size: 4-byte ptrs:  16 bytes    (including 4 overhead)
119                           8-byte ptrs:  24/32 bytes (including, 4/8 overhead)
120
121        When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
122        ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
123        needed; 4 (8) for a trailing size field
124        and 8 (16) bytes for free list pointers. Thus, the minimum
125        allocatable size is 16/24/32 bytes.
126
127        Even a request for zero bytes (i.e., malloc(0)) returns a
128        pointer to something of the minimum allocatable size.
129
130   Maximum allocated size: 4-byte size_t: 2^31 -  8 bytes
131                           8-byte size_t: 2^63 - 16 bytes
132
133        It is assumed that (possibly signed) size_t bit values suffice to
134        represent chunk sizes. `Possibly signed' is due to the fact
135        that `size_t' may be defined on a system as either a signed or
136        an unsigned type. To be conservative, values that would appear
137        as negative numbers are avoided.
138        Requests for sizes with a negative sign bit will return a
139        minimum-sized chunk.
140
141   Maximum overhead wastage per allocated chunk: normally 15 bytes
142
143        Alignment demands, plus the minimum allocatable size restriction
144        make the normal worst-case wastage 15 bytes (i.e., up to 15
145        more bytes will be allocated than were requested in malloc), with
146        two exceptions:
147          1. Because requests for zero bytes allocate non-zero space,
148             the worst case wastage for a request of zero bytes is 24 bytes.
149          2. For requests >= mmap_threshold that are serviced via
150             mmap(), the worst case wastage is 8 bytes plus the remainder
151             from a system page (the minimal mmap unit); typically 4096 bytes.
152
153 * Limitations
154
155     Here are some features that are NOT currently supported
156
157     * No automated mechanism for fully checking that all accesses
158       to malloced memory stay within their bounds.
159     * No support for compaction.
160
161 * Synopsis of compile-time options:
162
163     People have reported using previous versions of this malloc on all
164     versions of Unix, sometimes by tweaking some of the defines
165     below. It has been tested most extensively on Solaris and
166     Linux. People have also reported adapting this malloc for use in
167     stand-alone embedded systems.
168
169     The implementation is in straight, hand-tuned ANSI C.  Among other
170     consequences, it uses a lot of macros.  Because of this, to be at
171     all usable, this code should be compiled using an optimizing compiler
172     (for example gcc -O2) that can simplify expressions and control
173     paths.
174
175   __STD_C                  (default: derived from C compiler defines)
176      Nonzero if using ANSI-standard C compiler, a C++ compiler, or
177      a C compiler sufficiently close to ANSI to get away with it.
178   MALLOC_DEBUG             (default: NOT defined)
179      Define to enable debugging. Adds fairly extensive assertion-based
180      checking to help track down memory errors, but noticeably slows down
181      execution.
182   MALLOC_HOOKS             (default: NOT defined)
183      Define to enable support run-time replacement of the allocation
184      functions through user-defined `hooks'.
185   REALLOC_ZERO_BYTES_FREES (default: NOT defined)
186      Define this if you think that realloc(p, 0) should be equivalent
187      to free(p). Otherwise, since malloc returns a unique pointer for
188      malloc(0), so does realloc(p, 0).
189   HAVE_MEMCPY               (default: defined)
190      Define if you are not otherwise using ANSI STD C, but still
191      have memcpy and memset in your C library and want to use them.
192      Otherwise, simple internal versions are supplied.
193   USE_MEMCPY               (default: 1 if HAVE_MEMCPY is defined, 0 otherwise)
194      Define as 1 if you want the C library versions of memset and
195      memcpy called in realloc and calloc (otherwise macro versions are used).
196      At least on some platforms, the simple macro versions usually
197      outperform libc versions.
198   HAVE_MMAP                 (default: defined as 1)
199      Define to non-zero to optionally make malloc() use mmap() to
200      allocate very large blocks.
201   HAVE_MREMAP                 (default: defined as 0 unless Linux libc set)
202      Define to non-zero to optionally make realloc() use mremap() to
203      reallocate very large blocks.
204   malloc_getpagesize        (default: derived from system #includes)
205      Either a constant or routine call returning the system page size.
206   HAVE_USR_INCLUDE_MALLOC_H (default: NOT defined)
207      Optionally define if you are on a system with a /usr/include/malloc.h
208      that declares struct mallinfo. It is not at all necessary to
209      define this even if you do, but will ensure consistency.
210   INTERNAL_SIZE_T           (default: size_t)
211      Define to a 32-bit type (probably `unsigned int') if you are on a
212      64-bit machine, yet do not want or need to allow malloc requests of
213      greater than 2^31 to be handled. This saves space, especially for
214      very small chunks.
215   _LIBC                     (default: NOT defined)
216      Defined only when compiled as part of the Linux libc/glibc.
217      Also note that there is some odd internal name-mangling via defines
218      (for example, internally, `malloc' is named `mALLOc') needed
219      when compiling in this case. These look funny but don't otherwise
220      affect anything.
221   LACKS_UNISTD_H            (default: undefined)
222      Define this if your system does not have a <unistd.h>.
223   MORECORE                  (default: sbrk)
224      The name of the routine to call to obtain more memory from the system.
225   MORECORE_FAILURE          (default: -1)
226      The value returned upon failure of MORECORE.
227   MORECORE_CLEARS           (default 1)
228      True (1) if the routine mapped to MORECORE zeroes out memory (which
229      holds for sbrk).
230   DEFAULT_TRIM_THRESHOLD
231   DEFAULT_TOP_PAD
232   DEFAULT_MMAP_THRESHOLD
233   DEFAULT_MMAP_MAX
234      Default values of tunable parameters (described in detail below)
235      controlling interaction with host system routines (sbrk, mmap, etc).
236      These values may also be changed dynamically via mallopt(). The
237      preset defaults are those that give best performance for typical
238      programs/systems.
239   DEFAULT_CHECK_ACTION
240      When the standard debugging hooks are in place, and a pointer is
241      detected as corrupt, do nothing (0), print an error message (1),
242      or call abort() (2).
243
244
245 */
246
247 /*
248
249 * Compile-time options for multiple threads:
250
251   USE_PTHREADS, USE_THR, USE_SPROC
252      Define one of these as 1 to select the thread interface:
253      POSIX threads, Solaris threads or SGI sproc's, respectively.
254      If none of these is defined as non-zero, you get a `normal'
255      malloc implementation which is not thread-safe.  Support for
256      multiple threads requires HAVE_MMAP=1.  As an exception, when
257      compiling for GNU libc, i.e. when _LIBC is defined, then none of
258      the USE_... symbols have to be defined.
259
260   HEAP_MIN_SIZE
261   HEAP_MAX_SIZE
262      When thread support is enabled, additional `heap's are created
263      with mmap calls.  These are limited in size; HEAP_MIN_SIZE should
264      be a multiple of the page size, while HEAP_MAX_SIZE must be a power
265      of two for alignment reasons.  HEAP_MAX_SIZE should be at least
266      twice as large as the mmap threshold.
267   THREAD_STATS
268      When this is defined as non-zero, some statistics on mutex locking
269      are computed.
270
271 */
272
273 \f
274
275
276 /* Preliminaries */
277
278 #ifndef __STD_C
279 #if defined (__STDC__)
280 #define __STD_C     1
281 #else
282 #if __cplusplus
283 #define __STD_C     1
284 #else
285 #define __STD_C     0
286 #endif /*__cplusplus*/
287 #endif /*__STDC__*/
288 #endif /*__STD_C*/
289
290 #ifndef Void_t
291 #if __STD_C
292 #define Void_t      void
293 #else
294 #define Void_t      char
295 #endif
296 #endif /*Void_t*/
297
298 #if __STD_C
299 # include <stddef.h>   /* for size_t */
300 # if defined(_LIBC) || defined(MALLOC_HOOKS)
301 #  include <stdlib.h>  /* for getenv(), abort() */
302 # endif
303 #else
304 # include <sys/types.h>
305 #endif
306
307 /* Macros for handling mutexes and thread-specific data.  This is
308    included early, because some thread-related header files (such as
309    pthread.h) should be included before any others. */
310 #include "thread-m.h"
311
312 #ifdef __cplusplus
313 extern "C" {
314 #endif
315
316 #include <stdio.h>    /* needed for malloc_stats */
317
318
319 /*
320   Compile-time options
321 */
322
323
324 /*
325     Debugging:
326
327     Because freed chunks may be overwritten with link fields, this
328     malloc will often die when freed memory is overwritten by user
329     programs.  This can be very effective (albeit in an annoying way)
330     in helping track down dangling pointers.
331
332     If you compile with -DMALLOC_DEBUG, a number of assertion checks are
333     enabled that will catch more memory errors. You probably won't be
334     able to make much sense of the actual assertion errors, but they
335     should help you locate incorrectly overwritten memory.  The
336     checking is fairly extensive, and will slow down execution
337     noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set will
338     attempt to check every non-mmapped allocated and free chunk in the
339     course of computing the summaries. (By nature, mmapped regions
340     cannot be checked very much automatically.)
341
342     Setting MALLOC_DEBUG may also be helpful if you are trying to modify
343     this code. The assertions in the check routines spell out in more
344     detail the assumptions and invariants underlying the algorithms.
345
346 */
347
348 #if MALLOC_DEBUG
349 #include <assert.h>
350 #else
351 #define assert(x) ((void)0)
352 #endif
353
354
355 /*
356   INTERNAL_SIZE_T is the word-size used for internal bookkeeping
357   of chunk sizes. On a 64-bit machine, you can reduce malloc
358   overhead by defining INTERNAL_SIZE_T to be a 32 bit `unsigned int'
359   at the expense of not being able to handle requests greater than
360   2^31. This limitation is hardly ever a concern; you are encouraged
361   to set this. However, the default version is the same as size_t.
362 */
363
364 #ifndef INTERNAL_SIZE_T
365 #define INTERNAL_SIZE_T size_t
366 #endif
367
368 /*
369   REALLOC_ZERO_BYTES_FREES should be set if a call to
370   realloc with zero bytes should be the same as a call to free.
371   Some people think it should. Otherwise, since this malloc
372   returns a unique pointer for malloc(0), so does realloc(p, 0).
373 */
374
375
376 /*   #define REALLOC_ZERO_BYTES_FREES */
377
378
379 /*
380   HAVE_MEMCPY should be defined if you are not otherwise using
381   ANSI STD C, but still have memcpy and memset in your C library
382   and want to use them in calloc and realloc. Otherwise simple
383   macro versions are defined here.
384
385   USE_MEMCPY should be defined as 1 if you actually want to
386   have memset and memcpy called. People report that the macro
387   versions are often enough faster than libc versions on many
388   systems that it is better to use them.
389
390 */
391
392 #define HAVE_MEMCPY 1
393
394 #ifndef USE_MEMCPY
395 #ifdef HAVE_MEMCPY
396 #define USE_MEMCPY 1
397 #else
398 #define USE_MEMCPY 0
399 #endif
400 #endif
401
402 #if (__STD_C || defined(HAVE_MEMCPY))
403
404 #if __STD_C
405 void* memset(void*, int, size_t);
406 void* memcpy(void*, const void*, size_t);
407 #else
408 Void_t* memset();
409 Void_t* memcpy();
410 #endif
411 #endif
412
413 #if USE_MEMCPY
414
415 /* The following macros are only invoked with (2n+1)-multiples of
416    INTERNAL_SIZE_T units, with a positive integer n. This is exploited
417    for fast inline execution when n is small. */
418
419 #define MALLOC_ZERO(charp, nbytes)                                            \
420 do {                                                                          \
421   INTERNAL_SIZE_T mzsz = (nbytes);                                            \
422   if(mzsz <= 9*sizeof(mzsz)) {                                                \
423     INTERNAL_SIZE_T* mz = (INTERNAL_SIZE_T*) (charp);                         \
424     if(mzsz >= 5*sizeof(mzsz)) {     *mz++ = 0;                               \
425                                      *mz++ = 0;                               \
426       if(mzsz >= 7*sizeof(mzsz)) {   *mz++ = 0;                               \
427                                      *mz++ = 0;                               \
428         if(mzsz >= 9*sizeof(mzsz)) { *mz++ = 0;                               \
429                                      *mz++ = 0; }}}                           \
430                                      *mz++ = 0;                               \
431                                      *mz++ = 0;                               \
432                                      *mz   = 0;                               \
433   } else memset((charp), 0, mzsz);                                            \
434 } while(0)
435
436 #define MALLOC_COPY(dest,src,nbytes)                                          \
437 do {                                                                          \
438   INTERNAL_SIZE_T mcsz = (nbytes);                                            \
439   if(mcsz <= 9*sizeof(mcsz)) {                                                \
440     INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) (src);                        \
441     INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) (dest);                       \
442     if(mcsz >= 5*sizeof(mcsz)) {     *mcdst++ = *mcsrc++;                     \
443                                      *mcdst++ = *mcsrc++;                     \
444       if(mcsz >= 7*sizeof(mcsz)) {   *mcdst++ = *mcsrc++;                     \
445                                      *mcdst++ = *mcsrc++;                     \
446         if(mcsz >= 9*sizeof(mcsz)) { *mcdst++ = *mcsrc++;                     \
447                                      *mcdst++ = *mcsrc++; }}}                 \
448                                      *mcdst++ = *mcsrc++;                     \
449                                      *mcdst++ = *mcsrc++;                     \
450                                      *mcdst   = *mcsrc  ;                     \
451   } else memcpy(dest, src, mcsz);                                             \
452 } while(0)
453
454 #else /* !USE_MEMCPY */
455
456 /* Use Duff's device for good zeroing/copying performance. */
457
458 #define MALLOC_ZERO(charp, nbytes)                                            \
459 do {                                                                          \
460   INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp);                           \
461   long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn;                         \
462   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
463   switch (mctmp) {                                                            \
464     case 0: for(;;) { *mzp++ = 0;                                             \
465     case 7:           *mzp++ = 0;                                             \
466     case 6:           *mzp++ = 0;                                             \
467     case 5:           *mzp++ = 0;                                             \
468     case 4:           *mzp++ = 0;                                             \
469     case 3:           *mzp++ = 0;                                             \
470     case 2:           *mzp++ = 0;                                             \
471     case 1:           *mzp++ = 0; if(mcn <= 0) break; mcn--; }                \
472   }                                                                           \
473 } while(0)
474
475 #define MALLOC_COPY(dest,src,nbytes)                                          \
476 do {                                                                          \
477   INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src;                            \
478   INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest;                           \
479   long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn;                         \
480   if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
481   switch (mctmp) {                                                            \
482     case 0: for(;;) { *mcdst++ = *mcsrc++;                                    \
483     case 7:           *mcdst++ = *mcsrc++;                                    \
484     case 6:           *mcdst++ = *mcsrc++;                                    \
485     case 5:           *mcdst++ = *mcsrc++;                                    \
486     case 4:           *mcdst++ = *mcsrc++;                                    \
487     case 3:           *mcdst++ = *mcsrc++;                                    \
488     case 2:           *mcdst++ = *mcsrc++;                                    \
489     case 1:           *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; }       \
490   }                                                                           \
491 } while(0)
492
493 #endif
494
495
496 /*
497   Define HAVE_MMAP to optionally make malloc() use mmap() to
498   allocate very large blocks.  These will be returned to the
499   operating system immediately after a free().
500 */
501
502 #ifndef HAVE_MMAP
503 #define HAVE_MMAP 1
504 #endif
505
506 /*
507   Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
508   large blocks.  This is currently only possible on Linux with
509   kernel versions newer than 1.3.77.
510 */
511
512 #ifndef HAVE_MREMAP
513 #define HAVE_MREMAP defined(__linux__)
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 Void_t *(*__morecore)(ptrdiff_t) = __default_morecore;
824
825 #else
826
827 Void_t * __default_morecore ();
828 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 #define mprotect __mprotect
839 #undef malloc_getpagesize
840 #define malloc_getpagesize __getpagesize()
841
842 #else /* _LIBC */
843
844 #if __STD_C
845 extern Void_t*     sbrk(ptrdiff_t);
846 #else
847 extern Void_t*     sbrk();
848 #endif
849
850 #ifndef MORECORE
851 #define MORECORE sbrk
852 #endif
853
854 #ifndef MORECORE_FAILURE
855 #define MORECORE_FAILURE -1
856 #endif
857
858 #ifndef MORECORE_CLEARS
859 #define MORECORE_CLEARS 1
860 #endif
861
862 #endif /* _LIBC */
863
864 #ifdef _LIBC
865
866 #define cALLOc          __libc_calloc
867 #define fREe            __libc_free
868 #define mALLOc          __libc_malloc
869 #define mEMALIGn        __libc_memalign
870 #define rEALLOc         __libc_realloc
871 #define vALLOc          __libc_valloc
872 #define pvALLOc         __libc_pvalloc
873 #define mALLINFo        __libc_mallinfo
874 #define mALLOPt         __libc_mallopt
875 #define mALLOC_STATs    __malloc_stats
876 #define mALLOC_USABLE_SIZe __malloc_usable_size
877 #define mALLOC_TRIm     __malloc_trim
878 #define mALLOC_GET_STATe __malloc_get_state
879 #define mALLOC_SET_STATe __malloc_set_state
880
881 #else
882
883 #define cALLOc          calloc
884 #define fREe            free
885 #define mALLOc          malloc
886 #define mEMALIGn        memalign
887 #define rEALLOc         realloc
888 #define vALLOc          valloc
889 #define pvALLOc         pvalloc
890 #define mALLINFo        mallinfo
891 #define mALLOPt         mallopt
892 #define mALLOC_STATs    malloc_stats
893 #define mALLOC_USABLE_SIZe malloc_usable_size
894 #define mALLOC_TRIm     malloc_trim
895 #define mALLOC_GET_STATe malloc_get_state
896 #define mALLOC_SET_STATe malloc_set_state
897
898 #endif
899
900 /* Public routines */
901
902 #if __STD_C
903
904 #ifndef _LIBC
905 void    ptmalloc_init(void);
906 #endif
907 Void_t* mALLOc(size_t);
908 void    fREe(Void_t*);
909 Void_t* rEALLOc(Void_t*, size_t);
910 Void_t* mEMALIGn(size_t, size_t);
911 Void_t* vALLOc(size_t);
912 Void_t* pvALLOc(size_t);
913 Void_t* cALLOc(size_t, size_t);
914 void    cfree(Void_t*);
915 int     mALLOC_TRIm(size_t);
916 size_t  mALLOC_USABLE_SIZe(Void_t*);
917 void    mALLOC_STATs(void);
918 int     mALLOPt(int, int);
919 struct mallinfo mALLINFo(void);
920 Void_t* mALLOC_GET_STATe(void);
921 int     mALLOC_SET_STATe(Void_t*);
922
923 #else /* !__STD_C */
924
925 #ifndef _LIBC
926 void    ptmalloc_init();
927 #endif
928 Void_t* mALLOc();
929 void    fREe();
930 Void_t* rEALLOc();
931 Void_t* mEMALIGn();
932 Void_t* vALLOc();
933 Void_t* pvALLOc();
934 Void_t* cALLOc();
935 void    cfree();
936 int     mALLOC_TRIm();
937 size_t  mALLOC_USABLE_SIZe();
938 void    mALLOC_STATs();
939 int     mALLOPt();
940 struct mallinfo mALLINFo();
941 Void_t* mALLOC_GET_STATe();
942 int     mALLOC_SET_STATe();
943
944 #endif /* __STD_C */
945
946
947 #ifdef __cplusplus
948 };  /* end of extern "C" */
949 #endif
950
951 #if !defined(NO_THREADS) && !HAVE_MMAP
952 "Can't have threads support without mmap"
953 #endif
954
955
956 /*
957   Type declarations
958 */
959
960
961 struct malloc_chunk
962 {
963   INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
964   INTERNAL_SIZE_T size;      /* Size in bytes, including overhead. */
965   struct malloc_chunk* fd;   /* double links -- used only if free. */
966   struct malloc_chunk* bk;
967 };
968
969 typedef struct malloc_chunk* mchunkptr;
970
971 /*
972
973    malloc_chunk details:
974
975     (The following includes lightly edited explanations by Colin Plumb.)
976
977     Chunks of memory are maintained using a `boundary tag' method as
978     described in e.g., Knuth or Standish.  (See the paper by Paul
979     Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
980     survey of such techniques.)  Sizes of free chunks are stored both
981     in the front of each chunk and at the end.  This makes
982     consolidating fragmented chunks into bigger chunks very fast.  The
983     size fields also hold bits representing whether chunks are free or
984     in use.
985
986     An allocated chunk looks like this:
987
988
989     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
990             |             Size of previous chunk, if allocated            | |
991             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
992             |             Size of chunk, in bytes                         |P|
993       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
994             |             User data starts here...                          .
995             .                                                               .
996             .             (malloc_usable_space() bytes)                     .
997             .                                                               |
998 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
999             |             Size of chunk                                     |
1000             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1001
1002
1003     Where "chunk" is the front of the chunk for the purpose of most of
1004     the malloc code, but "mem" is the pointer that is returned to the
1005     user.  "Nextchunk" is the beginning of the next contiguous chunk.
1006
1007     Chunks always begin on even word boundaries, so the mem portion
1008     (which is returned to the user) is also on an even word boundary, and
1009     thus double-word aligned.
1010
1011     Free chunks are stored in circular doubly-linked lists, and look like this:
1012
1013     chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1014             |             Size of previous chunk                            |
1015             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1016     `head:' |             Size of chunk, in bytes                         |P|
1017       mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1018             |             Forward pointer to next chunk in list             |
1019             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1020             |             Back pointer to previous chunk in list            |
1021             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1022             |             Unused space (may be 0 bytes long)                .
1023             .                                                               .
1024             .                                                               |
1025 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1026     `foot:' |             Size of chunk, in bytes                           |
1027             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1028
1029     The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1030     chunk size (which is always a multiple of two words), is an in-use
1031     bit for the *previous* chunk.  If that bit is *clear*, then the
1032     word before the current chunk size contains the previous chunk
1033     size, and can be used to find the front of the previous chunk.
1034     (The very first chunk allocated always has this bit set,
1035     preventing access to non-existent (or non-owned) memory.)
1036
1037     Note that the `foot' of the current chunk is actually represented
1038     as the prev_size of the NEXT chunk. (This makes it easier to
1039     deal with alignments etc).
1040
1041     The two exceptions to all this are
1042
1043      1. The special chunk `top', which doesn't bother using the
1044         trailing size field since there is no
1045         next contiguous chunk that would have to index off it. (After
1046         initialization, `top' is forced to always exist.  If it would
1047         become less than MINSIZE bytes long, it is replenished via
1048         malloc_extend_top.)
1049
1050      2. Chunks allocated via mmap, which have the second-lowest-order
1051         bit (IS_MMAPPED) set in their size fields.  Because they are
1052         never merged or traversed from any other chunk, they have no
1053         foot size or inuse information.
1054
1055     Available chunks are kept in any of several places (all declared below):
1056
1057     * `av': An array of chunks serving as bin headers for consolidated
1058        chunks. Each bin is doubly linked.  The bins are approximately
1059        proportionally (log) spaced.  There are a lot of these bins
1060        (128). This may look excessive, but works very well in
1061        practice.  All procedures maintain the invariant that no
1062        consolidated chunk physically borders another one. Chunks in
1063        bins are kept in size order, with ties going to the
1064        approximately least recently used chunk.
1065
1066        The chunks in each bin are maintained in decreasing sorted order by
1067        size.  This is irrelevant for the small bins, which all contain
1068        the same-sized chunks, but facilitates best-fit allocation for
1069        larger chunks. (These lists are just sequential. Keeping them in
1070        order almost never requires enough traversal to warrant using
1071        fancier ordered data structures.)  Chunks of the same size are
1072        linked with the most recently freed at the front, and allocations
1073        are taken from the back.  This results in LRU or FIFO allocation
1074        order, which tends to give each chunk an equal opportunity to be
1075        consolidated with adjacent freed chunks, resulting in larger free
1076        chunks and less fragmentation.
1077
1078     * `top': The top-most available chunk (i.e., the one bordering the
1079        end of available memory) is treated specially. It is never
1080        included in any bin, is used only if no other chunk is
1081        available, and is released back to the system if it is very
1082        large (see M_TRIM_THRESHOLD).
1083
1084     * `last_remainder': A bin holding only the remainder of the
1085        most recently split (non-top) chunk. This bin is checked
1086        before other non-fitting chunks, so as to provide better
1087        locality for runs of sequentially allocated chunks.
1088
1089     *  Implicitly, through the host system's memory mapping tables.
1090        If supported, requests greater than a threshold are usually
1091        serviced via calls to mmap, and then later released via munmap.
1092
1093 */
1094
1095 /*
1096    Bins
1097
1098     The bins are an array of pairs of pointers serving as the
1099     heads of (initially empty) doubly-linked lists of chunks, laid out
1100     in a way so that each pair can be treated as if it were in a
1101     malloc_chunk. (This way, the fd/bk offsets for linking bin heads
1102     and chunks are the same).
1103
1104     Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1105     8 bytes apart. Larger bins are approximately logarithmically
1106     spaced. (See the table below.)
1107
1108     Bin layout:
1109
1110     64 bins of size       8
1111     32 bins of size      64
1112     16 bins of size     512
1113      8 bins of size    4096
1114      4 bins of size   32768
1115      2 bins of size  262144
1116      1 bin  of size what's left
1117
1118     There is actually a little bit of slop in the numbers in bin_index
1119     for the sake of speed. This makes no difference elsewhere.
1120
1121     The special chunks `top' and `last_remainder' get their own bins,
1122     (this is implemented via yet more trickery with the av array),
1123     although `top' is never properly linked to its bin since it is
1124     always handled specially.
1125
1126 */
1127
1128 #define NAV             128   /* number of bins */
1129
1130 typedef struct malloc_chunk* mbinptr;
1131
1132 /* An arena is a configuration of malloc_chunks together with an array
1133    of bins.  With multiple threads, it must be locked via a mutex
1134    before changing its data structures.  One or more `heaps' are
1135    associated with each arena, except for the main_arena, which is
1136    associated only with the `main heap', i.e.  the conventional free
1137    store obtained with calls to MORECORE() (usually sbrk).  The `av'
1138    array is never mentioned directly in the code, but instead used via
1139    bin access macros. */
1140
1141 typedef struct _arena {
1142   mbinptr av[2*NAV + 2];
1143   struct _arena *next;
1144   size_t size;
1145 #if THREAD_STATS
1146   long stat_lock_direct, stat_lock_loop, stat_lock_wait;
1147 #endif
1148   mutex_t mutex;
1149 } arena;
1150
1151
1152 /* A heap is a single contiguous memory region holding (coalesceable)
1153    malloc_chunks.  It is allocated with mmap() and always starts at an
1154    address aligned to HEAP_MAX_SIZE.  Not used unless compiling for
1155    multiple threads. */
1156
1157 typedef struct _heap_info {
1158   arena *ar_ptr; /* Arena for this heap. */
1159   struct _heap_info *prev; /* Previous heap. */
1160   size_t size;   /* Current size in bytes. */
1161   size_t pad;    /* Make sure the following data is properly aligned. */
1162 } heap_info;
1163
1164
1165 /*
1166   Static functions (forward declarations)
1167 */
1168
1169 #if __STD_C
1170
1171 static void      chunk_free(arena *ar_ptr, mchunkptr p);
1172 static mchunkptr chunk_alloc(arena *ar_ptr, INTERNAL_SIZE_T size);
1173 static mchunkptr chunk_realloc(arena *ar_ptr, mchunkptr oldp,
1174                                INTERNAL_SIZE_T oldsize, INTERNAL_SIZE_T nb);
1175 static mchunkptr chunk_align(arena *ar_ptr, INTERNAL_SIZE_T nb,
1176                              size_t alignment);
1177 static int       main_trim(size_t pad);
1178 #ifndef NO_THREADS
1179 static int       heap_trim(heap_info *heap, size_t pad);
1180 #endif
1181 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1182 static Void_t*   malloc_check(size_t sz);
1183 static void      free_check(Void_t* mem);
1184 static Void_t*   realloc_check(Void_t* oldmem, size_t bytes);
1185 static Void_t*   memalign_check(size_t alignment, size_t bytes);
1186 static Void_t*   malloc_starter(size_t sz);
1187 static void      free_starter(Void_t* mem);
1188 static Void_t*   malloc_atfork(size_t sz);
1189 static void      free_atfork(Void_t* mem);
1190 #endif
1191
1192 #else
1193
1194 static void      chunk_free();
1195 static mchunkptr chunk_alloc();
1196 static mchunkptr chunk_realloc();
1197 static mchunkptr chunk_align();
1198 static int       main_trim();
1199 #ifndef NO_THREADS
1200 static int       heap_trim();
1201 #endif
1202 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1203 static Void_t*   malloc_check();
1204 static void      free_check();
1205 static Void_t*   realloc_check();
1206 static Void_t*   memalign_check();
1207 static Void_t*   malloc_starter();
1208 static void      free_starter();
1209 static Void_t*   malloc_atfork();
1210 static void      free_atfork();
1211 #endif
1212
1213 #endif
1214
1215 \f
1216
1217 /* sizes, alignments */
1218
1219 #define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
1220 #define MALLOC_ALIGNMENT       (SIZE_SZ + SIZE_SZ)
1221 #define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
1222 #define MINSIZE                (sizeof(struct malloc_chunk))
1223
1224 /* conversion from malloc headers to user pointers, and back */
1225
1226 #define chunk2mem(p)   ((Void_t*)((char*)(p) + 2*SIZE_SZ))
1227 #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1228
1229 /* pad request bytes into a usable size */
1230
1231 #define request2size(req) \
1232  (((long)((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) < \
1233   (long)(MINSIZE + MALLOC_ALIGN_MASK)) ? MINSIZE : \
1234    (((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK)))
1235
1236 /* Check if m has acceptable alignment */
1237
1238 #define aligned_OK(m)    (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1239
1240
1241 \f
1242
1243 /*
1244   Physical chunk operations
1245 */
1246
1247
1248 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1249
1250 #define PREV_INUSE 0x1
1251
1252 /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1253
1254 #define IS_MMAPPED 0x2
1255
1256 /* Bits to mask off when extracting size */
1257
1258 #define SIZE_BITS (PREV_INUSE|IS_MMAPPED)
1259
1260
1261 /* Ptr to next physical malloc_chunk. */
1262
1263 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE) ))
1264
1265 /* Ptr to previous physical malloc_chunk */
1266
1267 #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
1268
1269
1270 /* Treat space at ptr + offset as a chunk */
1271
1272 #define chunk_at_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
1273
1274
1275 \f
1276
1277 /*
1278   Dealing with use bits
1279 */
1280
1281 /* extract p's inuse bit */
1282
1283 #define inuse(p) \
1284  ((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE)
1285
1286 /* extract inuse bit of previous chunk */
1287
1288 #define prev_inuse(p)  ((p)->size & PREV_INUSE)
1289
1290 /* check for mmap()'ed chunk */
1291
1292 #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1293
1294 /* set/clear chunk as in use without otherwise disturbing */
1295
1296 #define set_inuse(p) \
1297  ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size |= PREV_INUSE
1298
1299 #define clear_inuse(p) \
1300  ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size &= ~(PREV_INUSE)
1301
1302 /* check/set/clear inuse bits in known places */
1303
1304 #define inuse_bit_at_offset(p, s)\
1305  (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
1306
1307 #define set_inuse_bit_at_offset(p, s)\
1308  (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)
1309
1310 #define clear_inuse_bit_at_offset(p, s)\
1311  (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
1312
1313
1314 \f
1315
1316 /*
1317   Dealing with size fields
1318 */
1319
1320 /* Get size, ignoring use bits */
1321
1322 #define chunksize(p)          ((p)->size & ~(SIZE_BITS))
1323
1324 /* Set size at head, without disturbing its use bit */
1325
1326 #define set_head_size(p, s)   ((p)->size = (((p)->size & PREV_INUSE) | (s)))
1327
1328 /* Set size/use ignoring previous bits in header */
1329
1330 #define set_head(p, s)        ((p)->size = (s))
1331
1332 /* Set size at footer (only when chunk is not in use) */
1333
1334 #define set_foot(p, s)   (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
1335
1336
1337 \f
1338
1339
1340 /* access macros */
1341
1342 #define bin_at(a, i)   ((mbinptr)((char*)&(((a)->av)[2*(i) + 2]) - 2*SIZE_SZ))
1343 #define init_bin(a, i) ((a)->av[2*i+2] = (a)->av[2*i+3] = bin_at((a), i))
1344 #define next_bin(b)    ((mbinptr)((char*)(b) + 2 * sizeof(mbinptr)))
1345 #define prev_bin(b)    ((mbinptr)((char*)(b) - 2 * sizeof(mbinptr)))
1346
1347 /*
1348    The first 2 bins are never indexed. The corresponding av cells are instead
1349    used for bookkeeping. This is not to save space, but to simplify
1350    indexing, maintain locality, and avoid some initialization tests.
1351 */
1352
1353 #define binblocks(a)      (bin_at(a,0)->size)/* bitvector of nonempty blocks */
1354 #define top(a)            (bin_at(a,0)->fd)  /* The topmost chunk */
1355 #define last_remainder(a) (bin_at(a,1))      /* remainder from last split */
1356
1357 /*
1358    Because top initially points to its own bin with initial
1359    zero size, thus forcing extension on the first malloc request,
1360    we avoid having any special code in malloc to check whether
1361    it even exists yet. But we still need to in malloc_extend_top.
1362 */
1363
1364 #define initial_top(a)    ((mchunkptr)bin_at(a, 0))
1365
1366 \f
1367
1368 /* field-extraction macros */
1369
1370 #define first(b) ((b)->fd)
1371 #define last(b)  ((b)->bk)
1372
1373 /*
1374   Indexing into bins
1375 */
1376
1377 #define bin_index(sz)                                                          \
1378 (((((unsigned long)(sz)) >> 9) ==    0) ?       (((unsigned long)(sz)) >>  3): \
1379  ((((unsigned long)(sz)) >> 9) <=    4) ?  56 + (((unsigned long)(sz)) >>  6): \
1380  ((((unsigned long)(sz)) >> 9) <=   20) ?  91 + (((unsigned long)(sz)) >>  9): \
1381  ((((unsigned long)(sz)) >> 9) <=   84) ? 110 + (((unsigned long)(sz)) >> 12): \
1382  ((((unsigned long)(sz)) >> 9) <=  340) ? 119 + (((unsigned long)(sz)) >> 15): \
1383  ((((unsigned long)(sz)) >> 9) <= 1364) ? 124 + (((unsigned long)(sz)) >> 18): \
1384                                           126)
1385 /*
1386   bins for chunks < 512 are all spaced 8 bytes apart, and hold
1387   identically sized chunks. This is exploited in malloc.
1388 */
1389
1390 #define MAX_SMALLBIN         63
1391 #define MAX_SMALLBIN_SIZE   512
1392 #define SMALLBIN_WIDTH        8
1393
1394 #define smallbin_index(sz)  (((unsigned long)(sz)) >> 3)
1395
1396 /*
1397    Requests are `small' if both the corresponding and the next bin are small
1398 */
1399
1400 #define is_small_request(nb) ((nb) < MAX_SMALLBIN_SIZE - SMALLBIN_WIDTH)
1401
1402 \f
1403
1404 /*
1405     To help compensate for the large number of bins, a one-level index
1406     structure is used for bin-by-bin searching.  `binblocks' is a
1407     one-word bitvector recording whether groups of BINBLOCKWIDTH bins
1408     have any (possibly) non-empty bins, so they can be skipped over
1409     all at once during during traversals. The bits are NOT always
1410     cleared as soon as all bins in a block are empty, but instead only
1411     when all are noticed to be empty during traversal in malloc.
1412 */
1413
1414 #define BINBLOCKWIDTH     4   /* bins per block */
1415
1416 /* bin<->block macros */
1417
1418 #define idx2binblock(ix)      ((unsigned)1 << ((ix) / BINBLOCKWIDTH))
1419 #define mark_binblock(a, ii)  (binblocks(a) |= idx2binblock(ii))
1420 #define clear_binblock(a, ii) (binblocks(a) &= ~(idx2binblock(ii)))
1421
1422
1423 \f
1424
1425 /* Static bookkeeping data */
1426
1427 /* Helper macro to initialize bins */
1428 #define IAV(i) bin_at(&main_arena, i), bin_at(&main_arena, i)
1429
1430 static arena main_arena = {
1431     {
1432  0, 0,
1433  IAV(0),   IAV(1),   IAV(2),   IAV(3),   IAV(4),   IAV(5),   IAV(6),   IAV(7),
1434  IAV(8),   IAV(9),   IAV(10),  IAV(11),  IAV(12),  IAV(13),  IAV(14),  IAV(15),
1435  IAV(16),  IAV(17),  IAV(18),  IAV(19),  IAV(20),  IAV(21),  IAV(22),  IAV(23),
1436  IAV(24),  IAV(25),  IAV(26),  IAV(27),  IAV(28),  IAV(29),  IAV(30),  IAV(31),
1437  IAV(32),  IAV(33),  IAV(34),  IAV(35),  IAV(36),  IAV(37),  IAV(38),  IAV(39),
1438  IAV(40),  IAV(41),  IAV(42),  IAV(43),  IAV(44),  IAV(45),  IAV(46),  IAV(47),
1439  IAV(48),  IAV(49),  IAV(50),  IAV(51),  IAV(52),  IAV(53),  IAV(54),  IAV(55),
1440  IAV(56),  IAV(57),  IAV(58),  IAV(59),  IAV(60),  IAV(61),  IAV(62),  IAV(63),
1441  IAV(64),  IAV(65),  IAV(66),  IAV(67),  IAV(68),  IAV(69),  IAV(70),  IAV(71),
1442  IAV(72),  IAV(73),  IAV(74),  IAV(75),  IAV(76),  IAV(77),  IAV(78),  IAV(79),
1443  IAV(80),  IAV(81),  IAV(82),  IAV(83),  IAV(84),  IAV(85),  IAV(86),  IAV(87),
1444  IAV(88),  IAV(89),  IAV(90),  IAV(91),  IAV(92),  IAV(93),  IAV(94),  IAV(95),
1445  IAV(96),  IAV(97),  IAV(98),  IAV(99),  IAV(100), IAV(101), IAV(102), IAV(103),
1446  IAV(104), IAV(105), IAV(106), IAV(107), IAV(108), IAV(109), IAV(110), IAV(111),
1447  IAV(112), IAV(113), IAV(114), IAV(115), IAV(116), IAV(117), IAV(118), IAV(119),
1448  IAV(120), IAV(121), IAV(122), IAV(123), IAV(124), IAV(125), IAV(126), IAV(127)
1449     },
1450     &main_arena, /* next */
1451     0, /* size */
1452 #if THREAD_STATS
1453     0, 0, 0, /* stat_lock_direct, stat_lock_loop, stat_lock_wait */
1454 #endif
1455     MUTEX_INITIALIZER /* mutex */
1456 };
1457
1458 #undef IAV
1459
1460 /* Thread specific data */
1461
1462 #ifndef NO_THREADS
1463 static tsd_key_t arena_key;
1464 static mutex_t list_lock = MUTEX_INITIALIZER;
1465 #endif
1466
1467 #if THREAD_STATS
1468 static int stat_n_heaps = 0;
1469 #define THREAD_STAT(x) x
1470 #else
1471 #define THREAD_STAT(x) do ; while(0)
1472 #endif
1473
1474 /* variables holding tunable values */
1475
1476 static unsigned long trim_threshold   = DEFAULT_TRIM_THRESHOLD;
1477 static unsigned long top_pad          = DEFAULT_TOP_PAD;
1478 static unsigned int  n_mmaps_max      = DEFAULT_MMAP_MAX;
1479 static unsigned long mmap_threshold   = DEFAULT_MMAP_THRESHOLD;
1480 static int           check_action     = DEFAULT_CHECK_ACTION;
1481
1482 /* The first value returned from sbrk */
1483 static char* sbrk_base = (char*)(-1);
1484
1485 /* The maximum memory obtained from system via sbrk */
1486 static unsigned long max_sbrked_mem = 0;
1487
1488 /* The maximum via either sbrk or mmap (too difficult to track with threads) */
1489 #ifdef NO_THREADS
1490 static unsigned long max_total_mem = 0;
1491 #endif
1492
1493 /* The total memory obtained from system via sbrk */
1494 #define sbrked_mem (main_arena.size)
1495
1496 /* Tracking mmaps */
1497
1498 static unsigned int n_mmaps = 0;
1499 static unsigned int max_n_mmaps = 0;
1500 static unsigned long mmapped_mem = 0;
1501 static unsigned long max_mmapped_mem = 0;
1502
1503
1504 \f
1505 #ifndef _LIBC
1506 #define weak_variable
1507 #else
1508 /* In GNU libc we want the hook variables to be weak definitions to
1509    avoid a problem with Emacs.  */
1510 #define weak_variable weak_function
1511 #endif
1512
1513 /* Already initialized? */
1514 int __malloc_initialized = 0;
1515
1516
1517 /* The following two functions are registered via thread_atfork() to
1518    make sure that the mutexes remain in a consistent state in the
1519    fork()ed version of a thread.  Also adapt the malloc and free hooks
1520    temporarily, because the `atfork' handler mechanism may use
1521    malloc/free internally (e.g. in LinuxThreads). */
1522
1523 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1524 static __malloc_ptr_t (*save_malloc_hook) __MALLOC_P ((size_t __size));
1525 static void           (*save_free_hook) __MALLOC_P ((__malloc_ptr_t __ptr));
1526 static Void_t*        save_arena;
1527 #endif
1528
1529 static void
1530 ptmalloc_lock_all __MALLOC_P((void))
1531 {
1532   arena *ar_ptr;
1533
1534   (void)mutex_lock(&list_lock);
1535   for(ar_ptr = &main_arena;;) {
1536     (void)mutex_lock(&ar_ptr->mutex);
1537     ar_ptr = ar_ptr->next;
1538     if(ar_ptr == &main_arena) break;
1539   }
1540 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1541   save_malloc_hook = __malloc_hook;
1542   save_free_hook = __free_hook;
1543   __malloc_hook = malloc_atfork;
1544   __free_hook = free_atfork;
1545   /* Only the current thread may perform malloc/free calls now. */
1546   tsd_getspecific(arena_key, save_arena);
1547   tsd_setspecific(arena_key, (Void_t*)0);
1548 #endif
1549 }
1550
1551 static void
1552 ptmalloc_unlock_all __MALLOC_P((void))
1553 {
1554   arena *ar_ptr;
1555
1556 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1557   tsd_setspecific(arena_key, save_arena);
1558   __malloc_hook = save_malloc_hook;
1559   __free_hook = save_free_hook;
1560 #endif
1561   for(ar_ptr = &main_arena;;) {
1562     (void)mutex_unlock(&ar_ptr->mutex);
1563     ar_ptr = ar_ptr->next;
1564     if(ar_ptr == &main_arena) break;
1565   }
1566   (void)mutex_unlock(&list_lock);
1567 }
1568
1569 /* Initialization routine. */
1570 #if defined(_LIBC)
1571 #if 0
1572 static void ptmalloc_init __MALLOC_P ((void)) __attribute__ ((constructor));
1573 #endif
1574
1575 static void
1576 ptmalloc_init __MALLOC_P((void))
1577 #else
1578 void
1579 ptmalloc_init __MALLOC_P((void))
1580 #endif
1581 {
1582 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1583   const char* s;
1584 #endif
1585
1586   if(__malloc_initialized) return;
1587   __malloc_initialized = 1;
1588 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1589   /* With some threads implementations, creating thread-specific data
1590      or initializing a mutex may call malloc() itself.  Provide a
1591      simple starter version (realloc() won't work). */
1592   save_malloc_hook = __malloc_hook;
1593   save_free_hook = __free_hook;
1594   __malloc_hook = malloc_starter;
1595   __free_hook = free_starter;
1596 #endif
1597 #if defined(_LIBC) && !defined (NO_THREADS)
1598   /* Initialize the pthreads interface. */
1599   if (__pthread_initialize != NULL)
1600     __pthread_initialize();
1601 #endif
1602 #ifndef NO_THREADS
1603   mutex_init(&main_arena.mutex);
1604   mutex_init(&list_lock);
1605   tsd_key_create(&arena_key, NULL);
1606   tsd_setspecific(arena_key, (Void_t *)&main_arena);
1607   thread_atfork(ptmalloc_lock_all, ptmalloc_unlock_all, ptmalloc_unlock_all);
1608 #endif
1609 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1610   if((s = getenv("MALLOC_TRIM_THRESHOLD_")))
1611     mALLOPt(M_TRIM_THRESHOLD, atoi(s));
1612   if((s = getenv("MALLOC_TOP_PAD_")))
1613     mALLOPt(M_TOP_PAD, atoi(s));
1614   if((s = getenv("MALLOC_MMAP_THRESHOLD_")))
1615     mALLOPt(M_MMAP_THRESHOLD, atoi(s));
1616   if((s = getenv("MALLOC_MMAP_MAX_")))
1617     mALLOPt(M_MMAP_MAX, atoi(s));
1618   s = getenv("MALLOC_CHECK_");
1619   __malloc_hook = save_malloc_hook;
1620   __free_hook = save_free_hook;
1621   if(s) {
1622     if(s[0]) mALLOPt(M_CHECK_ACTION, (int)(s[0] - '0'));
1623     __malloc_check_init();
1624   }
1625   if(__malloc_initialize_hook != NULL)
1626     (*__malloc_initialize_hook)();
1627 #endif
1628 }
1629
1630 /* There are platforms (e.g. Hurd) with a link-time hook mechanism. */
1631 #ifdef thread_atfork_static
1632 thread_atfork_static(ptmalloc_lock_all, ptmalloc_unlock_all, \
1633                      ptmalloc_unlock_all)
1634 #endif
1635
1636 #if defined(_LIBC) || defined(MALLOC_HOOKS)
1637
1638 /* Hooks for debugging versions.  The initial hooks just call the
1639    initialization routine, then do the normal work. */
1640
1641 static Void_t*
1642 #if __STD_C
1643 malloc_hook_ini(size_t sz)
1644 #else
1645 malloc_hook_ini(sz) size_t sz;
1646 #endif
1647 {
1648   __malloc_hook = NULL;
1649   __realloc_hook = NULL;
1650   __memalign_hook = NULL;
1651   ptmalloc_init();
1652   return mALLOc(sz);
1653 }
1654
1655 static Void_t*
1656 #if __STD_C
1657 realloc_hook_ini(Void_t* ptr, size_t sz)
1658 #else
1659 realloc_hook_ini(ptr, sz) Void_t* ptr; size_t sz;
1660 #endif
1661 {
1662   __malloc_hook = NULL;
1663   __realloc_hook = NULL;
1664   __memalign_hook = NULL;
1665   ptmalloc_init();
1666   return rEALLOc(ptr, sz);
1667 }
1668
1669 static Void_t*
1670 #if __STD_C
1671 memalign_hook_ini(size_t sz, size_t alignment)
1672 #else
1673 memalign_hook_ini(sz, alignment) size_t sz; size_t alignment;
1674 #endif
1675 {
1676   __malloc_hook = NULL;
1677   __realloc_hook = NULL;
1678   __memalign_hook = NULL;
1679   ptmalloc_init();
1680   return mEMALIGn(sz, alignment);
1681 }
1682
1683 void weak_variable (*__malloc_initialize_hook) __MALLOC_P ((void)) = NULL;
1684 void weak_variable (*__free_hook) __MALLOC_P ((__malloc_ptr_t __ptr)) = NULL;
1685 __malloc_ptr_t weak_variable (*__malloc_hook)
1686  __MALLOC_P ((size_t __size)) = malloc_hook_ini;
1687 __malloc_ptr_t weak_variable (*__realloc_hook)
1688  __MALLOC_P ((__malloc_ptr_t __ptr, size_t __size)) = realloc_hook_ini;
1689 __malloc_ptr_t weak_variable (*__memalign_hook)
1690  __MALLOC_P ((size_t __size, size_t __alignment)) = memalign_hook_ini;
1691 void weak_variable (*__after_morecore_hook) __MALLOC_P ((void)) = NULL;
1692
1693 /* Activate a standard set of debugging hooks. */
1694 void
1695 __malloc_check_init()
1696 {
1697   __malloc_hook = malloc_check;
1698   __free_hook = free_check;
1699   __realloc_hook = realloc_check;
1700   __memalign_hook = memalign_check;
1701   if(check_action == 1)
1702     fprintf(stderr, "malloc: using debugging hooks\n");
1703 }
1704
1705 #endif
1706
1707
1708 \f
1709
1710
1711 /* Routines dealing with mmap(). */
1712
1713 #if HAVE_MMAP
1714
1715 #ifndef MAP_ANONYMOUS
1716
1717 static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1718
1719 #define MMAP(size, prot) ((dev_zero_fd < 0) ? \
1720  (dev_zero_fd = open("/dev/zero", O_RDWR), \
1721   mmap(0, (size), (prot), MAP_PRIVATE, dev_zero_fd, 0)) : \
1722    mmap(0, (size), (prot), MAP_PRIVATE, dev_zero_fd, 0))
1723
1724 #else
1725
1726 #define MMAP(size, prot) \
1727  (mmap(0, (size), (prot), MAP_PRIVATE|MAP_ANONYMOUS, -1, 0))
1728
1729 #endif
1730
1731 #if __STD_C
1732 static mchunkptr mmap_chunk(size_t size)
1733 #else
1734 static mchunkptr mmap_chunk(size) size_t size;
1735 #endif
1736 {
1737   size_t page_mask = malloc_getpagesize - 1;
1738   mchunkptr p;
1739
1740   if(n_mmaps >= n_mmaps_max) return 0; /* too many regions */
1741
1742   /* For mmapped chunks, the overhead is one SIZE_SZ unit larger, because
1743    * there is no following chunk whose prev_size field could be used.
1744    */
1745   size = (size + SIZE_SZ + page_mask) & ~page_mask;
1746
1747   p = (mchunkptr)MMAP(size, PROT_READ|PROT_WRITE);
1748   if(p == (mchunkptr) MAP_FAILED) return 0;
1749
1750   n_mmaps++;
1751   if (n_mmaps > max_n_mmaps) max_n_mmaps = n_mmaps;
1752
1753   /* We demand that eight bytes into a page must be 8-byte aligned. */
1754   assert(aligned_OK(chunk2mem(p)));
1755
1756   /* The offset to the start of the mmapped region is stored
1757    * in the prev_size field of the chunk; normally it is zero,
1758    * but that can be changed in memalign().
1759    */
1760   p->prev_size = 0;
1761   set_head(p, size|IS_MMAPPED);
1762
1763   mmapped_mem += size;
1764   if ((unsigned long)mmapped_mem > (unsigned long)max_mmapped_mem)
1765     max_mmapped_mem = mmapped_mem;
1766 #ifdef NO_THREADS
1767   if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem)
1768     max_total_mem = mmapped_mem + sbrked_mem;
1769 #endif
1770   return p;
1771 }
1772
1773 #if __STD_C
1774 static void munmap_chunk(mchunkptr p)
1775 #else
1776 static void munmap_chunk(p) mchunkptr p;
1777 #endif
1778 {
1779   INTERNAL_SIZE_T size = chunksize(p);
1780   int ret;
1781
1782   assert (chunk_is_mmapped(p));
1783   assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + sbrked_mem));
1784   assert((n_mmaps > 0));
1785   assert(((p->prev_size + size) & (malloc_getpagesize-1)) == 0);
1786
1787   n_mmaps--;
1788   mmapped_mem -= (size + p->prev_size);
1789
1790   ret = munmap((char *)p - p->prev_size, size + p->prev_size);
1791
1792   /* munmap returns non-zero on failure */
1793   assert(ret == 0);
1794 }
1795
1796 #if HAVE_MREMAP
1797
1798 #if __STD_C
1799 static mchunkptr mremap_chunk(mchunkptr p, size_t new_size)
1800 #else
1801 static mchunkptr mremap_chunk(p, new_size) mchunkptr p; size_t new_size;
1802 #endif
1803 {
1804   size_t page_mask = malloc_getpagesize - 1;
1805   INTERNAL_SIZE_T offset = p->prev_size;
1806   INTERNAL_SIZE_T size = chunksize(p);
1807   char *cp;
1808
1809   assert (chunk_is_mmapped(p));
1810   assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + sbrked_mem));
1811   assert((n_mmaps > 0));
1812   assert(((size + offset) & (malloc_getpagesize-1)) == 0);
1813
1814   /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
1815   new_size = (new_size + offset + SIZE_SZ + page_mask) & ~page_mask;
1816
1817   cp = (char *)mremap((char *)p - offset, size + offset, new_size,
1818                       MREMAP_MAYMOVE);
1819
1820   if (cp == (char *)-1) return 0;
1821
1822   p = (mchunkptr)(cp + offset);
1823
1824   assert(aligned_OK(chunk2mem(p)));
1825
1826   assert((p->prev_size == offset));
1827   set_head(p, (new_size - offset)|IS_MMAPPED);
1828
1829   mmapped_mem -= size + offset;
1830   mmapped_mem += new_size;
1831   if ((unsigned long)mmapped_mem > (unsigned long)max_mmapped_mem)
1832     max_mmapped_mem = mmapped_mem;
1833 #ifdef NO_THREADS
1834   if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem)
1835     max_total_mem = mmapped_mem + sbrked_mem;
1836 #endif
1837   return p;
1838 }
1839
1840 #endif /* HAVE_MREMAP */
1841
1842 #endif /* HAVE_MMAP */
1843
1844 \f
1845
1846 /* Managing heaps and arenas (for concurrent threads) */
1847
1848 #ifndef NO_THREADS
1849
1850 /* Create a new heap.  size is automatically rounded up to a multiple
1851    of the page size. */
1852
1853 static heap_info *
1854 #if __STD_C
1855 new_heap(size_t size)
1856 #else
1857 new_heap(size) size_t size;
1858 #endif
1859 {
1860   size_t page_mask = malloc_getpagesize - 1;
1861   char *p1, *p2;
1862   unsigned long ul;
1863   heap_info *h;
1864
1865   if(size+top_pad < HEAP_MIN_SIZE)
1866     size = HEAP_MIN_SIZE;
1867   else if(size+top_pad <= HEAP_MAX_SIZE)
1868     size += top_pad;
1869   else if(size > HEAP_MAX_SIZE)
1870     return 0;
1871   else
1872     size = HEAP_MAX_SIZE;
1873   size = (size + page_mask) & ~page_mask;
1874
1875   p1 = (char *)MMAP(HEAP_MAX_SIZE<<1, PROT_NONE);
1876   if(p1 == MAP_FAILED)
1877     return 0;
1878   p2 = (char *)(((unsigned long)p1 + HEAP_MAX_SIZE) & ~(HEAP_MAX_SIZE-1));
1879   ul = p2 - p1;
1880   munmap(p1, ul);
1881   munmap(p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul);
1882   if(mprotect(p2, size, PROT_READ|PROT_WRITE) != 0) {
1883     munmap(p2, HEAP_MAX_SIZE);
1884     return 0;
1885   }
1886   h = (heap_info *)p2;
1887   h->size = size;
1888   THREAD_STAT(stat_n_heaps++);
1889   return h;
1890 }
1891
1892 /* Grow or shrink a heap.  size is automatically rounded up to a
1893    multiple of the page size if it is positive. */
1894
1895 static int
1896 #if __STD_C
1897 grow_heap(heap_info *h, long diff)
1898 #else
1899 grow_heap(h, diff) heap_info *h; long diff;
1900 #endif
1901 {
1902   size_t page_mask = malloc_getpagesize - 1;
1903   long new_size;
1904
1905   if(diff >= 0) {
1906     diff = (diff + page_mask) & ~page_mask;
1907     new_size = (long)h->size + diff;
1908     if(new_size > HEAP_MAX_SIZE)
1909       return -1;
1910     if(mprotect((char *)h + h->size, diff, PROT_READ|PROT_WRITE) != 0)
1911       return -2;
1912   } else {
1913     new_size = (long)h->size + diff;
1914     if(new_size < (long)sizeof(*h))
1915       return -1;
1916     if(mprotect((char *)h + new_size, -diff, PROT_NONE) != 0)
1917       return -2;
1918   }
1919   h->size = new_size;
1920   return 0;
1921 }
1922
1923 /* Delete a heap. */
1924
1925 #define delete_heap(heap) munmap((char*)(heap), HEAP_MAX_SIZE)
1926
1927 /* arena_get() acquires an arena and locks the corresponding mutex.
1928    First, try the one last locked successfully by this thread.  (This
1929    is the common case and handled with a macro for speed.)  Then, loop
1930    once over the circularly linked list of arenas.  If no arena is
1931    readily available, create a new one. */
1932
1933 #define arena_get(ptr, size) do { \
1934   Void_t *vptr = NULL; \
1935   ptr = (arena *)tsd_getspecific(arena_key, vptr); \
1936   if(ptr && !mutex_trylock(&ptr->mutex)) { \
1937     THREAD_STAT(++(ptr->stat_lock_direct)); \
1938   } else \
1939     ptr = arena_get2(ptr, (size)); \
1940 } while(0)
1941
1942 static arena *
1943 #if __STD_C
1944 arena_get2(arena *a_tsd, size_t size)
1945 #else
1946 arena_get2(a_tsd, size) arena *a_tsd; size_t size;
1947 #endif
1948 {
1949   arena *a;
1950   heap_info *h;
1951   char *ptr;
1952   int i;
1953   unsigned long misalign;
1954
1955   if(!a_tsd)
1956     a = a_tsd = &main_arena;
1957   else {
1958     a = a_tsd->next;
1959     if(!a) {
1960       /* This can only happen while initializing the new arena. */
1961       (void)mutex_lock(&main_arena.mutex);
1962       THREAD_STAT(++(main_arena.stat_lock_wait));
1963       return &main_arena;
1964     }
1965   }
1966
1967   /* Check the global, circularly linked list for available arenas. */
1968   do {
1969     if(!mutex_trylock(&a->mutex)) {
1970       THREAD_STAT(++(a->stat_lock_loop));
1971       tsd_setspecific(arena_key, (Void_t *)a);
1972       return a;
1973     }
1974     a = a->next;
1975   } while(a != a_tsd);
1976
1977   /* Nothing immediately available, so generate a new arena. */
1978   h = new_heap(size + (sizeof(*h) + sizeof(*a) + MALLOC_ALIGNMENT));
1979   if(!h)
1980     return 0;
1981   a = h->ar_ptr = (arena *)(h+1);
1982   for(i=0; i<NAV; i++)
1983     init_bin(a, i);
1984   a->next = NULL;
1985   a->size = h->size;
1986   tsd_setspecific(arena_key, (Void_t *)a);
1987   mutex_init(&a->mutex);
1988   i = mutex_lock(&a->mutex); /* remember result */
1989
1990   /* Set up the top chunk, with proper alignment. */
1991   ptr = (char *)(a + 1);
1992   misalign = (unsigned long)chunk2mem(ptr) & MALLOC_ALIGN_MASK;
1993   if (misalign > 0)
1994     ptr += MALLOC_ALIGNMENT - misalign;
1995   top(a) = (mchunkptr)ptr;
1996   set_head(top(a), (((char*)h + h->size) - ptr) | PREV_INUSE);
1997
1998   /* Add the new arena to the list. */
1999   (void)mutex_lock(&list_lock);
2000   a->next = main_arena.next;
2001   main_arena.next = a;
2002   (void)mutex_unlock(&list_lock);
2003
2004   if(i) /* locking failed; keep arena for further attempts later */
2005     return 0;
2006
2007   THREAD_STAT(++(a->stat_lock_loop));
2008   return a;
2009 }
2010
2011 /* find the heap and corresponding arena for a given ptr */
2012
2013 #define heap_for_ptr(ptr) \
2014  ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))
2015 #define arena_for_ptr(ptr) \
2016  (((mchunkptr)(ptr) < top(&main_arena) && (char *)(ptr) >= sbrk_base) ? \
2017   &main_arena : heap_for_ptr(ptr)->ar_ptr)
2018
2019 #else /* defined(NO_THREADS) */
2020
2021 /* Without concurrent threads, there is only one arena. */
2022
2023 #define arena_get(ptr, sz) (ptr = &main_arena)
2024 #define arena_for_ptr(ptr) (&main_arena)
2025
2026 #endif /* !defined(NO_THREADS) */
2027
2028 \f
2029
2030 /*
2031   Debugging support
2032 */
2033
2034 #if MALLOC_DEBUG
2035
2036
2037 /*
2038   These routines make a number of assertions about the states
2039   of data structures that should be true at all times. If any
2040   are not true, it's very likely that a user program has somehow
2041   trashed memory. (It's also possible that there is a coding error
2042   in malloc. In which case, please report it!)
2043 */
2044
2045 #if __STD_C
2046 static void do_check_chunk(arena *ar_ptr, mchunkptr p)
2047 #else
2048 static void do_check_chunk(ar_ptr, p) arena *ar_ptr; mchunkptr p;
2049 #endif
2050 {
2051   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2052
2053   /* No checkable chunk is mmapped */
2054   assert(!chunk_is_mmapped(p));
2055
2056 #ifndef NO_THREADS
2057   if(ar_ptr != &main_arena) {
2058     heap_info *heap = heap_for_ptr(p);
2059     assert(heap->ar_ptr == ar_ptr);
2060     assert((char *)p + sz <= (char *)heap + heap->size);
2061     return;
2062   }
2063 #endif
2064
2065   /* Check for legal address ... */
2066   assert((char*)p >= sbrk_base);
2067   if (p != top(ar_ptr))
2068     assert((char*)p + sz <= (char*)top(ar_ptr));
2069   else
2070     assert((char*)p + sz <= sbrk_base + sbrked_mem);
2071
2072 }
2073
2074
2075 #if __STD_C
2076 static void do_check_free_chunk(arena *ar_ptr, mchunkptr p)
2077 #else
2078 static void do_check_free_chunk(ar_ptr, p) arena *ar_ptr; mchunkptr p;
2079 #endif
2080 {
2081   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2082   mchunkptr next = chunk_at_offset(p, sz);
2083
2084   do_check_chunk(ar_ptr, p);
2085
2086   /* Check whether it claims to be free ... */
2087   assert(!inuse(p));
2088
2089   /* Must have OK size and fields */
2090   assert((long)sz >= (long)MINSIZE);
2091   assert((sz & MALLOC_ALIGN_MASK) == 0);
2092   assert(aligned_OK(chunk2mem(p)));
2093   /* ... matching footer field */
2094   assert(next->prev_size == sz);
2095   /* ... and is fully consolidated */
2096   assert(prev_inuse(p));
2097   assert (next == top(ar_ptr) || inuse(next));
2098
2099   /* ... and has minimally sane links */
2100   assert(p->fd->bk == p);
2101   assert(p->bk->fd == p);
2102 }
2103
2104 #if __STD_C
2105 static void do_check_inuse_chunk(arena *ar_ptr, mchunkptr p)
2106 #else
2107 static void do_check_inuse_chunk(ar_ptr, p) arena *ar_ptr; mchunkptr p;
2108 #endif
2109 {
2110   mchunkptr next = next_chunk(p);
2111   do_check_chunk(ar_ptr, p);
2112
2113   /* Check whether it claims to be in use ... */
2114   assert(inuse(p));
2115
2116   /* ... whether its size is OK (it might be a fencepost) ... */
2117   assert(chunksize(p) >= MINSIZE || next->size == (0|PREV_INUSE));
2118
2119   /* ... and is surrounded by OK chunks.
2120     Since more things can be checked with free chunks than inuse ones,
2121     if an inuse chunk borders them and debug is on, it's worth doing them.
2122   */
2123   if (!prev_inuse(p))
2124   {
2125     mchunkptr prv = prev_chunk(p);
2126     assert(next_chunk(prv) == p);
2127     do_check_free_chunk(ar_ptr, prv);
2128   }
2129   if (next == top(ar_ptr))
2130   {
2131     assert(prev_inuse(next));
2132     assert(chunksize(next) >= MINSIZE);
2133   }
2134   else if (!inuse(next))
2135     do_check_free_chunk(ar_ptr, next);
2136
2137 }
2138
2139 #if __STD_C
2140 static void do_check_malloced_chunk(arena *ar_ptr,
2141                                     mchunkptr p, INTERNAL_SIZE_T s)
2142 #else
2143 static void do_check_malloced_chunk(ar_ptr, p, s)
2144 arena *ar_ptr; mchunkptr p; INTERNAL_SIZE_T s;
2145 #endif
2146 {
2147   INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
2148   long room = sz - s;
2149
2150   do_check_inuse_chunk(ar_ptr, p);
2151
2152   /* Legal size ... */
2153   assert((long)sz >= (long)MINSIZE);
2154   assert((sz & MALLOC_ALIGN_MASK) == 0);
2155   assert(room >= 0);
2156   assert(room < (long)MINSIZE);
2157
2158   /* ... and alignment */
2159   assert(aligned_OK(chunk2mem(p)));
2160
2161
2162   /* ... and was allocated at front of an available chunk */
2163   assert(prev_inuse(p));
2164
2165 }
2166
2167
2168 #define check_free_chunk(A,P) do_check_free_chunk(A,P)
2169 #define check_inuse_chunk(A,P) do_check_inuse_chunk(A,P)
2170 #define check_chunk(A,P) do_check_chunk(A,P)
2171 #define check_malloced_chunk(A,P,N) do_check_malloced_chunk(A,P,N)
2172 #else
2173 #define check_free_chunk(A,P)
2174 #define check_inuse_chunk(A,P)
2175 #define check_chunk(A,P)
2176 #define check_malloced_chunk(A,P,N)
2177 #endif
2178
2179 \f
2180
2181 /*
2182   Macro-based internal utilities
2183 */
2184
2185
2186 /*
2187   Linking chunks in bin lists.
2188   Call these only with variables, not arbitrary expressions, as arguments.
2189 */
2190
2191 /*
2192   Place chunk p of size s in its bin, in size order,
2193   putting it ahead of others of same size.
2194 */
2195
2196
2197 #define frontlink(A, P, S, IDX, BK, FD)                                       \
2198 {                                                                             \
2199   if (S < MAX_SMALLBIN_SIZE)                                                  \
2200   {                                                                           \
2201     IDX = smallbin_index(S);                                                  \
2202     mark_binblock(A, IDX);                                                    \
2203     BK = bin_at(A, IDX);                                                      \
2204     FD = BK->fd;                                                              \
2205     P->bk = BK;                                                               \
2206     P->fd = FD;                                                               \
2207     FD->bk = BK->fd = P;                                                      \
2208   }                                                                           \
2209   else                                                                        \
2210   {                                                                           \
2211     IDX = bin_index(S);                                                       \
2212     BK = bin_at(A, IDX);                                                      \
2213     FD = BK->fd;                                                              \
2214     if (FD == BK) mark_binblock(A, IDX);                                      \
2215     else                                                                      \
2216     {                                                                         \
2217       while (FD != BK && S < chunksize(FD)) FD = FD->fd;                      \
2218       BK = FD->bk;                                                            \
2219     }                                                                         \
2220     P->bk = BK;                                                               \
2221     P->fd = FD;                                                               \
2222     FD->bk = BK->fd = P;                                                      \
2223   }                                                                           \
2224 }
2225
2226
2227 /* take a chunk off a list */
2228
2229 #define unlink(P, BK, FD)                                                     \
2230 {                                                                             \
2231   BK = P->bk;                                                                 \
2232   FD = P->fd;                                                                 \
2233   FD->bk = BK;                                                                \
2234   BK->fd = FD;                                                                \
2235 }                                                                             \
2236
2237 /* Place p as the last remainder */
2238
2239 #define link_last_remainder(A, P)                                             \
2240 {                                                                             \
2241   last_remainder(A)->fd = last_remainder(A)->bk = P;                          \
2242   P->fd = P->bk = last_remainder(A);                                          \
2243 }
2244
2245 /* Clear the last_remainder bin */
2246
2247 #define clear_last_remainder(A) \
2248   (last_remainder(A)->fd = last_remainder(A)->bk = last_remainder(A))
2249
2250
2251
2252 \f
2253
2254 /*
2255   Extend the top-most chunk by obtaining memory from system.
2256   Main interface to sbrk (but see also malloc_trim).
2257 */
2258
2259 #if __STD_C
2260 static void malloc_extend_top(arena *ar_ptr, INTERNAL_SIZE_T nb)
2261 #else
2262 static void malloc_extend_top(ar_ptr, nb) arena *ar_ptr; INTERNAL_SIZE_T nb;
2263 #endif
2264 {
2265   unsigned long pagesz   = malloc_getpagesize;
2266   mchunkptr old_top      = top(ar_ptr);        /* Record state of old top */
2267   INTERNAL_SIZE_T old_top_size = chunksize(old_top);
2268   INTERNAL_SIZE_T top_size;                    /* new size of top chunk */
2269
2270 #ifndef NO_THREADS
2271   if(ar_ptr == &main_arena) {
2272 #endif
2273
2274     char*     brk;                  /* return value from sbrk */
2275     INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of sbrked space */
2276     INTERNAL_SIZE_T correction;     /* bytes for 2nd sbrk call */
2277     char*     new_brk;              /* return of 2nd sbrk call */
2278     char*     old_end = (char*)(chunk_at_offset(old_top, old_top_size));
2279
2280     /* Pad request with top_pad plus minimal overhead */
2281     INTERNAL_SIZE_T sbrk_size = nb + top_pad + MINSIZE;
2282
2283     /* If not the first time through, round to preserve page boundary */
2284     /* Otherwise, we need to correct to a page size below anyway. */
2285     /* (We also correct below if an intervening foreign sbrk call.) */
2286
2287     if (sbrk_base != (char*)(-1))
2288       sbrk_size = (sbrk_size + (pagesz - 1)) & ~(pagesz - 1);
2289
2290     brk = (char*)(MORECORE (sbrk_size));
2291
2292     /* Fail if sbrk failed or if a foreign sbrk call killed our space */
2293     if (brk == (char*)(MORECORE_FAILURE) ||
2294         (brk < old_end && old_top != initial_top(&main_arena)))
2295       return;
2296
2297 #if defined(_LIBC) || defined(MALLOC_HOOKS)
2298     /* Call the `morecore' hook if necessary.  */
2299     if (__after_morecore_hook)
2300       (*__after_morecore_hook) ();
2301 #endif
2302
2303     sbrked_mem += sbrk_size;
2304
2305     if (brk == old_end) { /* can just add bytes to current top */
2306       top_size = sbrk_size + old_top_size;
2307       set_head(old_top, top_size | PREV_INUSE);
2308       old_top = 0; /* don't free below */
2309     } else {
2310       if (sbrk_base == (char*)(-1)) /* First time through. Record base */
2311         sbrk_base = brk;
2312       else
2313         /* Someone else called sbrk().  Count those bytes as sbrked_mem. */
2314         sbrked_mem += brk - (char*)old_end;
2315
2316       /* Guarantee alignment of first new chunk made from this space */
2317       front_misalign = (unsigned long)chunk2mem(brk) & MALLOC_ALIGN_MASK;
2318       if (front_misalign > 0) {
2319         correction = (MALLOC_ALIGNMENT) - front_misalign;
2320         brk += correction;
2321       } else
2322         correction = 0;
2323
2324       /* Guarantee the next brk will be at a page boundary */
2325       correction += pagesz - ((unsigned long)(brk + sbrk_size) & (pagesz - 1));
2326
2327       /* Allocate correction */
2328       new_brk = (char*)(MORECORE (correction));
2329       if (new_brk == (char*)(MORECORE_FAILURE)) return;
2330
2331 #if defined(_LIBC) || defined(MALLOC_HOOKS)
2332       /* Call the `morecore' hook if necessary.  */
2333       if (__after_morecore_hook)
2334         (*__after_morecore_hook) ();
2335 #endif
2336
2337       sbrked_mem += correction;
2338
2339       top(&main_arena) = (mchunkptr)brk;
2340       top_size = new_brk - brk + correction;
2341       set_head(top(&main_arena), top_size | PREV_INUSE);
2342
2343       if (old_top == initial_top(&main_arena))
2344         old_top = 0; /* don't free below */
2345     }
2346
2347     if ((unsigned long)sbrked_mem > (unsigned long)max_sbrked_mem)
2348       max_sbrked_mem = sbrked_mem;
2349 #ifdef NO_THREADS
2350     if ((unsigned long)(mmapped_mem + sbrked_mem) >
2351         (unsigned long)max_total_mem)
2352       max_total_mem = mmapped_mem + sbrked_mem;
2353 #endif
2354
2355 #ifndef NO_THREADS
2356   } else { /* ar_ptr != &main_arena */
2357     heap_info *old_heap, *heap;
2358     size_t old_heap_size;
2359
2360     if(old_top_size < MINSIZE) /* this should never happen */
2361       return;
2362
2363     /* First try to extend the current heap. */
2364     if(MINSIZE + nb <= old_top_size)
2365       return;
2366     old_heap = heap_for_ptr(old_top);
2367     old_heap_size = old_heap->size;
2368     if(grow_heap(old_heap, MINSIZE + nb - old_top_size) == 0) {
2369       ar_ptr->size += old_heap->size - old_heap_size;
2370       top_size = ((char *)old_heap + old_heap->size) - (char *)old_top;
2371       set_head(old_top, top_size | PREV_INUSE);
2372       return;
2373     }
2374
2375     /* A new heap must be created. */
2376     heap = new_heap(nb + (MINSIZE + sizeof(*heap)));
2377     if(!heap)
2378       return;
2379     heap->ar_ptr = ar_ptr;
2380     heap->prev = old_heap;
2381     ar_ptr->size += heap->size;
2382
2383     /* Set up the new top, so we can safely use chunk_free() below. */
2384     top(ar_ptr) = chunk_at_offset(heap, sizeof(*heap));
2385     top_size = heap->size - sizeof(*heap);
2386     set_head(top(ar_ptr), top_size | PREV_INUSE);
2387   }
2388 #endif /* !defined(NO_THREADS) */
2389
2390   /* We always land on a page boundary */
2391   assert(((unsigned long)((char*)top(ar_ptr) + top_size) & (pagesz-1)) == 0);
2392
2393   /* Setup fencepost and free the old top chunk. */
2394   if(old_top) {
2395     /* The fencepost takes at least MINSIZE bytes, because it might
2396        become the top chunk again later.  Note that a footer is set
2397        up, too, although the chunk is marked in use. */
2398     old_top_size -= MINSIZE;
2399     set_head(chunk_at_offset(old_top, old_top_size + 2*SIZE_SZ), 0|PREV_INUSE);
2400     if(old_top_size >= MINSIZE) {
2401       set_head(chunk_at_offset(old_top, old_top_size), (2*SIZE_SZ)|PREV_INUSE);
2402       set_foot(chunk_at_offset(old_top, old_top_size), (2*SIZE_SZ));
2403       set_head_size(old_top, old_top_size);
2404       chunk_free(ar_ptr, old_top);
2405     } else {
2406       set_head(old_top, (old_top_size + 2*SIZE_SZ)|PREV_INUSE);
2407       set_foot(old_top, (old_top_size + 2*SIZE_SZ));
2408     }
2409   }
2410 }
2411
2412
2413 \f
2414
2415 /* Main public routines */
2416
2417
2418 /*
2419   Malloc Algorithm:
2420
2421     The requested size is first converted into a usable form, `nb'.
2422     This currently means to add 4 bytes overhead plus possibly more to
2423     obtain 8-byte alignment and/or to obtain a size of at least
2424     MINSIZE (currently 16, 24, or 32 bytes), the smallest allocatable
2425     size.  (All fits are considered `exact' if they are within MINSIZE
2426     bytes.)
2427
2428     From there, the first successful of the following steps is taken:
2429
2430       1. The bin corresponding to the request size is scanned, and if
2431          a chunk of exactly the right size is found, it is taken.
2432
2433       2. The most recently remaindered chunk is used if it is big
2434          enough.  This is a form of (roving) first fit, used only in
2435          the absence of exact fits. Runs of consecutive requests use
2436          the remainder of the chunk used for the previous such request
2437          whenever possible. This limited use of a first-fit style
2438          allocation strategy tends to give contiguous chunks
2439          coextensive lifetimes, which improves locality and can reduce
2440          fragmentation in the long run.
2441
2442       3. Other bins are scanned in increasing size order, using a
2443          chunk big enough to fulfill the request, and splitting off
2444          any remainder.  This search is strictly by best-fit; i.e.,
2445          the smallest (with ties going to approximately the least
2446          recently used) chunk that fits is selected.
2447
2448       4. If large enough, the chunk bordering the end of memory
2449          (`top') is split off. (This use of `top' is in accord with
2450          the best-fit search rule.  In effect, `top' is treated as
2451          larger (and thus less well fitting) than any other available
2452          chunk since it can be extended to be as large as necessary
2453          (up to system limitations).
2454
2455       5. If the request size meets the mmap threshold and the
2456          system supports mmap, and there are few enough currently
2457          allocated mmapped regions, and a call to mmap succeeds,
2458          the request is allocated via direct memory mapping.
2459
2460       6. Otherwise, the top of memory is extended by
2461          obtaining more space from the system (normally using sbrk,
2462          but definable to anything else via the MORECORE macro).
2463          Memory is gathered from the system (in system page-sized
2464          units) in a way that allows chunks obtained across different
2465          sbrk calls to be consolidated, but does not require
2466          contiguous memory. Thus, it should be safe to intersperse
2467          mallocs with other sbrk calls.
2468
2469
2470       All allocations are made from the the `lowest' part of any found
2471       chunk. (The implementation invariant is that prev_inuse is
2472       always true of any allocated chunk; i.e., that each allocated
2473       chunk borders either a previously allocated and still in-use chunk,
2474       or the base of its memory arena.)
2475
2476 */
2477
2478 #if __STD_C
2479 Void_t* mALLOc(size_t bytes)
2480 #else
2481 Void_t* mALLOc(bytes) size_t bytes;
2482 #endif
2483 {
2484   arena *ar_ptr;
2485   INTERNAL_SIZE_T nb; /* padded request size */
2486   mchunkptr victim;
2487
2488 #if defined(_LIBC) || defined(MALLOC_HOOKS)
2489   if (__malloc_hook != NULL) {
2490     Void_t* result;
2491
2492     result = (*__malloc_hook)(bytes);
2493     return result;
2494   }
2495 #endif
2496
2497   nb = request2size(bytes);
2498   arena_get(ar_ptr, nb);
2499   if(!ar_ptr)
2500     return 0;
2501   victim = chunk_alloc(ar_ptr, nb);
2502   (void)mutex_unlock(&ar_ptr->mutex);
2503   if(!victim) {
2504     /* Maybe the failure is due to running out of mmapped areas. */
2505     if(ar_ptr != &main_arena) {
2506       (void)mutex_lock(&main_arena.mutex);
2507       victim = chunk_alloc(&main_arena, nb);
2508       (void)mutex_unlock(&main_arena.mutex);
2509     }
2510     if(!victim) return 0;
2511   }
2512   return chunk2mem(victim);
2513 }
2514
2515 static mchunkptr
2516 #if __STD_C
2517 chunk_alloc(arena *ar_ptr, INTERNAL_SIZE_T nb)
2518 #else
2519 chunk_alloc(ar_ptr, nb) arena *ar_ptr; INTERNAL_SIZE_T nb;
2520 #endif
2521 {
2522   mchunkptr victim;                  /* inspected/selected chunk */
2523   INTERNAL_SIZE_T victim_size;       /* its size */
2524   int       idx;                     /* index for bin traversal */
2525   mbinptr   bin;                     /* associated bin */
2526   mchunkptr remainder;               /* remainder from a split */
2527   long      remainder_size;          /* its size */
2528   int       remainder_index;         /* its bin index */
2529   unsigned long block;               /* block traverser bit */
2530   int       startidx;                /* first bin of a traversed block */
2531   mchunkptr fwd;                     /* misc temp for linking */
2532   mchunkptr bck;                     /* misc temp for linking */
2533   mbinptr q;                         /* misc temp */
2534
2535
2536   /* Check for exact match in a bin */
2537
2538   if (is_small_request(nb))  /* Faster version for small requests */
2539   {
2540     idx = smallbin_index(nb);
2541
2542     /* No traversal or size check necessary for small bins.  */
2543
2544     q = bin_at(ar_ptr, idx);
2545     victim = last(q);
2546
2547     /* Also scan the next one, since it would have a remainder < MINSIZE */
2548     if (victim == q)
2549     {
2550       q = next_bin(q);
2551       victim = last(q);
2552     }
2553     if (victim != q)
2554     {
2555       victim_size = chunksize(victim);
2556       unlink(victim, bck, fwd);
2557       set_inuse_bit_at_offset(victim, victim_size);
2558       check_malloced_chunk(ar_ptr, victim, nb);
2559       return victim;
2560     }
2561
2562     idx += 2; /* Set for bin scan below. We've already scanned 2 bins. */
2563
2564   }
2565   else
2566   {
2567     idx = bin_index(nb);
2568     bin = bin_at(ar_ptr, idx);
2569
2570     for (victim = last(bin); victim != bin; victim = victim->bk)
2571     {
2572       victim_size = chunksize(victim);
2573       remainder_size = victim_size - nb;
2574
2575       if (remainder_size >= (long)MINSIZE) /* too big */
2576       {
2577         --idx; /* adjust to rescan below after checking last remainder */
2578         break;
2579       }
2580
2581       else if (remainder_size >= 0) /* exact fit */
2582       {
2583         unlink(victim, bck, fwd);
2584         set_inuse_bit_at_offset(victim, victim_size);
2585         check_malloced_chunk(ar_ptr, victim, nb);
2586         return victim;
2587       }
2588     }
2589
2590     ++idx;
2591
2592   }
2593
2594   /* Try to use the last split-off remainder */
2595
2596   if ( (victim = last_remainder(ar_ptr)->fd) != last_remainder(ar_ptr))
2597   {
2598     victim_size = chunksize(victim);
2599     remainder_size = victim_size - nb;
2600
2601     if (remainder_size >= (long)MINSIZE) /* re-split */
2602     {
2603       remainder = chunk_at_offset(victim, nb);
2604       set_head(victim, nb | PREV_INUSE);
2605       link_last_remainder(ar_ptr, remainder);
2606       set_head(remainder, remainder_size | PREV_INUSE);
2607       set_foot(remainder, remainder_size);
2608       check_malloced_chunk(ar_ptr, victim, nb);
2609       return victim;
2610     }
2611
2612     clear_last_remainder(ar_ptr);
2613
2614     if (remainder_size >= 0)  /* exhaust */
2615     {
2616       set_inuse_bit_at_offset(victim, victim_size);
2617       check_malloced_chunk(ar_ptr, victim, nb);
2618       return victim;
2619     }
2620
2621     /* Else place in bin */
2622
2623     frontlink(ar_ptr, victim, victim_size, remainder_index, bck, fwd);
2624   }
2625
2626   /*
2627      If there are any possibly nonempty big-enough blocks,
2628      search for best fitting chunk by scanning bins in blockwidth units.
2629   */
2630
2631   if ( (block = idx2binblock(idx)) <= binblocks(ar_ptr))
2632   {
2633
2634     /* Get to the first marked block */
2635
2636     if ( (block & binblocks(ar_ptr)) == 0)
2637     {
2638       /* force to an even block boundary */
2639       idx = (idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH;
2640       block <<= 1;
2641       while ((block & binblocks(ar_ptr)) == 0)
2642       {
2643         idx += BINBLOCKWIDTH;
2644         block <<= 1;
2645       }
2646     }
2647
2648     /* For each possibly nonempty block ... */
2649     for (;;)
2650     {
2651       startidx = idx;          /* (track incomplete blocks) */
2652       q = bin = bin_at(ar_ptr, idx);
2653
2654       /* For each bin in this block ... */
2655       do
2656       {
2657         /* Find and use first big enough chunk ... */
2658
2659         for (victim = last(bin); victim != bin; victim = victim->bk)
2660         {
2661           victim_size = chunksize(victim);
2662           remainder_size = victim_size - nb;
2663
2664           if (remainder_size >= (long)MINSIZE) /* split */
2665           {
2666             remainder = chunk_at_offset(victim, nb);
2667             set_head(victim, nb | PREV_INUSE);
2668             unlink(victim, bck, fwd);
2669             link_last_remainder(ar_ptr, remainder);
2670             set_head(remainder, remainder_size | PREV_INUSE);
2671             set_foot(remainder, remainder_size);
2672             check_malloced_chunk(ar_ptr, victim, nb);
2673             return victim;
2674           }
2675
2676           else if (remainder_size >= 0)  /* take */
2677           {
2678             set_inuse_bit_at_offset(victim, victim_size);
2679             unlink(victim, bck, fwd);
2680             check_malloced_chunk(ar_ptr, victim, nb);
2681             return victim;
2682           }
2683
2684         }
2685
2686        bin = next_bin(bin);
2687
2688       } while ((++idx & (BINBLOCKWIDTH - 1)) != 0);
2689
2690       /* Clear out the block bit. */
2691
2692       do   /* Possibly backtrack to try to clear a partial block */
2693       {
2694         if ((startidx & (BINBLOCKWIDTH - 1)) == 0)
2695         {
2696           binblocks(ar_ptr) &= ~block;
2697           break;
2698         }
2699         --startidx;
2700         q = prev_bin(q);
2701       } while (first(q) == q);
2702
2703       /* Get to the next possibly nonempty block */
2704
2705       if ( (block <<= 1) <= binblocks(ar_ptr) && (block != 0) )
2706       {
2707         while ((block & binblocks(ar_ptr)) == 0)
2708         {
2709           idx += BINBLOCKWIDTH;
2710           block <<= 1;
2711         }
2712       }
2713       else
2714         break;
2715     }
2716   }
2717
2718
2719   /* Try to use top chunk */
2720
2721   /* Require that there be a remainder, ensuring top always exists  */
2722   if ( (remainder_size = chunksize(top(ar_ptr)) - nb) < (long)MINSIZE)
2723   {
2724
2725 #if HAVE_MMAP
2726     /* If big and would otherwise need to extend, try to use mmap instead */
2727     if ((unsigned long)nb >= (unsigned long)mmap_threshold &&
2728         (victim = mmap_chunk(nb)) != 0)
2729       return victim;
2730 #endif
2731
2732     /* Try to extend */
2733     malloc_extend_top(ar_ptr, nb);
2734     if ((remainder_size = chunksize(top(ar_ptr)) - nb) < (long)MINSIZE)
2735       return 0; /* propagate failure */
2736   }
2737
2738   victim = top(ar_ptr);
2739   set_head(victim, nb | PREV_INUSE);
2740   top(ar_ptr) = chunk_at_offset(victim, nb);
2741   set_head(top(ar_ptr), remainder_size | PREV_INUSE);
2742   check_malloced_chunk(ar_ptr, victim, nb);
2743   return victim;
2744
2745 }
2746
2747
2748 \f
2749
2750 /*
2751
2752   free() algorithm :
2753
2754     cases:
2755
2756        1. free(0) has no effect.
2757
2758        2. If the chunk was allocated via mmap, it is released via munmap().
2759
2760        3. If a returned chunk borders the current high end of memory,
2761           it is consolidated into the top, and if the total unused
2762           topmost memory exceeds the trim threshold, malloc_trim is
2763           called.
2764
2765        4. Other chunks are consolidated as they arrive, and
2766           placed in corresponding bins. (This includes the case of
2767           consolidating with the current `last_remainder').
2768
2769 */
2770
2771
2772 #if __STD_C
2773 void fREe(Void_t* mem)
2774 #else
2775 void fREe(mem) Void_t* mem;
2776 #endif
2777 {
2778   arena *ar_ptr;
2779   mchunkptr p;                          /* chunk corresponding to mem */
2780
2781 #if defined(_LIBC) || defined(MALLOC_HOOKS)
2782   if (__free_hook != NULL) {
2783     (*__free_hook)(mem);
2784     return;
2785   }
2786 #endif
2787
2788   if (mem == 0)                              /* free(0) has no effect */
2789     return;
2790
2791   p = mem2chunk(mem);
2792
2793 #if HAVE_MMAP
2794   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
2795   {
2796     munmap_chunk(p);
2797     return;
2798   }
2799 #endif
2800
2801   ar_ptr = arena_for_ptr(p);
2802 #if THREAD_STATS
2803   if(!mutex_trylock(&ar_ptr->mutex))
2804     ++(ar_ptr->stat_lock_direct);
2805   else {
2806     (void)mutex_lock(&ar_ptr->mutex);
2807     ++(ar_ptr->stat_lock_wait);
2808   }
2809 #else
2810   (void)mutex_lock(&ar_ptr->mutex);
2811 #endif
2812   chunk_free(ar_ptr, p);
2813   (void)mutex_unlock(&ar_ptr->mutex);
2814 }
2815
2816 static void
2817 #if __STD_C
2818 chunk_free(arena *ar_ptr, mchunkptr p)
2819 #else
2820 chunk_free(ar_ptr, p) arena *ar_ptr; mchunkptr p;
2821 #endif
2822 {
2823   INTERNAL_SIZE_T hd = p->size; /* its head field */
2824   INTERNAL_SIZE_T sz;  /* its size */
2825   int       idx;       /* its bin index */
2826   mchunkptr next;      /* next contiguous chunk */
2827   INTERNAL_SIZE_T nextsz; /* its size */
2828   INTERNAL_SIZE_T prevsz; /* size of previous contiguous chunk */
2829   mchunkptr bck;       /* misc temp for linking */
2830   mchunkptr fwd;       /* misc temp for linking */
2831   int       islr;      /* track whether merging with last_remainder */
2832
2833   check_inuse_chunk(ar_ptr, p);
2834
2835   sz = hd & ~PREV_INUSE;
2836   next = chunk_at_offset(p, sz);
2837   nextsz = chunksize(next);
2838
2839   if (next == top(ar_ptr))                         /* merge with top */
2840   {
2841     sz += nextsz;
2842
2843     if (!(hd & PREV_INUSE))                    /* consolidate backward */
2844     {
2845       prevsz = p->prev_size;
2846       p = chunk_at_offset(p, -prevsz);
2847       sz += prevsz;
2848       unlink(p, bck, fwd);
2849     }
2850
2851     set_head(p, sz | PREV_INUSE);
2852     top(ar_ptr) = p;
2853
2854 #ifndef NO_THREADS
2855     if(ar_ptr == &main_arena) {
2856 #endif
2857       if ((unsigned long)(sz) >= (unsigned long)trim_threshold)
2858         main_trim(top_pad);
2859 #ifndef NO_THREADS
2860     } else {
2861       heap_info *heap = heap_for_ptr(p);
2862
2863       assert(heap->ar_ptr == ar_ptr);
2864
2865       /* Try to get rid of completely empty heaps, if possible. */
2866       if((unsigned long)(sz) >= (unsigned long)trim_threshold ||
2867          p == chunk_at_offset(heap, sizeof(*heap)))
2868         heap_trim(heap, top_pad);
2869     }
2870 #endif
2871     return;
2872   }
2873
2874   islr = 0;
2875
2876   if (!(hd & PREV_INUSE))                    /* consolidate backward */
2877   {
2878     prevsz = p->prev_size;
2879     p = chunk_at_offset(p, -prevsz);
2880     sz += prevsz;
2881
2882     if (p->fd == last_remainder(ar_ptr))     /* keep as last_remainder */
2883       islr = 1;
2884     else
2885       unlink(p, bck, fwd);
2886   }
2887
2888   if (!(inuse_bit_at_offset(next, nextsz)))   /* consolidate forward */
2889   {
2890     sz += nextsz;
2891
2892     if (!islr && next->fd == last_remainder(ar_ptr))
2893                                               /* re-insert last_remainder */
2894     {
2895       islr = 1;
2896       link_last_remainder(ar_ptr, p);
2897     }
2898     else
2899       unlink(next, bck, fwd);
2900
2901     next = chunk_at_offset(p, sz);
2902   }
2903   else
2904     set_head(next, nextsz);                  /* clear inuse bit */
2905
2906   set_head(p, sz | PREV_INUSE);
2907   next->prev_size = sz;
2908   if (!islr)
2909     frontlink(ar_ptr, p, sz, idx, bck, fwd);
2910
2911 #ifndef NO_THREADS
2912   /* Check whether the heap containing top can go away now. */
2913   if(next->size < MINSIZE &&
2914      (unsigned long)sz > trim_threshold &&
2915      ar_ptr != &main_arena) {                /* fencepost */
2916     heap_info* heap = heap_for_ptr(top(ar_ptr));
2917
2918     if(top(ar_ptr) == chunk_at_offset(heap, sizeof(*heap)) &&
2919        heap->prev == heap_for_ptr(p))
2920       heap_trim(heap, top_pad);
2921   }
2922 #endif
2923 }
2924
2925
2926 \f
2927
2928
2929 /*
2930
2931   Realloc algorithm:
2932
2933     Chunks that were obtained via mmap cannot be extended or shrunk
2934     unless HAVE_MREMAP is defined, in which case mremap is used.
2935     Otherwise, if their reallocation is for additional space, they are
2936     copied.  If for less, they are just left alone.
2937
2938     Otherwise, if the reallocation is for additional space, and the
2939     chunk can be extended, it is, else a malloc-copy-free sequence is
2940     taken.  There are several different ways that a chunk could be
2941     extended. All are tried:
2942
2943        * Extending forward into following adjacent free chunk.
2944        * Shifting backwards, joining preceding adjacent space
2945        * Both shifting backwards and extending forward.
2946        * Extending into newly sbrked space
2947
2948     Unless the #define REALLOC_ZERO_BYTES_FREES is set, realloc with a
2949     size argument of zero (re)allocates a minimum-sized chunk.
2950
2951     If the reallocation is for less space, and the new request is for
2952     a `small' (<512 bytes) size, then the newly unused space is lopped
2953     off and freed.
2954
2955     The old unix realloc convention of allowing the last-free'd chunk
2956     to be used as an argument to realloc is no longer supported.
2957     I don't know of any programs still relying on this feature,
2958     and allowing it would also allow too many other incorrect
2959     usages of realloc to be sensible.
2960
2961
2962 */
2963
2964
2965 #if __STD_C
2966 Void_t* rEALLOc(Void_t* oldmem, size_t bytes)
2967 #else
2968 Void_t* rEALLOc(oldmem, bytes) Void_t* oldmem; size_t bytes;
2969 #endif
2970 {
2971   arena *ar_ptr;
2972   INTERNAL_SIZE_T    nb;      /* padded request size */
2973
2974   mchunkptr oldp;             /* chunk corresponding to oldmem */
2975   INTERNAL_SIZE_T    oldsize; /* its size */
2976
2977   mchunkptr newp;             /* chunk to return */
2978
2979 #if defined(_LIBC) || defined(MALLOC_HOOKS)
2980   if (__realloc_hook != NULL) {
2981     Void_t* result;
2982
2983     result = (*__realloc_hook)(oldmem, bytes);
2984     return result;
2985   }
2986 #endif
2987
2988 #ifdef REALLOC_ZERO_BYTES_FREES
2989   if (bytes == 0) { fREe(oldmem); return 0; }
2990 #endif
2991
2992   /* realloc of null is supposed to be same as malloc */
2993   if (oldmem == 0) return mALLOc(bytes);
2994
2995   oldp    = mem2chunk(oldmem);
2996   oldsize = chunksize(oldp);
2997
2998   nb = request2size(bytes);
2999
3000 #if HAVE_MMAP
3001   if (chunk_is_mmapped(oldp))
3002   {
3003     Void_t* newmem;
3004
3005 #if HAVE_MREMAP
3006     newp = mremap_chunk(oldp, nb);
3007     if(newp) return chunk2mem(newp);
3008 #endif
3009     /* Note the extra SIZE_SZ overhead. */
3010     if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */
3011     /* Must alloc, copy, free. */
3012     newmem = mALLOc(bytes);
3013     if (newmem == 0) return 0; /* propagate failure */
3014     MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
3015     munmap_chunk(oldp);
3016     return newmem;
3017   }
3018 #endif
3019
3020   ar_ptr = arena_for_ptr(oldp);
3021 #if THREAD_STATS
3022   if(!mutex_trylock(&ar_ptr->mutex))
3023     ++(ar_ptr->stat_lock_direct);
3024   else {
3025     (void)mutex_lock(&ar_ptr->mutex);
3026     ++(ar_ptr->stat_lock_wait);
3027   }
3028 #else
3029   (void)mutex_lock(&ar_ptr->mutex);
3030 #endif
3031
3032 #ifndef NO_THREADS
3033   /* As in malloc(), remember this arena for the next allocation. */
3034   tsd_setspecific(arena_key, (Void_t *)ar_ptr);
3035 #endif
3036
3037   newp = chunk_realloc(ar_ptr, oldp, oldsize, nb);
3038
3039   (void)mutex_unlock(&ar_ptr->mutex);
3040   return newp ? chunk2mem(newp) : NULL;
3041 }
3042
3043 static mchunkptr
3044 #if __STD_C
3045 chunk_realloc(arena* ar_ptr, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
3046               INTERNAL_SIZE_T nb)
3047 #else
3048 chunk_realloc(ar_ptr, oldp, oldsize, nb)
3049 arena* ar_ptr; mchunkptr oldp; INTERNAL_SIZE_T oldsize, nb;
3050 #endif
3051 {
3052   mchunkptr newp = oldp;      /* chunk to return */
3053   INTERNAL_SIZE_T newsize = oldsize; /* its size */
3054
3055   mchunkptr next;             /* next contiguous chunk after oldp */
3056   INTERNAL_SIZE_T  nextsize;  /* its size */
3057
3058   mchunkptr prev;             /* previous contiguous chunk before oldp */
3059   INTERNAL_SIZE_T  prevsize;  /* its size */
3060
3061   mchunkptr remainder;        /* holds split off extra space from newp */
3062   INTERNAL_SIZE_T  remainder_size;   /* its size */
3063
3064   mchunkptr bck;              /* misc temp for linking */
3065   mchunkptr fwd;              /* misc temp for linking */
3066
3067   check_inuse_chunk(ar_ptr, oldp);
3068
3069   if ((long)(oldsize) < (long)(nb))
3070   {
3071
3072     /* Try expanding forward */
3073
3074     next = chunk_at_offset(oldp, oldsize);
3075     if (next == top(ar_ptr) || !inuse(next))
3076     {
3077       nextsize = chunksize(next);
3078
3079       /* Forward into top only if a remainder */
3080       if (next == top(ar_ptr))
3081       {
3082         if ((long)(nextsize + newsize) >= (long)(nb + MINSIZE))
3083         {
3084           newsize += nextsize;
3085           top(ar_ptr) = chunk_at_offset(oldp, nb);
3086           set_head(top(ar_ptr), (newsize - nb) | PREV_INUSE);
3087           set_head_size(oldp, nb);
3088           return oldp;
3089         }
3090       }
3091
3092       /* Forward into next chunk */
3093       else if (((long)(nextsize + newsize) >= (long)(nb)))
3094       {
3095         unlink(next, bck, fwd);
3096         newsize  += nextsize;
3097         goto split;
3098       }
3099     }
3100     else
3101     {
3102       next = 0;
3103       nextsize = 0;
3104     }
3105
3106     /* Try shifting backwards. */
3107
3108     if (!prev_inuse(oldp))
3109     {
3110       prev = prev_chunk(oldp);
3111       prevsize = chunksize(prev);
3112
3113       /* try forward + backward first to save a later consolidation */
3114
3115       if (next != 0)
3116       {
3117         /* into top */
3118         if (next == top(ar_ptr))
3119         {
3120           if ((long)(nextsize + prevsize + newsize) >= (long)(nb + MINSIZE))
3121           {
3122             unlink(prev, bck, fwd);
3123             newp = prev;
3124             newsize += prevsize + nextsize;
3125             MALLOC_COPY(chunk2mem(newp), chunk2mem(oldp), oldsize - SIZE_SZ);
3126             top(ar_ptr) = chunk_at_offset(newp, nb);
3127             set_head(top(ar_ptr), (newsize - nb) | PREV_INUSE);
3128             set_head_size(newp, nb);
3129             return newp;
3130           }
3131         }
3132
3133         /* into next chunk */
3134         else if (((long)(nextsize + prevsize + newsize) >= (long)(nb)))
3135         {
3136           unlink(next, bck, fwd);
3137           unlink(prev, bck, fwd);
3138           newp = prev;
3139           newsize += nextsize + prevsize;
3140           MALLOC_COPY(chunk2mem(newp), chunk2mem(oldp), oldsize - SIZE_SZ);
3141           goto split;
3142         }
3143       }
3144
3145       /* backward only */
3146       if (prev != 0 && (long)(prevsize + newsize) >= (long)nb)
3147       {
3148         unlink(prev, bck, fwd);
3149         newp = prev;
3150         newsize += prevsize;
3151         MALLOC_COPY(chunk2mem(newp), chunk2mem(oldp), oldsize - SIZE_SZ);
3152         goto split;
3153       }
3154     }
3155
3156     /* Must allocate */
3157
3158     newp = chunk_alloc (ar_ptr, nb);
3159
3160     if (newp == 0) {
3161       /* Maybe the failure is due to running out of mmapped areas. */
3162       if (ar_ptr != &main_arena) {
3163         (void)mutex_lock(&main_arena.mutex);
3164         newp = chunk_alloc(&main_arena, nb);
3165         (void)mutex_unlock(&main_arena.mutex);
3166       }
3167       if (newp == 0) /* propagate failure */
3168         return 0;
3169     }
3170
3171     /* Avoid copy if newp is next chunk after oldp. */
3172     /* (This can only happen when new chunk is sbrk'ed.) */
3173
3174     if ( newp == next_chunk(oldp))
3175     {
3176       newsize += chunksize(newp);
3177       newp = oldp;
3178       goto split;
3179     }
3180
3181     /* Otherwise copy, free, and exit */
3182     MALLOC_COPY(chunk2mem(newp), chunk2mem(oldp), oldsize - SIZE_SZ);
3183     chunk_free(ar_ptr, oldp);
3184     return newp;
3185   }
3186
3187
3188  split:  /* split off extra room in old or expanded chunk */
3189
3190   if (newsize - nb >= MINSIZE) /* split off remainder */
3191   {
3192     remainder = chunk_at_offset(newp, nb);
3193     remainder_size = newsize - nb;
3194     set_head_size(newp, nb);
3195     set_head(remainder, remainder_size | PREV_INUSE);
3196     set_inuse_bit_at_offset(remainder, remainder_size);
3197     chunk_free(ar_ptr, remainder);
3198   }
3199   else
3200   {
3201     set_head_size(newp, newsize);
3202     set_inuse_bit_at_offset(newp, newsize);
3203   }
3204
3205   check_inuse_chunk(ar_ptr, newp);
3206   return newp;
3207 }
3208
3209
3210 \f
3211
3212 /*
3213
3214   memalign algorithm:
3215
3216     memalign requests more than enough space from malloc, finds a spot
3217     within that chunk that meets the alignment request, and then
3218     possibly frees the leading and trailing space.
3219
3220     The alignment argument must be a power of two. This property is not
3221     checked by memalign, so misuse may result in random runtime errors.
3222
3223     8-byte alignment is guaranteed by normal malloc calls, so don't
3224     bother calling memalign with an argument of 8 or less.
3225
3226     Overreliance on memalign is a sure way to fragment space.
3227
3228 */
3229
3230
3231 #if __STD_C
3232 Void_t* mEMALIGn(size_t alignment, size_t bytes)
3233 #else
3234 Void_t* mEMALIGn(alignment, bytes) size_t alignment; size_t bytes;
3235 #endif
3236 {
3237   arena *ar_ptr;
3238   INTERNAL_SIZE_T    nb;      /* padded  request size */
3239   mchunkptr p;
3240
3241 #if defined(_LIBC) || defined(MALLOC_HOOKS)
3242   if (__memalign_hook != NULL) {
3243     Void_t* result;
3244
3245     result = (*__memalign_hook)(alignment, bytes);
3246     return result;
3247   }
3248 #endif
3249
3250   /* If need less alignment than we give anyway, just relay to malloc */
3251
3252   if (alignment <= MALLOC_ALIGNMENT) return mALLOc(bytes);
3253
3254   /* Otherwise, ensure that it is at least a minimum chunk size */
3255
3256   if (alignment <  MINSIZE) alignment = MINSIZE;
3257
3258   nb = request2size(bytes);
3259   arena_get(ar_ptr, nb + alignment + MINSIZE);
3260   if(!ar_ptr)
3261     return 0;
3262   p = chunk_align(ar_ptr, nb, alignment);
3263   (void)mutex_unlock(&ar_ptr->mutex);
3264   if(!p) {
3265     /* Maybe the failure is due to running out of mmapped areas. */
3266     if(ar_ptr != &main_arena) {
3267       (void)mutex_lock(&main_arena.mutex);
3268       p = chunk_align(&main_arena, nb, alignment);
3269       (void)mutex_unlock(&main_arena.mutex);
3270     }
3271     if(!p) return 0;
3272   }
3273   return chunk2mem(p);
3274 }
3275
3276 static mchunkptr
3277 #if __STD_C
3278 chunk_align(arena* ar_ptr, INTERNAL_SIZE_T nb, size_t alignment)
3279 #else
3280 chunk_align(ar_ptr, nb, alignment)
3281 arena* ar_ptr; INTERNAL_SIZE_T nb; size_t alignment;
3282 #endif
3283 {
3284   char*     m;                /* memory returned by malloc call */
3285   mchunkptr p;                /* corresponding chunk */
3286   char*     brk;              /* alignment point within p */
3287   mchunkptr newp;             /* chunk to return */
3288   INTERNAL_SIZE_T  newsize;   /* its size */
3289   INTERNAL_SIZE_T  leadsize;  /* leading space befor alignment point */
3290   mchunkptr remainder;        /* spare room at end to split off */
3291   long      remainder_size;   /* its size */
3292
3293   /* Call chunk_alloc with worst case padding to hit alignment. */
3294   p = chunk_alloc(ar_ptr, nb + alignment + MINSIZE);
3295   if (p == 0)
3296     return 0; /* propagate failure */
3297
3298   m = chunk2mem(p);
3299
3300   if ((((unsigned long)(m)) % alignment) == 0) /* aligned */
3301   {
3302 #if HAVE_MMAP
3303     if(chunk_is_mmapped(p)) {
3304       return p; /* nothing more to do */
3305     }
3306 #endif
3307   }
3308   else /* misaligned */
3309   {
3310     /*
3311       Find an aligned spot inside chunk.
3312       Since we need to give back leading space in a chunk of at
3313       least MINSIZE, if the first calculation places us at
3314       a spot with less than MINSIZE leader, we can move to the
3315       next aligned spot -- we've allocated enough total room so that
3316       this is always possible.
3317     */
3318
3319     brk = (char*)mem2chunk(((unsigned long)(m + alignment - 1)) & -alignment);
3320     if ((long)(brk - (char*)(p)) < (long)MINSIZE) brk += alignment;
3321
3322     newp = (mchunkptr)brk;
3323     leadsize = brk - (char*)(p);
3324     newsize = chunksize(p) - leadsize;
3325
3326 #if HAVE_MMAP
3327     if(chunk_is_mmapped(p))
3328     {
3329       newp->prev_size = p->prev_size + leadsize;
3330       set_head(newp, newsize|IS_MMAPPED);
3331       return newp;
3332     }
3333 #endif
3334
3335     /* give back leader, use the rest */
3336
3337     set_head(newp, newsize | PREV_INUSE);
3338     set_inuse_bit_at_offset(newp, newsize);
3339     set_head_size(p, leadsize);
3340     chunk_free(ar_ptr, p);
3341     p = newp;
3342
3343     assert (newsize>=nb && (((unsigned long)(chunk2mem(p))) % alignment) == 0);
3344   }
3345
3346   /* Also give back spare room at the end */
3347
3348   remainder_size = chunksize(p) - nb;
3349
3350   if (remainder_size >= (long)MINSIZE)
3351   {
3352     remainder = chunk_at_offset(p, nb);
3353     set_head(remainder, remainder_size | PREV_INUSE);
3354     set_head_size(p, nb);
3355     chunk_free(ar_ptr, remainder);
3356   }
3357
3358   check_inuse_chunk(ar_ptr, p);
3359   return p;
3360 }
3361
3362 \f
3363
3364
3365 /*
3366     valloc just invokes memalign with alignment argument equal
3367     to the page size of the system (or as near to this as can
3368     be figured out from all the includes/defines above.)
3369 */
3370
3371 #if __STD_C
3372 Void_t* vALLOc(size_t bytes)
3373 #else
3374 Void_t* vALLOc(bytes) size_t bytes;
3375 #endif
3376 {
3377   return mEMALIGn (malloc_getpagesize, bytes);
3378 }
3379
3380 /*
3381   pvalloc just invokes valloc for the nearest pagesize
3382   that will accommodate request
3383 */
3384
3385
3386 #if __STD_C
3387 Void_t* pvALLOc(size_t bytes)
3388 #else
3389 Void_t* pvALLOc(bytes) size_t bytes;
3390 #endif
3391 {
3392   size_t pagesize = malloc_getpagesize;
3393   return mEMALIGn (pagesize, (bytes + pagesize - 1) & ~(pagesize - 1));
3394 }
3395
3396 /*
3397
3398   calloc calls chunk_alloc, then zeroes out the allocated chunk.
3399
3400 */
3401
3402 #if __STD_C
3403 Void_t* cALLOc(size_t n, size_t elem_size)
3404 #else
3405 Void_t* cALLOc(n, elem_size) size_t n; size_t elem_size;
3406 #endif
3407 {
3408   arena *ar_ptr;
3409   mchunkptr p, oldtop;
3410   INTERNAL_SIZE_T sz, csz, oldtopsize;
3411   Void_t* mem;
3412
3413 #if defined(_LIBC) || defined(MALLOC_HOOKS)
3414   if (__malloc_hook != NULL) {
3415     sz = n * elem_size;
3416     mem = (*__malloc_hook)(sz);
3417     if(mem == 0)
3418       return 0;
3419 #ifdef HAVE_MEMCPY
3420     return memset(mem, 0, sz);
3421 #else
3422     while(sz > 0) ((char*)mem)[--sz] = 0; /* rather inefficient */
3423     return mem;
3424 #endif
3425   }
3426 #endif
3427
3428   sz = request2size(n * elem_size);
3429   arena_get(ar_ptr, sz);
3430   if(!ar_ptr)
3431     return 0;
3432
3433   /* check if expand_top called, in which case don't need to clear */
3434 #if MORECORE_CLEARS
3435   oldtop = top(ar_ptr);
3436   oldtopsize = chunksize(top(ar_ptr));
3437 #endif
3438   p = chunk_alloc (ar_ptr, sz);
3439
3440   /* Only clearing follows, so we can unlock early. */
3441   (void)mutex_unlock(&ar_ptr->mutex);
3442
3443   if (p == 0) {
3444     /* Maybe the failure is due to running out of mmapped areas. */
3445     if(ar_ptr != &main_arena) {
3446       (void)mutex_lock(&main_arena.mutex);
3447       p = chunk_alloc(&main_arena, sz);
3448       (void)mutex_unlock(&main_arena.mutex);
3449     }
3450     if (p == 0) return 0;
3451   }
3452   mem = chunk2mem(p);
3453
3454   /* Two optional cases in which clearing not necessary */
3455
3456 #if HAVE_MMAP
3457   if (chunk_is_mmapped(p)) return mem;
3458 #endif
3459
3460   csz = chunksize(p);
3461
3462 #if MORECORE_CLEARS
3463   if (p == oldtop && csz > oldtopsize) {
3464     /* clear only the bytes from non-freshly-sbrked memory */
3465     csz = oldtopsize;
3466   }
3467 #endif
3468
3469   MALLOC_ZERO(mem, csz - SIZE_SZ);
3470   return mem;
3471 }
3472
3473 /*
3474
3475   cfree just calls free. It is needed/defined on some systems
3476   that pair it with calloc, presumably for odd historical reasons.
3477
3478 */
3479
3480 #if !defined(_LIBC)
3481 #if __STD_C
3482 void cfree(Void_t *mem)
3483 #else
3484 void cfree(mem) Void_t *mem;
3485 #endif
3486 {
3487   free(mem);
3488 }
3489 #endif
3490
3491 \f
3492
3493 /*
3494
3495     Malloc_trim gives memory back to the system (via negative
3496     arguments to sbrk) if there is unused memory at the `high' end of
3497     the malloc pool. You can call this after freeing large blocks of
3498     memory to potentially reduce the system-level memory requirements
3499     of a program. However, it cannot guarantee to reduce memory. Under
3500     some allocation patterns, some large free blocks of memory will be
3501     locked between two used chunks, so they cannot be given back to
3502     the system.
3503
3504     The `pad' argument to malloc_trim represents the amount of free
3505     trailing space to leave untrimmed. If this argument is zero,
3506     only the minimum amount of memory to maintain internal data
3507     structures will be left (one page or less). Non-zero arguments
3508     can be supplied to maintain enough trailing space to service
3509     future expected allocations without having to re-obtain memory
3510     from the system.
3511
3512     Malloc_trim returns 1 if it actually released any memory, else 0.
3513
3514 */
3515
3516 #if __STD_C
3517 int mALLOC_TRIm(size_t pad)
3518 #else
3519 int mALLOC_TRIm(pad) size_t pad;
3520 #endif
3521 {
3522   int res;
3523
3524   (void)mutex_lock(&main_arena.mutex);
3525   res = main_trim(pad);
3526   (void)mutex_unlock(&main_arena.mutex);
3527   return res;
3528 }
3529
3530 /* Trim the main arena. */
3531
3532 static int
3533 #if __STD_C
3534 main_trim(size_t pad)
3535 #else
3536 main_trim(pad) size_t pad;
3537 #endif
3538 {
3539   mchunkptr top_chunk;   /* The current top chunk */
3540   long  top_size;        /* Amount of top-most memory */
3541   long  extra;           /* Amount to release */
3542   char* current_brk;     /* address returned by pre-check sbrk call */
3543   char* new_brk;         /* address returned by negative sbrk call */
3544
3545   unsigned long pagesz = malloc_getpagesize;
3546
3547   top_chunk = top(&main_arena);
3548   top_size = chunksize(top_chunk);
3549   extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
3550
3551   if (extra < (long)pagesz) /* Not enough memory to release */
3552     return 0;
3553
3554   /* Test to make sure no one else called sbrk */
3555   current_brk = (char*)(MORECORE (0));
3556   if (current_brk != (char*)(top_chunk) + top_size)
3557     return 0;     /* Apparently we don't own memory; must fail */
3558
3559   new_brk = (char*)(MORECORE (-extra));
3560
3561 #if defined(_LIBC) || defined(MALLOC_HOOKS)
3562   /* Call the `morecore' hook if necessary.  */
3563   if (__after_morecore_hook)
3564     (*__after_morecore_hook) ();
3565 #endif
3566
3567   if (new_brk == (char*)(MORECORE_FAILURE)) { /* sbrk failed? */
3568     /* Try to figure out what we have */
3569     current_brk = (char*)(MORECORE (0));
3570     top_size = current_brk - (char*)top_chunk;
3571     if (top_size >= (long)MINSIZE) /* if not, we are very very dead! */
3572     {
3573       sbrked_mem = current_brk - sbrk_base;
3574       set_head(top_chunk, top_size | PREV_INUSE);
3575     }
3576     check_chunk(&main_arena, top_chunk);
3577     return 0;
3578   }
3579   sbrked_mem -= extra;
3580
3581   /* Success. Adjust top accordingly. */
3582   set_head(top_chunk, (top_size - extra) | PREV_INUSE);
3583   check_chunk(&main_arena, top_chunk);
3584   return 1;
3585 }
3586
3587 #ifndef NO_THREADS
3588
3589 static int
3590 #if __STD_C
3591 heap_trim(heap_info *heap, size_t pad)
3592 #else
3593 heap_trim(heap, pad) heap_info *heap; size_t pad;
3594 #endif
3595 {
3596   unsigned long pagesz = malloc_getpagesize;
3597   arena *ar_ptr = heap->ar_ptr;
3598   mchunkptr top_chunk = top(ar_ptr), p, bck, fwd;
3599   heap_info *prev_heap;
3600   long new_size, top_size, extra;
3601
3602   /* Can this heap go away completely ? */
3603   while(top_chunk == chunk_at_offset(heap, sizeof(*heap))) {
3604     prev_heap = heap->prev;
3605     p = chunk_at_offset(prev_heap, prev_heap->size - (MINSIZE-2*SIZE_SZ));
3606     assert(p->size == (0|PREV_INUSE)); /* must be fencepost */
3607     p = prev_chunk(p);
3608     new_size = chunksize(p) + (MINSIZE-2*SIZE_SZ);
3609     assert(new_size>0 && new_size<(long)(2*MINSIZE));
3610     if(!prev_inuse(p))
3611       new_size += p->prev_size;
3612     assert(new_size>0 && new_size<HEAP_MAX_SIZE);
3613     if(new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)
3614       break;
3615     ar_ptr->size -= heap->size;
3616     delete_heap(heap);
3617     heap = prev_heap;
3618     if(!prev_inuse(p)) { /* consolidate backward */
3619       p = prev_chunk(p);
3620       unlink(p, bck, fwd);
3621     }
3622     assert(((unsigned long)((char*)p + new_size) & (pagesz-1)) == 0);
3623     assert( ((char*)p + new_size) == ((char*)heap + heap->size) );
3624     top(ar_ptr) = top_chunk = p;
3625     set_head(top_chunk, new_size | PREV_INUSE);
3626     check_chunk(ar_ptr, top_chunk);
3627   }
3628   top_size = chunksize(top_chunk);
3629   extra = ((top_size - pad - MINSIZE + (pagesz-1))/pagesz - 1) * pagesz;
3630   if(extra < (long)pagesz)
3631     return 0;
3632   /* Try to shrink. */
3633   if(grow_heap(heap, -extra) != 0)
3634     return 0;
3635   ar_ptr->size -= extra;
3636
3637   /* Success. Adjust top accordingly. */
3638   set_head(top_chunk, (top_size - extra) | PREV_INUSE);
3639   check_chunk(ar_ptr, top_chunk);
3640   return 1;
3641 }
3642
3643 #endif
3644
3645 \f
3646