jdk

1
/*
2
 * Copyright (c) 1997, 2024, 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 "cds/archiveBuilder.hpp"
27
#include "cds/cdsConfig.hpp"
28
#include "cds/dynamicArchive.hpp"
29
#include "classfile/altHashing.hpp"
30
#include "classfile/classLoaderData.hpp"
31
#include "classfile/compactHashtable.hpp"
32
#include "classfile/javaClasses.hpp"
33
#include "classfile/symbolTable.hpp"
34
#include "memory/allocation.inline.hpp"
35
#include "memory/metaspaceClosure.hpp"
36
#include "memory/resourceArea.hpp"
37
#include "oops/oop.inline.hpp"
38
#include "runtime/atomic.hpp"
39
#include "runtime/interfaceSupport.inline.hpp"
40
#include "runtime/timerTrace.hpp"
41
#include "runtime/trimNativeHeap.hpp"
42
#include "services/diagnosticCommand.hpp"
43
#include "utilities/concurrentHashTable.inline.hpp"
44
#include "utilities/concurrentHashTableTasks.inline.hpp"
45
#include "utilities/utf8.hpp"
46

47
// We used to not resize at all, so let's be conservative
48
// and not set it too short before we decide to resize,
49
// to match previous startup behavior
50
const double PREF_AVG_LIST_LEN = 8.0;
51
// 2^24 is max size, like StringTable.
52
const size_t END_SIZE = 24;
53
// If a chain gets to 100 something might be wrong
54
const size_t REHASH_LEN = 100;
55

56
const size_t ON_STACK_BUFFER_LENGTH = 128;
57

58
// --------------------------------------------------------------------------
59

60
inline bool symbol_equals_compact_hashtable_entry(Symbol* value, const char* key, int len) {
61
  if (value->equals(key, len)) {
62
    return true;
63
  } else {
64
    return false;
65
  }
66
}
67

68
static OffsetCompactHashtable<
69
  const char*, Symbol*,
70
  symbol_equals_compact_hashtable_entry
71
> _shared_table;
72

73
static OffsetCompactHashtable<
74
  const char*, Symbol*,
75
  symbol_equals_compact_hashtable_entry
76
> _dynamic_shared_table;
77

78
// --------------------------------------------------------------------------
79

80
typedef ConcurrentHashTable<SymbolTableConfig, mtSymbol> SymbolTableHash;
81
static SymbolTableHash* _local_table = nullptr;
82

83
volatile bool SymbolTable::_has_work = 0;
84
volatile bool SymbolTable::_needs_rehashing = false;
85

86
// For statistics
87
static size_t _symbols_removed = 0;
88
static size_t _symbols_counted = 0;
89
static size_t _current_size = 0;
90

91
static volatile size_t _items_count = 0;
92
static volatile bool   _has_items_to_clean = false;
93

94

95
static volatile bool _alt_hash = false;
96

97
#ifdef USE_LIBRARY_BASED_TLS_ONLY
98
static volatile bool _lookup_shared_first = false;
99
#else
100
// "_lookup_shared_first" can get highly contended with many cores if multiple threads
101
// are updating "lookup success history" in a global shared variable. If built-in TLS is available, use it.
102
static THREAD_LOCAL bool _lookup_shared_first = false;
103
#endif
104

105
// Static arena for symbols that are not deallocated
106
Arena* SymbolTable::_arena = nullptr;
107

108
static bool _rehashed = false;
109
static uint64_t _alt_hash_seed = 0;
110

111
static inline void log_trace_symboltable_helper(Symbol* sym, const char* msg) {
112
#ifndef PRODUCT
113
  ResourceMark rm;
114
  log_trace(symboltable)("%s [%s]", msg, sym->as_quoted_ascii());
115
#endif // PRODUCT
116
}
117

118
// Pick hashing algorithm.
119
static unsigned int hash_symbol(const char* s, int len, bool useAlt) {
120
  return useAlt ?
121
  AltHashing::halfsiphash_32(_alt_hash_seed, (const uint8_t*)s, len) :
122
  java_lang_String::hash_code((const jbyte*)s, len);
123
}
124

125
#if INCLUDE_CDS
126
static unsigned int hash_shared_symbol(const char* s, int len) {
127
  return java_lang_String::hash_code((const jbyte*)s, len);
128
}
129
#endif
130

131
class SymbolTableConfig : public AllStatic {
132

133
public:
134
  typedef Symbol Value;  // value of the Node in the hashtable
135

136
  static uintx get_hash(Value const& value, bool* is_dead) {
137
    *is_dead = (value.refcount() == 0);
138
    if (*is_dead) {
139
      return 0;
140
    } else {
141
      return hash_symbol((const char*)value.bytes(), value.utf8_length(), _alt_hash);
142
    }
143
  }
144
  // We use default allocation/deallocation but counted
145
  static void* allocate_node(void* context, size_t size, Value const& value) {
146
    SymbolTable::item_added();
147
    return allocate_node_impl(size, value);
148
  }
149
  static void free_node(void* context, void* memory, Value & value) {
150
    // We get here because #1 some threads lost a race to insert a newly created Symbol
151
    // or #2 we're cleaning up unused symbol.
152
    // If #1, then the symbol can be either permanent,
153
    // or regular newly created one (refcount==1)
154
    // If #2, then the symbol is dead (refcount==0)
155
    assert(value.is_permanent() || (value.refcount() == 1) || (value.refcount() == 0),
156
           "refcount %d", value.refcount());
157
#if INCLUDE_CDS
158
    if (CDSConfig::is_dumping_static_archive()) {
159
      // We have allocated with MetaspaceShared::symbol_space_alloc(). No deallocation is needed.
160
      // Unreferenced Symbols will not be copied into the archive.
161
      return;
162
    }
163
#endif
164
    if (value.refcount() == 1) {
165
      value.decrement_refcount();
166
      assert(value.refcount() == 0, "expected dead symbol");
167
    }
168
    if (value.refcount() != PERM_REFCOUNT) {
169
      FreeHeap(memory);
170
    } else {
171
      MutexLocker ml(SymbolArena_lock, Mutex::_no_safepoint_check_flag); // Protect arena
172
      // Deleting permanent symbol should not occur very often (insert race condition),
173
      // so log it.
174
      log_trace_symboltable_helper(&value, "Freeing permanent symbol");
175
      size_t alloc_size = SymbolTableHash::get_dynamic_node_size(value.byte_size());
176
      if (!SymbolTable::arena()->Afree(memory, alloc_size)) {
177
        log_trace_symboltable_helper(&value, "Leaked permanent symbol");
178
      }
179
    }
180
    SymbolTable::item_removed();
181
  }
182

183
private:
184
  static void* allocate_node_impl(size_t size, Value const& value) {
185
    size_t alloc_size = SymbolTableHash::get_dynamic_node_size(value.byte_size());
186
#if INCLUDE_CDS
187
    if (CDSConfig::is_dumping_static_archive()) {
188
      MutexLocker ml(DumpRegion_lock, Mutex::_no_safepoint_check_flag);
189
      // To get deterministic output from -Xshare:dump, we ensure that Symbols are allocated in
190
      // increasing addresses. When the symbols are copied into the archive, we preserve their
191
      // relative address order (sorted, see ArchiveBuilder::gather_klasses_and_symbols).
192
      //
193
      // We cannot use arena because arena chunks are allocated by the OS. As a result, for example,
194
      // the archived symbol of "java/lang/Object" may sometimes be lower than "java/lang/String", and
195
      // sometimes be higher. This would cause non-deterministic contents in the archive.
196
      DEBUG_ONLY(static void* last = nullptr);
197
      void* p = (void*)MetaspaceShared::symbol_space_alloc(alloc_size);
198
      assert(p > last, "must increase monotonically");
199
      DEBUG_ONLY(last = p);
200
      return p;
201
    }
202
#endif
203
    if (value.refcount() != PERM_REFCOUNT) {
204
      return AllocateHeap(alloc_size, mtSymbol);
205
    } else {
206
      // Allocate to global arena
207
      MutexLocker ml(SymbolArena_lock, Mutex::_no_safepoint_check_flag); // Protect arena
208
      return SymbolTable::arena()->Amalloc(alloc_size);
209
    }
210
  }
211
};
212

213
void SymbolTable::create_table ()  {
214
  size_t start_size_log_2 = ceil_log2(SymbolTableSize);
215
  _current_size = ((size_t)1) << start_size_log_2;
216
  log_trace(symboltable)("Start size: " SIZE_FORMAT " (" SIZE_FORMAT ")",
217
                         _current_size, start_size_log_2);
218
  _local_table = new SymbolTableHash(start_size_log_2, END_SIZE, REHASH_LEN, true);
219

220
  // Initialize the arena for global symbols, size passed in depends on CDS.
221
  if (symbol_alloc_arena_size == 0) {
222
    _arena = new (mtSymbol) Arena(mtSymbol);
223
  } else {
224
    _arena = new (mtSymbol) Arena(mtSymbol, Arena::Tag::tag_other, symbol_alloc_arena_size);
225
  }
226
}
227

228
void SymbolTable::reset_has_items_to_clean() { Atomic::store(&_has_items_to_clean, false); }
229
void SymbolTable::mark_has_items_to_clean()  { Atomic::store(&_has_items_to_clean, true); }
230
bool SymbolTable::has_items_to_clean()       { return Atomic::load(&_has_items_to_clean); }
231

232
void SymbolTable::item_added() {
233
  Atomic::inc(&_items_count);
234
}
235

236
void SymbolTable::item_removed() {
237
  Atomic::inc(&(_symbols_removed));
238
  Atomic::dec(&_items_count);
239
}
240

241
double SymbolTable::get_load_factor() {
242
  return (double)_items_count/(double)_current_size;
243
}
244

245
size_t SymbolTable::table_size() {
246
  return ((size_t)1) << _local_table->get_size_log2(Thread::current());
247
}
248

249
bool SymbolTable::has_work() { return Atomic::load_acquire(&_has_work); }
250

251
void SymbolTable::trigger_cleanup() {
252
  // Avoid churn on ServiceThread
253
  if (!has_work()) {
254
    MutexLocker ml(Service_lock, Mutex::_no_safepoint_check_flag);
255
    _has_work = true;
256
    Service_lock->notify_all();
257
  }
258
}
259

260
class SymbolsDo : StackObj {
261
  SymbolClosure *_cl;
262
public:
263
  SymbolsDo(SymbolClosure *cl) : _cl(cl) {}
264
  bool operator()(Symbol* value) {
265
    assert(value != nullptr, "expected valid value");
266
    _cl->do_symbol(&value);
267
    return true;
268
  };
269
};
270

271
class SharedSymbolIterator {
272
  SymbolClosure* _symbol_closure;
273
public:
274
  SharedSymbolIterator(SymbolClosure* f) : _symbol_closure(f) {}
275
  void do_value(Symbol* symbol) {
276
    _symbol_closure->do_symbol(&symbol);
277
  }
278
};
279

280
// Call function for all symbols in the symbol table.
281
void SymbolTable::symbols_do(SymbolClosure *cl) {
282
  assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint");
283
  // all symbols from shared table
284
  SharedSymbolIterator iter(cl);
285
  _shared_table.iterate(&iter);
286
  _dynamic_shared_table.iterate(&iter);
287

288
  // all symbols from the dynamic table
289
  SymbolsDo sd(cl);
290
  _local_table->do_safepoint_scan(sd);
291
}
292

293
// Call function for all symbols in shared table. Used by -XX:+PrintSharedArchiveAndExit
294
void SymbolTable::shared_symbols_do(SymbolClosure *cl) {
295
  SharedSymbolIterator iter(cl);
296
  _shared_table.iterate(&iter);
297
  _dynamic_shared_table.iterate(&iter);
298
}
299

300
Symbol* SymbolTable::lookup_dynamic(const char* name,
301
                                    int len, unsigned int hash) {
302
  Symbol* sym = do_lookup(name, len, hash);
303
  assert((sym == nullptr) || sym->refcount() != 0, "refcount must not be zero");
304
  return sym;
305
}
306

307
#if INCLUDE_CDS
308
Symbol* SymbolTable::lookup_shared(const char* name,
309
                                   int len, unsigned int hash) {
310
  Symbol* sym = nullptr;
311
  if (!_shared_table.empty()) {
312
    if (_alt_hash) {
313
      // hash_code parameter may use alternate hashing algorithm but the shared table
314
      // always uses the same original hash code.
315
      hash = hash_shared_symbol(name, len);
316
    }
317
    sym = _shared_table.lookup(name, hash, len);
318
    if (sym == nullptr && DynamicArchive::is_mapped()) {
319
      sym = _dynamic_shared_table.lookup(name, hash, len);
320
    }
321
  }
322
  return sym;
323
}
324
#endif
325

326
Symbol* SymbolTable::lookup_common(const char* name,
327
                            int len, unsigned int hash) {
328
  Symbol* sym;
329
  if (_lookup_shared_first) {
330
    sym = lookup_shared(name, len, hash);
331
    if (sym == nullptr) {
332
      _lookup_shared_first = false;
333
      sym = lookup_dynamic(name, len, hash);
334
    }
335
  } else {
336
    sym = lookup_dynamic(name, len, hash);
337
    if (sym == nullptr) {
338
      sym = lookup_shared(name, len, hash);
339
      if (sym != nullptr) {
340
        _lookup_shared_first = true;
341
      }
342
    }
343
  }
344
  return sym;
345
}
346

347
// Symbols should represent entities from the constant pool that are
348
// limited to <64K in length, but usage errors creep in allowing Symbols
349
// to be used for arbitrary strings. For debug builds we will assert if
350
// a string is too long, whereas product builds will truncate it.
351
static int check_length(const char* name, int len) {
352
  assert(len <= Symbol::max_length(),
353
         "String length %d exceeds the maximum Symbol length of %d", len, Symbol::max_length());
354
  if (len > Symbol::max_length()) {
355
    warning("A string \"%.80s ... %.80s\" exceeds the maximum Symbol "
356
            "length of %d and has been truncated", name, (name + len - 80), Symbol::max_length());
357
    len = Symbol::max_length();
358
  }
359
  return len;
360
}
361

362
Symbol* SymbolTable::new_symbol(const char* name, int len) {
363
  len = check_length(name, len);
364
  unsigned int hash = hash_symbol(name, len, _alt_hash);
365
  Symbol* sym = lookup_common(name, len, hash);
366
  if (sym == nullptr) {
367
    sym = do_add_if_needed(name, len, hash, /* is_permanent */ false);
