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   // TODO(maniscalco): Add test case (bug 356266).
 112   const sync_pb::AttachmentMetadata& metadata = entry.GetAttachmentMetadata();
 113   for (int i = 0; i < metadata.record_size(); ++i) {
 114     if (!metadata.record(i).is_on_server()) {
 115       return true;
 116     }
 117   }
 118   return false;
 119 }
 120
 121 // An entry is not considered ready for commit if any are true:
 122 // 1. It's in conflict.
 123 // 2. It requires encryption (either the type is encrypted but a passphrase
 124 //    is missing from the cryptographer, or the entry itself wasn't properly
 125 //    encrypted).
 126 // 3. It's type is currently throttled.
 127 // 4. It's a delete but has not been committed.
 128 bool IsEntryReadyForCommit(ModelTypeSet requested_types,
 129                            ModelTypeSet encrypted_types,
 130                            bool passphrase_missing,
 131                            const syncable::Entry& entry) {
 132   DCHECK(entry.GetIsUnsynced());
 133   if (IsEntryInConflict(entry))
 134     return false;
 135
 136   const ModelType type = entry.GetModelType();
 137   // We special case the nigori node because even though it is considered an
 138   // "encrypted type", not all nigori node changes require valid encryption
 139   // (ex: sync_tabs).
 140   if ((type != NIGORI) && encrypted_types.Has(type) &&
 141       (passphrase_missing ||
 142        syncable::EntryNeedsEncryption(encrypted_types, entry))) {
 143     // This entry requires encryption but is not properly encrypted (possibly
 144     // due to the cryptographer not being initialized or the user hasn't
 145     // provided the most recent passphrase).
 146     DVLOG(1) << "Excluding entry from commit due to lack of encryption "
 147              << entry;
 148     return false;
 149   }
 150
 151   // Ignore it if it's not in our set of requested types.
 152   if (!requested_types.Has(type))
 153     return false;
 154
 155   if (entry.GetIsDel() && !entry.GetId().ServerKnows()) {
 156     // New clients (following the resolution of crbug.com/125381) should not
 157     // create such items.  Old clients may have left some in the database
 158     // (crbug.com/132905), but we should now be cleaning them on startup.
 159     NOTREACHED() << "Found deleted and unsynced local item: " << entry;
 160     return false;
 161   }
 162
 163   // Extra validity checks.
 164   syncable::Id id = entry.GetId();
 165   if (id == entry.GetParentId()) {
 166     CHECK(id.IsRoot()) << "Non-root item is self parenting." << entry;
 167     // If the root becomes unsynced it can cause us problems.
 168     NOTREACHED() << "Root item became unsynced " << entry;
 169     return false;
 170   }
 171
 172   if (entry.IsRoot()) {
 173     NOTREACHED() << "Permanent item became unsynced " << entry;
 174     return false;
 175   }
 176
 177   if (HasAttachmentNotOnServer(entry)) {
 178     // This entry is not ready to be sent to the server because it has one or
 179     // more attachments that have not yet been uploaded to the server.  The idea
 180     // here is avoid propagating an entry with dangling attachment references.
 181     return false;
 182   }
 183
 184   DVLOG(2) << "Entry is ready for commit: " << entry;
 185   return true;
 186 }
 187
 188 // Filters |unsynced_handles| to remove all entries that do not belong to the
 189 // specified |requested_types|, or are not eligible for a commit at this time.
 190 void FilterUnreadyEntries(
 191     syncable::BaseTransaction* trans,
 192     ModelTypeSet requested_types,
 193     ModelTypeSet encrypted_types,
 194     bool passphrase_missing,
 195     const syncable::Directory::Metahandles& unsynced_handles,
 196     std::set<int64>* ready_unsynced_set) {
 197   for (syncable::Directory::Metahandles::const_iterator iter =
 198        unsynced_handles.begin(); iter != unsynced_handles.end(); ++iter) {
 199     syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter);
 200     // TODO(maniscalco): While we check if entry is ready to be committed, we
 201     // also need to check that all of its ancestors (parents, transitive) are
 202     // ready to be committed.  Once attachments can prevent an entry from being
 203     // committable, this method must ensure all ancestors are ready for commit
 204     // (bug 356273).
 205     if (IsEntryReadyForCommit(requested_types,
 206                               encrypted_types,
 207                               passphrase_missing,
 208                               entry)) {
 209       ready_unsynced_set->insert(*iter);
 210     }
 211   }
 212 }
 213
 214 // This class helps to implement OrderCommitIds().  Its members track the
 215 // progress of a traversal while its methods extend it.  It can return early if
 216 // the traversal reaches the desired size before the full traversal is complete.
 217 class Traversal {
 218  public:
 219   Traversal(
 220     syncable::BaseTransaction* trans,
 221     int64 max_entries,
 222     syncable::Directory::Metahandles* out);
 223   ~Traversal();
 224
 225   // First step of traversal building.  Adds non-deleted items in order.
 226   void AddCreatesAndMoves(const std::set<int64>& ready_unsynced_set);
 227
 228   // Second step of traverals building.  Appends deleted items.
 229   void AddDeletes(const std::set<int64>& ready_unsynced_set);
 230
 231  private:
 232   // The following functions do not modify the traversal directly.  They return
 233   // their results in the |result| vector instead.
 234   bool AddUncommittedParentsAndTheirPredecessors(
 235       const std::set<int64>& ready_unsynced_set,
 236       const syncable::Entry& item,
 237       syncable::Directory::Metahandles* result) const;
 238
 239   void TryAddItem(const std::set<int64>& ready_unsynced_set,
 240                   const syncable::Entry& item,
 241                   syncable::Directory::Metahandles* result) const;
 242
 243   void AddItemThenPredecessors(
 244       const std::set<int64>& ready_unsynced_set,
 245       const syncable::Entry& item,
 246       syncable::Directory::Metahandles* result) const;
 247
 248   void AddPredecessorsThenItem(
 249       const std::set<int64>& ready_unsynced_set,
 250       const syncable::Entry& item,
 251       syncable::Directory::Metahandles* result) const;
 252
 253   // Returns true if we've collected enough items.
 254   bool IsFull() const;
 255
 256   // Returns true if the specified handle is already in the traversal.
 257   bool HaveItem(int64 handle) const;
 258
 259   // Adds the specified handles to the traversal.
 260   void AppendManyToTraversal(const syncable::Directory::Metahandles& handles);
 261
 262   // Adds the specifed handle to the traversal.
 263   void AppendToTraversal(int64 handle);
 264
 265   syncable::Directory::Metahandles* out_;
 266   std::set<int64> added_handles_;
 267   const size_t max_entries_;
 268   syncable::BaseTransaction* trans_;
 269
 270   DISALLOW_COPY_AND_ASSIGN(Traversal);
 271 };
 272
 273 Traversal::Traversal(
 274     syncable::BaseTransaction* trans,
 275     int64 max_entries,
 276     syncable::Directory::Metahandles* out)
 277   : out_(out),
 278     max_entries_(max_entries),
 279     trans_(trans) { }
 280
 281 Traversal::~Traversal() {}
 282
 283 bool Traversal::AddUncommittedParentsAndTheirPredecessors(
 284     const std::set<int64>& ready_unsynced_set,
 285     const syncable::Entry& item,
 286     syncable::Directory::Metahandles* result) const {
 287   syncable::Directory::Metahandles dependencies;
 288   syncable::Id parent_id = item.GetParentId();
 289
 290   // Climb the tree adding entries leaf -> root.
 291   while (!parent_id.ServerKnows()) {
 292     syncable::Entry parent(trans_, syncable::GET_BY_ID, parent_id);
 293     CHECK(parent.good()) << "Bad user-only parent in item path.";
 294     int64 handle = parent.GetMetahandle();
 295     if (HaveItem(handle)) {
 296       // We've already added this parent (and therefore all of its parents).
 297       // We can return early.
 298       break;
 299     }
 300     if (IsEntryInConflict(parent)) {
 301       // We ignore all entries that are children of a conflicing item.  Return
 302       // false immediately to forget the traversal we've built up so far.
 303       DVLOG(1) << "Parent was in conflict, omitting " << item;
 304       return false;
 305     }
 306     AddItemThenPredecessors(ready_unsynced_set,
 307                             parent,
 308                             &dependencies);
 309     parent_id = parent.GetParentId();
 310   }
 311
 312   // Reverse what we added to get the correct order.
 313   result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
 314   return true;
 315 }
 316
 317 // Adds the given item to the list if it is unsynced and ready for commit.
 318 void Traversal::TryAddItem(const std::set<int64>& ready_unsynced_set,
 319                            const syncable::Entry& item,
 320                            syncable::Directory::Metahandles* result) const {
 321   DCHECK(item.GetIsUnsynced());
 322   int64 item_handle = item.GetMetahandle();
 323   if (ready_unsynced_set.count(item_handle) != 0) {
 324     result->push_back(item_handle);
 325   }
 326 }
 327
 328 // Adds the given item, and all its unsynced predecessors.  The traversal will
 329 // be cut short if any item along the traversal is not IS_UNSYNCED, or if we
 330 // detect that this area of the tree has already been traversed.  Items that are
 331 // not 'ready' for commit (see IsEntryReadyForCommit()) will not be added to the
 332 // list, though they will not stop the traversal.
 333 void Traversal::AddItemThenPredecessors(
 334     const std::set<int64>& ready_unsynced_set,
 335     const syncable::Entry& item,
 336     syncable::Directory::Metahandles* result) const {
 337   int64 item_handle = item.GetMetahandle();
 338   if (HaveItem(item_handle)) {
 339     // We've already added this item to the commit set, and so must have
 340     // already added the predecessors as well.
 341     return;
 342   }
 343   TryAddItem(ready_unsynced_set, item, result);
 344   if (item.GetIsDel())
 345     return;  // Deleted items have no predecessors.
 346
 347   syncable::Id prev_id = item.GetPredecessorId();
 348   while (!prev_id.IsRoot()) {
 349     syncable::Entry prev(trans_, syncable::GET_BY_ID, prev_id);
 350     CHECK(prev.good()) << "Bad id when walking predecessors.";
 351     if (!prev.GetIsUnsynced()) {
 352       // We're interested in "runs" of unsynced items.  This item breaks
 353       // the streak, so we stop traversing.
 354       return;
 355     }
 356     int64 handle = prev.GetMetahandle();
 357     if (HaveItem(handle)) {
 358       // We've already added this item to the commit set, and so must have
 359       // already added the predecessors as well.
 360       return;
 361     }
 362     TryAddItem(ready_unsynced_set, prev, result);
 363     prev_id = prev.GetPredecessorId();
 364   }
 365 }
 366
 367 // Same as AddItemThenPredecessor, but the traversal order will be reversed.
 368 void Traversal::AddPredecessorsThenItem(
 369     const std::set<int64>& ready_unsynced_set,
 370     const syncable::Entry& item,
 371     syncable::Directory::Metahandles* result) const {
 372   syncable::Directory::Metahandles dependencies;
 373   AddItemThenPredecessors(ready_unsynced_set, item, &dependencies);
 374
 375   // Reverse what we added to get the correct order.
 376   result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
 377 }
 378
 379 bool Traversal::IsFull() const {
 380   return out_->size() >= max_entries_;
 381 }
 382
 383 bool Traversal::HaveItem(int64 handle) const {
 384   return added_handles_.find(handle) != added_handles_.end();
 385 }
 386
 387 void Traversal::AppendManyToTraversal(
 388     const syncable::Directory::Metahandles& handles) {
 389   out_->insert(out_->end(), handles.begin(), handles.end());
 390   added_handles_.insert(handles.begin(), handles.end());
 391 }
 392
 393 void Traversal::AppendToTraversal(int64 metahandle) {
 394   out_->push_back(metahandle);
 395   added_handles_.insert(metahandle);
 396 }
 397
 398 void Traversal::AddCreatesAndMoves(
 399     const std::set<int64>& ready_unsynced_set) {
 400   // Add moves and creates, and prepend their uncommitted parents.
 401   for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin();
 402        !IsFull() && iter != ready_unsynced_set.end(); ++iter) {
 403     int64 metahandle = *iter;
 404     if (HaveItem(metahandle))
 405       continue;
 406
 407     syncable::Entry entry(trans_,
 408                           syncable::GET_BY_HANDLE,
 409                           metahandle);
 410     if (!entry.GetIsDel()) {
 411       // We only commit an item + its dependencies if it and all its
 412       // dependencies are not in conflict.
 413       syncable::Directory::Metahandles item_dependencies;
 414       if (AddUncommittedParentsAndTheirPredecessors(
 415               ready_unsynced_set,
 416               entry,
 417               &item_dependencies)) {
 418         AddPredecessorsThenItem(ready_unsynced_set,
 419                                 entry,
 420                                 &item_dependencies);
 421         AppendManyToTraversal(item_dependencies);
 422       }
 423     }
 424   }
 425
 426   // It's possible that we overcommitted while trying to expand dependent
 427   // items.  If so, truncate the set down to the allowed size.
 428   if (out_->size() > max_entries_)
 429     out_->resize(max_entries_);
 430 }
 431
 432 void Traversal::AddDeletes(
 433     const std::set<int64>& ready_unsynced_set) {
 434   set<syncable::Id> legal_delete_parents;
 435
 436   for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin();
 437        !IsFull() && iter != ready_unsynced_set.end(); ++iter) {
 438     int64 metahandle = *iter;
 439     if (HaveItem(metahandle))
 440       continue;
 441
 442     syncable::Entry entry(trans_, syncable::GET_BY_HANDLE,
 443                           metahandle);
 444
 445     if (entry.GetIsDel()) {
 446       syncable::Entry parent(trans_, syncable::GET_BY_ID,
 447                              entry.GetParentId());
 448       // If the parent is deleted and unsynced, then any children of that
 449       // parent don't need to be added to the delete queue.
 450       //
 451       // Note: the parent could be synced if there was an update deleting a
 452       // folder when we had a deleted all items in it.
 453       // We may get more updates, or we may want to delete the entry.
 454       if (parent.good() && parent.GetIsDel() && parent.GetIsUnsynced()) {
 455         // However, if an entry is moved, these rules can apply differently.
 456         //
 457         // If the entry was moved, then the destination parent was deleted,
 458         // then we'll miss it in the roll up. We have to add it in manually.
 459         // TODO(chron): Unit test for move / delete cases:
 460         // Case 1: Locally moved, then parent deleted
 461         // Case 2: Server moved, then locally issue recursive delete.
 462         if (entry.GetId().ServerKnows() &&
 463             entry.GetParentId() != entry.GetServerParentId()) {
 464           DVLOG(1) << "Inserting moved and deleted entry, will be missed by "
 465                    << "delete roll." << entry.GetId();
 466
 467           AppendToTraversal(metahandle);
 468         }
 469
 470         // Skip this entry since it's a child of a parent that will be
 471         // deleted. The server will unroll the delete and delete the
 472         // child as well.
 473         continue;
 474       }
 475
 476       legal_delete_parents.insert(entry.GetParentId());
 477     }
 478   }
 479
 480   // We could store all the potential entries with a particular parent during
 481   // the above scan, but instead we rescan here. This is less efficient, but
 482   // we're dropping memory alloc/dealloc in favor of linear scans of recently
 483   // examined entries.
 484   //
 485   // Scan through the UnsyncedMetaHandles again. If we have a deleted
 486   // entry, then check if the parent is in legal_delete_parents.
 487   //
 488   // Parent being in legal_delete_parents means for the child:
 489   //   a recursive delete is not currently happening (no recent deletes in same
 490   //     folder)
 491   //   parent did expect at least one old deleted child
 492   //   parent was not deleted
 493   for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin();
 494        !IsFull() && iter != ready_unsynced_set.end(); ++iter) {
 495     int64 metahandle = *iter;
 496     if (HaveItem(metahandle))
 497       continue;
 498     syncable::Entry entry(trans_, syncable::GET_BY_HANDLE, metahandle);
 499     if (entry.GetIsDel()) {
 500       syncable::Id parent_id = entry.GetParentId();
 501       if (legal_delete_parents.count(parent_id)) {
 502         AppendToTraversal(metahandle);
 503       }
 504     }
 505   }
 506 }
 507
 508 void OrderCommitIds(
 509     syncable::BaseTransaction* trans,
 510     size_t max_entries,
 511     const std::set<int64>& ready_unsynced_set,
 512     syncable::Directory::Metahandles* out) {
 513   // Commits follow these rules:
 514   // 1. Moves or creates are preceded by needed folder creates, from
 515   //    root to leaf.  For folders whose contents are ordered, moves
 516   //    and creates appear in order.
 517   // 2. Moves/Creates before deletes.
 518   // 3. Deletes, collapsed.
 519   // We commit deleted moves under deleted items as moves when collapsing
 520   // delete trees.
 521
 522   Traversal traversal(trans, max_entries, out);
 523
 524   // Add moves and creates, and prepend their uncommitted parents.
 525   traversal.AddCreatesAndMoves(ready_unsynced_set);
 526
 527   // Add all deletes.
 528   traversal.AddDeletes(ready_unsynced_set);
 529 }
 530
 531 }  // namespace
 532
 533 }  // namespace syncer