Home | History | Annotate | Download | only in sanitizer_common 
      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
    188