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