| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 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 "chrome/browser/sync/engine/conflict_resolver.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 #include <list> | |
| 9 #include <map> | |
| 10 #include <set> | |
| 11 | |
| 12 #include "base/location.h" | |
| 13 #include "base/metrics/histogram.h" | |
| 14 #include "chrome/browser/sync/engine/syncer.h" | |
| 15 #include "chrome/browser/sync/engine/syncer_util.h" | |
| 16 #include "chrome/browser/sync/protocol/service_constants.h" | |
| 17 #include "chrome/browser/sync/sessions/status_controller.h" | |
| 18 #include "chrome/browser/sync/syncable/syncable.h" | |
| 19 #include "chrome/browser/sync/util/cryptographer.h" | |
| 20 #include "sync/protocol/nigori_specifics.pb.h" | |
| 21 | |
| 22 using std::list; | |
| 23 using std::map; | |
| 24 using std::set; | |
| 25 using syncable::BaseTransaction; | |
| 26 using syncable::Directory; | |
| 27 using syncable::Entry; | |
| 28 using syncable::GetModelTypeFromSpecifics; | |
| 29 using syncable::Id; | |
| 30 using syncable::IsRealDataType; | |
| 31 using syncable::MutableEntry; | |
| 32 using syncable::WriteTransaction; | |
| 33 | |
| 34 namespace browser_sync { | |
| 35 | |
| 36 using sessions::ConflictProgress; | |
| 37 using sessions::StatusController; | |
| 38 | |
| 39 namespace { | |
| 40 | |
| 41 const int SYNC_CYCLES_BEFORE_ADMITTING_DEFEAT = 8; | |
| 42 | |
| 43 } // namespace | |
| 44 | |
| 45 ConflictResolver::ConflictResolver() { | |
| 46 } | |
| 47 | |
| 48 ConflictResolver::~ConflictResolver() { | |
| 49 } | |
| 50 | |
| 51 void ConflictResolver::IgnoreLocalChanges(MutableEntry* entry) { | |
| 52 // An update matches local actions, merge the changes. | |
| 53 // This is a little fishy because we don't actually merge them. | |
| 54 // In the future we should do a 3-way merge. | |
| 55 // With IS_UNSYNCED false, changes should be merged. | |
| 56 entry->Put(syncable::IS_UNSYNCED, false); | |
| 57 } | |
| 58 | |
| 59 void ConflictResolver::OverwriteServerChanges(WriteTransaction* trans, | |
| 60 MutableEntry * entry) { | |
| 61 // This is similar to an overwrite from the old client. | |
| 62 // This is equivalent to a scenario where we got the update before we'd | |
| 63 // made our local client changes. | |
| 64 // TODO(chron): This is really a general property clobber. We clobber | |
| 65 // the server side property. Perhaps we should actually do property merging. | |
| 66 entry->Put(syncable::BASE_VERSION, entry->Get(syncable::SERVER_VERSION)); | |
| 67 entry->Put(syncable::IS_UNAPPLIED_UPDATE, false); | |
| 68 } | |
| 69 | |
| 70 ConflictResolver::ProcessSimpleConflictResult | |
| 71 ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans, | |
| 72 const Id& id, | |
| 73 const Cryptographer* cryptographer, | |
| 74 StatusController* status) { | |
| 75 MutableEntry entry(trans, syncable::GET_BY_ID, id); | |
| 76 // Must be good as the entry won't have been cleaned up. | |
| 77 CHECK(entry.good()); | |
| 78 | |
| 79 // This function can only resolve simple conflicts. Simple conflicts have | |
| 80 // both IS_UNSYNCED and IS_UNAPPLIED_UDPATE set. | |
| 81 if (!entry.Get(syncable::IS_UNAPPLIED_UPDATE) || | |
| 82 !entry.Get(syncable::IS_UNSYNCED)) { | |
| 83 // This is very unusual, but it can happen in tests. We may be able to | |
| 84 // assert NOTREACHED() here when those tests are updated. | |
| 85 return NO_SYNC_PROGRESS; | |
| 86 } | |
| 87 | |
| 88 if (entry.Get(syncable::IS_DEL) && entry.Get(syncable::SERVER_IS_DEL)) { | |
| 89 // we've both deleted it, so lets just drop the need to commit/update this | |
| 90 // entry. | |
| 91 entry.Put(syncable::IS_UNSYNCED, false); | |
| 92 entry.Put(syncable::IS_UNAPPLIED_UPDATE, false); | |
| 93 // we've made changes, but they won't help syncing progress. | |
| 94 // METRIC simple conflict resolved by merge. | |
| 95 return NO_SYNC_PROGRESS; | |
| 96 } | |
| 97 | |
| 98 // This logic determines "client wins" vs. "server wins" strategy picking. | |
| 99 // By the time we get to this point, we rely on the following to be true: | |
| 100 // a) We can decrypt both the local and server data (else we'd be in | |
| 101 // conflict encryption and not attempting to resolve). | |
| 102 // b) All unsynced changes have been re-encrypted with the default key ( | |
| 103 // occurs either in AttemptToUpdateEntry, SetPassphrase, or | |
| 104 // RefreshEncryption). | |
| 105 // c) Base_server_specifics having a valid datatype means that we received | |
| 106 // an undecryptable update that only changed specifics, and since then have | |
| 107 // not received any further non-specifics-only or decryptable updates. | |
| 108 // d) If the server_specifics match specifics, server_specifics are | |
| 109 // encrypted with the default key, and all other visible properties match, | |
| 110 // then we can safely ignore the local changes as redundant. | |
| 111 // e) Otherwise if the base_server_specifics match the server_specifics, no | |
| 112 // functional change must have been made server-side (else | |
| 113 // base_server_specifics would have been cleared), and we can therefore | |
| 114 // safely ignore the server changes as redundant. | |
| 115 // f) Otherwise, it's in general safer to ignore local changes, with the | |
| 116 // exception of deletion conflicts (choose to undelete) and conflicts | |
| 117 // where the non_unique_name or parent don't match. | |
| 118 if (!entry.Get(syncable::SERVER_IS_DEL)) { | |
| 119 // TODO(nick): The current logic is arbitrary; instead, it ought to be made | |
| 120 // consistent with the ModelAssociator behavior for a datatype. It would | |
| 121 // be nice if we could route this back to ModelAssociator code to pick one | |
| 122 // of three options: CLIENT, SERVER, or MERGE. Some datatypes (autofill) | |
| 123 // are easily mergeable. | |
| 124 // See http://crbug.com/77339. | |
| 125 bool name_matches = entry.Get(syncable::NON_UNIQUE_NAME) == | |
| 126 entry.Get(syncable::SERVER_NON_UNIQUE_NAME); | |
| 127 bool parent_matches = entry.Get(syncable::PARENT_ID) == | |
| 128 entry.Get(syncable::SERVER_PARENT_ID); | |
| 129 bool entry_deleted = entry.Get(syncable::IS_DEL); | |
| 130 | |
| 131 // This positional check is meant to be necessary but not sufficient. As a | |
| 132 // result, it may be false even when the position hasn't changed, possibly | |
| 133 // resulting in unnecessary commits, but if it's true the position has | |
| 134 // definitely not changed. The check works by verifying that the prev id | |
| 135 // as calculated from the server position (which will ignore any | |
| 136 // unsynced/unapplied predecessors and be root for non-bookmark datatypes) | |
| 137 // matches the client prev id. Because we traverse chains of conflicting | |
| 138 // items in predecessor -> successor order, we don't need to also verify the | |
| 139 // successor matches (If it's in conflict, we'll verify it next. If it's | |
| 140 // not, then it should be taken into account already in the | |
| 141 // ComputePrevIdFromServerPosition calculation). This works even when there | |
| 142 // are chains of conflicting items. | |
| 143 // | |
| 144 // Example: Original sequence was abcde. Server changes to aCDbe, while | |
| 145 // client changes to aDCbe (C and D are in conflict). Locally, D's prev id | |
| 146 // is a, while C's prev id is D. On the other hand, the server prev id will | |
| 147 // ignore unsynced/unapplied items, so D's server prev id will also be a, | |
| 148 // just like C's. Because we traverse in client predecessor->successor | |
| 149 // order, we evaluate D first. Since prev id and server id match, we | |
| 150 // consider the position to have remained the same for D, and will unset | |
| 151 // it's UNSYNCED/UNAPPLIED bits. When we evaluate C though, we'll see that | |
| 152 // the prev id is D locally while the server's prev id is a. C will | |
| 153 // therefore count as a positional conflict (and the local data will be | |
| 154 // overwritten by the server data typically). The final result will be | |
| 155 // aCDbe (the same as the server's view). Even though both C and D were | |
| 156 // modified, only one counted as being in actual conflict and was resolved | |
| 157 // with local/server wins. | |
| 158 // | |
| 159 // In general, when there are chains of positional conflicts, only the first | |
| 160 // item in chain (based on the clients point of view) will have both it's | |
| 161 // server prev id and local prev id match. For all the rest the server prev | |
| 162 // id will be the predecessor of the first item in the chain, and therefore | |
| 163 // not match the local prev id. | |
| 164 // | |
| 165 // Similarly, chains of conflicts where the server and client info are the | |
| 166 // same are supported due to the predecessor->successor ordering. In this | |
| 167 // case, from the first item onward, we unset the UNSYNCED/UNAPPLIED bits as | |
| 168 // we decide that nothing changed. The subsequent item's server prev id will | |
| 169 // accurately match the local prev id because the predecessor is no longer | |
| 170 // UNSYNCED/UNAPPLIED. | |
| 171 // TODO(zea): simplify all this once we can directly compare server position | |
| 172 // to client position. | |
| 173 syncable::Id server_prev_id = entry.ComputePrevIdFromServerPosition( | |
| 174 entry.Get(syncable::SERVER_PARENT_ID)); | |
| 175 bool needs_reinsertion = !parent_matches || | |
| 176 server_prev_id != entry.Get(syncable::PREV_ID); | |
| 177 DVLOG_IF(1, needs_reinsertion) << "Insertion needed, server prev id " | |
| 178 << " is " << server_prev_id << ", local prev id is " | |
| 179 << entry.Get(syncable::PREV_ID); | |
| 180 const sync_pb::EntitySpecifics& specifics = | |
| 181 entry.Get(syncable::SPECIFICS); | |
| 182 const sync_pb::EntitySpecifics& server_specifics = | |
| 183 entry.Get(syncable::SERVER_SPECIFICS); | |
| 184 const sync_pb::EntitySpecifics& base_server_specifics = | |
| 185 entry.Get(syncable::BASE_SERVER_SPECIFICS); | |
| 186 std::string decrypted_specifics, decrypted_server_specifics; | |
| 187 bool specifics_match = false; | |
| 188 bool server_encrypted_with_default_key = false; | |
| 189 if (specifics.has_encrypted()) { | |
| 190 DCHECK(cryptographer->CanDecryptUsingDefaultKey(specifics.encrypted())); | |
| 191 decrypted_specifics = cryptographer->DecryptToString( | |
| 192 specifics.encrypted()); | |
| 193 } else { | |
| 194 decrypted_specifics = specifics.SerializeAsString(); | |
| 195 } | |
| 196 if (server_specifics.has_encrypted()) { | |
| 197 server_encrypted_with_default_key = | |
| 198 cryptographer->CanDecryptUsingDefaultKey( | |
| 199 server_specifics.encrypted()); | |
| 200 decrypted_server_specifics = cryptographer->DecryptToString( | |
| 201 server_specifics.encrypted()); | |
| 202 } else { | |
| 203 decrypted_server_specifics = server_specifics.SerializeAsString(); | |
| 204 } | |
| 205 if (decrypted_server_specifics == decrypted_specifics && | |
| 206 server_encrypted_with_default_key == specifics.has_encrypted()) { | |
| 207 specifics_match = true; | |
| 208 } | |
| 209 bool base_server_specifics_match = false; | |
| 210 if (server_specifics.has_encrypted() && | |
| 211 IsRealDataType(GetModelTypeFromSpecifics(base_server_specifics))) { | |
| 212 std::string decrypted_base_server_specifics; | |
| 213 if (!base_server_specifics.has_encrypted()) { | |
| 214 decrypted_base_server_specifics = | |
| 215 base_server_specifics.SerializeAsString(); | |
| 216 } else { | |
| 217 decrypted_base_server_specifics = cryptographer->DecryptToString( | |
| 218 base_server_specifics.encrypted()); | |
| 219 } | |
| 220 if (decrypted_server_specifics == decrypted_base_server_specifics) | |
| 221 base_server_specifics_match = true; | |
| 222 } | |
| 223 | |
| 224 // We manually merge nigori data. | |
| 225 if (entry.GetModelType() == syncable::NIGORI) { | |
| 226 // Create a new set of specifics based on the server specifics (which | |
| 227 // preserves their encryption keys). | |
| 228 sync_pb::EntitySpecifics specifics = | |
| 229 entry.Get(syncable::SERVER_SPECIFICS); | |
| 230 sync_pb::NigoriSpecifics* server_nigori = specifics.mutable_nigori(); | |
| 231 // Store the merged set of encrypted types (cryptographer->Update(..) will | |
| 232 // have merged the local types already). | |
| 233 cryptographer->UpdateNigoriFromEncryptedTypes(server_nigori); | |
| 234 // The local set of keys is already merged with the server's set within | |
| 235 // the cryptographer. If we don't have pending keys we can store the | |
| 236 // merged set back immediately. Else we preserve the server keys and will | |
| 237 // update the nigori when the user provides the pending passphrase via | |
| 238 // SetPassphrase(..). | |
| 239 if (cryptographer->is_ready()) { | |
| 240 cryptographer->GetKeys(server_nigori->mutable_encrypted()); | |
| 241 } | |
| 242 // TODO(zea): Find a better way of doing this. As it stands, we have to | |
| 243 // update this code whenever we add a new non-cryptographer related field | |
| 244 // to the nigori node. | |
| 245 if (entry.Get(syncable::SPECIFICS).nigori().sync_tabs()) { | |
| 246 server_nigori->set_sync_tabs(true); | |
| 247 } | |
| 248 // We deliberately leave the server's device information. This client will | |
| 249 // add it's own device information on restart. | |
| 250 entry.Put(syncable::SPECIFICS, specifics); | |
| 251 DVLOG(1) << "Resovling simple conflict, merging nigori nodes: " << entry; | |
| 252 status->increment_num_server_overwrites(); | |
| 253 OverwriteServerChanges(trans, &entry); | |
| 254 UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict", | |
| 255 NIGORI_MERGE, | |
| 256 CONFLICT_RESOLUTION_SIZE); | |
| 257 } else if (!entry_deleted && name_matches && parent_matches && | |
| 258 specifics_match && !needs_reinsertion) { | |
| 259 DVLOG(1) << "Resolving simple conflict, everything matches, ignoring " | |
| 260 << "changes for: " << entry; | |
| 261 // This unsets both IS_UNSYNCED and IS_UNAPPLIED_UPDATE, and sets the | |
| 262 // BASE_VERSION to match the SERVER_VERSION. If we didn't also unset | |
| 263 // IS_UNAPPLIED_UPDATE, then we would lose unsynced positional data from | |
| 264 // adjacent entries when the server update gets applied and the item is | |
| 265 // re-inserted into the PREV_ID/NEXT_ID linked list. This is primarily | |
| 266 // an issue because we commit after applying updates, and is most | |
| 267 // commonly seen when positional changes are made while a passphrase | |
| 268 // is required (and hence there will be many encryption conflicts). | |
| 269 OverwriteServerChanges(trans, &entry); | |
| 270 IgnoreLocalChanges(&entry); | |
| 271 UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict", | |
| 272 CHANGES_MATCH, | |
| 273 CONFLICT_RESOLUTION_SIZE); | |
| 274 } else if (base_server_specifics_match) { | |
| 275 DVLOG(1) << "Resolving simple conflict, ignoring server encryption " | |
| 276 << " changes for: " << entry; | |
| 277 status->increment_num_server_overwrites(); | |
| 278 OverwriteServerChanges(trans, &entry); | |
| 279 UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict", | |
| 280 IGNORE_ENCRYPTION, | |
| 281 CONFLICT_RESOLUTION_SIZE); | |
| 282 } else if (entry_deleted || !name_matches || !parent_matches) { | |
| 283 OverwriteServerChanges(trans, &entry); | |
| 284 status->increment_num_server_overwrites(); | |
| 285 DVLOG(1) << "Resolving simple conflict, overwriting server changes " | |
| 286 << "for: " << entry; | |
| 287 UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict", | |
| 288 OVERWRITE_SERVER, | |
| 289 CONFLICT_RESOLUTION_SIZE); | |
| 290 } else { | |
| 291 DVLOG(1) << "Resolving simple conflict, ignoring local changes for: " | |
| 292 << entry; | |
| 293 IgnoreLocalChanges(&entry); | |
| 294 status->increment_num_local_overwrites(); | |
| 295 UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict", | |
| 296 OVERWRITE_LOCAL, | |
| 297 CONFLICT_RESOLUTION_SIZE); | |
| 298 } | |
| 299 // Now that we've resolved the conflict, clear the prev server | |
| 300 // specifics. | |
| 301 entry.Put(syncable::BASE_SERVER_SPECIFICS, sync_pb::EntitySpecifics()); | |
| 302 return SYNC_PROGRESS; | |
| 303 } else { // SERVER_IS_DEL is true | |
| 304 // If a server deleted folder has local contents it should be a hierarchy | |
| 305 // conflict. Hierarchy conflicts should not be processed by this function. | |
| 306 // We could end up here if a change was made since we last tried to detect | |
| 307 // conflicts, which was during update application. | |
| 308 if (entry.Get(syncable::IS_DIR)) { | |
| 309 Directory::ChildHandles children; | |
| 310 trans->directory()->GetChildHandlesById(trans, | |
| 311 entry.Get(syncable::ID), | |
| 312 &children); | |
| 313 if (0 != children.size()) { | |
| 314 DVLOG(1) << "Entry is a server deleted directory with local contents, " | |
| 315 << "should be a hierarchy conflict. (race condition)."; | |
| 316 return NO_SYNC_PROGRESS; | |
| 317 } | |
| 318 } | |
| 319 | |
| 320 // The entry is deleted on the server but still exists locally. | |
| 321 if (!entry.Get(syncable::UNIQUE_CLIENT_TAG).empty()) { | |
| 322 // If we've got a client-unique tag, we can undelete while retaining | |
| 323 // our present ID. | |
| 324 DCHECK_EQ(entry.Get(syncable::SERVER_VERSION), 0) << "For the server to " | |
| 325 "know to re-create, client-tagged items should revert to version 0 " | |
| 326 "when server-deleted."; | |
| 327 OverwriteServerChanges(trans, &entry); | |
| 328 status->increment_num_server_overwrites(); | |
| 329 DVLOG(1) << "Resolving simple conflict, undeleting server entry: " | |
| 330 << entry; | |
| 331 UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict", | |
| 332 OVERWRITE_SERVER, | |
| 333 CONFLICT_RESOLUTION_SIZE); | |
| 334 // Clobber the versions, just in case the above DCHECK is violated. | |
| 335 entry.Put(syncable::SERVER_VERSION, 0); | |
| 336 entry.Put(syncable::BASE_VERSION, 0); | |
| 337 } else { | |
| 338 // Otherwise, we've got to undelete by creating a new locally | |
| 339 // uncommitted entry. | |
| 340 SyncerUtil::SplitServerInformationIntoNewEntry(trans, &entry); | |
| 341 | |
| 342 MutableEntry server_update(trans, syncable::GET_BY_ID, id); | |
| 343 CHECK(server_update.good()); | |
| 344 CHECK(server_update.Get(syncable::META_HANDLE) != | |
| 345 entry.Get(syncable::META_HANDLE)) | |
| 346 << server_update << entry; | |
| 347 UMA_HISTOGRAM_ENUMERATION("Sync.ResolveSimpleConflict", | |
| 348 UNDELETE, | |
| 349 CONFLICT_RESOLUTION_SIZE); | |
| 350 } | |
| 351 return SYNC_PROGRESS; | |
| 352 } | |
| 353 } | |
| 354 | |
| 355 bool ConflictResolver::ResolveConflicts(syncable::WriteTransaction* trans, | |
| 356 const Cryptographer* cryptographer, | |
| 357 const ConflictProgress& progress, | |
| 358 sessions::StatusController* status) { | |
| 359 bool forward_progress = false; | |
| 360 // Iterate over simple conflict items. | |
| 361 set<Id>::const_iterator conflicting_item_it; | |
| 362 set<Id> processed_items; | |
| 363 for (conflicting_item_it = progress.SimpleConflictingItemsBegin(); | |
| 364 conflicting_item_it != progress.SimpleConflictingItemsEnd(); | |
| 365 ++conflicting_item_it) { | |
| 366 Id id = *conflicting_item_it; | |
| 367 if (processed_items.count(id) > 0) | |
| 368 continue; | |
| 369 | |
| 370 // We have a simple conflict. In order check if positions have changed, | |
| 371 // we need to process conflicting predecessors before successors. Traverse | |
| 372 // backwards through all continuous conflicting predecessors, building a | |
| 373 // stack of items to resolve in predecessor->successor order, then process | |
| 374 // each item individually. | |
| 375 list<Id> predecessors; | |
| 376 Id prev_id = id; | |
| 377 do { | |
| 378 predecessors.push_back(prev_id); | |
| 379 Entry entry(trans, syncable::GET_BY_ID, prev_id); | |
| 380 // Any entry in conflict must be valid. | |
| 381 CHECK(entry.good()); | |
| 382 Id new_prev_id = entry.Get(syncable::PREV_ID); | |
| 383 if (new_prev_id == prev_id) | |
| 384 break; | |
| 385 prev_id = new_prev_id; | |
| 386 } while (processed_items.count(prev_id) == 0 && | |
| 387 progress.HasSimpleConflictItem(prev_id)); // Excludes root. | |
| 388 while (!predecessors.empty()) { | |
| 389 id = predecessors.back(); | |
| 390 predecessors.pop_back(); | |
| 391 switch (ProcessSimpleConflict(trans, id, cryptographer, status)) { | |
| 392 case NO_SYNC_PROGRESS: | |
| 393 break; | |
| 394 case SYNC_PROGRESS: | |
| 395 forward_progress = true; | |
| 396 break; | |
| 397 } | |
| 398 processed_items.insert(id); | |
| 399 } | |
| 400 } | |
| 401 return forward_progress; | |
| 402 } | |
| 403 | |
| 404 } // namespace browser_sync | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 9699057:
[Sync] Move 'sync' target to sync/ (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/src