368
  }
369
  assert(sym->refcount() != 0, "lookup should have incremented the count");
370
  assert(sym->equals(name, len), "symbol must be properly initialized");
371
  return sym;
372
}
373

374
Symbol* SymbolTable::new_symbol(const Symbol* sym, int begin, int end) {
375
  assert(begin <= end && end <= sym->utf8_length(), "just checking");
376
  assert(sym->refcount() != 0, "require a valid symbol");
377
  const char* name = (const char*)sym->base() + begin;
378
  int len = end - begin;
379
  assert(len <= Symbol::max_length(), "sanity");
380
  unsigned int hash = hash_symbol(name, len, _alt_hash);
381
  Symbol* found = lookup_common(name, len, hash);
382
  if (found == nullptr) {
383
    found = do_add_if_needed(name, len, hash, /* is_permanent */ false);
384
  }
385
  return found;
386
}
387

388
class SymbolTableLookup : StackObj {
389
private:
390
  uintx _hash;
391
  int _len;
392
  const char* _str;
393
public:
394
  SymbolTableLookup(const char* key, int len, uintx hash)
395
  : _hash(hash), _len(len), _str(key) {}
396
  uintx get_hash() const {
397
    return _hash;
398
  }
399
  // Note: When equals() returns "true", the symbol's refcount is incremented. This is
400
  // needed to ensure that the symbol is kept alive before equals() returns to the caller,
401
  // so that another thread cannot clean the symbol up concurrently. The caller is
402
  // responsible for decrementing the refcount, when the symbol is no longer needed.
403
  bool equals(Symbol* value) {
404
    assert(value != nullptr, "expected valid value");
405
    Symbol *sym = value;
406
    if (sym->equals(_str, _len)) {
407
      if (sym->try_increment_refcount()) {
408
        // something is referencing this symbol now.
409
        return true;
410
      } else {
411
        assert(sym->refcount() == 0, "expected dead symbol");
412
        return false;
413
      }
414
    } else {
415
      return false;
416
    }
417
  }
418
  bool is_dead(Symbol* value) {
419
    return value->refcount() == 0;
420
  }
421
};
422

