1/* Malloc implementation for multiple threads without lock contention.
2   Copyright (C) 1996-2015 Free Software Foundation, Inc.
3   This file is part of the GNU C Library.
4   Contributed by Wolfram Gloger <wg@malloc.de>
5   and Doug Lea <dl@cs.oswego.edu>, 2001.
6
7   The GNU C Library is free software; you can redistribute it and/or
8   modify it under the terms of the GNU Lesser General Public License as
9   published by the Free Software Foundation; either version 2.1 of the
10   License, or (at your option) any later version.
11
12   The GNU C Library is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15   Lesser General Public License for more details.
16
17   You should have received a copy of the GNU Lesser General Public
18   License along with the GNU C Library; see the file COPYING.LIB.  If
19   not, see <http://www.gnu.org/licenses/>.  */
20
21/*
22  This is a version (aka ptmalloc2) of malloc/free/realloc written by
23  Doug Lea and adapted to multiple threads/arenas by Wolfram Gloger.
24
25  There have been substantial changes made after the integration into
26  glibc in all parts of the code.  Do not look for much commonality
27  with the ptmalloc2 version.
28
29* Version ptmalloc2-20011215
30  based on:
31  VERSION 2.7.0 Sun Mar 11 14:14:06 2001  Doug Lea  (dl at gee)
32
33* Quickstart
34
35  In order to compile this implementation, a Makefile is provided with
36  the ptmalloc2 distribution, which has pre-defined targets for some
37  popular systems (e.g. "make posix" for Posix threads).  All that is
38  typically required with regard to compiler flags is the selection of
39  the thread package via defining one out of USE_PTHREADS, USE_THR or
40  USE_SPROC.  Check the thread-m.h file for what effects this has.
41  Many/most systems will additionally require USE_TSD_DATA_HACK to be
42  defined, so this is the default for "make posix".
43
44* Why use this malloc?
45
46  This is not the fastest, most space-conserving, most portable, or
47  most tunable malloc ever written. However it is among the fastest
48  while also being among the most space-conserving, portable and tunable.
49  Consistent balance across these factors results in a good general-purpose
50  allocator for malloc-intensive programs.
51
52  The main properties of the algorithms are:
53  * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
54    with ties normally decided via FIFO (i.e. least recently used).
55  * For small (<= 64 bytes by default) requests, it is a caching
56    allocator, that maintains pools of quickly recycled chunks.
57  * In between, and for combinations of large and small requests, it does
58    the best it can trying to meet both goals at once.
59  * For very large requests (>= 128KB by default), it relies on system
60    memory mapping facilities, if supported.
61
62  For a longer but slightly out of date high-level description, see
63     http://gee.cs.oswego.edu/dl/html/malloc.html
64
65  You may already by default be using a C library containing a malloc
66  that is  based on some version of this malloc (for example in
67  linux). You might still want to use the one in this file in order to
68  customize settings or to avoid overheads associated with library
69  versions.
70
71* Contents, described in more detail in "description of public routines" below.
72
73  Standard (ANSI/SVID/...)  functions:
74    malloc(size_t n);
75    calloc(size_t n_elements, size_t element_size);
76    free(void* p);
77    realloc(void* p, size_t n);
78    memalign(size_t alignment, size_t n);
79    valloc(size_t n);
80    mallinfo()
81    mallopt(int parameter_number, int parameter_value)
82
83  Additional functions:
84    independent_calloc(size_t n_elements, size_t size, void* chunks[]);
85    independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
86    pvalloc(size_t n);
87    cfree(void* p);
88    malloc_trim(size_t pad);
89    malloc_usable_size(void* p);
90    malloc_stats();
91
92* Vital statistics:
93
94  Supported pointer representation:       4 or 8 bytes
95  Supported size_t  representation:       4 or 8 bytes
96       Note that size_t is allowed to be 4 bytes even if pointers are 8.
97       You can adjust this by defining INTERNAL_SIZE_T
98
99  Alignment:                              2 * sizeof(size_t) (default)
100       (i.e., 8 byte alignment with 4byte size_t). This suffices for
101       nearly all current machines and C compilers. However, you can
102       define MALLOC_ALIGNMENT to be wider than this if necessary.
103
104  Minimum overhead per allocated chunk:   4 or 8 bytes
105       Each malloced chunk has a hidden word of overhead holding size
106       and status information.
107
108  Minimum allocated size: 4-byte ptrs:  16 bytes    (including 4 overhead)
109			  8-byte ptrs:  24/32 bytes (including, 4/8 overhead)
110
111       When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
112       ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
113       needed; 4 (8) for a trailing size field and 8 (16) bytes for
114       free list pointers. Thus, the minimum allocatable size is
115       16/24/32 bytes.
116
117       Even a request for zero bytes (i.e., malloc(0)) returns a
118       pointer to something of the minimum allocatable size.
119
120       The maximum overhead wastage (i.e., number of extra bytes
121       allocated than were requested in malloc) is less than or equal
122       to the minimum size, except for requests >= mmap_threshold that
123       are serviced via mmap(), where the worst case wastage is 2 *
124       sizeof(size_t) bytes plus the remainder from a system page (the
125       minimal mmap unit); typically 4096 or 8192 bytes.
126
127  Maximum allocated size:  4-byte size_t: 2^32 minus about two pages
128			   8-byte size_t: 2^64 minus about two pages
129
130       It is assumed that (possibly signed) size_t values suffice to
131       represent chunk sizes. `Possibly signed' is due to the fact
132       that `size_t' may be defined on a system as either a signed or
133       an unsigned type. The ISO C standard says that it must be
134       unsigned, but a few systems are known not to adhere to this.
135       Additionally, even when size_t is unsigned, sbrk (which is by
136       default used to obtain memory from system) accepts signed
137       arguments, and may not be able to handle size_t-wide arguments
138       with negative sign bit.  Generally, values that would
139       appear as negative after accounting for overhead and alignment
140       are supported only via mmap(), which does not have this
141       limitation.
142
143       Requests for sizes outside the allowed range will perform an optional
144       failure action and then return null. (Requests may also
145       also fail because a system is out of memory.)
146
147  Thread-safety: thread-safe
148
149  Compliance: I believe it is compliant with the 1997 Single Unix Specification
150       Also SVID/XPG, ANSI C, and probably others as well.
151
152* Synopsis of compile-time options:
153
154    People have reported using previous versions of this malloc on all
155    versions of Unix, sometimes by tweaking some of the defines
156    below. It has been tested most extensively on Solaris and Linux.
157    People also report using it in stand-alone embedded systems.
158
159    The implementation is in straight, hand-tuned ANSI C.  It is not
160    at all modular. (Sorry!)  It uses a lot of macros.  To be at all
161    usable, this code should be compiled using an optimizing compiler
162    (for example gcc -O3) that can simplify expressions and control
163    paths. (FAQ: some macros import variables as arguments rather than
164    declare locals because people reported that some debuggers
165    otherwise get confused.)
166
167    OPTION                     DEFAULT VALUE
168
169    Compilation Environment options:
170
171    HAVE_MREMAP                0
172
173    Changing default word sizes:
174
175    INTERNAL_SIZE_T            size_t
176    MALLOC_ALIGNMENT           MAX (2 * sizeof(INTERNAL_SIZE_T),
177				    __alignof__ (long double))
178
179    Configuration and functionality options:
180
181    USE_PUBLIC_MALLOC_WRAPPERS NOT defined
182    USE_MALLOC_LOCK            NOT defined
183    MALLOC_DEBUG               NOT defined
184    REALLOC_ZERO_BYTES_FREES   1
185    TRIM_FASTBINS              0
186
187    Options for customizing MORECORE:
188
189    MORECORE                   sbrk
190    MORECORE_FAILURE           -1
191    MORECORE_CONTIGUOUS        1
192    MORECORE_CANNOT_TRIM       NOT defined
193    MORECORE_CLEARS            1
194    MMAP_AS_MORECORE_SIZE      (1024 * 1024)
195
196    Tuning options that are also dynamically changeable via mallopt:
197
198    DEFAULT_MXFAST             64 (for 32bit), 128 (for 64bit)
199    DEFAULT_TRIM_THRESHOLD     128 * 1024
200    DEFAULT_TOP_PAD            0
201    DEFAULT_MMAP_THRESHOLD     128 * 1024
202    DEFAULT_MMAP_MAX           65536
203
204    There are several other #defined constants and macros that you
205    probably don't want to touch unless you are extending or adapting malloc.  */
206
207/*
208  void* is the pointer type that malloc should say it returns
209*/
210
211#ifndef void
212#define void      void
213#endif /*void*/
214
215#include <stddef.h>   /* for size_t */
216#include <stdlib.h>   /* for getenv(), abort() */
217#include <unistd.h>   /* for __libc_enable_secure */
218
219#include <malloc-machine.h>
220#include <malloc-sysdep.h>
221
222#include <atomic.h>
223#include <_itoa.h>
224#include <bits/wordsize.h>
225#include <sys/sysinfo.h>
226
227#include <ldsodefs.h>
228
229#include <unistd.h>
230#include <stdio.h>    /* needed for malloc_stats */
231#include <errno.h>
232
233#include <shlib-compat.h>
234
235/* For uintptr_t.  */
236#include <stdint.h>
237
238/* For va_arg, va_start, va_end.  */
239#include <stdarg.h>
240
241/* For MIN, MAX, powerof2.  */
242#include <sys/param.h>
243
244/* For ALIGN_UP et. al.  */
245#include <libc-internal.h>
246
247
248/*
249  Debugging:
250
251  Because freed chunks may be overwritten with bookkeeping fields, this
252  malloc will often die when freed memory is overwritten by user
253  programs.  This can be very effective (albeit in an annoying way)
254  in helping track down dangling pointers.
255
256  If you compile with -DMALLOC_DEBUG, a number of assertion checks are
257  enabled that will catch more memory errors. You probably won't be
258  able to make much sense of the actual assertion errors, but they
259  should help you locate incorrectly overwritten memory.  The checking
260  is fairly extensive, and will slow down execution
261  noticeably. Calling malloc_stats or mallinfo with MALLOC_DEBUG set
262  will attempt to check every non-mmapped allocated and free chunk in
263  the course of computing the summmaries. (By nature, mmapped regions
264  cannot be checked very much automatically.)
265
266  Setting MALLOC_DEBUG may also be helpful if you are trying to modify
267  this code. The assertions in the check routines spell out in more
268  detail the assumptions and invariants underlying the algorithms.
269
270  Setting MALLOC_DEBUG does NOT provide an automated mechanism for
271  checking that all accesses to malloced memory stay within their
272  bounds. However, there are several add-ons and adaptations of this
273  or other mallocs available that do this.
274*/
275
276#ifndef MALLOC_DEBUG
277#define MALLOC_DEBUG 0
278#endif
279
280#ifdef NDEBUG
281# define assert(expr) ((void) 0)
282#else
283# define assert(expr) \
284  ((expr)								      \
285   ? ((void) 0)								      \
286   : __malloc_assert (#expr, __FILE__, __LINE__, __func__))
287
288extern const char *__progname;
289
290static void
291__malloc_assert (const char *assertion, const char *file, unsigned int line,
292		 const char *function)
293{
294  (void) __fxprintf (NULL, "%s%s%s:%u: %s%sAssertion `%s' failed.\n",
295		     __progname, __progname[0] ? ": " : "",
296		     file, line,
297		     function ? function : "", function ? ": " : "",
298		     assertion);
299  fflush (stderr);
300  abort ();
301}
302#endif
303
304
305/*
306  INTERNAL_SIZE_T is the word-size used for internal bookkeeping
307  of chunk sizes.
308
309  The default version is the same as size_t.
310
311  While not strictly necessary, it is best to define this as an
312  unsigned type, even if size_t is a signed type. This may avoid some
313  artificial size limitations on some systems.
314
315  On a 64-bit machine, you may be able to reduce malloc overhead by
316  defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
317  expense of not being able to handle more than 2^32 of malloced
318  space. If this limitation is acceptable, you are encouraged to set
319  this unless you are on a platform requiring 16byte alignments. In
320  this case the alignment requirements turn out to negate any
321  potential advantages of decreasing size_t word size.
322
323  Implementors: Beware of the possible combinations of:
324     - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
325       and might be the same width as int or as long
326     - size_t might have different width and signedness as INTERNAL_SIZE_T
327     - int and long might be 32 or 64 bits, and might be the same width
328  To deal with this, most comparisons and difference computations
329  among INTERNAL_SIZE_Ts should cast them to unsigned long, being
330  aware of the fact that casting an unsigned int to a wider long does
331  not sign-extend. (This also makes checking for negative numbers
332  awkward.) Some of these casts result in harmless compiler warnings
333  on some systems.
334*/
335
336#ifndef INTERNAL_SIZE_T
337#define INTERNAL_SIZE_T size_t
338#endif
339
340/* The corresponding word size */
341#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
342
343
344/*
345  MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
346  It must be a power of two at least 2 * SIZE_SZ, even on machines
347  for which smaller alignments would suffice. It may be defined as
348  larger than this though. Note however that code and data structures
349  are optimized for the case of 8-byte alignment.
350*/
351
352
353#ifndef MALLOC_ALIGNMENT
354# if !SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_16)
355/* This is the correct definition when there is no past ABI to constrain it.
356
357   Among configurations with a past ABI constraint, it differs from
358   2*SIZE_SZ only on powerpc32.  For the time being, changing this is
359   causing more compatibility problems due to malloc_get_state and
360   malloc_set_state than will returning blocks not adequately aligned for
361   long double objects under -mlong-double-128.  */
362
363#  define MALLOC_ALIGNMENT       (2 *SIZE_SZ < __alignof__ (long double)      \
364                                  ? __alignof__ (long double) : 2 *SIZE_SZ)
365# else
366#  define MALLOC_ALIGNMENT       (2 *SIZE_SZ)
367# endif
368#endif
369
370/* The corresponding bit mask value */
371#define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
372
373
374
375/*
376  REALLOC_ZERO_BYTES_FREES should be set if a call to
377  realloc with zero bytes should be the same as a call to free.
378  This is required by the C standard. Otherwise, since this malloc
379  returns a unique pointer for malloc(0), so does realloc(p, 0).
380*/
381
382#ifndef REALLOC_ZERO_BYTES_FREES
383#define REALLOC_ZERO_BYTES_FREES 1
384#endif
385
386/*
387  TRIM_FASTBINS controls whether free() of a very small chunk can
388  immediately lead to trimming. Setting to true (1) can reduce memory
389  footprint, but will almost always slow down programs that use a lot
390  of small chunks.
391
392  Define this only if you are willing to give up some speed to more
393  aggressively reduce system-level memory footprint when releasing
394  memory in programs that use many small chunks.  You can get
395  essentially the same effect by setting MXFAST to 0, but this can
396  lead to even greater slowdowns in programs using many small chunks.
397  TRIM_FASTBINS is an in-between compile-time option, that disables
398  only those chunks bordering topmost memory from being placed in
399  fastbins.
400*/
401
402#ifndef TRIM_FASTBINS
403#define TRIM_FASTBINS  0
404#endif
405
406
407/* Definition for getting more memory from the OS.  */
408#define MORECORE         (*__morecore)
409#define MORECORE_FAILURE 0
410void * __default_morecore (ptrdiff_t);
411void *(*__morecore)(ptrdiff_t) = __default_morecore;
412
413
414#include <string.h>
415
416/*
417  MORECORE-related declarations. By default, rely on sbrk
418*/
419
420
421/*
422  MORECORE is the name of the routine to call to obtain more memory
423  from the system.  See below for general guidance on writing
424  alternative MORECORE functions, as well as a version for WIN32 and a
425  sample version for pre-OSX macos.
426*/
427
428#ifndef MORECORE
429#define MORECORE sbrk
430#endif
431
432/*
433  MORECORE_FAILURE is the value returned upon failure of MORECORE
434  as well as mmap. Since it cannot be an otherwise valid memory address,
435  and must reflect values of standard sys calls, you probably ought not
436  try to redefine it.
437*/
438
439#ifndef MORECORE_FAILURE
440#define MORECORE_FAILURE (-1)
441#endif
442
443/*
444  If MORECORE_CONTIGUOUS is true, take advantage of fact that
445  consecutive calls to MORECORE with positive arguments always return
446  contiguous increasing addresses.  This is true of unix sbrk.  Even
447  if not defined, when regions happen to be contiguous, malloc will
448  permit allocations spanning regions obtained from different
449  calls. But defining this when applicable enables some stronger
450  consistency checks and space efficiencies.
451*/
452
453#ifndef MORECORE_CONTIGUOUS
454#define MORECORE_CONTIGUOUS 1
455#endif
456
457/*
458  Define MORECORE_CANNOT_TRIM if your version of MORECORE
459  cannot release space back to the system when given negative
460  arguments. This is generally necessary only if you are using
461  a hand-crafted MORECORE function that cannot handle negative arguments.
462*/
463
464/* #define MORECORE_CANNOT_TRIM */
465
466/*  MORECORE_CLEARS           (default 1)
467     The degree to which the routine mapped to MORECORE zeroes out
468     memory: never (0), only for newly allocated space (1) or always
469     (2).  The distinction between (1) and (2) is necessary because on
470     some systems, if the application first decrements and then
471     increments the break value, the contents of the reallocated space
472     are unspecified.
473 */
474
475#ifndef MORECORE_CLEARS
476# define MORECORE_CLEARS 1
477#endif
478
479
480/*
481   MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
482   sbrk fails, and mmap is used as a backup.  The value must be a
483   multiple of page size.  This backup strategy generally applies only
484   when systems have "holes" in address space, so sbrk cannot perform
485   contiguous expansion, but there is still space available on system.
486   On systems for which this is known to be useful (i.e. most linux
487   kernels), this occurs only when programs allocate huge amounts of
488   memory.  Between this, and the fact that mmap regions tend to be
489   limited, the size should be large, to avoid too many mmap calls and
490   thus avoid running out of kernel resources.  */
491
492#ifndef MMAP_AS_MORECORE_SIZE
493#define MMAP_AS_MORECORE_SIZE (1024 * 1024)
494#endif
495
496/*
497  Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
498  large blocks.
499*/
500
501#ifndef HAVE_MREMAP
502#define HAVE_MREMAP 0
503#endif
504
505
506/*
507  This version of malloc supports the standard SVID/XPG mallinfo
508  routine that returns a struct containing usage properties and
509  statistics. It should work on any SVID/XPG compliant system that has
510  a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
511  install such a thing yourself, cut out the preliminary declarations
512  as described above and below and save them in a malloc.h file. But
513  there's no compelling reason to bother to do this.)
514
515  The main declaration needed is the mallinfo struct that is returned
516  (by-copy) by mallinfo().  The SVID/XPG malloinfo struct contains a
517  bunch of fields that are not even meaningful in this version of
518  malloc.  These fields are are instead filled by mallinfo() with
519  other numbers that might be of interest.
520*/
521
522
523/* ---------- description of public routines ------------ */
524
525/*
526  malloc(size_t n)
527  Returns a pointer to a newly allocated chunk of at least n bytes, or null
528  if no space is available. Additionally, on failure, errno is
529  set to ENOMEM on ANSI C systems.
530
531  If n is zero, malloc returns a minumum-sized chunk. (The minimum
532  size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
533  systems.)  On most systems, size_t is an unsigned type, so calls
534  with negative arguments are interpreted as requests for huge amounts
535  of space, which will often fail. The maximum supported value of n
536  differs across systems, but is in all cases less than the maximum
537  representable value of a size_t.
538*/
539void*  __libc_malloc(size_t);
540libc_hidden_proto (__libc_malloc)
541
542/*
543  free(void* p)
544  Releases the chunk of memory pointed to by p, that had been previously
545  allocated using malloc or a related routine such as realloc.
546  It has no effect if p is null. It can have arbitrary (i.e., bad!)
547  effects if p has already been freed.
548
549  Unless disabled (using mallopt), freeing very large spaces will
550  when possible, automatically trigger operations that give
551  back unused memory to the system, thus reducing program footprint.
552*/
553void     __libc_free(void*);
554libc_hidden_proto (__libc_free)
555
556/*
557  calloc(size_t n_elements, size_t element_size);
558  Returns a pointer to n_elements * element_size bytes, with all locations
559  set to zero.
560*/
561void*  __libc_calloc(size_t, size_t);
562
563/*
564  realloc(void* p, size_t n)
565  Returns a pointer to a chunk of size n that contains the same data
566  as does chunk p up to the minimum of (n, p's size) bytes, or null
567  if no space is available.
568
569  The returned pointer may or may not be the same as p. The algorithm
570  prefers extending p when possible, otherwise it employs the
571  equivalent of a malloc-copy-free sequence.
572
573  If p is null, realloc is equivalent to malloc.
574
575  If space is not available, realloc returns null, errno is set (if on
576  ANSI) and p is NOT freed.
577
578  if n is for fewer bytes than already held by p, the newly unused
579  space is lopped off and freed if possible.  Unless the #define
580  REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
581  zero (re)allocates a minimum-sized chunk.
582
583  Large chunks that were internally obtained via mmap will always
584  be reallocated using malloc-copy-free sequences unless
585  the system supports MREMAP (currently only linux).
586
587  The old unix realloc convention of allowing the last-free'd chunk
588  to be used as an argument to realloc is not supported.
589*/
590void*  __libc_realloc(void*, size_t);
591libc_hidden_proto (__libc_realloc)
592
593/*
594  memalign(size_t alignment, size_t n);
595  Returns a pointer to a newly allocated chunk of n bytes, aligned
596  in accord with the alignment argument.
597
598  The alignment argument should be a power of two. If the argument is
599  not a power of two, the nearest greater power is used.
600  8-byte alignment is guaranteed by normal malloc calls, so don't
601  bother calling memalign with an argument of 8 or less.
602
603  Overreliance on memalign is a sure way to fragment space.
604*/
605void*  __libc_memalign(size_t, size_t);
606libc_hidden_proto (__libc_memalign)
607
608/*
609  valloc(size_t n);
610  Equivalent to memalign(pagesize, n), where pagesize is the page
611  size of the system. If the pagesize is unknown, 4096 is used.
612*/
613void*  __libc_valloc(size_t);
614
615
616
617/*
618  mallopt(int parameter_number, int parameter_value)
619  Sets tunable parameters The format is to provide a
620  (parameter-number, parameter-value) pair.  mallopt then sets the
621  corresponding parameter to the argument value if it can (i.e., so
622  long as the value is meaningful), and returns 1 if successful else
623  0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,
624  normally defined in malloc.h.  Only one of these (M_MXFAST) is used
625  in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
626  so setting them has no effect. But this malloc also supports four
627  other options in mallopt. See below for details.  Briefly, supported
628  parameters are as follows (listed defaults are for "typical"
629  configurations).
630
631  Symbol            param #   default    allowed param values
632  M_MXFAST          1         64         0-80  (0 disables fastbins)
633  M_TRIM_THRESHOLD -1         128*1024   any   (-1U disables trimming)
634  M_TOP_PAD        -2         0          any
635  M_MMAP_THRESHOLD -3         128*1024   any   (or 0 if no MMAP support)
636  M_MMAP_MAX       -4         65536      any   (0 disables use of mmap)
637*/
638int      __libc_mallopt(int, int);
639libc_hidden_proto (__libc_mallopt)
640
641
642/*
643  mallinfo()
644  Returns (by copy) a struct containing various summary statistics:
645
646  arena:     current total non-mmapped bytes allocated from system
647  ordblks:   the number of free chunks
648  smblks:    the number of fastbin blocks (i.e., small chunks that
649	       have been freed but not use resused or consolidated)
650  hblks:     current number of mmapped regions
651  hblkhd:    total bytes held in mmapped regions
652  usmblks:   the maximum total allocated space. This will be greater
653		than current total if trimming has occurred.
654  fsmblks:   total bytes held in fastbin blocks
655  uordblks:  current total allocated space (normal or mmapped)
656  fordblks:  total free space
657  keepcost:  the maximum number of bytes that could ideally be released
658	       back to system via malloc_trim. ("ideally" means that
659	       it ignores page restrictions etc.)
660
661  Because these fields are ints, but internal bookkeeping may
662  be kept as longs, the reported values may wrap around zero and
663  thus be inaccurate.
664*/
665struct mallinfo __libc_mallinfo(void);
666
667
668/*
669  pvalloc(size_t n);
670  Equivalent to valloc(minimum-page-that-holds(n)), that is,
671  round up n to nearest pagesize.
672 */
673void*  __libc_pvalloc(size_t);
674
675/*
676  malloc_trim(size_t pad);
677
678  If possible, gives memory back to the system (via negative
679  arguments to sbrk) if there is unused memory at the `high' end of
680  the malloc pool. You can call this after freeing large blocks of
681  memory to potentially reduce the system-level memory requirements
682  of a program. However, it cannot guarantee to reduce memory. Under
683  some allocation patterns, some large free blocks of memory will be
684  locked between two used chunks, so they cannot be given back to
685  the system.
686
687  The `pad' argument to malloc_trim represents the amount of free
688  trailing space to leave untrimmed. If this argument is zero,
689  only the minimum amount of memory to maintain internal data
690  structures will be left (one page or less). Non-zero arguments
691  can be supplied to maintain enough trailing space to service
692  future expected allocations without having to re-obtain memory
693  from the system.
694
695  Malloc_trim returns 1 if it actually released any memory, else 0.
696  On systems that do not support "negative sbrks", it will always
697  return 0.
698*/
699int      __malloc_trim(size_t);
700
701/*
702  malloc_usable_size(void* p);
703
704  Returns the number of bytes you can actually use in
705  an allocated chunk, which may be more than you requested (although
706  often not) due to alignment and minimum size constraints.
707  You can use this many bytes without worrying about
708  overwriting other allocated objects. This is not a particularly great
709  programming practice. malloc_usable_size can be more useful in
710  debugging and assertions, for example:
711
712  p = malloc(n);
713  assert(malloc_usable_size(p) >= 256);
714
715*/
716size_t   __malloc_usable_size(void*);
717
718/*
719  malloc_stats();
720  Prints on stderr the amount of space obtained from the system (both
721  via sbrk and mmap), the maximum amount (which may be more than
722  current if malloc_trim and/or munmap got called), and the current
723  number of bytes allocated via malloc (or realloc, etc) but not yet
724  freed. Note that this is the number of bytes allocated, not the
725  number requested. It will be larger than the number requested
726  because of alignment and bookkeeping overhead. Because it includes
727  alignment wastage as being in use, this figure may be greater than
728  zero even when no user-level chunks are allocated.
729
730  The reported current and maximum system memory can be inaccurate if
731  a program makes other calls to system memory allocation functions
732  (normally sbrk) outside of malloc.
733
734  malloc_stats prints only the most commonly interesting statistics.
735  More information can be obtained by calling mallinfo.
736
737*/
738void     __malloc_stats(void);
739
740/*
741  malloc_get_state(void);
742
743  Returns the state of all malloc variables in an opaque data
744  structure.
745*/
746void*  __malloc_get_state(void);
747
748/*
749  malloc_set_state(void* state);
750
751  Restore the state of all malloc variables from data obtained with
752  malloc_get_state().
753*/
754int      __malloc_set_state(void*);
755
756/*
757  posix_memalign(void **memptr, size_t alignment, size_t size);
758
759  POSIX wrapper like memalign(), checking for validity of size.
760*/
761int      __posix_memalign(void **, size_t, size_t);
762
763/* mallopt tuning options */
764
765/*
766  M_MXFAST is the maximum request size used for "fastbins", special bins
767  that hold returned chunks without consolidating their spaces. This
768  enables future requests for chunks of the same size to be handled
769  very quickly, but can increase fragmentation, and thus increase the
770  overall memory footprint of a program.
771
772  This malloc manages fastbins very conservatively yet still
773  efficiently, so fragmentation is rarely a problem for values less
774  than or equal to the default.  The maximum supported value of MXFAST
775  is 80. You wouldn't want it any higher than this anyway.  Fastbins
776  are designed especially for use with many small structs, objects or
777  strings -- the default handles structs/objects/arrays with sizes up
778  to 8 4byte fields, or small strings representing words, tokens,
779  etc. Using fastbins for larger objects normally worsens
780  fragmentation without improving speed.
781
782  M_MXFAST is set in REQUEST size units. It is internally used in
783  chunksize units, which adds padding and alignment.  You can reduce
784  M_MXFAST to 0 to disable all use of fastbins.  This causes the malloc
785  algorithm to be a closer approximation of fifo-best-fit in all cases,
786  not just for larger requests, but will generally cause it to be
787  slower.
788*/
789
790
791/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
792#ifndef M_MXFAST
793#define M_MXFAST            1
794#endif
795
796#ifndef DEFAULT_MXFAST
797#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)
798#endif
799
800
801/*
802  M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
803  to keep before releasing via malloc_trim in free().
804
805  Automatic trimming is mainly useful in long-lived programs.
806  Because trimming via sbrk can be slow on some systems, and can
807  sometimes be wasteful (in cases where programs immediately
808  afterward allocate more large chunks) the value should be high
809  enough so that your overall system performance would improve by
810  releasing this much memory.
811
812  The trim threshold and the mmap control parameters (see below)
813  can be traded off with one another. Trimming and mmapping are
814  two different ways of releasing unused memory back to the
815  system. Between these two, it is often possible to keep
816  system-level demands of a long-lived program down to a bare
817  minimum. For example, in one test suite of sessions measuring
818  the XF86 X server on Linux, using a trim threshold of 128K and a
819  mmap threshold of 192K led to near-minimal long term resource
820  consumption.
821
822  If you are using this malloc in a long-lived program, it should
823  pay to experiment with these values.  As a rough guide, you
824  might set to a value close to the average size of a process
825  (program) running on your system.  Releasing this much memory
826  would allow such a process to run in memory.  Generally, it's
827  worth it to tune for trimming rather tham memory mapping when a
828  program undergoes phases where several large chunks are
829  allocated and released in ways that can reuse each other's
830  storage, perhaps mixed with phases where there are no such
831  chunks at all.  And in well-behaved long-lived programs,
832  controlling release of large blocks via trimming versus mapping
833  is usually faster.
834
835  However, in most programs, these parameters serve mainly as
836  protection against the system-level effects of carrying around
837  massive amounts of unneeded memory. Since frequent calls to
838  sbrk, mmap, and munmap otherwise degrade performance, the default
839  parameters are set to relatively high values that serve only as
840  safeguards.
841
842  The trim value It must be greater than page size to have any useful
843  effect.  To disable trimming completely, you can set to
844  (unsigned long)(-1)
845
846  Trim settings interact with fastbin (MXFAST) settings: Unless
847  TRIM_FASTBINS is defined, automatic trimming never takes place upon
848  freeing a chunk with size less than or equal to MXFAST. Trimming is
849  instead delayed until subsequent freeing of larger chunks. However,
850  you can still force an attempted trim by calling malloc_trim.
851
852  Also, trimming is not generally possible in cases where
853  the main arena is obtained via mmap.
854
855  Note that the trick some people use of mallocing a huge space and
856  then freeing it at program startup, in an attempt to reserve system
857  memory, doesn't have the intended effect under automatic trimming,
858  since that memory will immediately be returned to the system.
859*/
860
861#define M_TRIM_THRESHOLD       -1
862
863#ifndef DEFAULT_TRIM_THRESHOLD
864#define DEFAULT_TRIM_THRESHOLD (128 * 1024)
865#endif
866
867/*
868  M_TOP_PAD is the amount of extra `padding' space to allocate or
869  retain whenever sbrk is called. It is used in two ways internally:
870
871  * When sbrk is called to extend the top of the arena to satisfy
872  a new malloc request, this much padding is added to the sbrk
873  request.
874
875  * When malloc_trim is called automatically from free(),
876  it is used as the `pad' argument.
877
878  In both cases, the actual amount of padding is rounded
879  so that the end of the arena is always a system page boundary.
880
881  The main reason for using padding is to avoid calling sbrk so
882  often. Having even a small pad greatly reduces the likelihood
883  that nearly every malloc request during program start-up (or
884  after trimming) will invoke sbrk, which needlessly wastes
885  time.
886
887  Automatic rounding-up to page-size units is normally sufficient
888  to avoid measurable overhead, so the default is 0.  However, in
889  systems where sbrk is relatively slow, it can pay to increase
890  this value, at the expense of carrying around more memory than
891  the program needs.
892*/
893
894#define M_TOP_PAD              -2
895
896#ifndef DEFAULT_TOP_PAD
897#define DEFAULT_TOP_PAD        (0)
898#endif
899
900/*
901  MMAP_THRESHOLD_MAX and _MIN are the bounds on the dynamically
902  adjusted MMAP_THRESHOLD.
903*/
904
905#ifndef DEFAULT_MMAP_THRESHOLD_MIN
906#define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
907#endif
908
909#ifndef DEFAULT_MMAP_THRESHOLD_MAX
910  /* For 32-bit platforms we cannot increase the maximum mmap
911     threshold much because it is also the minimum value for the
912     maximum heap size and its alignment.  Going above 512k (i.e., 1M
913     for new heaps) wastes too much address space.  */
914# if __WORDSIZE == 32
915#  define DEFAULT_MMAP_THRESHOLD_MAX (512 * 1024)
916# else
917#  define DEFAULT_MMAP_THRESHOLD_MAX (4 * 1024 * 1024 * sizeof(long))
918# endif
919#endif
920
921/*
922  M_MMAP_THRESHOLD is the request size threshold for using mmap()
923  to service a request. Requests of at least this size that cannot
924  be allocated using already-existing space will be serviced via mmap.
925  (If enough normal freed space already exists it is used instead.)
926
927  Using mmap segregates relatively large chunks of memory so that
928  they can be individually obtained and released from the host
929  system. A request serviced through mmap is never reused by any
930  other request (at least not directly; the system may just so
931  happen to remap successive requests to the same locations).
932
933  Segregating space in this way has the benefits that:
934
935   1. Mmapped space can ALWAYS be individually released back
936      to the system, which helps keep the system level memory
937      demands of a long-lived program low.
938   2. Mapped memory can never become `locked' between
939      other chunks, as can happen with normally allocated chunks, which
940      means that even trimming via malloc_trim would not release them.
941   3. On some systems with "holes" in address spaces, mmap can obtain
942      memory that sbrk cannot.
943
944  However, it has the disadvantages that:
945
946   1. The space cannot be reclaimed, consolidated, and then
947      used to service later requests, as happens with normal chunks.
948   2. It can lead to more wastage because of mmap page alignment
949      requirements
950   3. It causes malloc performance to be more dependent on host
951      system memory management support routines which may vary in
952      implementation quality and may impose arbitrary
953      limitations. Generally, servicing a request via normal
954      malloc steps is faster than going through a system's mmap.
955
956  The advantages of mmap nearly always outweigh disadvantages for
957  "large" chunks, but the value of "large" varies across systems.  The
958  default is an empirically derived value that works well in most
959  systems.
960
961
962  Update in 2006:
963  The above was written in 2001. Since then the world has changed a lot.
964  Memory got bigger. Applications got bigger. The virtual address space
965  layout in 32 bit linux changed.
966
967  In the new situation, brk() and mmap space is shared and there are no
968  artificial limits on brk size imposed by the kernel. What is more,
969  applications have started using transient allocations larger than the
970  128Kb as was imagined in 2001.
971
972  The price for mmap is also high now; each time glibc mmaps from the
973  kernel, the kernel is forced to zero out the memory it gives to the
974  application. Zeroing memory is expensive and eats a lot of cache and
975  memory bandwidth. This has nothing to do with the efficiency of the
976  virtual memory system, by doing mmap the kernel just has no choice but
977  to zero.
978
979  In 2001, the kernel had a maximum size for brk() which was about 800
980  megabytes on 32 bit x86, at that point brk() would hit the first
981  mmaped shared libaries and couldn't expand anymore. With current 2.6
982  kernels, the VA space layout is different and brk() and mmap
983  both can span the entire heap at will.
984
985  Rather than using a static threshold for the brk/mmap tradeoff,
986  we are now using a simple dynamic one. The goal is still to avoid
987  fragmentation. The old goals we kept are
988  1) try to get the long lived large allocations to use mmap()
989  2) really large allocations should always use mmap()
990  and we're adding now:
991  3) transient allocations should use brk() to avoid forcing the kernel
992     having to zero memory over and over again
993
994  The implementation works with a sliding threshold, which is by default
995  limited to go between 128Kb and 32Mb (64Mb for 64 bitmachines) and starts
996  out at 128Kb as per the 2001 default.
997
998  This allows us to satisfy requirement 1) under the assumption that long
999  lived allocations are made early in the process' lifespan, before it has
1000  started doing dynamic allocations of the same size (which will
1001  increase the threshold).
1002
1003  The upperbound on the threshold satisfies requirement 2)
1004
1005  The threshold goes up in value when the application frees memory that was
1006  allocated with the mmap allocator. The idea is that once the application
1007  starts freeing memory of a certain size, it's highly probable that this is
1008  a size the application uses for transient allocations. This estimator
1009  is there to satisfy the new third requirement.
1010
1011*/
1012
1013#define M_MMAP_THRESHOLD      -3
1014
1015#ifndef DEFAULT_MMAP_THRESHOLD
1016#define DEFAULT_MMAP_THRESHOLD DEFAULT_MMAP_THRESHOLD_MIN
1017#endif
1018
1019/*
1020  M_MMAP_MAX is the maximum number of requests to simultaneously
1021  service using mmap. This parameter exists because
1022  some systems have a limited number of internal tables for
1023  use by mmap, and using more than a few of them may degrade
1024  performance.
1025
1026  The default is set to a value that serves only as a safeguard.
1027  Setting to 0 disables use of mmap for servicing large requests.
1028*/
1029
1030#define M_MMAP_MAX             -4
1031
1032#ifndef DEFAULT_MMAP_MAX
1033#define DEFAULT_MMAP_MAX       (65536)
1034#endif
1035
1036#include <malloc.h>
1037
1038#ifndef RETURN_ADDRESS
1039#define RETURN_ADDRESS(X_) (NULL)
1040#endif
1041
1042/* On some platforms we can compile internal, not exported functions better.
1043   Let the environment provide a macro and define it to be empty if it
1044   is not available.  */
1045#ifndef internal_function
1046# define internal_function
1047#endif
1048
1049/* Forward declarations.  */
1050struct malloc_chunk;
1051typedef struct malloc_chunk* mchunkptr;
1052
1053/* Internal routines.  */
1054
1055static void*  _int_malloc(mstate, size_t);
1056static void     _int_free(mstate, mchunkptr, int);
1057static void*  _int_realloc(mstate, mchunkptr, INTERNAL_SIZE_T,
1058			   INTERNAL_SIZE_T);
1059static void*  _int_memalign(mstate, size_t, size_t);
1060static void*  _mid_memalign(size_t, size_t, void *);
1061
1062static void malloc_printerr(int action, const char *str, void *ptr, mstate av);
1063
1064static void* internal_function mem2mem_check(void *p, size_t sz);
1065static int internal_function top_check(void);
1066static void internal_function munmap_chunk(mchunkptr p);
1067#if HAVE_MREMAP
1068static mchunkptr internal_function mremap_chunk(mchunkptr p, size_t new_size);
1069#endif
1070
1071static void*   malloc_check(size_t sz, const void *caller);
1072static void      free_check(void* mem, const void *caller);
1073static void*   realloc_check(void* oldmem, size_t bytes,
1074			       const void *caller);
1075static void*   memalign_check(size_t alignment, size_t bytes,
1076				const void *caller);
1077#ifndef NO_THREADS
1078static void*   malloc_atfork(size_t sz, const void *caller);
1079static void      free_atfork(void* mem, const void *caller);
1080#endif
1081
1082/* ------------------ MMAP support ------------------  */
1083
1084
1085#include <fcntl.h>
1086#include <sys/mman.h>
1087
1088#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1089# define MAP_ANONYMOUS MAP_ANON
1090#endif
1091
1092#ifndef MAP_NORESERVE
1093# define MAP_NORESERVE 0
1094#endif
1095
1096#define MMAP(addr, size, prot, flags) \
1097 __mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_PRIVATE, -1, 0)
1098
1099
1100/*
1101  -----------------------  Chunk representations -----------------------
1102*/
1103
1104
1105/*
1106  This struct declaration is misleading (but accurate and necessary).
1107  It declares a "view" into memory allowing access to necessary
1108  fields at known offsets from a given base. See explanation below.
1109*/
1110
1111struct malloc_chunk {
1112
1113  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
1114  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
1115
1116  struct malloc_chunk* fd;         /* double links -- used only if free. */
1117  struct malloc_chunk* bk;
1118
1119  /* Only used for large blocks: pointer to next larger size.  */
1120  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
1121  struct malloc_chunk* bk_nextsize;
1122};
1123
1124
1125/*
1126   malloc_chunk details:
1127
1128    (The following includes lightly edited explanations by Colin Plumb.)
1129
1130    Chunks of memory are maintained using a `boundary tag' method as
1131    described in e.g., Knuth or Standish.  (See the paper by Paul
1132    Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1133    survey of such techniques.)  Sizes of free chunks are stored both
1134    in the front of each chunk and at the end.  This makes
1135    consolidating fragmented chunks into bigger chunks very fast.  The
1136    size fields also hold bits representing whether chunks are free or
1137    in use.
1138
1139    An allocated chunk looks like this:
1140
1141
1142    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1143	    |             Size of previous chunk, if allocated            | |
1144	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1145	    |             Size of chunk, in bytes                       |M|P|
1146      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1147	    |             User data starts here...                          .
1148	    .                                                               .
1149	    .             (malloc_usable_size() bytes)                      .
1150	    .                                                               |
1151nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1152	    |             Size of chunk                                     |
1153	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1154
1155
1156    Where "chunk" is the front of the chunk for the purpose of most of
1157    the malloc code, but "mem" is the pointer that is returned to the
1158    user.  "Nextchunk" is the beginning of the next contiguous chunk.
1159
1160    Chunks always begin on even word boundaries, so the mem portion
1161    (which is returned to the user) is also on an even word boundary, and
1162    thus at least double-word aligned.
1163
1164    Free chunks are stored in circular doubly-linked lists, and look like this:
1165
1166    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1167	    |             Size of previous chunk                            |
1168	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1169    `head:' |             Size of chunk, in bytes                         |P|
1170      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1171	    |             Forward pointer to next chunk in list             |
1172	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1173	    |             Back pointer to previous chunk in list            |
1174	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1175	    |             Unused space (may be 0 bytes long)                .
1176	    .                                                               .
1177	    .                                                               |
1178nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1179    `foot:' |             Size of chunk, in bytes                           |
1180	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1181
1182    The P (PREV_INUSE) bit, stored in the unused low-order bit of the
1183    chunk size (which is always a multiple of two words), is an in-use
1184    bit for the *previous* chunk.  If that bit is *clear*, then the
1185    word before the current chunk size contains the previous chunk
1186    size, and can be used to find the front of the previous chunk.
1187    The very first chunk allocated always has this bit set,
1188    preventing access to non-existent (or non-owned) memory. If
1189    prev_inuse is set for any given chunk, then you CANNOT determine
1190    the size of the previous chunk, and might even get a memory
1191    addressing fault when trying to do so.
1192
1193    Note that the `foot' of the current chunk is actually represented
1194    as the prev_size of the NEXT chunk. This makes it easier to
1195    deal with alignments etc but can be very confusing when trying
1196    to extend or adapt this code.
1197
1198    The two exceptions to all this are
1199
1200     1. The special chunk `top' doesn't bother using the
1201	trailing size field since there is no next contiguous chunk
1202	that would have to index off it. After initialization, `top'
1203	is forced to always exist.  If it would become less than
1204	MINSIZE bytes long, it is replenished.
1205
1206     2. Chunks allocated via mmap, which have the second-lowest-order
1207	bit M (IS_MMAPPED) set in their size fields.  Because they are
1208	allocated one-by-one, each must contain its own trailing size field.
1209
1210*/
1211
1212/*
1213  ---------- Size and alignment checks and conversions ----------
1214*/
1215
1216/* conversion from malloc headers to user pointers, and back */
1217
1218#define chunk2mem(p)   ((void*)((char*)(p) + 2*SIZE_SZ))
1219#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
1220
1221/* The smallest possible chunk */
1222#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))
1223
1224/* The smallest size we can malloc is an aligned minimal chunk */
1225
1226#define MINSIZE  \
1227  (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1228
1229/* Check if m has acceptable alignment */
1230
1231#define aligned_OK(m)  (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
1232
1233#define misaligned_chunk(p) \
1234  ((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
1235   & MALLOC_ALIGN_MASK)
1236
1237
1238/*
1239   Check if a request is so large that it would wrap around zero when
1240   padded and aligned. To simplify some other code, the bound is made
1241   low enough so that adding MINSIZE will also not wrap around zero.
1242 */
1243
1244#define REQUEST_OUT_OF_RANGE(req)                                 \
1245  ((unsigned long) (req) >=						      \
1246   (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
1247
1248/* pad request bytes into a usable size -- internal version */
1249
1250#define request2size(req)                                         \
1251  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
1252   MINSIZE :                                                      \
1253   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
1254
1255/*  Same, except also perform argument check */
1256
1257#define checked_request2size(req, sz)                             \
1258  if (REQUEST_OUT_OF_RANGE (req)) {					      \
1259      __set_errno (ENOMEM);						      \
1260      return 0;								      \
1261    }									      \
1262  (sz) = request2size (req);
1263
1264/*
1265   --------------- Physical chunk operations ---------------
1266 */
1267
1268
1269/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1270#define PREV_INUSE 0x1
1271
1272/* extract inuse bit of previous chunk */
1273#define prev_inuse(p)       ((p)->size & PREV_INUSE)
1274
1275
1276/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1277#define IS_MMAPPED 0x2
1278
1279/* check for mmap()'ed chunk */
1280#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1281
1282
1283/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
1284   from a non-main arena.  This is only set immediately before handing
1285   the chunk to the user, if necessary.  */
1286#define NON_MAIN_ARENA 0x4
1287
1288/* check for chunk from non-main arena */
1289#define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)
1290
1291
1292/*
1293   Bits to mask off when extracting size
1294
1295   Note: IS_MMAPPED is intentionally not masked off from size field in
1296   macros for which mmapped chunks should never be seen. This should
1297   cause helpful core dumps to occur if it is tried by accident by
1298   people extending or adapting this malloc.
1299 */
1300#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
1301
1302/* Get size, ignoring use bits */
1303#define chunksize(p)         ((p)->size & ~(SIZE_BITS))
1304
1305
1306/* Ptr to next physical malloc_chunk. */
1307#define next_chunk(p) ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))
1308
1309/* Ptr to previous physical malloc_chunk */
1310#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - ((p)->prev_size)))
1311
1312/* Treat space at ptr + offset as a chunk */
1313#define chunk_at_offset(p, s)  ((mchunkptr) (((char *) (p)) + (s)))
1314
1315/* extract p's inuse bit */
1316#define inuse(p)							      \
1317  ((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
1318
1319/* set/clear chunk as being inuse without otherwise disturbing */
1320#define set_inuse(p)							      \
1321  ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
1322
1323#define clear_inuse(p)							      \
1324  ((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
1325
1326
1327/* check/set/clear inuse bits in known places */
1328#define inuse_bit_at_offset(p, s)					      \
1329  (((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
1330
1331#define set_inuse_bit_at_offset(p, s)					      \
1332  (((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)
1333
1334#define clear_inuse_bit_at_offset(p, s)					      \
1335  (((mchunkptr) (((char *) (p)) + (s)))->size &= ~(PREV_INUSE))
1336
1337
1338/* Set size at head, without disturbing its use bit */
1339#define set_head_size(p, s)  ((p)->size = (((p)->size & SIZE_BITS) | (s)))
1340
1341/* Set size/use field */
1342#define set_head(p, s)       ((p)->size = (s))
1343
1344/* Set size at footer (only when chunk is not in use) */
1345#define set_foot(p, s)       (((mchunkptr) ((char *) (p) + (s)))->prev_size = (s))
1346
1347
1348/*
1349   -------------------- Internal data structures --------------------
1350
1351   All internal state is held in an instance of malloc_state defined
1352   below. There are no other static variables, except in two optional
1353   cases:
1354 * If USE_MALLOC_LOCK is defined, the mALLOC_MUTEx declared above.
1355 * If mmap doesn't support MAP_ANONYMOUS, a dummy file descriptor
1356     for mmap.
1357
1358   Beware of lots of tricks that minimize the total bookkeeping space
1359   requirements. The result is a little over 1K bytes (for 4byte
1360   pointers and size_t.)
1361 */
1362
1363/*
1364   Bins
1365
1366    An array of bin headers for free chunks. Each bin is doubly
1367    linked.  The bins are approximately proportionally (log) spaced.
1368    There are a lot of these bins (128). This may look excessive, but
1369    works very well in practice.  Most bins hold sizes that are
1370    unusual as malloc request sizes, but are more usual for fragments
1371    and consolidated sets of chunks, which is what these bins hold, so
1372    they can be found quickly.  All procedures maintain the invariant
1373    that no consolidated chunk physically borders another one, so each
1374    chunk in a list is known to be preceeded and followed by either
1375    inuse chunks or the ends of memory.
1376
1377    Chunks in bins are kept in size order, with ties going to the
1378    approximately least recently used chunk. Ordering isn't needed
1379    for the small bins, which all contain the same-sized chunks, but
1380    facilitates best-fit allocation for larger chunks. These lists
1381    are just sequential. Keeping them in order almost never requires
1382    enough traversal to warrant using fancier ordered data
1383    structures.
1384
1385    Chunks of the same size are linked with the most
1386    recently freed at the front, and allocations are taken from the
1387    back.  This results in LRU (FIFO) allocation order, which tends
1388    to give each chunk an equal opportunity to be consolidated with
1389    adjacent freed chunks, resulting in larger free chunks and less
1390    fragmentation.
1391
1392    To simplify use in double-linked lists, each bin header acts
1393    as a malloc_chunk. This avoids special-casing for headers.
1394    But to conserve space and improve locality, we allocate
1395    only the fd/bk pointers of bins, and then use repositioning tricks
1396    to treat these as the fields of a malloc_chunk*.
1397 */
1398
1399typedef struct malloc_chunk *mbinptr;
1400
1401/* addressing -- note that bin_at(0) does not exist */
1402#define bin_at(m, i) \
1403  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			      \
1404             - offsetof (struct malloc_chunk, fd))
1405
1406/* analog of ++bin */
1407#define next_bin(b)  ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))
1408
1409/* Reminders about list directionality within bins */
1410#define first(b)     ((b)->fd)
1411#define last(b)      ((b)->bk)
1412
1413/* Take a chunk off a bin list */
1414#define unlink(AV, P, BK, FD) {                                            \
1415    FD = P->fd;								      \
1416    BK = P->bk;								      \
1417    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))		      \
1418      malloc_printerr (check_action, "corrupted double-linked list", P, AV);  \
1419    else {								      \
1420        FD->bk = BK;							      \
1421        BK->fd = FD;							      \
1422        if (!in_smallbin_range (P->size)				      \
1423            && __builtin_expect (P->fd_nextsize != NULL, 0)) {		      \
1424	    if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)	      \
1425		|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
1426	      malloc_printerr (check_action,				      \
1427			       "corrupted double-linked list (not small)",    \
1428			       P, AV);					      \
1429            if (FD->fd_nextsize == NULL) {				      \
1430                if (P->fd_nextsize == P)				      \
1431                  FD->fd_nextsize = FD->bk_nextsize = FD;		      \
1432                else {							      \
1433                    FD->fd_nextsize = P->fd_nextsize;			      \
1434                    FD->bk_nextsize = P->bk_nextsize;			      \
1435                    P->fd_nextsize->bk_nextsize = FD;			      \
1436                    P->bk_nextsize->fd_nextsize = FD;			      \
1437                  }							      \
1438              } else {							      \
1439                P->fd_nextsize->bk_nextsize = P->bk_nextsize;		      \
1440                P->bk_nextsize->fd_nextsize = P->fd_nextsize;		      \
1441              }								      \
1442          }								      \
1443      }									      \
1444}
1445
1446/*
1447   Indexing
1448
1449    Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1450    8 bytes apart. Larger bins are approximately logarithmically spaced:
1451
1452    64 bins of size       8
1453    32 bins of size      64
1454    16 bins of size     512
1455     8 bins of size    4096
1456     4 bins of size   32768
1457     2 bins of size  262144
1458     1 bin  of size what's left
1459
1460    There is actually a little bit of slop in the numbers in bin_index
1461    for the sake of speed. This makes no difference elsewhere.
1462
1463    The bins top out around 1MB because we expect to service large
1464    requests via mmap.
1465
1466    Bin 0 does not exist.  Bin 1 is the unordered list; if that would be
1467    a valid chunk size the small bins are bumped up one.
1468 */
1469
1470#define NBINS             128
1471#define NSMALLBINS         64
1472#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
1473#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
1474#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
1475
1476#define in_smallbin_range(sz)  \
1477  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
1478
1479#define smallbin_index(sz) \
1480  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
1481   + SMALLBIN_CORRECTION)
1482
1483#define largebin_index_32(sz)                                                \
1484  (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
1485   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
1486   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1487   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1488   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1489   126)
1490
1491#define largebin_index_32_big(sz)                                            \
1492  (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((unsigned long) (sz)) >> 6) :\
1493   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
1494   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1495   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1496   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1497   126)
1498
1499// XXX It remains to be seen whether it is good to keep the widths of
1500// XXX the buckets the same or whether it should be scaled by a factor
1501// XXX of two as well.
1502#define largebin_index_64(sz)                                                \
1503  (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
1504   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
1505   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1506   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1507   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1508   126)
1509
1510#define largebin_index(sz) \
1511  (SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
1512   : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
1513   : largebin_index_32 (sz))
1514
1515#define bin_index(sz) \
1516  ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))
1517
1518
1519/*
1520   Unsorted chunks
1521
1522    All remainders from chunk splits, as well as all returned chunks,
1523    are first placed in the "unsorted" bin. They are then placed
1524    in regular bins after malloc gives them ONE chance to be used before
1525    binning. So, basically, the unsorted_chunks list acts as a queue,
1526    with chunks being placed on it in free (and malloc_consolidate),
1527    and taken off (to be either used or placed in bins) in malloc.
1528
1529    The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
1530    does not have to be taken into account in size comparisons.
1531 */
1532
1533/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
1534#define unsorted_chunks(M)          (bin_at (M, 1))
1535
1536/*
1537   Top
1538
1539    The top-most available chunk (i.e., the one bordering the end of
1540    available memory) is treated specially. It is never included in
1541    any bin, is used only if no other chunk is available, and is
1542    released back to the system if it is very large (see
1543    M_TRIM_THRESHOLD).  Because top initially
1544    points to its own bin with initial zero size, thus forcing
1545    extension on the first malloc request, we avoid having any special
1546    code in malloc to check whether it even exists yet. But we still
1547    need to do so when getting memory from system, so we make
1548    initial_top treat the bin as a legal but unusable chunk during the
1549    interval between initialization and the first call to
1550    sysmalloc. (This is somewhat delicate, since it relies on
1551    the 2 preceding words to be zero during this interval as well.)
1552 */
1553
1554/* Conveniently, the unsorted bin can be used as dummy top on first call */
1555#define initial_top(M)              (unsorted_chunks (M))
1556
1557/*
1558   Binmap
1559
1560    To help compensate for the large number of bins, a one-level index
1561    structure is used for bin-by-bin searching.  `binmap' is a
1562    bitvector recording whether bins are definitely empty so they can
1563    be skipped over during during traversals.  The bits are NOT always
1564    cleared as soon as bins are empty, but instead only
1565    when they are noticed to be empty during traversal in malloc.
1566 */
1567
1568/* Conservatively use 32 bits per map word, even if on 64bit system */
1569#define BINMAPSHIFT      5
1570#define BITSPERMAP       (1U << BINMAPSHIFT)
1571#define BINMAPSIZE       (NBINS / BITSPERMAP)
1572
1573#define idx2block(i)     ((i) >> BINMAPSHIFT)
1574#define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
1575
1576#define mark_bin(m, i)    ((m)->binmap[idx2block (i)] |= idx2bit (i))
1577#define unmark_bin(m, i)  ((m)->binmap[idx2block (i)] &= ~(idx2bit (i)))
1578#define get_binmap(m, i)  ((m)->binmap[idx2block (i)] & idx2bit (i))
1579
1580/*
1581   Fastbins
1582
1583    An array of lists holding recently freed small chunks.  Fastbins
1584    are not doubly linked.  It is faster to single-link them, and
1585    since chunks are never removed from the middles of these lists,
1586    double linking is not necessary. Also, unlike regular bins, they
1587    are not even processed in FIFO order (they use faster LIFO) since
1588    ordering doesn't much matter in the transient contexts in which
1589    fastbins are normally used.
1590
1591    Chunks in fastbins keep their inuse bit set, so they cannot
1592    be consolidated with other free chunks. malloc_consolidate
1593    releases all chunks in fastbins and consolidates them with
1594    other free chunks.
1595 */
1596
1597typedef struct malloc_chunk *mfastbinptr;
1598#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
1599
1600/* offset 2 to use otherwise unindexable first 2 bins */
1601#define fastbin_index(sz) \
1602  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
1603
1604
1605/* The maximum fastbin request size we support */
1606#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)
1607
1608#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
1609
1610/*
1611   FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
1612   that triggers automatic consolidation of possibly-surrounding
1613   fastbin chunks. This is a heuristic, so the exact value should not
1614   matter too much. It is defined at half the default trim threshold as a
1615   compromise heuristic to only attempt consolidation if it is likely
1616   to lead to trimming. However, it is not dynamically tunable, since
1617   consolidation reduces fragmentation surrounding large chunks even
1618   if trimming is not used.
1619 */
1620
1621#define FASTBIN_CONSOLIDATION_THRESHOLD  (65536UL)
1622
1623/*
1624   Since the lowest 2 bits in max_fast don't matter in size comparisons,
1625   they are used as flags.
1626 */
1627
1628/*
1629   FASTCHUNKS_BIT held in max_fast indicates that there are probably
1630   some fastbin chunks. It is set true on entering a chunk into any
1631   fastbin, and cleared only in malloc_consolidate.
1632
1633   The truth value is inverted so that have_fastchunks will be true
1634   upon startup (since statics are zero-filled), simplifying
1635   initialization checks.
1636 */
1637
1638#define FASTCHUNKS_BIT        (1U)
1639
1640#define have_fastchunks(M)     (((M)->flags & FASTCHUNKS_BIT) == 0)
1641#define clear_fastchunks(M)    catomic_or (&(M)->flags, FASTCHUNKS_BIT)
1642#define set_fastchunks(M)      catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
1643
1644/*
1645   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
1646   regions.  Otherwise, contiguity is exploited in merging together,
1647   when possible, results from consecutive MORECORE calls.
1648
1649   The initial value comes from MORECORE_CONTIGUOUS, but is
1650   changed dynamically if mmap is ever used as an sbrk substitute.
1651 */
1652
1653#define NONCONTIGUOUS_BIT     (2U)
1654
1655#define contiguous(M)          (((M)->flags & NONCONTIGUOUS_BIT) == 0)
1656#define noncontiguous(M)       (((M)->flags & NONCONTIGUOUS_BIT) != 0)
1657#define set_noncontiguous(M)   ((M)->flags |= NONCONTIGUOUS_BIT)
1658#define set_contiguous(M)      ((M)->flags &= ~NONCONTIGUOUS_BIT)
1659
1660/* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the
1661   arena.  Such an arena is no longer used to allocate chunks.  Chunks
1662   allocated in that arena before detecting corruption are not freed.  */
1663
1664#define ARENA_CORRUPTION_BIT (4U)
1665
1666#define arena_is_corrupt(A)	(((A)->flags & ARENA_CORRUPTION_BIT))
1667#define set_arena_corrupt(A)	((A)->flags |= ARENA_CORRUPTION_BIT)
1668
1669/*
1670   Set value of max_fast.
1671   Use impossibly small value if 0.
1672   Precondition: there are no existing fastbin chunks.
1673   Setting the value clears fastchunk bit but preserves noncontiguous bit.
1674 */
1675
1676#define set_max_fast(s) \
1677  global_max_fast = (((s) == 0)						      \
1678                     ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
1679#define get_max_fast() global_max_fast
1680
1681
1682/*
1683   ----------- Internal state representation and initialization -----------
1684 */
1685
1686struct malloc_state
1687{
1688  /* Serialize access.  */
1689  mutex_t mutex;
1690
1691  /* Flags (formerly in max_fast).  */
1692  int flags;
1693
1694  /* Fastbins */
1695  mfastbinptr fastbinsY[NFASTBINS];
1696
1697  /* Base of the topmost chunk -- not otherwise kept in a bin */
1698  mchunkptr top;
1699
1700  /* The remainder from the most recent split of a small request */
1701  mchunkptr last_remainder;
1702
1703  /* Normal bins packed as described above */
1704  mchunkptr bins[NBINS * 2 - 2];
1705
1706  /* Bitmap of bins */
1707  unsigned int binmap[BINMAPSIZE];
1708
1709  /* Linked list */
1710  struct malloc_state *next;
1711
1712  /* Linked list for free arenas.  Access to this field is serialized
1713     by list_lock in arena.c.  */
1714  struct malloc_state *next_free;
1715
1716  /* Number of threads attached to this arena.  0 if the arena is on
1717     the free list.  Access to this field is serialized by list_lock
1718     in arena.c.  */
1719  INTERNAL_SIZE_T attached_threads;
1720
1721  /* Memory allocated from the system in this arena.  */
1722  INTERNAL_SIZE_T system_mem;
1723  INTERNAL_SIZE_T max_system_mem;
1724};
1725
1726struct malloc_par
1727{
1728  /* Tunable parameters */
1729  unsigned long trim_threshold;
1730  INTERNAL_SIZE_T top_pad;
1731  INTERNAL_SIZE_T mmap_threshold;
1732  INTERNAL_SIZE_T arena_test;
1733  INTERNAL_SIZE_T arena_max;
1734
1735  /* Memory map support */
1736  int n_mmaps;
1737  int n_mmaps_max;
1738  int max_n_mmaps;
1739  /* the mmap_threshold is dynamic, until the user sets
1740     it manually, at which point we need to disable any
1741     dynamic behavior. */
1742  int no_dyn_threshold;
1743
1744  /* Statistics */
1745  INTERNAL_SIZE_T mmapped_mem;
1746  /*INTERNAL_SIZE_T  sbrked_mem;*/
1747  /*INTERNAL_SIZE_T  max_sbrked_mem;*/
1748  INTERNAL_SIZE_T max_mmapped_mem;
1749  INTERNAL_SIZE_T max_total_mem;  /* only kept for NO_THREADS */
1750
1751  /* First address handed out by MORECORE/sbrk.  */
1752  char *sbrk_base;
1753};
1754
1755/* There are several instances of this struct ("arenas") in this
1756   malloc.  If you are adapting this malloc in a way that does NOT use
1757   a static or mmapped malloc_state, you MUST explicitly zero-fill it
1758   before using. This malloc relies on the property that malloc_state
1759   is initialized to all zeroes (as is true of C statics).  */
1760
1761static struct malloc_state main_arena =
1762{
1763  .mutex = _LIBC_LOCK_INITIALIZER,
1764  .next = &main_arena,
1765  .attached_threads = 1
1766};
1767
1768/* There is only one instance of the malloc parameters.  */
1769
1770static struct malloc_par mp_ =
1771{
1772  .top_pad = DEFAULT_TOP_PAD,
1773  .n_mmaps_max = DEFAULT_MMAP_MAX,
1774  .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
1775  .trim_threshold = DEFAULT_TRIM_THRESHOLD,
1776#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
1777  .arena_test = NARENAS_FROM_NCORES (1)
1778};
1779
1780
1781/*  Non public mallopt parameters.  */
1782#define M_ARENA_TEST -7
1783#define M_ARENA_MAX  -8
1784
1785
1786/* Maximum size of memory handled in fastbins.  */
1787static INTERNAL_SIZE_T global_max_fast;
1788
1789/*
1790   Initialize a malloc_state struct.
1791
1792   This is called only from within malloc_consolidate, which needs
1793   be called in the same contexts anyway.  It is never called directly
1794   outside of malloc_consolidate because some optimizing compilers try
1795   to inline it at all call points, which turns out not to be an
1796   optimization at all. (Inlining it in malloc_consolidate is fine though.)
1797 */
1798
1799static void
1800malloc_init_state (mstate av)
1801{
1802  int i;
1803  mbinptr bin;
1804
1805  /* Establish circular links for normal bins */
1806  for (i = 1; i < NBINS; ++i)
1807    {
1808      bin = bin_at (av, i);
1809      bin->fd = bin->bk = bin;
1810    }
1811
1812#if MORECORE_CONTIGUOUS
1813  if (av != &main_arena)
1814#endif
1815  set_noncontiguous (av);
1816  if (av == &main_arena)
1817    set_max_fast (DEFAULT_MXFAST);
1818  av->flags |= FASTCHUNKS_BIT;
1819
1820  av->top = initial_top (av);
1821}
1822
1823/*
1824   Other internal utilities operating on mstates
1825 */
1826
1827static void *sysmalloc (INTERNAL_SIZE_T, mstate);
1828static int      systrim (size_t, mstate);
1829static void     malloc_consolidate (mstate);
1830
1831
1832/* -------------- Early definitions for debugging hooks ---------------- */
1833
1834/* Define and initialize the hook variables.  These weak definitions must
1835   appear before any use of the variables in a function (arena.c uses one).  */
1836#ifndef weak_variable
1837/* In GNU libc we want the hook variables to be weak definitions to
1838   avoid a problem with Emacs.  */
1839# define weak_variable weak_function
1840#endif
1841
1842/* Forward declarations.  */
1843static void *malloc_hook_ini (size_t sz,
1844                              const void *caller) __THROW;
1845static void *realloc_hook_ini (void *ptr, size_t sz,
1846                               const void *caller) __THROW;
1847static void *memalign_hook_ini (size_t alignment, size_t sz,
1848                                const void *caller) __THROW;
1849
1850void weak_variable (*__malloc_initialize_hook) (void) = NULL;
1851void weak_variable (*__free_hook) (void *__ptr,
1852                                   const void *) = NULL;
1853void *weak_variable (*__malloc_hook)
1854  (size_t __size, const void *) = malloc_hook_ini;
1855void *weak_variable (*__realloc_hook)
1856  (void *__ptr, size_t __size, const void *)
1857  = realloc_hook_ini;
1858void *weak_variable (*__memalign_hook)
1859  (size_t __alignment, size_t __size, const void *)
1860  = memalign_hook_ini;
1861void weak_variable (*__after_morecore_hook) (void) = NULL;
1862
1863
1864/* ---------------- Error behavior ------------------------------------ */
1865
1866#ifndef DEFAULT_CHECK_ACTION
1867# define DEFAULT_CHECK_ACTION 3
1868#endif
1869
1870static int check_action = DEFAULT_CHECK_ACTION;
1871
1872
1873/* ------------------ Testing support ----------------------------------*/
1874
1875static int perturb_byte;
1876
1877static void
1878alloc_perturb (char *p, size_t n)
1879{
1880  if (__glibc_unlikely (perturb_byte))
1881    memset (p, perturb_byte ^ 0xff, n);
1882}
1883
1884static void
1885free_perturb (char *p, size_t n)
1886{
1887  if (__glibc_unlikely (perturb_byte))
1888    memset (p, perturb_byte, n);
1889}
1890
1891
1892
1893#include <stap-probe.h>
1894
1895/* ------------------- Support for multiple arenas -------------------- */
1896#include "arena.c"
1897
1898/*
1899   Debugging support
1900
1901   These routines make a number of assertions about the states
1902   of data structures that should be true at all times. If any
1903   are not true, it's very likely that a user program has somehow
1904   trashed memory. (It's also possible that there is a coding error
1905   in malloc. In which case, please report it!)
1906 */
1907
1908#if !MALLOC_DEBUG
1909
1910# define check_chunk(A, P)
1911# define check_free_chunk(A, P)
1912# define check_inuse_chunk(A, P)
1913# define check_remalloced_chunk(A, P, N)
1914# define check_malloced_chunk(A, P, N)
1915# define check_malloc_state(A)
1916
1917#else
1918
1919# define check_chunk(A, P)              do_check_chunk (A, P)
1920# define check_free_chunk(A, P)         do_check_free_chunk (A, P)
1921# define check_inuse_chunk(A, P)        do_check_inuse_chunk (A, P)
1922# define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
1923# define check_malloced_chunk(A, P, N)   do_check_malloced_chunk (A, P, N)
1924# define check_malloc_state(A)         do_check_malloc_state (A)
1925
1926/*
1927   Properties of all chunks
1928 */
1929
1930static void
1931do_check_chunk (mstate av, mchunkptr p)
1932{
1933  unsigned long sz = chunksize (p);
1934  /* min and max possible addresses assuming contiguous allocation */
1935  char *max_address = (char *) (av->top) + chunksize (av->top);
1936  char *min_address = max_address - av->system_mem;
1937
1938  if (!chunk_is_mmapped (p))
1939    {
1940      /* Has legal address ... */
1941      if (p != av->top)
1942        {
1943          if (contiguous (av))
1944            {
1945              assert (((char *) p) >= min_address);
1946              assert (((char *) p + sz) <= ((char *) (av->top)));
1947            }
1948        }
1949      else
1950        {
1951          /* top size is always at least MINSIZE */
1952          assert ((unsigned long) (sz) >= MINSIZE);
1953          /* top predecessor always marked inuse */
1954          assert (prev_inuse (p));
1955        }
1956    }
1957  else
1958    {
1959      /* address is outside main heap  */
1960      if (contiguous (av) && av->top != initial_top (av))
1961        {
1962          assert (((char *) p) < min_address || ((char *) p) >= max_address);
1963        }
1964      /* chunk is page-aligned */
1965      assert (((p->prev_size + sz) & (GLRO (dl_pagesize) - 1)) == 0);
1966      /* mem is aligned */
1967      assert (aligned_OK (chunk2mem (p)));
1968    }
1969}
1970
1971/*
1972   Properties of free chunks
1973 */
1974
1975static void
1976do_check_free_chunk (mstate av, mchunkptr p)
1977{
1978  INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
1979  mchunkptr next = chunk_at_offset (p, sz);
1980
1981  do_check_chunk (av, p);
1982
1983  /* Chunk must claim to be free ... */
1984  assert (!inuse (p));
1985  assert (!chunk_is_mmapped (p));
1986
1987  /* Unless a special marker, must have OK fields */
1988  if ((unsigned long) (sz) >= MINSIZE)
1989    {
1990      assert ((sz & MALLOC_ALIGN_MASK) == 0);
1991      assert (aligned_OK (chunk2mem (p)));
1992      /* ... matching footer field */
1993      assert (next->prev_size == sz);
1994      /* ... and is fully consolidated */
1995      assert (prev_inuse (p));
1996      assert (next == av->top || inuse (next));
1997
1998      /* ... and has minimally sane links */
1999      assert (p->fd->bk == p);
2000      assert (p->bk->fd == p);
2001    }
2002  else /* markers are always of size SIZE_SZ */
2003    assert (sz == SIZE_SZ);
2004}
2005
2006/*
2007   Properties of inuse chunks
2008 */
2009
2010static void
2011do_check_inuse_chunk (mstate av, mchunkptr p)
2012{
2013  mchunkptr next;
2014
2015  do_check_chunk (av, p);
2016
2017  if (chunk_is_mmapped (p))
2018    return; /* mmapped chunks have no next/prev */
2019
2020  /* Check whether it claims to be in use ... */
2021  assert (inuse (p));
2022
2023  next = next_chunk (p);
2024
2025  /* ... and is surrounded by OK chunks.
2026     Since more things can be checked with free chunks than inuse ones,
2027     if an inuse chunk borders them and debug is on, it's worth doing them.
2028   */
2029  if (!prev_inuse (p))
2030    {
2031      /* Note that we cannot even look at prev unless it is not inuse */
2032      mchunkptr prv = prev_chunk (p);
2033      assert (next_chunk (prv) == p);
2034      do_check_free_chunk (av, prv);
2035    }
2036
2037  if (next == av->top)
2038    {
2039      assert (prev_inuse (next));
2040      assert (chunksize (next) >= MINSIZE);
2041    }
2042  else if (!inuse (next))
2043    do_check_free_chunk (av, next);
2044}
2045
2046/*
2047   Properties of chunks recycled from fastbins
2048 */
2049
2050static void
2051do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2052{
2053  INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
2054
2055  if (!chunk_is_mmapped (p))
2056    {
2057      assert (av == arena_for_chunk (p));
2058      if (chunk_non_main_arena (p))
2059        assert (av != &main_arena);
2060      else
2061        assert (av == &main_arena);
2062    }
2063
2064  do_check_inuse_chunk (av, p);
2065
2066  /* Legal size ... */
2067  assert ((sz & MALLOC_ALIGN_MASK) == 0);
2068  assert ((unsigned long) (sz) >= MINSIZE);
2069  /* ... and alignment */
2070  assert (aligned_OK (chunk2mem (p)));
2071  /* chunk is less than MINSIZE more than request */
2072  assert ((long) (sz) - (long) (s) >= 0);
2073  assert ((long) (sz) - (long) (s + MINSIZE) < 0);
2074}
2075
2076/*
2077   Properties of nonrecycled chunks at the point they are malloced
2078 */
2079
2080static void
2081do_check_malloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
2082{
2083  /* same as recycled case ... */
2084  do_check_remalloced_chunk (av, p, s);
2085
2086  /*
2087     ... plus,  must obey implementation invariant that prev_inuse is
2088     always true of any allocated chunk; i.e., that each allocated
2089     chunk borders either a previously allocated and still in-use
2090     chunk, or the base of its memory arena. This is ensured
2091     by making all allocations from the `lowest' part of any found
2092     chunk.  This does not necessarily hold however for chunks
2093     recycled via fastbins.
2094   */
2095
2096  assert (prev_inuse (p));
2097}
2098
2099
2100/*
2101   Properties of malloc_state.
2102
2103   This may be useful for debugging malloc, as well as detecting user
2104   programmer errors that somehow write into malloc_state.
2105
2106   If you are extending or experimenting with this malloc, you can
2107   probably figure out how to hack this routine to print out or
2108   display chunk addresses, sizes, bins, and other instrumentation.
2109 */
2110
2111static void
2112do_check_malloc_state (mstate av)
2113{
2114  int i;
2115  mchunkptr p;
2116  mchunkptr q;
2117  mbinptr b;
2118  unsigned int idx;
2119  INTERNAL_SIZE_T size;
2120  unsigned long total = 0;
2121  int max_fast_bin;
2122
2123  /* internal size_t must be no wider than pointer type */
2124  assert (sizeof (INTERNAL_SIZE_T) <= sizeof (char *));
2125
2126  /* alignment is a power of 2 */
2127  assert ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT - 1)) == 0);
2128
2129  /* cannot run remaining checks until fully initialized */
2130  if (av->top == 0 || av->top == initial_top (av))
2131    return;
2132
2133  /* pagesize is a power of 2 */
2134  assert (powerof2(GLRO (dl_pagesize)));
2135
2136  /* A contiguous main_arena is consistent with sbrk_base.  */
2137  if (av == &main_arena && contiguous (av))
2138    assert ((char *) mp_.sbrk_base + av->system_mem ==
2139            (char *) av->top + chunksize (av->top));
2140
2141  /* properties of fastbins */
2142
2143  /* max_fast is in allowed range */
2144  assert ((get_max_fast () & ~1) <= request2size (MAX_FAST_SIZE));
2145
2146  max_fast_bin = fastbin_index (get_max_fast ());
2147
2148  for (i = 0; i < NFASTBINS; ++i)
2149    {
2150      p = fastbin (av, i);
2151
2152      /* The following test can only be performed for the main arena.
2153         While mallopt calls malloc_consolidate to get rid of all fast
2154         bins (especially those larger than the new maximum) this does
2155         only happen for the main arena.  Trying to do this for any
2156         other arena would mean those arenas have to be locked and
2157         malloc_consolidate be called for them.  This is excessive.  And
2158         even if this is acceptable to somebody it still cannot solve
2159         the problem completely since if the arena is locked a
2160         concurrent malloc call might create a new arena which then
2161         could use the newly invalid fast bins.  */
2162
2163      /* all bins past max_fast are empty */
2164      if (av == &main_arena && i > max_fast_bin)
2165        assert (p == 0);
2166
2167      while (p != 0)
2168        {
2169          /* each chunk claims to be inuse */
2170          do_check_inuse_chunk (av, p);
2171          total += chunksize (p);
2172          /* chunk belongs in this bin */
2173          assert (fastbin_index (chunksize (p)) == i);
2174          p = p->fd;
2175        }
2176    }
2177
2178  if (total != 0)
2179    assert (have_fastchunks (av));
2180  else if (!have_fastchunks (av))
2181    assert (total == 0);
2182
2183  /* check normal bins */
2184  for (i = 1; i < NBINS; ++i)
2185    {
2186      b = bin_at (av, i);
2187
2188      /* binmap is accurate (except for bin 1 == unsorted_chunks) */
2189      if (i >= 2)
2190        {
2191          unsigned int binbit = get_binmap (av, i);
2192          int empty = last (b) == b;
2193          if (!binbit)
2194            assert (empty);
2195          else if (!empty)
2196            assert (binbit);
2197        }
2198
2199      for (p = last (b); p != b; p = p->bk)
2200        {
2201          /* each chunk claims to be free */
2202          do_check_free_chunk (av, p);
2203          size = chunksize (p);
2204          total += size;
2205          if (i >= 2)
2206            {
2207              /* chunk belongs in bin */
2208              idx = bin_index (size);
2209              assert (idx == i);
2210              /* lists are sorted */
2211              assert (p->bk == b ||
2212                      (unsigned long) chunksize (p->bk) >= (unsigned long) chunksize (p));
2213
2214              if (!in_smallbin_range (size))
2215                {
2216                  if (p->fd_nextsize != NULL)
2217                    {
2218                      if (p->fd_nextsize == p)
2219                        assert (p->bk_nextsize == p);
2220                      else
2221                        {
2222                          if (p->fd_nextsize == first (b))
2223                            assert (chunksize (p) < chunksize (p->fd_nextsize));
2224                          else
2225                            assert (chunksize (p) > chunksize (p->fd_nextsize));
2226
2227                          if (p == first (b))
2228                            assert (chunksize (p) > chunksize (p->bk_nextsize));
2229                          else
2230                            assert (chunksize (p) < chunksize (p->bk_nextsize));
2231                        }
2232                    }
2233                  else
2234                    assert (p->bk_nextsize == NULL);
2235                }
2236            }
2237          else if (!in_smallbin_range (size))
2238            assert (p->fd_nextsize == NULL && p->bk_nextsize == NULL);
2239          /* chunk is followed by a legal chain of inuse chunks */
2240          for (q = next_chunk (p);
2241               (q != av->top && inuse (q) &&
2242                (unsigned long) (chunksize (q)) >= MINSIZE);
2243               q = next_chunk (q))
2244            do_check_inuse_chunk (av, q);
2245        }
2246    }
2247
2248  /* top chunk is OK */
2249  check_chunk (av, av->top);
2250}
2251#endif
2252
2253
2254/* ----------------- Support for debugging hooks -------------------- */
2255#include "hooks.c"
2256
2257
2258/* ----------- Routines dealing with system allocation -------------- */
2259
2260/*
2261   sysmalloc handles malloc cases requiring more memory from the system.
2262   On entry, it is assumed that av->top does not have enough
2263   space to service request for nb bytes, thus requiring that av->top
2264   be extended or replaced.
2265 */
2266
2267static void *
2268sysmalloc (INTERNAL_SIZE_T nb, mstate av)
2269{
2270  mchunkptr old_top;              /* incoming value of av->top */
2271  INTERNAL_SIZE_T old_size;       /* its size */
2272  char *old_end;                  /* its end address */
2273
2274  long size;                      /* arg to first MORECORE or mmap call */
2275  char *brk;                      /* return value from MORECORE */
2276
2277  long correction;                /* arg to 2nd MORECORE call */
2278  char *snd_brk;                  /* 2nd return val */
2279
2280  INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
2281  INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
2282  char *aligned_brk;              /* aligned offset into brk */
2283
2284  mchunkptr p;                    /* the allocated/returned chunk */
2285  mchunkptr remainder;            /* remainder from allocation */
2286  unsigned long remainder_size;   /* its size */
2287
2288
2289  size_t pagesize = GLRO (dl_pagesize);
2290  bool tried_mmap = false;
2291
2292
2293  /*
2294     If have mmap, and the request size meets the mmap threshold, and
2295     the system supports mmap, and there are few enough currently
2296     allocated mmapped regions, try to directly map this request
2297     rather than expanding top.
2298   */
2299
2300  if (av == NULL
2301      || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
2302	  && (mp_.n_mmaps < mp_.n_mmaps_max)))
2303    {
2304      char *mm;           /* return value from mmap call*/
2305
2306    try_mmap:
2307      /*
2308         Round up size to nearest page.  For mmapped chunks, the overhead
2309         is one SIZE_SZ unit larger than for normal chunks, because there
2310         is no following chunk whose prev_size field could be used.
2311
2312         See the front_misalign handling below, for glibc there is no
2313         need for further alignments unless we have have high alignment.
2314       */
2315      if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2316        size = ALIGN_UP (nb + SIZE_SZ, pagesize);
2317      else
2318        size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
2319      tried_mmap = true;
2320
2321      /* Don't try if size wraps around 0 */
2322      if ((unsigned long) (size) > (unsigned long) (nb))
2323        {
2324          mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2325
2326          if (mm != MAP_FAILED)
2327            {
2328              /*
2329                 The offset to the start of the mmapped region is stored
2330                 in the prev_size field of the chunk. This allows us to adjust
2331                 returned start address to meet alignment requirements here
2332                 and in memalign(), and still be able to compute proper
2333                 address argument for later munmap in free() and realloc().
2334               */
2335
2336              if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2337                {
2338                  /* For glibc, chunk2mem increases the address by 2*SIZE_SZ and
2339                     MALLOC_ALIGN_MASK is 2*SIZE_SZ-1.  Each mmap'ed area is page
2340                     aligned and therefore definitely MALLOC_ALIGN_MASK-aligned.  */
2341                  assert (((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
2342                  front_misalign = 0;
2343                }
2344              else
2345                front_misalign = (INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK;
2346              if (front_misalign > 0)
2347                {
2348                  correction = MALLOC_ALIGNMENT - front_misalign;
2349                  p = (mchunkptr) (mm + correction);
2350                  p->prev_size = correction;
2351                  set_head (p, (size - correction) | IS_MMAPPED);
2352                }
2353              else
2354                {
2355                  p = (mchunkptr) mm;
2356                  set_head (p, size | IS_MMAPPED);
2357                }
2358
2359              /* update statistics */
2360
2361              int new = atomic_exchange_and_add (&mp_.n_mmaps, 1) + 1;
2362              atomic_max (&mp_.max_n_mmaps, new);
2363
2364              unsigned long sum;
2365              sum = atomic_exchange_and_add (&mp_.mmapped_mem, size) + size;
2366              atomic_max (&mp_.max_mmapped_mem, sum);
2367
2368              check_chunk (av, p);
2369
2370              return chunk2mem (p);
2371            }
2372        }
2373    }
2374
2375  /* There are no usable arenas and mmap also failed.  */
2376  if (av == NULL)
2377    return 0;
2378
2379  /* Record incoming configuration of top */
2380
2381  old_top = av->top;
2382  old_size = chunksize (old_top);
2383  old_end = (char *) (chunk_at_offset (old_top, old_size));
2384
2385  brk = snd_brk = (char *) (MORECORE_FAILURE);
2386
2387  /*
2388     If not the first time through, we require old_size to be
2389     at least MINSIZE and to have prev_inuse set.
2390   */
2391
2392  assert ((old_top == initial_top (av) && old_size == 0) ||
2393          ((unsigned long) (old_size) >= MINSIZE &&
2394           prev_inuse (old_top) &&
2395           ((unsigned long) old_end & (pagesize - 1)) == 0));
2396
2397  /* Precondition: not enough current space to satisfy nb request */
2398  assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));
2399
2400
2401  if (av != &main_arena)
2402    {
2403      heap_info *old_heap, *heap;
2404      size_t old_heap_size;
2405
2406      /* First try to extend the current heap. */
2407      old_heap = heap_for_ptr (old_top);
2408      old_heap_size = old_heap->size;
2409      if ((long) (MINSIZE + nb - old_size) > 0
2410          && grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
2411        {
2412          av->system_mem += old_heap->size - old_heap_size;
2413          arena_mem += old_heap->size - old_heap_size;
2414          set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
2415                    | PREV_INUSE);
2416        }
2417      else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
2418        {
2419          /* Use a newly allocated heap.  */
2420          heap->ar_ptr = av;
2421          heap->prev = old_heap;
2422          av->system_mem += heap->size;
2423          arena_mem += heap->size;
2424          /* Set up the new top.  */
2425          top (av) = chunk_at_offset (heap, sizeof (*heap));
2426          set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);
2427
2428          /* Setup fencepost and free the old top chunk with a multiple of
2429             MALLOC_ALIGNMENT in size. */
2430          /* The fencepost takes at least MINSIZE bytes, because it might
2431             become the top chunk again later.  Note that a footer is set
2432             up, too, although the chunk is marked in use. */
2433          old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
2434          set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), 0 | PREV_INUSE);
2435          if (old_size >= MINSIZE)
2436            {
2437              set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ) | PREV_INUSE);
2438              set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));
2439              set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
2440              _int_free (av, old_top, 1);
2441            }
2442          else
2443            {
2444              set_head (old_top, (old_size + 2 * SIZE_SZ) | PREV_INUSE);
2445              set_foot (old_top, (old_size + 2 * SIZE_SZ));
2446            }
2447        }
2448      else if (!tried_mmap)
2449        /* We can at least try to use to mmap memory.  */
2450        goto try_mmap;
2451    }
2452  else     /* av == main_arena */
2453
2454
2455    { /* Request enough space for nb + pad + overhead */
2456      size = nb + mp_.top_pad + MINSIZE;
2457
2458      /*
2459         If contiguous, we can subtract out existing space that we hope to
2460         combine with new space. We add it back later only if
2461         we don't actually get contiguous space.
2462       */
2463
2464      if (contiguous (av))
2465        size -= old_size;
2466
2467      /*
2468         Round to a multiple of page size.
2469         If MORECORE is not contiguous, this ensures that we only call it
2470         with whole-page arguments.  And if MORECORE is contiguous and
2471         this is not first time through, this preserves page-alignment of
2472         previous calls. Otherwise, we correct to page-align below.
2473       */
2474
2475      size = ALIGN_UP (size, pagesize);
2476
2477      /*
2478         Don't try to call MORECORE if argument is so big as to appear
2479         negative. Note that since mmap takes size_t arg, it may succeed
2480         below even if we cannot call MORECORE.
2481       */
2482
2483      if (size > 0)
2484        {
2485          brk = (char *) (MORECORE (size));
2486          LIBC_PROBE (memory_sbrk_more, 2, brk, size);
2487        }
2488
2489      if (brk != (char *) (MORECORE_FAILURE))
2490        {
2491          /* Call the `morecore' hook if necessary.  */
2492          void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2493          if (__builtin_expect (hook != NULL, 0))
2494            (*hook)();
2495        }
2496      else
2497        {
2498          /*
2499             If have mmap, try using it as a backup when MORECORE fails or
2500             cannot be used. This is worth doing on systems that have "holes" in
2501             address space, so sbrk cannot extend to give contiguous space, but
2502             space is available elsewhere.  Note that we ignore mmap max count
2503             and threshold limits, since the space will not be used as a
2504             segregated mmap region.
2505           */
2506
2507          /* Cannot merge with old top, so add its size back in */
2508          if (contiguous (av))
2509            size = ALIGN_UP (size + old_size, pagesize);
2510
2511          /* If we are relying on mmap as backup, then use larger units */
2512          if ((unsigned long) (size) < (unsigned long) (MMAP_AS_MORECORE_SIZE))
2513            size = MMAP_AS_MORECORE_SIZE;
2514
2515          /* Don't try if size wraps around 0 */
2516          if ((unsigned long) (size) > (unsigned long) (nb))
2517            {
2518              char *mbrk = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
2519
2520              if (mbrk != MAP_FAILED)
2521                {
2522                  /* We do not need, and cannot use, another sbrk call to find end */
2523                  brk = mbrk;
2524                  snd_brk = brk + size;
2525
2526                  /*
2527                     Record that we no longer have a contiguous sbrk region.
2528                     After the first time mmap is used as backup, we do not
2529                     ever rely on contiguous space since this could incorrectly
2530                     bridge regions.
2531                   */
2532                  set_noncontiguous (av);
2533                }
2534            }
2535        }
2536
2537      if (brk != (char *) (MORECORE_FAILURE))
2538        {
2539          if (mp_.sbrk_base == 0)
2540            mp_.sbrk_base = brk;
2541          av->system_mem += size;
2542
2543          /*
2544             If MORECORE extends previous space, we can likewise extend top size.
2545           */
2546
2547          if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
2548            set_head (old_top, (size + old_size) | PREV_INUSE);
2549
2550          else if (contiguous (av) && old_size && brk < old_end)
2551            {
2552              /* Oops!  Someone else killed our space..  Can't touch anything.  */
2553              malloc_printerr (3, "break adjusted to free malloc space", brk,
2554			       av);
2555            }
2556
2557          /*
2558             Otherwise, make adjustments:
2559
2560           * If the first time through or noncontiguous, we need to call sbrk
2561              just to find out where the end of memory lies.
2562
2563           * We need to ensure that all returned chunks from malloc will meet
2564              MALLOC_ALIGNMENT
2565
2566           * If there was an intervening foreign sbrk, we need to adjust sbrk
2567              request size to account for fact that we will not be able to
2568              combine new space with existing space in old_top.
2569
2570           * Almost all systems internally allocate whole pages at a time, in
2571              which case we might as well use the whole last page of request.
2572              So we allocate enough more memory to hit a page boundary now,
2573              which in turn causes future contiguous calls to page-align.
2574           */
2575
2576          else
2577            {
2578              front_misalign = 0;
2579              end_misalign = 0;
2580              correction = 0;
2581              aligned_brk = brk;
2582
2583              /* handle contiguous cases */
2584              if (contiguous (av))
2585                {
2586                  /* Count foreign sbrk as system_mem.  */
2587                  if (old_size)
2588                    av->system_mem += brk - old_end;
2589
2590                  /* Guarantee alignment of first new chunk made from this space */
2591
2592                  front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2593                  if (front_misalign > 0)
2594                    {
2595                      /*
2596                         Skip over some bytes to arrive at an aligned position.
2597                         We don't need to specially mark these wasted front bytes.
2598                         They will never be accessed anyway because
2599                         prev_inuse of av->top (and any chunk created from its start)
2600                         is always true after initialization.
2601                       */
2602
2603                      correction = MALLOC_ALIGNMENT - front_misalign;
2604                      aligned_brk += correction;
2605                    }
2606
2607                  /*
2608                     If this isn't adjacent to existing space, then we will not
2609                     be able to merge with old_top space, so must add to 2nd request.
2610                   */
2611
2612                  correction += old_size;
2613
2614                  /* Extend the end address to hit a page boundary */
2615                  end_misalign = (INTERNAL_SIZE_T) (brk + size + correction);
2616                  correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;
2617
2618                  assert (correction >= 0);
2619                  snd_brk = (char *) (MORECORE (correction));
2620
2621                  /*
2622                     If can't allocate correction, try to at least find out current
2623                     brk.  It might be enough to proceed without failing.
2624
2625                     Note that if second sbrk did NOT fail, we assume that space
2626                     is contiguous with first sbrk. This is a safe assumption unless
2627                     program is multithreaded but doesn't use locks and a foreign sbrk
2628                     occurred between our first and second calls.
2629                   */
2630
2631                  if (snd_brk == (char *) (MORECORE_FAILURE))
2632                    {
2633                      correction = 0;
2634                      snd_brk = (char *) (MORECORE (0));
2635                    }
2636                  else
2637                    {
2638                      /* Call the `morecore' hook if necessary.  */
2639                      void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2640                      if (__builtin_expect (hook != NULL, 0))
2641                        (*hook)();
2642                    }
2643                }
2644
2645              /* handle non-contiguous cases */
2646              else
2647                {
2648                  if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
2649                    /* MORECORE/mmap must correctly align */
2650                    assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0);
2651                  else
2652                    {
2653                      front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
2654                      if (front_misalign > 0)
2655                        {
2656                          /*
2657                             Skip over some bytes to arrive at an aligned position.
2658                             We don't need to specially mark these wasted front bytes.
2659                             They will never be accessed anyway because
2660                             prev_inuse of av->top (and any chunk created from its start)
2661                             is always true after initialization.
2662                           */
2663
2664                          aligned_brk += MALLOC_ALIGNMENT - front_misalign;
2665                        }
2666                    }
2667
2668                  /* Find out current end of memory */
2669                  if (snd_brk == (char *) (MORECORE_FAILURE))
2670                    {
2671                      snd_brk = (char *) (MORECORE (0));
2672                    }
2673                }
2674
2675              /* Adjust top based on results of second sbrk */
2676              if (snd_brk != (char *) (MORECORE_FAILURE))
2677                {
2678                  av->top = (mchunkptr) aligned_brk;
2679                  set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
2680                  av->system_mem += correction;
2681
2682                  /*
2683                     If not the first time through, we either have a
2684                     gap due to foreign sbrk or a non-contiguous region.  Insert a
2685                     double fencepost at old_top to prevent consolidation with space
2686                     we don't own. These fenceposts are artificial chunks that are
2687                     marked as inuse and are in any case too small to use.  We need
2688                     two to make sizes and alignments work out.
2689                   */
2690
2691                  if (old_size != 0)
2692                    {
2693                      /*
2694                         Shrink old_top to insert fenceposts, keeping size a
2695                         multiple of MALLOC_ALIGNMENT. We know there is at least
2696                         enough space in old_top to do this.
2697                       */
2698                      old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
2699                      set_head (old_top, old_size | PREV_INUSE);
2700
2701                      /*
2702                         Note that the following assignments completely overwrite
2703                         old_top when old_size was previously MINSIZE.  This is
2704                         intentional. We need the fencepost, even if old_top otherwise gets
2705                         lost.
2706                       */
2707                      chunk_at_offset (old_top, old_size)->size =
2708                        (2 * SIZE_SZ) | PREV_INUSE;
2709
2710                      chunk_at_offset (old_top, old_size + 2 * SIZE_SZ)->size =
2711                        (2 * SIZE_SZ) | PREV_INUSE;
2712
2713                      /* If possible, release the rest. */
2714                      if (old_size >= MINSIZE)
2715                        {
2716                          _int_free (av, old_top, 1);
2717                        }
2718                    }
2719                }
2720            }
2721        }
2722    } /* if (av !=  &main_arena) */
2723
2724  if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
2725    av->max_system_mem = av->system_mem;
2726  check_malloc_state (av);
2727
2728  /* finally, do the allocation */
2729  p = av->top;
2730  size = chunksize (p);
2731
2732  /* check that one of the above allocation paths succeeded */
2733  if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
2734    {
2735      remainder_size = size - nb;
2736      remainder = chunk_at_offset (p, nb);
2737      av->top = remainder;
2738      set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
2739      set_head (remainder, remainder_size | PREV_INUSE);
2740      check_malloced_chunk (av, p, nb);
2741      return chunk2mem (p);
2742    }
2743
2744  /* catch all failure paths */
2745  __set_errno (ENOMEM);
2746  return 0;
2747}
2748
2749
2750/*
2751   systrim is an inverse of sorts to sysmalloc.  It gives memory back
2752   to the system (via negative arguments to sbrk) if there is unused
2753   memory at the `high' end of the malloc pool. It is called
2754   automatically by free() when top space exceeds the trim
2755   threshold. It is also called by the public malloc_trim routine.  It
2756   returns 1 if it actually released any memory, else 0.
2757 */
2758
2759static int
2760systrim (size_t pad, mstate av)
2761{
2762  long top_size;         /* Amount of top-most memory */
2763  long extra;            /* Amount to release */
2764  long released;         /* Amount actually released */
2765  char *current_brk;     /* address returned by pre-check sbrk call */
2766  char *new_brk;         /* address returned by post-check sbrk call */
2767  size_t pagesize;
2768  long top_area;
2769
2770  pagesize = GLRO (dl_pagesize);
2771  top_size = chunksize (av->top);
2772
2773  top_area = top_size - MINSIZE - 1;
2774  if (top_area <= pad)
2775    return 0;
2776
2777  /* Release in pagesize units and round down to the nearest page.  */
2778  extra = ALIGN_DOWN(top_area - pad, pagesize);
2779
2780  if (extra == 0)
2781    return 0;
2782
2783  /*
2784     Only proceed if end of memory is where we last set it.
2785     This avoids problems if there were foreign sbrk calls.
2786   */
2787  current_brk = (char *) (MORECORE (0));
2788  if (current_brk == (char *) (av->top) + top_size)
2789    {
2790      /*
2791         Attempt to release memory. We ignore MORECORE return value,
2792         and instead call again to find out where new end of memory is.
2793         This avoids problems if first call releases less than we asked,
2794         of if failure somehow altered brk value. (We could still
2795         encounter problems if it altered brk in some very bad way,
2796         but the only thing we can do is adjust anyway, which will cause
2797         some downstream failure.)
2798       */
2799
2800      MORECORE (-extra);
2801      /* Call the `morecore' hook if necessary.  */
2802      void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
2803      if (__builtin_expect (hook != NULL, 0))
2804        (*hook)();
2805      new_brk = (char *) (MORECORE (0));
2806
2807      LIBC_PROBE (memory_sbrk_less, 2, new_brk, extra);
2808
2809      if (new_brk != (char *) MORECORE_FAILURE)
2810        {
2811          released = (long) (current_brk - new_brk);
2812
2813          if (released != 0)
2814            {
2815              /* Success. Adjust top. */
2816              av->system_mem -= released;
2817              set_head (av->top, (top_size - released) | PREV_INUSE);
2818              check_malloc_state (av);
2819              return 1;
2820            }
2821        }
2822    }
2823  return 0;
2824}
2825
2826static void
2827internal_function
2828munmap_chunk (mchunkptr p)
2829{
2830  INTERNAL_SIZE_T size = chunksize (p);
2831
2832  assert (chunk_is_mmapped (p));
2833
2834  uintptr_t block = (uintptr_t) p - p->prev_size;
2835  size_t total_size = p->prev_size + size;
2836  /* Unfortunately we have to do the compilers job by hand here.  Normally
2837     we would test BLOCK and TOTAL-SIZE separately for compliance with the
2838     page size.  But gcc does not recognize the optimization possibility
2839     (in the moment at least) so we combine the two values into one before
2840     the bit test.  */
2841  if (__builtin_expect (((block | total_size) & (GLRO (dl_pagesize) - 1)) != 0, 0))
2842    {
2843      malloc_printerr (check_action, "munmap_chunk(): invalid pointer",
2844                       chunk2mem (p), NULL);
2845      return;
2846    }
2847
2848  atomic_decrement (&mp_.n_mmaps);
2849  atomic_add (&mp_.mmapped_mem, -total_size);
2850
2851  /* If munmap failed the process virtual memory address space is in a
2852     bad shape.  Just leave the block hanging around, the process will
2853     terminate shortly anyway since not much can be done.  */
2854  __munmap ((char *) block, total_size);
2855}
2856
2857#if HAVE_MREMAP
2858
2859static mchunkptr
2860internal_function
2861mremap_chunk (mchunkptr p, size_t new_size)
2862{
2863  size_t pagesize = GLRO (dl_pagesize);
2864  INTERNAL_SIZE_T offset = p->prev_size;
2865  INTERNAL_SIZE_T size = chunksize (p);
2866  char *cp;
2867
2868  assert (chunk_is_mmapped (p));
2869  assert (((size + offset) & (GLRO (dl_pagesize) - 1)) == 0);
2870
2871  /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */
2872  new_size = ALIGN_UP (new_size + offset + SIZE_SZ, pagesize);
2873
2874  /* No need to remap if the number of pages does not change.  */
2875  if (size + offset == new_size)
2876    return p;
2877
2878  cp = (char *) __mremap ((char *) p - offset, size + offset, new_size,
2879                          MREMAP_MAYMOVE);
2880
2881  if (cp == MAP_FAILED)
2882    return 0;
2883
2884  p = (mchunkptr) (cp + offset);
2885
2886  assert (aligned_OK (chunk2mem (p)));
2887
2888  assert ((p->prev_size == offset));
2889  set_head (p, (new_size - offset) | IS_MMAPPED);
2890
2891  INTERNAL_SIZE_T new;
2892  new = atomic_exchange_and_add (&mp_.mmapped_mem, new_size - size - offset)
2893        + new_size - size - offset;
2894  atomic_max (&mp_.max_mmapped_mem, new);
2895  return p;
2896}
2897#endif /* HAVE_MREMAP */
2898
2899/*------------------------ Public wrappers. --------------------------------*/
2900
2901void *
2902__libc_malloc (size_t bytes)
2903{
2904  mstate ar_ptr;
2905  void *victim;
2906
2907  void *(*hook) (size_t, const void *)
2908    = atomic_forced_read (__malloc_hook);
2909  if (__builtin_expect (hook != NULL, 0))
2910    return (*hook)(bytes, RETURN_ADDRESS (0));
2911
2912  arena_get (ar_ptr, bytes);
2913
2914  victim = _int_malloc (ar_ptr, bytes);
2915  /* Retry with another arena only if we were able to find a usable arena
2916     before.  */
2917  if (!victim && ar_ptr != NULL)
2918    {
2919      LIBC_PROBE (memory_malloc_retry, 1, bytes);
2920      ar_ptr = arena_get_retry (ar_ptr, bytes);
2921      victim = _int_malloc (ar_ptr, bytes);
2922    }
2923
2924  if (ar_ptr != NULL)
2925    (void) mutex_unlock (&ar_ptr->mutex);
2926
2927  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
2928          ar_ptr == arena_for_chunk (mem2chunk (victim)));
2929  return victim;
2930}
2931libc_hidden_def (__libc_malloc)
2932
2933void
2934__libc_free (void *mem)
2935{
2936  mstate ar_ptr;
2937  mchunkptr p;                          /* chunk corresponding to mem */
2938
2939  void (*hook) (void *, const void *)
2940    = atomic_forced_read (__free_hook);
2941  if (__builtin_expect (hook != NULL, 0))
2942    {
2943      (*hook)(mem, RETURN_ADDRESS (0));
2944      return;
2945    }
2946
2947  if (mem == 0)                              /* free(0) has no effect */
2948    return;
2949
2950  p = mem2chunk (mem);
2951
2952  if (chunk_is_mmapped (p))                       /* release mmapped memory. */
2953    {
2954      /* see if the dynamic brk/mmap threshold needs adjusting */
2955      if (!mp_.no_dyn_threshold
2956          && p->size > mp_.mmap_threshold
2957          && p->size <= DEFAULT_MMAP_THRESHOLD_MAX)
2958        {
2959          mp_.mmap_threshold = chunksize (p);
2960          mp_.trim_threshold = 2 * mp_.mmap_threshold;
2961          LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
2962                      mp_.mmap_threshold, mp_.trim_threshold);
2963        }
2964      munmap_chunk (p);
2965      return;
2966    }
2967
2968  ar_ptr = arena_for_chunk (p);
2969  _int_free (ar_ptr, p, 0);
2970}
2971libc_hidden_def (__libc_free)
2972
2973void *
2974__libc_realloc (void *oldmem, size_t bytes)
2975{
2976  mstate ar_ptr;
2977  INTERNAL_SIZE_T nb;         /* padded request size */
2978
2979  void *newp;             /* chunk to return */
2980
2981  void *(*hook) (void *, size_t, const void *) =
2982    atomic_forced_read (__realloc_hook);
2983  if (__builtin_expect (hook != NULL, 0))
2984    return (*hook)(oldmem, bytes, RETURN_ADDRESS (0));
2985
2986#if REALLOC_ZERO_BYTES_FREES
2987  if (bytes == 0 && oldmem != NULL)
2988    {
2989      __libc_free (oldmem); return 0;
2990    }
2991#endif
2992
2993  /* realloc of null is supposed to be same as malloc */
2994  if (oldmem == 0)
2995    return __libc_malloc (bytes);
2996
2997  /* chunk corresponding to oldmem */
2998  const mchunkptr oldp = mem2chunk (oldmem);
2999  /* its size */
3000  const INTERNAL_SIZE_T oldsize = chunksize (oldp);
3001
3002  if (chunk_is_mmapped (oldp))
3003    ar_ptr = NULL;
3004  else
3005    ar_ptr = arena_for_chunk (oldp);
3006
3007  /* Little security check which won't hurt performance: the
3008     allocator never wrapps around at the end of the address space.
3009     Therefore we can exclude some size values which might appear
3010     here by accident or by "design" from some intruder.  */
3011  if (__builtin_expect ((uintptr_t) oldp > (uintptr_t) -oldsize, 0)
3012      || __builtin_expect (misaligned_chunk (oldp), 0))
3013    {
3014      malloc_printerr (check_action, "realloc(): invalid pointer", oldmem,
3015		       ar_ptr);
3016      return NULL;
3017    }
3018
3019  checked_request2size (bytes, nb);
3020
3021  if (chunk_is_mmapped (oldp))
3022    {
3023      void *newmem;
3024
3025#if HAVE_MREMAP
3026      newp = mremap_chunk (oldp, nb);
3027      if (newp)
3028        return chunk2mem (newp);
3029#endif
3030      /* Note the extra SIZE_SZ overhead. */
3031      if (oldsize - SIZE_SZ >= nb)
3032        return oldmem;                         /* do nothing */
3033
3034      /* Must alloc, copy, free. */
3035      newmem = __libc_malloc (bytes);
3036      if (newmem == 0)
3037        return 0;              /* propagate failure */
3038
3039      memcpy (newmem, oldmem, oldsize - 2 * SIZE_SZ);
3040      munmap_chunk (oldp);
3041      return newmem;
3042    }
3043
3044  (void) mutex_lock (&ar_ptr->mutex);
3045
3046  newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
3047
3048  (void) mutex_unlock (&ar_ptr->mutex);
3049  assert (!newp || chunk_is_mmapped (mem2chunk (newp)) ||
3050          ar_ptr == arena_for_chunk (mem2chunk (newp)));
3051
3052  if (newp == NULL)
3053    {
3054      /* Try harder to allocate memory in other arenas.  */
3055      LIBC_PROBE (memory_realloc_retry, 2, bytes, oldmem);
3056      newp = __libc_malloc (bytes);
3057      if (newp != NULL)
3058        {
3059          memcpy (newp, oldmem, oldsize - SIZE_SZ);
3060          _int_free (ar_ptr, oldp, 0);
3061        }
3062    }
3063
3064  return newp;
3065}
3066libc_hidden_def (__libc_realloc)
3067
3068void *
3069__libc_memalign (size_t alignment, size_t bytes)
3070{
3071  void *address = RETURN_ADDRESS (0);
3072  return _mid_memalign (alignment, bytes, address);
3073}
3074
3075static void *
3076_mid_memalign (size_t alignment, size_t bytes, void *address)
3077{
3078  mstate ar_ptr;
3079  void *p;
3080
3081  void *(*hook) (size_t, size_t, const void *) =
3082    atomic_forced_read (__memalign_hook);
3083  if (__builtin_expect (hook != NULL, 0))
3084    return (*hook)(alignment, bytes, address);
3085
3086  /* If we need less alignment than we give anyway, just relay to malloc.  */
3087  if (alignment <= MALLOC_ALIGNMENT)
3088    return __libc_malloc (bytes);
3089
3090  /* Otherwise, ensure that it is at least a minimum chunk size */
3091  if (alignment < MINSIZE)
3092    alignment = MINSIZE;
3093
3094  /* If the alignment is greater than SIZE_MAX / 2 + 1 it cannot be a
3095     power of 2 and will cause overflow in the check below.  */
3096  if (alignment > SIZE_MAX / 2 + 1)
3097    {
3098      __set_errno (EINVAL);
3099      return 0;
3100    }
3101
3102  /* Check for overflow.  */
3103  if (bytes > SIZE_MAX - alignment - MINSIZE)
3104    {
3105      __set_errno (ENOMEM);
3106      return 0;
3107    }
3108
3109
3110  /* Make sure alignment is power of 2.  */
3111  if (!powerof2 (alignment))
3112    {
3113      size_t a = MALLOC_ALIGNMENT * 2;
3114      while (a < alignment)
3115        a <<= 1;
3116      alignment = a;
3117    }
3118
3119  arena_get (ar_ptr, bytes + alignment + MINSIZE);
3120
3121  p = _int_memalign (ar_ptr, alignment, bytes);
3122  if (!p && ar_ptr != NULL)
3123    {
3124      LIBC_PROBE (memory_memalign_retry, 2, bytes, alignment);
3125      ar_ptr = arena_get_retry (ar_ptr, bytes);
3126      p = _int_memalign (ar_ptr, alignment, bytes);
3127    }
3128
3129  if (ar_ptr != NULL)
3130    (void) mutex_unlock (&ar_ptr->mutex);
3131
3132  assert (!p || chunk_is_mmapped (mem2chunk (p)) ||
3133          ar_ptr == arena_for_chunk (mem2chunk (p)));
3134  return p;
3135}
3136/* For ISO C11.  */
3137weak_alias (__libc_memalign, aligned_alloc)
3138libc_hidden_def (__libc_memalign)
3139
3140void *
3141__libc_valloc (size_t bytes)
3142{
3143  if (__malloc_initialized < 0)
3144    ptmalloc_init ();
3145
3146  void *address = RETURN_ADDRESS (0);
3147  size_t pagesize = GLRO (dl_pagesize);
3148  return _mid_memalign (pagesize, bytes, address);
3149}
3150
3151void *
3152__libc_pvalloc (size_t bytes)
3153{
3154  if (__malloc_initialized < 0)
3155    ptmalloc_init ();
3156
3157  void *address = RETURN_ADDRESS (0);
3158  size_t pagesize = GLRO (dl_pagesize);
3159  size_t rounded_bytes = ALIGN_UP (bytes, pagesize);
3160
3161  /* Check for overflow.  */
3162  if (bytes > SIZE_MAX - 2 * pagesize - MINSIZE)
3163    {
3164      __set_errno (ENOMEM);
3165      return 0;
3166    }
3167
3168  return _mid_memalign (pagesize, rounded_bytes, address);
3169}
3170
3171void *
3172__libc_calloc (size_t n, size_t elem_size)
3173{
3174  mstate av;
3175  mchunkptr oldtop, p;
3176  INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
3177  void *mem;
3178  unsigned long clearsize;
3179  unsigned long nclears;
3180  INTERNAL_SIZE_T *d;
3181
3182  /* size_t is unsigned so the behavior on overflow is defined.  */
3183  bytes = n * elem_size;
3184#define HALF_INTERNAL_SIZE_T \
3185  (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
3186  if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0))
3187    {
3188      if (elem_size != 0 && bytes / elem_size != n)
3189        {
3190          __set_errno (ENOMEM);
3191          return 0;
3192        }
3193    }
3194
3195  void *(*hook) (size_t, const void *) =
3196    atomic_forced_read (__malloc_hook);
3197  if (__builtin_expect (hook != NULL, 0))
3198    {
3199      sz = bytes;
3200      mem = (*hook)(sz, RETURN_ADDRESS (0));
3201      if (mem == 0)
3202        return 0;
3203
3204      return memset (mem, 0, sz);
3205    }
3206
3207  sz = bytes;
3208
3209  arena_get (av, sz);
3210  if (av)
3211    {
3212      /* Check if we hand out the top chunk, in which case there may be no
3213	 need to clear. */
3214#if MORECORE_CLEARS
3215      oldtop = top (av);
3216      oldtopsize = chunksize (top (av));
3217# if MORECORE_CLEARS < 2
3218      /* Only newly allocated memory is guaranteed to be cleared.  */
3219      if (av == &main_arena &&
3220	  oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *) oldtop)
3221	oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *) oldtop);
3222# endif
3223      if (av != &main_arena)
3224	{
3225	  heap_info *heap = heap_for_ptr (oldtop);
3226	  if (oldtopsize < (char *) heap + heap->mprotect_size - (char *) oldtop)
3227	    oldtopsize = (char *) heap + heap->mprotect_size - (char *) oldtop;
3228	}
3229#endif
3230    }
3231  else
3232    {
3233      /* No usable arenas.  */
3234      oldtop = 0;
3235      oldtopsize = 0;
3236    }
3237  mem = _int_malloc (av, sz);
3238
3239
3240  assert (!mem || chunk_is_mmapped (mem2chunk (mem)) ||
3241          av == arena_for_chunk (mem2chunk (mem)));
3242
3243  if (mem == 0 && av != NULL)
3244    {
3245      LIBC_PROBE (memory_calloc_retry, 1, sz);
3246      av = arena_get_retry (av, sz);
3247      mem = _int_malloc (av, sz);
3248    }
3249
3250  if (av != NULL)
3251    (void) mutex_unlock (&av->mutex);
3252
3253  /* Allocation failed even after a retry.  */
3254  if (mem == 0)
3255    return 0;
3256
3257  p = mem2chunk (mem);
3258
3259  /* Two optional cases in which clearing not necessary */
3260  if (chunk_is_mmapped (p))
3261    {
3262      if (__builtin_expect (perturb_byte, 0))
3263        return memset (mem, 0, sz);
3264
3265      return mem;
3266    }
3267
3268  csz = chunksize (p);
3269
3270#if MORECORE_CLEARS
3271  if (perturb_byte == 0 && (p == oldtop && csz > oldtopsize))
3272    {
3273      /* clear only the bytes from non-freshly-sbrked memory */
3274      csz = oldtopsize;
3275    }
3276#endif
3277
3278  /* Unroll clear of <= 36 bytes (72 if 8byte sizes).  We know that
3279     contents have an odd number of INTERNAL_SIZE_T-sized words;
3280     minimally 3.  */
3281  d = (INTERNAL_SIZE_T *) mem;
3282  clearsize = csz - SIZE_SZ;
3283  nclears = clearsize / sizeof (INTERNAL_SIZE_T);
3284  assert (nclears >= 3);
3285
3286  if (nclears > 9)
3287    return memset (d, 0, clearsize);
3288
3289  else
3290    {
3291      *(d + 0) = 0;
3292      *(d + 1) = 0;
3293      *(d + 2) = 0;
3294      if (nclears > 4)
3295        {
3296          *(d + 3) = 0;
3297          *(d + 4) = 0;
3298          if (nclears > 6)
3299            {
3300              *(d + 5) = 0;
3301              *(d + 6) = 0;
3302              if (nclears > 8)
3303                {
3304                  *(d + 7) = 0;
3305                  *(d + 8) = 0;
3306                }
3307            }
3308        }
3309    }
3310
3311  return mem;
3312}
3313
3314/*
3315   ------------------------------ malloc ------------------------------
3316 */
3317
3318static void *
3319_int_malloc (mstate av, size_t bytes)
3320{
3321  INTERNAL_SIZE_T nb;               /* normalized request size */
3322  unsigned int idx;                 /* associated bin index */
3323  mbinptr bin;                      /* associated bin */
3324
3325  mchunkptr victim;                 /* inspected/selected chunk */
3326  INTERNAL_SIZE_T size;             /* its size */
3327  int victim_index;                 /* its bin index */
3328
3329  mchunkptr remainder;              /* remainder from a split */
3330  unsigned long remainder_size;     /* its size */
3331
3332  unsigned int block;               /* bit map traverser */
3333  unsigned int bit;                 /* bit map traverser */
3334  unsigned int map;                 /* current word of binmap */
3335
3336  mchunkptr fwd;                    /* misc temp for linking */
3337  mchunkptr bck;                    /* misc temp for linking */
3338
3339  const char *errstr = NULL;
3340
3341  /*
3342     Convert request size to internal form by adding SIZE_SZ bytes
3343     overhead plus possibly more to obtain necessary alignment and/or
3344     to obtain a size of at least MINSIZE, the smallest allocatable
3345     size. Also, checked_request2size traps (returning 0) request sizes
3346     that are so large that they wrap around zero when padded and
3347     aligned.
3348   */
3349
3350  checked_request2size (bytes, nb);
3351
3352  /* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
3353     mmap.  */
3354  if (__glibc_unlikely (av == NULL))
3355    {
3356      void *p = sysmalloc (nb, av);
3357      if (p != NULL)
3358	alloc_perturb (p, bytes);
3359      return p;
3360    }
3361
3362  /*
3363     If the size qualifies as a fastbin, first check corresponding bin.
3364     This code is safe to execute even if av is not yet initialized, so we
3365     can try it without checking, which saves some time on this fast path.
3366   */
3367
3368  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
3369    {
3370      idx = fastbin_index (nb);
3371      mfastbinptr *fb = &fastbin (av, idx);
3372      mchunkptr pp = *fb;
3373      do
3374        {
3375          victim = pp;
3376          if (victim == NULL)
3377            break;
3378        }
3379      while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
3380             != victim);
3381      if (victim != 0)
3382        {
3383          if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
3384            {
3385              errstr = "malloc(): memory corruption (fast)";
3386            errout:
3387              malloc_printerr (check_action, errstr, chunk2mem (victim), av);
3388              return NULL;
3389            }
3390          check_remalloced_chunk (av, victim, nb);
3391          void *p = chunk2mem (victim);
3392          alloc_perturb (p, bytes);
3393          return p;
3394        }
3395    }
3396
3397  /*
3398     If a small request, check regular bin.  Since these "smallbins"
3399     hold one size each, no searching within bins is necessary.
3400     (For a large request, we need to wait until unsorted chunks are
3401     processed to find best fit. But for small ones, fits are exact
3402     anyway, so we can check now, which is faster.)
3403   */
3404
3405  if (in_smallbin_range (nb))
3406    {
3407      idx = smallbin_index (nb);
3408      bin = bin_at (av, idx);
3409
3410      if ((victim = last (bin)) != bin)
3411        {
3412          if (victim == 0) /* initialization check */
3413            malloc_consolidate (av);
3414          else
3415            {
3416              bck = victim->bk;
3417	if (__glibc_unlikely (bck->fd != victim))
3418                {
3419                  errstr = "malloc(): smallbin double linked list corrupted";
3420                  goto errout;
3421                }
3422              set_inuse_bit_at_offset (victim, nb);
3423              bin->bk = bck;
3424              bck->fd = bin;
3425
3426              if (av != &main_arena)
3427                victim->size |= NON_MAIN_ARENA;
3428              check_malloced_chunk (av, victim, nb);
3429              void *p = chunk2mem (victim);
3430              alloc_perturb (p, bytes);
3431              return p;
3432            }
3433        }
3434    }
3435
3436  /*
3437     If this is a large request, consolidate fastbins before continuing.
3438     While it might look excessive to kill all fastbins before
3439     even seeing if there is space available, this avoids
3440     fragmentation problems normally associated with fastbins.
3441     Also, in practice, programs tend to have runs of either small or
3442     large requests, but less often mixtures, so consolidation is not
3443     invoked all that often in most programs. And the programs that
3444     it is called frequently in otherwise tend to fragment.
3445   */
3446
3447  else
3448    {
3449      idx = largebin_index (nb);
3450      if (have_fastchunks (av))
3451        malloc_consolidate (av);
3452    }
3453
3454  /*
3455     Process recently freed or remaindered chunks, taking one only if
3456     it is exact fit, or, if this a small request, the chunk is remainder from
3457     the most recent non-exact fit.  Place other traversed chunks in
3458     bins.  Note that this step is the only place in any routine where
3459     chunks are placed in bins.
3460
3461     The outer loop here is needed because we might not realize until
3462     near the end of malloc that we should have consolidated, so must
3463     do so and retry. This happens at most once, and only when we would
3464     otherwise need to expand memory to service a "small" request.
3465   */
3466
3467  for (;; )
3468    {
3469      int iters = 0;
3470      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
3471        {
3472          bck = victim->bk;
3473          if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
3474              || __builtin_expect (victim->size > av->system_mem, 0))
3475            malloc_printerr (check_action, "malloc(): memory corruption",
3476                             chunk2mem (victim), av);
3477          size = chunksize (victim);
3478
3479          /*
3480             If a small request, try to use last remainder if it is the
3481             only chunk in unsorted bin.  This helps promote locality for
3482             runs of consecutive small requests. This is the only
3483             exception to best-fit, and applies only when there is
3484             no exact fit for a small chunk.
3485           */
3486
3487          if (in_smallbin_range (nb) &&
3488              bck == unsorted_chunks (av) &&
3489              victim == av->last_remainder &&
3490              (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
3491            {
3492              /* split and reattach remainder */
3493              remainder_size = size - nb;
3494              remainder = chunk_at_offset (victim, nb);
3495              unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
3496              av->last_remainder = remainder;
3497              remainder->bk = remainder->fd = unsorted_chunks (av);
3498              if (!in_smallbin_range (remainder_size))
3499                {
3500                  remainder->fd_nextsize = NULL;
3501                  remainder->bk_nextsize = NULL;
3502                }
3503
3504              set_head (victim, nb | PREV_INUSE |
3505                        (av != &main_arena ? NON_MAIN_ARENA : 0));
3506              set_head (remainder, remainder_size | PREV_INUSE);
3507              set_foot (remainder, remainder_size);
3508
3509              check_malloced_chunk (av, victim, nb);
3510              void *p = chunk2mem (victim);
3511              alloc_perturb (p, bytes);
3512              return p;
3513            }
3514
3515          /* remove from unsorted list */
3516          unsorted_chunks (av)->bk = bck;
3517          bck->fd = unsorted_chunks (av);
3518
3519          /* Take now instead of binning if exact fit */
3520
3521          if (size == nb)
3522            {
3523              set_inuse_bit_at_offset (victim, size);
3524              if (av != &main_arena)
3525                victim->size |= NON_MAIN_ARENA;
3526              check_malloced_chunk (av, victim, nb);
3527              void *p = chunk2mem (victim);
3528              alloc_perturb (p, bytes);
3529              return p;
3530            }
3531
3532          /* place chunk in bin */
3533
3534          if (in_smallbin_range (size))
3535            {
3536              victim_index = smallbin_index (size);
3537              bck = bin_at (av, victim_index);
3538              fwd = bck->fd;
3539            }
3540          else
3541            {
3542              victim_index = largebin_index (size);
3543              bck = bin_at (av, victim_index);
3544              fwd = bck->fd;
3545
3546              /* maintain large bins in sorted order */
3547              if (fwd != bck)
3548                {
3549                  /* Or with inuse bit to speed comparisons */
3550                  size |= PREV_INUSE;
3551                  /* if smaller than smallest, bypass loop below */
3552                  assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
3553                  if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
3554                    {
3555                      fwd = bck;
3556                      bck = bck->bk;
3557
3558                      victim->fd_nextsize = fwd->fd;
3559                      victim->bk_nextsize = fwd->fd->bk_nextsize;
3560                      fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
3561                    }
3562                  else
3563                    {
3564                      assert ((fwd->size & NON_MAIN_ARENA) == 0);
3565                      while ((unsigned long) size < fwd->size)
3566                        {
3567                          fwd = fwd->fd_nextsize;
3568                          assert ((fwd->size & NON_MAIN_ARENA) == 0);
3569                        }
3570
3571                      if ((unsigned long) size == (unsigned long) fwd->size)
3572                        /* Always insert in the second position.  */
3573                        fwd = fwd->fd;
3574                      else
3575                        {
3576                          victim->fd_nextsize = fwd;
3577                          victim->bk_nextsize = fwd->bk_nextsize;
3578                          fwd->bk_nextsize = victim;
3579                          victim->bk_nextsize->fd_nextsize = victim;
3580                        }
3581                      bck = fwd->bk;
3582                    }
3583                }
3584              else
3585                victim->fd_nextsize = victim->bk_nextsize = victim;
3586            }
3587
3588          mark_bin (av, victim_index);
3589          victim->bk = bck;
3590          victim->fd = fwd;
3591          fwd->bk = victim;
3592          bck->fd = victim;
3593
3594#define MAX_ITERS       10000
3595          if (++iters >= MAX_ITERS)
3596            break;
3597        }
3598
3599      /*
3600         If a large request, scan through the chunks of current bin in
3601         sorted order to find smallest that fits.  Use the skip list for this.
3602       */
3603
3604      if (!in_smallbin_range (nb))
3605        {
3606          bin = bin_at (av, idx);
3607
3608          /* skip scan if empty or largest chunk is too small */
3609          if ((victim = first (bin)) != bin &&
3610              (unsigned long) (victim->size) >= (unsigned long) (nb))
3611            {
3612              victim = victim->bk_nextsize;
3613              while (((unsigned long) (size = chunksize (victim)) <
3614                      (unsigned long) (nb)))
3615                victim = victim->bk_nextsize;
3616
3617              /* Avoid removing the first entry for a size so that the skip
3618                 list does not have to be rerouted.  */
3619              if (victim != last (bin) && victim->size == victim->fd->size)
3620                victim = victim->fd;
3621
3622              remainder_size = size - nb;
3623              unlink (av, victim, bck, fwd);
3624
3625              /* Exhaust */
3626              if (remainder_size < MINSIZE)
3627                {
3628                  set_inuse_bit_at_offset (victim, size);
3629                  if (av != &main_arena)
3630                    victim->size |= NON_MAIN_ARENA;
3631                }
3632              /* Split */
3633              else
3634                {
3635                  remainder = chunk_at_offset (victim, nb);
3636                  /* We cannot assume the unsorted list is empty and therefore
3637                     have to perform a complete insert here.  */
3638                  bck = unsorted_chunks (av);
3639                  fwd = bck->fd;
3640	  if (__glibc_unlikely (fwd->bk != bck))
3641                    {
3642                      errstr = "malloc(): corrupted unsorted chunks";
3643                      goto errout;
3644                    }
3645                  remainder->bk = bck;
3646                  remainder->fd = fwd;
3647                  bck->fd = remainder;
3648                  fwd->bk = remainder;
3649                  if (!in_smallbin_range (remainder_size))
3650                    {
3651                      remainder->fd_nextsize = NULL;
3652                      remainder->bk_nextsize = NULL;
3653                    }
3654                  set_head (victim, nb | PREV_INUSE |
3655                            (av != &main_arena ? NON_MAIN_ARENA : 0));
3656                  set_head (remainder, remainder_size | PREV_INUSE);
3657                  set_foot (remainder, remainder_size);
3658                }
3659              check_malloced_chunk (av, victim, nb);
3660              void *p = chunk2mem (victim);
3661              alloc_perturb (p, bytes);
3662              return p;
3663            }
3664        }
3665
3666      /*
3667         Search for a chunk by scanning bins, starting with next largest
3668         bin. This search is strictly by best-fit; i.e., the smallest
3669         (with ties going to approximately the least recently used) chunk
3670         that fits is selected.
3671
3672         The bitmap avoids needing to check that most blocks are nonempty.
3673         The particular case of skipping all bins during warm-up phases
3674         when no chunks have been returned yet is faster than it might look.
3675       */
3676
3677      ++idx;
3678      bin = bin_at (av, idx);
3679      block = idx2block (idx);
3680      map = av->binmap[block];
3681      bit = idx2bit (idx);
3682
3683      for (;; )
3684        {
3685          /* Skip rest of block if there are no more set bits in this block.  */
3686          if (bit > map || bit == 0)
3687            {
3688              do
3689                {
3690                  if (++block >= BINMAPSIZE) /* out of bins */
3691                    goto use_top;
3692                }
3693              while ((map = av->binmap[block]) == 0);
3694
3695              bin = bin_at (av, (block << BINMAPSHIFT));
3696              bit = 1;
3697            }
3698
3699          /* Advance to bin with set bit. There must be one. */
3700          while ((bit & map) == 0)
3701            {
3702              bin = next_bin (bin);
3703              bit <<= 1;
3704              assert (bit != 0);
3705            }
3706
3707          /* Inspect the bin. It is likely to be non-empty */
3708          victim = last (bin);
3709
3710          /*  If a false alarm (empty bin), clear the bit. */
3711          if (victim == bin)
3712            {
3713              av->binmap[block] = map &= ~bit; /* Write through */
3714              bin = next_bin (bin);
3715              bit <<= 1;
3716            }
3717
3718          else
3719            {
3720              size = chunksize (victim);
3721
3722              /*  We know the first chunk in this bin is big enough to use. */
3723              assert ((unsigned long) (size) >= (unsigned long) (nb));
3724
3725              remainder_size = size - nb;
3726
3727              /* unlink */
3728              unlink (av, victim, bck, fwd);
3729
3730              /* Exhaust */
3731              if (remainder_size < MINSIZE)
3732                {
3733                  set_inuse_bit_at_offset (victim, size);
3734                  if (av != &main_arena)
3735                    victim->size |= NON_MAIN_ARENA;
3736                }
3737
3738              /* Split */
3739              else
3740                {
3741                  remainder = chunk_at_offset (victim, nb);
3742
3743                  /* We cannot assume the unsorted list is empty and therefore
3744                     have to perform a complete insert here.  */
3745                  bck = unsorted_chunks (av);
3746                  fwd = bck->fd;
3747	  if (__glibc_unlikely (fwd->bk != bck))
3748                    {
3749                      errstr = "malloc(): corrupted unsorted chunks 2";
3750                      goto errout;
3751                    }
3752                  remainder->bk = bck;
3753                  remainder->fd = fwd;
3754                  bck->fd = remainder;
3755                  fwd->bk = remainder;
3756
3757                  /* advertise as last remainder */
3758                  if (in_smallbin_range (nb))
3759                    av->last_remainder = remainder;
3760                  if (!in_smallbin_range (remainder_size))
3761                    {
3762                      remainder->fd_nextsize = NULL;
3763                      remainder->bk_nextsize = NULL;
3764                    }
3765                  set_head (victim, nb | PREV_INUSE |
3766                            (av != &main_arena ? NON_MAIN_ARENA : 0));
3767                  set_head (remainder, remainder_size | PREV_INUSE);
3768                  set_foot (remainder, remainder_size);
3769                }
3770              check_malloced_chunk (av, victim, nb);
3771              void *p = chunk2mem (victim);
3772              alloc_perturb (p, bytes);
3773              return p;
3774            }
3775        }
3776
3777    use_top:
3778      /*
3779         If large enough, split off the chunk bordering the end of memory
3780         (held in av->top). Note that this is in accord with the best-fit
3781         search rule.  In effect, av->top is treated as larger (and thus
3782         less well fitting) than any other available chunk since it can
3783         be extended to be as large as necessary (up to system
3784         limitations).
3785
3786         We require that av->top always exists (i.e., has size >=
3787         MINSIZE) after initialization, so if it would otherwise be
3788         exhausted by current request, it is replenished. (The main
3789         reason for ensuring it exists is that we may need MINSIZE space
3790         to put in fenceposts in sysmalloc.)
3791       */
3792
3793      victim = av->top;
3794      size = chunksize (victim);
3795
3796      if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
3797        {
3798          remainder_size = size - nb;
3799          remainder = chunk_at_offset (victim, nb);
3800          av->top = remainder;
3801          set_head (victim, nb | PREV_INUSE |
3802                    (av != &main_arena ? NON_MAIN_ARENA : 0));
3803          set_head (remainder, remainder_size | PREV_INUSE);
3804
3805          check_malloced_chunk (av, victim, nb);
3806          void *p = chunk2mem (victim);
3807          alloc_perturb (p, bytes);
3808          return p;
3809        }
3810
3811      /* When we are using atomic ops to free fast chunks we can get
3812         here for all block sizes.  */
3813      else if (have_fastchunks (av))
3814        {
3815          malloc_consolidate (av);
3816          /* restore original bin index */
3817          if (in_smallbin_range (nb))
3818            idx = smallbin_index (nb);
3819          else
3820            idx = largebin_index (nb);
3821        }
3822
3823      /*
3824         Otherwise, relay to handle system-dependent cases
3825       */
3826      else
3827        {
3828          void *p = sysmalloc (nb, av);
3829          if (p != NULL)
3830            alloc_perturb (p, bytes);
3831          return p;
3832        }
3833    }
3834}
3835
3836/*
3837   ------------------------------ free ------------------------------
3838 */
3839
3840static void
3841_int_free (mstate av, mchunkptr p, int have_lock)
3842{
3843  INTERNAL_SIZE_T size;        /* its size */
3844  mfastbinptr *fb;             /* associated fastbin */
3845  mchunkptr nextchunk;         /* next contiguous chunk */
3846  INTERNAL_SIZE_T nextsize;    /* its size */
3847  int nextinuse;               /* true if nextchunk is used */
3848  INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
3849  mchunkptr bck;               /* misc temp for linking */
3850  mchunkptr fwd;               /* misc temp for linking */
3851
3852  const char *errstr = NULL;
3853  int locked = 0;
3854
3855  size = chunksize (p);
3856
3857  /* Little security check which won't hurt performance: the
3858     allocator never wrapps around at the end of the address space.
3859     Therefore we can exclude some size values which might appear
3860     here by accident or by "design" from some intruder.  */
3861  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
3862      || __builtin_expect (misaligned_chunk (p), 0))
3863    {
3864      errstr = "free(): invalid pointer";
3865    errout:
3866      if (!have_lock && locked)
3867        (void) mutex_unlock (&av->mutex);
3868      malloc_printerr (check_action, errstr, chunk2mem (p), av);
3869      return;
3870    }
3871  /* We know that each chunk is at least MINSIZE bytes in size or a
3872     multiple of MALLOC_ALIGNMENT.  */
3873  if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
3874    {
3875      errstr = "free(): invalid size";
3876      goto errout;
3877    }
3878
3879  check_inuse_chunk(av, p);
3880
3881  /*
3882    If eligible, place chunk on a fastbin so it can be found
3883    and used quickly in malloc.
3884  */
3885
3886  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
3887
3888#if TRIM_FASTBINS
3889      /*
3890	If TRIM_FASTBINS set, don't place chunks
3891	bordering top into fastbins
3892      */
3893      && (chunk_at_offset(p, size) != av->top)
3894#endif
3895      ) {
3896
3897    if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
3898	|| __builtin_expect (chunksize (chunk_at_offset (p, size))
3899			     >= av->system_mem, 0))
3900      {
3901	/* We might not have a lock at this point and concurrent modifications
3902	   of system_mem might have let to a false positive.  Redo the test
3903	   after getting the lock.  */
3904	if (have_lock
3905	    || ({ assert (locked == 0);
3906		  mutex_lock(&av->mutex);
3907		  locked = 1;
3908		  chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
3909		    || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
3910	      }))
3911	  {
3912	    errstr = "free(): invalid next size (fast)";
3913	    goto errout;
3914	  }
3915	if (! have_lock)
3916	  {
3917	    (void)mutex_unlock(&av->mutex);
3918	    locked = 0;
3919	  }
3920      }
3921
3922    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
3923
3924    set_fastchunks(av);
3925    unsigned int idx = fastbin_index(size);
3926    fb = &fastbin (av, idx);
3927
3928    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
3929    mchunkptr old = *fb, old2;
3930    unsigned int old_idx = ~0u;
3931    do
3932      {
3933	/* Check that the top of the bin is not the record we are going to add
3934	   (i.e., double free).  */
3935	if (__builtin_expect (old == p, 0))
3936	  {
3937	    errstr = "double free or corruption (fasttop)";
3938	    goto errout;
3939	  }
3940	/* Check that size of fastbin chunk at the top is the same as
3941	   size of the chunk that we are adding.  We can dereference OLD
3942	   only if we have the lock, otherwise it might have already been
3943	   deallocated.  See use of OLD_IDX below for the actual check.  */
3944	if (have_lock && old != NULL)
3945	  old_idx = fastbin_index(chunksize(old));
3946	p->fd = old2 = old;
3947      }
3948    while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
3949
3950    if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
3951      {
3952	errstr = "invalid fastbin entry (free)";
3953	goto errout;
3954      }
3955  }
3956
3957  /*
3958    Consolidate other non-mmapped chunks as they arrive.
3959  */
3960
3961  else if (!chunk_is_mmapped(p)) {
3962    if (! have_lock) {
3963      (void)mutex_lock(&av->mutex);
3964      locked = 1;
3965    }
3966
3967    nextchunk = chunk_at_offset(p, size);
3968
3969    /* Lightweight tests: check whether the block is already the
3970       top block.  */
3971    if (__glibc_unlikely (p == av->top))
3972      {
3973	errstr = "double free or corruption (top)";
3974	goto errout;
3975      }
3976    /* Or whether the next chunk is beyond the boundaries of the arena.  */
3977    if (__builtin_expect (contiguous (av)
3978			  && (char *) nextchunk
3979			  >= ((char *) av->top + chunksize(av->top)), 0))
3980      {
3981	errstr = "double free or corruption (out)";
3982	goto errout;
3983      }
3984    /* Or whether the block is actually not marked used.  */
3985    if (__glibc_unlikely (!prev_inuse(nextchunk)))
3986      {
3987	errstr = "double free or corruption (!prev)";
3988	goto errout;
3989      }
3990
3991    nextsize = chunksize(nextchunk);
3992    if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
3993	|| __builtin_expect (nextsize >= av->system_mem, 0))
3994      {
3995	errstr = "free(): invalid next size (normal)";
3996	goto errout;
3997      }
3998
3999    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
4000
4001    /* consolidate backward */
4002    if (!prev_inuse(p)) {
4003      prevsize = p->prev_size;
4004      size += prevsize;
4005      p = chunk_at_offset(p, -((long) prevsize));
4006      unlink(av, p, bck, fwd);
4007    }
4008
4009    if (nextchunk != av->top) {
4010      /* get and clear inuse bit */
4011      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4012
4013      /* consolidate forward */
4014      if (!nextinuse) {
4015	unlink(av, nextchunk, bck, fwd);
4016	size += nextsize;
4017      } else
4018	clear_inuse_bit_at_offset(nextchunk, 0);
4019
4020      /*
4021	Place the chunk in unsorted chunk list. Chunks are
4022	not placed into regular bins until after they have
4023	been given one chance to be used in malloc.
4024      */
4025
4026      bck = unsorted_chunks(av);
4027      fwd = bck->fd;
4028      if (__glibc_unlikely (fwd->bk != bck))
4029	{
4030	  errstr = "free(): corrupted unsorted chunks";
4031	  goto errout;
4032	}
4033      p->fd = fwd;
4034      p->bk = bck;
4035      if (!in_smallbin_range(size))
4036	{
4037	  p->fd_nextsize = NULL;
4038	  p->bk_nextsize = NULL;
4039	}
4040      bck->fd = p;
4041      fwd->bk = p;
4042
4043      set_head(p, size | PREV_INUSE);
4044      set_foot(p, size);
4045
4046      check_free_chunk(av, p);
4047    }
4048
4049    /*
4050      If the chunk borders the current high end of memory,
4051      consolidate into top
4052    */
4053
4054    else {
4055      size += nextsize;
4056      set_head(p, size | PREV_INUSE);
4057      av->top = p;
4058      check_chunk(av, p);
4059    }
4060
4061    /*
4062      If freeing a large space, consolidate possibly-surrounding
4063      chunks. Then, if the total unused topmost memory exceeds trim
4064      threshold, ask malloc_trim to reduce top.
4065
4066      Unless max_fast is 0, we don't know if there are fastbins
4067      bordering top, so we cannot tell for sure whether threshold
4068      has been reached unless fastbins are consolidated.  But we
4069      don't want to consolidate on each free.  As a compromise,
4070      consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4071      is reached.
4072    */
4073
4074    if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
4075      if (have_fastchunks(av))
4076	malloc_consolidate(av);
4077
4078      if (av == &main_arena) {
4079#ifndef MORECORE_CANNOT_TRIM
4080	if ((unsigned long)(chunksize(av->top)) >=
4081	    (unsigned long)(mp_.trim_threshold))
4082	  systrim(mp_.top_pad, av);
4083#endif
4084      } else {
4085	/* Always try heap_trim(), even if the top chunk is not
4086	   large, because the corresponding heap might go away.  */
4087	heap_info *heap = heap_for_ptr(top(av));
4088
4089	assert(heap->ar_ptr == av);
4090	heap_trim(heap, mp_.top_pad);
4091      }
4092    }
4093
4094    if (! have_lock) {
4095      assert (locked);
4096      (void)mutex_unlock(&av->mutex);
4097    }
4098  }
4099  /*
4100    If the chunk was allocated via mmap, release via munmap().
4101  */
4102
4103  else {
4104    munmap_chunk (p);
4105  }
4106}
4107
4108/*
4109  ------------------------- malloc_consolidate -------------------------
4110
4111  malloc_consolidate is a specialized version of free() that tears
4112  down chunks held in fastbins.  Free itself cannot be used for this
4113  purpose since, among other things, it might place chunks back onto
4114  fastbins.  So, instead, we need to use a minor variant of the same
4115  code.
4116
4117  Also, because this routine needs to be called the first time through
4118  malloc anyway, it turns out to be the perfect place to trigger
4119  initialization code.
4120*/
4121
4122static void malloc_consolidate(mstate av)
4123{
4124  mfastbinptr*    fb;                 /* current fastbin being consolidated */
4125  mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
4126  mchunkptr       p;                  /* current chunk being consolidated */
4127  mchunkptr       nextp;              /* next chunk to consolidate */
4128  mchunkptr       unsorted_bin;       /* bin header */
4129  mchunkptr       first_unsorted;     /* chunk to link to */
4130
4131  /* These have same use as in free() */
4132  mchunkptr       nextchunk;
4133  INTERNAL_SIZE_T size;
4134  INTERNAL_SIZE_T nextsize;
4135  INTERNAL_SIZE_T prevsize;
4136  int             nextinuse;
4137  mchunkptr       bck;
4138  mchunkptr       fwd;
4139
4140  /*
4141    If max_fast is 0, we know that av hasn't
4142    yet been initialized, in which case do so below
4143  */
4144
4145  if (get_max_fast () != 0) {
4146    clear_fastchunks(av);
4147
4148    unsorted_bin = unsorted_chunks(av);
4149
4150    /*
4151      Remove each chunk from fast bin and consolidate it, placing it
4152      then in unsorted bin. Among other reasons for doing this,
4153      placing in unsorted bin avoids needing to calculate actual bins
4154      until malloc is sure that chunks aren't immediately going to be
4155      reused anyway.
4156    */
4157
4158    maxfb = &fastbin (av, NFASTBINS - 1);
4159    fb = &fastbin (av, 0);
4160    do {
4161      p = atomic_exchange_acq (fb, 0);
4162      if (p != 0) {
4163	do {
4164	  check_inuse_chunk(av, p);
4165	  nextp = p->fd;
4166
4167	  /* Slightly streamlined version of consolidation code in free() */
4168	  size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
4169	  nextchunk = chunk_at_offset(p, size);
4170	  nextsize = chunksize(nextchunk);
4171
4172	  if (!prev_inuse(p)) {
4173	    prevsize = p->prev_size;
4174	    size += prevsize;
4175	    p = chunk_at_offset(p, -((long) prevsize));
4176	    unlink(av, p, bck, fwd);
4177	  }
4178
4179	  if (nextchunk != av->top) {
4180	    nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
4181
4182	    if (!nextinuse) {
4183	      size += nextsize;
4184	      unlink(av, nextchunk, bck, fwd);
4185	    } else
4186	      clear_inuse_bit_at_offset(nextchunk, 0);
4187
4188	    first_unsorted = unsorted_bin->fd;
4189	    unsorted_bin->fd = p;
4190	    first_unsorted->bk = p;
4191
4192	    if (!in_smallbin_range (size)) {
4193	      p->fd_nextsize = NULL;
4194	      p->bk_nextsize = NULL;
4195	    }
4196
4197	    set_head(p, size | PREV_INUSE);
4198	    p->bk = unsorted_bin;
4199	    p->fd = first_unsorted;
4200	    set_foot(p, size);
4201	  }
4202
4203	  else {
4204	    size += nextsize;
4205	    set_head(p, size | PREV_INUSE);
4206	    av->top = p;
4207	  }
4208
4209	} while ( (p = nextp) != 0);
4210
4211      }
4212    } while (fb++ != maxfb);
4213  }
4214  else {
4215    malloc_init_state(av);
4216    check_malloc_state(av);
4217  }
4218}
4219
4220/*
4221  ------------------------------ realloc ------------------------------
4222*/
4223
4224void*
4225_int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
4226	     INTERNAL_SIZE_T nb)
4227{
4228  mchunkptr        newp;            /* chunk to return */
4229  INTERNAL_SIZE_T  newsize;         /* its size */
4230  void*          newmem;          /* corresponding user mem */
4231
4232  mchunkptr        next;            /* next contiguous chunk after oldp */
4233
4234  mchunkptr        remainder;       /* extra space at end of newp */
4235  unsigned long    remainder_size;  /* its size */
4236
4237  mchunkptr        bck;             /* misc temp for linking */
4238  mchunkptr        fwd;             /* misc temp for linking */
4239
4240  unsigned long    copysize;        /* bytes to copy */
4241  unsigned int     ncopies;         /* INTERNAL_SIZE_T words to copy */
4242  INTERNAL_SIZE_T* s;               /* copy source */
4243  INTERNAL_SIZE_T* d;               /* copy destination */
4244
4245  const char *errstr = NULL;
4246
4247  /* oldmem size */
4248  if (__builtin_expect (oldp->size <= 2 * SIZE_SZ, 0)
4249      || __builtin_expect (oldsize >= av->system_mem, 0))
4250    {
4251      errstr = "realloc(): invalid old size";
4252    errout:
4253      malloc_printerr (check_action, errstr, chunk2mem (oldp), av);
4254      return NULL;
4255    }
4256
4257  check_inuse_chunk (av, oldp);
4258
4259  /* All callers already filter out mmap'ed chunks.  */
4260  assert (!chunk_is_mmapped (oldp));
4261
4262  next = chunk_at_offset (oldp, oldsize);
4263  INTERNAL_SIZE_T nextsize = chunksize (next);
4264  if (__builtin_expect (next->size <= 2 * SIZE_SZ, 0)
4265      || __builtin_expect (nextsize >= av->system_mem, 0))
4266    {
4267      errstr = "realloc(): invalid next size";
4268      goto errout;
4269    }
4270
4271  if ((unsigned long) (oldsize) >= (unsigned long) (nb))
4272    {
4273      /* already big enough; split below */
4274      newp = oldp;
4275      newsize = oldsize;
4276    }
4277
4278  else
4279    {
4280      /* Try to expand forward into top */
4281      if (next == av->top &&
4282          (unsigned long) (newsize = oldsize + nextsize) >=
4283          (unsigned long) (nb + MINSIZE))
4284        {
4285          set_head_size (oldp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4286          av->top = chunk_at_offset (oldp, nb);
4287          set_head (av->top, (newsize - nb) | PREV_INUSE);
4288          check_inuse_chunk (av, oldp);
4289          return chunk2mem (oldp);
4290        }
4291
4292      /* Try to expand forward into next chunk;  split off remainder below */
4293      else if (next != av->top &&
4294               !inuse (next) &&
4295               (unsigned long) (newsize = oldsize + nextsize) >=
4296               (unsigned long) (nb))
4297        {
4298          newp = oldp;
4299          unlink (av, next, bck, fwd);
4300        }
4301
4302      /* allocate, copy, free */
4303      else
4304        {
4305          newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK);
4306          if (newmem == 0)
4307            return 0; /* propagate failure */
4308
4309          newp = mem2chunk (newmem);
4310          newsize = chunksize (newp);
4311
4312          /*
4313             Avoid copy if newp is next chunk after oldp.
4314           */
4315          if (newp == next)
4316            {
4317              newsize += oldsize;
4318              newp = oldp;
4319            }
4320          else
4321            {
4322              /*
4323                 Unroll copy of <= 36 bytes (72 if 8byte sizes)
4324                 We know that contents have an odd number of
4325                 INTERNAL_SIZE_T-sized words; minimally 3.
4326               */
4327
4328              copysize = oldsize - SIZE_SZ;
4329              s = (INTERNAL_SIZE_T *) (chunk2mem (oldp));
4330              d = (INTERNAL_SIZE_T *) (newmem);
4331              ncopies = copysize / sizeof (INTERNAL_SIZE_T);
4332              assert (ncopies >= 3);
4333
4334              if (ncopies > 9)
4335                memcpy (d, s, copysize);
4336
4337              else
4338                {
4339                  *(d + 0) = *(s + 0);
4340                  *(d + 1) = *(s + 1);
4341                  *(d + 2) = *(s + 2);
4342                  if (ncopies > 4)
4343                    {
4344                      *(d + 3) = *(s + 3);
4345                      *(d + 4) = *(s + 4);
4346                      if (ncopies > 6)
4347                        {
4348                          *(d + 5) = *(s + 5);
4349                          *(d + 6) = *(s + 6);
4350                          if (ncopies > 8)
4351                            {
4352                              *(d + 7) = *(s + 7);
4353                              *(d + 8) = *(s + 8);
4354                            }
4355                        }
4356                    }
4357                }
4358
4359              _int_free (av, oldp, 1);
4360              check_inuse_chunk (av, newp);
4361              return chunk2mem (newp);
4362            }
4363        }
4364    }
4365
4366  /* If possible, free extra space in old or extended chunk */
4367
4368  assert ((unsigned long) (newsize) >= (unsigned long) (nb));
4369
4370  remainder_size = newsize - nb;
4371
4372  if (remainder_size < MINSIZE)   /* not enough extra to split off */
4373    {
4374      set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4375      set_inuse_bit_at_offset (newp, newsize);
4376    }
4377  else   /* split remainder */
4378    {
4379      remainder = chunk_at_offset (newp, nb);
4380      set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
4381      set_head (remainder, remainder_size | PREV_INUSE |
4382                (av != &main_arena ? NON_MAIN_ARENA : 0));
4383      /* Mark remainder as inuse so free() won't complain */
4384      set_inuse_bit_at_offset (remainder, remainder_size);
4385      _int_free (av, remainder, 1);
4386    }
4387
4388  check_inuse_chunk (av, newp);
4389  return chunk2mem (newp);
4390}
4391
4392/*
4393   ------------------------------ memalign ------------------------------
4394 */
4395
4396static void *
4397_int_memalign (mstate av, size_t alignment, size_t bytes)
4398{
4399  INTERNAL_SIZE_T nb;             /* padded  request size */
4400  char *m;                        /* memory returned by malloc call */
4401  mchunkptr p;                    /* corresponding chunk */
4402  char *brk;                      /* alignment point within p */
4403  mchunkptr newp;                 /* chunk to return */
4404  INTERNAL_SIZE_T newsize;        /* its size */
4405  INTERNAL_SIZE_T leadsize;       /* leading space before alignment point */
4406  mchunkptr remainder;            /* spare room at end to split off */
4407  unsigned long remainder_size;   /* its size */
4408  INTERNAL_SIZE_T size;
4409
4410
4411
4412  checked_request2size (bytes, nb);
4413
4414  /*
4415     Strategy: find a spot within that chunk that meets the alignment
4416     request, and then possibly free the leading and trailing space.
4417   */
4418
4419
4420  /* Call malloc with worst case padding to hit alignment. */
4421
4422  m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
4423
4424  if (m == 0)
4425    return 0;           /* propagate failure */
4426
4427  p = mem2chunk (m);
4428
4429  if ((((unsigned long) (m)) % alignment) != 0)   /* misaligned */
4430
4431    { /*
4432                Find an aligned spot inside chunk.  Since we need to give back
4433                leading space in a chunk of at least MINSIZE, if the first
4434                calculation places us at a spot with less than MINSIZE leader,
4435                we can move to the next aligned spot -- we've allocated enough
4436                total room so that this is always possible.
4437                 */
4438      brk = (char *) mem2chunk (((unsigned long) (m + alignment - 1)) &
4439                                - ((signed long) alignment));
4440      if ((unsigned long) (brk - (char *) (p)) < MINSIZE)
4441        brk += alignment;
4442
4443      newp = (mchunkptr) brk;
4444      leadsize = brk - (char *) (p);
4445      newsize = chunksize (p) - leadsize;
4446
4447      /* For mmapped chunks, just adjust offset */
4448      if (chunk_is_mmapped (p))
4449        {
4450          newp->prev_size = p->prev_size + leadsize;
4451          set_head (newp, newsize | IS_MMAPPED);
4452          return chunk2mem (newp);
4453        }
4454
4455      /* Otherwise, give back leader, use the rest */
4456      set_head (newp, newsize | PREV_INUSE |
4457                (av != &main_arena ? NON_MAIN_ARENA : 0));
4458      set_inuse_bit_at_offset (newp, newsize);
4459      set_head_size (p, leadsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
4460      _int_free (av, p, 1);
4461      p = newp;
4462
4463      assert (newsize >= nb &&
4464              (((unsigned long) (chunk2mem (p))) % alignment) == 0);
4465    }
4466
4467  /* Also give back spare room at the end */
4468  if (!chunk_is_mmapped (p))
4469    {
4470      size = chunksize (p);
4471      if ((unsigned long) (size) > (unsigned long) (nb + MINSIZE))
4472        {
4473          remainder_size = size - nb;
4474          remainder = chunk_at_offset (p, nb);
4475          set_head (remainder, remainder_size | PREV_INUSE |
4476                    (av != &main_arena ? NON_MAIN_ARENA : 0));
4477          set_head_size (p, nb);
4478          _int_free (av, remainder, 1);
4479        }
4480    }
4481
4482  check_inuse_chunk (av, p);
4483  return chunk2mem (p);
4484}
4485
4486
4487/*
4488   ------------------------------ malloc_trim ------------------------------
4489 */
4490
4491static int
4492mtrim (mstate av, size_t pad)
4493{
4494  /* Don't touch corrupt arenas.  */
4495  if (arena_is_corrupt (av))
4496    return 0;
4497
4498  /* Ensure initialization/consolidation */
4499  malloc_consolidate (av);
4500
4501  const size_t ps = GLRO (dl_pagesize);
4502  int psindex = bin_index (ps);
4503  const size_t psm1 = ps - 1;
4504
4505  int result = 0;
4506  for (int i = 1; i < NBINS; ++i)
4507    if (i == 1 || i >= psindex)
4508      {
4509        mbinptr bin = bin_at (av, i);
4510
4511        for (mchunkptr p = last (bin); p != bin; p = p->bk)
4512          {
4513            INTERNAL_SIZE_T size = chunksize (p);
4514
4515            if (size > psm1 + sizeof (struct malloc_chunk))
4516              {
4517                /* See whether the chunk contains at least one unused page.  */
4518                char *paligned_mem = (char *) (((uintptr_t) p
4519                                                + sizeof (struct malloc_chunk)
4520                                                + psm1) & ~psm1);
4521
4522                assert ((char *) chunk2mem (p) + 4 * SIZE_SZ <= paligned_mem);
4523                assert ((char *) p + size > paligned_mem);
4524
4525                /* This is the size we could potentially free.  */
4526                size -= paligned_mem - (char *) p;
4527
4528                if (size > psm1)
4529                  {
4530#if MALLOC_DEBUG
4531                    /* When debugging we simulate destroying the memory
4532                       content.  */
4533                    memset (paligned_mem, 0x89, size & ~psm1);
4534#endif
4535                    __madvise (paligned_mem, size & ~psm1, MADV_DONTNEED);
4536
4537                    result = 1;
4538                  }
4539              }
4540          }
4541      }
4542
4543#ifndef MORECORE_CANNOT_TRIM
4544  return result | (av == &main_arena ? systrim (pad, av) : 0);
4545
4546#else
4547  return result;
4548#endif
4549}
4550
4551
4552int
4553__malloc_trim (size_t s)
4554{
4555  int result = 0;
4556
4557  if (__malloc_initialized < 0)
4558    ptmalloc_init ();
4559
4560  mstate ar_ptr = &main_arena;
4561  do
4562    {
4563      (void) mutex_lock (&ar_ptr->mutex);
4564      result |= mtrim (ar_ptr, s);
4565      (void) mutex_unlock (&ar_ptr->mutex);
4566
4567      ar_ptr = ar_ptr->next;
4568    }
4569  while (ar_ptr != &main_arena);
4570
4571  return result;
4572}
4573
4574
4575/*
4576   ------------------------- malloc_usable_size -------------------------
4577 */
4578
4579static size_t
4580musable (void *mem)
4581{
4582  mchunkptr p;
4583  if (mem != 0)
4584    {
4585      p = mem2chunk (mem);
4586
4587      if (__builtin_expect (using_malloc_checking == 1, 0))
4588        return malloc_check_get_size (p);
4589
4590      if (chunk_is_mmapped (p))
4591        return chunksize (p) - 2 * SIZE_SZ;
4592      else if (inuse (p))
4593        return chunksize (p) - SIZE_SZ;
4594    }
4595  return 0;
4596}
4597
4598
4599size_t
4600__malloc_usable_size (void *m)
4601{
4602  size_t result;
4603
4604  result = musable (m);
4605  return result;
4606}
4607
4608/*
4609   ------------------------------ mallinfo ------------------------------
4610   Accumulate malloc statistics for arena AV into M.
4611 */
4612
4613static void
4614int_mallinfo (mstate av, struct mallinfo *m)
4615{
4616  size_t i;
4617  mbinptr b;
4618  mchunkptr p;
4619  INTERNAL_SIZE_T avail;
4620  INTERNAL_SIZE_T fastavail;
4621  int nblocks;
4622  int nfastblocks;
4623
4624  /* Ensure initialization */
4625  if (av->top == 0)
4626    malloc_consolidate (av);
4627
4628  check_malloc_state (av);
4629
4630  /* Account for top */
4631  avail = chunksize (av->top);
4632  nblocks = 1;  /* top always exists */
4633
4634  /* traverse fastbins */
4635  nfastblocks = 0;
4636  fastavail = 0;
4637
4638  for (i = 0; i < NFASTBINS; ++i)
4639    {
4640      for (p = fastbin (av, i); p != 0; p = p->fd)
4641        {
4642          ++nfastblocks;
4643          fastavail += chunksize (p);
4644        }
4645    }
4646
4647  avail += fastavail;
4648
4649  /* traverse regular bins */
4650  for (i = 1; i < NBINS; ++i)
4651    {
4652      b = bin_at (av, i);
4653      for (p = last (b); p != b; p = p->bk)
4654        {
4655          ++nblocks;
4656          avail += chunksize (p);
4657        }
4658    }
4659
4660  m->smblks += nfastblocks;
4661  m->ordblks += nblocks;
4662  m->fordblks += avail;
4663  m->uordblks += av->system_mem - avail;
4664  m->arena += av->system_mem;
4665  m->fsmblks += fastavail;
4666  if (av == &main_arena)
4667    {
4668      m->hblks = mp_.n_mmaps;
4669      m->hblkhd = mp_.mmapped_mem;
4670      m->usmblks = mp_.max_total_mem;
4671      m->keepcost = chunksize (av->top);
4672    }
4673}
4674
4675
4676struct mallinfo
4677__libc_mallinfo (void)
4678{
4679  struct mallinfo m;
4680  mstate ar_ptr;
4681
4682  if (__malloc_initialized < 0)
4683    ptmalloc_init ();
4684
4685  memset (&m, 0, sizeof (m));
4686  ar_ptr = &main_arena;
4687  do
4688    {
4689      (void) mutex_lock (&ar_ptr->mutex);
4690      int_mallinfo (ar_ptr, &m);
4691      (void) mutex_unlock (&ar_ptr->mutex);
4692
4693      ar_ptr = ar_ptr->next;
4694    }
4695  while (ar_ptr != &main_arena);
4696
4697  return m;
4698}
4699
4700/*
4701   ------------------------------ malloc_stats ------------------------------
4702 */
4703
4704void
4705__malloc_stats (void)
4706{
4707  int i;
4708  mstate ar_ptr;
4709  unsigned int in_use_b = mp_.mmapped_mem, system_b = in_use_b;
4710
4711  if (__malloc_initialized < 0)
4712    ptmalloc_init ();
4713  _IO_flockfile (stderr);
4714  int old_flags2 = ((_IO_FILE *) stderr)->_flags2;
4715  ((_IO_FILE *) stderr)->_flags2 |= _IO_FLAGS2_NOTCANCEL;
4716  for (i = 0, ar_ptr = &main_arena;; i++)
4717    {
4718      struct mallinfo mi;
4719
4720      memset (&mi, 0, sizeof (mi));
4721      (void) mutex_lock (&ar_ptr->mutex);
4722      int_mallinfo (ar_ptr, &mi);
4723      fprintf (stderr, "Arena %d:\n", i);
4724      fprintf (stderr, "system bytes     = %10u\n", (unsigned int) mi.arena);
4725      fprintf (stderr, "in use bytes     = %10u\n", (unsigned int) mi.uordblks);
4726#if MALLOC_DEBUG > 1
4727      if (i > 0)
4728        dump_heap (heap_for_ptr (top (ar_ptr)));
4729#endif
4730      system_b += mi.arena;
4731      in_use_b += mi.uordblks;
4732      (void) mutex_unlock (&ar_ptr->mutex);
4733      ar_ptr = ar_ptr->next;
4734      if (ar_ptr == &main_arena)
4735        break;
4736    }
4737  fprintf (stderr, "Total (incl. mmap):\n");
4738  fprintf (stderr, "system bytes     = %10u\n", system_b);
4739  fprintf (stderr, "in use bytes     = %10u\n", in_use_b);
4740  fprintf (stderr, "max mmap regions = %10u\n", (unsigned int) mp_.max_n_mmaps);
4741  fprintf (stderr, "max mmap bytes   = %10lu\n",
4742           (unsigned long) mp_.max_mmapped_mem);
4743  ((_IO_FILE *) stderr)->_flags2 |= old_flags2;
4744  _IO_funlockfile (stderr);
4745}
4746
4747
4748/*
4749   ------------------------------ mallopt ------------------------------
4750 */
4751
4752int
4753__libc_mallopt (int param_number, int value)
4754{
4755  mstate av = &main_arena;
4756  int res = 1;
4757
4758  if (__malloc_initialized < 0)
4759    ptmalloc_init ();
4760  (void) mutex_lock (&av->mutex);
4761  /* Ensure initialization/consolidation */
4762  malloc_consolidate (av);
4763
4764  LIBC_PROBE (memory_mallopt, 2, param_number, value);
4765
4766  switch (param_number)
4767    {
4768    case M_MXFAST:
4769      if (value >= 0 && value <= MAX_FAST_SIZE)
4770        {
4771          LIBC_PROBE (memory_mallopt_mxfast, 2, value, get_max_fast ());
4772          set_max_fast (value);
4773        }
4774      else
4775        res = 0;
4776      break;
4777
4778    case M_TRIM_THRESHOLD:
4779      LIBC_PROBE (memory_mallopt_trim_threshold, 3, value,
4780                  mp_.trim_threshold, mp_.no_dyn_threshold);
4781      mp_.trim_threshold = value;
4782      mp_.no_dyn_threshold = 1;
4783      break;
4784
4785    case M_TOP_PAD:
4786      LIBC_PROBE (memory_mallopt_top_pad, 3, value,
4787                  mp_.top_pad, mp_.no_dyn_threshold);
4788      mp_.top_pad = value;
4789      mp_.no_dyn_threshold = 1;
4790      break;
4791
4792    case M_MMAP_THRESHOLD:
4793      /* Forbid setting the threshold too high. */
4794      if ((unsigned long) value > HEAP_MAX_SIZE / 2)
4795        res = 0;
4796      else
4797        {
4798          LIBC_PROBE (memory_mallopt_mmap_threshold, 3, value,
4799                      mp_.mmap_threshold, mp_.no_dyn_threshold);
4800          mp_.mmap_threshold = value;
4801          mp_.no_dyn_threshold = 1;
4802        }
4803      break;
4804
4805    case M_MMAP_MAX:
4806      LIBC_PROBE (memory_mallopt_mmap_max, 3, value,
4807                  mp_.n_mmaps_max, mp_.no_dyn_threshold);
4808      mp_.n_mmaps_max = value;
4809      mp_.no_dyn_threshold = 1;
4810      break;
4811
4812    case M_CHECK_ACTION:
4813      LIBC_PROBE (memory_mallopt_check_action, 2, value, check_action);
4814      check_action = value;
4815      break;
4816
4817    case M_PERTURB:
4818      LIBC_PROBE (memory_mallopt_perturb, 2, value, perturb_byte);
4819      perturb_byte = value;
4820      break;
4821
4822    case M_ARENA_TEST:
4823      if (value > 0)
4824        {
4825          LIBC_PROBE (memory_mallopt_arena_test, 2, value, mp_.arena_test);
4826          mp_.arena_test = value;
4827        }
4828      break;
4829
4830    case M_ARENA_MAX:
4831      if (value > 0)
4832        {
4833          LIBC_PROBE (memory_mallopt_arena_max, 2, value, mp_.arena_max);
4834          mp_.arena_max = value;
4835        }
4836      break;
4837    }
4838  (void) mutex_unlock (&av->mutex);
4839  return res;
4840}
4841libc_hidden_def (__libc_mallopt)
4842
4843
4844/*
4845   -------------------- Alternative MORECORE functions --------------------
4846 */
4847
4848
4849/*
4850   General Requirements for MORECORE.
4851
4852   The MORECORE function must have the following properties:
4853
4854   If MORECORE_CONTIGUOUS is false:
4855
4856 * MORECORE must allocate in multiples of pagesize. It will
4857      only be called with arguments that are multiples of pagesize.
4858
4859 * MORECORE(0) must return an address that is at least
4860      MALLOC_ALIGNMENT aligned. (Page-aligning always suffices.)
4861
4862   else (i.e. If MORECORE_CONTIGUOUS is true):
4863
4864 * Consecutive calls to MORECORE with positive arguments
4865      return increasing addresses, indicating that space has been
4866      contiguously extended.
4867
4868 * MORECORE need not allocate in multiples of pagesize.
4869      Calls to MORECORE need not have args of multiples of pagesize.
4870
4871 * MORECORE need not page-align.
4872
4873   In either case:
4874
4875 * MORECORE may allocate more memory than requested. (Or even less,
4876      but this will generally result in a malloc failure.)
4877
4878 * MORECORE must not allocate memory when given argument zero, but
4879      instead return one past the end address of memory from previous
4880      nonzero call. This malloc does NOT call MORECORE(0)
4881      until at least one call with positive arguments is made, so
4882      the initial value returned is not important.
4883
4884 * Even though consecutive calls to MORECORE need not return contiguous
4885      addresses, it must be OK for malloc'ed chunks to span multiple
4886      regions in those cases where they do happen to be contiguous.
4887
4888 * MORECORE need not handle negative arguments -- it may instead
4889      just return MORECORE_FAILURE when given negative arguments.
4890      Negative arguments are always multiples of pagesize. MORECORE
4891      must not misinterpret negative args as large positive unsigned
4892      args. You can suppress all such calls from even occurring by defining
4893      MORECORE_CANNOT_TRIM,
4894
4895   There is some variation across systems about the type of the
4896   argument to sbrk/MORECORE. If size_t is unsigned, then it cannot
4897   actually be size_t, because sbrk supports negative args, so it is
4898   normally the signed type of the same width as size_t (sometimes
4899   declared as "intptr_t", and sometimes "ptrdiff_t").  It doesn't much
4900   matter though. Internally, we use "long" as arguments, which should
4901   work across all reasonable possibilities.
4902
4903   Additionally, if MORECORE ever returns failure for a positive
4904   request, then mmap is used as a noncontiguous system allocator. This
4905   is a useful backup strategy for systems with holes in address spaces
4906   -- in this case sbrk cannot contiguously expand the heap, but mmap
4907   may be able to map noncontiguous space.
4908
4909   If you'd like mmap to ALWAYS be used, you can define MORECORE to be
4910   a function that always returns MORECORE_FAILURE.
4911
4912   If you are using this malloc with something other than sbrk (or its
4913   emulation) to supply memory regions, you probably want to set
4914   MORECORE_CONTIGUOUS as false.  As an example, here is a custom
4915   allocator kindly contributed for pre-OSX macOS.  It uses virtually
4916   but not necessarily physically contiguous non-paged memory (locked
4917   in, present and won't get swapped out).  You can use it by
4918   uncommenting this section, adding some #includes, and setting up the
4919   appropriate defines above:
4920
4921 *#define MORECORE osMoreCore
4922 *#define MORECORE_CONTIGUOUS 0
4923
4924   There is also a shutdown routine that should somehow be called for
4925   cleanup upon program exit.
4926
4927 *#define MAX_POOL_ENTRIES 100
4928 *#define MINIMUM_MORECORE_SIZE  (64 * 1024)
4929   static int next_os_pool;
4930   void *our_os_pools[MAX_POOL_ENTRIES];
4931
4932   void *osMoreCore(int size)
4933   {
4934    void *ptr = 0;
4935    static void *sbrk_top = 0;
4936
4937    if (size > 0)
4938    {
4939      if (size < MINIMUM_MORECORE_SIZE)
4940         size = MINIMUM_MORECORE_SIZE;
4941      if (CurrentExecutionLevel() == kTaskLevel)
4942         ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4943      if (ptr == 0)
4944      {
4945        return (void *) MORECORE_FAILURE;
4946      }
4947      // save ptrs so they can be freed during cleanup
4948      our_os_pools[next_os_pool] = ptr;
4949      next_os_pool++;
4950      ptr = (void *) ((((unsigned long) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4951      sbrk_top = (char *) ptr + size;
4952      return ptr;
4953    }
4954    else if (size < 0)
4955    {
4956      // we don't currently support shrink behavior
4957      return (void *) MORECORE_FAILURE;
4958    }
4959    else
4960    {
4961      return sbrk_top;
4962    }
4963   }
4964
4965   // cleanup any allocated memory pools
4966   // called as last thing before shutting down driver
4967
4968   void osCleanupMem(void)
4969   {
4970    void **ptr;
4971
4972    for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4973      if (*ptr)
4974      {
4975         PoolDeallocate(*ptr);
4976 * ptr = 0;
4977      }
4978   }
4979
4980 */
4981
4982
4983/* Helper code.  */
4984
4985extern char **__libc_argv attribute_hidden;
4986
4987static void
4988malloc_printerr (int action, const char *str, void *ptr, mstate ar_ptr)
4989{
4990  /* Avoid using this arena in future.  We do not attempt to synchronize this
4991     with anything else because we minimally want to ensure that __libc_message
4992     gets its resources safely without stumbling on the current corruption.  */
4993  if (ar_ptr)
4994    set_arena_corrupt (ar_ptr);
4995
4996  if ((action & 5) == 5)
4997    __libc_message (action & 2, "%s\n", str);
4998  else if (action & 1)
4999    {
5000      char buf[2 * sizeof (uintptr_t) + 1];
5001
5002      buf[sizeof (buf) - 1] = '\0';
5003      char *cp = _itoa_word ((uintptr_t) ptr, &buf[sizeof (buf) - 1], 16, 0);
5004      while (cp > buf)
5005        *--cp = '0';
5006
5007      __libc_message (action & 2, "*** Error in `%s': %s: 0x%s ***\n",
5008                      __libc_argv[0] ? : "<unknown>", str, cp);
5009    }
5010  else if (action & 2)
5011    abort ();
5012}
5013
5014/* We need a wrapper function for one of the additions of POSIX.  */
5015int
5016__posix_memalign (void **memptr, size_t alignment, size_t size)
5017{
5018  void *mem;
5019
5020  /* Test whether the SIZE argument is valid.  It must be a power of
5021     two multiple of sizeof (void *).  */
5022  if (alignment % sizeof (void *) != 0
5023      || !powerof2 (alignment / sizeof (void *))
5024      || alignment == 0)
5025    return EINVAL;
5026
5027
5028  void *address = RETURN_ADDRESS (0);
5029  mem = _mid_memalign (alignment, size, address);
5030
5031  if (mem != NULL)
5032    {
5033      *memptr = mem;
5034      return 0;
5035    }
5036
5037  return ENOMEM;
5038}
5039weak_alias (__posix_memalign, posix_memalign)
5040
5041
5042int
5043__malloc_info (int options, FILE *fp)
5044{
5045  /* For now, at least.  */
5046  if (options != 0)
5047    return EINVAL;
5048
5049  int n = 0;
5050  size_t total_nblocks = 0;
5051  size_t total_nfastblocks = 0;
5052  size_t total_avail = 0;
5053  size_t total_fastavail = 0;
5054  size_t total_system = 0;
5055  size_t total_max_system = 0;
5056  size_t total_aspace = 0;
5057  size_t total_aspace_mprotect = 0;
5058
5059
5060
5061  if (__malloc_initialized < 0)
5062    ptmalloc_init ();
5063
5064  fputs ("<malloc version=\"1\">\n", fp);
5065
5066  /* Iterate over all arenas currently in use.  */
5067  mstate ar_ptr = &main_arena;
5068  do
5069    {
5070      fprintf (fp, "<heap nr=\"%d\">\n<sizes>\n", n++);
5071
5072      size_t nblocks = 0;
5073      size_t nfastblocks = 0;
5074      size_t avail = 0;
5075      size_t fastavail = 0;
5076      struct
5077      {
5078	size_t from;
5079	size_t to;
5080	size_t total;
5081	size_t count;
5082      } sizes[NFASTBINS + NBINS - 1];
5083#define nsizes (sizeof (sizes) / sizeof (sizes[0]))
5084
5085      mutex_lock (&ar_ptr->mutex);
5086
5087      for (size_t i = 0; i < NFASTBINS; ++i)
5088	{
5089	  mchunkptr p = fastbin (ar_ptr, i);
5090	  if (p != NULL)
5091	    {
5092	      size_t nthissize = 0;
5093	      size_t thissize = chunksize (p);
5094
5095	      while (p != NULL)
5096		{
5097		  ++nthissize;
5098		  p = p->fd;
5099		}
5100
5101	      fastavail += nthissize * thissize;
5102	      nfastblocks += nthissize;
5103	      sizes[i].from = thissize - (MALLOC_ALIGNMENT - 1);
5104	      sizes[i].to = thissize;
5105	      sizes[i].count = nthissize;
5106	    }
5107	  else
5108	    sizes[i].from = sizes[i].to = sizes[i].count = 0;
5109
5110	  sizes[i].total = sizes[i].count * sizes[i].to;
5111	}
5112
5113
5114      mbinptr bin;
5115      struct malloc_chunk *r;
5116
5117      for (size_t i = 1; i < NBINS; ++i)
5118	{
5119	  bin = bin_at (ar_ptr, i);
5120	  r = bin->fd;
5121	  sizes[NFASTBINS - 1 + i].from = ~((size_t) 0);
5122	  sizes[NFASTBINS - 1 + i].to = sizes[NFASTBINS - 1 + i].total
5123					  = sizes[NFASTBINS - 1 + i].count = 0;
5124
5125	  if (r != NULL)
5126	    while (r != bin)
5127	      {
5128		++sizes[NFASTBINS - 1 + i].count;
5129		sizes[NFASTBINS - 1 + i].total += r->size;
5130		sizes[NFASTBINS - 1 + i].from
5131		  = MIN (sizes[NFASTBINS - 1 + i].from, r->size);
5132		sizes[NFASTBINS - 1 + i].to = MAX (sizes[NFASTBINS - 1 + i].to,
5133						   r->size);
5134
5135		r = r->fd;
5136	      }
5137
5138	  if (sizes[NFASTBINS - 1 + i].count == 0)
5139	    sizes[NFASTBINS - 1 + i].from = 0;
5140	  nblocks += sizes[NFASTBINS - 1 + i].count;
5141	  avail += sizes[NFASTBINS - 1 + i].total;
5142	}
5143
5144      mutex_unlock (&ar_ptr->mutex);
5145
5146      total_nfastblocks += nfastblocks;
5147      total_fastavail += fastavail;
5148
5149      total_nblocks += nblocks;
5150      total_avail += avail;
5151
5152      for (size_t i = 0; i < nsizes; ++i)
5153	if (sizes[i].count != 0 && i != NFASTBINS)
5154	  fprintf (fp, "							      \
5155  <size from=\"%zu\" to=\"%zu\" total=\"%zu\" count=\"%zu\"/>\n",
5156		   sizes[i].from, sizes[i].to, sizes[i].total, sizes[i].count);
5157
5158      if (sizes[NFASTBINS].count != 0)
5159	fprintf (fp, "\
5160  <unsorted from=\"%zu\" to=\"%zu\" total=\"%zu\" count=\"%zu\"/>\n",
5161		 sizes[NFASTBINS].from, sizes[NFASTBINS].to,
5162		 sizes[NFASTBINS].total, sizes[NFASTBINS].count);
5163
5164      total_system += ar_ptr->system_mem;
5165      total_max_system += ar_ptr->max_system_mem;
5166
5167      fprintf (fp,
5168	       "</sizes>\n<total type=\"fast\" count=\"%zu\" size=\"%zu\"/>\n"
5169	       "<total type=\"rest\" count=\"%zu\" size=\"%zu\"/>\n"
5170	       "<system type=\"current\" size=\"%zu\"/>\n"
5171	       "<system type=\"max\" size=\"%zu\"/>\n",
5172	       nfastblocks, fastavail, nblocks, avail,
5173	       ar_ptr->system_mem, ar_ptr->max_system_mem);
5174
5175      if (ar_ptr != &main_arena)
5176	{
5177	  heap_info *heap = heap_for_ptr (top (ar_ptr));
5178	  fprintf (fp,
5179		   "<aspace type=\"total\" size=\"%zu\"/>\n"
5180		   "<aspace type=\"mprotect\" size=\"%zu\"/>\n",
5181		   heap->size, heap->mprotect_size);
5182	  total_aspace += heap->size;
5183	  total_aspace_mprotect += heap->mprotect_size;
5184	}
5185      else
5186	{
5187	  fprintf (fp,
5188		   "<aspace type=\"total\" size=\"%zu\"/>\n"
5189		   "<aspace type=\"mprotect\" size=\"%zu\"/>\n",
5190		   ar_ptr->system_mem, ar_ptr->system_mem);
5191	  total_aspace += ar_ptr->system_mem;
5192	  total_aspace_mprotect += ar_ptr->system_mem;
5193	}
5194
5195      fputs ("</heap>\n", fp);
5196      ar_ptr = ar_ptr->next;
5197    }
5198  while (ar_ptr != &main_arena);
5199
5200  fprintf (fp,
5201	   "<total type=\"fast\" count=\"%zu\" size=\"%zu\"/>\n"
5202	   "<total type=\"rest\" count=\"%zu\" size=\"%zu\"/>\n"
5203	   "<total type=\"mmap\" count=\"%d\" size=\"%zu\"/>\n"
5204	   "<system type=\"current\" size=\"%zu\"/>\n"
5205	   "<system type=\"max\" size=\"%zu\"/>\n"
5206	   "<aspace type=\"total\" size=\"%zu\"/>\n"
5207	   "<aspace type=\"mprotect\" size=\"%zu\"/>\n"
5208	   "</malloc>\n",
5209	   total_nfastblocks, total_fastavail, total_nblocks, total_avail,
5210	   mp_.n_mmaps, mp_.mmapped_mem,
5211	   total_system, total_max_system,
5212	   total_aspace, total_aspace_mprotect);
5213
5214  return 0;
5215}
5216weak_alias (__malloc_info, malloc_info)
5217
5218
5219strong_alias (__libc_calloc, __calloc) weak_alias (__libc_calloc, calloc)
5220strong_alias (__libc_free, __cfree) weak_alias (__libc_free, cfree)
5221strong_alias (__libc_free, __free) strong_alias (__libc_free, free)
5222strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)
5223strong_alias (__libc_memalign, __memalign)
5224weak_alias (__libc_memalign, memalign)
5225strong_alias (__libc_realloc, __realloc) strong_alias (__libc_realloc, realloc)
5226strong_alias (__libc_valloc, __valloc) weak_alias (__libc_valloc, valloc)
5227strong_alias (__libc_pvalloc, __pvalloc) weak_alias (__libc_pvalloc, pvalloc)
5228strong_alias (__libc_mallinfo, __mallinfo)
5229weak_alias (__libc_mallinfo, mallinfo)
5230strong_alias (__libc_mallopt, __mallopt) weak_alias (__libc_mallopt, mallopt)
5231
5232weak_alias (__malloc_stats, malloc_stats)
5233weak_alias (__malloc_usable_size, malloc_usable_size)
5234weak_alias (__malloc_trim, malloc_trim)
5235weak_alias (__malloc_get_state, malloc_get_state)
5236weak_alias (__malloc_set_state, malloc_set_state)
5237
5238
5239/* ------------------------------------------------------------
5240   History:
5241
5242   [see ftp://g.oswego.edu/pub/misc/malloc.c for the history of dlmalloc]
5243
5244 */
5245/*
5246 * Local variables:
5247 * c-basic-offset: 2
5248 * End:
5249 */
5250