blob: b2561170cd53747da86410fbf3c093d5ce49b772 [file] [log] [blame]
// Copyright 2013 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 <deque>
#include <set>
#include <string>
#include <vector>
#include "base/basictypes.h"
#include "base/containers/hash_tables.h"
#include "base/files/file_util.h"
#include "base/gtest_prod_util.h"
#include "base/values.h"
#include "sync/api/attachments/attachment_id.h"
#include "sync/base/sync_export.h"
#include "sync/internal_api/public/util/report_unrecoverable_error_function.h"
#include "sync/internal_api/public/util/weak_handle.h"
#include "sync/syncable/dir_open_result.h"
#include "sync/syncable/entry.h"
#include "sync/syncable/entry_kernel.h"
#include "sync/syncable/metahandle_set.h"
#include "sync/syncable/parent_child_index.h"
#include "sync/syncable/syncable_delete_journal.h"
namespace syncer {
class Cryptographer;
class TestUserShare;
class UnrecoverableErrorHandler;
namespace syncable {
class BaseTransaction;
class BaseWriteTransaction;
class DirectoryChangeDelegate;
class DirectoryBackingStore;
class NigoriHandler;
class ScopedKernelLock;
class TransactionObserver;
class WriteTransaction;
enum InvariantCheckLevel {
OFF = 0, // No checking.
VERIFY_CHANGES = 1, // Checks only mutated entries. Does not check hierarchy.
FULL_DB_VERIFICATION = 2 // Check every entry. This can be expensive.
// Directory stores and manages EntryKernels.
// This class is tightly coupled to several other classes (see friends).
class SYNC_EXPORT Directory {
friend class BaseTransaction;
friend class Entry;
friend class ModelNeutralMutableEntry;
friend class MutableEntry;
friend class ReadTransaction;
friend class ScopedKernelLock;
friend class WriteTransaction;
friend class SyncableDirectoryTest;
friend class syncer::TestUserShare;
FRIEND_TEST_ALL_PREFIXES(SyncableDirectoryTest, ManageDeleteJournals);
typedef std::vector<int64> Metahandles;
// Be careful when using these hash_map containers. According to the spec,
// inserting into them may invalidate all iterators.
// It gets worse, though. The Anroid STL library has a bug that means it may
// invalidate all iterators when you erase from the map, too. That means that
// you can't iterate while erasing. STLDeleteElements(), std::remove_if(),
// and other similar functions are off-limits too, until this bug is fixed.
// See
typedef base::hash_map<int64, EntryKernel*> MetahandlesMap;
typedef base::hash_map<std::string, EntryKernel*> IdsMap;
typedef base::hash_map<std::string, EntryKernel*> TagsMap;
typedef std::string AttachmentIdUniqueId;
typedef base::hash_map<AttachmentIdUniqueId, MetahandleSet>
static const base::FilePath::CharType kSyncDatabaseFilename[];
// The dirty/clean state of kernel fields backed by the share_info table.
// This is public so it can be used in SaveChangesSnapshot for persistence.
enum KernelShareInfoStatus {
// Various data that the Directory::Kernel we are backing (persisting data
// for) needs saved across runs of the application.
struct SYNC_EXPORT_PRIVATE PersistedKernelInfo {
// Set the |download_progress| entry for the given model to a
// "first sync" start point. When such a value is sent to the server,
// a full download of all objects of the model will be initiated.
void ResetDownloadProgress(ModelType model_type);
// Whether a valid progress marker exists for |model_type|.
bool HasEmptyDownloadProgress(ModelType model_type);
// Last sync timestamp fetched from the server.
sync_pb::DataTypeProgressMarker download_progress[MODEL_TYPE_COUNT];
// Sync-side transaction version per data type. Monotonically incremented
// when updating native model. A copy is also saved in native model.
// Later out-of-sync models can be detected and fixed by comparing
// transaction versions of sync model and native model.
// TODO(hatiaol): implement detection and fixing of out-of-sync models.
// Bug 154858.
int64 transaction_version[MODEL_TYPE_COUNT];
// The store birthday we were given by the server. Contents are opaque to
// the client.
std::string store_birthday;
// The next local ID that has not been used with this cache-GUID.
int64 next_id;
// The serialized bag of chips we were given by the server. Contents are
// opaque to the client. This is the serialization of a message of type
// ChipBag defined in sync.proto. It can contains NULL characters.
std::string bag_of_chips;
// The per-datatype context.
sync_pb::DataTypeContext datatype_context[MODEL_TYPE_COUNT];
// What the Directory needs on initialization to create itself and its Kernel.
// Filled by DirectoryBackingStore::Load.
struct KernelLoadInfo {
PersistedKernelInfo kernel_info;
std::string cache_guid; // Created on first initialization, never changes.
int64 max_metahandle; // Computed (using sql MAX aggregate) on init.
KernelLoadInfo() : max_metahandle(0) {
// When the Directory is told to SaveChanges, a SaveChangesSnapshot is
// constructed and forms a consistent snapshot of what needs to be sent to
// the backing store.
struct SYNC_EXPORT_PRIVATE SaveChangesSnapshot {
KernelShareInfoStatus kernel_info_status;
PersistedKernelInfo kernel_info;
EntryKernelSet dirty_metas;
MetahandleSet metahandles_to_purge;
EntryKernelSet delete_journals;
MetahandleSet delete_journals_to_purge;
// Does not take ownership of |encryptor|.
// |report_unrecoverable_error_function| may be NULL.
// Takes ownership of |store|.
DirectoryBackingStore* store,
UnrecoverableErrorHandler* unrecoverable_error_handler,
NigoriHandler* nigori_handler,
Cryptographer* cryptographer);
virtual ~Directory();
// Does not take ownership of |delegate|, which must not be NULL.
// Starts sending events to |delegate| if the returned result is
// OPENED. Note that events to |delegate| may be sent from *any*
// thread. |transaction_observer| must be initialized.
DirOpenResult Open(const std::string& name,
DirectoryChangeDelegate* delegate,
const WeakHandle<TransactionObserver>&
// Stops sending events to the delegate and the transaction
// observer.
void Close();
int64 NextMetahandle();
// Returns a negative integer unique to this client.
syncable::Id NextId();
bool good() const { return NULL != kernel_; }
// The download progress is an opaque token provided by the sync server
// to indicate the continuation state of the next GetUpdates operation.
void GetDownloadProgress(
ModelType type,
sync_pb::DataTypeProgressMarker* value_out) const;
void GetDownloadProgressAsString(
ModelType type,
std::string* value_out) const;
void SetDownloadProgress(
ModelType type,
const sync_pb::DataTypeProgressMarker& value);
bool HasEmptyDownloadProgress(ModelType type) const;
// Gets the total number of entries in the directory.
size_t GetEntriesCount() const;
// Gets/Increments transaction version of a model type. Must be called when
// holding kernel mutex.
int64 GetTransactionVersion(ModelType type) const;
void IncrementTransactionVersion(ModelType type);
// Getter/setters for the per datatype context.
void GetDataTypeContext(BaseTransaction* trans,
ModelType type,
sync_pb::DataTypeContext* context) const;
void SetDataTypeContext(BaseWriteTransaction* trans,
ModelType type,
const sync_pb::DataTypeContext& context);
ModelTypeSet InitialSyncEndedTypes();
bool InitialSyncEndedForType(ModelType type);
bool InitialSyncEndedForType(BaseTransaction* trans, ModelType type);
const std::string& name() const { return kernel_->name; }
// (Account) Store birthday is opaque to the client, so we keep it in the
// format it is in the proto buffer in case we switch to a binary birthday
// later.
std::string store_birthday() const;
void set_store_birthday(const std::string& store_birthday);
// (Account) Bag of chip is an opaque state used by the server to track the
// client.
std::string bag_of_chips() const;
void set_bag_of_chips(const std::string& bag_of_chips);
// Unique to each account / client pair.
std::string cache_guid() const;
// Returns a pointer to our Nigori node handler.
NigoriHandler* GetNigoriHandler();
// Returns a pointer to our cryptographer. Does not transfer ownership.
// Not thread safe, so should only be accessed while holding a transaction.
Cryptographer* GetCryptographer(const BaseTransaction* trans);
// Returns true if the directory had encountered an unrecoverable error.
// Note: Any function in |Directory| that can be called without holding a
// transaction need to check if the Directory already has an unrecoverable
// error on it.
bool unrecoverable_error_set(const BaseTransaction* trans) const;
// Called to immediately report an unrecoverable error (but don't
// propagate it up).
void ReportUnrecoverableError() {
if (report_unrecoverable_error_function_) {
// Called to set the unrecoverable error on the directory and to propagate
// the error to upper layers.
void OnUnrecoverableError(const BaseTransaction* trans,
const tracked_objects::Location& location,
const std::string & message);
DeleteJournal* delete_journal();
// Returns the child meta handles (even those for deleted/unlinked
// nodes) for given parent id. Clears |result| if there are no
// children.
bool GetChildHandlesById(BaseTransaction*, const Id& parent_id,
Metahandles* result);
// Counts all items under the given node, including the node itself.
int GetTotalNodeCount(BaseTransaction*, EntryKernel* kernel_) const;
// Returns this item's position within its parent folder.
// The left-most item is 0, second left-most is 1, etc.
int GetPositionIndex(BaseTransaction*, EntryKernel* kernel_) const;
// Returns true iff |id| has children.
bool HasChildren(BaseTransaction* trans, const Id& id);
// Find the first child in the positional ordering under a parent,
// and fill in |*first_child_id| with its id. Fills in a root Id if
// parent has no children. Returns true if the first child was
// successfully found, or false if an error was encountered.
Id GetFirstChildId(BaseTransaction* trans, const EntryKernel* parent);
// These functions allow one to fetch the next or previous item under
// the same folder. Returns the "root" ID if there is no predecessor
// or successor.
// TODO(rlarocque): These functions are used mainly for tree traversal. We
// should replace these with an iterator API. See
syncable::Id GetPredecessorId(EntryKernel*);
syncable::Id GetSuccessorId(EntryKernel*);
// Places |e| as a successor to |predecessor|. If |predecessor| is NULL,
// |e| will be placed as the left-most item in its folder.
// Both |e| and |predecessor| must be valid entries under the same parent.
// TODO(rlarocque): This function includes limited support for placing items
// with valid positions (ie. Bookmarks) as siblings of items that have no set
// ordering (ie. Autofill items). This support is required only for tests,
// and should be removed. See
void PutPredecessor(EntryKernel* e, EntryKernel* predecessor);
// SaveChanges works by taking a consistent snapshot of the current Directory
// state and indices (by deep copy) under a ReadTransaction, passing this
// snapshot to the backing store under no transaction, and finally cleaning
// up by either purging entries no longer needed (this part done under a
// WriteTransaction) or rolling back the dirty bits. It also uses
// internal locking to enforce SaveChanges operations are mutually exclusive.
bool SaveChanges();
// Returns the number of entities with the unsynced bit set.
int64 unsynced_entity_count() const;
// Get GetUnsyncedMetaHandles should only be called after SaveChanges and
// before any new entries have been created. The intention is that the
// syncer should call it from its PerformSyncQueries member.
void GetUnsyncedMetaHandles(BaseTransaction* trans,
Metahandles* result);
// Returns whether or not this |type| has unapplied updates.
bool TypeHasUnappliedUpdates(ModelType type);
// Get all the metahandles for unapplied updates for a given set of
// server types.
void GetUnappliedUpdateMetaHandles(BaseTransaction* trans,
FullModelTypeSet server_types,
std::vector<int64>* result);
// Get all the metahandles of entries of |type|.
void GetMetaHandlesOfType(BaseTransaction* trans,
ModelType type,
Metahandles* result);
// Get metahandle counts for various criteria to show on the
// about:sync page. The information is computed on the fly
// each time. If this results in a significant performance hit,
// additional data structures can be added to cache results.
void CollectMetaHandleCounts(std::vector<int>* num_entries_by_type,
std::vector<int>* num_to_delete_entries_by_type);
// Returns a ListValue serialization of all nodes for the given type.
scoped_ptr<base::ListValue> GetNodeDetailsForType(
BaseTransaction* trans,
ModelType type);
// Sets the level of invariant checking performed after transactions.
void SetInvariantCheckLevel(InvariantCheckLevel check_level);
// Checks tree metadata consistency following a transaction. It is intended
// to provide a reasonable tradeoff between performance and comprehensiveness
// and may be used in release code.
bool CheckInvariantsOnTransactionClose(
syncable::BaseTransaction* trans,
const MetahandleSet& modified_handles);
// Forces a full check of the directory. This operation may be slow and
// should not be invoked outside of tests.
bool FullyCheckTreeInvariants(BaseTransaction *trans);
// Purges data associated with any entries whose ModelType or ServerModelType
// is found in |disabled_types|, from sync directory _both_ in memory and on
// disk. Only valid, "real" model types are allowed in |disabled_types| (see
// model_type.h for definitions).
// 1. Data associated with |types_to_journal| is saved in the delete journal
// to help prevent back-from-dead problem due to offline delete in the next
// sync session. |types_to_journal| must be a subset of |disabled_types|.
// 2. Data associated with |types_to_unapply| is reset to an "unapplied"
// state, wherein all local data is deleted and IS_UNAPPLIED is set to true.
// This is useful when there's no benefit in discarding the currently
// downloaded state, such as when there are cryptographer errors.
// |types_to_unapply| must be a subset of |disabled_types|.
// 3. All other data is purged entirely.
// Note: "Purge" is just meant to distinguish from "deleting" entries, which
// means something different in the syncable namespace.
// WARNING! This can be real slow, as it iterates over all entries.
// WARNING! Performs synchronous I/O.
// Returns: true on success, false if an error was encountered.
virtual bool PurgeEntriesWithTypeIn(ModelTypeSet disabled_types,
ModelTypeSet types_to_journal,
ModelTypeSet types_to_unapply);
// Resets the base_versions and server_versions of all synced entities
// associated with |type| to 1.
// WARNING! This can be slow, as it iterates over all entries for a type.
bool ResetVersionsForType(BaseWriteTransaction* trans, ModelType type);
// Returns true iff the attachment identified by |attachment_id_proto| is
// linked to an entry.
// An attachment linked to a deleted entry is still considered linked if the
// entry hasn't yet been purged.
bool IsAttachmentLinked(
const sync_pb::AttachmentIdProto& attachment_id_proto) const;
// Given attachment id return metahandles to all entries that reference this
// attachment.
void GetMetahandlesByAttachmentId(
BaseTransaction* trans,
const sync_pb::AttachmentIdProto& attachment_id_proto,
Metahandles* result);
// Change entry to not dirty. Used in special case when we don't want to
// persist modified entry on disk. e.g. SyncBackupManager uses this to
// preserve sync preferences in DB on disk.
void UnmarkDirtyEntry(WriteTransaction* trans, Entry* entry);
// Clears |ids| and fills it with the ids of attachments that need to be
// uploaded to the sync server.
void GetAttachmentIdsToUpload(BaseTransaction* trans,
ModelType type,
AttachmentIdList* ids);
struct Kernel {
// |delegate| must not be NULL. |transaction_observer| must be
// initialized.
Kernel(const std::string& name, const KernelLoadInfo& info,
DirectoryChangeDelegate* delegate,
const WeakHandle<TransactionObserver>& transaction_observer);
// Implements ReadTransaction / WriteTransaction using a simple lock.
base::Lock transaction_mutex;
// Protected by transaction_mutex. Used by WriteTransactions.
int64 next_write_transaction_id;
// The name of this directory.
std::string const name;
// Protects all members below.
// The mutex effectively protects all the indices, but not the
// entries themselves. So once a pointer to an entry is pulled
// from the index, the mutex can be unlocked and entry read or written.
// Never hold the mutex and do anything with the database or any
// other buffered IO. Violating this rule will result in deadlock.
base::Lock mutex;
// Entries indexed by metahandle. This container is considered to be the
// owner of all EntryKernels, which may be referened by the other
// containers. If you remove an EntryKernel from this map, you probably
// want to remove it from all other containers and delete it, too.
MetahandlesMap metahandles_map;
// Entries indexed by id
IdsMap ids_map;
// Entries indexed by server tag.
// This map does not include any entries with non-existent server tags.
TagsMap server_tags_map;
// Entries indexed by client tag.
// This map does not include any entries with non-existent client tags.
// IS_DEL items are included.
TagsMap client_tags_map;
// Contains non-deleted items, indexed according to parent and position
// within parent. Protected by the ScopedKernelLock.
ParentChildIndex parent_child_index;
// This index keeps track of which metahandles refer to a given attachment.
// Think of it as the inverse of EntryKernel's AttachmentMetadata Records.
// Because entries can be undeleted (e.g. PutIsDel(false)), entries should
// not removed from the index until they are actually deleted from memory.
// All access should go through IsAttachmentLinked,
// RemoveFromAttachmentIndex, AddToAttachmentIndex, and
// UpdateAttachmentIndex methods to avoid iterator invalidation errors.
IndexByAttachmentId index_by_attachment_id;
// 3 in-memory indices on bits used extremely frequently by the syncer.
// |unapplied_update_metahandles| is keyed by the server model type.
MetahandleSet unapplied_update_metahandles[MODEL_TYPE_COUNT];
MetahandleSet unsynced_metahandles;
// Contains metahandles that are most likely dirty (though not
// necessarily). Dirtyness is confirmed in TakeSnapshotForSaveChanges().
MetahandleSet dirty_metahandles;
// When a purge takes place, we remove items from all our indices and stash
// them in here so that SaveChanges can persist their permanent deletion.
MetahandleSet metahandles_to_purge;
KernelShareInfoStatus info_status;
// These 3 members are backed in the share_info table, and
// their state is marked by the flag above.
// A structure containing the Directory state that is written back into the
// database on SaveChanges.
PersistedKernelInfo persisted_info;
// A unique identifier for this account's cache db, used to generate
// unique server IDs. No need to lock, only written at init time.
const std::string cache_guid;
// It doesn't make sense for two threads to run SaveChanges at the same
// time; this mutex protects that activity.
base::Lock save_changes_mutex;
// The next metahandle is protected by kernel mutex.
int64 next_metahandle;
// The delegate for directory change events. Must not be NULL.
DirectoryChangeDelegate* const delegate;
// The transaction observer.
const WeakHandle<TransactionObserver> transaction_observer;
// You'll notice that some of these methods have two forms. One that takes a
// ScopedKernelLock and one that doesn't. The general pattern is that those
// without a ScopedKernelLock parameter construct one internally before
// calling the form that takes one.
virtual EntryKernel* GetEntryByHandle(int64 handle);
virtual EntryKernel* GetEntryByHandle(const ScopedKernelLock& lock,
int64 metahandle);
virtual EntryKernel* GetEntryById(const Id& id);
virtual EntryKernel* GetEntryById(const ScopedKernelLock& lock, const Id& id);
EntryKernel* GetEntryByServerTag(const std::string& tag);
virtual EntryKernel* GetEntryByClientTag(const std::string& tag);
// For new entry creation only
bool InsertEntry(BaseWriteTransaction* trans, EntryKernel* entry);
bool InsertEntry(const ScopedKernelLock& lock,
BaseWriteTransaction* trans,
EntryKernel* entry);
bool ReindexId(BaseWriteTransaction* trans, EntryKernel* const entry,
const Id& new_id);
bool ReindexParentId(BaseWriteTransaction* trans, EntryKernel* const entry,
const Id& new_parent_id);
// Update the attachment index for |metahandle| removing it from the index
// under |old_metadata| entries and add it under |new_metadata| entries.
void UpdateAttachmentIndex(const int64 metahandle,
const sync_pb::AttachmentMetadata& old_metadata,
const sync_pb::AttachmentMetadata& new_metadata);
// Remove each of |metahandle|'s attachment ids from index_by_attachment_id.
void RemoveFromAttachmentIndex(
const ScopedKernelLock& lock,
const int64 metahandle,
const sync_pb::AttachmentMetadata& attachment_metadata);
// Add each of |metahandle|'s attachment ids to the index_by_attachment_id.
void AddToAttachmentIndex(
const ScopedKernelLock& lock,
const int64 metahandle,
const sync_pb::AttachmentMetadata& attachment_metadata);
void ClearDirtyMetahandles(const ScopedKernelLock& lock);
DirOpenResult OpenImpl(
const std::string& name,
DirectoryChangeDelegate* delegate,
const WeakHandle<TransactionObserver>& transaction_observer);
// A helper that implements the logic of checking tree invariants.
bool CheckTreeInvariants(syncable::BaseTransaction* trans,
const MetahandleSet& handles);
// Helper to prime metahandles_map, ids_map, parent_child_index,
// unsynced_metahandles, unapplied_update_metahandles, server_tags_map and
// client_tags_map from metahandles_index. The input |handles_map| will be
// cleared during the initialization process.
void InitializeIndices(MetahandlesMap* handles_map);
// Constructs a consistent snapshot of the current Directory state and
// indices (by deep copy) under a ReadTransaction for use in |snapshot|.
// See SaveChanges() for more information.
void TakeSnapshotForSaveChanges(SaveChangesSnapshot* snapshot);
// Purges from memory any unused, safe to remove entries that were
// successfully deleted on disk as a result of the SaveChanges that processed
// |snapshot|. See SaveChanges() for more information.
bool VacuumAfterSaveChanges(const SaveChangesSnapshot& snapshot);
// Rolls back dirty bits in the event that the SaveChanges that
// processed |snapshot| failed, for example, due to no disk space.
void HandleSaveChangesFailure(const SaveChangesSnapshot& snapshot);
// Used by CheckTreeInvariants.
void GetAllMetaHandles(BaseTransaction* trans, MetahandleSet* result);
// Used by VacuumAfterSaveChanges.
bool SafeToPurgeFromMemory(WriteTransaction* trans,
const EntryKernel* const entry) const;
// A helper used by GetTotalNodeCount.
void GetChildSetForKernel(
EntryKernel* kernel_,
std::deque<const OrderedChildSet*>* child_sets) const;
// Append the handles of the children of |parent_id| to |result|.
void AppendChildHandles(const ScopedKernelLock& lock,
const Id& parent_id,
Directory::Metahandles* result);
// Helper methods used by PurgeDisabledTypes.
void UnapplyEntry(EntryKernel* entry);
void DeleteEntry(const ScopedKernelLock& lock,
bool save_to_journal,
EntryKernel* entry,
EntryKernelSet* entries_to_journal);
// A private version of the public GetMetaHandlesOfType for when you already
// have a ScopedKernelLock.
void GetMetaHandlesOfType(const ScopedKernelLock& lock,
BaseTransaction* trans,
ModelType type,
std::vector<int64>* result);
Kernel* kernel_;
scoped_ptr<DirectoryBackingStore> store_;
UnrecoverableErrorHandler* const unrecoverable_error_handler_;
const ReportUnrecoverableErrorFunction report_unrecoverable_error_function_;
bool unrecoverable_error_set_;
// Not owned.
NigoriHandler* const nigori_handler_;
Cryptographer* const cryptographer_;
InvariantCheckLevel invariant_check_level_;
// Maintain deleted entries not in |kernel_| until it's verified that they
// are deleted in native models as well.
scoped_ptr<DeleteJournal> delete_journal_;
} // namespace syncable
} // namespace syncer