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