contrib/compiler-rt/lib/scudo/standalone/local_cache.h

   1 //===-- local_cache.h -------------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef SCUDO_LOCAL_CACHE_H_
  10 #define SCUDO_LOCAL_CACHE_H_
  11
  12 #include "internal_defs.h"
  13 #include "report.h"
  14 #include "stats.h"
  15
  16 namespace scudo {
  17
  18 template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache {
  19   typedef typename SizeClassAllocator::SizeClassMap SizeClassMap;
  20
  21   struct TransferBatch {
  22     static const u32 MaxNumCached = SizeClassMap::MaxNumCachedHint;
  23     void setFromArray(void **Array, u32 N) {
  24       DCHECK_LE(N, MaxNumCached);
  25       for (u32 I = 0; I < N; I++)
  26         Batch[I] = Array[I];
  27       Count = N;
  28     }
  29     void clear() { Count = 0; }
  30     void add(void *P) {
  31       DCHECK_LT(Count, MaxNumCached);
  32       Batch[Count++] = P;
  33     }
  34     void copyToArray(void **Array) const {
  35       for (u32 I = 0; I < Count; I++)
  36         Array[I] = Batch[I];
  37     }
  38     u32 getCount() const { return Count; }
  39     void *get(u32 I) const {
  40       DCHECK_LE(I, Count);
  41       return Batch[I];
  42     }
  43     static u32 getMaxCached(uptr Size) {
  44       return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size));
  45     }
  46     TransferBatch *Next;
  47
  48   private:
  49     u32 Count;
  50     void *Batch[MaxNumCached];
  51   };
  52
  53   void initLinkerInitialized(GlobalStats *S, SizeClassAllocator *A) {
  54     Stats.initLinkerInitialized();
  55     if (S)
  56       S->link(&Stats);
  57     Allocator = A;
  58   }
  59
  60   void init(GlobalStats *S, SizeClassAllocator *A) {
  61     memset(this, 0, sizeof(*this));
  62     initLinkerInitialized(S, A);
  63   }
  64
  65   void destroy(GlobalStats *S) {
  66     drain();
  67     if (S)
  68       S->unlink(&Stats);
  69   }
  70
  71   void *allocate(uptr ClassId) {
  72     CHECK_LT(ClassId, NumClasses);
  73     PerClass *C = &PerClassArray[ClassId];
  74     if (C->Count == 0) {
  75       if (UNLIKELY(!refill(C, ClassId)))
  76         return nullptr;
  77       DCHECK_GT(C->Count, 0);
  78     }
  79     // We read ClassSize first before accessing Chunks because it's adjacent to
  80     // Count, while Chunks might be further off (depending on Count). That keeps
  81     // the memory accesses in close quarters.
  82     const uptr ClassSize = C->ClassSize;
  83     void *P = C->Chunks[--C->Count];
  84     // The jury is still out as to whether any kind of PREFETCH here increases
  85     // performance. It definitely decreases performance on Android though.
  86     // if (!SCUDO_ANDROID) PREFETCH(P);
  87     Stats.add(StatAllocated, ClassSize);
  88     return P;
  89   }
  90
  91   void deallocate(uptr ClassId, void *P) {
  92     CHECK_LT(ClassId, NumClasses);
  93     PerClass *C = &PerClassArray[ClassId];
  94     // We still have to initialize the cache in the event that the first heap
  95     // operation in a thread is a deallocation.
  96     initCacheMaybe(C);
  97     if (C->Count == C->MaxCount)
  98       drain(C, ClassId);
  99     // See comment in allocate() about memory accesses.
 100     const uptr ClassSize = C->ClassSize;
 101     C->Chunks[C->Count++] = P;
 102     Stats.sub(StatAllocated, ClassSize);
 103   }
 104
 105   void drain() {
 106     for (uptr I = 0; I < NumClasses; I++) {
 107       PerClass *C = &PerClassArray[I];
 108       while (C->Count > 0)
 109         drain(C, I);
 110     }
 111   }
 112
 113   TransferBatch *createBatch(uptr ClassId, void *B) {
 114     if (ClassId != SizeClassMap::BatchClassId)
 115       B = allocate(SizeClassMap::BatchClassId);
 116     return reinterpret_cast<TransferBatch *>(B);
 117   }
 118
 119   LocalStats &getStats() { return Stats; }
 120
 121 private:
 122   static const uptr NumClasses = SizeClassMap::NumClasses;
 123   struct PerClass {
 124     u32 Count;
 125     u32 MaxCount;
 126     uptr ClassSize;
 127     void *Chunks[2 * TransferBatch::MaxNumCached];
 128   };
 129   PerClass PerClassArray[NumClasses];
 130   LocalStats Stats;
 131   SizeClassAllocator *Allocator;
 132
 133   ALWAYS_INLINE void initCacheMaybe(PerClass *C) {
 134     if (LIKELY(C->MaxCount))
 135       return;
 136     initCache();
 137     DCHECK_NE(C->MaxCount, 0U);
 138   }
 139
 140   NOINLINE void initCache() {
 141     for (uptr I = 0; I < NumClasses; I++) {
 142       PerClass *P = &PerClassArray[I];
 143       const uptr Size = SizeClassAllocator::getSizeByClassId(I);
 144       P->MaxCount = 2 * TransferBatch::getMaxCached(Size);
 145       P->ClassSize = Size;
 146     }
 147   }
 148
 149   void destroyBatch(uptr ClassId, void *B) {
 150     if (ClassId != SizeClassMap::BatchClassId)
 151       deallocate(SizeClassMap::BatchClassId, B);
 152   }
 153
 154   NOINLINE bool refill(PerClass *C, uptr ClassId) {
 155     initCacheMaybe(C);
 156     TransferBatch *B = Allocator->popBatch(this, ClassId);
 157     if (UNLIKELY(!B))
 158       return false;
 159     DCHECK_GT(B->getCount(), 0);
 160     B->copyToArray(C->Chunks);
 161     C->Count = B->getCount();
 162     destroyBatch(ClassId, B);
 163     return true;
 164   }
 165
 166   NOINLINE void drain(PerClass *C, uptr ClassId) {
 167     const u32 Count = Min(C->MaxCount / 2, C->Count);
 168     const uptr FirstIndexToDrain = C->Count - Count;
 169     TransferBatch *B = createBatch(ClassId, C->Chunks[FirstIndexToDrain]);
 170     if (UNLIKELY(!B))
 171       reportOutOfMemory(
 172           SizeClassAllocator::getSizeByClassId(SizeClassMap::BatchClassId));
 173     B->setFromArray(&C->Chunks[FirstIndexToDrain], Count);
 174     C->Count -= Count;
 175     Allocator->pushBatch(ClassId, B);
 176   }
 177 };
 178
 179 } // namespace scudo
 180
 181 #endif // SCUDO_LOCAL_CACHE_H_