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