1 /*
2 * Copyright (c) 2015, 2023, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 #include "precompiled.hpp"
25 #include "classfile/symbolTable.hpp"
26 #include "memory/allocation.hpp"
27 #include "memory/resourceArea.hpp"
28 #include "oops/symbolHandle.hpp"
29 #include "unittest.hpp"
30 #include "utilities/debug.hpp"
31 #include "utilities/globalDefinitions.hpp"
32 #include "utilities/resourceHash.hpp"
33
34 class CommonResourceHashtableTest : public ::testing::Test {
35 protected:
36 typedef void* K;
37 typedef uintx V;
38 const static MEMFLAGS MEM_TYPE = mtInternal;
39
40 static unsigned identity_hash(const K& k) {
41 return (unsigned) (uintptr_t) k;
42 }
43
44 static unsigned bad_hash(const K& k) {
45 return 1;
46 }
47
48 static void* as_K(uintptr_t val) {
49 return (void*) val;
50 }
51
52 class EqualityTestIter {
53 public:
54
55 bool do_entry(K const& k, V const& v) {
56 if ((uintptr_t) k != (uintptr_t) v) {
57 EXPECT_EQ((uintptr_t) k, (uintptr_t) v);
58 return false;
59 } else {
60 return true; // continue iteration
61 }
62 }
63 };
64
65 class DeleterTestIter {
66 int _val;
67 public:
68 DeleterTestIter(int i) : _val(i) {}
69
70 bool do_entry(K const& k, V const& v) {
71 if ((uintptr_t) k == (uintptr_t) _val) {
72 // Delete me!
73 return true;
74 } else {
75 return false; // continue iteration
76 }
77 }
78 };
79
80 };
81
82 class SmallResourceHashtableTest : public CommonResourceHashtableTest {
83 protected:
84
85 template<
86 unsigned (*HASH) (K const&) = primitive_hash<K>,
87 bool (*EQUALS)(K const&, K const&) = primitive_equals<K>,
88 unsigned SIZE = 256,
89 AnyObj::allocation_type ALLOC_TYPE = AnyObj::RESOURCE_AREA
90 >
91 class Runner : public AllStatic {
92 public:
93
94 static void test(V step) {
95 EqualityTestIter et;
96 ResourceHashtable<K, V, SIZE, ALLOC_TYPE, MEM_TYPE, HASH, EQUALS> rh;
97
98 ASSERT_FALSE(rh.contains(as_K(step)));
99
100 ASSERT_TRUE(rh.put(as_K(step), step));
101 ASSERT_TRUE(rh.contains(as_K(step)));
102
103 ASSERT_FALSE(rh.put(as_K(step), step));
104
105 ASSERT_TRUE(rh.put(as_K(2 * step), 2 * step));
106 ASSERT_TRUE(rh.put(as_K(3 * step), 3 * step));
107 ASSERT_TRUE(rh.put(as_K(4 * step), 4 * step));
108 ASSERT_TRUE(rh.put(as_K(5 * step), 5 * step));
109
110 ASSERT_FALSE(rh.remove(as_K(0x0)));
111
112 rh.iterate(&et);
113 if (::testing::Test::HasFailure()) {
114 return;
115 }
116
117 ASSERT_TRUE(rh.remove(as_K(step)));
118 ASSERT_FALSE(rh.contains(as_K(step)));
119 rh.iterate(&et);
120
121
122 // Test put_if_absent(key) (creating a default-created value)
123 bool created = false;
124 V* v = rh.put_if_absent(as_K(step), &created);
125 ASSERT_TRUE(rh.contains(as_K(step)));
126 ASSERT_TRUE(created);
127 *v = (V)step;
128
129 // Calling this function a second time should yield the same value pointer
130 V* v2 = rh.put_if_absent(as_K(step), &created);
131 ASSERT_EQ(v, v2);
132 ASSERT_EQ(*v2, *v);
133 ASSERT_FALSE(created);
134
135 ASSERT_TRUE(rh.remove(as_K(step)));
136 ASSERT_FALSE(rh.contains(as_K(step)));
137 rh.iterate(&et);
138
139 // Test put_if_absent(key, value)
140 v = rh.put_if_absent(as_K(step), step, &created);
141 ASSERT_EQ(*v, step);
142 ASSERT_TRUE(rh.contains(as_K(step)));
143 ASSERT_TRUE(created);
144
145 v2 = rh.put_if_absent(as_K(step), step, &created);
146 // Calling this function a second time should yield the same value pointer
147 ASSERT_EQ(v, v2);
148 ASSERT_EQ(*v2, (V)step);
149 ASSERT_FALSE(created);
150
151 ASSERT_TRUE(rh.remove(as_K(step)));
152 ASSERT_FALSE(rh.contains(as_K(step)));
153 rh.iterate(&et);
154
155 rh.unlink_all();
156 }
157 };
158 };
159
160 TEST_VM_F(SmallResourceHashtableTest, default) {
161 ResourceMark rm;
162 Runner<>::test(0x1);
163 }
164
165 TEST_VM_F(SmallResourceHashtableTest, default_shifted) {
166 ResourceMark rm;
167 Runner<>::test(0x10);
168 }
169
170 TEST_VM_F(SmallResourceHashtableTest, bad_hash) {
171 ResourceMark rm;
172 Runner<bad_hash>::test(0x1);
173 }
174
175 TEST_VM_F(SmallResourceHashtableTest, bad_hash_shifted) {
176 ResourceMark rm;
177 Runner<bad_hash>::test(0x10);
178 }
179
180 TEST_VM_F(SmallResourceHashtableTest, identity_hash) {
181 ResourceMark rm;
182 Runner<identity_hash>::test(0x1);
183 }
184
185 TEST_VM_F(SmallResourceHashtableTest, identity_hash_shifted) {
186 ResourceMark rm;
187 Runner<identity_hash>::test(0x10);
188 }
189
190 TEST_VM_F(SmallResourceHashtableTest, primitive_hash_no_rm) {
191 Runner<primitive_hash<K>, primitive_equals<K>, 512, AnyObj::C_HEAP>::test(0x1);
192 }
193
194 TEST_VM_F(SmallResourceHashtableTest, primitive_hash_no_rm_shifted) {
195 Runner<primitive_hash<K>, primitive_equals<K>, 512, AnyObj::C_HEAP>::test(0x10);
196 }
197
198 TEST_VM_F(SmallResourceHashtableTest, bad_hash_no_rm) {
199 Runner<bad_hash, primitive_equals<K>, 512, AnyObj::C_HEAP>::test(0x1);
200 }
201
202 TEST_VM_F(SmallResourceHashtableTest, bad_hash_no_rm_shifted) {
203 Runner<bad_hash, primitive_equals<K>, 512, AnyObj::C_HEAP>::test(0x10);
204 }
205
206 TEST_VM_F(SmallResourceHashtableTest, identity_hash_no_rm) {
207 Runner<identity_hash, primitive_equals<K>, 1, AnyObj::C_HEAP>::test(0x1);
208 }
209
210 TEST_VM_F(SmallResourceHashtableTest, identity_hash_no_rm_shifted) {
211 Runner<identity_hash, primitive_equals<K>, 1, AnyObj::C_HEAP>::test(0x10);
212 }
213
214 class GenericResourceHashtableTest : public CommonResourceHashtableTest {
215 protected:
216
217 template<
218 unsigned (*HASH) (K const&) = primitive_hash<K>,
219 bool (*EQUALS)(K const&, K const&) = primitive_equals<K>,
220 unsigned SIZE = 256,
221 AnyObj::allocation_type ALLOC_TYPE = AnyObj::RESOURCE_AREA
222 >
223 class Runner : public AllStatic {
224 public:
225
226 static void test(unsigned num_elements = SIZE) {
227 EqualityTestIter et;
228 ResourceHashtable<K, V, SIZE, ALLOC_TYPE, MEM_TYPE, HASH, EQUALS> rh;
229
230 for (uintptr_t i = 0; i < num_elements; ++i) {
231 ASSERT_TRUE(rh.put(as_K(i), i));
232 }
233
234 rh.iterate(&et);
235 if (::testing::Test::HasFailure()) {
236 return;
237 }
238
239 for (uintptr_t i = num_elements; i > 0; --i) {
240 uintptr_t index = i - 1;
241 ASSERT_TRUE((rh.remove(as_K(index))));
242 }
243
244 rh.iterate(&et);
245 if (::testing::Test::HasFailure()) {
246 return;
247 }
248 for (uintptr_t i = num_elements; i > 0; --i) {
249 uintptr_t index = i - 1;
250 ASSERT_FALSE(rh.remove(as_K(index)));
251 }
252 rh.iterate(&et);
253
254 // Add more entries in and then delete one.
255 for (uintptr_t i = 10; i > 0; --i) {
256 uintptr_t index = i - 1;
257 ASSERT_TRUE(rh.put(as_K(index), index));
258 }
259 DeleterTestIter dt(5);
260 rh.unlink(&dt);
261 ASSERT_FALSE(rh.get(as_K(5)));
262
263 rh.unlink_all();
264 for (uintptr_t i = 10; i > 0; --i) {
265 uintptr_t index = i - 1;
266 ASSERT_FALSE(rh.get(as_K(index)));
267 }
268 }
269 };
270 };
271
272 TEST_VM_F(GenericResourceHashtableTest, default) {
273 ResourceMark rm;
274 Runner<>::test();
275 }
276
277 TEST_VM_F(GenericResourceHashtableTest, bad_hash) {
278 ResourceMark rm;
279 Runner<bad_hash>::test();
280 }
281
282 TEST_VM_F(GenericResourceHashtableTest, identity_hash) {
283 ResourceMark rm;
284 Runner<identity_hash>::test();
285 }
286
287 TEST_VM_F(GenericResourceHashtableTest, primitive_hash_no_rm) {
288 Runner<primitive_hash<K>, primitive_equals<K>, 512, AnyObj::C_HEAP>::test();
289 }
290
291 TEST_VM_F(GenericResourceHashtableTest, bad_hash_no_rm) {
292 Runner<bad_hash, primitive_equals<K>, 512, AnyObj::C_HEAP>::test();
293 }
294
295 TEST_VM_F(GenericResourceHashtableTest, identity_hash_no_rm) {
296 Runner<identity_hash, primitive_equals<K>, 1, AnyObj::C_HEAP>::test(512);
297 }
298
299 // Simple ResourceHashtable whose key is a SymbolHandle and value is an int
300 // This test is to show that the SymbolHandle will correctly handle the refcounting
301 // in the table.
302 class SimpleResourceHashtableDeleteTest : public ::testing::Test {
303 public:
304 ResourceHashtable<SymbolHandle, int, 107, AnyObj::C_HEAP, mtTest, SymbolHandle::compute_hash> _simple_test_table;
305
306 class SimpleDeleter : public StackObj {
307 public:
308 bool do_entry(SymbolHandle& key, int value) {
309 return true;
310 }
311 };
312 };
313
314 TEST_VM_F(SimpleResourceHashtableDeleteTest, simple_remove) {
315 TempNewSymbol t = SymbolTable::new_symbol("abcdefg_simple");
316 Symbol* s = t;
317 int s_orig_count = s->refcount();
318 _simple_test_table.put(s, 55);
319 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount should be incremented in table";
320
321 // Deleting this value from a hashtable
322 _simple_test_table.remove(s);
323 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be same as start";
324 }
325
326 TEST_VM_F(SimpleResourceHashtableDeleteTest, simple_delete) {
327 TempNewSymbol t = SymbolTable::new_symbol("abcdefg_simple");
328 Symbol* s = t;
329 int s_orig_count = s->refcount();
330 _simple_test_table.put(s, 66);
331 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount should be incremented in table";
332
333 // Use unlink to remove the matching (or all) values from the table.
334 SimpleDeleter deleter;
335 _simple_test_table.unlink(&deleter);
336 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be same as start";
337 }
338
339 TEST_VM_F(SimpleResourceHashtableDeleteTest, simle_unlink_all) {
340 TempNewSymbol t = SymbolTable::new_symbol("abcdefg_simple");
341 Symbol* s = t;
342 int s_orig_count = s->refcount();
343 _simple_test_table.put(s, 66);
344 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount should be incremented in table";
345
346 // Use unlink_all to remove the matching (or all) values from the table.
347 _simple_test_table.unlink_all();
348 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be same as start";
349 }
350
351 // More complicated ResourceHashtable with SymbolHandle in the key. Since the *same* Symbol is part
352 // of the value, it's not necessary to manipulate the refcount of the key, but you must in the value.
353 // Luckily SymbolHandle does this.
354 class ResourceHashtableDeleteTest : public ::testing::Test {
355 public:
356 class TestValue : public CHeapObj<mtTest> {
357 SymbolHandle _s;
358 public:
359 // Never have ctors and dtors fix refcounts without copy ctors and assignment operators!
360 // Unless it's declared and used as a CHeapObj with
361 // NONCOPYABLE(TestValue)
362
363 // Using SymbolHandle deals with refcount manipulation so this class doesn't have to
364 // have dtors, copy ctors and assignment operators to do so.
365 TestValue(Symbol* name) : _s(name) { }
366 // Symbol* s() const { return _s; } // needed for conversion from TempNewSymbol to SymbolHandle member
367 };
368
369 // ResourceHashtable whose value is a *copy* of TestValue.
370 ResourceHashtable<Symbol*, TestValue, 107, AnyObj::C_HEAP, mtTest> _test_table;
371
372 class Deleter : public StackObj {
373 public:
374 bool do_entry(Symbol*& key, TestValue& value) {
375 // Since we didn't increment the key, we shouldn't decrement it.
376 // Calling delete on the hashtable Node which contains value will
377 // decrement the refcount. That's actually best since the whole
378 // entry will be gone at once.
379 return true;
380 }
381 };
382
383 // ResourceHashtable whose value is a pointer to TestValue.
384 ResourceHashtable<Symbol*, TestValue*, 107, AnyObj::C_HEAP, mtTest> _ptr_test_table;
385
386 class PtrDeleter : public StackObj {
387 public:
388 bool do_entry(Symbol*& key, TestValue*& value) {
389 // If the hashtable value is a pointer, need to delete it from here.
390 // This will also potentially make the refcount of the Key = 0, but the
391 // next thing that happens is that the hashtable node is deleted so this is ok.
392 delete value;
393 return true;
394 }
395 };
396 };
397
398
399 TEST_VM_F(ResourceHashtableDeleteTest, value_remove) {
400 TempNewSymbol s = SymbolTable::new_symbol("abcdefg");
401 int s_orig_count = s->refcount();
402 {
403 TestValue tv(s);
404 // Since TestValue contains the pointer to the key, it will handle the
405 // refcounting.
406 _test_table.put(s, tv);
407 ASSERT_EQ(s->refcount(), s_orig_count + 2) << "refcount incremented by copy";
408 }
409 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount incremented in table";
410
411 // Deleting this value from a hashtable calls the destructor!
412 _test_table.remove(s);
413 // Removal should make the refcount be the original refcount.
414 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be as we started";
415 }
416
417 TEST_VM_F(ResourceHashtableDeleteTest, value_delete) {
418 TempNewSymbol d = SymbolTable::new_symbol("defghijklmnop");
419 int d_orig_count = d->refcount();
420 {
421 TestValue tv(d);
422 // Same as above, but the do_entry does nothing because the value is deleted when the
423 // hashtable node is deleted.
424 _test_table.put(d, tv);
425 ASSERT_EQ(d->refcount(), d_orig_count + 2) << "refcount incremented by copy";
426 }
427 ASSERT_EQ(d->refcount(), d_orig_count + 1) << "refcount incremented in table";
428 Deleter deleter;
429 _test_table.unlink(&deleter);
430 ASSERT_EQ(d->refcount(), d_orig_count) << "refcount should be as we started";
431 }
432
433 TEST_VM_F(ResourceHashtableDeleteTest, value_unlink_all) {
434 TempNewSymbol d = SymbolTable::new_symbol("defghijklmnop");
435 int d_orig_count = d->refcount();
436 {
437 TestValue tv(d);
438 // Same as above, but the do_entry does nothing because the value is deleted when the
439 // hashtable node is deleted.
440 _test_table.put(d, tv);
441 ASSERT_EQ(d->refcount(), d_orig_count + 2) << "refcount incremented by copy";
442 }
443 ASSERT_EQ(d->refcount(), d_orig_count + 1) << "refcount incremented in table";
444 _test_table.unlink_all();
445 ASSERT_EQ(d->refcount(), d_orig_count) << "refcount should be as we started";
446 }
447
448 TEST_VM_F(ResourceHashtableDeleteTest, check_delete_ptr) {
449 TempNewSymbol s = SymbolTable::new_symbol("abcdefg_ptr");
450 int s_orig_count = s->refcount();
451 {
452 TestValue* tv = new TestValue(s);
453 // Again since TestValue contains the pointer to the key Symbol, it will
454 // handle the refcounting.
455 _ptr_test_table.put(s, tv);
456 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount incremented by allocation";
457 }
458 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount incremented in table";
459
460 // Deleting this pointer value from a hashtable must call the destructor in the
461 // do_entry function.
462 PtrDeleter deleter;
463 _ptr_test_table.unlink(&deleter);
464 // Removal should make the refcount be the original refcount.
465 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be as we started";
466 }
467
468 class ResourceHashtablePrintTest : public ::testing::Test {
469 public:
470 class TestValue {
471 int _i;
472 int _j;
473 int _k;
474 public:
475 TestValue(int i) : _i(i), _j(i+1), _k(i+2) {}
476 };
477 ResourceHashtable<int, TestValue*, 30, AnyObj::C_HEAP, mtTest> _test_table;
478
479 class TableDeleter {
480 public:
481 bool do_entry(int& key, TestValue*& val) {
482 delete val;
483 return true;
484 }
485 };
486 };
487
488 TEST_VM_F(ResourceHashtablePrintTest, print_test) {
489 for (int i = 0; i < 300; i++) {
490 TestValue* tv = new TestValue(i);
491 _test_table.put(i, tv); // all the entries can be the same.
492 }
493 auto printer = [&] (int& key, TestValue*& val) {
494 return sizeof(*val);
495 };
496 TableStatistics ts = _test_table.statistics_calculate(printer);
497 ResourceMark rm;
498 stringStream st;
499 ts.print(&st, "TestTable");
500 // Verify output in string
501 const char* strings[] = {
502 "Number of buckets", "Number of entries", "300", "Number of literals", "Average bucket size", "Maximum bucket size" };
503 for (const auto& str : strings) {
504 ASSERT_THAT(st.base(), testing::HasSubstr(str));
505 }
506 // Cleanup: need to delete pointers in entries
507 TableDeleter deleter;
508 _test_table.unlink(&deleter);
509 }