source: libcfa/src/heap.cfa@ 34d194c

Last change on this file since 34d194c was 34d194c, checked in by Peter A. Buhr <pabuhr@…>, 5 days ago

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