Check node references during sync DB init

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.

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=111033

[rlarocque, 2011-11-09 21:56:15]

My plan was to fix issue 103307 then commit this change.  However, it looks like
we will need to merge this onto M16 to fix issue 100374, which blocks M16 stable
release.  

It's unlikely that a fix to issue 103307 could be merged this late in the cycle.
 So we need to work around it.  

Tim pointed out that DirectoryBackingStore can delete the database in response
to certain failures.  I've modified this patch so that we can also delete the
database from DirectoryManager if the database consistency check fails.  

I also considered moving the consistency check to DirectoryBackingStore and
performing the deletion there, or moving the deletion and retry logic into the
Directory load function, but both of these options involved more code changes
than I'm willing to tolerate.  We should revisit those ideas on M17, but I don't
think it's worth the risk on a commit that's heading into M16.

[rlarocque, 2011-11-10 21:31:48]

Please disregard this review request for now.  There are two serious issues with
it that need to be resolved.  

First, this patch does not compile on Windows.  I have a fix for this almost
ready.  

While fixing the first issue, I decided to do one last round of testing.  It's a
good thing I did.  It turns out that deleting the database puts us into a state
where we believe the backend is initialized, but attempts to lookup the Nigori
will fail.  This can lead to DCHECKs and other unexpected behaviour.  

We transition out of this unusual state once the initial sync cycle is complete.
 That makes it difficult to detect when testing with a small account, but
obvious for larger accounts.

[rlarocque, 2011-11-11 23:27:57]

Reduce scope back to what it was in patch set #1, but retain
the Windows compile fixes from patch set #2.

This CL depends requires that issue 103307 be fixed in order for it to be
effective.  There is a separate CL in progress for this.  

This has not been very well tested in combination with that change.  I'm
uploading this for reference only.  I'll send another ping when this CL is ready
for review + commit.

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

http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
File chrome/browser/sync/syncable/syncable.cc (right):

