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