Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/heap.cfa

    r1aa6ecb rcfbc703d  
    1010// Created On       : Tue Dec 19 21:58:35 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Oct 18 07:42:09 2019
    13 // Update Count     : 556
     12// Last Modified On : Wed Apr  1 15:59:53 2020
     13// Update Count     : 692
    1414//
    1515
    … …  
    1818#include <stdio.h>                                                                              // snprintf, fileno
    1919#include <errno.h>                                                                              // errno
     20#include <string.h>                                                                             // memset, memcpy
    2021extern "C" {
    2122#include <sys/mman.h>                                                                   // mmap, munmap
    … …  
    2728#include "bits/locks.hfa"                                                               // __spinlock_t
    2829#include "startup.hfa"                                                                  // STARTUP_PRIORITY_MEMORY
    29 #include "stdlib.hfa"                                                                   // bsearchl
     30//#include "stdlib.hfa"                                                                 // bsearchl
    3031#include "malloc.h"
    3132
     33#define MIN(x, y) (y > x ? x : y)
    3234
    3335static bool traceHeap = false;
    3436
    35 inline bool traceHeap() {
    36         return traceHeap;
    37 } // traceHeap
     37inline bool traceHeap() { return traceHeap; }
    3838
    3939bool traceHeapOn() {
    … …  
    4949} // traceHeapOff
    5050
    51 
    52 static bool checkFree = false;
    53 
    54 inline bool checkFree() {
    55         return checkFree;
    56 } // checkFree
    57 
    58 bool checkFreeOn() {
    59         bool temp = checkFree;
    60         checkFree = true;
     51bool traceHeapTerm() { return false; }
     52
     53
     54static bool prtFree = false;
     55
     56inline bool prtFree() {
     57        return prtFree;
     58} // prtFree
     59
     60bool prtFreeOn() {
     61        bool temp = prtFree;
     62        prtFree = true;
    6163        return temp;
    62 } // checkFreeOn
    63 
    64 bool checkFreeOff() {
    65         bool temp = checkFree;
    66         checkFree = false;
     64} // prtFreeOn
     65
     66bool prtFreeOff() {
     67        bool temp = prtFree;
     68        prtFree = false;
    6769        return temp;
    68 } // checkFreeOff
    69 
    70 
    71 // static bool traceHeapTerm = false;
    72 
    73 // inline bool traceHeapTerm() {
    74 //      return traceHeapTerm;
    75 // } // traceHeapTerm
    76 
    77 // bool traceHeapTermOn() {
    78 //      bool temp = traceHeapTerm;
    79 //      traceHeapTerm = true;
    80 //      return temp;
    81 // } // traceHeapTermOn
    82 
    83 // bool traceHeapTermOff() {
    84 //      bool temp = traceHeapTerm;
    85 //      traceHeapTerm = false;
    86 //      return temp;
    87 // } // traceHeapTermOff
     70} // prtFreeOff
    8871
    8972
    9073enum {
     74        // Define the default extension heap amount in units of bytes. When the uC++ supplied heap reaches the brk address,
     75        // the brk address is extended by the extension amount.
     76        __CFA_DEFAULT_HEAP_EXPANSION__ = (1 * 1024 * 1024),
     77
     78        // Define the mmap crossover point during allocation. Allocations less than this amount are allocated from buckets;
     79        // values greater than or equal to this value are mmap from the operating system.
    9180        __CFA_DEFAULT_MMAP_START__ = (512 * 1024 + 1),
    92         __CFA_DEFAULT_HEAP_EXPANSION__ = (1 * 1024 * 1024),
    9381};
    9482
    … …  
    10593static unsigned int allocFree;                                                  // running total of allocations minus frees
    10694
    107 static void checkUnfreed() {
     95static void prtUnfreed() {
    10896        if ( allocFree != 0 ) {
    10997                // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
    110                 // char helpText[512];
    111                 // 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"
    112                 //                                      "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n",
    113                 //                                      (long int)getpid(), allocFree, allocFree ); // always print the UNIX pid
    114                 // __cfaabi_dbg_bits_write( helpText, len );
    115         } // if
    116 } // checkUnfreed
     98                char helpText[512];
     99                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"
     100                                                        "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n",
     101                                                        (long int)getpid(), allocFree, allocFree ); // always print the UNIX pid
     102                __cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug
     103        } // if
     104} // prtUnfreed
    117105
    118106extern "C" {
    … …  
    123111        void heapAppStop() {                                                            // called by __cfaabi_appready_startdown
    124112                fclose( stdin ); fclose( stdout );
    125                 checkUnfreed();
     113                prtUnfreed();
    126114        } // heapAppStop
    127115} // extern "C"
    128116#endif // __CFA_DEBUG__
     117
    129118
    130119// statically allocated variables => zero filled.
    … …  
    134123static unsigned int maxBucketsUsed;                                             // maximum number of buckets in use
    135124
    136 
    137 // #comment TD : This defined is significantly different from the __ALIGN__ define from locks.hfa
    138 #define ALIGN 16
    139125
    140126#define SPINLOCK 0
    … …  
    147133// Recursive definitions: HeapManager needs size of bucket array and bucket area needs sizeof HeapManager storage.
    148134// Break recusion by hardcoding number of buckets and statically checking number is correct after bucket array defined.
    149 enum { NoBucketSizes = 93 };                                                    // number of buckets sizes
     135enum { NoBucketSizes = 91 };                                                    // number of buckets sizes
    150136
    151137struct HeapManager {
    … …  
    164150                                                        union {
    165151//                                                              FreeHeader * home;              // allocated block points back to home locations (must overlay alignment)
     152                                                                // 2nd low-order bit => zero filled
    166153                                                                void * home;                    // allocated block points back to home locations (must overlay alignment)
    167154                                                                size_t blockSize;               // size for munmap (must overlay alignment)
    … …  
    183170                                struct FakeHeader {
    184171                                        #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
    185                                         uint32_t alignment;                                     // low-order bits of home/blockSize used for tricks
     172                                        // 1st low-order bit => fake header & alignment
     173                                        uint32_t alignment;
    186174                                        #endif // __ORDER_LITTLE_ENDIAN__
    187175
    … …  
    193181                                } fake; // FakeHeader
    194182                        } kind; // Kind
     183                        uint32_t dimension;                                                     // used by calloc-like to remember number of array elements
    195184                } header; // Header
    196                 char pad[ALIGN - sizeof( Header )];
     185                char pad[libAlign() - sizeof( Header )];
    197186                char data[0];                                                                   // storage
    198187        }; // Storage
    199188
    200         static_assert( ALIGN >= sizeof( Storage ), "ALIGN < sizeof( Storage )" );
     189        static_assert( libAlign() >= sizeof( Storage ), "libAlign() < sizeof( Storage )" );
    201190
    202191        struct FreeHeader {
    … …  
    228217#define __STATISTICS__
    229218
     219// Bucket size must be multiple of 16.
    230220// Powers of 2 are common allocation sizes, so make powers of 2 generate the minimum required size.
    231221static const unsigned int bucketSizes[] @= {                    // different bucket sizes
    232         16, 32, 48, 64,
    233         64 + sizeof(HeapManager.Storage), 96, 112, 128, 128 + sizeof(HeapManager.Storage), 160, 192, 224,
    234         256 + sizeof(HeapManager.Storage), 320, 384, 448, 512 + sizeof(HeapManager.Storage), 640, 768, 896,
    235         1_024 + sizeof(HeapManager.Storage), 1_536, 2_048 + sizeof(HeapManager.Storage), 2_560, 3_072, 3_584, 4_096 + sizeof(HeapManager.Storage), 6_144,
    236         8_192 + sizeof(HeapManager.Storage), 9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360,
    237         16_384 + sizeof(HeapManager.Storage), 18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720,
    238         32_768 + sizeof(HeapManager.Storage), 36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440,
    239         65_536 + sizeof(HeapManager.Storage), 73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880,
    240         131_072 + sizeof(HeapManager.Storage), 147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760,
    241         262_144 + sizeof(HeapManager.Storage), 294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520,
    242         524_288 + sizeof(HeapManager.Storage), 655_360, 786_432, 917_504, 1_048_576 + sizeof(HeapManager.Storage), 1_179_648, 1_310_720, 1_441_792,
    243         1_572_864, 1_703_936, 1_835_008, 1_966_080, 2_097_152 + sizeof(HeapManager.Storage), 2_621_440, 3_145_728, 3_670_016,
    244         4_194_304 + sizeof(HeapManager.Storage)
     222        16, 32, 48, 64 + sizeof(HeapManager.Storage), // 4
     223        96, 112, 128 + sizeof(HeapManager.Storage), // 3
     224        160, 192, 224, 256 + sizeof(HeapManager.Storage), // 4
     225        320, 384, 448, 512 + sizeof(HeapManager.Storage), // 4
     226        640, 768, 896, 1_024 + sizeof(HeapManager.Storage), // 4
     227        1_536, 2_048 + sizeof(HeapManager.Storage), // 2
     228        2_560, 3_072, 3_584, 4_096 + sizeof(HeapManager.Storage), // 4
     229        6_144, 8_192 + sizeof(HeapManager.Storage), // 2
     230        9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360, 16_384 + sizeof(HeapManager.Storage), // 8
     231        18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720, 32_768 + sizeof(HeapManager.Storage), // 8
     232        36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440, 65_536 + sizeof(HeapManager.Storage), // 8
     233        73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880, 131_072 + sizeof(HeapManager.Storage), // 8
     234        147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760, 262_144 + sizeof(HeapManager.Storage), // 8
     235        294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520, 524_288 + sizeof(HeapManager.Storage), // 8
     236        655_360, 786_432, 917_504, 1_048_576 + sizeof(HeapManager.Storage), // 4
     237        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
     238        2_621_440, 3_145_728, 3_670_016, 4_194_304 + sizeof(HeapManager.Storage), // 4
    245239};
    246240
    … …  
    251245static unsigned char lookup[LookupSizes];                               // O(1) lookup for small sizes
    252246#endif // FASTLOOKUP
     247
    253248static int mmapFd = -1;                                                                 // fake or actual fd for anonymous file
    254 
    255 
    256249#ifdef __CFA_DEBUG__
    257250static bool heapBoot = 0;                                                               // detect recursion during boot
    … …  
    259252static HeapManager heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing
    260253
    261 // #comment TD : The return type of this function should be commented
    262 static inline bool setMmapStart( size_t value ) {
    263   if ( value < pageSize || bucketSizes[NoBucketSizes - 1] < value ) return true;
    264         mmapStart = value;                                                                      // set global
    265 
    266         // find the closest bucket size less than or equal to the mmapStart size
    267         maxBucketsUsed = bsearchl( (unsigned int)mmapStart, bucketSizes, NoBucketSizes ); // binary search
    268         assert( maxBucketsUsed < NoBucketSizes );                       // subscript failure ?
    269         assert( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ?
    270         return false;
    271 } // setMmapStart
    272 
    273 
    274 static void ?{}( HeapManager & manager ) with ( manager ) {
    275         pageSize = sysconf( _SC_PAGESIZE );
    276 
    277         for ( unsigned int i = 0; i < NoBucketSizes; i += 1 ) { // initialize the free lists
    278                 freeLists[i].blockSize = bucketSizes[i];
    279         } // for
    280 
    281         #ifdef FASTLOOKUP
    282         unsigned int idx = 0;
    283         for ( unsigned int i = 0; i < LookupSizes; i += 1 ) {
    284                 if ( i > bucketSizes[idx] ) idx += 1;
    285                 lookup[i] = idx;
    286         } // for
    287         #endif // FASTLOOKUP
    288 
    289         if ( setMmapStart( default_mmap_start() ) ) {
    290                 abort( "HeapManager : internal error, mmap start initialization failure." );
    291         } // if
    292         heapExpand = default_heap_expansion();
    293 
    294         char * End = (char *)sbrk( 0 );
    295         sbrk( (char *)libCeiling( (long unsigned int)End, libAlign() ) - End ); // move start of heap to multiple of alignment
    296         heapBegin = heapEnd = sbrk( 0 );                                        // get new start point
    297 } // HeapManager
    298 
    299 
    300 static void ^?{}( HeapManager & ) {
    301         #ifdef __STATISTICS__
    302         // if ( traceHeapTerm() ) {
    303         //      printStats();
    304         //      if ( checkfree() ) checkFree( heapManager, true );
    305         // } // if
    306         #endif // __STATISTICS__
    307 } // ~HeapManager
    308 
    309 
    310 static void memory_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_MEMORY ) ));
    311 void memory_startup( void ) {
    312         #ifdef __CFA_DEBUG__
    313         if ( unlikely( heapBoot ) ) {                                           // check for recursion during system boot
    314                 // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
    315                 abort( "boot() : internal error, recursively invoked during system boot." );
    316         } // if
    317         heapBoot = true;
    318         #endif // __CFA_DEBUG__
    319 
    320         //assert( heapManager.heapBegin != 0 );
    321         //heapManager{};
    322         if ( heapManager.heapBegin == 0 ) heapManager{};
    323 } // memory_startup
    324 
    325 static void memory_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_MEMORY ) ));
    326 void memory_shutdown( void ) {
    327         ^heapManager{};
    328 } // memory_shutdown
    329 
    330254
    331255#ifdef __STATISTICS__
    332 static unsigned long long int mmap_storage;                             // heap statistics counters
     256// Heap statistics counters.
     257static unsigned long long int mmap_storage;
    333258static unsigned int mmap_calls;
    334259static unsigned long long int munmap_storage;
    … …  
    346271static unsigned long long int cmemalign_storage;
    347272static unsigned int cmemalign_calls;
     273static unsigned long long int resize_storage;
     274static unsigned int resize_calls;
    348275static unsigned long long int realloc_storage;
    349276static unsigned int realloc_calls;
    350 
    351 static int statfd;                                                                              // statistics file descriptor (changed by malloc_stats_fd)
    352 
     277// Statistics file descriptor (changed by malloc_stats_fd).
     278static int statfd = STDERR_FILENO;                                              // default stderr
    353279
    354280// Use "write" because streams may be shutdown when calls are made.
    355281static void printStats() {
    356282        char helpText[512];
    357         __cfaabi_dbg_bits_print_buffer( helpText, sizeof(helpText),
     283        __cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText),
    358284                                                                        "\nHeap statistics:\n"
    359285                                                                        "  malloc: calls %u / storage %llu\n"
    … …  
    361287                                                                        "  memalign: calls %u / storage %llu\n"
    362288                                                                        "  cmemalign: calls %u / storage %llu\n"
     289                                                                        "  resize: calls %u / storage %llu\n"
    363290                                                                        "  realloc: calls %u / storage %llu\n"
    364291                                                                        "  free: calls %u / storage %llu\n"
    … …  
    370297                                                                        memalign_calls, memalign_storage,
    371298                                                                        cmemalign_calls, cmemalign_storage,
     299                                                                        resize_calls, resize_storage,
    372300                                                                        realloc_calls, realloc_storage,
    373301                                                                        free_calls, free_storage,
    … …  
    389317                                                "<total type=\"memalign\" count=\"%u\" size=\"%llu\"/>\n"
    390318                                                "<total type=\"cmemalign\" count=\"%u\" size=\"%llu\"/>\n"
     319                                                "<total type=\"resize\" count=\"%u\" size=\"%llu\"/>\n"
    391320                                                "<total type=\"realloc\" count=\"%u\" size=\"%llu\"/>\n"
    392321                                                "<total type=\"free\" count=\"%u\" size=\"%llu\"/>\n"
    … …  
    399328                                                memalign_calls, memalign_storage,
    400329                                                cmemalign_calls, cmemalign_storage,
     330                                                resize_calls, resize_storage,
    401331                                                realloc_calls, realloc_storage,
    402332                                                free_calls, free_storage,
    … …  
    405335                                                sbrk_calls, sbrk_storage
    406336                );
    407         return write( fileno( stream ), helpText, len );        // -1 => error
     337        __cfaabi_bits_write( fileno( stream ), helpText, len ); // ensures all bytes written or exit
     338        return len;
    408339} // printStatsXML
    409340#endif // __STATISTICS__
    410341
    411 // #comment TD : Is this the samething as Out-of-Memory?
    412 static inline void noMemory() {
    413         abort( "Heap memory exhausted at %zu bytes.\n"
    414                    "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
    415                    ((char *)(sbrk( 0 )) - (char *)(heapManager.heapBegin)) );
    416 } // noMemory
    417 
    418 
    419 static inline void checkAlign( size_t alignment ) {
    420         if ( alignment < sizeof(void *) || ! libPow2( alignment ) ) {
    421                 abort( "Alignment %zu for memory allocation is less than sizeof(void *) and/or not a power of 2.", alignment );
    422         } // if
    423 } // checkAlign
     342
     343// static inline void noMemory() {
     344//      abort( "Heap memory exhausted at %zu bytes.\n"
     345//                 "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
     346//                 ((char *)(sbrk( 0 )) - (char *)(heapManager.heapBegin)) );
     347// } // noMemory
    424348
    425349
    … …  
    431355
    432356
    433 static inline void checkHeader( bool check, const char * name, void * addr ) {
    434         if ( unlikely( check ) ) {                                                      // bad address ?
    435                 abort( "Attempt to %s storage %p with address outside the heap.\n"
    436                            "Possible cause is duplicate free on same block or overwriting of memory.",
    437                            name, addr );
    438         } // if
    439 } // checkHeader
    440 
    441 // #comment TD : function should be commented and/or have a more evocative name
    442 //               this isn't either a check or a constructor which is what I would expect this function to be
    443 static inline void fakeHeader( HeapManager.Storage.Header *& header, size_t & size, size_t & alignment ) {
    444         if ( unlikely( (header->kind.fake.alignment & 1) == 1 ) ) { // fake header ?
    445                 size_t offset = header->kind.fake.offset;
    446                 alignment = header->kind.fake.alignment & -2;   // remove flag from value
    447                 #ifdef __CFA_DEBUG__
    448                 checkAlign( alignment );                                                // check alignment
    449                 #endif // __CFA_DEBUG__
    450                 header = (HeapManager.Storage.Header *)((char *)header - offset);
    451         } // if
    452 } // fakeHeader
    453 
    454 // #comment TD : Why is this a define
    455 #define headerAddr( addr ) ((HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) ))
    456 
    457 static inline bool headers( const char * name, void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem, size_t & size, size_t & alignment ) with ( heapManager ) {
    458         header = headerAddr( addr );
    459 
    460         if ( unlikely( heapEnd < addr ) ) {                                     // mmapped ?
    461                 fakeHeader( header, size, alignment );
    462                 size = header->kind.real.blockSize & -3;                // mmap size
    463                 return true;
    464         } // if
    465 
    466         #ifdef __CFA_DEBUG__
    467         checkHeader( addr < heapBegin || header < (HeapManager.Storage.Header *)heapBegin, name, addr ); // bad low address ?
    468         #endif // __CFA_DEBUG__
    469 
    470         // #comment TD : This code looks weird...
    471         //               It's called as the first statement of both branches of the last if, with the same parameters in all cases
    472 
    473         // header may be safe to dereference
    474         fakeHeader( header, size, alignment );
    475         #ifdef __CFA_DEBUG__
    476         checkHeader( header < (HeapManager.Storage.Header *)heapBegin || (HeapManager.Storage.Header *)heapEnd < header, name, addr ); // bad address ? (offset could be + or -)
    477         #endif // __CFA_DEBUG__
    478 
    479         freeElem = (HeapManager.FreeHeader *)((size_t)header->kind.real.home & -3);
    480         #ifdef __CFA_DEBUG__
    481         if ( freeElem < &freeLists[0] || &freeLists[NoBucketSizes] <= freeElem ) {
    482                 abort( "Attempt to %s storage %p with corrupted header.\n"
    483                            "Possible cause is duplicate free on same block or overwriting of header information.",
    484                            name, addr );
    485         } // if
    486         #endif // __CFA_DEBUG__
    487         size = freeElem->blockSize;
    488         return false;
    489 } // headers
    490 
    491 
    492 static inline void * extend( size_t size ) with ( heapManager ) {
    493         lock( extlock __cfaabi_dbg_ctx2 );
    494         ptrdiff_t rem = heapRemaining - size;
    495         if ( rem < 0 ) {
    496                 // If the size requested is bigger than the current remaining storage, increase the size of the heap.
    497 
    498                 size_t increase = libCeiling( size > heapExpand ? size : heapExpand, libAlign() );
    499                 if ( sbrk( increase ) == (void *)-1 ) {
    500                         unlock( extlock );
    501                         errno = ENOMEM;
    502                         return 0;
    503                 } // if
    504                 #ifdef __STATISTICS__
    505                 sbrk_calls += 1;
    506                 sbrk_storage += increase;
    507                 #endif // __STATISTICS__
    508                 #ifdef __CFA_DEBUG__
    509                 // Set new memory to garbage so subsequent uninitialized usages might fail.
    510                 memset( (char *)heapEnd + heapRemaining, '\377', increase );
    511                 #endif // __CFA_DEBUG__
    512                 rem = heapRemaining + increase - size;
    513         } // if
    514 
    515         HeapManager.Storage * block = (HeapManager.Storage *)heapEnd;
    516         heapRemaining = rem;
    517         heapEnd = (char *)heapEnd + size;
    518         unlock( extlock );
    519         return block;
    520 } // extend
    521 
    522 
     357// thunk problem
    523358size_t Bsearchl( unsigned int key, const unsigned int * vals, size_t dim ) {
    524359        size_t l = 0, m, h = dim;
    … …  
    535370
    536371
     372static inline bool setMmapStart( size_t value ) {               // true => mmapped, false => sbrk
     373  if ( value < pageSize || bucketSizes[NoBucketSizes - 1] < value ) return true;
     374        mmapStart = value;                                                                      // set global
     375
     376        // find the closest bucket size less than or equal to the mmapStart size
     377        maxBucketsUsed = Bsearchl( (unsigned int)mmapStart, bucketSizes, NoBucketSizes ); // binary search
     378        assert( maxBucketsUsed < NoBucketSizes );                       // subscript failure ?
     379        assert( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ?
     380        return false;
     381} // setMmapStart
     382
     383
     384// <-------+----------------------------------------------------> bsize (bucket size)
     385// |header |addr
     386//==================================================================================
     387//                   align/offset |
     388// <-----------------<------------+-----------------------------> bsize (bucket size)
     389//                   |fake-header | addr
     390#define headerAddr( addr ) ((HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) ))
     391#define realHeader( header ) ((HeapManager.Storage.Header *)((char *)header - header->kind.fake.offset))
     392
     393// <-------<<--------------------- dsize ---------------------->> bsize (bucket size)
     394// |header |addr
     395//==================================================================================
     396//                   align/offset |
     397// <------------------------------<<---------- dsize --------->>> bsize (bucket size)
     398//                   |fake-header |addr
     399#define dataStorage( bsize, addr, header ) (bsize - ( (char *)addr - (char *)header ))
     400
     401
     402static inline void checkAlign( size_t alignment ) {
     403        if ( alignment < libAlign() || ! libPow2( alignment ) ) {
     404                abort( "Alignment %zu for memory allocation is less than %d and/or not a power of 2.", alignment, libAlign() );
     405        } // if
     406} // checkAlign
     407
     408
     409static inline void checkHeader( bool check, const char name[], void * addr ) {
     410        if ( unlikely( check ) ) {                                                      // bad address ?
     411                abort( "Attempt to %s storage %p with address outside the heap.\n"
     412                           "Possible cause is duplicate free on same block or overwriting of memory.",
     413                           name, addr );
     414        } // if
     415} // checkHeader
     416
     417
     418static inline void fakeHeader( HeapManager.Storage.Header *& header, size_t & alignment ) {
     419        if ( unlikely( (header->kind.fake.alignment & 1) == 1 ) ) { // fake header ?
     420                alignment = header->kind.fake.alignment & -2;   // remove flag from value
     421                #ifdef __CFA_DEBUG__
     422                checkAlign( alignment );                                                // check alignment
     423                #endif // __CFA_DEBUG__
     424                header = realHeader( header );                                  // backup from fake to real header
     425        } // if
     426} // fakeHeader
     427
     428
     429static inline bool headers( const char name[] __attribute__(( unused )), void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem, size_t & size, size_t & alignment ) with ( heapManager ) {
     430        header = headerAddr( addr );
     431
     432        if ( unlikely( heapEnd < addr ) ) {                                     // mmapped ?
     433                fakeHeader( header, alignment );
     434                size = header->kind.real.blockSize & -3;                // mmap size
     435                return true;
     436        } // if
     437
     438        #ifdef __CFA_DEBUG__
     439        checkHeader( addr < heapBegin || header < (HeapManager.Storage.Header *)heapBegin, name, addr ); // bad low address ?
     440        #endif // __CFA_DEBUG__
     441
     442        // header may be safe to dereference
     443        fakeHeader( header, alignment );
     444        #ifdef __CFA_DEBUG__
     445        checkHeader( header < (HeapManager.Storage.Header *)heapBegin || (HeapManager.Storage.Header *)heapEnd < header, name, addr ); // bad address ? (offset could be + or -)
     446        #endif // __CFA_DEBUG__
     447
     448        freeElem = (HeapManager.FreeHeader *)((size_t)header->kind.real.home & -3);
     449        #ifdef __CFA_DEBUG__
     450        if ( freeElem < &freeLists[0] || &freeLists[NoBucketSizes] <= freeElem ) {
     451                abort( "Attempt to %s storage %p with corrupted header.\n"
     452                           "Possible cause is duplicate free on same block or overwriting of header information.",
     453                           name, addr );
     454        } // if
     455        #endif // __CFA_DEBUG__
     456        size = freeElem->blockSize;
     457        return false;
     458} // headers
     459
     460
     461static inline void * extend( size_t size ) with ( heapManager ) {
     462        lock( extlock __cfaabi_dbg_ctx2 );
     463        ptrdiff_t rem = heapRemaining - size;
     464        if ( rem < 0 ) {
     465                // If the size requested is bigger than the current remaining storage, increase the size of the heap.
     466
     467                size_t increase = libCeiling( size > heapExpand ? size : heapExpand, libAlign() );
     468                if ( sbrk( increase ) == (void *)-1 ) {
     469                        unlock( extlock );
     470                        errno = ENOMEM;
     471                        return 0p;
     472                } // if
     473                #ifdef __STATISTICS__
     474                sbrk_calls += 1;
     475                sbrk_storage += increase;
     476                #endif // __STATISTICS__
     477                #ifdef __CFA_DEBUG__
     478                // Set new memory to garbage so subsequent uninitialized usages might fail.
     479                memset( (char *)heapEnd + heapRemaining, '\377', increase );
     480                #endif // __CFA_DEBUG__
     481                rem = heapRemaining + increase - size;
     482        } // if
     483
     484        HeapManager.Storage * block = (HeapManager.Storage *)heapEnd;
     485        heapRemaining = rem;
     486        heapEnd = (char *)heapEnd + size;
     487        unlock( extlock );
     488        return block;
     489} // extend
     490
     491
    537492static inline void * doMalloc( size_t size ) with ( heapManager ) {
    538493        HeapManager.Storage * block;                                            // pointer to new block of storage
    … …  
    541496        // along with the block and is a multiple of the alignment size.
    542497
    543   if ( unlikely( size > ~0ul - sizeof(HeapManager.Storage) ) ) return 0;
     498  if ( unlikely( size > ~0ul - sizeof(HeapManager.Storage) ) ) return 0p;
    544499        size_t tsize = size + sizeof(HeapManager.Storage);
    545500        if ( likely( tsize < mmapStart ) ) {                            // small size => sbrk
    … …  
    574529                block = freeElem->freeList.pop();
    575530                #endif // SPINLOCK
    576                 if ( unlikely( block == 0 ) ) {                                 // no free block ?
     531                if ( unlikely( block == 0p ) ) {                                // no free block ?
    577532                        #if defined( SPINLOCK )
    578533                        unlock( freeElem->lock );
    … …  
    583538
    584539                        block = (HeapManager.Storage *)extend( tsize ); // mutual exclusion on call
    585   if ( unlikely( block == 0 ) ) return 0;
    586                         #if defined( SPINLOCK )
     540  if ( unlikely( block == 0p ) ) return 0p;
     541                #if defined( SPINLOCK )
    587542                } else {
    588543                        freeElem->freeList = block->header.kind.real.next;
    589544                        unlock( freeElem->lock );
    590                         #endif // SPINLOCK
     545                #endif // SPINLOCK
    591546                } // if
    592547
    593548                block->header.kind.real.home = freeElem;                // pointer back to free list of apropriate size
    594549        } else {                                                                                        // large size => mmap
    595   if ( unlikely( size > ~0ul - pageSize ) ) return 0;
     550  if ( unlikely( size > ~0ul - pageSize ) ) return 0p;
    596551                tsize = libCeiling( tsize, pageSize );                  // must be multiple of page size
    597552                #ifdef __STATISTICS__
    … …  
    611566        } // if
    612567
    613         void * area = &(block->data);                                           // adjust off header to user bytes
     568        void * addr = &(block->data);                                           // adjust off header to user bytes
    614569
    615570        #ifdef __CFA_DEBUG__
    616         assert( ((uintptr_t)area & (libAlign() - 1)) == 0 ); // minimum alignment ?
     571        assert( ((uintptr_t)addr & (libAlign() - 1)) == 0 ); // minimum alignment ?
    617572        __atomic_add_fetch( &allocFree, tsize, __ATOMIC_SEQ_CST );
    618573        if ( traceHeap() ) {
    619574                enum { BufferSize = 64 };
    620575                char helpText[BufferSize];
    621                 int len = snprintf( helpText, BufferSize, "%p = Malloc( %zu ) (allocated %zu)\n", area, size, tsize );
    622                 // int len = snprintf( helpText, BufferSize, "Malloc %p %zu\n", area, size );
    623                 __cfaabi_dbg_bits_write( helpText, len );
     576                int len = snprintf( helpText, BufferSize, "%p = Malloc( %zu ) (allocated %zu)\n", addr, size, tsize );
     577                // int len = snprintf( helpText, BufferSize, "Malloc %p %zu\n", addr, size );
     578                __cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug
    624579        } // if
    625580        #endif // __CFA_DEBUG__
    626581
    627         return area;
     582        return addr;
    628583} // doMalloc
    629584
    … …  
    631586static inline void doFree( void * addr ) with ( heapManager ) {
    632587        #ifdef __CFA_DEBUG__
    633         if ( unlikely( heapManager.heapBegin == 0 ) ) {
     588        if ( unlikely( heapManager.heapBegin == 0p ) ) {
    634589                abort( "doFree( %p ) : internal error, called before heap is initialized.", addr );
    635590        } // if
    … …  
    677632                char helpText[BufferSize];
    678633                int len = snprintf( helpText, sizeof(helpText), "Free( %p ) size:%zu\n", addr, size );
    679                 __cfaabi_dbg_bits_write( helpText, len );
     634                __cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug
    680635        } // if
    681636        #endif // __CFA_DEBUG__
    … …  
    683638
    684639
    685 size_t checkFree( HeapManager & manager ) with ( manager ) {
     640size_t prtFree( HeapManager & manager ) with ( manager ) {
    686641        size_t total = 0;
    687642        #ifdef __STATISTICS__
    688         __cfaabi_dbg_bits_acquire();
    689         __cfaabi_dbg_bits_print_nolock( "\nBin lists (bin size : free blocks on list)\n" );
     643        __cfaabi_bits_acquire();
     644        __cfaabi_bits_print_nolock( STDERR_FILENO, "\nBin lists (bin size : free blocks on list)\n" );
    690645        #endif // __STATISTICS__
    691646        for ( unsigned int i = 0; i < maxBucketsUsed; i += 1 ) {
    … …  
    696651
    697652                #if defined( SPINLOCK )
    698                 for ( HeapManager.Storage * p = freeLists[i].freeList; p != 0; p = p->header.kind.real.next ) {
     653                for ( HeapManager.Storage * p = freeLists[i].freeList; p != 0p; p = p->header.kind.real.next ) {
    699654                #else
    700                 for ( HeapManager.Storage * p = freeLists[i].freeList.top(); p != 0; p = p->header.kind.real.next.top ) {
     655                for ( HeapManager.Storage * p = freeLists[i].freeList.top(); p != 0p; p = p->header.kind.real.next.top ) {
    701656                #endif // SPINLOCK
    702657                        total += size;
    … …  
    707662
    708663                #ifdef __STATISTICS__
    709                 __cfaabi_dbg_bits_print_nolock( "%7zu, %-7u  ", size, N );
    710                 if ( (i + 1) % 8 == 0 ) __cfaabi_dbg_bits_print_nolock( "\n" );
     664                __cfaabi_bits_print_nolock( STDERR_FILENO, "%7zu, %-7u  ", size, N );
     665                if ( (i + 1) % 8 == 0 ) __cfaabi_bits_print_nolock( STDERR_FILENO, "\n" );
    711666                #endif // __STATISTICS__
    712667        } // for
    713668        #ifdef __STATISTICS__
    714         __cfaabi_dbg_bits_print_nolock( "\ntotal free blocks:%zu\n", total );
    715         __cfaabi_dbg_bits_release();
     669        __cfaabi_bits_print_nolock( STDERR_FILENO, "\ntotal free blocks:%zu\n", total );
     670        __cfaabi_bits_release();
    716671        #endif // __STATISTICS__
    717672        return (char *)heapEnd - (char *)heapBegin - total;
    718 } // checkFree
     673} // prtFree
     674
     675
     676static void ?{}( HeapManager & manager ) with ( manager ) {
     677        pageSize = sysconf( _SC_PAGESIZE );
     678
     679        for ( unsigned int i = 0; i < NoBucketSizes; i += 1 ) { // initialize the free lists
     680                freeLists[i].blockSize = bucketSizes[i];
     681        } // for
     682
     683        #ifdef FASTLOOKUP
     684        unsigned int idx = 0;
     685        for ( unsigned int i = 0; i < LookupSizes; i += 1 ) {
     686                if ( i > bucketSizes[idx] ) idx += 1;
     687                lookup[i] = idx;
     688        } // for
     689        #endif // FASTLOOKUP
     690
     691        if ( setMmapStart( default_mmap_start() ) ) {
     692                abort( "HeapManager : internal error, mmap start initialization failure." );
     693        } // if
     694        heapExpand = default_heap_expansion();
     695
     696        char * end = (char *)sbrk( 0 );
     697        sbrk( (char *)libCeiling( (long unsigned int)end, libAlign() ) - end ); // move start of heap to multiple of alignment
     698        heapBegin = heapEnd = sbrk( 0 );                                        // get new start point
     699} // HeapManager
     700
     701
     702static void ^?{}( HeapManager & ) {
     703        #ifdef __STATISTICS__
     704        if ( traceHeapTerm() ) {
     705                printStats();
     706                // if ( prtfree() ) prtFree( heapManager, true );
     707        } // if
     708        #endif // __STATISTICS__
     709} // ~HeapManager
     710
     711
     712static void memory_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_MEMORY ) ));
     713void memory_startup( void ) {
     714        #ifdef __CFA_DEBUG__
     715        if ( unlikely( heapBoot ) ) {                                           // check for recursion during system boot
     716                // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
     717                abort( "boot() : internal error, recursively invoked during system boot." );
     718        } // if
     719        heapBoot = true;
     720        #endif // __CFA_DEBUG__
     721
     722        //assert( heapManager.heapBegin != 0 );
     723        //heapManager{};
     724        if ( heapManager.heapBegin == 0p ) heapManager{};
     725} // memory_startup
     726
     727static void memory_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_MEMORY ) ));
     728void memory_shutdown( void ) {
     729        ^heapManager{};
     730} // memory_shutdown
    719731
    720732
    721733static inline void * mallocNoStats( size_t size ) {             // necessary for malloc statistics
    722734        //assert( heapManager.heapBegin != 0 );
    723         if ( unlikely( heapManager.heapBegin == 0 ) ) heapManager{}; // called before memory_startup ?
    724         void * area = doMalloc( size );
    725         if ( unlikely( area == 0 ) ) errno = ENOMEM;            // POSIX
    726         return area;
     735        if ( unlikely( heapManager.heapBegin == 0p ) ) heapManager{}; // called before memory_startup ?
     736        void * addr = doMalloc( size );
     737        if ( unlikely( addr == 0p ) ) errno = ENOMEM;           // POSIX
     738        return addr;
    727739} // mallocNoStats
     740
     741
     742static inline void * callocNoStats( size_t noOfElems, size_t elemSize ) {
     743        size_t size = noOfElems * elemSize;
     744        char * addr = (char *)mallocNoStats( size );
     745  if ( unlikely( addr == 0p ) ) return 0p;
     746
     747        HeapManager.Storage.Header * header;
     748        HeapManager.FreeHeader * freeElem;
     749        size_t bsize, alignment;
     750        bool mapped __attribute__(( unused )) = headers( "calloc", addr, header, freeElem, bsize, alignment );
     751        #ifndef __CFA_DEBUG__
     752        // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
     753        if ( ! mapped )
     754        #endif // __CFA_DEBUG__
     755                // Zero entire data space even when > than size => realloc without a new allocation and zero fill works.
     756                // <-------00000000000000000000000000000000000000000000000000000> bsize (bucket size)
     757                // `-header`-addr                      `-size
     758                memset( addr, '\0', bsize - sizeof(HeapManager.Storage) ); // set to zeros
     759
     760        assert( noOfElems <= UINT32_MAX );
     761        header->dimension = noOfElems;                                          // store number of array elements
     762        header->kind.real.blockSize |= 2;                                       // mark as zero filled
     763        return addr;
     764} // callocNoStats
    728765
    729766
    … …  
    745782        // subtract libAlign() because it is already the minimum alignment
    746783        // add sizeof(Storage) for fake header
    747         // #comment TD : this is the only place that calls doMalloc without calling mallocNoStats, why ?
    748         char * area = (char *)doMalloc( size + alignment - libAlign() + sizeof(HeapManager.Storage) );
    749   if ( unlikely( area == 0 ) ) return area;
     784        char * addr = (char *)mallocNoStats( size + alignment - libAlign() + sizeof(HeapManager.Storage) );
     785  if ( unlikely( addr == 0p ) ) return addr;
    750786
    751787        // address in the block of the "next" alignment address
    752         char * user = (char *)libCeiling( (uintptr_t)(area + sizeof(HeapManager.Storage)), alignment );
     788        char * user = (char *)libCeiling( (uintptr_t)(addr + sizeof(HeapManager.Storage)), alignment );
    753789
    754790        // address of header from malloc
    755         HeapManager.Storage.Header * realHeader = headerAddr( area );
     791        HeapManager.Storage.Header * realHeader = headerAddr( addr );
    756792        // address of fake header * before* the alignment location
    757793        HeapManager.Storage.Header * fakeHeader = headerAddr( user );
    … …  
    763799        return user;
    764800} // memalignNoStats
     801
     802
     803static inline void * cmemalignNoStats( size_t alignment, size_t noOfElems, size_t elemSize ) {
     804        size_t size = noOfElems * elemSize;
     805        char * addr = (char *)memalignNoStats( alignment, size );
     806  if ( unlikely( addr == 0p ) ) return 0p;
     807        HeapManager.Storage.Header * header;
     808        HeapManager.FreeHeader * freeElem;
     809        size_t bsize;
     810        bool mapped __attribute__(( unused )) = headers( "cmemalign", addr, header, freeElem, bsize, alignment );
     811        #ifndef __CFA_DEBUG__
     812        // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
     813        if ( ! mapped )
     814        #endif // __CFA_DEBUG__
     815                memset( addr, '\0', dataStorage( bsize, addr, header ) ); // set to zeros
     816
     817        assert( noOfElems <= UINT32_MAX );
     818        header->dimension = noOfElems;                                          // store initial array size
     819        header->kind.real.blockSize |= 2;                                       // mark as zero filled
     820        return addr;
     821} // cmemalignNoStats
    765822
    766823
    … …  
    775832
    776833extern "C" {
    777         // The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not
    778         // initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be
    779         // successfully passed to free().
     834        // Allocates size bytes and returns a pointer to the allocated memory. The memory is not initialized. If size is 0,
     835        // then malloc() returns either 0p, or a unique pointer value that can later be successfully passed to free().
    780836        void * malloc( size_t size ) {
    781837                #ifdef __STATISTICS__
    … …  
    787843        } // malloc
    788844
    789         // The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to
    790         // the allocated memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either NULL, or a
    791         // unique pointer value that can later be successfully passed to free().
     845        // Allocate memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated
     846        // memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either 0p, or a unique pointer
     847        // value that can later be successfully passed to free().
    792848        void * calloc( size_t noOfElems, size_t elemSize ) {
    793                 size_t size = noOfElems * elemSize;
    794849                #ifdef __STATISTICS__
    795850                __atomic_add_fetch( &calloc_calls, 1, __ATOMIC_SEQ_CST );
    796                 __atomic_add_fetch( &calloc_storage, size, __ATOMIC_SEQ_CST );
    797                 #endif // __STATISTICS__
    798 
    799                 char * area = (char *)mallocNoStats( size );
    800           if ( unlikely( area == 0 ) ) return 0;
     851                __atomic_add_fetch( &calloc_storage, noOfElems * elemSize, __ATOMIC_SEQ_CST );
     852                #endif // __STATISTICS__
     853
     854                return callocNoStats( noOfElems, elemSize );
     855        } // calloc
     856
     857        // Change the size of the memory block pointed to by ptr to size bytes. The contents are undefined.  If ptr is 0p,
     858        // then the call is equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not 0p,
     859        // then the call is equivalent to free(ptr). Unless ptr is 0p, it must have been returned by an earlier call to
     860        // malloc(), calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done.
     861
     862        void * resize( void * oaddr, size_t size ) {
     863                #ifdef __STATISTICS__
     864                __atomic_add_fetch( &resize_calls, 1, __ATOMIC_SEQ_CST );
     865                __atomic_add_fetch( &resize_storage, size, __ATOMIC_SEQ_CST );
     866                #endif // __STATISTICS__
     867
     868                // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
     869          if ( unlikely( size == 0 ) ) { free( oaddr ); return mallocNoStats( size ); } // special cases
     870          if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size );
    801871
    802872                HeapManager.Storage.Header * header;
    803873                HeapManager.FreeHeader * freeElem;
    804                 size_t asize, alignment;
    805                 bool mapped __attribute__(( unused )) = headers( "calloc", area, header, freeElem, asize, alignment );
    806                 #ifndef __CFA_DEBUG__
    807                 // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
    808                 if ( ! mapped )
    809                 #endif // __CFA_DEBUG__
    810                         memset( area, '\0', asize - sizeof(HeapManager.Storage) ); // set to zeros
    811 
    812                 header->kind.real.blockSize |= 2;                               // mark as zero filled
    813                 return area;
    814         } // calloc
    815 
    816         // #comment TD : Document this function
    817         void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ) {
    818                 size_t size = noOfElems * elemSize;
    819                 #ifdef __STATISTICS__
    820                 __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST );
    821                 __atomic_add_fetch( &cmemalign_storage, size, __ATOMIC_SEQ_CST );
    822                 #endif // __STATISTICS__
    823 
    824                 char * area = (char *)memalignNoStats( alignment, size );
    825           if ( unlikely( area == 0 ) ) return 0;
     874                size_t bsize, oalign = 0;
     875                headers( "resize", oaddr, header, freeElem, bsize, oalign );
     876                size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket
     877
     878                // same size, DO NOT preserve STICKY PROPERTIES.
     879                if ( oalign == 0 && size <= odsize && odsize <= size * 2 ) { // allow 50% wasted storage for smaller size
     880                        header->kind.real.blockSize &= -2;                      // no alignment and turn off 0 fill
     881                        return oaddr;
     882                } // if
     883       
     884                // change size, DO NOT preserve STICKY PROPERTIES.
     885                void * naddr = mallocNoStats( size );                   // create new area
     886                free( oaddr );
     887                return naddr;
     888        } // resize
     889
     890
     891        // Same as resize but the contents shall be unchanged in the range from the start of the region up to the minimum of
     892        // the old and new sizes.
     893        void * realloc( void * oaddr, size_t size ) {
     894                #ifdef __STATISTICS__
     895                __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
     896                __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
     897                #endif // __STATISTICS__
     898
     899                // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
     900          if ( unlikely( size == 0 ) ) { free( oaddr ); return mallocNoStats( size ); } // special cases
     901          if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size );
     902
    826903                HeapManager.Storage.Header * header;
    827904                HeapManager.FreeHeader * freeElem;
    828                 size_t asize;
    829                 bool mapped __attribute__(( unused )) = headers( "cmemalign", area, header, freeElem, asize, alignment );
    830                 #ifndef __CFA_DEBUG__
    831                 // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
    832                 if ( ! mapped )
    833                         #endif // __CFA_DEBUG__
    834                         memset( area, '\0', asize - ( (char *)area - (char *)header ) ); // set to zeros
    835                 header->kind.real.blockSize |= 2;                               // mark as zero filled
    836 
    837                 return area;
    838         } // cmemalign
    839 
    840         // The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be
    841         // unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size
    842         // is larger than the old size, the added memory will not be initialized.  If ptr is NULL, then the call is
    843         // equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call
    844         // is equivalent to free(ptr). Unless ptr is NULL, it must have been returned by an earlier call to malloc(),
    845         // calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done.
    846         void * realloc( void * addr, size_t size ) {
    847                 #ifdef __STATISTICS__
    848                 __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
    849                 #endif // __STATISTICS__
    850 
    851           if ( unlikely( addr == 0 ) ) return mallocNoStats( size ); // special cases
    852           if ( unlikely( size == 0 ) ) { free( addr ); return 0; }
    853 
    854                 HeapManager.Storage.Header * header;
    855                 HeapManager.FreeHeader * freeElem;
    856                 size_t asize, alignment = 0;
    857                 headers( "realloc", addr, header, freeElem, asize, alignment );
    858 
    859                 size_t usize = asize - ( (char *)addr - (char *)header ); // compute the amount of user storage in the block
    860                 if ( usize >= size ) {                                                  // already sufficient storage
    861                         // This case does not result in a new profiler entry because the previous one still exists and it must match with
    862                         // the free for this memory.  Hence, this realloc does not appear in the profiler output.
    863                         return addr;
    864                 } // if
    865 
    866                 #ifdef __STATISTICS__
    867                 __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
    868                 #endif // __STATISTICS__
    869 
    870                 void * area;
    871                 if ( unlikely( alignment != 0 ) ) {                             // previous request memalign?
    872                         area = memalign( alignment, size );                     // create new aligned area
     905                size_t bsize, oalign = 0;
     906                headers( "realloc", oaddr, header, freeElem, bsize, oalign );
     907
     908                size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket
     909          if ( size <= odsize && odsize <= size * 2 ) { // allow up to 50% wasted storage in smaller size
     910                        // Do not know size of original allocation => cannot do 0 fill for any additional space because do not know
     911                        // where to start filling, i.e., do not overwrite existing values in space.
     912                        return oaddr;
     913                } // if
     914
     915                // change size and copy old content to new storage
     916
     917                void * naddr;
     918                if ( unlikely( oalign != 0 ) ) {                                // previous request memalign?
     919                        if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill
     920                                naddr = cmemalignNoStats( oalign, 1, size ); // create new aligned area
     921                        } else {
     922                                naddr = memalignNoStats( oalign, size ); // create new aligned area
     923                        } // if
    873924                } else {
    874                         area = mallocNoStats( size );                           // create new area
    875                 } // if
    876           if ( unlikely( area == 0 ) ) return 0;
    877                 if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill (calloc/cmemalign) ?
    878                         assert( (header->kind.real.blockSize & 1) == 0 );
    879                         bool mapped __attribute__(( unused )) = headers( "realloc", area, header, freeElem, asize, alignment );
    880                         #ifndef __CFA_DEBUG__
    881                         // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
    882                         if ( ! mapped )
    883                         #endif // __CFA_DEBUG__
    884                                 memset( (char *)area + usize, '\0', asize - ( (char *)area - (char *)header ) - usize ); // zero-fill back part
    885                         header->kind.real.blockSize |= 2;                       // mark new request as zero fill
    886                 } // if
    887                 memcpy( area, addr, usize );                                    // copy bytes
    888                 free( addr );
    889                 return area;
     925                        if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill
     926                                naddr = callocNoStats( 1, size );               // create new area
     927                        } else {
     928                                naddr = mallocNoStats( size );                  // create new area
     929                        } // if
     930                } // if
     931          if ( unlikely( naddr == 0p ) ) return 0p;
     932
     933                headers( "realloc", naddr, header, freeElem, bsize, oalign );
     934                size_t ndsize = dataStorage( bsize, naddr, header ); // data storage avilable in bucket
     935                // To preserve prior fill, the entire bucket must be copied versus the size.
     936                memcpy( naddr, oaddr, MIN( odsize, ndsize ) );  // copy bytes
     937                free( oaddr );
     938                return naddr;
    890939        } // realloc
    891940
    892         // The obsolete function memalign() allocates size bytes and returns a pointer to the allocated memory. The memory
    893         // address will be a multiple of alignment, which must be a power of two.
     941        // Allocates size bytes and returns a pointer to the allocated memory. The memory address shall be a multiple of
     942        // alignment, which must be a power of two. (obsolete)
    894943        void * memalign( size_t alignment, size_t size ) {
    895944                #ifdef __STATISTICS__
    … …  
    898947                #endif // __STATISTICS__
    899948
    900                 void * area = memalignNoStats( alignment, size );
    901 
    902                 return area;
     949                return memalignNoStats( alignment, size );
    903950        } // memalign
    904951
    905         // The function aligned_alloc() is the same as memalign(), except for the added restriction that size should be a
    906         // multiple of alignment.
     952
     953        // Same as calloc() with memory alignment.
     954        void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ) {
     955                #ifdef __STATISTICS__
     956                __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST );
     957                __atomic_add_fetch( &cmemalign_storage, noOfElems * elemSize, __ATOMIC_SEQ_CST );
     958                #endif // __STATISTICS__
     959
     960                return cmemalignNoStats( alignment, noOfElems, elemSize );
     961        } // cmemalign
     962
     963        // Same as memalign(), but ISO/IEC 2011 C11 Section 7.22.2 states: the value of size shall be an integral multiple
     964    // of alignment. This requirement is universally ignored.
    907965        void * aligned_alloc( size_t alignment, size_t size ) {
    908966                return memalign( alignment, size );
    … …  
    910968
    911969
    912         // The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr. The
    913         // address of the allocated memory will be a multiple of alignment, which must be a power of two and a multiple of
    914         // sizeof(void *). If size is 0, then posix_memalign() returns either NULL, or a unique pointer value that can later
    915         // be successfully passed to free(3).
     970        // Allocates size bytes and places the address of the allocated memory in *memptr. The address of the allocated
     971        // memory shall be a multiple of alignment, which must be a power of two and a multiple of sizeof(void *). If size
     972        // is 0, then posix_memalign() returns either 0p, or a unique pointer value that can later be successfully passed to
     973        // free(3).
    916974        int posix_memalign( void ** memptr, size_t alignment, size_t size ) {
    917975          if ( alignment < sizeof(void *) || ! libPow2( alignment ) ) return EINVAL; // check alignment
    918976                * memptr = memalign( alignment, size );
    919           if ( unlikely( * memptr == 0 ) ) return ENOMEM;
     977          if ( unlikely( * memptr == 0p ) ) return ENOMEM;
    920978                return 0;
    921979        } // posix_memalign
    922980
    923         // The obsolete function valloc() allocates size bytes and returns a pointer to the allocated memory. The memory
    924         // address will be a multiple of the page size.  It is equivalent to memalign(sysconf(_SC_PAGESIZE),size).
     981        // Allocates size bytes and returns a pointer to the allocated memory. The memory address shall be a multiple of the
     982        // page size.  It is equivalent to memalign(sysconf(_SC_PAGESIZE),size).
    925983        void * valloc( size_t size ) {
    926984                return memalign( pageSize, size );
    … …  
    928986
    929987
    930         // The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to
    931         // malloc(), calloc() or realloc().  Otherwise, or if free(ptr) has already been called before, undefined behavior
    932         // occurs. If ptr is NULL, no operation is performed.
     988        // Same as valloc but rounds size to multiple of page size.
     989        void * pvalloc( size_t size ) {
     990                return memalign( pageSize, libCeiling( size, pageSize ) );
     991        } // pvalloc
     992
     993
     994        // Frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc()
     995        // or realloc().  Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. If ptr is
     996        // 0p, no operation is performed.
    933997        void free( void * addr ) {
    934998                #ifdef __STATISTICS__
    … …  
    9361000                #endif // __STATISTICS__
    9371001
    938                 // #comment TD : To decrease nesting I would but the special case in the
    939                 //               else instead, plus it reads more naturally to have the
    940                 //               short / normal case instead
    941                 if ( unlikely( addr == 0 ) ) {                                  // special case
    942                         #ifdef __CFA_DEBUG__
    943                         if ( traceHeap() ) {
    944                                 #define nullmsg "Free( 0x0 ) size:0\n"
    945                                 // Do not debug print free( 0 ), as it can cause recursive entry from sprintf.
    946                                 __cfaabi_dbg_bits_write( nullmsg, sizeof(nullmsg) - 1 );
    947                         } // if
    948                         #endif // __CFA_DEBUG__
     1002          if ( unlikely( addr == 0p ) ) {                                       // special case
     1003                        // #ifdef __CFA_DEBUG__
     1004                        // if ( traceHeap() ) {
     1005                        //      #define nullmsg "Free( 0x0 ) size:0\n"
     1006                        //      // Do not debug print free( 0p ), as it can cause recursive entry from sprintf.
     1007                        //      __cfaabi_dbg_write( nullmsg, sizeof(nullmsg) - 1 );
     1008                        // } // if
     1009                        // #endif // __CFA_DEBUG__
    9491010                        return;
    9501011                } // exit
    … …  
    9531014        } // free
    9541015
    955         // The mallopt() function adjusts parameters that control the behavior of the memory-allocation functions (see
    956         // malloc(3)). The param argument specifies the parameter to be modified, and value specifies the new value for that
    957         // parameter.
    958         int mallopt( int option, int value ) {
    959                 choose( option ) {
    960                   case M_TOP_PAD:
    961                         if ( setHeapExpand( value ) ) fallthru default;
    962                   case M_MMAP_THRESHOLD:
    963                         if ( setMmapStart( value ) ) fallthru default;
    964                   default:
    965                         // #comment TD : 1 for unsopported feels wrong
    966                         return 1;                                                                       // success, or unsupported
    967                 } // switch
    968                 return 0;                                                                               // error
    969         } // mallopt
    970 
    971         // The malloc_trim() function attempts to release free memory at the top of the heap (by calling sbrk(2) with a
    972         // suitable argument).
    973         int malloc_trim( size_t ) {
    974                 return 0;                                                                               // => impossible to release memory
    975         } // malloc_trim
    976 
    977         // The malloc_usable_size() function returns the number of usable bytes in the block pointed to by ptr, a pointer to
    978         // a block of memory allocated by malloc(3) or a related function.
    979         size_t malloc_usable_size( void * addr ) {
    980           if ( unlikely( addr == 0 ) ) return 0;                        // null allocation has 0 size
    981 
    982                 HeapManager.Storage.Header * header;
    983                 HeapManager.FreeHeader * freeElem;
    984                 size_t size, alignment;
    985 
    986                 headers( "malloc_usable_size", addr, header, freeElem, size, alignment );
    987                 size_t usize = size - ( (char *)addr - (char *)header ); // compute the amount of user storage in the block
    988                 return usize;
    989         } // malloc_usable_size
    990 
    991 
    992     // The malloc_alignment() function returns the alignment of the allocation.
     1016
     1017        // Returns the alignment of the allocation.
    9931018        size_t malloc_alignment( void * addr ) {
    994           if ( unlikely( addr == 0 ) ) return libAlign();       // minimum alignment
     1019          if ( unlikely( addr == 0p ) ) return libAlign();      // minimum alignment
    9951020                HeapManager.Storage.Header * header = headerAddr( addr );
    9961021                if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ?
    9971022                        return header->kind.fake.alignment & -2;        // remove flag from value
    9981023                } else {
    999                         return libAlign ();                                                     // minimum alignment
     1024                        return libAlign();                                                      // minimum alignment
    10001025                } // if
    10011026        } // malloc_alignment
    10021027
    10031028
    1004     // The malloc_zero_fill() function returns true if the allocation is zero filled, i.e., initially allocated by calloc().
     1029        // Returns true if the allocation is zero filled, i.e., initially allocated by calloc().
    10051030        bool malloc_zero_fill( void * addr ) {
    1006           if ( unlikely( addr == 0 ) ) return false;            // null allocation is not zero fill
     1031          if ( unlikely( addr == 0p ) ) return false;           // null allocation is not zero fill
    10071032                HeapManager.Storage.Header * header = headerAddr( addr );
    10081033                if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ?
    1009                         header = (HeapManager.Storage.Header *)((char *)header - header->kind.fake.offset);
     1034                        header = realHeader( header );                          // backup from fake to real header
    10101035                } // if
    10111036                return (header->kind.real.blockSize & 2) != 0;  // zero filled (calloc/cmemalign) ?
    … …  
    10131038
    10141039
    1015     // The malloc_stats() function prints (on default standard error) statistics about memory allocated by malloc(3) and
    1016     // related functions.
     1040        // Returns number of elements if the allocation is for an array, i.e., by calloc().
     1041        size_t malloc_dimension( void * addr ) {
     1042          if ( unlikely( addr == 0p ) ) return false;           // null allocation is not zero fill
     1043                HeapManager.Storage.Header * header = headerAddr( addr );
     1044                if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ?
     1045                        header = realHeader( header );                          // backup from fake to real header
     1046                } // if
     1047                return header->dimension;                                               // array (calloc/cmemalign)
     1048        } // malloc_zero_fill
     1049
     1050
     1051        // Returns the number of usable bytes in the block pointed to by ptr, a pointer to a block of memory allocated by
     1052        // malloc or a related function.
     1053        size_t malloc_usable_size( void * addr ) {
     1054          if ( unlikely( addr == 0p ) ) return 0;                       // null allocation has 0 size
     1055                HeapManager.Storage.Header * header;
     1056                HeapManager.FreeHeader * freeElem;
     1057                size_t bsize, alignment;
     1058
     1059                headers( "malloc_usable_size", addr, header, freeElem, bsize, alignment );
     1060                return dataStorage( bsize, addr, header );      // data storage in bucket
     1061        } // malloc_usable_size
     1062
     1063
     1064        // Prints (on default standard error) statistics about memory allocated by malloc and related functions.
    10171065        void malloc_stats( void ) {
    10181066                #ifdef __STATISTICS__
    10191067                printStats();
    1020                 if ( checkFree() ) checkFree( heapManager );
     1068                if ( prtFree() ) prtFree( heapManager );
    10211069                #endif // __STATISTICS__
    10221070        } // malloc_stats
    10231071
    1024         // The malloc_stats_fd() function changes the file descripter where malloc_stats() writes the statistics.
    1025         int malloc_stats_fd( int fd ) {
     1072        // Changes the file descripter where malloc_stats() writes statistics.
     1073        int malloc_stats_fd( int fd __attribute__(( unused )) ) {
    10261074                #ifdef __STATISTICS__
    10271075                int temp = statfd;
    … …  
    10331081        } // malloc_stats_fd
    10341082
    1035         // The malloc_info() function exports an XML string that describes the current state of the memory-allocation
    1036         // implementation in the caller.  The string is printed on the file stream stream.  The exported string includes
    1037         // information about all arenas (see malloc(3)).
     1083
     1084        // Adjusts parameters that control the behavior of the memory-allocation functions (see malloc). The param argument
     1085        // specifies the parameter to be modified, and value specifies the new value for that parameter.
     1086        int mallopt( int option, int value ) {
     1087                choose( option ) {
     1088                  case M_TOP_PAD:
     1089                        if ( setHeapExpand( value ) ) return 1;
     1090                  case M_MMAP_THRESHOLD:
     1091                        if ( setMmapStart( value ) ) return 1;
     1092                } // switch
     1093                return 0;                                                                               // error, unsupported
     1094        } // mallopt
     1095
     1096        // Attempt to release free memory at the top of the heap (by calling sbrk with a suitable argument).
     1097        int malloc_trim( size_t ) {
     1098                return 0;                                                                               // => impossible to release memory
     1099        } // malloc_trim
     1100
     1101
     1102        // Exports an XML string that describes the current state of the memory-allocation implementation in the caller.
     1103        // The string is printed on the file stream stream.  The exported string includes information about all arenas (see
     1104        // malloc).
    10381105        int malloc_info( int options, FILE * stream ) {
     1106                if ( options != 0 ) { errno = EINVAL; return -1; }
    10391107                return printStatsXML( stream );
    10401108        } // malloc_info
    10411109
    10421110
    1043         // The malloc_get_state() function records the current state of all malloc(3) internal bookkeeping variables (but
    1044         // not the actual contents of the heap or the state of malloc_hook(3) functions pointers).  The state is recorded in
    1045         // a system-dependent opaque data structure dynamically allocated via malloc(3), and a pointer to that data
    1046         // structure is returned as the function result.  (It is the caller's responsibility to free(3) this memory.)
     1111        // Records the current state of all malloc internal bookkeeping variables (but not the actual contents of the heap
     1112        // or the state of malloc_hook functions pointers).  The state is recorded in a system-dependent opaque data
     1113        // structure dynamically allocated via malloc, and a pointer to that data structure is returned as the function
     1114        // result.  (The caller must free this memory.)
    10471115        void * malloc_get_state( void ) {
    1048                 return 0;                                                                               // unsupported
     1116                return 0p;                                                                              // unsupported
    10491117        } // malloc_get_state
    10501118
    10511119
    1052         // The malloc_set_state() function restores the state of all malloc(3) internal bookkeeping variables to the values
    1053         // recorded in the opaque data structure pointed to by state.
     1120        // Restores the state of all malloc internal bookkeeping variables to the values recorded in the opaque data
     1121        // structure pointed to by state.
    10541122        int malloc_set_state( void * ptr ) {
    10551123                return 0;                                                                               // unsupported
    … …  
    10581126
    10591127
     1128// Must have CFA linkage to overload with C linkage realloc.
     1129void * resize( void * oaddr, size_t nalign, size_t size ) {
     1130        #ifdef __STATISTICS__
     1131        __atomic_add_fetch( &resize_calls, 1, __ATOMIC_SEQ_CST );
     1132        __atomic_add_fetch( &resize_storage, size, __ATOMIC_SEQ_CST );
     1133        #endif // __STATISTICS__
     1134
     1135        // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
     1136  if ( unlikely( size == 0 ) ) { free( oaddr ); return memalignNoStats( nalign, size ); } // special cases
     1137  if ( unlikely( oaddr == 0p ) ) return memalignNoStats( nalign, size );
     1138
     1139
     1140        if ( unlikely( nalign == 0 ) ) nalign = libAlign();     // reset alignment to minimum
     1141        #ifdef __CFA_DEBUG__
     1142        else
     1143                checkAlign( nalign );                                                   // check alignment
     1144        #endif // __CFA_DEBUG__
     1145
     1146        HeapManager.Storage.Header * header;
     1147        HeapManager.FreeHeader * freeElem;
     1148        size_t bsize, oalign = 0;
     1149        headers( "resize", oaddr, header, freeElem, bsize, oalign );
     1150        size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket
     1151
     1152        if ( oalign <= nalign && (uintptr_t)oaddr % nalign == 0 ) { // <= alignment and new alignment happens to match
     1153                if ( oalign >= libAlign() ) {                                   // fake header ?
     1154                        headerAddr( oaddr )->kind.fake.alignment = nalign | 1; // update alignment (could be the same)
     1155                } // if
     1156                if ( size <= odsize && odsize <= size * 2 ) {   // allow 50% wasted storage for smaller size
     1157                        header->kind.real.blockSize &= -2;                      // turn off 0 fill
     1158                        return oaddr;
     1159                } // if
     1160        } // if
     1161
     1162        // change size
     1163
     1164        void * naddr;
     1165        if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill
     1166                naddr = cmemalignNoStats( nalign, 1, size );    // create new aligned area
     1167        } else {
     1168                naddr = memalignNoStats( nalign, size );                // create new aligned area
     1169        } // if
     1170
     1171        free( oaddr );
     1172        return naddr;
     1173} // resize
     1174
     1175
     1176void * realloc( void * oaddr, size_t nalign, size_t size ) {
     1177        if ( unlikely( nalign == 0 ) ) nalign = libAlign();     // reset alignment to minimum
     1178        #ifdef __CFA_DEBUG__
     1179        else
     1180                checkAlign( nalign );                                                   // check alignment
     1181        #endif // __CFA_DEBUG__
     1182
     1183        HeapManager.Storage.Header * header;
     1184        HeapManager.FreeHeader * freeElem;
     1185        size_t bsize, oalign = 0;
     1186        headers( "realloc", oaddr, header, freeElem, bsize, oalign );
     1187        size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket
     1188
     1189        if ( oalign <= nalign && (uintptr_t)oaddr % nalign == 0 ) { // <= alignment and new alignment happens to match
     1190                if ( oalign >= libAlign() ) {                                   // fake header ?
     1191                        headerAddr( oaddr )->kind.fake.alignment = nalign | 1; // update alignment (could be the same)
     1192                } // if
     1193                return realloc( oaddr, size );
     1194        } // if
     1195
     1196        // change size and copy old content to new storage
     1197
     1198        #ifdef __STATISTICS__
     1199        __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
     1200        __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
     1201        #endif // __STATISTICS__
     1202
     1203        // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
     1204  if ( unlikely( size == 0 ) ) { free( oaddr ); return memalignNoStats( nalign, size ); } // special cases
     1205  if ( unlikely( oaddr == 0p ) ) return memalignNoStats( nalign, size );
     1206
     1207        void * naddr;
     1208        if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill
     1209                naddr = cmemalignNoStats( nalign, 1, size );    // create new aligned area
     1210        } else {
     1211                naddr = memalignNoStats( nalign, size );                // create new aligned area
     1212        } // if
     1213
     1214        headers( "realloc", naddr, header, freeElem, bsize, oalign );
     1215        size_t ndsize = dataStorage( bsize, naddr, header ); // data storage available in bucket
     1216        // To preserve prior fill, the entire bucket must be copied versus the size.
     1217        memcpy( naddr, oaddr, MIN( odsize, ndsize ) );          // copy bytes
     1218        free( oaddr );
     1219        return naddr;
     1220} // realloc
     1221
     1222
    10601223// Local Variables: //
    10611224// tab-width: 4 //
Note: See TracChangeset for help on using the changeset viewer.