contrib/compiler-rt/lib/sanitizer_common/sanitizer_quarantine.h

   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
  24 namespace __sanitizer {
  25
  26 template<typename Node> class QuarantineCache;
  27
  28 struct QuarantineBatch {
  29   static const uptr kSize = 1021;
  30   QuarantineBatch *next;
  31   uptr size;
  32   uptr count;
  33   void *batch[kSize];
  34 };
  35
  36 COMPILER_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);
  42 template<typename Callback, typename Node>
  43 class 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     atomic_store(&max_size_, size, memory_order_release);
  53     atomic_store(&min_size_, size / 10 * 9,
  54                  memory_order_release); // 90% of max size.
  55     max_cache_size_ = cache_size;
  56   }
  57
  58   uptr GetSize() const { return atomic_load(&max_size_, memory_order_acquire); }
  59
  60   void Put(Cache *c, Callback cb, Node *ptr, uptr size) {
  61     c->Enqueue(cb, ptr, size);
  62     if (c->Size() > max_cache_size_)
  63       Drain(c, cb);
  64   }
  65
  66   void NOINLINE Drain(Cache *c, Callback cb) {
  67     {
  68       SpinMutexLock l(&cache_mutex_);
  69       cache_.Transfer(c);
  70     }
  71     if (cache_.Size() > GetSize() && recycle_mutex_.TryLock())
  72       Recycle(cb);
  73   }
  74
  75  private:
  76   // Read-only data.
  77   char pad0_[kCacheLineSize];
  78   atomic_uintptr_t max_size_;
  79   atomic_uintptr_t min_size_;
  80   uptr max_cache_size_;
  81   char pad1_[kCacheLineSize];
  82   SpinMutex cache_mutex_;
  83   SpinMutex recycle_mutex_;
  84   Cache cache_;
  85   char pad2_[kCacheLineSize];
  86
  87   void NOINLINE Recycle(Callback cb) {
  88     Cache tmp;
  89     uptr min_size = atomic_load(&min_size_, memory_order_acquire);
  90     {
  91       SpinMutexLock l(&cache_mutex_);
  92       while (cache_.Size() > min_size) {
  93         QuarantineBatch *b = cache_.DequeueBatch();
  94         tmp.EnqueueBatch(b);
  95       }
  96     }
  97     recycle_mutex_.Unlock();
  98     DoRecycle(&tmp, cb);
  99   }
 100
 101   void NOINLINE DoRecycle(Cache *c, Callback cb) {
 102     while (QuarantineBatch *b = c->DequeueBatch()) {
 103       const uptr kPrefetch = 16;
 104       CHECK(kPrefetch <= ARRAY_SIZE(b->batch));
 105       for (uptr i = 0; i < kPrefetch; i++)
 106         PREFETCH(b->batch[i]);
 107       for (uptr i = 0, count = b->count; i < count; i++) {
 108         if (i + kPrefetch < count)
 109           PREFETCH(b->batch[i + kPrefetch]);
 110         cb.Recycle((Node*)b->batch[i]);
 111       }
 112       cb.Deallocate(b);
 113     }
 114   }
 115 };
 116
 117 // Per-thread cache of memory blocks.
 118 template<typename Callback>
 119 class QuarantineCache {
 120  public:
 121   explicit QuarantineCache(LinkerInitialized) {
 122   }
 123
 124   QuarantineCache()
 125       : size_() {
 126     list_.clear();
 127   }
 128
 129   uptr Size() const {
 130     return atomic_load(&size_, memory_order_relaxed);
 131   }
 132
 133   void Enqueue(Callback cb, void *ptr, uptr size) {
 134     if (list_.empty() || list_.back()->count == QuarantineBatch::kSize) {
 135       AllocBatch(cb);
 136       size += sizeof(QuarantineBatch);  // Count the batch in Quarantine size.
 137     }
 138     QuarantineBatch *b = list_.back();
 139     CHECK(b);
 140     b->batch[b->count++] = ptr;
 141     b->size += size;
 142     SizeAdd(size);
 143   }
 144
 145   void Transfer(QuarantineCache *c) {
 146     list_.append_back(&c->list_);
 147     SizeAdd(c->Size());
 148     atomic_store(&c->size_, 0, memory_order_relaxed);
 149   }
 150
 151   void EnqueueBatch(QuarantineBatch *b) {
 152     list_.push_back(b);
 153     SizeAdd(b->size);
 154   }
 155
 156   QuarantineBatch *DequeueBatch() {
 157     if (list_.empty())
 158       return nullptr;
 159     QuarantineBatch *b = list_.front();
 160     list_.pop_front();
 161     SizeSub(b->size);
 162     return b;
 163   }
 164
 165  private:
 166   IntrusiveList<QuarantineBatch> list_;
 167   atomic_uintptr_t size_;
 168
 169   void SizeAdd(uptr add) {
 170     atomic_store(&size_, Size() + add, memory_order_relaxed);
 171   }
 172   void SizeSub(uptr sub) {
 173     atomic_store(&size_, Size() - sub, memory_order_relaxed);
 174   }
 175
 176   NOINLINE QuarantineBatch* AllocBatch(Callback cb) {
 177     QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b));
 178     CHECK(b);
 179     b->count = 0;
 180     b->size = 0;
 181     list_.push_back(b);
 182     return b;
 183   }
 184 };
 185 } // namespace __sanitizer
 186
 187 #endif // SANITIZER_QUARANTINE_H