Mon, 02 Aug 2010 12:51:43 -0700
6814437: G1: remove the _new_refs array
Summary: The per-worker _new_refs array is used to hold references that point into the collection set. It is populated during RSet updating and subsequently processed. In the event of an evacuation failure it processed again to recreate the RSets of regions in the collection set. Remove the per-worker _new_refs array by processing the references directly. Use a DirtyCardQueue to hold the cards containing the references so that the RSets of regions in the collection set can be recreated when handling an evacuation failure.
Reviewed-by: iveresov, jmasa, tonyp
1 /*
2 * Copyright (c) 2001, 2009, 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 "incls/_precompiled.incl"
26 # include "incls/_collectionSetChooser.cpp.incl"
28 CSetChooserCache::CSetChooserCache() {
29 for (int i = 0; i < CacheLength; ++i)
30 _cache[i] = NULL;
31 clear();
32 }
34 void CSetChooserCache::clear() {
35 _occupancy = 0;
36 _first = 0;
37 for (int i = 0; i < CacheLength; ++i) {
38 HeapRegion *hr = _cache[i];
39 if (hr != NULL)
40 hr->set_sort_index(-1);
41 _cache[i] = NULL;
42 }
43 }
45 #ifndef PRODUCT
46 bool CSetChooserCache::verify() {
47 int index = _first;
48 HeapRegion *prev = NULL;
49 for (int i = 0; i < _occupancy; ++i) {
50 guarantee(_cache[index] != NULL, "cache entry should not be empty");
51 HeapRegion *hr = _cache[index];
52 guarantee(!hr->is_young(), "should not be young!");
53 if (prev != NULL) {
54 guarantee(prev->gc_efficiency() >= hr->gc_efficiency(),
55 "cache should be correctly ordered");
56 }
57 guarantee(hr->sort_index() == get_sort_index(index),
58 "sort index should be correct");
59 index = trim_index(index + 1);
60 prev = hr;
61 }
63 for (int i = 0; i < (CacheLength - _occupancy); ++i) {
64 guarantee(_cache[index] == NULL, "cache entry should be empty");
65 index = trim_index(index + 1);
66 }
68 guarantee(index == _first, "we should have reached where we started from");
69 return true;
70 }
71 #endif // PRODUCT
73 void CSetChooserCache::insert(HeapRegion *hr) {
74 assert(!is_full(), "cache should not be empty");
75 hr->calc_gc_efficiency();
77 int empty_index;
78 if (_occupancy == 0) {
79 empty_index = _first;
80 } else {
81 empty_index = trim_index(_first + _occupancy);
82 assert(_cache[empty_index] == NULL, "last slot should be empty");
83 int last_index = trim_index(empty_index - 1);
84 HeapRegion *last = _cache[last_index];
85 assert(last != NULL,"as the cache is not empty, last should not be empty");
86 while (empty_index != _first &&
87 last->gc_efficiency() < hr->gc_efficiency()) {
88 _cache[empty_index] = last;
89 last->set_sort_index(get_sort_index(empty_index));
90 empty_index = last_index;
91 last_index = trim_index(last_index - 1);
92 last = _cache[last_index];
93 }
94 }
95 _cache[empty_index] = hr;
96 hr->set_sort_index(get_sort_index(empty_index));
98 ++_occupancy;
99 assert(verify(), "cache should be consistent");
100 }
102 HeapRegion *CSetChooserCache::remove_first() {
103 if (_occupancy > 0) {
104 assert(_cache[_first] != NULL, "cache should have at least one region");
105 HeapRegion *ret = _cache[_first];
106 _cache[_first] = NULL;
107 ret->set_sort_index(-1);
108 --_occupancy;
109 _first = trim_index(_first + 1);
110 assert(verify(), "cache should be consistent");
111 return ret;
112 } else {
113 return NULL;
114 }
115 }
117 // this is a bit expensive... but we expect that it should not be called
118 // to often.
119 void CSetChooserCache::remove(HeapRegion *hr) {
120 assert(_occupancy > 0, "cache should not be empty");
121 assert(hr->sort_index() < -1, "should already be in the cache");
122 int index = get_index(hr->sort_index());
123 assert(_cache[index] == hr, "index should be correct");
124 int next_index = trim_index(index + 1);
125 int last_index = trim_index(_first + _occupancy - 1);
126 while (index != last_index) {
127 assert(_cache[next_index] != NULL, "should not be null");
128 _cache[index] = _cache[next_index];
129 _cache[index]->set_sort_index(get_sort_index(index));
131 index = next_index;
132 next_index = trim_index(next_index+1);
133 }
134 assert(index == last_index, "should have reached the last one");
135 _cache[index] = NULL;
136 hr->set_sort_index(-1);
137 --_occupancy;
138 assert(verify(), "cache should be consistent");
139 }
141 static inline int orderRegions(HeapRegion* hr1, HeapRegion* hr2) {
142 if (hr1 == NULL) {
143 if (hr2 == NULL) return 0;
144 else return 1;
145 } else if (hr2 == NULL) {
146 return -1;
147 }
148 if (hr2->gc_efficiency() < hr1->gc_efficiency()) return -1;
149 else if (hr1->gc_efficiency() < hr2->gc_efficiency()) return 1;
150 else return 0;
151 }
153 static int orderRegions(HeapRegion** hr1p, HeapRegion** hr2p) {
154 return orderRegions(*hr1p, *hr2p);
155 }
157 CollectionSetChooser::CollectionSetChooser() :
158 // The line below is the worst bit of C++ hackery I've ever written
159 // (Detlefs, 11/23). You should think of it as equivalent to
160 // "_regions(100, true)": initialize the growable array and inform it
161 // that it should allocate its elem array(s) on the C heap. The first
162 // argument, however, is actually a comma expression (new-expr, 100).
163 // The purpose of the new_expr is to inform the growable array that it
164 // is *already* allocated on the C heap: it uses the placement syntax to
165 // keep it from actually doing any allocation.
166 _markedRegions((ResourceObj::operator new (sizeof(GrowableArray<HeapRegion*>),
167 (void*)&_markedRegions,
168 ResourceObj::C_HEAP),
169 100),
170 true),
171 _curMarkedIndex(0),
172 _numMarkedRegions(0),
173 _unmarked_age_1_returned_as_new(false),
174 _first_par_unreserved_idx(0)
175 {}
179 #ifndef PRODUCT
180 bool CollectionSetChooser::verify() {
181 int index = 0;
182 guarantee(_curMarkedIndex <= _numMarkedRegions,
183 "_curMarkedIndex should be within bounds");
184 while (index < _curMarkedIndex) {
185 guarantee(_markedRegions.at(index++) == NULL,
186 "all entries before _curMarkedIndex should be NULL");
187 }
188 HeapRegion *prev = NULL;
189 while (index < _numMarkedRegions) {
190 HeapRegion *curr = _markedRegions.at(index++);
191 if (curr != NULL) {
192 int si = curr->sort_index();
193 guarantee(!curr->is_young(), "should not be young!");
194 guarantee(si > -1 && si == (index-1), "sort index invariant");
195 if (prev != NULL) {
196 guarantee(orderRegions(prev, curr) != 1, "regions should be sorted");
197 }
198 prev = curr;
199 }
200 }
201 return _cache.verify();
202 }
203 #endif
205 bool
206 CollectionSetChooser::addRegionToCache() {
207 assert(!_cache.is_full(), "cache should not be full");
209 HeapRegion *hr = NULL;
210 while (hr == NULL && _curMarkedIndex < _numMarkedRegions) {
211 hr = _markedRegions.at(_curMarkedIndex++);
212 }
213 if (hr == NULL)
214 return false;
215 assert(!hr->is_young(), "should not be young!");
216 assert(hr->sort_index() == _curMarkedIndex-1, "sort_index invariant");
217 _markedRegions.at_put(hr->sort_index(), NULL);
218 _cache.insert(hr);
219 assert(!_cache.is_empty(), "cache should not be empty");
220 assert(verify(), "cache should be consistent");
221 return false;
222 }
224 void
225 CollectionSetChooser::fillCache() {
226 while (!_cache.is_full() && addRegionToCache()) {
227 }
228 }
230 void
231 CollectionSetChooser::sortMarkedHeapRegions() {
232 guarantee(_cache.is_empty(), "cache should be empty");
233 // First trim any unused portion of the top in the parallel case.
234 if (_first_par_unreserved_idx > 0) {
235 if (G1PrintParCleanupStats) {
236 gclog_or_tty->print(" Truncating _markedRegions from %d to %d.\n",
237 _markedRegions.length(), _first_par_unreserved_idx);
238 }
239 assert(_first_par_unreserved_idx <= _markedRegions.length(),
240 "Or we didn't reserved enough length");
241 _markedRegions.trunc_to(_first_par_unreserved_idx);
242 }
243 _markedRegions.sort(orderRegions);
244 assert(_numMarkedRegions <= _markedRegions.length(), "Requirement");
245 assert(_numMarkedRegions == 0
246 || _markedRegions.at(_numMarkedRegions-1) != NULL,
247 "Testing _numMarkedRegions");
248 assert(_numMarkedRegions == _markedRegions.length()
249 || _markedRegions.at(_numMarkedRegions) == NULL,
250 "Testing _numMarkedRegions");
251 if (G1PrintParCleanupStats) {
252 gclog_or_tty->print_cr(" Sorted %d marked regions.", _numMarkedRegions);
253 }
254 for (int i = 0; i < _numMarkedRegions; i++) {
255 assert(_markedRegions.at(i) != NULL, "Should be true by sorting!");
256 _markedRegions.at(i)->set_sort_index(i);
257 if (G1PrintRegionLivenessInfo > 0) {
258 if (i == 0) gclog_or_tty->print_cr("Sorted marked regions:");
259 if (i < G1PrintRegionLivenessInfo ||
260 (_numMarkedRegions-i) < G1PrintRegionLivenessInfo) {
261 HeapRegion* hr = _markedRegions.at(i);
262 size_t u = hr->used();
263 gclog_or_tty->print_cr(" Region %d: %d used, %d max live, %5.2f%%.",
264 i, u, hr->max_live_bytes(),
265 100.0*(float)hr->max_live_bytes()/(float)u);
266 }
267 }
268 }
269 if (G1PolicyVerbose > 1)
270 printSortedHeapRegions();
271 assert(verify(), "should now be sorted");
272 }
274 void
275 printHeapRegion(HeapRegion *hr) {
276 if (hr->isHumongous())
277 gclog_or_tty->print("H: ");
278 if (hr->in_collection_set())
279 gclog_or_tty->print("CS: ");
280 gclog_or_tty->print_cr("Region " PTR_FORMAT " (%s%s) "
281 "[" PTR_FORMAT ", " PTR_FORMAT"] "
282 "Used: " SIZE_FORMAT "K, garbage: " SIZE_FORMAT "K.",
283 hr, hr->is_young() ? "Y " : " ",
284 hr->is_marked()? "M1" : "M0",
285 hr->bottom(), hr->end(),
286 hr->used()/K, hr->garbage_bytes()/K);
287 }
289 void
290 CollectionSetChooser::addMarkedHeapRegion(HeapRegion* hr) {
291 assert(!hr->isHumongous(),
292 "Humongous regions shouldn't be added to the collection set");
293 assert(!hr->is_young(), "should not be young!");
294 _markedRegions.append(hr);
295 _numMarkedRegions++;
296 hr->calc_gc_efficiency();
297 }
299 void
300 CollectionSetChooser::
301 prepareForAddMarkedHeapRegionsPar(size_t n_regions, size_t chunkSize) {
302 _first_par_unreserved_idx = 0;
303 size_t max_waste = ParallelGCThreads * chunkSize;
304 // it should be aligned with respect to chunkSize
305 size_t aligned_n_regions =
306 (n_regions + (chunkSize - 1)) / chunkSize * chunkSize;
307 assert( aligned_n_regions % chunkSize == 0, "should be aligned" );
308 _markedRegions.at_put_grow((int)(aligned_n_regions + max_waste - 1), NULL);
309 }
311 jint
312 CollectionSetChooser::getParMarkedHeapRegionChunk(jint n_regions) {
313 jint res = Atomic::add(n_regions, &_first_par_unreserved_idx);
314 assert(_markedRegions.length() > res + n_regions - 1,
315 "Should already have been expanded");
316 return res - n_regions;
317 }
319 void
320 CollectionSetChooser::setMarkedHeapRegion(jint index, HeapRegion* hr) {
321 assert(_markedRegions.at(index) == NULL, "precondition");
322 assert(!hr->is_young(), "should not be young!");
323 _markedRegions.at_put(index, hr);
324 hr->calc_gc_efficiency();
325 }
327 void
328 CollectionSetChooser::incNumMarkedHeapRegions(jint inc_by) {
329 (void)Atomic::add(inc_by, &_numMarkedRegions);
330 }
332 void
333 CollectionSetChooser::clearMarkedHeapRegions(){
334 for (int i = 0; i < _markedRegions.length(); i++) {
335 HeapRegion* r = _markedRegions.at(i);
336 if (r != NULL) r->set_sort_index(-1);
337 }
338 _markedRegions.clear();
339 _curMarkedIndex = 0;
340 _numMarkedRegions = 0;
341 _cache.clear();
342 };
344 void
345 CollectionSetChooser::updateAfterFullCollection() {
346 G1CollectedHeap* g1h = G1CollectedHeap::heap();
347 clearMarkedHeapRegions();
348 }
350 void
351 CollectionSetChooser::printSortedHeapRegions() {
352 gclog_or_tty->print_cr("Printing %d Heap Regions sorted by amount of known garbage",
353 _numMarkedRegions);
355 DEBUG_ONLY(int marked_count = 0;)
356 for (int i = 0; i < _markedRegions.length(); i++) {
357 HeapRegion* r = _markedRegions.at(i);
358 if (r != NULL) {
359 printHeapRegion(r);
360 DEBUG_ONLY(marked_count++;)
361 }
362 }
363 assert(marked_count == _numMarkedRegions, "must be");
364 gclog_or_tty->print_cr("Done sorted heap region print");
365 }
367 void CollectionSetChooser::removeRegion(HeapRegion *hr) {
368 int si = hr->sort_index();
369 assert(si == -1 || hr->is_marked(), "Sort index not valid.");
370 if (si > -1) {
371 assert(_markedRegions.at(si) == hr, "Sort index not valid." );
372 _markedRegions.at_put(si, NULL);
373 } else if (si < -1) {
374 assert(_cache.region_in_cache(hr), "should be in the cache");
375 _cache.remove(hr);
376 assert(hr->sort_index() == -1, "sort index invariant");
377 }
378 hr->set_sort_index(-1);
379 }
381 // if time_remaining < 0.0, then this method should try to return
382 // a region, whether it fits within the remaining time or not
383 HeapRegion*
384 CollectionSetChooser::getNextMarkedRegion(double time_remaining,
385 double avg_prediction) {
386 G1CollectedHeap* g1h = G1CollectedHeap::heap();
387 G1CollectorPolicy* g1p = g1h->g1_policy();
388 fillCache();
389 if (_cache.is_empty()) {
390 assert(_curMarkedIndex == _numMarkedRegions,
391 "if cache is empty, list should also be empty");
392 return NULL;
393 }
395 HeapRegion *hr = _cache.get_first();
396 assert(hr != NULL, "if cache not empty, first entry should be non-null");
397 double predicted_time = g1h->predict_region_elapsed_time_ms(hr, false);
399 if (g1p->adaptive_young_list_length()) {
400 if (time_remaining - predicted_time < 0.0) {
401 g1h->check_if_region_is_too_expensive(predicted_time);
402 return NULL;
403 }
404 } else {
405 if (predicted_time > 2.0 * avg_prediction) {
406 return NULL;
407 }
408 }
410 HeapRegion *hr2 = _cache.remove_first();
411 assert(hr == hr2, "cache contents should not have changed");
413 return hr;
414 }