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