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 "list.h"
  14 #include "platform.h"
  15 #include "report.h"
  16 #include "stats.h"
  17 #include "string_utils.h"
  18
  19 namespace scudo {
  20
  21 template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache {
  22   typedef typename SizeClassAllocator::SizeClassMap SizeClassMap;
  23   typedef typename SizeClassAllocator::CompactPtrT CompactPtrT;
  24
  25   void init(GlobalStats *S, SizeClassAllocator *A) {
  26     DCHECK(isEmpty());
  27     Stats.init();
  28     if (LIKELY(S))
  29       S->link(&Stats);
  30     Allocator = A;
  31   }
  32
  33   void destroy(GlobalStats *S) {
  34     drain();
  35     if (LIKELY(S))
  36       S->unlink(&Stats);
  37   }
  38
  39   void *allocate(uptr ClassId) {
  40     DCHECK_LT(ClassId, NumClasses);
  41     PerClass *C = &PerClassArray[ClassId];
  42     if (C->Count == 0) {
  43       initCacheMaybe(C);
  44
  45       // Refill half of the number of max cached.
  46       DCHECK_GT(C->MaxCount / 2, 0U);
  47       if (UNLIKELY(!refill(C, ClassId, C->MaxCount / 2)))
  48         return nullptr;
  49       DCHECK_GT(C->Count, 0);
  50     }
  51     // We read ClassSize first before accessing Chunks because it's adjacent to
  52     // Count, while Chunks might be further off (depending on Count). That keeps
  53     // the memory accesses in close quarters.
  54     const uptr ClassSize = C->ClassSize;
  55     CompactPtrT CompactP = C->Chunks[--C->Count];
  56     Stats.add(StatAllocated, ClassSize);
  57     Stats.sub(StatFree, ClassSize);
  58     return Allocator->decompactPtr(ClassId, CompactP);
  59   }
  60
  61   bool deallocate(uptr ClassId, void *P) {
  62     CHECK_LT(ClassId, NumClasses);
  63     PerClass *C = &PerClassArray[ClassId];
  64     // We still have to initialize the cache in the event that the first heap
  65     // operation in a thread is a deallocation.
  66     initCacheMaybe(C);
  67
  68     // If the cache is full, drain half of blocks back to the main allocator.
  69     const bool NeedToDrainCache = C->Count == C->MaxCount;
  70     if (NeedToDrainCache)
  71       drain(C, ClassId);
  72     // See comment in allocate() about memory accesses.
  73     const uptr ClassSize = C->ClassSize;
  74     C->Chunks[C->Count++] =
  75         Allocator->compactPtr(ClassId, reinterpret_cast<uptr>(P));
  76     Stats.sub(StatAllocated, ClassSize);
  77     Stats.add(StatFree, ClassSize);
  78
  79     return NeedToDrainCache;
  80   }
  81
  82   bool isEmpty() const {
  83     for (uptr I = 0; I < NumClasses; ++I)
  84       if (PerClassArray[I].Count)
  85         return false;
  86     return true;
  87   }
  88
  89   void drain() {
  90     // Drain BatchClassId last as it may be needed while draining normal blocks.
  91     for (uptr I = 0; I < NumClasses; ++I) {
  92       if (I == BatchClassId)
  93         continue;
  94       while (PerClassArray[I].Count > 0)
  95         drain(&PerClassArray[I], I);
  96     }
  97     while (PerClassArray[BatchClassId].Count > 0)
  98       drain(&PerClassArray[BatchClassId], BatchClassId);
  99     DCHECK(isEmpty());
 100   }
 101
 102   void *getBatchClassBlock() {
 103     void *B = allocate(BatchClassId);
 104     if (UNLIKELY(!B))
 105       reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId));
 106     return B;
 107   }
 108
 109   LocalStats &getStats() { return Stats; }
 110
 111   void getStats(ScopedString *Str) {
 112     bool EmptyCache = true;
 113     for (uptr I = 0; I < NumClasses; ++I) {
 114       if (PerClassArray[I].Count == 0)
 115         continue;
 116
 117       EmptyCache = false;
 118       // The size of BatchClass is set to 0 intentionally. See the comment in
 119       // initCache() for more details.
 120       const uptr ClassSize = I == BatchClassId
 121                                  ? SizeClassAllocator::getSizeByClassId(I)
 122                                  : PerClassArray[I].ClassSize;
 123       // Note that the string utils don't support printing u16 thus we cast it
 124       // to a common use type uptr.
 125       Str->append("    %02zu (%6zu): cached: %4zu max: %4zu\n", I, ClassSize,
 126                   static_cast<uptr>(PerClassArray[I].Count),
 127                   static_cast<uptr>(PerClassArray[I].MaxCount));
 128     }
 129
 130     if (EmptyCache)
 131       Str->append("    No block is cached.\n");
 132   }
 133
 134   static u16 getMaxCached(uptr Size) {
 135     return Min(SizeClassMap::MaxNumCachedHint,
 136                SizeClassMap::getMaxCachedHint(Size));
 137   }
 138
 139 private:
 140   static const uptr NumClasses = SizeClassMap::NumClasses;
 141   static const uptr BatchClassId = SizeClassMap::BatchClassId;
 142   struct alignas(SCUDO_CACHE_LINE_SIZE) PerClass {
 143     u16 Count;
 144     u16 MaxCount;
 145     // Note: ClassSize is zero for the transfer batch.
 146     uptr ClassSize;
 147     CompactPtrT Chunks[2 * SizeClassMap::MaxNumCachedHint];
 148   };
 149   PerClass PerClassArray[NumClasses] = {};
 150   LocalStats Stats;
 151   SizeClassAllocator *Allocator = nullptr;
 152
 153   ALWAYS_INLINE void initCacheMaybe(PerClass *C) {
 154     if (LIKELY(C->MaxCount))
 155       return;
 156     initCache();
 157     DCHECK_NE(C->MaxCount, 0U);
 158   }
 159
 160   NOINLINE void initCache() {
 161     for (uptr I = 0; I < NumClasses; I++) {
 162       PerClass *P = &PerClassArray[I];
 163       const uptr Size = SizeClassAllocator::getSizeByClassId(I);
 164       P->MaxCount = static_cast<u16>(2 * getMaxCached(Size));
 165       if (I != BatchClassId) {
 166         P->ClassSize = Size;
 167       } else {
 168         // ClassSize in this struct is only used for malloc/free stats, which
 169         // should only track user allocations, not internal movements.
 170         P->ClassSize = 0;
 171       }
 172     }
 173   }
 174
 175   void destroyBatch(uptr ClassId, void *B) {
 176     if (ClassId != BatchClassId)
 177       deallocate(BatchClassId, B);
 178   }
 179
 180   NOINLINE bool refill(PerClass *C, uptr ClassId, u16 MaxRefill) {
 181     const u16 NumBlocksRefilled =
 182         Allocator->popBlocks(this, ClassId, C->Chunks, MaxRefill);
 183     DCHECK_LE(NumBlocksRefilled, MaxRefill);
 184     C->Count = static_cast<u16>(C->Count + NumBlocksRefilled);
 185     return NumBlocksRefilled != 0;
 186   }
 187
 188   NOINLINE void drain(PerClass *C, uptr ClassId) {
 189     const u16 Count = Min(static_cast<u16>(C->MaxCount / 2), C->Count);
 190     Allocator->pushBlocks(this, ClassId, &C->Chunks[0], Count);
 191     // u16 will be promoted to int by arithmetic type conversion.
 192     C->Count = static_cast<u16>(C->Count - Count);
 193     for (u16 I = 0; I < C->Count; I++)
 194       C->Chunks[I] = C->Chunks[I + Count];
 195   }
 196 };
 197
 198 } // namespace scudo
 199
 200 #endif // SCUDO_LOCAL_CACHE_H_