1 /*
2 * Copyright (c) 1997, 2025, 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 "cds/archiveBuilder.hpp"
26 #include "cds/archiveHeapLoader.inline.hpp"
27 #include "cds/archiveHeapWriter.hpp"
28 #include "cds/cdsConfig.hpp"
29 #include "cds/heapShared.hpp"
30 #include "classfile/altHashing.hpp"
31 #include "classfile/compactHashtable.hpp"
32 #include "classfile/javaClasses.inline.hpp"
33 #include "classfile/stringTable.hpp"
34 #include "classfile/vmClasses.hpp"
35 #include "compiler/compileBroker.hpp"
36 #include "gc/shared/collectedHeap.hpp"
37 #include "gc/shared/oopStorage.inline.hpp"
38 #include "gc/shared/oopStorageSet.hpp"
39 #include "gc/shared/stringdedup/stringDedup.hpp"
40 #include "logging/log.hpp"
41 #include "logging/logStream.hpp"
42 #include "memory/allocation.inline.hpp"
43 #include "memory/oopFactory.hpp"
44 #include "memory/resourceArea.hpp"
45 #include "oops/access.inline.hpp"
46 #include "oops/compressedOops.hpp"
47 #include "oops/oop.inline.hpp"
48 #include "oops/typeArrayOop.inline.hpp"
49 #include "oops/weakHandle.inline.hpp"
50 #include "runtime/atomic.hpp"
51 #include "runtime/handles.inline.hpp"
52 #include "runtime/interfaceSupport.inline.hpp"
53 #include "runtime/mutexLocker.hpp"
54 #include "runtime/safepointVerifiers.hpp"
55 #include "runtime/timerTrace.hpp"
56 #include "runtime/trimNativeHeap.hpp"
57 #include "runtime/vmOperations.hpp"
58 #include "services/diagnosticCommand.hpp"
59 #include "utilities/concurrentHashTable.inline.hpp"
60 #include "utilities/concurrentHashTableTasks.inline.hpp"
61 #include "utilities/macros.hpp"
62 #include "utilities/resizeableResourceHash.hpp"
63 #include "utilities/utf8.hpp"
64 #if INCLUDE_G1GC
65 #include "gc/g1/g1CollectedHeap.hpp"
66 #endif
67
68 // We prefer short chains of avg 2
69 const double PREF_AVG_LIST_LEN = 2.0;
70 // 2^24 is max size
71 const size_t END_SIZE = 24;
72 // If a chain gets to 100 something might be wrong
73 const size_t REHASH_LEN = 100;
74 // If we have as many dead items as 50% of the number of bucket
75 const double CLEAN_DEAD_HIGH_WATER_MARK = 0.5;
76
77 #if INCLUDE_CDS_JAVA_HEAP
78 bool StringTable::_is_two_dimensional_shared_strings_array = false;
79 OopHandle StringTable::_shared_strings_array;
80 int StringTable::_shared_strings_array_root_index;
81
82 inline oop StringTable::read_string_from_compact_hashtable(address base_address, u4 index) {
83 assert(ArchiveHeapLoader::is_in_use(), "sanity");
84 objArrayOop array = (objArrayOop)(_shared_strings_array.resolve());
85 oop s;
86
87 if (!_is_two_dimensional_shared_strings_array) {
88 s = array->obj_at((int)index);
89 } else {
90 int primary_index = index >> _secondary_array_index_bits;
91 int secondary_index = index & _secondary_array_index_mask;
92 objArrayOop secondary = (objArrayOop)array->obj_at(primary_index);
93 s = secondary->obj_at(secondary_index);
94 }
95
96 assert(java_lang_String::is_instance(s), "must be");
97 return s;
98 }
99
100 typedef CompactHashtable<
101 const StringTable::StringWrapper&, oop,
102 StringTable::read_string_from_compact_hashtable,
103 StringTable::wrapped_string_equals> SharedStringTable;
104
105 static SharedStringTable _shared_table;
106 #endif
107
108 // --------------------------------------------------------------------------
109
110 typedef ConcurrentHashTable<StringTableConfig, mtSymbol> StringTableHash;
111 static StringTableHash* _local_table = nullptr;
112
113 volatile bool StringTable::_has_work = false;
114 volatile bool StringTable::_needs_rehashing = false;
115 OopStorage* StringTable::_oop_storage;
116
117 static size_t _current_size = 0;
118 static volatile size_t _items_count = 0;
119 DEBUG_ONLY(static bool _disable_interning_during_cds_dump = false);
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 = log2i_ceil(StringTableSize);
313 _current_size = ((size_t)1) << start_size_log_2;
314 log_trace(stringtable)("Start size: %zu (%zu)",
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 size_t StringTable::items_count_acquire() {
352 return Atomic::load_acquire(&_items_count);
353 }
354
355 void StringTable::trigger_concurrent_work() {
356 // Avoid churn on ServiceThread
357 if (!has_work()) {
358 MutexLocker ml(Service_lock, Mutex::_no_safepoint_check_flag);
359 Atomic::store(&_has_work, true);
360 Service_lock->notify_all();
361 }
362 }
363
364 // Probing
365 oop StringTable::lookup(Symbol* symbol) {
366 ResourceMark rm;
367 int length;
368 jchar* chars = symbol->as_unicode(length);
369 return lookup(chars, length);
370 }
371
372 oop StringTable::lookup(const jchar* name, int len) {
373 unsigned int hash = java_lang_String::hash_code(name, len);
374 StringWrapper wrapped_name(name, len);
375 oop string = lookup_shared(wrapped_name, hash);
376 if (string != nullptr) {
377 return string;
378 }
379 if (_alt_hash) {
380 hash = hash_string(name, len, true);
381 }
382 return do_lookup(wrapped_name, hash);
383 }
384
385 class StringTableGet : public StackObj {
386 Thread* _thread;
387 Handle _return;
388 public:
389 StringTableGet(Thread* thread) : _thread(thread) {}
390 void operator()(WeakHandle* val) {
391 oop result = val->resolve();
392 assert(result != nullptr, "Result should be reachable");
393 _return = Handle(_thread, result);
394 }
395 oop get_res_oop() {
396 return _return();
397 }
398 };
399
400 void StringTable::update_needs_rehash(bool rehash) {
401 if (rehash) {
402 _needs_rehashing = true;
403 trigger_concurrent_work();
404 }
405 }
406
407 oop StringTable::do_lookup(const StringWrapper& name, uintx hash) {
408 Thread* thread = Thread::current();
409 StringTableGet stg(thread);
410 bool rehash_warning;
411
412 switch (name.type) {
413 case StringType::OopStr: {
414 StringTableLookupOop lookup(thread, hash, name.oop_str);
415 _local_table->get(thread, lookup, stg, &rehash_warning);
416 break;
417 }
418 case StringType::UnicodeStr: {
419 StringTableLookupUnicode lookup(thread, hash, name.unicode_str, static_cast<int>(name.length));
420 _local_table->get(thread, lookup, stg, &rehash_warning);
421 break;
422 }
423 case StringType::SymbolStr: {
424 StringTableLookupUTF8 lookup(thread, hash, get_symbol_utf8(name), name.length);
425 _local_table->get(thread, lookup, stg, &rehash_warning);
426 break;
427 }
428 case StringType::UTF8Str: {
429 StringTableLookupUTF8 lookup(thread, hash, name.utf8_str, name.length);
430 _local_table->get(thread, lookup, stg, &rehash_warning);
431 break;
432 }
433 default:
434 ShouldNotReachHere();
435 }
436
437 update_needs_rehash(rehash_warning);
438 return stg.get_res_oop();
439 }
440
441 // Converts and allocates to a unicode string and stores the unicode length in len
442 const jchar* StringTable::to_unicode(const StringWrapper& wrapped_str, int &len, TRAPS) {
443 switch (wrapped_str.type) {
444 case StringType::UnicodeStr:
445 len = static_cast<int>(wrapped_str.length);
446 return wrapped_str.unicode_str;
447 case StringType::OopStr:
448 return java_lang_String::as_unicode_string(wrapped_str.oop_str(), len, CHECK_NULL);
449 case StringType::SymbolStr: {
450 const char* utf8_str = get_symbol_utf8(wrapped_str);
451 int unicode_length = UTF8::unicode_length(utf8_str, wrapped_str.symbol_str->utf8_length());
452 jchar* chars = NEW_RESOURCE_ARRAY(jchar, unicode_length);
453 UTF8::convert_to_unicode(utf8_str, chars, unicode_length);
454 len = unicode_length;
455 return chars;
456 }
457 case StringType::UTF8Str: {
458 int unicode_length = UTF8::unicode_length(wrapped_str.utf8_str);
459 jchar* chars = NEW_RESOURCE_ARRAY(jchar, unicode_length);
460 UTF8::convert_to_unicode(wrapped_str.utf8_str, chars, unicode_length);
461 len = unicode_length;
462 return chars;
463 }
464 default:
465 ShouldNotReachHere();
466 }
467 return nullptr;
468 }
469
470 Handle StringTable::handle_from_wrapped_string(const StringWrapper& wrapped_str, TRAPS) {
471 switch (wrapped_str.type) {
472 case StringType::OopStr:
473 return wrapped_str.oop_str;
474 case StringType::UnicodeStr:
475 return java_lang_String::create_from_unicode(wrapped_str.unicode_str, static_cast<int>(wrapped_str.length), THREAD);
476 case StringType::SymbolStr:
477 return java_lang_String::create_from_symbol(wrapped_str.symbol_str, THREAD);
478 case StringType::UTF8Str:
479 return java_lang_String::create_from_str(wrapped_str.utf8_str, THREAD);
480 default:
481 ShouldNotReachHere();
482 }
483 return Handle();
484 }
485
486 // Interning
487 oop StringTable::intern(Symbol* symbol, TRAPS) {
488 if (symbol == nullptr) return nullptr;
489 int length = symbol->utf8_length();
490 StringWrapper name(symbol, length);
491 oop result = intern(name, CHECK_NULL);
492 return result;
493 }
494
495 oop StringTable::intern(oop string, TRAPS) {
496 if (string == nullptr) return nullptr;
497 int length = java_lang_String::length(string);
498 Handle h_string (THREAD, string);
499 StringWrapper name(h_string, length);
500 oop result = intern(name, CHECK_NULL);
501 return result;
502 }
503
504 oop StringTable::intern(const char* utf8_string, TRAPS) {
505 if (utf8_string == nullptr) return nullptr;
506 size_t length = strlen(utf8_string);
507 StringWrapper name(utf8_string, length);
508 oop result = intern(name, CHECK_NULL);
509 return result;
510 }
511
512 oop StringTable::intern(const StringWrapper& name, TRAPS) {
513 assert(!Atomic::load_acquire(&_disable_interning_during_cds_dump),
514 "All threads that may intern strings should have been stopped before CDS starts copying the interned string table");
515
516 // shared table always uses java_lang_String::hash_code
517 unsigned int hash = hash_wrapped_string(name);
518 oop found_string = lookup_shared(name, hash);
519 if (found_string != nullptr) {
520 return found_string;
521 }
522
523 if (_alt_hash) {
524 ResourceMark rm(THREAD);
525 // Convert to unicode for alt hashing
526 int unicode_length;
527 const jchar* chars = to_unicode(name, unicode_length, CHECK_NULL);
528 hash = hash_string(chars, unicode_length, true);
529 }
530
531 found_string = do_lookup(name, hash);
532 if (found_string != nullptr) {
533 return found_string;
534 }
535 return do_intern(name, hash, THREAD);
536 }
537
538 oop StringTable::do_intern(const StringWrapper& name, uintx hash, TRAPS) {
539 HandleMark hm(THREAD); // cleanup strings created
540 Handle string_h = handle_from_wrapped_string(name, CHECK_NULL);
541
542 assert(StringTable::wrapped_string_equals(string_h(), name),
543 "string must be properly initialized");
544
545 // Notify deduplication support that the string is being interned. A string
546 // must never be deduplicated after it has been interned. Doing so interferes
547 // with compiler optimizations done on e.g. interned string literals.
548 if (StringDedup::is_enabled()) {
549 StringDedup::notify_intern(string_h());
550 }
551
552 StringTableLookupOop lookup(THREAD, hash, string_h);
553 StringTableGet stg(THREAD);
554
555 bool rehash_warning;
556 do {
557 // Callers have already looked up the String, so just go to add.
558 WeakHandle wh(_oop_storage, string_h);
559 // The hash table takes ownership of the WeakHandle, even if it's not inserted.
560 if (_local_table->insert(THREAD, lookup, wh, &rehash_warning)) {
561 update_needs_rehash(rehash_warning);
562 return wh.resolve();
563 }
564 // In case another thread did a concurrent add, return value already in the table.
565 // This could fail if the String got gc'ed concurrently, so loop back until success.
566 if (_local_table->get(THREAD, lookup, stg, &rehash_warning)) {
567 update_needs_rehash(rehash_warning);
568 return stg.get_res_oop();
569 }
570 } while(true);
571 }
572
573 // Concurrent work
574 void StringTable::grow(JavaThread* jt) {
575 StringTableHash::GrowTask gt(_local_table);
576 if (!gt.prepare(jt)) {
577 return;
578 }
579 log_trace(stringtable)("Started to grow");
580 {
581 TraceTime timer("Grow", TRACETIME_LOG(Debug, stringtable, perf));
582 while (gt.do_task(jt)) {
583 gt.pause(jt);
584 {
585 ThreadBlockInVM tbivm(jt);
586 }
587 gt.cont(jt);
588 }
589 }
590 gt.done(jt);
591 _current_size = table_size();
592 log_debug(stringtable)("Grown to size:%zu", _current_size);
593 }
594
595 struct StringTableDoDelete : StackObj {
596 void operator()(WeakHandle* val) {
597 /* do nothing */
598 }
599 };
600
601 struct StringTableDeleteCheck : StackObj {
602 long _count;
603 long _item;
604 StringTableDeleteCheck() : _count(0), _item(0) {}
605 bool operator()(WeakHandle* val) {
606 ++_item;
607 oop tmp = val->peek();
608 if (tmp == nullptr) {
609 ++_count;
610 return true;
611 } else {
612 return false;
613 }
614 }
615 };
616
617 void StringTable::clean_dead_entries(JavaThread* jt) {
618 StringTableHash::BulkDeleteTask bdt(_local_table);
619 if (!bdt.prepare(jt)) {
620 return;
621 }
622
623 StringTableDeleteCheck stdc;
624 StringTableDoDelete stdd;
625 NativeHeapTrimmer::SuspendMark sm("stringtable");
626 {
627 TraceTime timer("Clean", TRACETIME_LOG(Debug, stringtable, perf));
628 while(bdt.do_task(jt, stdc, stdd)) {
629 bdt.pause(jt);
630 {
631 ThreadBlockInVM tbivm(jt);
632 }
633 bdt.cont(jt);
634 }
635 bdt.done(jt);
636 }
637 log_debug(stringtable)("Cleaned %ld of %ld", stdc._count, stdc._item);
638 }
639
640 void StringTable::gc_notification(size_t num_dead) {
641 log_trace(stringtable)("Uncleaned items:%zu", num_dead);
642
643 if (has_work()) {
644 return;
645 }
646
647 double load_factor = StringTable::get_load_factor();
648 double dead_factor = StringTable::get_dead_factor(num_dead);
649 // We should clean/resize if we have more dead than alive,
650 // more items than preferred load factor or
651 // more dead items than water mark.
652 if ((dead_factor > load_factor) ||
653 (load_factor > PREF_AVG_LIST_LEN) ||
654 (dead_factor > CLEAN_DEAD_HIGH_WATER_MARK)) {
655 log_debug(stringtable)("Concurrent work triggered, live factor: %g dead factor: %g",
656 load_factor, dead_factor);
657 trigger_concurrent_work();
658 }
659 }
660
661 bool StringTable::should_grow() {
662 return get_load_factor() > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached();
663 }
664
665 void StringTable::do_concurrent_work(JavaThread* jt) {
666 // Rehash if needed. Rehashing goes to a safepoint but the rest of this
667 // work is concurrent.
668 if (needs_rehashing() && maybe_rehash_table()) {
669 Atomic::release_store(&_has_work, false);
670 return; // done, else grow
671 }
672 log_debug(stringtable, perf)("Concurrent work, live factor: %g", get_load_factor());
673 // We prefer growing, since that also removes dead items
674 if (should_grow()) {
675 grow(jt);
676 } else {
677 clean_dead_entries(jt);
678 }
679 Atomic::release_store(&_has_work, false);
680 }
681
682 // Called at VM_Operation safepoint
683 void StringTable::rehash_table() {
684 assert(SafepointSynchronize::is_at_safepoint(), "must be called at safepoint");
685 // The ServiceThread initiates the rehashing so it is not resizing.
686 assert (_local_table->is_safepoint_safe(), "Should not be resizing now");
687
688 _alt_hash_seed = AltHashing::compute_seed();
689
690 // We use current size, not max size.
691 size_t new_size = _local_table->get_size_log2(Thread::current());
692 StringTableHash* new_table = new StringTableHash(new_size, END_SIZE, REHASH_LEN, true);
693 // Use alt hash from now on
694 _alt_hash = true;
695 _local_table->rehash_nodes_to(Thread::current(), new_table);
696
697 // free old table
698 delete _local_table;
699 _local_table = new_table;
700
701 _rehashed = true;
702 _needs_rehashing = false;
703 }
704
705 bool StringTable::maybe_rehash_table() {
706 log_debug(stringtable)("Table imbalanced, rehashing called.");
707
708 // Grow instead of rehash.
709 if (should_grow()) {
710 log_debug(stringtable)("Choosing growing over rehashing.");
711 _needs_rehashing = false;
712 return false;
713 }
714 // Already rehashed.
715 if (_rehashed) {
716 log_warning(stringtable)("Rehashing already done, still long lists.");
717 _needs_rehashing = false;
718 return false;
719 }
720
721 VM_RehashStringTable op;
722 VMThread::execute(&op);
723 return true; // return true because we tried.
724 }
725
726 // Statistics
727 static size_t literal_size(oop obj) {
728 if (obj == nullptr) {
729 return 0;
730 }
731
732 size_t word_size = obj->size();
733
734 if (obj->klass() == vmClasses::String_klass()) {
735 // This may overcount if String.value arrays are shared.
736 word_size += java_lang_String::value(obj)->size();
737 }
738
739 return word_size * HeapWordSize;
740 }
741
742 struct SizeFunc : StackObj {
743 size_t operator()(WeakHandle* val) {
744 oop s = val->peek();
745 if (s == nullptr) {
746 // Dead
747 return 0;
748 }
749 return literal_size(s);
750 };
751 };
752
753 TableStatistics StringTable::get_table_statistics() {
754 static TableStatistics ts;
755 SizeFunc sz;
756
757 Thread* jt = Thread::current();
758 StringTableHash::StatisticsTask sts(_local_table);
759 if (!sts.prepare(jt)) {
760 return ts; // return old table statistics
761 }
762 {
763 TraceTime timer("GetStatistics", TRACETIME_LOG(Debug, stringtable, perf));
764 while (sts.do_task(jt, sz)) {
765 sts.pause(jt);
766 if (jt->is_Java_thread()) {
767 ThreadBlockInVM tbivm(JavaThread::cast(jt));
768 }
769 sts.cont(jt);
770 }
771 }
772 ts = sts.done(jt);
773 return ts;
774 }
775
776 void StringTable::print_table_statistics(outputStream* st) {
777 TableStatistics ts = get_table_statistics();
778 ts.print(st, "StringTable");
779 #if INCLUDE_CDS_JAVA_HEAP
780 if (!_shared_table.empty()) {
781 _shared_table.print_table_statistics(st, "Shared String Table");
782 }
783 #endif
784 }
785
786 // Verification
787 class VerifyStrings : StackObj {
788 public:
789 bool operator()(WeakHandle* val) {
790 oop s = val->peek();
791 if (s != nullptr) {
792 assert(java_lang_String::length(s) >= 0, "Length on string must work.");
793 }
794 return true;
795 };
796 };
797
798 // This verification is part of Universe::verify() and needs to be quick.
799 void StringTable::verify() {
800 VerifyStrings vs;
801 _local_table->do_safepoint_scan(vs);
802 }
803
804 // Verification and comp
805 class StringTable::VerifyCompStrings : StackObj {
806 static unsigned string_hash(oop const& str) {
807 return java_lang_String::hash_code_noupdate(str);
808 }
809 static bool string_equals(oop const& a, oop const& b) {
810 return java_lang_String::equals(a, b);
811 }
812
813 ResizeableResourceHashtable<oop, bool, AnyObj::C_HEAP, mtInternal,
814 string_hash, string_equals> _table;
815 public:
816 size_t _errors;
817 VerifyCompStrings() : _table(unsigned(items_count_acquire() / 8) + 1, 0 /* do not resize */), _errors(0) {}
818 bool operator()(WeakHandle* val) {
819 oop s = val->resolve();
820 if (s == nullptr) {
821 return true;
822 }
823 bool created;
824 _table.put_if_absent(s, true, &created);
825 assert(created, "Duplicate strings");
826 if (!created) {
827 _errors++;
828 }
829 return true;
830 };
831 };
832
833 size_t StringTable::verify_and_compare_entries() {
834 Thread* thr = Thread::current();
835 VerifyCompStrings vcs;
836 _local_table->do_scan(thr, vcs);
837 return vcs._errors;
838 }
839
840 static void print_string(Thread* current, outputStream* st, oop s) {
841 typeArrayOop value = java_lang_String::value_no_keepalive(s);
842 int length = java_lang_String::length(s);
843 bool is_latin1 = java_lang_String::is_latin1(s);
844
845 if (length <= 0) {
846 st->print("%d: ", length);
847 } else {
848 ResourceMark rm(current);
849 size_t utf8_length = length;
850 char* utf8_string;
851
852 if (!is_latin1) {
853 jchar* chars = value->char_at_addr(0);
854 utf8_string = UNICODE::as_utf8(chars, utf8_length);
855 } else {
856 jbyte* bytes = value->byte_at_addr(0);
857 utf8_string = UNICODE::as_utf8(bytes, utf8_length);
858 }
859
860 st->print("%zu: ", utf8_length);
861 HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
862 }
863 st->cr();
864 }
865
866 // Dumping
867 class PrintString : StackObj {
868 Thread* _thr;
869 outputStream* _st;
870 public:
871 PrintString(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
872 bool operator()(WeakHandle* val) {
873 oop s = val->peek();
874 if (s == nullptr) {
875 return true;
876 }
877 print_string(_thr, _st, s);
878 return true;
879 };
880 };
881
882 class PrintSharedString : StackObj {
883 Thread* _thr;
884 outputStream* _st;
885 public:
886 PrintSharedString(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
887 void do_value(oop s) {
888 if (s == nullptr) {
889 return;
890 }
891 print_string(_thr, _st, s);
892 };
893 };
894
895 void StringTable::dump(outputStream* st, bool verbose) {
896 if (!verbose) {
897 print_table_statistics(st);
898 } else {
899 Thread* thr = Thread::current();
900 ResourceMark rm(thr);
901 st->print_cr("VERSION: 1.1");
902 PrintString ps(thr, st);
903 if (!_local_table->try_scan(thr, ps)) {
904 st->print_cr("dump unavailable at this moment");
905 }
906 #if INCLUDE_CDS_JAVA_HEAP
907 if (!_shared_table.empty()) {
908 st->print_cr("#----------------");
909 st->print_cr("# Shared strings:");
910 st->print_cr("#----------------");
911 PrintSharedString pss(thr, st);
912 _shared_table.iterate(&pss);
913 }
914 #endif
915 }
916 }
917
918 // Utility for dumping strings
919 StringtableDCmd::StringtableDCmd(outputStream* output, bool heap) :
920 DCmdWithParser(output, heap),
921 _verbose("-verbose", "Dump the content of each string in the table",
922 "BOOLEAN", false, "false") {
923 _dcmdparser.add_dcmd_option(&_verbose);
924 }
925
926 void StringtableDCmd::execute(DCmdSource source, TRAPS) {
927 VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpStrings,
928 _verbose.value());
929 VMThread::execute(&dumper);
930 }
931
932 // Sharing
933 #if INCLUDE_CDS_JAVA_HEAP
934 size_t StringTable::shared_entry_count() {
935 return _shared_table.entry_count();
936 }
937
938 oop StringTable::lookup_shared(const StringWrapper& name, unsigned int hash) {
939 assert(hash == hash_wrapped_string(name),
940 "hash must be computed using java_lang_String::hash_code");
941 // len is required but is already part of StringWrapper, so 0 is used
942 return _shared_table.lookup(name, hash, 0);
943 }
944
945 oop StringTable::lookup_shared(const jchar* name, int len) {
946 StringWrapper wrapped_name(name, len);
947 // len is required but is already part of StringWrapper, so 0 is used
948 return _shared_table.lookup(wrapped_name, java_lang_String::hash_code(name, len), 0);
949 }
950
951 // This is called BEFORE we enter the CDS safepoint. We can still allocate Java object arrays to
952 // be used by the shared strings table.
953 void StringTable::allocate_shared_strings_array(TRAPS) {
954 if (!CDSConfig::is_dumping_heap()) {
955 return;
956 }
957
958 CompileBroker::wait_for_no_active_tasks();
959
960 precond(CDSConfig::allow_only_single_java_thread());
961
962 // At this point, no more strings will be added:
963 // - There's only a single Java thread (this thread). It no longer executes Java bytecodes
964 // so JIT compilation will eventually stop.
965 // - CompileBroker has no more active tasks, so all JIT requests have been processed.
966
967 // This flag will be cleared after intern table dumping has completed, so we can run the
968 // compiler again (for future AOT method compilation, etc).
969 DEBUG_ONLY(Atomic::release_store(&_disable_interning_during_cds_dump, true));
970
971 if (items_count_acquire() > (size_t)max_jint) {
972 fatal("Too many strings to be archived: %zu", items_count_acquire());
973 }
974
975 int total = (int)items_count_acquire();
976 size_t single_array_size = objArrayOopDesc::object_size(total);
977
978 log_info(aot)("allocated string table for %d strings", total);
979
980 if (!ArchiveHeapWriter::is_too_large_to_archive(single_array_size)) {
981 // The entire table can fit in a single array
982 objArrayOop array = oopFactory::new_objArray(vmClasses::Object_klass(), total, CHECK);
983 _shared_strings_array = OopHandle(Universe::vm_global(), array);
984 log_info(aot)("string table array (single level) length = %d", total);
985 } else {
986 // Split the table in two levels of arrays.
987 int primary_array_length = (total + _secondary_array_max_length - 1) / _secondary_array_max_length;
988 size_t primary_array_size = objArrayOopDesc::object_size(primary_array_length);
989 size_t secondary_array_size = objArrayOopDesc::object_size(_secondary_array_max_length);
990
991 if (ArchiveHeapWriter::is_too_large_to_archive(secondary_array_size)) {
992 // This can only happen if you have an extremely large number of classes that
993 // refer to more than 16384 * 16384 = 26M interned strings! Not a practical concern
994 // but bail out for safety.
995 log_error(aot)("Too many strings to be archived: %zu", items_count_acquire());
996 MetaspaceShared::unrecoverable_writing_error();
997 }
998
999 objArrayOop primary = oopFactory::new_objArray(vmClasses::Object_klass(), primary_array_length, CHECK);
1000 objArrayHandle primaryHandle(THREAD, primary);
1001 _shared_strings_array = OopHandle(Universe::vm_global(), primary);
1002
1003 log_info(aot)("string table array (primary) length = %d", primary_array_length);
1004 for (int i = 0; i < primary_array_length; i++) {
1005 int len;
1006 if (total > _secondary_array_max_length) {
1007 len = _secondary_array_max_length;
1008 } else {
1009 len = total;
1010 }
1011 total -= len;
1012
1013 objArrayOop secondary = oopFactory::new_objArray(vmClasses::Object_klass(), len, CHECK);
1014 primaryHandle()->obj_at_put(i, secondary);
1015
1016 log_info(aot)("string table array (secondary)[%d] length = %d", i, len);
1017 assert(!ArchiveHeapWriter::is_too_large_to_archive(secondary), "sanity");
1018 }
1019
1020 assert(total == 0, "must be");
1021 _is_two_dimensional_shared_strings_array = true;
1022 }
1023 }
1024
1025 #ifndef PRODUCT
1026 void StringTable::verify_secondary_array_index_bits() {
1027 int max;
1028 for (max = 1; ; max++) {
1029 size_t next_size = objArrayOopDesc::object_size(1 << (max + 1));
1030 if (ArchiveHeapWriter::is_too_large_to_archive(next_size)) {
1031 break;
1032 }
1033 }
1034 // Currently max is 17 for +UseCompressedOops, 16 for -UseCompressedOops.
1035 // When we add support for Shenandoah (which has a smaller mininum region size than G1),
1036 // max will become 15/14.
1037 //
1038 // We use _secondary_array_index_bits==14 as that will be the eventual value, and will
1039 // make testing easier.
1040 assert(_secondary_array_index_bits <= max,
1041 "_secondary_array_index_bits (%d) must be smaller than max possible value (%d)",
1042 _secondary_array_index_bits, max);
1043 }
1044 #endif // PRODUCT
1045
1046 // This is called AFTER we enter the CDS safepoint.
1047 //
1048 // For each shared string:
1049 // [1] Store it into _shared_strings_array. Encode its position as a 32-bit index.
1050 // [2] Store the index and hashcode into _shared_table.
1051 oop StringTable::init_shared_strings_array() {
1052 assert(CDSConfig::is_dumping_heap(), "must be");
1053 objArrayOop array = (objArrayOop)(_shared_strings_array.resolve());
1054
1055 verify_secondary_array_index_bits();
1056
1057 int index = 0;
1058 auto copy_into_array = [&] (WeakHandle* val) {
1059 oop string = val->peek();
1060 if (string != nullptr && !ArchiveHeapWriter::is_string_too_large_to_archive(string)) {
1061 // If string is too large, don't put it into the string table.
1062 // - If there are no other refernences to it, it won't be stored into the archive,
1063 // so we are all good.
1064 // - If there's a referece to it, we will report an error inside HeapShared.cpp and
1065 // dumping will fail.
1066 HeapShared::add_to_dumped_interned_strings(string);
1067 if (!_is_two_dimensional_shared_strings_array) {
1068 assert(index < array->length(), "no strings should have been added");
1069 array->obj_at_put(index, string);
1070 } else {
1071 int primary_index = index >> _secondary_array_index_bits;
1072 int secondary_index = index & _secondary_array_index_mask;
1073
1074 assert(primary_index < array->length(), "no strings should have been added");
1075 objArrayOop secondary = (objArrayOop)array->obj_at(primary_index);
1076
1077 assert(secondary != nullptr && secondary->is_objArray(), "must be");
1078 assert(secondary_index < secondary->length(), "no strings should have been added");
1079 secondary->obj_at_put(secondary_index, string);
1080 }
1081 index ++;
1082 }
1083 return true;
1084 };
1085
1086 _local_table->do_safepoint_scan(copy_into_array);
1087 log_info(aot)("Archived %d interned strings", index);
1088 return array;
1089 };
1090
1091 void StringTable::write_shared_table() {
1092 _shared_table.reset();
1093 CompactHashtableWriter writer((int)items_count_acquire(), ArchiveBuilder::string_stats());
1094
1095 int index = 0;
1096 auto copy_into_shared_table = [&] (WeakHandle* val) {
1097 oop string = val->peek();
1098 if (string != nullptr && !ArchiveHeapWriter::is_string_too_large_to_archive(string)) {
1099 unsigned int hash = java_lang_String::hash_code(string);
1100 writer.add(hash, index);
1101 index ++;
1102 }
1103 return true;
1104 };
1105 _local_table->do_safepoint_scan(copy_into_shared_table);
1106 writer.dump(&_shared_table, "string");
1107
1108 DEBUG_ONLY(Atomic::release_store(&_disable_interning_during_cds_dump, false));
1109 }
1110
1111 void StringTable::set_shared_strings_array_index(int root_index) {
1112 _shared_strings_array_root_index = root_index;
1113 }
1114
1115 void StringTable::serialize_shared_table_header(SerializeClosure* soc) {
1116 if (soc->writing() && !CDSConfig::is_dumping_heap()) {
1117 _shared_table.reset();
1118 _is_two_dimensional_shared_strings_array = false;
1119 _shared_strings_array_root_index = -1;
1120 }
1121
1122 _shared_table.serialize_header(soc);
1123
1124 if (soc->writing()) {
1125 // Sanity. Make sure we don't use the shared table at dump time
1126 _shared_table.reset();
1127 } else if (!ArchiveHeapLoader::is_in_use()) {
1128 _shared_table.reset();
1129 }
1130
1131 soc->do_bool(&_is_two_dimensional_shared_strings_array);
1132 soc->do_int(&_shared_strings_array_root_index);
1133 }
1134 #endif //INCLUDE_CDS_JAVA_HEAP