Home | History | Annotate | Download | only in drive_backend 
      1 // Copyright 2013 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "chrome/browser/sync_file_system/drive_backend/metadata_database.h"
      6 
      7 #include <stack>
      8 
      9 #include "base/bind.h"
     10 #include "base/callback.h"
     11 #include "base/files/file_path.h"
     12 #include "base/location.h"
     13 #include "base/memory/scoped_vector.h"
     14 #include "base/message_loop/message_loop_proxy.h"
     15 #include "base/sequenced_task_runner.h"
     16 #include "base/stl_util.h"
     17 #include "base/strings/string_number_conversions.h"
     18 #include "base/strings/string_util.h"
     19 #include "base/strings/stringprintf.h"
     20 #include "base/task_runner_util.h"
     21 #include "base/threading/thread_restrictions.h"
     22 #include "chrome/browser/google_apis/drive_api_parser.h"
     23 #include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
     24 #include "chrome/browser/sync_file_system/drive_backend/metadata_db_migration_util.h"
     25 #include "chrome/browser/sync_file_system/logger.h"
     26 #include "chrome/browser/sync_file_system/syncable_file_system_util.h"
     27 #include "third_party/leveldatabase/src/include/leveldb/db.h"
     28 #include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
     29 #include "webkit/common/fileapi/file_system_util.h"
     30 
     31 namespace sync_file_system {
     32 namespace drive_backend {
     33 
     34 const char kDatabaseVersionKey[] = "VERSION";
     35 const int64 kCurrentDatabaseVersion = 3;
     36 const char kServiceMetadataKey[] = "SERVICE";
     37 const char kFileMetadataKeyPrefix[] = "FILE: ";
     38 const char kFileTrackerKeyPrefix[] = "TRACKER: ";
     39 
     40 struct DatabaseContents {
     41   scoped_ptr<ServiceMetadata> service_metadata;
     42   ScopedVector<FileMetadata> file_metadata;
     43   ScopedVector<FileTracker> file_trackers;
     44 };
     45 
     46 namespace {
     47 
     48 typedef MetadataDatabase::FileByID FileByID;
     49 typedef MetadataDatabase::TrackerByID TrackerByID;
     50 typedef MetadataDatabase::TrackersByParentAndTitle TrackersByParentAndTitle;
     51 typedef MetadataDatabase::TrackersByTitle TrackersByTitle;
     52 
     53 std::string RemovePrefix(const std::string& str, const std::string& prefix) {
     54   if (StartsWithASCII(str, prefix, true))
     55     return str.substr(prefix.size());
     56   return str;
     57 }
     58 
     59 base::FilePath ReverseConcatPathComponents(
     60     const std::vector<base::FilePath>& components) {
     61   if (components.empty())
     62     return base::FilePath(FILE_PATH_LITERAL("/")).NormalizePathSeparators();
     63 
     64   size_t total_size = 0;
     65   typedef std::vector<base::FilePath> PathComponents;
     66   for (PathComponents::const_iterator itr = components.begin();
     67        itr != components.end(); ++itr)
     68     total_size += itr->value().size() + 1;
     69 
     70   base::FilePath::StringType result;
     71   result.reserve(total_size);
     72   for (PathComponents::const_reverse_iterator itr = components.rbegin();
     73        itr != components.rend(); ++itr) {
     74     result.append(1, base::FilePath::kSeparators[0]);
     75     result.append(itr->value());
     76   }
     77 
     78   return base::FilePath(result).NormalizePathSeparators();
     79 }
     80 
     81 scoped_ptr<FileMetadata> CreateFileMetadataFromChangeResource(
     82     const google_apis::ChangeResource& change) {
     83   scoped_ptr<FileMetadata> file(new FileMetadata);
     84   file->set_file_id(change.file_id());
     85 
     86   FileDetails* details = file->mutable_details();
     87   details->set_change_id(change.change_id());
     88 
     89   if (change.is_deleted()) {
     90     details->set_deleted(true);
     91     return file.Pass();
     92   }
     93 
     94   const google_apis::FileResource& file_resource = *change.file();
     95   for (ScopedVector<google_apis::ParentReference>::const_iterator itr =
     96            file_resource.parents().begin();
     97        itr != file_resource.parents().end();
     98        ++itr) {
     99     details->add_parent_folder_ids((*itr)->file_id());
    100   }
    101   details->set_title(file_resource.title());
    102 
    103   google_apis::DriveEntryKind kind = file_resource.GetKind();
    104   if (kind == google_apis::ENTRY_KIND_FILE)
    105     details->set_file_kind(FILE_KIND_FILE);
    106   else if (kind == google_apis::ENTRY_KIND_FOLDER)
    107     details->set_file_kind(FILE_KIND_FOLDER);
    108   else
    109     details->set_file_kind(FILE_KIND_UNSUPPORTED);
    110 
    111   details->set_md5(file_resource.md5_checksum());
    112   details->set_etag(file_resource.etag());
    113   details->set_creation_time(file_resource.created_date().ToInternalValue());
    114   details->set_modification_time(
    115       file_resource.modified_date().ToInternalValue());
    116   details->set_deleted(false);
    117 
    118   return file.Pass();
    119 }
    120 
    121 void AdaptLevelDBStatusToSyncStatusCode(const SyncStatusCallback& callback,
    122                                         const leveldb::Status& status) {
    123   callback.Run(LevelDBStatusToSyncStatusCode(status));
    124 }
    125 
    126 void PutServiceMetadataToBatch(const ServiceMetadata& service_metadata,
    127                                leveldb::WriteBatch* batch) {
    128   std::string value;
    129   bool success = service_metadata.SerializeToString(&value);
    130   DCHECK(success);
    131   batch->Put(kServiceMetadataKey, value);
    132 }
    133 
    134 void PutFileToBatch(const FileMetadata& file, leveldb::WriteBatch* batch) {
    135   std::string value;
    136   bool success = file.SerializeToString(&value);
    137   DCHECK(success);
    138   batch->Put(kFileMetadataKeyPrefix + file.file_id(), value);
    139 }
    140 
    141 void PutTrackerToBatch(const FileTracker& tracker, leveldb::WriteBatch* batch) {
    142   std::string value;
    143   bool success = tracker.SerializeToString(&value);
    144   DCHECK(success);
    145   batch->Put(kFileTrackerKeyPrefix + base::Int64ToString(tracker.tracker_id()),
    146              value);
    147 }
    148 
    149 void PutFileDeletionToBatch(const std::string& file_id,
    150                             leveldb::WriteBatch* batch) {
    151   batch->Delete(kFileMetadataKeyPrefix + file_id);
    152 }
    153 
    154 void PutTrackerDeletionToBatch(int64 tracker_id, leveldb::WriteBatch* batch) {
    155   batch->Delete(kFileTrackerKeyPrefix + base::Int64ToString(tracker_id));
    156 }
    157 
    158 void PushChildTrackersToStack(
    159     const TrackersByParentAndTitle& trackers_by_parent,
    160     int64 parent_tracker_id,
    161     std::stack<int64>* stack) {
    162   TrackersByParentAndTitle::const_iterator found =
    163       trackers_by_parent.find(parent_tracker_id);
    164   if (found == trackers_by_parent.end())
    165     return;
    166 
    167   for (TrackersByTitle::const_iterator title_itr = found->second.begin();
    168        title_itr != found->second.end(); ++title_itr) {
    169     const TrackerSet& trackers = title_itr->second;
    170     for (TrackerSet::const_iterator tracker_itr = trackers.begin();
    171          tracker_itr != trackers.end(); ++tracker_itr) {
    172       stack->push((*tracker_itr)->tracker_id());
    173     }
    174   }
    175 }
    176 
    177 std::string GetTrackerTitle(const FileTracker& tracker) {
    178   if (tracker.has_synced_details())
    179     return tracker.synced_details().title();
    180   return std::string();
    181 }
    182 
    183 // Returns true if |db| has no content.
    184 bool IsDatabaseEmpty(leveldb::DB* db) {
    185   DCHECK(db);
    186   scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
    187   itr->SeekToFirst();
    188   return !itr->Valid();
    189 }
    190 
    191 SyncStatusCode OpenDatabase(const base::FilePath& path,
    192                             scoped_ptr<leveldb::DB>* db_out,
    193                             bool* created) {
    194   base::ThreadRestrictions::AssertIOAllowed();
    195   DCHECK(db_out);
    196   DCHECK(created);
    197 
    198   leveldb::Options options;
    199   options.max_open_files = 64;  // Use minimum.
    200   options.create_if_missing = true;
    201   leveldb::DB* db = NULL;
    202   leveldb::Status db_status =
    203       leveldb::DB::Open(options, path.AsUTF8Unsafe(), &db);
    204   SyncStatusCode status = LevelDBStatusToSyncStatusCode(db_status);
    205   if (status != SYNC_STATUS_OK) {
    206     delete db;
    207     return status;
    208   }
    209 
    210   *created = IsDatabaseEmpty(db);
    211   db_out->reset(db);
    212   return status;
    213 }
    214 
    215 SyncStatusCode MigrateDatabaseIfNeeded(leveldb::DB* db) {
    216   base::ThreadRestrictions::AssertIOAllowed();
    217   DCHECK(db);
    218   std::string value;
    219   leveldb::Status status =
    220       db->Get(leveldb::ReadOptions(), kDatabaseVersionKey, &value);
    221   int64 version = 0;
    222   if (status.ok()) {
    223     if (!base::StringToInt64(value, &version))
    224       return SYNC_DATABASE_ERROR_FAILED;
    225   } else {
    226     if (!status.IsNotFound())
    227       return SYNC_DATABASE_ERROR_FAILED;
    228   }
    229 
    230   switch (version) {
    231     case 0:
    232       drive_backend::MigrateDatabaseFromV0ToV1(db);
    233       // fall-through
    234     case 1:
    235       drive_backend::MigrateDatabaseFromV1ToV2(db);
    236       // fall-through
    237     case 2:
    238       // TODO(tzik): Migrate database from version 2 to 3.
    239       //   * Add sync-root folder as active, dirty and needs_folder_listing
    240       //     folder.
    241       //   * Add app-root folders for each origins.  Each app-root folder for
    242       //     an enabled origin should be a active, dirty and
    243       //     needs_folder_listing folder.  And Each app-root folder for a
    244       //     disabled origin should be an inactive, dirty and
    245       //     non-needs_folder_listing folder.
    246       //   * Add a file metadata for each file in previous version.
    247       NOTIMPLEMENTED();
    248       return SYNC_DATABASE_ERROR_FAILED;
    249       // fall-through
    250     case 3:
    251       DCHECK_EQ(3, kCurrentDatabaseVersion);
    252       return SYNC_STATUS_OK;
    253     default:
    254       return SYNC_DATABASE_ERROR_FAILED;
    255   }
    256 }
    257 
    258 SyncStatusCode WriteVersionInfo(leveldb::DB* db) {
    259   base::ThreadRestrictions::AssertIOAllowed();
    260   DCHECK(db);
    261   return LevelDBStatusToSyncStatusCode(
    262       db->Put(leveldb::WriteOptions(),
    263               kDatabaseVersionKey,
    264               base::Int64ToString(kCurrentDatabaseVersion)));
    265 }
    266 
    267 SyncStatusCode ReadDatabaseContents(leveldb::DB* db,
    268                                     DatabaseContents* contents) {
    269   base::ThreadRestrictions::AssertIOAllowed();
    270   DCHECK(db);
    271   DCHECK(contents);
    272 
    273   scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
    274   for (itr->SeekToFirst(); itr->Valid(); itr->Next()) {
    275     std::string key = itr->key().ToString();
    276     std::string value = itr->value().ToString();
    277     if (key == kServiceMetadataKey) {
    278       scoped_ptr<ServiceMetadata> service_metadata(new ServiceMetadata);
    279       if (!service_metadata->ParseFromString(value)) {
    280         util::Log(logging::LOG_WARNING, FROM_HERE,
    281                   "Failed to parse SyncServiceMetadata");
    282         continue;
    283       }
    284 
    285       contents->service_metadata = service_metadata.Pass();
    286       continue;
    287     }
    288 
    289     if (StartsWithASCII(key, kFileMetadataKeyPrefix, true)) {
    290       std::string file_id = RemovePrefix(key, kFileMetadataKeyPrefix);
    291 
    292       scoped_ptr<FileMetadata> file(new FileMetadata);
    293       if (!file->ParseFromString(itr->value().ToString())) {
    294         util::Log(logging::LOG_WARNING, FROM_HERE,
    295                   "Failed to parse a FileMetadata");
    296         continue;
    297       }
    298 
    299       contents->file_metadata.push_back(file.release());
    300       continue;
    301     }
    302 
    303     if (StartsWithASCII(key, kFileTrackerKeyPrefix, true)) {
    304       int64 tracker_id = 0;
    305       if (!base::StringToInt64(RemovePrefix(key, kFileTrackerKeyPrefix),
    306                                &tracker_id)) {
    307         util::Log(logging::LOG_WARNING, FROM_HERE,
    308                   "Failed to parse TrackerID");
    309         continue;
    310       }
    311 
    312       scoped_ptr<FileTracker> tracker(new FileTracker);
    313       if (!tracker->ParseFromString(itr->value().ToString())) {
    314         util::Log(logging::LOG_WARNING, FROM_HERE,
    315                   "Failed to parse a Tracker");
    316         continue;
    317       }
    318       contents->file_trackers.push_back(tracker.release());
    319       continue;
    320     }
    321   }
    322 
    323   return SYNC_STATUS_OK;
    324 }
    325 
    326 SyncStatusCode InitializeServiceMetadata(DatabaseContents* contents,
    327                                          leveldb::WriteBatch* batch) {
    328 
    329   if (!contents->service_metadata) {
    330     contents->service_metadata.reset(new ServiceMetadata);
    331     contents->service_metadata->set_next_tracker_id(1);
    332 
    333     std::string value;
    334     contents->service_metadata->SerializeToString(&value);
    335     batch->Put(kServiceMetadataKey, value);
    336   }
    337   return SYNC_STATUS_OK;
    338 }
    339 
    340 SyncStatusCode RemoveUnreachableItems(DatabaseContents* contents,
    341                                       leveldb::WriteBatch* batch) {
    342   TrackerByID unvisited_trackers;
    343   typedef std::map<int64, std::set<FileTracker*> > TrackersByParent;
    344   TrackersByParent trackers_by_parent;
    345 
    346   for (ScopedVector<FileTracker>::iterator itr =
    347            contents->file_trackers.begin();
    348        itr != contents->file_trackers.end();
    349        ++itr) {
    350     FileTracker* tracker = *itr;
    351     DCHECK(!ContainsKey(unvisited_trackers, tracker->tracker_id()));
    352     unvisited_trackers[tracker->tracker_id()] = tracker;
    353     if (tracker->parent_tracker_id())
    354       trackers_by_parent[tracker->parent_tracker_id()].insert(tracker);
    355   }
    356 
    357   // Traverse synced tracker tree. Take only active items, app-root and their
    358   // children. Drop unreachable items.
    359   ScopedVector<FileTracker> reachable_trackers;
    360   std::stack<int64> pending;
    361   if (contents->service_metadata->sync_root_tracker_id())
    362     pending.push(contents->service_metadata->sync_root_tracker_id());
    363 
    364   while (!pending.empty()) {
    365     int64 tracker_id = pending.top();
    366     pending.pop();
    367 
    368     {
    369       TrackerByID::iterator found = unvisited_trackers.find(tracker_id);
    370       if (found == unvisited_trackers.end())
    371         continue;
    372 
    373       FileTracker* tracker = found->second;
    374       unvisited_trackers.erase(found);
    375       reachable_trackers.push_back(tracker);
    376 
    377       if (!tracker->active() && !tracker->is_app_root())
    378         continue;
    379     }
    380 
    381     TrackersByParent::iterator found = trackers_by_parent.find(tracker_id);
    382     if (found == trackers_by_parent.end())
    383       continue;
    384 
    385     for (std::set<FileTracker*>::const_iterator itr =
    386              found->second.begin();
    387          itr != found->second.end();
    388          ++itr)
    389       pending.push((*itr)->tracker_id());
    390   }
    391 
    392   // Delete all unreachable trackers.
    393   for (TrackerByID::iterator itr = unvisited_trackers.begin();
    394        itr != unvisited_trackers.end(); ++itr) {
    395     FileTracker* tracker = itr->second;
    396     PutTrackerDeletionToBatch(tracker->tracker_id(), batch);
    397     delete tracker;
    398   }
    399   unvisited_trackers.clear();
    400 
    401   // |reachable_trackers| contains all files/folders reachable from sync-root
    402   // folder via active folders and app-root folders.
    403   // Update the tracker set in database contents with the reachable tracker set.
    404   contents->file_trackers.weak_clear();
    405   contents->file_trackers.swap(reachable_trackers);
    406 
    407   // Do the similar traverse for FileMetadata and remove FileMetadata that don't
    408   // have reachable trackers.
    409   FileByID unreferred_files;
    410   for (ScopedVector<FileMetadata>::const_iterator itr =
    411            contents->file_metadata.begin();
    412        itr != contents->file_metadata.end();
    413        ++itr) {
    414     unreferred_files.insert(std::make_pair((*itr)->file_id(), *itr));
    415   }
    416 
    417   ScopedVector<FileMetadata> referred_files;
    418   for (ScopedVector<FileTracker>::const_iterator itr =
    419            contents->file_trackers.begin();
    420        itr != contents->file_trackers.end();
    421        ++itr) {
    422     FileByID::iterator found = unreferred_files.find((*itr)->file_id());
    423     if (found != unreferred_files.end()) {
    424       referred_files.push_back(found->second);
    425       unreferred_files.erase(found);
    426     }
    427   }
    428 
    429   for (FileByID::iterator itr = unreferred_files.begin();
    430        itr != unreferred_files.end(); ++itr) {
    431     FileMetadata* file = itr->second;
    432     PutFileDeletionToBatch(file->file_id(), batch);
    433     delete file;
    434   }
    435   unreferred_files.clear();
    436 
    437   contents->file_metadata.weak_clear();
    438   contents->file_metadata.swap(referred_files);
    439 
    440   return SYNC_STATUS_OK;
    441 }
    442 
    443 template <typename Container, typename Key, typename Value>
    444 bool FindItem(const Container& container, const Key& key, Value* value) {
    445   typename Container::const_iterator found = container.find(key);
    446   if (found == container.end())
    447     return false;
    448   if (value)
    449     *value = *found->second;
    450   return true;
    451 }
    452 
    453 template <typename Container, typename Key>
    454 typename Container::mapped_type FindAndEraseItem(Container* container,
    455                                                  const Key& key) {
    456   typedef typename Container::mapped_type Value;
    457   typename Container::iterator found = container->find(key);
    458   if (found == container->end())
    459     return Value();
    460 
    461   Value result = found->second;
    462   container->erase(found);
    463   return result;
    464 }
    465 
    466 void RunSoon(const tracked_objects::Location& from_here,
    467              const base::Closure& closure) {
    468   base::MessageLoopProxy::current()->PostTask(from_here, closure);
    469 }
    470 
    471 }  // namespace
    472 
    473 bool MetadataDatabase::DirtyTrackerComparator::operator()(
    474     const FileTracker* left,
    475     const FileTracker* right) const {
    476   return left->tracker_id() < right->tracker_id();
    477 }
    478 
    479 // static
    480 void MetadataDatabase::Create(base::SequencedTaskRunner* task_runner,
    481                               const base::FilePath& database_path,
    482                               const CreateCallback& callback) {
    483   task_runner->PostTask(FROM_HERE, base::Bind(
    484       &CreateOnTaskRunner,
    485       base::MessageLoopProxy::current(),
    486       make_scoped_refptr(task_runner),
    487       database_path, callback));
    488 }
    489 
    490 MetadataDatabase::~MetadataDatabase() {
    491   task_runner_->DeleteSoon(FROM_HERE, db_.release());
    492   STLDeleteContainerPairSecondPointers(
    493       file_by_id_.begin(), file_by_id_.end());
    494   STLDeleteContainerPairSecondPointers(
    495       tracker_by_id_.begin(), tracker_by_id_.end());
    496 }
    497 
    498 int64 MetadataDatabase::GetLargestChangeID() const {
    499   return service_metadata_->largest_change_id();
    500 }
    501 
    502 void MetadataDatabase::RegisterApp(const std::string& app_id,
    503                                    const std::string& folder_id,
    504                                    const SyncStatusCallback& callback) {
    505   if (FindAppRootTracker(app_id, NULL)) {
    506     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
    507     return;
    508   }
    509 
    510   TrackerSet trackers;
    511   if (!FindTrackersByFileID(folder_id, &trackers) ||
    512       trackers.has_active() ||
    513       trackers.tracker_set().size() != 1) {
    514     util::Log(logging::LOG_WARNING, FROM_HERE,
    515               "Failed to register App for %s", app_id.c_str());
    516     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_HAS_CONFLICT));
    517     return;
    518   }
    519 
    520   FileTracker* tracker = *trackers.tracker_set().begin();
    521 
    522   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
    523   RegisterTrackerAsAppRoot(app_id, tracker->tracker_id(), batch.get());
    524   WriteToDatabase(batch.Pass(), callback);
    525 }
    526 
    527 void MetadataDatabase::DisableApp(const std::string& app_id,
    528                                   const SyncStatusCallback& callback) {
    529   FileTracker tracker;
    530   if (!FindAppRootTracker(app_id, &tracker)) {
    531     RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
    532     return;
    533   }
    534 
    535   if (!tracker.active()) {
    536     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
    537     return;
    538   }
    539 
    540   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
    541   MakeTrackerInactive(tracker.tracker_id(), batch.get());
    542   WriteToDatabase(batch.Pass(), callback);
    543 }
    544 
    545 void MetadataDatabase::EnableApp(const std::string& app_id,
    546                                  const SyncStatusCallback& callback) {
    547   FileTracker tracker;
    548   if (!FindAppRootTracker(app_id, &tracker)) {
    549     RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
    550     return;
    551   }
    552 
    553   if (tracker.active()) {
    554     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
    555     return;
    556   }
    557 
    558   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
    559   MakeTrackerActive(tracker.tracker_id(), batch.get());
    560   WriteToDatabase(batch.Pass(), callback);
    561 }
    562 
    563 void MetadataDatabase::UnregisterApp(const std::string& app_id,
    564                                      const SyncStatusCallback& callback) {
    565   FileTracker tracker;
    566   if (!FindAppRootTracker(app_id, &tracker)) {
    567     RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
    568     return;
    569   }
    570 
    571   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
    572   UnregisterTrackerAsAppRoot(app_id, batch.get());
    573   WriteToDatabase(batch.Pass(), callback);
    574 }
    575 
    576 bool MetadataDatabase::FindAppRootTracker(const std::string& app_id,
    577                                           FileTracker* tracker) const {
    578   return FindItem(app_root_by_app_id_, app_id, tracker);
    579 }
    580 
    581 bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
    582                                         FileMetadata* file) const {
    583   return FindItem(file_by_id_, file_id, file);
    584 }
    585 
    586 bool MetadataDatabase::FindTrackersByFileID(const std::string& file_id,
    587                                             TrackerSet* trackers) const {
    588   TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
    589   if (found == trackers_by_file_id_.end())
    590     return false;
    591   if (trackers)
    592     *trackers = found->second;
    593   return true;
    594 }
    595 
    596 bool MetadataDatabase::FindTrackerByTrackerID(int64 tracker_id,
    597                                               FileTracker* tracker) const {
    598   return FindItem(tracker_by_id_, tracker_id, tracker);
    599 }
    600 
    601 bool MetadataDatabase::BuildPathForTracker(int64 tracker_id,
    602                                            base::FilePath* path) const {
    603   FileTracker current;
    604   if (!FindTrackerByTrackerID(tracker_id, &current) || !current.active())
    605     return false;
    606 
    607   std::vector<base::FilePath> components;
    608   while (!current.is_app_root()) {
    609     std::string title = GetTrackerTitle(current);
    610     if (title.empty())
    611       return false;
    612     components.push_back(base::FilePath::FromUTF8Unsafe(title));
    613     if (!FindTrackerByTrackerID(current.parent_tracker_id(), &current) ||
    614         !current.active())
    615       return false;
    616   }
    617 
    618   if (path)
    619     *path = ReverseConcatPathComponents(components);
    620 
    621   return true;
    622 }
    623 
    624 void MetadataDatabase::UpdateByChangeList(
    625     ScopedVector<google_apis::ChangeResource> changes,
    626     const SyncStatusCallback& callback) {
    627   scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
    628 
    629   for (ScopedVector<google_apis::ChangeResource>::const_iterator itr =
    630            changes.begin();
    631        itr != changes.end();
    632        ++itr) {
    633     const google_apis::ChangeResource& change = **itr;
    634     scoped_ptr<FileMetadata> file(
    635         CreateFileMetadataFromChangeResource(change));
    636     std::string file_id = file->file_id();
    637 
    638     MarkTrackersDirtyByFileID(file_id, batch.get());
    639     if (!file->details().deleted())
    640       MaybeAddTrackersForNewFile(*file, batch.get());
    641 
    642     if (FindTrackersByFileID(file_id, NULL)) {
    643       PutFileToBatch(*file, batch.get());
    644 
    645       FileMetadata* file_ptr = file.release();
    646       std::swap(file_ptr, file_by_id_[file_id]);
    647       delete file_ptr;
    648     }
    649   }
    650 
    651   WriteToDatabase(batch.Pass(), callback);
    652 }
    653 
    654 MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner)
    655     : task_runner_(task_runner), weak_ptr_factory_(this) {
    656   DCHECK(task_runner);
    657 }
    658 
    659 // static
    660 void MetadataDatabase::CreateOnTaskRunner(
    661     base::SingleThreadTaskRunner* callback_runner,
    662     base::SequencedTaskRunner* task_runner,
    663     const base::FilePath& database_path,
    664     const CreateCallback& callback) {
    665   scoped_ptr<MetadataDatabase> metadata_database(
    666       new MetadataDatabase(task_runner));
    667   SyncStatusCode status =
    668       metadata_database->InitializeOnTaskRunner(database_path);
    669   if (status != SYNC_STATUS_OK)
    670     metadata_database.reset();
    671 
    672   callback_runner->PostTask(FROM_HERE, base::Bind(
    673       callback, status, base::Passed(&metadata_database)));
    674 }
    675 
    676 // static
    677 SyncStatusCode MetadataDatabase::CreateForTesting(
    678     scoped_ptr<leveldb::DB> db,
    679     scoped_ptr<MetadataDatabase>* metadata_database_out) {
    680   scoped_ptr<MetadataDatabase> metadata_database(
    681       new MetadataDatabase(base::MessageLoopProxy::current()));
    682   metadata_database->db_ = db.Pass();
    683   SyncStatusCode status =
    684       metadata_database->InitializeOnTaskRunner(base::FilePath());
    685   if (status == SYNC_STATUS_OK)
    686     *metadata_database_out = metadata_database.Pass();
    687   return status;
    688 }
    689 
    690 SyncStatusCode MetadataDatabase::InitializeOnTaskRunner(
    691     const base::FilePath& database_path) {
    692   base::ThreadRestrictions::AssertIOAllowed();
    693   DCHECK(task_runner_->RunsTasksOnCurrentThread());
    694 
    695   SyncStatusCode status = SYNC_STATUS_UNKNOWN;
    696   bool created = false;
    697   // Open database unless |db_| is overridden for testing.
    698   if (!db_) {
    699     status = OpenDatabase(database_path, &db_, &created);
    700     if (status != SYNC_STATUS_OK)
    701       return status;
    702   }
    703 
    704   if (created) {
    705     status = WriteVersionInfo(db_.get());
    706     if (status != SYNC_STATUS_OK)
    707       return status;
    708   } else {
    709     status = MigrateDatabaseIfNeeded(db_.get());
    710     if (status != SYNC_STATUS_OK)
    711       return status;
    712   }
    713 
    714   DatabaseContents contents;
    715   status = ReadDatabaseContents(db_.get(), &contents);
    716   if (status != SYNC_STATUS_OK)
    717     return status;
    718 
    719   leveldb::WriteBatch batch;
    720   status = InitializeServiceMetadata(&contents, &batch);
    721   if (status != SYNC_STATUS_OK)
    722     return status;
    723 
    724   status = RemoveUnreachableItems(&contents, &batch);
    725   if (status != SYNC_STATUS_OK)
    726     return status;
    727 
    728   status = LevelDBStatusToSyncStatusCode(
    729       db_->Write(leveldb::WriteOptions(), &batch));
    730   if (status != SYNC_STATUS_OK)
    731     return status;
    732 
    733   BuildIndexes(&contents);
    734   return status;
    735 }
    736 
    737 void MetadataDatabase::BuildIndexes(DatabaseContents* contents) {
    738   service_metadata_ = contents->service_metadata.Pass();
    739 
    740   for (ScopedVector<FileMetadata>::const_iterator itr =
    741            contents->file_metadata.begin();
    742        itr != contents->file_metadata.end();
    743        ++itr) {
    744     file_by_id_[(*itr)->file_id()] = *itr;
    745   }
    746   contents->file_metadata.weak_clear();
    747 
    748   for (ScopedVector<FileTracker>::const_iterator itr =
    749            contents->file_trackers.begin();
    750        itr != contents->file_trackers.end();
    751        ++itr) {
    752     FileTracker* tracker = *itr;
    753     tracker_by_id_[tracker->tracker_id()] = tracker;
    754     trackers_by_file_id_[tracker->file_id()].Insert(tracker);
    755 
    756     if (tracker->is_app_root())
    757       app_root_by_app_id_[tracker->app_id()] = tracker;
    758 
    759     if (tracker->parent_tracker_id()) {
    760       std::string title = GetTrackerTitle(*tracker);
    761       TrackerSet* trackers =
    762           &trackers_by_parent_and_title_[tracker->parent_tracker_id()][title];
    763       trackers->Insert(tracker);
    764     }
    765 
    766     if (tracker->dirty())
    767       dirty_trackers_.insert(tracker);
    768   }
    769   contents->file_trackers.weak_clear();
    770 }
    771 
    772 void MetadataDatabase::RegisterTrackerAsAppRoot(
    773     const std::string& app_id,
    774     int64 tracker_id,
    775     leveldb::WriteBatch* batch) {
    776   FileTracker* tracker = tracker_by_id_[tracker_id];
    777   DCHECK(tracker);
    778   tracker->set_app_id(app_id);
    779   tracker->set_is_app_root(true);
    780   app_root_by_app_id_[app_id] = tracker;
    781 
    782   MakeTrackerActive(tracker->tracker_id(), batch);
    783 }
    784 
    785 void MetadataDatabase::UnregisterTrackerAsAppRoot(
    786     const std::string& app_id,
    787     leveldb::WriteBatch* batch) {
    788   FileTracker* tracker = FindAndEraseItem(&app_root_by_app_id_, app_id);
    789   tracker->set_app_id(std::string());
    790   tracker->set_is_app_root(false);
    791 
    792   // Inactivate the tracker to drop all descendant.
    793   // (Note that we set is_app_root to false before calling this.)
    794   MakeTrackerInactive(tracker->tracker_id(), batch);
    795 }
    796 
    797 void MetadataDatabase::MakeTrackerActive(int64 tracker_id,
    798                                          leveldb::WriteBatch* batch) {
    799   FileTracker* tracker = tracker_by_id_[tracker_id];
    800   int64 parent_tracker_id = tracker->parent_tracker_id();
    801   DCHECK(tracker->has_synced_details());
    802   trackers_by_file_id_[tracker->file_id()].Activate(tracker);
    803   if (parent_tracker_id) {
    804     trackers_by_parent_and_title_[parent_tracker_id][
    805         tracker->synced_details().title()].Activate(tracker);
    806   }
    807   tracker->set_active(true);
    808   tracker->set_needs_folder_listing(
    809       tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
    810   tracker->set_dirty(true);
    811   dirty_trackers_.insert(tracker);
    812 
    813   PutTrackerToBatch(*tracker, batch);
    814 }
    815 
    816 void MetadataDatabase::MakeTrackerInactive(int64 tracker_id,
    817                                            leveldb::WriteBatch* batch) {
    818   FileTracker* tracker = tracker_by_id_[tracker_id];
    819   trackers_by_file_id_[tracker->file_id()].Inactivate(tracker);
    820 
    821   std::string title = GetTrackerTitle(*tracker);
    822   int64 parent_tracker_id = tracker->parent_tracker_id();
    823   if (parent_tracker_id)
    824     trackers_by_parent_and_title_[parent_tracker_id][title].Inactivate(tracker);
    825   tracker->set_active(false);
    826 
    827   // Keep the folder tree under an app-root, since we keep the local files of
    828   // SyncFileSystem.
    829   if (!tracker->is_app_root())
    830     RemoveAllDescendantTrackers(tracker_id, batch);
    831   MarkTrackersDirtyByFileID(tracker->file_id(), batch);
    832   if (parent_tracker_id)
    833     MarkTrackersDirtyByPath(parent_tracker_id, title, batch);
    834   PutTrackerToBatch(*tracker, batch);
    835 }
    836 
    837 void MetadataDatabase::CreateTrackerForParentAndFileID(
    838     const FileTracker& parent_tracker,
    839     const std::string& file_id,
    840     leveldb::WriteBatch* batch) {
    841   int64 tracker_id = GetNextTrackerID(batch);
    842   scoped_ptr<FileTracker> tracker(new FileTracker);
    843   tracker->set_tracker_id(tracker_id);
    844   tracker->set_parent_tracker_id(parent_tracker.tracker_id());
    845   tracker->set_file_id(file_id);
    846   tracker->set_app_id(parent_tracker.app_id());
    847   tracker->set_is_app_root(false);
    848   tracker->set_dirty(true);
    849   tracker->set_active(false);
    850   tracker->set_needs_folder_listing(false);
    851   PutTrackerToBatch(*tracker, batch);
    852 
    853   trackers_by_file_id_[file_id].Insert(tracker.get());
    854   // Note: |trackers_by_parent_and_title_| does not map from
    855   // FileMetadata::details but from FileTracker::synced_details, which is filled
    856   // on tracker updated phase.  Use empty string as the title since
    857   // FileTracker::synced_details is empty here.
    858   trackers_by_parent_and_title_[parent_tracker.tracker_id()][std::string()]
    859       .Insert(tracker.get());
    860   dirty_trackers_.insert(tracker.get());
    861   tracker_by_id_[tracker_id] = tracker.release();
    862 }
    863 
    864 void MetadataDatabase::RemoveTrackerIgnoringSiblings(
    865     int64 tracker_id,
    866     leveldb::WriteBatch* batch) {
    867   FileTracker* tracker = FindAndEraseItem(&tracker_by_id_, tracker_id);
    868   if (!tracker)
    869     return;
    870 
    871   EraseTrackerFromFileIDIndex(tracker, batch);
    872   if (tracker->is_app_root())
    873     app_root_by_app_id_.erase(tracker->app_id());
    874   EraseTrackerFromPathIndex(tracker);
    875 
    876   MarkTrackersDirtyByFileID(tracker->file_id(), batch);
    877   // Do not mark the same path trackers as dirty, since the caller is deleting
    878   // all its siblings.
    879   delete tracker;
    880   PutTrackerDeletionToBatch(tracker_id, batch);
    881 }
    882 
    883 void MetadataDatabase::MaybeAddTrackersForNewFile(
    884     const FileMetadata& file,
    885     leveldb::WriteBatch* batch) {
    886   std::set<int64> known_parents;
    887   TrackersByFileID::iterator found = trackers_by_file_id_.find(file.file_id());
    888   if (found != trackers_by_file_id_.end()) {
    889     for (TrackerSet::const_iterator itr = found->second.begin();
    890          itr != found->second.end(); ++itr) {
    891       int64 parent_tracker_id = (*itr)->parent_tracker_id();
    892       if (parent_tracker_id)
    893         known_parents.insert(parent_tracker_id);
    894     }
    895   }
    896 
    897   for (int i = 0; i < file.details().parent_folder_ids_size(); ++i) {
    898     std::string parent_folder_id = file.details().parent_folder_ids(i);
    899     TrackersByFileID::iterator found =
    900         trackers_by_file_id_.find(parent_folder_id);
    901     if (found == trackers_by_file_id_.end())
    902       continue;
    903 
    904     for (TrackerSet::const_iterator itr = found->second.begin();
    905          itr != found->second.end(); ++itr) {
    906       FileTracker* parent_tracker = *itr;
    907       int64 parent_tracker_id = parent_tracker->tracker_id();
    908       if (!parent_tracker->active() && !parent_tracker->is_app_root())
    909         continue;
    910 
    911       if (ContainsKey(known_parents, parent_tracker_id))
    912         continue;
    913 
    914       CreateTrackerForParentAndFileID(*parent_tracker, file.file_id(), batch);
    915     }
    916   }
    917 }
    918 
    919 void MetadataDatabase::RemoveAllDescendantTrackers(int64 root_tracker_id,
    920                                                    leveldb::WriteBatch* batch) {
    921   std::stack<int64> pending_trackers;
    922   PushChildTrackersToStack(trackers_by_parent_and_title_,
    923                            root_tracker_id, &pending_trackers);
    924 
    925   while (!pending_trackers.empty()) {
    926     int64 tracker_id = pending_trackers.top();
    927     pending_trackers.pop();
    928     PushChildTrackersToStack(trackers_by_parent_and_title_,
    929                              tracker_id, &pending_trackers);
    930     RemoveTrackerIgnoringSiblings(tracker_id, batch);
    931   }
    932 }
    933 
    934 void MetadataDatabase::EraseTrackerFromFileIDIndex(FileTracker* tracker,
    935                                                    leveldb::WriteBatch* batch) {
    936   TrackersByFileID::iterator found =
    937       trackers_by_file_id_.find(tracker->file_id());
    938   if (found == trackers_by_file_id_.end())
    939     return;
    940 
    941   TrackerSet* trackers = &found->second;
    942   trackers->Erase(tracker);
    943   if (!trackers->tracker_set().empty())
    944     return;
    945   trackers_by_file_id_.erase(found);
    946   EraseFileFromDatabase(tracker->file_id(), batch);
    947 }
    948 
    949 void MetadataDatabase::EraseFileFromDatabase(const std::string& file_id,
    950                                              leveldb::WriteBatch* batch) {
    951   FileMetadata* file = FindAndEraseItem(&file_by_id_, file_id);
    952   if (!file)
    953     return;
    954   delete file;
    955   PutFileDeletionToBatch(file_id, batch);
    956 }
    957 
    958 void MetadataDatabase::EraseTrackerFromPathIndex(FileTracker* tracker) {
    959   TrackersByParentAndTitle::iterator found =
    960       trackers_by_parent_and_title_.find(tracker->parent_tracker_id());
    961   if (found == trackers_by_parent_and_title_.end())
    962     return;
    963 
    964   std::string title = GetTrackerTitle(*tracker);
    965   TrackersByTitle* trackers_by_title = &found->second;
    966   TrackersByTitle::iterator found_by_title = trackers_by_title->find(title);
    967   TrackerSet* conflicting_trackers = &found_by_title->second;
    968   conflicting_trackers->Erase(tracker);
    969 
    970   if (conflicting_trackers->tracker_set().empty()) {
    971     trackers_by_title->erase(found_by_title);
    972     if (trackers_by_title->empty())
    973       trackers_by_parent_and_title_.erase(found);
    974   }
    975 }
    976 
    977 void MetadataDatabase::MarkTrackerSetDirty(
    978     TrackerSet* trackers,
    979     leveldb::WriteBatch* batch) {
    980   for (TrackerSet::iterator itr = trackers->begin();
    981        itr != trackers->end(); ++itr) {
    982     FileTracker* tracker = *itr;
    983     if (tracker->dirty())
    984       continue;
    985     tracker->set_dirty(true);
    986     PutTrackerToBatch(*tracker, batch);
    987     dirty_trackers_.insert(tracker);
    988   }
    989 }
    990 
    991 void MetadataDatabase::MarkTrackersDirtyByFileID(
    992     const std::string& file_id,
    993     leveldb::WriteBatch* batch) {
    994   TrackersByFileID::iterator found = trackers_by_file_id_.find(file_id);
    995   if (found != trackers_by_file_id_.end())
    996     MarkTrackerSetDirty(&found->second, batch);
    997 }
    998 
    999 void MetadataDatabase::MarkTrackersDirtyByPath(int64 parent_tracker_id,
   1000                                                const std::string& title,
   1001                                                leveldb::WriteBatch* batch) {
   1002   TrackersByParentAndTitle::iterator found =
   1003       trackers_by_parent_and_title_.find(parent_tracker_id);
   1004   if (found == trackers_by_parent_and_title_.end()) {
   1005     NOTREACHED() << "parent: " << parent_tracker_id
   1006                  << ", title: " << title;
   1007     return;
   1008   }
   1009 
   1010   TrackersByTitle::iterator itr = found->second.find(title);
   1011   if (itr != found->second.end())
   1012     MarkTrackerSetDirty(&itr->second, batch);
   1013 }
   1014 
   1015 int64 MetadataDatabase::GetNextTrackerID(leveldb::WriteBatch* batch) {
   1016   int64 tracker_id = service_metadata_->next_tracker_id();
   1017   service_metadata_->set_next_tracker_id(tracker_id + 1);
   1018   PutServiceMetadataToBatch(*service_metadata_, batch);
   1019   DCHECK_GT(tracker_id, 0);
   1020   return tracker_id;
   1021 }
   1022 
   1023 void MetadataDatabase::WriteToDatabase(scoped_ptr<leveldb::WriteBatch> batch,
   1024                                        const SyncStatusCallback& callback) {
   1025   base::PostTaskAndReplyWithResult(
   1026       task_runner_.get(),
   1027       FROM_HERE,
   1028       base::Bind(&leveldb::DB::Write,
   1029                  base::Unretained(db_.get()),
   1030                  leveldb::WriteOptions(),
   1031                  base::Owned(batch.release())),
   1032       base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
   1033 }
   1034 
   1035 }  // namespace drive_backend
   1036 }  // namespace sync_file_system
   1037