From be73e57308680382efd1e60fa03ac1eb5abcc9c7 Mon Sep 17 00:00:00 2001
From: Andreas Gampe <agampe@google.com>
Date: Thu, 3 Apr 2014 10:46:42 -0700
Subject: [PATCH] Fix off-by-1 error in new SpaceBitmap

Do not visit_end in the VisitMarkedRange code.

Change-Id: Iaf02788509b21a102cd1c0e2db3cbd09d0522bfa
---
 runtime/gc/accounting/space_bitmap-inl.h   | 19 +++++++-
 runtime/gc/accounting/space_bitmap.h       |  3 ++
 runtime/gc/accounting/space_bitmap_test.cc | 73 ++++++++++++++++++++++++++++++
 3 files changed, 93 insertions(+), 2 deletions(-)

diff --git a/runtime/gc/accounting/space_bitmap-inl.h b/runtime/gc/accounting/space_bitmap-inl.h
index 0fbd27c14..880ff1f74 100644
--- a/runtime/gc/accounting/space_bitmap-inl.h
+++ b/runtime/gc/accounting/space_bitmap-inl.h
@@ -58,6 +58,14 @@ template <typename Visitor>
 void SpaceBitmap::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end,
                                    const Visitor& visitor) const {
   DCHECK_LT(visit_begin, visit_end);
+#if 0
+  for (uintptr_t i = visit_begin; i < visit_end; i += kAlignment) {
+    mirror::Object* obj = reinterpret_cast<mirror::Object*>(i);
+    if (Test(obj)) {
+      visitor(obj);
+    }
+  }
+#else
   DCHECK_LE(heap_begin_, visit_begin);
   DCHECK_LE(visit_end, HeapLimit());
 
@@ -114,14 +122,20 @@ void SpaceBitmap::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end,
     }
 
     // Right edge is unique.
-    right_edge = bitmap_begin_[index_end];
+    // But maybe we don't have anything to do: visit_end starts in a new word...
+    if (bit_end == 0) {
+      // Do not read memory, as it could be after the end of the bitmap.
+      right_edge = 0;
+    } else {
+      right_edge = bitmap_begin_[index_end];
+    }
   } else {
     // Right edge = left edge.
     right_edge = left_edge;
   }
 
   // Right edge handling.
-  right_edge &= ((static_cast<uword>(1) << bit_end) - 1) | (static_cast<uword>(1) << bit_end);
+  right_edge &= ((static_cast<uword>(1) << bit_end) - 1);
   if (right_edge != 0) {
     const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
     do {
@@ -131,6 +145,7 @@ void SpaceBitmap::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end,
       right_edge ^= (static_cast<uword>(1)) << shift;
     } while (right_edge != 0);
   }
+#endif
 }
 
 inline bool SpaceBitmap::Modify(const mirror::Object* obj, bool do_set) {
diff --git a/runtime/gc/accounting/space_bitmap.h b/runtime/gc/accounting/space_bitmap.h
index aa24b0324..a88f3e475 100644
--- a/runtime/gc/accounting/space_bitmap.h
+++ b/runtime/gc/accounting/space_bitmap.h
@@ -123,6 +123,9 @@ class SpaceBitmap {
     }
   }
 
+  /**
+   * Visit the live objects in the range [visit_begin, visit_end).
+   */
   template <typename Visitor>
   void VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
diff --git a/runtime/gc/accounting/space_bitmap_test.cc b/runtime/gc/accounting/space_bitmap_test.cc
index ba4e2ac8f..68994a8ba 100644
--- a/runtime/gc/accounting/space_bitmap_test.cc
+++ b/runtime/gc/accounting/space_bitmap_test.cc
@@ -86,6 +86,79 @@ TEST_F(SpaceBitmapTest, ScanRange) {
   }
 }
 
+class SimpleCounter {
+ public:
+  explicit SimpleCounter(size_t* counter) : count_(counter) {}
+
+  void operator()(mirror::Object* obj) const {
+    (*count_)++;
+  }
+
+  size_t* count_;
+};
+
+class RandGen {
+ public:
+  explicit RandGen(uint32_t seed) : val_(seed) {}
+
+  uint32_t next() {
+    val_ = val_ * 48271 % 2147483647;
+    return val_;
+  }
+
+  uint32_t val_;
+};
+
+void compat_test() NO_THREAD_SAFETY_ANALYSIS {
+  byte* heap_begin = reinterpret_cast<byte*>(0x10000000);
+  size_t heap_capacity = 16 * MB;
+
+  // Seed with 0x1234 for reproducability.
+  RandGen r(0x1234);
+
+
+  for (int i = 0; i < 5 ; ++i) {
+    UniquePtr<SpaceBitmap> space_bitmap(SpaceBitmap::Create("test bitmap",
+                                                            heap_begin, heap_capacity));
+
+    for (int j = 0; j < 10000; ++j) {
+      size_t offset = (r.next() % heap_capacity) & ~(0x7);
+      bool set = r.next() % 2 == 1;
+
+      if (set) {
+        space_bitmap->Set(reinterpret_cast<mirror::Object*>(heap_begin + offset));
+      } else {
+        space_bitmap->Clear(reinterpret_cast<mirror::Object*>(heap_begin + offset));
+      }
+    }
+
+    for (int j = 0; j < 50; ++j) {
+      size_t count = 0;
+      SimpleCounter c(&count);
+
+      size_t offset = (r.next() % heap_capacity) & ~(0x7);
+      size_t remain = heap_capacity - offset;
+      size_t end = offset + ((r.next() % (remain + 1)) & ~(0x7));
+
+      space_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(heap_begin) + offset,
+                                     reinterpret_cast<uintptr_t>(heap_begin) + end, c);
+
+      size_t manual = 0;
+      for (uintptr_t k = offset; k < end; k += kObjectAlignment) {
+        if (space_bitmap->Test(reinterpret_cast<mirror::Object*>(heap_begin + k))) {
+          manual++;
+        }
+      }
+
+      EXPECT_EQ(count, manual);
+    }
+  }
+}
+
+TEST_F(SpaceBitmapTest, Visitor) {
+  compat_test();
+}
+
 }  // namespace accounting
 }  // namespace gc
 }  // namespace art
-- 
2.11.0