1 //===-- sanitizer_quarantine.h ----------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Memory quarantine for AddressSanitizer and potentially other tools.
11 // Quarantine caches some specified amount of memory in per-thread caches,
12 // then evicts to global FIFO queue. When the queue reaches specified threshold,
13 // oldest memory is recycled.
15 //===----------------------------------------------------------------------===//
17 #ifndef SANITIZER_QUARANTINE_H
18 #define SANITIZER_QUARANTINE_H
20 #include "sanitizer_internal_defs.h"
21 #include "sanitizer_mutex.h"
22 #include "sanitizer_list.h"
24 namespace __sanitizer {
26 template<typename Node> class QuarantineCache;
28 struct QuarantineBatch {
29 static const uptr kSize = 1021;
30 QuarantineBatch *next;
35 void init(void *ptr, uptr size) {
38 this->size = size + sizeof(QuarantineBatch); // Account for the batch size.
41 // The total size of quarantined nodes recorded in this batch.
42 uptr quarantined_size() const {
43 return size - sizeof(QuarantineBatch);
46 void push_back(void *ptr, uptr size) {
47 CHECK_LT(count, kSize);
52 bool can_merge(const QuarantineBatch* const from) const {
53 return count + from->count <= kSize;
56 void merge(QuarantineBatch* const from) {
57 CHECK_LE(count + from->count, kSize);
58 CHECK_GE(size, sizeof(QuarantineBatch));
60 for (uptr i = 0; i < from->count; ++i)
61 batch[count + i] = from->batch[i];
63 size += from->quarantined_size();
66 from->size = sizeof(QuarantineBatch);
70 COMPILER_CHECK(sizeof(QuarantineBatch) <= (1 << 13)); // 8Kb.
72 // The callback interface is:
73 // void Callback::Recycle(Node *ptr);
74 // void *cb.Allocate(uptr size);
75 // void cb.Deallocate(void *ptr);
76 template<typename Callback, typename Node>
79 typedef QuarantineCache<Callback> Cache;
81 explicit Quarantine(LinkerInitialized)
82 : cache_(LINKER_INITIALIZED) {
85 void Init(uptr size, uptr cache_size) {
86 // Thread local quarantine size can be zero only when global quarantine size
87 // is zero (it allows us to perform just one atomic read per Put() call).
88 CHECK((size == 0 && cache_size == 0) || cache_size != 0);
90 atomic_store(&max_size_, size, memory_order_relaxed);
91 atomic_store(&min_size_, size / 10 * 9,
92 memory_order_relaxed); // 90% of max size.
93 atomic_store(&max_cache_size_, cache_size, memory_order_relaxed);
96 uptr GetSize() const { return atomic_load(&max_size_, memory_order_relaxed); }
97 uptr GetCacheSize() const {
98 return atomic_load(&max_cache_size_, memory_order_relaxed);
101 void Put(Cache *c, Callback cb, Node *ptr, uptr size) {
102 uptr cache_size = GetCacheSize();
104 c->Enqueue(cb, ptr, size);
106 // GetCacheSize() == 0 only when GetSize() == 0 (see Init).
109 // Check cache size anyway to accommodate for runtime cache_size change.
110 if (c->Size() > cache_size)
114 void NOINLINE Drain(Cache *c, Callback cb) {
116 SpinMutexLock l(&cache_mutex_);
119 if (cache_.Size() > GetSize() && recycle_mutex_.TryLock())
123 void PrintStats() const {
124 // It assumes that the world is stopped, just as the allocator's PrintStats.
125 Printf("Quarantine limits: global: %zdMb; thread local: %zdKb\n",
126 GetSize() >> 20, GetCacheSize() >> 10);
132 char pad0_[kCacheLineSize];
133 atomic_uintptr_t max_size_;
134 atomic_uintptr_t min_size_;
135 atomic_uintptr_t max_cache_size_;
136 char pad1_[kCacheLineSize];
137 SpinMutex cache_mutex_;
138 SpinMutex recycle_mutex_;
140 char pad2_[kCacheLineSize];
142 void NOINLINE Recycle(Callback cb) {
144 uptr min_size = atomic_load(&min_size_, memory_order_relaxed);
146 SpinMutexLock l(&cache_mutex_);
147 // Go over the batches and merge partially filled ones to
148 // save some memory, otherwise batches themselves (since the memory used
149 // by them is counted against quarantine limit) can overcome the actual
150 // user's quarantined chunks, which diminishes the purpose of the
152 uptr cache_size = cache_.Size();
153 uptr overhead_size = cache_.OverheadSize();
154 CHECK_GE(cache_size, overhead_size);
155 // Do the merge only when overhead exceeds this predefined limit (might
156 // require some tuning). It saves us merge attempt when the batch list
157 // quarantine is unlikely to contain batches suitable for merge.
158 const uptr kOverheadThresholdPercents = 100;
159 if (cache_size > overhead_size &&
160 overhead_size * (100 + kOverheadThresholdPercents) >
161 cache_size * kOverheadThresholdPercents) {
162 cache_.MergeBatches(&tmp);
164 // Extract enough chunks from the quarantine to get below the max
165 // quarantine size and leave some leeway for the newly quarantined chunks.
166 while (cache_.Size() > min_size) {
167 tmp.EnqueueBatch(cache_.DequeueBatch());
170 recycle_mutex_.Unlock();
174 void NOINLINE DoRecycle(Cache *c, Callback cb) {
175 while (QuarantineBatch *b = c->DequeueBatch()) {
176 const uptr kPrefetch = 16;
177 CHECK(kPrefetch <= ARRAY_SIZE(b->batch));
178 for (uptr i = 0; i < kPrefetch; i++)
179 PREFETCH(b->batch[i]);
180 for (uptr i = 0, count = b->count; i < count; i++) {
181 if (i + kPrefetch < count)
182 PREFETCH(b->batch[i + kPrefetch]);
183 cb.Recycle((Node*)b->batch[i]);
190 // Per-thread cache of memory blocks.
191 template<typename Callback>
192 class QuarantineCache {
194 explicit QuarantineCache(LinkerInitialized) {
202 // Total memory used, including internal accounting.
204 return atomic_load(&size_, memory_order_relaxed);
207 // Memory used for internal accounting.
208 uptr OverheadSize() const {
209 return list_.size() * sizeof(QuarantineBatch);
212 void Enqueue(Callback cb, void *ptr, uptr size) {
213 if (list_.empty() || list_.back()->count == QuarantineBatch::kSize) {
214 QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b));
219 list_.back()->push_back(ptr, size);
224 void Transfer(QuarantineCache *from_cache) {
225 list_.append_back(&from_cache->list_);
226 SizeAdd(from_cache->Size());
228 atomic_store(&from_cache->size_, 0, memory_order_relaxed);
231 void EnqueueBatch(QuarantineBatch *b) {
236 QuarantineBatch *DequeueBatch() {
239 QuarantineBatch *b = list_.front();
245 void MergeBatches(QuarantineCache *to_deallocate) {
246 uptr extracted_size = 0;
247 QuarantineBatch *current = list_.front();
248 while (current && current->next) {
249 if (current->can_merge(current->next)) {
250 QuarantineBatch *extracted = current->next;
251 // Move all the chunks into the current batch.
252 current->merge(extracted);
253 CHECK_EQ(extracted->count, 0);
254 CHECK_EQ(extracted->size, sizeof(QuarantineBatch));
255 // Remove the next batch from the list and account for its size.
256 list_.extract(current, extracted);
257 extracted_size += extracted->size;
258 // Add it to deallocation list.
259 to_deallocate->EnqueueBatch(extracted);
261 current = current->next;
264 SizeSub(extracted_size);
267 void PrintStats() const {
268 uptr batch_count = 0;
269 uptr total_overhead_bytes = 0;
270 uptr total_bytes = 0;
271 uptr total_quarantine_chunks = 0;
272 for (List::ConstIterator it = list_.begin(); it != list_.end(); ++it) {
274 total_bytes += (*it).size;
275 total_overhead_bytes += (*it).size - (*it).quarantined_size();
276 total_quarantine_chunks += (*it).count;
278 uptr quarantine_chunks_capacity = batch_count * QuarantineBatch::kSize;
279 int chunks_usage_percent = quarantine_chunks_capacity == 0 ?
280 0 : total_quarantine_chunks * 100 / quarantine_chunks_capacity;
281 uptr total_quarantined_bytes = total_bytes - total_overhead_bytes;
282 int memory_overhead_percent = total_quarantined_bytes == 0 ?
283 0 : total_overhead_bytes * 100 / total_quarantined_bytes;
284 Printf("Global quarantine stats: batches: %zd; bytes: %zd (user: %zd); "
285 "chunks: %zd (capacity: %zd); %d%% chunks used; %d%% memory overhead"
287 batch_count, total_bytes, total_quarantined_bytes,
288 total_quarantine_chunks, quarantine_chunks_capacity,
289 chunks_usage_percent, memory_overhead_percent);
293 typedef IntrusiveList<QuarantineBatch> List;
296 atomic_uintptr_t size_;
298 void SizeAdd(uptr add) {
299 atomic_store(&size_, Size() + add, memory_order_relaxed);
301 void SizeSub(uptr sub) {
302 atomic_store(&size_, Size() - sub, memory_order_relaxed);
306 } // namespace __sanitizer
308 #endif // SANITIZER_QUARANTINE_H