1 /*
2 * Copyright (c) 2020, 2024, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2020 SAP SE. All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26 #include "precompiled.hpp"
27 #include "memory/metaspace/blockTree.hpp"
28 #include "memory/metaspace/counters.hpp"
29 #include "memory/resourceArea.hpp"
30 // #define LOG_PLEASE
31 #include "metaspaceGtestCommon.hpp"
32
33 using metaspace::BlockTree;
34 using metaspace::MemRangeCounter;
35
36 // Small helper. Given a 0-terminated array of sizes, a feeder buffer and a tree,
37 // add blocks of these sizes to the tree in the order they appear in the array.
38 static void create_nodes(const size_t sizes[], FeederBuffer& fb, BlockTree& bt) {
39 for (int i = 0; sizes[i] > 0; i ++) {
40 size_t s = sizes[i];
41 MetaWord* p = fb.get(s);
42 bt.add_block(p, s);
43 }
44 }
45
46 #define CHECK_BT_CONTENT(bt, expected_num, expected_size) { \
47 EXPECT_EQ(bt.count(), (unsigned)expected_num); \
48 EXPECT_EQ(bt.total_size(), (size_t)expected_size); \
49 if (expected_num == 0) { \
50 EXPECT_TRUE(bt.is_empty()); \
51 } else { \
52 EXPECT_FALSE(bt.is_empty()); \
53 } \
54 }
55
56 TEST_VM(metaspace, BlockTree_basic) {
57
58 BlockTree bt;
59 CHECK_BT_CONTENT(bt, 0, 0);
60
61 size_t real_size = 0;
62 MetaWord* p = nullptr;
63 MetaWord arr[10000];
64
65 ASSERT_LE(BlockTree::MinWordSize, (size_t)6); // Sanity check. Adjust if Node is changed.
66
67 const size_t minws = BlockTree::MinWordSize;
68
69 // remove_block from empty tree should yield nothing
70 p = bt.remove_block(minws, &real_size);
71 EXPECT_NULL(p);
72 EXPECT_0(real_size);
73 CHECK_BT_CONTENT(bt, 0, 0);
74
75 // Add some blocks and retrieve them right away.
76 size_t sizes[] = {
77 minws, // smallest possible
78 minws + 10,
79 1024,
80 4711,
81 0
82 };
83
84 for (int i = 0; sizes[i] > 0; i++) {
85 bt.add_block(arr, sizes[i]);
86 CHECK_BT_CONTENT(bt, 1, sizes[i]);
87
88 DEBUG_ONLY(bt.verify();)
89
90 MetaWord* p = bt.remove_block(sizes[i], &real_size);
91 EXPECT_EQ(p, arr);
92 EXPECT_EQ(real_size, (size_t)sizes[i]);
93 CHECK_BT_CONTENT(bt, 0, 0);
94 }
95
96 }
97
98 // Helper for test_find_nearest_fit_with_tree.
99 // Out of an array of sizes return the closest upper match to a requested size.
100 // Returns SIZE_MAX if none found.
101 static size_t helper_find_nearest_fit(const size_t sizes[], size_t request_size) {
102 size_t best = SIZE_MAX;
103 for (int i = 0; sizes[i] > 0; i++) {
104 if (sizes[i] >= request_size && sizes[i] < best) {
105 best = sizes[i];
106 }
107 }
108 return best;
109 }
110
111 // Given a sequence of (0-terminated) sizes, add blocks of those sizes to the tree in the order given. Then, ask
112 // for a request size and check that it is the expected result.
113 static void test_find_nearest_fit_with_tree(const size_t sizes[], size_t request_size) {
114
115 BlockTree bt;
116 FeederBuffer fb(4 * K);
117
118 create_nodes(sizes, fb, bt);
119
120 DEBUG_ONLY(bt.verify();)
121
122 size_t expected_size = helper_find_nearest_fit(sizes, request_size);
123 size_t real_size = 0;
124 MetaWord* p = bt.remove_block(request_size, &real_size);
125
126 if (expected_size != SIZE_MAX) {
127 EXPECT_NOT_NULL(p);
128 EXPECT_EQ(real_size, expected_size);
129 } else {
130 EXPECT_NULL(p);
131 EXPECT_0(real_size);
132 }
133
134 LOG(SIZE_FORMAT ": " SIZE_FORMAT ".", request_size, real_size);
135
136 }
137
138 TEST_VM(metaspace, BlockTree_find_nearest_fit) {
139
140 // Test tree for test_find_nearest_fit looks like this
141 // 30
142 // / \
143 // / \
144 // / \
145 // 17 50
146 // / \ / \
147 // / \ / \
148 // 10 28 32 51
149 // \
150 // 35
151
152 static const size_t sizes[] = {
153 30, 17, 10, 28,
154 50, 32, 51, 35,
155 0 // stop
156 };
157
158 BlockTree bt;
159 FeederBuffer fb(4 * K);
160
161 create_nodes(sizes, fb, bt);
162
163 for (int i = BlockTree::MinWordSize; i <= 60; i ++) {
164 test_find_nearest_fit_with_tree(sizes, i);
165 }
166
167 }
168
169 // Test repeated adding and removing of blocks of the same size, which
170 // should exercise the list-part of the tree.
171 TEST_VM(metaspace, BlockTree_basic_siblings)
172 {
173 BlockTree bt;
174 FeederBuffer fb(4 * K);
175
176 CHECK_BT_CONTENT(bt, 0, 0);
177
178 const size_t test_size = BlockTree::MinWordSize;
179 const int num = 10;
180
181 for (int i = 0; i < num; i++) {
182 bt.add_block(fb.get(test_size), test_size);
183 CHECK_BT_CONTENT(bt, i + 1, (i + 1) * test_size);
184 }
185
186 DEBUG_ONLY(bt.verify();)
187
188 for (int i = num; i > 0; i --) {
189 size_t real_size = 4711;
190 MetaWord* p = bt.remove_block(test_size, &real_size);
191 EXPECT_TRUE(fb.is_valid_pointer(p));
192 EXPECT_EQ(real_size, (size_t)test_size);
193 CHECK_BT_CONTENT(bt, i - 1, (i - 1) * test_size);
194 }
195
196 }
197
198 #ifdef ASSERT
199 TEST_VM(metaspace, BlockTree_print_test) {
200
201 static const size_t sizes[] = {
202 30, 17, 10, 28,
203 50, 32, 51, 35,
204 0 // stop
205 };
206
207 BlockTree bt;
208 FeederBuffer fb(4 * K);
209
210 create_nodes(sizes, fb, bt);
211
212 ResourceMark rm;
213
214 stringStream ss;
215 bt.print_tree(&ss);
216
217 LOG("%s", ss.as_string());
218 }
219
220 // Test that an overwritten node would result in an assert and a printed tree
221 TEST_VM_ASSERT_MSG(metaspace, BlockTree_overwriter_test, ".*failed: Invalid node") {
222 static const size_t sizes1[] = { 30, 17, 0 };
223 static const size_t sizes2[] = { 12, 12, 0 };
224
225 BlockTree bt;
226 FeederBuffer fb(4 * K);
227
228 // some nodes...
229 create_nodes(sizes1, fb, bt);
230
231 // a node we will break...
232 MetaWord* p_broken = fb.get(12);
233 bt.add_block(p_broken, 12);
234
235 // some more nodes...
236 create_nodes(sizes2, fb, bt);
237
238 // overwrite node memory (only the very first byte), then verify tree.
239 // Verification should catch the broken canary, print the tree,
240 // then assert.
241 LOG("Will break node at " PTR_FORMAT ".", p2i(p_broken));
242 tty->print_cr("Death test, please ignore the following \"Invalid node\" printout.");
243 *((char*)p_broken) = '\0';
244 bt.verify();
245 }
246 #endif
247
248 class BlockTreeTest {
249
250 FeederBuffer _fb;
251
252 BlockTree _bt[2];
253 MemRangeCounter _cnt[2];
254
255 RandSizeGenerator _rgen;
256
257 #define CHECK_COUNTERS \
258 CHECK_BT_CONTENT(_bt[0], _cnt[0].count(), _cnt[0].total_size()) \
259 CHECK_BT_CONTENT(_bt[1], _cnt[1].count(), _cnt[1].total_size())
260
261 #define CHECK_COUNTERS_ARE_0 \
262 CHECK_BT_CONTENT(_bt[0], 0, 0) \
263 CHECK_BT_CONTENT(_bt[1], 0, 0)
264
265 #ifdef ASSERT
266 void verify_trees() {
267 _bt[0].verify();
268 _bt[1].verify();
269 }
270 #endif
271
272 enum feeding_pattern_t {
273 scatter = 1,
274 left_right = 2,
275 right_left = 3
276 };
277
278 // Feed the whole feeder buffer to the trees, according to feeding_pattern.
279 void feed_all(feeding_pattern_t feeding_pattern) {
280
281 MetaWord* p = nullptr;
282 unsigned added = 0;
283
284 // If we feed in small graining, we cap the number of blocks to limit test duration.
285 const unsigned max_blocks = 2000;
286
287 size_t old_feeding_size = feeding_pattern == right_left ? _rgen.max() : _rgen.min();
288 do {
289 size_t s = 0;
290 switch (feeding_pattern) {
291 case scatter:
292 // fill completely random
293 s =_rgen.get();
294 break;
295 case left_right:
296 // fill in ascending order to provoke a misformed tree.
297 s = MIN2(_rgen.get(), old_feeding_size);
298 old_feeding_size = s;
299 break;
300 case right_left:
301 // same, but descending.
302 s = MAX2(_rgen.get(), old_feeding_size);
303 old_feeding_size = s;
304 break;
305 }
306
307 // Get a block from the feeder buffer; feed it alternatingly to either tree.
308 p = _fb.get(s);
309 if (p != nullptr) {
310 int which = added % 2;
311 added++;
312 _bt[which].add_block(p, s);
313 _cnt[which].add(s);
314 CHECK_COUNTERS
315 }
316 } while (p != nullptr && added < max_blocks);
317
318 DEBUG_ONLY(verify_trees();)
319
320 // Trees should contain the same number of nodes (+-1)
321 EXPECT_TRUE(_bt[0].count() == _bt[1].count() ||
322 _bt[0].count() == _bt[1].count() + 1);
323
324 }
325
326 void ping_pong_loop(int iterations) {
327
328 // We loop and in each iteration randomly retrieve a block from one tree and add it to another.
329 for (int i = 0; i < iterations; i++) {
330 int taker = 0;
331 int giver = 1;
332 if ((os::random() % 10) > 5) {
333 giver = 0; taker = 1;
334 }
335 size_t s =_rgen.get();
336 size_t real_size = 0;
337 MetaWord* p = _bt[giver].remove_block(s, &real_size);
338 if (p != nullptr) {
339 ASSERT_TRUE(_fb.is_valid_range(p, real_size));
340 ASSERT_GE(real_size, s);
341 _bt[taker].add_block(p, real_size);
342 _cnt[giver].sub(real_size);
343 _cnt[taker].add(real_size);
344 CHECK_COUNTERS;
345 }
346
347 #ifdef ASSERT
348 if (true) {//i % 1000 == 0) {
349 verify_trees();
350 }
351 #endif
352 }
353 }
354
355 // Drain the trees. While draining, observe the order of the drained items.
356 void drain_all() {
357
358 for (int which = 0; which < 2; which++) {
359 BlockTree* bt = _bt + which;
360 size_t last_size = 0;
361 while (!bt->is_empty()) {
362
363 // We only query for the minimal size. Actually returned size should be
364 // monotonously growing since remove_block should always return the closest fit.
365 size_t real_size = 4711;
366 MetaWord* p = bt->remove_block(BlockTree::MinWordSize, &real_size);
367 ASSERT_TRUE(_fb.is_valid_range(p, real_size));
368
369 ASSERT_GE(real_size, last_size);
370 last_size = real_size;
371
372 _cnt[which].sub(real_size);
373 CHECK_COUNTERS;
374
375 DEBUG_ONLY(bt->verify();)
376
377 }
378 }
379
380 }
381
382 void test(feeding_pattern_t feeding_pattern) {
383
384 CHECK_COUNTERS_ARE_0
385
386 feed_all(feeding_pattern);
387
388 LOG("Blocks in circulation: bt1=%d:" SIZE_FORMAT ", bt2=%d:" SIZE_FORMAT ".",
389 _bt[0].count(), _bt[0].total_size(),
390 _bt[1].count(), _bt[1].total_size());
391
392 ping_pong_loop(5000);
393
394 LOG("After Pingpong: bt1=%d:" SIZE_FORMAT ", bt2=%d:" SIZE_FORMAT ".",
395 _bt[0].count(), _bt[0].total_size(),
396 _bt[1].count(), _bt[1].total_size());
397
398 drain_all();
399
400 CHECK_COUNTERS_ARE_0
401 }
402
403 public:
404
405 BlockTreeTest(size_t min_word_size, size_t max_word_size) :
406 _fb(2 * M),
407 _bt(),
408 _rgen(min_word_size, max_word_size)
409 {
410 CHECK_COUNTERS;
411 DEBUG_ONLY(verify_trees();)
412 }
413
414 void test_scatter() { test(scatter); }
415 void test_right_left() { test(right_left); }
416 void test_left_right() { test(left_right); }
417
418 };
419
420 #define DO_TEST(name, feedingpattern, min, max) \
421 TEST_VM(metaspace, BlockTree_##name##_##feedingpattern) { \
422 BlockTreeTest btt(min, max); \
423 btt.test_##feedingpattern(); \
424 }
425
426 #define DO_TEST_ALL_PATTERNS(name, min, max) \
427 DO_TEST(name, scatter, min, max) \
428 DO_TEST(name, right_left, min, max) \
429 DO_TEST(name, left_right, min, max)
430
431 DO_TEST_ALL_PATTERNS(wide, BlockTree::MinWordSize, 128 * K);
432 DO_TEST_ALL_PATTERNS(narrow, BlockTree::MinWordSize, 16)
433 DO_TEST_ALL_PATTERNS(129, BlockTree::MinWordSize, 129)
434 DO_TEST_ALL_PATTERNS(4K, BlockTree::MinWordSize, 4*K)
435