Thu, 22 Sep 2011 10:57:37 -0700
6484982: G1: process references during evacuation pauses
Summary: G1 now uses two reference processors - one is used by concurrent marking and the other is used by STW GCs (both full and incremental evacuation pauses). In an evacuation pause, the reference processor is embedded into the closures used to scan objects. Doing so causes causes reference objects to be 'discovered' by the reference processor. At the end of the evacuation pause, these discovered reference objects are processed - preserving (and copying) referent objects (and their reachable graphs) as appropriate.
Reviewed-by: ysr, jwilhelm, brutisso, stefank, tonyp
1 /*
2 * Copyright (c) 2001, 2011, 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 */
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"
34 #define SPARSE_PRT_VERBOSE 0
36 #define UNROLL_CARD_LOOPS 1
38 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) {
39 sprt_iter->init(this);
40 }
42 void SparsePRTEntry::init(RegionIdx_t region_ind) {
43 _region_ind = region_ind;
44 _next_index = NullEntry;
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 }
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 }
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 }
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 }
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 }
142 void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const {
143 copy_cards(&e->_cards[0]);
144 }
146 // ----------------------------------------------------------------------
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 }
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 }
169 void RSHashTable::clear() {
170 _occupied_entries = 0;
171 _occupied_cards = 0;
172 guarantee(_entries != NULL, "INV");
173 guarantee(_buckets != NULL, "INV");
175 guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1,
176 "_capacity too large");
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
304 void RSHashTable::free_entry(int fi) {
305 entry(fi)->set_next_index(_free_list);
306 _free_list = fi;
307 }
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 }
317 CardIdx_t 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 }
331 size_t RSHashTableIter::compute_card_ind(CardIdx_t ci) {
332 return (_rsht->entry(_bl_ind)->r_ind() * HeapRegion::CardsPerRegion) + ci;
333 }
335 bool RSHashTableIter::has_next(size_t& card_index) {
336 _card_ind++;
337 CardIdx_t ci;
338 if (_card_ind < SparsePRTEntry::cards_num() &&
339 ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) !=
340 SparsePRTEntry::NullEntry)) {
341 card_index = compute_card_ind(ci);
342 return true;
343 }
344 // Otherwise, must find the next valid entry.
345 _card_ind = 0;
347 if (_bl_ind != RSHashTable::NullEntry) {
348 _bl_ind = _rsht->entry(_bl_ind)->next_index();
349 ci = find_first_card_in_list();
350 if (ci != SparsePRTEntry::NullEntry) {
351 card_index = compute_card_ind(ci);
352 return true;
353 }
354 }
355 // If we didn't return above, must go to the next non-null table index.
356 _tbl_ind++;
357 while ((size_t)_tbl_ind < _rsht->capacity()) {
358 _bl_ind = _rsht->_buckets[_tbl_ind];
359 ci = find_first_card_in_list();
360 if (ci != SparsePRTEntry::NullEntry) {
361 card_index = compute_card_ind(ci);
362 return true;
363 }
364 // Otherwise, try next entry.
365 _tbl_ind++;
366 }
367 // Otherwise, there were no entry.
368 return false;
369 }
371 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
372 SparsePRTEntry* e = entry_for_region_ind(region_index);
373 return (e != NULL && e->contains_card(card_index));
374 }
376 size_t RSHashTable::mem_size() const {
377 return sizeof(this) +
378 capacity() * (SparsePRTEntry::size() + sizeof(int));
379 }
381 // ----------------------------------------------------------------------
383 SparsePRT* SparsePRT::_head_expanded_list = NULL;
385 void SparsePRT::add_to_expanded_list(SparsePRT* sprt) {
386 // We could expand multiple times in a pause -- only put on list once.
387 if (sprt->expanded()) return;
388 sprt->set_expanded(true);
389 SparsePRT* hd = _head_expanded_list;
390 while (true) {
391 sprt->_next_expanded = hd;
392 SparsePRT* res =
393 (SparsePRT*)
394 Atomic::cmpxchg_ptr(sprt, &_head_expanded_list, hd);
395 if (res == hd) return;
396 else hd = res;
397 }
398 }
401 SparsePRT* SparsePRT::get_from_expanded_list() {
402 SparsePRT* hd = _head_expanded_list;
403 while (hd != NULL) {
404 SparsePRT* next = hd->next_expanded();
405 SparsePRT* res =
406 (SparsePRT*)
407 Atomic::cmpxchg_ptr(next, &_head_expanded_list, hd);
408 if (res == hd) {
409 hd->set_next_expanded(NULL);
410 return hd;
411 } else {
412 hd = res;
413 }
414 }
415 return NULL;
416 }
418 void SparsePRT::reset_for_cleanup_tasks() {
419 _head_expanded_list = NULL;
420 }
422 void SparsePRT::do_cleanup_work(SparsePRTCleanupTask* sprt_cleanup_task) {
423 if (should_be_on_expanded_list()) {
424 sprt_cleanup_task->add(this);
425 }
426 }
428 void SparsePRT::finish_cleanup_task(SparsePRTCleanupTask* sprt_cleanup_task) {
429 assert(ParGCRareEvent_lock->owned_by_self(), "pre-condition");
430 SparsePRT* head = sprt_cleanup_task->head();
431 SparsePRT* tail = sprt_cleanup_task->tail();
432 if (head != NULL) {
433 assert(tail != NULL, "if head is not NULL, so should tail");
435 tail->set_next_expanded(_head_expanded_list);
436 _head_expanded_list = head;
437 } else {
438 assert(tail == NULL, "if head is NULL, so should tail");
439 }
440 }
442 bool SparsePRT::should_be_on_expanded_list() {
443 if (_expanded) {
444 assert(_cur != _next, "if _expanded is true, cur should be != _next");
445 } else {
446 assert(_cur == _next, "if _expanded is false, cur should be == _next");
447 }
448 return expanded();
449 }
451 void SparsePRT::cleanup_all() {
452 // First clean up all expanded tables so they agree on next and cur.
453 SparsePRT* sprt = get_from_expanded_list();
454 while (sprt != NULL) {
455 sprt->cleanup();
456 sprt = get_from_expanded_list();
457 }
458 }
461 SparsePRT::SparsePRT(HeapRegion* hr) :
462 _hr(hr), _expanded(false), _next_expanded(NULL)
463 {
464 _cur = new RSHashTable(InitialCapacity);
465 _next = _cur;
466 }
469 SparsePRT::~SparsePRT() {
470 assert(_next != NULL && _cur != NULL, "Inv");
471 if (_cur != _next) { delete _cur; }
472 delete _next;
473 }
476 size_t SparsePRT::mem_size() const {
477 // We ignore "_cur" here, because it either = _next, or else it is
478 // on the deleted list.
479 return sizeof(this) + _next->mem_size();
480 }
482 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) {
483 #if SPARSE_PRT_VERBOSE
484 gclog_or_tty->print_cr(" Adding card %d from region %d to region "
485 SIZE_FORMAT" sparse.",
486 card_index, region_id, _hr->hrs_index());
487 #endif
488 if (_next->occupied_entries() * 2 > _next->capacity()) {
489 expand();
490 }
491 return _next->add_card(region_id, card_index);
492 }
494 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) {
495 return _next->get_cards(region_id, cards);
496 }
498 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) {
499 return _next->get_entry(region_id);
500 }
502 bool SparsePRT::delete_entry(RegionIdx_t region_id) {
503 return _next->delete_entry(region_id);
504 }
506 void SparsePRT::clear() {
507 // If they differ, _next is bigger then cur, so next has no chance of
508 // being the initial size.
509 if (_next != _cur) {
510 delete _next;
511 }
513 if (_cur->capacity() != InitialCapacity) {
514 delete _cur;
515 _cur = new RSHashTable(InitialCapacity);
516 } else {
517 _cur->clear();
518 }
519 _next = _cur;
520 _expanded = false;
521 }
523 void SparsePRT::cleanup() {
524 // Make sure that the current and next tables agree.
525 if (_cur != _next) {
526 delete _cur;
527 }
528 _cur = _next;
529 set_expanded(false);
530 }
532 void SparsePRT::expand() {
533 RSHashTable* last = _next;
534 _next = new RSHashTable(last->capacity() * 2);
536 #if SPARSE_PRT_VERBOSE
537 gclog_or_tty->print_cr(" Expanded sparse table for "SIZE_FORMAT" to %d.",
538 _hr->hrs_index(), _next->capacity());
539 #endif
540 for (size_t i = 0; i < last->capacity(); i++) {
541 SparsePRTEntry* e = last->entry((int)i);
542 if (e->valid_entry()) {
543 #if SPARSE_PRT_VERBOSE
544 gclog_or_tty->print_cr(" During expansion, transferred entry for %d.",
545 e->r_ind());
546 #endif
547 _next->add_entry(e);
548 }
549 }
550 if (last != _cur) {
551 delete last;
552 }
553 add_to_expanded_list(this);
554 }
556 void SparsePRTCleanupTask::add(SparsePRT* sprt) {
557 assert(sprt->should_be_on_expanded_list(), "pre-condition");
559 sprt->set_next_expanded(NULL);
560 if (_tail != NULL) {
561 _tail->set_next_expanded(sprt);
562 } else {
563 _head = sprt;
564 }
565 _tail = sprt;
566 }