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