1//===-- sanitizer_quarantine.h ----------------------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 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. 14// 15//===----------------------------------------------------------------------===// 16 17#ifndef SANITIZER_QUARANTINE_H 18#define SANITIZER_QUARANTINE_H 19 20#include "sanitizer_internal_defs.h" 21#include "sanitizer_mutex.h" 22#include "sanitizer_list.h" 23 24namespace __sanitizer { 25 26template<typename Node> class QuarantineCache; 27 28struct QuarantineBatch { 29 static const uptr kSize = 1021; 30 QuarantineBatch *next; 31 uptr size; 32 uptr count; 33 void *batch[kSize]; 34}; 35 36COMPILER_CHECK(sizeof(QuarantineBatch) <= (1 << 13)); // 8Kb. 37 38// The callback interface is: 39// void Callback::Recycle(Node *ptr); 40// void *cb.Allocate(uptr size); 41// void cb.Deallocate(void *ptr); 42template<typename Callback, typename Node> 43class Quarantine { 44 public: 45 typedef QuarantineCache<Callback> Cache; 46 47 explicit Quarantine(LinkerInitialized) 48 : cache_(LINKER_INITIALIZED) { 49 } 50 51 void Init(uptr size, uptr cache_size) { 52 max_size_ = size; 53 min_size_ = size / 10 * 9; // 90% of max size. 54 max_cache_size_ = cache_size; 55 } 56 57 void Put(Cache *c, Callback cb, Node *ptr, uptr size) { 58 c->Enqueue(cb, ptr, size); 59 if (c->Size() > max_cache_size_) 60 Drain(c, cb); 61 } 62 63 void NOINLINE Drain(Cache *c, Callback cb) { 64 { 65 SpinMutexLock l(&cache_mutex_); 66 cache_.Transfer(c); 67 } 68 if (cache_.Size() > max_size_ && recycle_mutex_.TryLock()) 69 Recycle(cb); 70 } 71 72 private: 73 // Read-only data. 74 char pad0_[kCacheLineSize]; 75 uptr max_size_; 76 uptr min_size_; 77 uptr max_cache_size_; 78 char pad1_[kCacheLineSize]; 79 SpinMutex cache_mutex_; 80 SpinMutex recycle_mutex_; 81 Cache cache_; 82 char pad2_[kCacheLineSize]; 83 84 void NOINLINE Recycle(Callback cb) { 85 Cache tmp; 86 { 87 SpinMutexLock l(&cache_mutex_); 88 while (cache_.Size() > min_size_) { 89 QuarantineBatch *b = cache_.DequeueBatch(); 90 tmp.EnqueueBatch(b); 91 } 92 } 93 recycle_mutex_.Unlock(); 94 DoRecycle(&tmp, cb); 95 } 96 97 void NOINLINE DoRecycle(Cache *c, Callback cb) { 98 while (QuarantineBatch *b = c->DequeueBatch()) { 99 const uptr kPrefetch = 16; 100 for (uptr i = 0; i < kPrefetch; i++) 101 PREFETCH(b->batch[i]); 102 for (uptr i = 0; i < b->count; i++) { 103 PREFETCH(b->batch[i + kPrefetch]); 104 cb.Recycle((Node*)b->batch[i]); 105 } 106 cb.Deallocate(b); 107 } 108 } 109}; 110 111// Per-thread cache of memory blocks. 112template<typename Callback> 113class QuarantineCache { 114 public: 115 explicit QuarantineCache(LinkerInitialized) { 116 } 117 118 QuarantineCache() 119 : size_() { 120 list_.clear(); 121 } 122 123 uptr Size() const { 124 return atomic_load(&size_, memory_order_relaxed); 125 } 126 127 void Enqueue(Callback cb, void *ptr, uptr size) { 128 if (list_.empty() || list_.back()->count == QuarantineBatch::kSize) { 129 AllocBatch(cb); 130 size += sizeof(QuarantineBatch); // Count the batch in Quarantine size. 131 } 132 QuarantineBatch *b = list_.back(); 133 b->batch[b->count++] = ptr; 134 b->size += size; 135 SizeAdd(size); 136 } 137 138 void Transfer(QuarantineCache *c) { 139 list_.append_back(&c->list_); 140 SizeAdd(c->Size()); 141 atomic_store(&c->size_, 0, memory_order_relaxed); 142 } 143 144 void EnqueueBatch(QuarantineBatch *b) { 145 list_.push_back(b); 146 SizeAdd(b->size); 147 } 148 149 QuarantineBatch *DequeueBatch() { 150 if (list_.empty()) 151 return 0; 152 QuarantineBatch *b = list_.front(); 153 list_.pop_front(); 154 SizeSub(b->size); 155 return b; 156 } 157 158 private: 159 IntrusiveList<QuarantineBatch> list_; 160 atomic_uintptr_t size_; 161 162 void SizeAdd(uptr add) { 163 atomic_store(&size_, Size() + add, memory_order_relaxed); 164 } 165 void SizeSub(uptr sub) { 166 atomic_store(&size_, Size() - sub, memory_order_relaxed); 167 } 168 169 NOINLINE QuarantineBatch* AllocBatch(Callback cb) { 170 QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b)); 171 b->count = 0; 172 b->size = 0; 173 list_.push_back(b); 174 return b; 175 } 176}; 177} // namespace __sanitizer 178 179#endif // #ifndef SANITIZER_QUARANTINE_H 180