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 }