More of the concurrent copying collector.

Bug: 12687968
Change-Id: I62f70274d47df6d6cab714df95c518b750ce3105

18 files changed, 3524 insertions, 43 deletions

diff --git a/runtime/gc/accounting/heap_bitmap-inl.h b/runtime/gc/accounting/heap_bitmap-inl.h
index 34c15c7f8b..8fcc87d3a1 100644
--- a/runtime/gc/accounting/heap_bitmap-inl.h
+++ b/runtime/gc/accounting/heap_bitmap-inl.h
@@ -105,6 +105,15 @@ inline ContinuousSpaceBitmap* HeapBitmap::GetContinuousSpaceBitmap(const mirror:
   return nullptr;
 }
 
+inline LargeObjectBitmap* HeapBitmap::GetLargeObjectBitmap(const mirror::Object* obj) const {
+  for (const auto& bitmap : large_object_bitmaps_) {
+    if (LIKELY(bitmap->HasAddress(obj))) {
+      return bitmap;
+    }
+  }
+  return nullptr;
+}
+
 }  // namespace accounting
 }  // namespace gc
 }  // namespace art
diff --git a/runtime/gc/accounting/heap_bitmap.h b/runtime/gc/accounting/heap_bitmap.h
index ca6dc46bde..245e074294 100644
--- a/runtime/gc/accounting/heap_bitmap.h
+++ b/runtime/gc/accounting/heap_bitmap.h
@@ -27,6 +27,10 @@ namespace gc {
 
 class Heap;
 
+namespace collector {
+  class ConcurrentCopying;
+}  // namespace collector
+
 namespace accounting {
 
 class HeapBitmap {
@@ -40,6 +44,7 @@ class HeapBitmap {
   bool AtomicTestAndSet(const mirror::Object* obj, const LargeObjectSetVisitor& visitor)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) ALWAYS_INLINE;
   ContinuousSpaceBitmap* GetContinuousSpaceBitmap(const mirror::Object* obj) const;
+  LargeObjectBitmap* GetLargeObjectBitmap(const mirror::Object* obj) const;
 
   void Walk(ObjectCallback* callback, void* arg)
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
@@ -78,6 +83,7 @@ class HeapBitmap {
       large_object_bitmaps_;
 
   friend class art::gc::Heap;
+  friend class art::gc::collector::ConcurrentCopying;
 };
 
 }  // namespace accounting
diff --git a/runtime/gc/accounting/read_barrier_table.h b/runtime/gc/accounting/read_barrier_table.h
new file mode 100644
index 0000000000..84d5da3ba7
--- /dev/null
+++ b/runtime/gc/accounting/read_barrier_table.h
@@ -0,0 +1,118 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_GC_ACCOUNTING_READ_BARRIER_TABLE_H_
+#define ART_RUNTIME_GC_ACCOUNTING_READ_BARRIER_TABLE_H_
+
+#include "base/mutex.h"
+#include "gc/space/space.h"
+#include "globals.h"
+#include "mem_map.h"
+
+namespace art {
+namespace gc {
+namespace accounting {
+
+// Used to decide whether to take the read barrier fast/slow paths for
+// kUseTableLookupReadBarrier. If an entry is set, take the read
+// barrier slow path. There's an entry per region.
+class ReadBarrierTable {
+ public:
+  ReadBarrierTable() {
+    size_t capacity = static_cast<size_t>(kHeapCapacity / kRegionSize);
+    DCHECK_EQ(kHeapCapacity / kRegionSize,
+              static_cast<uint64_t>(static_cast<size_t>(kHeapCapacity / kRegionSize)));
+    std::string error_msg;
+    MemMap* mem_map = MemMap::MapAnonymous("read barrier table", nullptr, capacity,
+                                           PROT_READ | PROT_WRITE, false, &error_msg);
+    CHECK(mem_map != nullptr && mem_map->Begin() != nullptr)
+        << "couldn't allocate read barrier table: " << error_msg;
+    mem_map_.reset(mem_map);
+  }
+  void ClearForSpace(space::ContinuousSpace* space) {
+    uint8_t* entry_start = EntryFromAddr(space->Begin());
+    uint8_t* entry_end = EntryFromAddr(space->Limit());
+    memset(reinterpret_cast<void*>(entry_start), 0, entry_end - entry_start);
+  }
+  void Clear(uint8_t* start_addr, uint8_t* end_addr) {
+    DCHECK(IsValidHeapAddr(start_addr)) << start_addr;
+    DCHECK(IsValidHeapAddr(end_addr)) << end_addr;
+    DCHECK(IsAligned<kRegionSize>(start_addr));
+    DCHECK(IsAligned<kRegionSize>(end_addr));
+    uint8_t* entry_start = EntryFromAddr(start_addr);
+    uint8_t* entry_end = EntryFromAddr(end_addr);
+    memset(reinterpret_cast<void*>(entry_start), 0, entry_end - entry_start);
+  }
+  bool IsSet(const void* heap_addr) const {
+    DCHECK(IsValidHeapAddr(heap_addr)) << heap_addr;
+    uint8_t entry_value = *EntryFromAddr(heap_addr);
+    DCHECK(entry_value == 0 || entry_value == kSetEntryValue);
+    return entry_value == kSetEntryValue;
+  }
+  void ClearAll() {
+    mem_map_->MadviseDontNeedAndZero();
+  }
+  void SetAll() {
+    memset(mem_map_->Begin(), kSetEntryValue, mem_map_->Size());
+  }
+  bool IsAllCleared() const {
+    for (uint32_t* p = reinterpret_cast<uint32_t*>(mem_map_->Begin());
+         p < reinterpret_cast<uint32_t*>(mem_map_->End()); ++p) {
+      if (*p != 0) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  // This should match RegionSpace::kRegionSize. static_assert'ed in concurrent_copying.h.
+  static constexpr size_t kRegionSize = 1 * MB;
+
+ private:
+  static constexpr uint64_t kHeapCapacity = 4ULL * GB;  // low 4gb.
+  static constexpr uint8_t kSetEntryValue = 0x01;
+
+  uint8_t* EntryFromAddr(const void* heap_addr) const {
+    DCHECK(IsValidHeapAddr(heap_addr)) << heap_addr;
+    uint8_t* entry_addr = mem_map_->Begin() + reinterpret_cast<uintptr_t>(heap_addr) / kRegionSize;
+    DCHECK(IsValidEntry(entry_addr)) << "heap_addr: " << heap_addr
+                                     << " entry_addr: " << reinterpret_cast<void*>(entry_addr);
+    return entry_addr;
+  }
+
+  bool IsValidHeapAddr(const void* heap_addr) const {
+#ifdef __LP64__
+    return reinterpret_cast<uint64_t>(heap_addr) < kHeapCapacity;
+#else
+    UNUSED(heap_addr);
+    return true;
+#endif
+  }
+
+  bool IsValidEntry(const uint8_t* entry_addr) const {
+    uint8_t* begin = mem_map_->Begin();
+    uint8_t* end = mem_map_->End();
+    return entry_addr >= begin && entry_addr < end;
+  }
+
+  std::unique_ptr<MemMap> mem_map_;
+};
+
+}  // namespace accounting
+}  // namespace gc
+}  // namespace art
+
+#endif  // ART_RUNTIME_GC_ACCOUNTING_READ_BARRIER_TABLE_H_
diff --git a/runtime/gc/allocator_type.h b/runtime/gc/allocator_type.h
index c6ebc7384c..f9a2ff6bc8 100644
--- a/runtime/gc/allocator_type.h
+++ b/runtime/gc/allocator_type.h
@@ -30,6 +30,8 @@ enum AllocatorType {
   kAllocatorTypeDlMalloc,  // Use dlmalloc allocator, has entrypoints.
   kAllocatorTypeNonMoving,  // Special allocator for non moving objects, doesn't have entrypoints.
   kAllocatorTypeLOS,  // Large object space, also doesn't have entrypoints.
+  kAllocatorTypeRegion,
+  kAllocatorTypeRegionTLAB,
 };
 std::ostream& operator<<(std::ostream& os, const AllocatorType& rhs);
 
diff --git a/runtime/gc/collector/concurrent_copying.cc b/runtime/gc/collector/concurrent_copying.cc
index 079eeba8a4..5fa3c8b342 100644
--- a/runtime/gc/collector/concurrent_copying.cc
+++ b/runtime/gc/collector/concurrent_copying.cc
@@ -16,10 +16,1627 @@
 
 #include "concurrent_copying.h"
 
+#include "gc/accounting/heap_bitmap-inl.h"
+#include "gc/accounting/space_bitmap-inl.h"
+#include "gc/space/image_space.h"
+#include "gc/space/space.h"
+#include "intern_table.h"
+#include "mirror/art_field-inl.h"
+#include "mirror/object-inl.h"
+#include "scoped_thread_state_change.h"
+#include "thread-inl.h"
+#include "thread_list.h"
+#include "well_known_classes.h"
+
 namespace art {
 namespace gc {
 namespace collector {
 
+ConcurrentCopying::ConcurrentCopying(Heap* heap, const std::string& name_prefix)
+    : GarbageCollector(heap,
+                       name_prefix + (name_prefix.empty() ? "" : " ") +
+                       "concurrent copying + mark sweep"),
+      region_space_(nullptr), gc_barrier_(new Barrier(0)), mark_queue_(2 * MB),
+      is_marking_(false), is_active_(false), is_asserting_to_space_invariant_(false),
+      heap_mark_bitmap_(nullptr), live_stack_freeze_size_(0),
+      skipped_blocks_lock_("concurrent copying bytes blocks lock", kMarkSweepMarkStackLock),
+      rb_table_(heap_->GetReadBarrierTable()),
+      force_evacuate_all_(false) {
+  static_assert(space::RegionSpace::kRegionSize == accounting::ReadBarrierTable::kRegionSize,
+                "The region space size and the read barrier table region size must match");
+  cc_heap_bitmap_.reset(new accounting::HeapBitmap(heap));
+  {
+    Thread* self = Thread::Current();
+    ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
+    // Cache this so that we won't have to lock heap_bitmap_lock_ in
+    // Mark() which could cause a nested lock on heap_bitmap_lock_
+    // when GC causes a RB while doing GC or a lock order violation
+    // (class_linker_lock_ and heap_bitmap_lock_).
+    heap_mark_bitmap_ = heap->GetMarkBitmap();
+  }
+}
+
+ConcurrentCopying::~ConcurrentCopying() {
+}
+
+void ConcurrentCopying::RunPhases() {
+  CHECK(kUseBakerReadBarrier || kUseTableLookupReadBarrier);
+  CHECK(!is_active_);
+  is_active_ = true;
+  Thread* self = Thread::Current();
+  Locks::mutator_lock_->AssertNotHeld(self);
+  {
+    ReaderMutexLock mu(self, *Locks::mutator_lock_);
+    InitializePhase();
+  }
+  FlipThreadRoots();
+  {
+    ReaderMutexLock mu(self, *Locks::mutator_lock_);
+    MarkingPhase();
+  }
+  // Verify no from space refs. This causes a pause.
+  if (kEnableNoFromSpaceRefsVerification || kIsDebugBuild) {
+    TimingLogger::ScopedTiming split("(Paused)VerifyNoFromSpaceReferences", GetTimings());
+    ScopedPause pause(this);
+    CheckEmptyMarkQueue();
+    if (kVerboseMode) {
+      LOG(INFO) << "Verifying no from-space refs";
+    }
+    VerifyNoFromSpaceReferences();
+    CheckEmptyMarkQueue();
+  }
+  {
+    ReaderMutexLock mu(self, *Locks::mutator_lock_);
+    ReclaimPhase();
+  }
+  FinishPhase();
+  CHECK(is_active_);
+  is_active_ = false;
+}
+
+void ConcurrentCopying::BindBitmaps() {
+  Thread* self = Thread::Current();
+  WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
+  // Mark all of the spaces we never collect as immune.
+  for (const auto& space : heap_->GetContinuousSpaces()) {
+    if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect
+        || space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect) {
+      CHECK(space->IsZygoteSpace() || space->IsImageSpace());
+      CHECK(immune_region_.AddContinuousSpace(space)) << "Failed to add space " << *space;
+      const char* bitmap_name = space->IsImageSpace() ? "cc image space bitmap" :
+          "cc zygote space bitmap";
+      // TODO: try avoiding using bitmaps for image/zygote to save space.
+      accounting::ContinuousSpaceBitmap* bitmap =
+          accounting::ContinuousSpaceBitmap::Create(bitmap_name, space->Begin(), space->Capacity());
+      cc_heap_bitmap_->AddContinuousSpaceBitmap(bitmap);
+      cc_bitmaps_.push_back(bitmap);
+    } else if (space == region_space_) {
+      accounting::ContinuousSpaceBitmap* bitmap =
+          accounting::ContinuousSpaceBitmap::Create("cc region space bitmap",
+                                                    space->Begin(), space->Capacity());
+      cc_heap_bitmap_->AddContinuousSpaceBitmap(bitmap);
+      cc_bitmaps_.push_back(bitmap);
+      region_space_bitmap_ = bitmap;
+    }
+  }
+}
+
+void ConcurrentCopying::InitializePhase() {
+  TimingLogger::ScopedTiming split("InitializePhase", GetTimings());
+  if (kVerboseMode) {
+    LOG(INFO) << "GC InitializePhase";
+    LOG(INFO) << "Region-space : " << reinterpret_cast<void*>(region_space_->Begin()) << "-"
+              << reinterpret_cast<void*>(region_space_->Limit());
+  }
+  CHECK(mark_queue_.IsEmpty());
+  immune_region_.Reset();
+  bytes_moved_.StoreRelaxed(0);
+  objects_moved_.StoreRelaxed(0);
+  if (GetCurrentIteration()->GetGcCause() == kGcCauseExplicit ||
+      GetCurrentIteration()->GetGcCause() == kGcCauseForNativeAlloc ||
+      GetCurrentIteration()->GetClearSoftReferences()) {
+    force_evacuate_all_ = true;
+  } else {
+    force_evacuate_all_ = false;
+  }
+  BindBitmaps();
+  if (kVerboseMode) {
+    LOG(INFO) << "force_evacuate_all=" << force_evacuate_all_;
+    LOG(INFO) << "Immune region: " << immune_region_.Begin() << "-" << immune_region_.End();
+    LOG(INFO) << "GC end of InitializePhase";
+  }
+}
+
+// Used to switch the thread roots of a thread from from-space refs to to-space refs.
+class ThreadFlipVisitor : public Closure {
+ public:
+  explicit ThreadFlipVisitor(ConcurrentCopying* concurrent_copying, bool use_tlab)
+      : concurrent_copying_(concurrent_copying), use_tlab_(use_tlab) {
+  }
+
+  virtual void Run(Thread* thread) OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    // Note: self is not necessarily equal to thread since thread may be suspended.
+    Thread* self = Thread::Current();
+    CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc)
+        << thread->GetState() << " thread " << thread << " self " << self;
+    if (use_tlab_ && thread->HasTlab()) {
+      if (ConcurrentCopying::kEnableFromSpaceAccountingCheck) {
+        // This must come before the revoke.
+        size_t thread_local_objects = thread->GetThreadLocalObjectsAllocated();
+        concurrent_copying_->region_space_->RevokeThreadLocalBuffers(thread);
+        reinterpret_cast<Atomic<size_t>*>(&concurrent_copying_->from_space_num_objects_at_first_pause_)->
+            FetchAndAddSequentiallyConsistent(thread_local_objects);
+      } else {
+        concurrent_copying_->region_space_->RevokeThreadLocalBuffers(thread);
+      }
+    }
+    if (kUseThreadLocalAllocationStack) {
+      thread->RevokeThreadLocalAllocationStack();
+    }
+    ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
+    thread->VisitRoots(ConcurrentCopying::ProcessRootCallback, concurrent_copying_);
+    concurrent_copying_->GetBarrier().Pass(self);
+  }
+
+ private:
+  ConcurrentCopying* const concurrent_copying_;
+  const bool use_tlab_;
+};
+
+// Called back from Runtime::FlipThreadRoots() during a pause.
+class FlipCallback : public Closure {
+ public:
+  explicit FlipCallback(ConcurrentCopying* concurrent_copying)
+      : concurrent_copying_(concurrent_copying) {
+  }
+
+  virtual void Run(Thread* thread) OVERRIDE EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    ConcurrentCopying* cc = concurrent_copying_;
+    TimingLogger::ScopedTiming split("(Paused)FlipCallback", cc->GetTimings());
+    // Note: self is not necessarily equal to thread since thread may be suspended.
+    Thread* self = Thread::Current();
+    CHECK(thread == self);
+    Locks::mutator_lock_->AssertExclusiveHeld(self);
+    cc->region_space_->SetFromSpace(cc->rb_table_, cc->force_evacuate_all_);
+    cc->SwapStacks(self);
+    if (ConcurrentCopying::kEnableFromSpaceAccountingCheck) {
+      cc->RecordLiveStackFreezeSize(self);
+      cc->from_space_num_objects_at_first_pause_ = cc->region_space_->GetObjectsAllocated();
+      cc->from_space_num_bytes_at_first_pause_ = cc->region_space_->GetBytesAllocated();
+    }
+    cc->is_marking_ = true;
+    if (UNLIKELY(Runtime::Current()->IsActiveTransaction())) {
+      CHECK(Runtime::Current()->IsCompiler());
+      TimingLogger::ScopedTiming split2("(Paused)VisitTransactionRoots", cc->GetTimings());
+      Runtime::Current()->VisitTransactionRoots(ConcurrentCopying::ProcessRootCallback, cc);
+    }
+  }
+
+ private:
+  ConcurrentCopying* const concurrent_copying_;
+};
+
+// Switch threads that from from-space to to-space refs. Forward/mark the thread roots.
+void ConcurrentCopying::FlipThreadRoots() {
+  TimingLogger::ScopedTiming split("FlipThreadRoots", GetTimings());
+  if (kVerboseMode) {
+    LOG(INFO) << "time=" << region_space_->Time();
+    region_space_->DumpNonFreeRegions(LOG(INFO));
+  }
+  Thread* self = Thread::Current();
+  Locks::mutator_lock_->AssertNotHeld(self);
+  gc_barrier_->Init(self, 0);
+  ThreadFlipVisitor thread_flip_visitor(this, heap_->use_tlab_);
+  FlipCallback flip_callback(this);
+  size_t barrier_count = Runtime::Current()->FlipThreadRoots(
+      &thread_flip_visitor, &flip_callback, this);
+  {
+    ScopedThreadStateChange tsc(self, kWaitingForCheckPointsToRun);
+    gc_barrier_->Increment(self, barrier_count);
+  }
+  is_asserting_to_space_invariant_ = true;
+  QuasiAtomic::ThreadFenceForConstructor();
+  if (kVerboseMode) {
+    LOG(INFO) << "time=" << region_space_->Time();
+    region_space_->DumpNonFreeRegions(LOG(INFO));
+    LOG(INFO) << "GC end of FlipThreadRoots";
+  }
+}
+
+void ConcurrentCopying::SwapStacks(Thread* self) {
+  heap_->SwapStacks(self);
+}
+
+void ConcurrentCopying::RecordLiveStackFreezeSize(Thread* self) {
+  WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
+  live_stack_freeze_size_ = heap_->GetLiveStack()->Size();
+}
+
+// Used to visit objects in the immune spaces.
+class ConcurrentCopyingImmuneSpaceObjVisitor {
+ public:
+  explicit ConcurrentCopyingImmuneSpaceObjVisitor(ConcurrentCopying* cc)
+      : collector_(cc) {}
+
+  void operator()(mirror::Object* obj) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
+    DCHECK(obj != nullptr);
+    DCHECK(collector_->immune_region_.ContainsObject(obj));
+    accounting::ContinuousSpaceBitmap* cc_bitmap =
+        collector_->cc_heap_bitmap_->GetContinuousSpaceBitmap(obj);
+    DCHECK(cc_bitmap != nullptr)
+        << "An immune space object must have a bitmap";
+    if (kIsDebugBuild) {
+      DCHECK(collector_->heap_->GetMarkBitmap()->Test(obj))
+          << "Immune space object must be already marked";
+    }
+    // This may or may not succeed, which is ok.
+    if (kUseBakerReadBarrier) {
+      obj->AtomicSetReadBarrierPointer(ReadBarrier::WhitePtr(), ReadBarrier::GrayPtr());
+    }
+    if (cc_bitmap->AtomicTestAndSet(obj)) {
+      // Already marked. Do nothing.
+    } else {
+      // Newly marked. Set the gray bit and push it onto the mark stack.
+      CHECK(!kUseBakerReadBarrier || obj->GetReadBarrierPointer() == ReadBarrier::GrayPtr());
+      collector_->PushOntoMarkStack<true>(obj);
+    }
+  }
+
+ private:
+  ConcurrentCopying* collector_;
+};
+
+class EmptyCheckpoint : public Closure {
+ public:
+  explicit EmptyCheckpoint(ConcurrentCopying* concurrent_copying)
+      : concurrent_copying_(concurrent_copying) {
+  }
+
+  virtual void Run(Thread* thread) OVERRIDE NO_THREAD_SAFETY_ANALYSIS {
+    // Note: self is not necessarily equal to thread since thread may be suspended.
+    Thread* self = Thread::Current();
+    CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc)
+        << thread->GetState() << " thread " << thread << " self " << self;
+    concurrent_copying_->GetBarrier().Pass(self);
+  }
+
+ private:
+  ConcurrentCopying* const concurrent_copying_;
+};
+
+// Concurrently mark roots that are guarded by read barriers and process the mark stack.
+void ConcurrentCopying::MarkingPhase() {
+  TimingLogger::ScopedTiming split("MarkingPhase", GetTimings());
+  if (kVerboseMode) {
+    LOG(INFO) << "GC MarkingPhase";
+  }
+  {
+    // Mark the image root. The WB-based collectors do not need to
+    // scan the image objects from roots by relying on the card table,
+    // but it's necessary for the RB to-space invariant to hold.
+    TimingLogger::ScopedTiming split1("VisitImageRoots", GetTimings());
+    gc::space::ImageSpace* image = heap_->GetImageSpace();
+    if (image != nullptr) {
+      mirror::ObjectArray<mirror::Object>* image_root = image->GetImageHeader().GetImageRoots();
+      mirror::Object* marked_image_root = Mark(image_root);
+      CHECK_EQ(image_root, marked_image_root) << "An image object does not move";
+      if (ReadBarrier::kEnableToSpaceInvariantChecks) {
+        AssertToSpaceInvariant(nullptr, MemberOffset(0), marked_image_root);
+      }
+    }
+  }
+  {
+    TimingLogger::ScopedTiming split2("VisitConstantRoots", GetTimings());
+    Runtime::Current()->VisitConstantRoots(ProcessRootCallback, this);
+  }
+  {
+    TimingLogger::ScopedTiming split3("VisitInternTableRoots", GetTimings());
+    Runtime::Current()->GetInternTable()->VisitRoots(ProcessRootCallback,
+                                                     this, kVisitRootFlagAllRoots);
+  }
+  {
+    TimingLogger::ScopedTiming split4("VisitClassLinkerRoots", GetTimings());
+    Runtime::Current()->GetClassLinker()->VisitRoots(ProcessRootCallback,
+                                                     this, kVisitRootFlagAllRoots);
+  }
+  {
+    // TODO: don't visit the transaction roots if it's not active.
+    TimingLogger::ScopedTiming split5("VisitNonThreadRoots", GetTimings());
+    Runtime::Current()->VisitNonThreadRoots(ProcessRootCallback, this);
+  }
+
+  // Immune spaces.
+  for (auto& space : heap_->GetContinuousSpaces()) {
+    if (immune_region_.ContainsSpace(space)) {
+      DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
+      accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
+      ConcurrentCopyingImmuneSpaceObjVisitor visitor(this);
+      live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
+                                    reinterpret_cast<uintptr_t>(space->Limit()),
+                                    visitor);
+    }
+  }
+
+  Thread* self = Thread::Current();
+  {
+    TimingLogger::ScopedTiming split6("ProcessMarkStack", GetTimings());
+    // Process the mark stack and issue an empty check point. If the
+    // mark stack is still empty after the check point, we're
+    // done. Otherwise, repeat.
+    ProcessMarkStack();
+    size_t count = 0;
+    while (!ProcessMarkStack()) {
+      ++count;
+      if (kVerboseMode) {
+        LOG(INFO) << "Issue an empty check point. " << count;
+      }
+      IssueEmptyCheckpoint();
+    }
+    // Need to ensure the mark stack is empty before reference
+    // processing to get rid of non-reference gray objects.
+    CheckEmptyMarkQueue();
+    // Enable the GetReference slow path and disallow access to the system weaks.
+    GetHeap()->GetReferenceProcessor()->EnableSlowPath();
+    Runtime::Current()->DisallowNewSystemWeaks();
+    QuasiAtomic::ThreadFenceForConstructor();
+    // Lock-unlock the system weak locks so that there's no thread in
+    // the middle of accessing system weaks.
+    Runtime::Current()->EnsureNewSystemWeaksDisallowed();
+    // Note: Do not issue a checkpoint from here to the
+    // SweepSystemWeaks call or else a deadlock due to
+    // WaitHoldingLocks() would occur.
+    if (kVerboseMode) {
+      LOG(INFO) << "Enabled the ref proc slow path & disabled access to system weaks.";
+      LOG(INFO) << "ProcessReferences";
+    }
+    ProcessReferences(self, true);
+    CheckEmptyMarkQueue();
+    if (kVerboseMode) {
+      LOG(INFO) << "SweepSystemWeaks";
+    }
+    SweepSystemWeaks(self);
+    if (kVerboseMode) {
+      LOG(INFO) << "SweepSystemWeaks done";
+    }
+    // Because hash_set::Erase() can call the hash function for
+    // arbitrary elements in the weak intern table in
+    // InternTable::Table::SweepWeaks(), the above SweepSystemWeaks()
+    // call may have marked some objects (strings) alive. So process
+    // the mark stack here once again.
+    ProcessMarkStack();
+    CheckEmptyMarkQueue();
+    // Disable marking.
+    if (kUseTableLookupReadBarrier) {
+      heap_->rb_table_->ClearAll();
+      DCHECK(heap_->rb_table_->IsAllCleared());
+    }
+    is_mark_queue_push_disallowed_.StoreSequentiallyConsistent(1);
+    is_marking_ = false;
+    if (kVerboseMode) {
+      LOG(INFO) << "AllowNewSystemWeaks";
+    }
+    Runtime::Current()->AllowNewSystemWeaks();
+    CheckEmptyMarkQueue();
+  }
+
+  if (kVerboseMode) {
+    LOG(INFO) << "GC end of MarkingPhase";
+  }
+}
+
+void ConcurrentCopying::IssueEmptyCheckpoint() {
+  Thread* self = Thread::Current();
+  EmptyCheckpoint check_point(this);
+  ThreadList* thread_list = Runtime::Current()->GetThreadList();
+  gc_barrier_->Init(self, 0);
+  size_t barrier_count = thread_list->RunCheckpoint(&check_point);
+  // Release locks then wait for all mutator threads to pass the barrier.
+  Locks::mutator_lock_->SharedUnlock(self);
+  {
+    ScopedThreadStateChange tsc(self, kWaitingForCheckPointsToRun);
+    gc_barrier_->Increment(self, barrier_count);
+  }
+  Locks::mutator_lock_->SharedLock(self);
+}
+
+mirror::Object* ConcurrentCopying::PopOffMarkStack() {
+  return mark_queue_.Dequeue();
+}
+
+template<bool kThreadSafe>
+void ConcurrentCopying::PushOntoMarkStack(mirror::Object* to_ref) {
+  CHECK_EQ(is_mark_queue_push_disallowed_.LoadRelaxed(), 0)
+      << " " << to_ref << " " << PrettyTypeOf(to_ref);
+  if (kThreadSafe) {
+    CHECK(mark_queue_.Enqueue(to_ref)) << "Mark queue overflow";
+  } else {
+    CHECK(mark_queue_.EnqueueThreadUnsafe(to_ref)) << "Mark queue overflow";
+  }
+}
+
+accounting::ObjectStack* ConcurrentCopying::GetAllocationStack() {
+  return heap_->allocation_stack_.get();
+}
+
+accounting::ObjectStack* ConcurrentCopying::GetLiveStack() {
+  return heap_->live_stack_.get();
+}
+
+inline mirror::Object* ConcurrentCopying::GetFwdPtr(mirror::Object* from_ref) {
+  DCHECK(region_space_->IsInFromSpace(from_ref));
+  LockWord lw = from_ref->GetLockWord(false);
+  if (lw.GetState() == LockWord::kForwardingAddress) {
+    mirror::Object* fwd_ptr = reinterpret_cast<mirror::Object*>(lw.ForwardingAddress());
+    CHECK(fwd_ptr != nullptr);
+    return fwd_ptr;
+  } else {
+    return nullptr;
+  }
+}
+
+inline void ConcurrentCopying::SetFwdPtr(mirror::Object* from_ref, mirror::Object* to_ref) {
+  DCHECK(region_space_->IsInFromSpace(from_ref));
+  DCHECK(region_space_->IsInToSpace(to_ref) || heap_->GetNonMovingSpace()->HasAddress(to_ref));
+  LockWord lw = from_ref->GetLockWord(false);
+  DCHECK_NE(lw.GetState(), LockWord::kForwardingAddress);
+  from_ref->SetLockWord(LockWord::FromForwardingAddress(reinterpret_cast<size_t>(to_ref)), false);
+}
+
+// The following visitors are that used to verify that there's no
+// references to the from-space left after marking.
+class ConcurrentCopyingVerifyNoFromSpaceRefsVisitor {
+ public:
+  explicit ConcurrentCopyingVerifyNoFromSpaceRefsVisitor(ConcurrentCopying* collector)
+      : collector_(collector) {}
+
+  void operator()(mirror::Object* ref) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
+    if (ref == nullptr) {
+      // OK.
+      return;
+    }
+    collector_->AssertToSpaceInvariant(nullptr, MemberOffset(0), ref);
+    if (kUseBakerReadBarrier) {
+      if (collector_->RegionSpace()->IsInToSpace(ref)) {
+        CHECK(ref->GetReadBarrierPointer() == nullptr)
+            << "To-space ref " << ref << " " << PrettyTypeOf(ref)
+            << " has non-white rb_ptr " << ref->GetReadBarrierPointer();
+      } else {
+        CHECK(ref->GetReadBarrierPointer() == ReadBarrier::BlackPtr() ||
+              (ref->GetReadBarrierPointer() == ReadBarrier::WhitePtr() &&
+               collector_->IsOnAllocStack(ref)))
+            << "Non-moving/unevac from space ref " << ref << " " << PrettyTypeOf(ref)
+            << " has non-black rb_ptr " << ref->GetReadBarrierPointer()
+            << " but isn't on the alloc stack (and has white rb_ptr)."
+            << " Is it in the non-moving space="
+            << (collector_->GetHeap()->GetNonMovingSpace()->HasAddress(ref));
+      }
+    }
+  }
+
+  static void RootCallback(mirror::Object** root, void *arg, const RootInfo& /*root_info*/)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    ConcurrentCopying* collector = reinterpret_cast<ConcurrentCopying*>(arg);
+    ConcurrentCopyingVerifyNoFromSpaceRefsVisitor visitor(collector);
+    DCHECK(root != nullptr);
+    visitor(*root);
+  }
+
+ private:
+  ConcurrentCopying* collector_;
+};
+
+class ConcurrentCopyingVerifyNoFromSpaceRefsFieldVisitor {
+ public:
+  explicit ConcurrentCopyingVerifyNoFromSpaceRefsFieldVisitor(ConcurrentCopying* collector)
+      : collector_(collector) {}
+
+  void operator()(mirror::Object* obj, MemberOffset offset, bool /* is_static */) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
+    mirror::Object* ref =
+        obj->GetFieldObject<mirror::Object, kDefaultVerifyFlags, kWithoutReadBarrier>(offset);
+    ConcurrentCopyingVerifyNoFromSpaceRefsVisitor visitor(collector_);
+    visitor(ref);
+  }
+  void operator()(mirror::Class* klass, mirror::Reference* ref) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
+    CHECK(klass->IsTypeOfReferenceClass());
+    this->operator()(ref, mirror::Reference::ReferentOffset(), false);
+  }
+
+ private:
+  ConcurrentCopying* collector_;
+};
+
+class ConcurrentCopyingVerifyNoFromSpaceRefsObjectVisitor {
+ public:
+  explicit ConcurrentCopyingVerifyNoFromSpaceRefsObjectVisitor(ConcurrentCopying* collector)
+      : collector_(collector) {}
+  void operator()(mirror::Object* obj) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    ObjectCallback(obj, collector_);
+  }
+  static void ObjectCallback(mirror::Object* obj, void *arg)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    CHECK(obj != nullptr);
+    ConcurrentCopying* collector = reinterpret_cast<ConcurrentCopying*>(arg);
+    space::RegionSpace* region_space = collector->RegionSpace();
+    CHECK(!region_space->IsInFromSpace(obj)) << "Scanning object " << obj << " in from space";
+    ConcurrentCopyingVerifyNoFromSpaceRefsFieldVisitor visitor(collector);
+    obj->VisitReferences<true>(visitor, visitor);
+    if (kUseBakerReadBarrier) {
+      if (collector->RegionSpace()->IsInToSpace(obj)) {
+        CHECK(obj->GetReadBarrierPointer() == nullptr)
+            << "obj=" << obj << " non-white rb_ptr " << obj->GetReadBarrierPointer();
+      } else {
+        CHECK(obj->GetReadBarrierPointer() == ReadBarrier::BlackPtr() ||
+              (obj->GetReadBarrierPointer() == ReadBarrier::WhitePtr() &&
+               collector->IsOnAllocStack(obj)))
+            << "Non-moving space/unevac from space ref " << obj << " " << PrettyTypeOf(obj)
+            << " has non-black rb_ptr " << obj->GetReadBarrierPointer()
+            << " but isn't on the alloc stack (and has white rb_ptr). Is it in the non-moving space="
+            << (collector->GetHeap()->GetNonMovingSpace()->HasAddress(obj));
+      }
+    }
+  }
+
+ private:
+  ConcurrentCopying* const collector_;
+};
+
+// Verify there's no from-space references left after the marking phase.
+void ConcurrentCopying::VerifyNoFromSpaceReferences() {
+  Thread* self = Thread::Current();
+  DCHECK(Locks::mutator_lock_->IsExclusiveHeld(self));
+  ConcurrentCopyingVerifyNoFromSpaceRefsObjectVisitor visitor(this);
+  // Roots.
+  {
+    ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
+    Runtime::Current()->VisitRoots(
+        ConcurrentCopyingVerifyNoFromSpaceRefsVisitor::RootCallback, this);
+  }
+  // The to-space.
+  region_space_->WalkToSpace(ConcurrentCopyingVerifyNoFromSpaceRefsObjectVisitor::ObjectCallback,
+                             this);
+  // Non-moving spaces.
+  {
+    WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
+    heap_->GetMarkBitmap()->Visit(visitor);
+  }
+  // The alloc stack.
+  {
+    ConcurrentCopyingVerifyNoFromSpaceRefsVisitor ref_visitor(this);
+    for (mirror::Object** it = heap_->allocation_stack_->Begin(),
+             **end = heap_->allocation_stack_->End(); it < end; ++it) {
+      mirror::Object* obj = *it;
+      if (obj != nullptr && obj->GetClass() != nullptr) {
+        // TODO: need to call this only if obj is alive?
+        ref_visitor(obj);
+        visitor(obj);
+      }
+    }
+  }
+  // TODO: LOS. But only refs in LOS are classes.
+}
+
+// The following visitors are used to assert the to-space invariant.
+class ConcurrentCopyingAssertToSpaceInvariantRefsVisitor {
+ public:
+  explicit ConcurrentCopyingAssertToSpaceInvariantRefsVisitor(ConcurrentCopying* collector)
+      : collector_(collector) {}
+
+  void operator()(mirror::Object* ref) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
+    if (ref == nullptr) {
+      // OK.
+      return;
+    }
+    collector_->AssertToSpaceInvariant(nullptr, MemberOffset(0), ref);
+  }
+  static void RootCallback(mirror::Object** root, void *arg, const RootInfo& /*root_info*/)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    ConcurrentCopying* collector = reinterpret_cast<ConcurrentCopying*>(arg);
+    ConcurrentCopyingAssertToSpaceInvariantRefsVisitor visitor(collector);
+    DCHECK(root != nullptr);
+    visitor(*root);
+  }
+
+ private:
+  ConcurrentCopying* collector_;
+};
+
+class ConcurrentCopyingAssertToSpaceInvariantFieldVisitor {
+ public:
+  explicit ConcurrentCopyingAssertToSpaceInvariantFieldVisitor(ConcurrentCopying* collector)
+      : collector_(collector) {}
+
+  void operator()(mirror::Object* obj, MemberOffset offset, bool /* is_static */) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
+    mirror::Object* ref =
+        obj->GetFieldObject<mirror::Object, kDefaultVerifyFlags, kWithoutReadBarrier>(offset);
+    ConcurrentCopyingAssertToSpaceInvariantRefsVisitor visitor(collector_);
+    visitor(ref);
+  }
+  void operator()(mirror::Class* klass, mirror::Reference* /* ref */) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
+    CHECK(klass->IsTypeOfReferenceClass());
+  }
+
+ private:
+  ConcurrentCopying* collector_;
+};
+
+class ConcurrentCopyingAssertToSpaceInvariantObjectVisitor {
+ public:
+  explicit ConcurrentCopyingAssertToSpaceInvariantObjectVisitor(ConcurrentCopying* collector)
+      : collector_(collector) {}
+  void operator()(mirror::Object* obj) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    ObjectCallback(obj, collector_);
+  }
+  static void ObjectCallback(mirror::Object* obj, void *arg)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    CHECK(obj != nullptr);
+    ConcurrentCopying* collector = reinterpret_cast<ConcurrentCopying*>(arg);
+    space::RegionSpace* region_space = collector->RegionSpace();
+    CHECK(!region_space->IsInFromSpace(obj)) << "Scanning object " << obj << " in from space";
+    collector->AssertToSpaceInvariant(nullptr, MemberOffset(0), obj);
+    ConcurrentCopyingAssertToSpaceInvariantFieldVisitor visitor(collector);
+    obj->VisitReferences<true>(visitor, visitor);
+  }
+
+ private:
+  ConcurrentCopying* collector_;
+};
+
+bool ConcurrentCopying::ProcessMarkStack() {
+  if (kVerboseMode) {
+    LOG(INFO) << "ProcessMarkStack. ";
+  }
+  size_t count = 0;
+  mirror::Object* to_ref;
+  while ((to_ref = PopOffMarkStack()) != nullptr) {
+    ++count;
+    DCHECK(!region_space_->IsInFromSpace(to_ref));
+    if (kUseBakerReadBarrier) {
+      DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::GrayPtr())
+          << " " << to_ref << " " << to_ref->GetReadBarrierPointer()
+          << " is_marked=" << IsMarked(to_ref);
+    }
+    // Scan ref fields.
+    Scan(to_ref);
+    // Mark the gray ref as white or black.
+    if (kUseBakerReadBarrier) {
+      DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::GrayPtr())
+          << " " << to_ref << " " << to_ref->GetReadBarrierPointer()
+          << " is_marked=" << IsMarked(to_ref);
+    }
+    if (to_ref->GetClass<kVerifyNone, kWithoutReadBarrier>()->IsTypeOfReferenceClass() &&
+        to_ref->AsReference()->GetReferent<kWithoutReadBarrier>() != nullptr &&
+        !IsInToSpace(to_ref->AsReference()->GetReferent<kWithoutReadBarrier>())) {
+      // Leave References gray so that GetReferent() will trigger RB.
+      CHECK(to_ref->AsReference()->IsEnqueued()) << "Left unenqueued ref gray " << to_ref;
+    } else {
+      if (kUseBakerReadBarrier) {
+        if (region_space_->IsInToSpace(to_ref)) {
+          // If to-space, change from gray to white.
+          bool success = to_ref->AtomicSetReadBarrierPointer(ReadBarrier::GrayPtr(),
+                                                             ReadBarrier::WhitePtr());
+          CHECK(success) << "Must succeed as we won the race.";
+          CHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::WhitePtr());
+        } else {
+          // If non-moving space/unevac from space, change from gray
+          // to black. We can't change gray to white because it's not
+          // safe to use CAS if two threads change values in opposite
+          // directions (A->B and B->A). So, we change it to black to
+          // indicate non-moving objects that have been marked
+          // through. Note we'd need to change from black to white
+          // later (concurrently).
+          bool success = to_ref->AtomicSetReadBarrierPointer(ReadBarrier::GrayPtr(),
+                                                             ReadBarrier::BlackPtr());
+          CHECK(success) << "Must succeed as we won the race.";
+          CHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::BlackPtr());
+        }
+      }
+    }
+    if (ReadBarrier::kEnableToSpaceInvariantChecks || kIsDebugBuild) {
+      ConcurrentCopyingAssertToSpaceInvariantObjectVisitor visitor(this);
+      visitor(to_ref);
+    }
+  }
+  // Return true if the stack was empty.
+  return count == 0;
+}
+
+void ConcurrentCopying::CheckEmptyMarkQueue() {
+  if (!mark_queue_.IsEmpty()) {
+    while (!mark_queue_.IsEmpty()) {
+      mirror::Object* obj = mark_queue_.Dequeue();
+      if (kUseBakerReadBarrier) {
+        mirror::Object* rb_ptr = obj->GetReadBarrierPointer();
+        LOG(INFO) << "On mark queue : " << obj << " " << PrettyTypeOf(obj) << " rb_ptr=" << rb_ptr
+                  << " is_marked=" << IsMarked(obj);
+      } else {
+        LOG(INFO) << "On mark queue : " << obj << " " << PrettyTypeOf(obj)
+                  << " is_marked=" << IsMarked(obj);
+      }
+    }
+    LOG(FATAL) << "mark queue is not empty";
+  }
+}
+
+void ConcurrentCopying::SweepSystemWeaks(Thread* self) {
+  TimingLogger::ScopedTiming split("SweepSystemWeaks", GetTimings());
+  ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
+  Runtime::Current()->SweepSystemWeaks(IsMarkedCallback, this);
+}
+
+void ConcurrentCopying::Sweep(bool swap_bitmaps) {
+  {
+    TimingLogger::ScopedTiming t("MarkStackAsLive", GetTimings());
+    accounting::ObjectStack* live_stack = heap_->GetLiveStack();
+    if (kEnableFromSpaceAccountingCheck) {
+      CHECK_GE(live_stack_freeze_size_, live_stack->Size());
+    }
+    heap_->MarkAllocStackAsLive(live_stack);
+    live_stack->Reset();
+  }
+  CHECK(mark_queue_.IsEmpty());
+  TimingLogger::ScopedTiming split("Sweep", GetTimings());
+  for (const auto& space : GetHeap()->GetContinuousSpaces()) {
+    if (space->IsContinuousMemMapAllocSpace()) {
+      space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace();
+      if (space == region_space_ || immune_region_.ContainsSpace(space)) {
+        continue;
+      }
+      TimingLogger::ScopedTiming split2(
+          alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepAllocSpace", GetTimings());
+      RecordFree(alloc_space->Sweep(swap_bitmaps));
+    }
+  }
+  SweepLargeObjects(swap_bitmaps);
+}
+
+void ConcurrentCopying::SweepLargeObjects(bool swap_bitmaps) {
+  TimingLogger::ScopedTiming split("SweepLargeObjects", GetTimings());
+  RecordFreeLOS(heap_->GetLargeObjectsSpace()->Sweep(swap_bitmaps));
+}
+
+class ConcurrentCopyingClearBlackPtrsVisitor {
+ public:
+  explicit ConcurrentCopyingClearBlackPtrsVisitor(ConcurrentCopying* cc)
+      : collector_(cc) {}
+  void operator()(mirror::Object* obj) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
+    DCHECK(obj != nullptr);
+    CHECK(collector_->heap_->GetMarkBitmap()->Test(obj)) << obj;
+    CHECK_EQ(obj->GetReadBarrierPointer(), ReadBarrier::BlackPtr()) << obj;
+    obj->SetReadBarrierPointer(ReadBarrier::WhitePtr());
+    CHECK_EQ(obj->GetReadBarrierPointer(), ReadBarrier::WhitePtr()) << obj;
+  }
+
+ private:
+  ConcurrentCopying* const collector_;
+};
+
+// Clear the black ptrs in non-moving objects back to white.
+void ConcurrentCopying::ClearBlackPtrs() {
+  CHECK(kUseBakerReadBarrier);
+  TimingLogger::ScopedTiming split("ClearBlackPtrs", GetTimings());
+  ConcurrentCopyingClearBlackPtrsVisitor visitor(this);
+  for (auto& space : heap_->GetContinuousSpaces()) {
+    if (space == region_space_) {
+      continue;
+    }
+    accounting::ContinuousSpaceBitmap* mark_bitmap = space->GetMarkBitmap();
+    if (kVerboseMode) {
+      LOG(INFO) << "ClearBlackPtrs: " << *space << " bitmap: " << *mark_bitmap;
+    }
+    mark_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
+                                  reinterpret_cast<uintptr_t>(space->Limit()),
+                                  visitor);
+  }
+  space::LargeObjectSpace* large_object_space = heap_->GetLargeObjectsSpace();
+  large_object_space->GetMarkBitmap()->VisitMarkedRange(
+      reinterpret_cast<uintptr_t>(large_object_space->Begin()),
+      reinterpret_cast<uintptr_t>(large_object_space->End()),
+      visitor);
+  // Objects on the allocation stack?
+  if (ReadBarrier::kEnableReadBarrierInvariantChecks || kIsDebugBuild) {
+    size_t count = GetAllocationStack()->Size();
+    mirror::Object** it = GetAllocationStack()->Begin();
+    mirror::Object** end = GetAllocationStack()->End();
+    for (size_t i = 0; i < count; ++i, ++it) {
+      CHECK(it < end);
+      mirror::Object* obj = *it;
+      if (obj != nullptr) {
+        // Must have been cleared above.
+        CHECK(obj->GetReadBarrierPointer() == ReadBarrier::WhitePtr()) << obj;
+      }
+    }
+  }
+}
+
+void ConcurrentCopying::ReclaimPhase() {
+  TimingLogger::ScopedTiming split("ReclaimPhase", GetTimings());
+  if (kVerboseMode) {
+    LOG(INFO) << "GC ReclaimPhase";
+  }
+  Thread* self = Thread::Current();
+
+  {
+    // Double-check that the mark stack is empty.
+    // Note: need to set this after VerifyNoFromSpaceRef().
+    is_asserting_to_space_invariant_ = false;
+    QuasiAtomic::ThreadFenceForConstructor();
+    if (kVerboseMode) {
+      LOG(INFO) << "Issue an empty check point. ";
+    }
+    IssueEmptyCheckpoint();
+    // Disable the check.
+    is_mark_queue_push_disallowed_.StoreSequentiallyConsistent(0);
+    CheckEmptyMarkQueue();
+  }
+
+  {
+    // Record freed objects.
+    TimingLogger::ScopedTiming split2("RecordFree", GetTimings());
+    // Don't include thread-locals that are in the to-space.
+    uint64_t from_bytes = region_space_->GetBytesAllocatedInFromSpace();
+    uint64_t from_objects = region_space_->GetObjectsAllocatedInFromSpace();
+    uint64_t unevac_from_bytes = region_space_->GetBytesAllocatedInUnevacFromSpace();
+    uint64_t unevac_from_objects = region_space_->GetObjectsAllocatedInUnevacFromSpace();
+    uint64_t to_bytes = bytes_moved_.LoadSequentiallyConsistent();
+    uint64_t to_objects = objects_moved_.LoadSequentiallyConsistent();
+    if (kEnableFromSpaceAccountingCheck) {
+      CHECK_EQ(from_space_num_objects_at_first_pause_, from_objects + unevac_from_objects);
+      CHECK_EQ(from_space_num_bytes_at_first_pause_, from_bytes + unevac_from_bytes);
+    }
+    CHECK_LE(to_objects, from_objects);
+    CHECK_LE(to_bytes, from_bytes);
+    int64_t freed_bytes = from_bytes - to_bytes;
+    int64_t freed_objects = from_objects - to_objects;
+    if (kVerboseMode) {
+      LOG(INFO) << "RecordFree:"
+                << " from_bytes=" << from_bytes << " from_objects=" << from_objects
+                << " unevac_from_bytes=" << unevac_from_bytes << " unevac_from_objects=" << unevac_from_objects
+                << " to_bytes=" << to_bytes << " to_objects=" << to_objects
+                << " freed_bytes=" << freed_bytes << " freed_objects=" << freed_objects
+                << " from_space size=" << region_space_->FromSpaceSize()
+                << " unevac_from_space size=" << region_space_->UnevacFromSpaceSize()
+                << " to_space size=" << region_space_->ToSpaceSize();
+      LOG(INFO) << "(before) num_bytes_allocated=" << heap_->num_bytes_allocated_.LoadSequentiallyConsistent();
+    }
+    RecordFree(ObjectBytePair(freed_objects, freed_bytes));
+    if (kVerboseMode) {
+      LOG(INFO) << "(after) num_bytes_allocated=" << heap_->num_bytes_allocated_.LoadSequentiallyConsistent();
+    }
+  }
+
+  {
+    TimingLogger::ScopedTiming split3("ComputeUnevacFromSpaceLiveRatio", GetTimings());
+    ComputeUnevacFromSpaceLiveRatio();
+  }
+
+  {
+    TimingLogger::ScopedTiming split4("ClearFromSpace", GetTimings());
+    region_space_->ClearFromSpace();
+  }
+
+  {
+    WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
+    if (kUseBakerReadBarrier) {
+      ClearBlackPtrs();
+    }
+    Sweep(false);
+    SwapBitmaps();
+    heap_->UnBindBitmaps();
+
+    // Remove bitmaps for the immune spaces.
+    while (!cc_bitmaps_.empty()) {
+      accounting::ContinuousSpaceBitmap* cc_bitmap = cc_bitmaps_.back();
+      cc_heap_bitmap_->RemoveContinuousSpaceBitmap(cc_bitmap);
+      delete cc_bitmap;
+      cc_bitmaps_.pop_back();
+    }
+    region_space_bitmap_ = nullptr;
+  }
+
+  if (kVerboseMode) {
+    LOG(INFO) << "GC end of ReclaimPhase";
+  }
+}
+
+class ConcurrentCopyingComputeUnevacFromSpaceLiveRatioVisitor {
+ public:
+  explicit ConcurrentCopyingComputeUnevacFromSpaceLiveRatioVisitor(ConcurrentCopying* cc)
+      : collector_(cc) {}
+  void operator()(mirror::Object* ref) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
+    DCHECK(ref != nullptr);
+    CHECK(collector_->region_space_bitmap_->Test(ref)) << ref;
+    CHECK(collector_->region_space_->IsInUnevacFromSpace(ref)) << ref;
+    if (kUseBakerReadBarrier) {
+      CHECK(ref->GetReadBarrierPointer() == ReadBarrier::BlackPtr()) << ref;
+      // Clear the black ptr.
+      ref->SetReadBarrierPointer(ReadBarrier::WhitePtr());
+    }
+    size_t obj_size = ref->SizeOf();
+    size_t alloc_size = RoundUp(obj_size, space::RegionSpace::kAlignment);
+    collector_->region_space_->AddLiveBytes(ref, alloc_size);
+  }
+
+ private:
+  ConcurrentCopying* collector_;
+};
+
+// Compute how much live objects are left in regions.
+void ConcurrentCopying::ComputeUnevacFromSpaceLiveRatio() {
+  region_space_->AssertAllRegionLiveBytesZeroOrCleared();
+  ConcurrentCopyingComputeUnevacFromSpaceLiveRatioVisitor visitor(this);
+  region_space_bitmap_->VisitMarkedRange(reinterpret_cast<uintptr_t>(region_space_->Begin()),
+                                         reinterpret_cast<uintptr_t>(region_space_->Limit()),
+                                         visitor);
+}
+
+// Assert the to-space invariant.
+void ConcurrentCopying::AssertToSpaceInvariant(mirror::Object* obj, MemberOffset offset,
+                                               mirror::Object* ref) {
+  CHECK(heap_->collector_type_ == kCollectorTypeCC) << static_cast<size_t>(heap_->collector_type_);
+  if (is_asserting_to_space_invariant_) {
+    if (region_space_->IsInToSpace(ref)) {
+      // OK.
+      return;
+    } else if (region_space_->IsInUnevacFromSpace(ref)) {
+      CHECK(region_space_bitmap_->Test(ref)) << ref;
+    } else if (region_space_->IsInFromSpace(ref)) {
+      // Not OK. Do extra logging.
+      if (obj != nullptr) {
+        if (kUseBakerReadBarrier) {
+          LOG(INFO) << "holder=" << obj << " " << PrettyTypeOf(obj)
+                    << " holder rb_ptr=" << obj->GetReadBarrierPointer();
+        } else {
+          LOG(INFO) << "holder=" << obj << " " << PrettyTypeOf(obj);
+        }
+        if (region_space_->IsInFromSpace(obj)) {
+          LOG(INFO) << "holder is in the from-space.";
+        } else if (region_space_->IsInToSpace(obj)) {
+          LOG(INFO) << "holder is in the to-space.";
+        } else if (region_space_->IsInUnevacFromSpace(obj)) {
+          LOG(INFO) << "holder is in the unevac from-space.";
+          if (region_space_bitmap_->Test(obj)) {
+            LOG(INFO) << "holder is marked in the region space bitmap.";
+          } else {
+            LOG(INFO) << "holder is not marked in the region space bitmap.";
+          }
+        } else {
+          // In a non-moving space.
+          if (immune_region_.ContainsObject(obj)) {
+            LOG(INFO) << "holder is in the image or the zygote space.";
+            accounting::ContinuousSpaceBitmap* cc_bitmap =
+                cc_heap_bitmap_->GetContinuousSpaceBitmap(obj);
+            CHECK(cc_bitmap != nullptr)
+                << "An immune space object must have a bitmap.";
+            if (cc_bitmap->Test(obj)) {
+              LOG(INFO) << "holder is marked in the bit map.";
+            } else {
+              LOG(INFO) << "holder is NOT marked in the bit map.";
+            }
+          } else {
+            LOG(INFO) << "holder is in a non-moving (or main) space.";
+            accounting::ContinuousSpaceBitmap* mark_bitmap =
+                heap_mark_bitmap_->GetContinuousSpaceBitmap(obj);
+            accounting::LargeObjectBitmap* los_bitmap =
+                heap_mark_bitmap_->GetLargeObjectBitmap(obj);
+            CHECK(los_bitmap != nullptr) << "LOS bitmap covers the entire address range";
+            bool is_los = mark_bitmap == nullptr;
+            if (!is_los && mark_bitmap->Test(obj)) {
+              LOG(INFO) << "holder is marked in the mark bit map.";
+            } else if (is_los && los_bitmap->Test(obj)) {
+              LOG(INFO) << "holder is marked in the los bit map.";
+            } else {
+              // If ref is on the allocation stack, then it is considered
+              // mark/alive (but not necessarily on the live stack.)
+              if (IsOnAllocStack(obj)) {
+                LOG(INFO) << "holder is on the alloc stack.";
+              } else {
+                LOG(INFO) << "holder is not marked or on the alloc stack.";
+              }
+            }
+          }
+        }
+        LOG(INFO) << "offset=" << offset.SizeValue();
+      }
+      CHECK(false) << "Found from-space ref " << ref << " " << PrettyTypeOf(ref);
+    } else {
+      // In a non-moving spaces. Check that the ref is marked.
+      if (immune_region_.ContainsObject(ref)) {
+        accounting::ContinuousSpaceBitmap* cc_bitmap =
+            cc_heap_bitmap_->GetContinuousSpaceBitmap(ref);
+        CHECK(cc_bitmap != nullptr)
+            << "An immune space ref must have a bitmap. " << ref;
+        if (kUseBakerReadBarrier) {
+          CHECK(cc_bitmap->Test(ref))
+              << "Unmarked immune space ref. obj=" << obj << " rb_ptr="
+              << obj->GetReadBarrierPointer() << " ref=" << ref;
+        } else {
+          CHECK(cc_bitmap->Test(ref))
+              << "Unmarked immune space ref. obj=" << obj << " ref=" << ref;
+        }
+      } else {
+        accounting::ContinuousSpaceBitmap* mark_bitmap =
+            heap_mark_bitmap_->GetContinuousSpaceBitmap(ref);
+        accounting::LargeObjectBitmap* los_bitmap =
+            heap_mark_bitmap_->GetLargeObjectBitmap(ref);
+        CHECK(los_bitmap != nullptr) << "LOS bitmap covers the entire address range";
+        bool is_los = mark_bitmap == nullptr;
+        if ((!is_los && mark_bitmap->Test(ref)) ||
+            (is_los && los_bitmap->Test(ref))) {
+          // OK.
+        } else {
+          // If ref is on the allocation stack, then it may not be
+          // marked live, but considered marked/alive (but not
+          // necessarily on the live stack).
+          CHECK(IsOnAllocStack(ref)) << "Unmarked ref that's not on the allocation stack. "
+                                     << "obj=" << obj << " ref=" << ref;
+        }
+      }
+    }
+  }
+}
+
+void ConcurrentCopying::ProcessRootCallback(mirror::Object** root, void* arg,
+                                            const RootInfo& /*root_info*/) {
+  reinterpret_cast<ConcurrentCopying*>(arg)->Process(root);
+}
+
+// Used to scan ref fields of an object.
+class ConcurrentCopyingRefFieldsVisitor {
+ public:
+  explicit ConcurrentCopyingRefFieldsVisitor(ConcurrentCopying* collector)
+      : collector_(collector) {}
+
+  void operator()(mirror::Object* obj, MemberOffset offset, bool /* is_static */)
+      const ALWAYS_INLINE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
+    collector_->Process(obj, offset);
+  }
+
+  void operator()(mirror::Class* klass, mirror::Reference* ref) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
+    CHECK(klass->IsTypeOfReferenceClass());
+    collector_->DelayReferenceReferent(klass, ref);
+  }
+
+ private:
+  ConcurrentCopying* const collector_;
+};
+
+// Scan ref fields of an object.
+void ConcurrentCopying::Scan(mirror::Object* to_ref) {
+  DCHECK(!region_space_->IsInFromSpace(to_ref));
+  ConcurrentCopyingRefFieldsVisitor visitor(this);
+  to_ref->VisitReferences<true>(visitor, visitor);
+}
+
+// Process a field.
+inline void ConcurrentCopying::Process(mirror::Object* obj, MemberOffset offset) {
+  mirror::Object* ref = obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier, false>(offset);
+  if (ref == nullptr || region_space_->IsInToSpace(ref)) {
+    return;
+  }
+  mirror::Object* to_ref = Mark(ref);
+  if (to_ref == ref) {
+    return;
+  }
+  // This may fail if the mutator writes to the field at the same time. But it's ok.
+  mirror::Object* expected_ref = ref;
+  mirror::Object* new_ref = to_ref;
+  do {
+    if (expected_ref !=
+        obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier, false>(offset)) {
+      // It was updated by the mutator.
+      break;
+    }
+  } while (!obj->CasFieldWeakSequentiallyConsistentObjectWithoutWriteBarrier<false, false, kVerifyNone>(
+      offset, expected_ref, new_ref));
+}
+
+// Process a root.
+void ConcurrentCopying::Process(mirror::Object** root) {
+  mirror::Object* ref = *root;
+  if (ref == nullptr || region_space_->IsInToSpace(ref)) {
+    return;
+  }
+  mirror::Object* to_ref = Mark(ref);
+  if (to_ref == ref) {
+    return;
+  }
+  Atomic<mirror::Object*>* addr = reinterpret_cast<Atomic<mirror::Object*>*>(root);
+  mirror::Object* expected_ref = ref;
+  mirror::Object* new_ref = to_ref;
+  do {
+    if (expected_ref != addr->LoadRelaxed()) {
+      // It was updated by the mutator.
+      break;
+    }
+  } while (!addr->CompareExchangeWeakSequentiallyConsistent(expected_ref, new_ref));
+}
+
+// Fill the given memory block with a dummy object. Used to fill in a
+// copy of objects that was lost in race.
+void ConcurrentCopying::FillWithDummyObject(mirror::Object* dummy_obj, size_t byte_size) {
+  CHECK(IsAligned<kObjectAlignment>(byte_size));
+  memset(dummy_obj, 0, byte_size);
+  mirror::Class* int_array_class = mirror::IntArray::GetArrayClass();
+  CHECK(int_array_class != nullptr);
+  AssertToSpaceInvariant(nullptr, MemberOffset(0), int_array_class);
+  size_t component_size = int_array_class->GetComponentSize();
+  CHECK_EQ(component_size, sizeof(int32_t));
+  size_t data_offset = mirror::Array::DataOffset(component_size).SizeValue();
+  if (data_offset > byte_size) {
+    // An int array is too big. Use java.lang.Object.
+    mirror::Class* java_lang_Object = WellKnownClasses::ToClass(WellKnownClasses::java_lang_Object);
+    AssertToSpaceInvariant(nullptr, MemberOffset(0), java_lang_Object);
+    CHECK_EQ(byte_size, java_lang_Object->GetObjectSize());
+    dummy_obj->SetClass(java_lang_Object);
+    CHECK_EQ(byte_size, dummy_obj->SizeOf());
+  } else {
+    // Use an int array.
+    dummy_obj->SetClass(int_array_class);
+    CHECK(dummy_obj->IsArrayInstance());
+    int32_t length = (byte_size - data_offset) / component_size;
+    dummy_obj->AsArray()->SetLength(length);
+    CHECK_EQ(dummy_obj->AsArray()->GetLength(), length)
+        << "byte_size=" << byte_size << " length=" << length
+        << " component_size=" << component_size << " data_offset=" << data_offset;
+    CHECK_EQ(byte_size, dummy_obj->SizeOf())
+        << "byte_size=" << byte_size << " length=" << length
+        << " component_size=" << component_size << " data_offset=" << data_offset;
+  }
+}
+
+// Reuse the memory blocks that were copy of objects that were lost in race.
+mirror::Object* ConcurrentCopying::AllocateInSkippedBlock(size_t alloc_size) {
+  // Try to reuse the blocks that were unused due to CAS failures.
+  CHECK(IsAligned<space::RegionSpace::kAlignment>(alloc_size));
+  Thread* self = Thread::Current();
+  size_t min_object_size = RoundUp(sizeof(mirror::Object), space::RegionSpace::kAlignment);
+  MutexLock mu(self, skipped_blocks_lock_);
+  auto it = skipped_blocks_map_.lower_bound(alloc_size);
+  if (it == skipped_blocks_map_.end()) {
+    // Not found.
+    return nullptr;
+  }
+  {
+    size_t byte_size = it->first;
+    CHECK_GE(byte_size, alloc_size);
+    if (byte_size > alloc_size && byte_size - alloc_size < min_object_size) {
+      // If remainder would be too small for a dummy object, retry with a larger request size.
+      it = skipped_blocks_map_.lower_bound(alloc_size + min_object_size);
+      if (it == skipped_blocks_map_.end()) {
+        // Not found.
+        return nullptr;
+      }
+      CHECK(IsAligned<space::RegionSpace::kAlignment>(it->first - alloc_size));
+      CHECK_GE(it->first - alloc_size, min_object_size)
+          << "byte_size=" << byte_size << " it->first=" << it->first << " alloc_size=" << alloc_size;
+    }
+  }
+  // Found a block.
+  CHECK(it != skipped_blocks_map_.end());
+  size_t byte_size = it->first;
+  uint8_t* addr = it->second;
+  CHECK_GE(byte_size, alloc_size);
+  CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr)));
+  CHECK(IsAligned<space::RegionSpace::kAlignment>(byte_size));
+  if (kVerboseMode) {
+    LOG(INFO) << "Reusing skipped bytes : " << reinterpret_cast<void*>(addr) << ", " << byte_size;
+  }
+  skipped_blocks_map_.erase(it);
+  memset(addr, 0, byte_size);
+  if (byte_size > alloc_size) {
+    // Return the remainder to the map.
+    CHECK(IsAligned<space::RegionSpace::kAlignment>(byte_size - alloc_size));
+    CHECK_GE(byte_size - alloc_size, min_object_size);
+    FillWithDummyObject(reinterpret_cast<mirror::Object*>(addr + alloc_size),
+                        byte_size - alloc_size);
+    CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr + alloc_size)));
+    skipped_blocks_map_.insert(std::make_pair(byte_size - alloc_size, addr + alloc_size));
+  }
+  return reinterpret_cast<mirror::Object*>(addr);
+}
+
+mirror::Object* ConcurrentCopying::Copy(mirror::Object* from_ref) {
+  DCHECK(region_space_->IsInFromSpace(from_ref));
+  // No read barrier to avoid nested RB that might violate the to-space
+  // invariant. Note that from_ref is a from space ref so the SizeOf()
+  // call will access the from-space meta objects, but it's ok and necessary.
+  size_t obj_size = from_ref->SizeOf<kDefaultVerifyFlags, kWithoutReadBarrier>();
+  size_t region_space_alloc_size = RoundUp(obj_size, space::RegionSpace::kAlignment);
+  size_t region_space_bytes_allocated = 0U;
+  size_t non_moving_space_bytes_allocated = 0U;
+  size_t bytes_allocated = 0U;
+  mirror::Object* to_ref = region_space_->AllocNonvirtual<true>(
+      region_space_alloc_size, &region_space_bytes_allocated, nullptr);
+  bytes_allocated = region_space_bytes_allocated;
+  if (to_ref != nullptr) {
+    DCHECK_EQ(region_space_alloc_size, region_space_bytes_allocated);
+  }
+  bool fall_back_to_non_moving = false;
+  if (UNLIKELY(to_ref == nullptr)) {
+    // Failed to allocate in the region space. Try the skipped blocks.
+    to_ref = AllocateInSkippedBlock(region_space_alloc_size);
+    if (to_ref != nullptr) {
+      // Succeeded to allocate in a skipped block.
+      if (heap_->use_tlab_) {
+        // This is necessary for the tlab case as it's not accounted in the space.
+        region_space_->RecordAlloc(to_ref);
+      }
+      bytes_allocated = region_space_alloc_size;
+    } else {
+      // Fall back to the non-moving space.
+      fall_back_to_non_moving = true;
+      if (kVerboseMode) {
+        LOG(INFO) << "Out of memory in the to-space. Fall back to non-moving. skipped_bytes="
+                  << to_space_bytes_skipped_.LoadSequentiallyConsistent()
+                  << " skipped_objects=" << to_space_objects_skipped_.LoadSequentiallyConsistent();
+      }
+      fall_back_to_non_moving = true;
+      to_ref = heap_->non_moving_space_->Alloc(Thread::Current(), obj_size,
+                                               &non_moving_space_bytes_allocated, nullptr);
+      CHECK(to_ref != nullptr) << "Fall-back non-moving space allocation failed";
+      bytes_allocated = non_moving_space_bytes_allocated;
+      // Mark it in the mark bitmap.
+      accounting::ContinuousSpaceBitmap* mark_bitmap =
+          heap_mark_bitmap_->GetContinuousSpaceBitmap(to_ref);
+      CHECK(mark_bitmap != nullptr);
+      CHECK(!mark_bitmap->AtomicTestAndSet(to_ref));
+    }
+  }
+  DCHECK(to_ref != nullptr);
+
+  // Attempt to install the forward pointer. This is in a loop as the
+  // lock word atomic write can fail.
+  while (true) {
+    // Copy the object. TODO: copy only the lockword in the second iteration and on?
+    memcpy(to_ref, from_ref, obj_size);
+    // Set the gray ptr.
+    if (kUseBakerReadBarrier) {
+      to_ref->SetReadBarrierPointer(ReadBarrier::GrayPtr());
+    }
+
+    LockWord old_lock_word = to_ref->GetLockWord(false);
+
+    if (old_lock_word.GetState() == LockWord::kForwardingAddress) {
+      // Lost the race. Another thread (either GC or mutator) stored
+      // the forwarding pointer first. Make the lost copy (to_ref)
+      // look like a valid but dead (dummy) object and keep it for
+      // future reuse.
+      FillWithDummyObject(to_ref, bytes_allocated);
+      if (!fall_back_to_non_moving) {
+        DCHECK(region_space_->IsInToSpace(to_ref));
+        if (bytes_allocated > space::RegionSpace::kRegionSize) {
+          // Free the large alloc.
+          region_space_->FreeLarge(to_ref, bytes_allocated);
+        } else {
+          // Record the lost copy for later reuse.
+          heap_->num_bytes_allocated_.FetchAndAddSequentiallyConsistent(bytes_allocated);
+          to_space_bytes_skipped_.FetchAndAddSequentiallyConsistent(bytes_allocated);
+          to_space_objects_skipped_.FetchAndAddSequentiallyConsistent(1);
+          MutexLock mu(Thread::Current(), skipped_blocks_lock_);
+          skipped_blocks_map_.insert(std::make_pair(bytes_allocated,
+                                                    reinterpret_cast<uint8_t*>(to_ref)));
+        }
+      } else {
+        DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
+        DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated);
+        // Free the non-moving-space chunk.
+        accounting::ContinuousSpaceBitmap* mark_bitmap =
+            heap_mark_bitmap_->GetContinuousSpaceBitmap(to_ref);
+        CHECK(mark_bitmap != nullptr);
+        CHECK(mark_bitmap->Clear(to_ref));
+        heap_->non_moving_space_->Free(Thread::Current(), to_ref);
+      }
+
+      // Get the winner's forward ptr.
+      mirror::Object* lost_fwd_ptr = to_ref;
+      to_ref = reinterpret_cast<mirror::Object*>(old_lock_word.ForwardingAddress());
+      CHECK(to_ref != nullptr);
+      CHECK_NE(to_ref, lost_fwd_ptr);
+      CHECK(region_space_->IsInToSpace(to_ref) || heap_->non_moving_space_->HasAddress(to_ref));
+      CHECK_NE(to_ref->GetLockWord(false).GetState(), LockWord::kForwardingAddress);
+      return to_ref;
+    }
+
+    LockWord new_lock_word = LockWord::FromForwardingAddress(reinterpret_cast<size_t>(to_ref));
+
+    // Try to atomically write the fwd ptr.
+    bool success = from_ref->CasLockWordWeakSequentiallyConsistent(old_lock_word, new_lock_word);
+    if (LIKELY(success)) {
+      // The CAS succeeded.
+      objects_moved_.FetchAndAddSequentiallyConsistent(1);
+      bytes_moved_.FetchAndAddSequentiallyConsistent(region_space_alloc_size);
+      if (LIKELY(!fall_back_to_non_moving)) {
+        DCHECK(region_space_->IsInToSpace(to_ref));
+      } else {
+        DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
+        DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated);
+      }
+      if (kUseBakerReadBarrier) {
+        DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::GrayPtr());
+      }
+      DCHECK(GetFwdPtr(from_ref) == to_ref);
+      CHECK_NE(to_ref->GetLockWord(false).GetState(), LockWord::kForwardingAddress);
+      PushOntoMarkStack<true>(to_ref);
+      return to_ref;
+    } else {
+      // The CAS failed. It may have lost the race or may have failed
+      // due to monitor/hashcode ops. Either way, retry.
+    }
+  }
+}
+
+mirror::Object* ConcurrentCopying::IsMarked(mirror::Object* from_ref) {
+  DCHECK(from_ref != nullptr);
+  if (region_space_->IsInToSpace(from_ref)) {
+    // It's already marked.
+    return from_ref;
+  }
+  mirror::Object* to_ref;
+  if (region_space_->IsInFromSpace(from_ref)) {
+    to_ref = GetFwdPtr(from_ref);
+    DCHECK(to_ref == nullptr || region_space_->IsInToSpace(to_ref) ||
+           heap_->non_moving_space_->HasAddress(to_ref))
+        << "from_ref=" << from_ref << " to_ref=" << to_ref;
+  } else if (region_space_->IsInUnevacFromSpace(from_ref)) {
+    if (region_space_bitmap_->Test(from_ref)) {
+      to_ref = from_ref;
+    } else {
+      to_ref = nullptr;
+    }
+  } else {
+    // from_ref is in a non-moving space.
+    if (immune_region_.ContainsObject(from_ref)) {
+      accounting::ContinuousSpaceBitmap* cc_bitmap =
+          cc_heap_bitmap_->GetContinuousSpaceBitmap(from_ref);
+      DCHECK(cc_bitmap != nullptr)
+          << "An immune space object must have a bitmap";
+      if (kIsDebugBuild) {
+        DCHECK(heap_mark_bitmap_->GetContinuousSpaceBitmap(from_ref)->Test(from_ref))
+            << "Immune space object must be already marked";
+      }
+      if (cc_bitmap->Test(from_ref)) {
+        // Already marked.
+        to_ref = from_ref;
+      } else {
+        // Newly marked.
+        to_ref = nullptr;
+      }
+    } else {
+      // Non-immune non-moving space. Use the mark bitmap.
+      accounting::ContinuousSpaceBitmap* mark_bitmap =
+          heap_mark_bitmap_->GetContinuousSpaceBitmap(from_ref);
+      accounting::LargeObjectBitmap* los_bitmap =
+          heap_mark_bitmap_->GetLargeObjectBitmap(from_ref);
+      CHECK(los_bitmap != nullptr) << "LOS bitmap covers the entire address range";
+      bool is_los = mark_bitmap == nullptr;
+      if (!is_los && mark_bitmap->Test(from_ref)) {
+        // Already marked.
+        to_ref = from_ref;
+      } else if (is_los && los_bitmap->Test(from_ref)) {
+        // Already marked in LOS.
+        to_ref = from_ref;
+      } else {
+        // Not marked.
+        if (IsOnAllocStack(from_ref)) {
+          // If on the allocation stack, it's considered marked.
+          to_ref = from_ref;
+        } else {
+          // Not marked.
+          to_ref = nullptr;
+        }
+      }
+    }
+  }
+  return to_ref;
+}
+
+bool ConcurrentCopying::IsOnAllocStack(mirror::Object* ref) {
+  QuasiAtomic::ThreadFenceAcquire();
+  accounting::ObjectStack* alloc_stack = GetAllocationStack();
+  mirror::Object** begin = alloc_stack->Begin();
+  // Important to read end once as it could be concurrently updated and screw up std::find().
+  mirror::Object** end = alloc_stack->End();
+  return std::find(begin, end, ref) != end;
+}
+
+mirror::Object* ConcurrentCopying::Mark(mirror::Object* from_ref) {
+  if (from_ref == nullptr) {
+    return nullptr;
+  }
+  DCHECK(from_ref != nullptr);
+  DCHECK(heap_->collector_type_ == kCollectorTypeCC);
+  if (region_space_->IsInToSpace(from_ref)) {
+    // It's already marked.
+    return from_ref;
+  }
+  mirror::Object* to_ref;
+  if (region_space_->IsInFromSpace(from_ref)) {
+    to_ref = GetFwdPtr(from_ref);
+    if (kUseBakerReadBarrier) {
+      DCHECK(to_ref != ReadBarrier::GrayPtr()) << "from_ref=" << from_ref << " to_ref=" << to_ref;
+    }
+    if (to_ref == nullptr) {
+      // It isn't marked yet. Mark it by copying it to the to-space.
+      to_ref = Copy(from_ref);
+    }
+    DCHECK(region_space_->IsInToSpace(to_ref) || heap_->non_moving_space_->HasAddress(to_ref))
+        << "from_ref=" << from_ref << " to_ref=" << to_ref;
+  } else if (region_space_->IsInUnevacFromSpace(from_ref)) {
+    // This may or may not succeed, which is ok.
+    if (kUseBakerReadBarrier) {
+      from_ref->AtomicSetReadBarrierPointer(ReadBarrier::WhitePtr(), ReadBarrier::GrayPtr());
+    }
+    if (region_space_bitmap_->AtomicTestAndSet(from_ref)) {
+      // Already marked.
+      to_ref = from_ref;
+    } else {
+      // Newly marked.
+      to_ref = from_ref;
+      if (kUseBakerReadBarrier) {
+        DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::GrayPtr());
+      }
+      PushOntoMarkStack<true>(to_ref);
+    }
+  } else {
+    // from_ref is in a non-moving space.
+    DCHECK(!region_space_->HasAddress(from_ref)) << from_ref;
+    if (immune_region_.ContainsObject(from_ref)) {
+      accounting::ContinuousSpaceBitmap* cc_bitmap =
+          cc_heap_bitmap_->GetContinuousSpaceBitmap(from_ref);
+      DCHECK(cc_bitmap != nullptr)
+          << "An immune space object must have a bitmap";
+      if (kIsDebugBuild) {
+        DCHECK(heap_mark_bitmap_->GetContinuousSpaceBitmap(from_ref)->Test(from_ref))
+            << "Immune space object must be already marked";
+      }
+      // This may or may not succeed, which is ok.
+      if (kUseBakerReadBarrier) {
+        from_ref->AtomicSetReadBarrierPointer(ReadBarrier::WhitePtr(), ReadBarrier::GrayPtr());
+      }
+      if (cc_bitmap->AtomicTestAndSet(from_ref)) {
+        // Already marked.
+        to_ref = from_ref;
+      } else {
+        // Newly marked.
+        to_ref = from_ref;
+        if (kUseBakerReadBarrier) {
+          DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::GrayPtr());
+        }
+        PushOntoMarkStack<true>(to_ref);
+      }
+    } else {
+      // Use the mark bitmap.
+      accounting::ContinuousSpaceBitmap* mark_bitmap =
+          heap_mark_bitmap_->GetContinuousSpaceBitmap(from_ref);
+      accounting::LargeObjectBitmap* los_bitmap =
+          heap_mark_bitmap_->GetLargeObjectBitmap(from_ref);
+      CHECK(los_bitmap != nullptr) << "LOS bitmap covers the entire address range";
+      bool is_los = mark_bitmap == nullptr;
+      if (!is_los && mark_bitmap->Test(from_ref)) {
+        // Already marked.
+        to_ref = from_ref;
+        if (kUseBakerReadBarrier) {
+          DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::GrayPtr() ||
+                 to_ref->GetReadBarrierPointer() == ReadBarrier::BlackPtr());
+        }
+      } else if (is_los && los_bitmap->Test(from_ref)) {
+        // Already marked in LOS.
+        to_ref = from_ref;
+        if (kUseBakerReadBarrier) {
+          DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::GrayPtr() ||
+                 to_ref->GetReadBarrierPointer() == ReadBarrier::BlackPtr());
+        }
+      } else {
+        // Not marked.
+        if (IsOnAllocStack(from_ref)) {
+          // If it's on the allocation stack, it's considered marked. Keep it white.
+          to_ref = from_ref;
+          // Objects on the allocation stack need not be marked.
+          if (!is_los) {
+            DCHECK(!mark_bitmap->Test(to_ref));
+          } else {
+            DCHECK(!los_bitmap->Test(to_ref));
+          }
+          if (kUseBakerReadBarrier) {
+            DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::WhitePtr());
+          }
+        } else {
+          // Not marked or on the allocation stack. Try to mark it.
+          // This may or may not succeed, which is ok.
+          if (kUseBakerReadBarrier) {
+            from_ref->AtomicSetReadBarrierPointer(ReadBarrier::WhitePtr(), ReadBarrier::GrayPtr());
+          }
+          if (!is_los && mark_bitmap->AtomicTestAndSet(from_ref)) {
+            // Already marked.
+            to_ref = from_ref;
+          } else if (is_los && los_bitmap->AtomicTestAndSet(from_ref)) {
+            // Already marked in LOS.
+            to_ref = from_ref;
+          } else {
+            // Newly marked.
+            to_ref = from_ref;
+            if (kUseBakerReadBarrier) {
+              DCHECK(to_ref->GetReadBarrierPointer() == ReadBarrier::GrayPtr());
+            }
+            PushOntoMarkStack<true>(to_ref);
+          }
+        }
+      }
+    }
+  }
+  return to_ref;
+}
+
+void ConcurrentCopying::FinishPhase() {
+  region_space_ = nullptr;
+  CHECK(mark_queue_.IsEmpty());
+  mark_queue_.Clear();
+  {
+    MutexLock mu(Thread::Current(), skipped_blocks_lock_);
+    skipped_blocks_map_.clear();
+  }
+  WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
+  heap_->ClearMarkedObjects();
+}
+
+mirror::Object* ConcurrentCopying::IsMarkedCallback(mirror::Object* from_ref, void* arg) {
+  return reinterpret_cast<ConcurrentCopying*>(arg)->IsMarked(from_ref);
+}
+
+bool ConcurrentCopying::IsHeapReferenceMarkedCallback(
+    mirror::HeapReference<mirror::Object>* field, void* arg) {
+  mirror::Object* from_ref = field->AsMirrorPtr();
+  mirror::Object* to_ref = reinterpret_cast<ConcurrentCopying*>(arg)->IsMarked(from_ref);
+  if (to_ref == nullptr) {
+    return false;
+  }
+  if (from_ref != to_ref) {
+    QuasiAtomic::ThreadFenceRelease();
+    field->Assign(to_ref);
+    QuasiAtomic::ThreadFenceSequentiallyConsistent();
+  }
+  return true;
+}
+
+mirror::Object* ConcurrentCopying::MarkCallback(mirror::Object* from_ref, void* arg) {
+  return reinterpret_cast<ConcurrentCopying*>(arg)->Mark(from_ref);
+}
+
+void ConcurrentCopying::ProcessMarkStackCallback(void* arg) {
+  reinterpret_cast<ConcurrentCopying*>(arg)->ProcessMarkStack();
+}
+
+void ConcurrentCopying::DelayReferenceReferent(mirror::Class* klass, mirror::Reference* reference) {
+  heap_->GetReferenceProcessor()->DelayReferenceReferent(
+      klass, reference, &IsHeapReferenceMarkedCallback, this);
+}
+
+void ConcurrentCopying::ProcessReferences(Thread* self, bool concurrent) {
+  TimingLogger::ScopedTiming split("ProcessReferences", GetTimings());
+  WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
+  GetHeap()->GetReferenceProcessor()->ProcessReferences(
+      concurrent, GetTimings(), GetCurrentIteration()->GetClearSoftReferences(),
+      &IsHeapReferenceMarkedCallback, &MarkCallback, &ProcessMarkStackCallback, this);
+}
+
+void ConcurrentCopying::RevokeAllThreadLocalBuffers() {
+  TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
+  region_space_->RevokeAllThreadLocalBuffers();
+}
+
 }  // namespace collector
 }  // namespace gc
 }  // namespace art
