1 //===-- local_cache.h -------------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef SCUDO_LOCAL_CACHE_H_ 10 #define SCUDO_LOCAL_CACHE_H_ 11 12 #include "internal_defs.h" 13 #include "report.h" 14 #include "stats.h" 15 16 namespace scudo { 17 18 template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache { 19 typedef typename SizeClassAllocator::SizeClassMap SizeClassMap; 20 typedef typename SizeClassAllocator::CompactPtrT CompactPtrT; 21 22 struct TransferBatch { 23 static const u32 MaxNumCached = SizeClassMap::MaxNumCachedHint; setFromArraySizeClassAllocatorLocalCache::TransferBatch24 void setFromArray(CompactPtrT *Array, u32 N) { 25 DCHECK_LE(N, MaxNumCached); 26 Count = N; 27 memcpy(Batch, Array, sizeof(Batch[0]) * Count); 28 } clearSizeClassAllocatorLocalCache::TransferBatch29 void clear() { Count = 0; } addSizeClassAllocatorLocalCache::TransferBatch30 void add(CompactPtrT P) { 31 DCHECK_LT(Count, MaxNumCached); 32 Batch[Count++] = P; 33 } copyToArraySizeClassAllocatorLocalCache::TransferBatch34 void copyToArray(CompactPtrT *Array) const { 35 memcpy(Array, Batch, sizeof(Batch[0]) * Count); 36 } getCountSizeClassAllocatorLocalCache::TransferBatch37 u32 getCount() const { return Count; } getSizeClassAllocatorLocalCache::TransferBatch38 CompactPtrT get(u32 I) const { 39 DCHECK_LE(I, Count); 40 return Batch[I]; 41 } getMaxCachedSizeClassAllocatorLocalCache::TransferBatch42 static u32 getMaxCached(uptr Size) { 43 return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size)); 44 } 45 TransferBatch *Next; 46 47 private: 48 u32 Count; 49 CompactPtrT Batch[MaxNumCached]; 50 }; 51 initLinkerInitializedSizeClassAllocatorLocalCache52 void initLinkerInitialized(GlobalStats *S, SizeClassAllocator *A) { 53 Stats.initLinkerInitialized(); 54 if (LIKELY(S)) 55 S->link(&Stats); 56 Allocator = A; 57 } 58 initSizeClassAllocatorLocalCache59 void init(GlobalStats *S, SizeClassAllocator *A) { 60 memset(this, 0, sizeof(*this)); 61 initLinkerInitialized(S, A); 62 } 63 destroySizeClassAllocatorLocalCache64 void destroy(GlobalStats *S) { 65 drain(); 66 if (LIKELY(S)) 67 S->unlink(&Stats); 68 } 69 allocateSizeClassAllocatorLocalCache70 void *allocate(uptr ClassId) { 71 DCHECK_LT(ClassId, NumClasses); 72 PerClass *C = &PerClassArray[ClassId]; 73 if (C->Count == 0) { 74 if (UNLIKELY(!refill(C, ClassId))) 75 return nullptr; 76 DCHECK_GT(C->Count, 0); 77 } 78 // We read ClassSize first before accessing Chunks because it's adjacent to 79 // Count, while Chunks might be further off (depending on Count). That keeps 80 // the memory accesses in close quarters. 81 const uptr ClassSize = C->ClassSize; 82 CompactPtrT CompactP = C->Chunks[--C->Count]; 83 Stats.add(StatAllocated, ClassSize); 84 Stats.sub(StatFree, ClassSize); 85 return Allocator->decompactPtr(ClassId, CompactP); 86 } 87 deallocateSizeClassAllocatorLocalCache88 void deallocate(uptr ClassId, void *P) { 89 CHECK_LT(ClassId, NumClasses); 90 PerClass *C = &PerClassArray[ClassId]; 91 // We still have to initialize the cache in the event that the first heap 92 // operation in a thread is a deallocation. 93 initCacheMaybe(C); 94 if (C->Count == C->MaxCount) 95 drain(C, ClassId); 96 // See comment in allocate() about memory accesses. 97 const uptr ClassSize = C->ClassSize; 98 C->Chunks[C->Count++] = 99 Allocator->compactPtr(ClassId, reinterpret_cast<uptr>(P)); 100 Stats.sub(StatAllocated, ClassSize); 101 Stats.add(StatFree, ClassSize); 102 } 103 isEmptySizeClassAllocatorLocalCache104 bool isEmpty() const { 105 for (uptr I = 0; I < NumClasses; ++I) 106 if (PerClassArray[I].Count) 107 return false; 108 return true; 109 } 110 drainSizeClassAllocatorLocalCache111 void drain() { 112 // Drain BatchClassId last as createBatch can refill it. 113 for (uptr I = 0; I < NumClasses; ++I) { 114 if (I == BatchClassId) 115 continue; 116 while (PerClassArray[I].Count > 0) 117 drain(&PerClassArray[I], I); 118 } 119 while (PerClassArray[BatchClassId].Count > 0) 120 drain(&PerClassArray[BatchClassId], BatchClassId); 121 DCHECK(isEmpty()); 122 } 123 createBatchSizeClassAllocatorLocalCache124 TransferBatch *createBatch(uptr ClassId, void *B) { 125 if (ClassId != BatchClassId) 126 B = allocate(BatchClassId); 127 return reinterpret_cast<TransferBatch *>(B); 128 } 129 getStatsSizeClassAllocatorLocalCache130 LocalStats &getStats() { return Stats; } 131 132 private: 133 static const uptr NumClasses = SizeClassMap::NumClasses; 134 static const uptr BatchClassId = SizeClassMap::BatchClassId; 135 struct PerClass { 136 u32 Count; 137 u32 MaxCount; 138 // Note: ClassSize is zero for the transfer batch. 139 uptr ClassSize; 140 CompactPtrT Chunks[2 * TransferBatch::MaxNumCached]; 141 }; 142 PerClass PerClassArray[NumClasses] = {}; 143 LocalStats Stats; 144 SizeClassAllocator *Allocator = nullptr; 145 initCacheMaybeSizeClassAllocatorLocalCache146 ALWAYS_INLINE void initCacheMaybe(PerClass *C) { 147 if (LIKELY(C->MaxCount)) 148 return; 149 initCache(); 150 DCHECK_NE(C->MaxCount, 0U); 151 } 152 initCacheSizeClassAllocatorLocalCache153 NOINLINE void initCache() { 154 for (uptr I = 0; I < NumClasses; I++) { 155 PerClass *P = &PerClassArray[I]; 156 const uptr Size = SizeClassAllocator::getSizeByClassId(I); 157 P->MaxCount = 2 * TransferBatch::getMaxCached(Size); 158 if (I != BatchClassId) { 159 P->ClassSize = Size; 160 } else { 161 // ClassSize in this struct is only used for malloc/free stats, which 162 // should only track user allocations, not internal movements. 163 P->ClassSize = 0; 164 } 165 } 166 } 167 destroyBatchSizeClassAllocatorLocalCache168 void destroyBatch(uptr ClassId, void *B) { 169 if (ClassId != BatchClassId) 170 deallocate(BatchClassId, B); 171 } 172 refillSizeClassAllocatorLocalCache173 NOINLINE bool refill(PerClass *C, uptr ClassId) { 174 initCacheMaybe(C); 175 TransferBatch *B = Allocator->popBatch(this, ClassId); 176 if (UNLIKELY(!B)) 177 return false; 178 DCHECK_GT(B->getCount(), 0); 179 C->Count = B->getCount(); 180 B->copyToArray(C->Chunks); 181 B->clear(); 182 destroyBatch(ClassId, B); 183 return true; 184 } 185 drainSizeClassAllocatorLocalCache186 NOINLINE void drain(PerClass *C, uptr ClassId) { 187 const u32 Count = Min(C->MaxCount / 2, C->Count); 188 TransferBatch *B = 189 createBatch(ClassId, Allocator->decompactPtr(ClassId, C->Chunks[0])); 190 if (UNLIKELY(!B)) 191 reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId)); 192 B->setFromArray(&C->Chunks[0], Count); 193 C->Count -= Count; 194 for (uptr I = 0; I < C->Count; I++) 195 C->Chunks[I] = C->Chunks[I + Count]; 196 Allocator->pushBatch(ClassId, B); 197 } 198 }; 199 200 } // namespace scudo 201 202 #endif // SCUDO_LOCAL_CACHE_H_ 203