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