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   static const uptr kNumClasses = SizeClassAllocator::kNumClasses;
  30   typedef typename Allocator::SizeClassMapT SizeClassMap;
  31   typedef typename Allocator::CompactPtrT CompactPtrT;
  32
  33   void Init(AllocatorGlobalStats *s) {
  34     stats_.Init();
  35     if (s)
  36       s->Register(&stats_);
  37   }
  38
  39   void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) {
  40     Drain(allocator);
  41     if (s)
  42       s->Unregister(&stats_);
  43   }
  44
  45   void *Allocate(SizeClassAllocator *allocator, uptr class_id) {
  46     CHECK_NE(class_id, 0UL);
  47     CHECK_LT(class_id, kNumClasses);
  48     PerClass *c = &per_class_[class_id];
  49     if (UNLIKELY(c->count == 0)) {
  50       if (UNLIKELY(!Refill(c, allocator, class_id)))
  51         return nullptr;
  52     }
  53     stats_.Add(AllocatorStatAllocated, c->class_size);
  54     CHECK_GT(c->count, 0);
  55     CompactPtrT chunk = c->chunks[--c->count];
  56     void *res = reinterpret_cast<void *>(allocator->CompactPtrToPointer(
  57         allocator->GetRegionBeginBySizeClass(class_id), chunk));
  58     return res;
  59   }
  60
  61   void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) {
  62     CHECK_NE(class_id, 0UL);
  63     CHECK_LT(class_id, kNumClasses);
  64     // If the first allocator call on a new thread is a deallocation, then
  65     // max_count will be zero, leading to check failure.
  66     InitCache();
  67     PerClass *c = &per_class_[class_id];
  68     stats_.Sub(AllocatorStatAllocated, c->class_size);
  69     CHECK_NE(c->max_count, 0UL);
  70     if (UNLIKELY(c->count == c->max_count))
  71       Drain(c, allocator, class_id, c->max_count / 2);
  72     CompactPtrT chunk = allocator->PointerToCompactPtr(
  73         allocator->GetRegionBeginBySizeClass(class_id),
  74         reinterpret_cast<uptr>(p));
  75     c->chunks[c->count++] = chunk;
  76   }
  77
  78   void Drain(SizeClassAllocator *allocator) {
  79     for (uptr class_id = 0; class_id < kNumClasses; class_id++) {
  80       PerClass *c = &per_class_[class_id];
  81       while (c->count > 0)
  82         Drain(c, allocator, class_id, c->count);
  83     }
  84   }
  85
  86   // private:
  87   struct PerClass {
  88     u32 count;
  89     u32 max_count;
  90     uptr class_size;
  91     CompactPtrT chunks[2 * SizeClassMap::kMaxNumCachedHint];
  92   };
  93   PerClass per_class_[kNumClasses];
  94   AllocatorStats stats_;
  95
  96   void InitCache() {
  97     if (per_class_[1].max_count)
  98       return;
  99     for (uptr i = 0; i < kNumClasses; i++) {
 100       PerClass *c = &per_class_[i];
 101       c->max_count = 2 * SizeClassMap::MaxCachedHint(i);
 102       c->class_size = Allocator::ClassIdToSize(i);
 103     }
 104   }
 105
 106   NOINLINE bool Refill(PerClass *c, SizeClassAllocator *allocator,
 107                        uptr class_id) {
 108     InitCache();
 109     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     InitCache();
 120     CHECK_GE(c->count, count);
 121     uptr first_idx_to_drain = c->count - count;
 122     c->count -= count;
 123     allocator->ReturnToAllocator(&stats_, class_id,
 124                                  &c->chunks[first_idx_to_drain], count);
 125   }
 126 };
 127
 128 // Cache used by SizeClassAllocator32.
 129 template <class SizeClassAllocator>
 130 struct SizeClassAllocator32LocalCache {
 131   typedef SizeClassAllocator Allocator;
 132   typedef typename Allocator::TransferBatch TransferBatch;
 133   static const uptr kNumClasses = SizeClassAllocator::kNumClasses;
 134
 135   void Init(AllocatorGlobalStats *s) {
 136     stats_.Init();
 137     if (s)
 138       s->Register(&stats_);
 139   }
 140
 141   void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) {
 142     Drain(allocator);
 143     if (s)
 144       s->Unregister(&stats_);
 145   }
 146
 147   void *Allocate(SizeClassAllocator *allocator, uptr class_id) {
 148     CHECK_NE(class_id, 0UL);
 149     CHECK_LT(class_id, kNumClasses);
 150     PerClass *c = &per_class_[class_id];
 151     if (UNLIKELY(c->count == 0)) {
 152       if (UNLIKELY(!Refill(allocator, class_id)))
 153         return nullptr;
 154     }
 155     stats_.Add(AllocatorStatAllocated, c->class_size);
 156     void *res = c->batch[--c->count];
 157     PREFETCH(c->batch[c->count - 1]);
 158     return res;
 159   }
 160
 161   void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) {
 162     CHECK_NE(class_id, 0UL);
 163     CHECK_LT(class_id, kNumClasses);
 164     // If the first allocator call on a new thread is a deallocation, then
 165     // max_count will be zero, leading to check failure.
 166     InitCache();
 167     PerClass *c = &per_class_[class_id];
 168     stats_.Sub(AllocatorStatAllocated, c->class_size);
 169     CHECK_NE(c->max_count, 0UL);
 170     if (UNLIKELY(c->count == c->max_count))
 171       Drain(allocator, class_id);
 172     c->batch[c->count++] = p;
 173   }
 174
 175   void Drain(SizeClassAllocator *allocator) {
 176     for (uptr class_id = 0; class_id < kNumClasses; class_id++) {
 177       PerClass *c = &per_class_[class_id];
 178       while (c->count > 0)
 179         Drain(allocator, class_id);
 180     }
 181   }
 182
 183   // private:
 184   typedef typename SizeClassAllocator::SizeClassMapT SizeClassMap;
 185   struct PerClass {
 186     uptr count;
 187     uptr max_count;
 188     uptr class_size;
 189     uptr class_id_for_transfer_batch;
 190     void *batch[2 * TransferBatch::kMaxNumCached];
 191   };
 192   PerClass per_class_[kNumClasses];
 193   AllocatorStats stats_;
 194
 195   void InitCache() {
 196     if (per_class_[1].max_count)
 197       return;
 198     // TransferBatch class is declared in SizeClassAllocator.
 199     uptr class_id_for_transfer_batch =
 200         SizeClassMap::ClassID(sizeof(TransferBatch));
 201     for (uptr i = 0; i < kNumClasses; i++) {
 202       PerClass *c = &per_class_[i];
 203       uptr max_cached = TransferBatch::MaxCached(i);
 204       c->max_count = 2 * max_cached;
 205       c->class_size = Allocator::ClassIdToSize(i);
 206       // We transfer chunks between central and thread-local free lists in
 207       // batches. For small size classes we allocate batches separately. For
 208       // large size classes we may use one of the chunks to store the batch.
 209       // sizeof(TransferBatch) must be a power of 2 for more efficient
 210       // allocation.
 211       c->class_id_for_transfer_batch = (c->class_size <
 212           TransferBatch::AllocationSizeRequiredForNElements(max_cached)) ?
 213               class_id_for_transfer_batch : 0;
 214     }
 215   }
 216
 217   // Returns a TransferBatch suitable for class_id.
 218   // For small size classes allocates the batch from the allocator.
 219   // For large size classes simply returns b.
 220   TransferBatch *CreateBatch(uptr class_id, SizeClassAllocator *allocator,
 221                              TransferBatch *b) {
 222     if (uptr batch_class_id = per_class_[class_id].class_id_for_transfer_batch)
 223       return (TransferBatch*)Allocate(allocator, batch_class_id);
 224     return b;
 225   }
 226
 227   // Destroys TransferBatch b.
 228   // For small size classes deallocates b to the allocator.
 229   // Does notthing for large size classes.
 230   void DestroyBatch(uptr class_id, SizeClassAllocator *allocator,
 231                     TransferBatch *b) {
 232     if (uptr batch_class_id = per_class_[class_id].class_id_for_transfer_batch)
 233       Deallocate(allocator, batch_class_id, b);
 234   }
 235
 236   NOINLINE bool Refill(SizeClassAllocator *allocator, uptr class_id) {
 237     InitCache();
 238     PerClass *c = &per_class_[class_id];
 239     TransferBatch *b = allocator->AllocateBatch(&stats_, this, class_id);
 240     if (UNLIKELY(!b))
 241       return false;
 242     CHECK_GT(b->Count(), 0);
 243     b->CopyToArray(c->batch);
 244     c->count = b->Count();
 245     DestroyBatch(class_id, allocator, b);
 246     return true;
 247   }
 248
 249   NOINLINE void Drain(SizeClassAllocator *allocator, uptr class_id) {
 250     InitCache();
 251     PerClass *c = &per_class_[class_id];
 252     uptr cnt = Min(c->max_count / 2, c->count);
 253     uptr first_idx_to_drain = c->count - cnt;
 254     TransferBatch *b = CreateBatch(
 255         class_id, allocator, (TransferBatch *)c->batch[first_idx_to_drain]);
 256     // Failure to allocate a batch while releasing memory is non recoverable.
 257     // TODO(alekseys): Figure out how to do it without allocating a new batch.
 258     if (UNLIKELY(!b))
 259       DieOnFailure::OnOOM();
 260     b->SetFromArray(allocator->GetRegionBeginBySizeClass(class_id),
 261                     &c->batch[first_idx_to_drain], cnt);
 262     c->count -= cnt;
 263     allocator->DeallocateBatch(&stats_, class_id, b);
 264   }
 265 };
 266