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