1 /*
  2  * Copyright (c) 1997, 2024, Oracle and/or its affiliates. All rights reserved.
  3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  4  *
  5  * This code is free software; you can redistribute it and/or modify it
  6  * under the terms of the GNU General Public License version 2 only, as
  7  * published by the Free Software Foundation.
  8  *
  9  * This code is distributed in the hope that it will be useful, but WITHOUT
 10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 12  * version 2 for more details (a copy is included in the LICENSE file that
 13  * accompanied this code).
 14  *
 15  * You should have received a copy of the GNU General Public License version
 16  * 2 along with this work; if not, write to the Free Software Foundation,
 17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 18  *
 19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 20  * or visit www.oracle.com if you need additional information or have any
 21  * questions.
 22  *
 23  */
 24 
 25 #include "precompiled.hpp"
 26 #include "cds/archiveBuilder.hpp"
 27 #include "cds/archiveHeapLoader.inline.hpp"
 28 #include "cds/archiveHeapWriter.hpp"
 29 #include "cds/cdsConfig.hpp"
 30 #include "cds/filemap.hpp"
 31 #include "cds/heapShared.hpp"
 32 #include "classfile/altHashing.hpp"
 33 #include "classfile/compactHashtable.hpp"
 34 #include "classfile/javaClasses.inline.hpp"
 35 #include "classfile/stringTable.hpp"
 36 #include "classfile/vmClasses.hpp"
 37 #include "gc/shared/collectedHeap.hpp"
 38 #include "gc/shared/oopStorage.inline.hpp"
 39 #include "gc/shared/oopStorageSet.hpp"
 40 #include "gc/shared/stringdedup/stringDedup.hpp"
 41 #include "logging/log.hpp"
 42 #include "logging/logStream.hpp"
 43 #include "memory/allocation.inline.hpp"
 44 #include "memory/oopFactory.hpp"
 45 #include "memory/resourceArea.hpp"
 46 #include "oops/access.inline.hpp"
 47 #include "oops/compressedOops.hpp"
 48 #include "oops/oop.inline.hpp"
 49 #include "oops/typeArrayOop.inline.hpp"
 50 #include "oops/weakHandle.inline.hpp"
 51 #include "runtime/atomic.hpp"
 52 #include "runtime/handles.inline.hpp"
 53 #include "runtime/interfaceSupport.inline.hpp"
 54 #include "runtime/mutexLocker.hpp"
 55 #include "runtime/safepointVerifiers.hpp"
 56 #include "runtime/timerTrace.hpp"
 57 #include "runtime/trimNativeHeap.hpp"
 58 #include "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 jchar*, oop,
