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