diff --git a/compiler-rt/lib/scudo/standalone/size_class_map.h b/compiler-rt/lib/scudo/standalone/size_class_map.h --- a/compiler-rt/lib/scudo/standalone/size_class_map.h +++ b/compiler-rt/lib/scudo/standalone/size_class_map.h @@ -9,11 +9,33 @@ #ifndef SCUDO_SIZE_CLASS_MAP_H_ #define SCUDO_SIZE_CLASS_MAP_H_ +#include "chunk.h" #include "common.h" #include "string_utils.h" namespace scudo { +inline uptr scaledLog2(uptr Size, uptr ZeroLog, uptr LogBits) { + const uptr L = getMostSignificantSetBitIndex(Size); + const uptr LBits = (Size >> (L - LogBits)) - (1 << LogBits); + const uptr HBits = (L - ZeroLog) << LogBits; + return LBits + HBits; +} + +template struct SizeClassMapBase { + static u32 getMaxCachedHint(uptr Size) { + DCHECK_LE(Size, MaxSize); + DCHECK_NE(Size, 0); + u32 N; + // Force a 32-bit division if the template parameters allow for it. + if (Config::MaxBytesCachedLog > 31 || Config::MaxSizeLog > 31) + N = static_cast((1UL << Config::MaxBytesCachedLog) / Size); + else + N = (1U << Config::MaxBytesCachedLog) / static_cast(Size); + return Max(1U, Min(Config::MaxNumCachedHint, N)); + } +}; + // SizeClassMap maps allocation sizes into size classes and back, in an // efficient table-free manner. // @@ -33,22 +55,24 @@ // of chunks that can be cached per-thread: // - MaxNumCachedHint is a hint for the max number of chunks cached per class. // - 2^MaxBytesCachedLog is the max number of bytes cached per class. +template +class FixedSizeClassMap : public SizeClassMapBase { + typedef SizeClassMapBase Base; -template -class SizeClassMap { - static const uptr MinSize = 1UL << MinSizeLog; - static const uptr MidSize = 1UL << MidSizeLog; + static const uptr MinSize = 1UL << Config::MinSizeLog; + static const uptr MidSize = 1UL << Config::MidSizeLog; static const uptr MidClass = MidSize / MinSize; - static const u8 S = NumBits - 1; + static const u8 S = Config::NumBits - 1; static const uptr M = (1UL << S) - 1; + static const uptr SizeDelta = Chunk::getHeaderSize(); + public: - static const u32 MaxNumCachedHint = MaxNumCachedHintT; + static const u32 MaxNumCachedHint = Config::MaxNumCachedHint; - static const uptr MaxSize = 1UL << MaxSizeLog; + static const uptr MaxSize = (1UL << Config::MaxSizeLog) + SizeDelta; static const uptr NumClasses = - MidClass + ((MaxSizeLog - MidSizeLog) << S) + 1; + MidClass + ((Config::MaxSizeLog - Config::MidSizeLog) << S) + 1; static_assert(NumClasses <= 256, ""); static const uptr LargestClassId = NumClasses - 1; static const uptr BatchClassId = 0; @@ -56,33 +80,20 @@ static uptr getSizeByClassId(uptr ClassId) { DCHECK_NE(ClassId, BatchClassId); if (ClassId <= MidClass) - return ClassId << MinSizeLog; + return (ClassId << Config::MinSizeLog) + SizeDelta; ClassId -= MidClass; const uptr T = MidSize << (ClassId >> S); - return T + (T >> S) * (ClassId & M); + return T + (T >> S) * (ClassId & M) + SizeDelta; } static uptr getClassIdBySize(uptr Size) { + if (Size <= SizeDelta + (1 << Config::MinSizeLog)) + return 1; + Size -= SizeDelta; DCHECK_LE(Size, MaxSize); if (Size <= MidSize) - return (Size + MinSize - 1) >> MinSizeLog; - Size -= 1; - const uptr L = getMostSignificantSetBitIndex(Size); - const uptr LBits = (Size >> (L - S)) - (1 << S); - const uptr HBits = (L - MidSizeLog) << S; - return MidClass + 1 + HBits + LBits; - } - - static u32 getMaxCachedHint(uptr Size) { - DCHECK_LE(Size, MaxSize); - DCHECK_NE(Size, 0); - u32 N; - // Force a 32-bit division if the template parameters allow for it. - if (MaxBytesCachedLog > 31 || MaxSizeLog > 31) - N = static_cast((1UL << MaxBytesCachedLog) / Size); - else - N = (1U << MaxBytesCachedLog) / static_cast(Size); - return Max(1U, Min(MaxNumCachedHint, N)); + return (Size + MinSize - 1) >> Config::MinSizeLog; + return MidClass + 1 + scaledLog2(Size - 1, Config::MidSizeLog, S); } static void print() { @@ -98,10 +109,10 @@ const uptr D = S - PrevS; const uptr P = PrevS ? (D * 100 / PrevS) : 0; const uptr L = S ? getMostSignificantSetBitIndex(S) : 0; - const uptr Cached = getMaxCachedHint(S) * S; + const uptr Cached = Base::getMaxCachedHint(S) * S; Buffer.append( "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n", - I, getSizeByClassId(I), D, P, L, getMaxCachedHint(S), Cached, + I, getSizeByClassId(I), D, P, L, Base::getMaxCachedHint(S), Cached, getClassIdBySize(S)); TotalCached += Cached; PrevS = S; @@ -124,7 +135,7 @@ CHECK_GT(getSizeByClassId(C), getSizeByClassId(C - 1)); } // Do not perform the loop if the maximum size is too large. - if (MaxSizeLog > 19) + if (Config::MaxSizeLog > 19) return; for (uptr S = 1; S <= MaxSize; S++) { const uptr C = getClassIdBySize(S); @@ -136,16 +147,118 @@ } }; -typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap; +template +class TableSizeClassMap : public SizeClassMapBase { + static const u8 S = Config::NumBits - 1; + static const uptr M = (1UL << S) - 1; + static const uptr ClassesSize = + sizeof(Config::Classes) / sizeof(Config::Classes[0]); + + struct SizeTable { + constexpr SizeTable() { + uptr Pos = 1 << Config::MidSizeLog; + uptr Inc = 1 << (Config::MidSizeLog - S); + for (uptr i = 0; i != getTableSize(); ++i) { + Pos += Inc; + if ((Pos & (Pos - 1)) == 0) + Inc *= 2; + Tab[i] = computeClassId(Pos + Config::SizeDelta); + } + } + + constexpr static u8 computeClassId(uptr Size) { + for (uptr i = 0; i != ClassesSize; ++i) { + if (Size <= Config::Classes[i]) + return i + 1; + } + return -1; + } + + constexpr static uptr getTableSize() { + return (Config::MaxSizeLog - Config::MidSizeLog) << S; + } -// TODO(kostyak): further tune class maps for Android & Fuchsia. + u8 Tab[getTableSize()] = {}; + }; + + static constexpr SizeTable Table = {}; + +public: + static const u32 MaxNumCachedHint = Config::MaxNumCachedHint; + + static const uptr NumClasses = ClassesSize + 1; + static_assert(NumClasses < 256, ""); + static const uptr LargestClassId = NumClasses - 1; + static const uptr BatchClassId = 0; + static const uptr MaxSize = Config::Classes[LargestClassId - 1]; + + static uptr getSizeByClassId(uptr ClassId) { + return Config::Classes[ClassId - 1]; + } + + static uptr getClassIdBySize(uptr Size) { + if (Size <= Config::Classes[0]) + return 1; + Size -= Config::SizeDelta; + DCHECK_LE(Size, MaxSize); + if (Size <= (1 << Config::MidSizeLog)) + return ((Size - 1) >> Config::MinSizeLog) + 1; + return Table.Tab[scaledLog2(Size - 1, Config::MidSizeLog, S)]; + } + + static void print() {} + static void validate() {} +}; + +struct AndroidSizeClassConfig { + static const uptr NumBits = 5; + static const uptr MinSizeLog = 4; + static const uptr MidSizeLog = 6; + static const uptr MaxSizeLog = 16; + static const u32 MaxNumCachedHint = 14; + static const uptr MaxBytesCachedLog = 14; + + static constexpr u32 Classes[32] = { + 0x20, 0x30, 0x40, 0x50, 0x60, 0x90, 0xa0, 0xb0, + 0xd0, 0xf0, 0x150, 0x1a0, 0x1c0, 0x210, 0x250, 0x330, + 0x450, 0x610, 0x810, 0xa10, 0xc10, 0x1010, 0x1310, 0x1c10, + 0x2210, 0x3210, 0x3610, 0x4010, 0x4810, 0x5c10, 0x7410, 0x10010, + }; + static const uptr SizeDelta = 16; +}; + +typedef TableSizeClassMap AndroidSizeClassMap; + +struct DefaultSizeClassConfig { + static const uptr NumBits = 3; + static const uptr MinSizeLog = 5; + static const uptr MidSizeLog = 8; + static const uptr MaxSizeLog = 17; + static const u32 MaxNumCachedHint = 8; + static const uptr MaxBytesCachedLog = 10; +}; + +typedef FixedSizeClassMap DefaultSizeClassMap; + +struct SvelteSizeClassConfig { #if SCUDO_WORDSIZE == 64U -typedef SizeClassMap<4, 4, 8, 14, 4, 10> SvelteSizeClassMap; -typedef SizeClassMap<2, 5, 9, 16, 14, 14> AndroidSizeClassMap; + static const uptr NumBits = 4; + static const uptr MinSizeLog = 4; + static const uptr MidSizeLog = 8; + static const uptr MaxSizeLog = 14; + static const u32 MaxNumCachedHint = 4; + static const uptr MaxBytesCachedLog = 10; #else -typedef SizeClassMap<4, 3, 7, 14, 5, 10> SvelteSizeClassMap; -typedef SizeClassMap<2, 5, 9, 16, 14, 14> AndroidSizeClassMap; + static const uptr NumBits = 4; + static const uptr MinSizeLog = 3; + static const uptr MidSizeLog = 7; + static const uptr MaxSizeLog = 14; + static const u32 MaxNumCachedHint = 5; + static const uptr MaxBytesCachedLog = 10; #endif +}; + +typedef FixedSizeClassMap SvelteSizeClassMap; } // namespace scudo diff --git a/compiler-rt/lib/scudo/standalone/tests/combined_test.cpp b/compiler-rt/lib/scudo/standalone/tests/combined_test.cpp --- a/compiler-rt/lib/scudo/standalone/tests/combined_test.cpp +++ b/compiler-rt/lib/scudo/standalone/tests/combined_test.cpp @@ -164,6 +164,7 @@ for (scudo::sptr Delta = -32; Delta < 32; Delta += 8) { const scudo::uptr NewSize = DataSize + Delta; void *NewP = Allocator->reallocate(P, NewSize); + P = NewP; EXPECT_EQ(NewP, P); for (scudo::uptr I = 0; I < DataSize - 32; I++) EXPECT_EQ((reinterpret_cast(NewP))[I], Marker); @@ -343,9 +344,19 @@ #endif } + +struct DeathSizeClassConfig { + static const scudo::uptr NumBits = 1; + static const scudo::uptr MinSizeLog = 10; + static const scudo::uptr MidSizeLog = 10; + static const scudo::uptr MaxSizeLog = 10; + static const scudo::u32 MaxNumCachedHint = 1; + static const scudo::uptr MaxBytesCachedLog = 10; +}; + struct DeathConfig { // Tiny allocator, its Primary only serves chunks of 1024 bytes. - using DeathSizeClassMap = scudo::SizeClassMap<1U, 10U, 10U, 10U, 1U, 10U>; + using DeathSizeClassMap = scudo::FixedSizeClassMap; typedef scudo::SizeClassAllocator64 Primary; typedef scudo::MapAllocator Secondary; template using TSDRegistryT = scudo::TSDRegistrySharedT; diff --git a/compiler-rt/lib/scudo/standalone/tests/size_class_map_test.cpp b/compiler-rt/lib/scudo/standalone/tests/size_class_map_test.cpp --- a/compiler-rt/lib/scudo/standalone/tests/size_class_map_test.cpp +++ b/compiler-rt/lib/scudo/standalone/tests/size_class_map_test.cpp @@ -28,12 +28,31 @@ testSizeClassMap(); } + +struct OneClassSizeClassConfig { + static const scudo::uptr NumBits = 1; + static const scudo::uptr MinSizeLog = 5; + static const scudo::uptr MidSizeLog = 5; + static const scudo::uptr MaxSizeLog = 5; + static const scudo::u32 MaxNumCachedHint = 0; + static const scudo::uptr MaxBytesCachedLog = 0; +}; + TEST(ScudoSizeClassMapTest, OneClassSizeClassMap) { - testSizeClassMap>(); + testSizeClassMap>(); } #if SCUDO_CAN_USE_PRIMARY64 +struct LargeMaxSizeClassConfig { + static const scudo::uptr NumBits = 3; + static const scudo::uptr MinSizeLog = 4; + static const scudo::uptr MidSizeLog = 8; + static const scudo::uptr MaxSizeLog = 63; + static const scudo::u32 MaxNumCachedHint = 128; + static const scudo::uptr MaxBytesCachedLog = 16; +}; + TEST(ScudoSizeClassMapTest, LargeMaxSizeClassMap) { - testSizeClassMap>(); + testSizeClassMap>(); } #endif