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/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 #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 (oopDesc::equals(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   G1SATBCardTableModRefBS::enqueue(existing_value);
 161 
 162   // Existing value found, deduplicate string
 163   java_lang_String::set_value(java_string, typeArrayOop(existing_value));
 164   return true;
 165 }
 166 
 167 void ShenandoahStrDedupTable::clear_claimed() {
 168   _claimed = 0;
 169   _partition_size = size() / (ShenandoahHeap::heap()->max_workers() * 4);
 170   _partition_size = MAX2(_partition_size, size_t(1));
 171 }
 172 
 173 size_t ShenandoahStrDedupTable::claim() {
 174   return (size_t)Atomic::add((jint)_partition_size, (volatile jint*)&_claimed) - _partition_size;
 175 }
 176 
 177 void ShenandoahStrDedupTable::parallel_oops_do(OopClosure* cl) {
 178   assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
 179 
 180   size_t index;
 181   size_t end_index;
 182   do {
 183     index = claim();
 184     end_index = MIN2(index + partition_size(), size());
 185 
 186     for (; index < end_index; index ++) {
 187       ShenandoahStrDedupEntry* volatile p = bucket(index);
 188       while (p != NULL) {
 189         p->do_oop(cl);
 190         p = p->next();
 191       }
 192     }
 193   } while (index < size());
 194 }
 195 
 196 void ShenandoahStrDedupTable::oops_do_slow(OopClosure* cl) {
 197   assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
 198   for (size_t index = 0; index < size(); index ++) {
 199     ShenandoahStrDedupEntry* volatile p = bucket(index);
 200     while (p != NULL) {
 201       p->do_oop(cl);
 202       p = p->next();
 203     }
 204   }
 205 }
 206 
 207 ShenandoahStrDedupEntry* ShenandoahStrDedupTable::allocate_entry(typeArrayOop value, unsigned int hash) {
 208   ShenandoahStrDedupEntry* entry = new ShenandoahStrDedupEntry();
 209   entry->set_hash(hash);
 210   entry->set_obj(value);
 211   return entry;
 212 }
 213 
 214 void ShenandoahStrDedupTable::release_entry(ShenandoahStrDedupEntry* entry) {
 215   assert(entry != NULL, "null entry");
 216   delete entry;
 217 }
 218 
 219 unsigned int ShenandoahStrDedupTable::hash_code(oop java_string, typeArrayOop value) {
 220   if (use_java_hash()) {
 221     unsigned int hash = java_lang_String::hash(java_string);
 222     if (hash == 0) {
 223       hash = java_hash_code(value);
 224       java_lang_String::set_hash(java_string, hash);
 225     }
 226     return hash;
 227   } else {
 228     return alt_hash_code(value);
 229   }
 230 }
 231 
 232 unsigned int ShenandoahStrDedupTable::java_hash_code(typeArrayOop value) {
 233   assert(use_java_hash(), "Must use java hash code");
 234   int length = value->length();
 235   const jchar* data = (jchar*)value->base(T_CHAR);
 236   return java_lang_String::hash_code(data, length);
 237 }
 238 
 239 unsigned int ShenandoahStrDedupTable::alt_hash_code(typeArrayOop value) {
 240   assert(hash_seed() != 0, "Must have hash seed");
 241   int length = value->length();
 242   const jchar* data = (jchar*)value->base(T_CHAR);
 243   return AltHashing::murmur3_32(hash_seed(), data, length);
 244 }
 245 
 246 void ShenandoahStrDedupTable::print_statistics(outputStream* out) const {
 247   out->print_cr("ShenandoahStrDedupTable: buckets: " SIZE_FORMAT " entries: " SIZE_FORMAT,
 248     size(), _entries);
 249 }
 250 
 251 #ifdef ASSERT
 252 void ShenandoahStrDedupTable::verify() {
 253   assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
 254   assert(Thread::current() == VMThread::vm_thread(), "only by vm thread");
 255   ShenandoahHeap* heap = ShenandoahHeap::heap();
 256 
 257   size_t num_entries = 0;
 258 
 259   for (size_t index = 0; index < size(); index ++) {
 260     ShenandoahStrDedupEntry* volatile head = bucket(index);
 261     while (head != NULL) {
 262       assert(heap->marking_context()->is_marked(head->obj()), "Must be marked");
 263 
 264       if (use_java_hash()) {
 265         assert(head->hash() == java_hash_code(head->obj()), "Wrong hash code");
 266       } else {
 267         assert(head->hash() == alt_hash_code(head->obj()), "Wrong alt hash code");
 268       }
 269 
 270       assert(index == hash_to_index(head->hash()), "Wrong bucket");
 271       num_entries ++;
 272       head = head->next();
 273     }
 274   }
 275   assert(num_entries == _entries, "The number of entries does not match");
 276 }
 277 
 278 #endif
 279 
 280 ShenandoahStrDedupTableCleanupTask::ShenandoahStrDedupTableCleanupTask() :
 281         _mark_context(ShenandoahHeap::heap()->marking_context()) {
 282 }
 283 
 284 bool ShenandoahStrDedupTableCleanupTask::is_alive(oop obj) const {
 285   return _mark_context->is_marked(obj);
 286 }
 287 
 288 ShenandoahStrDedupTableUnlinkTask::ShenandoahStrDedupTableUnlinkTask(ShenandoahStrDedupTable* const table) :
 289   _table(table) {
 290   log_debug(gc, stringdedup)("Cleanup StringDedup table");
 291   table->clear_claimed();
 292 }
 293 
 294 void ShenandoahStrDedupTableUnlinkTask::do_parallel_cleanup() {
 295   ShenandoahStrDedupTable* const table = _table;
 296   size_t partition = table->partition_size();
 297   size_t removed = 0;
 298   size_t table_end = table->size();
 299 
 300   size_t index;
 301   size_t end_index;
 302   do {
 303     index = table->claim();
 304     end_index = MIN2(index + partition, table_end);
 305     for (; index < end_index; index ++) {
 306       ShenandoahStrDedupEntry* volatile* head_addr = table->bucket_addr(index);
 307       ShenandoahStrDedupEntry* volatile head;
 308       while (*head_addr != NULL) {
 309         head = *head_addr;
 310         if (!is_alive(head->obj())) {
 311           *head_addr = head->next();
 312           table->release_entry(head);
 313           removed ++;
 314         } else {
 315           head_addr = head->next_addr();
 316         }
 317       }
 318     }
 319   } while (index < table_end);
 320 
 321   Atomic::add(-((jlong)removed), (volatile jlong*)&table->_entries);
 322 }
 323 
 324 ShenandoahStrDedupTableRemapTask::ShenandoahStrDedupTableRemapTask(ShenandoahStrDedupTable* const src,
 325                                                                    ShenandoahStrDedupTable* const dest) :
 326   _src_table(src), _dest_table(dest) {
 327   src->clear_claimed();
 328 }
 329 
 330 ShenandoahStrDedupTableRehashTask::ShenandoahStrDedupTableRehashTask(
 331   ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
 332   ShenandoahStrDedupTableRemapTask(src, dest) {
 333   log_debug(gc, stringdedup)("Rehash StringDedup table");
 334 }
 335 
 336 void ShenandoahStrDedupTableRehashTask::do_parallel_cleanup() {
 337   size_t partition = src_table()->partition_size();
 338 
 339   size_t added = 0;
 340   size_t table_end = src_table()->size();
 341   size_t index;
 342   size_t end_index;
 343   do {
 344     index = src_table()->claim();
 345     end_index = MIN2(index + partition, table_end);
 346     for (; index < end_index; index ++) {
 347       ShenandoahStrDedupEntry* volatile * head_addr = src_table()->bucket_addr(index);
 348       ShenandoahStrDedupEntry* volatile head = *head_addr;
 349       *head_addr = NULL;
 350 
 351       ShenandoahStrDedupEntry* tmp;
 352       while(head != NULL) {
 353         tmp = head;
 354         head = head->next();
 355         tmp->set_next(NULL);
 356         if (is_alive(tmp->obj())) {
 357           dest_table()->add(tmp);
 358           added ++;
 359         } else {
 360           src_table()->release_entry(tmp);
 361         }
 362       }
 363     }
 364   } while (index < table_end);
 365 
 366   Atomic::add((jlong)added, (volatile jlong*)&dest_table()->_entries);
 367 }
 368 
 369 ShenandoahStrDedupShrinkTableTask::ShenandoahStrDedupShrinkTableTask(
 370   ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
 371   ShenandoahStrDedupTableRemapTask(src, dest) {
 372   assert(is_power_of_2(src->size()), "Source table size must be a power of 2");
 373   assert(is_power_of_2(dest->size()), "Destination table size must be a power of 2");
 374   assert(src->size() / dest->size() == 2, "Shrink in half");
 375   log_debug(gc, stringdedup)("Shrink StringDedup table");
 376 }
 377 
 378 void ShenandoahStrDedupShrinkTableTask::do_parallel_cleanup() {
 379   size_t partition = src_table()->partition_size();
 380   size_t transferred = 0;
 381 
 382   size_t half_size = src_table()->size() / 2;
 383   // Only scan first half of table.
 384   // To shrink the table in half, we merge buckets at index and (index + half_size)
 385   size_t table_end = src_table()->size() / 2;
 386 
 387   size_t index;
 388   size_t end_index;
 389   do {
 390     index = src_table()->claim();
 391     end_index = MIN2(index + partition, table_end);
 392     for (; index < end_index; index ++) {
 393       ShenandoahStrDedupEntry* volatile * src_head_addr = src_table()->bucket_addr(index);
 394       ShenandoahStrDedupEntry* volatile * dest_head_addr = dest_table()->bucket_addr(index);
 395       ShenandoahStrDedupEntry* volatile   src_head = *src_head_addr;
 396       *src_head_addr = NULL;
 397       // transfer entries at index
 398       transferred += transfer_bucket(src_head, dest_head_addr);
 399 
 400       // transfer entries at index + half_size
 401       src_head_addr = src_table()->bucket_addr(index + half_size);
 402       src_head = *src_head_addr;
 403       *src_head_addr = NULL;
 404       transferred += transfer_bucket(src_head, dest_head_addr);
 405     }
 406   } while (index < table_end);
 407 
 408   Atomic::add((jlong)transferred, (volatile jlong*)&dest_table()->_entries);
 409 }
 410 
 411 size_t ShenandoahStrDedupShrinkTableTask::transfer_bucket(ShenandoahStrDedupEntry* volatile src,
 412   ShenandoahStrDedupEntry* volatile * dest) {
 413   ShenandoahStrDedupEntry* tmp;
 414   size_t transferred = 0;
 415 
 416   while (src != NULL) {
 417     tmp = src;
 418     src = src->next();
 419     tmp->set_next(NULL);
 420     if (is_alive(tmp->obj())) {
 421       if (*dest != NULL) {
 422         tmp->set_next(*dest);
 423       }
 424       *dest = tmp;
 425       transferred ++;
 426     } else {
 427       src_table()->release_entry(tmp);
 428     }
 429   }
 430 
 431   return transferred;
 432 }
 433 
 434 ShenandoahStrDedupExpandTableTask::ShenandoahStrDedupExpandTableTask(
 435   ShenandoahStrDedupTable* const src, ShenandoahStrDedupTable* const dest) :
 436   ShenandoahStrDedupTableRemapTask(src, dest) {
 437   assert(is_power_of_2(src->size()), "Source table size must be a power of 2");
 438   assert(is_power_of_2(dest->size()), "Destination table size must be a power of 2");
 439   assert(dest->size() == 2 * src->size(), "Double the size");
 440 
 441   log_debug(gc, stringdedup)("Expand StringDedup table");
 442 
 443   int n = exact_log2_long(src->size());
 444   _bit_mask = nth_bit(n);
 445 }
 446 
 447 void ShenandoahStrDedupExpandTableTask::do_parallel_cleanup() {
 448   size_t partition = src_table()->partition_size();
 449   size_t table_end = src_table()->size();
 450 
 451   size_t transferred = 0;
 452   size_t index;
 453   size_t end_index;
 454   do {
 455     index = src_table()->claim();
 456     end_index = MIN2(index + partition, table_end);
 457     for (; index < end_index; index ++) {
 458       // split current source bucket into bucket[index] and bucket[index + half_size]
 459       // in destination table
 460       ShenandoahStrDedupEntry* volatile * src_head_addr = src_table()->bucket_addr(index);
 461       ShenandoahStrDedupEntry* volatile   src_head = *src_head_addr;
 462       ShenandoahStrDedupEntry* volatile * dest_low_addr =  dest_table()->bucket_addr(index);
 463       ShenandoahStrDedupEntry* volatile * dest_high_addr = dest_table()->bucket_addr(index + src_table()->size());
 464       *src_head_addr = NULL;
 465 
 466       transferred += split_bucket(src_head, dest_low_addr, dest_high_addr);
 467     }
 468   } while (index < table_end);
 469   Atomic::add((jlong)transferred, (volatile jlong*)&dest_table()->_entries);
 470 }
 471 
 472 size_t ShenandoahStrDedupExpandTableTask::split_bucket(ShenandoahStrDedupEntry* volatile src,
 473     ShenandoahStrDedupEntry* volatile * dest_low,
 474     ShenandoahStrDedupEntry* volatile * dest_high) {
 475   size_t transferred = 0;
 476 
 477   ShenandoahStrDedupEntry* volatile tmp;
 478   ShenandoahStrDedupEntry* volatile * target;
 479   while (src != NULL) {
 480     tmp = src;
 481     src = src->next();
 482 
 483     if (is_alive(tmp->obj())) {
 484       tmp->set_next(NULL);
 485       unsigned int hash = tmp->hash();
 486       if ((hash & _bit_mask) == 0) {
 487         target = dest_low;
 488       } else {
 489         target = dest_high;
 490       }
 491 
 492       if (*target != NULL) {
 493         tmp->set_next(*target);
 494       }
 495 
 496       *target = tmp;
 497       transferred ++;
 498     } else {
 499       src_table()->release_entry(tmp);
 500     }
 501   }
 502   return transferred;
 503 }