# HG changeset patch
# User coleenp
# Date 1340718747 14400
# Node ID faa8d30306e896ba98ba9d9d7b2a42cf07151255
# Parent  409abd9115421ef64519df7eaf0369682d29780b
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
Summary: Cannot delete _buckets and HashtableEntries in shared space (CDS)
Reviewed-by: acorn, kvn, dlong, dcubed, kamg

diff -r 409abd911542 -r faa8d30306e8 src/share/vm/classfile/symbolTable.cpp
--- a/src/share/vm/classfile/symbolTable.cpp	Fri Jun 22 13:35:02 2012 -0700
+++ b/src/share/vm/classfile/symbolTable.cpp	Tue Jun 26 09:52:27 2012 -0400
@@ -43,33 +43,13 @@
 jint SymbolTable::_seed = 0;
 
 Symbol* SymbolTable::allocate_symbol(const u1* name, int len, TRAPS) {
-  // Don't allow symbols to be created which cannot fit in a Symbol*.
-  if (len > Symbol::max_length()) {
-    THROW_MSG_0(vmSymbols::java_lang_InternalError(),
-                "name is too long to represent");
-  }
+  assert (len <= Symbol::max_length(), "should be checked by caller");
+
   Symbol* sym = new (len) Symbol(name, len);
   assert(sym != NULL, "new should call vm_exit_out_of_memory if C_HEAP is exhausted");
   return sym;
 }
 
