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 uint HeapRegionSetBase::calculate_region_num(HeapRegion* hr) {
39 assert(hr->startsHumongous(), "pre-condition");
40 assert(hr->capacity() % HeapRegion::GrainBytes == 0, "invariant");
41 uint region_num = (uint) (hr->capacity() >> HeapRegion::LogOfHRGrainBytes);
42 assert(region_num > 0, "sanity");
43 return region_num;
44 }
45
46 void HeapRegionSetBase::fill_in_ext_msg(hrs_ext_msg* msg, const char* message) {
47 msg->append("[%s] %s ln: %u rn: %u cy: "SIZE_FORMAT" ud: "SIZE_FORMAT,
48 name(), message, length(), region_num(),
49 total_capacity_bytes(), total_used_bytes());
50 fill_in_ext_msg_extra(msg);
51 }
52
53 bool HeapRegionSetBase::verify_region(HeapRegion* hr,
54 HeapRegionSetBase* expected_containing_set) {
55 const char* error_message = NULL;
56
57 if (!regions_humongous()) {
58 if (hr->isHumongous()) {
59 error_message = "the region should not be humongous";
60 }
61 } else {
62 if (!hr->isHumongous() || !hr->startsHumongous()) {
63 error_message = "the region should be 'starts humongous'";
64 }
65 }
66
67 if (!regions_empty()) {
68 if (hr->is_empty()) {
69 error_message = "the region should not be empty";
70 }
71 } else {
72 if (!hr->is_empty()) {
73 error_message = "the region should be empty";
74 }
75 }
76
77 #ifdef ASSERT
78 // The _containing_set field is only available when ASSERT is defined.
79 if (hr->containing_set() != expected_containing_set) {
80 error_message = "inconsistent containing set found";
81 }
82 #endif // ASSERT
83
84 const char* extra_error_message = verify_region_extra(hr);
85 if (extra_error_message != NULL) {
86 error_message = extra_error_message;
87 }
88
89 if (error_message != NULL) {
90 outputStream* out = tty;
91 out->cr();
92 out->print_cr("## [%s] %s", name(), error_message);
93 out->print_cr("## Offending Region: "PTR_FORMAT, hr);
94 out->print_cr(" "HR_FORMAT, HR_FORMAT_PARAMS(hr));
95 #ifdef ASSERT
96 out->print_cr(" containing set: "PTR_FORMAT, hr->containing_set());
97 #endif // ASSERT
98 out->print_cr("## Offending Region Set: "PTR_FORMAT, this);
99 print_on(out);
100 return false;
101 } else {
102 return true;
103 }
104 }
105
106 void HeapRegionSetBase::verify() {
107 // It's important that we also observe the MT safety protocol even
108 // for the verification calls. If we do verification without the
109 // appropriate locks and the set changes underneath our feet
110 // verification might fail and send us on a wild goose chase.
111 hrs_assert_mt_safety_ok(this);
112
113 guarantee(( is_empty() && length() == 0 && region_num() == 0 &&
114 total_used_bytes() == 0 && total_capacity_bytes() == 0) ||
115 (!is_empty() && length() >= 0 && region_num() >= 0 &&
116 total_used_bytes() >= 0 && total_capacity_bytes() >= 0),
117 hrs_ext_msg(this, "invariant"));
118
119 guarantee((!regions_humongous() && region_num() == length()) ||
120 ( regions_humongous() && region_num() >= length()),
121 hrs_ext_msg(this, "invariant"));
122
123 guarantee(!regions_empty() || total_used_bytes() == 0,
124 hrs_ext_msg(this, "invariant"));
125
126 guarantee(total_used_bytes() <= total_capacity_bytes(),
127 hrs_ext_msg(this, "invariant"));
128 }
129
130 void HeapRegionSetBase::verify_start() {
131 // See comment in verify() about MT safety and verification.
132 hrs_assert_mt_safety_ok(this);
133 assert(!_verify_in_progress,
134 hrs_ext_msg(this, "verification should not be in progress"));
135
136 // Do the basic verification first before we do the checks over the regions.
137 HeapRegionSetBase::verify();
138
139 _calc_length = 0;
140 _calc_region_num = 0;
141 _calc_total_capacity_bytes = 0;
142 _calc_total_used_bytes = 0;
143 _verify_in_progress = true;
144 }
145
146 void HeapRegionSetBase::verify_next_region(HeapRegion* hr) {
147 // See comment in verify() about MT safety and verification.
148 hrs_assert_mt_safety_ok(this);
149 assert(_verify_in_progress,
150 hrs_ext_msg(this, "verification should be in progress"));
151
152 guarantee(verify_region(hr, this), hrs_ext_msg(this, "region verification"));
153
154 _calc_length += 1;
155 if (!hr->isHumongous()) {
156 _calc_region_num += 1;
157 } else {
158 _calc_region_num += calculate_region_num(hr);
159 }
160 _calc_total_capacity_bytes += hr->capacity();
161 _calc_total_used_bytes += hr->used();
162 }
163
164 void HeapRegionSetBase::verify_end() {
165 // See comment in verify() about MT safety and verification.
166 hrs_assert_mt_safety_ok(this);
167 assert(_verify_in_progress,
168 hrs_ext_msg(this, "verification should be in progress"));
169
170 guarantee(length() == _calc_length,
171 hrs_err_msg("[%s] length: %u should be == calc length: %u",
172 name(), length(), _calc_length));
173
174 guarantee(region_num() == _calc_region_num,
175 hrs_err_msg("[%s] region num: %u should be == calc region num: %u",
176 name(), region_num(), _calc_region_num));
177
178 guarantee(total_capacity_bytes() == _calc_total_capacity_bytes,
179 hrs_err_msg("[%s] capacity bytes: "SIZE_FORMAT" should be == "
180 "calc capacity bytes: "SIZE_FORMAT,
181 name(),
182 total_capacity_bytes(), _calc_total_capacity_bytes));
183
184 guarantee(total_used_bytes() == _calc_total_used_bytes,
185 hrs_err_msg("[%s] used bytes: "SIZE_FORMAT" should be == "
186 "calc used bytes: "SIZE_FORMAT,
187 name(), total_used_bytes(), _calc_total_used_bytes));
188
189 _verify_in_progress = false;
190 }
191
192 void HeapRegionSetBase::clear_phase() {
193 assert(_phase != HRSPhaseNone, "pre-condition");
194 _phase = HRSPhaseNone;
195 }
196
197 void HeapRegionSetBase::set_phase(HRSPhase phase) {
198 assert(_phase == HRSPhaseNone, "pre-condition");
199 assert(phase != HRSPhaseNone, "pre-condition");
200 _phase = phase;
201 }
202
203 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
204 out->cr();
205 out->print_cr("Set: %s ("PTR_FORMAT")", name(), this);
206 out->print_cr(" Region Assumptions");
207 out->print_cr(" humongous : %s", BOOL_TO_STR(regions_humongous()));
208 out->print_cr(" empty : %s", BOOL_TO_STR(regions_empty()));
209 out->print_cr(" Attributes");
210 out->print_cr(" length : %14u", length());
211 out->print_cr(" region num : %14u", region_num());
212 out->print_cr(" total capacity : "SIZE_FORMAT_W(14)" bytes",
213 total_capacity_bytes());
214 out->print_cr(" total used : "SIZE_FORMAT_W(14)" bytes",
215 total_used_bytes());
216 }
217
218 void HeapRegionSetBase::clear() {
219 _length = 0;
220 _region_num = 0;
221 _total_used_bytes = 0;
222 }
223
224 HeapRegionSetBase::HeapRegionSetBase(const char* name)
225 : _name(name), _verify_in_progress(false),
226 _calc_length(0), _calc_region_num(0),
227 _calc_total_capacity_bytes(0), _calc_total_used_bytes(0) { }
228
229 //////////////////// HeapRegionSet ////////////////////
230
231 void HeapRegionSet::update_from_proxy(HeapRegionSet* proxy_set) {
232 hrs_assert_mt_safety_ok(this);
233 hrs_assert_mt_safety_ok(proxy_set);
234 hrs_assert_sets_match(this, proxy_set);
235
236 verify_optional();
237 proxy_set->verify_optional();
238
239 if (proxy_set->is_empty()) return;
240
241 assert(proxy_set->length() <= _length,
242 hrs_err_msg("[%s] proxy set length: %u should be <= length: %u",
243 name(), proxy_set->length(), _length));
244 _length -= proxy_set->length();
245
246 assert(proxy_set->region_num() <= _region_num,
247 hrs_err_msg("[%s] proxy set region num: %u should be <= region num: %u",
248 name(), proxy_set->region_num(), _region_num));
249 _region_num -= proxy_set->region_num();
250
251 assert(proxy_set->total_used_bytes() <= _total_used_bytes,
252 hrs_err_msg("[%s] proxy set used bytes: "SIZE_FORMAT" "
253 "should be <= used bytes: "SIZE_FORMAT,
254 name(), proxy_set->total_used_bytes(),
255 _total_used_bytes));
256 _total_used_bytes -= proxy_set->total_used_bytes();
257
258 proxy_set->clear();
259
260 verify_optional();
261 proxy_set->verify_optional();
262 }
263
264 //////////////////// HeapRegionLinkedList ////////////////////
265
266 void HeapRegionLinkedList::fill_in_ext_msg_extra(hrs_ext_msg* msg) {
267 msg->append(" hd: "PTR_FORMAT" tl: "PTR_FORMAT, head(), tail());
268 }
269
270 void HeapRegionLinkedList::add_as_head(HeapRegionLinkedList* from_list) {
271 hrs_assert_mt_safety_ok(this);
272 hrs_assert_mt_safety_ok(from_list);
273
274 verify_optional();
275 from_list->verify_optional();
276
277 if (from_list->is_empty()) return;
278
279 #ifdef ASSERT
280 HeapRegionLinkedListIterator iter(from_list);
281 while (iter.more_available()) {
282 HeapRegion* hr = iter.get_next();
283 // In set_containing_set() we check that we either set the value
284 // from NULL to non-NULL or vice versa to catch bugs. So, we have
285 // to NULL it first before setting it to the value.
286 hr->set_containing_set(NULL);
287 hr->set_containing_set(this);
288 }
289 #endif // ASSERT
290
291 if (_head != NULL) {
292 assert(length() > 0 && _tail != NULL, hrs_ext_msg(this, "invariant"));
293 from_list->_tail->set_next(_head);
294 } else {
295 assert(length() == 0 && _head == NULL, hrs_ext_msg(this, "invariant"));
296 _tail = from_list->_tail;
297 }
298 _head = from_list->_head;
299
300 _length += from_list->length();
301 _region_num += from_list->region_num();
302 _total_used_bytes += from_list->total_used_bytes();
303 from_list->clear();
304
305 verify_optional();
306 from_list->verify_optional();
307 }
308
309 void HeapRegionLinkedList::add_as_tail(HeapRegionLinkedList* from_list) {
310 hrs_assert_mt_safety_ok(this);
311 hrs_assert_mt_safety_ok(from_list);
312
313 verify_optional();
314 from_list->verify_optional();
315
316 if (from_list->is_empty()) return;
317
318 #ifdef ASSERT
319 HeapRegionLinkedListIterator iter(from_list);
320 while (iter.more_available()) {
321 HeapRegion* hr = iter.get_next();
322 // In set_containing_set() we check that we either set the value
323 // from NULL to non-NULL or vice versa to catch bugs. So, we have
324 // to NULL it first before setting it to the value.
325 hr->set_containing_set(NULL);
326 hr->set_containing_set(this);
327 }
328 #endif // ASSERT
329
330 if (_tail != NULL) {
331 assert(length() > 0 && _head != NULL, hrs_ext_msg(this, "invariant"));
332 _tail->set_next(from_list->_head);
333 } else {
334 assert(length() == 0 && _head == NULL, hrs_ext_msg(this, "invariant"));
335 _head = from_list->_head;
336 }
337 _tail = from_list->_tail;
338
339 _length += from_list->length();
340 _region_num += from_list->region_num();
341 _total_used_bytes += from_list->total_used_bytes();
342 from_list->clear();
343
344 verify_optional();
345 from_list->verify_optional();
346 }
347
348 void HeapRegionLinkedList::remove_all() {
349 hrs_assert_mt_safety_ok(this);
350 verify_optional();
351
352 HeapRegion* curr = _head;
353 while (curr != NULL) {
354 hrs_assert_region_ok(this, curr, this);
355
356 HeapRegion* next = curr->next();
357 curr->set_next(NULL);
358 curr->set_containing_set(NULL);
359 curr = next;
360 }
361 clear();
362
363 verify_optional();
364 }
365
366 void HeapRegionLinkedList::remove_all_pending(uint target_count) {
367 hrs_assert_mt_safety_ok(this);
368 assert(target_count > 1, hrs_ext_msg(this, "pre-condition"));
369 assert(!is_empty(), hrs_ext_msg(this, "pre-condition"));
370
371 verify_optional();
372 DEBUG_ONLY(uint old_length = length();)
373
374 HeapRegion* curr = _head;
375 HeapRegion* prev = NULL;
376 uint count = 0;
377 while (curr != NULL) {
378 hrs_assert_region_ok(this, curr, this);
379 HeapRegion* next = curr->next();
380
381 if (curr->pending_removal()) {
382 assert(count < target_count,
383 hrs_err_msg("[%s] should not come across more regions "
384 "pending for removal than target_count: %u",
385 name(), target_count));
386
387 if (prev == NULL) {
388 assert(_head == curr, hrs_ext_msg(this, "invariant"));
389 _head = next;
390 } else {
391 assert(_head != curr, hrs_ext_msg(this, "invariant"));
392 prev->set_next(next);
393 }
394 if (next == NULL) {
395 assert(_tail == curr, hrs_ext_msg(this, "invariant"));
396 _tail = prev;
397 } else {
398 assert(_tail != curr, hrs_ext_msg(this, "invariant"));
399 }
400
401 curr->set_next(NULL);
402 remove_internal(curr);
403 curr->set_pending_removal(false);
404
405 count += 1;
406
407 // If we have come across the target number of regions we can
408 // just bail out. However, for debugging purposes, we can just
409 // carry on iterating to make sure there are not more regions
410 // tagged with pending removal.
411 DEBUG_ONLY(if (count == target_count) break;)
412 } else {
413 prev = curr;
414 }
415 curr = next;
416 }
417
418 assert(count == target_count,
419 hrs_err_msg("[%s] count: %u should be == target_count: %u",
420 name(), count, target_count));
421 assert(length() + target_count == old_length,
422 hrs_err_msg("[%s] new length should be consistent "
423 "new length: %u old length: %u target_count: %u",
424 name(), length(), old_length, target_count));
425
426 verify_optional();
427 }
428
429 void HeapRegionLinkedList::verify() {
430 // See comment in HeapRegionSetBase::verify() about MT safety and
431 // verification.
432 hrs_assert_mt_safety_ok(this);
433
434 // This will also do the basic verification too.
435 verify_start();
436
437 HeapRegion* curr = _head;
438 HeapRegion* prev1 = NULL;
439 HeapRegion* prev0 = NULL;
440 uint count = 0;
441 while (curr != NULL) {
442 verify_next_region(curr);
443
444 count += 1;
445 guarantee(count < _unrealistically_long_length,
446 hrs_err_msg("[%s] the calculated length: %u "
447 "seems very long, is there maybe a cycle? "
448 "curr: "PTR_FORMAT" prev0: "PTR_FORMAT" "
449 "prev1: "PTR_FORMAT" length: %u",
450 name(), count, curr, prev0, prev1, length()));
451
452 prev1 = prev0;
453 prev0 = curr;
454 curr = curr->next();
455 }
456
457 guarantee(_tail == prev0, hrs_ext_msg(this, "post-condition"));
458
459 verify_end();
460 }
461
462 void HeapRegionLinkedList::clear() {
463 HeapRegionSetBase::clear();
464 _head = NULL;
465 _tail = NULL;
466 }
467
468 void HeapRegionLinkedList::print_on(outputStream* out, bool print_contents) {
469 HeapRegionSetBase::print_on(out, print_contents);
470 out->print_cr(" Linking");
471 out->print_cr(" head : "PTR_FORMAT, _head);
472 out->print_cr(" tail : "PTR_FORMAT, _tail);
473
474 if (print_contents) {
475 out->print_cr(" Contents");
476 HeapRegionLinkedListIterator iter(this);
477 while (iter.more_available()) {
478 HeapRegion* hr = iter.get_next();
479 hr->print_on(out);
480 }
481 }
482 }