(Experimental) Add Brooks pointers.

This feature is disabled by default.

Verified that the Brooks pointers are installed correctly by using the
CMS/SS collectors.

Change-Id: Ia9be9814ab6e29169ac85edc4792ce8c81d552a9

13 files changed, 171 insertions, 1 deletions

diff --git a/runtime/asm_support.h b/runtime/asm_support.h
index 4c42099..0c1a72a 100644
--- a/runtime/asm_support.h
+++ b/runtime/asm_support.h
@@ -17,6 +17,8 @@
 #ifndef ART_RUNTIME_ASM_SUPPORT_H_
 #define ART_RUNTIME_ASM_SUPPORT_H_
 
+#include "brooks_pointer.h"
+
 // Value loaded into rSUSPEND for quick. When this value is counted down to zero we do a suspend
 // check.
 #define SUSPEND_CHECK_INTERVAL (1000)
@@ -25,6 +27,8 @@
 #define CLASS_OFFSET 0
 #define LOCK_WORD_OFFSET 4
 
+#ifndef USE_BROOKS_POINTER
+
 // Offsets within java.lang.Class.
 #define CLASS_COMPONENT_TYPE_OFFSET 12
 
@@ -43,4 +47,26 @@
 #define METHOD_PORTABLE_CODE_OFFSET 40
 #define METHOD_QUICK_CODE_OFFSET 48
 
+#else
+
+// Offsets within java.lang.Class.
+#define CLASS_COMPONENT_TYPE_OFFSET 20
+
+// Array offsets.
+#define ARRAY_LENGTH_OFFSET 16
+#define OBJECT_ARRAY_DATA_OFFSET 20
+
+// Offsets within java.lang.String.
+#define STRING_VALUE_OFFSET 16
+#define STRING_COUNT_OFFSET 20
+#define STRING_OFFSET_OFFSET 28
+#define STRING_DATA_OFFSET 20
+
+// Offsets within java.lang.Method.
+#define METHOD_DEX_CACHE_METHODS_OFFSET 20
+#define METHOD_PORTABLE_CODE_OFFSET 48
+#define METHOD_QUICK_CODE_OFFSET 56
+
+#endif
+
 #endif  // ART_RUNTIME_ASM_SUPPORT_H_
