1 //===-- size_map_verify_unit_tests.cpp ------------------------------------===//
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 #include "libsize_map_verify.h"
10 #include "tests/scudo_unit_test.h"
11
12 namespace scudo {
13
14 class SmokeConfigTest {
15 // This test is the base test config.
16 public:
17 static constexpr u32 Classes[] = {
18 32, 48, 64, 80, 96, 112, 144, 176, 192, 224, 288,
19 352, 448, 592, 800, 1104, 1648, 2096, 2576, 3120, 4112, 4624,
20 7120, 8720, 11664, 14224, 16400, 18448, 23056, 29456, 33296, 65552,
21 };
22 static const u32 MinSizeLog = 4;
23 static const u32 MidSizeLog = 6;
24 static const u32 MaxSizeLog = 16;
25 static const u32 NumBits = 7;
26
27 static const u32 SizeDelta = 16;
28
29 static const u32 MaxNumCachedHint = 13;
30 static const u32 MaxBytesCachedLog = 13;
31 };
TEST(ScudoToolSizeMapVerifyTest,generate_smoke_config)32 TEST(ScudoToolSizeMapVerifyTest, generate_smoke_config) {
33 std::string NumBitsMessage;
34 EXPECT_TRUE(generateNumBits<SmokeConfigTest>(NumBitsMessage));
35 EXPECT_EQ("NumBits = 7\n", NumBitsMessage);
36 }
TEST(ScudoToolSizeMapVerifyTest,verify_smoke_config)37 TEST(ScudoToolSizeMapVerifyTest, verify_smoke_config) {
38 std::string verifySizeMessage;
39 EXPECT_TRUE(verifySizeClass<SmokeConfigTest>(verifySizeMessage));
40 EXPECT_EQ("MidSizeLog non-szTable formula is used until: 80\n",
41 verifySizeMessage);
42 }
43 class SizeIncreaseConfigPass {
44 // Test shows that when every size and Min/Mid/Max changes that
45 // NumBits remains the same.
46 // Demonstrating NumBits changes based on how close the sizes
47 // are to each other.
48 public:
49 static constexpr u32 Classes[] = {
50 80, 144, 208, 272, 336, 400, 528, 656,
51 720, 848, 1104, 1360, 1744, 2320, 3152, 4368,
52 6544, 8336, 10256, 12432, 16400, 18448, 28432, 34832,
53 46608, 56848, 65552, 73744, 92176, 117776, 133136, 262160,
54 };
55 static const u32 MinSizeLog = 6;
56 static const u32 MidSizeLog = 8;
57 static const u32 MaxSizeLog = 18;
58 static const u32 NumBits = 7;
59
60 static const u32 SizeDelta = 16;
61
62 static const u32 MaxNumCachedHint = 13;
63 static const u32 MaxBytesCachedLog = 13;
64 };
TEST(ScudoToolSizeMapVerifyTest,generate_size_increase_config)65 TEST(ScudoToolSizeMapVerifyTest, generate_size_increase_config) {
66 std::string NumBitsMessage;
67 EXPECT_TRUE(generateNumBits<SizeIncreaseConfigPass>(NumBitsMessage));
68 EXPECT_EQ("NumBits = 7\n", NumBitsMessage);
69 }
TEST(ScudoToolSizeMapVerifyTest,verify_size_increase_config)70 TEST(ScudoToolSizeMapVerifyTest, verify_size_increase_config) {
71 std::string verifySizeMessage;
72 EXPECT_TRUE(verifySizeClass<SizeIncreaseConfigPass>(verifySizeMessage));
73 EXPECT_EQ("MidSizeLog non-szTable formula is used until: 272\n",
74 verifySizeMessage);
75 }
76 class MaxSizeConfigPass {
77 // This config uses the largest sizes permitted in size_class_map
78 // showing that NumBits does not need to increase due to sizes being
79 // too large and also shows the limit for MaxSizeLog.
80 // Primary allocator works up to 524304.
81 public:
82 static constexpr u32 Classes[] = {
83 144, 272, 400, 528, 656, 784, 1040, 1296,
84 1424, 1680, 2192, 2704, 3472, 4624, 6288, 8720,
85 13072, 16656, 20496, 24848, 32784, 36880, 56848, 69648,
86 93200, 113680, 131088, 147472, 184336, 235536, 266256, 524304,
87 };
88 static const u32 MinSizeLog = 7;
89 static const u32 MidSizeLog = 9;
90 static const u32 MaxSizeLog = 19;
91 static const u32 NumBits = 7;
92
93 static const u32 SizeDelta = 16;
94
95 static const u32 MaxNumCachedHint = 13;
96 static const u32 MaxBytesCachedLog = 13;
97 };
TEST(ScudoToolSizeMapVerifyTest,generate_max_size_config)98 TEST(ScudoToolSizeMapVerifyTest, generate_max_size_config) {
99 std::string NumBitsMessage;
100 EXPECT_TRUE(generateNumBits<MaxSizeConfigPass>(NumBitsMessage));
101 EXPECT_EQ("NumBits = 7\n", NumBitsMessage);
102 }
TEST(ScudoToolSizeMapVerifyTest,verify_max_size_config)103 TEST(ScudoToolSizeMapVerifyTest, verify_max_size_config) {
104 std::string verifySizeMessage;
105 EXPECT_TRUE(verifySizeClass<MaxSizeConfigPass>(verifySizeMessage));
106 EXPECT_EQ("MidSizeLog non-szTable formula is used until: 528\n",
107 verifySizeMessage);
108 }
109 class SizeDecreaseConfigFail {
110 // The NumBits decreasing causes a failure:
111 // NumBits not large enough to notice bit difference between numbers.
112 // NumBits cannot be increased due to MidSizeLog - 1 being the limit.
113 public:
114 static constexpr u32 Classes[] = {
115 24, 32, 40, 48, 56, 64, 80, 96, 104, 120, 152,
116 184, 232, 304, 408, 560, 832, 1056, 1296, 1568, 2064, 2320,
117 3568, 4368, 5840, 7120, 8208, 9232, 11536, 14736, 16656, 32784,
118 };
119 static const u32 MinSizeLog = 3;
120 static const u32 MidSizeLog = 5;
121 static const u32 MaxSizeLog = 15;
122 static const u32 NumBits = 6;
123
124 static const u32 SizeDelta = 16;
125
126 static const u32 MaxNumCachedHint = 13;
127 static const u32 MaxBytesCachedLog = 13;
128 };
TEST(ScudoToolSizeMapVerifyTest,generate_size_decrease_config)129 TEST(ScudoToolSizeMapVerifyTest, generate_size_decrease_config) {
130 std::string NumBitsMessage;
131 EXPECT_FALSE(generateNumBits<SizeDecreaseConfigFail>(NumBitsMessage));
132 EXPECT_NE("NumBits = 7\n", NumBitsMessage);
133 }
TEST(ScudoToolSizeMapVerifyTest,verify_size_decrease_config)134 TEST(ScudoToolSizeMapVerifyTest, verify_size_decrease_config) {
135 std::string verifySizeMessage;
136 EXPECT_FALSE(verifySizeClass<SizeDecreaseConfigFail>(verifySizeMessage));
137 EXPECT_EQ(
138 "MidSizeLog non-szTable formula is used until: 48\n\nNumBits not "
139 "large enough to distinguish between values. \nHard max NumBits - 1 "
140 "cannot exceed MidSizeLog.\nIf NumBits is at max then increase "
141 "Min/Mid/Max sizelogs and increase the sizes accordingly.\n\n\n",
142 verifySizeMessage);
143 }
144 class MidSizeLog10ConfigPass {
145 // Expands the use of the non-table formula to 1040.
146 // Shows how to expand the non-table formula by increasing MidSizeLog and
147 // by ensuring an equal step between sizes up to MidSizeLog.
148 // Shows the tool's ability to use a larger MidSizeLog and a smaller szTable.
149 // Demonstrates how many sizes are needed to increase the MidSizeLog.
150 public:
151 static constexpr u32 Classes[] = {
152 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192,
153 208, 224, 240, 256, 272, 288, 304, 320, 336, 352, 368,
154 384, 400, 416, 432, 448, 464, 480, 496, 512, 528, 544,
155 560, 576, 592, 608, 624, 640, 656, 672, 688, 704, 720,
156 736, 752, 768, 784, 800, 816, 832, 848, 864, 880, 896,
157 912, 928, 944, 960, 976, 992, 1008, 1024, 1040, 1104, 1648,
158 2096, 2576, 3120, 4112, 4624, 7120, 8720, 11664, 14224, 16400, 18448,
159 23056, 29456, 33296, 65552,
160 };
161 static const u32 MinSizeLog = 4;
162 static const u32 MidSizeLog = 10;
163 static const u32 MaxSizeLog = 16;
164 static const u32 NumBits = 7;
165
166 static const u32 SizeDelta = 16;
167
168 static const u32 MaxNumCachedHint = 13;
169 static const u32 MaxBytesCachedLog = 13;
170 };
TEST(ScudoToolSizeMapVerifyTest,generate_midsizelog_10_config)171 TEST(ScudoToolSizeMapVerifyTest, generate_midsizelog_10_config) {
172 std::string NumBitsMessage;
173 EXPECT_TRUE(generateNumBits<MidSizeLog10ConfigPass>(NumBitsMessage));
174 EXPECT_EQ("NumBits = 7\n", NumBitsMessage);
175 }
TEST(ScudoToolSizeMapVerifyTest,verify_midsizelog_10_config)176 TEST(ScudoToolSizeMapVerifyTest, verify_midsizelog_10_config) {
177 std::string verifySizeMessage;
178 EXPECT_TRUE(verifySizeClass<MidSizeLog10ConfigPass>(verifySizeMessage));
179 EXPECT_EQ("MidSizeLog non-szTable formula is used until: 1040\n",
180 verifySizeMessage);
181 }
182 class NumBitsIncreaseConfigPass {
183 // Demonstrates when to increase NumBits and how to do it.
184 // Ensure NumBits - 1 <= MidSizeLog, with an equal step until MidSizeLog.
185 // Increasing NumBits allows more bits to be checked when analyzing sizes
186 // NumBits 8 checks 7 bits from the most-significant-bit-index.
187 // Here NumBits 8 is needed for the sizes 288 and 290.
188 // Shows NumBits increases szTable's flexibility for new sizes.
189 // Another condition to remember:
190 // Sizes cannot be just 1 larger than previous size.
191 public:
192 static constexpr u32 Classes[] = {
193 32, 48, 64, 80, 96, 112, 128, 144, 176,
194 192, 224, 288, 290, 352, 448, 592, 800, 1104,
195 1648, 2096, 2576, 3120, 4112, 4624, 7120, 8720, 11664,
196 14224, 16400, 18448, 23056, 29456, 33296, 65552,
197 };
198 static const u32 MinSizeLog = 4;
199 static const u32 MidSizeLog = 7;
200 static const u32 MaxSizeLog = 16;
201 static const u32 NumBits = 8;
202
203 static const u32 SizeDelta = 16;
204
205 static const u32 MaxNumCachedHint = 13;
206 static const u32 MaxBytesCachedLog = 13;
207 };
TEST(ScudoToolSizeMapVerifyTest,generate_numbits_increase_config)208 TEST(ScudoToolSizeMapVerifyTest, generate_numbits_increase_config) {
209 std::string NumBitsMessage;
210 EXPECT_TRUE(generateNumBits<NumBitsIncreaseConfigPass>(NumBitsMessage));
211 EXPECT_EQ("NumBits = 8\n", NumBitsMessage);
212 }
TEST(ScudoToolSizeMapVerifyTest,verify_numbits_increase_config)213 TEST(ScudoToolSizeMapVerifyTest, verify_numbits_increase_config) {
214 std::string verifySizeMessage;
215 EXPECT_TRUE(verifySizeClass<NumBitsIncreaseConfigPass>(verifySizeMessage));
216 EXPECT_EQ("MidSizeLog non-szTable formula is used until: 144\n",
217 verifySizeMessage);
218 }
219 class MidEqualMaxConfigPass {
220 // The equality of MidSizeLog and MaxSizeLog shows how the szTable
221 // does not need to be used, which makes NumBits obselete.
222 // The test shows that the formula can be used for every size.
223 public:
224 static constexpr u32 Classes[] = {
225 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224,
226 240, 256, 272, 288, 304, 320, 336, 352, 368, 384, 400, 416, 432,
227 448, 464, 480, 496, 512, 528, 544, 560, 576, 592, 608, 624, 640,
228 656, 672, 688, 704, 720, 736, 752, 768, 784, 800, 816, 832, 848,
229 864, 880, 896, 912, 928, 944, 960, 976, 992, 1008, 1024, 1040,
230 };
231 static const u32 MinSizeLog = 4;
232 static const u32 MidSizeLog = 10;
233 static const u32 MaxSizeLog = 10;
234 static const u32 NumBits = 7;
235
236 static const u32 SizeDelta = 16;
237
238 static const u32 MaxNumCachedHint = 13;
239 static const u32 MaxBytesCachedLog = 13;
240 };
TEST(ScudoToolSizeMapVerifyTest,generate_mid_equal_max_config)241 TEST(ScudoToolSizeMapVerifyTest, generate_mid_equal_max_config) {
242 std::string NumBitsMessage;
243 EXPECT_TRUE(generateNumBits<MidEqualMaxConfigPass>(NumBitsMessage));
244 EXPECT_EQ(
245 "MidSizeLog = MaxSizeLog, NumBits not used for these sizes. Only uses "
246 "the formula without szTable.\n",
247 NumBitsMessage);
248 }
TEST(ScudoToolSizeMapVerifyTest,verify_mid_equal_max_config)249 TEST(ScudoToolSizeMapVerifyTest, verify_mid_equal_max_config) {
250 std::string verifySizeMessage;
251 EXPECT_TRUE(verifySizeClass<MidEqualMaxConfigPass>(verifySizeMessage));
252 EXPECT_EQ("MidSizeLog non-szTable formula is used until: 1040\nMidSizeLog = "
253 "MaxSizeLog, szTable and NumBits are not used at all.\n",
254 verifySizeMessage);
255 }
256 class SizeDeltaConfigPass {
257 // Test shows that when changing SizeDelta, min and max have to
258 // change to match.
259 // Every size needs to change by whatever the SizeDelta changed by.
260 // Sizes need to be added to make Mid match.
261 public:
262 static constexpr u32 Classes[] = {
263 16, 24, 32, 40, 48, 56, 64, 72, 88,
264 104, 136, 168, 184, 216, 280, 344, 440, 584,
265 792, 1096, 1640, 2088, 2568, 3112, 4104, 4616, 7112,
266 8712, 11656, 14216, 16392, 18440, 23048, 29448, 33288, 65544,
267 };
268 static const u32 MinSizeLog = 3;
269 static const u32 MidSizeLog = 6;
270 static const u32 MaxSizeLog = 16;
271 static const u32 NumBits = 7;
272
273 static const u32 SizeDelta = 8;
274
275 static const u32 MaxNumCachedHint = 13;
276 static const u32 MaxBytesCachedLog = 13;
277 };
TEST(ScudoToolSizeMapVerifyTest,generate_size_delta_config)278 TEST(ScudoToolSizeMapVerifyTest, generate_size_delta_config) {
279 std::string NumBitsMessage;
280 EXPECT_TRUE(generateNumBits<SizeDeltaConfigPass>(NumBitsMessage));
281 EXPECT_EQ("NumBits = 7\n", NumBitsMessage);
282 }
TEST(ScudoToolSizeMapVerifyTest,verify_size_delta_config)283 TEST(ScudoToolSizeMapVerifyTest, verify_size_delta_config) {
284 std::string verifySizeMessage;
285 EXPECT_TRUE(verifySizeClass<SizeDeltaConfigPass>(verifySizeMessage));
286 EXPECT_EQ("MidSizeLog non-szTable formula is used until: 72\n",
287 verifySizeMessage);
288 }
289 } // namespace scudo