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; 24 void setFromArray(CompactPtrT *Array, u32 N) { 25 DCHECK_LE(N, MaxNumCached); 26 Count = N; 27 memcpy(Batch, Array, sizeof(Batch[0]) * Count); 28 } 29 void clear() { Count = 0; } 30 void add(CompactPtrT P) { 31 DCHECK_LT(Count, MaxNumCached); 32 Batch[Count++] = P; 33 } 34 void copyToArray(CompactPtrT *Array) const { 35 memcpy(Array, Batch, sizeof(Batch[0]) * Count); 36 } 37 u32 getCount() const { return Count; } 38 CompactPtrT get(u32 I) const { 39 DCHECK_LE(I, Count); 40 return Batch[I]; 41 } 42 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 52 void init(GlobalStats *S, SizeClassAllocator *A) { 53 DCHECK(isEmpty()); 54 Stats.init(); 55 if (LIKELY(S)) 56 S->link(&Stats); 57 Allocator = A; 58 } 59 60 void destroy(GlobalStats *S) { 61 drain(); 62 if (LIKELY(S)) 63 S->unlink(&Stats); 64 } 65 66 void *allocate(uptr ClassId) { 67 DCHECK_LT(ClassId, NumClasses); 68 PerClass *C = &PerClassArray[ClassId]; 69 if (C->Count == 0) { 70 if (UNLIKELY(!refill(C, ClassId))) 71 return nullptr; 72 DCHECK_GT(C->Count, 0); 73 } 74 // We read ClassSize first before accessing Chunks because it's adjacent to 75 // Count, while Chunks might be further off (depending on Count). That keeps 76 // the memory accesses in close quarters. 77 const uptr ClassSize = C->ClassSize; 78 CompactPtrT CompactP = C->Chunks[--C->Count]; 79 Stats.add(StatAllocated, ClassSize); 80 Stats.sub(StatFree, ClassSize); 81 return Allocator->decompactPtr(ClassId, CompactP); 82 } 83 84 void deallocate(uptr ClassId, void *P) { 85 CHECK_LT(ClassId, NumClasses); 86 PerClass *C = &PerClassArray[ClassId]; 87 // We still have to initialize the cache in the event that the first heap 88 // operation in a thread is a deallocation. 89 initCacheMaybe(C); 90 if (C->Count == C->MaxCount) 91 drain(C, ClassId); 92 // See comment in allocate() about memory accesses. 93 const uptr ClassSize = C->ClassSize; 94 C->Chunks[C->Count++] = 95 Allocator->compactPtr(ClassId, reinterpret_cast<uptr>(P)); 96 Stats.sub(StatAllocated, ClassSize); 97 Stats.add(StatFree, ClassSize); 98 } 99 100 bool isEmpty() const { 101 for (uptr I = 0; I < NumClasses; ++I) 102 if (PerClassArray[I].Count) 103 return false; 104 return true; 105 } 106 107 void drain() { 108 // Drain BatchClassId last as createBatch can refill it. 109 for (uptr I = 0; I < NumClasses; ++I) { 110 if (I == BatchClassId) 111 continue; 112 while (PerClassArray[I].Count > 0) 113 drain(&PerClassArray[I], I); 114 } 115 while (PerClassArray[BatchClassId].Count > 0) 116 drain(&PerClassArray[BatchClassId], BatchClassId); 117 DCHECK(isEmpty()); 118 } 119 120 TransferBatch *createBatch(uptr ClassId, void *B) { 121 if (ClassId != BatchClassId) 122 B = allocate(BatchClassId); 123 return reinterpret_cast<TransferBatch *>(B); 124 } 125 126 LocalStats &getStats() { return Stats; } 127 128 private: 129 static const uptr NumClasses = SizeClassMap::NumClasses; 130 static const uptr BatchClassId = SizeClassMap::BatchClassId; 131 struct PerClass { 132 u32 Count; 133 u32 MaxCount; 134 // Note: ClassSize is zero for the transfer batch. 135 uptr ClassSize; 136 CompactPtrT Chunks[2 * TransferBatch::MaxNumCached]; 137 }; 138 PerClass PerClassArray[NumClasses] = {}; 139 LocalStats Stats; 140 SizeClassAllocator *Allocator = nullptr; 141 142 ALWAYS_INLINE void initCacheMaybe(PerClass *C) { 143 if (LIKELY(C->MaxCount)) 144 return; 145 initCache(); 146 DCHECK_NE(C->MaxCount, 0U); 147 } 148 149 NOINLINE void initCache() { 150 for (uptr I = 0; I < NumClasses; I++) { 151 PerClass *P = &PerClassArray[I]; 152 const uptr Size = SizeClassAllocator::getSizeByClassId(I); 153 P->MaxCount = 2 * TransferBatch::getMaxCached(Size); 154 if (I != BatchClassId) { 155 P->ClassSize = Size; 156 } else { 157 // ClassSize in this struct is only used for malloc/free stats, which 158 // should only track user allocations, not internal movements. 159 P->ClassSize = 0; 160 } 161 } 162 } 163 164 void destroyBatch(uptr ClassId, void *B) { 165 if (ClassId != BatchClassId) 166 deallocate(BatchClassId, B); 167 } 168 169 NOINLINE bool refill(PerClass *C, uptr ClassId) { 170 initCacheMaybe(C); 171 TransferBatch *B = Allocator->popBatch(this, ClassId); 172 if (UNLIKELY(!B)) 173 return false; 174 DCHECK_GT(B->getCount(), 0); 175 C->Count = B->getCount(); 176 B->copyToArray(C->Chunks); 177 B->clear(); 178 destroyBatch(ClassId, B); 179 return true; 180 } 181 182 NOINLINE void drain(PerClass *C, uptr ClassId) { 183 const u32 Count = Min(C->MaxCount / 2, C->Count); 184 TransferBatch *B = 185 createBatch(ClassId, Allocator->decompactPtr(ClassId, C->Chunks[0])); 186 if (UNLIKELY(!B)) 187 reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId)); 188 B->setFromArray(&C->Chunks[0], Count); 189 C->Count -= Count; 190 for (uptr I = 0; I < C->Count; I++) 191 C->Chunks[I] = C->Chunks[I + Count]; 192 Allocator->pushBatch(ClassId, B); 193 } 194 }; 195 196 } // namespace scudo 197 198 #endif // SCUDO_LOCAL_CACHE_H_ 199