1 /*
  2  * Copyright (c) 1997, 2025, Oracle and/or its affiliates. All rights reserved.
  3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  4  *
  5  * This code is free software; you can redistribute it and/or modify it
  6  * under the terms of the GNU General Public License version 2 only, as
  7  * published by the Free Software Foundation.
  8  *
  9  * This code is distributed in the hope that it will be useful, but WITHOUT
 10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 12  * version 2 for more details (a copy is included in the LICENSE file that
 13  * accompanied this code).
 14  *
 15  * You should have received a copy of the GNU General Public License version
 16  * 2 along with this work; if not, write to the Free Software Foundation,
 17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 18  *
 19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 20  * or visit www.oracle.com if you need additional information or have any
 21  * questions.
 22  *
 23  */
 24 
 25 #include "cds/archiveBuilder.hpp"
 26 #include "cds/cdsConfig.hpp"
 27 #include "cds/dynamicArchive.hpp"
 28 #include "classfile/altHashing.hpp"
 29 #include "classfile/classLoaderData.hpp"
 30 #include "classfile/compactHashtable.hpp"
 31 #include "classfile/javaClasses.hpp"
 32 #include "classfile/symbolTable.hpp"
 33 #include "memory/allocation.inline.hpp"
 34 #include "memory/metaspaceClosure.hpp"
 35 #include "memory/resourceArea.hpp"
 36 #include "oops/oop.inline.hpp"
 37 #include "runtime/atomic.hpp"
 38 #include "runtime/interfaceSupport.inline.hpp"
 39 #include "runtime/timerTrace.hpp"
 40 #include "runtime/trimNativeHeap.hpp"
 41 #include "services/diagnosticCommand.hpp"
 42 #include "utilities/concurrentHashTable.inline.hpp"
 43 #include "utilities/concurrentHashTableTasks.inline.hpp"
 44 #include "utilities/utf8.hpp"
 45 
 46 // We used to not resize at all, so let's be conservative
 47 // and not set it too short before we decide to resize,
 48 // to match previous startup behavior
 49 const double PREF_AVG_LIST_LEN = 8.0;
 50 // 2^24 is max size, like StringTable.
 51 const size_t END_SIZE = 24;
 52 // If a chain gets to 100 something might be wrong
 53 const size_t REHASH_LEN = 100;
 54 
 55 const size_t ON_STACK_BUFFER_LENGTH = 128;
 56 
 57 // --------------------------------------------------------------------------
 58 
 59 inline bool symbol_equals_compact_hashtable_entry(Symbol* value, const char* key, int len) {
 60   if (value->equals(key, len)) {
 61     return true;
 62   } else {
 63     return false;
 64   }
 65 }
 66 
 67 static OffsetCompactHashtable<
 68   const char*, Symbol*,
 69   symbol_equals_compact_hashtable_entry
 70 > _shared_table, _dynamic_shared_table, _shared_table_for_dumping;





 71 
 72 // --------------------------------------------------------------------------
 73 
 74 typedef ConcurrentHashTable<SymbolTableConfig, mtSymbol> SymbolTableHash;
 75 static SymbolTableHash* _local_table = nullptr;
 76 
 77 volatile bool SymbolTable::_has_work = 0;
 78 volatile bool SymbolTable::_needs_rehashing = false;
 79 
 80 // For statistics
 81 static size_t _symbols_removed = 0;
 82 static size_t _symbols_counted = 0;
 83 static size_t _current_size = 0;
 84 
 85 static volatile size_t _items_count = 0;
 86 static volatile bool   _has_items_to_clean = false;
 87 
 88 
 89 static volatile bool _alt_hash = false;
 90 
 91 #ifdef USE_LIBRARY_BASED_TLS_ONLY
 92 static volatile bool _lookup_shared_first = false;
 93 #else
 94 // "_lookup_shared_first" can get highly contended with many cores if multiple threads
 95 // are updating "lookup success history" in a global shared variable. If built-in TLS is available, use it.
 96 static THREAD_LOCAL bool _lookup_shared_first = false;
 97 #endif
 98 
 99 // Static arena for symbols that are not deallocated
