Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 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 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 12 | #include "chunk.h" |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 13 | #include "common.h" |
| 14 | #include "string_utils.h" |
| 15 | |
| 16 | namespace scudo { |
| 17 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 18 | inline uptr scaledLog2(uptr Size, uptr ZeroLog, uptr LogBits) { |
| 19 | const uptr L = getMostSignificantSetBitIndex(Size); |
| 20 | const uptr LBits = (Size >> (L - LogBits)) - (1 << LogBits); |
| 21 | const uptr HBits = (L - ZeroLog) << LogBits; |
| 22 | return LBits + HBits; |
| 23 | } |
| 24 | |
| 25 | template <typename Config> struct SizeClassMapBase { |
| 26 | static u32 getMaxCachedHint(uptr Size) { |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 27 | DCHECK_NE(Size, 0); |
| 28 | u32 N; |
| 29 | // Force a 32-bit division if the template parameters allow for it. |
| 30 | if (Config::MaxBytesCachedLog > 31 || Config::MaxSizeLog > 31) |
| 31 | N = static_cast<u32>((1UL << Config::MaxBytesCachedLog) / Size); |
| 32 | else |
| 33 | N = (1U << Config::MaxBytesCachedLog) / static_cast<u32>(Size); |
| 34 | return Max(1U, Min(Config::MaxNumCachedHint, N)); |
| 35 | } |
| 36 | }; |
| 37 | |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 38 | // SizeClassMap maps allocation sizes into size classes and back, in an |
| 39 | // efficient table-free manner. |
| 40 | // |
| 41 | // Class 0 is a special class that doesn't abide by the same rules as other |
| 42 | // classes. The allocator uses it to hold batches. |
| 43 | // |
| 44 | // The other sizes are controlled by the template parameters: |
| 45 | // - MinSizeLog: defines the first class as 2^MinSizeLog bytes. |
| 46 | // - MaxSizeLog: defines the last class as 2^MaxSizeLog bytes. |
| 47 | // - MidSizeLog: classes increase with step 2^MinSizeLog from 2^MinSizeLog to |
| 48 | // 2^MidSizeLog bytes. |
| 49 | // - NumBits: the number of non-zero bits in sizes after 2^MidSizeLog. |
| 50 | // eg. with NumBits==3 all size classes after 2^MidSizeLog look like |
| 51 | // 0b1xx0..0 (where x is either 0 or 1). |
| 52 | // |
| 53 | // This class also gives a hint to a thread-caching allocator about the amount |
| 54 | // of chunks that can be cached per-thread: |
| 55 | // - MaxNumCachedHint is a hint for the max number of chunks cached per class. |
| 56 | // - 2^MaxBytesCachedLog is the max number of bytes cached per class. |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 57 | template <typename Config> |
| 58 | class FixedSizeClassMap : public SizeClassMapBase<Config> { |
| 59 | typedef SizeClassMapBase<Config> Base; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 60 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 61 | static const uptr MinSize = 1UL << Config::MinSizeLog; |
| 62 | static const uptr MidSize = 1UL << Config::MidSizeLog; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 63 | static const uptr MidClass = MidSize / MinSize; |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 64 | static const u8 S = Config::NumBits - 1; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 65 | static const uptr M = (1UL << S) - 1; |
| 66 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 67 | public: |
| 68 | static const u32 MaxNumCachedHint = Config::MaxNumCachedHint; |
| 69 | |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 70 | static const uptr MaxSize = (1UL << Config::MaxSizeLog) + Config::SizeDelta; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 71 | static const uptr NumClasses = |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 72 | MidClass + ((Config::MaxSizeLog - Config::MidSizeLog) << S) + 1; |
Dynamic Tools Team | 09e6d48 | 2019-11-26 18:18:14 -0800 | [diff] [blame] | 73 | static_assert(NumClasses <= 256, ""); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 74 | static const uptr LargestClassId = NumClasses - 1; |
| 75 | static const uptr BatchClassId = 0; |
| 76 | |
| 77 | static uptr getSizeByClassId(uptr ClassId) { |
| 78 | DCHECK_NE(ClassId, BatchClassId); |
| 79 | if (ClassId <= MidClass) |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 80 | return (ClassId << Config::MinSizeLog) + Config::SizeDelta; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 81 | ClassId -= MidClass; |
| 82 | const uptr T = MidSize << (ClassId >> S); |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 83 | return T + (T >> S) * (ClassId & M) + Config::SizeDelta; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 84 | } |
| 85 | |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 86 | static u8 getSizeLSBByClassId(uptr ClassId) { |
| 87 | return u8(getLeastSignificantSetBitIndex(getSizeByClassId(ClassId))); |
| 88 | } |
| 89 | |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 90 | static constexpr bool usesCompressedLSBFormat() { return false; } |
Peter Collingbourne | e910c69 | 2021-04-22 12:59:57 -0700 | [diff] [blame] | 91 | |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 92 | static uptr getClassIdBySize(uptr Size) { |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 93 | if (Size <= Config::SizeDelta + (1 << Config::MinSizeLog)) |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 94 | return 1; |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 95 | Size -= Config::SizeDelta; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 96 | DCHECK_LE(Size, MaxSize); |
| 97 | if (Size <= MidSize) |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 98 | return (Size + MinSize - 1) >> Config::MinSizeLog; |
| 99 | return MidClass + 1 + scaledLog2(Size - 1, Config::MidSizeLog, S); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 100 | } |
Dynamic Tools Team | a98a996 | 2020-02-13 09:27:18 -0800 | [diff] [blame] | 101 | |
| 102 | static u32 getMaxCachedHint(uptr Size) { |
| 103 | DCHECK_LE(Size, MaxSize); |
| 104 | return Base::getMaxCachedHint(Size); |
| 105 | } |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 106 | }; |
| 107 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 108 | template <typename Config> |
| 109 | class TableSizeClassMap : public SizeClassMapBase<Config> { |
Dynamic Tools Team | a98a996 | 2020-02-13 09:27:18 -0800 | [diff] [blame] | 110 | typedef SizeClassMapBase<Config> Base; |
| 111 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 112 | static const u8 S = Config::NumBits - 1; |
| 113 | static const uptr M = (1UL << S) - 1; |
| 114 | static const uptr ClassesSize = |
| 115 | sizeof(Config::Classes) / sizeof(Config::Classes[0]); |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 116 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 117 | struct SizeTable { |
| 118 | constexpr SizeTable() { |
| 119 | uptr Pos = 1 << Config::MidSizeLog; |
| 120 | uptr Inc = 1 << (Config::MidSizeLog - S); |
| 121 | for (uptr i = 0; i != getTableSize(); ++i) { |
| 122 | Pos += Inc; |
| 123 | if ((Pos & (Pos - 1)) == 0) |
| 124 | Inc *= 2; |
| 125 | Tab[i] = computeClassId(Pos + Config::SizeDelta); |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | constexpr static u8 computeClassId(uptr Size) { |
| 130 | for (uptr i = 0; i != ClassesSize; ++i) { |
| 131 | if (Size <= Config::Classes[i]) |
Dynamic Tools Team | a98a996 | 2020-02-13 09:27:18 -0800 | [diff] [blame] | 132 | return static_cast<u8>(i + 1); |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 133 | } |
Dynamic Tools Team | a98a996 | 2020-02-13 09:27:18 -0800 | [diff] [blame] | 134 | return static_cast<u8>(-1); |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 135 | } |
| 136 | |
| 137 | constexpr static uptr getTableSize() { |
| 138 | return (Config::MaxSizeLog - Config::MidSizeLog) << S; |
| 139 | } |
| 140 | |
| 141 | u8 Tab[getTableSize()] = {}; |
| 142 | }; |
| 143 | |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 144 | static constexpr SizeTable SzTable = {}; |
| 145 | |
| 146 | struct LSBTable { |
| 147 | constexpr LSBTable() { |
Peter Collingbourne | e910c69 | 2021-04-22 12:59:57 -0700 | [diff] [blame] | 148 | u8 Min = 255, Max = 0; |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 149 | for (uptr I = 0; I != ClassesSize; ++I) { |
| 150 | for (u8 Bit = 0; Bit != 64; ++Bit) { |
| 151 | if (Config::Classes[I] & (1 << Bit)) { |
| 152 | Tab[I] = Bit; |
Peter Collingbourne | e910c69 | 2021-04-22 12:59:57 -0700 | [diff] [blame] | 153 | if (Bit < Min) |
| 154 | Min = Bit; |
| 155 | if (Bit > Max) |
| 156 | Max = Bit; |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 157 | break; |
| 158 | } |
| 159 | } |
| 160 | } |
Peter Collingbourne | e910c69 | 2021-04-22 12:59:57 -0700 | [diff] [blame] | 161 | |
| 162 | if (Max - Min > 3 || ClassesSize > 32) |
| 163 | return; |
| 164 | |
| 165 | UseCompressedFormat = true; |
| 166 | CompressedMin = Min; |
| 167 | for (uptr I = 0; I != ClassesSize; ++I) |
| 168 | CompressedValue |= u64(Tab[I] - Min) << (I * 2); |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 169 | } |
| 170 | |
| 171 | u8 Tab[ClassesSize] = {}; |
Peter Collingbourne | e910c69 | 2021-04-22 12:59:57 -0700 | [diff] [blame] | 172 | |
| 173 | bool UseCompressedFormat = false; |
| 174 | u8 CompressedMin = 0; |
| 175 | u64 CompressedValue = 0; |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 176 | }; |
| 177 | |
| 178 | static constexpr LSBTable LTable = {}; |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 179 | |
| 180 | public: |
| 181 | static const u32 MaxNumCachedHint = Config::MaxNumCachedHint; |
| 182 | |
| 183 | static const uptr NumClasses = ClassesSize + 1; |
| 184 | static_assert(NumClasses < 256, ""); |
| 185 | static const uptr LargestClassId = NumClasses - 1; |
| 186 | static const uptr BatchClassId = 0; |
| 187 | static const uptr MaxSize = Config::Classes[LargestClassId - 1]; |
| 188 | |
| 189 | static uptr getSizeByClassId(uptr ClassId) { |
| 190 | return Config::Classes[ClassId - 1]; |
| 191 | } |
| 192 | |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 193 | static u8 getSizeLSBByClassId(uptr ClassId) { |
Peter Collingbourne | e910c69 | 2021-04-22 12:59:57 -0700 | [diff] [blame] | 194 | if (LTable.UseCompressedFormat) |
| 195 | return ((LTable.CompressedValue >> ((ClassId - 1) * 2)) & 3) + |
| 196 | LTable.CompressedMin; |
| 197 | else |
| 198 | return LTable.Tab[ClassId - 1]; |
| 199 | } |
| 200 | |
| 201 | static constexpr bool usesCompressedLSBFormat() { |
| 202 | return LTable.UseCompressedFormat; |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 203 | } |
| 204 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 205 | static uptr getClassIdBySize(uptr Size) { |
| 206 | if (Size <= Config::Classes[0]) |
| 207 | return 1; |
| 208 | Size -= Config::SizeDelta; |
| 209 | DCHECK_LE(Size, MaxSize); |
| 210 | if (Size <= (1 << Config::MidSizeLog)) |
| 211 | return ((Size - 1) >> Config::MinSizeLog) + 1; |
Peter Collingbourne | 39f99a9 | 2021-04-21 21:03:45 -0700 | [diff] [blame] | 212 | return SzTable.Tab[scaledLog2(Size - 1, Config::MidSizeLog, S)]; |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 213 | } |
| 214 | |
Dynamic Tools Team | a98a996 | 2020-02-13 09:27:18 -0800 | [diff] [blame] | 215 | static u32 getMaxCachedHint(uptr Size) { |
| 216 | DCHECK_LE(Size, MaxSize); |
| 217 | return Base::getMaxCachedHint(Size); |
| 218 | } |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 219 | }; |
| 220 | |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame] | 221 | struct DefaultSizeClassConfig { |
| 222 | static const uptr NumBits = 3; |
| 223 | static const uptr MinSizeLog = 5; |
| 224 | static const uptr MidSizeLog = 8; |
| 225 | static const uptr MaxSizeLog = 17; |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 226 | static const u32 MaxNumCachedHint = 14; |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame] | 227 | static const uptr MaxBytesCachedLog = 10; |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 228 | static const uptr SizeDelta = 0; |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame] | 229 | }; |
| 230 | |
| 231 | typedef FixedSizeClassMap<DefaultSizeClassConfig> DefaultSizeClassMap; |
| 232 | |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 233 | struct FuchsiaSizeClassConfig { |
| 234 | static const uptr NumBits = 3; |
| 235 | static const uptr MinSizeLog = 5; |
| 236 | static const uptr MidSizeLog = 8; |
| 237 | static const uptr MaxSizeLog = 17; |
| 238 | static const u32 MaxNumCachedHint = 10; |
| 239 | static const uptr MaxBytesCachedLog = 10; |
| 240 | static const uptr SizeDelta = Chunk::getHeaderSize(); |
| 241 | }; |
| 242 | |
| 243 | typedef FixedSizeClassMap<FuchsiaSizeClassConfig> FuchsiaSizeClassMap; |
| 244 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 245 | struct AndroidSizeClassConfig { |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 246 | #if SCUDO_WORDSIZE == 64U |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 247 | static const uptr NumBits = 7; |
| 248 | static const uptr MinSizeLog = 4; |
| 249 | static const uptr MidSizeLog = 6; |
| 250 | static const uptr MaxSizeLog = 16; |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame] | 251 | static const u32 MaxNumCachedHint = 13; |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 252 | static const uptr MaxBytesCachedLog = 13; |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 253 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 254 | static constexpr u32 Classes[] = { |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 255 | 0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00090, 0x000b0, |
| 256 | 0x000c0, 0x000e0, 0x00120, 0x00160, 0x001c0, 0x00250, 0x00320, 0x00450, |
| 257 | 0x00670, 0x00830, 0x00a10, 0x00c30, 0x01010, 0x01210, 0x01bd0, 0x02210, |
| 258 | 0x02d90, 0x03790, 0x04010, 0x04810, 0x05a10, 0x07310, 0x08210, 0x10010, |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 259 | }; |
| 260 | static const uptr SizeDelta = 16; |
| 261 | #else |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 262 | static const uptr NumBits = 8; |
| 263 | static const uptr MinSizeLog = 4; |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 264 | static const uptr MidSizeLog = 7; |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 265 | static const uptr MaxSizeLog = 16; |
| 266 | static const u32 MaxNumCachedHint = 14; |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 267 | static const uptr MaxBytesCachedLog = 13; |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 268 | |
| 269 | static constexpr u32 Classes[] = { |
| 270 | 0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00080, 0x00090, |
Dynamic Tools Team | ebcf82d | 2020-02-25 14:23:34 -0800 | [diff] [blame] | 271 | 0x000a0, 0x000b0, 0x000c0, 0x000e0, 0x000f0, 0x00110, 0x00120, 0x00130, |
| 272 | 0x00150, 0x00160, 0x00170, 0x00190, 0x001d0, 0x00210, 0x00240, 0x002a0, |
| 273 | 0x00330, 0x00370, 0x003a0, 0x00400, 0x00430, 0x004a0, 0x00530, 0x00610, |
| 274 | 0x00730, 0x00840, 0x00910, 0x009c0, 0x00a60, 0x00b10, 0x00ca0, 0x00e00, |
| 275 | 0x00fb0, 0x01030, 0x01130, 0x011f0, 0x01490, 0x01650, 0x01930, 0x02010, |
| 276 | 0x02190, 0x02490, 0x02850, 0x02d50, 0x03010, 0x03210, 0x03c90, 0x04090, |
| 277 | 0x04510, 0x04810, 0x05c10, 0x06f10, 0x07310, 0x08010, 0x0c010, 0x10010, |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 278 | }; |
| 279 | static const uptr SizeDelta = 16; |
| 280 | #endif |
| 281 | }; |
| 282 | |
| 283 | typedef TableSizeClassMap<AndroidSizeClassConfig> AndroidSizeClassMap; |
| 284 | |
Peter Collingbourne | 1b55294 | 2021-04-22 16:09:23 -0700 | [diff] [blame] | 285 | #if SCUDO_WORDSIZE == 64U && defined(__clang__) |
Peter Collingbourne | e910c69 | 2021-04-22 12:59:57 -0700 | [diff] [blame] | 286 | static_assert(AndroidSizeClassMap::usesCompressedLSBFormat(), ""); |
| 287 | #endif |
| 288 | |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 289 | struct SvelteSizeClassConfig { |
| 290 | #if SCUDO_WORDSIZE == 64U |
| 291 | static const uptr NumBits = 4; |
| 292 | static const uptr MinSizeLog = 4; |
| 293 | static const uptr MidSizeLog = 8; |
| 294 | static const uptr MaxSizeLog = 14; |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame] | 295 | static const u32 MaxNumCachedHint = 13; |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 296 | static const uptr MaxBytesCachedLog = 10; |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 297 | static const uptr SizeDelta = Chunk::getHeaderSize(); |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 298 | #else |
| 299 | static const uptr NumBits = 4; |
| 300 | static const uptr MinSizeLog = 3; |
| 301 | static const uptr MidSizeLog = 7; |
| 302 | static const uptr MaxSizeLog = 14; |
Kostya Kortchinsky | c936954 | 2021-02-10 10:17:18 -0800 | [diff] [blame] | 303 | static const u32 MaxNumCachedHint = 14; |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 304 | static const uptr MaxBytesCachedLog = 10; |
Kostya Kortchinsky | 27c58d4 | 2021-05-19 09:10:30 -0700 | [diff] [blame] | 305 | static const uptr SizeDelta = Chunk::getHeaderSize(); |
Dynamic Tools Team | 130bfdb | 2020-02-10 15:53:07 -0800 | [diff] [blame] | 306 | #endif |
| 307 | }; |
| 308 | |
| 309 | typedef FixedSizeClassMap<SvelteSizeClassConfig> SvelteSizeClassMap; |
| 310 | |
| 311 | template <typename SCMap> inline void printMap() { |
| 312 | ScopedString Buffer(1024); |
| 313 | uptr PrevS = 0; |
| 314 | uptr TotalCached = 0; |
| 315 | for (uptr I = 0; I < SCMap::NumClasses; I++) { |
| 316 | if (I == SCMap::BatchClassId) |
| 317 | continue; |
| 318 | const uptr S = SCMap::getSizeByClassId(I); |
| 319 | const uptr D = S - PrevS; |
| 320 | const uptr P = PrevS ? (D * 100 / PrevS) : 0; |
| 321 | const uptr L = S ? getMostSignificantSetBitIndex(S) : 0; |
| 322 | const uptr Cached = SCMap::getMaxCachedHint(S) * S; |
| 323 | Buffer.append( |
| 324 | "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n", |
| 325 | I, S, D, P, L, SCMap::getMaxCachedHint(S), Cached, |
| 326 | SCMap::getClassIdBySize(S)); |
| 327 | TotalCached += Cached; |
| 328 | PrevS = S; |
| 329 | } |
| 330 | Buffer.append("Total Cached: %zu\n", TotalCached); |
| 331 | Buffer.output(); |
| 332 | } |
| 333 | |
| 334 | template <typename SCMap> static void validateMap() { |
| 335 | for (uptr C = 0; C < SCMap::NumClasses; C++) { |
| 336 | if (C == SCMap::BatchClassId) |
| 337 | continue; |
| 338 | const uptr S = SCMap::getSizeByClassId(C); |
| 339 | CHECK_NE(S, 0U); |
| 340 | CHECK_EQ(SCMap::getClassIdBySize(S), C); |
| 341 | if (C < SCMap::LargestClassId) |
| 342 | CHECK_EQ(SCMap::getClassIdBySize(S + 1), C + 1); |
| 343 | CHECK_EQ(SCMap::getClassIdBySize(S - 1), C); |
| 344 | if (C - 1 != SCMap::BatchClassId) |
| 345 | CHECK_GT(SCMap::getSizeByClassId(C), SCMap::getSizeByClassId(C - 1)); |
| 346 | } |
| 347 | // Do not perform the loop if the maximum size is too large. |
| 348 | if (SCMap::MaxSize > (1 << 19)) |
| 349 | return; |
| 350 | for (uptr S = 1; S <= SCMap::MaxSize; S++) { |
| 351 | const uptr C = SCMap::getClassIdBySize(S); |
| 352 | CHECK_LT(C, SCMap::NumClasses); |
| 353 | CHECK_GE(SCMap::getSizeByClassId(C), S); |
| 354 | if (C - 1 != SCMap::BatchClassId) |
| 355 | CHECK_LT(SCMap::getSizeByClassId(C - 1), S); |
| 356 | } |
| 357 | } |
Dynamic Tools Team | 517193e | 2019-09-11 14:48:41 +0000 | [diff] [blame] | 358 | } // namespace scudo |
| 359 | |
| 360 | #endif // SCUDO_SIZE_CLASS_MAP_H_ |