1 /* 2 * Copyright (c) 2018, 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 "runtime/mutex.hpp" 26 #include "runtime/semaphore.hpp" 27 #include "runtime/thread.hpp" 28 #include "runtime/vmThread.hpp" 29 #include "runtime/vm_operations.hpp" 30 #include "utilities/concurrentHashTable.inline.hpp" 31 #include "utilities/concurrentHashTableTasks.inline.hpp" 32 #include "utilitiesHelper.inline.hpp" 33 #include "unittest.hpp" 34 35 // NOTE: On win32 gtest asserts are not mt-safe. 36 // Amusingly as long as they do not assert they are mt-safe. 37 #define SIZE_32 5 38 39 struct Pointer; 40 41 typedef ConcurrentHashTable<uintptr_t, Pointer, mtInternal> SimpleTestTable; 42 typedef ConcurrentHashTable<uintptr_t, Pointer, mtInternal>::MultiGetHandle SimpleTestGetHandle; 43 44 // Simplest working CRPT implementation for the hash-table. 45 struct Pointer : public SimpleTestTable::BaseConfig { 46 static uintx get_hash(const uintptr_t& value, bool* dead_hash) { 47 return (uintx)value; 48 } 49 static const uintptr_t& notfound() { 50 static uintptr_t notfound = 0; 51 return notfound; 52 } 53 static void* allocate_node(size_t size, const uintptr_t& value) { 54 return ::malloc(size); 55 } 56 static void free_node(void* memory, const uintptr_t& value) { 57 ::free(memory); 58 } 59 }; 60 61 struct SimpleTestLookup { 62 uintptr_t _val; 63 SimpleTestLookup(uintptr_t val) : _val(val) {} 64 uintx get_hash() { 65 return Pointer::get_hash(_val, NULL); 66 } 67 bool equals(const uintptr_t* value, bool* is_dead) { 68 return _val == *value; 69 } 70 }; 71 72 static void cht_insert(Thread* thr) { 73 uintptr_t val = 0x2; 74 SimpleTestLookup stl(val); 75 SimpleTestTable* cht = new SimpleTestTable(); 76 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed."; 77 EXPECT_EQ(cht->get_copy(thr, stl), val) << "Getting an existing value failed."; 78 EXPECT_TRUE(cht->remove(thr, stl)) << "Removing an existing value failed."; 79 EXPECT_FALSE(cht->remove(thr, stl)) << "Removing an already removed item succeeded."; 80 EXPECT_NE(cht->get_copy(thr, stl), val) << "Getting a removed value succeeded."; 81 delete cht; 82 } 83 84 struct ValVerify { 85 uintptr_t _val; 86 bool called_get; 87 bool called_insert; 88 ValVerify(uintptr_t val) : called_get(false), called_insert(false), _val(val) {} 89 void operator()(bool inserted, uintptr_t* val) { 90 EXPECT_EQ(_val, *val) << "The value inserted is not correct."; 91 if (inserted) { 92 called_insert = true; 93 } else { 94 called_get = true; 95 } 96 } 97 void verify(bool get, bool insert) { 98 EXPECT_EQ(called_get, get) << "Get unexpected"; 99 EXPECT_EQ(called_insert, insert) << "Insert unexpected"; 100 } 101 }; 102 103 static void cht_get_insert_helper(Thread* thr, SimpleTestTable* cht, uintptr_t val) { 104 { 105 SimpleTestLookup stl(val); 106 ValVerify vv(val); 107 EXPECT_EQ(cht->get_insert(thr, stl, val, vv), false) << "Inserting an unique value failed."; 108 vv.verify(false, true); 109 } 110 111 { 112 SimpleTestLookup stl(val); 113 ValVerify vv(val); 114 EXPECT_EQ(cht->get_insert(thr, stl, val, vv), true) << "Getting an old value failed."; 115 vv.verify(true, false); 116 } 117 } 118 119 static void cht_get_insert(Thread* thr) { 120 uintptr_t val = 0x2; 121 SimpleTestLookup stl(val); 122 SimpleTestTable* cht = new SimpleTestTable(); 123 124 { 125 SCOPED_TRACE("First"); 126 cht_get_insert_helper(thr, cht, val); 127 } 128 EXPECT_EQ(cht->get_copy(thr, stl), val) << "Get an old value failed"; 129 EXPECT_TRUE(cht->remove(thr, stl)) << "Removing existing value failed."; 130 EXPECT_NE(cht->get_copy(thr, stl), val) << "Got an already removed item."; 131 132 { 133 SCOPED_TRACE("Second"); 134 cht_get_insert_helper(thr, cht, val); 135 } 136 137 delete cht; 138 } 139 140 static bool getinsert_bulkdelete_eval(uintptr_t* val) { 141 EXPECT_TRUE(*val > 0 && *val < 4) << "Val wrong for this test."; 142 return (*val & 0x1); // Delete all values ending with first bit set. 143 } 144 145 static void getinsert_bulkdelete_del(uintptr_t* val) { 146 EXPECT_EQ(*val & 0x1, (uintptr_t)1) << "Deleting wrong value."; 147 } 148 149 static void cht_getinsert_bulkdelete_insert_verified(Thread* thr, SimpleTestTable* cht, uintptr_t val, 150 bool verify_expect_get, bool verify_expect_inserted) { 151 ValVerify vv(val); 152 SimpleTestLookup stl(val); 153 EXPECT_EQ(cht->get_insert(thr, stl, val, vv), verify_expect_get) << "Inserting an unique value failed."; 154 vv.verify(verify_expect_get, verify_expect_inserted); 155 } 156 157 static void cht_getinsert_bulkdelete(Thread* thr) { 158 uintptr_t val1 = 1; 159 uintptr_t val2 = 2; 160 uintptr_t val3 = 3; 161 SimpleTestLookup stl1(val1), stl2(val2), stl3(val3); 162 163 SimpleTestTable* cht = new SimpleTestTable(); 164 cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, false, true); 165 cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); 166 cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, false, true); 167 168 EXPECT_TRUE(cht->remove(thr, stl2)) << "Remove did not find value."; 169 170 cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, true, false); // val1 should be present 171 cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); // val2 should be inserted 172 cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, true, false); // val3 should be present 173 174 EXPECT_EQ(cht->get_copy(thr, stl1), val1) << "Get did not find value."; 175 EXPECT_EQ(cht->get_copy(thr, stl2), val2) << "Get did not find value."; 176 EXPECT_EQ(cht->get_copy(thr, stl3), val3) << "Get did not find value."; 177 178 // Removes all odd values. 179 cht->bulk_delete(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del); 180 181 EXPECT_EQ(cht->get_copy(thr, stl1), (uintptr_t)0) << "Odd value should not exist."; 182 EXPECT_FALSE(cht->remove(thr, stl1)) << "Odd value should not exist."; 183 EXPECT_EQ(cht->get_copy(thr, stl2), val2) << "Even value should not have been removed."; 184 EXPECT_EQ(cht->get_copy(thr, stl3), (uintptr_t)0) << "Add value should not exists."; 185 EXPECT_FALSE(cht->remove(thr, stl3)) << "Odd value should not exists."; 186 187 delete cht; 188 } 189 190 static void cht_getinsert_bulkdelete_task(Thread* thr) { 191 uintptr_t val1 = 1; 192 uintptr_t val2 = 2; 193 uintptr_t val3 = 3; 194 SimpleTestLookup stl1(val1), stl2(val2), stl3(val3); 195 196 SimpleTestTable* cht = new SimpleTestTable(); 197 cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, false, true); 198 cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); 199 cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, false, true); 200 201 EXPECT_TRUE(cht->remove(thr, stl2)) << "Remove did not find value."; 202 203 cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, true, false); // val1 should be present 204 cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); // val2 should be inserted 205 cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, true, false); // val3 should be present 206 207 EXPECT_EQ(cht->get_copy(thr, stl1), val1) << "Get did not find value."; 208 EXPECT_EQ(cht->get_copy(thr, stl2), val2) << "Get did not find value."; 209 EXPECT_EQ(cht->get_copy(thr, stl3), val3) << "Get did not find value."; 210 211 // Removes all odd values. 212 SimpleTestTable::BulkDeleteTask bdt(cht); 213 if (bdt.prepare(thr)) { 214 while(bdt.doTask(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del)) { 215 bdt.pause(thr); 216 EXPECT_TRUE(bdt.cont(thr)) << "Uncontended continue should work."; 217 } 218 bdt.done(thr); 219 } 220 221 EXPECT_EQ(cht->get_copy(thr, stl1), (uintptr_t)0) << "Odd value should not exist."; 222 EXPECT_FALSE(cht->remove(thr, stl1)) << "Odd value should not exist."; 223 EXPECT_EQ(cht->get_copy(thr, stl2), val2) << "Even value should not have been removed."; 224 EXPECT_EQ(cht->get_copy(thr, stl3), (uintptr_t)0) << "Add value should not exists."; 225 EXPECT_FALSE(cht->remove(thr, stl3)) << "Odd value should not exists."; 226 227 delete cht; 228 } 229 230 static void cht_scope(Thread* thr) { 231 uintptr_t val = 0x2; 232 SimpleTestLookup stl(val); 233 SimpleTestTable* cht = new SimpleTestTable(); 234 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed."; 235 { 236 SimpleTestGetHandle get_handle(thr, cht); 237 EXPECT_EQ(*get_handle.get(stl), val) << "Getting a pre-existing value failed."; 238 } 239 // We do remove here to make sure the value-handle 'unlocked' the table when leaving the scope. 240 EXPECT_TRUE(cht->remove(thr, stl)) << "Removing a pre-existing value failed."; 241 EXPECT_FALSE(cht->get_copy(thr, stl) == val) << "Got a removed value."; 242 delete cht; 243 } 244 245 struct ChtScan { 246 size_t _count; 247 ChtScan() : _count(0) {} 248 bool operator()(uintptr_t* val) { 249 EXPECT_EQ(*val, (uintptr_t)0x2) << "Got an unknown value."; 250 EXPECT_EQ(_count, 0u) << "Only one value should be in table."; 251 _count++; 252 return true; /* continue scan */ 253 } 254 }; 255 256 static void cht_scan(Thread* thr) { 257 uintptr_t val = 0x2; 258 SimpleTestLookup stl(val); 259 ChtScan scan; 260 SimpleTestTable* cht = new SimpleTestTable(); 261 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed."; 262 EXPECT_EQ(cht->try_scan(thr, scan), true) << "Scanning an non-growing/shrinking table should work."; 263 EXPECT_TRUE(cht->remove(thr, stl)) << "Removing a pre-existing value failed."; 264 EXPECT_FALSE(cht->get_copy(thr, stl) == val) << "Got a removed value."; 265 delete cht; 266 } 267 268 struct ChtCountScan { 269 size_t _count; 270 ChtCountScan() : _count(0) {} 271 bool operator()(uintptr_t* val) { 272 _count++; 273 return true; /* continue scan */ 274 } 275 }; 276 277 static void cht_move_to(Thread* thr) { 278 uintptr_t val1 = 0x2; 279 uintptr_t val2 = 0xe0000002; 280 uintptr_t val3 = 0x3; 281 SimpleTestLookup stl1(val1), stl2(val2), stl3(val3); 282 SimpleTestTable* from_cht = new SimpleTestTable(); 283 EXPECT_TRUE(from_cht->insert(thr, stl1, val1)) << "Insert unique value failed."; 284 EXPECT_TRUE(from_cht->insert(thr, stl2, val2)) << "Insert unique value failed."; 285 EXPECT_TRUE(from_cht->insert(thr, stl3, val3)) << "Insert unique value failed."; 286 287 SimpleTestTable* to_cht = new SimpleTestTable(); 288 EXPECT_TRUE(from_cht->try_move_nodes_to(thr, to_cht)) << "Moving nodes to new table failed"; 289 290 ChtCountScan scan_old; 291 EXPECT_TRUE(from_cht->try_scan(thr, scan_old)) << "Scanning table should work."; 292 EXPECT_EQ(scan_old._count, (size_t)0) << "All items should be moved"; 293 294 ChtCountScan scan_new; 295 EXPECT_TRUE(to_cht->try_scan(thr, scan_new)) << "Scanning table should work."; 296 EXPECT_EQ(scan_new._count, (size_t)3) << "All items should be moved"; 297 EXPECT_TRUE(to_cht->get_copy(thr, stl1) == val1) << "Getting an inserted value should work."; 298 EXPECT_TRUE(to_cht->get_copy(thr, stl2) == val2) << "Getting an inserted value should work."; 299 EXPECT_TRUE(to_cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work."; 300 } 301 302 static void cht_grow(Thread* thr) { 303 uintptr_t val = 0x2; 304 uintptr_t val2 = 0x22; 305 uintptr_t val3 = 0x222; 306 SimpleTestLookup stl(val), stl2(val2), stl3(val3); 307 SimpleTestTable* cht = new SimpleTestTable(); 308 309 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed."; 310 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed."; 311 EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed."; 312 EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed."; 313 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work."; 314 EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an inserted value should work."; 315 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work."; 316 317 EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work."; 318 319 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work."; 320 EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value should have failed."; 321 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work."; 322 323 324 EXPECT_TRUE(cht->grow(thr)) << "Growing uncontended should not fail."; 325 326 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after grow failed."; 327 EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value after grow should have failed."; 328 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an item after grow failed."; 329 330 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed."; 331 EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work."; 332 333 EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail."; 334 335 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after shrink failed."; 336 EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an item after shrink failed."; 337 EXPECT_FALSE(cht->get_copy(thr, stl3) == val3) << "Getting a removed value after shrink should have failed."; 338 339 delete cht; 340 } 341 342 static void cht_task_grow(Thread* thr) { 343 uintptr_t val = 0x2; 344 uintptr_t val2 = 0x22; 345 uintptr_t val3 = 0x222; 346 SimpleTestLookup stl(val), stl2(val2), stl3(val3); 347 SimpleTestTable* cht = new SimpleTestTable(); 348 349 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed."; 350 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed."; 351 EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed."; 352 EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed."; 353 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work."; 354 EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an inserted value should work."; 355 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work."; 356 357 EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work."; 358 359 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work."; 360 EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value should have failed."; 361 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work."; 362 363 SimpleTestTable::GrowTask gt(cht); 364 EXPECT_TRUE(gt.prepare(thr)) << "Growing uncontended should not fail."; 365 while(gt.doTask(thr)) { /* grow */ } 366 gt.done(thr); 367 368 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after grow failed."; 369 EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value after grow should have failed."; 370 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an item after grow failed."; 371 372 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed."; 373 EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work."; 374 375 EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail."; 376 377 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after shrink failed."; 378 EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an item after shrink failed."; 379 EXPECT_FALSE(cht->get_copy(thr, stl3) == val3) << "Getting a removed value after shrink should have failed."; 380 381 delete cht; 382 } 383 384 TEST_VM(ConcurrentHashTable, basic_insert) { 385 nomt_test_doer(cht_insert); 386 } 387 388 TEST_VM(ConcurrentHashTable, basic_get_insert) { 389 nomt_test_doer(cht_get_insert); 390 } 391 392 TEST_VM(ConcurrentHashTable, basic_scope) { 393 nomt_test_doer(cht_scope); 394 } 395 396 TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete) { 397 nomt_test_doer(cht_getinsert_bulkdelete); 398 } 399 400 TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete_task) { 401 nomt_test_doer(cht_getinsert_bulkdelete_task); 402 } 403 404 TEST_VM(ConcurrentHashTable, basic_scan) { 405 nomt_test_doer(cht_scan); 406 } 407 408 TEST_VM(ConcurrentHashTable, basic_move_to) { 409 nomt_test_doer(cht_move_to); 410 } 411 412 TEST_VM(ConcurrentHashTable, basic_grow) { 413 nomt_test_doer(cht_grow); 414 } 415 416 TEST_VM(ConcurrentHashTable, task_grow) { 417 nomt_test_doer(cht_task_grow); 418 } 419 420 //############################################################################################# 421 422 class TestInterface; 423 424 typedef ConcurrentHashTable<uintptr_t, TestInterface, mtInternal> TestTable; 425 typedef ConcurrentHashTable<uintptr_t, TestInterface, mtInternal>::MultiGetHandle TestGetHandle; 426 427 class TestInterface : public TestTable::BaseConfig { 428 public: 429 static uintx get_hash(const uintptr_t& value, bool* dead_hash) { 430 return (uintx)(value + 18446744073709551557ul) * 18446744073709551557ul; 431 } 432 static const uintptr_t& notfound() { 433 static uintptr_t notfound = 0; 434 return notfound; 435 } 436 }; 437 438 struct TestLookup { 439 uintptr_t _val; 440 TestLookup(uintptr_t val) : _val(val) {} 441 uintx get_hash() { 442 return TestInterface::get_hash(_val, NULL); 443 } 444 bool equals(const uintptr_t* value, bool* is_dead) { 445 return _val == *value; 446 } 447 }; 448 449 class CHTTestThread : public JavaTestThread { 450 public: 451 uintptr_t _start; 452 uintptr_t _stop; 453 TestTable *_cht; 454 jlong _stop_ms; 455 CHTTestThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) 456 : JavaTestThread(post), _start(start), _stop(stop), _cht(cht) {} 457 virtual void premain() {} 458 void main_run() { 459 premain(); 460 _stop_ms = os::javaTimeMillis() + 2000; // 2 seconds max test time 461 while (keep_looping() && test_loop()) { /* */ } 462 postmain(); 463 } 464 virtual void postmain() {} 465 virtual bool keep_looping() { 466 return _stop_ms > os::javaTimeMillis(); 467 }; 468 virtual bool test_loop() = 0; 469 virtual ~CHTTestThread() {} 470 }; 471 472 class ValueSaver { 473 uintptr_t* _vals; 474 size_t _it; 475 size_t _size; 476 public: 477 ValueSaver() : _it(0), _size(1024) { 478 _vals = NEW_C_HEAP_ARRAY(uintptr_t, _size, mtInternal); 479 } 480 481 bool operator()(uintptr_t* val) { 482 _vals[_it++] = *val; 483 if (_it == _size) { 484 _size *= 2; 485 _vals = REALLOC_RESOURCE_ARRAY(uintptr_t, _vals, _size/2, _size); 486 } 487 return true; 488 } 489 490 void check() { 491 for (size_t i = 0; i < _it; i++) { 492 size_t count = 0; 493 for (size_t j = (i + 1u); j < _it; j++) { 494 if (_vals[i] == _vals[j]) { 495 count++; 496 } 497 } 498 EXPECT_EQ(count, 0u); 499 } 500 } 501 }; 502 503 static void integrity_check(Thread* thr, TestTable* cht) 504 { 505 ValueSaver vs; 506 cht->do_scan(thr, vs); 507 vs.check(); 508 } 509 510 //############################################################################################# 511 // All threads are working on different items 512 // This item should only be delete by this thread 513 // Thus get_unsafe is safe for this test. 514 515 class SimpleInserterThread : public CHTTestThread { 516 public: 517 static volatile bool _exit; 518 519 SimpleInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) 520 : CHTTestThread(start, stop, cht, post) {}; 521 virtual ~SimpleInserterThread(){} 522 523 bool keep_looping() { 524 return !_exit; 525 } 526 527 bool test_loop() { 528 bool grow; 529 for (uintptr_t v = _start; v <= _stop; v++) { 530 TestLookup tl(v); 531 EXPECT_TRUE(_cht->insert(this, tl, v, &grow)) << "Inserting an unique value should work."; 532 } 533 for (uintptr_t v = _start; v <= _stop; v++) { 534 TestLookup tl(v); 535 EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed."; 536 } 537 for (uintptr_t v = _start; v <= _stop; v++) { 538 TestLookup tl(v); 539 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed."; 540 } 541 for (uintptr_t v = _start; v <= _stop; v++) { 542 TestLookup tl(v); 543 EXPECT_TRUE(_cht->get_copy(this, tl) == TestInterface::notfound()) << "Got a removed value."; 544 } 545 return true; 546 } 547 }; 548 549 volatile bool SimpleInserterThread::_exit = false; 550 551 class RunnerSimpleInserterThread : public CHTTestThread { 552 public: 553 Semaphore _done; 554 555 RunnerSimpleInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) { 556 _cht = new TestTable(SIZE_32, SIZE_32); 557 }; 558 virtual ~RunnerSimpleInserterThread(){} 559 560 void premain() { 561 562 SimpleInserterThread* ins1 = new SimpleInserterThread((uintptr_t)0x100, (uintptr_t) 0x1FF, _cht, &_done); 563 SimpleInserterThread* ins2 = new SimpleInserterThread((uintptr_t)0x200, (uintptr_t) 0x2FF, _cht, &_done); 564 SimpleInserterThread* ins3 = new SimpleInserterThread((uintptr_t)0x300, (uintptr_t) 0x3FF, _cht, &_done); 565 SimpleInserterThread* ins4 = new SimpleInserterThread((uintptr_t)0x400, (uintptr_t) 0x4FF, _cht, &_done); 566 567 for (uintptr_t v = 0x500; v < 0x5FF; v++ ) { 568 TestLookup tl(v); 569 EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work."; 570 } 571 572 ins1->doit(); 573 ins2->doit(); 574 ins3->doit(); 575 ins4->doit(); 576 577 } 578 579 bool test_loop() { 580 for (uintptr_t v = 0x500; v < 0x5FF; v++ ) { 581 TestLookup tl(v); 582 EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";; 583 } 584 return true; 585 } 586 587 void postmain() { 588 SimpleInserterThread::_exit = true; 589 for (int i = 0; i < 4; i++) { 590 _done.wait(); 591 } 592 for (uintptr_t v = 0x500; v < 0x5FF; v++ ) { 593 TestLookup tl(v); 594 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed."; 595 } 596 integrity_check(this, _cht); 597 delete _cht; 598 } 599 }; 600 601 602 TEST_VM(ConcurrentHashTable, concurrent_simple) { 603 SimpleInserterThread::_exit = false; 604 mt_test_doer<RunnerSimpleInserterThread>(); 605 } 606 607 //############################################################################################# 608 // In this test we try to get a 'bad' value 609 class DeleteInserterThread : public CHTTestThread { 610 public: 611 static volatile bool _exit; 612 613 DeleteInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {}; 614 virtual ~DeleteInserterThread(){} 615 616 bool keep_looping() { 617 return !_exit; 618 } 619 620 bool test_loop() { 621 for (uintptr_t v = _start; v <= _stop; v++) { 622 TestLookup tl(v); 623 _cht->insert(this, tl, v); 624 } 625 for (uintptr_t v = _start; v <= _stop; v++) { 626 TestLookup tl(v); 627 _cht->remove(this, tl); 628 } 629 return true; 630 } 631 }; 632 633 volatile bool DeleteInserterThread::_exit = true; 634 635 class RunnerDeleteInserterThread : public CHTTestThread { 636 public: 637 Semaphore _done; 638 639 RunnerDeleteInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) { 640 _cht = new TestTable(SIZE_32, SIZE_32); 641 }; 642 virtual ~RunnerDeleteInserterThread(){} 643 644 void premain() { 645 DeleteInserterThread* ins1 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done); 646 DeleteInserterThread* ins2 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done); 647 DeleteInserterThread* ins3 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done); 648 DeleteInserterThread* ins4 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done); 649 650 ins1->doit(); 651 ins2->doit(); 652 ins3->doit(); 653 ins4->doit(); 654 } 655 656 bool test_loop() { 657 for (uintptr_t v = 0x1; v < 0xFFF; v++ ) { 658 uintptr_t tv; 659 if (v & 0x1) { 660 TestLookup tl(v); 661 tv = _cht->get_copy(this, tl); 662 } else { 663 TestLookup tl(v); 664 TestGetHandle value_handle(this, _cht); 665 uintptr_t* tmp = value_handle.get(tl); 666 tv = tmp != NULL ? *tmp : 0; 667 } 668 EXPECT_TRUE(tv == 0 || tv == v) << "Got unknown value."; 669 } 670 return true; 671 } 672 673 void postmain() { 674 DeleteInserterThread::_exit = true; 675 for (int i = 0; i < 4; i++) { 676 _done.wait(); 677 } 678 integrity_check(this, _cht); 679 delete _cht; 680 } 681 }; 682 683 TEST_VM(ConcurrentHashTable, concurrent_deletes) { 684 DeleteInserterThread::_exit = false; 685 mt_test_doer<RunnerDeleteInserterThread>(); 686 } 687 688 //############################################################################################# 689 690 #define START_SIZE 13 691 #define END_SIZE 17 692 #define START (uintptr_t)0x10000 693 #define RANGE (uintptr_t)0xFFFF 694 695 #define GSTEST_THREAD_COUNT 5 696 697 698 class GSInserterThread: public CHTTestThread { 699 public: 700 static volatile bool _shrink; 701 GSInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {}; 702 virtual ~GSInserterThread(){} 703 bool keep_looping() { 704 return !(_shrink && _cht->get_size_log2(this) == START_SIZE); 705 } 706 bool test_loop() { 707 bool grow; 708 for (uintptr_t v = _start; v <= _stop; v++) { 709 TestLookup tl(v); 710 EXPECT_TRUE(_cht->insert(this, tl, v, &grow)) << "Inserting an unique value should work."; 711 if (grow && !_shrink) { 712 _cht->grow(this); 713 } 714 } 715 for (uintptr_t v = _start; v <= _stop; v++) { 716 TestLookup tl(v); 717 EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed."; 718 } 719 for (uintptr_t v = _start; v <= _stop; v++) { 720 TestLookup tl(v); 721 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed."; 722 } 723 if (_shrink) { 724 _cht->shrink(this); 725 } 726 for (uintptr_t v = _start; v <= _stop; v++) { 727 TestLookup tl(v); 728 EXPECT_FALSE(_cht->get_copy(this, tl) == v) << "Getting a removed value should have failed."; 729 } 730 if (!_shrink && _cht->get_size_log2(this) == END_SIZE) { 731 _shrink = true; 732 } 733 return true; 734 } 735 }; 736 737 volatile bool GSInserterThread::_shrink = false; 738 739 class GSScannerThread : public CHTTestThread { 740 public: 741 GSScannerThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {}; 742 virtual ~GSScannerThread(){} 743 744 bool operator()(uintptr_t* val) { 745 if (*val >= this->_start && *val <= this->_stop) { 746 return false; 747 } 748 // continue scan 749 return true; 750 } 751 752 bool test_loop() { 753 _cht->try_scan(this, *this); 754 os::naked_short_sleep(5); 755 return true; 756 } 757 }; 758 759 class RunnerGSInserterThread : public CHTTestThread { 760 public: 761 uintptr_t _start; 762 uintptr_t _range; 763 Semaphore _done; 764 765 RunnerGSInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) { 766 _cht = new TestTable(START_SIZE, END_SIZE, 2); 767 }; 768 virtual ~RunnerGSInserterThread(){} 769 770 void premain() { 771 volatile bool timeout = false; 772 _start = START; 773 _range = RANGE; 774 CHTTestThread* tt[GSTEST_THREAD_COUNT]; 775 tt[0] = new GSInserterThread(_start, _start + _range, _cht, &_done); 776 _start += _range + 1; 777 tt[1] = new GSInserterThread(_start, _start + _range, _cht, &_done); 778 _start += _range + 1; 779 tt[2] = new GSInserterThread(_start, _start + _range, _cht, &_done); 780 _start += _range + 1; 781 tt[3] = new GSInserterThread(_start, _start + _range, _cht, &_done); 782 tt[4] = new GSScannerThread(_start, _start + _range, _cht, &_done); 783 _start += _range + 1; 784 785 786 for (uintptr_t v = _start; v <= (_start + _range); v++ ) { 787 TestLookup tl(v); 788 EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work."; 789 } 790 791 for (int i = 0; i < GSTEST_THREAD_COUNT; i++) { 792 tt[i]->doit(); 793 } 794 } 795 796 bool test_loop() { 797 for (uintptr_t v = _start; v <= (_start + _range); v++ ) { 798 TestLookup tl(v); 799 EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed."; 800 } 801 return true; 802 } 803 804 void postmain() { 805 GSInserterThread::_shrink = true; 806 for (uintptr_t v = _start; v <= (_start + _range); v++ ) { 807 TestLookup tl(v); 808 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed."; 809 } 810 for (int i = 0; i < GSTEST_THREAD_COUNT; i++) { 811 _done.wait(); 812 } 813 EXPECT_TRUE(_cht->get_size_log2(this) == START_SIZE) << "Not at start size."; 814 Count cnt; 815 _cht->do_scan(this, cnt); 816 EXPECT_TRUE(cnt._cnt == 0) << "Items still in table"; 817 delete _cht; 818 } 819 820 struct Count { 821 Count() : _cnt(0) {} 822 size_t _cnt; 823 bool operator()(uintptr_t*) { _cnt++; return true; }; 824 }; 825 }; 826 827 TEST_VM(ConcurrentHashTable, concurrent_scan_grow_shrink) { 828 GSInserterThread::_shrink = false; 829 mt_test_doer<RunnerGSInserterThread>(); 830 } 831 832 833 //############################################################################################# 834 835 #define GI_BD_GI_BD_START_SIZE 13 836 #define GI_BD_END_SIZE 17 837 #define GI_BD_START (uintptr_t)0x1 838 #define GI_BD_RANGE (uintptr_t)0x3FFFF 839 840 #define GI_BD_TEST_THREAD_COUNT 4 841 842 843 class GI_BD_InserterThread: public CHTTestThread { 844 public: 845 static volatile bool _shrink; 846 uintptr_t _br; 847 GI_BD_InserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post, uintptr_t br) 848 : CHTTestThread(start, stop, cht, post), _br(br) {}; 849 virtual ~GI_BD_InserterThread(){} 850 851 bool keep_looping() { 852 return !(_shrink && _cht->get_size_log2(this) == GI_BD_GI_BD_START_SIZE); 853 } 854 855 bool test_loop() { 856 bool grow; 857 MyDel del(_br); 858 for (uintptr_t v = _start; v <= _stop; v++) { 859 ValVerify vv(v); 860 TestLookup tl(v); 861 _cht->get_insert(this, tl, v, vv, &grow); 862 EXPECT_NE(vv.called_get, vv.called_insert) << "Non or both callbacks was called."; 863 if (grow && !_shrink) { 864 _cht->grow(this); 865 } 866 } 867 if (_shrink) { 868 _cht->shrink(this); 869 } 870 _cht->try_bulk_delete(this, *this, del); 871 if (!_shrink && _cht->is_max_size_reached()) { 872 _shrink = true; 873 } 874 _cht->bulk_delete(this, *this, del); 875 return true; 876 } 877 878 bool operator()(uintptr_t* val) { 879 return (*val & _br) == 1; 880 } 881 882 struct MyDel { 883 MyDel(uintptr_t &br) : _br(br) {}; 884 uintptr_t &_br; 885 void operator()(uintptr_t* val) { 886 EXPECT_EQ((*val & _br), _br) << "Removing an item that should not have been removed."; 887 } 888 }; 889 }; 890 891 volatile bool GI_BD_InserterThread::_shrink = false; 892 893 class RunnerGI_BD_InserterThread : public CHTTestThread { 894 public: 895 Semaphore _done; 896 uintptr_t _start; 897 uintptr_t _range; 898 RunnerGI_BD_InserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) { 899 _cht = new TestTable(GI_BD_GI_BD_START_SIZE, GI_BD_END_SIZE, 2); 900 }; 901 virtual ~RunnerGI_BD_InserterThread(){} 902 903 void premain() { 904 _start = GI_BD_START; 905 _range = GI_BD_RANGE; 906 CHTTestThread* tt[GI_BD_TEST_THREAD_COUNT]; 907 tt[0] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x1); 908 tt[1] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x2); 909 tt[2] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x4); 910 tt[3] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x8); 911 912 for (uintptr_t v = _start; v <= (_start + _range); v++ ) { 913 TestLookup tl(v); 914 EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work."; 915 } 916 917 for (int i =0; i < GI_BD_TEST_THREAD_COUNT; i++) { 918 tt[i]->doit(); 919 } 920 } 921 922 bool test_loop() { 923 for (uintptr_t v = _start; v <= (_start + _range); v++ ) { 924 TestLookup tl(v); 925 if (v & 0xF) { 926 _cht->get_copy(this, tl); 927 } else { 928 EXPECT_EQ(_cht->get_copy(this, tl), v) << "Item ending with 0xX0 should never be removed."; 929 } 930 } 931 return true; 932 } 933 934 void postmain() { 935 GI_BD_InserterThread::_shrink = true; 936 for (uintptr_t v = _start; v <= (_start + _range); v++ ) { 937 TestLookup tl(v); 938 if (v & 0xF) { 939 _cht->remove(this, tl); 940 } else { 941 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing item ending with 0xX0 should always work."; 942 } 943 } 944 for (int i = 0; i < GI_BD_TEST_THREAD_COUNT; i++) { 945 _done.wait(); 946 } 947 EXPECT_TRUE(_cht->get_size_log2(this) == GI_BD_GI_BD_START_SIZE) << "We have not shrunk back to start size."; 948 delete _cht; 949 } 950 }; 951 952 TEST_VM(ConcurrentHashTable, concurrent_get_insert_bulk_delete) { 953 GI_BD_InserterThread::_shrink = false; 954 mt_test_doer<RunnerGI_BD_InserterThread>(); 955 }