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.
5 #ifndef SYNC_SYNCABLE_DIRECTORY_H_
6 #define SYNC_SYNCABLE_DIRECTORY_H_
13 #include "base/basictypes.h"
14 #include "base/containers/hash_tables.h"
15 #include "base/file_util.h"
16 #include "base/gtest_prod_util.h"
17 #include "sync/base/sync_export.h"
18 #include "sync/internal_api/public/util/report_unrecoverable_error_function.h"
19 #include "sync/internal_api/public/util/weak_handle.h"
20 #include "sync/syncable/dir_open_result.h"
21 #include "sync/syncable/entry_kernel.h"
22 #include "sync/syncable/metahandle_set.h"
23 #include "sync/syncable/parent_child_index.h"
24 #include "sync/syncable/syncable_delete_journal.h"
30 class UnrecoverableErrorHandler;
34 class BaseTransaction;
35 class BaseWriteTransaction;
36 class DirectoryChangeDelegate;
37 class DirectoryBackingStore;
39 class ScopedKernelLock;
40 class TransactionObserver;
41 class WriteTransaction;
43 enum InvariantCheckLevel {
44 OFF = 0, // No checking.
45 VERIFY_CHANGES = 1, // Checks only mutated entries. Does not check hierarchy.
46 FULL_DB_VERIFICATION = 2 // Check every entry. This can be expensive.
49 class SYNC_EXPORT Directory {
50 friend class BaseTransaction;
52 friend class ModelNeutralMutableEntry;
53 friend class MutableEntry;
54 friend class ReadTransaction;
55 friend class ScopedKernelLock;
56 friend class WriteTransaction;
57 friend class SyncableDirectoryTest;
58 friend class syncer::TestUserShare;
59 FRIEND_TEST_ALL_PREFIXES(SyncableDirectoryTest, ManageDeleteJournals);
60 FRIEND_TEST_ALL_PREFIXES(SyncableDirectoryTest,
61 TakeSnapshotGetsAllDirtyHandlesTest);
62 FRIEND_TEST_ALL_PREFIXES(SyncableDirectoryTest,
63 TakeSnapshotGetsOnlyDirtyHandlesTest);
64 FRIEND_TEST_ALL_PREFIXES(SyncableDirectoryTest,
65 TakeSnapshotGetsMetahandlesToPurge);
68 typedef std::vector<int64> Metahandles;
70 // Be careful when using these hash_map containers. According to the spec,
71 // inserting into them may invalidate all iterators.
73 // It gets worse, though. The Anroid STL library has a bug that means it may
74 // invalidate all iterators when you erase from the map, too. That means that
75 // you can't iterate while erasing. STLDeleteElements(), std::remove_if(),
76 // and other similar functions are off-limits too, until this bug is fixed.
78 // See http://sourceforge.net/p/stlport/bugs/239/.
79 typedef base::hash_map<int64, EntryKernel*> MetahandlesMap;
80 typedef base::hash_map<std::string, EntryKernel*> IdsMap;
81 typedef base::hash_map<std::string, EntryKernel*> TagsMap;
83 static const base::FilePath::CharType kSyncDatabaseFilename[];
85 // The dirty/clean state of kernel fields backed by the share_info table.
86 // This is public so it can be used in SaveChangesSnapshot for persistence.
87 enum KernelShareInfoStatus {
88 KERNEL_SHARE_INFO_INVALID,
89 KERNEL_SHARE_INFO_VALID,
90 KERNEL_SHARE_INFO_DIRTY
93 // Various data that the Directory::Kernel we are backing (persisting data
94 // for) needs saved across runs of the application.
95 struct SYNC_EXPORT_PRIVATE PersistedKernelInfo {
96 PersistedKernelInfo();
97 ~PersistedKernelInfo();
99 // Set the |download_progress| entry for the given model to a
100 // "first sync" start point. When such a value is sent to the server,
101 // a full download of all objects of the model will be initiated.
102 void reset_download_progress(ModelType model_type);
104 // Last sync timestamp fetched from the server.
105 sync_pb::DataTypeProgressMarker download_progress[MODEL_TYPE_COUNT];
106 // Sync-side transaction version per data type. Monotonically incremented
107 // when updating native model. A copy is also saved in native model.
108 // Later out-of-sync models can be detected and fixed by comparing
109 // transaction versions of sync model and native model.
110 // TODO(hatiaol): implement detection and fixing of out-of-sync models.
112 int64 transaction_version[MODEL_TYPE_COUNT];
113 // The store birthday we were given by the server. Contents are opaque to
115 std::string store_birthday;
116 // The next local ID that has not been used with this cache-GUID.
118 // The serialized bag of chips we were given by the server. Contents are
119 // opaque to the client. This is the serialization of a message of type
120 // ChipBag defined in sync.proto. It can contains NULL characters.
121 std::string bag_of_chips;
124 // What the Directory needs on initialization to create itself and its Kernel.
125 // Filled by DirectoryBackingStore::Load.
126 struct KernelLoadInfo {
127 PersistedKernelInfo kernel_info;
128 std::string cache_guid; // Created on first initialization, never changes.
129 int64 max_metahandle; // Computed (using sql MAX aggregate) on init.
130 KernelLoadInfo() : max_metahandle(0) {
134 // When the Directory is told to SaveChanges, a SaveChangesSnapshot is
135 // constructed and forms a consistent snapshot of what needs to be sent to
136 // the backing store.
137 struct SYNC_EXPORT_PRIVATE SaveChangesSnapshot {
138 SaveChangesSnapshot();
139 ~SaveChangesSnapshot();
141 KernelShareInfoStatus kernel_info_status;
142 PersistedKernelInfo kernel_info;
143 EntryKernelSet dirty_metas;
144 MetahandleSet metahandles_to_purge;
145 EntryKernelSet delete_journals;
146 MetahandleSet delete_journals_to_purge;
149 // Does not take ownership of |encryptor|.
150 // |report_unrecoverable_error_function| may be NULL.
151 // Takes ownership of |store|.
153 DirectoryBackingStore* store,
154 UnrecoverableErrorHandler* unrecoverable_error_handler,
155 ReportUnrecoverableErrorFunction
156 report_unrecoverable_error_function,
157 NigoriHandler* nigori_handler,
158 Cryptographer* cryptographer);
159 virtual ~Directory();
161 // Does not take ownership of |delegate|, which must not be NULL.
162 // Starts sending events to |delegate| if the returned result is
163 // OPENED. Note that events to |delegate| may be sent from *any*
164 // thread. |transaction_observer| must be initialized.
165 DirOpenResult Open(const std::string& name,
166 DirectoryChangeDelegate* delegate,
167 const WeakHandle<TransactionObserver>&
168 transaction_observer);
170 // Stops sending events to the delegate and the transaction
174 int64 NextMetahandle();
175 // Returns a negative integer unique to this client.
176 syncable::Id NextId();
178 bool good() const { return NULL != kernel_; }
180 // The download progress is an opaque token provided by the sync server
181 // to indicate the continuation state of the next GetUpdates operation.
182 void GetDownloadProgress(
184 sync_pb::DataTypeProgressMarker* value_out) const;
185 void GetDownloadProgressAsString(
187 std::string* value_out) const;
188 size_t GetEntriesCount() const;
189 void SetDownloadProgress(
191 const sync_pb::DataTypeProgressMarker& value);
193 // Gets/Increments transaction version of a model type. Must be called when
194 // holding kernel mutex.
195 int64 GetTransactionVersion(ModelType type) const;
196 void IncrementTransactionVersion(ModelType type);
198 ModelTypeSet InitialSyncEndedTypes();
199 bool InitialSyncEndedForType(ModelType type);
200 bool InitialSyncEndedForType(BaseTransaction* trans, ModelType type);
202 const std::string& name() const { return kernel_->name; }
204 // (Account) Store birthday is opaque to the client, so we keep it in the
205 // format it is in the proto buffer in case we switch to a binary birthday
207 std::string store_birthday() const;
208 void set_store_birthday(const std::string& store_birthday);
210 // (Account) Bag of chip is an opaque state used by the server to track the
212 std::string bag_of_chips() const;
213 void set_bag_of_chips(const std::string& bag_of_chips);
215 // Unique to each account / client pair.
216 std::string cache_guid() const;
218 // Returns a pointer to our Nigori node handler.
219 NigoriHandler* GetNigoriHandler();
221 // Returns a pointer to our cryptographer. Does not transfer ownership.
222 // Not thread safe, so should only be accessed while holding a transaction.
223 Cryptographer* GetCryptographer(const BaseTransaction* trans);
225 // Returns true if the directory had encountered an unrecoverable error.
226 // Note: Any function in |Directory| that can be called without holding a
227 // transaction need to check if the Directory already has an unrecoverable
229 bool unrecoverable_error_set(const BaseTransaction* trans) const;
231 // Called to immediately report an unrecoverable error (but don't
233 void ReportUnrecoverableError() {
234 if (report_unrecoverable_error_function_) {
235 report_unrecoverable_error_function_();
239 // Called to set the unrecoverable error on the directory and to propagate
240 // the error to upper layers.
241 void OnUnrecoverableError(const BaseTransaction* trans,
242 const tracked_objects::Location& location,
243 const std::string & message);
245 DeleteJournal* delete_journal();
247 // Returns the child meta handles (even those for deleted/unlinked
248 // nodes) for given parent id. Clears |result| if there are no
250 bool GetChildHandlesById(BaseTransaction*, const Id& parent_id,
251 Metahandles* result);
253 // Returns the child meta handles (even those for deleted/unlinked
254 // nodes) for given meta handle. Clears |result| if there are no
256 bool GetChildHandlesByHandle(BaseTransaction*, int64 handle,
257 Metahandles* result);
259 // Counts all items under the given node, including the node itself.
260 int GetTotalNodeCount(BaseTransaction*, EntryKernel* kernel_) const;
262 // Returns this item's position within its parent folder.
263 // The left-most item is 0, second left-most is 1, etc.
264 int GetPositionIndex(BaseTransaction*, EntryKernel* kernel_) const;
266 // Returns true iff |id| has children.
267 bool HasChildren(BaseTransaction* trans, const Id& id);
269 // Find the first child in the positional ordering under a parent,
270 // and fill in |*first_child_id| with its id. Fills in a root Id if
271 // parent has no children. Returns true if the first child was
272 // successfully found, or false if an error was encountered.
273 Id GetFirstChildId(BaseTransaction* trans, const EntryKernel* parent);
275 // These functions allow one to fetch the next or previous item under
276 // the same folder. Returns the "root" ID if there is no predecessor
279 // TODO(rlarocque): These functions are used mainly for tree traversal. We
280 // should replace these with an iterator API. See crbug.com/178275.
281 syncable::Id GetPredecessorId(EntryKernel*);
282 syncable::Id GetSuccessorId(EntryKernel*);
284 // Places |e| as a successor to |predecessor|. If |predecessor| is NULL,
285 // |e| will be placed as the left-most item in its folder.
287 // Both |e| and |predecessor| must be valid entries under the same parent.
289 // TODO(rlarocque): This function includes limited support for placing items
290 // with valid positions (ie. Bookmarks) as siblings of items that have no set
291 // ordering (ie. Autofill items). This support is required only for tests,
292 // and should be removed. See crbug.com/178282.
293 void PutPredecessor(EntryKernel* e, EntryKernel* predecessor);
295 // SaveChanges works by taking a consistent snapshot of the current Directory
296 // state and indices (by deep copy) under a ReadTransaction, passing this
297 // snapshot to the backing store under no transaction, and finally cleaning
298 // up by either purging entries no longer needed (this part done under a
299 // WriteTransaction) or rolling back the dirty bits. It also uses
300 // internal locking to enforce SaveChanges operations are mutually exclusive.
302 // WARNING: THIS METHOD PERFORMS SYNCHRONOUS I/O VIA SQLITE.
305 // Fill in |result| with all entry kernels.
306 void GetAllEntryKernels(BaseTransaction* trans,
307 std::vector<const EntryKernel*>* result);
309 // Returns the number of entities with the unsynced bit set.
310 int64 unsynced_entity_count() const;
312 // Get GetUnsyncedMetaHandles should only be called after SaveChanges and
313 // before any new entries have been created. The intention is that the
314 // syncer should call it from its PerformSyncQueries member.
315 void GetUnsyncedMetaHandles(BaseTransaction* trans,
316 Metahandles* result);
318 // Returns all server types with unapplied updates. A subset of
319 // those types can then be passed into
320 // GetUnappliedUpdateMetaHandles() below.
321 FullModelTypeSet GetServerTypesWithUnappliedUpdates(
322 BaseTransaction* trans) const;
324 // Get all the metahandles for unapplied updates for a given set of
326 void GetUnappliedUpdateMetaHandles(BaseTransaction* trans,
327 FullModelTypeSet server_types,
328 std::vector<int64>* result);
330 // Get metahandle counts for various criteria to show on the
331 // about:sync page. The information is computed on the fly
332 // each time. If this results in a significant performance hit,
333 // additional data structures can be added to cache results.
334 void CollectMetaHandleCounts(std::vector<int>* num_entries_by_type,
335 std::vector<int>* num_to_delete_entries_by_type);
337 // Sets the level of invariant checking performed after transactions.
338 void SetInvariantCheckLevel(InvariantCheckLevel check_level);
340 // Checks tree metadata consistency following a transaction. It is intended
341 // to provide a reasonable tradeoff between performance and comprehensiveness
342 // and may be used in release code.
343 bool CheckInvariantsOnTransactionClose(
344 syncable::BaseTransaction* trans,
345 const MetahandleSet& modified_handles);
347 // Forces a full check of the directory. This operation may be slow and
348 // should not be invoked outside of tests.
349 bool FullyCheckTreeInvariants(BaseTransaction *trans);
351 // Purges data associated with any entries whose ModelType or ServerModelType
352 // is found in |disabled_types|, from sync directory _both_ in memory and on
353 // disk. Only valid, "real" model types are allowed in |disabled_types| (see
354 // model_type.h for definitions).
355 // 1. Data associated with |types_to_journal| is saved in the delete journal
356 // to help prevent back-from-dead problem due to offline delete in the next
357 // sync session. |types_to_journal| must be a subset of |disabled_types|.
358 // 2. Data associated with |types_to_unapply| is reset to an "unapplied"
359 // state, wherein all local data is deleted and IS_UNAPPLIED is set to true.
360 // This is useful when there's no benefit in discarding the currently
361 // downloaded state, such as when there are cryptographer errors.
362 // |types_to_unapply| must be a subset of |disabled_types|.
363 // 3. All other data is purged entirely.
364 // Note: "Purge" is just meant to distinguish from "deleting" entries, which
365 // means something different in the syncable namespace.
366 // WARNING! This can be real slow, as it iterates over all entries.
367 // WARNING! Performs synchronous I/O.
368 // Returns: true on success, false if an error was encountered.
369 virtual bool PurgeEntriesWithTypeIn(ModelTypeSet disabled_types,
370 ModelTypeSet types_to_journal,
371 ModelTypeSet types_to_unapply);
373 protected: // for friends, mainly used by Entry constructors
374 virtual EntryKernel* GetEntryByHandle(int64 handle);
375 virtual EntryKernel* GetEntryByHandle(int64 metahandle,
376 ScopedKernelLock* lock);
377 virtual EntryKernel* GetEntryById(const Id& id);
378 EntryKernel* GetEntryByServerTag(const std::string& tag);
379 virtual EntryKernel* GetEntryByClientTag(const std::string& tag);
380 EntryKernel* GetRootEntry();
381 bool ReindexId(BaseWriteTransaction* trans, EntryKernel* const entry,
383 bool ReindexParentId(BaseWriteTransaction* trans, EntryKernel* const entry,
384 const Id& new_parent_id);
385 void ClearDirtyMetahandles();
387 DirOpenResult OpenImpl(
388 const std::string& name,
389 DirectoryChangeDelegate* delegate,
390 const WeakHandle<TransactionObserver>& transaction_observer);
394 // |delegate| must not be NULL. |transaction_observer| must be
396 Kernel(const std::string& name, const KernelLoadInfo& info,
397 DirectoryChangeDelegate* delegate,
398 const WeakHandle<TransactionObserver>& transaction_observer);
402 // Implements ReadTransaction / WriteTransaction using a simple lock.
403 base::Lock transaction_mutex;
405 // Protected by transaction_mutex. Used by WriteTransactions.
406 int64 next_write_transaction_id;
408 // The name of this directory.
409 std::string const name;
411 // Protects all members below.
412 // The mutex effectively protects all the indices, but not the
413 // entries themselves. So once a pointer to an entry is pulled
414 // from the index, the mutex can be unlocked and entry read or written.
416 // Never hold the mutex and do anything with the database or any
417 // other buffered IO. Violating this rule will result in deadlock.
420 // Entries indexed by metahandle. This container is considered to be the
421 // owner of all EntryKernels, which may be referened by the other
422 // containers. If you remove an EntryKernel from this map, you probably
423 // want to remove it from all other containers and delete it, too.
424 MetahandlesMap metahandles_map;
426 // Entries indexed by id
429 // Entries indexed by server tag.
430 // This map does not include any entries with non-existent server tags.
431 TagsMap server_tags_map;
433 // Entries indexed by client tag.
434 // This map does not include any entries with non-existent client tags.
435 // IS_DEL items are included.
436 TagsMap client_tags_map;
438 // Contains non-deleted items, indexed according to parent and position
439 // within parent. Protected by the ScopedKernelLock.
440 ParentChildIndex parent_child_index;
442 // 3 in-memory indices on bits used extremely frequently by the syncer.
443 // |unapplied_update_metahandles| is keyed by the server model type.
444 MetahandleSet unapplied_update_metahandles[MODEL_TYPE_COUNT];
445 MetahandleSet unsynced_metahandles;
446 // Contains metahandles that are most likely dirty (though not
447 // necessarily). Dirtyness is confirmed in TakeSnapshotForSaveChanges().
448 MetahandleSet dirty_metahandles;
450 // When a purge takes place, we remove items from all our indices and stash
451 // them in here so that SaveChanges can persist their permanent deletion.
452 MetahandleSet metahandles_to_purge;
454 KernelShareInfoStatus info_status;
456 // These 3 members are backed in the share_info table, and
457 // their state is marked by the flag above.
459 // A structure containing the Directory state that is written back into the
460 // database on SaveChanges.
461 PersistedKernelInfo persisted_info;
463 // A unique identifier for this account's cache db, used to generate
464 // unique server IDs. No need to lock, only written at init time.
465 const std::string cache_guid;
467 // It doesn't make sense for two threads to run SaveChanges at the same
468 // time; this mutex protects that activity.
469 base::Lock save_changes_mutex;
471 // The next metahandle is protected by kernel mutex.
472 int64 next_metahandle;
474 // The delegate for directory change events. Must not be NULL.
475 DirectoryChangeDelegate* const delegate;
477 // The transaction observer.
478 const WeakHandle<TransactionObserver> transaction_observer;
481 // These private versions expect the kernel lock to already be held
483 EntryKernel* GetEntryById(const Id& id, ScopedKernelLock* const lock);
485 // A helper that implements the logic of checking tree invariants.
486 bool CheckTreeInvariants(syncable::BaseTransaction* trans,
487 const MetahandleSet& handles);
489 // Helper to prime metahandles_map, ids_map, parent_child_index,
490 // unsynced_metahandles, unapplied_update_metahandles, server_tags_map and
491 // client_tags_map from metahandles_index. The input |handles_map| will be
492 // cleared during the initialization process.
493 void InitializeIndices(MetahandlesMap* handles_map);
495 // Constructs a consistent snapshot of the current Directory state and
496 // indices (by deep copy) under a ReadTransaction for use in |snapshot|.
497 // See SaveChanges() for more information.
498 void TakeSnapshotForSaveChanges(SaveChangesSnapshot* snapshot);
500 // Purges from memory any unused, safe to remove entries that were
501 // successfully deleted on disk as a result of the SaveChanges that processed
502 // |snapshot|. See SaveChanges() for more information.
503 bool VacuumAfterSaveChanges(const SaveChangesSnapshot& snapshot);
505 // Rolls back dirty bits in the event that the SaveChanges that
506 // processed |snapshot| failed, for example, due to no disk space.
507 void HandleSaveChangesFailure(const SaveChangesSnapshot& snapshot);
509 // For new entry creation only
510 bool InsertEntry(BaseWriteTransaction* trans,
511 EntryKernel* entry, ScopedKernelLock* lock);
512 bool InsertEntry(BaseWriteTransaction* trans, EntryKernel* entry);
514 // Used by CheckTreeInvariants
515 void GetAllMetaHandles(BaseTransaction* trans, MetahandleSet* result);
516 bool SafeToPurgeFromMemory(WriteTransaction* trans,
517 const EntryKernel* const entry) const;
519 // A helper used by GetTotalNodeCount.
520 void GetChildSetForKernel(
522 EntryKernel* kernel_,
523 std::deque<const OrderedChildSet*>* child_sets) const;
525 // Append the handles of the children of |parent_id| to |result|.
526 void AppendChildHandles(
527 const ScopedKernelLock& lock,
528 const Id& parent_id, Directory::Metahandles* result);
530 // Helper methods used by PurgeDisabledTypes.
531 void UnapplyEntry(EntryKernel* entry);
532 void DeleteEntry(bool save_to_journal,
534 EntryKernelSet* entries_to_journal);
538 scoped_ptr<DirectoryBackingStore> store_;
540 UnrecoverableErrorHandler* const unrecoverable_error_handler_;
541 const ReportUnrecoverableErrorFunction report_unrecoverable_error_function_;
542 bool unrecoverable_error_set_;
545 NigoriHandler* const nigori_handler_;
546 Cryptographer* const cryptographer_;
548 InvariantCheckLevel invariant_check_level_;
550 // Maintain deleted entries not in |kernel_| until it's verified that they
551 // are deleted in native models as well.
552 scoped_ptr<DeleteJournal> delete_journal_;
554 DISALLOW_COPY_AND_ASSIGN(Directory);
557 } // namespace syncable
558 } // namespace syncer
560 #endif // SYNC_SYNCABLE_DIRECTORY_H_