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/heapRegionSeq.inline.hpp"
28 #include "gc_implementation/g1/heapRegionSets.hpp"
29 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
30 #include "memory/allocation.hpp"
32 // Private
34 uint HeapRegionSeq::find_contiguous_from(uint from, uint num) {
35 uint len = length();
36 assert(num > 1, "use this only for sequences of length 2 or greater");
37 assert(from <= len,
38 err_msg("from: %u should be valid and <= than %u", from, len));
40 uint curr = from;
41 uint first = G1_NULL_HRS_INDEX;
42 uint num_so_far = 0;
43 while (curr < len && num_so_far < num) {
44 if (at(curr)->is_empty()) {
45 if (first == G1_NULL_HRS_INDEX) {
46 first = curr;
47 num_so_far = 1;
48 } else {
49 num_so_far += 1;
50 }
51 } else {
52 first = G1_NULL_HRS_INDEX;
53 num_so_far = 0;
54 }
55 curr += 1;
56 }
57 assert(num_so_far <= num, "post-condition");
58 if (num_so_far == num) {
59 // we found enough space for the humongous object
60 assert(from <= first && first < len, "post-condition");
61 assert(first < curr && (curr - first) == num, "post-condition");
62 for (uint i = first; i < first + num; ++i) {
63 assert(at(i)->is_empty(), "post-condition");
64 }
65 return first;
66 } else {
67 // we failed to find enough space for the humongous object
68 return G1_NULL_HRS_INDEX;
69 }
70 }
72 // Public
74 void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* end,
75 uint max_length) {
76 assert((uintptr_t) bottom % HeapRegion::GrainBytes == 0,
77 "bottom should be heap region aligned");
78 assert((uintptr_t) end % HeapRegion::GrainBytes == 0,
79 "end should be heap region aligned");
81 _length = 0;
82 _heap_bottom = bottom;
83 _heap_end = end;
84 _region_shift = HeapRegion::LogOfHRGrainBytes;
85 _next_search_index = 0;
86 _allocated_length = 0;
87 _max_length = max_length;
89 _regions = NEW_C_HEAP_ARRAY(HeapRegion*, max_length, mtGC);
90 memset(_regions, 0, (size_t) max_length * sizeof(HeapRegion*));
91 _regions_biased = _regions - ((uintx) bottom >> _region_shift);
93 assert(&_regions[0] == &_regions_biased[addr_to_index_biased(bottom)],
94 "bottom should be included in the region with index 0");
95 }
97 MemRegion HeapRegionSeq::expand_by(HeapWord* old_end,
98 HeapWord* new_end,
99 FreeRegionList* list) {
100 assert(old_end < new_end, "don't call it otherwise");
101 G1CollectedHeap* g1h = G1CollectedHeap::heap();
103 HeapWord* next_bottom = old_end;
104 assert(_heap_bottom <= next_bottom, "invariant");
105 while (next_bottom < new_end) {
106 assert(next_bottom < _heap_end, "invariant");
107 uint index = length();
109 assert(index < _max_length, "otherwise we cannot expand further");
110 if (index == 0) {
111 // We have not allocated any regions so far
112 assert(next_bottom == _heap_bottom, "invariant");
113 } else {
114 // next_bottom should match the end of the last/previous region
115 assert(next_bottom == at(index - 1)->end(), "invariant");
116 }
118 if (index == _allocated_length) {
119 // We have to allocate a new HeapRegion.
120 HeapRegion* new_hr = g1h->new_heap_region(index, next_bottom);
121 if (new_hr == NULL) {
122 // allocation failed, we bail out and return what we have done so far
123 return MemRegion(old_end, next_bottom);
124 }
125 assert(_regions[index] == NULL, "invariant");
126 _regions[index] = new_hr;
127 increment_length(&_allocated_length);
128 }
129 // Have to increment the length first, otherwise we will get an
130 // assert failure at(index) below.
131 increment_length(&_length);
132 HeapRegion* hr = at(index);
133 list->add_as_tail(hr);
135 next_bottom = hr->end();
136 }
137 assert(next_bottom == new_end, "post-condition");
138 return MemRegion(old_end, next_bottom);
139 }
141 uint HeapRegionSeq::free_suffix() {
142 uint res = 0;
143 uint index = length();
144 while (index > 0) {
145 index -= 1;
146 if (!at(index)->is_empty()) {
147 break;
148 }
149 res += 1;
150 }
151 return res;
152 }
154 uint HeapRegionSeq::find_contiguous(uint num) {
155 assert(num > 1, "use this only for sequences of length 2 or greater");
156 assert(_next_search_index <= length(),
157 err_msg("_next_search_index: %u should be valid and <= than %u",
158 _next_search_index, length()));
160 uint start = _next_search_index;
161 uint res = find_contiguous_from(start, num);
162 if (res == G1_NULL_HRS_INDEX && start > 0) {
163 // Try starting from the beginning. If _next_search_index was 0,
164 // no point in doing this again.
165 res = find_contiguous_from(0, num);
166 }
167 if (res != G1_NULL_HRS_INDEX) {
168 assert(res < length(), err_msg("res: %u should be valid", res));
169 _next_search_index = res + num;
170 assert(_next_search_index <= length(),
171 err_msg("_next_search_index: %u should be valid and <= than %u",
172 _next_search_index, length()));
173 }
174 return res;
175 }
177 void HeapRegionSeq::iterate(HeapRegionClosure* blk) const {
178 iterate_from((HeapRegion*) NULL, blk);
179 }
181 void HeapRegionSeq::iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const {
182 uint hr_index = 0;
183 if (hr != NULL) {
184 hr_index = hr->hrs_index();
185 }
187 uint len = length();
188 for (uint i = hr_index; i < len; i += 1) {
189 bool res = blk->doHeapRegion(at(i));
190 if (res) {
191 blk->incomplete();
192 return;
193 }
194 }
195 for (uint i = 0; i < hr_index; i += 1) {
196 bool res = blk->doHeapRegion(at(i));
197 if (res) {
198 blk->incomplete();
199 return;
200 }
201 }
202 }
204 MemRegion HeapRegionSeq::shrink_by(size_t shrink_bytes,
205 uint* num_regions_deleted) {
206 // Reset this in case it's currently pointing into the regions that
207 // we just removed.
208 _next_search_index = 0;
210 assert(shrink_bytes % os::vm_page_size() == 0, "unaligned");
211 assert(shrink_bytes % HeapRegion::GrainBytes == 0, "unaligned");
212 assert(length() > 0, "the region sequence should not be empty");
213 assert(length() <= _allocated_length, "invariant");
214 assert(_allocated_length > 0, "we should have at least one region committed");
216 // around the loop, i will be the next region to be removed
217 uint i = length() - 1;
218 assert(i > 0, "we should never remove all regions");
219 // [last_start, end) is the MemRegion that covers the regions we will remove.
220 HeapWord* end = at(i)->end();
221 HeapWord* last_start = end;
222 *num_regions_deleted = 0;
223 while (shrink_bytes > 0) {
224 HeapRegion* cur = at(i);
225 // We should leave the humongous regions where they are.
226 if (cur->isHumongous()) break;
227 // We should stop shrinking if we come across a non-empty region.
228 if (!cur->is_empty()) break;
230 i -= 1;
231 *num_regions_deleted += 1;
232 shrink_bytes -= cur->capacity();
233 last_start = cur->bottom();
234 decrement_length(&_length);
235 // We will reclaim the HeapRegion. _allocated_length should be
236 // covering this index. So, even though we removed the region from
237 // the active set by decreasing _length, we still have it
238 // available in the future if we need to re-use it.
239 assert(i > 0, "we should never remove all regions");
240 assert(length() > 0, "we should never remove all regions");
241 }
242 return MemRegion(last_start, end);
243 }
245 #ifndef PRODUCT
246 void HeapRegionSeq::verify_optional() {
247 guarantee(_length <= _allocated_length,
248 err_msg("invariant: _length: %u _allocated_length: %u",
249 _length, _allocated_length));
250 guarantee(_allocated_length <= _max_length,
251 err_msg("invariant: _allocated_length: %u _max_length: %u",
252 _allocated_length, _max_length));
253 guarantee(_next_search_index <= _length,
254 err_msg("invariant: _next_search_index: %u _length: %u",
255 _next_search_index, _length));
257 HeapWord* prev_end = _heap_bottom;
258 for (uint i = 0; i < _allocated_length; i += 1) {
259 HeapRegion* hr = _regions[i];
260 guarantee(hr != NULL, err_msg("invariant: i: %u", i));
261 guarantee(hr->bottom() == prev_end,
262 err_msg("invariant i: %u "HR_FORMAT" prev_end: "PTR_FORMAT,
263 i, HR_FORMAT_PARAMS(hr), prev_end));
264 guarantee(hr->hrs_index() == i,
265 err_msg("invariant: i: %u hrs_index(): %u", i, hr->hrs_index()));
266 if (i < _length) {
267 // Asserts will fire if i is >= _length
268 HeapWord* addr = hr->bottom();
269 guarantee(addr_to_region(addr) == hr, "sanity");
270 guarantee(addr_to_region_unsafe(addr) == hr, "sanity");
271 } else {
272 guarantee(hr->is_empty(), "sanity");
273 guarantee(!hr->isHumongous(), "sanity");
274 // using assert instead of guarantee here since containing_set()
275 // is only available in non-product builds.
276 assert(hr->containing_set() == NULL, "sanity");
277 }
278 if (hr->startsHumongous()) {
279 prev_end = hr->orig_end();
280 } else {
281 prev_end = hr->end();
282 }
283 }
284 for (uint i = _allocated_length; i < _max_length; i += 1) {
285 guarantee(_regions[i] == NULL, err_msg("invariant i: %u", i));
286 }
287 }
288 #endif // PRODUCT