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