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 15namespace 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 37template <u8 NumBits, u8 MinSizeLog, u8 MidSizeLog, u8 MaxSizeLog, 38 u32 MaxNumCachedHintT, u8 MaxBytesCachedLog> 39class 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 46public: 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 static_assert(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 ScopedString Buffer(1024); 90 uptr PrevS = 0; 91 uptr TotalCached = 0; 92 for (uptr I = 0; I < NumClasses; I++) { 93 if (I == BatchClassId) 94 continue; 95 const uptr S = getSizeByClassId(I); 96 if (S >= MidSize / 2 && (S & (S - 1)) == 0) 97 Buffer.append("\n"); 98 const uptr D = S - PrevS; 99 const uptr P = PrevS ? (D * 100 / PrevS) : 0; 100 const uptr L = S ? getMostSignificantSetBitIndex(S) : 0; 101 const uptr Cached = getMaxCachedHint(S) * S; 102 Buffer.append( 103 "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n", 104 I, getSizeByClassId(I), D, P, L, getMaxCachedHint(S), Cached, 105 getClassIdBySize(S)); 106 TotalCached += Cached; 107 PrevS = S; 108 } 109 Buffer.append("Total Cached: %zu\n", TotalCached); 110 Buffer.output(); 111 } 112 113 static void validate() { 114 for (uptr C = 0; C < NumClasses; C++) { 115 if (C == BatchClassId) 116 continue; 117 const uptr S = getSizeByClassId(C); 118 CHECK_NE(S, 0U); 119 CHECK_EQ(getClassIdBySize(S), C); 120 if (C < LargestClassId) 121 CHECK_EQ(getClassIdBySize(S + 1), C + 1); 122 CHECK_EQ(getClassIdBySize(S - 1), C); 123 if (C - 1 != BatchClassId) 124 CHECK_GT(getSizeByClassId(C), getSizeByClassId(C - 1)); 125 } 126 // Do not perform the loop if the maximum size is too large. 127 if (MaxSizeLog > 19) 128 return; 129 for (uptr S = 1; S <= MaxSize; S++) { 130 const uptr C = getClassIdBySize(S); 131 CHECK_LT(C, NumClasses); 132 CHECK_GE(getSizeByClassId(C), S); 133 if (C - 1 != BatchClassId) 134 CHECK_LT(getSizeByClassId(C - 1), S); 135 } 136 } 137}; 138 139typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap; 140 141// TODO(kostyak): further tune class maps for Android & Fuchsia. 142#if SCUDO_WORDSIZE == 64U 143typedef SizeClassMap<4, 4, 8, 14, 4, 10> SvelteSizeClassMap; 144typedef SizeClassMap<3, 5, 8, 17, 14, 14> AndroidSizeClassMap; 145#else 146typedef SizeClassMap<4, 3, 7, 14, 5, 10> SvelteSizeClassMap; 147typedef SizeClassMap<3, 5, 8, 17, 14, 14> AndroidSizeClassMap; 148#endif 149 150} // namespace scudo 151 152#endif // SCUDO_SIZE_CLASS_MAP_H_ 153