diff --git a/build/Android.common.mk b/build/Android.common.mk
index bf8f271..34e8627 100644
--- a/build/Android.common.mk
+++ b/build/Android.common.mk
@@ -350,6 +350,7 @@
 	src/mutex.h \
 	src/object.h \
 	src/thread.h \
+	src/space.h \
 	src/verifier/method_verifier.h
 
 LIBARTTEST_COMMON_SRC_FILES := \
@@ -379,6 +380,7 @@
 	src/reference_table_test.cc \
 	src/runtime_support_test.cc \
 	src/runtime_test.cc \
+	src/space_bitmap_test.cc \
 	src/space_test.cc \
 	src/utils_test.cc \
 	src/zip_archive_test.cc \
diff --git a/src/card_table.cc b/src/card_table.cc
index 758a889..6c127b6 100644
--- a/src/card_table.cc
+++ b/src/card_table.cc
@@ -88,16 +88,11 @@
   ANNOTATE_BENIGN_RACE_SIZED(begin, (end - begin), "writes to GC card table");
 }
 
-void CardTable::ClearNonImageSpaceCards(Heap* heap) {
+void CardTable::ClearSpaceCards(Space* space) {
   // TODO: clear just the range of the table that has been modified
-  const std::vector<Space*>& spaces = heap->GetSpaces();
-  for (size_t i = 0; i < spaces.size(); ++i) {
-    if (!spaces[i]->IsImageSpace()) {
-      byte* card_start = CardFromAddr(spaces[i]->Begin());
-      byte* card_end = CardFromAddr(spaces[i]->End());
-      memset(reinterpret_cast<void*>(card_start), GC_CARD_CLEAN, card_end - card_start);
-    }
-  }
+  byte* card_start = CardFromAddr(space->Begin());
+  byte* card_end = CardFromAddr(space->End()); // Make sure to round up.
+  memset(reinterpret_cast<void*>(card_start), GC_CARD_CLEAN, card_end - card_start);
 }
 
 void CardTable::ClearCardTable() {
@@ -117,30 +112,6 @@
   }
 }
 
-void CardTable::Scan(SpaceBitmap* bitmap, byte* scan_begin, byte* scan_end, Callback* visitor, void* arg) const {
-  DCHECK(bitmap->HasAddress(scan_begin));
-  DCHECK(bitmap->HasAddress(scan_end - 1));  // scan_end is the byte after the last byte we scan.
-  byte* card_cur = CardFromAddr(scan_begin);
-  byte* card_end = CardFromAddr(scan_end);
-  while (card_cur < card_end) {
-    while (card_cur < card_end && *card_cur == GC_CARD_CLEAN) {
-      card_cur++;
-    }
-    byte* run_start = card_cur;
-
-    while (card_cur < card_end && *card_cur == GC_CARD_DIRTY) {
-      card_cur++;
-    }
-    byte* run_end = card_cur;
-
-    if (run_start != run_end) {
-      bitmap->VisitRange(reinterpret_cast<uintptr_t>(AddrFromCard(run_start)),
-                                      reinterpret_cast<uintptr_t>(AddrFromCard(run_end)),
-                                      visitor, arg);
-    }
-  }
-}
-
 void CardTable::VerifyCardTable() {
   UNIMPLEMENTED(WARNING) << "Card table verification";
 }
diff --git a/src/card_table.h b/src/card_table.h
index ea46cfe..d065bed 100644
--- a/src/card_table.h
+++ b/src/card_table.h
@@ -20,11 +20,13 @@
 #include "globals.h"
 #include "logging.h"
 #include "mem_map.h"
+#include "space_bitmap.h"
 #include "UniquePtr.h"
 
 namespace art {
 
 class Heap;
+class Space;
 class SpaceBitmap;
 class Object;
 
@@ -70,9 +72,31 @@
     return biased_begin_;
   }
 
-  // For every dirty card between begin and end invoke the visitor with the specified argument
-  typedef void Callback(Object* obj, void* arg);
-  void Scan(SpaceBitmap* bitmap, byte* begin, byte* end, Callback* visitor, void* arg) const;
+  // For every dirty card between begin and end invoke the visitor with the specified argument.
+  template <typename Visitor>
+  void Scan(SpaceBitmap* bitmap, byte* scan_begin, byte* scan_end, const Visitor& visitor) const {
+    DCHECK(bitmap->HasAddress(scan_begin));
+    DCHECK(bitmap->HasAddress(scan_end - 1));  // scan_end is the byte after the last byte we scan.
+    byte* card_cur = CardFromAddr(scan_begin);
+    byte* card_end = CardFromAddr(scan_end);
+    while (card_cur < card_end) {
+      while (card_cur < card_end && *card_cur == GC_CARD_CLEAN) {
+        card_cur++;
+      }
+      byte* run_start = card_cur;
+
+      while (card_cur < card_end && *card_cur == GC_CARD_DIRTY) {
+        card_cur++;
+      }
+      byte* run_end = card_cur;
+
+      if (run_start != run_end) {
+        uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(run_start));
+        uintptr_t end = reinterpret_cast<uintptr_t>(AddrFromCard(run_end));
+        bitmap->VisitMarkedRange(start, end, visitor);
+      }
+    }
+  }
 
   // Assertion used to check the given address is covered by the card table
   void CheckAddrIsInCardTable(const byte* addr) const;
@@ -81,7 +105,7 @@
   void ClearCardTable();
 
   // Resets all of the bytes in the card table which do not map to the image space.
-  void ClearNonImageSpaceCards(Heap* heap);
+  void ClearSpaceCards(Space* space);
 
   // Returns the first address in the heap which maps to this card.
   void* AddrFromCard(const byte *card_addr) const {
@@ -92,8 +116,6 @@
     uintptr_t offset = card_addr - biased_begin_;
     return reinterpret_cast<void*>(offset << GC_CARD_SHIFT);
   }
- private:
-  CardTable(MemMap* begin, byte* biased_begin, size_t offset);
 
   // Returns the address of the relevant byte in the card table, given an address on the heap.
   byte* CardFromAddr(const void *addr) const {
@@ -104,6 +126,9 @@
     return card_addr;
   }
 
+ private:
+  CardTable(MemMap* begin, byte* biased_begin, size_t offset);
+
   // Returns true iff the card table address is within the bounds of the card table.
   bool IsValidCard(const byte* card_addr) const {
     byte* begin = mem_map_->Begin() + offset_;
diff --git a/src/heap.cc b/src/heap.cc
index 005609b..a96472b 100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -24,6 +24,7 @@
 
 #include "card_table.h"
 #include "debugger.h"
+#include "heap_bitmap.h"
 #include "image.h"
 #include "mark_sweep.h"
 #include "mod_union_table.h"
@@ -141,6 +142,7 @@
       card_table_(NULL),
       card_marking_disabled_(false),
       is_gc_running_(false),
+      concurrent_start_bytes_(std::numeric_limits<size_t>::max()),
       concurrent_start_size_(128 * KB),
       concurrent_min_free_(256 * KB),
       try_running_gc_(false),
@@ -153,6 +155,7 @@
       reference_queueNext_offset_(0),
       reference_pendingNext_offset_(0),
       finalizer_reference_zombie_offset_(0),
+      have_zygote_space_(false),
       target_utilization_(0.5),
       verify_objects_(false) {
   if (VLOG_IS_ON(heap) || VLOG_IS_ON(startup)) {
@@ -164,8 +167,8 @@
   Space* first_space = NULL;
   Space* last_space = NULL;
 
-  live_bitmap_.reset(new HeapBitmap);
-  mark_bitmap_.reset(new HeapBitmap);
+  live_bitmap_.reset(new HeapBitmap(this));
+  mark_bitmap_.reset(new HeapBitmap(this));
 
   // Requested begin for the alloc space, to follow the mapped image and oat files
   byte* requested_begin = NULL;
@@ -210,10 +213,8 @@
   UniquePtr<AllocSpace> alloc_space(Space::CreateAllocSpace(
       "alloc space", initial_size, growth_limit, capacity, requested_begin));
   alloc_space_ = alloc_space.release();
+  CHECK(alloc_space_ != NULL) << "Failed to create alloc space";
   AddSpace(alloc_space_);
-  if (alloc_space_ == NULL) {
-    LOG(FATAL) << "Failed to create alloc space";
-  }
 
   UpdateFirstAndLastSpace(&first_space, &last_space, alloc_space_);
   byte* heap_begin = first_space->Begin();
@@ -228,44 +229,48 @@
   }
 
   // Allocate the card table.
-  UniquePtr<CardTable> card_table(CardTable::Create(heap_begin, heap_capacity));
-  if (card_table.get() == NULL) {
-    LOG(FATAL) << "Failed to create card table";
-  }
+  card_table_.reset(CardTable::Create(heap_begin, heap_capacity));
+  CHECK(card_table_.get() != NULL) << "Failed to create card table";
 
-  // Allocate the mod-union table
-  ModUnionTableReferenceCache* mod_union_table = new ModUnionTableReferenceCache(this);
-  mod_union_table->Init();
-  mod_union_table_ = mod_union_table;
+  mod_union_table_.reset(new ModUnionTableToZygoteAllocspace<ModUnionTableReferenceCache>(this));
+  CHECK(mod_union_table_.get() != NULL) << "Failed to create mod-union table";
 
-  card_table_ = card_table.release();
+  zygote_mod_union_table_.reset(new ModUnionTableCardCache(this));
+  CHECK(zygote_mod_union_table_.get() != NULL) << "Failed to create Zygote mod-union table";
 
   num_bytes_allocated_ = 0;
   num_objects_allocated_ = 0;
 
-  mark_stack_ = MarkStack::Create();
+  mark_stack_.reset(MarkStack::Create());
 
   // It's still too early to take a lock because there are no threads yet,
   // but we can create the heap lock now. We don't create it earlier to
   // make it clear that you can't use locks during heap initialization.
-  lock_ = new Mutex("Heap lock", kHeapLock);
-  condition_ = new ConditionVariable("Heap condition variable");
-
-  concurrent_start_bytes_ = std::numeric_limits<size_t>::max();
+  lock_.reset(new Mutex("Heap lock", kHeapLock));
+  condition_.reset(new ConditionVariable("Heap condition variable"));
 
   if (VLOG_IS_ON(heap) || VLOG_IS_ON(startup)) {
     LOG(INFO) << "Heap() exiting";
   }
 }
 
+// Sort spaces based on begin address
+class SpaceSorter {
+ public:
+  bool operator () (const Space* a, const Space* b) const {
+    return a->Begin() < b->Begin();
+  }
+};
+
 void Heap::AddSpace(Space* space) {
+  DCHECK(space != NULL);
   DCHECK(space->GetLiveBitmap() != NULL);
   live_bitmap_->AddSpaceBitmap(space->GetLiveBitmap());
-
   DCHECK(space->GetMarkBitmap() != NULL);
   mark_bitmap_->AddSpaceBitmap(space->GetMarkBitmap());
-
   spaces_.push_back(space);
+  // Ensure that spaces remain sorted in increasing order of start address (required for CMS finger)
+  std::sort(spaces_.begin(), spaces_.end(), SpaceSorter());
 }
 
 Heap::~Heap() {
@@ -275,11 +280,6 @@
   // all daemon threads are suspended, and we also know that the threads list have been deleted, so
   // those threads can't resume. We're the only running thread, and we can do whatever we like...
   STLDeleteElements(&spaces_);
-  delete card_table_;
-  delete mod_union_table_;
-  delete mark_stack_;
-  delete condition_;
-  delete lock_;
 }
 
 Space* Heap::FindSpaceFromObject(const Object* obj) const {
@@ -345,6 +345,10 @@
         RequestConcurrentGC();
       }
       VerifyObject(obj);
+
+      // Additional verification to ensure that we did not allocate into a zygote space.
+      DCHECK(!have_zygote_space_ || !FindSpaceFromObject(obj)->IsZygoteSpace());
+
       return obj;
     }
     total_bytes_free = GetFreeMemory();
@@ -399,13 +403,25 @@
 }
 #endif
 
