1 /*
   2  * Copyright (c) 2001, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "gc/g1/heapRegion.hpp"
  27 #include "gc/g1/heapRegionBounds.inline.hpp"
  28 #include "gc/g1/heapRegionRemSet.hpp"
  29 #include "gc/g1/sparsePRT.hpp"
  30 #include "gc/shared/cardTableBarrierSet.hpp"
  31 #include "gc/shared/space.inline.hpp"
  32 #include "memory/allocation.inline.hpp"
  33 #include "runtime/atomic.hpp"
  34 #include "runtime/mutexLocker.hpp"
  35 
  36 // Check that the size of the SparsePRTEntry is evenly divisible by the maximum
  37 // member type to avoid SIGBUS when accessing them.
  38 STATIC_ASSERT(sizeof(SparsePRTEntry) % sizeof(int) == 0);
  39 
  40 void SparsePRTEntry::init(RegionIdx_t region_ind) {
  41   // Check that the card array element type can represent all cards in the region.
  42   // Choose a large SparsePRTEntry::card_elem_t (e.g. CardIdx_t) if required.
  43   assert(((size_t)1 << (sizeof(SparsePRTEntry::card_elem_t) * BitsPerByte)) *
  44          G1CardTable::card_size >= HeapRegionBounds::max_size(), "precondition");
  45   assert(G1RSetSparseRegionEntries > 0, "precondition");
  46   _region_ind = region_ind;
  47   _next_index = RSHashTable::NullEntry;
  48   _next_null = 0;
  49 }
  50 
  51 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const {
  52   for (int i = 0; i < num_valid_cards(); i++) {
  53     if (card(i) == card_index) {
  54       return true;
  55     }
  56   }
  57   return false;
  58 }
  59 
  60 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {
  61   for (int i = 0; i < num_valid_cards(); i++) {
  62     if (card(i) == card_index) {
  63       return found;
  64     }
  65   }
  66   if (num_valid_cards() < cards_num() - 1) {
  67     _cards[_next_null] = (card_elem_t)card_index;
  68     _next_null++;
  69     return added;
  70    }
  71   // Otherwise, we're full.
  72   return overflow;
  73 }
  74 
  75 void SparsePRTEntry::copy_cards(card_elem_t* cards) const {
  76   memcpy(cards, _cards, cards_num() * sizeof(card_elem_t));
  77 }
  78 
  79 void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const {
  80   copy_cards(e->_cards);
  81   assert(_next_null >= 0, "invariant");
  82   assert(_next_null <= cards_num(), "invariant");
  83   e->_next_null = _next_null;
  84 }
  85 
  86 // ----------------------------------------------------------------------
  87 
  88 float RSHashTable::TableOccupancyFactor = 0.5f;
  89 
  90 RSHashTable::RSHashTable(size_t capacity) :
  91   _num_entries(0),
  92   _capacity(capacity),
  93   _capacity_mask(capacity-1),
  94   _occupied_entries(0),
  95   _occupied_cards(0),
  96   _entries(NULL),
  97   _buckets(NEW_C_HEAP_ARRAY(int, capacity, mtGC)),
  98   _free_region(0),
  99   _free_list(NullEntry)
 100 {
 101   _num_entries = (capacity * TableOccupancyFactor) + 1;
 102   _entries = (SparsePRTEntry*)NEW_C_HEAP_ARRAY(char, _num_entries * SparsePRTEntry::size(), mtGC);
 103   clear();
 104 }
 105 
 106 RSHashTable::~RSHashTable() {
 107   if (_entries != NULL) {
 108     FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries);
 109     _entries = NULL;
 110   }
 111   if (_buckets != NULL) {
 112     FREE_C_HEAP_ARRAY(int, _buckets);
 113     _buckets = NULL;
 114   }
 115 }
 116 
 117 void RSHashTable::clear() {
 118   _occupied_entries = 0;
 119   _occupied_cards = 0;
 120   guarantee(_entries != NULL, "INV");
 121   guarantee(_buckets != NULL, "INV");
 122 
 123   guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1,
 124                 "_capacity too large");
 125 
 126   // This will put -1 == NullEntry in the key field of all entries.
 127   memset((void*)_entries, NullEntry, _num_entries * SparsePRTEntry::size());
 128   memset((void*)_buckets, NullEntry, _capacity * sizeof(int));
 129   _free_list = NullEntry;
 130   _free_region = 0;
 131 }
 132 
 133 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) {
 134   SparsePRTEntry* e = entry_for_region_ind_create(region_ind);
 135   assert(e != NULL && e->r_ind() == region_ind,
 136          "Postcondition of call above.");
 137   SparsePRTEntry::AddCardResult res = e->add_card(card_index);
 138   if (res == SparsePRTEntry::added) _occupied_cards++;
 139   assert(e->num_valid_cards() > 0, "Postcondition");
 140   return res != SparsePRTEntry::overflow;
 141 }
 142 
 143 SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) const {
 144   int ind = (int) (region_ind & capacity_mask());
 145   int cur_ind = _buckets[ind];
 146   SparsePRTEntry* cur;
 147   while (cur_ind != NullEntry &&
 148          (cur = entry(cur_ind))->r_ind() != region_ind) {
 149     cur_ind = cur->next_index();
 150   }
 151 
 152   if (cur_ind == NullEntry) return NULL;
 153   // Otherwise...
 154   assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
 155   assert(cur->num_valid_cards() > 0, "Inv");
 156   return cur;
 157 }
 158 
 159 bool RSHashTable::delete_entry(RegionIdx_t region_ind) {
 160   int ind = (int) (region_ind & capacity_mask());
 161   int* prev_loc = &_buckets[ind];
 162   int cur_ind = *prev_loc;
 163   SparsePRTEntry* cur;
 164   while (cur_ind != NullEntry &&
 165          (cur = entry(cur_ind))->r_ind() != region_ind) {
 166     prev_loc = cur->next_index_addr();
 167     cur_ind = *prev_loc;
 168   }
 169 
 170   if (cur_ind == NullEntry) return false;
 171   // Otherwise, splice out "cur".
 172   *prev_loc = cur->next_index();
 173   _occupied_cards -= cur->num_valid_cards();
 174   free_entry(cur_ind);
 175   _occupied_entries--;
 176   return true;
 177 }
 178 
 179 SparsePRTEntry*
 180 RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) {
 181   SparsePRTEntry* res = get_entry(region_ind);
 182   if (res == NULL) {
 183     int new_ind = alloc_entry();
 184     res = entry(new_ind);
 185     res->init(region_ind);
 186     // Insert at front.
 187     int ind = (int) (region_ind & capacity_mask());
 188     res->set_next_index(_buckets[ind]);
 189     _buckets[ind] = new_ind;
 190     _occupied_entries++;
 191   }
 192   return res;
 193 }
 194 
 195 int RSHashTable::alloc_entry() {
 196   int res;
 197   if (_free_list != NullEntry) {
 198     res = _free_list;
 199     _free_list = entry(res)->next_index();
 200     return res;
 201   } else if ((size_t)_free_region < _num_entries) {
 202     res = _free_region;
 203     _free_region++;
 204     return res;
 205   } else {
 206     return NullEntry;
 207   }
 208 }
 209 
 210 void RSHashTable::free_entry(int fi) {
 211   entry(fi)->set_next_index(_free_list);
 212   _free_list = fi;
 213 }
 214 
 215 void RSHashTable::add_entry(SparsePRTEntry* e) {
 216   assert(e->num_valid_cards() > 0, "Precondition.");
 217   SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind());
 218   e->copy_cards(e2);
 219   _occupied_cards += e2->num_valid_cards();
 220   assert(e2->num_valid_cards() > 0, "Postcondition.");
 221 }
 222 
 223 CardIdx_t RSHashTableIter::find_first_card_in_list() {
 224   while (_bl_ind != RSHashTable::NullEntry) {
 225     SparsePRTEntry* sparse_entry = _rsht->entry(_bl_ind);
 226     if (sparse_entry->num_valid_cards() > 0) {
 227       return sparse_entry->card(0);
 228     } else {
 229       _bl_ind = sparse_entry->next_index();
 230     }
 231   }
 232   // Otherwise, none found:
 233   return NoCardFound;
 234 }
 235 
 236 size_t RSHashTableIter::compute_card_ind(CardIdx_t ci) {
 237   return (_rsht->entry(_bl_ind)->r_ind() * HeapRegion::CardsPerRegion) + ci;
 238 }
 239 
 240 bool RSHashTableIter::has_next(size_t& card_index) {
 241   _card_ind++;
 242   if (_bl_ind >= 0) {
 243     SparsePRTEntry* e = _rsht->entry(_bl_ind);
 244     if (_card_ind < e->num_valid_cards()) {
 245       CardIdx_t ci = e->card(_card_ind);
 246       card_index = compute_card_ind(ci);
 247       return true;
 248     }
 249   }
 250 
 251   // Otherwise, must find the next valid entry.
 252   _card_ind = 0;
 253 
 254   if (_bl_ind != RSHashTable::NullEntry) {
 255       _bl_ind = _rsht->entry(_bl_ind)->next_index();
 256       CardIdx_t ci = find_first_card_in_list();
 257       if (ci != NoCardFound) {
 258         card_index = compute_card_ind(ci);
 259         return true;
 260       }
 261   }
 262   // If we didn't return above, must go to the next non-null table index.
 263   _tbl_ind++;
 264   while ((size_t)_tbl_ind < _rsht->capacity()) {
 265     _bl_ind = _rsht->_buckets[_tbl_ind];
 266     CardIdx_t ci = find_first_card_in_list();
 267     if (ci != NoCardFound) {
 268       card_index = compute_card_ind(ci);
 269       return true;
 270     }
 271     // Otherwise, try next entry.
 272     _tbl_ind++;
 273   }
 274   // Otherwise, there were no entry.
 275   return false;
 276 }
 277 
 278 bool RSHashTableBucketIter::has_next(SparsePRTEntry*& entry) {
 279   while (_bl_ind == RSHashTable::NullEntry)  {
 280     if (_tbl_ind == (int)_rsht->capacity() - 1) {
 281       return false;
 282     }
 283     _tbl_ind++;
 284     _bl_ind = _rsht->_buckets[_tbl_ind];
 285   }
 286   entry = _rsht->entry(_bl_ind);
 287   _bl_ind = entry->next_index();
 288   return true;
 289 }
 290 
 291 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
 292   SparsePRTEntry* e = get_entry(region_index);
 293   return (e != NULL && e->contains_card(card_index));
 294 }
 295 
 296 size_t RSHashTable::mem_size() const {
 297   return sizeof(RSHashTable) +
 298     _num_entries * (SparsePRTEntry::size() + sizeof(int));
 299 }
 300 
 301 // ----------------------------------------------------------------------
 302 
 303 SparsePRT::SparsePRT() :
 304   _table(new RSHashTable(InitialCapacity)) {
 305 }
 306 
 307 
 308 SparsePRT::~SparsePRT() {
 309   delete _table;
 310 }
 311 
 312 
 313 size_t SparsePRT::mem_size() const {
 314   // We ignore "_cur" here, because it either = _next, or else it is
 315   // on the deleted list.
 316   return sizeof(SparsePRT) + _table->mem_size();
 317 }
 318 
 319 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) {
 320   if (_table->should_expand()) {
 321     expand();
 322   }
 323   return _table->add_card(region_id, card_index);
 324 }
 325 
 326 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) {
 327   return _table->get_entry(region_id);
 328 }
 329 
 330 bool SparsePRT::delete_entry(RegionIdx_t region_id) {
 331   return _table->delete_entry(region_id);
 332 }
 333 
 334 void SparsePRT::clear() {
 335   // If the entry table is not at initial capacity, just create a new one.
 336   if (_table->capacity() != InitialCapacity) {
 337     delete _table;
 338     _table = new RSHashTable(InitialCapacity);
 339   } else {
 340     _table->clear();
 341   }
 342 }
 343 
 344 void SparsePRT::expand() {
 345   RSHashTable* last = _table;
 346   _table = new RSHashTable(last->capacity() * 2);
 347   for (size_t i = 0; i < last->num_entries(); i++) {
 348     SparsePRTEntry* e = last->entry((int)i);
 349     if (e->valid_entry()) {
 350       _table->add_entry(e);
 351     }
 352   }
 353   delete last;
 354 }