-bool SymbolTable::allocate_symbols(int names_count, const u1** names,
-                                   int* lengths, Symbol** syms, TRAPS) {
-  for (int i = 0; i< names_count; i++) {
-    if (lengths[i] > Symbol::max_length()) {
-      THROW_MSG_0(vmSymbols::java_lang_InternalError(),
-                  "name is too long to represent");
-    }
-  }
-
-  for (int i = 0; i< names_count; i++) {
-    int len = lengths[i];
-    syms[i] = new (len) Symbol(names[i], len);
-    assert(syms[i] != NULL, "new should call vm_exit_out_of_memory if "
-                            "C_HEAP is exhausted");
-  }
-  return true;
-}
 
 // Call function for all symbols in the symbol table.
 void SymbolTable::symbols_do(SymbolClosure *cl) {
@@ -94,9 +74,14 @@
   int total = 0;
   size_t memory_total = 0;
   for (int i = 0; i < the_table()->table_size(); ++i) {
-    for (HashtableEntry<Symbol*>** p = the_table()->bucket_addr(i); *p != NULL; ) {
-      HashtableEntry<Symbol*>* entry = *p;
-      if (entry->is_shared()) {
+    HashtableEntry<Symbol*>** p = the_table()->bucket_addr(i);
+    HashtableEntry<Symbol*>* entry = the_table()->bucket(i);
+    while (entry != NULL) {
+      // Shared entries are normally at the end of the bucket and if we run into
+      // a shared entry, then there is nothing more to remove. However, if we
+      // have rehashed the table, then the shared entries are no longer at the
+      // end of the bucket.
+      if (entry->is_shared() && !use_alternate_hashcode()) {
         break;
       }
       Symbol* s = entry->literal();
@@ -105,6 +90,7 @@
       assert(s != NULL, "just checking");
       // If reference count is zero, remove.
       if (s->refcount() == 0) {
+        assert(!entry->is_shared(), "shared entries should be kept live");
         delete s;
         removed++;
         *p = entry->next();
@@ -112,6 +98,8 @@
       } else {
         p = entry->next_addr();
       }
+      // get next entry
+      entry = (HashtableEntry<Symbol*>*)HashtableEntry<Symbol*>::make_ptr(*p);
     }
   }
   symbols_removed += removed;
@@ -134,7 +122,8 @@
 // with the existing strings.   Set flag to use the alternate hash code afterwards.
 void SymbolTable::rehash_table() {
   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
-  assert(!DumpSharedSpaces, "this should never happen with -Xshare:dump");
+  // This should never happen with -Xshare:dump but it might in testing mode.
+  if (DumpSharedSpaces) return;
   // Create a new symbol table
   SymbolTable* new_table = new SymbolTable();
 
@@ -175,12 +164,11 @@
   return NULL;
 }
 
-// Pick hashing algorithm, but return value already given if not using a new
-// hash algorithm.
-unsigned int SymbolTable::hash_symbol(const char* s, int len, unsigned int hashValue) {
+// Pick hashing algorithm.
+unsigned int SymbolTable::hash_symbol(const char* s, int len) {
   return use_alternate_hashcode() ?
            AltHashing::murmur3_32(seed(), (const jbyte*)s, len) :
-           (hashValue != 0 ? hashValue : java_lang_String::to_hash(s, len));
+           java_lang_String::to_hash(s, len);
 }
 
 
@@ -200,6 +188,9 @@
   // Found
   if (s != NULL) return s;
 
+  // Grab SymbolTable_lock first.
+  MutexLocker ml(SymbolTable_lock, THREAD);
+
   // Otherwise, add to symbol to table
   return the_table()->basic_add(index, (u1*)name, len, hashValue, CHECK_NULL);
 }
@@ -237,6 +228,9 @@
   // We can't include the code in No_Safepoint_Verifier because of the
   // ResourceMark.
 
+  // Allocation must be done before grabbing the SymbolTable_lock lock
+  MutexLocker ml(SymbolTable_lock, THREAD);
+
   return the_table()->basic_add(index, (u1*)buffer, len, hashValue, CHECK_NULL);
 }
 
@@ -304,6 +298,9 @@
 void SymbolTable::add(constantPoolHandle cp, int names_count,
                       const char** names, int* lengths, int* cp_indices,
                       unsigned int* hashValues, TRAPS) {
+  // Grab SymbolTable_lock first.
+  MutexLocker ml(SymbolTable_lock, THREAD);
+
   SymbolTable* table = the_table();
   bool added = table->basic_add(cp, names_count, names, lengths,
                                 cp_indices, hashValues, CHECK);
@@ -318,38 +315,47 @@
   }
 }
 
-Symbol* SymbolTable::basic_add(int index, u1 *name, int len,
-                                 unsigned int hashValue_arg, TRAPS) {
+Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len,
+                               unsigned int hashValue_arg, TRAPS) {
   assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(),
          "proposed name of symbol must be stable");
 
-  // We assume that lookup() has been called already, that it failed,
-  // and symbol was not found.  We create the symbol here.
-  Symbol* sym = allocate_symbol(name, len, CHECK_NULL);
+  // Don't allow symbols to be created which cannot fit in a Symbol*.
+  if (len > Symbol::max_length()) {
+    THROW_MSG_0(vmSymbols::java_lang_InternalError(),
+                "name is too long to represent");
+  }
 
-  // Allocation must be done before grabbing the SymbolTable_lock lock
-  MutexLocker ml(SymbolTable_lock, THREAD);
-
-  assert(sym->equals((char*)name, len), "symbol must be properly initialized");
+  // Cannot hit a safepoint in this function because the "this" pointer can move.
+  No_Safepoint_Verifier nsv;
 
   // Check if the symbol table has been rehashed, if so, need to recalculate
-  // the hash value.
-  unsigned int hashValue = hash_symbol((const char*)name, len, hashValue_arg);
+  // the hash value and index.
+  unsigned int hashValue;
+  int index;
+  if (use_alternate_hashcode()) {
+    hashValue = hash_symbol((const char*)name, len);
+    index = hash_to_index(hashValue);
+  } else {
+    hashValue = hashValue_arg;
+    index = index_arg;
+  }
 
   // Since look-up was done lock-free, we need to check if another
   // thread beat us in the race to insert the symbol.
-
   Symbol* test = lookup(index, (char*)name, len, hashValue);
   if (test != NULL) {
-    // A race occurred and another thread introduced the symbol, this one
-    // will be dropped and collected.
-    delete sym;
+    // A race occurred and another thread introduced the symbol.
     assert(test->refcount() != 0, "lookup should have incremented the count");
     return test;
   }
 
+  // Create a new symbol.
+  Symbol* sym = allocate_symbol(name, len, CHECK_NULL);
+  assert(sym->equals((char*)name, len), "symbol must be properly initialized");
+
   HashtableEntry<Symbol*>* entry = new_entry(hashValue, sym);
-  sym->increment_refcount();
+  sym->increment_refcount();  // increment refcount in external hashtable
   add_entry(index, entry);
   return sym;
 }
