Add database recovery for FileSystemDirectoryDatabase.

webkit/fileapi/file_system_directory_database.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "webkit/fileapi/file_system_directory_database.h"
 
 #include <math.h>
 
 #include "base/file_util.h"
 #include "base/location.h"
 #include "base/metrics/histogram.h"
 #include "base/pickle.h"
 #include "base/string_number_conversions.h"
 #include "base/string_util.h"
 #include "third_party/leveldatabase/src/include/leveldb/db.h"
 #include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
+#include "webkit/fileapi/file_system_usage_cache.h"
 #include "webkit/fileapi/file_system_util.h"
 
 namespace {
 
 bool PickleFromFileInfo(
     const fileapi::FileSystemDirectoryDatabase::FileInfo& info,
     Pickle* pickle) {
   DCHECK(pickle);
   std::string data_path;
   // Round off here to match the behavior of the filesystem on real files.
@@ skipping 71 matching lines @@
 
 const char* LastIntegerKey() {
   return kLastIntegerKey;
 }
 
 std::string GetFileLookupKey(
     fileapi::FileSystemDirectoryDatabase::FileId file_id) {
   return base::Int64ToString(file_id);
 }
 
+// Assumptions:
+//  - Any database entry is one of:
+//    - ("CHILD_OF:|parent_id|:<name>", "|file_id|"),
+//    - ("LAST_FILE_ID", "|last_file_id|"),
+//    - ("LAST_INTEGER", "|last_integer|"),
+//    - ("|file_id|", "pickled FileInfo")
+//        whire FileInfo has |parent_id|, |data_path|, |name| and
+//        |modification_time|,
+// Constraints:
+//  - Each |file_id| has unique backing file.

[ericu, 2012/04/03 01:52:11]

No--there are file_ids for directories, which have no backing files.

[tzik, 2012/04/04 06:50:39]

Done.

+//  - Each file in |filesystem_data_directory_| has a database entry.
+//  - Directory structure is tree, i.e. connected and acyclic.
+class DatabaseCheckHelper {
+ public:
+  typedef fileapi::FileSystemDirectoryDatabase::FileId FileId;
+  typedef fileapi::FileSystemDirectoryDatabase::FileInfo FileInfo;
+
+  DatabaseCheckHelper(fileapi::FileSystemDirectoryDatabase* dir_db,
+                      leveldb::DB* db,
+                      const FilePath& path);
+
+  bool IsFileSystemConsistent() {
+    return IsDatabaseEmpty() ||
+        (ScanDatabase() && ScanDirectory() && ScanHierarchy());
+  }
+
+ private:
+  bool IsDatabaseEmpty();
+  bool ScanDatabase();

[ericu, 2012/04/03 01:52:11]

It's probably worth a comment that these need to be called in a specific order,
even though this is all private.

[tzik, 2012/04/04 06:50:39]

Done.

+  bool ScanDirectory();
+  bool ScanHierarchy();
+
+  fileapi::FileSystemDirectoryDatabase* dir_db_;
+  leveldb::DB* db_;
+  FilePath path_;
+
+  std::set<FilePath> files_in_db_;
+
+  size_t num_directories_in_db_;
+  size_t num_files_in_db_;
+  size_t num_hierarchy_links_in_db_;
+
+  FileId last_file_id_;
+  FileId last_integer_;
+};
+
+DatabaseCheckHelper::DatabaseCheckHelper(
+    fileapi::FileSystemDirectoryDatabase* dir_db,
+    leveldb::DB* db,
+    const FilePath& path)
+    : dir_db_(dir_db), db_(db), path_(path),
+      files_in_db_(),

[ericu, 2012/04/03 01:52:11]

Omit the default constructor for files_in_db.

[tzik, 2012/04/04 06:50:39]

Done.

+      num_directories_in_db_(0),
+      num_files_in_db_(0),
+      num_hierarchy_links_in_db_(0),
+      last_file_id_(-1), last_integer_(-1) {
+  DCHECK(dir_db_);
+  DCHECK(db_);
+  DCHECK(!path_.empty() && file_util::DirectoryExists(path_));
+}
+
+bool DatabaseCheckHelper::IsDatabaseEmpty() {
+  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
+  itr->SeekToFirst();
+  return !itr->Valid();
+}
+
+bool DatabaseCheckHelper::ScanDatabase() {
+  // Scans all database entries sequentially to verify each of them has unique
+  // backing file.
+  int64 max_file_id = -1;
+
+  scoped_ptr<leveldb::Iterator> itr(db_->NewIterator(leveldb::ReadOptions()));
+  for (itr->SeekToFirst(); itr->Valid(); itr->Next()) {
+    std::string key = itr->key().ToString();
+    if (StartsWithASCII(key, kChildLookupPrefix, true)) {
+      // key: "CHILD_OF:<parent_id>:<name>"
+      // value: "<child_id>"
+      ++num_hierarchy_links_in_db_;
+    } else if (key == kLastFileIdKey) {
+      // key: "LAST_FILE_ID"
+      // value: "<last_file_id>"
+      if (last_file_id_ >= 0 ||
+          !base::StringToInt64(itr->value().ToString(), &last_file_id_))
+        return false;
+
+      if (last_file_id_ < 0)
+        return false;
+    } else if (key == kLastIntegerKey) {
+      // key: "LAST_INTEGER"
+      // value: "<last_integer>"
+      if (last_integer_ >= 0 ||
+          !base::StringToInt64(itr->value().ToString(), &last_integer_))
+        return false;
+    } else {
+      // key: "<entry_id>"
+      // value: "<pickled FileInfo>"
+      FileInfo file_info;
+      if (!FileInfoFromPickle(
+              Pickle(itr->value().data(), itr->value().size()), &file_info))
+        return false;
+
+      FileId file_id = -1;
+      if (!base::StringToInt64(key, &file_id) || file_id < 0)
+        return false;
+
+      if (max_file_id < file_id)
+        max_file_id = file_id;
+
+      if (file_info.is_directory()) {
+        ++num_directories_in_db_;

[ericu, 2012/04/03 01:52:11]

Verify that there's no data path in the pickle.

[tzik, 2012/04/04 06:50:39]

Done.
Implementation of FileInfo::is_directory() is data_path.empty(), currently.
So IMO, DCHECK() is enough strict.

+      } else {
+        ++num_files_in_db_;

[ericu, 2012/04/03 01:52:11]

Verify that the file id is unique.

[tzik, 2012/04/04 06:50:39]

Done.

+
+        // Ensure any pair of file entry don't share their data_path.
+        if (!files_in_db_.insert(file_info.data_path).second)
+          return false;
+
+        // Ensure the backing file exists as a normal file.
+        base::PlatformFileInfo platform_file_info;
+        if (!file_util::GetFileInfo(
+                path_.Append(file_info.data_path), &platform_file_info) ||
+            platform_file_info.is_directory ||
+            platform_file_info.is_symbolic_link)
+          return false;
+      }
+    }
+  }
+
+  // TODO(tzik): Add constraint for |last_integer_| to avoid possible
+  // data path confliction on ObfuscatedFileUtil.
+  return max_file_id <= last_file_id_;
+}
+
+bool DatabaseCheckHelper::ScanDirectory() {
+  // Scans all local file system entries to verify each of them has a database
+  // entry.
+  const FilePath kExcludes[] = {
+    FilePath(kDirectoryDatabaseName),
+    FilePath(fileapi::FileSystemUsageCache::kUsageFileName),
+  };
+
+  std::stack<FilePath> pending_directories;
+  pending_directories.push(FilePath());
+
+  while (!pending_directories.empty()) {
+    FilePath dir_path = pending_directories.top();
+    pending_directories.pop();
+
+    FilePath absolute_path = dir_path.empty() ? path_ : path_.Append(dir_path);
+    file_util::FileEnumerator file_enum(
+        path_.Append(dir_path), false /* recursive */,
+        static_cast<file_util::FileEnumerator::FileType>(
+            file_util::FileEnumerator::DIRECTORIES |
+            file_util::FileEnumerator::FILES));
+
+    FilePath file_path;
+    while (!(file_path = file_enum.Next()).empty()) {
+      file_util::FileEnumerator::FindInfo find_info;
+      file_enum.GetFindInfo(&find_info);
+
+      if (std::find(kExcludes, kExcludes + arraysize(kExcludes),
+                    dir_path) != kExcludes + arraysize(kExcludes))

[ericu, 2012/04/03 01:52:11]

Add a counter to make sure that you find the right number of these files.

[tzik, 2012/04/04 06:50:39]

IMO, it is not needed for now.
After patchset 5, this path is relative to filesystem_data_directory. So, it can
not exceed # of excluded path.
And since the database works properly at this point, we can assume the Paths
directory exists. Absence of .usage file makes no problem, so we can ignore it
exists or not.

[ericu, 2012/04/05 00:22:26]

That works.

+        continue;
+
+      if (file_util::FileEnumerator::IsLink(find_info))
+        return false;
+
+      FilePath data_path = dir_path.Append(
+          file_util::FileEnumerator::GetFilename(find_info));
+      pending_directories.push(data_path);

[ericu, 2012/04/03 01:52:11]

You're adding all files to pending_directories, not just the directories.

[tzik, 2012/04/04 06:50:39]

Done.
This part of CL was broken..

+      if (file_util::FileEnumerator::IsDirectory(find_info))
+        continue;
+
+      // Check if the file has a database entry.
+      std::set<FilePath>::iterator itr = files_in_db_.find(data_path);
+      if (itr == files_in_db_.end())
+        return false;
+      files_in_db_.erase(itr);
+    }
+  }
+
+  return files_in_db_.empty();
+}
+
+bool DatabaseCheckHelper::ScanHierarchy() {
+  size_t visited_directories = 0;
+  size_t visited_files = 0;
+  size_t visited_links = 0;
+
+  std::stack<FileId> directories;
+  directories.push(0);
+
+  // Check if the root directory exists as a directory.
+  FileInfo file_info;
+  if (!dir_db_->GetFileInfo(0, &file_info))
+    return false;
+  if (file_info.parent_id != 0 ||
+      !file_info.is_directory())
+    return false;
+
+  while (!directories.empty()) {
+    ++visited_directories;
+    FileId dir_id = directories.top();
+    directories.pop();
+
+    std::vector<FileId> children;
+    if (!dir_db_->ListChildren(dir_id, &children))
+      return false;
+    for (std::vector<FileId>::iterator itr = children.begin();
+         itr != children.end();
+         ++itr) {
+      // Any directory must not have root directory as child.
+      if (!*itr)
+        return false;
+
+      // Check if the child knows the parent as its parent.
+      FileInfo file_info;
+      if (!dir_db_->GetFileInfo(*itr, &file_info))
+        return false;
+      if (file_info.parent_id != dir_id)
+        return false;
+
+      // Check if the parent knows the name of its child correctly.
+      FileId file_id;
+      if (!dir_db_->GetChildWithName(dir_id, file_info.name, &file_id) ||
+          file_id != *itr)
+        return false;
+
+      if (file_info.is_directory())
+        directories.push(*itr);
+      else
+        ++visited_files;
+      ++visited_links;
+    }
+  }
+
+  // Check if we've visited all database entries.
+  return num_directories_in_db_ == visited_directories &&
+      num_files_in_db_ == visited_files &&
+      num_hierarchy_links_in_db_ == visited_links;
+}
+
 }  // namespace
 
 namespace fileapi {
 
 FileSystemDirectoryDatabase::FileInfo::FileInfo() : parent_id(0) {
 }
 
 FileSystemDirectoryDatabase::FileInfo::~FileInfo() {
 }
 
 FileSystemDirectoryDatabase::FileSystemDirectoryDatabase(
     const FilePath& filesystem_data_directory)
     : filesystem_data_directory_(filesystem_data_directory) {
 }
 
 FileSystemDirectoryDatabase::~FileSystemDirectoryDatabase() {
 }
 
 bool FileSystemDirectoryDatabase::GetChildWithName(
     FileId parent_id, const FilePath::StringType& name, FileId* child_id) {
-  if (!Init(FAIL_ON_CORRUPTION))
+  if (!Init(REPAIR_ON_CORRUPTION))
     return false;
   DCHECK(child_id);
   std::string child_key = GetChildLookupKey(parent_id, name);
   std::string child_id_string;
   leveldb::Status status =
       db_->Get(leveldb::ReadOptions(), child_key, &child_id_string);
   if (status.IsNotFound())
     return false;
   if (status.ok()) {
     if (!base::StringToInt64(child_id_string, child_id)) {
@@ skipping 20 matching lines @@
     if (!GetChildWithName(local_id, name, &local_id))
       return false;
   }
   *file_id = local_id;
   return true;
 }
 
 bool FileSystemDirectoryDatabase::ListChildren(
     FileId parent_id, std::vector<FileId>* children) {
   // Check to add later: fail if parent is a file, at least in debug builds.
-  if (!Init(FAIL_ON_CORRUPTION))
+  if (!Init(REPAIR_ON_CORRUPTION))
     return false;
   DCHECK(children);
   std::string child_key_prefix = GetChildListingKeyPrefix(parent_id);
 
   scoped_ptr<leveldb::Iterator> iter(db_->NewIterator(leveldb::ReadOptions()));
   iter->Seek(child_key_prefix);
   children->clear();
   while (iter->Valid() &&
       StartsWithASCII(iter->key().ToString(), child_key_prefix, true)) {
     std::string child_id_string = iter->value().ToString();
     FileId child_id;
     if (!base::StringToInt64(child_id_string, &child_id)) {
       LOG(ERROR) << "Hit database corruption!";
       return false;
     }
     children->push_back(child_id);
     iter->Next();
   }
   return true;
 }
 
 bool FileSystemDirectoryDatabase::GetFileInfo(FileId file_id, FileInfo* info) {
-  if (!Init(FAIL_ON_CORRUPTION))
+  if (!Init(REPAIR_ON_CORRUPTION))
     return false;
   DCHECK(info);
   std::string file_key = GetFileLookupKey(file_id);
   std::string file_data_string;
   leveldb::Status status =
       db_->Get(leveldb::ReadOptions(), file_key, &file_data_string);
   if (status.ok()) {
     return FileInfoFromPickle(
         Pickle(file_data_string.data(), file_data_string.length()), info);
   }
   // Special-case the root, for databases that haven't been initialized yet.
   // Without this, a query for the root's file info, made before creating the
   // first file in the database, will fail and confuse callers.
   if (status.IsNotFound() && !file_id) {
     info->name = FilePath::StringType();
     info->data_path = FilePath();
     info->modification_time = base::Time::Now();
     info->parent_id = 0;
     return true;
   }
   HandleError(FROM_HERE, status);
   return false;
 }
 
 bool FileSystemDirectoryDatabase::AddFileInfo(
     const FileInfo& info, FileId* file_id) {
-  if (!Init(FAIL_ON_CORRUPTION))
+  if (!Init(REPAIR_ON_CORRUPTION))
     return false;
   DCHECK(file_id);
   std::string child_key = GetChildLookupKey(info.parent_id, info.name);
   std::string child_id_string;
   leveldb::Status status =
       db_->Get(leveldb::ReadOptions(), child_key, &child_id_string);
   if (status.ok()) {
     LOG(ERROR) << "File exists already!";
     return false;
   }
@@ skipping 21 matching lines @@
   status = db_->Write(leveldb::WriteOptions(), &batch);
   if (!status.ok()) {
     HandleError(FROM_HERE, status);
     return false;
   }
   *file_id = temp_id;
   return true;
 }
 
 bool FileSystemDirectoryDatabase::RemoveFileInfo(FileId file_id) {
-  if (!Init(FAIL_ON_CORRUPTION))
+  if (!Init(REPAIR_ON_CORRUPTION))
     return false;
   leveldb::WriteBatch batch;
   if (!RemoveFileInfoHelper(file_id, &batch))
     return false;
   leveldb::Status status = db_->Write(leveldb::WriteOptions(), &batch);
   if (!status.ok()) {
     HandleError(FROM_HERE, status);
     return false;
   }
   return true;
 }
 
 bool FileSystemDirectoryDatabase::UpdateFileInfo(
     FileId file_id, const FileInfo& new_info) {
   // TODO: We should also check to see that this doesn't create a loop, but
   // perhaps only in a debug build.
-  if (!Init(FAIL_ON_CORRUPTION))
+  if (!Init(REPAIR_ON_CORRUPTION))
     return false;
   DCHECK(file_id);  // You can't remove the root, ever.  Just delete the DB.
   FileInfo old_info;
   if (!GetFileInfo(file_id, &old_info))
     return false;
   if (old_info.parent_id != new_info.parent_id &&
       !VerifyIsDirectory(new_info.parent_id))
     return false;
   if (old_info.parent_id != new_info.parent_id ||
       old_info.name != new_info.name) {
@@ skipping 63 matching lines @@
                      pickle.size()));
   leveldb::Status status = db_->Write(leveldb::WriteOptions(), &batch);
   if (!status.ok()) {
     HandleError(FROM_HERE, status);
     return false;
   }
   return true;
 }
 
 bool FileSystemDirectoryDatabase::GetNextInteger(int64* next) {
-  if (!Init(FAIL_ON_CORRUPTION))
+  if (!Init(REPAIR_ON_CORRUPTION))
     return false;
   DCHECK(next);
   std::string int_string;
   leveldb::Status status =
       db_->Get(leveldb::ReadOptions(), LastIntegerKey(), &int_string);
   if (status.ok()) {
     int64 temp;
     if (!base::StringToInt64(int_string, &temp)) {
       LOG(ERROR) << "Hit database corruption!";
       return false;
@@ skipping 41 matching lines @@
   options.create_if_missing = true;
   leveldb::DB* db;
   leveldb::Status status = leveldb::DB::Open(options, path, &db);
   ReportInitStatus(status);
   if (status.ok()) {
     db_.reset(db);
     return true;
   }
   HandleError(FROM_HERE, status);
 
-  if (recovery_option == FAIL_ON_CORRUPTION)
+  switch (recovery_option) {
+    case FAIL_ON_CORRUPTION:
+      return false;
+    case REPAIR_ON_CORRUPTION:
+      if (RepairDatabase(path))
+        return Init(FAIL_ON_CORRUPTION);
+      // fall through
+    case DELETE_ON_CORRUPTION:
+      if (!file_util::Delete(filesystem_data_directory_, true))
+        return false;
+      if (!file_util::CreateDirectory(filesystem_data_directory_))
+        return false;
+      return Init(FAIL_ON_CORRUPTION);
+  }
+
+  NOTREACHED();
+  return false;
+}
+
+bool FileSystemDirectoryDatabase::RepairDatabase(const std::string& db_path) {
+  DCHECK(!db_.get());
+  if (!leveldb::RepairDB(db_path, leveldb::Options()).ok())
     return false;
+  if (!Init(FAIL_ON_CORRUPTION))

[ericu, 2012/04/03 01:52:11]

You're calling Init(FAIL_ON_CORRUPTION) both here and at line 673; it seems that
one should be enough.  At 673 you could just return true.

[tzik, 2012/04/04 06:50:39]

Done.

+    return false;
+  if (IsFileSystemConsistent())
+    return true;
+  db_.reset();
+  return false;
+}
 
-  DCHECK_EQ(DELETE_ON_CORRUPTION, recovery_option);
-  if (!file_util::Delete(filesystem_data_directory_, true))
+bool FileSystemDirectoryDatabase::IsFileSystemConsistent() {
+  if (!Init(FAIL_ON_CORRUPTION))
     return false;
-  if (!file_util::CreateDirectory(filesystem_data_directory_))
-    return false;
-  return Init(FAIL_ON_CORRUPTION);
+  DatabaseCheckHelper helper(this, db_.get(), filesystem_data_directory_);
+  return helper.IsFileSystemConsistent();
 }
 
 void FileSystemDirectoryDatabase::ReportInitStatus(
     const leveldb::Status& status) {
   base::Time now = base::Time::Now();
   const base::TimeDelta minimum_interval =
       base::TimeDelta::FromHours(kMinimumReportIntervalHours);
   if (last_reported_time_ + minimum_interval >= now)
     return;
   last_reported_time_ = now;
@@ skipping 27 matching lines @@
   batch.Put(LastIntegerKey(), base::Int64ToString(-1));
   leveldb::Status status = db_->Write(leveldb::WriteOptions(), &batch);
   if (!status.ok()) {
     HandleError(FROM_HERE, status);
     return false;
   }
   return true;
 }
 
 bool FileSystemDirectoryDatabase::GetLastFileId(FileId* file_id) {
-  if (!Init(FAIL_ON_CORRUPTION))
+  if (!Init(REPAIR_ON_CORRUPTION))
     return false;
   DCHECK(file_id);
   std::string id_string;
   leveldb::Status status =
       db_->Get(leveldb::ReadOptions(), LastFileIdKey(), &id_string);
   if (status.ok()) {
     if (!base::StringToInt64(id_string, file_id)) {
       LOG(ERROR) << "Hit database corruption!";
       return false;
     }
@@ skipping 69 matching lines @@
 
 void FileSystemDirectoryDatabase::HandleError(
     const tracked_objects::Location& from_here,
     const leveldb::Status& status) {
   LOG(ERROR) << "FileSystemDirectoryDatabase failed at: "
              << from_here.ToString() << " with error: " << status.ToString();
   db_.reset();
 }
 
 }  // namespace fileapi