Context Navigation

heap.cfa @ 524627e

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 524627e was 1e034d9, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago
forammting, add missing call to header in alignment realloc
Property mode set to `100644`
File size: 43.7 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.c --
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 : Sun Nov 24 17:56:15 2019
13	// Update Count : 638
14	//
15
16	#include <unistd.h> // sbrk, sysconf
17	#include <stdbool.h> // true, false
18	#include <stdio.h> // snprintf, fileno
19	#include <errno.h> // errno
20	#include <string.h> // memset, memcpy
21	extern "C" {
22	#include <sys/mman.h> // mmap, munmap
23	} // extern "C"
24
25	// #comment TD : Many of these should be merged into math I believe
26	#include "bits/align.hfa" // libPow2
27	#include "bits/defs.hfa" // likely, unlikely
28	#include "bits/locks.hfa" // __spinlock_t
29	#include "startup.hfa" // STARTUP_PRIORITY_MEMORY
30	//#include "stdlib.hfa" // bsearchl
31	#include "malloc.h"
32
33	#define MIN(x, y) (y > x ? x : y)
34
35	static bool traceHeap = false;
36
37	inline bool traceHeap() {
38	return traceHeap;
39	} // traceHeap
40
41	bool traceHeapOn() {
42	bool temp = traceHeap;
43	traceHeap = true;
44	return temp;
45	} // traceHeapOn
46
47	bool traceHeapOff() {
48	bool temp = traceHeap;
49	traceHeap = false;
50	return temp;
51	} // traceHeapOff
52
53
54	static bool prtFree = false;
55
56	inline bool prtFree() {
57	return prtFree;
58	} // prtFree
59
60	bool prtFreeOn() {
61	bool temp = prtFree;
62	prtFree = true;
63	return temp;
64	} // prtFreeOn
65
66	bool prtFreeOff() {
67	bool temp = prtFree;
68	prtFree = false;
69	return temp;
70	} // prtFreeOff
71
72
73	// static bool traceHeapTerm = false;
74
75	// inline bool traceHeapTerm() {
76	// return traceHeapTerm;
77	// } // traceHeapTerm
78
79	// bool traceHeapTermOn() {
80	// bool temp = traceHeapTerm;
81	// traceHeapTerm = true;
82	// return temp;
83	// } // traceHeapTermOn
84
85	// bool traceHeapTermOff() {
86	// bool temp = traceHeapTerm;
87	// traceHeapTerm = false;
88	// return temp;
89	// } // traceHeapTermOff
90
91
92	enum {
93	// Define the default extension heap amount in units of bytes. When the uC++ supplied heap reaches the brk address,
94	// the brk address is extended by the extension amount.
95	__CFA_DEFAULT_HEAP_EXPANSION__ = (1 * 1024 * 1024),
96
97	// Define the mmap crossover point during allocation. Allocations less than this amount are allocated from buckets;
98	// values greater than or equal to this value are mmap from the operating system.
99	__CFA_DEFAULT_MMAP_START__ = (512 * 1024 + 1),
100	};
101
102	size_t default_mmap_start() __attribute__(( weak )) {
103	return __CFA_DEFAULT_MMAP_START__;
104	} // default_mmap_start
105
106	size_t default_heap_expansion() __attribute__(( weak )) {
107	return __CFA_DEFAULT_HEAP_EXPANSION__;
108	} // default_heap_expansion
109
110
111	#ifdef __CFA_DEBUG__
112	static unsigned int allocFree; // running total of allocations minus frees
113
114	static void prtUnfreed() {
115	if ( allocFree != 0 ) {
116	// DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
117	// char helpText[512];
118	// int len = snprintf( helpText, sizeof(helpText), "CFA warning (UNIX pid:%ld) : program terminating with %u(0x%x) bytes of storage allocated but not freed.\n"
119	// "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n",
120	// (long int)getpid(), allocFree, allocFree ); // always print the UNIX pid
121	// __cfaabi_dbg_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug
122	} // if
123	} // prtUnfreed
124
125	extern "C" {
126	void heapAppStart() { // called by __cfaabi_appready_startup
127	allocFree = 0;
128	} // heapAppStart
129
130	void heapAppStop() { // called by __cfaabi_appready_startdown
131	fclose( stdin ); fclose( stdout );
132	prtUnfreed();
133	} // heapAppStop
134	} // extern "C"
135	#endif // __CFA_DEBUG__
136
137
138	// statically allocated variables => zero filled.
139	static size_t pageSize; // architecture pagesize
140	static size_t heapExpand; // sbrk advance
141	static size_t mmapStart; // cross over point for mmap
142	static unsigned int maxBucketsUsed; // maximum number of buckets in use
143
144
145	#define SPINLOCK 0
146	#define LOCKFREE 1
147	#define BUCKETLOCK SPINLOCK
148	#if BUCKETLOCK == LOCKFREE
149	#include <uStackLF.h>
150	#endif // LOCKFREE
151
152	// Recursive definitions: HeapManager needs size of bucket array and bucket area needs sizeof HeapManager storage.
153	// Break recusion by hardcoding number of buckets and statically checking number is correct after bucket array defined.
154	enum { NoBucketSizes = 91 }; // number of buckets sizes
155
156	struct HeapManager {
157	// struct FreeHeader; // forward declaration
158
159	struct Storage {
160	struct Header { // header
161	union Kind {
162	struct RealHeader {
163	union {
164	struct { // 4-byte word => 8-byte header, 8-byte word => 16-byte header
165	#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __SIZEOF_POINTER__ == 4
166	uint32_t padding; // unused, force home/blocksize to overlay alignment in fake header
167	#endif // __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __SIZEOF_POINTER__ == 4
168
169	union {
170	// FreeHeader * home; // allocated block points back to home locations (must overlay alignment)
171	void * home; // allocated block points back to home locations (must overlay alignment)
172	size_t blockSize; // size for munmap (must overlay alignment)
173	#if BUCKLOCK == SPINLOCK
174	Storage * next; // freed block points next freed block of same size
175	#endif // SPINLOCK
176	};
177
178	#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && __SIZEOF_POINTER__ == 4
179	uint32_t padding; // unused, force home/blocksize to overlay alignment in fake header
180	#endif // __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && __SIZEOF_POINTER__ == 4
181	};
182	// future code
183	#if BUCKLOCK == LOCKFREE
184	Stack<Storage>::Link next; // freed block points next freed block of same size (double-wide)
185	#endif // LOCKFREE
186	};
187	} real; // RealHeader
188	struct FakeHeader {
189	#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
190	uint32_t alignment; // low-order bits of home/blockSize used for tricks
191	#endif // __ORDER_LITTLE_ENDIAN__
192
193	uint32_t offset;
194
195	#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
196	uint32_t alignment; // low-order bits of home/blockSize used for tricks
197	#endif // __ORDER_BIG_ENDIAN__
198	} fake; // FakeHeader
199	} kind; // Kind
200	} header; // Header
201	char pad[libAlign() - sizeof( Header )];
202	char data[0]; // storage
203	}; // Storage
204
205	static_assert( libAlign() >= sizeof( Storage ), "libAlign() < sizeof( Storage )" );
206
207	struct FreeHeader {
208	#if BUCKLOCK == SPINLOCK
209	__spinlock_t lock; // must be first field for alignment
210	Storage * freeList;
211	#elif BUCKLOCK == LOCKFREE
212	// future code
213	StackLF<Storage> freeList;
214	#else
215	#error undefined lock type for bucket lock
216	#endif // SPINLOCK
217	size_t blockSize; // size of allocations on this list
218	}; // FreeHeader
219
220	// must be first fields for alignment
221	__spinlock_t extlock; // protects allocation-buffer extension
222	FreeHeader freeLists[NoBucketSizes]; // buckets for different allocation sizes
223
224	void * heapBegin; // start of heap
225	void * heapEnd; // logical end of heap
226	size_t heapRemaining; // amount of storage not allocated in the current chunk
227	}; // HeapManager
228
229	static inline size_t getKey( const HeapManager.FreeHeader & freeheader ) { return freeheader.blockSize; }
230
231
232	#define FASTLOOKUP
233	#define __STATISTICS__
234
235	// Bucket size must be multiple of 16.
236	// Powers of 2 are common allocation sizes, so make powers of 2 generate the minimum required size.
237	static const unsigned int bucketSizes[] @= { // different bucket sizes
238	16, 32, 48, 64 + sizeof(HeapManager.Storage), // 4
239	96, 112, 128 + sizeof(HeapManager.Storage), // 3
240	160, 192, 224, 256 + sizeof(HeapManager.Storage), // 4
241	320, 384, 448, 512 + sizeof(HeapManager.Storage), // 4
242	640, 768, 896, 1_024 + sizeof(HeapManager.Storage), // 4
243	1_536, 2_048 + sizeof(HeapManager.Storage), // 2
244	2_560, 3_072, 3_584, 4_096 + sizeof(HeapManager.Storage), // 4
245	6_144, 8_192 + sizeof(HeapManager.Storage), // 2
246	9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360, 16_384 + sizeof(HeapManager.Storage), // 8
247	18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720, 32_768 + sizeof(HeapManager.Storage), // 8
248	36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440, 65_536 + sizeof(HeapManager.Storage), // 8
249	73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880, 131_072 + sizeof(HeapManager.Storage), // 8
250	147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760, 262_144 + sizeof(HeapManager.Storage), // 8
251	294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520, 524_288 + sizeof(HeapManager.Storage), // 8
252	655_360, 786_432, 917_504, 1_048_576 + sizeof(HeapManager.Storage), // 4
253	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(HeapManager.Storage), // 8
254	2_621_440, 3_145_728, 3_670_016, 4_194_304 + sizeof(HeapManager.Storage), // 4
255	};
256
257	static_assert( NoBucketSizes == sizeof(bucketSizes) / sizeof(bucketSizes[0]), "size of bucket array wrong" );
258
259	#ifdef FASTLOOKUP
260	enum { LookupSizes = 65_536 + sizeof(HeapManager.Storage) }; // number of fast lookup sizes
261	static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes
262	#endif // FASTLOOKUP
263
264	static int mmapFd = -1; // fake or actual fd for anonymous file
265	#ifdef __CFA_DEBUG__
266	static bool heapBoot = 0; // detect recursion during boot
267	#endif // __CFA_DEBUG__
268	static HeapManager heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing
269
270
271	#ifdef __STATISTICS__
272	// Heap statistics counters.
273	static unsigned long long int mmap_storage;
274	static unsigned int mmap_calls;
275	static unsigned long long int munmap_storage;
276	static unsigned int munmap_calls;
277	static unsigned long long int sbrk_storage;
278	static unsigned int sbrk_calls;
279	static unsigned long long int malloc_storage;
280	static unsigned int malloc_calls;
281	static unsigned long long int free_storage;
282	static unsigned int free_calls;
283	static unsigned long long int calloc_storage;
284	static unsigned int calloc_calls;
285	static unsigned long long int memalign_storage;
286	static unsigned int memalign_calls;
287	static unsigned long long int cmemalign_storage;
288	static unsigned int cmemalign_calls;
289	static unsigned long long int realloc_storage;
290	static unsigned int realloc_calls;
291	// Statistics file descriptor (changed by malloc_stats_fd).
292	static int statfd = STDERR_FILENO; // default stderr
293
294	// Use "write" because streams may be shutdown when calls are made.
295	static void printStats() {
296	char helpText[512];
297	__cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText),
298	"\nHeap statistics:\n"
299	" malloc: calls %u / storage %llu\n"
300	" calloc: calls %u / storage %llu\n"
301	" memalign: calls %u / storage %llu\n"
302	" cmemalign: calls %u / storage %llu\n"
303	" realloc: calls %u / storage %llu\n"
304	" free: calls %u / storage %llu\n"
305	" mmap: calls %u / storage %llu\n"
306	" munmap: calls %u / storage %llu\n"
307	" sbrk: calls %u / storage %llu\n",
308	malloc_calls, malloc_storage,
309	calloc_calls, calloc_storage,
310	memalign_calls, memalign_storage,
311	cmemalign_calls, cmemalign_storage,
312	realloc_calls, realloc_storage,
313	free_calls, free_storage,
314	mmap_calls, mmap_storage,
315	munmap_calls, munmap_storage,
316	sbrk_calls, sbrk_storage
317	);
318	} // printStats
319
320	static int printStatsXML( FILE * stream ) { // see malloc_info
321	char helpText[512];
322	int len = snprintf( helpText, sizeof(helpText),
323	"<malloc version=\"1\">\n"
324	"<heap nr=\"0\">\n"
325	"<sizes>\n"
326	"</sizes>\n"
327	"<total type=\"malloc\" count=\"%u\" size=\"%llu\"/>\n"
328	"<total type=\"calloc\" count=\"%u\" size=\"%llu\"/>\n"
329	"<total type=\"memalign\" count=\"%u\" size=\"%llu\"/>\n"
330	"<total type=\"cmemalign\" count=\"%u\" size=\"%llu\"/>\n"
331	"<total type=\"realloc\" count=\"%u\" size=\"%llu\"/>\n"
332	"<total type=\"free\" count=\"%u\" size=\"%llu\"/>\n"
333	"<total type=\"mmap\" count=\"%u\" size=\"%llu\"/>\n"
334	"<total type=\"munmap\" count=\"%u\" size=\"%llu\"/>\n"
335	"<total type=\"sbrk\" count=\"%u\" size=\"%llu\"/>\n"
336	"</malloc>",
337	malloc_calls, malloc_storage,
338	calloc_calls, calloc_storage,
339	memalign_calls, memalign_storage,
340	cmemalign_calls, cmemalign_storage,
341	realloc_calls, realloc_storage,
342	free_calls, free_storage,
343	mmap_calls, mmap_storage,
344	munmap_calls, munmap_storage,
345	sbrk_calls, sbrk_storage
346	);
347	__cfaabi_bits_write( fileno( stream ), helpText, len ); // ensures all bytes written or exit
348	return len;
349	} // printStatsXML
350	#endif // __STATISTICS__
351
352
353	// #comment TD : Is this the samething as Out-of-Memory?
354	static inline void noMemory() {
355	abort( "Heap memory exhausted at %zu bytes.\n"
356	"Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
357	((char )(sbrk( 0 )) - (char )(heapManager.heapBegin)) );
358	} // noMemory
359
360
361	static inline void checkAlign( size_t alignment ) {
362	if ( alignment < libAlign() \|\| ! libPow2( alignment ) ) {
363	abort( "Alignment %zu for memory allocation is less than %d and/or not a power of 2.", alignment, libAlign() );
364	} // if
365	} // checkAlign
366
367
368	static inline bool setHeapExpand( size_t value ) {
369	if ( heapExpand < pageSize ) return true;
370	heapExpand = value;
371	return false;
372	} // setHeapExpand
373
374
375	// thunk problem
376	size_t Bsearchl( unsigned int key, const unsigned int * vals, size_t dim ) {
377	size_t l = 0, m, h = dim;
378	while ( l < h ) {
379	m = (l + h) / 2;
380	if ( (unsigned int &)(vals[m]) < key ) { // cast away const
381	l = m + 1;
382	} else {
383	h = m;
384	} // if
385	} // while
386	return l;
387	} // Bsearchl
388
389
390	static inline bool setMmapStart( size_t value ) { // true => mmapped, false => sbrk
391	if ( value < pageSize \|\| bucketSizes[NoBucketSizes - 1] < value ) return true;
392	mmapStart = value; // set global
393
394	// find the closest bucket size less than or equal to the mmapStart size
395	maxBucketsUsed = Bsearchl( (unsigned int)mmapStart, bucketSizes, NoBucketSizes ); // binary search
396	assert( maxBucketsUsed < NoBucketSizes ); // subscript failure ?
397	assert( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ?
398	return false;
399	} // setMmapStart
400
401
402	static inline void checkHeader( bool check, const char * name, void * addr ) {
403	if ( unlikely( check ) ) { // bad address ?
404	abort( "Attempt to %s storage %p with address outside the heap.\n"
405	"Possible cause is duplicate free on same block or overwriting of memory.",
406	name, addr );
407	} // if
408	} // checkHeader
409
410
411	static inline void fakeHeader( HeapManager.Storage.Header *& header, size_t & alignment ) {
412	if ( unlikely( (header->kind.fake.alignment & 1) == 1 ) ) { // fake header ?
413	size_t offset = header->kind.fake.offset;
414	alignment = header->kind.fake.alignment & -2; // remove flag from value
415	#ifdef __CFA_DEBUG__
416	checkAlign( alignment ); // check alignment
417	#endif // __CFA_DEBUG__
418	header = (HeapManager.Storage.Header )((char )header - offset);
419	} // if
420	} // fakeHeader
421
422
423	// <-------+----------------------------------------------------> bsize (bucket size)
424	// \|header \|addr
425	//==================================================================================
426	// \| alignment
427	// <-----------------<------------+-----------------------------> bsize (bucket size)
428	// \|fake-header \| addr
429	#define headerAddr( addr ) ((HeapManager.Storage.Header )( (char )addr - sizeof(HeapManager.Storage) ))
430
431	// <-------<<--------------------- dsize ---------------------->> bsize (bucket size)
432	// \|header \|addr
433	//==================================================================================
434	// \| alignment
435	// <------------------------------<<---------- dsize --------->>> bsize (bucket size)
436	// \|fake-header \|addr
437	#define dataStorage( bsize, addr, header ) (bsize - ( (char )addr - (char )header ))
438
439
440	static inline bool headers( const char * name __attribute__(( unused )), void * addr, HeapManager.Storage.Header & header, HeapManager.FreeHeader & freeElem, size_t & size, size_t & alignment ) with ( heapManager ) {
441	header = headerAddr( addr );
442
443	if ( unlikely( heapEnd < addr ) ) { // mmapped ?
444	fakeHeader( header, alignment );
445	size = header->kind.real.blockSize & -3; // mmap size
446	return true;
447	} // if
448
449	#ifdef __CFA_DEBUG__
450	checkHeader( addr < heapBegin \|\| header < (HeapManager.Storage.Header *)heapBegin, name, addr ); // bad low address ?
451	#endif // __CFA_DEBUG__
452
453	// header may be safe to dereference
454	fakeHeader( header, alignment );
455	#ifdef __CFA_DEBUG__
456	checkHeader( header < (HeapManager.Storage.Header )heapBegin \|\| (HeapManager.Storage.Header )heapEnd < header, name, addr ); // bad address ? (offset could be + or -)
457	#endif // __CFA_DEBUG__
458
459	freeElem = (HeapManager.FreeHeader *)((size_t)header->kind.real.home & -3);
460	#ifdef __CFA_DEBUG__
461	if ( freeElem < &freeLists[0] \|\| &freeLists[NoBucketSizes] <= freeElem ) {
462	abort( "Attempt to %s storage %p with corrupted header.\n"
463	"Possible cause is duplicate free on same block or overwriting of header information.",
464	name, addr );
465	} // if
466	#endif // __CFA_DEBUG__
467	size = freeElem->blockSize;
468	return false;
469	} // headers
470
471
472	static inline void * extend( size_t size ) with ( heapManager ) {
473	lock( extlock __cfaabi_dbg_ctx2 );
474	ptrdiff_t rem = heapRemaining - size;
475	if ( rem < 0 ) {
476	// If the size requested is bigger than the current remaining storage, increase the size of the heap.
477
478	size_t increase = libCeiling( size > heapExpand ? size : heapExpand, libAlign() );
479	if ( sbrk( increase ) == (void *)-1 ) {
480	unlock( extlock );
481	errno = ENOMEM;
482	return 0p;
483	} // if
484	#ifdef __STATISTICS__
485	sbrk_calls += 1;
486	sbrk_storage += increase;
487	#endif // __STATISTICS__
488	#ifdef __CFA_DEBUG__
489	// Set new memory to garbage so subsequent uninitialized usages might fail.
490	memset( (char *)heapEnd + heapRemaining, '\377', increase );
491	#endif // __CFA_DEBUG__
492	rem = heapRemaining + increase - size;
493	} // if
494
495	HeapManager.Storage * block = (HeapManager.Storage *)heapEnd;
496	heapRemaining = rem;
497	heapEnd = (char *)heapEnd + size;
498	unlock( extlock );
499	return block;
500	} // extend
501
502
503	static inline void * doMalloc( size_t size ) with ( heapManager ) {
504	HeapManager.Storage * block; // pointer to new block of storage
505
506	// Look up size in the size list. Make sure the user request includes space for the header that must be allocated
507	// along with the block and is a multiple of the alignment size.
508
509	if ( unlikely( size > ~0ul - sizeof(HeapManager.Storage) ) ) return 0p;
510	size_t tsize = size + sizeof(HeapManager.Storage);
511	if ( likely( tsize < mmapStart ) ) { // small size => sbrk
512	size_t posn;
513	#ifdef FASTLOOKUP
514	if ( tsize < LookupSizes ) posn = lookup[tsize];
515	else
516	#endif // FASTLOOKUP
517	posn = Bsearchl( (unsigned int)tsize, bucketSizes, (size_t)maxBucketsUsed );
518	HeapManager.FreeHeader * freeElem = &freeLists[posn];
519	// #ifdef FASTLOOKUP
520	// if ( tsize < LookupSizes )
521	// freeElem = &freeLists[lookup[tsize]];
522	// else
523	// #endif // FASTLOOKUP
524	// freeElem = bsearchl( tsize, freeLists, (size_t)maxBucketsUsed ); // binary search
525	// HeapManager.FreeHeader * freeElem =
526	// #ifdef FASTLOOKUP
527	// tsize < LookupSizes ? &freeLists[lookup[tsize]] :
528	// #endif // FASTLOOKUP
529	// bsearchl( tsize, freeLists, (size_t)maxBucketsUsed ); // binary search
530	assert( freeElem <= &freeLists[maxBucketsUsed] ); // subscripting error ?
531	assert( tsize <= freeElem->blockSize ); // search failure ?
532	tsize = freeElem->blockSize; // total space needed for request
533
534	// Spin until the lock is acquired for this particular size of block.
535
536	#if defined( SPINLOCK )
537	lock( freeElem->lock __cfaabi_dbg_ctx2 );
538	block = freeElem->freeList; // remove node from stack
539	#else
540	block = freeElem->freeList.pop();
541	#endif // SPINLOCK
542	if ( unlikely( block == 0p ) ) { // no free block ?
543	#if defined( SPINLOCK )
544	unlock( freeElem->lock );
545	#endif // SPINLOCK
546
547	// Freelist for that size was empty, so carve it out of the heap if there's enough left, or get some more
548	// and then carve it off.
549
550	block = (HeapManager.Storage *)extend( tsize ); // mutual exclusion on call
551	if ( unlikely( block == 0p ) ) return 0p;
552	#if defined( SPINLOCK )
553	} else {
554	freeElem->freeList = block->header.kind.real.next;
555	unlock( freeElem->lock );
556	#endif // SPINLOCK
557	} // if
558
559	block->header.kind.real.home = freeElem; // pointer back to free list of apropriate size
560	} else { // large size => mmap
561	if ( unlikely( size > ~0ul - pageSize ) ) return 0p;
562	tsize = libCeiling( tsize, pageSize ); // must be multiple of page size
563	#ifdef __STATISTICS__
564	__atomic_add_fetch( &mmap_calls, 1, __ATOMIC_SEQ_CST );
565	__atomic_add_fetch( &mmap_storage, tsize, __ATOMIC_SEQ_CST );
566	#endif // __STATISTICS__
567	block = (HeapManager.Storage *)mmap( 0, tsize, PROT_READ \| PROT_WRITE, MAP_PRIVATE \| MAP_ANONYMOUS, mmapFd, 0 );
568	if ( block == (HeapManager.Storage *)MAP_FAILED ) {
569	// Do not call strerror( errno ) as it may call malloc.
570	abort( "(HeapManager &)0x%p.doMalloc() : internal error, mmap failure, size:%zu error:%d.", &heapManager, tsize, errno );
571	} // if
572	#ifdef __CFA_DEBUG__
573	// Set new memory to garbage so subsequent uninitialized usages might fail.
574	memset( block, '\377', tsize );
575	#endif // __CFA_DEBUG__
576	block->header.kind.real.blockSize = tsize; // storage size for munmap
577	} // if
578
579	void * addr = &(block->data); // adjust off header to user bytes
580
581	#ifdef __CFA_DEBUG__
582	assert( ((uintptr_t)addr & (libAlign() - 1)) == 0 ); // minimum alignment ?
583	__atomic_add_fetch( &allocFree, tsize, __ATOMIC_SEQ_CST );
584	if ( traceHeap() ) {
585	enum { BufferSize = 64 };
586	char helpText[BufferSize];
587	int len = snprintf( helpText, BufferSize, "%p = Malloc( %zu ) (allocated %zu)\n", addr, size, tsize );
588	// int len = snprintf( helpText, BufferSize, "Malloc %p %zu\n", addr, size );
589	__cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug
590	} // if
591	#endif // __CFA_DEBUG__
592
593	return addr;
594	} // doMalloc
595
596
597	static inline void doFree( void * addr ) with ( heapManager ) {
598	#ifdef __CFA_DEBUG__
599	if ( unlikely( heapManager.heapBegin == 0p ) ) {
600	abort( "doFree( %p ) : internal error, called before heap is initialized.", addr );
601	} // if
602	#endif // __CFA_DEBUG__
603
604	HeapManager.Storage.Header * header;
605	HeapManager.FreeHeader * freeElem;
606	size_t size, alignment; // not used (see realloc)
607
608	if ( headers( "free", addr, header, freeElem, size, alignment ) ) { // mmapped ?
609	#ifdef __STATISTICS__
610	__atomic_add_fetch( &munmap_calls, 1, __ATOMIC_SEQ_CST );
611	__atomic_add_fetch( &munmap_storage, size, __ATOMIC_SEQ_CST );
612	#endif // __STATISTICS__
613	if ( munmap( header, size ) == -1 ) {
614	#ifdef __CFA_DEBUG__
615	abort( "Attempt to deallocate storage %p not allocated or with corrupt header.\n"
616	"Possible cause is invalid pointer.",
617	addr );
618	#endif // __CFA_DEBUG__
619	} // if
620	} else {
621	#ifdef __CFA_DEBUG__
622	// Set free memory to garbage so subsequent usages might fail.
623	memset( ((HeapManager.Storage *)header)->data, '\377', freeElem->blockSize - sizeof( HeapManager.Storage ) );
624	#endif // __CFA_DEBUG__
625
626	#ifdef __STATISTICS__
627	free_storage += size;
628	#endif // __STATISTICS__
629	#if defined( SPINLOCK )
630	lock( freeElem->lock __cfaabi_dbg_ctx2 ); // acquire spin lock
631	header->kind.real.next = freeElem->freeList; // push on stack
632	freeElem->freeList = (HeapManager.Storage *)header;
633	unlock( freeElem->lock ); // release spin lock
634	#else
635	freeElem->freeList.push( (HeapManager.Storage )header );
636	#endif // SPINLOCK
637	} // if
638
639	#ifdef __CFA_DEBUG__
640	__atomic_add_fetch( &allocFree, -size, __ATOMIC_SEQ_CST );
641	if ( traceHeap() ) {
642	enum { BufferSize = 64 };
643	char helpText[BufferSize];
644	int len = snprintf( helpText, sizeof(helpText), "Free( %p ) size:%zu\n", addr, size );
645	__cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug
646	} // if
647	#endif // __CFA_DEBUG__
648	} // doFree
649
650
651	size_t prtFree( HeapManager & manager ) with ( manager ) {
652	size_t total = 0;
653	#ifdef __STATISTICS__
654	__cfaabi_bits_acquire();
655	__cfaabi_bits_print_nolock( STDERR_FILENO, "\nBin lists (bin size : free blocks on list)\n" );
656	#endif // __STATISTICS__
657	for ( unsigned int i = 0; i < maxBucketsUsed; i += 1 ) {
658	size_t size = freeLists[i].blockSize;
659	#ifdef __STATISTICS__
660	unsigned int N = 0;
661	#endif // __STATISTICS__
662
663	#if defined( SPINLOCK )
664	for ( HeapManager.Storage * p = freeLists[i].freeList; p != 0p; p = p->header.kind.real.next ) {
665	#else
666	for ( HeapManager.Storage * p = freeLists[i].freeList.top(); p != 0p; p = p->header.kind.real.next.top ) {
667	#endif // SPINLOCK
668	total += size;
669	#ifdef __STATISTICS__
670	N += 1;
671	#endif // __STATISTICS__
672	} // for
673
674	#ifdef __STATISTICS__
675	__cfaabi_bits_print_nolock( STDERR_FILENO, "%7zu, %-7u ", size, N );
676	if ( (i + 1) % 8 == 0 ) __cfaabi_bits_print_nolock( STDERR_FILENO, "\n" );
677	#endif // __STATISTICS__
678	} // for
679	#ifdef __STATISTICS__
680	__cfaabi_bits_print_nolock( STDERR_FILENO, "\ntotal free blocks:%zu\n", total );
681	__cfaabi_bits_release();
682	#endif // __STATISTICS__
683	return (char )heapEnd - (char )heapBegin - total;
684	} // prtFree
685
686
687	static void ?{}( HeapManager & manager ) with ( manager ) {
688	pageSize = sysconf( _SC_PAGESIZE );
689
690	for ( unsigned int i = 0; i < NoBucketSizes; i += 1 ) { // initialize the free lists
691	freeLists[i].blockSize = bucketSizes[i];
692	} // for
693
694	#ifdef FASTLOOKUP
695	unsigned int idx = 0;
696	for ( unsigned int i = 0; i < LookupSizes; i += 1 ) {
697	if ( i > bucketSizes[idx] ) idx += 1;
698	lookup[i] = idx;
699	} // for
700	#endif // FASTLOOKUP
701
702	if ( setMmapStart( default_mmap_start() ) ) {
703	abort( "HeapManager : internal error, mmap start initialization failure." );
704	} // if
705	heapExpand = default_heap_expansion();
706
707	char * end = (char *)sbrk( 0 );
708	sbrk( (char *)libCeiling( (long unsigned int)end, libAlign() ) - end ); // move start of heap to multiple of alignment
709	heapBegin = heapEnd = sbrk( 0 ); // get new start point
710	} // HeapManager
711
712
713	static void ^?{}( HeapManager & ) {
714	#ifdef __STATISTICS__
715	// if ( traceHeapTerm() ) {
716	// printStats();
717	// if ( prtfree() ) prtFree( heapManager, true );
718	// } // if
719	#endif // __STATISTICS__
720	} // ~HeapManager
721
722
723	static void memory_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_MEMORY ) ));
724	void memory_startup( void ) {
725	#ifdef __CFA_DEBUG__
726	if ( unlikely( heapBoot ) ) { // check for recursion during system boot
727	// DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
728	abort( "boot() : internal error, recursively invoked during system boot." );
729	} // if
730	heapBoot = true;
731	#endif // __CFA_DEBUG__
732
733	//assert( heapManager.heapBegin != 0 );
734	//heapManager{};
735	if ( heapManager.heapBegin == 0p ) heapManager{};
736	} // memory_startup
737
738	static void memory_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_MEMORY ) ));
739	void memory_shutdown( void ) {
740	^heapManager{};
741	} // memory_shutdown
742
743
744	static inline void * mallocNoStats( size_t size ) { // necessary for malloc statistics
745	//assert( heapManager.heapBegin != 0 );
746	if ( unlikely( heapManager.heapBegin == 0p ) ) heapManager{}; // called before memory_startup ?
747	void * addr = doMalloc( size );
748	if ( unlikely( addr == 0p ) ) errno = ENOMEM; // POSIX
749	return addr;
750	} // mallocNoStats
751
752
753	static inline void * callocNoStats( size_t noOfElems, size_t elemSize ) {
754	size_t size = noOfElems * elemSize;
755	char * addr = (char *)mallocNoStats( size );
756	if ( unlikely( addr == 0p ) ) return 0p;
757
758	HeapManager.Storage.Header * header;
759	HeapManager.FreeHeader * freeElem;
760	size_t bsize, alignment;
761	bool mapped __attribute__(( unused )) = headers( "calloc", addr, header, freeElem, bsize, alignment );
762	#ifndef __CFA_DEBUG__
763	// Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
764	if ( ! mapped )
765	#endif // __CFA_DEBUG__
766	// Zero entire data space even when > than size => realloc without a new allocation and zero fill works.
767	// <-------00000000000000000000000000000000000000000000000000000> bsize (bucket size)
768	// `-header`-addr `-size
769	memset( addr, '\0', bsize - sizeof(HeapManager.Storage) ); // set to zeros
770
771	header->kind.real.blockSize \|= 2; // mark as zero filled
772	return addr;
773	} // callocNoStats
774
775
776	static inline void * memalignNoStats( size_t alignment, size_t size ) { // necessary for malloc statistics
777	#ifdef __CFA_DEBUG__
778	checkAlign( alignment ); // check alignment
779	#endif // __CFA_DEBUG__
780
781	// if alignment <= default alignment, do normal malloc as two headers are unnecessary
782	if ( unlikely( alignment <= libAlign() ) ) return mallocNoStats( size );
783
784	// Allocate enough storage to guarantee an address on the alignment boundary, and sufficient space before it for
785	// administrative storage. NOTE, WHILE THERE ARE 2 HEADERS, THE FIRST ONE IS IMPLICITLY CREATED BY DOMALLOC.
786	// .-------------v-----------------v----------------v----------,
787	// \| Real Header \| ... padding ... \| Fake Header \| data ... \|
788	// `-------------^-----------------^-+--------------^----------'
789	// \|<--------------------------------' offset/align \|<-- alignment boundary
790
791	// subtract libAlign() because it is already the minimum alignment
792	// add sizeof(Storage) for fake header
793	char * addr = (char *)mallocNoStats( size + alignment - libAlign() + sizeof(HeapManager.Storage) );
794	if ( unlikely( addr == 0p ) ) return addr;
795
796	// address in the block of the "next" alignment address
797	char * user = (char *)libCeiling( (uintptr_t)(addr + sizeof(HeapManager.Storage)), alignment );
798
799	// address of header from malloc
800	HeapManager.Storage.Header * realHeader = headerAddr( addr );
801	// address of fake header * before* the alignment location
802	HeapManager.Storage.Header * fakeHeader = headerAddr( user );
803	// SKULLDUGGERY: insert the offset to the start of the actual storage block and remember alignment
804	fakeHeader->kind.fake.offset = (char )fakeHeader - (char )realHeader;
805	// SKULLDUGGERY: odd alignment imples fake header
806	fakeHeader->kind.fake.alignment = alignment \| 1;
807
808	return user;
809	} // memalignNoStats
810
811
812	static inline void * cmemalignNoStats( size_t alignment, size_t noOfElems, size_t elemSize ) {
813	size_t size = noOfElems * elemSize;
814	char * addr = (char *)memalignNoStats( alignment, size );
815	if ( unlikely( addr == 0p ) ) return 0p;
816	HeapManager.Storage.Header * header;
817	HeapManager.FreeHeader * freeElem;
818	size_t bsize;
819	bool mapped __attribute__(( unused )) = headers( "cmemalign", addr, header, freeElem, bsize, alignment );
820	#ifndef __CFA_DEBUG__
821	// Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
822	if ( ! mapped )
823	#endif // __CFA_DEBUG__
824	memset( addr, '\0', dataStorage( bsize, addr, header ) ); // set to zeros
825	header->kind.real.blockSize \|= 2; // mark as zero filled
826
827	return addr;
828	} // cmemalignNoStats
829
830
831	// supported mallopt options
832	#ifndef M_MMAP_THRESHOLD
833	#define M_MMAP_THRESHOLD (-1)
834	#endif // M_TOP_PAD
835	#ifndef M_TOP_PAD
836	#define M_TOP_PAD (-2)
837	#endif // M_TOP_PAD
838
839
840	extern "C" {
841	// The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not
842	// initialized. If size is 0, then malloc() returns either 0p, or a unique pointer value that can later be
843	// successfully passed to free().
844	void * malloc( size_t size ) {
845	#ifdef __STATISTICS__
846	__atomic_add_fetch( &malloc_calls, 1, __ATOMIC_SEQ_CST );
847	__atomic_add_fetch( &malloc_storage, size, __ATOMIC_SEQ_CST );
848	#endif // __STATISTICS__
849
850	return mallocNoStats( size );
851	} // malloc
852
853	// The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to
854	// the allocated memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either 0p, or a
855	// unique pointer value that can later be successfully passed to free().
856	void * calloc( size_t noOfElems, size_t elemSize ) {
857	#ifdef __STATISTICS__
858	__atomic_add_fetch( &calloc_calls, 1, __ATOMIC_SEQ_CST );
859	__atomic_add_fetch( &calloc_storage, noOfElems * elemSize, __ATOMIC_SEQ_CST );
860	#endif // __STATISTICS__
861
862	return callocNoStats( noOfElems, elemSize );
863	} // calloc
864
865	// The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be
866	// unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size
867	// is larger than the old size, the added memory will not be initialized. If ptr is 0p, then the call is
868	// equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not 0p, then the call
869	// is equivalent to free(ptr). Unless ptr is 0p, it must have been returned by an earlier call to malloc(),
870	// calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done.
871	void * realloc( void * oaddr, size_t size ) {
872	#ifdef __STATISTICS__
873	__atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
874	#endif // __STATISTICS__
875
876	if ( unlikely( size == 0 ) ) { free( oaddr ); return 0p; } // special cases
877	if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size );
878
879	HeapManager.Storage.Header * header;
880	HeapManager.FreeHeader * freeElem;
881	size_t bsize, oalign = 0;
882	headers( "realloc", oaddr, header, freeElem, bsize, oalign );
883
884	size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket
885	if ( size <= odsize && odsize <= size * 2 ) { // allow up to 50% wasted storage in smaller size
886	// Do not know size of original allocation => cannot do 0 fill for any additional space because do not know
887	// where to start filling, i.e., do not overwrite existing values in space.
888	//
889	// This case does not result in a new profiler entry because the previous one still exists and it must match with
890	// the free for this memory. Hence, this realloc does not appear in the profiler output.
891	return oaddr;
892	} // if
893
894	#ifdef __STATISTICS__
895	__atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
896	#endif // __STATISTICS__
897
898	// change size and copy old content to new storage
899
900	void * naddr;
901	if ( unlikely( oalign != 0 ) ) { // previous request memalign?
902	if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill
903	naddr = cmemalignNoStats( oalign, 1, size ); // create new aligned area
904	} else {
905	naddr = memalignNoStats( oalign, size ); // create new aligned area
906	} // if
907	} else {
908	if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill
909	naddr = callocNoStats( 1, size ); // create new area
910	} else {
911	naddr = mallocNoStats( size ); // create new area
912	} // if
913	} // if
914	if ( unlikely( naddr == 0p ) ) return 0p;
915
916	headers( "realloc", naddr, header, freeElem, bsize, oalign );
917	size_t ndsize = dataStorage( bsize, naddr, header ); // data storage avilable in bucket
918	// To preserve prior fill, the entire bucket must be copied versus the size.
919	memcpy( naddr, oaddr, MIN( odsize, ndsize ) ); // copy bytes
920	free( oaddr );
921	return naddr;
922	} // realloc
923
924	// The obsolete function memalign() allocates size bytes and returns a pointer to the allocated memory. The memory
925	// address will be a multiple of alignment, which must be a power of two.
926	void * memalign( size_t alignment, size_t size ) {
927	#ifdef __STATISTICS__
928	__atomic_add_fetch( &memalign_calls, 1, __ATOMIC_SEQ_CST );
929	__atomic_add_fetch( &memalign_storage, size, __ATOMIC_SEQ_CST );
930	#endif // __STATISTICS__
931
932	return memalignNoStats( alignment, size );
933	} // memalign
934
935
936	// The cmemalign() function is the same as calloc() with memory alignment.
937	void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ) {
938	#ifdef __STATISTICS__
939	__atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST );
940	__atomic_add_fetch( &cmemalign_storage, noOfElems * elemSize, __ATOMIC_SEQ_CST );
941	#endif // __STATISTICS__
942
943	return cmemalignNoStats( alignment, noOfElems, elemSize );
944	} // cmemalign
945
946	// The function aligned_alloc() is the same as memalign(), except for the added restriction that size should be a
947	// multiple of alignment.
948	void * aligned_alloc( size_t alignment, size_t size ) {
949	return memalign( alignment, size );
950	} // aligned_alloc
951
952
953	// The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr. The
954	// address of the allocated memory will be a multiple of alignment, which must be a power of two and a multiple of
955	// sizeof(void *). If size is 0, then posix_memalign() returns either 0p, or a unique pointer value that can later
956	// be successfully passed to free(3).
957	int posix_memalign( void ** memptr, size_t alignment, size_t size ) {
958	if ( alignment < sizeof(void *) \|\| ! libPow2( alignment ) ) return EINVAL; // check alignment
959	* memptr = memalign( alignment, size );
960	if ( unlikely( * memptr == 0p ) ) return ENOMEM;
961	return 0;
962	} // posix_memalign
963
964	// The obsolete function valloc() allocates size bytes and returns a pointer to the allocated memory. The memory
965	// address will be a multiple of the page size. It is equivalent to memalign(sysconf(_SC_PAGESIZE),size).
966	void * valloc( size_t size ) {
967	return memalign( pageSize, size );
968	} // valloc
969
970
971	// The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to
972	// malloc(), calloc() or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior
973	// occurs. If ptr is 0p, no operation is performed.
974	void free( void * addr ) {
975	#ifdef __STATISTICS__
976	__atomic_add_fetch( &free_calls, 1, __ATOMIC_SEQ_CST );
977	#endif // __STATISTICS__
978
979	if ( unlikely( addr == 0p ) ) { // special case
980	// #ifdef __CFA_DEBUG__
981	// if ( traceHeap() ) {
982	// #define nullmsg "Free( 0x0 ) size:0\n"
983	// // Do not debug print free( 0p ), as it can cause recursive entry from sprintf.
984	// __cfaabi_dbg_write( nullmsg, sizeof(nullmsg) - 1 );
985	// } // if
986	// #endif // __CFA_DEBUG__
987	return;
988	} // exit
989
990	doFree( addr );
991	} // free
992
993
994	// The malloc_alignment() function returns the alignment of the allocation.
995	size_t malloc_alignment( void * addr ) {
996	if ( unlikely( addr == 0p ) ) return libAlign(); // minimum alignment
997	HeapManager.Storage.Header * header = headerAddr( addr );
998	if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ?
999	return header->kind.fake.alignment & -2; // remove flag from value
1000	} else {
1001	return libAlign (); // minimum alignment
1002	} // if
1003	} // malloc_alignment
1004
1005
1006	// The malloc_zero_fill() function returns true if the allocation is zero filled, i.e., initially allocated by calloc().
1007	bool malloc_zero_fill( void * addr ) {
1008	if ( unlikely( addr == 0p ) ) return false; // null allocation is not zero fill
1009	HeapManager.Storage.Header * header = headerAddr( addr );
1010	if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ?
1011	header = (HeapManager.Storage.Header )((char )header - header->kind.fake.offset);
1012	} // if
1013	return (header->kind.real.blockSize & 2) != 0; // zero filled (calloc/cmemalign) ?
1014	} // malloc_zero_fill
1015
1016
1017	// The malloc_usable_size() function returns the number of usable bytes in the block pointed to by ptr, a pointer to
1018	// a block of memory allocated by malloc(3) or a related function.
1019	size_t malloc_usable_size( void * addr ) {
1020	if ( unlikely( addr == 0p ) ) return 0; // null allocation has 0 size
1021	HeapManager.Storage.Header * header;
1022	HeapManager.FreeHeader * freeElem;
1023	size_t bsize, alignment;
1024
1025	headers( "malloc_usable_size", addr, header, freeElem, bsize, alignment );
1026	return dataStorage( bsize, addr, header ); // data storage in bucket
1027	} // malloc_usable_size
1028
1029
1030	// The malloc_stats() function prints (on default standard error) statistics about memory allocated by malloc(3) and
1031	// related functions.
1032	void malloc_stats( void ) {
1033	#ifdef __STATISTICS__
1034	printStats();
1035	if ( prtFree() ) prtFree( heapManager );
1036	#endif // __STATISTICS__
1037	} // malloc_stats
1038
1039	// The malloc_stats_fd() function changes the file descripter where malloc_stats() writes the statistics.
1040	int malloc_stats_fd( int fd __attribute__(( unused )) ) {
1041	#ifdef __STATISTICS__
1042	int temp = statfd;
1043	statfd = fd;
1044	return temp;
1045	#else
1046	return -1;
1047	#endif // __STATISTICS__
1048	} // malloc_stats_fd
1049
1050
1051	// The mallopt() function adjusts parameters that control the behavior of the memory-allocation functions (see
1052	// malloc(3)). The param argument specifies the parameter to be modified, and value specifies the new value for that
1053	// parameter.
1054	int mallopt( int option, int value ) {
1055	choose( option ) {
1056	case M_TOP_PAD:
1057	if ( setHeapExpand( value ) ) return 1;
1058	case M_MMAP_THRESHOLD:
1059	if ( setMmapStart( value ) ) return 1;
1060	} // switch
1061	return 0; // error, unsupported
1062	} // mallopt
1063
1064	// The malloc_trim() function attempts to release free memory at the top of the heap (by calling sbrk(2) with a
1065	// suitable argument).
1066	int malloc_trim( size_t ) {
1067	return 0; // => impossible to release memory
1068	} // malloc_trim
1069
1070
1071	// The malloc_info() function exports an XML string that describes the current state of the memory-allocation
1072	// implementation in the caller. The string is printed on the file stream stream. The exported string includes
1073	// information about all arenas (see malloc(3)).
1074	int malloc_info( int options, FILE * stream ) {
1075	if ( options != 0 ) { errno = EINVAL; return -1; }
1076	return printStatsXML( stream );
1077	} // malloc_info
1078
1079
1080	// The malloc_get_state() function records the current state of all malloc(3) internal bookkeeping variables (but
1081	// not the actual contents of the heap or the state of malloc_hook(3) functions pointers). The state is recorded in
1082	// a system-dependent opaque data structure dynamically allocated via malloc(3), and a pointer to that data
1083	// structure is returned as the function result. (It is the caller's responsibility to free(3) this memory.)
1084	void * malloc_get_state( void ) {
1085	return 0p; // unsupported
1086	} // malloc_get_state
1087
1088
1089	// The malloc_set_state() function restores the state of all malloc(3) internal bookkeeping variables to the values
1090	// recorded in the opaque data structure pointed to by state.
1091	int malloc_set_state( void * ptr ) {
1092	return 0; // unsupported
1093	} // malloc_set_state
1094	} // extern "C"
1095
1096
1097	// Must have CFA linkage to overload with C linkage realloc.
1098	void * realloc( void * oaddr, size_t nalign, size_t size ) {
1099	#ifdef __STATISTICS__
1100	__atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
1101	#endif // __STATISTICS__
1102
1103	if ( unlikely( size == 0 ) ) { free( oaddr ); return 0p; } // special cases
1104	if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size );
1105
1106	if ( unlikely( nalign == 0 ) ) nalign = libAlign(); // reset alignment to minimum
1107	#ifdef __CFA_DEBUG__
1108	else
1109	checkAlign( nalign ); // check alignment
1110	#endif // __CFA_DEBUG__
1111
1112	HeapManager.Storage.Header * header;
1113	HeapManager.FreeHeader * freeElem;
1114	size_t bsize, oalign = 0;
1115	headers( "realloc", oaddr, header, freeElem, bsize, oalign );
1116	size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket
1117
1118	if ( oalign != 0 && (uintptr_t)oaddr % nalign == 0 ) { // has alignment and just happens to work out
1119	headerAddr( oaddr )->kind.fake.alignment = nalign \| 1; // update alignment (could be the same)
1120	return realloc( oaddr, size );
1121	} // if
1122
1123	#ifdef __STATISTICS__
1124	__atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
1125	#endif // __STATISTICS__
1126
1127	// change size and copy old content to new storage
1128
1129	void * naddr;
1130	if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill
1131	naddr = cmemalignNoStats( nalign, 1, size ); // create new aligned area
1132	} else {
1133	naddr = memalignNoStats( nalign, size ); // create new aligned area
1134	} // if
1135
1136	headers( "realloc", naddr, header, freeElem, bsize, oalign );
1137	size_t ndsize = dataStorage( bsize, naddr, header ); // data storage avilable in bucket
1138	// To preserve prior fill, the entire bucket must be copied versus the size.
1139	memcpy( naddr, oaddr, MIN( odsize, ndsize ) ); // copy bytes
1140	free( oaddr );
1141	return naddr;
1142	} // realloc
1143
1144
1145	// Local Variables: //
1146	// tab-width: 4 //
1147	// compile-command: "cfa -nodebug -O2 heap.cfa" //
1148	// End: //

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

Download in other formats:

Original Format