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 40 PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC 41 42 // -------------------------------------------------------------------------- 43 // the number of buckets a thread claims 44 const int ClaimChunkSize = 32; 45 46 SymbolTable* SymbolTable::_the_table = NULL; 47 // Static arena for symbols that are not deallocated 48 Arena* SymbolTable::_arena = NULL; 49 bool SymbolTable::_needs_rehashing = false; 50 51 Symbol* 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 70 void 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. 80 void 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 91 int SymbolTable::_symbols_removed = 0; 92 int SymbolTable::_symbols_counted = 0; 93 volatile int SymbolTable::_parallel_claimed_idx = 0; 94 95 void 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. 129 void 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 142 void 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. 170 void 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 189 Symbol* 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 >= rehash_count && !needs_rehashing()) { 205 _needs_rehashing = check_rehash_table(count); 206 } 207 return NULL; 208 } 209 210 // Pick hashing algorithm. 211 unsigned 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 225 Symbol* 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 241 Symbol* 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 280 Symbol* 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 292 Symbol** 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. 310 Symbol* 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 325 Symbol* 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 341 void 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 362 Symbol* 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 376 Symbol* 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. 422 bool 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 472 void 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 486 void SymbolTable::dump(outputStream* st) { 487 the_table()->dump_table(st, "SymbolTable"); 488 } 489 490 491 //--------------------------------------------------------------------------- 492 // Non-product code 493 494 #ifndef PRODUCT 495 496 void SymbolTable::print_histogram() { 497 MutexLocker ml(SymbolTable_lock); 498 const int results_length = 100; 499 int counts[results_length]; 500 int sizes[results_length]; 501 int i,j; 502 503 // initialize results to zero 504 for (j = 0; j < results_length; j++) { 505 counts[j] = 0; 506 sizes[j] = 0; 507 } 508 509 int total_size = 0; 510 int total_count = 0; 511 int total_length = 0; 512 int max_length = 0; 513 int out_of_range_count = 0; 514 int out_of_range_size = 0; 515 for (i = 0; i < the_table()->table_size(); i++) { 516 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i); 517 for ( ; p != NULL; p = p->next()) { 518 int size = p->literal()->size(); 519 int len = p->literal()->utf8_length(); 520 if (len < results_length) { 521 counts[len]++; 522 sizes[len] += size; 523 } else { 524 out_of_range_count++; 525 out_of_range_size += size; 526 } 527 total_count++; 528 total_size += size; 529 total_length += len; 530 max_length = MAX2(max_length, len); 531 } 532 } 533 tty->print_cr("Symbol Table Histogram:"); 534 tty->print_cr(" Total number of symbols %7d", total_count); 535 tty->print_cr(" Total size in memory %7dK", 536 (total_size*HeapWordSize)/1024); 537 tty->print_cr(" Total counted %7d", _symbols_counted); 538 tty->print_cr(" Total removed %7d", _symbols_removed); 539 if (_symbols_counted > 0) { 540 tty->print_cr(" Percent removed %3.2f", 541 ((float)_symbols_removed/(float)_symbols_counted)* 100); 542 } 543 tty->print_cr(" Reference counts %7d", Symbol::_total_count); 544 tty->print_cr(" Symbol arena used %7dK", arena()->used()/1024); 545 tty->print_cr(" Symbol arena size %7dK", arena()->size_in_bytes()/1024); 546 tty->print_cr(" Total symbol length %7d", total_length); 547 tty->print_cr(" Maximum symbol length %7d", max_length); 548 tty->print_cr(" Average symbol length %7.2f", ((float) total_length / (float) total_count)); 549 tty->print_cr(" Symbol length histogram:"); 550 tty->print_cr(" %6s %10s %10s", "Length", "#Symbols", "Size"); 551 for (i = 0; i < results_length; i++) { 552 if (counts[i] > 0) { 553 tty->print_cr(" %6d %10d %10dK", i, counts[i], (sizes[i]*HeapWordSize)/1024); 554 } 555 } 556 tty->print_cr(" >=%6d %10d %10dK\n", results_length, 557 out_of_range_count, (out_of_range_size*HeapWordSize)/1024); 558 } 559 560 void SymbolTable::print() { 561 for (int i = 0; i < the_table()->table_size(); ++i) { 562 HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i); 563 HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i); 564 if (entry != NULL) { 565 while (entry != NULL) { 566 tty->print(PTR_FORMAT " ", entry->literal()); 567 entry->literal()->print(); 568 tty->print(" %d", entry->literal()->refcount()); 569 p = entry->next_addr(); 570 entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p); 571 } 572 tty->cr(); 573 } 574 } 575 } 576 #endif // PRODUCT