components/drive/resource_metadata_storage.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "components/drive/resource_metadata_storage.h"
   6
   7 #include <map>
   8 #include <set>
   9
  10 #include "base/bind.h"
  11 #include "base/containers/hash_tables.h"
  12 #include "base/files/file_util.h"
  13 #include "base/location.h"
  14 #include "base/logging.h"
  15 #include "base/metrics/histogram.h"
  16 #include "base/metrics/sparse_histogram.h"
  17 #include "base/sequenced_task_runner.h"
  18 #include "base/threading/thread_restrictions.h"
  19 #include "components/drive/drive.pb.h"
  20 #include "components/drive/drive_api_util.h"
  21 #include "third_party/leveldatabase/env_chromium.h"
  22 #include "third_party/leveldatabase/src/include/leveldb/db.h"
  23 #include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
  24
  25 namespace drive {
  26 namespace internal {
  27
  28 namespace {
  29
  30 // Enum to describe DB initialization status.
  31 enum DBInitStatus {
  32   DB_INIT_SUCCESS,
  33   DB_INIT_NOT_FOUND,
  34   DB_INIT_CORRUPTION,
  35   DB_INIT_IO_ERROR,
  36   DB_INIT_FAILED,
  37   DB_INIT_INCOMPATIBLE,
  38   DB_INIT_BROKEN,
  39   DB_INIT_OPENED_EXISTING_DB,
  40   DB_INIT_CREATED_NEW_DB,
  41   DB_INIT_REPLACED_EXISTING_DB_WITH_NEW_DB,
  42   DB_INIT_MAX_VALUE,
  43 };
  44
  45 // Enum to describe DB validity check failure reason.
  46 enum CheckValidityFailureReason {
  47   CHECK_VALIDITY_FAILURE_INVALID_HEADER,
  48   CHECK_VALIDITY_FAILURE_BROKEN_ID_ENTRY,
  49   CHECK_VALIDITY_FAILURE_BROKEN_ENTRY,
  50   CHECK_VALIDITY_FAILURE_INVALID_LOCAL_ID,
  51   CHECK_VALIDITY_FAILURE_INVALID_PARENT_ID,
  52   CHECK_VALIDITY_FAILURE_BROKEN_CHILD_MAP,
  53   CHECK_VALIDITY_FAILURE_CHILD_ENTRY_COUNT_MISMATCH,
  54   CHECK_VALIDITY_FAILURE_ITERATOR_ERROR,
  55   CHECK_VALIDITY_FAILURE_MAX_VALUE,
  56 };
  57
  58 // The name of the DB which stores the metadata.
  59 const base::FilePath::CharType kResourceMapDBName[] =
  60     FILE_PATH_LITERAL("resource_metadata_resource_map.db");
  61
  62 // The name of the DB which couldn't be opened, but is preserved just in case.
  63 const base::FilePath::CharType kPreservedResourceMapDBName[] =
  64     FILE_PATH_LITERAL("resource_metadata_preserved_resource_map.db");
  65
  66 // The name of the DB which couldn't be opened, and was replaced with a new one.
  67 const base::FilePath::CharType kTrashedResourceMapDBName[] =
  68     FILE_PATH_LITERAL("resource_metadata_trashed_resource_map.db");
  69
  70 // Meant to be a character which never happen to be in real IDs.
  71 const char kDBKeyDelimeter = '\0';
  72
  73 // String used as a suffix of a key for a cache entry.
  74 const char kCacheEntryKeySuffix[] = "CACHE";
  75
  76 // String used as a prefix of a key for a resource-ID-to-local-ID entry.
  77 const char kIdEntryKeyPrefix[] = "ID";
  78
  79 // Returns a string to be used as the key for the header.
  80 std::string GetHeaderDBKey() {
  81   std::string key;
  82   key.push_back(kDBKeyDelimeter);
  83   key.append("HEADER");
  84   return key;
  85 }
  86
  87 // Returns true if |key| is a key for a child entry.
  88 bool IsChildEntryKey(const leveldb::Slice& key) {
  89   return !key.empty() && key[key.size() - 1] == kDBKeyDelimeter;
  90 }
  91
  92 // Returns true if |key| is a key for a cache entry.
  93 bool IsCacheEntryKey(const leveldb::Slice& key) {
  94   // A cache entry key should end with |kDBKeyDelimeter + kCacheEntryKeySuffix|.
  95   const leveldb::Slice expected_suffix(kCacheEntryKeySuffix,
  96                                        arraysize(kCacheEntryKeySuffix) - 1);
  97   if (key.size() < 1 + expected_suffix.size() ||
  98       key[key.size() - expected_suffix.size() - 1] != kDBKeyDelimeter)
  99     return false;
 100
 101   const leveldb::Slice key_substring(
 102       key.data() + key.size() - expected_suffix.size(), expected_suffix.size());
 103   return key_substring.compare(expected_suffix) == 0;
 104 }
 105
 106 // Returns ID extracted from a cache entry key.
 107 std::string GetIdFromCacheEntryKey(const leveldb::Slice& key) {
 108   DCHECK(IsCacheEntryKey(key));
 109   // Drop the suffix |kDBKeyDelimeter + kCacheEntryKeySuffix| from the key.
 110   const size_t kSuffixLength = arraysize(kCacheEntryKeySuffix) - 1;
 111   const int id_length = key.size() - 1 - kSuffixLength;
 112   return std::string(key.data(), id_length);
 113 }
 114
 115 // Returns a string to be used as a key for a resource-ID-to-local-ID entry.
 116 std::string GetIdEntryKey(const std::string& resource_id) {
 117   std::string key;
 118   key.push_back(kDBKeyDelimeter);
 119   key.append(kIdEntryKeyPrefix);
 120   key.push_back(kDBKeyDelimeter);
 121   key.append(resource_id);
 122   return key;
 123 }
 124
 125 // Returns true if |key| is a key for a resource-ID-to-local-ID entry.
 126 bool IsIdEntryKey(const leveldb::Slice& key) {
 127   // A resource-ID-to-local-ID entry key should start with
 128   // |kDBKeyDelimeter + kIdEntryKeyPrefix + kDBKeyDelimeter|.
 129   const leveldb::Slice expected_prefix(kIdEntryKeyPrefix,
 130                                        arraysize(kIdEntryKeyPrefix) - 1);
 131   if (key.size() < 2 + expected_prefix.size())
 132     return false;
 133   const leveldb::Slice key_substring(key.data() + 1, expected_prefix.size());
 134   return key[0] == kDBKeyDelimeter &&
 135       key_substring.compare(expected_prefix) == 0 &&
 136       key[expected_prefix.size() + 1] == kDBKeyDelimeter;
 137 }
 138
 139 // Returns the resource ID extracted from a resource-ID-to-local-ID entry key.
 140 std::string GetResourceIdFromIdEntryKey(const leveldb::Slice& key) {
 141   DCHECK(IsIdEntryKey(key));
 142   // Drop the prefix |kDBKeyDelimeter + kIdEntryKeyPrefix + kDBKeyDelimeter|
 143   // from the key.
 144   const size_t kPrefixLength = arraysize(kIdEntryKeyPrefix) - 1;
 145   const int offset = kPrefixLength + 2;
 146   return std::string(key.data() + offset, key.size() - offset);
 147 }
 148
 149 // Converts leveldb::Status to DBInitStatus.
 150 DBInitStatus LevelDBStatusToDBInitStatus(const leveldb::Status& status) {
 151   if (status.ok())
 152     return DB_INIT_SUCCESS;
 153   if (status.IsNotFound())
 154     return DB_INIT_NOT_FOUND;
 155   if (status.IsCorruption())
 156     return DB_INIT_CORRUPTION;
 157   if (status.IsIOError())
 158     return DB_INIT_IO_ERROR;
 159   return DB_INIT_FAILED;
 160 }
 161
 162 // Converts leveldb::Status to FileError.
 163 FileError LevelDBStatusToFileError(const leveldb::Status& status) {
 164   if (status.ok())
 165     return FILE_ERROR_OK;
 166   if (status.IsNotFound())
 167     return FILE_ERROR_NOT_FOUND;
 168   if (leveldb_env::IndicatesDiskFull(status))
 169     return FILE_ERROR_NO_LOCAL_SPACE;
 170   return FILE_ERROR_FAILED;
 171 }
 172
 173 ResourceMetadataHeader GetDefaultHeaderEntry() {
 174   ResourceMetadataHeader header;
 175   header.set_version(ResourceMetadataStorage::kDBVersion);
 176   return header;
 177 }
 178
 179 bool MoveIfPossible(const base::FilePath& from, const base::FilePath& to) {
 180   return !base::PathExists(from) || base::Move(from, to);
 181 }
 182
 183 void RecordCheckValidityFailure(CheckValidityFailureReason reason) {
 184   UMA_HISTOGRAM_ENUMERATION("Drive.MetadataDBValidityCheckFailureReason",
 185                             reason,
 186                             CHECK_VALIDITY_FAILURE_MAX_VALUE);
 187 }
 188
 189 }  // namespace
 190
 191 ResourceMetadataStorage::Iterator::Iterator(scoped_ptr<leveldb::Iterator> it)
 192   : it_(it.Pass()) {
 193   base::ThreadRestrictions::AssertIOAllowed();
 194   DCHECK(it_);
 195
 196   // Skip the header entry.
 197   // Note: The header entry comes before all other entries because its key
 198   // starts with kDBKeyDelimeter. (i.e. '\0')
 199   it_->Seek(leveldb::Slice(GetHeaderDBKey()));
 200
 201   Advance();
 202 }
 203
 204 ResourceMetadataStorage::Iterator::~Iterator() {
 205   base::ThreadRestrictions::AssertIOAllowed();
 206 }
 207
 208 bool ResourceMetadataStorage::Iterator::IsAtEnd() const {
 209   base::ThreadRestrictions::AssertIOAllowed();
 210   return !it_->Valid();
 211 }
 212
 213 std::string ResourceMetadataStorage::Iterator::GetID() const {
 214   return it_->key().ToString();
 215 }
 216
 217 const ResourceEntry& ResourceMetadataStorage::Iterator::GetValue() const {
 218   base::ThreadRestrictions::AssertIOAllowed();
 219   DCHECK(!IsAtEnd());
 220   return entry_;
 221 }
 222
 223 void ResourceMetadataStorage::Iterator::Advance() {
 224   base::ThreadRestrictions::AssertIOAllowed();
 225   DCHECK(!IsAtEnd());
 226
 227   for (it_->Next() ; it_->Valid(); it_->Next()) {
 228     if (!IsChildEntryKey(it_->key()) &&
 229         !IsIdEntryKey(it_->key()) &&
 230         entry_.ParseFromArray(it_->value().data(), it_->value().size())) {
 231       break;
 232     }
 233   }
 234 }
 235
 236 bool ResourceMetadataStorage::Iterator::HasError() const {
 237   base::ThreadRestrictions::AssertIOAllowed();
 238   return !it_->status().ok();
 239 }
 240
 241 // static
 242 bool ResourceMetadataStorage::UpgradeOldDB(
 243     const base::FilePath& directory_path) {
 244   base::ThreadRestrictions::AssertIOAllowed();
 245   static_assert(
 246       kDBVersion == 13,
 247       "database version and this function must be updated at the same time");
 248
 249   const base::FilePath resource_map_path =
 250       directory_path.Append(kResourceMapDBName);
 251   const base::FilePath preserved_resource_map_path =
 252       directory_path.Append(kPreservedResourceMapDBName);
 253
 254   if (base::PathExists(preserved_resource_map_path)) {
 255     // Preserved DB is found. The previous attempt to create a new DB should not
 256     // be successful. Discard the imperfect new DB and restore the old DB.
 257     if (!base::DeleteFile(resource_map_path, false /* recursive */) ||
 258         !base::Move(preserved_resource_map_path, resource_map_path))
 259       return false;
 260   }
 261
 262   if (!base::PathExists(resource_map_path))
 263     return false;
 264
 265   // Open DB.
 266   leveldb::DB* db = NULL;
 267   leveldb::Options options;
 268   options.max_open_files = 0;  // Use minimum.
 269   options.create_if_missing = false;
 270   options.reuse_logs = leveldb_env::kDefaultLogReuseOptionValue;
 271   if (!leveldb::DB::Open(options, resource_map_path.AsUTF8Unsafe(), &db).ok())
 272     return false;
 273   scoped_ptr<leveldb::DB> resource_map(db);
 274
 275   // Check DB version.
 276   std::string serialized_header;
 277   ResourceMetadataHeader header;
 278   if (!resource_map->Get(leveldb::ReadOptions(),
 279                          leveldb::Slice(GetHeaderDBKey()),
 280                          &serialized_header).ok() ||
 281       !header.ParseFromString(serialized_header))
 282     return false;
 283   UMA_HISTOGRAM_SPARSE_SLOWLY("Drive.MetadataDBVersionBeforeUpgradeCheck",
 284                               header.version());
 285
 286   if (header.version() == kDBVersion) {
 287     // Before r272134, UpgradeOldDB() was not deleting unused ID entries.
 288     // Delete unused ID entries to fix crbug.com/374648.
 289     std::set<std::string> used_ids;
 290
 291     scoped_ptr<leveldb::Iterator> it(
 292         resource_map->NewIterator(leveldb::ReadOptions()));
 293     it->Seek(leveldb::Slice(GetHeaderDBKey()));
 294     it->Next();
 295     for (; it->Valid(); it->Next()) {
 296       if (IsCacheEntryKey(it->key())) {
 297         used_ids.insert(GetIdFromCacheEntryKey(it->key()));
 298       } else if (!IsChildEntryKey(it->key()) && !IsIdEntryKey(it->key())) {
 299         used_ids.insert(it->key().ToString());
 300       }
 301     }
 302     if (!it->status().ok())
 303       return false;
 304
 305     leveldb::WriteBatch batch;
 306     for (it->SeekToFirst(); it->Valid(); it->Next()) {
 307       if (IsIdEntryKey(it->key()) && !used_ids.count(it->value().ToString()))
 308         batch.Delete(it->key());
 309     }
 310     if (!it->status().ok())
 311       return false;
 312
 313     return resource_map->Write(leveldb::WriteOptions(), &batch).ok();
 314   } else if (header.version() < 6) {  // Too old, nothing can be done.
 315     return false;
 316   } else if (header.version() < 11) {  // Cache entries can be reused.
 317     leveldb::ReadOptions options;
 318     options.verify_checksums = true;
 319     scoped_ptr<leveldb::Iterator> it(resource_map->NewIterator(options));
 320
 321     leveldb::WriteBatch batch;
 322     // First, remove all entries.
 323     for (it->SeekToFirst(); it->Valid(); it->Next())
 324       batch.Delete(it->key());
 325
 326     // Put ID entries and cache entries.
 327     for (it->SeekToFirst(); it->Valid(); it->Next()) {
 328       if (IsCacheEntryKey(it->key())) {
 329         FileCacheEntry cache_entry;
 330         if (!cache_entry.ParseFromArray(it->value().data(), it->value().size()))
 331           return false;
 332
 333         // The resource ID might be in old WAPI format. We need to canonicalize
 334         // to the format of API service currently in use.
 335         const std::string& id = GetIdFromCacheEntryKey(it->key());
 336         const std::string& id_new = util::CanonicalizeResourceId(id);
 337
 338         // Before v11, resource ID was directly used as local ID. Such entries
 339         // can be migrated by adding an identity ID mapping.
 340         batch.Put(GetIdEntryKey(id_new), id_new);
 341
 342         // Put cache state into a ResourceEntry.
 343         ResourceEntry entry;
 344         entry.set_local_id(id_new);
 345         entry.set_resource_id(id_new);
 346         *entry.mutable_file_specific_info()->mutable_cache_state() =
 347             cache_entry;
 348
 349         std::string serialized_entry;
 350         if (!entry.SerializeToString(&serialized_entry)) {
 351           DLOG(ERROR) << "Failed to serialize the entry: " << id;
 352           return false;
 353         }
 354         batch.Put(id_new, serialized_entry);
 355       }
 356     }
 357     if (!it->status().ok())
 358       return false;
 359
 360     // Put header with the latest version number.
 361     std::string serialized_header;
 362     if (!GetDefaultHeaderEntry().SerializeToString(&serialized_header))
 363       return false;
 364     batch.Put(GetHeaderDBKey(), serialized_header);
 365
 366     return resource_map->Write(leveldb::WriteOptions(), &batch).ok();
 367   } else if (header.version() < 12) {  // Cache and ID map entries are reusable.
 368     leveldb::ReadOptions options;
 369     options.verify_checksums = true;
 370     scoped_ptr<leveldb::Iterator> it(resource_map->NewIterator(options));
 371
 372     // First, get the set of local IDs associated with cache entries.
 373     std::set<std::string> cached_entry_ids;
 374     for (it->SeekToFirst(); it->Valid(); it->Next()) {
 375       if (IsCacheEntryKey(it->key()))
 376         cached_entry_ids.insert(GetIdFromCacheEntryKey(it->key()));
 377     }
 378     if (!it->status().ok())
 379       return false;
 380
 381     // Remove all entries except used ID entries.
 382     leveldb::WriteBatch batch;
 383     std::map<std::string, std::string> local_id_to_resource_id;
 384     for (it->SeekToFirst(); it->Valid(); it->Next()) {
 385       const bool is_used_id = IsIdEntryKey(it->key()) &&
 386           cached_entry_ids.count(it->value().ToString());
 387       if (is_used_id) {
 388         local_id_to_resource_id[it->value().ToString()] =
 389             GetResourceIdFromIdEntryKey(it->key());
 390       } else {
 391         batch.Delete(it->key());
 392       }
 393     }
 394     if (!it->status().ok())
 395       return false;
 396
 397     // Put cache entries.
 398     for (it->SeekToFirst(); it->Valid(); it->Next()) {
 399       if (IsCacheEntryKey(it->key())) {
 400         const std::string& id = GetIdFromCacheEntryKey(it->key());
 401
 402         std::map<std::string, std::string>::const_iterator iter_resource_id =
 403             local_id_to_resource_id.find(id);
 404         if (iter_resource_id == local_id_to_resource_id.end())
 405           continue;
 406
 407         FileCacheEntry cache_entry;
 408         if (!cache_entry.ParseFromArray(it->value().data(), it->value().size()))
 409           return false;
 410
 411         // Put cache state into a ResourceEntry.
 412         ResourceEntry entry;
 413         entry.set_local_id(id);
 414         entry.set_resource_id(iter_resource_id->second);
 415         *entry.mutable_file_specific_info()->mutable_cache_state() =
 416             cache_entry;
 417
 418         std::string serialized_entry;
 419         if (!entry.SerializeToString(&serialized_entry)) {
 420           DLOG(ERROR) << "Failed to serialize the entry: " << id;
 421           return false;
 422         }
 423         batch.Put(id, serialized_entry);
 424       }
 425     }
 426     if (!it->status().ok())
 427       return false;
 428
 429     // Put header with the latest version number.
 430     std::string serialized_header;
 431     if (!GetDefaultHeaderEntry().SerializeToString(&serialized_header))
 432       return false;
 433     batch.Put(GetHeaderDBKey(), serialized_header);
 434
 435     return resource_map->Write(leveldb::WriteOptions(), &batch).ok();
 436   } else if (header.version() < 13) {  // Reuse all entries.
 437     leveldb::ReadOptions options;
 438     options.verify_checksums = true;
 439     scoped_ptr<leveldb::Iterator> it(resource_map->NewIterator(options));
 440
 441     // First, get local ID to resource ID map.
 442     std::map<std::string, std::string> local_id_to_resource_id;
 443     for (it->SeekToFirst(); it->Valid(); it->Next()) {
 444       if (IsIdEntryKey(it->key())) {
 445         local_id_to_resource_id[it->value().ToString()] =
 446             GetResourceIdFromIdEntryKey(it->key());
 447       }
 448     }
 449     if (!it->status().ok())
 450       return false;
 451
 452     leveldb::WriteBatch batch;
 453     // Merge cache entries to ResourceEntry.
 454     for (it->SeekToFirst(); it->Valid(); it->Next()) {
 455       if (IsCacheEntryKey(it->key())) {
 456         const std::string& id = GetIdFromCacheEntryKey(it->key());
 457
 458         FileCacheEntry cache_entry;
 459         if (!cache_entry.ParseFromArray(it->value().data(), it->value().size()))
 460           return false;
 461
 462         std::string serialized_entry;
 463         leveldb::Status status = resource_map->Get(options,
 464                                                    leveldb::Slice(id),
 465                                                    &serialized_entry);
 466
 467         std::map<std::string, std::string>::const_iterator iter_resource_id =
 468             local_id_to_resource_id.find(id);
 469
 470         // No need to keep cache-only entries without resource ID.
 471         if (status.IsNotFound() &&
 472             iter_resource_id == local_id_to_resource_id.end())
 473           continue;
 474
 475         ResourceEntry entry;
 476         if (status.ok()) {
 477           if (!entry.ParseFromString(serialized_entry))
 478             return false;
 479         } else if (status.IsNotFound()) {
 480           entry.set_local_id(id);
 481           entry.set_resource_id(iter_resource_id->second);
 482         } else {
 483           DLOG(ERROR) << "Failed to get the entry: " << id;
 484           return false;
 485         }
 486         *entry.mutable_file_specific_info()->mutable_cache_state() =
 487             cache_entry;
 488
 489         if (!entry.SerializeToString(&serialized_entry)) {
 490           DLOG(ERROR) << "Failed to serialize the entry: " << id;
 491           return false;
 492         }
 493         batch.Delete(it->key());
 494         batch.Put(id, serialized_entry);
 495       }
 496     }
 497     if (!it->status().ok())
 498       return false;
 499
 500     // Put header with the latest version number.
 501     header.set_version(ResourceMetadataStorage::kDBVersion);
 502     std::string serialized_header;
 503     if (!header.SerializeToString(&serialized_header))
 504       return false;
 505     batch.Put(GetHeaderDBKey(), serialized_header);
 506
 507     return resource_map->Write(leveldb::WriteOptions(), &batch).ok();
 508   }
 509
 510   LOG(WARNING) << "Unexpected DB version: " << header.version();
 511   return false;
 512 }
 513
 514 ResourceMetadataStorage::ResourceMetadataStorage(
 515     const base::FilePath& directory_path,
 516     base::SequencedTaskRunner* blocking_task_runner)
 517     : directory_path_(directory_path),
 518       cache_file_scan_is_needed_(true),
 519       blocking_task_runner_(blocking_task_runner) {
 520 }
 521
 522 void ResourceMetadataStorage::Destroy() {
 523   blocking_task_runner_->PostTask(
 524       FROM_HERE,
 525       base::Bind(&ResourceMetadataStorage::DestroyOnBlockingPool,
 526                  base::Unretained(this)));
 527 }
 528
 529 bool ResourceMetadataStorage::Initialize() {
 530   base::ThreadRestrictions::AssertIOAllowed();
 531
 532   resource_map_.reset();
 533
 534   const base::FilePath resource_map_path =
 535       directory_path_.Append(kResourceMapDBName);
 536   const base::FilePath preserved_resource_map_path =
 537       directory_path_.Append(kPreservedResourceMapDBName);
 538   const base::FilePath trashed_resource_map_path =
 539       directory_path_.Append(kTrashedResourceMapDBName);
 540
 541   // Discard unneeded DBs.
 542   if (!base::DeleteFile(preserved_resource_map_path, true /* recursive */) ||
 543       !base::DeleteFile(trashed_resource_map_path, true /* recursive */)) {
 544     LOG(ERROR) << "Failed to remove unneeded DBs.";
 545     return false;
 546   }
 547
 548   // Try to open the existing DB.
 549   leveldb::DB* db = NULL;
 550   leveldb::Options options;
 551   options.max_open_files = 0;  // Use minimum.
 552   options.create_if_missing = false;
 553   options.reuse_logs = leveldb_env::kDefaultLogReuseOptionValue;
 554
 555   DBInitStatus open_existing_result = DB_INIT_NOT_FOUND;
 556   leveldb::Status status;
 557   if (base::PathExists(resource_map_path)) {
 558     status = leveldb::DB::Open(options, resource_map_path.AsUTF8Unsafe(), &db);
 559     open_existing_result = LevelDBStatusToDBInitStatus(status);
 560   }
 561
 562   if (open_existing_result == DB_INIT_SUCCESS) {
 563     resource_map_.reset(db);
 564
 565     // Check the validity of existing DB.
 566     int db_version = -1;
 567     ResourceMetadataHeader header;
 568     if (GetHeader(&header) == FILE_ERROR_OK)
 569       db_version = header.version();
 570
 571     bool should_discard_db = true;
 572     if (db_version != kDBVersion) {
 573       open_existing_result = DB_INIT_INCOMPATIBLE;
 574       DVLOG(1) << "Reject incompatible DB.";
 575     } else if (!CheckValidity()) {
 576       open_existing_result = DB_INIT_BROKEN;
 577       LOG(ERROR) << "Reject invalid DB.";
 578     } else {
 579       should_discard_db = false;
 580     }
 581
 582     if (should_discard_db)
 583       resource_map_.reset();
 584     else
 585       cache_file_scan_is_needed_ = false;
 586   }
 587
 588   UMA_HISTOGRAM_ENUMERATION("Drive.MetadataDBOpenExistingResult",
 589                             open_existing_result,
 590                             DB_INIT_MAX_VALUE);
 591
 592   DBInitStatus init_result = DB_INIT_OPENED_EXISTING_DB;
 593
 594   // Failed to open the existing DB, create new DB.
 595   if (!resource_map_) {
 596     // Move the existing DB to the preservation path. The moved old DB is
 597     // deleted once the new DB creation succeeds, or is restored later in
 598     // UpgradeOldDB() when the creation fails.
 599     MoveIfPossible(resource_map_path, preserved_resource_map_path);
 600
 601     // Create DB.
 602     options.max_open_files = 0;  // Use minimum.
 603     options.create_if_missing = true;
 604     options.error_if_exists = true;
 605     options.reuse_logs = leveldb_env::kDefaultLogReuseOptionValue;
 606
 607     status = leveldb::DB::Open(options, resource_map_path.AsUTF8Unsafe(), &db);
 608     if (status.ok()) {
 609       resource_map_.reset(db);
 610
 611       // Set up header and trash the old DB.
 612       if (PutHeader(GetDefaultHeaderEntry()) == FILE_ERROR_OK &&
 613           MoveIfPossible(preserved_resource_map_path,
 614                          trashed_resource_map_path)) {
 615         init_result = open_existing_result == DB_INIT_NOT_FOUND ?
 616             DB_INIT_CREATED_NEW_DB : DB_INIT_REPLACED_EXISTING_DB_WITH_NEW_DB;
 617       } else {
 618         init_result = DB_INIT_FAILED;
 619         resource_map_.reset();
 620       }
 621     } else {
 622       LOG(ERROR) << "Failed to create resource map DB: " << status.ToString();
 623       init_result = LevelDBStatusToDBInitStatus(status);
 624     }
 625   }
 626
 627   UMA_HISTOGRAM_ENUMERATION("Drive.MetadataDBInitResult",
 628                             init_result,
 629                             DB_INIT_MAX_VALUE);
 630   return resource_map_;
 631 }
 632
 633 void ResourceMetadataStorage::RecoverCacheInfoFromTrashedResourceMap(
 634     RecoveredCacheInfoMap* out_info) {
 635   const base::FilePath trashed_resource_map_path =
 636       directory_path_.Append(kTrashedResourceMapDBName);
 637
 638   if (!base::PathExists(trashed_resource_map_path))
 639     return;
 640
 641   leveldb::Options options;
 642   options.max_open_files = 0;  // Use minimum.
 643   options.create_if_missing = false;
 644   options.reuse_logs = leveldb_env::kDefaultLogReuseOptionValue;
 645
 646   // Trashed DB may be broken, repair it first.
 647   leveldb::Status status;
 648   status = leveldb::RepairDB(trashed_resource_map_path.AsUTF8Unsafe(), options);
 649   if (!status.ok()) {
 650     LOG(ERROR) << "Failed to repair trashed DB: " << status.ToString();
 651     return;
 652   }
 653
 654   // Open it.
 655   leveldb::DB* db = NULL;
 656   status = leveldb::DB::Open(options, trashed_resource_map_path.AsUTF8Unsafe(),
 657                              &db);
 658   if (!status.ok()) {
 659     LOG(ERROR) << "Failed to open trashed DB: " << status.ToString();
 660     return;
 661   }
 662   scoped_ptr<leveldb::DB> resource_map(db);
 663
 664   // Check DB version.
 665   std::string serialized_header;
 666   ResourceMetadataHeader header;
 667   if (!resource_map->Get(leveldb::ReadOptions(),
 668                          leveldb::Slice(GetHeaderDBKey()),
 669                          &serialized_header).ok() ||
 670       !header.ParseFromString(serialized_header) ||
 671       header.version() != kDBVersion) {
 672     LOG(ERROR) << "Incompatible DB version: " << header.version();
 673     return;
 674   }
 675
 676   // Collect cache entries.
 677   scoped_ptr<leveldb::Iterator> it(
 678       resource_map->NewIterator(leveldb::ReadOptions()));
 679   for (it->SeekToFirst(); it->Valid(); it->Next()) {
 680     if (!IsChildEntryKey(it->key()) &&
 681         !IsIdEntryKey(it->key())) {
 682       const std::string id = it->key().ToString();
 683       ResourceEntry entry;
 684       if (entry.ParseFromArray(it->value().data(), it->value().size()) &&
 685           entry.file_specific_info().has_cache_state()) {
 686         RecoveredCacheInfo* info = &(*out_info)[id];
 687         info->is_dirty = entry.file_specific_info().cache_state().is_dirty();
 688         info->md5 = entry.file_specific_info().cache_state().md5();
 689         info->title = entry.title();
 690       }
 691     }
 692   }
 693 }
 694
 695 FileError ResourceMetadataStorage::SetLargestChangestamp(
 696     int64 largest_changestamp) {
 697   base::ThreadRestrictions::AssertIOAllowed();
 698
 699   ResourceMetadataHeader header;
 700   FileError error = GetHeader(&header);
 701   if (error != FILE_ERROR_OK) {
 702     DLOG(ERROR) << "Failed to get the header.";
 703     return error;
 704   }
 705   header.set_largest_changestamp(largest_changestamp);
 706   return PutHeader(header);
 707 }
 708
 709 FileError ResourceMetadataStorage::GetLargestChangestamp(
 710     int64* largest_changestamp) {
 711   base::ThreadRestrictions::AssertIOAllowed();
 712   ResourceMetadataHeader header;
 713   FileError error = GetHeader(&header);
 714   if (error != FILE_ERROR_OK) {
 715     DLOG(ERROR) << "Failed to get the header.";
 716     return error;
 717   }
 718   *largest_changestamp = header.largest_changestamp();
 719   return FILE_ERROR_OK;
 720 }
 721
 722 FileError ResourceMetadataStorage::PutEntry(const ResourceEntry& entry) {
 723   base::ThreadRestrictions::AssertIOAllowed();
 724
 725   const std::string& id = entry.local_id();
 726   DCHECK(!id.empty());
 727
 728   // Try to get existing entry.
 729   std::string serialized_entry;
 730   leveldb::Status status = resource_map_->Get(leveldb::ReadOptions(),
 731                                               leveldb::Slice(id),
 732                                               &serialized_entry);
 733   if (!status.ok() && !status.IsNotFound())  // Unexpected errors.
 734     return LevelDBStatusToFileError(status);
 735
 736   ResourceEntry old_entry;
 737   if (status.ok() && !old_entry.ParseFromString(serialized_entry))
 738     return FILE_ERROR_FAILED;
 739
 740   // Construct write batch.
 741   leveldb::WriteBatch batch;
 742
 743   // Remove from the old parent.
 744   if (!old_entry.parent_local_id().empty()) {
 745     batch.Delete(GetChildEntryKey(old_entry.parent_local_id(),
 746                                   old_entry.base_name()));
 747   }
 748   // Add to the new parent.
 749   if (!entry.parent_local_id().empty())
 750     batch.Put(GetChildEntryKey(entry.parent_local_id(), entry.base_name()), id);
 751
 752   // Refresh resource-ID-to-local-ID mapping entry.
 753   if (old_entry.resource_id() != entry.resource_id()) {
 754     // Resource ID should not change.
 755     DCHECK(old_entry.resource_id().empty() || entry.resource_id().empty());
 756
 757     if (!old_entry.resource_id().empty())
 758       batch.Delete(GetIdEntryKey(old_entry.resource_id()));
 759     if (!entry.resource_id().empty())
 760       batch.Put(GetIdEntryKey(entry.resource_id()), id);
 761   }
 762
 763   // Put the entry itself.
 764   if (!entry.SerializeToString(&serialized_entry)) {
 765     DLOG(ERROR) << "Failed to serialize the entry: " << id;
 766     return FILE_ERROR_FAILED;
 767   }
 768   batch.Put(id, serialized_entry);
 769
 770   status = resource_map_->Write(leveldb::WriteOptions(), &batch);
 771   return LevelDBStatusToFileError(status);
 772 }
 773
 774 FileError ResourceMetadataStorage::GetEntry(const std::string& id,
 775                                             ResourceEntry* out_entry) {
 776   base::ThreadRestrictions::AssertIOAllowed();
 777   DCHECK(!id.empty());
 778
 779   std::string serialized_entry;
 780   const leveldb::Status status = resource_map_->Get(leveldb::ReadOptions(),
 781                                                     leveldb::Slice(id),
 782                                                     &serialized_entry);
 783   if (!status.ok())
 784     return LevelDBStatusToFileError(status);
 785   if (!out_entry->ParseFromString(serialized_entry))
 786     return FILE_ERROR_FAILED;
 787   return FILE_ERROR_OK;
 788 }
 789
 790 FileError ResourceMetadataStorage::RemoveEntry(const std::string& id) {
 791   base::ThreadRestrictions::AssertIOAllowed();
 792   DCHECK(!id.empty());
 793
 794   ResourceEntry entry;
 795   FileError error = GetEntry(id, &entry);
 796   if (error != FILE_ERROR_OK)
 797     return error;
 798
 799   leveldb::WriteBatch batch;
 800
 801   // Remove from the parent.
 802   if (!entry.parent_local_id().empty())
 803     batch.Delete(GetChildEntryKey(entry.parent_local_id(), entry.base_name()));
 804
 805   // Remove resource ID-local ID mapping entry.
 806   if (!entry.resource_id().empty())
 807     batch.Delete(GetIdEntryKey(entry.resource_id()));
 808
 809   // Remove the entry itself.
 810   batch.Delete(id);
 811
 812   const leveldb::Status status = resource_map_->Write(leveldb::WriteOptions(),
 813                                                       &batch);
 814   return LevelDBStatusToFileError(status);
 815 }
 816
 817 scoped_ptr<ResourceMetadataStorage::Iterator>
 818 ResourceMetadataStorage::GetIterator() {
 819   base::ThreadRestrictions::AssertIOAllowed();
 820
 821   scoped_ptr<leveldb::Iterator> it(
 822       resource_map_->NewIterator(leveldb::ReadOptions()));
 823   return make_scoped_ptr(new Iterator(it.Pass()));
 824 }
 825
 826 FileError ResourceMetadataStorage::GetChild(const std::string& parent_id,
 827                                             const std::string& child_name,
 828                                             std::string* child_id) {
 829   base::ThreadRestrictions::AssertIOAllowed();
 830   DCHECK(!parent_id.empty());
 831   DCHECK(!child_name.empty());
 832
 833   const leveldb::Status status =
 834       resource_map_->Get(
 835           leveldb::ReadOptions(),
 836           leveldb::Slice(GetChildEntryKey(parent_id, child_name)),
 837           child_id);
 838   return LevelDBStatusToFileError(status);
 839 }
 840
 841 FileError ResourceMetadataStorage::GetChildren(
 842     const std::string& parent_id,
 843     std::vector<std::string>* children) {
 844   base::ThreadRestrictions::AssertIOAllowed();
 845   DCHECK(!parent_id.empty());
 846
 847   // Iterate over all entries with keys starting with |parent_id|.
 848   scoped_ptr<leveldb::Iterator> it(
 849       resource_map_->NewIterator(leveldb::ReadOptions()));
 850   for (it->Seek(parent_id);
 851        it->Valid() && it->key().starts_with(leveldb::Slice(parent_id));
 852        it->Next()) {
 853     if (IsChildEntryKey(it->key()))
 854       children->push_back(it->value().ToString());
 855   }
 856   return LevelDBStatusToFileError(it->status());
 857 }
 858
 859 ResourceMetadataStorage::RecoveredCacheInfo::RecoveredCacheInfo()
 860     : is_dirty(false) {}
 861
 862 ResourceMetadataStorage::RecoveredCacheInfo::~RecoveredCacheInfo() {}
 863
 864 FileError ResourceMetadataStorage::GetIdByResourceId(
 865     const std::string& resource_id,
 866     std::string* out_id) {
 867   base::ThreadRestrictions::AssertIOAllowed();
 868   DCHECK(!resource_id.empty());
 869
 870   const leveldb::Status status = resource_map_->Get(
 871       leveldb::ReadOptions(),
 872       leveldb::Slice(GetIdEntryKey(resource_id)),
 873       out_id);
 874   return LevelDBStatusToFileError(status);
 875 }
 876
 877 ResourceMetadataStorage::~ResourceMetadataStorage() {
 878   base::ThreadRestrictions::AssertIOAllowed();
 879 }
 880
 881 void ResourceMetadataStorage::DestroyOnBlockingPool() {
 882   delete this;
 883 }
 884
 885 // static
 886 std::string ResourceMetadataStorage::GetChildEntryKey(
 887     const std::string& parent_id,
 888     const std::string& child_name) {
 889   DCHECK(!parent_id.empty());
 890   DCHECK(!child_name.empty());
 891
 892   std::string key = parent_id;
 893   key.push_back(kDBKeyDelimeter);
 894   key.append(child_name);
 895   key.push_back(kDBKeyDelimeter);
 896   return key;
 897 }
 898
 899 FileError ResourceMetadataStorage::PutHeader(
 900     const ResourceMetadataHeader& header) {
 901   base::ThreadRestrictions::AssertIOAllowed();
 902
 903   std::string serialized_header;
 904   if (!header.SerializeToString(&serialized_header)) {
 905     DLOG(ERROR) << "Failed to serialize the header";
 906     return FILE_ERROR_FAILED;
 907   }
 908
 909   const leveldb::Status status = resource_map_->Put(
 910       leveldb::WriteOptions(),
 911       leveldb::Slice(GetHeaderDBKey()),
 912       leveldb::Slice(serialized_header));
 913   return LevelDBStatusToFileError(status);
 914 }
 915
 916 FileError ResourceMetadataStorage::GetHeader(ResourceMetadataHeader* header) {
 917   base::ThreadRestrictions::AssertIOAllowed();
 918
 919   std::string serialized_header;
 920   const leveldb::Status status = resource_map_->Get(
 921       leveldb::ReadOptions(),
 922       leveldb::Slice(GetHeaderDBKey()),
 923       &serialized_header);
 924   if (!status.ok())
 925     return LevelDBStatusToFileError(status);
 926   return header->ParseFromString(serialized_header) ?
 927       FILE_ERROR_OK : FILE_ERROR_FAILED;
 928 }
 929
 930 bool ResourceMetadataStorage::CheckValidity() {
 931   base::ThreadRestrictions::AssertIOAllowed();
 932
 933   // Perform read with checksums verification enabled.
 934   leveldb::ReadOptions options;
 935   options.verify_checksums = true;
 936
 937   scoped_ptr<leveldb::Iterator> it(resource_map_->NewIterator(options));
 938   it->SeekToFirst();
 939
 940   // DB is organized like this:
 941   //
 942   // <key>                          : <value>
 943   // "\0HEADER"                     : ResourceMetadataHeader
 944   // "\0ID\0|resource ID 1|"        : Local ID associated to resource ID 1.
 945   // "\0ID\0|resource ID 2|"        : Local ID associated to resource ID 2.
 946   // ...
 947   // "|ID of A|"                    : ResourceEntry for entry A.
 948   // "|ID of A|\0|child name 1|\0"  : ID of the 1st child entry of entry A.
 949   // "|ID of A|\0|child name 2|\0"  : ID of the 2nd child entry of entry A.
 950   // ...
 951   // "|ID of A|\0|child name n|\0"  : ID of the nth child entry of entry A.
 952   // "|ID of B|"                    : ResourceEntry for entry B.
 953   // ...
 954
 955   // Check the header.
 956   ResourceMetadataHeader header;
 957   if (!it->Valid() ||
 958       it->key() != GetHeaderDBKey() ||  // Header entry must come first.
 959       !header.ParseFromArray(it->value().data(), it->value().size()) ||
 960       header.version() != kDBVersion) {
 961     DLOG(ERROR) << "Invalid header detected. version = " << header.version();
 962     RecordCheckValidityFailure(CHECK_VALIDITY_FAILURE_INVALID_HEADER);
 963     return false;
 964   }
 965
 966   // First scan. Remember relationships between IDs.
 967   typedef base::hash_map<std::string, std::string> KeyToIdMapping;
 968   KeyToIdMapping local_id_to_resource_id_map;
 969   KeyToIdMapping child_key_to_local_id_map;
 970   std::set<std::string> resource_entries;
 971   std::string first_resource_entry_key;
 972   for (it->Next(); it->Valid(); it->Next()) {
 973     if (IsChildEntryKey(it->key())) {
 974       child_key_to_local_id_map[it->key().ToString()] = it->value().ToString();
 975       continue;
 976     }
 977
 978     if (IsIdEntryKey(it->key())) {
 979       const auto result = local_id_to_resource_id_map.insert(std::make_pair(
 980           it->value().ToString(),
 981           GetResourceIdFromIdEntryKey(it->key().ToString())));
 982       // Check that no local ID is associated with more than one resource ID.
 983       if (!result.second) {
 984         DLOG(ERROR) << "Broken ID entry.";
 985         RecordCheckValidityFailure(CHECK_VALIDITY_FAILURE_BROKEN_ID_ENTRY);
 986         return false;
 987       }
 988       continue;
 989     }
 990
 991     // Remember the key of the first resource entry record, so the second scan
 992     // can start from this point.
 993     if (first_resource_entry_key.empty())
 994       first_resource_entry_key = it->key().ToString();
 995
 996     resource_entries.insert(it->key().ToString());
 997   }
 998
 999   // Second scan. Verify relationships and resource entry correctness.
1000   size_t num_entries_with_parent = 0;
1001   ResourceEntry entry;
1002   for (it->Seek(first_resource_entry_key); it->Valid(); it->Next()) {
1003     if (IsChildEntryKey(it->key()))
1004       continue;
1005
1006     if (!entry.ParseFromArray(it->value().data(), it->value().size())) {
1007       DLOG(ERROR) << "Broken entry detected.";
1008       RecordCheckValidityFailure(CHECK_VALIDITY_FAILURE_BROKEN_ENTRY);
1009       return false;
1010     }
1011
1012     // Resource-ID-to-local-ID mapping without entry for the local ID is OK,
1013     // but if it exists, then the resource ID must be consistent.
1014     const auto mapping_it =
1015         local_id_to_resource_id_map.find(it->key().ToString());
1016     if (mapping_it != local_id_to_resource_id_map.end() &&
1017         entry.resource_id() != mapping_it->second) {
1018       DLOG(ERROR) << "Broken ID entry.";
1019       RecordCheckValidityFailure(CHECK_VALIDITY_FAILURE_BROKEN_ID_ENTRY);
1020       return false;
1021     }
1022
1023     // If the parent is referenced, then confirm that it exists and check the
1024     // parent-child relationships.
1025     if (!entry.parent_local_id().empty()) {
1026       const auto mapping_it = resource_entries.find(entry.parent_local_id());
1027       if (mapping_it == resource_entries.end()) {
1028         DLOG(ERROR) << "Parent entry not found.";
1029         RecordCheckValidityFailure(CHECK_VALIDITY_FAILURE_INVALID_PARENT_ID);
1030         return false;
1031       }
1032
1033       // Check if parent-child relationship is stored correctly.
1034       const auto child_mapping_it = child_key_to_local_id_map.find(
1035           GetChildEntryKey(entry.parent_local_id(), entry.base_name()));
1036       if (child_mapping_it == child_key_to_local_id_map.end() ||
1037           leveldb::Slice(child_mapping_it->second) != it->key()) {
1038         DLOG(ERROR) << "Child map is broken.";
1039         RecordCheckValidityFailure(CHECK_VALIDITY_FAILURE_BROKEN_CHILD_MAP);
1040         return false;
1041       }
1042       ++num_entries_with_parent;
1043     }
1044   }
1045
1046   if (!it->status().ok()) {
1047     DLOG(ERROR) << "Error during checking resource map. status = "
1048                 << it->status().ToString();
1049     RecordCheckValidityFailure(CHECK_VALIDITY_FAILURE_ITERATOR_ERROR);
1050     return false;
1051   }
1052
1053   if (child_key_to_local_id_map.size() != num_entries_with_parent) {
1054     DLOG(ERROR) << "Child entry count mismatch.";
1055     RecordCheckValidityFailure(
1056         CHECK_VALIDITY_FAILURE_CHILD_ENTRY_COUNT_MISMATCH);
1057     return false;
1058   }
1059
1060   return true;
1061 }
1062
1063 }  // namespace internal
1064 }  // namespace drive