symbolTable.cpp revision 6853:91eeb8807a03
1/* 2 * Copyright (c) 1997, 2014, 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/javaClasses.hpp" 28#include "classfile/symbolTable.hpp" 29#include "classfile/systemDictionary.hpp" 30#include "gc_interface/collectedHeap.inline.hpp" 31#include "memory/allocation.inline.hpp" 32#include "memory/filemap.hpp" 33#include "memory/gcLocker.inline.hpp" 34#include "oops/oop.inline.hpp" 35#include "oops/oop.inline2.hpp" 36#include "runtime/atomic.inline.hpp" 37#include "runtime/mutexLocker.hpp" 38#include "utilities/hashtable.inline.hpp" 39 40PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC 41 42// -------------------------------------------------------------------------- 43// the number of buckets a thread claims 44const int ClaimChunkSize = 32; 45 46SymbolTable* SymbolTable::_the_table = NULL; 47// Static arena for symbols that are not deallocated 48Arena* SymbolTable::_arena = NULL; 49bool SymbolTable::_needs_rehashing = false; 50 51Symbol* SymbolTable::allocate_symbol(const u1* name, int len, bool c_heap, TRAPS) { 52 assert (len <= Symbol::max_length(), "should be checked by caller"); 53 54 Symbol* sym; 55 56 if (DumpSharedSpaces) { 57 // Allocate all symbols to CLD shared metaspace 58 sym = new (len, ClassLoaderData::the_null_class_loader_data(), THREAD) Symbol(name, len, -1); 59 } else if (c_heap) { 60 // refcount starts as 1 61 sym = new (len, THREAD) Symbol(name, len, 1); 62 assert(sym != NULL, "new should call vm_exit_out_of_memory if C_HEAP is exhausted"); 63 } else { 64 // Allocate to global arena 65 sym = new (len, arena(), THREAD) Symbol(name, len, -1); 66 } 67 return sym; 68} 69 70void SymbolTable::initialize_symbols(int arena_alloc_size) { 71 // Initialize the arena for global symbols, size passed in depends on CDS. 72 if (arena_alloc_size == 0) { 73 _arena = new (mtSymbol) Arena(mtSymbol); 74 } else { 75 _arena = new (mtSymbol) Arena(mtSymbol, arena_alloc_size); 76 } 77} 78 79// Call function for all symbols in the symbol table. 80void SymbolTable::symbols_do(SymbolClosure *cl) { 81 const int n = the_table()->table_size(); 82 for (int i = 0; i < n; i++) { 83 for (HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i); 84 p != NULL; 85 p = p->next()) { 86 cl->do_symbol(p->literal_addr()); 87 } 88 } 89} 90 91int SymbolTable::_symbols_removed = 0; 92int SymbolTable::_symbols_counted = 0; 93volatile int SymbolTable::_parallel_claimed_idx = 0; 94 95void SymbolTable::buckets_unlink(int start_idx, int end_idx, int* processed, int* removed, size_t* memory_total) { 96 for (int i = start_idx; i < end_idx; ++i) { 97 HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i); 98 HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i); 99 while (entry != NULL) { 100 // Shared entries are normally at the end of the bucket and if we run into 101 // a shared entry, then there is nothing more to remove. However, if we 102 // have rehashed the table, then the shared entries are no longer at the 103 // end of the bucket. 104 if (entry->is_shared() && !use_alternate_hashcode()) { 105 break; 106 } 107 Symbol* s = entry->literal(); 108 (*memory_total) += s->size(); 109 (*processed)++; 110 assert(s != NULL, "just checking"); 111 // If reference count is zero, remove. 112 if (s->refcount() == 0) { 113 assert(!entry->is_shared(), "shared entries should be kept live"); 114 delete s; 115 (*removed)++; 116 *p = entry->next(); 117 the_table()->free_entry(entry); 118 } else { 119 p = entry->next_addr(); 120 } 121 // get next entry 122 entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p); 123 } 124 } 125} 126 127// Remove unreferenced symbols from the symbol table 128// This is done late during GC. 129void SymbolTable::unlink(int* processed, int* removed) { 130 size_t memory_total = 0; 131 buckets_unlink(0, the_table()->table_size(), processed, removed, &memory_total); 132 _symbols_removed += *removed; 133 _symbols_counted += *processed; 134 // Exclude printing for normal PrintGCDetails because people parse 135 // this output. 136 if (PrintGCDetails && Verbose && WizardMode) { 137 gclog_or_tty->print(" [Symbols=%d size=" SIZE_FORMAT "K] ", *processed, 138 (memory_total*HeapWordSize)/1024); 139 } 140} 141 142void SymbolTable::possibly_parallel_unlink(int* processed, int* removed) { 143 const int limit = the_table()->table_size(); 144 145 size_t memory_total = 0; 146 147 for (;;) { 148 // Grab next set of buckets to scan 149 int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize; 150 if (start_idx >= limit) { 151 // End of table 152 break; 153 } 154 155 int end_idx = MIN2(limit, start_idx + ClaimChunkSize); 156 buckets_unlink(start_idx, end_idx, processed, removed, &memory_total); 157 } 158 Atomic::add(*processed, &_symbols_counted); 159 Atomic::add(*removed, &_symbols_removed); 160 // Exclude printing for normal PrintGCDetails because people parse 161 // this output. 162 if (PrintGCDetails && Verbose && WizardMode) { 163 gclog_or_tty->print(" [Symbols: scanned=%d removed=%d size=" SIZE_FORMAT "K] ", *processed, *removed, 164 (memory_total*HeapWordSize)/1024); 165 } 166} 167 168// Create a new table and using alternate hash code, populate the new table 169// with the existing strings. Set flag to use the alternate hash code afterwards. 170void SymbolTable::rehash_table() { 171 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint"); 172 // This should never happen with -Xshare:dump but it might in testing mode. 173 if (DumpSharedSpaces) return; 174 // Create a new symbol table 175 SymbolTable* new_table = new SymbolTable(); 176 177 the_table()->move_to(new_table); 178 179 // Delete the table and buckets (entries are reused in new table). 180 delete _the_table; 181 // Don't check if we need rehashing until the table gets unbalanced again. 182 // Then rehash with a new global seed. 183 _needs_rehashing = false; 184 _the_table = new_table; 185} 186 187// Lookup a symbol in a bucket. 188 189Symbol* SymbolTable::lookup(int index, const char* name, 190 int len, unsigned int hash) { 191 int count = 0; 192 for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) { 193 count++; // count all entries in this bucket, not just ones with same hash 194 if (e->hash() == hash) { 195 Symbol* sym = e->literal(); 196 if (sym->equals(name, len)) { 197 // something is referencing this symbol now. 198 sym->increment_refcount(); 199 return sym; 200 } 201 } 202 } 203 // If the bucket size is too deep check if this hash code is insufficient. 204 if (count >= BasicHashtable<mtSymbol>::rehash_count && !needs_rehashing()) { 205 _needs_rehashing = check_rehash_table(count); 206 } 207 return NULL; 208} 209 210// Pick hashing algorithm. 211unsigned int SymbolTable::hash_symbol(const char* s, int len) { 212 return use_alternate_hashcode() ? 213 AltHashing::murmur3_32(seed(), (const jbyte*)s, len) : 214 java_lang_String::hash_code(s, len); 215} 216 217 218// We take care not to be blocking while holding the 219// SymbolTable_lock. Otherwise, the system might deadlock, since the 220// symboltable is used during compilation (VM_thread) The lock free 221// synchronization is simplified by the fact that we do not delete 222// entries in the symbol table during normal execution (only during 223// safepoints). 224 225Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) { 226 unsigned int hashValue = hash_symbol(name, len); 227 int index = the_table()->hash_to_index(hashValue); 228 229 Symbol* s = the_table()->lookup(index, name, len, hashValue); 230 231 // Found 232 if (s != NULL) return s; 233 234 // Grab SymbolTable_lock first. 235 MutexLocker ml(SymbolTable_lock, THREAD); 236 237 // Otherwise, add to symbol to table 238 return the_table()->basic_add(index, (u1*)name, len, hashValue, true, CHECK_NULL); 239} 240 241Symbol* SymbolTable::lookup(const Symbol* sym, int begin, int end, TRAPS) { 242 char* buffer; 243 int index, len; 244 unsigned int hashValue; 245 char* name; 246 { 247 debug_only(No_Safepoint_Verifier nsv;) 248 249 name = (char*)sym->base() + begin; 250 len = end - begin; 251 hashValue = hash_symbol(name, len); 252 index = the_table()->hash_to_index(hashValue); 253 Symbol* s = the_table()->lookup(index, name, len, hashValue); 254 255 // Found 256 if (s != NULL) return s; 257 } 258 259 // Otherwise, add to symbol to table. Copy to a C string first. 260 char stack_buf[128]; 261 ResourceMark rm(THREAD); 262 if (len <= 128) { 263 buffer = stack_buf; 264 } else { 265 buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len); 266 } 267 for (int i=0; i<len; i++) { 268 buffer[i] = name[i]; 269 } 270 // Make sure there is no safepoint in the code above since name can't move. 271 // We can't include the code in No_Safepoint_Verifier because of the 272 // ResourceMark. 273 274 // Grab SymbolTable_lock first. 275 MutexLocker ml(SymbolTable_lock, THREAD); 276 277 return the_table()->basic_add(index, (u1*)buffer, len, hashValue, true, CHECK_NULL); 278} 279 280Symbol* SymbolTable::lookup_only(const char* name, int len, 281 unsigned int& hash) { 282 hash = hash_symbol(name, len); 283 int index = the_table()->hash_to_index(hash); 284 285 Symbol* s = the_table()->lookup(index, name, len, hash); 286 return s; 287} 288 289// Look up the address of the literal in the SymbolTable for this Symbol* 290// Do not create any new symbols 291// Do not increment the reference count to keep this alive 292Symbol** SymbolTable::lookup_symbol_addr(Symbol* sym){ 293 unsigned int hash = hash_symbol((char*)sym->bytes(), sym->utf8_length()); 294 int index = the_table()->hash_to_index(hash); 295 296 for (HashtableEntry<Symbol*, mtSymbol>* e = the_table()->bucket(index); e != NULL; e = e->next()) { 297 if (e->hash() == hash) { 298 Symbol* literal_sym = e->literal(); 299 if (sym == literal_sym) { 300 return e->literal_addr(); 301 } 302 } 303 } 304 return NULL; 305} 306 307// Suggestion: Push unicode-based lookup all the way into the hashing 308// and probing logic, so there is no need for convert_to_utf8 until 309// an actual new Symbol* is created. 310Symbol* SymbolTable::lookup_unicode(const jchar* name, int utf16_length, TRAPS) { 311 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length); 312 char stack_buf[128]; 313 if (utf8_length < (int) sizeof(stack_buf)) { 314 char* chars = stack_buf; 315 UNICODE::convert_to_utf8(name, utf16_length, chars); 316 return lookup(chars, utf8_length, THREAD); 317 } else { 318 ResourceMark rm(THREAD); 319 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);; 320 UNICODE::convert_to_utf8(name, utf16_length, chars); 321 return lookup(chars, utf8_length, THREAD); 322 } 323} 324 325Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length, 326 unsigned int& hash) { 327 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length); 328 char stack_buf[128]; 329 if (utf8_length < (int) sizeof(stack_buf)) { 330 char* chars = stack_buf; 331 UNICODE::convert_to_utf8(name, utf16_length, chars); 332 return lookup_only(chars, utf8_length, hash); 333 } else { 334 ResourceMark rm; 335 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);; 336 UNICODE::convert_to_utf8(name, utf16_length, chars); 337 return lookup_only(chars, utf8_length, hash); 338 } 339} 340 341void SymbolTable::add(ClassLoaderData* loader_data, constantPoolHandle cp, 342 int names_count, 343 const char** names, int* lengths, int* cp_indices, 344 unsigned int* hashValues, TRAPS) { 345 // Grab SymbolTable_lock first. 346 MutexLocker ml(SymbolTable_lock, THREAD); 347 348 SymbolTable* table = the_table(); 349 bool added = table->basic_add(loader_data, cp, names_count, names, lengths, 350 cp_indices, hashValues, CHECK); 351 if (!added) { 352 // do it the hard way 353 for (int i=0; i<names_count; i++) { 354 int index = table->hash_to_index(hashValues[i]); 355 bool c_heap = !loader_data->is_the_null_class_loader_data(); 356 Symbol* sym = table->basic_add(index, (u1*)names[i], lengths[i], hashValues[i], c_heap, CHECK); 357 cp->symbol_at_put(cp_indices[i], sym); 358 } 359 } 360} 361 362Symbol* SymbolTable::new_permanent_symbol(const char* name, TRAPS) { 363 unsigned int hash; 364 Symbol* result = SymbolTable::lookup_only((char*)name, (int)strlen(name), hash); 365 if (result != NULL) { 366 return result; 367 } 368 // Grab SymbolTable_lock first. 369 MutexLocker ml(SymbolTable_lock, THREAD); 370 371 SymbolTable* table = the_table(); 372 int index = table->hash_to_index(hash); 373 return table->basic_add(index, (u1*)name, (int)strlen(name), hash, false, THREAD); 374} 375 376Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len, 377 unsigned int hashValue_arg, bool c_heap, TRAPS) { 378 assert(!Universe::heap()->is_in_reserved(name), 379 "proposed name of symbol must be stable"); 380 381 // Don't allow symbols to be created which cannot fit in a Symbol*. 382 if (len > Symbol::max_length()) { 383 THROW_MSG_0(vmSymbols::java_lang_InternalError(), 384 "name is too long to represent"); 385 } 386 387 // Cannot hit a safepoint in this function because the "this" pointer can move. 388 No_Safepoint_Verifier nsv; 389 390 // Check if the symbol table has been rehashed, if so, need to recalculate 391 // the hash value and index. 392 unsigned int hashValue; 393 int index; 394 if (use_alternate_hashcode()) { 395 hashValue = hash_symbol((const char*)name, len); 396 index = hash_to_index(hashValue); 397 } else { 398 hashValue = hashValue_arg; 399 index = index_arg; 400 } 401 402 // Since look-up was done lock-free, we need to check if another 403 // thread beat us in the race to insert the symbol. 404 Symbol* test = lookup(index, (char*)name, len, hashValue); 405 if (test != NULL) { 406 // A race occurred and another thread introduced the symbol. 407 assert(test->refcount() != 0, "lookup should have incremented the count"); 408 return test; 409 } 410 411 // Create a new symbol. 412 Symbol* sym = allocate_symbol(name, len, c_heap, CHECK_NULL); 413 assert(sym->equals((char*)name, len), "symbol must be properly initialized"); 414 415 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym); 416 add_entry(index, entry); 417 return sym; 418} 419 420// This version of basic_add adds symbols in batch from the constant pool 421// parsing. 422bool SymbolTable::basic_add(ClassLoaderData* loader_data, constantPoolHandle cp, 423 int names_count, 424 const char** names, int* lengths, 425 int* cp_indices, unsigned int* hashValues, 426 TRAPS) { 427 428 // Check symbol names are not too long. If any are too long, don't add any. 429 for (int i = 0; i< names_count; i++) { 430 if (lengths[i] > Symbol::max_length()) { 431 THROW_MSG_0(vmSymbols::java_lang_InternalError(), 432 "name is too long to represent"); 433 } 434 } 435 436 // Cannot hit a safepoint in this function because the "this" pointer can move. 437 No_Safepoint_Verifier nsv; 438 439 for (int i=0; i<names_count; i++) { 440 // Check if the symbol table has been rehashed, if so, need to recalculate 441 // the hash value. 442 unsigned int hashValue; 443 if (use_alternate_hashcode()) { 444 hashValue = hash_symbol(names[i], lengths[i]); 445 } else { 446 hashValue = hashValues[i]; 447 } 448 // Since look-up was done lock-free, we need to check if another 449 // thread beat us in the race to insert the symbol. 450 int index = hash_to_index(hashValue); 451 Symbol* test = lookup(index, names[i], lengths[i], hashValue); 452 if (test != NULL) { 453 // A race occurred and another thread introduced the symbol, this one 454 // will be dropped and collected. Use test instead. 455 cp->symbol_at_put(cp_indices[i], test); 456 assert(test->refcount() != 0, "lookup should have incremented the count"); 457 } else { 458 // Create a new symbol. The null class loader is never unloaded so these 459 // are allocated specially in a permanent arena. 460 bool c_heap = !loader_data->is_the_null_class_loader_data(); 461 Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], c_heap, CHECK_(false)); 462 assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized"); // why wouldn't it be??? 463 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym); 464 add_entry(index, entry); 465 cp->symbol_at_put(cp_indices[i], sym); 466 } 467 } 468 return true; 469} 470 471 472void SymbolTable::verify() { 473 for (int i = 0; i < the_table()->table_size(); ++i) { 474 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i); 475 for ( ; p != NULL; p = p->next()) { 476 Symbol* s = (Symbol*)(p->literal()); 477 guarantee(s != NULL, "symbol is NULL"); 478 unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length()); 479 guarantee(p->hash() == h, "broken hash in symbol table entry"); 480 guarantee(the_table()->hash_to_index(h) == i, 481 "wrong index in symbol table"); 482 } 483 } 484} 485 486void SymbolTable::dump(outputStream* st) { 487 the_table()->dump_table(st, "SymbolTable"); 488} 489 490 491//--------------------------------------------------------------------------- 492// Non-product code 493 494#ifndef PRODUCT 495 496void SymbolTable::print_histogram() { 497 MutexLocker ml(SymbolTable_lock); 498 const int results_length = 100; 499 int results[results_length]; 500 int i,j; 501 502 // initialize results to zero 503 for (j = 0; j < results_length; j++) { 504 results[j] = 0; 505 } 506 507 int total = 0; 508 int max_symbols = 0; 509 int out_of_range = 0; 510 int memory_total = 0; 511 int count = 0; 512 for (i = 0; i < the_table()->table_size(); i++) { 513 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i); 514 for ( ; p != NULL; p = p->next()) { 515 memory_total += p->literal()->size(); 516 count++; 517 int counter = p->literal()->utf8_length(); 518 total += counter; 519 if (counter < results_length) { 520 results[counter]++; 521 } else { 522 out_of_range++; 523 } 524 max_symbols = MAX2(max_symbols, counter); 525 } 526 } 527 tty->print_cr("Symbol Table:"); 528 tty->print_cr("Total number of symbols %5d", count); 529 tty->print_cr("Total size in memory %5dK", 530 (memory_total*HeapWordSize)/1024); 531 tty->print_cr("Total counted %5d", _symbols_counted); 532 tty->print_cr("Total removed %5d", _symbols_removed); 533 if (_symbols_counted > 0) { 534 tty->print_cr("Percent removed %3.2f", 535 ((float)_symbols_removed/(float)_symbols_counted)* 100); 536 } 537 tty->print_cr("Reference counts %5d", Symbol::_total_count); 538 tty->print_cr("Symbol arena size %5d used %5d", 539 arena()->size_in_bytes(), arena()->used()); 540 tty->print_cr("Histogram of symbol length:"); 541 tty->print_cr("%8s %5d", "Total ", total); 542 tty->print_cr("%8s %5d", "Maximum", max_symbols); 543 tty->print_cr("%8s %3.2f", "Average", 544 ((float) total / (float) the_table()->table_size())); 545 tty->print_cr("%s", "Histogram:"); 546 tty->print_cr(" %s %29s", "Length", "Number chains that length"); 547 for (i = 0; i < results_length; i++) { 548 if (results[i] > 0) { 549 tty->print_cr("%6d %10d", i, results[i]); 550 } 551 } 552 if (Verbose) { 553 int line_length = 70; 554 tty->print_cr("%s %30s", " Length", "Number chains that length"); 555 for (i = 0; i < results_length; i++) { 556 if (results[i] > 0) { 557 tty->print("%4d", i); 558 for (j = 0; (j < results[i]) && (j < line_length); j++) { 559 tty->print("%1s", "*"); 560 } 561 if (j == line_length) { 562 tty->print("%1s", "+"); 563 } 564 tty->cr(); 565 } 566 } 567 } 568 tty->print_cr(" %s %d: %d\n", "Number chains longer than", 569 results_length, out_of_range); 570} 571 572void SymbolTable::print() { 573 for (int i = 0; i < the_table()->table_size(); ++i) { 574 HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i); 575 HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i); 576 if (entry != NULL) { 577 while (entry != NULL) { 578 tty->print(PTR_FORMAT " ", entry->literal()); 579 entry->literal()->print(); 580 tty->print(" %d", entry->literal()->refcount()); 581 p = entry->next_addr(); 582 entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p); 583 } 584 tty->cr(); 585 } 586 } 587} 588#endif // PRODUCT 589