Index: lib/scudo/standalone/CMakeLists.txt =================================================================== --- lib/scudo/standalone/CMakeLists.txt +++ lib/scudo/standalone/CMakeLists.txt @@ -71,6 +71,7 @@ platform.h report.h secondary.h + size_class_map.h stats.h string_utils.h vector.h) Index: lib/scudo/standalone/common.h =================================================================== --- lib/scudo/standalone/common.h +++ lib/scudo/standalone/common.h @@ -67,7 +67,7 @@ INLINE uptr getLeastSignificantSetBitIndex(uptr X) { DCHECK_NE(X, 0U); - return static_cast(__builtin_ctzll(X)); + return static_cast(__builtin_ctzl(X)); } INLINE uptr getLog2(uptr X) { Index: lib/scudo/standalone/size_class_map.h =================================================================== --- lib/scudo/standalone/size_class_map.h +++ lib/scudo/standalone/size_class_map.h @@ -0,0 +1,149 @@ +//===-- size_class_map.h ----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SCUDO_SIZE_CLASS_MAP_H_ +#define SCUDO_SIZE_CLASS_MAP_H_ + +#include "common.h" +#include "string_utils.h" + +namespace scudo { + +// SizeClassMap maps allocation sizes into size classes and back, in an +// efficient table-free manner. +// +// Class 0 is a special class that doesn't abide by the same rules as other +// classes. The allocator uses it to hold batches. +// +// The other sizes are controlled by the template parameters: +// - MinSizeLog: defines the first class as 2^MinSizeLog bytes. +// - MaxSizeLog: defines the last class as 2^MaxSizeLog bytes. +// - MidSizeLog: classes increase with step 2^MinSizeLog from 2^MinSizeLog to +// 2^MidSizeLog bytes. +// - NumBits: the number of non-zero bits in sizes after 2^MidSizeLog. +// eg. with NumBits==3 all size classes after 2^MidSizeLog look like +// 0b1xx0..0 (where x is either 0 or 1). +// +// This class also gives a hint to a thread-caching allocator about the amount +// 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 SizeClassMap { + static const uptr MinSize = 1UL << MinSizeLog; + static const uptr MidSize = 1UL << MidSizeLog; + static const uptr MidClass = MidSize / MinSize; + static const u8 S = NumBits - 1; + static const uptr M = (1UL << S) - 1; + +public: + static const u32 MaxNumCachedHint = MaxNumCachedHintT; + + static const uptr MaxSize = 1UL << MaxSizeLog; + static const uptr NumClasses = + MidClass + ((MaxSizeLog - MidSizeLog) << S) + 1; + COMPILER_CHECK(NumClasses <= 256); + static const uptr LargestClassId = NumClasses - 1; + static const uptr BatchClassId = 0; + + static uptr getSizeByClassId(uptr ClassId) { + DCHECK_NE(ClassId, BatchClassId); + if (ClassId <= MidClass) + return ClassId << MinSizeLog; + ClassId -= MidClass; + const uptr T = MidSize << (ClassId >> S); + return T + (T >> S) * (ClassId & M); + } + + static uptr getClassIdBySize(uptr Size) { + DCHECK_LE(Size, MaxSize); + if (Size <= MidSize) + return (Size + MinSize - 1) >> MinSizeLog; + const uptr L = getMostSignificantSetBitIndex(Size); + const uptr HBits = (Size >> (L - S)) & M; + const uptr LBits = Size & ((1UL << (L - S)) - 1); + const uptr L1 = L - MidSizeLog; + return MidClass + (L1 << S) + HBits + (LBits > 0); + } + + 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)); + } + + static void print() { + uptr PrevS = 0; + uptr TotalCached = 0; + for (uptr I = 0; I < NumClasses; I++) { + if (I == BatchClassId) + continue; + const uptr S = getSizeByClassId(I); + if (S >= MidSize / 2 && (S & (S - 1)) == 0) + Printf("\n"); + 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; + Printf( + "C%02zu => S: %zu diff: +%zu %02zu%% L %zu Cached: %zu %zu; id %zu\n", + I, getSizeByClassId(I), D, P, L, getMaxCachedHint(S), Cached, + getClassIdBySize(S)); + TotalCached += Cached; + PrevS = S; + } + Printf("Total Cached: %zu\n", TotalCached); + } + + static void validate() { + for (uptr C = 0; C < NumClasses; C++) { + if (C == BatchClassId) + continue; + const uptr S = getSizeByClassId(C); + CHECK_NE(S, 0U); + CHECK_EQ(getClassIdBySize(S), C); + if (C < LargestClassId) + CHECK_EQ(getClassIdBySize(S + 1), C + 1); + CHECK_EQ(getClassIdBySize(S - 1), C); + CHECK_GT(getSizeByClassId(C), getSizeByClassId(C - 1)); + } + // Do not perform the loop if the maximum size is too large. + if (MaxSizeLog > 19) + return; + for (uptr S = 1; S <= MaxSize; S++) { + const uptr C = getClassIdBySize(S); + CHECK_LT(C, NumClasses); + CHECK_GE(getSizeByClassId(C), S); + if (C > 0) + CHECK_LT(getSizeByClassId(C - 1), S); + } + } +}; + +typedef SizeClassMap<3, 5, 8, 17, 8, 10> DefaultSizeClassMap; + +// TODO(kostyak): further tune class maps for Android & Fuchsia. +#if SCUDO_WORDSIZE == 64U +typedef SizeClassMap<3, 5, 8, 15, 8, 10> SvelteSizeClassMap; +typedef SizeClassMap<3, 5, 8, 16, 14, 12> AndroidSizeClassMap; +#else +typedef SizeClassMap<3, 4, 7, 15, 8, 10> SvelteSizeClassMap; +typedef SizeClassMap<3, 4, 7, 16, 14, 12> AndroidSizeClassMap; +#endif + +} // namespace scudo + +#endif // SCUDO_SIZE_CLASS_MAP_H_ Index: lib/scudo/standalone/tests/CMakeLists.txt =================================================================== --- lib/scudo/standalone/tests/CMakeLists.txt +++ lib/scudo/standalone/tests/CMakeLists.txt @@ -58,6 +58,7 @@ mutex_test.cc report_test.cc secondary_test.cc + size_class_map_test.cc stats_test.cc strings_test.cc vector_test.cc Index: lib/scudo/standalone/tests/size_class_map_test.cc =================================================================== --- lib/scudo/standalone/tests/size_class_map_test.cc +++ lib/scudo/standalone/tests/size_class_map_test.cc @@ -0,0 +1,38 @@ +//===-- size_class_map_test.cc ----------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "scudo/standalone/size_class_map.h" +#include "gtest/gtest.h" + +template void testSizeClassMap() { + typedef SizeClassMap SCMap; + SCMap::print(); + SCMap::validate(); +} + +TEST(ScudoSizeClassMapTest, DefaultSizeClassMap) { + testSizeClassMap(); +} + +TEST(ScudoSizeClassMapTest, SvelteSizeClassMap) { + testSizeClassMap(); +} + +TEST(ScudoSizeClassMapTest, AndroidSizeClassMap) { + testSizeClassMap(); +} + +TEST(ScudoSizeClassMapTest, OneClassSizeClassMap) { + testSizeClassMap>(); +} + +#if SCUDO_CAN_USE_PRIMARY64 +TEST(ScudoSizeClassMapTest, LargeMaxSizeClassMap) { + testSizeClassMap>(); +} +#endif