source: src/libcfa/heap.c@ 40a7d9c

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr no_list persistent-indexer pthread-emulation qualifiedEnum
Last change on this file since 40a7d9c was d46ed6e, checked in by Peter A. Buhr <pabuhr@…>, 7 years ago

first attempt for new thread-safe heap
  • Property mode set to 100644
File size: 33.3 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 Jul 25 16:42:02 2018
13// Update Count : 438
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
20extern "C" {
21#include <sys/mman.h> // mmap, munmap
22} // extern "C"
23
24#include "bits/align.h" // libPow2
25#include "bits/defs.h" // likely, unlikely
26#include "bits/locks.h" // __spinlock_t
27#include "startup.h" // STARTUP_PRIORITY_MEMORY
28#include "stdlib" // bsearchl
29#include "malloc.h"
30
31
32enum {
33 __CFA_DEFAULT_MMAP_START__ = (512 * 1024 + 1),
34 __CFA_DEFAULT_HEAP_EXPANSION__ = (1 * 1024 * 1024),
35};
36
37size_t default_mmap_start() __attribute__(( weak )) {
38 return __CFA_DEFAULT_MMAP_START__;
39} // default_mmap_start
40
41size_t default_heap_expansion() __attribute__(( weak )) {
42 return __CFA_DEFAULT_HEAP_EXPANSION__;
43} // default_heap_expansion
44
45
46// supported mallopt options
47#ifndef M_MMAP_THRESHOLD
48#define M_MMAP_THRESHOLD (-1)
49#endif // M_TOP_PAD
50#ifndef M_TOP_PAD
51#define M_TOP_PAD (-2)
52#endif // M_TOP_PAD
53
54#define FASTLOOKUP
55#define __STATISTICS__
56
57#define SPINLOCK 0
58#define LOCKFREE 1
59#define BUCKETLOCK SPINLOCK
60#if BUCKETLOCK == LOCKFREE
61#include <uStackLF.h>
62#endif // LOCKFREE
63
64#define ALIGN 16
65
66// enum { NoBucketSizes = 93, // number of buckets sizes
67// #ifdef FASTLOOKUP
68// LookupSizes = 65536, // number of fast lookup sizes
69// #endif // FASTLOOKUP
70// };
71#define NoBucketSizes 93 // number of buckets sizes
72#ifdef FASTLOOKUP
73#define LookupSizes 65536 // number of fast lookup sizes
74#endif // FASTLOOKUP
75
76
77static _Bool traceHeap = false;
78
79inline _Bool traceHeap() {
80 return traceHeap;
81} // traceHeap
82
83_Bool traceHeapOn() {
84 _Bool temp = traceHeap;
85 traceHeap = true;
86 return temp;
87} // traceHeapOn
88
89_Bool traceHeapOff() {
90 _Bool temp = traceHeap;
91 traceHeap = false;
92 return temp;
93} // traceHeapOff
94
95
96// static _Bool prtHeapTerm = false;
97
98// inline _Bool prtHeapTerm() {
99// return prtHeapTerm;
100// } // prtHeapTerm
101
102// _Bool prtHeapTermOn() {
103// _Bool temp = traceHeap;
104// traceHeap = true;
105// return temp;
106// } // prtHeapTermOn
107
108// _Bool prtHeapTermOff() {
109// _Bool temp = traceHeap;
110// traceHeap = false;
111// return temp;
112// } // prtHeapTermOff
113
114
115// statically allocated variables => zero filled.
116
117static size_t pageSize; // architecture pagesize
118static size_t heapExpand; // sbrk advance
119static size_t mmapStart; // cross over point for mmap
120static unsigned int maxBucketsUsed; // maximum number of buckets in use
121static unsigned int bucketSizes[NoBucketSizes] = { // different bucket sizes
122 16, 32, 48, 64,
123 80, 96, 112, 128, 144, 160, 192, 224,
124 256, 320, 384, 448, 512, 640, 768, 896,
125 1024, 1536, 2048, 2560, 3072, 3584, 4096, 6144,
126 8192, 9216, 10240, 11264, 12288, 13312, 14336, 15360,
127 16384, 18432, 20480, 22528, 24576, 26624, 28672, 30720,
128 32768, 36864, 40960, 45056, 49152, 53248, 57344, 61440,
129 65536, 73728, 81920, 90112, 98304, 106496, 114688, 122880,
130 131072, 147456, 163840, 180224, 196608, 212992, 229376, 245760,
131 262144, 294912, 327680, 360448, 393216, 425984, 458752, 491520,
132 524288, 655360, 786432, 917504, 1048576, 1179648, 1310720, 1441792,
133 1572864, 1703936, 1835008, 1966080, 2097152, 2621440, 3145728, 3670016,
134 4194304
135};
136#ifdef FASTLOOKUP
137static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes
138#endif // FASTLOOKUP
139static int mmapFd = -1; // fake or actual fd for anonymous file
140
141static unsigned int allocfree; // running total of allocations minus frees
142static unsigned int appStart; // storage allocation when application starts
143
144static void checkUnfreed() {
145 #ifdef __CFA_DEBUG__
146 unsigned int total = allocfree - appStart;
147 if ( total != 0 ) {
148 // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
149 // char helpText[512];
150 // int len = snprintf( helpText, 512, "CFA warning (UNIX pid:%ld) : program terminating with %u(0x%x) bytes of storage allocated but not freed.\n"
151 // "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n",
152 // (long int)getpid(), total, total ); // always print the UNIX pid
153 // __cfaabi_dbg_bits_write( helpText, len );
154 } // if
155 #endif // __CFA_DEBUG__
156} // checkUnfreed
157
158#ifdef __CFA_DEBUG__
159extern "C" {
160void heapAppStart() { // called by __cfaabi_appready_startup
161 appStart = allocfree;
162} // heapAppStart
163
164void heapAppStop() { // called by __cfaabi_appready_startdown
165 checkUnfreed();
166} // heapAppStop
167} // extern "C"
168#endif // __CFA_DEBUG__
169
170
171struct HeapManager {
172// struct FreeHeader; // forward declaration
173
174 struct Storage {
175 struct Header { // header
176 union Kind {
177 struct RealHeader {
178 union {
179 struct { // 32-bit word => 64-bit header, 64-bit word => 128-bit header
180 #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __U_WORDSIZE__ == 32
181 uint32_t padding; // unused, force home/blocksize to overlay alignment in fake header
182 #endif // __U_WORDSIZE__ == 32 && __U_WORDSIZE__ == 32
183
184 union {
185// FreeHeader * home; // allocated block points back to home locations (must overlay alignment)
186 void * home; // allocated block points back to home locations (must overlay alignment)
187 size_t blockSize; // size for munmap (must overlay alignment)
188 #if BUCKLOCK == SPINLOCK
189 Storage * next; // freed block points next freed block of same size
190 #endif // SPINLOCK
191 };
192
193 #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __U_WORDSIZE__ == 32
194 uint32_t padding; // unused, force home/blocksize to overlay alignment in fake header
195 #endif // __U_WORDSIZE__ == 32 && __U_WORDSIZE__ == 32
196
197 };
198 #if BUCKLOCK == LOCKFREE
199 Stack<Storage>::Link next; // freed block points next freed block of same size (double-wide)
200 #endif // LOCKFREE
201 };
202 } real;
203 struct FakeHeader {
204 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
205 uint32_t alignment; // low-order bits of home/blockSize used for tricks
206 #endif // __BYTE_ORDER__
207
208 uint32_t offset;
209
210 #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
211 uint32_t alignment; // low-order bits of home/blockSize used for tricks
212 #endif // __BYTE_ORDER__
213 } fake;
214 } kind;
215 } header; // Header
216 char pad[ALIGN - sizeof( Header )];
217 char data[0]; // storage
218 }; // Storage
219
220 static_assert( ALIGN >= sizeof( Storage ), "ALIGN < sizeof( Storage )" );
221
222 struct FreeHeader {
223 #if BUCKLOCK == SPINLOCK
224 __spinlock_t lock; // must be first field for alignment
225 Storage * freeList;
226 #elif BUCKLOCK == LOCKFREE
227 StackLF<Storage> freeList;
228 #else
229 #error undefined lock type for bucket lock
230 #endif // SPINLOCK
231 size_t blockSize; // size of allocations on this list
232 }; // FreeHeader
233
234 // must be first fields for alignment
235 __spinlock_t extlock; // protects allocation-buffer extension
236 FreeHeader freeLists[NoBucketSizes]; // buckets for different allocation sizes
237
238 void * heapBegin; // start of heap
239 void * heapEnd; // logical end of heap
240 size_t heapRemaining; // amount of storage not allocated in the current chunk
241}; // HeapManager
242
243
244static inline _Bool setMmapStart( size_t value ) {
245 if ( value < pageSize || bucketSizes[NoBucketSizes - 1] < value ) return true;
246 mmapStart = value; // set global
247
248 // find the closest bucket size less than or equal to the mmapStart size
249 maxBucketsUsed = bsearchl( (unsigned int)mmapStart, bucketSizes, NoBucketSizes ); // binary search
250 assert( maxBucketsUsed < NoBucketSizes ); // subscript failure ?
251 assert( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ?
252 return false;
253} // setMmapStart
254
255
256static void ?{}( HeapManager & manager ) with ( manager ) {
257 pageSize = sysconf( _SC_PAGESIZE );
258
259 for ( unsigned int i = 0; i < NoBucketSizes; i += 1 ) { // initialize the free lists
260 freeLists[i].blockSize = bucketSizes[i];
261 } // for
262
263 #ifdef FASTLOOKUP
264 unsigned int idx = 0;
265 for ( unsigned int i = 0; i < LookupSizes; i += 1 ) {
266 if ( i > bucketSizes[idx] ) idx += 1;
267 lookup[i] = idx;
268 } // for
269 #endif // FASTLOOKUP
270
271 if ( setMmapStart( default_mmap_start() ) ) {
272 abort( "HeapManager : internal error, mmap start initialization failure." );
273 } // if
274 heapExpand = default_heap_expansion();
275
276 char * End = (char *)sbrk( 0 );
277 sbrk( (char *)libCeiling( (long unsigned int)End, libAlign() ) - End ); // move start of heap to multiple of alignment
278 heapBegin = heapEnd = sbrk( 0 ); // get new start point
279} // HeapManager
280
281
282static void ^?{}( HeapManager & ) {
283 #ifdef __STATISTICS__
284 // if ( prtHeapTerm() ) {
285 // printStats();
286 // checkFree( heapManager, true );
287 // } // if
288 #endif // __STATISTICS__
289} // ~HeapManager
290
291
292#ifdef __CFA_DEBUG__
293static _Bool heapBoot = 0; // detect recursion during boot
294#endif // __CFA_DEBUG__
295static HeapManager heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing
296
297static void memory_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_MEMORY ) ));
298void memory_startup( void ) {
299 #ifdef __CFA_DEBUG__
300 if ( unlikely( heapBoot ) ) { // check for recursion during system boot
301 // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
302 abort( "boot() : internal error, recursively invoked during system boot." );
303 } // if
304 heapBoot = true;
305 #endif // __CFA_DEBUG__
306
307 heapManager{};
308} // memory_startup
309
310static void memory_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_MEMORY ) ));
311void memory_shutdown( void ) {
312 ^heapManager{};
313} // memory_shutdown
314
315static inline size_t getKey( const HeapManager.FreeHeader & freeheader ) { return freeheader.blockSize; }
316
317
318#ifdef __STATISTICS__
319static unsigned long long int mmap_storage; // heap statistics counters
320static unsigned int mmap_calls;
321static unsigned long long int munmap_storage;
322static unsigned int munmap_calls;
323static unsigned long long int sbrk_storage;
324static unsigned int sbrk_calls;
325static unsigned long long int malloc_storage;
326static unsigned int malloc_calls;
327static unsigned long long int free_storage;
328static unsigned int free_calls;
329static unsigned long long int calloc_storage;
330static unsigned int calloc_calls;
331static unsigned long long int memalign_storage;
332static unsigned int memalign_calls;
333static unsigned long long int cmemalign_storage;
334static unsigned int cmemalign_calls;
335static unsigned long long int realloc_storage;
336static unsigned int realloc_calls;
337
338static int statfd; // statistics file descriptor (changed by malloc_stats_fd)
339
340
341// Use "write" because streams may be shutdown when calls are made.
342static void printStats() {
343 char helpText[512];
344 int len = snprintf( helpText, 512,
345 "\nHeap statistics:\n"
346 " malloc: calls %u / storage %llu\n"
347 " calloc: calls %u / storage %llu\n"
348 " memalign: calls %u / storage %llu\n"
349 " cmemalign: calls %u / storage %llu\n"
350 " realloc: calls %u / storage %llu\n"
351 " free: calls %u / storage %llu\n"
352 " mmap: calls %u / storage %llu\n"
353 " munmap: calls %u / storage %llu\n"
354 " sbrk: calls %u / storage %llu\n",
355 malloc_calls, malloc_storage,
356 calloc_calls, calloc_storage,
357 memalign_calls, memalign_storage,
358 cmemalign_calls, cmemalign_storage,
359 realloc_calls, realloc_storage,
360 free_calls, free_storage,
361 mmap_calls, mmap_storage,
362 munmap_calls, munmap_storage,
363 sbrk_calls, sbrk_storage
364 );
365 write( statfd, helpText, len );
366} // printStats
367
368
369static int printStatsXML( FILE * stream ) {
370 char helpText[512];
371 int len = snprintf( helpText, 512,
372 "<malloc version=\"1\">\n"
373 "<heap nr=\"0\">\n"
374 "<sizes>\n"
375 "</sizes>\n"
376 "<total type=\"malloc\" count=\"%u\" size=\"%llu\"/>\n"
377 "<total type=\"calloc\" count=\"%u\" size=\"%llu\"/>\n"
378 "<total type=\"memalign\" count=\"%u\" size=\"%llu\"/>\n"
379 "<total type=\"cmemalign\" count=\"%u\" size=\"%llu\"/>\n"
380 "<total type=\"realloc\" count=\"%u\" size=\"%llu\"/>\n"
381 "<total type=\"free\" count=\"%u\" size=\"%llu\"/>\n"
382 "<total type=\"mmap\" count=\"%u\" size=\"%llu\"/>\n"
383 "<total type=\"munmap\" count=\"%u\" size=\"%llu\"/>\n"
384 "<total type=\"sbrk\" count=\"%u\" size=\"%llu\"/>\n"
385 "</malloc>",
386 malloc_calls, malloc_storage,
387 calloc_calls, calloc_storage,
388 memalign_calls, memalign_storage,
389 cmemalign_calls, cmemalign_storage,
390 realloc_calls, realloc_storage,
391 free_calls, free_storage,
392 mmap_calls, mmap_storage,
393 munmap_calls, munmap_storage,
394 sbrk_calls, sbrk_storage
395 );
396 return write( fileno( stream ), helpText, len ); // -1 => error
397} // printStatsXML
398#endif // __STATISTICS__
399
400
401static inline void noMemory() {
402 abort( "Heap memory exhausted at %zu bytes.\n"
403 "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
404 ((char *)(sbrk( 0 )) - (char *)(heapManager.heapBegin)) );
405} // noMemory
406
407
408static inline void checkAlign( size_t alignment ) {
409 if ( alignment < sizeof(void *) || ! libPow2( alignment ) ) {
410 abort( "Alignment %zu for memory allocation is less than sizeof(void *) and/or not a power of 2.", alignment );
411 } // if
412} // checkAlign
413
414
415static inline _Bool setHeapExpand( size_t value ) {
416 if ( heapExpand < pageSize ) return true;
417 heapExpand = value;
418 return false;
419} // setHeapExpand
420
421
422static inline void checkHeader( _Bool check, const char * name, void * addr ) {
423 if ( unlikely( check ) ) { // bad address ?
424 abort( "Attempt to %s storage %p with address outside the heap.\n"
425 "Possible cause is duplicate free on same block or overwriting of memory.",
426 name, addr );
427 } // if
428} // checkHeader
429
430
431static inline void fakeHeader( HeapManager.Storage.Header *& header, size_t & size, size_t & alignment ) {
432 if ( unlikely( (header->kind.fake.alignment & 1) == 1 ) ) { // fake header ?
433 size_t offset = header->kind.fake.offset;
434 alignment = header->kind.fake.alignment & -2; // remove flag from value
435 #ifdef __CFA_DEBUG__
436 checkAlign( alignment ); // check alignment
437 #endif // __CFA_DEBUG__
438 header = (HeapManager.Storage.Header *)((char *)header - offset);
439 } // if
440} // fakeHeader
441
442
443#define headerAddr( addr ) ((HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) ))
444
445static inline _Bool headers( const char * name, void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem, size_t & size, size_t & alignment ) with ( heapManager ) {
446 header = headerAddr( addr );
447
448 if ( unlikely( heapEnd < addr ) ) { // mmapped ?
449 fakeHeader( header, size, alignment );
450 size = header->kind.real.blockSize & -3; // mmap size
451 return true;
452 } // if
453
454 #ifdef __CFA_DEBUG__
455 checkHeader( addr < heapBegin || header < (HeapManager.Storage.Header *)heapBegin, name, addr ); // bad low address ?
456 #endif // __CFA_DEBUG__
457 // header may be safe to dereference
458 fakeHeader( header, size, alignment );
459 #ifdef __CFA_DEBUG__
460 checkHeader( header < (HeapManager.Storage.Header *)heapBegin || (HeapManager.Storage.Header *)heapEnd < header, name, addr ); // bad address ? (offset could be + or -)
461 #endif // __CFA_DEBUG__
462
463 freeElem = (HeapManager.FreeHeader *)((size_t)header->kind.real.home & -3);
464 #ifdef __CFA_DEBUG__
465 if ( freeElem < &freeLists[0] || &freeLists[NoBucketSizes] <= freeElem ) {
466 abort( "Attempt to %s storage %p with corrupted header.\n"
467 "Possible cause is duplicate free on same block or overwriting of header information.",
468 name, addr );
469 } // if
470 #endif // __CFA_DEBUG__
471 size = freeElem->blockSize;
472 return false;
473} // headers
474
475
476static inline void * extend( size_t size ) with ( heapManager ) {
477 lock( extlock __cfaabi_dbg_ctx2 );
478 ptrdiff_t rem = heapRemaining - size;
479 if ( rem < 0 ) {
480 // If the size requested is bigger than the current remaining storage, increase the size of the heap.
481
482 size_t increase = libCeiling( size > heapExpand ? size : heapExpand, libAlign() );
483 if ( sbrk( increase ) == (void *)-1 ) {
484 unlock( extlock );
485 errno = ENOMEM;
486 return 0;
487 } // if
488#ifdef __STATISTICS__
489 sbrk_calls += 1;
490 sbrk_storage += increase;
491#endif // __STATISTICS__
492#ifdef __CFA_DEBUG__
493 // Set new memory to garbage so subsequent uninitialized usages might fail.
494 memset( (char *)heapEnd + heapRemaining, '\377', increase );
495#endif // __CFA_DEBUG__
496 rem = heapRemaining + increase - size;
497 } // if
498
499 HeapManager.Storage * block = (HeapManager.Storage *)heapEnd;
500 heapRemaining = rem;
501 heapEnd = (char *)heapEnd + size;
502 unlock( extlock );
503 return block;
504} // extend
505
506
507static inline void * doMalloc( size_t size ) with ( heapManager ) {
508 HeapManager.Storage * block;
509
510 // Look up size in the size list. Make sure the user request includes space for the header that must be allocated
511 // along with the block and is a multiple of the alignment size.
512
513 size_t tsize = size + sizeof(HeapManager.Storage);
514 if ( likely( tsize < mmapStart ) ) { // small size => sbrk
515 HeapManager.FreeHeader * freeElem =
516 #ifdef FASTLOOKUP
517 tsize < LookupSizes ? &freeLists[lookup[tsize]] :
518 #endif // FASTLOOKUP
519 bsearchl( tsize, freeLists, (size_t)maxBucketsUsed ); // binary search
520 assert( freeElem <= &freeLists[maxBucketsUsed] ); // subscripting error ?
521 assert( tsize <= freeElem->blockSize ); // search failure ?
522 tsize = freeElem->blockSize; // total space needed for request
523
524 // Spin until the lock is acquired for this particular size of block.
525
526 #if defined( SPINLOCK )
527 lock( freeElem->lock __cfaabi_dbg_ctx2 );
528 block = freeElem->freeList; // remove node from stack
529 #else
530 block = freeElem->freeList.pop();
531 #endif // SPINLOCK
532 if ( unlikely( block == 0 ) ) { // no free block ?
533 #if defined( SPINLOCK )
534 unlock( freeElem->lock );
535 #endif // SPINLOCK
536 // Freelist for that size was empty, so carve it out of the heap if there's enough left, or get some more
537 // and then carve it off.
538
539 block = (HeapManager.Storage *)extend( tsize ); // mutual exclusion on call
540 if ( unlikely( block == 0 ) ) return 0;
541 #if defined( SPINLOCK )
542 } else {
543 freeElem->freeList = block->header.kind.real.next;
544 unlock( freeElem->lock );
545 #endif // SPINLOCK
546 } // if
547
548 block->header.kind.real.home = freeElem; // pointer back to free list of apropriate size
549 } else { // large size => mmap
550 tsize = libCeiling( tsize, pageSize ); // must be multiple of page size
551 #ifdef __STATISTICS__
552 __atomic_add_fetch( &mmap_calls, 1, __ATOMIC_SEQ_CST );
553 __atomic_add_fetch( &mmap_storage, tsize, __ATOMIC_SEQ_CST );
554 #endif // __STATISTICS__
555 block = (HeapManager.Storage *)mmap( 0, tsize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, mmapFd, 0 );
556 if ( block == (HeapManager.Storage *)MAP_FAILED ) {
557 // Do not call strerror( errno ) as it may call malloc.
558 abort( "(HeapManager &)0x%p.doMalloc() : internal error, mmap failure, size:%zu error:%d.", &heapManager, tsize, errno );
559 } // if
560#ifdef __CFA_DEBUG__
561 // Set new memory to garbage so subsequent uninitialized usages might fail.
562 memset( block, '\377', tsize );
563#endif // __CFA_DEBUG__
564 block->header.kind.real.blockSize = tsize; // storage size for munmap
565 } // if
566
567 void * area = &(block->data); // adjust off header to user bytes
568
569 #ifdef __CFA_DEBUG__
570 assert( ((uintptr_t)area & (libAlign() - 1)) == 0 ); // minimum alignment ?
571 __atomic_add_fetch( &allocfree, tsize, __ATOMIC_SEQ_CST );
572 if ( traceHeap() ) {
573 enum { BufferSize = 64 };
574 char helpText[BufferSize];
575 int len = snprintf( helpText, BufferSize, "%p = Malloc( %zu ) (allocated %zu)\n", area, size, tsize );
576 // int len = snprintf( helpText, BufferSize, "Malloc %p %zu\n", area, size );
577 __cfaabi_dbg_bits_write( helpText, len );
578 } // if
579 #endif // __CFA_DEBUG__
580
581 return area;
582} // doMalloc
583
584
585static inline void doFree( void * addr ) with ( heapManager ) {
586 #ifdef __CFA_DEBUG__
587 if ( unlikely( heapManager.heapBegin == 0 ) ) {
588 abort( "doFree( %p ) : internal error, called before heap is initialized.", addr );
589 } // if
590 #endif // __CFA_DEBUG__
591
592 HeapManager.Storage.Header * header;
593 HeapManager.FreeHeader * freeElem;
594 size_t size, alignment; // not used (see realloc)
595
596 if ( headers( "free", addr, header, freeElem, size, alignment ) ) { // mmapped ?
597 #ifdef __STATISTICS__
598 __atomic_add_fetch( &munmap_calls, 1, __ATOMIC_SEQ_CST );
599 __atomic_add_fetch( &munmap_storage, size, __ATOMIC_SEQ_CST );
600 #endif // __STATISTICS__
601 if ( munmap( header, size ) == -1 ) {
602 #ifdef __CFA_DEBUG__
603 abort( "Attempt to deallocate storage %p not allocated or with corrupt header.\n"
604 "Possible cause is invalid pointer.",
605 addr );
606 #endif // __CFA_DEBUG__
607 } // if
608 } else {
609 #ifdef __CFA_DEBUG__
610 // Set free memory to garbage so subsequent usages might fail.
611 memset( ((HeapManager.Storage *)header)->data, '\377', freeElem->blockSize - sizeof( HeapManager.Storage ) );
612 #endif // __CFA_DEBUG__
613
614 #ifdef __STATISTICS__
615 free_storage += size;
616 #endif // __STATISTICS__
617 #if defined( SPINLOCK )
618 lock( freeElem->lock __cfaabi_dbg_ctx2 ); // acquire spin lock
619 header->kind.real.next = freeElem->freeList; // push on stack
620 freeElem->freeList = (HeapManager.Storage *)header;
621 unlock( freeElem->lock ); // release spin lock
622 #else
623 freeElem->freeList.push( *(HeapManager.Storage *)header );
624 #endif // SPINLOCK
625 } // if
626
627 #ifdef __CFA_DEBUG__
628 __atomic_add_fetch( &allocfree, -size, __ATOMIC_SEQ_CST );
629 if ( traceHeap() ) {
630 enum { BufferSize = 64 };
631 char helpText[BufferSize];
632 int len = snprintf( helpText, BufferSize, "Free( %p ) size:%zu\n", addr, size );
633 __cfaabi_dbg_bits_write( helpText, len );
634 } // if
635 #endif // __CFA_DEBUG__
636} // doFree
637
638
639size_t checkFree( HeapManager & manager, _Bool prt ) with ( manager ) {
640 size_t total = 0;
641 #ifdef __STATISTICS__
642 __cfaabi_dbg_bits_acquire();
643 if ( prt ) __cfaabi_dbg_bits_print_nolock( "\nBin lists (bin size : free blocks on list)\n" );
644 #endif // __STATISTICS__
645 for ( unsigned int i = 0; i < maxBucketsUsed; i += 1 ) {
646 size_t size = freeLists[i].blockSize;
647 #ifdef __STATISTICS__
648 unsigned int N = 0;
649 #endif // __STATISTICS__
650 #if defined( SPINLOCK )
651 for ( HeapManager.Storage * p = freeLists[i].freeList; p != 0; p = p->header.kind.real.next ) {
652 #else
653 for ( HeapManager.Storage * p = freeLists[i].freeList.top(); p != 0; p = p->header.kind.real.next.top ) {
654 #endif // SPINLOCK
655 total += size;
656 #ifdef __STATISTICS__
657 N += 1;
658 #endif // __STATISTICS__
659 } // for
660 #ifdef __STATISTICS__
661 if ( prt ) __cfaabi_dbg_bits_print_nolock( "%7zu, %-7u ", size, N );
662 if ( (i + 1) % 8 == 0 ) __cfaabi_dbg_bits_print_nolock( "\n" );
663 #endif // __STATISTICS__
664 } // for
665 #ifdef __STATISTICS__
666 if ( prt ) __cfaabi_dbg_bits_print_nolock( "\ntotal free blocks:%zu\n", total );
667 __cfaabi_dbg_bits_release();
668 #endif // __STATISTICS__
669 return (char *)heapEnd - (char *)heapBegin - total;
670} // checkFree
671
672
673static inline void * malloc2( size_t size ) { // necessary for malloc statistics
674 assert( heapManager.heapBegin != 0 ) ; // heap started
675 void * area = doMalloc( size );
676 if ( unlikely( area == 0 ) ) errno = ENOMEM; // POSIX
677 return area;
678} // malloc2
679
680
681static inline void * memalign2( size_t alignment, size_t size ) { // necessary for malloc statistics
682#ifdef __CFA_DEBUG__
683 checkAlign( alignment ); // check alignment
684#endif // __CFA_DEBUG__
685
686 // if alignment <= default alignment, do normal malloc as two headers are unnecessary
687 if ( unlikely( alignment <= libAlign() ) ) return malloc2( size );
688
689 // Allocate enough storage to guarantee an address on the alignment boundary, and sufficient space before it for
690 // administrative storage. NOTE, WHILE THERE ARE 2 HEADERS, THE FIRST ONE IS IMPLICITLY CREATED BY DOMALLOC.
691 // .-------------v-----------------v----------------v----------,
692 // | Real Header | ... padding ... | Fake Header | data ... |
693 // `-------------^-----------------^-+--------------^----------'
694 // |<--------------------------------' offset/align |<-- alignment boundary
695
696 // subtract libAlign() because it is already the minimum alignment
697 // add sizeof(Storage) for fake header
698 char * area = (char *)doMalloc( size + alignment - libAlign() + sizeof(HeapManager.Storage) );
699 if ( unlikely( area == 0 ) ) return area;
700
701 // address in the block of the "next" alignment address
702 char * user = (char *)libCeiling( (uintptr_t)(area + sizeof(HeapManager.Storage)), alignment );
703
704 // address of header from malloc
705 HeapManager.Storage.Header * realHeader = headerAddr( area );
706 // address of fake header * before* the alignment location
707 HeapManager.Storage.Header * fakeHeader = headerAddr( user );
708 // SKULLDUGGERY: insert the offset to the start of the actual storage block and remember alignment
709 fakeHeader->kind.fake.offset = (char *)fakeHeader - (char *)realHeader;
710 // SKULLDUGGERY: odd alignment imples fake header
711 fakeHeader->kind.fake.alignment = alignment | 1;
712
713 return user;
714} // memalign2
715
716
717extern "C" {
718 void * malloc( size_t size ) {
719 #ifdef __STATISTICS__
720 __atomic_add_fetch( &malloc_calls, 1, __ATOMIC_SEQ_CST );
721 __atomic_add_fetch( &malloc_storage, size, __ATOMIC_SEQ_CST );
722 #endif // __STATISTICS__
723
724 return malloc2( size );
725 } // malloc
726
727
728 void * calloc( size_t noOfElems, size_t elemSize ) {
729 size_t size = noOfElems * elemSize;
730 #ifdef __STATISTICS__
731 __atomic_add_fetch( &calloc_calls, 1, __ATOMIC_SEQ_CST );
732 __atomic_add_fetch( &calloc_storage, size, __ATOMIC_SEQ_CST );
733 #endif // __STATISTICS__
734
735 char * area = (char *)malloc2( size );
736 if ( unlikely( area == 0 ) ) return 0;
737 HeapManager.Storage.Header * header;
738 HeapManager.FreeHeader * freeElem;
739 size_t asize, alignment;
740 _Bool mapped __attribute__(( unused )) = headers( "calloc", area, header, freeElem, asize, alignment );
741 #ifndef __CFA_DEBUG__
742 // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
743 if ( ! mapped )
744 #endif // __CFA_DEBUG__
745 memset( area, '\0', asize - sizeof(HeapManager.Storage) ); // set to zeros
746 header->kind.real.blockSize |= 2; // mark as zero filled
747 return area;
748 } // calloc
749
750
751 void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ) {
752 size_t size = noOfElems * elemSize;
753 #ifdef __STATISTICS__
754 __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST );
755 __atomic_add_fetch( &cmemalign_storage, size, __ATOMIC_SEQ_CST );
756 #endif // __STATISTICS__
757
758 char * area = (char *)memalign2( alignment, size );
759 if ( unlikely( area == 0 ) ) return 0;
760 HeapManager.Storage.Header * header;
761 HeapManager.FreeHeader * freeElem;
762 size_t asize;
763 _Bool mapped __attribute__(( unused )) = headers( "cmemalign", area, header, freeElem, asize, alignment );
764 #ifndef __CFA_DEBUG__
765 // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
766 if ( ! mapped )
767 #endif // __CFA_DEBUG__
768 memset( area, '\0', asize - ( (char *)area - (char *)header ) ); // set to zeros
769 header->kind.real.blockSize |= 2; // mark as zero filled
770
771 return area;
772 } // cmemalign
773
774
775 void * realloc( void * addr, size_t size ) {
776 #ifdef __STATISTICS__
777 __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
778 #endif // __STATISTICS__
779
780 if ( unlikely( addr == 0 ) ) return malloc2( size ); // special cases
781 if ( unlikely( size == 0 ) ) { free( addr ); return 0; }
782
783 HeapManager.Storage.Header * header;
784 HeapManager.FreeHeader * freeElem;
785 size_t asize, alignment = 0;
786 headers( "realloc", addr, header, freeElem, asize, alignment );
787
788 size_t usize = asize - ( (char *)addr - (char *)header ); // compute the amount of user storage in the block
789 if ( usize >= size ) { // already sufficient storage
790 // This case does not result in a new profiler entry because the previous one still exists and it must match with
791 // the free for this memory. Hence, this realloc does not appear in the profiler output.
792 return addr;
793 } // if
794
795 #ifdef __STATISTICS__
796 __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
797 #endif // __STATISTICS__
798
799 void * area;
800 if ( unlikely( alignment != 0 ) ) { // previous request memalign?
801 area = memalign( alignment, size ); // create new area
802 } else {
803 area = malloc2( size ); // create new area
804 } // if
805 if ( unlikely( area == 0 ) ) return 0;
806 if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill (calloc/cmemalign) ?
807 assert( (header->kind.real.blockSize & 1) == 0 );
808 _Bool mapped __attribute__(( unused )) = headers( "realloc", area, header, freeElem, asize, alignment );
809 #ifndef __CFA_DEBUG__
810 // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
811 if ( ! mapped )
812 #endif // __CFA_DEBUG__
813 memset( (char *)area + usize, '\0', asize - ( (char *)area - (char *)header ) - usize ); // zero-fill back part
814 header->kind.real.blockSize |= 2; // mark new request as zero fill
815 } // if
816 memcpy( area, addr, usize ); // copy bytes
817 free( addr );
818 return area;
819 } // realloc
820
821
822 void * memalign( size_t alignment, size_t size ) {
823 #ifdef __STATISTICS__
824 __atomic_add_fetch( &memalign_calls, 1, __ATOMIC_SEQ_CST );
825 __atomic_add_fetch( &memalign_storage, size, __ATOMIC_SEQ_CST );
826 #endif // __STATISTICS__
827
828 void * area = memalign2( alignment, size );
829
830 return area;
831 } // memalign
832
833
834 void * aligned_alloc( size_t alignment, size_t size ) {
835 return memalign( alignment, size );
836 } // aligned_alloc
837
838
839 int posix_memalign( void ** memptr, size_t alignment, size_t size ) {
840 if ( alignment < sizeof(void *) || ! libPow2( alignment ) ) return EINVAL; // check alignment
841 * memptr = memalign( alignment, size );
842 if ( unlikely( * memptr == 0 ) ) return ENOMEM;
843 return 0;
844 } // posix_memalign
845
846
847 void * valloc( size_t size ) {
848 return memalign( pageSize, size );
849 } // valloc
850
851
852 void free( void * addr ) {
853 #ifdef __STATISTICS__
854 __atomic_add_fetch( &free_calls, 1, __ATOMIC_SEQ_CST );
855 #endif // __STATISTICS__
856
857 if ( unlikely( addr == 0 ) ) { // special case
858 #ifdef __CFA_DEBUG__
859 if ( traceHeap() ) {
860 #define nullmsg "Free( 0x0 ) size:0\n"
861 // Do not debug print free( 0 ), as it can cause recursive entry from sprintf.
862 __cfaabi_dbg_bits_write( nullmsg, sizeof(nullmsg) - 1 );
863 } // if
864 #endif // __CFA_DEBUG__
865 return;
866 } // exit
867
868 doFree( addr );
869 } // free
870
871 int mallopt( int option, int value ) {
872 choose( option ) {
873 case M_TOP_PAD:
874 if ( setHeapExpand( value ) ) fallthru default;
875 case M_MMAP_THRESHOLD:
876 if ( setMmapStart( value ) ) fallthru default;
877 default:
878 return 1; // success, or unsupported
879 } // switch
880 return 0; // error
881 } // mallopt
882
883
884 int malloc_trim( size_t ) {
885 return 0; // => impossible to release memory
886 } // malloc_trim
887
888 size_t malloc_usable_size( void * addr ) {
889 if ( unlikely( addr == 0 ) ) return 0; // null allocation has 0 size
890 HeapManager.Storage.Header * header;
891 HeapManager.FreeHeader * freeElem;
892 size_t size, alignment;
893
894 headers( "malloc_usable_size", addr, header, freeElem, size, alignment );
895 size_t usize = size - ( (char *)addr - (char *)header ); // compute the amount of user storage in the block
896 return usize;
897 } // malloc_usable_size
898
899
900 size_t malloc_alignment( void * addr ) {
901 if ( unlikely( addr == 0 ) ) return libAlign(); // minimum alignment
902 HeapManager.Storage.Header * header = (HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) );
903 if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ?
904 return header->kind.fake.alignment & -2; // remove flag from value
905 } else {
906 return libAlign (); // minimum alignment
907 } // if
908 } // malloc_alignment
909
910
911 _Bool malloc_zero_fill( void * addr ) {
912 if ( unlikely( addr == 0 ) ) return false; // null allocation is not zero fill
913 HeapManager.Storage.Header * header = (HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) );
914 if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ?
915 header = (HeapManager.Storage.Header *)((char *)header - header->kind.fake.offset);
916 } // if
917 return (header->kind.real.blockSize & 2) != 0; // zero filled (calloc/cmemalign) ?
918 } // malloc_zero_fill
919
920
921 void malloc_stats( void ) {
922 #ifdef __STATISTICS__
923 printStats();
924 checkFree( heapManager, true );
925 #endif // __STATISTICS__
926 } // malloc_stats
927
928
929 int malloc_stats_fd( int fd ) {
930 #ifdef __STATISTICS__
931 int temp = statfd;
932 statfd = fd;
933 return temp;
934 #else
935 return -1;
936 #endif // __STATISTICS__
937 } // malloc_stats_fd
938
939
940 int malloc_info( int options, FILE * stream ) {
941 return printStatsXML( stream );
942 } // malloc_info
943
944
945 void * malloc_get_state( void ) {
946 return 0;
947 } // malloc_get_state
948
949
950 int malloc_set_state( void * ptr ) {
951 return 0;
952 } // malloc_set_state
953} // extern "C"
954
955
956// Local Variables: //
957// tab-width: 4 //
958// compile-command: "cfa -nodebug -O2 heap.c" //
959// End: //
Note: See TracBrowser for help on using the repository browser.