+void Heap::DumpSpaces() {
+  // TODO: C++0x auto
+  for (Spaces::iterator it = spaces_.begin(); it != spaces_.end(); ++it) {
+    LOG(INFO) << **it;
+  }
+}
+
 void Heap::VerifyObjectLocked(const Object* obj) {
   lock_->AssertHeld();
   if (obj != NULL) {
     if (!IsAligned<kObjectAlignment>(obj)) {
       LOG(FATAL) << "Object isn't aligned: " << obj;
     } else if (!GetLiveBitmap()->Test(obj)) {
-      LOG(FATAL) << "Object is dead: " << obj;
+      Space* space = FindSpaceFromObject(obj);
+      if (space == NULL) {
+        DumpSpaces();
+        LOG(FATAL) << "Object " << obj << " is not contained in any space";
+      }
+      LOG(FATAL) << "Object is dead: " << obj << " in space " << *space;
     }
     // Ignore early dawn of the universe verifications
     if (num_objects_allocated_ > 10) {
@@ -498,19 +514,6 @@
     return obj;
   }
 
-  // TODO: C++0x auto
-  for (Spaces::const_iterator cur = spaces_.begin(); cur != spaces_.end(); ++cur) {
-    if ((*cur)->IsAllocSpace() && *cur != alloc_space_) {
-      AllocSpace* space = (*cur)->AsAllocSpace();
-      Object* obj = AllocateLocked(space, size);
-      if (obj != NULL) {
-        RecordAllocationLocked(space, obj);
-        // Switch to this alloc space since the old one did not have enough storage.
-        alloc_space_ = space;
-        return obj;
-      }
-    }
-  }
   return NULL;
 }
 
@@ -526,7 +529,7 @@
   if (alloc_size > space->Capacity()) {
     // On failure collect soft references
     WaitForConcurrentGcToComplete();
-    CollectGarbageInternal(false, true);
+    CollectGarbageInternal(false, false, true);
     return NULL;
   }
 
@@ -553,9 +556,19 @@
     ++Runtime::Current()->GetStats()->gc_for_alloc_count;
     ++Thread::Current()->GetStats()->gc_for_alloc_count;
   }
