1/*
2 * Copyright (c) 2011, 2018, 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/g1/g1CollectedHeap.inline.hpp"
27#include "gc/g1/heapRegionRemSet.hpp"
28#include "gc/g1/heapRegionSet.inline.hpp"
29
30uint FreeRegionList::_unrealistically_long_length = 0;
31
32#ifndef PRODUCT
33void HeapRegionSetBase::verify_region(HeapRegion* hr) {
34 assert(hr->containing_set() == this, "Inconsistent containing set for %u", hr->hrm_index());
35 assert(!hr->is_young(), "Adding young region %u", hr->hrm_index()); // currently we don't use these sets for young regions
36 assert(_checker == NULL || _checker->is_correct_type(hr), "Wrong type of region %u (%s) and set %s",
37 hr->hrm_index(), hr->get_type_str(), name());
38 assert(!hr->is_free() || hr->is_empty(), "Free region %u is not empty for set %s", hr->hrm_index(), name());
39 assert(!hr->is_empty() || hr->is_free() || hr->is_archive(),
40 "Empty region %u is not free or archive for set %s", hr->hrm_index(), name());
41}
42#endif
43
44void HeapRegionSetBase::verify() {
45 // It's important that we also observe the MT safety protocol even
46 // for the verification calls. If we do verification without the
47 // appropriate locks and the set changes underneath our feet
48 // verification might fail and send us on a wild goose chase.
49 check_mt_safety();
50
51 guarantee_heap_region_set(( is_empty() && length() == 0) ||
52 (!is_empty() && length() > 0),
53 "invariant");
54}
55
56void HeapRegionSetBase::verify_start() {
57 // See comment in verify() about MT safety and verification.
58 check_mt_safety();
59 assert_heap_region_set(!_verify_in_progress, "verification should not be in progress");
60
61 // Do the basic verification first before we do the checks over the regions.
62 HeapRegionSetBase::verify();
63
64 _verify_in_progress = true;
65}
66
67void HeapRegionSetBase::verify_end() {
68 // See comment in verify() about MT safety and verification.
69 check_mt_safety();
70 assert_heap_region_set(_verify_in_progress, "verification should be in progress");
71
72 _verify_in_progress = false;
73}
74
75void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
76 out->cr();
77 out->print_cr("Set: %s (" PTR_FORMAT ")", name(), p2i(this));
78 out->print_cr(" Region Type : %s", _checker->get_description());
79 out->print_cr(" Length : %14u", length());
80}
81
82HeapRegionSetBase::HeapRegionSetBase(const char* name, HeapRegionSetChecker* checker)
83 : _checker(checker), _length(0), _name(name), _verify_in_progress(false)
84{
85}
86
87void FreeRegionList::set_unrealistically_long_length(uint len) {
88 guarantee(_unrealistically_long_length == 0, "should only be set once");
89 _unrealistically_long_length = len;
90}
91
92void FreeRegionList::remove_all() {
93 check_mt_safety();
94 verify_optional();
95
96 HeapRegion* curr = _head;
97 while (curr != NULL) {
98 verify_region(curr);
99
100 HeapRegion* next = curr->next();
101 curr->set_next(NULL);
102 curr->set_prev(NULL);
103 curr->set_containing_set(NULL);
104 curr = next;
105 }
106 clear();
107
108 verify_optional();
109}
110
111void FreeRegionList::add_ordered(FreeRegionList* from_list) {
112 check_mt_safety();
113 from_list->check_mt_safety();
114
115 verify_optional();
116 from_list->verify_optional();
117
118 if (from_list->is_empty()) {
119 return;
120 }
121
122 #ifdef ASSERT
123 FreeRegionListIterator iter(from_list);
124 while (iter.more_available()) {
125 HeapRegion* hr = iter.get_next();
126 // In set_containing_set() we check that we either set the value
127 // from NULL to non-NULL or vice versa to catch bugs. So, we have
128 // to NULL it first before setting it to the value.
129 hr->set_containing_set(NULL);
130 hr->set_containing_set(this);
131 }
132 #endif // ASSERT
133
134 if (is_empty()) {
135 assert_free_region_list(length() == 0 && _tail == NULL, "invariant");
136 _head = from_list->_head;
137 _tail = from_list->_tail;
138 } else {
139 HeapRegion* curr_to = _head;
140 HeapRegion* curr_from = from_list->_head;
141
142 while (curr_from != NULL) {
143 while (curr_to != NULL && curr_to->hrm_index() < curr_from->hrm_index()) {
144 curr_to = curr_to->next();
145 }
146
147 if (curr_to == NULL) {
148 // The rest of the from list should be added as tail
149 _tail->set_next(curr_from);
150 curr_from->set_prev(_tail);
151 curr_from = NULL;
152 } else {
153 HeapRegion* next_from = curr_from->next();
154
155 curr_from->set_next(curr_to);
156 curr_from->set_prev(curr_to->prev());
157 if (curr_to->prev() == NULL) {
158 _head = curr_from;
159 } else {
160 curr_to->prev()->set_next(curr_from);
161 }
162 curr_to->set_prev(curr_from);
163
164 curr_from = next_from;
165 }
166 }
167
168 if (_tail->hrm_index() < from_list->_tail->hrm_index()) {
169 _tail = from_list->_tail;
170 }
171 }
172
173 _length += from_list->length();
174 from_list->clear();
175
176 verify_optional();
177 from_list->verify_optional();
178}
179
180void FreeRegionList::remove_starting_at(HeapRegion* first, uint num_regions) {
181 check_mt_safety();
182 assert_free_region_list(num_regions >= 1, "pre-condition");
183 assert_free_region_list(!is_empty(), "pre-condition");
184
185 verify_optional();
186 DEBUG_ONLY(uint old_length = length();)
187
188 HeapRegion* curr = first;
189 uint count = 0;
190 while (count < num_regions) {
191 verify_region(curr);
192 HeapRegion* next = curr->next();
193 HeapRegion* prev = curr->prev();
194
195 assert(count < num_regions,
196 "[%s] should not come across more regions "
197 "pending for removal than num_regions: %u",
198 name(), num_regions);
199
200 if (prev == NULL) {
201 assert_free_region_list(_head == curr, "invariant");
202 _head = next;
203 } else {
204 assert_free_region_list(_head != curr, "invariant");
205 prev->set_next(next);
206 }
207 if (next == NULL) {
208 assert_free_region_list(_tail == curr, "invariant");
209 _tail = prev;
210 } else {
211 assert_free_region_list(_tail != curr, "invariant");
212 next->set_prev(prev);
213 }
214 if (_last == curr) {
215 _last = NULL;
216 }
217
218 curr->set_next(NULL);
219 curr->set_prev(NULL);
220 remove(curr);
221
222 count++;
223 curr = next;
224 }
225
226 assert(count == num_regions,
227 "[%s] count: %u should be == num_regions: %u",
228 name(), count, num_regions);
229 assert(length() + num_regions == old_length,
230 "[%s] new length should be consistent "
231 "new length: %u old length: %u num_regions: %u",
232 name(), length(), old_length, num_regions);
233
234 verify_optional();
235}
236
237uint FreeRegionList::num_of_regions_in_range(uint start, uint end) const {
238 HeapRegion* cur = _head;
239 uint num = 0;
240 while (cur != NULL) {
241 uint index = cur->hrm_index();
242 if (index > end) {
243 break;
244 } else if (index >= start) {
245 num++;
246 }
247 cur = cur->next();
248 }
249 return num;
250}
251
252void FreeRegionList::verify() {
253 // See comment in HeapRegionSetBase::verify() about MT safety and
254 // verification.
255 check_mt_safety();
256
257 // This will also do the basic verification too.
258 verify_start();
259
260 verify_list();
261
262 verify_end();
263}
264
265void FreeRegionList::clear() {
266 _length = 0;
267 _head = NULL;
268 _tail = NULL;
269 _last = NULL;
270}
271
272void FreeRegionList::verify_list() {
273 HeapRegion* curr = _head;
274 HeapRegion* prev1 = NULL;
275 HeapRegion* prev0 = NULL;
276 uint count = 0;
277 size_t capacity = 0;
278 uint last_index = 0;
279
280 guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev");
281 while (curr != NULL) {
282 verify_region(curr);
283
284 count++;
285 guarantee(count < _unrealistically_long_length,
286 "[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: " PTR_FORMAT " prev0: " PTR_FORMAT " " "prev1: " PTR_FORMAT " length: %u",
287 name(), count, p2i(curr), p2i(prev0), p2i(prev1), length());
288
289 if (curr->next() != NULL) {
290 guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up");
291 }
292 guarantee(curr->hrm_index() == 0 || curr->hrm_index() > last_index, "List should be sorted");
293 last_index = curr->hrm_index();
294
295 capacity += curr->capacity();
296
297 prev1 = prev0;
298 prev0 = curr;
299 curr = curr->next();
300 }
301
302 guarantee(_tail == prev0, "Expected %s to end with %u but it ended with %u.", name(), _tail->hrm_index(), prev0->hrm_index());
303 guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next");
304 guarantee(length() == count, "%s count mismatch. Expected %u, actual %u.", name(), length(), count);
305}
306