# HG changeset patch
# User jmasa
# Date 1343450477 25200
# Node ID f8f2cc6553cffa9993fbed898b9fddbaf0722c37
# Parent  2f94212bcbe3dfa6ef9ce680a03973a80679b828# Parent  ad6062b5f71d67a2e1125f9bf4645a73d35cd784
Merge

diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/collectionSetChooser.hpp
--- a/hotspot/src/share/vm/gc_implementation/g1/collectionSetChooser.hpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/collectionSetChooser.hpp	Fri Jul 27 21:41:17 2012 -0700
@@ -153,4 +153,47 @@
   void verify() PRODUCT_RETURN;
 };
 
+class CSetChooserParUpdater : public StackObj {
+private:
+  CollectionSetChooser* _chooser;
+  bool _parallel;
+  uint _chunk_size;
+  uint _cur_chunk_idx;
+  uint _cur_chunk_end;
+  uint _regions_added;
+  size_t _reclaimable_bytes_added;
+
+public:
+  CSetChooserParUpdater(CollectionSetChooser* chooser,
+                        bool parallel, uint chunk_size) :
+    _chooser(chooser), _parallel(parallel), _chunk_size(chunk_size),
+    _cur_chunk_idx(0), _cur_chunk_end(0),
+    _regions_added(0), _reclaimable_bytes_added(0) { }
+
+  ~CSetChooserParUpdater() {
+    if (_parallel && _regions_added > 0) {
+      _chooser->update_totals(_regions_added, _reclaimable_bytes_added);
+    }
+  }
+
+  void add_region(HeapRegion* hr) {
+    if (_parallel) {
+      if (_cur_chunk_idx == _cur_chunk_end) {
+        _cur_chunk_idx = _chooser->claim_array_chunk(_chunk_size);
+        _cur_chunk_end = _cur_chunk_idx + _chunk_size;
+      }
+      assert(_cur_chunk_idx < _cur_chunk_end, "invariant");
+      _chooser->set_region(_cur_chunk_idx, hr);
+      _cur_chunk_idx += 1;
+    } else {
+      _chooser->add_region(hr);
+    }
+    _regions_added += 1;
+    _reclaimable_bytes_added += hr->reclaimable_bytes();
+  }
+
+  bool should_add(HeapRegion* hr) { return _chooser->should_add(hr); }
+};
+
 #endif // SHARE_VM_GC_IMPLEMENTATION_G1_COLLECTIONSETCHOOSER_HPP
+
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/concurrentMark.cpp
--- a/hotspot/src/share/vm/gc_implementation/g1/concurrentMark.cpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/concurrentMark.cpp	Fri Jul 27 21:41:17 2012 -0700
@@ -1226,9 +1226,7 @@
     } else {
       // Starts humongous case: calculate how many regions are part of
       // this humongous region and then set the bit range.
-      G1CollectedHeap* g1h = G1CollectedHeap::heap();
-      HeapRegion *last_hr = g1h->heap_region_containing_raw(hr->end() - 1);
-      BitMap::idx_t end_index = (BitMap::idx_t) last_hr->hrs_index() + 1;
+      BitMap::idx_t end_index = (BitMap::idx_t) hr->last_hc_index();
       _region_bm->par_at_put_range(index, end_index, true);
     }
   }
@@ -1645,26 +1643,27 @@
   size_t freed_bytes() { return _freed_bytes; }
 
   bool doHeapRegion(HeapRegion *hr) {
+    if (hr->continuesHumongous()) {
+      return false;
+    }
     // We use a claim value of zero here because all regions
     // were claimed with value 1 in the FinalCount task.
-    hr->reset_gc_time_stamp();
-    if (!hr->continuesHumongous()) {
-      double start = os::elapsedTime();
-      _regions_claimed++;
-      hr->note_end_of_marking();
-      _max_live_bytes += hr->max_live_bytes();
-      _g1->free_region_if_empty(hr,
-                                &_freed_bytes,
-                                _local_cleanup_list,
-                                _old_proxy_set,
-                                _humongous_proxy_set,
-                                _hrrs_cleanup_task,
-                                true /* par */);
-      double region_time = (os::elapsedTime() - start);
-      _claimed_region_time += region_time;
-      if (region_time > _max_region_time) {
-        _max_region_time = region_time;
-      }
+    _g1->reset_gc_time_stamps(hr);
+    double start = os::elapsedTime();
+    _regions_claimed++;
+    hr->note_end_of_marking();
+    _max_live_bytes += hr->max_live_bytes();
+    _g1->free_region_if_empty(hr,
+                              &_freed_bytes,
+                              _local_cleanup_list,
+                              _old_proxy_set,
+                              _humongous_proxy_set,
+                              _hrrs_cleanup_task,
+                              true /* par */);
+    double region_time = (os::elapsedTime() - start);
+    _claimed_region_time += region_time;
+    if (region_time > _max_region_time) {
+      _max_region_time = region_time;
     }
     return false;
   }
@@ -1881,6 +1880,7 @@
   } else {
     g1_par_note_end_task.work(0);
   }