102   StringTable::read_string_from_compact_hashtable,
103   java_lang_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 
120 volatile bool _alt_hash = false;
121 
122 static bool _rehashed = false;
123 static uint64_t _alt_hash_seed = 0;
124 
125 static unsigned int hash_string(const jchar* s, int len, bool useAlt) {
126   return  useAlt ?
127     AltHashing::halfsiphash_32(_alt_hash_seed, s, len) :
128     java_lang_String::hash_code(s, len);
129 }
130 
131 class StringTableConfig : public StackObj {
132  private:
133  public:
134   typedef WeakHandle Value;
135 
136   static uintx get_hash(Value const& value, bool* is_dead) {
137     oop val_oop = value.peek();
138     if (val_oop == nullptr) {
139       *is_dead = true;
140       return 0;
141     }
142     *is_dead = false;
143     ResourceMark rm;
144     // All String oops are hashed as unicode
145     int length;
146     jchar* chars = java_lang_String::as_unicode_string_or_null(val_oop, length);
147     if (chars != nullptr) {
148       return hash_string(chars, length, _alt_hash);
149     }
150     vm_exit_out_of_memory(length, OOM_MALLOC_ERROR, "get hash from oop");
151     return 0;
152   }
153   // We use default allocation/deallocation but counted
154   static void* allocate_node(void* context, size_t size, Value const& value) {
155     StringTable::item_added();
156     return AllocateHeap(size, mtSymbol);
157   }
158   static void free_node(void* context, void* memory, Value& value) {
159     value.release(StringTable::_oop_storage);
160     FreeHeap(memory);
161     StringTable::item_removed();
162   }
163 };
164 
165 class StringTableLookupJchar : StackObj {
166  private:
167   Thread* _thread;
168   uintx _hash;
169   int _len;
170   const jchar* _str;
171   Handle _found;
172 
173  public:
174   StringTableLookupJchar(Thread* thread, uintx hash, const jchar* key, int len)
175     : _thread(thread), _hash(hash), _len(len), _str(key) {
176   }
177   uintx get_hash() const {
178     return _hash;
179   }
180   bool equals(WeakHandle* value) {
181     oop val_oop = value->peek();
182     if (val_oop == nullptr) {
183       return false;
184     }
185     bool equals = java_lang_String::equals(val_oop, _str, _len);
186     if (!equals) {
187       return false;
188     }
189     // Need to resolve weak handle and Handleize through possible safepoint.
190      _found = Handle(_thread, value->resolve());
191     return true;
192   }
193   bool is_dead(WeakHandle* value) {
194     oop val_oop = value->peek();
195     return val_oop == nullptr;
196   }
197 };
198 
199 class StringTableLookupOop : public StackObj {
200  private:
201   Thread* _thread;
202   uintx _hash;
203   Handle _find;
204   Handle _found;  // Might be a different oop with the same value that's already
205                   // in the table, which is the point.
206  public:
207   StringTableLookupOop(Thread* thread, uintx hash, Handle handle)
208     : _thread(thread), _hash(hash), _find(handle) { }
209 
210   uintx get_hash() const {
211     return _hash;
212   }
213 
214   bool equals(WeakHandle* value) {
215     oop val_oop = value->peek();
216     if (val_oop == nullptr) {
217       return false;
218     }
219     bool equals = java_lang_String::equals(_find(), val_oop);
220     if (!equals) {
221       return false;
222     }
223     // Need to resolve weak handle and Handleize through possible safepoint.
224     _found = Handle(_thread, value->resolve());
225     return true;
226   }
227 
228   bool is_dead(WeakHandle* value) {
229     oop val_oop = value->peek();
230     return val_oop == nullptr;
231   }
232 };
233 
234 void StringTable::create_table() {
235   size_t start_size_log_2 = ceil_log2(StringTableSize);
236   _current_size = ((size_t)1) << start_size_log_2;
237   log_trace(stringtable)("Start size: " SIZE_FORMAT " (" SIZE_FORMAT ")",
238                          _current_size, start_size_log_2);
239   _local_table = new StringTableHash(start_size_log_2, END_SIZE, REHASH_LEN, true);
240   _oop_storage = OopStorageSet::create_weak("StringTable Weak", mtSymbol);
241   _oop_storage->register_num_dead_callback(&gc_notification);
242 
243 #if INCLUDE_CDS_JAVA_HEAP
244   if (ArchiveHeapLoader::is_in_use()) {
245     _shared_strings_array = OopHandle(Universe::vm_global(), HeapShared::get_root(_shared_strings_array_root_index));
246   }
247 #endif
248 }
249 
250 void StringTable::item_added() {
251   Atomic::inc(&_items_count);
252 }
253 
254 void StringTable::item_removed() {
255   Atomic::dec(&_items_count);
256 }
257 
258 double StringTable::get_load_factor() {
259   return double(_items_count)/double(_current_size);
260 }
261 
262 double StringTable::get_dead_factor(size_t num_dead) {
263   return double(num_dead)/double(_current_size);
264 }
265 
266 size_t StringTable::table_size() {
267   return ((size_t)1) << _local_table->get_size_log2(Thread::current());
268 }
269 
270 void StringTable::trigger_concurrent_work() {
271   MutexLocker ml(Service_lock, Mutex::_no_safepoint_check_flag);
272   Atomic::store(&_has_work, true);
273   Service_lock->notify_all();
274 }
275 
276 // Probing
277 oop StringTable::lookup(Symbol* symbol) {
278   ResourceMark rm;
279   int length;
280   jchar* chars = symbol->as_unicode(length);
281   return lookup(chars, length);
282 }
283 
284 oop StringTable::lookup(const jchar* name, int len) {
285   unsigned int hash = java_lang_String::hash_code(name, len);
286   oop string = lookup_shared(name, len, hash);
287   if (string != nullptr) {
288     return string;
289   }
290   if (_alt_hash) {
291     hash = hash_string(name, len, true);
292   }
293   return do_lookup(name, len, hash);
294 }
295 
296 class StringTableGet : public StackObj {
297   Thread* _thread;
298   Handle  _return;
299  public:
300   StringTableGet(Thread* thread) : _thread(thread) {}
301   void operator()(WeakHandle* val) {
302     oop result = val->resolve();
303     assert(result != nullptr, "Result should be reachable");
304     _return = Handle(_thread, result);
305   }
306   oop get_res_oop() {
307     return _return();
308   }
309 };
310 
311 oop StringTable::do_lookup(const jchar* name, int len, uintx hash) {
312   Thread* thread = Thread::current();
313   StringTableLookupJchar lookup(thread, hash, name, len);
314   StringTableGet stg(thread);
315   bool rehash_warning;
316   _local_table->get(thread, lookup, stg, &rehash_warning);
317   update_needs_rehash(rehash_warning);
318   return stg.get_res_oop();
319 }
320 
321 // Interning
322 oop StringTable::intern(Symbol* symbol, TRAPS) {
323   if (symbol == nullptr) return nullptr;
324   ResourceMark rm(THREAD);
325   int length;
326   jchar* chars = symbol->as_unicode(length);
327   Handle string;
328   oop result = intern(string, chars, length, CHECK_NULL);
329   return result;
330 }
331 
332 oop StringTable::intern(oop string, TRAPS) {
333   if (string == nullptr) return nullptr;
334   ResourceMark rm(THREAD);
335   int length;
336   Handle h_string (THREAD, string);
337   jchar* chars = java_lang_String::as_unicode_string(string, length,
338                                                      CHECK_NULL);
339   oop result = intern(h_string, chars, length, CHECK_NULL);
340   return result;
341 }
342 
343 oop StringTable::intern(const char* utf8_string, TRAPS) {
344   if (utf8_string == nullptr) return nullptr;
345   ResourceMark rm(THREAD);
346   int length = UTF8::unicode_length(utf8_string);
347   jchar* chars = NEW_RESOURCE_ARRAY(jchar, length);
348   UTF8::convert_to_unicode(utf8_string, chars, length);
349   Handle string;
350   oop result = intern(string, chars, length, CHECK_NULL);
351   return result;
352 }
353 
354 oop StringTable::intern(Handle string_or_null_h, const jchar* name, int len, TRAPS) {
355   // shared table always uses java_lang_String::hash_code
356   unsigned int hash = java_lang_String::hash_code(name, len);
357   oop found_string = lookup_shared(name, len, hash);
358   if (found_string != nullptr) {
359     return found_string;
360   }
361   if (_alt_hash) {
362     hash = hash_string(name, len, true);
363   }
364   found_string = do_lookup(name, len, hash);
365   if (found_string != nullptr) {
366     return found_string;
367   }
368   return do_intern(string_or_null_h, name, len, hash, THREAD);
369 }
370 
371 oop StringTable::do_intern(Handle string_or_null_h, const jchar* name,
372                            int len, uintx hash, TRAPS) {
373   HandleMark hm(THREAD);  // cleanup strings created
374   Handle string_h;
375 
376   if (!string_or_null_h.is_null()) {
377     string_h = string_or_null_h;
378   } else {
379     string_h = java_lang_String::create_from_unicode(name, len, CHECK_NULL);
380   }
381 
382   assert(java_lang_String::equals(string_h(), name, len),
383          "string must be properly initialized");
384   assert(len == java_lang_String::length(string_h()), "Must be same length");
385 
386   // Notify deduplication support that the string is being interned.  A string
387   // must never be deduplicated after it has been interned.  Doing so interferes
388   // with compiler optimizations done on e.g. interned string literals.
389   if (StringDedup::is_enabled()) {
390     StringDedup::notify_intern(string_h());
391   }
392 
393   StringTableLookupOop lookup(THREAD, hash, string_h);
394   StringTableGet stg(THREAD);
395 
396   bool rehash_warning;
397   do {
398     // Callers have already looked up the String using the jchar* name, so just go to add.
399     WeakHandle wh(_oop_storage, string_h);
400     // The hash table takes ownership of the WeakHandle, even if it's not inserted.
401     if (_local_table->insert(THREAD, lookup, wh, &rehash_warning)) {
402       update_needs_rehash(rehash_warning);
403       return wh.resolve();
404     }
405     // In case another thread did a concurrent add, return value already in the table.
406     // This could fail if the String got gc'ed concurrently, so loop back until success.
407     if (_local_table->get(THREAD, lookup, stg, &rehash_warning)) {
408       update_needs_rehash(rehash_warning);
409       return stg.get_res_oop();
410     }
411   } while(true);
412 }
413 
414 // Concurrent work
415 void StringTable::grow(JavaThread* jt) {
416   StringTableHash::GrowTask gt(_local_table);
417   if (!gt.prepare(jt)) {
418     return;
419   }
420   log_trace(stringtable)("Started to grow");
421   {
422     TraceTime timer("Grow", TRACETIME_LOG(Debug, stringtable, perf));
423     while (gt.do_task(jt)) {
424       gt.pause(jt);
425       {
426         ThreadBlockInVM tbivm(jt);
427       }
428       gt.cont(jt);
429     }
430   }
431   gt.done(jt);
432   _current_size = table_size();
433   log_debug(stringtable)("Grown to size:" SIZE_FORMAT, _current_size);
434 }
435 
436 struct StringTableDoDelete : StackObj {
437   void operator()(WeakHandle* val) {
438     /* do nothing */
439   }
440 };
441 
442 struct StringTableDeleteCheck : StackObj {
443   long _count;
444   long _item;
445   StringTableDeleteCheck() : _count(0), _item(0) {}
446   bool operator()(WeakHandle* val) {
447     ++_item;
448     oop tmp = val->peek();
449     if (tmp == nullptr) {
450       ++_count;
451       return true;
452     } else {
453       return false;
454     }
455   }
456 };
457 
458 void StringTable::clean_dead_entries(JavaThread* jt) {
459   StringTableHash::BulkDeleteTask bdt(_local_table);
460   if (!bdt.prepare(jt)) {
461     return;
462   }
463 
464   StringTableDeleteCheck stdc;
465   StringTableDoDelete stdd;
466   NativeHeapTrimmer::SuspendMark sm("stringtable");
467   {
468     TraceTime timer("Clean", TRACETIME_LOG(Debug, stringtable, perf));
469     while(bdt.do_task(jt, stdc, stdd)) {
470       bdt.pause(jt);
471       {
472         ThreadBlockInVM tbivm(jt);
473       }
474       bdt.cont(jt);
475     }
476     bdt.done(jt);
477   }
478   log_debug(stringtable)("Cleaned %ld of %ld", stdc._count, stdc._item);
479 }
480 
481 void StringTable::gc_notification(size_t num_dead) {
482   log_trace(stringtable)("Uncleaned items:" SIZE_FORMAT, num_dead);
483 
484   if (has_work()) {
485     return;
486   }
487 
488   double load_factor = StringTable::get_load_factor();
489   double dead_factor = StringTable::get_dead_factor(num_dead);
490   // We should clean/resize if we have more dead than alive,
491   // more items than preferred load factor or
492   // more dead items than water mark.
493   if ((dead_factor > load_factor) ||
494       (load_factor > PREF_AVG_LIST_LEN) ||
495       (dead_factor > CLEAN_DEAD_HIGH_WATER_MARK)) {
496     log_debug(stringtable)("Concurrent work triggered, live factor: %g dead factor: %g",
497                            load_factor, dead_factor);
498     trigger_concurrent_work();
499   }
500 }
501 
502 bool StringTable::has_work() {
503   return Atomic::load_acquire(&_has_work);
504 }
505 
506 void StringTable::do_concurrent_work(JavaThread* jt) {
507   double load_factor = get_load_factor();
508   log_debug(stringtable, perf)("Concurrent work, live factor: %g", load_factor);
509   // We prefer growing, since that also removes dead items
510   if (load_factor > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached()) {
511     grow(jt);
512   } else {
513     clean_dead_entries(jt);
514   }
515   Atomic::release_store(&_has_work, false);
516 }
517 
518 // Rehash
519 bool StringTable::do_rehash() {
520   if (!_local_table->is_safepoint_safe()) {
521     return false;
522   }
523 
524   // We use current size, not max size.
525   size_t new_size = _local_table->get_size_log2(Thread::current());
526   StringTableHash* new_table = new StringTableHash(new_size, END_SIZE, REHASH_LEN, true);
527   // Use alt hash from now on
528   _alt_hash = true;
529   if (!_local_table->try_move_nodes_to(Thread::current(), new_table)) {
530     _alt_hash = false;
531     delete new_table;
532     return false;
533   }
534 
535   // free old table
536   delete _local_table;
537   _local_table = new_table;
538 
539   return true;
540 }
541 
542 bool StringTable::should_grow() {
543   return get_load_factor() > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached();
544 }
545 
546 bool StringTable::rehash_table_expects_safepoint_rehashing() {
547   // No rehashing required
548   if (!needs_rehashing()) {
549     return false;
550   }
551 
552   // Grow instead of rehash
553   if (should_grow()) {
554     return false;
555   }
556 
557   // Already rehashed
558   if (_rehashed) {
559     return false;
560   }
561 
562   // Resizing in progress
563   if (!_local_table->is_safepoint_safe()) {
564     return false;
565   }
566 
567   return true;
568 }
569 
570 void StringTable::rehash_table() {
571   log_debug(stringtable)("Table imbalanced, rehashing called.");
572 
573   // Grow instead of rehash.
574   if (should_grow()) {
575     log_debug(stringtable)("Choosing growing over rehashing.");
576     trigger_concurrent_work();
577     _needs_rehashing = false;
578     return;
579   }
580   // Already rehashed.
581   if (_rehashed) {
582     log_warning(stringtable)("Rehashing already done, still long lists.");
583     trigger_concurrent_work();
584     _needs_rehashing = false;
585     return;
586   }
587 
588   _alt_hash_seed = AltHashing::compute_seed();
589   {
590     if (do_rehash()) {
591       _rehashed = true;
592     } else {
593       log_info(stringtable)("Resizes in progress rehashing skipped.");
594     }
595   }
596   _needs_rehashing = false;
597 }
598 
599 // Statistics
600 static size_t literal_size(oop obj) {
601   if (obj == nullptr) {
602     return 0;
603   }
604 
605   size_t word_size = obj->size();
606 
607   if (obj->klass() == vmClasses::String_klass()) {
608     // This may overcount if String.value arrays are shared.
609     word_size += java_lang_String::value(obj)->size();
610   }
611 
612   return word_size * HeapWordSize;
613 }
614 
615 struct SizeFunc : StackObj {
616   size_t operator()(WeakHandle* val) {
617     oop s = val->peek();
618     if (s == nullptr) {
619       // Dead
620       return 0;
621     }
622     return literal_size(s);
623   };
624 };
625 
626 TableStatistics StringTable::get_table_statistics() {
627   static TableStatistics ts;
628   SizeFunc sz;
629   ts = _local_table->statistics_get(Thread::current(), sz, ts);
630   return ts;
631 }
632 
633 void StringTable::print_table_statistics(outputStream* st) {
634   SizeFunc sz;
635   _local_table->statistics_to(Thread::current(), sz, st, "StringTable");
636 #if INCLUDE_CDS_JAVA_HEAP
637   if (!_shared_table.empty()) {
638     _shared_table.print_table_statistics(st, "Shared String Table");
639   }
640 #endif
641 }
642 
643 // Verification
644 class VerifyStrings : StackObj {
645  public:
646   bool operator()(WeakHandle* val) {
647     oop s = val->peek();
648     if (s != nullptr) {
649       assert(java_lang_String::length(s) >= 0, "Length on string must work.");
650     }
651     return true;
652   };
653 };
654 
655 // This verification is part of Universe::verify() and needs to be quick.
656 void StringTable::verify() {
657   VerifyStrings vs;
658   _local_table->do_safepoint_scan(vs);
659 }
660 
661 // Verification and comp
662 class VerifyCompStrings : StackObj {
663   static unsigned string_hash(oop const& str) {
664     return java_lang_String::hash_code_noupdate(str);
665   }
666   static bool string_equals(oop const& a, oop const& b) {
667     return java_lang_String::equals(a, b);
668   }
669 
670   ResizeableResourceHashtable<oop, bool, AnyObj::C_HEAP, mtInternal,
671                               string_hash, string_equals> _table;
672  public:
673   size_t _errors;
674   VerifyCompStrings() : _table(unsigned(_items_count / 8) + 1, 0 /* do not resize */), _errors(0) {}
675   bool operator()(WeakHandle* val) {
676     oop s = val->resolve();
677     if (s == nullptr) {
678       return true;
679     }
680     bool created;
681     _table.put_if_absent(s, true, &created);
682     assert(created, "Duplicate strings");
683     if (!created) {
684       _errors++;
685     }
686     return true;
687   };
688 };
689 
690 size_t StringTable::verify_and_compare_entries() {
691   Thread* thr = Thread::current();
692   VerifyCompStrings vcs;
693   _local_table->do_scan(thr, vcs);
694   return vcs._errors;
695 }
696 
697 static void print_string(Thread* current, outputStream* st, oop s) {
698   typeArrayOop value     = java_lang_String::value_no_keepalive(s);
699   int          length    = java_lang_String::length(s);
700   bool         is_latin1 = java_lang_String::is_latin1(s);
701 
702   if (length <= 0) {
703     st->print("%d: ", length);
704   } else {
705     ResourceMark rm(current);
706     int utf8_length = length;
707     char* utf8_string;
708 
709     if (!is_latin1) {
710       jchar* chars = value->char_at_addr(0);
711       utf8_string = UNICODE::as_utf8(chars, utf8_length);
712     } else {
713       jbyte* bytes = value->byte_at_addr(0);
714       utf8_string = UNICODE::as_utf8(bytes, utf8_length);
715     }
716 
717     st->print("%d: ", utf8_length);
718     HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
719   }
720   st->cr();
721 }
722 
723 // Dumping
724 class PrintString : StackObj {
725   Thread* _thr;
726   outputStream* _st;
727  public:
728   PrintString(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
729   bool operator()(WeakHandle* val) {
730     oop s = val->peek();
731     if (s == nullptr) {
732       return true;
733     }
734     print_string(_thr, _st, s);
735     return true;
736   };
737 };
738 
739 class PrintSharedString : StackObj {
740   Thread* _thr;
741   outputStream* _st;
742 public:
743   PrintSharedString(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
744   void do_value(oop s) {
745     if (s == nullptr) {
746       return;
747     }
748     print_string(_thr, _st, s);
749   };
750 };
751 
752 void StringTable::dump(outputStream* st, bool verbose) {
753   if (!verbose) {
754     print_table_statistics(st);
755   } else {
756     Thread* thr = Thread::current();
757     ResourceMark rm(thr);
758     st->print_cr("VERSION: 1.1");
759     PrintString ps(thr, st);
760     if (!_local_table->try_scan(thr, ps)) {
761       st->print_cr("dump unavailable at this moment");
762     }
763 #if INCLUDE_CDS_JAVA_HEAP
764     if (!_shared_table.empty()) {
765       st->print_cr("#----------------");
766       st->print_cr("# Shared strings:");
767       st->print_cr("#----------------");
768       PrintSharedString pss(thr, st);
769       _shared_table.iterate(&pss);
770     }
771 #endif
772   }
773 }
774 
775 // Utility for dumping strings
776 StringtableDCmd::StringtableDCmd(outputStream* output, bool heap) :
777                                  DCmdWithParser(output, heap),
778   _verbose("-verbose", "Dump the content of each string in the table",
779            "BOOLEAN", false, "false") {
780   _dcmdparser.add_dcmd_option(&_verbose);
781 }
782 
783 void StringtableDCmd::execute(DCmdSource source, TRAPS) {
784   VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpStrings,
785                          _verbose.value());
786   VMThread::execute(&dumper);
787 }
788 
789 // Sharing
790 #if INCLUDE_CDS_JAVA_HEAP
791 size_t StringTable::shared_entry_count() {
792   return _shared_table.entry_count();
793 }
794 
795 oop StringTable::lookup_shared(const jchar* name, int len, unsigned int hash) {
796   assert(hash == java_lang_String::hash_code(name, len),
797          "hash must be computed using java_lang_String::hash_code");
798   return _shared_table.lookup(name, hash, len);
799 }
800 
801 oop StringTable::lookup_shared(const jchar* name, int len) {
802   return _shared_table.lookup(name, java_lang_String::hash_code(name, len), len);
803 }
804 
805 // This is called BEFORE we enter the CDS safepoint. We can allocate heap objects.
806 // This should be called when we know no more strings will be added (which will be easy
807 // to guarantee because CDS runs with a single Java thread. See JDK-8253495.)
808 void StringTable::allocate_shared_strings_array(TRAPS) {
809   if (!CDSConfig::is_dumping_heap()) {
810     return;
811   }
812   if (_items_count > (size_t)max_jint) {
813     fatal("Too many strings to be archived: %zu", _items_count);
814   }
815 
816   int total = (int)_items_count;
817   size_t single_array_size = objArrayOopDesc::object_size(total);
818 
819   log_info(cds)("allocated string table for %d strings", total);
820 
821   if (!ArchiveHeapWriter::is_too_large_to_archive(single_array_size)) {
822     // The entire table can fit in a single array
823     objArrayOop array = oopFactory::new_objArray(vmClasses::Object_klass(), total, CHECK);
824     _shared_strings_array = OopHandle(Universe::vm_global(), array);
825     log_info(cds)("string table array (single level) length = %d", total);
826   } else {
827     // Split the table in two levels of arrays.
828     int primary_array_length = (total + _secondary_array_max_length - 1) / _secondary_array_max_length;
829     size_t primary_array_size = objArrayOopDesc::object_size(primary_array_length);
830     size_t secondary_array_size = objArrayOopDesc::object_size(_secondary_array_max_length);
831 
832     if (ArchiveHeapWriter::is_too_large_to_archive(secondary_array_size)) {
833       // This can only happen if you have an extremely large number of classes that
834       // refer to more than 16384 * 16384 = 26M interned strings! Not a practical concern
835       // but bail out for safety.
836       log_error(cds)("Too many strings to be archived: %zu", _items_count);
837       MetaspaceShared::unrecoverable_writing_error();
838     }
839 
840     objArrayOop primary = oopFactory::new_objArray(vmClasses::Object_klass(), primary_array_length, CHECK);
841     objArrayHandle primaryHandle(THREAD, primary);
842     _shared_strings_array = OopHandle(Universe::vm_global(), primary);
843 
844     log_info(cds)("string table array (primary) length = %d", primary_array_length);
845     for (int i = 0; i < primary_array_length; i++) {
846       int len;
847       if (total > _secondary_array_max_length) {
848         len = _secondary_array_max_length;
849       } else {
850         len = total;
851       }
852       total -= len;
853 
854       objArrayOop secondary = oopFactory::new_objArray(vmClasses::Object_klass(), len, CHECK);
855       primaryHandle()->obj_at_put(i, secondary);
856 
857       log_info(cds)("string table array (secondary)[%d] length = %d", i, len);
858       assert(!ArchiveHeapWriter::is_too_large_to_archive(secondary), "sanity");
859     }
860 
861     assert(total == 0, "must be");
862     _is_two_dimensional_shared_strings_array = true;
863   }
864 }
865 
866 #ifndef PRODUCT
867 void StringTable::verify_secondary_array_index_bits() {
868   int max;
869   for (max = 1; ; max++) {
870     size_t next_size = objArrayOopDesc::object_size(1 << (max + 1));
871     if (ArchiveHeapWriter::is_too_large_to_archive(next_size)) {
872       break;
873     }
874   }
875   // Currently max is 17 for +UseCompressedOops, 16 for -UseCompressedOops.
876   // When we add support for Shenandoah (which has a smaller mininum region size than G1),
877   // max will become 15/14.
878   //
879   // We use _secondary_array_index_bits==14 as that will be the eventual value, and will
880   // make testing easier.
881   assert(_secondary_array_index_bits <= max,
882          "_secondary_array_index_bits (%d) must be smaller than max possible value (%d)",
883          _secondary_array_index_bits, max);
884 }
885 #endif // PRODUCT
886 
887 // This is called AFTER we enter the CDS safepoint.
888 //
889 // For each shared string:
890 // [1] Store it into _shared_strings_array. Encode its position as a 32-bit index.
891 // [2] Store the index and hashcode into _shared_table.
892 oop StringTable::init_shared_table(const DumpedInternedStrings* dumped_interned_strings) {
893   assert(HeapShared::can_write(), "must be");
894   objArrayOop array = (objArrayOop)(_shared_strings_array.resolve());
895 
896   verify_secondary_array_index_bits();
897 
898   _shared_table.reset();
899   CompactHashtableWriter writer((int)_items_count, ArchiveBuilder::string_stats());
900 
901   int index = 0;
902   auto copy_into_array = [&] (oop string, bool value_ignored) {
903     unsigned int hash = java_lang_String::hash_code(string);
904     writer.add(hash, index);
905 
906     if (!_is_two_dimensional_shared_strings_array) {
907       assert(index < array->length(), "no strings should have been added");
908       array->obj_at_put(index, string);
909     } else {
910       int primary_index = index >> _secondary_array_index_bits;
911       int secondary_index = index & _secondary_array_index_mask;
912 
913       assert(primary_index < array->length(), "no strings should have been added");
914       objArrayOop secondary = (objArrayOop)array->obj_at(primary_index);
915 
916       assert(secondary != nullptr && secondary->is_objArray(), "must be");
917       assert(secondary_index < secondary->length(), "no strings should have been added");
918       secondary->obj_at_put(secondary_index, string);
919     }
920 
921     index ++;
922   };
923   dumped_interned_strings->iterate_all(copy_into_array);
924 
925   writer.dump(&_shared_table, "string");
926 
927   return array;
928 }
929 
930 void StringTable::set_shared_strings_array_index(int root_index) {
931   _shared_strings_array_root_index = root_index;
932 }
933 
934 void StringTable::serialize_shared_table_header(SerializeClosure* soc) {
935   _shared_table.serialize_header(soc);
936 
937   if (soc->writing()) {
938     // Sanity. Make sure we don't use the shared table at dump time
939     _shared_table.reset();
940   } else if (!ArchiveHeapLoader::is_in_use()) {
941     _shared_table.reset();
942   }
943 
944   soc->do_bool(&_is_two_dimensional_shared_strings_array);
945   soc->do_int(&_shared_strings_array_root_index);
946 }
947 #endif //INCLUDE_CDS_JAVA_HEAP