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 Count = N; 26 memcpy(Batch, Array, sizeof(void *) * Count); 27 } 28 void clear() { Count = 0; } 29 void add(void *P) { 30 DCHECK_LT(Count, MaxNumCached); 31 Batch[Count++] = P; 32 } 33 void copyToArray(void **Array) const { 34 memcpy(Array, Batch, sizeof(void *) * Count); 35 } 36 u32 getCount() const { return Count; } 37 void *get(u32 I) const { 38 DCHECK_LE(I, Count); 39 return Batch[I]; 40 } 41 static u32 getMaxCached(uptr Size) { 42 return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size)); 43 } 44 TransferBatch *Next; 45 46 private: 47 u32 Count; 48 void *Batch[MaxNumCached]; 49 }; 50 51 void initLinkerInitialized(GlobalStats *S, SizeClassAllocator *A) { 52 Stats.initLinkerInitialized(); 53 if (LIKELY(S)) 54 S->link(&Stats); 55 Allocator = A; 56 } 57 58 void init(GlobalStats *S, SizeClassAllocator *A) { 59 memset(this, 0, sizeof(*this)); 60 initLinkerInitialized(S, A); 61 } 62 63 void destroy(GlobalStats *S) { 64 drain(); 65 if (LIKELY(S)) 66 S->unlink(&Stats); 67 } 68 69 void *allocate(uptr ClassId) { 70 DCHECK_LT(ClassId, NumClasses); 71 PerClass *C = &PerClassArray[ClassId]; 72 if (C->Count == 0) { 73 if (UNLIKELY(!refill(C, ClassId))) 74 return nullptr; 75 DCHECK_GT(C->Count, 0); 76 } 77 // We read ClassSize first before accessing Chunks because it's adjacent to 78 // Count, while Chunks might be further off (depending on Count). That keeps 79 // the memory accesses in close quarters. 80 const uptr ClassSize = C->ClassSize; 81 void *P = C->Chunks[--C->Count]; 82 // The jury is still out as to whether any kind of PREFETCH here increases 83 // performance. It definitely decreases performance on Android though. 84 // if (!SCUDO_ANDROID) PREFETCH(P); 85 Stats.add(StatAllocated, ClassSize); 86 Stats.sub(StatFree, ClassSize); 87 return P; 88 } 89 90 void deallocate(uptr ClassId, void *P) { 91 CHECK_LT(ClassId, NumClasses); 92 PerClass *C = &PerClassArray[ClassId]; 93 // We still have to initialize the cache in the event that the first heap 94 // operation in a thread is a deallocation. 95 initCacheMaybe(C); 96 if (C->Count == C->MaxCount) 97 drain(C, ClassId); 98 // See comment in allocate() about memory accesses. 99 const uptr ClassSize = C->ClassSize; 100 C->Chunks[C->Count++] = P; 101 Stats.sub(StatAllocated, ClassSize); 102 Stats.add(StatFree, 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 C->Count = B->getCount(); 161 B->copyToArray(C->Chunks); 162 B->clear(); 163 destroyBatch(ClassId, B); 164 return true; 165 } 166 167 NOINLINE void drain(PerClass *C, uptr ClassId) { 168 const u32 Count = Min(C->MaxCount / 2, C->Count); 169 TransferBatch *B = createBatch(ClassId, C->Chunks[0]); 170 if (UNLIKELY(!B)) 171 reportOutOfMemory( 172 SizeClassAllocator::getSizeByClassId(SizeClassMap::BatchClassId)); 173 B->setFromArray(&C->Chunks[0], Count); 174 C->Count -= Count; 175 for (uptr I = 0; I < C->Count; I++) 176 C->Chunks[I] = C->Chunks[I + Count]; 177 Allocator->pushBatch(ClassId, B); 178 } 179 }; 180 181 } // namespace scudo 182 183 #endif // SCUDO_LOCAL_CACHE_H_ 184