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 }