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