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
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);
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;
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
|
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "classfile/altHashing.hpp"
27 #include "classfile/compactHashtable.hpp"
28 #include "classfile/javaClasses.hpp"
29 #include "classfile/symbolTable.hpp"
30 #include "classfile/systemDictionary.hpp"
31 #include "gc_interface/collectedHeap.inline.hpp"
32 #include "memory/allocation.inline.hpp"
33 #include "memory/filemap.hpp"
34 #include "memory/gcLocker.inline.hpp"
35 #include "oops/oop.inline.hpp"
36 #include "oops/oop.inline2.hpp"
37 #include "runtime/atomic.inline.hpp"
38 #include "runtime/mutexLocker.hpp"
39 #include "utilities/hashtable.inline.hpp"
40
41 PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
42
43 // --------------------------------------------------------------------------
44 // the number of buckets a thread claims
45 const int ClaimChunkSize = 32;
46
47 SymbolTable* SymbolTable::_the_table = NULL;
48 // Static arena for symbols that are not deallocated
49 Arena* SymbolTable::_arena = NULL;
50 bool SymbolTable::_needs_rehashing = false;
51 bool SymbolTable::_lookup_shared_first = false;
52
53 CompactHashtable<Symbol*, char> SymbolTable::_shared_table;
54
55 Symbol* SymbolTable::allocate_symbol(const u1* name, int len, bool c_heap, TRAPS) {
56 assert (len <= Symbol::max_length(), "should be checked by caller");
57
58 Symbol* sym;
59
60 if (DumpSharedSpaces) {
61 // Allocate all symbols to CLD shared metaspace
62 sym = new (len, ClassLoaderData::the_null_class_loader_data(), THREAD) Symbol(name, len, -1);
63 } else if (c_heap) {
64 // refcount starts as 1
65 sym = new (len, THREAD) Symbol(name, len, 1);
66 assert(sym != NULL, "new should call vm_exit_out_of_memory if C_HEAP is exhausted");
67 } else {
68 // Allocate to global arena
69 sym = new (len, arena(), THREAD) Symbol(name, len, -1);
70 }
71 return sym;
72 }
73
173 // with the existing strings. Set flag to use the alternate hash code afterwards.
174 void SymbolTable::rehash_table() {
175 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
176 // This should never happen with -Xshare:dump but it might in testing mode.
177 if (DumpSharedSpaces) return;
178 // Create a new symbol table
179 SymbolTable* new_table = new SymbolTable();
180
181 the_table()->move_to(new_table);
182
183 // Delete the table and buckets (entries are reused in new table).
184 delete _the_table;
185 // Don't check if we need rehashing until the table gets unbalanced again.
186 // Then rehash with a new global seed.
187 _needs_rehashing = false;
188 _the_table = new_table;
189 }
190
191 // Lookup a symbol in a bucket.
192
193 Symbol* SymbolTable::lookup_dynamic(int index, const char* name,
194 int len, unsigned int hash) {
195 int count = 0;
196 for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) {
197 count++; // count all entries in this bucket, not just ones with same hash
198 if (e->hash() == hash) {
199 Symbol* sym = e->literal();
200 if (sym->equals(name, len)) {
201 // something is referencing this symbol now.
202 sym->increment_refcount();
203 return sym;
204 }
205 }
206 }
207 // If the bucket size is too deep check if this hash code is insufficient.
208 if (count >= rehash_count && !needs_rehashing()) {
209 _needs_rehashing = check_rehash_table(count);
210 }
211 return NULL;
212 }
213
214 Symbol* SymbolTable::lookup_shared(const char* name,
215 int len, unsigned int hash) {
216 return _shared_table.lookup(name, hash, len);
217 }
218
219 Symbol* SymbolTable::lookup(int index, const char* name,
220 int len, unsigned int hash) {
221 Symbol* sym;
222 if (_lookup_shared_first) {
223 sym = lookup_shared(name, len, hash);
224 if (sym != NULL) {
225 return sym;
226 }
227 _lookup_shared_first = false;
228 return lookup_dynamic(index, name, len, hash);
229 } else {
230 sym = lookup_dynamic(index, name, len, hash);
231 if (sym != NULL) {
232 return sym;
233 }
234 sym = lookup_shared(name, len, hash);
235 if (sym != NULL) {
236 _lookup_shared_first = true;
237 }
238 return sym;
239 }
240 }
241
242 // Pick hashing algorithm.
243 unsigned int SymbolTable::hash_symbol(const char* s, int len) {
244 return use_alternate_hashcode() ?
245 AltHashing::murmur3_32(seed(), (const jbyte*)s, len) :
246 java_lang_String::hash_code(s, len);
247 }
248
249
250 // We take care not to be blocking while holding the
251 // SymbolTable_lock. Otherwise, the system might deadlock, since the
252 // symboltable is used during compilation (VM_thread) The lock free
253 // synchronization is simplified by the fact that we do not delete
254 // entries in the symbol table during normal execution (only during
255 // safepoints).
256
257 Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) {
258 unsigned int hashValue = hash_symbol(name, len);
259 int index = the_table()->hash_to_index(hashValue);
260
261 Symbol* s = the_table()->lookup(index, name, len, hashValue);
498 }
499 }
500 return true;
501 }
502
503
504 void SymbolTable::verify() {
505 for (int i = 0; i < the_table()->table_size(); ++i) {
506 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
507 for ( ; p != NULL; p = p->next()) {
508 Symbol* s = (Symbol*)(p->literal());
509 guarantee(s != NULL, "symbol is NULL");
510 unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length());
511 guarantee(p->hash() == h, "broken hash in symbol table entry");
512 guarantee(the_table()->hash_to_index(h) == i,
513 "wrong index in symbol table");
514 }
515 }
516 }
517
518 void SymbolTable::dump(outputStream* st, bool verbose) {
519 if (!verbose) {
520 the_table()->dump_table(st, "SymbolTable");
521 } else {
522 st->print_cr("VERSION: 1.0");
523 for (int i = 0; i < the_table()->table_size(); ++i) {
524 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
525 for ( ; p != NULL; p = p->next()) {
526 Symbol* s = (Symbol*)(p->literal());
527 const char* utf8_string = (const char*)s->bytes();
528 int utf8_length = s->utf8_length();
529 st->print("%d %d: ", utf8_length, s->refcount());
530 HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
531 st->cr();
532 }
533 }
534 }
535 }
536
537 bool SymbolTable::copy_compact_table(char** top, char*end) {
538 #if INCLUDE_CDS
539 CompactHashtableWriter ch_table("symbol", the_table()->number_of_entries(),
540 &MetaspaceShared::stats()->symbol);
541 if (*top + ch_table.get_required_bytes() > end) {
542 // not enough space left
543 return false;
544 }
545
546 for (int i = 0; i < the_table()->table_size(); ++i) {
547 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
548 for ( ; p != NULL; p = p->next()) {
549 Symbol* s = (Symbol*)(p->literal());
550 unsigned int fixed_hash = hash_symbol((char*)s->bytes(), s->utf8_length());
551 assert(fixed_hash == p->hash(), "must not rehash during dumping");
552 ch_table.add(fixed_hash, s);
553 }
554 }
555
556 char* old_top = *top;
557 ch_table.dump(top, end);
558
559 *top = (char*)align_pointer_up(*top, sizeof(void*));
560 #endif
561 return true;
562 }
563
564 const char* SymbolTable::init_shared_table(const char* buffer) {
565 const char* end = _shared_table.init(buffer);
566 return (const char*)align_pointer_up(end, sizeof(void*));
567 }
568
569 //---------------------------------------------------------------------------
570 // Non-product code
571
572 #ifndef PRODUCT
573
574 void SymbolTable::print_histogram() {
575 MutexLocker ml(SymbolTable_lock);
576 const int results_length = 100;
577 int counts[results_length];
578 int sizes[results_length];
579 int i,j;
580
581 // initialize results to zero
582 for (j = 0; j < results_length; j++) {
583 counts[j] = 0;
584 sizes[j] = 0;
585 }
586
587 int total_size = 0;
635 out_of_range_count, (out_of_range_size*HeapWordSize)/1024);
636 }
637
638 void SymbolTable::print() {
639 for (int i = 0; i < the_table()->table_size(); ++i) {
640 HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i);
641 HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i);
642 if (entry != NULL) {
643 while (entry != NULL) {
644 tty->print(PTR_FORMAT " ", entry->literal());
645 entry->literal()->print();
646 tty->print(" %d", entry->literal()->refcount());
647 p = entry->next_addr();
648 entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p);
649 }
650 tty->cr();
651 }
652 }
653 }
654 #endif // PRODUCT
655
656
657 // Utility for dumping symbols
658 SymboltableDCmd::SymboltableDCmd(outputStream* output, bool heap) :
659 DCmdWithParser(output, heap),
660 _verbose("-verbose", "Dump the content of each symbol in the table",
661 "BOOLEAN", false, "false") {
662 _dcmdparser.add_dcmd_option(&_verbose);
663 }
664
665 void SymboltableDCmd::execute(DCmdSource source, TRAPS) {
666 VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpSymbols,
667 _verbose.value());
668 VMThread::execute(&dumper);
669 }
670
671 int SymboltableDCmd::num_arguments() {
672 ResourceMark rm;
673 SymboltableDCmd* dcmd = new SymboltableDCmd(NULL, false);
674 if (dcmd != NULL) {
675 DCmdMark mark(dcmd);
676 return dcmd->_dcmdparser.num_arguments();
677 } else {
678 return 0;
679 }
680 }
|