1 /*

     2  * Copyright (c) 2011, 2016, 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 

    30 uint FreeRegionList::_unrealistically_long_length = 0;

    31 

    32 #ifndef PRODUCT

    33 void 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(hr->is_humongous() == regions_humongous(), "Wrong humongous state for region %u and set %s", hr->hrm_index(), name());

    37   assert(hr->is_free() == regions_free(), "Wrong free state for region %u and set %s", hr->hrm_index(), 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 

    44 void 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 

    56 void 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 

    67 void 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 

    75 void 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 Assumptions");

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

    80   out->print_cr("    free              : %s", BOOL_TO_STR(regions_free()));

    81   out->print_cr("  Attributes");

    82   out->print_cr("    length            : %14u", length());

    83 }

    84 

    85 HeapRegionSetBase::HeapRegionSetBase(const char* name, bool humongous, bool free, HRSMtSafeChecker* mt_safety_checker)

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

    87     _is_humongous(humongous), _is_free(free), _mt_safety_checker(mt_safety_checker),

    88     _length(0)

    89 { }

    90 

    91 void FreeRegionList::set_unrealistically_long_length(uint len) {

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

    93   _unrealistically_long_length = len;

    94 }

    95 

    96 void FreeRegionList::remove_all() {

    97   check_mt_safety();

    98   verify_optional();

    99 

   100   HeapRegion* curr = _head;

   101   while (curr != NULL) {

   102     verify_region(curr);

   103 

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

   105     curr->set_next(NULL);

   106     curr->set_prev(NULL);

   107     curr->set_containing_set(NULL);

   108     curr = next;

   109   }

   110   clear();

   111 

   112   verify_optional();

   113 }

   114 

   115 void FreeRegionList::add_ordered(FreeRegionList* from_list) {

   116   check_mt_safety();

   117   from_list->check_mt_safety();

   118 

   119   verify_optional();

   120   from_list->verify_optional();

   121 

   122   if (from_list->is_empty()) {

   123     return;

   124   }

   125 

   126   #ifdef ASSERT

   127   FreeRegionListIterator iter(from_list);

   128   while (iter.more_available()) {

   129     HeapRegion* hr = iter.get_next();

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

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

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

   133     hr->set_containing_set(NULL);

   134     hr->set_containing_set(this);

   135   }

   136   #endif // ASSERT

   137 

   138   if (is_empty()) {

   139     assert_free_region_list(length() == 0 && _tail == NULL, "invariant");

   140     _head = from_list->_head;

   141     _tail = from_list->_tail;

   142   } else {

   143     HeapRegion* curr_to = _head;

   144     HeapRegion* curr_from = from_list->_head;

   145 

   146     while (curr_from != NULL) {

   147       while (curr_to != NULL && curr_to->hrm_index() < curr_from->hrm_index()) {

   148         curr_to = curr_to->next();

   149       }

   150 

   151       if (curr_to == NULL) {

   152         // The rest of the from list should be added as tail

   153         _tail->set_next(curr_from);

   154         curr_from->set_prev(_tail);

   155         curr_from = NULL;

   156       } else {

   157         HeapRegion* next_from = curr_from->next();

   158 

   159         curr_from->set_next(curr_to);

   160         curr_from->set_prev(curr_to->prev());

   161         if (curr_to->prev() == NULL) {

   162           _head = curr_from;

   163         } else {

   164           curr_to->prev()->set_next(curr_from);

   165         }

   166         curr_to->set_prev(curr_from);

   167 

   168         curr_from = next_from;

   169       }

   170     }

   171 

   172     if (_tail->hrm_index() < from_list->_tail->hrm_index()) {

   173       _tail = from_list->_tail;

   174     }

   175   }

   176 

   177   _length += from_list->length();

   178   from_list->clear();

   179 

   180   verify_optional();

   181   from_list->verify_optional();

   182 }

   183 

   184 void FreeRegionList::remove_starting_at(HeapRegion* first, uint num_regions) {

   185   check_mt_safety();

   186   assert_free_region_list(num_regions >= 1, "pre-condition");

   187   assert_free_region_list(!is_empty(), "pre-condition");

   188 

   189   verify_optional();

   190   DEBUG_ONLY(uint old_length = length();)

   191 

   192   HeapRegion* curr = first;

   193   uint count = 0;

   194   while (count < num_regions) {

   195     verify_region(curr);

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

   197     HeapRegion* prev = curr->prev();

   198 

   199     assert(count < num_regions,

   200            "[%s] should not come across more regions "

   201            "pending for removal than num_regions: %u",

   202            name(), num_regions);

   203 

   204     if (prev == NULL) {

   205       assert_free_region_list(_head == curr, "invariant");

   206       _head = next;

   207     } else {

   208       assert_free_region_list(_head != curr, "invariant");

   209       prev->set_next(next);

   210     }

   211     if (next == NULL) {

   212       assert_free_region_list(_tail == curr, "invariant");

   213       _tail = prev;

   214     } else {

   215       assert_free_region_list(_tail != curr, "invariant");

   216       next->set_prev(prev);

   217     }

   218     if (_last == curr) {

   219       _last = NULL;

   220     }

   221 

   222     curr->set_next(NULL);

   223     curr->set_prev(NULL);

   224     remove(curr);

   225 

   226     count++;

   227     curr = next;

   228   }

   229 

   230   assert(count == num_regions,

   231          "[%s] count: %u should be == num_regions: %u",

   232          name(), count, num_regions);

   233   assert(length() + num_regions == old_length,

   234          "[%s] new length should be consistent "

   235          "new length: %u old length: %u num_regions: %u",

   236          name(), length(), old_length, num_regions);

   237 

   238   verify_optional();

   239 }

   240 

   241 void FreeRegionList::verify() {

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

   243   // verification.

   244   check_mt_safety();

   245 

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

   247   verify_start();

   248 

   249   verify_list();

   250 

   251   verify_end();

   252 }

   253 

   254 void FreeRegionList::clear() {

   255   _length = 0;

   256   _head = NULL;

   257   _tail = NULL;

   258   _last = NULL;

   259 }

   260 

   261 void FreeRegionList::verify_list() {

   262   HeapRegion* curr = _head;

   263   HeapRegion* prev1 = NULL;

   264   HeapRegion* prev0 = NULL;

   265   uint count = 0;

   266   size_t capacity = 0;

   267   uint last_index = 0;

   268 

   269   guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev");

   270   while (curr != NULL) {

   271     verify_region(curr);

   272 

   273     count++;

   274     guarantee(count < _unrealistically_long_length,

   275               "[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: " PTR_FORMAT " prev0: " PTR_FORMAT " " "prev1: " PTR_FORMAT " length: %u",

   276               name(), count, p2i(curr), p2i(prev0), p2i(prev1), length());

   277 

   278     if (curr->next() != NULL) {

   279       guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up");

   280     }

   281     guarantee(curr->hrm_index() == 0 || curr->hrm_index() > last_index, "List should be sorted");

   282     last_index = curr->hrm_index();

   283 

   284     capacity += curr->capacity();

   285 

   286     prev1 = prev0;

   287     prev0 = curr;

   288     curr = curr->next();

   289   }

   290 

   291   guarantee(_tail == prev0, "Expected %s to end with %u but it ended with %u.", name(), _tail->hrm_index(), prev0->hrm_index());

   292   guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next");

   293   guarantee(length() == count, "%s count mismatch. Expected %u, actual %u.", name(), length(), count);

   294 }

   295 

   296 // Note on the check_mt_safety() methods below:

   297 //

   298 // Verification of the "master" heap region sets / lists that are

   299 // maintained by G1CollectedHeap is always done during a STW pause and

   300 // by the VM thread at the start / end of the pause. The standard

   301 // verification methods all assert check_mt_safety(). This is

   302 // important as it ensures that verification is done without

   303 // concurrent updates taking place at the same time. It follows, that,

   304 // for the "master" heap region sets / lists, the check_mt_safety()

   305 // method should include the VM thread / STW case.

   306 

   307 void MasterFreeRegionListMtSafeChecker::check() {

   308   // Master Free List MT safety protocol:

   309   // (a) If we're at a safepoint, operations on the master free list

   310   // should be invoked by either the VM thread (which will serialize

   311   // them) or by the GC workers while holding the

   312   // FreeList_lock.

   313   // (b) If we're not at a safepoint, operations on the master free

   314   // list should be invoked while holding the Heap_lock.

   315 

   316   if (SafepointSynchronize::is_at_safepoint()) {

   317     guarantee(Thread::current()->is_VM_thread() ||

   318               FreeList_lock->owned_by_self(), "master free list MT safety protocol at a safepoint");

   319   } else {

   320     guarantee(Heap_lock->owned_by_self(), "master free list MT safety protocol outside a safepoint");

   321   }

   322 }

   323 

   324 void SecondaryFreeRegionListMtSafeChecker::check() {

   325   // Secondary Free List MT safety protocol:

   326   // Operations on the secondary free list should always be invoked

   327   // while holding the SecondaryFreeList_lock.

   328 

   329   guarantee(SecondaryFreeList_lock->owned_by_self(), "secondary free list MT safety protocol");

   330 }

   331 

   332 void OldRegionSetMtSafeChecker::check() {

   333   // Master Old Set MT safety protocol:

   334   // (a) If we're at a safepoint, operations on the master old set

   335   // should be invoked:

   336   // - by the VM thread (which will serialize them), or

   337   // - by the GC workers while holding the FreeList_lock, if we're

   338   //   at a safepoint for an evacuation pause (this lock is taken

   339   //   anyway when an GC alloc region is retired so that a new one

   340   //   is allocated from the free list), or

   341   // - by the GC workers while holding the OldSets_lock, if we're at a

   342   //   safepoint for a cleanup pause.

   343   // (b) If we're not at a safepoint, operations on the master old set

   344   // should be invoked while holding the Heap_lock.

   345 

   346   if (SafepointSynchronize::is_at_safepoint()) {

   347     guarantee(Thread::current()->is_VM_thread()

   348         || FreeList_lock->owned_by_self() || OldSets_lock->owned_by_self(),

   349         "master old set MT safety protocol at a safepoint");

   350   } else {

   351     guarantee(Heap_lock->owned_by_self(), "master old set MT safety protocol outside a safepoint");

   352   }

   353 }

   354 

   355 void HumongousRegionSetMtSafeChecker::check() {

   356   // Humongous Set MT safety protocol:

   357   // (a) If we're at a safepoint, operations on the master humongous

   358   // set should be invoked by either the VM thread (which will

   359   // serialize them) or by the GC workers while holding the

   360   // OldSets_lock.

   361   // (b) If we're not at a safepoint, operations on the master

   362   // humongous set should be invoked while holding the Heap_lock.

   363 

   364   if (SafepointSynchronize::is_at_safepoint()) {

   365     guarantee(Thread::current()->is_VM_thread() ||

   366               OldSets_lock->owned_by_self(),

   367               "master humongous set MT safety protocol at a safepoint");

   368   } else {

   369     guarantee(Heap_lock->owned_by_self(),

   370               "master humongous set MT safety protocol outside a safepoint");

   371   }

   372 }