< prev index next >
test/hotspot/gtest/metaspace/test_blocktree.cpp
Print this page
rev 60811 : imported patch jep387-all.patch
rev 60812 : [mq]: diff1
@@ -1,8 +1,8 @@
/*
- * Copyright (c) 2018, 2020, Oracle and/or its affiliates. All rights reserved.
- * Copyright (c) 2018, 2020 SAP SE. All rights reserved.
+ * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2020 SAP SE. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
@@ -23,14 +23,29 @@
*
*/
#include "precompiled.hpp"
-//#define LOG_PLEASE
-
-#include "metaspaceTestsCommon.hpp"
-
+#include "memory/metaspace/msBlockTree.hpp"
+#include "memory/metaspace/msCounter.hpp"
+#include "memory/resourceArea.hpp"
+
+// #define LOG_PLEASE
+#include "metaspaceGtestCommon.hpp"
+
+using metaspace::BlockTree;
+using metaspace::MemRangeCounter;
+
+// Small helper. Given a 0-terminated array of sizes, a feeder buffer and a tree,
+// add blocks of these sizes to the tree in the order they appear in the array.
+static void create_nodes(const size_t sizes[], FeederBuffer& fb, BlockTree& bt) {
+ for (int i = 0; sizes[i] > 0; i ++) {
+ size_t s = sizes[i];
+ MetaWord* p = fb.get(s);
+ bt.add_block(p, s);
+ }
+}
#define CHECK_BT_CONTENT(bt, expected_num, expected_size) { \
EXPECT_EQ(bt.count(), (unsigned)expected_num); \
EXPECT_EQ(bt.total_size(), (size_t)expected_size); \
if (expected_num == 0) { \
@@ -47,126 +62,167 @@
size_t real_size = 0;
MetaWord* p = NULL;
MetaWord arr[10000];
- const size_t minws = BlockTree::minimal_word_size;
- const size_t maxws = 4096;
+ ASSERT_LE(BlockTree::MinWordSize, (size_t)6); // Sanity check. Adjust if Node is changed.
- // get_block from empty tree should yield nothing
- p = bt.get_block(minws, &real_size);
- EXPECT_EQ(p, (MetaWord*)NULL);
- EXPECT_EQ(real_size, (size_t)0);
+ const size_t minws = BlockTree::MinWordSize;
+
+ // remove_block from empty tree should yield nothing
+ p = bt.remove_block(minws, &real_size);
+ EXPECT_NULL(p);
+ EXPECT_0(real_size);
CHECK_BT_CONTENT(bt, 0, 0);
// Add some blocks and retrieve them right away.
size_t sizes[] = {
- minws + 10,
- maxws - 10,
minws, // smallest possible
- maxws - 1, // largest possible
+ minws + 10,
+ 1024,
+ 4711,
0
};
- for (int i = 0; sizes[i] > 0; i ++) {
+ for (int i = 0; sizes[i] > 0; i++) {
bt.add_block(arr, sizes[i]);
CHECK_BT_CONTENT(bt, 1, sizes[i]);
DEBUG_ONLY(bt.verify();)
- MetaWord* p = bt.get_block(sizes[i], &real_size);
+ MetaWord* p = bt.remove_block(sizes[i], &real_size);
EXPECT_EQ(p, arr);
EXPECT_EQ(real_size, (size_t)sizes[i]);
CHECK_BT_CONTENT(bt, 0, 0);
}
}
-TEST_VM(metaspace, BlockTree_closest_fit) {
+// Helper for test_find_nearest_fit_with_tree.
+// Out of an array of sizes return the closest upper match to a requested size.
+// Returns SIZE_MAX if none found.
+static size_t helper_find_nearest_fit(const size_t sizes[], size_t request_size) {
+ size_t best = SIZE_MAX;
+ for (int i = 0; sizes[i] > 0; i++) {
+ if (sizes[i] >= request_size && sizes[i] < best) {
+ best = sizes[i];
+ }
+ }
+ return best;
+}
+
+// Given a sequence of (0-terminated) sizes, add blocks of those sizes to the tree in the order given. Then, ask
+// for a request size and check that it is the expected result.
+static void test_find_nearest_fit_with_tree(const size_t sizes[], size_t request_size) {
- // Test the fact that getting blocks should always return the closest fit
BlockTree bt;
- FeederBuffer fb(10000);
+ FeederBuffer fb(4 * K);
- const size_t minws = BlockTree::minimal_word_size;
- const size_t maxws = 256;
+ create_nodes(sizes, fb, bt);
- size_t sizes[] = {
- minws + 9,
- minws + 3,
- minws + 9,
- minws,
- minws + 8,
- maxws - 2,
- minws,
- maxws - 1,
- 0
- };
+ DEBUG_ONLY(bt.verify();)
- size_t size_added = 0;
- int num_added = 0;
+ size_t expected_size = helper_find_nearest_fit(sizes, request_size);
+ size_t real_size = 0;
+ MetaWord* p = bt.remove_block(request_size, &real_size);
- for (int i = 0; sizes[i] > 0; i ++) {
- const size_t s = sizes[i];
- MetaWord* p = fb.get(s);
- bt.add_block(p, s);
- num_added ++; size_added += s;
- CHECK_BT_CONTENT(bt, num_added, size_added);
+ if (expected_size != SIZE_MAX) {
+ EXPECT_NOT_NULL(p);
+ EXPECT_EQ(real_size, expected_size);
+ } else {
+ EXPECT_NULL(p);
+ EXPECT_0(real_size);
}
- DEBUG_ONLY(bt.verify();)
+ LOG(SIZE_FORMAT ": " SIZE_FORMAT ".", request_size, real_size);
- size_t last_size = 0;
- while (bt.is_empty() == false) {
- size_t real_size = 0;
- MetaWord* p = bt.get_block(minws, &real_size);
- EXPECT_TRUE(fb.is_valid_range(p, real_size));
+}
- EXPECT_GE(real_size, last_size);
- last_size = real_size;
+TEST_VM(metaspace, BlockTree_find_nearest_fit) {
- num_added --;
- size_added -= real_size;
- CHECK_BT_CONTENT(bt, num_added, size_added);
- }
+ // Test tree for test_find_nearest_fit looks like this
+ // 30
+ // / \
+ // / \
+ // / \
+ // 17 50
+ // / \ / \
+ // / \ / \
+ // 10 28 32 51
+ // \
+ // 35
+
+ static const size_t sizes[] = {
+ 30, 17, 10, 28,
+ 50, 32, 51, 35,
+ 0 // stop
+ };
- CHECK_BT_CONTENT(bt, 0, 0);
+ BlockTree bt;
+ FeederBuffer fb(4 * K);
-}
+ create_nodes(sizes, fb, bt);
+ for (int i = BlockTree::MinWordSize; i <= 60; i ++) {
+ test_find_nearest_fit_with_tree(sizes, i);
+ }
+
+}
+// Test repeated adding and removing of blocks of the same size, which
+// should exercise the list-part of the tree.
TEST_VM(metaspace, BlockTree_basic_siblings)
{
BlockTree bt;
+ FeederBuffer fb(4 * K);
+
CHECK_BT_CONTENT(bt, 0, 0);
- const size_t minws = BlockTree::minimal_word_size;
- const size_t maxws = 256;
- const size_t test_size = minws + 17;
+ const size_t test_size = BlockTree::MinWordSize;
const int num = 10;
- MetaWord* arr = NEW_C_HEAP_ARRAY(MetaWord, num * test_size, mtInternal);
-
- for (int i = 0; i < num; i ++) {
- bt.add_block(arr + (i * test_size), test_size);
+ for (int i = 0; i < num; i++) {
+ bt.add_block(fb.get(test_size), test_size);
CHECK_BT_CONTENT(bt, i + 1, (i + 1) * test_size);
}
DEBUG_ONLY(bt.verify();)
for (int i = num; i > 0; i --) {
size_t real_size = 4711;
- MetaWord* p = bt.get_block(test_size, &real_size);
- EXPECT_LT(p, arr + num * test_size);
- EXPECT_GE(p, arr);
+ MetaWord* p = bt.remove_block(test_size, &real_size);
+ EXPECT_TRUE(fb.is_valid_pointer(p));
EXPECT_EQ(real_size, (size_t)test_size);
CHECK_BT_CONTENT(bt, i - 1, (i - 1) * test_size);
}
- FREE_C_HEAP_ARRAY(MetaWord, arr);
}
+#ifdef ASSERT
+TEST_VM(metaspace, BlockTree_print_test) {
+
+ static const size_t sizes[] = {
+ 30, 17, 10, 28,
+ 50, 32, 51, 35,
+ 0 // stop
+ };
+
+ BlockTree bt;
+ FeederBuffer fb(4 * K);
+
+ create_nodes(sizes, fb, bt);
+
+ ResourceMark rm;
+
+ stringStream ss;
+ bt.print_tree(&ss);
+
+ LOG("%s", ss.as_string());
+
+}
+#endif
+
class BlockTreeTest {
FeederBuffer _fb;
BlockTree _bt[2];
@@ -193,13 +249,13 @@
scatter = 1,
left_right = 2,
right_left = 3
};
+ // Feed the whole feeder buffer to the trees, according to feeding_pattern.
void feed_all(feeding_pattern_t feeding_pattern) {
- // Feed the whole feaderbuffer space to the trees.
MetaWord* p = NULL;
unsigned added = 0;
// If we feed in small graining, we cap the number of blocks to limit test duration.
const unsigned max_blocks = 2000;
@@ -211,54 +267,53 @@
case scatter:
// fill completely random
s =_rgen.get();
break;
case left_right:
- // fill in ascending order to annoy trees.
+ // fill in ascending order to provoke a misformed tree.
s = MIN2(_rgen.get(), old_feeding_size);
old_feeding_size = s;
break;
case right_left:
// same, but descending.
s = MAX2(_rgen.get(), old_feeding_size);
old_feeding_size = s;
break;
}
+ // Get a block from the feeder buffer; feed it alternatingly to either tree.
p = _fb.get(s);
if (p != NULL) {
int which = added % 2;
- added ++;
+ added++;
_bt[which].add_block(p, s);
_cnt[which].add(s);
CHECK_COUNTERS
}
- DEBUG_ONLY(verify_trees();)
- CHECK_COUNTERS;
} while (p != NULL && added < max_blocks);
- // Trees should be populated in a balanced way, and not empty
- EXPECT_TRUE( _bt[0].count() == _bt[1].count() ||
- (_bt[0].count() == _bt[1].count() + 1 && _bt[0].count() > 0));
+ DEBUG_ONLY(verify_trees();)
+
+ // Trees should contain the same number of nodes (+-1)
+ EXPECT_TRUE(_bt[0].count() == _bt[1].count() ||
+ _bt[0].count() == _bt[1].count() + 1);
}
void ping_pong_loop(int iterations) {
// We loop and in each iteration randomly retrieve a block from one tree and add it to another.
- for (int i = 0; i < iterations; i ++) {
+ for (int i = 0; i < iterations; i++) {
int taker = 0;
int giver = 1;
if ((os::random() % 10) > 5) {
giver = 0; taker = 1;
}
size_t s =_rgen.get();
size_t real_size = 0;
- MetaWord* p = _bt[giver].get_block(s, &real_size);
- if (p == NULL) {
- // Todo: check that bt really has no larger block than this.
- } else {
+ MetaWord* p = _bt[giver].remove_block(s, &real_size);
+ if (p != NULL) {
ASSERT_TRUE(_fb.is_valid_range(p, real_size));
ASSERT_GE(real_size, s);
_bt[taker].add_block(p, real_size);
_cnt[giver].sub(real_size);
_cnt[taker].add(real_size);
@@ -274,32 +329,29 @@
}
// Drain the trees. While draining, observe the order of the drained items.
void drain_all() {
- for (int which = 0; which < 2; which ++) {
+ for (int which = 0; which < 2; which++) {
BlockTree* bt = _bt + which;
size_t last_size = 0;
while(!bt->is_empty()) {
// We only query for the minimal size. Actually returned size should be
- // monotonously growing since get_block should always return the closest fit.
+ // monotonously growing since remove_block should always return the closest fit.
size_t real_size = 4711;
- MetaWord* p = bt->get_block(BlockTree::minimal_word_size, &real_size);
+ MetaWord* p = bt->remove_block(BlockTree::MinWordSize, &real_size);
ASSERT_TRUE(_fb.is_valid_range(p, real_size));
ASSERT_GE(real_size, last_size);
last_size = real_size;
_cnt[which].sub(real_size);
CHECK_COUNTERS;
-#ifdef ASSERT
- if (true) {//i % 1000 == 0) {
- bt->verify();
- }
-#endif
+ DEBUG_ONLY(bt->verify();)
+
}
}
}
@@ -311,22 +363,21 @@
LOG("Blocks in circulation: bt1=%d:" SIZE_FORMAT ", bt2=%d:" SIZE_FORMAT ".",
_bt[0].count(), _bt[0].total_size(),
_bt[1].count(), _bt[1].total_size());
- ping_pong_loop(2000);
+ ping_pong_loop(5000);
LOG("After Pingpong: bt1=%d:" SIZE_FORMAT ", bt2=%d:" SIZE_FORMAT ".",
_bt[0].count(), _bt[0].total_size(),
_bt[1].count(), _bt[1].total_size());
drain_all();
CHECK_COUNTERS_ARE_0
}
-
public:
BlockTreeTest(size_t min_word_size, size_t max_word_size) :
_fb(2 * M),
_bt(),
@@ -334,11 +385,10 @@
{
CHECK_COUNTERS;
DEBUG_ONLY(verify_trees();)
}
-
void test_scatter() { test(scatter); }
void test_right_left() { test(right_left); }
void test_left_right() { test(left_right); }
};
@@ -352,13 +402,10 @@
#define DO_TEST_ALL_PATTERNS(name, min, max) \
DO_TEST(name, scatter, min, max) \
DO_TEST(name, right_left, min, max) \
DO_TEST(name, left_right, min, max)
-
-DO_TEST_ALL_PATTERNS(wide, BlockTree::minimal_word_size, 128 * K);
-DO_TEST_ALL_PATTERNS(narrow, BlockTree::minimal_word_size, 16)
-DO_TEST_ALL_PATTERNS(129, BlockTree::minimal_word_size, 129)
-DO_TEST_ALL_PATTERNS(4K, BlockTree::minimal_word_size, 4*K)
-
-
+DO_TEST_ALL_PATTERNS(wide, BlockTree::MinWordSize, 128 * K);
+DO_TEST_ALL_PATTERNS(narrow, BlockTree::MinWordSize, 16)
+DO_TEST_ALL_PATTERNS(129, BlockTree::MinWordSize, 129)
+DO_TEST_ALL_PATTERNS(4K, BlockTree::MinWordSize, 4*K)
< prev index next >