--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/memory/metaspace/blockListArray.hpp Sat Nov 23 11:05:16 2019 +0100
@@ -0,0 +1,154 @@
+/*
+ * Copyright (c) 2019, SAP SE. All rights reserved.
+ * Copyright (c) 2019, 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.
+ *
+ */
+
+#ifndef SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_HPP
+#define SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_HPP
+
+#include "memory/allocation.hpp"
+#include "utilities/debug.hpp"
+#include "utilities/globalDefinitions.hpp"
+
+
+class outputStream;
+
+namespace metaspace {
+
+struct block_t {
+ block_t* next;
+ size_t size;
+};
+
+struct block_stats_t {
+ size_t word_size;
+ int num_blocks;
+};
+
+// A bitmap keeping track of which list is occupied. Smallest list corresponds to lowest order bit.
+// 1 means list is not empty, 0 means list is empty.
+class BlockListFreeMap {
+
+ typedef uint32_t mask_type;
+ mask_type _mask;
+
+ static mask_type mask_for_pos(int pos) { return 1 << pos; }
+
+public:
+
+ BlockListFreeMap() : _mask(0) {}
+
+ bool all_zero() const { return _mask == 0; }
+
+ bool get_bit(int pos) const { return (_mask & mask_for_pos(pos)) != 0 ? true : false; }
+ void set_bit(int pos) { _mask |= mask_for_pos(pos); }
+ void clr_bit(int pos) { _mask &= ~mask_for_pos(pos); }
+
+ // Starting at (including) pos, find the position of the next 1 bit.
+ // Return -1 if not found.
+ inline int find_next_set_bit(int pos) const;
+
+ static int size() { return sizeof(mask_type) * 8; }
+
+};
+
+template <
+ size_t min_word_size,
+ size_t spread,
+ int num_bins
+>
+class BlockListArray {
+
+ STATIC_ASSERT(sizeof(block_t) <= (min_word_size * BytesPerWord));
+
+ block_t* _bins[num_bins];
+
+ BlockListFreeMap _map;
+
+ // e.g. spread = 4
+ //
+ // sz bno (put) bno (get)
+ // (guarant)
+ // 0 00 00
+ // 1 00 01
+ // 2 00 01
+ // 3 00 01
+ // 4 01 01
+ // 5 01 02
+ // 6 01 02
+ // 7 01 02
+ // 8 02 02
+ // 9 02 03
+ // 10 02 03
+ // 11 02 03
+ //
+ // put -> no = wordsize / spread
+ //
+ // get -> no = (req_wordsize + spread - 1) / spread
+
+ // The bin number for a given word size.
+ static int bin_for_size(size_t word_size) {
+ assert(word_size >= min_word_size && word_size < maximal_word_size(),
+ "Word size oob (" SIZE_FORMAT ")", word_size);
+ return (word_size - min_word_size) / spread;
+ }
+
+ // [minimal, maximal) size of blocks which are held in a bin.
+ // Note that when taking a block out of the bin, only the minimum block size
+ // is guaranteed.
+ static size_t minimal_word_size_in_bin(int bno) {
+ return min_word_size + (bno * spread);
+ }
+ static size_t maximal_word_size_in_bin(int bno) {
+ return minimal_word_size_in_bin(bno) + spread;
+ }
+
+public:
+
+ BlockListArray() : _map() {
+ assert(BlockListFreeMap::size() >= num_bins, "Map too small.");
+ ::memset(_bins, 0, sizeof(_bins));
+ }
+
+ // [min, max) word size
+ static size_t minimal_word_size() { return min_word_size; }
+ static size_t maximal_word_size() { return min_word_size + (spread * num_bins); }
+
+ inline void put(MetaWord* p, size_t word_size);
+
+ inline block_t* get(size_t word_size);
+
+#ifdef ASSERT
+ void verify() const;
+#endif
+
+ void statistics(block_stats_t* stats) const;
+
+ void print(outputStream* st) const;
+
+};
+
+
+} // namespace metaspace
+
+#endif // SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_HPP
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/memory/metaspace/blockListArray.inline.hpp Sat Nov 23 11:05:16 2019 +0100
@@ -0,0 +1,142 @@
+/*
+ * Copyright (c) 2019, SAP SE. All rights reserved.
+ * Copyright (c) 2019, 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.
+ *
+ */
+
+#ifndef SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_INLINE_HPP
+#define SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_INLINE_HPP
+
+#include "memory/allocation.hpp"
+#include "memory/metaspace/blockListArray.hpp"
+#include "utilities/debug.hpp"
+#include "utilities/globalDefinitions.hpp"
+#include "utilities/ostream.hpp"
+
+namespace metaspace {
+
+
+// Starting at (including) pos, find the position of the next 1 bit.
+// Return -1 if not found.
+int BlockListFreeMap::find_next_set_bit(int pos) const {
+
+ if (get_bit(pos)) {
+ return pos;
+ }
+ mask_type m2 = _mask;
+ int pos2 = pos + 1;
+ m2 >>= pos2;
+ if (m2 > 0) {
+ while ((m2 & (mask_type)1) == 0) {
+ m2 >>= 1;
+ pos2 ++;
+ }
+ return pos2;
+ }
+ return -1;
+
+}
+
+///////////////////////////////////////
+
+template <size_t min_word_size, size_t spread, int num_bins>
+void BlockListArray<min_word_size, spread, num_bins>::put(MetaWord* p, size_t word_size) {
+ assert(word_size >= minimal_word_size() && word_size < maximal_word_size(), "Invalid word size");
+ block_t* b = (block_t*)p;
+ int bno = bin_for_size(word_size);
+ assert(bno >= 0 && bno < num_bins, "Sanity");
+ assert(b != _bins[bno], "double add?");
+ b->next = _bins[bno];
+ b->size = word_size;
+ _bins[bno] = b;
+ _map.set_bit(bno);
+}
+
+template <size_t min_word_size, size_t spread, int num_bins>
+block_t* BlockListArray<min_word_size, spread, num_bins>::get(size_t word_size) {
+ // Adjust size for spread (we need the bin number which guarantees word_size).
+ word_size += (spread - 1);
+ if (word_size >= maximal_word_size()) {
+ return NULL;
+ }
+ int bno = bin_for_size(word_size);
+ bno = _map.find_next_set_bit(bno);
+ if (bno != -1) {
+ assert(bno >= 0 && bno < num_bins, "Sanity");
+ assert(_bins[bno] != NULL, "Sanity");
+ block_t* b = _bins[bno];
+ _bins[bno] = b->next;
+ if (_bins[bno] == NULL) {
+ _map.clr_bit(bno);
+ }
+ return b;
+ }
+ return NULL;
+}
+
+#ifdef ASSERT
+template <size_t min_word_size, size_t spread, int num_bins>
+void BlockListArray<min_word_size, spread, num_bins>::verify() const {
+ for (int i = 0; i < num_bins; i ++) {
+ assert(_map.get_bit(i) == (_bins[i] != NULL), "Sanity");
+ const size_t min_size = minimal_word_size_in_bin(i);
+ const size_t max_size = maximal_word_size_in_bin(i);
+ for(block_t* b = _bins[i]; b != NULL; b = b->next) {
+ assert(b->size >= min_size && b->size < max_size, "Sanity");
+ }
+ }
+}
+#endif // ASSERT
+
+
+template <size_t min_word_size, size_t spread, int num_bins>
+void BlockListArray<min_word_size, spread, num_bins>::statistics(block_stats_t* stats) const {
+ for (int i = 0; i < num_bins; i ++) {
+ for(block_t* b = _bins[i]; b != NULL; b = b->next) {
+ stats->num_blocks ++;
+ stats->word_size += b->size;
+ }
+ }
+}
+
+template <size_t min_word_size, size_t spread, int num_bins>
+void BlockListArray<min_word_size, spread, num_bins>::print(outputStream* st) const {
+ bool first = true;
+ for (int i = 0; i < num_bins; i ++) {
+ int n = 0;
+ for(block_t* b = _bins[i]; b != NULL; b = b->next) {
+ n ++;
+ }
+ if (n > 0) {
+ if (!first) {
+ st->print(", ");
+ } else {
+ first = false;
+ }
+ st->print(SIZE_FORMAT "=%d", minimal_word_size_in_bin(i), n);
+ }
+ }
+}
+
+} // namespace metaspace
+
+#endif // SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_INLINE_HPP
--- a/src/hotspot/share/memory/metaspace/leftOverBins.cpp Fri Nov 01 10:28:15 2019 +0100
+++ b/src/hotspot/share/memory/metaspace/leftOverBins.cpp Sat Nov 23 11:05:16 2019 +0100
@@ -24,6 +24,7 @@
*/
#include "precompiled.hpp"
+#include "memory/metaspace/blockListArray.inline.hpp"
#include "memory/metaspace/leftOverBins.inline.hpp"
#include "utilities/globalDefinitions.hpp"
#include "utilities/ostream.hpp"
--- a/src/hotspot/share/memory/metaspace/leftOverBins.hpp Fri Nov 01 10:28:15 2019 +0100
+++ b/src/hotspot/share/memory/metaspace/leftOverBins.hpp Sat Nov 23 11:05:16 2019 +0100
@@ -27,6 +27,7 @@
#define SHARE_MEMORY_METASPACE_LEFTOVERBINS_HPP
#include "memory/allocation.hpp"
+#include "memory/metaspace/blockListArray.hpp"
#include "memory/metaspace/counter.hpp"
#include "utilities/bitMap.hpp"
#include "utilities/debug.hpp"
@@ -47,121 +48,9 @@
// due to interrupted class loading. These blocks are small or
// very small.
-class BinMap {
-
- typedef uint32_t mask_type;
- mask_type _mask;
-
- static mask_type mask_for_pos(int pos) { return 1 << pos; }
-
-public:
-
- BinMap() : _mask(0) {}
-
- bool all_zero() const { return _mask == 0; }
-
- bool get_bit(int pos) const { return (_mask & mask_for_pos(pos)) != 0 ? true : false; }
- void set_bit(int pos) { _mask |= mask_for_pos(pos); }
- void clr_bit(int pos) { _mask &= ~mask_for_pos(pos); }
-
- // Starting at (including) pos, find the position of the next 1 bit.
- // Return -1 if not found.
- inline int find_next_set_bit(int pos) const;
-
- static int size() { return sizeof(mask_type) * 8; }
-
-};
-
-struct block_t {
- block_t* next;
- size_t size;
-};
-
-struct block_stats_t {
- size_t word_size;
- int num_blocks;
-};
-
-template <
- size_t min_word_size,
- size_t spread,
- int num_bins
->
-class Bins {
-
- STATIC_ASSERT(sizeof(block_t) <= (min_word_size * BytesPerWord));
-
- block_t* _bins[num_bins];
-
- BinMap _mask;
-
- // e.g. spread = 4
- //
- // sz bno (put) bno (get)
- // (guarant)
- // 0 00 00
- // 1 00 01
- // 2 00 01
- // 3 00 01
- // 4 01 01
- // 5 01 02
- // 6 01 02
- // 7 01 02
- // 8 02 02
- // 9 02 03
- // 10 02 03
- // 11 02 03
- //
- // put -> no = wordsize / spread
- //
- // get -> no = (req_wordsize + spread - 1) / spread
-
- // The bin number for a given word size.
- static int bin_for_size(size_t word_size) {
- assert(word_size >= min_word_size && word_size < maximal_word_size(),
- "Word size oob (" SIZE_FORMAT ")", word_size);
- return (word_size - min_word_size) / spread;
- }
-
- // [minimal, maximal) size of blocks which are held in a bin.
- // Note that when taking a block out of the bin, only the minimum block size
- // is guaranteed.
- static size_t minimal_word_size_in_bin(int bno) {
- return min_word_size + (bno * spread);
- }
- static size_t maximal_word_size_in_bin(int bno) {
- return minimal_word_size_in_bin(bno) + spread;
- }
-
-public:
-
- Bins() : _mask() {
- assert(BinMap::size() >= num_bins, "mask too small");
- ::memset(_bins, 0, sizeof(_bins));
- }
-
- // [min, max) word size
- static size_t minimal_word_size() { return min_word_size; }
- static size_t maximal_word_size() { return min_word_size + (spread * num_bins); }
-
- inline void put(MetaWord* p, size_t word_size);
-
- inline block_t* get(size_t word_size);
-
-#ifdef ASSERT
- void verify() const;
-#endif
-
- void statistics(block_stats_t* stats) const;
-
- void print(outputStream* st) const;
-
-};
-
-
class LeftOverManager : public CHeapObj<mtInternal> {
- typedef Bins<2, 2, 16> VerySmallBinsType;
+ typedef BlockListArray<2, 2, 16> VerySmallBinsType;
VerySmallBinsType _very_small_bins;
block_t* _large_block_reserve;
--- a/src/hotspot/share/memory/metaspace/leftOverBins.inline.hpp Fri Nov 01 10:28:15 2019 +0100
+++ b/src/hotspot/share/memory/metaspace/leftOverBins.inline.hpp Sat Nov 23 11:05:16 2019 +0100
@@ -27,6 +27,7 @@
#define SHARE_MEMORY_METASPACE_LEFTOVERBINS_INLINE_HPP
#include "memory/allocation.hpp"
+#include "memory/metaspace/blockListArray.inline.hpp"
#include "memory/metaspace/leftOverBins.hpp"
#include "utilities/debug.hpp"
#include "utilities/globalDefinitions.hpp"
@@ -35,108 +36,6 @@
namespace metaspace {
-// Starting at (including) pos, find the position of the next 1 bit.
-// Return -1 if not found.
-int BinMap::find_next_set_bit(int pos) const {
- if (get_bit(pos)) {
- return pos;
- }
- mask_type m2 = _mask;
- int pos2 = pos + 1;
- m2 >>= pos2;
- if (m2 > 0) {
- while ((m2 & (mask_type)1) == 0) {
- m2 >>= 1;
- pos2 ++;
- }
- return pos2;
- }
- return -1;
-}
-
-///////////////////////////////////////
-
-template <size_t min_word_size, size_t spread, int num_bins>
-void Bins<min_word_size, spread, num_bins>::put(MetaWord* p, size_t word_size) {
- assert(word_size >= minimal_word_size() && word_size < maximal_word_size(), "Invalid word size");
- block_t* b = (block_t*)p;
- int bno = bin_for_size(word_size);
- assert(bno >= 0 && bno < num_bins, "Sanity");
- assert(b != _bins[bno], "double add?");
- b->next = _bins[bno];
- b->size = word_size;
- _bins[bno] = b;
- _mask.set_bit(bno);
-}
-
-template <size_t min_word_size, size_t spread, int num_bins>
-block_t* Bins<min_word_size, spread, num_bins>::get(size_t word_size) {
- // Adjust size for spread (we need the bin number which guarantees word_size).
- word_size += (spread - 1);
- if (word_size >= maximal_word_size()) {
- return NULL;
- }
- int bno = bin_for_size(word_size);
- bno = _mask.find_next_set_bit(bno);
- if (bno != -1) {
- assert(bno >= 0 && bno < num_bins, "Sanity");
- assert(_bins[bno] != NULL, "Sanity");
- block_t* b = _bins[bno];
- _bins[bno] = b->next;
- if (_bins[bno] == NULL) {
- _mask.clr_bit(bno);
- }
- return b;
- }
- return NULL;
-}
-
-#ifdef ASSERT
-template <size_t min_word_size, size_t spread, int num_bins>
-void Bins<min_word_size, spread, num_bins>::verify() const {
- for (int i = 0; i < num_bins; i ++) {
- assert(_mask.get_bit(i) == (_bins[i] != NULL), "Sanity");
- const size_t min_size = minimal_word_size_in_bin(i);
- const size_t max_size = maximal_word_size_in_bin(i);
- for(block_t* b = _bins[i]; b != NULL; b = b->next) {
- assert(b->size >= min_size && b->size < max_size, "Sanity");
- }
- }
-}
-#endif // ASSERT
-
-
-template <size_t min_word_size, size_t spread, int num_bins>
-void Bins<min_word_size, spread, num_bins>::statistics(block_stats_t* stats) const {
- for (int i = 0; i < num_bins; i ++) {
- for(block_t* b = _bins[i]; b != NULL; b = b->next) {
- stats->num_blocks ++;
- stats->word_size += b->size;
- }
- }
-}
-
-template <size_t min_word_size, size_t spread, int num_bins>
-void Bins<min_word_size, spread, num_bins>::print(outputStream* st) const {
- bool first = true;
- for (int i = 0; i < num_bins; i ++) {
- int n = 0;
- for(block_t* b = _bins[i]; b != NULL; b = b->next) {
- n ++;
- }
- if (n > 0) {
- if (!first) {
- st->print(", ");
- } else {
- first = false;
- }
- st->print(SIZE_FORMAT "=%d", minimal_word_size_in_bin(i), n);
- }
- }
-}
-
-
-
///////////////////////////////////////
// Take the topmost block from the large block reserve list
--- a/test/hotspot/gtest/metaspace/metaspaceTestsCommon.hpp Fri Nov 01 10:28:15 2019 +0100
+++ b/test/hotspot/gtest/metaspace/metaspaceTestsCommon.hpp Sat Nov 23 11:05:16 2019 +0100
@@ -26,6 +26,7 @@
#include "memory/allocation.hpp"
+#include "memory/metaspace/blockListArray.inline.hpp"
#include "memory/metaspace/chunkAllocSequence.hpp"
#include "memory/metaspace/chunkHeaderPool.hpp"
#include "memory/metaspace/chunkLevel.hpp"
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/gtest/metaspace/test_blockListArray.cpp Sat Nov 23 11:05:16 2019 +0100
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2019, SAP SE. All rights reserved.
+ * Copyright (c) 2019, 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"
+
+//#define LOG_PLEASE
+
+#include "metaspaceTestsCommon.hpp"
+
+TEST_VM(metaspace, BlockListFreeMap_mask_basic) {
+ // Basic tests
+ metaspace::BlockListFreeMap map;
+ EXPECT_TRUE(map.all_zero());
+ for (int i = 0; i < map.size(); i ++) {
+ map.set_bit(i);
+ EXPECT_TRUE(map.get_bit(i));
+ map.clr_bit(i);
+ EXPECT_FALSE(map.get_bit(i));
+ EXPECT_TRUE(map.all_zero());
+ }
+}
+
+TEST_VM(metaspace, BlockListFreeMap_mask_find_next_set_bit) {
+ metaspace::BlockListFreeMap map;
+ EXPECT_TRUE(map.all_zero());
+ for (int i = 0; i < map.size(); i ++) {
+ map.set_bit(i);
+ for (int j = 0; j < i; j ++) {
+ int n = map.find_next_set_bit(j);
+ if (j <= i) {
+ EXPECT_EQ(n, i);
+ } else {
+ EXPECT_EQ(n, -1);
+ }
+ }
+ map.clr_bit(i);
+ }
+}
+
--- a/test/hotspot/gtest/metaspace/test_leftOverBins.cpp Fri Nov 01 10:28:15 2019 +0100
+++ b/test/hotspot/gtest/metaspace/test_leftOverBins.cpp Sat Nov 23 11:05:16 2019 +0100
@@ -216,35 +216,6 @@
};
-TEST_VM(metaspace, leftoverbins_mask_basic) {
- // Basic tests
- metaspace::BinMap map;
- EXPECT_TRUE(map.all_zero());
- for (int i = 0; i < map.size(); i ++) {
- map.set_bit(i);
- EXPECT_TRUE(map.get_bit(i));
- map.clr_bit(i);
- EXPECT_FALSE(map.get_bit(i));
- EXPECT_TRUE(map.all_zero());
- }
-}
-
-TEST_VM(metaspace, leftoverbins_mask_find_next_set_bit) {
- metaspace::BinMap map;
- EXPECT_TRUE(map.all_zero());
- for (int i = 0; i < map.size(); i ++) {
- map.set_bit(i);
- for (int j = 0; j < i; j ++) {
- int n = map.find_next_set_bit(j);
- if (j <= i) {
- EXPECT_EQ(n, i);
- } else {
- EXPECT_EQ(n, -1);
- }
- }
- map.clr_bit(i);
- }
-}
TEST_VM(metaspace, leftoverbins_basics) {