Change card cache mod-union table to use bitmaps

Previously used card sets, using bitmaps saves memory and slightly
increases performance.

Added mod union table test.

Performance EvaluateAndApplyChanges (minimal changes):

Before (card cache image mu table):
UpdateAndMarkImageModUnionTable: Avg: 524.320us
ImageModUnionClearCards: Avg: 54.580us
Native PSS: ~67500kB

After (card cache image mu table):
UpdateAndMarkImageModUnionTable: Avg: 515.600us
ImageModUnionClearCards: Avg: 53.780us
Native PSS: ~66014kB

Native PSS was higher before since the mod_union_table->SetCards()
which happens pre zygote fork was allocating a large amount of
std::nodes.

Bug: 11859910

Change-Id: I956b7e51d5572feec1393ffa618b7b7d8c147b28

8 files changed, 838 insertions, 79 deletions

diff --git a/runtime/gc/accounting/bitmap-inl.h b/runtime/gc/accounting/bitmap-inl.h
new file mode 100644
index 0000000..e87a0c0
--- /dev/null
+++ b/runtime/gc/accounting/bitmap-inl.h
@@ -0,0 +1,152 @@
+/*
+ * Copyright (C) 2015 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_BITMAP_INL_H_
+#define ART_RUNTIME_GC_ACCOUNTING_BITMAP_INL_H_
+
+#include "bitmap.h"
+
+#include <memory>
+
+#include "atomic.h"
+#include "base/logging.h"
+#include "utils.h"
+
+namespace art {
+namespace gc {
+namespace accounting {
+
+inline bool Bitmap::AtomicTestAndSetBit(uintptr_t bit_index) {
+  CheckValidBitIndex(bit_index);
+  const size_t word_index = BitIndexToWordIndex(bit_index);
+  const uintptr_t word_mask = BitIndexToMask(bit_index);
+  auto* atomic_entry = reinterpret_cast<Atomic<uintptr_t>*>(&bitmap_begin_[word_index]);
+  uintptr_t old_word;
+  do {
+    old_word = atomic_entry->LoadRelaxed();
+    // Fast path: The bit is already set.
+    if ((old_word & word_mask) != 0) {
+      DCHECK(TestBit(bit_index));
+      return true;
+    }
+  } while (!atomic_entry->CompareExchangeWeakSequentiallyConsistent(old_word,
+                                                                    old_word | word_mask));
+  DCHECK(TestBit(bit_index));
+  return false;
+}
+
+inline bool Bitmap::TestBit(uintptr_t bit_index) const {
+  CheckValidBitIndex(bit_index);
+  return (bitmap_begin_[BitIndexToWordIndex(bit_index)] & BitIndexToMask(bit_index)) != 0;
+}
+
+template<typename Visitor>
+inline void Bitmap::VisitSetBits(uintptr_t bit_start, uintptr_t bit_end, const Visitor& visitor)
+    const {
+  DCHECK_LE(bit_start, bit_end);
+  CheckValidBitIndex(bit_start);
+  const uintptr_t index_start = BitIndexToWordIndex(bit_start);
+  const uintptr_t index_end = BitIndexToWordIndex(bit_end);
+  if (bit_start != bit_end) {
+    CheckValidBitIndex(bit_end - 1);
+  }
+
+  // Index(begin)  ...    Index(end)
+  // [xxxxx???][........][????yyyy]
+  //      ^                   ^
+  //      |                   #---- Bit of visit_end
+  //      #---- Bit of visit_begin
+  //
+
+  // Left edge.
+  uintptr_t left_edge = bitmap_begin_[index_start];
+  // Clear the lower bits that are not in range.
+  left_edge &= ~((static_cast<uintptr_t>(1) << (bit_start % kBitsPerBitmapWord)) - 1);
+
+  // Right edge. Either unique, or left_edge.
+  uintptr_t right_edge;
+
+  if (index_start < index_end) {
+    // Left edge != right edge.
+
+    // Traverse left edge.
+    if (left_edge != 0) {
+      const uintptr_t ptr_base = WordIndexToBitIndex(index_start);
+      do {
+        const size_t shift = CTZ(left_edge);
+        visitor(ptr_base + shift);
+        left_edge ^= static_cast<uintptr_t>(1) << shift;
+      } while (left_edge != 0);
+    }
+
+    // Traverse the middle, full part.
+    for (size_t i = index_start + 1; i < index_end; ++i) {
+      uintptr_t w = bitmap_begin_[i];
+      if (w != 0) {
+        const uintptr_t ptr_base = WordIndexToBitIndex(i);
+        do {
+          const size_t shift = CTZ(w);
+          visitor(ptr_base + shift);
+          w ^= static_cast<uintptr_t>(1) << shift;
+        } while (w != 0);
+      }
+    }
+
+    // Right edge is unique.
+    // But maybe we don't have anything to do: visit_end starts in a new word...
+    if (bit_end == 0) {
+      // Do not read memory, as it could be after the end of the bitmap.
+      right_edge = 0;
+    } else {
+      right_edge = bitmap_begin_[index_end];
+    }
+  } else {
+    right_edge = left_edge;
+  }
+
+  // Right edge handling.
+  right_edge &= ((static_cast<uintptr_t>(1) << (bit_end % kBitsPerBitmapWord)) - 1);
+  if (right_edge != 0) {
+    const uintptr_t ptr_base = WordIndexToBitIndex(index_end);
+    do {
+      const size_t shift = CTZ(right_edge);
+      visitor(ptr_base + shift);
+      right_edge ^= (static_cast<uintptr_t>(1)) << shift;
+    } while (right_edge != 0);
+  }
+}
+
+template<bool kSetBit>
+inline bool Bitmap::ModifyBit(uintptr_t bit_index) {
+  CheckValidBitIndex(bit_index);
+  const size_t word_index = BitIndexToWordIndex(bit_index);
+  const uintptr_t word_mask = BitIndexToMask(bit_index);
+  uintptr_t* address = &bitmap_begin_[word_index];
+  uintptr_t old_word = *address;
+  if (kSetBit) {
+    *address = old_word | word_mask;
+  } else {
+    *address = old_word & ~word_mask;
+  }
+  DCHECK_EQ(TestBit(bit_index), kSetBit);
+  return (old_word & word_mask) != 0;
+}
+
+}  // namespace accounting
+}  // namespace gc
+}  // namespace art
+
+#endif  // ART_RUNTIME_GC_ACCOUNTING_BITMAP_INL_H_
diff --git a/runtime/gc/accounting/bitmap.cc b/runtime/gc/accounting/bitmap.cc
new file mode 100644
index 0000000..de47f60
--- /dev/null
+++ b/runtime/gc/accounting/bitmap.cc
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2015 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 "bitmap-inl.h"
+
+#include "card_table.h"
+#include "mem_map.h"
+
+namespace art {
+namespace gc {
+namespace accounting {
+
+Bitmap* Bitmap::CreateFromMemMap(MemMap* mem_map, size_t num_bits) {
+  CHECK(mem_map != nullptr);
+  return new Bitmap(mem_map, num_bits);
+}
+
+Bitmap::Bitmap(MemMap* mem_map, size_t bitmap_size)
+    : mem_map_(mem_map), bitmap_begin_(reinterpret_cast<uintptr_t*>(mem_map->Begin())),
+      bitmap_size_(bitmap_size) {
+  CHECK(bitmap_begin_ != nullptr);
+  CHECK_NE(bitmap_size, 0U);
+}
+
+MemMap* Bitmap::AllocateMemMap(const std::string& name, size_t num_bits) {
+  const size_t bitmap_size = RoundUp(
+      RoundUp(num_bits, kBitsPerBitmapWord) / kBitsPerBitmapWord * sizeof(uintptr_t), kPageSize);
+  std::string error_msg;
+  std::unique_ptr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), nullptr, bitmap_size,
+                                                       PROT_READ | PROT_WRITE, false, &error_msg));
+  if (UNLIKELY(mem_map.get() == nullptr)) {
+    LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg;
+    return nullptr;
+  }
+  return mem_map.release();
+}
+
+Bitmap* Bitmap::Create(const std::string& name, size_t num_bits) {
+  auto* const mem_map = AllocateMemMap(name, num_bits);
+  if (mem_map == nullptr) {
+    return nullptr;
+  }
+  return CreateFromMemMap(mem_map, num_bits);
+}
+
+void Bitmap::Clear() {
+  if (bitmap_begin_ != nullptr) {
+    mem_map_->MadviseDontNeedAndZero();
+  }
+}
+
+void Bitmap::CopyFrom(Bitmap* source_bitmap) {
+  DCHECK_EQ(BitmapSize(), source_bitmap->BitmapSize());
+  std::copy(source_bitmap->Begin(),
+            source_bitmap->Begin() + BitmapSize() / kBitsPerBitmapWord, Begin());
+}
+
+template<size_t kAlignment>
+MemoryRangeBitmap<kAlignment>* MemoryRangeBitmap<kAlignment>::Create(
+    const std::string& name, uintptr_t cover_begin, uintptr_t cover_end) {
+  CHECK_ALIGNED(cover_begin, kAlignment);
+  CHECK_ALIGNED(cover_end, kAlignment);
+  const size_t num_bits = (cover_end - cover_begin) / kAlignment;
+  auto* const mem_map = Bitmap::AllocateMemMap(name, num_bits);
+  return CreateFromMemMap(mem_map, cover_begin, num_bits);
+}
+
+template<size_t kAlignment>
+MemoryRangeBitmap<kAlignment>* MemoryRangeBitmap<kAlignment>::CreateFromMemMap(
+    MemMap* mem_map, uintptr_t begin, size_t num_bits) {
+  return new MemoryRangeBitmap(mem_map, begin, num_bits);
+}
+
+template class MemoryRangeBitmap<CardTable::kCardSize>;
+
+}  // namespace accounting
+}  // namespace gc
+}  // namespace art
+
diff --git a/runtime/gc/accounting/bitmap.h b/runtime/gc/accounting/bitmap.h
new file mode 100644
index 0000000..cf2c293
--- /dev/null
+++ b/runtime/gc/accounting/bitmap.h
@@ -0,0 +1,192 @@
+/*
+ * Copyright (C) 2015 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_BITMAP_H_
+#define ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
+
+#include <limits.h>
+#include <stdint.h>
+#include <memory>
+#include <set>
+#include <vector>
+
+#include "base/mutex.h"
+#include "globals.h"
+#include "object_callbacks.h"
+
+namespace art {
+
+class MemMap;
+
+namespace gc {
+namespace accounting {
+
+// TODO: Use this code to implement SpaceBitmap.
+class Bitmap {
+ public:
+  // Create and initialize a bitmap with size num_bits. Storage is allocated with a MemMap.
+  static Bitmap* Create(const std::string& name, size_t num_bits);
+
+  // Initialize a space bitmap using the provided mem_map as the live bits. Takes ownership of the
+  // mem map. The address range covered starts at heap_begin and is of size equal to heap_capacity.
+  // Objects are kAlignement-aligned.
+  static Bitmap* CreateFromMemMap(MemMap* mem_map, size_t num_bits);
+
+  // offset is the difference from base to a index.
+  static ALWAYS_INLINE constexpr size_t BitIndexToWordIndex(uintptr_t offset) {
+    return offset / kBitsPerBitmapWord;
+  }
+
+  template<typename T>
+  static ALWAYS_INLINE constexpr T WordIndexToBitIndex(T word_index) {
+    return static_cast<T>(word_index * kBitsPerBitmapWord);
+  }
+
+  static ALWAYS_INLINE constexpr uintptr_t BitIndexToMask(uintptr_t bit_index) {
+    return static_cast<uintptr_t>(1) << (bit_index % kBitsPerBitmapWord);
+  }
+
+  ALWAYS_INLINE bool SetBit(size_t bit_index) {
+    return ModifyBit<true>(bit_index);
+  }
+
+  ALWAYS_INLINE bool ClearBit(size_t bit_index) {
+    return ModifyBit<false>(bit_index);
+  }
+
+  ALWAYS_INLINE bool TestBit(size_t bit_index) const;
+
+  // Returns true if the bit_index was previously set.
+  ALWAYS_INLINE bool AtomicTestAndSetBit(size_t bit_index);
+
+  // Fill the bitmap with zeroes.  Returns the bitmap's memory to the system as a side-effect.
+  void Clear();
+
+  // Visit the all the set bits range [visit_begin, visit_end) where visit_begin and visit_end are
+  // bit indices visitor is called with the index of each set bit.
+  template <typename Visitor>
+  void VisitSetBits(uintptr_t visit_begin, size_t visit_end, const Visitor& visitor) const;
+
+  void CopyFrom(Bitmap* source_bitmap);
+
+  // Starting address of our internal storage.
+  uintptr_t* Begin() {
+    return bitmap_begin_;
+  }
+
+  // Size of our bitmap in bits.
+  size_t BitmapSize() const {
+    return bitmap_size_;
+  }
+
+  // Check that a bit index is valid with a DCHECK.
+  ALWAYS_INLINE void CheckValidBitIndex(size_t bit_index) const {
+    DCHECK_LT(bit_index, BitmapSize());
+  }
+
+  std::string Dump() const;
+
+ protected:
+  static constexpr size_t kBitsPerBitmapWord = sizeof(uintptr_t) * kBitsPerByte;
+
+  Bitmap(MemMap* mem_map, size_t bitmap_size);
+
+  // Allocate the mem-map for a bitmap based on how many bits are required.
+  static MemMap* AllocateMemMap(const std::string& name, size_t num_bits);
+
+  template<bool kSetBit>
+  ALWAYS_INLINE bool ModifyBit(uintptr_t bit_index);
+
+  // Backing storage for bitmap.
+  std::unique_ptr<MemMap> mem_map_;
+
+  // This bitmap itself, word sized for efficiency in scanning.
+  uintptr_t* const bitmap_begin_;
+
+  // Number of bits in the bitmap.
+  const size_t bitmap_size_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(Bitmap);
+};
+
+// One bit per kAlignment in range (start, end]
+template<size_t kAlignment>
+class MemoryRangeBitmap : public Bitmap {
+ public:
+  static MemoryRangeBitmap* Create(const std::string& name, uintptr_t cover_begin,
+                                   uintptr_t cover_end);
+  static MemoryRangeBitmap* CreateFromMemMap(MemMap* mem_map, uintptr_t cover_begin,
+                                             size_t num_bits);
+
+  // Beginning of the memory range that the bitmap covers.
+  ALWAYS_INLINE uintptr_t CoverBegin() const {
+    return cover_begin_;
+  }
+
+  // End of the memory range that the bitmap covers.
+  ALWAYS_INLINE uintptr_t CoverEnd() const {
+    return cover_end_;
+  }
+
+  // Return the address associated with a bit index.
+  ALWAYS_INLINE uintptr_t AddrFromBitIndex(size_t bit_index) const {
+    const uintptr_t addr = CoverBegin() + bit_index * kAlignment;
+    DCHECK_EQ(BitIndexFromAddr(addr), bit_index);
+    return addr;
+  }
+
+  // Return the bit index associated with an address .
+  ALWAYS_INLINE uintptr_t BitIndexFromAddr(uintptr_t addr) const {
+    DCHECK(HasAddress(addr)) << CoverBegin() << " <= " <<  addr << " < " << CoverEnd();
+    return (addr - CoverBegin()) / kAlignment;
+  }
+
+  ALWAYS_INLINE bool HasAddress(const uintptr_t addr) const {
+    return cover_begin_ <= addr && addr < cover_end_;
+  }
+
+  ALWAYS_INLINE bool Set(uintptr_t addr) {
+    return SetBit(BitIndexFromAddr(addr));
+  }
+
+  ALWAYS_INLINE bool Clear(size_t addr) {
+    return ClearBit(BitIndexFromAddr(addr));
+  }
+
+  ALWAYS_INLINE bool Test(size_t addr) const {
+    return TestBit(BitIndexFromAddr(addr));
+  }
+
+  // Returns true if the object was previously set.
+  ALWAYS_INLINE bool AtomicTestAndSet(size_t addr) {
+    return AtomicTestAndSetBit(BitIndexFromAddr(addr));
+  }
+
+ private:
+  MemoryRangeBitmap(MemMap* mem_map, uintptr_t begin, size_t num_bits)
+     : Bitmap(mem_map, num_bits), cover_begin_(begin), cover_end_(begin + kAlignment * num_bits) {
+  }
+
+  uintptr_t const cover_begin_;
+  uintptr_t const cover_end_;
+};
+
+}  // namespace accounting
+}  // namespace gc
+}  // namespace art
+
+#endif  // ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
diff --git a/runtime/gc/accounting/mod_union_table.cc b/runtime/gc/accounting/mod_union_table.cc
index b1ccc0b..a3fac58 100644
--- a/runtime/gc/accounting/mod_union_table.cc
+++ b/runtime/gc/accounting/mod_union_table.cc
@@ -19,6 +19,7 @@
 #include <memory>
 
 #include "base/stl_util.h"
+#include "bitmap-inl.h"
 #include "card_table-inl.h"
 #include "heap_bitmap.h"
 #include "gc/accounting/space_bitmap-inl.h"
@@ -40,14 +41,14 @@ namespace art {
 namespace gc {
 namespace accounting {
 
-class ModUnionClearCardSetVisitor {
+class ModUnionAddToCardSetVisitor {
  public:
-  explicit ModUnionClearCardSetVisitor(ModUnionTable::CardSet* const cleared_cards)
-    : cleared_cards_(cleared_cards) {
+  explicit ModUnionAddToCardSetVisitor(ModUnionTable::CardSet* const cleared_cards)
+      : cleared_cards_(cleared_cards) {
   }
 
-  inline void operator()(uint8_t* card, uint8_t expected_value, uint8_t new_value) const {
-    UNUSED(new_value);
+  inline void operator()(uint8_t* card, uint8_t expected_value,
+                         uint8_t new_value ATTRIBUTE_UNUSED) const {
     if (expected_value == CardTable::kCardDirty) {
       cleared_cards_->insert(card);
     }
@@ -57,18 +58,38 @@ class ModUnionClearCardSetVisitor {
   ModUnionTable::CardSet* const cleared_cards_;
 };
 
-class ModUnionClearCardVisitor {
+class ModUnionAddToCardBitmapVisitor {
  public:
-  explicit ModUnionClearCardVisitor(std::vector<uint8_t*>* cleared_cards)
-    : cleared_cards_(cleared_cards) {
+  explicit ModUnionAddToCardBitmapVisitor(ModUnionTable::CardBitmap* bitmap,
+                                          CardTable* card_table)
+      : bitmap_(bitmap), card_table_(card_table) {
   }
 
-  void operator()(uint8_t* card, uint8_t expected_card, uint8_t new_card) const {
-    UNUSED(new_card);
+  inline void operator()(uint8_t* card, uint8_t expected_value,
+                         uint8_t new_value ATTRIBUTE_UNUSED) const {
+    if (expected_value == CardTable::kCardDirty) {
+      // We want the address the card represents, not the address of the card.
+      bitmap_->Set(reinterpret_cast<uintptr_t>(card_table_->AddrFromCard(card)));
+    }
+  }
+
+ private:
+  ModUnionTable::CardBitmap* const bitmap_;
+  CardTable* const card_table_;
+};
+
+class ModUnionAddToCardVectorVisitor {
+ public:
+  explicit ModUnionAddToCardVectorVisitor(std::vector<uint8_t*>* cleared_cards)
+      : cleared_cards_(cleared_cards) {
+  }
+
+  void operator()(uint8_t* card, uint8_t expected_card, uint8_t new_card ATTRIBUTE_UNUSED) const {
     if (expected_card == CardTable::kCardDirty) {
       cleared_cards_->push_back(card);
     }
   }
+
  private:
   std::vector<uint8_t*>* const cleared_cards_;
 };
@@ -77,19 +98,19 @@ class ModUnionUpdateObjectReferencesVisitor {
  public:
   ModUnionUpdateObjectReferencesVisitor(MarkHeapReferenceCallback* callback, void* arg,
                                         space::ContinuousSpace* from_space,
-                                        space::ImageSpace* image_space,
+                                        space::ContinuousSpace* immune_space,
                                         bool* contains_reference_to_other_space)
-    : callback_(callback), arg_(arg), from_space_(from_space), image_space_(image_space),
+    : callback_(callback), arg_(arg), from_space_(from_space), immune_space_(immune_space),
       contains_reference_to_other_space_(contains_reference_to_other_space) {
   }
 
   // Extra parameters are required since we use this same visitor signature for checking objects.
-  void operator()(Object* obj, MemberOffset offset, bool /*is_static*/) const
+  void operator()(Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     // Only add the reference if it is non null and fits our criteria.
-    mirror::HeapReference<Object>* obj_ptr = obj->GetFieldObjectReferenceAddr(offset);
+    mirror::HeapReference<Object>* const obj_ptr = obj->GetFieldObjectReferenceAddr(offset);
     mirror::Object* ref = obj_ptr->AsMirrorPtr();
-    if (ref != nullptr && !from_space_->HasAddress(ref) && !image_space_->HasAddress(ref)) {
+    if (ref != nullptr && !from_space_->HasAddress(ref) && !immune_space_->HasAddress(ref)) {
       *contains_reference_to_other_space_ = true;
       callback_(obj_ptr, arg_);
     }
@@ -97,27 +118,30 @@ class ModUnionUpdateObjectReferencesVisitor {
 
  private:
   MarkHeapReferenceCallback* const callback_;
-  void* arg_;
+  void* const arg_;
   // Space which we are scanning
   space::ContinuousSpace* const from_space_;
-  space::ImageSpace* const image_space_;
+  space::ContinuousSpace* const immune_space_;
   // Set if we have any references to another space.
   bool* const contains_reference_to_other_space_;
 };
 
 class ModUnionScanImageRootVisitor {
  public:
+  // Immune space is any other space which we don't care about references to. Currently this is
+  // the image space in the case of the zygote mod union table.
   ModUnionScanImageRootVisitor(MarkHeapReferenceCallback* callback, void* arg,
-                               space::ContinuousSpace* from_space, space::ImageSpace* image_space,
+                               space::ContinuousSpace* from_space,
+                               space::ContinuousSpace* immune_space,
                                bool* contains_reference_to_other_space)
-      : callback_(callback), arg_(arg), from_space_(from_space), image_space_(image_space),
+      : callback_(callback), arg_(arg), from_space_(from_space), immune_space_(immune_space),
         contains_reference_to_other_space_(contains_reference_to_other_space) {}
 
   void operator()(Object* root) const
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-    DCHECK(root != NULL);
-    ModUnionUpdateObjectReferencesVisitor ref_visitor(callback_, arg_, from_space_, image_space_,
+    DCHECK(root != nullptr);
+    ModUnionUpdateObjectReferencesVisitor ref_visitor(callback_, arg_, from_space_, immune_space_,
                                                       contains_reference_to_other_space_);
     root->VisitReferences<kMovingClasses>(ref_visitor, VoidFunctor());
   }
@@ -127,14 +151,14 @@ class ModUnionScanImageRootVisitor {
   void* const arg_;
   // Space which we are scanning
   space::ContinuousSpace* const from_space_;
-  space::ImageSpace* const image_space_;
+  space::ContinuousSpace* const immune_space_;
   // Set if we have any references to another space.
   bool* const contains_reference_to_other_space_;
 };
 
 void ModUnionTableReferenceCache::ClearCards() {
   CardTable* card_table = GetHeap()->GetCardTable();
-  ModUnionClearCardSetVisitor visitor(&cleared_cards_);
+  ModUnionAddToCardSetVisitor visitor(&cleared_cards_);
   // Clear dirty cards in the this space and update the corresponding mod-union bits.
   card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), visitor);
 }
@@ -324,9 +348,54 @@ void ModUnionTableReferenceCache::UpdateAndMarkReferences(MarkHeapReferenceCallb
   }
 }
 