423
class SymbolTableGet : public StackObj {
424
  Symbol* _return;
425
public:
426
  SymbolTableGet() : _return(nullptr) {}
427
  void operator()(Symbol* value) {
428
    assert(value != nullptr, "expected valid value");
429
    _return = value;
430
  }
431
  Symbol* get_res_sym() const {
432
    return _return;
433
  }
434
};
435

436
void SymbolTable::update_needs_rehash(bool rehash) {
437
  if (rehash) {
438
    _needs_rehashing = true;
439
    trigger_cleanup();
440
  }
441
}
442

443
Symbol* SymbolTable::do_lookup(const char* name, int len, uintx hash) {
444
  Thread* thread = Thread::current();
445
  SymbolTableLookup lookup(name, len, hash);
446
  SymbolTableGet stg;
447
  bool rehash_warning = false;
448
  _local_table->get(thread, lookup, stg, &rehash_warning);
449
  update_needs_rehash(rehash_warning);
450
  Symbol* sym = stg.get_res_sym();
451
  assert((sym == nullptr) || sym->refcount() != 0, "found dead symbol");
452
  return sym;
453
}
454

455
Symbol* SymbolTable::lookup_only(const char* name, int len, unsigned int& hash) {
456
  hash = hash_symbol(name, len, _alt_hash);
457
  return lookup_common(name, len, hash);
458
}
459