@@ -358,21 +364,27 @@
                             const char** names, int* lengths,
                             int* cp_indices, unsigned int* hashValues,
                             TRAPS) {
-  Symbol* syms[symbol_alloc_batch_size];
-  bool allocated = allocate_symbols(names_count, (const u1**)names, lengths,
-                                    syms, CHECK_false);
-  if (!allocated) {
-    return false;
+
+  // Check symbol names are not too long.  If any are too long, don't add any.
+  for (int i = 0; i< names_count; i++) {
+    if (lengths[i] > Symbol::max_length()) {
+      THROW_MSG_0(vmSymbols::java_lang_InternalError(),
+                  "name is too long to represent");
+    }
   }
 
-  // Allocation must be done before grabbing the SymbolTable_lock lock
-  MutexLocker ml(SymbolTable_lock, THREAD);
+  // Cannot hit a safepoint in this function because the "this" pointer can move.
+  No_Safepoint_Verifier nsv;
 
   for (int i=0; i<names_count; i++) {
-    assert(syms[i]->equals(names[i], lengths[i]), "symbol must be properly initialized");
     // Check if the symbol table has been rehashed, if so, need to recalculate
     // the hash value.
-    unsigned int hashValue = hash_symbol(names[i], lengths[i], hashValues[i]);
+    unsigned int hashValue;
+    if (use_alternate_hashcode()) {
+      hashValue = hash_symbol(names[i], lengths[i]);
+    } else {
+      hashValue = hashValues[i];
+    }
     // Since look-up was done lock-free, we need to check if another
     // thread beat us in the race to insert the symbol.
     int index = hash_to_index(hashValue);
@@ -382,9 +394,9 @@
       // will be dropped and collected. Use test instead.
       cp->symbol_at_put(cp_indices[i], test);
       assert(test->refcount() != 0, "lookup should have incremented the count");
-      delete syms[i];
     } else {
-      Symbol* sym = syms[i];
+      Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], CHECK_(false));
+      assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized");  // why wouldn't it be???
       HashtableEntry<Symbol*>* entry = new_entry(hashValue, sym);
       sym->increment_refcount();  // increment refcount in external hashtable
       add_entry(index, entry);
@@ -573,9 +585,9 @@
 jint StringTable::_seed = 0;
 
 // Pick hashing algorithm
-unsigned int StringTable::hash_string(const jchar* s, int len, unsigned int hashValue) {
+unsigned int StringTable::hash_string(const jchar* s, int len) {
   return use_alternate_hashcode() ? AltHashing::murmur3_32(seed(), s, len) :
-            (hashValue != 0 ? hashValue : java_lang_String::to_hash(s, len));
+                                    java_lang_String::to_hash(s, len);
 }
 
 oop StringTable::lookup(int index, jchar* name,
@@ -597,29 +609,25 @@
 }
 
 
-oop StringTable::basic_add(int index, Handle string_or_null, jchar* name,
+oop StringTable::basic_add(int index_arg, Handle string, jchar* name,
                            int len, unsigned int hashValue_arg, TRAPS) {
-  debug_only(StableMemoryChecker smc(name, len * sizeof(name[0])));
-  assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(),
-         "proposed name of symbol must be stable");
-
-  Handle string;
-  // try to reuse the string if possible
-  if (!string_or_null.is_null() && (!JavaObjectsInPerm || string_or_null()->is_perm())) {
-    string = string_or_null;
-  } else {
-    string = java_lang_String::create_tenured_from_unicode(name, len, CHECK_NULL);
-  }
-
-  // Allocation must be done before grapping the SymbolTable_lock lock
-  MutexLocker ml(StringTable_lock, THREAD);
 
   assert(java_lang_String::equals(string(), name, len),
          "string must be properly initialized");
+  // Cannot hit a safepoint in this function because the "this" pointer can move.
+  No_Safepoint_Verifier nsv;
 
   // Check if the symbol table has been rehashed, if so, need to recalculate
-  // the hash value before second lookup.
-  unsigned int hashValue = hash_string(name, len, hashValue_arg);
+  // the hash value and index before second lookup.
+  unsigned int hashValue;
+  int index;
+  if (use_alternate_hashcode()) {
+    hashValue = hash_string(name, len);
+    index = hash_to_index(hashValue);
+  } else {
+    hashValue = hashValue_arg;
+    index = index_arg;
+  }
 
   // Since look-up was done lock-free, we need to check if another
   // thread beat us in the race to insert the symbol.
@@ -650,13 +658,29 @@
                         int len, TRAPS) {
   unsigned int hashValue = hash_string(name, len);
   int index = the_table()->hash_to_index(hashValue);
-  oop string = the_table()->lookup(index, name, len, hashValue);
+  oop found_string = the_table()->lookup(index, name, len, hashValue);
 
   // Found
-  if (string != NULL) return string;
+  if (found_string != NULL) return found_string;
+
+  debug_only(StableMemoryChecker smc(name, len * sizeof(name[0])));
+  assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(),
+         "proposed name of symbol must be stable");
+
+  Handle string;
+  // try to reuse the string if possible
+  if (!string_or_null.is_null() && (!JavaObjectsInPerm || string_or_null()->is_perm())) {
+    string = string_or_null;
+  } else {
+    string = java_lang_String::create_tenured_from_unicode(name, len, CHECK_NULL);
+  }
+
+  // Grab the StringTable_lock before getting the_table() because it could
+  // change at safepoint.
+  MutexLocker ml(StringTable_lock, THREAD);
 
   // Otherwise, add to symbol to table
-  return the_table()->basic_add(index, string_or_null, name, len,
+  return the_table()->basic_add(index, string, name, len,
                                 hashValue, CHECK_NULL);
 }
 
@@ -699,18 +723,24 @@
   // entries at a safepoint.
   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
   for (int i = 0; i < the_table()->table_size(); ++i) {
-    for (HashtableEntry<oop>** p = the_table()->bucket_addr(i); *p != NULL; ) {
-      HashtableEntry<oop>* entry = *p;
-      if (entry->is_shared()) {
+    HashtableEntry<oop>** p = the_table()->bucket_addr(i);
+    HashtableEntry<oop>* entry = the_table()->bucket(i);
+    while (entry != NULL) {
+      // Shared entries are normally at the end of the bucket and if we run into
+      // a shared entry, then there is nothing more to remove. However, if we
+      // have rehashed the table, then the shared entries are no longer at the
+      // end of the bucket.
+      if (entry->is_shared() && !use_alternate_hashcode()) {
         break;
       }
       assert(entry->literal() != NULL, "just checking");
-      if (is_alive->do_object_b(entry->literal())) {
+      if (entry->is_shared() || is_alive->do_object_b(entry->literal())) {
         p = entry->next_addr();
       } else {
         *p = entry->next();
         the_table()->free_entry(entry);
       }
+      entry = (HashtableEntry<oop>*)HashtableEntry<oop>::make_ptr(*p);
     }
   }
 }
@@ -781,7 +811,8 @@
 // with the existing strings.   Set flag to use the alternate hash code afterwards.
 void StringTable::rehash_table() {
   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
-  assert(!DumpSharedSpaces, "this should never happen with -Xshare:dump");
+  // This should never happen with -Xshare:dump but it might in testing mode.
+  if (DumpSharedSpaces) return;
   StringTable* new_table = new StringTable();
 
   // Initialize new global seed for hashing.
diff -r 409abd911542 -r faa8d30306e8 src/share/vm/classfile/symbolTable.hpp
--- a/src/share/vm/classfile/symbolTable.hpp	Fri Jun 22 13:35:02 2012 -0700
+++ b/src/share/vm/classfile/symbolTable.hpp	Tue Jun 26 09:52:27 2012 -0400
@@ -88,7 +88,6 @@
   static int symbols_counted;
 
   Symbol* allocate_symbol(const u1* name, int len, TRAPS);   // Assumes no characters larger than 0x7F
-  bool allocate_symbols(int names_count, const u1** names, int* lengths, Symbol** syms, TRAPS);
 
   // Adding elements
   Symbol* basic_add(int index, u1* name, int len,
@@ -144,7 +143,7 @@
     _the_table = new SymbolTable(t, number_of_entries);
   }
 
-  static unsigned int hash_symbol(const char* s, int len, unsigned int hashValue = 0);
+  static unsigned int hash_symbol(const char* s, int len);
 
   static Symbol* lookup(const char* name, int len, TRAPS);
   // lookup only, won't add. Also calculate hash.
@@ -279,7 +278,7 @@
   // Hashing algorithm, used as the hash value used by the
   //     StringTable for bucket selection and comparison (stored in the
   //     HashtableEntry structures).  This is used in the String.intern() method.
-  static unsigned int hash_string(const jchar* s, int len, unsigned int hashValue = 0);
+  static unsigned int hash_string(const jchar* s, int len);
 
   // Internal test.
   static void test_alt_hash() PRODUCT_RETURN;
diff -r 409abd911542 -r faa8d30306e8 src/share/vm/utilities/hashtable.cpp
--- a/src/share/vm/utilities/hashtable.cpp	Fri Jun 22 13:35:02 2012 -0700
+++ b/src/share/vm/utilities/hashtable.cpp	Tue Jun 26 09:52:27 2012 -0400
@@ -24,6 +24,7 @@
 
 #include "precompiled.hpp"
 #include "memory/allocation.inline.hpp"
+#include "memory/filemap.hpp"
 #include "memory/resourceArea.hpp"
 #include "oops/oop.inline.hpp"
 #include "runtime/safepoint.hpp"
@@ -119,8 +120,16 @@
       // Get a new index relative to the new table (can also change size)
       int index = new_table->hash_to_index(hashValue);
       p->set_hash(hashValue);
+      // Keep the shared bit in the Hashtable entry to indicate that this entry
+      // can't be deleted.   The shared bit is the LSB in the _next field so
+      // walking the hashtable past these entries requires
+      // BasicHashtableEntry::make_ptr() call.
+      bool keep_shared = p->is_shared();
       unlink_entry(p);
       new_table->add_entry(index, p);
+      if (keep_shared) {
+        p->set_shared();
+      }
       p = next;
     }
   }
@@ -135,6 +144,19 @@
   free_buckets();
 }
 
+void BasicHashtable::free_buckets() {
+  if (NULL != _buckets) {
+    // Don't delete the buckets in the shared space.  They aren't
+    // allocated by os::malloc
+    if (!UseSharedSpaces ||
+        !FileMapInfo::current_info()->is_in_shared_space(_buckets)) {
+       FREE_C_HEAP_ARRAY(HashtableBucket, _buckets);
+    }
+    _buckets = NULL;
+  }
+}
+
+
 // Reverse the order of elements in the hash buckets.
 
 void BasicHashtable::reverse() {
diff -r 409abd911542 -r faa8d30306e8 src/share/vm/utilities/hashtable.hpp
--- a/src/share/vm/utilities/hashtable.hpp	Fri Jun 22 13:35:02 2012 -0700
+++ b/src/share/vm/utilities/hashtable.hpp	Tue Jun 26 09:52:27 2012 -0400
@@ -217,12 +217,7 @@
   }
 
   // Free the buckets in this hashtable
-  void free_buckets() {
-    if (NULL != _buckets) {
-      FREE_C_HEAP_ARRAY(HashtableBucket, _buckets);
-      _buckets = NULL;
-    }
-  }
+  void free_buckets();
 
 public:
   int table_size() { return _table_size; }