Stop-the-world compaction phase

The CL implements the core logic for per-page compaction, but in
a stop-the-world pause. Even though it's performed during a pause, it
handles every page independetly as the final goal is to have a
concurrent implementation.

This CL doesn't handle updating the native roots. Also, the black
allocations since the marking-phase pause are not handled yet.

Test: art/test/testrunner/testrunner.py
Bug: 160737021
Change-Id: Ib0be20663e0f9f76ee66a2a42180c4bd3579e41b

12 files changed, 959 insertions, 37 deletions

diff --git a/runtime/gc/accounting/bitmap.h b/runtime/gc/accounting/bitmap.h
index a44b7c7446..cab8ecf015 100644
--- a/runtime/gc/accounting/bitmap.h
+++ b/runtime/gc/accounting/bitmap.h
@@ -98,7 +98,7 @@ class Bitmap {
   std::string Dump() const;
 
  protected:
-  static constexpr size_t kBitsPerBitmapWord = sizeof(uintptr_t) * kBitsPerByte;
+  static constexpr size_t kBitsPerBitmapWord = kBitsPerIntPtrT;
 
   Bitmap(MemMap&& mem_map, size_t bitmap_size);
   ~Bitmap();
diff --git a/runtime/gc/accounting/space_bitmap-inl.h b/runtime/gc/accounting/space_bitmap-inl.h
index d460e00075..e7825e6953 100644
--- a/runtime/gc/accounting/space_bitmap-inl.h
+++ b/runtime/gc/accounting/space_bitmap-inl.h
@@ -64,7 +64,44 @@ inline bool SpaceBitmap<kAlignment>::Test(const mirror::Object* obj) const {
 }
 
 template<size_t kAlignment>
-template<typename Visitor>
+inline mirror::Object* SpaceBitmap<kAlignment>::FindPrecedingObject(uintptr_t visit_begin,
+                                                                    uintptr_t visit_end) const {
+  // Covers [visit_end, visit_begin].
+  visit_end = std::max(heap_begin_, visit_end);
+  DCHECK_LE(visit_end, visit_begin);
+  DCHECK_LT(visit_begin, HeapLimit());
+
+  const uintptr_t offset_start = visit_begin - heap_begin_;
+  const uintptr_t offset_end = visit_end - heap_begin_;
+  uintptr_t index_start = OffsetToIndex(offset_start);
+  const uintptr_t index_end = OffsetToIndex(offset_end);
+
+  // Start with the right edge
+  uintptr_t word = bitmap_begin_[index_start].load(std::memory_order_relaxed);
+  // visit_begin could be the first word of the object we are looking for.
+  const uintptr_t right_edge_mask = OffsetToMask(offset_start);
+  word &= right_edge_mask | (right_edge_mask - 1);
+  while (index_start > index_end) {
+    if (word != 0) {
+      const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_;
+      size_t pos_leading_set_bit = kBitsPerIntPtrT - CLZ(word) - 1;
+      return reinterpret_cast<mirror::Object*>(ptr_base + pos_leading_set_bit * kAlignment);
+    }
+    word = bitmap_begin_[--index_start].load(std::memory_order_relaxed);
+  }
+
+  word &= ~(OffsetToMask(offset_end) - 1);
+  if (word != 0) {
+    const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
+    size_t pos_leading_set_bit = kBitsPerIntPtrT - CLZ(word) - 1;
+    return reinterpret_cast<mirror::Object*>(ptr_base + pos_leading_set_bit * kAlignment);
+  } else {
+    return nullptr;
+  }
+}
+
+template<size_t kAlignment>
+template<bool kVisitOnce, typename Visitor>
 inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin,
                                                       uintptr_t visit_end,
                                                       Visitor&& visitor) const {
@@ -114,6 +151,9 @@ inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin,
         const size_t shift = CTZ(left_edge);
         mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
         visitor(obj);
+        if (kVisitOnce) {
+          return;
+        }
         left_edge ^= (static_cast<uintptr_t>(1)) << shift;
       } while (left_edge != 0);
     }
@@ -128,6 +168,9 @@ inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin,
           const size_t shift = CTZ(w);
           mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
           visitor(obj);
+          if (kVisitOnce) {
+            return;
+          }
           w ^= (static_cast<uintptr_t>(1)) << shift;
         } while (w != 0);
       }
@@ -155,6 +198,9 @@ inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin,
       const size_t shift = CTZ(right_edge);
       mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
       visitor(obj);
+      if (kVisitOnce) {
+        return;
+      }
       right_edge ^= (static_cast<uintptr_t>(1)) << shift;
     } while (right_edge != 0);
   }
diff --git a/runtime/gc/accounting/space_bitmap.h b/runtime/gc/accounting/space_bitmap.h
index 6fc35d92fb..09a7ce402b 100644
--- a/runtime/gc/accounting/space_bitmap.h
+++ b/runtime/gc/accounting/space_bitmap.h
@@ -131,10 +131,15 @@ class SpaceBitmap {
     }
   }
 
-  // Visit the live objects in the range [visit_begin, visit_end).
+  // Find first object while scanning bitmap backwards from visit_begin -> visit_end.
+  // Covers [visit_end, visit_begin] range.
+  mirror::Object* FindPrecedingObject(uintptr_t visit_begin, uintptr_t visit_end = 0) const;
+
+  // Visit the live objects in the range [visit_begin, visit_end). If kVisitOnce
+  // is true, then only the first live object will be visited.
   // TODO: Use lock annotations when clang is fixed.
   // REQUIRES(Locks::heap_bitmap_lock_) REQUIRES_SHARED(Locks::mutator_lock_);
-  template <typename Visitor>
+  template <bool kVisitOnce = false, typename Visitor>
   void VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, Visitor&& visitor) const
       NO_THREAD_SAFETY_ANALYSIS;
 
diff --git a/runtime/gc/collector/mark_compact-inl.h b/runtime/gc/collector/mark_compact-inl.h
index 0bda8cce76..1397fa6c51 100644
--- a/runtime/gc/collector/mark_compact-inl.h
+++ b/runtime/gc/collector/mark_compact-inl.h
@@ -19,12 +19,15 @@
 
 #include "mark_compact.h"
 
