1 // Copyright 2012 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_command.h" 6 7 #include <set> 8 #include <utility> 9 #include <vector> 10 11 #include "sync/engine/syncer_util.h" 12 #include "sync/sessions/nudge_tracker.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 using sessions::OrderedCommitSet; 26 using sessions::SyncSession; 27 using sessions::StatusController; 28 29 GetCommitIdsCommand::GetCommitIdsCommand( 30 syncable::BaseTransaction* trans, 31 ModelTypeSet requested_types, 32 const size_t commit_batch_size, 33 sessions::OrderedCommitSet* commit_set) 34 : trans_(trans), 35 requested_types_(requested_types), 36 requested_commit_batch_size_(commit_batch_size), 37 commit_set_(commit_set) { 38 } 39 40 GetCommitIdsCommand::~GetCommitIdsCommand() {} 41 42 SyncerError GetCommitIdsCommand::ExecuteImpl(SyncSession* session) { 43 // Gather the full set of unsynced items and store it in the session. They 44 // are not in the correct order for commit. 45 std::set<int64> ready_unsynced_set; 46 syncable::Directory::Metahandles all_unsynced_handles; 47 GetUnsyncedEntries(trans_, 48 &all_unsynced_handles); 49 50 ModelTypeSet encrypted_types; 51 bool passphrase_missing = false; 52 Cryptographer* cryptographer = 53 session->context()-> 54 directory()->GetCryptographer(trans_); 55 if (cryptographer) { 56 encrypted_types = session->context()->directory()->GetNigoriHandler()-> 57 GetEncryptedTypes(trans_); 58 passphrase_missing = cryptographer->has_pending_keys(); 59 }; 60 61 // We filter out all unready entries from the set of unsynced handles. This 62 // new set of ready and unsynced items is then what we use to determine what 63 // is a candidate for commit. The caller of this SyncerCommand is responsible 64 // for ensuring that no throttled types are included among the 65 // requested_types. 66 FilterUnreadyEntries(trans_, 67 requested_types_, 68 encrypted_types, 69 passphrase_missing, 70 all_unsynced_handles, 71 &ready_unsynced_set); 72 73 BuildCommitIds(trans_, 74 session->context()->routing_info(), 75 ready_unsynced_set); 76 77 const vector<syncable::Id>& verified_commit_ids = 78 commit_set_->GetAllCommitIds(); 79 80 for (size_t i = 0; i < verified_commit_ids.size(); i++) 81 DVLOG(1) << "Debug commit batch result:" << verified_commit_ids[i]; 82 83 return SYNCER_OK; 84 } 85 86 namespace { 87 88 bool IsEntryInConflict(const syncable::Entry& entry) { 89 if (entry.Get(syncable::IS_UNSYNCED) && 90 entry.Get(syncable::SERVER_VERSION) > 0 && 91 (entry.Get(syncable::SERVER_VERSION) > 92 entry.Get(syncable::BASE_VERSION))) { 93 // The local and server versions don't match. The item must be in 94 // conflict, so there's no point in attempting to commit. 95 DCHECK(entry.Get(syncable::IS_UNAPPLIED_UPDATE)); 96 DVLOG(1) << "Excluding entry from commit due to version mismatch " 97 << entry; 98 return true; 99 } 100 return false; 101 } 102 103 // An entry is not considered ready for commit if any are true: 104 // 1. It's in conflict. 105 // 2. It requires encryption (either the type is encrypted but a passphrase 106 // is missing from the cryptographer, or the entry itself wasn't properly 107 // encrypted). 108 // 3. It's type is currently throttled. 109 // 4. It's a delete but has not been committed. 110 bool IsEntryReadyForCommit(ModelTypeSet requested_types, 111 ModelTypeSet encrypted_types, 112 bool passphrase_missing, 113 const syncable::Entry& entry) { 114 DCHECK(entry.Get(syncable::IS_UNSYNCED)); 115 if (IsEntryInConflict(entry)) 116 return false; 117 118 const ModelType type = entry.GetModelType(); 119 // We special case the nigori node because even though it is considered an 120 // "encrypted type", not all nigori node changes require valid encryption 121 // (ex: sync_tabs). 122 if ((type != NIGORI) && encrypted_types.Has(type) && 123 (passphrase_missing || 124 syncable::EntryNeedsEncryption(encrypted_types, entry))) { 125 // This entry requires encryption but is not properly encrypted (possibly 126 // due to the cryptographer not being initialized or the user hasn't 127 // provided the most recent passphrase). 128 DVLOG(1) << "Excluding entry from commit due to lack of encryption " 129 << entry; 130 return false; 131 } 132 133 // Ignore it if it's not in our set of requested types. 134 if (!requested_types.Has(type)) 135 return false; 136 137 if (entry.Get(syncable::IS_DEL) && !entry.Get(syncable::ID).ServerKnows()) { 138 // New clients (following the resolution of crbug.com/125381) should not 139 // create such items. Old clients may have left some in the database 140 // (crbug.com/132905), but we should now be cleaning them on startup. 141 NOTREACHED() << "Found deleted and unsynced local item: " << entry; 142 return false; 143 } 144 145 // Extra validity checks. 146 syncable::Id id = entry.Get(syncable::ID); 147 if (id == entry.Get(syncable::PARENT_ID)) { 148 CHECK(id.IsRoot()) << "Non-root item is self parenting." << entry; 149 // If the root becomes unsynced it can cause us problems. 150 NOTREACHED() << "Root item became unsynced " << entry; 151 return false; 152 } 153 154 if (entry.IsRoot()) { 155 NOTREACHED() << "Permanent item became unsynced " << entry; 156 return false; 157 } 158 159 DVLOG(2) << "Entry is ready for commit: " << entry; 160 return true; 161 } 162 163 } // namespace 164 165 void GetCommitIdsCommand::FilterUnreadyEntries( 166 syncable::BaseTransaction* trans, 167 ModelTypeSet requested_types, 168 ModelTypeSet encrypted_types, 169 bool passphrase_missing, 170 const syncable::Directory::Metahandles& unsynced_handles, 171 std::set<int64>* ready_unsynced_set) { 172 for (syncable::Directory::Metahandles::const_iterator iter = 173 unsynced_handles.begin(); iter != unsynced_handles.end(); ++iter) { 174 syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter); 175 if (IsEntryReadyForCommit(requested_types, 176 encrypted_types, 177 passphrase_missing, 178 entry)) { 179 ready_unsynced_set->insert(*iter); 180 } 181 } 182 } 183 184 bool GetCommitIdsCommand::AddUncommittedParentsAndTheirPredecessors( 185 syncable::BaseTransaction* trans, 186 const ModelSafeRoutingInfo& routes, 187 const std::set<int64>& ready_unsynced_set, 188 const syncable::Entry& item, 189 sessions::OrderedCommitSet* result) const { 190 OrderedCommitSet item_dependencies(routes); 191 syncable::Id parent_id = item.Get(syncable::PARENT_ID); 192 193 // Climb the tree adding entries leaf -> root. 194 while (!parent_id.ServerKnows()) { 195 syncable::Entry parent(trans, syncable::GET_BY_ID, parent_id); 196 CHECK(parent.good()) << "Bad user-only parent in item path."; 197 int64 handle = parent.Get(syncable::META_HANDLE); 198 if (commit_set_->HaveCommitItem(handle)) { 199 // We've already added this parent (and therefore all of its parents). 200 // We can return early. 201 break; 202 } 203 if (IsEntryInConflict(parent)) { 204 // We ignore all entries that are children of a conflicing item. Return 205 // false immediately to forget the traversal we've built up so far. 206 DVLOG(1) << "Parent was in conflict, omitting " << item; 207 return false; 208 } 209 AddItemThenPredecessors(trans, 210 ready_unsynced_set, 211 parent, 212 &item_dependencies); 213 parent_id = parent.Get(syncable::PARENT_ID); 214 } 215 216 // Reverse what we added to get the correct order. 217 result->AppendReverse(item_dependencies); 218 return true; 219 } 220 221 // Adds the given item to the list if it is unsynced and ready for commit. 222 void GetCommitIdsCommand::TryAddItem(const std::set<int64>& ready_unsynced_set, 223 const syncable::Entry& item, 224 OrderedCommitSet* result) const { 225 DCHECK(item.Get(syncable::IS_UNSYNCED)); 226 int64 item_handle = item.Get(syncable::META_HANDLE); 227 if (ready_unsynced_set.count(item_handle) != 0) { 228 result->AddCommitItem(item_handle, item.Get(syncable::ID), 229 item.GetModelType()); 230 } 231 } 232 233 // Adds the given item, and all its unsynced predecessors. The traversal will 234 // be cut short if any item along the traversal is not IS_UNSYNCED, or if we 235 // detect that this area of the tree has already been traversed. Items that are 236 // not 'ready' for commit (see IsEntryReadyForCommit()) will not be added to the 237 // list, though they will not stop the traversal. 238 void GetCommitIdsCommand::AddItemThenPredecessors( 239 syncable::BaseTransaction* trans, 240 const std::set<int64>& ready_unsynced_set, 241 const syncable::Entry& item, 242 OrderedCommitSet* result) const { 243 int64 item_handle = item.Get(syncable::META_HANDLE); 244 if (commit_set_->HaveCommitItem(item_handle)) { 245 // We've already added this item to the commit set, and so must have 246 // already added the predecessors as well. 247 return; 248 } 249 TryAddItem(ready_unsynced_set, item, result); 250 if (item.Get(syncable::IS_DEL)) 251 return; // Deleted items have no predecessors. 252 253 syncable::Id prev_id = item.GetPredecessorId(); 254 while (!prev_id.IsRoot()) { 255 syncable::Entry prev(trans, syncable::GET_BY_ID, prev_id); 256 CHECK(prev.good()) << "Bad id when walking predecessors."; 257 if (!prev.Get(syncable::IS_UNSYNCED)) { 258 // We're interested in "runs" of unsynced items. This item breaks 259 // the streak, so we stop traversing. 260 return; 261 } 262 int64 handle = prev.Get(syncable::META_HANDLE); 263 if (commit_set_->HaveCommitItem(handle)) { 264 // We've already added this item to the commit set, and so must have 265 // already added the predecessors as well. 266 return; 267 } 268 TryAddItem(ready_unsynced_set, prev, result); 269 prev_id = prev.GetPredecessorId(); 270 } 271 } 272 273 // Same as AddItemThenPredecessor, but the traversal order will be reversed. 274 void GetCommitIdsCommand::AddPredecessorsThenItem( 275 syncable::BaseTransaction* trans, 276 const ModelSafeRoutingInfo& routes, 277 const std::set<int64>& ready_unsynced_set, 278 const syncable::Entry& item, 279 OrderedCommitSet* result) const { 280 OrderedCommitSet item_dependencies(routes); 281 AddItemThenPredecessors(trans, ready_unsynced_set, item, &item_dependencies); 282 283 // Reverse what we added to get the correct order. 284 result->AppendReverse(item_dependencies); 285 } 286 287 bool GetCommitIdsCommand::IsCommitBatchFull() const { 288 return commit_set_->Size() >= requested_commit_batch_size_; 289 } 290 291 void GetCommitIdsCommand::AddCreatesAndMoves( 292 syncable::BaseTransaction* trans, 293 const ModelSafeRoutingInfo& routes, 294 const std::set<int64>& ready_unsynced_set) { 295 // Add moves and creates, and prepend their uncommitted parents. 296 for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin(); 297 !IsCommitBatchFull() && iter != ready_unsynced_set.end(); ++iter) { 298 int64 metahandle = *iter; 299 if (commit_set_->HaveCommitItem(metahandle)) 300 continue; 301 302 syncable::Entry entry(trans, 303 syncable::GET_BY_HANDLE, 304 metahandle); 305 if (!entry.Get(syncable::IS_DEL)) { 306 // We only commit an item + its dependencies if it and all its 307 // dependencies are not in conflict. 308 OrderedCommitSet item_dependencies(routes); 309 if (AddUncommittedParentsAndTheirPredecessors( 310 trans, 311 routes, 312 ready_unsynced_set, 313 entry, 314 &item_dependencies)) { 315 AddPredecessorsThenItem(trans, 316 routes, 317 ready_unsynced_set, 318 entry, 319 &item_dependencies); 320 commit_set_->Append(item_dependencies); 321 } 322 } 323 } 324 325 // It's possible that we overcommitted while trying to expand dependent 326 // items. If so, truncate the set down to the allowed size. 327 commit_set_->Truncate(requested_commit_batch_size_); 328 } 329 330 void GetCommitIdsCommand::AddDeletes( 331 syncable::BaseTransaction* trans, 332 const std::set<int64>& ready_unsynced_set) { 333 set<syncable::Id> legal_delete_parents; 334 335 for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin(); 336 !IsCommitBatchFull() && iter != ready_unsynced_set.end(); ++iter) { 337 int64 metahandle = *iter; 338 if (commit_set_->HaveCommitItem(metahandle)) 339 continue; 340 341 syncable::Entry entry(trans, syncable::GET_BY_HANDLE, 342 metahandle); 343 344 if (entry.Get(syncable::IS_DEL)) { 345 syncable::Entry parent(trans, syncable::GET_BY_ID, 346 entry.Get(syncable::PARENT_ID)); 347 // If the parent is deleted and unsynced, then any children of that 348 // parent don't need to be added to the delete queue. 349 // 350 // Note: the parent could be synced if there was an update deleting a 351 // folder when we had a deleted all items in it. 352 // We may get more updates, or we may want to delete the entry. 353 if (parent.good() && 354 parent.Get(syncable::IS_DEL) && 355 parent.Get(syncable::IS_UNSYNCED)) { 356 // However, if an entry is moved, these rules can apply differently. 357 // 358 // If the entry was moved, then the destination parent was deleted, 359 // then we'll miss it in the roll up. We have to add it in manually. 360 // TODO(chron): Unit test for move / delete cases: 361 // Case 1: Locally moved, then parent deleted 362 // Case 2: Server moved, then locally issue recursive delete. 363 if (entry.Get(syncable::ID).ServerKnows() && 364 entry.Get(syncable::PARENT_ID) != 365 entry.Get(syncable::SERVER_PARENT_ID)) { 366 DVLOG(1) << "Inserting moved and deleted entry, will be missed by " 367 << "delete roll." << entry.Get(syncable::ID); 368 369 commit_set_->AddCommitItem(metahandle, 370 entry.Get(syncable::ID), 371 entry.GetModelType()); 372 } 373 374 // Skip this entry since it's a child of a parent that will be 375 // deleted. The server will unroll the delete and delete the 376 // child as well. 377 continue; 378 } 379 380 legal_delete_parents.insert(entry.Get(syncable::PARENT_ID)); 381 } 382 } 383 384 // We could store all the potential entries with a particular parent during 385 // the above scan, but instead we rescan here. This is less efficient, but 386 // we're dropping memory alloc/dealloc in favor of linear scans of recently 387 // examined entries. 388 // 389 // Scan through the UnsyncedMetaHandles again. If we have a deleted 390 // entry, then check if the parent is in legal_delete_parents. 391 // 392 // Parent being in legal_delete_parents means for the child: 393 // a recursive delete is not currently happening (no recent deletes in same 394 // folder) 395 // parent did expect at least one old deleted child 396 // parent was not deleted 397 for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin(); 398 !IsCommitBatchFull() && iter != ready_unsynced_set.end(); ++iter) { 399 int64 metahandle = *iter; 400 if (commit_set_->HaveCommitItem(metahandle)) 401 continue; 402 syncable::Entry entry(trans, syncable::GET_BY_HANDLE, 403 metahandle); 404 if (entry.Get(syncable::IS_DEL)) { 405 syncable::Id parent_id = entry.Get(syncable::PARENT_ID); 406 if (legal_delete_parents.count(parent_id)) { 407 commit_set_->AddCommitItem(metahandle, entry.Get(syncable::ID), 408 entry.GetModelType()); 409 } 410 } 411 } 412 } 413 414 void GetCommitIdsCommand::BuildCommitIds( 415 syncable::BaseTransaction* trans, 416 const ModelSafeRoutingInfo& routes, 417 const std::set<int64>& ready_unsynced_set) { 418 // Commits follow these rules: 419 // 1. Moves or creates are preceded by needed folder creates, from 420 // root to leaf. For folders whose contents are ordered, moves 421 // and creates appear in order. 422 // 2. Moves/Creates before deletes. 423 // 3. Deletes, collapsed. 424 // We commit deleted moves under deleted items as moves when collapsing 425 // delete trees. 426 427 // Add moves and creates, and prepend their uncommitted parents. 428 AddCreatesAndMoves(trans, routes, ready_unsynced_set); 429 430 // Add all deletes. 431 AddDeletes(trans, ready_unsynced_set); 432 } 433 434 } // namespace syncer 435