# HG changeset patch # User stuefe # Date 1574503516 -3600 # Node ID 6ce12ce00d3eb6fed521d79f7849e71a218e68e5 # Parent b537e638630695590650beac40a96a648745d0d1 Factor out block list array from LOM since we may use it elsewhere diff -r b537e6386306 -r 6ce12ce00d3e src/hotspot/share/memory/metaspace/blockListArray.hpp --- /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 diff -r b537e6386306 -r 6ce12ce00d3e src/hotspot/share/memory/metaspace/blockListArray.inline.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 +void BlockListArray::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 +block_t* BlockListArray::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 +void BlockListArray::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 +void BlockListArray::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 +void BlockListArray::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 diff -r b537e6386306 -r 6ce12ce00d3e src/hotspot/share/memory/metaspace/leftOverBins.cpp --- 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" diff -r b537e6386306 -r 6ce12ce00d3e src/hotspot/share/memory/metaspace/leftOverBins.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 { - typedef Bins<2, 2, 16> VerySmallBinsType; + typedef BlockListArray<2, 2, 16> VerySmallBinsType; VerySmallBinsType _very_small_bins; block_t* _large_block_reserve; diff -r b537e6386306 -r 6ce12ce00d3e src/hotspot/share/memory/metaspace/leftOverBins.inline.hpp --- 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 -void 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 -block_t* 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 -void 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 -void 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 -void 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 diff -r b537e6386306 -r 6ce12ce00d3e test/hotspot/gtest/metaspace/metaspaceTestsCommon.hpp --- 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" diff -r b537e6386306 -r 6ce12ce00d3e test/hotspot/gtest/metaspace/test_blockListArray.cpp --- /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); + } +} + diff -r b537e6386306 -r 6ce12ce00d3e test/hotspot/gtest/metaspace/test_leftOverBins.cpp --- 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) {