1 /*
   2  * Copyright (c) 2001, 2014, 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   SparsePRTEntry* entry = get_entry(region_ind);
 198   if (entry == NULL) {
 199     return false;
 200   }
 201   // Otherwise...
 202   entry->copy_cards(cards);
 203   return true;
 204 }
 205 
 206 SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) const {
 207   int ind = (int) (region_ind & capacity_mask());
 208   int cur_ind = _buckets[ind];
 209   SparsePRTEntry* cur;
 210   while (cur_ind != NullEntry &&
 211          (cur = entry(cur_ind))->r_ind() != region_ind) {
 212     cur_ind = cur->next_index();
 213   }
 214 
 215   if (cur_ind == NullEntry) return NULL;
 216   // Otherwise...
 217   assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
 218   assert(cur->num_valid_cards() > 0, "Inv");
 219   return cur;
 220 }
 221 
 222 bool RSHashTable::delete_entry(RegionIdx_t region_ind) {
 223   int ind = (int) (region_ind & capacity_mask());
 224   int* prev_loc = &_buckets[ind];
 225   int cur_ind = *prev_loc;
 226   SparsePRTEntry* cur;
 227   while (cur_ind != NullEntry &&
 228          (cur = entry(cur_ind))->r_ind() != region_ind) {
 229     prev_loc = cur->next_index_addr();
 230     cur_ind = *prev_loc;
 231   }
 232 
 233   if (cur_ind == NullEntry) return false;
 234   // Otherwise, splice out "cur".
 235   *prev_loc = cur->next_index();
 236   _occupied_cards -= cur->num_valid_cards();
 237   free_entry(cur_ind);
 238   _occupied_entries--;
 239   return true;
 240 }
 241 
 242 SparsePRTEntry*
 243 RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) {
 244   SparsePRTEntry* res = get_entry(region_ind);
 245   if (res == NULL) {
 246     int new_ind = alloc_entry();
 247     assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room.");
 248     res = entry(new_ind);
 249     res->init(region_ind);
 250     // Insert at front.
 251     int ind = (int) (region_ind & capacity_mask());
 252     res->set_next_index(_buckets[ind]);
 253     _buckets[ind] = new_ind;
 254     _occupied_entries++;
 255   }
 256   return res;
 257 }
 258 
 259 int RSHashTable::alloc_entry() {
 260   int res;
 261   if (_free_list != NullEntry) {
 262     res = _free_list;
 263     _free_list = entry(res)->next_index();
 264     return res;
 265   } else if ((size_t) _free_region+1 < capacity()) {
 266     res = _free_region;
 267     _free_region++;
 268     return res;
 269   } else {
 270     return NullEntry;
 271   }
 272 }
 273 
 274 void RSHashTable::free_entry(int fi) {
 275   entry(fi)->set_next_index(_free_list);
 276   _free_list = fi;
 277 }
 278 
 279 void RSHashTable::add_entry(SparsePRTEntry* e) {
 280   assert(e->num_valid_cards() > 0, "Precondition.");
 281   SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind());
 282   e->copy_cards(e2);
 283   _occupied_cards += e2->num_valid_cards();
 284   assert(e2->num_valid_cards() > 0, "Postcondition.");
 285 }
 286 
 287 CardIdx_t RSHashTableIter::find_first_card_in_list() {
 288   CardIdx_t res;
 289   while (_bl_ind != RSHashTable::NullEntry) {
 290     res = _rsht->entry(_bl_ind)->card(0);
 291     if (res != SparsePRTEntry::NullEntry) {
 292       return res;
 293     } else {
 294       _bl_ind = _rsht->entry(_bl_ind)->next_index();
 295     }
 296   }
 297   // Otherwise, none found:
 298   return SparsePRTEntry::NullEntry;
 299 }
 300 
 301 size_t RSHashTableIter::compute_card_ind(CardIdx_t ci) {
 302   return (_rsht->entry(_bl_ind)->r_ind() * HeapRegion::CardsPerRegion) + ci;
 303 }
 304 
 305 bool RSHashTableIter::has_next(size_t& card_index) {
 306   _card_ind++;
 307   CardIdx_t ci;
 308   if (_card_ind < SparsePRTEntry::cards_num() &&
 309       ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) !=
 310        SparsePRTEntry::NullEntry)) {
 311     card_index = compute_card_ind(ci);
 312     return true;
 313   }
 314   // Otherwise, must find the next valid entry.
 315   _card_ind = 0;
 316 
 317   if (_bl_ind != RSHashTable::NullEntry) {
 318       _bl_ind = _rsht->entry(_bl_ind)->next_index();
 319       ci = find_first_card_in_list();
 320       if (ci != SparsePRTEntry::NullEntry) {
 321         card_index = compute_card_ind(ci);
 322         return true;
 323       }
 324   }
 325   // If we didn't return above, must go to the next non-null table index.
 326   _tbl_ind++;
 327   while ((size_t)_tbl_ind < _rsht->capacity()) {
 328     _bl_ind = _rsht->_buckets[_tbl_ind];
 329     ci = find_first_card_in_list();
 330     if (ci != SparsePRTEntry::NullEntry) {
 331       card_index = compute_card_ind(ci);
 332       return true;
 333     }
 334     // Otherwise, try next entry.
 335     _tbl_ind++;
 336   }
 337   // Otherwise, there were no entry.
 338   return false;
 339 }
 340 
 341 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
 342   SparsePRTEntry* e = get_entry(region_index);
 343   return (e != NULL && e->contains_card(card_index));
 344 }
 345 
 346 size_t RSHashTable::mem_size() const {
 347   return sizeof(RSHashTable) +
 348     capacity() * (SparsePRTEntry::size() + sizeof(int));
 349 }
 350 
 351 // ----------------------------------------------------------------------
 352 
 353 SparsePRT* SparsePRT::_head_expanded_list = NULL;
 354 
 355 void SparsePRT::add_to_expanded_list(SparsePRT* sprt) {
 356   // We could expand multiple times in a pause -- only put on list once.
 357   if (sprt->expanded()) return;
 358   sprt->set_expanded(true);
 359   SparsePRT* hd = _head_expanded_list;
 360   while (true) {
 361     sprt->_next_expanded = hd;
 362     SparsePRT* res =
 363       (SparsePRT*)
 364       Atomic::cmpxchg_ptr(sprt, &_head_expanded_list, hd);
 365     if (res == hd) return;
 366     else hd = res;
 367   }
 368 }
 369 
 370 
 371 SparsePRT* SparsePRT::get_from_expanded_list() {
 372   SparsePRT* hd = _head_expanded_list;
 373   while (hd != NULL) {
 374     SparsePRT* next = hd->next_expanded();
 375     SparsePRT* res =
 376       (SparsePRT*)
 377       Atomic::cmpxchg_ptr(next, &_head_expanded_list, hd);
 378     if (res == hd) {
 379       hd->set_next_expanded(NULL);
 380       return hd;
 381     } else {
 382       hd = res;
 383     }
 384   }
 385   return NULL;
 386 }
 387 
 388 void SparsePRT::reset_for_cleanup_tasks() {
 389   _head_expanded_list = NULL;
 390 }
 391 
 392 void SparsePRT::do_cleanup_work(SparsePRTCleanupTask* sprt_cleanup_task) {
 393   if (should_be_on_expanded_list()) {
 394     sprt_cleanup_task->add(this);
 395   }
 396 }
 397 
 398 void SparsePRT::finish_cleanup_task(SparsePRTCleanupTask* sprt_cleanup_task) {
 399   assert(ParGCRareEvent_lock->owned_by_self(), "pre-condition");
 400   SparsePRT* head = sprt_cleanup_task->head();
 401   SparsePRT* tail = sprt_cleanup_task->tail();
 402   if (head != NULL) {
 403     assert(tail != NULL, "if head is not NULL, so should tail");
 404 
 405     tail->set_next_expanded(_head_expanded_list);
 406     _head_expanded_list = head;
 407   } else {
 408     assert(tail == NULL, "if head is NULL, so should tail");
 409   }
 410 }
 411 
 412 bool SparsePRT::should_be_on_expanded_list() {
 413   if (_expanded) {
 414     assert(_cur != _next, "if _expanded is true, cur should be != _next");
 415   } else {
 416     assert(_cur == _next, "if _expanded is false, cur should be == _next");
 417   }
 418   return expanded();
 419 }
 420 
 421 void SparsePRT::cleanup_all() {
 422   // First clean up all expanded tables so they agree on next and cur.
 423   SparsePRT* sprt = get_from_expanded_list();
 424   while (sprt != NULL) {
 425     sprt->cleanup();
 426     sprt = get_from_expanded_list();
 427   }
 428 }
 429 
 430 
 431 SparsePRT::SparsePRT(HeapRegion* hr) :
 432   _hr(hr), _expanded(false), _next_expanded(NULL)
 433 {
 434   _cur = new RSHashTable(InitialCapacity);
 435   _next = _cur;
 436 }
 437 
 438 
 439 SparsePRT::~SparsePRT() {
 440   assert(_next != NULL && _cur != NULL, "Inv");
 441   if (_cur != _next) { delete _cur; }
 442   delete _next;
 443 }
 444 
 445 
 446 size_t SparsePRT::mem_size() const {
 447   // We ignore "_cur" here, because it either = _next, or else it is
 448   // on the deleted list.
 449   return sizeof(SparsePRT) + _next->mem_size();
 450 }
 451 
 452 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) {
 453 #if SPARSE_PRT_VERBOSE
 454   gclog_or_tty->print_cr("  Adding card %d from region %d to region %u sparse.",
 455                          card_index, region_id, _hr->hrs_index());
 456 #endif
 457   if (_next->occupied_entries() * 2 > _next->capacity()) {
 458     expand();
 459   }
 460   return _next->add_card(region_id, card_index);
 461 }
 462 
 463 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) {
 464   return _next->get_cards(region_id, cards);
 465 }
 466 
 467 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) {
 468   return _next->get_entry(region_id);
 469 }
 470 
 471 bool SparsePRT::delete_entry(RegionIdx_t region_id) {
 472   return _next->delete_entry(region_id);
 473 }
 474 
 475 void SparsePRT::clear() {
 476   // If they differ, _next is bigger then cur, so next has no chance of
 477   // being the initial size.
 478   if (_next != _cur) {
 479     delete _next;
 480   }
 481 
 482   if (_cur->capacity() != InitialCapacity) {
 483     delete _cur;
 484     _cur = new RSHashTable(InitialCapacity);
 485   } else {
 486     _cur->clear();
 487   }
 488   _next = _cur;
 489   _expanded = false;
 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 %u 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 }
 524 
 525 void SparsePRTCleanupTask::add(SparsePRT* sprt) {
 526   assert(sprt->should_be_on_expanded_list(), "pre-condition");
 527 
 528   sprt->set_next_expanded(NULL);
 529   if (_tail != NULL) {
 530     _tail->set_next_expanded(sprt);
 531   } else {
 532     _head = sprt;
 533   }
 534   _tail = sprt;
 535 }