38 #include "runtime/mutexLocker.hpp"

    35 #include "runtime/interfaceSupport.inline.hpp"

    39 #include "runtime/safepointVerifiers.hpp"

    36 #include "runtime/timerTrace.hpp"

    41 #include "utilities/hashtable.inline.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

    50 bool SymbolTable::_needs_rehashing = false;

    65 

    51 bool SymbolTable::_lookup_shared_first = false;

    66 static juint murmur_seed = 0;

    52 

    67 

    53 CompactHashtable<Symbol*, char> SymbolTable::_shared_table;

    68 static inline void log_trace_symboltable_helper(Symbol* sym, const char* msg) {

    54 

    69 #ifndef PRODUCT

    55 Symbol* SymbolTable::allocate_symbol(const u1* name, int len, bool c_heap, TRAPS) {

    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     MutexLocker ml(SymbolTable_lock); // 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) {

    65     sym = new (len, THREAD) Symbol(name, len, 1);

   196     sym = new (len, THREAD) Symbol((const u1*)name, len, 1);

    69     sym = new (len, arena(), THREAD) Symbol(name, len, PERM_REFCOUNT);

   200     MutexLocker ml(SymbolTable_lock); // Protect arena

   201     sym = new (len, arena(), THREAD) Symbol((const u1*)name, len, PERM_REFCOUNT);

    89   const int n = the_table()->table_size();

   233   SymbolsDo sd(cl);

    90   for (int i = 0; i < n; i++) {

   234   if (!SymbolTable::the_table()->_local_table->try_scan(Thread::current(), sd)) {

    91     for (HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);

   235     log_info(stringtable)("symbols_do unavailable at this moment");

    92          p != NULL;

   236   }

    93          p = p->next()) {

   237 }

    94       cl->do_symbol(p->literal_addr());

   238 

    95     }

   239 class MetaspacePointersDo : StackObj {

    96   }

   240   MetaspaceClosure *_it;

    97 }

   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 };

   101   const int n = the_table()->table_size();

   253   MetaspacePointersDo mpd(it);

   102   for (int i = 0; i < n; i++) {

   254   SymbolTable::the_table()->_local_table->do_scan(Thread::current(), mpd);

   103     for (HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);

   255 }

   104          p != NULL;

   256 

   105          p = p->next()) {

   257 Symbol* SymbolTable::lookup_dynamic(const char* name,

   106       it->push(p->literal_addr());

   107     }

   108   }

   109 }

   110 

   111 int SymbolTable::_symbols_removed = 0;

   112 int SymbolTable::_symbols_counted = 0;

   113 volatile int SymbolTable::_parallel_claimed_idx = 0;

   114 

   115 void SymbolTable::buckets_unlink(int start_idx, int end_idx, BucketUnlinkContext* context) {

   116   for (int i = start_idx; i < end_idx; ++i) {

   117     HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i);

   118     HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i);

   119     while (entry != NULL) {

   120       // Shared entries are normally at the end of the bucket and if we run into

   121       // a shared entry, then there is nothing more to remove. However, if we

   122       // have rehashed the table, then the shared entries are no longer at the

   123       // end of the bucket.

   124       if (entry->is_shared() && !use_alternate_hashcode()) {

   125         break;

   126       }

   127       Symbol* s = entry->literal();

   128       context->_num_processed++;

   129       assert(s != NULL, "just checking");

   130       // If reference count is zero, remove.

   131       if (s->refcount() == 0) {

   132         assert(!entry->is_shared(), "shared entries should be kept live");

   133         delete s;

   134         *p = entry->next();

   135         context->free_entry(entry);

   136       } else {

   137         p = entry->next_addr();

   138       }

   139       // get next entry

   140       entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p);

   141     }

   142   }

   143 }

   144 

   145 // Remove unreferenced symbols from the symbol table

   146 // This is done late during GC.

   147 void SymbolTable::unlink(int* processed, int* removed) {

   148   BucketUnlinkContext context;

   149   buckets_unlink(0, the_table()->table_size(), &context);

   150   _the_table->bulk_free_entries(&context);

   151   *processed = context._num_processed;

   152   *removed = context._num_removed;

   153 

   154   _symbols_removed = context._num_removed;

   155   _symbols_counted = context._num_processed;

   156 }

   157 

   158 void SymbolTable::possibly_parallel_unlink(int* processed, int* removed) {

   159   const int limit = the_table()->table_size();

   160 

   161   BucketUnlinkContext context;

   162   for (;;) {

   163     // Grab next set of buckets to scan

   164     int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;

   165     if (start_idx >= limit) {

   166       // End of table

   167       break;

   168     }

   169 

   170     int end_idx = MIN2(limit, start_idx + ClaimChunkSize);

   171     buckets_unlink(start_idx, end_idx, &context);

   172   }

   173 

   174   _the_table->bulk_free_entries(&context);

   175   *processed = context._num_processed;

   176   *removed = context._num_removed;

   177 

   178   Atomic::add(context._num_processed, &_symbols_counted);

   179   Atomic::add(context._num_removed, &_symbols_removed);

   180 }

   181 

   182 // Create a new table and using alternate hash code, populate the new table

   183 // with the existing strings.   Set flag to use the alternate hash code afterwards.

   184 void SymbolTable::rehash_table() {

   185   if (DumpSharedSpaces) {

   186     tty->print_cr("Warning: rehash_table should not be called while dumping archive");

   187     return;

   188   }

   189 

   190   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");

   191   // This should never happen with -Xshare:dump but it might in testing mode.

   192   if (DumpSharedSpaces) return;

   193 

   194   // Create a new symbol table

   195   SymbolTable* new_table = new SymbolTable();

   196 

   197   the_table()->move_to(new_table);

   198 

   199   // Delete the table and buckets (entries are reused in new table).

   200   delete _the_table;

   201   // Don't check if we need rehashing until the table gets unbalanced again.

   202   // Then rehash with a new global seed.

   203   _needs_rehashing = false;

   204   _the_table = new_table;

   205 }

   206 

   207 // Lookup a symbol in a bucket.

   208 

   209 Symbol* SymbolTable::lookup_dynamic(int index, const char* name,

   211   int count = 0;

   259   Symbol* sym = SymbolTable::the_table()->do_lookup(name, len, hash);

   212   for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) {

   260   assert((sym == NULL) || sym->refcount() != 0, "refcount must not be zero");

   213     count++;  // count all entries in this bucket, not just ones with same hash

   261   return sym;

   214     if (e->hash() == hash) {

   215       Symbol* sym = e->literal();

   216       // Skip checking already dead symbols in the bucket.

   217       if (sym->refcount() == 0) {

   218         count--;   // Don't count this symbol towards rehashing.

   219       } else if (sym->equals(name, len)) {

   220         if (sym->try_increment_refcount()) {

   221           // something is referencing this symbol now.

   222           return sym;

   223         } else {

   224           count--;   // don't count this symbol.

   225         }

   226       }

   227     }

   228   }

   229   // If the bucket size is too deep check if this hash code is insufficient.

   230   if (count >= rehash_count && !needs_rehashing()) {

   231     _needs_rehashing = check_rehash_table(count);

   232   }

   233   return NULL;

   238   if (use_alternate_hashcode()) {

   266   if (!_shared_table.empty()) {

   239     // hash_code parameter may use alternate hashing algorithm but the shared table

   267     if (SymbolTable::_alt_hash) {

   240     // always uses the same original hash code.

   268       // hash_code parameter may use alternate hashing algorithm but the shared table

   241     hash = hash_shared_symbol(name, len);

   269       // always uses the same original hash code.

   242   }

   270       hash = hash_shared_symbol(name, len);

   243   return _shared_table.lookup(name, hash, len);

   271     }

   244 }

   272     return _shared_table.lookup(name, hash, len);

   245 

   273   } else {

   246 Symbol* SymbolTable::lookup(int index, const char* name,

   274     return NULL;

   275   }

   276 }

   277 

   278 Symbol* SymbolTable::lookup_common(const char* name,

   251     if (sym != NULL) {

   283     if (sym == NULL) {

   252       return sym;

   284       _lookup_shared_first = false;

   253     }

   285       sym = lookup_dynamic(name, len, hash);

   254     _lookup_shared_first = false;

   286     }

   255     return lookup_dynamic(index, name, len, hash);

   287   } else {

   256   } else {

   288     sym = lookup_dynamic(name, len, hash);

   257     sym = lookup_dynamic(index, name, len, hash);

   289     if (sym == NULL) {

   258     if (sym != NULL) {

   290       sym = lookup_shared(name, len, hash);

   259       return sym;

   291       if (sym != NULL) {

   260     }

   292         _lookup_shared_first = true;

   261     sym = lookup_shared(name, len, hash);

   293       }

   262     if (sym != NULL) {

   294     }

   263       _lookup_shared_first = true;

   295   }

   264     }

   265     return sym;

   266   }

   267 }

   268 

   269 u4 SymbolTable::encode_shared(Symbol* sym) {

   270   assert(DumpSharedSpaces, "called only during dump time");

   271   uintx base_address = uintx(MetaspaceShared::shared_rs()->base());

   272   uintx offset = uintx(sym) - base_address;

   273   assert(offset < 0x7fffffff, "sanity");

   274   return u4(offset);

   275 }

   276 

   277 Symbol* SymbolTable::decode_shared(u4 offset) {

   278   assert(!DumpSharedSpaces, "called only during runtime");

   279   uintx base_address = _shared_table.base_address();

   280   Symbol* sym = (Symbol*)(base_address + offset);

   281 

   282 #ifndef PRODUCT

   283   const char* s = (const char*)sym->bytes();

   284   int len = sym->utf8_length();

   285   unsigned int hash = hash_symbol(s, len);

   286   assert(sym == lookup_shared(s, len, hash), "must be shared symbol");

   287 #endif

   288 

   312   unsigned int hashValue = hash_symbol(name, len);

   300   unsigned int hash = hash_symbol(name, len, SymbolTable::_alt_hash);

   313   int index = the_table()->hash_to_index(hashValue);

   301   Symbol* sym = SymbolTable::the_table()->lookup_common(name, len, hash);

   314 

   302   if (sym == NULL) {

   315   Symbol* s = the_table()->lookup(index, name, len, hashValue);

   303     sym = SymbolTable::the_table()->do_add_if_needed(name, len, hash, true, CHECK_NULL);

   316 

   304   }

   317   // Found

   305   assert(sym->refcount() != 0, "lookup should have incremented the count");

   318   if (s != NULL) return s;

   306   assert(sym->equals(name, len), "symbol must be properly initialized");

   319 

   307   return sym;

   320   // Grab SymbolTable_lock first.

   321   MutexLocker ml(SymbolTable_lock, THREAD);

   322 

   323   // Otherwise, add to symbol to table

   324   return the_table()->basic_add(index, (u1*)name, len, hashValue, true, THREAD);

   328   char* buffer;

   311   assert(sym->refcount() != 0, "require a valid symbol");

   329   int index, len;

   312   const char* name = (const char*)sym->base() + begin;

   330   unsigned int hashValue;

   313   int len = end - begin;

   331   char* name;

   314   unsigned int hash = hash_symbol(name, len, SymbolTable::_alt_hash);

   332   {

   315   Symbol* found = SymbolTable::the_table()->lookup_common(name, len, hash);

   333     debug_only(NoSafepointVerifier nsv;)

   316   if (found == NULL) {

   334 

   317     found = SymbolTable::the_table()->do_add_if_needed(name, len, hash, true, THREAD);

   335     name = (char*)sym->base() + begin;

   318   }

   336     len = end - begin;

   319   return found;

   337     hashValue = hash_symbol(name, len);

   320 }

   338     index = the_table()->hash_to_index(hashValue);

   321 

   339     Symbol* s = the_table()->lookup(index, name, len, hashValue);

   322 class SymbolTableLookup : StackObj {

   340 

   323 private:

   341     // Found

   324   Thread* _thread;

   342     if (s != NULL) return s;

   325   uintx _hash;

   343   }

   326   int _len;

   344 

   327   const char* _str;

   345   // Otherwise, add to symbol to table. Copy to a C string first.

   328 public:

   346   char stack_buf[128];

   329   SymbolTableLookup(Thread* thread, const char* key, int len, uintx hash)

   347   ResourceMark rm(THREAD);

   330   : _thread(thread), _hash(hash), _len(len), _str(key) {}

   348   if (len <= 128) {

   331   uintx get_hash() const {

   349     buffer = stack_buf;

   332     return _hash;

   350   } else {

   333   }

   351     buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len);

   334   bool equals(Symbol** value, bool* is_dead) {

   352   }

   335     assert(value != NULL, "expected valid value");

   353   for (int i=0; i<len; i++) {

   336     assert(*value != NULL, "value should point to a symbol");

   354     buffer[i] = name[i];

   337     Symbol *sym = *value;

   355   }

   338     if (sym->equals(_str, _len)) {

   356   // Make sure there is no safepoint in the code above since name can't move.

   339       if (sym->try_increment_refcount()) {

   357   // We can't include the code in NoSafepointVerifier because of the

   340         // something is referencing this symbol now.

   358   // ResourceMark.

   341         return true;

   359 

   342       } else {

   360   // Grab SymbolTable_lock first.

   343         assert(sym->refcount() == 0, "expected dead symbol");

   361   MutexLocker ml(SymbolTable_lock, THREAD);

   344         *is_dead = true;

   362 

   345         return false;

   363   return the_table()->basic_add(index, (u1*)buffer, len, hashValue, true, THREAD);

   364 }

   365 

   366 Symbol* SymbolTable::lookup_only(const char* name, int len,

   367                                    unsigned int& hash) {

   368   hash = hash_symbol(name, len);

   369   int index = the_table()->hash_to_index(hash);

   370 

   371   Symbol* s = the_table()->lookup(index, name, len, hash);

   372   return s;

   373 }

   374 

   375 // Look up the address of the literal in the SymbolTable for this Symbol*

   376 // Do not create any new symbols

   377 // Do not increment the reference count to keep this alive

   378 Symbol** SymbolTable::lookup_symbol_addr(Symbol* sym){

   379   unsigned int hash = hash_symbol((char*)sym->bytes(), sym->utf8_length());

   380   int index = the_table()->hash_to_index(hash);

   381 

   382   for (HashtableEntry<Symbol*, mtSymbol>* e = the_table()->bucket(index); e != NULL; e = e->next()) {

   383     if (e->hash() == hash) {

   384       Symbol* literal_sym = e->literal();

   385       if (sym == literal_sym) {

   386         return e->literal_addr();

   388     }

   347     } else {

   389   }

   348       *is_dead = (sym->refcount() == 0);

   390   return NULL;

   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);

   398   char stack_buf[128];

   392   char stack_buf[ON_STACK_BUFFER_LENGTH];

   405     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);;

   399     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);

   414   char stack_buf[128];

   408   char stack_buf[ON_STACK_BUFFER_LENGTH];

   421     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);;

   415     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);

   428                       int names_count,

   422                       int names_count, const char** names, int* lengths,

   429                       const char** names, int* lengths, int* cp_indices,

   423                       int* cp_indices, unsigned int* hashValues, TRAPS) {

   430                       unsigned int* hashValues, TRAPS) {

   424   bool c_heap = !loader_data->is_the_null_class_loader_data();

   431   // Grab SymbolTable_lock first.

   425   for (int i = 0; i < names_count; i++) {

   432   MutexLocker ml(SymbolTable_lock, THREAD);

   426     const char *name = names[i];

   433 

   427     int len = lengths[i];

   434   SymbolTable* table = the_table();

   428     unsigned int hash = hashValues[i];

   435   bool added = table->basic_add(loader_data, cp, names_count, names, lengths,

   429     Symbol* sym = SymbolTable::the_table()->lookup_common(name, len, hash);

   436                                 cp_indices, hashValues, CHECK);

   430     if (sym == NULL) {

   437   if (!added) {

   431       sym = SymbolTable::the_table()->do_add_if_needed(name, len, hash, c_heap, CHECK);

   438     // do it the hard way

   432     }

   439     for (int i=0; i<names_count; i++) {

   433     assert(sym->refcount() != 0, "lookup should have incremented the count");

   440       int index = table->hash_to_index(hashValues[i]);

   434     cp->symbol_at_put(cp_indices[i], sym);

   441       bool c_heap = !loader_data->is_the_null_class_loader_data();

   435   }

   442       Symbol* sym = table->basic_add(index, (u1*)names[i], lengths[i], hashValues[i], c_heap, CHECK);

   436 }

   443       cp->symbol_at_put(cp_indices[i], sym);

   437 

   444     }

   438 class SymbolTableCreateEntry : public StackObj {

   445   }

   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) == _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;

   449   unsigned int hash;

   518   unsigned int hash = 0;

   450   Symbol* result = SymbolTable::lookup_only((char*)name, (int)strlen(name), hash);

   519   int len = (int)strlen(name);

   451   if (result != NULL) {

   520   Symbol* sym = SymbolTable::lookup_only(name, len, hash);

   452     return result;

   521   if (sym == NULL) {

   453   }

   522     sym = SymbolTable::the_table()->do_add_if_needed(name, len, hash, false, CHECK_NULL);

   454   // Grab SymbolTable_lock first.

   523   }

   455   MutexLocker ml(SymbolTable_lock, THREAD);

   524   if (sym->refcount() != PERM_REFCOUNT) {

   456 

   525     sym->increment_refcount();

   457   SymbolTable* table = the_table();

   526     log_trace_symboltable_helper(sym, "Asked for a permanent symbol, but got a regular one");

   458   int index = table->hash_to_index(hash);

   527   }

   459   return table->basic_add(index, (u1*)name, (int)strlen(name), hash, false, THREAD);

   460 }

   461 

   462 Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len,

   463                                unsigned int hashValue_arg, bool c_heap, TRAPS) {

   464   assert(!Universe::heap()->is_in_reserved(name),

   465          "proposed name of symbol must be stable");

   466 

   467   // Don't allow symbols to be created which cannot fit in a Symbol*.

   468   if (len > Symbol::max_length()) {

   469     THROW_MSG_0(vmSymbols::java_lang_InternalError(),

   470                 "name is too long to represent");

   471   }

   472 

   473   // Cannot hit a safepoint in this function because the "this" pointer can move.

   474   NoSafepointVerifier nsv;

   475 

   476   // Check if the symbol table has been rehashed, if so, need to recalculate

   477   // the hash value and index.

   478   unsigned int hashValue;

   479   int index;

   480   if (use_alternate_hashcode()) {

   481     hashValue = hash_symbol((const char*)name, len);

   482     index = hash_to_index(hashValue);

   483   } else {

   484     hashValue = hashValue_arg;

   485     index = index_arg;

   486   }

   487 

   488   // Since look-up was done lock-free, we need to check if another

   489   // thread beat us in the race to insert the symbol.

   490   Symbol* test = lookup(index, (char*)name, len, hashValue);

   491   if (test != NULL) {

   492     // A race occurred and another thread introduced the symbol.

   493     assert(test->refcount() != 0, "lookup should have incremented the count");

   494     return test;

   495   }

   496 

   497   // Create a new symbol.

   498   Symbol* sym = allocate_symbol(name, len, c_heap, CHECK_NULL);

   499   assert(sym->equals((char*)name, len), "symbol must be properly initialized");

   500 

   501   HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);

   502   add_entry(index, entry);

   506 // This version of basic_add adds symbols in batch from the constant pool

   531 struct SizeFunc : StackObj {

   507 // parsing.

   532   size_t operator()(Symbol** value) {

   508 bool SymbolTable::basic_add(ClassLoaderData* loader_data, const constantPoolHandle& cp,

   533     assert(value != NULL, "expected valid value");

   509                             int names_count,

   534     assert(*value != NULL, "value should point to a symbol");

   510                             const char** names, int* lengths,

   535     return (*value)->size() * HeapWordSize;

   511                             int* cp_indices, unsigned int* hashValues,

   536   };

   512                             TRAPS) {

   537 };

   513 

   538 

   514   // Check symbol names are not too long.  If any are too long, don't add any.

   539 void SymbolTable::print_table_statistics(outputStream* st,

   515   for (int i = 0; i< names_count; i++) {

   540                                          const char* table_name) {

   516     if (lengths[i] > Symbol::max_length()) {

   541   SizeFunc sz;

   517       THROW_MSG_0(vmSymbols::java_lang_InternalError(),

   542   _local_table->statistics_to(Thread::current(), sz, st, table_name);

   518                   "name is too long to represent");

   543 }

   519     }

   544 

   520   }

   545 // Verification

   521 

   546 class VerifySymbols : StackObj {

   522   // Cannot hit a safepoint in this function because the "this" pointer can move.

   547 public:

   523   NoSafepointVerifier nsv;

   548   bool operator()(Symbol** value) {

   524 

   549     guarantee(value != NULL, "expected valid value");

   525   for (int i=0; i<names_count; i++) {

   550     guarantee(*value != NULL, "value should point to a symbol");

   526     // Check if the symbol table has been rehashed, if so, need to recalculate

   551     Symbol* sym = *value;

   527     // the hash value.

   552     guarantee(sym->equals((const char*)sym->bytes(), sym->utf8_length()),

   528     unsigned int hashValue;

   553               "symbol must be internally consistent");

   529     if (use_alternate_hashcode()) {

   554     return true;

   530       hashValue = hash_symbol(names[i], lengths[i]);

   555   };

   531     } else {

   556 };

   532       hashValue = hashValues[i];

   533     }

   534     // Since look-up was done lock-free, we need to check if another

   535     // thread beat us in the race to insert the symbol.

   536     int index = hash_to_index(hashValue);

   537     Symbol* test = lookup(index, names[i], lengths[i], hashValue);

   538     if (test != NULL) {

   539       // A race occurred and another thread introduced the symbol, this one

   540       // will be dropped and collected. Use test instead.

   541       cp->symbol_at_put(cp_indices[i], test);

   542       assert(test->refcount() != 0, "lookup should have incremented the count");

   543     } else {

   544       // Create a new symbol.  The null class loader is never unloaded so these

   545       // are allocated specially in a permanent arena.

   546       bool c_heap = !loader_data->is_the_null_class_loader_data();

   547       Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], c_heap, CHECK_(false));

   548       assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized");  // why wouldn't it be???

   549       HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);

   550       add_entry(index, entry);

   551       cp->symbol_at_put(cp_indices[i], sym);

   552     }

   553   }

   554   return true;

   555 }

   556 

   559   for (int i = 0; i < the_table()->table_size(); ++i) {

   559   Thread* thr = Thread::current();

   560     HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);

   560   VerifySymbols vs;

   561     for ( ; p != NULL; p = p->next()) {

   561   if (!SymbolTable::the_table()->_local_table->try_scan(thr, vs)) {

   562       Symbol* s = (Symbol*)(p->literal());

   562     log_info(stringtable)("verify unavailable at this moment");

   563       guarantee(s != NULL, "symbol is NULL");

   563   }

   564       unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length());

   564 }

   565       guarantee(p->hash() == h, "broken hash in symbol table entry");

   565 

   566       guarantee(the_table()->hash_to_index(h) == i,

   566 // Dumping

   567                 "wrong index in symbol table");

   567 class DumpSymbol : StackObj {

   568     }

   568   Thread* _thr;

   569   }

   569   outputStream* _st;

   570 }

   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 };

   574     the_table()->print_table_statistics(st, "SymbolTable");

   587     SymbolTable::the_table()->print_table_statistics(st, "SymbolTable");

   575   } else {

   588   } else {

   576     st->print_cr("VERSION: 1.0");

   589     Thread* thr = Thread::current();

   577     for (int i = 0; i < the_table()->table_size(); ++i) {

   590     ResourceMark rm(thr);

   578       HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);

   591     st->print_cr("VERSION: 1.1");

   579       for ( ; p != NULL; p = p->next()) {

   592     DumpSymbol ds(thr, st);

   580         Symbol* s = (Symbol*)(p->literal());

   593     if (!SymbolTable::the_table()->_local_table->try_scan(thr, ds)) {

   581         const char* utf8_string = (const char*)s->bytes();

   594       log_info(symboltable)("dump unavailable at this moment");

   582         int utf8_length = s->utf8_length();

   595     }

   583         st->print("%d %d: ", utf8_length, s->refcount());

   596   }

   584         HashtableTextDump::put_utf8(st, utf8_string, utf8_length);

   597 }

   585         st->cr();

   598 

   586       }

   599 #if INCLUDE_CDS

   587     }

   600 struct CopyToArchive : StackObj {

   588   }

   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);

   592 #if INCLUDE_CDS

   627   _shared_table.reset();

   593     _shared_table.reset();

   628 

   594 

   629   int num_buckets = (int)(SymbolTable::the_table()->_items_count / SharedSymbolTableBucketSize);

   595     int num_buckets = the_table()->number_of_entries() /

   630   // calculation of num_buckets can result in zero buckets, we need at least one

   596                             SharedSymbolTableBucketSize;

   631   CompactSymbolTableWriter writer(num_buckets > 1 ? num_buckets : 1,

   597     CompactSymbolTableWriter writer(num_buckets,

   632                                   &MetaspaceShared::stats()->symbol);

   598                                     &MetaspaceShared::stats()->symbol);

   633   copy_shared_symbol_table(&writer);

   599     for (int i = 0; i < the_table()->table_size(); ++i) {

   634   writer.dump(&_shared_table);

   600       HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);

   635 

   601       for ( ; p != NULL; p = p->next()) {

   636   // Verify table is correct

   602         Symbol* s = (Symbol*)(p->literal());

   637   Symbol* sym = vmSymbols::java_lang_Object();

   603       unsigned int fixed_hash =  hash_shared_symbol((char*)s->bytes(), s->utf8_length());

   638   const char* name = (const char*)sym->bytes();

   604         assert(fixed_hash == p->hash(), "must not rehash during dumping");

   639   int len = sym->utf8_length();

   605         writer.add(fixed_hash, s);

   640   unsigned int hash = hash_symbol(name, len, SymbolTable::_alt_hash);

   606       }

   641   assert(sym == _shared_table.lookup(name, hash, len), "sanity");

   607     }

   608 

   609     writer.dump(&_shared_table);

   610 

   611     // Verify table is correct

   612     Symbol* sym = vmSymbols::java_lang_Object();

   613     const char* name = (const char*)sym->bytes();

   614     int len = sym->utf8_length();

   615     unsigned int hash = hash_symbol(name, len);

   616     assert(sym == _shared_table.lookup(name, hash, len), "sanity");

   617 #endif

   629 #endif

   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();