460
// Suggestion: Push unicode-based lookup all the way into the hashing
461
// and probing logic, so there is no need for convert_to_utf8 until
462
// an actual new Symbol* is created.
463
Symbol* SymbolTable::new_symbol(const jchar* name, int utf16_length) {
464
  int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
465
  char stack_buf[ON_STACK_BUFFER_LENGTH];
466
  if (utf8_length < (int) sizeof(stack_buf)) {
467
    char* chars = stack_buf;
468
    UNICODE::convert_to_utf8(name, utf16_length, chars);
469
    return new_symbol(chars, utf8_length);
470
  } else {
471
    ResourceMark rm;
472
    char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
473
    UNICODE::convert_to_utf8(name, utf16_length, chars);
474
    return new_symbol(chars, utf8_length);
475
  }
476
}
477

478
Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,
479
                                         unsigned int& hash) {
480
  int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
481
  char stack_buf[ON_STACK_BUFFER_LENGTH];
482
  if (utf8_length < (int) sizeof(stack_buf)) {
483
    char* chars = stack_buf;
484
    UNICODE::convert_to_utf8(name, utf16_length, chars);
485
    return lookup_only(chars, utf8_length, hash);
486
  } else {
487
    ResourceMark rm;
488
    char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
489
    UNICODE::convert_to_utf8(name, utf16_length, chars);
490
    return lookup_only(chars, utf8_length, hash);
491
  }
492
}
493

