changeset 9676:3bef2d08010e

8055283: Expand ResourceHashtable with C_HEAP allocation, removal and some unit tests Reviewed-by: ehelin, tschatzl, coleenp
author mgerdin
date Mon, 18 Aug 2014 14:37:55 +0200
parents 923bde1cd574
children 7977bf8f391e 766ae06f30ca
files src/share/vm/prims/jni.cpp src/share/vm/utilities/resourceHash.cpp src/share/vm/utilities/resourceHash.hpp
diffstat 3 files changed, 224 insertions(+), 4 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/vm/prims/jni.cpp	Mon Nov 02 14:28:19 2015 +0100
+++ b/src/share/vm/prims/jni.cpp	Mon Aug 18 14:37:55 2014 +0200
@@ -3867,6 +3867,7 @@
 void TestBitMap_test();
 void TestAsUtf8();
 void Test_linked_list();
+void TestResourcehash_test();
 void TestChunkedList_test();
 #if INCLUDE_ALL_GCS
 void TestOldFreeSpaceCalculation_test();
@@ -3904,6 +3905,7 @@
     run_unit_test(TestKlass_test());
     run_unit_test(TestBitMap_test());
     run_unit_test(TestAsUtf8());
+    run_unit_test(TestResourcehash_test());
     run_unit_test(ObjectMonitor::sanity_checks());
     run_unit_test(Test_linked_list());
     run_unit_test(TestChunkedList_test());
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/vm/utilities/resourceHash.cpp	Mon Aug 18 14:37:55 2014 +0200
@@ -0,0 +1,182 @@
+/*
+ * Copyright (c) 2015 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.
+ *
+ */
+
+#include "precompiled.hpp"
+#include "memory/allocation.hpp"
+#include "memory/resourceArea.hpp"
+#include "utilities/debug.hpp"
+#include "utilities/resourceHash.hpp"
+
+#ifndef PRODUCT
+
+/////////////// Unit tests ///////////////
+
+class TestResourceHashtable : public AllStatic {
+  typedef void* K;
+  typedef int V;
+
+  static unsigned identity_hash(const K& k) {
+    return (unsigned)(uintptr_t)k;
+  }
+
+  static unsigned bad_hash(const K& k) {
+    return 1;
+  }
+
+  class EqualityTestIter {
+   public:
+    bool do_entry(K const& k, V const& v) {
+      assert((uintptr_t)k == (uintptr_t)v, "");
+      return true; // continue iteration
+    }
+  };
+
+  template<
+  unsigned (*HASH)  (K const&)           = primitive_hash<K>,
+  bool     (*EQUALS)(K const&, K const&) = primitive_equals<K>,
+  unsigned SIZE = 256,
+  ResourceObj::allocation_type ALLOC_TYPE = ResourceObj::RESOURCE_AREA,
+  MEMFLAGS MEM_TYPE = mtInternal
+  >
+  class Runner : public AllStatic {
+    static void* as_K(uintptr_t val) { return (void*)val; }
+
+   public:
+    static void test_small() {
+      EqualityTestIter et;
+      ResourceHashtable<K, V, HASH, EQUALS, SIZE, ALLOC_TYPE, MEM_TYPE> rh;
+
+      assert(!rh.contains(as_K(0x1)), "");
+
+      assert(rh.put(as_K(0x1), 0x1), "");
+      assert(rh.contains(as_K(0x1)), "");
+
+      assert(!rh.put(as_K(0x1), 0x1), "");
+
+      assert(rh.put(as_K(0x2), 0x2), "");
+      assert(rh.put(as_K(0x3), 0x3), "");
+      assert(rh.put(as_K(0x4), 0x4), "");
+      assert(rh.put(as_K(0x5), 0x5), "");
+
+      assert(!rh.remove(as_K(0x0)), "");
+      rh.iterate(&et);
+
+      assert(rh.remove(as_K(0x1)), "");
+      rh.iterate(&et);
+
+    }
+
+    // We use keys with the low bits cleared since the default hash will do some shifting
+    static void test_small_shifted() {
+      EqualityTestIter et;
+      ResourceHashtable<K, V, HASH, EQUALS, SIZE, ALLOC_TYPE, MEM_TYPE> rh;
+
+      assert(!rh.contains(as_K(0x10)), "");
+
+      assert(rh.put(as_K(0x10), 0x10), "");
+      assert(rh.contains(as_K(0x10)), "");
+
+      assert(!rh.put(as_K(0x10), 0x10), "");
+
+      assert(rh.put(as_K(0x20), 0x20), "");
+      assert(rh.put(as_K(0x30), 0x30), "");
+      assert(rh.put(as_K(0x40), 0x40), "");
+      assert(rh.put(as_K(0x50), 0x50), "");
+
+      assert(!rh.remove(as_K(0x00)), "");
+
+      assert(rh.remove(as_K(0x10)), "");
+
+      rh.iterate(&et);
+    }
+
+    static void test(unsigned num_elements = SIZE) {
+      EqualityTestIter et;
+      ResourceHashtable<K, V, HASH, EQUALS, SIZE, ALLOC_TYPE, MEM_TYPE> rh;
+
+      for (uintptr_t i = 0; i < num_elements; ++i) {
+        assert(rh.put(as_K(i), i), "");
+      }
+
+      rh.iterate(&et);
+
+      for (uintptr_t i = num_elements; i > 0; --i) {
+        uintptr_t index = i - 1;
+        assert(rh.remove(as_K(index)), "");
+      }
+      rh.iterate(&et);
+      for (uintptr_t i = num_elements; i > 0; --i) {
+        uintptr_t index = i - 1;
+        assert(!rh.remove(as_K(index)), "");
+      }
+      rh.iterate(&et);
+    }
+  };
+
+ public:
+  static void run_tests() {
+    {
+      ResourceMark rm;
+      Runner<>::test_small();
+      Runner<>::test_small_shifted();
+      Runner<>::test();
+    }
+
+    {
+      ResourceMark rm;
+      Runner<identity_hash>::test_small();
+      Runner<identity_hash>::test_small_shifted();
+      Runner<identity_hash>::test();
+    }
+
+    {
+      ResourceMark rm;
+      Runner<bad_hash>::test_small();
+      Runner<bad_hash>::test_small_shifted();
+      Runner<bad_hash>::test();
+    }
+
+
+    assert(Thread::current()->resource_area()->nesting() == 0, "this code depends on not having an active ResourceMark");
+    // The following test calls will cause an assert if resource allocations occur since we don't have an active mark
+    Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test_small();
+    Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test_small_shifted();
+    Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test();
+
+    Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test_small();
+    Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test_small_shifted();
+    Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test();
+
+    Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test_small();
+    Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test_small_shifted();
+    Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test(512);
+  }
+};
+
+void TestResourcehash_test() {
+  TestResourceHashtable::run_tests();
+}
+
+#endif // not PRODUCT
+
--- a/src/share/vm/utilities/resourceHash.hpp	Mon Nov 02 14:28:19 2015 +0100
+++ b/src/share/vm/utilities/resourceHash.hpp	Mon Aug 18 14:37:55 2014 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2012, 2015 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
@@ -35,7 +35,7 @@
 
 template<typename K> unsigned primitive_hash(const K& k) {
   unsigned hash = (unsigned)((uintptr_t)k);
-  return hash ^ (hash > 3); // just in case we're dealing with aligned ptrs
+  return hash ^ (hash >> 3); // just in case we're dealing with aligned ptrs
 }
 
 template<typename K> bool primitive_equals(const K& k0, const K& k1) {
@@ -50,7 +50,9 @@
     //typename ResourceHashtableFns<K>::equals_fn EQUALS = primitive_equals<K>,
     unsigned (*HASH)  (K const&)           = primitive_hash<K>,
     bool     (*EQUALS)(K const&, K const&) = primitive_equals<K>,
-    unsigned SIZE = 256
+    unsigned SIZE = 256,
+    ResourceObj::allocation_type ALLOC_TYPE = ResourceObj::RESOURCE_AREA,
+    MEMFLAGS MEM_TYPE = mtInternal
     >
 class ResourceHashtable : public ResourceObj {
  private:
@@ -91,6 +93,21 @@
  public:
   ResourceHashtable() { memset(_table, 0, SIZE * sizeof(Node*)); }
 
+  ~ResourceHashtable() {
+    if (ALLOC_TYPE == C_HEAP) {
+      Node* const* bucket = _table;
+      while (bucket < &_table[SIZE]) {
+        Node* node = *bucket;
+        while (node != NULL) {
+          Node* cur = node;
+          node = node->_next;
+          delete cur;
+        }
+        ++bucket;
+      }
+    }
+  }
+
   bool contains(K const& key) const {
     return get(key) != NULL;
   }
@@ -117,11 +134,26 @@
       (*ptr)->_value = value;
       return false;
     } else {
-      *ptr = new Node(hv, key, value);
+      *ptr = new (ALLOC_TYPE, MEM_TYPE) Node(hv, key, value);
       return true;
     }
   }
 
+  bool remove(K const& key) {
+    unsigned hv = HASH(key);
+    Node** ptr = lookup_node(hv, key);
+
+    Node* node = *ptr;
+    if (node != NULL) {
+      *ptr = node->_next;
+      if (ALLOC_TYPE == C_HEAP) {
+        delete node;
+      }
+      return true;
+    }
+    return false;
+  }
+
   // ITER contains bool do_entry(K const&, V const&), which will be
   // called for each entry in the table.  If do_entry() returns false,
   // the iteration is cancelled.
@@ -138,6 +170,10 @@
       ++bucket;
     }
   }
+
+  static size_t node_size() {
+    return sizeof(Node);
+  }
 };