-  // We don't need a WaitForConcurrentGcToComplete here since we checked
-  // is_gc_running_ earlier and we are in a heap lock.
-  CollectGarbageInternal(false, false);
+
+  if (have_zygote_space_) {
+    // We don't need a WaitForConcurrentGcToComplete here since we checked is_gc_running_ earlier
+    // and we are in a heap lock. Try partial GC first.
+    CollectGarbageInternal(true, false, false);
+    ptr = space->AllocWithoutGrowth(alloc_size);
+    if (ptr != NULL) {
+      return ptr;
+    }
+  }
+
+  // Partial GC didn't free enough memory, try a full GC.
+  CollectGarbageInternal(false, false, false);
   ptr = space->AllocWithoutGrowth(alloc_size);
   if (ptr != NULL) {
     return ptr;
@@ -581,7 +594,7 @@
   // OLD-TODO: wait for the finalizers from the previous GC to finish
   VLOG(gc) << "Forcing collection of SoftReferences for " << PrettySize(alloc_size) << " allocation";
   // We don't need a WaitForConcurrentGcToComplete here either.
-  CollectGarbageInternal(false, true);
+  CollectGarbageInternal(false, false, true);
   ptr = space->AllocWithGrowth(alloc_size);
   if (ptr != NULL) {
     return ptr;
@@ -654,14 +667,43 @@
   // If we just waited for a GC to complete then we do not need to do another
   // GC unless we clear soft references.
   if (!WaitForConcurrentGcToComplete() || clear_soft_references) {
-    CollectGarbageInternal(false, clear_soft_references);
+    CollectGarbageInternal(have_zygote_space_, true, clear_soft_references);
   }
 }
 
-void Heap::CollectGarbageInternal(bool concurrent, bool clear_soft_references) {
+void Heap::PreZygoteFork() {
+  ScopedHeapLock heap_lock;
+
+  // Try to see if we have any Zygote spaces.
+  if (have_zygote_space_) {
+    return;
+  }
+
+  VLOG(heap) << "Starting PreZygoteFork with alloc space size " << PrettySize(GetBytesAllocated());
+
+  // Replace the first alloc space we find with a zygote space.
+  // TODO: C++0x auto
+  for (Spaces::iterator it = spaces_.begin(); it != spaces_.end(); ++it) {
+    if ((*it)->IsAllocSpace()) {
+      AllocSpace* zygote_space = (*it)->AsAllocSpace();
+
+      // Turns the current alloc space into a Zygote space and obtain the new alloc space composed
+      // of the remaining available heap memory.
+      alloc_space_ = zygote_space->CreateZygoteSpace();
+
+      // Change the GC retention policy of the zygote space to only collect when full.
+      zygote_space->SetGcRetentionPolicy(GCRP_FULL_COLLECT);
+      AddSpace(alloc_space_);
+      have_zygote_space_ = true;
+      break;
+    }
+  }
+}
+
+void Heap::CollectGarbageInternal(bool partial_gc, bool concurrent, bool clear_soft_references) {
   lock_->AssertHeld();
 
-  CHECK(!is_gc_running_);
+  CHECK(!is_gc_running_) << "Attempted recursive GC";
   is_gc_running_ = true;
 
   TimingLogger timings("CollectGarbageInternal");
@@ -674,19 +716,41 @@
   size_t initial_size = num_bytes_allocated_;
   Object* cleared_references = NULL;
   {
-    MarkSweep mark_sweep(mark_stack_);
+    MarkSweep mark_sweep(mark_stack_.get());
     timings.AddSplit("ctor");
 
     mark_sweep.Init();
     timings.AddSplit("Init");
 
-    if (concurrent) {
-      card_table_->ClearNonImageSpaceCards(this);
-      timings.AddSplit("ClearNonImageSpaceCards");
-    }
+    // Make sure that the tables have the correct pointer for the mark sweep.
+    mod_union_table_->Init(&mark_sweep);
+    zygote_mod_union_table_->Init(&mark_sweep);
 
     // Clear image space cards and keep track of cards we cleared in the mod-union table.
-    mod_union_table_->ClearCards();
+    for (Spaces::iterator it = spaces_.begin(); it != spaces_.end(); ++it) {
+      Space* space = *it;
+      if (space->IsImageSpace()) {
+        mod_union_table_->ClearCards(*it);
+      } else if (space->GetGcRetentionPolicy() == GCRP_FULL_COLLECT) {
+        zygote_mod_union_table_->ClearCards(space);
+      } else if (concurrent) {
+        card_table_->ClearSpaceCards(space);
+      }
+    }
+    timings.AddSplit("ClearCards");
+
+#if VERIFY_MOD_UNION
+    mod_union_table_->Verify();
+    zygote_mod_union_table_->Verify();
+#endif
+
+    if (partial_gc) {
+      // Copy the mark bits over from the live bits, do this as early as possible or else we can
+      // accidentally un-mark roots.
+      // Needed for scanning dirty objects.
+      mark_sweep.CopyMarkBits();
+      timings.AddSplit("CopyMarkBits");
+    }
 
     mark_sweep.MarkRoots();
     timings.AddSplit("MarkRoots");
@@ -703,17 +767,26 @@
       timings.AddSplit("RootEnd");
     }
 
+    // Update zygote mod union table.
+    if (partial_gc) {
+      zygote_mod_union_table_->Update();
+      timings.AddSplit("UpdateZygoteModUnionTable");
+
+      zygote_mod_union_table_->MarkReferences();
+      timings.AddSplit("ZygoteMarkReferences");
+    }
+
     // Processes the cards we cleared earlier and adds their objects into the mod-union table.
-    mod_union_table_->Update(&mark_sweep);
+    mod_union_table_->Update();
     timings.AddSplit("UpdateModUnionTable");
 
     // Scans all objects in the mod-union table.
-    mod_union_table_->MarkReferences(&mark_sweep);
+    mod_union_table_->MarkReferences();
     timings.AddSplit("MarkImageToAllocSpaceReferences");
 
     // Recursively mark all the non-image bits set in the mark bitmap.
-    mark_sweep.RecursiveMark();
-    timings.AddSplit("RecursiveMark");
+    mark_sweep.RecursiveMark(partial_gc);
+    timings.AddSplit(partial_gc ? "PartialMark" : "RecursiveMark");
 
     if (concurrent) {
       dirty_begin = NanoTime();
@@ -739,7 +812,8 @@
     // instead, resulting in no new allocated objects being incorrectly freed by sweep.
     for (Spaces::iterator it = spaces_.begin(); it != spaces_.end(); ++it) {
       Space* space = *it;
-      if (space->IsAllocSpace()) {
+      // We never allocate into zygote spaces.
+      if (space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT) {
         live_bitmap_->ReplaceBitmap(space->GetLiveBitmap(), space->GetMarkBitmap());
         mark_bitmap_->ReplaceBitmap(space->GetMarkBitmap(), space->GetLiveBitmap());
         space->AsAllocSpace()->SwapBitmaps();
@@ -756,7 +830,7 @@
       Unlock();
     }
 
-    mark_sweep.Sweep();
+    mark_sweep.Sweep(partial_gc);
     timings.AddSplit("Sweep");
 
     cleared_references = mark_sweep.GetClearedReferences();
@@ -791,18 +865,20 @@
 
     // If the GC was slow, then print timings in the log.
     if (concurrent) {
-      uint64_t pause_roots_time = (root_end - t0) / 1000 * 1000;
-      uint64_t pause_dirty_time = (dirty_end - dirty_begin) / 1000 * 1000;
-      if (pause_roots_time > MsToNs(5) || pause_dirty_time > MsToNs(5)) {
-        LOG(INFO) << "GC freed " << PrettySize(bytes_freed) << ", " << GetPercentFree() << "% free, "
+      uint64_t pause_roots = (root_end - t0) / 1000 * 1000;
+      uint64_t pause_dirty = (dirty_end - dirty_begin) / 1000 * 1000;
+      if (pause_roots > MsToNs(5) || pause_dirty > MsToNs(5)) {
+        LOG(INFO) << (partial_gc ? "Partial " : "")
+                  << "GC freed " << PrettySize(bytes_freed) << ", " << GetPercentFree() << "% free, "
                   << PrettySize(num_bytes_allocated_) << "/" << PrettySize(GetTotalMemory()) << ", "
-                  << "paused " << PrettyDuration(pause_roots_time) << "+" << PrettyDuration(pause_dirty_time)
+                  << "paused " << PrettyDuration(pause_roots) << "+" << PrettyDuration(pause_dirty)
                   << ", total " << PrettyDuration(duration_ns);
       }
     } else {
       if (duration_ns > MsToNs(50)) {
         uint64_t markSweepTime = (dirty_end - t0) / 1000 * 1000;
-        LOG(INFO) << "GC freed " << PrettySize(bytes_freed) << ", " << GetPercentFree() << "% free, "
+        LOG(INFO) << (partial_gc ? "Partial " : "")
+                  << "GC freed " << PrettySize(bytes_freed) << ", " << GetPercentFree() << "% free, "
                   << PrettySize(num_bytes_allocated_) << "/" << PrettySize(GetTotalMemory()) << ", "
                   << "paused " << PrettyDuration(markSweepTime)
                   << ", total " << PrettyDuration(duration_ns);
@@ -854,20 +930,15 @@
 }
 
 void Heap::SetIdealFootprint(size_t max_allowed_footprint) {
-  // TODO: C++0x auto
-  for (Spaces::const_iterator cur = spaces_.begin(); cur != spaces_.end(); ++cur) {
-    if ((*cur)->IsAllocSpace()) {
-      AllocSpace* alloc_space = (*cur)->AsAllocSpace();
-      // TODO: Behavior for multiple alloc spaces?
-      size_t alloc_space_capacity = alloc_space->Capacity();
-      if (max_allowed_footprint > alloc_space_capacity) {
-        VLOG(gc) << "Clamp target GC heap from " << PrettySize(max_allowed_footprint)
-                 << " to " << PrettySize(alloc_space_capacity);
-        max_allowed_footprint = alloc_space_capacity;
-      }
-      alloc_space->SetFootprintLimit(max_allowed_footprint);
-    }
+  AllocSpace* alloc_space = alloc_space_;
+  // TODO: Behavior for multiple alloc spaces?
+  size_t alloc_space_capacity = alloc_space->Capacity();
+  if (max_allowed_footprint > alloc_space_capacity) {
+    VLOG(gc) << "Clamp target GC heap from " << PrettySize(max_allowed_footprint)
+             << " to " << PrettySize(alloc_space_capacity);
+    max_allowed_footprint = alloc_space_capacity;
   }
+  alloc_space->SetFootprintLimit(max_allowed_footprint);
 }
 
 // kHeapIdealFree is the ideal maximum free size, when we grow the heap for utilization.
@@ -1049,7 +1120,9 @@
   CHECK(!is_gc_running_);
   // Current thread needs to be runnable or else we can't suspend all threads.
   ScopedThreadStateChange tsc(Thread::Current(), kRunnable);
-  CollectGarbageInternal(true, false);
+  if (!WaitForConcurrentGcToComplete()) {
+    CollectGarbageInternal(have_zygote_space_, true, false);
+  }
 }
 
 void Heap::Trim(AllocSpace* alloc_space) {
diff --git a/src/heap.h b/src/heap.h
index e383665..a1b1bd9 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -39,7 +39,6 @@
 class ImageSpace;
 class MarkStack;
 class ModUnionTable;
-class ModUnionTableBitmap;
 class Object;
 class Space;
 class SpaceTest;
@@ -195,7 +194,7 @@
   }
 
   CardTable* GetCardTable() {
-    return card_table_;
+    return card_table_.get();
   }
 
   void DisableCardMarking() {
@@ -236,10 +235,13 @@
     return mark_bitmap_.get();
   }
 
-  // Assumes there is only one image space.
+  void PreZygoteFork();
+
   // DEPRECATED: Should remove in "near" future when support for multiple image spaces is added.
+  // Assumes there is only one image space.
   ImageSpace* GetImageSpace();
   AllocSpace* GetAllocSpace();
+  void DumpSpaces();
 
  private:
   // Allocates uninitialized storage.
@@ -258,7 +260,7 @@
   void RecordAllocationLocked(AllocSpace* space, const Object* object);
 
   // TODO: can we teach GCC to understand the weird locking in here?
-  void CollectGarbageInternal(bool concurrent, bool clear_soft_references) NO_THREAD_SAFETY_ANALYSIS;
+  void CollectGarbageInternal(bool partial_gc, bool concurrent, bool clear_soft_references) NO_THREAD_SAFETY_ANALYSIS;
 
   // Given the current contents of the alloc space, increase the allowed heap footprint to match
   // the target utilization ratio.  This should only be called immediately after a full garbage
@@ -275,19 +277,22 @@
 
   static void VerificationCallback(Object* obj, void* arg);
 
-  Mutex* lock_;
-  ConditionVariable* condition_;
+  UniquePtr<Mutex> lock_;
+  UniquePtr<ConditionVariable> condition_;
 
   Spaces spaces_;
 
   // The alloc space which we are currently allocating into.
   AllocSpace* alloc_space_;
 
-  // TODO: Reduce memory usage, this bitmap currently takes 1 bit per 8 bytes
-  // of image space.
-  ModUnionTable* mod_union_table_;
+  // The mod-union table remembers all of the referneces from the image space to the alloc /
+  // zygote spaces.
+  UniquePtr<ModUnionTable> mod_union_table_;
 
-  CardTable* card_table_;
+  // This table holds all of the references from the zygote space to the alloc space.
+  UniquePtr<ModUnionTable> zygote_mod_union_table_;
+
+  UniquePtr<CardTable> card_table_;
 
   // Used by the image writer to disable card marking on copied objects
   // TODO: remove
@@ -313,7 +318,7 @@
   bool requesting_gc_;
 
   // Mark stack that we reuse to avoid re-allocating the mark stack
-  MarkStack* mark_stack_;
+  UniquePtr<MarkStack> mark_stack_;
 
   // Number of bytes allocated.  Adjusted after each allocation and free.
   size_t num_bytes_allocated_;
@@ -339,6 +344,9 @@
   // offset of java.lang.ref.FinalizerReference.zombie
   MemberOffset finalizer_reference_zombie_offset_;
 
+  // If we have a zygote space.
+  bool have_zygote_space_;
+
   // Target ideal heap utilization ratio
   float target_utilization_;
 
@@ -347,6 +355,7 @@
   friend class ScopedHeapLock;
   FRIEND_TEST(SpaceTest, AllocAndFree);
   FRIEND_TEST(SpaceTest, AllocAndFreeList);
+  FRIEND_TEST(SpaceTest, ZygoteSpace);
   friend class SpaceTest;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(Heap);
diff --git a/src/heap_bitmap.cc b/src/heap_bitmap.cc
index 7d81a5d..50a037b 100644
--- a/src/heap_bitmap.cc
+++ b/src/heap_bitmap.cc
@@ -1,16 +1,31 @@
 #include "heap_bitmap.h"
+#include "space.h"
 
 namespace art {
 
 void HeapBitmap::ReplaceBitmap(SpaceBitmap* old_bitmap, SpaceBitmap* new_bitmap) {
   // TODO: C++0x auto
-  for (Bitmaps::iterator cur  = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
-    if (*cur == old_bitmap) {
-      *cur = new_bitmap;
+  for (Bitmaps::iterator it = bitmaps_.begin(); it != bitmaps_.end(); ++it) {
+    if (*it == old_bitmap) {
+      *it = new_bitmap;
       return;
     }
   }
   LOG(FATAL) << "bitmap " << static_cast<const void*>(old_bitmap) << " not found";
 }
 
+void HeapBitmap::AddSpaceBitmap(SpaceBitmap* bitmap) {
+  DCHECK(bitmap != NULL);
+
+  // Check for interval overlap.
+  for (Bitmaps::const_iterator it = bitmaps_.begin(); it != bitmaps_.end(); ++it) {
+    SpaceBitmap* cur_bitmap = *it;
+    if (bitmap->HeapBegin() < cur_bitmap->HeapSize() + cur_bitmap->HeapSize() &&
+        bitmap->HeapBegin() + bitmap->HeapSize() > cur_bitmap->HeapBegin()) {
+      LOG(FATAL) << "Overlapping space bitmaps added to heap bitmap!";
+    }
+  }
+  bitmaps_.push_back(bitmap);
+}
+
 }  // namespace art
diff --git a/src/heap_bitmap.h b/src/heap_bitmap.h
index 29a7b1f..4333199 100644
--- a/src/heap_bitmap.h
+++ b/src/heap_bitmap.h
@@ -69,11 +69,16 @@
     // Find and replace a bitmap pointer, this is used by for the bitmap swapping in the GC.
     void ReplaceBitmap(SpaceBitmap* old_bitmap, SpaceBitmap* new_bitmap);
 
-   private:
-    void AddSpaceBitmap(SpaceBitmap* space) {
-      bitmaps_.push_back(space);
+    HeapBitmap(Heap* heap) : heap_(heap) {
+
     }
 
+   private:
+
+    const Heap* const heap_;
+
+    void AddSpaceBitmap(SpaceBitmap* bitmap);
+
     typedef std::vector<SpaceBitmap*> Bitmaps;
     Bitmaps bitmaps_;
 
diff --git a/src/mark_sweep.cc b/src/mark_sweep.cc
index 5155e30..df394db 100644
--- a/src/mark_sweep.cc
+++ b/src/mark_sweep.cc
@@ -59,7 +59,7 @@
   const Spaces& spaces = heap_->GetSpaces();
   // TODO: C++0x auto
   for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
-    if ((*cur)->IsAllocSpace()) {
+    if ((*cur)->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT) {
       current_mark_bitmap_ = (*cur)->GetMarkBitmap();
       break;
     }
@@ -126,14 +126,6 @@
   Runtime::Current()->VisitRoots(MarkObjectVisitor, this);
 }
 
-void MarkSweep::ScanImageRootVisitor(Object* root, void* arg) {
-  DCHECK(root != NULL);
-  DCHECK(arg != NULL);
-  MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
-  // We do not need to mark since live == marked for image spaces.
-  mark_sweep->ScanObject(root);
-}
-
 class CheckObjectVisitor {
  public:
   CheckObjectVisitor(MarkSweep* const mark_sweep)
@@ -163,28 +155,45 @@
   mark_sweep->CheckObject(root);
 }
 
-// Marks all objects that are in images and have been touched by the mutator
-void MarkSweep::ScanDirtyImageRoots() {
+void MarkSweep::CopyMarkBits() {
   const std::vector<Space*>& spaces = heap_->GetSpaces();
-  CardTable* card_table = heap_->GetCardTable();
   for (size_t i = 0; i < spaces.size(); ++i) {
-    if (spaces[i]->IsImageSpace()) {
-      byte* begin = spaces[i]->Begin();
-      byte* end = spaces[i]->End();
-      card_table->Scan(spaces[i]->GetLiveBitmap(), begin, end, ScanImageRootVisitor, this);
+    Space* space = spaces[i];
+    if (space->GetGcRetentionPolicy() == GCRP_FULL_COLLECT) {
+      SpaceBitmap* live_bitmap = space->GetLiveBitmap();
+      SpaceBitmap* mark_bitmap = space->GetMarkBitmap();
+      DCHECK_EQ(live_bitmap->Size(), mark_bitmap->Size());
+      std::copy(live_bitmap->Begin(), live_bitmap->Begin() + live_bitmap->Size() / kWordSize, mark_bitmap->Begin());
     }
   }
 }
 
-void MarkSweep::CheckBitmapCallback(Object* obj, void* finger, void* arg) {
-  MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
-  mark_sweep->finger_ = reinterpret_cast<Object*>(finger);
-  mark_sweep->CheckObject(obj);
-}
+class ScanImageRootVisitor {
+ public:
+  ScanImageRootVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
 
-void MarkSweep::CheckBitmapNoFingerCallback(Object* obj, void* arg) {
-  MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
-  mark_sweep->CheckObject(obj);
+  }
+
+  void operator ()(const Object* root) const {
+    DCHECK(root != NULL);
+    mark_sweep_->ScanObject(root);
+  }
+
+ private:
+  MarkSweep* const mark_sweep_;
+};
+
+// Marks all objects that are in images and have been touched by the mutator
+void MarkSweep::ScanDirtyImageRoots() {
+  const std::vector<Space*>& spaces = heap_->GetSpaces();
+  CardTable* card_table = heap_->GetCardTable();
+  ScanImageRootVisitor image_root_visitor(this);
+  for (size_t i = 0; i < spaces.size(); ++i) {
+    Space* space = spaces[i];
+    if (space->IsImageSpace()) {
+      card_table->Scan(space->GetLiveBitmap(), space->Begin(), space->End(), image_root_visitor);
+    }
+  }
 }
 
 void MarkSweep::ScanBitmapCallback(Object* obj, void* finger, void* arg) {
@@ -201,37 +210,53 @@
 void MarkSweep::ScanGrayObjects() {
   const std::vector<Space*>& spaces = heap_->GetSpaces();
   CardTable* card_table = heap_->GetCardTable();
+  ScanImageRootVisitor image_root_visitor(this);
   for (size_t i = 0; i < spaces.size(); ++i) {
     byte* begin = spaces[i]->Begin();
     byte* end = spaces[i]->End();
     // Image spaces are handled properly since live == marked for them.
-    card_table->Scan(spaces[i]->GetMarkBitmap(), begin, end, ScanImageRootVisitor, this);
+    card_table->Scan(spaces[i]->GetMarkBitmap(), begin, end, image_root_visitor);
   }
 }
 
+class CheckBitmapVisitor {
+ public:
+  CheckBitmapVisitor(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) {
+
+  }
+
+  void operator ()(const Object* obj) const {
+    DCHECK(obj != NULL);
+    mark_sweep_->CheckObject(obj);
+  }
+
+ private:
+  MarkSweep* mark_sweep_;
+};
+
 void MarkSweep::VerifyImageRoots() {
   // Verify roots ensures that all the references inside the image space point
   // objects which are either in the image space or marked objects in the alloc
   // space
 #ifndef NDEBUG
-  void* arg = reinterpret_cast<void*>(this);
-  const std::vector<Space*>& spaces = heap_->GetSpaces();
-  for (size_t i = 0; i < spaces.size(); ++i) {
-    if (spaces[i]->IsImageSpace()) {
-      uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
-      uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
-      SpaceBitmap* live_bitmap = spaces[i]->GetLiveBitmap();
+  CheckBitmapVisitor visitor(this);
+  const Spaces& spaces = heap_->GetSpaces();
+  for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
+    const Space* space = *it;
+    if (space->IsImageSpace()) {
+      uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
+      uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
+      SpaceBitmap* live_bitmap = space->GetLiveBitmap();
       DCHECK(live_bitmap != NULL);
-      live_bitmap->ScanWalk(begin, end, CheckBitmapCallback, arg);
+      live_bitmap->VisitMarkedRange(begin, end, visitor);
     }
   }
-  finger_ = reinterpret_cast<Object*>(~0);
 #endif
 }
 
 // Populates the mark stack based on the set of marked objects and
 // recursively marks until the mark stack is emptied.
-void MarkSweep::RecursiveMark() {
+void MarkSweep::RecursiveMark(bool partial) {
   // RecursiveMark will build the lists of known instances of the Reference classes.
   // See DelayReferenceReferent for details.
   CHECK(soft_reference_list_ == NULL);
@@ -241,12 +266,17 @@
   CHECK(cleared_reference_list_ == NULL);
 
   void* arg = reinterpret_cast<void*>(this);
-  const std::vector<Space*>& spaces = heap_->GetSpaces();
+  const Spaces& spaces = heap_->GetSpaces();
+
   for (size_t i = 0; i < spaces.size(); ++i) {
-    if (spaces[i]->IsAllocSpace()) {
-      uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
-      uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
-      current_mark_bitmap_ = spaces[i]->GetMarkBitmap();
+    Space* space = spaces[i];
+    if (space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT ||
+        (!partial && space->GetGcRetentionPolicy() == GCRP_FULL_COLLECT)
+        ) {
+      uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
+      uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
+
+      current_mark_bitmap_ = space->GetMarkBitmap();
       current_mark_bitmap_->ScanWalk(begin, end, &ScanBitmapCallback, arg);
     }
   }
@@ -305,7 +335,6 @@
     for (size_t i = 0; i < num_ptrs; ++i) {
       Object* obj = static_cast<Object*>(ptrs[i]);
       freed_bytes += space->AllocationSize(obj);
-      heap->GetLiveBitmap()->Clear(obj);
     }
     // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit
     space->FreeList(num_ptrs, ptrs);
@@ -313,14 +342,25 @@
     for (size_t i = 0; i < num_ptrs; ++i) {
       Object* obj = static_cast<Object*>(ptrs[i]);
       freed_bytes += space->AllocationSize(obj);
-      heap->GetLiveBitmap()->Clear(obj);
       space->Free(obj);
     }
   }
   heap->RecordFreeLocked(freed_objects, freed_bytes);
 }
 
-void MarkSweep::Sweep() {
+void MarkSweep::ZygoteSweepCallback(size_t num_ptrs, Object** ptrs, void* arg) {
+  ScopedHeapLock lock;
+  SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg);
+  Heap* heap = context->heap;
+  // We don't free any actual memory to avoid dirtying the shared zygote pages.
+  for (size_t i = 0; i < num_ptrs; ++i) {
+    Object* obj = static_cast<Object*>(ptrs[i]);
+    heap->GetLiveBitmap()->Clear(obj);
+    heap->GetCardTable()->MarkCard(obj);
+  }
+}
+
+void MarkSweep::Sweep(bool partial) {
   SweepSystemWeaks();
 
   DCHECK(mark_stack_->IsEmpty());
@@ -329,15 +369,25 @@
   SweepCallbackContext scc;
   scc.heap = heap_;
   for (size_t i = 0; i < spaces.size(); ++i) {
-    if (!spaces[i]->IsImageSpace()) {
-      uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
-      uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
-      scc.space = spaces[i]->AsAllocSpace();
-      // Bitmaps are pre-swapped for optimization which enables sweeping with the heap unlocked.
-      SpaceBitmap* live_bitmap = scc.space->GetMarkBitmap();
-      SpaceBitmap* mark_bitmap = scc.space->GetLiveBitmap();
-      SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end,
-                            &MarkSweep::SweepCallback, reinterpret_cast<void*>(&scc));
+    Space* space = spaces[i];
+    if (
+        space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT ||
+        (!partial && space->GetGcRetentionPolicy() == GCRP_FULL_COLLECT)
+        ) {
+      uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
+      uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
+      scc.space = space->AsAllocSpace();
+      SpaceBitmap* live_bitmap = space->GetLiveBitmap();
+      SpaceBitmap* mark_bitmap = space->GetMarkBitmap();
+      if (space->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT) {
+        // Bitmaps are pre-swapped for optimization which enables sweeping with the heap unlocked.
+        SpaceBitmap::SweepWalk(
+            *mark_bitmap, *live_bitmap, begin, end, &SweepCallback, reinterpret_cast<void*>(&scc));
+      } else {
+        // Zygote sweep takes care of dirtying cards and clearing live bits, does not free actual memory.
+        SpaceBitmap::SweepWalk(
+            *live_bitmap, *mark_bitmap, begin, end, &ZygoteSweepCallback, reinterpret_cast<void*>(&scc));
+      }
     }
   }
 }
@@ -500,7 +550,7 @@
 
 // Scans an object reference.  Determines the type of the reference
 // and dispatches to a specialized scanning routine.
-inline void MarkSweep::ScanObject(const Object* obj) {
+void MarkSweep::ScanObject(const Object* obj) {
   DCHECK(obj != NULL);
   DCHECK(obj->GetClass() != NULL);
   DCHECK(heap_->GetMarkBitmap()->Test(obj));
@@ -517,6 +567,7 @@
 void MarkSweep::ProcessMarkStack() {
   while (!mark_stack_->IsEmpty()) {
     const Object* obj = mark_stack_->Pop();
+    DCHECK(obj != NULL);
     ScanObject(obj);
   }
 }
@@ -649,7 +700,7 @@
   const Spaces& spaces = heap_->GetSpaces();
   // TODO: C++0x auto
   for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
-    if ((*cur)->IsAllocSpace()) {
+    if ((*cur)->GetGcRetentionPolicy() != GCRP_NEVER_COLLECT) {
       (*cur)->GetMarkBitmap()->Clear();
     }
   }
diff --git a/src/mark_sweep.h b/src/mark_sweep.h
index 5f275a4..108da87 100644
--- a/src/mark_sweep.h
+++ b/src/mark_sweep.h
@@ -57,7 +57,10 @@
   }
 
   // Builds a mark stack and recursively mark until it empties.
-  void RecursiveMark();
+  void RecursiveMark(bool partial);
+
+  // Copies mark bits from live bitmap of zygote space to mark bitmap for partial GCs.
+  void CopyMarkBits();
 
   // Builds a mark stack with objects on dirty cards and recursively mark
   // until it empties.
@@ -66,6 +69,10 @@
   // Remarks the root set after completing the concurrent mark.
   void ReMarkRoots();
 
+  Heap* GetHeap() {
+    return heap_;
+  }
+
   void ProcessReferences(bool clear_soft_references) {
     ProcessReferences(&soft_reference_list_, clear_soft_references,
                       &weak_reference_list_,
@@ -74,12 +81,15 @@
   }
 
   // Sweeps unmarked objects to complete the garbage collection.
-  void Sweep();
+  void Sweep(bool partial);
 
   Object* GetClearedReferences() {
     return cleared_reference_list_;
   }
 
+  // Blackens an object.
+  void ScanObject(const Object* obj);
+
  private:
   // Returns true if the object has its bit set in the mark bitmap.
   bool IsMarked(const Object* object) const {
@@ -97,8 +107,6 @@
 
   static void ReMarkObjectVisitor(const Object* root, void* arg);
 
-  static void ScanImageRootVisitor(Object* root, void* arg);
-
   static void VerifyImageRootVisitor(Object* root, void* arg);
 
   static void ScanDirtyCardCallback(Object* obj, void* arg);
@@ -111,16 +119,12 @@
 
   static void ScanBitmapCallback(Object* obj, void* finger, void* arg);
 
-  static void CheckBitmapCallback(Object* obj, void* finger, void* arg);
-
-  static void CheckBitmapNoFingerCallback(Object* obj, void* arg);
-
   static void SweepCallback(size_t num_ptrs, Object** ptrs, void* arg);
 
-  void CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static);
+  // Special sweep for zygote that just marks objects / dirties cards.
+  static void ZygoteSweepCallback(size_t num_ptrs, Object** ptrs, void* arg);
 
-  // Blackens an object.
-  void ScanObject(const Object* obj);
+  void CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static);
 
   void CheckObject(const Object* obj);
 
@@ -275,14 +279,20 @@
   size_t other_count_;
 
   friend class AddIfReachesAllocSpaceVisitor; // Used by mod-union table.
+  friend class CheckBitmapVisitor;
   friend class CheckObjectVisitor;
+  friend class CheckReferenceVisitor;
   friend class InternTableEntryIsUnmarked;
   friend class MarkIfReachesAllocspaceVisitor;
+  friend class ModUnionCheckReferences;
   friend class ModUnionClearCardVisitor;
   friend class ModUnionReferenceVisitor;
   friend class ModUnionVisitor;
   friend class ModUnionTableBitmap;
   friend class ModUnionTableReferenceCache;
+  friend class ModUnionScanImageRootVisitor;
+  friend class ScanBitmapVisitor;
+  friend class ScanImageRootVisitor;
 
   DISALLOW_COPY_AND_ASSIGN(MarkSweep);
 };
diff --git a/src/mem_map.cc b/src/mem_map.cc
index 409e653..9e86772 100644
--- a/src/mem_map.cc
+++ b/src/mem_map.cc
@@ -134,6 +134,13 @@
   CHECK_NE(base_size_, 0U);
 };
 
+void MemMap::UnMapAtEnd(byte* new_end) {
+  DCHECK_GE(new_end, Begin());
+  DCHECK_LE(new_end, End());
+  size_t unmap_size = End() - new_end;
+  munmap(new_end, unmap_size);
+  size_ -= unmap_size;
+}
 
 bool MemMap::Protect(int prot) {
   if (base_begin_ == NULL && base_size_ == 0) {
diff --git a/src/mem_map.h b/src/mem_map.h
index f442570..c7744bb 100644
--- a/src/mem_map.h
+++ b/src/mem_map.h
@@ -75,11 +75,14 @@
     return begin_ + size_;
   }
 
+  // Trim by unmapping pages at the end of the map.
+  void UnMapAtEnd(byte* new_end);
+
  private:
   MemMap(byte* begin, size_t size, void* base_begin, size_t base_size, int prot);
 
   byte* const begin_;  // Start of data.
-  const size_t size_;  // Length of data.
+  size_t size_;  // Length of data.
 
   void* const base_begin_;  // Page-aligned base address.
   const size_t base_size_;  // Length of mapping.
diff --git a/src/mod_union_table.cc b/src/mod_union_table.cc
index 3b0de40..19964af 100644
--- a/src/mod_union_table.cc
+++ b/src/mod_union_table.cc
@@ -39,6 +39,7 @@
     for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
       if ((*cur)->IsAllocSpace() && (*cur)->Contains(ref)) {
         bitmap_->Set(obj);
+        break;
       }
     }
   }
@@ -80,88 +81,86 @@
   std::vector<byte*>* cleared_cards_;
 };
 
-ModUnionTableBitmap::ModUnionTableBitmap(Heap* heap) : heap_(heap) {
+ModUnionTableBitmap::ModUnionTableBitmap(Heap* heap) : ModUnionTable(heap)  {
   // Prevent fragmentation of the heap which is caused by resizing of the vector.
   // TODO: Make a new vector which uses madvise (basically same as a mark stack).
   cleared_cards_.reserve(32);
+  const Spaces& spaces = mark_sweep_->GetHeap()->GetSpaces();
+  // Create one heap bitmap per image space.
+  // TODO: C++0x auto
+  for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
+    Space* space = *it;
+    if (space->IsImageSpace()) {
+      // The mod-union table is only needed when we have an image space since it's purpose is to
+      // cache image roots.
+      UniquePtr<SpaceBitmap> bitmap(SpaceBitmap::Create("mod-union table bitmap", space->Begin(), space->Capacity()));
+      CHECK(bitmap.get() != NULL) << "Failed to create mod-union bitmap";
+      bitmaps_.Put(space, bitmap.release());
+    }
+  }
 }
 
 ModUnionTableBitmap::~ModUnionTableBitmap() {
   STLDeleteValues(&bitmaps_);
 }
 
-void ModUnionTableBitmap::Init() {
-  const Spaces& spaces = heap_->GetSpaces();
-
-  // Create one heap bitmap per image space.
-  for (size_t i = 0; i < spaces.size(); ++i) {
-    if (spaces[i]->IsImageSpace()) {
-      // Allocate the mod-union table
-      // The mod-union table is only needed when we have an image space since it's purpose is to cache image roots.
-      UniquePtr<SpaceBitmap> bitmap(SpaceBitmap::Create("mod-union table bitmap", spaces[i]->Begin(), spaces[i]->Capacity()));
-      if (bitmap.get() == NULL) {
-        LOG(FATAL) << "Failed to create mod-union bitmap";
-      }
-
-      bitmaps_.Put(spaces[i], bitmap.release());
-    }
-  }
+void ModUnionTableBitmap::ClearCards(Space* space) {
+  CardTable* card_table = mark_sweep_->heap_->GetCardTable();
+  ModUnionClearCardVisitor visitor(&cleared_cards_);
+  // Clear dirty cards in the this image space and update the corresponding mod-union bits.
+  card_table->VisitClear(space->Begin(), space->End(), visitor);
 }
 
-void ModUnionTableBitmap::ClearCards() {
-  CardTable* card_table = heap_->GetCardTable();
-  for (BitmapMap::iterator it = bitmaps_.begin(); it != bitmaps_.end(); ++it) {
-    const Space* space = it->first;
-    ModUnionClearCardVisitor visitor(&cleared_cards_);
-    // Clear dirty cards in the this image space and update the corresponding mod-union bits.
-    card_table->VisitClear(space->Begin(), space->End(), visitor);
-  }
-}
-
-void ModUnionTableBitmap::Update(MarkSweep* mark_sweep) {
-  CardTable* card_table = heap_->GetCardTable();
+void ModUnionTableBitmap::Update() {
+  CardTable* card_table = mark_sweep_->heap_->GetCardTable();
   while (!cleared_cards_.empty()) {
     byte* card = cleared_cards_.back();
     cleared_cards_.pop_back();
 
-    // Find out which bitmap the card maps to.
-    SpaceBitmap* bitmap = 0;
-    const Space* space = 0;
-    for (BitmapMap::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
-      space = cur->first;
-      if (space->Contains(reinterpret_cast<Object*>(card_table->AddrFromCard(card)))) {
-        bitmap = cur->second;
-        break;
-      }
-    }
-    DCHECK(bitmap != NULL);
-
     uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card));
-    uintptr_t end = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card + 1));
+    uintptr_t end = start + GC_CARD_SIZE;
+    Space* space = heap_->FindSpaceFromObject(reinterpret_cast<Object*>(start));
+    SpaceBitmap* bitmap = space->GetLiveBitmap();
 
-    // Clear the mod-union bitmap range corresponding to this card so that we
-    // don't have any objects marked which do not reach the alloc space.
+    // Clear the mod-union bitmap range corresponding to this card so that we don't have any
+    // objects marked which do not reach the alloc space.
     bitmap->VisitRange(start, end, SpaceBitmap::ClearVisitor(bitmap));
 
-    // At this point we need to update the mod-union bitmap to contain all the
-    // objects which reach the alloc space.
-    ModUnionVisitor visitor(mark_sweep, bitmap);
+    // At this point we need to update the mod-union bitmap to contain all the objects which reach
+    // the alloc space.
+    ModUnionVisitor visitor(mark_sweep_, bitmap);
     space->GetLiveBitmap()->VisitMarkedRange(start, end, visitor);
   }
 }
 
+class ModUnionScanImageRootVisitor {
+ public:
+  ModUnionScanImageRootVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
+
+  }
+
+  void operator ()(const Object* root) const {
+    DCHECK(root != NULL);
+    mark_sweep_->ScanObject(root);
+  }
+
+ private:
+  MarkSweep* const mark_sweep_;
+};
+
 void ModUnionTableBitmap::MarkReferences(MarkSweep* mark_sweep) {
   // Some tests have no image space, and therefore no mod-union bitmap.
+  ModUnionScanImageRootVisitor image_root_scanner(mark_sweep);
   for (BitmapMap::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
     const Space* space = cur->first;
     uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
     uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
-    cur->second->VisitRange(begin, end, MarkSweep::ScanImageRootVisitor, mark_sweep);
+    cur->second->VisitMarkedRange(begin, end, image_root_scanner);
   }
 }
 
 
-ModUnionTableReferenceCache::ModUnionTableReferenceCache(Heap* heap) : heap_(heap) {
+ModUnionTableReferenceCache::ModUnionTableReferenceCache(Heap* heap) : ModUnionTable(heap) {
   cleared_cards_.reserve(32);
 }
 
@@ -169,51 +168,43 @@
 
 }
 
-void ModUnionTableReferenceCache::Init() {
 
+void ModUnionTableReferenceCache::ClearCards(Space* space) {
+  CardTable* card_table = GetMarkSweep()->GetHeap()->GetCardTable();
+  ModUnionClearCardVisitor visitor(&cleared_cards_);
+  // Clear dirty cards in the this space and update the corresponding mod-union bits.
+  card_table->VisitClear(space->Begin(), space->End(), visitor);
 }
 
-void ModUnionTableReferenceCache::ClearCards() {
-  const Spaces& spaces = heap_->GetSpaces();
-  CardTable* card_table = heap_->GetCardTable();
-
-  // Create one heap bitmap per image space.
-  for (size_t i = 0; i < spaces.size(); ++i) {
-    if (spaces[i]->IsImageSpace()) {
-      ModUnionClearCardVisitor visitor(&cleared_cards_);
-      // Clear dirty cards in the this image space and update the corresponding mod-union bits.
-      card_table->VisitClear(spaces[i]->Begin(), spaces[i]->End(), visitor);
-    }
-  }
-}
-
-class AddIfReachesAllocSpaceVisitor {
+class AddToReferenceArrayVisitor {
  public:
-  explicit AddIfReachesAllocSpaceVisitor(
-        MarkSweep* const mark_sweep,
+  explicit AddToReferenceArrayVisitor(
+      ModUnionTableReferenceCache* const mod_union_table,
         ModUnionTableReferenceCache::ReferenceArray* references)
-    : mark_sweep_(mark_sweep),
+    : mod_union_table_(mod_union_table),
       references_(references) {
   }
 
   // Extra parameters are required since we use this same visitor signature for checking objects.
-  void operator ()(const Object* /* obj */, const Object* ref, const MemberOffset& /* offset */, bool /* is_static */) const {
-    if (mark_sweep_->heap_->GetAllocSpace()->Contains(ref)) {
+  void operator ()(const Object* obj, const Object* ref, const MemberOffset& /* offset */,
+                     bool /* is_static */) const {
+    // Only add the reference if it fits our criteria.
+    if (mod_union_table_->AddReference(obj, ref)) {
       references_->push_back(ref);
     }
   }
 
  private:
-  MarkSweep* const mark_sweep_;
-  ModUnionTableReferenceCache::ReferenceArray* references_;
+  ModUnionTableReferenceCache* mod_union_table_;
+  ModUnionTable::ReferenceArray* references_;
 };
 
 class ModUnionReferenceVisitor {
  public:
   explicit ModUnionReferenceVisitor(
-        MarkSweep* const mark_sweep,
+        ModUnionTableReferenceCache* const mod_union_table,
         ModUnionTableReferenceCache::ReferenceArray* references)
-    : mark_sweep_(mark_sweep),
+    : mod_union_table_(mod_union_table),
       references_(references) {
   }
 
@@ -221,50 +212,190 @@
     DCHECK(obj != NULL);
     // We don't have an early exit since we use the visitor pattern, an early
     // exit should significantly speed this up.
-    AddIfReachesAllocSpaceVisitor visitor(mark_sweep_, references_);
-    mark_sweep_->VisitObjectReferences(obj, visitor);
+    AddToReferenceArrayVisitor visitor(mod_union_table_, references_);
+    mod_union_table_->GetMarkSweep()->VisitObjectReferences(obj, visitor);
   }
  private:
-  MarkSweep* const mark_sweep_;
-  ModUnionTableReferenceCache::ReferenceArray* references_;
+  ModUnionTableReferenceCache* const mod_union_table_;
+  ModUnionTable::ReferenceArray* references_;
 };
 
-void ModUnionTableReferenceCache::Update(MarkSweep* mark_sweep) {
-  CardTable* card_table = heap_->GetCardTable();
-  while (!cleared_cards_.empty()) {
-    byte* card = cleared_cards_.back();
-    cleared_cards_.pop_back();
 
-    // Update the corresponding references for the card
+class CheckReferenceVisitor {
+ public:
+  typedef std::set<const Object*> ReferenceSet;
+
+  explicit CheckReferenceVisitor(
+      ModUnionTableReferenceCache* const mod_union_table,
+      const ReferenceSet& references)
+    : mod_union_table_(mod_union_table),
+      references_(references) {
+  }
+
+  // Extra parameters are required since we use this same visitor signature for checking objects.
+  void operator ()(const Object* obj, const Object* ref, const MemberOffset& /* offset */, bool /* is_static */) const {
+    Heap* heap = mod_union_table_->GetMarkSweep()->GetHeap();
+    if (mod_union_table_->AddReference(obj, ref) && references_.find(ref) == references_.end()) {
+      Space* from_space = heap->FindSpaceFromObject(obj);
+      Space* to_space = heap->FindSpaceFromObject(ref);
+      LOG(INFO) << "Object " << reinterpret_cast<const void*>(obj) << "(" << PrettyTypeOf(obj) << ")"
+                << "References " << reinterpret_cast<const void*>(ref)
+                << "(" << PrettyTypeOf(ref) << ") without being in mod-union table";
+      LOG(INFO) << "FromSpace " << from_space->GetName() << " type " << from_space->GetGcRetentionPolicy();
+      LOG(INFO) << "ToSpace " << to_space->GetName() << " type " << to_space->GetGcRetentionPolicy();
+      mod_union_table_->GetHeap()->DumpSpaces();
+      LOG(FATAL) << "FATAL ERROR";
+    }
+  }
+
+ private:
+  ModUnionTableReferenceCache* const mod_union_table_;
+  const ReferenceSet& references_;
+};
+
+class ModUnionCheckReferences {
+ public:
+  typedef std::set<const Object*> ReferenceSet;
+
+  explicit ModUnionCheckReferences (
+      ModUnionTableReferenceCache* const mod_union_table,
+      const ReferenceSet& references)
+    : mod_union_table_(mod_union_table),
+      references_(references) {
+  }
+
+  void operator ()(Object* obj) const {
+    DCHECK(obj != NULL);
+    MarkSweep* mark_sweep = mod_union_table_->GetMarkSweep();
+    CheckReferenceVisitor visitor(mod_union_table_, references_);
+    mark_sweep->VisitObjectReferences(obj, visitor);
+  }
+
+ private:
+  ModUnionTableReferenceCache* const mod_union_table_;
+  const ReferenceSet& references_;
+};
+
+void ModUnionTableReferenceCache::Verify() {
+#if VERIFY_MOD_UNION
+  // Start by checking that everything in the mod union table is marked.
+  Heap* heap = GetMarkSweep()->GetHeap();
+  for (ReferenceMap::const_iterator it = references_.begin(); it != references_.end(); ++it) {
+    for (ReferenceArray::const_iterator it_ref = it->second.begin(); it_ref != it->second.end(); ++it_ref ) {
+      DCHECK(heap->GetLiveBitmap()->Test(*it_ref));
+    }
+  }
+
+  // Check the references of each clean card which is also in the mod union table.
+  for (ReferenceMap::const_iterator it = references_.begin(); it != references_.end(); ++it) {
+    const byte* card = &*it->first;
+    if (*card == GC_CARD_CLEAN) {
+      std::set<const Object*> reference_set;
+      for (ReferenceArray::const_iterator itr = it->second.begin(); itr != it->second.end();++itr) {
+        reference_set.insert(*itr);
+      }
+      ModUnionCheckReferences visitor(this, reference_set);
+      CardTable* card_table = heap->GetCardTable();
+      uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card));
+      uintptr_t end = start + GC_CARD_SIZE;
+      SpaceBitmap* live_bitmap =
+              heap->FindSpaceFromObject(reinterpret_cast<Object*>(start))->GetLiveBitmap();
+      live_bitmap->VisitMarkedRange(start, end, visitor);
+    }
+  }
+#endif
+}
+
+void ModUnionTableReferenceCache::Update() {
+  Heap* heap = GetMarkSweep()->GetHeap();
+  CardTable* card_table = heap->GetCardTable();
+
+  ReferenceArray cards_references;
+  ModUnionReferenceVisitor visitor(this, &cards_references);
+
+  for (size_t i = 0; i < cleared_cards_.size(); ++i) {
+    byte* card = cleared_cards_[i];
+
+    // Clear and re-compute alloc space references associated with this card.
+    cards_references.clear();
+    uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card));
+    uintptr_t end = start + GC_CARD_SIZE;
+    SpaceBitmap* live_bitmap =
+        heap->FindSpaceFromObject(reinterpret_cast<Object*>(start))->GetLiveBitmap();
+    live_bitmap->VisitMarkedRange(start, end, visitor);
+
+    // Update the corresponding references for the card.
     // TODO: C++0x auto
     ReferenceMap::iterator found = references_.find(card);
     if (found == references_.end()) {
-      references_.Put(card, ReferenceArray());
-      found = references_.find(card);
+      if (cards_references.empty()) {
+        // No reason to add empty array.
+        continue;
+      }
+      references_.Put(card, cards_references);
+    } else {
+      found->second = cards_references;
     }
-
-    // Clear and re-compute alloc space references associated with this card.
-    ReferenceArray& cards_references = found->second;
-    cards_references.clear();
-    ModUnionReferenceVisitor visitor(mark_sweep, &cards_references);
-    uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card));
-    uintptr_t end = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card + 1));
-    SpaceBitmap* live_bitmap =
-        heap_->FindSpaceFromObject(reinterpret_cast<Object*>(start))->GetLiveBitmap();
-    live_bitmap->VisitMarkedRange(start, end, visitor);
   }
+  cleared_cards_.clear();
 }
 
-void ModUnionTableReferenceCache::MarkReferences(MarkSweep* mark_sweep) {
+void ModUnionTableReferenceCache::MarkReferences() {
+  Heap* heap = GetMarkSweep()->GetHeap();
+  HeapBitmap* mark_bitmap = heap->GetMarkBitmap();
   // TODO: C++0x auto
   size_t count = 0;
   for (ReferenceMap::const_iterator it = references_.begin(); it != references_.end(); ++it) {
     for (ReferenceArray::const_iterator it_ref = it->second.begin(); it_ref != it->second.end(); ++it_ref ) {
-      mark_sweep->MarkObject(*it_ref);
+      mark_bitmap->Set(*it_ref);
       ++count;
     }
   }
-  VLOG(heap) << "Marked " << count << " references in mod union table";
+  if (VLOG_IS_ON(heap)) {
+    VLOG(gc) << "Marked " << count << " references in mod union table";
+  }
+}
+
+ModUnionTableCardCache::ModUnionTableCardCache(Heap* heap) : ModUnionTable(heap) {
+
+}
+
+ModUnionTableCardCache::~ModUnionTableCardCache() {
+
+}
+
+class ModUnionClearCardSetVisitor {
+ public:
+  explicit ModUnionClearCardSetVisitor(std::set<byte*>* const cleared_cards)
+    : cleared_cards_(cleared_cards) {
+  }
+
+  void operator ()(byte* card) const {
+    cleared_cards_->insert(card);
+  }
+ private:
+  std::set<byte*>* const cleared_cards_;
+};
+
+void ModUnionTableCardCache::ClearCards(Space* space) {
+  CardTable* card_table = GetMarkSweep()->GetHeap()->GetCardTable();
+  ModUnionClearCardSetVisitor visitor(&cleared_cards_);
+  // Clear dirty cards in the this space and update the corresponding mod-union bits.
+  card_table->VisitClear(space->Begin(), space->End(), visitor);
+}
+
+// Mark all references to the alloc space(s).
+void ModUnionTableCardCache::MarkReferences() {
+  CardTable* card_table = heap_->GetCardTable();
+  ModUnionScanImageRootVisitor visitor(GetMarkSweep());
+  for (ClearedCards::const_iterator it = cleared_cards_.begin(); it != cleared_cards_.end(); ++it) {
+    byte* card = *it;
+    uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card));
+    uintptr_t end = start + GC_CARD_SIZE;
+    SpaceBitmap* live_bitmap =
+        heap_->FindSpaceFromObject(reinterpret_cast<Object*>(start))->GetLiveBitmap();
+    live_bitmap->VisitMarkedRange(start, end, visitor);
+  }
 }
 
 }  // namespace art
diff --git a/src/mod_union_table.h b/src/mod_union_table.h
index a9111ee..f41fc32 100644
--- a/src/mod_union_table.h
+++ b/src/mod_union_table.h
@@ -17,7 +17,11 @@
 #ifndef ART_SRC_MOD_UNION_TABLE_H_
 #define ART_SRC_MOD_UNION_TABLE_H_
 
+#include "heap.h"
 #include "safe_map.h"
+#include "space.h"
+
+#define VERIFY_MOD_UNION 0
 
 namespace art {
 
@@ -25,78 +29,173 @@
 class HeapBitmap;
 class Space;
 
+// Base class
 class ModUnionTable {
  public:
-  // Clear cards image space cards.
-  virtual void ClearCards() = 0;
+  typedef std::vector<const Object*> ReferenceArray;
 
-  // Update the mod-union table.
-  virtual void Update(MarkSweep* mark_sweep) = 0;
+  ModUnionTable(Heap* heap) : heap_(heap), mark_sweep_(0) {
 
-  // Mark all references to the alloc space(s).
-  virtual void MarkReferences(MarkSweep* mark_sweep) = 0;
+  }
 
   virtual ~ModUnionTable() {
 
   }
+
+  // Clear cards which map to a memory range of a space.
+  virtual void ClearCards(Space* space) = 0;
+
+  // Update the mod-union table.
+  virtual void Update() = 0;
+
+  // Mark all references which are stored in the mod union table.
+  virtual void MarkReferences() = 0;
+
+  // Verification, sanity checks that we don't have clean cards which conflict with out cached data
+  // for said cards.
+  virtual void Verify() = 0;
+
+  // Should probably clean this up later.
+  void Init(MarkSweep* mark_sweep) {
+    mark_sweep_ = mark_sweep;
+  }
+
+  MarkSweep* GetMarkSweep() {
+    return mark_sweep_;
+  }
+
+  Heap* GetHeap() {
+    return heap_;
+  }
+
+ protected:
+  Heap* heap_;
+  MarkSweep* mark_sweep_;
 };
 
 // Bitmap implementation.
+// DEPRECATED, performs strictly less well than merely caching which cards were dirty.
 class ModUnionTableBitmap : public ModUnionTable {
  public:
   ModUnionTableBitmap(Heap* heap);
   virtual ~ModUnionTableBitmap();
 
-  void Init();
-
-  // Clear image space cards.
-  void ClearCards();
+  // Clear space cards.
+  void ClearCards(Space* space);
 
   // Update table based on cleared cards.
-  void Update(MarkSweep* mark_sweep);
+  void Update();
 
   // Mark all references to the alloc space(s).
   void MarkReferences(MarkSweep* mark_sweep);
- private:
+
+ protected:
   // Cleared card array, used to update the mod-union table.
   std::vector<byte*> cleared_cards_;
 
   // One bitmap per image space.
-  // TODO: Add support for zygote spaces?
-  typedef SafeMap<Space*,  SpaceBitmap*> BitmapMap;
+  // TODO: Add support for Zygote spaces?
+  typedef SafeMap<Space*, SpaceBitmap*> BitmapMap;
   BitmapMap bitmaps_;
-
-  Heap* heap_;
 };
 
-// Reference caching implementation. Caches references pointing to alloc space(s)
-// for each card.
+// Reference caching implementation. Caches references pointing to alloc space(s) for each card.
 class ModUnionTableReferenceCache : public ModUnionTable {
  public:
-  typedef std::vector<const Object*> ReferenceArray;
   typedef SafeMap<const byte*, ReferenceArray > ReferenceMap;
 
   ModUnionTableReferenceCache(Heap* heap);
   virtual ~ModUnionTableReferenceCache();
 
-  void Init();
-
-  // Clear image space cards.
-  void ClearCards();
+  // Clear and store cards for a space.
+  void ClearCards(Space* space);
 
   // Update table based on cleared cards.
-  void Update(MarkSweep* mark_sweep);
+  void Update();
 
   // Mark all references to the alloc space(s).
-  void MarkReferences(MarkSweep* mark_sweep);
- private:
+  void MarkReferences();
+
+  // Verify the mod-union table.
+  void Verify();
+
+  // Function that tells whether or not to add a reference to the table.
+  virtual bool AddReference(const Object* obj, const Object* ref) = 0;
+
+ protected:
   // Cleared card array, used to update the mod-union table.
   std::vector<byte*> cleared_cards_;
 
   // Maps from dirty cards to their corresponding alloc space references.
   ReferenceMap references_;
+};
 
-  Heap* heap_;
+// Card caching implementation. Keeps track of which cards we cleared and only this information.
+class ModUnionTableCardCache : public ModUnionTable {
+ public:
+  typedef std::set<byte*> ClearedCards;
+  typedef SafeMap<const byte*, ReferenceArray > ReferenceMap;
+
+  ModUnionTableCardCache(Heap* heap);
+  virtual ~ModUnionTableCardCache();
+
+  // Clear and store cards for a space.
+  void ClearCards(Space* space);
+
+  // Nothing to update.
+  void Update() {}
+
+  // Mark all references to the alloc space(s).
+  void MarkReferences();
+
+  // Nothing to verify.
+  void Verify() {}
+
+ protected:
+  // Cleared card array, used to update the mod-union table.
+  ClearedCards cleared_cards_;
+};
+
+template <typename Implementation>
+class ModUnionTableToZygoteAllocspace : public Implementation {
+public:
+  ModUnionTableToZygoteAllocspace(Heap* heap) : Implementation(heap) {
+  }
+
+  bool AddReference(const Object* /* obj */, const Object* ref) {
+    const Spaces& spaces = Implementation::GetMarkSweep()->GetHeap()->GetSpaces();
+    for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
+      if ((*it)->Contains(ref)) {
+        return (*it)->IsAllocSpace();
+      }
+    }
+    if (ref != NULL) {
+      Implementation::GetHeap()->DumpSpaces();
+      LOG(FATAL) << "Reference " << ref << " not in any space!";
+    }
+    return false;
+  }
+};
+
+template <typename Implementation>
+class ModUnionTableToAllocspace : public Implementation {
+public:
+  ModUnionTableToAllocspace(Heap* heap) : Implementation(heap) {
+  }
+
+  bool AddReference(const Object* /* obj */, const Object* ref) {
+    const Spaces& spaces = Implementation::GetMarkSweep()->GetHeap()->GetSpaces();
+    for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
+      if ((*it)->Contains(ref)) {
+        return (*it)->GetGcRetentionPolicy() == GCRP_ALWAYS_COLLECT;
+      }
+    }
+    if (ref != NULL) {
+      Implementation::GetHeap()->DumpSpaces();
+      LOG(FATAL) << "Reference " << ref << " not in any space!";
+    }
+    return false;
+  }
 };
 
 }  // namespace art
diff --git a/src/native/dalvik_system_Zygote.cc b/src/native/dalvik_system_Zygote.cc
index 3323a23..4fb8397 100644
--- a/src/native/dalvik_system_Zygote.cc
+++ b/src/native/dalvik_system_Zygote.cc
@@ -295,7 +295,7 @@
                                      jstring java_se_info, jstring java_se_name, bool is_system_server) {
   Runtime* runtime = Runtime::Current();
   CHECK(runtime->IsZygote()) << "runtime instance not started with -Xzygote";
-  if (false) { // TODO: do we need do anything special like !dvmGcPreZygoteFork()?
+  if (!runtime->PreZygoteFork()) {
     LOG(FATAL) << "pre-fork heap failed";
   }
 
diff --git a/src/runtime.cc b/src/runtime.cc
index 79f75c7..ae4f16e 100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -222,6 +222,11 @@
   // notreached
 }
 
+bool Runtime::PreZygoteFork() {
+  heap_->PreZygoteFork();
+  return true;
+}
+
 void Runtime::CallExitHook(jint status) {
   if (exit_ != NULL) {
     ScopedThreadStateChange tsc(Thread::Current(), kNative);
diff --git a/src/runtime.h b/src/runtime.h
index b5c3608..c583ab1 100644
--- a/src/runtime.h
+++ b/src/runtime.h
@@ -310,6 +310,7 @@
   void SetStatsEnabled(bool new_state);
 
   void DidForkFromZygote();
+  bool PreZygoteFork();
 
   void EnableMethodTracing(Trace* tracer);
   void DisableMethodTracing();
diff --git a/src/space.cc b/src/space.cc
index 3d8c5e0..24eca26 100644
--- a/src/space.cc
+++ b/src/space.cc
@@ -22,6 +22,7 @@
 #include "image.h"
 #include "logging.h"
 #include "os.h"
+#include "space_bitmap.h"
 #include "stl_util.h"
 #include "utils.h"
 
@@ -42,13 +43,16 @@
 
 size_t AllocSpace::bitmap_index_ = 0;
 
-AllocSpace::AllocSpace(const std::string& name, MemMap* mem_map, void* mspace, byte* end,
+AllocSpace::AllocSpace(const std::string& name, MemMap* mem_map, void* mspace, byte* begin, byte* end,
                        size_t growth_limit)
-    : Space(name, mem_map, end), mspace_(mspace), growth_limit_(growth_limit) {
+    : Space(name, mem_map, begin, end, GCRP_ALWAYS_COLLECT), mspace_(mspace), growth_limit_(growth_limit) {
   CHECK(mspace != NULL);
 
   size_t bitmap_index = bitmap_index_++;
 
+  DCHECK(reinterpret_cast<uintptr_t>(mem_map->Begin()) % static_cast<uintptr_t>GC_CARD_SIZE == 0);
+  DCHECK(reinterpret_cast<uintptr_t>(mem_map->End()) % static_cast<uintptr_t>GC_CARD_SIZE == 0);
+
   live_bitmap_.reset(SpaceBitmap::Create(
       StringPrintf("allocspace-%s-live-bitmap-%d", name.c_str(), static_cast<int>(bitmap_index)),
       Begin(), Capacity()));
@@ -120,7 +124,8 @@
   }
 
   // Everything is set so record in immutable structure and leave
-  AllocSpace* space = new AllocSpace(name, mem_map.release(), mspace, end, growth_limit);
+  MemMap* mem_map_ptr = mem_map.release();
+  AllocSpace* space = new AllocSpace(name, mem_map_ptr, mspace, mem_map_ptr->Begin(), end, growth_limit);
   if (VLOG_IS_ON(heap) || VLOG_IS_ON(startup)) {
     LOG(INFO) << "Space::CreateAllocSpace exiting (" << PrettyDuration(NanoTime() - start_time)
         << " ) " << *space;
@@ -176,6 +181,50 @@
   return result;
 }
 
+AllocSpace* AllocSpace::CreateZygoteSpace() {
+  end_ = reinterpret_cast<byte*>(RoundUp(reinterpret_cast<uintptr_t>(end_), kPageSize));
+  DCHECK(IsAligned<GC_CARD_SIZE>(begin_));
+  DCHECK(IsAligned<GC_CARD_SIZE>(end_));
+  DCHECK(IsAligned<kPageSize>(begin_));
+  DCHECK(IsAligned<kPageSize>(end_));
+  size_t size = RoundUp(Size(), kPageSize);
+  // Trim the heap so that we minimize the size of the Zygote space.
+  Trim();
+  // Trim our mem-map to free unused pages.
+  mem_map_->UnMapAtEnd(end_);
+  // TODO: Not hardcode these in?
+  const size_t starting_size = kPageSize;
+  const size_t initial_size = 2 * MB;
+  // Remaining size is for the new alloc space.
+  const size_t growth_limit = growth_limit_ - size;
+  const size_t capacity = Capacity() - size;
+  VLOG(heap) << "Begin " << reinterpret_cast<const void*>(begin_);
+  VLOG(heap) << "End " << reinterpret_cast<const void*>(end_);
+  VLOG(heap) << "Size " << size;
+  VLOG(heap) << "GrowthLimit " << growth_limit_;
+  VLOG(heap) << "Capacity " << Capacity();
+  growth_limit_ = RoundUp(size, kPageSize);
+  // FIXME: Do we need reference counted pointers here?
+  // Make the two spaces share the same mark bitmaps since the bitmaps span both of the spaces.
+  VLOG(heap) << "Creating new alloc space: ";
+  VLOG(heap) << "Size " << mem_map_->Size();
+  VLOG(heap) << "GrowthLimit " << PrettySize(growth_limit);
+  VLOG(heap) << "Capacity " << PrettySize(capacity);
+  UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name_.c_str(), end_, capacity, PROT_READ | PROT_WRITE));
+  void* mspace = CreateMallocSpace(end_, starting_size, initial_size);
+  // Protect memory beyond the initial size.
+  byte* end = mem_map->Begin() + starting_size;
+  if (capacity - initial_size > 0) {
+    CHECK_MEMORY_CALL(mprotect, (end, capacity - initial_size, PROT_NONE), name_.c_str());
+  }
+  AllocSpace* alloc_space = new AllocSpace(name_, mem_map.release(), mspace, end_, end, growth_limit);
+  live_bitmap_->Trim(Capacity()); // TODO - kPageSize?
+  mark_bitmap_->Trim(Capacity()); // TODO - kPageSize?
+  name_ += "-zygote-transformed";
+  VLOG(heap) << "zygote space creation done";
+  return alloc_space;
+}
+
 void AllocSpace::Free(Object* ptr) {
 #if DEBUG_SPACES
   CHECK(ptr != NULL);
@@ -309,7 +358,7 @@
 size_t ImageSpace::bitmap_index_ = 0;
 
 ImageSpace::ImageSpace(const std::string& name, MemMap* mem_map)
-    : Space(name, mem_map, mem_map->End()) {
+    : Space(name, mem_map, mem_map->Begin(), mem_map->End(), GCRP_NEVER_COLLECT) {
   const size_t bitmap_index = bitmap_index_++;
   live_bitmap_.reset(SpaceBitmap::Create(
       StringPrintf("imagespace-%s-live-bitmap-%d", name.c_str(), static_cast<int>(bitmap_index)),
diff --git a/src/space.h b/src/space.h
index be0fb61..1aeb33e 100644
--- a/src/space.h
+++ b/src/space.h
@@ -33,6 +33,13 @@
 class Object;
 class SpaceBitmap;
 
+enum GcRetentionPolicy {
+  GCRP_NEVER_COLLECT,
+  GCRP_ALWAYS_COLLECT,
+  GCRP_FULL_COLLECT,
+};
+std::ostream& operator<<(std::ostream& os, const GcRetentionPolicy& policy);
+
 // A space contains memory allocated for managed objects.
 class Space {
  public:
@@ -85,6 +92,14 @@
     return Capacity();
   }
 
+  GcRetentionPolicy GetGcRetentionPolicy() const {
+    return gc_retention_policy_;
+  }
+
+  void SetGcRetentionPolicy(GcRetentionPolicy gc_retention_policy) {
+    gc_retention_policy_ = gc_retention_policy;
+  }
+
   ImageSpace* AsImageSpace() {
     DCHECK(IsImageSpace());
     return down_cast<ImageSpace*>(this);
@@ -97,6 +112,7 @@
 
   virtual bool IsAllocSpace() const = 0;
   virtual bool IsImageSpace() const = 0;
+  virtual bool IsZygoteSpace() const = 0;
 
   virtual SpaceBitmap* GetLiveBitmap() const = 0;
   virtual SpaceBitmap* GetMarkBitmap() const = 0;
@@ -106,8 +122,12 @@
   }
 
  protected:
-  Space(const std::string& name, MemMap* mem_map, byte* end)
-      : name_(name), mem_map_(mem_map), begin_(mem_map->Begin()), end_(end) {}
+  Space(const std::string& name, MemMap* mem_map, byte* begin, byte* end, GcRetentionPolicy gc_retention_policy)
+      : name_(name),
+        mem_map_(mem_map),
+        begin_(begin),
+        end_(end),
+        gc_retention_policy_(gc_retention_policy) {}
 
   std::string name_;
 
@@ -117,9 +137,12 @@
   // The beginning of the storage for fast access (always equals mem_map_->GetAddress())
   byte* const begin_;
 
-  // Current end of the space
+  // Current end of the space.
   byte* end_;
 
+  // Garbage collection retention policy, used to figure out when we should sweep over this space.
+  GcRetentionPolicy gc_retention_policy_;
+
   DISALLOW_COPY_AND_ASSIGN(Space);
 };
 
@@ -180,13 +203,17 @@
   }
 
   virtual bool IsAllocSpace() const {
-    return true;
+    return gc_retention_policy_ != GCRP_NEVER_COLLECT;
   }
 
   virtual bool IsImageSpace() const {
     return false;
   }
 
+  virtual bool IsZygoteSpace() const {
+    return gc_retention_policy_ == GCRP_FULL_COLLECT;
+  }
+
   virtual SpaceBitmap* GetLiveBitmap() const {
     return live_bitmap_.get();
   }
@@ -198,6 +225,9 @@
   // Swap the live and mark bitmaps of this space. This is used by the GC for concurrent sweeping.
   void SwapBitmaps();
 
+  // Turn ourself into a zygote space and return a new alloc space which has our unused memory.
+  AllocSpace* CreateZygoteSpace();
+
  private:
   friend class Space;
 
@@ -205,7 +235,7 @@
   UniquePtr<SpaceBitmap> mark_bitmap_;
   static size_t bitmap_index_;
 
-  AllocSpace(const std::string& name, MemMap* mem_map, void* mspace, byte* end,
+  AllocSpace(const std::string& name, MemMap* mem_map, void* mspace, byte* begin, byte* end,
              size_t growth_limit);
 
   bool Init(size_t initial_size, size_t maximum_size, size_t growth_size, byte* requested_base);
@@ -252,11 +282,17 @@
     return true;
   }
 
+  virtual bool IsZygoteSpace() const {
+    return false;
+  }
+
   virtual SpaceBitmap* GetLiveBitmap() const {
    return live_bitmap_.get();
  }
 
  virtual SpaceBitmap* GetMarkBitmap() const {
+   // ImageSpaces have the same bitmap for both live and marked. This helps reduce the number of
+   // special cases to test against.
    return live_bitmap_.get();
  }
 
diff --git a/src/space_bitmap.cc b/src/space_bitmap.cc
index 28dee45..74bc07c 100644
--- a/src/space_bitmap.cc
+++ b/src/space_bitmap.cc
@@ -38,6 +38,17 @@
 // Clean up any resources associated with the bitmap.
 SpaceBitmap::~SpaceBitmap() {}
 
+void SpaceBitmap::Trim(size_t heap_capacity) {
+  size_t new_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize;
+  if (new_size < bitmap_size_) {
+    bitmap_size_ = new_size;
+  }
+  // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity
+  // should be marked.
+  // TODO: Fix this code is, it broken and causes rare heap corruption!
+  // mem_map_->Trim(reinterpret_cast<byte*>(heap_begin_ + bitmap_size_));
+}
+
 // Fill the bitmap with zeroes.  Returns the bitmap's memory to the
 // system as a side-effect.
 void SpaceBitmap::Clear() {
@@ -61,24 +72,6 @@
   return index < bitmap_size_ / kWordSize;
 }
 
-void SpaceBitmap::VisitRange(uintptr_t visit_begin, uintptr_t visit_end, Callback* visitor, void* arg) const {
-  size_t start = OffsetToIndex(visit_begin - heap_begin_);
-  size_t end = OffsetToIndex(visit_end - heap_begin_ - 1);
-  for (size_t i = start; i <= end; i++) {
-    word w = bitmap_begin_[i];
-    if (w != 0) {
-      word high_bit = 1 << (kBitsPerWord - 1);
-      uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
-      while (w != 0) {
-        const int shift = CLZ(w);
-        Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
-        (*visitor)(obj, arg);
-        w &= ~(high_bit >> shift);
-      }
-    }
-  }
-}
-
 // Visits set bits in address order.  The callback is not permitted to
 // change the bitmap bits or max during the traversal.
 void SpaceBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) {
@@ -116,11 +109,24 @@
   CHECK(callback != NULL);
   CHECK_LE(scan_begin, scan_end);
   CHECK_GE(scan_begin, heap_begin_);
-  size_t start = OffsetToIndex(scan_begin - heap_begin_);
+
+  // This function doesn't support unaligned boundaries yet.
+  size_t begin_offset = scan_begin - heap_begin_;
+  size_t end_offset = scan_end - heap_begin_;
+  DCHECK((begin_offset / kAlignment) % kBitsPerWord == 0)
+      << "scan begin " << reinterpret_cast<const void*>(scan_begin)
+      << " with offset " << begin_offset
+      << " not aligned to word boundary";
+  DCHECK((end_offset / kAlignment) % kBitsPerWord == 0)
+      << "scan end " << reinterpret_cast<const void*>(scan_end)
+      << " with offset " << end_offset
+      << " not aligned to word boundary";
+
+  size_t start = OffsetToIndex(begin_offset);
   if (scan_end < heap_end_) {
     // The end of the space we're looking at is before the current maximum bitmap PC, scan to that
     // and don't recompute end on each iteration
-    size_t end = OffsetToIndex(scan_end - heap_begin_ - 1);
+    size_t end = OffsetToIndex(end_offset - 1);
     for (size_t i = start; i <= end; i++) {
       word w = bitmap_begin_[i];
       if (UNLIKELY(w != 0)) {
diff --git a/src/space_bitmap.h b/src/space_bitmap.h
index fa79d5d..1e8a9a7 100644
--- a/src/space_bitmap.h
+++ b/src/space_bitmap.h
@@ -60,7 +60,7 @@
 
   // Pack the bits in backwards so they come out in address order when using CLZ.
   static word OffsetToMask(uintptr_t offset_) {
-    return 1 << (sizeof(word) * 8 - 1 - (offset_ / kAlignment) % kBitsPerWord);
+    return 1 << (kBitsPerWord - 1 - (offset_ / kAlignment) % kBitsPerWord);
   }
 
   inline void Set(const Object* obj) {
@@ -112,21 +112,68 @@
 
   template <typename Visitor>
   void VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const {
-    size_t start = OffsetToIndex(visit_begin - heap_begin_);
-    size_t end = OffsetToIndex(visit_end - heap_begin_ - 1);
-    for (size_t i = start; i <= end; i++) {
-      word w = bitmap_begin_[i];
+    DCHECK_LT(visit_begin, visit_end);
+
+    const size_t bit_index_start = (visit_begin - heap_begin_) / kAlignment;
+    const size_t bit_index_end = (visit_end - heap_begin_ - 1) / kAlignment;
+
+    size_t word_start = bit_index_start / kBitsPerWord;
+    size_t word_end = bit_index_end / kBitsPerWord;
+
+    const size_t high_bit = 1 << (kBitsPerWord - 1);
+
+    // Trim off left_bits of left bits.
+    size_t edge_word = bitmap_begin_[word_start];
+
+    // Handle bits on the left first as a special case
+    size_t left_bits = bit_index_start & (kBitsPerWord - 1);
+    if (left_bits != 0) {
+      edge_word &= (1 << (kBitsPerWord - left_bits)) - 1;
+    }
+
+    // If word_start == word_end then handle this case at the same place we handle the right edge.
+    if (edge_word != 0 && word_start < word_end) {
+      uintptr_t ptr_base = IndexToOffset(word_start) + heap_begin_;
+      do {
+        const size_t shift = CLZ(edge_word);
+        Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
+        visitor(obj);
+        edge_word &= ~(high_bit >> shift);
+      } while (edge_word != 0);
+    }
+    word_start++;
+
+    for (size_t i = word_start; i < word_end; i++) {
+      size_t w = bitmap_begin_[i];
       if (w != 0) {
-        word high_bit = 1 << (kBitsPerWord - 1);
         uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
         do {
-          const int shift = CLZ(w);
+          const size_t shift = CLZ(w);
           Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
           visitor(obj);
           w &= ~(high_bit >> shift);
         } while (w != 0);
       }
     }
+
+    // Handle the right edge, and also the left edge if both edges are on the same word.
+    size_t right_bits = bit_index_end & (kBitsPerWord - 1);
+
+    // If word_start == word_end then we need to use the word which we removed the left bits.
+    if (word_start <= word_end) {
+      edge_word = bitmap_begin_[word_end];
+    }
+
+    // Bits that we trim off the right.
+    const size_t trim_bits = kBitsPerWord - 1 - right_bits;
+    edge_word &= ~((1 << trim_bits) - 1);
+    uintptr_t ptr_base = IndexToOffset(word_end) + heap_begin_;
+    while (edge_word != 0) {
+      const int shift = CLZ(edge_word);
+      Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
+      visitor(obj);
+      edge_word &= ~(high_bit >> shift);
+    }
   }
 
   void Walk(Callback* callback, void* arg);
@@ -140,6 +187,27 @@
                         uintptr_t base, uintptr_t max,
                         SweepCallback* thunk, void* arg);
 
+  // Starting address of our internal storage.
+  word* Begin() {
+    return bitmap_begin_;
+  }
+
+  // Size of our internal storage
+  size_t Size() const {
+    return bitmap_size_;
+  }
+
+  // Size in bytes of the memory that the bitmaps spans.
+  size_t HeapSize() const {
+    return IndexToOffset(Size() / kWordSize);
+  }
+
+  uintptr_t HeapBegin() {
+    return heap_begin_;
+  }
+
+  void Trim(size_t heap_capcity);
+
  private:
   // TODO: heap_end_ is initialized so that the heap bitmap is empty, this doesn't require the -1,
   // however, we document that this is expected on heap_end_
@@ -172,7 +240,7 @@
   word* const bitmap_begin_;
 
   // Size of this bitmap.
-  const size_t bitmap_size_;
+  size_t bitmap_size_;
 
   // The base address of the heap, which corresponds to the word containing the first bit in the
   // bitmap.
diff --git a/src/space_bitmap_test.cc b/src/space_bitmap_test.cc
new file mode 100644
index 0000000..a2f1afc
--- /dev/null
+++ b/src/space_bitmap_test.cc
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2012 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 "space_bitmap.h"
+
+#include "common_test.h"
+#include "dlmalloc.h"
+#include "globals.h"
+#include "UniquePtr.h"
+
+#include <stdint.h>
+
+namespace art {
+
+class SpaceBitmapTest : public CommonTest {
+ public:
+};
+
+TEST_F(SpaceBitmapTest, Init) {
+  byte* heap_begin = reinterpret_cast<byte*>(0x10000000);
+  size_t heap_capacity = 16 * MB;
+  UniquePtr<SpaceBitmap> space_bitmap(SpaceBitmap::Create("test-bitmap",
+                                                          heap_begin, heap_capacity));
+  EXPECT_TRUE(space_bitmap.get() != NULL);
+}
+
+class BitmapVerify {
+ public:
+  BitmapVerify(SpaceBitmap* bitmap, const Object* begin, const Object* end)
+    : bitmap_(bitmap),
+      begin_(begin),
+      end_(end) {}
+
+  void operator ()(const Object* obj) {
+    EXPECT_TRUE(obj >= begin_);
+    EXPECT_TRUE(obj <= end_);
+    EXPECT_TRUE(bitmap_->Test(obj) == ((reinterpret_cast<uintptr_t>(obj) & 0xF) != 0));
+  }
+
+  SpaceBitmap* bitmap_;
+  const Object* begin_;
+  const Object* end_;
+};
+
+TEST_F(SpaceBitmapTest, ScanRange) {
+  byte* heap_begin = reinterpret_cast<byte*>(0x10000000);
+  size_t heap_capacity = 16 * MB;
+
+  UniquePtr<SpaceBitmap> space_bitmap(SpaceBitmap::Create("test-bitmap",
+                                                          heap_begin, heap_capacity));
+  EXPECT_TRUE(space_bitmap.get() != NULL);
+
+  // Set all the odd bits in the first BitsPerWord * 3 to one.
+  for (size_t j = 0;j < kBitsPerWord * 3; ++j) {
+    const Object* obj = reinterpret_cast<Object*>(heap_begin + j * SpaceBitmap::kAlignment);
+    if (reinterpret_cast<uintptr_t>(obj) & 0xF) {
+      space_bitmap->Set(obj);
+    }
+  }
+  // Try every possible starting bit in the first word. Then for each starting bit, try each
+  // possible length up to a maximum of kBitsPerWord * 2 - 1 bits.
+  // This handles all the cases, having runs which start and end on the same word, and different
+  // words.
+  for (size_t i = 0; i < static_cast<size_t>(kBitsPerWord); ++i) {
+    Object* start = reinterpret_cast<Object*>(heap_begin + i * SpaceBitmap::kAlignment);
+    for (size_t j = 0; j < static_cast<size_t>(kBitsPerWord * 2); ++j) {
+      Object* end = reinterpret_cast<Object*>(heap_begin + (i + j) * SpaceBitmap::kAlignment);
+      BitmapVerify(space_bitmap.get(), start, end);
+    }
+  }
+}
+
+}  // namespace art
diff --git a/src/space_test.cc b/src/space_test.cc
index 7ac0493..f377a61 100644
--- a/src/space_test.cc
+++ b/src/space_test.cc
@@ -70,6 +70,73 @@
   }
 }
 
+TEST_F(SpaceTest, ZygoteSpace) {
+    AllocSpace* space(Space::CreateAllocSpace("test", 4 * MB, 16 * MB, 16 * MB, NULL));
+    ASSERT_TRUE(space != NULL);
+
+  // Make space findable to the heap, will also delete space when runtime is cleaned up
+    Runtime::Current()->GetHeap()->AddSpace(space);
+
+    // Succeeds, fits without adjusting the footprint limit.
+    Object* ptr1 = space->AllocWithoutGrowth(1 * MB);
+    EXPECT_TRUE(ptr1 != NULL);
+
+    // Fails, requires a higher footprint limit.
+    Object* ptr2 = space->AllocWithoutGrowth(8 * MB);
+    EXPECT_TRUE(ptr2 == NULL);
+
+    // Succeeds, adjusts the footprint.
+    Object* ptr3 = space->AllocWithGrowth(8 * MB);
+    EXPECT_TRUE(ptr3 != NULL);
+
+    // Fails, requires a higher footprint limit.
+    Object* ptr4 = space->AllocWithoutGrowth(8 * MB);
+    EXPECT_TRUE(ptr4 == NULL);
+
+    // Also fails, requires a higher allowed footprint.
+    Object* ptr5 = space->AllocWithGrowth(8 * MB);
+    EXPECT_TRUE(ptr5 == NULL);
+
+    // Release some memory.
+    size_t free3 = space->AllocationSize(ptr3);
+    space->Free(ptr3);
+    EXPECT_LE(8U * MB, free3);
+
+    // Succeeds, now that memory has been freed.
+    void* ptr6 = space->AllocWithGrowth(9 * MB);
+    EXPECT_TRUE(ptr6 != NULL);
+
+    // Final clean up.
+    size_t free1 = space->AllocationSize(ptr1);
+    space->Free(ptr1);
+    EXPECT_LE(1U * MB, free1);
+
+    // Make sure that the zygote space isn't directly at the start of the space.
+    space->AllocWithoutGrowth(1U * MB);
+    space = space->CreateZygoteSpace();
+
+    // Make space findable to the heap, will also delete space when runtime is cleaned up
+    Runtime::Current()->GetHeap()->AddSpace(space);
+
+    // Succeeds, fits without adjusting the footprint limit.
+    ptr1 = space->AllocWithoutGrowth(1 * MB);
+    EXPECT_TRUE(ptr1 != NULL);
+
+    // Fails, requires a higher footprint limit.
+    ptr2 = space->AllocWithoutGrowth(8 * MB);
+    EXPECT_TRUE(ptr2 == NULL);
+
+    // Succeeds, adjusts the footprint.
+    ptr3 = space->AllocWithGrowth(2 * MB);
+    EXPECT_TRUE(ptr3 != NULL);
+    space->Free(ptr3);
+
+    // Final clean up.
+    free1 = space->AllocationSize(ptr1);
+    space->Free(ptr1);
+    EXPECT_LE(1U * MB, free1);
+}
+
 TEST_F(SpaceTest, AllocAndFree) {
   AllocSpace* space(Space::CreateAllocSpace("test", 4 * MB, 16 * MB, 16 * MB, NULL));
   ASSERT_TRUE(space != NULL);