metadata_database_index_on_disk.cc revision 116680a4aac90f2aa7413d9095a592090648e557 
1// Copyright 2014 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_index_on_disk.h"
6
7#include "base/format_macros.h"
8#include "base/logging.h"
9#include "base/strings/string_number_conversions.h"
10#include "base/strings/string_util.h"
11#include "chrome/browser/sync_file_system/drive_backend/drive_backend_constants.h"
12#include "chrome/browser/sync_file_system/drive_backend/drive_backend_util.h"
13#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
14#include "chrome/browser/sync_file_system/logger.h"
15#include "third_party/leveldatabase/src/include/leveldb/db.h"
16#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
17
18// LevelDB database schema
19// =======================
20//
21// NOTE
22// - Entries are sorted by keys.
23// - int64 value is serialized as a string by base::Int64ToString().
24// - ServiceMetadata, FileMetadata, and FileTracker values are serialized
25//   as a string by SerializeToString() of protocol buffers.
26//
27// Version 4:
28//   # Version of this schema
29//   key: "VERSION"
30//   value: "4"
31//
32//   # Metadata of the SyncFS service (compatible with version 3)
33//   key: "SERVICE"
34//   value: <ServiceMetadata 'service_metadata'>
35//
36//   # Metadata of remote files (compatible with version 3)
37//   key: "FILE: " + <string 'file_id'>
38//   value: <FileMetadata 'metadata'>
39//
40//   # Trackers of remote file updates (compatible with version 3)
41//   key: "TRACKER: " + <int64 'tracker_id'>
42//   value: <FileTracker 'tracker'>
43//
44//   # Index from App ID to the tracker ID
45//   key: "APP_ROOT: " + <string 'app_id'>
46//   value: <int64 'app_root_tracker_id'>
47//
48//   # Index from file ID to the active tracker ID
49//   key: "ACTIVE_FILE: " + <string 'file_id'>
50//   value: <int64 'active_tracker_id'>
51//
52//   # Index from file ID to a tracker ID
53//   key: "TRACKER_FILE: " + <string 'file_id'> + '\x00' + <int64 'tracker_id'>
54//   value: <empty>
55//
56//   # Tracker IDs; a file metadata linked to multiple tracker IDs.
57//   key: "MULTI_FILE: " + <int64 'tracker_id'>
58//   value: <empty>
59//
60//   # Index from the parent tracker ID and the title to the active tracker ID
61//   key: "ACTIVE_PATH: " + <int64 'parent_tracker_id'> +
62//        '\x00' + <string 'title'>
63//   value: <int64 'active_tracker_id'>
64//
65//   # Index from the parent tracker ID and the title to a tracker ID
66//   key: "TRACKER_PATH: " + <int64 'parent_tracker_id'> +
67//        '\x00' + <string 'title'> + '\x00' + <int64 'tracker_id'>
68//   value: <empty>
69//
70//   # Tracker IDs; a parent tracker ID and a title figure multiple tracker IDs
71//   key: "MULTI_PATH: " + <int64 'tracker_id'>
72//   value: <empty>
73//
74//   # Dirty tracker IDs
75//   key: "DIRTY: " + <int64 'dirty_tracker_id'>
76//   value: <empty>
77//
78//   # Demoted dirty tracker IDs
79//   key: "DEMOTED_DIRTY: " + <int64 'demoted_dirty_tracker_id'>
80//   value: <empty>
81
82namespace sync_file_system {
83namespace drive_backend {
84
85namespace {
86
87std::string GenerateAppRootIDByAppIDKey(const std::string& app_id) {
88  return kAppRootIDByAppIDKeyPrefix + app_id;
89}
90
91std::string GenerateActiveTrackerIDByFileIDKey(const std::string& file_id) {
92  return kActiveTrackerIDByFileIDKeyPrefix + file_id;
93}
94
95std::string GenerateTrackerIDByFileIDKeyPrefix(const std::string& file_id) {
96  std::ostringstream oss;
97  oss << kTrackerIDByFileIDKeyPrefix << file_id << '\0';
98  return oss.str();
99}
100
101std::string GenerateMultiTrackerKey(const std::string& file_id) {
102  return kMultiTrackerByFileIDKeyPrefix + file_id;
103}
104
105std::string GenerateActiveTrackerIDByParentAndTitleKey(
106    int64 parent_id, const std::string& title) {
107  std::ostringstream oss;
108  oss << kActiveTrackerIDByParentAndTitleKeyPrefix << parent_id
109      << '\0' << title;
110  return oss.str();
111}
112
113std::string GenerateTrackerIDByParentAndTitleKeyPrefix(
114    int64 parent_id, const std::string& title) {
115  std::ostringstream oss;
116  oss << kTrackerIDByParentAndTitleKeyPrefix << parent_id << '\0'
117      << title << '\0';
118  return oss.str();
119}
120
121std::string GenerateTrackerIDsByParentIDKeyPrefix(int64 parent_id) {
122  std::ostringstream oss;
123  oss << kTrackerIDByParentAndTitleKeyPrefix << parent_id << '\0';
124  return oss.str();
125}
126
127std::string GenerateMultiBackingParentAndTitleKey(
128    int64 parent_id, const std::string& title) {
129  std::ostringstream oss;
130  oss << kMultiBackingParentAndTitleKeyPrefix << parent_id << '\0'
131      << title;
132  return oss.str();
133}
134
135std::string GenerateDirtyIDKey(int64 tracker_id) {
136  return kDirtyIDKeyPrefix + base::Int64ToString(tracker_id);
137}
138
139std::string GenerateDemotedDirtyIDKey(int64 tracker_id) {
140  return kDemotedDirtyIDKeyPrefix + base::Int64ToString(tracker_id);
141}
142
143}  // namespace
144
145// static
146scoped_ptr<MetadataDatabaseIndexOnDisk>
147MetadataDatabaseIndexOnDisk::Create(
148    leveldb::DB* db, leveldb::WriteBatch* batch) {
149  DCHECK(db);
150
151  PutVersionToBatch(kDatabaseOnDiskVersion, batch);
152  scoped_ptr<MetadataDatabaseIndexOnDisk>
153      index(new MetadataDatabaseIndexOnDisk(db));
154  return index.Pass();
155}
156
157MetadataDatabaseIndexOnDisk::~MetadataDatabaseIndexOnDisk() {}
158
159bool MetadataDatabaseIndexOnDisk::GetFileMetadata(
160    const std::string& file_id, FileMetadata* metadata) const {
161  const std::string key = kFileMetadataKeyPrefix + file_id;
162  std::string value;
163  leveldb::Status status = db_->Get(leveldb::ReadOptions(), key, &value);
164
165  if (status.IsNotFound())
166    return false;
167
168  if (!status.ok()) {
169    util::Log(logging::LOG_WARNING, FROM_HERE,
170              "LevelDB error (%s) in getting FileMetadata for ID: %s",
171              status.ToString().c_str(),
172              file_id.c_str());
173    return false;
174  }
175
176  FileMetadata tmp_metadata;
177  if (!tmp_metadata.ParseFromString(value)) {
178    util::Log(logging::LOG_WARNING, FROM_HERE,
179              "Failed to parse a FileMetadata for ID: %s",
180              file_id.c_str());
181    return false;
182  }
183  if (metadata)
184    metadata->CopyFrom(tmp_metadata);
185
186  return true;
187}
188
189bool MetadataDatabaseIndexOnDisk::GetFileTracker(
190    int64 tracker_id, FileTracker* tracker) const {
191  const std::string key =
192      kFileTrackerKeyPrefix + base::Int64ToString(tracker_id);
193  std::string value;
194  leveldb::Status status = db_->Get(leveldb::ReadOptions(), key, &value);
195
196  if (status.IsNotFound())
197    return false;
198
199  if (!status.ok()) {
200    util::Log(logging::LOG_WARNING, FROM_HERE,
201              "LevelDB error (%s) in getting FileTracker for ID: %" PRId64,
202              status.ToString().c_str(),
203              tracker_id);
204    return false;
205  }
206
207  FileTracker tmp_tracker;
208  if (!tmp_tracker.ParseFromString(value)) {
209    util::Log(logging::LOG_WARNING, FROM_HERE,
210              "Failed to parse a Tracker for ID: %" PRId64,
211              tracker_id);
212    return false;
213  }
214  if (tracker)
215    tracker->CopyFrom(tmp_tracker);
216
217  return true;
218}
219
220void MetadataDatabaseIndexOnDisk::StoreFileMetadata(
221    scoped_ptr<FileMetadata> metadata, leveldb::WriteBatch* batch) {
222  DCHECK(metadata);
223  PutFileMetadataToBatch(*metadata, batch);
224}
225
226void MetadataDatabaseIndexOnDisk::StoreFileTracker(
227    scoped_ptr<FileTracker> tracker, leveldb::WriteBatch* batch) {
228  DCHECK(tracker);
229  PutFileTrackerToBatch(*tracker, batch);
230
231  int64 tracker_id = tracker->tracker_id();
232  FileTracker old_tracker;
233  if (!GetFileTracker(tracker_id, &old_tracker)) {
234    DVLOG(3) << "Adding new tracker: " << tracker->tracker_id()
235             << " " << GetTrackerTitle(*tracker);
236    AddToAppIDIndex(*tracker, batch);
237    AddToFileIDIndexes(*tracker, batch);
238    AddToPathIndexes(*tracker, batch);
239    AddToDirtyTrackerIndexes(*tracker, batch);
240  } else {
241    DVLOG(3) << "Updating tracker: " << tracker->tracker_id()
242             << " " << GetTrackerTitle(*tracker);
243    UpdateInAppIDIndex(old_tracker, *tracker, batch);
244    UpdateInFileIDIndexes(old_tracker, *tracker, batch);
245    UpdateInPathIndexes(old_tracker, *tracker, batch);
246    UpdateInDirtyTrackerIndexes(old_tracker, *tracker, batch);
247  }
248}
249
250void MetadataDatabaseIndexOnDisk::RemoveFileMetadata(
251    const std::string& file_id, leveldb::WriteBatch* batch) {
252  PutFileMetadataDeletionToBatch(file_id, batch);
253}
254
255void MetadataDatabaseIndexOnDisk::RemoveFileTracker(
256    int64 tracker_id, leveldb::WriteBatch* batch) {
257  PutFileTrackerDeletionToBatch(tracker_id, batch);
258
259  FileTracker tracker;
260  if (!GetFileTracker(tracker_id, &tracker)) {
261    NOTREACHED();
262    return;
263  }
264
265  DVLOG(1) << "Removing tracker: "
266           << tracker.tracker_id() << " " << GetTrackerTitle(tracker);
267  RemoveFromAppIDIndex(tracker, batch);
268  RemoveFromFileIDIndexes(tracker, batch);
269  RemoveFromPathIndexes(tracker, batch);
270  RemoveFromDirtyTrackerIndexes(tracker, batch);
271}
272
273TrackerIDSet MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByFileID(
274    const std::string& file_id) const {
275  return GetTrackerIDSetByPrefix(
276      GenerateActiveTrackerIDByFileIDKey(file_id),
277      GenerateTrackerIDByFileIDKeyPrefix(file_id));
278}
279
280int64 MetadataDatabaseIndexOnDisk::GetAppRootTracker(
281    const std::string& app_id) const {
282  const std::string key = GenerateAppRootIDByAppIDKey(app_id);
283  std::string value;
284  leveldb::Status status = db_->Get(leveldb::ReadOptions(), key, &value);
285
286  if (status.IsNotFound())
287    return kInvalidTrackerID;
288
289  if (!status.ok()) {
290    util::Log(logging::LOG_WARNING, FROM_HERE,
291              "LevelDB error (%s) in getting AppRoot for AppID: %s",
292              status.ToString().c_str(),
293              app_id.c_str());
294    return kInvalidTrackerID;
295  }
296
297  int64 root_id;
298  if (!base::StringToInt64(value, &root_id)) {
299    util::Log(logging::LOG_WARNING, FROM_HERE,
300              "Failed to parse a root ID (%s) for an App ID: %s",
301              value.c_str(),
302              app_id.c_str());
303    return kInvalidTrackerID;
304  }
305
306  return root_id;
307}
308
309TrackerIDSet MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByParentAndTitle(
310    int64 parent_tracker_id, const std::string& title) const {
311  return GetTrackerIDSetByPrefix(
312      GenerateActiveTrackerIDByParentAndTitleKey(parent_tracker_id, title),
313      GenerateTrackerIDByParentAndTitleKeyPrefix(parent_tracker_id, title));
314}
315
316std::vector<int64> MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByParent(
317    int64 parent_id) const {
318  std::vector<int64> result;
319
320  const std::string prefix = GenerateTrackerIDsByParentIDKeyPrefix(parent_id);
321  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
322  for (itr->Seek(prefix); itr->Valid(); itr->Next()) {
323    const std::string& key(itr->key().ToString());
324    std::string title_and_id;
325    if (!RemovePrefix(key, prefix, &title_and_id))
326      break;
327
328    size_t pos = title_and_id.rfind('\0');
329    DCHECK(pos != std::string::npos);
330
331    int64 tracker_id;
332    if (!base::StringToInt64(title_and_id.substr(pos + 1), &tracker_id))
333      continue;
334    result.push_back(tracker_id);
335  }
336  return result;
337}
338
339std::string MetadataDatabaseIndexOnDisk::PickMultiTrackerFileID() const {
340  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
341  itr->Seek(kMultiTrackerByFileIDKeyPrefix);
342  if (!itr->Valid())
343    return std::string();
344
345  std::string file_id;
346  if (!RemovePrefix(itr->key().ToString(),
347                    kMultiTrackerByFileIDKeyPrefix, &file_id))
348    return std::string();
349
350  return file_id;
351}
352
353ParentIDAndTitle MetadataDatabaseIndexOnDisk::PickMultiBackingFilePath() const {
354  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
355  itr->Seek(kMultiBackingParentAndTitleKeyPrefix);
356  if (!itr->Valid())
357    return ParentIDAndTitle();
358
359  std::string value;
360  if (!RemovePrefix(itr->key().ToString(),
361                    kMultiBackingParentAndTitleKeyPrefix, &value))
362    return ParentIDAndTitle();
363
364  size_t pos = value.find('\0');  // '\0' is a separator.
365  int64 parent_id;
366  if (pos == std::string::npos ||
367      !base::StringToInt64(value.substr(0, pos), &parent_id))
368    return ParentIDAndTitle();
369
370  // Successfully found an entry.
371  return ParentIDAndTitle(parent_id, value.substr(pos + 1));
372}
373
374int64 MetadataDatabaseIndexOnDisk::PickDirtyTracker() const {
375  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
376  itr->Seek(kDirtyIDKeyPrefix);
377  if (!itr->Valid())
378    return kInvalidTrackerID;
379
380  std::string id_str;
381  if (!RemovePrefix(itr->key().ToString(), kDirtyIDKeyPrefix, &id_str))
382    return kInvalidTrackerID;
383
384  int64 tracker_id;
385  if (!base::StringToInt64(id_str, &tracker_id))
386    return kInvalidTrackerID;
387
388  return tracker_id;
389}
390
391void MetadataDatabaseIndexOnDisk::DemoteDirtyTracker(
392    int64 tracker_id, leveldb::WriteBatch* batch) {
393  const std::string key = GenerateDirtyIDKey(tracker_id);
394
395  std::string value;
396  leveldb::Status status = db_->Get(leveldb::ReadOptions(), key, &value);
397  if (status.IsNotFound())
398    return;
399  if (!status.ok()) {
400    util::Log(logging::LOG_WARNING, FROM_HERE,
401              "LevelDB error (%s) in getting a dirty tracker for ID: %" PRId64,
402              status.ToString().c_str(),
403              tracker_id);
404    return;
405  }
406
407  batch->Delete(key);
408  batch->Put(GenerateDemotedDirtyIDKey(tracker_id), std::string());
409}
410
411bool MetadataDatabaseIndexOnDisk::HasDemotedDirtyTracker() const {
412  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
413  itr->Seek(kDemotedDirtyIDKeyPrefix);
414  if (!itr->Valid())
415    return false;
416  return StartsWithASCII(itr->key().ToString(), kDemotedDirtyIDKeyPrefix, true);
417}
418
419void MetadataDatabaseIndexOnDisk::PromoteDemotedDirtyTrackers(
420    leveldb::WriteBatch* batch) {
421  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
422  for (itr->Seek(kDirtyIDKeyPrefix); itr->Valid(); itr->Next()) {
423    std::string id_str;
424    if (!RemovePrefix(itr->key().ToString(), kDirtyIDKeyPrefix, &id_str))
425      break;
426
427    int64 tracker_id;
428    if (!base::StringToInt64(id_str, &tracker_id))
429      continue;
430
431    batch->Delete(itr->key());
432    batch->Put(GenerateDemotedDirtyIDKey(tracker_id), std::string());
433  }
434}
435
436size_t MetadataDatabaseIndexOnDisk::CountDirtyTracker() const {
437  size_t num_dirty_trackers = 0;
438
439  // TODO(peria): Store the number of dirty trackers, and do not iterate
440  // everytime.
441  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
442  for (itr->Seek(kDirtyIDKeyPrefix); itr->Valid(); itr->Next()) {
443    if (!StartsWithASCII(itr->key().ToString(), kDirtyIDKeyPrefix, true))
444      break;
445    ++num_dirty_trackers;
446  }
447
448  for (itr->Seek(kDemotedDirtyIDKeyPrefix); itr->Valid(); itr->Next()) {
449    if (!StartsWithASCII(itr->key().ToString(), kDemotedDirtyIDKeyPrefix, true))
450      break;
451    ++num_dirty_trackers;
452  }
453
454  return num_dirty_trackers;
455}
456
457size_t MetadataDatabaseIndexOnDisk::CountFileMetadata() const {
458  // TODO(peria): Cache the number of FileMetadata in the DB.
459  size_t count = 0;
460  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
461  for (itr->Seek(kFileMetadataKeyPrefix); itr->Valid(); itr->Next()) {
462    if (!StartsWithASCII(itr->key().ToString(), kFileMetadataKeyPrefix, true))
463      break;
464    ++count;
465  }
466  return count;
467}
468
469size_t MetadataDatabaseIndexOnDisk::CountFileTracker() const {
470  // TODO(peria): Cache the number of FileTracker in the DB.
471  size_t count = 0;
472  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
473  for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) {
474    if (!StartsWithASCII(itr->key().ToString(), kFileTrackerKeyPrefix, true))
475      break;
476    ++count;
477  }
478  return count;
479}
480
481void MetadataDatabaseIndexOnDisk::SetSyncRootTrackerID(
482    int64 sync_root_id, leveldb::WriteBatch* batch) const {
483  service_metadata_->set_sync_root_tracker_id(sync_root_id);
484  PutServiceMetadataToBatch(*service_metadata_, batch);
485}
486
487void MetadataDatabaseIndexOnDisk::SetLargestChangeID(
488    int64 largest_change_id, leveldb::WriteBatch* batch) const {
489  service_metadata_->set_largest_change_id(largest_change_id);
490  PutServiceMetadataToBatch(*service_metadata_, batch);
491}
492
493void MetadataDatabaseIndexOnDisk::SetNextTrackerID(
494    int64 next_tracker_id, leveldb::WriteBatch* batch) const {
495  service_metadata_->set_next_tracker_id(next_tracker_id);
496  PutServiceMetadataToBatch(*service_metadata_, batch);
497}
498
499int64 MetadataDatabaseIndexOnDisk::GetSyncRootTrackerID() const {
500  if (!service_metadata_->has_sync_root_tracker_id())
501    return kInvalidTrackerID;
502  return service_metadata_->sync_root_tracker_id();
503}
504
505int64 MetadataDatabaseIndexOnDisk::GetLargestChangeID() const {
506  if (!service_metadata_->has_largest_change_id())
507    return kInvalidTrackerID;
508  return service_metadata_->largest_change_id();
509}
510
511int64 MetadataDatabaseIndexOnDisk::GetNextTrackerID() const {
512  if (!service_metadata_->has_next_tracker_id())
513    return kInvalidTrackerID;
514  return service_metadata_->next_tracker_id();
515}
516
517std::vector<std::string>
518MetadataDatabaseIndexOnDisk::GetRegisteredAppIDs() const {
519  std::vector<std::string> result;
520  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
521  for (itr->Seek(kAppRootIDByAppIDKeyPrefix); itr->Valid(); itr->Next()) {
522    std::string id;
523    if (!RemovePrefix(itr->key().ToString(), kAppRootIDByAppIDKeyPrefix, &id))
524      break;
525    result.push_back(id);
526  }
527  return result;
528}
529
530std::vector<int64> MetadataDatabaseIndexOnDisk::GetAllTrackerIDs() const {
531  std::vector<int64> tracker_ids;
532  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
533  for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) {
534    std::string id_str;
535    if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, &id_str))
536      break;
537
538    int64 tracker_id;
539    if (!base::StringToInt64(id_str, &tracker_id))
540      continue;
541    tracker_ids.push_back(tracker_id);
542  }
543  return tracker_ids;
544}
545
546std::vector<std::string>
547MetadataDatabaseIndexOnDisk::GetAllMetadataIDs() const {
548  std::vector<std::string> file_ids;
549  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
550  for (itr->Seek(kFileMetadataKeyPrefix); itr->Valid(); itr->Next()) {
551    std::string file_id;
552    if (!RemovePrefix(itr->key().ToString(), kFileMetadataKeyPrefix, &file_id))
553      break;
554    file_ids.push_back(file_id);
555  }
556  return file_ids;
557}
558
559void MetadataDatabaseIndexOnDisk::BuildTrackerIndexes(
560    leveldb::WriteBatch* batch) {
561  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
562  for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) {
563    if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, NULL))
564      break;
565
566    FileTracker tracker;
567    if (!tracker.ParseFromString(itr->value().ToString())) {
568      util::Log(logging::LOG_WARNING, FROM_HERE,
569                "Failed to parse a Tracker");
570      continue;
571    }
572
573    AddToAppIDIndex(tracker, batch);
574    AddToFileIDIndexes(tracker, batch);
575    AddToPathIndexes(tracker, batch);
576    AddToDirtyTrackerIndexes(tracker, batch);
577  }
578}
579
580MetadataDatabaseIndexOnDisk::MetadataDatabaseIndexOnDisk(leveldb::DB* db)
581    : db_(db) {
582  // TODO(peria): Add UMA to measure the number of FileMetadata, FileTracker,
583  //    and AppRootId.
584  // TODO(peria): If the DB version is 3, build up index lists.
585  service_metadata_ = InitializeServiceMetadata(db_);
586}
587
588void MetadataDatabaseIndexOnDisk::AddToAppIDIndex(
589    const FileTracker& tracker, leveldb::WriteBatch* batch) {
590  if (!IsAppRoot(tracker)) {
591    DVLOG(3) << "  Tracker for " << tracker.file_id() << " is not an App root.";
592    return;
593  }
594
595  DVLOG(1) << "  Add to App root by App ID: " << tracker.app_id();
596
597  const std::string db_key = GenerateAppRootIDByAppIDKey(tracker.app_id());
598  DCHECK(tracker.active());
599  DCHECK(!DBHasKey(db_key));
600  batch->Put(db_key, base::Int64ToString(tracker.tracker_id()));
601}
602
603void MetadataDatabaseIndexOnDisk::UpdateInAppIDIndex(
604    const FileTracker& old_tracker,
605    const FileTracker& new_tracker,
606    leveldb::WriteBatch* batch) {
607  DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id());
608
609  if (IsAppRoot(old_tracker) && !IsAppRoot(new_tracker)) {
610    DCHECK(old_tracker.active());
611    DCHECK(!new_tracker.active());
612    const std::string key = GenerateAppRootIDByAppIDKey(old_tracker.app_id());
613    DCHECK(DBHasKey(key));
614
615    DVLOG(1) << "  Remove from App root by App ID: " << old_tracker.app_id();
616    batch->Delete(key);
617  } else if (!IsAppRoot(old_tracker) && IsAppRoot(new_tracker)) {
618    DCHECK(!old_tracker.active());
619    DCHECK(new_tracker.active());
620    const std::string key = GenerateAppRootIDByAppIDKey(new_tracker.app_id());
621    DCHECK(!DBHasKey(key));
622
623    DVLOG(1) << "  Add to App root by App ID: " << new_tracker.app_id();
624    batch->Put(key, base::Int64ToString(new_tracker.tracker_id()));
625  }
626}
627
628void MetadataDatabaseIndexOnDisk::RemoveFromAppIDIndex(
629    const FileTracker& tracker, leveldb::WriteBatch* batch) {
630  if (!IsAppRoot(tracker)) {
631    DVLOG(3) << "  Tracker for " << tracker.file_id() << " is not an App root.";
632    return;
633  }
634
635  DCHECK(tracker.active());
636  const std::string key = GenerateAppRootIDByAppIDKey(tracker.app_id());
637  DCHECK(DBHasKey(key));
638
639  DVLOG(1) << "  Remove from App root by App ID: " << tracker.app_id();
640  batch->Delete(key);
641}
642
643void MetadataDatabaseIndexOnDisk::AddToFileIDIndexes(
644    const FileTracker& new_tracker, leveldb::WriteBatch* batch) {
645  const std::string& file_id = new_tracker.file_id();
646
647  DVLOG(1) << "  Add to trackers by file ID: " << file_id;
648  const std::string prefix = GenerateTrackerIDByFileIDKeyPrefix(file_id);
649  AddToTrackerIDSetWithPrefix(
650      GenerateActiveTrackerIDByFileIDKey(file_id),
651      prefix, new_tracker, batch);
652
653  const std::string multi_tracker_key = GenerateMultiTrackerKey(file_id);
654  if (!DBHasKey(multi_tracker_key) &&
655      CountWithPrefix(prefix, new_tracker.tracker_id()) != NONE) {
656    DVLOG(1) << "  Add to multi-tracker file IDs: " << file_id;
657    batch->Put(multi_tracker_key, std::string());
658  }
659}
660
661void MetadataDatabaseIndexOnDisk::UpdateInFileIDIndexes(
662    const FileTracker& old_tracker,
663    const FileTracker& new_tracker,
664    leveldb::WriteBatch* batch) {
665  DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id());
666  DCHECK_EQ(old_tracker.file_id(), new_tracker.file_id());
667
668  const std::string& file_id = new_tracker.file_id();
669  const std::string prefix = GenerateTrackerIDByFileIDKeyPrefix(file_id);
670  DCHECK(DBHasKey(prefix + base::Int64ToString(new_tracker.tracker_id())));
671
672  if (old_tracker.active() && !new_tracker.active()) {
673    DeactivateInTrackerIDSetWithPrefix(
674        GenerateActiveTrackerIDByFileIDKey(file_id), prefix,
675        new_tracker.tracker_id(), batch);
676  } else if (!old_tracker.active() && new_tracker.active()) {
677    ActivateInTrackerIDSetWithPrefix(
678        GenerateActiveTrackerIDByFileIDKey(file_id), prefix,
679        new_tracker.tracker_id(), batch);
680  }
681}
682
683void MetadataDatabaseIndexOnDisk::RemoveFromFileIDIndexes(
684    const FileTracker& tracker, leveldb::WriteBatch* batch) {
685  const std::string& file_id = tracker.file_id();
686  const std::string prefix =
687      GenerateTrackerIDByFileIDKeyPrefix(file_id);
688
689  if (!EraseInTrackerIDSetWithPrefix(
690          GenerateActiveTrackerIDByFileIDKey(file_id),
691          prefix, tracker.tracker_id(), batch))
692    return;
693
694  DVLOG(1) << "  Remove from trackers by file ID: " << tracker.tracker_id();
695
696  const std::string multi_key = GenerateMultiTrackerKey(file_id);
697  if (DBHasKey(multi_key) &&
698      CountWithPrefix(prefix, tracker.tracker_id()) != MULTIPLE) {
699    DVLOG(1) << "  Remove from multi-tracker file IDs: " << file_id;
700    batch->Delete(multi_key);
701  }
702}
703
704void MetadataDatabaseIndexOnDisk::AddToPathIndexes(
705    const FileTracker& new_tracker, leveldb::WriteBatch* batch) {
706  int64 parent_id = new_tracker.parent_tracker_id();
707  std::string title = GetTrackerTitle(new_tracker);
708
709  DVLOG(1) << "  Add to trackers by parent and title: "
710           << parent_id << " " << title;
711
712  const std::string prefix =
713      GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title);
714  AddToTrackerIDSetWithPrefix(
715      GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title),
716      prefix, new_tracker, batch);
717
718  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
719  for (itr->Seek(prefix); itr->Valid(); itr->Next()) {
720    std::string id_str;
721    if (!RemovePrefix(itr->key().ToString(), prefix, &id_str))
722      break;
723
724    int64 tracker_id;
725    if (!base::StringToInt64(id_str, &tracker_id))
726      continue;
727    if (tracker_id == new_tracker.tracker_id()) {
728      NOTREACHED();
729      continue;
730    }
731
732    const std::string multi_key =
733        GenerateMultiBackingParentAndTitleKey(parent_id, title);
734    DVLOG_IF(1, !DBHasKey(multi_key))
735        << "  Add to multi backing file paths: " << parent_id << " " << title;
736    batch->Put(GenerateMultiBackingParentAndTitleKey(parent_id, title),
737               std::string());
738    break;
739  }
740}
741
742void MetadataDatabaseIndexOnDisk::UpdateInPathIndexes(
743    const FileTracker& old_tracker,
744    const FileTracker& new_tracker,
745    leveldb::WriteBatch* batch) {
746  DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id());
747  DCHECK_EQ(old_tracker.parent_tracker_id(), new_tracker.parent_tracker_id());
748  DCHECK(GetTrackerTitle(old_tracker) == GetTrackerTitle(new_tracker) ||
749         !old_tracker.has_synced_details());
750
751  int64 tracker_id = new_tracker.tracker_id();
752  int64 parent_id = new_tracker.parent_tracker_id();
753  const std::string old_title = GetTrackerTitle(old_tracker);
754  const std::string title = GetTrackerTitle(new_tracker);
755
756  if (old_title != title) {
757    const std::string old_prefix =
758        GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, old_title);
759    EraseInTrackerIDSetWithPrefix(
760        GenerateActiveTrackerIDByParentAndTitleKey(parent_id, old_title),
761        old_prefix, tracker_id, batch);
762
763    if (!old_title.empty() &&
764        CountWithPrefix(old_prefix, tracker_id) != MULTIPLE) {
765      const std::string old_multi_backing_key =
766          GenerateMultiBackingParentAndTitleKey(parent_id, old_title);
767      DVLOG_IF(1, DBHasKey(old_multi_backing_key))
768          << "  Remove from multi backing file paths: "
769          << parent_id << " " << old_title;
770      batch->Delete(old_multi_backing_key);
771    }
772
773    DVLOG(1) << "  Add to trackers by parent and title: "
774             << parent_id << " " << title;
775
776    const std::string prefix =
777        GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title);
778    AddToTrackerIDSetWithPrefix(
779        GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title),
780        prefix, new_tracker, batch);
781
782    if (CountWithPrefix(prefix, tracker_id) != NONE) {
783      const std::string multi_backing_key =
784          GenerateMultiBackingParentAndTitleKey(parent_id, title);
785      DVLOG_IF(1, !DBHasKey(multi_backing_key))
786          << "  Add to multi backing file_paths: "
787          << parent_id << " " << title;
788      batch->Put(multi_backing_key, std::string());
789    }
790
791    return;
792  }
793
794  const std::string active_tracker_key =
795      GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title);
796  const std::string prefix =
797      GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title);
798  if (old_tracker.active() && !new_tracker.active()) {
799    DeactivateInTrackerIDSetWithPrefix(
800        active_tracker_key, prefix, tracker_id, batch);
801  } else if (!old_tracker.active() && new_tracker.active()) {
802    ActivateInTrackerIDSetWithPrefix(
803        active_tracker_key, prefix, tracker_id, batch);
804  }
805}
806
807void MetadataDatabaseIndexOnDisk::RemoveFromPathIndexes(
808    const FileTracker& tracker, leveldb::WriteBatch* batch) {
809  int64 tracker_id = tracker.tracker_id();
810  int64 parent_id = tracker.parent_tracker_id();
811  std::string title = GetTrackerTitle(tracker);
812
813  DVLOG(1) << "  Remove from trackers by parent and title: "
814           << parent_id << " " << title;
815
816  const std::string active_tracker_key =
817      GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title);
818  const std::string key_prefix =
819      GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title);
820  if (!EraseInTrackerIDSetWithPrefix(
821          active_tracker_key, key_prefix, tracker_id, batch))
822    return;
823
824  const std::string multi_key =
825      GenerateMultiBackingParentAndTitleKey(parent_id, title);
826  if (!title.empty() && DBHasKey(multi_key) &&
827      CountWithPrefix(key_prefix, tracker_id) != MULTIPLE) {
828    DVLOG(1) << "  Remove from multi backing file paths: "
829             << parent_id << " " << title;
830    batch->Delete(multi_key);
831  }
832}
833
834void MetadataDatabaseIndexOnDisk::AddToDirtyTrackerIndexes(
835    const FileTracker& new_tracker,
836    leveldb::WriteBatch* batch) {
837  const std::string dirty_key = GenerateDirtyIDKey(new_tracker.tracker_id());
838  DCHECK(!DBHasKey(dirty_key));
839  DCHECK(!DBHasKey(GenerateDemotedDirtyIDKey(new_tracker.tracker_id())));
840
841  if (new_tracker.dirty()) {
842    DVLOG(1) << "  Add to dirty tracker IDs: " << new_tracker.tracker_id();
843    batch->Put(dirty_key, std::string());
844  }
845}
846
847void MetadataDatabaseIndexOnDisk::UpdateInDirtyTrackerIndexes(
848    const FileTracker& old_tracker,
849    const FileTracker& new_tracker,
850    leveldb::WriteBatch* batch) {
851  DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id());
852
853  int64 tracker_id = new_tracker.tracker_id();
854  const std::string dirty_key = GenerateDirtyIDKey(tracker_id);
855  const std::string demoted_key = GenerateDemotedDirtyIDKey(tracker_id);
856  if (old_tracker.dirty() && !new_tracker.dirty()) {
857    DCHECK(DBHasKey(dirty_key) || DBHasKey(demoted_key));
858
859    DVLOG(1) << "  Remove from dirty trackers IDs: " << tracker_id;
860
861    batch->Delete(dirty_key);
862    batch->Delete(demoted_key);
863  } else if (!old_tracker.dirty() && new_tracker.dirty()) {
864    DCHECK(!DBHasKey(dirty_key));
865    DCHECK(!DBHasKey(demoted_key));
866
867    DVLOG(1) << "  Add to dirty tracker IDs: " << tracker_id;
868
869    batch->Put(dirty_key, std::string());
870  }
871}
872
873void MetadataDatabaseIndexOnDisk::RemoveFromDirtyTrackerIndexes(
874    const FileTracker& tracker, leveldb::WriteBatch* batch) {
875  if (tracker.dirty()) {
876    int64 tracker_id = tracker.tracker_id();
877    const std::string dirty_key = GenerateDirtyIDKey(tracker_id);
878    const std::string demoted_key = GenerateDemotedDirtyIDKey(tracker_id);
879    DCHECK(DBHasKey(dirty_key) || DBHasKey(demoted_key));
880
881    DVLOG(1) << "  Remove from dirty tracker IDs: " << tracker_id;
882    batch->Delete(dirty_key);
883    batch->Delete(demoted_key);
884  }
885}
886
887TrackerIDSet MetadataDatabaseIndexOnDisk::GetTrackerIDSetByPrefix(
888    const std::string& active_tracker_key,
889    const std::string& ids_prefix) const {
890  TrackerIDSet trackers;
891
892  // Seek IDs.
893  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
894  for (itr->Seek(ids_prefix); itr->Valid(); itr->Next()) {
895    const std::string& key(itr->key().ToString());
896    std::string id_str;
897    if (!RemovePrefix(key, ids_prefix, &id_str))
898      break;
899
900    int64 tracker_id;
901    if (!base::StringToInt64(id_str, &tracker_id))
902      continue;
903    trackers.InsertInactiveTracker(tracker_id);
904  }
905
906  // Set an active tracker ID, if available.
907  std::string value;
908  leveldb::Status status = db_->Get(leveldb::ReadOptions(),
909                                    active_tracker_key, &value);
910  int64 active_tracker;
911  if (status.ok() && base::StringToInt64(value, &active_tracker) &&
912      active_tracker != kInvalidTrackerID) {
913    trackers.Activate(active_tracker);
914  }
915
916  return trackers;
917}
918
919void MetadataDatabaseIndexOnDisk::AddToTrackerIDSetWithPrefix(
920    const std::string& active_tracker_key, const std::string& key_prefix,
921    const FileTracker& tracker, leveldb::WriteBatch* batch) {
922  DCHECK(tracker.tracker_id());
923
924  const std::string id_str = base::Int64ToString(tracker.tracker_id());
925  batch->Put(key_prefix + id_str, std::string());
926  if (tracker.active())
927    batch->Put(active_tracker_key, id_str);
928}
929
930bool MetadataDatabaseIndexOnDisk::EraseInTrackerIDSetWithPrefix(
931    const std::string& active_tracker_key, const std::string& key_prefix,
932    int64 tracker_id, leveldb::WriteBatch* batch) {
933  std::string value;
934  const std::string del_key = key_prefix + base::Int64ToString(tracker_id);
935  leveldb::Status status = db_->Get(leveldb::ReadOptions(), del_key, &value);
936  if (status.IsNotFound())
937    return false;
938
939  batch->Delete(del_key);
940
941  size_t count = 0;
942  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
943  for (itr->Seek(key_prefix); itr->Valid(); itr->Next()) {
944    const std::string key = itr->key().ToString();
945    if (!StartsWithASCII(key, key_prefix, true))
946      break;
947    // Entry for |del_key| is not deleted yet.
948    if (key == del_key)
949      continue;
950    ++count;
951    break;
952  }
953
954  if (count > 0) {
955    // TrackerIDSet is still alive.  Deactivate if the tracker is active.
956    leveldb::Status status =
957        db_->Get(leveldb::ReadOptions(), active_tracker_key, &value);
958    int64 active_tracker_id;
959    if (status.ok() && base::StringToInt64(value, &active_tracker_id) &&
960        active_tracker_id == tracker_id) {
961      batch->Put(active_tracker_key, base::Int64ToString(kInvalidTrackerID));
962    }
963  } else {
964    // TrackerIDSet is no longer alive.  Erase active tracker entry.
965    batch->Delete(active_tracker_key);
966  }
967
968  return true;
969}
970
971void MetadataDatabaseIndexOnDisk::ActivateInTrackerIDSetWithPrefix(
972    const std::string& active_tracker_key, const std::string& key_prefix,
973    int64 tracker_id, leveldb::WriteBatch* batch) {
974  DCHECK(DBHasKey(key_prefix + base::Int64ToString(tracker_id)));
975
976  std::string value;
977  leveldb::Status status = db_->Get(leveldb::ReadOptions(),
978                                    active_tracker_key, &value);
979  int64 active_tracker_id;
980  if (status.ok() && base::StringToInt64(value, &active_tracker_id)) {
981    DCHECK(active_tracker_id != tracker_id);
982    batch->Put(active_tracker_key, base::Int64ToString(tracker_id));
983  }
984}
985
986void MetadataDatabaseIndexOnDisk::DeactivateInTrackerIDSetWithPrefix(
987    const std::string& active_tracker_key, const std::string& key_prefix,
988    int64 tracker_id, leveldb::WriteBatch* batch) {
989  DCHECK(DBHasKey(key_prefix + base::Int64ToString(tracker_id)));
990
991  std::string value;
992  leveldb::Status status = db_->Get(leveldb::ReadOptions(),
993                                    active_tracker_key, &value);
994  int64 active_tracker_id;
995  if (status.ok() && base::StringToInt64(value, &active_tracker_id)) {
996    DCHECK(active_tracker_id == tracker_id);
997    batch->Put(active_tracker_key, base::Int64ToString(kInvalidTrackerID));
998  }
999}
1000
1001bool MetadataDatabaseIndexOnDisk::DBHasKey(const std::string& key) {
1002  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
1003  itr->Seek(key);
1004  return itr->Valid() && (itr->key() == key);
1005}
1006
1007MetadataDatabaseIndexOnDisk::NumEntries
1008MetadataDatabaseIndexOnDisk::CountWithPrefix(
1009    const std::string& prefix, int64 ignored_id) {
1010  const std::string ignored = base::Int64ToString(ignored_id);
1011
1012  size_t count = 0;
1013  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
1014  for (itr->Seek(prefix); itr->Valid() && count <= 1; itr->Next()) {
1015    std::string value;
1016    if (!RemovePrefix(itr->key().ToString(), prefix, &value))
1017      break;
1018    if (value == ignored)
1019      continue;
1020
1021    ++count;
1022  }
1023
1024  if (count >= 2)
1025    return MULTIPLE;
1026  return count == 0 ? NONE : SINGLE;
1027}
1028
1029}  // namespace drive_backend
1030}  // namespace sync_file_system
1031