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/leveldb_wrapper.h"
14#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
15#include "chrome/browser/sync_file_system/logger.h"
16#include "third_party/leveldatabase/src/include/leveldb/status.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//
82//   # Timestamp when the last validation ran
83//   key: "LAST_VALID"
84//   value: <time_t 'last_valid_time'>
85
86namespace sync_file_system {
87namespace drive_backend {
88
89namespace {
90
91std::string GenerateAppRootIDByAppIDKey(const std::string& app_id) {
92  return kAppRootIDByAppIDKeyPrefix + app_id;
93}
94
95std::string GenerateActiveTrackerIDByFileIDKey(const std::string& file_id) {
96  return kActiveTrackerIDByFileIDKeyPrefix + file_id;
97}
98
99std::string GenerateTrackerIDByFileIDKeyPrefix(const std::string& file_id) {
100  std::ostringstream oss;
101  oss << kTrackerIDByFileIDKeyPrefix << file_id << '\0';
102  return oss.str();
103}
104
105std::string GenerateMultiTrackerKey(const std::string& file_id) {
106  return kMultiTrackerByFileIDKeyPrefix + file_id;
107}
108
109std::string GenerateActiveTrackerIDByParentAndTitleKey(
110    int64 parent_id, const std::string& title) {
111  std::ostringstream oss;
112  oss << kActiveTrackerIDByParentAndTitleKeyPrefix << parent_id
113      << '\0' << title;
114  return oss.str();
115}
116
117std::string GenerateTrackerIDByParentAndTitleKeyPrefix(
118    int64 parent_id, const std::string& title) {
119  std::ostringstream oss;
120  oss << kTrackerIDByParentAndTitleKeyPrefix << parent_id << '\0'
121      << title << '\0';
122  return oss.str();
123}
124
125std::string GenerateTrackerIDsByParentIDKeyPrefix(int64 parent_id) {
126  std::ostringstream oss;
127  oss << kTrackerIDByParentAndTitleKeyPrefix << parent_id << '\0';
128  return oss.str();
129}
130
131std::string GenerateMultiBackingParentAndTitleKey(
132    int64 parent_id, const std::string& title) {
133  std::ostringstream oss;
134  oss << kMultiBackingParentAndTitleKeyPrefix << parent_id << '\0'
135      << title;
136  return oss.str();
137}
138
139std::string GenerateDirtyIDKey(int64 tracker_id) {
140  return kDirtyIDKeyPrefix + base::Int64ToString(tracker_id);
141}
142
143std::string GenerateDemotedDirtyIDKey(int64 tracker_id) {
144  return kDemotedDirtyIDKeyPrefix + base::Int64ToString(tracker_id);
145}
146
147void RemoveUnreachableItems(LevelDBWrapper* db, int64 sync_root_tracker_id) {
148  DCHECK(db);
149
150  typedef std::map<int64, std::set<int64> > ChildTrackersByParent;
151  ChildTrackersByParent trackers_by_parent;
152  {
153    // Set up links from parent tracker to child trackers.
154    std::set<int64> inactive_trackers;
155    scoped_ptr<LevelDBWrapper::Iterator> itr = db->NewIterator();
156    for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) {
157      if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, NULL))
158        break;
159
160      scoped_ptr<FileTracker> tracker(new FileTracker);
161      if (!tracker->ParseFromString(itr->value().ToString())) {
162        util::Log(logging::LOG_WARNING, FROM_HERE,
163                  "Failed to parse a Tracker");
164        continue;
165      }
166
167      int64 parent_tracker_id = tracker->parent_tracker_id();
168      int64 tracker_id = tracker->tracker_id();
169      trackers_by_parent[parent_tracker_id].insert(tracker_id);
170      if (!tracker->active())
171        inactive_trackers.insert(tracker_id);
172    }
173
174    // Drop links from inactive trackers.
175    for (std::set<int64>::iterator iter = inactive_trackers.begin();
176         iter != inactive_trackers.end(); ++iter) {
177      trackers_by_parent.erase(*iter);
178    }
179  }
180
181  // Traverse tracker tree from sync-root.
182  std::set<int64> visited_trackers;
183  {
184    std::vector<int64> pending;
185    if (sync_root_tracker_id != kInvalidTrackerID)
186      pending.push_back(sync_root_tracker_id);
187
188    while (!pending.empty()) {
189      int64 tracker_id = pending.back();
190      DCHECK_NE(kInvalidTrackerID, tracker_id);
191      pending.pop_back();
192
193      if (!visited_trackers.insert(tracker_id).second) {
194        NOTREACHED();
195        continue;
196      }
197
198      AppendContents(
199          LookUpMap(trackers_by_parent, tracker_id, std::set<int64>()),
200          &pending);
201    }
202  }
203
204  // Delete all unreachable trackers, and list all |file_id| referred by
205  // remained trackers.
206  base::hash_set<std::string> referred_file_ids;
207  {
208    scoped_ptr<LevelDBWrapper::Iterator> itr = db->NewIterator();
209    for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) {
210      if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, NULL))
211        break;
212
213      scoped_ptr<FileTracker> tracker(new FileTracker);
214      if (!tracker->ParseFromString(itr->value().ToString())) {
215        util::Log(logging::LOG_WARNING, FROM_HERE,
216                  "Failed to parse a Tracker");
217        continue;
218      }
219
220      if (ContainsKey(visited_trackers, tracker->tracker_id())) {
221        referred_file_ids.insert(tracker->file_id());
222      } else {
223        PutFileTrackerDeletionToDB(tracker->tracker_id(), db);
224      }
225    }
226  }
227
228  // Delete all unreferred metadata.
229  {
230    scoped_ptr<LevelDBWrapper::Iterator> itr = db->NewIterator();
231    for (itr->Seek(kFileMetadataKeyPrefix); itr->Valid(); itr->Next()) {
232      if (!RemovePrefix(itr->key().ToString(), kFileMetadataKeyPrefix, NULL))
233        break;
234
235      scoped_ptr<FileMetadata> metadata(new FileMetadata);
236      if (!metadata->ParseFromString(itr->value().ToString())) {
237        util::Log(logging::LOG_WARNING, FROM_HERE,
238                  "Failed to parse a Tracker");
239        continue;
240      }
241
242      if (!ContainsKey(referred_file_ids, metadata->file_id()))
243        PutFileMetadataDeletionToDB(metadata->file_id(), db);
244    }
245  }
246}
247
248}  // namespace
249
250// static
251scoped_ptr<MetadataDatabaseIndexOnDisk>
252MetadataDatabaseIndexOnDisk::Create(LevelDBWrapper* db) {
253  DCHECK(db);
254
255  scoped_ptr<ServiceMetadata> service_metadata = InitializeServiceMetadata(db);
256  if (!service_metadata)
257    return scoped_ptr<MetadataDatabaseIndexOnDisk>();
258
259  PutVersionToDB(kDatabaseOnDiskVersion, db);
260  RemoveUnreachableItems(db, service_metadata->sync_root_tracker_id());
261  scoped_ptr<MetadataDatabaseIndexOnDisk>
262      index(new MetadataDatabaseIndexOnDisk(db));
263
264  return index.Pass();
265}
266
267MetadataDatabaseIndexOnDisk::~MetadataDatabaseIndexOnDisk() {}
268
269bool MetadataDatabaseIndexOnDisk::GetFileMetadata(
270    const std::string& file_id, FileMetadata* metadata) const {
271  const std::string key = kFileMetadataKeyPrefix + file_id;
272  std::string value;
273  leveldb::Status status = db_->Get(key, &value);
274
275  if (status.IsNotFound())
276    return false;
277
278  if (!status.ok()) {
279    util::Log(logging::LOG_WARNING, FROM_HERE,
280              "LevelDB error (%s) in getting FileMetadata for ID: %s",
281              status.ToString().c_str(),
282              file_id.c_str());
283    return false;
284  }
285
286  FileMetadata tmp_metadata;
287  if (!tmp_metadata.ParseFromString(value)) {
288    util::Log(logging::LOG_WARNING, FROM_HERE,
289              "Failed to parse a FileMetadata for ID: %s",
290              file_id.c_str());
291    return false;
292  }
293  if (metadata)
294    metadata->CopyFrom(tmp_metadata);
295
296  return true;
297}
298
299bool MetadataDatabaseIndexOnDisk::GetFileTracker(
300    int64 tracker_id, FileTracker* tracker) const {
301  const std::string key =
302      kFileTrackerKeyPrefix + base::Int64ToString(tracker_id);
303  std::string value;
304  leveldb::Status status = db_->Get(key, &value);
305
306  if (status.IsNotFound())
307    return false;
308
309  if (!status.ok()) {
310    util::Log(logging::LOG_WARNING, FROM_HERE,
311              "LevelDB error (%s) in getting FileTracker for ID: %" PRId64,
312              status.ToString().c_str(),
313              tracker_id);
314    return false;
315  }
316
317  FileTracker tmp_tracker;
318  if (!tmp_tracker.ParseFromString(value)) {
319    util::Log(logging::LOG_WARNING, FROM_HERE,
320              "Failed to parse a Tracker for ID: %" PRId64,
321              tracker_id);
322    return false;
323  }
324  if (tracker)
325    tracker->CopyFrom(tmp_tracker);
326
327  return true;
328}
329
330void MetadataDatabaseIndexOnDisk::StoreFileMetadata(
331    scoped_ptr<FileMetadata> metadata) {
332  DCHECK(metadata);
333  PutFileMetadataToDB(*metadata, db_);
334}
335
336void MetadataDatabaseIndexOnDisk::StoreFileTracker(
337    scoped_ptr<FileTracker> tracker) {
338  DCHECK(tracker);
339
340  int64 tracker_id = tracker->tracker_id();
341  FileTracker old_tracker;
342  if (!GetFileTracker(tracker_id, &old_tracker)) {
343    DVLOG(3) << "Adding new tracker: " << tracker->tracker_id()
344             << " " << GetTrackerTitle(*tracker);
345    AddToAppIDIndex(*tracker);
346    AddToFileIDIndexes(*tracker);
347    AddToPathIndexes(*tracker);
348    AddToDirtyTrackerIndexes(*tracker);
349  } else {
350    DVLOG(3) << "Updating tracker: " << tracker->tracker_id()
351             << " " << GetTrackerTitle(*tracker);
352    UpdateInAppIDIndex(old_tracker, *tracker);
353    UpdateInFileIDIndexes(old_tracker, *tracker);
354    UpdateInPathIndexes(old_tracker, *tracker);
355    UpdateInDirtyTrackerIndexes(old_tracker, *tracker);
356
357  }
358
359  PutFileTrackerToDB(*tracker, db_);
360}
361
362void MetadataDatabaseIndexOnDisk::RemoveFileMetadata(
363    const std::string& file_id) {
364  PutFileMetadataDeletionToDB(file_id, db_);
365}
366
367void MetadataDatabaseIndexOnDisk::RemoveFileTracker(int64 tracker_id) {
368  FileTracker tracker;
369  if (!GetFileTracker(tracker_id, &tracker)) {
370    NOTREACHED();
371    return;
372  }
373
374  DVLOG(1) << "Removing tracker: "
375           << tracker.tracker_id() << " " << GetTrackerTitle(tracker);
376  RemoveFromAppIDIndex(tracker);
377  RemoveFromFileIDIndexes(tracker);
378  RemoveFromPathIndexes(tracker);
379  RemoveFromDirtyTrackerIndexes(tracker);
380
381  PutFileTrackerDeletionToDB(tracker_id, db_);
382}
383
384TrackerIDSet MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByFileID(
385    const std::string& file_id) const {
386  return GetTrackerIDSetByPrefix(
387      GenerateActiveTrackerIDByFileIDKey(file_id),
388      GenerateTrackerIDByFileIDKeyPrefix(file_id));
389}
390
391int64 MetadataDatabaseIndexOnDisk::GetAppRootTracker(
392    const std::string& app_id) const {
393  const std::string key = GenerateAppRootIDByAppIDKey(app_id);
394  std::string value;
395  leveldb::Status status = db_->Get(key, &value);
396
397  if (status.IsNotFound())
398    return kInvalidTrackerID;
399
400  if (!status.ok()) {
401    util::Log(logging::LOG_WARNING, FROM_HERE,
402              "LevelDB error (%s) in getting AppRoot for AppID: %s",
403              status.ToString().c_str(),
404              app_id.c_str());
405    return kInvalidTrackerID;
406  }
407
408  int64 root_id;
409  if (!base::StringToInt64(value, &root_id)) {
410    util::Log(logging::LOG_WARNING, FROM_HERE,
411              "Failed to parse a root ID (%s) for an App ID: %s",
412              value.c_str(),
413              app_id.c_str());
414    return kInvalidTrackerID;
415  }
416
417  return root_id;
418}
419
420TrackerIDSet MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByParentAndTitle(
421    int64 parent_tracker_id, const std::string& title) const {
422  return GetTrackerIDSetByPrefix(
423      GenerateActiveTrackerIDByParentAndTitleKey(parent_tracker_id, title),
424      GenerateTrackerIDByParentAndTitleKeyPrefix(parent_tracker_id, title));
425}
426
427std::vector<int64> MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByParent(
428    int64 parent_id) const {
429  std::vector<int64> result;
430
431  const std::string prefix = GenerateTrackerIDsByParentIDKeyPrefix(parent_id);
432  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
433  for (itr->Seek(prefix); itr->Valid(); itr->Next()) {
434    const std::string& key(itr->key().ToString());
435    std::string title_and_id;
436    if (!RemovePrefix(key, prefix, &title_and_id))
437      break;
438
439    size_t pos = title_and_id.rfind('\0');
440    DCHECK(pos != std::string::npos);
441
442    int64 tracker_id;
443    if (!base::StringToInt64(title_and_id.substr(pos + 1), &tracker_id))
444      continue;
445    result.push_back(tracker_id);
446  }
447  return result;
448}
449
450std::string MetadataDatabaseIndexOnDisk::PickMultiTrackerFileID() const {
451  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
452  itr->Seek(kMultiTrackerByFileIDKeyPrefix);
453  if (!itr->Valid())
454    return std::string();
455
456  std::string file_id;
457  if (!RemovePrefix(itr->key().ToString(),
458                    kMultiTrackerByFileIDKeyPrefix, &file_id))
459    return std::string();
460
461  return file_id;
462}
463
464ParentIDAndTitle MetadataDatabaseIndexOnDisk::PickMultiBackingFilePath() const {
465  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
466  itr->Seek(kMultiBackingParentAndTitleKeyPrefix);
467  if (!itr->Valid())
468    return ParentIDAndTitle();
469
470  std::string value;
471  if (!RemovePrefix(itr->key().ToString(),
472                    kMultiBackingParentAndTitleKeyPrefix, &value))
473    return ParentIDAndTitle();
474
475  size_t pos = value.find('\0');  // '\0' is a separator.
476  if (pos == std::string::npos)
477    return ParentIDAndTitle();
478
479  int64 parent_id;
480  return base::StringToInt64(value.substr(0, pos), &parent_id) ?
481      ParentIDAndTitle(parent_id, value.substr(pos + 1)) : ParentIDAndTitle();
482}
483
484int64 MetadataDatabaseIndexOnDisk::PickDirtyTracker() const {
485  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
486  itr->Seek(kDirtyIDKeyPrefix);
487  if (!itr->Valid())
488    return kInvalidTrackerID;
489
490  std::string id_str;
491  if (!RemovePrefix(itr->key().ToString(), kDirtyIDKeyPrefix, &id_str))
492    return kInvalidTrackerID;
493
494  int64 tracker_id;
495  if (!base::StringToInt64(id_str, &tracker_id))
496    return kInvalidTrackerID;
497
498  return tracker_id;
499}
500
501void MetadataDatabaseIndexOnDisk::DemoteDirtyTracker(int64 tracker_id) {
502  const std::string key = GenerateDirtyIDKey(tracker_id);
503
504  std::string value;
505  leveldb::Status status = db_->Get(key, &value);
506  if (status.IsNotFound())
507    return;
508  if (!status.ok()) {
509    util::Log(logging::LOG_WARNING, FROM_HERE,
510              "LevelDB error (%s) in getting a dirty tracker for ID: %" PRId64,
511              status.ToString().c_str(),
512              tracker_id);
513    return;
514  }
515
516  db_->Delete(key);
517  db_->Put(GenerateDemotedDirtyIDKey(tracker_id), std::string());
518  --num_dirty_trackers_;
519}
520
521bool MetadataDatabaseIndexOnDisk::HasDemotedDirtyTracker() const {
522  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
523  itr->Seek(kDemotedDirtyIDKeyPrefix);
524  if (!itr->Valid())
525    return false;
526  return StartsWithASCII(itr->key().ToString(), kDemotedDirtyIDKeyPrefix, true);
527}
528
529void MetadataDatabaseIndexOnDisk::PromoteDemotedDirtyTracker(int64 tracker_id) {
530  std::string demoted_key = GenerateDemotedDirtyIDKey(tracker_id);
531
532  std::string empty;
533  if (db_->Get(demoted_key, &empty).ok()) {
534    db_->Delete(demoted_key);
535    db_->Put(GenerateDirtyIDKey(tracker_id), std::string());
536    ++num_dirty_trackers_;
537  }
538}
539
540bool MetadataDatabaseIndexOnDisk::PromoteDemotedDirtyTrackers() {
541  bool promoted = false;
542  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
543  for (itr->Seek(kDemotedDirtyIDKeyPrefix); itr->Valid(); itr->Next()) {
544    std::string id_str;
545    if (!RemovePrefix(itr->key().ToString(), kDemotedDirtyIDKeyPrefix, &id_str))
546      break;
547
548    int64 tracker_id;
549    if (!base::StringToInt64(id_str, &tracker_id))
550      continue;
551
552    db_->Delete(itr->key().ToString());
553    db_->Put(GenerateDirtyIDKey(tracker_id), std::string());
554    ++num_dirty_trackers_;
555    promoted = true;
556  }
557  return promoted;
558}
559
560size_t MetadataDatabaseIndexOnDisk::CountDirtyTracker() const {
561  return num_dirty_trackers_;
562}
563
564size_t MetadataDatabaseIndexOnDisk::CountFileMetadata() const {
565  // TODO(peria): Cache the number of FileMetadata in the DB.
566  size_t count = 0;
567  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
568  for (itr->Seek(kFileMetadataKeyPrefix); itr->Valid(); itr->Next()) {
569    if (!StartsWithASCII(itr->key().ToString(), kFileMetadataKeyPrefix, true))
570      break;
571    ++count;
572  }
573  return count;
574}
575
576size_t MetadataDatabaseIndexOnDisk::CountFileTracker() const {
577  // TODO(peria): Cache the number of FileTracker in the DB.
578  size_t count = 0;
579  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
580  for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) {
581    if (!StartsWithASCII(itr->key().ToString(), kFileTrackerKeyPrefix, true))
582      break;
583    ++count;
584  }
585  return count;
586}
587
588void MetadataDatabaseIndexOnDisk::SetSyncRootTrackerID(
589    int64 sync_root_id) const {
590  service_metadata_->set_sync_root_tracker_id(sync_root_id);
591  PutServiceMetadataToDB(*service_metadata_, db_);
592}
593
594void MetadataDatabaseIndexOnDisk::SetLargestChangeID(
595    int64 largest_change_id) const {
596  service_metadata_->set_largest_change_id(largest_change_id);
597  PutServiceMetadataToDB(*service_metadata_, db_);
598}
599
600void MetadataDatabaseIndexOnDisk::SetNextTrackerID(
601    int64 next_tracker_id) const {
602  service_metadata_->set_next_tracker_id(next_tracker_id);
603  PutServiceMetadataToDB(*service_metadata_, db_);
604}
605
606int64 MetadataDatabaseIndexOnDisk::GetSyncRootTrackerID() const {
607  if (!service_metadata_->has_sync_root_tracker_id())
608    return kInvalidTrackerID;
609  return service_metadata_->sync_root_tracker_id();
610}
611
612int64 MetadataDatabaseIndexOnDisk::GetLargestChangeID() const {
613  if (!service_metadata_->has_largest_change_id())
614    return kInvalidTrackerID;
615  return service_metadata_->largest_change_id();
616}
617
618int64 MetadataDatabaseIndexOnDisk::GetNextTrackerID() const {
619  if (!service_metadata_->has_next_tracker_id())
620    return kInvalidTrackerID;
621  return service_metadata_->next_tracker_id();
622}
623
624std::vector<std::string>
625MetadataDatabaseIndexOnDisk::GetRegisteredAppIDs() const {
626  std::vector<std::string> result;
627  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
628  for (itr->Seek(kAppRootIDByAppIDKeyPrefix); itr->Valid(); itr->Next()) {
629    std::string id;
630    if (!RemovePrefix(itr->key().ToString(), kAppRootIDByAppIDKeyPrefix, &id))
631      break;
632    result.push_back(id);
633  }
634  return result;
635}
636
637std::vector<int64> MetadataDatabaseIndexOnDisk::GetAllTrackerIDs() const {
638  std::vector<int64> tracker_ids;
639  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
640  for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) {
641    std::string id_str;
642    if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, &id_str))
643      break;
644
645    int64 tracker_id;
646    if (!base::StringToInt64(id_str, &tracker_id))
647      continue;
648    tracker_ids.push_back(tracker_id);
649  }
650  return tracker_ids;
651}
652
653std::vector<std::string>
654MetadataDatabaseIndexOnDisk::GetAllMetadataIDs() const {
655  std::vector<std::string> file_ids;
656  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
657  for (itr->Seek(kFileMetadataKeyPrefix); itr->Valid(); itr->Next()) {
658    std::string file_id;
659    if (!RemovePrefix(itr->key().ToString(), kFileMetadataKeyPrefix, &file_id))
660      break;
661    file_ids.push_back(file_id);
662  }
663  return file_ids;
664}
665
666int64 MetadataDatabaseIndexOnDisk::BuildTrackerIndexes() {
667  int64 num_puts_before = db_->num_puts();
668
669  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
670  for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) {
671    if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, NULL))
672      break;
673
674    FileTracker tracker;
675    if (!tracker.ParseFromString(itr->value().ToString())) {
676      util::Log(logging::LOG_WARNING, FROM_HERE,
677                "Failed to parse a Tracker");
678      continue;
679    }
680
681    AddToAppIDIndex(tracker);
682    AddToFileIDIndexes(tracker);
683    AddToPathIndexes(tracker);
684    AddToDirtyTrackerIndexes(tracker);
685  }
686
687  return db_->num_puts() - num_puts_before;
688}
689
690int64 MetadataDatabaseIndexOnDisk::DeleteTrackerIndexes() {
691  const char* kIndexPrefixes[] = {
692    kAppRootIDByAppIDKeyPrefix, kActiveTrackerIDByFileIDKeyPrefix,
693    kTrackerIDByFileIDKeyPrefix, kMultiTrackerByFileIDKeyPrefix,
694    kActiveTrackerIDByParentAndTitleKeyPrefix,
695    kTrackerIDByParentAndTitleKeyPrefix, kMultiBackingParentAndTitleKeyPrefix,
696    kDirtyIDKeyPrefix, kDemotedDirtyIDKeyPrefix
697  };
698
699  int64 num_deletes_before = db_->num_deletes();
700  for (size_t i = 0; i < arraysize(kIndexPrefixes); ++i)
701    DeleteKeyStartsWith(kIndexPrefixes[i]);
702  num_dirty_trackers_ = 0;
703  return db_->num_deletes() - num_deletes_before;
704}
705
706LevelDBWrapper* MetadataDatabaseIndexOnDisk::GetDBForTesting() {
707  return db_;
708}
709
710MetadataDatabaseIndexOnDisk::MetadataDatabaseIndexOnDisk(LevelDBWrapper* db)
711    : db_(db),
712      num_dirty_trackers_(0) {
713  // TODO(peria): Add UMA to measure the number of FileMetadata, FileTracker,
714  //    and AppRootId.
715  service_metadata_ = InitializeServiceMetadata(db_);
716
717  // Check if index is valid, if no validations run in 7 days.
718  const int64 kThresholdToValidateInDays = 7;
719
720  int64 last_check_time = 0;
721  std::string value;
722  if (db_->Get(kLastValidationTimeKey, &value).ok())
723    base::StringToInt64(value, &last_check_time);
724  base::TimeDelta since_last_check =
725      base::Time::Now() - base::Time::FromInternalValue(last_check_time);
726  int64 since_last_check_in_days = since_last_check.InDays();
727  if (since_last_check_in_days >= kThresholdToValidateInDays ||
728      since_last_check_in_days < 0) {
729    // TODO(peria): Add UMA to check if the number of deleted entries and the
730    // number of built entries are different or not.
731    DeleteTrackerIndexes();
732    BuildTrackerIndexes();
733    db_->Put(kLastValidationTimeKey,
734             base::Int64ToString(base::Time::Now().ToInternalValue()));
735  } else {
736    num_dirty_trackers_ = CountDirtyTrackerInternal();
737  }
738}
739
740void MetadataDatabaseIndexOnDisk::AddToAppIDIndex(const FileTracker& tracker) {
741  if (!IsAppRoot(tracker)) {
742    DVLOG(3) << "  Tracker for " << tracker.file_id() << " is not an App root.";
743    return;
744  }
745
746  DVLOG(1) << "  Add to App root by App ID: " << tracker.app_id();
747
748  const std::string db_key = GenerateAppRootIDByAppIDKey(tracker.app_id());
749  DCHECK(tracker.active());
750  DCHECK(!DBHasKey(db_key));
751  db_->Put(db_key, base::Int64ToString(tracker.tracker_id()));
752}
753
754void MetadataDatabaseIndexOnDisk::UpdateInAppIDIndex(
755    const FileTracker& old_tracker,
756    const FileTracker& new_tracker) {
757  DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id());
758
759  if (IsAppRoot(old_tracker) && !IsAppRoot(new_tracker)) {
760    DCHECK(old_tracker.active());
761    DCHECK(!new_tracker.active());
762    const std::string key = GenerateAppRootIDByAppIDKey(old_tracker.app_id());
763    DCHECK(DBHasKey(key));
764
765    DVLOG(1) << "  Remove from App root by App ID: " << old_tracker.app_id();
766    db_->Delete(key);
767  } else if (!IsAppRoot(old_tracker) && IsAppRoot(new_tracker)) {
768    DCHECK(!old_tracker.active());
769    DCHECK(new_tracker.active());
770    const std::string key = GenerateAppRootIDByAppIDKey(new_tracker.app_id());
771    DCHECK(!DBHasKey(key));
772
773    DVLOG(1) << "  Add to App root by App ID: " << new_tracker.app_id();
774    db_->Put(key, base::Int64ToString(new_tracker.tracker_id()));
775  }
776}
777
778void MetadataDatabaseIndexOnDisk::RemoveFromAppIDIndex(
779    const FileTracker& tracker) {
780  if (!IsAppRoot(tracker)) {
781    DVLOG(3) << "  Tracker for " << tracker.file_id() << " is not an App root.";
782    return;
783  }
784
785  DCHECK(tracker.active());
786  const std::string key = GenerateAppRootIDByAppIDKey(tracker.app_id());
787  DCHECK(DBHasKey(key));
788
789  DVLOG(1) << "  Remove from App root by App ID: " << tracker.app_id();
790  db_->Delete(key);
791}
792
793void MetadataDatabaseIndexOnDisk::AddToFileIDIndexes(
794    const FileTracker& new_tracker) {
795  const std::string& file_id = new_tracker.file_id();
796
797  DVLOG(1) << "  Add to trackers by file ID: " << file_id;
798  const std::string prefix = GenerateTrackerIDByFileIDKeyPrefix(file_id);
799  AddToTrackerIDSetWithPrefix(
800      GenerateActiveTrackerIDByFileIDKey(file_id), prefix, new_tracker);
801
802  const std::string multi_tracker_key = GenerateMultiTrackerKey(file_id);
803  if (!DBHasKey(multi_tracker_key) &&
804      CountWithPrefix(prefix, new_tracker.tracker_id()) != NONE) {
805    DVLOG(1) << "  Add to multi-tracker file IDs: " << file_id;
806    db_->Put(multi_tracker_key, std::string());
807  }
808}
809
810void MetadataDatabaseIndexOnDisk::UpdateInFileIDIndexes(
811    const FileTracker& old_tracker,
812    const FileTracker& new_tracker) {
813  DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id());
814  DCHECK_EQ(old_tracker.file_id(), new_tracker.file_id());
815
816  const std::string& file_id = new_tracker.file_id();
817  const std::string prefix = GenerateTrackerIDByFileIDKeyPrefix(file_id);
818  DCHECK(DBHasKey(prefix + base::Int64ToString(new_tracker.tracker_id())));
819
820  if (old_tracker.active() && !new_tracker.active()) {
821    DeactivateInTrackerIDSetWithPrefix(
822        GenerateActiveTrackerIDByFileIDKey(file_id), prefix,
823        new_tracker.tracker_id());
824  } else if (!old_tracker.active() && new_tracker.active()) {
825    ActivateInTrackerIDSetWithPrefix(
826        GenerateActiveTrackerIDByFileIDKey(file_id), prefix,
827        new_tracker.tracker_id());
828  }
829}
830
831void MetadataDatabaseIndexOnDisk::RemoveFromFileIDIndexes(
832    const FileTracker& tracker) {
833  const std::string& file_id = tracker.file_id();
834  const std::string prefix =
835      GenerateTrackerIDByFileIDKeyPrefix(file_id);
836
837  if (!EraseInTrackerIDSetWithPrefix(
838          GenerateActiveTrackerIDByFileIDKey(file_id),
839          prefix, tracker.tracker_id()))
840    return;
841
842  DVLOG(1) << "  Remove from trackers by file ID: " << tracker.tracker_id();
843
844  const std::string multi_key = GenerateMultiTrackerKey(file_id);
845  if (DBHasKey(multi_key) &&
846      CountWithPrefix(prefix, tracker.tracker_id()) != MULTIPLE) {
847    DVLOG(1) << "  Remove from multi-tracker file IDs: " << file_id;
848    db_->Delete(multi_key);
849  }
850}
851
852void MetadataDatabaseIndexOnDisk::AddToPathIndexes(
853    const FileTracker& new_tracker) {
854  int64 parent_id = new_tracker.parent_tracker_id();
855  std::string title = GetTrackerTitle(new_tracker);
856
857  DVLOG(1) << "  Add to trackers by parent and title: "
858           << parent_id << " " << title;
859
860  const std::string prefix =
861      GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title);
862  if (!title.empty()) {
863    scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
864    for (itr->Seek(prefix); itr->Valid(); itr->Next()) {
865      std::string id_str;
866      if (!RemovePrefix(itr->key().ToString(), prefix, &id_str))
867        break;
868
869      int64 tracker_id;
870      if (!base::StringToInt64(id_str, &tracker_id))
871        continue;
872      if (tracker_id == new_tracker.tracker_id()) {
873        NOTREACHED();
874        continue;
875      }
876
877      const std::string multi_key =
878          GenerateMultiBackingParentAndTitleKey(parent_id, title);
879      DVLOG_IF(1, !DBHasKey(multi_key))
880          << "  Add to multi backing file paths: " << parent_id << " " << title;
881      db_->Put(multi_key, std::string());
882      break;
883    }
884  }
885
886  AddToTrackerIDSetWithPrefix(
887      GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title),
888      prefix, new_tracker);
889}
890
891void MetadataDatabaseIndexOnDisk::UpdateInPathIndexes(
892    const FileTracker& old_tracker,
893    const FileTracker& new_tracker) {
894  DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id());
895  DCHECK_EQ(old_tracker.parent_tracker_id(), new_tracker.parent_tracker_id());
896  DCHECK(GetTrackerTitle(old_tracker) == GetTrackerTitle(new_tracker) ||
897         !old_tracker.has_synced_details());
898
899  int64 tracker_id = new_tracker.tracker_id();
900  int64 parent_id = new_tracker.parent_tracker_id();
901  const std::string old_title = GetTrackerTitle(old_tracker);
902  const std::string title = GetTrackerTitle(new_tracker);
903
904  if (old_title != title) {
905    const std::string old_prefix =
906        GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, old_title);
907    EraseInTrackerIDSetWithPrefix(
908        GenerateActiveTrackerIDByParentAndTitleKey(parent_id, old_title),
909        old_prefix, tracker_id);
910
911    if (!old_title.empty() &&
912        CountWithPrefix(old_prefix, tracker_id) != MULTIPLE) {
913      const std::string old_multi_backing_key =
914          GenerateMultiBackingParentAndTitleKey(parent_id, old_title);
915      DVLOG_IF(1, DBHasKey(old_multi_backing_key))
916          << "  Remove from multi backing file paths: "
917          << parent_id << " " << old_title;
918      db_->Delete(old_multi_backing_key);
919    }
920
921    DVLOG(1) << "  Add to trackers by parent and title: "
922             << parent_id << " " << title;
923
924    const std::string prefix =
925        GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title);
926    AddToTrackerIDSetWithPrefix(
927        GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title),
928        prefix, new_tracker);
929
930    if (!title.empty() && CountWithPrefix(prefix, tracker_id) != NONE) {
931      const std::string multi_backing_key =
932          GenerateMultiBackingParentAndTitleKey(parent_id, title);
933      DVLOG_IF(1, !DBHasKey(multi_backing_key))
934          << "  Add to multi backing file_paths: "
935          << parent_id << " " << title;
936      db_->Put(multi_backing_key, std::string());
937    }
938
939    return;
940  }
941
942  const std::string active_tracker_key =
943      GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title);
944  const std::string prefix =
945      GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title);
946  if (old_tracker.active() && !new_tracker.active()) {
947    DeactivateInTrackerIDSetWithPrefix(
948        active_tracker_key, prefix, tracker_id);
949  } else if (!old_tracker.active() && new_tracker.active()) {
950    ActivateInTrackerIDSetWithPrefix(
951        active_tracker_key, prefix, tracker_id);
952  }
953}
954
955void MetadataDatabaseIndexOnDisk::RemoveFromPathIndexes(
956    const FileTracker& tracker) {
957  int64 tracker_id = tracker.tracker_id();
958  int64 parent_id = tracker.parent_tracker_id();
959  std::string title = GetTrackerTitle(tracker);
960
961  DVLOG(1) << "  Remove from trackers by parent and title: "
962           << parent_id << " " << title;
963
964  const std::string active_tracker_key =
965      GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title);
966  const std::string key_prefix =
967      GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title);
968  if (!EraseInTrackerIDSetWithPrefix(
969          active_tracker_key, key_prefix, tracker_id))
970    return;
971
972  const std::string multi_key =
973      GenerateMultiBackingParentAndTitleKey(parent_id, title);
974  if (!title.empty() && DBHasKey(multi_key) &&
975      CountWithPrefix(key_prefix, tracker_id) != MULTIPLE) {
976    DVLOG(1) << "  Remove from multi backing file paths: "
977             << parent_id << " " << title;
978    db_->Delete(multi_key);
979  }
980}
981
982void MetadataDatabaseIndexOnDisk::AddToDirtyTrackerIndexes(
983    const FileTracker& new_tracker) {
984  const std::string dirty_key = GenerateDirtyIDKey(new_tracker.tracker_id());
985  DCHECK(!DBHasKey(dirty_key));
986  DCHECK(!DBHasKey(GenerateDemotedDirtyIDKey(new_tracker.tracker_id())));
987
988  if (new_tracker.dirty()) {
989    DVLOG(1) << "  Add to dirty tracker IDs: " << new_tracker.tracker_id();
990    db_->Put(dirty_key, std::string());
991    ++num_dirty_trackers_;
992  }
993}
994
995void MetadataDatabaseIndexOnDisk::UpdateInDirtyTrackerIndexes(
996    const FileTracker& old_tracker,
997    const FileTracker& new_tracker) {
998  DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id());
999
1000  int64 tracker_id = new_tracker.tracker_id();
1001  const std::string dirty_key = GenerateDirtyIDKey(tracker_id);
1002  const std::string demoted_key = GenerateDemotedDirtyIDKey(tracker_id);
1003  if (old_tracker.dirty() && !new_tracker.dirty()) {
1004    DCHECK(DBHasKey(dirty_key) || DBHasKey(demoted_key));
1005
1006    DVLOG(1) << "  Remove from dirty trackers IDs: " << tracker_id;
1007
1008    if (DBHasKey(dirty_key))
1009      --num_dirty_trackers_;
1010    db_->Delete(dirty_key);
1011    db_->Delete(demoted_key);
1012  } else if (!old_tracker.dirty() && new_tracker.dirty()) {
1013    DCHECK(!DBHasKey(dirty_key));
1014    DCHECK(!DBHasKey(demoted_key));
1015
1016    DVLOG(1) << "  Add to dirty tracker IDs: " << tracker_id;
1017
1018    db_->Put(dirty_key, std::string());
1019    ++num_dirty_trackers_;
1020  }
1021}
1022
1023void MetadataDatabaseIndexOnDisk::RemoveFromDirtyTrackerIndexes(
1024    const FileTracker& tracker) {
1025  if (tracker.dirty()) {
1026    int64 tracker_id = tracker.tracker_id();
1027    const std::string dirty_key = GenerateDirtyIDKey(tracker_id);
1028    const std::string demoted_key = GenerateDemotedDirtyIDKey(tracker_id);
1029    DCHECK(DBHasKey(dirty_key) || DBHasKey(demoted_key));
1030
1031    DVLOG(1) << "  Remove from dirty tracker IDs: " << tracker_id;
1032    if (DBHasKey(dirty_key))
1033      --num_dirty_trackers_;
1034    db_->Delete(dirty_key);
1035    db_->Delete(demoted_key);
1036  }
1037}
1038
1039TrackerIDSet MetadataDatabaseIndexOnDisk::GetTrackerIDSetByPrefix(
1040    const std::string& active_tracker_key,
1041    const std::string& ids_prefix) const {
1042  TrackerIDSet trackers;
1043
1044  // Seek IDs.
1045  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
1046  for (itr->Seek(ids_prefix); itr->Valid(); itr->Next()) {
1047    const std::string& key(itr->key().ToString());
1048    std::string id_str;
1049    if (!RemovePrefix(key, ids_prefix, &id_str))
1050      break;
1051
1052    int64 tracker_id;
1053    if (!base::StringToInt64(id_str, &tracker_id))
1054      continue;
1055    trackers.InsertInactiveTracker(tracker_id);
1056  }
1057
1058  // Set an active tracker ID, if available.
1059  std::string value;
1060  leveldb::Status status = db_->Get(active_tracker_key, &value);
1061  int64 active_tracker;
1062  if (status.ok() && base::StringToInt64(value, &active_tracker)) {
1063    DCHECK_NE(kInvalidTrackerID, active_tracker);
1064    trackers.Activate(active_tracker);
1065  }
1066
1067  return trackers;
1068}
1069
1070void MetadataDatabaseIndexOnDisk::AddToTrackerIDSetWithPrefix(
1071    const std::string& active_tracker_key, const std::string& key_prefix,
1072    const FileTracker& tracker) {
1073  DCHECK(tracker.tracker_id());
1074
1075  const std::string id_str = base::Int64ToString(tracker.tracker_id());
1076  db_->Put(key_prefix + id_str, std::string());
1077  if (tracker.active())
1078    db_->Put(active_tracker_key, id_str);
1079}
1080
1081bool MetadataDatabaseIndexOnDisk::EraseInTrackerIDSetWithPrefix(
1082    const std::string& active_tracker_key, const std::string& key_prefix,
1083    int64 tracker_id) {
1084  std::string value;
1085  const std::string del_key = key_prefix + base::Int64ToString(tracker_id);
1086  leveldb::Status status = db_->Get(del_key, &value);
1087  if (status.IsNotFound())
1088    return false;
1089
1090  db_->Delete(del_key);
1091
1092  status = db_->Get(active_tracker_key, &value);
1093  int64 active_tracker_id;
1094  if (status.ok() && base::StringToInt64(value, &active_tracker_id) &&
1095      active_tracker_id == tracker_id) {
1096    db_->Delete(active_tracker_key);
1097  }
1098
1099  return true;
1100}
1101
1102void MetadataDatabaseIndexOnDisk::ActivateInTrackerIDSetWithPrefix(
1103    const std::string& active_tracker_key, const std::string& key_prefix,
1104    int64 tracker_id) {
1105  DCHECK(DBHasKey(key_prefix + base::Int64ToString(tracker_id)));
1106
1107  std::string value;
1108  leveldb::Status status = db_->Get(active_tracker_key, &value);
1109  int64 active_tracker_id = kInvalidTrackerID;
1110  if (status.IsNotFound() ||
1111      (status.ok() && base::StringToInt64(value, &active_tracker_id))) {
1112    DCHECK(active_tracker_id != tracker_id);
1113    db_->Put(active_tracker_key, base::Int64ToString(tracker_id));
1114  }
1115}
1116
1117void MetadataDatabaseIndexOnDisk::DeactivateInTrackerIDSetWithPrefix(
1118    const std::string& active_tracker_key, const std::string& key_prefix,
1119    int64 tracker_id) {
1120  DCHECK(DBHasKey(key_prefix + base::Int64ToString(tracker_id)));
1121
1122  std::string value;
1123  leveldb::Status status = db_->Get(active_tracker_key, &value);
1124  int64 active_tracker_id;
1125  if (status.ok() && base::StringToInt64(value, &active_tracker_id)) {
1126    DCHECK(active_tracker_id == tracker_id);
1127    db_->Delete(active_tracker_key);
1128  }
1129}
1130
1131bool MetadataDatabaseIndexOnDisk::DBHasKey(const std::string& key) {
1132  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
1133  itr->Seek(key);
1134  return itr->Valid() && (itr->key() == key);
1135}
1136
1137size_t MetadataDatabaseIndexOnDisk::CountDirtyTrackerInternal() const {
1138  size_t num_dirty_trackers = 0;
1139
1140  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
1141  for (itr->Seek(kDirtyIDKeyPrefix); itr->Valid(); itr->Next()) {
1142    if (!StartsWithASCII(itr->key().ToString(), kDirtyIDKeyPrefix, true))
1143      break;
1144    ++num_dirty_trackers;
1145  }
1146
1147  return num_dirty_trackers;
1148}
1149
1150MetadataDatabaseIndexOnDisk::NumEntries
1151MetadataDatabaseIndexOnDisk::CountWithPrefix(
1152    const std::string& prefix, int64 ignored_id) {
1153  const std::string ignored = base::Int64ToString(ignored_id);
1154
1155  size_t count = 0;
1156  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
1157  for (itr->Seek(prefix); itr->Valid() && count <= 1; itr->Next()) {
1158    std::string value;
1159    if (!RemovePrefix(itr->key().ToString(), prefix, &value))
1160      break;
1161    if (value == ignored)
1162      continue;
1163
1164    ++count;
1165  }
1166
1167  if (count >= 2)
1168    return MULTIPLE;
1169  return count == 0 ? NONE : SINGLE;
1170}
1171
1172void MetadataDatabaseIndexOnDisk::DeleteKeyStartsWith(
1173    const std::string& prefix) {
1174  scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator());
1175  for (itr->Seek(prefix); itr->Valid();) {
1176    const std::string key = itr->key().ToString();
1177    if (!StartsWithASCII(key, prefix, true))
1178      break;
1179    itr->Delete();
1180  }
1181}
1182
1183}  // namespace drive_backend
1184}  // namespace sync_file_system
1185