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