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