Context Navigation

heap.cfa @ 508cff0

Last change on this file since 508cff0 was df2e00f, checked in by Andrew Beach <ajbeach@…>, 3 months ago
Made heap pass the invariant check. We should be able to enable invariants on the standard library. Also added the reproductions for new trac trickets.
Property mode set to `100644`
File size: 69.4 KB

Line
1	//
2	// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
3	//
4	// The contents of this file are covered under the licence agreement in the
5	// file "LICENCE" distributed with Cforall.
6	//
7	// heap.cfa --
8	//
9	// Author : Peter A. Buhr
10	// Created On : Tue Dec 19 21:58:35 2017
11	// Last Modified By : Peter A. Buhr
12	// Last Modified On : Wed Aug 7 10:14:47 2024
13	// Update Count : 1646
14	//
15
16	#include <stdio.h>
17	#include <string.h> // memset, memcpy
18	#include <limits.h> // ULONG_MAX
19	#include <errno.h> // errno, ENOMEM, EINVAL
20	#include <unistd.h> // STDERR_FILENO, sbrk, sysconf, write
21	#include <sys/mman.h> // mmap, munmap
22	extern "C" {
23	#include <sys/sysinfo.h> // get_nprocs
24	} // extern "C"
25
26	#include "heap.hfa"
27	#include "bits/align.hfa" // libAlign
28	#include "bits/defs.hfa" // likely, unlikely
29	#include "concurrency/kernel/fwd.hfa" // disable_interrupts, enable_interrupts
30	#include "startup.hfa" // STARTUP_PRIORITY_MEMORY
31	#include "math.hfa" // ceiling, min
32	#include "bitmanip.hfa" // is_pow2, ceiling2
33
34	// supported mallopt options
35	#ifndef M_MMAP_THRESHOLD
36	#define M_MMAP_THRESHOLD (-1)
37	#endif // M_MMAP_THRESHOLD
38
39	#ifndef M_TOP_PAD
40	#define M_TOP_PAD (-2)
41	#endif // M_TOP_PAD
42
43	#define FASTLOOKUP // use O(1) table lookup from allocation size to bucket size
44	#define OWNERSHIP // return freed memory to owner thread
45	#define RETURNSPIN // toggle spinlock / lockfree queue
46	#if ! defined( OWNERSHIP ) && defined( RETURNSPIN )
47	#warning "RETURNSPIN is ignored without OWNERSHIP; suggest commenting out RETURNSPIN"
48	#endif // ! OWNERSHIP && RETURNSPIN
49
50	#define CACHE_ALIGN 64
51	#define CALIGN __attribute__(( aligned(CACHE_ALIGN) ))
52
53	#define TLSMODEL __attribute__(( tls_model("initial-exec") ))
54
55	#define __STATISTICS__
56
57	enum {
58	// The default extension heap amount in units of bytes. When the current heap reaches the brk address, the brk
59	// address is extended by the extension amount.
60	__CFA_DEFAULT_HEAP_EXPANSION__ = 10 * 1024 * 1024,
61
62	// The mmap crossover point during allocation. Allocations less than this amount are allocated from buckets; values
63	// greater than or equal to this value are mmap from the operating system.
64	__CFA_DEFAULT_MMAP_START__ = 512 * 1024 + 1,
65
66	// The default unfreed storage amount in units of bytes. When the uC++ program ends it subtracts this amount from
67	// the malloc/free counter to adjust for storage the program does not free.
68	__CFA_DEFAULT_HEAP_UNFREED__ = 0
69	}; // enum
70
71
72	//####################### Heap Trace/Print ####################
73
74
75	static bool traceHeap = false;
76
77	inline bool traceHeap() libcfa_public { return traceHeap; }
78
79	bool traceHeapOn() libcfa_public {
80	bool temp = traceHeap;
81	traceHeap = true;
82	return temp;
83	} // traceHeapOn
84
85	bool traceHeapOff() libcfa_public {
86	bool temp = traceHeap;
87	traceHeap = false;
88	return temp;
89	} // traceHeapOff
90
91	bool traceHeapTerm() libcfa_public { return false; }
92
93
94	static bool prtFree = false;
95
96	bool prtFree() {
97	return prtFree;
98	} // prtFree
99
100	bool prtFreeOn() {
101	bool temp = prtFree;
102	prtFree = true;
103	return temp;
104	} // prtFreeOn
105
106	bool prtFreeOff() {
107	bool temp = prtFree;
108	prtFree = false;
109	return temp;
110	} // prtFreeOff
111
112
113	//######################### Helpers #########################
114
115
116	// CFA generic Bsearchl does not inline, so substitute with hand-coded binary-search.
117	inline __attribute__((always_inline))
118	static size_t Bsearchl( unsigned int key, const unsigned int vals[], size_t dim ) {
119	size_t l = 0, m, h = dim;
120	while ( l < h ) {
121	m = (l + h) / 2;
122	if ( (unsigned int &)(vals[m]) < key ) { // cast away const
123	l = m + 1;
124	} else {
125	h = m;
126	} // if
127	} // while
128	return l;
129	} // Bsearchl
130
131
132	// pause to prevent excess processor bus usage
133	#if defined( __i386 ) \|\| defined( __x86_64 )
134	#define Pause() __asm__ __volatile__ ( "pause" : : : )
135	#elif defined(__ARM_ARCH)
136	#define Pause() __asm__ __volatile__ ( "YIELD" : : : )
137	#else
138	#error unsupported architecture
139	#endif
140
141	typedef volatile uintptr_t SpinLock_t;
142
143	static inline __attribute__((always_inline)) void lock( volatile SpinLock_t & slock ) {
144	enum { SPIN_START = 4, SPIN_END = 64 * 1024, };
145	unsigned int spin = SPIN_START;
146
147	for ( unsigned int i = 1;; i += 1 ) {
148	if ( slock == 0 && __atomic_test_and_set( &slock, __ATOMIC_ACQUIRE ) == 0 ) break; // Fence
149	for ( volatile unsigned int s = 0; s < spin; s += 1 ) Pause(); // exponential spin
150	spin += spin; // powers of 2
151	//if ( i % 64 == 0 ) spin += spin; // slowly increase by powers of 2
152	if ( spin > SPIN_END ) spin = SPIN_END; // cap spinning
153	} // for
154	} // spin_lock
155
156	static inline __attribute__((always_inline)) void unlock( volatile SpinLock_t & slock ) {
157	__atomic_clear( &slock, __ATOMIC_RELEASE ); // Fence
158	} // spin_unlock
159
160
161	//####################### Heap Statistics ####################
162
163
164	#ifdef __STATISTICS__
165	enum { CntTriples = 12 }; // number of counter triples
166	enum { MALLOC, AALLOC, CALLOC, MEMALIGN, AMEMALIGN, CMEMALIGN, RESIZE, REALLOC, FREE };
167
168	struct StatsOverlay { // overlay for iteration
169	unsigned int calls, calls_0;
170	unsigned long long int request, alloc;
171	};
172
173	// Heap statistics counters.
174	union HeapStatistics {
175	struct { // minimum qualification
176	unsigned int malloc_calls, malloc_0_calls;
177	unsigned long long int malloc_storage_request, malloc_storage_alloc;
178	unsigned int aalloc_calls, aalloc_0_calls;
179	unsigned long long int aalloc_storage_request, aalloc_storage_alloc;
180	unsigned int calloc_calls, calloc_0_calls;
181	unsigned long long int calloc_storage_request, calloc_storage_alloc;
182	unsigned int memalign_calls, memalign_0_calls;
183	unsigned long long int memalign_storage_request, memalign_storage_alloc;
184	unsigned int amemalign_calls, amemalign_0_calls;
185	unsigned long long int amemalign_storage_request, amemalign_storage_alloc;
186	unsigned int cmemalign_calls, cmemalign_0_calls;
187	unsigned long long int cmemalign_storage_request, cmemalign_storage_alloc;
188	unsigned int resize_calls, resize_0_calls;
189	unsigned long long int resize_storage_request, resize_storage_alloc;
190	unsigned int realloc_calls, realloc_0_calls;
191	unsigned long long int realloc_storage_request, realloc_storage_alloc;
192	unsigned int free_calls, free_null_0_calls;
193	unsigned long long int free_storage_request, free_storage_alloc;
194	unsigned int return_pulls, return_pushes;
195	unsigned long long int return_storage_request, return_storage_alloc;
196	unsigned int mmap_calls, mmap_0_calls; // no zero calls
197	unsigned long long int mmap_storage_request, mmap_storage_alloc;
198	unsigned int munmap_calls, munmap_0_calls; // no zero calls
199	unsigned long long int munmap_storage_request, munmap_storage_alloc;
200	};
201	struct StatsOverlay counters[CntTriples]; // overlay for iteration
202	}; // HeapStatistics
203
204	static_assert( sizeof(HeapStatistics) == CntTriples * sizeof(StatsOverlay),
205	"Heap statistics counter-triplets does not match with array size" );
206
207	static void HeapStatisticsCtor( HeapStatistics & stats ) {
208	memset( &stats, '\0', sizeof(stats) ); // very fast
209	// for ( unsigned int i = 0; i < CntTriples; i += 1 ) {
210	// stats.counters[i].calls = stats.counters[i].calls_0 = stats.counters[i].request = stats.counters[i].alloc = 0;
211	// } // for
212	} // HeapStatisticsCtor
213
214	static HeapStatistics & ?+=?( HeapStatistics & lhs, const HeapStatistics & rhs ) {
215	for ( unsigned int i = 0; i < CntTriples; i += 1 ) {
216	lhs.counters[i].calls += rhs.counters[i].calls;
217	lhs.counters[i].calls_0 += rhs.counters[i].calls_0;
218	lhs.counters[i].request += rhs.counters[i].request;
219	lhs.counters[i].alloc += rhs.counters[i].alloc;
220	} // for
221	return lhs;
222	} // ?+=?
223	#endif // __STATISTICS__
224
225
226	// Recursive definitions: HeapManager needs size of bucket array and bucket area needs sizeof HeapManager storage.
227	// Break recursion by hardcoding number of buckets and statically checking number is correct after bucket array defined.
228	enum { NoBucketSizes = 91 }; // number of buckets sizes
229
230	struct Heap {
231	struct Storage {
232	struct Header { // header
233	union Kind {
234	struct RealHeader { // 4-byte word => 8-byte header, 8-byte word => 16-byte header
235	union {
236	// 2nd low-order bit => zero filled, 3rd low-order bit => mmapped
237	// FreeHeader * home; // allocated block points back to home locations (must overlay alignment)
238	void * home; // allocated block points back to home locations (must overlay alignment)
239	size_t blockSize; // size for munmap (must overlay alignment)
240	Storage * next; // freed block points to next freed block of same size
241	};
242	size_t size; // allocation size in bytes
243	} real; // RealHeader
244
245	struct FakeHeader {
246	uintptr_t alignment; // 1st low-order bit => fake header & alignment
247	uintptr_t offset;
248	} fake; // FakeHeader
249	} kind; // Kind
250	} header; // Header
251
252	char pad[libAlign() - sizeof( Header )];
253	char data[0]; // storage
254	}; // Storage
255
256	static_assert( libAlign() >= sizeof( Storage ), "minimum alignment < sizeof( Storage )" );
257
258	struct CALIGN FreeHeader {
259	#ifdef OWNERSHIP
260	#ifdef RETURNSPIN
261	SpinLock_t returnLock;
262	#endif // RETURNSPIN
263	Storage * returnList; // other thread return list
264	#endif // OWNERSHIP
265
266	Storage * freeList; // thread free list
267	Heap * homeManager; // heap owner (free storage to bucket, from bucket to heap)
268	size_t blockSize; // size of allocations on this list
269	}; // FreeHeader
270
271	FreeHeader freeLists[NoBucketSizes]; // buckets for different allocation sizes
272	void * heapBuffer; // start of free storage in buffer
273	size_t heapReserve; // amount of remaining free storage in buffer
274
275	#if defined( __STATISTICS__ ) \|\| defined( __CFA_DEBUG__ )
276	Heap * nextHeapManager; // intrusive link of existing heaps; traversed to collect statistics or check unfreed storage
277	#endif // __STATISTICS__ \|\| __CFA_DEBUG__
278	Heap * nextFreeHeapManager; // intrusive link of free heaps from terminated threads; reused by new threads
279
280	#ifdef __CFA_DEBUG__
281	ptrdiff_t allocUnfreed; // running total of allocations minus frees; can be negative
282	#endif // __CFA_DEBUG__
283
284	#ifdef __STATISTICS__
285	HeapStatistics stats; // local statistic table for this heap
286	#endif // __STATISTICS__
287	}; // Heap
288
289
290	struct HeapMaster {
291	SpinLock_t extLock; // protects allocation-buffer extension
292	SpinLock_t mgrLock; // protects freeHeapManagersList, heapManagersList, heapManagersStorage, heapManagersStorageEnd
293
294	void * heapBegin; // start of heap
295	void * heapEnd; // logical end of heap
296	size_t heapRemaining; // amount of storage not allocated in the current chunk
297	size_t pageSize; // architecture pagesize
298	size_t heapExpand; // sbrk advance
299	size_t mmapStart; // cross over point for mmap
300	unsigned int maxBucketsUsed; // maximum number of buckets in use
301
302	Heap * heapManagersList; // heap-list head
303	Heap * freeHeapManagersList; // free-list head
304
305	// Heap superblocks are not linked; heaps in superblocks are linked via intrusive links.
306	Heap * heapManagersStorage; // next heap to use in heap superblock
307	Heap * heapManagersStorageEnd; // logical heap outside of superblock's end
308
309	#ifdef __STATISTICS__
310	HeapStatistics stats; // global stats for thread-local heaps to add there counters when exiting
311	unsigned long int threads_started, threads_exited; // counts threads that have started and exited
312	unsigned long int reused_heap, new_heap; // counts reusability of heaps
313	unsigned int sbrk_calls;
314	unsigned long long int sbrk_storage;
315	int stats_fd;
316	#endif // __STATISTICS__
317	}; // HeapMaster
318
319
320	#ifdef FASTLOOKUP
321	enum { LookupSizes = 65_536 + sizeof(Heap.Storage) }; // number of fast lookup sizes
322	static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes
323	#endif // FASTLOOKUP
324
325	static volatile bool heapMasterBootFlag = false; // trigger for first heap
326	static HeapMaster heapMaster @= {}; // program global
327
328	static void heapMasterCtor();
329	static void heapMasterDtor();
330	static Heap * getHeap();
331
332
333	// Size of array must harmonize with NoBucketSizes and individual bucket sizes must be multiple of 16.
334	// Smaller multiples of 16 and powers of 2 are common allocation sizes, so make them generate the minimum required bucket size.
335	// malloc(0) returns 0p, so no bucket is necessary for 0 bytes returning an address that can be freed.
336	static const unsigned int bucketSizes[] @= { // different bucket sizes
337	16 + sizeof(Heap.Storage), 32 + sizeof(Heap.Storage), 48 + sizeof(Heap.Storage), 64 + sizeof(Heap.Storage), // 4
338	96 + sizeof(Heap.Storage), 112 + sizeof(Heap.Storage), 128 + sizeof(Heap.Storage), // 3
339	160, 192, 224, 256 + sizeof(Heap.Storage), // 4
340	320, 384, 448, 512 + sizeof(Heap.Storage), // 4
341	640, 768, 896, 1_024 + sizeof(Heap.Storage), // 4
342	1_536, 2_048 + sizeof(Heap.Storage), // 2
343	2_560, 3_072, 3_584, 4_096 + sizeof(Heap.Storage), // 4
344	6_144, 8_192 + sizeof(Heap.Storage), // 2
345	9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360, 16_384 + sizeof(Heap.Storage), // 8
346	18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720, 32_768 + sizeof(Heap.Storage), // 8
347	36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440, 65_536 + sizeof(Heap.Storage), // 8
348	73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880, 131_072 + sizeof(Heap.Storage), // 8
349	147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760, 262_144 + sizeof(Heap.Storage), // 8
350	294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520, 524_288 + sizeof(Heap.Storage), // 8
351	655_360, 786_432, 917_504, 1_048_576 + sizeof(Heap.Storage), // 4
352	1_179_648, 1_310_720, 1_441_792, 1_572_864, 1_703_936, 1_835_008, 1_966_080, 2_097_152 + sizeof(Heap.Storage), // 8
353	2_621_440, 3_145_728, 3_670_016, 4_194_304 + sizeof(Heap.Storage), // 4
354	};
355
356	static_assert( sizeof(bucketSizes) == NoBucketSizes * sizeof(unsigned int), "size of bucket array wrong" );
357
358
359	// extern visibility, used by runtime kernel
360	libcfa_public size_t __page_size; // architecture pagesize
361	libcfa_public int __map_prot; // common mmap/mprotect protection
362
363
364	// Thread-local storage is allocated lazily when the storage is accessed.
365	static __thread size_t PAD1 CALIGN TLSMODEL __attribute__(( unused )); // protect false sharing
366	static __thread Heap * heapManager CALIGN TLSMODEL;
367	static __thread bool heapManagerBootFlag CALIGN TLSMODEL = false;
368	static __thread size_t PAD2 CALIGN TLSMODEL __attribute__(( unused )); // protect further false sharing
369
370
371	// declare helper functions for HeapMaster
372	void noMemory(); // forward, called by "builtin_new" when malloc returns 0
373
374
375	void heapMasterCtor() with( heapMaster ) {
376	// Singleton pattern to initialize heap master
377
378	verify( bucketSizes[0] == (16 + sizeof(Heap.Storage)) );
379
380	__page_size = sysconf( _SC_PAGESIZE );
381	__map_prot = PROT_READ \| PROT_WRITE \| PROT_EXEC;
382
383	extLock = 0;
384	mgrLock = 0;
385
386	char * end = (char *)sbrk( 0 );
387	heapBegin = heapEnd = sbrk( (char *)ceiling2( (long unsigned int)end, libAlign() ) - end ); // move start of heap to multiple of alignment
388	heapRemaining = 0;
389	heapExpand = malloc_expansion();
390	mmapStart = malloc_mmap_start();
391
392	// find the closest bucket size less than or equal to the mmapStart size
393	maxBucketsUsed = Bsearchl( mmapStart, bucketSizes, NoBucketSizes ); // binary search
394
395	verify( (mmapStart >= pageSize) && (bucketSizes[NoBucketSizes - 1] >= mmapStart) );
396	verify( maxBucketsUsed < NoBucketSizes ); // subscript failure ?
397	verify( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ?
398
399	heapManagersList = 0p;
400	freeHeapManagersList = 0p;
401
402	heapManagersStorage = 0p;
403	heapManagersStorageEnd = 0p;
404
405	#ifdef __STATISTICS__
406	HeapStatisticsCtor( stats ); // clear statistic counters
407	threads_started = threads_exited = 0;
408	reused_heap = new_heap = 0;
409	sbrk_calls = sbrk_storage = 0;
410	stats_fd = STDERR_FILENO;
411	#endif // __STATISTICS__
412
413	#ifdef FASTLOOKUP
414	for ( unsigned int i = 0, idx = 0; i < LookupSizes; i += 1 ) {
415	if ( i > bucketSizes[idx] ) idx += 1;
416	lookup[i] = idx;
417	verify( i <= bucketSizes[idx] );
418	verify( (i <= 32 && idx == 0) \|\| (i > bucketSizes[idx - 1]) );
419	} // for
420	#endif // FASTLOOKUP
421
422	heapMasterBootFlag = true;
423	} // heapMasterCtor
424
425
426	#define NO_MEMORY_MSG "** Error ** insufficient heap memory available to allocate %zd new bytes."
427
428	Heap * getHeap() with( heapMaster ) {
429	Heap * heap;
430	if ( freeHeapManagersList ) { // free heap for reused ?
431	heap = freeHeapManagersList;
432	freeHeapManagersList = heap->nextFreeHeapManager;
433
434	#ifdef __STATISTICS__
435	reused_heap += 1;
436	#endif // __STATISTICS__
437	} else { // free heap not found, create new
438	// Heap size is about 12K, FreeHeader (128 bytes because of cache alignment) * NoBucketSizes (91) => 128 heaps *
439	// 12K ~= 120K byte superblock. Where 128-heap superblock handles a medium sized multi-processor server.
440	size_t remaining = heapManagersStorageEnd - heapManagersStorage; // remaining free heaps in superblock
441	if ( ! heapManagersStorage \|\| remaining == 0 ) {
442	// Each block of heaps is a multiple of the number of cores on the computer.
443	int HeapDim = get_nprocs(); // get_nprocs_conf does not work
444	size_t size = HeapDim * sizeof( Heap );
445
446	heapManagersStorage = (Heap *)mmap( 0, size, PROT_READ \| PROT_WRITE, MAP_PRIVATE \| MAP_ANONYMOUS, -1, 0 );
447	if ( unlikely( heapManagersStorage == (Heap *)MAP_FAILED ) ) { // failed ?
448	if ( errno == ENOMEM ) abort( NO_MEMORY_MSG, size ); // no memory
449	// Do not call strerror( errno ) as it may call malloc.
450	abort( "** Error ** attempt to allocate block of heaps of size %zu bytes and mmap failed with errno %d.", size, errno );
451	} // if
452	heapManagersStorageEnd = &heapManagersStorage[HeapDim]; // outside array
453	} // if
454
455	heap = heapManagersStorage;
456	heapManagersStorage = heapManagersStorage + 1; // bump next heap
457
458	#if defined( __STATISTICS__ ) \|\| defined( __CFA_DEBUG__ )
459	heap->nextHeapManager = heapManagersList;
460	#endif // __STATISTICS__ \|\| __CFA_DEBUG__
461	heapManagersList = heap;
462
463	#ifdef __STATISTICS__
464	new_heap += 1;
465	#endif // __STATISTICS__
466
467	with( *heap ) {
468	for ( unsigned int j = 0; j < NoBucketSizes; j += 1 ) { // initialize free lists
469	#ifdef OWNERSHIP
470	#ifdef RETURNSPIN
471	freeLists[j].returnLock = 0;
472	freeLists[j].returnList = 0p;
473	#endif // RETURNSPIN
474	#endif // OWNERSHIP
475
476	freeLists[j].freeList = 0p;
477	freeLists[j].homeManager = heap;
478	freeLists[j].blockSize = bucketSizes[j];
479	} // for
480
481	heapBuffer = 0p;
482	heapReserve = 0;
483	nextFreeHeapManager = 0p;
484	#ifdef __CFA_DEBUG__
485	allocUnfreed = 0;
486	#endif // __CFA_DEBUG__
487	heapManagerBootFlag = true;
488	} // with
489	} // if
490
491	return heap;
492	} // getHeap
493
494
495	void heapManagerCtor() libcfa_public {
496	if ( unlikely( ! heapMasterBootFlag ) ) heapMasterCtor();
497
498	lock( heapMaster.mgrLock ); // protect heapMaster counters
499
500	assert( ! heapManagerBootFlag );
501
502	// get storage for heap manager
503
504	heapManager = getHeap();
505
506	#ifdef __STATISTICS__
507	HeapStatisticsCtor( heapManager->stats ); // heap local
508	heapMaster.threads_started += 1;
509	#endif // __STATISTICS__
510
511	unlock( heapMaster.mgrLock );
512	} // heapManagerCtor
513
514
515	void heapManagerDtor() libcfa_public {
516	if ( unlikely( ! heapManagerBootFlag ) ) return; // thread never used ?
517
518	lock( heapMaster.mgrLock );
519
520	// place heap on list of free heaps for reusability
521	heapManager->nextFreeHeapManager = heapMaster.freeHeapManagersList;
522	heapMaster.freeHeapManagersList = heapManager;
523
524	#ifdef __STATISTICS__
525	heapMaster.stats += heapManager->stats; // retain this heap's statistics
526	heapMaster.threads_exited += 1;
527	#endif // __STATISTICS__
528
529	// Do not set heapManager to NULL because it is used after Cforall is shutdown but before the program shuts down.
530
531	heapManagerBootFlag = false;
532	unlock( heapMaster.mgrLock );
533	} // heapManagerDtor
534
535
536	//####################### Memory Allocation Routines Helpers ####################
537
538
539	extern int cfa_main_returned; // from interpose.cfa
540	extern "C" {
541	void memory_startup( void ) { // singleton => called once at start of program
542	if ( ! heapMasterBootFlag ) heapManagerCtor(); // sanity check
543	} // memory_startup
544
545	void memory_shutdown( void ) {
546	heapManagerDtor();
547	} // memory_shutdown
548
549	void heapAppStart() { // called by __cfaabi_appready_startup
550	verify( heapManager );
551	#ifdef __CFA_DEBUG__
552	heapManager->allocUnfreed = 0; // clear prior allocation counts
553	#endif // __CFA_DEBUG__
554
555	#ifdef __STATISTICS__
556	HeapStatisticsCtor( heapManager->stats ); // clear prior statistic counters
557	#endif // __STATISTICS__
558	} // heapAppStart
559
560	void heapAppStop() { // called by __cfaabi_appready_startdown
561	fclose( stdin ); fclose( stdout ); // free buffer storage
562	if ( ! cfa_main_returned ) return; // do not check unfreed storage if exit called
563
564	#ifdef __STATISTICS__
565	if ( getenv( "CFA_MALLOC_STATS" ) ) { // check for external printing
566	malloc_stats();
567	} // if
568	#endif // __STATISTICS__
569
570	#ifdef __CFA_DEBUG__
571	// allocUnfreed is set to 0 when a heap is created and it accumulates any unfreed storage during its multiple thread
572	// usages. At the end, add up each heap allocUnfreed value across all heaps to get the total unfreed storage.
573	ptrdiff_t allocUnfreed = 0;
574	for ( Heap * heap = heapMaster.heapManagersList; heap; heap = heap->nextHeapManager ) {
575	allocUnfreed += heap->allocUnfreed;
576	} // for
577
578	allocUnfreed -= malloc_unfreed(); // subtract any user specified unfreed storage
579	if ( allocUnfreed > 0 ) {
580	// DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
581	char helpText[512];
582	__cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText),
583	"CFA warning (UNIX pid:%ld) : program terminating with %td(%#tx) bytes of storage allocated but not freed.\n"
584	"Possible cause is mismatched allocation/deallocation calls (malloc/free), direct constructor call without a direct destructor call, or system/library routines not freeing storage.\n",
585	(long int)getpid(), allocUnfreed, allocUnfreed ); // always print the UNIX pid
586	} // if
587	#endif // __CFA_DEBUG__
588	} // heapAppStop
589	} // extern "C"
590
591
592	#ifdef __STATISTICS__
593	#define prtFmt \
594	"\nHeap statistics: (storage request / allocation)\n" \
595	" malloc >0 calls %'u; 0 calls %'u; storage %'llu / %'llu bytes\n" \
596	" aalloc >0 calls %'u; 0 calls %'u; storage %'llu / %'llu bytes\n" \
597	" calloc >0 calls %'u; 0 calls %'u; storage %'llu / %'llu bytes\n" \
598	" memalign >0 calls %'u; 0 calls %'u; storage %'llu / %'llu bytes\n" \
599	" amemalign >0 calls %'u; 0 calls %'u; storage %'llu / %'llu bytes\n" \
600	" cmemalign >0 calls %'u; 0 calls %'u; storage %'llu / %'llu bytes\n" \
601	" resize >0 calls %'u; 0 calls %'u; storage %'llu / %'llu bytes\n" \
602	" realloc >0 calls %'u; 0 calls %'u; storage %'llu / %'llu bytes\n" \
603	" free !null calls %'u; null/0 calls %'u; storage %'llu / %'llu bytes\n" \
604	" return pulls %'u; pushes %'u; storage %'llu / %'llu bytes\n" \
605	" sbrk calls %'u; storage %'llu bytes\n" \
606	" mmap calls %'u; storage %'llu / %'llu bytes\n" \
607	" munmap calls %'u; storage %'llu / %'llu bytes\n" \
608	" threads started %'lu; exited %'lu\n" \
609	" heaps new %'lu; reused %'lu\n"
610
611	// Use "write" because streams may be shutdown when calls are made.
612	static int printStats( HeapStatistics & stats ) with( heapMaster, stats ) { // see malloc_stats
613	char helpText[sizeof(prtFmt) + 1024]; // space for message and values
614	return __cfaabi_bits_print_buffer( stats_fd, helpText, sizeof(helpText), prtFmt,
615	malloc_calls, malloc_0_calls, malloc_storage_request, malloc_storage_alloc,
616	aalloc_calls, aalloc_0_calls, aalloc_storage_request, aalloc_storage_alloc,
617	calloc_calls, calloc_0_calls, calloc_storage_request, calloc_storage_alloc,
618	memalign_calls, memalign_0_calls, memalign_storage_request, memalign_storage_alloc,
619	amemalign_calls, amemalign_0_calls, amemalign_storage_request, amemalign_storage_alloc,
620	cmemalign_calls, cmemalign_0_calls, cmemalign_storage_request, cmemalign_storage_alloc,
621	resize_calls, resize_0_calls, resize_storage_request, resize_storage_alloc,
622	realloc_calls, realloc_0_calls, realloc_storage_request, realloc_storage_alloc,
623	free_calls, free_null_0_calls, free_storage_request, free_storage_alloc,
624	return_pulls, return_pushes, return_storage_request, return_storage_alloc,
625	sbrk_calls, sbrk_storage,
626	mmap_calls, mmap_storage_request, mmap_storage_alloc,
627	munmap_calls, munmap_storage_request, munmap_storage_alloc,
628	threads_started, threads_exited,
629	new_heap, reused_heap
630	);
631	} // printStats
632
633	#define prtFmtXML \
634	"<malloc version=\"1\">\n" \
635	"<heap nr=\"0\">\n" \
636	"<sizes>\n" \
637	"</sizes>\n" \
638	"<total type=\"malloc\" >0 count=\"%'u;\" 0 count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
639	"<total type=\"aalloc\" >0 count=\"%'u;\" 0 count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
640	"<total type=\"calloc\" >0 count=\"%'u;\" 0 count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
641	"<total type=\"memalign\" >0 count=\"%'u;\" 0 count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
642	"<total type=\"amemalign\" >0 count=\"%'u;\" 0 count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
643	"<total type=\"cmemalign\" >0 count=\"%'u;\" 0 count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
644	"<total type=\"resize\" >0 count=\"%'u;\" 0 count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
645	"<total type=\"realloc\" >0 count=\"%'u;\" 0 count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
646	"<total type=\"free\" !null=\"%'u;\" 0 null/0=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
647	"<total type=\"return\" pulls=\"%'u;\" 0 pushes=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
648	"<total type=\"sbrk\" count=\"%'u;\" size=\"%'llu\"/> bytes\n" \
649	"<total type=\"mmap\" count=\"%'u;\" size=\"%'llu / %'llu\" / > bytes\n" \
650	"<total type=\"munmap\" count=\"%'u;\" size=\"%'llu / %'llu\"/> bytes\n" \
651	"<total type=\"threads\" started=\"%'lu;\" exited=\"%'lu\"/>\n" \
652	"<total type=\"heaps\" new=\"%'lu;\" reused=\"%'lu\"/>\n" \
653	"</malloc>"
654
655	static int printStatsXML( HeapStatistics & stats, FILE * stream ) with( heapMaster, stats ) { // see malloc_info
656	char helpText[sizeof(prtFmtXML) + 1024]; // space for message and values
657	return __cfaabi_bits_print_buffer( fileno( stream ), helpText, sizeof(helpText), prtFmtXML,
658	malloc_calls, malloc_0_calls, malloc_storage_request, malloc_storage_alloc,
659	aalloc_calls, aalloc_0_calls, aalloc_storage_request, aalloc_storage_alloc,
660	calloc_calls, calloc_0_calls, calloc_storage_request, calloc_storage_alloc,
661	memalign_calls, memalign_0_calls, memalign_storage_request, memalign_storage_alloc,
662	amemalign_calls, amemalign_0_calls, amemalign_storage_request, amemalign_storage_alloc,
663	cmemalign_calls, cmemalign_0_calls, cmemalign_storage_request, cmemalign_storage_alloc,
664	resize_calls, resize_0_calls, resize_storage_request, resize_storage_alloc,
665	realloc_calls, realloc_0_calls, realloc_storage_request, realloc_storage_alloc,
666	free_calls, free_null_0_calls, free_storage_request, free_storage_alloc,
667	return_pulls, return_pushes, return_storage_request, return_storage_alloc,
668	sbrk_calls, sbrk_storage,
669	mmap_calls, mmap_storage_request, mmap_storage_alloc,
670	munmap_calls, munmap_storage_request, munmap_storage_alloc,
671	threads_started, threads_exited,
672	new_heap, reused_heap
673	);
674	} // printStatsXML
675
676	static HeapStatistics & collectStats( HeapStatistics & stats ) with( heapMaster ) {
677	lock( heapMaster.mgrLock );
678
679	stats += heapMaster.stats;
680	for ( Heap * heap = heapManagersList; heap; heap = heap->nextHeapManager ) {
681	stats += heap->stats;
682	} // for
683
684	unlock( heapMaster.mgrLock );
685	return stats;
686	} // collectStats
687
688	static inline void clearStats() {
689	lock( heapMaster.mgrLock );
690
691	// Zero the heap master and all active thread heaps.
692	HeapStatisticsCtor( heapMaster.stats );
693	for ( Heap * heap = heapMaster.heapManagersList; heap; heap = heap->nextHeapManager ) {
694	HeapStatisticsCtor( heap->stats );
695	} // for
696
697	unlock( heapMaster.mgrLock );
698	} // clearStats
699	#endif // __STATISTICS__
700
701
702	static bool setMmapStart( size_t value ) with( heapMaster ) { // true => mmapped, false => sbrk
703	if ( value < __page_size \|\| bucketSizes[NoBucketSizes - 1] < value ) return false;
704	mmapStart = value; // set global
705
706	// find the closest bucket size less than or equal to the mmapStart size
707	maxBucketsUsed = Bsearchl( mmapStart, bucketSizes, NoBucketSizes ); // binary search
708
709	verify( maxBucketsUsed < NoBucketSizes ); // subscript failure ?
710	verify( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ?
711	return true;
712	} // setMmapStart
713
714
715	// <-------+----------------------------------------------------> bsize (bucket size)
716	// \|header \|addr
717	//==================================================================================
718	// align/offset \|
719	// <-----------------<------------+-----------------------------> bsize (bucket size)
720	// \|fake-header \| addr
721	#define HeaderAddr( addr ) ((Heap.Storage.Header )( (char )addr - sizeof(Heap.Storage) ))
722	#define RealHeader( header ) ((Heap.Storage.Header )((char )header - header->kind.fake.offset))
723
724	// <-------<<--------------------- dsize ---------------------->> bsize (bucket size)
725	// \|header \|addr
726	//==================================================================================
727	// align/offset \|
728	// <------------------------------<<---------- dsize --------->>> bsize (bucket size)
729	// \|fake-header \|addr
730	#define DataStorage( bsize, addr, header ) (bsize - ( (char )addr - (char )header ))
731
732
733	inline __attribute__((always_inline))
734	static void checkAlign( size_t alignment ) {
735	if ( unlikely( alignment < libAlign() \|\| ! is_pow2( alignment ) ) ) {
736	abort( "** Error ** alignment %zu for memory allocation is less than %d and/or not a power of 2.", alignment, libAlign() );
737	} // if
738	} // checkAlign
739
740
741	inline __attribute__((always_inline))
742	static void checkHeader( bool check, const char name[], void * addr ) {
743	if ( unlikely( check ) ) { // bad address ?
744	abort( "** Error ** attempt to %s storage %p with address outside the heap.\n"
745	"Possible cause is duplicate free on same block or overwriting of memory.",
746	name, addr );
747	} // if
748	} // checkHeader
749
750
751	// Manipulate sticky bits stored in unused 3 low-order bits of an address.
752	// bit0 => alignment => fake header
753	// bit1 => zero filled (calloc)
754	// bit2 => mapped allocation versus sbrk
755	#define StickyBits( header ) (((header)->kind.real.blockSize & 0x7))
756	#define ClearStickyBits( addr ) (typeof(addr))((uintptr_t)(addr) & ~7)
757	#define MarkAlignmentBit( align ) ((align) \| 1)
758	#define AlignmentBit( header ) ((((header)->kind.fake.alignment) & 1))
759	#define ClearAlignmentBit( header ) (((header)->kind.fake.alignment) & ~1)
760	#define ZeroFillBit( header ) ((((header)->kind.real.blockSize) & 2))
761	#define ClearZeroFillBit( header ) ((((header)->kind.real.blockSize) &= ~2))
762	#define MarkZeroFilledBit( header ) ((header)->kind.real.blockSize \|= 2)
763	#define MmappedBit( header ) ((((header)->kind.real.blockSize) & 4))
764	#define MarkMmappedBit( size ) ((size) \| 4)
765
766
767	inline __attribute__((always_inline))
768	static void fakeHeader( Heap.Storage.Header *& header, size_t & alignment ) {
769	if ( unlikely( AlignmentBit( header ) ) ) { // fake header ?
770	alignment = ClearAlignmentBit( header ); // clear flag from value
771	#ifdef __CFA_DEBUG__
772	checkAlign( alignment ); // check alignment
773	#endif // __CFA_DEBUG__
774	header = RealHeader( header ); // backup from fake to real header
775	} else {
776	alignment = libAlign(); // => no fake header
777	} // if
778	} // fakeHeader
779
780
781	inline __attribute__((always_inline))
782	static bool headers( const char name[] __attribute__(( unused )), void * addr, Heap.Storage.Header *& header,
783	Heap.FreeHeader & freeHead, size_t & size, size_t & alignment ) with( heapMaster, heapManager ) {
784	header = HeaderAddr( addr );
785
786	#ifdef __CFA_DEBUG__
787	checkHeader( header < (Heap.Storage.Header *)heapBegin, name, addr ); // bad low address ?
788	#endif // __CFA_DEBUG__
789
790	if ( likely( ! StickyBits( header ) ) ) { // no sticky bits ?
791	freeHead = (Heap.FreeHeader *)(header->kind.real.home);
792	alignment = libAlign();
793	} else {
794	fakeHeader( header, alignment );
795	if ( unlikely( MmappedBit( header ) ) ) { // mmapped storage ?
796	verify( addr < heapBegin \|\| heapEnd < addr );
797	size = ClearStickyBits( header->kind.real.blockSize ); // mmap size
798	freeHead = 0p; // prevent uninitialized warning
799	return true;
800	} // if
801
802	freeHead = (Heap.FreeHeader *)(ClearStickyBits( header->kind.real.home ));
803	} // if
804	size = freeHead->blockSize;
805
806	#ifdef __CFA_DEBUG__
807	checkHeader( header < (Heap.Storage.Header )heapBegin \|\| (Heap.Storage.Header )heapEnd < header, name, addr ); // bad address ? (offset could be + or -)
808
809	Heap * homeManager;
810	if ( unlikely( freeHead == 0p \|\| // freed and only free-list node => null link
811	// freed and link points at another free block not to a bucket in the bucket array.
812	(homeManager = freeHead->homeManager, freeHead < &homeManager->freeLists[0] \|\|
813	&homeManager->freeLists[NoBucketSizes] <= freeHead ) ) ) {
814	abort( "** Error ** attempt to %s storage %p with corrupted header.\n"
815	"Possible cause is duplicate free on same block or overwriting of header information.",
816	name, addr );
817	} // if
818	#endif // __CFA_DEBUG__
819
820	return false;
821	} // headers
822
823
824	static void * master_extend( size_t size ) with( heapMaster ) {
825	lock( extLock );
826
827	ptrdiff_t rem = heapRemaining - size;
828	if ( unlikely( rem < 0 ) ) { // negative ?
829	// If the size requested is bigger than the current remaining storage, increase the size of the heap.
830
831	size_t increase = ceiling2( size > heapExpand ? size : heapExpand, libAlign() );
832	if ( unlikely( sbrk( increase ) == (void *)-1 ) ) { // failed, no memory ?
833	unlock( extLock );
834	abort( NO_MEMORY_MSG, size ); // give up
835	} // if
836
837	// Make storage executable for thunks.
838	if ( mprotect( (char *)heapEnd + heapRemaining, increase, __map_prot ) ) {
839	unlock( extLock );
840	abort( "** Error ** attempt to make heap storage executable for thunks and mprotect failed with errno %d.", errno );
841	} // if
842
843	rem = heapRemaining + increase - size;
844
845	#ifdef __STATISTICS__
846	sbrk_calls += 1;
847	sbrk_storage += increase;
848	#endif // __STATISTICS__
849	} // if
850
851	Heap.Storage * block = (Heap.Storage *)heapEnd;
852	heapRemaining = rem;
853	heapEnd = (char *)heapEnd + size;
854
855	unlock( extLock );
856	return block;
857	} // master_extend
858
859
860	__attribute__(( noinline ))
861	static void * manager_extend( size_t size ) with( *heapManager ) {
862	ptrdiff_t rem = heapReserve - size;
863
864	if ( unlikely( rem < 0 ) ) { // negative ?
865	// If the size requested is bigger than the current remaining reserve, use the current reserve to populate
866	// smaller freeLists, and increase the reserve.
867
868	rem = heapReserve; // positive
869
870	if ( (unsigned int)rem >= bucketSizes[0] ) { // minimal size ? otherwise ignore
871	size_t bucket;
872	#ifdef FASTLOOKUP
873	if ( likely( rem < LookupSizes ) ) bucket = lookup[rem];
874	#endif // FASTLOOKUP
875	bucket = Bsearchl( rem, bucketSizes, heapMaster.maxBucketsUsed );
876	verify( 0 <= bucket && bucket <= heapMaster.maxBucketsUsed );
877	Heap.FreeHeader * freeHead = &(freeLists[bucket]);
878
879	// The remaining storage may not be bucket size, whereas all other allocations are. Round down to previous
880	// bucket size in this case.
881	if ( unlikely( freeHead->blockSize > (size_t)rem ) ) freeHead -= 1;
882	Heap.Storage * block = (Heap.Storage *)heapBuffer;
883
884	block->header.kind.real.next = freeHead->freeList; // push on stack
885	freeHead->freeList = block;
886	} // if
887
888	size_t increase = ceiling( size > ( heapMaster.heapExpand / 10 ) ? size : ( heapMaster.heapExpand / 10 ), libAlign() );
889	heapBuffer = master_extend( increase );
890	rem = increase - size;
891	} // if
892
893	Heap.Storage * block = (Heap.Storage *)heapBuffer;
894	heapReserve = rem;
895	heapBuffer = (char *)heapBuffer + size;
896
897	return block;
898	} // manager_extend
899
900
901	#ifdef __STATISTICS__
902	#define STAT_NAME __counter
903	#define STAT_PARM , unsigned int STAT_NAME
904	#define STAT_ARG( name ) , name
905	#define STAT_0_CNT( counter ) heapManager->stats.counters[counter].calls_0 += 1
906	#else
907	#define STAT_NAME
908	#define STAT_PARM
909	#define STAT_ARG( name )
910	#define STAT_0_CNT( counter )
911	#endif // __STATISTICS__
912
913	#define BOOT_HEAP_MANAGER \
914	if ( unlikely( ! heapMasterBootFlag ) ) { \
915	heapManagerCtor(); /* trigger for first heap */ \
916	} /* if */ \
917	verify( heapManager );
918
919	#define __NONNULL_0_ALLOC__ /* Uncomment to return non-null address for malloc( 0 ). */
920	#ifndef __NONNULL_0_ALLOC__
921	#define __NULL_0_ALLOC__( counter, ... ) /* 0 byte allocation returns null pointer */ \
922	if ( unlikely( size == 0 ) ) { \
923	STAT_0_CNT( counter ); \
924	__VA_ARGS__; /* call routine, if specified */ \
925	return 0p; \
926	} /* if */
927	#else
928	#define __NULL_0_ALLOC__( counter, ... )
929	#endif // __NONNULL_0_ALLOC__
930
931	#ifdef __DEBUG__
932	#define __OVERFLOW_MALLOC__( ... ) \
933	if ( unlikely( size > ULONG_MAX - sizeof(Heap.Storage) ) ) { /* error check */ \
934	__VA_ARGS__; /* call routine, if specified */ \
935	return 0p; \
936	} /* if */
937	#else
938	#define __OVERFLOW_MALLOC__( ... )
939	#endif // __DEBUG__
940
941	#define PROLOG( counter, ... ) \
942	BOOT_HEAP_MANAGER; \
943	__NULL_0_ALLOC__( counter, __VA_ARGS__ ) \
944	__OVERFLOW_MALLOC__( __VA_ARGS__ )
945
946	#define SCRUB_SIZE 1024lu
947	// Do not use '\xfe' for scrubbing because dereferencing an address composed of it causes a SIGSEGV without a valid IP
948	// pointer in the interrupt frame.
949	#define SCRUB '\xff'
950
951	static void * doMalloc( size_t size STAT_PARM ) libcfa_nopreempt with( *heapManager ) {
952	PROLOG( STAT_NAME );
953
954	Heap.Storage * block; // pointer to new block of storage
955
956	// Look up size in the size list. Make sure the user request includes space for the header that must be allocated
957	// along with the block and is a multiple of the alignment size.
958	size_t tsize = size + sizeof(Heap.Storage);
959
960	#ifdef __STATISTICS__
961	#ifdef __NONNULL_0_ALLOC__
962	if ( unlikely( size == 0 ) ) // malloc( 0 ) ?
963	stats.counters[STAT_NAME].calls_0 += 1;
964	else
965	#endif // __NONNULL_0_ALLOC__
966	stats.counters[STAT_NAME].calls += 1;
967	stats.counters[STAT_NAME].request += size;
968	#endif // __STATISTICS__
969
970	#ifdef __CFA_DEBUG__
971	allocUnfreed += size;
972	#endif // __CFA_DEBUG__
973
974	if ( likely( tsize < heapMaster.mmapStart ) ) { // small size => sbrk
975	size_t bucket;
976	#ifdef FASTLOOKUP
977	if ( likely( tsize < LookupSizes ) ) bucket = lookup[tsize];
978	else
979	#endif // FASTLOOKUP
980	bucket = Bsearchl( tsize, bucketSizes, heapMaster.maxBucketsUsed );
981	verify( 0 <= bucket && bucket <= heapMaster.maxBucketsUsed );
982	Heap.FreeHeader * freeHead = &freeLists[bucket];
983
984	verify( freeHead <= &freeLists[heapMaster.maxBucketsUsed] ); // subscripting error ?
985	verify( tsize <= freeHead->blockSize ); // search failure ?
986
987	tsize = freeHead->blockSize; // total space needed for request
988	#ifdef __STATISTICS__
989	stats.counters[STAT_NAME].alloc += tsize;
990	#endif // __STATISTICS__
991
992	block = freeHead->freeList; // remove node from stack
993	if ( unlikely( block == 0p ) ) { // no free block ?
994	// Freelist for this size is empty, so check return list (OWNERSHIP), or carve it out of the heap if there
995	// is enough left, or get some more heap storage and carve it off.
996	#ifdef OWNERSHIP
997	if ( unlikely( freeHead->returnList ) ) { // race, get next time if lose race
998	#ifdef RETURNSPIN
999	lock( freeHead->returnLock );
1000	block = freeHead->returnList;
1001	freeHead->returnList = 0p;
1002	unlock( freeHead->returnLock );
1003	#else
1004	block = __atomic_exchange_n( &freeHead->returnList, 0p, __ATOMIC_SEQ_CST );
1005	#endif // RETURNSPIN
1006
1007	verify( block );
1008	#ifdef __STATISTICS__
1009	stats.return_pulls += 1;
1010	#endif // __STATISTICS__
1011
1012	// OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
1013
1014	freeHead->freeList = block->header.kind.real.next; // merge returnList into freeHead
1015	} else {
1016	#endif // OWNERSHIP
1017	// Do not leave kernel thread as manager_extend accesses heapManager.
1018	disable_interrupts();
1019	block = (Heap.Storage *)manager_extend( tsize ); // mutual exclusion on call
1020	enable_interrupts( false );
1021
1022	// OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
1023
1024	#ifdef __CFA_DEBUG__
1025	// Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first SCRUB_SIZE bytes.
1026	memset( block->data, SCRUB, min( SCRUB_SIZE, tsize - sizeof(Heap.Storage) ) );
1027	#endif // __CFA_DEBUG__
1028	#ifdef OWNERSHIP
1029	} // if
1030	#endif // OWNERSHIP
1031	} else {
1032	// Memory is scrubbed in doFree.
1033	freeHead->freeList = block->header.kind.real.next;
1034	} // if
1035
1036	block->header.kind.real.home = freeHead; // pointer back to free list of apropriate size
1037	} else { // large size => mmap
1038	if ( unlikely( size > ULONG_MAX - __page_size ) ) return 0p;
1039	tsize = ceiling2( tsize, __page_size ); // must be multiple of page size
1040
1041	#ifdef __STATISTICS__
1042	stats.counters[STAT_NAME].alloc += tsize;
1043	stats.mmap_calls += 1;
1044	stats.mmap_storage_request += size;
1045	stats.mmap_storage_alloc += tsize;
1046	#endif // __STATISTICS__
1047
1048	disable_interrupts();
1049	block = (Heap.Storage *)mmap( 0, tsize, __map_prot, MAP_PRIVATE \| MAP_ANONYMOUS, -1, 0 );
1050	enable_interrupts( false );
1051
1052	// OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
1053
1054	if ( unlikely( block == (Heap.Storage *)MAP_FAILED ) ) { // failed ?
1055	if ( errno == ENOMEM ) abort( NO_MEMORY_MSG, tsize ); // no memory
1056	// Do not call strerror( errno ) as it may call malloc.
1057	abort( "** Error ** attempt to allocate large object (> %zu) of size %zu bytes and mmap failed with errno %d.",
1058	size, heapMaster.mmapStart, errno );
1059	} // if
1060	block->header.kind.real.blockSize = MarkMmappedBit( tsize ); // storage size for munmap
1061
1062	#ifdef __CFA_DEBUG__
1063	// Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first SCRUB_SIZE bytes. The
1064	// rest of the storage set to 0 by mmap.
1065	memset( block->data, SCRUB, min( SCRUB_SIZE, tsize - sizeof(Heap.Storage) ) );
1066	#endif // __CFA_DEBUG__
1067	} // if
1068
1069	block->header.kind.real.size = size; // store allocation size
1070	void * addr = &(block->data); // adjust off header to user bytes
1071	verify( ((uintptr_t)addr & (libAlign() - 1)) == 0 ); // minimum alignment ?
1072
1073	#ifdef __CFA_DEBUG__
1074	if ( traceHeap() ) {
1075	char helpText[64];
1076	__cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText),
1077	"%p = Malloc( %zu ) (allocated %zu)\n", addr, size, tsize ); // print debug/nodebug
1078	} // if
1079	#endif // __CFA_DEBUG__
1080
1081	// poll_interrupts(); // call rollforward
1082
1083	return addr;
1084	} // doMalloc
1085
1086
1087	static void doFree( void * addr ) libcfa_nopreempt with( *heapManager ) {
1088	// char buf[64];
1089	// int len = sprintf( buf, "doFree addr %p\n", addr );
1090	// write( 2, buf, len );
1091
1092	verify( addr );
1093
1094	// detect free after thread-local storage destruction and use global stats in that case
1095
1096	Heap.Storage.Header * header;
1097	Heap.FreeHeader * freeHead;
1098	size_t size, alignment;
1099
1100	bool mapped = headers( "free", addr, header, freeHead, size, alignment );
1101	#if defined( __STATISTICS__ ) \|\| defined( __CFA_DEBUG__ )
1102	size_t rsize = header->kind.real.size; // optimization
1103	#endif // __STATISTICS__ \|\| __CFA_DEBUG__
1104
1105	// Do not move these down because heap can be null!
1106	#ifdef __STATISTICS__
1107	#ifdef __NONNULL_0_ALLOC__
1108	if ( unlikely( rsize == 0 ) ) // malloc( 0 ) ?
1109	stats.free_null_0_calls += 1;
1110	else
1111	#endif // __NONNULL_0_ALLOC__
1112	heapManager->stats.free_calls += 1; // count free amd implicit frees from resize/realloc
1113	stats.free_storage_request += rsize;
1114	stats.free_storage_alloc += size;
1115	#endif // __STATISTICS__
1116
1117	#ifdef __CFA_DEBUG__
1118	allocUnfreed -= rsize;
1119	#endif // __CFA_DEBUG__
1120
1121	if ( unlikely( mapped ) ) { // mmapped ?
1122	#ifdef __STATISTICS__
1123	stats.munmap_calls += 1;
1124	stats.munmap_storage_request += rsize;
1125	stats.munmap_storage_alloc += size;
1126	#endif // __STATISTICS__
1127
1128	// OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
1129
1130	// Does not matter where this storage is freed.
1131	if ( unlikely( munmap( header, size ) == -1 ) ) {
1132	// Do not call strerror( errno ) as it may call malloc.
1133	abort( "** Error ** attempt to deallocate large object %p and munmap failed with errno %d.\n"
1134	"Possible cause is invalid delete pointer: either not allocated or with corrupt header.",
1135	addr, errno );
1136	} // if
1137	} else {
1138	assert( freeHead );
1139	#ifdef __CFA_DEBUG__
1140	// memset is NOT always inlined!
1141	disable_interrupts();
1142	// Scrub old memory so subsequent usages might fail. Only scrub the first/last SCRUB_SIZE bytes.
1143	char * data = ((Heap.Storage *)header)->data; // data address
1144	size_t dsize = size - sizeof(Heap.Storage); // data size
1145	if ( dsize <= SCRUB_SIZE * 2 ) {
1146	memset( data, SCRUB, dsize ); // scrub all
1147	} else {
1148	memset( data, SCRUB, SCRUB_SIZE ); // scrub front
1149	memset( data + dsize - SCRUB_SIZE, SCRUB, SCRUB_SIZE ); // scrub back
1150	} // if
1151	enable_interrupts( false );
1152	#endif // __CFA_DEBUG__
1153
1154	#ifdef OWNERSHIP
1155	if ( likely( heapManager == freeHead->homeManager ) ) { // belongs to this thread
1156	header->kind.real.next = freeHead->freeList; // push on stack
1157	freeHead->freeList = (Heap.Storage *)header;
1158	} else { // return to thread owner
1159	verify( heapManager );
1160
1161	#ifdef RETURNSPIN
1162	lock( freeHead->returnLock );
1163	header->kind.real.next = freeHead->returnList; // push to bucket return list
1164	freeHead->returnList = (Heap.Storage *)header;
1165	unlock( freeHead->returnLock );
1166	#else // lock free
1167	header->kind.real.next = freeHead->returnList; // link new node to top node
1168	// CAS resets header->kind.real.next = freeHead->returnList on failure
1169	while ( ! __atomic_compare_exchange_n( &freeHead->returnList, &header->kind.real.next, (Heap.Storage *)header,
1170	false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) );
1171
1172	#ifdef __STATISTICS__
1173	stats.return_pushes += 1;
1174	stats.return_storage_request += rsize;
1175	stats.return_storage_alloc += size;
1176	#endif // __STATISTICS__
1177	#endif // RETURNSPIN
1178	} // if
1179
1180	#else // no OWNERSHIP
1181
1182	// kind.real.home is address in owner thread's freeLists, so compute the equivalent position in this thread's freeList.
1183	freeHead = &freeLists[ClearStickyBits( (Heap.FreeHeader *)(header->kind.real.home) ) - &freeHead->homeManager->freeLists[0]];
1184	header->kind.real.next = freeHead->freeList; // push on stack
1185	freeHead->freeList = (Heap.Storage *)header;
1186	#endif // ! OWNERSHIP
1187
1188	// OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
1189	} // if
1190
1191	#ifdef __CFA_DEBUG__
1192	if ( traceHeap() ) {
1193	char helpText[64];
1194	__cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText),
1195	"Free( %p ) size:%zu\n", addr, size ); // print debug/nodebug
1196	} // if
1197	#endif // __CFA_DEBUG__
1198
1199	// poll_interrupts(); // call rollforward
1200	} // doFree
1201
1202
1203	size_t prtFree( Heap & manager ) with( manager ) {
1204	size_t total = 0;
1205	#ifdef __STATISTICS__
1206	__cfaabi_bits_acquire();
1207	__cfaabi_bits_print_nolock( STDERR_FILENO, "\nBin lists (bin size : free blocks on list)\n" );
1208	#endif // __STATISTICS__
1209	for ( unsigned int i = 0; i < heapMaster.maxBucketsUsed; i += 1 ) {
1210	size_t size = freeLists[i].blockSize;
1211	#ifdef __STATISTICS__
1212	unsigned int N = 0;
1213	#endif // __STATISTICS__
1214
1215	for ( Heap.Storage * p = freeLists[i].freeList; p != 0p; p = p->header.kind.real.next ) {
1216	total += size;
1217	#ifdef __STATISTICS__
1218	N += 1;
1219	#endif // __STATISTICS__
1220	} // for
1221
1222	#ifdef __STATISTICS__
1223	__cfaabi_bits_print_nolock( STDERR_FILENO, "%7zu, %-7u ", size, N );
1224	if ( (i + 1) % 8 == 0 ) __cfaabi_bits_print_nolock( STDERR_FILENO, "\n" );
1225	#endif // __STATISTICS__
1226	} // for
1227	#ifdef __STATISTICS__
1228	__cfaabi_bits_print_nolock( STDERR_FILENO, "\ntotal free blocks:%zu\n", total );
1229	__cfaabi_bits_release();
1230	#endif // __STATISTICS__
1231	return (char )heapMaster.heapEnd - (char )heapMaster.heapBegin - total;
1232	} // prtFree
1233
1234
1235	#ifdef __STATISTICS__
1236	static void incCalls( size_t statName ) libcfa_nopreempt {
1237	heapManager->stats.counters[statName].calls += 1;
1238	} // incCalls
1239
1240	static void incZeroCalls( size_t statName ) libcfa_nopreempt {
1241	heapManager->stats.counters[statName].calls_0 += 1;
1242	} // incZeroCalls
1243	#endif // __STATISTICS__
1244
1245	#ifdef __CFA_DEBUG__
1246	static void incUnfreed( intptr_t offset ) libcfa_nopreempt {
1247	heapManager->allocUnfreed += offset;
1248	} // incUnfreed
1249	#endif // __CFA_DEBUG__
1250
1251
1252	static void * memalignNoStats( size_t alignment, size_t size STAT_PARM ) {
1253	checkAlign( alignment ); // check alignment
1254
1255	// if alignment <= default alignment or size == 0, do normal malloc as two headers are unnecessary
1256	if ( unlikely( alignment <= libAlign() \|\| size == 0 ) ) return doMalloc( size STAT_ARG( STAT_NAME ) );
1257
1258	// Allocate enough storage to guarantee an address on the alignment boundary, and sufficient space before it for
1259	// administrative storage. NOTE, WHILE THERE ARE 2 HEADERS, THE FIRST ONE IS IMPLICITLY CREATED BY DOMALLOC.
1260	// .-------------v-----------------v----------------v----------,
1261	// \| Real Header \| ... padding ... \| Fake Header \| data ... \|
1262	// `-------------^-----------------^-+--------------^----------'
1263	// \|<--------------------------------' offset/align \|<-- alignment boundary
1264
1265	// subtract libAlign() because it is already the minimum alignment
1266	// add sizeof(Storage) for fake header
1267	size_t offset = alignment - libAlign() + sizeof(Heap.Storage);
1268	char * addr = (char *)doMalloc( size + offset STAT_ARG( STAT_NAME ) );
1269
1270	// address in the block of the "next" alignment address
1271	char * user = (char *)ceiling2( (uintptr_t)(addr + sizeof(Heap.Storage)), alignment );
1272
1273	// address of header from malloc
1274	Heap.Storage.Header * realHeader = HeaderAddr( addr );
1275	realHeader->kind.real.size = size; // correct size to eliminate above alignment offset
1276	#ifdef __CFA_DEBUG__
1277	incUnfreed( -offset ); // adjustment off the offset from call to doMalloc
1278	#endif // __CFA_DEBUG__
1279
1280	// address of fake header before the alignment location
1281	Heap.Storage.Header * fakeHeader = HeaderAddr( user );
1282
1283	// SKULLDUGGERY: insert the offset to the start of the actual storage block and remember alignment
1284	fakeHeader->kind.fake.offset = (char )fakeHeader - (char )realHeader;
1285	// SKULLDUGGERY: odd alignment implies fake header
1286	fakeHeader->kind.fake.alignment = MarkAlignmentBit( alignment );
1287
1288	return user;
1289	} // memalignNoStats
1290
1291
1292	//####################### Memory Allocation Routines ####################
1293
1294
1295	extern "C" {
1296	// Allocates size bytes and returns a pointer to the allocated memory. The contents are undefined. If size is 0,
1297	// then malloc() returns a unique pointer value that can later be successfully passed to free().
1298	void * malloc( size_t size ) libcfa_public {
1299	return doMalloc( size STAT_ARG( MALLOC ) );
1300	} // malloc
1301
1302
1303	// Same as malloc() except size bytes is an array of dim elements each of elemSize bytes.
1304	void * aalloc( size_t dim, size_t elemSize ) libcfa_public {
1305	return doMalloc( dim * elemSize STAT_ARG( AALLOC ) );
1306	} // aalloc
1307
1308
1309	// Same as aalloc() with memory set to zero.
1310	void * calloc( size_t dim, size_t elemSize ) libcfa_public {
1311	size_t size = dim * elemSize;
1312	char * addr = (char *)doMalloc( size STAT_ARG( CALLOC ) );
1313
1314	if ( unlikely( addr == NULL ) ) return NULL; // stop further processing if 0p is returned
1315
1316	Heap.Storage.Header * header;
1317	Heap.FreeHeader * freeHead;
1318	size_t bsize, alignment;
1319
1320	#ifndef __CFA_DEBUG__
1321	bool mapped =
1322	#endif // __CFA_DEBUG__
1323	headers( "calloc", addr, header, freeHead, bsize, alignment );
1324
1325	#ifndef __CFA_DEBUG__
1326	// Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
1327	if ( likely( ! mapped ) )
1328	#endif // __CFA_DEBUG__
1329	// <-------0000000000000000000000000000UUUUUUUUUUUUUUUUUUUUUUUUU> bsize (bucket size) U => undefined
1330	// `-header`-addr `-size
1331	memset( addr, '\0', size ); // set to zeros
1332
1333	MarkZeroFilledBit( header ); // mark as zero fill
1334	return addr;
1335	} // calloc
1336
1337
1338	// Change the size of the memory block pointed to by oaddr to size bytes. The contents are undefined. If oaddr is
1339	// 0p, then the call is equivalent to malloc(size), for all values of size; if size is equal to zero, and oaddr is
1340	// not 0p, then the call is equivalent to free(oaddr). Unless oaddr is 0p, it must have been returned by an earlier
1341	// call to malloc(), alloc(), calloc() or realloc(). If the area pointed to was moved, a free(oaddr) is done.
1342	void * resize( void * oaddr, size_t size ) libcfa_public {
1343	if ( unlikely( oaddr == 0p ) ) { // => malloc( size )
1344	return doMalloc( size STAT_ARG( RESIZE ) );
1345	} // if
1346
1347	PROLOG( RESIZE, doFree( oaddr ) ); // => free( oaddr )
1348
1349	Heap.Storage.Header * header;
1350	Heap.FreeHeader * freeHead;
1351	size_t bsize, oalign;
1352	headers( "resize", oaddr, header, freeHead, bsize, oalign );
1353
1354	size_t odsize = DataStorage( bsize, oaddr, header ); // data storage available in bucket
1355	// same size, DO NOT PRESERVE STICKY PROPERTIES.
1356	if ( oalign == libAlign() && size <= odsize && odsize <= size * 2 ) { // allow 50% wasted storage for smaller size
1357	ClearZeroFillBit( header ); // no alignment and turn off 0 fill
1358	#ifdef __CFA_DEBUG__
1359	incUnfreed( size - header->kind.real.size ); // adjustment off the size difference
1360	#endif // __CFA_DEBUG__
1361	header->kind.real.size = size; // reset allocation size
1362	#ifdef __STATISTICS__
1363	incCalls( RESIZE );
1364	#endif // __STATISTICS__
1365	return oaddr;
1366	} // if
1367
1368	// change size, DO NOT PRESERVE STICKY PROPERTIES.
1369	doFree( oaddr ); // free previous storage
1370
1371	return doMalloc( size STAT_ARG( RESIZE ) ); // create new area
1372	} // resize
1373
1374
1375	// Same as resize() but the contents are unchanged in the range from the start of the region up to the minimum of
1376	// the old and new sizes.
1377	void * realloc( void * oaddr, size_t size ) libcfa_public {
1378	// char buf[64];
1379	// int len = sprintf( buf, "realloc1 oaddr %p size %d\n", oaddr, size );
1380	// write( 2, buf, len );
1381	if ( unlikely( oaddr == 0p ) ) { // => malloc( size )
1382	return doMalloc( size STAT_ARG( REALLOC ) );
1383	} // if
1384
1385	PROLOG( REALLOC, doFree( oaddr ) ); // => free( oaddr )
1386
1387	Heap.Storage.Header * header;
1388	Heap.FreeHeader * freeHead;
1389	size_t bsize, oalign;
1390	headers( "realloc", oaddr, header, freeHead, bsize, oalign );
1391
1392	size_t odsize = DataStorage( bsize, oaddr, header ); // data storage available in bucket
1393	size_t osize = header->kind.real.size; // old allocation size
1394	bool ozfill = ZeroFillBit( header ); // old allocation zero filled
1395	if ( unlikely( size <= odsize ) && odsize <= size * 2 ) { // allow up to 50% wasted storage
1396	#ifdef __CFA_DEBUG__
1397	incUnfreed( size - header->kind.real.size ); // adjustment off the size difference
1398	#endif // __CFA_DEBUG__
1399	header->kind.real.size = size; // reset allocation size
1400	if ( unlikely( ozfill ) && size > osize ) { // previous request zero fill and larger ?
1401	memset( (char *)oaddr + osize, '\0', size - osize ); // initialize added storage
1402	} // if
1403	#ifdef __STATISTICS__
1404	incCalls( REALLOC );
1405	#endif // __STATISTICS__
1406	return oaddr;
1407	} // if
1408
1409	// change size and copy old content to new storage
1410
1411	void * naddr;
1412	if ( likely( oalign <= libAlign() ) ) { // previous request not aligned ?
1413	naddr = doMalloc( size STAT_ARG( REALLOC ) ); // create new area
1414	} else {
1415	naddr = memalignNoStats( oalign, size STAT_ARG( REALLOC ) ); // create new aligned area
1416	} // if
1417
1418	headers( "realloc", naddr, header, freeHead, bsize, oalign );
1419	// To preserve prior fill, the entire bucket must be copied versus the size.
1420	memcpy( naddr, oaddr, min( osize, size ) ); // copy bytes
1421	doFree( oaddr ); // free previous storage
1422
1423	if ( unlikely( ozfill ) ) { // previous request zero fill ?
1424	MarkZeroFilledBit( header ); // mark new request as zero filled
1425	if ( size > osize ) { // previous request larger ?
1426	memset( (char *)naddr + osize, '\0', size - osize ); // initialize added storage
1427	} // if
1428	} // if
1429	return naddr;
1430	} // realloc
1431
1432
1433	// Same as realloc() except the new allocation size is large enough for an array of nelem elements of size elsize.
1434	void * reallocarray( void * oaddr, size_t dim, size_t elemSize ) libcfa_public {
1435	return realloc( oaddr, dim * elemSize );
1436	} // reallocarray
1437
1438
1439	// Same as malloc() except the memory address is a multiple of alignment, which must be a power of two. (obsolete)
1440	void * memalign( size_t alignment, size_t size ) libcfa_public {
1441	return memalignNoStats( alignment, size STAT_ARG( MEMALIGN ) );
1442	} // memalign
1443
1444
1445	// Same as aalloc() with memory alignment.
1446	void * amemalign( size_t alignment, size_t dim, size_t elemSize ) libcfa_public {
1447	return memalignNoStats( alignment, dim * elemSize STAT_ARG( AMEMALIGN ) );
1448	} // amemalign
1449
1450
1451	// Same as calloc() with memory alignment.
1452	void * cmemalign( size_t alignment, size_t dim, size_t elemSize ) libcfa_public {
1453	size_t size = dim * elemSize;
1454	char * addr = (char *)memalignNoStats( alignment, size STAT_ARG( CMEMALIGN ) );
1455
1456	if ( unlikely( addr == NULL ) ) return NULL; // stop further processing if 0p is returned
1457
1458	Heap.Storage.Header * header;
1459	Heap.FreeHeader * freeHead;
1460	size_t bsize;
1461
1462	#ifndef __CFA_DEBUG__
1463	bool mapped =
1464	#endif // __CFA_DEBUG__
1465	headers( "cmemalign", addr, header, freeHead, bsize, alignment );
1466
1467	// Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
1468	#ifndef __CFA_DEBUG__
1469	if ( ! mapped )
1470	#endif // __CFA_DEBUG__
1471	// <-------0000000000000000000000000000UUUUUUUUUUUUUUUUUUUUUUUUU> bsize (bucket size) U => undefined
1472	// `-header`-addr `-size
1473	memset( addr, '\0', size ); // set to zeros
1474
1475	MarkZeroFilledBit( header ); // mark as zero filled
1476	return addr;
1477	} // cmemalign
1478
1479
1480	// Same as memalign(), but ISO/IEC 2011 C11 Section 7.22.2 states: the value of size shall be an integral multiple
1481	// of alignment. This requirement is universally ignored.
1482	void * aligned_alloc( size_t alignment, size_t size ) libcfa_public {
1483	return memalign( alignment, size );
1484	} // aligned_alloc
1485
1486
1487	// Allocates size bytes and places the address of the allocated memory in *memptr. The address of the allocated
1488	// memory shall be a multiple of alignment, which must be a power of two and a multiple of sizeof(void *). If size
1489	// is 0, then posix_memalign() returns either 0p, or a unique pointer value that can later be successfully passed to
1490	// free(3).
1491	int posix_memalign( void ** memptr, size_t alignment, size_t size ) libcfa_public {
1492	if ( unlikely( alignment < libAlign() \|\| ! is_pow2( alignment ) ) ) return EINVAL; // check alignment
1493	*memptr = memalign( alignment, size );
1494	return 0;
1495	} // posix_memalign
1496
1497
1498	// Allocates size bytes and returns a pointer to the allocated memory. The memory address shall be a multiple of the
1499	// page size. It is equivalent to memalign(sysconf(_SC_PAGESIZE),size).
1500	void * valloc( size_t size ) libcfa_public {
1501	return memalign( __page_size, size );
1502	} // valloc
1503
1504
1505	// Same as valloc but rounds size to multiple of page size.
1506	void * pvalloc( size_t size ) libcfa_public {
1507	return memalign( __page_size, ceiling2( size, __page_size ) ); // round size to multiple of page size
1508	} // pvalloc
1509
1510
1511	// Frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc()
1512	// or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behaviour occurs. If ptr is
1513	// 0p, no operation is performed.
1514	void free( void * addr ) libcfa_public {
1515	if ( unlikely( addr == 0p ) ) { // special case
1516	#ifdef __STATISTICS__
1517	if ( heapManager )
1518	incZeroCalls( FREE );
1519	#endif // __STATISTICS__
1520	return;
1521	} // if
1522
1523	doFree( addr ); // handles heapManager == nullptr
1524	} // free
1525
1526
1527	// Returns the alignment of an allocation.
1528	size_t malloc_alignment( void * addr ) libcfa_public {
1529	if ( unlikely( addr == 0p ) ) return libAlign(); // minimum alignment
1530	Heap.Storage.Header * header = HeaderAddr( addr );
1531	if ( unlikely( AlignmentBit( header ) ) ) { // fake header ?
1532	return ClearAlignmentBit( header ); // clear flag from value
1533	} else {
1534	return libAlign(); // minimum alignment
1535	} // if
1536	} // malloc_alignment
1537
1538
1539	// Returns true if the allocation is zero filled, e.g., allocated by calloc().
1540	bool malloc_zero_fill( void * addr ) libcfa_public {
1541	if ( unlikely( addr == 0p ) ) return false; // null allocation is not zero fill
1542	Heap.Storage.Header * header = HeaderAddr( addr );
1543	if ( unlikely( AlignmentBit( header ) ) ) { // fake header ?
1544	header = RealHeader( header ); // backup from fake to real header
1545	} // if
1546	return ZeroFillBit( header ); // zero filled ?
1547	} // malloc_zero_fill
1548
1549
1550	// Returns original total allocation size (not bucket size) => array size is dimension * sizeof(T).
1551	size_t malloc_size( void * addr ) libcfa_public {
1552	if ( unlikely( addr == 0p ) ) return 0; // null allocation has zero size
1553	Heap.Storage.Header * header = HeaderAddr( addr );
1554	if ( unlikely( AlignmentBit( header ) ) ) { // fake header ?
1555	header = RealHeader( header ); // backup from fake to real header
1556	} // if
1557	return header->kind.real.size;
1558	} // malloc_size
1559
1560
1561	// Returns the number of usable bytes in the block pointed to by ptr, a pointer to a block of memory allocated by
1562	// malloc or a related function.
1563	size_t malloc_usable_size( void * addr ) libcfa_public {
1564	if ( unlikely( addr == 0p ) ) return 0; // null allocation has 0 size
1565	Heap.Storage.Header * header;
1566	Heap.FreeHeader * freeHead;
1567	size_t bsize, alignment;
1568
1569	headers( "malloc_usable_size", addr, header, freeHead, bsize, alignment );
1570	return DataStorage( bsize, addr, header ); // data storage in bucket
1571	} // malloc_usable_size
1572
1573
1574	// Prints (on default standard error) statistics about memory allocated by malloc and related functions.
1575	void malloc_stats( void ) libcfa_public {
1576	#ifdef __STATISTICS__
1577	HeapStatistics stats;
1578	HeapStatisticsCtor( stats );
1579	if ( printStats( collectStats( stats ) ) == -1 ) {
1580	#else
1581	#define MALLOC_STATS_MSG "malloc_stats statistics disabled.\n"
1582	if ( write( STDERR_FILENO, MALLOC_STATS_MSG, sizeof( MALLOC_STATS_MSG ) - 1 /* size includes '\0' */ ) == -1 ) {
1583	#endif // __STATISTICS__
1584	abort( "** Error ** write failed in malloc_stats" );
1585	} // if
1586	} // malloc_stats
1587
1588
1589	// Zero the heap master and all active thread heaps.
1590	void malloc_stats_clear() {
1591	#ifdef __STATISTICS__
1592	clearStats();
1593	#else
1594	#define MALLOC_STATS_MSG "malloc_stats statistics disabled.\n"
1595	if ( write( STDERR_FILENO, MALLOC_STATS_MSG, sizeof( MALLOC_STATS_MSG ) - 1 /* size includes '\0' */ ) == -1 ) {
1596	abort( "** Error ** write failed in malloc_stats" );
1597	} // if
1598	#endif // __STATISTICS__
1599	} // malloc_stats_clear
1600
1601	// Changes the file descriptor where malloc_stats() writes statistics.
1602	int malloc_stats_fd( int fd __attribute__(( unused )) ) libcfa_public {
1603	#ifdef __STATISTICS__
1604	int temp = heapMaster.stats_fd;
1605	heapMaster.stats_fd = fd;
1606	return temp;
1607	#else
1608	return -1; // unsupported
1609	#endif // __STATISTICS__
1610	} // malloc_stats_fd
1611
1612
1613	// Prints an XML string that describes the current state of the memory-allocation implementation in the caller.
1614	// The string is printed on the file stream stream. The exported string includes information about all arenas (see
1615	// malloc).
1616	int malloc_info( int options, FILE * stream __attribute__(( unused )) ) libcfa_public {
1617	if ( options != 0 ) { errno = EINVAL; return -1; }
1618	#ifdef __STATISTICS__
1619	HeapStatistics stats;
1620	HeapStatisticsCtor( stats );
1621	return printStatsXML( collectStats( stats ), stream ); // returns bytes written or -1
1622	#else
1623	return 0; // unsupported
1624	#endif // __STATISTICS__
1625	} // malloc_info
1626
1627
1628	// Adjusts parameters that control the behaviour of the memory-allocation functions (see malloc). The param argument
1629	// specifies the parameter to be modified, and value specifies the new value for that parameter.
1630	int mallopt( int option, int value ) libcfa_public {
1631	if ( value < 0 ) return 0;
1632	choose( option ) {
1633	case M_TOP_PAD:
1634	heapMaster.heapExpand = ceiling2( value, __page_size );
1635	return 1;
1636	case M_MMAP_THRESHOLD:
1637	if ( setMmapStart( value ) ) return 1;
1638	} // choose
1639	return 0; // error, unsupported
1640	} // mallopt
1641
1642
1643	// Attempt to release free memory at the top of the heap (by calling sbrk with a suitable argument).
1644	int malloc_trim( size_t ) libcfa_public {
1645	return 0; // => impossible to release memory
1646	} // malloc_trim
1647
1648
1649	// Records the current state of all malloc internal bookkeeping variables (but not the actual contents of the heap
1650	// or the state of malloc_hook functions pointers). The state is recorded in a system-dependent opaque data
1651	// structure dynamically allocated via malloc, and a pointer to that data structure is returned as the function
1652	// result. (The caller must free this memory.)
1653	void * malloc_get_state( void ) libcfa_public {
1654	return 0p; // unsupported
1655	} // malloc_get_state
1656
1657
1658	// Restores the state of all malloc internal bookkeeping variables to the values recorded in the opaque data
1659	// structure pointed to by state.
1660	int malloc_set_state( void * ) libcfa_public {
1661	return 0; // unsupported
1662	} // malloc_set_state
1663
1664
1665	// Sets the amount (bytes) to extend the heap when there is insufficent free storage to service an allocation.
1666	__attribute__((weak)) size_t malloc_expansion() libcfa_public { return __CFA_DEFAULT_HEAP_EXPANSION__; }
1667
1668	// Sets the crossover point between allocations occuring in the sbrk area or separately mmapped.
1669	__attribute__((weak)) size_t malloc_mmap_start() libcfa_public { return __CFA_DEFAULT_MMAP_START__; }
1670
1671	// Amount subtracted to adjust for unfreed program storage (debug only).
1672	__attribute__((weak)) size_t malloc_unfreed() libcfa_public { return __CFA_DEFAULT_HEAP_UNFREED__; }
1673	} // extern "C"
1674
1675
1676	// Must have CFA linkage to overload with C linkage realloc.
1677	void * resize( void * oaddr, size_t nalign, size_t size ) libcfa_public {
1678	if ( unlikely( oaddr == 0p ) ) { // => malloc( size )
1679	return memalignNoStats( nalign, size STAT_ARG( RESIZE ) );
1680	} // if
1681
1682	PROLOG( RESIZE, doFree( oaddr ) ); // => free( oaddr )
1683
1684	// Attempt to reuse existing alignment.
1685	Heap.Storage.Header * header = HeaderAddr( oaddr );
1686	bool isFakeHeader = AlignmentBit( header ); // old fake header ?
1687	size_t oalign;
1688
1689	if ( unlikely( isFakeHeader ) ) {
1690	checkAlign( nalign ); // check alignment
1691	oalign = ClearAlignmentBit( header ); // old alignment
1692	if ( unlikely( (uintptr_t)oaddr % nalign == 0 // lucky match ?
1693	&& ( oalign <= nalign // going down
1694	\|\| (oalign >= nalign && oalign <= 256) ) // little alignment storage wasted ?
1695	) ) {
1696	HeaderAddr( oaddr )->kind.fake.alignment = MarkAlignmentBit( nalign ); // update alignment (could be the same)
1697	Heap.FreeHeader * freeHead;
1698	size_t bsize, oalign;
1699	headers( "resize", oaddr, header, freeHead, bsize, oalign );
1700	size_t odsize = DataStorage( bsize, oaddr, header ); // data storage available in bucket
1701
1702	if ( size <= odsize && odsize <= size * 2 ) { // allow 50% wasted data storage
1703	HeaderAddr( oaddr )->kind.fake.alignment = MarkAlignmentBit( nalign ); // update alignment (could be the same)
1704	ClearZeroFillBit( header ); // turn off 0 fill
1705	#ifdef __CFA_DEBUG__
1706	incUnfreed( size - header->kind.real.size ); // adjustment off the size difference
1707	#endif // __CFA_DEBUG__
1708	header->kind.real.size = size; // reset allocation size
1709	#ifdef __STATISTICS__
1710	incCalls( RESIZE );
1711	#endif // __STATISTICS__
1712	return oaddr;
1713	} // if
1714	} // if
1715	} else if ( ! isFakeHeader // old real header (aligned on libAlign) ?
1716	&& nalign == libAlign() ) { // new alignment also on libAlign => no fake header needed
1717	return resize( oaddr, size ); // duplicate special case checks
1718	} // if
1719
1720	// change size, DO NOT PRESERVE STICKY PROPERTIES.
1721	doFree( oaddr ); // free previous storage
1722	return memalignNoStats( nalign, size STAT_ARG( RESIZE ) ); // create new aligned area
1723	} // resize
1724
1725
1726	void * realloc( void * oaddr, size_t nalign, size_t size ) libcfa_public {
1727	// char buf[64];
1728	// int len = sprintf( buf, "realloc2 oaddr %p size %d\n", oaddr, size );
1729	// write( 2, buf, len );
1730	if ( unlikely( oaddr == 0p ) ) { // => malloc( size )
1731	return memalignNoStats( nalign, size STAT_ARG( REALLOC ) );
1732	} // if
1733
1734	PROLOG( REALLOC, doFree( oaddr ) ); // => free( oaddr )
1735
1736	// Attempt to reuse existing alignment.
1737	Heap.Storage.Header * header = HeaderAddr( oaddr );
1738	bool isFakeHeader = AlignmentBit( header ); // old fake header ?
1739	size_t oalign;
1740	if ( unlikely( isFakeHeader ) ) {
1741	checkAlign( nalign ); // check alignment
1742	oalign = ClearAlignmentBit( header ); // old alignment
1743	if ( unlikely( (uintptr_t)oaddr % nalign == 0 // lucky match ?
1744	&& ( oalign <= nalign // going down
1745	\|\| (oalign >= nalign && oalign <= 256) ) // little alignment storage wasted ?
1746	) ) {
1747	HeaderAddr( oaddr )->kind.fake.alignment = MarkAlignmentBit( nalign ); // update alignment (could be the same)
1748	return realloc( oaddr, size ); // duplicate special case checks
1749	} // if
1750	} else if ( ! isFakeHeader // old real header (aligned on libAlign) ?
1751	&& nalign == libAlign() ) { // new alignment also on libAlign => no fake header needed
1752	return realloc( oaddr, size ); // duplicate special case checks
1753	} // if
1754
1755	Heap.FreeHeader * freeHead;
1756	size_t bsize;
1757	headers( "realloc", oaddr, header, freeHead, bsize, oalign );
1758
1759	// change size and copy old content to new storage
1760
1761	size_t osize = header->kind.real.size; // old allocation size
1762	bool ozfill = ZeroFillBit( header ); // old allocation zero filled
1763
1764	void * naddr = memalignNoStats( nalign, size STAT_ARG( REALLOC ) ); // create new aligned area
1765
1766	headers( "realloc", naddr, header, freeHead, bsize, oalign );
1767	memcpy( naddr, oaddr, min( osize, size ) ); // copy bytes
1768	doFree( oaddr ); // free previous storage
1769
1770	if ( unlikely( ozfill ) ) { // previous request zero fill ?
1771	MarkZeroFilledBit( header ); // mark new request as zero filled
1772	if ( size > osize ) { // previous request larger ?
1773	memset( (char *)naddr + osize, '\0', size - osize ); // initialize added storage
1774	} // if
1775	} // if
1776	return naddr;
1777	} // realloc
1778
1779
1780	void * reallocarray( void * oaddr, size_t nalign, size_t dim, size_t elemSize ) __THROW {
1781	return realloc( oaddr, nalign, dim * elemSize );
1782	} // reallocarray
1783
1784
1785	// Local Variables: //
1786	// tab-width: 4 //
1787	// compile-command: "cfa -nodebug -O2 heap.cfa" //
1788	// End: //

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format