| // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "sync/engine/get_commit_ids_command.h" |
| |
| #include <set> |
| #include <utility> |
| #include <vector> |
| |
| #include "sync/engine/syncer_util.h" |
| #include "sync/engine/throttled_data_type_tracker.h" |
| #include "sync/syncable/entry.h" |
| #include "sync/syncable/mutable_entry.h" |
| #include "sync/syncable/nigori_handler.h" |
| #include "sync/syncable/nigori_util.h" |
| #include "sync/syncable/syncable_util.h" |
| #include "sync/syncable/write_transaction.h" |
| #include "sync/util/cryptographer.h" |
| |
| using std::set; |
| using std::vector; |
| |
| namespace syncer { |
| |
| using sessions::OrderedCommitSet; |
| using sessions::SyncSession; |
| using sessions::StatusController; |
| |
| GetCommitIdsCommand::GetCommitIdsCommand( |
| const size_t commit_batch_size, |
| sessions::OrderedCommitSet* commit_set) |
| : requested_commit_batch_size_(commit_batch_size), |
| commit_set_(commit_set) { |
| } |
| |
| GetCommitIdsCommand::~GetCommitIdsCommand() {} |
| |
| SyncerError GetCommitIdsCommand::ExecuteImpl(SyncSession* session) { |
| // Gather the full set of unsynced items and store it in the session. They |
| // are not in the correct order for commit. |
| std::set<int64> ready_unsynced_set; |
| syncable::Directory::UnsyncedMetaHandles all_unsynced_handles; |
| GetUnsyncedEntries(session->write_transaction(), |
| &all_unsynced_handles); |
| |
| ModelTypeSet encrypted_types; |
| bool passphrase_missing = false; |
| Cryptographer* cryptographer = |
| session->context()-> |
| directory()->GetCryptographer(session->write_transaction()); |
| if (cryptographer) { |
| encrypted_types = session->context()->directory()->GetNigoriHandler()-> |
| GetEncryptedTypes(session->write_transaction()); |
| passphrase_missing = cryptographer->has_pending_keys(); |
| }; |
| |
| const ModelTypeSet throttled_types = |
| session->context()->throttled_data_type_tracker()->GetThrottledTypes(); |
| // We filter out all unready entries from the set of unsynced handles. This |
| // new set of ready and unsynced items (which excludes throttled items as |
| // well) is then what we use to determine what is a candidate for commit. |
| FilterUnreadyEntries(session->write_transaction(), |
| throttled_types, |
| encrypted_types, |
| passphrase_missing, |
| all_unsynced_handles, |
| &ready_unsynced_set); |
| |
| BuildCommitIds(session->write_transaction(), |
| session->routing_info(), |
| ready_unsynced_set); |
| |
| const vector<syncable::Id>& verified_commit_ids = |
| commit_set_->GetAllCommitIds(); |
| |
| for (size_t i = 0; i < verified_commit_ids.size(); i++) |
| DVLOG(1) << "Debug commit batch result:" << verified_commit_ids[i]; |
| |
| return SYNCER_OK; |
| } |
| |
| namespace { |
| |
| bool IsEntryInConflict(const syncable::Entry& entry) { |
| if (entry.Get(syncable::IS_UNSYNCED) && |
| entry.Get(syncable::SERVER_VERSION) > 0 && |
| (entry.Get(syncable::SERVER_VERSION) > |
| entry.Get(syncable::BASE_VERSION))) { |
| // The local and server versions don't match. The item must be in |
| // conflict, so there's no point in attempting to commit. |
| DCHECK(entry.Get(syncable::IS_UNAPPLIED_UPDATE)); |
| DVLOG(1) << "Excluding entry from commit due to version mismatch " |
| << entry; |
| return true; |
| } |
| return false; |
| } |
| |
| // An entry is not considered ready for commit if any are true: |
| // 1. It's in conflict. |
| // 2. It requires encryption (either the type is encrypted but a passphrase |
| // is missing from the cryptographer, or the entry itself wasn't properly |
| // encrypted). |
| // 3. It's type is currently throttled. |
| // 4. It's a delete but has not been committed. |
| bool IsEntryReadyForCommit(ModelTypeSet throttled_types, |
| ModelTypeSet encrypted_types, |
| bool passphrase_missing, |
| const syncable::Entry& entry) { |
| DCHECK(entry.Get(syncable::IS_UNSYNCED)); |
| if (IsEntryInConflict(entry)) |
| return false; |
| |
| const ModelType type = entry.GetModelType(); |
| // We special case the nigori node because even though it is considered an |
| // "encrypted type", not all nigori node changes require valid encryption |
| // (ex: sync_tabs). |
| if ((type != NIGORI) && encrypted_types.Has(type) && |
| (passphrase_missing || |
| syncable::EntryNeedsEncryption(encrypted_types, entry))) { |
| // This entry requires encryption but is not properly encrypted (possibly |
| // due to the cryptographer not being initialized or the user hasn't |
| // provided the most recent passphrase). |
| DVLOG(1) << "Excluding entry from commit due to lack of encryption " |
| << entry; |
| return false; |
| } |
| |
| // Look at the throttled types. |
| if (throttled_types.Has(type)) |
| return false; |
| |
| if (entry.Get(syncable::IS_DEL) && !entry.Get(syncable::ID).ServerKnows()) { |
| // New clients (following the resolution of crbug.com/125381) should not |
| // create such items. Old clients may have left some in the database |
| // (crbug.com/132905), but we should now be cleaning them on startup. |
| NOTREACHED() << "Found deleted and unsynced local item: " << entry; |
| return false; |
| } |
| |
| // Extra validity checks. |
| syncable::Id id = entry.Get(syncable::ID); |
| if (id == entry.Get(syncable::PARENT_ID)) { |
| CHECK(id.IsRoot()) << "Non-root item is self parenting." << entry; |
| // If the root becomes unsynced it can cause us problems. |
| NOTREACHED() << "Root item became unsynced " << entry; |
| return false; |
| } |
| |
| if (entry.IsRoot()) { |
| NOTREACHED() << "Permanent item became unsynced " << entry; |
| return false; |
| } |
| |
| DVLOG(2) << "Entry is ready for commit: " << entry; |
| return true; |
| } |
| |
| } // namespace |
| |
| void GetCommitIdsCommand::FilterUnreadyEntries( |
| syncable::BaseTransaction* trans, |
| ModelTypeSet throttled_types, |
| ModelTypeSet encrypted_types, |
| bool passphrase_missing, |
| const syncable::Directory::UnsyncedMetaHandles& unsynced_handles, |
| std::set<int64>* ready_unsynced_set) { |
| for (syncable::Directory::UnsyncedMetaHandles::const_iterator iter = |
| unsynced_handles.begin(); iter != unsynced_handles.end(); ++iter) { |
| syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter); |
| if (IsEntryReadyForCommit(throttled_types, |
| encrypted_types, |
| passphrase_missing, |
| entry)) { |
| ready_unsynced_set->insert(*iter); |
| } |
| } |
| } |
| |
| bool GetCommitIdsCommand::AddUncommittedParentsAndTheirPredecessors( |
| syncable::BaseTransaction* trans, |
| const ModelSafeRoutingInfo& routes, |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| sessions::OrderedCommitSet* result) const { |
| OrderedCommitSet item_dependencies(routes); |
| syncable::Id parent_id = item.Get(syncable::PARENT_ID); |
| |
| // Climb the tree adding entries leaf -> root. |
| while (!parent_id.ServerKnows()) { |
| syncable::Entry parent(trans, syncable::GET_BY_ID, parent_id); |
| CHECK(parent.good()) << "Bad user-only parent in item path."; |
| int64 handle = parent.Get(syncable::META_HANDLE); |
| if (commit_set_->HaveCommitItem(handle)) { |
| // We've already added this parent (and therefore all of its parents). |
| // We can return early. |
| break; |
| } |
| if (!AddItemThenPredecessors(trans, ready_unsynced_set, parent, |
| &item_dependencies)) { |
| // There was a parent/predecessor in conflict. We return without adding |
| // anything to |commit_set|. |
| DVLOG(1) << "Parent or parent's predecessor was in conflict, omitting " |
| << item; |
| return false; |
| } |
| parent_id = parent.Get(syncable::PARENT_ID); |
| } |
| |
| // Reverse what we added to get the correct order. |
| result->AppendReverse(item_dependencies); |
| return true; |
| } |
| |
| bool GetCommitIdsCommand::AddItem(const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| OrderedCommitSet* result) const { |
| DCHECK(item.Get(syncable::IS_UNSYNCED)); |
| // An item in conflict means that dependent items (successors and children) |
| // cannot be added either. |
| if (IsEntryInConflict(item)) |
| return false; |
| int64 item_handle = item.Get(syncable::META_HANDLE); |
| if (ready_unsynced_set.count(item_handle) == 0) { |
| // It's not in conflict, but not ready for commit. Just return true without |
| // adding it to the commit set. |
| return true; |
| } |
| result->AddCommitItem(item_handle, item.Get(syncable::ID), |
| item.GetModelType()); |
| return true; |
| } |
| |
| bool GetCommitIdsCommand::AddItemThenPredecessors( |
| syncable::BaseTransaction* trans, |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| OrderedCommitSet* result) const { |
| int64 item_handle = item.Get(syncable::META_HANDLE); |
| if (commit_set_->HaveCommitItem(item_handle)) { |
| // We've already added this item to the commit set, and so must have |
| // already added the predecessors as well. |
| return true; |
| } |
| if (!AddItem(ready_unsynced_set, item, result)) |
| return false; // Item is in conflict. |
| if (item.Get(syncable::IS_DEL)) |
| return true; // Deleted items have no predecessors. |
| |
| syncable::Id prev_id = item.Get(syncable::PREV_ID); |
| while (!prev_id.IsRoot()) { |
| syncable::Entry prev(trans, syncable::GET_BY_ID, prev_id); |
| CHECK(prev.good()) << "Bad id when walking predecessors."; |
| if (!prev.Get(syncable::IS_UNSYNCED)) |
| break; |
| int64 handle = prev.Get(syncable::META_HANDLE); |
| if (commit_set_->HaveCommitItem(handle)) { |
| // We've already added this item to the commit set, and so must have |
| // already added the predecessors as well. |
| return true; |
| } |
| if (!AddItem(ready_unsynced_set, prev, result)) |
| return false; // Item is in conflict. |
| prev_id = prev.Get(syncable::PREV_ID); |
| } |
| return true; |
| } |
| |
| bool GetCommitIdsCommand::AddPredecessorsThenItem( |
| syncable::BaseTransaction* trans, |
| const ModelSafeRoutingInfo& routes, |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| OrderedCommitSet* result) const { |
| OrderedCommitSet item_dependencies(routes); |
| if (!AddItemThenPredecessors(trans, ready_unsynced_set, item, |
| &item_dependencies)) { |
| // Either the item or its predecessors are in conflict, so don't add any |
| // items to the commit set. |
| DVLOG(1) << "Predecessor was in conflict, omitting " << item; |
| return false; |
| } |
| |
| // Reverse what we added to get the correct order. |
| result->AppendReverse(item_dependencies); |
| return true; |
| } |
| |
| bool GetCommitIdsCommand::IsCommitBatchFull() const { |
| return commit_set_->Size() >= requested_commit_batch_size_; |
| } |
| |
| void GetCommitIdsCommand::AddCreatesAndMoves( |
| syncable::WriteTransaction* write_transaction, |
| const ModelSafeRoutingInfo& routes, |
| const std::set<int64>& ready_unsynced_set) { |
| // Add moves and creates, and prepend their uncommitted parents. |
| for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin(); |
| !IsCommitBatchFull() && iter != ready_unsynced_set.end(); ++iter) { |
| int64 metahandle = *iter; |
| if (commit_set_->HaveCommitItem(metahandle)) |
| continue; |
| |
| syncable::Entry entry(write_transaction, |
| syncable::GET_BY_HANDLE, |
| metahandle); |
| if (!entry.Get(syncable::IS_DEL)) { |
| // We only commit an item + its dependencies if it and all its |
| // dependencies are not in conflict. |
| OrderedCommitSet item_dependencies(routes); |
| if (AddUncommittedParentsAndTheirPredecessors( |
| write_transaction, |
| routes, |
| ready_unsynced_set, |
| entry, |
| &item_dependencies) && |
| AddPredecessorsThenItem(write_transaction, |
| routes, |
| ready_unsynced_set, |
| entry, |
| &item_dependencies)) { |
| commit_set_->Append(item_dependencies); |
| } |
| } |
| } |
| |
| // It's possible that we overcommitted while trying to expand dependent |
| // items. If so, truncate the set down to the allowed size. |
| commit_set_->Truncate(requested_commit_batch_size_); |
| } |
| |
| void GetCommitIdsCommand::AddDeletes( |
| syncable::WriteTransaction* write_transaction, |
| const std::set<int64>& ready_unsynced_set) { |
| set<syncable::Id> legal_delete_parents; |
| |
| for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin(); |
| !IsCommitBatchFull() && iter != ready_unsynced_set.end(); ++iter) { |
| int64 metahandle = *iter; |
| if (commit_set_->HaveCommitItem(metahandle)) |
| continue; |
| |
| syncable::Entry entry(write_transaction, syncable::GET_BY_HANDLE, |
| metahandle); |
| |
| if (entry.Get(syncable::IS_DEL)) { |
| syncable::Entry parent(write_transaction, syncable::GET_BY_ID, |
| entry.Get(syncable::PARENT_ID)); |
| // If the parent is deleted and unsynced, then any children of that |
| // parent don't need to be added to the delete queue. |
| // |
| // Note: the parent could be synced if there was an update deleting a |
| // folder when we had a deleted all items in it. |
| // We may get more updates, or we may want to delete the entry. |
| if (parent.good() && |
| parent.Get(syncable::IS_DEL) && |
| parent.Get(syncable::IS_UNSYNCED)) { |
| // However, if an entry is moved, these rules can apply differently. |
| // |
| // If the entry was moved, then the destination parent was deleted, |
| // then we'll miss it in the roll up. We have to add it in manually. |
| // TODO(chron): Unit test for move / delete cases: |
| // Case 1: Locally moved, then parent deleted |
| // Case 2: Server moved, then locally issue recursive delete. |
| if (entry.Get(syncable::ID).ServerKnows() && |
| entry.Get(syncable::PARENT_ID) != |
| entry.Get(syncable::SERVER_PARENT_ID)) { |
| DVLOG(1) << "Inserting moved and deleted entry, will be missed by " |
| << "delete roll." << entry.Get(syncable::ID); |
| |
| commit_set_->AddCommitItem(metahandle, |
| entry.Get(syncable::ID), |
| entry.GetModelType()); |
| } |
| |
| // Skip this entry since it's a child of a parent that will be |
| // deleted. The server will unroll the delete and delete the |
| // child as well. |
| continue; |
| } |
| |
| legal_delete_parents.insert(entry.Get(syncable::PARENT_ID)); |
| } |
| } |
| |
| // We could store all the potential entries with a particular parent during |
| // the above scan, but instead we rescan here. This is less efficient, but |
| // we're dropping memory alloc/dealloc in favor of linear scans of recently |
| // examined entries. |
| // |
| // Scan through the UnsyncedMetaHandles again. If we have a deleted |
| // entry, then check if the parent is in legal_delete_parents. |
| // |
| // Parent being in legal_delete_parents means for the child: |
| // a recursive delete is not currently happening (no recent deletes in same |
| // folder) |
| // parent did expect at least one old deleted child |
| // parent was not deleted |
| for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin(); |
| !IsCommitBatchFull() && iter != ready_unsynced_set.end(); ++iter) { |
| int64 metahandle = *iter; |
| if (commit_set_->HaveCommitItem(metahandle)) |
| continue; |
| syncable::MutableEntry entry(write_transaction, syncable::GET_BY_HANDLE, |
| metahandle); |
| if (entry.Get(syncable::IS_DEL)) { |
| syncable::Id parent_id = entry.Get(syncable::PARENT_ID); |
| if (legal_delete_parents.count(parent_id)) { |
| commit_set_->AddCommitItem(metahandle, entry.Get(syncable::ID), |
| entry.GetModelType()); |
| } |
| } |
| } |
| } |
| |
| void GetCommitIdsCommand::BuildCommitIds( |
| syncable::WriteTransaction* write_transaction, |
| const ModelSafeRoutingInfo& routes, |
| const std::set<int64>& ready_unsynced_set) { |
| // Commits follow these rules: |
| // 1. Moves or creates are preceded by needed folder creates, from |
| // root to leaf. For folders whose contents are ordered, moves |
| // and creates appear in order. |
| // 2. Moves/Creates before deletes. |
| // 3. Deletes, collapsed. |
| // We commit deleted moves under deleted items as moves when collapsing |
| // delete trees. |
| |
| // Add moves and creates, and prepend their uncommitted parents. |
| AddCreatesAndMoves(write_transaction, routes, ready_unsynced_set); |
| |
| // Add all deletes. |
| AddDeletes(write_transaction, ready_unsynced_set); |
| } |
| |
| } // namespace syncer |