1 /*
2 * Copyright (c) 1997, 2024, 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 "cds/archiveBuilder.hpp"
27 #include "cds/archiveHeapLoader.inline.hpp"
28 #include "cds/archiveHeapWriter.hpp"
29 #include "cds/cdsConfig.hpp"
30 #include "cds/filemap.hpp"
31 #include "cds/heapShared.hpp"
32 #include "classfile/altHashing.hpp"
33 #include "classfile/compactHashtable.hpp"
34 #include "classfile/javaClasses.inline.hpp"
35 #include "classfile/stringTable.hpp"
36 #include "classfile/vmClasses.hpp"
37 #include "gc/shared/collectedHeap.hpp"
38 #include "gc/shared/oopStorage.inline.hpp"
39 #include "gc/shared/oopStorageSet.hpp"
40 #include "gc/shared/stringdedup/stringDedup.hpp"
41 #include "logging/log.hpp"
42 #include "logging/logStream.hpp"
43 #include "memory/allocation.inline.hpp"
44 #include "memory/oopFactory.hpp"
45 #include "memory/resourceArea.hpp"
46 #include "oops/access.inline.hpp"
47 #include "oops/compressedOops.hpp"
48 #include "oops/oop.inline.hpp"
49 #include "oops/typeArrayOop.inline.hpp"
50 #include "oops/weakHandle.inline.hpp"
51 #include "runtime/atomic.hpp"
52 #include "runtime/handles.inline.hpp"
53 #include "runtime/interfaceSupport.inline.hpp"
54 #include "runtime/mutexLocker.hpp"
55 #include "runtime/safepointVerifiers.hpp"
56 #include "runtime/timerTrace.hpp"
57 #include "runtime/trimNativeHeap.hpp"
58 #include "runtime/vmOperations.hpp"
59 #include "services/diagnosticCommand.hpp"
60 #include "utilities/concurrentHashTable.inline.hpp"
61 #include "utilities/concurrentHashTableTasks.inline.hpp"
62 #include "utilities/macros.hpp"
63 #include "utilities/resizeableResourceHash.hpp"
64 #include "utilities/utf8.hpp"
65 #if INCLUDE_G1GC
66 #include "gc/g1/g1CollectedHeap.hpp"
67 #endif
68
69 // We prefer short chains of avg 2
70 const double PREF_AVG_LIST_LEN = 2.0;
71 // 2^24 is max size
72 const size_t END_SIZE = 24;
73 // If a chain gets to 100 something might be wrong
74 const size_t REHASH_LEN = 100;
75 // If we have as many dead items as 50% of the number of bucket
76 const double CLEAN_DEAD_HIGH_WATER_MARK = 0.5;
77
78 #if INCLUDE_CDS_JAVA_HEAP
79 bool StringTable::_is_two_dimensional_shared_strings_array = false;
80 OopHandle StringTable::_shared_strings_array;
81 int StringTable::_shared_strings_array_root_index;
82
83 inline oop StringTable::read_string_from_compact_hashtable(address base_address, u4 index) {
84 assert(ArchiveHeapLoader::is_in_use(), "sanity");
85 objArrayOop array = (objArrayOop)(_shared_strings_array.resolve());
86 oop s;
87
88 if (!_is_two_dimensional_shared_strings_array) {
89 s = array->obj_at((int)index);
90 } else {
91 int primary_index = index >> _secondary_array_index_bits;
92 int secondary_index = index & _secondary_array_index_mask;
93 objArrayOop secondary = (objArrayOop)array->obj_at(primary_index);
94 s = secondary->obj_at(secondary_index);
95 }
96
97 assert(java_lang_String::is_instance(s), "must be");
98 return s;
99 }
100
101 typedef CompactHashtable<
102 const StringTable::StringWrapper&, oop,
103 StringTable::read_string_from_compact_hashtable,
104 StringTable::wrapped_string_equals> SharedStringTable;
105
106 static SharedStringTable _shared_table;
107 #endif
108
109 // --------------------------------------------------------------------------
110
111 typedef ConcurrentHashTable<StringTableConfig, mtSymbol> StringTableHash;
112 static StringTableHash* _local_table = nullptr;
113
114 volatile bool StringTable::_has_work = false;
115 volatile bool StringTable::_needs_rehashing = false;
116 OopStorage* StringTable::_oop_storage;
117
118 static size_t _current_size = 0;
119 static volatile size_t _items_count = 0;
120
121 volatile bool _alt_hash = false;
122
123 static bool _rehashed = false;
124 static uint64_t _alt_hash_seed = 0;
125
126 enum class StringType {
127 OopStr, UnicodeStr, SymbolStr, UTF8Str
128 };
129
130 struct StringWrapperInternal {
131 union {
132 const Handle oop_str;
133 const jchar* unicode_str;
134 const Symbol* symbol_str;
135 const char* utf8_str;
136 };
137 const StringType type;
138 const size_t length;
139
140 StringWrapperInternal(const Handle oop_str, const size_t length) : oop_str(oop_str), type(StringType::OopStr), length(length) {}
141 StringWrapperInternal(const jchar* unicode_str, const size_t length) : unicode_str(unicode_str), type(StringType::UnicodeStr), length(length) {}
142 StringWrapperInternal(const Symbol* symbol_str, const size_t length) : symbol_str(symbol_str), type(StringType::SymbolStr), length(length) {}
143 StringWrapperInternal(const char* utf8_str, const size_t length) : utf8_str(utf8_str), type(StringType::UTF8Str), length(length) {}
144 };
145
146 static unsigned int hash_string(const jchar* s, int len, bool useAlt) {
147 return useAlt ?
148 AltHashing::halfsiphash_32(_alt_hash_seed, s, len) :
149 java_lang_String::hash_code(s, len);
150 }
151
152 const char* StringTable::get_symbol_utf8(const StringWrapper& symbol) {
153 return reinterpret_cast<const char*>(symbol.symbol_str->bytes());
154 }
155
156 unsigned int StringTable::hash_wrapped_string(const StringWrapper& wrapped_str) {
157 switch (wrapped_str.type) {
158 case StringType::OopStr:
159 return java_lang_String::hash_code(wrapped_str.oop_str());
160 case StringType::UnicodeStr:
161 return java_lang_String::hash_code(wrapped_str.unicode_str, static_cast<int>(wrapped_str.length));
162 case StringType::SymbolStr:
163 return java_lang_String::hash_code(get_symbol_utf8(wrapped_str), wrapped_str.length);
164 case StringType::UTF8Str:
165 return java_lang_String::hash_code(wrapped_str.utf8_str, wrapped_str.length);
166 default:
167 ShouldNotReachHere();
168 }
169 return 0;
170 }
171
172 // Unnamed int needed to fit CompactHashtable's equals type signature
173 bool StringTable::wrapped_string_equals(oop java_string, const StringWrapper& wrapped_str, int) {
174 switch (wrapped_str.type) {
175 case StringType::OopStr:
176 return java_lang_String::equals(java_string, wrapped_str.oop_str());
177 case StringType::UnicodeStr:
178 return java_lang_String::equals(java_string, wrapped_str.unicode_str, static_cast<int>(wrapped_str.length));
179 case StringType::SymbolStr:
180 return java_lang_String::equals(java_string, get_symbol_utf8(wrapped_str), wrapped_str.length);
181 case StringType::UTF8Str:
182 return java_lang_String::equals(java_string, wrapped_str.utf8_str, wrapped_str.length);
183 default:
184 ShouldNotReachHere();
185 }
186 return false;
187 }
188
189 class StringTableConfig : public StackObj {
190 private:
191 public:
192 typedef WeakHandle Value;
193
194 static uintx get_hash(Value const& value, bool* is_dead) {
195 oop val_oop = value.peek();
196 if (val_oop == nullptr) {
197 *is_dead = true;
198 return 0;
199 }
200 *is_dead = false;
201 ResourceMark rm;
202 // All String oops are hashed as unicode
203 int length;
204 jchar* chars = java_lang_String::as_unicode_string_or_null(val_oop, length);
205 if (chars != nullptr) {
206 return hash_string(chars, length, _alt_hash);
207 }
208 vm_exit_out_of_memory(length, OOM_MALLOC_ERROR, "get hash from oop");
209 return 0;
210 }
211 // We use default allocation/deallocation but counted
212 static void* allocate_node(void* context, size_t size, Value const& value) {
213 StringTable::item_added();
214 return AllocateHeap(size, mtSymbol);
215 }
216 static void free_node(void* context, void* memory, Value& value) {
217 value.release(StringTable::_oop_storage);
218 FreeHeap(memory);
219 StringTable::item_removed();
220 }
221 };
222
223 class StringTableLookup : StackObj {
224 uintx _hash;
225
226 protected:
227 Thread* _thread;
228 Handle _found;
229
230 public:
231 StringTableLookup(Thread* thread, uintx hash)
232 : _hash(hash), _thread(thread) {}
233 uintx get_hash() const { return _hash; }
234 bool is_dead(WeakHandle* value) {
235 oop val_oop = value->peek();
236 return val_oop == nullptr;
237 }
238 };
239
240 class StringTableLookupUnicode : public StringTableLookup {
241 private:
242 const jchar* _str;
243 int _len;
244
245 public:
246 StringTableLookupUnicode(Thread* thread, uintx hash, const jchar* key, int len)
247 : StringTableLookup(thread, hash), _str(key), _len(len) {}
248
249 bool equals(const WeakHandle* value) {
250 oop val_oop = value->peek();
251 if (val_oop == nullptr) {
252 return false;
253 }
254 bool equals = java_lang_String::equals(val_oop, _str, _len);
255 if (!equals) {
256 return false;
257 }
258 // Need to resolve weak handle and Handleize through possible safepoint.
259 _found = Handle(_thread, value->resolve());
260 return true;
261 }
262 };
263
264 class StringTableLookupUTF8 : public StringTableLookup {
265 private:
266 const char* _str;
267 size_t _utf8_len;
268
269 public:
270 StringTableLookupUTF8(Thread* thread, uintx hash, const char* key, size_t utf8_len)
271 : StringTableLookup(thread, hash), _str(key), _utf8_len(utf8_len) {}
272
273 bool equals(const WeakHandle* value) {
274 oop val_oop = value->peek();
275 if (val_oop == nullptr) {
276 return false;
277 }
278 bool equals = java_lang_String::equals(val_oop, _str, _utf8_len);
279 if (!equals) {
280 return false;
281 }
282 // Need to resolve weak handle and Handleize through possible safepoint.
283 _found = Handle(_thread, value->resolve());
284 return true;
285 }
286 };
287
288 class StringTableLookupOop : public StringTableLookup {
289 private:
290 Handle _find;
291
292 public:
293 StringTableLookupOop(Thread* thread, uintx hash, Handle handle)
294 : StringTableLookup(thread, hash), _find(handle) {}
295
296 bool equals(WeakHandle* value) {
297 oop val_oop = value->peek();
298 if (val_oop == nullptr) {
299 return false;
300 }
301 bool equals = java_lang_String::equals(_find(), val_oop);
302 if (!equals) {
303 return false;
304 }
305 // Need to resolve weak handle and Handleize through possible safepoint.
306 _found = Handle(_thread, value->resolve());
307 return true;
308 }
309 };
310
311 void StringTable::create_table() {
312 size_t start_size_log_2 = ceil_log2(StringTableSize);
313 _current_size = ((size_t)1) << start_size_log_2;
314 log_trace(stringtable)("Start size: " SIZE_FORMAT " (" SIZE_FORMAT ")",
315 _current_size, start_size_log_2);
316 _local_table = new StringTableHash(start_size_log_2, END_SIZE, REHASH_LEN, true);
317 _oop_storage = OopStorageSet::create_weak("StringTable Weak", mtSymbol);
318 _oop_storage->register_num_dead_callback(&gc_notification);
319
320 #if INCLUDE_CDS_JAVA_HEAP
321 if (ArchiveHeapLoader::is_in_use()) {
322 _shared_strings_array = OopHandle(Universe::vm_global(), HeapShared::get_root(_shared_strings_array_root_index));
323 }
324 #endif
325 }
326
327 void StringTable::item_added() {
328 Atomic::inc(&_items_count);
329 }
330
331 void StringTable::item_removed() {
332 Atomic::dec(&_items_count);
333 }
334
335 double StringTable::get_load_factor() {
336 return double(_items_count)/double(_current_size);
337 }
338
339 double StringTable::get_dead_factor(size_t num_dead) {
340 return double(num_dead)/double(_current_size);
341 }
342
343 size_t StringTable::table_size() {
344 return ((size_t)1) << _local_table->get_size_log2(Thread::current());
345 }
346
347 bool StringTable::has_work() {
348 return Atomic::load_acquire(&_has_work);
349 }
350
351 void StringTable::trigger_concurrent_work() {
352 // Avoid churn on ServiceThread
353 if (!has_work()) {
354 MutexLocker ml(Service_lock, Mutex::_no_safepoint_check_flag);
355 Atomic::store(&_has_work, true);
356 Service_lock->notify_all();
357 }
358 }
359
360 // Probing
361 oop StringTable::lookup(Symbol* symbol) {
362 ResourceMark rm;
363 int length;
364 jchar* chars = symbol->as_unicode(length);
365 return lookup(chars, length);
366 }
367
368 oop StringTable::lookup(const jchar* name, int len) {
369 unsigned int hash = java_lang_String::hash_code(name, len);
370 StringWrapper wrapped_name(name, len);
371 oop string = lookup_shared(wrapped_name, hash);
372 if (string != nullptr) {
373 return string;
374 }
375 if (_alt_hash) {
376 hash = hash_string(name, len, true);
377 }
378 return do_lookup(wrapped_name, hash);
379 }
380
381 class StringTableGet : public StackObj {
382 Thread* _thread;
383 Handle _return;
384 public:
385 StringTableGet(Thread* thread) : _thread(thread) {}
386 void operator()(WeakHandle* val) {
387 oop result = val->resolve();
388 assert(result != nullptr, "Result should be reachable");
389 _return = Handle(_thread, result);
390 }
391 oop get_res_oop() {
392 return _return();
393 }
394 };
395
396 void StringTable::update_needs_rehash(bool rehash) {
397 if (rehash) {
398 _needs_rehashing = true;
399 trigger_concurrent_work();
400 }
401 }
402
403 oop StringTable::do_lookup(const StringWrapper& name, uintx hash) {
404 Thread* thread = Thread::current();
405 StringTableGet stg(thread);
406 bool rehash_warning;
407
408 switch (name.type) {
409 case StringType::OopStr: {
410 StringTableLookupOop lookup(thread, hash, name.oop_str);
411 _local_table->get(thread, lookup, stg, &rehash_warning);
412 break;
413 }
414 case StringType::UnicodeStr: {
415 StringTableLookupUnicode lookup(thread, hash, name.unicode_str, static_cast<int>(name.length));
416 _local_table->get(thread, lookup, stg, &rehash_warning);
417 break;
418 }
419 case StringType::SymbolStr: {
420 StringTableLookupUTF8 lookup(thread, hash, get_symbol_utf8(name), name.length);
421 _local_table->get(thread, lookup, stg, &rehash_warning);
422 break;
423 }
424 case StringType::UTF8Str: {
425 StringTableLookupUTF8 lookup(thread, hash, name.utf8_str, name.length);
426 _local_table->get(thread, lookup, stg, &rehash_warning);
427 break;
428 }
429 default:
430 ShouldNotReachHere();
431 }
432
433 update_needs_rehash(rehash_warning);
434 return stg.get_res_oop();
435 }
436
437 // Converts and allocates to a unicode string and stores the unicode length in len
438 const jchar* StringTable::to_unicode(const StringWrapper& wrapped_str, int &len, TRAPS) {
439 switch (wrapped_str.type) {
440 case StringType::UnicodeStr:
441 len = static_cast<int>(wrapped_str.length);
442 return wrapped_str.unicode_str;
443 case StringType::OopStr:
444 return java_lang_String::as_unicode_string(wrapped_str.oop_str(), len, CHECK_NULL);
445 case StringType::SymbolStr: {
446 const char* utf8_str = get_symbol_utf8(wrapped_str);
447 int unicode_length = UTF8::unicode_length(utf8_str, wrapped_str.symbol_str->utf8_length());
448 jchar* chars = NEW_RESOURCE_ARRAY(jchar, unicode_length);
449 UTF8::convert_to_unicode(utf8_str, chars, unicode_length);
450 len = unicode_length;
451 return chars;
452 }
453 case StringType::UTF8Str: {
454 int unicode_length = UTF8::unicode_length(wrapped_str.utf8_str);
455 jchar* chars = NEW_RESOURCE_ARRAY(jchar, unicode_length);
456 UTF8::convert_to_unicode(wrapped_str.utf8_str, chars, unicode_length);
457 len = unicode_length;
458 return chars;
459 }
460 default:
461 ShouldNotReachHere();
462 }
463 return nullptr;
464 }
465
466 Handle StringTable::handle_from_wrapped_string(const StringWrapper& wrapped_str, TRAPS) {
467 switch (wrapped_str.type) {
468 case StringType::OopStr:
469 return wrapped_str.oop_str;
470 case StringType::UnicodeStr:
471 return java_lang_String::create_from_unicode(wrapped_str.unicode_str, static_cast<int>(wrapped_str.length), THREAD);
472 case StringType::SymbolStr:
473 return java_lang_String::create_from_symbol(wrapped_str.symbol_str, THREAD);
474 case StringType::UTF8Str:
475 return java_lang_String::create_from_str(wrapped_str.utf8_str, THREAD);
476 default:
477 ShouldNotReachHere();
478 }
479 return Handle();
480 }
481
482 // Interning
483 oop StringTable::intern(Symbol* symbol, TRAPS) {
484 if (symbol == nullptr) return nullptr;
485 int length = symbol->utf8_length();
486 StringWrapper name(symbol, length);
487 oop result = intern(name, CHECK_NULL);
488 return result;
489 }
490
491 oop StringTable::intern(oop string, TRAPS) {
492 if (string == nullptr) return nullptr;
493 int length = java_lang_String::length(string);
494 Handle h_string (THREAD, string);
495 StringWrapper name(h_string, length);
496 oop result = intern(name, CHECK_NULL);
497 return result;
498 }
499
500 oop StringTable::intern(const char* utf8_string, TRAPS) {
501 if (utf8_string == nullptr) return nullptr;
502 size_t length = strlen(utf8_string);
503 StringWrapper name(utf8_string, length);
504 oop result = intern(name, CHECK_NULL);
505 return result;
506 }
507
508 oop StringTable::intern(const StringWrapper& name, TRAPS) {
509 // shared table always uses java_lang_String::hash_code
510 unsigned int hash = hash_wrapped_string(name);
511 oop found_string = lookup_shared(name, hash);
512 if (found_string != nullptr) {
513 return found_string;
514 }
515
516 if (_alt_hash) {
517 ResourceMark rm(THREAD);
518 // Convert to unicode for alt hashing
519 int unicode_length;
520 const jchar* chars = to_unicode(name, unicode_length, CHECK_NULL);
521 hash = hash_string(chars, unicode_length, true);
522 }
523
524 found_string = do_lookup(name, hash);
525 if (found_string != nullptr) {
526 return found_string;
527 }
528 return do_intern(name, hash, THREAD);
529 }
530
531 oop StringTable::do_intern(const StringWrapper& name, uintx hash, TRAPS) {
532 HandleMark hm(THREAD); // cleanup strings created
533 Handle string_h = handle_from_wrapped_string(name, CHECK_NULL);
534
535 assert(StringTable::wrapped_string_equals(string_h(), name),
536 "string must be properly initialized");
537
538 // Notify deduplication support that the string is being interned. A string
539 // must never be deduplicated after it has been interned. Doing so interferes
540 // with compiler optimizations done on e.g. interned string literals.
541 if (StringDedup::is_enabled()) {
542 StringDedup::notify_intern(string_h());
543 }
544
545 StringTableLookupOop lookup(THREAD, hash, string_h);
546 StringTableGet stg(THREAD);
547
548 bool rehash_warning;
549 do {
550 // Callers have already looked up the String, so just go to add.
551 WeakHandle wh(_oop_storage, string_h);
552 // The hash table takes ownership of the WeakHandle, even if it's not inserted.
553 if (_local_table->insert(THREAD, lookup, wh, &rehash_warning)) {
554 update_needs_rehash(rehash_warning);
555 return wh.resolve();
556 }
557 // In case another thread did a concurrent add, return value already in the table.
558 // This could fail if the String got gc'ed concurrently, so loop back until success.
559 if (_local_table->get(THREAD, lookup, stg, &rehash_warning)) {
560 update_needs_rehash(rehash_warning);
561 return stg.get_res_oop();
562 }
563 } while(true);
564 }
565
566 // Concurrent work
567 void StringTable::grow(JavaThread* jt) {
568 StringTableHash::GrowTask gt(_local_table);
569 if (!gt.prepare(jt)) {
570 return;
571 }
572 log_trace(stringtable)("Started to grow");
573 {
574 TraceTime timer("Grow", TRACETIME_LOG(Debug, stringtable, perf));
575 while (gt.do_task(jt)) {
576 gt.pause(jt);
577 {
578 ThreadBlockInVM tbivm(jt);
579 }
580 gt.cont(jt);
581 }
582 }
583 gt.done(jt);
584 _current_size = table_size();
585 log_debug(stringtable)("Grown to size:" SIZE_FORMAT, _current_size);
586 }
587
588 struct StringTableDoDelete : StackObj {
589 void operator()(WeakHandle* val) {
590 /* do nothing */
591 }
592 };
593
594 struct StringTableDeleteCheck : StackObj {
595 long _count;
596 long _item;
597 StringTableDeleteCheck() : _count(0), _item(0) {}
598 bool operator()(WeakHandle* val) {
599 ++_item;
600 oop tmp = val->peek();
601 if (tmp == nullptr) {
602 ++_count;
603 return true;
604 } else {
605 return false;
606 }
607 }
608 };
609
610 void StringTable::clean_dead_entries(JavaThread* jt) {
611 StringTableHash::BulkDeleteTask bdt(_local_table);
612 if (!bdt.prepare(jt)) {
613 return;
614 }
615
616 StringTableDeleteCheck stdc;
617 StringTableDoDelete stdd;
618 NativeHeapTrimmer::SuspendMark sm("stringtable");
619 {
620 TraceTime timer("Clean", TRACETIME_LOG(Debug, stringtable, perf));
621 while(bdt.do_task(jt, stdc, stdd)) {
622 bdt.pause(jt);
623 {
624 ThreadBlockInVM tbivm(jt);
625 }
626 bdt.cont(jt);
627 }
628 bdt.done(jt);
629 }
630 log_debug(stringtable)("Cleaned %ld of %ld", stdc._count, stdc._item);
631 }
632
633 void StringTable::gc_notification(size_t num_dead) {
634 log_trace(stringtable)("Uncleaned items:" SIZE_FORMAT, num_dead);
635
636 if (has_work()) {
637 return;
638 }
639
640 double load_factor = StringTable::get_load_factor();
641 double dead_factor = StringTable::get_dead_factor(num_dead);
642 // We should clean/resize if we have more dead than alive,
643 // more items than preferred load factor or
644 // more dead items than water mark.
645 if ((dead_factor > load_factor) ||
646 (load_factor > PREF_AVG_LIST_LEN) ||
647 (dead_factor > CLEAN_DEAD_HIGH_WATER_MARK)) {
648 log_debug(stringtable)("Concurrent work triggered, live factor: %g dead factor: %g",
649 load_factor, dead_factor);
650 trigger_concurrent_work();
651 }
652 }
653
654 bool StringTable::should_grow() {
655 return get_load_factor() > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached();
656 }
657
658 void StringTable::do_concurrent_work(JavaThread* jt) {
659 // Rehash if needed. Rehashing goes to a safepoint but the rest of this
660 // work is concurrent.
661 if (needs_rehashing() && maybe_rehash_table()) {
662 Atomic::release_store(&_has_work, false);
663 return; // done, else grow
664 }
665 log_debug(stringtable, perf)("Concurrent work, live factor: %g", get_load_factor());
666 // We prefer growing, since that also removes dead items
667 if (should_grow()) {
668 grow(jt);
669 } else {
670 clean_dead_entries(jt);
671 }
672 Atomic::release_store(&_has_work, false);
673 }
674
675 // Called at VM_Operation safepoint
676 void StringTable::rehash_table() {
677 assert(SafepointSynchronize::is_at_safepoint(), "must be called at safepoint");
678 // The ServiceThread initiates the rehashing so it is not resizing.
679 assert (_local_table->is_safepoint_safe(), "Should not be resizing now");
680
681 _alt_hash_seed = AltHashing::compute_seed();
682
683 // We use current size, not max size.
684 size_t new_size = _local_table->get_size_log2(Thread::current());
685 StringTableHash* new_table = new StringTableHash(new_size, END_SIZE, REHASH_LEN, true);
686 // Use alt hash from now on
687 _alt_hash = true;
688 _local_table->rehash_nodes_to(Thread::current(), new_table);
689
690 // free old table
691 delete _local_table;
692 _local_table = new_table;
693
694 _rehashed = true;
695 _needs_rehashing = false;
696 }
697
698 bool StringTable::maybe_rehash_table() {
699 log_debug(stringtable)("Table imbalanced, rehashing called.");
700
701 // Grow instead of rehash.
702 if (should_grow()) {
703 log_debug(stringtable)("Choosing growing over rehashing.");
704 _needs_rehashing = false;
705 return false;
706 }
707 // Already rehashed.
708 if (_rehashed) {
709 log_warning(stringtable)("Rehashing already done, still long lists.");
710 _needs_rehashing = false;
711 return false;
712 }
713
714 VM_RehashStringTable op;
715 VMThread::execute(&op);
716 return true; // return true because we tried.
717 }
718
719 // Statistics
720 static size_t literal_size(oop obj) {
721 if (obj == nullptr) {
722 return 0;
723 }
724
725 size_t word_size = obj->size();
726
727 if (obj->klass() == vmClasses::String_klass()) {
728 // This may overcount if String.value arrays are shared.
729 word_size += java_lang_String::value(obj)->size();
730 }
731
732 return word_size * HeapWordSize;
733 }
734
735 struct SizeFunc : StackObj {
736 size_t operator()(WeakHandle* val) {
737 oop s = val->peek();
738 if (s == nullptr) {
739 // Dead
740 return 0;
741 }
742 return literal_size(s);
743 };
744 };
745
746 TableStatistics StringTable::get_table_statistics() {
747 static TableStatistics ts;
748 SizeFunc sz;
749 ts = _local_table->statistics_get(Thread::current(), sz, ts);
750 return ts;
751 }
752
753 void StringTable::print_table_statistics(outputStream* st) {
754 SizeFunc sz;
755 _local_table->statistics_to(Thread::current(), sz, st, "StringTable");
756 #if INCLUDE_CDS_JAVA_HEAP
757 if (!_shared_table.empty()) {
758 _shared_table.print_table_statistics(st, "Shared String Table");
759 }
760 #endif
761 }
762
763 // Verification
764 class VerifyStrings : StackObj {
765 public:
766 bool operator()(WeakHandle* val) {
767 oop s = val->peek();
768 if (s != nullptr) {
769 assert(java_lang_String::length(s) >= 0, "Length on string must work.");
770 }
771 return true;
772 };
773 };
774
775 // This verification is part of Universe::verify() and needs to be quick.
776 void StringTable::verify() {
777 VerifyStrings vs;
778 _local_table->do_safepoint_scan(vs);
779 }
780
781 // Verification and comp
782 class VerifyCompStrings : StackObj {
783 static unsigned string_hash(oop const& str) {
784 return java_lang_String::hash_code_noupdate(str);
785 }
786 static bool string_equals(oop const& a, oop const& b) {
787 return java_lang_String::equals(a, b);
788 }
789
790 ResizeableResourceHashtable<oop, bool, AnyObj::C_HEAP, mtInternal,
791 string_hash, string_equals> _table;
792 public:
793 size_t _errors;
794 VerifyCompStrings() : _table(unsigned(_items_count / 8) + 1, 0 /* do not resize */), _errors(0) {}
795 bool operator()(WeakHandle* val) {
796 oop s = val->resolve();
797 if (s == nullptr) {
798 return true;
799 }
800 bool created;
801 _table.put_if_absent(s, true, &created);
802 assert(created, "Duplicate strings");
803 if (!created) {
804 _errors++;
805 }
806 return true;
807 };
808 };
809
810 size_t StringTable::verify_and_compare_entries() {
811 Thread* thr = Thread::current();
812 VerifyCompStrings vcs;
813 _local_table->do_scan(thr, vcs);
814 return vcs._errors;
815 }
816
817 static void print_string(Thread* current, outputStream* st, oop s) {
818 typeArrayOop value = java_lang_String::value_no_keepalive(s);
819 int length = java_lang_String::length(s);
820 bool is_latin1 = java_lang_String::is_latin1(s);
821
822 if (length <= 0) {
823 st->print("%d: ", length);
824 } else {
825 ResourceMark rm(current);
826 size_t utf8_length = length;
827 char* utf8_string;
828
829 if (!is_latin1) {
830 jchar* chars = value->char_at_addr(0);
831 utf8_string = UNICODE::as_utf8(chars, utf8_length);
832 } else {
833 jbyte* bytes = value->byte_at_addr(0);
834 utf8_string = UNICODE::as_utf8(bytes, utf8_length);
835 }
836
837 st->print("%zu: ", utf8_length);
838 HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
839 }
840 st->cr();
841 }
842
843 // Dumping
844 class PrintString : StackObj {
845 Thread* _thr;
846 outputStream* _st;
847 public:
848 PrintString(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
849 bool operator()(WeakHandle* val) {
850 oop s = val->peek();
851 if (s == nullptr) {
852 return true;
853 }
854 print_string(_thr, _st, s);
855 return true;
856 };
857 };
858
859 class PrintSharedString : StackObj {
860 Thread* _thr;
861 outputStream* _st;
862 public:
863 PrintSharedString(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
864 void do_value(oop s) {
865 if (s == nullptr) {
866 return;
867 }
868 print_string(_thr, _st, s);
869 };
870 };
871
872 void StringTable::dump(outputStream* st, bool verbose) {
873 if (!verbose) {
874 print_table_statistics(st);
875 } else {
876 Thread* thr = Thread::current();
877 ResourceMark rm(thr);
878 st->print_cr("VERSION: 1.1");
879 PrintString ps(thr, st);
880 if (!_local_table->try_scan(thr, ps)) {
881 st->print_cr("dump unavailable at this moment");
882 }
883 #if INCLUDE_CDS_JAVA_HEAP
884 if (!_shared_table.empty()) {
885 st->print_cr("#----------------");
886 st->print_cr("# Shared strings:");
887 st->print_cr("#----------------");
888 PrintSharedString pss(thr, st);
889 _shared_table.iterate(&pss);
890 }
891 #endif
892 }
893 }
894
895 // Utility for dumping strings
896 StringtableDCmd::StringtableDCmd(outputStream* output, bool heap) :
897 DCmdWithParser(output, heap),
898 _verbose("-verbose", "Dump the content of each string in the table",
899 "BOOLEAN", false, "false") {
900 _dcmdparser.add_dcmd_option(&_verbose);
901 }
902
903 void StringtableDCmd::execute(DCmdSource source, TRAPS) {
904 VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpStrings,
905 _verbose.value());
906 VMThread::execute(&dumper);
907 }
908
909 // Sharing
910 #if INCLUDE_CDS_JAVA_HEAP
911 size_t StringTable::shared_entry_count() {
912 return _shared_table.entry_count();
913 }
914
915 oop StringTable::lookup_shared(const StringWrapper& name, unsigned int hash) {
916 assert(hash == hash_wrapped_string(name),
917 "hash must be computed using java_lang_String::hash_code");
918 // len is required but is already part of StringWrapper, so 0 is used
919 return _shared_table.lookup(name, hash, 0);
920 }
921
922 oop StringTable::lookup_shared(const jchar* name, int len) {
923 StringWrapper wrapped_name(name, len);
924 // len is required but is already part of StringWrapper, so 0 is used
925 return _shared_table.lookup(wrapped_name, java_lang_String::hash_code(name, len), 0);
926 }
927
928 // This is called BEFORE we enter the CDS safepoint. We can allocate heap objects.
929 // This should be called when we know no more strings will be added (which will be easy
930 // to guarantee because CDS runs with a single Java thread. See JDK-8253495.)
931 void StringTable::allocate_shared_strings_array(TRAPS) {
932 if (!CDSConfig::is_dumping_heap()) {
933 return;
934 }
935 if (_items_count > (size_t)max_jint) {
936 fatal("Too many strings to be archived: %zu", _items_count);
937 }
938
939 int total = (int)_items_count;
940 size_t single_array_size = objArrayOopDesc::object_size(total);
941
942 log_info(cds)("allocated string table for %d strings", total);
943
944 if (!ArchiveHeapWriter::is_too_large_to_archive(single_array_size)) {
945 // The entire table can fit in a single array
946 objArrayOop array = oopFactory::new_objArray(vmClasses::Object_klass(), total, CHECK);
947 _shared_strings_array = OopHandle(Universe::vm_global(), array);
948 log_info(cds)("string table array (single level) length = %d", total);
949 } else {
950 // Split the table in two levels of arrays.
951 int primary_array_length = (total + _secondary_array_max_length - 1) / _secondary_array_max_length;
952 size_t primary_array_size = objArrayOopDesc::object_size(primary_array_length);
953 size_t secondary_array_size = objArrayOopDesc::object_size(_secondary_array_max_length);
954
955 if (ArchiveHeapWriter::is_too_large_to_archive(secondary_array_size)) {
956 // This can only happen if you have an extremely large number of classes that
957 // refer to more than 16384 * 16384 = 26M interned strings! Not a practical concern
958 // but bail out for safety.
959 log_error(cds)("Too many strings to be archived: %zu", _items_count);
960 MetaspaceShared::unrecoverable_writing_error();
961 }
962
963 objArrayOop primary = oopFactory::new_objArray(vmClasses::Object_klass(), primary_array_length, CHECK);
964 objArrayHandle primaryHandle(THREAD, primary);
965 _shared_strings_array = OopHandle(Universe::vm_global(), primary);
966
967 log_info(cds)("string table array (primary) length = %d", primary_array_length);
968 for (int i = 0; i < primary_array_length; i++) {
969 int len;
970 if (total > _secondary_array_max_length) {
971 len = _secondary_array_max_length;
972 } else {
973 len = total;
974 }
975 total -= len;
976
977 objArrayOop secondary = oopFactory::new_objArray(vmClasses::Object_klass(), len, CHECK);
978 primaryHandle()->obj_at_put(i, secondary);
979
980 log_info(cds)("string table array (secondary)[%d] length = %d", i, len);
981 assert(!ArchiveHeapWriter::is_too_large_to_archive(secondary), "sanity");
982 }
983
984 assert(total == 0, "must be");
985 _is_two_dimensional_shared_strings_array = true;
986 }
987 }
988
989 #ifndef PRODUCT
990 void StringTable::verify_secondary_array_index_bits() {
991 int max;
992 for (max = 1; ; max++) {
993 size_t next_size = objArrayOopDesc::object_size(1 << (max + 1));
994 if (ArchiveHeapWriter::is_too_large_to_archive(next_size)) {
995 break;
996 }
997 }
998 // Currently max is 17 for +UseCompressedOops, 16 for -UseCompressedOops.
999 // When we add support for Shenandoah (which has a smaller mininum region size than G1),
1000 // max will become 15/14.
1001 //
1002 // We use _secondary_array_index_bits==14 as that will be the eventual value, and will
1003 // make testing easier.
1004 assert(_secondary_array_index_bits <= max,
1005 "_secondary_array_index_bits (%d) must be smaller than max possible value (%d)",
1006 _secondary_array_index_bits, max);
1007 }
1008 #endif // PRODUCT
1009
1010 // This is called AFTER we enter the CDS safepoint.
1011 //
1012 // For each shared string:
1013 // [1] Store it into _shared_strings_array. Encode its position as a 32-bit index.
1014 // [2] Store the index and hashcode into _shared_table.
1015 oop StringTable::init_shared_table(const DumpedInternedStrings* dumped_interned_strings) {
1016 assert(HeapShared::can_write(), "must be");
1017 objArrayOop array = (objArrayOop)(_shared_strings_array.resolve());
1018
1019 verify_secondary_array_index_bits();
1020
1021 _shared_table.reset();
1022 CompactHashtableWriter writer((int)_items_count, ArchiveBuilder::string_stats());
1023
1024 int index = 0;
1025 auto copy_into_array = [&] (oop string, bool value_ignored) {
1026 unsigned int hash = java_lang_String::hash_code(string);
1027 writer.add(hash, index);
1028
1029 if (!_is_two_dimensional_shared_strings_array) {
1030 assert(index < array->length(), "no strings should have been added");
1031 array->obj_at_put(index, string);
1032 } else {
1033 int primary_index = index >> _secondary_array_index_bits;
1034 int secondary_index = index & _secondary_array_index_mask;
1035
1036 assert(primary_index < array->length(), "no strings should have been added");
1037 objArrayOop secondary = (objArrayOop)array->obj_at(primary_index);
1038
1039 assert(secondary != nullptr && secondary->is_objArray(), "must be");
1040 assert(secondary_index < secondary->length(), "no strings should have been added");
1041 secondary->obj_at_put(secondary_index, string);
1042 }
1043
1044 index ++;
1045 };
1046 dumped_interned_strings->iterate_all(copy_into_array);
1047
1048 writer.dump(&_shared_table, "string");
1049
1050 return array;
1051 }
1052
1053 void StringTable::set_shared_strings_array_index(int root_index) {
1054 _shared_strings_array_root_index = root_index;
1055 }
1056
1057 void StringTable::serialize_shared_table_header(SerializeClosure* soc) {
1058 if (soc->writing() && !HeapShared::can_write()) {
1059 _shared_table.reset();
1060 _is_two_dimensional_shared_strings_array = false;
1061 _shared_strings_array_root_index = -1;
1062 }
1063
1064 _shared_table.serialize_header(soc);
1065
1066 if (soc->writing()) {
1067 // Sanity. Make sure we don't use the shared table at dump time
1068 _shared_table.reset();
1069 } else if (!ArchiveHeapLoader::is_in_use()) {
1070 _shared_table.reset();
1071 }
1072
1073 soc->do_bool(&_is_two_dimensional_shared_strings_array);
1074 soc->do_int(&_shared_strings_array_root_index);
1075 }
1076 #endif //INCLUDE_CDS_JAVA_HEAP