--- a/src/share/vm/gc_implementation/g1/heapRegionSet.cpp	Thu Mar 06 11:11:04 2014 +0100
+++ b/src/share/vm/gc_implementation/g1/heapRegionSet.cpp	Fri Mar 14 10:15:46 2014 +0100
@@ -23,171 +23,60 @@
  */
 
 #include "precompiled.hpp"
+#include "gc_implementation/g1/heapRegionRemSet.hpp"
 #include "gc_implementation/g1/heapRegionSet.inline.hpp"
 
-uint HeapRegionSetBase::_unrealistically_long_length = 0;
-HRSPhase HeapRegionSetBase::_phase = HRSPhaseNone;
-
-//////////////////// HeapRegionSetBase ////////////////////
-
-void HeapRegionSetBase::set_unrealistically_long_length(uint len) {
-  guarantee(_unrealistically_long_length == 0, "should only be set once");
-  _unrealistically_long_length = len;
-}
+uint FreeRegionList::_unrealistically_long_length = 0;
 
 void HeapRegionSetBase::fill_in_ext_msg(hrs_ext_msg* msg, const char* message) {
-  msg->append("[%s] %s ln: %u rn: %u cy: "SIZE_FORMAT" ud: "SIZE_FORMAT,
-              name(), message, length(), region_num(),
-              total_capacity_bytes(), total_used_bytes());
+  msg->append("[%s] %s ln: %u cy: "SIZE_FORMAT,
+              name(), message, length(), total_capacity_bytes());
   fill_in_ext_msg_extra(msg);
 }
 
