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 534