Changeset 7a2057a
- Timestamp:
- Oct 30, 2022, 3:58:39 PM (2 years ago)
- Branches:
- ADT, ast-experimental, master
- Children:
- c7f12a4
- Parents:
- 0b1ca47
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/heap.cfa
r0b1ca47 r7a2057a 10 10 // Created On : Tue Dec 19 21:58:35 2017 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Oct 13 22:21:52202213 // Update Count : 15 5712 // Last Modified On : Sun Oct 30 15:33:13 2022 13 // Update Count : 1580 14 14 // 15 15 … … 43 43 44 44 #define FASTLOOKUP // use O(1) table lookup from allocation size to bucket size 45 #define RETURNSPIN // toggle spinlock / lockfree stack46 45 #define OWNERSHIP // return freed memory to owner thread 46 #define RETURNSPIN // toggle spinlock / lockfree queue 47 #if ! defined( OWNERSHIP ) && defined( RETURNSPIN ) 48 #warning "RETURNSPIN is ignored without OWNERSHIP; suggest commenting out RETURNSPIN" 49 #endif // ! OWNERSHIP && RETURNSPIN 47 50 48 51 #define CACHE_ALIGN 64 … … 109 112 110 113 111 //######################### Spin Lock ######################### 114 //######################### Helpers ######################### 115 116 117 // generic Bsearchl does not inline, so substitute with hand-coded binary-search. 118 inline __attribute__((always_inline)) 119 static size_t Bsearchl( unsigned int key, const unsigned int vals[], size_t dim ) { 120 size_t l = 0, m, h = dim; 121 while ( l < h ) { 122 m = (l + h) / 2; 123 if ( (unsigned int &)(vals[m]) < key ) { // cast away const 124 l = m + 1; 125 } else { 126 h = m; 127 } // if 128 } // while 129 return l; 130 } // Bsearchl 112 131 113 132 … … 206 225 207 226 208 #define SPINLOCK 0209 #define LOCKFREE 1210 #define BUCKETLOCK SPINLOCK211 #if BUCKETLOCK == SPINLOCK212 #elif BUCKETLOCK == LOCKFREE213 #include <containers/lockfree.hfa>214 #else215 #error undefined lock type for bucket lock216 #endif // LOCKFREE217 218 227 // Recursive definitions: HeapManager needs size of bucket array and bucket area needs sizeof HeapManager storage. 219 228 // Break recursion by hardcoding number of buckets and statically checking number is correct after bucket array defined. … … 232 241 void * home; // allocated block points back to home locations (must overlay alignment) 233 242 size_t blockSize; // size for munmap (must overlay alignment) 234 #if BUCKETLOCK == SPINLOCK235 243 Storage * next; // freed block points to next freed block of same size 236 #endif // SPINLOCK237 244 }; 238 245 size_t size; // allocation size in bytes 239 246 }; 240 #if BUCKETLOCK == LOCKFREE241 Link(Storage) next; // freed block points next freed block of same size (double-wide)242 #endif // LOCKFREE243 247 }; 244 248 } real; // RealHeader … … 259 263 struct __attribute__(( aligned (8) )) FreeHeader { 260 264 size_t blockSize __attribute__(( aligned(8) )); // size of allocations on this list 261 #if BUCKETLOCK == SPINLOCK262 265 #ifdef OWNERSHIP 263 266 #ifdef RETURNSPIN … … 266 269 Storage * returnList; // other thread return list 267 270 #endif // OWNERSHIP 271 268 272 Storage * freeList; // thread free list 269 #else270 StackLF(Storage) freeList;271 #endif // BUCKETLOCK272 273 Heap * homeManager; // heap owner (free storage to bucket, from bucket to heap) 273 274 }; // FreeHeader … … 290 291 #endif // __STATISTICS__ 291 292 }; // Heap 292 293 #if BUCKETLOCK == LOCKFREE294 inline __attribute__((always_inline))295 static {296 Link(Heap.Storage) * ?`next( Heap.Storage * this ) { return &this->header.kind.real.next; }297 void ?{}( Heap.FreeHeader & ) {}298 void ^?{}( Heap.FreeHeader & ) {}299 } // distribution300 #endif // LOCKFREE301 293 302 294 … … 385 377 386 378 387 // generic Bsearchl does not inline, so substitute with hand-coded binary-search.388 inline __attribute__((always_inline))389 static size_t Bsearchl( unsigned int key, const unsigned int vals[], size_t dim ) {390 size_t l = 0, m, h = dim;391 while ( l < h ) {392 m = (l + h) / 2;393 if ( (unsigned int &)(vals[m]) < key ) { // cast away const394 l = m + 1;395 } else {396 h = m;397 } // if398 } // while399 return l;400 } // Bsearchl401 402 403 379 void heapMasterCtor() with( heapMaster ) { 404 380 // Singleton pattern to initialize heap master … … 409 385 __map_prot = PROT_READ | PROT_WRITE | PROT_EXEC; 410 386 411 ?{}( extLock );412 ?{}( mgrLock );387 extLock = 0; 388 mgrLock = 0; 413 389 414 390 char * end = (char *)sbrk( 0 ); … … 497 473 #ifdef OWNERSHIP 498 474 #ifdef RETURNSPIN 499 ?{}( freeLists[j].returnLock ); 475 freeLists[j].returnLock = 0; 476 freeLists[j].returnList = 0p; 500 477 #endif // RETURNSPIN 501 freeLists[j].returnList = 0p;502 478 #endif // OWNERSHIP 479 503 480 freeLists[j].freeList = 0p; 504 481 freeLists[j].homeManager = heap; … … 710 687 // find the closest bucket size less than or equal to the mmapStart size 711 688 maxBucketsUsed = Bsearchl( mmapStart, bucketSizes, NoBucketSizes ); // binary search 689 712 690 verify( maxBucketsUsed < NoBucketSizes ); // subscript failure ? 713 691 verify( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ? … … 971 949 #endif // __STATISTICS__ 972 950 973 // Spin until the lock is acquired for this particular size of block.974 975 #if BUCKETLOCK == SPINLOCK976 951 block = freeHead->freeList; // remove node from stack 977 #else978 block = pop( freeHead->freeList );979 #endif // BUCKETLOCK980 952 if ( unlikely( block == 0p ) ) { // no free block ? 953 // Freelist for this size is empty, so check return list (OWNERSHIP), carve it out of the heap, if there 954 // is enough left, or get some more heap storage and carve it off. 981 955 #ifdef OWNERSHIP 982 // Freelist for that size is empty, so carve it out of the heap, if there is enough left, or get some more 983 // and then carve it off. 984 #ifdef RETURNSPIN 985 #if BUCKETLOCK == SPINLOCK 986 lock( freeHead->returnLock ); 987 block = freeHead->returnList; 988 freeHead->returnList = 0p; 989 unlock( freeHead->returnLock ); 990 #else 991 block = __atomic_exchange_n( &freeHead->returnList, nullptr, __ATOMIC_SEQ_CST ); 992 #endif // RETURNSPIN 993 994 if ( likely( block == 0p ) ) { // return list also empty? 956 if ( unlikely( freeHead->returnList ) ) { // race, get next time if lose race 957 #ifdef RETURNSPIN 958 lock( freeHead->returnLock ); 959 block = freeHead->returnList; 960 freeHead->returnList = 0p; 961 unlock( freeHead->returnLock ); 962 #else 963 block = __atomic_exchange_n( &freeHead->returnList, 0p, __ATOMIC_SEQ_CST ); 964 #endif // RETURNSPIN 965 966 verify( block ); 967 #ifdef __STATISTICS__ 968 stats.return_pulls += 1; 969 #endif // __STATISTICS__ 970 971 // OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED. 972 973 freeHead->freeList = block->header.kind.real.next; // merge returnList into freeHead 974 } else { 995 975 #endif // OWNERSHIP 996 976 // Do not leave kernel thread as manager_extend accesses heapManager. … … 1002 982 1003 983 #ifdef __CFA_DEBUG__ 1004 // Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first 1024bytes.984 // Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first SCRUB_SIZE bytes. 1005 985 memset( block->data, SCRUB, min( SCRUB_SIZE, tsize - sizeof(Heap.Storage) ) ); 1006 986 #endif // __CFA_DEBUG__ 1007 #endif // BUCKETLOCK1008 987 #ifdef OWNERSHIP 1009 } else { // merge returnList into freeHead1010 #ifdef __STATISTICS__1011 stats.return_pulls += 1;1012 #endif // __STATISTICS__1013 1014 // OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.1015 1016 freeHead->freeList = block->header.kind.real.next;1017 988 } // if 1018 989 #endif // OWNERSHIP … … 1026 997 if ( unlikely( size > ULONG_MAX - __page_size ) ) return 0p; 1027 998 tsize = ceiling2( tsize, __page_size ); // must be multiple of page size 999 1028 1000 #ifdef __STATISTICS__ 1029 1001 stats.counters[STAT_NAME].alloc += tsize; … … 1042 1014 if ( errno == ENOMEM ) abort( NO_MEMORY_MSG, tsize ); // no memory 1043 1015 // Do not call strerror( errno ) as it may call malloc. 1044 abort( "**** Error **** attempt to allocate large object (> %zu) of size %zu bytes and mmap failed with errno %d.", size, heapMaster.mmapStart, errno ); 1016 abort( "**** Error **** attempt to allocate large object (> %zu) of size %zu bytes and mmap failed with errno %d.", 1017 size, heapMaster.mmapStart, errno ); 1045 1018 } // if 1046 1019 block->header.kind.real.blockSize = MarkMmappedBit( tsize ); // storage size for munmap 1047 1020 1048 1021 #ifdef __CFA_DEBUG__ 1049 // Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first 1024 bytes. The rest of1050 // the storage set to 0 by mmap.1022 // Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first SCRUB_SIZE bytes. The 1023 // rest of the storage set to 0 by mmap. 1051 1024 memset( block->data, SCRUB, min( SCRUB_SIZE, tsize - sizeof(Heap.Storage) ) ); 1052 1025 #endif // __CFA_DEBUG__ … … 1126 1099 #endif // __CFA_DEBUG__ 1127 1100 1101 #ifdef OWNERSHIP 1128 1102 if ( likely( heapManager == freeHead->homeManager ) ) { // belongs to this thread 1129 1103 header->kind.real.next = freeHead->freeList; // push on stack … … 1132 1106 verify( heapManager ); 1133 1107 1134 #ifdef OWNERSHIP1135 1108 #ifdef RETURNSPIN 1136 1109 lock( freeHead->returnLock ); … … 1141 1114 header->kind.real.next = freeHead->returnList; // link new node to top node 1142 1115 // CAS resets header->kind.real.next = freeHead->returnList on failure 1143 while ( ! __atomic_compare_exchange_n( &freeHead->returnList, &header->kind.real.next, header,1116 while ( ! __atomic_compare_exchange_n( &freeHead->returnList, &header->kind.real.next, (Heap.Storage *)header, 1144 1117 false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ); 1145 1118 #endif // RETURNSPIN 1146 1147 #else // no OWNERSHIP 1148 1149 freeHead = &heap->freeLists[ClearStickyBits( header->kind.real.home ) - &freeHead->homeManager->freeLists[0]]; 1150 header->kind.real.next = freeHead->freeList; // push on stack 1151 freeHead->freeList = (Heap.Storage *)header; 1152 #endif // ! OWNERSHIP 1153 1154 #ifdef __U_STATISTICS__ 1155 stats.return_pushes += 1; 1156 stats.return_storage_request += rsize; 1157 stats.return_storage_alloc += size; 1158 #endif // __U_STATISTICS__ 1159 1160 // OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED. 1161 } // if 1119 } // if 1120 1121 #else // no OWNERSHIP 1122 1123 // kind.real.home is address in owner thread's freeLists, so compute the equivalent position in this thread's freeList. 1124 freeHead = &freeLists[ClearStickyBits( (Heap.FreeHeader *)(header->kind.real.home) ) - &freeHead->homeManager->freeLists[0]]; 1125 header->kind.real.next = freeHead->freeList; // push on stack 1126 freeHead->freeList = (Heap.Storage *)header; 1127 #endif // ! OWNERSHIP 1128 1129 #ifdef __U_STATISTICS__ 1130 stats.return_pushes += 1; 1131 stats.return_storage_request += rsize; 1132 stats.return_storage_alloc += size; 1133 #endif // __U_STATISTICS__ 1134 1135 // OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED. 1162 1136 } // if 1163 1137 … … 1186 1160 #endif // __STATISTICS__ 1187 1161 1188 #if BUCKETLOCK == SPINLOCK1189 1162 for ( Heap.Storage * p = freeLists[i].freeList; p != 0p; p = p->header.kind.real.next ) { 1190 #else1191 for(;;) {1192 // for ( Heap.Storage * p = top( freeLists[i].freeList ); p != 0p; p = (p)`next->top ) {1193 // for ( Heap.Storage * p = top( freeLists[i].freeList ); p != 0p; /* p = getNext( p )->top */) {1194 // Heap.Storage * temp = p->header.kind.real.next.top; // FIX ME: direct assignent fails, initialization works`1195 // typeof(p) temp = (( p )`next)->top; // FIX ME: direct assignent fails, initialization works`1196 // p = temp;1197 #endif // BUCKETLOCK1198 1163 total += size; 1199 1164 #ifdef __STATISTICS__
Note: See TracChangeset
for help on using the changeset viewer.