Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(25)

Side by Side Diff: sync/engine/get_commit_ids.cc

Issue 2130453004: [Sync] Move //sync to //components/sync. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Rebase. Created 4 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « sync/engine/get_commit_ids.h ('k') | sync/engine/get_updates_delegate.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright 2013 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.h"
6
7 #include <stddef.h>
8 #include <stdint.h>
9
10 #include <set>
11 #include <vector>
12
13 #include "base/macros.h"
14 #include "sync/engine/syncer_util.h"
15 #include "sync/syncable/directory.h"
16 #include "sync/syncable/entry.h"
17 #include "sync/syncable/nigori_handler.h"
18 #include "sync/syncable/nigori_util.h"
19 #include "sync/syncable/syncable_base_transaction.h"
20 #include "sync/syncable/syncable_util.h"
21 #include "sync/util/cryptographer.h"
22
23 using std::set;
24 using std::vector;
25
26 namespace syncer {
27
28 namespace {
29
30 // Forward-declare some helper functions. This gives us more options for
31 // ordering the function defintions within this file.
32
33 // Filters |unsynced_handles| to remove all entries that do not belong to the
34 // specified |requested_types|, or are not eligible for a commit at this time.
35 void FilterUnreadyEntries(
36 syncable::BaseTransaction* trans,
37 ModelTypeSet requested_types,
38 ModelTypeSet encrypted_types,
39 bool passphrase_missing,
40 const syncable::Directory::Metahandles& unsynced_handles,
41 std::set<int64_t>* ready_unsynced_set);
42
43 // Given a set of commit metahandles that are ready for commit
44 // (|ready_unsynced_set|), sorts these into commit order and places up to
45 // |max_entries| of them in the output parameter |out|.
46 //
47 // See the header file for an explanation of commit ordering.
48 void OrderCommitIds(syncable::BaseTransaction* trans,
49 size_t max_entries,
50 const std::set<int64_t>& ready_unsynced_set,
51 std::vector<int64_t>* out);
52
53 } // namespace
54
55 void GetCommitIdsForType(
56 syncable::BaseTransaction* trans,
57 ModelType type,
58 size_t max_entries,
59 syncable::Directory::Metahandles* out) {
60 syncable::Directory* dir = trans->directory();
61
62 // Gather the full set of unsynced items and store it in the session. They
63 // are not in the correct order for commit.
64 std::set<int64_t> ready_unsynced_set;
65 syncable::Directory::Metahandles all_unsynced_handles;
66 GetUnsyncedEntries(trans, &all_unsynced_handles);
67
68 ModelTypeSet encrypted_types;
69 bool passphrase_missing = false;
70 Cryptographer* cryptographer = dir->GetCryptographer(trans);
71 if (cryptographer) {
72 encrypted_types = dir->GetNigoriHandler()->GetEncryptedTypes(trans);
73 passphrase_missing = cryptographer->has_pending_keys();
74 }
75
76 // We filter out all unready entries from the set of unsynced handles. This
77 // new set of ready and unsynced items is then what we use to determine what
78 // is a candidate for commit. The caller is responsible for ensuring that no
79 // throttled types are included among the requested_types.
80 FilterUnreadyEntries(trans,
81 ModelTypeSet(type),
82 encrypted_types,
83 passphrase_missing,
84 all_unsynced_handles,
85 &ready_unsynced_set);
86
87 OrderCommitIds(trans, max_entries, ready_unsynced_set, out);
88
89 for (size_t i = 0; i < out->size(); i++) {
90 DVLOG(1) << "Debug commit batch result:" << (*out)[i];
91 }
92 }
93
94 namespace {
95
96 bool IsEntryInConflict(const syncable::Entry& entry) {
97 if (entry.GetIsUnsynced() &&
98 entry.GetServerVersion() > 0 &&
99 (entry.GetServerVersion() > entry.GetBaseVersion())) {
100 // The local and server versions don't match. The item must be in
101 // conflict, so there's no point in attempting to commit.
102 DCHECK(entry.GetIsUnappliedUpdate());
103 DVLOG(1) << "Excluding entry from commit due to version mismatch "
104 << entry;
105 return true;
106 }
107 return false;
108 }
109
110 // Return true if this entry has any attachments that haven't yet been uploaded
111 // to the server.
112 bool HasAttachmentNotOnServer(const syncable::Entry& entry) {
113 const sync_pb::AttachmentMetadata& metadata = entry.GetAttachmentMetadata();
114 for (int i = 0; i < metadata.record_size(); ++i) {
115 if (!metadata.record(i).is_on_server()) {
116 return true;
117 }
118 }
119 return false;
120 }
121
122 // An entry may not commit if any are true:
123 // 1. It requires encryption (either the type is encrypted but a passphrase
124 // is missing from the cryptographer, or the entry itself wasn't properly
125 // encrypted).
126 // 2. It's type is currently throttled.
127 // 3. It's a delete but has not been committed.
128 bool MayEntryCommit(ModelTypeSet requested_types,
129 ModelTypeSet encrypted_types,
130 bool passphrase_missing,
131 const syncable::Entry& entry) {
132 DCHECK(entry.GetIsUnsynced());
133
134 const ModelType type = entry.GetModelType();
135 // We special case the nigori node because even though it is considered an
136 // "encrypted type", not all nigori node changes require valid encryption
137 // (ex: sync_tabs).
138 if ((type != NIGORI) && encrypted_types.Has(type) &&
139 (passphrase_missing ||
140 syncable::EntryNeedsEncryption(encrypted_types, entry))) {
141 // This entry requires encryption but is not properly encrypted (possibly
142 // due to the cryptographer not being initialized or the user hasn't
143 // provided the most recent passphrase).
144 DVLOG(1) << "Excluding entry from commit due to lack of encryption "
145 << entry;
146 return false;
147 }
148
149 // Ignore it if it's not in our set of requested types.
150 if (!requested_types.Has(type))
151 return false;
152
153 if (entry.GetIsDel() && !entry.GetId().ServerKnows()) {
154 // New clients (following the resolution of crbug.com/125381) should not
155 // create such items. Old clients may have left some in the database
156 // (crbug.com/132905), but we should now be cleaning them on startup.
157 NOTREACHED() << "Found deleted and unsynced local item: " << entry;
158 return false;
159 }
160
161 // Extra validity checks.
162 syncable::Id id = entry.GetId();
163 if (id == entry.GetParentId()) {
164 CHECK(id.IsRoot()) << "Non-root item is self parenting." << entry;
165 // If the root becomes unsynced it can cause us problems.
166 NOTREACHED() << "Root item became unsynced " << entry;
167 return false;
168 }
169
170 if (entry.IsRoot()) {
171 NOTREACHED() << "Permanent item became unsynced " << entry;
172 return false;
173 }
174
175 if (HasAttachmentNotOnServer(entry)) {
176 // This entry is not ready to be sent to the server because it has one or
177 // more attachments that have not yet been uploaded to the server. The idea
178 // here is avoid propagating an entry with dangling attachment references.
179 return false;
180 }
181
182 DVLOG(2) << "Entry is ready for commit: " << entry;
183 return true;
184 }
185
186 bool SupportsHierarchy(const syncable::Entry& item) {
187 // Types with explicit server supported hierarchy only.
188 return IsTypeWithServerGeneratedRoot(item.GetModelType());
189 }
190
191 // Excludes ancestors of deleted conflicted items from
192 // |ready_unsynced_set|.
193 void ExcludeDeletedAncestors(
194 syncable::BaseTransaction* trans,
195 const std::vector<int64_t>& deleted_conflicted_items,
196 std::set<int64_t>* ready_unsynced_set) {
197 for (auto iter = deleted_conflicted_items.begin();
198 iter != deleted_conflicted_items.end(); ++iter) {
199 syncable::Entry item(trans, syncable::GET_BY_HANDLE, *iter);
200 syncable::Id parent_id = item.GetParentId();
201 DCHECK(!parent_id.IsNull());
202
203 while (!parent_id.IsRoot()) {
204 syncable::Entry parent(trans, syncable::GET_BY_ID, parent_id);
205 CHECK(parent.good()) << "Bad user-only parent in item path.";
206 int64_t handle = parent.GetMetahandle();
207
208 if (!parent.GetIsDel())
209 break;
210
211 auto ready_iter = ready_unsynced_set->find(handle);
212 if (ready_iter == ready_unsynced_set->end())
213 break;
214
215 // Remove this entry from |ready_unsynced_set|.
216 ready_unsynced_set->erase(ready_iter);
217 parent_id = parent.GetParentId();
218 }
219 }
220 }
221
222 // Iterates over children of items from |conflicted_items| list that are in
223 // |ready_unsynced_set|, exludes them from |ready_unsynced_set| and adds them
224 // to |excluded_items| list.
225 void ExcludeChildren(syncable::BaseTransaction* trans,
226 const std::vector<int64_t>& conflicted_items,
227 std::vector<int64_t>* excluded_items,
228 std::set<int64_t>* ready_unsynced_set) {
229 for (auto iter = conflicted_items.begin(); iter != conflicted_items.end();
230 ++iter) {
231 syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter);
232
233 if (!entry.GetIsDir() || entry.GetIsDel())
234 continue;
235
236 std::vector<int64_t> children;
237 entry.GetChildHandles(&children);
238
239 for (std::vector<int64_t>::const_iterator child_iter = children.begin();
240 child_iter != children.end(); ++child_iter) {
241 // Collect all child handles that are in |ready_unsynced_set|.
242 int64_t child_handle = *child_iter;
243 auto ready_iter = ready_unsynced_set->find(child_handle);
244 if (ready_iter != ready_unsynced_set->end()) {
245 // Remove this entry from |ready_unsynced_set| and add it
246 // to |excluded_items|.
247 ready_unsynced_set->erase(ready_iter);
248 excluded_items->push_back(child_handle);
249 }
250 }
251 }
252 }
253
254 // Filters |unsynced_handles| to remove all entries that do not belong to the
255 // specified |requested_types|, or are not eligible for a commit at this time.
256 void FilterUnreadyEntries(
257 syncable::BaseTransaction* trans,
258 ModelTypeSet requested_types,
259 ModelTypeSet encrypted_types,
260 bool passphrase_missing,
261 const syncable::Directory::Metahandles& unsynced_handles,
262 std::set<int64_t>* ready_unsynced_set) {
263 std::vector<int64_t> deleted_conflicted_items;
264 std::vector<int64_t> conflicted_items;
265
266 // Go over all unsynced handles, filter the ones that might be committed based
267 // on type / encryption, then based on whether they are in conflict add them
268 // to either |ready_unsynced_set| or one of the conflicted lists.
269 for (auto iter = unsynced_handles.begin(); iter != unsynced_handles.end();
270 ++iter) {
271 syncable::Entry entry(trans, syncable::GET_BY_HANDLE, *iter);
272 // TODO(maniscalco): While we check if entry is ready to be committed, we
273 // also need to check that all of its ancestors (parents, transitive) are
274 // ready to be committed. Once attachments can prevent an entry from being
275 // committable, this method must ensure all ancestors are ready for commit
276 // (bug 356273).
277 if (MayEntryCommit(requested_types, encrypted_types, passphrase_missing,
278 entry)) {
279 if (IsEntryInConflict(entry)) {
280 // Conflicting hierarchical entries might prevent their ancestors or
281 // descendants from being committed.
282 if (SupportsHierarchy(entry)) {
283 if (entry.GetIsDel()) {
284 deleted_conflicted_items.push_back(*iter);
285 } else if (entry.GetIsDir()) {
286 // Populate the initial version of |conflicted_items| with folder
287 // items that are in conflict.
288 conflicted_items.push_back(*iter);
289 }
290 }
291 } else {
292 ready_unsynced_set->insert(*iter);
293 }
294 }
295 }
296
297 // If there are any deleted conflicted entries, remove their deleted ancestors
298 // from |ready_unsynced_set| as well.
299 ExcludeDeletedAncestors(trans, deleted_conflicted_items, ready_unsynced_set);
300
301 // Starting with conflicted_items containing conflicted folders go down and
302 // exclude all descendants from |ready_unsynced_set|.
303 while (!conflicted_items.empty()) {
304 std::vector<int64_t> new_list;
305 ExcludeChildren(trans, conflicted_items, &new_list, ready_unsynced_set);
306 conflicted_items.swap(new_list);
307 }
308 }
309
310 // This class helps to implement OrderCommitIds(). Its members track the
311 // progress of a traversal while its methods extend it. It can return early if
312 // the traversal reaches the desired size before the full traversal is complete.
313 class Traversal {
314 public:
315 Traversal(syncable::BaseTransaction* trans,
316 int64_t max_entries,
317 syncable::Directory::Metahandles* out);
318 ~Traversal();
319
320 // First step of traversal building. Adds non-deleted items in order.
321 void AddCreatesAndMoves(const std::set<int64_t>& ready_unsynced_set);
322
323 // Second step of traverals building. Appends deleted items.
324 void AddDeletes(const std::set<int64_t>& ready_unsynced_set);
325
326 private:
327 // The following functions do not modify the traversal directly. They return
328 // their results in the |result| vector instead.
329 void AddUncommittedParents(const std::set<int64_t>& ready_unsynced_set,
330 const syncable::Entry& item,
331 syncable::Directory::Metahandles* result) const;
332
333 bool TryAddItem(const std::set<int64_t>& ready_unsynced_set,
334 const syncable::Entry& item,
335 syncable::Directory::Metahandles* result) const;
336
337 void AddDeletedParents(const std::set<int64_t>& ready_unsynced_set,
338 const syncable::Entry& item,
339 const syncable::Directory::Metahandles& traversed,
340 syncable::Directory::Metahandles* result) const;
341
342 // Returns true if we've collected enough items.
343 bool IsFull() const;
344
345 // Returns true if the specified handle is already in the traversal.
346 bool HaveItem(int64_t handle) const;
347
348 // Adds the specified handles to the traversal.
349 void AppendManyToTraversal(const syncable::Directory::Metahandles& handles);
350
351 // Adds the specifed handle to the traversal.
352 void AppendToTraversal(int64_t handle);
353
354 syncable::Directory::Metahandles* out_;
355 std::set<int64_t> added_handles_;
356 const size_t max_entries_;
357 syncable::BaseTransaction* trans_;
358
359 DISALLOW_COPY_AND_ASSIGN(Traversal);
360 };
361
362 Traversal::Traversal(syncable::BaseTransaction* trans,
363 int64_t max_entries,
364 syncable::Directory::Metahandles* out)
365 : out_(out), max_entries_(max_entries), trans_(trans) {}
366
367 Traversal::~Traversal() {}
368
369 void Traversal::AddUncommittedParents(
370 const std::set<int64_t>& ready_unsynced_set,
371 const syncable::Entry& item,
372 syncable::Directory::Metahandles* result) const {
373 DCHECK(SupportsHierarchy(item));
374 syncable::Directory::Metahandles dependencies;
375 syncable::Id parent_id = item.GetParentId();
376
377 // Climb the tree adding entries leaf -> root.
378 while (!parent_id.ServerKnows()) {
379 syncable::Entry parent(trans_, syncable::GET_BY_ID, parent_id);
380 CHECK(parent.good()) << "Bad user-only parent in item path.";
381 int64_t handle = parent.GetMetahandle();
382 if (HaveItem(handle)) {
383 // We've already added this parent (and therefore all of its parents).
384 // We can return early.
385 break;
386 }
387
388 if (!TryAddItem(ready_unsynced_set, parent, &dependencies)) {
389 // The parent isn't in |ready_unsynced_set|.
390 break;
391 }
392
393 parent_id = parent.GetParentId();
394 }
395
396 // Reverse what we added to get the correct order.
397 result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
398 }
399
400 // Adds the given item to the list if it is unsynced and ready for commit.
401 bool Traversal::TryAddItem(const std::set<int64_t>& ready_unsynced_set,
402 const syncable::Entry& item,
403 syncable::Directory::Metahandles* result) const {
404 DCHECK(item.GetIsUnsynced());
405 int64_t item_handle = item.GetMetahandle();
406 if (ready_unsynced_set.count(item_handle) != 0) {
407 result->push_back(item_handle);
408 return true;
409 }
410 return false;
411 }
412
413 // Traverses the tree from bottom to top, adding the deleted parents of the
414 // given |item|. Stops traversing if it encounters a non-deleted node, or
415 // a node that was already listed in the |traversed| list.
416 //
417 // The result list is reversed before it is returned, so the resulting
418 // traversal is in top to bottom order. Also note that this function appends
419 // to the result list without clearing it.
420 void Traversal::AddDeletedParents(
421 const std::set<int64_t>& ready_unsynced_set,
422 const syncable::Entry& item,
423 const syncable::Directory::Metahandles& traversed,
424 syncable::Directory::Metahandles* result) const {
425 DCHECK(SupportsHierarchy(item));
426 syncable::Directory::Metahandles dependencies;
427 syncable::Id parent_id = item.GetParentId();
428
429 // Climb the tree adding entries leaf -> root.
430 while (!parent_id.IsRoot()) {
431 syncable::Entry parent(trans_, syncable::GET_BY_ID, parent_id);
432
433 if (!parent.good()) {
434 // This is valid because the parent could have gone away a long time ago
435 //
436 // Consider the case where a folder is server-unknown and locally
437 // deleted, and has a child that is server-known, deleted, and unsynced.
438 // The parent could be dropped from memory at any time, but its child
439 // needs to be committed first.
440 break;
441 }
442 int64_t handle = parent.GetMetahandle();
443 if (!parent.GetIsUnsynced()) {
444 // In some rare cases, our parent can be both deleted and unsynced.
445 // (ie. the server-unknown parent case).
446 break;
447 }
448 if (!parent.GetIsDel()) {
449 // We're not intersted in non-deleted parents.
450 break;
451 }
452 if (std::find(traversed.begin(), traversed.end(), handle) !=
453 traversed.end()) {
454 // We've already added this parent (and therefore all of its parents).
455 // We can return early.
456 break;
457 }
458
459 if (!TryAddItem(ready_unsynced_set, parent, &dependencies)) {
460 // The parent isn't in ready_unsynced_set.
461 break;
462 }
463
464 parent_id = parent.GetParentId();
465 }
466
467 // Reverse what we added to get the correct order.
468 result->insert(result->end(), dependencies.rbegin(), dependencies.rend());
469 }
470
471 bool Traversal::IsFull() const {
472 return out_->size() >= max_entries_;
473 }
474
475 bool Traversal::HaveItem(int64_t handle) const {
476 return added_handles_.find(handle) != added_handles_.end();
477 }
478
479 void Traversal::AppendManyToTraversal(
480 const syncable::Directory::Metahandles& handles) {
481 out_->insert(out_->end(), handles.begin(), handles.end());
482 added_handles_.insert(handles.begin(), handles.end());
483 }
484
485 void Traversal::AppendToTraversal(int64_t metahandle) {
486 out_->push_back(metahandle);
487 added_handles_.insert(metahandle);
488 }
489
490 void Traversal::AddCreatesAndMoves(
491 const std::set<int64_t>& ready_unsynced_set) {
492 // Add moves and creates, and prepend their uncommitted parents.
493 for (std::set<int64_t>::const_iterator iter = ready_unsynced_set.begin();
494 !IsFull() && iter != ready_unsynced_set.end(); ++iter) {
495 int64_t metahandle = *iter;
496 if (HaveItem(metahandle))
497 continue;
498
499 syncable::Entry entry(trans_,
500 syncable::GET_BY_HANDLE,
501 metahandle);
502 if (!entry.GetIsDel()) {
503 if (SupportsHierarchy(entry)) {
504 // We only commit an item + its dependencies if it and all its
505 // dependencies are not in conflict.
506 syncable::Directory::Metahandles item_dependencies;
507 AddUncommittedParents(ready_unsynced_set, entry, &item_dependencies);
508 TryAddItem(ready_unsynced_set, entry, &item_dependencies);
509 AppendManyToTraversal(item_dependencies);
510 } else {
511 // No hierarchy dependencies, just commit the item itself.
512 AppendToTraversal(metahandle);
513 }
514 }
515 }
516
517 // It's possible that we overcommitted while trying to expand dependent
518 // items. If so, truncate the set down to the allowed size.
519 if (out_->size() > max_entries_)
520 out_->resize(max_entries_);
521 }
522
523 void Traversal::AddDeletes(const std::set<int64_t>& ready_unsynced_set) {
524 syncable::Directory::Metahandles deletion_list;
525
526 // Note: we iterate over all the unsynced set, regardless of the max size.
527 // The max size is only enforced after the top-to-bottom order has been
528 // reversed, in order to ensure children are always deleted before parents.
529 for (std::set<int64_t>::const_iterator iter = ready_unsynced_set.begin();
530 iter != ready_unsynced_set.end(); ++iter) {
531 int64_t metahandle = *iter;
532
533 if (HaveItem(metahandle))
534 continue;
535
536 if (std::find(deletion_list.begin(), deletion_list.end(), metahandle) !=
537 deletion_list.end()) {
538 continue;
539 }
540
541 syncable::Entry entry(trans_, syncable::GET_BY_HANDLE,
542 metahandle);
543
544 if (entry.GetIsDel()) {
545 if (SupportsHierarchy(entry)) {
546 syncable::Directory::Metahandles parents;
547 AddDeletedParents(ready_unsynced_set, entry, deletion_list, &parents);
548 // Append parents and chilren in top to bottom order.
549 deletion_list.insert(deletion_list.end(), parents.begin(),
550 parents.end());
551 }
552 deletion_list.push_back(metahandle);
553 }
554 }
555
556 // We've been gathering deletions in top to bottom order. Now we reverse the
557 // order as we prepare the list.
558 std::reverse(deletion_list.begin(), deletion_list.end());
559 AppendManyToTraversal(deletion_list);
560
561 // It's possible that we overcommitted while trying to expand dependent
562 // items. If so, truncate the set down to the allowed size.
563 if (out_->size() > max_entries_)
564 out_->resize(max_entries_);
565 }
566
567 void OrderCommitIds(syncable::BaseTransaction* trans,
568 size_t max_entries,
569 const std::set<int64_t>& ready_unsynced_set,
570 syncable::Directory::Metahandles* out) {
571 // Commits follow these rules:
572 // 1. Moves or creates are preceded by needed folder creates, from
573 // root to leaf.
574 // 2. Moves/Creates before deletes.
575 // 3. Deletes, collapsed.
576 // We commit deleted moves under deleted items as moves when collapsing
577 // delete trees.
578
579 Traversal traversal(trans, max_entries, out);
580
581 // Add moves and creates, and prepend their uncommitted parents.
582 traversal.AddCreatesAndMoves(ready_unsynced_set);
583
584 // Add all deletes.
585 traversal.AddDeletes(ready_unsynced_set);
586 }
587
588 } // namespace
589
590 } // namespace syncer
OLDNEW
« no previous file with comments | « sync/engine/get_commit_ids.h ('k') | sync/engine/get_updates_delegate.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698