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 { 29a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov static const uptr kSize = 1024; 30a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *next; 31a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov uptr size; 32a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov uptr count; 33a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void *batch[kSize]; 34a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov}; 35a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 369fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov// The callback interface is: 37a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov// void Callback::Recycle(Node *ptr); 38a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov// void *cb.Allocate(uptr size); 39a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov// void cb.Deallocate(void *ptr); 409fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukovtemplate<typename Callback, typename Node> 419fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukovclass Quarantine { 429fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov public: 43a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov typedef QuarantineCache<Callback> Cache; 449fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 459fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov explicit Quarantine(LinkerInitialized) 469fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov : cache_(LINKER_INITIALIZED) { 479fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 489fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 499fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov void Init(uptr size, uptr cache_size) { 509fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov max_size_ = size; 51a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov min_size_ = size / 10 * 9; // 90% of max size. 529fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov max_cache_size_ = cache_size; 539fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 549fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 55a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void Put(Cache *c, Callback cb, Node *ptr, uptr size) { 56a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov c->Enqueue(cb, ptr, size); 579fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov if (c->Size() > max_cache_size_) 589fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov Drain(c, cb); 599fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 609fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 61a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void NOINLINE Drain(Cache *c, Callback cb) { 62a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov { 63a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SpinMutexLock l(&cache_mutex_); 64a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov cache_.Transfer(c); 65a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 66f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov if (cache_.Size() > max_size_ && recycle_mutex_.TryLock()) 67f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov Recycle(cb); 689fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 699fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 709fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov private: 71a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov // Read-only data. 72a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov char pad0_[kCacheLineSize]; 739fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov uptr max_size_; 74a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov uptr min_size_; 759fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov uptr max_cache_size_; 76a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov char pad1_[kCacheLineSize]; 77a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SpinMutex cache_mutex_; 78a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SpinMutex recycle_mutex_; 799fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov Cache cache_; 80a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov char pad2_[kCacheLineSize]; 81f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov 82f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov void NOINLINE Recycle(Callback cb) { 83f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov Cache tmp; 84f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov { 85f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov SpinMutexLock l(&cache_mutex_); 86f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov while (cache_.Size() > min_size_) { 87f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov QuarantineBatch *b = cache_.DequeueBatch(); 88f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov tmp.EnqueueBatch(b); 89f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov } 90f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov } 91f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov recycle_mutex_.Unlock(); 92f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov DoRecycle(&tmp, cb); 93f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov } 94f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov 95f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov void NOINLINE DoRecycle(Cache *c, Callback cb) { 96f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov while (QuarantineBatch *b = c->DequeueBatch()) { 97f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov const uptr kPrefetch = 16; 98f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov for (uptr i = 0; i < kPrefetch; i++) 99f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov PREFETCH(b->batch[i]); 100f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov for (uptr i = 0; i < b->count; i++) { 101f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov PREFETCH(b->batch[i + kPrefetch]); 102f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov cb.Recycle((Node*)b->batch[i]); 103f99b94e19022f473b8de15a793801fd5deb5ba7eDmitry Vyukov } 104f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov cb.Deallocate(b); 105f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov } 106f79419553c6a636a4304cd40bda3e6d581e6137eDmitry Vyukov } 1079fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov}; 1089fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 109a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov// Per-thread cache of memory blocks. 110a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukovtemplate<typename Callback> 1119fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukovclass QuarantineCache { 1129fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov public: 1139fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov explicit QuarantineCache(LinkerInitialized) { 1149fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 1159fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 116a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineCache() 117a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov : size_() { 118a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.clear(); 119a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 120a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 1219fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov uptr Size() const { 122a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov return atomic_load(&size_, memory_order_relaxed); 123a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 124a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 125a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void Enqueue(Callback cb, void *ptr, uptr size) { 126a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov if (list_.empty() || list_.back()->count == QuarantineBatch::kSize) 127a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov AllocBatch(cb); 128a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *b = list_.back(); 129a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov b->batch[b->count++] = ptr; 130a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov b->size += size; 131a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SizeAdd(size); 1329fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 1339fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 134a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void Transfer(QuarantineCache *c) { 135a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.append_back(&c->list_); 136a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SizeAdd(c->Size()); 137a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov atomic_store(&c->size_, 0, memory_order_relaxed); 1389fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 1399fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 140a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void EnqueueBatch(QuarantineBatch *b) { 141a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.push_back(b); 142a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov SizeAdd(b->size); 143a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 144a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 145a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *DequeueBatch() { 146a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov if (list_.empty()) 1479fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov return 0; 148a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *b = list_.front(); 149a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.pop_front(); 150e174cd1ee373c3b77f3ce8e7fc62f70d0668d03dTimur Iskhodzhanov // FIXME: should probably add SizeSub method? 151e174cd1ee373c3b77f3ce8e7fc62f70d0668d03dTimur Iskhodzhanov // See https://code.google.com/p/thread-sanitizer/issues/detail?id=20 152e174cd1ee373c3b77f3ce8e7fc62f70d0668d03dTimur Iskhodzhanov SizeAdd(0 - b->size); 153a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov return b; 1549fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov } 1559fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 1569fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov private: 157a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov IntrusiveList<QuarantineBatch> list_; 158a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov atomic_uintptr_t size_; 159a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 160a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov void SizeAdd(uptr add) { 161a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov atomic_store(&size_, Size() + add, memory_order_relaxed); 162a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 163a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov 1642b10d3944d911c07f2a10cf248300260ed67454aTimur Iskhodzhanov NOINLINE QuarantineBatch* AllocBatch(Callback cb) { 165a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b)); 166a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov b->count = 0; 167a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov b->size = 0; 168a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov list_.push_back(b); 169a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov return b; 170a61ec8172611a75d80e86355352c7b2dd3cb8125Dmitry Vyukov } 1719fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov}; 172ba5e99668e3030cc5bab357a04271a1bdbac209cAlexey Samsonov} // namespace __sanitizer 1739fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov 1749fc0df892cab8735e7de0e86e995a3202c42cf82Dmitry Vyukov#endif // #ifndef SANITIZER_QUARANTINE_H 175