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.
+//
+// This function is "Unsafe" because it does not attempt to acquire any locks
+// that may be protecting this list that gets passed in.  The caller is
+// responsible for ensuring that no one modifies this list while the function is
+// running.
+bool VerifyReferenceIntegrityUnsafe(const syncable::MetahandlesIndex &index) {
+  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 (!VerifyReferenceIntegrityUnsafe(metas_bucket)) {
+    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