source: libcfa/src/heap.cfa@ 393d59a

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 393d59a was ada0246d, checked in by Peter A. Buhr <pabuhr@…>, 5 years ago

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