1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
|
// 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_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);
syncable::ModelTypeSet encrypted_types;
bool passphrase_missing = false;
Cryptographer* cryptographer =
session->context()->
directory()->GetCryptographer(session->write_transaction());
if (cryptographer) {
encrypted_types = cryptographer->GetEncryptedTypes();
passphrase_missing = cryptographer->has_pending_keys();
};
const syncable::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(syncable::ModelTypeSet throttled_types,
syncable::ModelTypeSet encrypted_types,
bool passphrase_missing,
const syncable::Entry& entry) {
DCHECK(entry.Get(syncable::IS_UNSYNCED));
if (IsEntryInConflict(entry))
return false;
const syncable::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 != syncable::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,
syncable::ModelTypeSet throttled_types,
syncable::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
|