1 /*
   2  * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "classfile/altHashing.hpp"
  27 #include "classfile/compactHashtable.hpp"
  28 #include "classfile/javaClasses.hpp"
  29 #include "classfile/symbolTable.hpp"
  30 #include "memory/allocation.inline.hpp"
  31 #include "memory/metaspaceClosure.hpp"
  32 #include "memory/metaspaceShared.hpp"
  33 #include "memory/resourceArea.hpp"
  34 #include "oops/oop.inline.hpp"
  35 #include "runtime/atomic.hpp"
  36 #include "runtime/interfaceSupport.inline.hpp"
  37 #include "runtime/timerTrace.hpp"
  38 #include "services/diagnosticCommand.hpp"
  39 #include "utilities/concurrentHashTable.inline.hpp"
  40 #include "utilities/concurrentHashTableTasks.inline.hpp"
  41 #include "utilities/utf8.hpp"
  42 
  43 // We used to not resize at all, so let's be conservative
  44 // and not set it too short before we decide to resize,
  45 // to match previous startup behavior
  46 const double PREF_AVG_LIST_LEN = 8.0;
  47 // 2^17 (131,072) is max size, which is about 6.5 times as large
  48 // as the previous table size (used to be 20,011),
  49 // which never resized
  50 const size_t END_SIZE = 17;
  51 // If a chain gets to 100 something might be wrong
  52 const size_t REHASH_LEN = 100;
  53 
  54 const size_t ON_STACK_BUFFER_LENGTH = 128;
  55 
  56 // --------------------------------------------------------------------------
  57 
  58 inline bool symbol_equals_compact_hashtable_entry(Symbol* value, const char* key, int len) {
  59   if (value->equals(key, len)) {
  60     assert(value->refcount() == PERM_REFCOUNT, "must be shared");
  61     return true;
  62   } else {
  63     return false;
  64   }
  65 }
  66 
  67 static OffsetCompactHashtable<
  68   const char*, Symbol*,
  69   symbol_equals_compact_hashtable_entry
  70 > _shared_table;
  71 
  72 // --------------------------------------------------------------------------
  73 SymbolTable* SymbolTable::_the_table = NULL;
  74 volatile bool SymbolTable::_alt_hash = false;
  75 volatile bool SymbolTable::_lookup_shared_first = false;
  76 // Static arena for symbols that are not deallocated
  77 Arena* SymbolTable::_arena = NULL;
  78 
  79 static juint murmur_seed = 0;
  80 
  81 static inline void log_trace_symboltable_helper(Symbol* sym, const char* msg) {
  82 #ifndef PRODUCT
  83   ResourceMark rm;
  84   log_trace(symboltable)("%s [%s]", msg, sym->as_quoted_ascii());
  85 #endif // PRODUCT
  86 }
  87 
  88 // Pick hashing algorithm.
  89 static uintx hash_symbol(const char* s, int len, bool useAlt) {
  90   return useAlt ?
  91   AltHashing::murmur3_32(murmur_seed, (const jbyte*)s, len) :
  92   java_lang_String::hash_code((const jbyte*)s, len);
  93 }
  94 
  95 static uintx hash_shared_symbol(const char* s, int len) {
  96   return java_lang_String::hash_code((const jbyte*)s, len);
  97 }
  98 
  99 class SymbolTableConfig : public SymbolTableHash::BaseConfig {
 100 private:
 101 public:
 102   static uintx get_hash(Symbol* const& value, bool* is_dead) {
 103     *is_dead = (value->refcount() == 0);
 104     if (*is_dead) {
 105       return 0;
 106     } else {
 107       return hash_symbol((const char*)value->bytes(), value->utf8_length(), SymbolTable::_alt_hash);
 108     }
 109   }
 110   // We use default allocation/deallocation but counted
 111   static void* allocate_node(size_t size, Symbol* const& value) {
 112     SymbolTable::item_added();
 113     return SymbolTableHash::BaseConfig::allocate_node(size, value);
 114   }
 115   static void free_node(void* memory, Symbol* const& value) {
 116     // We get here because #1 some threads lost a race to insert a newly created Symbol
 117     // or #2 we're cleaning up unused symbol.
 118     // If #1, then the symbol can be either permanent (refcount==PERM_REFCOUNT),
 119     // or regular newly created one (refcount==1)
 120     // If #2, then the symbol is dead (refcount==0)
 121     assert((value->refcount() == PERM_REFCOUNT) || (value->refcount() == 1) || (value->refcount() == 0),
 122            "refcount %d", value->refcount());
 123     if (value->refcount() == 1) {
 124       value->decrement_refcount();
 125       assert(value->refcount() == 0, "expected dead symbol");
 126     }
 127     SymbolTable::delete_symbol(value);
 128     SymbolTableHash::BaseConfig::free_node(memory, value);
 129     SymbolTable::item_removed();
 130   }
 131 };
 132 
 133 static size_t ceil_log2(size_t value) {
 134   size_t ret;
 135   for (ret = 1; ((size_t)1 << ret) < value; ++ret);
 136   return ret;
 137 }
 138 
 139 SymbolTable::SymbolTable() :
 140   _symbols_removed(0), _symbols_counted(0), _local_table(NULL),
 141   _current_size(0), _has_work(0), _needs_rehashing(false),
 142   _items_count(0), _has_items_to_clean(false) {
 143 
 144   size_t start_size_log_2 = ceil_log2(SymbolTableSize);
 145   _current_size = ((size_t)1) << start_size_log_2;
 146   log_trace(symboltable)("Start size: " SIZE_FORMAT " (" SIZE_FORMAT ")",
 147                          _current_size, start_size_log_2);
 148   _local_table = new SymbolTableHash(start_size_log_2, END_SIZE, REHASH_LEN);
 149 }
 150 
 151 void SymbolTable::delete_symbol(Symbol* sym) {
 152   if (sym->refcount() == PERM_REFCOUNT) {
 153     MutexLocker ml(SymbolArena_lock, Mutex::_no_safepoint_check_flag); // Protect arena
 154     // Deleting permanent symbol should not occur very often (insert race condition),
 155     // so log it.
 156     log_trace_symboltable_helper(sym, "Freeing permanent symbol");
 157     if (!arena()->Afree(sym, sym->size())) {
 158       log_trace_symboltable_helper(sym, "Leaked permanent symbol");
 159     }
 160   } else {
 161     delete sym;
 162   }
 163 }
 164 
 165 void SymbolTable::update_needs_rehash(bool rehash) {
 166   if (rehash) {
 167     _needs_rehashing = true;
 168   }
 169 }
 170 
 171 void SymbolTable::reset_has_items_to_clean() { Atomic::store(false, &_has_items_to_clean); }
 172 void SymbolTable::mark_has_items_to_clean()  { Atomic::store(true, &_has_items_to_clean); }
 173 bool SymbolTable::has_items_to_clean() const { return Atomic::load(&_has_items_to_clean); }
 174 
 175 void SymbolTable::item_added() {
 176   Atomic::inc(&(SymbolTable::the_table()->_items_count));
 177 }
 178 
 179 void SymbolTable::item_removed() {
 180   Atomic::inc(&(SymbolTable::the_table()->_symbols_removed));
 181   Atomic::dec(&(SymbolTable::the_table()->_items_count));
 182 }
 183 
 184 double SymbolTable::get_load_factor() const {
 185   return (double)_items_count/_current_size;
 186 }
 187 
 188 size_t SymbolTable::table_size() {
 189   return ((size_t)1) << _local_table->get_size_log2(Thread::current());
 190 }
 191 
 192 void SymbolTable::trigger_cleanup() {
 193   MutexLocker ml(Service_lock, Mutex::_no_safepoint_check_flag);
 194   SymbolTable::the_table()->_has_work = true;
 195   Service_lock->notify_all();
 196 }
 197 
 198 Symbol* SymbolTable::allocate_symbol(const char* name, int len, bool c_heap, TRAPS) {
 199   assert (len <= Symbol::max_length(), "should be checked by caller");
 200 
 201   Symbol* sym;
 202   if (DumpSharedSpaces) {
 203     c_heap = false;
 204   }
 205   if (c_heap) {
 206     // refcount starts as 1
 207     sym = new (len, THREAD) Symbol((const u1*)name, len, 1);
 208     assert(sym != NULL, "new should call vm_exit_out_of_memory if C_HEAP is exhausted");
 209   } else {
 210     // Allocate to global arena
 211     MutexLocker ml(SymbolArena_lock, Mutex::_no_safepoint_check_flag); // Protect arena
 212     sym = new (len, arena(), THREAD) Symbol((const u1*)name, len, PERM_REFCOUNT);
 213   }
 214   return sym;
 215 }
 216 
 217 void SymbolTable::initialize_symbols(int arena_alloc_size) {
 218   // Initialize the arena for global symbols, size passed in depends on CDS.
 219   if (arena_alloc_size == 0) {
 220     _arena = new (mtSymbol) Arena(mtSymbol);
 221   } else {
 222     _arena = new (mtSymbol) Arena(mtSymbol, arena_alloc_size);
 223   }
 224 }
 225 
 226 class SymbolsDo : StackObj {
 227   SymbolClosure *_cl;
 228 public:
 229   SymbolsDo(SymbolClosure *cl) : _cl(cl) {}
 230   bool operator()(Symbol** value) {
 231     assert(value != NULL, "expected valid value");
 232     assert(*value != NULL, "value should point to a symbol");
 233     _cl->do_symbol(value);
 234     return true;
 235   };
 236 };
 237 
 238 class SharedSymbolIterator {
 239   SymbolClosure* _symbol_closure;
 240 public:
 241   SharedSymbolIterator(SymbolClosure* f) : _symbol_closure(f) {}
 242   void do_value(Symbol* symbol) {
 243     _symbol_closure->do_symbol(&symbol);
 244   }
 245 };
 246 
 247 // Call function for all symbols in the symbol table.
 248 void SymbolTable::symbols_do(SymbolClosure *cl) {
 249   // all symbols from shared table
 250   SharedSymbolIterator iter(cl);
 251   _shared_table.iterate(&iter);
 252 
 253   // all symbols from the dynamic table
 254   SymbolsDo sd(cl);
 255   if (!SymbolTable::the_table()->_local_table->try_scan(Thread::current(), sd)) {
 256     log_info(stringtable)("symbols_do unavailable at this moment");
 257   }
 258 }
 259 
 260 class MetaspacePointersDo : StackObj {
 261   MetaspaceClosure *_it;
 262 public:
 263   MetaspacePointersDo(MetaspaceClosure *it) : _it(it) {}
 264   bool operator()(Symbol** value) {
 265     assert(value != NULL, "expected valid value");
 266     assert(*value != NULL, "value should point to a symbol");
 267     _it->push(value);
 268     return true;
 269   };
 270 };
 271 
 272 void SymbolTable::metaspace_pointers_do(MetaspaceClosure* it) {
 273   assert(DumpSharedSpaces, "called only during dump time");
 274   MetaspacePointersDo mpd(it);
 275   SymbolTable::the_table()->_local_table->do_safepoint_scan(mpd);
 276 }
 277 
 278 Symbol* SymbolTable::lookup_dynamic(const char* name,
 279                                     int len, unsigned int hash) {
 280   Symbol* sym = SymbolTable::the_table()->do_lookup(name, len, hash);
 281   assert((sym == NULL) || sym->refcount() != 0, "refcount must not be zero");
 282   return sym;
 283 }
 284 
 285 Symbol* SymbolTable::lookup_shared(const char* name,
 286                                    int len, unsigned int hash) {
 287   if (!_shared_table.empty()) {
 288     if (SymbolTable::_alt_hash) {
 289       // hash_code parameter may use alternate hashing algorithm but the shared table
 290       // always uses the same original hash code.
 291       hash = hash_shared_symbol(name, len);
 292     }
 293     return _shared_table.lookup(name, hash, len);
 294   } else {
 295     return NULL;
 296   }
 297 }
 298 
 299 Symbol* SymbolTable::lookup_common(const char* name,
 300                             int len, unsigned int hash) {
 301   Symbol* sym;
 302   if (_lookup_shared_first) {
 303     sym = lookup_shared(name, len, hash);
 304     if (sym == NULL) {
 305       _lookup_shared_first = false;
 306       sym = lookup_dynamic(name, len, hash);
 307     }
 308   } else {
 309     sym = lookup_dynamic(name, len, hash);
 310     if (sym == NULL) {
 311       sym = lookup_shared(name, len, hash);
 312       if (sym != NULL) {
 313         _lookup_shared_first = true;
 314       }
 315     }
 316   }
 317   return sym;
 318 }
 319 
 320 Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) {
 321   unsigned int hash = hash_symbol(name, len, SymbolTable::_alt_hash);
 322   Symbol* sym = SymbolTable::the_table()->lookup_common(name, len, hash);
 323   if (sym == NULL) {
 324     sym = SymbolTable::the_table()->do_add_if_needed(name, len, hash, true, CHECK_NULL);
 325   }
 326   assert(sym->refcount() != 0, "lookup should have incremented the count");
 327   assert(sym->equals(name, len), "symbol must be properly initialized");
 328   return sym;
 329 }
 330 
 331 Symbol* SymbolTable::lookup(const Symbol* sym, int begin, int end, TRAPS) {
 332   assert(sym->refcount() != 0, "require a valid symbol");
 333   const char* name = (const char*)sym->base() + begin;
 334   int len = end - begin;
 335   unsigned int hash = hash_symbol(name, len, SymbolTable::_alt_hash);
 336   Symbol* found = SymbolTable::the_table()->lookup_common(name, len, hash);
 337   if (found == NULL) {
 338     found = SymbolTable::the_table()->do_add_if_needed(name, len, hash, true, THREAD);
 339   }
 340   return found;
 341 }
 342 
 343 class SymbolTableLookup : StackObj {
 344 private:
 345   Thread* _thread;
 346   uintx _hash;
 347   int _len;
 348   const char* _str;
 349 public:
 350   SymbolTableLookup(Thread* thread, const char* key, int len, uintx hash)
 351   : _thread(thread), _hash(hash), _len(len), _str(key) {}
 352   uintx get_hash() const {
 353     return _hash;
 354   }
 355   bool equals(Symbol** value, bool* is_dead) {
 356     assert(value != NULL, "expected valid value");
 357     assert(*value != NULL, "value should point to a symbol");
 358     Symbol *sym = *value;
 359     if (sym->equals(_str, _len)) {
 360       if (sym->try_increment_refcount()) {
 361         // something is referencing this symbol now.
 362         return true;
 363       } else {
 364         assert(sym->refcount() == 0, "expected dead symbol");
 365         *is_dead = true;
 366         return false;
 367       }
 368     } else {
 369       *is_dead = (sym->refcount() == 0);
 370       return false;
 371     }
 372   }
 373 };
 374 
 375 class SymbolTableGet : public StackObj {
 376   Symbol* _return;
 377 public:
 378   SymbolTableGet() : _return(NULL) {}
 379   void operator()(Symbol** value) {
 380     assert(value != NULL, "expected valid value");
 381     assert(*value != NULL, "value should point to a symbol");
 382     _return = *value;
 383   }
 384   Symbol* get_res_sym() const {
 385     return _return;
 386   }
 387 };
 388 
 389 Symbol* SymbolTable::do_lookup(const char* name, int len, uintx hash) {
 390   Thread* thread = Thread::current();
 391   SymbolTableLookup lookup(thread, name, len, hash);
 392   SymbolTableGet stg;
 393   bool rehash_warning = false;
 394   _local_table->get(thread, lookup, stg, &rehash_warning);
 395   update_needs_rehash(rehash_warning);
 396   Symbol* sym = stg.get_res_sym();
 397   assert((sym == NULL) || sym->refcount() != 0, "found dead symbol");
 398   return sym;
 399 }
 400 
 401 Symbol* SymbolTable::lookup_only(const char* name, int len, unsigned int& hash) {
 402   hash = hash_symbol(name, len, SymbolTable::_alt_hash);
 403   return SymbolTable::the_table()->lookup_common(name, len, hash);
 404 }
 405 
 406 // Suggestion: Push unicode-based lookup all the way into the hashing
 407 // and probing logic, so there is no need for convert_to_utf8 until
 408 // an actual new Symbol* is created.
 409 Symbol* SymbolTable::lookup_unicode(const jchar* name, int utf16_length, TRAPS) {
 410   int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
 411   char stack_buf[ON_STACK_BUFFER_LENGTH];
 412   if (utf8_length < (int) sizeof(stack_buf)) {
 413     char* chars = stack_buf;
 414     UNICODE::convert_to_utf8(name, utf16_length, chars);
 415     return lookup(chars, utf8_length, THREAD);
 416   } else {
 417     ResourceMark rm(THREAD);
 418     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
 419     UNICODE::convert_to_utf8(name, utf16_length, chars);
 420     return lookup(chars, utf8_length, THREAD);
 421   }
 422 }
 423 
 424 Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,
 425                                            unsigned int& hash) {
 426   int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
 427   char stack_buf[ON_STACK_BUFFER_LENGTH];
 428   if (utf8_length < (int) sizeof(stack_buf)) {
 429     char* chars = stack_buf;
 430     UNICODE::convert_to_utf8(name, utf16_length, chars);
 431     return lookup_only(chars, utf8_length, hash);
 432   } else {
 433     ResourceMark rm;
 434     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
 435     UNICODE::convert_to_utf8(name, utf16_length, chars);
 436     return lookup_only(chars, utf8_length, hash);
 437   }
 438 }
 439 
 440 void SymbolTable::new_symbols(ClassLoaderData* loader_data, const constantPoolHandle& cp,
 441                               int names_count, const char** names, int* lengths,
 442                               int* cp_indices, unsigned int* hashValues, TRAPS) {
 443   bool c_heap = !loader_data->is_the_null_class_loader_data();
 444   for (int i = 0; i < names_count; i++) {
 445     const char *name = names[i];
 446     int len = lengths[i];
 447     unsigned int hash = hashValues[i];
 448     assert(SymbolTable::the_table()->lookup_shared(name, len, hash) == NULL, "must have checked already");
 449     Symbol* sym = SymbolTable::the_table()->do_add_if_needed(name, len, hash, c_heap, CHECK);
 450     assert(sym->refcount() != 0, "lookup should have incremented the count");
 451     cp->symbol_at_put(cp_indices[i], sym);
 452   }
 453 }
 454 
 455 Symbol* SymbolTable::do_add_if_needed(const char* name, int len, uintx hash, bool heap, TRAPS) {
 456   SymbolTableLookup lookup(THREAD, name, len, hash);
 457   SymbolTableGet stg;
 458   bool clean_hint = false;
 459   bool rehash_warning = false;
 460   Symbol* sym = NULL;
 461 
 462   do {
 463     if (_local_table->get(THREAD, lookup, stg, &rehash_warning)) {
 464       sym = stg.get_res_sym();
 465       break;
 466     }
 467     sym = SymbolTable::the_table()->allocate_symbol(name, len, heap, THREAD);
 468     if (_local_table->insert(THREAD, lookup, sym, &rehash_warning, &clean_hint)) {
 469       break;
 470     }
 471   } while(true);
 472 
 473   update_needs_rehash(rehash_warning);
 474 
 475   if (clean_hint) {
 476     mark_has_items_to_clean();
 477     check_concurrent_work();
 478   }
 479 
 480   assert((sym == NULL) || sym->refcount() != 0, "found dead symbol");
 481   return sym;
 482 }
 483 
 484 Symbol* SymbolTable::new_permanent_symbol(const char* name, TRAPS) {
 485   unsigned int hash = 0;
 486   int len = (int)strlen(name);
 487   Symbol* sym = SymbolTable::lookup_only(name, len, hash);
 488   if (sym == NULL) {
 489     sym = SymbolTable::the_table()->do_add_if_needed(name, len, hash, false, CHECK_NULL);
 490   }
 491   if (!sym->is_permanent()) {
 492     sym->make_permanent();
 493     log_trace_symboltable_helper(sym, "Asked for a permanent symbol, but got a regular one");
 494   }
 495   return sym;
 496 }
 497 
 498 struct SizeFunc : StackObj {
 499   size_t operator()(Symbol** value) {
 500     assert(value != NULL, "expected valid value");
 501     assert(*value != NULL, "value should point to a symbol");
 502     return (*value)->size() * HeapWordSize;
 503   };
 504 };
 505 
 506 TableStatistics SymbolTable::get_table_statistics() {
 507   static TableStatistics ts;
 508   SizeFunc sz;
 509   ts = _local_table->statistics_get(Thread::current(), sz, ts);
 510   return ts;
 511 }
 512 
 513 void SymbolTable::print_table_statistics(outputStream* st,
 514                                          const char* table_name) {
 515   SizeFunc sz;
 516   _local_table->statistics_to(Thread::current(), sz, st, table_name);
 517 }
 518 
 519 // Verification
 520 class VerifySymbols : StackObj {
 521 public:
 522   bool operator()(Symbol** value) {
 523     guarantee(value != NULL, "expected valid value");
 524     guarantee(*value != NULL, "value should point to a symbol");
 525     Symbol* sym = *value;
 526     guarantee(sym->equals((const char*)sym->bytes(), sym->utf8_length()),
 527               "symbol must be internally consistent");
 528     return true;
 529   };
 530 };
 531 
 532 void SymbolTable::verify() {
 533   Thread* thr = Thread::current();
 534   VerifySymbols vs;
 535   if (!SymbolTable::the_table()->_local_table->try_scan(thr, vs)) {
 536     log_info(stringtable)("verify unavailable at this moment");
 537   }
 538 }
 539 
 540 // Dumping
 541 class DumpSymbol : StackObj {
 542   Thread* _thr;
 543   outputStream* _st;
 544 public:
 545   DumpSymbol(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
 546   bool operator()(Symbol** value) {
 547     assert(value != NULL, "expected valid value");
 548     assert(*value != NULL, "value should point to a symbol");
 549     Symbol* sym = *value;
 550     const char* utf8_string = (const char*)sym->bytes();
 551     int utf8_length = sym->utf8_length();
 552     _st->print("%d %d: ", utf8_length, sym->refcount());
 553     HashtableTextDump::put_utf8(_st, utf8_string, utf8_length);
 554     _st->cr();
 555     return true;
 556   };
 557 };
 558 
 559 void SymbolTable::dump(outputStream* st, bool verbose) {
 560   if (!verbose) {
 561     SymbolTable::the_table()->print_table_statistics(st, "SymbolTable");
 562   } else {
 563     Thread* thr = Thread::current();
 564     ResourceMark rm(thr);
 565     st->print_cr("VERSION: 1.1");
 566     DumpSymbol ds(thr, st);
 567     if (!SymbolTable::the_table()->_local_table->try_scan(thr, ds)) {
 568       log_info(symboltable)("dump unavailable at this moment");
 569     }
 570   }
 571 }
 572 
 573 #if INCLUDE_CDS
 574 struct CopyToArchive : StackObj {
 575   CompactHashtableWriter* _writer;
 576   CopyToArchive(CompactHashtableWriter* writer) : _writer(writer) {}
 577   bool operator()(Symbol** value) {
 578     assert(value != NULL, "expected valid value");
 579     assert(*value != NULL, "value should point to a symbol");
 580     Symbol* sym = *value;
 581     unsigned int fixed_hash = hash_shared_symbol((const char*)sym->bytes(), sym->utf8_length());
 582     assert(fixed_hash == hash_symbol((const char*)sym->bytes(), sym->utf8_length(), false),
 583            "must not rehash during dumping");
 584     _writer->add(fixed_hash, MetaspaceShared::object_delta_u4(sym));
 585     return true;
 586   }
 587 };
 588 
 589 void SymbolTable::copy_shared_symbol_table(CompactHashtableWriter* writer) {
 590   CopyToArchive copy(writer);
 591   SymbolTable::the_table()->_local_table->do_safepoint_scan(copy);
 592 }
 593 
 594 void SymbolTable::write_to_archive() {
 595   _shared_table.reset();
 596 
 597   int num_buckets = CompactHashtableWriter::default_num_buckets(
 598       SymbolTable::the_table()->_items_count);
 599   CompactHashtableWriter writer(num_buckets,
 600                                 &MetaspaceShared::stats()->symbol);
 601   copy_shared_symbol_table(&writer);
 602   writer.dump(&_shared_table, "symbol");
 603 
 604   // Verify table is correct
 605   Symbol* sym = vmSymbols::java_lang_Object();
 606   const char* name = (const char*)sym->bytes();
 607   int len = sym->utf8_length();
 608   unsigned int hash = hash_symbol(name, len, SymbolTable::_alt_hash);
 609   assert(sym == _shared_table.lookup(name, hash, len), "sanity");
 610 }
 611 
 612 void SymbolTable::serialize_shared_table_header(SerializeClosure* soc) {
 613   _shared_table.serialize_header(soc);
 614 
 615   if (soc->writing()) {
 616     // Sanity. Make sure we don't use the shared table at dump time
 617     _shared_table.reset();
 618   }
 619 }
 620 #endif //INCLUDE_CDS
 621 
 622 // Concurrent work
 623 void SymbolTable::grow(JavaThread* jt) {
 624   SymbolTableHash::GrowTask gt(_local_table);
 625   if (!gt.prepare(jt)) {
 626     return;
 627   }
 628   log_trace(symboltable)("Started to grow");
 629   {
 630     TraceTime timer("Grow", TRACETIME_LOG(Debug, symboltable, perf));
 631     while (gt.do_task(jt)) {
 632       gt.pause(jt);
 633       {
 634         ThreadBlockInVM tbivm(jt);
 635       }
 636       gt.cont(jt);
 637     }
 638   }
 639   gt.done(jt);
 640   _current_size = table_size();
 641   log_debug(symboltable)("Grown to size:" SIZE_FORMAT, _current_size);
 642 }
 643 
 644 struct SymbolTableDoDelete : StackObj {
 645   size_t _deleted;
 646   SymbolTableDoDelete() : _deleted(0) {}
 647   void operator()(Symbol** value) {
 648     assert(value != NULL, "expected valid value");
 649     assert(*value != NULL, "value should point to a symbol");
 650     Symbol *sym = *value;
 651     assert(sym->refcount() == 0, "refcount");
 652     _deleted++;
 653   }
 654 };
 655 
 656 struct SymbolTableDeleteCheck : StackObj {
 657   size_t _processed;
 658   SymbolTableDeleteCheck() : _processed(0) {}
 659   bool operator()(Symbol** value) {
 660     assert(value != NULL, "expected valid value");
 661     assert(*value != NULL, "value should point to a symbol");
 662     _processed++;
 663     Symbol *sym = *value;
 664     return (sym->refcount() == 0);
 665   }
 666 };
 667 
 668 void SymbolTable::clean_dead_entries(JavaThread* jt) {
 669   SymbolTableHash::BulkDeleteTask bdt(_local_table);
 670   if (!bdt.prepare(jt)) {
 671     return;
 672   }
 673 
 674   SymbolTableDeleteCheck stdc;
 675   SymbolTableDoDelete stdd;
 676   {
 677     TraceTime timer("Clean", TRACETIME_LOG(Debug, symboltable, perf));
 678     while (bdt.do_task(jt, stdc, stdd)) {
 679       bdt.pause(jt);
 680       {
 681         ThreadBlockInVM tbivm(jt);
 682       }
 683       bdt.cont(jt);
 684     }
 685     SymbolTable::the_table()->reset_has_items_to_clean();
 686     bdt.done(jt);
 687   }
 688 
 689   Atomic::add(stdc._processed, &_symbols_counted);
 690 
 691   log_debug(symboltable)("Cleaned " SIZE_FORMAT " of " SIZE_FORMAT,
 692                          stdd._deleted, stdc._processed);
 693 }
 694 
 695 void SymbolTable::check_concurrent_work() {
 696   if (_has_work) {
 697     return;
 698   }
 699   // We should clean/resize if we have
 700   // more items than preferred load factor or
 701   // more dead items than water mark.
 702   if (has_items_to_clean() || (get_load_factor() > PREF_AVG_LIST_LEN)) {
 703     log_debug(symboltable)("Concurrent work triggered, load factor: %f, items to clean: %s",
 704                            get_load_factor(), has_items_to_clean() ? "true" : "false");
 705     trigger_cleanup();
 706   }
 707 }
 708 
 709 void SymbolTable::concurrent_work(JavaThread* jt) {
 710   double load_factor = get_load_factor();
 711   log_debug(symboltable, perf)("Concurrent work, live factor: %g", load_factor);
 712   // We prefer growing, since that also removes dead items
 713   if (load_factor > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached()) {
 714     grow(jt);
 715   } else {
 716     clean_dead_entries(jt);
 717   }
 718   _has_work = false;
 719 }
 720 
 721 void SymbolTable::do_concurrent_work(JavaThread* jt) {
 722   SymbolTable::the_table()->concurrent_work(jt);
 723 }
 724 
 725 // Rehash
 726 bool SymbolTable::do_rehash() {
 727   if (!_local_table->is_safepoint_safe()) {
 728     return false;
 729   }
 730 
 731   // We use max size
 732   SymbolTableHash* new_table = new SymbolTableHash(END_SIZE, END_SIZE, REHASH_LEN);
 733   // Use alt hash from now on
 734   _alt_hash = true;
 735   if (!_local_table->try_move_nodes_to(Thread::current(), new_table)) {
 736     _alt_hash = false;
 737     delete new_table;
 738     return false;
 739   }
 740 
 741   // free old table
 742   delete _local_table;
 743   _local_table = new_table;
 744 
 745   return true;
 746 }
 747 
 748 void SymbolTable::try_rehash_table() {
 749   static bool rehashed = false;
 750   log_debug(symboltable)("Table imbalanced, rehashing called.");
 751 
 752   // Grow instead of rehash.
 753   if (get_load_factor() > PREF_AVG_LIST_LEN &&
 754       !_local_table->is_max_size_reached()) {
 755     log_debug(symboltable)("Choosing growing over rehashing.");
 756     trigger_cleanup();
 757     _needs_rehashing = false;
 758     return;
 759   }
 760 
 761   // Already rehashed.
 762   if (rehashed) {
 763     log_warning(symboltable)("Rehashing already done, still long lists.");
 764     trigger_cleanup();
 765     _needs_rehashing = false;
 766     return;
 767   }
 768 
 769   murmur_seed = AltHashing::compute_seed();
 770 
 771   if (do_rehash()) {
 772     rehashed = true;
 773   } else {
 774     log_info(symboltable)("Resizes in progress rehashing skipped.");
 775   }
 776 
 777   _needs_rehashing = false;
 778 }
 779 
 780 void SymbolTable::rehash_table() {
 781   SymbolTable::the_table()->try_rehash_table();
 782 }
 783 
 784 //---------------------------------------------------------------------------
 785 // Non-product code
 786 
 787 #ifndef PRODUCT
 788 
 789 class HistogramIterator : StackObj {
 790 public:
 791   static const size_t results_length = 100;
 792   size_t counts[results_length];
 793   size_t sizes[results_length];
 794   size_t total_size;
 795   size_t total_count;
 796   size_t total_length;
 797   size_t max_length;
 798   size_t out_of_range_count;
 799   size_t out_of_range_size;
 800   HistogramIterator() : total_size(0), total_count(0), total_length(0),
 801                         max_length(0), out_of_range_count(0), out_of_range_size(0) {
 802     // initialize results to zero
 803     for (size_t i = 0; i < results_length; i++) {
 804       counts[i] = 0;
 805       sizes[i] = 0;
 806     }
 807   }
 808   bool operator()(Symbol** value) {
 809     assert(value != NULL, "expected valid value");
 810     assert(*value != NULL, "value should point to a symbol");
 811     Symbol* sym = *value;
 812     size_t size = sym->size();
 813     size_t len = sym->utf8_length();
 814     if (len < results_length) {
 815       counts[len]++;
 816       sizes[len] += size;
 817     } else {
 818       out_of_range_count++;
 819       out_of_range_size += size;
 820     }
 821     total_count++;
 822     total_size += size;
 823     total_length += len;
 824     max_length = MAX2(max_length, len);
 825 
 826     return true;
 827   };
 828 };
 829 
 830 void SymbolTable::print_histogram() {
 831   SymbolTable* st = SymbolTable::the_table();
 832   HistogramIterator hi;
 833   st->_local_table->do_scan(Thread::current(), hi);
 834   tty->print_cr("Symbol Table Histogram:");
 835   tty->print_cr("  Total number of symbols  " SIZE_FORMAT_W(7), hi.total_count);
 836   tty->print_cr("  Total size in memory     " SIZE_FORMAT_W(7) "K",
 837           (hi.total_size * wordSize) / 1024);
 838   tty->print_cr("  Total counted            " SIZE_FORMAT_W(7), st->_symbols_counted);
 839   tty->print_cr("  Total removed            " SIZE_FORMAT_W(7), st->_symbols_removed);
 840   if (SymbolTable::the_table()->_symbols_counted > 0) {
 841     tty->print_cr("  Percent removed          %3.2f",
 842           ((float)st->_symbols_removed / st->_symbols_counted) * 100);
 843   }
 844   tty->print_cr("  Reference counts         " SIZE_FORMAT_W(7), Symbol::_total_count);
 845   tty->print_cr("  Symbol arena used        " SIZE_FORMAT_W(7) "K", arena()->used() / 1024);
 846   tty->print_cr("  Symbol arena size        " SIZE_FORMAT_W(7) "K", arena()->size_in_bytes() / 1024);
 847   tty->print_cr("  Total symbol length      " SIZE_FORMAT_W(7), hi.total_length);
 848   tty->print_cr("  Maximum symbol length    " SIZE_FORMAT_W(7), hi.max_length);
 849   tty->print_cr("  Average symbol length    %7.2f", ((float)hi.total_length / hi.total_count));
 850   tty->print_cr("  Symbol length histogram:");
 851   tty->print_cr("    %6s %10s %10s", "Length", "#Symbols", "Size");
 852   for (size_t i = 0; i < hi.results_length; i++) {
 853     if (hi.counts[i] > 0) {
 854       tty->print_cr("    " SIZE_FORMAT_W(6) " " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) "K",
 855                     i, hi.counts[i], (hi.sizes[i] * wordSize) / 1024);
 856     }
 857   }
 858   tty->print_cr("  >=" SIZE_FORMAT_W(6) " " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) "K\n",
 859                 hi.results_length, hi.out_of_range_count, (hi.out_of_range_size*wordSize) / 1024);
 860 }
 861 #endif // PRODUCT
 862 
 863 // Utility for dumping symbols
 864 SymboltableDCmd::SymboltableDCmd(outputStream* output, bool heap) :
 865                                  DCmdWithParser(output, heap),
 866   _verbose("-verbose", "Dump the content of each symbol in the table",
 867            "BOOLEAN", false, "false") {
 868   _dcmdparser.add_dcmd_option(&_verbose);
 869 }
 870 
 871 void SymboltableDCmd::execute(DCmdSource source, TRAPS) {
 872   VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpSymbols,
 873                          _verbose.value());
 874   VMThread::execute(&dumper);
 875 }
 876 
 877 int SymboltableDCmd::num_arguments() {
 878   ResourceMark rm;
 879   SymboltableDCmd* dcmd = new SymboltableDCmd(NULL, false);
 880   if (dcmd != NULL) {
 881     DCmdMark mark(dcmd);
 882     return dcmd->_dcmdparser.num_arguments();
 883   } else {
 884     return 0;
 885   }
 886 }