Subversion Repositories HelenOS-historic

Rev

Rev 1656 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

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