diff --git a/runtime/brooks_pointer.h b/runtime/brooks_pointer.h
new file mode 100644
index 0000000..3dac6e9
--- /dev/null
+++ b/runtime/brooks_pointer.h
@@ -0,0 +1,27 @@
+/*
+ * 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_BROOKS_POINTER_H_
+#define ART_RUNTIME_BROOKS_POINTER_H_
+
+// This is in a separate file (from globals.h) because asm_support.h
+// (a C header, not C++) can't include globals.h.
+
+// Uncomment this and the two fields in Object.java (libcore) to
+// enable brooks pointers.
+// #define USE_BROOKS_POINTER
+
+#endif  // ART_RUNTIME_BROOKS_POINTER_H_
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 69d957f..ff6f9de 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -205,6 +205,9 @@ void ClassLinker::InitFromCompiler(const std::vector<const DexFile*>& boot_class
   CHECK(java_lang_Class.get() != NULL);
   mirror::Class::SetClassClass(java_lang_Class.get());
   java_lang_Class->SetClass(java_lang_Class.get());
+  if (kUseBrooksPointer) {
+    java_lang_Class->AssertSelfBrooksPointer();
+  }
   java_lang_Class->SetClassSize(sizeof(mirror::ClassClass));
   heap->DecrementDisableMovingGC(self);
   // AllocClass(mirror::Class*) can now be used
@@ -1744,6 +1747,9 @@ void ClassLinker::LoadClass(const DexFile& dex_file,
   CHECK(descriptor != NULL);
 
   klass->SetClass(GetClassRoot(kJavaLangClass));
+  if (kUseBrooksPointer) {
+    klass->AssertSelfBrooksPointer();
+  }
   uint32_t access_flags = dex_class_def.access_flags_;
   // Make sure that none of our runtime-only flags are set.
   CHECK_EQ(access_flags & ~kAccJavaFlagsMask, 0U);
diff --git a/runtime/class_linker_test.cc b/runtime/class_linker_test.cc
index d6a67cc..0cd8e71 100644
--- a/runtime/class_linker_test.cc
+++ b/runtime/class_linker_test.cc
@@ -451,6 +451,10 @@ struct ObjectOffsets : public CheckOffsets<mirror::Object> {
 
     // alphabetical 32-bit
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(mirror::Object, monitor_), "shadow$_monitor_"));
+#ifdef USE_BROOKS_POINTER
+    offsets.push_back(CheckOffset(OFFSETOF_MEMBER(mirror::Object, x_brooks_ptr_), "shadow$_x_brooks_ptr_"));
+    offsets.push_back(CheckOffset(OFFSETOF_MEMBER(mirror::Object, x_padding_), "shadow$_x_padding_"));
+#endif
   };
 };
 
@@ -705,11 +709,21 @@ TEST_F(ClassLinkerTest, FindClass) {
   EXPECT_FALSE(JavaLangObject->IsSynthetic());
   EXPECT_EQ(2U, JavaLangObject->NumDirectMethods());
   EXPECT_EQ(11U, JavaLangObject->NumVirtualMethods());
-  EXPECT_EQ(2U, JavaLangObject->NumInstanceFields());
+  if (!kUseBrooksPointer) {
+    EXPECT_EQ(2U, JavaLangObject->NumInstanceFields());
+  } else {
+    EXPECT_EQ(4U, JavaLangObject->NumInstanceFields());
+  }
   FieldHelper fh(JavaLangObject->GetInstanceField(0));
   EXPECT_STREQ(fh.GetName(), "shadow$_klass_");
   fh.ChangeField(JavaLangObject->GetInstanceField(1));
   EXPECT_STREQ(fh.GetName(), "shadow$_monitor_");
+  if (kUseBrooksPointer) {
+    fh.ChangeField(JavaLangObject->GetInstanceField(2));
+    EXPECT_STREQ(fh.GetName(), "shadow$_x_brooks_ptr_");
+    fh.ChangeField(JavaLangObject->GetInstanceField(3));
+    EXPECT_STREQ(fh.GetName(), "shadow$_x_padding_");
+  }
 
   EXPECT_EQ(0U, JavaLangObject->NumStaticFields());
   EXPECT_EQ(0U, kh.NumDirectInterfaces());
diff --git a/runtime/gc/collector/mark_sweep.cc b/runtime/gc/collector/mark_sweep.cc
index cc34689..736dcb1 100644
--- a/runtime/gc/collector/mark_sweep.cc
+++ b/runtime/gc/collector/mark_sweep.cc
@@ -439,6 +439,12 @@ mirror::Object* MarkSweep::MarkObjectCallback(mirror::Object* obj, void* arg) {
 
 inline void MarkSweep::UnMarkObjectNonNull(const Object* obj) {
   DCHECK(!IsImmune(obj));
+
+  if (kUseBrooksPointer) {
+    // Verify all the objects have the correct Brooks pointer installed.
+    obj->AssertSelfBrooksPointer();
+  }
+
   // Try to take advantage of locality of references within a space, failing this find the space
   // the hard way.
   accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_;
@@ -459,6 +465,11 @@ inline void MarkSweep::UnMarkObjectNonNull(const Object* obj) {
 inline void MarkSweep::MarkObjectNonNull(const Object* obj) {
   DCHECK(obj != NULL);
 
+  if (kUseBrooksPointer) {
+    // Verify all the objects have the correct Brooks pointer installed.
+    obj->AssertSelfBrooksPointer();
+  }
+
   if (IsImmune(obj)) {
     DCHECK(IsMarked(obj));
     return;
@@ -521,6 +532,11 @@ bool MarkSweep::MarkLargeObject(const Object* obj, bool set) {
 inline bool MarkSweep::MarkObjectParallel(const Object* obj) {
   DCHECK(obj != NULL);
 
+  if (kUseBrooksPointer) {
+    // Verify all the objects have the correct Brooks pointer installed.
+    obj->AssertSelfBrooksPointer();
+  }
+
   if (IsImmune(obj)) {
     DCHECK(IsMarked(obj));
     return false;
diff --git a/runtime/gc/collector/semi_space.cc b/runtime/gc/collector/semi_space.cc
index fe8c253..d639db5 100644
--- a/runtime/gc/collector/semi_space.cc
+++ b/runtime/gc/collector/semi_space.cc
@@ -517,6 +517,12 @@ mirror::Object* SemiSpace::MarkNonForwardedObject(mirror::Object* obj) {
   // references.
   saved_bytes_ +=
       CopyAvoidingDirtyingPages(reinterpret_cast<void*>(forward_address), obj, object_size);
+  if (kUseBrooksPointer) {
+    obj->AssertSelfBrooksPointer();
+    DCHECK_EQ(forward_address->GetBrooksPointer(), obj);
+    forward_address->SetBrooksPointer(forward_address);
+    forward_address->AssertSelfBrooksPointer();
+  }
   if (to_space_live_bitmap_ != nullptr) {
     to_space_live_bitmap_->Set(forward_address);
   }
@@ -529,6 +535,12 @@ mirror::Object* SemiSpace::MarkNonForwardedObject(mirror::Object* obj) {
 // the to-space and have their forward address updated. Objects which have been newly marked are
 // pushed on the mark stack.
 Object* SemiSpace::MarkObject(Object* obj) {
+  if (kUseBrooksPointer) {
+    // Verify all the objects have the correct forward pointer installed.
+    if (obj != nullptr) {
+      obj->AssertSelfBrooksPointer();
+    }
+  }
   Object* forward_address = obj;
   if (obj != nullptr && !IsImmune(obj)) {
     if (from_space_->HasAddress(obj)) {
diff --git a/runtime/gc/heap-inl.h b/runtime/gc/heap-inl.h
index 3d591f0..2e47a02 100644
--- a/runtime/gc/heap-inl.h
+++ b/runtime/gc/heap-inl.h
@@ -65,6 +65,10 @@ inline mirror::Object* Heap::AllocObjectWithAllocator(Thread* self, mirror::Clas
     }
   }
   obj->SetClass(klass);
+  if (kUseBrooksPointer) {
+    obj->SetBrooksPointer(obj);
+    obj->AssertSelfBrooksPointer();
+  }
   pre_fence_visitor(obj);
   DCHECK_GT(bytes_allocated, 0u);
   const size_t new_num_bytes_allocated =
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 58db7a8..4435d98 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -1402,6 +1402,12 @@ class ZygoteCompactingCollector : public collector::SemiSpace {
     }
     // Copy the object over to its new location.
     memcpy(reinterpret_cast<void*>(forward_address), obj, object_size);
+    if (kUseBrooksPointer) {
+      obj->AssertSelfBrooksPointer();
+      DCHECK_EQ(forward_address->GetBrooksPointer(), obj);
+      forward_address->SetBrooksPointer(forward_address);
+      forward_address->AssertSelfBrooksPointer();
+    }
     return forward_address;
   }
 };
diff --git a/runtime/gc/space/image_space.cc b/runtime/gc/space/image_space.cc
index 12c5451..76c4d25 100644
--- a/runtime/gc/space/image_space.cc
+++ b/runtime/gc/space/image_space.cc
@@ -133,6 +133,11 @@ void ImageSpace::VerifyImageAllocations() {
     mirror::Object* obj = reinterpret_cast<mirror::Object*>(current);
     CHECK(live_bitmap_->Test(obj));
     CHECK(obj->GetClass() != nullptr) << "Image object at address " << obj << " has null class";
+    if (kUseBrooksPointer) {
+      CHECK(obj->GetBrooksPointer() == obj)
+          << "Bad Brooks pointer: obj=" << reinterpret_cast<void*>(obj)
+          << " brooks_ptr=" << reinterpret_cast<void*>(obj->GetBrooksPointer());
+    }
     current += RoundUp(obj->SizeOf(), kObjectAlignment);
   }
 }
diff --git a/runtime/gc/space/space_test.h b/runtime/gc/space/space_test.h
index 093967e..41077f3 100644
--- a/runtime/gc/space/space_test.h
+++ b/runtime/gc/space/space_test.h
@@ -49,6 +49,9 @@ class SpaceTest : public CommonTest {
                                                                                       null_loader);
     EXPECT_TRUE(byte_array_class != nullptr);
     o->SetClass(byte_array_class);
+    if (kUseBrooksPointer) {
+      o->SetBrooksPointer(o.get());
+    }
     mirror::Array* arr = o->AsArray<kVerifyNone>();
     size_t header_size = SizeOfZeroLengthByteArray();
     int32_t length = size - header_size;
diff --git a/runtime/globals.h b/runtime/globals.h
index 8c3ae56..83e3028 100644
--- a/runtime/globals.h
+++ b/runtime/globals.h
@@ -19,6 +19,7 @@
 
 #include <stddef.h>
 #include <stdint.h>
+#include "brooks_pointer.h"
 
 namespace art {
 
@@ -92,6 +93,12 @@ static constexpr bool kMovingMethods = false;
 // code, if possible.
 static constexpr bool kEmbedClassInCode = true;
 
+#ifdef USE_BROOKS_POINTER
+static constexpr bool kUseBrooksPointer = true;
+#else
+static constexpr bool kUseBrooksPointer = false;
+#endif
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_GLOBALS_H_
diff --git a/runtime/mirror/object-inl.h b/runtime/mirror/object-inl.h
index df8104d..478cc36 100644
--- a/runtime/mirror/object-inl.h
+++ b/runtime/mirror/object-inl.h
@@ -92,6 +92,38 @@ inline void Object::Wait(Thread* self, int64_t ms, int32_t ns) {
   Monitor::Wait(self, this, ms, ns, true, kTimedWaiting);
 }
 
+inline Object* Object::GetBrooksPointer() {
+#ifdef USE_BROOKS_POINTER
+  DCHECK(kUseBrooksPointer);
+  return GetFieldObject<Object, kVerifyNone>(OFFSET_OF_OBJECT_MEMBER(Object, x_brooks_ptr_), false);
+#else
+  LOG(FATAL) << "Unreachable";
+  return nullptr;
+#endif
+}
+
+inline void Object::SetBrooksPointer(Object* brooks_pointer) {
+#ifdef USE_BROOKS_POINTER
+  DCHECK(kUseBrooksPointer);
+  // We don't mark the card as this occurs as part of object allocation. Not all objects have
+  // backing cards, such as large objects.
+  SetFieldObjectWithoutWriteBarrier<false, false, kVerifyNone>(
+      OFFSET_OF_OBJECT_MEMBER(Object, x_brooks_ptr_), brooks_pointer, false);
+#else
+  LOG(FATAL) << "Unreachable";
+#endif
+}
+
+inline void Object::AssertSelfBrooksPointer() const {
+#ifdef USE_BROOKS_POINTER
+  DCHECK(kUseBrooksPointer);
+  Object* obj = const_cast<Object*>(this);
+  DCHECK_EQ(obj, obj->GetBrooksPointer());
+#else
+  LOG(FATAL) << "Unreachable";
+#endif
+}
+
 template<VerifyObjectFlags kVerifyFlags>
 inline bool Object::VerifierInstanceOf(Class* klass) {
   DCHECK(klass != NULL);
diff --git a/runtime/mirror/object.h b/runtime/mirror/object.h
index 7487dd2..ded4e0a 100644
--- a/runtime/mirror/object.h
+++ b/runtime/mirror/object.h
@@ -76,6 +76,10 @@ class MANAGED Object {
   template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags>
   void SetClass(Class* new_klass) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
+  Object* GetBrooksPointer() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void SetBrooksPointer(Object* brooks_pointer) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void AssertSelfBrooksPointer() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
   // The verifier treats all interfaces as java.lang.Object and relies on runtime checks in
   // invoke-interface to detect incompatible interface types.
   template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags>
@@ -260,6 +264,14 @@ class MANAGED Object {
   // Monitor and hash code information.
   uint32_t monitor_;
 
+#ifdef USE_BROOKS_POINTER
+  // Note names use a 'x' prefix and the x_brooks_ptr_ is of type int
+  // instead of Object to go with the alphabetical/by-type field order
+  // on the Java side.
+  uint32_t x_brooks_ptr_;  // For the Brooks pointer.
+  uint32_t x_padding_;     // For 8-byte alignment. TODO: get rid of this.
+#endif
+
   friend class art::ImageWriter;
   friend class art::Monitor;
   friend struct art::ObjectOffsets;  // for verifying offset information