Fix race in root marking.

There was a race which caused the class linker / intern table to not
become dirty after adding a root. We now guard the is dirty flag by
the corresponding locks to prevent this from occuring. This was
causing roots to be occasionally missed.

Also fixes the bug where we occasionally scan more cards than
needed.

Bug: 10626133

Change-Id: I0f6e72d92035ff463954d66988ef610ea0df61be

7 files changed, 41 insertions, 47 deletions

diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 37b62ad..0773a8d 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -192,7 +192,8 @@ ClassLinker::ClassLinker(InternTable* intern_table)
       class_roots_(NULL),
       array_iftable_(NULL),
       init_done_(false),
-      is_dirty_(false),
+      dex_caches_dirty_(false),
+      class_table_dirty_(false),
       intern_table_(intern_table),
       portable_resolution_trampoline_(NULL),
       quick_resolution_trampoline_(NULL) {
@@ -1088,20 +1089,30 @@ void ClassLinker::InitFromImage() {
 // Keep in sync with InitCallback. Anything we visit, we need to
 // reinit references to when reinitializing a ClassLinker from a
 // mapped image.
-void ClassLinker::VisitRoots(RootVisitor* visitor, void* arg, bool clean_dirty) {
+void ClassLinker::VisitRoots(RootVisitor* visitor, void* arg, bool only_dirty, bool clean_dirty) {
   visitor(class_roots_, arg);
   Thread* self = Thread::Current();
   {
     ReaderMutexLock mu(self, dex_lock_);
-    for (mirror::DexCache* dex_cache : dex_caches_) {
-      visitor(dex_cache, arg);
+    if (!only_dirty || dex_caches_dirty_) {
+      for (mirror::DexCache* dex_cache : dex_caches_) {
+        visitor(dex_cache, arg);
+      }
+      if (clean_dirty) {
+        dex_caches_dirty_ = false;
+      }
     }
   }
 
   {
     ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
-    for (const std::pair<size_t, mirror::Class*>& it : class_table_) {
-      visitor(it.second, arg);
+    if (!only_dirty || class_table_dirty_) {
+      for (const std::pair<size_t, mirror::Class*>& it : class_table_) {
+        visitor(it.second, arg);
+      }
+      if (clean_dirty) {
+        class_table_dirty_ = false;
+      }
     }
 
     // We deliberately ignore the class roots in the image since we
@@ -1109,9 +1120,6 @@ void ClassLinker::VisitRoots(RootVisitor* visitor, void* arg, bool clean_dirty)
   }
 
   visitor(array_iftable_, arg);
-  if (clean_dirty) {
-    is_dirty_ = false;
-  }
 }
 
 void ClassLinker::VisitClasses(ClassVisitor* visitor, void* arg) {
@@ -1928,7 +1936,7 @@ void ClassLinker::RegisterDexFileLocked(const DexFile& dex_file, SirtRef<mirror:
   CHECK(dex_cache->GetLocation()->Equals(dex_file.GetLocation()));
   dex_caches_.push_back(dex_cache.get());
   dex_cache->SetDexFile(&dex_file);
-  Dirty();
+  dex_caches_dirty_ = true;
 }
 
 void ClassLinker::RegisterDexFile(const DexFile& dex_file) {
@@ -2203,7 +2211,7 @@ mirror::Class* ClassLinker::InsertClass(const char* descriptor, mirror::Class* k
   }
   Runtime::Current()->GetHeap()->VerifyObject(klass);
   class_table_.insert(std::make_pair(hash, klass));
-  Dirty();
+  class_table_dirty_ = true;
   return NULL;
 }
 
@@ -2316,7 +2324,7 @@ void ClassLinker::MoveImageClassesToClassTable() {
       }
     }
   }
-  Dirty();
+  class_table_dirty_ = true;
   dex_cache_image_class_lookup_required_ = false;
   self->EndAssertNoThreadSuspension(old_no_suspend_cause);
 }
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index c5fb72c..20efbb4 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -231,7 +231,7 @@ class ClassLinker {
       LOCKS_EXCLUDED(dex_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  void VisitRoots(RootVisitor* visitor, void* arg, bool clean_dirty)
+  void VisitRoots(RootVisitor* visitor, void* arg, bool only_dirty, bool clean_dirty)
       LOCKS_EXCLUDED(Locks::classlinker_classes_lock_, dex_lock_);
 
   mirror::DexCache* FindDexCache(const DexFile& dex_file) const
@@ -335,14 +335,6 @@ class ClassLinker {
   pid_t GetClassesLockOwner();  // For SignalCatcher.
   pid_t GetDexLockOwner();  // For SignalCatcher.
 
-  bool IsDirty() const {
-    return is_dirty_;
-  }
-
-  void Dirty() {
-    is_dirty_ = true;
-  }
-
   const void* GetPortableResolutionTrampoline() const {
     return portable_resolution_trampoline_;
   }
@@ -617,7 +609,8 @@ class ClassLinker {
   mirror::IfTable* array_iftable_;
 
   bool init_done_;
-  bool is_dirty_;
+  bool dex_caches_dirty_ GUARDED_BY(dex_lock_);
+  bool class_table_dirty_ GUARDED_BY(Locks::classlinker_classes_lock_);
 
   InternTable* intern_table_;
 
diff --git a/runtime/class_linker_test.cc b/runtime/class_linker_test.cc
index 6442f5a..995434c 100644
--- a/runtime/class_linker_test.cc
+++ b/runtime/class_linker_test.cc
@@ -331,7 +331,7 @@ class ClassLinkerTest : public CommonTest {
       const char* descriptor = dex->GetTypeDescriptor(type_id);
       AssertDexFileClass(class_loader, descriptor);
     }
-    class_linker_->VisitRoots(TestRootVisitor, NULL, false);
+    class_linker_->VisitRoots(TestRootVisitor, NULL, false, false);
     // Verify the dex cache has resolution methods in all resolved method slots
     mirror::DexCache* dex_cache = class_linker_->FindDexCache(*dex);
     mirror::ObjectArray<mirror::ArtMethod>* resolved_methods = dex_cache->GetResolvedMethods();
diff --git a/runtime/gc/accounting/card_table-inl.h b/runtime/gc/accounting/card_table-inl.h
index c5e8812..0cfbd6f 100644
--- a/runtime/gc/accounting/card_table-inl.h
+++ b/runtime/gc/accounting/card_table-inl.h
@@ -64,10 +64,9 @@ inline void CardTable::Scan(SpaceBitmap* bitmap, byte* scan_begin, byte* scan_en
   byte* aligned_end = card_end -
       (reinterpret_cast<uintptr_t>(card_end) & (sizeof(uintptr_t) - 1));
 
-  // Now we have the words, we can send these to be processed in parallel.
-  uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur);
   uintptr_t* word_end = reinterpret_cast<uintptr_t*>(aligned_end);
-  for (;;) {
+  for (uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur); word_cur < word_end;
+      ++word_cur) {
     while (LIKELY(*word_cur == 0)) {
       ++word_cur;
       if (UNLIKELY(word_cur >= word_end)) {
@@ -78,6 +77,8 @@ inline void CardTable::Scan(SpaceBitmap* bitmap, byte* scan_begin, byte* scan_en
     // Find the first dirty card.
     uintptr_t start_word = *word_cur;
     uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(reinterpret_cast<byte*>(word_cur)));
+    // TODO: Investigate if processing continuous runs of dirty cards with a single bitmap visit is
+    // more efficient.
     for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
       if (static_cast<byte>(start_word) >= minimum_age) {
         auto* card = reinterpret_cast<byte*>(word_cur) + i;
@@ -88,7 +89,6 @@ inline void CardTable::Scan(SpaceBitmap* bitmap, byte* scan_begin, byte* scan_en
       start_word >>= 8;
       start += kCardSize;
     }
-    ++word_cur;
   }
   exit_for:
 
diff --git a/runtime/intern_table.cc b/runtime/intern_table.cc
index e3a75cf..89c15f8 100644
--- a/runtime/intern_table.cc
+++ b/runtime/intern_table.cc
@@ -42,13 +42,15 @@ void InternTable::DumpForSigQuit(std::ostream& os) const {
 }
 
 void InternTable::VisitRoots(RootVisitor* visitor, void* arg,
-                             bool clean_dirty) {
+                             bool only_dirty, bool clean_dirty) {
   MutexLock mu(Thread::Current(), intern_table_lock_);
-  for (const auto& strong_intern : strong_interns_) {
-    visitor(strong_intern.second, arg);
-  }
-  if (clean_dirty) {
-    is_dirty_ = false;
+  if (!only_dirty || is_dirty_) {
+    for (const auto& strong_intern : strong_interns_) {
+      visitor(strong_intern.second, arg);
+    }
+    if (clean_dirty) {
+      is_dirty_ = false;
+    }
   }
   // Note: we deliberately don't visit the weak_interns_ table and the immutable
   // image roots.
@@ -123,7 +125,7 @@ mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) {
     }
 
     // Mark as dirty so that we rescan the roots.
-    Dirty();
+    is_dirty_ = true;
 
     // Check the image for a match.
     mirror::String* image = LookupStringFromImage(s);
diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index a804d1f..07615dc 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -62,15 +62,10 @@ class InternTable {
 
   size_t Size() const;
 
-  void VisitRoots(RootVisitor* visitor, void* arg, bool clean_dirty);
+  void VisitRoots(RootVisitor* visitor, void* arg, bool only_dirty, bool clean_dirty);
 
   void DumpForSigQuit(std::ostream& os) const;
 
-  bool IsDirty() const { return is_dirty_; }
-  void Dirty() {
-    is_dirty_ = true;
-  }
-
  private:
   typedef std::multimap<int32_t, mirror::String*> Table;
 
@@ -83,7 +78,7 @@ class InternTable {
   void Remove(Table& table, const mirror::String* s, uint32_t hash_code);
 
   mutable Mutex intern_table_lock_;
-  bool is_dirty_;
+  bool is_dirty_ GUARDED_BY(intern_table_lock_);
   Table strong_interns_ GUARDED_BY(intern_table_lock_);
   Table weak_interns_ GUARDED_BY(intern_table_lock_);
 };
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 09cbd0b..70a4df5 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -1132,12 +1132,8 @@ void Runtime::DetachCurrentThread() {
 
 void Runtime::VisitConcurrentRoots(RootVisitor* visitor, void* arg, bool only_dirty,
                                    bool clean_dirty) {
-  if (!only_dirty || intern_table_->IsDirty()) {
-    intern_table_->VisitRoots(visitor, arg, clean_dirty);
-  }
-  if (!only_dirty || class_linker_->IsDirty()) {
-    class_linker_->VisitRoots(visitor, arg, clean_dirty);
-  }
+  intern_table_->VisitRoots(visitor, arg, only_dirty, clean_dirty);
+  class_linker_->VisitRoots(visitor, arg, only_dirty, clean_dirty);
 }
 
 void Runtime::VisitNonThreadRoots(RootVisitor* visitor, void* arg) {