494
void SymbolTable::new_symbols(ClassLoaderData* loader_data, const constantPoolHandle& cp,
495
                              int names_count, const char** names, int* lengths,
496
                              int* cp_indices, unsigned int* hashValues) {
497
  // Note that is_permanent will be false for non-strong hidden classes.
498
  // even if their loader is the boot loader because they will have a different cld.
499
  bool is_permanent = loader_data->is_the_null_class_loader_data();
500
  for (int i = 0; i < names_count; i++) {
501
    const char *name = names[i];
502
    int len = lengths[i];
503
    assert(len <= Symbol::max_length(), "must be - these come from the constant pool");
504
    unsigned int hash = hashValues[i];
505
    assert(lookup_shared(name, len, hash) == nullptr, "must have checked already");
506
    Symbol* sym = do_add_if_needed(name, len, hash, is_permanent);
507
    assert(sym->refcount() != 0, "lookup should have incremented the count");
508
    cp->symbol_at_put(cp_indices[i], sym);
509
  }
510
}
511

512
Symbol* SymbolTable::do_add_if_needed(const char* name, int len, uintx hash, bool is_permanent) {
513
  assert(len <= Symbol::max_length(), "caller should have ensured this");
514
  SymbolTableLookup lookup(name, len, hash);
515
  SymbolTableGet stg;
516
  bool clean_hint = false;
517
  bool rehash_warning = false;
518
  Thread* current = Thread::current();
519
  Symbol* sym;
520

521
  ResourceMark rm(current);
522
  const int alloc_size = Symbol::byte_size(len);
523
  u1* u1_buf = NEW_RESOURCE_ARRAY_IN_THREAD(current, u1, alloc_size);
524
  Symbol* tmp = ::new ((void*)u1_buf) Symbol((const u1*)name, len,
525
                                             (is_permanent || CDSConfig::is_dumping_static_archive()) ? PERM_REFCOUNT : 1);
526

527
  do {
528
    if (_local_table->insert(current, lookup, *tmp, &rehash_warning, &clean_hint)) {
529
      if (_local_table->get(current, lookup, stg, &rehash_warning)) {
530
        sym = stg.get_res_sym();
531
        // The get adds one to ref count, but we inserted with our ref already included.
532
        // Therefore decrement with one.
533
        if (sym->refcount() != PERM_REFCOUNT) {
534
          sym->decrement_refcount();
535
        }
536
        break;
537
      }
538
    }
539

540
    // In case another thread did a concurrent add, return value already in the table.
541
    // This could fail if the symbol got deleted concurrently, so loop back until success.
542
    if (_local_table->get(current, lookup, stg, &rehash_warning)) {
543
      // The lookup added a refcount, which is ours.
544
      sym = stg.get_res_sym();
545
      break;
546
    }
547
  } while(true);
548

549
  update_needs_rehash(rehash_warning);
550

551
  if (clean_hint) {
552
    mark_has_items_to_clean();
553
    check_concurrent_work();
554
  }
555

556
  assert((sym == nullptr) || sym->refcount() != 0, "found dead symbol");
557
  return sym;
558
}
559

560
Symbol* SymbolTable::new_permanent_symbol(const char* name) {
561
  unsigned int hash = 0;
562
  int len = check_length(name, (int)strlen(name));
563
  Symbol* sym = SymbolTable::lookup_only(name, len, hash);
564
  if (sym == nullptr) {
565
    sym = do_add_if_needed(name, len, hash, /* is_permanent */ true);
566
  }
567
  if (!sym->is_permanent()) {
568
    sym->make_permanent();
569
    log_trace_symboltable_helper(sym, "Asked for a permanent symbol, but got a regular one");
570
  }
571
  return sym;
572
}
573

574
struct SizeFunc : StackObj {
575
  size_t operator()(Symbol* value) {
576
    assert(value != nullptr, "expected valid value");
577
    return (value)->size() * HeapWordSize;
578
  };
579
};
580

581
TableStatistics SymbolTable::get_table_statistics() {
582
  static TableStatistics ts;
583
  SizeFunc sz;
584
  ts = _local_table->statistics_get(Thread::current(), sz, ts);
585
  return ts;
586
}
587

588
void SymbolTable::print_table_statistics(outputStream* st) {
589
  SizeFunc sz;
590
  _local_table->statistics_to(Thread::current(), sz, st, "SymbolTable");
591

592
  if (!_shared_table.empty()) {
593
    _shared_table.print_table_statistics(st, "Shared Symbol Table");
594
  }
595

596
  if (!_dynamic_shared_table.empty()) {
597
    _dynamic_shared_table.print_table_statistics(st, "Dynamic Shared Symbol Table");
598
  }
599
}
600

601
// Verification
602
class VerifySymbols : StackObj {
603
public:
604
  bool operator()(Symbol* value) {
605
    guarantee(value != nullptr, "expected valid value");
606
    Symbol* sym = value;
607
    guarantee(sym->equals((const char*)sym->bytes(), sym->utf8_length()),
608
              "symbol must be internally consistent");
609
    return true;
610
  };
611
};
612

