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