1 /*
2 * Copyright (c) 2017, 2018, Red Hat, Inc. All rights reserved.
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/shenandoah/shenandoahBarrierSet.inline.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 #include "runtime/vmThread.hpp"
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 bool ShenandoahStrDedupEntry::cas_set_next(ShenandoahStrDedupEntry* next) {
46 return Atomic::cmpxchg_ptr(next, &_next, (ShenandoahStrDedupEntry*)NULL) == NULL;
47 }
48
49 ShenandoahStrDedupTable::ShenandoahStrDedupTable(size_t size, jint hash_seed) :
50 _size(size), _hash_seed(hash_seed), _entries(0), _claimed(0), _partition_size(0),
51 _rehash_needed(false), _shrink_threshold((uintx)(size * _shrink_load_factor)),
52 _grow_threshold((uintx)(size * _grow_load_factor))
53 {
54 assert(size >= _min_size && size <= _max_size, "Invalid table size");
55 _buckets = NEW_C_HEAP_ARRAY(ShenandoahStrDedupEntry* volatile, size, mtGC);
56 for (size_t index = 0; index < size; index ++) {
57 _buckets[index] = NULL;
58 }
59 }
60
61 ShenandoahStrDedupTable::~ShenandoahStrDedupTable() {
62 for (size_t index = 0; index < size(); index ++) {
63 ShenandoahStrDedupEntry* volatile head = bucket(index);
64 ShenandoahStrDedupEntry* volatile tmp;
65 while (head != NULL) {
66 tmp = head;
67 head = head->next();
68 release_entry(tmp);
69 }
70 }
71 }
72
73 typeArrayOop ShenandoahStrDedupTable::lookup_or_add(typeArrayOop value, unsigned int hash, uintx& count) {
74 ShenandoahStrDedupEntry* volatile* head_addr = bucket_addr(hash_to_index(hash));
75 count = 0;
76 ShenandoahStrDedupEntry* new_entry = NULL;
77 if (*head_addr == NULL) {
78 new_entry = allocate_entry(value, hash);
79 if (Atomic::cmpxchg_ptr(new_entry, head_addr, (ShenandoahStrDedupEntry*)NULL) == NULL) {
80 Atomic::inc((volatile jint*)&_entries);
81 return value;
82 }
83 }
84
85 ShenandoahStrDedupEntry* volatile head = *head_addr;
86 assert(head != NULL, "Should not be null");
87
88 while (head != NULL) {
89 if (head->equals(value, hash)) {
90 if (new_entry != NULL) release_entry(new_entry);
91 return head->obj();
92 } else if (head->next() == NULL) {
93 if (new_entry == NULL) new_entry = allocate_entry(value, hash);
94 if (head->cas_set_next(new_entry)) {
95 Atomic::inc((volatile jint*)&_entries);
96 return value;
97 }
98 }
99
100 count ++;
101 head = head->next();
102 assert(head != NULL, "Should not be null");
103 }
104
105 // Should have found existing one or added new one
106 ShouldNotReachHere();
107 return NULL;
108 }
109
110 void ShenandoahStrDedupTable::add(ShenandoahStrDedupEntry* entry) {
111 assert(SafepointSynchronize::is_at_safepoint(), "Only at a safepoint");
112 assert(!use_java_hash(), "Only used when rehashing the table");
113 unsigned int hash = alt_hash_code(entry->obj());
114 entry->set_hash(hash);
115
116 ShenandoahStrDedupEntry* volatile* head_addr = bucket_addr(hash_to_index(hash));
117 if (*head_addr == NULL) {
118 if (Atomic::cmpxchg_ptr(entry, head_addr, (ShenandoahStrDedupEntry*)NULL) == NULL) {
119 return;
120 }
121 }
122
123 ShenandoahStrDedupEntry* volatile head = *head_addr;
124 assert(head != NULL, "Should not be null");
125
126 while (head != NULL) {
127 if (head->next() == NULL && (head->cas_set_next(entry))) {
128 return;
129 }
130
131 head = head->next();
132 // Some one beats us
133 assert(head != NULL, "Should not be null");
134 }
135 }
136
137 bool ShenandoahStrDedupTable::deduplicate(oop java_string) {
138 assert(java_lang_String::is_instance(java_string), "Must be a string");
139
140 typeArrayOop value = java_lang_String::value(java_string);
141 if (value == NULL) {
142 return false;
143 }
144
145 unsigned int hash = hash_code(java_string, value);
146
147 uintx count = 0;
148 typeArrayOop existing_value = lookup_or_add(value, hash, count);
149 assert(existing_value != NULL, "Must have found or added");
150 if (count > _rehash_threshold) {
151 _rehash_needed = true;
152 }
153
154 if (existing_value == value) {
155 return false;
156 }
157
158 // Enqueue the reference to make sure it is kept alive. Concurrent mark might
159 // otherwise declare it dead if there are no other strong references to this object.
160 ShenandoahBarrierSet* bs = ShenandoahBarrierSet::barrier_set();
161 bs->keep_alive_barrier(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 void ShenandoahStrDedupTable::clear_claimed() {
169 _claimed = 0;
170 _partition_size = size() / (ShenandoahHeap::heap()->max_workers() * 4);
171 _partition_size = MAX2(_partition_size, size_t(1));
172 }
173
174 size_t ShenandoahStrDedupTable::claim() {
175 return (size_t)Atomic::add((jint)_partition_size, (volatile jint*)&_claimed) - _partition_size;
176 }
177
178 void ShenandoahStrDedupTable::parallel_oops_do(OopClosure* cl) {
179 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
180
181 size_t index;
182 size_t end_index;
183 do {
184 index = claim();
185 end_index = MIN2(index + partition_size(), size());
186
187 for (; index < end_index; index ++) {
188 ShenandoahStrDedupEntry* volatile p = bucket(index);
189 while (p != NULL) {
190 p->do_oop(cl);
191 p = p->next();
192 }
193 }
194 } while (index < size());
195 }
196
197 void ShenandoahStrDedupTable::oops_do_slow(OopClosure* cl) {
198 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
199 for (size_t index = 0; index < size(); index ++) {
200 ShenandoahStrDedupEntry* volatile p = bucket(index);
201 while (p != NULL) {
202 p->do_oop(cl);
203 p = p->next();
204 }
205 }
206 }
207
208 ShenandoahStrDedupEntry* ShenandoahStrDedupTable::allocate_entry(typeArrayOop value, unsigned int hash) {
209 ShenandoahStrDedupEntry* entry = new ShenandoahStrDedupEntry();
210 entry->set_hash(hash);
211 entry->set_obj(value);
212 return entry;
213 }
214
215 void ShenandoahStrDedupTable::release_entry(ShenandoahStrDedupEntry* entry) {
216 assert(entry != NULL, "null entry");
217 delete entry;
218 }
219
220 unsigned int ShenandoahStrDedupTable::hash_code(oop java_string, typeArrayOop value) {
221 if (use_java_hash()) {
222 unsigned int hash = java_lang_String::hash(java_string);
223 if (hash == 0) {
224 hash = java_hash_code(value);
225 java_lang_String::set_hash(java_string, hash);
226 }
227 return hash;
228 } else {
229 return alt_hash_code(value);
230 }
231 }
232
233 unsigned int ShenandoahStrDedupTable::java_hash_code(typeArrayOop value) {
234 assert(use_java_hash(), "Must use java hash code");
235 int length = value->length();
236 const jchar* data = (jchar*)value->base(T_CHAR);
237 return java_lang_String::hash_code(data, length);
238 }
239
240 unsigned int ShenandoahStrDedupTable::alt_hash_code(typeArrayOop value) {
241 assert(hash_seed() != 0, "Must have hash seed");
242 int length = value->length();
243 const jchar* data = (jchar*)value->base(T_CHAR);
244 return AltHashing::halfsiphash_32(hash_seed(), (const uint16_t*)data, length);
245 }
246
247 void ShenandoahStrDedupTable::print_statistics(outputStream* out) const {
248 out->print_cr("ShenandoahStrDedupTable: buckets: " SIZE_FORMAT " entries: " SIZE_FORMAT,
249 size(), _entries);
250 }
251
252 #ifdef ASSERT
253 void ShenandoahStrDedupTable::verify() {
254 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
255 assert(Thread::current() == VMThread::vm_thread(), "only by vm thread");
256 ShenandoahHeap* heap = ShenandoahHeap::heap();
257
258 size_t num_entries = 0;
259
260 for (size_t index = 0; index < size(); index ++) {
261 ShenandoahStrDedupEntry* volatile head = bucket(index);
262 while (head != NULL) {
263 assert(heap->marking_context()->is_marked(head->obj()), "Must be marked");
264
265 if (use_java_hash()) {
266 assert(head->hash() == java_hash_code(head->obj()), "Wrong hash code");
267 } else {
268 assert(head->hash() == alt_hash_code(head->obj()), "Wrong alt hash code");
269 }
270
271 assert(index == hash_to_index(head->hash()), "Wrong bucket");
272 num_entries ++;
273 head = head->next();
274 }
275 }
276 assert(num_entries == _entries, "The number of entries does not match");
277 }
278
279 #endif
280
281 ShenandoahStrDedupTableCleanupTask::ShenandoahStrDedupTableCleanupTask() :
282 _mark_context(ShenandoahHeap::heap()->marking_context()) {
283 }
284
285 bool ShenandoahStrDedupTableCleanupTask::is_alive(oop obj) const {
286 return _mark_context->is_marked(obj);
287 }
288
289 ShenandoahStrDedupTableUnlinkTask::ShenandoahStrDedupTableUnlinkTask(ShenandoahStrDedupTable* const table) :
290 _table(table) {
291 log_debug(gc, stringdedup)("Cleanup StringDedup table");
292 table->clear_claimed();
293 }
294
295 void ShenandoahStrDedupTableUnlinkTask::do_parallel_cleanup() {
296 ShenandoahStrDedupTable* const table = _table;
297 size_t partition = table->partition_size();
298 size_t removed = 0;
299 size_t table_end = table->size();
300
301 size_t index;
302 size_t end_index;
303 do {
304 index = table->claim();
305 end_index = MIN2(index + partition, table_end);
306 for (; index < end_index; index ++) {
307 ShenandoahStrDedupEntry* volatile* head_addr = table->bucket_addr(index);
308 ShenandoahStrDedupEntry* volatile head;
309 while (*head_addr != NULL) {
310 head = *head_addr;
311 if (!is_alive(head->obj())) {
312 *head_addr = head->next();
313 table->release_entry(head);
314 removed ++;
315 } else {
316 head_addr = head->next_addr();
317 }
318 }
319 }
320 } while (index < table_end);
321
322 Atomic::add(-((jlong)removed), (volatile jlong*)&table->_entries);
323 }
324
325 ShenandoahStrDedupTableRemapTask::ShenandoahStrDedupTableRemapTask(ShenandoahStrDedupTable* const src,
326 ShenandoahStrDedupTable* const dest) :
327 _src_table(src), _dest_table(dest) {
328 src->clear_claimed();
329 }
330
331 ShenandoahStrDedupTableRehashTask::ShenandoahStrDedupTableRehashTask(
332 ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
333 ShenandoahStrDedupTableRemapTask(src, dest) {
334 log_debug(gc, stringdedup)("Rehash StringDedup table");
335 }
336
337 void ShenandoahStrDedupTableRehashTask::do_parallel_cleanup() {
338 size_t partition = src_table()->partition_size();
339
340 size_t added = 0;
341 size_t table_end = src_table()->size();
342 size_t index;
343 size_t end_index;
344 do {
345 index = src_table()->claim();
346 end_index = MIN2(index + partition, table_end);
347 for (; index < end_index; index ++) {
348 ShenandoahStrDedupEntry* volatile * head_addr = src_table()->bucket_addr(index);
349 ShenandoahStrDedupEntry* volatile head = *head_addr;
350 *head_addr = NULL;
351
352 ShenandoahStrDedupEntry* tmp;
353 while(head != NULL) {
354 tmp = head;
355 head = head->next();
356 tmp->set_next(NULL);
357 if (is_alive(tmp->obj())) {
358 dest_table()->add(tmp);
359 added ++;
360 } else {
361 src_table()->release_entry(tmp);
362 }
363 }
364 }
365 } while (index < table_end);
366
367 Atomic::add((jlong)added, (volatile jlong*)&dest_table()->_entries);
368 }
369
370 ShenandoahStrDedupShrinkTableTask::ShenandoahStrDedupShrinkTableTask(
371 ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
372 ShenandoahStrDedupTableRemapTask(src, dest) {
373 assert(is_power_of_2(src->size()), "Source table size must be a power of 2");
374 assert(is_power_of_2(dest->size()), "Destination table size must be a power of 2");
375 assert(src->size() / dest->size() == 2, "Shrink in half");
376 log_debug(gc, stringdedup)("Shrink StringDedup table");
377 }
378
379 void ShenandoahStrDedupShrinkTableTask::do_parallel_cleanup() {
380 size_t partition = src_table()->partition_size();
381 size_t transferred = 0;
382
383 size_t half_size = src_table()->size() / 2;
384 // Only scan first half of table.
385 // To shrink the table in half, we merge buckets at index and (index + half_size)
386 size_t table_end = src_table()->size() / 2;
387
388 size_t index;
389 size_t end_index;
390 do {
391 index = src_table()->claim();
392 end_index = MIN2(index + partition, table_end);
393 for (; index < end_index; index ++) {
394 ShenandoahStrDedupEntry* volatile * src_head_addr = src_table()->bucket_addr(index);
395 ShenandoahStrDedupEntry* volatile * dest_head_addr = dest_table()->bucket_addr(index);
396 ShenandoahStrDedupEntry* volatile src_head = *src_head_addr;
397 *src_head_addr = NULL;
398 // transfer entries at index
399 transferred += transfer_bucket(src_head, dest_head_addr);
400
401 // transfer entries at index + half_size
402 src_head_addr = src_table()->bucket_addr(index + half_size);
403 src_head = *src_head_addr;
404 *src_head_addr = NULL;
405 transferred += transfer_bucket(src_head, dest_head_addr);
406 }
407 } while (index < table_end);
408
409 Atomic::add((jlong)transferred, (volatile jlong*)&dest_table()->_entries);
410 }
411
412 size_t ShenandoahStrDedupShrinkTableTask::transfer_bucket(ShenandoahStrDedupEntry* volatile src,
413 ShenandoahStrDedupEntry* volatile * dest) {
414 ShenandoahStrDedupEntry* tmp;
415 size_t transferred = 0;
416
417 while (src != NULL) {
418 tmp = src;
419 src = src->next();
420 tmp->set_next(NULL);
421 if (is_alive(tmp->obj())) {
422 if (*dest != NULL) {
423 tmp->set_next(*dest);
424 }
425 *dest = tmp;
426 transferred ++;
427 } else {
428 src_table()->release_entry(tmp);
429 }
430 }
431
432 return transferred;
433 }
434
435 ShenandoahStrDedupExpandTableTask::ShenandoahStrDedupExpandTableTask(
436 ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
437 ShenandoahStrDedupTableRemapTask(src, dest) {
438 assert(is_power_of_2(src->size()), "Source table size must be a power of 2");
439 assert(is_power_of_2(dest->size()), "Destination table size must be a power of 2");
440 assert(dest->size() == 2 * src->size(), "Double the size");
441
442 log_debug(gc, stringdedup)("Expand StringDedup table");
443
444 int n = exact_log2_long(src->size());
445 _bit_mask = nth_bit(n);
446 }
447
448 void ShenandoahStrDedupExpandTableTask::do_parallel_cleanup() {
449 size_t partition = src_table()->partition_size();
450 size_t table_end = src_table()->size();
451
452 size_t transferred = 0;
453 size_t index;
454 size_t end_index;
455 do {
456 index = src_table()->claim();
457 end_index = MIN2(index + partition, table_end);
458 for (; index < end_index; index ++) {
459 // split current source bucket into bucket[index] and bucket[index + half_size]
460 // in destination table
461 ShenandoahStrDedupEntry* volatile * src_head_addr = src_table()->bucket_addr(index);
462 ShenandoahStrDedupEntry* volatile src_head = *src_head_addr;
463 ShenandoahStrDedupEntry* volatile * dest_low_addr = dest_table()->bucket_addr(index);
464 ShenandoahStrDedupEntry* volatile * dest_high_addr = dest_table()->bucket_addr(index + src_table()->size());
465 *src_head_addr = NULL;
466
467 transferred += split_bucket(src_head, dest_low_addr, dest_high_addr);
468 }
469 } while (index < table_end);
470 Atomic::add((jlong)transferred, (volatile jlong*)&dest_table()->_entries);
471 }
472
473 size_t ShenandoahStrDedupExpandTableTask::split_bucket(ShenandoahStrDedupEntry* volatile src,
474 ShenandoahStrDedupEntry* volatile * dest_low,
475 ShenandoahStrDedupEntry* volatile * dest_high) {
476 size_t transferred = 0;
477
478 ShenandoahStrDedupEntry* volatile tmp;
479 ShenandoahStrDedupEntry* volatile * target;
480 while (src != NULL) {
481 tmp = src;
482 src = src->next();
483
484 if (is_alive(tmp->obj())) {
485 tmp->set_next(NULL);
486 unsigned int hash = tmp->hash();
487 if ((hash & _bit_mask) == 0) {
488 target = dest_low;
489 } else {
490 target = dest_high;
491 }
492
493 if (*target != NULL) {
494 tmp->set_next(*target);
495 }
496
497 *target = tmp;
498 transferred ++;
499 } else {
500 src_table()->release_entry(tmp);
501 }
502 }
503 return transferred;
504 }