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