1 /* 2 * Copyright (c) 1997, 2012, 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/mutexLocker.hpp" 37 #include "utilities/hashtable.inline.hpp" 38 #include "utilities/numberSeq.hpp" 39 40 // -------------------------------------------------------------------------- 41 42 SymbolTable* SymbolTable::_the_table = NULL; 43 // Static arena for symbols that are not deallocated 44 Arena* SymbolTable::_arena = NULL; 45 bool SymbolTable::_needs_rehashing = false; 46 47 Symbol* SymbolTable::allocate_symbol(const u1* name, int len, bool c_heap, TRAPS) { 48 assert (len <= Symbol::max_length(), "should be checked by caller"); 49 50 Symbol* sym; 51 52 if (c_heap) { 53 // refcount starts as 1 54 assert(!DumpSharedSpaces, "never allocate to C heap"); 55 sym = new (len, THREAD) Symbol(name, len, 1); 56 assert(sym != NULL, "new should call vm_exit_out_of_memory if C_HEAP is exhausted"); 57 } else { 58 if (DumpSharedSpaces) { 59 sym = new (len, ClassLoaderData::the_null_class_loader_data(), THREAD) Symbol(name, len, -1); 60 } else { 61 sym = new (len, arena(), THREAD) Symbol(name, len, -1); 62 } 63 } 64 return sym; 65 } 66 67 void SymbolTable::initialize_symbols(int arena_alloc_size) { 68 // Initialize the arena for global symbols, size passed in depends on CDS. 69 if (arena_alloc_size == 0) { 70 _arena = new (mtSymbol) Arena(); 71 } else { 72 _arena = new (mtSymbol) Arena(arena_alloc_size); 73 } 74 } 75 76 // Call function for all symbols in the symbol table. 77 void SymbolTable::symbols_do(SymbolClosure *cl) { 78 const int n = the_table()->table_size(); 79 for (int i = 0; i < n; i++) { 80 for (HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i); 81 p != NULL; 82 p = p->next()) { 83 cl->do_symbol(p->literal_addr()); 84 } 85 } 86 } 87 88 int SymbolTable::symbols_removed = 0; 89 int SymbolTable::symbols_counted = 0; 90 91 // Remove unreferenced symbols from the symbol table 92 // This is done late during GC. 93 void SymbolTable::unlink() { 94 int removed = 0; 95 int total = 0; 96 size_t memory_total = 0; 97 for (int i = 0; i < the_table()->table_size(); ++i) { 98 HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i); 99 HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i); 100 while (entry != NULL) { 101 // Shared entries are normally at the end of the bucket and if we run into 102 // a shared entry, then there is nothing more to remove. However, if we 103 // have rehashed the table, then the shared entries are no longer at the 104 // end of the bucket. 105 if (entry->is_shared() && !use_alternate_hashcode()) { 106 break; 107 } 108 Symbol* s = entry->literal(); 109 memory_total += s->size(); 110 total++; 111 assert(s != NULL, "just checking"); 112 // If reference count is zero, remove. 113 if (s->refcount() == 0) { 114 assert(!entry->is_shared(), "shared entries should be kept live"); 115 delete s; 116 removed++; 117 *p = entry->next(); 118 the_table()->free_entry(entry); 119 } else { 120 p = entry->next_addr(); 121 } 122 // get next entry 123 entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p); 124 } 125 } 126 symbols_removed += removed; 127 symbols_counted += total; 128 // Exclude printing for normal PrintGCDetails because people parse 129 // this output. 130 if (PrintGCDetails && Verbose && WizardMode) { 131 gclog_or_tty->print(" [Symbols=%d size=" SIZE_FORMAT "K] ", total, 132 (memory_total*HeapWordSize)/1024); 133 } 134 } 135 136 // Create a new table and using alternate hash code, populate the new table 137 // with the existing strings. Set flag to use the alternate hash code afterwards. 138 void SymbolTable::rehash_table() { 139 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint"); 140 // This should never happen with -Xshare:dump but it might in testing mode. 141 if (DumpSharedSpaces) return; 142 // Create a new symbol table 143 SymbolTable* new_table = new SymbolTable(); 144 145 the_table()->move_to(new_table); 146 147 // Delete the table and buckets (entries are reused in new table). 148 delete _the_table; 149 // Don't check if we need rehashing until the table gets unbalanced again. 150 // Then rehash with a new global seed. 151 _needs_rehashing = false; 152 _the_table = new_table; 153 } 154 155 // Lookup a symbol in a bucket. 156 157 Symbol* SymbolTable::lookup(int index, const char* name, 158 int len, unsigned int hash) { 159 int count = 0; 160 for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) { 161 count++; // count all entries in this bucket, not just ones with same hash 162 if (e->hash() == hash) { 163 Symbol* sym = e->literal(); 164 if (sym->equals(name, len)) { 165 // something is referencing this symbol now. 166 sym->increment_refcount(); 167 return sym; 168 } 169 } 170 } 171 // If the bucket size is too deep check if this hash code is insufficient. 172 if (count >= BasicHashtable<mtSymbol>::rehash_count && !needs_rehashing()) { 173 _needs_rehashing = check_rehash_table(count); 174 } 175 return NULL; 176 } 177 178 // Pick hashing algorithm. 179 unsigned int SymbolTable::hash_symbol(const char* s, int len) { 180 return use_alternate_hashcode() ? 181 AltHashing::murmur3_32(seed(), (const jbyte*)s, len) : 182 java_lang_String::hash_code(s, len); 183 } 184 185 186 // We take care not to be blocking while holding the 187 // SymbolTable_lock. Otherwise, the system might deadlock, since the 188 // symboltable is used during compilation (VM_thread) The lock free 189 // synchronization is simplified by the fact that we do not delete 190 // entries in the symbol table during normal execution (only during 191 // safepoints). 192 193 Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) { 194 unsigned int hashValue = hash_symbol(name, len); 195 int index = the_table()->hash_to_index(hashValue); 196 197 Symbol* s = the_table()->lookup(index, name, len, hashValue); 198 199 // Found 200 if (s != NULL) return s; 201 202 // Grab SymbolTable_lock first. 203 MutexLocker ml(SymbolTable_lock, THREAD); 204 205 // Otherwise, add to symbol to table 206 return the_table()->basic_add(index, (u1*)name, len, hashValue, true, CHECK_NULL); 207 } 208 209 Symbol* SymbolTable::lookup(const Symbol* sym, int begin, int end, TRAPS) { 210 char* buffer; 211 int index, len; 212 unsigned int hashValue; 213 char* name; 214 { 215 debug_only(No_Safepoint_Verifier nsv;) 216 217 name = (char*)sym->base() + begin; 218 len = end - begin; 219 hashValue = hash_symbol(name, len); 220 index = the_table()->hash_to_index(hashValue); 221 Symbol* s = the_table()->lookup(index, name, len, hashValue); 222 223 // Found 224 if (s != NULL) return s; 225 } 226 227 // Otherwise, add to symbol to table. Copy to a C string first. 228 char stack_buf[128]; 229 ResourceMark rm(THREAD); 230 if (len <= 128) { 231 buffer = stack_buf; 232 } else { 233 buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len); 234 } 235 for (int i=0; i<len; i++) { 236 buffer[i] = name[i]; 237 } 238 // Make sure there is no safepoint in the code above since name can't move. 239 // We can't include the code in No_Safepoint_Verifier because of the 240 // ResourceMark. 241 242 // Grab SymbolTable_lock first. 243 MutexLocker ml(SymbolTable_lock, THREAD); 244 245 return the_table()->basic_add(index, (u1*)buffer, len, hashValue, true, CHECK_NULL); 246 } 247 248 Symbol* SymbolTable::lookup_only(const char* name, int len, 249 unsigned int& hash) { 250 hash = hash_symbol(name, len); 251 int index = the_table()->hash_to_index(hash); 252 253 Symbol* s = the_table()->lookup(index, name, len, hash); 254 return s; 255 } 256 257 // Look up the address of the literal in the SymbolTable for this Symbol* 258 // Do not create any new symbols 259 // Do not increment the reference count to keep this alive 260 Symbol** SymbolTable::lookup_symbol_addr(Symbol* sym){ 261 unsigned int hash = hash_symbol((char*)sym->bytes(), sym->utf8_length()); 262 int index = the_table()->hash_to_index(hash); 263 264 for (HashtableEntry<Symbol*, mtSymbol>* e = the_table()->bucket(index); e != NULL; e = e->next()) { 265 if (e->hash() == hash) { 266 Symbol* literal_sym = e->literal(); 267 if (sym == literal_sym) { 268 return e->literal_addr(); 269 } 270 } 271 } 272 return NULL; 273 } 274 275 // Suggestion: Push unicode-based lookup all the way into the hashing 276 // and probing logic, so there is no need for convert_to_utf8 until 277 // an actual new Symbol* is created. 278 Symbol* SymbolTable::lookup_unicode(const jchar* name, int utf16_length, TRAPS) { 279 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length); 280 char stack_buf[128]; 281 if (utf8_length < (int) sizeof(stack_buf)) { 282 char* chars = stack_buf; 283 UNICODE::convert_to_utf8(name, utf16_length, chars); 284 return lookup(chars, utf8_length, THREAD); 285 } else { 286 ResourceMark rm(THREAD); 287 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);; 288 UNICODE::convert_to_utf8(name, utf16_length, chars); 289 return lookup(chars, utf8_length, THREAD); 290 } 291 } 292 293 Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length, 294 unsigned int& hash) { 295 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length); 296 char stack_buf[128]; 297 if (utf8_length < (int) sizeof(stack_buf)) { 298 char* chars = stack_buf; 299 UNICODE::convert_to_utf8(name, utf16_length, chars); 300 return lookup_only(chars, utf8_length, hash); 301 } else { 302 ResourceMark rm; 303 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);; 304 UNICODE::convert_to_utf8(name, utf16_length, chars); 305 return lookup_only(chars, utf8_length, hash); 306 } 307 } 308 309 void SymbolTable::add(ClassLoaderData* loader_data, constantPoolHandle cp, 310 int names_count, 311 const char** names, int* lengths, int* cp_indices, 312 unsigned int* hashValues, TRAPS) { 313 // Grab SymbolTable_lock first. 314 MutexLocker ml(SymbolTable_lock, THREAD); 315 316 SymbolTable* table = the_table(); 317 bool added = table->basic_add(loader_data, cp, names_count, names, lengths, 318 cp_indices, hashValues, CHECK); 319 if (!added) { 320 // do it the hard way 321 for (int i=0; i<names_count; i++) { 322 int index = table->hash_to_index(hashValues[i]); 323 bool c_heap = !loader_data->is_the_null_class_loader_data(); 324 Symbol* sym = table->basic_add(index, (u1*)names[i], lengths[i], hashValues[i], c_heap, CHECK); 325 cp->symbol_at_put(cp_indices[i], sym); 326 } 327 } 328 } 329 330 Symbol* SymbolTable::new_permanent_symbol(const char* name, TRAPS) { 331 unsigned int hash; 332 Symbol* result = SymbolTable::lookup_only((char*)name, (int)strlen(name), hash); 333 if (result != NULL) { 334 return result; 335 } 336 // Grab SymbolTable_lock first. 337 MutexLocker ml(SymbolTable_lock, THREAD); 338 339 SymbolTable* table = the_table(); 340 int index = table->hash_to_index(hash); 341 return table->basic_add(index, (u1*)name, (int)strlen(name), hash, false, THREAD); 342 } 343 344 Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len, 345 unsigned int hashValue_arg, bool c_heap, TRAPS) { 346 assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(), 347 "proposed name of symbol must be stable"); 348 349 // Don't allow symbols to be created which cannot fit in a Symbol*. 350 if (len > Symbol::max_length()) { 351 THROW_MSG_0(vmSymbols::java_lang_InternalError(), 352 "name is too long to represent"); 353 } 354 355 // Cannot hit a safepoint in this function because the "this" pointer can move. 356 No_Safepoint_Verifier nsv; 357 358 // Check if the symbol table has been rehashed, if so, need to recalculate 359 // the hash value and index. 360 unsigned int hashValue; 361 int index; 362 if (use_alternate_hashcode()) { 363 hashValue = hash_symbol((const char*)name, len); 364 index = hash_to_index(hashValue); 365 } else { 366 hashValue = hashValue_arg; 367 index = index_arg; 368 } 369 370 // Since look-up was done lock-free, we need to check if another 371 // thread beat us in the race to insert the symbol. 372 Symbol* test = lookup(index, (char*)name, len, hashValue); 373 if (test != NULL) { 374 // A race occurred and another thread introduced the symbol. 375 assert(test->refcount() != 0, "lookup should have incremented the count"); 376 return test; 377 } 378 379 // Create a new symbol. 380 Symbol* sym = allocate_symbol(name, len, c_heap, CHECK_NULL); 381 assert(sym->equals((char*)name, len), "symbol must be properly initialized"); 382 383 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym); 384 add_entry(index, entry); 385 return sym; 386 } 387 388 // This version of basic_add adds symbols in batch from the constant pool 389 // parsing. 390 bool SymbolTable::basic_add(ClassLoaderData* loader_data, constantPoolHandle cp, 391 int names_count, 392 const char** names, int* lengths, 393 int* cp_indices, unsigned int* hashValues, 394 TRAPS) { 395 396 // Check symbol names are not too long. If any are too long, don't add any. 397 for (int i = 0; i< names_count; i++) { 398 if (lengths[i] > Symbol::max_length()) { 399 THROW_MSG_0(vmSymbols::java_lang_InternalError(), 400 "name is too long to represent"); 401 } 402 } 403 404 // Cannot hit a safepoint in this function because the "this" pointer can move. 405 No_Safepoint_Verifier nsv; 406 407 for (int i=0; i<names_count; i++) { 408 // Check if the symbol table has been rehashed, if so, need to recalculate 409 // the hash value. 410 unsigned int hashValue; 411 if (use_alternate_hashcode()) { 412 hashValue = hash_symbol(names[i], lengths[i]); 413 } else { 414 hashValue = hashValues[i]; 415 } 416 // Since look-up was done lock-free, we need to check if another 417 // thread beat us in the race to insert the symbol. 418 int index = hash_to_index(hashValue); 419 Symbol* test = lookup(index, names[i], lengths[i], hashValue); 420 if (test != NULL) { 421 // A race occurred and another thread introduced the symbol, this one 422 // will be dropped and collected. Use test instead. 423 cp->symbol_at_put(cp_indices[i], test); 424 assert(test->refcount() != 0, "lookup should have incremented the count"); 425 } else { 426 // Create a new symbol. The null class loader is never unloaded so these 427 // are allocated specially in a permanent arena. 428 bool c_heap = !loader_data->is_the_null_class_loader_data(); 429 Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], c_heap, CHECK_(false)); 430 assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized"); // why wouldn't it be??? 431 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym); 432 add_entry(index, entry); 433 cp->symbol_at_put(cp_indices[i], sym); 434 } 435 } 436 return true; 437 } 438 439 440 void SymbolTable::verify() { 441 for (int i = 0; i < the_table()->table_size(); ++i) { 442 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i); 443 for ( ; p != NULL; p = p->next()) { 444 Symbol* s = (Symbol*)(p->literal()); 445 guarantee(s != NULL, "symbol is NULL"); 446 unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length()); 447 guarantee(p->hash() == h, "broken hash in symbol table entry"); 448 guarantee(the_table()->hash_to_index(h) == i, 449 "wrong index in symbol table"); 450 } 451 } 452 } 453 454 void SymbolTable::dump(outputStream* st) { 455 NumberSeq summary; 456 for (int i = 0; i < the_table()->table_size(); ++i) { 457 int count = 0; 458 for (HashtableEntry<Symbol*, mtSymbol>* e = the_table()->bucket(i); 459 e != NULL; e = e->next()) { 460 count++; 461 } 462 summary.add((double)count); 463 } 464 st->print_cr("SymbolTable statistics:"); 465 st->print_cr("Number of buckets : %7d", summary.num()); 466 st->print_cr("Average bucket size : %7.0f", summary.avg()); 467 st->print_cr("Variance of bucket size : %7.0f", summary.variance()); 468 st->print_cr("Std. dev. of bucket size: %7.0f", summary.sd()); 469 st->print_cr("Maximum bucket size : %7.0f", summary.maximum()); 470 } 471 472 473 //--------------------------------------------------------------------------- 474 // Non-product code 475 476 #ifndef PRODUCT 477 478 void SymbolTable::print_histogram() { 479 MutexLocker ml(SymbolTable_lock); 480 const int results_length = 100; 481 int results[results_length]; 482 int i,j; 483 484 // initialize results to zero 485 for (j = 0; j < results_length; j++) { 486 results[j] = 0; 487 } 488 489 int total = 0; 490 int max_symbols = 0; 491 int out_of_range = 0; 492 int memory_total = 0; 493 int count = 0; 494 for (i = 0; i < the_table()->table_size(); i++) { 495 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i); 496 for ( ; p != NULL; p = p->next()) { 497 memory_total += p->literal()->size(); 498 count++; 499 int counter = p->literal()->utf8_length(); 500 total += counter; 501 if (counter < results_length) { 502 results[counter]++; 503 } else { 504 out_of_range++; 505 } 506 max_symbols = MAX2(max_symbols, counter); 507 } 508 } 509 tty->print_cr("Symbol Table:"); 510 tty->print_cr("Total number of symbols %5d", count); 511 tty->print_cr("Total size in memory %5dK", 512 (memory_total*HeapWordSize)/1024); 513 tty->print_cr("Total counted %5d", symbols_counted); 514 tty->print_cr("Total removed %5d", symbols_removed); 515 if (symbols_counted > 0) { 516 tty->print_cr("Percent removed %3.2f", 517 ((float)symbols_removed/(float)symbols_counted)* 100); 518 } 519 tty->print_cr("Reference counts %5d", Symbol::_total_count); 520 tty->print_cr("Symbol arena size %5d used %5d", 521 arena()->size_in_bytes(), arena()->used()); 522 tty->print_cr("Histogram of symbol length:"); 523 tty->print_cr("%8s %5d", "Total ", total); 524 tty->print_cr("%8s %5d", "Maximum", max_symbols); 525 tty->print_cr("%8s %3.2f", "Average", 526 ((float) total / (float) the_table()->table_size())); 527 tty->print_cr("%s", "Histogram:"); 528 tty->print_cr(" %s %29s", "Length", "Number chains that length"); 529 for (i = 0; i < results_length; i++) { 530 if (results[i] > 0) { 531 tty->print_cr("%6d %10d", i, results[i]); 532 } 533 } 534 if (Verbose) { 535 int line_length = 70; 536 tty->print_cr("%s %30s", " Length", "Number chains that length"); 537 for (i = 0; i < results_length; i++) { 538 if (results[i] > 0) { 539 tty->print("%4d", i); 540 for (j = 0; (j < results[i]) && (j < line_length); j++) { 541 tty->print("%1s", "*"); 542 } 543 if (j == line_length) { 544 tty->print("%1s", "+"); 545 } 546 tty->cr(); 547 } 548 } 549 } 550 tty->print_cr(" %s %d: %d\n", "Number chains longer than", 551 results_length, out_of_range); 552 } 553 554 void SymbolTable::print() { 555 for (int i = 0; i < the_table()->table_size(); ++i) { 556 HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i); 557 HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i); 558 if (entry != NULL) { 559 while (entry != NULL) { 560 tty->print(PTR_FORMAT " ", entry->literal()); 561 entry->literal()->print(); 562 tty->print(" %d", entry->literal()->refcount()); 563 p = entry->next_addr(); 564 entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p); 565 } 566 tty->cr(); 567 } 568 } 569 } 570 #endif // PRODUCT 571 572 // -------------------------------------------------------------------------- 573 574 #ifdef ASSERT 575 class StableMemoryChecker : public StackObj { 576 enum { _bufsize = wordSize*4 }; 577 578 address _region; 579 jint _size; 580 u1 _save_buf[_bufsize]; 581 582 int sample(u1* save_buf) { 583 if (_size <= _bufsize) { 584 memcpy(save_buf, _region, _size); 585 return _size; 586 } else { 587 // copy head and tail 588 memcpy(&save_buf[0], _region, _bufsize/2); 589 memcpy(&save_buf[_bufsize/2], _region + _size - _bufsize/2, _bufsize/2); 590 return (_bufsize/2)*2; 591 } 592 } 593 594 public: 595 StableMemoryChecker(const void* region, jint size) { 596 _region = (address) region; 597 _size = size; 598 sample(_save_buf); 599 } 600 601 bool verify() { 602 u1 check_buf[sizeof(_save_buf)]; 603 int check_size = sample(check_buf); 604 return (0 == memcmp(_save_buf, check_buf, check_size)); 605 } 606 607 void set_region(const void* region) { _region = (address) region; } 608 }; 609 #endif 610 611 612 // -------------------------------------------------------------------------- 613 StringTable* StringTable::_the_table = NULL; 614 615 bool StringTable::_needs_rehashing = false; 616 617 // Pick hashing algorithm 618 unsigned int StringTable::hash_string(const jchar* s, int len) { 619 return use_alternate_hashcode() ? AltHashing::murmur3_32(seed(), s, len) : 620 java_lang_String::hash_code(s, len); 621 } 622 623 oop StringTable::lookup(int index, jchar* name, 624 int len, unsigned int hash) { 625 int count = 0; 626 for (HashtableEntry<oop, mtSymbol>* l = bucket(index); l != NULL; l = l->next()) { 627 count++; 628 if (l->hash() == hash) { 629 if (java_lang_String::equals(l->literal(), name, len)) { 630 return l->literal(); 631 } 632 } 633 } 634 // If the bucket size is too deep check if this hash code is insufficient. 635 if (count >= BasicHashtable<mtSymbol>::rehash_count && !needs_rehashing()) { 636 _needs_rehashing = check_rehash_table(count); 637 } 638 return NULL; 639 } 640 641 642 oop StringTable::basic_add(int index_arg, Handle string, jchar* name, 643 int len, unsigned int hashValue_arg, TRAPS) { 644 645 assert(java_lang_String::equals(string(), name, len), 646 "string must be properly initialized"); 647 // Cannot hit a safepoint in this function because the "this" pointer can move. 648 No_Safepoint_Verifier nsv; 649 650 // Check if the symbol table has been rehashed, if so, need to recalculate 651 // the hash value and index before second lookup. 652 unsigned int hashValue; 653 int index; 654 if (use_alternate_hashcode()) { 655 hashValue = hash_string(name, len); 656 index = hash_to_index(hashValue); 657 } else { 658 hashValue = hashValue_arg; 659 index = index_arg; 660 } 661 662 // Since look-up was done lock-free, we need to check if another 663 // thread beat us in the race to insert the symbol. 664 665 oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int) 666 if (test != NULL) { 667 // Entry already added 668 return test; 669 } 670 671 HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string()); 672 add_entry(index, entry); 673 return string(); 674 } 675 676 677 oop StringTable::lookup(Symbol* symbol) { 678 ResourceMark rm; 679 int length; 680 jchar* chars = symbol->as_unicode(length); 681 unsigned int hashValue = hash_string(chars, length); 682 int index = the_table()->hash_to_index(hashValue); 683 return the_table()->lookup(index, chars, length, hashValue); 684 } 685 686 687 oop StringTable::intern(Handle string_or_null, jchar* name, 688 int len, TRAPS) { 689 unsigned int hashValue = hash_string(name, len); 690 int index = the_table()->hash_to_index(hashValue); 691 oop found_string = the_table()->lookup(index, name, len, hashValue); 692 693 // Found 694 if (found_string != NULL) return found_string; 695 696 debug_only(StableMemoryChecker smc(name, len * sizeof(name[0]))); 697 assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(), 698 "proposed name of symbol must be stable"); 699 700 Handle string; 701 // try to reuse the string if possible 702 if (!string_or_null.is_null()) { 703 string = string_or_null; 704 } else { 705 string = java_lang_String::create_from_unicode(name, len, CHECK_NULL); 706 } 707 708 // Grab the StringTable_lock before getting the_table() because it could 709 // change at safepoint. 710 MutexLocker ml(StringTable_lock, THREAD); 711 712 // Otherwise, add to symbol to table 713 return the_table()->basic_add(index, string, name, len, 714 hashValue, CHECK_NULL); 715 } 716 717 oop StringTable::intern(Symbol* symbol, TRAPS) { 718 if (symbol == NULL) return NULL; 719 ResourceMark rm(THREAD); 720 int length; 721 jchar* chars = symbol->as_unicode(length); 722 Handle string; 723 oop result = intern(string, chars, length, CHECK_NULL); 724 return result; 725 } 726 727 728 oop StringTable::intern(oop string, TRAPS) 729 { 730 if (string == NULL) return NULL; 731 ResourceMark rm(THREAD); 732 int length; 733 Handle h_string (THREAD, string); 734 jchar* chars = java_lang_String::as_unicode_string(string, length); 735 oop result = intern(h_string, chars, length, CHECK_NULL); 736 return result; 737 } 738 739 740 oop StringTable::intern(const char* utf8_string, TRAPS) { 741 if (utf8_string == NULL) return NULL; 742 ResourceMark rm(THREAD); 743 int length = UTF8::unicode_length(utf8_string); 744 jchar* chars = NEW_RESOURCE_ARRAY(jchar, length); 745 UTF8::convert_to_unicode(utf8_string, chars, length); 746 Handle string; 747 oop result = intern(string, chars, length, CHECK_NULL); 748 return result; 749 } 750 751 void StringTable::unlink(BoolObjectClosure* is_alive) { 752 // Readers of the table are unlocked, so we should only be removing 753 // entries at a safepoint. 754 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint"); 755 for (int i = 0; i < the_table()->table_size(); ++i) { 756 HashtableEntry<oop, mtSymbol>** p = the_table()->bucket_addr(i); 757 HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i); 758 while (entry != NULL) { 759 // Shared entries are normally at the end of the bucket and if we run into 760 // a shared entry, then there is nothing more to remove. However, if we 761 // have rehashed the table, then the shared entries are no longer at the 762 // end of the bucket. 763 if (entry->is_shared() && !use_alternate_hashcode()) { 764 break; 765 } 766 assert(entry->literal() != NULL, "just checking"); 767 if (entry->is_shared() || is_alive->do_object_b(entry->literal())) { 768 p = entry->next_addr(); 769 } else { 770 *p = entry->next(); 771 the_table()->free_entry(entry); 772 } 773 entry = (HashtableEntry<oop, mtSymbol>*)HashtableEntry<oop, mtSymbol>::make_ptr(*p); 774 } 775 } 776 } 777 778 void StringTable::oops_do(OopClosure* f) { 779 for (int i = 0; i < the_table()->table_size(); ++i) { 780 HashtableEntry<oop, mtSymbol>** p = the_table()->bucket_addr(i); 781 HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i); 782 while (entry != NULL) { 783 f->do_oop((oop*)entry->literal_addr()); 784 785 // Did the closure remove the literal from the table? 786 if (entry->literal() == NULL) { 787 assert(!entry->is_shared(), "immutable hashtable entry?"); 788 *p = entry->next(); 789 the_table()->free_entry(entry); 790 } else { 791 p = entry->next_addr(); 792 } 793 entry = (HashtableEntry<oop, mtSymbol>*)HashtableEntry<oop, mtSymbol>::make_ptr(*p); 794 } 795 } 796 } 797 798 void StringTable::verify() { 799 for (int i = 0; i < the_table()->table_size(); ++i) { 800 HashtableEntry<oop, mtSymbol>* p = the_table()->bucket(i); 801 for ( ; p != NULL; p = p->next()) { 802 oop s = p->literal(); 803 guarantee(s != NULL, "interned string is NULL"); 804 unsigned int h = java_lang_String::hash_string(s); 805 guarantee(p->hash() == h, "broken hash in string table entry"); 806 guarantee(the_table()->hash_to_index(h) == i, 807 "wrong index in string table"); 808 } 809 } 810 } 811 812 void StringTable::dump(outputStream* st) { 813 NumberSeq summary; 814 for (int i = 0; i < the_table()->table_size(); ++i) { 815 HashtableEntry<oop, mtSymbol>* p = the_table()->bucket(i); 816 int count = 0; 817 for ( ; p != NULL; p = p->next()) { 818 count++; 819 } 820 summary.add((double)count); 821 } 822 st->print_cr("StringTable statistics:"); 823 st->print_cr("Number of buckets : %7d", summary.num()); 824 st->print_cr("Average bucket size : %7.0f", summary.avg()); 825 st->print_cr("Variance of bucket size : %7.0f", summary.variance()); 826 st->print_cr("Std. dev. of bucket size: %7.0f", summary.sd()); 827 st->print_cr("Maximum bucket size : %7.0f", summary.maximum()); 828 } 829 830 831 // Create a new table and using alternate hash code, populate the new table 832 // with the existing strings. Set flag to use the alternate hash code afterwards. 833 void StringTable::rehash_table() { 834 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint"); 835 // This should never happen with -Xshare:dump but it might in testing mode. 836 if (DumpSharedSpaces) return; 837 StringTable* new_table = new StringTable(); 838 839 // Rehash the table 840 the_table()->move_to(new_table); 841 842 // Delete the table and buckets (entries are reused in new table). 843 delete _the_table; 844 // Don't check if we need rehashing until the table gets unbalanced again. 845 // Then rehash with a new global seed. 846 _needs_rehashing = false; 847 _the_table = new_table; 848 }