1 //===-- sanitizer_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 // Memory quarantine for AddressSanitizer and potentially other tools.
10 // Quarantine caches some specified amount of memory in per-thread caches,
11 // then evicts to global FIFO queue. When the queue reaches specified threshold,
12 // oldest memory is recycled.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #ifndef SANITIZER_QUARANTINE_H
17 #define SANITIZER_QUARANTINE_H
18
19 #include "sanitizer_internal_defs.h"
20 #include "sanitizer_mutex.h"
21 #include "sanitizer_list.h"
22
23 namespace __sanitizer {
24
25 template<typename Node> class QuarantineCache;
26
27 struct QuarantineBatch {
28 static const uptr kSize = 1021;
29 QuarantineBatch *next;
30 uptr size;
31 uptr count;
32 void *batch[kSize];
33
34 void init(void *ptr, uptr size) {
35 count = 1;
36 batch[0] = ptr;
37 this->size = size + sizeof(QuarantineBatch); // Account for the batch size.
38 }
39
40 // The total size of quarantined nodes recorded in this batch.
41 uptr quarantined_size() const {
42 return size - sizeof(QuarantineBatch);
43 }
44
45 void push_back(void *ptr, uptr size) {
46 CHECK_LT(count, kSize);
47 batch[count++] = ptr;
48 this->size += size;
49 }
50
51 bool can_merge(const QuarantineBatch* const from) const {
52 return count + from->count <= kSize;
53 }
54
55 void merge(QuarantineBatch* const from) {
56 CHECK_LE(count + from->count, kSize);
57 CHECK_GE(size, sizeof(QuarantineBatch));
58
59 for (uptr i = 0; i < from->count; ++i)
60 batch[count + i] = from->batch[i];
61 count += from->count;
62 size += from->quarantined_size();
63
64 from->count = 0;
65 from->size = sizeof(QuarantineBatch);
66 }
67 };
68
69 COMPILER_CHECK(sizeof(QuarantineBatch) <= (1 << 13)); // 8Kb.
70
71 // The callback interface is:
72 // void Callback::Recycle(Node *ptr);
73 // void *cb.Allocate(uptr size);
74 // void cb.Deallocate(void *ptr);
75 template<typename Callback, typename Node>
76 class Quarantine {
77 public:
78 typedef QuarantineCache<Callback> Cache;
79
80 explicit Quarantine(LinkerInitialized)
81 : cache_(LINKER_INITIALIZED) {
82 }
83
84 void Init(uptr size, uptr cache_size) {
85 // Thread local quarantine size can be zero only when global quarantine size
86 // is zero (it allows us to perform just one atomic read per Put() call).
87 CHECK((size == 0 && cache_size == 0) || cache_size != 0);
88
89 atomic_store_relaxed(&max_size_, size);
90 atomic_store_relaxed(&min_size_, size / 10 * 9); // 90% of max size.
91 atomic_store_relaxed(&max_cache_size_, cache_size);
92
93 cache_mutex_.Init();
94 recycle_mutex_.Init();
95 }
96
97 uptr GetSize() const { return atomic_load_relaxed(&max_size_); }
98 uptr GetCacheSize() const {
99 return atomic_load_relaxed(&max_cache_size_);
100 }
101
102 void Put(Cache *c, Callback cb, Node *ptr, uptr size) {
103 uptr cache_size = GetCacheSize();
104 if (cache_size) {
105 c->Enqueue(cb, ptr, size);
106 } else {
107 // GetCacheSize() == 0 only when GetSize() == 0 (see Init).
108 cb.Recycle(ptr);
109 }
110 // Check cache size anyway to accommodate for runtime cache_size change.
111 if (c->Size() > cache_size)
112 Drain(c, cb);
113 }
114
115 void NOINLINE Drain(Cache *c, Callback cb) {
116 {
117 SpinMutexLock l(&cache_mutex_);
118 cache_.Transfer(c);
119 }
120 if (cache_.Size() > GetSize() && recycle_mutex_.TryLock())
121 Recycle(atomic_load_relaxed(&min_size_), cb);
122 }
123
124 void NOINLINE DrainAndRecycle(Cache *c, Callback cb) {
125 {
126 SpinMutexLock l(&cache_mutex_);
127 cache_.Transfer(c);
128 }
129 recycle_mutex_.Lock();
130 Recycle(0, cb);
131 }
132
133 void PrintStats() const {
134 // It assumes that the world is stopped, just as the allocator's PrintStats.
135 Printf("Quarantine limits: global: %zdMb; thread local: %zdKb\n",
136 GetSize() >> 20, GetCacheSize() >> 10);
137 cache_.PrintStats();
138 }
139
140 private:
141 // Read-only data.
142 char pad0_[kCacheLineSize];
143 atomic_uintptr_t max_size_;
144 atomic_uintptr_t min_size_;
145 atomic_uintptr_t max_cache_size_;
146 char pad1_[kCacheLineSize];
147 StaticSpinMutex cache_mutex_;
148 StaticSpinMutex recycle_mutex_;
149 Cache cache_;
150 char pad2_[kCacheLineSize];
151
152 void NOINLINE Recycle(uptr min_size, Callback cb)
153 SANITIZER_REQUIRES(recycle_mutex_) SANITIZER_RELEASE(recycle_mutex_) {
154 Cache tmp;
155 {
156 SpinMutexLock l(&cache_mutex_);
157 // Go over the batches and merge partially filled ones to
158 // save some memory, otherwise batches themselves (since the memory used
159 // by them is counted against quarantine limit) can overcome the actual
160 // user's quarantined chunks, which diminishes the purpose of the
161 // quarantine.
162 uptr cache_size = cache_.Size();
163 uptr overhead_size = cache_.OverheadSize();
164 CHECK_GE(cache_size, overhead_size);
165 // Do the merge only when overhead exceeds this predefined limit (might
166 // require some tuning). It saves us merge attempt when the batch list
167 // quarantine is unlikely to contain batches suitable for merge.
168 const uptr kOverheadThresholdPercents = 100;
169 if (cache_size > overhead_size &&
170 overhead_size * (100 + kOverheadThresholdPercents) >
171 cache_size * kOverheadThresholdPercents) {
172 cache_.MergeBatches(&tmp);
173 }
174 // Extract enough chunks from the quarantine to get below the max
175 // quarantine size and leave some leeway for the newly quarantined chunks.
176 while (cache_.Size() > min_size) {
177 tmp.EnqueueBatch(cache_.DequeueBatch());
178 }
179 }
180 recycle_mutex_.Unlock();
181 DoRecycle(&tmp, cb);
182 }
183
184 void NOINLINE DoRecycle(Cache *c, Callback cb) {
185 while (QuarantineBatch *b = c->DequeueBatch()) {
186 const uptr kPrefetch = 16;
187 CHECK(kPrefetch <= ARRAY_SIZE(b->batch));
188 for (uptr i = 0; i < kPrefetch; i++)
189 PREFETCH(b->batch[i]);
190 for (uptr i = 0, count = b->count; i < count; i++) {
191 if (i + kPrefetch < count)
192 PREFETCH(b->batch[i + kPrefetch]);
193 cb.Recycle((Node*)b->batch[i]);
194 }
195 cb.Deallocate(b);
196 }
197 }
198 };
199
200 // Per-thread cache of memory blocks.
201 template<typename Callback>
202 class QuarantineCache {
203 public:
204 explicit QuarantineCache(LinkerInitialized) {
205 }
206
207 QuarantineCache()
208 : size_() {
209 list_.clear();
210 }
211
212 // Total memory used, including internal accounting.
213 uptr Size() const {
214 return atomic_load_relaxed(&size_);
215 }
216
217 // Memory used for internal accounting.
218 uptr OverheadSize() const {
219 return list_.size() * sizeof(QuarantineBatch);
220 }
221
222 void Enqueue(Callback cb, void *ptr, uptr size) {
223 if (list_.empty() || list_.back()->count == QuarantineBatch::kSize) {
224 QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b));
225 CHECK(b);
226 b->init(ptr, size);
227 EnqueueBatch(b);
228 } else {
229 list_.back()->push_back(ptr, size);
230 SizeAdd(size);
231 }
232 }
233
234 void Transfer(QuarantineCache *from_cache) {
235 list_.append_back(&from_cache->list_);
236 SizeAdd(from_cache->Size());
237
238 atomic_store_relaxed(&from_cache->size_, 0);
239 }
240
241 void EnqueueBatch(QuarantineBatch *b) {
242 list_.push_back(b);
243 SizeAdd(b->size);
244 }
245
246 QuarantineBatch *DequeueBatch() {
247 if (list_.empty())
248 return nullptr;
249 QuarantineBatch *b = list_.front();
250 list_.pop_front();
251 SizeSub(b->size);
252 return b;
253 }
254
255 void MergeBatches(QuarantineCache *to_deallocate) {
256 uptr extracted_size = 0;
257 QuarantineBatch *current = list_.front();
258 while (current && current->next) {
259 if (current->can_merge(current->next)) {
260 QuarantineBatch *extracted = current->next;
261 // Move all the chunks into the current batch.
262 current->merge(extracted);
263 CHECK_EQ(extracted->count, 0);
264 CHECK_EQ(extracted->size, sizeof(QuarantineBatch));
265 // Remove the next batch from the list and account for its size.
266 list_.extract(current, extracted);
267 extracted_size += extracted->size;
268 // Add it to deallocation list.
269 to_deallocate->EnqueueBatch(extracted);
270 } else {
271 current = current->next;
272 }
273 }
274 SizeSub(extracted_size);
275 }
276
277 void PrintStats() const {
278 uptr batch_count = 0;
279 uptr total_overhead_bytes = 0;
280 uptr total_bytes = 0;
281 uptr total_quarantine_chunks = 0;
282 for (List::ConstIterator it = list_.begin(); it != list_.end(); ++it) {
283 batch_count++;
284 total_bytes += (*it).size;
285 total_overhead_bytes += (*it).size - (*it).quarantined_size();
286 total_quarantine_chunks += (*it).count;
287 }
288 uptr quarantine_chunks_capacity = batch_count * QuarantineBatch::kSize;
289 int chunks_usage_percent = quarantine_chunks_capacity == 0 ?
290 0 : total_quarantine_chunks * 100 / quarantine_chunks_capacity;
291 uptr total_quarantined_bytes = total_bytes - total_overhead_bytes;
292 int memory_overhead_percent = total_quarantined_bytes == 0 ?
293 0 : total_overhead_bytes * 100 / total_quarantined_bytes;
294 Printf("Global quarantine stats: batches: %zd; bytes: %zd (user: %zd); "
295 "chunks: %zd (capacity: %zd); %d%% chunks used; %d%% memory overhead"
296 "\n",
297 batch_count, total_bytes, total_quarantined_bytes,
298 total_quarantine_chunks, quarantine_chunks_capacity,
299 chunks_usage_percent, memory_overhead_percent);
300 }
301
302 private:
303 typedef IntrusiveList<QuarantineBatch> List;
304
305 List list_;
306 atomic_uintptr_t size_;
307
308 void SizeAdd(uptr add) {
309 atomic_store_relaxed(&size_, Size() + add);
310 }
311 void SizeSub(uptr sub) {
312 atomic_store_relaxed(&size_, Size() - sub);
313 }
314 };
315
316 } // namespace __sanitizer
317
318 #endif // SANITIZER_QUARANTINE_H