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