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