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