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