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 */
24
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"
31
32 // Private
33
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));
39
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 }
71
72 // Public
73
74 MemRegion HeapRegionSeq::expand_to(HeapWord* new_end, FreeRegionList* list) {
75 assert(_heap_end < new_end && new_end <= _max_heap_end,
76 err_msg("new_end: "PTR_FORMAT" heap end: "PTR_FORMAT" "
77 "max heap end: "PTR_FORMAT, new_end, _heap_end, _max_heap_end));
78 G1CollectedHeap* g1h = G1CollectedHeap::heap();
79
80 uint new_length = length_for(new_end);
81 uint index = length();
82 HeapWord* next_hr_bottom = _heap_end;
83 while (index < new_length) {
84 assert(length_for(next_hr_bottom) == index,
85 err_msg("invariant, length_for: "PTR_FORMAT" %u index: %u",
86 next_hr_bottom, length_for(next_hr_bottom), index));
87
88 if (index == 0) {
89 // We have not allocated any regions so far.
90 assert(next_hr_bottom == _heap_bottom, "invariant");
91 } else {
92 // The previous region should exist.
93 assert(_regions[index - 1] != NULL, "invariant");
94 // next_hr_bottom should match the end of the previous region.
95 assert(next_hr_bottom == _regions[index - 1]->end(), "invariant");
96 }
97
98 HeapRegion* hr;
99 if (index < _length_high_watermark) {
100 // This region should have been previously allocated.
101 assert(_regions[index] != NULL, err_msg("invariant, index: %u", index));
102
103 hr = _regions[index];
104 } else {
105 // We have to allocate a new region.
106 assert(_regions[index] == NULL, err_msg("invariant, index: %u", index));
107
108 hr = g1h->new_heap_region(index, next_hr_bottom);
109 // If allocation fails, bail out and return what we have done so far.
110 if (hr == NULL) break;
111 _regions[index] = hr;
112 }
113 list->add_as_tail(hr);
114
115 index += 1;
116 next_hr_bottom = hr->end();
117 }
118
119 HeapWord* prev_heap_end = update_heap_end(next_hr_bottom);
120 return MemRegion(prev_heap_end, next_hr_bottom);
121 }
122
123 uint HeapRegionSeq::free_suffix() {
124 uint res = 0;
125 uint index = length();
126 while (index > 0) {
127 index -= 1;
128 if (!at(index)->is_empty()) break;
129 res += 1;
130 }
131 return res;
132 }
133
134 uint HeapRegionSeq::find_contiguous(uint num) {
135 assert(num > 1, "use this only for sequences of length 2 or greater");
136 assert(_next_search_index <= length(),
137 err_msg("_next_search_index: %u should be valid and <= than %u",
138 _next_search_index, length()));
139
140 uint start = _next_search_index;
141 uint res = find_contiguous_from(start, num);
142 if (res == G1_NULL_HRS_INDEX && start > 0) {
143 // Try starting from the beginning. If _next_search_index was 0,
144 // no point in doing this again.
145 res = find_contiguous_from(0, num);
146 }
147 if (res != G1_NULL_HRS_INDEX) {
148 assert(res < length(), err_msg("res: %u should be valid", res));
149 _next_search_index = res + num;
150 assert(_next_search_index <= length(),
151 err_msg("_next_search_index: %u should be valid and <= than %u",
152 _next_search_index, length()));
153 }
154 return res;
155 }
156
157 void HeapRegionSeq::iterate(HeapRegionClosure* blk) const {
158 iterate_from((HeapRegion*) NULL, blk);
159 }
160
161 void HeapRegionSeq::iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const {
162 uint hr_index = 0;
163 if (hr != NULL) {
164 hr_index = hr->hrs_index();
165 }
166
167 uint len = length();
168 for (uint i = hr_index; i < len; i += 1) {
169 bool res = blk->doHeapRegion(at(i));
170 if (res) {
171 blk->incomplete();
172 return;
173 }
174 }
175 for (uint i = 0; i < hr_index; i += 1) {
176 bool res = blk->doHeapRegion(at(i));
177 if (res) {
178 blk->incomplete();
179 return;
180 }
181 }
182 }
183
184 MemRegion HeapRegionSeq::shrink_to(HeapWord* new_end,
185 uint* num_regions_deleted) {
186 assert(_heap_bottom < new_end && new_end <= _heap_end,
187 err_msg("new_end: "PTR_FORMAT" heap bottom: "PTR_FORMAT" "
188 "heap end: "PTR_FORMAT, new_end, _heap_bottom, _heap_end));
189
190 // Reset this in case it's currently pointing into the regions that
191 // we just removed.
192 _next_search_index = 0;
193
194 uint new_length = length_for(new_end);
195 uint index = length();
196 HeapWord* last_hr_bottom = _heap_end;
197 while (index > new_length) {
198 assert(length_for(last_hr_bottom) == index,
199 err_msg("invariant, length_for: "PTR_FORMAT" %u index: %u",
200 last_hr_bottom, length_for(last_hr_bottom), index));
201
202 HeapRegion* hr = at(index - 1);
203 // We should leave the humongous regions where they are.
204 if (hr->isHumongous()) break;
205 // We should stop shrinking if we come across a non-empty region.
206 if (!hr->is_empty()) break;
207
208 index -= 1;
209 last_hr_bottom = hr->bottom();
210 }
211
212 *num_regions_deleted = length() - index;
213
214 if (new_end == _heap_end) {
215 assert(*num_regions_deleted == 0, "invariant");
216 } else {
217 assert(*num_regions_deleted > 0, "invariant");
218 }
219
220 HeapWord* prev_heap_end = update_heap_end(last_hr_bottom);
221 return MemRegion(last_hr_bottom, prev_heap_end);
222 }
223
224 #ifndef PRODUCT
225 void HeapRegionSeq::verify_optional() {
226 G1HeapSpanningTableBase::verify_optional();
227
228 guarantee(_next_search_index <= _length,
229 err_msg("invariant: _next_search_index: %u _length: %u",
230 _next_search_index, _length));
231
232 HeapWord* prev_end = _heap_bottom;
233 for (uint i = 0; i < _length_high_watermark; i += 1) {
234 HeapRegion* hr = _regions[i];
235 guarantee(hr != NULL, err_msg("invariant: i: %u", i));
236 guarantee(hr->bottom() == prev_end,
237 err_msg("invariant i: %u "HR_FORMAT" prev_end: "PTR_FORMAT,
238 i, HR_FORMAT_PARAMS(hr), prev_end));
239 guarantee(hr->hrs_index() == i,
240 err_msg("invariant: i: %u hrs_index(): %u", i, hr->hrs_index()));
241 if (i < _length) {
242 // Asserts will fire if i is >= _length
243 HeapWord* addr = hr->bottom();
244 guarantee(at(addr) == hr, "sanity");
245 guarantee(at_unsafe(addr) == hr, "sanity");
246 } else {
247 guarantee(hr->is_empty(), "sanity");
248 guarantee(!hr->isHumongous(), "sanity");
249 // using assert instead of guarantee here since containing_set()
250 // is only available in non-product builds.
251 assert(hr->containing_set() == NULL, "sanity");
252 }
253 if (hr->startsHumongous()) {
254 prev_end = hr->orig_end();
255 } else {
256 prev_end = hr->end();
257 }
258 }
259 for (uint i = _length_high_watermark; i < _max_length; i += 1) {
260 guarantee(_regions[i] == NULL, err_msg("invariant i: %u", i));
261 }
262 }
263 #endif // PRODUCT
264
265 void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* max_end) {
266 initialize_base(bottom, max_end, HeapRegion::LogOfHRGrainBytes);
267 _next_search_index = 0;
268 _regions = create_new_array();
269 _regions_biased = get_biased_array(_regions);
270 }