613
void SymbolTable::verify() {
614
  Thread* thr = Thread::current();
615
  VerifySymbols vs;
616
  if (!_local_table->try_scan(thr, vs)) {
617
    log_info(symboltable)("verify unavailable at this moment");
618
  }
619
}
620

621
static void print_symbol(outputStream* st, Symbol* sym) {
622
  const char* utf8_string = (const char*)sym->bytes();
623
  int utf8_length = sym->utf8_length();
624
  st->print("%d %d: ", utf8_length, sym->refcount());
625
  HashtableTextDump::put_utf8(st, utf8_string, utf8_length);
626
  st->cr();
627
}
628

629
// Dumping
630
class DumpSymbol : StackObj {
631
  Thread* _thr;
632
  outputStream* _st;
633
public:
634
  DumpSymbol(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}
635
  bool operator()(Symbol* value) {
636
    assert(value != nullptr, "expected valid value");
637
    print_symbol(_st, value);
638
    return true;
639
  };
640
};
641

642
class DumpSharedSymbol : StackObj {
643
  outputStream* _st;
644
public:
645
  DumpSharedSymbol(outputStream* st) : _st(st) {}
646
  void do_value(Symbol* value) {
647
    assert(value != nullptr, "value should point to a symbol");
648
    print_symbol(_st, value);
649
  };
650
};
651

652
void SymbolTable::dump(outputStream* st, bool verbose) {
653
  if (!verbose) {
654
    print_table_statistics(st);
655
  } else {
656
    Thread* thr = Thread::current();
657
    ResourceMark rm(thr);
658
    st->print_cr("VERSION: 1.1");
659
    DumpSymbol ds(thr, st);
660
    if (!_local_table->try_scan(thr, ds)) {
661
      log_info(symboltable)("dump unavailable at this moment");
662
    }
663
    if (!_shared_table.empty()) {
664
      st->print_cr("#----------------");
665
      st->print_cr("# Shared symbols:");
666
      st->print_cr("#----------------");
667
      DumpSharedSymbol dss(st);
668
      _shared_table.iterate(&dss);
669
    }
670
    if (!_dynamic_shared_table.empty()) {
671
      st->print_cr("#------------------------");
672
      st->print_cr("# Dynamic shared symbols:");
673
      st->print_cr("#------------------------");
674
      DumpSharedSymbol dss(st);
675
      _dynamic_shared_table.iterate(&dss);
676
    }
677
  }
678
}
679

680
#if INCLUDE_CDS
681
void SymbolTable::copy_shared_symbol_table(GrowableArray<Symbol*>* symbols,
682
                                           CompactHashtableWriter* writer) {
683
  ArchiveBuilder* builder = ArchiveBuilder::current();
684
  int len = symbols->length();
685
  for (int i = 0; i < len; i++) {
686
    Symbol* sym = ArchiveBuilder::get_buffered_symbol(symbols->at(i));
687
    unsigned int fixed_hash = hash_shared_symbol((const char*)sym->bytes(), sym->utf8_length());
688
    assert(fixed_hash == hash_symbol((const char*)sym->bytes(), sym->utf8_length(), false),
689
           "must not rehash during dumping");
690
    sym->set_permanent();
691
    writer->add(fixed_hash, builder->buffer_to_offset_u4((address)sym));
692
  }
693
}
694

695
size_t SymbolTable::estimate_size_for_archive() {
696
  if (_items_count > (size_t)max_jint) {
697
    fatal("Too many symbols to be archived: %zu", _items_count);
698
  }
699
  return CompactHashtableWriter::estimate_size(int(_items_count));
700
}
701

702
void SymbolTable::write_to_archive(GrowableArray<Symbol*>* symbols) {
703
  CompactHashtableWriter writer(int(_items_count), ArchiveBuilder::symbol_stats());
704
  copy_shared_symbol_table(symbols, &writer);
705
  if (CDSConfig::is_dumping_static_archive()) {
706
    _shared_table.reset();
707
    writer.dump(&_shared_table, "symbol");
708
  } else {
709
    assert(CDSConfig::is_dumping_dynamic_archive(), "must be");
710
    _dynamic_shared_table.reset();
711
    writer.dump(&_dynamic_shared_table, "symbol");
712
  }
713
}
714

715
void SymbolTable::serialize_shared_table_header(SerializeClosure* soc,
716
                                                bool is_static_archive) {
717
  OffsetCompactHashtable<const char*, Symbol*, symbol_equals_compact_hashtable_entry> * table;
718
  if (is_static_archive) {
719
    table = &_shared_table;
720
  } else {
721
    table = &_dynamic_shared_table;
722
  }
723
  table->serialize_header(soc);
724
  if (soc->writing()) {
725
    // Sanity. Make sure we don't use the shared table at dump time
726
    table->reset();
727
  }
728
}
729
#endif //INCLUDE_CDS
730

