Tue, 21 Aug 2012 14:10:39 -0700
7185699: G1: Prediction model discrepancies
Summary: Correct the result value of G1CollectedHeap::pending_card_num(). Change the code that calculates the GC efficiency of a non-young heap region to use historical data from mixed GCs and the actual number of live bytes when predicting how long it would take to collect the region. Changes were also reviewed by Thomas Schatzl.
Reviewed-by: azeemj, brutisso
1 /*
2 * Copyright (c) 2001, 2012, 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, mtGC)),
152 _buckets(NEW_C_HEAP_ARRAY(int, capacity, mtGC)),
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, mtGC);
161 _entries = NULL;
162 }
163 if (_buckets != NULL) {
164 FREE_C_HEAP_ARRAY(int, _buckets, mtGC);
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 %u sparse.",
485 card_index, region_id, _hr->hrs_index());
486 #endif
487 if (_next->occupied_entries() * 2 > _next->capacity()) {
488 expand();
489 }
490 return _next->add_card(region_id, card_index);
491 }
493 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) {
494 return _next->get_cards(region_id, cards);
495 }
497 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) {
498 return _next->get_entry(region_id);
499 }
501 bool SparsePRT::delete_entry(RegionIdx_t region_id) {
502 return _next->delete_entry(region_id);
503 }
505 void SparsePRT::clear() {
506 // If they differ, _next is bigger then cur, so next has no chance of
507 // being the initial size.
508 if (_next != _cur) {
509 delete _next;
510 }
512 if (_cur->capacity() != InitialCapacity) {
513 delete _cur;
514 _cur = new RSHashTable(InitialCapacity);
515 } else {
516 _cur->clear();
517 }
518 _next = _cur;
519 _expanded = false;
520 }
522 void SparsePRT::cleanup() {
523 // Make sure that the current and next tables agree.
524 if (_cur != _next) {
525 delete _cur;
526 }
527 _cur = _next;
528 set_expanded(false);
529 }
531 void SparsePRT::expand() {
532 RSHashTable* last = _next;
533 _next = new RSHashTable(last->capacity() * 2);
535 #if SPARSE_PRT_VERBOSE
536 gclog_or_tty->print_cr(" Expanded sparse table for %u to %d.",
537 _hr->hrs_index(), _next->capacity());
538 #endif
539 for (size_t i = 0; i < last->capacity(); i++) {
540 SparsePRTEntry* e = last->entry((int)i);
541 if (e->valid_entry()) {
542 #if SPARSE_PRT_VERBOSE
543 gclog_or_tty->print_cr(" During expansion, transferred entry for %d.",
544 e->r_ind());
545 #endif
546 _next->add_entry(e);
547 }
548 }
549 if (last != _cur) {
550 delete last;
551 }
552 add_to_expanded_list(this);
553 }
555 void SparsePRTCleanupTask::add(SparsePRT* sprt) {
556 assert(sprt->should_be_on_expanded_list(), "pre-condition");
558 sprt->set_next_expanded(NULL);
559 if (_tail != NULL) {
560 _tail->set_next_expanded(sprt);
561 } else {
562 _head = sprt;
563 }
564 _tail = sprt;
565 }