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(Batch, Count, &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(&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
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(&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
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(&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