1 /*
2 * Copyright (c) 2017, 2018, Red Hat, Inc. and/or its affiliates.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 *
22 */
23
24 #include "precompiled.hpp"
25
26 #include "classfile/altHashing.hpp"
27 #include "classfile/javaClasses.hpp"
28 #include "gc_implementation/g1/g1SATBCardTableModRefBS.hpp"
29 #include "gc_implementation/shenandoah/shenandoahHeap.inline.hpp"
30 #include "gc_implementation/shenandoah/shenandoahLogging.hpp"
31 #include "gc_implementation/shenandoah/shenandoahStrDedupTable.hpp"
32 #include "memory/allocation.hpp"
33 #include "runtime/atomic.hpp"
34 #include "runtime/safepoint.hpp"
35
36
37 const size_t ShenandoahStrDedupTable::_min_size = (1 << 10); // 1024
38 const size_t ShenandoahStrDedupTable::_max_size = (1 << 24); // 16777216
39 const double ShenandoahStrDedupTable::_grow_load_factor = 2.0; // Grow table at 200% load
40 const double ShenandoahStrDedupTable::_shrink_load_factor = _grow_load_factor / 3.0; // Shrink table at 67% load
41 const double ShenandoahStrDedupTable::_max_cache_factor = 0.1; // Cache a maximum of 10% of the table size
42 const uintx ShenandoahStrDedupTable::_rehash_multiple = 60; // Hash bucket has 60 times more collisions than expected
43 const uintx ShenandoahStrDedupTable::_rehash_threshold = (uintx)(_rehash_multiple * _grow_load_factor);
44
45
46 bool ShenandoahStrDedupEntry::cas_set_next(ShenandoahStrDedupEntry* next) {
47 return Atomic::cmpxchg_ptr(next, &_next, (ShenandoahStrDedupEntry*)NULL) == NULL;
48 }
49
50 ShenandoahStrDedupTable::ShenandoahStrDedupTable(size_t size, jint hash_seed) :
51 _size(size), _hash_seed(hash_seed), _entries(0), _claimed(0), _partition_size(0),
52 _rehash_needed(false), _shrink_threshold((uintx)(size * _shrink_load_factor)),
53 _grow_threshold((uintx)(size * _grow_load_factor))
54 {
55 assert(size >= _min_size && size <= _max_size, "Invalid table size");
56 _buckets = NEW_C_HEAP_ARRAY(ShenandoahStrDedupEntry* volatile, size, mtGC);
57 for (size_t index = 0; index < size; index ++) {
58 _buckets[index] = NULL;
59 }
60 }
61
62 ShenandoahStrDedupTable::~ShenandoahStrDedupTable() {
63 for (size_t index = 0; index < size(); index ++) {
64 ShenandoahStrDedupEntry* volatile head = bucket(index);
65 ShenandoahStrDedupEntry* volatile tmp;
66 while (head != NULL) {
67 tmp = head;
68 head = head->next();
69 release_entry(tmp);
70 }
71 }
72 }
73
74 typeArrayOop ShenandoahStrDedupTable::lookup_or_add(typeArrayOop value, unsigned int hash, uintx& count) {
75 ShenandoahStrDedupEntry* volatile* head_addr = bucket_addr(hash_to_index(hash));
76 count = 0;
77 ShenandoahStrDedupEntry* new_entry = NULL;
78 if (*head_addr == NULL) {
79 new_entry = allocate_entry(value, hash);
80 if (Atomic::cmpxchg_ptr(new_entry, head_addr, (ShenandoahStrDedupEntry*)NULL) == NULL) {
81 Atomic::inc((volatile jint*)&_entries);
82 return value;
83 }
84 }
85
86 ShenandoahStrDedupEntry* volatile head = *head_addr;
87 assert(head != NULL, "Should not be null");
88
89 while (head != NULL) {
90 if (head->equals(value, hash)) {
91 if (new_entry != NULL) release_entry(new_entry);
92 return head->obj();
93 } else if (head->next() == NULL) {
94 if (new_entry == NULL) new_entry = allocate_entry(value, hash);
95 if (head->cas_set_next(new_entry)) {
96 Atomic::inc((volatile jint*)&_entries);
97 return value;
98 }
99 }
100
101 count ++;
102 head = head->next();
103 assert(head != NULL, "Should not be null");
104 }
105
106 // Should have found existing one or added new one
107 ShouldNotReachHere();
108 return NULL;
109 }
110
111 void ShenandoahStrDedupTable::add(ShenandoahStrDedupEntry* entry) {
112 assert(SafepointSynchronize::is_at_safepoint(), "Only at a safepoint");
113 assert(!use_java_hash(), "Only used when rehashing the table");
114 unsigned int hash = alt_hash_code(entry->obj());
115 entry->set_hash(hash);
116
117 ShenandoahStrDedupEntry* volatile* head_addr = bucket_addr(hash_to_index(hash));
118 if (*head_addr == NULL) {
119 if (Atomic::cmpxchg_ptr(entry, head_addr, (ShenandoahStrDedupEntry*)NULL) == NULL) {
120 return;
121 }
122 }
123
124 ShenandoahStrDedupEntry* volatile head = *head_addr;
125 assert(head != NULL, "Should not be null");
126
127 while (head != NULL) {
128 if (head->next() == NULL && (head->cas_set_next(entry))) {
129 return;
130 }
131
132 head = head->next();
133 // Some one beats us
134 assert(head != NULL, "Should not be null");
135 }
136 }
137
138 bool ShenandoahStrDedupTable::deduplicate(oop java_string) {
139 assert(java_lang_String::is_instance(java_string), "Must be a string");
140
141 typeArrayOop value = java_lang_String::value(java_string);
142 if (value == NULL) {
143 return false;
144 }
145
146 unsigned int hash = hash_code(java_string, value);
147
148 uintx count = 0;
149 typeArrayOop existing_value = lookup_or_add(value, hash, count);
150 assert(existing_value != NULL, "Must have found or added");
151 if (count > _rehash_threshold) {
152 _rehash_needed = true;
153 }
154
155 if (oopDesc::equals(existing_value, value)) {
156 return false;
157 }
158
159 // Enqueue the reference to make sure it is kept alive. Concurrent mark might
160 // otherwise declare it dead if there are no other strong references to this object.
161 G1SATBCardTableModRefBS::enqueue(existing_value);
162
163 // Existing value found, deduplicate string
164 java_lang_String::set_value(java_string, typeArrayOop(existing_value));
165 return true;
166 }
167
168
169 void ShenandoahStrDedupTable::clear_claimed() {
170 _claimed = 0;
171 _partition_size = size() / (ShenandoahHeap::heap()->max_workers() * 4);
172 _partition_size = MAX2(_partition_size, size_t(1));
173 }
174
175 size_t ShenandoahStrDedupTable::claim() {
176 return (size_t)Atomic::add((jint)_partition_size, (volatile jint*)&_claimed) - _partition_size;
177 }
178
179 void ShenandoahStrDedupTable::parallel_oops_do(OopClosure* cl) {
180 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
181
182 size_t index;
183 size_t end_index;
184 do {
185 index = claim();
186 end_index = MIN2(index + partition_size(), size());
187
188 for (; index < end_index; index ++) {
189 ShenandoahStrDedupEntry* volatile p = bucket(index);
190 while (p != NULL) {
191 p->do_oop(cl);
192 p = p->next();
193 }
194 }
195 } while (index < size());
196 }
197
198 void ShenandoahStrDedupTable::oops_do_slow(OopClosure* cl) {
199 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
200 for (size_t index = 0; index < size(); index ++) {
201 ShenandoahStrDedupEntry* volatile p = bucket(index);
202 while (p != NULL) {
203 p->do_oop(cl);
204 p = p->next();
205 }
206 }
207 }
208
209 ShenandoahStrDedupEntry* ShenandoahStrDedupTable::allocate_entry(typeArrayOop value, unsigned int hash) {
210 ShenandoahStrDedupEntry* entry = new ShenandoahStrDedupEntry();
211 entry->set_hash(hash);
212 entry->set_obj(value);
213 return entry;
214 }
215
216 void ShenandoahStrDedupTable::release_entry(ShenandoahStrDedupEntry* entry) {
217 assert(entry != NULL, "null entry");
218 delete entry;
219 }
220
221 unsigned int ShenandoahStrDedupTable::hash_code(oop java_string, typeArrayOop value) {
222 if (use_java_hash()) {
223 unsigned int hash = java_lang_String::hash(java_string);
224 if (hash == 0) {
225 hash = java_hash_code(value);
226 java_lang_String::set_hash(java_string, hash);
227 }
228 return hash;
229 } else {
230 return alt_hash_code(value);
231 }
232 }
233
234 unsigned int ShenandoahStrDedupTable::java_hash_code(typeArrayOop value) {
235 assert(use_java_hash(), "Must use java hash code");
236 int length = value->length();
237 const jchar* data = (jchar*)value->base(T_CHAR);
238 return java_lang_String::hash_code(data, length);
239 }
240
241 unsigned int ShenandoahStrDedupTable::alt_hash_code(typeArrayOop value) {
242 assert(hash_seed() != 0, "Must have hash seed");
243 int length = value->length();
244 const jchar* data = (jchar*)value->base(T_CHAR);
245 return AltHashing::murmur3_32(hash_seed(), data, length);
246 }
247
248 void ShenandoahStrDedupTable::print_statistics(outputStream* out) const {
249 out->print_cr("ShenandoahStrDedupTable: buckets: " SIZE_FORMAT " entries: " SIZE_FORMAT,
250 size(), _entries);
251 }
252
253 #ifdef ASSERT
254 void ShenandoahStrDedupTable::verify() {
255 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
256 assert(Thread::current() == VMThread::vm_thread(), "only by vm thread");
257 ShenandoahHeap* heap = ShenandoahHeap::heap();
258
259 size_t num_entries = 0;
260
261 for (size_t index = 0; index < size(); index ++) {
262 ShenandoahStrDedupEntry* volatile head = bucket(index);
263 while (head != NULL) {
264 assert(heap->next_marking_context()->is_marked(head->obj()), "Must be marked");
265
266 if (use_java_hash()) {
267 assert(head->hash() == java_hash_code(head->obj()), "Wrong hash code");
268 } else {
269 assert(head->hash() == alt_hash_code(head->obj()), "Wrong alt hash code");
270 }
271
272 assert(index == hash_to_index(head->hash()), "Wrong bucket");
273 num_entries ++;
274 head = head->next();
275 }
276 }
277 assert(num_entries == _entries, "The number of entries does not match");
278 }
279
280 #endif
281
282 ShenandoahStrDedupTableCleanupTask::ShenandoahStrDedupTableCleanupTask() :
283 _mark_context(ShenandoahHeap::heap()->next_marking_context()) {
284 }
285
286 bool ShenandoahStrDedupTableCleanupTask::is_alive(oop obj) const {
287 return _mark_context->is_marked(obj);
288 }
289
290 ShenandoahStrDedupTableUnlinkTask::ShenandoahStrDedupTableUnlinkTask(ShenandoahStrDedupTable* const table) :
291 _table(table) {
292 log_debug(gc, stringdedup)("Cleanup StringDedup table");
293 table->clear_claimed();
294 }
295
296 void ShenandoahStrDedupTableUnlinkTask::do_parallel_cleanup() {
297 ShenandoahStrDedupTable* const table = _table;
298 size_t partition = table->partition_size();
299 size_t removed = 0;
300 size_t table_end = table->size();
301
302 size_t index;
303 size_t end_index;
304 do {
305 index = table->claim();
306 end_index = MIN2(index + partition, table_end);
307 for (; index < end_index; index ++) {
308 ShenandoahStrDedupEntry* volatile* head_addr = table->bucket_addr(index);
309 ShenandoahStrDedupEntry* volatile head;
310 while (*head_addr != NULL) {
311 head = *head_addr;
312 if (!is_alive(head->obj())) {
313 *head_addr = head->next();
314 table->release_entry(head);
315 removed ++;
316 } else {
317 head_addr = head->next_addr();
318 }
319 }
320 }
321 } while (index < table_end);
322
323 Atomic::add(-((jlong)removed), (volatile jlong*)&table->_entries);
324 }
325
326 ShenandoahStrDedupTableRemapTask::ShenandoahStrDedupTableRemapTask(ShenandoahStrDedupTable* const src,
327 ShenandoahStrDedupTable* const dest) :
328 _src_table(src), _dest_table(dest) {
329 src->clear_claimed();
330 }
331
332 ShenandoahStrDedupTableRehashTask::ShenandoahStrDedupTableRehashTask(
333 ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
334 ShenandoahStrDedupTableRemapTask(src, dest) {
335 log_debug(gc, stringdedup)("Rehash StringDedup table");
336 }
337
338 void ShenandoahStrDedupTableRehashTask::do_parallel_cleanup() {
339 size_t partition = src_table()->partition_size();
340
341 size_t added = 0;
342 size_t table_end = src_table()->size();
343 size_t index;
344 size_t end_index;
345 do {
346 index = src_table()->claim();
347 end_index = MIN2(index + partition, table_end);
348 for (; index < end_index; index ++) {
349 ShenandoahStrDedupEntry* volatile * head_addr = src_table()->bucket_addr(index);
350 ShenandoahStrDedupEntry* volatile head = *head_addr;
351 *head_addr = NULL;
352
353 ShenandoahStrDedupEntry* tmp;
354 while(head != NULL) {
355 tmp = head;
356 head = head->next();
357 tmp->set_next(NULL);
358 if (is_alive(tmp->obj())) {
359 dest_table()->add(tmp);
360 added ++;
361 } else {
362 src_table()->release_entry(tmp);
363 }
364 }
365 }
366 } while (index < table_end);
367
368 Atomic::add((jlong)added, (volatile jlong*)&dest_table()->_entries);
369 }
370
371
372 ShenandoahStrDedupShrinkTableTask::ShenandoahStrDedupShrinkTableTask(
373 ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
374 ShenandoahStrDedupTableRemapTask(src, dest) {
375 assert(is_power_of_2(src->size()), "Source table size must be a power of 2");
376 assert(is_power_of_2(dest->size()), "Destination table size must be a power of 2");
377 assert(src->size() / dest->size() == 2, "Shrink in half");
378 log_debug(gc, stringdedup)("Shrink StringDedup table");
379 }
380
381 void ShenandoahStrDedupShrinkTableTask::do_parallel_cleanup() {
382 size_t partition = src_table()->partition_size();
383 size_t transferred = 0;
384
385 size_t half_size = src_table()->size() / 2;
386 // Only scan first half of table.
387 // To shrink the table in half, we merge buckets at index and (index + half_size)
388 size_t table_end = src_table()->size() / 2;
389
390 size_t index;
391 size_t end_index;
392 do {
393 index = src_table()->claim();
394 end_index = MIN2(index + partition, table_end);
395 for (; index < end_index; index ++) {
396 ShenandoahStrDedupEntry* volatile * src_head_addr = src_table()->bucket_addr(index);
397 ShenandoahStrDedupEntry* volatile * dest_head_addr = dest_table()->bucket_addr(index);
398 ShenandoahStrDedupEntry* volatile src_head = *src_head_addr;
399 *src_head_addr = NULL;
400 // transfer entries at index
401 transferred += transfer_bucket(src_head, dest_head_addr);
402
403 // transfer entries at index + half_size
404 src_head_addr = src_table()->bucket_addr(index + half_size);
405 src_head = *src_head_addr;
406 *src_head_addr = NULL;
407 transferred += transfer_bucket(src_head, dest_head_addr);
408 }
409 } while (index < table_end);
410
411 Atomic::add((jlong)transferred, (volatile jlong*)&dest_table()->_entries);
412 }
413
414
415 size_t ShenandoahStrDedupShrinkTableTask::transfer_bucket(ShenandoahStrDedupEntry* volatile src,
416 ShenandoahStrDedupEntry* volatile * dest) {
417 ShenandoahStrDedupEntry* tmp;
418 size_t transferred = 0;
419
420 while (src != NULL) {
421 tmp = src;
422 src = src->next();
423 tmp->set_next(NULL);
424 if (is_alive(tmp->obj())) {
425 if (*dest != NULL) {
426 tmp->set_next(*dest);
427 }
428 *dest = tmp;
429 transferred ++;
430 } else {
431 src_table()->release_entry(tmp);
432 }
433 }
434
435 return transferred;
436 }
437
438 ShenandoahStrDedupExpandTableTask::ShenandoahStrDedupExpandTableTask(
439 ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
440 ShenandoahStrDedupTableRemapTask(src, dest) {
441 assert(is_power_of_2(src->size()), "Source table size must be a power of 2");
442 assert(is_power_of_2(dest->size()), "Destination table size must be a power of 2");
443 assert(dest->size() == 2 * src->size(), "Double the size");
444
445 log_debug(gc, stringdedup)("Expand StringDedup table");
446
447 int n = exact_log2_long(src->size());
448 _bit_mask = nth_bit(n);
449 }
450
451 void ShenandoahStrDedupExpandTableTask::do_parallel_cleanup() {
452 size_t partition = src_table()->partition_size();
453 size_t table_end = src_table()->size();
454
455 size_t transferred = 0;
456 size_t index;
457 size_t end_index;
458 do {
459 index = src_table()->claim();
460 end_index = MIN2(index + partition, table_end);
461 for (; index < end_index; index ++) {
462 // split current source bucket into bucket[index] and bucket[index + half_size]
463 // in destination table
464 ShenandoahStrDedupEntry* volatile * src_head_addr = src_table()->bucket_addr(index);
465 ShenandoahStrDedupEntry* volatile src_head = *src_head_addr;
466 ShenandoahStrDedupEntry* volatile * dest_low_addr = dest_table()->bucket_addr(index);
467 ShenandoahStrDedupEntry* volatile * dest_high_addr = dest_table()->bucket_addr(index + src_table()->size());
468 *src_head_addr = NULL;
469
470 transferred += split_bucket(src_head, dest_low_addr, dest_high_addr);
471 }
472 } while (index < table_end);
473 Atomic::add((jlong)transferred, (volatile jlong*)&dest_table()->_entries);
474 }
475
476 size_t ShenandoahStrDedupExpandTableTask::split_bucket(ShenandoahStrDedupEntry* volatile src,
477 ShenandoahStrDedupEntry* volatile * dest_low,
478 ShenandoahStrDedupEntry* volatile * dest_high) {
479 size_t transferred = 0;
480
481 ShenandoahStrDedupEntry* volatile tmp;
482 ShenandoahStrDedupEntry* volatile * target;
483 while (src != NULL) {
484 tmp = src;
485 src = src->next();
486
487 if (is_alive(tmp->obj())) {
488 tmp->set_next(NULL);
489 unsigned int hash = tmp->hash();
490 if ((hash & _bit_mask) == 0) {
491 target = dest_low;
492 } else {
493 target = dest_high;
494 }
495
496 if (*target != NULL) {
497 tmp->set_next(*target);
498 }
499
500 *target = tmp;
501 transferred ++;
502 } else {
503 src_table()->release_entry(tmp);
504 }
505 }
506 return transferred;
507 }