1 /* 2 * Copyright (c) 2015, 2022, 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 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 }; 264 }; 265 266 TEST_VM_F(GenericResourceHashtableTest, default) { 267 ResourceMark rm; 268 Runner<>::test(); 269 } 270 271 TEST_VM_F(GenericResourceHashtableTest, bad_hash) { 272 ResourceMark rm; 273 Runner<bad_hash>::test(); 274 } 275 276 TEST_VM_F(GenericResourceHashtableTest, identity_hash) { 277 ResourceMark rm; 278 Runner<identity_hash>::test(); 279 } 280 281 TEST_VM_F(GenericResourceHashtableTest, primitive_hash_no_rm) { 282 Runner<primitive_hash<K>, primitive_equals<K>, 512, AnyObj::C_HEAP>::test(); 283 } 284 285 TEST_VM_F(GenericResourceHashtableTest, bad_hash_no_rm) { 286 Runner<bad_hash, primitive_equals<K>, 512, AnyObj::C_HEAP>::test(); 287 } 288 289 TEST_VM_F(GenericResourceHashtableTest, identity_hash_no_rm) { 290 Runner<identity_hash, primitive_equals<K>, 1, AnyObj::C_HEAP>::test(512); 291 } 292 293 // Simple ResourceHashtable whose key is a SymbolHandle and value is an int 294 // This test is to show that the SymbolHandle will correctly handle the refcounting 295 // in the table. 296 class SimpleResourceHashtableDeleteTest : public ::testing::Test { 297 public: 298 ResourceHashtable<SymbolHandle, int, 107, AnyObj::C_HEAP, mtTest, SymbolHandle::compute_hash> _simple_test_table; 299 300 class SimpleDeleter : public StackObj { 301 public: 302 bool do_entry(SymbolHandle& key, int value) { 303 return true; 304 } 305 }; 306 }; 307 308 TEST_VM_F(SimpleResourceHashtableDeleteTest, simple_remove) { 309 TempNewSymbol t = SymbolTable::new_symbol("abcdefg_simple"); 310 Symbol* s = t; 311 int s_orig_count = s->refcount(); 312 _simple_test_table.put(s, 55); 313 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount should be incremented in table"; 314 315 // Deleting this value from a hashtable 316 _simple_test_table.remove(s); 317 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be same as start"; 318 } 319 320 TEST_VM_F(SimpleResourceHashtableDeleteTest, simple_delete) { 321 TempNewSymbol t = SymbolTable::new_symbol("abcdefg_simple"); 322 Symbol* s = t; 323 int s_orig_count = s->refcount(); 324 _simple_test_table.put(s, 66); 325 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount should be incremented in table"; 326 327 // Use unlink to remove the matching (or all) values from the table. 328 SimpleDeleter deleter; 329 _simple_test_table.unlink(&deleter); 330 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be same as start"; 331 } 332 333 // More complicated ResourceHashtable with SymbolHandle in the key. Since the *same* Symbol is part 334 // of the value, it's not necessary to manipulate the refcount of the key, but you must in the value. 335 // Luckily SymbolHandle does this. 336 class ResourceHashtableDeleteTest : public ::testing::Test { 337 public: 338 class TestValue : public CHeapObj<mtTest> { 339 SymbolHandle _s; 340 public: 341 // Never have ctors and dtors fix refcounts without copy ctors and assignment operators! 342 // Unless it's declared and used as a CHeapObj with 343 // NONCOPYABLE(TestValue) 344 345 // Using SymbolHandle deals with refcount manipulation so this class doesn't have to 346 // have dtors, copy ctors and assignment operators to do so. 347 TestValue(Symbol* name) : _s(name) { } 348 // Symbol* s() const { return _s; } // needed for conversion from TempNewSymbol to SymbolHandle member 349 }; 350 351 // ResourceHashtable whose value is a *copy* of TestValue. 352 ResourceHashtable<Symbol*, TestValue, 107, AnyObj::C_HEAP, mtTest> _test_table; 353 354 class Deleter : public StackObj { 355 public: 356 bool do_entry(Symbol*& key, TestValue& value) { 357 // Since we didn't increment the key, we shouldn't decrement it. 358 // Calling delete on the hashtable Node which contains value will 359 // decrement the refcount. That's actually best since the whole 360 // entry will be gone at once. 361 return true; 362 } 363 }; 364 365 // ResourceHashtable whose value is a pointer to TestValue. 366 ResourceHashtable<Symbol*, TestValue*, 107, AnyObj::C_HEAP, mtTest> _ptr_test_table; 367 368 class PtrDeleter : public StackObj { 369 public: 370 bool do_entry(Symbol*& key, TestValue*& value) { 371 // If the hashtable value is a pointer, need to delete it from here. 372 // This will also potentially make the refcount of the Key = 0, but the 373 // next thing that happens is that the hashtable node is deleted so this is ok. 374 delete value; 375 return true; 376 } 377 }; 378 }; 379 380 381 TEST_VM_F(ResourceHashtableDeleteTest, value_remove) { 382 TempNewSymbol s = SymbolTable::new_symbol("abcdefg"); 383 int s_orig_count = s->refcount(); 384 { 385 TestValue tv(s); 386 // Since TestValue contains the pointer to the key, it will handle the 387 // refcounting. 388 _test_table.put(s, tv); 389 ASSERT_EQ(s->refcount(), s_orig_count + 2) << "refcount incremented by copy"; 390 } 391 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount incremented in table"; 392 393 // Deleting this value from a hashtable calls the destructor! 394 _test_table.remove(s); 395 // Removal should make the refcount be the original refcount. 396 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be as we started"; 397 } 398 399 TEST_VM_F(ResourceHashtableDeleteTest, value_delete) { 400 TempNewSymbol d = SymbolTable::new_symbol("defghijklmnop"); 401 int d_orig_count = d->refcount(); 402 { 403 TestValue tv(d); 404 // Same as above, but the do_entry does nothing because the value is deleted when the 405 // hashtable node is deleted. 406 _test_table.put(d, tv); 407 ASSERT_EQ(d->refcount(), d_orig_count + 2) << "refcount incremented by copy"; 408 } 409 ASSERT_EQ(d->refcount(), d_orig_count + 1) << "refcount incremented in table"; 410 Deleter deleter; 411 _test_table.unlink(&deleter); 412 ASSERT_EQ(d->refcount(), d_orig_count) << "refcount should be as we started"; 413 } 414 415 TEST_VM_F(ResourceHashtableDeleteTest, check_delete_ptr) { 416 TempNewSymbol s = SymbolTable::new_symbol("abcdefg_ptr"); 417 int s_orig_count = s->refcount(); 418 { 419 TestValue* tv = new TestValue(s); 420 // Again since TestValue contains the pointer to the key Symbol, it will 421 // handle the refcounting. 422 _ptr_test_table.put(s, tv); 423 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount incremented by allocation"; 424 } 425 ASSERT_EQ(s->refcount(), s_orig_count + 1) << "refcount incremented in table"; 426 427 // Deleting this pointer value from a hashtable must call the destructor in the 428 // do_entry function. 429 PtrDeleter deleter; 430 _ptr_test_table.unlink(&deleter); 431 // Removal should make the refcount be the original refcount. 432 ASSERT_EQ(s->refcount(), s_orig_count) << "refcount should be as we started"; 433 } 434 435 class ResourceHashtablePrintTest : public ::testing::Test { 436 public: 437 class TestValue { 438 int _i; 439 int _j; 440 int _k; 441 public: 442 TestValue(int i) : _i(i), _j(i+1), _k(i+2) {} 443 }; 444 ResourceHashtable<int, TestValue*, 30, AnyObj::C_HEAP, mtTest> _test_table; 445 446 class TableDeleter { 447 public: 448 bool do_entry(int& key, TestValue*& val) { 449 delete val; 450 return true; 451 } 452 }; 453 }; 454 455 TEST_VM_F(ResourceHashtablePrintTest, print_test) { 456 for (int i = 0; i < 300; i++) { 457 TestValue* tv = new TestValue(i); 458 _test_table.put(i, tv); // all the entries can be the same. 459 } 460 auto printer = [&] (int& key, TestValue*& val) { 461 return sizeof(*val); 462 }; 463 TableStatistics ts = _test_table.statistics_calculate(printer); 464 ResourceMark rm; 465 stringStream st; 466 ts.print(&st, "TestTable"); 467 // Verify output in string 468 const char* strings[] = { 469 "Number of buckets", "Number of entries", "300", "Number of literals", "Average bucket size", "Maximum bucket size" }; 470 for (const auto& str : strings) { 471 ASSERT_THAT(st.base(), testing::HasSubstr(str)); 472 } 473 // Cleanup: need to delete pointers in entries 474 TableDeleter deleter; 475 _test_table.unlink(&deleter); 476 }