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