Debian Codegraph @

src/dlmalloc.c

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