src/share/vm/classfile/symbolTable.cpp
Index Unified diffs Context diffs Sdiffs Wdiffs Patch New Old Previous File Next File

## src/share/vm/classfile/symbolTable.cpp

Print this page

      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   for (int i = start_idx; i < end_idx; ++i) {
     101     HashtableEntry<Symbol*, mtSymbol>** p = the_table()->bucket_addr(i);
     102     HashtableEntry<Symbol*, mtSymbol>* entry = the_table()->bucket(i);
     103     while (entry != NULL) {
     104       // Shared entries are normally at the end of the bucket and if we run into
     105       // a shared entry, then there is nothing more to remove. However, if we
     106       // have rehashed the table, then the shared entries are no longer at the
     107       // end of the bucket.
     108       if (entry->is_shared() && !use_alternate_hashcode()) {
     109         break;
     110       }
     111       Symbol* s = entry->literal();
     112       (*memory_total) += s->size();
     113       (*processed)++;
     114       assert(s != NULL, "just checking");
     115       // If reference count is zero, remove.
     116       if (s->refcount() == 0) {
     117         assert(!entry->is_shared(), "shared entries should be kept live");
     118         delete s;
     119         (*removed)++;
     175   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
     176   // This should never happen with -Xshare:dump but it might in testing mode.
     177   if (DumpSharedSpaces) return;
     178   // Create a new symbol table
     179   SymbolTable* new_table = new SymbolTable();
     180
     181   the_table()->move_to(new_table);
     182
     183   // Delete the table and buckets (entries are reused in new table).
     184   delete _the_table;
     185   // Don't check if we need rehashing until the table gets unbalanced again.
     186   // Then rehash with a new global seed.
     187   _needs_rehashing = false;
     188   _the_table = new_table;
     189 }
     190
     191 // Lookup a symbol in a bucket.
     192
     193 Symbol* SymbolTable::lookup(int index, const char* name,
     194                               int len, unsigned int hash) {
     195   int count = 0;

     196   for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) {
     197     count++;  // count all entries in this bucket, not just ones with same hash
     198     if (e->hash() == hash) {
     199       Symbol* sym = e->literal();
     200       if (sym->equals(name, len)) {
     201         // something is referencing this symbol now.
     202         sym->increment_refcount();

     203         return sym;
     204       }
     205     }
     206   }
     207   // If the bucket size is too deep check if this hash code is insufficient.
     208   if (count >= rehash_count && !needs_rehashing()) {
     209     _needs_rehashing = check_rehash_table(count);
     210   }

     211   return NULL;
     212 }
     213
     214 // Pick hashing algorithm.
     215 unsigned int SymbolTable::hash_symbol(const char* s, int len) {
     216   return use_alternate_hashcode() ?
     217            AltHashing::murmur3_32(seed(), (const jbyte*)s, len) :
     218            java_lang_String::hash_code(s, len);
     219 }
     220
     221
     222 // We take care not to be blocking while holding the
     223 // SymbolTable_lock. Otherwise, the system might deadlock, since the
     224 // symboltable is used during compilation (VM_thread) The lock free
     225 // synchronization is simplified by the fact that we do not delete
     226 // entries in the symbol table during normal execution (only during
     227 // safepoints).
     228
     229 Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) {
     230   unsigned int hashValue = hash_symbol(name, len);
     362     }
     363   }
     364 }
     365
     366 Symbol* SymbolTable::new_permanent_symbol(const char* name, TRAPS) {
     367   unsigned int hash;
     368   Symbol* result = SymbolTable::lookup_only((char*)name, (int)strlen(name), hash);
     369   if (result != NULL) {
     370     return result;
     371   }
     372   // Grab SymbolTable_lock first.
     373   MutexLocker ml(SymbolTable_lock, THREAD);
     374
     375   SymbolTable* table = the_table();
     376   int index = table->hash_to_index(hash);
     377   return table->basic_add(index, (u1*)name, (int)strlen(name), hash, false, THREAD);
     378 }
     379
     380 Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len,
     381                                unsigned int hashValue_arg, bool c_heap, TRAPS) {

     382   assert(!Universe::heap()->is_in_reserved(name),
     383          "proposed name of symbol must be stable");
     384
     385   // Don't allow symbols to be created which cannot fit in a Symbol*.
     386   if (len > Symbol::max_length()) {
     387     THROW_MSG_0(vmSymbols::java_lang_InternalError(),
     388                 "name is too long to represent");
     389   }
     390
     391   // Cannot hit a safepoint in this function because the "this" pointer can move.
     392   No_Safepoint_Verifier nsv;
     393
     394   // Check if the symbol table has been rehashed, if so, need to recalculate
     395   // the hash value and index.
     396   unsigned int hashValue;
     397   int index;
     398   if (use_alternate_hashcode()) {
     399     hashValue = hash_symbol((const char*)name, len);
     400     index = hash_to_index(hashValue);
     401   } else {
     402     hashValue = hashValue_arg;
     403     index = index_arg;
     404   }
     405
     406   // Since look-up was done lock-free, we need to check if another
     407   // thread beat us in the race to insert the symbol.
     408   Symbol* test = lookup(index, (char*)name, len, hashValue);
     409   if (test != NULL) {
     410     // A race occurred and another thread introduced the symbol.
     411     assert(test->refcount() != 0, "lookup should have incremented the count");
     412     return test;
     413   }
     414
     415   // Create a new symbol.
     416   Symbol* sym = allocate_symbol(name, len, c_heap, CHECK_NULL);
     417   assert(sym->equals((char*)name, len), "symbol must be properly initialized");
     418
     419   HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
     420   add_entry(index, entry);

     421   return sym;
     422 }
     423
     424 // This version of basic_add adds symbols in batch from the constant pool
     425 // parsing.
     426 bool SymbolTable::basic_add(ClassLoaderData* loader_data, constantPoolHandle cp,
     427                             int names_count,
     428                             const char** names, int* lengths,
     429                             int* cp_indices, unsigned int* hashValues,
     430                             TRAPS) {

     431
     432   // Check symbol names are not too long.  If any are too long, don't add any.
     433   for (int i = 0; i< names_count; i++) {
     434     if (lengths[i] > Symbol::max_length()) {
     435       THROW_MSG_0(vmSymbols::java_lang_InternalError(),
     436                   "name is too long to represent");
     437     }
     438   }
     439
     440   // Cannot hit a safepoint in this function because the "this" pointer can move.
     441   No_Safepoint_Verifier nsv;
     442
     443   for (int i=0; i<names_count; i++) {
     444     // Check if the symbol table has been rehashed, if so, need to recalculate
     445     // the hash value.
     446     unsigned int hashValue;
     447     if (use_alternate_hashcode()) {
     448       hashValue = hash_symbol(names[i], lengths[i]);
     449     } else {
     450       hashValue = hashValues[i];
     451     }
     452     // Since look-up was done lock-free, we need to check if another
     453     // thread beat us in the race to insert the symbol.
     454     int index = hash_to_index(hashValue);
     455     Symbol* test = lookup(index, names[i], lengths[i], hashValue);
     456     if (test != NULL) {
     457       // A race occurred and another thread introduced the symbol, this one
     458       // will be dropped and collected. Use test instead.
     459       cp->symbol_at_put(cp_indices[i], test);
     460       assert(test->refcount() != 0, "lookup should have incremented the count");
     461     } else {
     462       // Create a new symbol.  The null class loader is never unloaded so these
     463       // are allocated specially in a permanent arena.
     464       bool c_heap = !loader_data->is_the_null_class_loader_data();
     465       Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], c_heap, CHECK_(false));
     466       assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized");  // why wouldn't it be???
     467       HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
     468       add_entry(index, entry);
     469       cp->symbol_at_put(cp_indices[i], sym);

     470     }
     471   }
     472   return true;
     473 }
     474
     475
     476 void SymbolTable::verify() {

     477   for (int i = 0; i < the_table()->table_size(); ++i) {
     478     HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
     479     for ( ; p != NULL; p = p->next()) {
     480       Symbol* s = (Symbol*)(p->literal());
     481       guarantee(s != NULL, "symbol is NULL");
     482       unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length());
     483       guarantee(p->hash() == h, "broken hash in symbol table entry");
     484       guarantee(the_table()->hash_to_index(h) == i,
     485                 "wrong index in symbol table");

     486     }
     487   }

     488 }
     489
     490 void SymbolTable::dump(outputStream* st) {
     491   the_table()->dump_table(st, "SymbolTable");
     492 }
     493
     494
     495 //---------------------------------------------------------------------------
     496 // Non-product code
     497
     498 #ifndef PRODUCT
     499
     500 void SymbolTable::print_histogram() {
     501   MutexLocker ml(SymbolTable_lock);
     502   const int results_length = 100;
     503   int results[results_length];
     504   int i,j;
     505
     506   // initialize results to zero
     507   for (j = 0; j < results_length; j++) {
     508     results[j] = 0;
     509   }
     510
     511   int total = 0;
     512   int max_symbols = 0;
     513   int out_of_range = 0;
     514   int memory_total = 0;
     515   int count = 0;
     516   for (i = 0; i < the_table()->table_size(); i++) {
     517     HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
     518     for ( ; p != NULL; p = p->next()) {
     519       memory_total += p->literal()->size();
     629   void set_region(const void* region) { _region = (address) region; }
     630 };
     631 #endif
     632
     633
     634 // --------------------------------------------------------------------------
     635 StringTable* StringTable::_the_table = NULL;
     636
     637 bool StringTable::_needs_rehashing = false;
     638
     639 volatile int StringTable::_parallel_claimed_idx = 0;
     640
     641 // Pick hashing algorithm
     642 unsigned int StringTable::hash_string(const jchar* s, int len) {
     643   return use_alternate_hashcode() ? AltHashing::murmur3_32(seed(), s, len) :
     644                                     java_lang_String::hash_code(s, len);
     645 }
     646
     647 oop StringTable::lookup(int index, jchar* name,
     648                         int len, unsigned int hash) {
     649   int count = 0;

     650   for (HashtableEntry<oop, mtSymbol>* l = bucket(index); l != NULL; l = l->next()) {
     651     count++;
     652     if (l->hash() == hash) {
     653       if (java_lang_String::equals(l->literal(), name, len)) {

     654         return l->literal();
     655       }
     656     }
     657   }
     658   // If the bucket size is too deep check if this hash code is insufficient.
     659   if (count >= rehash_count && !needs_rehashing()) {
     660     _needs_rehashing = check_rehash_table(count);
     661   }

     662   return NULL;
     663 }
     664
     665
     666 oop StringTable::basic_add(int index_arg, Handle string, jchar* name,
     667                            int len, unsigned int hashValue_arg, TRAPS) {
     668

     669   assert(java_lang_String::equals(string(), name, len),
     670          "string must be properly initialized");
     671   // Cannot hit a safepoint in this function because the "this" pointer can move.
     672   No_Safepoint_Verifier nsv;
     673
     674   // Check if the symbol table has been rehashed, if so, need to recalculate
     675   // the hash value and index before second lookup.
     676   unsigned int hashValue;
     677   int index;
     678   if (use_alternate_hashcode()) {
     679     hashValue = hash_string(name, len);
     680     index = hash_to_index(hashValue);
     681   } else {
     682     hashValue = hashValue_arg;
     683     index = index_arg;
     684   }
     685
     686   // Since look-up was done lock-free, we need to check if another
     687   // thread beat us in the race to insert the symbol.
     688
     689   oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int)
     690   if (test != NULL) {
     691     // Entry already added
     692     return test;
     693   }
     694
     695   HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string());
     696   add_entry(index, entry);

     697   return string();
     698 }
     699
     700
     701 oop StringTable::lookup(Symbol* symbol) {
     702   ResourceMark rm;
     703   int length;
     704   jchar* chars = symbol->as_unicode(length);
     705   return lookup(chars, length);
     706 }
     707
     708 // Tell the GC that this string was looked up in the StringTable.
     709 static void ensure_string_alive(oop string) {
     710   // A lookup in the StringTable could return an object that was previously
     711   // considered dead. The SATB part of G1 needs to get notified about this
     712   // potential resurrection, otherwise the marking might not find the object.
     713 #if INCLUDE_ALL_GCS
     714   if (UseG1GC && string != NULL) {
     715     G1SATBCardTableModRefBS::enqueue(string);
     716   }
     867          err_msg("Index ordering: start_idx=" INT32_FORMAT", end_idx=" INT32_FORMAT,
     868                  start_idx, end_idx));
     869
     870   for (int i = start_idx; i < end_idx; ++i) {
     871     HashtableEntry<oop, mtSymbol>** p = the_table()->bucket_addr(i);
     872     HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);
     873     while (entry != NULL) {
     874       assert(!entry->is_shared(), "CDS not used for the StringTable");
     875
     876       if (is_alive->do_object_b(entry->literal())) {
     877         if (f != NULL) {
     878           f->do_oop((oop*)entry->literal_addr());
     879         }
     880         p = entry->next_addr();
     881       } else {
     882         *p = entry->next();
     883         the_table()->free_entry(entry);
     884         (*removed)++;
     885       }
     886       (*processed)++;

     887       entry = *p;
     888     }
     889   }
     890 }
     891
     892 void StringTable::oops_do(OopClosure* f) {
     893   buckets_oops_do(f, 0, the_table()->table_size());
     894 }
     895
     896 void StringTable::possibly_parallel_oops_do(OopClosure* f) {
     897   const int limit = the_table()->table_size();
     898
     899   for (;;) {
     900     // Grab next set of buckets to scan
     901     int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;
     902     if (start_idx >= limit) {
     903       // End of table
     904       break;
     905     }
     906
     907     int end_idx = MIN2(limit, start_idx + ClaimChunkSize);
     908     buckets_oops_do(f, start_idx, end_idx);
     909   }
     910 }
     911
     912 // This verification is part of Universe::verify() and needs to be quick.
     913 // See StringTable::verify_and_compare() below for exhaustive verification.
     914 void StringTable::verify() {

     915   for (int i = 0; i < the_table()->table_size(); ++i) {
     916     HashtableEntry<oop, mtSymbol>* p = the_table()->bucket(i);
     917     for ( ; p != NULL; p = p->next()) {
     918       oop s = p->literal();
     919       guarantee(s != NULL, "interned string is NULL");
     920       unsigned int h = java_lang_String::hash_string(s);
     921       guarantee(p->hash() == h, "broken hash in string table entry");

     922       guarantee(the_table()->hash_to_index(h) == i,
     923                 "wrong index in string table");

     924     }
     925   }
     926 }
     927
     928 void StringTable::dump(outputStream* st) {
     929   the_table()->dump_table(st, "StringTable");
     930 }
     931
     932 StringTable::VerifyRetTypes StringTable::compare_entries(
     933                                       int bkt1, int e_cnt1,
     934                                       HashtableEntry<oop, mtSymbol>* e_ptr1,
     935                                       int bkt2, int e_cnt2,
     936                                       HashtableEntry<oop, mtSymbol>* e_ptr2) {
     937   // These entries are sanity checked by verify_and_compare_entries()
     938   // before this function is called.
     939   oop str1 = e_ptr1->literal();
     940   oop str2 = e_ptr2->literal();
     941
     942   if (str1 == str2) {
     943     tty->print_cr("ERROR: identical oop values (0x" PTR_FORMAT ") "
     944                   "in entry @ bucket[%d][%d] and entry @ bucket[%d][%d]",
     945                   (void *)str1, bkt1, e_cnt1, bkt2, e_cnt2);
     946     return _verify_fail_continue;
     947   }
     948
     949   if (java_lang_String::equals(str1, str2)) {
      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)++;
     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);
     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();
     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   }
     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)) {

src/share/vm/classfile/symbolTable.cpp
Index Unified diffs Context diffs Sdiffs Wdiffs Patch New Old Previous File Next File