src/sync/engine/get_commit_ids.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "sync/engine/get_commit_ids.h"
   6
   7 #include <set>
   8 #include <vector>
   9
  10 #include "base/basictypes.h"
  11 #include "sync/engine/syncer_util.h"
  12 #include "sync/syncable/directory.h"
  13 #include "sync/syncable/entry.h"
  14 #include "sync/syncable/nigori_handler.h"
  15 #include "sync/syncable/nigori_util.h"
  16 #include "sync/syncable/syncable_base_transaction.h"
  17 #include "sync/syncable/syncable_util.h"
  18 #include "sync/util/cryptographer.h"
  19
  20 using std::set;
  21 using std::vector;
  22
  23 namespace syncer {
  24
  25 namespace {
  26
  27 // Forward-declare some helper functions.  This gives us more options for
  28 // ordering the function defintions within this file.
  29
  30 // Filters |unsynced_handles| to remove all entries that do not belong to the
  31 // specified |requested_types|, or are not eligible for a commit at this time.
  32 void FilterUnreadyEntries(
  33     syncable::BaseTransaction* trans,
  34     ModelTypeSet requested_types,
  35     ModelTypeSet encrypted_types,
  36     bool passphrase_missing,
  37     const syncable::Directory::Metahandles& unsynced_handles,
  38     std::set<int64>* ready_unsynced_set);
  39
  40 // Given a set of commit metahandles that are ready for commit
  41 // (|ready_unsynced_set|), sorts these into commit order and places up to
  42 // |max_entries| of them in the output parameter |out|.
  43 //
  44 // See the header file for an explanation of commit ordering.
  45 void OrderCommitIds(
  46     syncable::BaseTransaction* trans,
  47     size_t max_entries,
  48     const std::set<int64>& ready_unsynced_set,
  49     std::vector<int64>* out);
  50
  51 }  // namespace
  52
  53 void GetCommitIdsForType(
  54     syncable::BaseTransaction* trans,
  55     ModelType type,
  56     size_t max_entries,
  57     syncable::Directory::Metahandles* out) {
  58   syncable::Directory* dir = trans->directory();
  59
  60   // Gather the full set of unsynced items and store it in the session. They
  61   // are not in the correct order for commit.
  62   std::set<int64> ready_unsynced_set;
  63   syncable::Directory::Metahandles all_unsynced_handles;
  64   GetUnsyncedEntries(trans, &all_unsynced_handles);
  65
  66   ModelTypeSet encrypted_types;
  67   bool passphrase_missing = false;
  68   Cryptographer* cryptographer = dir->GetCryptographer(trans);
  69   if (cryptographer) {
  70     encrypted_types = dir->GetNigoriHandler()->GetEncryptedTypes(trans);
  71     passphrase_missing = cryptographer->has_pending_keys();
  72   };
  73
  74   // We filter out all unready entries from the set of unsynced handles. This
  75   // new set of ready and unsynced items is then what we use to determine what
  76   // is a candidate for commit.  The caller is responsible for ensuring that no
  77   // throttled types are included among the requested_types.
  78   FilterUnreadyEntries(trans,
  79                        ModelTypeSet(type),
  80                        encrypted_types,
  81                        passphrase_missing,
  82                        all_unsynced_handles,
  83                        &ready_unsynced_set);
  84
  85   OrderCommitIds(trans, max_entries, ready_unsynced_set, out);
  86
  87   for (size_t i = 0; i < out->size(); i++) {
  88     DVLOG(1) << "Debug commit batch result:" << (*out)[i];
  89   }
  90 }
  91
  92 namespace {
  93
  94 bool IsEntryInConflict(const syncable::Entry& entry) {
  95   if (entry.GetIsUnsynced() &&
  96       entry.GetServerVersion() > 0 &&
  97       (entry.GetServerVersion() > entry.GetBaseVersion())) {
  98     // The local and server versions don't match. The item must be in
  99     // conflict, so there's no point in attempting to commit.
 100     DCHECK(entry.GetIsUnappliedUpdate());
 101     DVLOG(1) << "Excluding entry from commit due to version mismatch "
 102              << entry;
 103     return true;
 104   }
 105   return false;
 106 }
 107
 108 // Return true if this entry has any attachments that haven't yet been uploaded
 109 // to the server.
 110 bool HasAttachmentNotOnServer(const syncable::Entry& entry) {
 111   const sync_pb::AttachmentMetadata& metadata = entry.GetAttachmentMetadata();
 112   for (int i = 0; i < metadata.record_size(); ++i) {
 113     if (!metadata.record(i).is_on_server()) {
 114       return true;
 115     }
 116   }
 117   return false;
 118 }
 119
 120 // An entry is not considered ready for commit if any are true:
 121 // 1. It's in conflict.
 122 // 2. It requires encryption (either the type is encrypted but a passphrase
 123 //    is missing from the cryptographer, or the entry itself wasn't properly
 124 //    encrypted).
 125 // 3. It's type is currently throttled.
 126 // 4. It's a delete but has not been committed.
 127 bool IsEntryReadyForCommit(ModelTypeSet requested_types,
 128                            ModelTypeSet encrypted_types,
 129                            bool passphrase_missing,
 130                            const syncable::Entry& entry) {
 131   DCHECK(entry.GetIsUnsynced());
 132   if (IsEntryInConflict(entry))
 133     return false;
 134
 135   const ModelType type = entry.GetModelType();
 136   // We special case the nigori node because even though it is considered an
 137   // "encrypted type", not all nigori node changes require valid encryption
 138   // (ex: sync_tabs).
 139   if ((type != NIGORI) && encrypted_types.Has(type) &&
 140       (passphrase_missing ||
 141        syncable::EntryNeedsEncryption(encrypted_types, entry))) {
 142     // This entry requires encryption but is not properly encrypted (possibly
 143     // due to the cryptographer not being initialized or the user hasn't
 144     // provided the most recent passphrase).
 145     DVLOG(1) << "Excluding entry from commit due to lack of encryption "
 146              << entry;
 147     return false;
 148   }
 149
 150   // Ignore it if it's not in our set of requested types.
 151   if (!requested_types.Has(type))
 152     return false;
 153
 154   if (entry.GetIsDel() && !entry.GetId().ServerKnows()) {
 155     // New clients (following the resolution of crbug.com/125381) should not
 156     // create such items.  Old clients may have left some in the database
 157     // (crbug.com/132905), but we should now be cleaning them on startup.
 158     NOTREACHED() << "Found deleted and unsynced local item: " << entry;
 159     return false;
 160   }
 161
 162   // Extra validity checks.
 163   syncable::Id id = entry.GetId();
 164   if (id == entry.GetParentId()) {
 165     CHECK(id.IsRoot()) << "Non-root item is self parenting." << entry;
 166     // If the root becomes unsynced it can cause us problems.
 167     NOTREACHED() << "Root item became unsynced " << entry;
 168     return false;
 169   }
 170
 171   if (entry.IsRoot()) {
 172     NOTREACHED() << "Permanent item became unsynced " << entry;
 173     return false;
 174   }
 175
 176   if (HasAttachmentNotOnServer(entry)) {
 177     // This entry is not ready to be sent to the server because it has one or
 178     // more attachments that have not yet been uploaded to the server.  The idea
 179     // here is avoid propagating an entry with dangling attachment references.
 180     return false;
 181   }
 182
 183   DVLOG(2) << "Entry is ready for commit: " << entry;
 184   return true;
 185 }
 186
 187 // Filters |unsynced_handles| to remove all entries that do not belong to the
 188 // specified |requested_types|, or are not eligible for a commit at this time.
 189 void FilterUnreadyEntries(
 190     syncable::BaseTransaction* trans,
 191     ModelTypeSet requested_types,
 192     ModelTypeSet encrypted_types,
 193     bool passphrase_missing,
 194     const syncable::Directory::Metahandles& unsynced_handles,
 195     std::set<int64>* ready_unsynced_set) {
 196   for (syncable::Directory::Metahandles::const_iterator iter =
 197        unsynced_handles.begin(); iter != unsynced_handles.end(); ++iter) {
 198     syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter);
 199     // TODO(maniscalco): While we check if entry is ready to be committed, we
 200     // also need to check that all of its ancestors (parents, transitive) are
 201     // ready to be committed.  Once attachments can prevent an entry from being
 202     // committable, this method must ensure all ancestors are ready for commit
 203     // (bug 356273).
 204     if (IsEntryReadyForCommit(requested_types,
 205                               encrypted_types,
 206                               passphrase_missing,
 207                               entry)) {
 208       ready_unsynced_set->insert(*iter);
 209     }
 210   }
 211 }
 212
 213 // This class helps to implement OrderCommitIds().  Its members track the
 214 // progress of a traversal while its methods extend it.  It can return early if
 215 // the traversal reaches the desired size before the full traversal is complete.
 216 class Traversal {
 217  public:
 218   Traversal(
 219     syncable::BaseTransaction* trans,
 220     int64 max_entries,
 221     syncable::Directory::Metahandles* out);
 222   ~Traversal();
 223
 224   // First step of traversal building.  Adds non-deleted items in order.
 225   void AddCreatesAndMoves(const std::set<int64>& ready_unsynced_set);
 226
 227   // Second step of traverals building.  Appends deleted items.
 228   void AddDeletes(const std::set<int64>& ready_unsynced_set);
 229
 230  private:
 231   // The following functions do not modify the traversal directly.  They return
 232   // their results in the |result| vector instead.
 233   bool AddUncommittedParentsAndTheirPredecessors(
 234       const std::set<int64>& ready_unsynced_set,
 235       const syncable::Entry& item,
 236       syncable::Directory::Metahandles* result) const;
 237
 238   void TryAddItem(const std::set<int64>& ready_unsynced_set,
 239                   const syncable::Entry& item,
 240                   syncable::Directory::Metahandles* result) const;
 241
 242   void AddItemThenPredecessors(
 243       const std::set<int64>& ready_unsynced_set,
 244       const syncable::Entry& item,
 245       syncable::Directory::Metahandles* result) const;
 246
 247   void AddPredecessorsThenItem(
 248       const std::set<int64>& ready_unsynced_set,
 249       const syncable::Entry& item,
 250       syncable::Directory::Metahandles* result) const;
 251
 252   bool AddDeletedParents(const std::set<int64>& ready_unsynced_set,
 253                          const syncable::Entry& item,
 254                          const syncable::Directory::Metahandles& traversed,
 255                          syncable::Directory::Metahandles* result) const;
 256
 257   // Returns true if we've collected enough items.
 258   bool IsFull() const;
 259
 260   // Returns true if the specified handle is already in the traversal.
 261   bool HaveItem(int64 handle) const;
 262
 263   // Adds the specified handles to the traversal.
 264   void AppendManyToTraversal(const syncable::Directory::Metahandles& handles);
 265
 266   // Adds the specifed handle to the traversal.
 267   void AppendToTraversal(int64 handle);
 268
 269   syncable::Directory::Metahandles* out_;
 270   std::set<int64> added_handles_;
 271   const size_t max_entries_;
 272   syncable::BaseTransaction* trans_;
 273
 274   DISALLOW_COPY_AND_ASSIGN(Traversal);
 275 };
 276
 277 Traversal::Traversal(
 278     syncable::BaseTransaction* trans,
 279     int64 max_entries,
 280     syncable::Directory::Metahandles* out)
 281   : out_(out),
 282     max_entries_(max_entries),
 283     trans_(trans) { }
 284
 285 Traversal::~Traversal() {}
 286
 287 bool Traversal::AddUncommittedParentsAndTheirPredecessors(
 288     const std::set<int64>& ready_unsynced_set,
 289     const syncable::Entry& item,
 290     syncable::Directory::Metahandles* result) const {
 291   syncable::Directory::Metahandles dependencies;
 292   syncable::Id parent_id = item.GetParentId();
 293
 294   // Climb the tree adding entries leaf -> root.
 295   while (!parent_id.ServerKnows()) {
 296     syncable::Entry parent(trans_, syncable::GET_BY_ID, parent_id);
 297     CHECK(parent.good()) << "Bad user-only parent in item path.";
 298     int64 handle = parent.GetMetahandle();
 299     if (HaveItem(handle)) {
 300       // We've already added this parent (and therefore all of its parents).
 301       // We can return early.
 302       break;
 303     }
 304     if (IsEntryInConflict(parent)) {
 305       // We ignore all entries that are children of a conflicing item.  Return
 306       // false immediately to forget the traversal we've built up so far.
 307       DVLOG(1) << "Parent was in conflict, omitting " << item;
 308       return false;
 309     }
 310     AddItemThenPredecessors(ready_unsynced_set,
 311                             parent,
 312                             &dependencies);
 313     parent_id = parent.GetParentId();
 314   }
 315
 316   // Reverse what we added to get the correct order.
 317   result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
 318   return true;
 319 }
 320
 321 // Adds the given item to the list if it is unsynced and ready for commit.
 322 void Traversal::TryAddItem(const std::set<int64>& ready_unsynced_set,
 323                            const syncable::Entry& item,
 324                            syncable::Directory::Metahandles* result) const {
 325   DCHECK(item.GetIsUnsynced());
 326   int64 item_handle = item.GetMetahandle();
 327   if (ready_unsynced_set.count(item_handle) != 0) {
 328     result->push_back(item_handle);
 329   }
 330 }
 331
 332 // Adds the given item, and all its unsynced predecessors.  The traversal will
 333 // be cut short if any item along the traversal is not IS_UNSYNCED, or if we
 334 // detect that this area of the tree has already been traversed.  Items that are
 335 // not 'ready' for commit (see IsEntryReadyForCommit()) will not be added to the
 336 // list, though they will not stop the traversal.
 337 void Traversal::AddItemThenPredecessors(
 338     const std::set<int64>& ready_unsynced_set,
 339     const syncable::Entry& item,
 340     syncable::Directory::Metahandles* result) const {
 341   int64 item_handle = item.GetMetahandle();
 342   if (HaveItem(item_handle)) {
 343     // We've already added this item to the commit set, and so must have
 344     // already added the predecessors as well.
 345     return;
 346   }
 347   TryAddItem(ready_unsynced_set, item, result);
 348   if (item.GetIsDel())
 349     return;  // Deleted items have no predecessors.
 350
 351   syncable::Id prev_id = item.GetPredecessorId();
 352   while (!prev_id.IsRoot()) {
 353     syncable::Entry prev(trans_, syncable::GET_BY_ID, prev_id);
 354     CHECK(prev.good()) << "Bad id when walking predecessors.";
 355     if (!prev.GetIsUnsynced()) {
 356       // We're interested in "runs" of unsynced items.  This item breaks
 357       // the streak, so we stop traversing.
 358       return;
 359     }
 360     int64 handle = prev.GetMetahandle();
 361     if (HaveItem(handle)) {
 362       // We've already added this item to the commit set, and so must have
 363       // already added the predecessors as well.
 364       return;
 365     }
 366     TryAddItem(ready_unsynced_set, prev, result);
 367     prev_id = prev.GetPredecessorId();
 368   }
 369 }
 370
 371 // Same as AddItemThenPredecessor, but the traversal order will be reversed.
 372 void Traversal::AddPredecessorsThenItem(
 373     const std::set<int64>& ready_unsynced_set,
 374     const syncable::Entry& item,
 375     syncable::Directory::Metahandles* result) const {
 376   syncable::Directory::Metahandles dependencies;
 377   AddItemThenPredecessors(ready_unsynced_set, item, &dependencies);
 378
 379   // Reverse what we added to get the correct order.
 380   result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
 381 }
 382
 383 // Traverses the tree from bottom to top, adding the deleted parents of the
 384 // given |item|.  Stops traversing if it encounters a non-deleted node, or
 385 // a node that was already listed in the |traversed| list.  Returns an error
 386 // (false) if a node along the traversal is in a conflict state.
 387 //
 388 // The result list is reversed before it is returned, so the resulting
 389 // traversal is in top to bottom order.  Also note that this function appends
 390 // to the result list without clearing it.
 391 bool Traversal::AddDeletedParents(
 392     const std::set<int64>& ready_unsynced_set,
 393     const syncable::Entry& item,
 394     const syncable::Directory::Metahandles& traversed,
 395     syncable::Directory::Metahandles* result) const {
 396   syncable::Directory::Metahandles dependencies;
 397   syncable::Id parent_id = item.GetParentId();
 398
 399   // Climb the tree adding entries leaf -> root.
 400   while (!parent_id.IsRoot()) {
 401     syncable::Entry parent(trans_, syncable::GET_BY_ID, parent_id);
 402
 403     if (!parent.good()) {
 404       // This is valid because the parent could have gone away a long time ago
 405       //
 406       // Consider the case where a folder is server-unknown and locally
 407       // deleted, and has a child that is server-known, deleted, and unsynced.
 408       // The parent could be dropped from memory at any time, but its child
 409       // needs to be committed first.
 410       break;
 411     }
 412     int64 handle = parent.GetMetahandle();
 413     if (!parent.GetIsUnsynced()) {
 414       // In some rare cases, our parent can be both deleted and unsynced.
 415       // (ie. the server-unknown parent case).
 416       break;
 417     }
 418     if (!parent.GetIsDel()) {
 419       // We're not intersted in non-deleted parents.
 420       break;
 421     }
 422     if (std::find(traversed.begin(), traversed.end(), handle) !=
 423         traversed.end()) {
 424       // We've already added this parent (and therefore all of its parents).
 425       // We can return early.
 426       break;
 427     }
 428     if (IsEntryInConflict(parent)) {
 429       // We ignore all entries that are children of a conflicing item.  Return
 430       // false immediately to forget the traversal we've built up so far.
 431       DVLOG(1) << "Parent was in conflict, omitting " << item;
 432       return false;
 433     }
 434     TryAddItem(ready_unsynced_set, parent, &dependencies);
 435     parent_id = parent.GetParentId();
 436   }
 437
 438   // Reverse what we added to get the correct order.
 439   result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
 440   return true;
 441 }
 442
 443 bool Traversal::IsFull() const {
 444   return out_->size() >= max_entries_;
 445 }
 446
 447 bool Traversal::HaveItem(int64 handle) const {
 448   return added_handles_.find(handle) != added_handles_.end();
 449 }
 450
 451 void Traversal::AppendManyToTraversal(
 452     const syncable::Directory::Metahandles& handles) {
 453   out_->insert(out_->end(), handles.begin(), handles.end());
 454   added_handles_.insert(handles.begin(), handles.end());
 455 }
 456
 457 void Traversal::AppendToTraversal(int64 metahandle) {
 458   out_->push_back(metahandle);
 459   added_handles_.insert(metahandle);
 460 }
 461
 462 void Traversal::AddCreatesAndMoves(
 463     const std::set<int64>& ready_unsynced_set) {
 464   // Add moves and creates, and prepend their uncommitted parents.
 465   for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin();
 466        !IsFull() && iter != ready_unsynced_set.end(); ++iter) {
 467     int64 metahandle = *iter;
 468     if (HaveItem(metahandle))
 469       continue;
 470
 471     syncable::Entry entry(trans_,
 472                           syncable::GET_BY_HANDLE,
 473                           metahandle);
 474     if (!entry.GetIsDel()) {
 475       // We only commit an item + its dependencies if it and all its
 476       // dependencies are not in conflict.
 477       syncable::Directory::Metahandles item_dependencies;
 478       if (AddUncommittedParentsAndTheirPredecessors(
 479               ready_unsynced_set,
 480               entry,
 481               &item_dependencies)) {
 482         AddPredecessorsThenItem(ready_unsynced_set,
 483                                 entry,
 484                                 &item_dependencies);
 485         AppendManyToTraversal(item_dependencies);
 486       }
 487     }
 488   }
 489
 490   // It's possible that we overcommitted while trying to expand dependent
 491   // items.  If so, truncate the set down to the allowed size.
 492   if (out_->size() > max_entries_)
 493     out_->resize(max_entries_);
 494 }
 495
 496 void Traversal::AddDeletes(const std::set<int64>& ready_unsynced_set) {
 497   syncable::Directory::Metahandles deletion_list;
 498
 499   for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin();
 500        !IsFull() && iter != ready_unsynced_set.end(); ++iter) {
 501     int64 metahandle = *iter;
 502
 503     if (HaveItem(metahandle))
 504       continue;
 505
 506     if (std::find(deletion_list.begin(), deletion_list.end(), metahandle) !=
 507         deletion_list.end()) {
 508       continue;
 509     }
 510
 511     syncable::Entry entry(trans_, syncable::GET_BY_HANDLE,
 512                           metahandle);
 513
 514     if (entry.GetIsDel()) {
 515       syncable::Directory::Metahandles parents;
 516       if (AddDeletedParents(
 517               ready_unsynced_set, entry, deletion_list, &parents)) {
 518         // Append parents and chilren in top to bottom order.
 519         deletion_list.insert(deletion_list.end(),
 520                              parents.begin(),
 521                              parents.end());
 522         deletion_list.push_back(metahandle);
 523       }
 524     }
 525
 526     if (deletion_list.size() + out_->size() > max_entries_)
 527       break;
 528   }
 529
 530   // We've been gathering deletions in top to bottom order.  Now we reverse the
 531   // order as we prepare the list.
 532   std::reverse(deletion_list.begin(), deletion_list.end());
 533   AppendManyToTraversal(deletion_list);
 534
 535   // It's possible that we overcommitted while trying to expand dependent
 536   // items.  If so, truncate the set down to the allowed size.
 537   if (out_->size() > max_entries_)
 538     out_->resize(max_entries_);
 539 }
 540
 541 void OrderCommitIds(
 542     syncable::BaseTransaction* trans,
 543     size_t max_entries,
 544     const std::set<int64>& ready_unsynced_set,
 545     syncable::Directory::Metahandles* out) {
 546   // Commits follow these rules:
 547   // 1. Moves or creates are preceded by needed folder creates, from
 548   //    root to leaf.  For folders whose contents are ordered, moves
 549   //    and creates appear in order.
 550   // 2. Moves/Creates before deletes.
 551   // 3. Deletes, collapsed.
 552   // We commit deleted moves under deleted items as moves when collapsing
 553   // delete trees.
 554
 555   Traversal traversal(trans, max_entries, out);
 556
 557   // Add moves and creates, and prepend their uncommitted parents.
 558   traversal.AddCreatesAndMoves(ready_unsynced_set);
 559
 560   // Add all deletes.
 561   traversal.AddDeletes(ready_unsynced_set);
 562 }
 563
 564 }  // namespace
 565
 566 }  // namespace syncer