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