1 /*
2 * Copyright (c) 1997, 2013, 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
39 // --------------------------------------------------------------------------
40
41 // the number of buckets a thread claims
42 const int ClaimChunkSize = 32;
43
44 SymbolTable* SymbolTable::_the_table = NULL;
45 // Static arena for symbols that are not deallocated
46 Arena* SymbolTable::_arena = NULL;
47 bool SymbolTable::_needs_rehashing = false;
48
49 Symbol* SymbolTable::allocate_symbol(const u1* name, int len, bool c_heap, TRAPS) {
50 assert (len <= Symbol::max_length(), "should be checked by caller");
51
52 Symbol* sym;
53
54 if (DumpSharedSpaces) {
55 // Allocate all symbols to CLD shared metaspace
56 sym = new (len, ClassLoaderData::the_null_class_loader_data(), THREAD) Symbol(name, len, -1);
57 } else if (c_heap) {
58 // refcount starts as 1
59 sym = new (len, THREAD) Symbol(name, len, 1);
60 assert(sym != NULL, "new should call vm_exit_out_of_memory if C_HEAP is exhausted");
61 } else {
62 // Allocate to global arena
63 sym = new (len, arena(), THREAD) Symbol(name, len, -1);
64 }
65 return sym;
66 }
67
68 void SymbolTable::initialize_symbols(int arena_alloc_size) {
69 // Initialize the arena for global symbols, size passed in depends on CDS.
70 if (arena_alloc_size == 0) {
71 _arena = new (mtSymbol) Arena();
72 } else {
73 _arena = new (mtSymbol) Arena(arena_alloc_size);
74 }
75 }
76
77 // Call function for all symbols in the symbol table.
78 void SymbolTable::symbols_do(SymbolClosure *cl) {
79 const int n = the_table()->table_size();
80 for (int i = 0; i < n; i++) {
81 for (HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
82 p != NULL;
83 p = p->next()) {
84 cl->do_symbol(p->literal_addr());
85 }
86 }
87 }
88
89 int SymbolTable::_symbols_removed = 0;
90 int SymbolTable::_symbols_counted = 0;
91 volatile int SymbolTable::_parallel_claimed_idx = 0;
92
93 void SymbolTable::buckets_unlink(int start_idx, int end_idx, int* processed, int* removed, size_t* memory_total) {
94 for (int i = start_idx; i < end_idx; ++i) {
95 HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i);
96 HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i);
97 while (entry != NULL) {
98 // Shared entries are normally at the end of the bucket and if we run into
99 // a shared entry, then there is nothing more to remove. However, if we
100 // have rehashed the table, then the shared entries are no longer at the
101 // end of the bucket.
102 if (entry->is_shared() && !use_alternate_hashcode()) {
103 break;
104 }
105 Symbol* s = entry->literal();
106 (*memory_total) += s->size();
107 (*processed)++;
108 assert(s != NULL, "just checking");
109 // If reference count is zero, remove.
110 if (s->refcount() == 0) {
111 assert(!entry->is_shared(), "shared entries should be kept live");
112 delete s;
113 (*removed)++;
114 *p = entry->next();
115 the_table()->free_entry(entry);
116 } else {
117 p = entry->next_addr();
118 }
119 // get next entry
120 entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p);
121 }
122 }
123 }
124
125 // Remove unreferenced symbols from the symbol table
126 // This is done late during GC.
127 void SymbolTable::unlink(int* processed, int* removed) {
128 size_t memory_total = 0;
129 buckets_unlink(0, the_table()->table_size(), processed, removed, &memory_total);
130 _symbols_removed += *removed;
131 _symbols_counted += *processed;
132 // Exclude printing for normal PrintGCDetails because people parse
133 // this output.
134 if (PrintGCDetails && Verbose && WizardMode) {
135 gclog_or_tty->print(" [Symbols=%d size=" SIZE_FORMAT "K] ", *processed,
136 (memory_total*HeapWordSize)/1024);
137 }
138 }
139
140 void SymbolTable::possibly_parallel_unlink(int* processed, int* removed) {
141 const int limit = the_table()->table_size();
142
143 size_t memory_total = 0;
144
145 for (;;) {
146 // Grab next set of buckets to scan
147 int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
148 if (start_idx >= limit) {
149 // End of table
150 break;
151 }
152
153 int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
154 buckets_unlink(start_idx, end_idx, processed, removed, &memory_total);
155 }
156 Atomic::add(*processed, &_symbols_counted);
157 Atomic::add(*removed, &_symbols_removed);
158 // Exclude printing for normal PrintGCDetails because people parse
159 // this output.
160 if (PrintGCDetails && Verbose && WizardMode) {
161 gclog_or_tty->print(" [Symbols: scanned=%d removed=%d size=" SIZE_FORMAT "K] ", *processed, *removed,
162 (memory_total*HeapWordSize)/1024);
163 }
164 }
165
166 // Create a new table and using alternate hash code, populate the new table
167 // with the existing strings. Set flag to use the alternate hash code afterwards.
168 void SymbolTable::rehash_table() {
169 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
170 // This should never happen with -Xshare:dump but it might in testing mode.
171 if (DumpSharedSpaces) return;
172 // Create a new symbol table
173 SymbolTable* new_table = new SymbolTable();
174
175 the_table()->move_to(new_table);
176
177 // Delete the table and buckets (entries are reused in new table).
178 delete _the_table;
179 // Don't check if we need rehashing until the table gets unbalanced again.
180 // Then rehash with a new global seed.
181 _needs_rehashing = false;
182 _the_table = new_table;
183 }
184
185 // Lookup a symbol in a bucket.
186
187 Symbol* SymbolTable::lookup(int index, const char* name,
188 int len, unsigned int hash) {
189 int count = 0;
190 for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) {
191 count++; // count all entries in this bucket, not just ones with same hash
192 if (e->hash() == hash) {
193 Symbol* sym = e->literal();
194 if (sym->equals(name, len)) {
195 // something is referencing this symbol now.
196 sym->increment_refcount();
197 return sym;
198 }
199 }
200 }
201 // If the bucket size is too deep check if this hash code is insufficient.
202 if (count >= BasicHashtable<mtSymbol>::rehash_count && !needs_rehashing()) {
203 _needs_rehashing = check_rehash_table(count);
204 }
205 return NULL;
206 }
207
208 // Pick hashing algorithm.
209 unsigned int SymbolTable::hash_symbol(const char* s, int len) {
210 return use_alternate_hashcode() ?
211 AltHashing::murmur3_32(seed(), (const jbyte*)s, len) :
212 java_lang_String::hash_code(s, len);
213 }
214
215
216 // We take care not to be blocking while holding the
217 // SymbolTable_lock. Otherwise, the system might deadlock, since the
218 // symboltable is used during compilation (VM_thread) The lock free
219 // synchronization is simplified by the fact that we do not delete
220 // entries in the symbol table during normal execution (only during
221 // safepoints).
222
223 Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) {
224 unsigned int hashValue = hash_symbol(name, len);
225 int index = the_table()->hash_to_index(hashValue);
226
227 Symbol* s = the_table()->lookup(index, name, len, hashValue);
228
229 // Found
230 if (s != NULL) return s;
231
232 // Grab SymbolTable_lock first.
233 MutexLocker ml(SymbolTable_lock, THREAD);
234
235 // Otherwise, add to symbol to table
236 return the_table()->basic_add(index, (u1*)name, len, hashValue, true, CHECK_NULL);
237 }
238
239 Symbol* SymbolTable::lookup(const Symbol* sym, int begin, int end, TRAPS) {
240 char* buffer;
241 int index, len;
242 unsigned int hashValue;
243 char* name;
244 {
245 debug_only(No_Safepoint_Verifier nsv;)
246
247 name = (char*)sym->base() + begin;
248 len = end - begin;
249 hashValue = hash_symbol(name, len);
250 index = the_table()->hash_to_index(hashValue);
251 Symbol* s = the_table()->lookup(index, name, len, hashValue);
252
253 // Found
254 if (s != NULL) return s;
255 }
256
257 // Otherwise, add to symbol to table. Copy to a C string first.
258 char stack_buf[128];
259 ResourceMark rm(THREAD);
260 if (len <= 128) {
261 buffer = stack_buf;
262 } else {
263 buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len);
264 }
265 for (int i=0; i<len; i++) {
266 buffer[i] = name[i];
267 }
268 // Make sure there is no safepoint in the code above since name can't move.
269 // We can't include the code in No_Safepoint_Verifier because of the
270 // ResourceMark.
271
272 // Grab SymbolTable_lock first.
273 MutexLocker ml(SymbolTable_lock, THREAD);
274
275 return the_table()->basic_add(index, (u1*)buffer, len, hashValue, true, CHECK_NULL);
276 }
277
278 Symbol* SymbolTable::lookup_only(const char* name, int len,
279 unsigned int& hash) {
280 hash = hash_symbol(name, len);
281 int index = the_table()->hash_to_index(hash);
282
283 Symbol* s = the_table()->lookup(index, name, len, hash);
284 return s;
285 }
286
287 // Look up the address of the literal in the SymbolTable for this Symbol*
288 // Do not create any new symbols
289 // Do not increment the reference count to keep this alive
290 Symbol** SymbolTable::lookup_symbol_addr(Symbol* sym){
291 unsigned int hash = hash_symbol((char*)sym->bytes(), sym->utf8_length());
292 int index = the_table()->hash_to_index(hash);
293
294 for (HashtableEntry<Symbol*, mtSymbol>* e = the_table()->bucket(index); e != NULL; e = e->next()) {
295 if (e->hash() == hash) {
296 Symbol* literal_sym = e->literal();
297 if (sym == literal_sym) {
298 return e->literal_addr();
299 }
300 }
301 }
302 return NULL;
303 }
304
305 // Suggestion: Push unicode-based lookup all the way into the hashing
306 // and probing logic, so there is no need for convert_to_utf8 until
307 // an actual new Symbol* is created.
308 Symbol* SymbolTable::lookup_unicode(const jchar* name, int utf16_length, TRAPS) {
309 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
310 char stack_buf[128];
311 if (utf8_length < (int) sizeof(stack_buf)) {
312 char* chars = stack_buf;
313 UNICODE::convert_to_utf8(name, utf16_length, chars);
314 return lookup(chars, utf8_length, THREAD);
315 } else {
316 ResourceMark rm(THREAD);
317 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);;
318 UNICODE::convert_to_utf8(name, utf16_length, chars);
319 return lookup(chars, utf8_length, THREAD);
320 }
321 }
322
323 Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,
324 unsigned int& hash) {
325 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
326 char stack_buf[128];
327 if (utf8_length < (int) sizeof(stack_buf)) {
328 char* chars = stack_buf;
329 UNICODE::convert_to_utf8(name, utf16_length, chars);
330 return lookup_only(chars, utf8_length, hash);
331 } else {
332 ResourceMark rm;
333 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);;
334 UNICODE::convert_to_utf8(name, utf16_length, chars);
335 return lookup_only(chars, utf8_length, hash);
336 }
337 }
338
339 void SymbolTable::add(ClassLoaderData* loader_data, constantPoolHandle cp,
340 int names_count,
341 const char** names, int* lengths, int* cp_indices,
342 unsigned int* hashValues, TRAPS) {
343 // Grab SymbolTable_lock first.
344 MutexLocker ml(SymbolTable_lock, THREAD);
345
346 SymbolTable* table = the_table();
347 bool added = table->basic_add(loader_data, cp, names_count, names, lengths,
348 cp_indices, hashValues, CHECK);
349 if (!added) {
350 // do it the hard way
351 for (int i=0; i<names_count; i++) {
352 int index = table->hash_to_index(hashValues[i]);
353 bool c_heap = !loader_data->is_the_null_class_loader_data();
354 Symbol* sym = table->basic_add(index, (u1*)names[i], lengths[i], hashValues[i], c_heap, CHECK);
355 cp->symbol_at_put(cp_indices[i], sym);
356 }
357 }
358 }
359
360 Symbol* SymbolTable::new_permanent_symbol(const char* name, TRAPS) {
361 unsigned int hash;
362 Symbol* result = SymbolTable::lookup_only((char*)name, (int)strlen(name), hash);
363 if (result != NULL) {
364 return result;
365 }
366 // Grab SymbolTable_lock first.
367 MutexLocker ml(SymbolTable_lock, THREAD);
368
369 SymbolTable* table = the_table();
370 int index = table->hash_to_index(hash);
371 return table->basic_add(index, (u1*)name, (int)strlen(name), hash, false, THREAD);
372 }
373
374 Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len,
375 unsigned int hashValue_arg, bool c_heap, TRAPS) {
376 assert(!Universe::heap()->is_in_reserved(name),
377 "proposed name of symbol must be stable");
378
379 // Don't allow symbols to be created which cannot fit in a Symbol*.
380 if (len > Symbol::max_length()) {
381 THROW_MSG_0(vmSymbols::java_lang_InternalError(),
382 "name is too long to represent");
383 }
384
385 // Cannot hit a safepoint in this function because the "this" pointer can move.
386 No_Safepoint_Verifier nsv;
387
388 // Check if the symbol table has been rehashed, if so, need to recalculate
389 // the hash value and index.
390 unsigned int hashValue;
391 int index;
392 if (use_alternate_hashcode()) {
393 hashValue = hash_symbol((const char*)name, len);
394 index = hash_to_index(hashValue);
395 } else {
396 hashValue = hashValue_arg;
397 index = index_arg;
398 }
399
400 // Since look-up was done lock-free, we need to check if another
401 // thread beat us in the race to insert the symbol.
402 Symbol* test = lookup(index, (char*)name, len, hashValue);
403 if (test != NULL) {
404 // A race occurred and another thread introduced the symbol.
405 assert(test->refcount() != 0, "lookup should have incremented the count");
406 return test;
407 }
408
409 // Create a new symbol.
410 Symbol* sym = allocate_symbol(name, len, c_heap, CHECK_NULL);
411 assert(sym->equals((char*)name, len), "symbol must be properly initialized");
412
413 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
414 add_entry(index, entry);
415 return sym;
416 }
417
418 // This version of basic_add adds symbols in batch from the constant pool
419 // parsing.
420 bool SymbolTable::basic_add(ClassLoaderData* loader_data, constantPoolHandle cp,
421 int names_count,
422 const char** names, int* lengths,
423 int* cp_indices, unsigned int* hashValues,
424 TRAPS) {
425
426 // Check symbol names are not too long. If any are too long, don't add any.
427 for (int i = 0; i< names_count; i++) {
428 if (lengths[i] > Symbol::max_length()) {
429 THROW_MSG_0(vmSymbols::java_lang_InternalError(),
430 "name is too long to represent");
431 }
432 }
433
434 // Cannot hit a safepoint in this function because the "this" pointer can move.
435 No_Safepoint_Verifier nsv;
436
437 for (int i=0; i<names_count; i++) {
438 // Check if the symbol table has been rehashed, if so, need to recalculate
439 // the hash value.
440 unsigned int hashValue;
441 if (use_alternate_hashcode()) {
442 hashValue = hash_symbol(names[i], lengths[i]);
443 } else {
444 hashValue = hashValues[i];
445 }
446 // Since look-up was done lock-free, we need to check if another
447 // thread beat us in the race to insert the symbol.
448 int index = hash_to_index(hashValue);
449 Symbol* test = lookup(index, names[i], lengths[i], hashValue);
450 if (test != NULL) {
451 // A race occurred and another thread introduced the symbol, this one
452 // will be dropped and collected. Use test instead.
453 cp->symbol_at_put(cp_indices[i], test);
454 assert(test->refcount() != 0, "lookup should have incremented the count");
455 } else {
456 // Create a new symbol. The null class loader is never unloaded so these
457 // are allocated specially in a permanent arena.
458 bool c_heap = !loader_data->is_the_null_class_loader_data();
459 Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], c_heap, CHECK_(false));
460 assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized"); // why wouldn't it be???
461 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
462 add_entry(index, entry);
463 cp->symbol_at_put(cp_indices[i], sym);
464 }
465 }
466 return true;
467 }
468
469
470 void SymbolTable::verify() {
471 for (int i = 0; i < the_table()->table_size(); ++i) {
472 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
473 for ( ; p != NULL; p = p->next()) {
474 Symbol* s = (Symbol*)(p->literal());
475 guarantee(s != NULL, "symbol is NULL");
476 unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length());
477 guarantee(p->hash() == h, "broken hash in symbol table entry");
478 guarantee(the_table()->hash_to_index(h) == i,
479 "wrong index in symbol table");
480 }
481 }
482 }
483
484 void SymbolTable::dump(outputStream* st) {
485 the_table()->dump_table(st, "SymbolTable");
486 }
487
488
489 //---------------------------------------------------------------------------
490 // Non-product code
491
492 #ifndef PRODUCT
493
494 void SymbolTable::print_histogram() {
495 MutexLocker ml(SymbolTable_lock);
496 const int results_length = 100;
497 int results[results_length];
498 int i,j;
499
500 // initialize results to zero
501 for (j = 0; j < results_length; j++) {
502 results[j] = 0;
503 }
504
505 int total = 0;
506 int max_symbols = 0;
507 int out_of_range = 0;
508 int memory_total = 0;
509 int count = 0;
510 for (i = 0; i < the_table()->table_size(); i++) {
511 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
512 for ( ; p != NULL; p = p->next()) {
513 memory_total += p->literal()->size();
514 count++;
515 int counter = p->literal()->utf8_length();
516 total += counter;
517 if (counter < results_length) {
518 results[counter]++;
519 } else {
520 out_of_range++;
521 }
522 max_symbols = MAX2(max_symbols, counter);
523 }
524 }
525 tty->print_cr("Symbol Table:");
526 tty->print_cr("Total number of symbols %5d", count);
527 tty->print_cr("Total size in memory %5dK",
528 (memory_total*HeapWordSize)/1024);
529 tty->print_cr("Total counted %5d", _symbols_counted);
530 tty->print_cr("Total removed %5d", _symbols_removed);
531 if (_symbols_counted > 0) {
532 tty->print_cr("Percent removed %3.2f",
533 ((float)_symbols_removed/(float)_symbols_counted)* 100);
534 }
535 tty->print_cr("Reference counts %5d", Symbol::_total_count);
536 tty->print_cr("Symbol arena size %5d used %5d",
537 arena()->size_in_bytes(), arena()->used());
538 tty->print_cr("Histogram of symbol length:");
539 tty->print_cr("%8s %5d", "Total ", total);
540 tty->print_cr("%8s %5d", "Maximum", max_symbols);
541 tty->print_cr("%8s %3.2f", "Average",
542 ((float) total / (float) the_table()->table_size()));
543 tty->print_cr("%s", "Histogram:");
544 tty->print_cr(" %s %29s", "Length", "Number chains that length");
545 for (i = 0; i < results_length; i++) {
546 if (results[i] > 0) {
547 tty->print_cr("%6d %10d", i, results[i]);
548 }
549 }
550 if (Verbose) {
551 int line_length = 70;
552 tty->print_cr("%s %30s", " Length", "Number chains that length");
553 for (i = 0; i < results_length; i++) {
554 if (results[i] > 0) {
555 tty->print("%4d", i);
556 for (j = 0; (j < results[i]) && (j < line_length); j++) {
557 tty->print("%1s", "*");
558 }
559 if (j == line_length) {
560 tty->print("%1s", "+");
561 }
562 tty->cr();
563 }
564 }
565 }
566 tty->print_cr(" %s %d: %d\n", "Number chains longer than",
567 results_length, out_of_range);
568 }
569
570 void SymbolTable::print() {
571 for (int i = 0; i < the_table()->table_size(); ++i) {
572 HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i);
573 HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i);
574 if (entry != NULL) {
575 while (entry != NULL) {
576 tty->print(PTR_FORMAT " ", entry->literal());
577 entry->literal()->print();
578 tty->print(" %d", entry->literal()->refcount());
579 p = entry->next_addr();
580 entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p);
581 }
582 tty->cr();
583 }
584 }
585 }
586 #endif // PRODUCT
587
588 // --------------------------------------------------------------------------
589
590 #ifdef ASSERT
591 class StableMemoryChecker : public StackObj {
592 enum { _bufsize = wordSize*4 };
593
594 address _region;
595 jint _size;
596 u1 _save_buf[_bufsize];
597
598 int sample(u1* save_buf) {
599 if (_size <= _bufsize) {
600 memcpy(save_buf, _region, _size);
601 return _size;
602 } else {
603 // copy head and tail
604 memcpy(&save_buf[0], _region, _bufsize/2);
605 memcpy(&save_buf[_bufsize/2], _region + _size - _bufsize/2, _bufsize/2);
606 return (_bufsize/2)*2;
607 }
608 }
609
610 public:
611 StableMemoryChecker(const void* region, jint size) {
612 _region = (address) region;
613 _size = size;
614 sample(_save_buf);
615 }
616
617 bool verify() {
618 u1 check_buf[sizeof(_save_buf)];
619 int check_size = sample(check_buf);
620 return (0 == memcmp(_save_buf, check_buf, check_size));
621 }
622
623 void set_region(const void* region) { _region = (address) region; }
624 };
625 #endif
626
627
628 // --------------------------------------------------------------------------
629 StringTable* StringTable::_the_table = NULL;
630
631 bool StringTable::_needs_rehashing = false;
632
633 volatile int StringTable::_parallel_claimed_idx = 0;
634
635 // Pick hashing algorithm
636 unsigned int StringTable::hash_string(const jchar* s, int len) {
637 return use_alternate_hashcode() ? AltHashing::murmur3_32(seed(), s, len) :
638 java_lang_String::hash_code(s, len);
639 }
640
641 oop StringTable::lookup(int index, jchar* name,
642 int len, unsigned int hash) {
643 int count = 0;
644 for (HashtableEntry<oop, mtSymbol>* l = bucket(index); l != NULL; l = l->next()) {
645 count++;
646 if (l->hash() == hash) {
647 if (java_lang_String::equals(l->literal(), name, len)) {
648 return l->literal();
649 }
650 }
651 }
652 // If the bucket size is too deep check if this hash code is insufficient.
653 if (count >= BasicHashtable<mtSymbol>::rehash_count && !needs_rehashing()) {
654 _needs_rehashing = check_rehash_table(count);
655 }
656 return NULL;
657 }
658
659
660 oop StringTable::basic_add(int index_arg, Handle string, jchar* name,
661 int len, unsigned int hashValue_arg, TRAPS) {
662
663 assert(java_lang_String::equals(string(), name, len),
664 "string must be properly initialized");
665 // Cannot hit a safepoint in this function because the "this" pointer can move.
666 No_Safepoint_Verifier nsv;
667
668 // Check if the symbol table has been rehashed, if so, need to recalculate
669 // the hash value and index before second lookup.
670 unsigned int hashValue;
671 int index;
672 if (use_alternate_hashcode()) {
673 hashValue = hash_string(name, len);
674 index = hash_to_index(hashValue);
675 } else {
676 hashValue = hashValue_arg;
677 index = index_arg;
678 }
679
680 // Since look-up was done lock-free, we need to check if another
681 // thread beat us in the race to insert the symbol.
682
683 oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int)
684 if (test != NULL) {
685 // Entry already added
686 return test;
687 }
688
689 HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string());
690 add_entry(index, entry);
691 return string();
692 }
693
694
695 oop StringTable::lookup(Symbol* symbol) {
696 ResourceMark rm;
697 int length;
698 jchar* chars = symbol->as_unicode(length);
699 return lookup(chars, length);
700 }
701
702
703 oop StringTable::lookup(jchar* name, int len) {
704 unsigned int hash = hash_string(name, len);
705 int index = the_table()->hash_to_index(hash);
706 return the_table()->lookup(index, name, len, hash);
707 }
708
709
710 oop StringTable::intern(Handle string_or_null, jchar* name,
711 int len, TRAPS) {
712 unsigned int hashValue = hash_string(name, len);
713 int index = the_table()->hash_to_index(hashValue);
714 oop found_string = the_table()->lookup(index, name, len, hashValue);
715
716 // Found
717 if (found_string != NULL) return found_string;
718
719 debug_only(StableMemoryChecker smc(name, len * sizeof(name[0])));
720 assert(!Universe::heap()->is_in_reserved(name),
721 "proposed name of symbol must be stable");
722
723 Handle string;
724 // try to reuse the string if possible
725 if (!string_or_null.is_null()) {
726 string = string_or_null;
727 } else {
728 string = java_lang_String::create_from_unicode(name, len, CHECK_NULL);
729 }
730
731 // Grab the StringTable_lock before getting the_table() because it could
732 // change at safepoint.
733 MutexLocker ml(StringTable_lock, THREAD);
734
735 // Otherwise, add to symbol to table
736 return the_table()->basic_add(index, string, name, len,
737 hashValue, CHECK_NULL);
738 }
739
740 oop StringTable::intern(Symbol* symbol, TRAPS) {
741 if (symbol == NULL) return NULL;
742 ResourceMark rm(THREAD);
743 int length;
744 jchar* chars = symbol->as_unicode(length);
745 Handle string;
746 oop result = intern(string, chars, length, CHECK_NULL);
747 return result;
748 }
749
750
751 oop StringTable::intern(oop string, TRAPS)
752 {
753 if (string == NULL) return NULL;
754 ResourceMark rm(THREAD);
755 int length;
756 Handle h_string (THREAD, string);
757 jchar* chars = java_lang_String::as_unicode_string(string, length, CHECK_NULL);
758 oop result = intern(h_string, chars, length, CHECK_NULL);
759 return result;
760 }
761
762
763 oop StringTable::intern(const char* utf8_string, TRAPS) {
764 if (utf8_string == NULL) return NULL;
765 ResourceMark rm(THREAD);
766 int length = UTF8::unicode_length(utf8_string);
767 jchar* chars = NEW_RESOURCE_ARRAY(jchar, length);
768 UTF8::convert_to_unicode(utf8_string, chars, length);
769 Handle string;
770 oop result = intern(string, chars, length, CHECK_NULL);
771 return result;
772 }
773
774 void StringTable::unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int* processed, int* removed) {
775 buckets_unlink_or_oops_do(is_alive, f, 0, the_table()->table_size(), processed, removed);
776 }
777
778 void StringTable::possibly_parallel_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int* processed, int* removed) {
779 // Readers of the table are unlocked, so we should only be removing
780 // entries at a safepoint.
781 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
782 const int limit = the_table()->table_size();
783
784 for (;;) {
785 // Grab next set of buckets to scan
786 int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
787 if (start_idx >= limit) {
788 // End of table
789 break;
790 }
791
792 int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
793 buckets_unlink_or_oops_do(is_alive, f, start_idx, end_idx, processed, removed);
794 }
795 }
796
797 void StringTable::buckets_oops_do(OopClosure* f, int start_idx, int end_idx) {
798 const int limit = the_table()->table_size();
799
800 assert(0 <= start_idx && start_idx <= limit,
801 err_msg("start_idx (" INT32_FORMAT ") is out of bounds", start_idx));
802 assert(0 <= end_idx && end_idx <= limit,
803 err_msg("end_idx (" INT32_FORMAT ") is out of bounds", end_idx));
804 assert(start_idx <= end_idx,
805 err_msg("Index ordering: start_idx=" INT32_FORMAT", end_idx=" INT32_FORMAT,
806 start_idx, end_idx));
807
808 for (int i = start_idx; i < end_idx; i += 1) {
809 HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);
810 while (entry != NULL) {
811 assert(!entry->is_shared(), "CDS not used for the StringTable");
812
813 f->do_oop((oop*)entry->literal_addr());
814
815 entry = entry->next();
816 }
817 }
818 }
819
820 void StringTable::buckets_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int start_idx, int end_idx, int* processed, int* removed) {
821 const int limit = the_table()->table_size();
822
823 assert(0 <= start_idx && start_idx <= limit,
824 err_msg("start_idx (" INT32_FORMAT ") is out of bounds", start_idx));
825 assert(0 <= end_idx && end_idx <= limit,
826 err_msg("end_idx (" INT32_FORMAT ") is out of bounds", end_idx));
827 assert(start_idx <= end_idx,
828 err_msg("Index ordering: start_idx=" INT32_FORMAT", end_idx=" INT32_FORMAT,
829 start_idx, end_idx));
830
831 for (int i = start_idx; i < end_idx; ++i) {
832 HashtableEntry<oop, mtSymbol>** p = the_table()->bucket_addr(i);
833 HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);
834 while (entry != NULL) {
835 assert(!entry->is_shared(), "CDS not used for the StringTable");
836
837 if (is_alive->do_object_b(entry->literal())) {
838 if (f != NULL) {
839 f->do_oop((oop*)entry->literal_addr());
840 }
841 p = entry->next_addr();
842 } else {
843 *p = entry->next();
844 the_table()->free_entry(entry);
845 (*removed)++;
846 }
847 (*processed)++;
848 entry = *p;
849 }
850 }
851 }
852
853 void StringTable::oops_do(OopClosure* f) {
854 buckets_oops_do(f, 0, the_table()->table_size());
855 }
856
857 void StringTable::possibly_parallel_oops_do(OopClosure* f) {
858 const int limit = the_table()->table_size();
859
860 for (;;) {
861 // Grab next set of buckets to scan
862 int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
863 if (start_idx >= limit) {
864 // End of table
865 break;
866 }
867
868 int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
869 buckets_oops_do(f, start_idx, end_idx);
870 }
871 }
872
873 // This verification is part of Universe::verify() and needs to be quick.
874 // See StringTable::verify_and_compare() below for exhaustive verification.
875 void StringTable::verify() {
876 for (int i = 0; i < the_table()->table_size(); ++i) {
877 HashtableEntry<oop, mtSymbol>* p = the_table()->bucket(i);
878 for ( ; p != NULL; p = p->next()) {
879 oop s = p->literal();
880 guarantee(s != NULL, "interned string is NULL");
881 unsigned int h = java_lang_String::hash_string(s);
882 guarantee(p->hash() == h, "broken hash in string table entry");
883 guarantee(the_table()->hash_to_index(h) == i,
884 "wrong index in string table");
885 }
886 }
887 }
888
889 void StringTable::dump(outputStream* st) {
890 the_table()->dump_table(st, "StringTable");
891 }
892
893 StringTable::VerifyRetTypes StringTable::compare_entries(
894 int bkt1, int e_cnt1,
895 HashtableEntry<oop, mtSymbol>* e_ptr1,
896 int bkt2, int e_cnt2,
897 HashtableEntry<oop, mtSymbol>* e_ptr2) {
898 // These entries are sanity checked by verify_and_compare_entries()
899 // before this function is called.
900 oop str1 = e_ptr1->literal();
901 oop str2 = e_ptr2->literal();
902
903 if (str1 == str2) {
904 tty->print_cr("ERROR: identical oop values (0x" PTR_FORMAT ") "
905 "in entry @ bucket[%d][%d] and entry @ bucket[%d][%d]",
906 (void *)str1, bkt1, e_cnt1, bkt2, e_cnt2);
907 return _verify_fail_continue;
908 }
909
910 if (java_lang_String::equals(str1, str2)) {
911 tty->print_cr("ERROR: identical String values in entry @ "
912 "bucket[%d][%d] and entry @ bucket[%d][%d]",
913 bkt1, e_cnt1, bkt2, e_cnt2);
914 return _verify_fail_continue;
915 }
916
917 return _verify_pass;
918 }
919
920 StringTable::VerifyRetTypes StringTable::verify_entry(int bkt, int e_cnt,
921 HashtableEntry<oop, mtSymbol>* e_ptr,
922 StringTable::VerifyMesgModes mesg_mode) {
923
924 VerifyRetTypes ret = _verify_pass; // be optimistic
925
926 oop str = e_ptr->literal();
927 if (str == NULL) {
928 if (mesg_mode == _verify_with_mesgs) {
929 tty->print_cr("ERROR: NULL oop value in entry @ bucket[%d][%d]", bkt,
930 e_cnt);
931 }
932 // NULL oop means no more verifications are possible
933 return _verify_fail_done;
934 }
935
936 if (str->klass() != SystemDictionary::String_klass()) {
937 if (mesg_mode == _verify_with_mesgs) {
938 tty->print_cr("ERROR: oop is not a String in entry @ bucket[%d][%d]",
939 bkt, e_cnt);
940 }
941 // not a String means no more verifications are possible
942 return _verify_fail_done;
943 }
944
945 unsigned int h = java_lang_String::hash_string(str);
946 if (e_ptr->hash() != h) {
947 if (mesg_mode == _verify_with_mesgs) {
948 tty->print_cr("ERROR: broken hash value in entry @ bucket[%d][%d], "
949 "bkt_hash=%d, str_hash=%d", bkt, e_cnt, e_ptr->hash(), h);
950 }
951 ret = _verify_fail_continue;
952 }
953
954 if (the_table()->hash_to_index(h) != bkt) {
955 if (mesg_mode == _verify_with_mesgs) {
956 tty->print_cr("ERROR: wrong index value for entry @ bucket[%d][%d], "
957 "str_hash=%d, hash_to_index=%d", bkt, e_cnt, h,
958 the_table()->hash_to_index(h));
959 }
960 ret = _verify_fail_continue;
961 }
962
963 return ret;
964 }
965
966 // See StringTable::verify() above for the quick verification that is
967 // part of Universe::verify(). This verification is exhaustive and
968 // reports on every issue that is found. StringTable::verify() only
969 // reports on the first issue that is found.
970 //
971 // StringTable::verify_entry() checks:
972 // - oop value != NULL (same as verify())
973 // - oop value is a String
974 // - hash(String) == hash in entry (same as verify())
975 // - index for hash == index of entry (same as verify())
976 //
977 // StringTable::compare_entries() checks:
978 // - oops are unique across all entries
979 // - String values are unique across all entries
980 //
981 int StringTable::verify_and_compare_entries() {
982 assert(StringTable_lock->is_locked(), "sanity check");
983
984 int fail_cnt = 0;
985
986 // first, verify all the entries individually:
987 for (int bkt = 0; bkt < the_table()->table_size(); bkt++) {
988 HashtableEntry<oop, mtSymbol>* e_ptr = the_table()->bucket(bkt);
989 for (int e_cnt = 0; e_ptr != NULL; e_ptr = e_ptr->next(), e_cnt++) {
990 VerifyRetTypes ret = verify_entry(bkt, e_cnt, e_ptr, _verify_with_mesgs);
991 if (ret != _verify_pass) {
992 fail_cnt++;
993 }
994 }
995 }
996
997 // Optimization: if the above check did not find any failures, then
998 // the comparison loop below does not need to call verify_entry()
999 // before calling compare_entries(). If there were failures, then we
1000 // have to call verify_entry() to see if the entry can be passed to
1001 // compare_entries() safely. When we call verify_entry() in the loop
1002 // below, we do so quietly to void duplicate messages and we don't
1003 // increment fail_cnt because the failures have already been counted.
1004 bool need_entry_verify = (fail_cnt != 0);
1005
1006 // second, verify all entries relative to each other:
1007 for (int bkt1 = 0; bkt1 < the_table()->table_size(); bkt1++) {
1008 HashtableEntry<oop, mtSymbol>* e_ptr1 = the_table()->bucket(bkt1);
1009 for (int e_cnt1 = 0; e_ptr1 != NULL; e_ptr1 = e_ptr1->next(), e_cnt1++) {
1010 if (need_entry_verify) {
1011 VerifyRetTypes ret = verify_entry(bkt1, e_cnt1, e_ptr1,
1012 _verify_quietly);
1013 if (ret == _verify_fail_done) {
1014 // cannot use the current entry to compare against other entries
1015 continue;
1016 }
1017 }
1018
1019 for (int bkt2 = bkt1; bkt2 < the_table()->table_size(); bkt2++) {
1020 HashtableEntry<oop, mtSymbol>* e_ptr2 = the_table()->bucket(bkt2);
1021 int e_cnt2;
1022 for (e_cnt2 = 0; e_ptr2 != NULL; e_ptr2 = e_ptr2->next(), e_cnt2++) {
1023 if (bkt1 == bkt2 && e_cnt2 <= e_cnt1) {
1024 // skip the entries up to and including the one that
1025 // we're comparing against
1026 continue;
1027 }
1028
1029 if (need_entry_verify) {
1030 VerifyRetTypes ret = verify_entry(bkt2, e_cnt2, e_ptr2,
1031 _verify_quietly);
1032 if (ret == _verify_fail_done) {
1033 // cannot compare against this entry
1034 continue;
1035 }
1036 }
1037
1038 // compare two entries, report and count any failures:
1039 if (compare_entries(bkt1, e_cnt1, e_ptr1, bkt2, e_cnt2, e_ptr2)
1040 != _verify_pass) {
1041 fail_cnt++;
1042 }
1043 }
1044 }
1045 }
1046 }
1047 return fail_cnt;
1048 }
1049
1050 // Create a new table and using alternate hash code, populate the new table
1051 // with the existing strings. Set flag to use the alternate hash code afterwards.
1052 void StringTable::rehash_table() {
1053 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
1054 // This should never happen with -Xshare:dump but it might in testing mode.
1055 if (DumpSharedSpaces) return;
1056 StringTable* new_table = new StringTable();
1057
1058 // Rehash the table
1059 the_table()->move_to(new_table);
1060
1061 // Delete the table and buckets (entries are reused in new table).
1062 delete _the_table;
1063 // Don't check if we need rehashing until the table gets unbalanced again.
1064 // Then rehash with a new global seed.
1065 _needs_rehashing = false;
1066 _the_table = new_table;
1067 }