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 }