--- a/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Mon Mar 09 11:32:57 2009 -0400
+++ b/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Tue Mar 10 00:47:05 2009 -0700
@@ -820,6 +820,40 @@
   }
 };
 
+class RebuildRSOutOfRegionClosure: public HeapRegionClosure {
+  G1CollectedHeap*   _g1h;
+  UpdateRSOopClosure _cl;
+  int                _worker_i;
+public:
+  RebuildRSOutOfRegionClosure(G1CollectedHeap* g1, int worker_i = 0) :
+    _cl(g1->g1_rem_set()->as_HRInto_G1RemSet(), worker_i),
+    _worker_i(worker_i),
+    _g1h(g1)
+  { }
+  bool doHeapRegion(HeapRegion* r) {
+    if (!r->continuesHumongous()) {
+      _cl.set_from(r);
+      r->oop_iterate(&_cl);
+    }
+    return false;
+  }
+};
+
+class ParRebuildRSTask: public AbstractGangTask {
+  G1CollectedHeap* _g1;
+public:
+  ParRebuildRSTask(G1CollectedHeap* g1)
+    : AbstractGangTask("ParRebuildRSTask"),
+      _g1(g1)
+  { }
+
+  void work(int i) {
+    RebuildRSOutOfRegionClosure rebuild_rs(_g1, i);
+    _g1->heap_region_par_iterate_chunked(&rebuild_rs, i,
+                                         HeapRegion::RebuildRSClaimValue);
+  }
+};
+
 void G1CollectedHeap::do_collection(bool full, bool clear_all_soft_refs,
                                     size_t word_size) {
   ResourceMark rm;
@@ -926,24 +960,35 @@
 
     reset_gc_time_stamp();
     // Since everything potentially moved, we will clear all remembered
-    // sets, and clear all cards.  Later we will also cards in the used
-    // portion of the heap after the resizing (which could be a shrinking.)
-    // We will also reset the GC time stamps of the regions.
+    // 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);
 
     // Resize the heap if necessary.
     resize_if_necessary_after_full_collection(full ? 0 : word_size);
 
-    // Since everything potentially moved, we will clear all remembered
-    // sets, but also dirty all cards corresponding to used regions.
-    PostMCRemSetInvalidateClosure rs_invalidate(mr_bs());
-    heap_region_iterate(&rs_invalidate);
     if (_cg1r->use_cache()) {
       _cg1r->clear_and_record_card_counts();
       _cg1r->clear_hot_cache();
     }
 
+    // Rebuild remembered sets of all regions.
+    if (ParallelGCThreads > 0) {
+      ParRebuildRSTask rebuild_rs_task(this);
+      assert(check_heap_region_claim_values(
+             HeapRegion::InitialClaimValue), "sanity check");
+      set_par_threads(workers()->total_workers());
+      workers()->run_task(&rebuild_rs_task);
+      set_par_threads(0);
+      assert(check_heap_region_claim_values(
+             HeapRegion::RebuildRSClaimValue), "sanity check");
+      reset_heap_region_claim_values();
+    } else {
+      RebuildRSOutOfRegionClosure rebuild_rs(this);
+      heap_region_iterate(&rebuild_rs);
+    }
+
     if (PrintGC) {
       print_size_transition(gclog_or_tty, g1h_prev_used, used(), capacity());
     }

--- a/src/share/vm/gc_implementation/g1/g1RemSet.cpp	Mon Mar 09 11:32:57 2009 -0400
+++ b/src/share/vm/gc_implementation/g1/g1RemSet.cpp	Tue Mar 10 00:47:05 2009 -0700
@@ -105,33 +105,6 @@
   _g1->heap_region_iterate(&rc);
 }
 
-class UpdateRSOopClosure: public OopClosure {
-  HeapRegion* _from;
-  HRInto_G1RemSet* _rs;
-  int _worker_i;
-public:
-  UpdateRSOopClosure(HRInto_G1RemSet* rs, int worker_i = 0) :
-    _from(NULL), _rs(rs), _worker_i(worker_i) {
-    guarantee(_rs != NULL, "Requires an HRIntoG1RemSet");
-  }
-
-  void set_from(HeapRegion* from) {
-    assert(from != NULL, "from region must be non-NULL");
-    _from = from;
-  }
-
-  virtual void do_oop(narrowOop* p) {
-    guarantee(false, "NYI");
-  }
-  virtual void do_oop(oop* p) {
-    assert(_from != NULL, "from region must be non-NULL");
-    _rs->par_write_ref(_from, p, _worker_i);
-  }
-  // Override: this closure is idempotent.
-  //  bool idempotent() { return true; }
-  bool apply_to_weak_ref_discovered_field() { return true; }
-};
-
 class UpdateRSOutOfRegionClosure: public HeapRegionClosure {
   G1CollectedHeap*    _g1h;
   ModRefBarrierSet*   _mr_bs;

--- a/src/share/vm/gc_implementation/g1/g1RemSet.hpp	Mon Mar 09 11:32:57 2009 -0400
+++ b/src/share/vm/gc_implementation/g1/g1RemSet.hpp	Tue Mar 10 00:47:05 2009 -0700
@@ -215,3 +215,27 @@
   int n() { return _n; };
   HeapWord* start_first() { return _start_first; }
 };
+
+class UpdateRSOopClosure: public OopClosure {
+  HeapRegion* _from;
+  HRInto_G1RemSet* _rs;
+  int _worker_i;
+public:
+  UpdateRSOopClosure(HRInto_G1RemSet* rs, int worker_i = 0) :
+    _from(NULL), _rs(rs), _worker_i(worker_i) {
+    guarantee(_rs != NULL, "Requires an HRIntoG1RemSet");
+  }
+
+  void set_from(HeapRegion* from) {
+    assert(from != NULL, "from region must be non-NULL");
+    _from = from;
+  }
+
+  virtual void do_oop(narrowOop* p);
+  virtual void do_oop(oop* p);
+
+  // Override: this closure is idempotent.
+  //  bool idempotent() { return true; }
+  bool apply_to_weak_ref_discovered_field() { return true; }
+};
+

--- a/src/share/vm/gc_implementation/g1/g1RemSet.inline.hpp	Mon Mar 09 11:32:57 2009 -0400
+++ b/src/share/vm/gc_implementation/g1/g1RemSet.inline.hpp	Tue Mar 10 00:47:05 2009 -0700
@@ -94,3 +94,12 @@
     }
   }
 }
+
+inline void UpdateRSOopClosure::do_oop(narrowOop* p) {
+  guarantee(false, "NYI");
+}
+
+inline void UpdateRSOopClosure::do_oop(oop* p) {
+  assert(_from != NULL, "from region must be non-NULL");
+  _rs->par_write_ref(_from, p, _worker_i);
+}

--- a/src/share/vm/gc_implementation/g1/heapRegion.hpp	Mon Mar 09 11:32:57 2009 -0400
+++ b/src/share/vm/gc_implementation/g1/heapRegion.hpp	Tue Mar 10 00:47:05 2009 -0700
@@ -318,7 +318,8 @@
     FinalCountClaimValue  = 1,
     NoteEndClaimValue     = 2,
     ScrubRemSetClaimValue = 3,
-    ParVerifyClaimValue   = 4
+    ParVerifyClaimValue   = 4,
+    RebuildRSClaimValue   = 5
   };
 
   // Concurrent refinement requires contiguous heap regions (in which TLABs