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