+  g1h->check_gc_time_stamps();
 
   if (!cleanup_list_is_empty()) {
     // The cleanup list is not empty, so we'll have to process it
@@ -2449,24 +2449,8 @@
     } else {
       HeapRegion* hr  = _g1h->heap_region_containing(obj);
       guarantee(hr != NULL, "invariant");
-      bool over_tams = false;
-      bool marked = false;
-
-      switch (_vo) {
-        case VerifyOption_G1UsePrevMarking:
-          over_tams = hr->obj_allocated_since_prev_marking(obj);
-          marked = _g1h->isMarkedPrev(obj);
-          break;
-        case VerifyOption_G1UseNextMarking:
-          over_tams = hr->obj_allocated_since_next_marking(obj);
-          marked = _g1h->isMarkedNext(obj);
-          break;
-        case VerifyOption_G1UseMarkWord:
-          marked = obj->is_gc_marked();
-          break;
-        default:
-          ShouldNotReachHere();
-      }
+      bool over_tams = _g1h->allocated_since_marking(obj, hr, _vo);
+      bool marked = _g1h->is_marked(obj, _vo);
 
       if (over_tams) {
         str = " >";
@@ -2502,24 +2486,8 @@
     _out(out), _vo(vo), _all(all), _hr(hr) { }
 
   void do_object(oop o) {
-    bool over_tams = false;
-    bool marked = false;
-
-    switch (_vo) {
-      case VerifyOption_G1UsePrevMarking:
-        over_tams = _hr->obj_allocated_since_prev_marking(o);
-        marked = _g1h->isMarkedPrev(o);
-        break;
-      case VerifyOption_G1UseNextMarking:
-        over_tams = _hr->obj_allocated_since_next_marking(o);
-        marked = _g1h->isMarkedNext(o);
-        break;
-      case VerifyOption_G1UseMarkWord:
-        marked = o->is_gc_marked();
-        break;
-      default:
-        ShouldNotReachHere();
-    }
+    bool over_tams = _g1h->allocated_since_marking(o, _hr, _vo);
+    bool marked = _g1h->is_marked(o, _vo);
     bool print_it = _all || over_tams || marked;
 
     if (print_it) {
@@ -2533,32 +2501,17 @@
 
 class PrintReachableRegionClosure : public HeapRegionClosure {
 private:
-  outputStream* _out;
-  VerifyOption  _vo;
-  bool          _all;
+  G1CollectedHeap* _g1h;
+  outputStream*    _out;
+  VerifyOption     _vo;
+  bool             _all;
 
 public:
   bool doHeapRegion(HeapRegion* hr) {
     HeapWord* b = hr->bottom();
     HeapWord* e = hr->end();
     HeapWord* t = hr->top();
-    HeapWord* p = NULL;
-
-    switch (_vo) {
-      case VerifyOption_G1UsePrevMarking:
-        p = hr->prev_top_at_mark_start();
-        break;
-      case VerifyOption_G1UseNextMarking:
-        p = hr->next_top_at_mark_start();
-        break;
-      case VerifyOption_G1UseMarkWord:
-        // When we are verifying marking using the mark word
-        // TAMS has no relevance.
-        assert(p == NULL, "post-condition");
-        break;
-      default:
-        ShouldNotReachHere();
-    }
+    HeapWord* p = _g1h->top_at_mark_start(hr, _vo);
     _out->print_cr("** ["PTR_FORMAT", "PTR_FORMAT"] top: "PTR_FORMAT" "
                    "TAMS: "PTR_FORMAT, b, e, t, p);
     _out->cr();
@@ -2580,20 +2533,9 @@
   PrintReachableRegionClosure(outputStream* out,
                               VerifyOption  vo,
                               bool          all) :
-    _out(out), _vo(vo), _all(all) { }
+    _g1h(G1CollectedHeap::heap()), _out(out), _vo(vo), _all(all) { }
 };
 
-static const char* verify_option_to_tams(VerifyOption vo) {
-  switch (vo) {
-    case VerifyOption_G1UsePrevMarking:
-      return "PTAMS";
-    case VerifyOption_G1UseNextMarking:
-      return "NTAMS";
-    default:
-      return "NONE";
-  }
-}
-
 void ConcurrentMark::print_reachable(const char* str,
                                      VerifyOption vo,
                                      bool all) {
@@ -2622,7 +2564,7 @@
   }
 
   outputStream* out = &fout;
-  out->print_cr("-- USING %s", verify_option_to_tams(vo));
+  out->print_cr("-- USING %s", _g1h->top_at_mark_start_str(vo));
   out->cr();
 
   out->print_cr("--- ITERATING OVER REGIONS");
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp
--- a/hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Fri Jul 27 21:41:17 2012 -0700
@@ -1149,13 +1149,16 @@
 }
 
 class PostMCRemSetClearClosure: public HeapRegionClosure {
+  G1CollectedHeap* _g1h;
   ModRefBarrierSet* _mr_bs;
 public:
-  PostMCRemSetClearClosure(ModRefBarrierSet* mr_bs) : _mr_bs(mr_bs) {}
+  PostMCRemSetClearClosure(G1CollectedHeap* g1h, ModRefBarrierSet* mr_bs) :
+    _g1h(g1h), _mr_bs(mr_bs) { }
   bool doHeapRegion(HeapRegion* r) {
-    r->reset_gc_time_stamp();
-    if (r->continuesHumongous())
+    if (r->continuesHumongous()) {
       return false;
+    }
+    _g1h->reset_gc_time_stamps(r);
     HeapRegionRemSet* hrrs = r->rem_set();
     if (hrrs != NULL) hrrs->clear();
     // You might think here that we could clear just the cards
@@ -1168,19 +1171,10 @@
   }
 };
 
-
-class PostMCRemSetInvalidateClosure: public HeapRegionClosure {
-  ModRefBarrierSet* _mr_bs;
-public:
-  PostMCRemSetInvalidateClosure(ModRefBarrierSet* mr_bs) : _mr_bs(mr_bs) {}
-  bool doHeapRegion(HeapRegion* r) {
-    if (r->continuesHumongous()) return false;
-    if (r->used_region().word_size() != 0) {
-      _mr_bs->invalidate(r->used_region(), true /*whole heap*/);
-    }
-    return false;
-  }
-};
+void G1CollectedHeap::clear_rsets_post_compaction() {
+  PostMCRemSetClearClosure rs_clear(this, mr_bs());
+  heap_region_iterate(&rs_clear);
+}
 
 class RebuildRSOutOfRegionClosure: public HeapRegionClosure {
   G1CollectedHeap*   _g1h;
@@ -1229,7 +1223,7 @@
       if (!hr->isHumongous()) {
         _hr_printer->post_compaction(hr, G1HRPrinter::Old);
       } else if (hr->startsHumongous()) {
-        if (hr->capacity() == HeapRegion::GrainBytes) {
+        if (hr->region_num() == 1) {
           // single humongous region
           _hr_printer->post_compaction(hr, G1HRPrinter::SingleHumongous);
         } else {
@@ -1247,6 +1241,11 @@
     : _hr_printer(hr_printer) { }
 };
 
+void G1CollectedHeap::print_hrs_post_compaction() {
+  PostCompactionPrinterClosure cl(hr_printer());
+  heap_region_iterate(&cl);
+}
+
 bool G1CollectedHeap::do_collection(bool explicit_gc,
                                     bool clear_all_soft_refs,
                                     size_t word_size) {
@@ -1402,8 +1401,8 @@
     // Since everything potentially moved, we will clear all remembered
     // sets, and clear all cards.  Later we will rebuild remebered
     // sets. We will also reset the GC time stamps of the regions.
-    PostMCRemSetClearClosure rs_clear(mr_bs());
-    heap_region_iterate(&rs_clear);
+    clear_rsets_post_compaction();
+    check_gc_time_stamps();
 
     // Resize the heap if necessary.
     resize_if_necessary_after_full_collection(explicit_gc ? 0 : word_size);
@@ -1413,9 +1412,7 @@
       // that all the COMMIT / UNCOMMIT events are generated before
       // the end GC event.
 
-      PostCompactionPrinterClosure cl(hr_printer());
-      heap_region_iterate(&cl);
-
+      print_hrs_post_compaction();
       _hr_printer.end_gc(true /* full */, (size_t) total_collections());
     }
 
@@ -2263,6 +2260,51 @@
   return _g1_committed.byte_size();
 }
 
+void G1CollectedHeap::reset_gc_time_stamps(HeapRegion* hr) {
+  assert(!hr->continuesHumongous(), "pre-condition");
+  hr->reset_gc_time_stamp();
+  if (hr->startsHumongous()) {
+    uint first_index = hr->hrs_index() + 1;
+    uint last_index = hr->last_hc_index();
+    for (uint i = first_index; i < last_index; i += 1) {
+      HeapRegion* chr = region_at(i);
+      assert(chr->continuesHumongous(), "sanity");
+      chr->reset_gc_time_stamp();
+    }
+  }
+}
+
+#ifndef PRODUCT
+class CheckGCTimeStampsHRClosure : public HeapRegionClosure {
+private:
+  unsigned _gc_time_stamp;
+  bool _failures;
+
+public:
+  CheckGCTimeStampsHRClosure(unsigned gc_time_stamp) :
+    _gc_time_stamp(gc_time_stamp), _failures(false) { }
+
+  virtual bool doHeapRegion(HeapRegion* hr) {
+    unsigned region_gc_time_stamp = hr->get_gc_time_stamp();
+    if (_gc_time_stamp != region_gc_time_stamp) {
+      gclog_or_tty->print_cr("Region "HR_FORMAT" has GC time stamp = %d, "
+                             "expected %d", HR_FORMAT_PARAMS(hr),
+                             region_gc_time_stamp, _gc_time_stamp);
+      _failures = true;
+    }
+    return false;
+  }
+
+  bool failures() { return _failures; }
+};
+
+void G1CollectedHeap::check_gc_time_stamps() {
+  CheckGCTimeStampsHRClosure cl(_gc_time_stamp);
+  heap_region_iterate(&cl);
+  guarantee(!cl.failures(), "all GC time stamps should have been reset");
+}
+#endif // PRODUCT
+
 void G1CollectedHeap::iterate_dirty_card_closure(CardTableEntryClosure* cl,
                                                  DirtyCardQueue* into_cset_dcq,
                                                  bool concurrent,
@@ -2530,7 +2572,7 @@
   IterateOopClosureRegionClosure(MemRegion mr, OopClosure* cl)
     : _mr(mr), _cl(cl) {}
   bool doHeapRegion(HeapRegion* r) {
-    if (! r->continuesHumongous()) {
+    if (!r->continuesHumongous()) {
       r->oop_iterate(_cl);
     }
     return false;
@@ -2601,14 +2643,9 @@
   _hrs.iterate(cl);
 }
 
-void G1CollectedHeap::heap_region_iterate_from(HeapRegion* r,
-                                               HeapRegionClosure* cl) const {
-  _hrs.iterate_from(r, cl);
-}
-
 void
 G1CollectedHeap::heap_region_par_iterate_chunked(HeapRegionClosure* cl,
-                                                 uint worker,
+                                                 uint worker_id,
                                                  uint no_of_par_workers,
                                                  jint claim_value) {
   const uint regions = n_regions();
@@ -2619,7 +2656,9 @@
          no_of_par_workers == workers()->total_workers(),
          "Non dynamic should use fixed number of workers");
   // try to spread out the starting points of the workers
-  const uint start_index = regions / max_workers * worker;
+  const HeapRegion* start_hr =
+                        start_region_for_worker(worker_id, no_of_par_workers);
+  const uint start_index = start_hr->hrs_index();
 
   // each worker will actually look at all regions
   for (uint count = 0; count < regions; ++count) {
@@ -2861,6 +2900,17 @@
   return result;
 }
 
+HeapRegion* G1CollectedHeap::start_region_for_worker(uint worker_i,
+                                                     uint no_of_par_workers) {
+  uint worker_num =
+           G1CollectedHeap::use_parallel_gc_threads() ? no_of_par_workers : 1U;
+  assert(UseDynamicNumberOfGCThreads ||
+         no_of_par_workers == workers()->total_workers(),
+         "Non dynamic should use fixed number of workers");
+  const uint start_index = n_regions() * worker_i / worker_num;
+  return region_at(start_index);
+}
+
 void G1CollectedHeap::collection_set_iterate(HeapRegionClosure* cl) {
   HeapRegion* r = g1_policy()->collection_set();
   while (r != NULL) {
@@ -2974,6 +3024,51 @@
   g1_rem_set()->prepare_for_verify();
 }
 
+bool G1CollectedHeap::allocated_since_marking(oop obj, HeapRegion* hr,
+                                              VerifyOption vo) {
+  switch (vo) {
+  case VerifyOption_G1UsePrevMarking:
+    return hr->obj_allocated_since_prev_marking(obj);
+  case VerifyOption_G1UseNextMarking:
+    return hr->obj_allocated_since_next_marking(obj);
+  case VerifyOption_G1UseMarkWord:
+    return false;
+  default:
+    ShouldNotReachHere();
+  }
+  return false; // keep some compilers happy
+}
+
+HeapWord* G1CollectedHeap::top_at_mark_start(HeapRegion* hr, VerifyOption vo) {
+  switch (vo) {
+  case VerifyOption_G1UsePrevMarking: return hr->prev_top_at_mark_start();
+  case VerifyOption_G1UseNextMarking: return hr->next_top_at_mark_start();
+  case VerifyOption_G1UseMarkWord:    return NULL;
+  default:                            ShouldNotReachHere();
+  }
+  return NULL; // keep some compilers happy
+}
+
+bool G1CollectedHeap::is_marked(oop obj, VerifyOption vo) {
+  switch (vo) {
+  case VerifyOption_G1UsePrevMarking: return isMarkedPrev(obj);
+  case VerifyOption_G1UseNextMarking: return isMarkedNext(obj);
+  case VerifyOption_G1UseMarkWord:    return obj->is_gc_marked();
+  default:                            ShouldNotReachHere();
+  }
+  return false; // keep some compilers happy
+}
+
+const char* G1CollectedHeap::top_at_mark_start_str(VerifyOption vo) {
+  switch (vo) {
+  case VerifyOption_G1UsePrevMarking: return "PTAMS";
+  case VerifyOption_G1UseNextMarking: return "NTAMS";
+  case VerifyOption_G1UseMarkWord:    return "NONE";
+  default:                            ShouldNotReachHere();
+  }
+  return NULL; // keep some compilers happy
+}
+
 class VerifyLivenessOopClosure: public OopClosure {
   G1CollectedHeap* _g1h;
   VerifyOption _vo;
@@ -3061,9 +3156,9 @@
 
 class VerifyRegionClosure: public HeapRegionClosure {
 private:
-  bool         _par;
-  VerifyOption _vo;
-  bool         _failures;
+  bool             _par;
+  VerifyOption     _vo;
+  bool             _failures;
 public:
   // _vo == UsePrevMarking -> use "prev" marking information,
   // _vo == UseNextMarking -> use "next" marking information,
@@ -3078,8 +3173,6 @@
   }
 
   bool doHeapRegion(HeapRegion* r) {
-    guarantee(_par || r->claim_value() == HeapRegion::InitialClaimValue,
-              "Should be unclaimed at verify points.");
     if (!r->continuesHumongous()) {
       bool failures = false;
       r->verify(_vo, &failures);
@@ -5612,19 +5705,18 @@
   size_t hr_capacity = hr->capacity();
   size_t hr_pre_used = 0;
   _humongous_set.remove_with_proxy(hr, humongous_proxy_set);
+  // We need to read this before we make the region non-humongous,
+  // otherwise the information will be gone.
+  uint last_index = hr->last_hc_index();
   hr->set_notHumongous();
   free_region(hr, &hr_pre_used, free_list, par);
 
   uint i = hr->hrs_index() + 1;
-  uint num = 1;
-  while (i < n_regions()) {
+  while (i < last_index) {
     HeapRegion* curr_hr = region_at(i);
-    if (!curr_hr->continuesHumongous()) {
-      break;
-    }
+    assert(curr_hr->continuesHumongous(), "invariant");
     curr_hr->set_notHumongous();
     free_region(curr_hr, &hr_pre_used, free_list, par);
-    num += 1;
     i += 1;
   }
   assert(hr_pre_used == hr_used,
@@ -5732,7 +5824,6 @@
 
 void G1CollectedHeap::verify_dirty_young_regions() {
   verify_dirty_young_list(_young_list->first_region());
-  verify_dirty_young_list(_young_list->first_survivor_region());
 }
 #endif
 
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.hpp
--- a/hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.hpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/g1CollectedHeap.hpp	Fri Jul 27 21:41:17 2012 -0700
@@ -375,6 +375,13 @@
   // this method will be found dead by the marking cycle).
   void allocate_dummy_regions() PRODUCT_RETURN;
 
+  // Clear RSets after a compaction. It also resets the GC time stamps.
+  void clear_rsets_post_compaction();
+
+  // If the HR printer is active, dump the state of the regions in the
+  // heap after a compaction.
+  void print_hrs_post_compaction();
+
   // These are macros so that, if the assert fires, we get the correct
   // line number, file, etc.
 
@@ -1061,11 +1068,18 @@
     clear_cset_start_regions();
   }
 
+  void check_gc_time_stamps() PRODUCT_RETURN;
+
   void increment_gc_time_stamp() {
     ++_gc_time_stamp;
     OrderAccess::fence();
   }
 
+  // Reset the given region's GC timestamp. If it's starts humongous,
+  // also reset the GC timestamp of its corresponding
+  // continues humongous regions too.
+  void reset_gc_time_stamps(HeapRegion* hr);
+
   void iterate_dirty_card_closure(CardTableEntryClosure* cl,
                                   DirtyCardQueue* into_cset_dcq,
                                   bool concurrent, int worker_i);
@@ -1302,11 +1316,6 @@
   // iteration early if the "doHeapRegion" method returns "true".
   void heap_region_iterate(HeapRegionClosure* blk) const;
 
-  // Iterate over heap regions starting with r (or the first region if "r"
-  // is NULL), in address order, terminating early if the "doHeapRegion"
-  // method returns "true".
-  void heap_region_iterate_from(HeapRegion* r, HeapRegionClosure* blk) const;
-
   // Return the region with the given index. It assumes the index is valid.
   HeapRegion* region_at(uint index) const { return _hrs.at(index); }
 
@@ -1351,6 +1360,11 @@
   // starting region for iterating over the current collection set.
   HeapRegion* start_cset_region_for_worker(int worker_i);
 
+  // This is a convenience method that is used by the
+  // HeapRegionIterator classes to calculate the starting region for
+  // each worker so that they do not all start from the same region.
+  HeapRegion* start_region_for_worker(uint worker_i, uint no_of_par_workers);
+
   // Iterate over the regions (if any) in the current collection set.
   void collection_set_iterate(HeapRegionClosure* blk);
 
@@ -1558,24 +1572,6 @@
   bool isMarkedPrev(oop obj) const;
   bool isMarkedNext(oop obj) const;
 
-  // vo == UsePrevMarking -> use "prev" marking information,
-  // vo == UseNextMarking -> use "next" marking information,
-  // vo == UseMarkWord    -> use mark word from object header
-  bool is_obj_dead_cond(const oop obj,
-                        const HeapRegion* hr,
-                        const VerifyOption vo) const {
-
-    switch (vo) {
-      case VerifyOption_G1UsePrevMarking:
-        return is_obj_dead(obj, hr);
-      case VerifyOption_G1UseNextMarking:
-        return is_obj_ill(obj, hr);
-      default:
-        assert(vo == VerifyOption_G1UseMarkWord, "must be");
-        return !obj->is_gc_marked();
-    }
-  }
-
   // Determine if an object is dead, given the object and also
   // the region to which the object belongs. An object is dead
   // iff a) it was not allocated since the last mark and b) it
@@ -1587,15 +1583,6 @@
       !isMarkedPrev(obj);
   }
 
-  // This is used when copying an object to survivor space.
-  // If the object is marked live, then we mark the copy live.
-  // If the object is allocated since the start of this mark
-  // cycle, then we mark the copy live.
-  // If the object has been around since the previous mark
-  // phase, and hasn't been marked yet during this phase,
-  // then we don't mark it, we just wait for the
-  // current marking cycle to get to it.
-
   // This function returns true when an object has been
   // around since the previous marking and hasn't yet
   // been marked during this marking.
@@ -1613,23 +1600,6 @@
   // Added if it is in permanent gen it isn't dead.
   // Added if it is NULL it isn't dead.
 
-  // vo == UsePrevMarking -> use "prev" marking information,
-  // vo == UseNextMarking -> use "next" marking information,
-  // vo == UseMarkWord    -> use mark word from object header
-  bool is_obj_dead_cond(const oop obj,
-                        const VerifyOption vo) const {
-
-    switch (vo) {
-      case VerifyOption_G1UsePrevMarking:
-        return is_obj_dead(obj);
-      case VerifyOption_G1UseNextMarking:
-        return is_obj_ill(obj);
-      default:
-        assert(vo == VerifyOption_G1UseMarkWord, "must be");
-        return !obj->is_gc_marked();
-    }
-  }
-
   bool is_obj_dead(const oop obj) const {
     const HeapRegion* hr = heap_region_containing(obj);
     if (hr == NULL) {
@@ -1652,6 +1622,42 @@
     else return is_obj_ill(obj, hr);
   }
 
+  // The methods below are here for convenience and dispatch the
+  // appropriate method depending on value of the given VerifyOption
+  // parameter. The options for that parameter are:
+  //
+  // vo == UsePrevMarking -> use "prev" marking information,
+  // vo == UseNextMarking -> use "next" marking information,
+  // vo == UseMarkWord    -> use mark word from object header
+
+  bool is_obj_dead_cond(const oop obj,
+                        const HeapRegion* hr,
+                        const VerifyOption vo) const {
+    switch (vo) {
+    case VerifyOption_G1UsePrevMarking: return is_obj_dead(obj, hr);
+    case VerifyOption_G1UseNextMarking: return is_obj_ill(obj, hr);
+    case VerifyOption_G1UseMarkWord:    return !obj->is_gc_marked();
+    default:                            ShouldNotReachHere();
+    }
+    return false; // keep some compilers happy
+  }
+
+  bool is_obj_dead_cond(const oop obj,
+                        const VerifyOption vo) const {
+    switch (vo) {
+    case VerifyOption_G1UsePrevMarking: return is_obj_dead(obj);
+    case VerifyOption_G1UseNextMarking: return is_obj_ill(obj);
+    case VerifyOption_G1UseMarkWord:    return !obj->is_gc_marked();
+    default:                            ShouldNotReachHere();
+    }
+    return false; // keep some compilers happy
+  }
+
+  bool allocated_since_marking(oop obj, HeapRegion* hr, VerifyOption vo);
+  HeapWord* top_at_mark_start(HeapRegion* hr, VerifyOption vo);
+  bool is_marked(oop obj, VerifyOption vo);
+  const char* top_at_mark_start_str(VerifyOption vo);
+
   // The following is just to alert the verification code
   // that a full collection has occurred and that the
   // remembered sets are no longer up to date.
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/g1CollectorPolicy.cpp
--- a/hotspot/src/share/vm/gc_implementation/g1/g1CollectorPolicy.cpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/g1CollectorPolicy.cpp	Fri Jul 27 21:41:17 2012 -0700
@@ -1528,35 +1528,13 @@
 
 class ParKnownGarbageHRClosure: public HeapRegionClosure {
   G1CollectedHeap* _g1h;
-  CollectionSetChooser* _hrSorted;
-  uint _marked_regions_added;
-  size_t _reclaimable_bytes_added;
-  uint _chunk_size;
-  uint _cur_chunk_idx;
-  uint _cur_chunk_end; // Cur chunk [_cur_chunk_idx, _cur_chunk_end)
-
-  void get_new_chunk() {
-    _cur_chunk_idx = _hrSorted->claim_array_chunk(_chunk_size);
-    _cur_chunk_end = _cur_chunk_idx + _chunk_size;
-  }
-  void add_region(HeapRegion* r) {
-    if (_cur_chunk_idx == _cur_chunk_end) {
-      get_new_chunk();
-    }
-    assert(_cur_chunk_idx < _cur_chunk_end, "postcondition");
-    _hrSorted->set_region(_cur_chunk_idx, r);
-    _marked_regions_added++;
-    _reclaimable_bytes_added += r->reclaimable_bytes();
-    _cur_chunk_idx++;
-  }
+  CSetChooserParUpdater _cset_updater;
 
 public:
   ParKnownGarbageHRClosure(CollectionSetChooser* hrSorted,
                            uint chunk_size) :
-      _g1h(G1CollectedHeap::heap()),
-      _hrSorted(hrSorted), _chunk_size(chunk_size),
-      _marked_regions_added(0), _reclaimable_bytes_added(0),
-      _cur_chunk_idx(0), _cur_chunk_end(0) { }
+    _g1h(G1CollectedHeap::heap()),
+    _cset_updater(hrSorted, true /* parallel */, chunk_size) { }
 
   bool doHeapRegion(HeapRegion* r) {
     // Do we have any marking information for this region?
@@ -1564,14 +1542,12 @@
       // We will skip any region that's currently used as an old GC
       // alloc region (we should not consider those for collection
       // before we fill them up).
-      if (_hrSorted->should_add(r) && !_g1h->is_old_gc_alloc_region(r)) {
-        add_region(r);
+      if (_cset_updater.should_add(r) && !_g1h->is_old_gc_alloc_region(r)) {
+        _cset_updater.add_region(r);
       }
     }
     return false;
   }
-  uint marked_regions_added() { return _marked_regions_added; }
-  size_t reclaimable_bytes_added() { return _reclaimable_bytes_added; }
 };
 
 class ParKnownGarbageTask: public AbstractGangTask {
@@ -1591,10 +1567,6 @@
     _g1->heap_region_par_iterate_chunked(&parKnownGarbageCl, worker_id,
                                          _g1->workers()->active_workers(),
                                          HeapRegion::InitialClaimValue);
-    uint regions_added = parKnownGarbageCl.marked_regions_added();
-    size_t reclaimable_bytes_added =
-                                   parKnownGarbageCl.reclaimable_bytes_added();
-    _hrSorted->update_totals(regions_added, reclaimable_bytes_added);
   }
 };
 
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/g1MarkSweep.cpp
--- a/hotspot/src/share/vm/gc_implementation/g1/g1MarkSweep.cpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/g1MarkSweep.cpp	Fri Jul 27 21:41:17 2012 -0700
@@ -262,18 +262,6 @@
   }
 };
 
-// Finds the first HeapRegion.
-class FindFirstRegionClosure: public HeapRegionClosure {
-  HeapRegion* _a_region;
-public:
-  FindFirstRegionClosure() : _a_region(NULL) {}
-  bool doHeapRegion(HeapRegion* r) {
-    _a_region = r;
-    return true;
-  }
-  HeapRegion* result() { return _a_region; }
-};
-
 void G1MarkSweep::mark_sweep_phase2() {
   // Now all live objects are marked, compute the new object addresses.
 
@@ -294,9 +282,8 @@
   TraceTime tm("phase 2", G1Log::fine() && Verbose, true, gclog_or_tty);
   GenMarkSweep::trace("2");
 
-  FindFirstRegionClosure cl;
-  g1h->heap_region_iterate(&cl);
-  HeapRegion *r = cl.result();
+  // find the first region
+  HeapRegion* r = g1h->region_at(0);
   CompactibleSpace* sp = r;
   if (r->isHumongous() && oop(r->bottom())->is_gc_marked()) {
     sp = r->next_compaction_space();
@@ -408,7 +395,3 @@
   g1h->heap_region_iterate(&blk);
 
 }
-
-// Local Variables: ***
-// c-indentation-style: gnu ***
-// End: ***
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/g1OopClosures.hpp
--- a/hotspot/src/share/vm/gc_implementation/g1/g1OopClosures.hpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/g1OopClosures.hpp	Fri Jul 27 21:41:17 2012 -0700
@@ -197,7 +197,6 @@
   HeapWord* _r_bottom;
   HeapWord* _r_end;
   OopClosure* _oc;
-  int _out_of_region;
 public:
   FilterOutOfRegionClosure(HeapRegion* r, OopClosure* oc);
   template <class T> void do_oop_nv(T* p);
@@ -205,7 +204,6 @@
   virtual void do_oop(narrowOop* p) { do_oop_nv(p); }
   bool apply_to_weak_ref_discovered_field() { return true; }
   bool do_header() { return false; }
-  int out_of_region() { return _out_of_region; }
 };
 
 // Closure for iterating over object fields during concurrent marking
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/g1OopClosures.inline.hpp
--- a/hotspot/src/share/vm/gc_implementation/g1/g1OopClosures.inline.hpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/g1OopClosures.inline.hpp	Fri Jul 27 21:41:17 2012 -0700
@@ -29,31 +29,22 @@
 #include "gc_implementation/g1/g1CollectedHeap.hpp"
 #include "gc_implementation/g1/g1OopClosures.hpp"
 #include "gc_implementation/g1/g1RemSet.hpp"
+#include "gc_implementation/g1/heapRegionRemSet.hpp"
 
 /*
  * This really ought to be an inline function, but apparently the C++
  * compiler sometimes sees fit to ignore inline declarations.  Sigh.
  */
 
-// This must a ifdef'ed because the counting it controls is in a
-// perf-critical inner loop.
-#define FILTERINTOCSCLOSURE_DOHISTOGRAMCOUNT 0
-
 template <class T>
 inline void FilterIntoCSClosure::do_oop_nv(T* p) {
   T heap_oop = oopDesc::load_heap_oop(p);
   if (!oopDesc::is_null(heap_oop) &&
       _g1->obj_in_cs(oopDesc::decode_heap_oop_not_null(heap_oop))) {
     _oc->do_oop(p);
-#if FILTERINTOCSCLOSURE_DOHISTOGRAMCOUNT
-    if (_dcto_cl != NULL)
-      _dcto_cl->incr_count();
-#endif
   }
 }
 
-#define FILTEROUTOFREGIONCLOSURE_DOHISTOGRAMCOUNT 0
-
 template <class T>
 inline void FilterOutOfRegionClosure::do_oop_nv(T* p) {
   T heap_oop = oopDesc::load_heap_oop(p);
@@ -61,9 +52,6 @@
     HeapWord* obj_hw = (HeapWord*)oopDesc::decode_heap_oop_not_null(heap_oop);
     if (obj_hw < _r_bottom || obj_hw >= _r_end) {
       _oc->do_oop(p);
-#if FILTEROUTOFREGIONCLOSURE_DOHISTOGRAMCOUNT
-      _out_of_region++;
-#endif
     }
   }
 }
@@ -182,6 +170,7 @@
 #endif // ASSERT
 
   assert(_from != NULL, "from region must be non-NULL");
+  assert(_from->is_in_reserved(p), "p is not in from");
 
   HeapRegion* to = _g1->heap_region_containing(obj);
   if (to != NULL && _from != to) {
@@ -212,14 +201,16 @@
       // or processed (if an evacuation failure occurs) at the end
       // of the collection.
       // See G1RemSet::cleanup_after_oops_into_collection_set_do().
-    } else {
-      // We either don't care about pushing references that point into the
-      // collection set (i.e. we're not during an evacuation pause) _or_
-      // the reference doesn't point into the collection set. Either way
-      // we add the reference directly to the RSet of the region containing
-      // the referenced object.
-      _g1_rem_set->par_write_ref(_from, p, _worker_i);
+      return;
     }
+
+    // We either don't care about pushing references that point into the
+    // collection set (i.e. we're not during an evacuation pause) _or_
+    // the reference doesn't point into the collection set. Either way
+    // we add the reference directly to the RSet of the region containing
+    // the referenced object.
+    assert(to->rem_set() != NULL, "Need per-region 'into' remsets.");
+    to->rem_set()->add_reference(p, _worker_i);
   }
 }
 
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/g1RemSet.cpp
--- a/hotspot/src/share/vm/gc_implementation/g1/g1RemSet.cpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/g1RemSet.cpp	Fri Jul 27 21:41:17 2012 -0700
@@ -280,62 +280,6 @@
   _g1p->phase_times()->record_update_rs_time(worker_i, (os::elapsedTime() - start) * 1000.0);
 }
 
-class CountRSSizeClosure: public HeapRegionClosure {
-  size_t _n;
-  size_t _tot;
-  size_t _max;
-  HeapRegion* _max_r;
-  enum {
-    N = 20,
-    MIN = 6
-  };
-  int _histo[N];
-public:
-  CountRSSizeClosure() : _n(0), _tot(0), _max(0), _max_r(NULL) {
-    for (int i = 0; i < N; i++) _histo[i] = 0;
-  }
-  bool doHeapRegion(HeapRegion* r) {
-    if (!r->continuesHumongous()) {
-      size_t occ = r->rem_set()->occupied();
-      _n++;
-      _tot += occ;
-      if (occ > _max) {
-        _max = occ;
-        _max_r = r;
-      }
-      // Fit it into a histo bin.
-      int s = 1 << MIN;
-      int i = 0;
-      while (occ > (size_t) s && i < (N-1)) {
-        s = s << 1;
-        i++;
-      }
-      _histo[i]++;
-    }
-    return false;
-  }
-  size_t n() { return _n; }
-  size_t tot() { return _tot; }
-  size_t mx() { return _max; }
-  HeapRegion* mxr() { return _max_r; }
-  void print_histo() {
-    int mx = N;
-    while (mx >= 0) {
-      if (_histo[mx-1] > 0) break;
-      mx--;
-    }
-    gclog_or_tty->print_cr("Number of regions with given RS sizes:");
-    gclog_or_tty->print_cr("           <= %8d   %8d", 1 << MIN, _histo[0]);
-    for (int i = 1; i < mx-1; i++) {
-      gclog_or_tty->print_cr("  %8d  - %8d   %8d",
-                    (1 << (MIN + i - 1)) + 1,
-                    1 << (MIN + i),
-                    _histo[i]);
-    }
-    gclog_or_tty->print_cr("            > %8d   %8d", (1 << (MIN+mx-2))+1, _histo[mx-1]);
-  }
-};
-
 void G1RemSet::cleanupHRRS() {
   HeapRegionRemSet::cleanup();
 }
@@ -349,17 +293,6 @@
     _cg1r->clear_and_record_card_counts();
   }
 
-  // Make this into a command-line flag...
-  if (G1RSCountHisto && (ParallelGCThreads == 0 || worker_i == 0)) {
-    CountRSSizeClosure count_cl;
-    _g1->heap_region_iterate(&count_cl);
-    gclog_or_tty->print_cr("Avg of %d RS counts is %f, max is %d, "
-                  "max region is " PTR_FORMAT,
-                  count_cl.n(), (float)count_cl.tot()/(float)count_cl.n(),
-                  count_cl.mx(), count_cl.mxr());
-    count_cl.print_histo();
-  }
-
   // We cache the value of 'oc' closure into the appropriate slot in the
   // _cset_rs_update_cl for this worker
   assert(worker_i < (int)n_workers(), "sanity");
@@ -568,8 +501,6 @@
 }
 
 
-static IntHistogram out_of_histo(50, 50);
-
 
 G1TriggerClosure::G1TriggerClosure() :
   _triggered(false) { }
@@ -671,7 +602,6 @@
       sdcq->enqueue(card_ptr);
     }
   } else {
-    out_of_histo.add_entry(filter_then_update_rs_oop_cl.out_of_region());
     _conc_refine_cards++;
   }
 
@@ -862,11 +792,6 @@
   card_repeat_count.print_on(gclog_or_tty);
 #endif
 
-  if (FILTEROUTOFREGIONCLOSURE_DOHISTOGRAMCOUNT) {
-    gclog_or_tty->print_cr("\nG1 rem-set out-of-region histogram: ");
-    gclog_or_tty->print_cr("  # of CS ptrs --> # of cards with that number.");
-    out_of_histo.print_on(gclog_or_tty);
-  }
   gclog_or_tty->print_cr("\n Concurrent RS processed %d cards",
                          _conc_refine_cards);
   DirtyCardQueueSet& dcqs = JavaThread::dirty_card_queue_set();
@@ -889,21 +814,24 @@
 
   HRRSStatsIter blk;
   g1->heap_region_iterate(&blk);
-  gclog_or_tty->print_cr("  Total heap region rem set sizes = " SIZE_FORMAT "K."
-                         "  Max = " SIZE_FORMAT "K.",
+  gclog_or_tty->print_cr("  Total heap region rem set sizes = "SIZE_FORMAT"K."
+                         "  Max = "SIZE_FORMAT"K.",
                          blk.total_mem_sz()/K, blk.max_mem_sz()/K);
-  gclog_or_tty->print_cr("  Static structures = " SIZE_FORMAT "K,"
-                         " free_lists = " SIZE_FORMAT "K.",
-                         HeapRegionRemSet::static_mem_size()/K,
-                         HeapRegionRemSet::fl_mem_size()/K);
-  gclog_or_tty->print_cr("    %d occupied cards represented.",
+  gclog_or_tty->print_cr("  Static structures = "SIZE_FORMAT"K,"
+                         " free_lists = "SIZE_FORMAT"K.",
+                         HeapRegionRemSet::static_mem_size() / K,
+                         HeapRegionRemSet::fl_mem_size() / K);
+  gclog_or_tty->print_cr("    "SIZE_FORMAT" occupied cards represented.",
                          blk.occupied());
-  gclog_or_tty->print_cr("    Max sz region = [" PTR_FORMAT ", " PTR_FORMAT " )"
-                         ", cap = " SIZE_FORMAT "K, occ = " SIZE_FORMAT "K.",
-                         blk.max_mem_sz_region()->bottom(), blk.max_mem_sz_region()->end(),
-                         (blk.max_mem_sz_region()->rem_set()->mem_size() + K - 1)/K,
-                         (blk.max_mem_sz_region()->rem_set()->occupied() + K - 1)/K);
-  gclog_or_tty->print_cr("    Did %d coarsenings.", HeapRegionRemSet::n_coarsenings());
+  HeapRegion* max_mem_sz_region = blk.max_mem_sz_region();
+  HeapRegionRemSet* rem_set = max_mem_sz_region->rem_set();
+  gclog_or_tty->print_cr("    Max size region = "HR_FORMAT", "
+                         "size = "SIZE_FORMAT "K, occupied = "SIZE_FORMAT"K.",
+                         HR_FORMAT_PARAMS(max_mem_sz_region),
+                         (rem_set->mem_size() + K - 1)/K,
+                         (rem_set->occupied() + K - 1)/K);
+  gclog_or_tty->print_cr("    Did %d coarsenings.",
+                         HeapRegionRemSet::n_coarsenings());
 }
 
 void G1RemSet::prepare_for_verify() {
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/heapRegion.cpp
--- a/hotspot/src/share/vm/gc_implementation/g1/heapRegion.cpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegion.cpp	Fri Jul 27 21:41:17 2012 -0700
@@ -44,14 +44,11 @@
                                  CardTableModRefBS::PrecisionStyle precision,
                                  FilterKind fk) :
   ContiguousSpaceDCTOC(hr, cl, precision, NULL),
-  _hr(hr), _fk(fk), _g1(g1)
-{ }
+  _hr(hr), _fk(fk), _g1(g1) { }
 
 FilterOutOfRegionClosure::FilterOutOfRegionClosure(HeapRegion* r,
                                                    OopClosure* oc) :
-  _r_bottom(r->bottom()), _r_end(r->end()),
-  _oc(oc), _out_of_region(0)
-{}
+  _r_bottom(r->bottom()), _r_end(r->end()), _oc(oc) { }
 
 class VerifyLiveClosure: public OopClosure {
 private:
@@ -512,35 +509,19 @@
   assert(HeapRegionRemSet::num_par_rem_sets() > 0, "Invariant.");
 }
 
-class NextCompactionHeapRegionClosure: public HeapRegionClosure {
-  const HeapRegion* _target;
-  bool _target_seen;
-  HeapRegion* _last;
-  CompactibleSpace* _res;
-public:
-  NextCompactionHeapRegionClosure(const HeapRegion* target) :
-    _target(target), _target_seen(false), _res(NULL) {}
-  bool doHeapRegion(HeapRegion* cur) {
-    if (_target_seen) {
-      if (!cur->isHumongous()) {
-        _res = cur;
-        return true;
-      }
-    } else if (cur == _target) {
-      _target_seen = true;
+CompactibleSpace* HeapRegion::next_compaction_space() const {
+  // We're not using an iterator given that it will wrap around when
+  // it reaches the last region and this is not what we want here.
+  G1CollectedHeap* g1h = G1CollectedHeap::heap();
+  uint index = hrs_index() + 1;
+  while (index < g1h->n_regions()) {
+    HeapRegion* hr = g1h->region_at(index);
+    if (!hr->isHumongous()) {
+      return hr;
     }
-    return false;
+    index += 1;
   }
-  CompactibleSpace* result() { return _res; }
-};
-
-CompactibleSpace* HeapRegion::next_compaction_space() const {
-  G1CollectedHeap* g1h = G1CollectedHeap::heap();
-  // cast away const-ness
-  HeapRegion* r = (HeapRegion*) this;
-  NextCompactionHeapRegionClosure blk(r);
-  g1h->heap_region_iterate_from(r, &blk);
-  return blk.result();
+  return NULL;
 }
 
 void HeapRegion::save_marks() {
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/heapRegion.hpp
--- a/hotspot/src/share/vm/gc_implementation/g1/heapRegion.hpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegion.hpp	Fri Jul 27 21:41:17 2012 -0700
@@ -55,7 +55,10 @@
 #define HR_FORMAT "%u:(%s)["PTR_FORMAT","PTR_FORMAT","PTR_FORMAT"]"
 #define HR_FORMAT_PARAMS(_hr_) \
                 (_hr_)->hrs_index(), \
-                (_hr_)->is_survivor() ? "S" : (_hr_)->is_young() ? "E" : "-", \
+                (_hr_)->is_survivor() ? "S" : (_hr_)->is_young() ? "E" : \
+                (_hr_)->startsHumongous() ? "HS" : \
+                (_hr_)->continuesHumongous() ? "HC" : \
+                !(_hr_)->is_empty() ? "O" : "F", \
                 (_hr_)->bottom(), (_hr_)->top(), (_hr_)->end()
 
 // sentinel value for hrs_index
@@ -173,6 +176,7 @@
   virtual HeapWord* saved_mark_word() const;
   virtual void set_saved_mark();
   void reset_gc_time_stamp() { _gc_time_stamp = 0; }
+  unsigned get_gc_time_stamp() { return _gc_time_stamp; }
 
   // See the comment above in the declaration of _pre_dummy_top for an
   // explanation of what it is.
@@ -439,6 +443,25 @@
     return _humongous_start_region;
   }
 
+  // Return the number of distinct regions that are covered by this region:
+  // 1 if the region is not humongous, >= 1 if the region is humongous.
+  uint region_num() const {
+    if (!isHumongous()) {
+      return 1U;
+    } else {
+      assert(startsHumongous(), "doesn't make sense on HC regions");
+      assert(capacity() % HeapRegion::GrainBytes == 0, "sanity");
+      return (uint) (capacity() >> HeapRegion::LogOfHRGrainBytes);
+    }
+  }
+
+  // Return the index + 1 of the last HC regions that's associated
+  // with this HS region.
+  uint last_hc_index() const {
+    assert(startsHumongous(), "don't call this otherwise");
+    return hrs_index() + region_num();
+  }
+
   // Same as Space::is_in_reserved, but will use the original size of the region.
   // The original size is different only for start humongous regions. They get
   // their _end set up to be the end of the last continues region of the
@@ -622,8 +645,8 @@
   bool is_marked() { return _prev_top_at_mark_start != bottom(); }
 
   void reset_during_compaction() {
-    guarantee( isHumongous() && startsHumongous(),
-               "should only be called for humongous regions");
+    assert(isHumongous() && startsHumongous(),
+           "should only be called for starts humongous regions");
 
     zero_marked_bytes();
     init_top_at_mark_start();
@@ -774,7 +797,7 @@
   virtual void oop_since_save_marks_iterate##nv_suffix(OopClosureType* cl);
   SPECIALIZED_SINCE_SAVE_MARKS_CLOSURES(HeapRegion_OOP_SINCE_SAVE_MARKS_DECL)
 
-  CompactibleSpace* next_compaction_space() const;
+  virtual CompactibleSpace* next_compaction_space() const;
 
   virtual void reset_after_compaction();
 
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/heapRegionRemSet.cpp
--- a/hotspot/src/share/vm/gc_implementation/g1/heapRegionRemSet.cpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegionRemSet.cpp	Fri Jul 27 21:41:17 2012 -0700
@@ -34,8 +34,6 @@
 #include "utilities/bitMap.inline.hpp"
 #include "utilities/globalDefinitions.hpp"
 
-// OtherRegionsTable
-
 class PerRegionTable: public CHeapObj<mtGC> {
   friend class OtherRegionsTable;
   friend class HeapRegionRemSetIterator;
@@ -44,19 +42,17 @@
   BitMap          _bm;
   jint            _occupied;
 
-  // next pointer for free/allocated lis
+  // next pointer for free/allocated 'all' list
   PerRegionTable* _next;
 
-  static PerRegionTable* _free_list;
+  // prev pointer for the allocated 'all' list
+  PerRegionTable* _prev;
 
-#ifdef _MSC_VER
-  // For some reason even though the classes are marked as friend they are unable
-  // to access CardsPerRegion when private/protected. Only the windows c++ compiler
-  // says this Sun CC and linux gcc don't have a problem with access when private
+  // next pointer in collision list
+  PerRegionTable * _collision_list_next;
 
-  public:
-
-#endif // _MSC_VER
+  // Global free list of PRTs
+  static PerRegionTable* _free_list;
 
 protected:
   // We need access in order to union things into the base table.
@@ -69,7 +65,8 @@
   PerRegionTable(HeapRegion* hr) :
     _hr(hr),
     _occupied(0),
-    _bm(HeapRegion::CardsPerRegion, false /* in-resource-area */)
+    _bm(HeapRegion::CardsPerRegion, false /* in-resource-area */),
+    _collision_list_next(NULL), _next(NULL), _prev(NULL)
   {}
 
   void add_card_work(CardIdx_t from_card, bool par) {
@@ -126,9 +123,13 @@
     return _occupied;
   }
 
-  void init(HeapRegion* hr) {
+  void init(HeapRegion* hr, bool clear_links_to_all_list) {
+    if (clear_links_to_all_list) {
+      set_next(NULL);
+      set_prev(NULL);
+    }
     _hr = hr;
-    _next = NULL;
+    _collision_list_next = NULL;
     _occupied = 0;
     _bm.clear();
   }
@@ -175,22 +176,25 @@
     return _bm.at(card_ind);
   }
 
-  PerRegionTable* next() const { return _next; }
-  void set_next(PerRegionTable* nxt) { _next = nxt; }
-  PerRegionTable** next_addr() { return &_next; }
-
-  static void free(PerRegionTable* prt) {
+  // Bulk-free the PRTs from prt to last, assumes that they are
+  // linked together using their _next field.
+  static void bulk_free(PerRegionTable* prt, PerRegionTable* last) {
     while (true) {
       PerRegionTable* fl = _free_list;
-      prt->set_next(fl);
-      PerRegionTable* res =
-        (PerRegionTable*)
-        Atomic::cmpxchg_ptr(prt, &_free_list, fl);
-      if (res == fl) return;
+      last->set_next(fl);
+      PerRegionTable* res = (PerRegionTable*) Atomic::cmpxchg_ptr(prt, &_free_list, fl);
+      if (res == fl) {
+        return;
+      }
     }
     ShouldNotReachHere();
   }
 
+  static void free(PerRegionTable* prt) {
+    bulk_free(prt, prt);
+  }
+
+  // Returns an initialized PerRegionTable instance.
   static PerRegionTable* alloc(HeapRegion* hr) {
     PerRegionTable* fl = _free_list;
     while (fl != NULL) {
@@ -199,7 +203,7 @@
         (PerRegionTable*)
         Atomic::cmpxchg_ptr(nxt, &_free_list, fl);
       if (res == fl) {
-        fl->init(hr);
+        fl->init(hr, true);
         return fl;
       } else {
         fl = _free_list;
@@ -209,6 +213,31 @@
     return new PerRegionTable(hr);
   }
 
+  PerRegionTable* next() const { return _next; }
+  void set_next(PerRegionTable* next) { _next = next; }
+  PerRegionTable* prev() const { return _prev; }
+  void set_prev(PerRegionTable* prev) { _prev = prev; }
+
+  // Accessor and Modification routines for the pointer for the
+  // singly linked collision list that links the PRTs within the
+  // OtherRegionsTable::_fine_grain_regions hash table.
+  //
+  // It might be useful to also make the collision list doubly linked
+  // to avoid iteration over the collisions list during scrubbing/deletion.
+  // OTOH there might not be many collisions.
+
+  PerRegionTable* collision_list_next() const {
+    return _collision_list_next;
+  }
+
+  void set_collision_list_next(PerRegionTable* next) {
+    _collision_list_next = next;
+  }
+
+  PerRegionTable** collision_list_next_addr() {
+    return &_collision_list_next;
+  }
+
   static size_t fl_mem_size() {
     PerRegionTable* cur = _free_list;
     size_t res = 0;
@@ -234,6 +263,7 @@
   _coarse_map(G1CollectedHeap::heap()->max_regions(),
               false /* in-resource-area */),
   _fine_grain_regions(NULL),
+  _first_all_fine_prts(NULL), _last_all_fine_prts(NULL),
   _n_fine_entries(0), _n_coarse_entries(0),
   _fine_eviction_start(0),
   _sparse_table(hr)
@@ -264,6 +294,66 @@
   }
 }
 
+void OtherRegionsTable::link_to_all(PerRegionTable* prt) {
+  // We always append to the beginning of the list for convenience;
+  // the order of entries in this list does not matter.
+  if (_first_all_fine_prts != NULL) {
+    assert(_first_all_fine_prts->prev() == NULL, "invariant");
+    _first_all_fine_prts->set_prev(prt);
+    prt->set_next(_first_all_fine_prts);
+  } else {
+    // this is the first element we insert. Adjust the "last" pointer
+    _last_all_fine_prts = prt;
+    assert(prt->next() == NULL, "just checking");
+  }
+  // the new element is always the first element without a predecessor
+  prt->set_prev(NULL);
+  _first_all_fine_prts = prt;
+
+  assert(prt->prev() == NULL, "just checking");
+  assert(_first_all_fine_prts == prt, "just checking");
+  assert((_first_all_fine_prts == NULL && _last_all_fine_prts == NULL) ||
+         (_first_all_fine_prts != NULL && _last_all_fine_prts != NULL),
+         "just checking");
+  assert(_last_all_fine_prts == NULL || _last_all_fine_prts->next() == NULL,
+         "just checking");
+  assert(_first_all_fine_prts == NULL || _first_all_fine_prts->prev() == NULL,
+         "just checking");
+}
+
+void OtherRegionsTable::unlink_from_all(PerRegionTable* prt) {
+  if (prt->prev() != NULL) {
+    assert(_first_all_fine_prts != prt, "just checking");
+    prt->prev()->set_next(prt->next());
+    // removing the last element in the list?
+    if (_last_all_fine_prts == prt) {
+      _last_all_fine_prts = prt->prev();
+    }
+  } else {
+    assert(_first_all_fine_prts == prt, "just checking");
+    _first_all_fine_prts = prt->next();
+    // list is empty now?
+    if (_first_all_fine_prts == NULL) {
+      _last_all_fine_prts = NULL;
+    }
+  }
+
+  if (prt->next() != NULL) {
+    prt->next()->set_prev(prt->prev());
+  }
+
+  prt->set_next(NULL);
+  prt->set_prev(NULL);
+
+  assert((_first_all_fine_prts == NULL && _last_all_fine_prts == NULL) ||
+         (_first_all_fine_prts != NULL && _last_all_fine_prts != NULL),
+         "just checking");
+  assert(_last_all_fine_prts == NULL || _last_all_fine_prts->next() == NULL,
+         "just checking");
+  assert(_first_all_fine_prts == NULL || _first_all_fine_prts->prev() == NULL,
+         "just checking");
+}
+
 int**  OtherRegionsTable::_from_card_cache = NULL;
 size_t OtherRegionsTable::_from_card_cache_max_regions = 0;
 size_t OtherRegionsTable::_from_card_cache_mem_size = 0;
@@ -386,13 +476,16 @@
 
       if (_n_fine_entries == _max_fine_entries) {
         prt = delete_region_table();
+        // There is no need to clear the links to the 'all' list here:
+        // prt will be reused immediately, i.e. remain in the 'all' list.
+        prt->init(from_hr, false /* clear_links_to_all_list */);
       } else {
         prt = PerRegionTable::alloc(from_hr);
+        link_to_all(prt);
       }
-      prt->init(from_hr);
 
       PerRegionTable* first_prt = _fine_grain_regions[ind];
-      prt->set_next(first_prt);  // XXX Maybe move to init?
+      prt->set_collision_list_next(first_prt);
       _fine_grain_regions[ind] = prt;
       _n_fine_entries++;
 
@@ -438,7 +531,7 @@
   assert(0 <= ind && ind < _max_fine_entries, "Preconditions.");
   PerRegionTable* prt = _fine_grain_regions[ind];
   while (prt != NULL && prt->hr() != hr) {
-    prt = prt->next();
+    prt = prt->collision_list_next();
   }
   // Loop postcondition is the method postcondition.
   return prt;
@@ -473,8 +566,8 @@
         max_ind = i;
         max_occ = cur_occ;
       }
-      prev = cur->next_addr();
-      cur = cur->next();
+      prev = cur->collision_list_next_addr();
+      cur = cur->collision_list_next();
     }
     i = i + _fine_eviction_stride;
     if (i >= _n_fine_entries) i = i - _n_fine_entries;
@@ -503,7 +596,7 @@
   }
 
   // Unsplice.
-  *max_prev = max->next();
+  *max_prev = max->collision_list_next();
   Atomic::inc(&_n_coarsenings);
   _n_fine_entries--;
   return max;
@@ -534,7 +627,7 @@
     PerRegionTable* cur = _fine_grain_regions[i];
     PerRegionTable** prev = &_fine_grain_regions[i];
     while (cur != NULL) {
-      PerRegionTable* nxt = cur->next();
+      PerRegionTable* nxt = cur->collision_list_next();
       // If the entire region is dead, eliminate.
       if (G1RSScrubVerbose) {
         gclog_or_tty->print_cr("     For other region %u:",
@@ -542,11 +635,12 @@
       }
       if (!region_bm->at((size_t) cur->hr()->hrs_index())) {
         *prev = nxt;
-        cur->set_next(NULL);
+        cur->set_collision_list_next(NULL);
         _n_fine_entries--;
         if (G1RSScrubVerbose) {
           gclog_or_tty->print_cr("          deleted via region map.");
         }
+        unlink_from_all(cur);
         PerRegionTable::free(cur);
       } else {
         // Do fine-grain elimination.
@@ -560,11 +654,12 @@
         // Did that empty the table completely?
         if (cur->occupied() == 0) {
           *prev = nxt;
-          cur->set_next(NULL);
+          cur->set_collision_list_next(NULL);
           _n_fine_entries--;
+          unlink_from_all(cur);
           PerRegionTable::free(cur);
         } else {
-          prev = cur->next_addr();
+          prev = cur->collision_list_next_addr();
         }
       }
       cur = nxt;
@@ -587,13 +682,15 @@
 
 size_t OtherRegionsTable::occ_fine() const {
   size_t sum = 0;
-  for (size_t i = 0; i < _max_fine_entries; i++) {
-    PerRegionTable* cur = _fine_grain_regions[i];
-    while (cur != NULL) {
-      sum += cur->occupied();
-      cur = cur->next();
-    }
+
+  size_t num = 0;
+  PerRegionTable * cur = _first_all_fine_prts;
+  while (cur != NULL) {
+    sum += cur->occupied();
+    cur = cur->next();
+    num++;
   }
+  guarantee(num == _n_fine_entries, "just checking");
   return sum;
 }
 
@@ -609,12 +706,10 @@
   // Cast away const in this case.
   MutexLockerEx x((Mutex*)&_m, Mutex::_no_safepoint_check_flag);
   size_t sum = 0;
-  for (size_t i = 0; i < _max_fine_entries; i++) {
-    PerRegionTable* cur = _fine_grain_regions[i];
-    while (cur != NULL) {
-      sum += cur->mem_size();
-      cur = cur->next();
-    }
+  PerRegionTable * cur = _first_all_fine_prts;
+  while (cur != NULL) {
+    sum += cur->mem_size();
+    cur = cur->next();
   }
   sum += (sizeof(PerRegionTable*) * _max_fine_entries);
   sum += (_coarse_map.size_in_words() * HeapWordSize);
@@ -632,22 +727,24 @@
 }
 
 void OtherRegionsTable::clear_fcc() {
+  size_t hrs_idx = hr()->hrs_index();
   for (int i = 0; i < HeapRegionRemSet::num_par_rem_sets(); i++) {
-    _from_card_cache[i][hr()->hrs_index()] = -1;
+    _from_card_cache[i][hrs_idx] = -1;
   }
 }
 
 void OtherRegionsTable::clear() {
   MutexLockerEx x(&_m, Mutex::_no_safepoint_check_flag);
-  for (size_t i = 0; i < _max_fine_entries; i++) {
-    PerRegionTable* cur = _fine_grain_regions[i];
-    while (cur != NULL) {
-      PerRegionTable* nxt = cur->next();
-      PerRegionTable::free(cur);
-      cur = nxt;
-    }
-    _fine_grain_regions[i] = NULL;
+  // if there are no entries, skip this step
+  if (_first_all_fine_prts != NULL) {
+    guarantee(_first_all_fine_prts != NULL && _last_all_fine_prts != NULL, "just checking");
+    PerRegionTable::bulk_free(_first_all_fine_prts, _last_all_fine_prts);
+    memset(_fine_grain_regions, 0, _max_fine_entries * sizeof(_fine_grain_regions[0]));
+  } else {
+    guarantee(_first_all_fine_prts == NULL && _last_all_fine_prts == NULL, "just checking");
   }
+
+  _first_all_fine_prts = _last_all_fine_prts = NULL;
   _sparse_table.clear();
   _coarse_map.clear();
   _n_fine_entries = 0;
@@ -686,12 +783,13 @@
   PerRegionTable** prev_addr = &_fine_grain_regions[ind];
   PerRegionTable* prt = *prev_addr;
   while (prt != NULL && prt->hr() != hr) {
-    prev_addr = prt->next_addr();
-    prt = prt->next();
+    prev_addr = prt->collision_list_next_addr();
+    prt = prt->collision_list_next();
   }
   if (prt != NULL) {
     assert(prt->hr() == hr, "Loop postcondition.");
-    *prev_addr = prt->next();
+    *prev_addr = prt->collision_list_next();
+    unlink_from_all(prt);
     PerRegionTable::free(prt);
     _n_fine_entries--;
     return true;
@@ -793,7 +891,6 @@
       G1CollectedHeap::heap()->bot_shared()->address_for_index(card_index);
     gclog_or_tty->print_cr("  Card " PTR_FORMAT, card_start);
   }
-
   if (iter.n_yielded() != occupied()) {
     gclog_or_tty->print_cr("Yielded disagrees with occupied:");
     gclog_or_tty->print_cr("  %6d yielded (%6d coarse, %6d fine).",
@@ -905,7 +1002,7 @@
   while (!fine_has_next()) {
     if (_cur_region_cur_card == (size_t) HeapRegion::CardsPerRegion) {
       _cur_region_cur_card = 0;
-      _fine_cur_prt = _fine_cur_prt->next();
+      _fine_cur_prt = _fine_cur_prt->collision_list_next();
     }
     if (_fine_cur_prt == NULL) {
       fine_find_next_non_null_prt();
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/heapRegionRemSet.hpp
--- a/hotspot/src/share/vm/gc_implementation/g1/heapRegionRemSet.hpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegionRemSet.hpp	Fri Jul 27 21:41:17 2012 -0700
@@ -82,6 +82,14 @@
   PerRegionTable** _fine_grain_regions;
   size_t           _n_fine_entries;
 
+  // The fine grain remembered sets are doubly linked together using
+  // their 'next' and 'prev' fields.
+  // This allows fast bulk freeing of all the fine grain remembered
+  // set entries, and fast finding of all of them without iterating
+  // over the _fine_grain_regions table.
+  PerRegionTable * _first_all_fine_prts;
+  PerRegionTable * _last_all_fine_prts;
+
   // Used to sample a subset of the fine grain PRTs to determine which
   // PRT to evict and coarsen.
   size_t        _fine_eviction_start;
@@ -114,6 +122,11 @@
   static size_t _from_card_cache_max_regions;
   static size_t _from_card_cache_mem_size;
 
+  // link/add the given fine grain remembered set into the "all" list
+  void link_to_all(PerRegionTable * prt);
+  // unlink/remove the given fine grain remembered set into the "all" list
+  void unlink_from_all(PerRegionTable * prt);
+
 public:
   OtherRegionsTable(HeapRegion* hr);
 
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.cpp
--- a/hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.cpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.cpp	Fri Jul 27 21:41:17 2012 -0700
@@ -35,14 +35,6 @@
   _unrealistically_long_length = len;
 }
 
-uint HeapRegionSetBase::calculate_region_num(HeapRegion* hr) {
-  assert(hr->startsHumongous(), "pre-condition");
-  assert(hr->capacity() % HeapRegion::GrainBytes == 0, "invariant");
-  uint region_num = (uint) (hr->capacity() >> HeapRegion::LogOfHRGrainBytes);
-  assert(region_num > 0, "sanity");
-  return region_num;
-}
-
 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(),
@@ -152,11 +144,7 @@
   guarantee(verify_region(hr, this), hrs_ext_msg(this, "region verification"));
 
   _calc_length               += 1;
-  if (!hr->isHumongous()) {
-    _calc_region_num         += 1;
-  } else {
-    _calc_region_num         += calculate_region_num(hr);
-  }
+  _calc_region_num           += hr->region_num();
   _calc_total_capacity_bytes += hr->capacity();
   _calc_total_used_bytes     += hr->used();
 }
@@ -292,7 +280,7 @@
     assert(length() >  0 && _tail != NULL, hrs_ext_msg(this, "invariant"));
     from_list->_tail->set_next(_head);
   } else {
-    assert(length() == 0 && _head == NULL, hrs_ext_msg(this, "invariant"));
+    assert(length() == 0 && _tail == NULL, hrs_ext_msg(this, "invariant"));
     _tail = from_list->_tail;
   }
   _head = from_list->_head;
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.hpp
--- a/hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.hpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.hpp	Fri Jul 27 21:41:17 2012 -0700
@@ -62,8 +62,6 @@
   friend class VMStructs;
 
 protected:
-  static uint calculate_region_num(HeapRegion* hr);
-
   static uint _unrealistically_long_length;
 
   // The number of regions added to the set. If the set contains
diff -r 2f94212bcbe3 -r f8f2cc6553cf hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.inline.hpp
--- a/hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.inline.hpp	Fri Jul 27 16:51:44 2012 -0700
+++ b/hotspot/src/share/vm/gc_implementation/g1/heapRegionSet.inline.hpp	Fri Jul 27 21:41:17 2012 -0700
@@ -33,11 +33,7 @@
   // Assumes the caller has already verified the region.
 
   _length           += 1;
-  if (!hr->isHumongous()) {
-    _region_num     += 1;
-  } else {
-    _region_num     += calculate_region_num(hr);
-  }
+  _region_num       += hr->region_num();
   _total_used_bytes += hr->used();
 }
 
@@ -54,12 +50,7 @@
   assert(_length > 0, hrs_ext_msg(this, "pre-condition"));
   _length -= 1;
 
-  uint region_num_diff;
-  if (!hr->isHumongous()) {
-    region_num_diff = 1;
-  } else {
-    region_num_diff = calculate_region_num(hr);
-  }
+  uint region_num_diff = hr->region_num();
   assert(region_num_diff <= _region_num,
          hrs_err_msg("[%s] region's region num: %u "
                      "should be <= region num: %u",