731
// Concurrent work
732
void SymbolTable::grow(JavaThread* jt) {
733
  SymbolTableHash::GrowTask gt(_local_table);
734
  if (!gt.prepare(jt)) {
735
    return;
736
  }
737
  log_trace(symboltable)("Started to grow");
738
  {
739
    TraceTime timer("Grow", TRACETIME_LOG(Debug, symboltable, perf));
740
    while (gt.do_task(jt)) {
741
      gt.pause(jt);
742
      {
743
        ThreadBlockInVM tbivm(jt);
744
      }
745
      gt.cont(jt);
746
    }
747
  }
748
  gt.done(jt);
749
  _current_size = table_size();
750
  log_debug(symboltable)("Grown to size:" SIZE_FORMAT, _current_size);
751
}
752

753
struct SymbolTableDoDelete : StackObj {
754
  size_t _deleted;
755
  SymbolTableDoDelete() : _deleted(0) {}
756
  void operator()(Symbol* value) {
757
    assert(value != nullptr, "expected valid value");
758
    Symbol *sym = value;
759
    assert(sym->refcount() == 0, "refcount");
760
    _deleted++;
761
  }
762
};
763

764
struct SymbolTableDeleteCheck : StackObj {
765
  size_t _processed;
766
  SymbolTableDeleteCheck() : _processed(0) {}
767
  bool operator()(Symbol* value) {
768
    assert(value != nullptr, "expected valid value");
769
    _processed++;
770
    Symbol *sym = value;
771
    return (sym->refcount() == 0);
772
  }
773
};
774

775
void SymbolTable::clean_dead_entries(JavaThread* jt) {
776
  SymbolTableHash::BulkDeleteTask bdt(_local_table);
777
  if (!bdt.prepare(jt)) {
778
    return;
779
  }
780

781
  SymbolTableDeleteCheck stdc;
782
  SymbolTableDoDelete stdd;
783
  NativeHeapTrimmer::SuspendMark sm("symboltable");
784
  {
785
    TraceTime timer("Clean", TRACETIME_LOG(Debug, symboltable, perf));
786
    while (bdt.do_task(jt, stdc, stdd)) {
787
      bdt.pause(jt);
788
      {
789
        ThreadBlockInVM tbivm(jt);
790
      }
791
      bdt.cont(jt);
792
    }
793
    reset_has_items_to_clean();
794
    bdt.done(jt);
795
  }
796

797
  Atomic::add(&_symbols_counted, stdc._processed);
798

799
  log_debug(symboltable)("Cleaned " SIZE_FORMAT " of " SIZE_FORMAT,
800
                         stdd._deleted, stdc._processed);
801
}
802

803
void SymbolTable::check_concurrent_work() {
804
  if (has_work()) {
805
    return;
806
  }
807
  // We should clean/resize if we have
808
  // more items than preferred load factor or
809
  // more dead items than water mark.
810
  if (has_items_to_clean() || (get_load_factor() > PREF_AVG_LIST_LEN)) {
811
    log_debug(symboltable)("Concurrent work triggered, load factor: %f, items to clean: %s",
812
                           get_load_factor(), has_items_to_clean() ? "true" : "false");
813
    trigger_cleanup();
814
  }
815
}
816

817
bool SymbolTable::should_grow() {
818
  return get_load_factor() > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached();
819
}
820

821
void SymbolTable::do_concurrent_work(JavaThread* jt) {
822
  // Rehash if needed.  Rehashing goes to a safepoint but the rest of this
823
  // work is concurrent.
824
  if (needs_rehashing() && maybe_rehash_table()) {
825
    Atomic::release_store(&_has_work, false);
826
    return; // done, else grow
827
  }
828
  log_debug(symboltable, perf)("Concurrent work, live factor: %g", get_load_factor());
829
  // We prefer growing, since that also removes dead items
830
  if (should_grow()) {
831
    grow(jt);
832
  } else {
833
    clean_dead_entries(jt);
834
  }
835
  Atomic::release_store(&_has_work, false);
836
}
837

838
// Called at VM_Operation safepoint
839
void SymbolTable::rehash_table() {
840
  assert(SafepointSynchronize::is_at_safepoint(), "must be called at safepoint");
841
  // The ServiceThread initiates the rehashing so it is not resizing.
842
  assert (_local_table->is_safepoint_safe(), "Should not be resizing now");
843

844
  _alt_hash_seed = AltHashing::compute_seed();
845

846
  // We use current size
847
  size_t new_size = _local_table->get_size_log2(Thread::current());
848
  SymbolTableHash* new_table = new SymbolTableHash(new_size, END_SIZE, REHASH_LEN, true);
849
  // Use alt hash from now on
850
  _alt_hash = true;
851
  _local_table->rehash_nodes_to(Thread::current(), new_table);
852

853
  // free old table
854
  delete _local_table;
855
  _local_table = new_table;
856

857
  _rehashed = true;
858
  _needs_rehashing = false;
859
}
860

