Check node references during sync DB init

chrome/browser/sync/syncable/syncable.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/sync/syncable/syncable.h"
 
 #include <algorithm>
 #include <cstring>
 #include <functional>
 #include <iomanip>
 #include <iterator>
 #include <limits>
 #include <set>
 #include <string>
 
 #include "base/compiler_specific.h"
+#include "base/debug/trace_event.h"
 #include "base/file_util.h"
 #include "base/hash_tables.h"
 #include "base/location.h"
 #include "base/logging.h"
 #include "base/memory/scoped_ptr.h"
 #include "base/perftimer.h"
 #include "base/stl_util.h"
 #include "base/string_number_conversions.h"
 #include "base/string_util.h"
 #include "base/time.h"
@@ skipping 17 matching lines @@
 enum InvariantCheckLevel {
   OFF = 0,
   VERIFY_IN_MEMORY = 1,
   FULL_DB_VERIFICATION = 2
 };
 
 static const InvariantCheckLevel kInvariantCheckLevel = VERIFY_IN_MEMORY;
 
 // Max number of milliseconds to spend checking syncable entry invariants
 static const int kInvariantCheckMaxMs = 50;
+
+struct IdPtrHashFunc {
+  size_t operator()(const syncable::Id* id) const {
+    return BASE_HASH_NAMESPACE::hash<std::string>()(id->value());
+  }
+};
+
+struct IdPtrCompareFunc {
+  bool operator()(const syncable::Id* id1, const syncable::Id* id2) const {
+    return *id1 == *id2;
+  }
+};
+
+// This function checks to see if the given list of Metahandles has any nodes
+// whose PREV_ID, PARENT_ID or NEXT_ID values refer to ID values that do not
+// actually exist.  Returns true on success.
+bool VerifyReferenceIntegrity(const syncable::MetahandlesIndex &index) {

[tim (not reviewing), 2011/11/14 19:23:44]

Should append 'Unsafe' to the function name, since it doesn't acquire the kernel
lock (OK since we only call it from init), but for that reason isn't safe to
call from elsewhere. I also think it should be made a private member function of
Directory.

[rlarocque, 2011/11/14 22:05:11]

I decided against making this a member of Directory for now.  If it were to be a
member, then it would make sense that it would act on the
kernel_->metahandles_index, since that's where the metahandles are stored most
of the time.  To perform this check at early startup, before
kernel_->metahandles_index is initialized, I had to pass the list as a
parameter.  That means that this function does not access any Directory members,
so I could separate it entirely from this class.  

I agree the Unsafe suffix would make sense if it were a member function. 
However, as a non-member function, I think it's safe to expect callers to assume
it would not know about the Directory's locking scheme.  

I intend to clean this up in M17, where I can perform some more invasive
refactoring of the directory initialization process.  

+  using namespace syncable;
+  typedef base::hash_set<const Id*, IdPtrHashFunc, IdPtrCompareFunc> IdsSet;
+
+  IdsSet ids_set;
+  bool is_ok = true;
+
+  ids_set.resize(index.size());
+  for (MetahandlesIndex::iterator it = index.begin();
+       it != index.end(); ++it) {
+    EntryKernel* entry = *it;
+    bool is_duplicate_id = !(ids_set.insert(&entry->ref(ID)).second);
+    is_ok = is_ok && !is_duplicate_id;
+  }
+
+  IdsSet::iterator end = ids_set.end();
+  for (MetahandlesIndex::iterator it = index.begin();
+       it != index.end(); ++it) {
+    EntryKernel* entry = *it;
+    bool prev_exists = (ids_set.find(&(entry->ref(PREV_ID))) != end);
+    bool parent_exists = (ids_set.find(&(entry->ref(PARENT_ID))) != end);
+    bool next_exists = (ids_set.find(&(entry->ref(NEXT_ID))) != end);
+    is_ok = is_ok && prev_exists && parent_exists && next_exists;
+  }
+  return is_ok;
+}
+
 }  // namespace
 
 using std::string;
 
 namespace syncable {
 
 #define ENUM_CASE(x) case x: return #x; break
 
 std::string WriterTagToString(WriterTag writer_tag) {
   switch (writer_tag) {
@@ skipping 406 matching lines @@
   store_ = CreateBackingStore(name, db_path);
 
   KernelLoadInfo info;
   // Temporary indices before kernel_ initialized in case Load fails. We 0(1)
   // swap these later.
   MetahandlesIndex metas_bucket;
   DirOpenResult result = store_->Load(&metas_bucket, &info);
   if (OPENED != result)
     return result;
 
+  if (!VerifyReferenceIntegrity(metas_bucket)) {

[tim (not reviewing), 2011/11/14 19:23:44]

style nit: file pattern is no { } on single line if.

+    return FAILED_LOGICAL_CORRUPTION;
+  }
+
   kernel_ = new Kernel(db_path, name, info, delegate);
   kernel_->metahandles_index->swap(metas_bucket);
   InitializeIndices();
   return OPENED;
 }
 
 void Directory::Close() {
   if (store_)
     delete store_;
   store_ = NULL;
@@ skipping 1529 matching lines @@
     if (entry->ref(NEXT_ID).IsRoot() ||
         entry->ref(NEXT_ID) != entry->ref(PREV_ID)) {
       return entry;
     }
   }
   // There were no children in the linked list.
   return NULL;
 }
 
 }  // namespace syncable