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