http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
chrome/browser/sync/syncable/syncable.cc:71: bool VerifyReferenceIntegrity(const
syncable::MetahandlesIndex &index) {
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.

http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
chrome/browser/sync/syncable/syncable.cc:524: if
(!VerifyReferenceIntegrity(metas_bucket)) {
style nit: file pattern is no { } on single line if.

[rlarocque, 2011-11-14 22:05:10]

http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
File chrome/browser/sync/syncable/syncable.cc (right):

http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
chrome/browser/sync/syncable/syncable.cc:71: bool VerifyReferenceIntegrity(const
syncable::MetahandlesIndex &index) {
On 2011/11/14 19:23:44, timsteele wrote:
> 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.

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.

[tim (not reviewing), 2011-11-14 22:16:22]

On 2011/11/14 22:05:10, rlarocque wrote:
>
http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
> File chrome/browser/sync/syncable/syncable.cc (right):
> 
>
http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
> chrome/browser/sync/syncable/syncable.cc:71: bool
VerifyReferenceIntegrity(const
> syncable::MetahandlesIndex &index) {
> On 2011/11/14 19:23:44, timsteele wrote:
> > 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.
> 
> 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.

I think 'Unsafe' is more even appropriate given that the function is just
floating around. We should definitely add the suffix here. I've seen us get
burned by exactly this kind of thing before. It's not an uncommon pattern in
sync code or in Chrome to do this and "I think it's safe" <<< "It's obvious" :)

[rlarocque, 2011-11-14 23:05:14]

On 2011/11/14 22:16:22, timsteele wrote:
> On 2011/11/14 22:05:10, rlarocque wrote:
> >
>
http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
> > File chrome/browser/sync/syncable/syncable.cc (right):
> > 
> >
>
http://codereview.chromium.org/8475017/diff/8001/chrome/browser/sync/syncable...
> > chrome/browser/sync/syncable/syncable.cc:71: bool
> VerifyReferenceIntegrity(const
> > syncable::MetahandlesIndex &index) {
> > On 2011/11/14 19:23:44, timsteele wrote:
> > > 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.
> > 
> > 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.
> 
> I think 'Unsafe' is more even appropriate given that the function is just
> floating around. We should definitely add the suffix here. I've seen us get
> burned by exactly this kind of thing before. It's not an uncommon pattern in
> sync code or in Chrome to do this and "I think it's safe" <<< "It's obvious"
:)

I suppose it can't hurt.  Done.

[rlarocque, 2011-11-15 21:40:56]

I had delayed sending the e-mail for this review because it depends on
http://codereview.chromium.org/8496002/.  That change is now committed as
r110177.  I'll try to land this change if/when r110177 makes it through the
waterfall.  

I now declare this CL open for review.  Reviewers, let me know what you think.

[tim (not reviewing), 2011-11-17 18:39:57]

LGTM

http://codereview.chromium.org/8475017/diff/14001/chrome/browser/sync/syncabl...
File chrome/browser/sync/syncable/directory_manager.cc (right):

http://codereview.chromium.org/8475017/diff/14001/chrome/browser/sync/syncabl...
chrome/browser/sync/syncable/directory_manager.cc:83: dir.reset(new Directory);
style nit - use Directory()

[rlarocque, 2011-11-17 19:13:29]

On 2011/11/17 18:39:57, timsteele wrote:
> LGTM
> 
>
http://codereview.chromium.org/8475017/diff/14001/chrome/browser/sync/syncabl...
> File chrome/browser/sync/syncable/directory_manager.cc (right):
> 
>
http://codereview.chromium.org/8475017/diff/14001/chrome/browser/sync/syncabl...
> chrome/browser/sync/syncable/directory_manager.cc:83: dir.reset(new
Directory);
> style nit - use Directory()

Interesting.  That change is not supposed to be there.  We don't want delete and
re-create the Directory at that level.  That's what issue 103824 was created
for.  

Patch set 4 was supposed to perform the rename to
"VerifyReferenceIntegrityUnsafe" and that's it.  I must have accidentally
re-uploaded a piece of the old patch.  

I will upload a new patch.  Thanks for bringing this to my attention!

[rlarocque, 2011-11-17 19:59:50]

That's better.  The latest upload is much closer to patch set #3.

[tim (not reviewing), 2011-11-17 21:21:09]

LGTM++

[rlarocque, 2011-11-18 19:49:38]

The previous patch didn't compile on Windows because of differences in the
definition of hash_set's template parameters.  

Since my custom traits were used to make hash_set<std::string*, ...> behave like
hash_set<std::string>, the obvious fix was to just use hash_set<std::string>.  I
was worried about the performance of the extra allocations, but it seems like
the cost is barely noticeable in practice.  Once again I've been taught that
premature optimization is usually misguided.  (In my defense, this didn't start
as premature optimization.  The hash_set<std::string*> was the result of a
series of changes to this patch that all made sense at the time.)

I left in the TRACE_EVENTs I used to check the performance impact of my changes.
 That will make it easier to debug if other people see big slowdowns in sync
startup time following this change.

[tim (not reviewing), 2011-11-19 00:23:40]

still LGTM

[commit-bot: I haz the power, 2011-11-19 00:28:31]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rlarocque@chromium.org/8475017/30001

[commit-bot: I haz the power, 2011-11-19 01:03:23]

Try job failure for 8475017-30001 (retry) on win_rel for step "compile" (clobber
build).
It's a second try, previously, step "compile" failed.
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_rel&nu...

[commit-bot: I haz the power, 2011-11-21 18:55:42]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rlarocque@chromium.org/8475017/30001

[commit-bot: I haz the power, 2011-11-21 18:55:44]

Can't apply patch for file chrome/browser/sync/syncable/syncable.cc.
While running patch -p1 --forward --force;
patching file chrome/browser/sync/syncable/syncable.cc
Hunk #3 FAILED at 501.
Hunk #4 FAILED at 514.
2 out of 4 hunks FAILED -- saving rejects to file
chrome/browser/sync/syncable/syncable.cc.rej

[commit-bot: I haz the power, 2011-11-21 21:32:44]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rlarocque@chromium.org/8475017/34001

[commit-bot: I haz the power, 2011-11-21 23:18:00]

Change committed as 111033