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