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 
17 namespace scudo {
18 
19 struct 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(Batch, Count, &State); }
61 };
62 
63 static_assert(sizeof(QuarantineBatch) <= (1U << 13), ""); // 8Kb.
64 
65 // Per-thread cache of memory blocks.
66 template <typename Callback> class QuarantineCache {
67 public:
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(&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(Size);
85     }
86   }
87 
88   void transfer(QuarantineCache *From) {
89     List.append_back(&From->List);
90     addToSize(From->getSize());
91     atomic_store_relaxed(&From->Size, 0);
92   }
93 
94   void enqueueBatch(QuarantineBatch *B) {
95     List.push_back(B);
96     addToSize(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(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(Current->Next)) {
113         QuarantineBatch *Extracted = Current->Next;
114         // Move all the chunks into the current batch.
115         Current->merge(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(Current, 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(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         "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 
159 private:
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);
171 template <typename Callback, typename Node> class GlobalQuarantine {
172 public:
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(&MaxSize, Size);
186     atomic_store_relaxed(&MinSize, Size / 10 * 9); // 90% of max size.
187     atomic_store_relaxed(&MaxCacheSize, CacheSize);
188 
189     Cache.init();
190   }
191 
192   uptr getMaxSize() const { return atomic_load_relaxed(&MaxSize); }
193   uptr getCacheSize() const { return atomic_load_relaxed(&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(atomic_load_relaxed(&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(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("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 
247 private:
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(&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(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