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 */
24
25 #include "precompiled.hpp"
26 #include "gc_implementation/g1/heapRegionSet.inline.hpp"
27
28 uint HeapRegionSetBase::_unrealistically_long_length = 0;
29 HRSPhase HeapRegionSetBase::_phase = HRSPhaseNone;
30
31 //////////////////// HeapRegionSetBase ////////////////////
32
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 }
37
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 }
44
45 bool HeapRegionSetBase::verify_region(HeapRegion* hr,
46 HeapRegionSetBase* expected_containing_set) {
47 const char* error_message = NULL;
48
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 }
58
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 }
68
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
75
76 const char* extra_error_message = verify_region_extra(hr);
77 if (extra_error_message != NULL) {
78 error_message = extra_error_message;
79 }
80
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 }
97
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);
104
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"));
110
111 guarantee((!regions_humongous() && region_num() == length()) ||
112 ( regions_humongous() && region_num() >= length()),
113 hrs_ext_msg(this, "invariant"));
114
115 guarantee(!regions_empty() || total_used_bytes() == 0,
116 hrs_ext_msg(this, "invariant"));
117
118 guarantee(total_used_bytes() <= total_capacity_bytes(),
119 hrs_ext_msg(this, "invariant"));
120 }
121
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"));
127
128 // Do the basic verification first before we do the checks over the regions.
129 HeapRegionSetBase::verify();
130
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 }
137
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"));
143
144 guarantee(verify_region(hr, this), hrs_ext_msg(this, "region verification"));
145
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 }
151
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"));
157
158 guarantee(length() == _calc_length,
159 hrs_err_msg("[%s] length: %u should be == calc length: %u",
160 name(), length(), _calc_length));
161
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));
165
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));
171
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));
176
177 _verify_in_progress = false;
178 }
179
180 void HeapRegionSetBase::clear_phase() {
181 assert(_phase != HRSPhaseNone, "pre-condition");
182 _phase = HRSPhaseNone;
183 }
184
185 void HeapRegionSetBase::set_phase(HRSPhase phase) {
186 assert(_phase == HRSPhaseNone, "pre-condition");
187 assert(phase != HRSPhaseNone, "pre-condition");
188 _phase = phase;
189 }
190
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 }
205
206 void HeapRegionSetBase::clear() {
207 _length = 0;
208 _region_num = 0;
209 _total_used_bytes = 0;
210 }
211
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) { }
216
217 //////////////////// HeapRegionSet ////////////////////
218
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);
223
224 verify_optional();
225 proxy_set->verify_optional();
226
227 if (proxy_set->is_empty()) return;
228
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();
233
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();
238
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();
245
246 proxy_set->clear();
247
248 verify_optional();
249 proxy_set->verify_optional();
250 }
251
252 //////////////////// HeapRegionLinkedList ////////////////////
253
254 void HeapRegionLinkedList::fill_in_ext_msg_extra(hrs_ext_msg* msg) {
255 msg->append(" hd: "PTR_FORMAT" tl: "PTR_FORMAT, head(), tail());
256 }
257
258 void HeapRegionLinkedList::add_as_head(HeapRegionLinkedList* from_list) {
259 hrs_assert_mt_safety_ok(this);
260 hrs_assert_mt_safety_ok(from_list);
261
262 verify_optional();
263 from_list->verify_optional();
264
265 if (from_list->is_empty()) return;
266
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
278
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;
287
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();
292
293 verify_optional();
294 from_list->verify_optional();
295 }
296
297 void HeapRegionLinkedList::add_as_tail(HeapRegionLinkedList* from_list) {
298 hrs_assert_mt_safety_ok(this);
299 hrs_assert_mt_safety_ok(from_list);
300
301 verify_optional();
302 from_list->verify_optional();
303
304 if (from_list->is_empty()) return;
305
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
317
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;
326
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();
331
332 verify_optional();
333 from_list->verify_optional();
334 }
335
336 void HeapRegionLinkedList::remove_all() {
337 hrs_assert_mt_safety_ok(this);
338 verify_optional();
339
340 HeapRegion* curr = _head;
341 while (curr != NULL) {
342 hrs_assert_region_ok(this, curr, this);
343
344 HeapRegion* next = curr->next();
345 curr->set_next(NULL);
346 curr->set_containing_set(NULL);
347 curr = next;
348 }
349 clear();
350
351 verify_optional();
352 }
353
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"));
358
359 verify_optional();
360 DEBUG_ONLY(uint old_length = length();)
361
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();
368
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));
374
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 }
388
389 curr->set_next(NULL);
390 remove_internal(curr);
391 curr->set_pending_removal(false);
392
393 count += 1;
394
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 }
405
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));
413
414 verify_optional();
415 }
416
417 void HeapRegionLinkedList::verify() {
418 // See comment in HeapRegionSetBase::verify() about MT safety and
419 // verification.
420 hrs_assert_mt_safety_ok(this);
421
422 // This will also do the basic verification too.
423 verify_start();
424
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);
431
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()));
439
440 prev1 = prev0;
441 prev0 = curr;
442 curr = curr->next();
443 }
444
445 guarantee(_tail == prev0, hrs_ext_msg(this, "post-condition"));
446
447 verify_end();
448 }
449
450 void HeapRegionLinkedList::clear() {
451 HeapRegionSetBase::clear();
452 _head = NULL;
453 _tail = NULL;
454 }
455
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);
461
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 }