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
39 struct Pointer : public AllStatic {
40 typedef uintptr_t Value;
get_hashPointer41 static uintx get_hash(const Value& value, bool* dead_hash) {
42 return (uintx)value;
43 }
allocate_nodePointer44 static void* allocate_node(size_t size, const Value& value) {
45 return ::malloc(size);
46 }
free_nodePointer47 static void free_node(void* memory, const Value& value) {
48 ::free(memory);
49 }
50 };
51
52 typedef ConcurrentHashTable<Pointer, mtInternal> SimpleTestTable;
53 typedef ConcurrentHashTable<Pointer, mtInternal>::MultiGetHandle SimpleTestGetHandle;
54
55 struct SimpleTestLookup {
56 uintptr_t _val;
SimpleTestLookupSimpleTestLookup57 SimpleTestLookup(uintptr_t val) : _val(val) {}
get_hashSimpleTestLookup58 uintx get_hash() {
59 return Pointer::get_hash(_val, NULL);
60 }
equalsSimpleTestLookup61 bool equals(const uintptr_t* value, bool* is_dead) {
62 return _val == *value;
63 }
64 };
65
66 struct ValueGet {
67 uintptr_t _return;
ValueGetValueGet68 ValueGet() : _return(0) {}
operator ()ValueGet69 void operator()(uintptr_t* value) {
70 EXPECT_NE(value, (uintptr_t*)NULL) << "expected valid value";
71 _return = *value;
72 }
get_valueValueGet73 uintptr_t get_value() const {
74 return _return;
75 }
76 };
77
cht_get_copy(SimpleTestTable * cht,Thread * thr,SimpleTestLookup stl)78 static uintptr_t cht_get_copy(SimpleTestTable* cht, Thread* thr, SimpleTestLookup stl) {
79 ValueGet vg;
80 cht->get(thr, stl, vg);
81 return vg.get_value();
82 }
83
cht_find(Thread * thr,SimpleTestTable * cht,uintptr_t val)84 static void cht_find(Thread* thr, SimpleTestTable* cht, uintptr_t val) {
85 SimpleTestLookup stl(val);
86 ValueGet vg;
87 EXPECT_EQ(cht->get(thr, stl, vg), true) << "Getting an old value failed.";
88 EXPECT_EQ(val, vg.get_value()) << "Getting an old value failed.";
89 }
90
cht_insert_and_find(Thread * thr,SimpleTestTable * cht,uintptr_t val)91 static void cht_insert_and_find(Thread* thr, SimpleTestTable* cht, uintptr_t val) {
92 SimpleTestLookup stl(val);
93 EXPECT_EQ(cht->insert(thr, stl, val), true) << "Inserting an unique value failed.";
94 cht_find(thr, cht, val);
95 }
96
cht_insert(Thread * thr)97 static void cht_insert(Thread* thr) {
98 uintptr_t val = 0x2;
99 SimpleTestLookup stl(val);
100 SimpleTestTable* cht = new SimpleTestTable();
101 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
102 EXPECT_EQ(cht_get_copy(cht, thr, stl), val) << "Getting an existing value failed.";
103 EXPECT_TRUE(cht->remove(thr, stl)) << "Removing an existing value failed.";
104 EXPECT_FALSE(cht->remove(thr, stl)) << "Removing an already removed item succeeded.";
105 EXPECT_NE(cht_get_copy(cht, thr, stl), val) << "Getting a removed value succeeded.";
106 delete cht;
107 }
108
cht_get_insert(Thread * thr)109 static void cht_get_insert(Thread* thr) {
110 uintptr_t val = 0x2;
111 SimpleTestLookup stl(val);
112 SimpleTestTable* cht = new SimpleTestTable();
113
114 {
115 SCOPED_TRACE("First");
116 cht_insert_and_find(thr, cht, val);
117 }
118 EXPECT_EQ(cht_get_copy(cht, thr, stl), val) << "Get an old value failed";
119 EXPECT_TRUE(cht->remove(thr, stl)) << "Removing existing value failed.";
120 EXPECT_NE(cht_get_copy(cht, thr, stl), val) << "Got an already removed item.";
121
122 {
123 SCOPED_TRACE("Second");
124 cht_insert_and_find(thr, cht, val);
125 }
126
127 delete cht;
128 }
129
getinsert_bulkdelete_eval(uintptr_t * val)130 static bool getinsert_bulkdelete_eval(uintptr_t* val) {
131 EXPECT_TRUE(*val > 0 && *val < 4) << "Val wrong for this test.";
132 return (*val & 0x1); // Delete all values ending with first bit set.
133 }
134
getinsert_bulkdelete_del(uintptr_t * val)135 static void getinsert_bulkdelete_del(uintptr_t* val) {
136 EXPECT_EQ(*val & 0x1, (uintptr_t)1) << "Deleting wrong value.";
137 }
138
cht_getinsert_bulkdelete_insert_verified(Thread * thr,SimpleTestTable * cht,uintptr_t val,bool verify_expect_get,bool verify_expect_inserted)139 static void cht_getinsert_bulkdelete_insert_verified(Thread* thr, SimpleTestTable* cht, uintptr_t val,
140 bool verify_expect_get, bool verify_expect_inserted) {
141 SimpleTestLookup stl(val);
142 if (verify_expect_inserted) {
143 cht_insert_and_find(thr, cht, val);
144 }
145 if (verify_expect_get) {
146 cht_find(thr, cht, val);
147 }
148 }
149
cht_getinsert_bulkdelete(Thread * thr)150 static void cht_getinsert_bulkdelete(Thread* thr) {
151 uintptr_t val1 = 1;
152 uintptr_t val2 = 2;
153 uintptr_t val3 = 3;
154 SimpleTestLookup stl1(val1), stl2(val2), stl3(val3);
155
156 SimpleTestTable* cht = new SimpleTestTable();
157 cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, false, true);
158 cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true);
159 cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, false, true);
160
161 EXPECT_TRUE(cht->remove(thr, stl2)) << "Remove did not find value.";
162
163 cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, true, false); // val1 should be present
164 cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); // val2 should be inserted
165 cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, true, false); // val3 should be present
166
167 EXPECT_EQ(cht_get_copy(cht, thr, stl1), val1) << "Get did not find value.";
168 EXPECT_EQ(cht_get_copy(cht, thr, stl2), val2) << "Get did not find value.";
169 EXPECT_EQ(cht_get_copy(cht, thr, stl3), val3) << "Get did not find value.";
170
171 // Removes all odd values.
172 cht->bulk_delete(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del);
173
174 EXPECT_EQ(cht_get_copy(cht, thr, stl1), (uintptr_t)0) << "Odd value should not exist.";
175 EXPECT_FALSE(cht->remove(thr, stl1)) << "Odd value should not exist.";
176 EXPECT_EQ(cht_get_copy(cht, thr, stl2), val2) << "Even value should not have been removed.";
177 EXPECT_EQ(cht_get_copy(cht, thr, stl3), (uintptr_t)0) << "Add value should not exists.";
178 EXPECT_FALSE(cht->remove(thr, stl3)) << "Odd value should not exists.";
179
180 delete cht;
181 }
182
cht_getinsert_bulkdelete_task(Thread * thr)183 static void cht_getinsert_bulkdelete_task(Thread* thr) {
184 uintptr_t val1 = 1;
185 uintptr_t val2 = 2;
186 uintptr_t val3 = 3;
187 SimpleTestLookup stl1(val1), stl2(val2), stl3(val3);
188
189 SimpleTestTable* cht = new SimpleTestTable();
190 cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, false, true);
191 cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true);
192 cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, false, true);
193
194 EXPECT_TRUE(cht->remove(thr, stl2)) << "Remove did not find value.";
195
196 cht_getinsert_bulkdelete_insert_verified(thr, cht, val1, true, false); // val1 should be present
197 cht_getinsert_bulkdelete_insert_verified(thr, cht, val2, false, true); // val2 should be inserted
198 cht_getinsert_bulkdelete_insert_verified(thr, cht, val3, true, false); // val3 should be present
199
200 EXPECT_EQ(cht_get_copy(cht, thr, stl1), val1) << "Get did not find value.";
201 EXPECT_EQ(cht_get_copy(cht, thr, stl2), val2) << "Get did not find value.";
202 EXPECT_EQ(cht_get_copy(cht, thr, stl3), val3) << "Get did not find value.";
203
204 // Removes all odd values.
205 SimpleTestTable::BulkDeleteTask bdt(cht);
206 if (bdt.prepare(thr)) {
207 while(bdt.do_task(thr, getinsert_bulkdelete_eval, getinsert_bulkdelete_del)) {
208 bdt.pause(thr);
209 bdt.cont(thr);
210 }
211 bdt.done(thr);
212 }
213
214 EXPECT_EQ(cht_get_copy(cht, thr, stl1), (uintptr_t)0) << "Odd value should not exist.";
215 EXPECT_FALSE(cht->remove(thr, stl1)) << "Odd value should not exist.";
216 EXPECT_EQ(cht_get_copy(cht, thr, stl2), val2) << "Even value should not have been removed.";
217 EXPECT_EQ(cht_get_copy(cht, thr, stl3), (uintptr_t)0) << "Add value should not exists.";
218 EXPECT_FALSE(cht->remove(thr, stl3)) << "Odd value should not exists.";
219
220 delete cht;
221 }
222
cht_scope(Thread * thr)223 static void cht_scope(Thread* thr) {
224 uintptr_t val = 0x2;
225 SimpleTestLookup stl(val);
226 SimpleTestTable* cht = new SimpleTestTable();
227 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
228 {
229 SimpleTestGetHandle get_handle(thr, cht);
230 EXPECT_EQ(*get_handle.get(stl), val) << "Getting a pre-existing value failed.";
231 }
232 // We do remove here to make sure the value-handle 'unlocked' the table when leaving the scope.
233 EXPECT_TRUE(cht->remove(thr, stl)) << "Removing a pre-existing value failed.";
234 EXPECT_FALSE(cht_get_copy(cht, thr, stl) == val) << "Got a removed value.";
235 delete cht;
236 }
237
238 struct ChtScan {
239 size_t _count;
ChtScanChtScan240 ChtScan() : _count(0) {}
operator ()ChtScan241 bool operator()(uintptr_t* val) {
242 EXPECT_EQ(*val, (uintptr_t)0x2) << "Got an unknown value.";
243 EXPECT_EQ(_count, 0u) << "Only one value should be in table.";
244 _count++;
245 return true; /* continue scan */
246 }
247 };
248
cht_scan(Thread * thr)249 static void cht_scan(Thread* thr) {
250 uintptr_t val = 0x2;
251 SimpleTestLookup stl(val);
252 ChtScan scan;
253 SimpleTestTable* cht = new SimpleTestTable();
254 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
255 EXPECT_EQ(cht->try_scan(thr, scan), true) << "Scanning an non-growing/shrinking table should work.";
256 EXPECT_TRUE(cht->remove(thr, stl)) << "Removing a pre-existing value failed.";
257 EXPECT_FALSE(cht_get_copy(cht, thr, stl) == val) << "Got a removed value.";
258 delete cht;
259 }
260
261 struct ChtCountScan {
262 size_t _count;
ChtCountScanChtCountScan263 ChtCountScan() : _count(0) {}
operator ()ChtCountScan264 bool operator()(uintptr_t* val) {
265 _count++;
266 return true; /* continue scan */
267 }
268 };
269
cht_move_to(Thread * thr)270 static void cht_move_to(Thread* thr) {
271 uintptr_t val1 = 0x2;
272 uintptr_t val2 = 0xe0000002;
273 uintptr_t val3 = 0x3;
274 SimpleTestLookup stl1(val1), stl2(val2), stl3(val3);
275 SimpleTestTable* from_cht = new SimpleTestTable();
276 EXPECT_TRUE(from_cht->insert(thr, stl1, val1)) << "Insert unique value failed.";
277 EXPECT_TRUE(from_cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
278 EXPECT_TRUE(from_cht->insert(thr, stl3, val3)) << "Insert unique value failed.";
279
280 SimpleTestTable* to_cht = new SimpleTestTable();
281 EXPECT_TRUE(from_cht->try_move_nodes_to(thr, to_cht)) << "Moving nodes to new table failed";
282
283 ChtCountScan scan_old;
284 EXPECT_TRUE(from_cht->try_scan(thr, scan_old)) << "Scanning table should work.";
285 EXPECT_EQ(scan_old._count, (size_t)0) << "All items should be moved";
286
287 ChtCountScan scan_new;
288 EXPECT_TRUE(to_cht->try_scan(thr, scan_new)) << "Scanning table should work.";
289 EXPECT_EQ(scan_new._count, (size_t)3) << "All items should be moved";
290 EXPECT_TRUE(cht_get_copy(to_cht, thr, stl1) == val1) << "Getting an inserted value should work.";
291 EXPECT_TRUE(cht_get_copy(to_cht, thr, stl2) == val2) << "Getting an inserted value should work.";
292 EXPECT_TRUE(cht_get_copy(to_cht, thr, stl3) == val3) << "Getting an inserted value should work.";
293 }
294
cht_grow(Thread * thr)295 static void cht_grow(Thread* thr) {
296 uintptr_t val = 0x2;
297 uintptr_t val2 = 0x22;
298 uintptr_t val3 = 0x222;
299 SimpleTestLookup stl(val), stl2(val2), stl3(val3);
300 SimpleTestTable* cht = new SimpleTestTable();
301
302 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
303 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
304 EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed.";
305 EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed.";
306 EXPECT_TRUE(cht_get_copy(cht, thr, stl) == val) << "Getting an inserted value should work.";
307 EXPECT_TRUE(cht_get_copy(cht, thr, stl2) == val2) << "Getting an inserted value should work.";
308 EXPECT_TRUE(cht_get_copy(cht, thr, stl3) == val3) << "Getting an inserted value should work.";
309
310 EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work.";
311
312 EXPECT_TRUE(cht_get_copy(cht, thr, stl) == val) << "Getting an inserted value should work.";
313 EXPECT_FALSE(cht_get_copy(cht, thr, stl2) == val2) << "Getting a removed value should have failed.";
314 EXPECT_TRUE(cht_get_copy(cht, thr, stl3) == val3) << "Getting an inserted value should work.";
315
316
317 EXPECT_TRUE(cht->grow(thr)) << "Growing uncontended should not fail.";
318
319 EXPECT_TRUE(cht_get_copy(cht, thr, stl) == val) << "Getting an item after grow failed.";
320 EXPECT_FALSE(cht_get_copy(cht, thr, stl2) == val2) << "Getting a removed value after grow should have failed.";
321 EXPECT_TRUE(cht_get_copy(cht, thr, stl3) == val3) << "Getting an item after grow failed.";
322
323 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
324 EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work.";
325
326 EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail.";
327
328 EXPECT_TRUE(cht_get_copy(cht, thr, stl) == val) << "Getting an item after shrink failed.";
329 EXPECT_TRUE(cht_get_copy(cht, thr, stl2) == val2) << "Getting an item after shrink failed.";
330 EXPECT_FALSE(cht_get_copy(cht, thr, stl3) == val3) << "Getting a removed value after shrink should have failed.";
331
332 delete cht;
333 }
334
cht_task_grow(Thread * thr)335 static void cht_task_grow(Thread* thr) {
336 uintptr_t val = 0x2;
337 uintptr_t val2 = 0x22;
338 uintptr_t val3 = 0x222;
339 SimpleTestLookup stl(val), stl2(val2), stl3(val3);
340 SimpleTestTable* cht = new SimpleTestTable();
341
342 EXPECT_TRUE(cht->insert(thr, stl, val)) << "Insert unique value failed.";
343 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
344 EXPECT_TRUE(cht->insert(thr, stl3, val3)) << "Insert unique value failed.";
345 EXPECT_FALSE(cht->insert(thr, stl3, val3)) << "Insert duplicate value should have failed.";
346 EXPECT_TRUE(cht_get_copy(cht, thr, stl) == val) << "Getting an inserted value should work.";
347 EXPECT_TRUE(cht_get_copy(cht, thr, stl2) == val2) << "Getting an inserted value should work.";
348 EXPECT_TRUE(cht_get_copy(cht, thr, stl3) == val3) << "Getting an inserted value should work.";
349
350 EXPECT_TRUE(cht->remove(thr, stl2)) << "Removing an inserted value should work.";
351
352 EXPECT_TRUE(cht_get_copy(cht, thr, stl) == val) << "Getting an inserted value should work.";
353 EXPECT_FALSE(cht_get_copy(cht, thr, stl2) == val2) << "Getting a removed value should have failed.";
354 EXPECT_TRUE(cht_get_copy(cht, thr, stl3) == val3) << "Getting an inserted value should work.";
355
356 SimpleTestTable::GrowTask gt(cht);
357 EXPECT_TRUE(gt.prepare(thr)) << "Growing uncontended should not fail.";
358 while(gt.do_task(thr)) { /* grow */ }
359 gt.done(thr);
360
361 EXPECT_TRUE(cht_get_copy(cht, thr, stl) == val) << "Getting an item after grow failed.";
362 EXPECT_FALSE(cht_get_copy(cht, thr, stl2) == val2) << "Getting a removed value after grow should have failed.";
363 EXPECT_TRUE(cht_get_copy(cht, thr, stl3) == val3) << "Getting an item after grow failed.";
364
365 EXPECT_TRUE(cht->insert(thr, stl2, val2)) << "Insert unique value failed.";
366 EXPECT_TRUE(cht->remove(thr, stl3)) << "Removing an inserted value should work.";
367
368 EXPECT_TRUE(cht->shrink(thr)) << "Shrinking uncontended should not fail.";
369
370 EXPECT_TRUE(cht_get_copy(cht, thr, stl) == val) << "Getting an item after shrink failed.";
371 EXPECT_TRUE(cht_get_copy(cht, thr, stl2) == val2) << "Getting an item after shrink failed.";
372 EXPECT_FALSE(cht_get_copy(cht, thr, stl3) == val3) << "Getting a removed value after shrink should have failed.";
373
374 delete cht;
375 }
376
TEST_VM(ConcurrentHashTable,basic_insert)377 TEST_VM(ConcurrentHashTable, basic_insert) {
378 nomt_test_doer(cht_insert);
379 }
380
TEST_VM(ConcurrentHashTable,basic_get_insert)381 TEST_VM(ConcurrentHashTable, basic_get_insert) {
382 nomt_test_doer(cht_get_insert);
383 }
384
TEST_VM(ConcurrentHashTable,basic_scope)385 TEST_VM(ConcurrentHashTable, basic_scope) {
386 nomt_test_doer(cht_scope);
387 }
388
TEST_VM(ConcurrentHashTable,basic_get_insert_bulk_delete)389 TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete) {
390 nomt_test_doer(cht_getinsert_bulkdelete);
391 }
392
TEST_VM(ConcurrentHashTable,basic_get_insert_bulk_delete_task)393 TEST_VM(ConcurrentHashTable, basic_get_insert_bulk_delete_task) {
394 nomt_test_doer(cht_getinsert_bulkdelete_task);
395 }
396
TEST_VM(ConcurrentHashTable,basic_scan)397 TEST_VM(ConcurrentHashTable, basic_scan) {
398 nomt_test_doer(cht_scan);
399 }
400
TEST_VM(ConcurrentHashTable,basic_move_to)401 TEST_VM(ConcurrentHashTable, basic_move_to) {
402 nomt_test_doer(cht_move_to);
403 }
404
TEST_VM(ConcurrentHashTable,basic_grow)405 TEST_VM(ConcurrentHashTable, basic_grow) {
406 nomt_test_doer(cht_grow);
407 }
408
TEST_VM(ConcurrentHashTable,task_grow)409 TEST_VM(ConcurrentHashTable, task_grow) {
410 nomt_test_doer(cht_task_grow);
411 }
412
413 //#############################################################################################
414
415 class TestInterface : public AllStatic {
416 public:
417 typedef uintptr_t Value;
get_hash(const Value & value,bool * dead_hash)418 static uintx get_hash(const Value& value, bool* dead_hash) {
419 return (uintx)(value + 18446744073709551557ul) * 18446744073709551557ul;
420 }
allocate_node(size_t size,const Value & value)421 static void* allocate_node(size_t size, const Value& value) {
422 return AllocateHeap(size, mtInternal);
423 }
free_node(void * memory,const Value & value)424 static void free_node(void* memory, const Value& value) {
425 FreeHeap(memory);
426 }
427 };
428
429 typedef ConcurrentHashTable<TestInterface, mtInternal> TestTable;
430 typedef ConcurrentHashTable<TestInterface, mtInternal>::MultiGetHandle TestGetHandle;
431
432 struct TestLookup {
433 uintptr_t _val;
TestLookupTestLookup434 TestLookup(uintptr_t val) : _val(val) {}
get_hashTestLookup435 uintx get_hash() {
436 return TestInterface::get_hash(_val, NULL);
437 }
equalsTestLookup438 bool equals(const uintptr_t* value, bool* is_dead) {
439 return _val == *value;
440 }
441 };
442
cht_get_copy(TestTable * cht,Thread * thr,TestLookup tl)443 static uintptr_t cht_get_copy(TestTable* cht, Thread* thr, TestLookup tl) {
444 ValueGet vg;
445 cht->get(thr, tl, vg);
446 return vg.get_value();
447 }
448
449 class CHTTestThread : public JavaTestThread {
450 public:
451 uintptr_t _start;
452 uintptr_t _stop;
453 TestTable *_cht;
454 jlong _stop_ms;
CHTTestThread(uintptr_t start,uintptr_t stop,TestTable * cht,Semaphore * post)455 CHTTestThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post)
456 : JavaTestThread(post), _start(start), _stop(stop), _cht(cht) {}
premain()457 virtual void premain() {}
main_run()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 }
postmain()464 virtual void postmain() {}
keep_looping()465 virtual bool keep_looping() {
466 return _stop_ms > os::javaTimeMillis();
467 };
468 virtual bool test_loop() = 0;
~CHTTestThread()469 virtual ~CHTTestThread() {}
470 };
471
472 class ValueSaver {
473 uintptr_t* _vals;
474 size_t _it;
475 size_t _size;
476 public:
ValueSaver()477 ValueSaver() : _it(0), _size(1024) {
478 _vals = NEW_C_HEAP_ARRAY(uintptr_t, _size, mtInternal);
479 }
480
operator ()(uintptr_t * val)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
check()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
integrity_check(Thread * thr,TestTable * cht)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
SimpleInserterThread(uintptr_t start,uintptr_t stop,TestTable * cht,Semaphore * post)519 SimpleInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post)
520 : CHTTestThread(start, stop, cht, post) {};
~SimpleInserterThread()521 virtual ~SimpleInserterThread(){}
522
keep_looping()523 bool keep_looping() {
524 return !_exit;
525 }
526
test_loop()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(_cht, 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(_cht, this, tl) == 0) << "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
RunnerSimpleInserterThread(Semaphore * post)555 RunnerSimpleInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
556 _cht = new TestTable(SIZE_32, SIZE_32);
557 };
~RunnerSimpleInserterThread()558 virtual ~RunnerSimpleInserterThread(){}
559
premain()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
test_loop()579 bool test_loop() {
580 for (uintptr_t v = 0x500; v < 0x5FF; v++ ) {
581 TestLookup tl(v);
582 EXPECT_TRUE(cht_get_copy(_cht, this, tl) == v) << "Getting an previously inserted value unsafe failed.";;
583 }
584 return true;
585 }
586
postmain()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
TEST_VM(ConcurrentHashTable,concurrent_simple)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
DeleteInserterThread(uintptr_t start,uintptr_t stop,TestTable * cht,Semaphore * post)613 DeleteInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
~DeleteInserterThread()614 virtual ~DeleteInserterThread(){}
615
keep_looping()616 bool keep_looping() {
617 return !_exit;
618 }
619
test_loop()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
RunnerDeleteInserterThread(Semaphore * post)639 RunnerDeleteInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
640 _cht = new TestTable(SIZE_32, SIZE_32);
641 };
~RunnerDeleteInserterThread()642 virtual ~RunnerDeleteInserterThread(){}
643
premain()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
test_loop()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(_cht, 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
postmain()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
TEST_VM(ConcurrentHashTable,concurrent_deletes)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;
GSInserterThread(uintptr_t start,uintptr_t stop,TestTable * cht,Semaphore * post)701 GSInserterThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
~GSInserterThread()702 virtual ~GSInserterThread(){}
keep_looping()703 bool keep_looping() {
704 return !(_shrink && _cht->get_size_log2(this) == START_SIZE);
705 }
test_loop()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(_cht, 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(_cht, 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:
GSScannerThread(uintptr_t start,uintptr_t stop,TestTable * cht,Semaphore * post)741 GSScannerThread(uintptr_t start, uintptr_t stop, TestTable* cht, Semaphore* post) : CHTTestThread(start, stop, cht, post) {};
~GSScannerThread()742 virtual ~GSScannerThread(){}
743
operator ()(uintptr_t * val)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
test_loop()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
RunnerGSInserterThread(Semaphore * post)765 RunnerGSInserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
766 _cht = new TestTable(START_SIZE, END_SIZE, 2);
767 };
~RunnerGSInserterThread()768 virtual ~RunnerGSInserterThread(){}
769
premain()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
test_loop()796 bool test_loop() {
797 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
798 TestLookup tl(v);
799 EXPECT_TRUE(cht_get_copy(_cht, this, tl) == v) << "Getting an previously inserted value unsafe failed.";
800 }
801 return true;
802 }
803
postmain()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 {
CountRunnerGSInserterThread::Count821 Count() : _cnt(0) {}
822 size_t _cnt;
operator ()RunnerGSInserterThread::Count823 bool operator()(uintptr_t*) { _cnt++; return true; };
824 };
825 };
826
TEST_VM(ConcurrentHashTable,concurrent_scan_grow_shrink)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;
GI_BD_InserterThread(uintptr_t start,uintptr_t stop,TestTable * cht,Semaphore * post,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) {};
~GI_BD_InserterThread()849 virtual ~GI_BD_InserterThread(){}
850
keep_looping()851 bool keep_looping() {
852 return !(_shrink && _cht->get_size_log2(this) == GI_BD_GI_BD_START_SIZE);
853 }
854
test_loop()855 bool test_loop() {
856 bool grow;
857 MyDel del(_br);
858 for (uintptr_t v = _start; v <= _stop; v++) {
859 {
860 TestLookup tl(v);
861 ValueGet vg;
862 do {
863 if (_cht->get(this, tl, vg, &grow)) {
864 EXPECT_EQ(v, vg.get_value()) << "Getting an old value failed.";
865 break;
866 }
867 if (_cht->insert(this, tl, v, &grow)) {
868 break;
869 }
870 } while(true);
871 }
872 if (grow && !_shrink) {
873 _cht->grow(this);
874 }
875 }
876 if (_shrink) {
877 _cht->shrink(this);
878 }
879 _cht->try_bulk_delete(this, *this, del);
880 if (!_shrink && _cht->is_max_size_reached()) {
881 _shrink = true;
882 }
883 _cht->bulk_delete(this, *this, del);
884 return true;
885 }
886
operator ()(uintptr_t * val)887 bool operator()(uintptr_t* val) {
888 return (*val & _br) == 1;
889 }
890
891 struct MyDel {
MyDelGI_BD_InserterThread::MyDel892 MyDel(uintptr_t &br) : _br(br) {};
893 uintptr_t &_br;
operator ()GI_BD_InserterThread::MyDel894 void operator()(uintptr_t* val) {
895 EXPECT_EQ((*val & _br), _br) << "Removing an item that should not have been removed.";
896 }
897 };
898 };
899
900 volatile bool GI_BD_InserterThread::_shrink = false;
901
902 class RunnerGI_BD_InserterThread : public CHTTestThread {
903 public:
904 Semaphore _done;
905 uintptr_t _start;
906 uintptr_t _range;
RunnerGI_BD_InserterThread(Semaphore * post)907 RunnerGI_BD_InserterThread(Semaphore* post) : CHTTestThread(0, 0, NULL, post) {
908 _cht = new TestTable(GI_BD_GI_BD_START_SIZE, GI_BD_END_SIZE, 2);
909 };
~RunnerGI_BD_InserterThread()910 virtual ~RunnerGI_BD_InserterThread(){}
911
premain()912 void premain() {
913 _start = GI_BD_START;
914 _range = GI_BD_RANGE;
915 CHTTestThread* tt[GI_BD_TEST_THREAD_COUNT];
916 tt[0] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x1);
917 tt[1] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x2);
918 tt[2] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x4);
919 tt[3] = new GI_BD_InserterThread(_start, _start + _range, _cht, &_done, (uintptr_t)0x8);
920
921 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
922 TestLookup tl(v);
923 EXPECT_TRUE(_cht->insert(this, tl, v)) << "Inserting an unique value should work.";
924 }
925
926 for (int i =0; i < GI_BD_TEST_THREAD_COUNT; i++) {
927 tt[i]->doit();
928 }
929 }
930
test_loop()931 bool test_loop() {
932 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
933 TestLookup tl(v);
934 if (v & 0xF) {
935 cht_get_copy(_cht, this, tl);
936 } else {
937 EXPECT_EQ(cht_get_copy(_cht, this, tl), v) << "Item ending with 0xX0 should never be removed.";
938 }
939 }
940 return true;
941 }
942
postmain()943 void postmain() {
944 GI_BD_InserterThread::_shrink = true;
945 for (uintptr_t v = _start; v <= (_start + _range); v++ ) {
946 TestLookup tl(v);
947 if (v & 0xF) {
948 _cht->remove(this, tl);
949 } else {
950 EXPECT_TRUE(_cht->remove(this, tl)) << "Removing item ending with 0xX0 should always work.";
951 }
952 }
953 for (int i = 0; i < GI_BD_TEST_THREAD_COUNT; i++) {
954 _done.wait();
955 }
956 EXPECT_TRUE(_cht->get_size_log2(this) == GI_BD_GI_BD_START_SIZE) << "We have not shrunk back to start size.";
957 delete _cht;
958 }
959 };
960
TEST_VM(ConcurrentHashTable,concurrent_get_insert_bulk_delete)961 TEST_VM(ConcurrentHashTable, concurrent_get_insert_bulk_delete) {
962 GI_BD_InserterThread::_shrink = false;
963 mt_test_doer<RunnerGI_BD_InserterThread>();
964 }
965
966 //#############################################################################################
967
968 class MT_BD_Thread : public JavaTestThread {
969 TestTable::BulkDeleteTask* _bd;
970 public:
MT_BD_Thread(Semaphore * post,TestTable::BulkDeleteTask * bd)971 MT_BD_Thread(Semaphore* post, TestTable::BulkDeleteTask* bd)
972 : JavaTestThread(post), _bd(bd){}
~MT_BD_Thread()973 virtual ~MT_BD_Thread() {}
main_run()974 void main_run() {
975 MyDel del;
976 while(_bd->do_task(this, *this, del));
977 }
978
operator ()(uintptr_t * val)979 bool operator()(uintptr_t* val) {
980 return true;
981 }
982
983 struct MyDel {
operator ()MT_BD_Thread::MyDel984 void operator()(uintptr_t* val) {
985 }
986 };
987 };
988
989 class Driver_BD_Thread : public JavaTestThread {
990 public:
991 Semaphore _done;
Driver_BD_Thread(Semaphore * post)992 Driver_BD_Thread(Semaphore* post) : JavaTestThread(post) {
993 };
~Driver_BD_Thread()994 virtual ~Driver_BD_Thread(){}
995
main_run()996 void main_run() {
997 Semaphore done(0);
998 TestTable* cht = new TestTable(16, 16, 2);
999 for (uintptr_t v = 1; v < 99999; v++ ) {
1000 TestLookup tl(v);
1001 EXPECT_TRUE(cht->insert(this, tl, v)) << "Inserting an unique value should work.";
1002 }
1003 TestTable::BulkDeleteTask bdt(cht, true /* mt */ );
1004 EXPECT_TRUE(bdt.prepare(this)) << "Uncontended prepare must work.";
1005
1006 MT_BD_Thread* tt[4];
1007 for (int i = 0; i < 4; i++) {
1008 tt[i] = new MT_BD_Thread(&done, &bdt);
1009 tt[i]->doit();
1010 }
1011
1012 for (uintptr_t v = 1; v < 99999; v++ ) {
1013 TestLookup tl(v);
1014 cht_get_copy(cht, this, tl);
1015 }
1016
1017 for (int i = 0; i < 4; i++) {
1018 done.wait();
1019 }
1020
1021 bdt.done(this);
1022
1023 cht->do_scan(this, *this);
1024 }
1025
operator ()(uintptr_t * val)1026 bool operator()(uintptr_t* val) {
1027 EXPECT_TRUE(false) << "No items should left";
1028 return true;
1029 }
1030 };
1031
TEST_VM(ConcurrentHashTable,concurrent_mt_bulk_delete)1032 TEST_VM(ConcurrentHashTable, concurrent_mt_bulk_delete) {
1033 mt_test_doer<Driver_BD_Thread>();
1034 }
1035