1 /*
   2  * Copyright (c) 2001, 2010, 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_implementation/g1/heapRegion.hpp"
  27 #include "gc_implementation/g1/heapRegionRemSet.hpp"
  28 #include "gc_implementation/g1/sparsePRT.hpp"
  29 #include "memory/allocation.inline.hpp"
  30 #include "memory/cardTableModRefBS.hpp"
  31 #include "memory/space.inline.hpp"
  32 #include "runtime/mutexLocker.hpp"
  33 
  34 #define SPARSE_PRT_VERBOSE 0
  35 
  36 #define UNROLL_CARD_LOOPS  1
  37 
  38 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) {
  39     sprt_iter->init(this);
  40 }
  41 
  42 void SparsePRTEntry::init(RegionIdx_t region_ind) {
  43   _region_ind = region_ind;
  44   _next_index = NullEntry;
  45 
  46 #if UNROLL_CARD_LOOPS
  47   assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
  48   for (int i = 0; i < cards_num(); i += UnrollFactor) {
  49     _cards[i] = NullEntry;
  50     _cards[i + 1] = NullEntry;
  51     _cards[i + 2] = NullEntry;
  52     _cards[i + 3] = NullEntry;
  53   }
  54 #else
  55   for (int i = 0; i < cards_num(); i++)
  56     _cards[i] = NullEntry;
  57 #endif
  58 }
  59 
  60 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const {
  61 #if UNROLL_CARD_LOOPS
  62   assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
  63   for (int i = 0; i < cards_num(); i += UnrollFactor) {
  64     if (_cards[i] == card_index ||
  65         _cards[i + 1] == card_index ||
  66         _cards[i + 2] == card_index ||
  67         _cards[i + 3] == card_index) return true;
  68   }
  69 #else
  70   for (int i = 0; i < cards_num(); i++) {
  71     if (_cards[i] == card_index) return true;
  72   }
  73 #endif
  74   // Otherwise, we're full.
  75   return false;
  76 }
  77 
  78 int SparsePRTEntry::num_valid_cards() const {
  79   int sum = 0;
  80 #if UNROLL_CARD_LOOPS
  81   assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
  82   for (int i = 0; i < cards_num(); i += UnrollFactor) {
  83     sum += (_cards[i] != NullEntry);
  84     sum += (_cards[i + 1] != NullEntry);
  85     sum += (_cards[i + 2] != NullEntry);
  86     sum += (_cards[i + 3] != NullEntry);
  87   }
  88 #else
  89   for (int i = 0; i < cards_num(); i++) {
  90     sum += (_cards[i] != NullEntry);
  91   }
  92 #endif
  93   // Otherwise, we're full.
  94   return sum;
  95 }
  96 
  97 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {
  98 #if UNROLL_CARD_LOOPS
  99   assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
 100   CardIdx_t c;
 101   for (int i = 0; i < cards_num(); i += UnrollFactor) {
 102     c = _cards[i];
 103     if (c == card_index) return found;
 104     if (c == NullEntry) { _cards[i] = card_index; return added; }
 105     c = _cards[i + 1];
 106     if (c == card_index) return found;
 107     if (c == NullEntry) { _cards[i + 1] = card_index; return added; }
 108     c = _cards[i + 2];
 109     if (c == card_index) return found;
 110     if (c == NullEntry) { _cards[i + 2] = card_index; return added; }
 111     c = _cards[i + 3];
 112     if (c == card_index) return found;
 113     if (c == NullEntry) { _cards[i + 3] = card_index; return added; }
 114   }
 115 #else
 116   for (int i = 0; i < cards_num(); i++) {
 117     CardIdx_t c = _cards[i];
 118     if (c == card_index) return found;
 119     if (c == NullEntry) { _cards[i] = card_index; return added; }
 120   }
 121 #endif
 122   // Otherwise, we're full.
 123   return overflow;
 124 }
 125 
 126 void SparsePRTEntry::copy_cards(CardIdx_t* cards) const {
 127 #if UNROLL_CARD_LOOPS
 128   assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
 129   for (int i = 0; i < cards_num(); i += UnrollFactor) {
 130     cards[i] = _cards[i];
 131     cards[i + 1] = _cards[i + 1];
 132     cards[i + 2] = _cards[i + 2];
 133     cards[i + 3] = _cards[i + 3];
 134   }
 135 #else
 136   for (int i = 0; i < cards_num(); i++) {
 137     cards[i] = _cards[i];
 138   }
 139 #endif
 140 }
 141 
 142 void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const {
 143   copy_cards(&e->_cards[0]);
 144 }
 145 
 146 // ----------------------------------------------------------------------
 147 
 148 RSHashTable::RSHashTable(size_t capacity) :
 149   _capacity(capacity), _capacity_mask(capacity-1),
 150   _occupied_entries(0), _occupied_cards(0),
 151   _entries((SparsePRTEntry*)NEW_C_HEAP_ARRAY(char, SparsePRTEntry::size() * capacity)),
 152   _buckets(NEW_C_HEAP_ARRAY(int, capacity)),
 153   _free_list(NullEntry), _free_region(0)
 154 {
 155   clear();
 156 }
 157 
 158 RSHashTable::~RSHashTable() {
 159   if (_entries != NULL) {
 160     FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries);
 161     _entries = NULL;
 162   }
 163   if (_buckets != NULL) {
 164     FREE_C_HEAP_ARRAY(int, _buckets);
 165     _buckets = NULL;
 166   }
 167 }
 168 
 169 void RSHashTable::clear() {
 170   _occupied_entries = 0;
 171   _occupied_cards = 0;
 172   guarantee(_entries != NULL, "INV");
 173   guarantee(_buckets != NULL, "INV");
 174 
 175   guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1,
 176                 "_capacity too large");
 177 
 178   // This will put -1 == NullEntry in the key field of all entries.
 179   memset(_entries, NullEntry, _capacity * SparsePRTEntry::size());
 180   memset(_buckets, NullEntry, _capacity * sizeof(int));
 181   _free_list = NullEntry;
 182   _free_region = 0;
 183 }
 184 
 185 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) {
 186   SparsePRTEntry* e = entry_for_region_ind_create(region_ind);
 187   assert(e != NULL && e->r_ind() == region_ind,
 188          "Postcondition of call above.");
 189   SparsePRTEntry::AddCardResult res = e->add_card(card_index);
 190   if (res == SparsePRTEntry::added) _occupied_cards++;
 191 #if SPARSE_PRT_VERBOSE
 192   gclog_or_tty->print_cr("       after add_card[%d]: valid-cards = %d.",
 193                          pointer_delta(e, _entries, SparsePRTEntry::size()),
 194                          e->num_valid_cards());
 195 #endif
 196   assert(e->num_valid_cards() > 0, "Postcondition");
 197   return res != SparsePRTEntry::overflow;
 198 }
 199 
 200 bool RSHashTable::get_cards(RegionIdx_t region_ind, CardIdx_t* cards) {
 201   int ind = (int) (region_ind & capacity_mask());
 202   int cur_ind = _buckets[ind];
 203   SparsePRTEntry* cur;
 204   while (cur_ind != NullEntry &&
 205          (cur = entry(cur_ind))->r_ind() != region_ind) {
 206     cur_ind = cur->next_index();
 207   }
 208 
 209   if (cur_ind == NullEntry) return false;
 210   // Otherwise...
 211   assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
 212   assert(cur->num_valid_cards() > 0, "Inv");
 213   cur->copy_cards(cards);
 214   return true;
 215 }
 216 
 217 SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) {
 218   int ind = (int) (region_ind & capacity_mask());
 219   int cur_ind = _buckets[ind];
 220   SparsePRTEntry* cur;
 221   while (cur_ind != NullEntry &&
 222          (cur = entry(cur_ind))->r_ind() != region_ind) {
 223     cur_ind = cur->next_index();
 224   }
 225 
 226   if (cur_ind == NullEntry) return NULL;
 227   // Otherwise...
 228   assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
 229   assert(cur->num_valid_cards() > 0, "Inv");
 230   return cur;
 231 }
 232 
 233 bool RSHashTable::delete_entry(RegionIdx_t region_ind) {
 234   int ind = (int) (region_ind & capacity_mask());
 235   int* prev_loc = &_buckets[ind];
 236   int cur_ind = *prev_loc;
 237   SparsePRTEntry* cur;
 238   while (cur_ind != NullEntry &&
 239          (cur = entry(cur_ind))->r_ind() != region_ind) {
 240     prev_loc = cur->next_index_addr();
 241     cur_ind = *prev_loc;
 242   }
 243 
 244   if (cur_ind == NullEntry) return false;
 245   // Otherwise, splice out "cur".
 246   *prev_loc = cur->next_index();
 247   _occupied_cards -= cur->num_valid_cards();
 248   free_entry(cur_ind);
 249   _occupied_entries--;
 250   return true;
 251 }
 252 
 253 SparsePRTEntry*
 254 RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const {
 255   assert(occupied_entries() < capacity(), "Precondition");
 256   int ind = (int) (region_ind & capacity_mask());
 257   int cur_ind = _buckets[ind];
 258   SparsePRTEntry* cur;
 259   while (cur_ind != NullEntry &&
 260          (cur = entry(cur_ind))->r_ind() != region_ind) {
 261     cur_ind = cur->next_index();
 262   }
 263 
 264   if (cur_ind != NullEntry) {
 265     assert(cur->r_ind() == region_ind, "Loop postcondition + test");
 266     return cur;
 267   } else {
 268     return NULL;
 269   }
 270 }
 271 
 272 SparsePRTEntry*
 273 RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) {
 274   SparsePRTEntry* res = entry_for_region_ind(region_ind);
 275   if (res == NULL) {
 276     int new_ind = alloc_entry();
 277     assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room.");
 278     res = entry(new_ind);
 279     res->init(region_ind);
 280     // Insert at front.
 281     int ind = (int) (region_ind & capacity_mask());
 282     res->set_next_index(_buckets[ind]);
 283     _buckets[ind] = new_ind;
 284     _occupied_entries++;
 285   }
 286   return res;
 287 }
 288 
 289 int RSHashTable::alloc_entry() {
 290   int res;
 291   if (_free_list != NullEntry) {
 292     res = _free_list;
 293     _free_list = entry(res)->next_index();
 294     return res;
 295   } else if ((size_t) _free_region+1 < capacity()) {
 296     res = _free_region;
 297     _free_region++;
 298     return res;
 299   } else {
 300     return NullEntry;
 301   }
 302 }
 303 
 304 void RSHashTable::free_entry(int fi) {
 305   entry(fi)->set_next_index(_free_list);
 306   _free_list = fi;
 307 }
 308 
 309 void RSHashTable::add_entry(SparsePRTEntry* e) {
 310   assert(e->num_valid_cards() > 0, "Precondition.");
 311   SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind());
 312   e->copy_cards(e2);
 313   _occupied_cards += e2->num_valid_cards();
 314   assert(e2->num_valid_cards() > 0, "Postcondition.");
 315 }
 316 
 317 CardIdx_t /* RSHashTable:: */ RSHashTableIter::find_first_card_in_list() {
 318   CardIdx_t res;
 319   while (_bl_ind != RSHashTable::NullEntry) {
 320     res = _rsht->entry(_bl_ind)->card(0);
 321     if (res != SparsePRTEntry::NullEntry) {
 322       return res;
 323     } else {
 324       _bl_ind = _rsht->entry(_bl_ind)->next_index();
 325     }
 326   }
 327   // Otherwise, none found:
 328   return SparsePRTEntry::NullEntry;
 329 }
 330 
 331 size_t /* RSHashTable:: */ RSHashTableIter::compute_card_ind(CardIdx_t ci) {
 332   return
 333     _heap_bot_card_ind
 334     + (_rsht->entry(_bl_ind)->r_ind() * HeapRegion::CardsPerRegion)
 335     + ci;
 336 }
 337 
 338 bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) {
 339   _card_ind++;
 340   CardIdx_t ci;
 341   if (_card_ind < SparsePRTEntry::cards_num() &&
 342       ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) !=
 343        SparsePRTEntry::NullEntry)) {
 344     card_index = compute_card_ind(ci);
 345     return true;
 346   }
 347   // Otherwise, must find the next valid entry.
 348   _card_ind = 0;
 349 
 350   if (_bl_ind != RSHashTable::NullEntry) {
 351       _bl_ind = _rsht->entry(_bl_ind)->next_index();
 352       ci = find_first_card_in_list();
 353       if (ci != SparsePRTEntry::NullEntry) {
 354         card_index = compute_card_ind(ci);
 355         return true;
 356       }
 357   }
 358   // If we didn't return above, must go to the next non-null table index.
 359   _tbl_ind++;
 360   while ((size_t)_tbl_ind < _rsht->capacity()) {
 361     _bl_ind = _rsht->_buckets[_tbl_ind];
 362     ci = find_first_card_in_list();
 363     if (ci != SparsePRTEntry::NullEntry) {
 364       card_index = compute_card_ind(ci);
 365       return true;
 366     }
 367     // Otherwise, try next entry.
 368     _tbl_ind++;
 369   }
 370   // Otherwise, there were no entry.
 371   return false;
 372 }
 373 
 374 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
 375   SparsePRTEntry* e = entry_for_region_ind(region_index);
 376   return (e != NULL && e->contains_card(card_index));
 377 }
 378 
 379 size_t RSHashTable::mem_size() const {
 380   return sizeof(this) +
 381     capacity() * (SparsePRTEntry::size() + sizeof(int));
 382 }
 383 
 384 // ----------------------------------------------------------------------
 385 
 386 SparsePRT* SparsePRT::_head_expanded_list = NULL;
 387 
 388 void SparsePRT::add_to_expanded_list(SparsePRT* sprt) {
 389   // We could expand multiple times in a pause -- only put on list once.
 390   if (sprt->expanded()) return;
 391   sprt->set_expanded(true);
 392   SparsePRT* hd = _head_expanded_list;
 393   while (true) {
 394     sprt->_next_expanded = hd;
 395     SparsePRT* res =
 396       (SparsePRT*)
 397       Atomic::cmpxchg_ptr(sprt, &_head_expanded_list, hd);
 398     if (res == hd) return;
 399     else hd = res;
 400   }
 401 }
 402 
 403 
 404 SparsePRT* SparsePRT::get_from_expanded_list() {
 405   SparsePRT* hd = _head_expanded_list;
 406   while (hd != NULL) {
 407     SparsePRT* next = hd->next_expanded();
 408     SparsePRT* res =
 409       (SparsePRT*)
 410       Atomic::cmpxchg_ptr(next, &_head_expanded_list, hd);
 411     if (res == hd) {
 412       hd->set_next_expanded(NULL);
 413       return hd;
 414     } else {
 415       hd = res;
 416     }
 417   }
 418   return NULL;
 419 }
 420 
 421 
 422 void SparsePRT::cleanup_all() {
 423   // First clean up all expanded tables so they agree on next and cur.
 424   SparsePRT* sprt = get_from_expanded_list();
 425   while (sprt != NULL) {
 426     sprt->cleanup();
 427     sprt = get_from_expanded_list();
 428   }
 429 }
 430 
 431 
 432 SparsePRT::SparsePRT(HeapRegion* hr) :
 433   _hr(hr), _expanded(false), _next_expanded(NULL)
 434 {
 435   _cur = new RSHashTable(InitialCapacity);
 436   _next = _cur;
 437 }
 438 
 439 
 440 SparsePRT::~SparsePRT() {
 441   assert(_next != NULL && _cur != NULL, "Inv");
 442   if (_cur != _next) { delete _cur; }
 443   delete _next;
 444 }
 445 
 446 
 447 size_t SparsePRT::mem_size() const {
 448   // We ignore "_cur" here, because it either = _next, or else it is
 449   // on the deleted list.
 450   return sizeof(this) + _next->mem_size();
 451 }
 452 
 453 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) {
 454 #if SPARSE_PRT_VERBOSE
 455   gclog_or_tty->print_cr("  Adding card %d from region %d to region %d sparse.",
 456                 card_index, region_id, _hr->hrs_index());
 457 #endif
 458   if (_next->occupied_entries() * 2 > _next->capacity()) {
 459     expand();
 460   }
 461   return _next->add_card(region_id, card_index);
 462 }
 463 
 464 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) {
 465   return _next->get_cards(region_id, cards);
 466 }
 467 
 468 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) {
 469   return _next->get_entry(region_id);
 470 }
 471 
 472 bool SparsePRT::delete_entry(RegionIdx_t region_id) {
 473   return _next->delete_entry(region_id);
 474 }
 475 
 476 void SparsePRT::clear() {
 477   // If they differ, _next is bigger then cur, so next has no chance of
 478   // being the initial size.
 479   if (_next != _cur) {
 480     delete _next;
 481   }
 482 
 483   if (_cur->capacity() != InitialCapacity) {
 484     delete _cur;
 485     _cur = new RSHashTable(InitialCapacity);
 486   } else {
 487     _cur->clear();
 488   }
 489   _next = _cur;
 490 }
 491 
 492 void SparsePRT::cleanup() {
 493   // Make sure that the current and next tables agree.
 494   if (_cur != _next) {
 495     delete _cur;
 496   }
 497   _cur = _next;
 498   set_expanded(false);
 499 }
 500 
 501 void SparsePRT::expand() {
 502   RSHashTable* last = _next;
 503   _next = new RSHashTable(last->capacity() * 2);
 504 
 505 #if SPARSE_PRT_VERBOSE
 506   gclog_or_tty->print_cr("  Expanded sparse table for %d to %d.",
 507                 _hr->hrs_index(), _next->capacity());
 508 #endif
 509   for (size_t i = 0; i < last->capacity(); i++) {
 510     SparsePRTEntry* e = last->entry((int)i);
 511     if (e->valid_entry()) {
 512 #if SPARSE_PRT_VERBOSE
 513       gclog_or_tty->print_cr("    During expansion, transferred entry for %d.",
 514                     e->r_ind());
 515 #endif
 516       _next->add_entry(e);
 517     }
 518   }
 519   if (last != _cur) {
 520     delete last;
 521   }
 522   add_to_expanded_list(this);
 523 }