Check node references during sync DB init

chrome/browser/sync/syncable/syncable.cc

Index: chrome/browser/sync/syncable/syncable.cc
diff --git a/chrome/browser/sync/syncable/syncable.cc b/chrome/browser/sync/syncable/syncable.cc
index efeecaf94440d8411742f63c28016e9bca6a3ec6..796ee74c36217f96a1aa15b3da7d6c801b3f0384 100644
--- a/chrome/browser/sync/syncable/syncable.cc
+++ b/chrome/browser/sync/syncable/syncable.cc
@@ -14,6 +14,7 @@
 #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"
@@ -51,6 +52,49 @@ 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;
@@ -477,6 +521,10 @@ DirOpenResult Directory::OpenImpl(const FilePath& file_path,
   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();