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