Replace ObjectSet with LargeObjectBitmap.

Speeds up large object marking since large objects no longer required
a lock. Changed the GCs to use the heap bitmap for marking objects
which aren't in the fast path. This eliminates the need for a
MarkLargeObject function.

Maps before (10 GC iterations):
Mean partial time: 180ms
Mean sticky time: 151ms

Maps after:
Mean partial time: 161ms
Mean sticky time: 101ms

Note: the GC durations are long due to recent ergonomic changes and
because the fast bulk free hasn't yet been enabled. Over 50% of the
GC time is spent in RosAllocSpace::FreeList.

Bug: 13571028

Change-Id: Id8f94718aeaa13052672ccbae1e8edf77d653f62

1 files changed, 45 insertions, 25 deletions

diff --git a/runtime/gc/accounting/heap_bitmap-inl.h b/runtime/gc/accounting/heap_bitmap-inl.h
index ed7b427a5f..c67542f484 100644
--- a/runtime/gc/accounting/heap_bitmap-inl.h
+++ b/runtime/gc/accounting/heap_bitmap-inl.h
@@ -30,9 +30,8 @@ inline void HeapBitmap::Visit(const Visitor& visitor) {
   for (const auto& bitmap : continuous_space_bitmaps_) {
     bitmap->VisitMarkedRange(bitmap->HeapBegin(), bitmap->HeapLimit(), visitor);
   }
-  DCHECK(!discontinuous_space_sets_.empty());
-  for (const auto& space_set : discontinuous_space_sets_) {
-    space_set->Visit(visitor);
+  for (const auto& bitmap : large_object_bitmaps_) {
+    bitmap->VisitMarkedRange(bitmap->HeapBegin(), bitmap->HeapLimit(), visitor);
   }
 }
 
@@ -40,46 +39,67 @@ inline bool HeapBitmap::Test(const mirror::Object* obj) {
   ContinuousSpaceBitmap* bitmap = GetContinuousSpaceBitmap(obj);
   if (LIKELY(bitmap != nullptr)) {
     return bitmap->Test(obj);
-  } else {
-    return GetDiscontinuousSpaceObjectSet(obj) != nullptr;
   }
+  for (const auto& bitmap : large_object_bitmaps_) {
+    if (LIKELY(bitmap->HasAddress(obj))) {
+      return bitmap->Test(obj);
+    }
+  }
+  LOG(FATAL) << "Invalid object " << obj;
+  return false;
 }
 
 inline void HeapBitmap::Clear(const mirror::Object* obj) {
   ContinuousSpaceBitmap* bitmap = GetContinuousSpaceBitmap(obj);
   if (LIKELY(bitmap != nullptr)) {
     bitmap->Clear(obj);
-  } else {
-    ObjectSet* set = GetDiscontinuousSpaceObjectSet(obj);
-    DCHECK(set != NULL);
-    set->Clear(obj);
+    return;
+  }
+  for (const auto& bitmap : large_object_bitmaps_) {
+    if (LIKELY(bitmap->HasAddress(obj))) {
+      bitmap->Clear(obj);
+    }
   }
+  LOG(FATAL) << "Invalid object " << obj;
 }
 
-inline void HeapBitmap::Set(const mirror::Object* obj) {
+template<typename LargeObjectSetVisitor>
+inline bool HeapBitmap::Set(const mirror::Object* obj, const LargeObjectSetVisitor& visitor) {
   ContinuousSpaceBitmap* bitmap = GetContinuousSpaceBitmap(obj);
-  if (LIKELY(bitmap != NULL)) {
-    bitmap->Set(obj);
-  } else {
-    ObjectSet* set = GetDiscontinuousSpaceObjectSet(obj);
-    DCHECK(set != NULL);
-    set->Set(obj);
+  if (LIKELY(bitmap != nullptr)) {
+    return bitmap->Set(obj);
+  }
+  visitor(obj);
+  for (const auto& bitmap : large_object_bitmaps_) {
+    if (LIKELY(bitmap->HasAddress(obj))) {
+      return bitmap->Set(obj);
+    }
   }
+  LOG(FATAL) << "Invalid object " << obj;
+  return false;
 }
 
-inline ContinuousSpaceBitmap* HeapBitmap::GetContinuousSpaceBitmap(const mirror::Object* obj) const {
-  for (const auto& bitmap : continuous_space_bitmaps_) {
-    if (bitmap->HasAddress(obj)) {
-      return bitmap;
+template<typename LargeObjectSetVisitor>
+inline bool HeapBitmap::AtomicTestAndSet(const mirror::Object* obj,
+                                         const LargeObjectSetVisitor& visitor) {
+  ContinuousSpaceBitmap* bitmap = GetContinuousSpaceBitmap(obj);
+  if (LIKELY(bitmap != nullptr)) {
+    return bitmap->AtomicTestAndSet(obj);
+  }
+  visitor(obj);
+  for (const auto& bitmap : large_object_bitmaps_) {
+    if (LIKELY(bitmap->HasAddress(obj))) {
+      return bitmap->AtomicTestAndSet(obj);
     }
   }
-  return nullptr;
+  LOG(FATAL) << "Invalid object " << obj;
+  return false;
 }
 
-inline ObjectSet* HeapBitmap::GetDiscontinuousSpaceObjectSet(const mirror::Object* obj) const {
-  for (const auto& space_set : discontinuous_space_sets_) {
-    if (space_set->Test(obj)) {
-      return space_set;
+inline ContinuousSpaceBitmap* HeapBitmap::GetContinuousSpaceBitmap(const mirror::Object* obj) const {
+  for (const auto& bitmap : continuous_space_bitmaps_) {
+    if (bitmap->HasAddress(obj)) {
+      return bitmap;
     }
   }
   return nullptr;