Line data Source code
1 : /*
2 : This is a version (aka dlmalloc) of malloc/free/realloc written by
3 : Doug Lea and released to the public domain, as explained at
4 : http://creativecommons.org/licenses/publicdomain. Send questions,
5 : comments, complaints, performance data, etc to dl@cs.oswego.edu
6 :
7 : * Version 2.8.3 Thu Sep 22 11:16:15 2005 Doug Lea (dl at gee)
8 :
9 : Note: There may be an updated version of this malloc obtainable at
10 : ftp://gee.cs.oswego.edu/pub/misc/malloc.c
11 : Check before installing!
12 :
13 : * Quickstart
14 :
15 : This library is all in one file to simplify the most common usage:
16 : ftp it, compile it (-O3), and link it into another program. All of
17 : the compile-time options default to reasonable values for use on
18 : most platforms. You might later want to step through various
19 : compile-time and dynamic tuning options.
20 :
21 : For convenience, an include file for code using this malloc is at:
22 : ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.3.h
23 : You don't really need this .h file unless you call functions not
24 : defined in your system include files. The .h file contains only the
25 : excerpts from this file needed for using this malloc on ANSI C/C++
26 : systems, so long as you haven't changed compile-time options about
27 : naming and tuning parameters. If you do, then you can create your
28 : own malloc.h that does include all settings by cutting at the point
29 : indicated below. Note that you may already by default be using a C
30 : library containing a malloc that is based on some version of this
31 : malloc (for example in linux). You might still want to use the one
32 : in this file to customize settings or to avoid overheads associated
33 : with library versions.
34 :
35 : * Vital statistics:
36 :
37 : Supported pointer/size_t representation: 4 or 8 bytes
38 : size_t MUST be an unsigned type of the same width as
39 : pointers. (If you are using an ancient system that declares
40 : size_t as a signed type, or need it to be a different width
41 : than pointers, you can use a previous release of this malloc
42 : (e.g. 2.7.2) supporting these.)
43 :
44 : Alignment: 8 bytes (default)
45 : This suffices for nearly all current machines and C compilers.
46 : However, you can define MALLOC_ALIGNMENT to be wider than this
47 : if necessary (up to 128bytes), at the expense of using more space.
48 :
49 : Minimum overhead per allocated chunk: 4 or 8 bytes (if 4byte sizes)
50 : 8 or 16 bytes (if 8byte sizes)
51 : Each malloced chunk has a hidden word of overhead holding size
52 : and status information, and additional cross-check word
53 : if FOOTERS is defined.
54 :
55 : Minimum allocated size: 4-byte ptrs: 16 bytes (including overhead)
56 : 8-byte ptrs: 32 bytes (including overhead)
57 :
58 : Even a request for zero bytes (i.e., malloc(0)) returns a
59 : pointer to something of the minimum allocatable size.
60 : The maximum overhead wastage (i.e., number of extra bytes
61 : allocated than were requested in malloc) is less than or equal
62 : to the minimum size, except for requests >= mmap_threshold that
63 : are serviced via mmap(), where the worst case wastage is about
64 : 32 bytes plus the remainder from a system page (the minimal
65 : mmap unit); typically 4096 or 8192 bytes.
66 :
67 : Security: static-safe; optionally more or less
68 : The "security" of malloc refers to the ability of malicious
69 : code to accentuate the effects of errors (for example, freeing
70 : space that is not currently malloc'ed or overwriting past the
71 : ends of chunks) in code that calls malloc. This malloc
72 : guarantees not to modify any memory locations below the base of
73 : heap, i.e., static variables, even in the presence of usage
74 : errors. The routines additionally detect most improper frees
75 : and reallocs. All this holds as long as the static bookkeeping
76 : for malloc itself is not corrupted by some other means. This
77 : is only one aspect of security -- these checks do not, and
78 : cannot, detect all possible programming errors.
79 :
80 : If FOOTERS is defined nonzero, then each allocated chunk
81 : carries an additional check word to verify that it was malloced
82 : from its space. These check words are the same within each
83 : execution of a program using malloc, but differ across
84 : executions, so externally crafted fake chunks cannot be
85 : freed. This improves security by rejecting frees/reallocs that
86 : could corrupt heap memory, in addition to the checks preventing
87 : writes to statics that are always on. This may further improve
88 : security at the expense of time and space overhead. (Note that
89 : FOOTERS may also be worth using with MSPACES.)
90 :
91 : By default detected errors cause the program to abort (calling
92 : "abort()"). You can override this to instead proceed past
93 : errors by defining PROCEED_ON_ERROR. In this case, a bad free
94 : has no effect, and a malloc that encounters a bad address
95 : caused by user overwrites will ignore the bad address by
96 : dropping pointers and indices to all known memory. This may
97 : be appropriate for programs that should continue if at all
98 : possible in the face of programming errors, although they may
99 : run out of memory because dropped memory is never reclaimed.
100 :
101 : If you don't like either of these options, you can define
102 : CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything
103 : else. And if if you are sure that your program using malloc has
104 : no errors or vulnerabilities, you can define INSECURE to 1,
105 : which might (or might not) provide a small performance improvement.
106 :
107 : Thread-safety: NOT thread-safe unless USE_LOCKS defined
108 : When USE_LOCKS is defined, each public call to malloc, free,
109 : etc is surrounded with either a pthread mutex or a win32
110 : spinlock (depending on WIN32). This is not especially fast, and
111 : can be a major bottleneck. It is designed only to provide
112 : minimal protection in concurrent environments, and to provide a
113 : basis for extensions. If you are using malloc in a concurrent
114 : program, consider instead using ptmalloc, which is derived from
115 : a version of this malloc. (See http://www.malloc.de).
116 :
117 : System requirements: Any combination of MORECORE and/or MMAP/MUNMAP
118 : This malloc can use unix sbrk or any emulation (invoked using
119 : the CALL_MORECORE macro) and/or mmap/munmap or any emulation
120 : (invoked using CALL_MMAP/CALL_MUNMAP) to get and release system
121 : memory. On most unix systems, it tends to work best if both
122 : MORECORE and MMAP are enabled. On Win32, it uses emulations
123 : based on VirtualAlloc. It also uses common C library functions
124 : like memset.
125 :
126 : Compliance: I believe it is compliant with the Single Unix Specification
127 : (See http://www.unix.org). Also SVID/XPG, ANSI C, and probably
128 : others as well.
129 :
130 : * Overview of algorithms
131 :
132 : This is not the fastest, most space-conserving, most portable, or
133 : most tunable malloc ever written. However it is among the fastest
134 : while also being among the most space-conserving, portable and
135 : tunable. Consistent balance across these factors results in a good
136 : general-purpose allocator for malloc-intensive programs.
137 :
138 : In most ways, this malloc is a best-fit allocator. Generally, it
139 : chooses the best-fitting existing chunk for a request, with ties
140 : broken in approximately least-recently-used order. (This strategy
141 : normally maintains low fragmentation.) However, for requests less
142 : than 256bytes, it deviates from best-fit when there is not an
143 : exactly fitting available chunk by preferring to use space adjacent
144 : to that used for the previous small request, as well as by breaking
145 : ties in approximately most-recently-used order. (These enhance
146 : locality of series of small allocations.) And for very large requests
147 : (>= 256Kb by default), it relies on system memory mapping
148 : facilities, if supported. (This helps avoid carrying around and
149 : possibly fragmenting memory used only for large chunks.)
150 :
151 : All operations (except malloc_stats and mallinfo) have execution
152 : times that are bounded by a constant factor of the number of bits in
153 : a size_t, not counting any clearing in calloc or copying in realloc,
154 : or actions surrounding MORECORE and MMAP that have times
155 : proportional to the number of non-contiguous regions returned by
156 : system allocation routines, which is often just 1.
157 :
158 : The implementation is not very modular and seriously overuses
159 : macros. Perhaps someday all C compilers will do as good a job
160 : inlining modular code as can now be done by brute-force expansion,
161 : but now, enough of them seem not to.
162 :
163 : Some compilers issue a lot of warnings about code that is
164 : dead/unreachable only on some platforms, and also about intentional
165 : uses of negation on unsigned types. All known cases of each can be
166 : ignored.
167 :
168 : For a longer but out of date high-level description, see
169 : http://gee.cs.oswego.edu/dl/html/malloc.html
170 :
171 : * MSPACES
172 : If MSPACES is defined, then in addition to malloc, free, etc.,
173 : this file also defines mspace_malloc, mspace_free, etc. These
174 : are versions of malloc routines that take an "mspace" argument
175 : obtained using create_mspace, to control all internal bookkeeping.
176 : If ONLY_MSPACES is defined, only these versions are compiled.
177 : So if you would like to use this allocator for only some allocations,
178 : and your system malloc for others, you can compile with
179 : ONLY_MSPACES and then do something like...
180 : static mspace mymspace = create_mspace(0,0); // for example
181 : #define mymalloc(bytes) mspace_malloc(mymspace, bytes)
182 :
183 : (Note: If you only need one instance of an mspace, you can instead
184 : use "USE_DL_PREFIX" to relabel the global malloc.)
185 :
186 : You can similarly create thread-local allocators by storing
187 : mspaces as thread-locals. For example:
188 : static __thread mspace tlms = 0;
189 : void* tlmalloc(size_t bytes) {
190 : if (tlms == 0) tlms = create_mspace(0, 0);
191 : return mspace_malloc(tlms, bytes);
192 : }
193 : void tlfree(void* mem) { mspace_free(tlms, mem); }
194 :
195 : Unless FOOTERS is defined, each mspace is completely independent.
196 : You cannot allocate from one and free to another (although
197 : conformance is only weakly checked, so usage errors are not always
198 : caught). If FOOTERS is defined, then each chunk carries around a tag
199 : indicating its originating mspace, and frees are directed to their
200 : originating spaces.
201 :
202 : ------------------------- Compile-time options ---------------------------
203 :
204 : Be careful in setting #define values for numerical constants of type
205 : size_t. On some systems, literal values are not automatically extended
206 : to size_t precision unless they are explicitly casted.
207 :
208 : WIN32 default: defined if _WIN32 defined
209 : Defining WIN32 sets up defaults for MS environment and compilers.
210 : Otherwise defaults are for unix.
211 :
212 : MALLOC_ALIGNMENT default: (size_t)8
213 : Controls the minimum alignment for malloc'ed chunks. It must be a
214 : power of two and at least 8, even on machines for which smaller
215 : alignments would suffice. It may be defined as larger than this
216 : though. Note however that code and data structures are optimized for
217 : the case of 8-byte alignment.
218 :
219 : MSPACES default: 0 (false)
220 : If true, compile in support for independent allocation spaces.
221 : This is only supported if HAVE_MMAP is true.
222 :
223 : ONLY_MSPACES default: 0 (false)
224 : If true, only compile in mspace versions, not regular versions.
225 :
226 : USE_LOCKS default: 0 (false)
227 : Causes each call to each public routine to be surrounded with
228 : pthread or WIN32 mutex lock/unlock. (If set true, this can be
229 : overridden on a per-mspace basis for mspace versions.)
230 :
231 : FOOTERS default: 0
232 : If true, provide extra checking and dispatching by placing
233 : information in the footers of allocated chunks. This adds
234 : space and time overhead.
235 :
236 : INSECURE default: 0
237 : If true, omit checks for usage errors and heap space overwrites.
238 :
239 : USE_DL_PREFIX default: NOT defined
240 : Causes compiler to prefix all public routines with the string 'dl'.
241 : This can be useful when you only want to use this malloc in one part
242 : of a program, using your regular system malloc elsewhere.
243 :
244 : ABORT default: defined as abort()
245 : Defines how to abort on failed checks. On most systems, a failed
246 : check cannot die with an "assert" or even print an informative
247 : message, because the underlying print routines in turn call malloc,
248 : which will fail again. Generally, the best policy is to simply call
249 : abort(). It's not very useful to do more than this because many
250 : errors due to overwriting will show up as address faults (null, odd
251 : addresses etc) rather than malloc-triggered checks, so will also
252 : abort. Also, most compilers know that abort() does not return, so
253 : can better optimize code conditionally calling it.
254 :
255 : PROCEED_ON_ERROR default: defined as 0 (false)
256 : Controls whether detected bad addresses cause them to bypassed
257 : rather than aborting. If set, detected bad arguments to free and
258 : realloc are ignored. And all bookkeeping information is zeroed out
259 : upon a detected overwrite of freed heap space, thus losing the
260 : ability to ever return it from malloc again, but enabling the
261 : application to proceed. If PROCEED_ON_ERROR is defined, the
262 : static variable malloc_corruption_error_count is compiled in
263 : and can be examined to see if errors have occurred. This option
264 : generates slower code than the default abort policy.
265 :
266 : DEBUG default: NOT defined
267 : The DEBUG setting is mainly intended for people trying to modify
268 : this code or diagnose problems when porting to new platforms.
269 : However, it may also be able to better isolate user errors than just
270 : using runtime checks. The assertions in the check routines spell
271 : out in more detail the assumptions and invariants underlying the
272 : algorithms. The checking is fairly extensive, and will slow down
273 : execution noticeably. Calling malloc_stats or mallinfo with DEBUG
274 : set will attempt to check every non-mmapped allocated and free chunk
275 : in the course of computing the summaries.
276 :
277 : ABORT_ON_ASSERT_FAILURE default: defined as 1 (true)
278 : Debugging assertion failures can be nearly impossible if your
279 : version of the assert macro causes malloc to be called, which will
280 : lead to a cascade of further failures, blowing the runtime stack.
281 : ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),
282 : which will usually make debugging easier.
283 :
284 : MALLOC_FAILURE_ACTION default: sets errno to ENOMEM, or no-op on win32
285 : The action to take before "return 0" when malloc fails to be able to
286 : return memory because there is none available.
287 :
288 : HAVE_MORECORE default: 1 (true) unless win32 or ONLY_MSPACES
289 : True if this system supports sbrk or an emulation of it.
290 :
291 : MORECORE default: sbrk
292 : The name of the sbrk-style system routine to call to obtain more
293 : memory. See below for guidance on writing custom MORECORE
294 : functions. The type of the argument to sbrk/MORECORE varies across
295 : systems. It cannot be size_t, because it supports negative
296 : arguments, so it is normally the signed type of the same width as
297 : size_t (sometimes declared as "intptr_t"). It doesn't much matter
298 : though. Internally, we only call it with arguments less than half
299 : the max value of a size_t, which should work across all reasonable
300 : possibilities, although sometimes generating compiler warnings. See
301 : near the end of this file for guidelines for creating a custom
302 : version of MORECORE.
303 :
304 : MORECORE_CONTIGUOUS default: 1 (true)
305 : If true, take advantage of fact that consecutive calls to MORECORE
306 : with positive arguments always return contiguous increasing
307 : addresses. This is true of unix sbrk. It does not hurt too much to
308 : set it true anyway, since malloc copes with non-contiguities.
309 : Setting it false when definitely non-contiguous saves time
310 : and possibly wasted space it would take to discover this though.
311 :
312 : MORECORE_CANNOT_TRIM default: NOT defined
313 : True if MORECORE cannot release space back to the system when given
314 : negative arguments. This is generally necessary only if you are
315 : using a hand-crafted MORECORE function that cannot handle negative
316 : arguments.
317 :
318 : HAVE_MMAP default: 1 (true)
319 : True if this system supports mmap or an emulation of it. If so, and
320 : HAVE_MORECORE is not true, MMAP is used for all system
321 : allocation. If set and HAVE_MORECORE is true as well, MMAP is
322 : primarily used to directly allocate very large blocks. It is also
323 : used as a backup strategy in cases where MORECORE fails to provide
324 : space from system. Note: A single call to MUNMAP is assumed to be
325 : able to unmap memory that may have be allocated using multiple calls
326 : to MMAP, so long as they are adjacent.
327 :
328 : HAVE_MREMAP default: 1 on linux, else 0
329 : If true realloc() uses mremap() to re-allocate large blocks and
330 : extend or shrink allocation spaces.
331 :
332 : MMAP_CLEARS default: 1 on unix
333 : True if mmap clears memory so calloc doesn't need to. This is true
334 : for standard unix mmap using /dev/zero.
335 :
336 : USE_BUILTIN_FFS default: 0 (i.e., not used)
337 : Causes malloc to use the builtin ffs() function to compute indices.
338 : Some compilers may recognize and intrinsify ffs to be faster than the
339 : supplied C version. Also, the case of x86 using gcc is special-cased
340 : to an asm instruction, so is already as fast as it can be, and so
341 : this setting has no effect. (On most x86s, the asm version is only
342 : slightly faster than the C version.)
343 :
344 : malloc_getpagesize default: derive from system includes, or 4096.
345 : The system page size. To the extent possible, this malloc manages
346 : memory from the system in page-size units. This may be (and
347 : usually is) a function rather than a constant. This is ignored
348 : if WIN32, where page size is determined using getSystemInfo during
349 : initialization.
350 :
351 : USE_DEV_RANDOM default: 0 (i.e., not used)
352 : Causes malloc to use /dev/random to initialize secure magic seed for
353 : stamping footers. Otherwise, the current time is used.
354 :
355 : NO_MALLINFO default: 0
356 : If defined, don't compile "mallinfo". This can be a simple way
357 : of dealing with mismatches between system declarations and
358 : those in this file.
359 :
360 : MALLINFO_FIELD_TYPE default: size_t
361 : The type of the fields in the mallinfo struct. This was originally
362 : defined as "int" in SVID etc, but is more usefully defined as
363 : size_t. The value is used only if HAVE_USR_INCLUDE_MALLOC_H is not set
364 :
365 : REALLOC_ZERO_BYTES_FREES default: not defined
366 : This should be set if a call to realloc with zero bytes should
367 : be the same as a call to free. Some people think it should. Otherwise,
368 : since this malloc returns a unique pointer for malloc(0), so does
369 : realloc(p, 0).
370 :
371 : LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H
372 : LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H, LACKS_ERRNO_H
373 : LACKS_STDLIB_H default: NOT defined unless on WIN32
374 : Define these if your system does not have these header files.
375 : You might need to manually insert some of the declarations they provide.
376 :
377 : DEFAULT_GRANULARITY default: page size if MORECORE_CONTIGUOUS,
378 : system_info.dwAllocationGranularity in WIN32,
379 : otherwise 64K.
380 : Also settable using mallopt(M_GRANULARITY, x)
381 : The unit for allocating and deallocating memory from the system. On
382 : most systems with contiguous MORECORE, there is no reason to
383 : make this more than a page. However, systems with MMAP tend to
384 : either require or encourage larger granularities. You can increase
385 : this value to prevent system allocation functions to be called so
386 : often, especially if they are slow. The value must be at least one
387 : page and must be a power of two. Setting to 0 causes initialization
388 : to either page size or win32 region size. (Note: In previous
389 : versions of malloc, the equivalent of this option was called
390 : "TOP_PAD")
391 :
392 : DEFAULT_TRIM_THRESHOLD default: 2MB
393 : Also settable using mallopt(M_TRIM_THRESHOLD, x)
394 : The maximum amount of unused top-most memory to keep before
395 : releasing via malloc_trim in free(). Automatic trimming is mainly
396 : useful in long-lived programs using contiguous MORECORE. Because
397 : trimming via sbrk can be slow on some systems, and can sometimes be
398 : wasteful (in cases where programs immediately afterward allocate
399 : more large chunks) the value should be high enough so that your
400 : overall system performance would improve by releasing this much
401 : memory. As a rough guide, you might set to a value close to the
402 : average size of a process (program) running on your system.
403 : Releasing this much memory would allow such a process to run in
404 : memory. Generally, it is worth tuning trim thresholds when a
405 : program undergoes phases where several large chunks are allocated
406 : and released in ways that can reuse each other's storage, perhaps
407 : mixed with phases where there are no such chunks at all. The trim
408 : value must be greater than page size to have any useful effect. To
409 : disable trimming completely, you can set to MAX_SIZE_T. Note that the trick
410 : some people use of mallocing a huge space and then freeing it at
411 : program startup, in an attempt to reserve system memory, doesn't
412 : have the intended effect under automatic trimming, since that memory
413 : will immediately be returned to the system.
414 :
415 : DEFAULT_MMAP_THRESHOLD default: 256K
416 : Also settable using mallopt(M_MMAP_THRESHOLD, x)
417 : The request size threshold for using MMAP to directly service a
418 : request. Requests of at least this size that cannot be allocated
419 : using already-existing space will be serviced via mmap. (If enough
420 : normal freed space already exists it is used instead.) Using mmap
421 : segregates relatively large chunks of memory so that they can be
422 : individually obtained and released from the host system. A request
423 : serviced through mmap is never reused by any other request (at least
424 : not directly; the system may just so happen to remap successive
425 : requests to the same locations). Segregating space in this way has
426 : the benefits that: Mmapped space can always be individually released
427 : back to the system, which helps keep the system level memory demands
428 : of a long-lived program low. Also, mapped memory doesn't become
429 : `locked' between other chunks, as can happen with normally allocated
430 : chunks, which means that even trimming via malloc_trim would not
431 : release them. However, it has the disadvantage that the space
432 : cannot be reclaimed, consolidated, and then used to service later
433 : requests, as happens with normal chunks. The advantages of mmap
434 : nearly always outweigh disadvantages for "large" chunks, but the
435 : value of "large" may vary across systems. The default is an
436 : empirically derived value that works well in most systems. You can
437 : disable mmap by setting to MAX_SIZE_T.
438 :
439 : */
440 :
441 : #ifndef WIN32
442 : #ifdef _WIN32
443 : #define WIN32 1
444 : #endif /* _WIN32 */
445 : #endif /* WIN32 */
446 : #ifdef WIN32
447 : #define WIN32_LEAN_AND_MEAN
448 : #include <windows.h>
449 : #define HAVE_MMAP 1
450 : #define HAVE_MORECORE 0
451 : #define LACKS_UNISTD_H
452 : #define LACKS_SYS_PARAM_H
453 : #define LACKS_SYS_MMAN_H
454 : #define LACKS_STRING_H
455 : #define LACKS_STRINGS_H
456 : #define LACKS_SYS_TYPES_H
457 : #define LACKS_ERRNO_H
458 : #define MALLOC_FAILURE_ACTION
459 : #define MMAP_CLEARS 0 /* WINCE and some others apparently don't clear */
460 : #endif /* WIN32 */
461 :
462 : #ifdef __OS2__
463 : #define INCL_DOS
464 : #include <os2.h>
465 : #define HAVE_MMAP 1
466 : #define HAVE_MORECORE 0
467 : #define LACKS_SYS_MMAN_H
468 : #endif /* __OS2__ */
469 :
470 : #if defined(DARWIN) || defined(_DARWIN)
471 : /* Mac OSX docs advise not to use sbrk; it seems better to use mmap */
472 : #ifndef HAVE_MORECORE
473 : #define HAVE_MORECORE 0
474 : #define HAVE_MMAP 1
475 : #endif /* HAVE_MORECORE */
476 : #endif /* DARWIN */
477 :
478 : #ifndef LACKS_SYS_TYPES_H
479 : #include <sys/types.h> /* For size_t */
480 : #endif /* LACKS_SYS_TYPES_H */
481 :
482 : /* The maximum possible size_t value has all bits set */
483 : #define MAX_SIZE_T (~(size_t)0)
484 :
485 : #ifndef ONLY_MSPACES
486 : #define ONLY_MSPACES 0
487 : #endif /* ONLY_MSPACES */
488 : #ifndef MSPACES
489 : #if ONLY_MSPACES
490 : #define MSPACES 1
491 : #else /* ONLY_MSPACES */
492 : #define MSPACES 0
493 : #endif /* ONLY_MSPACES */
494 : #endif /* MSPACES */
495 : #ifndef MALLOC_ALIGNMENT
496 : #define MALLOC_ALIGNMENT ((size_t)8U)
497 : #endif /* MALLOC_ALIGNMENT */
498 : #ifndef FOOTERS
499 : #define FOOTERS 0
500 : #endif /* FOOTERS */
501 : #ifndef ABORT
502 : #define ABORT abort()
503 : #endif /* ABORT */
504 : #ifndef ABORT_ON_ASSERT_FAILURE
505 : #define ABORT_ON_ASSERT_FAILURE 1
506 : #endif /* ABORT_ON_ASSERT_FAILURE */
507 : #ifndef PROCEED_ON_ERROR
508 : #define PROCEED_ON_ERROR 0
509 : #endif /* PROCEED_ON_ERROR */
510 : #ifndef USE_LOCKS
511 : #define USE_LOCKS 0
512 : #endif /* USE_LOCKS */
513 : #ifndef INSECURE
514 : #define INSECURE 0
515 : #endif /* INSECURE */
516 : #ifndef HAVE_MMAP
517 : #define HAVE_MMAP 1
518 : #endif /* HAVE_MMAP */
519 : #ifndef MMAP_CLEARS
520 : #define MMAP_CLEARS 1
521 : #endif /* MMAP_CLEARS */
522 : #ifndef HAVE_MREMAP
523 : #ifdef linux
524 : #define HAVE_MREMAP 1
525 : #else /* linux */
526 : #define HAVE_MREMAP 0
527 : #endif /* linux */
528 : #endif /* HAVE_MREMAP */
529 : #ifndef MALLOC_FAILURE_ACTION
530 : #define MALLOC_FAILURE_ACTION errno = ENOMEM;
531 : #endif /* MALLOC_FAILURE_ACTION */
532 : #ifndef HAVE_MORECORE
533 : #if ONLY_MSPACES
534 : #define HAVE_MORECORE 0
535 : #else /* ONLY_MSPACES */
536 : #define HAVE_MORECORE 1
537 : #endif /* ONLY_MSPACES */
538 : #endif /* HAVE_MORECORE */
539 : #if !HAVE_MORECORE
540 : #define MORECORE_CONTIGUOUS 0
541 : #else /* !HAVE_MORECORE */
542 : #ifndef MORECORE
543 : #define MORECORE sbrk
544 : #endif /* MORECORE */
545 : #ifndef MORECORE_CONTIGUOUS
546 : #define MORECORE_CONTIGUOUS 1
547 : #endif /* MORECORE_CONTIGUOUS */
548 : #endif /* HAVE_MORECORE */
549 : #ifndef DEFAULT_GRANULARITY
550 : #if MORECORE_CONTIGUOUS
551 : #define DEFAULT_GRANULARITY (0) /* 0 means to compute in init_mparams */
552 : #else /* MORECORE_CONTIGUOUS */
553 : #define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)
554 : #endif /* MORECORE_CONTIGUOUS */
555 : #endif /* DEFAULT_GRANULARITY */
556 : #ifndef DEFAULT_TRIM_THRESHOLD
557 : #ifndef MORECORE_CANNOT_TRIM
558 : #define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)
559 : #else /* MORECORE_CANNOT_TRIM */
560 : #define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T
561 : #endif /* MORECORE_CANNOT_TRIM */
562 : #endif /* DEFAULT_TRIM_THRESHOLD */
563 : #ifndef DEFAULT_MMAP_THRESHOLD
564 : #if HAVE_MMAP
565 : #define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)
566 : #else /* HAVE_MMAP */
567 : #define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T
568 : #endif /* HAVE_MMAP */
569 : #endif /* DEFAULT_MMAP_THRESHOLD */
570 : #ifndef USE_BUILTIN_FFS
571 : #define USE_BUILTIN_FFS 0
572 : #endif /* USE_BUILTIN_FFS */
573 : #ifndef USE_DEV_RANDOM
574 : #define USE_DEV_RANDOM 0
575 : #endif /* USE_DEV_RANDOM */
576 : #ifndef NO_MALLINFO
577 : #define NO_MALLINFO 0
578 : #endif /* NO_MALLINFO */
579 : #ifndef MALLINFO_FIELD_TYPE
580 : #define MALLINFO_FIELD_TYPE size_t
581 : #endif /* MALLINFO_FIELD_TYPE */
582 :
583 : /*
584 : mallopt tuning options. SVID/XPG defines four standard parameter
585 : numbers for mallopt, normally defined in malloc.h. None of these
586 : are used in this malloc, so setting them has no effect. But this
587 : malloc does support the following options.
588 : */
589 :
590 : #define M_TRIM_THRESHOLD (-1)
591 : #define M_GRANULARITY (-2)
592 : #define M_MMAP_THRESHOLD (-3)
593 :
594 : /* ------------------------ Mallinfo declarations ------------------------ */
595 :
596 : #if !NO_MALLINFO
597 : /*
598 : This version of malloc supports the standard SVID/XPG mallinfo
599 : routine that returns a struct containing usage properties and
600 : statistics. It should work on any system that has a
601 : /usr/include/malloc.h defining struct mallinfo. The main
602 : declaration needed is the mallinfo struct that is returned (by-copy)
603 : by mallinfo(). The malloinfo struct contains a bunch of fields that
604 : are not even meaningful in this version of malloc. These fields are
605 : are instead filled by mallinfo() with other numbers that might be of
606 : interest.
607 :
608 : HAVE_USR_INCLUDE_MALLOC_H should be set if you have a
609 : /usr/include/malloc.h file that includes a declaration of struct
610 : mallinfo. If so, it is included; else a compliant version is
611 : declared below. These must be precisely the same for mallinfo() to
612 : work. The original SVID version of this struct, defined on most
613 : systems with mallinfo, declares all fields as ints. But some others
614 : define as unsigned long. If your system defines the fields using a
615 : type of different width than listed here, you MUST #include your
616 : system version and #define HAVE_USR_INCLUDE_MALLOC_H.
617 : */
618 :
619 : /* #define HAVE_USR_INCLUDE_MALLOC_H */
620 :
621 : #ifdef HAVE_USR_INCLUDE_MALLOC_H
622 : #include "/usr/include/malloc.h"
623 : #else /* HAVE_USR_INCLUDE_MALLOC_H */
624 :
625 : /* HP-UX's stdlib.h redefines mallinfo unless _STRUCT_MALLINFO is defined */
626 : #define _STRUCT_MALLINFO
627 :
628 : struct mallinfo {
629 : MALLINFO_FIELD_TYPE arena; /* non-mmapped space allocated from system */
630 : MALLINFO_FIELD_TYPE ordblks; /* number of free chunks */
631 : MALLINFO_FIELD_TYPE smblks; /* always 0 */
632 : MALLINFO_FIELD_TYPE hblks; /* always 0 */
633 : MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */
634 : MALLINFO_FIELD_TYPE usmblks; /* maximum total allocated space */
635 : MALLINFO_FIELD_TYPE fsmblks; /* always 0 */
636 : MALLINFO_FIELD_TYPE uordblks; /* total allocated space */
637 : MALLINFO_FIELD_TYPE fordblks; /* total free space */
638 : MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */
639 : };
640 :
641 : #endif /* HAVE_USR_INCLUDE_MALLOC_H */
642 : #endif /* NO_MALLINFO */
643 :
644 : #ifdef __cplusplus
645 : extern "C" {
646 : #endif /* __cplusplus */
647 :
648 : #if !ONLY_MSPACES
649 :
650 : /* ------------------- Declarations of public routines ------------------- */
651 :
652 : #ifndef USE_DL_PREFIX
653 : #define dlcalloc calloc
654 : #define dlfree free
655 : #define dlmalloc malloc
656 : #define dlmemalign memalign
657 : #define dlrealloc realloc
658 : #define dlvalloc valloc
659 : #define dlpvalloc pvalloc
660 : #define dlmallinfo mallinfo
661 : #define dlmallopt mallopt
662 : #define dlmalloc_trim malloc_trim
663 : #define dlmalloc_stats malloc_stats
664 : #define dlmalloc_usable_size malloc_usable_size
665 : #define dlmalloc_footprint malloc_footprint
666 : #define dlmalloc_max_footprint malloc_max_footprint
667 : #define dlindependent_calloc independent_calloc
668 : #define dlindependent_comalloc independent_comalloc
669 : #endif /* USE_DL_PREFIX */
670 :
671 :
672 : /*
673 : malloc(size_t n)
674 : Returns a pointer to a newly allocated chunk of at least n bytes, or
675 : null if no space is available, in which case errno is set to ENOMEM
676 : on ANSI C systems.
677 :
678 : If n is zero, malloc returns a minimum-sized chunk. (The minimum
679 : size is 16 bytes on most 32bit systems, and 32 bytes on 64bit
680 : systems.) Note that size_t is an unsigned type, so calls with
681 : arguments that would be negative if signed are interpreted as
682 : requests for huge amounts of space, which will often fail. The
683 : maximum supported value of n differs across systems, but is in all
684 : cases less than the maximum representable value of a size_t.
685 : */
686 : void* dlmalloc(size_t);
687 :
688 : /*
689 : free(void* p)
690 : Releases the chunk of memory pointed to by p, that had been previously
691 : allocated using malloc or a related routine such as realloc.
692 : It has no effect if p is null. If p was not malloced or already
693 : freed, free(p) will by default cause the current program to abort.
694 : */
695 : void dlfree(void*);
696 :
697 : /*
698 : calloc(size_t n_elements, size_t element_size);
699 : Returns a pointer to n_elements * element_size bytes, with all locations
700 : set to zero.
701 : */
702 : void* dlcalloc(size_t, size_t);
703 :
704 : /*
705 : realloc(void* p, size_t n)
706 : Returns a pointer to a chunk of size n that contains the same data
707 : as does chunk p up to the minimum of (n, p's size) bytes, or null
708 : if no space is available.
709 :
710 : The returned pointer may or may not be the same as p. The algorithm
711 : prefers extending p in most cases when possible, otherwise it
712 : employs the equivalent of a malloc-copy-free sequence.
713 :
714 : If p is null, realloc is equivalent to malloc.
715 :
716 : If space is not available, realloc returns null, errno is set (if on
717 : ANSI) and p is NOT freed.
718 :
719 : if n is for fewer bytes than already held by p, the newly unused
720 : space is lopped off and freed if possible. realloc with a size
721 : argument of zero (re)allocates a minimum-sized chunk.
722 :
723 : The old unix realloc convention of allowing the last-free'd chunk
724 : to be used as an argument to realloc is not supported.
725 : */
726 :
727 : void* dlrealloc(void*, size_t);
728 :
729 : /*
730 : memalign(size_t alignment, size_t n);
731 : Returns a pointer to a newly allocated chunk of n bytes, aligned
732 : in accord with the alignment argument.
733 :
734 : The alignment argument should be a power of two. If the argument is
735 : not a power of two, the nearest greater power is used.
736 : 8-byte alignment is guaranteed by normal malloc calls, so don't
737 : bother calling memalign with an argument of 8 or less.
738 :
739 : Overreliance on memalign is a sure way to fragment space.
740 : */
741 : void* dlmemalign(size_t, size_t);
742 :
743 : /*
744 : valloc(size_t n);
745 : Equivalent to memalign(pagesize, n), where pagesize is the page
746 : size of the system. If the pagesize is unknown, 4096 is used.
747 : */
748 : void* dlvalloc(size_t);
749 :
750 : /*
751 : mallopt(int parameter_number, int parameter_value)
752 : Sets tunable parameters The format is to provide a
753 : (parameter-number, parameter-value) pair. mallopt then sets the
754 : corresponding parameter to the argument value if it can (i.e., so
755 : long as the value is meaningful), and returns 1 if successful else
756 : 0. SVID/XPG/ANSI defines four standard param numbers for mallopt,
757 : normally defined in malloc.h. None of these are use in this malloc,
758 : so setting them has no effect. But this malloc also supports other
759 : options in mallopt. See below for details. Briefly, supported
760 : parameters are as follows (listed defaults are for "typical"
761 : configurations).
762 :
763 : Symbol param # default allowed param values
764 : M_TRIM_THRESHOLD -1 2*1024*1024 any (MAX_SIZE_T disables)
765 : M_GRANULARITY -2 page size any power of 2 >= page size
766 : M_MMAP_THRESHOLD -3 256*1024 any (or 0 if no MMAP support)
767 : */
768 : int dlmallopt(int, int);
769 :
770 : /*
771 : malloc_footprint();
772 : Returns the number of bytes obtained from the system. The total
773 : number of bytes allocated by malloc, realloc etc., is less than this
774 : value. Unlike mallinfo, this function returns only a precomputed
775 : result, so can be called frequently to monitor memory consumption.
776 : Even if locks are otherwise defined, this function does not use them,
777 : so results might not be up to date.
778 : */
779 : size_t dlmalloc_footprint(void);
780 :
781 : /*
782 : malloc_max_footprint();
783 : Returns the maximum number of bytes obtained from the system. This
784 : value will be greater than current footprint if deallocated space
785 : has been reclaimed by the system. The peak number of bytes allocated
786 : by malloc, realloc etc., is less than this value. Unlike mallinfo,
787 : this function returns only a precomputed result, so can be called
788 : frequently to monitor memory consumption. Even if locks are
789 : otherwise defined, this function does not use them, so results might
790 : not be up to date.
791 : */
792 : size_t dlmalloc_max_footprint(void);
793 :
794 : #if !NO_MALLINFO
795 : /*
796 : mallinfo()
797 : Returns (by copy) a struct containing various summary statistics:
798 :
799 : arena: current total non-mmapped bytes allocated from system
800 : ordblks: the number of free chunks
801 : smblks: always zero.
802 : hblks: current number of mmapped regions
803 : hblkhd: total bytes held in mmapped regions
804 : usmblks: the maximum total allocated space. This will be greater
805 : than current total if trimming has occurred.
806 : fsmblks: always zero
807 : uordblks: current total allocated space (normal or mmapped)
808 : fordblks: total free space
809 : keepcost: the maximum number of bytes that could ideally be released
810 : back to system via malloc_trim. ("ideally" means that
811 : it ignores page restrictions etc.)
812 :
813 : Because these fields are ints, but internal bookkeeping may
814 : be kept as longs, the reported values may wrap around zero and
815 : thus be inaccurate.
816 : */
817 : struct mallinfo dlmallinfo(void);
818 : #endif /* NO_MALLINFO */
819 :
820 : /*
821 : independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);
822 :
823 : independent_calloc is similar to calloc, but instead of returning a
824 : single cleared space, it returns an array of pointers to n_elements
825 : independent elements that can hold contents of size elem_size, each
826 : of which starts out cleared, and can be independently freed,
827 : realloc'ed etc. The elements are guaranteed to be adjacently
828 : allocated (this is not guaranteed to occur with multiple callocs or
829 : mallocs), which may also improve cache locality in some
830 : applications.
831 :
832 : The "chunks" argument is optional (i.e., may be null, which is
833 : probably the most typical usage). If it is null, the returned array
834 : is itself dynamically allocated and should also be freed when it is
835 : no longer needed. Otherwise, the chunks array must be of at least
836 : n_elements in length. It is filled in with the pointers to the
837 : chunks.
838 :
839 : In either case, independent_calloc returns this pointer array, or
840 : null if the allocation failed. If n_elements is zero and "chunks"
841 : is null, it returns a chunk representing an array with zero elements
842 : (which should be freed if not wanted).
843 :
844 : Each element must be individually freed when it is no longer
845 : needed. If you'd like to instead be able to free all at once, you
846 : should instead use regular calloc and assign pointers into this
847 : space to represent elements. (In this case though, you cannot
848 : independently free elements.)
849 :
850 : independent_calloc simplifies and speeds up implementations of many
851 : kinds of pools. It may also be useful when constructing large data
852 : structures that initially have a fixed number of fixed-sized nodes,
853 : but the number is not known at compile time, and some of the nodes
854 : may later need to be freed. For example:
855 :
856 : struct Node { int item; struct Node* next; };
857 :
858 : struct Node* build_list() {
859 : struct Node** pool;
860 : int n = read_number_of_nodes_needed();
861 : if (n <= 0) return 0;
862 : pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);
863 : if (pool == 0) die();
864 : // organize into a linked list...
865 : struct Node* first = pool[0];
866 : for (i = 0; i < n-1; ++i)
867 : pool[i]->next = pool[i+1];
868 : free(pool); // Can now free the array (or not, if it is needed later)
869 : return first;
870 : }
871 : */
872 : void** dlindependent_calloc(size_t, size_t, void**);
873 :
874 : /*
875 : independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);
876 :
877 : independent_comalloc allocates, all at once, a set of n_elements
878 : chunks with sizes indicated in the "sizes" array. It returns
879 : an array of pointers to these elements, each of which can be
880 : independently freed, realloc'ed etc. The elements are guaranteed to
881 : be adjacently allocated (this is not guaranteed to occur with
882 : multiple callocs or mallocs), which may also improve cache locality
883 : in some applications.
884 :
885 : The "chunks" argument is optional (i.e., may be null). If it is null
886 : the returned array is itself dynamically allocated and should also
887 : be freed when it is no longer needed. Otherwise, the chunks array
888 : must be of at least n_elements in length. It is filled in with the
889 : pointers to the chunks.
890 :
891 : In either case, independent_comalloc returns this pointer array, or
892 : null if the allocation failed. If n_elements is zero and chunks is
893 : null, it returns a chunk representing an array with zero elements
894 : (which should be freed if not wanted).
895 :
896 : Each element must be individually freed when it is no longer
897 : needed. If you'd like to instead be able to free all at once, you
898 : should instead use a single regular malloc, and assign pointers at
899 : particular offsets in the aggregate space. (In this case though, you
900 : cannot independently free elements.)
901 :
902 : independent_comallac differs from independent_calloc in that each
903 : element may have a different size, and also that it does not
904 : automatically clear elements.
905 :
906 : independent_comalloc can be used to speed up allocation in cases
907 : where several structs or objects must always be allocated at the
908 : same time. For example:
909 :
910 : struct Head { ... }
911 : struct Foot { ... }
912 :
913 : void send_message(char* msg) {
914 : int msglen = strlen(msg);
915 : size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };
916 : void* chunks[3];
917 : if (independent_comalloc(3, sizes, chunks) == 0)
918 : die();
919 : struct Head* head = (struct Head*)(chunks[0]);
920 : char* body = (char*)(chunks[1]);
921 : struct Foot* foot = (struct Foot*)(chunks[2]);
922 : // ...
923 : }
924 :
925 : In general though, independent_comalloc is worth using only for
926 : larger values of n_elements. For small values, you probably won't
927 : detect enough difference from series of malloc calls to bother.
928 :
929 : Overuse of independent_comalloc can increase overall memory usage,
930 : since it cannot reuse existing noncontiguous small chunks that
931 : might be available for some of the elements.
932 : */
933 : void** dlindependent_comalloc(size_t, size_t*, void**);
934 :
935 :
936 : /*
937 : pvalloc(size_t n);
938 : Equivalent to valloc(minimum-page-that-holds(n)), that is,
939 : round up n to nearest pagesize.
940 : */
941 : void* dlpvalloc(size_t);
942 :
943 : /*
944 : malloc_trim(size_t pad);
945 :
946 : If possible, gives memory back to the system (via negative arguments
947 : to sbrk) if there is unused memory at the `high' end of the malloc
948 : pool or in unused MMAP segments. You can call this after freeing
949 : large blocks of memory to potentially reduce the system-level memory
950 : requirements of a program. However, it cannot guarantee to reduce
951 : memory. Under some allocation patterns, some large free blocks of
952 : memory will be locked between two used chunks, so they cannot be
953 : given back to the system.
954 :
955 : The `pad' argument to malloc_trim represents the amount of free
956 : trailing space to leave untrimmed. If this argument is zero, only
957 : the minimum amount of memory to maintain internal data structures
958 : will be left. Non-zero arguments can be supplied to maintain enough
959 : trailing space to service future expected allocations without having
960 : to re-obtain memory from the system.
961 :
962 : Malloc_trim returns 1 if it actually released any memory, else 0.
963 : */
964 : int dlmalloc_trim(size_t);
965 :
966 : /*
967 : malloc_usable_size(void* p);
968 :
969 : Returns the number of bytes you can actually use in
970 : an allocated chunk, which may be more than you requested (although
971 : often not) due to alignment and minimum size constraints.
972 : You can use this many bytes without worrying about
973 : overwriting other allocated objects. This is not a particularly great
974 : programming practice. malloc_usable_size can be more useful in
975 : debugging and assertions, for example:
976 :
977 : p = malloc(n);
978 : assert(malloc_usable_size(p) >= 256);
979 : */
980 : size_t dlmalloc_usable_size(void*);
981 :
982 : /*
983 : malloc_stats();
984 : Prints on stderr the amount of space obtained from the system (both
985 : via sbrk and mmap), the maximum amount (which may be more than
986 : current if malloc_trim and/or munmap got called), and the current
987 : number of bytes allocated via malloc (or realloc, etc) but not yet
988 : freed. Note that this is the number of bytes allocated, not the
989 : number requested. It will be larger than the number requested
990 : because of alignment and bookkeeping overhead. Because it includes
991 : alignment wastage as being in use, this figure may be greater than
992 : zero even when no user-level chunks are allocated.
993 :
994 : The reported current and maximum system memory can be inaccurate if
995 : a program makes other calls to system memory allocation functions
996 : (normally sbrk) outside of malloc.
997 :
998 : malloc_stats prints only the most commonly interesting statistics.
999 : More information can be obtained by calling mallinfo.
1000 : */
1001 : void dlmalloc_stats(void);
1002 :
1003 : #endif /* ONLY_MSPACES */
1004 :
1005 : #if MSPACES
1006 :
1007 : /*
1008 : mspace is an opaque type representing an independent
1009 : region of space that supports mspace_malloc, etc.
1010 : */
1011 : typedef void* mspace;
1012 :
1013 : /*
1014 : create_mspace creates and returns a new independent space with the
1015 : given initial capacity, or, if 0, the default granularity size. It
1016 : returns null if there is no system memory available to create the
1017 : space. If argument locked is non-zero, the space uses a separate
1018 : lock to control access. The capacity of the space will grow
1019 : dynamically as needed to service mspace_malloc requests. You can
1020 : control the sizes of incremental increases of this space by
1021 : compiling with a different DEFAULT_GRANULARITY or dynamically
1022 : setting with mallopt(M_GRANULARITY, value).
1023 : */
1024 : mspace create_mspace(size_t capacity, int locked);
1025 :
1026 : /*
1027 : destroy_mspace destroys the given space, and attempts to return all
1028 : of its memory back to the system, returning the total number of
1029 : bytes freed. After destruction, the results of access to all memory
1030 : used by the space become undefined.
1031 : */
1032 : size_t destroy_mspace(mspace msp);
1033 :
1034 : /*
1035 : create_mspace_with_base uses the memory supplied as the initial base
1036 : of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this
1037 : space is used for bookkeeping, so the capacity must be at least this
1038 : large. (Otherwise 0 is returned.) When this initial space is
1039 : exhausted, additional memory will be obtained from the system.
1040 : Destroying this space will deallocate all additionally allocated
1041 : space (if possible) but not the initial base.
1042 : */
1043 : mspace create_mspace_with_base(void* base, size_t capacity, int locked);
1044 :
1045 : /*
1046 : mspace_malloc behaves as malloc, but operates within
1047 : the given space.
1048 : */
1049 : void* mspace_malloc(mspace msp, size_t bytes);
1050 :
1051 : /*
1052 : mspace_free behaves as free, but operates within
1053 : the given space.
1054 :
1055 : If compiled with FOOTERS==1, mspace_free is not actually needed.
1056 : free may be called instead of mspace_free because freed chunks from
1057 : any space are handled by their originating spaces.
1058 : */
1059 : void mspace_free(mspace msp, void* mem);
1060 :
1061 : /*
1062 : mspace_realloc behaves as realloc, but operates within
1063 : the given space.
1064 :
1065 : If compiled with FOOTERS==1, mspace_realloc is not actually
1066 : needed. realloc may be called instead of mspace_realloc because
1067 : realloced chunks from any space are handled by their originating
1068 : spaces.
1069 : */
1070 : void* mspace_realloc(mspace msp, void* mem, size_t newsize);
1071 :
1072 : /*
1073 : mspace_calloc behaves as calloc, but operates within
1074 : the given space.
1075 : */
1076 : void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);
1077 :
1078 : /*
1079 : mspace_memalign behaves as memalign, but operates within
1080 : the given space.
1081 : */
1082 : void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);
1083 :
1084 : /*
1085 : mspace_independent_calloc behaves as independent_calloc, but
1086 : operates within the given space.
1087 : */
1088 : void** mspace_independent_calloc(mspace msp, size_t n_elements,
1089 : size_t elem_size, void* chunks[]);
1090 :
1091 : /*
1092 : mspace_independent_comalloc behaves as independent_comalloc, but
1093 : operates within the given space.
1094 : */
1095 : void** mspace_independent_comalloc(mspace msp, size_t n_elements,
1096 : size_t sizes[], void* chunks[]);
1097 :
1098 : /*
1099 : mspace_footprint() returns the number of bytes obtained from the
1100 : system for this space.
1101 : */
1102 : size_t mspace_footprint(mspace msp);
1103 :
1104 : /*
1105 : mspace_max_footprint() returns the peak number of bytes obtained from the
1106 : system for this space.
1107 : */
1108 : size_t mspace_max_footprint(mspace msp);
1109 :
1110 :
1111 : #if !NO_MALLINFO
1112 : /*
1113 : mspace_mallinfo behaves as mallinfo, but reports properties of
1114 : the given space.
1115 : */
1116 : struct mallinfo mspace_mallinfo(mspace msp);
1117 : #endif /* NO_MALLINFO */
1118 :
1119 : /*
1120 : mspace_malloc_stats behaves as malloc_stats, but reports
1121 : properties of the given space.
1122 : */
1123 : void mspace_malloc_stats(mspace msp);
1124 :
1125 : /*
1126 : mspace_trim behaves as malloc_trim, but
1127 : operates within the given space.
1128 : */
1129 : int mspace_trim(mspace msp, size_t pad);
1130 :
1131 : /*
1132 : An alias for mallopt.
1133 : */
1134 : int mspace_mallopt(int, int);
1135 :
1136 : #endif /* MSPACES */
1137 :
1138 : #ifdef __cplusplus
1139 : }; /* end of extern "C" */
1140 : #endif /* __cplusplus */
1141 :
1142 : /*
1143 : ========================================================================
1144 : To make a fully customizable malloc.h header file, cut everything
1145 : above this line, put into file malloc.h, edit to suit, and #include it
1146 : on the next line, as well as in programs that use this malloc.
1147 : ========================================================================
1148 : */
1149 :
1150 : /* #include "malloc.h" */
1151 :
1152 : /*------------------------------ internal #includes ---------------------- */
1153 :
1154 : #ifdef _MSC_VER
1155 : #pragma warning( disable : 4146 ) /* no "unsigned" warnings */
1156 : #endif /* _MSC_VER */
1157 :
1158 : #include <stdio.h> /* for printing in malloc_stats */
1159 :
1160 : #ifndef LACKS_ERRNO_H
1161 : #include <errno.h> /* for MALLOC_FAILURE_ACTION */
1162 : #endif /* LACKS_ERRNO_H */
1163 : #if FOOTERS
1164 : #include <time.h> /* for magic initialization */
1165 : #endif /* FOOTERS */
1166 : #ifndef LACKS_STDLIB_H
1167 : #include <stdlib.h> /* for abort() */
1168 : #endif /* LACKS_STDLIB_H */
1169 : #ifdef DEBUG
1170 : #if ABORT_ON_ASSERT_FAILURE
1171 : #define assert(x) if(!(x)) ABORT
1172 : #else /* ABORT_ON_ASSERT_FAILURE */
1173 : #include <assert.h>
1174 : #endif /* ABORT_ON_ASSERT_FAILURE */
1175 : #else /* DEBUG */
1176 : #define assert(x)
1177 : #endif /* DEBUG */
1178 : #ifndef LACKS_STRING_H
1179 : #include <string.h> /* for memset etc */
1180 : #endif /* LACKS_STRING_H */
1181 : #if USE_BUILTIN_FFS
1182 : #ifndef LACKS_STRINGS_H
1183 : #include <strings.h> /* for ffs */
1184 : #endif /* LACKS_STRINGS_H */
1185 : #endif /* USE_BUILTIN_FFS */
1186 : #if HAVE_MMAP
1187 : #ifndef LACKS_SYS_MMAN_H
1188 : #include <sys/mman.h> /* for mmap */
1189 : #endif /* LACKS_SYS_MMAN_H */
1190 : #ifndef LACKS_FCNTL_H
1191 : #include <fcntl.h>
1192 : #endif /* LACKS_FCNTL_H */
1193 : #endif /* HAVE_MMAP */
1194 : #if HAVE_MORECORE
1195 : #ifndef LACKS_UNISTD_H
1196 : #include <unistd.h> /* for sbrk */
1197 : #else /* LACKS_UNISTD_H */
1198 : #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
1199 : extern void* sbrk(ptrdiff_t);
1200 : #endif /* FreeBSD etc */
1201 : #endif /* LACKS_UNISTD_H */
1202 : #endif /* HAVE_MMAP */
1203 :
1204 : #ifndef WIN32
1205 : #ifndef malloc_getpagesize
1206 : # ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */
1207 : # ifndef _SC_PAGE_SIZE
1208 : # define _SC_PAGE_SIZE _SC_PAGESIZE
1209 : # endif
1210 : # endif
1211 : # ifdef _SC_PAGE_SIZE
1212 : # define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
1213 : # else
1214 : # if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
1215 : extern size_t getpagesize();
1216 : # define malloc_getpagesize getpagesize()
1217 : # else
1218 : # ifdef WIN32 /* use supplied emulation of getpagesize */
1219 : # define malloc_getpagesize getpagesize()
1220 : # else
1221 : # ifndef LACKS_SYS_PARAM_H
1222 : # include <sys/param.h>
1223 : # endif
1224 : # ifdef EXEC_PAGESIZE
1225 : # define malloc_getpagesize EXEC_PAGESIZE
1226 : # else
1227 : # ifdef NBPG
1228 : # ifndef CLSIZE
1229 : # define malloc_getpagesize NBPG
1230 : # else
1231 : # define malloc_getpagesize (NBPG * CLSIZE)
1232 : # endif
1233 : # else
1234 : # ifdef NBPC
1235 : # define malloc_getpagesize NBPC
1236 : # else
1237 : # ifdef PAGESIZE
1238 : # define malloc_getpagesize PAGESIZE
1239 : # else /* just guess */
1240 : # define malloc_getpagesize ((size_t)4096U)
1241 : # endif
1242 : # endif
1243 : # endif
1244 : # endif
1245 : # endif
1246 : # endif
1247 : # endif
1248 : #endif
1249 : #endif
1250 :
1251 : /* ------------------- size_t and alignment properties -------------------- */
1252 :
1253 : /* The byte and bit size of a size_t */
1254 : #define SIZE_T_SIZE (sizeof(size_t))
1255 : #define SIZE_T_BITSIZE (sizeof(size_t) << 3)
1256 :
1257 : /* Some constants coerced to size_t */
1258 : /* Annoying but necessary to avoid errors on some platforms */
1259 : #define SIZE_T_ZERO ((size_t)0)
1260 : #define SIZE_T_ONE ((size_t)1)
1261 : #define SIZE_T_TWO ((size_t)2)
1262 : #define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)
1263 : #define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)
1264 : #define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)
1265 : #define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)
1266 :
1267 : /* The bit mask value corresponding to MALLOC_ALIGNMENT */
1268 : #define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)
1269 :
1270 : /* True if address a has acceptable alignment */
1271 : #define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)
1272 :
1273 : /* the number of bytes to offset an address to align it */
1274 : #define align_offset(A)\
1275 : ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\
1276 : ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))
1277 :
1278 : /* -------------------------- MMAP preliminaries ------------------------- */
1279 :
1280 : /*
1281 : If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and
1282 : checks to fail so compiler optimizer can delete code rather than
1283 : using so many "#if"s.
1284 : */
1285 :
1286 :
1287 : /* MORECORE and MMAP must return MFAIL on failure */
1288 : #define MFAIL ((void*)(MAX_SIZE_T))
1289 : #define CMFAIL ((char*)(MFAIL)) /* defined for convenience */
1290 :
1291 : #if !HAVE_MMAP
1292 : #define IS_MMAPPED_BIT (SIZE_T_ZERO)
1293 : #define USE_MMAP_BIT (SIZE_T_ZERO)
1294 : #define CALL_MMAP(s) MFAIL
1295 : #define CALL_MUNMAP(a, s) (-1)
1296 : #define DIRECT_MMAP(s) MFAIL
1297 :
1298 : #else /* HAVE_MMAP */
1299 : #define IS_MMAPPED_BIT (SIZE_T_ONE)
1300 : #define USE_MMAP_BIT (SIZE_T_ONE)
1301 :
1302 : #if !defined(WIN32) && !defined (__OS2__)
1303 : #define CALL_MUNMAP(a, s) munmap((a), (s))
1304 : #define MMAP_PROT (PROT_READ|PROT_WRITE)
1305 : #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1306 : #define MAP_ANONYMOUS MAP_ANON
1307 : #endif /* MAP_ANON */
1308 : #ifdef MAP_ANONYMOUS
1309 : #define MMAP_FLAGS (MAP_PRIVATE|MAP_ANONYMOUS)
1310 : #define CALL_MMAP(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)
1311 : #else /* MAP_ANONYMOUS */
1312 : /*
1313 : Nearly all versions of mmap support MAP_ANONYMOUS, so the following
1314 : is unlikely to be needed, but is supplied just in case.
1315 : */
1316 : #define MMAP_FLAGS (MAP_PRIVATE)
1317 : static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */
1318 : #define CALL_MMAP(s) ((dev_zero_fd < 0) ? \
1319 : (dev_zero_fd = open("/dev/zero", O_RDWR), \
1320 : mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \
1321 : mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))
1322 : #endif /* MAP_ANONYMOUS */
1323 :
1324 : #define DIRECT_MMAP(s) CALL_MMAP(s)
1325 :
1326 : #elif defined(__OS2__)
1327 :
1328 : /* OS/2 MMAP via DosAllocMem */
1329 : static void* os2mmap(size_t size) {
1330 : void* ptr;
1331 : if (DosAllocMem(&ptr, size, OBJ_ANY|PAG_COMMIT|PAG_READ|PAG_WRITE) &&
1332 : DosAllocMem(&ptr, size, PAG_COMMIT|PAG_READ|PAG_WRITE))
1333 : return MFAIL;
1334 : return ptr;
1335 : }
1336 :
1337 : #define os2direct_mmap(n) os2mmap(n)
1338 :
1339 : /* This function supports releasing coalesed segments */
1340 : static int os2munmap(void* ptr, size_t size) {
1341 : while (size) {
1342 : ULONG ulSize = size;
1343 : ULONG ulFlags = 0;
1344 : if (DosQueryMem(ptr, &ulSize, &ulFlags) != 0)
1345 : return -1;
1346 : if ((ulFlags & PAG_BASE) == 0 ||(ulFlags & PAG_COMMIT) == 0 ||
1347 : ulSize > size)
1348 : return -1;
1349 : if (DosFreeMem(ptr) != 0)
1350 : return -1;
1351 : ptr = ( void * ) ( ( char * ) ptr + ulSize );
1352 : size -= ulSize;
1353 : }
1354 : return 0;
1355 : }
1356 :
1357 : #define CALL_MMAP(s) os2mmap(s)
1358 : #define CALL_MUNMAP(a, s) os2munmap((a), (s))
1359 : #define DIRECT_MMAP(s) os2direct_mmap(s)
1360 :
1361 : #else /* WIN32 */
1362 :
1363 : /* Win32 MMAP via VirtualAlloc */
1364 : static void* win32mmap(size_t size) {
1365 : void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_EXECUTE_READWRITE);
1366 : return (ptr != 0)? ptr: MFAIL;
1367 : }
1368 :
1369 : /* For direct MMAP, use MEM_TOP_DOWN to minimize interference */
1370 : static void* win32direct_mmap(size_t size) {
1371 : void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,
1372 : PAGE_EXECUTE_READWRITE);
1373 : return (ptr != 0)? ptr: MFAIL;
1374 : }
1375 :
1376 : /* This function supports releasing coalesed segments */
1377 : static int win32munmap(void* ptr, size_t size) {
1378 : MEMORY_BASIC_INFORMATION minfo;
1379 : char* cptr = ptr;
1380 : while (size) {
1381 : if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)
1382 : return -1;
1383 : if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||
1384 : minfo.State != MEM_COMMIT || minfo.RegionSize > size)
1385 : return -1;
1386 : if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)
1387 : return -1;
1388 : cptr += minfo.RegionSize;
1389 : size -= minfo.RegionSize;
1390 : }
1391 : return 0;
1392 : }
1393 :
1394 : #define CALL_MMAP(s) win32mmap(s)
1395 : #define CALL_MUNMAP(a, s) win32munmap((a), (s))
1396 : #define DIRECT_MMAP(s) win32direct_mmap(s)
1397 : #endif /* WIN32 */
1398 : #endif /* HAVE_MMAP */
1399 :
1400 : #if HAVE_MMAP && HAVE_MREMAP
1401 : #define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))
1402 : #else /* HAVE_MMAP && HAVE_MREMAP */
1403 : #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL
1404 : #endif /* HAVE_MMAP && HAVE_MREMAP */
1405 :
1406 : #if HAVE_MORECORE
1407 : #define CALL_MORECORE(S) MORECORE(S)
1408 : #else /* HAVE_MORECORE */
1409 : #define CALL_MORECORE(S) MFAIL
1410 : #endif /* HAVE_MORECORE */
1411 :
1412 : /* mstate bit set if contiguous morecore disabled or failed */
1413 : #define USE_NONCONTIGUOUS_BIT (4U)
1414 :
1415 : /* segment bit set in create_mspace_with_base */
1416 : #define EXTERN_BIT (8U)
1417 :
1418 :
1419 : /* --------------------------- Lock preliminaries ------------------------ */
1420 :
1421 : #if USE_LOCKS
1422 :
1423 : /*
1424 : When locks are defined, there are up to two global locks:
1425 :
1426 : * If HAVE_MORECORE, morecore_mutex protects sequences of calls to
1427 : MORECORE. In many cases sys_alloc requires two calls, that should
1428 : not be interleaved with calls by other threads. This does not
1429 : protect against direct calls to MORECORE by other threads not
1430 : using this lock, so there is still code to cope the best we can on
1431 : interference.
1432 :
1433 : * magic_init_mutex ensures that mparams.magic and other
1434 : unique mparams values are initialized only once.
1435 : */
1436 :
1437 : #if !defined(WIN32) && !defined(__OS2__)
1438 : /* By default use posix locks */
1439 : #include <pthread.h>
1440 : #define MLOCK_T pthread_mutex_t
1441 : #define INITIAL_LOCK(l) pthread_mutex_init(l, NULL)
1442 : #define ACQUIRE_LOCK(l) pthread_mutex_lock(l)
1443 : #define RELEASE_LOCK(l) pthread_mutex_unlock(l)
1444 :
1445 : #if HAVE_MORECORE
1446 : static MLOCK_T morecore_mutex = PTHREAD_MUTEX_INITIALIZER;
1447 : #endif /* HAVE_MORECORE */
1448 :
1449 : static MLOCK_T magic_init_mutex = PTHREAD_MUTEX_INITIALIZER;
1450 :
1451 : #elif defined(__OS2__)
1452 : #define MLOCK_T HMTX
1453 : #define INITIAL_LOCK(l) DosCreateMutexSem(0, l, 0, FALSE)
1454 : #define ACQUIRE_LOCK(l) DosRequestMutexSem(*l, SEM_INDEFINITE_WAIT)
1455 : #define RELEASE_LOCK(l) DosReleaseMutexSem(*l)
1456 : #if HAVE_MORECORE
1457 : static MLOCK_T morecore_mutex;
1458 : #endif /* HAVE_MORECORE */
1459 : static MLOCK_T magic_init_mutex;
1460 :
1461 : #else /* WIN32 */
1462 : /*
1463 : Because lock-protected regions have bounded times, and there
1464 : are no recursive lock calls, we can use simple spinlocks.
1465 : */
1466 :
1467 : #define MLOCK_T long
1468 : static int win32_acquire_lock (MLOCK_T *sl) {
1469 : for (;;) {
1470 : #ifdef InterlockedCompareExchangePointer
1471 : if (!InterlockedCompareExchange(sl, 1, 0))
1472 : return 0;
1473 : #else /* Use older void* version */
1474 : if (!InterlockedCompareExchange((void**)sl, (void*)1, (void*)0))
1475 : return 0;
1476 : #endif /* InterlockedCompareExchangePointer */
1477 : Sleep (0);
1478 : }
1479 : }
1480 :
1481 : static void win32_release_lock (MLOCK_T *sl) {
1482 : InterlockedExchange (sl, 0);
1483 : }
1484 :
1485 : #define INITIAL_LOCK(l) *(l)=0
1486 : #define ACQUIRE_LOCK(l) win32_acquire_lock(l)
1487 : #define RELEASE_LOCK(l) win32_release_lock(l)
1488 : #if HAVE_MORECORE
1489 : static MLOCK_T morecore_mutex;
1490 : #endif /* HAVE_MORECORE */
1491 : static MLOCK_T magic_init_mutex;
1492 : #endif /* WIN32 */
1493 :
1494 : #define USE_LOCK_BIT (2U)
1495 : #else /* USE_LOCKS */
1496 : #define USE_LOCK_BIT (0U)
1497 : #define INITIAL_LOCK(l)
1498 : #endif /* USE_LOCKS */
1499 :
1500 : #if USE_LOCKS && HAVE_MORECORE
1501 : #define ACQUIRE_MORECORE_LOCK() ACQUIRE_LOCK(&morecore_mutex);
1502 : #define RELEASE_MORECORE_LOCK() RELEASE_LOCK(&morecore_mutex);
1503 : #else /* USE_LOCKS && HAVE_MORECORE */
1504 : #define ACQUIRE_MORECORE_LOCK()
1505 : #define RELEASE_MORECORE_LOCK()
1506 : #endif /* USE_LOCKS && HAVE_MORECORE */
1507 :
1508 : #if USE_LOCKS
1509 : #define ACQUIRE_MAGIC_INIT_LOCK() ACQUIRE_LOCK(&magic_init_mutex);
1510 : #define RELEASE_MAGIC_INIT_LOCK() RELEASE_LOCK(&magic_init_mutex);
1511 : #else /* USE_LOCKS */
1512 : #define ACQUIRE_MAGIC_INIT_LOCK()
1513 : #define RELEASE_MAGIC_INIT_LOCK()
1514 : #endif /* USE_LOCKS */
1515 :
1516 :
1517 : /* ----------------------- Chunk representations ------------------------ */
1518 :
1519 : /*
1520 : (The following includes lightly edited explanations by Colin Plumb.)
1521 :
1522 : The malloc_chunk declaration below is misleading (but accurate and
1523 : necessary). It declares a "view" into memory allowing access to
1524 : necessary fields at known offsets from a given base.
1525 :
1526 : Chunks of memory are maintained using a `boundary tag' method as
1527 : originally described by Knuth. (See the paper by Paul Wilson
1528 : ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
1529 : techniques.) Sizes of free chunks are stored both in the front of
1530 : each chunk and at the end. This makes consolidating fragmented
1531 : chunks into bigger chunks fast. The head fields also hold bits
1532 : representing whether chunks are free or in use.
1533 :
1534 : Here are some pictures to make it clearer. They are "exploded" to
1535 : show that the state of a chunk can be thought of as extending from
1536 : the high 31 bits of the head field of its header through the
1537 : prev_foot and PINUSE_BIT bit of the following chunk header.
1538 :
1539 : A chunk that's in use looks like:
1540 :
1541 : chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1542 : | Size of previous chunk (if P = 1) |
1543 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1544 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1545 : | Size of this chunk 1| +-+
1546 : mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1547 : | |
1548 : +- -+
1549 : | |
1550 : +- -+
1551 : | :
1552 : +- size - sizeof(size_t) available payload bytes -+
1553 : : |
1554 : chunk-> +- -+
1555 : | |
1556 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1557 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
1558 : | Size of next chunk (may or may not be in use) | +-+
1559 : mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1560 :
1561 : And if it's free, it looks like this:
1562 :
1563 : chunk-> +- -+
1564 : | User payload (must be in use, or we would have merged!) |
1565 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1566 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
1567 : | Size of this chunk 0| +-+
1568 : mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1569 : | Next pointer |
1570 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1571 : | Prev pointer |
1572 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1573 : | :
1574 : +- size - sizeof(struct chunk) unused bytes -+
1575 : : |
1576 : chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1577 : | Size of this chunk |
1578 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1579 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
1580 : | Size of next chunk (must be in use, or we would have merged)| +-+
1581 : mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1582 : | :
1583 : +- User payload -+
1584 : : |
1585 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1586 : |0|
1587 : +-+
1588 : Note that since we always merge adjacent free chunks, the chunks
1589 : adjacent to a free chunk must be in use.
1590 :
1591 : Given a pointer to a chunk (which can be derived trivially from the
1592 : payload pointer) we can, in O(1) time, find out whether the adjacent
1593 : chunks are free, and if so, unlink them from the lists that they
1594 : are on and merge them with the current chunk.
1595 :
1596 : Chunks always begin on even word boundaries, so the mem portion
1597 : (which is returned to the user) is also on an even word boundary, and
1598 : thus at least double-word aligned.
1599 :
1600 : The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
1601 : chunk size (which is always a multiple of two words), is an in-use
1602 : bit for the *previous* chunk. If that bit is *clear*, then the
1603 : word before the current chunk size contains the previous chunk
1604 : size, and can be used to find the front of the previous chunk.
1605 : The very first chunk allocated always has this bit set, preventing
1606 : access to non-existent (or non-owned) memory. If pinuse is set for
1607 : any given chunk, then you CANNOT determine the size of the
1608 : previous chunk, and might even get a memory addressing fault when
1609 : trying to do so.
1610 :
1611 : The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
1612 : the chunk size redundantly records whether the current chunk is
1613 : inuse. This redundancy enables usage checks within free and realloc,
1614 : and reduces indirection when freeing and consolidating chunks.
1615 :
1616 : Each freshly allocated chunk must have both cinuse and pinuse set.
1617 : That is, each allocated chunk borders either a previously allocated
1618 : and still in-use chunk, or the base of its memory arena. This is
1619 : ensured by making all allocations from the the `lowest' part of any
1620 : found chunk. Further, no free chunk physically borders another one,
1621 : so each free chunk is known to be preceded and followed by either
1622 : inuse chunks or the ends of memory.
1623 :
1624 : Note that the `foot' of the current chunk is actually represented
1625 : as the prev_foot of the NEXT chunk. This makes it easier to
1626 : deal with alignments etc but can be very confusing when trying
1627 : to extend or adapt this code.
1628 :
1629 : The exceptions to all this are
1630 :
1631 : 1. The special chunk `top' is the top-most available chunk (i.e.,
1632 : the one bordering the end of available memory). It is treated
1633 : specially. Top is never included in any bin, is used only if
1634 : no other chunk is available, and is released back to the
1635 : system if it is very large (see M_TRIM_THRESHOLD). In effect,
1636 : the top chunk is treated as larger (and thus less well
1637 : fitting) than any other available chunk. The top chunk
1638 : doesn't update its trailing size field since there is no next
1639 : contiguous chunk that would have to index off it. However,
1640 : space is still allocated for it (TOP_FOOT_SIZE) to enable
1641 : separation or merging when space is extended.
1642 :
1643 : 3. Chunks allocated via mmap, which have the lowest-order bit
1644 : (IS_MMAPPED_BIT) set in their prev_foot fields, and do not set
1645 : PINUSE_BIT in their head fields. Because they are allocated
1646 : one-by-one, each must carry its own prev_foot field, which is
1647 : also used to hold the offset this chunk has within its mmapped
1648 : region, which is needed to preserve alignment. Each mmapped
1649 : chunk is trailed by the first two fields of a fake next-chunk
1650 : for sake of usage checks.
1651 :
1652 : */
1653 :
1654 : struct malloc_chunk {
1655 : size_t prev_foot; /* Size of previous chunk (if free). */
1656 : size_t head; /* Size and inuse bits. */
1657 : struct malloc_chunk* fd; /* double links -- used only if free. */
1658 : struct malloc_chunk* bk;
1659 : };
1660 :
1661 : typedef struct malloc_chunk mchunk;
1662 : typedef struct malloc_chunk* mchunkptr;
1663 : typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */
1664 : typedef size_t bindex_t; /* Described below */
1665 : typedef unsigned int binmap_t; /* Described below */
1666 : typedef unsigned int flag_t; /* The type of various bit flag sets */
1667 :
1668 : /* ------------------- Chunks sizes and alignments ----------------------- */
1669 :
1670 : #define MCHUNK_SIZE (sizeof(mchunk))
1671 :
1672 : #if FOOTERS
1673 : #define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
1674 : #else /* FOOTERS */
1675 : #define CHUNK_OVERHEAD (SIZE_T_SIZE)
1676 : #endif /* FOOTERS */
1677 :
1678 : /* MMapped chunks need a second word of overhead ... */
1679 : #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)
1680 : /* ... and additional padding for fake next-chunk at foot */
1681 : #define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES)
1682 :
1683 : /* The smallest size we can malloc is an aligned minimal chunk */
1684 : #define MIN_CHUNK_SIZE\
1685 : ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
1686 :
1687 : /* conversion from malloc headers to user pointers, and back */
1688 : #define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))
1689 : #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))
1690 : /* chunk associated with aligned address A */
1691 : #define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))
1692 :
1693 : /* Bounds on request (not chunk) sizes. */
1694 : #define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)
1695 : #define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)
1696 :
1697 : /* pad request bytes into a usable size */
1698 : #define pad_request(req) \
1699 : (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)
1700 :
1701 : /* pad request, checking for minimum (but not maximum) */
1702 : #define request2size(req) \
1703 : (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
1704 :
1705 :
1706 : /* ------------------ Operations on head and foot fields ----------------- */
1707 :
1708 : /*
1709 : The head field of a chunk is or'ed with PINUSE_BIT when previous
1710 : adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
1711 : use. If the chunk was obtained with mmap, the prev_foot field has
1712 : IS_MMAPPED_BIT set, otherwise holding the offset of the base of the
1713 : mmapped region to the base of the chunk.
1714 : */
1715 :
1716 : #define PINUSE_BIT (SIZE_T_ONE)
1717 : #define CINUSE_BIT (SIZE_T_TWO)
1718 : #define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)
1719 :
1720 : /* Head value for fenceposts */
1721 : #define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)
1722 :
1723 : /* extraction of fields from head words */
1724 : #define cinuse(p) ((p)->head & CINUSE_BIT)
1725 : #define pinuse(p) ((p)->head & PINUSE_BIT)
1726 : #define chunksize(p) ((p)->head & ~(INUSE_BITS))
1727 :
1728 : #define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)
1729 : #define clear_cinuse(p) ((p)->head &= ~CINUSE_BIT)
1730 :
1731 : /* Treat space at ptr +/- offset as a chunk */
1732 : #define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
1733 : #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))
1734 :
1735 : /* Ptr to next or previous physical malloc_chunk. */
1736 : #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~INUSE_BITS)))
1737 : #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
1738 :
1739 : /* extract next chunk's pinuse bit */
1740 : #define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)
1741 :
1742 : /* Get/set size at footer */
1743 : #define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)
1744 : #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))
1745 :
1746 : /* Set size, pinuse bit, and foot */
1747 : #define set_size_and_pinuse_of_free_chunk(p, s)\
1748 : ((p)->head = (s|PINUSE_BIT), set_foot(p, s))
1749 :
1750 : /* Set size, pinuse bit, foot, and clear next pinuse */
1751 : #define set_free_with_pinuse(p, s, n)\
1752 : (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))
1753 :
1754 : #define is_mmapped(p)\
1755 : (!((p)->head & PINUSE_BIT) && ((p)->prev_foot & IS_MMAPPED_BIT))
1756 :
1757 : /* Get the internal overhead associated with chunk p */
1758 : #define overhead_for(p)\
1759 : (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)
1760 :
1761 : /* Return true if malloced space is not necessarily cleared */
1762 : #if MMAP_CLEARS
1763 : #define calloc_must_clear(p) (!is_mmapped(p))
1764 : #else /* MMAP_CLEARS */
1765 : #define calloc_must_clear(p) (1)
1766 : #endif /* MMAP_CLEARS */
1767 :
1768 : /* ---------------------- Overlaid data structures ----------------------- */
1769 :
1770 : /*
1771 : When chunks are not in use, they are treated as nodes of either
1772 : lists or trees.
1773 :
1774 : "Small" chunks are stored in circular doubly-linked lists, and look
1775 : like this:
1776 :
1777 : chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1778 : | Size of previous chunk |
1779 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1780 : `head:' | Size of chunk, in bytes |P|
1781 : mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1782 : | Forward pointer to next chunk in list |
1783 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1784 : | Back pointer to previous chunk in list |
1785 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1786 : | Unused space (may be 0 bytes long) .
1787 : . .
1788 : . |
1789 : nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1790 : `foot:' | Size of chunk, in bytes |
1791 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1792 :
1793 : Larger chunks are kept in a form of bitwise digital trees (aka
1794 : tries) keyed on chunksizes. Because malloc_tree_chunks are only for
1795 : free chunks greater than 256 bytes, their size doesn't impose any
1796 : constraints on user chunk sizes. Each node looks like:
1797 :
1798 : chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1799 : | Size of previous chunk |
1800 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1801 : `head:' | Size of chunk, in bytes |P|
1802 : mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1803 : | Forward pointer to next chunk of same size |
1804 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1805 : | Back pointer to previous chunk of same size |
1806 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1807 : | Pointer to left child (child[0]) |
1808 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1809 : | Pointer to right child (child[1]) |
1810 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1811 : | Pointer to parent |
1812 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1813 : | bin index of this chunk |
1814 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1815 : | Unused space .
1816 : . |
1817 : nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1818 : `foot:' | Size of chunk, in bytes |
1819 : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1820 :
1821 : Each tree holding treenodes is a tree of unique chunk sizes. Chunks
1822 : of the same size are arranged in a circularly-linked list, with only
1823 : the oldest chunk (the next to be used, in our FIFO ordering)
1824 : actually in the tree. (Tree members are distinguished by a non-null
1825 : parent pointer.) If a chunk with the same size an an existing node
1826 : is inserted, it is linked off the existing node using pointers that
1827 : work in the same way as fd/bk pointers of small chunks.
1828 :
1829 : Each tree contains a power of 2 sized range of chunk sizes (the
1830 : smallest is 0x100 <= x < 0x180), which is is divided in half at each
1831 : tree level, with the chunks in the smaller half of the range (0x100
1832 : <= x < 0x140 for the top nose) in the left subtree and the larger
1833 : half (0x140 <= x < 0x180) in the right subtree. This is, of course,
1834 : done by inspecting individual bits.
1835 :
1836 : Using these rules, each node's left subtree contains all smaller
1837 : sizes than its right subtree. However, the node at the root of each
1838 : subtree has no particular ordering relationship to either. (The
1839 : dividing line between the subtree sizes is based on trie relation.)
1840 : If we remove the last chunk of a given size from the interior of the
1841 : tree, we need to replace it with a leaf node. The tree ordering
1842 : rules permit a node to be replaced by any leaf below it.
1843 :
1844 : The smallest chunk in a tree (a common operation in a best-fit
1845 : allocator) can be found by walking a path to the leftmost leaf in
1846 : the tree. Unlike a usual binary tree, where we follow left child
1847 : pointers until we reach a null, here we follow the right child
1848 : pointer any time the left one is null, until we reach a leaf with
1849 : both child pointers null. The smallest chunk in the tree will be
1850 : somewhere along that path.
1851 :
1852 : The worst case number of steps to add, find, or remove a node is
1853 : bounded by the number of bits differentiating chunks within
1854 : bins. Under current bin calculations, this ranges from 6 up to 21
1855 : (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
1856 : is of course much better.
1857 : */
1858 :
1859 : struct malloc_tree_chunk {
1860 : /* The first four fields must be compatible with malloc_chunk */
1861 : size_t prev_foot;
1862 : size_t head;
1863 : struct malloc_tree_chunk* fd;
1864 : struct malloc_tree_chunk* bk;
1865 :
1866 : struct malloc_tree_chunk* child[2];
1867 : struct malloc_tree_chunk* parent;
1868 : bindex_t index;
1869 : };
1870 :
1871 : typedef struct malloc_tree_chunk tchunk;
1872 : typedef struct malloc_tree_chunk* tchunkptr;
1873 : typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
1874 :
1875 : /* A little helper macro for trees */
1876 : #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])
1877 :
1878 : /* ----------------------------- Segments -------------------------------- */
1879 :
1880 : /*
1881 : Each malloc space may include non-contiguous segments, held in a
1882 : list headed by an embedded malloc_segment record representing the
1883 : top-most space. Segments also include flags holding properties of
1884 : the space. Large chunks that are directly allocated by mmap are not
1885 : included in this list. They are instead independently created and
1886 : destroyed without otherwise keeping track of them.
1887 :
1888 : Segment management mainly comes into play for spaces allocated by
1889 : MMAP. Any call to MMAP might or might not return memory that is
1890 : adjacent to an existing segment. MORECORE normally contiguously
1891 : extends the current space, so this space is almost always adjacent,
1892 : which is simpler and faster to deal with. (This is why MORECORE is
1893 : used preferentially to MMAP when both are available -- see
1894 : sys_alloc.) When allocating using MMAP, we don't use any of the
1895 : hinting mechanisms (inconsistently) supported in various
1896 : implementations of unix mmap, or distinguish reserving from
1897 : committing memory. Instead, we just ask for space, and exploit
1898 : contiguity when we get it. It is probably possible to do
1899 : better than this on some systems, but no general scheme seems
1900 : to be significantly better.
1901 :
1902 : Management entails a simpler variant of the consolidation scheme
1903 : used for chunks to reduce fragmentation -- new adjacent memory is
1904 : normally prepended or appended to an existing segment. However,
1905 : there are limitations compared to chunk consolidation that mostly
1906 : reflect the fact that segment processing is relatively infrequent
1907 : (occurring only when getting memory from system) and that we
1908 : don't expect to have huge numbers of segments:
1909 :
1910 : * Segments are not indexed, so traversal requires linear scans. (It
1911 : would be possible to index these, but is not worth the extra
1912 : overhead and complexity for most programs on most platforms.)
1913 : * New segments are only appended to old ones when holding top-most
1914 : memory; if they cannot be prepended to others, they are held in
1915 : different segments.
1916 :
1917 : Except for the top-most segment of an mstate, each segment record
1918 : is kept at the tail of its segment. Segments are added by pushing
1919 : segment records onto the list headed by &mstate.seg for the
1920 : containing mstate.
1921 :
1922 : Segment flags control allocation/merge/deallocation policies:
1923 : * If EXTERN_BIT set, then we did not allocate this segment,
1924 : and so should not try to deallocate or merge with others.
1925 : (This currently holds only for the initial segment passed
1926 : into create_mspace_with_base.)
1927 : * If IS_MMAPPED_BIT set, the segment may be merged with
1928 : other surrounding mmapped segments and trimmed/de-allocated
1929 : using munmap.
1930 : * If neither bit is set, then the segment was obtained using
1931 : MORECORE so can be merged with surrounding MORECORE'd segments
1932 : and deallocated/trimmed using MORECORE with negative arguments.
1933 : */
1934 :
1935 : struct malloc_segment {
1936 : char* base; /* base address */
1937 : size_t size; /* allocated size */
1938 : struct malloc_segment* next; /* ptr to next segment */
1939 : #if FFI_MMAP_EXEC_WRIT
1940 : /* The mmap magic is supposed to store the address of the executable
1941 : segment at the very end of the requested block. */
1942 :
1943 : # define mmap_exec_offset(b,s) (*(ptrdiff_t*)((b)+(s)-sizeof(ptrdiff_t)))
1944 :
1945 : /* We can only merge segments if their corresponding executable
1946 : segments are at identical offsets. */
1947 : # define check_segment_merge(S,b,s) \
1948 : (mmap_exec_offset((b),(s)) == (S)->exec_offset)
1949 :
1950 : # define add_segment_exec_offset(p,S) ((char*)(p) + (S)->exec_offset)
1951 : # define sub_segment_exec_offset(p,S) ((char*)(p) - (S)->exec_offset)
1952 :
1953 : /* The removal of sflags only works with HAVE_MORECORE == 0. */
1954 :
1955 : # define get_segment_flags(S) (IS_MMAPPED_BIT)
1956 : # define set_segment_flags(S,v) \
1957 : (((v) != IS_MMAPPED_BIT) ? (ABORT, (v)) : \
1958 : (((S)->exec_offset = \
1959 : mmap_exec_offset((S)->base, (S)->size)), \
1960 : (mmap_exec_offset((S)->base + (S)->exec_offset, (S)->size) != \
1961 : (S)->exec_offset) ? (ABORT, (v)) : \
1962 : (mmap_exec_offset((S)->base, (S)->size) = 0), (v)))
1963 :
1964 : /* We use an offset here, instead of a pointer, because then, when
1965 : base changes, we don't have to modify this. On architectures
1966 : with segmented addresses, this might not work. */
1967 : ptrdiff_t exec_offset;
1968 : #else
1969 :
1970 : # define get_segment_flags(S) ((S)->sflags)
1971 : # define set_segment_flags(S,v) ((S)->sflags = (v))
1972 : # define check_segment_merge(S,b,s) (1)
1973 :
1974 : flag_t sflags; /* mmap and extern flag */
1975 : #endif
1976 : };
1977 :
1978 : #define is_mmapped_segment(S) (get_segment_flags(S) & IS_MMAPPED_BIT)
1979 : #define is_extern_segment(S) (get_segment_flags(S) & EXTERN_BIT)
1980 :
1981 : typedef struct malloc_segment msegment;
1982 : typedef struct malloc_segment* msegmentptr;
1983 :
1984 : /* ---------------------------- malloc_state ----------------------------- */
1985 :
1986 : /*
1987 : A malloc_state holds all of the bookkeeping for a space.
1988 : The main fields are:
1989 :
1990 : Top
1991 : The topmost chunk of the currently active segment. Its size is
1992 : cached in topsize. The actual size of topmost space is
1993 : topsize+TOP_FOOT_SIZE, which includes space reserved for adding
1994 : fenceposts and segment records if necessary when getting more
1995 : space from the system. The size at which to autotrim top is
1996 : cached from mparams in trim_check, except that it is disabled if
1997 : an autotrim fails.
1998 :
1999 : Designated victim (dv)
2000 : This is the preferred chunk for servicing small requests that
2001 : don't have exact fits. It is normally the chunk split off most
2002 : recently to service another small request. Its size is cached in
2003 : dvsize. The link fields of this chunk are not maintained since it
2004 : is not kept in a bin.
2005 :
2006 : SmallBins
2007 : An array of bin headers for free chunks. These bins hold chunks
2008 : with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
2009 : chunks of all the same size, spaced 8 bytes apart. To simplify
2010 : use in double-linked lists, each bin header acts as a malloc_chunk
2011 : pointing to the real first node, if it exists (else pointing to
2012 : itself). This avoids special-casing for headers. But to avoid
2013 : waste, we allocate only the fd/bk pointers of bins, and then use
2014 : repositioning tricks to treat these as the fields of a chunk.
2015 :
2016 : TreeBins
2017 : Treebins are pointers to the roots of trees holding a range of
2018 : sizes. There are 2 equally spaced treebins for each power of two
2019 : from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
2020 : larger.
2021 :
2022 : Bin maps
2023 : There is one bit map for small bins ("smallmap") and one for
2024 : treebins ("treemap). Each bin sets its bit when non-empty, and
2025 : clears the bit when empty. Bit operations are then used to avoid
2026 : bin-by-bin searching -- nearly all "search" is done without ever
2027 : looking at bins that won't be selected. The bit maps
2028 : conservatively use 32 bits per map word, even if on 64bit system.
2029 : For a good description of some of the bit-based techniques used
2030 : here, see Henry S. Warren Jr's book "Hacker's Delight" (and
2031 : supplement at http://hackersdelight.org/). Many of these are
2032 : intended to reduce the branchiness of paths through malloc etc, as
2033 : well as to reduce the number of memory locations read or written.
2034 :
2035 : Segments
2036 : A list of segments headed by an embedded malloc_segment record
2037 : representing the initial space.
2038 :
2039 : Address check support
2040 : The least_addr field is the least address ever obtained from
2041 : MORECORE or MMAP. Attempted frees and reallocs of any address less
2042 : than this are trapped (unless INSECURE is defined).
2043 :
2044 : Magic tag
2045 : A cross-check field that should always hold same value as mparams.magic.
2046 :
2047 : Flags
2048 : Bits recording whether to use MMAP, locks, or contiguous MORECORE
2049 :
2050 : Statistics
2051 : Each space keeps track of current and maximum system memory
2052 : obtained via MORECORE or MMAP.
2053 :
2054 : Locking
2055 : If USE_LOCKS is defined, the "mutex" lock is acquired and released
2056 : around every public call using this mspace.
2057 : */
2058 :
2059 : /* Bin types, widths and sizes */
2060 : #define NSMALLBINS (32U)
2061 : #define NTREEBINS (32U)
2062 : #define SMALLBIN_SHIFT (3U)
2063 : #define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)
2064 : #define TREEBIN_SHIFT (8U)
2065 : #define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)
2066 : #define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)
2067 : #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)
2068 :
2069 : struct malloc_state {
2070 : binmap_t smallmap;
2071 : binmap_t treemap;
2072 : size_t dvsize;
2073 : size_t topsize;
2074 : char* least_addr;
2075 : mchunkptr dv;
2076 : mchunkptr top;
2077 : size_t trim_check;
2078 : size_t magic;
2079 : mchunkptr smallbins[(NSMALLBINS+1)*2];
2080 : tbinptr treebins[NTREEBINS];
2081 : size_t footprint;
2082 : size_t max_footprint;
2083 : flag_t mflags;
2084 : #if USE_LOCKS
2085 : MLOCK_T mutex; /* locate lock among fields that rarely change */
2086 : #endif /* USE_LOCKS */
2087 : msegment seg;
2088 : };
2089 :
2090 : typedef struct malloc_state* mstate;
2091 :
2092 : /* ------------- Global malloc_state and malloc_params ------------------- */
2093 :
2094 : /*
2095 : malloc_params holds global properties, including those that can be
2096 : dynamically set using mallopt. There is a single instance, mparams,
2097 : initialized in init_mparams.
2098 : */
2099 :
2100 : struct malloc_params {
2101 : size_t magic;
2102 : size_t page_size;
2103 : size_t granularity;
2104 : size_t mmap_threshold;
2105 : size_t trim_threshold;
2106 : flag_t default_mflags;
2107 : };
2108 :
2109 : static struct malloc_params mparams;
2110 :
2111 : /* The global malloc_state used for all non-"mspace" calls */
2112 : static struct malloc_state _gm_;
2113 : #define gm (&_gm_)
2114 : #define is_global(M) ((M) == &_gm_)
2115 : #define is_initialized(M) ((M)->top != 0)
2116 :
2117 : /* -------------------------- system alloc setup ------------------------- */
2118 :
2119 : /* Operations on mflags */
2120 :
2121 : #define use_lock(M) ((M)->mflags & USE_LOCK_BIT)
2122 : #define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)
2123 : #define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)
2124 :
2125 : #define use_mmap(M) ((M)->mflags & USE_MMAP_BIT)
2126 : #define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT)
2127 : #define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT)
2128 :
2129 : #define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT)
2130 : #define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT)
2131 :
2132 : #define set_lock(M,L)\
2133 : ((M)->mflags = (L)?\
2134 : ((M)->mflags | USE_LOCK_BIT) :\
2135 : ((M)->mflags & ~USE_LOCK_BIT))
2136 :
2137 : /* page-align a size */
2138 : #define page_align(S)\
2139 : (((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))
2140 :
2141 : /* granularity-align a size */
2142 : #define granularity_align(S)\
2143 : (((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))
2144 :
2145 : #define is_page_aligned(S)\
2146 : (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)
2147 : #define is_granularity_aligned(S)\
2148 : (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)
2149 :
2150 : /* True if segment S holds address A */
2151 : #define segment_holds(S, A)\
2152 : ((char*)(A) >= S->base && (char*)(A) < S->base + S->size)
2153 :
2154 : /* Return segment holding given address */
2155 0 : static msegmentptr segment_holding(mstate m, char* addr) {
2156 0 : msegmentptr sp = &m->seg;
2157 : for (;;) {
2158 0 : if (addr >= sp->base && addr < sp->base + sp->size)
2159 0 : return sp;
2160 0 : if ((sp = sp->next) == 0)
2161 0 : return 0;
2162 : }
2163 : }
2164 :
2165 : /* Return true if segment contains a segment link */
2166 0 : static int has_segment_link(mstate m, msegmentptr ss) {
2167 0 : msegmentptr sp = &m->seg;
2168 : for (;;) {
2169 0 : if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)
2170 0 : return 1;
2171 0 : if ((sp = sp->next) == 0)
2172 0 : return 0;
2173 : }
2174 : }
2175 :
2176 : #ifndef MORECORE_CANNOT_TRIM
2177 : #define should_trim(M,s) ((s) > (M)->trim_check)
2178 : #else /* MORECORE_CANNOT_TRIM */
2179 : #define should_trim(M,s) (0)
2180 : #endif /* MORECORE_CANNOT_TRIM */
2181 :
2182 : /*
2183 : TOP_FOOT_SIZE is padding at the end of a segment, including space
2184 : that may be needed to place segment records and fenceposts when new
2185 : noncontiguous segments are added.
2186 : */
2187 : #define TOP_FOOT_SIZE\
2188 : (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)
2189 :
2190 :
2191 : /* ------------------------------- Hooks -------------------------------- */
2192 :
2193 : /*
2194 : PREACTION should be defined to return 0 on success, and nonzero on
2195 : failure. If you are not using locking, you can redefine these to do
2196 : anything you like.
2197 : */
2198 :
2199 : #if USE_LOCKS
2200 :
2201 : /* Ensure locks are initialized */
2202 : #define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())
2203 :
2204 : #define PREACTION(M) ((GLOBALLY_INITIALIZE() || use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)
2205 : #define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }
2206 : #else /* USE_LOCKS */
2207 :
2208 : #ifndef PREACTION
2209 : #define PREACTION(M) (0)
2210 : #endif /* PREACTION */
2211 :
2212 : #ifndef POSTACTION
2213 : #define POSTACTION(M)
2214 : #endif /* POSTACTION */
2215 :
2216 : #endif /* USE_LOCKS */
2217 :
2218 : /*
2219 : CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.
2220 : USAGE_ERROR_ACTION is triggered on detected bad frees and
2221 : reallocs. The argument p is an address that might have triggered the
2222 : fault. It is ignored by the two predefined actions, but might be
2223 : useful in custom actions that try to help diagnose errors.
2224 : */
2225 :
2226 : #if PROCEED_ON_ERROR
2227 :
2228 : /* A count of the number of corruption errors causing resets */
2229 : int malloc_corruption_error_count;
2230 :
2231 : /* default corruption action */
2232 : static void reset_on_error(mstate m);
2233 :
2234 : #define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)
2235 : #define USAGE_ERROR_ACTION(m, p)
2236 :
2237 : #else /* PROCEED_ON_ERROR */
2238 :
2239 : #ifndef CORRUPTION_ERROR_ACTION
2240 : #define CORRUPTION_ERROR_ACTION(m) ABORT
2241 : #endif /* CORRUPTION_ERROR_ACTION */
2242 :
2243 : #ifndef USAGE_ERROR_ACTION
2244 : #define USAGE_ERROR_ACTION(m,p) ABORT
2245 : #endif /* USAGE_ERROR_ACTION */
2246 :
2247 : #endif /* PROCEED_ON_ERROR */
2248 :
2249 : /* -------------------------- Debugging setup ---------------------------- */
2250 :
2251 : #if ! DEBUG
2252 :
2253 : #define check_free_chunk(M,P)
2254 : #define check_inuse_chunk(M,P)
2255 : #define check_malloced_chunk(M,P,N)
2256 : #define check_mmapped_chunk(M,P)
2257 : #define check_malloc_state(M)
2258 : #define check_top_chunk(M,P)
2259 :
2260 : #else /* DEBUG */
2261 : #define check_free_chunk(M,P) do_check_free_chunk(M,P)
2262 : #define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)
2263 : #define check_top_chunk(M,P) do_check_top_chunk(M,P)
2264 : #define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)
2265 : #define check_mmapped_chunk(M,P) do_check_mmapped_chunk(M,P)
2266 : #define check_malloc_state(M) do_check_malloc_state(M)
2267 :
2268 : static void do_check_any_chunk(mstate m, mchunkptr p);
2269 : static void do_check_top_chunk(mstate m, mchunkptr p);
2270 : static void do_check_mmapped_chunk(mstate m, mchunkptr p);
2271 : static void do_check_inuse_chunk(mstate m, mchunkptr p);
2272 : static void do_check_free_chunk(mstate m, mchunkptr p);
2273 : static void do_check_malloced_chunk(mstate m, void* mem, size_t s);
2274 : static void do_check_tree(mstate m, tchunkptr t);
2275 : static void do_check_treebin(mstate m, bindex_t i);
2276 : static void do_check_smallbin(mstate m, bindex_t i);
2277 : static void do_check_malloc_state(mstate m);
2278 : static int bin_find(mstate m, mchunkptr x);
2279 : static size_t traverse_and_check(mstate m);
2280 : #endif /* DEBUG */
2281 :
2282 : /* ---------------------------- Indexing Bins ---------------------------- */
2283 :
2284 : #define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)
2285 : #define small_index(s) ((s) >> SMALLBIN_SHIFT)
2286 : #define small_index2size(i) ((i) << SMALLBIN_SHIFT)
2287 : #define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))
2288 :
2289 : /* addressing by index. See above about smallbin repositioning */
2290 : #define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))
2291 : #define treebin_at(M,i) (&((M)->treebins[i]))
2292 :
2293 : /* assign tree index for size S to variable I */
2294 : #if defined(__GNUC__) && defined(i386)
2295 : #define compute_tree_index(S, I)\
2296 : {\
2297 : size_t X = S >> TREEBIN_SHIFT;\
2298 : if (X == 0)\
2299 : I = 0;\
2300 : else if (X > 0xFFFF)\
2301 : I = NTREEBINS-1;\
2302 : else {\
2303 : unsigned int K;\
2304 : __asm__("bsrl %1,%0\n\t" : "=r" (K) : "rm" (X));\
2305 : I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\
2306 : }\
2307 : }
2308 : #else /* GNUC */
2309 : #define compute_tree_index(S, I)\
2310 : {\
2311 : size_t X = S >> TREEBIN_SHIFT;\
2312 : if (X == 0)\
2313 : I = 0;\
2314 : else if (X > 0xFFFF)\
2315 : I = NTREEBINS-1;\
2316 : else {\
2317 : unsigned int Y = (unsigned int)X;\
2318 : unsigned int N = ((Y - 0x100) >> 16) & 8;\
2319 : unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
2320 : N += K;\
2321 : N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
2322 : K = 14 - N + ((Y <<= K) >> 15);\
2323 : I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
2324 : }\
2325 : }
2326 : #endif /* GNUC */
2327 :
2328 : /* Bit representing maximum resolved size in a treebin at i */
2329 : #define bit_for_tree_index(i) \
2330 : (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)
2331 :
2332 : /* Shift placing maximum resolved bit in a treebin at i as sign bit */
2333 : #define leftshift_for_tree_index(i) \
2334 : ((i == NTREEBINS-1)? 0 : \
2335 : ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))
2336 :
2337 : /* The size of the smallest chunk held in bin with index i */
2338 : #define minsize_for_tree_index(i) \
2339 : ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \
2340 : (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))
2341 :
2342 :
2343 : /* ------------------------ Operations on bin maps ----------------------- */
2344 :
2345 : /* bit corresponding to given index */
2346 : #define idx2bit(i) ((binmap_t)(1) << (i))
2347 :
2348 : /* Mark/Clear bits with given index */
2349 : #define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))
2350 : #define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))
2351 : #define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))
2352 :
2353 : #define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))
2354 : #define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))
2355 : #define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))
2356 :
2357 : /* index corresponding to given bit */
2358 :
2359 : #if defined(__GNUC__) && defined(i386)
2360 : #define compute_bit2idx(X, I)\
2361 : {\
2362 : unsigned int J;\
2363 : __asm__("bsfl %1,%0\n\t" : "=r" (J) : "rm" (X));\
2364 : I = (bindex_t)J;\
2365 : }
2366 :
2367 : #else /* GNUC */
2368 : #if USE_BUILTIN_FFS
2369 : #define compute_bit2idx(X, I) I = ffs(X)-1
2370 :
2371 : #else /* USE_BUILTIN_FFS */
2372 : #define compute_bit2idx(X, I)\
2373 : {\
2374 : unsigned int Y = X - 1;\
2375 : unsigned int K = Y >> (16-4) & 16;\
2376 : unsigned int N = K; Y >>= K;\
2377 : N += K = Y >> (8-3) & 8; Y >>= K;\
2378 : N += K = Y >> (4-2) & 4; Y >>= K;\
2379 : N += K = Y >> (2-1) & 2; Y >>= K;\
2380 : N += K = Y >> (1-0) & 1; Y >>= K;\
2381 : I = (bindex_t)(N + Y);\
2382 : }
2383 : #endif /* USE_BUILTIN_FFS */
2384 : #endif /* GNUC */
2385 :
2386 : /* isolate the least set bit of a bitmap */
2387 : #define least_bit(x) ((x) & -(x))
2388 :
2389 : /* mask with all bits to left of least bit of x on */
2390 : #define left_bits(x) ((x<<1) | -(x<<1))
2391 :
2392 : /* mask with all bits to left of or equal to least bit of x on */
2393 : #define same_or_left_bits(x) ((x) | -(x))
2394 :
2395 :
2396 : /* ----------------------- Runtime Check Support ------------------------- */
2397 :
2398 : /*
2399 : For security, the main invariant is that malloc/free/etc never
2400 : writes to a static address other than malloc_state, unless static
2401 : malloc_state itself has been corrupted, which cannot occur via
2402 : malloc (because of these checks). In essence this means that we
2403 : believe all pointers, sizes, maps etc held in malloc_state, but
2404 : check all of those linked or offsetted from other embedded data
2405 : structures. These checks are interspersed with main code in a way
2406 : that tends to minimize their run-time cost.
2407 :
2408 : When FOOTERS is defined, in addition to range checking, we also
2409 : verify footer fields of inuse chunks, which can be used guarantee
2410 : that the mstate controlling malloc/free is intact. This is a
2411 : streamlined version of the approach described by William Robertson
2412 : et al in "Run-time Detection of Heap-based Overflows" LISA'03
2413 : http://www.usenix.org/events/lisa03/tech/robertson.html The footer
2414 : of an inuse chunk holds the xor of its mstate and a random seed,
2415 : that is checked upon calls to free() and realloc(). This is
2416 : (probablistically) unguessable from outside the program, but can be
2417 : computed by any code successfully malloc'ing any chunk, so does not
2418 : itself provide protection against code that has already broken
2419 : security through some other means. Unlike Robertson et al, we
2420 : always dynamically check addresses of all offset chunks (previous,
2421 : next, etc). This turns out to be cheaper than relying on hashes.
2422 : */
2423 :
2424 : #if !INSECURE
2425 : /* Check if address a is at least as high as any from MORECORE or MMAP */
2426 : #define ok_address(M, a) ((char*)(a) >= (M)->least_addr)
2427 : /* Check if address of next chunk n is higher than base chunk p */
2428 : #define ok_next(p, n) ((char*)(p) < (char*)(n))
2429 : /* Check if p has its cinuse bit on */
2430 : #define ok_cinuse(p) cinuse(p)
2431 : /* Check if p has its pinuse bit on */
2432 : #define ok_pinuse(p) pinuse(p)
2433 :
2434 : #else /* !INSECURE */
2435 : #define ok_address(M, a) (1)
2436 : #define ok_next(b, n) (1)
2437 : #define ok_cinuse(p) (1)
2438 : #define ok_pinuse(p) (1)
2439 : #endif /* !INSECURE */
2440 :
2441 : #if (FOOTERS && !INSECURE)
2442 : /* Check if (alleged) mstate m has expected magic field */
2443 : #define ok_magic(M) ((M)->magic == mparams.magic)
2444 : #else /* (FOOTERS && !INSECURE) */
2445 : #define ok_magic(M) (1)
2446 : #endif /* (FOOTERS && !INSECURE) */
2447 :
2448 :
2449 : /* In gcc, use __builtin_expect to minimize impact of checks */
2450 : #if !INSECURE
2451 : #if defined(__GNUC__) && __GNUC__ >= 3
2452 : #define RTCHECK(e) __builtin_expect(e, 1)
2453 : #else /* GNUC */
2454 : #define RTCHECK(e) (e)
2455 : #endif /* GNUC */
2456 : #else /* !INSECURE */
2457 : #define RTCHECK(e) (1)
2458 : #endif /* !INSECURE */
2459 :
2460 : /* macros to set up inuse chunks with or without footers */
2461 :
2462 : #if !FOOTERS
2463 :
2464 : #define mark_inuse_foot(M,p,s)
2465 :
2466 : /* Set cinuse bit and pinuse bit of next chunk */
2467 : #define set_inuse(M,p,s)\
2468 : ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2469 : ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2470 :
2471 : /* Set cinuse and pinuse of this chunk and pinuse of next chunk */
2472 : #define set_inuse_and_pinuse(M,p,s)\
2473 : ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2474 : ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)
2475 :
2476 : /* Set size, cinuse and pinuse bit of this chunk */
2477 : #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2478 : ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))
2479 :
2480 : #else /* FOOTERS */
2481 :
2482 : /* Set foot of inuse chunk to be xor of mstate and seed */
2483 : #define mark_inuse_foot(M,p,s)\
2484 : (((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))
2485 :
2486 : #define get_mstate_for(p)\
2487 : ((mstate)(((mchunkptr)((char*)(p) +\
2488 : (chunksize(p))))->prev_foot ^ mparams.magic))
2489 :
2490 : #define set_inuse(M,p,s)\
2491 : ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\
2492 : (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \
2493 : mark_inuse_foot(M,p,s))
2494 :
2495 : #define set_inuse_and_pinuse(M,p,s)\
2496 : ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2497 : (((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\
2498 : mark_inuse_foot(M,p,s))
2499 :
2500 : #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
2501 : ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
2502 : mark_inuse_foot(M, p, s))
2503 :
2504 : #endif /* !FOOTERS */
2505 :
2506 : /* ---------------------------- setting mparams -------------------------- */
2507 :
2508 : /* Initialize mparams */
2509 0 : static int init_mparams(void) {
2510 0 : if (mparams.page_size == 0) {
2511 : size_t s;
2512 :
2513 0 : mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
2514 0 : mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;
2515 : #if MORECORE_CONTIGUOUS
2516 : mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;
2517 : #else /* MORECORE_CONTIGUOUS */
2518 0 : mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;
2519 : #endif /* MORECORE_CONTIGUOUS */
2520 :
2521 : #if (FOOTERS && !INSECURE)
2522 : {
2523 : #if USE_DEV_RANDOM
2524 : int fd;
2525 : unsigned char buf[sizeof(size_t)];
2526 : /* Try to use /dev/urandom, else fall back on using time */
2527 : if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&
2528 : read(fd, buf, sizeof(buf)) == sizeof(buf)) {
2529 : s = *((size_t *) buf);
2530 : close(fd);
2531 : }
2532 : else
2533 : #endif /* USE_DEV_RANDOM */
2534 : s = (size_t)(time(0) ^ (size_t)0x55555555U);
2535 :
2536 : s |= (size_t)8U; /* ensure nonzero */
2537 : s &= ~(size_t)7U; /* improve chances of fault for bad values */
2538 :
2539 : }
2540 : #else /* (FOOTERS && !INSECURE) */
2541 0 : s = (size_t)0x58585858U;
2542 : #endif /* (FOOTERS && !INSECURE) */
2543 0 : ACQUIRE_MAGIC_INIT_LOCK();
2544 0 : if (mparams.magic == 0) {
2545 0 : mparams.magic = s;
2546 : /* Set up lock for main malloc area */
2547 0 : INITIAL_LOCK(&gm->mutex);
2548 0 : gm->mflags = mparams.default_mflags;
2549 : }
2550 0 : RELEASE_MAGIC_INIT_LOCK();
2551 :
2552 : #if !defined(WIN32) && !defined(__OS2__)
2553 0 : mparams.page_size = malloc_getpagesize;
2554 0 : mparams.granularity = ((DEFAULT_GRANULARITY != 0)?
2555 0 : DEFAULT_GRANULARITY : mparams.page_size);
2556 : #elif defined (__OS2__)
2557 : /* if low-memory is used, os2munmap() would break
2558 : if it were anything other than 64k */
2559 : mparams.page_size = 4096u;
2560 : mparams.granularity = 65536u;
2561 : #else /* WIN32 */
2562 : {
2563 : SYSTEM_INFO system_info;
2564 : GetSystemInfo(&system_info);
2565 : mparams.page_size = system_info.dwPageSize;
2566 : mparams.granularity = system_info.dwAllocationGranularity;
2567 : }
2568 : #endif /* WIN32 */
2569 :
2570 : /* Sanity-check configuration:
2571 : size_t must be unsigned and as wide as pointer type.
2572 : ints must be at least 4 bytes.
2573 : alignment must be at least 8.
2574 : Alignment, min chunk size, and page size must all be powers of 2.
2575 : */
2576 0 : if ((sizeof(size_t) != sizeof(char*)) ||
2577 : (MAX_SIZE_T < MIN_CHUNK_SIZE) ||
2578 : (sizeof(int) < 4) ||
2579 : (MALLOC_ALIGNMENT < (size_t)8U) ||
2580 : ((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||
2581 : ((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) ||
2582 0 : ((mparams.granularity & (mparams.granularity-SIZE_T_ONE)) != 0) ||
2583 0 : ((mparams.page_size & (mparams.page_size-SIZE_T_ONE)) != 0))
2584 0 : ABORT;
2585 : }
2586 0 : return 0;
2587 : }
2588 :
2589 : /* support for mallopt */
2590 0 : static int change_mparam(int param_number, int value) {
2591 0 : size_t val = (size_t)value;
2592 0 : init_mparams();
2593 0 : switch(param_number) {
2594 : case M_TRIM_THRESHOLD:
2595 0 : mparams.trim_threshold = val;
2596 0 : return 1;
2597 : case M_GRANULARITY:
2598 0 : if (val >= mparams.page_size && ((val & (val-1)) == 0)) {
2599 0 : mparams.granularity = val;
2600 0 : return 1;
2601 : }
2602 : else
2603 0 : return 0;
2604 : case M_MMAP_THRESHOLD:
2605 0 : mparams.mmap_threshold = val;
2606 0 : return 1;
2607 : default:
2608 0 : return 0;
2609 : }
2610 : }
2611 :
2612 : #if DEBUG
2613 : /* ------------------------- Debugging Support --------------------------- */
2614 :
2615 : /* Check properties of any chunk, whether free, inuse, mmapped etc */
2616 0 : static void do_check_any_chunk(mstate m, mchunkptr p) {
2617 0 : assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
2618 0 : assert(ok_address(m, p));
2619 0 : }
2620 :
2621 : /* Check properties of top chunk */
2622 0 : static void do_check_top_chunk(mstate m, mchunkptr p) {
2623 0 : msegmentptr sp = segment_holding(m, (char*)p);
2624 0 : size_t sz = chunksize(p);
2625 0 : assert(sp != 0);
2626 0 : assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
2627 0 : assert(ok_address(m, p));
2628 0 : assert(sz == m->topsize);
2629 0 : assert(sz > 0);
2630 0 : assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);
2631 0 : assert(pinuse(p));
2632 0 : assert(!next_pinuse(p));
2633 0 : }
2634 :
2635 : /* Check properties of (inuse) mmapped chunks */
2636 0 : static void do_check_mmapped_chunk(mstate m, mchunkptr p) {
2637 0 : size_t sz = chunksize(p);
2638 0 : size_t len = (sz + (p->prev_foot & ~IS_MMAPPED_BIT) + MMAP_FOOT_PAD);
2639 0 : assert(is_mmapped(p));
2640 0 : assert(use_mmap(m));
2641 0 : assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));
2642 0 : assert(ok_address(m, p));
2643 0 : assert(!is_small(sz));
2644 0 : assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);
2645 0 : assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);
2646 0 : assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);
2647 0 : }
2648 :
2649 : /* Check properties of inuse chunks */
2650 0 : static void do_check_inuse_chunk(mstate m, mchunkptr p) {
2651 0 : do_check_any_chunk(m, p);
2652 0 : assert(cinuse(p));
2653 0 : assert(next_pinuse(p));
2654 : /* If not pinuse and not mmapped, previous chunk has OK offset */
2655 0 : assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);
2656 0 : if (is_mmapped(p))
2657 0 : do_check_mmapped_chunk(m, p);
2658 0 : }
2659 :
2660 : /* Check properties of free chunks */
2661 0 : static void do_check_free_chunk(mstate m, mchunkptr p) {
2662 0 : size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
2663 0 : mchunkptr next = chunk_plus_offset(p, sz);
2664 0 : do_check_any_chunk(m, p);
2665 0 : assert(!cinuse(p));
2666 0 : assert(!next_pinuse(p));
2667 0 : assert (!is_mmapped(p));
2668 0 : if (p != m->dv && p != m->top) {
2669 0 : if (sz >= MIN_CHUNK_SIZE) {
2670 0 : assert((sz & CHUNK_ALIGN_MASK) == 0);
2671 0 : assert(is_aligned(chunk2mem(p)));
2672 0 : assert(next->prev_foot == sz);
2673 0 : assert(pinuse(p));
2674 0 : assert (next == m->top || cinuse(next));
2675 0 : assert(p->fd->bk == p);
2676 0 : assert(p->bk->fd == p);
2677 : }
2678 : else /* markers are always of size SIZE_T_SIZE */
2679 0 : assert(sz == SIZE_T_SIZE);
2680 : }
2681 0 : }
2682 :
2683 : /* Check properties of malloced chunks at the point they are malloced */
2684 0 : static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {
2685 0 : if (mem != 0) {
2686 0 : mchunkptr p = mem2chunk(mem);
2687 0 : size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);
2688 0 : do_check_inuse_chunk(m, p);
2689 0 : assert((sz & CHUNK_ALIGN_MASK) == 0);
2690 0 : assert(sz >= MIN_CHUNK_SIZE);
2691 0 : assert(sz >= s);
2692 : /* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */
2693 0 : assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));
2694 : }
2695 0 : }
2696 :
2697 : /* Check a tree and its subtrees. */
2698 0 : static void do_check_tree(mstate m, tchunkptr t) {
2699 0 : tchunkptr head = 0;
2700 0 : tchunkptr u = t;
2701 0 : bindex_t tindex = t->index;
2702 0 : size_t tsize = chunksize(t);
2703 : bindex_t idx;
2704 0 : compute_tree_index(tsize, idx);
2705 0 : assert(tindex == idx);
2706 0 : assert(tsize >= MIN_LARGE_SIZE);
2707 0 : assert(tsize >= minsize_for_tree_index(idx));
2708 0 : assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));
2709 :
2710 : do { /* traverse through chain of same-sized nodes */
2711 0 : do_check_any_chunk(m, ((mchunkptr)u));
2712 0 : assert(u->index == tindex);
2713 0 : assert(chunksize(u) == tsize);
2714 0 : assert(!cinuse(u));
2715 0 : assert(!next_pinuse(u));
2716 0 : assert(u->fd->bk == u);
2717 0 : assert(u->bk->fd == u);
2718 0 : if (u->parent == 0) {
2719 0 : assert(u->child[0] == 0);
2720 0 : assert(u->child[1] == 0);
2721 : }
2722 : else {
2723 0 : assert(head == 0); /* only one node on chain has parent */
2724 0 : head = u;
2725 0 : assert(u->parent != u);
2726 0 : assert (u->parent->child[0] == u ||
2727 : u->parent->child[1] == u ||
2728 : *((tbinptr*)(u->parent)) == u);
2729 0 : if (u->child[0] != 0) {
2730 0 : assert(u->child[0]->parent == u);
2731 0 : assert(u->child[0] != u);
2732 0 : do_check_tree(m, u->child[0]);
2733 : }
2734 0 : if (u->child[1] != 0) {
2735 0 : assert(u->child[1]->parent == u);
2736 0 : assert(u->child[1] != u);
2737 0 : do_check_tree(m, u->child[1]);
2738 : }
2739 0 : if (u->child[0] != 0 && u->child[1] != 0) {
2740 0 : assert(chunksize(u->child[0]) < chunksize(u->child[1]));
2741 : }
2742 : }
2743 0 : u = u->fd;
2744 0 : } while (u != t);
2745 0 : assert(head != 0);
2746 0 : }
2747 :
2748 : /* Check all the chunks in a treebin. */
2749 0 : static void do_check_treebin(mstate m, bindex_t i) {
2750 0 : tbinptr* tb = treebin_at(m, i);
2751 0 : tchunkptr t = *tb;
2752 0 : int empty = (m->treemap & (1U << i)) == 0;
2753 0 : if (t == 0)
2754 0 : assert(empty);
2755 0 : if (!empty)
2756 0 : do_check_tree(m, t);
2757 0 : }
2758 :
2759 : /* Check all the chunks in a smallbin. */
2760 0 : static void do_check_smallbin(mstate m, bindex_t i) {
2761 0 : sbinptr b = smallbin_at(m, i);
2762 0 : mchunkptr p = b->bk;
2763 0 : unsigned int empty = (m->smallmap & (1U << i)) == 0;
2764 0 : if (p == b)
2765 0 : assert(empty);
2766 0 : if (!empty) {
2767 0 : for (; p != b; p = p->bk) {
2768 0 : size_t size = chunksize(p);
2769 : mchunkptr q;
2770 : /* each chunk claims to be free */
2771 0 : do_check_free_chunk(m, p);
2772 : /* chunk belongs in bin */
2773 0 : assert(small_index(size) == i);
2774 0 : assert(p->bk == b || chunksize(p->bk) == chunksize(p));
2775 : /* chunk is followed by an inuse chunk */
2776 0 : q = next_chunk(p);
2777 0 : if (q->head != FENCEPOST_HEAD)
2778 0 : do_check_inuse_chunk(m, q);
2779 : }
2780 : }
2781 0 : }
2782 :
2783 : /* Find x in a bin. Used in other check functions. */
2784 0 : static int bin_find(mstate m, mchunkptr x) {
2785 0 : size_t size = chunksize(x);
2786 0 : if (is_small(size)) {
2787 0 : bindex_t sidx = small_index(size);
2788 0 : sbinptr b = smallbin_at(m, sidx);
2789 0 : if (smallmap_is_marked(m, sidx)) {
2790 0 : mchunkptr p = b;
2791 : do {
2792 0 : if (p == x)
2793 0 : return 1;
2794 0 : } while ((p = p->fd) != b);
2795 : }
2796 : }
2797 : else {
2798 : bindex_t tidx;
2799 0 : compute_tree_index(size, tidx);
2800 0 : if (treemap_is_marked(m, tidx)) {
2801 0 : tchunkptr t = *treebin_at(m, tidx);
2802 0 : size_t sizebits = size << leftshift_for_tree_index(tidx);
2803 0 : while (t != 0 && chunksize(t) != size) {
2804 0 : t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
2805 0 : sizebits <<= 1;
2806 : }
2807 0 : if (t != 0) {
2808 0 : tchunkptr u = t;
2809 : do {
2810 0 : if (u == (tchunkptr)x)
2811 0 : return 1;
2812 0 : } while ((u = u->fd) != t);
2813 : }
2814 : }
2815 : }
2816 0 : return 0;
2817 : }
2818 :
2819 : /* Traverse each chunk and check it; return total */
2820 0 : static size_t traverse_and_check(mstate m) {
2821 0 : size_t sum = 0;
2822 0 : if (is_initialized(m)) {
2823 0 : msegmentptr s = &m->seg;
2824 0 : sum += m->topsize + TOP_FOOT_SIZE;
2825 0 : while (s != 0) {
2826 0 : mchunkptr q = align_as_chunk(s->base);
2827 0 : mchunkptr lastq = 0;
2828 0 : assert(pinuse(q));
2829 0 : while (segment_holds(s, q) &&
2830 0 : q != m->top && q->head != FENCEPOST_HEAD) {
2831 0 : sum += chunksize(q);
2832 0 : if (cinuse(q)) {
2833 0 : assert(!bin_find(m, q));
2834 0 : do_check_inuse_chunk(m, q);
2835 : }
2836 : else {
2837 0 : assert(q == m->dv || bin_find(m, q));
2838 0 : assert(lastq == 0 || cinuse(lastq)); /* Not 2 consecutive free */
2839 0 : do_check_free_chunk(m, q);
2840 : }
2841 0 : lastq = q;
2842 0 : q = next_chunk(q);
2843 : }
2844 0 : s = s->next;
2845 : }
2846 : }
2847 0 : return sum;
2848 : }
2849 :
2850 : /* Check all properties of malloc_state. */
2851 0 : static void do_check_malloc_state(mstate m) {
2852 : bindex_t i;
2853 : size_t total;
2854 : /* check bins */
2855 0 : for (i = 0; i < NSMALLBINS; ++i)
2856 0 : do_check_smallbin(m, i);
2857 0 : for (i = 0; i < NTREEBINS; ++i)
2858 0 : do_check_treebin(m, i);
2859 :
2860 0 : if (m->dvsize != 0) { /* check dv chunk */
2861 0 : do_check_any_chunk(m, m->dv);
2862 0 : assert(m->dvsize == chunksize(m->dv));
2863 0 : assert(m->dvsize >= MIN_CHUNK_SIZE);
2864 0 : assert(bin_find(m, m->dv) == 0);
2865 : }
2866 :
2867 0 : if (m->top != 0) { /* check top chunk */
2868 0 : do_check_top_chunk(m, m->top);
2869 0 : assert(m->topsize == chunksize(m->top));
2870 0 : assert(m->topsize > 0);
2871 0 : assert(bin_find(m, m->top) == 0);
2872 : }
2873 :
2874 0 : total = traverse_and_check(m);
2875 0 : assert(total <= m->footprint);
2876 0 : assert(m->footprint <= m->max_footprint);
2877 0 : }
2878 : #endif /* DEBUG */
2879 :
2880 : /* ----------------------------- statistics ------------------------------ */
2881 :
2882 : #if !NO_MALLINFO
2883 : static struct mallinfo internal_mallinfo(mstate m) {
2884 : struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
2885 : if (!PREACTION(m)) {
2886 : check_malloc_state(m);
2887 : if (is_initialized(m)) {
2888 : size_t nfree = SIZE_T_ONE; /* top always free */
2889 : size_t mfree = m->topsize + TOP_FOOT_SIZE;
2890 : size_t sum = mfree;
2891 : msegmentptr s = &m->seg;
2892 : while (s != 0) {
2893 : mchunkptr q = align_as_chunk(s->base);
2894 : while (segment_holds(s, q) &&
2895 : q != m->top && q->head != FENCEPOST_HEAD) {
2896 : size_t sz = chunksize(q);
2897 : sum += sz;
2898 : if (!cinuse(q)) {
2899 : mfree += sz;
2900 : ++nfree;
2901 : }
2902 : q = next_chunk(q);
2903 : }
2904 : s = s->next;
2905 : }
2906 :
2907 : nm.arena = sum;
2908 : nm.ordblks = nfree;
2909 : nm.hblkhd = m->footprint - sum;
2910 : nm.usmblks = m->max_footprint;
2911 : nm.uordblks = m->footprint - mfree;
2912 : nm.fordblks = mfree;
2913 : nm.keepcost = m->topsize;
2914 : }
2915 :
2916 : POSTACTION(m);
2917 : }
2918 : return nm;
2919 : }
2920 : #endif /* !NO_MALLINFO */
2921 :
2922 0 : static void internal_malloc_stats(mstate m) {
2923 0 : if (!PREACTION(m)) {
2924 0 : size_t maxfp = 0;
2925 0 : size_t fp = 0;
2926 0 : size_t used = 0;
2927 0 : check_malloc_state(m);
2928 0 : if (is_initialized(m)) {
2929 0 : msegmentptr s = &m->seg;
2930 0 : maxfp = m->max_footprint;
2931 0 : fp = m->footprint;
2932 0 : used = fp - (m->topsize + TOP_FOOT_SIZE);
2933 :
2934 0 : while (s != 0) {
2935 0 : mchunkptr q = align_as_chunk(s->base);
2936 0 : while (segment_holds(s, q) &&
2937 0 : q != m->top && q->head != FENCEPOST_HEAD) {
2938 0 : if (!cinuse(q))
2939 0 : used -= chunksize(q);
2940 0 : q = next_chunk(q);
2941 : }
2942 0 : s = s->next;
2943 : }
2944 : }
2945 :
2946 0 : fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));
2947 0 : fprintf(stderr, "system bytes = %10lu\n", (unsigned long)(fp));
2948 0 : fprintf(stderr, "in use bytes = %10lu\n", (unsigned long)(used));
2949 :
2950 0 : POSTACTION(m);
2951 : }
2952 0 : }
2953 :
2954 : /* ----------------------- Operations on smallbins ----------------------- */
2955 :
2956 : /*
2957 : Various forms of linking and unlinking are defined as macros. Even
2958 : the ones for trees, which are very long but have very short typical
2959 : paths. This is ugly but reduces reliance on inlining support of
2960 : compilers.
2961 : */
2962 :
2963 : /* Link a free chunk into a smallbin */
2964 : #define insert_small_chunk(M, P, S) {\
2965 : bindex_t I = small_index(S);\
2966 : mchunkptr B = smallbin_at(M, I);\
2967 : mchunkptr F = B;\
2968 : assert(S >= MIN_CHUNK_SIZE);\
2969 : if (!smallmap_is_marked(M, I))\
2970 : mark_smallmap(M, I);\
2971 : else if (RTCHECK(ok_address(M, B->fd)))\
2972 : F = B->fd;\
2973 : else {\
2974 : CORRUPTION_ERROR_ACTION(M);\
2975 : }\
2976 : B->fd = P;\
2977 : F->bk = P;\
2978 : P->fd = F;\
2979 : P->bk = B;\
2980 : }
2981 :
2982 : /* Unlink a chunk from a smallbin */
2983 : #define unlink_small_chunk(M, P, S) {\
2984 : mchunkptr F = P->fd;\
2985 : mchunkptr B = P->bk;\
2986 : bindex_t I = small_index(S);\
2987 : assert(P != B);\
2988 : assert(P != F);\
2989 : assert(chunksize(P) == small_index2size(I));\
2990 : if (F == B)\
2991 : clear_smallmap(M, I);\
2992 : else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\
2993 : (B == smallbin_at(M,I) || ok_address(M, B)))) {\
2994 : F->bk = B;\
2995 : B->fd = F;\
2996 : }\
2997 : else {\
2998 : CORRUPTION_ERROR_ACTION(M);\
2999 : }\
3000 : }
3001 :
3002 : /* Unlink the first chunk from a smallbin */
3003 : #define unlink_first_small_chunk(M, B, P, I) {\
3004 : mchunkptr F = P->fd;\
3005 : assert(P != B);\
3006 : assert(P != F);\
3007 : assert(chunksize(P) == small_index2size(I));\
3008 : if (B == F)\
3009 : clear_smallmap(M, I);\
3010 : else if (RTCHECK(ok_address(M, F))) {\
3011 : B->fd = F;\
3012 : F->bk = B;\
3013 : }\
3014 : else {\
3015 : CORRUPTION_ERROR_ACTION(M);\
3016 : }\
3017 : }
3018 :
3019 : /* Replace dv node, binning the old one */
3020 : /* Used only when dvsize known to be small */
3021 : #define replace_dv(M, P, S) {\
3022 : size_t DVS = M->dvsize;\
3023 : if (DVS != 0) {\
3024 : mchunkptr DV = M->dv;\
3025 : assert(is_small(DVS));\
3026 : insert_small_chunk(M, DV, DVS);\
3027 : }\
3028 : M->dvsize = S;\
3029 : M->dv = P;\
3030 : }
3031 :
3032 : /* ------------------------- Operations on trees ------------------------- */
3033 :
3034 : /* Insert chunk into tree */
3035 : #define insert_large_chunk(M, X, S) {\
3036 : tbinptr* H;\
3037 : bindex_t I;\
3038 : compute_tree_index(S, I);\
3039 : H = treebin_at(M, I);\
3040 : X->index = I;\
3041 : X->child[0] = X->child[1] = 0;\
3042 : if (!treemap_is_marked(M, I)) {\
3043 : mark_treemap(M, I);\
3044 : *H = X;\
3045 : X->parent = (tchunkptr)H;\
3046 : X->fd = X->bk = X;\
3047 : }\
3048 : else {\
3049 : tchunkptr T = *H;\
3050 : size_t K = S << leftshift_for_tree_index(I);\
3051 : for (;;) {\
3052 : if (chunksize(T) != S) {\
3053 : tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\
3054 : K <<= 1;\
3055 : if (*C != 0)\
3056 : T = *C;\
3057 : else if (RTCHECK(ok_address(M, C))) {\
3058 : *C = X;\
3059 : X->parent = T;\
3060 : X->fd = X->bk = X;\
3061 : break;\
3062 : }\
3063 : else {\
3064 : CORRUPTION_ERROR_ACTION(M);\
3065 : break;\
3066 : }\
3067 : }\
3068 : else {\
3069 : tchunkptr F = T->fd;\
3070 : if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
3071 : T->fd = F->bk = X;\
3072 : X->fd = F;\
3073 : X->bk = T;\
3074 : X->parent = 0;\
3075 : break;\
3076 : }\
3077 : else {\
3078 : CORRUPTION_ERROR_ACTION(M);\
3079 : break;\
3080 : }\
3081 : }\
3082 : }\
3083 : }\
3084 : }
3085 :
3086 : /*
3087 : Unlink steps:
3088 :
3089 : 1. If x is a chained node, unlink it from its same-sized fd/bk links
3090 : and choose its bk node as its replacement.
3091 : 2. If x was the last node of its size, but not a leaf node, it must
3092 : be replaced with a leaf node (not merely one with an open left or
3093 : right), to make sure that lefts and rights of descendants
3094 : correspond properly to bit masks. We use the rightmost descendant
3095 : of x. We could use any other leaf, but this is easy to locate and
3096 : tends to counteract removal of leftmosts elsewhere, and so keeps
3097 : paths shorter than minimally guaranteed. This doesn't loop much
3098 : because on average a node in a tree is near the bottom.
3099 : 3. If x is the base of a chain (i.e., has parent links) relink
3100 : x's parent and children to x's replacement (or null if none).
3101 : */
3102 :
3103 : #define unlink_large_chunk(M, X) {\
3104 : tchunkptr XP = X->parent;\
3105 : tchunkptr R;\
3106 : if (X->bk != X) {\
3107 : tchunkptr F = X->fd;\
3108 : R = X->bk;\
3109 : if (RTCHECK(ok_address(M, F))) {\
3110 : F->bk = R;\
3111 : R->fd = F;\
3112 : }\
3113 : else {\
3114 : CORRUPTION_ERROR_ACTION(M);\
3115 : }\
3116 : }\
3117 : else {\
3118 : tchunkptr* RP;\
3119 : if (((R = *(RP = &(X->child[1]))) != 0) ||\
3120 : ((R = *(RP = &(X->child[0]))) != 0)) {\
3121 : tchunkptr* CP;\
3122 : while ((*(CP = &(R->child[1])) != 0) ||\
3123 : (*(CP = &(R->child[0])) != 0)) {\
3124 : R = *(RP = CP);\
3125 : }\
3126 : if (RTCHECK(ok_address(M, RP)))\
3127 : *RP = 0;\
3128 : else {\
3129 : CORRUPTION_ERROR_ACTION(M);\
3130 : }\
3131 : }\
3132 : }\
3133 : if (XP != 0) {\
3134 : tbinptr* H = treebin_at(M, X->index);\
3135 : if (X == *H) {\
3136 : if ((*H = R) == 0) \
3137 : clear_treemap(M, X->index);\
3138 : }\
3139 : else if (RTCHECK(ok_address(M, XP))) {\
3140 : if (XP->child[0] == X) \
3141 : XP->child[0] = R;\
3142 : else \
3143 : XP->child[1] = R;\
3144 : }\
3145 : else\
3146 : CORRUPTION_ERROR_ACTION(M);\
3147 : if (R != 0) {\
3148 : if (RTCHECK(ok_address(M, R))) {\
3149 : tchunkptr C0, C1;\
3150 : R->parent = XP;\
3151 : if ((C0 = X->child[0]) != 0) {\
3152 : if (RTCHECK(ok_address(M, C0))) {\
3153 : R->child[0] = C0;\
3154 : C0->parent = R;\
3155 : }\
3156 : else\
3157 : CORRUPTION_ERROR_ACTION(M);\
3158 : }\
3159 : if ((C1 = X->child[1]) != 0) {\
3160 : if (RTCHECK(ok_address(M, C1))) {\
3161 : R->child[1] = C1;\
3162 : C1->parent = R;\
3163 : }\
3164 : else\
3165 : CORRUPTION_ERROR_ACTION(M);\
3166 : }\
3167 : }\
3168 : else\
3169 : CORRUPTION_ERROR_ACTION(M);\
3170 : }\
3171 : }\
3172 : }
3173 :
3174 : /* Relays to large vs small bin operations */
3175 :
3176 : #define insert_chunk(M, P, S)\
3177 : if (is_small(S)) insert_small_chunk(M, P, S)\
3178 : else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }
3179 :
3180 : #define unlink_chunk(M, P, S)\
3181 : if (is_small(S)) unlink_small_chunk(M, P, S)\
3182 : else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }
3183 :
3184 :
3185 : /* Relays to internal calls to malloc/free from realloc, memalign etc */
3186 :
3187 : #if ONLY_MSPACES
3188 : #define internal_malloc(m, b) mspace_malloc(m, b)
3189 : #define internal_free(m, mem) mspace_free(m,mem);
3190 : #else /* ONLY_MSPACES */
3191 : #if MSPACES
3192 : #define internal_malloc(m, b)\
3193 : (m == gm)? dlmalloc(b) : mspace_malloc(m, b)
3194 : #define internal_free(m, mem)\
3195 : if (m == gm) dlfree(mem); else mspace_free(m,mem);
3196 : #else /* MSPACES */
3197 : #define internal_malloc(m, b) dlmalloc(b)
3198 : #define internal_free(m, mem) dlfree(mem)
3199 : #endif /* MSPACES */
3200 : #endif /* ONLY_MSPACES */
3201 :
3202 : /* ----------------------- Direct-mmapping chunks ----------------------- */
3203 :
3204 : /*
3205 : Directly mmapped chunks are set up with an offset to the start of
3206 : the mmapped region stored in the prev_foot field of the chunk. This
3207 : allows reconstruction of the required argument to MUNMAP when freed,
3208 : and also allows adjustment of the returned chunk to meet alignment
3209 : requirements (especially in memalign). There is also enough space
3210 : allocated to hold a fake next chunk of size SIZE_T_SIZE to maintain
3211 : the PINUSE bit so frees can be checked.
3212 : */
3213 :
3214 : /* Malloc using mmap */
3215 0 : static void* mmap_alloc(mstate m, size_t nb) {
3216 0 : size_t mmsize = granularity_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3217 0 : if (mmsize > nb) { /* Check for wrap around 0 */
3218 0 : char* mm = (char*)(DIRECT_MMAP(mmsize));
3219 0 : if (mm != CMFAIL) {
3220 0 : size_t offset = align_offset(chunk2mem(mm));
3221 0 : size_t psize = mmsize - offset - MMAP_FOOT_PAD;
3222 0 : mchunkptr p = (mchunkptr)(mm + offset);
3223 0 : p->prev_foot = offset | IS_MMAPPED_BIT;
3224 0 : (p)->head = (psize|CINUSE_BIT);
3225 : mark_inuse_foot(m, p, psize);
3226 0 : chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;
3227 0 : chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;
3228 :
3229 0 : if (mm < m->least_addr)
3230 0 : m->least_addr = mm;
3231 0 : if ((m->footprint += mmsize) > m->max_footprint)
3232 0 : m->max_footprint = m->footprint;
3233 0 : assert(is_aligned(chunk2mem(p)));
3234 0 : check_mmapped_chunk(m, p);
3235 0 : return chunk2mem(p);
3236 : }
3237 : }
3238 0 : return 0;
3239 : }
3240 :
3241 : /* Realloc using mmap */
3242 0 : static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) {
3243 0 : size_t oldsize = chunksize(oldp);
3244 0 : if (is_small(nb)) /* Can't shrink mmap regions below small size */
3245 0 : return 0;
3246 : /* Keep old chunk if big enough but not too big */
3247 0 : if (oldsize >= nb + SIZE_T_SIZE &&
3248 0 : (oldsize - nb) <= (mparams.granularity << 1))
3249 0 : return oldp;
3250 : else {
3251 0 : size_t offset = oldp->prev_foot & ~IS_MMAPPED_BIT;
3252 0 : size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;
3253 0 : size_t newmmsize = granularity_align(nb + SIX_SIZE_T_SIZES +
3254 : CHUNK_ALIGN_MASK);
3255 0 : char* cp = (char*)CALL_MREMAP((char*)oldp - offset,
3256 : oldmmsize, newmmsize, 1);
3257 0 : if (cp != CMFAIL) {
3258 0 : mchunkptr newp = (mchunkptr)(cp + offset);
3259 0 : size_t psize = newmmsize - offset - MMAP_FOOT_PAD;
3260 0 : newp->head = (psize|CINUSE_BIT);
3261 : mark_inuse_foot(m, newp, psize);
3262 0 : chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;
3263 0 : chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;
3264 :
3265 0 : if (cp < m->least_addr)
3266 0 : m->least_addr = cp;
3267 0 : if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)
3268 0 : m->max_footprint = m->footprint;
3269 0 : check_mmapped_chunk(m, newp);
3270 0 : return newp;
3271 : }
3272 : }
3273 0 : return 0;
3274 : }
3275 :
3276 : /* -------------------------- mspace management -------------------------- */
3277 :
3278 : /* Initialize top chunk and its size */
3279 0 : static void init_top(mstate m, mchunkptr p, size_t psize) {
3280 : /* Ensure alignment */
3281 0 : size_t offset = align_offset(chunk2mem(p));
3282 0 : p = (mchunkptr)((char*)p + offset);
3283 0 : psize -= offset;
3284 :
3285 0 : m->top = p;
3286 0 : m->topsize = psize;
3287 0 : p->head = psize | PINUSE_BIT;
3288 : /* set size of fake trailing chunk holding overhead space only once */
3289 0 : chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;
3290 0 : m->trim_check = mparams.trim_threshold; /* reset on each update */
3291 0 : }
3292 :
3293 : /* Initialize bins for a new mstate that is otherwise zeroed out */
3294 0 : static void init_bins(mstate m) {
3295 : /* Establish circular links for smallbins */
3296 : bindex_t i;
3297 0 : for (i = 0; i < NSMALLBINS; ++i) {
3298 0 : sbinptr bin = smallbin_at(m,i);
3299 0 : bin->fd = bin->bk = bin;
3300 : }
3301 0 : }
3302 :
3303 : #if PROCEED_ON_ERROR
3304 :
3305 : /* default corruption action */
3306 : static void reset_on_error(mstate m) {
3307 : int i;
3308 : ++malloc_corruption_error_count;
3309 : /* Reinitialize fields to forget about all memory */
3310 : m->smallbins = m->treebins = 0;
3311 : m->dvsize = m->topsize = 0;
3312 : m->seg.base = 0;
3313 : m->seg.size = 0;
3314 : m->seg.next = 0;
3315 : m->top = m->dv = 0;
3316 : for (i = 0; i < NTREEBINS; ++i)
3317 : *treebin_at(m, i) = 0;
3318 : init_bins(m);
3319 : }
3320 : #endif /* PROCEED_ON_ERROR */
3321 :
3322 : /* Allocate chunk and prepend remainder with chunk in successor base. */
3323 0 : static void* prepend_alloc(mstate m, char* newbase, char* oldbase,
3324 : size_t nb) {
3325 0 : mchunkptr p = align_as_chunk(newbase);
3326 0 : mchunkptr oldfirst = align_as_chunk(oldbase);
3327 0 : size_t psize = (char*)oldfirst - (char*)p;
3328 0 : mchunkptr q = chunk_plus_offset(p, nb);
3329 0 : size_t qsize = psize - nb;
3330 0 : set_size_and_pinuse_of_inuse_chunk(m, p, nb);
3331 :
3332 0 : assert((char*)oldfirst > (char*)q);
3333 0 : assert(pinuse(oldfirst));
3334 0 : assert(qsize >= MIN_CHUNK_SIZE);
3335 :
3336 : /* consolidate remainder with first chunk of old base */
3337 0 : if (oldfirst == m->top) {
3338 0 : size_t tsize = m->topsize += qsize;
3339 0 : m->top = q;
3340 0 : q->head = tsize | PINUSE_BIT;
3341 0 : check_top_chunk(m, q);
3342 : }
3343 0 : else if (oldfirst == m->dv) {
3344 0 : size_t dsize = m->dvsize += qsize;
3345 0 : m->dv = q;
3346 0 : set_size_and_pinuse_of_free_chunk(q, dsize);
3347 : }
3348 : else {
3349 0 : if (!cinuse(oldfirst)) {
3350 0 : size_t nsize = chunksize(oldfirst);
3351 0 : unlink_chunk(m, oldfirst, nsize);
3352 0 : oldfirst = chunk_plus_offset(oldfirst, nsize);
3353 0 : qsize += nsize;
3354 : }
3355 0 : set_free_with_pinuse(q, qsize, oldfirst);
3356 0 : insert_chunk(m, q, qsize);
3357 0 : check_free_chunk(m, q);
3358 : }
3359 :
3360 0 : check_malloced_chunk(m, chunk2mem(p), nb);
3361 0 : return chunk2mem(p);
3362 : }
3363 :
3364 :
3365 : /* Add a segment to hold a new noncontiguous region */
3366 0 : static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {
3367 : /* Determine locations and sizes of segment, fenceposts, old top */
3368 0 : char* old_top = (char*)m->top;
3369 0 : msegmentptr oldsp = segment_holding(m, old_top);
3370 0 : char* old_end = oldsp->base + oldsp->size;
3371 0 : size_t ssize = pad_request(sizeof(struct malloc_segment));
3372 0 : char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);
3373 0 : size_t offset = align_offset(chunk2mem(rawsp));
3374 0 : char* asp = rawsp + offset;
3375 0 : char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;
3376 0 : mchunkptr sp = (mchunkptr)csp;
3377 0 : msegmentptr ss = (msegmentptr)(chunk2mem(sp));
3378 0 : mchunkptr tnext = chunk_plus_offset(sp, ssize);
3379 0 : mchunkptr p = tnext;
3380 0 : int nfences = 0;
3381 :
3382 : /* reset top to new space */
3383 0 : init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
3384 :
3385 : /* Set up segment record */
3386 0 : assert(is_aligned(ss));
3387 0 : set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);
3388 0 : *ss = m->seg; /* Push current record */
3389 0 : m->seg.base = tbase;
3390 0 : m->seg.size = tsize;
3391 0 : (void)set_segment_flags(&m->seg, mmapped);
3392 0 : m->seg.next = ss;
3393 :
3394 : /* Insert trailing fenceposts */
3395 0 : for (;;) {
3396 0 : mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);
3397 0 : p->head = FENCEPOST_HEAD;
3398 0 : ++nfences;
3399 0 : if ((char*)(&(nextp->head)) < old_end)
3400 0 : p = nextp;
3401 : else
3402 0 : break;
3403 : }
3404 0 : assert(nfences >= 2);
3405 :
3406 : /* Insert the rest of old top into a bin as an ordinary free chunk */
3407 0 : if (csp != old_top) {
3408 0 : mchunkptr q = (mchunkptr)old_top;
3409 0 : size_t psize = csp - old_top;
3410 0 : mchunkptr tn = chunk_plus_offset(q, psize);
3411 0 : set_free_with_pinuse(q, psize, tn);
3412 0 : insert_chunk(m, q, psize);
3413 : }
3414 :
3415 0 : check_top_chunk(m, m->top);
3416 0 : }
3417 :
3418 : /* -------------------------- System allocation -------------------------- */
3419 :
3420 : /* Get memory from system using MORECORE or MMAP */
3421 0 : static void* sys_alloc(mstate m, size_t nb) {
3422 0 : char* tbase = CMFAIL;
3423 0 : size_t tsize = 0;
3424 0 : flag_t mmap_flag = 0;
3425 :
3426 0 : init_mparams();
3427 :
3428 : /* Directly map large chunks */
3429 0 : if (use_mmap(m) && nb >= mparams.mmap_threshold) {
3430 0 : void* mem = mmap_alloc(m, nb);
3431 0 : if (mem != 0)
3432 0 : return mem;
3433 : }
3434 :
3435 : /*
3436 : Try getting memory in any of three ways (in most-preferred to
3437 : least-preferred order):
3438 : 1. A call to MORECORE that can normally contiguously extend memory.
3439 : (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or
3440 : or main space is mmapped or a previous contiguous call failed)
3441 : 2. A call to MMAP new space (disabled if not HAVE_MMAP).
3442 : Note that under the default settings, if MORECORE is unable to
3443 : fulfill a request, and HAVE_MMAP is true, then mmap is
3444 : used as a noncontiguous system allocator. This is a useful backup
3445 : strategy for systems with holes in address spaces -- in this case
3446 : sbrk cannot contiguously expand the heap, but mmap may be able to
3447 : find space.
3448 : 3. A call to MORECORE that cannot usually contiguously extend memory.
3449 : (disabled if not HAVE_MORECORE)
3450 : */
3451 :
3452 : if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
3453 : char* br = CMFAIL;
3454 : msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
3455 : size_t asize = 0;
3456 : ACQUIRE_MORECORE_LOCK();
3457 :
3458 : if (ss == 0) { /* First time through or recovery */
3459 : char* base = (char*)CALL_MORECORE(0);
3460 : if (base != CMFAIL) {
3461 : asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
3462 : /* Adjust to end on a page boundary */
3463 : if (!is_page_aligned(base))
3464 : asize += (page_align((size_t)base) - (size_t)base);
3465 : /* Can't call MORECORE if size is negative when treated as signed */
3466 : if (asize < HALF_MAX_SIZE_T &&
3467 : (br = (char*)(CALL_MORECORE(asize))) == base) {
3468 : tbase = base;
3469 : tsize = asize;
3470 : }
3471 : }
3472 : }
3473 : else {
3474 : /* Subtract out existing available top space from MORECORE request. */
3475 : asize = granularity_align(nb - m->topsize + TOP_FOOT_SIZE + SIZE_T_ONE);
3476 : /* Use mem here only if it did continuously extend old space */
3477 : if (asize < HALF_MAX_SIZE_T &&
3478 : (br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {
3479 : tbase = br;
3480 : tsize = asize;
3481 : }
3482 : }
3483 :
3484 : if (tbase == CMFAIL) { /* Cope with partial failure */
3485 : if (br != CMFAIL) { /* Try to use/extend the space we did get */
3486 : if (asize < HALF_MAX_SIZE_T &&
3487 : asize < nb + TOP_FOOT_SIZE + SIZE_T_ONE) {
3488 : size_t esize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE - asize);
3489 : if (esize < HALF_MAX_SIZE_T) {
3490 : char* end = (char*)CALL_MORECORE(esize);
3491 : if (end != CMFAIL)
3492 : asize += esize;
3493 : else { /* Can't use; try to release */
3494 : (void)CALL_MORECORE(-asize);
3495 : br = CMFAIL;
3496 : }
3497 : }
3498 : }
3499 : }
3500 : if (br != CMFAIL) { /* Use the space we did get */
3501 : tbase = br;
3502 : tsize = asize;
3503 : }
3504 : else
3505 : disable_contiguous(m); /* Don't try contiguous path in the future */
3506 : }
3507 :
3508 : RELEASE_MORECORE_LOCK();
3509 : }
3510 :
3511 0 : if (HAVE_MMAP && tbase == CMFAIL) { /* Try MMAP */
3512 0 : size_t req = nb + TOP_FOOT_SIZE + SIZE_T_ONE;
3513 0 : size_t rsize = granularity_align(req);
3514 0 : if (rsize > nb) { /* Fail if wraps around zero */
3515 0 : char* mp = (char*)(CALL_MMAP(rsize));
3516 0 : if (mp != CMFAIL) {
3517 0 : tbase = mp;
3518 0 : tsize = rsize;
3519 0 : mmap_flag = IS_MMAPPED_BIT;
3520 : }
3521 : }
3522 : }
3523 :
3524 : if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
3525 : size_t asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);
3526 : if (asize < HALF_MAX_SIZE_T) {
3527 : char* br = CMFAIL;
3528 : char* end = CMFAIL;
3529 : ACQUIRE_MORECORE_LOCK();
3530 : br = (char*)(CALL_MORECORE(asize));
3531 : end = (char*)(CALL_MORECORE(0));
3532 : RELEASE_MORECORE_LOCK();
3533 : if (br != CMFAIL && end != CMFAIL && br < end) {
3534 : size_t ssize = end - br;
3535 : if (ssize > nb + TOP_FOOT_SIZE) {
3536 : tbase = br;
3537 : tsize = ssize;
3538 : }
3539 : }
3540 : }
3541 : }
3542 :
3543 0 : if (tbase != CMFAIL) {
3544 :
3545 0 : if ((m->footprint += tsize) > m->max_footprint)
3546 0 : m->max_footprint = m->footprint;
3547 :
3548 0 : if (!is_initialized(m)) { /* first-time initialization */
3549 0 : m->seg.base = m->least_addr = tbase;
3550 0 : m->seg.size = tsize;
3551 0 : (void)set_segment_flags(&m->seg, mmap_flag);
3552 0 : m->magic = mparams.magic;
3553 0 : init_bins(m);
3554 0 : if (is_global(m))
3555 0 : init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
3556 : else {
3557 : /* Offset top by embedded malloc_state */
3558 0 : mchunkptr mn = next_chunk(mem2chunk(m));
3559 0 : init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
3560 : }
3561 : }
3562 :
3563 : else {
3564 : /* Try to merge with an existing segment */
3565 0 : msegmentptr sp = &m->seg;
3566 0 : while (sp != 0 && tbase != sp->base + sp->size)
3567 0 : sp = sp->next;
3568 0 : if (sp != 0 &&
3569 0 : !is_extern_segment(sp) &&
3570 0 : check_segment_merge(sp, tbase, tsize) &&
3571 0 : (get_segment_flags(sp) & IS_MMAPPED_BIT) == mmap_flag &&
3572 0 : segment_holds(sp, m->top)) { /* append */
3573 0 : sp->size += tsize;
3574 0 : init_top(m, m->top, m->topsize + tsize);
3575 : }
3576 : else {
3577 0 : if (tbase < m->least_addr)
3578 0 : m->least_addr = tbase;
3579 0 : sp = &m->seg;
3580 0 : while (sp != 0 && sp->base != tbase + tsize)
3581 0 : sp = sp->next;
3582 0 : if (sp != 0 &&
3583 0 : !is_extern_segment(sp) &&
3584 0 : check_segment_merge(sp, tbase, tsize) &&
3585 : (get_segment_flags(sp) & IS_MMAPPED_BIT) == mmap_flag) {
3586 0 : char* oldbase = sp->base;
3587 0 : sp->base = tbase;
3588 0 : sp->size += tsize;
3589 0 : return prepend_alloc(m, tbase, oldbase, nb);
3590 : }
3591 : else
3592 0 : add_segment(m, tbase, tsize, mmap_flag);
3593 : }
3594 : }
3595 :
3596 0 : if (nb < m->topsize) { /* Allocate from new or extended top space */
3597 0 : size_t rsize = m->topsize -= nb;
3598 0 : mchunkptr p = m->top;
3599 0 : mchunkptr r = m->top = chunk_plus_offset(p, nb);
3600 0 : r->head = rsize | PINUSE_BIT;
3601 0 : set_size_and_pinuse_of_inuse_chunk(m, p, nb);
3602 0 : check_top_chunk(m, m->top);
3603 0 : check_malloced_chunk(m, chunk2mem(p), nb);
3604 0 : return chunk2mem(p);
3605 : }
3606 : }
3607 :
3608 0 : MALLOC_FAILURE_ACTION;
3609 0 : return 0;
3610 : }
3611 :
3612 : /* ----------------------- system deallocation -------------------------- */
3613 :
3614 : /* Unmap and unlink any mmapped segments that don't contain used chunks */
3615 0 : static size_t release_unused_segments(mstate m) {
3616 0 : size_t released = 0;
3617 0 : msegmentptr pred = &m->seg;
3618 0 : msegmentptr sp = pred->next;
3619 0 : while (sp != 0) {
3620 0 : char* base = sp->base;
3621 0 : size_t size = sp->size;
3622 0 : msegmentptr next = sp->next;
3623 : if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {
3624 0 : mchunkptr p = align_as_chunk(base);
3625 0 : size_t psize = chunksize(p);
3626 : /* Can unmap if first chunk holds entire segment and not pinned */
3627 0 : if (!cinuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {
3628 0 : tchunkptr tp = (tchunkptr)p;
3629 0 : assert(segment_holds(sp, (char*)sp));
3630 0 : if (p == m->dv) {
3631 0 : m->dv = 0;
3632 0 : m->dvsize = 0;
3633 : }
3634 : else {
3635 0 : unlink_large_chunk(m, tp);
3636 : }
3637 0 : if (CALL_MUNMAP(base, size) == 0) {
3638 0 : released += size;
3639 0 : m->footprint -= size;
3640 : /* unlink obsoleted record */
3641 0 : sp = pred;
3642 0 : sp->next = next;
3643 : }
3644 : else { /* back out if cannot unmap */
3645 0 : insert_large_chunk(m, tp, psize);
3646 : }
3647 : }
3648 : }
3649 0 : pred = sp;
3650 0 : sp = next;
3651 : }
3652 0 : return released;
3653 : }
3654 :
3655 0 : static int sys_trim(mstate m, size_t pad) {
3656 0 : size_t released = 0;
3657 0 : if (pad < MAX_REQUEST && is_initialized(m)) {
3658 0 : pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */
3659 :
3660 0 : if (m->topsize > pad) {
3661 : /* Shrink top space in granularity-size units, keeping at least one */
3662 0 : size_t unit = mparams.granularity;
3663 0 : size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -
3664 : SIZE_T_ONE) * unit;
3665 0 : msegmentptr sp = segment_holding(m, (char*)m->top);
3666 :
3667 : if (!is_extern_segment(sp)) {
3668 : if (is_mmapped_segment(sp)) {
3669 0 : if (HAVE_MMAP &&
3670 0 : sp->size >= extra &&
3671 0 : !has_segment_link(m, sp)) { /* can't shrink if pinned */
3672 0 : size_t newsize = sp->size - extra;
3673 : /* Prefer mremap, fall back to munmap */
3674 0 : if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||
3675 0 : (CALL_MUNMAP(sp->base + newsize, extra) == 0)) {
3676 0 : released = extra;
3677 : }
3678 : }
3679 : }
3680 : else if (HAVE_MORECORE) {
3681 : if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */
3682 : extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;
3683 : ACQUIRE_MORECORE_LOCK();
3684 : {
3685 : /* Make sure end of memory is where we last set it. */
3686 : char* old_br = (char*)(CALL_MORECORE(0));
3687 : if (old_br == sp->base + sp->size) {
3688 : char* rel_br = (char*)(CALL_MORECORE(-extra));
3689 : char* new_br = (char*)(CALL_MORECORE(0));
3690 : if (rel_br != CMFAIL && new_br < old_br)
3691 : released = old_br - new_br;
3692 : }
3693 : }
3694 : RELEASE_MORECORE_LOCK();
3695 : }
3696 : }
3697 :
3698 0 : if (released != 0) {
3699 0 : sp->size -= released;
3700 0 : m->footprint -= released;
3701 0 : init_top(m, m->top, m->topsize - released);
3702 0 : check_top_chunk(m, m->top);
3703 : }
3704 : }
3705 :
3706 : /* Unmap any unused mmapped segments */
3707 : if (HAVE_MMAP)
3708 0 : released += release_unused_segments(m);
3709 :
3710 : /* On failure, disable autotrim to avoid repeated failed future calls */
3711 0 : if (released == 0)
3712 0 : m->trim_check = MAX_SIZE_T;
3713 : }
3714 :
3715 0 : return (released != 0)? 1 : 0;
3716 : }
3717 :
3718 : /* ---------------------------- malloc support --------------------------- */
3719 :
3720 : /* allocate a large request from the best fitting chunk in a treebin */
3721 0 : static void* tmalloc_large(mstate m, size_t nb) {
3722 0 : tchunkptr v = 0;
3723 0 : size_t rsize = -nb; /* Unsigned negation */
3724 : tchunkptr t;
3725 : bindex_t idx;
3726 0 : compute_tree_index(nb, idx);
3727 :
3728 0 : if ((t = *treebin_at(m, idx)) != 0) {
3729 : /* Traverse tree for this bin looking for node with size == nb */
3730 0 : size_t sizebits = nb << leftshift_for_tree_index(idx);
3731 0 : tchunkptr rst = 0; /* The deepest untaken right subtree */
3732 0 : for (;;) {
3733 : tchunkptr rt;
3734 0 : size_t trem = chunksize(t) - nb;
3735 0 : if (trem < rsize) {
3736 0 : v = t;
3737 0 : if ((rsize = trem) == 0)
3738 0 : break;
3739 : }
3740 0 : rt = t->child[1];
3741 0 : t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
3742 0 : if (rt != 0 && rt != t)
3743 0 : rst = rt;
3744 0 : if (t == 0) {
3745 0 : t = rst; /* set t to least subtree holding sizes > nb */
3746 0 : break;
3747 : }
3748 0 : sizebits <<= 1;
3749 : }
3750 : }
3751 :
3752 0 : if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
3753 0 : binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
3754 0 : if (leftbits != 0) {
3755 : bindex_t i;
3756 0 : binmap_t leastbit = least_bit(leftbits);
3757 0 : compute_bit2idx(leastbit, i);
3758 0 : t = *treebin_at(m, i);
3759 : }
3760 : }
3761 :
3762 0 : while (t != 0) { /* find smallest of tree or subtree */
3763 0 : size_t trem = chunksize(t) - nb;
3764 0 : if (trem < rsize) {
3765 0 : rsize = trem;
3766 0 : v = t;
3767 : }
3768 0 : t = leftmost_child(t);
3769 : }
3770 :
3771 : /* If dv is a better fit, return 0 so malloc will use it */
3772 0 : if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
3773 0 : if (RTCHECK(ok_address(m, v))) { /* split */
3774 0 : mchunkptr r = chunk_plus_offset(v, nb);
3775 0 : assert(chunksize(v) == rsize + nb);
3776 0 : if (RTCHECK(ok_next(v, r))) {
3777 0 : unlink_large_chunk(m, v);
3778 0 : if (rsize < MIN_CHUNK_SIZE)
3779 0 : set_inuse_and_pinuse(m, v, (rsize + nb));
3780 : else {
3781 0 : set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3782 0 : set_size_and_pinuse_of_free_chunk(r, rsize);
3783 0 : insert_chunk(m, r, rsize);
3784 : }
3785 0 : return chunk2mem(v);
3786 : }
3787 : }
3788 0 : CORRUPTION_ERROR_ACTION(m);
3789 : }
3790 0 : return 0;
3791 : }
3792 :
3793 : /* allocate a small request from the best fitting chunk in a treebin */
3794 0 : static void* tmalloc_small(mstate m, size_t nb) {
3795 : tchunkptr t, v;
3796 : size_t rsize;
3797 : bindex_t i;
3798 0 : binmap_t leastbit = least_bit(m->treemap);
3799 0 : compute_bit2idx(leastbit, i);
3800 :
3801 0 : v = t = *treebin_at(m, i);
3802 0 : rsize = chunksize(t) - nb;
3803 :
3804 0 : while ((t = leftmost_child(t)) != 0) {
3805 0 : size_t trem = chunksize(t) - nb;
3806 0 : if (trem < rsize) {
3807 0 : rsize = trem;
3808 0 : v = t;
3809 : }
3810 : }
3811 :
3812 0 : if (RTCHECK(ok_address(m, v))) {
3813 0 : mchunkptr r = chunk_plus_offset(v, nb);
3814 0 : assert(chunksize(v) == rsize + nb);
3815 0 : if (RTCHECK(ok_next(v, r))) {
3816 0 : unlink_large_chunk(m, v);
3817 0 : if (rsize < MIN_CHUNK_SIZE)
3818 0 : set_inuse_and_pinuse(m, v, (rsize + nb));
3819 : else {
3820 0 : set_size_and_pinuse_of_inuse_chunk(m, v, nb);
3821 0 : set_size_and_pinuse_of_free_chunk(r, rsize);
3822 0 : replace_dv(m, r, rsize);
3823 : }
3824 0 : return chunk2mem(v);
3825 : }
3826 : }
3827 :
3828 0 : CORRUPTION_ERROR_ACTION(m);
3829 : return 0;
3830 : }
3831 :
3832 : /* --------------------------- realloc support --------------------------- */
3833 :
3834 0 : static void* internal_realloc(mstate m, void* oldmem, size_t bytes) {
3835 0 : if (bytes >= MAX_REQUEST) {
3836 0 : MALLOC_FAILURE_ACTION;
3837 0 : return 0;
3838 : }
3839 0 : if (!PREACTION(m)) {
3840 0 : mchunkptr oldp = mem2chunk(oldmem);
3841 0 : size_t oldsize = chunksize(oldp);
3842 0 : mchunkptr next = chunk_plus_offset(oldp, oldsize);
3843 0 : mchunkptr newp = 0;
3844 0 : void* extra = 0;
3845 :
3846 : /* Try to either shrink or extend into top. Else malloc-copy-free */
3847 :
3848 0 : if (RTCHECK(ok_address(m, oldp) && ok_cinuse(oldp) &&
3849 0 : ok_next(oldp, next) && ok_pinuse(next))) {
3850 0 : size_t nb = request2size(bytes);
3851 0 : if (is_mmapped(oldp))
3852 0 : newp = mmap_resize(m, oldp, nb);
3853 0 : else if (oldsize >= nb) { /* already big enough */
3854 0 : size_t rsize = oldsize - nb;
3855 0 : newp = oldp;
3856 0 : if (rsize >= MIN_CHUNK_SIZE) {
3857 0 : mchunkptr remainder = chunk_plus_offset(newp, nb);
3858 0 : set_inuse(m, newp, nb);
3859 0 : set_inuse(m, remainder, rsize);
3860 0 : extra = chunk2mem(remainder);
3861 : }
3862 : }
3863 0 : else if (next == m->top && oldsize + m->topsize > nb) {
3864 : /* Expand into top */
3865 0 : size_t newsize = oldsize + m->topsize;
3866 0 : size_t newtopsize = newsize - nb;
3867 0 : mchunkptr newtop = chunk_plus_offset(oldp, nb);
3868 0 : set_inuse(m, oldp, nb);
3869 0 : newtop->head = newtopsize |PINUSE_BIT;
3870 0 : m->top = newtop;
3871 0 : m->topsize = newtopsize;
3872 0 : newp = oldp;
3873 : }
3874 : }
3875 : else {
3876 0 : USAGE_ERROR_ACTION(m, oldmem);
3877 : POSTACTION(m);
3878 : return 0;
3879 : }
3880 :
3881 0 : POSTACTION(m);
3882 :
3883 0 : if (newp != 0) {
3884 0 : if (extra != 0) {
3885 0 : internal_free(m, extra);
3886 : }
3887 0 : check_inuse_chunk(m, newp);
3888 0 : return chunk2mem(newp);
3889 : }
3890 : else {
3891 0 : void* newmem = internal_malloc(m, bytes);
3892 0 : if (newmem != 0) {
3893 0 : size_t oc = oldsize - overhead_for(oldp);
3894 0 : memcpy(newmem, oldmem, (oc < bytes)? oc : bytes);
3895 0 : internal_free(m, oldmem);
3896 : }
3897 0 : return newmem;
3898 : }
3899 : }
3900 0 : return 0;
3901 : }
3902 :
3903 : /* --------------------------- memalign support -------------------------- */
3904 :
3905 0 : static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
3906 0 : if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */
3907 0 : return internal_malloc(m, bytes);
3908 0 : if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
3909 0 : alignment = MIN_CHUNK_SIZE;
3910 0 : if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */
3911 0 : size_t a = MALLOC_ALIGNMENT << 1;
3912 0 : while (a < alignment) a <<= 1;
3913 0 : alignment = a;
3914 : }
3915 :
3916 0 : if (bytes >= MAX_REQUEST - alignment) {
3917 0 : if (m != 0) { /* Test isn't needed but avoids compiler warning */
3918 0 : MALLOC_FAILURE_ACTION;
3919 : }
3920 : }
3921 : else {
3922 0 : size_t nb = request2size(bytes);
3923 0 : size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;
3924 0 : char* mem = (char*)internal_malloc(m, req);
3925 0 : if (mem != 0) {
3926 0 : void* leader = 0;
3927 0 : void* trailer = 0;
3928 0 : mchunkptr p = mem2chunk(mem);
3929 :
3930 0 : if (PREACTION(m)) return 0;
3931 0 : if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */
3932 : /*
3933 : Find an aligned spot inside chunk. Since we need to give
3934 : back leading space in a chunk of at least MIN_CHUNK_SIZE, if
3935 : the first calculation places us at a spot with less than
3936 : MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
3937 : We've allocated enough total room so that this is always
3938 : possible.
3939 : */
3940 0 : char* br = (char*)mem2chunk((size_t)(((size_t)(mem +
3941 : alignment -
3942 : SIZE_T_ONE)) &
3943 : -alignment));
3944 0 : char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?
3945 0 : br : br+alignment;
3946 0 : mchunkptr newp = (mchunkptr)pos;
3947 0 : size_t leadsize = pos - (char*)(p);
3948 0 : size_t newsize = chunksize(p) - leadsize;
3949 :
3950 0 : if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */
3951 0 : newp->prev_foot = p->prev_foot + leadsize;
3952 0 : newp->head = (newsize|CINUSE_BIT);
3953 : }
3954 : else { /* Otherwise, give back leader, use the rest */
3955 0 : set_inuse(m, newp, newsize);
3956 0 : set_inuse(m, p, leadsize);
3957 0 : leader = chunk2mem(p);
3958 : }
3959 0 : p = newp;
3960 : }
3961 :
3962 : /* Give back spare room at the end */
3963 0 : if (!is_mmapped(p)) {
3964 0 : size_t size = chunksize(p);
3965 0 : if (size > nb + MIN_CHUNK_SIZE) {
3966 0 : size_t remainder_size = size - nb;
3967 0 : mchunkptr remainder = chunk_plus_offset(p, nb);
3968 0 : set_inuse(m, p, nb);
3969 0 : set_inuse(m, remainder, remainder_size);
3970 0 : trailer = chunk2mem(remainder);
3971 : }
3972 : }
3973 :
3974 0 : assert (chunksize(p) >= nb);
3975 0 : assert((((size_t)(chunk2mem(p))) % alignment) == 0);
3976 0 : check_inuse_chunk(m, p);
3977 0 : POSTACTION(m);
3978 0 : if (leader != 0) {
3979 0 : internal_free(m, leader);
3980 : }
3981 0 : if (trailer != 0) {
3982 0 : internal_free(m, trailer);
3983 : }
3984 0 : return chunk2mem(p);
3985 : }
3986 : }
3987 0 : return 0;
3988 : }
3989 :
3990 : /* ------------------------ comalloc/coalloc support --------------------- */
3991 :
3992 0 : static void** ialloc(mstate m,
3993 : size_t n_elements,
3994 : size_t* sizes,
3995 : int opts,
3996 : void* chunks[]) {
3997 : /*
3998 : This provides common support for independent_X routines, handling
3999 : all of the combinations that can result.
4000 :
4001 : The opts arg has:
4002 : bit 0 set if all elements are same size (using sizes[0])
4003 : bit 1 set if elements should be zeroed
4004 : */
4005 :
4006 : size_t element_size; /* chunksize of each element, if all same */
4007 : size_t contents_size; /* total size of elements */
4008 : size_t array_size; /* request size of pointer array */
4009 : void* mem; /* malloced aggregate space */
4010 : mchunkptr p; /* corresponding chunk */
4011 : size_t remainder_size; /* remaining bytes while splitting */
4012 : void** marray; /* either "chunks" or malloced ptr array */
4013 : mchunkptr array_chunk; /* chunk for malloced ptr array */
4014 : flag_t was_enabled; /* to disable mmap */
4015 : size_t size;
4016 : size_t i;
4017 :
4018 : /* compute array length, if needed */
4019 0 : if (chunks != 0) {
4020 0 : if (n_elements == 0)
4021 0 : return chunks; /* nothing to do */
4022 0 : marray = chunks;
4023 0 : array_size = 0;
4024 : }
4025 : else {
4026 : /* if empty req, must still return chunk representing empty array */
4027 0 : if (n_elements == 0)
4028 0 : return (void**)internal_malloc(m, 0);
4029 0 : marray = 0;
4030 0 : array_size = request2size(n_elements * (sizeof(void*)));
4031 : }
4032 :
4033 : /* compute total element size */
4034 0 : if (opts & 0x1) { /* all-same-size */
4035 0 : element_size = request2size(*sizes);
4036 0 : contents_size = n_elements * element_size;
4037 : }
4038 : else { /* add up all the sizes */
4039 0 : element_size = 0;
4040 0 : contents_size = 0;
4041 0 : for (i = 0; i != n_elements; ++i)
4042 0 : contents_size += request2size(sizes[i]);
4043 : }
4044 :
4045 0 : size = contents_size + array_size;
4046 :
4047 : /*
4048 : Allocate the aggregate chunk. First disable direct-mmapping so
4049 : malloc won't use it, since we would not be able to later
4050 : free/realloc space internal to a segregated mmap region.
4051 : */
4052 0 : was_enabled = use_mmap(m);
4053 0 : disable_mmap(m);
4054 0 : mem = internal_malloc(m, size - CHUNK_OVERHEAD);
4055 0 : if (was_enabled)
4056 0 : enable_mmap(m);
4057 0 : if (mem == 0)
4058 0 : return 0;
4059 :
4060 0 : if (PREACTION(m)) return 0;
4061 0 : p = mem2chunk(mem);
4062 0 : remainder_size = chunksize(p);
4063 :
4064 0 : assert(!is_mmapped(p));
4065 :
4066 0 : if (opts & 0x2) { /* optionally clear the elements */
4067 0 : memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);
4068 : }
4069 :
4070 : /* If not provided, allocate the pointer array as final part of chunk */
4071 0 : if (marray == 0) {
4072 : size_t array_chunk_size;
4073 0 : array_chunk = chunk_plus_offset(p, contents_size);
4074 0 : array_chunk_size = remainder_size - contents_size;
4075 0 : marray = (void**) (chunk2mem(array_chunk));
4076 0 : set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);
4077 0 : remainder_size = contents_size;
4078 : }
4079 :
4080 : /* split out elements */
4081 0 : for (i = 0; ; ++i) {
4082 0 : marray[i] = chunk2mem(p);
4083 0 : if (i != n_elements-1) {
4084 0 : if (element_size != 0)
4085 0 : size = element_size;
4086 : else
4087 0 : size = request2size(sizes[i]);
4088 0 : remainder_size -= size;
4089 0 : set_size_and_pinuse_of_inuse_chunk(m, p, size);
4090 0 : p = chunk_plus_offset(p, size);
4091 : }
4092 : else { /* the final element absorbs any overallocation slop */
4093 0 : set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);
4094 0 : break;
4095 : }
4096 : }
4097 :
4098 : #if DEBUG
4099 0 : if (marray != chunks) {
4100 : /* final element must have exactly exhausted chunk */
4101 0 : if (element_size != 0) {
4102 0 : assert(remainder_size == element_size);
4103 : }
4104 : else {
4105 0 : assert(remainder_size == request2size(sizes[i]));
4106 : }
4107 0 : check_inuse_chunk(m, mem2chunk(marray));
4108 : }
4109 0 : for (i = 0; i != n_elements; ++i)
4110 0 : check_inuse_chunk(m, mem2chunk(marray[i]));
4111 :
4112 : #endif /* DEBUG */
4113 :
4114 0 : POSTACTION(m);
4115 0 : return marray;
4116 : }
4117 :
4118 :
4119 : /* -------------------------- public routines ---------------------------- */
4120 :
4121 : #if !ONLY_MSPACES
4122 :
4123 0 : void* dlmalloc(size_t bytes) {
4124 : /*
4125 : Basic algorithm:
4126 : If a small request (< 256 bytes minus per-chunk overhead):
4127 : 1. If one exists, use a remainderless chunk in associated smallbin.
4128 : (Remainderless means that there are too few excess bytes to
4129 : represent as a chunk.)
4130 : 2. If it is big enough, use the dv chunk, which is normally the
4131 : chunk adjacent to the one used for the most recent small request.
4132 : 3. If one exists, split the smallest available chunk in a bin,
4133 : saving remainder in dv.
4134 : 4. If it is big enough, use the top chunk.
4135 : 5. If available, get memory from system and use it
4136 : Otherwise, for a large request:
4137 : 1. Find the smallest available binned chunk that fits, and use it
4138 : if it is better fitting than dv chunk, splitting if necessary.
4139 : 2. If better fitting than any binned chunk, use the dv chunk.
4140 : 3. If it is big enough, use the top chunk.
4141 : 4. If request size >= mmap threshold, try to directly mmap this chunk.
4142 : 5. If available, get memory from system and use it
4143 :
4144 : The ugly goto's here ensure that postaction occurs along all paths.
4145 : */
4146 :
4147 0 : if (!PREACTION(gm)) {
4148 : void* mem;
4149 : size_t nb;
4150 0 : if (bytes <= MAX_SMALL_REQUEST) {
4151 : bindex_t idx;
4152 : binmap_t smallbits;
4153 0 : nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
4154 0 : idx = small_index(nb);
4155 0 : smallbits = gm->smallmap >> idx;
4156 :
4157 0 : if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
4158 : mchunkptr b, p;
4159 0 : idx += ~smallbits & 1; /* Uses next bin if idx empty */
4160 0 : b = smallbin_at(gm, idx);
4161 0 : p = b->fd;
4162 0 : assert(chunksize(p) == small_index2size(idx));
4163 0 : unlink_first_small_chunk(gm, b, p, idx);
4164 0 : set_inuse_and_pinuse(gm, p, small_index2size(idx));
4165 0 : mem = chunk2mem(p);
4166 0 : check_malloced_chunk(gm, mem, nb);
4167 0 : goto postaction;
4168 : }
4169 :
4170 0 : else if (nb > gm->dvsize) {
4171 0 : if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
4172 : mchunkptr b, p, r;
4173 : size_t rsize;
4174 : bindex_t i;
4175 0 : binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4176 0 : binmap_t leastbit = least_bit(leftbits);
4177 0 : compute_bit2idx(leastbit, i);
4178 0 : b = smallbin_at(gm, i);
4179 0 : p = b->fd;
4180 0 : assert(chunksize(p) == small_index2size(i));
4181 0 : unlink_first_small_chunk(gm, b, p, i);
4182 0 : rsize = small_index2size(i) - nb;
4183 : /* Fit here cannot be remainderless if 4byte sizes */
4184 0 : if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4185 0 : set_inuse_and_pinuse(gm, p, small_index2size(i));
4186 : else {
4187 0 : set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4188 0 : r = chunk_plus_offset(p, nb);
4189 0 : set_size_and_pinuse_of_free_chunk(r, rsize);
4190 0 : replace_dv(gm, r, rsize);
4191 : }
4192 0 : mem = chunk2mem(p);
4193 0 : check_malloced_chunk(gm, mem, nb);
4194 0 : goto postaction;
4195 : }
4196 :
4197 0 : else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
4198 0 : check_malloced_chunk(gm, mem, nb);
4199 0 : goto postaction;
4200 : }
4201 : }
4202 : }
4203 0 : else if (bytes >= MAX_REQUEST)
4204 0 : nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
4205 : else {
4206 0 : nb = pad_request(bytes);
4207 0 : if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
4208 0 : check_malloced_chunk(gm, mem, nb);
4209 0 : goto postaction;
4210 : }
4211 : }
4212 :
4213 0 : if (nb <= gm->dvsize) {
4214 0 : size_t rsize = gm->dvsize - nb;
4215 0 : mchunkptr p = gm->dv;
4216 0 : if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4217 0 : mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
4218 0 : gm->dvsize = rsize;
4219 0 : set_size_and_pinuse_of_free_chunk(r, rsize);
4220 0 : set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4221 : }
4222 : else { /* exhaust dv */
4223 0 : size_t dvs = gm->dvsize;
4224 0 : gm->dvsize = 0;
4225 0 : gm->dv = 0;
4226 0 : set_inuse_and_pinuse(gm, p, dvs);
4227 : }
4228 0 : mem = chunk2mem(p);
4229 0 : check_malloced_chunk(gm, mem, nb);
4230 0 : goto postaction;
4231 : }
4232 :
4233 0 : else if (nb < gm->topsize) { /* Split top */
4234 0 : size_t rsize = gm->topsize -= nb;
4235 0 : mchunkptr p = gm->top;
4236 0 : mchunkptr r = gm->top = chunk_plus_offset(p, nb);
4237 0 : r->head = rsize | PINUSE_BIT;
4238 0 : set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4239 0 : mem = chunk2mem(p);
4240 0 : check_top_chunk(gm, gm->top);
4241 0 : check_malloced_chunk(gm, mem, nb);
4242 0 : goto postaction;
4243 : }
4244 :
4245 0 : mem = sys_alloc(gm, nb);
4246 :
4247 : postaction:
4248 0 : POSTACTION(gm);
4249 0 : return mem;
4250 : }
4251 :
4252 0 : return 0;
4253 : }
4254 :
4255 0 : void dlfree(void* mem) {
4256 : /*
4257 : Consolidate freed chunks with preceding or succeeding bordering
4258 : free chunks, if they exist, and then place in a bin. Intermixed
4259 : with special cases for top, dv, mmapped chunks, and usage errors.
4260 : */
4261 :
4262 0 : if (mem != 0) {
4263 0 : mchunkptr p = mem2chunk(mem);
4264 : #if FOOTERS
4265 : mstate fm = get_mstate_for(p);
4266 : if (!ok_magic(fm)) {
4267 : USAGE_ERROR_ACTION(fm, p);
4268 : return;
4269 : }
4270 : #else /* FOOTERS */
4271 : #define fm gm
4272 : #endif /* FOOTERS */
4273 0 : if (!PREACTION(fm)) {
4274 0 : check_inuse_chunk(fm, p);
4275 0 : if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
4276 0 : size_t psize = chunksize(p);
4277 0 : mchunkptr next = chunk_plus_offset(p, psize);
4278 0 : if (!pinuse(p)) {
4279 0 : size_t prevsize = p->prev_foot;
4280 0 : if ((prevsize & IS_MMAPPED_BIT) != 0) {
4281 0 : prevsize &= ~IS_MMAPPED_BIT;
4282 0 : psize += prevsize + MMAP_FOOT_PAD;
4283 0 : if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4284 0 : fm->footprint -= psize;
4285 0 : goto postaction;
4286 : }
4287 : else {
4288 0 : mchunkptr prev = chunk_minus_offset(p, prevsize);
4289 0 : psize += prevsize;
4290 0 : p = prev;
4291 0 : if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4292 0 : if (p != fm->dv) {
4293 0 : unlink_chunk(fm, p, prevsize);
4294 : }
4295 0 : else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4296 0 : fm->dvsize = psize;
4297 0 : set_free_with_pinuse(p, psize, next);
4298 0 : goto postaction;
4299 : }
4300 : }
4301 : else
4302 0 : goto erroraction;
4303 : }
4304 : }
4305 :
4306 0 : if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
4307 0 : if (!cinuse(next)) { /* consolidate forward */
4308 0 : if (next == fm->top) {
4309 0 : size_t tsize = fm->topsize += psize;
4310 0 : fm->top = p;
4311 0 : p->head = tsize | PINUSE_BIT;
4312 0 : if (p == fm->dv) {
4313 0 : fm->dv = 0;
4314 0 : fm->dvsize = 0;
4315 : }
4316 0 : if (should_trim(fm, tsize))
4317 0 : sys_trim(fm, 0);
4318 0 : goto postaction;
4319 : }
4320 0 : else if (next == fm->dv) {
4321 0 : size_t dsize = fm->dvsize += psize;
4322 0 : fm->dv = p;
4323 0 : set_size_and_pinuse_of_free_chunk(p, dsize);
4324 0 : goto postaction;
4325 : }
4326 : else {
4327 0 : size_t nsize = chunksize(next);
4328 0 : psize += nsize;
4329 0 : unlink_chunk(fm, next, nsize);
4330 0 : set_size_and_pinuse_of_free_chunk(p, psize);
4331 0 : if (p == fm->dv) {
4332 0 : fm->dvsize = psize;
4333 0 : goto postaction;
4334 : }
4335 : }
4336 : }
4337 : else
4338 0 : set_free_with_pinuse(p, psize, next);
4339 0 : insert_chunk(fm, p, psize);
4340 0 : check_free_chunk(fm, p);
4341 0 : goto postaction;
4342 : }
4343 : }
4344 : erroraction:
4345 0 : USAGE_ERROR_ACTION(fm, p);
4346 : postaction:
4347 0 : POSTACTION(fm);
4348 : }
4349 : }
4350 : #if !FOOTERS
4351 : #undef fm
4352 : #endif /* FOOTERS */
4353 0 : }
4354 :
4355 0 : void* dlcalloc(size_t n_elements, size_t elem_size) {
4356 : void* mem;
4357 0 : size_t req = 0;
4358 0 : if (n_elements != 0) {
4359 0 : req = n_elements * elem_size;
4360 0 : if (((n_elements | elem_size) & ~(size_t)0xffff) &&
4361 0 : (req / n_elements != elem_size))
4362 0 : req = MAX_SIZE_T; /* force downstream failure on overflow */
4363 : }
4364 0 : mem = dlmalloc(req);
4365 0 : if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
4366 0 : memset(mem, 0, req);
4367 0 : return mem;
4368 : }
4369 :
4370 0 : void* dlrealloc(void* oldmem, size_t bytes) {
4371 0 : if (oldmem == 0)
4372 0 : return dlmalloc(bytes);
4373 : #ifdef REALLOC_ZERO_BYTES_FREES
4374 : if (bytes == 0) {
4375 : dlfree(oldmem);
4376 : return 0;
4377 : }
4378 : #endif /* REALLOC_ZERO_BYTES_FREES */
4379 : else {
4380 : #if ! FOOTERS
4381 0 : mstate m = gm;
4382 : #else /* FOOTERS */
4383 : mstate m = get_mstate_for(mem2chunk(oldmem));
4384 : if (!ok_magic(m)) {
4385 : USAGE_ERROR_ACTION(m, oldmem);
4386 : return 0;
4387 : }
4388 : #endif /* FOOTERS */
4389 0 : return internal_realloc(m, oldmem, bytes);
4390 : }
4391 : }
4392 :
4393 0 : void* dlmemalign(size_t alignment, size_t bytes) {
4394 0 : return internal_memalign(gm, alignment, bytes);
4395 : }
4396 :
4397 0 : void** dlindependent_calloc(size_t n_elements, size_t elem_size,
4398 : void* chunks[]) {
4399 0 : size_t sz = elem_size; /* serves as 1-element array */
4400 0 : return ialloc(gm, n_elements, &sz, 3, chunks);
4401 : }
4402 :
4403 0 : void** dlindependent_comalloc(size_t n_elements, size_t sizes[],
4404 : void* chunks[]) {
4405 0 : return ialloc(gm, n_elements, sizes, 0, chunks);
4406 : }
4407 :
4408 0 : void* dlvalloc(size_t bytes) {
4409 : size_t pagesz;
4410 0 : init_mparams();
4411 0 : pagesz = mparams.page_size;
4412 0 : return dlmemalign(pagesz, bytes);
4413 : }
4414 :
4415 0 : void* dlpvalloc(size_t bytes) {
4416 : size_t pagesz;
4417 0 : init_mparams();
4418 0 : pagesz = mparams.page_size;
4419 0 : return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));
4420 : }
4421 :
4422 0 : int dlmalloc_trim(size_t pad) {
4423 0 : int result = 0;
4424 0 : if (!PREACTION(gm)) {
4425 0 : result = sys_trim(gm, pad);
4426 0 : POSTACTION(gm);
4427 : }
4428 0 : return result;
4429 : }
4430 :
4431 0 : size_t dlmalloc_footprint(void) {
4432 0 : return gm->footprint;
4433 : }
4434 :
4435 0 : size_t dlmalloc_max_footprint(void) {
4436 0 : return gm->max_footprint;
4437 : }
4438 :
4439 : #if !NO_MALLINFO
4440 : struct mallinfo dlmallinfo(void) {
4441 : return internal_mallinfo(gm);
4442 : }
4443 : #endif /* NO_MALLINFO */
4444 :
4445 0 : void dlmalloc_stats() {
4446 0 : internal_malloc_stats(gm);
4447 0 : }
4448 :
4449 0 : size_t dlmalloc_usable_size(void* mem) {
4450 0 : if (mem != 0) {
4451 0 : mchunkptr p = mem2chunk(mem);
4452 0 : if (cinuse(p))
4453 0 : return chunksize(p) - overhead_for(p);
4454 : }
4455 0 : return 0;
4456 : }
4457 :
4458 0 : int dlmallopt(int param_number, int value) {
4459 0 : return change_mparam(param_number, value);
4460 : }
4461 :
4462 : #endif /* !ONLY_MSPACES */
4463 :
4464 : /* ----------------------------- user mspaces ---------------------------- */
4465 :
4466 : #if MSPACES
4467 :
4468 : static mstate init_user_mstate(char* tbase, size_t tsize) {
4469 : size_t msize = pad_request(sizeof(struct malloc_state));
4470 : mchunkptr mn;
4471 : mchunkptr msp = align_as_chunk(tbase);
4472 : mstate m = (mstate)(chunk2mem(msp));
4473 : memset(m, 0, msize);
4474 : INITIAL_LOCK(&m->mutex);
4475 : msp->head = (msize|PINUSE_BIT|CINUSE_BIT);
4476 : m->seg.base = m->least_addr = tbase;
4477 : m->seg.size = m->footprint = m->max_footprint = tsize;
4478 : m->magic = mparams.magic;
4479 : m->mflags = mparams.default_mflags;
4480 : disable_contiguous(m);
4481 : init_bins(m);
4482 : mn = next_chunk(mem2chunk(m));
4483 : init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);
4484 : check_top_chunk(m, m->top);
4485 : return m;
4486 : }
4487 :
4488 : mspace create_mspace(size_t capacity, int locked) {
4489 : mstate m = 0;
4490 : size_t msize = pad_request(sizeof(struct malloc_state));
4491 : init_mparams(); /* Ensure pagesize etc initialized */
4492 :
4493 : if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4494 : size_t rs = ((capacity == 0)? mparams.granularity :
4495 : (capacity + TOP_FOOT_SIZE + msize));
4496 : size_t tsize = granularity_align(rs);
4497 : char* tbase = (char*)(CALL_MMAP(tsize));
4498 : if (tbase != CMFAIL) {
4499 : m = init_user_mstate(tbase, tsize);
4500 : set_segment_flags(&m->seg, IS_MMAPPED_BIT);
4501 : set_lock(m, locked);
4502 : }
4503 : }
4504 : return (mspace)m;
4505 : }
4506 :
4507 : mspace create_mspace_with_base(void* base, size_t capacity, int locked) {
4508 : mstate m = 0;
4509 : size_t msize = pad_request(sizeof(struct malloc_state));
4510 : init_mparams(); /* Ensure pagesize etc initialized */
4511 :
4512 : if (capacity > msize + TOP_FOOT_SIZE &&
4513 : capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {
4514 : m = init_user_mstate((char*)base, capacity);
4515 : set_segment_flags(&m->seg, EXTERN_BIT);
4516 : set_lock(m, locked);
4517 : }
4518 : return (mspace)m;
4519 : }
4520 :
4521 : size_t destroy_mspace(mspace msp) {
4522 : size_t freed = 0;
4523 : mstate ms = (mstate)msp;
4524 : if (ok_magic(ms)) {
4525 : msegmentptr sp = &ms->seg;
4526 : while (sp != 0) {
4527 : char* base = sp->base;
4528 : size_t size = sp->size;
4529 : flag_t flag = get_segment_flags(sp);
4530 : sp = sp->next;
4531 : if ((flag & IS_MMAPPED_BIT) && !(flag & EXTERN_BIT) &&
4532 : CALL_MUNMAP(base, size) == 0)
4533 : freed += size;
4534 : }
4535 : }
4536 : else {
4537 : USAGE_ERROR_ACTION(ms,ms);
4538 : }
4539 : return freed;
4540 : }
4541 :
4542 : /*
4543 : mspace versions of routines are near-clones of the global
4544 : versions. This is not so nice but better than the alternatives.
4545 : */
4546 :
4547 :
4548 : void* mspace_malloc(mspace msp, size_t bytes) {
4549 : mstate ms = (mstate)msp;
4550 : if (!ok_magic(ms)) {
4551 : USAGE_ERROR_ACTION(ms,ms);
4552 : return 0;
4553 : }
4554 : if (!PREACTION(ms)) {
4555 : void* mem;
4556 : size_t nb;
4557 : if (bytes <= MAX_SMALL_REQUEST) {
4558 : bindex_t idx;
4559 : binmap_t smallbits;
4560 : nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
4561 : idx = small_index(nb);
4562 : smallbits = ms->smallmap >> idx;
4563 :
4564 : if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
4565 : mchunkptr b, p;
4566 : idx += ~smallbits & 1; /* Uses next bin if idx empty */
4567 : b = smallbin_at(ms, idx);
4568 : p = b->fd;
4569 : assert(chunksize(p) == small_index2size(idx));
4570 : unlink_first_small_chunk(ms, b, p, idx);
4571 : set_inuse_and_pinuse(ms, p, small_index2size(idx));
4572 : mem = chunk2mem(p);
4573 : check_malloced_chunk(ms, mem, nb);
4574 : goto postaction;
4575 : }
4576 :
4577 : else if (nb > ms->dvsize) {
4578 : if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
4579 : mchunkptr b, p, r;
4580 : size_t rsize;
4581 : bindex_t i;
4582 : binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4583 : binmap_t leastbit = least_bit(leftbits);
4584 : compute_bit2idx(leastbit, i);
4585 : b = smallbin_at(ms, i);
4586 : p = b->fd;
4587 : assert(chunksize(p) == small_index2size(i));
4588 : unlink_first_small_chunk(ms, b, p, i);
4589 : rsize = small_index2size(i) - nb;
4590 : /* Fit here cannot be remainderless if 4byte sizes */
4591 : if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4592 : set_inuse_and_pinuse(ms, p, small_index2size(i));
4593 : else {
4594 : set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4595 : r = chunk_plus_offset(p, nb);
4596 : set_size_and_pinuse_of_free_chunk(r, rsize);
4597 : replace_dv(ms, r, rsize);
4598 : }
4599 : mem = chunk2mem(p);
4600 : check_malloced_chunk(ms, mem, nb);
4601 : goto postaction;
4602 : }
4603 :
4604 : else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {
4605 : check_malloced_chunk(ms, mem, nb);
4606 : goto postaction;
4607 : }
4608 : }
4609 : }
4610 : else if (bytes >= MAX_REQUEST)
4611 : nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
4612 : else {
4613 : nb = pad_request(bytes);
4614 : if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
4615 : check_malloced_chunk(ms, mem, nb);
4616 : goto postaction;
4617 : }
4618 : }
4619 :
4620 : if (nb <= ms->dvsize) {
4621 : size_t rsize = ms->dvsize - nb;
4622 : mchunkptr p = ms->dv;
4623 : if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4624 : mchunkptr r = ms->dv = chunk_plus_offset(p, nb);
4625 : ms->dvsize = rsize;
4626 : set_size_and_pinuse_of_free_chunk(r, rsize);
4627 : set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4628 : }
4629 : else { /* exhaust dv */
4630 : size_t dvs = ms->dvsize;
4631 : ms->dvsize = 0;
4632 : ms->dv = 0;
4633 : set_inuse_and_pinuse(ms, p, dvs);
4634 : }
4635 : mem = chunk2mem(p);
4636 : check_malloced_chunk(ms, mem, nb);
4637 : goto postaction;
4638 : }
4639 :
4640 : else if (nb < ms->topsize) { /* Split top */
4641 : size_t rsize = ms->topsize -= nb;
4642 : mchunkptr p = ms->top;
4643 : mchunkptr r = ms->top = chunk_plus_offset(p, nb);
4644 : r->head = rsize | PINUSE_BIT;
4645 : set_size_and_pinuse_of_inuse_chunk(ms, p, nb);
4646 : mem = chunk2mem(p);
4647 : check_top_chunk(ms, ms->top);
4648 : check_malloced_chunk(ms, mem, nb);
4649 : goto postaction;
4650 : }
4651 :
4652 : mem = sys_alloc(ms, nb);
4653 :
4654 : postaction:
4655 : POSTACTION(ms);
4656 : return mem;
4657 : }
4658 :
4659 : return 0;
4660 : }
4661 :
4662 : void mspace_free(mspace msp, void* mem) {
4663 : if (mem != 0) {
4664 : mchunkptr p = mem2chunk(mem);
4665 : #if FOOTERS
4666 : mstate fm = get_mstate_for(p);
4667 : #else /* FOOTERS */
4668 : mstate fm = (mstate)msp;
4669 : #endif /* FOOTERS */
4670 : if (!ok_magic(fm)) {
4671 : USAGE_ERROR_ACTION(fm, p);
4672 : return;
4673 : }
4674 : if (!PREACTION(fm)) {
4675 : check_inuse_chunk(fm, p);
4676 : if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {
4677 : size_t psize = chunksize(p);
4678 : mchunkptr next = chunk_plus_offset(p, psize);
4679 : if (!pinuse(p)) {
4680 : size_t prevsize = p->prev_foot;
4681 : if ((prevsize & IS_MMAPPED_BIT) != 0) {
4682 : prevsize &= ~IS_MMAPPED_BIT;
4683 : psize += prevsize + MMAP_FOOT_PAD;
4684 : if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4685 : fm->footprint -= psize;
4686 : goto postaction;
4687 : }
4688 : else {
4689 : mchunkptr prev = chunk_minus_offset(p, prevsize);
4690 : psize += prevsize;
4691 : p = prev;
4692 : if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4693 : if (p != fm->dv) {
4694 : unlink_chunk(fm, p, prevsize);
4695 : }
4696 : else if ((next->head & INUSE_BITS) == INUSE_BITS) {
4697 : fm->dvsize = psize;
4698 : set_free_with_pinuse(p, psize, next);
4699 : goto postaction;
4700 : }
4701 : }
4702 : else
4703 : goto erroraction;
4704 : }
4705 : }
4706 :
4707 : if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {
4708 : if (!cinuse(next)) { /* consolidate forward */
4709 : if (next == fm->top) {
4710 : size_t tsize = fm->topsize += psize;
4711 : fm->top = p;
4712 : p->head = tsize | PINUSE_BIT;
4713 : if (p == fm->dv) {
4714 : fm->dv = 0;
4715 : fm->dvsize = 0;
4716 : }
4717 : if (should_trim(fm, tsize))
4718 : sys_trim(fm, 0);
4719 : goto postaction;
4720 : }
4721 : else if (next == fm->dv) {
4722 : size_t dsize = fm->dvsize += psize;
4723 : fm->dv = p;
4724 : set_size_and_pinuse_of_free_chunk(p, dsize);
4725 : goto postaction;
4726 : }
4727 : else {
4728 : size_t nsize = chunksize(next);
4729 : psize += nsize;
4730 : unlink_chunk(fm, next, nsize);
4731 : set_size_and_pinuse_of_free_chunk(p, psize);
4732 : if (p == fm->dv) {
4733 : fm->dvsize = psize;
4734 : goto postaction;
4735 : }
4736 : }
4737 : }
4738 : else
4739 : set_free_with_pinuse(p, psize, next);
4740 : insert_chunk(fm, p, psize);
4741 : check_free_chunk(fm, p);
4742 : goto postaction;
4743 : }
4744 : }
4745 : erroraction:
4746 : USAGE_ERROR_ACTION(fm, p);
4747 : postaction:
4748 : POSTACTION(fm);
4749 : }
4750 : }
4751 : }
4752 :
4753 : void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {
4754 : void* mem;
4755 : size_t req = 0;
4756 : mstate ms = (mstate)msp;
4757 : if (!ok_magic(ms)) {
4758 : USAGE_ERROR_ACTION(ms,ms);
4759 : return 0;
4760 : }
4761 : if (n_elements != 0) {
4762 : req = n_elements * elem_size;
4763 : if (((n_elements | elem_size) & ~(size_t)0xffff) &&
4764 : (req / n_elements != elem_size))
4765 : req = MAX_SIZE_T; /* force downstream failure on overflow */
4766 : }
4767 : mem = internal_malloc(ms, req);
4768 : if (mem != 0 && calloc_must_clear(mem2chunk(mem)))
4769 : memset(mem, 0, req);
4770 : return mem;
4771 : }
4772 :
4773 : void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {
4774 : if (oldmem == 0)
4775 : return mspace_malloc(msp, bytes);
4776 : #ifdef REALLOC_ZERO_BYTES_FREES
4777 : if (bytes == 0) {
4778 : mspace_free(msp, oldmem);
4779 : return 0;
4780 : }
4781 : #endif /* REALLOC_ZERO_BYTES_FREES */
4782 : else {
4783 : #if FOOTERS
4784 : mchunkptr p = mem2chunk(oldmem);
4785 : mstate ms = get_mstate_for(p);
4786 : #else /* FOOTERS */
4787 : mstate ms = (mstate)msp;
4788 : #endif /* FOOTERS */
4789 : if (!ok_magic(ms)) {
4790 : USAGE_ERROR_ACTION(ms,ms);
4791 : return 0;
4792 : }
4793 : return internal_realloc(ms, oldmem, bytes);
4794 : }
4795 : }
4796 :
4797 : void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {
4798 : mstate ms = (mstate)msp;
4799 : if (!ok_magic(ms)) {
4800 : USAGE_ERROR_ACTION(ms,ms);
4801 : return 0;
4802 : }
4803 : return internal_memalign(ms, alignment, bytes);
4804 : }
4805 :
4806 : void** mspace_independent_calloc(mspace msp, size_t n_elements,
4807 : size_t elem_size, void* chunks[]) {
4808 : size_t sz = elem_size; /* serves as 1-element array */
4809 : mstate ms = (mstate)msp;
4810 : if (!ok_magic(ms)) {
4811 : USAGE_ERROR_ACTION(ms,ms);
4812 : return 0;
4813 : }
4814 : return ialloc(ms, n_elements, &sz, 3, chunks);
4815 : }
4816 :
4817 : void** mspace_independent_comalloc(mspace msp, size_t n_elements,
4818 : size_t sizes[], void* chunks[]) {
4819 : mstate ms = (mstate)msp;
4820 : if (!ok_magic(ms)) {
4821 : USAGE_ERROR_ACTION(ms,ms);
4822 : return 0;
4823 : }
4824 : return ialloc(ms, n_elements, sizes, 0, chunks);
4825 : }
4826 :
4827 : int mspace_trim(mspace msp, size_t pad) {
4828 : int result = 0;
4829 : mstate ms = (mstate)msp;
4830 : if (ok_magic(ms)) {
4831 : if (!PREACTION(ms)) {
4832 : result = sys_trim(ms, pad);
4833 : POSTACTION(ms);
4834 : }
4835 : }
4836 : else {
4837 : USAGE_ERROR_ACTION(ms,ms);
4838 : }
4839 : return result;
4840 : }
4841 :
4842 : void mspace_malloc_stats(mspace msp) {
4843 : mstate ms = (mstate)msp;
4844 : if (ok_magic(ms)) {
4845 : internal_malloc_stats(ms);
4846 : }
4847 : else {
4848 : USAGE_ERROR_ACTION(ms,ms);
4849 : }
4850 : }
4851 :
4852 : size_t mspace_footprint(mspace msp) {
4853 : size_t result;
4854 : mstate ms = (mstate)msp;
4855 : if (ok_magic(ms)) {
4856 : result = ms->footprint;
4857 : }
4858 : USAGE_ERROR_ACTION(ms,ms);
4859 : return result;
4860 : }
4861 :
4862 :
4863 : size_t mspace_max_footprint(mspace msp) {
4864 : size_t result;
4865 : mstate ms = (mstate)msp;
4866 : if (ok_magic(ms)) {
4867 : result = ms->max_footprint;
4868 : }
4869 : USAGE_ERROR_ACTION(ms,ms);
4870 : return result;
4871 : }
4872 :
4873 :
4874 : #if !NO_MALLINFO
4875 : struct mallinfo mspace_mallinfo(mspace msp) {
4876 : mstate ms = (mstate)msp;
4877 : if (!ok_magic(ms)) {
4878 : USAGE_ERROR_ACTION(ms,ms);
4879 : }
4880 : return internal_mallinfo(ms);
4881 : }
4882 : #endif /* NO_MALLINFO */
4883 :
4884 : int mspace_mallopt(int param_number, int value) {
4885 : return change_mparam(param_number, value);
4886 : }
4887 :
4888 : #endif /* MSPACES */
4889 :
4890 : /* -------------------- Alternative MORECORE functions ------------------- */
4891 :
4892 : /*
4893 : Guidelines for creating a custom version of MORECORE:
4894 :
4895 : * For best performance, MORECORE should allocate in multiples of pagesize.
4896 : * MORECORE may allocate more memory than requested. (Or even less,
4897 : but this will usually result in a malloc failure.)
4898 : * MORECORE must not allocate memory when given argument zero, but
4899 : instead return one past the end address of memory from previous
4900 : nonzero call.
4901 : * For best performance, consecutive calls to MORECORE with positive
4902 : arguments should return increasing addresses, indicating that
4903 : space has been contiguously extended.
4904 : * Even though consecutive calls to MORECORE need not return contiguous
4905 : addresses, it must be OK for malloc'ed chunks to span multiple
4906 : regions in those cases where they do happen to be contiguous.
4907 : * MORECORE need not handle negative arguments -- it may instead
4908 : just return MFAIL when given negative arguments.
4909 : Negative arguments are always multiples of pagesize. MORECORE
4910 : must not misinterpret negative args as large positive unsigned
4911 : args. You can suppress all such calls from even occurring by defining
4912 : MORECORE_CANNOT_TRIM,
4913 :
4914 : As an example alternative MORECORE, here is a custom allocator
4915 : kindly contributed for pre-OSX macOS. It uses virtually but not
4916 : necessarily physically contiguous non-paged memory (locked in,
4917 : present and won't get swapped out). You can use it by uncommenting
4918 : this section, adding some #includes, and setting up the appropriate
4919 : defines above:
4920 :
4921 : #define MORECORE osMoreCore
4922 :
4923 : There is also a shutdown routine that should somehow be called for
4924 : cleanup upon program exit.
4925 :
4926 : #define MAX_POOL_ENTRIES 100
4927 : #define MINIMUM_MORECORE_SIZE (64 * 1024U)
4928 : static int next_os_pool;
4929 : void *our_os_pools[MAX_POOL_ENTRIES];
4930 :
4931 : void *osMoreCore(int size)
4932 : {
4933 : void *ptr = 0;
4934 : static void *sbrk_top = 0;
4935 :
4936 : if (size > 0)
4937 : {
4938 : if (size < MINIMUM_MORECORE_SIZE)
4939 : size = MINIMUM_MORECORE_SIZE;
4940 : if (CurrentExecutionLevel() == kTaskLevel)
4941 : ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);
4942 : if (ptr == 0)
4943 : {
4944 : return (void *) MFAIL;
4945 : }
4946 : // save ptrs so they can be freed during cleanup
4947 : our_os_pools[next_os_pool] = ptr;
4948 : next_os_pool++;
4949 : ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);
4950 : sbrk_top = (char *) ptr + size;
4951 : return ptr;
4952 : }
4953 : else if (size < 0)
4954 : {
4955 : // we don't currently support shrink behavior
4956 : return (void *) MFAIL;
4957 : }
4958 : else
4959 : {
4960 : return sbrk_top;
4961 : }
4962 : }
4963 :
4964 : // cleanup any allocated memory pools
4965 : // called as last thing before shutting down driver
4966 :
4967 : void osCleanupMem(void)
4968 : {
4969 : void **ptr;
4970 :
4971 : for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)
4972 : if (*ptr)
4973 : {
4974 : PoolDeallocate(*ptr);
4975 : *ptr = 0;
4976 : }
4977 : }
4978 :
4979 : */
4980 :
4981 :
4982 : /* -----------------------------------------------------------------------
4983 : History:
4984 : V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee)
4985 : * Add max_footprint functions
4986 : * Ensure all appropriate literals are size_t
4987 : * Fix conditional compilation problem for some #define settings
4988 : * Avoid concatenating segments with the one provided
4989 : in create_mspace_with_base
4990 : * Rename some variables to avoid compiler shadowing warnings
4991 : * Use explicit lock initialization.
4992 : * Better handling of sbrk interference.
4993 : * Simplify and fix segment insertion, trimming and mspace_destroy
4994 : * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x
4995 : * Thanks especially to Dennis Flanagan for help on these.
4996 :
4997 : V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee)
4998 : * Fix memalign brace error.
4999 :
5000 : V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee)
5001 : * Fix improper #endif nesting in C++
5002 : * Add explicit casts needed for C++
5003 :
5004 : V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee)
5005 : * Use trees for large bins
5006 : * Support mspaces
5007 : * Use segments to unify sbrk-based and mmap-based system allocation,
5008 : removing need for emulation on most platforms without sbrk.
5009 : * Default safety checks
5010 : * Optional footer checks. Thanks to William Robertson for the idea.
5011 : * Internal code refactoring
5012 : * Incorporate suggestions and platform-specific changes.
5013 : Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,
5014 : Aaron Bachmann, Emery Berger, and others.
5015 : * Speed up non-fastbin processing enough to remove fastbins.
5016 : * Remove useless cfree() to avoid conflicts with other apps.
5017 : * Remove internal memcpy, memset. Compilers handle builtins better.
5018 : * Remove some options that no one ever used and rename others.
5019 :
5020 : V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee)
5021 : * Fix malloc_state bitmap array misdeclaration
5022 :
5023 : V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)
5024 : * Allow tuning of FIRST_SORTED_BIN_SIZE
5025 : * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.
5026 : * Better detection and support for non-contiguousness of MORECORE.
5027 : Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger
5028 : * Bypass most of malloc if no frees. Thanks To Emery Berger.
5029 : * Fix freeing of old top non-contiguous chunk im sysmalloc.
5030 : * Raised default trim and map thresholds to 256K.
5031 : * Fix mmap-related #defines. Thanks to Lubos Lunak.
5032 : * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.
5033 : * Branch-free bin calculation
5034 : * Default trim and mmap thresholds now 256K.
5035 :
5036 : V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)
5037 : * Introduce independent_comalloc and independent_calloc.
5038 : Thanks to Michael Pachos for motivation and help.
5039 : * Make optional .h file available
5040 : * Allow > 2GB requests on 32bit systems.
5041 : * new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.
5042 : Thanks also to Andreas Mueller <a.mueller at paradatec.de>,
5043 : and Anonymous.
5044 : * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for
5045 : helping test this.)
5046 : * memalign: check alignment arg
5047 : * realloc: don't try to shift chunks backwards, since this
5048 : leads to more fragmentation in some programs and doesn't
5049 : seem to help in any others.
5050 : * Collect all cases in malloc requiring system memory into sysmalloc
5051 : * Use mmap as backup to sbrk
5052 : * Place all internal state in malloc_state
5053 : * Introduce fastbins (although similar to 2.5.1)
5054 : * Many minor tunings and cosmetic improvements
5055 : * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK
5056 : * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS
5057 : Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.
5058 : * Include errno.h to support default failure action.
5059 :
5060 : V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)
5061 : * return null for negative arguments
5062 : * Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>
5063 : * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'
5064 : (e.g. WIN32 platforms)
5065 : * Cleanup header file inclusion for WIN32 platforms
5066 : * Cleanup code to avoid Microsoft Visual C++ compiler complaints
5067 : * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing
5068 : memory allocation routines
5069 : * Set 'malloc_getpagesize' for WIN32 platforms (needs more work)
5070 : * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to
5071 : usage of 'assert' in non-WIN32 code
5072 : * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to
5073 : avoid infinite loop
5074 : * Always call 'fREe()' rather than 'free()'
5075 :
5076 : V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)
5077 : * Fixed ordering problem with boundary-stamping
5078 :
5079 : V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)
5080 : * Added pvalloc, as recommended by H.J. Liu
5081 : * Added 64bit pointer support mainly from Wolfram Gloger
5082 : * Added anonymously donated WIN32 sbrk emulation
5083 : * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen
5084 : * malloc_extend_top: fix mask error that caused wastage after
5085 : foreign sbrks
5086 : * Add linux mremap support code from HJ Liu
5087 :
5088 : V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)
5089 : * Integrated most documentation with the code.
5090 : * Add support for mmap, with help from
5091 : Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5092 : * Use last_remainder in more cases.
5093 : * Pack bins using idea from colin@nyx10.cs.du.edu
5094 : * Use ordered bins instead of best-fit threshold
5095 : * Eliminate block-local decls to simplify tracing and debugging.
5096 : * Support another case of realloc via move into top
5097 : * Fix error occurring when initial sbrk_base not word-aligned.
5098 : * Rely on page size for units instead of SBRK_UNIT to
5099 : avoid surprises about sbrk alignment conventions.
5100 : * Add mallinfo, mallopt. Thanks to Raymond Nijssen
5101 : (raymond@es.ele.tue.nl) for the suggestion.
5102 : * Add `pad' argument to malloc_trim and top_pad mallopt parameter.
5103 : * More precautions for cases where other routines call sbrk,
5104 : courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).
5105 : * Added macros etc., allowing use in linux libc from
5106 : H.J. Lu (hjl@gnu.ai.mit.edu)
5107 : * Inverted this history list
5108 :
5109 : V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)
5110 : * Re-tuned and fixed to behave more nicely with V2.6.0 changes.
5111 : * Removed all preallocation code since under current scheme
5112 : the work required to undo bad preallocations exceeds
5113 : the work saved in good cases for most test programs.
5114 : * No longer use return list or unconsolidated bins since
5115 : no scheme using them consistently outperforms those that don't
5116 : given above changes.
5117 : * Use best fit for very large chunks to prevent some worst-cases.
5118 : * Added some support for debugging
5119 :
5120 : V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)
5121 : * Removed footers when chunks are in use. Thanks to
5122 : Paul Wilson (wilson@cs.texas.edu) for the suggestion.
5123 :
5124 : V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)
5125 : * Added malloc_trim, with help from Wolfram Gloger
5126 : (wmglo@Dent.MED.Uni-Muenchen.DE).
5127 :
5128 : V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)
5129 :
5130 : V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)
5131 : * realloc: try to expand in both directions
5132 : * malloc: swap order of clean-bin strategy;
5133 : * realloc: only conditionally expand backwards
5134 : * Try not to scavenge used bins
5135 : * Use bin counts as a guide to preallocation
5136 : * Occasionally bin return list chunks in first scan
5137 : * Add a few optimizations from colin@nyx10.cs.du.edu
5138 :
5139 : V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)
5140 : * faster bin computation & slightly different binning
5141 : * merged all consolidations to one part of malloc proper
5142 : (eliminating old malloc_find_space & malloc_clean_bin)
5143 : * Scan 2 returns chunks (not just 1)
5144 : * Propagate failure in realloc if malloc returns 0
5145 : * Add stuff to allow compilation on non-ANSI compilers
5146 : from kpv@research.att.com
5147 :
5148 : V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
5149 : * removed potential for odd address access in prev_chunk
5150 : * removed dependency on getpagesize.h
5151 : * misc cosmetics and a bit more internal documentation
5152 : * anticosmetics: mangled names in macros to evade debugger strangeness
5153 : * tested on sparc, hp-700, dec-mips, rs6000
5154 : with gcc & native cc (hp, dec only) allowing
5155 : Detlefs & Zorn comparison study (in SIGPLAN Notices.)
5156 :
5157 : Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
5158 : * Based loosely on libg++-1.2X malloc. (It retains some of the overall
5159 : structure of old version, but most details differ.)
5160 :
5161 : */
|
