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) 2011, 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/heapRegionSet.inline.hpp"
28 uint HeapRegionSetBase::_unrealistically_long_length = 0;
29 HRSPhase HeapRegionSetBase::_phase = HRSPhaseNone;
31 //////////////////// HeapRegionSetBase ////////////////////
33 void HeapRegionSetBase::set_unrealistically_long_length(uint len) {
34 guarantee(_unrealistically_long_length == 0, "should only be set once");
35 _unrealistically_long_length = len;
36 }
38 void HeapRegionSetBase::fill_in_ext_msg(hrs_ext_msg* msg, const char* message) {
39 msg->append("[%s] %s ln: %u rn: %u cy: "SIZE_FORMAT" ud: "SIZE_FORMAT,
40 name(), message, length(), region_num(),
41 total_capacity_bytes(), total_used_bytes());
42 fill_in_ext_msg_extra(msg);
43 }
45 bool HeapRegionSetBase::verify_region(HeapRegion* hr,
46 HeapRegionSetBase* expected_containing_set) {
47 const char* error_message = NULL;
49 if (!regions_humongous()) {
50 if (hr->isHumongous()) {
51 error_message = "the region should not be humongous";
52 }
53 } else {
54 if (!hr->isHumongous() || !hr->startsHumongous()) {
55 error_message = "the region should be 'starts humongous'";
56 }
57 }
59 if (!regions_empty()) {
60 if (hr->is_empty()) {
61 error_message = "the region should not be empty";
62 }
63 } else {
64 if (!hr->is_empty()) {
65 error_message = "the region should be empty";
66 }
67 }
69 #ifdef ASSERT
70 // The _containing_set field is only available when ASSERT is defined.
71 if (hr->containing_set() != expected_containing_set) {
72 error_message = "inconsistent containing set found";
73 }
74 #endif // ASSERT
76 const char* extra_error_message = verify_region_extra(hr);
77 if (extra_error_message != NULL) {
78 error_message = extra_error_message;
79 }
81 if (error_message != NULL) {
82 outputStream* out = tty;
83 out->cr();
84 out->print_cr("## [%s] %s", name(), error_message);
85 out->print_cr("## Offending Region: "PTR_FORMAT, hr);
86 out->print_cr(" "HR_FORMAT, HR_FORMAT_PARAMS(hr));
87 #ifdef ASSERT
88 out->print_cr(" containing set: "PTR_FORMAT, hr->containing_set());
89 #endif // ASSERT
90 out->print_cr("## Offending Region Set: "PTR_FORMAT, this);
91 print_on(out);
92 return false;
93 } else {
94 return true;
95 }
96 }
98 void HeapRegionSetBase::verify() {
99 // It's important that we also observe the MT safety protocol even
100 // for the verification calls. If we do verification without the
101 // appropriate locks and the set changes underneath our feet
102 // verification might fail and send us on a wild goose chase.
103 hrs_assert_mt_safety_ok(this);
105 guarantee(( is_empty() && length() == 0 && region_num() == 0 &&
106 total_used_bytes() == 0 && total_capacity_bytes() == 0) ||
107 (!is_empty() && length() >= 0 && region_num() >= 0 &&
108 total_used_bytes() >= 0 && total_capacity_bytes() >= 0),
109 hrs_ext_msg(this, "invariant"));
111 guarantee((!regions_humongous() && region_num() == length()) ||
112 ( regions_humongous() && region_num() >= length()),
113 hrs_ext_msg(this, "invariant"));
115 guarantee(!regions_empty() || total_used_bytes() == 0,
116 hrs_ext_msg(this, "invariant"));
118 guarantee(total_used_bytes() <= total_capacity_bytes(),
119 hrs_ext_msg(this, "invariant"));
120 }
122 void HeapRegionSetBase::verify_start() {
123 // See comment in verify() about MT safety and verification.
124 hrs_assert_mt_safety_ok(this);
125 assert(!_verify_in_progress,
126 hrs_ext_msg(this, "verification should not be in progress"));
128 // Do the basic verification first before we do the checks over the regions.
129 HeapRegionSetBase::verify();
131 _calc_length = 0;
132 _calc_region_num = 0;
133 _calc_total_capacity_bytes = 0;
134 _calc_total_used_bytes = 0;
135 _verify_in_progress = true;
136 }
138 void HeapRegionSetBase::verify_next_region(HeapRegion* hr) {
139 // See comment in verify() about MT safety and verification.
140 hrs_assert_mt_safety_ok(this);
141 assert(_verify_in_progress,
142 hrs_ext_msg(this, "verification should be in progress"));
144 guarantee(verify_region(hr, this), hrs_ext_msg(this, "region verification"));
146 _calc_length += 1;
147 _calc_region_num += hr->region_num();
148 _calc_total_capacity_bytes += hr->capacity();
149 _calc_total_used_bytes += hr->used();
150 }
152 void HeapRegionSetBase::verify_end() {
153 // See comment in verify() about MT safety and verification.
154 hrs_assert_mt_safety_ok(this);
155 assert(_verify_in_progress,
156 hrs_ext_msg(this, "verification should be in progress"));
158 guarantee(length() == _calc_length,
159 hrs_err_msg("[%s] length: %u should be == calc length: %u",
160 name(), length(), _calc_length));
162 guarantee(region_num() == _calc_region_num,
163 hrs_err_msg("[%s] region num: %u should be == calc region num: %u",
164 name(), region_num(), _calc_region_num));
166 guarantee(total_capacity_bytes() == _calc_total_capacity_bytes,
167 hrs_err_msg("[%s] capacity bytes: "SIZE_FORMAT" should be == "
168 "calc capacity bytes: "SIZE_FORMAT,
169 name(),
170 total_capacity_bytes(), _calc_total_capacity_bytes));
172 guarantee(total_used_bytes() == _calc_total_used_bytes,
173 hrs_err_msg("[%s] used bytes: "SIZE_FORMAT" should be == "
174 "calc used bytes: "SIZE_FORMAT,
175 name(), total_used_bytes(), _calc_total_used_bytes));
177 _verify_in_progress = false;
178 }
180 void HeapRegionSetBase::clear_phase() {
181 assert(_phase != HRSPhaseNone, "pre-condition");
182 _phase = HRSPhaseNone;
183 }
185 void HeapRegionSetBase::set_phase(HRSPhase phase) {
186 assert(_phase == HRSPhaseNone, "pre-condition");
187 assert(phase != HRSPhaseNone, "pre-condition");
188 _phase = phase;
189 }
191 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
192 out->cr();
193 out->print_cr("Set: %s ("PTR_FORMAT")", name(), this);
194 out->print_cr(" Region Assumptions");
195 out->print_cr(" humongous : %s", BOOL_TO_STR(regions_humongous()));
196 out->print_cr(" empty : %s", BOOL_TO_STR(regions_empty()));
197 out->print_cr(" Attributes");
198 out->print_cr(" length : %14u", length());
199 out->print_cr(" region num : %14u", region_num());
200 out->print_cr(" total capacity : "SIZE_FORMAT_W(14)" bytes",
201 total_capacity_bytes());
202 out->print_cr(" total used : "SIZE_FORMAT_W(14)" bytes",
203 total_used_bytes());
204 }
206 void HeapRegionSetBase::clear() {
207 _length = 0;
208 _region_num = 0;
209 _total_used_bytes = 0;
210 }
212 HeapRegionSetBase::HeapRegionSetBase(const char* name)
213 : _name(name), _verify_in_progress(false),
214 _calc_length(0), _calc_region_num(0),
215 _calc_total_capacity_bytes(0), _calc_total_used_bytes(0) { }
217 //////////////////// HeapRegionSet ////////////////////
219 void HeapRegionSet::update_from_proxy(HeapRegionSet* proxy_set) {
220 hrs_assert_mt_safety_ok(this);
221 hrs_assert_mt_safety_ok(proxy_set);
222 hrs_assert_sets_match(this, proxy_set);
224 verify_optional();
225 proxy_set->verify_optional();
227 if (proxy_set->is_empty()) return;
229 assert(proxy_set->length() <= _length,
230 hrs_err_msg("[%s] proxy set length: %u should be <= length: %u",
231 name(), proxy_set->length(), _length));
232 _length -= proxy_set->length();
234 assert(proxy_set->region_num() <= _region_num,
235 hrs_err_msg("[%s] proxy set region num: %u should be <= region num: %u",
236 name(), proxy_set->region_num(), _region_num));
237 _region_num -= proxy_set->region_num();
239 assert(proxy_set->total_used_bytes() <= _total_used_bytes,
240 hrs_err_msg("[%s] proxy set used bytes: "SIZE_FORMAT" "
241 "should be <= used bytes: "SIZE_FORMAT,
242 name(), proxy_set->total_used_bytes(),
243 _total_used_bytes));
244 _total_used_bytes -= proxy_set->total_used_bytes();
246 proxy_set->clear();
248 verify_optional();
249 proxy_set->verify_optional();
250 }
252 //////////////////// HeapRegionLinkedList ////////////////////
254 void HeapRegionLinkedList::fill_in_ext_msg_extra(hrs_ext_msg* msg) {
255 msg->append(" hd: "PTR_FORMAT" tl: "PTR_FORMAT, head(), tail());
256 }
258 void HeapRegionLinkedList::add_as_head(HeapRegionLinkedList* from_list) {
259 hrs_assert_mt_safety_ok(this);
260 hrs_assert_mt_safety_ok(from_list);
262 verify_optional();
263 from_list->verify_optional();
265 if (from_list->is_empty()) return;
267 #ifdef ASSERT
268 HeapRegionLinkedListIterator iter(from_list);
269 while (iter.more_available()) {
270 HeapRegion* hr = iter.get_next();
271 // In set_containing_set() we check that we either set the value
272 // from NULL to non-NULL or vice versa to catch bugs. So, we have
273 // to NULL it first before setting it to the value.
274 hr->set_containing_set(NULL);
275 hr->set_containing_set(this);
276 }
277 #endif // ASSERT
279 if (_head != NULL) {
280 assert(length() > 0 && _tail != NULL, hrs_ext_msg(this, "invariant"));
281 from_list->_tail->set_next(_head);
282 } else {
283 assert(length() == 0 && _tail == NULL, hrs_ext_msg(this, "invariant"));
284 _tail = from_list->_tail;
285 }
286 _head = from_list->_head;
288 _length += from_list->length();
289 _region_num += from_list->region_num();
290 _total_used_bytes += from_list->total_used_bytes();
291 from_list->clear();
293 verify_optional();
294 from_list->verify_optional();
295 }
297 void HeapRegionLinkedList::add_as_tail(HeapRegionLinkedList* from_list) {
298 hrs_assert_mt_safety_ok(this);
299 hrs_assert_mt_safety_ok(from_list);
301 verify_optional();
302 from_list->verify_optional();
304 if (from_list->is_empty()) return;
306 #ifdef ASSERT
307 HeapRegionLinkedListIterator iter(from_list);
308 while (iter.more_available()) {
309 HeapRegion* hr = iter.get_next();
310 // In set_containing_set() we check that we either set the value
311 // from NULL to non-NULL or vice versa to catch bugs. So, we have
312 // to NULL it first before setting it to the value.
313 hr->set_containing_set(NULL);
314 hr->set_containing_set(this);
315 }
316 #endif // ASSERT
318 if (_tail != NULL) {
319 assert(length() > 0 && _head != NULL, hrs_ext_msg(this, "invariant"));
320 _tail->set_next(from_list->_head);
321 } else {
322 assert(length() == 0 && _head == NULL, hrs_ext_msg(this, "invariant"));
323 _head = from_list->_head;
324 }
325 _tail = from_list->_tail;
327 _length += from_list->length();
328 _region_num += from_list->region_num();
329 _total_used_bytes += from_list->total_used_bytes();
330 from_list->clear();
332 verify_optional();
333 from_list->verify_optional();
334 }
336 void HeapRegionLinkedList::remove_all() {
337 hrs_assert_mt_safety_ok(this);
338 verify_optional();
340 HeapRegion* curr = _head;
341 while (curr != NULL) {
342 hrs_assert_region_ok(this, curr, this);
344 HeapRegion* next = curr->next();
345 curr->set_next(NULL);
346 curr->set_containing_set(NULL);
347 curr = next;
348 }
349 clear();
351 verify_optional();
352 }
354 void HeapRegionLinkedList::remove_all_pending(uint target_count) {
355 hrs_assert_mt_safety_ok(this);
356 assert(target_count > 1, hrs_ext_msg(this, "pre-condition"));
357 assert(!is_empty(), hrs_ext_msg(this, "pre-condition"));
359 verify_optional();
360 DEBUG_ONLY(uint old_length = length();)
362 HeapRegion* curr = _head;
363 HeapRegion* prev = NULL;
364 uint count = 0;
365 while (curr != NULL) {
366 hrs_assert_region_ok(this, curr, this);
367 HeapRegion* next = curr->next();
369 if (curr->pending_removal()) {
370 assert(count < target_count,
371 hrs_err_msg("[%s] should not come across more regions "
372 "pending for removal than target_count: %u",
373 name(), target_count));
375 if (prev == NULL) {
376 assert(_head == curr, hrs_ext_msg(this, "invariant"));
377 _head = next;
378 } else {
379 assert(_head != curr, hrs_ext_msg(this, "invariant"));
380 prev->set_next(next);
381 }
382 if (next == NULL) {
383 assert(_tail == curr, hrs_ext_msg(this, "invariant"));
384 _tail = prev;
385 } else {
386 assert(_tail != curr, hrs_ext_msg(this, "invariant"));
387 }
389 curr->set_next(NULL);
390 remove_internal(curr);
391 curr->set_pending_removal(false);
393 count += 1;
395 // If we have come across the target number of regions we can
396 // just bail out. However, for debugging purposes, we can just
397 // carry on iterating to make sure there are not more regions
398 // tagged with pending removal.
399 DEBUG_ONLY(if (count == target_count) break;)
400 } else {
401 prev = curr;
402 }
403 curr = next;
404 }
406 assert(count == target_count,
407 hrs_err_msg("[%s] count: %u should be == target_count: %u",
408 name(), count, target_count));
409 assert(length() + target_count == old_length,
410 hrs_err_msg("[%s] new length should be consistent "
411 "new length: %u old length: %u target_count: %u",
412 name(), length(), old_length, target_count));
414 verify_optional();
415 }
417 void HeapRegionLinkedList::verify() {
418 // See comment in HeapRegionSetBase::verify() about MT safety and
419 // verification.
420 hrs_assert_mt_safety_ok(this);
422 // This will also do the basic verification too.
423 verify_start();
425 HeapRegion* curr = _head;
426 HeapRegion* prev1 = NULL;
427 HeapRegion* prev0 = NULL;
428 uint count = 0;
429 while (curr != NULL) {
430 verify_next_region(curr);
432 count += 1;
433 guarantee(count < _unrealistically_long_length,
434 hrs_err_msg("[%s] the calculated length: %u "
435 "seems very long, is there maybe a cycle? "
436 "curr: "PTR_FORMAT" prev0: "PTR_FORMAT" "
437 "prev1: "PTR_FORMAT" length: %u",
438 name(), count, curr, prev0, prev1, length()));
440 prev1 = prev0;
441 prev0 = curr;
442 curr = curr->next();
443 }
445 guarantee(_tail == prev0, hrs_ext_msg(this, "post-condition"));
447 verify_end();
448 }
450 void HeapRegionLinkedList::clear() {
451 HeapRegionSetBase::clear();
452 _head = NULL;
453 _tail = NULL;
454 }
456 void HeapRegionLinkedList::print_on(outputStream* out, bool print_contents) {
457 HeapRegionSetBase::print_on(out, print_contents);
458 out->print_cr(" Linking");
459 out->print_cr(" head : "PTR_FORMAT, _head);
460 out->print_cr(" tail : "PTR_FORMAT, _tail);
462 if (print_contents) {
463 out->print_cr(" Contents");
464 HeapRegionLinkedListIterator iter(this);
465 while (iter.more_available()) {
466 HeapRegion* hr = iter.get_next();
467 hr->print_on(out);
468 }
469 }
470 }