Use the card table to speed up the GSS collector.

Scan only dirty cards, as opposed to the whole space, to find
references from the non-moving spaces to the bump pointer spaces at
bump pointer space only collections.

With this change, the Ritz MemAllocTest speeds up by 8-10% on host and
2-3% on N4. The Ritz EvaluateFibonacci speeds up by 8% and its average
pause time is reduced by 43% on N4.

Bug: 11650816
Change-Id: I1eefe75776bc37e24673b301ffa65a25f9bd4cde

10 files changed, 444 insertions, 15 deletions

diff --git a/runtime/Android.mk b/runtime/Android.mk
index 115363478c..cca7d03031 100644
--- a/runtime/Android.mk
+++ b/runtime/Android.mk
@@ -50,6 +50,7 @@ LIBART_COMMON_SRC_FILES := \
 	gc/accounting/gc_allocator.cc \
 	gc/accounting/heap_bitmap.cc \
 	gc/accounting/mod_union_table.cc \
+	gc/accounting/remembered_set.cc \
 	gc/accounting/space_bitmap.cc \
 	gc/collector/garbage_collector.cc \
 	gc/collector/immune_region.cc \
diff --git a/runtime/gc/accounting/remembered_set.cc b/runtime/gc/accounting/remembered_set.cc
new file mode 100644
index 0000000000..e6508dc1c7
--- /dev/null
+++ b/runtime/gc/accounting/remembered_set.cc
@@ -0,0 +1,164 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "remembered_set.h"
+
+#include "base/stl_util.h"
+#include "card_table-inl.h"
+#include "heap_bitmap.h"
+#include "gc/collector/mark_sweep.h"
+#include "gc/collector/mark_sweep-inl.h"
+#include "gc/collector/semi_space.h"
+#include "gc/heap.h"
+#include "gc/space/space.h"
+#include "mirror/art_field-inl.h"
+#include "mirror/object-inl.h"
+#include "mirror/class-inl.h"
+#include "mirror/object_array-inl.h"
+#include "space_bitmap-inl.h"
+#include "thread.h"
+#include "UniquePtr.h"
+
+namespace art {
+namespace gc {
+namespace accounting {
+
+class RememberedSetCardVisitor {
+ public:
+  explicit RememberedSetCardVisitor(RememberedSet::CardSet* const dirty_cards)
+      : dirty_cards_(dirty_cards) {}
+
+  void operator()(byte* card, byte expected_value, byte new_value) const {
+    if (expected_value == CardTable::kCardDirty) {
+      dirty_cards_->insert(card);
+    }
+  }
+
+ private:
+  RememberedSet::CardSet* const dirty_cards_;
+};
+
+void RememberedSet::ClearCards() {
+  CardTable* card_table = GetHeap()->GetCardTable();
+  RememberedSetCardVisitor card_visitor(&dirty_cards_);
+  // Clear dirty cards in the space and insert them into the dirty card set.
+  card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), card_visitor);
+}
+
+class RememberedSetReferenceVisitor {
+ public:
+  RememberedSetReferenceVisitor(MarkObjectCallback* callback, space::ContinuousSpace* target_space,
+                                bool* const contains_reference_to_target_space, void* arg)
+      : callback_(callback), target_space_(target_space), arg_(arg),
+        contains_reference_to_target_space_(contains_reference_to_target_space) {}
+
+  void operator()(mirror::Object* obj, mirror::Object* ref,
+                  const MemberOffset& offset, bool /* is_static */) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    if (ref != nullptr) {
+      if (target_space_->HasAddress(ref)) {
+        *contains_reference_to_target_space_ = true;
+        mirror::Object* new_ref = callback_(ref, arg_);
+        DCHECK(!target_space_->HasAddress(new_ref));
+        if (new_ref != ref) {
+          obj->SetFieldObjectWithoutWriteBarrier<false>(offset, new_ref, false);
+        }
+      }
+    }
+  }
+
+ private:
+  MarkObjectCallback* const callback_;
+  space::ContinuousSpace* const target_space_;
+  void* const arg_;
+  bool* const contains_reference_to_target_space_;
+};
+
+class RememberedSetObjectVisitor {
+ public:
+  RememberedSetObjectVisitor(MarkObjectCallback* callback, space::ContinuousSpace* target_space,
+                             bool* const contains_reference_to_target_space, void* arg)
+      : callback_(callback), target_space_(target_space), arg_(arg),
+        contains_reference_to_target_space_(contains_reference_to_target_space) {}
+
+  void operator()(mirror::Object* obj) const EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    DCHECK(obj != NULL);
+    RememberedSetReferenceVisitor ref_visitor(callback_, target_space_,
+                                              contains_reference_to_target_space_, arg_);
+    collector::MarkSweep::VisitObjectReferences(obj, ref_visitor, true);
+  }
+
+ private:
+  MarkObjectCallback* const callback_;
+  space::ContinuousSpace* const target_space_;
+  void* const arg_;
+  bool* const contains_reference_to_target_space_;
+};
+
+void RememberedSet::UpdateAndMarkReferences(MarkObjectCallback* callback,
+                                            space::ContinuousSpace* target_space, void* arg) {
+  CardTable* card_table = heap_->GetCardTable();
+  bool contains_reference_to_target_space = false;
+  RememberedSetObjectVisitor obj_visitor(callback, target_space,
+                                         &contains_reference_to_target_space, arg);
+  SpaceBitmap* bitmap = space_->GetLiveBitmap();
+  CardSet remove_card_set;
+  for (byte* const card_addr : dirty_cards_) {
+    contains_reference_to_target_space = false;
+    uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr));
+    DCHECK(space_->HasAddress(reinterpret_cast<mirror::Object*>(start)));
+    bitmap->VisitMarkedRange(start, start + CardTable::kCardSize, obj_visitor);
+    if (!contains_reference_to_target_space) {
+      // It was in the dirty card set, but it didn't actually contain
+      // a reference to the target space. So, remove it from the dirty
+      // card set so we won't have to scan it again (unless it gets
+      // dirty again.)
+      remove_card_set.insert(card_addr);
+    }
+  }
+
+  // Remove the cards that didn't contain a reference to the target
+  // space from the dirty card set.
+  for (byte* const card_addr : remove_card_set) {
+    DCHECK(dirty_cards_.find(card_addr) != dirty_cards_.end());
+    dirty_cards_.erase(card_addr);
+  }
+}
+
+void RememberedSet::Dump(std::ostream& os) {
+  CardTable* card_table = heap_->GetCardTable();
+  os << "RememberedSet dirty cards: [";
+  for (const byte* card_addr : dirty_cards_) {
+    auto start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr));
+    auto end = start + CardTable::kCardSize;
+    os << reinterpret_cast<void*>(start) << "-" << reinterpret_cast<void*>(end) << "\n";
+  }
+  os << "]";
+}
+
+void RememberedSet::AssertAllDirtyCardsAreWithinSpace() const {
+  CardTable* card_table = heap_->GetCardTable();
+  for (const byte* card_addr : dirty_cards_) {
+    auto start = reinterpret_cast<byte*>(card_table->AddrFromCard(card_addr));
+    auto end = start + CardTable::kCardSize;
+    DCHECK(space_->Begin() <= start && end <= space_->End());
+  }
+}
+
+}  // namespace accounting
+}  // namespace gc
+}  // namespace art
diff --git a/runtime/gc/accounting/remembered_set.h b/runtime/gc/accounting/remembered_set.h
new file mode 100644
index 0000000000..92feeb1f04
--- /dev/null
+++ b/runtime/gc/accounting/remembered_set.h
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_GC_ACCOUNTING_REMEMBERED_SET_H_
+#define ART_RUNTIME_GC_ACCOUNTING_REMEMBERED_SET_H_
+
+#include "gc_allocator.h"
+#include "globals.h"
+#include "object_callbacks.h"
+#include "safe_map.h"
+
+#include <set>
+#include <vector>
+
+namespace art {
+namespace gc {
+
+namespace collector {
+  class MarkSweep;
+}  // namespace collector
+namespace space {
+  class ContinuousSpace;
+}  // namespace space
+
+class Heap;
+
+namespace accounting {
+
+// The remembered set keeps track of cards that may contain references
+// from the free list spaces to the bump pointer spaces.
+class RememberedSet {
+ public:
+  typedef std::set<byte*, std::less<byte*>, GcAllocator<byte*> > CardSet;
+
+  explicit RememberedSet(const std::string& name, Heap* heap, space::ContinuousSpace* space)
+      : name_(name), heap_(heap), space_(space) {}
+
+  // Clear dirty cards and add them to the dirty card set.
+  void ClearCards();
+
+  // Mark through all references to the target space.
+  void UpdateAndMarkReferences(MarkObjectCallback* callback,
+                               space::ContinuousSpace* target_space, void* arg)
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  void Dump(std::ostream& os);
+
+  space::ContinuousSpace* GetSpace() {
+    return space_;
+  }
+  Heap* GetHeap() const {
+    return heap_;
+  }
+  const std::string& GetName() const {
+    return name_;
+  }
+  void AssertAllDirtyCardsAreWithinSpace() const;
+
+ private:
+  const std::string name_;
+  Heap* const heap_;
+  space::ContinuousSpace* const space_;
+
+  CardSet dirty_cards_;
+};
+
+}  // namespace accounting
+}  // namespace gc
+}  // namespace art
+
+#endif  // ART_RUNTIME_GC_ACCOUNTING_REMEMBERED_SET_H_
diff --git a/runtime/gc/collector/immune_region.cc b/runtime/gc/collector/immune_region.cc
index 9e6538456f..70a62133a6 100644
--- a/runtime/gc/collector/immune_region.cc
+++ b/runtime/gc/collector/immune_region.cc
@@ -56,9 +56,14 @@ bool ImmuneRegion::AddContinuousSpace(space::ContinuousSpace* space) {
 }
 
 bool ImmuneRegion::ContainsSpace(const space::ContinuousSpace* space) const {
-  return
+  bool contains =
       begin_ <= reinterpret_cast<mirror::Object*>(space->Begin()) &&
       end_ >= reinterpret_cast<mirror::Object*>(space->Limit());
+  if (kIsDebugBuild && contains) {
+    // A bump pointer space shoult not be in the immune region.
+    DCHECK(space->GetType() != space::kSpaceTypeBumpPointerSpace);
+  }
+  return contains;
 }
 
 }  // namespace collector