+ModUnionTableCardCache::ModUnionTableCardCache(const std::string& name, Heap* heap,
+                                               space::ContinuousSpace* space)
+    : ModUnionTable(name, heap, space) {
+  // Normally here we could use End() instead of Limit(), but for testing we may want to have a
+  // mod-union table for a space which can still grow.
+  if (!space->IsImageSpace()) {
+    CHECK_ALIGNED(reinterpret_cast<uintptr_t>(space->Limit()), CardTable::kCardSize);
+  }
+  card_bitmap_.reset(CardBitmap::Create(
+      "mod union bitmap", reinterpret_cast<uintptr_t>(space->Begin()),
+      RoundUp(reinterpret_cast<uintptr_t>(space->Limit()), CardTable::kCardSize)));
+}
+
+class CardBitVisitor {
+ public:
+  CardBitVisitor(MarkHeapReferenceCallback* callback, void* arg, space::ContinuousSpace* space,
+                 space::ContinuousSpace* immune_space, ModUnionTable::CardBitmap* card_bitmap)
+      : callback_(callback), arg_(arg), space_(space), immune_space_(immune_space),
+        bitmap_(space->GetLiveBitmap()), card_bitmap_(card_bitmap) {
+    DCHECK(immune_space_ != nullptr);
+  }
+
+  void operator()(size_t bit_index) const {
+    const uintptr_t start = card_bitmap_->AddrFromBitIndex(bit_index);
+    DCHECK(space_->HasAddress(reinterpret_cast<mirror::Object*>(start)))
+        << start << " " << *space_;
+    bool reference_to_other_space = false;
+    ModUnionScanImageRootVisitor scan_visitor(callback_, arg_, space_, immune_space_,
+                                              &reference_to_other_space);
+    bitmap_->VisitMarkedRange(start, start + CardTable::kCardSize, scan_visitor);
+    if (!reference_to_other_space) {
+      // No non null reference to another space, clear the bit.
+      card_bitmap_->ClearBit(bit_index);
+    }
+  }
+
+ private:
+  MarkHeapReferenceCallback* const callback_;
+  void* const arg_;
+  space::ContinuousSpace* const space_;
+  space::ContinuousSpace* const immune_space_;
+  ContinuousSpaceBitmap* const bitmap_;
+  ModUnionTable::CardBitmap* const card_bitmap_;
+};
+
 void ModUnionTableCardCache::ClearCards() {
-  CardTable* card_table = GetHeap()->GetCardTable();
-  ModUnionClearCardSetVisitor visitor(&cleared_cards_);
+  CardTable* const card_table = GetHeap()->GetCardTable();
+  ModUnionAddToCardBitmapVisitor visitor(card_bitmap_.get(), card_table);
   // Clear dirty cards in the this space and update the corresponding mod-union bits.
   card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), visitor);
 }
