8030750: SA: Alternate hashing not implemented
authorsballal
Wed, 26 Apr 2017 14:59:52 +0530
changeset 44897 1d9f4d0c9927
parent 44896 2ef5ea002441
child 44898 b80c30ca5fcd
8030750: SA: Alternate hashing not implemented Summary: Implement alternate hashing in SA Reviewed-by: dsamersoff Contributed-by: sharath.ballal@oracle.com
hotspot/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/memory/AltHashing.java
hotspot/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/memory/SymbolTable.java
hotspot/src/share/vm/runtime/vmStructs.cpp
hotspot/src/share/vm/utilities/hashtable.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/memory/AltHashing.java	Wed Apr 26 14:59:52 2017 +0530
@@ -0,0 +1,94 @@
+/*
+ * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+package sun.jvm.hotspot.memory;
+
+public class AltHashing {
+    public static long murmur3_32(long seed, byte[] data) {
+      long h1 = seed;
+      int len = data.length;
+      int count = len;
+
+      int offset = 0;
+
+      // body
+      while (count >= 4) {
+          long k1 = (data[offset] & 0x0FF)
+              | (data[offset + 1] & 0x0FF) << 8
+              | (data[offset + 2] & 0x0FF) << 16
+              | data[offset + 3] << 24;
+
+          count -= 4;
+          offset += 4;
+
+          k1 *= 0xcc9e2d51;
+          k1 = Integer.rotateLeft((int)k1, 15);
+          k1 *= 0x1b873593;
+          k1 &= 0xFFFFFFFFL;
+
+          h1 ^= k1;
+          h1 = Integer.rotateLeft((int)h1, 13);
+          h1 = h1 * 5 + 0xe6546b64;
+          h1 &= 0xFFFFFFFFL;
+      }
+
+      //tail
+      if (count > 0) {
+          long k1 = 0;
+
+          switch (count) {
+              case 3:
+                  k1 ^= (data[offset + 2] & 0xff) << 16;
+                  // fall through
+              case 2:
+                  k1 ^= (data[offset + 1] & 0xff) << 8;
+                  // fall through
+              case 1:
+                  k1 ^= (data[offset] & 0xff);
+                  // fall through
+              default:
+                  k1 *= 0xcc9e2d51;
+                  k1 = Integer.rotateLeft((int)k1, 15);
+                  k1 *= 0x1b873593;
+                  k1 &= 0xFFFFFFFFL;
+                  h1 ^= k1;
+                  h1 &= 0xFFFFFFFFL;
+          }
+      }
+
+      // finalization
+      h1 ^= len;
+
+      // finalization mix force all bits of a hash block to avalanche
+      h1 ^= h1 >> 16;
+      h1 *= 0x85ebca6b;
+      h1 &= 0xFFFFFFFFL;
+      h1 ^= h1 >> 13;
+      h1 *= 0xc2b2ae35;
+      h1 &= 0xFFFFFFFFL;
+      h1 ^= h1 >> 16;
+
+      return h1 & 0xFFFFFFFFL;
+  }
+}
--- a/hotspot/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/memory/SymbolTable.java	Tue Apr 25 08:18:29 2017 +0000
+++ b/hotspot/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/memory/SymbolTable.java	Wed Apr 26 14:59:52 2017 +0530
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2001, 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2001, 2017, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -45,11 +45,14 @@
     Type type = db.lookupType("SymbolTable");
     theTableField  = type.getAddressField("_the_table");
     sharedTableField = type.getAddressField("_shared_table");
+    type = db.lookupType("RehashableSymbolHashtable");
+    seedField = type.getCIntegerField("_seed");
   }
 
   // Fields
   private static AddressField theTableField;
   private static AddressField sharedTableField;
+  private static CIntegerField seedField;
 
   private CompactHashTable sharedTable;
 
@@ -62,6 +65,17 @@
     return table;
   }
 
+  public static long getSeed() {
+      return (long) seedField.getValue();
+  }
+
+  public static boolean useAlternateHashcode() {
+      if (getSeed() != 0) {
+          return true;
+      }
+      return false;
+  }
+
   public SymbolTable(Address addr) {
     super(addr);
   }
@@ -86,11 +100,17 @@
   public Symbol probe(byte[] name) {
     long hashValue = hashSymbol(name);
 
+    // shared table does not use alternate hashing algorithm,
+    // it always uses the same original hash code.
     Symbol s = sharedTable.probe(name, hashValue);
     if (s != null) {
       return s;
     }
 
+    if (useAlternateHashcode()) {
+        hashValue = AltHashing.murmur3_32(getSeed(), name);
+    }
+
     for (HashtableEntry e = (HashtableEntry) bucket(hashToIndex(hashValue)); e != null; e = (HashtableEntry) e.next()) {
       if (e.hash() == hashValue) {
          Symbol sym = Symbol.create(e.literalValue());
--- a/hotspot/src/share/vm/runtime/vmStructs.cpp	Tue Apr 25 08:18:29 2017 +0000
+++ b/hotspot/src/share/vm/runtime/vmStructs.cpp	Wed Apr 26 14:59:52 2017 +0530
@@ -199,6 +199,7 @@
 typedef HashtableEntry<Klass*, mtClass>       KlassHashtableEntry;
 typedef TwoOopHashtable<Symbol*, mtClass>     SymbolTwoOopHashtable;
 typedef CompactHashtable<Symbol*, char>       SymbolCompactHashTable;
+typedef RehashableHashtable<Symbol*, mtSymbol>   RehashableSymbolHashtable;
 
 //--------------------------------------------------------------------------------
 // VM_STRUCTS
@@ -584,6 +585,7 @@
                                                                                                                                      \
      static_field(SymbolTable,                 _the_table,                                    SymbolTable*)                          \
      static_field(SymbolTable,                 _shared_table,                                 SymbolCompactHashTable)                \
+     static_field(RehashableSymbolHashtable,   _seed,                                         juint)                                 \
                                                                                                                                      \
   /***************/                                                                                                                  \
   /* StringTable */                                                                                                                  \
@@ -1602,6 +1604,8 @@
                                                                           \
   declare_toplevel_type(BasicHashtable<mtInternal>)                       \
     declare_type(IntptrHashtable, BasicHashtable<mtInternal>)             \
+  declare_toplevel_type(BasicHashtable<mtSymbol>)                         \
+    declare_type(RehashableSymbolHashtable, BasicHashtable<mtSymbol>)     \
   declare_type(SymbolTable, SymbolHashtable)                              \
   declare_type(StringTable, StringHashtable)                              \
     declare_type(LoaderConstraintTable, KlassHashtable)                   \
--- a/hotspot/src/share/vm/utilities/hashtable.hpp	Tue Apr 25 08:18:29 2017 +0000
+++ b/hotspot/src/share/vm/utilities/hashtable.hpp	Wed Apr 26 14:59:52 2017 +0530
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2003, 2016, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2003, 2017, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -294,6 +294,7 @@
 };
 
 template <class T, MEMFLAGS F> class RehashableHashtable : public Hashtable<T, F> {
+ friend class VMStructs;
  protected:
 
   enum {