changeset 11216:299de0f2244c

8047328: Improve memory usage for cards in SparsePRTEntry Summary: Use uint16_t for cards in a SparsePRTEntry, and use an additional integer to record the current position on where to add the next card. Reviewed-by: mgerdin, ehelin Contributed-by: Andreas Sjoberg <andreas.sjoberg@oracle.com>, Thomas Schatzl <thomas.schatzl@oracle.com>
author tschatzl
date Tue, 10 May 2016 16:42:14 +0200
parents 6b701219b703
children 8e3c3195f07f
files src/share/vm/gc/g1/heapRegionRemSet.cpp src/share/vm/gc/g1/sparsePRT.cpp src/share/vm/gc/g1/sparsePRT.hpp
diffstat 3 files changed, 86 insertions(+), 89 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/vm/gc/g1/heapRegionRemSet.cpp	Tue May 10 16:40:15 2016 +0200
+++ b/src/share/vm/gc/g1/heapRegionRemSet.cpp	Tue May 10 16:42:14 2016 +0200
@@ -103,7 +103,7 @@
       CardIdx_t from_card = (CardIdx_t)
           hw_offset >> (CardTableModRefBS::card_shift - LogHeapWordSize);
 
-      assert(0 <= from_card && (size_t)from_card < HeapRegion::CardsPerRegion,
+      assert((size_t)from_card < HeapRegion::CardsPerRegion,
              "Must be in range.");
       add_card_work(from_card, par);
     }
@@ -386,7 +386,7 @@
         uintptr_t(from_hr->bottom())
           >> CardTableModRefBS::card_shift;
       CardIdx_t card_index = from_card - from_hr_bot_card_index;
