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, _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 = SymbolTableHash::get_dynamic_node_size(value.byte_size());
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 = 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 = 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 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 <= Symbol::max_length(),
348 "String length %d exceeds the maximum Symbol length of %d", len, Symbol::max_length());
349 if (len > Symbol::max_length()) {
350 warning("A string \"%.80s ... %.80s\" exceeds the maximum Symbol "
351 "length of %d and has been truncated", name, (name + len - 80), Symbol::max_length());
352 len = Symbol::max_length();
353 }
354 return len;
355 }
356
357 Symbol* SymbolTable::new_symbol(const char* name, int len) {
358 len = check_length(name, len);
359 unsigned int hash = hash_symbol(name, len, _alt_hash);
360 Symbol* sym = lookup_common(name, len, hash);
361 if (sym == nullptr) {
362 sym = do_add_if_needed(name, len, hash, /* is_permanent */ false);
363 }
364 assert(sym->refcount() != 0, "lookup should have incremented the count");
365 assert(sym->equals(name, len), "symbol must be properly initialized");
366 return sym;
367 }
368
369 Symbol* SymbolTable::new_symbol(const Symbol* sym, int begin, int end) {
370 assert(begin <= end && end <= sym->utf8_length(), "just checking");
371 assert(sym->refcount() != 0, "require a valid symbol");
372 const char* name = (const char*)sym->base() + begin;
373 int len = end - begin;
374 assert(len <= Symbol::max_length(), "sanity");
375 unsigned int hash = hash_symbol(name, len, _alt_hash);
376 Symbol* found = lookup_common(name, len, hash);
377 if (found == nullptr) {
378 found = do_add_if_needed(name, len, hash, /* is_permanent */ false);
379 }
380 return found;
381 }
382
383 class SymbolTableLookup : StackObj {
384 private:
385 uintx _hash;
386 int _len;
387 const char* _str;
388 public:
389 SymbolTableLookup(const char* key, int len, uintx hash)
390 : _hash(hash), _len(len), _str(key) {}
391 uintx get_hash() const {
392 return _hash;
393 }
394 // Note: When equals() returns "true", the symbol's refcount is incremented. This is
395 // needed to ensure that the symbol is kept alive before equals() returns to the caller,
396 // so that another thread cannot clean the symbol up concurrently. The caller is
397 // responsible for decrementing the refcount, when the symbol is no longer needed.
398 bool equals(Symbol* value) {
399 assert(value != nullptr, "expected valid value");
400 Symbol *sym = value;
401 if (sym->equals(_str, _len)) {
402 if (sym->try_increment_refcount()) {
403 // something is referencing this symbol now.
404 return true;
405 } else {
406 assert(sym->refcount() == 0, "expected dead symbol");
407 return false;
408 }
409 } else {
410 return false;
411 }
412 }
413 bool is_dead(Symbol* value) {
414 return value->refcount() == 0;
415 }
416 };
417
418 class SymbolTableGet : public StackObj {
419 Symbol* _return;
420 public:
421 SymbolTableGet() : _return(nullptr) {}
422 void operator()(Symbol* value) {
423 assert(value != nullptr, "expected valid value");
424 _return = value;
425 }
426 Symbol* get_res_sym() const {
427 return _return;
428 }
429 };
430
431 void SymbolTable::update_needs_rehash(bool rehash) {
432 if (rehash) {
433 _needs_rehashing = true;
434 trigger_cleanup();
435 }
436 }
437
438 Symbol* SymbolTable::do_lookup(const char* name, int len, uintx hash) {
439 Thread* thread = Thread::current();
440 SymbolTableLookup lookup(name, len, hash);
441 SymbolTableGet stg;
442 bool rehash_warning = false;
443 _local_table->get(thread, lookup, stg, &rehash_warning);
444 update_needs_rehash(rehash_warning);
445 Symbol* sym = stg.get_res_sym();
446 assert((sym == nullptr) || sym->refcount() != 0, "found dead symbol");
447 return sym;
448 }
449
450 Symbol* SymbolTable::lookup_only(const char* name, int len, unsigned int& hash) {
451 hash = hash_symbol(name, len, _alt_hash);
452 return lookup_common(name, len, hash);
453 }
454
455 // Suggestion: Push unicode-based lookup all the way into the hashing
456 // and probing logic, so there is no need for convert_to_utf8 until
457 // an actual new Symbol* is created.
458 Symbol* SymbolTable::new_symbol(const jchar* name, int utf16_length) {
459 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
460 char stack_buf[ON_STACK_BUFFER_LENGTH];
461 if (utf8_length < (int) sizeof(stack_buf)) {
462 char* chars = stack_buf;
463 UNICODE::convert_to_utf8(name, utf16_length, chars);
464 return new_symbol(chars, utf8_length);
465 } else {
466 ResourceMark rm;
467 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
468 UNICODE::convert_to_utf8(name, utf16_length, chars);
469 return new_symbol(chars, utf8_length);
470 }
471 }
472
473 Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,
474 unsigned int& hash) {
475 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
476 char stack_buf[ON_STACK_BUFFER_LENGTH];
477 if (utf8_length < (int) sizeof(stack_buf)) {
478 char* chars = stack_buf;
479 UNICODE::convert_to_utf8(name, utf16_length, chars);
480 return lookup_only(chars, utf8_length, hash);
481 } else {
482 ResourceMark rm;
483 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
484 UNICODE::convert_to_utf8(name, utf16_length, chars);
485 return lookup_only(chars, utf8_length, hash);
486 }
487 }
488
489 void SymbolTable::new_symbols(ClassLoaderData* loader_data, const constantPoolHandle& cp,
490 int names_count, const char** names, int* lengths,
491 int* cp_indices, unsigned int* hashValues) {
492 // Note that is_permanent will be false for non-strong hidden classes.
493 // even if their loader is the boot loader because they will have a different cld.
494 bool is_permanent = loader_data->is_the_null_class_loader_data();
495 for (int i = 0; i < names_count; i++) {
496 const char *name = names[i];
497 int len = lengths[i];
498 assert(len <= Symbol::max_length(), "must be - these come from the constant pool");
499 unsigned int hash = hashValues[i];
500 assert(lookup_shared(name, len, hash) == nullptr, "must have checked already");
501 Symbol* sym = do_add_if_needed(name, len, hash, is_permanent);
502 assert(sym->refcount() != 0, "lookup should have incremented the count");
503 cp->symbol_at_put(cp_indices[i], sym);
504 }
505 }
506
507 Symbol* SymbolTable::do_add_if_needed(const char* name, int len, uintx hash, bool is_permanent) {
508 assert(len <= Symbol::max_length(), "caller should have ensured this");
509 SymbolTableLookup lookup(name, len, hash);
510 SymbolTableGet stg;
511 bool clean_hint = false;
512 bool rehash_warning = false;
513 Thread* current = Thread::current();
514 Symbol* sym;
515
516 ResourceMark rm(current);
517 const int alloc_size = Symbol::byte_size(len);
518 u1* u1_buf = NEW_RESOURCE_ARRAY_IN_THREAD(current, u1, alloc_size);
519 Symbol* tmp = ::new ((void*)u1_buf) Symbol((const u1*)name, len,
520 (is_permanent || CDSConfig::is_dumping_static_archive()) ? PERM_REFCOUNT : 1);
521
522 do {
523 if (_local_table->insert(current, lookup, *tmp, &rehash_warning, &clean_hint)) {
524 if (_local_table->get(current, lookup, stg, &rehash_warning)) {
525 sym = stg.get_res_sym();
526 // The get adds one to ref count, but we inserted with our ref already included.
527 // Therefore decrement with one.
528 if (sym->refcount() != PERM_REFCOUNT) {
529 sym->decrement_refcount();
530 }
531 break;
532 }
533 }
534
535 // In case another thread did a concurrent add, return value already in the table.
536 // This could fail if the symbol got deleted concurrently, so loop back until success.
537 if (_local_table->get(current, lookup, stg, &rehash_warning)) {
538 // The lookup added a refcount, which is ours.
539 sym = stg.get_res_sym();
540 break;
541 }
542 } while(true);
543
544 update_needs_rehash(rehash_warning);
545
546 if (clean_hint) {
547 mark_has_items_to_clean();
548 check_concurrent_work();
549 }
550
551 assert((sym == nullptr) || sym->refcount() != 0, "found dead symbol");
552 return sym;
553 }
554
555 Symbol* SymbolTable::new_permanent_symbol(const char* name) {
556 unsigned int hash = 0;
557 int len = check_length(name, (int)strlen(name));
558 Symbol* sym = SymbolTable::lookup_only(name, len, hash);
559 if (sym == nullptr) {
560 sym = do_add_if_needed(name, len, hash, /* is_permanent */ true);
561 }
562 if (!sym->is_permanent()) {
563 sym->make_permanent();
564 log_trace_symboltable_helper(sym, "Asked for a permanent symbol, but got a regular one");
565 }
566 return sym;
567 }
568
569 struct SizeFunc : StackObj {
570 size_t operator()(Symbol* value) {
571 assert(value != nullptr, "expected valid value");
572 return (value)->size() * HeapWordSize;
573 };
574 };
575
576 TableStatistics SymbolTable::get_table_statistics() {
577 static TableStatistics ts;
578 SizeFunc sz;
579 ts = _local_table->statistics_get(Thread::current(), sz, ts);
580 return ts;
581 }
582
583 void SymbolTable::print_table_statistics(outputStream* st) {
584 SizeFunc sz;
585 _local_table->statistics_to(Thread::current(), sz, st, "SymbolTable");
586
587 if (!_shared_table.empty()) {
588 _shared_table.print_table_statistics(st, "Shared Symbol Table");
589 }
590
591 if (!_dynamic_shared_table.empty()) {
592 _dynamic_shared_table.print_table_statistics(st, "Dynamic Shared Symbol Table");
593 }
594 }
595
596 // Verification
597 class VerifySymbols : StackObj {
598 public:
599 bool operator()(Symbol* value) {
600 guarantee(value != nullptr, "expected valid value");
601 Symbol* sym = value;
602 guarantee(sym->equals((const char*)sym->bytes(), sym->utf8_length()),
603 "symbol must be internally consistent");
604 return true;
605 };
606 };
607
608 void SymbolTable::verify() {
609 Thread* thr = Thread::current();
610 VerifySymbols vs;
611 if (!_local_table->try_scan(thr, vs)) {
612 log_info(symboltable)("verify unavailable at this moment");
613 }
614 }
615
616 static void print_symbol(outputStream* st, Symbol* sym) {
617 const char* utf8_string = (const char*)sym->bytes();
618 int utf8_length = sym->utf8_length();
619 st->print("%d %d: ", utf8_length, sym->refcount());
620 HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
621 st->cr();
622 }
623
624 // Dumping
625 class DumpSymbol : StackObj {
626 Thread* _thr;
627 outputStream* _st;
628 public:
629 DumpSymbol(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
630 bool operator()(Symbol* value) {
631 assert(value != nullptr, "expected valid value");
632 print_symbol(_st, value);
633 return true;
634 };
635 };
636
637 class DumpSharedSymbol : StackObj {
638 outputStream* _st;
639 public:
640 DumpSharedSymbol(outputStream* st) : _st(st) {}
641 void do_value(Symbol* value) {
642 assert(value != nullptr, "value should point to a symbol");
643 print_symbol(_st, value);
644 };
645 };
646
647 void SymbolTable::dump(outputStream* st, bool verbose) {
648 if (!verbose) {
649 print_table_statistics(st);
650 } else {
651 Thread* thr = Thread::current();
652 ResourceMark rm(thr);
653 st->print_cr("VERSION: 1.1");
654 DumpSymbol ds(thr, st);
655 if (!_local_table->try_scan(thr, ds)) {
656 log_info(symboltable)("dump unavailable at this moment");
657 }
658 if (!_shared_table.empty()) {
659 st->print_cr("#----------------");
660 st->print_cr("# Shared symbols:");
661 st->print_cr("#----------------");
662 DumpSharedSymbol dss(st);
663 _shared_table.iterate(&dss);
664 }
665 if (!_dynamic_shared_table.empty()) {
666 st->print_cr("#------------------------");
667 st->print_cr("# Dynamic shared symbols:");
668 st->print_cr("#------------------------");
669 DumpSharedSymbol dss(st);
670 _dynamic_shared_table.iterate(&dss);
671 }
672 }
673 }
674
675 #if INCLUDE_CDS
676 void SymbolTable::copy_shared_symbol_table(GrowableArray<Symbol*>* symbols,
677 CompactHashtableWriter* writer) {
678 ArchiveBuilder* builder = ArchiveBuilder::current();
679 int len = symbols->length();
680 for (int i = 0; i < len; i++) {
681 Symbol* sym = ArchiveBuilder::get_buffered_symbol(symbols->at(i));
682 unsigned int fixed_hash = hash_shared_symbol((const char*)sym->bytes(), sym->utf8_length());
683 assert(fixed_hash == hash_symbol((const char*)sym->bytes(), sym->utf8_length(), false),
684 "must not rehash during dumping");
685 sym->set_permanent();
686 writer->add(fixed_hash, builder->buffer_to_offset_u4((address)sym));
687 }
688 }
689
690 size_t SymbolTable::estimate_size_for_archive() {
691 if (_items_count > (size_t)max_jint) {
692 fatal("Too many symbols to be archived: %zu", _items_count);
693 }
694 return CompactHashtableWriter::estimate_size(int(_items_count));
695 }
696
697 void SymbolTable::write_to_archive(GrowableArray<Symbol*>* symbols) {
698 CompactHashtableWriter writer(int(_items_count), ArchiveBuilder::symbol_stats());
699 copy_shared_symbol_table(symbols, &writer);
700 _shared_table_for_dumping.reset();
701 writer.dump(&_shared_table_for_dumping, "symbol");
702 }
703
704 void SymbolTable::serialize_shared_table_header(SerializeClosure* soc,
705 bool is_static_archive) {
706 OffsetCompactHashtable<const char*, Symbol*, symbol_equals_compact_hashtable_entry> * table;
707 if (soc->reading()) {
708 if (is_static_archive) {
709 table = &_shared_table;
710 } else {
711 table = &_dynamic_shared_table;
712 }
713 } else {
714 table = &_shared_table_for_dumping;
715 }
716
717 table->serialize_header(soc);
718 }
719 #endif //INCLUDE_CDS
720
721 // Concurrent work
722 void SymbolTable::grow(JavaThread* jt) {
723 SymbolTableHash::GrowTask gt(_local_table);
724 if (!gt.prepare(jt)) {
725 return;
726 }
727 log_trace(symboltable)("Started to grow");
728 {
729 TraceTime timer("Grow", TRACETIME_LOG(Debug, symboltable, perf));
730 while (gt.do_task(jt)) {
731 gt.pause(jt);
732 {
733 ThreadBlockInVM tbivm(jt);
734 }
735 gt.cont(jt);
736 }
737 }
738 gt.done(jt);
739 _current_size = table_size();
740 log_debug(symboltable)("Grown to size:" SIZE_FORMAT, _current_size);
741 }
742
743 struct SymbolTableDoDelete : StackObj {
744 size_t _deleted;
745 SymbolTableDoDelete() : _deleted(0) {}
746 void operator()(Symbol* value) {
747 assert(value != nullptr, "expected valid value");
748 Symbol *sym = value;
749 assert(sym->refcount() == 0, "refcount");
750 _deleted++;
751 }
752 };
753
754 struct SymbolTableDeleteCheck : StackObj {
755 size_t _processed;
756 SymbolTableDeleteCheck() : _processed(0) {}
757 bool operator()(Symbol* value) {
758 assert(value != nullptr, "expected valid value");
759 _processed++;
760 Symbol *sym = value;
761 return (sym->refcount() == 0);
762 }
763 };
764
765 void SymbolTable::clean_dead_entries(JavaThread* jt) {
766 SymbolTableHash::BulkDeleteTask bdt(_local_table);
767 if (!bdt.prepare(jt)) {
768 return;
769 }
770
771 SymbolTableDeleteCheck stdc;
772 SymbolTableDoDelete stdd;
773 NativeHeapTrimmer::SuspendMark sm("symboltable");
774 {
775 TraceTime timer("Clean", TRACETIME_LOG(Debug, symboltable, perf));
776 while (bdt.do_task(jt, stdc, stdd)) {
777 bdt.pause(jt);
778 {
779 ThreadBlockInVM tbivm(jt);
780 }
781 bdt.cont(jt);
782 }
783 reset_has_items_to_clean();
784 bdt.done(jt);
785 }
786
787 Atomic::add(&_symbols_counted, stdc._processed);
788
789 log_debug(symboltable)("Cleaned " SIZE_FORMAT " of " SIZE_FORMAT,
790 stdd._deleted, stdc._processed);
791 }
792
793 void SymbolTable::check_concurrent_work() {
794 if (has_work()) {
795 return;
796 }
797 // We should clean/resize if we have
798 // more items than preferred load factor or
799 // more dead items than water mark.
800 if (has_items_to_clean() || (get_load_factor() > PREF_AVG_LIST_LEN)) {
801 log_debug(symboltable)("Concurrent work triggered, load factor: %f, items to clean: %s",
802 get_load_factor(), has_items_to_clean() ? "true" : "false");
803 trigger_cleanup();
804 }
805 }
806
807 bool SymbolTable::should_grow() {
808 return get_load_factor() > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached();
809 }
810
811 void SymbolTable::do_concurrent_work(JavaThread* jt) {
812 // Rehash if needed. Rehashing goes to a safepoint but the rest of this
813 // work is concurrent.
814 if (needs_rehashing() && maybe_rehash_table()) {
815 Atomic::release_store(&_has_work, false);
816 return; // done, else grow
817 }
818 log_debug(symboltable, perf)("Concurrent work, live factor: %g", get_load_factor());
819 // We prefer growing, since that also removes dead items
820 if (should_grow()) {
821 grow(jt);
822 } else {
823 clean_dead_entries(jt);
824 }
825 Atomic::release_store(&_has_work, false);
826 }
827
828 // Called at VM_Operation safepoint
829 void SymbolTable::rehash_table() {
830 assert(SafepointSynchronize::is_at_safepoint(), "must be called at safepoint");
831 // The ServiceThread initiates the rehashing so it is not resizing.
832 assert (_local_table->is_safepoint_safe(), "Should not be resizing now");
833
834 _alt_hash_seed = AltHashing::compute_seed();
835
836 // We use current size
837 size_t new_size = _local_table->get_size_log2(Thread::current());
838 SymbolTableHash* new_table = new SymbolTableHash(new_size, END_SIZE, REHASH_LEN, true);
839 // Use alt hash from now on
840 _alt_hash = true;
841 _local_table->rehash_nodes_to(Thread::current(), new_table);
842
843 // free old table
844 delete _local_table;
845 _local_table = new_table;
846
847 _rehashed = true;
848 _needs_rehashing = false;
849 }
850
851 bool SymbolTable::maybe_rehash_table() {
852 log_debug(symboltable)("Table imbalanced, rehashing called.");
853
854 // Grow instead of rehash.
855 if (should_grow()) {
856 log_debug(symboltable)("Choosing growing over rehashing.");
857 _needs_rehashing = false;
858 return false;
859 }
860
861 // Already rehashed.
862 if (_rehashed) {
863 log_warning(symboltable)("Rehashing already done, still long lists.");
864 _needs_rehashing = false;
865 return false;
866 }
867
868 VM_RehashSymbolTable op;
869 VMThread::execute(&op);
870 return true;
871 }
872
873 //---------------------------------------------------------------------------
874 // Non-product code
875
876 #ifndef PRODUCT
877
878 class HistogramIterator : StackObj {
879 public:
880 static const size_t results_length = 100;
881 size_t counts[results_length];
882 size_t sizes[results_length];
883 size_t total_size;
884 size_t total_count;
885 size_t total_length;
886 size_t max_length;
887 size_t out_of_range_count;
888 size_t out_of_range_size;
889 HistogramIterator() : total_size(0), total_count(0), total_length(0),
890 max_length(0), out_of_range_count(0), out_of_range_size(0) {
891 // initialize results to zero
892 for (size_t i = 0; i < results_length; i++) {
893 counts[i] = 0;
894 sizes[i] = 0;
895 }
896 }
897 bool operator()(Symbol* value) {
898 assert(value != nullptr, "expected valid value");
899 Symbol* sym = value;
900 size_t size = sym->size();
901 size_t len = sym->utf8_length();
902 if (len < results_length) {
903 counts[len]++;
904 sizes[len] += size;
905 } else {
906 out_of_range_count++;
907 out_of_range_size += size;
908 }
909 total_count++;
910 total_size += size;
911 total_length += len;
912 max_length = MAX2(max_length, len);
913
914 return true;
915 };
916 };
917
918 void SymbolTable::print_histogram() {
919 HistogramIterator hi;
920 _local_table->do_scan(Thread::current(), hi);
921 tty->print_cr("Symbol Table Histogram:");
922 tty->print_cr(" Total number of symbols " SIZE_FORMAT_W(7), hi.total_count);
923 tty->print_cr(" Total size in memory " SIZE_FORMAT_W(7) "K", (hi.total_size * wordSize) / K);
924 tty->print_cr(" Total counted " SIZE_FORMAT_W(7), _symbols_counted);
925 tty->print_cr(" Total removed " SIZE_FORMAT_W(7), _symbols_removed);
926 if (_symbols_counted > 0) {
927 tty->print_cr(" Percent removed %3.2f",
928 ((double)_symbols_removed / (double)_symbols_counted) * 100);
929 }
930 tty->print_cr(" Reference counts " SIZE_FORMAT_W(7), Symbol::_total_count);
931 tty->print_cr(" Symbol arena used " SIZE_FORMAT_W(7) "K", arena()->used() / K);
932 tty->print_cr(" Symbol arena size " SIZE_FORMAT_W(7) "K", arena()->size_in_bytes() / K);
933 tty->print_cr(" Total symbol length " SIZE_FORMAT_W(7), hi.total_length);
934 tty->print_cr(" Maximum symbol length " SIZE_FORMAT_W(7), hi.max_length);
935 tty->print_cr(" Average symbol length %7.2f", ((double)hi.total_length / (double)hi.total_count));
936 tty->print_cr(" Symbol length histogram:");
937 tty->print_cr(" %6s %10s %10s", "Length", "#Symbols", "Size");
938 for (size_t i = 0; i < hi.results_length; i++) {
939 if (hi.counts[i] > 0) {
940 tty->print_cr(" " SIZE_FORMAT_W(6) " " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) "K",
941 i, hi.counts[i], (hi.sizes[i] * wordSize) / K);
942 }
943 }
944 tty->print_cr(" >=" SIZE_FORMAT_W(6) " " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) "K\n",
945 hi.results_length, hi.out_of_range_count, (hi.out_of_range_size*wordSize) / K);
946 }
947 #endif // PRODUCT
948
949 // Utility for dumping symbols
950 SymboltableDCmd::SymboltableDCmd(outputStream* output, bool heap) :
951 DCmdWithParser(output, heap),
952 _verbose("-verbose", "Dump the content of each symbol in the table",
953 "BOOLEAN", false, "false") {
954 _dcmdparser.add_dcmd_option(&_verbose);
955 }
956
957 void SymboltableDCmd::execute(DCmdSource source, TRAPS) {
958 VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpSymbols,
959 _verbose.value());
960 VMThread::execute(&dumper);
961 }