blob: f5dde90b7a4df9b0cbcf22e47c988507b96d0c3e [file] [log] [blame]
// 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/syncable/syncable.h"
#include <algorithm>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iterator>
#include <limits>
#include <set>
#include <string>
#include "base/basictypes.h"
#include "base/debug/trace_event.h"
#include "base/compiler_specific.h"
#include "base/debug/trace_event.h"
#include "base/file_util.h"
#include "base/hash_tables.h"
#include "base/location.h"
#include "base/logging.h"
#include "base/memory/scoped_ptr.h"
#include "base/perftimer.h"
#include "base/stl_util.h"
#include "base/string_number_conversions.h"
#include "base/string_util.h"
#include "base/time.h"
#include "base/utf_string_conversions.h"
#include "base/values.h"
#include "sync/protocol/proto_value_conversions.h"
#include "sync/protocol/service_constants.h"
#include "sync/syncable/directory_backing_store.h"
#include "sync/syncable/directory_change_delegate.h"
#include "sync/syncable/in_memory_directory_backing_store.h"
#include "sync/syncable/model_type.h"
#include "sync/syncable/on_disk_directory_backing_store.h"
#include "sync/syncable/syncable-inl.h"
#include "sync/syncable/syncable_changes_version.h"
#include "sync/syncable/syncable_columns.h"
#include "sync/syncable/syncable_enum_conversions.h"
#include "sync/syncable/transaction_observer.h"
#include "sync/util/logging.h"
#include "sync/util/cryptographer.h"
#include "net/base/escape.h"
namespace {
enum InvariantCheckLevel {
OFF = 0,
VERIFY_IN_MEMORY = 1,
FULL_DB_VERIFICATION = 2
};
const InvariantCheckLevel kInvariantCheckLevel = VERIFY_IN_MEMORY;
// Max number of milliseconds to spend checking syncable entry invariants
const int kInvariantCheckMaxMs = 50;
// This function checks to see if the given list of Metahandles has any nodes
// whose PREV_ID, PARENT_ID or NEXT_ID values refer to ID values that do not
// actually exist. Returns true on success.
//
// This function is "Unsafe" because it does not attempt to acquire any locks
// that may be protecting this list that gets passed in. The caller is
// responsible for ensuring that no one modifies this list while the function is
// running.
bool VerifyReferenceIntegrityUnsafe(const syncable::MetahandlesIndex &index) {
TRACE_EVENT0("sync", "SyncDatabaseIntegrityCheck");
using namespace syncable;
typedef base::hash_set<std::string> IdsSet;
IdsSet ids_set;
bool is_ok = true;
for (MetahandlesIndex::const_iterator it = index.begin();
it != index.end(); ++it) {
EntryKernel* entry = *it;
bool is_duplicate_id = !(ids_set.insert(entry->ref(ID).value()).second);
is_ok = is_ok && !is_duplicate_id;
}
IdsSet::iterator end = ids_set.end();
for (MetahandlesIndex::const_iterator it = index.begin();
it != index.end(); ++it) {
EntryKernel* entry = *it;
bool prev_exists = (ids_set.find(entry->ref(PREV_ID).value()) != end);
bool parent_exists = (ids_set.find(entry->ref(PARENT_ID).value()) != end);
bool next_exists = (ids_set.find(entry->ref(NEXT_ID).value()) != end);
is_ok = is_ok && prev_exists && parent_exists && next_exists;
}
return is_ok;
}
} // namespace
using std::string;
using browser_sync::Encryptor;
using browser_sync::ReportUnrecoverableErrorFunction;
using browser_sync::UnrecoverableErrorHandler;
namespace syncable {
namespace {
// Function to handle runtime failures on syncable code. Rather than crashing,
// if the |condition| is false the following will happen:
// 1. Sets unrecoverable error on transaction.
// 2. Returns false.
bool SyncAssert(bool condition,
const tracked_objects::Location& location,
const char* msg,
BaseTransaction* trans) {
if (!condition) {
trans->OnUnrecoverableError(location, msg);
return false;
}
return true;
}
} // namespace
#define ENUM_CASE(x) case x: return #x; break
std::string WriterTagToString(WriterTag writer_tag) {
switch (writer_tag) {
ENUM_CASE(INVALID);
ENUM_CASE(SYNCER);
ENUM_CASE(AUTHWATCHER);
ENUM_CASE(UNITTEST);
ENUM_CASE(VACUUM_AFTER_SAVE);
ENUM_CASE(PURGE_ENTRIES);
ENUM_CASE(SYNCAPI);
};
NOTREACHED();
return "";
}
#undef ENUM_CASE
WriteTransactionInfo::WriteTransactionInfo(
int64 id,
tracked_objects::Location location,
WriterTag writer,
ImmutableEntryKernelMutationMap mutations)
: id(id),
location_string(location.ToString()),
writer(writer),
mutations(mutations) {}
WriteTransactionInfo::WriteTransactionInfo()
: id(-1), writer(INVALID) {}
WriteTransactionInfo::~WriteTransactionInfo() {}
base::DictionaryValue* WriteTransactionInfo::ToValue(
size_t max_mutations_size) const {
DictionaryValue* dict = new DictionaryValue();
dict->SetString("id", base::Int64ToString(id));
dict->SetString("location", location_string);
dict->SetString("writer", WriterTagToString(writer));
Value* mutations_value = NULL;
const size_t mutations_size = mutations.Get().size();
if (mutations_size <= max_mutations_size) {
mutations_value = EntryKernelMutationMapToValue(mutations.Get());
} else {
mutations_value =
Value::CreateStringValue(
base::Uint64ToString(static_cast<uint64>(mutations_size)) +
" mutations");
}
dict->Set("mutations", mutations_value);
return dict;
}
DictionaryValue* EntryKernelMutationToValue(
const EntryKernelMutation& mutation) {
DictionaryValue* dict = new DictionaryValue();
dict->Set("original", mutation.original.ToValue());
dict->Set("mutated", mutation.mutated.ToValue());
return dict;
}
ListValue* EntryKernelMutationMapToValue(
const EntryKernelMutationMap& mutations) {
ListValue* list = new ListValue();
for (EntryKernelMutationMap::const_iterator it = mutations.begin();
it != mutations.end(); ++it) {
list->Append(EntryKernelMutationToValue(it->second));
}
return list;
}
namespace {
// A ScopedIndexUpdater temporarily removes an entry from an index,
// and restores it to the index when the scope exits. This simplifies
// the common pattern where items need to be removed from an index
// before updating the field.
//
// This class is parameterized on the Indexer traits type, which
// must define a Comparator and a static bool ShouldInclude
// function for testing whether the item ought to be included
// in the index.
template<typename Indexer>
class ScopedIndexUpdater {
public:
ScopedIndexUpdater(const ScopedKernelLock& proof_of_lock,
EntryKernel* entry,
typename Index<Indexer>::Set* index)
: entry_(entry),
index_(index) {
// First call to ShouldInclude happens before the field is updated.
if (Indexer::ShouldInclude(entry_)) {
// TODO(lipalani): Replace this CHECK with |SyncAssert| by refactorting
// this class into a function.
CHECK(index_->erase(entry_));
}
}
~ScopedIndexUpdater() {
// Second call to ShouldInclude happens after the field is updated.
if (Indexer::ShouldInclude(entry_)) {
// TODO(lipalani): Replace this CHECK with |SyncAssert| by refactorting
// this class into a function.
CHECK(index_->insert(entry_).second);
}
}
private:
// The entry that was temporarily removed from the index.
EntryKernel* entry_;
// The index which we are updating.
typename Index<Indexer>::Set* const index_;
};
// Helper function to add an item to the index, if it ought to be added.
template<typename Indexer>
void InitializeIndexEntry(EntryKernel* entry,
typename Index<Indexer>::Set* index) {
if (Indexer::ShouldInclude(entry)) {
index->insert(entry);
}
}
} // namespace
///////////////////////////////////////////////////////////////////////////
// Comparator and filter functions for the indices.
// static
bool ClientTagIndexer::ShouldInclude(const EntryKernel* a) {
return !a->ref(UNIQUE_CLIENT_TAG).empty();
}
bool ParentIdAndHandleIndexer::Comparator::operator() (
const syncable::EntryKernel* a,
const syncable::EntryKernel* b) const {
int cmp = a->ref(PARENT_ID).compare(b->ref(PARENT_ID));
if (cmp != 0)
return cmp < 0;
int64 a_position = a->ref(SERVER_POSITION_IN_PARENT);
int64 b_position = b->ref(SERVER_POSITION_IN_PARENT);
if (a_position != b_position)
return a_position < b_position;
cmp = a->ref(ID).compare(b->ref(ID));
return cmp < 0;
}
// static
bool ParentIdAndHandleIndexer::ShouldInclude(const EntryKernel* a) {
// This index excludes deleted items and the root item. The root
// item is excluded so that it doesn't show up as a child of itself.
return !a->ref(IS_DEL) && !a->ref(ID).IsRoot();
}
///////////////////////////////////////////////////////////////////////////
// EntryKernel
EntryKernel::EntryKernel() : dirty_(false) {
// Everything else should already be default-initialized.
for (int i = INT64_FIELDS_BEGIN; i < INT64_FIELDS_END; ++i) {
int64_fields[i] = 0;
}
}
EntryKernel::~EntryKernel() {}
syncable::ModelType EntryKernel::GetServerModelType() const {
ModelType specifics_type = GetModelTypeFromSpecifics(ref(SERVER_SPECIFICS));
if (specifics_type != UNSPECIFIED)
return specifics_type;
if (ref(ID).IsRoot())
return TOP_LEVEL_FOLDER;
// Loose check for server-created top-level folders that aren't
// bound to a particular model type.
if (!ref(UNIQUE_SERVER_TAG).empty() && ref(SERVER_IS_DIR))
return TOP_LEVEL_FOLDER;
return UNSPECIFIED;
}
namespace {
// Utility function to loop through a set of enum values and add the
// field keys/values in the kernel to the given dictionary.
//
// V should be convertible to Value.
template <class T, class U, class V>
void SetFieldValues(const EntryKernel& kernel,
DictionaryValue* dictionary_value,
const char* (*enum_key_fn)(T),
V* (*enum_value_fn)(U),
int field_key_min, int field_key_max) {
DCHECK_LE(field_key_min, field_key_max);
for (int i = field_key_min; i <= field_key_max; ++i) {
T field = static_cast<T>(i);
const std::string& key = enum_key_fn(field);
V* value = enum_value_fn(kernel.ref(field));
dictionary_value->Set(key, value);
}
}
// Helper functions for SetFieldValues().
StringValue* Int64ToValue(int64 i) {
return Value::CreateStringValue(base::Int64ToString(i));
}
StringValue* TimeToValue(const base::Time& t) {
return Value::CreateStringValue(browser_sync::GetTimeDebugString(t));
}
StringValue* IdToValue(const Id& id) {
return id.ToValue();
}
} // namespace
DictionaryValue* EntryKernel::ToValue() const {
DictionaryValue* kernel_info = new DictionaryValue();
kernel_info->SetBoolean("isDirty", is_dirty());
kernel_info->Set("serverModelType", ModelTypeToValue(GetServerModelType()));
// Int64 fields.
SetFieldValues(*this, kernel_info,
&GetMetahandleFieldString, &Int64ToValue,
INT64_FIELDS_BEGIN, META_HANDLE);
SetFieldValues(*this, kernel_info,
&GetBaseVersionString, &Int64ToValue,
META_HANDLE + 1, BASE_VERSION);
SetFieldValues(*this, kernel_info,
&GetInt64FieldString, &Int64ToValue,
BASE_VERSION + 1, INT64_FIELDS_END - 1);
// Time fields.
SetFieldValues(*this, kernel_info,
&GetTimeFieldString, &TimeToValue,
TIME_FIELDS_BEGIN, TIME_FIELDS_END - 1);
// ID fields.
SetFieldValues(*this, kernel_info,
&GetIdFieldString, &IdToValue,
ID_FIELDS_BEGIN, ID_FIELDS_END - 1);
// Bit fields.
SetFieldValues(*this, kernel_info,
&GetIndexedBitFieldString, &Value::CreateBooleanValue,
BIT_FIELDS_BEGIN, INDEXED_BIT_FIELDS_END - 1);
SetFieldValues(*this, kernel_info,
&GetIsDelFieldString, &Value::CreateBooleanValue,
INDEXED_BIT_FIELDS_END, IS_DEL);
SetFieldValues(*this, kernel_info,
&GetBitFieldString, &Value::CreateBooleanValue,
IS_DEL + 1, BIT_FIELDS_END - 1);
// String fields.
{
// Pick out the function overload we want.
StringValue* (*string_to_value)(const std::string&) =
&Value::CreateStringValue;
SetFieldValues(*this, kernel_info,
&GetStringFieldString, string_to_value,
STRING_FIELDS_BEGIN, STRING_FIELDS_END - 1);
}
// Proto fields.
SetFieldValues(*this, kernel_info,
&GetProtoFieldString, &browser_sync::EntitySpecificsToValue,
PROTO_FIELDS_BEGIN, PROTO_FIELDS_END - 1);
// Bit temps.
SetFieldValues(*this, kernel_info,
&GetBitTempString, &Value::CreateBooleanValue,
BIT_TEMPS_BEGIN, BIT_TEMPS_END - 1);
return kernel_info;
}
///////////////////////////////////////////////////////////////////////////
// Directory
// static
const FilePath::CharType Directory::kSyncDatabaseFilename[] =
FILE_PATH_LITERAL("SyncData.sqlite3");
void Directory::InitKernelForTest(
const std::string& name,
DirectoryChangeDelegate* delegate,
const browser_sync::WeakHandle<TransactionObserver>&
transaction_observer) {
DCHECK(!kernel_);
kernel_ = new Kernel(name, KernelLoadInfo(), delegate, transaction_observer);
}
Directory::PersistedKernelInfo::PersistedKernelInfo()
: next_id(0) {
for (int i = FIRST_REAL_MODEL_TYPE; i < MODEL_TYPE_COUNT; ++i) {
reset_download_progress(ModelTypeFromInt(i));
}
}
Directory::PersistedKernelInfo::~PersistedKernelInfo() {}
void Directory::PersistedKernelInfo::reset_download_progress(
ModelType model_type) {
download_progress[model_type].set_data_type_id(
GetSpecificsFieldNumberFromModelType(model_type));
// An empty-string token indicates no prior knowledge.
download_progress[model_type].set_token(std::string());
}
Directory::SaveChangesSnapshot::SaveChangesSnapshot()
: kernel_info_status(KERNEL_SHARE_INFO_INVALID) {
}
Directory::SaveChangesSnapshot::~SaveChangesSnapshot() {}
Directory::Kernel::Kernel(
const std::string& name,
const KernelLoadInfo& info, DirectoryChangeDelegate* delegate,
const browser_sync::WeakHandle<TransactionObserver>&
transaction_observer)
: refcount(1),
next_write_transaction_id(0),
name(name),
metahandles_index(new Directory::MetahandlesIndex),
ids_index(new Directory::IdsIndex),
parent_id_child_index(new Directory::ParentIdChildIndex),
client_tag_index(new Directory::ClientTagIndex),
unsynced_metahandles(new MetahandleSet),
dirty_metahandles(new MetahandleSet),
metahandles_to_purge(new MetahandleSet),
info_status(Directory::KERNEL_SHARE_INFO_VALID),
persisted_info(info.kernel_info),
cache_guid(info.cache_guid),
next_metahandle(info.max_metahandle + 1),
delegate(delegate),
transaction_observer(transaction_observer) {
DCHECK(delegate);
DCHECK(transaction_observer.IsInitialized());
}
void Directory::Kernel::AddRef() {
base::subtle::NoBarrier_AtomicIncrement(&refcount, 1);
}
void Directory::Kernel::Release() {
if (!base::subtle::NoBarrier_AtomicIncrement(&refcount, -1))
delete this;
}
Directory::Kernel::~Kernel() {
CHECK_EQ(0, refcount);
delete unsynced_metahandles;
delete dirty_metahandles;
delete metahandles_to_purge;
delete parent_id_child_index;
delete client_tag_index;
delete ids_index;
STLDeleteElements(metahandles_index);
delete metahandles_index;
}
Directory::Directory(
Encryptor* encryptor,
UnrecoverableErrorHandler* unrecoverable_error_handler,
ReportUnrecoverableErrorFunction report_unrecoverable_error_function)
: cryptographer_(encryptor),
kernel_(NULL),
store_(NULL),
unrecoverable_error_handler_(unrecoverable_error_handler),
report_unrecoverable_error_function_(
report_unrecoverable_error_function),
unrecoverable_error_set_(false) {
}
Directory::~Directory() {
Close();
}
DirOpenResult Directory::Open(
const FilePath& file_path, const string& name,
DirectoryChangeDelegate* delegate,
const browser_sync::WeakHandle<TransactionObserver>&
transaction_observer) {
TRACE_EVENT0("sync", "SyncDatabaseOpen");
FilePath db_path(file_path);
file_util::AbsolutePath(&db_path);
DirectoryBackingStore* store = new OnDiskDirectoryBackingStore(name, db_path);
const DirOpenResult result =
OpenImpl(store, name, delegate, transaction_observer);
if (OPENED != result)
Close();
return result;
}
DirOpenResult Directory::OpenInMemoryForTest(
const string& name, DirectoryChangeDelegate* delegate,
const browser_sync::WeakHandle<TransactionObserver>&
transaction_observer) {
DirectoryBackingStore* store = new InMemoryDirectoryBackingStore(name);
const DirOpenResult result =
OpenImpl(store, name, delegate, transaction_observer);
if (OPENED != result)
Close();
return result;
}
void Directory::InitializeIndices() {
MetahandlesIndex::iterator it = kernel_->metahandles_index->begin();
for (; it != kernel_->metahandles_index->end(); ++it) {
EntryKernel* entry = *it;
InitializeIndexEntry<ParentIdAndHandleIndexer>(entry,
kernel_->parent_id_child_index);
InitializeIndexEntry<IdIndexer>(entry, kernel_->ids_index);
InitializeIndexEntry<ClientTagIndexer>(entry, kernel_->client_tag_index);
const int64 metahandle = entry->ref(META_HANDLE);
if (entry->ref(IS_UNSYNCED))
kernel_->unsynced_metahandles->insert(metahandle);
if (entry->ref(IS_UNAPPLIED_UPDATE)) {
const ModelType type = entry->GetServerModelType();
kernel_->unapplied_update_metahandles[type].insert(metahandle);
}
DCHECK(!entry->is_dirty());
}
}
DirOpenResult Directory::OpenImpl(
DirectoryBackingStore* store,
const string& name,
DirectoryChangeDelegate* delegate,
const browser_sync::WeakHandle<TransactionObserver>&
transaction_observer) {
DCHECK_EQ(static_cast<DirectoryBackingStore*>(NULL), store_);
store_ = store;
KernelLoadInfo info;
// Temporary indices before kernel_ initialized in case Load fails. We 0(1)
// swap these later.
MetahandlesIndex metas_bucket;
DirOpenResult result = store_->Load(&metas_bucket, &info);
if (OPENED != result)
return result;
if (!VerifyReferenceIntegrityUnsafe(metas_bucket))
return FAILED_LOGICAL_CORRUPTION;
kernel_ = new Kernel(name, info, delegate, transaction_observer);
kernel_->metahandles_index->swap(metas_bucket);
InitializeIndices();
return OPENED;
}
void Directory::Close() {
if (store_)
delete store_;
store_ = NULL;
if (kernel_) {
bool del = !base::subtle::NoBarrier_AtomicIncrement(&kernel_->refcount, -1);
DCHECK(del) << "Kernel should only have a single ref";
if (del)
delete kernel_;
kernel_ = NULL;
}
}
void Directory::OnUnrecoverableError(const BaseTransaction* trans,
const tracked_objects::Location& location,
const std::string & message) {
DCHECK(trans != NULL);
unrecoverable_error_set_ = true;
unrecoverable_error_handler_->OnUnrecoverableError(location,
message);
}
EntryKernel* Directory::GetEntryById(const Id& id) {
ScopedKernelLock lock(this);
return GetEntryById(id, &lock);
}
EntryKernel* Directory::GetEntryById(const Id& id,
ScopedKernelLock* const lock) {
DCHECK(kernel_);
// Find it in the in memory ID index.
kernel_->needle.put(ID, id);
IdsIndex::iterator id_found = kernel_->ids_index->find(&kernel_->needle);
if (id_found != kernel_->ids_index->end()) {
return *id_found;
}
return NULL;
}
EntryKernel* Directory::GetEntryByClientTag(const string& tag) {
ScopedKernelLock lock(this);
DCHECK(kernel_);
// Find it in the ClientTagIndex.
kernel_->needle.put(UNIQUE_CLIENT_TAG, tag);
ClientTagIndex::iterator found = kernel_->client_tag_index->find(
&kernel_->needle);
if (found != kernel_->client_tag_index->end()) {
return *found;
}
return NULL;
}
EntryKernel* Directory::GetEntryByServerTag(const string& tag) {
ScopedKernelLock lock(this);
DCHECK(kernel_);
// We don't currently keep a separate index for the tags. Since tags
// only exist for server created items that are the first items
// to be created in a store, they should have small metahandles.
// So, we just iterate over the items in sorted metahandle order,
// looking for a match.
MetahandlesIndex& set = *kernel_->metahandles_index;
for (MetahandlesIndex::iterator i = set.begin(); i != set.end(); ++i) {
if ((*i)->ref(UNIQUE_SERVER_TAG) == tag) {
return *i;
}
}
return NULL;
}
EntryKernel* Directory::GetEntryByHandle(int64 metahandle) {
ScopedKernelLock lock(this);
return GetEntryByHandle(metahandle, &lock);
}
EntryKernel* Directory::GetEntryByHandle(int64 metahandle,
ScopedKernelLock* lock) {
// Look up in memory
kernel_->needle.put(META_HANDLE, metahandle);
MetahandlesIndex::iterator found =
kernel_->metahandles_index->find(&kernel_->needle);
if (found != kernel_->metahandles_index->end()) {
// Found it in memory. Easy.
return *found;
}
return NULL;
}
bool Directory::GetChildHandlesById(
BaseTransaction* trans, const Id& parent_id,
Directory::ChildHandles* result) {
if (!SyncAssert(this == trans->directory(), FROM_HERE,
"Directories don't match", trans))
return false;
result->clear();
ScopedKernelLock lock(this);
AppendChildHandles(lock, parent_id, result);
return true;
}
bool Directory::GetChildHandlesByHandle(
BaseTransaction* trans, int64 handle,
Directory::ChildHandles* result) {
if (!SyncAssert(this == trans->directory(), FROM_HERE,
"Directories don't match", trans))
return false;
result->clear();
ScopedKernelLock lock(this);
EntryKernel* kernel = GetEntryByHandle(handle, &lock);
if (!kernel)
return true;
AppendChildHandles(lock, kernel->ref(ID), result);
return true;
}
EntryKernel* Directory::GetRootEntry() {
return GetEntryById(Id());
}
bool Directory::InsertEntry(WriteTransaction* trans, EntryKernel* entry) {
ScopedKernelLock lock(this);
return InsertEntry(trans, entry, &lock);
}
bool Directory::InsertEntry(WriteTransaction* trans,
EntryKernel* entry,
ScopedKernelLock* lock) {
DCHECK(NULL != lock);
if (!SyncAssert(NULL != entry, FROM_HERE, "Entry is null", trans))
return false;
static const char error[] = "Entry already in memory index.";
if (!SyncAssert(kernel_->metahandles_index->insert(entry).second,
FROM_HERE,
error,
trans))
return false;
if (!entry->ref(IS_DEL)) {
if (!SyncAssert(kernel_->parent_id_child_index->insert(entry).second,
FROM_HERE,
error,
trans)) {
return false;
}
}
if (!SyncAssert(kernel_->ids_index->insert(entry).second,
FROM_HERE,
error,
trans))
return false;
// Should NEVER be created with a client tag.
if (!SyncAssert(entry->ref(UNIQUE_CLIENT_TAG).empty(), FROM_HERE,
"Client should be empty", trans))
return false;
return true;
}
bool Directory::ReindexId(WriteTransaction* trans,
EntryKernel* const entry,
const Id& new_id) {
ScopedKernelLock lock(this);
if (NULL != GetEntryById(new_id, &lock))
return false;
{
// Update the indices that depend on the ID field.
ScopedIndexUpdater<IdIndexer> updater_a(lock, entry, kernel_->ids_index);
ScopedIndexUpdater<ParentIdAndHandleIndexer> updater_b(lock, entry,
kernel_->parent_id_child_index);
entry->put(ID, new_id);
}
return true;
}
bool Directory::ReindexParentId(WriteTransaction* trans,
EntryKernel* const entry,
const Id& new_parent_id) {
ScopedKernelLock lock(this);
{
// Update the indices that depend on the PARENT_ID field.
ScopedIndexUpdater<ParentIdAndHandleIndexer> index_updater(lock, entry,
kernel_->parent_id_child_index);
entry->put(PARENT_ID, new_parent_id);
}
return true;
}
bool Directory::unrecoverable_error_set(const BaseTransaction* trans) const {
DCHECK(trans != NULL);
return unrecoverable_error_set_;
}
void Directory::ClearDirtyMetahandles() {
kernel_->transaction_mutex.AssertAcquired();
kernel_->dirty_metahandles->clear();
}
bool Directory::SafeToPurgeFromMemory(WriteTransaction* trans,
const EntryKernel* const entry) const {
bool safe = entry->ref(IS_DEL) && !entry->is_dirty() &&
!entry->ref(SYNCING) && !entry->ref(IS_UNAPPLIED_UPDATE) &&
!entry->ref(IS_UNSYNCED);
if (safe) {
int64 handle = entry->ref(META_HANDLE);
const ModelType type = entry->GetServerModelType();
if (!SyncAssert(kernel_->dirty_metahandles->count(handle) == 0U,
FROM_HERE,
"Dirty metahandles should be empty", trans))
return false;
// TODO(tim): Bug 49278.
if (!SyncAssert(!kernel_->unsynced_metahandles->count(handle),
FROM_HERE,
"Unsynced handles should be empty",
trans))
return false;
if (!SyncAssert(!kernel_->unapplied_update_metahandles[type].count(handle),
FROM_HERE,
"Unapplied metahandles should be empty",
trans))
return false;
}
return safe;
}
void Directory::TakeSnapshotForSaveChanges(SaveChangesSnapshot* snapshot) {
ReadTransaction trans(FROM_HERE, this);
ScopedKernelLock lock(this);
// If there is an unrecoverable error then just bail out.
if (unrecoverable_error_set(&trans))
return;
// Deep copy dirty entries from kernel_->metahandles_index into snapshot and
// clear dirty flags.
for (MetahandleSet::const_iterator i = kernel_->dirty_metahandles->begin();
i != kernel_->dirty_metahandles->end(); ++i) {
EntryKernel* entry = GetEntryByHandle(*i, &lock);
if (!entry)
continue;
// Skip over false positives; it happens relatively infrequently.
if (!entry->is_dirty())
continue;
snapshot->dirty_metas.insert(snapshot->dirty_metas.end(), *entry);
DCHECK_EQ(1U, kernel_->dirty_metahandles->count(*i));
// We don't bother removing from the index here as we blow the entire thing
// in a moment, and it unnecessarily complicates iteration.
entry->clear_dirty(NULL);
}
ClearDirtyMetahandles();
// Set purged handles.
DCHECK(snapshot->metahandles_to_purge.empty());
snapshot->metahandles_to_purge.swap(*(kernel_->metahandles_to_purge));
// Fill kernel_info_status and kernel_info.
snapshot->kernel_info = kernel_->persisted_info;
// To avoid duplicates when the process crashes, we record the next_id to be
// greater magnitude than could possibly be reached before the next save
// changes. In other words, it's effectively impossible for the user to
// generate 65536 new bookmarks in 3 seconds.
snapshot->kernel_info.next_id -= 65536;
snapshot->kernel_info_status = kernel_->info_status;
// This one we reset on failure.
kernel_->info_status = KERNEL_SHARE_INFO_VALID;
}
bool Directory::SaveChanges() {
bool success = false;
DCHECK(store_);
base::AutoLock scoped_lock(kernel_->save_changes_mutex);
// Snapshot and save.
SaveChangesSnapshot snapshot;
TakeSnapshotForSaveChanges(&snapshot);
success = store_->SaveChanges(snapshot);
// Handle success or failure.
if (success)
success = VacuumAfterSaveChanges(snapshot);
else
HandleSaveChangesFailure(snapshot);
return success;
}
bool Directory::VacuumAfterSaveChanges(const SaveChangesSnapshot& snapshot) {
if (snapshot.dirty_metas.empty())
return true;
// Need a write transaction as we are about to permanently purge entries.
WriteTransaction trans(FROM_HERE, VACUUM_AFTER_SAVE, this);
ScopedKernelLock lock(this);
// Now drop everything we can out of memory.
for (EntryKernelSet::const_iterator i = snapshot.dirty_metas.begin();
i != snapshot.dirty_metas.end(); ++i) {
kernel_->needle.put(META_HANDLE, i->ref(META_HANDLE));
MetahandlesIndex::iterator found =
kernel_->metahandles_index->find(&kernel_->needle);
EntryKernel* entry = (found == kernel_->metahandles_index->end() ?
NULL : *found);
if (entry && SafeToPurgeFromMemory(&trans, entry)) {
// We now drop deleted metahandles that are up to date on both the client
// and the server.
size_t num_erased = 0;
num_erased = kernel_->ids_index->erase(entry);
DCHECK_EQ(1u, num_erased);
num_erased = kernel_->metahandles_index->erase(entry);
DCHECK_EQ(1u, num_erased);
// Might not be in it
num_erased = kernel_->client_tag_index->erase(entry);
DCHECK_EQ(entry->ref(UNIQUE_CLIENT_TAG).empty(), !num_erased);
if (!SyncAssert(!kernel_->parent_id_child_index->count(entry),
FROM_HERE,
"Deleted entry still present",
(&trans)))
return false;
delete entry;
}
if (trans.unrecoverable_error_set())
return false;
}
return true;
}
void Directory::PurgeEntriesWithTypeIn(ModelTypeSet types) {
if (types.Empty())
return;
{
WriteTransaction trans(FROM_HERE, PURGE_ENTRIES, this);
{
ScopedKernelLock lock(this);
MetahandlesIndex::iterator it = kernel_->metahandles_index->begin();
while (it != kernel_->metahandles_index->end()) {
const sync_pb::EntitySpecifics& local_specifics = (*it)->ref(SPECIFICS);
const sync_pb::EntitySpecifics& server_specifics =
(*it)->ref(SERVER_SPECIFICS);
ModelType local_type = GetModelTypeFromSpecifics(local_specifics);
ModelType server_type = GetModelTypeFromSpecifics(server_specifics);
// Note the dance around incrementing |it|, since we sometimes erase().
if ((IsRealDataType(local_type) && types.Has(local_type)) ||
(IsRealDataType(server_type) && types.Has(server_type))) {
if (!UnlinkEntryFromOrder(*it, NULL, &lock))
return;
int64 handle = (*it)->ref(META_HANDLE);
kernel_->metahandles_to_purge->insert(handle);
size_t num_erased = 0;
EntryKernel* entry = *it;
num_erased = kernel_->ids_index->erase(entry);
DCHECK_EQ(1u, num_erased);
num_erased = kernel_->client_tag_index->erase(entry);
DCHECK_EQ(entry->ref(UNIQUE_CLIENT_TAG).empty(), !num_erased);
num_erased = kernel_->unsynced_metahandles->erase(handle);
DCHECK_EQ(entry->ref(IS_UNSYNCED), num_erased > 0);
num_erased =
kernel_->unapplied_update_metahandles[server_type].erase(handle);
DCHECK_EQ(entry->ref(IS_UNAPPLIED_UPDATE), num_erased > 0);
num_erased = kernel_->parent_id_child_index->erase(entry);
DCHECK_EQ(entry->ref(IS_DEL), !num_erased);
kernel_->metahandles_index->erase(it++);
delete entry;
} else {
++it;
}
}
// Ensure meta tracking for these data types reflects the deleted state.
for (syncable::ModelTypeSet::Iterator it = types.First();
it.Good(); it.Inc()) {
set_initial_sync_ended_for_type_unsafe(it.Get(), false);
kernel_->persisted_info.reset_download_progress(it.Get());
}
}
}
}
void Directory::HandleSaveChangesFailure(const SaveChangesSnapshot& snapshot) {
ScopedKernelLock lock(this);
kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
// Because we optimistically cleared the dirty bit on the real entries when
// taking the snapshot, we must restore it on failure. Not doing this could
// cause lost data, if no other changes are made to the in-memory entries
// that would cause the dirty bit to get set again. Setting the bit ensures
// that SaveChanges will at least try again later.
for (EntryKernelSet::const_iterator i = snapshot.dirty_metas.begin();
i != snapshot.dirty_metas.end(); ++i) {
kernel_->needle.put(META_HANDLE, i->ref(META_HANDLE));
MetahandlesIndex::iterator found =
kernel_->metahandles_index->find(&kernel_->needle);
if (found != kernel_->metahandles_index->end()) {
(*found)->mark_dirty(kernel_->dirty_metahandles);
}
}
kernel_->metahandles_to_purge->insert(snapshot.metahandles_to_purge.begin(),
snapshot.metahandles_to_purge.end());
}
void Directory::GetDownloadProgress(
ModelType model_type,
sync_pb::DataTypeProgressMarker* value_out) const {
ScopedKernelLock lock(this);
return value_out->CopyFrom(
kernel_->persisted_info.download_progress[model_type]);
}
void Directory::GetDownloadProgressAsString(
ModelType model_type,
std::string* value_out) const {
ScopedKernelLock lock(this);
kernel_->persisted_info.download_progress[model_type].SerializeToString(
value_out);
}
size_t Directory::GetEntriesCount() const {
ScopedKernelLock lock(this);
return kernel_->metahandles_index ? kernel_->metahandles_index->size() : 0;
}
void Directory::SetDownloadProgress(
ModelType model_type,
const sync_pb::DataTypeProgressMarker& new_progress) {
ScopedKernelLock lock(this);
kernel_->persisted_info.download_progress[model_type].CopyFrom(new_progress);
kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}
bool Directory::initial_sync_ended_for_type(ModelType type) const {
ScopedKernelLock lock(this);
return kernel_->persisted_info.initial_sync_ended.Has(type);
}
template <class T> void Directory::TestAndSet(
T* kernel_data, const T* data_to_set) {
if (*kernel_data != *data_to_set) {
*kernel_data = *data_to_set;
kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}
}
void Directory::set_initial_sync_ended_for_type(ModelType type, bool x) {
ScopedKernelLock lock(this);
set_initial_sync_ended_for_type_unsafe(type, x);
}
void Directory::set_initial_sync_ended_for_type_unsafe(ModelType type,
bool x) {
if (kernel_->persisted_info.initial_sync_ended.Has(type) == x)
return;
if (x) {
kernel_->persisted_info.initial_sync_ended.Put(type);
} else {
kernel_->persisted_info.initial_sync_ended.Remove(type);
}
kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}
void Directory::SetNotificationStateUnsafe(
const std::string& notification_state) {
if (notification_state == kernel_->persisted_info.notification_state)
return;
kernel_->persisted_info.notification_state = notification_state;
kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}
string Directory::store_birthday() const {
ScopedKernelLock lock(this);
return kernel_->persisted_info.store_birthday;
}
void Directory::set_store_birthday(const string& store_birthday) {
ScopedKernelLock lock(this);
if (kernel_->persisted_info.store_birthday == store_birthday)
return;
kernel_->persisted_info.store_birthday = store_birthday;
kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}
std::string Directory::GetNotificationState() const {
ScopedKernelLock lock(this);
std::string notification_state = kernel_->persisted_info.notification_state;
return notification_state;
}
void Directory::SetNotificationState(const std::string& notification_state) {
ScopedKernelLock lock(this);
SetNotificationStateUnsafe(notification_state);
}
string Directory::cache_guid() const {
// No need to lock since nothing ever writes to it after load.
return kernel_->cache_guid;
}
browser_sync::Cryptographer* Directory::GetCryptographer(
const BaseTransaction* trans) {
DCHECK_EQ(this, trans->directory());
return &cryptographer_;
}
void Directory::GetAllMetaHandles(BaseTransaction* trans,
MetahandleSet* result) {
result->clear();
ScopedKernelLock lock(this);
MetahandlesIndex::iterator i;
for (i = kernel_->metahandles_index->begin();
i != kernel_->metahandles_index->end();
++i) {
result->insert((*i)->ref(META_HANDLE));
}
}
void Directory::GetAllEntryKernels(BaseTransaction* trans,
std::vector<const EntryKernel*>* result) {
result->clear();
ScopedKernelLock lock(this);
result->insert(result->end(),
kernel_->metahandles_index->begin(),
kernel_->metahandles_index->end());
}
void Directory::GetUnsyncedMetaHandles(BaseTransaction* trans,
UnsyncedMetaHandles* result) {
result->clear();
ScopedKernelLock lock(this);
copy(kernel_->unsynced_metahandles->begin(),
kernel_->unsynced_metahandles->end(), back_inserter(*result));
}
int64 Directory::unsynced_entity_count() const {
ScopedKernelLock lock(this);
return kernel_->unsynced_metahandles->size();
}
FullModelTypeSet Directory::GetServerTypesWithUnappliedUpdates(
BaseTransaction* trans) const {
syncable::FullModelTypeSet server_types;
ScopedKernelLock lock(this);
for (int i = UNSPECIFIED; i < MODEL_TYPE_COUNT; ++i) {
const ModelType type = ModelTypeFromInt(i);
if (!kernel_->unapplied_update_metahandles[type].empty()) {
server_types.Put(type);
}
}
return server_types;
}
void Directory::GetUnappliedUpdateMetaHandles(
BaseTransaction* trans,
FullModelTypeSet server_types,
std::vector<int64>* result) {
result->clear();
ScopedKernelLock lock(this);
for (int i = UNSPECIFIED; i < MODEL_TYPE_COUNT; ++i) {
const ModelType type = ModelTypeFromInt(i);
if (server_types.Has(type)) {
std::copy(kernel_->unapplied_update_metahandles[type].begin(),
kernel_->unapplied_update_metahandles[type].end(),
back_inserter(*result));
}
}
}
class IdFilter {
public:
virtual ~IdFilter() { }
virtual bool ShouldConsider(const Id& id) const = 0;
};
class FullScanFilter : public IdFilter {
public:
virtual bool ShouldConsider(const Id& id) const {
return true;
}
};
class SomeIdsFilter : public IdFilter {
public:
virtual bool ShouldConsider(const Id& id) const {
return std::binary_search(ids_.begin(), ids_.end(), id);
}
std::vector<Id> ids_;
};
bool Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
const EntryKernelMutationMap& mutations) {
MetahandleSet handles;
SomeIdsFilter filter;
filter.ids_.reserve(mutations.size());
for (EntryKernelMutationMap::const_iterator it = mutations.begin(),
end = mutations.end(); it != end; ++it) {
filter.ids_.push_back(it->second.mutated.ref(ID));
handles.insert(it->first);
}
std::sort(filter.ids_.begin(), filter.ids_.end());
if (!CheckTreeInvariants(trans, handles, filter))
return false;
return true;
}
bool Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
bool full_scan) {
// TODO(timsteele): This is called every time a WriteTransaction finishes.
// The performance hit is substantial given that we now examine every single
// syncable entry. Need to redesign this.
MetahandleSet handles;
GetAllMetaHandles(trans, &handles);
if (full_scan) {
FullScanFilter fullfilter;
if (!CheckTreeInvariants(trans, handles, fullfilter))
return false;
} else {
SomeIdsFilter filter;
MetahandleSet::iterator i;
for (i = handles.begin() ; i != handles.end() ; ++i) {
Entry e(trans, GET_BY_HANDLE, *i);
if (!SyncAssert(e.good(), FROM_HERE, "Entry is bad", trans))
return false;
filter.ids_.push_back(e.Get(ID));
}
std::sort(filter.ids_.begin(), filter.ids_.end());
if (!CheckTreeInvariants(trans, handles, filter))
return false;
}
return true;
}
bool Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
const MetahandleSet& handles,
const IdFilter& idfilter) {
const int64 max_ms = kInvariantCheckMaxMs;
PerfTimer check_timer;
MetahandleSet::const_iterator i;
int entries_done = 0;
for (i = handles.begin() ; i != handles.end() ; ++i) {
int64 metahandle = *i;
Entry e(trans, GET_BY_HANDLE, metahandle);
if (!SyncAssert(e.good(), FROM_HERE, "Entry is bad", trans))
return false;
syncable::Id id = e.Get(ID);
syncable::Id parentid = e.Get(PARENT_ID);
if (id.IsRoot()) {
if (!SyncAssert(e.Get(IS_DIR), FROM_HERE,
"Entry should be a directory",
trans))
return false;
if (!SyncAssert(parentid.IsRoot(), FROM_HERE,
"Entry should be root",
trans))
return false;
if (!SyncAssert(!e.Get(IS_UNSYNCED), FROM_HERE,
"Entry should be sycned",
trans))
return false;
++entries_done;
continue;
}
if (!e.Get(IS_DEL)) {
if (!SyncAssert(id != parentid, FROM_HERE,
"Id should be different from parent id.",
trans))
return false;
if (!SyncAssert(!e.Get(NON_UNIQUE_NAME).empty(), FROM_HERE,
"Non unique name should not be empty.",
trans))
return false;
int safety_count = handles.size() + 1;
while (!parentid.IsRoot()) {
if (!idfilter.ShouldConsider(parentid))
break;
Entry parent(trans, GET_BY_ID, parentid);
if (!SyncAssert(parent.good(), FROM_HERE,
"Parent entry is not valid.",
trans))
return false;
if (!SyncAssert(parent.Get(IS_DIR), FROM_HERE,
"Parent should be a directory",
trans))
return false;
if (!SyncAssert(!parent.Get(IS_DEL), FROM_HERE,
"Parent should not have been marked for deletion.",
trans))
return false;
if (!SyncAssert(handles.end() != handles.find(parent.Get(META_HANDLE)),
FROM_HERE,
"Parent should be in the index.",
trans))
return false;
parentid = parent.Get(PARENT_ID);
if (!SyncAssert(--safety_count > 0, FROM_HERE,
"Count should be greater than zero.",
trans))
return false;
}
}
int64 base_version = e.Get(BASE_VERSION);
int64 server_version = e.Get(SERVER_VERSION);
bool using_unique_client_tag = !e.Get(UNIQUE_CLIENT_TAG).empty();
if (CHANGES_VERSION == base_version || 0 == base_version) {
if (e.Get(IS_UNAPPLIED_UPDATE)) {
// Must be a new item, or a de-duplicated unique client tag
// that was created both locally and remotely.
if (!using_unique_client_tag) {
if (!SyncAssert(e.Get(IS_DEL), FROM_HERE,
"The entry should not have been deleted.",
trans))
return false;
}
// It came from the server, so it must have a server ID.
if (!SyncAssert(id.ServerKnows(), FROM_HERE,
"The id should be from a server.",
trans))
return false;
} else {
if (e.Get(IS_DIR)) {
// TODO(chron): Implement this mode if clients ever need it.
// For now, you can't combine a client tag and a directory.
if (!SyncAssert(!using_unique_client_tag, FROM_HERE,
"Directory cannot have a client tag.",
trans))
return false;
}
// Should be an uncomitted item, or a successfully deleted one.
if (!e.Get(IS_DEL)) {
if (!SyncAssert(e.Get(IS_UNSYNCED), FROM_HERE,
"The item should be unsynced.",
trans))
return false;
}
// If the next check failed, it would imply that an item exists
// on the server, isn't waiting for application locally, but either
// is an unsynced create or a sucessful delete in the local copy.
// Either way, that's a mismatch.
if (!SyncAssert(0 == server_version, FROM_HERE,
"Server version should be zero.",
trans))
return false;
// Items that aren't using the unique client tag should have a zero
// base version only if they have a local ID. Items with unique client
// tags are allowed to use the zero base version for undeletion and
// de-duplication; the unique client tag trumps the server ID.
if (!using_unique_client_tag) {
if (!SyncAssert(!id.ServerKnows(), FROM_HERE,
"Should be a client only id.",
trans))
return false;
}
}
} else {
if (!SyncAssert(id.ServerKnows(),
FROM_HERE,
"Should be a server id.",
trans))
return false;
}
++entries_done;
int64 elapsed_ms = check_timer.Elapsed().InMilliseconds();
if (elapsed_ms > max_ms) {
DVLOG(1) << "Cutting Invariant check short after " << elapsed_ms
<< "ms. Processed " << entries_done << "/" << handles.size()
<< " entries";
return true;
}
}
return true;
}
///////////////////////////////////////////////////////////////////////////////
// ScopedKernelLock
ScopedKernelLock::ScopedKernelLock(const Directory* dir)
: scoped_lock_(dir->kernel_->mutex), dir_(const_cast<Directory*>(dir)) {
}
///////////////////////////////////////////////////////////////////////////
// Transactions
void BaseTransaction::Lock() {
TRACE_EVENT2("sync_lock_contention", "AcquireLock",
"src_file", from_here_.file_name(),
"src_func", from_here_.function_name());
dirkernel_->transaction_mutex.Acquire();
}
void BaseTransaction::Unlock() {
dirkernel_->transaction_mutex.Release();
}
void BaseTransaction::OnUnrecoverableError(
const tracked_objects::Location& location,
const std::string& message) {
unrecoverable_error_set_ = true;
unrecoverable_error_location_ = location;
unrecoverable_error_msg_ = message;
// Note: We dont call the Directory's OnUnrecoverableError method right
// away. Instead we wait to unwind the stack and in the destructor of the
// transaction we would call the OnUnrecoverableError method.
directory()->ReportUnrecoverableError();
}
bool BaseTransaction::unrecoverable_error_set() const {
return unrecoverable_error_set_;
}
void BaseTransaction::HandleUnrecoverableErrorIfSet() {
if (unrecoverable_error_set_) {
directory()->OnUnrecoverableError(this,
unrecoverable_error_location_,
unrecoverable_error_msg_);
}
}
BaseTransaction::BaseTransaction(const tracked_objects::Location& from_here,
const char* name,
WriterTag writer,
Directory* directory)
: from_here_(from_here), name_(name), writer_(writer),
directory_(directory), dirkernel_(directory->kernel_),
unrecoverable_error_set_(false) {
// TODO(lipalani): Don't issue a good transaction if the directory has
// unrecoverable error set. And the callers have to check trans.good before
// proceeding.
TRACE_EVENT_BEGIN2("sync", name_,
"src_file", from_here_.file_name(),
"src_func", from_here_.function_name());
}
BaseTransaction::~BaseTransaction() {
TRACE_EVENT_END0("sync", name_);
}
ReadTransaction::ReadTransaction(const tracked_objects::Location& location,
Directory* directory)
: BaseTransaction(location, "ReadTransaction", INVALID, directory) {
Lock();
}
ReadTransaction::~ReadTransaction() {
HandleUnrecoverableErrorIfSet();
Unlock();
}
WriteTransaction::WriteTransaction(const tracked_objects::Location& location,
WriterTag writer, Directory* directory)
: BaseTransaction(location, "WriteTransaction", writer, directory) {
Lock();
}
void WriteTransaction::SaveOriginal(const EntryKernel* entry) {
if (!entry) {
return;
}
// Insert only if it's not already there.
const int64 handle = entry->ref(META_HANDLE);
EntryKernelMutationMap::iterator it = mutations_.lower_bound(handle);
if (it == mutations_.end() || it->first != handle) {
EntryKernelMutation mutation;
mutation.original = *entry;
ignore_result(mutations_.insert(it, std::make_pair(handle, mutation)));
}
}
ImmutableEntryKernelMutationMap WriteTransaction::RecordMutations() {
dirkernel_->transaction_mutex.AssertAcquired();
for (syncable::EntryKernelMutationMap::iterator it = mutations_.begin();
it != mutations_.end();) {
EntryKernel* kernel = directory()->GetEntryByHandle(it->first);
if (!kernel) {
NOTREACHED();
continue;
}
if (kernel->is_dirty()) {
it->second.mutated = *kernel;
++it;
} else {
DCHECK(!it->second.original.is_dirty());
// Not actually mutated, so erase from |mutations_|.
mutations_.erase(it++);
}
}
return ImmutableEntryKernelMutationMap(&mutations_);
}
void WriteTransaction::UnlockAndNotify(
const ImmutableEntryKernelMutationMap& mutations) {
// Work while transaction mutex is held.
ModelTypeSet models_with_changes;
bool has_mutations = !mutations.Get().empty();
if (has_mutations) {
models_with_changes = NotifyTransactionChangingAndEnding(mutations);
}
Unlock();
// Work after mutex is relased.
if (has_mutations) {
NotifyTransactionComplete(models_with_changes);
}
}
ModelTypeSet WriteTransaction::NotifyTransactionChangingAndEnding(
const ImmutableEntryKernelMutationMap& mutations) {
dirkernel_->transaction_mutex.AssertAcquired();
DCHECK(!mutations.Get().empty());
WriteTransactionInfo write_transaction_info(
dirkernel_->next_write_transaction_id, from_here_, writer_, mutations);
++dirkernel_->next_write_transaction_id;
ImmutableWriteTransactionInfo immutable_write_transaction_info(
&write_transaction_info);
DirectoryChangeDelegate* const delegate = dirkernel_->delegate;
if (writer_ == syncable::SYNCAPI) {
delegate->HandleCalculateChangesChangeEventFromSyncApi(
immutable_write_transaction_info, this);
} else {
delegate->HandleCalculateChangesChangeEventFromSyncer(
immutable_write_transaction_info, this);
}
ModelTypeSet models_with_changes =
delegate->HandleTransactionEndingChangeEvent(
immutable_write_transaction_info, this);
dirkernel_->transaction_observer.Call(FROM_HERE,
&TransactionObserver::OnTransactionWrite,
immutable_write_transaction_info, models_with_changes);
return models_with_changes;
}
void WriteTransaction::NotifyTransactionComplete(
ModelTypeSet models_with_changes) {
dirkernel_->delegate->HandleTransactionCompleteChangeEvent(
models_with_changes);
}
WriteTransaction::~WriteTransaction() {
const ImmutableEntryKernelMutationMap& mutations = RecordMutations();
if (!unrecoverable_error_set_) {
if (OFF != kInvariantCheckLevel) {
const bool full_scan = (FULL_DB_VERIFICATION == kInvariantCheckLevel);
if (full_scan)
directory()->CheckTreeInvariants(this, full_scan);
else
directory()->CheckTreeInvariants(this, mutations.Get());
}
}
// |CheckTreeInvariants| could have thrown an unrecoverable error.
if (unrecoverable_error_set_) {
HandleUnrecoverableErrorIfSet();
Unlock();
return;
}
UnlockAndNotify(mutations);
}
///////////////////////////////////////////////////////////////////////////
// Entry
Entry::Entry(BaseTransaction* trans, GetById, const Id& id)
: basetrans_(trans) {
kernel_ = trans->directory()->GetEntryById(id);
}
Entry::Entry(BaseTransaction* trans, GetByClientTag, const string& tag)
: basetrans_(trans) {
kernel_ = trans->directory()->GetEntryByClientTag(tag);
}
Entry::Entry(BaseTransaction* trans, GetByServerTag, const string& tag)
: basetrans_(trans) {
kernel_ = trans->directory()->GetEntryByServerTag(tag);
}
Entry::Entry(BaseTransaction* trans, GetByHandle, int64 metahandle)
: basetrans_(trans) {
kernel_ = trans->directory()->GetEntryByHandle(metahandle);
}
Directory* Entry::dir() const {
return basetrans_->directory();
}
Id Entry::ComputePrevIdFromServerPosition(const Id& parent_id) const {
return dir()->ComputePrevIdFromServerPosition(kernel_, parent_id);
}
DictionaryValue* Entry::ToValue() const {
DictionaryValue* entry_info = new DictionaryValue();
entry_info->SetBoolean("good", good());
if (good()) {
entry_info->Set("kernel", kernel_->ToValue());
entry_info->Set("modelType",
ModelTypeToValue(GetModelType()));
entry_info->SetBoolean("existsOnClientBecauseNameIsNonEmpty",
ExistsOnClientBecauseNameIsNonEmpty());
entry_info->SetBoolean("isRoot", IsRoot());
}
return entry_info;
}
const string& Entry::Get(StringField field) const {
DCHECK(kernel_);
return kernel_->ref(field);
}
syncable::ModelType Entry::GetServerModelType() const {
ModelType specifics_type = kernel_->GetServerModelType();
if (specifics_type != UNSPECIFIED)
return specifics_type;
// Otherwise, we don't have a server type yet. That should only happen
// if the item is an uncommitted locally created item.
// It's possible we'll need to relax these checks in the future; they're
// just here for now as a safety measure.
DCHECK(Get(IS_UNSYNCED));
DCHECK_EQ(Get(SERVER_VERSION), 0);
DCHECK(Get(SERVER_IS_DEL));
// Note: can't enforce !Get(ID).ServerKnows() here because that could
// actually happen if we hit AttemptReuniteLostCommitResponses.
return UNSPECIFIED;
}
syncable::ModelType Entry::GetModelType() const {
ModelType specifics_type = GetModelTypeFromSpecifics(Get(SPECIFICS));
if (specifics_type != UNSPECIFIED)
return specifics_type;
if (IsRoot())
return TOP_LEVEL_FOLDER;
// Loose check for server-created top-level folders that aren't
// bound to a particular model type.
if (!Get(UNIQUE_SERVER_TAG).empty() && Get(IS_DIR))
return TOP_LEVEL_FOLDER;
return UNSPECIFIED;
}
///////////////////////////////////////////////////////////////////////////
// MutableEntry
MutableEntry::MutableEntry(WriteTransaction* trans, Create,
const Id& parent_id, const string& name)
: Entry(trans),
write_transaction_(trans) {
Init(trans, parent_id, name);
}
void MutableEntry::Init(WriteTransaction* trans, const Id& parent_id,
const string& name) {
scoped_ptr<EntryKernel> kernel(new EntryKernel);
kernel_ = NULL;
kernel->put(ID, trans->directory_->NextId());
kernel->put(META_HANDLE, trans->directory_->NextMetahandle());
kernel->mark_dirty(trans->directory_->kernel_->dirty_metahandles);
kernel->put(PARENT_ID, parent_id);
kernel->put(NON_UNIQUE_NAME, name);
const base::Time& now = base::Time::Now();
kernel->put(CTIME, now);
kernel->put(MTIME, now);
// We match the database defaults here
kernel->put(BASE_VERSION, CHANGES_VERSION);
if (!trans->directory()->InsertEntry(trans, kernel.get())) {
return; // We failed inserting, nothing more to do.
}
// Because this entry is new, it was originally deleted.
kernel->put(IS_DEL, true);
trans->SaveOriginal(kernel.get());
kernel->put(IS_DEL, false);
// Now swap the pointers.
kernel_ = kernel.release();
}
MutableEntry::MutableEntry(WriteTransaction* trans, CreateNewUpdateItem,
const Id& id)
: Entry(trans), write_transaction_(trans) {
Entry same_id(trans, GET_BY_ID, id);
kernel_ = NULL;
if (same_id.good()) {
return; // already have an item with this ID.
}
scoped_ptr<EntryKernel> kernel(new EntryKernel());
kernel->put(ID, id);
kernel->put(META_HANDLE, trans->directory_->NextMetahandle());
kernel->mark_dirty(trans->directory_->kernel_->dirty_metahandles);
kernel->put(IS_DEL, true);
// We match the database defaults here
kernel->put(BASE_VERSION, CHANGES_VERSION);
if (!trans->directory()->InsertEntry(trans, kernel.get())) {
return; // Failed inserting.
}
trans->SaveOriginal(kernel.get());
kernel_ = kernel.release();
}
MutableEntry::MutableEntry(WriteTransaction* trans, GetById, const Id& id)
: Entry(trans, GET_BY_ID, id), write_transaction_(trans) {
trans->SaveOriginal(kernel_);
}
MutableEntry::MutableEntry(WriteTransaction* trans, GetByHandle,
int64 metahandle)
: Entry(trans, GET_BY_HANDLE, metahandle), write_transaction_(trans) {
trans->SaveOriginal(kernel_);
}
MutableEntry::MutableEntry(WriteTransaction* trans, GetByClientTag,
const std::string& tag)
: Entry(trans, GET_BY_CLIENT_TAG, tag), write_transaction_(trans) {
trans->SaveOriginal(kernel_);
}
MutableEntry::MutableEntry(WriteTransaction* trans, GetByServerTag,
const string& tag)
: Entry(trans, GET_BY_SERVER_TAG, tag), write_transaction_(trans) {
trans->SaveOriginal(kernel_);
}
bool MutableEntry::PutIsDel(bool is_del) {
DCHECK(kernel_);
if (is_del == kernel_->ref(IS_DEL)) {
return true;
}
if (is_del) {
if (!UnlinkFromOrder()) {
return false;
}
}
{
ScopedKernelLock lock(dir());
// Some indices don't include deleted items and must be updated
// upon a value change.
ScopedIndexUpdater<ParentIdAndHandleIndexer> updater(lock, kernel_,
dir()->kernel_->parent_id_child_index);
kernel_->put(IS_DEL, is_del);
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
if (!is_del)
// Restores position to the 0th index.
if (!PutPredecessor(Id())) {
// TODO(lipalani) : Propagate the error to caller. crbug.com/100444.
NOTREACHED();
}
return true;
}
bool MutableEntry::Put(Int64Field field, const int64& value) {
DCHECK(kernel_);
if (kernel_->ref(field) != value) {
ScopedKernelLock lock(dir());
if (SERVER_POSITION_IN_PARENT == field) {
ScopedIndexUpdater<ParentIdAndHandleIndexer> updater(lock, kernel_,
dir()->kernel_->parent_id_child_index);
kernel_->put(field, value);
} else {
kernel_->put(field, value);
}
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
return true;
}
bool MutableEntry::Put(TimeField field, const base::Time& value) {
DCHECK(kernel_);
if (kernel_->ref(field) != value) {
kernel_->put(field, value);
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
return true;
}
bool MutableEntry::Put(IdField field, const Id& value) {
DCHECK(kernel_);
if (kernel_->ref(field) != value) {
if (ID == field) {
if (!dir()->ReindexId(write_transaction(), kernel_, value))
return false;
} else if (PARENT_ID == field) {
PutParentIdPropertyOnly(value); // Makes sibling order inconsistent.
// Fixes up the sibling order inconsistency.
if (!PutPredecessor(Id())) {
// TODO(lipalani) : Propagate the error to caller. crbug.com/100444.
NOTREACHED();
}
} else {
kernel_->put(field, value);
}
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
return true;
}
void MutableEntry::PutParentIdPropertyOnly(const Id& parent_id) {
dir()->ReindexParentId(write_transaction(), kernel_, parent_id);
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
bool MutableEntry::Put(BaseVersion field, int64 value) {
DCHECK(kernel_);
if (kernel_->ref(field) != value) {
kernel_->put(field, value);
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
return true;
}
bool MutableEntry::Put(StringField field, const string& value) {
return PutImpl(field, value);
}
bool MutableEntry::Put(ProtoField field,
const sync_pb::EntitySpecifics& value) {
DCHECK(kernel_);
// TODO(ncarter): This is unfortunately heavyweight. Can we do
// better?
if (kernel_->ref(field).SerializeAsString() != value.SerializeAsString()) {
const bool update_unapplied_updates_index =
(field == SERVER_SPECIFICS) && kernel_->ref(IS_UNAPPLIED_UPDATE);
if (update_unapplied_updates_index) {
// Remove ourselves from unapplied_update_metahandles with our
// old server type.
const syncable::ModelType old_server_type =
kernel_->GetServerModelType();
const int64 metahandle = kernel_->ref(META_HANDLE);
size_t erase_count =
dir()->kernel_->unapplied_update_metahandles[old_server_type]
.erase(metahandle);
DCHECK_EQ(erase_count, 1u);
}
kernel_->put(field, value);
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
if (update_unapplied_updates_index) {
// Add ourselves back into unapplied_update_metahandles with our
// new server type.
const syncable::ModelType new_server_type =
kernel_->GetServerModelType();
const int64 metahandle = kernel_->ref(META_HANDLE);
dir()->kernel_->unapplied_update_metahandles[new_server_type]
.insert(metahandle);
}
}
return true;
}
bool MutableEntry::Put(BitField field, bool value) {
DCHECK(kernel_);
if (kernel_->ref(field) != value) {
kernel_->put(field, value);
kernel_->mark_dirty(GetDirtyIndexHelper());
}
return true;
}
MetahandleSet* MutableEntry::GetDirtyIndexHelper() {
return dir()->kernel_->dirty_metahandles;
}
bool MutableEntry::PutUniqueClientTag(const string& new_tag) {
// There is no SERVER_UNIQUE_CLIENT_TAG. This field is similar to ID.
string old_tag = kernel_->ref(UNIQUE_CLIENT_TAG);
if (old_tag == new_tag) {
return true;
}
ScopedKernelLock lock(dir());
if (!new_tag.empty()) {
// Make sure your new value is not in there already.
EntryKernel lookup_kernel_ = *kernel_;
lookup_kernel_.put(UNIQUE_CLIENT_TAG, new_tag);
bool new_tag_conflicts =
(dir()->kernel_->client_tag_index->count(&lookup_kernel_) > 0);
if (new_tag_conflicts) {
return false;
}
}
{
ScopedIndexUpdater<ClientTagIndexer> index_updater(lock, kernel_,
dir()->kernel_->client_tag_index);
kernel_->put(UNIQUE_CLIENT_TAG, new_tag);
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
return true;
}
bool MutableEntry::PutImpl(StringField field, const string& value) {
DCHECK(kernel_);
if (field == UNIQUE_CLIENT_TAG) {
return PutUniqueClientTag(value);
}
if (kernel_->ref(field) != value) {
kernel_->put(field, value);
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
return true;
}
bool MutableEntry::Put(IndexedBitField field, bool value) {
DCHECK(kernel_);
if (kernel_->ref(field) != value) {
MetahandleSet* index;
if (IS_UNSYNCED == field) {
index = dir()->kernel_->unsynced_metahandles;
} else {
// Use kernel_->GetServerModelType() instead of
// GetServerModelType() as we may trigger some DCHECKs in the
// latter.
index =
&dir()->kernel_->unapplied_update_metahandles[
kernel_->GetServerModelType()];
}
ScopedKernelLock lock(dir());
if (value) {
if (!SyncAssert(index->insert(kernel_->ref(META_HANDLE)).second,
FROM_HERE,
"Could not insert",
write_transaction())) {
return false;
}
} else {
if (!SyncAssert(1U == index->erase(kernel_->ref(META_HANDLE)),
FROM_HERE,
"Entry Not succesfully erased",
write_transaction())) {
return false;
}
}
kernel_->put(field, value);
kernel_->mark_dirty(dir()->kernel_->dirty_metahandles);
}
return true;
}
bool MutableEntry::UnlinkFromOrder() {
ScopedKernelLock lock(dir());
return dir()->UnlinkEntryFromOrder(kernel_, write_transaction(), &lock);
}
bool Directory::UnlinkEntryFromOrder(EntryKernel* entry,
WriteTransaction* trans,
ScopedKernelLock* lock) {
if (!SyncAssert(!trans || this == trans->directory(),
FROM_HERE,
"Transaction not pointing to the right directory",
trans))
return false;
Id old_previous = entry->ref(PREV_ID);
Id old_next = entry->ref(NEXT_ID);
entry->put(NEXT_ID, entry->ref(ID));
entry->put(PREV_ID, entry->ref(ID));
entry->mark_dirty(kernel_->dirty_metahandles);
if (!old_previous.IsRoot()) {
if (old_previous == old_next) {
// Note previous == next doesn't imply previous == next == Get(ID). We
// could have prev==next=="c-XX" and Get(ID)=="sX..." if an item was added
// and deleted before receiving the server ID in the commit response.
if (!SyncAssert(
(old_next == entry->ref(ID)) || !old_next.ServerKnows(),
FROM_HERE,
"Encounteered inconsistent entry while deleting",
trans)) {
return false;
}
return true; // Done if we were already self-looped (hence unlinked).
}
EntryKernel* previous_entry = GetEntryById(old_previous, lock);
ModelType type = GetModelTypeFromSpecifics(entry->ref(SPECIFICS));
// TODO(tim): Multiple asserts here for bug 101039 investigation.
if (type == AUTOFILL) {
if (!SyncAssert(previous_entry != NULL,
FROM_HERE,
"Could not find previous autofill entry",
trans)) {
return false;
}
} else {
if (!SyncAssert(previous_entry != NULL,
FROM_HERE,
"Could not find previous entry",
trans)) {
return false;
}
}
if (trans)
trans->SaveOriginal(previous_entry);
previous_entry->put(NEXT_ID, old_next);
previous_entry->mark_dirty(kernel_->dirty_metahandles);
}
if (!old_next.IsRoot()) {
EntryKernel* next_entry = GetEntryById(old_next, lock);
if (!SyncAssert(next_entry != NULL,
FROM_HERE,
"Could not find next entry",
trans)) {
return false;
}
if (trans)
trans->SaveOriginal(next_entry);
next_entry->put(PREV_ID, old_previous);
next_entry->mark_dirty(kernel_->dirty_metahandles);
}
return true;
}
bool MutableEntry::PutPredecessor(const Id& predecessor_id) {
if (!UnlinkFromOrder())
return false;
if (Get(IS_DEL)) {
DCHECK(predecessor_id.IsNull());
return true;
}
// TODO(ncarter): It should be possible to not maintain position for
// non-bookmark items. However, we'd need to robustly handle all possible
// permutations of setting IS_DEL and the SPECIFICS to identify the
// object type; or else, we'd need to add a ModelType to the
// MutableEntry's Create ctor.
// if (!ShouldMaintainPosition()) {
// return false;
// }
// This is classic insert-into-doubly-linked-list from CS 101 and your last
// job interview. An "IsRoot" Id signifies the head or tail.
Id successor_id;
if (!predecessor_id.IsRoot()) {
MutableEntry predecessor(write_transaction(), GET_BY_ID, predecessor_id);
if (!predecessor.good()) {
LOG(ERROR) << "Predecessor is not good : "
<< predecessor_id.GetServerId();
return false;
}
if (predecessor.Get(PARENT_ID) != Get(PARENT_ID))
return false;
successor_id = predecessor.Get(NEXT_ID);
predecessor.Put(NEXT_ID, Get(ID));
} else {
syncable::Directory* dir = trans()->directory();
if (!dir->GetFirstChildId(trans(), Get(PARENT_ID), &successor_id)) {
return false;
}
}
if (!successor_id.IsRoot()) {
MutableEntry successor(write_transaction(), GET_BY_ID, successor_id);
if (!successor.good()) {
LOG(ERROR) << "Successor is not good: "
<< successor_id.GetServerId();
return false;
}
if (successor.Get(PARENT_ID) != Get(PARENT_ID))
return false;
successor.Put(PREV_ID, Get(ID));
}
DCHECK(predecessor_id != Get(ID));
DCHECK(successor_id != Get(ID));
Put(PREV_ID, predecessor_id);
Put(NEXT_ID, successor_id);
return true;
}
bool MutableEntry::Put(BitTemp field, bool value) {
DCHECK(kernel_);
kernel_->put(field, value);
return true;
}
///////////////////////////////////////////////////////////////////////////
// High-level functions
int64 Directory::NextMetahandle() {
ScopedKernelLock lock(this);
int64 metahandle = (kernel_->next_metahandle)++;
return metahandle;
}
// Always returns a client ID that is the string representation of a negative
// number.
Id Directory::NextId() {
int64 result;
{
ScopedKernelLock lock(this);
result = (kernel_->persisted_info.next_id)--;
kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}
DCHECK_LT(result, 0);
return Id::CreateFromClientString(base::Int64ToString(result));
}
bool Directory::HasChildren(BaseTransaction* trans, const Id& id) {
ScopedKernelLock lock(this);
return (GetPossibleFirstChild(lock, id) != NULL);
}
bool Directory::GetFirstChildId(BaseTransaction* trans,
const Id& parent_id,
Id* first_child_id) {
ScopedKernelLock lock(this);
EntryKernel* entry = GetPossibleFirstChild(lock, parent_id);
if (!entry) {
*first_child_id = Id();
return true;
}
// Walk to the front of the list; the server position ordering
// is commonly identical to the linked-list ordering, but pending
// unsynced or unapplied items may diverge.
while (!entry->ref(PREV_ID).IsRoot()) {
entry = GetEntryById(entry->ref(PREV_ID), &lock);
if (!entry) {
*first_child_id = Id();
return false;
}
}
*first_child_id = entry->ref(ID);
return true;
}
bool Directory::GetLastChildIdForTest(
BaseTransaction* trans, const Id& parent_id, Id* last_child_id) {
ScopedKernelLock lock(this);
EntryKernel* entry = GetPossibleLastChildForTest(lock, parent_id);
if (!entry) {
*last_child_id = Id();
return true;
}
// Walk to the back of the list; the server position ordering
// is commonly identical to the linked-list ordering, but pending
// unsynced or unapplied items may diverge.
while (!entry->ref(NEXT_ID).IsRoot()) {
entry = GetEntryById(entry->ref(NEXT_ID), &lock);
if (!entry) {
*last_child_id = Id();
return false;
}
}
*last_child_id = entry->ref(ID);
return true;
}
Id Directory::ComputePrevIdFromServerPosition(
const EntryKernel* entry,
const syncable::Id& parent_id) {
ScopedKernelLock lock(this);
// Find the natural insertion point in the parent_id_child_index, and
// work back from there, filtering out ineligible candidates.
ParentIdChildIndex::iterator sibling = LocateInParentChildIndex(lock,
parent_id, entry->ref(SERVER_POSITION_IN_PARENT), entry->ref(ID));
ParentIdChildIndex::iterator first_sibling =
GetParentChildIndexLowerBound(lock, parent_id);
while (sibling != first_sibling) {
--sibling;
EntryKernel* candidate = *sibling;
// The item itself should never be in the range under consideration.
DCHECK_NE(candidate->ref(META_HANDLE), entry->ref(META_HANDLE));
// Ignore unapplied updates -- they might not even be server-siblings.
if (candidate->ref(IS_UNAPPLIED_UPDATE))
continue;
// We can't trust the SERVER_ fields of unsynced items, but they are
// potentially legitimate local predecessors. In the case where
// |update_item| and an unsynced item wind up in the same insertion
// position, we need to choose how to order them. The following check puts
// the unapplied update first; removing it would put the unsynced item(s)
// first.
if (candidate->ref(IS_UNSYNCED))
continue;
// Skip over self-looped items, which are not valid predecessors. This
// shouldn't happen in practice, but is worth defending against.
if (candidate->ref(PREV_ID) == candidate->ref(NEXT_ID) &&
!candidate->ref(PREV_ID).IsRoot()) {
NOTREACHED();
continue;
}
return candidate->ref(ID);
}
// This item will be the first in the sibling order.
return Id();
}
bool IsLegalNewParent(BaseTransaction* trans, const Id& entry_id,
const Id& new_parent_id) {
if (entry_id.IsRoot())
return false;
// we have to ensure that the entry is not an ancestor of the new parent.
Id ancestor_id = new_parent_id;
while (!ancestor_id.IsRoot()) {
if (entry_id == ancestor_id)
return false;
Entry new_parent(trans, GET_BY_ID, ancestor_id);
if (!SyncAssert(new_parent.good(),
FROM_HERE,
"Invalid new parent",
trans))
return false;
ancestor_id = new_parent.Get(PARENT_ID);
}
return true;
}
// This function sets only the flags needed to get this entry to sync.
bool MarkForSyncing(syncable::MutableEntry* e) {
DCHECK_NE(static_cast<MutableEntry*>(NULL), e);
DCHECK(!e->IsRoot()) << "We shouldn't mark a permanent object for syncing.";
if (!(e->Put(IS_UNSYNCED, true)))
return false;
e->Put(SYNCING, false);
return true;
}
std::ostream& operator<<(std::ostream& os, const Entry& entry) {
int i;
EntryKernel* const kernel = entry.kernel_;
for (i = BEGIN_FIELDS; i < INT64_FIELDS_END; ++i) {
os << g_metas_columns[i].name << ": "
<< kernel->ref(static_cast<Int64Field>(i)) << ", ";
}
for ( ; i < TIME_FIELDS_END; ++i) {
os << g_metas_columns[i].name << ": "
<< browser_sync::GetTimeDebugString(
kernel->ref(static_cast<TimeField>(i))) << ", ";
}
for ( ; i < ID_FIELDS_END; ++i) {
os << g_metas_columns[i].name << ": "
<< kernel->ref(static_cast<IdField>(i)) << ", ";
}
os << "Flags: ";
for ( ; i < BIT_FIELDS_END; ++i) {
if (kernel->ref(static_cast<BitField>(i)))
os << g_metas_columns[i].name << ", ";
}
for ( ; i < STRING_FIELDS_END; ++i) {
const string& field = kernel->ref(static_cast<StringField>(i));
os << g_metas_columns[i].name << ": " << field << ", ";
}
for ( ; i < PROTO_FIELDS_END; ++i) {
os << g_metas_columns[i].name << ": "
<< net::EscapePath(
kernel->ref(static_cast<ProtoField>(i)).SerializeAsString())
<< ", ";
}
os << "TempFlags: ";
for ( ; i < BIT_TEMPS_END; ++i) {
if (kernel->ref(static_cast<BitTemp>(i)))
os << "#" << i - BIT_TEMPS_BEGIN << ", ";
}
return os;
}
std::ostream& operator<<(std::ostream& s, const Blob& blob) {
for (Blob::const_iterator i = blob.begin(); i != blob.end(); ++i)
s << std::hex << std::setw(2)
<< std::setfill('0') << static_cast<unsigned int>(*i);
return s << std::dec;
}
Directory::ParentIdChildIndex::iterator Directory::LocateInParentChildIndex(
const ScopedKernelLock& lock,
const Id& parent_id,
int64 position_in_parent,
const Id& item_id_for_tiebreaking) {
kernel_->needle.put(PARENT_ID, parent_id);
kernel_->needle.put(SERVER_POSITION_IN_PARENT, position_in_parent);
kernel_->needle.put(ID, item_id_for_tiebreaking);
return kernel_->parent_id_child_index->lower_bound(&kernel_->needle);
}
Directory::ParentIdChildIndex::iterator
Directory::GetParentChildIndexLowerBound(const ScopedKernelLock& lock,
const Id& parent_id) {
// Peg the parent ID, and use the least values for the remaining
// index variables.
return LocateInParentChildIndex(lock, parent_id,
std::numeric_limits<int64>::min(),
Id::GetLeastIdForLexicographicComparison());
}
Directory::ParentIdChildIndex::iterator
Directory::GetParentChildIndexUpperBound(const ScopedKernelLock& lock,
const Id& parent_id) {
// The upper bound of |parent_id|'s range is the lower
// bound of |++parent_id|'s range.
return GetParentChildIndexLowerBound(lock,
parent_id.GetLexicographicSuccessor());
}
void Directory::AppendChildHandles(const ScopedKernelLock& lock,
const Id& parent_id,
Directory::ChildHandles* result) {
typedef ParentIdChildIndex::iterator iterator;
CHECK(result);
for (iterator i = GetParentChildIndexLowerBound(lock, parent_id),
end = GetParentChildIndexUpperBound(lock, parent_id);
i != end; ++i) {
DCHECK_EQ(parent_id, (*i)->ref(PARENT_ID));
result->push_back((*i)->ref(META_HANDLE));
}
}
EntryKernel* Directory::GetPossibleFirstChild(
const ScopedKernelLock& lock, const Id& parent_id) {
// We can use the server positional ordering as a hint because it's generally
// in sync with the local (linked-list) positional ordering, and we have an
// index on it.
ParentIdChildIndex::iterator candidate =
GetParentChildIndexLowerBound(lock, parent_id);
ParentIdChildIndex::iterator end_range =
GetParentChildIndexUpperBound(lock, parent_id);
for (; candidate != end_range; ++candidate) {
EntryKernel* entry = *candidate;
// Filter out self-looped items, which are temporarily not in the child
// ordering.
if (entry->ref(PREV_ID).IsRoot() ||
entry->ref(PREV_ID) != entry->ref(NEXT_ID)) {
return entry;
}
}
// There were no children in the linked list.
return NULL;
}
EntryKernel* Directory::GetPossibleLastChildForTest(
const ScopedKernelLock& lock, const Id& parent_id) {
// We can use the server positional ordering as a hint because it's generally
// in sync with the local (linked-list) positional ordering, and we have an
// index on it.
ParentIdChildIndex::iterator begin_range =
GetParentChildIndexLowerBound(lock, parent_id);
ParentIdChildIndex::iterator candidate =
GetParentChildIndexUpperBound(lock, parent_id);
while (begin_range != candidate) {
--candidate;
EntryKernel* entry = *candidate;
// Filter out self-looped items, which are temporarily not in the child
// ordering.
if (entry->ref(NEXT_ID).IsRoot() ||
entry->ref(NEXT_ID) != entry->ref(PREV_ID)) {
return entry;
}
}
// There were no children in the linked list.
return NULL;
}
} // namespace syncable