libsanitizer/sanitizer_common/sanitizer_quarantine.h

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