| // Copyright (c) 2010 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 "chrome/browser/sync/engine/conflict_resolver.h" |
| |
| #include <map> |
| #include <set> |
| |
| #include "chrome/browser/sync/engine/syncer.h" |
| #include "chrome/browser/sync/engine/syncer_util.h" |
| #include "chrome/browser/sync/protocol/service_constants.h" |
| #include "chrome/browser/sync/sessions/status_controller.h" |
| #include "chrome/browser/sync/syncable/directory_manager.h" |
| #include "chrome/browser/sync/syncable/syncable.h" |
| #include "chrome/common/deprecated/event_sys-inl.h" |
| |
| using std::map; |
| using std::set; |
| using syncable::BaseTransaction; |
| using syncable::Directory; |
| using syncable::Entry; |
| using syncable::Id; |
| using syncable::MutableEntry; |
| using syncable::ScopedDirLookup; |
| using syncable::WriteTransaction; |
| |
| namespace browser_sync { |
| |
| using sessions::ConflictProgress; |
| using sessions::StatusController; |
| |
| const int SYNC_CYCLES_BEFORE_ADMITTING_DEFEAT = 8; |
| |
| ConflictResolver::ConflictResolver() { |
| } |
| |
| ConflictResolver::~ConflictResolver() { |
| } |
| |
| void ConflictResolver::IgnoreLocalChanges(MutableEntry* entry) { |
| // An update matches local actions, merge the changes. |
| // This is a little fishy because we don't actually merge them. |
| // In the future we should do a 3-way merge. |
| VLOG(1) << "Server and local changes match, merging:" << entry; |
| // With IS_UNSYNCED false, changes should be merged. |
| // METRIC simple conflict resolved by merge. |
| entry->Put(syncable::IS_UNSYNCED, false); |
| } |
| |
| void ConflictResolver::OverwriteServerChanges(WriteTransaction* trans, |
| MutableEntry * entry) { |
| // This is similar to an overwrite from the old client. |
| // This is equivalent to a scenario where we got the update before we'd |
| // made our local client changes. |
| // TODO(chron): This is really a general property clobber. We clobber |
| // the server side property. Perhaps we should actually do property merging. |
| entry->Put(syncable::BASE_VERSION, entry->Get(syncable::SERVER_VERSION)); |
| entry->Put(syncable::IS_UNAPPLIED_UPDATE, false); |
| // METRIC conflict resolved by overwrite. |
| } |
| |
| ConflictResolver::ProcessSimpleConflictResult |
| ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans, |
| const Id& id) { |
| MutableEntry entry(trans, syncable::GET_BY_ID, id); |
| // Must be good as the entry won't have been cleaned up. |
| CHECK(entry.good()); |
| // If an update fails, locally we have to be in a set or unsynced. We're not |
| // in a set here, so we must be unsynced. |
| if (!entry.Get(syncable::IS_UNSYNCED)) { |
| return NO_SYNC_PROGRESS; |
| } |
| |
| if (!entry.Get(syncable::IS_UNAPPLIED_UPDATE)) { |
| if (!entry.Get(syncable::PARENT_ID).ServerKnows()) { |
| VLOG(1) << "Item conflicting because its parent not yet committed. Id: " |
| << id; |
| } else { |
| VLOG(1) << "No set for conflicting entry id " << id << ". There should " |
| "be an update/commit that will fix this soon. This message " |
| "should not repeat."; |
| } |
| return NO_SYNC_PROGRESS; |
| } |
| |
| if (entry.Get(syncable::IS_DEL) && entry.Get(syncable::SERVER_IS_DEL)) { |
| // we've both deleted it, so lets just drop the need to commit/update this |
| // entry. |
| entry.Put(syncable::IS_UNSYNCED, false); |
| entry.Put(syncable::IS_UNAPPLIED_UPDATE, false); |
| // we've made changes, but they won't help syncing progress. |
| // METRIC simple conflict resolved by merge. |
| return NO_SYNC_PROGRESS; |
| } |
| |
| if (!entry.Get(syncable::SERVER_IS_DEL)) { |
| // This logic determines "client wins" vs. "server wins" strategy picking. |
| // TODO(nick): The current logic is arbitrary; instead, it ought to be made |
| // consistent with the ModelAssociator behavior for a datatype. It would |
| // be nice if we could route this back to ModelAssociator code to pick one |
| // of three options: CLIENT, SERVER, or MERGE. Some datatypes (autofill) |
| // are easily mergeable. |
| bool name_matches = entry.Get(syncable::NON_UNIQUE_NAME) == |
| entry.Get(syncable::SERVER_NON_UNIQUE_NAME); |
| bool parent_matches = entry.Get(syncable::PARENT_ID) == |
| entry.Get(syncable::SERVER_PARENT_ID); |
| bool entry_deleted = entry.Get(syncable::IS_DEL); |
| |
| if (!entry_deleted && name_matches && parent_matches) { |
| VLOG(1) << "Resolving simple conflict, ignoring local changes for:" |
| << entry; |
| IgnoreLocalChanges(&entry); |
| } else { |
| VLOG(1) << "Resolving simple conflict, overwriting server changes for:" |
| << entry; |
| OverwriteServerChanges(trans, &entry); |
| } |
| return SYNC_PROGRESS; |
| } else { // SERVER_IS_DEL is true |
| // If a server deleted folder has local contents we should be in a set. |
| if (entry.Get(syncable::IS_DIR)) { |
| Directory::ChildHandles children; |
| trans->directory()->GetChildHandles(trans, |
| entry.Get(syncable::ID), |
| &children); |
| if (0 != children.size()) { |
| VLOG(1) << "Entry is a server deleted directory with local contents, " |
| "should be in a set. (race condition)."; |
| return NO_SYNC_PROGRESS; |
| } |
| } |
| |
| // The entry is deleted on the server but still exists locally. |
| if (!entry.Get(syncable::UNIQUE_CLIENT_TAG).empty()) { |
| // If we've got a client-unique tag, we can undelete while retaining |
| // our present ID. |
| DCHECK_EQ(entry.Get(syncable::SERVER_VERSION), 0) << "For the server to " |
| "know to re-create, client-tagged items should revert to version 0 " |
| "when server-deleted."; |
| OverwriteServerChanges(trans, &entry); |
| // Clobber the versions, just in case the above DCHECK is violated. |
| entry.Put(syncable::SERVER_VERSION, 0); |
| entry.Put(syncable::BASE_VERSION, 0); |
| } else { |
| // Otherwise, we've got to undelete by creating a new locally |
| // uncommitted entry. |
| SyncerUtil::SplitServerInformationIntoNewEntry(trans, &entry); |
| |
| MutableEntry server_update(trans, syncable::GET_BY_ID, id); |
| CHECK(server_update.good()); |
| CHECK(server_update.Get(syncable::META_HANDLE) != |
| entry.Get(syncable::META_HANDLE)) |
| << server_update << entry; |
| } |
| return SYNC_PROGRESS; |
| } |
| } |
| |
| ConflictResolver::ConflictSetCountMapKey ConflictResolver::GetSetKey( |
| ConflictSet* set) { |
| // TODO(sync): Come up with a better scheme for set hashing. This scheme |
| // will make debugging easy. |
| // If this call to sort is removed, we need to add one before we use |
| // binary_search in ProcessConflictSet. |
| sort(set->begin(), set->end()); |
| std::stringstream rv; |
| for (ConflictSet::iterator i = set->begin() ; i != set->end() ; ++i ) |
| rv << *i << "."; |
| return rv.str(); |
| } |
| |
| namespace { |
| |
| bool AttemptToFixCircularConflict(WriteTransaction* trans, |
| ConflictSet* conflict_set) { |
| ConflictSet::const_iterator i, j; |
| for (i = conflict_set->begin() ; i != conflict_set->end() ; ++i) { |
| MutableEntry entryi(trans, syncable::GET_BY_ID, *i); |
| if (entryi.Get(syncable::PARENT_ID) == |
| entryi.Get(syncable::SERVER_PARENT_ID) || |
| !entryi.Get(syncable::IS_UNAPPLIED_UPDATE) || |
| !entryi.Get(syncable::IS_DIR)) { |
| continue; |
| } |
| Id parentid = entryi.Get(syncable::SERVER_PARENT_ID); |
| // Create the entry here as it's the only place we could ever get a parentid |
| // that doesn't correspond to a real entry. |
| Entry parent(trans, syncable::GET_BY_ID, parentid); |
| if (!parent.good()) // server parent update not received yet |
| continue; |
| // This loop walks upwards from the server parent. If we hit the root (0) |
| // all is well. If we hit the entry we're examining it means applying the |
| // parent id would cause a loop. We don't need more general loop detection |
| // because we know our local tree is valid. |
| while (!parentid.IsRoot()) { |
| Entry parent(trans, syncable::GET_BY_ID, parentid); |
| CHECK(parent.good()); |
| if (parentid == *i) |
| break; // It's a loop. |
| parentid = parent.Get(syncable::PARENT_ID); |
| } |
| if (parentid.IsRoot()) |
| continue; |
| VLOG(1) << "Overwriting server changes to avoid loop: " << entryi; |
| entryi.Put(syncable::BASE_VERSION, entryi.Get(syncable::SERVER_VERSION)); |
| entryi.Put(syncable::IS_UNSYNCED, true); |
| entryi.Put(syncable::IS_UNAPPLIED_UPDATE, false); |
| // METRIC conflict resolved by breaking dir loop. |
| return true; |
| } |
| return false; |
| } |
| |
| bool AttemptToFixUnsyncedEntryInDeletedServerTree(WriteTransaction* trans, |
| ConflictSet* conflict_set, |
| const Entry& entry) { |
| if (!entry.Get(syncable::IS_UNSYNCED) || entry.Get(syncable::IS_DEL)) |
| return false; |
| Id parentid = entry.Get(syncable::PARENT_ID); |
| MutableEntry parent(trans, syncable::GET_BY_ID, parentid); |
| if (!parent.good() || !parent.Get(syncable::IS_UNAPPLIED_UPDATE) || |
| !parent.Get(syncable::SERVER_IS_DEL) || |
| !binary_search(conflict_set->begin(), conflict_set->end(), parentid)) |
| return false; |
| // We're trying to commit into a directory tree that's been deleted. To |
| // solve this we recreate the directory tree. |
| // |
| // We do this in two parts, first we ensure the tree is unaltered since the |
| // conflict was detected. |
| Id id = parentid; |
| while (!id.IsRoot()) { |
| if (!binary_search(conflict_set->begin(), conflict_set->end(), id)) |
| break; |
| Entry parent(trans, syncable::GET_BY_ID, id); |
| if (!parent.good() || !parent.Get(syncable::IS_UNAPPLIED_UPDATE) || |
| !parent.Get(syncable::SERVER_IS_DEL)) |
| return false; |
| id = parent.Get(syncable::PARENT_ID); |
| } |
| // Now we fix up the entries. |
| id = parentid; |
| while (!id.IsRoot()) { |
| MutableEntry parent(trans, syncable::GET_BY_ID, id); |
| if (!binary_search(conflict_set->begin(), conflict_set->end(), id)) |
| break; |
| VLOG(1) << "Giving directory a new id so we can undelete it " << parent; |
| ClearServerData(&parent); |
| SyncerUtil::ChangeEntryIDAndUpdateChildren(trans, &parent, |
| trans->directory()->NextId()); |
| parent.Put(syncable::BASE_VERSION, 0); |
| parent.Put(syncable::IS_UNSYNCED, true); |
| id = parent.Get(syncable::PARENT_ID); |
| // METRIC conflict resolved by recreating dir tree. |
| } |
| return true; |
| } |
| |
| // TODO(chron): needs unit test badly |
| bool AttemptToFixUpdateEntryInDeletedLocalTree(WriteTransaction* trans, |
| ConflictSet* conflict_set, |
| const Entry& entry) { |
| if (!entry.Get(syncable::IS_UNAPPLIED_UPDATE) || |
| entry.Get(syncable::SERVER_IS_DEL)) |
| return false; |
| Id parent_id = entry.Get(syncable::SERVER_PARENT_ID); |
| MutableEntry parent(trans, syncable::GET_BY_ID, parent_id); |
| if (!parent.good() || !parent.Get(syncable::IS_DEL) || |
| !binary_search(conflict_set->begin(), conflict_set->end(), parent_id)) { |
| return false; |
| } |
| // We've deleted a directory tree that's got contents on the server. We |
| // recreate the directory to solve the problem. |
| // |
| // We do this in two parts, first we ensure the tree is unaltered since |
| // the conflict was detected. |
| Id id = parent_id; |
| // As we will be crawling the path of deleted entries there's a chance we'll |
| // end up having to reparent an item as there will be an invalid parent. |
| Id reroot_id = syncable::kNullId; |
| // Similarly crawling deleted items means we risk loops. |
| int loop_detection = conflict_set->size(); |
| while (!id.IsRoot() && --loop_detection >= 0) { |
| Entry parent(trans, syncable::GET_BY_ID, id); |
| // If we get a bad parent, or a parent that's deleted on client and server |
| // we recreate the hierarchy in the root. |
| if (!parent.good()) { |
| reroot_id = id; |
| break; |
| } |
| CHECK(parent.Get(syncable::IS_DIR)); |
| if (!binary_search(conflict_set->begin(), conflict_set->end(), id)) { |
| // We've got to an entry that's not in the set. If it has been deleted |
| // between set building and this point in time we return false. If it had |
| // been deleted earlier it would have been in the set. |
| // TODO(sync): Revisit syncer code organization to see if conflict |
| // resolution can be done in the same transaction as set building. |
| if (parent.Get(syncable::IS_DEL)) |
| return false; |
| break; |
| } |
| if (!parent.Get(syncable::IS_DEL) || |
| parent.Get(syncable::SERVER_IS_DEL) || |
| !parent.Get(syncable::IS_UNSYNCED)) { |
| return false; |
| } |
| id = parent.Get(syncable::PARENT_ID); |
| } |
| // If we find we've been looping we re-root the hierarchy. |
| if (loop_detection < 0) { |
| if (id == entry.Get(syncable::ID)) |
| reroot_id = entry.Get(syncable::PARENT_ID); |
| else |
| reroot_id = id; |
| } |
| // Now we fix things up by undeleting all the folders in the item's path. |
| id = parent_id; |
| while (!id.IsRoot() && id != reroot_id) { |
| if (!binary_search(conflict_set->begin(), conflict_set->end(), id)) { |
| break; |
| } |
| MutableEntry entry(trans, syncable::GET_BY_ID, id); |
| |
| VLOG(1) << "Undoing our deletion of " << entry |
| << ", will have name " << entry.Get(syncable::NON_UNIQUE_NAME); |
| |
| Id parent_id = entry.Get(syncable::PARENT_ID); |
| if (parent_id == reroot_id) { |
| parent_id = trans->root_id(); |
| } |
| entry.Put(syncable::PARENT_ID, parent_id); |
| entry.Put(syncable::IS_DEL, false); |
| id = entry.Get(syncable::PARENT_ID); |
| // METRIC conflict resolved by recreating dir tree. |
| } |
| return true; |
| } |
| |
| bool AttemptToFixRemovedDirectoriesWithContent(WriteTransaction* trans, |
| ConflictSet* conflict_set) { |
| ConflictSet::const_iterator i,j; |
| for (i = conflict_set->begin() ; i != conflict_set->end() ; ++i) { |
| Entry entry(trans, syncable::GET_BY_ID, *i); |
| if (AttemptToFixUnsyncedEntryInDeletedServerTree(trans, |
| conflict_set, entry)) { |
| return true; |
| } |
| if (AttemptToFixUpdateEntryInDeletedLocalTree(trans, conflict_set, entry)) |
| return true; |
| } |
| return false; |
| } |
| |
| } // namespace |
| |
| // TODO(sync): Eliminate conflict sets. They're not necessary. |
| bool ConflictResolver::ProcessConflictSet(WriteTransaction* trans, |
| ConflictSet* conflict_set, |
| int conflict_count) { |
| int set_size = conflict_set->size(); |
| if (set_size < 2) { |
| LOG(WARNING) << "Skipping conflict set because it has size " << set_size; |
| // We can end up with sets of size one if we have a new item in a set that |
| // we tried to commit transactionally. This should not be a persistent |
| // situation. |
| return false; |
| } |
| if (conflict_count < 3) { |
| // Avoid resolving sets that could be the result of transient conflicts. |
| // Transient conflicts can occur because the client or server can be |
| // slightly out of date. |
| return false; |
| } |
| |
| VLOG(1) << "Fixing a set containing " << set_size << " items"; |
| |
| // Fix circular conflicts. |
| if (AttemptToFixCircularConflict(trans, conflict_set)) |
| return true; |
| // Check for problems involving contents of removed folders. |
| if (AttemptToFixRemovedDirectoriesWithContent(trans, conflict_set)) |
| return true; |
| return false; |
| } |
| |
| template <typename InputIt> |
| bool ConflictResolver::LogAndSignalIfConflictStuck( |
| BaseTransaction* trans, |
| int attempt_count, |
| InputIt begin, |
| InputIt end, |
| StatusController* status) { |
| if (attempt_count < SYNC_CYCLES_BEFORE_ADMITTING_DEFEAT) { |
| return false; |
| } |
| |
| // Don't signal stuck if we're not up to date. |
| if (status->num_server_changes_remaining() > 0) { |
| return false; |
| } |
| |
| LOG(ERROR) << "[BUG] Conflict set cannot be resolved, has " |
| << end - begin << " items:"; |
| for (InputIt i = begin ; i != end ; ++i) { |
| Entry e(trans, syncable::GET_BY_ID, *i); |
| if (e.good()) |
| LOG(ERROR) << " " << e; |
| else |
| LOG(ERROR) << " Bad ID:" << *i; |
| } |
| |
| status->set_syncer_stuck(true); |
| |
| return true; |
| // TODO(sync): If we're stuck for a while we need to alert the user, clear |
| // cache or reset syncing. At the very least we should stop trying something |
| // that's obviously not working. |
| } |
| |
| bool ConflictResolver::ResolveSimpleConflicts(const ScopedDirLookup& dir, |
| StatusController* status) { |
| WriteTransaction trans(dir, syncable::SYNCER, __FILE__, __LINE__); |
| bool forward_progress = false; |
| const ConflictProgress& progress = status->conflict_progress(); |
| // First iterate over simple conflict items (those that belong to no set). |
| set<Id>::const_iterator conflicting_item_it; |
| for (conflicting_item_it = progress.ConflictingItemsBeginConst(); |
| conflicting_item_it != progress.ConflictingItemsEnd(); |
| ++conflicting_item_it) { |
| Id id = *conflicting_item_it; |
| map<Id, ConflictSet*>::const_iterator item_set_it = |
| progress.IdToConflictSetFind(id); |
| if (item_set_it == progress.IdToConflictSetEnd() || |
| 0 == item_set_it->second) { |
| // We have a simple conflict. |
| switch (ProcessSimpleConflict(&trans, id)) { |
| case NO_SYNC_PROGRESS: |
| { |
| int conflict_count = (simple_conflict_count_map_[id] += 2); |
| LogAndSignalIfConflictStuck(&trans, conflict_count, |
| &id, &id + 1, status); |
| break; |
| } |
| case SYNC_PROGRESS: |
| forward_progress = true; |
| break; |
| } |
| } |
| } |
| // Reduce the simple_conflict_count for each item currently tracked. |
| SimpleConflictCountMap::iterator i = simple_conflict_count_map_.begin(); |
| while (i != simple_conflict_count_map_.end()) { |
| if (0 == --(i->second)) |
| simple_conflict_count_map_.erase(i++); |
| else |
| ++i; |
| } |
| return forward_progress; |
| } |
| |
| bool ConflictResolver::ResolveConflicts(const ScopedDirLookup& dir, |
| StatusController* status) { |
| const ConflictProgress& progress = status->conflict_progress(); |
| bool rv = false; |
| if (ResolveSimpleConflicts(dir, status)) |
| rv = true; |
| WriteTransaction trans(dir, syncable::SYNCER, __FILE__, __LINE__); |
| set<Id> children_of_dirs_merged_last_round; |
| std::swap(children_of_merged_dirs_, children_of_dirs_merged_last_round); |
| set<ConflictSet*>::const_iterator set_it; |
| for (set_it = progress.ConflictSetsBegin(); |
| set_it != progress.ConflictSetsEnd(); |
| set_it++) { |
| ConflictSet* conflict_set = *set_it; |
| ConflictSetCountMapKey key = GetSetKey(conflict_set); |
| conflict_set_count_map_[key] += 2; |
| int conflict_count = conflict_set_count_map_[key]; |
| // Keep a metric for new sets. |
| if (2 == conflict_count) { |
| // METRIC conflict sets seen ++ |
| } |
| // See if this set contains entries whose parents were merged last round. |
| if (SortedCollectionsIntersect(children_of_dirs_merged_last_round.begin(), |
| children_of_dirs_merged_last_round.end(), |
| conflict_set->begin(), |
| conflict_set->end())) { |
| VLOG(1) << "Accelerating resolution for hierarchical merge."; |
| conflict_count += 2; |
| } |
| // See if we should process this set. |
| if (ProcessConflictSet(&trans, conflict_set, conflict_count)) { |
| rv = true; |
| } |
| LogAndSignalIfConflictStuck(&trans, conflict_count, |
| conflict_set->begin(), |
| conflict_set->end(), status); |
| } |
| if (rv) { |
| // This code means we don't signal that syncing is stuck when any conflict |
| // resolution has occured. |
| // TODO(sync): As this will also reduce our sensitivity to problem |
| // conditions and increase the time for cascading resolutions we may have to |
| // revisit this code later, doing something more intelligent. |
| conflict_set_count_map_.clear(); |
| simple_conflict_count_map_.clear(); |
| } |
| ConflictSetCountMap::iterator i = conflict_set_count_map_.begin(); |
| while (i != conflict_set_count_map_.end()) { |
| if (0 == --i->second) { |
| conflict_set_count_map_.erase(i++); |
| // METRIC self resolved conflict sets ++. |
| } else { |
| ++i; |
| } |
| } |
| return rv; |
| } |
| |
| } // namespace browser_sync |
