# HG changeset patch
# User stuefe
# Date 1574764160 -3600
# Node ID 1558266946de51bb6cdab73726037d2b1a7278d2
# Parent  990b1fed3b47412e1284a06bf6265c028d9f698f
Improve BLA and LOM tests

diff -r 990b1fed3b47 -r 1558266946de src/hotspot/share/memory/metaspace/blockListArray.hpp
--- a/src/hotspot/share/memory/metaspace/blockListArray.hpp	Mon Nov 25 16:35:14 2019 +0100
+++ b/src/hotspot/share/memory/metaspace/blockListArray.hpp	Tue Nov 26 11:29:20 2019 +0100
@@ -64,8 +64,8 @@
   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.
+  // Starting at the position following pos, find the 1 bit.
+  // Return its position, or -1 if not found.
   inline int find_next_set_bit(int pos) const;
 
   static int size() { return sizeof(mask_type) * 8; }
@@ -146,6 +146,9 @@
 
   void print(outputStream* st) const;
 
+  // Returns true if the array contains no blocks.
+  bool is_empty() const { return _map.all_zero(); }
+
 };
 
 
diff -r 990b1fed3b47 -r 1558266946de src/hotspot/share/memory/metaspace/blockListArray.inline.hpp
--- a/src/hotspot/share/memory/metaspace/blockListArray.inline.hpp	Mon Nov 25 16:35:14 2019 +0100
+++ b/src/hotspot/share/memory/metaspace/blockListArray.inline.hpp	Tue Nov 26 11:29:20 2019 +0100
@@ -38,22 +38,17 @@
 // Starting at (including) pos, find the position of the next 1 bit.
 // Return -1 if not found.
 int BlockListArrayMask::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;
+  if (m2 == 0) {
+    return -1;
   }
-  return -1;
-
+  while ((m2 & (mask_type)1) == 0) {
+    m2 >>= 1;
+    pos2 ++;
+  }
+  return pos2;
 }
 
 ///////////////////////////////////////
@@ -73,13 +68,17 @@
 
 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);
+  // First look at the bin holding the band word_size is in. But if the spread is > 1,
+  // the topmost block in the bin may actually be too small to hold word_size (note that
+  // blocks in the bin list are unsorted). Still worth a look.
+  if (_bins[bno] != NULL && _bins[bno]->size >= word_size) {
+    // found a fit.
+  } else {
+    // Did not find a fit. Look in the larger bins.
+    bno = _map.find_next_set_bit(bno);
   }
