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