1 /*

     2  * Copyright (c) 2011, 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 size_t HeapRegionSetBase::_unrealistically_long_length = 0;

    29 

    30 //////////////////// HeapRegionSetBase ////////////////////

    31 

    32 void HeapRegionSetBase::set_unrealistically_long_length(size_t len) {

    33   guarantee(_unrealistically_long_length == 0, "should only be set once");

    34   _unrealistically_long_length = len;

    35 }

    36 

    37 size_t HeapRegionSetBase::calculate_region_num(HeapRegion* hr) {

    38   assert(hr->startsHumongous(), "pre-condition");

    39   assert(hr->capacity() % HeapRegion::GrainBytes == 0, "invariant");

    40   size_t region_num = hr->capacity() >> HeapRegion::LogOfHRGrainBytes;

    41   assert(region_num > 0, "sanity");

    42   return region_num;

    43 }

    44 

    45 void HeapRegionSetBase::fill_in_ext_msg(hrl_ext_msg* msg, const char* message) {

    46   msg->append("[%s] %s "

    47               "ln: "SIZE_FORMAT" rn: "SIZE_FORMAT" "

    48               "cy: "SIZE_FORMAT" ud: "SIZE_FORMAT,

    49               name(), message, length(), region_num(),

    50               total_capacity_bytes(), total_used_bytes());

    51   fill_in_ext_msg_extra(msg);

    52 }

    53 

    54 bool HeapRegionSetBase::verify_region(HeapRegion* hr,

    55                                   HeapRegionSetBase* expected_containing_set) {

    56   const char* error_message = NULL;

    57 

    58   if (!regions_humongous()) {

    59     if (hr->isHumongous()) {

    60       error_message = "the region should not be humongous";

    61     }

    62   } else {

    63     if (!hr->isHumongous() || !hr->startsHumongous()) {

    64       error_message = "the region should be 'starts humongous'";

    65     }

    66   }

    67 

    68   if (!regions_empty()) {

    69     if (hr->is_empty()) {

    70       error_message = "the region should not be empty";

    71     }

    72   } else {

    73     if (!hr->is_empty()) {

    74       error_message = "the region should be empty";

    75     }

    76   }

    77 

    78 #ifdef ASSERT

    79   // The _containing_set field is only available when ASSERT is defined.

    80   if (hr->containing_set() != expected_containing_set) {

    81     error_message = "inconsistent containing set found";

    82   }

    83 #endif // ASSERT

    84 

    85   const char* extra_error_message = verify_region_extra(hr);

    86   if (extra_error_message != NULL) {

    87     error_message = extra_error_message;

    88   }

    89 

    90   if (error_message != NULL) {

    91     outputStream* out = tty;

    92     out->cr();

    93     out->print_cr("## [%s] %s", name(), error_message);

    94     out->print_cr("## Offending Region: "PTR_FORMAT, hr);

    95     out->print_cr("   "HR_FORMAT, HR_FORMAT_PARAMS(hr));

    96 #ifdef ASSERT

    97     out->print_cr("   containing set: "PTR_FORMAT, hr->containing_set());

    98 #endif // ASSERT

    99     out->print_cr("## Offending Region Set: "PTR_FORMAT, this);

   100     print_on(out);

   101     return false;

   102   } else {

   103     return true;

   104   }

   105 }

   106 

   107 void HeapRegionSetBase::verify() {

   108   // It's important that we also observe the MT safety protocol even

   109   // for the verification calls. If we do verification without the

   110   // appropriate locks and the set changes underneath our feet

   111   // verification might fail and send us on a wild goose chase.

   112   hrl_assert_mt_safety_ok(this);

   113 

   114   guarantee(( is_empty() && length() == 0 && region_num() == 0 &&

   115               total_used_bytes() == 0 && total_capacity_bytes() == 0) ||

   116             (!is_empty() && length() >= 0 && region_num() >= 0 &&

   117               total_used_bytes() >= 0 && total_capacity_bytes() >= 0),

   118             hrl_ext_msg(this, "invariant"));

   119 

   120   guarantee((!regions_humongous() && region_num() == length()) ||

   121             ( regions_humongous() && region_num() >= length()),

   122             hrl_ext_msg(this, "invariant"));

   123 

   124   guarantee(!regions_empty() || total_used_bytes() == 0,

   125             hrl_ext_msg(this, "invariant"));

   126 

   127   guarantee(total_used_bytes() <= total_capacity_bytes(),

   128             hrl_ext_msg(this, "invariant"));

   129 }

   130 

   131 void HeapRegionSetBase::verify_start() {

   132   // See comment in verify() about MT safety and verification.

   133   hrl_assert_mt_safety_ok(this);

   134   assert(!_verify_in_progress,

   135          hrl_ext_msg(this, "verification should not be in progress"));

   136 

   137   // Do the basic verification first before we do the checks over the regions.

   138   HeapRegionSetBase::verify();

   139 

   140   _calc_length               = 0;

   141   _calc_region_num           = 0;

   142   _calc_total_capacity_bytes = 0;

   143   _calc_total_used_bytes     = 0;

   144   _verify_in_progress        = true;

   145 }

   146 

   147 void HeapRegionSetBase::verify_next_region(HeapRegion* hr) {

   148   // See comment in verify() about MT safety and verification.

   149   hrl_assert_mt_safety_ok(this);

   150   assert(_verify_in_progress,

   151          hrl_ext_msg(this, "verification should be in progress"));

   152 

   153   guarantee(verify_region(hr, this), hrl_ext_msg(this, "region verification"));

   154 

   155   _calc_length               += 1;

   156   if (!hr->isHumongous()) {

   157     _calc_region_num         += 1;

   158   } else {

   159     _calc_region_num         += calculate_region_num(hr);

   160   }

   161   _calc_total_capacity_bytes += hr->capacity();

   162   _calc_total_used_bytes     += hr->used();

   163 }

   164 

   165 void HeapRegionSetBase::verify_end() {

   166   // See comment in verify() about MT safety and verification.

   167   hrl_assert_mt_safety_ok(this);

   168   assert(_verify_in_progress,

   169          hrl_ext_msg(this, "verification should be in progress"));

   170 

   171   guarantee(length() == _calc_length,

   172             hrl_err_msg("[%s] length: "SIZE_FORMAT" should be == "

   173                         "calc length: "SIZE_FORMAT,

   174                         name(), length(), _calc_length));

   175 

   176   guarantee(region_num() == _calc_region_num,

   177             hrl_err_msg("[%s] region num: "SIZE_FORMAT" should be == "

   178                         "calc region num: "SIZE_FORMAT,

   179                         name(), region_num(), _calc_region_num));

   180 

   181   guarantee(total_capacity_bytes() == _calc_total_capacity_bytes,

   182             hrl_err_msg("[%s] capacity bytes: "SIZE_FORMAT" should be == "

   183                         "calc capacity bytes: "SIZE_FORMAT,

   184                         name(),

   185                         total_capacity_bytes(), _calc_total_capacity_bytes));

   186 

   187   guarantee(total_used_bytes() == _calc_total_used_bytes,

   188             hrl_err_msg("[%s] used bytes: "SIZE_FORMAT" should be == "

   189                         "calc used bytes: "SIZE_FORMAT,

   190                         name(), total_used_bytes(), _calc_total_used_bytes));

   191 

   192   _verify_in_progress = false;

   193 }

   194 

   195 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {

   196   out->cr();

   197   out->print_cr("Set: %s ("PTR_FORMAT")", name(), this);

   198   out->print_cr("  Region Assumptions");

   199   out->print_cr("    humongous         : %s", BOOL_TO_STR(regions_humongous()));

   200   out->print_cr("    empty             : %s", BOOL_TO_STR(regions_empty()));

   201   out->print_cr("  Attributes");

   202   out->print_cr("    length            : "SIZE_FORMAT_W(14), length());

   203   out->print_cr("    region num        : "SIZE_FORMAT_W(14), region_num());

   204   out->print_cr("    total capacity    : "SIZE_FORMAT_W(14)" bytes",

   205                 total_capacity_bytes());

   206   out->print_cr("    total used        : "SIZE_FORMAT_W(14)" bytes",

   207                 total_used_bytes());

   208 }

   209 

   210 void HeapRegionSetBase::clear() {

   211   _length           = 0;

   212   _region_num       = 0;

   213   _total_used_bytes = 0;

   214 }

   215 

   216 HeapRegionSetBase::HeapRegionSetBase(const char* name)

   217   : _name(name), _verify_in_progress(false),

   218     _calc_length(0), _calc_region_num(0),

   219     _calc_total_capacity_bytes(0), _calc_total_used_bytes(0) { }

   220 

   221 //////////////////// HeapRegionSet ////////////////////

   222 

   223 void HeapRegionSet::update_from_proxy(HeapRegionSet* proxy_set) {

   224   hrl_assert_mt_safety_ok(this);

   225   hrl_assert_mt_safety_ok(proxy_set);

   226   hrl_assert_sets_match(this, proxy_set);

   227 

   228   verify_optional();

   229   proxy_set->verify_optional();

   230 

   231   if (proxy_set->is_empty()) return;

   232 

   233   assert(proxy_set->length() <= _length,

   234          hrl_err_msg("[%s] proxy set length: "SIZE_FORMAT" "

   235                      "should be <= length: "SIZE_FORMAT,

   236                      name(), proxy_set->length(), _length));

   237   _length -= proxy_set->length();

   238 

   239   assert(proxy_set->region_num() <= _region_num,

   240          hrl_err_msg("[%s] proxy set region num: "SIZE_FORMAT" "

   241                      "should be <= region num: "SIZE_FORMAT,

   242                      name(), proxy_set->region_num(), _region_num));

   243   _region_num -= proxy_set->region_num();

   244 

   245   assert(proxy_set->total_used_bytes() <= _total_used_bytes,

   246          hrl_err_msg("[%s] proxy set used bytes: "SIZE_FORMAT" "

   247                      "should be <= used bytes: "SIZE_FORMAT,

   248                      name(), proxy_set->total_used_bytes(),

   249                      _total_used_bytes));

   250   _total_used_bytes -= proxy_set->total_used_bytes();

   251 

   252   proxy_set->clear();

   253 

   254   verify_optional();

   255   proxy_set->verify_optional();

   256 }

   257 

   258 //////////////////// HeapRegionLinkedList ////////////////////

   259 

   260 void HeapRegionLinkedList::fill_in_ext_msg_extra(hrl_ext_msg* msg) {

   261   msg->append(" hd: "PTR_FORMAT" tl: "PTR_FORMAT, head(), tail());

   262 }

   263 

   264 void HeapRegionLinkedList::add_as_tail(HeapRegionLinkedList* from_list) {

   265   hrl_assert_mt_safety_ok(this);

   266   hrl_assert_mt_safety_ok(from_list);

   267 

   268   verify_optional();

   269   from_list->verify_optional();

   270 

   271   if (from_list->is_empty()) return;

   272 

   273 #ifdef ASSERT

   274   HeapRegionLinkedListIterator iter(from_list);

   275   while (iter.more_available()) {

   276     HeapRegion* hr = iter.get_next();

   277     // In set_containing_set() we check that we either set the value

   278     // from NULL to non-NULL or vice versa to catch bugs. So, we have

   279     // to NULL it first before setting it to the value.

   280     hr->set_containing_set(NULL);

   281     hr->set_containing_set(this);

   282   }

   283 #endif // ASSERT

   284 

   285   if (_tail != NULL) {

   286     assert(length() >  0 && _head != NULL, hrl_ext_msg(this, "invariant"));

   287     _tail->set_next(from_list->_head);

   288   } else {

   289     assert(length() == 0 && _head == NULL, hrl_ext_msg(this, "invariant"));

   290     _head = from_list->_head;

   291   }

   292   _tail = from_list->_tail;

   293 

   294   _length           += from_list->length();

   295   _region_num       += from_list->region_num();

   296   _total_used_bytes += from_list->total_used_bytes();

   297   from_list->clear();

   298 

   299   verify_optional();

   300   from_list->verify_optional();

   301 }

   302 

   303 void HeapRegionLinkedList::remove_all() {

   304   hrl_assert_mt_safety_ok(this);

   305   verify_optional();

   306 

   307   HeapRegion* curr = _head;

   308   while (curr != NULL) {

   309     hrl_assert_region_ok(this, curr, this);

   310 

   311     HeapRegion* next = curr->next();

   312     curr->set_next(NULL);

   313     curr->set_containing_set(NULL);

   314     curr = next;

   315   }

   316   clear();

   317 

   318   verify_optional();

   319 }

   320 

   321 void HeapRegionLinkedList::remove_all_pending(size_t target_count) {

   322   hrl_assert_mt_safety_ok(this);

   323   assert(target_count > 1, hrl_ext_msg(this, "pre-condition"));

   324   assert(!is_empty(), hrl_ext_msg(this, "pre-condition"));

   325 

   326   verify_optional();

   327   DEBUG_ONLY(size_t old_length = length();)

   328 

   329   HeapRegion* curr = _head;

   330   HeapRegion* prev = NULL;

   331   size_t count = 0;

   332   while (curr != NULL) {

   333     hrl_assert_region_ok(this, curr, this);

   334     HeapRegion* next = curr->next();

   335 

   336     if (curr->pending_removal()) {

   337       assert(count < target_count,

   338              hrl_err_msg("[%s] should not come across more regions "

   339                          "pending for removal than target_count: "SIZE_FORMAT,

   340                          name(), target_count));

   341 

   342       if (prev == NULL) {

   343         assert(_head == curr, hrl_ext_msg(this, "invariant"));

   344         _head = next;

   345       } else {

   346         assert(_head != curr, hrl_ext_msg(this, "invariant"));

   347         prev->set_next(next);

   348       }

   349       if (next == NULL) {

   350         assert(_tail == curr, hrl_ext_msg(this, "invariant"));

   351         _tail = prev;

   352       } else {

   353         assert(_tail != curr, hrl_ext_msg(this, "invariant"));

   354       }

   355 

   356       curr->set_next(NULL);

   357       remove_internal(curr);

   358       curr->set_pending_removal(false);

   359 

   360       count += 1;

   361 

   362       // If we have come across the target number of regions we can

   363       // just bail out. However, for debugging purposes, we can just

   364       // carry on iterating to make sure there are not more regions

   365       // tagged with pending removal.

   366       DEBUG_ONLY(if (count == target_count) break;)

   367     } else {

   368       prev = curr;

   369     }

   370     curr = next;

   371   }

   372 

   373   assert(count == target_count,

   374          hrl_err_msg("[%s] count: "SIZE_FORMAT" should be == "

   375                      "target_count: "SIZE_FORMAT, name(), count, target_count));

   376   assert(length() + target_count == old_length,

   377          hrl_err_msg("[%s] new length should be consistent "

   378                      "new length: "SIZE_FORMAT" old length: "SIZE_FORMAT" "

   379                      "target_count: "SIZE_FORMAT,

   380                      name(), length(), old_length, target_count));

   381 

   382   verify_optional();

   383 }

   384 

   385 void HeapRegionLinkedList::verify() {

   386   // See comment in HeapRegionSetBase::verify() about MT safety and

   387   // verification.

   388   hrl_assert_mt_safety_ok(this);

   389 

   390   // This will also do the basic verification too.

   391   verify_start();

   392 

   393   HeapRegion* curr  = _head;

   394   HeapRegion* prev1 = NULL;

   395   HeapRegion* prev0 = NULL;

   396   size_t      count = 0;

   397   while (curr != NULL) {

   398     verify_next_region(curr);

   399 

   400     count += 1;

   401     guarantee(count < _unrealistically_long_length,

   402               hrl_err_msg("[%s] the calculated length: "SIZE_FORMAT" "

   403                           "seems very long, is there maybe a cycle? "

   404                           "curr: "PTR_FORMAT" prev0: "PTR_FORMAT" "

   405                           "prev1: "PTR_FORMAT" length: "SIZE_FORMAT,

   406                           name(), count, curr, prev0, prev1, length()));

   407 

   408     prev1 = prev0;

   409     prev0 = curr;

   410     curr  = curr->next();

   411   }

   412 

   413   guarantee(_tail == prev0, hrl_ext_msg(this, "post-condition"));

   414 

   415   verify_end();

   416 }

   417 

   418 void HeapRegionLinkedList::clear() {

   419   HeapRegionSetBase::clear();

   420   _head = NULL;

   421   _tail = NULL;

   422 }

   423 

   424 void HeapRegionLinkedList::print_on(outputStream* out, bool print_contents) {

   425   HeapRegionSetBase::print_on(out, print_contents);

   426   out->print_cr("  Linking");

   427   out->print_cr("    head              : "PTR_FORMAT, _head);

   428   out->print_cr("    tail              : "PTR_FORMAT, _tail);

   429 

   430   if (print_contents) {

   431     out->print_cr("  Contents");

   432     HeapRegionLinkedListIterator iter(this);

   433     while (iter.more_available()) {

   434       HeapRegion* hr = iter.get_next();

   435       hr->print_on(out);

   436     }

   437   }

   438 }