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