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