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