diff --git a/runtime/gc/collector/mark_sweep.cc b/runtime/gc/collector/mark_sweep.cc
index 4f3ad32546..fe5a75f406 100644
--- a/runtime/gc/collector/mark_sweep.cc
+++ b/runtime/gc/collector/mark_sweep.cc
@@ -201,7 +201,7 @@ void MarkSweep::PreCleanCards() {
     Thread* self = Thread::Current();
     CHECK(!Locks::mutator_lock_->IsExclusiveHeld(self));
     // Process dirty cards and add dirty cards to mod union tables, also ages cards.
-    heap_->ProcessCards(timings_);
+    heap_->ProcessCards(timings_, false);
     // The checkpoint root marking is required to avoid a race condition which occurs if the
     // following happens during a reference write:
     // 1. mutator dirties the card (write barrier)
@@ -241,7 +241,7 @@ void MarkSweep::MarkingPhase() {
   FindDefaultMarkBitmap();
 
   // Process dirty cards and add dirty cards to mod union tables.
-  heap_->ProcessCards(timings_);
+  heap_->ProcessCards(timings_, false);
 
   // Need to do this before the checkpoint since we don't want any threads to add references to
   // the live stack during the recursive mark.
diff --git a/runtime/gc/collector/semi_space.cc b/runtime/gc/collector/semi_space.cc
index 23b155cffc..5b9c39795c 100644
--- a/runtime/gc/collector/semi_space.cc
+++ b/runtime/gc/collector/semi_space.cc
@@ -27,6 +27,7 @@
 #include "base/timing_logger.h"
 #include "gc/accounting/heap_bitmap.h"
 #include "gc/accounting/mod_union_table.h"
+#include "gc/accounting/remembered_set.h"
 #include "gc/accounting/space_bitmap-inl.h"
 #include "gc/heap.h"
 #include "gc/space/bump_pointer_space.h"
@@ -182,7 +183,7 @@ void SemiSpace::MarkingPhase() {
   // Assume the cleared space is already empty.
   BindBitmaps();
   // Process dirty cards and add dirty cards to mod-union tables.
-  heap_->ProcessCards(timings_);
+  heap_->ProcessCards(timings_, kUseRememberedSet && generational_);
   // Clear the whole card table since we can not get any additional dirty cards during the
   // paused GC. This saves memory but only works for pause the world collectors.
   timings_.NewSplit("ClearCardTable");
@@ -214,13 +215,29 @@ void SemiSpace::UpdateAndMarkModUnion() {
                                      "UpdateAndMarkImageModUnionTable",
                                      &timings_);
         table->UpdateAndMarkReferences(MarkObjectCallback, this);
+      } else if (heap_->FindRememberedSetFromSpace(space) != nullptr) {
+        DCHECK(kUseRememberedSet);
+        // If a bump pointer space only collection, the non-moving
+        // space is added to the immune space. The non-moving space
+        // doesn't have a mod union table, but has a remembered
+        // set. Its dirty cards will be scanned later in
+        // MarkReachableObjects().
+        DCHECK(generational_ && !whole_heap_collection_ &&
+               (space == heap_->GetNonMovingSpace() || space == heap_->GetPrimaryFreeListSpace()))
+            << "Space " << space->GetName() << " "
+            << "generational_=" << generational_ << " "
+            << "whole_heap_collection_=" << whole_heap_collection_ << " ";
       } else {
+        DCHECK(!kUseRememberedSet);
         // If a bump pointer space only collection, the non-moving
         // space is added to the immune space. But the non-moving
         // space doesn't have a mod union table. Instead, its live
         // bitmap will be scanned later in MarkReachableObjects().
         DCHECK(generational_ && !whole_heap_collection_ &&
-               (space == heap_->GetNonMovingSpace() || space == heap_->GetPrimaryFreeListSpace()));
+               (space == heap_->GetNonMovingSpace() || space == heap_->GetPrimaryFreeListSpace()))
+            << "Space " << space->GetName() << " "
+            << "generational_=" << generational_ << " "
+            << "whole_heap_collection_=" << whole_heap_collection_ << " ";
       }
     }
   }