-bool HeapRegionSetBase::verify_region(HeapRegion* hr,
-                                  HeapRegionSetBase* expected_containing_set) {
-  const char* error_message = NULL;
-
-  if (!regions_humongous()) {
-    if (hr->isHumongous()) {
-      error_message = "the region should not be humongous";
-    }
-  } else {
-    if (!hr->isHumongous() || !hr->startsHumongous()) {
-      error_message = "the region should be 'starts humongous'";
-    }
-  }
-
-  if (!regions_empty()) {
-    if (hr->is_empty()) {
-      error_message = "the region should not be empty";
-    }
-  } else {
-    if (!hr->is_empty()) {
-      error_message = "the region should be empty";
-    }
-  }
-
-#ifdef ASSERT
-  // The _containing_set field is only available when ASSERT is defined.
-  if (hr->containing_set() != expected_containing_set) {
-    error_message = "inconsistent containing set found";
-  }
-#endif // ASSERT
-
-  const char* extra_error_message = verify_region_extra(hr);
-  if (extra_error_message != NULL) {
-    error_message = extra_error_message;
-  }
-
-  if (error_message != NULL) {
-    outputStream* out = tty;
-    out->cr();
-    out->print_cr("## [%s] %s", name(), error_message);
-    out->print_cr("## Offending Region: "PTR_FORMAT, hr);
-    out->print_cr("   "HR_FORMAT, HR_FORMAT_PARAMS(hr));
-#ifdef ASSERT
-    out->print_cr("   containing set: "PTR_FORMAT, hr->containing_set());
-#endif // ASSERT
-    out->print_cr("## Offending Region Set: "PTR_FORMAT, this);
-    print_on(out);
-    return false;
-  } else {
-    return true;
-  }
+#ifndef PRODUCT
+void HeapRegionSetBase::verify_region(HeapRegion* hr) {
+  assert(hr->containing_set() == this, err_msg("Inconsistent containing set for %u", hr->hrs_index()));
+  assert(!hr->is_young(), err_msg("Adding young region %u", hr->hrs_index())); // currently we don't use these sets for young regions
+  assert(hr->isHumongous() == regions_humongous(), err_msg("Wrong humongous state for region %u and set %s", hr->hrs_index(), name()));
+  assert(hr->is_empty() == regions_empty(), err_msg("Wrong empty state for region %u and set %s", hr->hrs_index(), name()));
+  assert(hr->rem_set()->verify_ready_for_par_iteration(), err_msg("Wrong iteration state %u", hr->hrs_index()));
 }
+#endif
 
 void HeapRegionSetBase::verify() {
   // It's important that we also observe the MT safety protocol even
   // for the verification calls. If we do verification without the
   // appropriate locks and the set changes underneath our feet
   // verification might fail and send us on a wild goose chase.
-  hrs_assert_mt_safety_ok(this);
-
-  guarantee(( is_empty() && length() == 0 && region_num() == 0 &&
-              total_used_bytes() == 0 && total_capacity_bytes() == 0) ||
-            (!is_empty() && length() >= 0 && region_num() >= 0 &&
-              total_used_bytes() >= 0 && total_capacity_bytes() >= 0),
-            hrs_ext_msg(this, "invariant"));
+  check_mt_safety();
 
-  guarantee((!regions_humongous() && region_num() == length()) ||
-            ( regions_humongous() && region_num() >= length()),
-            hrs_ext_msg(this, "invariant"));
-
-  guarantee(!regions_empty() || total_used_bytes() == 0,
-            hrs_ext_msg(this, "invariant"));
-
-  guarantee(total_used_bytes() <= total_capacity_bytes(),
+  guarantee(( is_empty() && length() == 0 && total_capacity_bytes() == 0) ||
+            (!is_empty() && length() >= 0 && total_capacity_bytes() >= 0),
             hrs_ext_msg(this, "invariant"));
 }
 
 void HeapRegionSetBase::verify_start() {
   // See comment in verify() about MT safety and verification.
-  hrs_assert_mt_safety_ok(this);
+  check_mt_safety();
   assert(!_verify_in_progress,
          hrs_ext_msg(this, "verification should not be in progress"));
 
   // Do the basic verification first before we do the checks over the regions.
   HeapRegionSetBase::verify();
 
-  _calc_length               = 0;
-  _calc_region_num           = 0;
-  _calc_total_capacity_bytes = 0;
-  _calc_total_used_bytes     = 0;
   _verify_in_progress        = true;
 }
 
-void HeapRegionSetBase::verify_next_region(HeapRegion* hr) {
-  // See comment in verify() about MT safety and verification.
-  hrs_assert_mt_safety_ok(this);
-  assert(_verify_in_progress,
-         hrs_ext_msg(this, "verification should be in progress"));
-
-  guarantee(verify_region(hr, this), hrs_ext_msg(this, "region verification"));
-
-  _calc_length               += 1;
-  _calc_region_num           += hr->region_num();
-  _calc_total_capacity_bytes += hr->capacity();
-  _calc_total_used_bytes     += hr->used();
-}
-
 void HeapRegionSetBase::verify_end() {
   // See comment in verify() about MT safety and verification.
-  hrs_assert_mt_safety_ok(this);
+  check_mt_safety();
   assert(_verify_in_progress,
          hrs_ext_msg(this, "verification should be in progress"));
 
-  guarantee(length() == _calc_length,
-            hrs_err_msg("[%s] length: %u should be == calc length: %u",
-                        name(), length(), _calc_length));
-
-  guarantee(region_num() == _calc_region_num,
-            hrs_err_msg("[%s] region num: %u should be == calc region num: %u",
-                        name(), region_num(), _calc_region_num));
-
-  guarantee(total_capacity_bytes() == _calc_total_capacity_bytes,
-            hrs_err_msg("[%s] capacity bytes: "SIZE_FORMAT" should be == "
-                        "calc capacity bytes: "SIZE_FORMAT,
-                        name(),
-                        total_capacity_bytes(), _calc_total_capacity_bytes));
-
-  guarantee(total_used_bytes() == _calc_total_used_bytes,
-            hrs_err_msg("[%s] used bytes: "SIZE_FORMAT" should be == "
-                        "calc used bytes: "SIZE_FORMAT,
-                        name(), total_used_bytes(), _calc_total_used_bytes));
-
   _verify_in_progress = false;
 }
 
-void HeapRegionSetBase::clear_phase() {
-  assert(_phase != HRSPhaseNone, "pre-condition");
-  _phase = HRSPhaseNone;
-}
-
-void HeapRegionSetBase::set_phase(HRSPhase phase) {
-  assert(_phase == HRSPhaseNone, "pre-condition");
-  assert(phase != HRSPhaseNone, "pre-condition");
-  _phase = phase;
-}
-
 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) {
   out->cr();
   out->print_cr("Set: %s ("PTR_FORMAT")", name(), this);
@@ -196,76 +85,38 @@
   out->print_cr("    empty             : %s", BOOL_TO_STR(regions_empty()));
   out->print_cr("  Attributes");
   out->print_cr("    length            : %14u", length());
-  out->print_cr("    region num        : %14u", region_num());
   out->print_cr("    total capacity    : "SIZE_FORMAT_W(14)" bytes",
                 total_capacity_bytes());
-  out->print_cr("    total used        : "SIZE_FORMAT_W(14)" bytes",
-                total_used_bytes());
-}
-
-void HeapRegionSetBase::clear() {
-  _length           = 0;
-  _region_num       = 0;
-  _total_used_bytes = 0;
 }
 
-HeapRegionSetBase::HeapRegionSetBase(const char* name)
+HeapRegionSetBase::HeapRegionSetBase(const char* name, bool humongous, bool empty, HRSMtSafeChecker* mt_safety_checker)
   : _name(name), _verify_in_progress(false),
-    _calc_length(0), _calc_region_num(0),
-    _calc_total_capacity_bytes(0), _calc_total_used_bytes(0) { }
-
-//////////////////// HeapRegionSet ////////////////////
-
-void HeapRegionSet::update_from_proxy(HeapRegionSet* proxy_set) {
-  hrs_assert_mt_safety_ok(this);
-  hrs_assert_mt_safety_ok(proxy_set);
-  hrs_assert_sets_match(this, proxy_set);
-
-  verify_optional();
-  proxy_set->verify_optional();
-
-  if (proxy_set->is_empty()) return;
+    _is_humongous(humongous), _is_empty(empty), _mt_safety_checker(mt_safety_checker),
+    _count()
+{ }
 
-  assert(proxy_set->length() <= _length,
-         hrs_err_msg("[%s] proxy set length: %u should be <= length: %u",
-                     name(), proxy_set->length(), _length));
-  _length -= proxy_set->length();
-
-  assert(proxy_set->region_num() <= _region_num,
-         hrs_err_msg("[%s] proxy set region num: %u should be <= region num: %u",
-                     name(), proxy_set->region_num(), _region_num));
-  _region_num -= proxy_set->region_num();
-
-  assert(proxy_set->total_used_bytes() <= _total_used_bytes,
-         hrs_err_msg("[%s] proxy set used bytes: "SIZE_FORMAT" "
-                     "should be <= used bytes: "SIZE_FORMAT,
-                     name(), proxy_set->total_used_bytes(),
-                     _total_used_bytes));
-  _total_used_bytes -= proxy_set->total_used_bytes();
-
-  proxy_set->clear();
-
-  verify_optional();
-  proxy_set->verify_optional();
+void FreeRegionList::set_unrealistically_long_length(uint len) {
+  guarantee(_unrealistically_long_length == 0, "should only be set once");
+  _unrealistically_long_length = len;
 }
 
-//////////////////// HeapRegionLinkedList ////////////////////
-
-void HeapRegionLinkedList::fill_in_ext_msg_extra(hrs_ext_msg* msg) {
+void FreeRegionList::fill_in_ext_msg_extra(hrs_ext_msg* msg) {
   msg->append(" hd: "PTR_FORMAT" tl: "PTR_FORMAT, head(), tail());
 }
 
-void HeapRegionLinkedList::add_as_head(HeapRegionLinkedList* from_list) {
-  hrs_assert_mt_safety_ok(this);
-  hrs_assert_mt_safety_ok(from_list);
+void FreeRegionList::add_as_head_or_tail(FreeRegionList* from_list, bool as_head) {
+  check_mt_safety();
+  from_list->check_mt_safety();
 
   verify_optional();
   from_list->verify_optional();
 
-  if (from_list->is_empty()) return;
+  if (from_list->is_empty()) {
+    return;
+  }
 
 #ifdef ASSERT
-  HeapRegionLinkedListIterator iter(from_list);
+  FreeRegionListIterator iter(from_list);
   while (iter.more_available()) {
     HeapRegion* hr = iter.get_next();
     // In set_containing_set() we check that we either set the value
@@ -276,70 +127,43 @@
   }
 #endif // ASSERT
 
-  if (_head != NULL) {
-    assert(length() >  0 && _tail != NULL, hrs_ext_msg(this, "invariant"));
-    from_list->_tail->set_next(_head);
-  } else {
+  if (_head == NULL) {
     assert(length() == 0 && _tail == NULL, hrs_ext_msg(this, "invariant"));
+    _head = from_list->_head;
     _tail = from_list->_tail;
+  } else {
+    assert(length() > 0 && _tail != NULL, hrs_ext_msg(this, "invariant"));
+    if (as_head) {
+      from_list->_tail->set_next(_head);
+      _head = from_list->_head;
+    } else {
+      _tail->set_next(from_list->_head);
+      _tail = from_list->_tail;
+    }
   }
-  _head = from_list->_head;
 
-  _length           += from_list->length();
-  _region_num       += from_list->region_num();
-  _total_used_bytes += from_list->total_used_bytes();
+  _count.increment(from_list->length(), from_list->total_capacity_bytes());
   from_list->clear();
 
   verify_optional();
   from_list->verify_optional();
 }
 
-void HeapRegionLinkedList::add_as_tail(HeapRegionLinkedList* from_list) {
-  hrs_assert_mt_safety_ok(this);
-  hrs_assert_mt_safety_ok(from_list);
-
-  verify_optional();
-  from_list->verify_optional();
-
-  if (from_list->is_empty()) return;
-
-#ifdef ASSERT
-  HeapRegionLinkedListIterator iter(from_list);
-  while (iter.more_available()) {
-    HeapRegion* hr = iter.get_next();
-    // In set_containing_set() we check that we either set the value
-    // from NULL to non-NULL or vice versa to catch bugs. So, we have
-    // to NULL it first before setting it to the value.
-    hr->set_containing_set(NULL);
-    hr->set_containing_set(this);
-  }
-#endif // ASSERT
-
-  if (_tail != NULL) {
-    assert(length() >  0 && _head != NULL, hrs_ext_msg(this, "invariant"));
-    _tail->set_next(from_list->_head);
-  } else {
-    assert(length() == 0 && _head == NULL, hrs_ext_msg(this, "invariant"));
-    _head = from_list->_head;
-  }
-  _tail = from_list->_tail;
-
-  _length           += from_list->length();
-  _region_num       += from_list->region_num();
-  _total_used_bytes += from_list->total_used_bytes();
-  from_list->clear();
-
-  verify_optional();
-  from_list->verify_optional();
+void FreeRegionList::add_as_head(FreeRegionList* from_list) {
+  add_as_head_or_tail(from_list, true /* as_head */);
 }
 
-void HeapRegionLinkedList::remove_all() {
-  hrs_assert_mt_safety_ok(this);
+void FreeRegionList::add_as_tail(FreeRegionList* from_list) {
+  add_as_head_or_tail(from_list, false /* as_head */);
+}
+
+void FreeRegionList::remove_all() {
+  check_mt_safety();
   verify_optional();
 
   HeapRegion* curr = _head;
   while (curr != NULL) {
-    hrs_assert_region_ok(this, curr, this);
+    verify_region(curr);
 
     HeapRegion* next = curr->next();
     curr->set_next(NULL);
@@ -351,8 +175,8 @@
   verify_optional();
 }
 
-void HeapRegionLinkedList::remove_all_pending(uint target_count) {
-  hrs_assert_mt_safety_ok(this);
+void FreeRegionList::remove_all_pending(uint target_count) {
+  check_mt_safety();
   assert(target_count > 1, hrs_ext_msg(this, "pre-condition"));
   assert(!is_empty(), hrs_ext_msg(this, "pre-condition"));
 
@@ -363,7 +187,7 @@
   HeapRegion* prev = NULL;
   uint count = 0;
   while (curr != NULL) {
-    hrs_assert_region_ok(this, curr, this);
+    verify_region(curr);
     HeapRegion* next = curr->next();
 
     if (curr->pending_removal()) {
@@ -387,7 +211,7 @@
       }
 
       curr->set_next(NULL);
-      remove_internal(curr);
+      remove(curr);
       curr->set_pending_removal(false);
 
       count += 1;
@@ -414,46 +238,26 @@
   verify_optional();
 }
 
-void HeapRegionLinkedList::verify() {
+void FreeRegionList::verify() {
   // See comment in HeapRegionSetBase::verify() about MT safety and
   // verification.
-  hrs_assert_mt_safety_ok(this);
+  check_mt_safety();
 
   // This will also do the basic verification too.
   verify_start();
 
-  HeapRegion* curr  = _head;
-  HeapRegion* prev1 = NULL;
-  HeapRegion* prev0 = NULL;
-  uint        count = 0;
-  while (curr != NULL) {
-    verify_next_region(curr);
-
-    count += 1;
-    guarantee(count < _unrealistically_long_length,
-              hrs_err_msg("[%s] the calculated length: %u "
-                          "seems very long, is there maybe a cycle? "
-                          "curr: "PTR_FORMAT" prev0: "PTR_FORMAT" "
-                          "prev1: "PTR_FORMAT" length: %u",
-                          name(), count, curr, prev0, prev1, length()));
-
-    prev1 = prev0;
-    prev0 = curr;
-    curr  = curr->next();
-  }
-
-  guarantee(_tail == prev0, hrs_ext_msg(this, "post-condition"));
+  verify_list();
 
   verify_end();
 }
 
-void HeapRegionLinkedList::clear() {
-  HeapRegionSetBase::clear();
+void FreeRegionList::clear() {
+  _count = HeapRegionSetCount();
   _head = NULL;
   _tail = NULL;
 }
 
-void HeapRegionLinkedList::print_on(outputStream* out, bool print_contents) {
+void FreeRegionList::print_on(outputStream* out, bool print_contents) {
   HeapRegionSetBase::print_on(out, print_contents);
   out->print_cr("  Linking");
   out->print_cr("    head              : "PTR_FORMAT, _head);
@@ -461,7 +265,7 @@
 
   if (print_contents) {
     out->print_cr("  Contents");
-    HeapRegionLinkedListIterator iter(this);
+    FreeRegionListIterator iter(this);
     while (iter.more_available()) {
       HeapRegion* hr = iter.get_next();
       hr->print_on(out);