100 Arena* SymbolTable::_arena = nullptr;
101 
102 static bool _rehashed = false;
103 static uint64_t _alt_hash_seed = 0;
104 
105 static inline void log_trace_symboltable_helper(Symbol* sym, const char* msg) {
106 #ifndef PRODUCT
107   ResourceMark rm;
108   log_trace(symboltable)("%s [%s]", msg, sym->as_quoted_ascii());
109 #endif // PRODUCT
110 }
111 
112 // Pick hashing algorithm.
113 static unsigned int hash_symbol(const char* s, int len, bool useAlt) {
114   return useAlt ?
115   AltHashing::halfsiphash_32(_alt_hash_seed, (const uint8_t*)s, len) :
116   java_lang_String::hash_code((const jbyte*)s, len);
117 }
118 
119 #if INCLUDE_CDS
120 static unsigned int hash_shared_symbol(const char* s, int len) {
121   return java_lang_String::hash_code((const jbyte*)s, len);
122 }
123 #endif
124 
125 class SymbolTableConfig : public AllStatic {
126 
127 public:
128   typedef Symbol Value;  // value of the Node in the hashtable
129 
130   static uintx get_hash(Value const& value, bool* is_dead) {
131     *is_dead = (value.refcount() == 0);
132     if (*is_dead) {
133       return 0;
134     } else {
135       return hash_symbol((const char*)value.bytes(), value.utf8_length(), _alt_hash);
136     }
137   }
138   // We use default allocation/deallocation but counted
139   static void* allocate_node(void* context, size_t size, Value const& value) {
140     SymbolTable::item_added();
141     return allocate_node_impl(size, value);
142   }
143   static void free_node(void* context, void* memory, Value & value) {
144     // We get here because #1 some threads lost a race to insert a newly created Symbol
145     // or #2 we're cleaning up unused symbol.
146     // If #1, then the symbol can be either permanent,
147     // or regular newly created one (refcount==1)
148     // If #2, then the symbol is dead (refcount==0)
149     assert(value.is_permanent() || (value.refcount() == 1) || (value.refcount() == 0),
150            "refcount %d", value.refcount());
151 #if INCLUDE_CDS
152     if (CDSConfig::is_dumping_static_archive()) {
153       // We have allocated with MetaspaceShared::symbol_space_alloc(). No deallocation is needed.
154       // Unreferenced Symbols will not be copied into the archive.
155       return;
156     }
157 #endif
158     if (value.refcount() == 1) {
159       value.decrement_refcount();
160       assert(value.refcount() == 0, "expected dead symbol");
161     }
162     if (value.refcount() != PERM_REFCOUNT) {
163       FreeHeap(memory);
164     } else {
165       MutexLocker ml(SymbolArena_lock, Mutex::_no_safepoint_check_flag); // Protect arena
166       // Deleting permanent symbol should not occur very often (insert race condition),
167       // so log it.
168       log_trace_symboltable_helper(&value, "Freeing permanent symbol");
169       size_t alloc_size = SymbolTableHash::get_dynamic_node_size(value.byte_size());
170       if (!SymbolTable::arena()->Afree(memory, alloc_size)) {
171         // Can't access the symbol after Afree, but we just printed it above.
172         NOT_PRODUCT(log_trace(symboltable)(" - 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 = SymbolTableHash::get_dynamic_node_size(value.byte_size());
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 = nullptr);
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 = log2i_ceil(SymbolTableSize);
210   _current_size = ((size_t)1) << start_size_log_2;
211   log_trace(symboltable)("Start size: %zu (%zu)",
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 bool SymbolTable::has_work() { return Atomic::load_acquire(&_has_work); }
245 
246 void SymbolTable::trigger_cleanup() {
247   // Avoid churn on ServiceThread
248   if (!has_work()) {
249     MutexLocker ml(Service_lock, Mutex::_no_safepoint_check_flag);
250     _has_work = true;
251     Service_lock->notify_all();
252   }
253 }
254 
255 class SymbolsDo : StackObj {
256   SymbolClosure *_cl;
257 public:
258   SymbolsDo(SymbolClosure *cl) : _cl(cl) {}
259   bool operator()(Symbol* value) {
260     assert(value != nullptr, "expected valid value");
261     _cl->do_symbol(&value);
262     return true;
263   };
264 };
265 
266 class SharedSymbolIterator {
267   SymbolClosure* _symbol_closure;
268 public:
269   SharedSymbolIterator(SymbolClosure* f) : _symbol_closure(f) {}
270   void do_value(Symbol* symbol) {
271     _symbol_closure->do_symbol(&symbol);
272   }
273 };
274 
275 // Call function for all symbols in the symbol table.
276 void SymbolTable::symbols_do(SymbolClosure *cl) {
277   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint");
278   // all symbols from shared table
279   SharedSymbolIterator iter(cl);
280   _shared_table.iterate(&iter);
281   _dynamic_shared_table.iterate(&iter);
282 
283   // all symbols from the dynamic table
284   SymbolsDo sd(cl);
285   _local_table->do_safepoint_scan(sd);
286 }
287 
288 // Call function for all symbols in shared table. Used by -XX:+PrintSharedArchiveAndExit
289 void SymbolTable::shared_symbols_do(SymbolClosure *cl) {
290   SharedSymbolIterator iter(cl);
291   _shared_table.iterate(&iter);
292   _dynamic_shared_table.iterate(&iter);
293 }
294 
295 Symbol* SymbolTable::lookup_dynamic(const char* name,
296                                     int len, unsigned int hash) {
297   Symbol* sym = do_lookup(name, len, hash);
298   assert((sym == nullptr) || sym->refcount() != 0, "refcount must not be zero");
299   return sym;
300 }
301 
302 #if INCLUDE_CDS
303 Symbol* SymbolTable::lookup_shared(const char* name,
304                                    int len, unsigned int hash) {
305   Symbol* sym = nullptr;
306   if (!_shared_table.empty()) {
307     if (_alt_hash) {
308       // hash_code parameter may use alternate hashing algorithm but the shared table
309       // always uses the same original hash code.
310       hash = hash_shared_symbol(name, len);
311     }
312     sym = _shared_table.lookup(name, hash, len);
313     if (sym == nullptr && DynamicArchive::is_mapped()) {
314       sym = _dynamic_shared_table.lookup(name, hash, len);
315     }
316   }
317   return sym;
318 }
319 #endif
320 
321 Symbol* SymbolTable::lookup_common(const char* name,
322                             int len, unsigned int hash) {
323   Symbol* sym;
324   if (_lookup_shared_first) {
325     sym = lookup_shared(name, len, hash);
326     if (sym == nullptr) {
327       _lookup_shared_first = false;
328       sym = lookup_dynamic(name, len, hash);
329     }
330   } else {
331     sym = lookup_dynamic(name, len, hash);
332     if (sym == nullptr) {
333       sym = lookup_shared(name, len, hash);
334       if (sym != nullptr) {
335         _lookup_shared_first = true;
336       }
337     }
338   }
339   return sym;
340 }
341 
342 // Symbols should represent entities from the constant pool that are
343 // limited to <64K in length, but usage errors creep in allowing Symbols
344 // to be used for arbitrary strings. For debug builds we will assert if
345 // a string is too long, whereas product builds will truncate it.
346 static int check_length(const char* name, int len) {
347   assert(len >= 0, "negative length %d suggests integer overflow in the caller", len);
348   assert(len <= Symbol::max_length(),
349          "String length %d exceeds the maximum Symbol length of %d", len, Symbol::max_length());
350   if (len > Symbol::max_length()) {
351     warning("A string \"%.80s ... %.80s\" exceeds the maximum Symbol "
352             "length of %d and has been truncated", name, (name + len - 80), Symbol::max_length());
353     len = Symbol::max_length();
354   }
355   return len;
356 }
357 
358 Symbol* SymbolTable::new_symbol(const char* name, int len) {
359   len = check_length(name, len);
360   unsigned int hash = hash_symbol(name, len, _alt_hash);
361   Symbol* sym = lookup_common(name, len, hash);
362   if (sym == nullptr) {
363     sym = do_add_if_needed(name, len, hash, /* is_permanent */ false);
364   }
365   assert(sym->refcount() != 0, "lookup should have incremented the count");
366   assert(sym->equals(name, len), "symbol must be properly initialized");
367   return sym;
368 }
369 
370 Symbol* SymbolTable::new_symbol(const Symbol* sym, int begin, int end) {
371   assert(begin <= end && end <= sym->utf8_length(), "just checking");
372   assert(sym->refcount() != 0, "require a valid symbol");
373   const char* name = (const char*)sym->base() + begin;
374   int len = end - begin;
375   assert(len <= Symbol::max_length(), "sanity");
376   unsigned int hash = hash_symbol(name, len, _alt_hash);
377   Symbol* found = lookup_common(name, len, hash);
378   if (found == nullptr) {
379     found = do_add_if_needed(name, len, hash, /* is_permanent */ false);
380   }
381   return found;
382 }
383 
384 class SymbolTableLookup : StackObj {
385 private:
386   uintx _hash;
387   int _len;
388   const char* _str;
389 public:
390   SymbolTableLookup(const char* key, int len, uintx hash)
391   : _hash(hash), _len(len), _str(key) {}
392   uintx get_hash() const {
393     return _hash;
394   }
395   // Note: When equals() returns "true", the symbol's refcount is incremented. This is
396   // needed to ensure that the symbol is kept alive before equals() returns to the caller,
397   // so that another thread cannot clean the symbol up concurrently. The caller is
398   // responsible for decrementing the refcount, when the symbol is no longer needed.
399   bool equals(Symbol* value) {
400     assert(value != nullptr, "expected valid value");
401     Symbol *sym = value;
402     if (sym->equals(_str, _len)) {
403       if (sym->try_increment_refcount()) {
404         // something is referencing this symbol now.
405         return true;
406       } else {
407         assert(sym->refcount() == 0, "expected dead symbol");
408         return false;
409       }
410     } else {
411       return false;
412     }
413   }
414   bool is_dead(Symbol* value) {
415     return value->refcount() == 0;
416   }
417 };
418 
419 class SymbolTableGet : public StackObj {
420   Symbol* _return;
421 public:
422   SymbolTableGet() : _return(nullptr) {}
423   void operator()(Symbol* value) {
424     assert(value != nullptr, "expected valid value");
425     _return = value;
426   }
427   Symbol* get_res_sym() const {
428     return _return;
429   }
430 };
431 
432 void SymbolTable::update_needs_rehash(bool rehash) {
433   if (rehash) {
434     _needs_rehashing = true;
435     trigger_cleanup();
436   }
437 }
438 
439 Symbol* SymbolTable::do_lookup(const char* name, int len, uintx hash) {
440   Thread* thread = Thread::current();
441   SymbolTableLookup lookup(name, len, hash);
442   SymbolTableGet stg;
443   bool rehash_warning = false;
444   _local_table->get(thread, lookup, stg, &rehash_warning);
445   update_needs_rehash(rehash_warning);
446   Symbol* sym = stg.get_res_sym();
447   assert((sym == nullptr) || sym->refcount() != 0, "found dead symbol");
448   return sym;
449 }
450 
451 Symbol* SymbolTable::lookup_only(const char* name, int len, unsigned int& hash) {
452   hash = hash_symbol(name, len, _alt_hash);
453   return lookup_common(name, len, hash);
454 }
455 
456 // Suggestion: Push unicode-based lookup all the way into the hashing
457 // and probing logic, so there is no need for convert_to_utf8 until
458 // an actual new Symbol* is created.
459 Symbol* SymbolTable::new_symbol(const jchar* name, int utf16_length) {
460   size_t utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
461   char stack_buf[ON_STACK_BUFFER_LENGTH];
462   if (utf8_length < sizeof(stack_buf)) {
463     char* chars = stack_buf;
464     UNICODE::convert_to_utf8(name, utf16_length, chars);
465     return new_symbol(chars, checked_cast<int>(utf8_length));
466   } else {
467     ResourceMark rm;
468     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
469     UNICODE::convert_to_utf8(name, utf16_length, chars);
470     return new_symbol(chars, checked_cast<int>(utf8_length));
471   }
472 }
473 
474 Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,
475                                          unsigned int& hash) {
476   size_t utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
477   char stack_buf[ON_STACK_BUFFER_LENGTH];
478   if (utf8_length < sizeof(stack_buf)) {
479     char* chars = stack_buf;
480     UNICODE::convert_to_utf8(name, utf16_length, chars);
481     return lookup_only(chars, checked_cast<int>(utf8_length), hash);
482   } else {
483     ResourceMark rm;
484     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
485     UNICODE::convert_to_utf8(name, utf16_length, chars);
486     return lookup_only(chars, checked_cast<int>(utf8_length), hash);
487   }
488 }
489 
490 void SymbolTable::new_symbols(ClassLoaderData* loader_data, const constantPoolHandle& cp,
491                               int names_count, const char** names, int* lengths,
492                               int* cp_indices, unsigned int* hashValues) {
493   // Note that is_permanent will be false for non-strong hidden classes.
494   // even if their loader is the boot loader because they will have a different cld.
495   bool is_permanent = loader_data->is_the_null_class_loader_data();
496   for (int i = 0; i < names_count; i++) {
497     const char *name = names[i];
498     int len = lengths[i];
499     assert(len <= Symbol::max_length(), "must be - these come from the constant pool");
500     unsigned int hash = hashValues[i];
501     assert(lookup_shared(name, len, hash) == nullptr, "must have checked already");
502     Symbol* sym = do_add_if_needed(name, len, hash, is_permanent);
503     assert(sym->refcount() != 0, "lookup should have incremented the count");
504     cp->symbol_at_put(cp_indices[i], sym);
505   }
506 }
507 
508 Symbol* SymbolTable::do_add_if_needed(const char* name, int len, uintx hash, bool is_permanent) {
509   assert(len <= Symbol::max_length(), "caller should have ensured this");
510   SymbolTableLookup lookup(name, len, hash);
511   SymbolTableGet stg;
512   bool clean_hint = false;
513   bool rehash_warning = false;
514   Thread* current = Thread::current();
515   Symbol* sym;
516 
517   ResourceMark rm(current);
518   const int alloc_size = Symbol::byte_size(len);
519   u1* u1_buf = NEW_RESOURCE_ARRAY_IN_THREAD(current, u1, alloc_size);
520   Symbol* tmp = ::new ((void*)u1_buf) Symbol((const u1*)name, len,
521                                              (is_permanent || CDSConfig::is_dumping_static_archive()) ? PERM_REFCOUNT : 1);
522 
523   do {
524     if (_local_table->insert(current, lookup, *tmp, &rehash_warning, &clean_hint)) {
525       if (_local_table->get(current, lookup, stg, &rehash_warning)) {
526         sym = stg.get_res_sym();
527         // The get adds one to ref count, but we inserted with our ref already included.
528         // Therefore decrement with one.
529         if (sym->refcount() != PERM_REFCOUNT) {
530           sym->decrement_refcount();
531         }
532         break;
533       }
534     }
535 
536     // In case another thread did a concurrent add, return value already in the table.
537     // This could fail if the symbol got deleted concurrently, so loop back until success.
538     if (_local_table->get(current, lookup, stg, &rehash_warning)) {
539       // The lookup added a refcount, which is ours.
540       sym = stg.get_res_sym();
541       break;
542     }
543   } while(true);
544 
545   update_needs_rehash(rehash_warning);
546 
547   if (clean_hint) {
548     mark_has_items_to_clean();
549     check_concurrent_work();
550   }
551 
552   assert((sym == nullptr) || sym->refcount() != 0, "found dead symbol");
553   return sym;
554 }
555 
556 Symbol* SymbolTable::new_permanent_symbol(const char* name) {
557   unsigned int hash = 0;
558   int len = check_length(name, (int)strlen(name));
559   Symbol* sym = SymbolTable::lookup_only(name, len, hash);
560   if (sym == nullptr) {
561     sym = do_add_if_needed(name, len, hash, /* is_permanent */ true);
562   }
563   if (!sym->is_permanent()) {
564     sym->make_permanent();
565     log_trace_symboltable_helper(sym, "Asked for a permanent symbol, but got a regular one");
566   }
567   return sym;
568 }
569 
570 struct SizeFunc : StackObj {
571   size_t operator()(Symbol* value) {
572     assert(value != nullptr, "expected valid value");
573     return (value)->size() * HeapWordSize;
574   };
575 };
576 
577 TableStatistics SymbolTable::get_table_statistics() {
578   static TableStatistics ts;
579   SizeFunc sz;
580   ts = _local_table->statistics_get(Thread::current(), sz, ts);
581   return ts;
582 }
583 
584 void SymbolTable::print_table_statistics(outputStream* st) {
585   SizeFunc sz;
586   _local_table->statistics_to(Thread::current(), sz, st, "SymbolTable");
587 
588   if (!_shared_table.empty()) {
589     _shared_table.print_table_statistics(st, "Shared Symbol Table");
590   }
591 
592   if (!_dynamic_shared_table.empty()) {
593     _dynamic_shared_table.print_table_statistics(st, "Dynamic Shared Symbol Table");
594   }
595 }
596 
597 // Verification
598 class VerifySymbols : StackObj {
599 public:
600   bool operator()(Symbol* value) {
601     guarantee(value != nullptr, "expected valid value");
602     Symbol* sym = value;
603     guarantee(sym->equals((const char*)sym->bytes(), sym->utf8_length()),
604               "symbol must be internally consistent");
605     return true;
606   };
607 };
608 
609 void SymbolTable::verify() {
610   Thread* thr = Thread::current();
611   VerifySymbols vs;
612   if (!_local_table->try_scan(thr, vs)) {
613     log_info(symboltable)("verify unavailable at this moment");
614   }
615 }
616 
617 static void print_symbol(outputStream* st, Symbol* sym) {
618   const char* utf8_string = (const char*)sym->bytes();
619   int utf8_length = sym->utf8_length();
620   st->print("%d %d: ", utf8_length, sym->refcount());
621   HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
622   st->cr();
623 }
624 
625 // Dumping
626 class DumpSymbol : StackObj {
627   Thread* _thr;
628   outputStream* _st;
629 public:
630   DumpSymbol(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
631   bool operator()(Symbol* value) {
632     assert(value != nullptr, "expected valid value");
633     print_symbol(_st, value);
634     return true;
635   };
636 };
637 
638 class DumpSharedSymbol : StackObj {
639   outputStream* _st;
640 public:
641   DumpSharedSymbol(outputStream* st) : _st(st) {}
642   void do_value(Symbol* value) {
643     assert(value != nullptr, "value should point to a symbol");
644     print_symbol(_st, value);
645   };
646 };
647 
648 void SymbolTable::dump(outputStream* st, bool verbose) {
649   if (!verbose) {
650     print_table_statistics(st);
651   } else {
652     Thread* thr = Thread::current();
653     ResourceMark rm(thr);
654     st->print_cr("VERSION: 1.1");
655     DumpSymbol ds(thr, st);
656     if (!_local_table->try_scan(thr, ds)) {
657       log_info(symboltable)("dump unavailable at this moment");
658     }
659     if (!_shared_table.empty()) {
660       st->print_cr("#----------------");
661       st->print_cr("# Shared symbols:");
662       st->print_cr("#----------------");
663       DumpSharedSymbol dss(st);
664       _shared_table.iterate(&dss);
665     }
666     if (!_dynamic_shared_table.empty()) {
667       st->print_cr("#------------------------");
668       st->print_cr("# Dynamic shared symbols:");
669       st->print_cr("#------------------------");
670       DumpSharedSymbol dss(st);
671       _dynamic_shared_table.iterate(&dss);
672     }
673   }
674 }
675 
676 #if INCLUDE_CDS
677 void SymbolTable::copy_shared_symbol_table(GrowableArray<Symbol*>* symbols,
678                                            CompactHashtableWriter* writer) {
679   ArchiveBuilder* builder = ArchiveBuilder::current();
680   int len = symbols->length();
681   for (int i = 0; i < len; i++) {
682     Symbol* sym = ArchiveBuilder::get_buffered_symbol(symbols->at(i));
683     unsigned int fixed_hash = hash_shared_symbol((const char*)sym->bytes(), sym->utf8_length());
684     assert(fixed_hash == hash_symbol((const char*)sym->bytes(), sym->utf8_length(), false),
685            "must not rehash during dumping");
686     sym->set_permanent();
687     writer->add(fixed_hash, builder->buffer_to_offset_u4((address)sym));
688   }
689 }
690 
691 size_t SymbolTable::estimate_size_for_archive() {
692   if (_items_count > (size_t)max_jint) {
693     fatal("Too many symbols to be archived: %zu", _items_count);
694   }
695   return CompactHashtableWriter::estimate_size(int(_items_count));
696 }
697 
698 void SymbolTable::write_to_archive(GrowableArray<Symbol*>* symbols) {
699   CompactHashtableWriter writer(int(_items_count), ArchiveBuilder::symbol_stats());
700   copy_shared_symbol_table(symbols, &writer);
701   _shared_table_for_dumping.reset();
702   writer.dump(&_shared_table_for_dumping, "symbol");






703 }
704 
705 void SymbolTable::serialize_shared_table_header(SerializeClosure* soc,
706                                                 bool is_static_archive) {
707   OffsetCompactHashtable<const char*, Symbol*, symbol_equals_compact_hashtable_entry> * table;
708   if (soc->reading()) {
709     if (is_static_archive) {
710       table = &_shared_table;
711     } else {
712       table = &_dynamic_shared_table;
713     }
714   } else {
715     table = &_shared_table_for_dumping;
716   }
717 
718   table->serialize_header(soc);




719 }
720 #endif //INCLUDE_CDS
721 
722 // Concurrent work
723 void SymbolTable::grow(JavaThread* jt) {
724   SymbolTableHash::GrowTask gt(_local_table);
725   if (!gt.prepare(jt)) {
726     return;
727   }
728   log_trace(symboltable)("Started to grow");
729   {
730     TraceTime timer("Grow", TRACETIME_LOG(Debug, symboltable, perf));
731     while (gt.do_task(jt)) {
732       gt.pause(jt);
733       {
734         ThreadBlockInVM tbivm(jt);
735       }
736       gt.cont(jt);
737     }
738   }
739   gt.done(jt);
740   _current_size = table_size();
741   log_debug(symboltable)("Grown to size:%zu", _current_size);
742 }
743 
744 struct SymbolTableDoDelete : StackObj {
745   size_t _deleted;
746   SymbolTableDoDelete() : _deleted(0) {}
747   void operator()(Symbol* value) {
748     assert(value != nullptr, "expected valid value");
749     Symbol *sym = value;
750     assert(sym->refcount() == 0, "refcount");
751     _deleted++;
752   }
753 };
754 
755 struct SymbolTableDeleteCheck : StackObj {
756   size_t _processed;
757   SymbolTableDeleteCheck() : _processed(0) {}
758   bool operator()(Symbol* value) {
759     assert(value != nullptr, "expected valid value");
760     _processed++;
761     Symbol *sym = value;
762     return (sym->refcount() == 0);
763   }
764 };
765 
766 void SymbolTable::clean_dead_entries(JavaThread* jt) {
767   SymbolTableHash::BulkDeleteTask bdt(_local_table);
768   if (!bdt.prepare(jt)) {
769     return;
770   }
771 
772   SymbolTableDeleteCheck stdc;
773   SymbolTableDoDelete stdd;
774   NativeHeapTrimmer::SuspendMark sm("symboltable");
775   {
776     TraceTime timer("Clean", TRACETIME_LOG(Debug, symboltable, perf));
777     while (bdt.do_task(jt, stdc, stdd)) {
778       bdt.pause(jt);
779       {
780         ThreadBlockInVM tbivm(jt);
781       }
782       bdt.cont(jt);
783     }
784     reset_has_items_to_clean();
785     bdt.done(jt);
786   }
787 
788   Atomic::add(&_symbols_counted, stdc._processed);
789 
790   log_debug(symboltable)("Cleaned %zu of %zu",
791                          stdd._deleted, stdc._processed);
792 }
793 
794 void SymbolTable::check_concurrent_work() {
795   if (has_work()) {
796     return;
797   }
798   // We should clean/resize if we have
799   // more items than preferred load factor or
800   // more dead items than water mark.
801   if (has_items_to_clean() || (get_load_factor() > PREF_AVG_LIST_LEN)) {
802     log_debug(symboltable)("Concurrent work triggered, load factor: %f, items to clean: %s",
803                            get_load_factor(), has_items_to_clean() ? "true" : "false");
804     trigger_cleanup();
805   }
806 }
807 
808 bool SymbolTable::should_grow() {
809   return get_load_factor() > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached();
810 }
811 
812 void SymbolTable::do_concurrent_work(JavaThread* jt) {
813   // Rehash if needed.  Rehashing goes to a safepoint but the rest of this
814   // work is concurrent.
815   if (needs_rehashing() && maybe_rehash_table()) {
816     Atomic::release_store(&_has_work, false);
817     return; // done, else grow
818   }
819   log_debug(symboltable, perf)("Concurrent work, live factor: %g", get_load_factor());
820   // We prefer growing, since that also removes dead items
821   if (should_grow()) {
822     grow(jt);
823   } else {
824     clean_dead_entries(jt);
825   }
826   Atomic::release_store(&_has_work, false);
827 }
828 
829 // Called at VM_Operation safepoint
830 void SymbolTable::rehash_table() {
831   assert(SafepointSynchronize::is_at_safepoint(), "must be called at safepoint");
832   // The ServiceThread initiates the rehashing so it is not resizing.
833   assert (_local_table->is_safepoint_safe(), "Should not be resizing now");
834 
835   _alt_hash_seed = AltHashing::compute_seed();
836 
837   // We use current size
838   size_t new_size = _local_table->get_size_log2(Thread::current());
839   SymbolTableHash* new_table = new SymbolTableHash(new_size, END_SIZE, REHASH_LEN, true);
840   // Use alt hash from now on
841   _alt_hash = true;
842   _local_table->rehash_nodes_to(Thread::current(), new_table);
843 
844   // free old table
845   delete _local_table;
846   _local_table = new_table;
847 
848   _rehashed = true;
849   _needs_rehashing = false;
850 }
851 
852 bool SymbolTable::maybe_rehash_table() {
853   log_debug(symboltable)("Table imbalanced, rehashing called.");
854 
855   // Grow instead of rehash.
856   if (should_grow()) {
857     log_debug(symboltable)("Choosing growing over rehashing.");
858     _needs_rehashing = false;
859     return false;
860   }
861 
862   // Already rehashed.
863   if (_rehashed) {
864     log_warning(symboltable)("Rehashing already done, still long lists.");
865     _needs_rehashing = false;
866     return false;
867   }
868 
869   VM_RehashSymbolTable op;
870   VMThread::execute(&op);
871   return true;
872 }
873 
874 //---------------------------------------------------------------------------
875 // Non-product code
876 
877 #ifndef PRODUCT
878 
879 class HistogramIterator : StackObj {
880 public:
881   static const size_t results_length = 100;
882   size_t counts[results_length];
883   size_t sizes[results_length];
884   size_t total_size;
885   size_t total_count;
886   size_t total_length;
887   size_t max_length;
888   size_t out_of_range_count;
889   size_t out_of_range_size;
890   HistogramIterator() : total_size(0), total_count(0), total_length(0),
891                         max_length(0), out_of_range_count(0), out_of_range_size(0) {
892     // initialize results to zero
893     for (size_t i = 0; i < results_length; i++) {
894       counts[i] = 0;
895       sizes[i] = 0;
896     }
897   }
898   bool operator()(Symbol* value) {
899     assert(value != nullptr, "expected valid value");
900     Symbol* sym = value;
901     size_t size = sym->size();
902     size_t len = sym->utf8_length();
903     if (len < results_length) {
904       counts[len]++;
905       sizes[len] += size;
906     } else {
907       out_of_range_count++;
908       out_of_range_size += size;
909     }
910     total_count++;
911     total_size += size;
912     total_length += len;
913     max_length = MAX2(max_length, len);
914 
915     return true;
916   };
917 };
918 
919 void SymbolTable::print_histogram() {
920   HistogramIterator hi;
921   _local_table->do_scan(Thread::current(), hi);
922   tty->print_cr("Symbol Table Histogram:");
923   tty->print_cr("  Total number of symbols  %7zu", hi.total_count);
924   tty->print_cr("  Total size in memory     %7zuK", (hi.total_size * wordSize) / K);
925   tty->print_cr("  Total counted            %7zu", _symbols_counted);
926   tty->print_cr("  Total removed            %7zu", _symbols_removed);
927   if (_symbols_counted > 0) {
928     tty->print_cr("  Percent removed          %3.2f",
929           ((double)_symbols_removed / (double)_symbols_counted) * 100);
930   }
931   tty->print_cr("  Reference counts         %7zu", Symbol::_total_count);
932   tty->print_cr("  Symbol arena used        %7zuK", arena()->used() / K);
933   tty->print_cr("  Symbol arena size        %7zuK", arena()->size_in_bytes() / K);
934   tty->print_cr("  Total symbol length      %7zu", hi.total_length);
935   tty->print_cr("  Maximum symbol length    %7zu", hi.max_length);
936   tty->print_cr("  Average symbol length    %7.2f", ((double)hi.total_length / (double)hi.total_count));
937   tty->print_cr("  Symbol length histogram:");
938   tty->print_cr("    %6s %10s %10s", "Length", "#Symbols", "Size");
939   for (size_t i = 0; i < hi.results_length; i++) {
940     if (hi.counts[i] > 0) {
941       tty->print_cr("    %6zu %10zu %10zuK",
942                     i, hi.counts[i], (hi.sizes[i] * wordSize) / K);
943     }
944   }
945   tty->print_cr("  >= %6zu %10zu %10zuK\n",
946                 hi.results_length, hi.out_of_range_count, (hi.out_of_range_size*wordSize) / K);
947 }
948 #endif // PRODUCT
949 
950 // Utility for dumping symbols
951 SymboltableDCmd::SymboltableDCmd(outputStream* output, bool heap) :
952                                  DCmdWithParser(output, heap),
953   _verbose("-verbose", "Dump the content of each symbol in the table",
954            "BOOLEAN", false, "false") {
955   _dcmdparser.add_dcmd_option(&_verbose);
956 }
957 
958 void SymboltableDCmd::execute(DCmdSource source, TRAPS) {
959   VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpSymbols,
960                          _verbose.value());
961   VMThread::execute(&dumper);
962 }
--- EOF ---