       1 /*
       2  * Copyright (c) 1997, 2014, 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/javaClasses.hpp"
      28 #include "classfile/symbolTable.hpp"
      29 #include "classfile/systemDictionary.hpp"
      30 #include "gc_interface/collectedHeap.inline.hpp"
      31 #include "memory/allocation.inline.hpp"
      32 #include "memory/filemap.hpp"
      33 #include "memory/gcLocker.inline.hpp"
      34 #include "oops/oop.inline.hpp"
      35 #include "oops/oop.inline2.hpp"
      36 #include "runtime/mutexLocker.hpp"
      37 #include "utilities/hashtable.inline.hpp"
      38 #if INCLUDE_ALL_GCS
      39 #include "gc_implementation/g1/g1SATBCardTableModRefBS.hpp"
      40 #include "gc_implementation/g1/g1StringDedup.hpp"
      41 #endif
      42
      43 PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
      44
      45 // --------------------------------------------------------------------------
      46
      47 // the number of buckets a thread claims
      48 const int ClaimChunkSize = 32;
      49
      50 SymbolTable* SymbolTable::_the_table = NULL;
      51 // Static arena for symbols that are not deallocated
      52 Arena* SymbolTable::_arena = NULL;
      53 bool SymbolTable::_needs_rehashing = false;
      54
      55 Symbol* SymbolTable::allocate_symbol(const u1* name, int len, bool c_heap, TRAPS) {
      56   assert (len <= Symbol::max_length(), "should be checked by caller");
      57
      58   Symbol* sym;
      59
      60   if (DumpSharedSpaces) {
      61     // Allocate all symbols to CLD shared metaspace
      62     sym = new (len, ClassLoaderData::the_null_class_loader_data(), THREAD) Symbol(name, len, -1);
      63   } else if (c_heap) {
      64     // refcount starts as 1
      65     sym = new (len, THREAD) Symbol(name, len, 1);
      66     assert(sym != NULL, "new should call vm_exit_out_of_memory if C_HEAP is exhausted");
      67   } else {
      68     // Allocate to global arena
      69     sym = new (len, arena(), THREAD) Symbol(name, len, -1);
      70   }
      71   return sym;
      72 }
      73
      74 void SymbolTable::initialize_symbols(int arena_alloc_size) {
      75   // Initialize the arena for global symbols, size passed in depends on CDS.
      76   if (arena_alloc_size == 0) {
      77     _arena = new (mtSymbol) Arena(mtSymbol);
      78   } else {
      79     _arena = new (mtSymbol) Arena(mtSymbol, arena_alloc_size);
      80   }
      81 }
      82
      83 // Call function for all symbols in the symbol table.
      84 void SymbolTable::symbols_do(SymbolClosure *cl) {
      85   const int n = the_table()->table_size();
      86   for (int i = 0; i < n; i++) {
      87     for (HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
      88          p != NULL;
      89          p = p->next()) {
      90       cl->do_symbol(p->literal_addr());
      91     }
      92   }
      93 }
      94
      95 int SymbolTable::_symbols_removed = 0;
      96 int SymbolTable::_symbols_counted = 0;
      97 volatile int SymbolTable::_parallel_claimed_idx = 0;
      98
      99 void SymbolTable::buckets_unlink(int start_idx, int end_idx, int* processed, int* removed, size_t* memory_total) {
     100   const int limit = the_table()->table_size();
     101
     102   assert(0 <= start_idx && start_idx <= limit,
     103          err_msg("start_idx (" INT32_FORMAT ") is out of bounds", start_idx));
     104   assert(0 <= end_idx && end_idx <= limit,
     105          err_msg("end_idx (" INT32_FORMAT ") is out of bounds", end_idx));
     106   assert(start_idx <= end_idx,
     107          err_msg("Index ordering: start_idx=" INT32_FORMAT", end_idx=" INT32_FORMAT,
     108                  start_idx, end_idx));
     109
     110   for (int i = start_idx; i < end_idx; ++i) {
     111     HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i);
     112     HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i);
     113     while (entry != NULL) {
     114       // Shared entries are normally at the end of the bucket and if we run into
     115       // a shared entry, then there is nothing more to remove. However, if we
     116       // have rehashed the table, then the shared entries are no longer at the
     117       // end of the bucket.
     118       if (entry->is_shared() && !use_alternate_hashcode()) {
     119         break;
     120       }
     121       Symbol* s = entry->literal();
     122       (*memory_total) += s->size();
     123       (*processed)++;
     124       assert(s != NULL, "just checking");
     125       // If reference count is zero, remove.
     126       if (s->refcount() == 0) {
     127         assert(!entry->is_shared(), "shared entries should be kept live");
     128         delete s;
     129         (*removed)++;
     130         *p = entry->next();
     131         the_table()->free_entry(entry);
     132       } else {
     133         p = entry->next_addr();
     134       }
     135       // get next entry
     136       entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p);
     137     }
     138   }
     139 }
     140
     141 // Remove unreferenced symbols from the symbol table
     142 // This is done late during GC.
     143 void SymbolTable::unlink(int* processed, int* removed) {
     144   size_t memory_total = 0;
     145   buckets_unlink(0, the_table()->table_size(), processed, removed, &memory_total);
     146   _symbols_removed += *removed;
     147   _symbols_counted += *processed;
     148   // Exclude printing for normal PrintGCDetails because people parse
     149   // this output.
     150   if (PrintGCDetails && Verbose && WizardMode) {
     151     gclog_or_tty->print(" [Symbols=%d size=" SIZE_FORMAT "K] ", *processed,
     152                         (memory_total*HeapWordSize)/1024);
     153   }
     154 }
     155
     156 void SymbolTable::possibly_parallel_unlink(int* processed, int* removed) {
     157   const int limit = the_table()->table_size();
     158
     159   size_t memory_total = 0;
     160
     161   for (;;) {
     162     // Grab next set of buckets to scan
     163     int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
     164     if (start_idx >= limit) {
     165       // End of table
     166       break;
     167     }
     168
     169     int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
     170     buckets_unlink(start_idx, end_idx, processed, removed, &memory_total);
     171   }
     172   Atomic::add(*processed, &_symbols_counted);
     173   Atomic::add(*removed, &_symbols_removed);
     174   // Exclude printing for normal PrintGCDetails because people parse
     175   // this output.
     176   if (PrintGCDetails && Verbose && WizardMode) {
     177     gclog_or_tty->print(" [Symbols: scanned=%d removed=%d size=" SIZE_FORMAT "K] ", *processed, *removed,
     178                         (memory_total*HeapWordSize)/1024);
     179   }
     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   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
     186   // This should never happen with -Xshare:dump but it might in testing mode.
     187   if (DumpSharedSpaces) return;
     188   // Create a new symbol table
     189   SymbolTable* new_table = new SymbolTable();
     190
     191   the_table()->move_to(new_table);
     192
     193   // Delete the table and buckets (entries are reused in new table).
     194   delete _the_table;
     195   // Don't check if we need rehashing until the table gets unbalanced again.
     196   // Then rehash with a new global seed.
     197   _needs_rehashing = false;
     198   _the_table = new_table;
     199 }
     200
     201 // Lookup a symbol in a bucket.
     202
     203 Symbol* SymbolTable::lookup(int index, const char* name,
     204                               int len, unsigned int hash) {
     205 #ifndef PRODUCT
     206 //#ifdef PRODUCT_TEST
     207   jlong time = os::javaTimeNanos();
     208   _debug_all_lookup_count++;
     209   _debug_lookup_count++;
     210 #endif
     211
     212   unsigned int count = 0;
     213   for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) {
     214     count++;  // count all entries in this bucket, not just ones with same hash
     215     if (e->hash() == hash) {
     216       Symbol* sym = e->literal();
     217       if (sym->equals(name, len)) {
     218         // something is referencing this symbol now.
     219         sym->increment_refcount();
     220
     221         e->_debug_lookups++;
     222 #ifndef PRODUCT
     223 //#ifdef PRODUCT_TEST
     224         {
     225           unsigned int duration = os::javaTimeNanos()-time;
     226           _debug_lookup_found_count++;
     227           _debug_lookup_found_max_duration = (_debug_lookup_found_max_duration > duration) ? _debug_lookup_found_max_duration : duration;
     228           _debug_lookup_found_total_duration += duration;
     229           _debug_chain_found_maximum_length = (_debug_chain_found_maximum_length > count) ? _debug_chain_found_maximum_length : count;
     230           _debug_chain_found_total_length += count;
     231           //fprintf(stderr, "SymL %d:%d::%lu:\"%s\"\n", true, count, os::javaTimeNanos(), name);
     232
     233           long thread_id = os::current_thread_id();
     234           for (int i=0; i<1024; i++) {
     235             if (_debug_table_threads[i] == thread_id) {
     236               break;
     237             } else if (_debug_table_threads[i] == 0) {
     238               _debug_table_threads[i] = thread_id;
     239               break;
     240             }
     241           }
     242         }
     243 #endif
     244
     245         return sym;
     246       }
     247     }
     248   }
     249   // If the bucket size is too deep check if this hash code is insufficient.
     250   if (count >= rehash_count && !needs_rehashing()) {
     251     _needs_rehashing = check_rehash_table(count);
     252   }
     253
     254 #ifndef PRODUCT
     255 //#ifdef PRODUCT_TEST
     256   {
     257     unsigned int duration = os::javaTimeNanos()-time;
     258     _debug_lookup_failed_count++;
     259     _debug_lookup_failed_max_duration = (_debug_lookup_failed_max_duration > duration) ? _debug_lookup_failed_max_duration : duration;
     260     _debug_lookup_failed_total_duration += duration;
     261     _debug_chain_failed_maximum_length = (_debug_chain_failed_maximum_length > count) ? _debug_chain_failed_maximum_length : count;
     262     _debug_chain_failed_total_length += count;
     263     //fprintf(stderr, "SymL %d:%d::%lu:\"%s\"\n", false, count, os::javaTimeNanos(), name);
     264   }
     265 #endif
     266
     267   return NULL;
     268 }
     269
     270 // Pick hashing algorithm.
     271 unsigned int SymbolTable::hash_symbol(const char* s, int len) {
     272   return use_alternate_hashcode() ?
     273            AltHashing::murmur3_32(seed(), (const jbyte*)s, len) :
     274            java_lang_String::hash_code(s, len);
     275 }
     276
     277
     278 // We take care not to be blocking while holding the
     279 // SymbolTable_lock. Otherwise, the system might deadlock, since the
     280 // symboltable is used during compilation (VM_thread) The lock free
     281 // synchronization is simplified by the fact that we do not delete
     282 // entries in the symbol table during normal execution (only during
     283 // safepoints).
     284
     285 Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) {
     286   unsigned int hashValue = hash_symbol(name, len);
     287   int index = the_table()->hash_to_index(hashValue);
     288
     289   Symbol* s = the_table()->lookup(index, name, len, hashValue);
     290
     291   // Found
     292   if (s != NULL) return s;
     293
     294   // Grab SymbolTable_lock first.
     295   MutexLocker ml(SymbolTable_lock, THREAD);
     296
     297   // Otherwise, add to symbol to table
     298   return the_table()->basic_add(index, (u1*)name, len, hashValue, true, CHECK_NULL);
     299 }
     300
     301 Symbol* SymbolTable::lookup(const Symbol* sym, int begin, int end, TRAPS) {
     302   char* buffer;
     303   int index, len;
     304   unsigned int hashValue;
     305   char* name;
     306   {
     307     debug_only(No_Safepoint_Verifier nsv;)
     308
     309     name = (char*)sym->base() + begin;
     310     len = end - begin;
     311     hashValue = hash_symbol(name, len);
     312     index = the_table()->hash_to_index(hashValue);
     313     Symbol* s = the_table()->lookup(index, name, len, hashValue);
     314
     315     // Found
     316     if (s != NULL) return s;
     317   }
     318
     319   // Otherwise, add to symbol to table. Copy to a C string first.
     320   char stack_buf[128];
     321   ResourceMark rm(THREAD);
     322   if (len <= 128) {
     323     buffer = stack_buf;
     324   } else {
     325     buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len);
     326   }
     327   for (int i=0; i<len; i++) {
     328     buffer[i] = name[i];
     329   }
     330   // Make sure there is no safepoint in the code above since name can't move.
     331   // We can't include the code in No_Safepoint_Verifier because of the
     332   // ResourceMark.
     333
     334   // Grab SymbolTable_lock first.
     335   MutexLocker ml(SymbolTable_lock, THREAD);
     336
     337   return the_table()->basic_add(index, (u1*)buffer, len, hashValue, true, CHECK_NULL);
     338 }
     339
     340 Symbol* SymbolTable::lookup_only(const char* name, int len,
     341                                    unsigned int& hash) {
     342   hash = hash_symbol(name, len);
     343   int index = the_table()->hash_to_index(hash);
     344
     345   Symbol* s = the_table()->lookup(index, name, len, hash);
     346   return s;
     347 }
     348
     349 // Look up the address of the literal in the SymbolTable for this Symbol*
     350 // Do not create any new symbols
     351 // Do not increment the reference count to keep this alive
     352 Symbol** SymbolTable::lookup_symbol_addr(Symbol* sym){
     353   unsigned int hash = hash_symbol((char*)sym->bytes(), sym->utf8_length());
     354   int index = the_table()->hash_to_index(hash);
     355
     356   for (HashtableEntry<Symbol*, mtSymbol>* e = the_table()->bucket(index); e != NULL; e = e->next()) {
     357     if (e->hash() == hash) {
     358       Symbol* literal_sym = e->literal();
     359       if (sym == literal_sym) {
     360         return e->literal_addr();
     361       }
     362     }
     363   }
     364   return NULL;
     365 }
     366
     367 // Suggestion: Push unicode-based lookup all the way into the hashing
     368 // and probing logic, so there is no need for convert_to_utf8 until
     369 // an actual new Symbol* is created.
     370 Symbol* SymbolTable::lookup_unicode(const jchar* name, int utf16_length, TRAPS) {
     371   int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
     372   char stack_buf[128];
     373   if (utf8_length < (int) sizeof(stack_buf)) {
     374     char* chars = stack_buf;
     375     UNICODE::convert_to_utf8(name, utf16_length, chars);
     376     return lookup(chars, utf8_length, THREAD);
     377   } else {
     378     ResourceMark rm(THREAD);
     379     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);;
     380     UNICODE::convert_to_utf8(name, utf16_length, chars);
     381     return lookup(chars, utf8_length, THREAD);
     382   }
     383 }
     384
     385 Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,
     386                                            unsigned int& hash) {
     387   int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
     388   char stack_buf[128];
     389   if (utf8_length < (int) sizeof(stack_buf)) {
     390     char* chars = stack_buf;
     391     UNICODE::convert_to_utf8(name, utf16_length, chars);
     392     return lookup_only(chars, utf8_length, hash);
     393   } else {
     394     ResourceMark rm;
     395     char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);;
     396     UNICODE::convert_to_utf8(name, utf16_length, chars);
     397     return lookup_only(chars, utf8_length, hash);
     398   }
     399 }
     400
     401 void SymbolTable::add(ClassLoaderData* loader_data, constantPoolHandle cp,
     402                       int names_count,
     403                       const char** names, int* lengths, int* cp_indices,
     404                       unsigned int* hashValues, TRAPS) {
     405   // Grab SymbolTable_lock first.
     406   MutexLocker ml(SymbolTable_lock, THREAD);
     407
     408   SymbolTable* table = the_table();
     409   bool added = table->basic_add(loader_data, cp, names_count, names, lengths,
     410                                 cp_indices, hashValues, CHECK);
     411   if (!added) {
     412     // do it the hard way
     413     for (int i=0; i<names_count; i++) {
     414       int index = table->hash_to_index(hashValues[i]);
     415       bool c_heap = !loader_data->is_the_null_class_loader_data();
     416       Symbol* sym = table->basic_add(index, (u1*)names[i], lengths[i], hashValues[i], c_heap, CHECK);
     417       cp->symbol_at_put(cp_indices[i], sym);
     418     }
     419   }
     420 }
     421
     422 Symbol* SymbolTable::new_permanent_symbol(const char* name, TRAPS) {
     423   unsigned int hash;
     424   Symbol* result = SymbolTable::lookup_only((char*)name, (int)strlen(name), hash);
     425   if (result != NULL) {
     426     return result;
     427   }
     428   // Grab SymbolTable_lock first.
     429   MutexLocker ml(SymbolTable_lock, THREAD);
     430
     431   SymbolTable* table = the_table();
     432   int index = table->hash_to_index(hash);
     433   return table->basic_add(index, (u1*)name, (int)strlen(name), hash, false, THREAD);
     434 }
     435
     436 Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len,
     437                                unsigned int hashValue_arg, bool c_heap, TRAPS) {
     438   assert(SymbolTable_lock->is_locked(), "must hold SymbolTable_lock");
     439   assert(!Universe::heap()->is_in_reserved(name),
     440          "proposed name of symbol must be stable");
     441
     442   // Don't allow symbols to be created which cannot fit in a Symbol*.
     443   if (len > Symbol::max_length()) {
     444     THROW_MSG_0(vmSymbols::java_lang_InternalError(),
     445                 "name is too long to represent");
     446   }
     447
     448   // Cannot hit a safepoint in this function because the "this" pointer can move.
     449   No_Safepoint_Verifier nsv;
     450
     451   // Check if the symbol table has been rehashed, if so, need to recalculate
     452   // the hash value and index.
     453   unsigned int hashValue;
     454   int index;
     455   if (use_alternate_hashcode()) {
     456     hashValue = hash_symbol((const char*)name, len);
     457     index = hash_to_index(hashValue);
     458   } else {
     459     hashValue = hashValue_arg;
     460     index = index_arg;
     461   }
     462
     463   // Since look-up was done lock-free, we need to check if another
     464   // thread beat us in the race to insert the symbol.
     465   Symbol* test = lookup(index, (char*)name, len, hashValue);
     466   if (test != NULL) {
     467     // A race occurred and another thread introduced the symbol.
     468     assert(test->refcount() != 0, "lookup should have incremented the count");
     469     return test;
     470   }
     471
     472   // Create a new symbol.
     473   Symbol* sym = allocate_symbol(name, len, c_heap, CHECK_NULL);
     474   assert(sym->equals((char*)name, len), "symbol must be properly initialized");
     475
     476   HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
     477   add_entry(index, entry);
     478
     479 #ifndef PRODUCT
     480 //#ifdef PRODUCT_TEST
     481   {
     482     _debug_all_insertion_count++;
     483     _debug_insertion_count++;
     484     //fprintf(stderr, "SymA %lu:\"%s\"\n", os::javaTimeNanos(), name);
     485   }
     486 #endif
     487
     488   return sym;
     489 }
     490
     491 // This version of basic_add adds symbols in batch from the constant pool
     492 // parsing.
     493 bool SymbolTable::basic_add(ClassLoaderData* loader_data, constantPoolHandle cp,
     494                             int names_count,
     495                             const char** names, int* lengths,
     496                             int* cp_indices, unsigned int* hashValues,
     497                             TRAPS) {
     498   assert(SymbolTable_lock->is_locked(), "must hold SymbolTable_lock");
     499
     500   // Check symbol names are not too long.  If any are too long, don't add any.
     501   for (int i = 0; i< names_count; i++) {
     502     if (lengths[i] > Symbol::max_length()) {
     503       THROW_MSG_0(vmSymbols::java_lang_InternalError(),
     504                   "name is too long to represent");
     505     }
     506   }
     507
     508   // Cannot hit a safepoint in this function because the "this" pointer can move.
     509   No_Safepoint_Verifier nsv;
     510
     511   for (int i=0; i<names_count; i++) {
     512     // Check if the symbol table has been rehashed, if so, need to recalculate
     513     // the hash value.
     514     unsigned int hashValue;
     515     if (use_alternate_hashcode()) {
     516       hashValue = hash_symbol(names[i], lengths[i]);
     517     } else {
     518       hashValue = hashValues[i];
     519     }
     520     // Since look-up was done lock-free, we need to check if another
     521     // thread beat us in the race to insert the symbol.
     522     int index = hash_to_index(hashValue);
     523     Symbol* test = lookup(index, names[i], lengths[i], hashValue);
     524     if (test != NULL) {
     525       // A race occurred and another thread introduced the symbol, this one
     526       // will be dropped and collected. Use test instead.
     527       cp->symbol_at_put(cp_indices[i], test);
     528       assert(test->refcount() != 0, "lookup should have incremented the count");
     529     } else {
     530       // Create a new symbol.  The null class loader is never unloaded so these
     531       // are allocated specially in a permanent arena.
     532       bool c_heap = !loader_data->is_the_null_class_loader_data();
     533       Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], c_heap, CHECK_(false));
     534       assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized");  // why wouldn't it be???
     535       HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
     536       add_entry(index, entry);
     537       cp->symbol_at_put(cp_indices[i], sym);
     538
     539 #ifndef PRODUCT
     540 //#ifdef PRODUCT_TEST
     541       {
     542         _debug_all_insertion_count++;
     543         _debug_insertion_count++;
     544         //fprintf(stderr, "SymA %lu:\"%s\"\n", os::javaTimeNanos(), names[i]);
     545       }
     546 #endif
     547
     548     }
     549   }
     550   return true;
     551 }
     552
     553 void SymbolTable::verify() {
     554   MutexLocker mu(SymbolTable_lock);
     555   int actual_count = 0;
     556   for (int i = 0; i < the_table()->table_size(); ++i) {
     557     HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
     558     for ( ; p != NULL; p = p->next()) {
     559       Symbol* s = (Symbol*)(p->literal());
     560       guarantee(s != NULL, "symbol is NULL");
     561       unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length());
     562       guarantee(p->hash() == h, "broken hash in symbol table entry");
     563       guarantee(the_table()->hash_to_index(h) == i,
     564                 "wrong index in symbol table");
     565       actual_count++;
     566     }
     567   }
     568   if (the_table()->number_of_entries()!=actual_count) {
     569     tty->print("StringTable assert failure: number_of_entries()!=actual_count [%d!=%d]\n", the_table()->number_of_entries(), actual_count);
     570   }
     571   guarantee(the_table()->number_of_entries() == actual_count, "should be equal");
     572 }
     573
     574 //---------------------------------------------------------------------------
     575 // Non-product code
     576
     577 #ifndef PRODUCT
     578 void SymbolTable::print_histogram() {
     579   MutexLocker ml(SymbolTable_lock);
     580   const int results_length = 100;
     581   int results[results_length];
     582   int i,j;
     583
     584   // initialize results to zero
     585   for (j = 0; j < results_length; j++) {
     586     results[j] = 0;
     587   }
     588
     589   int total = 0;
     590   int max_symbols = 0;
     591   int out_of_range = 0;
     592   int memory_total = 0;
     593   int count = 0;
     594   for (i = 0; i < the_table()->table_size(); i++) {
     595     HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
     596     for ( ; p != NULL; p = p->next()) {
     597       memory_total += p->literal()->size();
     598       count++;
     599       int counter = p->literal()->utf8_length();
     600       total += counter;
     601       if (counter < results_length) {
     602         results[counter]++;
     603       } else {
     604         out_of_range++;
     605       }
     606       max_symbols = MAX2(max_symbols, counter);
     607     }
     608   }
     609   tty->print_cr("Symbol Table:");
     610   tty->print_cr("Total number of symbols  %5d", count);
     611   tty->print_cr("Total size in memory     %5dK",
     612           (memory_total*HeapWordSize)/1024);
     613   tty->print_cr("Total counted            %5d", _symbols_counted);
     614   tty->print_cr("Total removed            %5d", _symbols_removed);
     615   if (_symbols_counted > 0) {
     616     tty->print_cr("Percent removed          %3.2f",
     617           ((float)_symbols_removed/(float)_symbols_counted)* 100);
     618   }
     619   tty->print_cr("Reference counts         %5d", Symbol::_total_count);
     620   tty->print_cr("Symbol arena size        %5d used %5d",
     621                  arena()->size_in_bytes(), arena()->used());
     622   tty->print_cr("Histogram of symbol length:");
     623   tty->print_cr("%8s %5d", "Total  ", total);
     624   tty->print_cr("%8s %5d", "Maximum", max_symbols);
     625   tty->print_cr("%8s %3.2f", "Average",
     626           ((float) total / (float) the_table()->table_size()));
     627   tty->print_cr("%s", "Histogram:");
     628   tty->print_cr(" %s %29s", "Length", "Number chains that length");
     629   for (i = 0; i < results_length; i++) {
     630     if (results[i] > 0) {
     631       tty->print_cr("%6d %10d", i, results[i]);
     632     }
     633   }
     634   if (Verbose) {
     635     int line_length = 70;
     636     tty->print_cr("%s %30s", " Length", "Number chains that length");
     637     for (i = 0; i < results_length; i++) {
     638       if (results[i] > 0) {
     639         tty->print("%4d", i);
     640         for (j = 0; (j < results[i]) && (j < line_length);  j++) {
     641           tty->print("%1s", "*");
     642         }
     643         if (j == line_length) {
     644           tty->print("%1s", "+");
     645         }
     646         tty->cr();
     647       }
     648     }
     649   }
     650   tty->print_cr(" %s %d: %d\n", "Number chains longer than",
     651                     results_length, out_of_range);
     652 }
     653
     654 void SymbolTable::print() {
     655   for (int i = 0; i < the_table()->table_size(); ++i) {
     656     HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i);
     657     HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i);
     658     if (entry != NULL) {
     659       while (entry != NULL) {
     660         tty->print(PTR_FORMAT " ", entry->literal());
     661         entry->literal()->print();
     662         tty->print(" %d", entry->literal()->refcount());
     663         p = entry->next_addr();
     664         entry = (HashtableEntry<Symbol*, mtSymbol>*)HashtableEntry<Symbol*, mtSymbol>::make_ptr(*p);
     665       }
     666       tty->cr();
     667     }
     668   }
     669 }
     670 #endif // PRODUCT
     671
     672 // --------------------------------------------------------------------------
     673
     674 #ifdef ASSERT
     675 class StableMemoryChecker : public StackObj {
     676   enum { _bufsize = wordSize*4 };
     677
     678   address _region;
     679   jint    _size;
     680   u1      _save_buf[_bufsize];
     681
     682   int sample(u1* save_buf) {
     683     if (_size <= _bufsize) {
     684       memcpy(save_buf, _region, _size);
     685       return _size;
     686     } else {
     687       // copy head and tail
     688       memcpy(&save_buf[0],          _region,                      _bufsize/2);
     689       memcpy(&save_buf[_bufsize/2], _region + _size - _bufsize/2, _bufsize/2);
     690       return (_bufsize/2)*2;
     691     }
     692   }
     693
     694  public:
     695   StableMemoryChecker(const void* region, jint size) {
     696     _region = (address) region;
     697     _size   = size;
     698     sample(_save_buf);
     699   }
     700
     701   bool verify() {
     702     u1 check_buf[sizeof(_save_buf)];
     703     int check_size = sample(check_buf);
     704     return (0 == memcmp(_save_buf, check_buf, check_size));
     705   }
     706
     707   void set_region(const void* region) { _region = (address) region; }
     708 };
     709 #endif
     710
     711
     712 // --------------------------------------------------------------------------
     713 StringTable* StringTable::_the_table = NULL;
     714
     715 bool StringTable::_needs_rehashing = false;
     716
     717 volatile int StringTable::_parallel_claimed_idx = 0;
     718
     719 // Pick hashing algorithm
     720 unsigned int StringTable::hash_string(const jchar* s, int len) {
     721   return use_alternate_hashcode() ? AltHashing::murmur3_32(seed(), s, len) :
     722                                     java_lang_String::hash_code(s, len);
     723 }
     724
     725 oop StringTable::lookup(int index, jchar* name,
     726                         int len, unsigned int hash) {
     727 #ifndef PRODUCT
     728 //#ifdef PRODUCT_TEST
     729   jlong time = os::javaTimeNanos();
     730   _debug_all_lookup_count++;
     731   _debug_lookup_count++;
     732 #endif
     733
     734   unsigned int count = 0;
     735   for (HashtableEntry<oop, mtSymbol>* l = bucket(index); l != NULL; l = l->next()) {
     736     count++;
     737     if (l->hash() == hash) {
     738       if (java_lang_String::equals(l->literal(), name, len)) {
     739
     740         l->_debug_lookups++;
     741 #ifndef PRODUCT
     742 //#ifdef PRODUCT_TEST
     743         {
     744           unsigned int duration = os::javaTimeNanos()-time;
     745           _debug_lookup_found_count++;
     746           _debug_lookup_found_max_duration = (_debug_lookup_found_max_duration > duration) ? _debug_lookup_found_max_duration : duration;
     747           _debug_lookup_found_total_duration += duration;
     748           _debug_chain_found_maximum_length = (_debug_chain_found_maximum_length > count) ? _debug_chain_found_maximum_length : count;
     749           _debug_chain_found_total_length += count;
     750
     751           long thread_id = os::current_thread_id();
     752           for (int i=0; i<1024; i++) {
     753             if (_debug_table_threads[i] == thread_id) {
     754               break;
     755             } else if (_debug_table_threads[i] == 0) {
     756               _debug_table_threads[i] = thread_id;
     757               break;
     758             }
     759           }
     760         }
     761 #endif
     762
     763         return l->literal();
     764       }
     765     }
     766   }
     767   // If the bucket size is too deep check if this hash code is insufficient.
     768   if (count >= rehash_count && !needs_rehashing()) {
     769     _needs_rehashing = check_rehash_table(count);
     770   }
     771
     772 #ifndef PRODUCT
     773 //#ifdef PRODUCT_TEST
     774   {
     775     unsigned int duration = os::javaTimeNanos()-time;
     776     _debug_lookup_failed_count++;
     777     _debug_lookup_failed_max_duration = (_debug_lookup_failed_max_duration > duration) ? _debug_lookup_failed_max_duration : duration;
     778     _debug_lookup_failed_total_duration += duration;
     779     _debug_chain_failed_maximum_length = (_debug_chain_failed_maximum_length > count) ? _debug_chain_failed_maximum_length : count;
     780     _debug_chain_failed_total_length += count;
     781   }
     782 #endif
     783
     784   return NULL;
     785 }
     786
     787
     788 oop StringTable::basic_add(int index_arg, Handle string, jchar* name,
     789                            int len, unsigned int hashValue_arg, TRAPS) {
     790
     791   assert(StringTable_lock->is_locked(), "must hold StringTable_lock");
     792   assert(java_lang_String::equals(string(), name, len),
     793          "string must be properly initialized");
     794   // Cannot hit a safepoint in this function because the "this" pointer can move.
     795   No_Safepoint_Verifier nsv;
     796
     797   // Check if the symbol table has been rehashed, if so, need to recalculate
     798   // the hash value and index before second lookup.
     799   unsigned int hashValue;
     800   int index;
     801   if (use_alternate_hashcode()) {
     802     hashValue = hash_string(name, len);
     803     index = hash_to_index(hashValue);
     804   } else {
     805     hashValue = hashValue_arg;
     806     index = index_arg;
     807   }
     808
     809   // Since look-up was done lock-free, we need to check if another
     810   // thread beat us in the race to insert the symbol.
     811
     812   oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int)
     813   if (test != NULL) {
     814     // Entry already added
     815     return test;
     816   }
     817
     818   HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string());
     819   add_entry(index, entry);
     820
     821 #ifndef PRODUCT
     822 //#ifdef PRODUCT_TEST
     823   {
     824     _debug_all_insertion_count++;
     825     _debug_insertion_count++;
     826   }
     827 #endif
     828
     829   return string();
     830 }
     831
     832
     833 oop StringTable::lookup(Symbol* symbol) {
     834   ResourceMark rm;
     835   int length;
     836   jchar* chars = symbol->as_unicode(length);
     837   return lookup(chars, length);
     838 }
     839
     840 // Tell the GC that this string was looked up in the StringTable.
     841 static void ensure_string_alive(oop string) {
     842   // A lookup in the StringTable could return an object that was previously
     843   // considered dead. The SATB part of G1 needs to get notified about this
     844   // potential resurrection, otherwise the marking might not find the object.
     845 #if INCLUDE_ALL_GCS
     846   if (UseG1GC && string != NULL) {
     847     G1SATBCardTableModRefBS::enqueue(string);
     848   }
     849 #endif
     850 }
     851
     852 oop StringTable::lookup(jchar* name, int len) {
     853   unsigned int hash = hash_string(name, len);
     854   int index = the_table()->hash_to_index(hash);
     855   oop string = the_table()->lookup(index, name, len, hash);
     856
     857   ensure_string_alive(string);
     858
     859   return string;
     860 }
     861
     862
     863 oop StringTable::intern(Handle string_or_null, jchar* name,
     864                         int len, TRAPS) {
     865   unsigned int hashValue = hash_string(name, len);
     866   int index = the_table()->hash_to_index(hashValue);
     867   oop found_string = the_table()->lookup(index, name, len, hashValue);
     868
     869   // Found
     870   if (found_string != NULL) {
     871     ensure_string_alive(found_string);
     872     return found_string;
     873   }
     874
     875   debug_only(StableMemoryChecker smc(name, len * sizeof(name[0])));
     876   assert(!Universe::heap()->is_in_reserved(name),
     877          "proposed name of symbol must be stable");
     878
     879   Handle string;
     880   // try to reuse the string if possible
     881   if (!string_or_null.is_null()) {
     882     string = string_or_null;
     883   } else {
     884     string = java_lang_String::create_from_unicode(name, len, CHECK_NULL);
     885   }
     886
     887 #if INCLUDE_ALL_GCS
     888   if (G1StringDedup::is_enabled()) {
     889     // Deduplicate the string before it is interned. Note that we should never
     890     // deduplicate a string after it has been interned. Doing so will counteract
     891     // compiler optimizations done on e.g. interned string literals.
     892     G1StringDedup::deduplicate(string());
     893   }
     894 #endif
     895
     896   // Grab the StringTable_lock before getting the_table() because it could
     897   // change at safepoint.
     898   oop added_or_found;
     899   {
     900     MutexLocker ml(StringTable_lock, THREAD);
     901     // Otherwise, add to symbol to table
     902     added_or_found = the_table()->basic_add(index, string, name, len,
     903                                   hashValue, CHECK_NULL);
     904   }
     905
     906   ensure_string_alive(added_or_found);
     907
     908   return added_or_found;
     909 }
     910
     911 oop StringTable::intern(Symbol* symbol, TRAPS) {
     912   if (symbol == NULL) return NULL;
     913   ResourceMark rm(THREAD);
     914   int length;
     915   jchar* chars = symbol->as_unicode(length);
     916   Handle string;
     917   oop result = intern(string, chars, length, CHECK_NULL);
     918   return result;
     919 }
     920
     921
     922 oop StringTable::intern(oop string, TRAPS)
     923 {
     924   if (string == NULL) return NULL;
     925   ResourceMark rm(THREAD);
     926   int length;
     927   Handle h_string (THREAD, string);
     928   jchar* chars = java_lang_String::as_unicode_string(string, length, CHECK_NULL);
     929   oop result = intern(h_string, chars, length, CHECK_NULL);
     930   return result;
     931 }
     932
     933
     934 oop StringTable::intern(const char* utf8_string, TRAPS) {
     935   if (utf8_string == NULL) return NULL;
     936   ResourceMark rm(THREAD);
     937   int length = UTF8::unicode_length(utf8_string);
     938   jchar* chars = NEW_RESOURCE_ARRAY(jchar, length);
     939   UTF8::convert_to_unicode(utf8_string, chars, length);
     940   Handle string;
     941   oop result = intern(string, chars, length, CHECK_NULL);
     942   return result;
     943 }
     944
     945 void StringTable::unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int* processed, int* removed) {
     946   buckets_unlink_or_oops_do(is_alive, f, 0, the_table()->table_size(), processed, removed);
     947 }
     948
     949 void StringTable::possibly_parallel_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int* processed, int* removed) {
     950   // Readers of the table are unlocked, so we should only be removing
     951   // entries at a safepoint.
     952   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
     953   const int limit = the_table()->table_size();
     954
     955   for (;;) {
     956     // Grab next set of buckets to scan
     957     int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
     958     if (start_idx >= limit) {
     959       // End of table
     960       break;
     961     }
     962
     963     int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
     964     buckets_unlink_or_oops_do(is_alive, f, start_idx, end_idx, processed, removed);
     965   }
     966 }
     967
     968 void StringTable::buckets_oops_do(OopClosure* f, int start_idx, int end_idx) {
     969   const int limit = the_table()->table_size();
     970
     971   assert(0 <= start_idx && start_idx <= limit,
     972          err_msg("start_idx (" INT32_FORMAT ") is out of bounds", start_idx));
     973   assert(0 <= end_idx && end_idx <= limit,
     974          err_msg("end_idx (" INT32_FORMAT ") is out of bounds", end_idx));
     975   assert(start_idx <= end_idx,
     976          err_msg("Index ordering: start_idx=" INT32_FORMAT", end_idx=" INT32_FORMAT,
     977                  start_idx, end_idx));
     978
     979   for (int i = start_idx; i < end_idx; i += 1) {
     980     HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);
     981     while (entry != NULL) {
     982       assert(!entry->is_shared(), "CDS not used for the StringTable");
     983
     984       f->do_oop((oop*)entry->literal_addr());
     985
     986       entry = entry->next();
     987     }
     988   }
     989 }
     990
     991 void StringTable::buckets_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int start_idx, int end_idx, int* processed, int* removed) {
     992   const int limit = the_table()->table_size();
     993
     994   assert(0 <= start_idx && start_idx <= limit,
     995          err_msg("start_idx (" INT32_FORMAT ") is out of bounds", start_idx));
     996   assert(0 <= end_idx && end_idx <= limit,
     997          err_msg("end_idx (" INT32_FORMAT ") is out of bounds", end_idx));
     998   assert(start_idx <= end_idx,
     999          err_msg("Index ordering: start_idx=" INT32_FORMAT", end_idx=" INT32_FORMAT,
    1000                  start_idx, end_idx));
    1001
    1002   for (int i = start_idx; i < end_idx; ++i) {
    1003     HashtableEntry<oop, mtSymbol>** p = the_table()->bucket_addr(i);
    1004     HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);
    1005     while (entry != NULL) {
    1006       assert(!entry->is_shared(), "CDS not used for the StringTable");
    1007
    1008       if (is_alive->do_object_b(entry->literal())) {
    1009         if (f != NULL) {
    1010           f->do_oop((oop*)entry->literal_addr());
    1011         }
    1012         p = entry->next_addr();
    1013       } else {
    1014         *p = entry->next();
    1015         the_table()->free_entry(entry);
    1016         (*removed)++;
    1017       }
    1018       (*processed)++;
    1019       entry = (HashtableEntry<oop, mtSymbol>*)HashtableEntry<oop, mtSymbol>::make_ptr(*p);
    1020       entry = *p;
    1021     }
    1022   }
    1023 }
    1024
    1025 void StringTable::oops_do(OopClosure* f) {
    1026   buckets_oops_do(f, 0, the_table()->table_size());
    1027 }
    1028
    1029 void StringTable::possibly_parallel_oops_do(OopClosure* f) {
    1030   const int limit = the_table()->table_size();
    1031
    1032   for (;;) {
    1033     // Grab next set of buckets to scan
    1034     int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
    1035     if (start_idx >= limit) {
    1036       // End of table
    1037       break;
    1038     }
    1039
    1040     int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
    1041     buckets_oops_do(f, start_idx, end_idx);
    1042   }
    1043 }
    1044
    1045 // This verification is part of Universe::verify() and needs to be quick.
    1046 // See StringTable::verify_and_compare() below for exhaustive verification.
    1047 void StringTable::verify() {
    1048   MutexLocker mu(StringTable_lock);
    1049   int actual_count = 0;
    1050   for (int i = 0; i < the_table()->table_size(); ++i) {
    1051     HashtableEntry<oop, mtSymbol>* p = the_table()->bucket(i);
    1052     for ( ; p != NULL; p = p->next()) {
    1053       oop s = p->literal();
    1054       guarantee(s != NULL, "interned string is NULL");
    1055       unsigned int h = java_lang_String::hash_string(s);
    1056       guarantee(p->hash() == h, "broken hash in string table entry");
    1057 //      if (the_table()->hash_to_index(h) != i) {
    1058 //        fprintf(stderr, "h: %d\n", h);
    1059 //        fprintf(stderr, "the_table()->hash_to_index(h: %d\n", the_table()->hash_to_index(h));
    1060 //        fprintf(stderr, "i: %d\n", i);
    1061 //      }
    1062       guarantee(the_table()->hash_to_index(h) == i,
    1063                 "wrong index in string table");
    1064       actual_count++;
    1065     }
    1066   }
    1067   if (the_table()->number_of_entries()!=actual_count) {
    1068     tty->print("StringTable assert failure: number_of_entries()!=actual_count [%d!=%d]\n", the_table()->number_of_entries(), actual_count);
    1069   }
    1070   guarantee(the_table()->number_of_entries() == actual_count, "should be equal");
    1071 }
    1072
    1073 StringTable::VerifyRetTypes StringTable::compare_entries(
    1074                                       int bkt1, int e_cnt1,
    1075                                       HashtableEntry<oop, mtSymbol>* e_ptr1,
    1076                                       int bkt2, int e_cnt2,
    1077                                       HashtableEntry<oop, mtSymbol>* e_ptr2) {
    1078   // These entries are sanity checked by verify_and_compare_entries()
    1079   // before this function is called.
    1080   oop str1 = e_ptr1->literal();
    1081   oop str2 = e_ptr2->literal();
    1082
    1083   if (str1 == str2) {
    1084     tty->print_cr("ERROR: identical oop values (0x" PTR_FORMAT ") "
    1085                   "in entry @ bucket[%d][%d] and entry @ bucket[%d][%d]",
    1086                   (void *)str1, bkt1, e_cnt1, bkt2, e_cnt2);
    1087     return _verify_fail_continue;
    1088   }
    1089
    1090   if (java_lang_String::equals(str1, str2)) {
    1091     tty->print_cr("ERROR: identical String values in entry @ "
    1092                   "bucket[%d][%d] and entry @ bucket[%d][%d]",
    1093                   bkt1, e_cnt1, bkt2, e_cnt2);
    1094     return _verify_fail_continue;
    1095   }
    1096
    1097   return _verify_pass;
    1098 }
    1099
    1100 StringTable::VerifyRetTypes StringTable::verify_entry(int bkt, int e_cnt,
    1101                                       HashtableEntry<oop, mtSymbol>* e_ptr,
    1102                                       StringTable::VerifyMesgModes mesg_mode) {
    1103
    1104   VerifyRetTypes ret = _verify_pass;  // be optimistic
    1105
    1106   oop str = e_ptr->literal();
    1107   if (str == NULL) {
    1108     if (mesg_mode == _verify_with_mesgs) {
    1109       tty->print_cr("ERROR: NULL oop value in entry @ bucket[%d][%d]", bkt,
    1110                     e_cnt);
    1111     }
    1112     // NULL oop means no more verifications are possible
    1113     return _verify_fail_done;
    1114   }
    1115
    1116   if (str->klass() != SystemDictionary::String_klass()) {
    1117     if (mesg_mode == _verify_with_mesgs) {
    1118       tty->print_cr("ERROR: oop is not a String in entry @ bucket[%d][%d]",
    1119                     bkt, e_cnt);
    1120     }
    1121     // not a String means no more verifications are possible
    1122     return _verify_fail_done;
    1123   }
    1124
    1125   unsigned int h = java_lang_String::hash_string(str);
    1126   if (e_ptr->hash() != h) {
    1127     if (mesg_mode == _verify_with_mesgs) {
    1128       tty->print_cr("ERROR: broken hash value in entry @ bucket[%d][%d], "
    1129                     "bkt_hash=%d, str_hash=%d", bkt, e_cnt, e_ptr->hash(), h);
    1130     }
    1131     ret = _verify_fail_continue;
    1132   }
    1133
    1134   if (the_table()->hash_to_index(h) != bkt) {
    1135     if (mesg_mode == _verify_with_mesgs) {
    1136       tty->print_cr("ERROR: wrong index value for entry @ bucket[%d][%d], "
    1137                     "str_hash=%d, hash_to_index=%d", bkt, e_cnt, h,
    1138                     the_table()->hash_to_index(h));
    1139     }
    1140     ret = _verify_fail_continue;
    1141   }
    1142
    1143   return ret;
    1144 }
    1145
    1146 // See StringTable::verify() above for the quick verification that is
    1147 // part of Universe::verify(). This verification is exhaustive and
    1148 // reports on every issue that is found. StringTable::verify() only
    1149 // reports on the first issue that is found.
    1150 //
    1151 // StringTable::verify_entry() checks:
    1152 // - oop value != NULL (same as verify())
    1153 // - oop value is a String
    1154 // - hash(String) == hash in entry (same as verify())
    1155 // - index for hash == index of entry (same as verify())
    1156 //
    1157 // StringTable::compare_entries() checks:
    1158 // - oops are unique across all entries
    1159 // - String values are unique across all entries
    1160 //
    1161 int StringTable::verify_and_compare_entries() {
    1162   assert(StringTable_lock->is_locked(), "sanity check");
    1163
    1164   int  fail_cnt = 0;
    1165
    1166   // first, verify all the entries individually:
    1167   for (int bkt = 0; bkt < the_table()->table_size(); bkt++) {
    1168     HashtableEntry<oop, mtSymbol>* e_ptr = the_table()->bucket(bkt);
    1169     for (int e_cnt = 0; e_ptr != NULL; e_ptr = e_ptr->next(), e_cnt++) {
    1170       VerifyRetTypes ret = verify_entry(bkt, e_cnt, e_ptr, _verify_with_mesgs);
    1171       if (ret != _verify_pass) {
    1172         fail_cnt++;
    1173       }
    1174     }
    1175   }
    1176
    1177   // Optimization: if the above check did not find any failures, then
    1178   // the comparison loop below does not need to call verify_entry()
    1179   // before calling compare_entries(). If there were failures, then we
    1180   // have to call verify_entry() to see if the entry can be passed to
    1181   // compare_entries() safely. When we call verify_entry() in the loop
    1182   // below, we do so quietly to void duplicate messages and we don't
    1183   // increment fail_cnt because the failures have already been counted.
    1184   bool need_entry_verify = (fail_cnt != 0);
    1185
    1186   // second, verify all entries relative to each other:
    1187   for (int bkt1 = 0; bkt1 < the_table()->table_size(); bkt1++) {
    1188     HashtableEntry<oop, mtSymbol>* e_ptr1 = the_table()->bucket(bkt1);
    1189     for (int e_cnt1 = 0; e_ptr1 != NULL; e_ptr1 = e_ptr1->next(), e_cnt1++) {
    1190       if (need_entry_verify) {
    1191         VerifyRetTypes ret = verify_entry(bkt1, e_cnt1, e_ptr1,
    1192                                           _verify_quietly);
    1193         if (ret == _verify_fail_done) {
    1194           // cannot use the current entry to compare against other entries
    1195           continue;
    1196         }
    1197       }
    1198
    1199       for (int bkt2 = bkt1; bkt2 < the_table()->table_size(); bkt2++) {
    1200         HashtableEntry<oop, mtSymbol>* e_ptr2 = the_table()->bucket(bkt2);
    1201         int e_cnt2;
    1202         for (e_cnt2 = 0; e_ptr2 != NULL; e_ptr2 = e_ptr2->next(), e_cnt2++) {
    1203           if (bkt1 == bkt2 && e_cnt2 <= e_cnt1) {
    1204             // skip the entries up to and including the one that
    1205             // we're comparing against
    1206             continue;
    1207           }
    1208
    1209           if (need_entry_verify) {
    1210             VerifyRetTypes ret = verify_entry(bkt2, e_cnt2, e_ptr2,
    1211                                               _verify_quietly);
    1212             if (ret == _verify_fail_done) {
    1213               // cannot compare against this entry
    1214               continue;
    1215             }
    1216           }
    1217
    1218           // compare two entries, report and count any failures:
    1219           if (compare_entries(bkt1, e_cnt1, e_ptr1, bkt2, e_cnt2, e_ptr2)
    1220               != _verify_pass) {
    1221             fail_cnt++;
    1222           }
    1223         }
    1224       }
    1225     }
    1226   }
    1227   return fail_cnt;
    1228 }
    1229
    1230 // Create a new table and using alternate hash code, populate the new table
    1231 // with the existing strings.   Set flag to use the alternate hash code afterwards.
    1232 void StringTable::rehash_table() {
    1233   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
    1234   // This should never happen with -Xshare:dump but it might in testing mode.
    1235   if (DumpSharedSpaces) return;
    1236   StringTable* new_table = new StringTable();
    1237
    1238   // Rehash the table
    1239   the_table()->move_to(new_table);
    1240
    1241   // Delete the table and buckets (entries are reused in new table).
    1242   delete _the_table;
    1243   // Don't check if we need rehashing until the table gets unbalanced again.
    1244   // Then rehash with a new global seed.
    1245   _needs_rehashing = false;
    1246   _the_table = new_table;
    1247 }