-      assert(0 <= card_index && (size_t)card_index < HeapRegion::CardsPerRegion,
+      assert((size_t)card_index < HeapRegion::CardsPerRegion,
              "Must be in range.");
       if (G1HRRSUseSparseTable &&
           _sparse_table.add_card(from_hrm_ind, card_index)) {
@@ -421,11 +421,9 @@
         // Transfer from sparse to fine-grain.
         SparsePRTEntry *sprt_entry = _sparse_table.get_entry(from_hrm_ind);
         assert(sprt_entry != NULL, "There should have been an entry");
-        for (int i = 0; i < SparsePRTEntry::cards_num(); i++) {
+        for (int i = 0; i < sprt_entry->num_valid_cards(); i++) {
           CardIdx_t c = sprt_entry->card(i);
-          if (c != SparsePRTEntry::NullEntry) {
-            prt->add_card(c);
-          }
+          prt->add_card(c);
         }
         // Now we can delete the sparse entry.
         bool res = _sparse_table.delete_entry(from_hrm_ind);
@@ -680,7 +678,7 @@
       uintptr_t(hr->bottom()) >> CardTableModRefBS::card_shift;
     assert(from_card >= hr_bot_card_index, "Inv");
     CardIdx_t card_index = from_card - hr_bot_card_index;
-    assert(0 <= card_index && (size_t)card_index < HeapRegion::CardsPerRegion,
+    assert((size_t)card_index < HeapRegion::CardsPerRegion,
            "Must be in range.");
     return _sparse_table.contains_card(hr_ind, card_index);
   }
--- a/src/share/vm/gc/g1/sparsePRT.cpp	Tue May 10 16:40:15 2016 +0200
+++ b/src/share/vm/gc/g1/sparsePRT.cpp	Tue May 10 16:42:14 2016 +0200
@@ -24,6 +24,7 @@
 
 #include "precompiled.hpp"
 #include "gc/g1/heapRegion.hpp"
+#include "gc/g1/heapRegionBounds.inline.hpp"
 #include "gc/g1/heapRegionRemSet.hpp"
 #include "gc/g1/sparsePRT.hpp"
 #include "gc/shared/cardTableModRefBS.hpp"
@@ -32,46 +33,54 @@
 #include "runtime/atomic.inline.hpp"
 #include "runtime/mutexLocker.hpp"
 
+// Check that the size of the SparsePRTEntry is evenly divisible by the maximum
+// member type to avoid SIGBUS when accessing them.
+STATIC_ASSERT(sizeof(SparsePRTEntry) % sizeof(int) == 0);
+
 void SparsePRTEntry::init(RegionIdx_t region_ind) {
+  // Check that the card array element type can represent all cards in the region.
+  // Choose a large SparsePRTEntry::card_elem_t (e.g. CardIdx_t) if required.
+  assert(((size_t)1 << (sizeof(SparsePRTEntry::card_elem_t) * BitsPerByte)) *
+         G1SATBCardTableModRefBS::card_size >= HeapRegionBounds::max_size(), "precondition");
+  assert(G1RSetSparseRegionEntries > 0, "precondition");
   _region_ind = region_ind;
-  _next_index = NullEntry;
-
-  for (int i = 0; i < cards_num(); i++) {
-    _cards[i] = NullEntry;
-  }
+  _next_index = RSHashTable::NullEntry;
+  _next_null = 0;
 }
 
 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const {
-  for (int i = 0; i < cards_num(); i++) {
-    if (_cards[i] == card_index) return true;
+  for (int i = 0; i < num_valid_cards(); i++) {
+    if (card(i) == card_index) {
+      return true;
+    }
   }
   return false;
 }
 
-int SparsePRTEntry::num_valid_cards() const {
-  int sum = 0;
-  for (int i = 0; i < cards_num(); i++) {
-    sum += (_cards[i] != NullEntry);
+SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {
+  for (int i = 0; i < num_valid_cards(); i++) {
+    if (card(i) == card_index) {
+      return found;
+    }
   }
-  return sum;
-}
-
-SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {
-  for (int i = 0; i < cards_num(); i++) {
-    CardIdx_t c = _cards[i];
-    if (c == card_index) return found;
-    if (c == NullEntry) { _cards[i] = card_index; return added; }
-  }
+  if (num_valid_cards() < cards_num() - 1) {
+    _cards[_next_null] = (card_elem_t)card_index;
+    _next_null++;
+    return added;
+   }
   // Otherwise, we're full.
   return overflow;
 }
 
-void SparsePRTEntry::copy_cards(CardIdx_t* cards) const {
-  memcpy(cards, _cards, cards_num() * sizeof(CardIdx_t));
+void SparsePRTEntry::copy_cards(card_elem_t* cards) const {
+  memcpy(cards, _cards, cards_num() * sizeof(card_elem_t));
 }
 
 void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const {
-  copy_cards(&e->_cards[0]);
+  copy_cards(e->_cards);
+  assert(_next_null >= 0, "invariant");
+  assert(_next_null <= cards_num(), "invariant");
+  e->_next_null = _next_null;
 }
 
 // ----------------------------------------------------------------------
@@ -127,16 +136,6 @@
   return res != SparsePRTEntry::overflow;
 }
 
-bool RSHashTable::get_cards(RegionIdx_t region_ind, CardIdx_t* cards) {
-  SparsePRTEntry* entry = get_entry(region_ind);
-  if (entry == NULL) {
-    return false;
-  }
-  // Otherwise...
-  entry->copy_cards(cards);
-  return true;
-}
-
 SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) const {
   int ind = (int) (region_ind & capacity_mask());
   int cur_ind = _buckets[ind];
@@ -218,17 +217,16 @@
 }
 
 CardIdx_t RSHashTableIter::find_first_card_in_list() {
-  CardIdx_t res;
   while (_bl_ind != RSHashTable::NullEntry) {
-    res = _rsht->entry(_bl_ind)->card(0);
-    if (res != SparsePRTEntry::NullEntry) {
-      return res;
+    SparsePRTEntry* sparse_entry = _rsht->entry(_bl_ind);
+    if (sparse_entry->num_valid_cards() > 0) {
+      return sparse_entry->card(0);
     } else {
-      _bl_ind = _rsht->entry(_bl_ind)->next_index();
+      _bl_ind = sparse_entry->next_index();
     }
   }
   // Otherwise, none found:
-  return SparsePRTEntry::NullEntry;
+  return NoCardFound;
 }
 
 size_t RSHashTableIter::compute_card_ind(CardIdx_t ci) {
@@ -237,20 +235,22 @@
 
 bool RSHashTableIter::has_next(size_t& card_index) {
   _card_ind++;
-  CardIdx_t ci;
-  if (_card_ind < SparsePRTEntry::cards_num() &&
-      ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) !=
-       SparsePRTEntry::NullEntry)) {
-    card_index = compute_card_ind(ci);
-    return true;
+  if (_bl_ind >= 0) {
+    SparsePRTEntry* e = _rsht->entry(_bl_ind);
+    if (_card_ind < e->num_valid_cards()) {
+      CardIdx_t ci = e->card(_card_ind);
+      card_index = compute_card_ind(ci);
+      return true;
+    }
   }
+
   // Otherwise, must find the next valid entry.
   _card_ind = 0;
 
   if (_bl_ind != RSHashTable::NullEntry) {
       _bl_ind = _rsht->entry(_bl_ind)->next_index();
-      ci = find_first_card_in_list();
-      if (ci != SparsePRTEntry::NullEntry) {
+      CardIdx_t ci = find_first_card_in_list();
+      if (ci != NoCardFound) {
         card_index = compute_card_ind(ci);
         return true;
       }
@@ -259,8 +259,8 @@
   _tbl_ind++;
   while ((size_t)_tbl_ind < _rsht->capacity()) {
     _bl_ind = _rsht->_buckets[_tbl_ind];
-    ci = find_first_card_in_list();
-    if (ci != SparsePRTEntry::NullEntry) {
+    CardIdx_t ci = find_first_card_in_list();
+    if (ci != NoCardFound) {
       card_index = compute_card_ind(ci);
       return true;
     }
@@ -389,10 +389,6 @@
   return _next->add_card(region_id, card_index);
 }
 
-bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) {
-  return _next->get_cards(region_id, cards);
-}
-
 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) {
   return _next->get_entry(region_id);
 }
--- a/src/share/vm/gc/g1/sparsePRT.hpp	Tue May 10 16:40:15 2016 +0200
+++ b/src/share/vm/gc/g1/sparsePRT.hpp	Tue May 10 16:42:14 2016 +0200
@@ -43,26 +43,32 @@
 // old versions synchronously.
 
 class SparsePRTEntry: public CHeapObj<mtGC> {
-public:
-  enum SomePublicConstants {
-    NullEntry     = -1,
-    UnrollFactor  =  4
-  };
 private:
+  // The type of a card entry.
+  typedef uint16_t card_elem_t;
+
+  // We need to make sizeof(SparsePRTEntry) an even multiple of maximum member size,
+  // in order to force correct alignment that could otherwise cause SIGBUS errors
+  // when reading the member variables. This calculates the minimum number of card
+  // array elements required to get that alignment.
+  static const size_t card_array_alignment = sizeof(int) / sizeof(card_elem_t);
+
   RegionIdx_t _region_ind;
   int         _next_index;
-  CardIdx_t   _cards[1];
+  int         _next_null;
+  // The actual cards stored in this array.
   // WARNING: Don't put any data members beyond this line. Card array has, in fact, variable length.
   // It should always be the last data member.
+  card_elem_t _cards[card_array_alignment];
+
+  // Copy the current entry's cards into "cards".
+  inline void copy_cards(card_elem_t* cards) const;
 public:
   // Returns the size of the entry, used for entry allocation.
-  static size_t size() { return sizeof(SparsePRTEntry) + sizeof(CardIdx_t) * (cards_num() - 1); }
+  static size_t size() { return sizeof(SparsePRTEntry) + sizeof(card_elem_t) * (cards_num() - card_array_alignment); }
   // Returns the size of the card array.
   static int cards_num() {
-    // The number of cards should be a multiple of 4, because that's our current
-    // unrolling factor.
-    static const int s = MAX2<int>(G1RSetSparseRegionEntries & ~(UnrollFactor - 1), UnrollFactor);
-    return s;
+    return align_size_up(G1RSetSparseRegionEntries, card_array_alignment);
   }
 
   // Set the region_ind to the given value, and delete all cards.
@@ -80,7 +86,7 @@
   inline bool contains_card(CardIdx_t card_index) const;
 
   // Returns the number of non-NULL card entries.
-  inline int num_valid_cards() const;
+  inline int num_valid_cards() const { return _next_null; }
 
   // Requires that the entry not contain the given card index.  If there is
   // space available, add the given card index to the entry and return
@@ -92,22 +98,20 @@
   };
   inline AddCardResult add_card(CardIdx_t card_index);
 
-  // Copy the current entry's cards into "cards".
-  inline void copy_cards(CardIdx_t* cards) const;
   // Copy the current entry's cards into the "_card" array of "e."
   inline void copy_cards(SparsePRTEntry* e) const;
 
-  inline CardIdx_t card(int i) const { return _cards[i]; }
+  inline CardIdx_t card(int i) const {
+    assert(i >= 0, "must be nonnegative");
+    assert(i < cards_num(), "range checking");
+    return (CardIdx_t)_cards[i];
+  }
 };
 
-
 class RSHashTable : public CHeapObj<mtGC> {
 
   friend class RSHashTableIter;
 
-  enum SomePrivateConstants {
-    NullEntry = -1
-  };
 
   // Inverse maximum hash table occupancy used.
   static float TableOccupancyFactor;
@@ -141,6 +145,8 @@
   RSHashTable(size_t capacity);
   ~RSHashTable();
 
+  static const int NullEntry = -1;
+
   bool should_expand() const { return _occupied_entries == _num_entries; }
 
   // Attempts to ensure that the given card_index in the given region is in
@@ -163,10 +169,10 @@
 
   void clear();
 
-  size_t capacity() const      { return _capacity;       }
+  size_t capacity() const      { return _capacity; }
   size_t capacity_mask() const { return _capacity_mask;  }
   size_t occupied_entries() const { return _occupied_entries; }
-  size_t occupied_cards() const   { return _occupied_cards;   }
+  size_t occupied_cards() const   { return _occupied_cards; }
   size_t mem_size() const;
   // The number of SparsePRTEntry instances available.
   size_t num_entries() const { return _num_entries; }
@@ -181,14 +187,17 @@
 
 // ValueObj because will be embedded in HRRS iterator.
 class RSHashTableIter VALUE_OBJ_CLASS_SPEC {
+  // Return value indicating "invalid/no card".
+  static const int NoCardFound = -1;
+
   int _tbl_ind;         // [-1, 0.._rsht->_capacity)
   int _bl_ind;          // [-1, 0.._rsht->_capacity)
   short _card_ind;      // [0..SparsePRTEntry::cards_num())
   RSHashTable* _rsht;
 
   // If the bucket list pointed to by _bl_ind contains a card, sets
-  // _bl_ind to the index of that entry, and returns the card.
-  // Otherwise, returns SparseEntry::NullEntry.
+  // _bl_ind to the index of that entry,
+  // Returns the card found if there is, otherwise returns InvalidCard.
   CardIdx_t find_first_card_in_list();
 
   // Computes the proper card index for the card whose offset in the
@@ -259,12 +268,6 @@
   // entries to a larger-capacity representation.
   bool add_card(RegionIdx_t region_id, CardIdx_t card_index);
 
-  // If the table hold an entry for "region_ind",  Copies its
-  // cards into "cards", which must be an array of length at least
-  // "SparePRTEntry::cards_num()", and returns "true"; otherwise,
-  // returns "false".
-  bool get_cards(RegionIdx_t region_ind, CardIdx_t* cards);
-
   // Return the pointer to the entry associated with the given region.
   SparsePRTEntry* get_entry(RegionIdx_t region_ind);