Disk cache: Fix the order in which we delete data

from the block files.

Stress testing the cache reveals a problem with the deletion
of some data from an entry: it is possible to crash in a way
that the block file thinks a block is free and an entry
thinks the block is in use. This CL corrects that issue.

There is also some new tests and a bunch of DCHECKS added
while looking for the problem, as well as adding tests to
make sure that a block file is accessed only from one thread
(there is no problem with the current code in that regard)

BUG=55605
TEST=netunittests

Review URL: http://codereview.chromium.org/3430004

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@59711 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 67 insertions, 2 deletions

diff --git a/net/disk_cache/block_files.cc b/net/disk_cache/block_files.cc
index 5461b7e..b81a868 100644
--- a/net/disk_cache/block_files.cc
+++ b/net/disk_cache/block_files.cc
@@ -7,9 +7,11 @@
 #include "base/file_util.h"
 #include "base/histogram.h"
 #include "base/string_util.h"
+#include "base/thread_checker.h"
 #include "base/time.h"
 #include "net/disk_cache/cache_util.h"
 #include "net/disk_cache/file_lock.h"
+#include "net/disk_cache/trace.h"
 
 using base::TimeTicks;
 
@@ -57,6 +59,7 @@ bool CreateMapBlock(int target, int size, disk_cache::BlockFileHeader* header,
       disk_cache::FileLock lock(header);
       int index_offset = j * 4 + 4 - target;
       *index = current * 32 + index_offset;
+      DCHECK_EQ(*index / 4, (*index + size - 1) / 4);
       uint32 to_add = ((1 << size) - 1) << index_offset;
       header->allocation_map[current] |= to_add;
 
@@ -118,6 +121,25 @@ void DeleteMapBlock(int index, int size, disk_cache::BlockFileHeader* header) {
   HISTOGRAM_TIMES("DiskCache.DeleteBlock", TimeTicks::Now() - start);
 }
 
+// Returns true if the specified block is used. Note that this is a simplified
+// version of DeleteMapBlock().
+bool UsedMapBlock(int index, int size, disk_cache::BlockFileHeader* header) {
+  if (size < 0 || size > disk_cache::kMaxNumBlocks) {
+    NOTREACHED();
+    return false;
+  }
+  int byte_index = index / 8;
+  uint8* byte_map = reinterpret_cast<uint8*>(header->allocation_map);
+  uint8 map_block = byte_map[byte_index];
+
+  if (index % 8 >= 4)
+    map_block >>= 4;
+
+  DCHECK((((1 << size) - 1) << (index % 8)) < 0x100);
+  uint8  to_clear = ((1 << size) - 1) << (index % 8);
+  return ((byte_map[byte_index] & to_clear) == to_clear);
+}
+
 // Restores the "empty counters" and allocation hints.
 void FixAllocationCounters(disk_cache::BlockFileHeader* header) {
   for (int i = 0; i < disk_cache::kMaxNumBlocks; i++) {
@@ -172,6 +194,8 @@ bool BlockFiles::Init(bool create_files) {
   if (init_)
     return false;
 
+  thread_checker_.reset(new ThreadChecker);
+
   block_files_.resize(kFirstAdditionalBlockFile);
   for (int i = 0; i < kFirstAdditionalBlockFile; i++) {
     if (create_files)
@@ -190,6 +214,9 @@ bool BlockFiles::Init(bool create_files) {
 }
 
 void BlockFiles::CloseFiles() {
+  if (init_) {
+    DCHECK(thread_checker_->CalledOnValidThread());
+  }
   init_ = false;
   for (unsigned int i = 0; i < block_files_.size(); i++) {
     if (block_files_[i]) {
@@ -201,6 +228,7 @@ void BlockFiles::CloseFiles() {
 }
 
 void BlockFiles::ReportStats() {
+  DCHECK(thread_checker_->CalledOnValidThread());
   int used_blocks[kFirstAdditionalBlockFile];
   int load[kFirstAdditionalBlockFile];
   for (int i = 0; i < kFirstAdditionalBlockFile; i++) {
@@ -217,6 +245,36 @@ void BlockFiles::ReportStats() {
   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_3", load[3], 101);
 }
 
+bool BlockFiles::IsValid(Addr address) {
+#ifdef NDEBUG
+  return true;
+#else
+  if (!address.is_initialized() || address.is_separate_file())
+    return false;
+
+  MappedFile* file = GetFile(address);
+  if (!file)
+    return false;
+
+  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
+  bool rv = UsedMapBlock(address.start_block(), address.num_blocks(), header);
+  DCHECK(rv);
+
+  static bool read_contents = false;
+  if (read_contents) {
+    scoped_array<char> buffer;
+    buffer.reset(new char[Addr::BlockSizeForFileType(BLOCK_4K) * 4]);
+    size_t size = address.BlockSize() * address.num_blocks();
+    size_t offset = address.start_block() * address.BlockSize() +
+                    kBlockHeaderSize;
+    bool ok = file->Read(buffer.get(), size, offset);
+    DCHECK(ok);
+  }
+
+  return rv;
+#endif
+}
+
 bool BlockFiles::CreateBlockFile(int index, FileType file_type, bool force) {
   FilePath name = Name(index);
   int flags =
@@ -282,6 +340,7 @@ bool BlockFiles::OpenBlockFile(int index) {
 }
 
 MappedFile* BlockFiles::GetFile(Addr address) {
+  DCHECK(thread_checker_->CalledOnValidThread());
   DCHECK(block_files_.size() >= 4);
   DCHECK(address.is_block_file() || !address.is_initialized());
   if (!address.is_initialized())
@@ -420,6 +479,7 @@ void BlockFiles::RemoveEmptyFile(FileType block_type) {
 
 bool BlockFiles::CreateBlock(FileType block_type, int block_count,
                              Addr* block_address) {
+  DCHECK(thread_checker_->CalledOnValidThread());
   if (block_type < RANKINGS || block_type > BLOCK_4K ||
       block_count < 1 || block_count > 4)
     return false;
@@ -447,10 +507,12 @@ bool BlockFiles::CreateBlock(FileType block_type, int block_count,
 
   Addr address(block_type, block_count, header->this_file, index);
   block_address->set_value(address.value());
+  Trace("CreateBlock 0x%x", address.value());
   return true;
 }
 
 void BlockFiles::DeleteBlock(Addr address, bool deep) {
+  DCHECK(thread_checker_->CalledOnValidThread());
   if (!address.is_initialized() || address.is_separate_file())
     return;
 
@@ -462,14 +524,17 @@ void BlockFiles::DeleteBlock(Addr address, bool deep) {
   if (!file)
     return;
 
+  Trace("DeleteBlock 0x%x", address.value());
+
+  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
+  DeleteMapBlock(address.start_block(), address.num_blocks(), header);
+
   size_t size = address.BlockSize() * address.num_blocks();
   size_t offset = address.start_block() * address.BlockSize() +
                   kBlockHeaderSize;
   if (deep)
     file->Write(zero_buffer_, size, offset);
 
-  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-  DeleteMapBlock(address.start_block(), address.num_blocks(), header);
   if (!header->num_entries) {
     // This file is now empty. Let's try to delete it.
     FileType type = Addr::RequiredFileType(header->entry_size);