1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/gc_implementation/g1/heapRegionSet.cpp Wed Jan 19 19:30:42 2011 -0500
1.3 @@ -0,0 +1,438 @@
1.4 +/*
1.5 + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#include "precompiled.hpp"
1.29 +#include "gc_implementation/g1/heapRegionSet.inline.hpp"
1.30 +
1.31 +size_t HeapRegionSetBase::_unrealistically_long_length = 0;
1.32 +
1.33 +//////////////////// HeapRegionSetBase ////////////////////
1.34 +
1.35 +void HeapRegionSetBase::set_unrealistically_long_length(size_t len) {
1.36 + guarantee(_unrealistically_long_length == 0, "should only be set once");
1.37 + _unrealistically_long_length = len;
1.38 +}
1.39 +
1.40 +size_t HeapRegionSetBase::calculate_region_num(HeapRegion* hr) {
1.41 + assert(hr->startsHumongous(), "pre-condition");
1.42 + assert(hr->capacity() % HeapRegion::GrainBytes == 0, "invariant");
1.43 + size_t region_num = hr->capacity() >> HeapRegion::LogOfHRGrainBytes;
1.44 + assert(region_num > 0, "sanity");
1.45 + return region_num;
1.46 +}
1.47 +
1.48 +void HeapRegionSetBase::fill_in_ext_msg(hrl_ext_msg* msg, const char* message) {
1.49 + msg->append("[%s] %s "
1.50 + "ln: "SIZE_FORMAT" rn: "SIZE_FORMAT" "
1.51 + "cy: "SIZE_FORMAT" ud: "SIZE_FORMAT,
1.52 + name(), message, length(), region_num(),
1.53 + total_capacity_bytes(), total_used_bytes());
1.54 + fill_in_ext_msg_extra(msg);
1.55 +}
1.56 +
1.57 +bool HeapRegionSetBase::verify_region(HeapRegion* hr,
1.58 + HeapRegionSetBase* expected_containing_set) {
1.59 + const char* error_message = NULL;
1.60 +
1.61 + if (!regions_humongous()) {
1.62 + if (hr->isHumongous()) {
1.63 + error_message = "the region should not be humongous";
1.64 + }
1.65 + } else {
1.66 + if (!hr->isHumongous() || !hr->startsHumongous()) {
1.67 + error_message = "the region should be 'starts humongous'";
1.68 + }
1.69 + }
1.70 +
1.71 + if (!regions_empty()) {
1.72 + if (hr->is_empty()) {
1.73 + error_message = "the region should not be empty";
1.74 + }
1.75 + } else {
1.76 + if (!hr->is_empty()) {
1.77 + error_message = "the region should be empty";
1.78 + }
1.79 + }
1.80 +
1.81 +#ifdef ASSERT
1.82 + // The _containing_set field is only available when ASSERT is defined.
1.83 + if (hr->containing_set() != expected_containing_set) {
1.84 + error_message = "inconsistent containing set found";
1.85 + }
1.86 +#endif // ASSERT
1.87 +
1.88 + const char* extra_error_message = verify_region_extra(hr);
1.89 + if (extra_error_message != NULL) {
1.90 + error_message = extra_error_message;
1.91 + }
1.92 +
1.93 + if (error_message != NULL) {
1.94 + outputStream* out = tty;
1.95 + out->cr();
1.96 + out->print_cr("## [%s] %s", name(), error_message);
1.97 + out->print_cr("## Offending Region: "PTR_FORMAT, hr);
1.98 + out->print_cr(" "HR_FORMAT, HR_FORMAT_PARAMS(hr));
1.99 +#ifdef ASSERT
1.100 + out->print_cr(" containing set: "PTR_FORMAT, hr->containing_set());
1.101 +#endif // ASSERT
1.102 + out->print_cr("## Offending Region Set: "PTR_FORMAT, this);
1.103 + print_on(out);
1.104 + return false;
1.105 + } else {
1.106 + return true;
1.107 + }
1.108 +}
1.109 +
1.110 +void HeapRegionSetBase::verify() {
1.111 + // It's important that we also observe the MT safety protocol even
1.112 + // for the verification calls. If we do verification without the
1.113 + // appropriate locks and the set changes underneath our feet
1.114 + // verification might fail and send us on a wild goose chase.
1.115 + hrl_assert_mt_safety_ok(this);
1.116 +
1.117 + guarantee(( is_empty() && length() == 0 && region_num() == 0 &&
1.118 + total_used_bytes() == 0 && total_capacity_bytes() == 0) ||
1.119 + (!is_empty() && length() >= 0 && region_num() >= 0 &&
1.120 + total_used_bytes() >= 0 && total_capacity_bytes() >= 0),
1.121 + hrl_ext_msg(this, "invariant"));
1.122 +
1.123 + guarantee((!regions_humongous() && region_num() == length()) ||
1.124 + ( regions_humongous() && region_num() >= length()),
1.125 + hrl_ext_msg(this, "invariant"));
1.126 +
1.127 + guarantee(!regions_empty() || total_used_bytes() == 0,
1.128 + hrl_ext_msg(this, "invariant"));
1.129 +
1.130 + guarantee(total_used_bytes() <= total_capacity_bytes(),
1.131 + hrl_ext_msg(this, "invariant"));
1.132 +}
1.133 +
1.134 +void HeapRegionSetBase::verify_start() {
1.135 + // See comment in verify() about MT safety and verification.
1.136 + hrl_assert_mt_safety_ok(this);
1.137 + assert(!_verify_in_progress,
1.138 + hrl_ext_msg(this, "verification should not be in progress"));
1.139 +
1.140 + // Do the basic verification first before we do the checks over the regions.
1.141 + HeapRegionSetBase::verify();
1.142 +
1.143 + _calc_length = 0;
1.144 + _calc_region_num = 0;
1.145 + _calc_total_capacity_bytes = 0;
1.146 + _calc_total_used_bytes = 0;
1.147 + _verify_in_progress = true;
1.148 +}
1.149 +
1.150 +void HeapRegionSetBase::verify_next_region(HeapRegion* hr) {
1.151 + // See comment in verify() about MT safety and verification.
1.152 + hrl_assert_mt_safety_ok(this);
1.153 + assert(_verify_in_progress,
1.154 + hrl_ext_msg(this, "verification should be in progress"));
1.155 +
1.156 + guarantee(verify_region(hr, this), hrl_ext_msg(this, "region verification"));
1.157 +
1.158 + _calc_length += 1;
1.159 + if (!hr->isHumongous()) {
1.160 + _calc_region_num += 1;
1.161 + } else {
1.162 + _calc_region_num += calculate_region_num(hr);
1.163 + }
1.164 + _calc_total_capacity_bytes += hr->capacity();
1.165 + _calc_total_used_bytes += hr->used();
1.166 +}
1.167 +
1.168 +void HeapRegionSetBase::verify_end() {
1.169 + // See comment in verify() about MT safety and verification.
1.170 + hrl_assert_mt_safety_ok(this);
1.171 + assert(_verify_in_progress,
1.172 + hrl_ext_msg(this, "verification should be in progress"));
1.173 +
1.174 + guarantee(length() == _calc_length,
1.175 + hrl_err_msg("[%s] length: "SIZE_FORMAT" should be == "
1.176 + "calc length: "SIZE_FORMAT,
1.177 + name(), length(), _calc_length));
1.178 +
1.179 + guarantee(region_num() == _calc_region_num,
1.180 + hrl_err_msg("[%s] region num: "SIZE_FORMAT" should be == "
1.181 + "calc region num: "SIZE_FORMAT,
1.182 + name(), region_num(), _calc_region_num));
1.183 +
1.184 + guarantee(total_capacity_bytes() == _calc_total_capacity_bytes,
1.185 + hrl_err_msg("[%s] capacity bytes: "SIZE_FORMAT" should be == "
1.186 + "calc capacity bytes: "SIZE_FORMAT,
1.187 + name(),
1.188 + total_capacity_bytes(), _calc_total_capacity_bytes));
1.189 +
1.190 + guarantee(total_used_bytes() == _calc_total_used_bytes,
1.191 + hrl_err_msg("[%s] used bytes: "SIZE_FORMAT" should be == "
1.192 + "calc used bytes: "SIZE_FORMAT,
1.193 + name(), total_used_bytes(), _calc_total_used_bytes));
1.194 +
1.195 + _verify_in_progress = false;
1.196 +}
1.197 +
1.198 +void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
1.199 + out->cr();
1.200 + out->print_cr("Set: %s ("PTR_FORMAT")", name(), this);
1.201 + out->print_cr(" Region Assumptions");
1.202 + out->print_cr(" humongous : %s", BOOL_TO_STR(regions_humongous()));
1.203 + out->print_cr(" empty : %s", BOOL_TO_STR(regions_empty()));
1.204 + out->print_cr(" Attributes");
1.205 + out->print_cr(" length : "SIZE_FORMAT_W(14), length());
1.206 + out->print_cr(" region num : "SIZE_FORMAT_W(14), region_num());
1.207 + out->print_cr(" total capacity : "SIZE_FORMAT_W(14)" bytes",
1.208 + total_capacity_bytes());
1.209 + out->print_cr(" total used : "SIZE_FORMAT_W(14)" bytes",
1.210 + total_used_bytes());
1.211 +}
1.212 +
1.213 +void HeapRegionSetBase::clear() {
1.214 + _length = 0;
1.215 + _region_num = 0;
1.216 + _total_used_bytes = 0;
1.217 +}
1.218 +
1.219 +HeapRegionSetBase::HeapRegionSetBase(const char* name)
1.220 + : _name(name), _verify_in_progress(false),
1.221 + _calc_length(0), _calc_region_num(0),
1.222 + _calc_total_capacity_bytes(0), _calc_total_used_bytes(0) { }
1.223 +
1.224 +//////////////////// HeapRegionSet ////////////////////
1.225 +
1.226 +void HeapRegionSet::update_from_proxy(HeapRegionSet* proxy_set) {
1.227 + hrl_assert_mt_safety_ok(this);
1.228 + hrl_assert_mt_safety_ok(proxy_set);
1.229 + hrl_assert_sets_match(this, proxy_set);
1.230 +
1.231 + verify_optional();
1.232 + proxy_set->verify_optional();
1.233 +
1.234 + if (proxy_set->is_empty()) return;
1.235 +
1.236 + assert(proxy_set->length() <= _length,
1.237 + hrl_err_msg("[%s] proxy set length: "SIZE_FORMAT" "
1.238 + "should be <= length: "SIZE_FORMAT,
1.239 + name(), proxy_set->length(), _length));
1.240 + _length -= proxy_set->length();
1.241 +
1.242 + assert(proxy_set->region_num() <= _region_num,
1.243 + hrl_err_msg("[%s] proxy set region num: "SIZE_FORMAT" "
1.244 + "should be <= region num: "SIZE_FORMAT,
1.245 + name(), proxy_set->region_num(), _region_num));
1.246 + _region_num -= proxy_set->region_num();
1.247 +
1.248 + assert(proxy_set->total_used_bytes() <= _total_used_bytes,
1.249 + hrl_err_msg("[%s] proxy set used bytes: "SIZE_FORMAT" "
1.250 + "should be <= used bytes: "SIZE_FORMAT,
1.251 + name(), proxy_set->total_used_bytes(),
1.252 + _total_used_bytes));
1.253 + _total_used_bytes -= proxy_set->total_used_bytes();
1.254 +
1.255 + proxy_set->clear();
1.256 +
1.257 + verify_optional();
1.258 + proxy_set->verify_optional();
1.259 +}
1.260 +
1.261 +//////////////////// HeapRegionLinkedList ////////////////////
1.262 +
1.263 +void HeapRegionLinkedList::fill_in_ext_msg_extra(hrl_ext_msg* msg) {
1.264 + msg->append(" hd: "PTR_FORMAT" tl: "PTR_FORMAT, head(), tail());
1.265 +}
1.266 +
1.267 +void HeapRegionLinkedList::add_as_tail(HeapRegionLinkedList* from_list) {
1.268 + hrl_assert_mt_safety_ok(this);
1.269 + hrl_assert_mt_safety_ok(from_list);
1.270 +
1.271 + verify_optional();
1.272 + from_list->verify_optional();
1.273 +
1.274 + if (from_list->is_empty()) return;
1.275 +
1.276 +#ifdef ASSERT
1.277 + HeapRegionLinkedListIterator iter(from_list);
1.278 + while (iter.more_available()) {
1.279 + HeapRegion* hr = iter.get_next();
1.280 + // In set_containing_set() we check that we either set the value
1.281 + // from NULL to non-NULL or vice versa to catch bugs. So, we have
1.282 + // to NULL it first before setting it to the value.
1.283 + hr->set_containing_set(NULL);
1.284 + hr->set_containing_set(this);
1.285 + }
1.286 +#endif // ASSERT
1.287 +
1.288 + if (_tail != NULL) {
1.289 + assert(length() > 0 && _head != NULL, hrl_ext_msg(this, "invariant"));
1.290 + _tail->set_next(from_list->_head);
1.291 + } else {
1.292 + assert(length() == 0 && _head == NULL, hrl_ext_msg(this, "invariant"));
1.293 + _head = from_list->_head;
1.294 + }
1.295 + _tail = from_list->_tail;
1.296 +
1.297 + _length += from_list->length();
1.298 + _region_num += from_list->region_num();
1.299 + _total_used_bytes += from_list->total_used_bytes();
1.300 + from_list->clear();
1.301 +
1.302 + verify_optional();
1.303 + from_list->verify_optional();
1.304 +}
1.305 +
1.306 +void HeapRegionLinkedList::remove_all() {
1.307 + hrl_assert_mt_safety_ok(this);
1.308 + verify_optional();
1.309 +
1.310 + HeapRegion* curr = _head;
1.311 + while (curr != NULL) {
1.312 + hrl_assert_region_ok(this, curr, this);
1.313 +
1.314 + HeapRegion* next = curr->next();
1.315 + curr->set_next(NULL);
1.316 + curr->set_containing_set(NULL);
1.317 + curr = next;
1.318 + }
1.319 + clear();
1.320 +
1.321 + verify_optional();
1.322 +}
1.323 +
1.324 +void HeapRegionLinkedList::remove_all_pending(size_t target_count) {
1.325 + hrl_assert_mt_safety_ok(this);
1.326 + assert(target_count > 1, hrl_ext_msg(this, "pre-condition"));
1.327 + assert(!is_empty(), hrl_ext_msg(this, "pre-condition"));
1.328 +
1.329 + verify_optional();
1.330 + DEBUG_ONLY(size_t old_length = length();)
1.331 +
1.332 + HeapRegion* curr = _head;
1.333 + HeapRegion* prev = NULL;
1.334 + size_t count = 0;
1.335 + while (curr != NULL) {
1.336 + hrl_assert_region_ok(this, curr, this);
1.337 + HeapRegion* next = curr->next();
1.338 +
1.339 + if (curr->pending_removal()) {
1.340 + assert(count < target_count,
1.341 + hrl_err_msg("[%s] should not come across more regions "
1.342 + "pending for removal than target_count: "SIZE_FORMAT,
1.343 + name(), target_count));
1.344 +
1.345 + if (prev == NULL) {
1.346 + assert(_head == curr, hrl_ext_msg(this, "invariant"));
1.347 + _head = next;
1.348 + } else {
1.349 + assert(_head != curr, hrl_ext_msg(this, "invariant"));
1.350 + prev->set_next(next);
1.351 + }
1.352 + if (next == NULL) {
1.353 + assert(_tail == curr, hrl_ext_msg(this, "invariant"));
1.354 + _tail = prev;
1.355 + } else {
1.356 + assert(_tail != curr, hrl_ext_msg(this, "invariant"));
1.357 + }
1.358 +
1.359 + curr->set_next(NULL);
1.360 + remove_internal(curr);
1.361 + curr->set_pending_removal(false);
1.362 +
1.363 + count += 1;
1.364 +
1.365 + // If we have come across the target number of regions we can
1.366 + // just bail out. However, for debugging purposes, we can just
1.367 + // carry on iterating to make sure there are not more regions
1.368 + // tagged with pending removal.
1.369 + DEBUG_ONLY(if (count == target_count) break;)
1.370 + } else {
1.371 + prev = curr;
1.372 + }
1.373 + curr = next;
1.374 + }
1.375 +
1.376 + assert(count == target_count,
1.377 + hrl_err_msg("[%s] count: "SIZE_FORMAT" should be == "
1.378 + "target_count: "SIZE_FORMAT, name(), count, target_count));
1.379 + assert(length() + target_count == old_length,
1.380 + hrl_err_msg("[%s] new length should be consistent "
1.381 + "new length: "SIZE_FORMAT" old length: "SIZE_FORMAT" "
1.382 + "target_count: "SIZE_FORMAT,
1.383 + name(), length(), old_length, target_count));
1.384 +
1.385 + verify_optional();
1.386 +}
1.387 +
1.388 +void HeapRegionLinkedList::verify() {
1.389 + // See comment in HeapRegionSetBase::verify() about MT safety and
1.390 + // verification.
1.391 + hrl_assert_mt_safety_ok(this);
1.392 +
1.393 + // This will also do the basic verification too.
1.394 + verify_start();
1.395 +
1.396 + HeapRegion* curr = _head;
1.397 + HeapRegion* prev1 = NULL;
1.398 + HeapRegion* prev0 = NULL;
1.399 + size_t count = 0;
1.400 + while (curr != NULL) {
1.401 + verify_next_region(curr);
1.402 +
1.403 + count += 1;
1.404 + guarantee(count < _unrealistically_long_length,
1.405 + hrl_err_msg("[%s] the calculated length: "SIZE_FORMAT" "
1.406 + "seems very long, is there maybe a cycle? "
1.407 + "curr: "PTR_FORMAT" prev0: "PTR_FORMAT" "
1.408 + "prev1: "PTR_FORMAT" length: "SIZE_FORMAT,
1.409 + name(), count, curr, prev0, prev1, length()));
1.410 +
1.411 + prev1 = prev0;
1.412 + prev0 = curr;
1.413 + curr = curr->next();
1.414 + }
1.415 +
1.416 + guarantee(_tail == prev0, hrl_ext_msg(this, "post-condition"));
1.417 +
1.418 + verify_end();
1.419 +}
1.420 +
1.421 +void HeapRegionLinkedList::clear() {
1.422 + HeapRegionSetBase::clear();
1.423 + _head = NULL;
1.424 + _tail = NULL;
1.425 +}
1.426 +
1.427 +void HeapRegionLinkedList::print_on(outputStream* out, bool print_contents) {
1.428 + HeapRegionSetBase::print_on(out, print_contents);
1.429 + out->print_cr(" Linking");
1.430 + out->print_cr(" head : "PTR_FORMAT, _head);
1.431 + out->print_cr(" tail : "PTR_FORMAT, _tail);
1.432 +
1.433 + if (print_contents) {
1.434 + out->print_cr(" Contents");
1.435 + HeapRegionLinkedListIterator iter(this);
1.436 + while (iter.more_available()) {
1.437 + HeapRegion* hr = iter.get_next();
1.438 + hr->print_on(out);
1.439 + }
1.440 + }
1.441 +}
