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