source: src/libcfa/heap.c @ c4f68dc

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since c4f68dc was c4f68dc, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

potential changes for ID/TD/TG problem

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