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 "threadHelper.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) : _val(val), called_get(false), called_insert(false) {}
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.do_task(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del)) {
215 bdt.pause(thr);
216 bdt.cont(thr);
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.do_task(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 }
956
957 //#############################################################################################
958
959 class MT_BD_Thread : public JavaTestThread {
960 TestTable::BulkDeleteTask* _bd;
961 public:
962 MT_BD_Thread(Semaphore* post, TestTable::BulkDeleteTask* bd)
963 : JavaTestThread(post), _bd(bd){}
964 virtual ~MT_BD_Thread() {}
965 void main_run() {
966 MyDel del;
967 while(_bd->do_task(this, *this, del));
968 }
969
970 bool operator()(uintptr_t* val) {
971 return true;
972 }
973
974 struct MyDel {
975 void operator()(uintptr_t* val) {
976 }
977 };
978 };
979
980 class Driver_BD_Thread : public JavaTestThread {
981 public:
982 Semaphore _done;
983 Driver_BD_Thread(Semaphore* post) : JavaTestThread(post) {
984 };
985 virtual ~Driver_BD_Thread(){}
986
987 void main_run() {
988 Semaphore done(0);
989 TestTable* cht = new TestTable(16, 16, 2);
990 for (uintptr_t v = 1; v < 99999; v++ ) {
991 TestLookup tl(v);
992 EXPECT_TRUE(cht->insert(this, tl, v)) << "Inserting an unique value should work.";
993 }
994 TestTable::BulkDeleteTask bdt(cht, true /* mt */ );
995 EXPECT_TRUE(bdt.prepare(this)) << "Uncontended prepare must work.";
996
997 MT_BD_Thread* tt[4];
998 for (int i = 0; i < 4; i++) {
999 tt[i] = new MT_BD_Thread(&done, &bdt);
1000 tt[i]->doit();
1001 }
1002
1003 for (uintptr_t v = 1; v < 99999; v++ ) {
1004 TestLookup tl(v);
1005 cht->get_copy(this, tl);
1006 }
1007
1008 for (int i = 0; i < 4; i++) {
1009 done.wait();
1010 }
1011
1012 bdt.done(this);
1013
1014 cht->do_scan(this, *this);
1015 }
1016
1017 bool operator()(uintptr_t* val) {
1018 EXPECT_TRUE(false) << "No items should left";
1019 return true;
1020 }
1021 };
1022
1023 TEST_VM(ConcurrentHashTable, concurrent_mt_bulk_delete) {
1024 mt_test_doer<Driver_BD_Thread>();
1025 }