19fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov//===-- sanitizer_quarantine.h ----------------------------------*- C++ -*-===// 29fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// 39fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// The LLVM Compiler Infrastructure 49fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// 59fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// This file is distributed under the University of Illinois Open Source 69fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// License. See LICENSE.TXT for details. 79fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// 89fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov//===----------------------------------------------------------------------===// 99fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// 109fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// Memory quarantine for AddressSanitizer and potentially other tools. 119fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// Quarantine caches some specified amount of memory in per-thread caches, 129fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// then evicts to global FIFO queue. When the queue reaches specified threshold, 139fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// oldest memory is recycled. 149fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// 159fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov//===----------------------------------------------------------------------===// 169fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 179fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov#ifndef SANITIZER_QUARANTINE_H 189fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov#define SANITIZER_QUARANTINE_H 199fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 209fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov#include "sanitizer_internal_defs.h" 219fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov#include "sanitizer_mutex.h" 22a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov#include "sanitizer_list.h" 239fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 249fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukovnamespace __sanitizer { 259fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 269fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukovtemplate<typename Node> class QuarantineCache; 279fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 28a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukovstruct QuarantineBatch { 29a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany static const uptr kSize = 1021; 30a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *next; 31a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov uptr size; 32a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov uptr count; 33a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void *batch[kSize]; 34a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov}; 35a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 36a650de81e9ce919edc876728fce7c1f4cdc4abccKostya SerebryanyCOMPILER_CHECK(sizeof(QuarantineBatch) <= (1 << 13)); // 8Kb. 37a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany 389fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// The callback interface is: 39a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov// void Callback::Recycle(Node *ptr); 40a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov// void *cb.Allocate(uptr size); 41a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov// void cb.Deallocate(void *ptr); 429fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukovtemplate<typename Callback, typename Node> 439fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukovclass Quarantine { 449fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov public: 45a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov typedef QuarantineCache<Callback> Cache; 469fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 479fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov explicit Quarantine(LinkerInitialized) 489fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov : cache_(LINKER_INITIALIZED) { 499fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 509fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 519fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov void Init(uptr size, uptr cache_size) { 5286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines atomic_store(&max_size_, size, memory_order_release); 5386277eb844c4983c81de62d7c050e92fe7155788Stephen Hines atomic_store(&min_size_, size / 10 * 9, 5486277eb844c4983c81de62d7c050e92fe7155788Stephen Hines memory_order_release); // 90% of max size. 559fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov max_cache_size_ = cache_size; 569fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 579fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 5886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines uptr GetSize() const { return atomic_load(&max_size_, memory_order_acquire); } 5986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines 60a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void Put(Cache *c, Callback cb, Node *ptr, uptr size) { 61a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov c->Enqueue(cb, ptr, size); 629fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov if (c->Size() > max_cache_size_) 639fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov Drain(c, cb); 649fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 659fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 66a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void NOINLINE Drain(Cache *c, Callback cb) { 67a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov { 68a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SpinMutexLock l(&cache_mutex_); 69a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov cache_.Transfer(c); 70a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 7186277eb844c4983c81de62d7c050e92fe7155788Stephen Hines if (cache_.Size() > GetSize() && recycle_mutex_.TryLock()) 72f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov Recycle(cb); 739fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 749fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 759fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov private: 76a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov // Read-only data. 77a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov char pad0_[kCacheLineSize]; 7886277eb844c4983c81de62d7c050e92fe7155788Stephen Hines atomic_uintptr_t max_size_; 7986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines atomic_uintptr_t min_size_; 809fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov uptr max_cache_size_; 81a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov char pad1_[kCacheLineSize]; 82a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SpinMutex cache_mutex_; 83a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SpinMutex recycle_mutex_; 849fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov Cache cache_; 85a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov char pad2_[kCacheLineSize]; 86f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov 87f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov void NOINLINE Recycle(Callback cb) { 88f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov Cache tmp; 8986277eb844c4983c81de62d7c050e92fe7155788Stephen Hines uptr min_size = atomic_load(&min_size_, memory_order_acquire); 90f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov { 91f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov SpinMutexLock l(&cache_mutex_); 9286277eb844c4983c81de62d7c050e92fe7155788Stephen Hines while (cache_.Size() > min_size) { 93f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov QuarantineBatch *b = cache_.DequeueBatch(); 94f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov tmp.EnqueueBatch(b); 95f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov } 96f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov } 97f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov recycle_mutex_.Unlock(); 98f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov DoRecycle(&tmp, cb); 99f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov } 100f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov 101f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov void NOINLINE DoRecycle(Cache *c, Callback cb) { 102f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov while (QuarantineBatch *b = c->DequeueBatch()) { 103f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov const uptr kPrefetch = 16; 104f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov for (uptr i = 0; i < kPrefetch; i++) 105f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov PREFETCH(b->batch[i]); 106f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov for (uptr i = 0; i < b->count; i++) { 107f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov PREFETCH(b->batch[i + kPrefetch]); 108f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov cb.Recycle((Node*)b->batch[i]); 109f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov } 110f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov cb.Deallocate(b); 111f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov } 112f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov } 1139fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov}; 1149fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 115a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov// Per-thread cache of memory blocks. 116a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukovtemplate<typename Callback> 1179fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukovclass QuarantineCache { 1189fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov public: 1199fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov explicit QuarantineCache(LinkerInitialized) { 1209fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 1219fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 122a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineCache() 123a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov : size_() { 124a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.clear(); 125a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 126a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 1279fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov uptr Size() const { 128a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov return atomic_load(&size_, memory_order_relaxed); 129a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 130a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 131a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void Enqueue(Callback cb, void *ptr, uptr size) { 132a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany if (list_.empty() || list_.back()->count == QuarantineBatch::kSize) { 133a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov AllocBatch(cb); 134a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany size += sizeof(QuarantineBatch); // Count the batch in Quarantine size. 135a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany } 136a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *b = list_.back(); 13786277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(b); 138a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov b->batch[b->count++] = ptr; 139a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov b->size += size; 140a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SizeAdd(size); 1419fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 1429fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 143a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void Transfer(QuarantineCache *c) { 144a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.append_back(&c->list_); 145a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SizeAdd(c->Size()); 146a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov atomic_store(&c->size_, 0, memory_order_relaxed); 1479fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 1489fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 149a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void EnqueueBatch(QuarantineBatch *b) { 150a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.push_back(b); 151a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SizeAdd(b->size); 152a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 153a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 154a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *DequeueBatch() { 155a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov if (list_.empty()) 1569fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov return 0; 157a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *b = list_.front(); 158a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.pop_front(); 159a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany SizeSub(b->size); 160a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov return b; 1619fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 1629fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 1639fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov private: 164a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov IntrusiveList<QuarantineBatch> list_; 165a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov atomic_uintptr_t size_; 166a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 167a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void SizeAdd(uptr add) { 168a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov atomic_store(&size_, Size() + add, memory_order_relaxed); 169a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 170a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany void SizeSub(uptr sub) { 171a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany atomic_store(&size_, Size() - sub, memory_order_relaxed); 172a650de81e9ce919edc876728fce7c1f4cdc4abccKostya Serebryany } 173a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 1742b10d3944d911c07f2a10cf248300260ed67454aTimur Iskhodzhanov NOINLINE QuarantineBatch* AllocBatch(Callback cb) { 175a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b)); 17686277eb844c4983c81de62d7c050e92fe7155788Stephen Hines CHECK(b); 177a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov b->count = 0; 178a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov b->size = 0; 179a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.push_back(b); 180a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov return b; 181a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 1829fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov}; 183ba5e99668e3030cc5bab357a04271a1bdbac209cAlexey Samsonov} // namespace __sanitizer 1849fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 1859fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov#endif // #ifndef SANITIZER_QUARANTINE_H 186