-  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");
@@ -110,6 +109,8 @@
 
 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 {
+  stats->num_blocks = 0;
+  stats->word_size = 0;
   for (int i = 0; i < num_bins; i ++) {
     for(block_t* b = _bins[i]; b != NULL; b = b->next) {
       stats->num_blocks ++;
diff -r 990b1fed3b47 -r 1558266946de src/hotspot/share/memory/metaspace/leftOverBins.hpp
--- a/src/hotspot/share/memory/metaspace/leftOverBins.hpp	Mon Nov 25 16:35:14 2019 +0100
+++ b/src/hotspot/share/memory/metaspace/leftOverBins.hpp	Tue Nov 26 11:29:20 2019 +0100
@@ -96,6 +96,10 @@
 
   void print(outputStream* st, bool detailed = false) const;
 
+  bool is_empty() const {
+    return _very_small_bins.is_empty() && _current == NULL;
+  }
+
   size_t total_word_size() const { return _total_word_size.get(); }
 
 };
diff -r 990b1fed3b47 -r 1558266946de test/hotspot/gtest/metaspace/metaspaceTestsCommon.hpp
--- a/test/hotspot/gtest/metaspace/metaspaceTestsCommon.hpp	Mon Nov 25 16:35:14 2019 +0100
+++ b/test/hotspot/gtest/metaspace/metaspaceTestsCommon.hpp	Tue Nov 26 11:29:20 2019 +0100
@@ -227,5 +227,33 @@
 
 size_t get_workingset_size();
 
+// A simple preallocated buffer used to "feed" someone.
+// Mimicks chunk retirement leftover blocks.
+class FeederBuffer {
+
+  MetaWord* _buf;
+  const size_t _size;
+  size_t _used;
+
+public:
+
+  FeederBuffer(size_t size) : _buf(NULL), _size(size), _used(0) {
+    _buf = NEW_C_HEAP_ARRAY(MetaWord, _size, mtInternal);
+  }
+
+  ~FeederBuffer() {
+    FREE_C_HEAP_ARRAY(MetaWord, _buf);
+  }
+
+  MetaWord* get(size_t word_size) {
+    if (_used > (_size - word_size)) {
+      return NULL;
+    }
+    MetaWord* p = _buf + _used;
+    _used += word_size;
+    return p;
+  }
+
+};
 
 #endif // GTEST_METASPACE_METASPACETESTCOMMON_HPP
diff -r 990b1fed3b47 -r 1558266946de test/hotspot/gtest/metaspace/test_blockListArray.cpp
--- a/test/hotspot/gtest/metaspace/test_blockListArray.cpp	Mon Nov 25 16:35:14 2019 +0100
+++ b/test/hotspot/gtest/metaspace/test_blockListArray.cpp	Tue Nov 26 11:29:20 2019 +0100
@@ -31,7 +31,7 @@
 
 TEST_VM(metaspace, BlockListFreeMap_mask_basic) {
   // Basic tests
-  metaspace::BlockListFreeMap map;
+  metaspace::BlockListArrayMask map;
   EXPECT_TRUE(map.all_zero());
   for (int i = 0; i < map.size(); i ++) {
     map.set_bit(i);
@@ -43,13 +43,13 @@
 }
 
 TEST_VM(metaspace, BlockListFreeMap_mask_find_next_set_bit) {
-  metaspace::BlockListFreeMap map;
+  metaspace::BlockListArrayMask 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) {
+      if (j < i) {
         EXPECT_EQ(n, i);
       } else {
         EXPECT_EQ(n, -1);
@@ -59,3 +59,115 @@
   }
 }
 
+#define CHECK_BLA_CONTENT(BLA, NUM_EXPECTED, SIZE_EXPECTED) \
+{ \
+  metaspace::block_stats_t stat; \
+  memset(&stat, 0xFF, sizeof(stat)); \
+  BLA.statistics(&stat); \
+  ASSERT_EQ(stat.num_blocks, (int)NUM_EXPECTED); \
+  ASSERT_EQ(stat.word_size, (size_t)SIZE_EXPECTED); \
+  if (NUM_EXPECTED == 0) { \
+	  ASSERT_TRUE(BLA.is_empty()); \
+  } else { \
+	  ASSERT_FALSE(BLA.is_empty()); \
+  } \
+}
+
+
+
+TEST_VM(metaspace, BlockListArray_basic) {
+
+  metaspace::BlockListArray<100, 5, 20> bla;
+  ASSERT_EQ(bla.maximal_word_size(), (size_t)200);
+  ASSERT_EQ(bla.minimal_word_size(), (size_t)100);
+
+  CHECK_BLA_CONTENT(bla, 0, 0);
+
+  // Put something into the bla and check bla.
+  // Take something out of the bla; any allocation smaller
+  // than the one block in it shall succeed.
+  MetaWord tmp[1024];
+
+  for (size_t feeding_size = 100; feeding_size < 200; feeding_size ++) {
+    for (size_t l = 100; l < 200; l ++) {
+      LOG(SIZE_FORMAT "-" SIZE_FORMAT, feeding_size, l);
+
+      bla.put(tmp, feeding_size);
+      CHECK_BLA_CONTENT(bla, 1, feeding_size);
+
+      metaspace::block_t* b = bla.get(l);
+
+      if (l <= feeding_size) {
+        // We expect the get() to work and return the block we just put in
+        // if the size we ask for is smaller than the size we put in.
+        ASSERT_NOT_NULL(b);
+        ASSERT_EQ((MetaWord*) b, tmp);
+        ASSERT_EQ(b->size, feeding_size);
+        CHECK_BLA_CONTENT(bla, 0, 0);
+        memset(b, 0xDE, b->size * sizeof(MetaWord));
+      } else {
+        // Otherwise we expect the bla to be unchanged.
+        assert(b == NULL, "s");
+        ASSERT_NULL(b);
+        CHECK_BLA_CONTENT(bla, 1, feeding_size);
+      }
+      DEBUG_ONLY(bla.verify();)
+
+      // Regardless of bla's state, empty it out for the next iteration.
+      bla.get(feeding_size);
+      CHECK_BLA_CONTENT(bla, 0, 0);
+    }
+  }
+}
+
+TEST_VM(metaspace, BlockListArray_fill_and_drain) {
+
+  metaspace::BlockListArray<100, 5, 20> bla;
+  ASSERT_EQ(bla.maximal_word_size(), (size_t)200);
+  ASSERT_EQ(bla.minimal_word_size(), (size_t)100);
+
+  CHECK_BLA_CONTENT(bla, 0, 0);
+
+  // Now feed it some memory:
+  FeederBuffer fb(16 * K);
+  RandSizeGenerator rgen(100, 200);
+  int num_fed = 0;
+  size_t size_fed = 0;
+  MetaWord* p = NULL;
+  do {
+    const size_t s = rgen.get();
+    p = fb.get(s);
+    if (p != NULL) {
+      num_fed ++;
+      size_fed += s;
+      bla.put(p, s);
+      CHECK_BLA_CONTENT(bla, num_fed, size_fed);
+    }
+  } while (p != NULL);
+
+  DEBUG_ONLY(bla.verify();)
+
+  // Now remove memory until empty:
+  int num_retrieved = 0;
+  size_t size_retrieved = 0;
+  metaspace::block_t* b = NULL;
+  do {
+    const size_t s = rgen.get();
+    metaspace::block_t* b = bla.get(s);
+    if (p != NULL) {
+      ASSERT_GE(b->size, s);
+      num_retrieved ++;
+      size_retrieved += b->size;
+      memset(b, 0xDE, b->size * BytesPerWord);
+      CHECK_BLA_CONTENT(bla, num_fed - num_retrieved,
+                             size_fed - size_retrieved);
+      ASSERT_LE(num_retrieved, num_fed);
+      ASSERT_LE(size_retrieved, size_fed);
+    }
+
+  } while (p != NULL);
+
+  DEBUG_ONLY(bla.verify();)
+
+}
+
diff -r 990b1fed3b47 -r 1558266946de test/hotspot/gtest/metaspace/test_leftOverBins.cpp
--- a/test/hotspot/gtest/metaspace/test_leftOverBins.cpp	Mon Nov 25 16:35:14 2019 +0100
+++ b/test/hotspot/gtest/metaspace/test_leftOverBins.cpp	Tue Nov 26 11:29:20 2019 +0100
@@ -29,36 +29,24 @@
 
 #include "metaspaceTestsCommon.hpp"
 
-class LeftOverBinsTest {
-
-  // A simple preallocated buffer used to "feed" the allocator.
-  // Mimicks chunk retirement leftover blocks.
-  class FeederBuffer {
-
-    static const size_t buf_word_size = 512 * K;
-    MetaWord* _buf;
-    size_t _used;
-
-  public:
+#define CHECK_LOM_CONTENT(lom, num_blocks_expected, word_size_expected) \
+{ \
+  if (word_size_expected > 0) { \
+    EXPECT_FALSE(lom.is_empty()); \
+  } else { \
+    EXPECT_TRUE(lom.is_empty()); \
+  } \
+  EXPECT_EQ(lom.total_word_size(), (size_t)word_size_expected); \
+  metaspace::block_stats_t s; \
+  memset(&s, 0xDD, sizeof(s)); \
+  lom.statistics(&s); \
+  EXPECT_EQ((size_t)word_size_expected, s.word_size); \
+  if (num_blocks_expected >= 0) { \
+	  EXPECT_EQ(num_blocks_expected, s.num_blocks); \
+  } \
+}
 
-    FeederBuffer() : _used(0) {
-      _buf = NEW_C_HEAP_ARRAY(MetaWord, buf_word_size, mtInternal);
-    }
-
-    ~FeederBuffer() {
-      FREE_C_HEAP_ARRAY(MetaWord, _buf);
-    }
-
-    MetaWord* get(size_t word_size) {
-      if (_used > (buf_word_size - word_size)) {
-        return NULL;
-      }
-      MetaWord* p = _buf + _used;
-      _used += word_size;
-      return p;
-    }
-
-  };
+class LeftOverBinsTest {
 
   FeederBuffer _fb;
   LeftOverManager _lom;
@@ -80,7 +68,6 @@
   // Array of the same size as the pool max capacity; holds the allocated elements.
   allocation_t* _allocations;
 
-
   int _num_allocs;
   int _num_deallocs;
   int _num_feeds;
@@ -187,14 +174,16 @@
 public:
 
   LeftOverBinsTest(size_t avg_alloc_size) :
-    _fb(), _lom(),
+    _fb(512 * K), _lom(),
     _rgen_feeding(128, 4096),
     _rgen_allocations(avg_alloc_size / 4, avg_alloc_size * 2, 0.01f, avg_alloc_size / 3, avg_alloc_size * 30),
     _allocations(NULL),
     _num_allocs(0), _num_deallocs(0), _num_feeds(0)
   {
+    CHECK_LOM_CONTENT(_lom, 0, 0);
     // some initial feeding
     _lom.add_block(_fb.get(1024), 1024);
+    CHECK_LOM_CONTENT(_lom, 1, 1024);
   }
 
 
@@ -222,21 +211,18 @@
   LeftOverManager lom;
   MetaWord tmp[1024];
   metaspace::block_stats_t stats;
+  CHECK_LOM_CONTENT(lom, 0, 0);
 
   lom.add_block(tmp, 1024);
   DEBUG_ONLY(lom.verify();)
-
-  lom.statistics(&stats);
-  EXPECT_EQ(stats.num_blocks, 1);
-  EXPECT_EQ(stats.word_size, (size_t)1024);
+  ASSERT_FALSE(lom.is_empty());
+  CHECK_LOM_CONTENT(lom, 1, 1024);
 
   MetaWord* p = lom.get_block(1024);
   EXPECT_EQ(p, tmp);
   DEBUG_ONLY(lom.verify();)
+  CHECK_LOM_CONTENT(lom, 0, 0);
 
-  lom.statistics(&stats);
-  EXPECT_EQ(stats.num_blocks, 0);
-  EXPECT_EQ(stats.word_size, (size_t)0);
 }
 
 TEST_VM(metaspace, leftoverbins_small) {