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,
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
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 {
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
|
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,
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
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 {
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
|