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