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