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 "list.h" 14 #include "platform.h" 15 #include "report.h" 16 #include "stats.h" 17 #include "string_utils.h" 18 19 namespace scudo { 20 21 template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache { 22 typedef typename SizeClassAllocator::SizeClassMap SizeClassMap; 23 typedef typename SizeClassAllocator::CompactPtrT CompactPtrT; 24 25 struct TransferBatch { 26 static const u16 MaxNumCached = SizeClassMap::MaxNumCachedHint; setFromArraySizeClassAllocatorLocalCache::TransferBatch27 void setFromArray(CompactPtrT *Array, u16 N) { 28 DCHECK_LE(N, MaxNumCached); 29 Count = N; 30 memcpy(Batch, Array, sizeof(Batch[0]) * Count); 31 } appendFromArraySizeClassAllocatorLocalCache::TransferBatch32 void appendFromArray(CompactPtrT *Array, u16 N) { 33 DCHECK_LE(N, MaxNumCached - Count); 34 memcpy(Batch + Count, Array, sizeof(Batch[0]) * N); 35 // u16 will be promoted to int by arithmetic type conversion. 36 Count = static_cast<u16>(Count + N); 37 } clearSizeClassAllocatorLocalCache::TransferBatch38 void clear() { Count = 0; } addSizeClassAllocatorLocalCache::TransferBatch39 void add(CompactPtrT P) { 40 DCHECK_LT(Count, MaxNumCached); 41 Batch[Count++] = P; 42 } copyToArraySizeClassAllocatorLocalCache::TransferBatch43 void copyToArray(CompactPtrT *Array) const { 44 memcpy(Array, Batch, sizeof(Batch[0]) * Count); 45 } getCountSizeClassAllocatorLocalCache::TransferBatch46 u16 getCount() const { return Count; } getSizeClassAllocatorLocalCache::TransferBatch47 CompactPtrT get(u16 I) const { 48 DCHECK_LE(I, Count); 49 return Batch[I]; 50 } getMaxCachedSizeClassAllocatorLocalCache::TransferBatch51 static u16 getMaxCached(uptr Size) { 52 return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size)); 53 } 54 TransferBatch *Next; 55 56 private: 57 CompactPtrT Batch[MaxNumCached]; 58 u16 Count; 59 }; 60 61 // A BatchGroup is used to collect blocks. Each group has a group id to 62 // identify the group kind of contained blocks. 63 struct BatchGroup { 64 // `Next` is used by IntrusiveList. 65 BatchGroup *Next; 66 // The compact base address of each group 67 uptr CompactPtrGroupBase; 68 // Cache value of TransferBatch::getMaxCached() 69 u16 MaxCachedPerBatch; 70 // Number of blocks pushed into this group. This is an increment-only 71 // counter. 72 uptr PushedBlocks; 73 // This is used to track how many bytes are not in-use since last time we 74 // tried to release pages. 75 uptr BytesInBGAtLastCheckpoint; 76 // Blocks are managed by TransferBatch in a list. 77 SinglyLinkedList<TransferBatch> Batches; 78 }; 79 80 static_assert(sizeof(BatchGroup) <= sizeof(TransferBatch), 81 "BatchGroup uses the same class size as TransferBatch"); 82 initSizeClassAllocatorLocalCache83 void init(GlobalStats *S, SizeClassAllocator *A) { 84 DCHECK(isEmpty()); 85 Stats.init(); 86 if (LIKELY(S)) 87 S->link(&Stats); 88 Allocator = A; 89 } 90 destroySizeClassAllocatorLocalCache91 void destroy(GlobalStats *S) { 92 drain(); 93 if (LIKELY(S)) 94 S->unlink(&Stats); 95 } 96 allocateSizeClassAllocatorLocalCache97 void *allocate(uptr ClassId) { 98 DCHECK_LT(ClassId, NumClasses); 99 PerClass *C = &PerClassArray[ClassId]; 100 if (C->Count == 0) { 101 if (UNLIKELY(!refill(C, ClassId))) 102 return nullptr; 103 DCHECK_GT(C->Count, 0); 104 } 105 // We read ClassSize first before accessing Chunks because it's adjacent to 106 // Count, while Chunks might be further off (depending on Count). That keeps 107 // the memory accesses in close quarters. 108 const uptr ClassSize = C->ClassSize; 109 CompactPtrT CompactP = C->Chunks[--C->Count]; 110 Stats.add(StatAllocated, ClassSize); 111 Stats.sub(StatFree, ClassSize); 112 return Allocator->decompactPtr(ClassId, CompactP); 113 } 114 deallocateSizeClassAllocatorLocalCache115 void deallocate(uptr ClassId, void *P) { 116 CHECK_LT(ClassId, NumClasses); 117 PerClass *C = &PerClassArray[ClassId]; 118 // We still have to initialize the cache in the event that the first heap 119 // operation in a thread is a deallocation. 120 initCacheMaybe(C); 121 if (C->Count == C->MaxCount) 122 drain(C, ClassId); 123 // See comment in allocate() about memory accesses. 124 const uptr ClassSize = C->ClassSize; 125 C->Chunks[C->Count++] = 126 Allocator->compactPtr(ClassId, reinterpret_cast<uptr>(P)); 127 Stats.sub(StatAllocated, ClassSize); 128 Stats.add(StatFree, ClassSize); 129 } 130 isEmptySizeClassAllocatorLocalCache131 bool isEmpty() const { 132 for (uptr I = 0; I < NumClasses; ++I) 133 if (PerClassArray[I].Count) 134 return false; 135 return true; 136 } 137 drainSizeClassAllocatorLocalCache138 void drain() { 139 // Drain BatchClassId last as createBatch can refill it. 140 for (uptr I = 0; I < NumClasses; ++I) { 141 if (I == BatchClassId) 142 continue; 143 while (PerClassArray[I].Count > 0) 144 drain(&PerClassArray[I], I); 145 } 146 while (PerClassArray[BatchClassId].Count > 0) 147 drain(&PerClassArray[BatchClassId], BatchClassId); 148 DCHECK(isEmpty()); 149 } 150 createBatchSizeClassAllocatorLocalCache151 TransferBatch *createBatch(uptr ClassId, void *B) { 152 if (ClassId != BatchClassId) 153 B = allocate(BatchClassId); 154 if (UNLIKELY(!B)) 155 reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId)); 156 return reinterpret_cast<TransferBatch *>(B); 157 } 158 createGroupSizeClassAllocatorLocalCache159 BatchGroup *createGroup() { 160 void *Ptr = allocate(BatchClassId); 161 if (UNLIKELY(!Ptr)) 162 reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId)); 163 return reinterpret_cast<BatchGroup *>(Ptr); 164 } 165 getStatsSizeClassAllocatorLocalCache166 LocalStats &getStats() { return Stats; } 167 getStatsSizeClassAllocatorLocalCache168 void getStats(ScopedString *Str) { 169 bool EmptyCache = true; 170 for (uptr I = 0; I < NumClasses; ++I) { 171 if (PerClassArray[I].Count == 0) 172 continue; 173 174 EmptyCache = false; 175 // The size of BatchClass is set to 0 intentionally. See the comment in 176 // initCache() for more details. 177 const uptr ClassSize = I == BatchClassId 178 ? SizeClassAllocator::getSizeByClassId(I) 179 : PerClassArray[I].ClassSize; 180 // Note that the string utils don't support printing u16 thus we cast it 181 // to a common use type uptr. 182 Str->append(" %02zu (%6zu): cached: %4zu max: %4zu\n", I, ClassSize, 183 static_cast<uptr>(PerClassArray[I].Count), 184 static_cast<uptr>(PerClassArray[I].MaxCount)); 185 } 186 187 if (EmptyCache) 188 Str->append(" No block is cached.\n"); 189 } 190 191 private: 192 static const uptr NumClasses = SizeClassMap::NumClasses; 193 static const uptr BatchClassId = SizeClassMap::BatchClassId; 194 struct alignas(SCUDO_CACHE_LINE_SIZE) PerClass { 195 u16 Count; 196 u16 MaxCount; 197 // Note: ClassSize is zero for the transfer batch. 198 uptr ClassSize; 199 CompactPtrT Chunks[2 * TransferBatch::MaxNumCached]; 200 }; 201 PerClass PerClassArray[NumClasses] = {}; 202 LocalStats Stats; 203 SizeClassAllocator *Allocator = nullptr; 204 initCacheMaybeSizeClassAllocatorLocalCache205 ALWAYS_INLINE void initCacheMaybe(PerClass *C) { 206 if (LIKELY(C->MaxCount)) 207 return; 208 initCache(); 209 DCHECK_NE(C->MaxCount, 0U); 210 } 211 initCacheSizeClassAllocatorLocalCache212 NOINLINE void initCache() { 213 for (uptr I = 0; I < NumClasses; I++) { 214 PerClass *P = &PerClassArray[I]; 215 const uptr Size = SizeClassAllocator::getSizeByClassId(I); 216 P->MaxCount = static_cast<u16>(2 * TransferBatch::getMaxCached(Size)); 217 if (I != BatchClassId) { 218 P->ClassSize = Size; 219 } else { 220 // ClassSize in this struct is only used for malloc/free stats, which 221 // should only track user allocations, not internal movements. 222 P->ClassSize = 0; 223 } 224 } 225 } 226 destroyBatchSizeClassAllocatorLocalCache227 void destroyBatch(uptr ClassId, void *B) { 228 if (ClassId != BatchClassId) 229 deallocate(BatchClassId, B); 230 } 231 refillSizeClassAllocatorLocalCache232 NOINLINE bool refill(PerClass *C, uptr ClassId) { 233 initCacheMaybe(C); 234 TransferBatch *B = Allocator->popBatch(this, ClassId); 235 if (UNLIKELY(!B)) 236 return false; 237 DCHECK_GT(B->getCount(), 0); 238 C->Count = B->getCount(); 239 B->copyToArray(C->Chunks); 240 B->clear(); 241 destroyBatch(ClassId, B); 242 return true; 243 } 244 drainSizeClassAllocatorLocalCache245 NOINLINE void drain(PerClass *C, uptr ClassId) { 246 const u16 Count = Min(static_cast<u16>(C->MaxCount / 2), C->Count); 247 Allocator->pushBlocks(this, ClassId, &C->Chunks[0], Count); 248 // u16 will be promoted to int by arithmetic type conversion. 249 C->Count = static_cast<u16>(C->Count - Count); 250 for (u16 I = 0; I < C->Count; I++) 251 C->Chunks[I] = C->Chunks[I + Count]; 252 } 253 }; 254 255 } // namespace scudo 256 257 #endif // SCUDO_LOCAL_CACHE_H_ 258