@@ -334,46 +403,51 @@ void ModUnionTableCardCache::ClearCards() {
 // Mark all references to the alloc space(s).
 void ModUnionTableCardCache::UpdateAndMarkReferences(MarkHeapReferenceCallback* callback,
                                                      void* arg) {
-  CardTable* card_table = heap_->GetCardTable();
-  space::ImageSpace* image_space = heap_->GetImageSpace();
-  ContinuousSpaceBitmap* bitmap = space_->GetLiveBitmap();
-  bool reference_to_other_space = false;
-  ModUnionScanImageRootVisitor scan_visitor(callback, arg, space_, image_space,
-                                            &reference_to_other_space);
-  for (auto it = cleared_cards_.begin(), end = cleared_cards_.end(); it != end; ) {
-    uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(*it));
-    DCHECK(space_->HasAddress(reinterpret_cast<Object*>(start)));
-    reference_to_other_space = false;
-    bitmap->VisitMarkedRange(start, start + CardTable::kCardSize, scan_visitor);
-    if (!reference_to_other_space) {
-      // No non null reference to another space, remove the card.
-      it = cleared_cards_.erase(it);
-    } else {
-      ++it;
-    }
-  }
+  auto* image_space = heap_->GetImageSpace();
+  // If we don't have an image space, just pass in space_ as the immune space. Pass in the same
+  // space_ instead of image_space to avoid a null check in ModUnionUpdateObjectReferencesVisitor.
+  CardBitVisitor visitor(callback, arg, space_, image_space != nullptr ? image_space : space_,
+      card_bitmap_.get());
+  card_bitmap_->VisitSetBits(
+      0, RoundUp(space_->Size(), CardTable::kCardSize) / CardTable::kCardSize, visitor);
 }
 
 void ModUnionTableCardCache::Dump(std::ostream& os) {
-  CardTable* card_table = heap_->GetCardTable();
   os << "ModUnionTable dirty cards: [";
-  for (const uint8_t* card_addr : cleared_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";
+  // TODO: Find cleaner way of doing this.
+  for (uint8_t* addr = space_->Begin(); addr < AlignUp(space_->End(), CardTable::kCardSize);
+      addr += CardTable::kCardSize) {
+    if (card_bitmap_->Test(reinterpret_cast<uintptr_t>(addr))) {
+      os << reinterpret_cast<void*>(addr) << "-"
+         << reinterpret_cast<void*>(addr + CardTable::kCardSize) << "\n";
+    }
   }
   os << "]";
 }
 
 void ModUnionTableCardCache::SetCards() {
-  CardTable* card_table = heap_->GetCardTable();
+  // Only clean up to the end since there cannot be any objects past the End() of the space.
   for (uint8_t* addr = space_->Begin(); addr < AlignUp(space_->End(), CardTable::kCardSize);
        addr += CardTable::kCardSize) {
-    cleared_cards_.insert(card_table->CardFromAddr(addr));
+    card_bitmap_->Set(reinterpret_cast<uintptr_t>(addr));
   }
 }
 
+bool ModUnionTableCardCache::ContainsCardFor(uintptr_t addr) {
+  return card_bitmap_->Test(addr);
+}
+
 void ModUnionTableReferenceCache::SetCards() {
+  for (uint8_t* addr = space_->Begin(); addr < AlignUp(space_->End(), CardTable::kCardSize);
+       addr += CardTable::kCardSize) {
+    cleared_cards_.insert(heap_->GetCardTable()->CardFromAddr(reinterpret_cast<void*>(addr)));
+  }
+}
+
+bool ModUnionTableReferenceCache::ContainsCardFor(uintptr_t addr) {
+  auto* card_ptr = heap_->GetCardTable()->CardFromAddr(reinterpret_cast<void*>(addr));
+  return cleared_cards_.find(card_ptr) != cleared_cards_.end() ||
+      references_.find(card_ptr) != references_.end();
 }
 
 }  // namespace accounting
