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 21 struct TransferBatch { 22 static const u32 MaxNumCached = SizeClassMap::MaxNumCachedHint; 23 void setFromArray(void **Array, u32 N) { 24 DCHECK_LE(N, MaxNumCached); 25 for (u32 I = 0; I < N; I++) 26 Batch[I] = Array[I]; 27 Count = N; 28 } 29 void clear() { Count = 0; } 30 void add(void *P) { 31 DCHECK_LT(Count, MaxNumCached); 32 Batch[Count++] = P; 33 } 34 void copyToArray(void **Array) const { 35 for (u32 I = 0; I < Count; I++) 36 Array[I] = Batch[I]; 37 } 38 u32 getCount() const { return Count; } 39 void *get(u32 I) const { 40 DCHECK_LE(I, Count); 41 return Batch[I]; 42 } 43 static u32 getMaxCached(uptr Size) { 44 return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size)); 45 } 46 TransferBatch *Next; 47 48 private: 49 u32 Count; 50 void *Batch[MaxNumCached]; 51 }; 52 53 void initLinkerInitialized(GlobalStats *S, SizeClassAllocator *A) { 54 Stats.initLinkerInitialized(); 55 if (S) 56 S->link(&Stats); 57 Allocator = A; 58 } 59 60 void init(GlobalStats *S, SizeClassAllocator *A) { 61 memset(this, 0, sizeof(*this)); 62 initLinkerInitialized(S, A); 63 } 64 65 void destroy(GlobalStats *S) { 66 drain(); 67 if (S) 68 S->unlink(&Stats); 69 } 70 71 void *allocate(uptr ClassId) { 72 CHECK_LT(ClassId, NumClasses); 73 PerClass *C = &PerClassArray[ClassId]; 74 if (C->Count == 0) { 75 if (UNLIKELY(!refill(C, ClassId))) 76 return nullptr; 77 DCHECK_GT(C->Count, 0); 78 } 79 // We read ClassSize first before accessing Chunks because it's adjacent to 80 // Count, while Chunks might be further off (depending on Count). That keeps 81 // the memory accesses in close quarters. 82 const uptr ClassSize = C->ClassSize; 83 void *P = C->Chunks[--C->Count]; 84 // The jury is still out as to whether any kind of PREFETCH here increases 85 // performance. It definitely decreases performance on Android though. 86 // if (!SCUDO_ANDROID) PREFETCH(P); 87 Stats.add(StatAllocated, ClassSize); 88 return P; 89 } 90 91 void deallocate(uptr ClassId, void *P) { 92 CHECK_LT(ClassId, NumClasses); 93 PerClass *C = &PerClassArray[ClassId]; 94 // We still have to initialize the cache in the event that the first heap 95 // operation in a thread is a deallocation. 96 initCacheMaybe(C); 97 if (C->Count == C->MaxCount) 98 drain(C, ClassId); 99 // See comment in allocate() about memory accesses. 100 const uptr ClassSize = C->ClassSize; 101 C->Chunks[C->Count++] = P; 102 Stats.sub(StatAllocated, ClassSize); 103 } 104 105 void drain() { 106 for (uptr I = 0; I < NumClasses; I++) { 107 PerClass *C = &PerClassArray[I]; 108 while (C->Count > 0) 109 drain(C, I); 110 } 111 } 112 113 TransferBatch *createBatch(uptr ClassId, void *B) { 114 if (ClassId != SizeClassMap::BatchClassId) 115 B = allocate(SizeClassMap::BatchClassId); 116 return reinterpret_cast<TransferBatch *>(B); 117 } 118 119 LocalStats &getStats() { return Stats; } 120 121 private: 122 static const uptr NumClasses = SizeClassMap::NumClasses; 123 struct PerClass { 124 u32 Count; 125 u32 MaxCount; 126 uptr ClassSize; 127 void *Chunks[2 * TransferBatch::MaxNumCached]; 128 }; 129 PerClass PerClassArray[NumClasses]; 130 LocalStats Stats; 131 SizeClassAllocator *Allocator; 132 133 ALWAYS_INLINE void initCacheMaybe(PerClass *C) { 134 if (LIKELY(C->MaxCount)) 135 return; 136 initCache(); 137 DCHECK_NE(C->MaxCount, 0U); 138 } 139 140 NOINLINE void initCache() { 141 for (uptr I = 0; I < NumClasses; I++) { 142 PerClass *P = &PerClassArray[I]; 143 const uptr Size = SizeClassAllocator::getSizeByClassId(I); 144 P->MaxCount = 2 * TransferBatch::getMaxCached(Size); 145 P->ClassSize = Size; 146 } 147 } 148 149 void destroyBatch(uptr ClassId, void *B) { 150 if (ClassId != SizeClassMap::BatchClassId) 151 deallocate(SizeClassMap::BatchClassId, B); 152 } 153 154 NOINLINE bool refill(PerClass *C, uptr ClassId) { 155 initCacheMaybe(C); 156 TransferBatch *B = Allocator->popBatch(this, ClassId); 157 if (UNLIKELY(!B)) 158 return false; 159 DCHECK_GT(B->getCount(), 0); 160 B->copyToArray(C->Chunks); 161 C->Count = B->getCount(); 162 destroyBatch(ClassId, B); 163 return true; 164 } 165 166 NOINLINE void drain(PerClass *C, uptr ClassId) { 167 const u32 Count = Min(C->MaxCount / 2, C->Count); 168 const uptr FirstIndexToDrain = C->Count - Count; 169 TransferBatch *B = createBatch(ClassId, C->Chunks[FirstIndexToDrain]); 170 if (UNLIKELY(!B)) 171 reportOutOfMemory( 172 SizeClassAllocator::getSizeByClassId(SizeClassMap::BatchClassId)); 173 B->setFromArray(&C->Chunks[FirstIndexToDrain], Count); 174 C->Count -= Count; 175 Allocator->pushBatch(ClassId, B); 176 } 177 }; 178 179 } // namespace scudo 180 181 #endif // SCUDO_LOCAL_CACHE_H_ 182