@@ -240,6 +257,42 @@ class SemiSpaceScanObjectVisitor {
   SemiSpace* const semi_space_;
 };
 
+// Used to verify that there's no references to the from-space.
+class SemiSpaceVerifyNoFromSpaceReferencesVisitor {
+ public:
+  explicit SemiSpaceVerifyNoFromSpaceReferencesVisitor(space::ContinuousMemMapAllocSpace* from_space) :
+      from_space_(from_space) {}
+
+  void operator()(Object* obj, Object* ref, const MemberOffset& offset, bool /* is_static */)
+      const ALWAYS_INLINE {
+    if (from_space_->HasAddress(ref)) {
+      Runtime::Current()->GetHeap()->DumpObject(LOG(INFO), obj);
+    }
+    DCHECK(!from_space_->HasAddress(ref));
+  }
+ private:
+  space::ContinuousMemMapAllocSpace* from_space_;
+};
+
+void SemiSpace::VerifyNoFromSpaceReferences(Object* obj) {
+  DCHECK(obj != NULL);
+  DCHECK(!from_space_->HasAddress(obj)) << "Scanning object " << obj << " in from space";
+  SemiSpaceVerifyNoFromSpaceReferencesVisitor visitor(from_space_);
+  MarkSweep::VisitObjectReferences(obj, visitor, kMovingClasses);
+}
+
+class SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor {
+ public:
+  explicit SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor(SemiSpace* ss) : semi_space_(ss) {}
+  void operator()(Object* obj) const
+      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
+    DCHECK(obj != nullptr);
+    semi_space_->VerifyNoFromSpaceReferences(obj);
+  }
+ private:
+  SemiSpace* const semi_space_;
+};
+
 void SemiSpace::MarkReachableObjects() {
   timings_.StartSplit("MarkStackAsLive");
   accounting::ObjectStack* live_stack = heap_->GetLiveStack();
@@ -250,18 +303,36 @@ void SemiSpace::MarkReachableObjects() {
   for (auto& space : heap_->GetContinuousSpaces()) {
     // If the space is immune and has no mod union table (the
     // non-moving space when the bump pointer space only collection is
-    // enabled,) then we need to scan its live bitmap as roots
+    // enabled,) then we need to scan its live bitmap or dirty cards as roots
     // (including the objects on the live stack which have just marked
     // in the live bitmap above in MarkAllocStackAsLive().)
     if (immune_region_.ContainsSpace(space) &&
         heap_->FindModUnionTableFromSpace(space) == nullptr) {
       DCHECK(generational_ && !whole_heap_collection_ &&
              (space == GetHeap()->GetNonMovingSpace() || space == GetHeap()->GetPrimaryFreeListSpace()));
-      accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap();
-      SemiSpaceScanObjectVisitor visitor(this);
-      live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
-                                    reinterpret_cast<uintptr_t>(space->End()),
-                                    visitor);
+      accounting::RememberedSet* rem_set = heap_->FindRememberedSetFromSpace(space);
+      if (kUseRememberedSet) {
+        DCHECK(rem_set != nullptr);
+        rem_set->UpdateAndMarkReferences(MarkObjectCallback, from_space_, this);
+        if (kIsDebugBuild) {
+          // Verify that there are no from-space references that
+          // remain in the space, that is, the remembered set (and the
+          // card table) didn't miss any from-space references in the
+          // space.
+          accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap();
+          SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor visitor(this);
+          live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
+                                        reinterpret_cast<uintptr_t>(space->End()),
+                                        visitor);
+        }
+      } else {
+        DCHECK(rem_set == nullptr);
+        accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap();
+        SemiSpaceScanObjectVisitor visitor(this);
+        live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
+                                      reinterpret_cast<uintptr_t>(space->End()),
+                                      visitor);
+      }
     }
   }
 