861
bool SymbolTable::maybe_rehash_table() {
862
  log_debug(symboltable)("Table imbalanced, rehashing called.");
863

864
  // Grow instead of rehash.
865
  if (should_grow()) {
866
    log_debug(symboltable)("Choosing growing over rehashing.");
867
    _needs_rehashing = false;
868
    return false;
869
  }
870

871
  // Already rehashed.
872
  if (_rehashed) {
873
    log_warning(symboltable)("Rehashing already done, still long lists.");
874
    _needs_rehashing = false;
875
    return false;
876
  }
877

878
  VM_RehashSymbolTable op;
879
  VMThread::execute(&op);
880
  return true;
881
}
882

883
//---------------------------------------------------------------------------
884
// Non-product code
885

886
#ifndef PRODUCT
887

888
class HistogramIterator : StackObj {
889
public:
890
  static const size_t results_length = 100;
891
  size_t counts[results_length];
892
  size_t sizes[results_length];
893
  size_t total_size;
894
  size_t total_count;
895
  size_t total_length;
896
  size_t max_length;
897
  size_t out_of_range_count;
898
  size_t out_of_range_size;
899
  HistogramIterator() : total_size(0), total_count(0), total_length(0),
900
                        max_length(0), out_of_range_count(0), out_of_range_size(0) {
901
    // initialize results to zero
902
    for (size_t i = 0; i < results_length; i++) {
903
      counts[i] = 0;
904
      sizes[i] = 0;
905
    }
906
  }
907
  bool operator()(Symbol* value) {
908
    assert(value != nullptr, "expected valid value");
909
    Symbol* sym = value;
910
    size_t size = sym->size();
911
    size_t len = sym->utf8_length();
912
    if (len < results_length) {
913
      counts[len]++;
914
      sizes[len] += size;
915
    } else {
916
      out_of_range_count++;
917
      out_of_range_size += size;
918
    }
919
    total_count++;
920
    total_size += size;
921
    total_length += len;
922
    max_length = MAX2(max_length, len);
923

924
    return true;
925
  };
926
};
927

928
void SymbolTable::print_histogram() {
929
  HistogramIterator hi;
930
  _local_table->do_scan(Thread::current(), hi);
931
  tty->print_cr("Symbol Table Histogram:");
932
  tty->print_cr("  Total number of symbols  " SIZE_FORMAT_W(7), hi.total_count);
933
  tty->print_cr("  Total size in memory     " SIZE_FORMAT_W(7) "K", (hi.total_size * wordSize) / K);
934
  tty->print_cr("  Total counted            " SIZE_FORMAT_W(7), _symbols_counted);
935
  tty->print_cr("  Total removed            " SIZE_FORMAT_W(7), _symbols_removed);
936
  if (_symbols_counted > 0) {
937
    tty->print_cr("  Percent removed          %3.2f",
938
          ((double)_symbols_removed / (double)_symbols_counted) * 100);
939
  }
940
  tty->print_cr("  Reference counts         " SIZE_FORMAT_W(7), Symbol::_total_count);
941
  tty->print_cr("  Symbol arena used        " SIZE_FORMAT_W(7) "K", arena()->used() / K);
942
  tty->print_cr("  Symbol arena size        " SIZE_FORMAT_W(7) "K", arena()->size_in_bytes() / K);
943
  tty->print_cr("  Total symbol length      " SIZE_FORMAT_W(7), hi.total_length);
944
  tty->print_cr("  Maximum symbol length    " SIZE_FORMAT_W(7), hi.max_length);
945
  tty->print_cr("  Average symbol length    %7.2f", ((double)hi.total_length / (double)hi.total_count));
946
  tty->print_cr("  Symbol length histogram:");
947
  tty->print_cr("    %6s %10s %10s", "Length", "#Symbols", "Size");
948
  for (size_t i = 0; i < hi.results_length; i++) {
949
    if (hi.counts[i] > 0) {
950
      tty->print_cr("    " SIZE_FORMAT_W(6) " " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) "K",
951
                    i, hi.counts[i], (hi.sizes[i] * wordSize) / K);
952
    }
953
  }
954
  tty->print_cr("  >=" SIZE_FORMAT_W(6) " " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) "K\n",
955
                hi.results_length, hi.out_of_range_count, (hi.out_of_range_size*wordSize) / K);
956
}
957
#endif // PRODUCT
958

959
// Utility for dumping symbols
960
SymboltableDCmd::SymboltableDCmd(outputStream* output, bool heap) :
961
                                 DCmdWithParser(output, heap),
962
  _verbose("-verbose", "Dump the content of each symbol in the table",
963
           "BOOLEAN", false, "false") {
964
  _dcmdparser.add_dcmd_option(&_verbose);
965
}
966

967
void SymboltableDCmd::execute(DCmdSource source, TRAPS) {
968
  VM_DumpHashtable dumper(output(), VM_DumpHashtable::DumpSymbols,
969
                         _verbose.value());
970
  VMThread::execute(&dumper);
971
}
972