diff --git a/runtime/gc/accounting/mod_union_table.h b/runtime/gc/accounting/mod_union_table.h
index d6342cf..2e232ca 100644
--- a/runtime/gc/accounting/mod_union_table.h
+++ b/runtime/gc/accounting/mod_union_table.h
@@ -17,7 +17,9 @@
 #ifndef ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
 #define ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
 
+#include "bitmap.h"
 #include "base/allocator.h"
+#include "card_table.h"
 #include "globals.h"
 #include "object_callbacks.h"
 #include "safe_map.h"
@@ -44,6 +46,7 @@ class Heap;
 
 namespace accounting {
 
+class Bitmap;
 class HeapBitmap;
 
 // The mod-union table is the union of modified cards. It is used to allow the card table to be
@@ -52,6 +55,7 @@ class ModUnionTable {
  public:
   typedef std::set<uint8_t*, std::less<uint8_t*>,
                    TrackingAllocator<uint8_t*, kAllocatorTagModUnionCardSet>> CardSet;
+  typedef MemoryRangeBitmap<CardTable::kCardSize> CardBitmap;
 
   explicit ModUnionTable(const std::string& name, Heap* heap, space::ContinuousSpace* space)
       : name_(name),
@@ -80,6 +84,10 @@ class ModUnionTable {
   // bitmap or not.
   virtual void Verify() EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) = 0;
 
+  // Returns true if a card is marked inside the mod union table. Used for testing. The address
+  // doesn't need to be aligned.
+  virtual bool ContainsCardFor(uintptr_t addr) = 0;
+
   virtual void Dump(std::ostream& os) = 0;
   space::ContinuousSpace* GetSpace() {
     return space_;
@@ -106,25 +114,27 @@ class ModUnionTableReferenceCache : public ModUnionTable {
   virtual ~ModUnionTableReferenceCache() {}
 
   // Clear and store cards for a space.
-  void ClearCards();
+  void ClearCards() OVERRIDE;
 
   // Update table based on cleared cards and mark all references to the other spaces.
-  void UpdateAndMarkReferences(MarkHeapReferenceCallback* callback, void* arg)
+  void UpdateAndMarkReferences(MarkHeapReferenceCallback* callback, void* arg) OVERRIDE
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
   // Exclusive lock is required since verify uses SpaceBitmap::VisitMarkedRange and
   // VisitMarkedRange can't know if the callback will modify the bitmap or not.
-  void Verify()
+  void Verify() OVERRIDE
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
   // Function that tells whether or not to add a reference to the table.
   virtual bool ShouldAddReference(const mirror::Object* ref) const = 0;
 
-  void Dump(std::ostream& os) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  virtual bool ContainsCardFor(uintptr_t addr) OVERRIDE;
+
+  virtual void Dump(std::ostream& os) OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  void SetCards() OVERRIDE;
+  virtual void SetCards() OVERRIDE;
 
  protected:
   // Cleared card array, used to update the mod-union table.
@@ -138,28 +148,32 @@ class ModUnionTableReferenceCache : public ModUnionTable {
 // Card caching implementation. Keeps track of which cards we cleared and only this information.
 class ModUnionTableCardCache : public ModUnionTable {
  public:
-  explicit ModUnionTableCardCache(const std::string& name, Heap* heap, space::ContinuousSpace* space)
-      : ModUnionTable(name, heap, space) {}
+  // Note: There is assumption that the space End() doesn't change.
+  explicit ModUnionTableCardCache(const std::string& name, Heap* heap,
+                                  space::ContinuousSpace* space);
   virtual ~ModUnionTableCardCache() {}
 
   // Clear and store cards for a space.
-  void ClearCards();
+  virtual void ClearCards() OVERRIDE;
 
   // Mark all references to the alloc space(s).
-  void UpdateAndMarkReferences(MarkHeapReferenceCallback* callback, void* arg)
+  virtual void UpdateAndMarkReferences(MarkHeapReferenceCallback* callback, void* arg) OVERRIDE
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   // Nothing to verify.
-  void Verify() {}
+  virtual void Verify() OVERRIDE {}
 
-  void Dump(std::ostream& os);
+  virtual void Dump(std::ostream& os) OVERRIDE;
 
-  void SetCards() OVERRIDE;
+  virtual bool ContainsCardFor(uintptr_t addr) OVERRIDE;
+
+  // Sets all the cards in the mod union table to be marked.
+  virtual void SetCards() OVERRIDE;
 
  protected:
-  // Cleared card array, used to update the mod-union table.
-  CardSet cleared_cards_;
+  // Cleared card bitmap, used to update the mod-union table.
+  std::unique_ptr<CardBitmap> card_bitmap_;
 };
 
 }  // namespace accounting
diff --git a/runtime/gc/accounting/mod_union_table_test.cc b/runtime/gc/accounting/mod_union_table_test.cc
new file mode 100644
index 0000000..87ce166
--- /dev/null
+++ b/runtime/gc/accounting/mod_union_table_test.cc
@@ -0,0 +1,242 @@
+/*
+ * Copyright (C) 2015 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 "mod_union_table-inl.h"
+
+#include "common_runtime_test.h"
+#include "gc/space/space-inl.h"
+#include "mirror/array-inl.h"
+#include "space_bitmap-inl.h"
+#include "thread-inl.h"
+
+namespace art {
+namespace gc {
+namespace accounting {
+
+class ModUnionTableFactory {
+ public:
+  enum TableType {
+    kTableTypeCardCache,
+    kTableTypeReferenceCache,
+    kTableTypeCount,  // Number of values in the enum.
+  };
+
+  // Target space is ignored for the card cache implementation.
+  static ModUnionTable* Create(
+      TableType type, space::ContinuousSpace* space, space::ContinuousSpace* target_space);
+};
+
+class ModUnionTableTest : public CommonRuntimeTest {
+ public:
+  ModUnionTableTest() : java_lang_object_array_(nullptr) {
+  }
+  mirror::ObjectArray<mirror::Object>* AllocObjectArray(
+      Thread* self, space::ContinuousMemMapAllocSpace* space, size_t component_count)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    auto* klass = GetObjectArrayClass(self, space);
+    const size_t size = ComputeArraySize(self, klass, component_count, 2);
+    size_t bytes_allocated = 0;
+    auto* obj = down_cast<mirror::ObjectArray<mirror::Object>*>(
+        space->Alloc(self, size, &bytes_allocated, nullptr));
+    if (obj != nullptr) {
+      obj->SetClass(klass);
+      obj->SetLength(static_cast<int32_t>(component_count));
+      space->GetLiveBitmap()->Set(obj);
+      EXPECT_GE(bytes_allocated, size);
+    }
+    return obj;
+  }
+  void ResetClass() {
+    java_lang_object_array_ = nullptr;
+  }
+  void RunTest(ModUnionTableFactory::TableType type);
+
+ private:
+  mirror::Class* GetObjectArrayClass(Thread* self, space::ContinuousMemMapAllocSpace* space)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    if (java_lang_object_array_ == nullptr) {
+      java_lang_object_array_ =
+          Runtime::Current()->GetClassLinker()->GetClassRoot(ClassLinker::kObjectArrayClass);
+      // Since the test doesn't have an image, the class of the object array keeps cards live
+      // inside the card cache mod-union table and causes the check
+      // ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj3)));
+      // to fail since the class ends up keeping the card dirty. To get around this, we make a fake
+      // copy of the class in the same space that we are allocating in.
+      DCHECK(java_lang_object_array_ != nullptr);
+      const size_t class_size = java_lang_object_array_->GetClassSize();
+      size_t bytes_allocated = 0;
+      auto* klass = down_cast<mirror::Class*>(space->Alloc(self, class_size, &bytes_allocated,
+                                                           nullptr));
+      DCHECK(klass != nullptr);
+      memcpy(klass, java_lang_object_array_, class_size);
+      Runtime::Current()->GetHeap()->GetCardTable()->MarkCard(klass);
+      java_lang_object_array_ = klass;
+    }
+    return java_lang_object_array_;
+  }
+  mirror::Class* java_lang_object_array_;
+};
+
+// Collect visited objects into container.
+static void CollectVisitedCallback(mirror::HeapReference<mirror::Object>* ref, void* arg)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  DCHECK(ref != nullptr);
+  DCHECK(arg != nullptr);
+  reinterpret_cast<std::set<mirror::Object*>*>(arg)->insert(ref->AsMirrorPtr());
+}
+
+// A mod union table that only holds references to a specified target space.
+class ModUnionTableRefCacheToSpace : public ModUnionTableReferenceCache {
+ public:
+  explicit ModUnionTableRefCacheToSpace(
+      const std::string& name, Heap* heap, space::ContinuousSpace* space,
+      space::ContinuousSpace* target_space)
+      : ModUnionTableReferenceCache(name, heap, space), target_space_(target_space) {}
+
+  bool ShouldAddReference(const mirror::Object* ref) const OVERRIDE {
+    return target_space_->HasAddress(ref);
+  }
+
+ private:
+  space::ContinuousSpace* const target_space_;
+};
+
+std::ostream& operator<<(std::ostream& oss, ModUnionTableFactory::TableType type) {
+  switch (type) {
+    case ModUnionTableFactory::kTableTypeCardCache: {
+      oss << "CardCache";
+      break;
+    }
+    case ModUnionTableFactory::kTableTypeReferenceCache: {
+      oss << "ReferenceCache";
+      break;
+    }
+    default: {
+      UNIMPLEMENTED(FATAL) << static_cast<size_t>(type);
+    }
+  }
+  return oss;
+}
+
+ModUnionTable* ModUnionTableFactory::Create(
+    TableType type, space::ContinuousSpace* space, space::ContinuousSpace* target_space) {
+  std::ostringstream name;
+  name << "Mod union table: " << type;
+  switch (type) {
+    case kTableTypeCardCache: {
+      return new ModUnionTableCardCache(name.str(), Runtime::Current()->GetHeap(), space);
+    }
+    case kTableTypeReferenceCache: {
+      return new ModUnionTableRefCacheToSpace(name.str(), Runtime::Current()->GetHeap(), space,
+                                              target_space);
+    }
+    default: {
+      UNIMPLEMENTED(FATAL) << "Invalid type " << type;
+    }
+  }
+  return nullptr;
+}
+
+TEST_F(ModUnionTableTest, TestCardCache) {
+  RunTest(ModUnionTableFactory::kTableTypeCardCache);
+}
+
+TEST_F(ModUnionTableTest, TestReferenceCache) {
+  RunTest(ModUnionTableFactory::kTableTypeReferenceCache);
+}
+
+void ModUnionTableTest::RunTest(ModUnionTableFactory::TableType type) {
+  Thread* const self = Thread::Current();
+  ScopedObjectAccess soa(self);
+  Runtime* const runtime = Runtime::Current();
+  gc::Heap* const heap = runtime->GetHeap();
+  // Use non moving space since moving GC don't necessarily have a primary free list space.
+  auto* space = heap->GetNonMovingSpace();
+  ResetClass();
+  // Create another space that we can put references in.
+  std::unique_ptr<space::DlMallocSpace> other_space(space::DlMallocSpace::Create(
+      "other space", 128 * KB, 4 * MB, 4 * MB, nullptr, false));
+  ASSERT_TRUE(other_space.get() != nullptr);
+  heap->AddSpace(other_space.get());
+  std::unique_ptr<ModUnionTable> table(ModUnionTableFactory::Create(
+      type, space, other_space.get()));
+  ASSERT_TRUE(table.get() != nullptr);
+  // Create some fake objects and put the main space and dirty cards in the non moving space.
+  auto* obj1 = AllocObjectArray(self, space, CardTable::kCardSize);
+  ASSERT_TRUE(obj1 != nullptr);
+  auto* obj2 = AllocObjectArray(self, space, CardTable::kCardSize);
+  ASSERT_TRUE(obj2 != nullptr);
+  auto* obj3 = AllocObjectArray(self, space, CardTable::kCardSize);
+  ASSERT_TRUE(obj3 != nullptr);
+  auto* obj4 = AllocObjectArray(self, space, CardTable::kCardSize);
+  ASSERT_TRUE(obj4 != nullptr);
+  // Dirty some cards.
+  obj1->Set(0, obj2);
+  obj2->Set(0, obj3);
+  obj3->Set(0, obj4);
+  obj4->Set(0, obj1);
+  // Dirty some more cards to objects in another space.
+  auto* other_space_ref1 = AllocObjectArray(self, other_space.get(), CardTable::kCardSize);
+  ASSERT_TRUE(other_space_ref1 != nullptr);
+  auto* other_space_ref2 = AllocObjectArray(self, other_space.get(), CardTable::kCardSize);
+  ASSERT_TRUE(other_space_ref2 != nullptr);
+  obj1->Set(1, other_space_ref1);
+  obj2->Set(3, other_space_ref2);
+  table->ClearCards();
+  std::set<mirror::Object*> visited;
+  table->UpdateAndMarkReferences(&CollectVisitedCallback, &visited);
+  // Check that we visited all the references in other spaces only.
+  ASSERT_GE(visited.size(), 2u);
+  ASSERT_TRUE(visited.find(other_space_ref1) != visited.end());
+  ASSERT_TRUE(visited.find(other_space_ref2) != visited.end());
+  // Verify that all the other references were visited.
+  // obj1, obj2 cards should still be in mod union table since they have references to other
+  // spaces.
+  ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj1)));
+  ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj2)));
+  // obj3, obj4 don't have a reference to any object in the other space, their cards should have
+  // been removed from the mod union table during UpdateAndMarkReferences.
+  ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj3)));
+  ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj4)));
+  {
+    // Currently no-op, make sure it still works however.
+    ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
+    table->Verify();
+  }
+  // Verify that dump doesn't crash.
+  std::ostringstream oss;
+  table->Dump(oss);
+  // Set all the cards, then verify.
+  table->SetCards();
+  // TODO: Check that the cards are actually set.
+  for (auto* ptr = space->Begin(); ptr < AlignUp(space->End(), CardTable::kCardSize);
+      ptr += CardTable::kCardSize) {
+    ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(ptr)));
+  }
+  // Visit again and make sure the cards got cleared back to their sane state.
+  visited.clear();
+  table->UpdateAndMarkReferences(&CollectVisitedCallback, &visited);
+  // Verify that the dump matches what we saw earlier.
+  std::ostringstream oss2;
+  table->Dump(oss2);
+  ASSERT_EQ(oss.str(), oss2.str());
+  // Remove the space we added so it doesn't persist to the next test.
+  heap->RemoveSpace(other_space.get());
+}
+
+}  // namespace accounting
+}  // namespace gc
+}  // namespace art
diff --git a/runtime/gc/accounting/space_bitmap.h b/runtime/gc/accounting/space_bitmap.h
index 7bc83ef..d6b3ed4 100644
--- a/runtime/gc/accounting/space_bitmap.h
+++ b/runtime/gc/accounting/space_bitmap.h
@@ -188,13 +188,6 @@ class SpaceBitmap {
 
   std::string Dump() const;
 
-  const void* GetObjectWordAddress(const mirror::Object* obj) const {
-    uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
-    const uintptr_t offset = addr - heap_begin_;
-    const size_t index = OffsetToIndex(offset);
-    return &bitmap_begin_[index];
-  }
-
  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_
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 9e159c2..00b03ff 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -398,14 +398,14 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
     rb_table_.reset(new accounting::ReadBarrierTable());
     DCHECK(rb_table_->IsAllCleared());
   }
-
-  // Card cache for now since it makes it easier for us to update the references to the copying
-  // spaces.
-  accounting::ModUnionTable* mod_union_table =
-      new accounting::ModUnionTableToZygoteAllocspace("Image mod-union table", this,
-                                                      GetImageSpace());
-  CHECK(mod_union_table != nullptr) << "Failed to create image mod-union table";
-  AddModUnionTable(mod_union_table);
+  if (GetImageSpace() != nullptr) {
+    // Don't add the image mod union table if we are running without an image, this can crash if
+    // we use the CardCache implementation.
+    accounting::ModUnionTable* mod_union_table = new accounting::ModUnionTableToZygoteAllocspace(
+        "Image mod-union table", this, GetImageSpace());
+    CHECK(mod_union_table != nullptr) << "Failed to create image mod-union table";
+    AddModUnionTable(mod_union_table);
+  }
   if (collector::SemiSpace::kUseRememberedSet && non_moving_space_ != main_space_) {
     accounting::RememberedSet* non_moving_space_rem_set =
         new accounting::RememberedSet("Non-moving space remembered set", this, non_moving_space_);