@@ -447,6 +518,10 @@ mirror::Object* SemiSpace::MarkNonForwardedObject(mirror::Object* obj) {
     } else {
       GetHeap()->num_bytes_allocated_.FetchAndAdd(bytes_promoted);
       bytes_promoted_ += bytes_promoted;
+      // Dirty the card at the destionation as it may contain
+      // references (including the class pointer) to the bump pointer
+      // space.
+      GetHeap()->WriteBarrierEveryFieldOf(forward_address);
       // Handle the bitmaps marking.
       accounting::SpaceBitmap* live_bitmap = promo_dest_space->GetLiveBitmap();
       DCHECK(live_bitmap != nullptr);
diff --git a/runtime/gc/collector/semi_space.h b/runtime/gc/collector/semi_space.h
index be7ec05f2a..08bfbc485d 100644
--- a/runtime/gc/collector/semi_space.h
+++ b/runtime/gc/collector/semi_space.h
@@ -63,6 +63,9 @@ namespace collector {
 
 class SemiSpace : public GarbageCollector {
  public:
+  // If true, use remembered sets in the generational mode.
+  static constexpr bool kUseRememberedSet = true;
+
   explicit SemiSpace(Heap* heap, bool generational = false,
                      const std::string& name_prefix = "");
 
@@ -100,6 +103,9 @@ class SemiSpace : public GarbageCollector {
   void ScanObject(mirror::Object* obj)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
 
+  void VerifyNoFromSpaceReferences(mirror::Object* obj)
+      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
+
   // Marks the root set at the start of a garbage collection.
   void MarkRoots()
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
diff --git a/runtime/gc/heap-inl.h b/runtime/gc/heap-inl.h
index 533e5dfedc..6cc44c9e88 100644
--- a/runtime/gc/heap-inl.h
+++ b/runtime/gc/heap-inl.h
@@ -20,6 +20,8 @@
 #include "heap.h"
 
 #include "debugger.h"
+#include "gc/accounting/card_table-inl.h"
+#include "gc/collector/semi_space.h"
 #include "gc/space/bump_pointer_space-inl.h"
 #include "gc/space/dlmalloc_space-inl.h"
 #include "gc/space/large_object_space.h"
@@ -75,6 +77,18 @@ inline mirror::Object* Heap::AllocObjectWithAllocator(Thread* self, mirror::Clas
     obj->SetBrooksPointer(obj);
     obj->AssertSelfBrooksPointer();
   }
+  if (collector::SemiSpace::kUseRememberedSet && UNLIKELY(allocator == kAllocatorTypeNonMoving)) {
+    // (Note this if statement will be constant folded away for the
+    // fast-path quick entry points.) Because SetClass() has no write
+    // barrier, if a non-moving space allocation, we need a write
+    // barrier as the class pointer may point to the bump pointer
+    // space (where the class pointer is an "old-to-young" reference,
+    // though rare) under the GSS collector with the remembered set
+    // enabled. We don't need this for kAllocatorTypeRosAlloc/DlMalloc
+    // cases because we don't directly allocate into the main alloc
+    // space (besides promotions) under the SS/GSS collector.
+    WriteBarrierField(obj, mirror::Object::ClassOffset(), klass);
+  }
   pre_fence_visitor(obj, usable_size);
   if (kIsDebugBuild && Runtime::Current()->IsStarted()) {
     CHECK_LE(obj->SizeOf(), usable_size);
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 45904ffca0..e8ee62f1dd 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -33,6 +33,7 @@
 #include "gc/accounting/heap_bitmap-inl.h"
 #include "gc/accounting/mod_union_table.h"
 #include "gc/accounting/mod_union_table-inl.h"
+#include "gc/accounting/remembered_set.h"
 #include "gc/accounting/space_bitmap-inl.h"
 #include "gc/collector/mark_sweep-inl.h"
 #include "gc/collector/partial_mark_sweep.h"
@@ -161,7 +162,8 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
   } else {
     if (kMovingCollector) {
       // We are the zygote, use bump pointer allocation + semi space collector.
-      desired_collector_type_ = kCollectorTypeSS;
+      bool generational = post_zygote_collector_type_ == kCollectorTypeGSS;
+      desired_collector_type_ = generational ? kCollectorTypeGSS : kCollectorTypeSS;
     } else {
       desired_collector_type_ = post_zygote_collector_type_;
     }
@@ -279,6 +281,13 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
   CHECK(mod_union_table != nullptr) << "Failed to create image mod-union table";
   AddModUnionTable(mod_union_table);
 
+  if (collector::SemiSpace::kUseRememberedSet) {
+    accounting::RememberedSet* non_moving_space_rem_set =
+        new accounting::RememberedSet("Non-moving space remembered set", this, non_moving_space_);
+    CHECK(non_moving_space_rem_set != nullptr) << "Failed to create non-moving space remembered set";
+    AddRememberedSet(non_moving_space_rem_set);
+  }
+
   // TODO: Count objects in the image space here.
   num_bytes_allocated_ = 0;
 
@@ -1469,7 +1478,7 @@ void Heap::ChangeCollector(CollectorType collector_type) {
 // Special compacting collector which uses sub-optimal bin packing to reduce zygote space size.
 class ZygoteCompactingCollector FINAL : public collector::SemiSpace {
  public:
-  explicit ZygoteCompactingCollector(gc::Heap* heap) : SemiSpace(heap, "zygote collector"),
+  explicit ZygoteCompactingCollector(gc::Heap* heap) : SemiSpace(heap, false, "zygote collector"),
       bin_live_bitmap_(nullptr), bin_mark_bitmap_(nullptr) {
   }
 
@@ -1618,6 +1627,16 @@ void Heap::PreZygoteFork() {
   // Remove the old space before creating the zygote space since creating the zygote space sets
   // the old alloc space's bitmaps to nullptr.
   RemoveSpace(old_alloc_space);
+  if (collector::SemiSpace::kUseRememberedSet) {
+    // Sanity bound check.
+    FindRememberedSetFromSpace(old_alloc_space)->AssertAllDirtyCardsAreWithinSpace();
+    // Remove the remembered set for the now zygote space (the old
+    // non-moving space). Note now that we have compacted objects into
+    // the zygote space, the data in the remembered set is no longer
+    // needed. The zygote space will instead have a mod-union table
+    // from this point on.
+    RemoveRememberedSet(old_alloc_space);
+  }
   space::ZygoteSpace* zygote_space = old_alloc_space->CreateZygoteSpace("alloc space",
                                                                         low_memory_mode_,
                                                                         &main_space_);
@@ -1640,6 +1659,13 @@ void Heap::PreZygoteFork() {
       new accounting::ModUnionTableCardCache("zygote space mod-union table", this, zygote_space);
   CHECK(mod_union_table != nullptr) << "Failed to create zygote space mod-union table";
   AddModUnionTable(mod_union_table);
+  if (collector::SemiSpace::kUseRememberedSet) {
+    // Add a new remembered set for the new main space.
+    accounting::RememberedSet* main_space_rem_set =
+        new accounting::RememberedSet("Main space remembered set", this, main_space_);
+    CHECK(main_space_rem_set != nullptr) << "Failed to create main space remembered set";
+    AddRememberedSet(main_space_rem_set);
+  }
   // Can't use RosAlloc for non moving space due to thread local buffers.
   // TODO: Non limited space for non-movable objects?
   MemMap* mem_map = post_zygote_non_moving_space_mem_map_.release();
@@ -1650,6 +1676,15 @@ void Heap::PreZygoteFork() {
   CHECK(new_non_moving_space != nullptr) << "Failed to create new non-moving space";
   new_non_moving_space->SetFootprintLimit(new_non_moving_space->Capacity());
   non_moving_space_ = new_non_moving_space;
+  if (collector::SemiSpace::kUseRememberedSet) {
+    // Add a new remembered set for the post-zygote non-moving space.
+    accounting::RememberedSet* post_zygote_non_moving_space_rem_set =
+        new accounting::RememberedSet("Post-zygote non-moving space remembered set", this,
+                                      non_moving_space_);
+    CHECK(post_zygote_non_moving_space_rem_set != nullptr)
+        << "Failed to create post-zygote non-moving space remembered set";
+    AddRememberedSet(post_zygote_non_moving_space_rem_set);
+  }
 }
 
 void Heap::FlushAllocStack() {
@@ -2034,6 +2069,11 @@ bool Heap::VerifyHeapReferences() {
       accounting::ModUnionTable* mod_union_table = table_pair.second;
       mod_union_table->Dump(LOG(ERROR) << mod_union_table->GetName() << ": ");
     }
+    // Dump remembered sets.
+    for (const auto& table_pair : remembered_sets_) {
+      accounting::RememberedSet* remembered_set = table_pair.second;
+      remembered_set->Dump(LOG(ERROR) << remembered_set->GetName() << ": ");
+    }
     DumpSpaces();
     return false;
   }
@@ -2185,15 +2225,29 @@ accounting::ModUnionTable* Heap::FindModUnionTableFromSpace(space::Space* space)
   return it->second;
 }
 
-void Heap::ProcessCards(TimingLogger& timings) {
+accounting::RememberedSet* Heap::FindRememberedSetFromSpace(space::Space* space) {
+  auto it = remembered_sets_.find(space);
+  if (it == remembered_sets_.end()) {
+    return nullptr;
+  }
+  return it->second;
+}
+
+void Heap::ProcessCards(TimingLogger& timings, bool use_rem_sets) {
   // Clear cards and keep track of cards cleared in the mod-union table.
   for (const auto& space : continuous_spaces_) {
     accounting::ModUnionTable* table = FindModUnionTableFromSpace(space);
+    accounting::RememberedSet* rem_set = FindRememberedSetFromSpace(space);
     if (table != nullptr) {
       const char* name = space->IsZygoteSpace() ? "ZygoteModUnionClearCards" :
           "ImageModUnionClearCards";
       TimingLogger::ScopedSplit split(name, &timings);
       table->ClearCards();
+    } else if (use_rem_sets && rem_set != nullptr) {
+      DCHECK(collector::SemiSpace::kUseRememberedSet && collector_type_ == kCollectorTypeGSS)
+          << static_cast<int>(collector_type_);
+      TimingLogger::ScopedSplit split("AllocSpaceRemSetClearCards", &timings);
+      rem_set->ClearCards();
     } else if (space->GetType() != space::kSpaceTypeBumpPointerSpace) {
       TimingLogger::ScopedSplit split("AllocSpaceClearCards", &timings);
       // No mod union table for the AllocSpace. Age the cards so that the GC knows that these cards
@@ -2694,5 +2748,22 @@ void Heap::CheckPreconditionsForAllocObject(mirror::Class* c, size_t byte_count)
   CHECK_GE(byte_count, sizeof(mirror::Object));
 }
 
+void Heap::AddRememberedSet(accounting::RememberedSet* remembered_set) {
+  CHECK(remembered_set != nullptr);
+  space::Space* space = remembered_set->GetSpace();
+  CHECK(space != nullptr);
+  CHECK(remembered_sets_.find(space) == remembered_sets_.end());
+  remembered_sets_.Put(space, remembered_set);
+  CHECK(remembered_sets_.find(space) != remembered_sets_.end());
+}
+
+void Heap::RemoveRememberedSet(space::Space* space) {
+  CHECK(space != nullptr);
+  auto it = remembered_sets_.find(space);
+  CHECK(it != remembered_sets_.end());
+  remembered_sets_.erase(it);
+  CHECK(remembered_sets_.find(space) == remembered_sets_.end());
+}
+
 }  // namespace gc
 }  // namespace art
diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h
index 1e0a59649c..de20a4ecbd 100644
--- a/runtime/gc/heap.h
+++ b/runtime/gc/heap.h
@@ -56,6 +56,7 @@ namespace accounting {
   class HeapBitmap;
   class ModUnionTable;
   class ObjectSet;
+  class RememberedSet;
 }  // namespace accounting
 
 namespace collector {
@@ -541,6 +542,10 @@ class Heap {
   accounting::ModUnionTable* FindModUnionTableFromSpace(space::Space* space);
   void AddModUnionTable(accounting::ModUnionTable* mod_union_table);
 
+  accounting::RememberedSet* FindRememberedSetFromSpace(space::Space* space);
+  void AddRememberedSet(accounting::RememberedSet* remembered_set);
+  void RemoveRememberedSet(space::Space* space);
+
   bool IsCompilingBoot() const;
   bool HasImageSpace() const;
 
@@ -660,7 +665,7 @@ class Heap {
   void SwapStacks(Thread* self);
 
   // Clear cards and update the mod union table.
-  void ProcessCards(TimingLogger& timings);
+  void ProcessCards(TimingLogger& timings, bool use_rem_sets);
 
   // Signal the heap trim daemon that there is something to do, either a heap transition or heap
   // trim.
@@ -701,6 +706,9 @@ class Heap {
   // A mod-union table remembers all of the references from the it's space to other spaces.
   SafeMap<space::Space*, accounting::ModUnionTable*> mod_union_tables_;
 
+  // A remembered set remembers all of the references from the it's space to the target space.
+  SafeMap<space::Space*, accounting::RememberedSet*> remembered_sets_;
+
   // Keep the free list allocator mem map lying around when we transition to background so that we
   // don't have to worry about virtual address space fragmentation.
   UniquePtr<MemMap> allocator_mem_map_;