| // Copyright 2013 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.h" |
| |
| #include <set> |
| #include <vector> |
| |
| #include "base/basictypes.h" |
| #include "sync/engine/syncer_util.h" |
| #include "sync/syncable/directory.h" |
| #include "sync/syncable/entry.h" |
| #include "sync/syncable/nigori_handler.h" |
| #include "sync/syncable/nigori_util.h" |
| #include "sync/syncable/syncable_base_transaction.h" |
| #include "sync/syncable/syncable_util.h" |
| #include "sync/util/cryptographer.h" |
| |
| using std::set; |
| using std::vector; |
| |
| namespace syncer { |
| |
| namespace { |
| |
| // Forward-declare some helper functions. This gives us more options for |
| // ordering the function defintions within this file. |
| |
| // Filters |unsynced_handles| to remove all entries that do not belong to the |
| // specified |requested_types|, or are not eligible for a commit at this time. |
| void FilterUnreadyEntries( |
| syncable::BaseTransaction* trans, |
| ModelTypeSet requested_types, |
| ModelTypeSet encrypted_types, |
| bool passphrase_missing, |
| const syncable::Directory::Metahandles& unsynced_handles, |
| std::set<int64>* ready_unsynced_set); |
| |
| // Given a set of commit metahandles that are ready for commit |
| // (|ready_unsynced_set|), sorts these into commit order and places up to |
| // |max_entries| of them in the output parameter |out|. |
| // |
| // See the header file for an explanation of commit ordering. |
| void OrderCommitIds( |
| syncable::BaseTransaction* trans, |
| size_t max_entries, |
| const std::set<int64>& ready_unsynced_set, |
| std::vector<int64>* out); |
| |
| } // namespace |
| |
| void GetCommitIdsForType( |
| syncable::BaseTransaction* trans, |
| ModelType type, |
| size_t max_entries, |
| syncable::Directory::Metahandles* out) { |
| syncable::Directory* dir = trans->directory(); |
| |
| // 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::Metahandles all_unsynced_handles; |
| GetUnsyncedEntries(trans, &all_unsynced_handles); |
| |
| ModelTypeSet encrypted_types; |
| bool passphrase_missing = false; |
| Cryptographer* cryptographer = dir->GetCryptographer(trans); |
| if (cryptographer) { |
| encrypted_types = dir->GetNigoriHandler()->GetEncryptedTypes(trans); |
| passphrase_missing = cryptographer->has_pending_keys(); |
| }; |
| |
| // We filter out all unready entries from the set of unsynced handles. This |
| // new set of ready and unsynced items is then what we use to determine what |
| // is a candidate for commit. The caller is responsible for ensuring that no |
| // throttled types are included among the requested_types. |
| FilterUnreadyEntries(trans, |
| ModelTypeSet(type), |
| encrypted_types, |
| passphrase_missing, |
| all_unsynced_handles, |
| &ready_unsynced_set); |
| |
| OrderCommitIds(trans, max_entries, ready_unsynced_set, out); |
| |
| for (size_t i = 0; i < out->size(); i++) { |
| DVLOG(1) << "Debug commit batch result:" << (*out)[i]; |
| } |
| } |
| |
| namespace { |
| |
| bool IsEntryInConflict(const syncable::Entry& entry) { |
| if (entry.GetIsUnsynced() && |
| entry.GetServerVersion() > 0 && |
| (entry.GetServerVersion() > entry.GetBaseVersion())) { |
| // 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.GetIsUnappliedUpdate()); |
| DVLOG(1) << "Excluding entry from commit due to version mismatch " |
| << entry; |
| return true; |
| } |
| return false; |
| } |
| |
| // Return true if this entry has any attachments that haven't yet been uploaded |
| // to the server. |
| bool HasAttachmentNotOnServer(const syncable::Entry& entry) { |
| const sync_pb::AttachmentMetadata& metadata = entry.GetAttachmentMetadata(); |
| for (int i = 0; i < metadata.record_size(); ++i) { |
| if (!metadata.record(i).is_on_server()) { |
| 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 requested_types, |
| ModelTypeSet encrypted_types, |
| bool passphrase_missing, |
| const syncable::Entry& entry) { |
| DCHECK(entry.GetIsUnsynced()); |
| 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; |
| } |
| |
| // Ignore it if it's not in our set of requested types. |
| if (!requested_types.Has(type)) |
| return false; |
| |
| if (entry.GetIsDel() && !entry.GetId().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.GetId(); |
| if (id == entry.GetParentId()) { |
| 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; |
| } |
| |
| if (HasAttachmentNotOnServer(entry)) { |
| // This entry is not ready to be sent to the server because it has one or |
| // more attachments that have not yet been uploaded to the server. The idea |
| // here is avoid propagating an entry with dangling attachment references. |
| return false; |
| } |
| |
| DVLOG(2) << "Entry is ready for commit: " << entry; |
| return true; |
| } |
| |
| // Filters |unsynced_handles| to remove all entries that do not belong to the |
| // specified |requested_types|, or are not eligible for a commit at this time. |
| void FilterUnreadyEntries( |
| syncable::BaseTransaction* trans, |
| ModelTypeSet requested_types, |
| ModelTypeSet encrypted_types, |
| bool passphrase_missing, |
| const syncable::Directory::Metahandles& unsynced_handles, |
| std::set<int64>* ready_unsynced_set) { |
| for (syncable::Directory::Metahandles::const_iterator iter = |
| unsynced_handles.begin(); iter != unsynced_handles.end(); ++iter) { |
| syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter); |
| // TODO(maniscalco): While we check if entry is ready to be committed, we |
| // also need to check that all of its ancestors (parents, transitive) are |
| // ready to be committed. Once attachments can prevent an entry from being |
| // committable, this method must ensure all ancestors are ready for commit |
| // (bug 356273). |
| if (IsEntryReadyForCommit(requested_types, |
| encrypted_types, |
| passphrase_missing, |
| entry)) { |
| ready_unsynced_set->insert(*iter); |
| } |
| } |
| } |
| |
| // This class helps to implement OrderCommitIds(). Its members track the |
| // progress of a traversal while its methods extend it. It can return early if |
| // the traversal reaches the desired size before the full traversal is complete. |
| class Traversal { |
| public: |
| Traversal( |
| syncable::BaseTransaction* trans, |
| int64 max_entries, |
| syncable::Directory::Metahandles* out); |
| ~Traversal(); |
| |
| // First step of traversal building. Adds non-deleted items in order. |
| void AddCreatesAndMoves(const std::set<int64>& ready_unsynced_set); |
| |
| // Second step of traverals building. Appends deleted items. |
| void AddDeletes(const std::set<int64>& ready_unsynced_set); |
| |
| private: |
| // The following functions do not modify the traversal directly. They return |
| // their results in the |result| vector instead. |
| bool AddUncommittedParentsAndTheirPredecessors( |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| syncable::Directory::Metahandles* result) const; |
| |
| void TryAddItem(const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| syncable::Directory::Metahandles* result) const; |
| |
| void AddItemThenPredecessors( |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| syncable::Directory::Metahandles* result) const; |
| |
| void AddPredecessorsThenItem( |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| syncable::Directory::Metahandles* result) const; |
| |
| bool AddDeletedParents(const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| const syncable::Directory::Metahandles& traversed, |
| syncable::Directory::Metahandles* result) const; |
| |
| // Returns true if we've collected enough items. |
| bool IsFull() const; |
| |
| // Returns true if the specified handle is already in the traversal. |
| bool HaveItem(int64 handle) const; |
| |
| // Adds the specified handles to the traversal. |
| void AppendManyToTraversal(const syncable::Directory::Metahandles& handles); |
| |
| // Adds the specifed handle to the traversal. |
| void AppendToTraversal(int64 handle); |
| |
| syncable::Directory::Metahandles* out_; |
| std::set<int64> added_handles_; |
| const size_t max_entries_; |
| syncable::BaseTransaction* trans_; |
| |
| DISALLOW_COPY_AND_ASSIGN(Traversal); |
| }; |
| |
| Traversal::Traversal( |
| syncable::BaseTransaction* trans, |
| int64 max_entries, |
| syncable::Directory::Metahandles* out) |
| : out_(out), |
| max_entries_(max_entries), |
| trans_(trans) { } |
| |
| Traversal::~Traversal() {} |
| |
| bool Traversal::AddUncommittedParentsAndTheirPredecessors( |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| syncable::Directory::Metahandles* result) const { |
| syncable::Directory::Metahandles dependencies; |
| syncable::Id parent_id = item.GetParentId(); |
| |
| // 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.GetMetahandle(); |
| if (HaveItem(handle)) { |
| // We've already added this parent (and therefore all of its parents). |
| // We can return early. |
| break; |
| } |
| if (IsEntryInConflict(parent)) { |
| // We ignore all entries that are children of a conflicing item. Return |
| // false immediately to forget the traversal we've built up so far. |
| DVLOG(1) << "Parent was in conflict, omitting " << item; |
| return false; |
| } |
| AddItemThenPredecessors(ready_unsynced_set, |
| parent, |
| &dependencies); |
| parent_id = parent.GetParentId(); |
| } |
| |
| // Reverse what we added to get the correct order. |
| result->insert(result->end(), dependencies.rbegin(), dependencies.rend()); |
| return true; |
| } |
| |
| // Adds the given item to the list if it is unsynced and ready for commit. |
| void Traversal::TryAddItem(const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| syncable::Directory::Metahandles* result) const { |
| DCHECK(item.GetIsUnsynced()); |
| int64 item_handle = item.GetMetahandle(); |
| if (ready_unsynced_set.count(item_handle) != 0) { |
| result->push_back(item_handle); |
| } |
| } |
| |
| // Adds the given item, and all its unsynced predecessors. The traversal will |
| // be cut short if any item along the traversal is not IS_UNSYNCED, or if we |
| // detect that this area of the tree has already been traversed. Items that are |
| // not 'ready' for commit (see IsEntryReadyForCommit()) will not be added to the |
| // list, though they will not stop the traversal. |
| void Traversal::AddItemThenPredecessors( |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| syncable::Directory::Metahandles* result) const { |
| int64 item_handle = item.GetMetahandle(); |
| if (HaveItem(item_handle)) { |
| // We've already added this item to the commit set, and so must have |
| // already added the predecessors as well. |
| return; |
| } |
| TryAddItem(ready_unsynced_set, item, result); |
| if (item.GetIsDel()) |
| return; // Deleted items have no predecessors. |
| |
| syncable::Id prev_id = item.GetPredecessorId(); |
| while (!prev_id.IsNull()) { |
| syncable::Entry prev(trans_, syncable::GET_BY_ID, prev_id); |
| CHECK(prev.good()) << "Bad id when walking predecessors."; |
| if (!prev.GetIsUnsynced()) { |
| // We're interested in "runs" of unsynced items. This item breaks |
| // the streak, so we stop traversing. |
| return; |
| } |
| int64 handle = prev.GetMetahandle(); |
| if (HaveItem(handle)) { |
| // We've already added this item to the commit set, and so must have |
| // already added the predecessors as well. |
| return; |
| } |
| TryAddItem(ready_unsynced_set, prev, result); |
| prev_id = prev.GetPredecessorId(); |
| } |
| } |
| |
| // Same as AddItemThenPredecessor, but the traversal order will be reversed. |
| void Traversal::AddPredecessorsThenItem( |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| syncable::Directory::Metahandles* result) const { |
| syncable::Directory::Metahandles dependencies; |
| AddItemThenPredecessors(ready_unsynced_set, item, &dependencies); |
| |
| // Reverse what we added to get the correct order. |
| result->insert(result->end(), dependencies.rbegin(), dependencies.rend()); |
| } |
| |
| // Traverses the tree from bottom to top, adding the deleted parents of the |
| // given |item|. Stops traversing if it encounters a non-deleted node, or |
| // a node that was already listed in the |traversed| list. Returns an error |
| // (false) if a node along the traversal is in a conflict state. |
| // |
| // The result list is reversed before it is returned, so the resulting |
| // traversal is in top to bottom order. Also note that this function appends |
| // to the result list without clearing it. |
| bool Traversal::AddDeletedParents( |
| const std::set<int64>& ready_unsynced_set, |
| const syncable::Entry& item, |
| const syncable::Directory::Metahandles& traversed, |
| syncable::Directory::Metahandles* result) const { |
| syncable::Directory::Metahandles dependencies; |
| syncable::Id parent_id = item.GetParentId(); |
| |
| // Climb the tree adding entries leaf -> root. |
| while (!parent_id.IsRoot()) { |
| syncable::Entry parent(trans_, syncable::GET_BY_ID, parent_id); |
| |
| if (!parent.good()) { |
| // This is valid because the parent could have gone away a long time ago |
| // |
| // Consider the case where a folder is server-unknown and locally |
| // deleted, and has a child that is server-known, deleted, and unsynced. |
| // The parent could be dropped from memory at any time, but its child |
| // needs to be committed first. |
| break; |
| } |
| int64 handle = parent.GetMetahandle(); |
| if (!parent.GetIsUnsynced()) { |
| // In some rare cases, our parent can be both deleted and unsynced. |
| // (ie. the server-unknown parent case). |
| break; |
| } |
| if (!parent.GetIsDel()) { |
| // We're not intersted in non-deleted parents. |
| break; |
| } |
| if (std::find(traversed.begin(), traversed.end(), handle) != |
| traversed.end()) { |
| // We've already added this parent (and therefore all of its parents). |
| // We can return early. |
| break; |
| } |
| if (IsEntryInConflict(parent)) { |
| // We ignore all entries that are children of a conflicing item. Return |
| // false immediately to forget the traversal we've built up so far. |
| DVLOG(1) << "Parent was in conflict, omitting " << item; |
| return false; |
| } |
| TryAddItem(ready_unsynced_set, parent, &dependencies); |
| parent_id = parent.GetParentId(); |
| } |
| |
| // Reverse what we added to get the correct order. |
| result->insert(result->end(), dependencies.rbegin(), dependencies.rend()); |
| return true; |
| } |
| |
| bool Traversal::IsFull() const { |
| return out_->size() >= max_entries_; |
| } |
| |
| bool Traversal::HaveItem(int64 handle) const { |
| return added_handles_.find(handle) != added_handles_.end(); |
| } |
| |
| void Traversal::AppendManyToTraversal( |
| const syncable::Directory::Metahandles& handles) { |
| out_->insert(out_->end(), handles.begin(), handles.end()); |
| added_handles_.insert(handles.begin(), handles.end()); |
| } |
| |
| void Traversal::AppendToTraversal(int64 metahandle) { |
| out_->push_back(metahandle); |
| added_handles_.insert(metahandle); |
| } |
| |
| void Traversal::AddCreatesAndMoves( |
| 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(); |
| !IsFull() && iter != ready_unsynced_set.end(); ++iter) { |
| int64 metahandle = *iter; |
| if (HaveItem(metahandle)) |
| continue; |
| |
| syncable::Entry entry(trans_, |
| syncable::GET_BY_HANDLE, |
| metahandle); |
| if (!entry.GetIsDel()) { |
| // We only commit an item + its dependencies if it and all its |
| // dependencies are not in conflict. |
| syncable::Directory::Metahandles item_dependencies; |
| if (AddUncommittedParentsAndTheirPredecessors( |
| ready_unsynced_set, |
| entry, |
| &item_dependencies)) { |
| AddPredecessorsThenItem(ready_unsynced_set, |
| entry, |
| &item_dependencies); |
| AppendManyToTraversal(item_dependencies); |
| } |
| } |
| } |
| |
| // It's possible that we overcommitted while trying to expand dependent |
| // items. If so, truncate the set down to the allowed size. |
| if (out_->size() > max_entries_) |
| out_->resize(max_entries_); |
| } |
| |
| void Traversal::AddDeletes(const std::set<int64>& ready_unsynced_set) { |
| syncable::Directory::Metahandles deletion_list; |
| |
| // Note: we iterate over all the unsynced set, regardless of the max size. |
| // The max size is only enforced after the top-to-bottom order has been |
| // reversed, in order to ensure children are always deleted before parents. |
| for (std::set<int64>::const_iterator iter = ready_unsynced_set.begin(); |
| iter != ready_unsynced_set.end(); ++iter) { |
| int64 metahandle = *iter; |
| |
| if (HaveItem(metahandle)) |
| continue; |
| |
| if (std::find(deletion_list.begin(), deletion_list.end(), metahandle) != |
| deletion_list.end()) { |
| continue; |
| } |
| |
| syncable::Entry entry(trans_, syncable::GET_BY_HANDLE, |
| metahandle); |
| |
| if (entry.GetIsDel()) { |
| syncable::Directory::Metahandles parents; |
| if (AddDeletedParents( |
| ready_unsynced_set, entry, deletion_list, &parents)) { |
| // Append parents and chilren in top to bottom order. |
| deletion_list.insert(deletion_list.end(), |
| parents.begin(), |
| parents.end()); |
| deletion_list.push_back(metahandle); |
| } |
| } |
| } |
| |
| // We've been gathering deletions in top to bottom order. Now we reverse the |
| // order as we prepare the list. |
| std::reverse(deletion_list.begin(), deletion_list.end()); |
| AppendManyToTraversal(deletion_list); |
| |
| // It's possible that we overcommitted while trying to expand dependent |
| // items. If so, truncate the set down to the allowed size. |
| if (out_->size() > max_entries_) |
| out_->resize(max_entries_); |
| } |
| |
| void OrderCommitIds( |
| syncable::BaseTransaction* trans, |
| size_t max_entries, |
| const std::set<int64>& ready_unsynced_set, |
| syncable::Directory::Metahandles* out) { |
| // 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. |
| |
| Traversal traversal(trans, max_entries, out); |
| |
| // Add moves and creates, and prepend their uncommitted parents. |
| traversal.AddCreatesAndMoves(ready_unsynced_set); |
| |
| // Add all deletes. |
| traversal.AddDeletes(ready_unsynced_set); |
| } |
| |
| } // namespace |
| |
| } // namespace syncer |