metadata_database.cc revision bb1529ce867d8845a77ec7cdf3e3003ef1771a40 
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
31namespace sync_file_system {
32namespace drive_backend {
33
34const char kDatabaseVersionKey[] = "VERSION";
35const int64 kCurrentDatabaseVersion = 3;
36const char kServiceMetadataKey[] = "SERVICE";
37const char kFileMetadataKeyPrefix[] = "FILE: ";
38const char kFileTrackerKeyPrefix[] = "TRACKER: ";
39
40struct DatabaseContents {
41  scoped_ptr<ServiceMetadata> service_metadata;
42  ScopedVector<FileMetadata> file_metadata;
43  ScopedVector<FileTracker> file_trackers;
44};
45
46namespace {
47
48typedef MetadataDatabase::FileByID FileByID;
49typedef MetadataDatabase::TrackerByID TrackerByID;
50typedef MetadataDatabase::TrackersByParentAndTitle TrackersByParentAndTitle;
51typedef MetadataDatabase::TrackersByTitle TrackersByTitle;
52
53std::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
59base::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
81void AdaptLevelDBStatusToSyncStatusCode(const SyncStatusCallback& callback,
82                                        const leveldb::Status& status) {
83  callback.Run(LevelDBStatusToSyncStatusCode(status));
84}
85
86void PutServiceMetadataToBatch(const ServiceMetadata& service_metadata,
87                               leveldb::WriteBatch* batch) {
88  std::string value;
89  bool success = service_metadata.SerializeToString(&value);
90  DCHECK(success);
91  batch->Put(kServiceMetadataKey, value);
92}
93
94void PutFileToBatch(const FileMetadata& file, leveldb::WriteBatch* batch) {
95  std::string value;
96  bool success = file.SerializeToString(&value);
97  DCHECK(success);
98  batch->Put(kFileMetadataKeyPrefix + file.file_id(), value);
99}
100
101void PutTrackerToBatch(const FileTracker& tracker, leveldb::WriteBatch* batch) {
102  std::string value;
103  bool success = tracker.SerializeToString(&value);
104  DCHECK(success);
105  batch->Put(kFileTrackerKeyPrefix + base::Int64ToString(tracker.tracker_id()),
106             value);
107}
108
109void PutFileDeletionToBatch(const std::string& file_id,
110                            leveldb::WriteBatch* batch) {
111  batch->Delete(kFileMetadataKeyPrefix + file_id);
112}
113
114void PutTrackerDeletionToBatch(int64 tracker_id, leveldb::WriteBatch* batch) {
115  batch->Delete(kFileTrackerKeyPrefix + base::Int64ToString(tracker_id));
116}
117
118std::string GetTrackerTitle(const FileTracker& tracker) {
119  if (tracker.has_synced_details())
120    return tracker.synced_details().title();
121  return std::string();
122}
123
124// Returns true if |db| has no content.
125bool IsDatabaseEmpty(leveldb::DB* db) {
126  DCHECK(db);
127  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
128  itr->SeekToFirst();
129  return !itr->Valid();
130}
131
132SyncStatusCode OpenDatabase(const base::FilePath& path,
133                            scoped_ptr<leveldb::DB>* db_out,
134                            bool* created) {
135  base::ThreadRestrictions::AssertIOAllowed();
136  DCHECK(db_out);
137  DCHECK(created);
138
139  leveldb::Options options;
140  options.max_open_files = 0;  // Use minimum.
141  options.create_if_missing = true;
142  leveldb::DB* db = NULL;
143  leveldb::Status db_status =
144      leveldb::DB::Open(options, path.AsUTF8Unsafe(), &db);
145  SyncStatusCode status = LevelDBStatusToSyncStatusCode(db_status);
146  if (status != SYNC_STATUS_OK) {
147    delete db;
148    return status;
149  }
150
151  *created = IsDatabaseEmpty(db);
152  db_out->reset(db);
153  return status;
154}
155
156SyncStatusCode MigrateDatabaseIfNeeded(leveldb::DB* db) {
157  base::ThreadRestrictions::AssertIOAllowed();
158  DCHECK(db);
159  std::string value;
160  leveldb::Status status =
161      db->Get(leveldb::ReadOptions(), kDatabaseVersionKey, &value);
162  int64 version = 0;
163  if (status.ok()) {
164    if (!base::StringToInt64(value, &version))
165      return SYNC_DATABASE_ERROR_FAILED;
166  } else {
167    if (!status.IsNotFound())
168      return SYNC_DATABASE_ERROR_FAILED;
169  }
170
171  switch (version) {
172    case 0:
173      drive_backend::MigrateDatabaseFromV0ToV1(db);
174      // fall-through
175    case 1:
176      drive_backend::MigrateDatabaseFromV1ToV2(db);
177      // fall-through
178    case 2:
179      // TODO(tzik): Migrate database from version 2 to 3.
180      //   * Add sync-root folder as active, dirty and needs_folder_listing
181      //     folder.
182      //   * Add app-root folders for each origins.  Each app-root folder for
183      //     an enabled origin should be a active, dirty and
184      //     needs_folder_listing folder.  And Each app-root folder for a
185      //     disabled origin should be an inactive, dirty and
186      //     non-needs_folder_listing folder.
187      //   * Add a file metadata for each file in previous version.
188      NOTIMPLEMENTED();
189      return SYNC_DATABASE_ERROR_FAILED;
190      // fall-through
191    case 3:
192      DCHECK_EQ(3, kCurrentDatabaseVersion);
193      return SYNC_STATUS_OK;
194    default:
195      return SYNC_DATABASE_ERROR_FAILED;
196  }
197}
198
199SyncStatusCode WriteVersionInfo(leveldb::DB* db) {
200  base::ThreadRestrictions::AssertIOAllowed();
201  DCHECK(db);
202  return LevelDBStatusToSyncStatusCode(
203      db->Put(leveldb::WriteOptions(),
204              kDatabaseVersionKey,
205              base::Int64ToString(kCurrentDatabaseVersion)));
206}
207
208SyncStatusCode ReadDatabaseContents(leveldb::DB* db,
209                                    DatabaseContents* contents) {
210  base::ThreadRestrictions::AssertIOAllowed();
211  DCHECK(db);
212  DCHECK(contents);
213
214  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
215  for (itr->SeekToFirst(); itr->Valid(); itr->Next()) {
216    std::string key = itr->key().ToString();
217    std::string value = itr->value().ToString();
218    if (key == kServiceMetadataKey) {
219      scoped_ptr<ServiceMetadata> service_metadata(new ServiceMetadata);
220      if (!service_metadata->ParseFromString(value)) {
221        util::Log(logging::LOG_WARNING, FROM_HERE,
222                  "Failed to parse SyncServiceMetadata");
223        continue;
224      }
225
226      contents->service_metadata = service_metadata.Pass();
227      continue;
228    }
229
230    if (StartsWithASCII(key, kFileMetadataKeyPrefix, true)) {
231      std::string file_id = RemovePrefix(key, kFileMetadataKeyPrefix);
232
233      scoped_ptr<FileMetadata> file(new FileMetadata);
234      if (!file->ParseFromString(itr->value().ToString())) {
235        util::Log(logging::LOG_WARNING, FROM_HERE,
236                  "Failed to parse a FileMetadata");
237        continue;
238      }
239
240      contents->file_metadata.push_back(file.release());
241      continue;
242    }
243
244    if (StartsWithASCII(key, kFileTrackerKeyPrefix, true)) {
245      int64 tracker_id = 0;
246      if (!base::StringToInt64(RemovePrefix(key, kFileTrackerKeyPrefix),
247                               &tracker_id)) {
248        util::Log(logging::LOG_WARNING, FROM_HERE,
249                  "Failed to parse TrackerID");
250        continue;
251      }
252
253      scoped_ptr<FileTracker> tracker(new FileTracker);
254      if (!tracker->ParseFromString(itr->value().ToString())) {
255        util::Log(logging::LOG_WARNING, FROM_HERE,
256                  "Failed to parse a Tracker");
257        continue;
258      }
259      contents->file_trackers.push_back(tracker.release());
260      continue;
261    }
262  }
263
264  return SYNC_STATUS_OK;
265}
266
267SyncStatusCode InitializeServiceMetadata(DatabaseContents* contents,
268                                         leveldb::WriteBatch* batch) {
269
270  if (!contents->service_metadata) {
271    contents->service_metadata.reset(new ServiceMetadata);
272    contents->service_metadata->set_next_tracker_id(1);
273
274    std::string value;
275    contents->service_metadata->SerializeToString(&value);
276    batch->Put(kServiceMetadataKey, value);
277  }
278  return SYNC_STATUS_OK;
279}
280
281SyncStatusCode RemoveUnreachableItems(DatabaseContents* contents,
282                                      leveldb::WriteBatch* batch) {
283  TrackerByID unvisited_trackers;
284  typedef std::map<int64, std::set<FileTracker*> > TrackersByParent;
285  TrackersByParent trackers_by_parent;
286
287  for (ScopedVector<FileTracker>::iterator itr =
288           contents->file_trackers.begin();
289       itr != contents->file_trackers.end();
290       ++itr) {
291    FileTracker* tracker = *itr;
292    DCHECK(!ContainsKey(unvisited_trackers, tracker->tracker_id()));
293    unvisited_trackers[tracker->tracker_id()] = tracker;
294    if (tracker->parent_tracker_id())
295      trackers_by_parent[tracker->parent_tracker_id()].insert(tracker);
296  }
297
298  // Traverse synced tracker tree. Take only active items, app-root and their
299  // children. Drop unreachable items.
300  ScopedVector<FileTracker> reachable_trackers;
301  std::stack<int64> pending;
302  if (contents->service_metadata->sync_root_tracker_id())
303    pending.push(contents->service_metadata->sync_root_tracker_id());
304
305  while (!pending.empty()) {
306    int64 tracker_id = pending.top();
307    pending.pop();
308
309    {
310      TrackerByID::iterator found = unvisited_trackers.find(tracker_id);
311      if (found == unvisited_trackers.end())
312        continue;
313
314      FileTracker* tracker = found->second;
315      unvisited_trackers.erase(found);
316      reachable_trackers.push_back(tracker);
317
318      if (!tracker->active() && !tracker->is_app_root())
319        continue;
320    }
321
322    TrackersByParent::iterator found = trackers_by_parent.find(tracker_id);
323    if (found == trackers_by_parent.end())
324      continue;
325
326    for (std::set<FileTracker*>::const_iterator itr =
327             found->second.begin();
328         itr != found->second.end();
329         ++itr)
330      pending.push((*itr)->tracker_id());
331  }
332
333  // Delete all unreachable trackers.
334  for (TrackerByID::iterator itr = unvisited_trackers.begin();
335       itr != unvisited_trackers.end(); ++itr) {
336    FileTracker* tracker = itr->second;
337    PutTrackerDeletionToBatch(tracker->tracker_id(), batch);
338    delete tracker;
339  }
340  unvisited_trackers.clear();
341
342  // |reachable_trackers| contains all files/folders reachable from sync-root
343  // folder via active folders and app-root folders.
344  // Update the tracker set in database contents with the reachable tracker set.
345  contents->file_trackers.weak_clear();
346  contents->file_trackers.swap(reachable_trackers);
347
348  // Do the similar traverse for FileMetadata and remove FileMetadata that don't
349  // have reachable trackers.
350  FileByID unreferred_files;
351  for (ScopedVector<FileMetadata>::const_iterator itr =
352           contents->file_metadata.begin();
353       itr != contents->file_metadata.end();
354       ++itr) {
355    unreferred_files.insert(std::make_pair((*itr)->file_id(), *itr));
356  }
357
358  ScopedVector<FileMetadata> referred_files;
359  for (ScopedVector<FileTracker>::const_iterator itr =
360           contents->file_trackers.begin();
361       itr != contents->file_trackers.end();
362       ++itr) {
363    FileByID::iterator found = unreferred_files.find((*itr)->file_id());
364    if (found != unreferred_files.end()) {
365      referred_files.push_back(found->second);
366      unreferred_files.erase(found);
367    }
368  }
369
370  for (FileByID::iterator itr = unreferred_files.begin();
371       itr != unreferred_files.end(); ++itr) {
372    FileMetadata* file = itr->second;
373    PutFileDeletionToBatch(file->file_id(), batch);
374    delete file;
375  }
376  unreferred_files.clear();
377
378  contents->file_metadata.weak_clear();
379  contents->file_metadata.swap(referred_files);
380
381  return SYNC_STATUS_OK;
382}
383
384template <typename Container, typename Key, typename Value>
385bool FindItem(const Container& container, const Key& key, Value* value) {
386  typename Container::const_iterator found = container.find(key);
387  if (found == container.end())
388    return false;
389  if (value)
390    *value = *found->second;
391  return true;
392}
393
394void RunSoon(const tracked_objects::Location& from_here,
395             const base::Closure& closure) {
396  base::MessageLoopProxy::current()->PostTask(from_here, closure);
397}
398
399}  // namespace
400
401bool MetadataDatabase::DirtyTrackerComparator::operator()(
402    const FileTracker* left,
403    const FileTracker* right) const {
404  return left->tracker_id() < right->tracker_id();
405}
406
407// static
408void MetadataDatabase::Create(base::SequencedTaskRunner* task_runner,
409                              const base::FilePath& database_path,
410                              const CreateCallback& callback) {
411  task_runner->PostTask(FROM_HERE, base::Bind(
412      &CreateOnTaskRunner,
413      base::MessageLoopProxy::current(),
414      make_scoped_refptr(task_runner),
415      database_path, callback));
416}
417
418MetadataDatabase::~MetadataDatabase() {
419  task_runner_->DeleteSoon(FROM_HERE, db_.release());
420  STLDeleteContainerPairSecondPointers(
421      file_by_id_.begin(), file_by_id_.end());
422  STLDeleteContainerPairSecondPointers(
423      tracker_by_id_.begin(), tracker_by_id_.end());
424}
425
426int64 MetadataDatabase::GetLargestChangeID() const {
427  return service_metadata_->largest_change_id();
428}
429
430void MetadataDatabase::RegisterApp(const std::string& app_id,
431                                   const std::string& folder_id,
432                                   const SyncStatusCallback& callback) {
433  NOTIMPLEMENTED();
434}
435
436void MetadataDatabase::DisableApp(const std::string& app_id,
437                                  const SyncStatusCallback& callback) {
438  NOTIMPLEMENTED();
439}
440
441void MetadataDatabase::EnableApp(const std::string& app_id,
442                                 const SyncStatusCallback& callback) {
443  NOTIMPLEMENTED();
444}
445
446void MetadataDatabase::UnregisterApp(const std::string& app_id,
447                                     const SyncStatusCallback& callback) {
448  NOTIMPLEMENTED();
449}
450
451void MetadataDatabase::UpdateByChangeList(
452    ScopedVector<google_apis::ChangeResource> changes,
453    const SyncStatusCallback& callback) {
454  NOTIMPLEMENTED();
455}
456
457MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner)
458    : task_runner_(task_runner), weak_ptr_factory_(this) {
459  DCHECK(task_runner);
460}
461
462// static
463void MetadataDatabase::CreateOnTaskRunner(
464    base::SingleThreadTaskRunner* callback_runner,
465    base::SequencedTaskRunner* task_runner,
466    const base::FilePath& database_path,
467    const CreateCallback& callback) {
468  scoped_ptr<MetadataDatabase> metadata_database(
469      new MetadataDatabase(task_runner));
470  SyncStatusCode status =
471      metadata_database->InitializeOnTaskRunner(database_path);
472  if (status != SYNC_STATUS_OK)
473    metadata_database.reset();
474
475  callback_runner->PostTask(FROM_HERE, base::Bind(
476      callback, status, base::Passed(&metadata_database)));
477}
478
479// static
480SyncStatusCode MetadataDatabase::CreateForTesting(
481    scoped_ptr<leveldb::DB> db,
482    scoped_ptr<MetadataDatabase>* metadata_database_out) {
483  scoped_ptr<MetadataDatabase> metadata_database(
484      new MetadataDatabase(base::MessageLoopProxy::current()));
485  metadata_database->db_ = db.Pass();
486  SyncStatusCode status =
487      metadata_database->InitializeOnTaskRunner(base::FilePath());
488  if (status == SYNC_STATUS_OK)
489    *metadata_database_out = metadata_database.Pass();
490  return status;
491}
492
493SyncStatusCode MetadataDatabase::InitializeOnTaskRunner(
494    const base::FilePath& database_path) {
495  base::ThreadRestrictions::AssertIOAllowed();
496  DCHECK(task_runner_->RunsTasksOnCurrentThread());
497
498  SyncStatusCode status = SYNC_STATUS_UNKNOWN;
499  bool created = false;
500  // Open database unless |db_| is overridden for testing.
501  if (!db_) {
502    status = OpenDatabase(database_path, &db_, &created);
503    if (status != SYNC_STATUS_OK)
504      return status;
505  }
506
507  if (created) {
508    status = WriteVersionInfo(db_.get());
509    if (status != SYNC_STATUS_OK)
510      return status;
511  } else {
512    status = MigrateDatabaseIfNeeded(db_.get());
513    if (status != SYNC_STATUS_OK)
514      return status;
515  }
516
517  DatabaseContents contents;
518  status = ReadDatabaseContents(db_.get(), &contents);
519  if (status != SYNC_STATUS_OK)
520    return status;
521
522  leveldb::WriteBatch batch;
523  status = InitializeServiceMetadata(&contents, &batch);
524  if (status != SYNC_STATUS_OK)
525    return status;
526
527  status = RemoveUnreachableItems(&contents, &batch);
528  if (status != SYNC_STATUS_OK)
529    return status;
530
531  status = LevelDBStatusToSyncStatusCode(
532      db_->Write(leveldb::WriteOptions(), &batch));
533  if (status != SYNC_STATUS_OK)
534    return status;
535
536  BuildIndexes(&contents);
537  return status;
538}
539
540void MetadataDatabase::BuildIndexes(DatabaseContents* contents) {
541  service_metadata_ = contents->service_metadata.Pass();
542
543  for (ScopedVector<FileMetadata>::const_iterator itr =
544           contents->file_metadata.begin();
545       itr != contents->file_metadata.end();
546       ++itr) {
547    file_by_id_[(*itr)->file_id()] = *itr;
548  }
549  contents->file_metadata.weak_clear();
550
551  for (ScopedVector<FileTracker>::const_iterator itr =
552           contents->file_trackers.begin();
553       itr != contents->file_trackers.end();
554       ++itr) {
555    FileTracker* tracker = *itr;
556    tracker_by_id_[tracker->tracker_id()] = tracker;
557    trackers_by_file_id_[tracker->file_id()].Insert(tracker);
558
559    if (tracker->is_app_root())
560      app_root_by_app_id_[tracker->app_id()] = tracker;
561
562    if (tracker->parent_tracker_id()) {
563      std::string title = GetTrackerTitle(*tracker);
564      TrackerSet* trackers =
565          &trackers_by_parent_and_title_[tracker->parent_tracker_id()][title];
566      trackers->Insert(tracker);
567    }
568
569    if (tracker->dirty())
570      dirty_trackers_.insert(tracker);
571  }
572  contents->file_trackers.weak_clear();
573}
574
575void MetadataDatabase::WriteToDatabase(scoped_ptr<leveldb::WriteBatch> batch,
576                                       const SyncStatusCallback& callback) {
577  base::PostTaskAndReplyWithResult(
578      task_runner_.get(),
579      FROM_HERE,
580      base::Bind(&leveldb::DB::Write,
581                 base::Unretained(db_.get()),
582                 leveldb::WriteOptions(),
583                 base::Owned(batch.release())),
584      base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
585}
586
587}  // namespace drive_backend
588}  // namespace sync_file_system
589