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/compactHashtable.hpp"
28 #include "classfile/javaClasses.hpp"
29 #include "classfile/stringTable.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 "runtime/atomic.inline.hpp"
37 #include "runtime/mutexLocker.hpp"
38 #include "utilities/hashtable.inline.hpp"
39 #include "utilities/macros.hpp"
40 #if INCLUDE_ALL_GCS
41 #include "gc_implementation/g1/g1SATBCardTableModRefBS.hpp"
42 #include "gc_implementation/g1/g1StringDedup.hpp"
43 #endif
44
45 PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
46
47 // the number of buckets a thread claims
48 const int ClaimChunkSize = 32;
49
50 #ifdef ASSERT
51 class StableMemoryChecker : public StackObj {
52 enum { _bufsize = wordSize*4 };
53
54 address _region;
55 jint _size;
56 u1 _save_buf[_bufsize];
57
58 int sample(u1* save_buf) {
59 if (_size <= _bufsize) {
60 memcpy(save_buf, _region, _size);
61 return _size;
62 } else {
63 // copy head and tail
64 memcpy(&save_buf[0], _region, _bufsize/2);
65 memcpy(&save_buf[_bufsize/2], _region + _size - _bufsize/2, _bufsize/2);
66 return (_bufsize/2)*2;
67 }
68 }
69
70 public:
71 StableMemoryChecker(const void* region, jint size) {
72 _region = (address) region;
73 _size = size;
74 sample(_save_buf);
75 }
76
77 bool verify() {
78 u1 check_buf[sizeof(_save_buf)];
79 int check_size = sample(check_buf);
80 return (0 == memcmp(_save_buf, check_buf, check_size));
81 }
82
83 void set_region(const void* region) { _region = (address) region; }
84 };
85 #endif
86
87
88 // --------------------------------------------------------------------------
89 StringTable* StringTable::_the_table = NULL;
90
91 bool StringTable::_needs_rehashing = false;
92
93 volatile int StringTable::_parallel_claimed_idx = 0;
94
95 // Pick hashing algorithm
96 unsigned int StringTable::hash_string(const jchar* s, int len) {
97 return use_alternate_hashcode() ? AltHashing::murmur3_32(seed(), s, len) :
98 java_lang_String::hash_code(s, len);
99 }
100
101 oop StringTable::lookup(int index, jchar* name,
102 int len, unsigned int hash) {
103 int count = 0;
104 for (HashtableEntry<oop, mtSymbol>* l = bucket(index); l != NULL; l = l->next()) {
105 count++;
106 if (l->hash() == hash) {
107 if (java_lang_String::equals(l->literal(), name, len)) {
108 return l->literal();
109 }
110 }
111 }
112 // If the bucket size is too deep check if this hash code is insufficient.
113 if (count >= rehash_count && !needs_rehashing()) {
114 _needs_rehashing = check_rehash_table(count);
115 }
116 return NULL;
117 }
118
119
120 oop StringTable::basic_add(int index_arg, Handle string, jchar* name,
121 int len, unsigned int hashValue_arg, TRAPS) {
122
123 assert(java_lang_String::equals(string(), name, len),
124 "string must be properly initialized");
125 // Cannot hit a safepoint in this function because the "this" pointer can move.
126 No_Safepoint_Verifier nsv;
127
128 // Check if the symbol table has been rehashed, if so, need to recalculate
129 // the hash value and index before second lookup.
130 unsigned int hashValue;
131 int index;
132 if (use_alternate_hashcode()) {
133 hashValue = hash_string(name, len);
134 index = hash_to_index(hashValue);
135 } else {
136 hashValue = hashValue_arg;
137 index = index_arg;
138 }
139
140 // Since look-up was done lock-free, we need to check if another
141 // thread beat us in the race to insert the symbol.
142
143 oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int)
144 if (test != NULL) {
145 // Entry already added
146 return test;
147 }
148
149 HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string());
150 add_entry(index, entry);
151 return string();
152 }
153
154
155 oop StringTable::lookup(Symbol* symbol) {
156 ResourceMark rm;
157 int length;
158 jchar* chars = symbol->as_unicode(length);
159 return lookup(chars, length);
160 }
161
162 // Tell the GC that this string was looked up in the StringTable.
163 static void ensure_string_alive(oop string) {
164 // A lookup in the StringTable could return an object that was previously
165 // considered dead. The SATB part of G1 needs to get notified about this
166 // potential resurrection, otherwise the marking might not find the object.
167 #if INCLUDE_ALL_GCS
168 if (UseG1GC && string != NULL) {
169 G1SATBCardTableModRefBS::enqueue(string);
170 }
171 #endif
172 }
173
174 oop StringTable::lookup(jchar* name, int len) {
175 unsigned int hash = hash_string(name, len);
176 int index = the_table()->hash_to_index(hash);
177 oop string = the_table()->lookup(index, name, len, hash);
178
179 ensure_string_alive(string);
180
181 return string;
182 }
183
184
185 oop StringTable::intern(Handle string_or_null, jchar* name,
186 int len, TRAPS) {
187 unsigned int hashValue = hash_string(name, len);
188 int index = the_table()->hash_to_index(hashValue);
189 oop found_string = the_table()->lookup(index, name, len, hashValue);
190
191 // Found
192 if (found_string != NULL) {
193 ensure_string_alive(found_string);
194 return found_string;
195 }
196
197 debug_only(StableMemoryChecker smc(name, len * sizeof(name[0])));
198 assert(!Universe::heap()->is_in_reserved(name),
199 "proposed name of symbol must be stable");
200
201 Handle string;
202 // try to reuse the string if possible
203 if (!string_or_null.is_null()) {
204 string = string_or_null;
205 } else {
206 string = java_lang_String::create_from_unicode(name, len, CHECK_NULL);
207 }
208
209 #if INCLUDE_ALL_GCS
210 if (G1StringDedup::is_enabled()) {
211 // Deduplicate the string before it is interned. Note that we should never
212 // deduplicate a string after it has been interned. Doing so will counteract
213 // compiler optimizations done on e.g. interned string literals.
214 G1StringDedup::deduplicate(string());
215 }
216 #endif
217
218 // Grab the StringTable_lock before getting the_table() because it could
219 // change at safepoint.
220 oop added_or_found;
221 {
222 MutexLocker ml(StringTable_lock, THREAD);
223 // Otherwise, add to symbol to table
224 added_or_found = the_table()->basic_add(index, string, name, len,
225 hashValue, CHECK_NULL);
226 }
227
228 ensure_string_alive(added_or_found);
229
230 return added_or_found;
231 }
232
233 oop StringTable::intern(Symbol* symbol, TRAPS) {
234 if (symbol == NULL) return NULL;
235 ResourceMark rm(THREAD);
236 int length;
237 jchar* chars = symbol->as_unicode(length);
238 Handle string;
239 oop result = intern(string, chars, length, CHECK_NULL);
240 return result;
241 }
242
243
244 oop StringTable::intern(oop string, TRAPS)
245 {
246 if (string == NULL) return NULL;
247 ResourceMark rm(THREAD);
248 int length;
249 Handle h_string (THREAD, string);
250 jchar* chars = java_lang_String::as_unicode_string(string, length, CHECK_NULL);
251 oop result = intern(h_string, chars, length, CHECK_NULL);
252 return result;
253 }
254
255
256 oop StringTable::intern(const char* utf8_string, TRAPS) {
257 if (utf8_string == NULL) return NULL;
258 ResourceMark rm(THREAD);
259 int length = UTF8::unicode_length(utf8_string);
260 jchar* chars = NEW_RESOURCE_ARRAY(jchar, length);
261 UTF8::convert_to_unicode(utf8_string, chars, length);
262 Handle string;
263 oop result = intern(string, chars, length, CHECK_NULL);
264 return result;
265 }
266
267 void StringTable::unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int* processed, int* removed) {
268 buckets_unlink_or_oops_do(is_alive, f, 0, the_table()->table_size(), processed, removed);
269 }
270
271 void StringTable::possibly_parallel_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int* processed, int* removed) {
272 // Readers of the table are unlocked, so we should only be removing
273 // entries at a safepoint.
274 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
275 const int limit = the_table()->table_size();
276
277 for (;;) {
278 // Grab next set of buckets to scan
279 int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
280 if (start_idx >= limit) {
281 // End of table
282 break;
283 }
284
285 int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
286 buckets_unlink_or_oops_do(is_alive, f, start_idx, end_idx, processed, removed);
287 }
288 }
289
290 void StringTable::buckets_oops_do(OopClosure* f, int start_idx, int end_idx) {
291 const int limit = the_table()->table_size();
292
293 assert(0 <= start_idx && start_idx <= limit,
294 err_msg("start_idx (%d) is out of bounds", start_idx));
295 assert(0 <= end_idx && end_idx <= limit,
296 err_msg("end_idx (%d) is out of bounds", end_idx));
297 assert(start_idx <= end_idx,
298 err_msg("Index ordering: start_idx=%d, end_idx=%d",
299 start_idx, end_idx));
300
301 for (int i = start_idx; i < end_idx; i += 1) {
302 HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);
303 while (entry != NULL) {
304 assert(!entry->is_shared(), "CDS not used for the StringTable");
305
306 f->do_oop((oop*)entry->literal_addr());
307
308 entry = entry->next();
309 }
310 }
311 }
312
313 void StringTable::buckets_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int start_idx, int end_idx, int* processed, int* removed) {
314 const int limit = the_table()->table_size();
315
316 assert(0 <= start_idx && start_idx <= limit,
317 err_msg("start_idx (%d) is out of bounds", start_idx));
318 assert(0 <= end_idx && end_idx <= limit,
319 err_msg("end_idx (%d) is out of bounds", end_idx));
320 assert(start_idx <= end_idx,
321 err_msg("Index ordering: start_idx=%d, end_idx=%d",
322 start_idx, end_idx));
323
324 for (int i = start_idx; i < end_idx; ++i) {
325 HashtableEntry<oop, mtSymbol>** p = the_table()->bucket_addr(i);
326 HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);
327 while (entry != NULL) {
328 assert(!entry->is_shared(), "CDS not used for the StringTable");
329
330 if (is_alive->do_object_b(entry->literal())) {
331 if (f != NULL) {
332 f->do_oop((oop*)entry->literal_addr());
333 }
334 p = entry->next_addr();
335 } else {
336 *p = entry->next();
337 the_table()->free_entry(entry);
338 (*removed)++;
339 }
340 (*processed)++;
341 entry = *p;
342 }
343 }
344 }
345
346 void StringTable::oops_do(OopClosure* f) {
347 buckets_oops_do(f, 0, the_table()->table_size());
348 }
349
350 void StringTable::possibly_parallel_oops_do(OopClosure* f) {
351 const int limit = the_table()->table_size();
352
353 for (;;) {
354 // Grab next set of buckets to scan
355 int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
356 if (start_idx >= limit) {
357 // End of table
358 break;
359 }
360
361 int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
362 buckets_oops_do(f, start_idx, end_idx);
363 }
364 }
365
366 // This verification is part of Universe::verify() and needs to be quick.
367 // See StringTable::verify_and_compare() below for exhaustive verification.
368 void StringTable::verify() {
369 for (int i = 0; i < the_table()->table_size(); ++i) {
370 HashtableEntry<oop, mtSymbol>* p = the_table()->bucket(i);
371 for ( ; p != NULL; p = p->next()) {
372 oop s = p->literal();
373 guarantee(s != NULL, "interned string is NULL");
374 unsigned int h = java_lang_String::hash_string(s);
375 guarantee(p->hash() == h, "broken hash in string table entry");
376 guarantee(the_table()->hash_to_index(h) == i,
377 "wrong index in string table");
378 }
379 }
380 }
381
382 void StringTable::dump(outputStream* st, bool verbose) {
383 if (!verbose) {
384 the_table()->dump_table(st, "StringTable");
385 } else {
386 Thread* THREAD = Thread::current();
387 st->print_cr("VERSION: 1.1");
388 for (int i = 0; i < the_table()->table_size(); ++i) {
389 HashtableEntry<oop, mtSymbol>* p = the_table()->bucket(i);
390 for ( ; p != NULL; p = p->next()) {
391 oop s = p->literal();
392 typeArrayOop value = java_lang_String::value(s);
393 int offset = java_lang_String::offset(s);
394 int length = java_lang_String::length(s);
395
396 if (length <= 0) {
397 st->print("%d: ", length);
398 } else {
399 ResourceMark rm(THREAD);
400 jchar* chars = (jchar*)value->char_at_addr(offset);
401 int utf8_length = UNICODE::utf8_length(chars, length);
402 char* utf8_string = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
403 UNICODE::convert_to_utf8(chars, length, utf8_string);
404
405 st->print("%d: ", utf8_length);
406 HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
407 }
408 st->cr();
409 }
410 }
411 }
412 }
413
414 StringTable::VerifyRetTypes StringTable::compare_entries(
415 int bkt1, int e_cnt1,
416 HashtableEntry<oop, mtSymbol>* e_ptr1,
417 int bkt2, int e_cnt2,
418 HashtableEntry<oop, mtSymbol>* e_ptr2) {
419 // These entries are sanity checked by verify_and_compare_entries()
420 // before this function is called.
421 oop str1 = e_ptr1->literal();
422 oop str2 = e_ptr2->literal();
423
424 if (str1 == str2) {
425 tty->print_cr("ERROR: identical oop values (0x" PTR_FORMAT ") "
426 "in entry @ bucket[%d][%d] and entry @ bucket[%d][%d]",
427 (void *)str1, bkt1, e_cnt1, bkt2, e_cnt2);
428 return _verify_fail_continue;
429 }
430
431 if (java_lang_String::equals(str1, str2)) {
432 tty->print_cr("ERROR: identical String values in entry @ "
433 "bucket[%d][%d] and entry @ bucket[%d][%d]",
434 bkt1, e_cnt1, bkt2, e_cnt2);
435 return _verify_fail_continue;
436 }
437
438 return _verify_pass;
439 }
440
441 StringTable::VerifyRetTypes StringTable::verify_entry(int bkt, int e_cnt,
442 HashtableEntry<oop, mtSymbol>* e_ptr,
443 StringTable::VerifyMesgModes mesg_mode) {
444
445 VerifyRetTypes ret = _verify_pass; // be optimistic
446
447 oop str = e_ptr->literal();
448 if (str == NULL) {
449 if (mesg_mode == _verify_with_mesgs) {
450 tty->print_cr("ERROR: NULL oop value in entry @ bucket[%d][%d]", bkt,
451 e_cnt);
452 }
453 // NULL oop means no more verifications are possible
454 return _verify_fail_done;
455 }
456
457 if (str->klass() != SystemDictionary::String_klass()) {
458 if (mesg_mode == _verify_with_mesgs) {
459 tty->print_cr("ERROR: oop is not a String in entry @ bucket[%d][%d]",
460 bkt, e_cnt);
461 }
462 // not a String means no more verifications are possible
463 return _verify_fail_done;
464 }
465
466 unsigned int h = java_lang_String::hash_string(str);
467 if (e_ptr->hash() != h) {
468 if (mesg_mode == _verify_with_mesgs) {
469 tty->print_cr("ERROR: broken hash value in entry @ bucket[%d][%d], "
470 "bkt_hash=%d, str_hash=%d", bkt, e_cnt, e_ptr->hash(), h);
471 }
472 ret = _verify_fail_continue;
473 }
474
475 if (the_table()->hash_to_index(h) != bkt) {
476 if (mesg_mode == _verify_with_mesgs) {
477 tty->print_cr("ERROR: wrong index value for entry @ bucket[%d][%d], "
478 "str_hash=%d, hash_to_index=%d", bkt, e_cnt, h,
479 the_table()->hash_to_index(h));
480 }
481 ret = _verify_fail_continue;
482 }
483
484 return ret;
485 }
486
487 // See StringTable::verify() above for the quick verification that is
488 // part of Universe::verify(). This verification is exhaustive and
489 // reports on every issue that is found. StringTable::verify() only
490 // reports on the first issue that is found.
491 //
492 // StringTable::verify_entry() checks:
493 // - oop value != NULL (same as verify())
494 // - oop value is a String
495 // - hash(String) == hash in entry (same as verify())
496 // - index for hash == index of entry (same as verify())
497 //
498 // StringTable::compare_entries() checks:
499 // - oops are unique across all entries
500 // - String values are unique across all entries
501 //
502 int StringTable::verify_and_compare_entries() {
503 assert(StringTable_lock->is_locked(), "sanity check");
504
505 int fail_cnt = 0;
506
507 // first, verify all the entries individually:
508 for (int bkt = 0; bkt < the_table()->table_size(); bkt++) {
509 HashtableEntry<oop, mtSymbol>* e_ptr = the_table()->bucket(bkt);
510 for (int e_cnt = 0; e_ptr != NULL; e_ptr = e_ptr->next(), e_cnt++) {
511 VerifyRetTypes ret = verify_entry(bkt, e_cnt, e_ptr, _verify_with_mesgs);
512 if (ret != _verify_pass) {
513 fail_cnt++;
514 }
515 }
516 }
517
518 // Optimization: if the above check did not find any failures, then
519 // the comparison loop below does not need to call verify_entry()
520 // before calling compare_entries(). If there were failures, then we
521 // have to call verify_entry() to see if the entry can be passed to
522 // compare_entries() safely. When we call verify_entry() in the loop
523 // below, we do so quietly to void duplicate messages and we don't
524 // increment fail_cnt because the failures have already been counted.
525 bool need_entry_verify = (fail_cnt != 0);
526
527 // second, verify all entries relative to each other:
528 for (int bkt1 = 0; bkt1 < the_table()->table_size(); bkt1++) {
529 HashtableEntry<oop, mtSymbol>* e_ptr1 = the_table()->bucket(bkt1);
530 for (int e_cnt1 = 0; e_ptr1 != NULL; e_ptr1 = e_ptr1->next(), e_cnt1++) {
531 if (need_entry_verify) {
532 VerifyRetTypes ret = verify_entry(bkt1, e_cnt1, e_ptr1,
533 _verify_quietly);
534 if (ret == _verify_fail_done) {
535 // cannot use the current entry to compare against other entries
536 continue;
537 }
538 }
539
540 for (int bkt2 = bkt1; bkt2 < the_table()->table_size(); bkt2++) {
541 HashtableEntry<oop, mtSymbol>* e_ptr2 = the_table()->bucket(bkt2);
542 int e_cnt2;
543 for (e_cnt2 = 0; e_ptr2 != NULL; e_ptr2 = e_ptr2->next(), e_cnt2++) {
544 if (bkt1 == bkt2 && e_cnt2 <= e_cnt1) {
545 // skip the entries up to and including the one that
546 // we're comparing against
547 continue;
548 }
549
550 if (need_entry_verify) {
551 VerifyRetTypes ret = verify_entry(bkt2, e_cnt2, e_ptr2,
552 _verify_quietly);
553 if (ret == _verify_fail_done) {
554 // cannot compare against this entry
555 continue;
556 }
557 }
558
559 // compare two entries, report and count any failures:
560 if (compare_entries(bkt1, e_cnt1, e_ptr1, bkt2, e_cnt2, e_ptr2)
561 != _verify_pass) {
562 fail_cnt++;
563 }
564 }
565 }
566 }
567 }
568 return fail_cnt;
569 }
570
571 // Create a new table and using alternate hash code, populate the new table
572 // with the existing strings. Set flag to use the alternate hash code afterwards.
573 void StringTable::rehash_table() {
574 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
575 // This should never happen with -Xshare:dump but it might in testing mode.
576 if (DumpSharedSpaces) return;
577 StringTable* new_table = new StringTable();
578
579 // Rehash the table
580 the_table()->move_to(new_table);
581
582 // Delete the table and buckets (entries are reused in new table).
583 delete _the_table;
584 // Don't check if we need rehashing until the table gets unbalanced again.
585 // Then rehash with a new global seed.
586 _needs_rehashing = false;
587 _the_table = new_table;
588 }
589
590 // Utility for dumping strings
591 StringtableDCmd::StringtableDCmd(outputStream* output, bool heap) :
592 DCmdWithParser(output, heap),
593 _verbose("-verbose", "Dump the content of each string in the table",
594 "BOOLEAN", false, "false") {
595 _dcmdparser.add_dcmd_option(&_verbose);
596 }
597
598 void StringtableDCmd::execute(DCmdSource source, TRAPS) {
599 VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpStrings,
600 _verbose.value());
601 VMThread::execute(&dumper);
602 }
603
604 int StringtableDCmd::num_arguments() {
605 ResourceMark rm;
606 StringtableDCmd* dcmd = new StringtableDCmd(NULL, false);
607 if (dcmd != NULL) {
608 DCmdMark mark(dcmd);
609 return dcmd->_dcmdparser.num_arguments();
610 } else {
611 return 0;
612 }
613 }