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/cdsConfig.hpp"
 28 #include "cds/dynamicArchive.hpp"
 29 #include "classfile/altHashing.hpp"
 30 #include "classfile/classLoaderData.hpp"
 31 #include "classfile/compactHashtable.hpp"
 32 #include "classfile/javaClasses.hpp"
 33 #include "classfile/symbolTable.hpp"
 34 #include "memory/allocation.inline.hpp"
 35 #include "memory/metaspaceClosure.hpp"
 36 #include "memory/resourceArea.hpp"
 37 #include "oops/oop.inline.hpp"
 38 #include "runtime/atomic.hpp"
 39 #include "runtime/interfaceSupport.inline.hpp"
 40 #include "runtime/timerTrace.hpp"
 41 #include "runtime/trimNativeHeap.hpp"
 42 #include "services/diagnosticCommand.hpp"
 43 #include "utilities/concurrentHashTable.inline.hpp"
 44 #include "utilities/concurrentHashTableTasks.inline.hpp"
 45 #include "utilities/utf8.hpp"
 46 
 47 // We used to not resize at all, so let's be conservative
 48 // and not set it too short before we decide to resize,
 49 // to match previous startup behavior
 50 const double PREF_AVG_LIST_LEN = 8.0;
 51 // 2^24 is max size, like StringTable.
 52 const size_t END_SIZE = 24;
 53 // If a chain gets to 100 something might be wrong
 54 const size_t REHASH_LEN = 100;
 55 
 56 const size_t ON_STACK_BUFFER_LENGTH = 128;
 57 
 58 // --------------------------------------------------------------------------
 59 
 60 inline bool symbol_equals_compact_hashtable_entry(Symbol* value, const char* key, int len) {
 61   if (value->equals(key, len)) {
 62     return true;
 63   } else {
 64     return false;
 65   }
 66 }
 67 
 68 static OffsetCompactHashtable<
 69   const char*, Symbol*,
 70   symbol_equals_compact_hashtable_entry
 71 > _shared_table;
 72 
 73 static OffsetCompactHashtable<
 74   const char*, Symbol*,
 75   symbol_equals_compact_hashtable_entry
 76 > _dynamic_shared_table;
 77 
 78 // --------------------------------------------------------------------------
 79 
 80 typedef ConcurrentHashTable<SymbolTableConfig, mtSymbol> SymbolTableHash;
 81 static SymbolTableHash* _local_table = nullptr;
 82 
 83 volatile bool SymbolTable::_has_work = 0;
 84 volatile bool SymbolTable::_needs_rehashing = false;
 85 
 86 // For statistics
 87 static size_t _symbols_removed = 0;
 88 static size_t _symbols_counted = 0;
 89 static size_t _current_size = 0;
 90 
 91 static volatile size_t _items_count = 0;
 92 static volatile bool   _has_items_to_clean = false;
 93 
 94 
 95 static volatile bool _alt_hash = false;
 96 
 97 #ifdef USE_LIBRARY_BASED_TLS_ONLY
 98 static volatile bool _lookup_shared_first = false;
 99 #else
