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 static void cht_grow(Thread* thr) {
269 uintptr_t val = 0x2;
270 uintptr_t val2 = 0x22;
271 uintptr_t val3 = 0x222;
272 SimpleTestLookup stl(val), stl2(val2), stl3(val3);
273 SimpleTestTable* cht = new SimpleTestTable();
274
275 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
276 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
277 EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed.";
278 EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed.";
279 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work.";
280 EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an inserted value should work.";
281 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work.";
282
283 EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work.";
284
285 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work.";
286 EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value should have failed.";
287 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work.";
288
289
290 EXPECT_TRUE(cht->grow(thr)) << "Growing uncontended should not fail.";
291
292 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after grow failed.";
293 EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value after grow should have failed.";
294 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an item after grow failed.";
295
296 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
297 EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work.";
298
299 EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail.";
300
301 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after shrink failed.";
302 EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an item after shrink failed.";
303 EXPECT_FALSE(cht->get_copy(thr, stl3) == val3) << "Getting a removed value after shrink should have failed.";
304
305 delete cht;
306 }
307
308 static void cht_task_grow(Thread* thr) {
309 uintptr_t val = 0x2;
310 uintptr_t val2 = 0x22;
311 uintptr_t val3 = 0x222;
312 SimpleTestLookup stl(val), stl2(val2), stl3(val3);
313 SimpleTestTable* cht = new SimpleTestTable();
314
315 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
316 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
317 EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed.";
318 EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed.";
319 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work.";
320 EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an inserted value should work.";
321 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work.";
322
323 EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work.";
324
325 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an inserted value should work.";
326 EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value should have failed.";
327 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an inserted value should work.";
328
329 SimpleTestTable::GrowTask gt(cht);
330 EXPECT_TRUE(gt.prepare(thr)) << "Growing uncontended should not fail.";
331 while(gt.doTask(thr)) { /* grow */ }
332 gt.done(thr);
333
334 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after grow failed.";
335 EXPECT_FALSE(cht->get_copy(thr, stl2) == val2) << "Getting a removed value after grow should have failed.";
336 EXPECT_TRUE(cht->get_copy(thr, stl3) == val3) << "Getting an item after grow failed.";
337
338 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
339 EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work.";
340
341 EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail.";
342
343 EXPECT_TRUE(cht->get_copy(thr, stl) == val) << "Getting an item after shrink failed.";
344 EXPECT_TRUE(cht->get_copy(thr, stl2) == val2) << "Getting an item after shrink failed.";
345 EXPECT_FALSE(cht->get_copy(thr, stl3) == val3) << "Getting a removed value after shrink should have failed.";
346
347 delete cht;
348 }
349
350 TEST_VM(ConcurrentHashTable, basic_insert) {
351 nomt_test_doer(cht_insert);
352 }
353
354 TEST_VM(ConcurrentHashTable, basic_get_insert) {
355 nomt_test_doer(cht_get_insert);
356 }
357
358 TEST_VM(ConcurrentHashTable, basic_scope) {
359 nomt_test_doer(cht_scope);
360 }
361
362 TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete) {
363 nomt_test_doer(cht_getinsert_bulkdelete);
364 }
365
366 TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete_task) {
367 nomt_test_doer(cht_getinsert_bulkdelete_task);
368 }
369
370 TEST_VM(ConcurrentHashTable, basic_scan) {
371 nomt_test_doer(cht_scan);
372 }
373
374 TEST_VM(ConcurrentHashTable, basic_grow) {
375 nomt_test_doer(cht_grow);
376 }
377
378 TEST_VM(ConcurrentHashTable, task_grow) {
379 nomt_test_doer(cht_task_grow);
380 }
381
382 //#############################################################################################
383
384 class TestInterface;
385
386 typedef ConcurrentHashTable<uintptr_t, TestInterface, mtInternal> TestTable;
387 typedef ConcurrentHashTable<uintptr_t, TestInterface, mtInternal>::MultiGetHandle TestGetHandle;
388
389 class TestInterface : public TestTable::BaseConfig {
390 public:
391 static uintx get_hash(const uintptr_t& value, bool* dead_hash) {
392 return (uintx)(value + 18446744073709551557ul) * 18446744073709551557ul;
393 }
394 static const uintptr_t& notfound() {
395 static uintptr_t notfound = 0;
396 return notfound;
397 }
398 };
399
400 struct TestLookup {
401 uintptr_t _val;
402 TestLookup(uintptr_t val) : _val(val) {}
403 uintx get_hash() {
404 return TestInterface::get_hash(_val, NULL);
405 }
406 bool equals(const uintptr_t* value, bool* is_dead) {
407 return _val == *value;
408 }
409 };
410
411 class CHTTestThread : public JavaTestThread {
412 public:
413 uintptr_t _start;
414 uintptr_t _stop;
415 TestTable *_cht;
416 jlong _stop_ms;
417 CHTTestThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post)
418 : JavaTestThread(post), _start(start), _stop(stop), _cht(cht) {}
419 virtual void premain() {}
420 void main_run() {
421 premain();
422 _stop_ms = os::javaTimeMillis() + 2000; // 2 seconds max test time
423 while (keep_looping() && test_loop()) { /* */ }
424 postmain();
425 }
426 virtual void postmain() {}
427 virtual bool keep_looping() {
428 return _stop_ms > os::javaTimeMillis();
429 };
430 virtual bool test_loop() = 0;
431 virtual ~CHTTestThread() {}
432 };
433
434 class ValueSaver {
435 uintptr_t* _vals;
436 size_t _it;
437 size_t _size;
438 public:
439 ValueSaver() : _it(0), _size(1024) {
440 _vals = NEW_C_HEAP_ARRAY(uintptr_t, _size, mtInternal);
441 }
442
443 bool operator()(uintptr_t* val) {
444 _vals[_it++] = *val;
445 if (_it == _size) {
446 _size *= 2;
447 _vals = REALLOC_RESOURCE_ARRAY(uintptr_t, _vals, _size/2, _size);
448 }
449 return true;
450 }
451
452 void check() {
453 for (size_t i = 0; i < _it; i++) {
454 size_t count = 0;
455 for (size_t j = (i + 1u); j < _it; j++) {
456 if (_vals[i] == _vals[j]) {
457 count++;
458 }
459 }
460 EXPECT_EQ(count, 0u);
461 }
462 }
463 };
464
465 static void integrity_check(Thread* thr, TestTable* cht)
466 {
467 ValueSaver vs;
468 cht->do_scan(thr, vs);
469 vs.check();
470 }
471
472 //#############################################################################################
473 // All threads are working on different items
474 // This item should only be delete by this thread
475 // Thus get_unsafe is safe for this test.
476
477 class SimpleInserterThread : public CHTTestThread {
478 public:
479 static volatile bool _exit;
480
481 SimpleInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post)
482 : CHTTestThread(start, stop, cht, post) {};
483 virtual ~SimpleInserterThread(){}
484
485 bool keep_looping() {
486 return !_exit;
487 }
488
489 bool test_loop() {
490 bool grow;
491 for (uintptr_t v = _start; v <= _stop; v++) {
492 TestLookup tl(v);
493 EXPECT_TRUE(_cht->insert(this, tl, v, &grow)) << "Inserting an unique value should work.";
494 }
495 for (uintptr_t v = _start; v <= _stop; v++) {
496 TestLookup tl(v);
497 EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";
498 }
499 for (uintptr_t v = _start; v <= _stop; v++) {
500 TestLookup tl(v);
501 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed.";
502 }
503 for (uintptr_t v = _start; v <= _stop; v++) {
504 TestLookup tl(v);
505 EXPECT_TRUE(_cht->get_copy(this, tl) == TestInterface::notfound()) << "Got a removed value.";
506 }
507 return true;
508 }
509 };
510
511 volatile bool SimpleInserterThread::_exit = false;
512
513 class RunnerSimpleInserterThread : public CHTTestThread {
514 public:
515 Semaphore _done;
516
517 RunnerSimpleInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
518 _cht = new TestTable(SIZE_32, SIZE_32);
519 };
520 virtual ~RunnerSimpleInserterThread(){}
521
522 void premain() {
523
524 SimpleInserterThread* ins1 = new SimpleInserterThread((uintptr_t)0x100, (uintptr_t) 0x1FF, _cht, &_done);
525 SimpleInserterThread* ins2 = new SimpleInserterThread((uintptr_t)0x200, (uintptr_t) 0x2FF, _cht, &_done);
526 SimpleInserterThread* ins3 = new SimpleInserterThread((uintptr_t)0x300, (uintptr_t) 0x3FF, _cht, &_done);
527 SimpleInserterThread* ins4 = new SimpleInserterThread((uintptr_t)0x400, (uintptr_t) 0x4FF, _cht, &_done);
528
529 for (uintptr_t v = 0x500; v < 0x5FF; v++ ) {
530 TestLookup tl(v);
531 EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work.";
532 }
533
534 ins1->doit();
535 ins2->doit();
536 ins3->doit();
537 ins4->doit();
538
539 }
540
541 bool test_loop() {
542 for (uintptr_t v = 0x500; v < 0x5FF; v++ ) {
543 TestLookup tl(v);
544 EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";;
545 }
546 return true;
547 }
548
549 void postmain() {
550 SimpleInserterThread::_exit = true;
551 for (int i = 0; i < 4; i++) {
552 _done.wait();
553 }
554 for (uintptr_t v = 0x500; v < 0x5FF; v++ ) {
555 TestLookup tl(v);
556 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed.";
557 }
558 integrity_check(this, _cht);
559 delete _cht;
560 }
561 };
562
563
564 TEST_VM(ConcurrentHashTable, concurrent_simple) {
565 SimpleInserterThread::_exit = false;
566 mt_test_doer<RunnerSimpleInserterThread>();
567 }
568
569 //#############################################################################################
570 // In this test we try to get a 'bad' value
571 class DeleteInserterThread : public CHTTestThread {
572 public:
573 static volatile bool _exit;
574
575 DeleteInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
576 virtual ~DeleteInserterThread(){}
577
578 bool keep_looping() {
579 return !_exit;
580 }
581
582 bool test_loop() {
583 for (uintptr_t v = _start; v <= _stop; v++) {
584 TestLookup tl(v);
585 _cht->insert(this, tl, v);
586 }
587 for (uintptr_t v = _start; v <= _stop; v++) {
588 TestLookup tl(v);
589 _cht->remove(this, tl);
590 }
591 return true;
592 }
593 };
594
595 volatile bool DeleteInserterThread::_exit = true;
596
597 class RunnerDeleteInserterThread : public CHTTestThread {
598 public:
599 Semaphore _done;
600
601 RunnerDeleteInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
602 _cht = new TestTable(SIZE_32, SIZE_32);
603 };
604 virtual ~RunnerDeleteInserterThread(){}
605
606 void premain() {
607 DeleteInserterThread* ins1 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done);
608 DeleteInserterThread* ins2 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done);
609 DeleteInserterThread* ins3 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done);
610 DeleteInserterThread* ins4 = new DeleteInserterThread((uintptr_t)0x1, (uintptr_t) 0xFFF, _cht, &_done);
611
612 ins1->doit();
613 ins2->doit();
614 ins3->doit();
615 ins4->doit();
616 }
617
618 bool test_loop() {
619 for (uintptr_t v = 0x1; v < 0xFFF; v++ ) {
620 uintptr_t tv;
621 if (v & 0x1) {
622 TestLookup tl(v);
623 tv = _cht->get_copy(this, tl);
624 } else {
625 TestLookup tl(v);
626 TestGetHandle value_handle(this, _cht);
627 uintptr_t* tmp = value_handle.get(tl);
628 tv = tmp != NULL ? *tmp : 0;
629 }
630 EXPECT_TRUE(tv == 0 || tv == v) << "Got unknown value.";
631 }
632 return true;
633 }
634
635 void postmain() {
636 DeleteInserterThread::_exit = true;
637 for (int i = 0; i < 4; i++) {
638 _done.wait();
639 }
640 integrity_check(this, _cht);
641 delete _cht;
642 }
643 };
644
645 TEST_VM(ConcurrentHashTable, concurrent_deletes) {
646 DeleteInserterThread::_exit = false;
647 mt_test_doer<RunnerDeleteInserterThread>();
648 }
649
650 //#############################################################################################
651
652 #define START_SIZE 13
653 #define END_SIZE 17
654 #define START (uintptr_t)0x10000
655 #define RANGE (uintptr_t)0xFFFF
656
657 #define GSTEST_THREAD_COUNT 5
658
659
660 class GSInserterThread: public CHTTestThread {
661 public:
662 static volatile bool _shrink;
663 GSInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
664 virtual ~GSInserterThread(){}
665 bool keep_looping() {
666 return !(_shrink && _cht->get_size_log2(this) == START_SIZE);
667 }
668 bool test_loop() {
669 bool grow;
670 for (uintptr_t v = _start; v <= _stop; v++) {
671 TestLookup tl(v);
672 EXPECT_TRUE(_cht->insert(this, tl, v, &grow)) << "Inserting an unique value should work.";
673 if (grow && !_shrink) {
674 _cht->grow(this);
675 }
676 }
677 for (uintptr_t v = _start; v <= _stop; v++) {
678 TestLookup tl(v);
679 EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";
680 }
681 for (uintptr_t v = _start; v <= _stop; v++) {
682 TestLookup tl(v);
683 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed.";
684 }
685 if (_shrink) {
686 _cht->shrink(this);
687 }
688 for (uintptr_t v = _start; v <= _stop; v++) {
689 TestLookup tl(v);
690 EXPECT_FALSE(_cht->get_copy(this, tl) == v) << "Getting a removed value should have failed.";
691 }
692 if (!_shrink && _cht->get_size_log2(this) == END_SIZE) {
693 _shrink = true;
694 }
695 return true;
696 }
697 };
698
699 volatile bool GSInserterThread::_shrink = false;
700
701 class GSScannerThread : public CHTTestThread {
702 public:
703 GSScannerThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
704 virtual ~GSScannerThread(){}
705
706 bool operator()(uintptr_t* val) {
707 if (*val >= this->_start && *val <= this->_stop) {
708 return false;
709 }
710 // continue scan
711 return true;
712 }
713
714 bool test_loop() {
715 _cht->try_scan(this, *this);
716 os::naked_short_sleep(5);
717 return true;
718 }
719 };
720
721 class RunnerGSInserterThread : public CHTTestThread {
722 public:
723 uintptr_t _start;
724 uintptr_t _range;
725 Semaphore _done;
726
727 RunnerGSInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
728 _cht = new TestTable(START_SIZE, END_SIZE, 2);
729 };
730 virtual ~RunnerGSInserterThread(){}
731
732 void premain() {
733 volatile bool timeout = false;
734 _start = START;
735 _range = RANGE;
736 CHTTestThread* tt[GSTEST_THREAD_COUNT];
737 tt[0] = new GSInserterThread(_start, _start + _range, _cht, &_done);
738 _start += _range + 1;
739 tt[1] = new GSInserterThread(_start, _start + _range, _cht, &_done);
740 _start += _range + 1;
741 tt[2] = new GSInserterThread(_start, _start + _range, _cht, &_done);
742 _start += _range + 1;
743 tt[3] = new GSInserterThread(_start, _start + _range, _cht, &_done);
744 tt[4] = new GSScannerThread(_start, _start + _range, _cht, &_done);
745 _start += _range + 1;
746
747
748 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
749 TestLookup tl(v);
750 EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work.";
751 }
752
753 for (int i = 0; i < GSTEST_THREAD_COUNT; i++) {
754 tt[i]->doit();
755 }
756 }
757
758 bool test_loop() {
759 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
760 TestLookup tl(v);
761 EXPECT_TRUE(_cht->get_copy(this, tl) == v) << "Getting an previously inserted value unsafe failed.";
762 }
763 return true;
764 }
765
766 void postmain() {
767 GSInserterThread::_shrink = true;
768 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
769 TestLookup tl(v);
770 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing an existing value failed.";
771 }
772 for (int i = 0; i < GSTEST_THREAD_COUNT; i++) {
773 _done.wait();
774 }
775 EXPECT_TRUE(_cht->get_size_log2(this) == START_SIZE) << "Not at start size.";
776 Count cnt;
777 _cht->do_scan(this, cnt);
778 EXPECT_TRUE(cnt._cnt == 0) << "Items still in table";
779 delete _cht;
780 }
781
782 struct Count {
783 Count() : _cnt(0) {}
784 size_t _cnt;
785 bool operator()(uintptr_t*) { _cnt++; return true; };
786 };
787 };
788
789 TEST_VM(ConcurrentHashTable, concurrent_scan_grow_shrink) {
790 GSInserterThread::_shrink = false;
791 mt_test_doer<RunnerGSInserterThread>();
792 }
793
794
795 //#############################################################################################
796
797 #define GI_BD_GI_BD_START_SIZE 13
798 #define GI_BD_END_SIZE 17
799 #define GI_BD_START (uintptr_t)0x1
800 #define GI_BD_RANGE (uintptr_t)0x3FFFF
801
802 #define GI_BD_TEST_THREAD_COUNT 4
803
804
805 class GI_BD_InserterThread: public CHTTestThread {
806 public:
807 static volatile bool _shrink;
808 uintptr_t _br;
809 GI_BD_InserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post, uintptr_t br)
810 : CHTTestThread(start, stop, cht, post), _br(br) {};
811 virtual ~GI_BD_InserterThread(){}
812
813 bool keep_looping() {
814 return !(_shrink && _cht->get_size_log2(this) == GI_BD_GI_BD_START_SIZE);
815 }
816
817 bool test_loop() {
818 bool grow;
819 MyDel del(_br);
820 for (uintptr_t v = _start; v <= _stop; v++) {
821 ValVerify vv(v);
822 TestLookup tl(v);
823 _cht->get_insert(this, tl, v, vv, &grow);
824 EXPECT_NE(vv.called_get, vv.called_insert) << "Non or both callbacks was called.";
825 if (grow && !_shrink) {
826 _cht->grow(this);
827 }
828 }
829 if (_shrink) {
830 _cht->shrink(this);
831 }
832 _cht->try_bulk_delete(this, *this, del);
833 if (!_shrink && _cht->is_max_size_reached()) {
834 _shrink = true;
835 }
836 _cht->bulk_delete(this, *this, del);
837 return true;
838 }
839
840 bool operator()(uintptr_t* val) {
841 return (*val & _br) == 1;
842 }
843
844 struct MyDel {
845 MyDel(uintptr_t &br) : _br(br) {};
846 uintptr_t &_br;
847 void operator()(uintptr_t* val) {
848 EXPECT_EQ((*val & _br), _br) << "Removing an item that should not have been removed.";
849 }
850 };
851 };
852
853 volatile bool GI_BD_InserterThread::_shrink = false;
854
855 class RunnerGI_BD_InserterThread : public CHTTestThread {
856 public:
857 Semaphore _done;
858 uintptr_t _start;
859 uintptr_t _range;
860 RunnerGI_BD_InserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
861 _cht = new TestTable(GI_BD_GI_BD_START_SIZE, GI_BD_END_SIZE, 2);
862 };
863 virtual ~RunnerGI_BD_InserterThread(){}
864
865 void premain() {
866 _start = GI_BD_START;
867 _range = GI_BD_RANGE;
868 CHTTestThread* tt[GI_BD_TEST_THREAD_COUNT];
869 tt[0] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x1);
870 tt[1] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x2);
871 tt[2] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x4);
872 tt[3] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x8);
873
874 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
875 TestLookup tl(v);
876 EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work.";
877 }
878
879 for (int i =0; i < GI_BD_TEST_THREAD_COUNT; i++) {
880 tt[i]->doit();
881 }
882 }
883
884 bool test_loop() {
885 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
886 TestLookup tl(v);
887 if (v & 0xF) {
888 _cht->get_copy(this, tl);
889 } else {
890 EXPECT_EQ(_cht->get_copy(this, tl), v) << "Item ending with 0xX0 should never be removed.";
891 }
892 }
893 return true;
894 }
895
896 void postmain() {
897 GI_BD_InserterThread::_shrink = true;
898 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
899 TestLookup tl(v);
900 if (v & 0xF) {
901 _cht->remove(this, tl);
902 } else {
903 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing item ending with 0xX0 should always work.";
904 }
905 }
906 for (int i = 0; i < GI_BD_TEST_THREAD_COUNT; i++) {
907 _done.wait();
908 }
909 EXPECT_TRUE(_cht->get_size_log2(this) == GI_BD_GI_BD_START_SIZE) << "We have not shrunk back to start size.";
910 delete _cht;
911 }
912 };
913
914 TEST_VM(ConcurrentHashTable, concurrent_get_insert_bulk_delete) {
915 GI_BD_InserterThread::_shrink = false;
916 mt_test_doer<RunnerGI_BD_InserterThread>();
917 }