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 #ifndef SYNC_SYNCABLE_DIRECTORY_H_ 6 #define SYNC_SYNCABLE_DIRECTORY_H_ 7 8 #include <deque> 9 #include <set> 10 #include <string> 11 #include <vector> 12 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" 25 26 namespace syncer { 27 28 class Cryptographer; 29 class TestUserShare; 30 class UnrecoverableErrorHandler; 31 32 namespace syncable { 33 34 class BaseTransaction; 35 class BaseWriteTransaction; 36 class DirectoryChangeDelegate; 37 class DirectoryBackingStore; 38 class NigoriHandler; 39 class ScopedKernelLock; 40 class TransactionObserver; 41 class WriteTransaction; 42 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. 47 }; 48 49 class SYNC_EXPORT Directory { 50 friend class BaseTransaction; 51 friend class Entry; 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); 66 67 public: 68 typedef std::vector<int64> Metahandles; 69 70 // Be careful when using these hash_map containers. According to the spec, 71 // inserting into them may invalidate all iterators. 72 // 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. 77 // 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; 82 83 static const base::FilePath::CharType kSyncDatabaseFilename[]; 84 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 91 }; 92 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(); 98 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); 103 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. 111 // Bug 154858. 112 int64 transaction_version[MODEL_TYPE_COUNT]; 113 // The store birthday we were given by the server. Contents are opaque to 114 // the client. 115 std::string store_birthday; 116 // The next local ID that has not been used with this cache-GUID. 117 int64 next_id; 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; 122 }; 123 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. KernelLoadInfoKernelLoadInfo130 KernelLoadInfo() : max_metahandle(0) { 131 } 132 }; 133 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(); 140 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; 147 }; 148 149 // Does not take ownership of |encryptor|. 150 // |report_unrecoverable_error_function| may be NULL. 151 // Takes ownership of |store|. 152 Directory( 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(); 160 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); 169 170 // Stops sending events to the delegate and the transaction 171 // observer. 172 void Close(); 173 174 int64 NextMetahandle(); 175 // Returns a negative integer unique to this client. 176 syncable::Id NextId(); 177 good()178 bool good() const { return NULL != kernel_; } 179 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( 183 ModelType type, 184 sync_pb::DataTypeProgressMarker* value_out) const; 185 void GetDownloadProgressAsString( 186 ModelType type, 187 std::string* value_out) const; 188 size_t GetEntriesCount() const; 189 void SetDownloadProgress( 190 ModelType type, 191 const sync_pb::DataTypeProgressMarker& value); 192 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); 197 198 ModelTypeSet InitialSyncEndedTypes(); 199 bool InitialSyncEndedForType(ModelType type); 200 bool InitialSyncEndedForType(BaseTransaction* trans, ModelType type); 201 name()202 const std::string& name() const { return kernel_->name; } 203 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 206 // later. 207 std::string store_birthday() const; 208 void set_store_birthday(const std::string& store_birthday); 209 210 // (Account) Bag of chip is an opaque state used by the server to track the 211 // client. 212 std::string bag_of_chips() const; 213 void set_bag_of_chips(const std::string& bag_of_chips); 214 215 // Unique to each account / client pair. 216 std::string cache_guid() const; 217 218 // Returns a pointer to our Nigori node handler. 219 NigoriHandler* GetNigoriHandler(); 220 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); 224 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 228 // error on it. 229 bool unrecoverable_error_set(const BaseTransaction* trans) const; 230 231 // Called to immediately report an unrecoverable error (but don't 232 // propagate it up). ReportUnrecoverableError()233 void ReportUnrecoverableError() { 234 if (report_unrecoverable_error_function_) { 235 report_unrecoverable_error_function_(); 236 } 237 } 238 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); 244 245 DeleteJournal* delete_journal(); 246 247 // Returns the child meta handles (even those for deleted/unlinked 248 // nodes) for given parent id. Clears |result| if there are no 249 // children. 250 bool GetChildHandlesById(BaseTransaction*, const Id& parent_id, 251 Metahandles* result); 252 253 // Returns the child meta handles (even those for deleted/unlinked 254 // nodes) for given meta handle. Clears |result| if there are no 255 // children. 256 bool GetChildHandlesByHandle(BaseTransaction*, int64 handle, 257 Metahandles* result); 258 259 // Counts all items under the given node, including the node itself. 260 int GetTotalNodeCount(BaseTransaction*, EntryKernel* kernel_) const; 261 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; 265 266 // Returns true iff |id| has children. 267 bool HasChildren(BaseTransaction* trans, const Id& id); 268 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); 274 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 277 // or successor. 278 // 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*); 283 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. 286 // 287 // Both |e| and |predecessor| must be valid entries under the same parent. 288 // 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); 294 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. 301 // 302 // WARNING: THIS METHOD PERFORMS SYNCHRONOUS I/O VIA SQLITE. 303 bool SaveChanges(); 304 305 // Fill in |result| with all entry kernels. 306 void GetAllEntryKernels(BaseTransaction* trans, 307 std::vector<const EntryKernel*>* result); 308 309 // Returns the number of entities with the unsynced bit set. 310 int64 unsynced_entity_count() const; 311 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); 317 318 // Returns whether or not this |type| has unapplied updates. 319 bool TypeHasUnappliedUpdates(ModelType type); 320 321 // Get all the metahandles for unapplied updates for a given set of 322 // server types. 323 void GetUnappliedUpdateMetaHandles(BaseTransaction* trans, 324 FullModelTypeSet server_types, 325 std::vector<int64>* result); 326 327 // Get metahandle counts for various criteria to show on the 328 // about:sync page. The information is computed on the fly 329 // each time. If this results in a significant performance hit, 330 // additional data structures can be added to cache results. 331 void CollectMetaHandleCounts(std::vector<int>* num_entries_by_type, 332 std::vector<int>* num_to_delete_entries_by_type); 333 334 // Sets the level of invariant checking performed after transactions. 335 void SetInvariantCheckLevel(InvariantCheckLevel check_level); 336 337 // Checks tree metadata consistency following a transaction. It is intended 338 // to provide a reasonable tradeoff between performance and comprehensiveness 339 // and may be used in release code. 340 bool CheckInvariantsOnTransactionClose( 341 syncable::BaseTransaction* trans, 342 const MetahandleSet& modified_handles); 343 344 // Forces a full check of the directory. This operation may be slow and 345 // should not be invoked outside of tests. 346 bool FullyCheckTreeInvariants(BaseTransaction *trans); 347 348 // Purges data associated with any entries whose ModelType or ServerModelType 349 // is found in |disabled_types|, from sync directory _both_ in memory and on 350 // disk. Only valid, "real" model types are allowed in |disabled_types| (see 351 // model_type.h for definitions). 352 // 1. Data associated with |types_to_journal| is saved in the delete journal 353 // to help prevent back-from-dead problem due to offline delete in the next 354 // sync session. |types_to_journal| must be a subset of |disabled_types|. 355 // 2. Data associated with |types_to_unapply| is reset to an "unapplied" 356 // state, wherein all local data is deleted and IS_UNAPPLIED is set to true. 357 // This is useful when there's no benefit in discarding the currently 358 // downloaded state, such as when there are cryptographer errors. 359 // |types_to_unapply| must be a subset of |disabled_types|. 360 // 3. All other data is purged entirely. 361 // Note: "Purge" is just meant to distinguish from "deleting" entries, which 362 // means something different in the syncable namespace. 363 // WARNING! This can be real slow, as it iterates over all entries. 364 // WARNING! Performs synchronous I/O. 365 // Returns: true on success, false if an error was encountered. 366 virtual bool PurgeEntriesWithTypeIn(ModelTypeSet disabled_types, 367 ModelTypeSet types_to_journal, 368 ModelTypeSet types_to_unapply); 369 370 protected: // for friends, mainly used by Entry constructors 371 virtual EntryKernel* GetEntryByHandle(int64 handle); 372 virtual EntryKernel* GetEntryByHandle(int64 metahandle, 373 ScopedKernelLock* lock); 374 virtual EntryKernel* GetEntryById(const Id& id); 375 EntryKernel* GetEntryByServerTag(const std::string& tag); 376 virtual EntryKernel* GetEntryByClientTag(const std::string& tag); 377 EntryKernel* GetRootEntry(); 378 bool ReindexId(BaseWriteTransaction* trans, EntryKernel* const entry, 379 const Id& new_id); 380 bool ReindexParentId(BaseWriteTransaction* trans, EntryKernel* const entry, 381 const Id& new_parent_id); 382 void ClearDirtyMetahandles(); 383 384 DirOpenResult OpenImpl( 385 const std::string& name, 386 DirectoryChangeDelegate* delegate, 387 const WeakHandle<TransactionObserver>& transaction_observer); 388 389 private: 390 struct Kernel { 391 // |delegate| must not be NULL. |transaction_observer| must be 392 // initialized. 393 Kernel(const std::string& name, const KernelLoadInfo& info, 394 DirectoryChangeDelegate* delegate, 395 const WeakHandle<TransactionObserver>& transaction_observer); 396 397 ~Kernel(); 398 399 // Implements ReadTransaction / WriteTransaction using a simple lock. 400 base::Lock transaction_mutex; 401 402 // Protected by transaction_mutex. Used by WriteTransactions. 403 int64 next_write_transaction_id; 404 405 // The name of this directory. 406 std::string const name; 407 408 // Protects all members below. 409 // The mutex effectively protects all the indices, but not the 410 // entries themselves. So once a pointer to an entry is pulled 411 // from the index, the mutex can be unlocked and entry read or written. 412 // 413 // Never hold the mutex and do anything with the database or any 414 // other buffered IO. Violating this rule will result in deadlock. 415 base::Lock mutex; 416 417 // Entries indexed by metahandle. This container is considered to be the 418 // owner of all EntryKernels, which may be referened by the other 419 // containers. If you remove an EntryKernel from this map, you probably 420 // want to remove it from all other containers and delete it, too. 421 MetahandlesMap metahandles_map; 422 423 // Entries indexed by id 424 IdsMap ids_map; 425 426 // Entries indexed by server tag. 427 // This map does not include any entries with non-existent server tags. 428 TagsMap server_tags_map; 429 430 // Entries indexed by client tag. 431 // This map does not include any entries with non-existent client tags. 432 // IS_DEL items are included. 433 TagsMap client_tags_map; 434 435 // Contains non-deleted items, indexed according to parent and position 436 // within parent. Protected by the ScopedKernelLock. 437 ParentChildIndex parent_child_index; 438 439 // 3 in-memory indices on bits used extremely frequently by the syncer. 440 // |unapplied_update_metahandles| is keyed by the server model type. 441 MetahandleSet unapplied_update_metahandles[MODEL_TYPE_COUNT]; 442 MetahandleSet unsynced_metahandles; 443 // Contains metahandles that are most likely dirty (though not 444 // necessarily). Dirtyness is confirmed in TakeSnapshotForSaveChanges(). 445 MetahandleSet dirty_metahandles; 446 447 // When a purge takes place, we remove items from all our indices and stash 448 // them in here so that SaveChanges can persist their permanent deletion. 449 MetahandleSet metahandles_to_purge; 450 451 KernelShareInfoStatus info_status; 452 453 // These 3 members are backed in the share_info table, and 454 // their state is marked by the flag above. 455 456 // A structure containing the Directory state that is written back into the 457 // database on SaveChanges. 458 PersistedKernelInfo persisted_info; 459 460 // A unique identifier for this account's cache db, used to generate 461 // unique server IDs. No need to lock, only written at init time. 462 const std::string cache_guid; 463 464 // It doesn't make sense for two threads to run SaveChanges at the same 465 // time; this mutex protects that activity. 466 base::Lock save_changes_mutex; 467 468 // The next metahandle is protected by kernel mutex. 469 int64 next_metahandle; 470 471 // The delegate for directory change events. Must not be NULL. 472 DirectoryChangeDelegate* const delegate; 473 474 // The transaction observer. 475 const WeakHandle<TransactionObserver> transaction_observer; 476 }; 477 478 // These private versions expect the kernel lock to already be held 479 // before calling. 480 EntryKernel* GetEntryById(const Id& id, ScopedKernelLock* const lock); 481 482 // A helper that implements the logic of checking tree invariants. 483 bool CheckTreeInvariants(syncable::BaseTransaction* trans, 484 const MetahandleSet& handles); 485 486 // Helper to prime metahandles_map, ids_map, parent_child_index, 487 // unsynced_metahandles, unapplied_update_metahandles, server_tags_map and 488 // client_tags_map from metahandles_index. The input |handles_map| will be 489 // cleared during the initialization process. 490 void InitializeIndices(MetahandlesMap* handles_map); 491 492 // Constructs a consistent snapshot of the current Directory state and 493 // indices (by deep copy) under a ReadTransaction for use in |snapshot|. 494 // See SaveChanges() for more information. 495 void TakeSnapshotForSaveChanges(SaveChangesSnapshot* snapshot); 496 497 // Purges from memory any unused, safe to remove entries that were 498 // successfully deleted on disk as a result of the SaveChanges that processed 499 // |snapshot|. See SaveChanges() for more information. 500 bool VacuumAfterSaveChanges(const SaveChangesSnapshot& snapshot); 501 502 // Rolls back dirty bits in the event that the SaveChanges that 503 // processed |snapshot| failed, for example, due to no disk space. 504 void HandleSaveChangesFailure(const SaveChangesSnapshot& snapshot); 505 506 // For new entry creation only 507 bool InsertEntry(BaseWriteTransaction* trans, 508 EntryKernel* entry, ScopedKernelLock* lock); 509 bool InsertEntry(BaseWriteTransaction* trans, EntryKernel* entry); 510 511 // Used by CheckTreeInvariants 512 void GetAllMetaHandles(BaseTransaction* trans, MetahandleSet* result); 513 bool SafeToPurgeFromMemory(WriteTransaction* trans, 514 const EntryKernel* const entry) const; 515 516 // A helper used by GetTotalNodeCount. 517 void GetChildSetForKernel( 518 BaseTransaction*, 519 EntryKernel* kernel_, 520 std::deque<const OrderedChildSet*>* child_sets) const; 521 522 // Append the handles of the children of |parent_id| to |result|. 523 void AppendChildHandles( 524 const ScopedKernelLock& lock, 525 const Id& parent_id, Directory::Metahandles* result); 526 527 // Helper methods used by PurgeDisabledTypes. 528 void UnapplyEntry(EntryKernel* entry); 529 void DeleteEntry(bool save_to_journal, 530 EntryKernel* entry, 531 EntryKernelSet* entries_to_journal); 532 533 Kernel* kernel_; 534 535 scoped_ptr<DirectoryBackingStore> store_; 536 537 UnrecoverableErrorHandler* const unrecoverable_error_handler_; 538 const ReportUnrecoverableErrorFunction report_unrecoverable_error_function_; 539 bool unrecoverable_error_set_; 540 541 // Not owned. 542 NigoriHandler* const nigori_handler_; 543 Cryptographer* const cryptographer_; 544 545 InvariantCheckLevel invariant_check_level_; 546 547 // Maintain deleted entries not in |kernel_| until it's verified that they 548 // are deleted in native models as well. 549 scoped_ptr<DeleteJournal> delete_journal_; 550 551 DISALLOW_COPY_AND_ASSIGN(Directory); 552 }; 553 554 } // namespace syncable 555 } // namespace syncer 556 557 #endif // SYNC_SYNCABLE_DIRECTORY_H_ 558