100 // "_lookup_shared_first" can get highly contended with many cores if multiple threads
101 // are updating "lookup success history" in a global shared variable. If built-in TLS is available, use it.
102 static THREAD_LOCAL bool _lookup_shared_first = false;
103 #endif
104 
105 // Static arena for symbols that are not deallocated
106 Arena* SymbolTable::_arena = nullptr;
107 
108 static bool _rehashed = false;
109 static uint64_t _alt_hash_seed = 0;
110 
111 static inline void log_trace_symboltable_helper(Symbol* sym, const char* msg) {
112 #ifndef PRODUCT
113   ResourceMark rm;
114   log_trace(symboltable)("%s [%s]", msg, sym->as_quoted_ascii());
115 #endif // PRODUCT
116 }
117 
118 // Pick hashing algorithm.
119 static unsigned int hash_symbol(const char* s, int len, bool useAlt) {
120   return useAlt ?
121   AltHashing::halfsiphash_32(_alt_hash_seed, (const uint8_t*)s, len) :
122   java_lang_String::hash_code((const jbyte*)s, len);
123 }
124 
125 #if INCLUDE_CDS
126 static unsigned int hash_shared_symbol(const char* s, int len) {
127   return java_lang_String::hash_code((const jbyte*)s, len);
128 }
129 #endif
130 
131 class SymbolTableConfig : public AllStatic {
132 
133 public:
134   typedef Symbol Value;  // value of the Node in the hashtable
135 
136   static uintx get_hash(Value const& value, bool* is_dead) {
137     *is_dead = (value.refcount() == 0);
138     if (*is_dead) {
139       return 0;
140     } else {
141       return hash_symbol((const char*)value.bytes(), value.utf8_length(), _alt_hash);
142     }
143   }
144   // We use default allocation/deallocation but counted
145   static void* allocate_node(void* context, size_t size, Value const& value) {
146     SymbolTable::item_added();
147     return allocate_node_impl(size, value);
148   }
149   static void free_node(void* context, void* memory, Value & value) {
150     // We get here because #1 some threads lost a race to insert a newly created Symbol
151     // or #2 we're cleaning up unused symbol.
152     // If #1, then the symbol can be either permanent,
153     // or regular newly created one (refcount==1)
154     // If #2, then the symbol is dead (refcount==0)
155     assert(value.is_permanent() || (value.refcount() == 1) || (value.refcount() == 0),
156            "refcount %d", value.refcount());
157 #if INCLUDE_CDS
158     if (CDSConfig::is_dumping_static_archive()) {
159       // We have allocated with MetaspaceShared::symbol_space_alloc(). No deallocation is needed.
160       // Unreferenced Symbols will not be copied into the archive.
161       return;
162     }
163 #endif
164     if (value.refcount() == 1) {
165       value.decrement_refcount();
166       assert(value.refcount() == 0, "expected dead symbol");
167     }
168     if (value.refcount() != PERM_REFCOUNT) {
169       FreeHeap(memory);
170     } else {
171       MutexLocker ml(SymbolArena_lock, Mutex::_no_safepoint_check_flag); // Protect arena
172       // Deleting permanent symbol should not occur very often (insert race condition),
173       // so log it.
174       log_trace_symboltable_helper(&value, "Freeing permanent symbol");
175       size_t alloc_size = SymbolTableHash::get_dynamic_node_size(value.byte_size());
176       if (!SymbolTable::arena()->Afree(memory, alloc_size)) {
177         log_trace_symboltable_helper(&value, "Leaked permanent symbol");
178       }
179     }
180     SymbolTable::item_removed();
181   }
182 
183 private:
184   static void* allocate_node_impl(size_t size, Value const& value) {
185     size_t alloc_size = SymbolTableHash::get_dynamic_node_size(value.byte_size());
186 #if INCLUDE_CDS
187     if (CDSConfig::is_dumping_static_archive()) {
188       MutexLocker ml(DumpRegion_lock, Mutex::_no_safepoint_check_flag);
189       // To get deterministic output from -Xshare:dump, we ensure that Symbols are allocated in
190       // increasing addresses. When the symbols are copied into the archive, we preserve their
191       // relative address order (sorted, see ArchiveBuilder::gather_klasses_and_symbols).
192       //
193       // We cannot use arena because arena chunks are allocated by the OS. As a result, for example,
194       // the archived symbol of "java/lang/Object" may sometimes be lower than "java/lang/String", and
195       // sometimes be higher. This would cause non-deterministic contents in the archive.
196       DEBUG_ONLY(static void* last = 0);
197       void* p = (void*)MetaspaceShared::symbol_space_alloc(alloc_size);
198       assert(p > last, "must increase monotonically");
199       DEBUG_ONLY(last = p);
200       return p;
201     }
202 #endif
203     if (value.refcount() != PERM_REFCOUNT) {
204       return AllocateHeap(alloc_size, mtSymbol);
205     } else {
206       // Allocate to global arena
207       MutexLocker ml(SymbolArena_lock, Mutex::_no_safepoint_check_flag); // Protect arena
208       return SymbolTable::arena()->Amalloc(alloc_size);
209     }
210   }
211 };
212 
213 void SymbolTable::create_table ()  {
214   size_t start_size_log_2 = ceil_log2(SymbolTableSize);
215   _current_size = ((size_t)1) << start_size_log_2;
216   log_trace(symboltable)("Start size: " SIZE_FORMAT " (" SIZE_FORMAT ")",
217                          _current_size, start_size_log_2);
218   _local_table = new SymbolTableHash(start_size_log_2, END_SIZE, REHASH_LEN, true);
219 
220   // Initialize the arena for global symbols, size passed in depends on CDS.
221   if (symbol_alloc_arena_size == 0) {
222     _arena = new (mtSymbol) Arena(mtSymbol);
223   } else {
224     _arena = new (mtSymbol) Arena(mtSymbol, Arena::Tag::tag_other, symbol_alloc_arena_size);
225   }
226 }
227 
228 void SymbolTable::reset_has_items_to_clean() { Atomic::store(&_has_items_to_clean, false); }
229 void SymbolTable::mark_has_items_to_clean()  { Atomic::store(&_has_items_to_clean, true); }
230 bool SymbolTable::has_items_to_clean()       { return Atomic::load(&_has_items_to_clean); }
231 
232 void SymbolTable::item_added() {
233   Atomic::inc(&_items_count);
234 }
235 
236 void SymbolTable::item_removed() {
237   Atomic::inc(&(_symbols_removed));
238   Atomic::dec(&_items_count);
239 }
240 
241 double SymbolTable::get_load_factor() {
242   return (double)_items_count/(double)_current_size;
243 }
244 
245 size_t SymbolTable::table_size() {
246   return ((size_t)1) << _local_table->get_size_log2(Thread::current());
247 }
248 
249 bool SymbolTable::has_work() { return Atomic::load_acquire(&_has_work); }
250 
251 void SymbolTable::trigger_cleanup() {
252   // Avoid churn on ServiceThread
253   if (!has_work()) {
254     MutexLocker ml(Service_lock, Mutex::_no_safepoint_check_flag);
255     _has_work = true;
256     Service_lock->notify_all();
257   }
258 }
259 
260 class SymbolsDo : StackObj {
261   SymbolClosure *_cl;
262 public:
263   SymbolsDo(SymbolClosure *cl) : _cl(cl) {}
264   bool operator()(Symbol* value) {
265     assert(value != nullptr, "expected valid value");
266     _cl->do_symbol(&value);
267     return true;
268   };
269 };
270 
271 class SharedSymbolIterator {
272   SymbolClosure* _symbol_closure;
273 public:
274   SharedSymbolIterator(SymbolClosure* f) : _symbol_closure(f) {}
275   void do_value(Symbol* symbol) {
276     _symbol_closure->do_symbol(&symbol);
277   }
278 };
279 
280 // Call function for all symbols in the symbol table.
281 void SymbolTable::symbols_do(SymbolClosure *cl) {
282   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint");
283   // all symbols from shared table
284   SharedSymbolIterator iter(cl);
285   _shared_table.iterate(&iter);
286   _dynamic_shared_table.iterate(&iter);
287 
288   // all symbols from the dynamic table
289   SymbolsDo sd(cl);
290   _local_table->do_safepoint_scan(sd);
291 }
292 
293 // Call function for all symbols in shared table. Used by -XX:+PrintSharedArchiveAndExit
294 void SymbolTable::shared_symbols_do(SymbolClosure *cl) {
295   SharedSymbolIterator iter(cl);
296   _shared_table.iterate(&iter);
297   _dynamic_shared_table.iterate(&iter);
298 }
299 
300 Symbol* SymbolTable::lookup_dynamic(const char* name,
301                                     int len, unsigned int hash) {
302   Symbol* sym = do_lookup(name, len, hash);
303   assert((sym == nullptr) || sym->refcount() != 0, "refcount must not be zero");
304   return sym;
305 }
306 
307 #if INCLUDE_CDS
308 Symbol* SymbolTable::lookup_shared(const char* name,
309                                    int len, unsigned int hash) {
310   Symbol* sym = nullptr;
311   if (!_shared_table.empty()) {
312     if (_alt_hash) {
313       // hash_code parameter may use alternate hashing algorithm but the shared table
314       // always uses the same original hash code.
315       hash = hash_shared_symbol(name, len);
316     }
317     sym = _shared_table.lookup(name, hash, len);
318     if (sym == nullptr && DynamicArchive::is_mapped()) {
319       sym = _dynamic_shared_table.lookup(name, hash, len);
320     }
321   }
322   return sym;
323 }
324 #endif
325 
326 Symbol* SymbolTable::lookup_common(const char* name,
327                             int len, unsigned int hash) {
328   Symbol* sym;
329   if (_lookup_shared_first) {
330     sym = lookup_shared(name, len, hash);
331     if (sym == nullptr) {
332       _lookup_shared_first = false;
333       sym = lookup_dynamic(name, len, hash);
334     }
335   } else {
336     sym = lookup_dynamic(name, len, hash);
337     if (sym == nullptr) {
338       sym = lookup_shared(name, len, hash);
339       if (sym != nullptr) {
340         _lookup_shared_first = true;
341       }
342     }
343   }
344   return sym;
345 }
346 
347 Symbol* SymbolTable::new_symbol(const char* name, int len) {
348   assert(len <= Symbol::max_length(), "sanity");
349   unsigned int hash = hash_symbol(name, len, _alt_hash);
350   Symbol* sym = lookup_common(name, len, hash);
351   if (sym == nullptr) {
352     sym = do_add_if_needed(name, len, hash, /* is_permanent */ false);
353   }
354   assert(sym->refcount() != 0, "lookup should have incremented the count");
355   assert(sym->equals(name, len), "symbol must be properly initialized");
356   return sym;
357 }
358 
359 Symbol* SymbolTable::new_symbol(const Symbol* sym, int begin, int end) {
360   assert(begin <= end && end <= sym->utf8_length(), "just checking");
361   assert(sym->refcount() != 0, "require a valid symbol");
362   const char* name = (const char*)sym->base() + begin;
363   int len = end - begin;
364   assert(len <= Symbol::max_length(), "sanity");
365   unsigned int hash = hash_symbol(name, len, _alt_hash);
366   Symbol* found = lookup_common(name, len, hash);
367   if (found == nullptr) {
368     found = do_add_if_needed(name, len, hash, /* is_permanent */ false);
369   }
370   return found;
371 }
372 
373 class SymbolTableLookup : StackObj {
374 private:
375   uintx _hash;
376   int _len;
377   const char* _str;
378 public:
379   SymbolTableLookup(const char* key, int len, uintx hash)
380   : _hash(hash), _len(len), _str(key) {}
381   uintx get_hash() const {
382     return _hash;
383   }
384   // Note: When equals() returns "true", the symbol's refcount is incremented. This is
385   // needed to ensure that the symbol is kept alive before equals() returns to the caller,
386   // so that another thread cannot clean the symbol up concurrently. The caller is
387   // responsible for decrementing the refcount, when the symbol is no longer needed.
388   bool equals(Symbol* value) {
389     assert(value != nullptr, "expected valid value");
390     Symbol *sym = value;
391     if (sym->equals(_str, _len)) {
392       if (sym->try_increment_refcount()) {
393         // something is referencing this symbol now.
394         return true;
395       } else {
396         assert(sym->refcount() == 0, "expected dead symbol");
397         return false;
398       }
399     } else {
400       return false;
401     }
402   }
403   bool is_dead(Symbol* value) {
404     return value->refcount() == 0;
405   }
406 };
407 
408 class SymbolTableGet : public StackObj {
409   Symbol* _return;
410 public:
411   SymbolTableGet() : _return(nullptr) {}
412   void operator()(Symbol* value) {
413     assert(value != nullptr, "expected valid value");
414     _return = value;
415   }
416   Symbol* get_res_sym() const {
417     return _return;
418   }
419 };
420 
421 void SymbolTable::update_needs_rehash(bool rehash) {
422   if (rehash) {
423     _needs_rehashing = true;
424     trigger_cleanup();
425   }
426 }
427 
428 Symbol* SymbolTable::do_lookup(const char* name, int len, uintx hash) {
429   Thread* thread = Thread::current();
430   SymbolTableLookup lookup(name, len, hash);
431   SymbolTableGet stg;
432   bool rehash_warning = false;
433   _local_table->get(thread, lookup, stg, &rehash_warning);
434   update_needs_rehash(rehash_warning);
435   Symbol* sym = stg.get_res_sym();
436   assert((sym == nullptr) || sym->refcount() != 0, "found dead symbol");
437   return sym;
438 }
439 
440 Symbol* SymbolTable::lookup_only(const char* name, int len, unsigned int& hash) {
441   hash = hash_symbol(name, len, _alt_hash);
442   return lookup_common(name, len, hash);
443 }
444 
445 // Suggestion: Push unicode-based lookup all the way into the hashing
446 // and probing logic, so there is no need for convert_to_utf8 until
447 // an actual new Symbol* is created.
448 Symbol* SymbolTable::new_symbol(const jchar* name, int utf16_length) {
449   int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
450   char stack_buf[ON_STACK_BUFFER_LENGTH];
451   if (utf8_length < (int) sizeof(stack_buf)) {
452     char* chars = stack_buf;
453     UNICODE::convert_to_utf8(name, utf16_length, chars);
454     return new_symbol(chars, utf8_length);
455   } else {
456     ResourceMark rm;
457     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
458     UNICODE::convert_to_utf8(name, utf16_length, chars);
459     return new_symbol(chars, utf8_length);
460   }
461 }
462 
463 Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,
464                                          unsigned int& hash) {
465   int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
466   char stack_buf[ON_STACK_BUFFER_LENGTH];
467   if (utf8_length < (int) sizeof(stack_buf)) {
468     char* chars = stack_buf;
469     UNICODE::convert_to_utf8(name, utf16_length, chars);
470     return lookup_only(chars, utf8_length, hash);
471   } else {
472     ResourceMark rm;
473     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
474     UNICODE::convert_to_utf8(name, utf16_length, chars);
475     return lookup_only(chars, utf8_length, hash);
476   }
477 }
478 
479 void SymbolTable::new_symbols(ClassLoaderData* loader_data, const constantPoolHandle& cp,
480                               int names_count, const char** names, int* lengths,
481                               int* cp_indices, unsigned int* hashValues) {
482   // Note that is_permanent will be false for non-strong hidden classes.
483   // even if their loader is the boot loader because they will have a different cld.
484   bool is_permanent = loader_data->is_the_null_class_loader_data();
485   for (int i = 0; i < names_count; i++) {
486     const char *name = names[i];
487     int len = lengths[i];
488     unsigned int hash = hashValues[i];
489     assert(lookup_shared(name, len, hash) == nullptr, "must have checked already");
490     Symbol* sym = do_add_if_needed(name, len, hash, is_permanent);
491     assert(sym->refcount() != 0, "lookup should have incremented the count");
492     cp->symbol_at_put(cp_indices[i], sym);
493   }
494 }
495 
496 Symbol* SymbolTable::do_add_if_needed(const char* name, int len, uintx hash, bool is_permanent) {
497   SymbolTableLookup lookup(name, len, hash);
498   SymbolTableGet stg;
499   bool clean_hint = false;
500   bool rehash_warning = false;
501   Thread* current = Thread::current();
502   Symbol* sym;
503 
504   ResourceMark rm(current);
505   const int alloc_size = Symbol::byte_size(len);
506   u1* u1_buf = NEW_RESOURCE_ARRAY_IN_THREAD(current, u1, alloc_size);
507   Symbol* tmp = ::new ((void*)u1_buf) Symbol((const u1*)name, len,
508                                              (is_permanent || CDSConfig::is_dumping_static_archive()) ? PERM_REFCOUNT : 1);
509 
510   do {
511     if (_local_table->insert(current, lookup, *tmp, &rehash_warning, &clean_hint)) {
512       if (_local_table->get(current, lookup, stg, &rehash_warning)) {
513         sym = stg.get_res_sym();
514         // The get adds one to ref count, but we inserted with our ref already included.
515         // Therefore decrement with one.
516         if (sym->refcount() != PERM_REFCOUNT) {
517           sym->decrement_refcount();
518         }
519         break;
520       }
521     }
522 
523     // In case another thread did a concurrent add, return value already in the table.
524     // This could fail if the symbol got deleted concurrently, so loop back until success.
525     if (_local_table->get(current, lookup, stg, &rehash_warning)) {
526       // The lookup added a refcount, which is ours.
527       sym = stg.get_res_sym();
528       break;
529     }
530   } while(true);
531 
532   update_needs_rehash(rehash_warning);
533 
534   if (clean_hint) {
535     mark_has_items_to_clean();
536     check_concurrent_work();
537   }
538 
539   assert((sym == nullptr) || sym->refcount() != 0, "found dead symbol");
540   return sym;
541 }
542 
543 Symbol* SymbolTable::new_permanent_symbol(const char* name) {
544   unsigned int hash = 0;
545   int len = (int)strlen(name);
546   Symbol* sym = SymbolTable::lookup_only(name, len, hash);
547   if (sym == nullptr) {
548     sym = do_add_if_needed(name, len, hash, /* is_permanent */ true);
549   }
550   if (!sym->is_permanent()) {
551     sym->make_permanent();
552     log_trace_symboltable_helper(sym, "Asked for a permanent symbol, but got a regular one");
553   }
554   return sym;
555 }
556 
557 struct SizeFunc : StackObj {
558   size_t operator()(Symbol* value) {
559     assert(value != nullptr, "expected valid value");
560     return (value)->size() * HeapWordSize;
561   };
562 };
563 
564 TableStatistics SymbolTable::get_table_statistics() {
565   static TableStatistics ts;
566   SizeFunc sz;
567   ts = _local_table->statistics_get(Thread::current(), sz, ts);
568   return ts;
569 }
570 
571 void SymbolTable::print_table_statistics(outputStream* st) {
572   SizeFunc sz;
573   _local_table->statistics_to(Thread::current(), sz, st, "SymbolTable");
574 
575   if (!_shared_table.empty()) {
576     _shared_table.print_table_statistics(st, "Shared Symbol Table");
577   }
578 
579   if (!_dynamic_shared_table.empty()) {
580     _dynamic_shared_table.print_table_statistics(st, "Dynamic Shared Symbol Table");
581   }
582 }
583 
584 // Verification
585 class VerifySymbols : StackObj {
586 public:
587   bool operator()(Symbol* value) {
588     guarantee(value != nullptr, "expected valid value");
589     Symbol* sym = value;
590     guarantee(sym->equals((const char*)sym->bytes(), sym->utf8_length()),
591               "symbol must be internally consistent");
592     return true;
593   };
594 };
595 
596 void SymbolTable::verify() {
597   Thread* thr = Thread::current();
598   VerifySymbols vs;
599   if (!_local_table->try_scan(thr, vs)) {
600     log_info(symboltable)("verify unavailable at this moment");
601   }
602 }
603 
604 static void print_symbol(outputStream* st, Symbol* sym) {
605   const char* utf8_string = (const char*)sym->bytes();
606   int utf8_length = sym->utf8_length();
607   st->print("%d %d: ", utf8_length, sym->refcount());
608   HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
609   st->cr();
610 }
611 
612 // Dumping
613 class DumpSymbol : StackObj {
614   Thread* _thr;
615   outputStream* _st;
616 public:
617   DumpSymbol(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
618   bool operator()(Symbol* value) {
619     assert(value != nullptr, "expected valid value");
620     print_symbol(_st, value);
621     return true;
622   };
623 };
624 
625 class DumpSharedSymbol : StackObj {
626   outputStream* _st;
627 public:
628   DumpSharedSymbol(outputStream* st) : _st(st) {}
629   void do_value(Symbol* value) {
630     assert(value != nullptr, "value should point to a symbol");
631     print_symbol(_st, value);
632   };
633 };
634 
635 void SymbolTable::dump(outputStream* st, bool verbose) {
636   if (!verbose) {
637     print_table_statistics(st);
638   } else {
639     Thread* thr = Thread::current();
640     ResourceMark rm(thr);
641     st->print_cr("VERSION: 1.1");
642     DumpSymbol ds(thr, st);
643     if (!_local_table->try_scan(thr, ds)) {
644       log_info(symboltable)("dump unavailable at this moment");
645     }
646     if (!_shared_table.empty()) {
647       st->print_cr("#----------------");
648       st->print_cr("# Shared symbols:");
649       st->print_cr("#----------------");
650       DumpSharedSymbol dss(st);
651       _shared_table.iterate(&dss);
652     }
653     if (!_dynamic_shared_table.empty()) {
654       st->print_cr("#------------------------");
655       st->print_cr("# Dynamic shared symbols:");
656       st->print_cr("#------------------------");
657       DumpSharedSymbol dss(st);
658       _dynamic_shared_table.iterate(&dss);
659     }
660   }
661 }
662 
663 #if INCLUDE_CDS
664 void SymbolTable::copy_shared_symbol_table(GrowableArray<Symbol*>* symbols,
665                                            CompactHashtableWriter* writer) {
666   ArchiveBuilder* builder = ArchiveBuilder::current();
667   int len = symbols->length();
668   for (int i = 0; i < len; i++) {
669     Symbol* sym = ArchiveBuilder::get_buffered_symbol(symbols->at(i));
670     unsigned int fixed_hash = hash_shared_symbol((const char*)sym->bytes(), sym->utf8_length());
671     assert(fixed_hash == hash_symbol((const char*)sym->bytes(), sym->utf8_length(), false),
672            "must not rehash during dumping");
673     sym->set_permanent();
674     writer->add(fixed_hash, builder->buffer_to_offset_u4((address)sym));
675   }
676 }
677 
678 size_t SymbolTable::estimate_size_for_archive() {
679   if (_items_count > (size_t)max_jint) {
680     fatal("Too many symbols to be archived: %zu", _items_count);
681   }
682   return CompactHashtableWriter::estimate_size(int(_items_count));
683 }
684 
685 void SymbolTable::write_to_archive(GrowableArray<Symbol*>* symbols) {
686   CompactHashtableWriter writer(int(_items_count), ArchiveBuilder::symbol_stats());
687   copy_shared_symbol_table(symbols, &writer);
688   if (CDSConfig::is_dumping_static_archive()) {
689     _shared_table.reset();
690     writer.dump(&_shared_table, "symbol");
691   } else {
692     assert(CDSConfig::is_dumping_dynamic_archive(), "must be");
693     _dynamic_shared_table.reset();
694     writer.dump(&_dynamic_shared_table, "symbol");
695   }
696 }
697 
698 void SymbolTable::serialize_shared_table_header(SerializeClosure* soc,
699                                                 bool is_static_archive) {
700   OffsetCompactHashtable<const char*, Symbol*, symbol_equals_compact_hashtable_entry> * table;
701   if (is_static_archive) {
702     table = &_shared_table;
703   } else {
704     table = &_dynamic_shared_table;
705   }
706   table->serialize_header(soc);
707   if (soc->writing()) {
708     // Sanity. Make sure we don't use the shared table at dump time
709     table->reset();
710   }
711 }
712 #endif //INCLUDE_CDS
713 
714 // Concurrent work
715 void SymbolTable::grow(JavaThread* jt) {
716   SymbolTableHash::GrowTask gt(_local_table);
717   if (!gt.prepare(jt)) {
718     return;
719   }
720   log_trace(symboltable)("Started to grow");
721   {
722     TraceTime timer("Grow", TRACETIME_LOG(Debug, symboltable, perf));
723     while (gt.do_task(jt)) {
724       gt.pause(jt);
725       {
726         ThreadBlockInVM tbivm(jt);
727       }
728       gt.cont(jt);
729     }
730   }
731   gt.done(jt);
732   _current_size = table_size();
733   log_debug(symboltable)("Grown to size:" SIZE_FORMAT, _current_size);
734 }
735 
736 struct SymbolTableDoDelete : StackObj {
737   size_t _deleted;
738   SymbolTableDoDelete() : _deleted(0) {}
739   void operator()(Symbol* value) {
740     assert(value != nullptr, "expected valid value");
741     Symbol *sym = value;
742     assert(sym->refcount() == 0, "refcount");
743     _deleted++;
744   }
745 };
746 
747 struct SymbolTableDeleteCheck : StackObj {
748   size_t _processed;
749   SymbolTableDeleteCheck() : _processed(0) {}
750   bool operator()(Symbol* value) {
751     assert(value != nullptr, "expected valid value");
752     _processed++;
753     Symbol *sym = value;
754     return (sym->refcount() == 0);
755   }
756 };
757 
758 void SymbolTable::clean_dead_entries(JavaThread* jt) {
759   SymbolTableHash::BulkDeleteTask bdt(_local_table);
760   if (!bdt.prepare(jt)) {
761     return;
762   }
763 
764   SymbolTableDeleteCheck stdc;
765   SymbolTableDoDelete stdd;
766   NativeHeapTrimmer::SuspendMark sm("symboltable");
767   {
768     TraceTime timer("Clean", TRACETIME_LOG(Debug, symboltable, perf));
769     while (bdt.do_task(jt, stdc, stdd)) {
770       bdt.pause(jt);
771       {
772         ThreadBlockInVM tbivm(jt);
773       }
774       bdt.cont(jt);
775     }
776     reset_has_items_to_clean();
777     bdt.done(jt);
778   }
779 
780   Atomic::add(&_symbols_counted, stdc._processed);
781 
782   log_debug(symboltable)("Cleaned " SIZE_FORMAT " of " SIZE_FORMAT,
783                          stdd._deleted, stdc._processed);
784 }
785 
786 void SymbolTable::check_concurrent_work() {
787   if (has_work()) {
788     return;
789   }
790   // We should clean/resize if we have
791   // more items than preferred load factor or
792   // more dead items than water mark.
793   if (has_items_to_clean() || (get_load_factor() > PREF_AVG_LIST_LEN)) {
794     log_debug(symboltable)("Concurrent work triggered, load factor: %f, items to clean: %s",
795                            get_load_factor(), has_items_to_clean() ? "true" : "false");
796     trigger_cleanup();
797   }
798 }
799 
800 bool SymbolTable::should_grow() {
801   return get_load_factor() > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached();
802 }
803 
804 void SymbolTable::do_concurrent_work(JavaThread* jt) {
805   // Rehash if needed.  Rehashing goes to a safepoint but the rest of this
806   // work is concurrent.
807   if (needs_rehashing() && maybe_rehash_table()) {
808     Atomic::release_store(&_has_work, false);
809     return; // done, else grow
810   }
811   log_debug(symboltable, perf)("Concurrent work, live factor: %g", get_load_factor());
812   // We prefer growing, since that also removes dead items
813   if (should_grow()) {
814     grow(jt);
815   } else {
816     clean_dead_entries(jt);
817   }
818   Atomic::release_store(&_has_work, false);
819 }
820 
821 // Called at VM_Operation safepoint
822 void SymbolTable::rehash_table() {
823   assert(SafepointSynchronize::is_at_safepoint(), "must be called at safepoint");
824   // The ServiceThread initiates the rehashing so it is not resizing.
825   assert (_local_table->is_safepoint_safe(), "Should not be resizing now");
826 
827   _alt_hash_seed = AltHashing::compute_seed();
828 
829   // We use current size
830   size_t new_size = _local_table->get_size_log2(Thread::current());
831   SymbolTableHash* new_table = new SymbolTableHash(new_size, END_SIZE, REHASH_LEN, true);
832   // Use alt hash from now on
833   _alt_hash = true;
834   _local_table->rehash_nodes_to(Thread::current(), new_table);
835 
836   // free old table
837   delete _local_table;
838   _local_table = new_table;
839 
840   _rehashed = true;
841   _needs_rehashing = false;
842 }
843 
844 bool SymbolTable::maybe_rehash_table() {
845   log_debug(symboltable)("Table imbalanced, rehashing called.");
846 
847   // Grow instead of rehash.
848   if (should_grow()) {
849     log_debug(symboltable)("Choosing growing over rehashing.");
850     _needs_rehashing = false;
851     return false;
852   }
853 
854   // Already rehashed.
855   if (_rehashed) {
856     log_warning(symboltable)("Rehashing already done, still long lists.");
857     _needs_rehashing = false;
858     return false;
859   }
860 
861   VM_RehashSymbolTable op;
862   VMThread::execute(&op);
863   return true;
864 }
865 
866 //---------------------------------------------------------------------------
867 // Non-product code
868 
869 #ifndef PRODUCT
870 
871 class HistogramIterator : StackObj {
872 public:
873   static const size_t results_length = 100;
874   size_t counts[results_length];
875   size_t sizes[results_length];
876   size_t total_size;
877   size_t total_count;
878   size_t total_length;
879   size_t max_length;
880   size_t out_of_range_count;
881   size_t out_of_range_size;
882   HistogramIterator() : total_size(0), total_count(0), total_length(0),
883                         max_length(0), out_of_range_count(0), out_of_range_size(0) {
884     // initialize results to zero
885     for (size_t i = 0; i < results_length; i++) {
886       counts[i] = 0;
887       sizes[i] = 0;
888     }
889   }
890   bool operator()(Symbol* value) {
891     assert(value != nullptr, "expected valid value");
892     Symbol* sym = value;
893     size_t size = sym->size();
894     size_t len = sym->utf8_length();
895     if (len < results_length) {
896       counts[len]++;
897       sizes[len] += size;
898     } else {
899       out_of_range_count++;
900       out_of_range_size += size;
901     }
902     total_count++;
903     total_size += size;
904     total_length += len;
905     max_length = MAX2(max_length, len);
906 
907     return true;
908   };
909 };
910 
911 void SymbolTable::print_histogram() {
912   HistogramIterator hi;
913   _local_table->do_scan(Thread::current(), hi);
914   tty->print_cr("Symbol Table Histogram:");
915   tty->print_cr("  Total number of symbols  " SIZE_FORMAT_W(7), hi.total_count);
916   tty->print_cr("  Total size in memory     " SIZE_FORMAT_W(7) "K", (hi.total_size * wordSize) / K);
917   tty->print_cr("  Total counted            " SIZE_FORMAT_W(7), _symbols_counted);
918   tty->print_cr("  Total removed            " SIZE_FORMAT_W(7), _symbols_removed);
919   if (_symbols_counted > 0) {
920     tty->print_cr("  Percent removed          %3.2f",
921           ((double)_symbols_removed / (double)_symbols_counted) * 100);
922   }
923   tty->print_cr("  Reference counts         " SIZE_FORMAT_W(7), Symbol::_total_count);
924   tty->print_cr("  Symbol arena used        " SIZE_FORMAT_W(7) "K", arena()->used() / K);
925   tty->print_cr("  Symbol arena size        " SIZE_FORMAT_W(7) "K", arena()->size_in_bytes() / K);
926   tty->print_cr("  Total symbol length      " SIZE_FORMAT_W(7), hi.total_length);
927   tty->print_cr("  Maximum symbol length    " SIZE_FORMAT_W(7), hi.max_length);
928   tty->print_cr("  Average symbol length    %7.2f", ((double)hi.total_length / (double)hi.total_count));
929   tty->print_cr("  Symbol length histogram:");
930   tty->print_cr("    %6s %10s %10s", "Length", "#Symbols", "Size");
931   for (size_t i = 0; i < hi.results_length; i++) {
932     if (hi.counts[i] > 0) {
933       tty->print_cr("    " SIZE_FORMAT_W(6) " " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) "K",
934                     i, hi.counts[i], (hi.sizes[i] * wordSize) / K);
935     }
936   }
937   tty->print_cr("  >=" SIZE_FORMAT_W(6) " " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) "K\n",
938                 hi.results_length, hi.out_of_range_count, (hi.out_of_range_size*wordSize) / K);
939 }
940 #endif // PRODUCT
941 
942 // Utility for dumping symbols
943 SymboltableDCmd::SymboltableDCmd(outputStream* output, bool heap) :
944                                  DCmdWithParser(output, heap),
945   _verbose("-verbose", "Dump the content of each symbol in the table",
946            "BOOLEAN", false, "false") {
947   _dcmdparser.add_dcmd_option(&_verbose);
948 }
949 
950 void SymboltableDCmd::execute(DCmdSource source, TRAPS) {
951   VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpSymbols,
952                          _verbose.value());
953   VMThread::execute(&dumper);
954 }