malloc.c source code [glibc/malloc/malloc.c]

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

Browse the source code of glibc/malloc/malloc.c