Ignore:
Timestamp:
Apr 1, 2020, 9:32:21 PM (19 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast, new-ast-unique-expr
Children:
6d43cdde
Parents:
5137f9f
Message:

add resize and more "alloc" routines

File:
1 edited

Legend:

Unmodified
Added
Removed
  • libcfa/src/heap.cfa

    r5137f9f rcfbc703  
    1010// Created On       : Tue Dec 19 21:58:35 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Mar  6 10:14:52 2020
    13 // Update Count     : 650
     12// Last Modified On : Wed Apr  1 15:59:53 2020
     13// Update Count     : 692
    1414//
    1515
     
    150150                                                        union {
    151151//                                                              FreeHeader * home;              // allocated block points back to home locations (must overlay alignment)
     152                                                                // 2nd low-order bit => zero filled
    152153                                                                void * home;                    // allocated block points back to home locations (must overlay alignment)
    153154                                                                size_t blockSize;               // size for munmap (must overlay alignment)
     
    169170                                struct FakeHeader {
    170171                                        #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
    171                                         uint32_t alignment;                                     // low-order bits of home/blockSize used for tricks
     172                                        // 1st low-order bit => fake header & alignment
     173                                        uint32_t alignment;
    172174                                        #endif // __ORDER_LITTLE_ENDIAN__
    173175
     
    179181                                } fake; // FakeHeader
    180182                        } kind; // Kind
     183                        uint32_t dimension;                                                     // used by calloc-like to remember number of array elements
    181184                } header; // Header
    182185                char pad[libAlign() - sizeof( Header )];
     
    268271static unsigned long long int cmemalign_storage;
    269272static unsigned int cmemalign_calls;
     273static unsigned long long int resize_storage;
     274static unsigned int resize_calls;
    270275static unsigned long long int realloc_storage;
    271276static unsigned int realloc_calls;
     
    282287                                                                        "  memalign: calls %u / storage %llu\n"
    283288                                                                        "  cmemalign: calls %u / storage %llu\n"
     289                                                                        "  resize: calls %u / storage %llu\n"
    284290                                                                        "  realloc: calls %u / storage %llu\n"
    285291                                                                        "  free: calls %u / storage %llu\n"
     
    291297                                                                        memalign_calls, memalign_storage,
    292298                                                                        cmemalign_calls, cmemalign_storage,
     299                                                                        resize_calls, resize_storage,
    293300                                                                        realloc_calls, realloc_storage,
    294301                                                                        free_calls, free_storage,
     
    310317                                                "<total type=\"memalign\" count=\"%u\" size=\"%llu\"/>\n"
    311318                                                "<total type=\"cmemalign\" count=\"%u\" size=\"%llu\"/>\n"
     319                                                "<total type=\"resize\" count=\"%u\" size=\"%llu\"/>\n"
    312320                                                "<total type=\"realloc\" count=\"%u\" size=\"%llu\"/>\n"
    313321                                                "<total type=\"free\" count=\"%u\" size=\"%llu\"/>\n"
     
    320328                                                memalign_calls, memalign_storage,
    321329                                                cmemalign_calls, cmemalign_storage,
     330                                                resize_calls, resize_storage,
    322331                                                realloc_calls, realloc_storage,
    323332                                                free_calls, free_storage,
     
    339348
    340349
    341 static inline void checkAlign( size_t alignment ) {
    342         if ( alignment < libAlign() || ! libPow2( alignment ) ) {
    343                 abort( "Alignment %zu for memory allocation is less than %d and/or not a power of 2.", alignment, libAlign() );
    344         } // if
    345 } // checkAlign
    346 
    347 
    348350static inline bool setHeapExpand( size_t value ) {
    349351  if ( heapExpand < pageSize ) return true;
     
    380382
    381383
     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
    382409static inline void checkHeader( bool check, const char name[], void * addr ) {
    383410        if ( unlikely( check ) ) {                                                      // bad address ?
     
    391418static inline void fakeHeader( HeapManager.Storage.Header *& header, size_t & alignment ) {
    392419        if ( unlikely( (header->kind.fake.alignment & 1) == 1 ) ) { // fake header ?
    393                 size_t offset = header->kind.fake.offset;
    394420                alignment = header->kind.fake.alignment & -2;   // remove flag from value
    395421                #ifdef __CFA_DEBUG__
    396422                checkAlign( alignment );                                                // check alignment
    397423                #endif // __CFA_DEBUG__
    398                 header = (HeapManager.Storage.Header *)((char *)header - offset);
     424                header = realHeader( header );                                  // backup from fake to real header
    399425        } // if
    400426} // fakeHeader
    401 
    402 
    403 // <-------+----------------------------------------------------> bsize (bucket size)
    404 // |header |addr
    405 //==================================================================================
    406 //                                | alignment
    407 // <-----------------<------------+-----------------------------> bsize (bucket size)
    408 //                   |fake-header | addr
    409 #define headerAddr( addr ) ((HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) ))
    410 
    411 // <-------<<--------------------- dsize ---------------------->> bsize (bucket size)
    412 // |header |addr
    413 //==================================================================================
    414 //                                | alignment
    415 // <------------------------------<<---------- dsize --------->>> bsize (bucket size)
    416 //                   |fake-header |addr
    417 #define dataStorage( bsize, addr, header ) (bsize - ( (char *)addr - (char *)header ))
    418427
    419428
     
    749758                memset( addr, '\0', bsize - sizeof(HeapManager.Storage) ); // set to zeros
    750759
     760        assert( noOfElems <= UINT32_MAX );
     761        header->dimension = noOfElems;                                          // store number of array elements
    751762        header->kind.real.blockSize |= 2;                                       // mark as zero filled
    752763        return addr;
     
    803814        #endif // __CFA_DEBUG__
    804815                memset( addr, '\0', dataStorage( bsize, addr, header ) ); // set to zeros
    805         header->kind.real.blockSize |= 2;                               // mark as zero filled
    806 
     816
     817        assert( noOfElems <= UINT32_MAX );
     818        header->dimension = noOfElems;                                          // store initial array size
     819        header->kind.real.blockSize |= 2;                                       // mark as zero filled
    807820        return addr;
    808821} // cmemalignNoStats
     
    842855        } // calloc
    843856
    844         // Change the size of the memory block pointed to by ptr to size bytes. The contents shall be unchanged in the range
    845         // from the start of the region up to the minimum of the old and new sizes. If the new size is larger than the old
    846         // size, the added memory shall not be initialized.  If ptr is 0p, then the call is equivalent to malloc(size), for
    847         // all values of size; if size is equal to zero, and ptr is not 0p, then the call is equivalent to free(ptr). Unless
    848         // ptr is 0p, it must have been returned by an earlier call to malloc(), calloc() or realloc(). If the area pointed
    849         // to was moved, a free(ptr) is done.
     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 );
     871
     872                HeapManager.Storage.Header * header;
     873                HeapManager.FreeHeader * freeElem;
     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.
    850893        void * realloc( void * oaddr, size_t size ) {
    851894                #ifdef __STATISTICS__
    852895                __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
     896                __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
    853897                #endif // __STATISTICS__
    854898
     
    866910                        // Do not know size of original allocation => cannot do 0 fill for any additional space because do not know
    867911                        // where to start filling, i.e., do not overwrite existing values in space.
    868                         //
    869                         // This case does not result in a new profiler entry because the previous one still exists and it must match with
    870                         // the free for this memory.  Hence, this realloc does not appear in the profiler output.
    871912                        return oaddr;
    872913                } // if
    873 
    874                 #ifdef __STATISTICS__
    875                 __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
    876                 #endif // __STATISTICS__
    877914
    878915                // change size and copy old content to new storage
     
    9851022                        return header->kind.fake.alignment & -2;        // remove flag from value
    9861023                } else {
    987                         return libAlign ();                                                     // minimum alignment
     1024                        return libAlign();                                                      // minimum alignment
    9881025                } // if
    9891026        } // malloc_alignment
     
    9951032                HeapManager.Storage.Header * header = headerAddr( addr );
    9961033                if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ?
    997                         header = (HeapManager.Storage.Header *)((char *)header - header->kind.fake.offset);
     1034                        header = realHeader( header );                          // backup from fake to real header
    9981035                } // if
    9991036                return (header->kind.real.blockSize & 2) != 0;  // zero filled (calloc/cmemalign) ?
     1037        } // malloc_zero_fill
     1038
     1039
     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)
    10001048        } // malloc_zero_fill
    10011049
     
    10791127
    10801128// Must have CFA linkage to overload with C linkage realloc.
    1081 void * realloc( void * oaddr, size_t nalign, size_t size ) {
     1129void * resize( void * oaddr, size_t nalign, size_t size ) {
    10821130        #ifdef __STATISTICS__
    1083         __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
     1131        __atomic_add_fetch( &resize_calls, 1, __ATOMIC_SEQ_CST );
     1132        __atomic_add_fetch( &resize_storage, size, __ATOMIC_SEQ_CST );
    10841133        #endif // __STATISTICS__
    10851134
    10861135        // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
    1087   if ( unlikely( size == 0 ) ) { free( oaddr ); return mallocNoStats( size ); } // special cases
    1088   if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size );
     1136  if ( unlikely( size == 0 ) ) { free( oaddr ); return memalignNoStats( nalign, size ); } // special cases
     1137  if ( unlikely( oaddr == 0p ) ) return memalignNoStats( nalign, size );
     1138
    10891139
    10901140        if ( unlikely( nalign == 0 ) ) nalign = libAlign();     // reset alignment to minimum
     
    10971147        HeapManager.FreeHeader * freeElem;
    10981148        size_t bsize, oalign = 0;
    1099         headers( "realloc", oaddr, header, freeElem, bsize, oalign );
     1149        headers( "resize", oaddr, header, freeElem, bsize, oalign );
    11001150        size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket
    11011151
    1102   if ( oalign != 0 && (uintptr_t)oaddr % nalign == 0 ) { // has alignment and just happens to work out
    1103                 headerAddr( oaddr )->kind.fake.alignment = nalign | 1; // update alignment (could be the same)
    1104                 return realloc( oaddr, size );
    1105         } // if
    1106 
    1107         #ifdef __STATISTICS__
    1108         __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST );
    1109         #endif // __STATISTICS__
    1110 
    1111         // change size and copy old content to new storage
     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
    11121163
    11131164        void * naddr;
     
    11181169        } // if
    11191170
     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
    11201214        headers( "realloc", naddr, header, freeElem, bsize, oalign );
    1121         size_t ndsize = dataStorage( bsize, naddr, header ); // data storage avilable in bucket
     1215        size_t ndsize = dataStorage( bsize, naddr, header ); // data storage available in bucket
    11221216        // To preserve prior fill, the entire bucket must be copied versus the size.
    11231217        memcpy( naddr, oaddr, MIN( odsize, ndsize ) );          // copy bytes
Note: See TracChangeset for help on using the changeset viewer.