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