diff --git a/runtime/gc/collector/concurrent_copying.h b/runtime/gc/collector/concurrent_copying.h
index ee5a785a1a..d740bf2109 100644
--- a/runtime/gc/collector/concurrent_copying.h
+++ b/runtime/gc/collector/concurrent_copying.h
@@ -17,34 +17,268 @@
 #ifndef ART_RUNTIME_GC_COLLECTOR_CONCURRENT_COPYING_H_
 #define ART_RUNTIME_GC_COLLECTOR_CONCURRENT_COPYING_H_
 
+#include "barrier.h"
 #include "garbage_collector.h"
+#include "immune_region.h"
+#include "jni.h"
+#include "object_callbacks.h"
+#include "offsets.h"
+#include "gc/accounting/atomic_stack.h"
+#include "gc/accounting/read_barrier_table.h"
+#include "gc/accounting/space_bitmap.h"
+#include "mirror/object.h"
+#include "mirror/object_reference.h"
+#include "safe_map.h"
+
+#include <unordered_map>
+#include <vector>
 
 namespace art {
+class RootInfo;
+
 namespace gc {
+
+namespace accounting {
+  typedef SpaceBitmap<kObjectAlignment> ContinuousSpaceBitmap;
+  class HeapBitmap;
+}  // namespace accounting
+
+namespace space {
+  class RegionSpace;
+}  // namespace space
+
 namespace collector {
 
-class ConcurrentCopying : public GarbageCollector {
+// Concurrent queue. Used as the mark stack. TODO: use a concurrent
+// stack for locality.
+class MarkQueue {
  public:
-  explicit ConcurrentCopying(Heap* heap, bool generational = false,
-                             const std::string& name_prefix = "")
-      : GarbageCollector(heap,
-                         name_prefix + (name_prefix.empty() ? "" : " ") +
-                         "concurrent copying + mark sweep") {
-    UNUSED(generational);
+  explicit MarkQueue(size_t size) : size_(size) {
+    CHECK(IsPowerOfTwo(size_));
+    buf_.reset(new Atomic<mirror::Object*>[size_]);
+    CHECK(buf_.get() != nullptr);
+    Clear();
+  }
+
+  ALWAYS_INLINE Atomic<mirror::Object*>* GetSlotAddr(size_t index) {
+    return &(buf_.get()[index & (size_ - 1)]);
+  }
+
+  // Multiple-proceducer enqueue.
+  bool Enqueue(mirror::Object* to_ref) {
+    size_t t;
+    do {
+      t = tail_.LoadRelaxed();
+      size_t h = head_.LoadSequentiallyConsistent();
+      if (t + size_ == h) {
+        // It's full.
+        return false;
+      }
+    } while (!tail_.CompareExchangeWeakSequentiallyConsistent(t, t + 1));
+    // We got a slot but its content has not been filled yet at this point.
+    GetSlotAddr(t)->StoreSequentiallyConsistent(to_ref);
+    return true;
   }
 
-  ~ConcurrentCopying() {}
+  // Thread-unsafe.
+  bool EnqueueThreadUnsafe(mirror::Object* to_ref) {
+    size_t t = tail_.LoadRelaxed();
+    size_t h = head_.LoadRelaxed();
+    if (t + size_ == h) {
+      // It's full.
+      return false;
+    }
+    GetSlotAddr(t)->StoreRelaxed(to_ref);
+    tail_.StoreRelaxed(t + 1);
+    return true;
+  }
+
+  // Single-consumer dequeue.
+  mirror::Object* Dequeue() {
+    size_t h = head_.LoadRelaxed();
+    size_t t = tail_.LoadSequentiallyConsistent();
+    if (h == t) {
+      // it's empty.
+      return nullptr;
+    }
+    Atomic<mirror::Object*>* slot = GetSlotAddr(h);
+    mirror::Object* ref = slot->LoadSequentiallyConsistent();
+    while (ref == nullptr) {
+      // Wait until the slot content becomes visible.
+      ref = slot->LoadSequentiallyConsistent();
+    }
+    slot->StoreRelaxed(nullptr);
+    head_.StoreSequentiallyConsistent(h + 1);
+    return ref;
+  }
+
+  bool IsEmpty() {
+    size_t h = head_.LoadSequentiallyConsistent();
+    size_t t = tail_.LoadSequentiallyConsistent();
+    return h == t;
+  }
+
+  void Clear() {
+    head_.StoreRelaxed(0);
+    tail_.StoreRelaxed(0);
+    memset(buf_.get(), 0, size_ * sizeof(Atomic<mirror::Object*>));
+  }
+
+ private:
+  Atomic<size_t> head_;
+  Atomic<size_t> tail_;
+
+  size_t size_;
+  std::unique_ptr<Atomic<mirror::Object*>> buf_;
+};
+
+class ConcurrentCopying : public GarbageCollector {
+ public:
+  // TODO: disable thse flags for production use.
+  // Enable the no-from-space-refs verification at the pause.
+  static constexpr bool kEnableNoFromSpaceRefsVerification = true;
+  // Enable the from-space bytes/objects check.
+  static constexpr bool kEnableFromSpaceAccountingCheck = true;
+  // Enable verbose mode.
+  static constexpr bool kVerboseMode = true;
+
+  ConcurrentCopying(Heap* heap, const std::string& name_prefix = "");
+  ~ConcurrentCopying();
+
+  virtual void RunPhases() OVERRIDE;
+  void InitializePhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void MarkingPhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void ReclaimPhase() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void FinishPhase();
 
-  virtual void RunPhases() OVERRIDE {}
+  void BindBitmaps() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
+      LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
   virtual GcType GetGcType() const OVERRIDE {
     return kGcTypePartial;
   }
   virtual CollectorType GetCollectorType() const OVERRIDE {
     return kCollectorTypeCC;
   }
-  virtual void RevokeAllThreadLocalBuffers() OVERRIDE {}
+  virtual void RevokeAllThreadLocalBuffers() OVERRIDE;
+  void SetRegionSpace(space::RegionSpace* region_space) {
+    DCHECK(region_space != nullptr);
+    region_space_ = region_space;
+  }
+  space::RegionSpace* RegionSpace() {
+    return region_space_;
+  }
+  void AssertToSpaceInvariant(mirror::Object* obj, MemberOffset offset, mirror::Object* ref)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  bool IsInToSpace(mirror::Object* ref) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    DCHECK(ref != nullptr);
+    return IsMarked(ref) == ref;
+  }
+  mirror::Object* Mark(mirror::Object* from_ref) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  bool IsMarking() const {
+    return is_marking_;
+  }
+  bool IsActive() const {
+    return is_active_;
+  }
+  Barrier& GetBarrier() {
+    return *gc_barrier_;
+  }
 
  private:
+  mirror::Object* PopOffMarkStack();
+  template<bool kThreadSafe>
+  void PushOntoMarkStack(mirror::Object* obj) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  mirror::Object* Copy(mirror::Object* from_ref) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void Scan(mirror::Object* to_ref) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void Process(mirror::Object* obj, MemberOffset offset)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void Process(mirror::Object** root) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  static void ProcessRootCallback(mirror::Object** root, void* arg, const RootInfo& root_info)
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void VerifyNoFromSpaceReferences() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
+  accounting::ObjectStack* GetAllocationStack();
+  accounting::ObjectStack* GetLiveStack();
+  bool ProcessMarkStack() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void DelayReferenceReferent(mirror::Class* klass, mirror::Reference* reference)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void ProcessReferences(Thread* self, bool concurrent)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  mirror::Object* IsMarked(mirror::Object* from_ref) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  static mirror::Object* MarkCallback(mirror::Object* from_ref, void* arg)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  static mirror::Object* IsMarkedCallback(mirror::Object* from_ref, void* arg)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  static bool IsHeapReferenceMarkedCallback(
+      mirror::HeapReference<mirror::Object>* field, void* arg)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  static void ProcessMarkStackCallback(void* arg)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void SweepSystemWeaks(Thread* self)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
+  void Sweep(bool swap_bitmaps)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
+  void SweepLargeObjects(bool swap_bitmaps)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
+  void ClearBlackPtrs()
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
+  void FillWithDummyObject(mirror::Object* dummy_obj, size_t byte_size)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  mirror::Object* AllocateInSkippedBlock(size_t alloc_size)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void CheckEmptyMarkQueue() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void IssueEmptyCheckpoint() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  bool IsOnAllocStack(mirror::Object* ref) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  mirror::Object* GetFwdPtr(mirror::Object* from_ref)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void SetFwdPtr(mirror::Object* from_ref, mirror::Object* to_ref)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void FlipThreadRoots() LOCKS_EXCLUDED(Locks::mutator_lock_);;
+  void SwapStacks(Thread* self);
+  void RecordLiveStackFreezeSize(Thread* self);
+  void ComputeUnevacFromSpaceLiveRatio();
+
+  space::RegionSpace* region_space_;      // The underlying region space.
+  std::unique_ptr<Barrier> gc_barrier_;
+  MarkQueue mark_queue_;
+  bool is_marking_;                       // True while marking is ongoing.
+  bool is_active_;                        // True while the collection is ongoing.
+  bool is_asserting_to_space_invariant_;  // True while asserting the to-space invariant.
+  ImmuneRegion immune_region_;
+  std::unique_ptr<accounting::HeapBitmap> cc_heap_bitmap_;
+  std::vector<accounting::SpaceBitmap<kObjectAlignment>*> cc_bitmaps_;
+  accounting::SpaceBitmap<kObjectAlignment>* region_space_bitmap_;
+  // A cache of Heap::GetMarkBitmap().
+  accounting::HeapBitmap* heap_mark_bitmap_;
+  size_t live_stack_freeze_size_;
+  size_t from_space_num_objects_at_first_pause_;
+  size_t from_space_num_bytes_at_first_pause_;
+  Atomic<int> is_mark_queue_push_disallowed_;
+
+  // How many objects and bytes we moved. Used for accounting.
+  Atomic<size_t> bytes_moved_;
+  Atomic<size_t> objects_moved_;
+
+  // The skipped blocks are memory blocks/chucks that were copies of
+  // objects that were unused due to lost races (cas failures) at
+  // object copy/forward pointer install. They are reused.
+  Mutex skipped_blocks_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+  std::multimap<size_t, uint8_t*> skipped_blocks_map_ GUARDED_BY(skipped_blocks_lock_);
+  Atomic<size_t> to_space_bytes_skipped_;
+  Atomic<size_t> to_space_objects_skipped_;
+
+  accounting::ReadBarrierTable* rb_table_;
+  bool force_evacuate_all_;  // True if all regions are evacuated.
+
+  friend class ConcurrentCopyingRefFieldsVisitor;
+  friend class ConcurrentCopyingImmuneSpaceObjVisitor;
+  friend class ConcurrentCopyingVerifyNoFromSpaceRefsVisitor;
+  friend class ConcurrentCopyingVerifyNoFromSpaceRefsObjectVisitor;
+  friend class ConcurrentCopyingClearBlackPtrsVisitor;
+  friend class ConcurrentCopyingLostCopyVisitor;
+  friend class ThreadFlipVisitor;
+  friend class FlipCallback;
+  friend class ConcurrentCopyingComputeUnevacFromSpaceLiveRatioVisitor;
+
   DISALLOW_COPY_AND_ASSIGN(ConcurrentCopying);
 };
 
diff --git a/runtime/gc/collector/immune_region.h b/runtime/gc/collector/immune_region.h
index 277525e831..30144f0b16 100644
--- a/runtime/gc/collector/immune_region.h
+++ b/runtime/gc/collector/immune_region.h
@@ -57,6 +57,13 @@ class ImmuneRegion {
     UpdateSize();
   }
 
+  mirror::Object* Begin() {
+    return begin_;
+  }
+  mirror::Object* End() {
+    return end_;
+  }
+
  private:
   bool IsEmpty() const {
     return size_ == 0;
diff --git a/runtime/gc/heap-inl.h b/runtime/gc/heap-inl.h
index 9d2f6d1238..b8c24521a2 100644
--- a/runtime/gc/heap-inl.h
+++ b/runtime/gc/heap-inl.h
@@ -25,6 +25,7 @@
 #include "gc/space/bump_pointer_space-inl.h"
 #include "gc/space/dlmalloc_space-inl.h"
 #include "gc/space/large_object_space.h"
+#include "gc/space/region_space-inl.h"
 #include "gc/space/rosalloc_space-inl.h"
 #include "runtime.h"
 #include "handle_scope-inl.h"
@@ -66,11 +67,12 @@ inline mirror::Object* Heap::AllocObjectWithAllocator(Thread* self, mirror::Clas
   size_t bytes_allocated;
   size_t usable_size;
   size_t new_num_bytes_allocated = 0;
-  if (allocator == kAllocatorTypeTLAB) {
+  if (allocator == kAllocatorTypeTLAB || allocator == kAllocatorTypeRegionTLAB) {
     byte_count = RoundUp(byte_count, space::BumpPointerSpace::kAlignment);
   }
   // If we have a thread local allocation we don't need to update bytes allocated.
-  if (allocator == kAllocatorTypeTLAB && byte_count <= self->TlabSize()) {
+  if ((allocator == kAllocatorTypeTLAB || allocator == kAllocatorTypeRegionTLAB) &&
+      byte_count <= self->TlabSize()) {
     obj = self->AllocTlab(byte_count);
     DCHECK(obj != nullptr) << "AllocTlab can't fail";
     obj->SetClass(klass);
@@ -195,7 +197,7 @@ template <const bool kInstrumented, const bool kGrow>
 inline mirror::Object* Heap::TryToAllocate(Thread* self, AllocatorType allocator_type,
                                            size_t alloc_size, size_t* bytes_allocated,
                                            size_t* usable_size) {
-  if (allocator_type != kAllocatorTypeTLAB &&
+  if (allocator_type != kAllocatorTypeTLAB && allocator_type != kAllocatorTypeRegionTLAB &&
       UNLIKELY(IsOutOfMemoryOnAllocation<kGrow>(allocator_type, alloc_size))) {
     return nullptr;
   }
@@ -265,6 +267,55 @@ inline mirror::Object* Heap::TryToAllocate(Thread* self, AllocatorType allocator
       *usable_size = alloc_size;
       break;
     }
+    case kAllocatorTypeRegion: {
+      DCHECK(region_space_ != nullptr);
+      alloc_size = RoundUp(alloc_size, space::RegionSpace::kAlignment);
+      ret = region_space_->AllocNonvirtual<false>(alloc_size, bytes_allocated, usable_size);
+      break;
+    }
+    case kAllocatorTypeRegionTLAB: {
+      DCHECK(region_space_ != nullptr);
+      DCHECK_ALIGNED(alloc_size, space::RegionSpace::kAlignment);
+      if (UNLIKELY(self->TlabSize() < alloc_size)) {
+        if (space::RegionSpace::kRegionSize >= alloc_size) {
+          // Non-large. Check OOME for a tlab.
+          if (LIKELY(!IsOutOfMemoryOnAllocation<kGrow>(allocator_type, space::RegionSpace::kRegionSize))) {
+            // Try to allocate a tlab.
+            if (!region_space_->AllocNewTlab(self)) {
+              // Failed to allocate a tlab. Try non-tlab.
+              ret = region_space_->AllocNonvirtual<false>(alloc_size, bytes_allocated, usable_size);
+              return ret;
+            }
+            *bytes_allocated = space::RegionSpace::kRegionSize;
+            // Fall-through.
+          } else {
+            // Check OOME for a non-tlab allocation.
+            if (!IsOutOfMemoryOnAllocation<kGrow>(allocator_type, alloc_size)) {
+              ret = region_space_->AllocNonvirtual<false>(alloc_size, bytes_allocated, usable_size);
+              return ret;
+            } else {
+              // Neither tlab or non-tlab works. Give up.
+              return nullptr;
+            }
+          }
+        } else {
+          // Large. Check OOME.
+          if (LIKELY(!IsOutOfMemoryOnAllocation<kGrow>(allocator_type, alloc_size))) {
+            ret = region_space_->AllocNonvirtual<false>(alloc_size, bytes_allocated, usable_size);
+            return ret;
+          } else {
+            return nullptr;
+          }
+        }
+      } else {
+        *bytes_allocated = 0;
+      }
+      // The allocation can't fail.
+      ret = self->AllocTlab(alloc_size);
+      DCHECK(ret != nullptr);
+      *usable_size = alloc_size;
+      break;
+    }
     default: {
       LOG(FATAL) << "Invalid allocator type";
       ret = nullptr;
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 6ba30c6580..ba06e0574f 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -49,6 +49,7 @@
 #include "gc/space/dlmalloc_space-inl.h"
 #include "gc/space/image_space.h"
 #include "gc/space/large_object_space.h"
+#include "gc/space/region_space.h"
 #include "gc/space/rosalloc_space-inl.h"
 #include "gc/space/space-inl.h"
 #include "gc/space/zygote_space.h"
@@ -176,6 +177,7 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
       current_non_moving_allocator_(kAllocatorTypeNonMoving),
       bump_pointer_space_(nullptr),
       temp_space_(nullptr),
+      region_space_(nullptr),
       min_free_(min_free),
       max_free_(max_free),
       target_utilization_(target_utilization),
@@ -211,6 +213,12 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
   mark_bitmap_.reset(new accounting::HeapBitmap(this));
   // Requested begin for the alloc space, to follow the mapped image and oat files
   uint8_t* requested_alloc_space_begin = nullptr;
+  if (foreground_collector_type_ == kCollectorTypeCC) {
+    // Need to use a low address so that we can allocate a contiguous
+    // 2 * Xmx space when there's no image (dex2oat for target).
+    CHECK_GE(300 * MB, non_moving_space_capacity);
+    requested_alloc_space_begin = reinterpret_cast<uint8_t*>(300 * MB) - non_moving_space_capacity;
+  }
   if (!image_file_name.empty()) {
     std::string error_msg;
     space::ImageSpace* image_space = space::ImageSpace::Create(image_file_name.c_str(),
@@ -241,8 +249,9 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
                                      +-main alloc space2 / bump space 2 (capacity_)+-
                                      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
   */
-  // We don't have hspace compaction enabled with GSS.
-  if (foreground_collector_type_ == kCollectorTypeGSS) {
+  // We don't have hspace compaction enabled with GSS or CC.
+  if (foreground_collector_type_ == kCollectorTypeGSS ||
+      foreground_collector_type_ == kCollectorTypeCC) {
     use_homogeneous_space_compaction_for_oom_ = false;
   }
   bool support_homogeneous_space_compaction =
@@ -280,10 +289,12 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
     // Try to reserve virtual memory at a lower address if we have a separate non moving space.
     request_begin = reinterpret_cast<uint8_t*>(300 * MB);
   }
-  // Attempt to create 2 mem maps at or after the requested begin.
-  main_mem_map_1.reset(MapAnonymousPreferredAddress(kMemMapSpaceName[0], request_begin, capacity_,
-                                                    &error_str));
-  CHECK(main_mem_map_1.get() != nullptr) << error_str;
+  if (foreground_collector_type_ != kCollectorTypeCC) {
+    // Attempt to create 2 mem maps at or after the requested begin.
+    main_mem_map_1.reset(MapAnonymousPreferredAddress(kMemMapSpaceName[0], request_begin, capacity_,
+                                                      &error_str));
+    CHECK(main_mem_map_1.get() != nullptr) << error_str;
+  }
   if (support_homogeneous_space_compaction ||
       background_collector_type_ == kCollectorTypeSS ||
       foreground_collector_type_ == kCollectorTypeSS) {
@@ -305,7 +316,10 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
     AddSpace(non_moving_space_);
   }
   // Create other spaces based on whether or not we have a moving GC.
-  if (IsMovingGc(foreground_collector_type_) && foreground_collector_type_ != kCollectorTypeGSS) {
+  if (foreground_collector_type_ == kCollectorTypeCC) {
+    region_space_ = space::RegionSpace::Create("Region space", capacity_ * 2, request_begin);
+    AddSpace(region_space_);
+  } else if (IsMovingGc(foreground_collector_type_) && foreground_collector_type_ != kCollectorTypeGSS) {
     // Create bump pointer spaces.
     // We only to create the bump pointer if the foreground collector is a compacting GC.
     // TODO: Place bump-pointer spaces somewhere to minimize size of card table.
@@ -379,6 +393,12 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
   // Allocate the card table.
   card_table_.reset(accounting::CardTable::Create(heap_begin, heap_capacity));
   CHECK(card_table_.get() != NULL) << "Failed to create card table";
+
+  if (foreground_collector_type_ == kCollectorTypeCC && kUseTableLookupReadBarrier) {
+    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 =
@@ -703,29 +723,64 @@ void Heap::CreateThreadPool() {
   }
 }
 
+// Visit objects when threads aren't suspended. If concurrent moving
+// GC, disable moving GC and suspend threads and then visit objects.
 void Heap::VisitObjects(ObjectCallback callback, void* arg) {
   Thread* self = Thread::Current();
-  if (Locks::mutator_lock_->IsExclusiveHeld(self)) {
-    // Threads are already suspended.
-    VisitObjectsInternal(callback, arg);
-  } else if (IsGcConcurrent() && IsMovingGc(collector_type_)) {
-    // Concurrent moving GC. Suspend all threads and visit objects.
-    DCHECK_EQ(collector_type_, foreground_collector_type_);
-    DCHECK_EQ(foreground_collector_type_, background_collector_type_)
-        << "Assume no transition such that collector_type_ won't change";
+  Locks::mutator_lock_->AssertSharedHeld(self);
+  DCHECK(!Locks::mutator_lock_->IsExclusiveHeld(self)) << "Call VisitObjectsPaused() instead";
+  if (IsGcConcurrentAndMoving()) {
+    // Concurrent moving GC. Just suspending threads isn't sufficient
+    // because a collection isn't one big pause and we could suspend
+    // threads in the middle (between phases) of a concurrent moving
+    // collection where it's not easily known which objects are alive
+    // (both the region space and the non-moving space) or which
+    // copies of objects to visit, and the to-space invariant could be
+    // easily broken. Visit objects while GC isn't running by using
+    // IncrementDisableMovingGC() and threads are suspended.
+    IncrementDisableMovingGC(self);
     self->TransitionFromRunnableToSuspended(kWaitingForVisitObjects);
     ThreadList* tl = Runtime::Current()->GetThreadList();
     tl->SuspendAll();
+    VisitObjectsInternalRegionSpace(callback, arg);
     VisitObjectsInternal(callback, arg);
     tl->ResumeAll();
     self->TransitionFromSuspendedToRunnable();
+    DecrementDisableMovingGC(self);
   } else {
     // GCs can move objects, so don't allow this.
     ScopedAssertNoThreadSuspension ants(self, "Visiting objects");
+    DCHECK(region_space_ == nullptr);
     VisitObjectsInternal(callback, arg);
   }
 }
 
+// Visit objects when threads are already suspended.
+void Heap::VisitObjectsPaused(ObjectCallback callback, void* arg) {
+  Thread* self = Thread::Current();
+  Locks::mutator_lock_->AssertExclusiveHeld(self);
+  VisitObjectsInternalRegionSpace(callback, arg);
+  VisitObjectsInternal(callback, arg);
+}
+
+// Visit objects in the region spaces.
+void Heap::VisitObjectsInternalRegionSpace(ObjectCallback callback, void* arg) {
+  Thread* self = Thread::Current();
+  Locks::mutator_lock_->AssertExclusiveHeld(self);
+  if (region_space_ != nullptr) {
+    DCHECK(IsGcConcurrentAndMoving());
+    if (!zygote_creation_lock_.IsExclusiveHeld(self)) {
+      // Exclude the pre-zygote fork time where the semi-space collector
+      // calls VerifyHeapReferences() as part of the zygote compaction
+      // which then would call here without the moving GC disabled,
+      // which is fine.
+      DCHECK(IsMovingGCDisabled(self));
+    }
+    region_space_->Walk(callback, arg);
+  }
+}
+
+// Visit objects in the other spaces.
 void Heap::VisitObjectsInternal(ObjectCallback callback, void* arg) {
   if (bump_pointer_space_ != nullptr) {
     // Visit objects in bump pointer space.
@@ -956,6 +1011,9 @@ void Heap::ThrowOutOfMemoryError(Thread* self, size_t byte_count, AllocatorType
     } else if (allocator_type == kAllocatorTypeBumpPointer ||
                allocator_type == kAllocatorTypeTLAB) {
       space = bump_pointer_space_;
+    } else if (allocator_type == kAllocatorTypeRegion ||
+               allocator_type == kAllocatorTypeRegionTLAB) {
+      space = region_space_;
     }
     if (space != nullptr) {
       space->LogFragmentationAllocFailure(oss, byte_count);
@@ -1062,6 +1120,9 @@ void Heap::TrimSpaces(Thread* self) {
   if (bump_pointer_space_ != nullptr) {
     total_alloc_space_allocated -= bump_pointer_space_->Size();
   }
+  if (region_space_ != nullptr) {
+    total_alloc_space_allocated -= region_space_->GetBytesAllocated();
+  }
   const float managed_utilization = static_cast<float>(total_alloc_space_allocated) /
       static_cast<float>(total_alloc_space_size);
   uint64_t gc_heap_end_ns = NanoTime();
@@ -1134,6 +1195,9 @@ bool Heap::IsLiveObjectLocked(mirror::Object* obj, bool search_allocation_stack,
     // a GC). When a GC isn't running End() - Begin() is 0 which means no objects are contained.
     return temp_space_->Contains(obj);
   }
+  if (region_space_ != nullptr && region_space_->HasAddress(obj)) {
+    return true;
+  }
   space::ContinuousSpace* c_space = FindContinuousSpaceFromObject(obj, true);
   space::DiscontinuousSpace* d_space = nullptr;
   if (c_space != nullptr) {
@@ -1780,7 +1844,15 @@ void Heap::ChangeCollector(CollectorType collector_type) {
     collector_type_ = collector_type;
     gc_plan_.clear();
     switch (collector_type_) {
-      case kCollectorTypeCC:  // Fall-through.
+      case kCollectorTypeCC: {
+        gc_plan_.push_back(collector::kGcTypeFull);
+        if (use_tlab_) {
+          ChangeAllocator(kAllocatorTypeRegionTLAB);
+        } else {
+          ChangeAllocator(kAllocatorTypeRegion);
+        }
+        break;
+      }
       case kCollectorTypeMC:  // Fall-through.
       case kCollectorTypeSS:  // Fall-through.
       case kCollectorTypeGSS: {
@@ -1963,7 +2035,11 @@ void Heap::PreZygoteFork() {
     // Compact the bump pointer space to a new zygote bump pointer space.
     bool reset_main_space = false;
     if (IsMovingGc(collector_type_)) {
-      zygote_collector.SetFromSpace(bump_pointer_space_);
+      if (collector_type_ == kCollectorTypeCC) {
+        zygote_collector.SetFromSpace(region_space_);
+      } else {
+        zygote_collector.SetFromSpace(bump_pointer_space_);
+      }
     } else {
       CHECK(main_space_ != nullptr);
       // Copy from the main space.
@@ -1984,7 +2060,11 @@ void Heap::PreZygoteFork() {
       delete old_main_space;
       AddSpace(main_space_);
     } else {
-      bump_pointer_space_->GetMemMap()->Protect(PROT_READ | PROT_WRITE);
+      if (collector_type_ == kCollectorTypeCC) {
+        region_space_->GetMemMap()->Protect(PROT_READ | PROT_WRITE);
+      } else {
+        bump_pointer_space_->GetMemMap()->Protect(PROT_READ | PROT_WRITE);
+      }
     }
     if (temp_space_ != nullptr) {
       CHECK(temp_space_->IsEmpty());
@@ -2154,7 +2234,9 @@ collector::GcType Heap::CollectGarbageInternal(collector::GcType gc_type, GcCaus
   // TODO: Clean this up.
   if (compacting_gc) {
     DCHECK(current_allocator_ == kAllocatorTypeBumpPointer ||
-           current_allocator_ == kAllocatorTypeTLAB);
+           current_allocator_ == kAllocatorTypeTLAB ||
+           current_allocator_ == kAllocatorTypeRegion ||
+           current_allocator_ == kAllocatorTypeRegionTLAB);
     switch (collector_type_) {
       case kCollectorTypeSS:
         // Fall-through.
@@ -2165,6 +2247,7 @@ collector::GcType Heap::CollectGarbageInternal(collector::GcType gc_type, GcCaus
         collector = semi_space_collector_;
         break;
       case kCollectorTypeCC:
+        concurrent_copying_collector_->SetRegionSpace(region_space_);
         collector = concurrent_copying_collector_;
         break;
       case kCollectorTypeMC:
@@ -2174,7 +2257,7 @@ collector::GcType Heap::CollectGarbageInternal(collector::GcType gc_type, GcCaus
       default:
         LOG(FATAL) << "Invalid collector type " << static_cast<size_t>(collector_type_);
     }
-    if (collector != mark_compact_collector_) {
+    if (collector != mark_compact_collector_ && collector != concurrent_copying_collector_) {
       temp_space_->GetMemMap()->Protect(PROT_READ | PROT_WRITE);
       CHECK(temp_space_->IsEmpty());
     }
@@ -2491,7 +2574,7 @@ size_t Heap::VerifyHeapReferences(bool verify_referents) {
   // 2. Allocated during the GC (pre sweep GC verification).
   // We don't want to verify the objects in the live stack since they themselves may be
   // pointing to dead objects if they are not reachable.
-  VisitObjects(VerifyObjectVisitor::VisitCallback, &visitor);
+  VisitObjectsPaused(VerifyObjectVisitor::VisitCallback, &visitor);
   // Verify the roots:
   Runtime::Current()->VisitRoots(VerifyReferenceVisitor::VerifyRootCallback, &visitor);
   if (visitor.GetFailureCount() > 0) {
@@ -2633,7 +2716,7 @@ void Heap::SwapStacks(Thread* self) {
 
 void Heap::RevokeAllThreadLocalAllocationStacks(Thread* self) {
   // This must be called only during the pause.
-  CHECK(Locks::mutator_lock_->IsExclusiveHeld(self));
+  DCHECK(Locks::mutator_lock_->IsExclusiveHeld(self));
   MutexLock mu(self, *Locks::runtime_shutdown_lock_);
   MutexLock mu2(self, *Locks::thread_list_lock_);
   std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
@@ -3175,6 +3258,9 @@ void Heap::RevokeThreadLocalBuffers(Thread* thread) {
   if (bump_pointer_space_ != nullptr) {
     bump_pointer_space_->RevokeThreadLocalBuffers(thread);
   }
+  if (region_space_ != nullptr) {
+    region_space_->RevokeThreadLocalBuffers(thread);
+  }
 }
 
 void Heap::RevokeRosAllocThreadLocalBuffers(Thread* thread) {
@@ -3190,6 +3276,9 @@ void Heap::RevokeAllThreadLocalBuffers() {
   if (bump_pointer_space_ != nullptr) {
     bump_pointer_space_->RevokeAllThreadLocalBuffers();
   }
+  if (region_space_ != nullptr) {
+    region_space_->RevokeAllThreadLocalBuffers();
+  }
 }
 
 bool Heap::IsGCRequestPending() const {
diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h
index 36a3767721..b0b53b0085 100644
--- a/runtime/gc/heap.h
+++ b/runtime/gc/heap.h
@@ -27,6 +27,7 @@
 #include "base/timing_logger.h"
 #include "gc/accounting/atomic_stack.h"
 #include "gc/accounting/card_table.h"
+#include "gc/accounting/read_barrier_table.h"
 #include "gc/gc_cause.h"
 #include "gc/collector/garbage_collector.h"
 #include "gc/collector/gc_type.h"
@@ -86,6 +87,7 @@ namespace space {
   class ImageSpace;
   class LargeObjectSpace;
   class MallocSpace;
+  class RegionSpace;
   class RosAllocSpace;
   class Space;
   class SpaceTest;
@@ -218,8 +220,8 @@ class Heap {
   void VisitObjects(ObjectCallback callback, void* arg)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
       LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
-  void VisitObjectsInternal(ObjectCallback callback, void* arg)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
+  void VisitObjectsPaused(ObjectCallback callback, void* arg)
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_)
       LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
 
   void CheckPreconditionsForAllocObject(mirror::Class* c, size_t byte_count)
@@ -410,6 +412,10 @@ class Heap {
     return card_table_.get();
   }
 
+  accounting::ReadBarrierTable* GetReadBarrierTable() const {
+    return rb_table_.get();
+  }
+
   void AddFinalizerReference(Thread* self, mirror::Object** object);
 
   // Returns the number of bytes currently allocated.
@@ -623,6 +629,30 @@ class Heap {
     return zygote_space_ != nullptr;
   }
 
+  collector::ConcurrentCopying* ConcurrentCopyingCollector() {
+    return concurrent_copying_collector_;
+  }
+
+  CollectorType CurrentCollectorType() {
+    return collector_type_;
+  }
+
+  bool IsGcConcurrentAndMoving() const {
+    if (IsGcConcurrent() && IsMovingGc(collector_type_)) {
+      // Assume no transition when a concurrent moving collector is used.
+      DCHECK_EQ(collector_type_, foreground_collector_type_);
+      DCHECK_EQ(foreground_collector_type_, background_collector_type_)
+          << "Assume no transition such that collector_type_ won't change";
+      return true;
+    }
+    return false;
+  }
+
+  bool IsMovingGCDisabled(Thread* self) {
+    MutexLock mu(self, *gc_complete_lock_);
+    return disable_moving_gc_count_ > 0;
+  }
+
   // Request an asynchronous trim.
   void RequestTrim(Thread* self) LOCKS_EXCLUDED(pending_task_lock_);
 
@@ -654,10 +684,14 @@ class Heap {
   static ALWAYS_INLINE bool AllocatorHasAllocationStack(AllocatorType allocator_type) {
     return
         allocator_type != kAllocatorTypeBumpPointer &&
-        allocator_type != kAllocatorTypeTLAB;
+        allocator_type != kAllocatorTypeTLAB &&
+        allocator_type != kAllocatorTypeRegion &&
+        allocator_type != kAllocatorTypeRegionTLAB;
   }
   static ALWAYS_INLINE bool AllocatorMayHaveConcurrentGC(AllocatorType allocator_type) {
-    return AllocatorHasAllocationStack(allocator_type);
+    return
+        allocator_type != kAllocatorTypeBumpPointer &&
+        allocator_type != kAllocatorTypeTLAB;
   }
   static bool IsMovingGc(CollectorType collector_type) {
     return collector_type == kCollectorTypeSS || collector_type == kCollectorTypeGSS ||
@@ -813,6 +847,13 @@ class Heap {
   // Trim 0 pages at the end of reference tables.
   void TrimIndirectReferenceTables(Thread* self);
 
+  void VisitObjectsInternal(ObjectCallback callback, void* arg)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
+      LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
+  void VisitObjectsInternalRegionSpace(ObjectCallback callback, void* arg)
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_)
+      LOCKS_EXCLUDED(Locks::heap_bitmap_lock_);
+
   // All-known continuous spaces, where objects lie within fixed bounds.
   std::vector<space::ContinuousSpace*> continuous_spaces_;
 
@@ -842,6 +883,8 @@ class Heap {
   // The card table, dirtied by the write barrier.
   std::unique_ptr<accounting::CardTable> card_table_;
 
+  std::unique_ptr<accounting::ReadBarrierTable> rb_table_;
+
   // A mod-union table remembers all of the references from the it's space to other spaces.
   AllocationTrackingSafeMap<space::Space*, accounting::ModUnionTable*, kAllocatorTagHeap>
       mod_union_tables_;
@@ -1020,6 +1063,8 @@ class Heap {
   // Temp space is the space which the semispace collector copies to.
   space::BumpPointerSpace* temp_space_;
 
+  space::RegionSpace* region_space_;
+
   // Minimum free guarantees that you always have at least min_free_ free bytes after growing for
   // utilization, regardless of target utilization ratio.
   size_t min_free_;
@@ -1088,6 +1133,7 @@ class Heap {
   friend class CollectorTransitionTask;
   friend class collector::GarbageCollector;
   friend class collector::MarkCompact;
+  friend class collector::ConcurrentCopying;
   friend class collector::MarkSweep;
   friend class collector::SemiSpace;
   friend class ReferenceQueue;
diff --git a/runtime/gc/reference_processor.h b/runtime/gc/reference_processor.h
index 5eb095b364..c67fd98034 100644
--- a/runtime/gc/reference_processor.h
+++ b/runtime/gc/reference_processor.h
@@ -53,7 +53,7 @@ class ReferenceProcessor {
   // The slow path bool is contained in the reference class object, can only be set once
   // Only allow setting this with mutators suspended so that we can avoid using a lock in the
   // GetReferent fast path as an optimization.
-  void EnableSlowPath() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void EnableSlowPath() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   // Decode the referent, may block if references are being processed.
   mirror::Object* GetReferent(Thread* self, mirror::Reference* reference)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) LOCKS_EXCLUDED(Locks::reference_processor_lock_);
diff --git a/runtime/gc/reference_queue.cc b/runtime/gc/reference_queue.cc
index f4efe3c823..7be0704d01 100644
--- a/runtime/gc/reference_queue.cc
+++ b/runtime/gc/reference_queue.cc
@@ -17,6 +17,7 @@
 #include "reference_queue.h"
 
 #include "accounting/card_table-inl.h"
+#include "collector/concurrent_copying.h"
 #include "heap.h"
 #include "mirror/class-inl.h"
 #include "mirror/object-inl.h"
@@ -85,6 +86,24 @@ mirror::Reference* ReferenceQueue::DequeuePendingReference() {
   } else {
     ref->SetPendingNext<false>(nullptr);
   }
+  Heap* heap = Runtime::Current()->GetHeap();
+  if (kUseBakerOrBrooksReadBarrier && heap->CurrentCollectorType() == kCollectorTypeCC &&
+      heap->ConcurrentCopyingCollector()->IsActive()) {
+    // Clear the gray ptr we left in ConcurrentCopying::ProcessMarkStack().
+    // We don't want to do this when the zygote compaction collector (SemiSpace) is running.
+    CHECK(ref != nullptr);
+    CHECK_EQ(ref->GetReadBarrierPointer(), ReadBarrier::GrayPtr())
+        << "ref=" << ref << " rb_ptr=" << ref->GetReadBarrierPointer();
+    if (heap->ConcurrentCopyingCollector()->RegionSpace()->IsInToSpace(ref)) {
+      // Moving objects.
+      ref->SetReadBarrierPointer(ReadBarrier::WhitePtr());
+      CHECK_EQ(ref->GetReadBarrierPointer(), ReadBarrier::WhitePtr());
+    } else {
+      // Non-moving objects.
+      ref->SetReadBarrierPointer(ReadBarrier::BlackPtr());
+      CHECK_EQ(ref->GetReadBarrierPointer(), ReadBarrier::BlackPtr());
+    }
+  }
   return ref;
 }
 
diff --git a/runtime/gc/space/bump_pointer_space.cc b/runtime/gc/space/bump_pointer_space.cc
index 04b09e9969..9675ba6f50 100644
--- a/runtime/gc/space/bump_pointer_space.cc
+++ b/runtime/gc/space/bump_pointer_space.cc
@@ -57,7 +57,7 @@ BumpPointerSpace::BumpPointerSpace(const std::string& name, MemMap* mem_map)
                                  kGcRetentionPolicyAlwaysCollect),
       growth_end_(mem_map->End()),
       objects_allocated_(0), bytes_allocated_(0),
-      block_lock_("Block lock"),
+      block_lock_("Block lock", kBumpPointerSpaceBlockLock),
       main_block_size_(0),
       num_blocks_(0) {
 }
@@ -172,7 +172,8 @@ void BumpPointerSpace::Walk(ObjectCallback* callback, void* arg) {
   // Walk all of the objects in the main block first.
   while (pos < main_end) {
     mirror::Object* obj = reinterpret_cast<mirror::Object*>(pos);
-    if (obj->GetClass() == nullptr) {
+    // No read barrier because obj may not be a valid object.
+    if (obj->GetClass<kDefaultVerifyFlags, kWithoutReadBarrier>() == nullptr) {
       // There is a race condition where a thread has just allocated an object but not set the
       // class. We can't know the size of this object, so we don't visit it and exit the function
       // since there is guaranteed to be not other blocks.
@@ -192,7 +193,8 @@ void BumpPointerSpace::Walk(ObjectCallback* callback, void* arg) {
     CHECK_LE(reinterpret_cast<const uint8_t*>(end_obj), End());
     // We don't know how many objects are allocated in the current block. When we hit a null class
     // assume its the end. TODO: Have a thread update the header when it flushes the block?
-    while (obj < end_obj && obj->GetClass() != nullptr) {
+    // No read barrier because obj may not be a valid object.
+    while (obj < end_obj && obj->GetClass<kDefaultVerifyFlags, kWithoutReadBarrier>() != nullptr) {
       callback(obj, arg);
       obj = GetNextObject(obj);
     }
diff --git a/runtime/gc/space/region_space-inl.h b/runtime/gc/space/region_space-inl.h
new file mode 100644
index 0000000000..fd00739ede
--- /dev/null
+++ b/runtime/gc/space/region_space-inl.h
@@ -0,0 +1,316 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_GC_SPACE_REGION_SPACE_INL_H_
+#define ART_RUNTIME_GC_SPACE_REGION_SPACE_INL_H_
+
+#include "region_space.h"
+
+namespace art {
+namespace gc {
+namespace space {
+
+inline mirror::Object* RegionSpace::Alloc(Thread*, size_t num_bytes, size_t* bytes_allocated,
+                                          size_t* usable_size) {
+  num_bytes = RoundUp(num_bytes, kAlignment);
+  return AllocNonvirtual<false>(num_bytes, bytes_allocated, usable_size);
+}
+
+inline mirror::Object* RegionSpace::AllocThreadUnsafe(Thread* self, size_t num_bytes,
+                                                      size_t* bytes_allocated,
+                                                      size_t* usable_size) {
+  Locks::mutator_lock_->AssertExclusiveHeld(self);
+  return Alloc(self, num_bytes, bytes_allocated, usable_size);
+}
+
+template<bool kForEvac>
+inline mirror::Object* RegionSpace::AllocNonvirtual(size_t num_bytes, size_t* bytes_allocated,
+                                                    size_t* usable_size) {
+  DCHECK(IsAligned<kAlignment>(num_bytes));
+  mirror::Object* obj;
+  if (LIKELY(num_bytes <= kRegionSize)) {
+    // Non-large object.
+    if (!kForEvac) {
+      obj = current_region_->Alloc(num_bytes, bytes_allocated, usable_size);
+    } else {
+      DCHECK(evac_region_ != nullptr);
+      obj = evac_region_->Alloc(num_bytes, bytes_allocated, usable_size);
+    }
+    if (LIKELY(obj != nullptr)) {
+      return obj;
+    }
+    MutexLock mu(Thread::Current(), region_lock_);
+    // Retry with current region since another thread may have updated it.
+    if (!kForEvac) {
+      obj = current_region_->Alloc(num_bytes, bytes_allocated, usable_size);
+    } else {
+      obj = evac_region_->Alloc(num_bytes, bytes_allocated, usable_size);
+    }
+    if (LIKELY(obj != nullptr)) {
+      return obj;
+    }
+    if (!kForEvac) {
+      // Retain sufficient free regions for full evacuation.
+      if ((num_non_free_regions_ + 1) * 2 > num_regions_) {
+        return nullptr;
+      }
+      for (size_t i = 0; i < num_regions_; ++i) {
+        Region* r = &regions_[i];
+        if (r->IsFree()) {
+          r->Unfree(time_);
+          r->SetNewlyAllocated();
+          ++num_non_free_regions_;
+          obj = r->Alloc(num_bytes, bytes_allocated, usable_size);
+          CHECK(obj != nullptr);
+          current_region_ = r;
+          return obj;
+        }
+      }
+    } else {
+      for (size_t i = 0; i < num_regions_; ++i) {
+        Region* r = &regions_[i];
+        if (r->IsFree()) {
+          r->Unfree(time_);
+          ++num_non_free_regions_;
+          obj = r->Alloc(num_bytes, bytes_allocated, usable_size);
+          CHECK(obj != nullptr);
+          evac_region_ = r;
+          return obj;
+        }
+      }
+    }
+  } else {
+    // Large object.
+    obj = AllocLarge<kForEvac>(num_bytes, bytes_allocated, usable_size);
+    if (LIKELY(obj != nullptr)) {
+      return obj;
+    }
+  }
+  return nullptr;
+}
+
+inline mirror::Object* RegionSpace::Region::Alloc(size_t num_bytes, size_t* bytes_allocated,
+                                                  size_t* usable_size) {
+  DCHECK_EQ(state_, static_cast<uint8_t>(kRegionToSpace));
+  DCHECK(IsAligned<kAlignment>(num_bytes));
+  Atomic<uint8_t*>* atomic_top = reinterpret_cast<Atomic<uint8_t*>*>(&top_);
+  uint8_t* old_top;
+  uint8_t* new_top;
+  do {
+    old_top = atomic_top->LoadRelaxed();
+    new_top = old_top + num_bytes;
+    if (UNLIKELY(new_top > end_)) {
+      return nullptr;
+    }
+  } while (!atomic_top->CompareExchangeWeakSequentiallyConsistent(old_top, new_top));
+  reinterpret_cast<Atomic<uint64_t>*>(&objects_allocated_)->FetchAndAddSequentiallyConsistent(1);
+  DCHECK_LE(atomic_top->LoadRelaxed(), end_);
+  DCHECK_LT(old_top, end_);
+  DCHECK_LE(new_top, end_);
+  *bytes_allocated = num_bytes;
+  if (usable_size != nullptr) {
+    *usable_size = num_bytes;
+  }
+  return reinterpret_cast<mirror::Object*>(old_top);
+}
+
+inline size_t RegionSpace::AllocationSizeNonvirtual(mirror::Object* obj, size_t* usable_size)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  size_t num_bytes = obj->SizeOf();
+  if (usable_size != nullptr) {
+    if (LIKELY(num_bytes <= kRegionSize)) {
+      DCHECK(RefToRegion(obj)->IsNormal());
+      *usable_size = RoundUp(num_bytes, kAlignment);
+    } else {
+      DCHECK(RefToRegion(obj)->IsLarge());
+      *usable_size = RoundUp(num_bytes, kRegionSize);
+    }
+  }
+  return num_bytes;
+}
+
+template<RegionSpace::SubSpaceType kSubSpaceType>
+uint64_t RegionSpace::GetBytesAllocatedInternal() {
+  uint64_t bytes = 0;
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (r->IsFree()) {
+      continue;
+    }
+    switch (kSubSpaceType) {
+      case kAllSpaces:
+        bytes += r->BytesAllocated();
+        break;
+      case kFromSpace:
+        if (r->IsInFromSpace()) {
+          bytes += r->BytesAllocated();
+        }
+        break;
+      case kUnevacFromSpace:
+        if (r->IsInUnevacFromSpace()) {
+          bytes += r->BytesAllocated();
+        }
+        break;
+      case kToSpace:
+        if (r->IsInToSpace()) {
+          bytes += r->BytesAllocated();
+        }
+        break;
+      default:
+        LOG(FATAL) << "Unexpected space type : " << static_cast<int>(kSubSpaceType);
+    }
+  }
+  return bytes;
+}
+
+template<RegionSpace::SubSpaceType kSubSpaceType>
+uint64_t RegionSpace::GetObjectsAllocatedInternal() {
+  uint64_t bytes = 0;
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (r->IsFree()) {
+      continue;
+    }
+    switch (kSubSpaceType) {
+      case kAllSpaces:
+        bytes += r->ObjectsAllocated();
+        break;
+      case kFromSpace:
+        if (r->IsInFromSpace()) {
+          bytes += r->ObjectsAllocated();
+        }
+        break;
+      case kUnevacFromSpace:
+        if (r->IsInUnevacFromSpace()) {
+          bytes += r->ObjectsAllocated();
+        }
+        break;
+      case kToSpace:
+        if (r->IsInToSpace()) {
+          bytes += r->ObjectsAllocated();
+        }
+        break;
+      default:
+        LOG(FATAL) << "Unexpected space type : " << static_cast<int>(kSubSpaceType);
+    }
+  }
+  return bytes;
+}
+
+template<bool kToSpaceOnly>
+void RegionSpace::WalkInternal(ObjectCallback* callback, void* arg) {
+  // TODO: MutexLock on region_lock_ won't work due to lock order
+  // issues (the classloader classes lock and the monitor lock). We
+  // call this with threads suspended.
+  Locks::mutator_lock_->AssertExclusiveHeld(Thread::Current());
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (r->IsFree() || (kToSpaceOnly && !r->IsInToSpace())) {
+      continue;
+    }
+    if (r->IsLarge()) {
+      mirror::Object* obj = reinterpret_cast<mirror::Object*>(r->Begin());
+      if (obj->GetClass() != nullptr) {
+        callback(obj, arg);
+      }
+    } else if (r->IsLargeTail()) {
+      // Do nothing.
+    } else {
+      uint8_t* pos = r->Begin();
+      uint8_t* top = r->Top();
+      while (pos < top) {
+        mirror::Object* obj = reinterpret_cast<mirror::Object*>(pos);
+        if (obj->GetClass<kDefaultVerifyFlags, kWithoutReadBarrier>() != nullptr) {
+          callback(obj, arg);
+          pos = reinterpret_cast<uint8_t*>(GetNextObject(obj));
+        } else {
+          break;
+        }
+      }
+    }
+  }
+}
+
+inline mirror::Object* RegionSpace::GetNextObject(mirror::Object* obj) {
+  const uintptr_t position = reinterpret_cast<uintptr_t>(obj) + obj->SizeOf();
+  return reinterpret_cast<mirror::Object*>(RoundUp(position, kAlignment));
+}
+
+template<bool kForEvac>
+mirror::Object* RegionSpace::AllocLarge(size_t num_bytes, size_t* bytes_allocated,
+                                        size_t* usable_size) {
+  DCHECK(IsAligned<kAlignment>(num_bytes));
+  DCHECK_GT(num_bytes, kRegionSize);
+  size_t num_regs = RoundUp(num_bytes, kRegionSize) / kRegionSize;
+  DCHECK_GT(num_regs, 0U);
+  DCHECK_LT((num_regs - 1) * kRegionSize, num_bytes);
+  DCHECK_LE(num_bytes, num_regs * kRegionSize);
+  MutexLock mu(Thread::Current(), region_lock_);
+  if (!kForEvac) {
+    // Retain sufficient free regions for full evacuation.
+    if ((num_non_free_regions_ + num_regs) * 2 > num_regions_) {
+      return nullptr;
+    }
+  }
+  // Find a large enough contiguous free regions.
+  size_t left = 0;
+  while (left + num_regs - 1 < num_regions_) {
+    bool found = true;
+    size_t right = left;
+    DCHECK_LT(right, left + num_regs)
+        << "The inner loop Should iterate at least once";
+    while (right < left + num_regs) {
+      if (regions_[right].IsFree()) {
+        ++right;
+      } else {
+        found = false;
+        break;
+      }
+    }
+    if (found) {
+      // right points to the one region past the last free region.
+      DCHECK_EQ(left + num_regs, right);
+      Region* first_reg = &regions_[left];
+      DCHECK(first_reg->IsFree());
+      first_reg->UnfreeLarge(time_);
+      ++num_non_free_regions_;
+      first_reg->SetTop(first_reg->Begin() + num_bytes);
+      for (size_t p = left + 1; p < right; ++p) {
+        DCHECK_LT(p, num_regions_);
+        DCHECK(regions_[p].IsFree());
+        regions_[p].UnfreeLargeTail(time_);
+        ++num_non_free_regions_;
+      }
+      *bytes_allocated = num_bytes;
+      if (usable_size != nullptr) {
+        *usable_size = num_regs * kRegionSize;
+      }
+      return reinterpret_cast<mirror::Object*>(first_reg->Begin());
+    } else {
+      // right points to the non-free region. Start with the one after it.
+      left = right + 1;
+    }
+  }
+  return nullptr;
+}
+
+}  // namespace space
+}  // namespace gc
+}  // namespace art
+
+#endif  // ART_RUNTIME_GC_SPACE_REGION_SPACE_INL_H_
diff --git a/runtime/gc/space/region_space.cc b/runtime/gc/space/region_space.cc
new file mode 100644
index 0000000000..2ecb79e7f0
--- /dev/null
+++ b/runtime/gc/space/region_space.cc
@@ -0,0 +1,412 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "bump_pointer_space.h"
+#include "bump_pointer_space-inl.h"
+#include "mirror/object-inl.h"
+#include "mirror/class-inl.h"
+#include "thread_list.h"
+
+namespace art {
+namespace gc {
+namespace space {
+
+// If a region has live objects whose size is less than this percent
+// value of the region size, evaculate the region.
+static constexpr uint kEvaculateLivePercentThreshold = 75U;
+
+RegionSpace* RegionSpace::Create(const std::string& name, size_t capacity,
+                                 uint8_t* requested_begin) {
+  capacity = RoundUp(capacity, kRegionSize);
+  std::string error_msg;
+  std::unique_ptr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), requested_begin, capacity,
+                                                       PROT_READ | PROT_WRITE, true, &error_msg));
+  if (mem_map.get() == nullptr) {
+    LOG(ERROR) << "Failed to allocate pages for alloc space (" << name << ") of size "
+        << PrettySize(capacity) << " with message " << error_msg;
+    MemMap::DumpMaps(LOG(ERROR));
+    return nullptr;
+  }
+  return new RegionSpace(name, mem_map.release());
+}
+
+RegionSpace::RegionSpace(const std::string& name, MemMap* mem_map)
+    : ContinuousMemMapAllocSpace(name, mem_map, mem_map->Begin(), mem_map->End(), mem_map->End(),
+                                 kGcRetentionPolicyAlwaysCollect),
+      region_lock_("Region lock", kRegionSpaceRegionLock), time_(1U) {
+  size_t mem_map_size = mem_map->Size();
+  CHECK_ALIGNED(mem_map_size, kRegionSize);
+  CHECK_ALIGNED(mem_map->Begin(), kRegionSize);
+  num_regions_ = mem_map_size / kRegionSize;
+  num_non_free_regions_ = 0U;
+  DCHECK_GT(num_regions_, 0U);
+  regions_.reset(new Region[num_regions_]);
+  uint8_t* region_addr = mem_map->Begin();
+  for (size_t i = 0; i < num_regions_; ++i, region_addr += kRegionSize) {
+    regions_[i] = Region(i, region_addr, region_addr + kRegionSize);
+  }
+  if (kIsDebugBuild) {
+    CHECK_EQ(regions_[0].Begin(), Begin());
+    for (size_t i = 0; i < num_regions_; ++i) {
+      CHECK(regions_[i].IsFree());
+      CHECK_EQ(static_cast<size_t>(regions_[i].End() - regions_[i].Begin()), kRegionSize);
+      if (i + 1 < num_regions_) {
+        CHECK_EQ(regions_[i].End(), regions_[i + 1].Begin());
+      }
+    }
+    CHECK_EQ(regions_[num_regions_ - 1].End(), Limit());
+  }
+  full_region_ = Region();
+  DCHECK(!full_region_.IsFree());
+  DCHECK(full_region_.IsNormal());
+  current_region_ = &full_region_;
+  evac_region_ = nullptr;
+  size_t ignored;
+  DCHECK(full_region_.Alloc(kAlignment, &ignored, nullptr) == nullptr);
+}
+
+size_t RegionSpace::FromSpaceSize() {
+  uint64_t num_regions = 0;
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (r->IsInFromSpace()) {
+      ++num_regions;
+    }
+  }
+  return num_regions * kRegionSize;
+}
+
+size_t RegionSpace::UnevacFromSpaceSize() {
+  uint64_t num_regions = 0;
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (r->IsInUnevacFromSpace()) {
+      ++num_regions;
+    }
+  }
+  return num_regions * kRegionSize;
+}
+
+size_t RegionSpace::ToSpaceSize() {
+  uint64_t num_regions = 0;
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (r->IsInToSpace()) {
+      ++num_regions;
+    }
+  }
+  return num_regions * kRegionSize;
+}
+
+inline bool RegionSpace::Region::ShouldBeEvacuated() {
+  DCHECK(state_ == kRegionToSpace || state_ == kRegionLargeToSpace);
+  // if the region was allocated after the start of the
+  // previous GC or the live ratio is below threshold, evacuate
+  // it.
+  bool result;
+  if (is_newly_allocated_) {
+    result = true;
+  } else {
+    bool is_live_percent_valid = live_bytes_ != static_cast<size_t>(-1);
+    if (is_live_percent_valid) {
+      uint live_percent = GetLivePercent();
+      if (state_ == kRegionToSpace) {
+        // Side node: live_percent == 0 does not necessarily mean
+        // there's no live objects due to rounding (there may be a
+        // few).
+        result = live_percent < kEvaculateLivePercentThreshold;
+      } else {
+        DCHECK(state_ == kRegionLargeToSpace);
+        result = live_percent == 0U;
+      }
+    } else {
+      result = false;
+    }
+  }
+  return result;
+}
+
+// Determine which regions to evacuate and mark them as
+// from-space. Mark the rest as unevacuated from-space.
+void RegionSpace::SetFromSpace(accounting::ReadBarrierTable* rb_table, bool force_evacuate_all) {
+  ++time_;
+  if (kUseTableLookupReadBarrier) {
+    DCHECK(rb_table->IsAllCleared());
+    rb_table->SetAll();
+  }
+  MutexLock mu(Thread::Current(), region_lock_);
+  size_t num_expected_large_tails = 0;
+  bool prev_large_evacuated = false;
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    RegionState state = static_cast<RegionState>(r->state_);
+    if (!r->IsFree()) {
+      DCHECK(r->IsInToSpace());
+      if (LIKELY(num_expected_large_tails == 0U)) {
+        DCHECK(state == kRegionToSpace || state == kRegionLargeToSpace);
+        bool should_evacuate = force_evacuate_all || r->ShouldBeEvacuated();
+        if (should_evacuate) {
+          r->SetAsFromSpace();
+          DCHECK(r->IsInFromSpace());
+        } else {
+          r->SetAsUnevacFromSpace();
+          DCHECK(r->IsInUnevacFromSpace());
+        }
+        if (UNLIKELY(state == kRegionLargeToSpace)) {
+          prev_large_evacuated = should_evacuate;
+          num_expected_large_tails = RoundUp(r->BytesAllocated(), kRegionSize) / kRegionSize - 1;
+          DCHECK_GT(num_expected_large_tails, 0U);
+        }
+      } else {
+        DCHECK(state == kRegionLargeTailToSpace);
+        if (prev_large_evacuated) {
+          r->SetAsFromSpace();
+          DCHECK(r->IsInFromSpace());
+        } else {
+          r->SetAsUnevacFromSpace();
+          DCHECK(r->IsInUnevacFromSpace());
+        }
+        --num_expected_large_tails;
+      }
+    } else {
+      DCHECK_EQ(num_expected_large_tails, 0U);
+      if (kUseTableLookupReadBarrier) {
+        // Clear the rb table for to-space regions.
+        rb_table->Clear(r->Begin(), r->End());
+      }
+    }
+  }
+  current_region_ = &full_region_;
+  evac_region_ = &full_region_;
+}
+
+void RegionSpace::ClearFromSpace() {
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (r->IsInFromSpace()) {
+      r->Clear();
+      --num_non_free_regions_;
+    } else if (r->IsInUnevacFromSpace()) {
+      r->SetUnevacFromSpaceAsToSpace();
+    }
+  }
+  evac_region_ = nullptr;
+}
+
+void RegionSpace::AssertAllRegionLiveBytesZeroOrCleared() {
+  if (kIsDebugBuild) {
+    MutexLock mu(Thread::Current(), region_lock_);
+    for (size_t i = 0; i < num_regions_; ++i) {
+      Region* r = &regions_[i];
+      size_t live_bytes = r->LiveBytes();
+      CHECK(live_bytes == 0U || live_bytes == static_cast<size_t>(-1)) << live_bytes;
+    }
+  }
+}
+
+void RegionSpace::LogFragmentationAllocFailure(std::ostream& os,
+                                               size_t /* failed_alloc_bytes */) {
+  size_t max_contiguous_allocation = 0;
+  MutexLock mu(Thread::Current(), region_lock_);
+  if (current_region_->End() - current_region_->Top() > 0) {
+    max_contiguous_allocation = current_region_->End() - current_region_->Top();
+  }
+  if (num_non_free_regions_ * 2 < num_regions_) {
+    // We reserve half of the regions for evaluation only. If we
+    // occupy more than half the regions, do not report the free
+    // regions as available.
+    size_t max_contiguous_free_regions = 0;
+    size_t num_contiguous_free_regions = 0;
+    bool prev_free_region = false;
+    for (size_t i = 0; i < num_regions_; ++i) {
+      Region* r = &regions_[i];
+      if (r->IsFree()) {
+        if (!prev_free_region) {
+          CHECK_EQ(num_contiguous_free_regions, 0U);
+          prev_free_region = true;
+        }
+        ++num_contiguous_free_regions;
+      } else {
+        if (prev_free_region) {
+          CHECK_NE(num_contiguous_free_regions, 0U);
+          max_contiguous_free_regions = std::max(max_contiguous_free_regions,
+                                                 num_contiguous_free_regions);
+          num_contiguous_free_regions = 0U;
+          prev_free_region = false;
+        }
+      }
+    }
+    max_contiguous_allocation = std::max(max_contiguous_allocation,
+                                         max_contiguous_free_regions * kRegionSize);
+  }
+  os << "; failed due to fragmentation (largest possible contiguous allocation "
+     <<  max_contiguous_allocation << " bytes)";
+  // Caller's job to print failed_alloc_bytes.
+}
+
+void RegionSpace::Clear() {
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (!r->IsFree()) {
+      --num_non_free_regions_;
+    }
+    r->Clear();
+  }
+  current_region_ = &full_region_;
+  evac_region_ = &full_region_;
+}
+
+void RegionSpace::Dump(std::ostream& os) const {
+  os << GetName() << " "
+      << reinterpret_cast<void*>(Begin()) << "-" << reinterpret_cast<void*>(Limit());
+}
+
+void RegionSpace::FreeLarge(mirror::Object* large_obj, size_t bytes_allocated) {
+  DCHECK(Contains(large_obj));
+  DCHECK(IsAligned<kRegionSize>(large_obj));
+  MutexLock mu(Thread::Current(), region_lock_);
+  uint8_t* begin_addr = reinterpret_cast<uint8_t*>(large_obj);
+  uint8_t* end_addr = AlignUp(reinterpret_cast<uint8_t*>(large_obj) + bytes_allocated, kRegionSize);
+  CHECK_LT(begin_addr, end_addr);
+  for (uint8_t* addr = begin_addr; addr < end_addr; addr += kRegionSize) {
+    Region* reg = RefToRegionLocked(reinterpret_cast<mirror::Object*>(addr));
+    if (addr == begin_addr) {
+      DCHECK(reg->IsLarge());
+    } else {
+      DCHECK(reg->IsLargeTail());
+    }
+    reg->Clear();
+    --num_non_free_regions_;
+  }
+  if (end_addr < Limit()) {
+    // If we aren't at the end of the space, check that the next region is not a large tail.
+    Region* following_reg = RefToRegionLocked(reinterpret_cast<mirror::Object*>(end_addr));
+    DCHECK(!following_reg->IsLargeTail());
+  }
+}
+
+void RegionSpace::DumpRegions(std::ostream& os) {
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    regions_[i].Dump(os);
+  }
+}
+
+void RegionSpace::DumpNonFreeRegions(std::ostream& os) {
+  MutexLock mu(Thread::Current(), region_lock_);
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* reg = &regions_[i];
+    if (!reg->IsFree()) {
+      reg->Dump(os);
+    }
+  }
+}
+
+void RegionSpace::RecordAlloc(mirror::Object* ref) {
+  CHECK(ref != nullptr);
+  Region* r = RefToRegion(ref);
+  reinterpret_cast<Atomic<uint64_t>*>(&r->objects_allocated_)->FetchAndAddSequentiallyConsistent(1);
+}
+
+bool RegionSpace::AllocNewTlab(Thread* self) {
+  MutexLock mu(self, region_lock_);
+  RevokeThreadLocalBuffersLocked(self);
+  // Retain sufficient free regions for full evacuation.
+  if ((num_non_free_regions_ + 1) * 2 > num_regions_) {
+    return false;
+  }
+  for (size_t i = 0; i < num_regions_; ++i) {
+    Region* r = &regions_[i];
+    if (r->IsFree()) {
+      r->Unfree(time_);
+      ++num_non_free_regions_;
+      // TODO: this is buggy. Debug it.
+      // r->SetNewlyAllocated();
+      r->SetTop(r->End());
+      r->is_a_tlab_ = true;
+      r->thread_ = self;
+      self->SetTlab(r->Begin(), r->End());
+      return true;
+    }
+  }
+  return false;
+}
+
+void RegionSpace::RevokeThreadLocalBuffers(Thread* thread) {
+  MutexLock mu(Thread::Current(), region_lock_);
+  RevokeThreadLocalBuffersLocked(thread);
+}
+
+void RegionSpace::RevokeThreadLocalBuffersLocked(Thread* thread) {
+  uint8_t* tlab_start = thread->GetTlabStart();
+  DCHECK_EQ(thread->HasTlab(), tlab_start != nullptr);
+  if (tlab_start != nullptr) {
+    DCHECK(IsAligned<kRegionSize>(tlab_start));
+    Region* r = RefToRegionLocked(reinterpret_cast<mirror::Object*>(tlab_start));
+    DCHECK(r->IsNormal());
+    DCHECK_EQ(thread->GetThreadLocalBytesAllocated(), kRegionSize);
+    r->RecordThreadLocalAllocations(thread->GetThreadLocalObjectsAllocated(),
+                                    thread->GetThreadLocalBytesAllocated());
+    r->is_a_tlab_ = false;
+    r->thread_ = nullptr;
+  }
+  thread->SetTlab(nullptr, nullptr);
+}
+
+void RegionSpace::RevokeAllThreadLocalBuffers() {
+  Thread* self = Thread::Current();
+  MutexLock mu(self, *Locks::runtime_shutdown_lock_);
+  MutexLock mu2(self, *Locks::thread_list_lock_);
+  std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
+  for (Thread* thread : thread_list) {
+    RevokeThreadLocalBuffers(thread);
+  }
+}
+
+void RegionSpace::AssertThreadLocalBuffersAreRevoked(Thread* thread) {
+  if (kIsDebugBuild) {
+    DCHECK(!thread->HasTlab());
+  }
+}
+
+void RegionSpace::AssertAllThreadLocalBuffersAreRevoked() {
+  if (kIsDebugBuild) {
+    Thread* self = Thread::Current();
+    MutexLock mu(self, *Locks::runtime_shutdown_lock_);
+    MutexLock mu2(self, *Locks::thread_list_lock_);
+    std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
+    for (Thread* thread : thread_list) {
+      AssertThreadLocalBuffersAreRevoked(thread);
+    }
+  }
+}
+
+void RegionSpace::Region::Dump(std::ostream& os) const {
+  os << "Region[" << idx_ << "]=" << reinterpret_cast<void*>(begin_) << "-" << reinterpret_cast<void*>(top_)
+     << "-" << reinterpret_cast<void*>(end_)
+     << " state=" << static_cast<uint>(state_) << " objects_allocated=" << objects_allocated_
+     << " alloc_time=" << alloc_time_ << " live_bytes=" << live_bytes_
+     << " is_newly_allocated=" << is_newly_allocated_ << " is_a_tlab=" << is_a_tlab_ << " thread=" << thread_ << "\n";
+}
+
+}  // namespace space
+}  // namespace gc
+}  // namespace art
diff --git a/runtime/gc/space/region_space.h b/runtime/gc/space/region_space.h
new file mode 100644
index 0000000000..b4a043f3ef
--- /dev/null
+++ b/runtime/gc/space/region_space.h
@@ -0,0 +1,541 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_GC_SPACE_REGION_SPACE_H_
+#define ART_RUNTIME_GC_SPACE_REGION_SPACE_H_
+
+#include "object_callbacks.h"
+#include "space.h"
+#include "gc/accounting/read_barrier_table.h"
+
+namespace art {
+namespace gc {
+namespace space {
+
+// A space that consists of equal-sized regions.
+class RegionSpace FINAL : public ContinuousMemMapAllocSpace {
+ public:
+  typedef void(*WalkCallback)(void *start, void *end, size_t num_bytes, void* callback_arg);
+
+  SpaceType GetType() const OVERRIDE {
+    return kSpaceTypeRegionSpace;
+  }
+
+  // Create a region space with the requested sizes. The requested base address is not
+  // guaranteed to be granted, if it is required, the caller should call Begin on the returned
+  // space to confirm the request was granted.
+  static RegionSpace* Create(const std::string& name, size_t capacity, uint8_t* requested_begin);
+
+  // Allocate num_bytes, returns nullptr if the space is full.
+  mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated,
+                        size_t* usable_size) OVERRIDE;
+  // Thread-unsafe allocation for when mutators are suspended, used by the semispace collector.
+  mirror::Object* AllocThreadUnsafe(Thread* self, size_t num_bytes, size_t* bytes_allocated,
+                                    size_t* usable_size)
+      OVERRIDE EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
+  // The main allocation routine.
+  template<bool kForEvac>
+  ALWAYS_INLINE mirror::Object* AllocNonvirtual(size_t num_bytes, size_t* bytes_allocated,
+                                                size_t* usable_size);
+  // Allocate/free large objects (objects that are larger than the region size.)
+  template<bool kForEvac>
+  mirror::Object* AllocLarge(size_t num_bytes, size_t* bytes_allocated, size_t* usable_size);
+  void FreeLarge(mirror::Object* large_obj, size_t bytes_allocated);
+
+  // Return the storage space required by obj.
+  size_t AllocationSize(mirror::Object* obj, size_t* usable_size) OVERRIDE
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    return AllocationSizeNonvirtual(obj, usable_size);
+  }
+  size_t AllocationSizeNonvirtual(mirror::Object* obj, size_t* usable_size)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  size_t Free(Thread*, mirror::Object*) OVERRIDE {
+    UNIMPLEMENTED(FATAL);
+    return 0;
+  }
+  size_t FreeList(Thread*, size_t, mirror::Object**) OVERRIDE {
+    UNIMPLEMENTED(FATAL);
+    return 0;
+  }
+  accounting::ContinuousSpaceBitmap* GetLiveBitmap() const OVERRIDE {
+    // No live bitmap.
+    return nullptr;
+  }
+  accounting::ContinuousSpaceBitmap* GetMarkBitmap() const OVERRIDE {
+    // No mark bitmap.
+    return nullptr;
+  }
+
+  void Clear() OVERRIDE LOCKS_EXCLUDED(region_lock_);
+
+  void Dump(std::ostream& os) const;
+  void DumpRegions(std::ostream& os);
+  void DumpNonFreeRegions(std::ostream& os);
+
+  void RevokeThreadLocalBuffers(Thread* thread) LOCKS_EXCLUDED(region_lock_);
+  void RevokeThreadLocalBuffersLocked(Thread* thread) EXCLUSIVE_LOCKS_REQUIRED(region_lock_);
+  void RevokeAllThreadLocalBuffers() LOCKS_EXCLUDED(Locks::runtime_shutdown_lock_,
+                                                    Locks::thread_list_lock_);
+  void AssertThreadLocalBuffersAreRevoked(Thread* thread) LOCKS_EXCLUDED(region_lock_);
+  void AssertAllThreadLocalBuffersAreRevoked() LOCKS_EXCLUDED(Locks::runtime_shutdown_lock_,
+                                                              Locks::thread_list_lock_);
+
+  enum SubSpaceType {
+    kAllSpaces,        // All spaces.
+    kFromSpace,        // From-space. To be evacuated.
+    kUnevacFromSpace,  // Unevacuated from-space. Not to be evacuated.
+    kToSpace,          // To-space.
+  };
+
+  template<SubSpaceType kSubSpaceType> uint64_t GetBytesAllocatedInternal();
+  template<SubSpaceType kSubSpaceType> uint64_t GetObjectsAllocatedInternal();
+  uint64_t GetBytesAllocated() {
+    return GetBytesAllocatedInternal<kAllSpaces>();
+  }
+  uint64_t GetObjectsAllocated() {
+    return GetObjectsAllocatedInternal<kAllSpaces>();
+  }
+  uint64_t GetBytesAllocatedInFromSpace() {
+    return GetBytesAllocatedInternal<kFromSpace>();
+  }
+  uint64_t GetObjectsAllocatedInFromSpace() {
+    return GetObjectsAllocatedInternal<kFromSpace>();
+  }
+  uint64_t GetBytesAllocatedInUnevacFromSpace() {
+    return GetBytesAllocatedInternal<kUnevacFromSpace>();
+  }
+  uint64_t GetObjectsAllocatedInUnevacFromSpace() {
+    return GetObjectsAllocatedInternal<kUnevacFromSpace>();
+  }
+
+  bool CanMoveObjects() const OVERRIDE {
+    return true;
+  }
+
+  bool Contains(const mirror::Object* obj) const {
+    const uint8_t* byte_obj = reinterpret_cast<const uint8_t*>(obj);
+    return byte_obj >= Begin() && byte_obj < Limit();
+  }
+
+  RegionSpace* AsRegionSpace() OVERRIDE {
+    return this;
+  }
+
+  // Go through all of the blocks and visit the continuous objects.
+  void Walk(ObjectCallback* callback, void* arg)
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    WalkInternal<false>(callback, arg);
+  }
+
+  void WalkToSpace(ObjectCallback* callback, void* arg)
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    WalkInternal<true>(callback, arg);
+  }
+
+  accounting::ContinuousSpaceBitmap::SweepCallback* GetSweepCallback() OVERRIDE {
+    return nullptr;
+  }
+  void LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) OVERRIDE
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  // Object alignment within the space.
+  static constexpr size_t kAlignment = kObjectAlignment;
+  // The region size.
+  static constexpr size_t kRegionSize = 1 * MB;
+
+  bool IsInFromSpace(mirror::Object* ref) {
+    if (HasAddress(ref)) {
+      Region* r = RefToRegionUnlocked(ref);
+      return r->IsInFromSpace();
+    }
+    return false;
+  }
+
+  bool IsInUnevacFromSpace(mirror::Object* ref) {
+    if (HasAddress(ref)) {
+      Region* r = RefToRegionUnlocked(ref);
+      return r->IsInUnevacFromSpace();
+    }
+    return false;
+  }
+
+  bool IsInToSpace(mirror::Object* ref) {
+    if (HasAddress(ref)) {
+      Region* r = RefToRegionUnlocked(ref);
+      return r->IsInToSpace();
+    }
+    return false;
+  }
+
+  void SetFromSpace(accounting::ReadBarrierTable* rb_table, bool force_evacuate_all)
+      LOCKS_EXCLUDED(region_lock_);
+
+  size_t FromSpaceSize();
+  size_t UnevacFromSpaceSize();
+  size_t ToSpaceSize();
+  void ClearFromSpace();
+
+  void AddLiveBytes(mirror::Object* ref, size_t alloc_size) {
+    Region* reg = RefToRegion(ref);
+    reg->AddLiveBytes(alloc_size);
+  }
+
+  void AssertAllRegionLiveBytesZeroOrCleared();
+
+  void RecordAlloc(mirror::Object* ref);
+  bool AllocNewTlab(Thread* self);
+
+  uint32_t Time() {
+    return time_;
+  }
+
+ private:
+  RegionSpace(const std::string& name, MemMap* mem_map);
+
+  template<bool kToSpaceOnly>
+  void WalkInternal(ObjectCallback* callback, void* arg) NO_THREAD_SAFETY_ANALYSIS;
+
+  enum RegionState {
+    kRegionFree,                      // Free region.
+    kRegionToSpace,                   // To-space region.
+    kRegionFromSpace,                 // From-space region. To be evacuated.
+    kRegionUnevacFromSpace,           // Unevacuated from-space region. Not to be evacuated.
+    kRegionLargeToSpace,              // Large (allocation larger than the region size) to-space.
+    kRegionLargeFromSpace,            // Large from-space. To be evacuated.
+    kRegionLargeUnevacFromSpace,      // Large unevacuated from-space.
+    kRegionLargeTailToSpace,          // Large tail (non-first regions of a large allocation).
+    kRegionLargeTailFromSpace,        // Large tail from-space.
+    kRegionLargeTailUnevacFromSpace,  // Large tail unevacuated from-space.
+  };
+
+  class Region {
+   public:
+    Region()
+        : idx_(static_cast<size_t>(-1)),
+          begin_(nullptr), top_(nullptr), end_(nullptr), state_(kRegionToSpace),
+          objects_allocated_(0), alloc_time_(0), live_bytes_(static_cast<size_t>(-1)),
+          is_newly_allocated_(false), is_a_tlab_(false), thread_(nullptr) {}
+
+    Region(size_t idx, uint8_t* begin, uint8_t* end)
+        : idx_(idx), begin_(begin), top_(begin), end_(end), state_(kRegionFree),
+          objects_allocated_(0), alloc_time_(0), live_bytes_(static_cast<size_t>(-1)),
+          is_newly_allocated_(false), is_a_tlab_(false), thread_(nullptr) {
+      DCHECK_LT(begin, end);
+      DCHECK_EQ(static_cast<size_t>(end - begin), kRegionSize);
+    }
+
+    void Clear() {
+      top_ = begin_;
+      state_ = kRegionFree;
+      objects_allocated_ = 0;
+      alloc_time_ = 0;
+      live_bytes_ = static_cast<size_t>(-1);
+      if (!kMadviseZeroes) {
+        memset(begin_, 0, end_ - begin_);
+      }
+      madvise(begin_, end_ - begin_, MADV_DONTNEED);
+      is_newly_allocated_ = false;
+      is_a_tlab_ = false;
+      thread_ = nullptr;
+    }
+
+    ALWAYS_INLINE mirror::Object* Alloc(size_t num_bytes, size_t* bytes_allocated,
+                                        size_t* usable_size);
+
+    bool IsFree() const {
+      bool is_free = state_ == kRegionFree;
+      if (is_free) {
+        DCHECK_EQ(begin_, top_);
+        DCHECK_EQ(objects_allocated_, 0U);
+      }
+      return is_free;
+    }
+
+    // Given a free region, declare it non-free (allocated).
+    void Unfree(uint32_t alloc_time) {
+      DCHECK(IsFree());
+      state_ = kRegionToSpace;
+      alloc_time_ = alloc_time;
+    }
+
+    void UnfreeLarge(uint32_t alloc_time) {
+      DCHECK(IsFree());
+      state_ = kRegionLargeToSpace;
+      alloc_time_ = alloc_time;
+    }
+
+    void UnfreeLargeTail(uint32_t alloc_time) {
+      DCHECK(IsFree());
+      state_ = kRegionLargeTailToSpace;
+      alloc_time_ = alloc_time;
+    }
+
+    void SetNewlyAllocated() {
+      is_newly_allocated_ = true;
+    }
+
+    // Non-large, non-large-tail.
+    bool IsNormal() const {
+      return state_ == kRegionToSpace || state_ == kRegionFromSpace ||
+          state_ == kRegionUnevacFromSpace;
+    }
+
+    bool IsLarge() const {
+      bool is_large = state_ == kRegionLargeToSpace || state_ == kRegionLargeFromSpace ||
+          state_ == kRegionLargeUnevacFromSpace;
+      if (is_large) {
+        DCHECK_LT(begin_ + 1 * MB, top_);
+      }
+      return is_large;
+    }
+
+    bool IsLargeTail() const {
+      bool is_large_tail = state_ == kRegionLargeTailToSpace ||
+          state_ == kRegionLargeTailFromSpace ||
+          state_ == kRegionLargeTailUnevacFromSpace;
+      if (is_large_tail) {
+        DCHECK_EQ(begin_, top_);
+      }
+      return is_large_tail;
+    }
+
+    size_t Idx() const {
+      return idx_;
+    }
+
+    bool IsInFromSpace() const {
+      return state_ == kRegionFromSpace || state_ == kRegionLargeFromSpace ||
+          state_ == kRegionLargeTailFromSpace;
+    }
+
+    bool IsInToSpace() const {
+      return state_ == kRegionToSpace || state_ == kRegionLargeToSpace ||
+          state_ == kRegionLargeTailToSpace;
+    }
+
+    bool IsInUnevacFromSpace() const {
+      return state_ == kRegionUnevacFromSpace || state_ == kRegionLargeUnevacFromSpace ||
+          state_ == kRegionLargeTailUnevacFromSpace;
+    }
+
+    void SetAsFromSpace() {
+      switch (state_) {
+        case kRegionToSpace:
+          state_ = kRegionFromSpace;
+          break;
+        case kRegionLargeToSpace:
+          state_ = kRegionLargeFromSpace;
+          break;
+        case kRegionLargeTailToSpace:
+          state_ = kRegionLargeTailFromSpace;
+          break;
+        default:
+          LOG(FATAL) << "Unexpected region state : " << static_cast<uint>(state_)
+                     << " idx=" << idx_;
+      }
+      live_bytes_ = static_cast<size_t>(-1);
+    }
+
+    void SetAsUnevacFromSpace() {
+      switch (state_) {
+        case kRegionToSpace:
+          state_ = kRegionUnevacFromSpace;
+          break;
+        case kRegionLargeToSpace:
+          state_ = kRegionLargeUnevacFromSpace;
+          break;
+        case kRegionLargeTailToSpace:
+          state_ = kRegionLargeTailUnevacFromSpace;
+          break;
+        default:
+          LOG(FATAL) << "Unexpected region state : " << static_cast<uint>(state_)
+                     << " idx=" << idx_;
+      }
+      live_bytes_ = 0U;
+    }
+
+    void SetUnevacFromSpaceAsToSpace() {
+      switch (state_) {
+        case kRegionUnevacFromSpace:
+          state_ = kRegionToSpace;
+          break;
+        case kRegionLargeUnevacFromSpace:
+          state_ = kRegionLargeToSpace;
+          break;
+        case kRegionLargeTailUnevacFromSpace:
+          state_ = kRegionLargeTailToSpace;
+          break;
+        default:
+          LOG(FATAL) << "Unexpected region state : " << static_cast<uint>(state_)
+                     << " idx=" << idx_;
+      }
+    }
+
+    ALWAYS_INLINE bool ShouldBeEvacuated();
+
+    void AddLiveBytes(size_t live_bytes) {
+      DCHECK(IsInUnevacFromSpace());
+      DCHECK(!IsLargeTail());
+      DCHECK_NE(live_bytes_, static_cast<size_t>(-1));
+      live_bytes_ += live_bytes;
+      DCHECK_LE(live_bytes_, BytesAllocated());
+    }
+
+    size_t LiveBytes() const {
+      return live_bytes_;
+    }
+
+    uint GetLivePercent() const {
+      DCHECK(IsInToSpace());
+      DCHECK(!IsLargeTail());
+      DCHECK_NE(live_bytes_, static_cast<size_t>(-1));
+      DCHECK_LE(live_bytes_, BytesAllocated());
+      size_t bytes_allocated = RoundUp(BytesAllocated(), kRegionSize);
+      DCHECK_GE(bytes_allocated, 0U);
+      uint result = (live_bytes_ * 100U) / bytes_allocated;
+      DCHECK_LE(result, 100U);
+      return result;
+    }
+
+    size_t BytesAllocated() const {
+      if (IsLarge()) {
+        DCHECK_LT(begin_ + kRegionSize, top_);
+        return static_cast<size_t>(top_ - begin_);
+      } else if (IsLargeTail()) {
+        DCHECK_EQ(begin_, top_);
+        return 0;
+      } else {
+        DCHECK(IsNormal()) << static_cast<uint>(state_);
+        DCHECK_LE(begin_, top_);
+        size_t bytes = static_cast<size_t>(top_ - begin_);
+        DCHECK_LE(bytes, kRegionSize);
+        return bytes;
+      }
+    }
+
+    size_t ObjectsAllocated() const {
+      if (IsLarge()) {
+        DCHECK_LT(begin_ + 1 * MB, top_);
+        DCHECK_EQ(objects_allocated_, 0U);
+        return 1;
+      } else if (IsLargeTail()) {
+        DCHECK_EQ(begin_, top_);
+        DCHECK_EQ(objects_allocated_, 0U);
+        return 0;
+      } else {
+        DCHECK(IsNormal()) << static_cast<uint>(state_);
+        return objects_allocated_;
+      }
+    }
+
+    uint8_t* Begin() const {
+      return begin_;
+    }
+
+    uint8_t* Top() const {
+      return top_;
+    }
+
+    void SetTop(uint8_t* new_top) {
+      top_ = new_top;
+    }
+
+    uint8_t* End() const {
+      return end_;
+    }
+
+    bool Contains(mirror::Object* ref) const {
+      return begin_ <= reinterpret_cast<uint8_t*>(ref) && reinterpret_cast<uint8_t*>(ref) < end_;
+    }
+
+    void Dump(std::ostream& os) const;
+
+    void RecordThreadLocalAllocations(size_t num_objects, size_t num_bytes) {
+      DCHECK(IsNormal());
+      DCHECK_EQ(objects_allocated_, 0U);
+      DCHECK_EQ(top_, end_);
+      objects_allocated_ = num_objects;
+      top_ = begin_ + num_bytes;
+      DCHECK_EQ(top_, end_);
+    }
+
+   private:
+    size_t idx_;                   // The region's index in the region space.
+    uint8_t* begin_;               // The begin address of the region.
+    // Can't use Atomic<uint8_t*> as Atomic's copy operator is implicitly deleted.
+    uint8_t* top_;                 // The current position of the allocation.
+    uint8_t* end_;                 // The end address of the region.
+    uint8_t state_;                // The region state (see RegionState).
+    uint64_t objects_allocated_;   // The number of objects allocated.
+    uint32_t alloc_time_;          // The allocation time of the region.
+    size_t live_bytes_;            // The live bytes. Used to compute the live percent.
+    bool is_newly_allocated_;      // True if it's allocated after the last collection.
+    bool is_a_tlab_;               // True if it's a tlab.
+    Thread* thread_;               // The owning thread if it's a tlab.
+
+    friend class RegionSpace;
+  };
+
+  Region* RefToRegion(mirror::Object* ref) LOCKS_EXCLUDED(region_lock_) {
+    MutexLock mu(Thread::Current(), region_lock_);
+    return RefToRegionLocked(ref);
+  }
+
+  Region* RefToRegionUnlocked(mirror::Object* ref) NO_THREAD_SAFETY_ANALYSIS {
+    // For a performance reason (this is frequently called via
+    // IsInFromSpace() etc.) we avoid taking a lock here. Note that
+    // since we only change a region from to-space to from-space only
+    // during a pause (SetFromSpace()) and from from-space to free
+    // (after GC is done) as long as ref is a valid reference into an
+    // allocated region, it's safe to access the region state without
+    // the lock.
+    return RefToRegionLocked(ref);
+  }
+
+  Region* RefToRegionLocked(mirror::Object* ref) EXCLUSIVE_LOCKS_REQUIRED(region_lock_) {
+    DCHECK(HasAddress(ref));
+    uintptr_t offset = reinterpret_cast<uintptr_t>(ref) - reinterpret_cast<uintptr_t>(Begin());
+    size_t reg_idx = offset / kRegionSize;
+    DCHECK_LT(reg_idx, num_regions_);
+    Region* reg = &regions_[reg_idx];
+    DCHECK_EQ(reg->Idx(), reg_idx);
+    DCHECK(reg->Contains(ref));
+    return reg;
+  }
+
+  mirror::Object* GetNextObject(mirror::Object* obj)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  Mutex region_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+
+  uint32_t time_;                  // The time as the number of collections since the startup.
+  size_t num_regions_;             // The number of regions in this space.
+  size_t num_non_free_regions_;    // The number of non-free regions in this space.
+  std::unique_ptr<Region[]> regions_ GUARDED_BY(region_lock_);
+                                   // The pointer to the region array.
+  Region* current_region_;         // The region that's being allocated currently.
+  Region* evac_region_;            // The region that's being evacuated to currently.
+  Region full_region_;             // The dummy/sentinel region that looks full.
+
+  DISALLOW_COPY_AND_ASSIGN(RegionSpace);
+};
+
+}  // namespace space
+}  // namespace gc
+}  // namespace art
+
+#endif  // ART_RUNTIME_GC_SPACE_REGION_SPACE_H_
diff --git a/runtime/gc/space/space.cc b/runtime/gc/space/space.cc
index 486d79ad1b..a2e2c1c7fb 100644
--- a/runtime/gc/space/space.cc
+++ b/runtime/gc/space/space.cc
@@ -58,6 +58,11 @@ BumpPointerSpace* Space::AsBumpPointerSpace() {
   UNREACHABLE();
 }
 
+RegionSpace* Space::AsRegionSpace() {
+  LOG(FATAL) << "Unreachable";
+  return nullptr;
+}
+
 AllocSpace* Space::AsAllocSpace() {
   UNIMPLEMENTED(FATAL) << "Unreachable";
   UNREACHABLE();
diff --git a/runtime/gc/space/space.h b/runtime/gc/space/space.h
index 860a4c9f39..d24650b60d 100644
--- a/runtime/gc/space/space.h
+++ b/runtime/gc/space/space.h
@@ -50,6 +50,7 @@ class DlMallocSpace;
 class RosAllocSpace;
 class ImageSpace;
 class LargeObjectSpace;
+class RegionSpace;
 class ZygoteSpace;
 
 static constexpr bool kDebugSpaces = kIsDebugBuild;
@@ -72,6 +73,7 @@ enum SpaceType {
   kSpaceTypeZygoteSpace,
   kSpaceTypeBumpPointerSpace,
   kSpaceTypeLargeObjectSpace,
+  kSpaceTypeRegionSpace,
 };
 std::ostream& operator<<(std::ostream& os, const SpaceType& space_type);
 
@@ -132,6 +134,11 @@ class Space {
   }
   virtual BumpPointerSpace* AsBumpPointerSpace();
 
+  bool IsRegionSpace() const {
+    return GetType() == kSpaceTypeRegionSpace;
+  }
+  virtual RegionSpace* AsRegionSpace();
+
   // Does this space hold large objects and implement the large object space abstraction?
   bool IsLargeObjectSpace() const {
     return GetType() == kSpaceTypeLargeObjectSpace;