1//===-- quarantine.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_QUARANTINE_H_
10#define SCUDO_QUARANTINE_H_
11
12#include "list.h"
13#include "mutex.h"
14#include "string_utils.h"
15#include "thread_annotations.h"
16
17namespace scudo {
18
19struct QuarantineBatch {
20 // With the following count, a batch (and the header that protects it) occupy
21 // 4096 bytes on 32-bit platforms, and 8192 bytes on 64-bit.
22 static const u32 MaxCount = 1019;
23 QuarantineBatch *Next;
24 uptr Size;
25 u32 Count;
26 void *Batch[MaxCount];
27
28 void init(void *Ptr, uptr Size) {
29 Count = 1;
30 Batch[0] = Ptr;
31 this->Size = Size + sizeof(QuarantineBatch); // Account for the Batch Size.
32 }
33
34 // The total size of quarantined nodes recorded in this batch.
35 uptr getQuarantinedSize() const { return Size - sizeof(QuarantineBatch); }
36
37 void push_back(void *Ptr, uptr Size) {
38 DCHECK_LT(Count, MaxCount);
39 Batch[Count++] = Ptr;
40 this->Size += Size;
41 }
42
43 bool canMerge(const QuarantineBatch *const From) const {
44 return Count + From->Count <= MaxCount;
45 }
46
47 void merge(QuarantineBatch *const From) {
48 DCHECK_LE(Count + From->Count, MaxCount);
49 DCHECK_GE(Size, sizeof(QuarantineBatch));
50
51 for (uptr I = 0; I < From->Count; ++I)
52 Batch[Count + I] = From->Batch[I];
53 Count += From->Count;
54 Size += From->getQuarantinedSize();
55
56 From->Count = 0;
57 From->Size = sizeof(QuarantineBatch);
58 }
59
60 void shuffle(u32 State) { ::scudo::shuffle(A: Batch, N: Count, RandState: &State); }
61};
62
63static_assert(sizeof(QuarantineBatch) <= (1U << 13), ""); // 8Kb.
64
65// Per-thread cache of memory blocks.
66template <typename Callback> class QuarantineCache {
67public:
68 void init() { DCHECK_EQ(atomic_load_relaxed(&Size), 0U); }
69
70 // Total memory used, including internal accounting.
71 uptr getSize() const { return atomic_load_relaxed(A: &Size); }
72 // Memory used for internal accounting.
73 uptr getOverheadSize() const { return List.size() * sizeof(QuarantineBatch); }
74
75 void enqueue(Callback Cb, void *Ptr, uptr Size) {
76 if (List.empty() || List.back()->Count == QuarantineBatch::MaxCount) {
77 QuarantineBatch *B =
78 reinterpret_cast<QuarantineBatch *>(Cb.allocate(sizeof(*B)));
79 DCHECK(B);
80 B->init(Ptr, Size);
81 enqueueBatch(B);
82 } else {
83 List.back()->push_back(Ptr, Size);
84 addToSize(add: Size);
85 }
86 }
87
88 void transfer(QuarantineCache *From) {
89 List.append_back(L: &From->List);
90 addToSize(add: From->getSize());
91 atomic_store_relaxed(&From->Size, 0);
92 }
93
94 void enqueueBatch(QuarantineBatch *B) {
95 List.push_back(X: B);
96 addToSize(add: B->Size);
97 }
98
99 QuarantineBatch *dequeueBatch() {
100 if (List.empty())
101 return nullptr;
102 QuarantineBatch *B = List.front();
103 List.pop_front();
104 subFromSize(sub: B->Size);
105 return B;
106 }
107
108 void mergeBatches(QuarantineCache *ToDeallocate) {
109 uptr ExtractedSize = 0;
110 QuarantineBatch *Current = List.front();
111 while (Current && Current->Next) {
112 if (Current->canMerge(From: Current->Next)) {
113 QuarantineBatch *Extracted = Current->Next;
114 // Move all the chunks into the current batch.
115 Current->merge(From: Extracted);
116 DCHECK_EQ(Extracted->Count, 0);
117 DCHECK_EQ(Extracted->Size, sizeof(QuarantineBatch));
118 // Remove the next batch From the list and account for its Size.
119 List.extract(Prev: Current, X: Extracted);
120 ExtractedSize += Extracted->Size;
121 // Add it to deallocation list.
122 ToDeallocate->enqueueBatch(Extracted);
123 } else {
124 Current = Current->Next;
125 }
126 }
127 subFromSize(sub: ExtractedSize);
128 }
129
130 void getStats(ScopedString *Str) const {
131 uptr BatchCount = 0;
132 uptr TotalOverheadBytes = 0;
133 uptr TotalBytes = 0;
134 uptr TotalQuarantineChunks = 0;
135 for (const QuarantineBatch &Batch : List) {
136 BatchCount++;
137 TotalBytes += Batch.Size;
138 TotalOverheadBytes += Batch.Size - Batch.getQuarantinedSize();
139 TotalQuarantineChunks += Batch.Count;
140 }
141 const uptr QuarantineChunksCapacity =
142 BatchCount * QuarantineBatch::MaxCount;
143 const uptr ChunksUsagePercent =
144 (QuarantineChunksCapacity == 0)
145 ? 0
146 : TotalQuarantineChunks * 100 / QuarantineChunksCapacity;
147 const uptr TotalQuarantinedBytes = TotalBytes - TotalOverheadBytes;
148 const uptr MemoryOverheadPercent =
149 (TotalQuarantinedBytes == 0)
150 ? 0
151 : TotalOverheadBytes * 100 / TotalQuarantinedBytes;
152 Str->append(
153 Format: "Stats: Quarantine: batches: %zu; bytes: %zu (user: %zu); chunks: %zu "
154 "(capacity: %zu); %zu%% chunks used; %zu%% memory overhead\n",
155 BatchCount, TotalBytes, TotalQuarantinedBytes, TotalQuarantineChunks,
156 QuarantineChunksCapacity, ChunksUsagePercent, MemoryOverheadPercent);
157 }
158
159private:
160 SinglyLinkedList<QuarantineBatch> List;
161 atomic_uptr Size = {};
162
163 void addToSize(uptr add) { atomic_store_relaxed(&Size, getSize() + add); }
164 void subFromSize(uptr sub) { atomic_store_relaxed(&Size, getSize() - sub); }
165};
166
167// The callback interface is:
168// void Callback::recycle(Node *Ptr);
169// void *Callback::allocate(uptr Size);
170// void Callback::deallocate(void *Ptr);
171template <typename Callback, typename Node> class GlobalQuarantine {
172public:
173 typedef QuarantineCache<Callback> CacheT;
174 using ThisT = GlobalQuarantine<Callback, Node>;
175
176 void init(uptr Size, uptr CacheSize) NO_THREAD_SAFETY_ANALYSIS {
177 DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));
178 DCHECK_EQ(atomic_load_relaxed(&MaxSize), 0U);
179 DCHECK_EQ(atomic_load_relaxed(&MinSize), 0U);
180 DCHECK_EQ(atomic_load_relaxed(&MaxCacheSize), 0U);
181 // Thread local quarantine size can be zero only when global quarantine size
182 // is zero (it allows us to perform just one atomic read per put() call).
183 CHECK((Size == 0 && CacheSize == 0) || CacheSize != 0);
184
185 atomic_store_relaxed(A: &MaxSize, V: Size);
186 atomic_store_relaxed(A: &MinSize, V: Size / 10 * 9); // 90% of max size.
187 atomic_store_relaxed(A: &MaxCacheSize, V: CacheSize);
188
189 Cache.init();
190 }
191
192 uptr getMaxSize() const { return atomic_load_relaxed(A: &MaxSize); }
193 uptr getCacheSize() const { return atomic_load_relaxed(A: &MaxCacheSize); }
194
195 // This is supposed to be used in test only.
196 bool isEmpty() {
197 ScopedLock L(CacheMutex);
198 return Cache.getSize() == 0U;
199 }
200
201 void put(CacheT *C, Callback Cb, Node *Ptr, uptr Size) {
202 C->enqueue(Cb, Ptr, Size);
203 if (C->getSize() > getCacheSize())
204 drain(C, Cb);
205 }
206
207 void NOINLINE drain(CacheT *C, Callback Cb) EXCLUDES(CacheMutex) {
208 bool needRecycle = false;
209 {
210 ScopedLock L(CacheMutex);
211 Cache.transfer(C);
212 needRecycle = Cache.getSize() > getMaxSize();
213 }
214
215 if (needRecycle && RecycleMutex.tryLock())
216 recycle(MinSize: atomic_load_relaxed(A: &MinSize), Cb);
217 }
218
219 void NOINLINE drainAndRecycle(CacheT *C, Callback Cb) EXCLUDES(CacheMutex) {
220 {
221 ScopedLock L(CacheMutex);
222 Cache.transfer(C);
223 }
224 RecycleMutex.lock();
225 recycle(MinSize: 0, Cb);
226 }
227
228 void getStats(ScopedString *Str) EXCLUDES(CacheMutex) {
229 ScopedLock L(CacheMutex);
230 // It assumes that the world is stopped, just as the allocator's printStats.
231 Cache.getStats(Str);
232 Str->append(Format: "Quarantine limits: global: %zuK; thread local: %zuK\n",
233 getMaxSize() >> 10, getCacheSize() >> 10);
234 }
235
236 void disable() NO_THREAD_SAFETY_ANALYSIS {
237 // RecycleMutex must be locked 1st since we grab CacheMutex within recycle.
238 RecycleMutex.lock();
239 CacheMutex.lock();
240 }
241
242 void enable() NO_THREAD_SAFETY_ANALYSIS {
243 CacheMutex.unlock();
244 RecycleMutex.unlock();
245 }
246
247private:
248 // Read-only data.
249 alignas(SCUDO_CACHE_LINE_SIZE) HybridMutex CacheMutex;
250 CacheT Cache GUARDED_BY(CacheMutex);
251 alignas(SCUDO_CACHE_LINE_SIZE) HybridMutex RecycleMutex;
252 atomic_uptr MinSize = {};
253 atomic_uptr MaxSize = {};
254 alignas(SCUDO_CACHE_LINE_SIZE) atomic_uptr MaxCacheSize = {};
255
256 void NOINLINE recycle(uptr MinSize, Callback Cb) RELEASE(RecycleMutex)
257 EXCLUDES(CacheMutex) {
258 CacheT Tmp;
259 Tmp.init();
260 {
261 ScopedLock L(CacheMutex);
262 // Go over the batches and merge partially filled ones to
263 // save some memory, otherwise batches themselves (since the memory used
264 // by them is counted against quarantine limit) can overcome the actual
265 // user's quarantined chunks, which diminishes the purpose of the
266 // quarantine.
267 const uptr CacheSize = Cache.getSize();
268 const uptr OverheadSize = Cache.getOverheadSize();
269 DCHECK_GE(CacheSize, OverheadSize);
270 // Do the merge only when overhead exceeds this predefined limit (might
271 // require some tuning). It saves us merge attempt when the batch list
272 // quarantine is unlikely to contain batches suitable for merge.
273 constexpr uptr OverheadThresholdPercents = 100;
274 if (CacheSize > OverheadSize &&
275 OverheadSize * (100 + OverheadThresholdPercents) >
276 CacheSize * OverheadThresholdPercents) {
277 Cache.mergeBatches(&Tmp);
278 }
279 // Extract enough chunks from the quarantine to get below the max
280 // quarantine size and leave some leeway for the newly quarantined chunks.
281 while (Cache.getSize() > MinSize)
282 Tmp.enqueueBatch(Cache.dequeueBatch());
283 }
284 RecycleMutex.unlock();
285 doRecycle(C: &Tmp, Cb);
286 }
287
288 void NOINLINE doRecycle(CacheT *C, Callback Cb) {
289 while (QuarantineBatch *B = C->dequeueBatch()) {
290 const u32 Seed = static_cast<u32>(
291 (reinterpret_cast<uptr>(B) ^ reinterpret_cast<uptr>(C)) >> 4);
292 B->shuffle(State: Seed);
293 constexpr uptr NumberOfPrefetch = 8UL;
294 CHECK(NumberOfPrefetch <= ARRAY_SIZE(B->Batch));
295 for (uptr I = 0; I < NumberOfPrefetch; I++)
296 PREFETCH(B->Batch[I]);
297 for (uptr I = 0, Count = B->Count; I < Count; I++) {
298 if (I + NumberOfPrefetch < Count)
299 PREFETCH(B->Batch[I + NumberOfPrefetch]);
300 Cb.recycle(reinterpret_cast<Node *>(B->Batch[I]));
301 }
302 Cb.deallocate(B);
303 }
304 }
305};
306
307} // namespace scudo
308
309#endif // SCUDO_QUARANTINE_H_
310