1 /* 2 * Copyright (c) 2018, 2020, Oracle and/or its affiliates. All rights reserved. 3 * Copyright (c) 2018, 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 28 //#define LOG_PLEASE 29 30 #include "metaspaceTestsCommon.hpp" 31 32 33 #define CHECK_BT_CONTENT(bt, expected_num, expected_size) { \ 34 EXPECT_EQ(bt.count(), (unsigned)expected_num); \ 35 EXPECT_EQ(bt.total_size(), (size_t)expected_size); \ 36 if (expected_num == 0) { \ 37 EXPECT_TRUE(bt.is_empty()); \ 38 } else { \ 39 EXPECT_FALSE(bt.is_empty()); \ 40 } \ 41 } 42 43 TEST_VM(metaspace, BlockTree_basic) { 44 45 BlockTree bt; 46 CHECK_BT_CONTENT(bt, 0, 0); 47 48 size_t real_size = 0; 49 MetaWord* p = NULL; 50 MetaWord arr[10000]; 51 52 const size_t minws = BlockTree::minimal_word_size; 53 const size_t maxws = 4096; 54 55 // get_block from empty tree should yield nothing 56 p = bt.get_block(minws, &real_size); 57 EXPECT_EQ(p, (MetaWord*)NULL); 58 EXPECT_EQ(real_size, (size_t)0); 59 CHECK_BT_CONTENT(bt, 0, 0); 60 61 // Add some blocks and retrieve them right away. 62 size_t sizes[] = { 63 minws + 10, 64 maxws - 10, 65 minws, // smallest possible 66 maxws - 1, // largest possible 67 0 68 }; 69 70 for (int i = 0; sizes[i] > 0; i ++) { 71 bt.add_block(arr, sizes[i]); 72 CHECK_BT_CONTENT(bt, 1, sizes[i]); 73 74 DEBUG_ONLY(bt.verify();) 75 76 MetaWord* p = bt.get_block(sizes[i], &real_size); 77 EXPECT_EQ(p, arr); 78 EXPECT_EQ(real_size, (size_t)sizes[i]); 79 CHECK_BT_CONTENT(bt, 0, 0); 80 } 81 82 } 83 84 TEST_VM(metaspace, BlockTree_closest_fit) { 85 86 // Test the fact that getting blocks should always return the closest fit 87 BlockTree bt; 88 FeederBuffer fb(10000); 89 90 const size_t minws = BlockTree::minimal_word_size; 91 const size_t maxws = 256; 92 93 size_t sizes[] = { 94 minws + 9, 95 minws + 3, 96 minws + 9, 97 minws, 98 minws + 8, 99 maxws - 2, 100 minws, 101 maxws - 1, 102 0 103 }; 104 105 size_t size_added = 0; 106 int num_added = 0; 107 108 for (int i = 0; sizes[i] > 0; i ++) { 109 const size_t s = sizes[i]; 110 MetaWord* p = fb.get(s); 111 bt.add_block(p, s); 112 num_added ++; size_added += s; 113 CHECK_BT_CONTENT(bt, num_added, size_added); 114 } 115 116 DEBUG_ONLY(bt.verify();) 117 118 size_t last_size = 0; 119 while (bt.is_empty() == false) { 120 size_t real_size = 0; 121 MetaWord* p = bt.get_block(minws, &real_size); 122 EXPECT_TRUE(fb.is_valid_range(p, real_size)); 123 124 EXPECT_GE(real_size, last_size); 125 last_size = real_size; 126 127 num_added --; 128 size_added -= real_size; 129 CHECK_BT_CONTENT(bt, num_added, size_added); 130 } 131 132 CHECK_BT_CONTENT(bt, 0, 0); 133 134 } 135 136 137 TEST_VM(metaspace, BlockTree_basic_siblings) 138 { 139 BlockTree bt; 140 CHECK_BT_CONTENT(bt, 0, 0); 141 142 const size_t minws = BlockTree::minimal_word_size; 143 const size_t maxws = 256; 144 const size_t test_size = minws + 17; 145 const int num = 10; 146 147 MetaWord* arr = NEW_C_HEAP_ARRAY(MetaWord, num * test_size, mtInternal); 148 149 for (int i = 0; i < num; i ++) { 150 bt.add_block(arr + (i * test_size), test_size); 151 CHECK_BT_CONTENT(bt, i + 1, (i + 1) * test_size); 152 } 153 154 DEBUG_ONLY(bt.verify();) 155 156 for (int i = num; i > 0; i --) { 157 size_t real_size = 4711; 158 MetaWord* p = bt.get_block(test_size, &real_size); 159 EXPECT_LT(p, arr + num * test_size); 160 EXPECT_GE(p, arr); 161 EXPECT_EQ(real_size, (size_t)test_size); 162 CHECK_BT_CONTENT(bt, i - 1, (i - 1) * test_size); 163 } 164 165 FREE_C_HEAP_ARRAY(MetaWord, arr); 166 } 167 168 class BlockTreeTest { 169 170 FeederBuffer _fb; 171 172 BlockTree _bt[2]; 173 MemRangeCounter _cnt[2]; 174 175 RandSizeGenerator _rgen; 176 177 #define CHECK_COUNTERS \ 178 CHECK_BT_CONTENT(_bt[0], _cnt[0].count(), _cnt[0].total_size()) \ 179 CHECK_BT_CONTENT(_bt[1], _cnt[1].count(), _cnt[1].total_size()) 180 181 #define CHECK_COUNTERS_ARE_0 \ 182 CHECK_BT_CONTENT(_bt[0], 0, 0) \ 183 CHECK_BT_CONTENT(_bt[1], 0, 0) 184 185 #ifdef ASSERT 186 void verify_trees() { 187 _bt[0].verify(); 188 _bt[1].verify(); 189 } 190 #endif 191 192 enum feeding_pattern_t { 193 scatter = 1, 194 left_right = 2, 195 right_left = 3 196 }; 197 198 void feed_all(feeding_pattern_t feeding_pattern) { 199 200 // Feed the whole feaderbuffer space to the trees. 201 MetaWord* p = NULL; 202 unsigned added = 0; 203 204 // If we feed in small graining, we cap the number of blocks to limit test duration. 205 const unsigned max_blocks = 2000; 206 207 size_t old_feeding_size = feeding_pattern == right_left ? _rgen.max() : _rgen.min(); 208 do { 209 size_t s = 0; 210 switch (feeding_pattern) { 211 case scatter: 212 // fill completely random 213 s =_rgen.get(); 214 break; 215 case left_right: 216 // fill in ascending order to annoy trees. 217 s = MIN2(_rgen.get(), old_feeding_size); 218 old_feeding_size = s; 219 break; 220 case right_left: 221 // same, but descending. 222 s = MAX2(_rgen.get(), old_feeding_size); 223 old_feeding_size = s; 224 break; 225 } 226 227 p = _fb.get(s); 228 if (p != NULL) { 229 int which = added % 2; 230 added ++; 231 _bt[which].add_block(p, s); 232 _cnt[which].add(s); 233 CHECK_COUNTERS 234 } 235 DEBUG_ONLY(verify_trees();) 236 CHECK_COUNTERS; 237 } while (p != NULL && added < max_blocks); 238 239 // Trees should be populated in a balanced way, and not empty 240 EXPECT_TRUE( _bt[0].count() == _bt[1].count() || 241 (_bt[0].count() == _bt[1].count() + 1 && _bt[0].count() > 0)); 242 243 } 244 245 void ping_pong_loop(int iterations) { 246 247 // We loop and in each iteration randomly retrieve a block from one tree and add it to another. 248 for (int i = 0; i < iterations; i ++) { 249 int taker = 0; 250 int giver = 1; 251 if ((os::random() % 10) > 5) { 252 giver = 0; taker = 1; 253 } 254 size_t s =_rgen.get(); 255 size_t real_size = 0; 256 MetaWord* p = _bt[giver].get_block(s, &real_size); 257 if (p == NULL) { 258 // Todo: check that bt really has no larger block than this. 259 } else { 260 ASSERT_TRUE(_fb.is_valid_range(p, real_size)); 261 ASSERT_GE(real_size, s); 262 _bt[taker].add_block(p, real_size); 263 _cnt[giver].sub(real_size); 264 _cnt[taker].add(real_size); 265 CHECK_COUNTERS; 266 } 267 268 #ifdef ASSERT 269 if (true) {//i % 1000 == 0) { 270 verify_trees(); 271 } 272 #endif 273 } 274 } 275 276 // Drain the trees. While draining, observe the order of the drained items. 277 void drain_all() { 278 279 for (int which = 0; which < 2; which ++) { 280 BlockTree* bt = _bt + which; 281 size_t last_size = 0; 282 while(!bt->is_empty()) { 283 284 // We only query for the minimal size. Actually returned size should be 285 // monotonously growing since get_block should always return the closest fit. 286 size_t real_size = 4711; 287 MetaWord* p = bt->get_block(BlockTree::minimal_word_size, &real_size); 288 ASSERT_TRUE(_fb.is_valid_range(p, real_size)); 289 290 ASSERT_GE(real_size, last_size); 291 last_size = real_size; 292 293 _cnt[which].sub(real_size); 294 CHECK_COUNTERS; 295 296 #ifdef ASSERT 297 if (true) {//i % 1000 == 0) { 298 bt->verify(); 299 } 300 #endif 301 } 302 } 303 304 } 305 306 void test(feeding_pattern_t feeding_pattern) { 307 308 CHECK_COUNTERS_ARE_0 309 310 feed_all(feeding_pattern); 311 312 LOG("Blocks in circulation: bt1=%d:" SIZE_FORMAT ", bt2=%d:" SIZE_FORMAT ".", 313 _bt[0].count(), _bt[0].total_size(), 314 _bt[1].count(), _bt[1].total_size()); 315 316 ping_pong_loop(2000); 317 318 LOG("After Pingpong: bt1=%d:" SIZE_FORMAT ", bt2=%d:" SIZE_FORMAT ".", 319 _bt[0].count(), _bt[0].total_size(), 320 _bt[1].count(), _bt[1].total_size()); 321 322 drain_all(); 323 324 CHECK_COUNTERS_ARE_0 325 } 326 327 328 public: 329 330 BlockTreeTest(size_t min_word_size, size_t max_word_size) : 331 _fb(2 * M), 332 _bt(), 333 _rgen(min_word_size, max_word_size) 334 { 335 CHECK_COUNTERS; 336 DEBUG_ONLY(verify_trees();) 337 } 338 339 340 void test_scatter() { test(scatter); } 341 void test_right_left() { test(right_left); } 342 void test_left_right() { test(left_right); } 343 344 }; 345 346 #define DO_TEST(name, feedingpattern, min, max) \ 347 TEST_VM(metaspace, BlockTree_##name##_##feedingpattern) { \ 348 BlockTreeTest btt(min, max); \ 349 btt.test_##feedingpattern(); \ 350 } 351 352 #define DO_TEST_ALL_PATTERNS(name, min, max) \ 353 DO_TEST(name, scatter, min, max) \ 354 DO_TEST(name, right_left, min, max) \ 355 DO_TEST(name, left_right, min, max) 356 357 358 DO_TEST_ALL_PATTERNS(wide, BlockTree::minimal_word_size, 128 * K); 359 DO_TEST_ALL_PATTERNS(narrow, BlockTree::minimal_word_size, 16) 360 DO_TEST_ALL_PATTERNS(129, BlockTree::minimal_word_size, 129) 361 DO_TEST_ALL_PATTERNS(4K, BlockTree::minimal_word_size, 4*K) 362 363 364