• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 = 1024;
30   QuarantineBatch *next;
31   uptr size;
32   uptr count;
33   void *batch[kSize];
34 };
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 
Quarantine(LinkerInitialized)45   explicit Quarantine(LinkerInitialized)
46       : cache_(LINKER_INITIALIZED) {
47   }
48 
Init(uptr size,uptr cache_size)49   void Init(uptr size, uptr cache_size) {
50     max_size_ = size;
51     min_size_ = size / 10 * 9;  // 90% of max size.
52     max_cache_size_ = cache_size;
53   }
54 
Put(Cache * c,Callback cb,Node * ptr,uptr size)55   void Put(Cache *c, Callback cb, Node *ptr, uptr size) {
56     c->Enqueue(cb, ptr, size);
57     if (c->Size() > max_cache_size_)
58       Drain(c, cb);
59   }
60 
Drain(Cache * c,Callback cb)61   void NOINLINE Drain(Cache *c, Callback cb) {
62     {
63       SpinMutexLock l(&cache_mutex_);
64       cache_.Transfer(c);
65     }
66     if (cache_.Size() > max_size_ && recycle_mutex_.TryLock())
67       Recycle(cb);
68   }
69 
70  private:
71   // Read-only data.
72   char pad0_[kCacheLineSize];
73   uptr max_size_;
74   uptr min_size_;
75   uptr max_cache_size_;
76   char pad1_[kCacheLineSize];
77   SpinMutex cache_mutex_;
78   SpinMutex recycle_mutex_;
79   Cache cache_;
80   char pad2_[kCacheLineSize];
81 
Recycle(Callback cb)82   void NOINLINE Recycle(Callback cb) {
83     Cache tmp;
84     {
85       SpinMutexLock l(&cache_mutex_);
86       while (cache_.Size() > min_size_) {
87         QuarantineBatch *b = cache_.DequeueBatch();
88         tmp.EnqueueBatch(b);
89       }
90     }
91     recycle_mutex_.Unlock();
92     DoRecycle(&tmp, cb);
93   }
94 
DoRecycle(Cache * c,Callback cb)95   void NOINLINE DoRecycle(Cache *c, Callback cb) {
96     while (QuarantineBatch *b = c->DequeueBatch()) {
97       const uptr kPrefetch = 16;
98       for (uptr i = 0; i < kPrefetch; i++)
99         PREFETCH(b->batch[i]);
100       for (uptr i = 0; i < b->count; i++) {
101         PREFETCH(b->batch[i + kPrefetch]);
102         cb.Recycle((Node*)b->batch[i]);
103       }
104       cb.Deallocate(b);
105     }
106   }
107 };
108 
109 // Per-thread cache of memory blocks.
110 template<typename Callback>
111 class QuarantineCache {
112  public:
QuarantineCache(LinkerInitialized)113   explicit QuarantineCache(LinkerInitialized) {
114   }
115 
QuarantineCache()116   QuarantineCache()
117       : size_() {
118     list_.clear();
119   }
120 
Size()121   uptr Size() const {
122     return atomic_load(&size_, memory_order_relaxed);
123   }
124 
Enqueue(Callback cb,void * ptr,uptr size)125   void Enqueue(Callback cb, void *ptr, uptr size) {
126     if (list_.empty() || list_.back()->count == QuarantineBatch::kSize)
127       AllocBatch(cb);
128     QuarantineBatch *b = list_.back();
129     b->batch[b->count++] = ptr;
130     b->size += size;
131     SizeAdd(size);
132   }
133 
Transfer(QuarantineCache * c)134   void Transfer(QuarantineCache *c) {
135     list_.append_back(&c->list_);
136     SizeAdd(c->Size());
137     atomic_store(&c->size_, 0, memory_order_relaxed);
138   }
139 
EnqueueBatch(QuarantineBatch * b)140   void EnqueueBatch(QuarantineBatch *b) {
141     list_.push_back(b);
142     SizeAdd(b->size);
143   }
144 
DequeueBatch()145   QuarantineBatch *DequeueBatch() {
146     if (list_.empty())
147       return 0;
148     QuarantineBatch *b = list_.front();
149     list_.pop_front();
150     // FIXME: should probably add SizeSub method?
151     // See https://code.google.com/p/thread-sanitizer/issues/detail?id=20
152     SizeAdd(0 - b->size);
153     return b;
154   }
155 
156  private:
157   IntrusiveList<QuarantineBatch> list_;
158   atomic_uintptr_t size_;
159 
SizeAdd(uptr add)160   void SizeAdd(uptr add) {
161     atomic_store(&size_, Size() + add, memory_order_relaxed);
162   }
163 
AllocBatch(Callback cb)164   NOINLINE QuarantineBatch* AllocBatch(Callback cb) {
165     QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b));
166     b->count = 0;
167     b->size = 0;
168     list_.push_back(b);
169     return b;
170   }
171 };
172 }  // namespace __sanitizer
173 
174 #endif  // #ifndef SANITIZER_QUARANTINE_H
175