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

   1 //===-- sanitizer_allocator_local_cache.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 // Part of the Sanitizer Allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #ifndef SANITIZER_ALLOCATOR_H
  14 #error This file must be included inside sanitizer_allocator.h
  15 #endif
  16
  17 // Objects of this type should be used as local caches for SizeClassAllocator64
  18 // or SizeClassAllocator32. Since the typical use of this class is to have one
  19 // object per thread in TLS, is has to be POD.
  20 template<class SizeClassAllocator>
  21 struct SizeClassAllocatorLocalCache
  22     : SizeClassAllocator::AllocatorCache {
  23 };
  24
  25 // Cache used by SizeClassAllocator64.
  26 template <class SizeClassAllocator>
  27 struct SizeClassAllocator64LocalCache {
  28   typedef SizeClassAllocator Allocator;
  29
  30   void Init(AllocatorGlobalStats *s) {
  31     stats_.Init();
  32     if (s)
  33       s->Register(&stats_);
  34   }
  35
  36   void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) {
  37     Drain(allocator);
  38     if (s)
  39       s->Unregister(&stats_);
  40   }
  41
  42   void *Allocate(SizeClassAllocator *allocator, uptr class_id) {
  43     CHECK_NE(class_id, 0UL);
  44     CHECK_LT(class_id, kNumClasses);
  45     PerClass *c = &per_class_[class_id];
  46     if (UNLIKELY(c->count == 0)) {
  47       if (UNLIKELY(!Refill(c, allocator, class_id)))
  48         return nullptr;
  49     }
  50     stats_.Add(AllocatorStatAllocated, c->class_size);
  51     CHECK_GT(c->count, 0);
  52     CompactPtrT chunk = c->chunks[--c->count];
  53     void *res = reinterpret_cast<void *>(allocator->CompactPtrToPointer(
  54         allocator->GetRegionBeginBySizeClass(class_id), chunk));
  55     return res;
  56   }
  57
  58   void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) {
  59     CHECK_NE(class_id, 0UL);
  60     CHECK_LT(class_id, kNumClasses);
  61     // If the first allocator call on a new thread is a deallocation, then
  62     // max_count will be zero, leading to check failure.
  63     InitCache();
  64     PerClass *c = &per_class_[class_id];
  65     stats_.Sub(AllocatorStatAllocated, c->class_size);
  66     CHECK_NE(c->max_count, 0UL);
  67     if (UNLIKELY(c->count == c->max_count))
  68       Drain(c, allocator, class_id, c->max_count / 2);
  69     CompactPtrT chunk = allocator->PointerToCompactPtr(
  70         allocator->GetRegionBeginBySizeClass(class_id),
  71         reinterpret_cast<uptr>(p));
  72     c->chunks[c->count++] = chunk;
  73   }
  74
  75   void Drain(SizeClassAllocator *allocator) {
  76     for (uptr i = 0; i < kNumClasses; i++) {
  77       PerClass *c = &per_class_[i];
  78       while (c->count > 0)
  79         Drain(c, allocator, i, c->count);
  80     }
  81   }
  82
  83  private:
  84   typedef typename Allocator::SizeClassMapT SizeClassMap;
  85   static const uptr kNumClasses = SizeClassMap::kNumClasses;
  86   typedef typename Allocator::CompactPtrT CompactPtrT;
  87
  88   struct PerClass {
  89     u32 count;
  90     u32 max_count;
  91     uptr class_size;
  92     CompactPtrT chunks[2 * SizeClassMap::kMaxNumCachedHint];
  93   };
  94   PerClass per_class_[kNumClasses];
  95   AllocatorStats stats_;
  96
  97   void InitCache() {
  98     if (LIKELY(per_class_[1].max_count))
  99       return;
 100     for (uptr i = 0; i < kNumClasses; i++) {
 101       PerClass *c = &per_class_[i];
 102       c->max_count = 2 * SizeClassMap::MaxCachedHint(i);
 103       c->class_size = Allocator::ClassIdToSize(i);
 104     }
 105   }
 106
 107   NOINLINE bool Refill(PerClass *c, SizeClassAllocator *allocator,
 108                        uptr class_id) {
 109     InitCache();
 110     uptr num_requested_chunks = c->max_count / 2;
 111     if (UNLIKELY(!allocator->GetFromAllocator(&stats_, class_id, c->chunks,
 112                                               num_requested_chunks)))
 113       return false;
 114     c->count = num_requested_chunks;
 115     return true;
 116   }
 117
 118   NOINLINE void Drain(PerClass *c, SizeClassAllocator *allocator, uptr class_id,
 119                       uptr count) {
 120     InitCache();
 121     CHECK_GE(c->count, count);
 122     uptr first_idx_to_drain = c->count - count;
 123     c->count -= count;
 124     allocator->ReturnToAllocator(&stats_, class_id,
 125                                  &c->chunks[first_idx_to_drain], count);
 126   }
 127 };
 128
 129 // Cache used by SizeClassAllocator32.
 130 template <class SizeClassAllocator>
 131 struct SizeClassAllocator32LocalCache {
 132   typedef SizeClassAllocator Allocator;
 133   typedef typename Allocator::TransferBatch TransferBatch;
 134
 135   void Init(AllocatorGlobalStats *s) {
 136     stats_.Init();
 137     if (s)
 138       s->Register(&stats_);
 139   }
 140
 141   // Returns a TransferBatch suitable for class_id.
 142   TransferBatch *CreateBatch(uptr class_id, SizeClassAllocator *allocator,
 143                              TransferBatch *b) {
 144     if (uptr batch_class_id = per_class_[class_id].batch_class_id)
 145       return (TransferBatch*)Allocate(allocator, batch_class_id);
 146     return b;
 147   }
 148
 149   // Destroys TransferBatch b.
 150   void DestroyBatch(uptr class_id, SizeClassAllocator *allocator,
 151                     TransferBatch *b) {
 152     if (uptr batch_class_id = per_class_[class_id].batch_class_id)
 153       Deallocate(allocator, batch_class_id, b);
 154   }
 155
 156   void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) {
 157     Drain(allocator);
 158     if (s)
 159       s->Unregister(&stats_);
 160   }
 161
 162   void *Allocate(SizeClassAllocator *allocator, uptr class_id) {
 163     CHECK_NE(class_id, 0UL);
 164     CHECK_LT(class_id, kNumClasses);
 165     PerClass *c = &per_class_[class_id];
 166     if (UNLIKELY(c->count == 0)) {
 167       if (UNLIKELY(!Refill(allocator, class_id)))
 168         return nullptr;
 169     }
 170     stats_.Add(AllocatorStatAllocated, c->class_size);
 171     void *res = c->batch[--c->count];
 172     PREFETCH(c->batch[c->count - 1]);
 173     return res;
 174   }
 175
 176   void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) {
 177     CHECK_NE(class_id, 0UL);
 178     CHECK_LT(class_id, kNumClasses);
 179     // If the first allocator call on a new thread is a deallocation, then
 180     // max_count will be zero, leading to check failure.
 181     InitCache();
 182     PerClass *c = &per_class_[class_id];
 183     stats_.Sub(AllocatorStatAllocated, c->class_size);
 184     CHECK_NE(c->max_count, 0UL);
 185     if (UNLIKELY(c->count == c->max_count))
 186       Drain(allocator, class_id);
 187     c->batch[c->count++] = p;
 188   }
 189
 190   void Drain(SizeClassAllocator *allocator) {
 191     for (uptr i = 0; i < kNumClasses; i++) {
 192       PerClass *c = &per_class_[i];
 193       while (c->count > 0)
 194         Drain(allocator, i);
 195     }
 196   }
 197
 198  private:
 199   typedef typename Allocator::SizeClassMapT SizeClassMap;
 200   static const uptr kBatchClassID = SizeClassMap::kBatchClassID;
 201   static const uptr kNumClasses = SizeClassMap::kNumClasses;
 202   // If kUseSeparateSizeClassForBatch is true, all TransferBatch objects are
 203   // allocated from kBatchClassID size class (except for those that are needed
 204   // for kBatchClassID itself). The goal is to have TransferBatches in a totally
 205   // different region of RAM to improve security.
 206   static const bool kUseSeparateSizeClassForBatch =
 207       Allocator::kUseSeparateSizeClassForBatch;
 208
 209   struct PerClass {
 210     uptr count;
 211     uptr max_count;
 212     uptr class_size;
 213     uptr batch_class_id;
 214     void *batch[2 * TransferBatch::kMaxNumCached];
 215   };
 216   PerClass per_class_[kNumClasses];
 217   AllocatorStats stats_;
 218
 219   void InitCache() {
 220     if (LIKELY(per_class_[1].max_count))
 221       return;
 222     const uptr batch_class_id = SizeClassMap::ClassID(sizeof(TransferBatch));
 223     for (uptr i = 0; i < kNumClasses; i++) {
 224       PerClass *c = &per_class_[i];
 225       uptr max_cached = TransferBatch::MaxCached(i);
 226       c->max_count = 2 * max_cached;
 227       c->class_size = Allocator::ClassIdToSize(i);
 228       // Precompute the class id to use to store batches for the current class
 229       // id. 0 means the class size is large enough to store a batch within one
 230       // of the chunks. If using a separate size class, it will always be
 231       // kBatchClassID, except for kBatchClassID itself.
 232       if (kUseSeparateSizeClassForBatch) {
 233         c->batch_class_id = (i == kBatchClassID) ? 0 : kBatchClassID;
 234       } else {
 235         c->batch_class_id = (c->class_size <
 236           TransferBatch::AllocationSizeRequiredForNElements(max_cached)) ?
 237               batch_class_id : 0;
 238       }
 239     }
 240   }
 241
 242   NOINLINE bool Refill(SizeClassAllocator *allocator, uptr class_id) {
 243     InitCache();
 244     PerClass *c = &per_class_[class_id];
 245     TransferBatch *b = allocator->AllocateBatch(&stats_, this, class_id);
 246     if (UNLIKELY(!b))
 247       return false;
 248     CHECK_GT(b->Count(), 0);
 249     b->CopyToArray(c->batch);
 250     c->count = b->Count();
 251     DestroyBatch(class_id, allocator, b);
 252     return true;
 253   }
 254
 255   NOINLINE void Drain(SizeClassAllocator *allocator, uptr class_id) {
 256     InitCache();
 257     PerClass *c = &per_class_[class_id];
 258     uptr cnt = Min(c->max_count / 2, c->count);
 259     uptr first_idx_to_drain = c->count - cnt;
 260     TransferBatch *b = CreateBatch(
 261         class_id, allocator, (TransferBatch *)c->batch[first_idx_to_drain]);
 262     // Failure to allocate a batch while releasing memory is non recoverable.
 263     // TODO(alekseys): Figure out how to do it without allocating a new batch.
 264     if (UNLIKELY(!b))
 265       DieOnFailure::OnOOM();
 266     b->SetFromArray(allocator->GetRegionBeginBySizeClass(class_id),
 267                     &c->batch[first_idx_to_drain], cnt);
 268     c->count -= cnt;
 269     allocator->DeallocateBatch(&stats_, class_id, b);
 270   }
 271 };
 272