contrib/llvm-project/compiler-rt/lib/scudo/standalone/size_class_map.h

   1 //===-- size_class_map.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_SIZE_CLASS_MAP_H_
  10 #define SCUDO_SIZE_CLASS_MAP_H_
  11
  12 #include "common.h"
  13 #include "string_utils.h"
  14
  15 namespace scudo {
  16
  17 // SizeClassMap maps allocation sizes into size classes and back, in an
  18 // efficient table-free manner.
  19 //
  20 // Class 0 is a special class that doesn't abide by the same rules as other
  21 // classes. The allocator uses it to hold batches.
  22 //
  23 // The other sizes are controlled by the template parameters:
  24 // - MinSizeLog: defines the first class as 2^MinSizeLog bytes.
  25 // - MaxSizeLog: defines the last class as 2^MaxSizeLog bytes.
  26 // - MidSizeLog: classes increase with step 2^MinSizeLog from 2^MinSizeLog to
  27 //               2^MidSizeLog bytes.
  28 // - NumBits: the number of non-zero bits in sizes after 2^MidSizeLog.
  29 //            eg. with NumBits==3 all size classes after 2^MidSizeLog look like
  30 //            0b1xx0..0 (where x is either 0 or 1).
  31 //
  32 // This class also gives a hint to a thread-caching allocator about the amount
  33 // of chunks that can be cached per-thread:
  34 // - MaxNumCachedHint is a hint for the max number of chunks cached per class.
  35 // - 2^MaxBytesCachedLog is the max number of bytes cached per class.
  36
  37 template <u8 NumBits, u8 MinSizeLog, u8 MidSizeLog, u8 MaxSizeLog,
  38           u32 MaxNumCachedHintT, u8 MaxBytesCachedLog>
  39 class SizeClassMap {
  40   static const uptr MinSize = 1UL << MinSizeLog;
  41   static const uptr MidSize = 1UL << MidSizeLog;
  42   static const uptr MidClass = MidSize / MinSize;
  43   static const u8 S = NumBits - 1;
  44   static const uptr M = (1UL << S) - 1;
  45
  46 public:
  47   static const u32 MaxNumCachedHint = MaxNumCachedHintT;
  48
  49   static const uptr MaxSize = 1UL << MaxSizeLog;
  50   static const uptr NumClasses =
  51       MidClass + ((MaxSizeLog - MidSizeLog) << S) + 1;
  52   COMPILER_CHECK(NumClasses <= 256);
  53   static const uptr LargestClassId = NumClasses - 1;
  54   static const uptr BatchClassId = 0;
  55
  56   static uptr getSizeByClassId(uptr ClassId) {
  57     DCHECK_NE(ClassId, BatchClassId);
  58     if (ClassId <= MidClass)
  59       return ClassId << MinSizeLog;
  60     ClassId -= MidClass;
  61     const uptr T = MidSize << (ClassId >> S);
  62     return T + (T >> S) * (ClassId & M);
  63   }
  64
  65   static uptr getClassIdBySize(uptr Size) {
  66     DCHECK_LE(Size, MaxSize);
  67     if (Size <= MidSize)
  68       return (Size + MinSize - 1) >> MinSizeLog;
  69     const uptr L = getMostSignificantSetBitIndex(Size);
  70     const uptr HBits = (Size >> (L - S)) & M;
  71     const uptr LBits = Size & ((1UL << (L - S)) - 1);
  72     const uptr L1 = L - MidSizeLog;
  73     return MidClass + (L1 << S) + HBits + (LBits > 0);
  74   }
  75
  76   static u32 getMaxCachedHint(uptr Size) {
  77     DCHECK_LE(Size, MaxSize);
  78     DCHECK_NE(Size, 0);
  79     u32 N;
  80     // Force a 32-bit division if the template parameters allow for it.
  81     if (MaxBytesCachedLog > 31 || MaxSizeLog > 31)
  82       N = static_cast<u32>((1UL << MaxBytesCachedLog) / Size);
  83     else
  84       N = (1U << MaxBytesCachedLog) / static_cast<u32>(Size);
  85     return Max(1U, Min(MaxNumCachedHint, N));
  86   }
  87
  88   static void print() {
  89     uptr PrevS = 0;
  90     uptr TotalCached = 0;
  91     for (uptr I = 0; I < NumClasses; I++) {
  92       if (I == BatchClassId)
  93         continue;
  94       const uptr S = getSizeByClassId(I);
  95       if (S >= MidSize / 2 && (S & (S - 1)) == 0)
  96         Printf("\n");
  97       const uptr D = S - PrevS;
  98       const uptr P = PrevS ? (D * 100 / PrevS) : 0;
  99       const uptr L = S ? getMostSignificantSetBitIndex(S) : 0;
 100       const uptr Cached = getMaxCachedHint(S) * S;
 101       Printf(
 102           "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n",
 103           I, getSizeByClassId(I), D, P, L, getMaxCachedHint(S), Cached,
 104           getClassIdBySize(S));
 105       TotalCached += Cached;
 106       PrevS = S;
 107     }
 108     Printf("Total Cached: %zu\n", TotalCached);
 109   }
 110
 111   static void validate() {
 112     for (uptr C = 0; C < NumClasses; C++) {
 113       if (C == BatchClassId)
 114         continue;
 115       const uptr S = getSizeByClassId(C);
 116       CHECK_NE(S, 0U);
 117       CHECK_EQ(getClassIdBySize(S), C);
 118       if (C < LargestClassId)
 119         CHECK_EQ(getClassIdBySize(S + 1), C + 1);
 120       CHECK_EQ(getClassIdBySize(S - 1), C);
 121       CHECK_GT(getSizeByClassId(C), getSizeByClassId(C - 1));
 122     }
 123     // Do not perform the loop if the maximum size is too large.
 124     if (MaxSizeLog > 19)
 125       return;
 126     for (uptr S = 1; S <= MaxSize; S++) {
 127       const uptr C = getClassIdBySize(S);
 128       CHECK_LT(C, NumClasses);
 129       CHECK_GE(getSizeByClassId(C), S);
 130       if (C > 0)
 131         CHECK_LT(getSizeByClassId(C - 1), S);
 132     }
 133   }
 134 };
 135
 136 typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap;
 137
 138 // TODO(kostyak): further tune class maps for Android & Fuchsia.
 139 #if SCUDO_WORDSIZE == 64U
 140 typedef SizeClassMap<3, 5, 8, 15, 8, 10> SvelteSizeClassMap;
 141 typedef SizeClassMap<3, 5, 8, 16, 14, 12> AndroidSizeClassMap;
 142 #else
 143 typedef SizeClassMap<3, 4, 7, 15, 8, 10> SvelteSizeClassMap;
 144 typedef SizeClassMap<3, 4, 7, 16, 14, 12> AndroidSizeClassMap;
 145 #endif
 146
 147 } // namespace scudo
 148
 149 #endif // SCUDO_SIZE_CLASS_MAP_H_