Check node references during sync DB init

This commit adds a check to verify that the NEXT_ID, PREV_ID and
PARENT_ID fields of nodes in the database point to the IDs of other
existing nodes.  The syncable::Database code assumes that this invariant
always holds and seems to do a good job of maintaining it.  This change
ensures that the invariant holds at the time the data is loaded from
disk.

There exist some corrupt databases that cause the directory to behave
unpredictably, since the code assumes the databsae is correct when it is
read from disk.  We can't do anything to fix those databases now that
they've been written, but we can detect the corruption and recreate the
affected databases.

This check is implemented using a set of hash maps, so the cost of the
check should scale well with the number of nodes (it's O(n)).  The
per-node cost of this check also seems cheap compared to the disc
access.  In release mode, loading 5000 nodes from a (probably in-cache)
sqlite database took 53ms, while the check took 9 ms.

BUG=101048
TEST=Manual.  Corrupted the database with external sqlite tool, verified
that the database was deleted and re-created next time Chrome was loaded.

Review URL: http://codereview.chromium.org/8475017

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@111033 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 48 insertions, 1 deletions

diff --git a/chrome/browser/sync/syncable/dir_open_result.h b/chrome/browser/sync/syncable/dir_open_result.h
index f64c6a6..4f082d5 100644
--- a/chrome/browser/sync/syncable/dir_open_result.h
+++ b/chrome/browser/sync/syncable/dir_open_result.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -13,6 +13,7 @@ enum DirOpenResult { OPENED,   // success.
                      FAILED_OPEN_DATABASE,  // sqlite_open() failed.
                      FAILED_DISK_FULL,  // The disk is full.
                      FAILED_DATABASE_CORRUPT,  // Something is wrong with the DB
+                     FAILED_LOGICAL_CORRUPTION, // Invalid database contents
 };
 }  // namespace syncable
 
diff --git a/chrome/browser/sync/syncable/syncable.cc b/chrome/browser/sync/syncable/syncable.cc
index b1548f0..c6ae039 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,42 @@ static const InvariantCheckLevel kInvariantCheckLevel = VERIFY_IN_MEMORY;
 
 // Max number of milliseconds to spend checking syncable entry invariants
 static const int kInvariantCheckMaxMs = 50;
+
+// 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) {
+  TRACE_EVENT0("sync", "SyncDatabaseIntegrityCheck");
+  using namespace syncable;
+  typedef base::hash_set<std::string> IdsSet;
+
+  IdsSet ids_set;
+  bool is_ok = true;
+
+  for (MetahandlesIndex::const_iterator it = index.begin();
+       it != index.end(); ++it) {
+    EntryKernel* entry = *it;
+    bool is_duplicate_id = !(ids_set.insert(entry->ref(ID).value()).second);
+    is_ok = is_ok && !is_duplicate_id;
+  }
+
+  IdsSet::iterator end = ids_set.end();
+  for (MetahandlesIndex::const_iterator it = index.begin();
+       it != index.end(); ++it) {
+    EntryKernel* entry = *it;
+    bool prev_exists = (ids_set.find(entry->ref(PREV_ID).value()) != end);
+    bool parent_exists = (ids_set.find(entry->ref(PARENT_ID).value()) != end);
+    bool next_exists = (ids_set.find(entry->ref(NEXT_ID).value()) != end);
+    is_ok = is_ok && prev_exists && parent_exists && next_exists;
+  }
+  return is_ok;
+}
+
 }  // namespace
 
 using std::string;
@@ -477,6 +514,7 @@ DirOpenResult Directory::OpenImpl(
     DirectoryChangeDelegate* delegate,
     const browser_sync::WeakHandle<TransactionObserver>&
         transaction_observer) {
+  TRACE_EVENT0("sync", "SyncDatabaseOpen");
   DCHECK_EQ(static_cast<DirectoryBackingStore*>(NULL), store_);
   FilePath db_path(file_path);
   file_util::AbsolutePath(&db_path);
@@ -490,6 +528,9 @@ DirOpenResult Directory::OpenImpl(
   if (OPENED != result)
     return result;
 
+  if (!VerifyReferenceIntegrityUnsafe(metas_bucket))
+    return FAILED_LOGICAL_CORRUPTION;
+
   kernel_ = new Kernel(db_path, name, info, delegate, transaction_observer);
   kernel_->metahandles_index->swap(metas_bucket);
   InitializeIndices();
diff --git a/chrome/browser/sync/syncable/syncable_id.h b/chrome/browser/sync/syncable/syncable_id.h
index 2267040..73eb934 100644
--- a/chrome/browser/sync/syncable/syncable_id.h
+++ b/chrome/browser/sync/syncable/syncable_id.h
@@ -87,6 +87,11 @@ class Id {
   inline bool operator > (const Id& that) const {
     return s_ > that.s_;
   }
+
+  const std::string& value() const {
+    return s_;
+  }
+
   // Return the next highest ID in the lexicographic ordering.  This is
   // useful for computing upper bounds on std::sets that are ordered
   // by operator<.