+#include "mirror/object-inl.h"
+
 namespace art {
 namespace gc {
 namespace collector {
 
 template <size_t kAlignment>
-uintptr_t MarkCompact::LiveWordsBitmap<kAlignment>::SetLiveWords(uintptr_t begin, size_t size) {
+inline uintptr_t MarkCompact::LiveWordsBitmap<kAlignment>::SetLiveWords(uintptr_t begin,
+                                                                        size_t size) {
   const uintptr_t begin_bit_idx = MemRangeBitmap::BitIndexFromAddr(begin);
   DCHECK(!Bitmap::TestBit(begin_bit_idx));
   const uintptr_t end_bit_idx = MemRangeBitmap::BitIndexFromAddr(begin + size);
@@ -47,6 +50,186 @@ uintptr_t MarkCompact::LiveWordsBitmap<kAlignment>::SetLiveWords(uintptr_t begin
   return begin_bit_idx;
 }
 
+template <size_t kAlignment> template <typename Visitor>
+inline void MarkCompact::LiveWordsBitmap<kAlignment>::VisitLiveStrides(uintptr_t begin_bit_idx,
+                                                                       const size_t bytes,
+                                                                       Visitor&& visitor) const {
+  // TODO: we may require passing end addr/end_bit_offset to the function.
+  const uintptr_t end_bit_idx = MemRangeBitmap::BitIndexFromAddr(CoverEnd());
+  DCHECK_LT(begin_bit_idx, end_bit_idx);
+  uintptr_t begin_word_idx = Bitmap::BitIndexToWordIndex(begin_bit_idx);
+  const uintptr_t end_word_idx = Bitmap::BitIndexToWordIndex(end_bit_idx);
+  DCHECK(Bitmap::TestBit(begin_bit_idx));
+  size_t stride_size = 0;
+  size_t idx_in_word = 0;
+  size_t num_heap_words = bytes / kAlignment;
+  uintptr_t live_stride_start_idx;
+  uintptr_t word = Bitmap::Begin()[begin_word_idx];
+
+  // Setup the first word.
+  word &= ~(Bitmap::BitIndexToMask(begin_bit_idx) - 1);
+  begin_bit_idx = RoundDown(begin_bit_idx, Bitmap::kBitsPerBitmapWord);
+
+  do {
+    if (UNLIKELY(begin_word_idx == end_word_idx)) {
+      word &= Bitmap::BitIndexToMask(end_bit_idx) - 1;
+    }
+    if (~word == 0) {
+      // All bits in the word are marked.
+      if (stride_size == 0) {
+        live_stride_start_idx = begin_bit_idx;
+      }
+      stride_size += Bitmap::kBitsPerBitmapWord;
+      if (num_heap_words <= stride_size) {
+        break;
+      }
+    } else {
+      while (word != 0) {
+        // discard 0s
+        size_t shift = CTZ(word);
+        idx_in_word += shift;
+        word >>= shift;
+        if (stride_size > 0) {
+          if (shift > 0) {
+            if (num_heap_words <= stride_size) {
+              break;
+            }
+            visitor(live_stride_start_idx, stride_size, /*is_last*/ false);
+            num_heap_words -= stride_size;
+            live_stride_start_idx = begin_bit_idx + idx_in_word;
+            stride_size = 0;
+          }
+        } else {
+          live_stride_start_idx = begin_bit_idx + idx_in_word;
+        }
+        // consume 1s
+        shift = CTZ(~word);
+        DCHECK_NE(shift, 0u);
+        word >>= shift;
+        idx_in_word += shift;
+        stride_size += shift;
+      }
+      // If the whole word == 0 or the higher bits are 0s, then we exit out of
+      // the above loop without completely consuming the word, so call visitor,
+      // if needed.
+      if (idx_in_word < Bitmap::kBitsPerBitmapWord && stride_size > 0) {
+        if (num_heap_words <= stride_size) {
+          break;
+        }
+        visitor(live_stride_start_idx, stride_size, /*is_last*/ false);
+        num_heap_words -= stride_size;
+        stride_size = 0;
+      }
+      idx_in_word = 0;
+    }
+    begin_bit_idx += Bitmap::kBitsPerBitmapWord;
+    begin_word_idx++;
+    if (UNLIKELY(begin_word_idx > end_word_idx)) {
+      num_heap_words = std::min(stride_size, num_heap_words);
+      break;
+    }
+    word = Bitmap::Begin()[begin_word_idx];
+  } while (true);
+
+  if (stride_size > 0) {
+    visitor(live_stride_start_idx, num_heap_words, /*is_last*/ true);
+  }
+}
+
+template <size_t kAlignment>
+inline
+uint32_t MarkCompact::LiveWordsBitmap<kAlignment>::FindNthLiveWordOffset(size_t offset_vec_idx,
+                                                                         uint32_t n) const {
+  DCHECK_LT(n, kBitsPerVectorWord);
+  const size_t index = offset_vec_idx * kBitmapWordsPerVectorWord;
+  for (uint32_t i = 0; i < kBitmapWordsPerVectorWord; i++) {
+    uintptr_t word = Bitmap::Begin()[index + i];
+    if (~word == 0) {
+      if (n < Bitmap::kBitsPerBitmapWord) {
+        return i * Bitmap::kBitsPerBitmapWord + n;
+      }
+      n -= Bitmap::kBitsPerBitmapWord;
+    } else {
+      uint32_t j = 0;
+      while (word != 0) {
+        // count contiguous 0s
+        uint32_t shift = CTZ(word);
+        word >>= shift;
+        j += shift;
+        // count contiguous 1s
+        shift = CTZ(~word);
+        DCHECK_NE(shift, 0u);
+        if (shift > n) {
+          return i * Bitmap::kBitsPerBitmapWord + j + n;
+        }
+        n -= shift;
+        word >>= shift;
+        j += shift;
+      }
+    }
+  }
+  UNREACHABLE();
+}
+
+inline void MarkCompact::UpdateRef(mirror::Object* obj, MemberOffset offset) {
+  mirror::Object* old_ref = obj->GetFieldObject<
+      mirror::Object, kVerifyNone, kWithoutReadBarrier, /*kIsVolatile*/false>(offset);
+  mirror::Object* new_ref = PostCompactAddress(old_ref);
+  if (new_ref != old_ref) {
+    obj->SetFieldObjectWithoutWriteBarrier<
+        /*kTransactionActive*/false, /*kCheckTransaction*/false, kVerifyNone, /*kIsVolatile*/false>(
+            offset,
+            new_ref);
+  }
+}
+
+inline void MarkCompact::UpdateRoot(mirror::CompressedReference<mirror::Object>* root) {
+  DCHECK(!root->IsNull());
+  mirror::Object* old_ref = root->AsMirrorPtr();
+  mirror::Object* new_ref = PostCompactAddress(old_ref);
+  if (old_ref != new_ref) {
+    root->Assign(new_ref);
+  }
+}
+
+template <size_t kAlignment>
+inline size_t MarkCompact::LiveWordsBitmap<kAlignment>::CountLiveWordsUpto(size_t bit_idx) const {
+  const size_t word_offset = Bitmap::BitIndexToWordIndex(bit_idx);
+  uintptr_t word;
+  size_t ret = 0;
+  // This is needed only if we decide to make offset_vector chunks 128-bit but
+  // still choose to use 64-bit word for bitmap. Ideally we should use 128-bit
+  // SIMD instructions to compute popcount.
+  if (kBitmapWordsPerVectorWord > 1) {
+    for (size_t i = RoundDown(word_offset, kBitmapWordsPerVectorWord); i < word_offset; i++) {
+      word = Bitmap::Begin()[i];
+      ret += POPCOUNT(word);
+    }
+  }
+  word = Bitmap::Begin()[word_offset];
+  const uintptr_t mask = Bitmap::BitIndexToMask(bit_idx);
+  DCHECK_NE(word & mask, 0u);
+  ret += POPCOUNT(word & (mask - 1));
+  return ret;
+}
+
+inline mirror::Object* MarkCompact::PostCompactAddress(mirror::Object* old_ref) const {
+  // TODO: To further speedup the check, maybe we should consider caching heap
+  // start/end in this object.
+  if (LIKELY(live_words_bitmap_->HasAddress(old_ref))) {
+    const uintptr_t begin = live_words_bitmap_->Begin();
+    const uintptr_t addr_offset = reinterpret_cast<uintptr_t>(old_ref) - begin;
+    const size_t vec_idx = addr_offset / kOffsetChunkSize;
+    const size_t live_bytes_in_bitmap_word =
+        live_words_bitmap_->CountLiveWordsUpto(addr_offset / kAlignment) * kAlignment;
+    return reinterpret_cast<mirror::Object*>(begin
+                                             + offset_vector_[vec_idx]
+                                             + live_bytes_in_bitmap_word);
+  } else {
+    return old_ref;
+  }
+}
+
 }  // namespace collector
 }  // namespace gc
 }  // namespace art
diff --git a/runtime/gc/collector/mark_compact.cc b/runtime/gc/collector/mark_compact.cc
index 3621fc2599..b4d903df59 100644
--- a/runtime/gc/collector/mark_compact.cc
+++ b/runtime/gc/collector/mark_compact.cc
@@ -19,9 +19,13 @@
 #include "base/systrace.h"
 #include "gc/accounting/mod_union_table-inl.h"
 #include "gc/reference_processor.h"
+#include "gc/space/bump_pointer_space.h"
+#include "mirror/object-refvisitor-inl.h"
 #include "scoped_thread_state_change-inl.h"
 #include "thread_list.h"
 
+#include <numeric>
+
 namespace art {
 namespace gc {
 namespace collector {
@@ -30,6 +34,7 @@ namespace collector {
 // significantly.
 static constexpr bool kCheckLocks = kDebugLocking;
 static constexpr bool kVerifyRootsMarked = kIsDebugBuild;
+static constexpr bool kConcurrentCompaction = false;
 
 template <size_t kAlignment>
 MarkCompact::LiveWordsBitmap<kAlignment>* MarkCompact::LiveWordsBitmap<kAlignment>::Create(
@@ -50,20 +55,35 @@ MarkCompact::MarkCompact(Heap* heap)
           reinterpret_cast<uintptr_t>(bump_pointer_space_->Begin()),
           reinterpret_cast<uintptr_t>(bump_pointer_space_->Limit())));
 
-  const size_t vector_size =
-          (bump_pointer_space->Limit() - bump_pointer_space->Begin()) / kOffsetChunkSize;
+  // Create one MemMap for all the data structures
+  size_t offset_vector_size = bump_pointer_space_->Capacity() / kOffsetChunkSize;
+  size_t nr_moving_pages = bump_pointer_space_->Capacity() / kPageSize;
+  size_t nr_non_moving_pages = heap->GetNonMovingSpace()->Capacity() / kPageSize;
 
   std::string err_msg;
-  offset_vector_map_.reset(MemMap::MapAnonymous("Concurrent mark-compact offset-vector",
-                                                vector_size * sizeof(uint32_t),
-                                                PROT_READ | PROT_WRITE,
-                                                /*low_4gb=*/ false,
-                                                &err_msg));
-  if (UNLIKELY(!offset_vector_map_->IsValid())) {
+  info_map_.reset(MemMap::MapAnonymous("Concurrent mark-compact offset-vector",
+                                       offset_vector_size * sizeof(uint32_t)
+                                       + nr_non_moving_pages * sizeof(ObjReference)
+                                       + nr_moving_pages * sizeof(ObjReference)
+                                       + nr_moving_pages * sizeof(uint32_t),
+                                       PROT_READ | PROT_WRITE,
+                                       /*low_4gb=*/ false,
+                                       &err_msg));
+  if (UNLIKELY(!info_map_->IsValid())) {
     LOG(ERROR) << "Failed to allocate concurrent mark-compact offset-vector: " << err_msg;
   } else {
-    offset_vector_ = reinterpret_cast<uint32_t*>(offset_vector_map_->Begin());
-    vector_length_ = vector_size;
+    uint8_t* p = info_map_->Begin();
+    offset_vector_ = reinterpret_cast<uint32_t*>(p);
+    vector_length_ = offset_vector_size;
+
+    p += offset_vector_size * sizeof(uint32_t);
+    first_objs_non_moving_space_ = reinterpret_cast<ObjReference*>(p);
+
+    p += nr_non_moving_pages * sizeof(ObjReference);
+    first_objs_moving_space_ = reinterpret_cast<ObjReference*>(p);
+
+    p += nr_moving_pages * sizeof(ObjReference);
+    pre_compact_offset_moving_space_ = reinterpret_cast<uint32_t*>(p);
   }
 }
 
@@ -109,10 +129,11 @@ void MarkCompact::BindAndResetBitmaps() {
       if (space == bump_pointer_space_) {
         // It is OK to clear the bitmap with mutators running since the only
         // place it is read is VisitObjects which has exclusion with this GC.
-        bump_pointer_bitmap_ = bump_pointer_space_->GetMarkBitmap();
-        bump_pointer_bitmap_->Clear();
+        current_space_bitmap_ = bump_pointer_space_->GetMarkBitmap();
+        current_space_bitmap_->Clear();
       } else {
         CHECK(space == heap_->GetNonMovingSpace());
+        non_moving_space_ = space;
         non_moving_space_bitmap_ = space->GetMarkBitmap();
       }
     }
@@ -124,6 +145,9 @@ void MarkCompact::InitializePhase() {
   mark_stack_ = heap_->GetMarkStack();
   CHECK(mark_stack_->IsEmpty());
   immune_spaces_.Reset();
+  compacting_ = false;
+  moving_first_objs_count_ = 0;
+  non_moving_first_objs_count_ = 0;
 }
 
 void MarkCompact::RunPhases() {
@@ -151,7 +175,7 @@ void MarkCompact::RunPhases() {
     ScopedPause pause(this);
     PreCompactionPhase();
   }
-  {
+  if (kConcurrentCompaction) {
     ReaderMutexLock mu(self, *Locks::mutator_lock_);
     CompactionPhase();
   }
@@ -160,15 +184,173 @@ void MarkCompact::RunPhases() {
   thread_running_gc_ = nullptr;
 }
 
+void MarkCompact::InitMovingSpaceFirstObjects(const size_t vec_len) {
+  // Find the first live word first.
+  size_t to_space_page_idx = 0;
+  uint32_t offset_in_vec_word;
+  uint32_t offset;
+  mirror::Object* obj;
+  const uintptr_t heap_begin = current_space_bitmap_->HeapBegin();
+
+  size_t offset_vec_idx;
+  // Find the first live word in the space
+  for (offset_vec_idx = 0; offset_vector_[offset_vec_idx] == 0; offset_vec_idx++) {
+    if (offset_vec_idx > vec_len) {
+      // We don't have any live data on the moving-space.
+      return;
+    }
+  }
+  // Use live-words bitmap to find the first word
+  offset_in_vec_word = live_words_bitmap_->FindNthLiveWordOffset(offset_vec_idx, /*n*/ 0);
+  offset = offset_vec_idx * kBitsPerVectorWord + offset_in_vec_word;
+  // The first object doesn't require using FindPrecedingObject().
+  obj = reinterpret_cast<mirror::Object*>(heap_begin + offset * kAlignment);
+  // TODO: add a check to validate the object.
+
+  pre_compact_offset_moving_space_[to_space_page_idx] = offset;
+  first_objs_moving_space_[to_space_page_idx].Assign(obj);
+  to_space_page_idx++;
+
+  uint32_t page_live_bytes = 0;
+  while (true) {
+    for (; page_live_bytes <= kPageSize; offset_vec_idx++) {
+      if (offset_vec_idx > vec_len) {
+        moving_first_objs_count_ = to_space_page_idx;
+        return;
+      }
+      page_live_bytes += offset_vector_[offset_vec_idx];
+    }
+    offset_vec_idx--;
+    page_live_bytes -= kPageSize;
+    DCHECK_LE(page_live_bytes, kOffsetChunkSize);
+    DCHECK_LE(page_live_bytes, offset_vector_[offset_vec_idx])
+        << " offset_vec_idx=" << offset_vec_idx
+        << " to_space_page_idx=" << to_space_page_idx
+        << " vec_len=" << vec_len;
+    offset_in_vec_word =
+            live_words_bitmap_->FindNthLiveWordOffset(
+                offset_vec_idx, (offset_vector_[offset_vec_idx] - page_live_bytes) / kAlignment);
+    offset = offset_vec_idx * kBitsPerVectorWord + offset_in_vec_word;
+    // TODO: Can we optimize this for large objects? If we are continuing a
+    // large object that spans multiple pages, then we may be able to do without
+    // calling FindPrecedingObject().
+    //
+    // Find the object which encapsulates offset in it, which could be
+    // starting at offset itself.
+    obj = current_space_bitmap_->FindPrecedingObject(heap_begin + offset * kAlignment);
+    // TODO: add a check to validate the object.
+    pre_compact_offset_moving_space_[to_space_page_idx] = offset;
+    first_objs_moving_space_[to_space_page_idx].Assign(obj);
+    to_space_page_idx++;
+    offset_vec_idx++;
+  }
+}
+
+void MarkCompact::InitNonMovingSpaceFirstObjects() {
+  accounting::ContinuousSpaceBitmap* bitmap = non_moving_space_->GetLiveBitmap();
+  uintptr_t begin = reinterpret_cast<uintptr_t>(non_moving_space_->Begin());
+  const uintptr_t end = reinterpret_cast<uintptr_t>(non_moving_space_->End());
+  mirror::Object* prev_obj;
+  size_t page_idx;
+  {
+    // Find first live object
+    mirror::Object* obj = nullptr;
+    bitmap->VisitMarkedRange</*kVisitOnce*/ true>(begin,
+                                                  end,
+                                                  [&obj] (mirror::Object* o) {
+                                                    obj = o;
+                                                  });
+    if (obj == nullptr) {
+      // There are no live objects in the non-moving space
+      return;
+    }
+    page_idx = (reinterpret_cast<uintptr_t>(obj) - begin) / kPageSize;
+    first_objs_non_moving_space_[page_idx++].Assign(obj);
+    prev_obj = obj;
+  }
+  // TODO: check obj is valid
+  uintptr_t prev_obj_end = reinterpret_cast<uintptr_t>(prev_obj)
+                           + RoundUp(prev_obj->SizeOf<kDefaultVerifyFlags>(), kAlignment);
+  // For every page find the object starting from which we need to call
+  // VisitReferences. It could either be an object that started on some
+  // preceding page, or some object starting within this page.
+  begin = RoundDown(reinterpret_cast<uintptr_t>(prev_obj) + kPageSize, kPageSize);
+  while (begin < end) {
+    // Utilize, if any, large object that started in some preceding page, but
+    // overlaps with this page as well.
+    if (prev_obj != nullptr && prev_obj_end > begin) {
+      first_objs_non_moving_space_[page_idx].Assign(prev_obj);
+    } else {
+      prev_obj_end = 0;
+      // It's sufficient to only search for previous object in the preceding page.
+      // If no live object started in that page and some object had started in
+      // the page preceding to that page, which was big enough to overlap with
+      // the current page, then we wouldn't be in the else part.
+      prev_obj = bitmap->FindPrecedingObject(begin, begin - kPageSize);
+      if (prev_obj != nullptr) {
+        prev_obj_end = reinterpret_cast<uintptr_t>(prev_obj)
+                        + RoundUp(prev_obj->SizeOf<kDefaultVerifyFlags>(), kAlignment);
+      }
+      if (prev_obj_end > begin) {
+        first_objs_non_moving_space_[page_idx].Assign(prev_obj);
+      } else {
+        // Find the first live object in this page
+        bitmap->VisitMarkedRange</*kVisitOnce*/ true>(
+                begin,
+                begin + kPageSize,
+                [this, page_idx] (mirror::Object* obj) {
+                  first_objs_non_moving_space_[page_idx].Assign(obj);
+                });
+      }
+      // An empty entry indicates that the page has no live objects and hence
+      // can be skipped.
+    }
+    begin += kPageSize;
+    page_idx++;
+  }
+  non_moving_first_objs_count_ = page_idx;
+}
+
 void MarkCompact::PrepareForCompaction() {
+  uint8_t* space_begin = bump_pointer_space_->Begin();
+  size_t vector_len = (black_allocations_begin_ - space_begin) / kOffsetChunkSize;
+  DCHECK_LE(vector_len, vector_length_);
+  for (size_t i = 0; i < vector_len; i++) {
+    DCHECK_LE(offset_vector_[i], kOffsetChunkSize);
+  }
+  InitMovingSpaceFirstObjects(vector_len);
+  InitNonMovingSpaceFirstObjects();
+
+  // TODO: We can do a lot of neat tricks with this offset vector to tune the
+  // compaction as we wish. Originally, the compaction algorithm slides all
+  // live objects towards the beginning of the heap. This is nice because it
+  // keeps the spatial locality of objects intact.
+  // However, sometimes it's desired to compact objects in certain portions
+  // of the heap. For instance, it is expected that, over time,
+  // objects towards the beginning of the heap are long lived and are always
+  // densely packed. In this case, it makes sense to only update references in
+  // there and not try to compact it.
+  // Furthermore, we might have some large objects and may not want to move such
+  // objects.
+  // We can adjust, without too much effort, the values in the offset_vector_ such
+  // that the objects in the dense beginning area aren't moved. OTOH, large
+  // objects, which could be anywhere in the heap, could also be kept from
+  // moving by using a similar trick. The only issue is that by doing this we will
+  // leave an unused hole in the middle of the heap which can't be used for
+  // allocations until we do a *full* compaction.
+  //
   // At this point every element in the offset_vector_ contains the live-bytes
   // of the corresponding chunk. For old-to-new address computation we need
-  // every element to reflect all the live-bytes till the corresponding chunk.
-  uint32_t prev = 0;
-  for (size_t i = 0; i < vector_length_; i++) {
-    uint32_t temp = offset_vector_[i];
-    offset_vector_[i] = prev;
-    prev += temp;
+  // every element to reflect total live-bytes till the corresponding chunk.
+  //
+  // Update the vector one past the heap usage as it is required for black
+  // allocated objects' post-compact address computation.
+  if (vector_len < vector_length_) {
+    vector_len++;
+  }
+  std::exclusive_scan(offset_vector_, offset_vector_ + vector_len, offset_vector_, 0);
+  for (size_t i = vector_len; i < vector_length_; i++) {
+    DCHECK_EQ(offset_vector_[i], 0u);
   }
   // How do we handle compaction of heap portion used for allocations after the
   // marking-pause?
@@ -240,7 +422,7 @@ void MarkCompact::PausePhase() {
     {
       TimingLogger::ScopedTiming t2("SwapStacks", GetTimings());
       heap_->SwapStacks();
-      live_stack_freeze_size_ = GetHeap()->GetLiveStack()->Size();
+      live_stack_freeze_size_ = heap_->GetLiveStack()->Size();
     }
   }
   heap_->PreSweepingGcVerification(this);
@@ -253,6 +435,11 @@ void MarkCompact::PausePhase() {
   // Enable the reference processing slow path, needs to be done with mutators
   // paused since there is no lock in the GetReferent fast path.
   heap_->GetReferenceProcessor()->EnableSlowPath();
+
+  // Capture 'end' of moving-space at this point. Every allocation beyond this
+  // point will be considered as in to-space.
+  // TODO: We may need to align up/adjust end to page boundary
+  black_allocations_begin_ = bump_pointer_space_->End();
 }
 
 void MarkCompact::SweepSystemWeaks(Thread* self) {
@@ -328,7 +515,264 @@ void MarkCompact::ReclaimPhase() {
   }
 }
 
+// We want to avoid checking for every reference if it's within the page or
+// not. This can be done if we know where in the page the holder object lies.
+// If it doesn't overlap either boundaries then we can skip the checks.
+template <bool kCheckBegin, bool kCheckEnd>
+class MarkCompact::RefsUpdateVisitor {
+ public:
+  explicit RefsUpdateVisitor(MarkCompact* collector,
+                             mirror::Object* obj,
+                             uint8_t* begin,
+                             uint8_t* end)
+      : collector_(collector), obj_(obj), begin_(begin), end_(end) {}
+
+  void operator()(mirror::Object* old ATTRIBUTE_UNUSED, MemberOffset offset, bool /* is_static */)
+      const ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES_SHARED(Locks::heap_bitmap_lock_) {
+    bool update = true;
+    if (kCheckBegin || kCheckEnd) {
+      uint8_t* ref = reinterpret_cast<uint8_t*>(obj_) + offset.Int32Value();
+      update = (!kCheckBegin || ref >= begin_) && (!kCheckEnd || ref < end_);
+    }
+    if (update) {
+      collector_->UpdateRef(obj_, offset);
+    }
+  }
+
+  // For object arrays we don't need to check boundaries here as it's done in
+  // VisitReferenes().
+  // TODO: Optimize reference updating using SIMD instructions. Object arrays
+  // are perfect as all references are tightly packed.
+  void operator()(mirror::Object* old ATTRIBUTE_UNUSED,
+                  MemberOffset offset,
+                  bool /*is_static*/,
+                  bool /*is_obj_array*/)
+      const ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES_SHARED(Locks::heap_bitmap_lock_) {
+    collector_->UpdateRef(obj_, offset);
+  }
+
+  void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
+      ALWAYS_INLINE
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (!root->IsNull()) {
+      VisitRoot(root);
+    }
+  }
+
+  void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
+      ALWAYS_INLINE
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    collector_->UpdateRoot(root);
+  }
+
+ private:
+  MarkCompact* const collector_;
+  mirror::Object* const obj_;
+  uint8_t* const begin_;
+  uint8_t* const end_;
+};
+
+void MarkCompact::CompactPage(mirror::Object* obj, uint32_t offset, uint8_t* addr) {
+  DCHECK(IsAligned<kPageSize>(addr));
+  obj = GetFromSpaceAddr(obj);
+  // TODO: assert that offset is within obj and obj is a valid object
+  DCHECK(live_words_bitmap_->Test(offset));
+  uint8_t* const start_addr = addr;
+  // How many distinct live-strides do we have.
+  size_t stride_count = 0;
+  uint8_t* last_stride;
+  uint32_t last_stride_begin = 0;
+  live_words_bitmap_->VisitLiveStrides(offset,
+                                       kPageSize,
+                                       [&] (uint32_t stride_begin,
+                                            size_t stride_size,
+                                            bool is_last) {
+                                         const size_t stride_in_bytes = stride_size * kAlignment;
+                                         DCHECK_LE(stride_in_bytes, kPageSize);
+                                         last_stride_begin = stride_begin;
+                                         memcpy(addr,
+                                                from_space_begin_ + stride_begin * kAlignment,
+                                                stride_in_bytes);
+                                         if (is_last) {
+                                            last_stride = addr;
+                                         }
+                                         addr += stride_in_bytes;
+                                         stride_count++;
+                                       });
+  DCHECK_LT(last_stride, start_addr + kPageSize);
+  DCHECK_GT(stride_count, 0u);
+  size_t obj_size;
+  {
+    // First object
+    // TODO: We can further differentiate on the basis of offset == 0 to avoid
+    // checking beginnings when it's true. But it's not a very likely case.
+    uint32_t offset_within_obj = offset * kAlignment
+                                 - (reinterpret_cast<uint8_t*>(obj) - from_space_begin_);
+    const bool update_native_roots = offset_within_obj == 0;
+    mirror::Object* to_ref = reinterpret_cast<mirror::Object*>(start_addr - offset_within_obj);
+    if (stride_count > 1) {
+      RefsUpdateVisitor</*kCheckBegin*/true, /*kCheckEnd*/false> visitor(this,
+                                                                         to_ref,
+                                                                         start_addr,
+                                                                         nullptr);
+      obj_size = update_native_roots
+                 ? obj->VisitRefsForCompaction(visitor,
+                                               MemberOffset(offset_within_obj),
+                                               MemberOffset(-1))
+                 : obj->VisitRefsForCompaction</*kFetchObjSize*/true, /*kVisitNativeRoots*/false>(
+                         visitor, MemberOffset(offset_within_obj), MemberOffset(-1));
+    } else {
+      RefsUpdateVisitor</*kCheckBegin*/true, /*kCheckEnd*/true> visitor(this,
+                                                                        to_ref,
+                                                                        start_addr,
+                                                                        start_addr + kPageSize);
+      obj_size = update_native_roots
+                 ? obj->VisitRefsForCompaction(visitor,
+                                               MemberOffset(offset_within_obj),
+                                               MemberOffset(offset_within_obj + kPageSize))
+                 : obj->VisitRefsForCompaction</*kFetchObjSize*/true, /*kVisitNativeRoots*/false>(
+                         visitor,
+                         MemberOffset(offset_within_obj),
+                         MemberOffset(offset_within_obj + kPageSize));
+    }
+    obj_size = RoundUp(obj_size, kAlignment);
+    DCHECK_GT(obj_size, offset_within_obj);
+    obj_size -= offset_within_obj;
+    // If there is only one stride, then adjust last_stride_begin to the
+    // end of the first object.
+    if (stride_count == 1) {
+      last_stride_begin += obj_size / kAlignment;
+    }
+  }
+
+  uint8_t* const end_addr = start_addr + kPageSize;
+  addr = start_addr + obj_size;
+  // All strides except the last one can be updated without any boundary
+  // checks.
+  while (addr < last_stride) {
+    mirror::Object* ref = reinterpret_cast<mirror::Object*>(addr);
+    RefsUpdateVisitor</*kCheckBegin*/false, /*kCheckEnd*/false>
+            visitor(this, ref, nullptr, nullptr);
+    obj_size = ref->VisitRefsForCompaction(visitor, MemberOffset(0), MemberOffset(-1));
+    addr += RoundUp(obj_size, kAlignment);
+  }
+  // Last stride may have multiple objects in it and we don't know where the
+  // last object which crosses the page boundary starts, therefore check
+  // page-end in all of these objects. Also, we need to call
+  // VisitRefsForCompaction() with from-space object as we fetch object size,
+  // which in case of klass requires 'class_size_'.
+  uint8_t* from_addr = from_space_begin_ + last_stride_begin * kAlignment;
+  while (addr < end_addr) {
+    mirror::Object* ref = reinterpret_cast<mirror::Object*>(addr);
+    obj = reinterpret_cast<mirror::Object*>(from_addr);
+    RefsUpdateVisitor</*kCheckBegin*/false, /*kCheckEnd*/true>
+            visitor(this, ref, nullptr, start_addr + kPageSize);
+    obj_size = obj->VisitRefsForCompaction(visitor,
+                                           MemberOffset(0),
+                                           MemberOffset(end_addr - addr));
+    obj_size = RoundUp(obj_size, kAlignment);
+    addr += obj_size;
+    from_addr += obj_size;
+  }
+}
+
+void MarkCompact::CompactMovingSpace() {
+  // For every page we have a starting object, which may have started in some
+  // preceding page, and an offset within that object from where we must start
+  // copying.
+  // Consult the live-words bitmap to copy all contiguously live words at a
+  // time. These words may constitute multiple objects. To avoid the need for
+  // consulting mark-bitmap to find where does the next live object start, we
+  // use the object-size returned by VisitRefsForCompaction.
+  //
+  // TODO: Should we do this in reverse? If the probability of accessing an object
+  // is inversely proportional to the object's age, then it may make sense.
+  uint8_t* current_page = bump_pointer_space_->Begin();
+  for (size_t i = 0; i < moving_first_objs_count_; i++) {
+    CompactPage(first_objs_moving_space_[i].AsMirrorPtr(),
+                pre_compact_offset_moving_space_[i],
+                current_page);
+    current_page += kPageSize;
+  }
+}
+
+void MarkCompact::UpdateNonMovingPage(mirror::Object* first, uint8_t* page) {
+  DCHECK_LT(reinterpret_cast<uint8_t*>(first), page + kPageSize);
+  // For every object found in the page, visit the previous object. This ensures
+  // that we can visit without checking page-end boundary.
+  // Call VisitRefsForCompaction with from-space read-barrier as the klass object and
+  // super-class loads require it.
+  // TODO: Set kVisitNativeRoots to false once we implement concurrent
+  // compaction
+  mirror::Object* curr_obj = first;
+  non_moving_space_bitmap_->VisitMarkedRange(
+          reinterpret_cast<uintptr_t>(first) + mirror::kObjectHeaderSize,
+          reinterpret_cast<uintptr_t>(page + kPageSize),
+          [&](mirror::Object* next_obj) {
+            // TODO: Once non-moving space update becomes concurrent, we'll
+            // require fetching the from-space address of 'curr_obj' and then call
+            // visitor on that.
+            if (reinterpret_cast<uint8_t*>(curr_obj) < page) {
+              RefsUpdateVisitor</*kCheckBegin*/true, /*kCheckEnd*/false>
+                      visitor(this, curr_obj, page, page + kPageSize);
+              MemberOffset begin_offset(page - reinterpret_cast<uint8_t*>(curr_obj));
+              // Native roots shouldn't be visited as they are done when this
+              // object's beginning was visited in the preceding page.
+              curr_obj->VisitRefsForCompaction</*kFetchObjSize*/false, /*kVisitNativeRoots*/false>(
+                      visitor, begin_offset, MemberOffset(-1));
+            } else {
+              RefsUpdateVisitor</*kCheckBegin*/false, /*kCheckEnd*/false>
+                      visitor(this, curr_obj, page, page + kPageSize);
+              curr_obj->VisitRefsForCompaction</*kFetchObjSize*/false>(visitor,
+                                                                       MemberOffset(0),
+                                                                       MemberOffset(-1));
+            }
+            curr_obj = next_obj;
+          });
+
+  MemberOffset end_offset(page + kPageSize - reinterpret_cast<uint8_t*>(curr_obj));
+  if (reinterpret_cast<uint8_t*>(curr_obj) < page) {
+    RefsUpdateVisitor</*kCheckBegin*/true, /*kCheckEnd*/true>
+            visitor(this, curr_obj, page, page + kPageSize);
+    curr_obj->VisitRefsForCompaction</*kFetchObjSize*/false>(
+        visitor, MemberOffset(page - reinterpret_cast<uint8_t*>(curr_obj)), end_offset);
+  } else {
+    RefsUpdateVisitor</*kCheckBegin*/false, /*kCheckEnd*/true>
+            visitor(this, curr_obj, page, page + kPageSize);
+    curr_obj->VisitRefsForCompaction</*kFetchObjSize*/false>(visitor, MemberOffset(0), end_offset);
+  }
+}
+
+void MarkCompact::UpdateNonMovingSpace() {
+  uint8_t* page = non_moving_space_->Begin();
+  for (size_t i = 0; i < non_moving_first_objs_count_; i++) {
+    mirror::Object* obj = first_objs_non_moving_space_[i].AsMirrorPtr();
+    // null means there are no objects on the page to update references.
+    if (obj != nullptr) {
+      UpdateNonMovingPage(obj, page);
+    }
+    page += kPageSize;
+  }
+}
+
+void MarkCompact::PreCompactionPhase() {
+  TimingLogger::ScopedTiming t("(Paused)CompactionPhase", GetTimings());
+  non_moving_space_bitmap_ = non_moving_space_->GetLiveBitmap();
+  // TODO: Refresh data-structures to catch-up on allocations that may have
+  // happened since PrepareForCompaction().
+  compacting_ = true;
+  if (!kConcurrentCompaction) {
+    UpdateNonMovingSpace();
+    CompactMovingSpace();
+  }
+}
+
 void MarkCompact::CompactionPhase() {
+  // TODO: This is the concurrent compaction phase.
+  TimingLogger::ScopedTiming t("CompactionPhase", GetTimings());
+  UNIMPLEMENTED(FATAL) << "Unreachable";
 }
 
 template <size_t kBufferSize>
@@ -880,7 +1324,8 @@ void MarkCompact::DelayReferenceReferent(ObjPtr<mirror::Class> klass,
 }
 
 void MarkCompact::FinishPhase() {
-  offset_vector_map_->MadviseDontNeedAndZero();
+  // TODO: unmap/madv_dontneed from-space mappings.
+  info_map_->MadviseDontNeedAndZero();
   live_words_bitmap_->ClearBitmap();
   CHECK(mark_stack_->IsEmpty());  // Ensure that the mark stack is empty.
   mark_stack_->Reset();
diff --git a/runtime/gc/collector/mark_compact.h b/runtime/gc/collector/mark_compact.h
index 0deb5d6775..54fe7dbb55 100644
--- a/runtime/gc/collector/mark_compact.h
+++ b/runtime/gc/collector/mark_compact.h
@@ -98,30 +98,65 @@ class MarkCompact : public GarbageCollector {
       REQUIRES_SHARED(Locks::mutator_lock_, Locks::heap_bitmap_lock_);
 
  private:
+  using ObjReference = mirror::ObjectReference</*kPoisonReferences*/ false, mirror::Object>;
   // Number of bits (live-words) covered by a single offset-vector (below)
   // entry/word.
   // TODO: Since popcount is performed usomg SIMD instructions, we should
   // consider using 128-bit in order to halve the offset-vector size.
-  static constexpr size_t kBitsPerVectorWord = kBitsPerIntPtrT;
-  static constexpr size_t kOffsetChunkSize = kBitsPerVectorWord * kAlignment;
+  static constexpr uint32_t kBitsPerVectorWord = kBitsPerIntPtrT;
+  static constexpr uint32_t kOffsetChunkSize = kBitsPerVectorWord * kAlignment;
+  static_assert(kOffsetChunkSize < kPageSize);
   // Bitmap with bits corresponding to every live word set. For an object
   // which is 4 words in size will have the corresponding 4 bits set. This is
-  // required for efficient computation of new-address (after-compaction) from
-  // the given old-address (pre-compacted).
+  // required for efficient computation of new-address (post-compaction) from
+  // the given old-address (pre-compaction).
   template <size_t kAlignment>
   class LiveWordsBitmap : private accounting::MemoryRangeBitmap<kAlignment> {
     using Bitmap = accounting::Bitmap;
     using MemRangeBitmap = accounting::MemoryRangeBitmap<kAlignment>;
 
    public:
+    static_assert(IsPowerOfTwo(kBitsPerVectorWord));
+    static_assert(IsPowerOfTwo(Bitmap::kBitsPerBitmapWord));
+    static_assert(kBitsPerVectorWord >= Bitmap::kBitsPerBitmapWord);
+    static constexpr uint32_t kBitmapWordsPerVectorWord =
+            kBitsPerVectorWord / Bitmap::kBitsPerBitmapWord;
+    static_assert(IsPowerOfTwo(kBitmapWordsPerVectorWord));
     static LiveWordsBitmap* Create(uintptr_t begin, uintptr_t end);
+
+    // Return offset (within the offset-vector chunk) of the nth live word.
+    uint32_t FindNthLiveWordOffset(size_t offset_vec_idx, uint32_t n) const;
     // Sets all bits in the bitmap corresponding to the given range. Also
     // returns the bit-index of the first word.
-    uintptr_t SetLiveWords(uintptr_t begin, size_t size);
+    ALWAYS_INLINE uintptr_t SetLiveWords(uintptr_t begin, size_t size);
+    // Count number of live words upto the given bit-index. This is to be used
+    // to compute the post-compact address of an old reference.
+    ALWAYS_INLINE size_t CountLiveWordsUpto(size_t bit_idx) const;
+    // Call visitor for every stride of contiguous marked bits in the live-word
+    // bitmap. Passes to the visitor index of the first marked bit in the
+    // stride, stride-size and whether it's the last stride in the given range
+    // or not.
+    template <typename Visitor>
+    ALWAYS_INLINE void VisitLiveStrides(uintptr_t begin_bit_idx,
+                                        const size_t bytes,
+                                        Visitor&& visitor) const;
     void ClearBitmap() { Bitmap::Clear(); }
-    uintptr_t Begin() const { return MemRangeBitmap::CoverBegin(); }
+    ALWAYS_INLINE uintptr_t Begin() const { return MemRangeBitmap::CoverBegin(); }
+    ALWAYS_INLINE bool HasAddress(mirror::Object* obj) const {
+      return MemRangeBitmap::HasAddress(reinterpret_cast<uintptr_t>(obj));
+    }
+    bool Test(uintptr_t bit_index) {
+      return Bitmap::TestBit(bit_index);
+    }
   };
 
+  // For a given pre-compact object, return its from-space address.
+  mirror::Object* GetFromSpaceAddr(mirror::Object* obj) const {
+    DCHECK(live_words_bitmap_->HasAddress(obj) && live_words_bitmap_->Test(obj));
+    uintptr_t offset = reinterpret_cast<uintptr_t>(obj) - live_words_bitmap_->Begin();
+    return reinterpret_cast<mirror::Object*>(from_space_begin_ + offset);
+  }
+
   void InitializePhase();
   void FinishPhase() REQUIRES(!Locks::mutator_lock_, !Locks::heap_bitmap_lock_);
   void MarkingPhase() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::heap_bitmap_lock_);
@@ -130,6 +165,17 @@ class MarkCompact : public GarbageCollector {
   void SweepSystemWeaks(Thread* self, const bool paused)
       REQUIRES_SHARED(Locks::mutator_lock_)
       REQUIRES(!Locks::heap_bitmap_lock_);
+  // Update the reference at given offset in the given object with post-compact
+  // address.
+  ALWAYS_INLINE void UpdateRef(mirror::Object* obj, MemberOffset offset)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+  // Update the given root with post-compact address.
+  ALWAYS_INLINE void UpdateRoot(mirror::CompressedReference<mirror::Object>* root)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+  // Given the pre-compact address, the function returns the post-compact
+  // address of the given object.
+  ALWAYS_INLINE mirror::Object* PostCompactAddress(mirror::Object* old_ref) const
+      REQUIRES_SHARED(Locks::mutator_lock_);
   // Identify immune spaces and reset card-table, mod-union-table, and mark
   // bitmaps.
   void BindAndResetBitmaps() REQUIRES_SHARED(Locks::mutator_lock_)
@@ -145,6 +191,34 @@ class MarkCompact : public GarbageCollector {
   // Compute offset-vector and other data structures required during concurrent
   // compaction
   void PrepareForCompaction() REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // Copy kPageSize live bytes starting from 'offset' (within the moving space),
+  // which must be within 'obj', into the kPageSize sized memory pointed by 'addr'.
+  // Then update the references within the copied objects. The boundary objects are
+  // partially updated such that only the references that lie in the page are updated.
+  // This is necessary to avoid cascading userfaults.
+  void CompactPage(mirror::Object* obj, uint32_t offset, uint8_t* addr)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+  // Compact the bump-pointer space.
+  void CompactMovingSpace() REQUIRES_SHARED(Locks::mutator_lock_);
+  // Update all the objects in the given non-moving space page. 'first' object
+  // could have started in some preceding page.
+  void UpdateNonMovingPage(mirror::Object* first, uint8_t* page)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+  // Update all the references in the non-moving space.
+  void UpdateNonMovingSpace() REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // For all the pages in non-moving space, find the first object that overlaps
+  // with the pages' start address, and store in first_objs_non_moving_space_ array.
+  void InitNonMovingSpaceFirstObjects() REQUIRES_SHARED(Locks::mutator_lock_);
+  // In addition to the first-objects for every post-compact moving space page,
+  // also find offsets within those objects from where the contents should be
+  // copied to the page. The offsets are relative to the moving-space's
+  // beginning. Store the computed first-object and offset in first_objs_moving_space_
+  // and pre_compact_offset_moving_space_ respectively.
+  void InitMovingSpaceFirstObjects(const size_t vec_len) REQUIRES_SHARED(Locks::mutator_lock_);
+
+
   // Perform reference-processing and the likes before sweeping the non-movable
   // spaces.
   void ReclaimPhase() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::heap_bitmap_lock_);
@@ -237,19 +311,43 @@ class MarkCompact : public GarbageCollector {
   // when collecting thread-stack roots using checkpoint.
   Mutex mark_stack_lock_;
   accounting::ObjectStack* mark_stack_;
-  // The main space bitmap
-  accounting::ContinuousSpaceBitmap* current_space_bitmap_;
-  accounting::ContinuousSpaceBitmap* non_moving_space_bitmap_;
   // Special bitmap wherein all the bits corresponding to an object are set.
+  // TODO: make LiveWordsBitmap encapsulated in this class rather than a
+  // pointer. We tend to access its members in performance-sensitive
+  // code-path. Also, use a single MemMap for all the GC's data structures,
+  // which we will clear in the end. This would help in limiting the number of
+  // VMAs that get created in the kernel.
   std::unique_ptr<LiveWordsBitmap<kAlignment>> live_words_bitmap_;
   // Any array of live-bytes in logical chunks of kOffsetChunkSize size
   // in the 'to-be-compacted' space.
-  std::unique_ptr<MemMap> offset_vector_map_;
+  std::unique_ptr<MemMap> info_map_;
   uint32_t* offset_vector_;
+  // The main space bitmap
+  accounting::ContinuousSpaceBitmap* current_space_bitmap_;
+  accounting::ContinuousSpaceBitmap* non_moving_space_bitmap_;
+
+  // For every page in the to-space (post-compact heap) we need to know the
+  // first object from which we must compact and/or update references. This is
+  // for both non-moving and moving space. Additionally, for the moving-space,
+  // we also need the offset within the object from where we need to start
+  // copying.
+  uint32_t* pre_compact_offset_moving_space_;
+  // first_objs_moving_space_[i] is the address of the first object for the ith page
+  ObjReference* first_objs_moving_space_;
+  ObjReference* first_objs_non_moving_space_;
+  size_t non_moving_first_objs_count_;
+  // Number of first-objects in the moving space.
+  size_t moving_first_objs_count_;
+
+  uint8_t* from_space_begin_;
+  uint8_t* black_allocations_begin_;
   size_t vector_length_;
   size_t live_stack_freeze_size_;
+  space::ContinuousSpace* non_moving_space_;
   const space::BumpPointerSpace* bump_pointer_space_;
   Thread* thread_running_gc_;
+  // Set to true when compacting starts.
+  bool compacting_;
 
   class VerifyRootMarkedVisitor;
   class ScanObjectVisitor;
@@ -257,6 +355,7 @@ class MarkCompact : public GarbageCollector {
   template<size_t kBufferSize> class ThreadRootsVisitor;
   class CardModifiedVisitor;
   class RefFieldsVisitor;
+  template <bool kCheckBegin, bool kCheckEnd> class RefsUpdateVisitor;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(MarkCompact);
 };
diff --git a/runtime/mirror/object-refvisitor-inl.h b/runtime/mirror/object-refvisitor-inl.h
index f98c433cdd..2361d79f3f 100644
--- a/runtime/mirror/object-refvisitor-inl.h
+++ b/runtime/mirror/object-refvisitor-inl.h
@@ -90,6 +90,102 @@ inline void Object::VisitReferences(const Visitor& visitor,
   }
 }
 
+// Could be called with from-space address of the object as we access klass and
+// length (in case of arrays/strings) and we don't want to cause cascading faults.
+template <bool kFetchObjSize,
+          bool kVisitNativeRoots,
+          VerifyObjectFlags kVerifyFlags,
+          ReadBarrierOption kReadBarrierOption,
+          typename Visitor>
+inline size_t Object::VisitRefsForCompaction(const Visitor& visitor,
+                                             MemberOffset begin,
+                                             MemberOffset end) {
+  constexpr VerifyObjectFlags kSizeOfFlags = RemoveThisFlags(kVerifyFlags);
+  size_t size;
+  // We want to continue using pre-compact klass to avoid cascading faults.
+  ObjPtr<Class> klass = GetClass<kVerifyFlags, kReadBarrierOption>();
+  visitor(this, ClassOffset(), /* is_static= */ false);
+  const uint32_t class_flags = klass->GetClassFlags<kVerifyNone>();
+  if (LIKELY(class_flags == kClassFlagNormal)) {
+    DCHECK((!klass->IsVariableSize<kVerifyFlags>()));
+    VisitInstanceFieldsReferences<kVerifyFlags, kReadBarrierOption>(klass, visitor);
+    size = kFetchObjSize ? klass->GetObjectSize<kSizeOfFlags>() : 0;
+    DCHECK((!klass->IsClassClass<kVerifyFlags>()));
+    DCHECK(!klass->IsStringClass<kVerifyFlags>());
+    DCHECK(!klass->IsClassLoaderClass<kVerifyFlags>());
+    DCHECK((!klass->IsArrayClass<kVerifyFlags>()));
+  } else {
+    if ((class_flags & kClassFlagNoReferenceFields) == 0) {
+      DCHECK(!klass->IsStringClass<kVerifyFlags>());
+      if (class_flags == kClassFlagClass) {
+        DCHECK((klass->IsClassClass<kVerifyFlags>()));
+        ObjPtr<Class> as_klass = AsClass<kVerifyNone>();
+        as_klass->VisitReferences<kVisitNativeRoots, kVerifyFlags, kReadBarrierOption>(klass,
+                                                                                       visitor);
+        return kFetchObjSize ? as_klass->SizeOf<kSizeOfFlags>() : 0;
+      } else if (class_flags == kClassFlagObjectArray) {
+        DCHECK((klass->IsObjectArrayClass<kVerifyFlags>()));
+        ObjPtr<ObjectArray<mirror::Object>> obj_arr = AsObjectArray<mirror::Object, kVerifyNone>();
+        obj_arr->VisitReferences(visitor, begin, end);
+        return kFetchObjSize ? obj_arr->SizeOf<kSizeOfFlags>() : 0;
+      } else if ((class_flags & kClassFlagReference) != 0) {
+        VisitInstanceFieldsReferences<kVerifyFlags, kReadBarrierOption>(klass, visitor);
+        // Visit referent also as this is about updating the reference only.
+        // There is no reference processing happening here.
+        visitor(this, mirror::Reference::ReferentOffset(), /* is_static= */ false);
+        if ((class_flags & kClassFlagFinalizerReference) != 0) {
+          visitor(this, mirror::FinalizerReference::ZombieOffset(), /* is_static= */ false);
+        }
+      } else if (class_flags == kClassFlagDexCache) {
+        ObjPtr<mirror::DexCache> const dex_cache = AsDexCache<kVerifyFlags, kReadBarrierOption>();
+        dex_cache->VisitReferences<kVisitNativeRoots,
+                                   kVerifyFlags,
+                                   kReadBarrierOption>(klass, visitor);
+      } else {
+        ObjPtr<mirror::ClassLoader> const class_loader =
+            AsClassLoader<kVerifyFlags, kReadBarrierOption>();
+        class_loader->VisitReferences<kVisitNativeRoots,
+                                      kVerifyFlags,
+                                      kReadBarrierOption>(klass, visitor);
+      }
+      size = kFetchObjSize ? klass->GetObjectSize<kSizeOfFlags>() : 0;
+    } else {
+      DCHECK((!klass->IsClassClass<kVerifyFlags>()));
+      DCHECK((!klass->IsObjectArrayClass<kVerifyFlags>()));
+      if (class_flags == kClassFlagString) {
+        size = kFetchObjSize ? AsString<kSizeOfFlags>()->template SizeOf<kSizeOfFlags>() : 0;
+      } else if (klass->IsArrayClass<kVerifyFlags>()) {
+        // TODO: We can optimize this by implementing a SizeOf() version which takes
+        // component-size-shift as an argument, thereby avoiding multiple loads of
+        // component_type.
+        size = kFetchObjSize ? AsArray<kSizeOfFlags>()->template SizeOf<kSizeOfFlags>() : 0;
+      } else {
+        DCHECK_NE(class_flags & kClassFlagNormal, 0u);
+        // Only possibility left is of a normal klass instance with no references.
+        size = kFetchObjSize ? klass->GetObjectSize<kSizeOfFlags>() : 0;
+      }
+
+      if (kIsDebugBuild) {
+        // String still has instance fields for reflection purposes but these don't exist in
+        // actual string instances.
+        if (!klass->IsStringClass<kVerifyFlags>()) {
+          size_t total_reference_instance_fields = 0;
+          ObjPtr<Class> super_class = klass;
+          do {
+            total_reference_instance_fields +=
+                super_class->NumReferenceInstanceFields<kVerifyFlags>();
+            super_class = super_class->GetSuperClass<kVerifyFlags, kReadBarrierOption>();
+          } while (super_class != nullptr);
+          // The only reference field should be the object's class. This field is handled at the
+          // beginning of the function.
+          CHECK_EQ(total_reference_instance_fields, 1u);
+        }
+      }
+    }
+  }
+  return size;
+}
+
 }  // namespace mirror
 }  // namespace art
 
diff --git a/runtime/mirror/object.h b/runtime/mirror/object.h
index ac7274588d..d83f3d6b00 100644
--- a/runtime/mirror/object.h
+++ b/runtime/mirror/object.h
@@ -647,6 +647,17 @@ class MANAGED LOCKABLE Object {
             typename JavaLangRefVisitor = VoidFunctor>
   void VisitReferences(const Visitor& visitor, const JavaLangRefVisitor& ref_visitor)
       NO_THREAD_SAFETY_ANALYSIS;
+  // VisitReferences version for compaction. It is invoked with from-space
+  // object so that portions of the object, like klass and length (for arrays),
+  // can be accessed without causing cascading faults.
+  template <bool kFetchObjSize = true,
+            bool kVisitNativeRoots = true,
+            VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags,
+            ReadBarrierOption kReadBarrierOption = kWithReadBarrier,
+            typename Visitor>
+  size_t VisitRefsForCompaction(const Visitor& visitor,
+                                MemberOffset begin,
+                                MemberOffset end) NO_THREAD_SAFETY_ANALYSIS;
 
   ArtField* FindFieldByOffset(MemberOffset offset) REQUIRES_SHARED(Locks::mutator_lock_);
 
diff --git a/runtime/mirror/object_array-inl.h b/runtime/mirror/object_array-inl.h
index e4fe03b357..1bd0185743 100644
--- a/runtime/mirror/object_array-inl.h
+++ b/runtime/mirror/object_array-inl.h
@@ -327,7 +327,20 @@ template<class T> template<typename Visitor>
 inline void ObjectArray<T>::VisitReferences(const Visitor& visitor) {
   const size_t length = static_cast<size_t>(GetLength());
   for (size_t i = 0; i < length; ++i) {
-    visitor(this, OffsetOfElement(i), false);
+    visitor(this, OffsetOfElement(i), /* is_static= */ false);
+  }
+}
+
+template<class T> template<typename Visitor>
+inline void ObjectArray<T>::VisitReferences(const Visitor& visitor,
+                                            MemberOffset begin,
+                                            MemberOffset end) {
+  const size_t length = static_cast<size_t>(GetLength());
+  begin = std::max(begin, OffsetOfElement(0));
+  end = std::min(end, OffsetOfElement(length));
+  while (begin < end) {
+    visitor(this, begin, /* is_static= */ false, /*is_obj_array*/ true);
+    begin += kHeapReferenceSize;
   }
 }
 
diff --git a/runtime/mirror/object_array.h b/runtime/mirror/object_array.h
index a20c86b82e..9a53708018 100644
--- a/runtime/mirror/object_array.h
+++ b/runtime/mirror/object_array.h
@@ -150,6 +150,10 @@ class MANAGED ObjectArray: public Array {
   // REQUIRES_SHARED(Locks::mutator_lock_).
   template<typename Visitor>
   void VisitReferences(const Visitor& visitor) NO_THREAD_SAFETY_ANALYSIS;
+  template<typename Visitor>
+  void VisitReferences(const Visitor& visitor,
+                       MemberOffset begin,
+                       MemberOffset end) NO_THREAD_SAFETY_ANALYSIS;
 
   friend class Object;  // For VisitReferences
   DISALLOW_IMPLICIT_CONSTRUCTORS(ObjectArray);
diff --git a/runtime/offsets.h b/runtime/offsets.h
index cc18bf4f74..7974111851 100644
--- a/runtime/offsets.h
+++ b/runtime/offsets.h
@@ -37,12 +37,28 @@ class Offset {
   constexpr size_t SizeValue() const {
     return val_;
   }
+  Offset& operator+=(const size_t rhs) {
+    val_ += rhs;
+    return *this;
+  }
   constexpr bool operator==(Offset o) const {
     return SizeValue() == o.SizeValue();
   }
   constexpr bool operator!=(Offset o) const {
     return !(*this == o);
   }
+  constexpr bool operator<(Offset o) const {
+    return SizeValue() < o.SizeValue();
+  }
+  constexpr bool operator<=(Offset o) const {
+    return !(*this > o);
+  }
+  constexpr bool operator>(Offset o) const {
+    return o < *this;
+  }
+  constexpr bool operator>=(Offset o) const {
+    return !(*this < o);
+  }
 
  protected:
   size_t val_;
diff --git a/runtime/read_barrier-inl.h b/runtime/read_barrier-inl.h
index b0434d8a81..6bc8f0b979 100644
--- a/runtime/read_barrier-inl.h
+++ b/runtime/read_barrier-inl.h
@@ -91,6 +91,10 @@ inline MirrorType* ReadBarrier::Barrier(
       LOG(FATAL) << "Unexpected read barrier type";
       UNREACHABLE();
     }
+  } else if (with_read_barrier) {
+    // TODO: invoke MarkCompact's function which translates a pre-compact
+    // address to from-space address, if we are in the compaction phase.
+    return ref_addr->template AsMirrorPtr<kIsVolatile>();
   } else {
     // No read barrier.
     return ref_addr->template AsMirrorPtr<kIsVolatile>();