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