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