Disk cache: Introduce BlockBitmaps for V3.

The new class encapsulates the group of headers/bitmaps
in use by the backend. In other words, this class plays the
role that BlockFiles plays for version 2 of the cache, but
without performing any IO.

BUG=241277
TEST=net_unittests
R=gavinp@chromium.org, rdsmith@chromium.org

Review URL: https://codereview.chromium.org/17816008

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

6 files changed, 242 insertions, 631 deletions

diff --git a/net/disk_cache/block_files.cc b/net/disk_cache/block_files.cc
index 9246ef1..896cdb1 100644
--- a/net/disk_cache/block_files.cc
+++ b/net/disk_cache/block_files.cc
@@ -52,9 +52,17 @@ BlockHeader::BlockHeader(const BlockHeader& other) : header_(other.header_) {
 BlockHeader::~BlockHeader() {
 }
 
-bool BlockHeader::CreateMapBlock(int target, int size, int* index) {
-  if (target <= 0 || target > kMaxNumBlocks ||
-      size <= 0 || size > kMaxNumBlocks) {
+bool BlockHeader::CreateMapBlock(int size, int* index) {
+  DCHECK(size > 0 && size <= kMaxNumBlocks);
+  int target = 0;
+  for (int i = size; i <= kMaxNumBlocks; i++) {
+    if (header_->empty[i - 1]) {
+      target = i;
+      break;
+    }
+  }
+
+  if (!target) {
     NOTREACHED();
     return false;
   }
@@ -144,10 +152,9 @@ void BlockHeader::DeleteMapBlock(int index, int size) {
 
 // Note that this is a simplified version of DeleteMapBlock().
 bool BlockHeader::UsedMapBlock(int index, int size) {
-  if (size < 0 || size > kMaxNumBlocks) {
-    NOTREACHED();
+  if (size < 0 || size > kMaxNumBlocks)
     return false;
-  }
+
   int byte_index = index / 8;
   uint8* byte_map = reinterpret_cast<uint8*>(header_->allocation_map);
   uint8 map_block = byte_map[byte_index];
@@ -177,7 +184,7 @@ void BlockHeader::FixAllocationCounters() {
   }
 }
 
-bool BlockHeader::NeedToGrowBlockFile(int block_count) {
+bool BlockHeader::NeedToGrowBlockFile(int block_count) const {
   bool have_space = false;
   int empty_blocks = 0;
   for (int i = 0; i < kMaxNumBlocks; i++) {
@@ -195,9 +202,19 @@ bool BlockHeader::NeedToGrowBlockFile(int block_count) {
   return !have_space;
 }
 
+bool BlockHeader::CanAllocate(int block_count) const {
+  DCHECK_GT(block_count, 0);
+  for (int i = block_count - 1; i < kMaxNumBlocks; i++) {
+    if (header_->empty[i])
+      return true;
+  }
+
+  return false;
+}
+
 int BlockHeader::EmptyBlocks() const {
   int empty_blocks = 0;
-  for (int i = 0; i < disk_cache::kMaxNumBlocks; i++) {
+  for (int i = 0; i < kMaxNumBlocks; i++) {
     empty_blocks += header_->empty[i] * (i + 1);
     if (header_->empty[i] < 0)
       return 0;
@@ -205,6 +222,14 @@ int BlockHeader::EmptyBlocks() const {
   return empty_blocks;
 }
 
+int BlockHeader::MinimumAllocations() const {
+  return header_->empty[kMaxNumBlocks - 1];
+}
+
+int BlockHeader::Capacity() const {
+  return header_->max_entries;
+}
+
 bool BlockHeader::ValidateCounters() const {
   if (header_->max_entries < 0 || header_->max_entries > kMaxBlocks ||
       header_->num_entries < 0)
@@ -217,10 +242,22 @@ bool BlockHeader::ValidateCounters() const {
   return true;
 }
 
+int BlockHeader::FileId() const {
+  return header_->this_file;
+}
+
+int BlockHeader::NextFileId() const {
+  return header_->next_file;
+}
+
 int BlockHeader::Size() const {
   return static_cast<int>(sizeof(*header_));
 }
 
+BlockFileHeader* BlockHeader::Header() {
+  return header_;
+}
+
 // ------------------------------------------------------------------------
 
 BlockFiles::BlockFiles(const base::FilePath& path)
@@ -260,7 +297,8 @@ bool BlockFiles::Init(bool create_files) {
 
 MappedFile* BlockFiles::GetFile(Addr address) {
   DCHECK(thread_checker_->CalledOnValidThread());
-  DCHECK(block_files_.size() >= 4);
+  DCHECK_GE(block_files_.size(),
+            static_cast<size_t>(kFirstAdditionalBlockFile));
   DCHECK(address.is_block_file() || !address.is_initialized());
   if (!address.is_initialized())
     return NULL;
@@ -272,16 +310,20 @@ MappedFile* BlockFiles::GetFile(Addr address) {
     if (!OpenBlockFile(file_index))
       return NULL;
   }
-  DCHECK(block_files_.size() >= static_cast<unsigned int>(file_index));
+  DCHECK_GE(block_files_.size(), static_cast<unsigned int>(file_index));
   return block_files_[file_index];
 }
 
 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)
+  DCHECK_NE(block_type, EXTERNAL);
+  DCHECK_NE(block_type, BLOCK_FILES);
+  DCHECK_NE(block_type, BLOCK_ENTRIES);
+  DCHECK_NE(block_type, BLOCK_EVICTED);
+  if (block_count < 1 || block_count > kMaxNumBlocks)
     return false;
+
   if (!init_)
     return false;
 
@@ -290,22 +332,13 @@ bool BlockFiles::CreateBlock(FileType block_type, int block_count,
     return false;
 
   ScopedFlush flush(file);
-  BlockHeader header(file);
+  BlockHeader file_header(file);
 
-  int target_size = 0;
-  for (int i = block_count; i <= 4; i++) {
-    if (header->empty[i - 1]) {
-      target_size = i;
-      break;
-    }
-  }
-
-  DCHECK(target_size);
   int index;
-  if (!header.CreateMapBlock(target_size, block_count, &index))
+  if (!file_header.CreateMapBlock(block_count, &index))
     return false;
 
-  Addr address(block_type, block_count, header->this_file, index);
+  Addr address(block_type, block_count, file_header.FileId(), index);
   block_address->set_value(address.value());
   Trace("CreateBlock 0x%x", address.value());
   return true;
@@ -332,15 +365,17 @@ void BlockFiles::DeleteBlock(Addr address, bool deep) {
   if (deep)
     file->Write(zero_buffer_, size, offset);
 
-  BlockHeader header(file);
-  header.DeleteMapBlock(address.start_block(), address.num_blocks());
+  BlockHeader file_header(file);
+  file_header.DeleteMapBlock(address.start_block(), address.num_blocks());
   file->Flush();
 
-  if (!header->num_entries) {
+  if (!file_header.Header()->num_entries) {
     // This file is now empty. Let's try to delete it.
-    FileType type = Addr::RequiredFileType(header->entry_size);
-    if (Addr::BlockSizeForFileType(RANKINGS) == header->entry_size)
+    FileType type = Addr::RequiredFileType(file_header.Header()->entry_size);
+    if (Addr::BlockSizeForFileType(RANKINGS) ==
+        file_header.Header()->entry_size) {
       type = RANKINGS;
+    }
     RemoveEmptyFile(type);  // Ignore failures.
   }
 }
@@ -450,13 +485,14 @@ bool BlockFiles::OpenBlockFile(int index) {
     return false;
   }
 
-  BlockHeader header(file.get());
+  BlockHeader file_header(file.get());
+  BlockFileHeader* header = file_header.Header();
   if (kBlockMagic != header->magic || kBlockVersion2 != header->version) {
     LOG(ERROR) << "Invalid file version or magic " << name.value();
     return false;
   }
 
-  if (header->updating || !header.ValidateCounters()) {
+  if (header->updating || !file_header.ValidateCounters()) {
     // Last instance was not properly shutdown, or counters are out of sync.
     if (!FixBlockFileHeader(file.get())) {
       LOG(ERROR) << "Unable to fix block file " << name.value();
@@ -516,19 +552,19 @@ bool BlockFiles::GrowBlockFile(MappedFile* file, BlockFileHeader* header) {
 MappedFile* BlockFiles::FileForNewBlock(FileType block_type, int block_count) {
   COMPILE_ASSERT(RANKINGS == 1, invalid_file_type);
   MappedFile* file = block_files_[block_type - 1];
-  BlockHeader header(file);
+  BlockHeader file_header(file);
 
   TimeTicks start = TimeTicks::Now();
-  while (header.NeedToGrowBlockFile(block_count)) {
-    if (kMaxBlocks == header->max_entries) {
+  while (file_header.NeedToGrowBlockFile(block_count)) {
+    if (kMaxBlocks == file_header.Header()->max_entries) {
       file = NextFile(file);
       if (!file)
         return NULL;
-      header = BlockHeader(file);
+      file_header = BlockHeader(file);
       continue;
     }
 
-    if (!GrowBlockFile(file, header.Get()))
+    if (!GrowBlockFile(file, file_header.Header()))
       return NULL;
     break;
   }
@@ -616,38 +652,39 @@ bool BlockFiles::RemoveEmptyFile(FileType block_type) {
 // DCHECK on header->updating because we may be fixing a crash.
 bool BlockFiles::FixBlockFileHeader(MappedFile* file) {
   ScopedFlush flush(file);
-  BlockHeader header(file);
+  BlockHeader file_header(file);
   int file_size = static_cast<int>(file->GetLength());
-  if (file_size < header.Size())
+  if (file_size < file_header.Size())
     return false;  // file_size > 2GB is also an error.
 
   const int kMinBlockSize = 36;
   const int kMaxBlockSize = 4096;
+  BlockFileHeader* header = file_header.Header();
   if (header->entry_size < kMinBlockSize ||
       header->entry_size > kMaxBlockSize || header->num_entries < 0)
     return false;
 
   // Make sure that we survive crashes.
   header->updating = 1;
-  int expected = header->entry_size * header->max_entries + header.Size();
+  int expected = header->entry_size * header->max_entries + file_header.Size();
   if (file_size != expected) {
-    int max_expected = header->entry_size * kMaxBlocks + header.Size();
+    int max_expected = header->entry_size * kMaxBlocks + file_header.Size();
     if (file_size < expected || header->empty[3] || file_size > max_expected) {
       NOTREACHED();
       LOG(ERROR) << "Unexpected file size";
       return false;
     }
     // We were in the middle of growing the file.
-    int num_entries = (file_size - header.Size()) / header->entry_size;
+    int num_entries = (file_size - file_header.Size()) / header->entry_size;
     header->max_entries = num_entries;
   }
 
-  header.FixAllocationCounters();
-  int empty_blocks = header.EmptyBlocks();
+  file_header.FixAllocationCounters();
+  int empty_blocks = file_header.EmptyBlocks();
   if (empty_blocks + header->num_entries > header->max_entries)
     header->num_entries = header->max_entries - empty_blocks;
 
-  if (!header.ValidateCounters())
+  if (!file_header.ValidateCounters())
     return false;
 
   header->updating = 0;
@@ -671,7 +708,7 @@ void BlockFiles::GetFileStats(int index, int* used_count, int* load) {
 
     max_blocks += header->max_entries;
     int used = header->max_entries;
-    for (int i = 0; i < 4; i++) {
+    for (int i = 0; i < kMaxNumBlocks; i++) {
       used -= header->empty[i] * (i + 1);
       DCHECK_GE(used, 0);
     }
diff --git a/net/disk_cache/block_files.h b/net/disk_cache/block_files.h
index 353c566..f8d5483 100644
--- a/net/disk_cache/block_files.h
+++ b/net/disk_cache/block_files.h
@@ -24,7 +24,11 @@ class ThreadChecker;
 namespace disk_cache {
 
 // An instance of this class represents the header of a block file in memory.
-// Note that this class doesn't perform any file operation.
+// Note that this class doesn't perform any file operation (as in it only deals
+// with entities in memory).
+// The header of a block file (and hence, this object) is all that is needed to
+// perform common operations like allocating or releasing space for storage;
+// actual access to that storage, however, is not performed through this class.
 class NET_EXPORT_PRIVATE BlockHeader {
  public:
   BlockHeader();
@@ -33,10 +37,9 @@ class NET_EXPORT_PRIVATE BlockHeader {
   BlockHeader(const BlockHeader& other);
   ~BlockHeader();
 
-  // Creates a new entry on the allocation map, updating the apropriate
-  // counters. |target| is the type of block to use (number of empty blocks),
-  // and |size| is the actual number of blocks to use.
-  bool CreateMapBlock(int target, int size, int* index);
+  // Creates a new entry of |size| blocks on the allocation map, updating the
+  // apropriate counters.
+  bool CreateMapBlock(int size, int* index);
 
   // Deletes the block pointed by |index|.
   void DeleteMapBlock(int index, int block_size);
@@ -49,20 +52,34 @@ class NET_EXPORT_PRIVATE BlockHeader {
 
   // Returns true if the current block file should not be used as-is to store
   // more records. |block_count| is the number of blocks to allocate.
-  bool NeedToGrowBlockFile(int block_count);
+  bool NeedToGrowBlockFile(int block_count) const;
+
+  // Returns true if this block file can be used to store an extra record of
+  // size |block_count|.
+  bool CanAllocate(int block_count) const;
 
   // Returns the number of empty blocks for this file.
   int EmptyBlocks() const;
 
+  // Returns the minumum number of allocations that can be satisfied.
+  int MinimumAllocations() const;
+
+  // Returns the number of blocks that this file can store.
+  int Capacity() const;
+
   // Returns true if the counters look OK.
   bool ValidateCounters() const;
 
+  // Returns the identifiers of this and the next file (0 if there is none).
+  int FileId() const;
+  int NextFileId() const;
+
   // Returns the size of the wrapped structure (BlockFileHeader).
   int Size() const;
 
-  BlockFileHeader* operator->() { return header_; }
-  void operator=(const BlockHeader& other) { header_ = other.header_; }
-  BlockFileHeader* Get() { return header_; }
+  // Returns a pointer to the underlying BlockFileHeader.
+  // TODO(rvargas): This may be removed with the support for V2.
+  BlockFileHeader* Header();
 
  private:
   BlockFileHeader* header_;
diff --git a/net/disk_cache/disk_format_base.h b/net/disk_cache/disk_format_base.h
index c8b7490..3198381 100644
--- a/net/disk_cache/disk_format_base.h
+++ b/net/disk_cache/disk_format_base.h
@@ -28,6 +28,7 @@ namespace disk_cache {
 typedef uint32 CacheAddr;
 
 const uint32 kBlockVersion2 = 0x20000;  // Version 2.0.
+const uint32 kBlockCurrentVersion = 0x30000;  // Version 3.0.
 
 const uint32 kBlockMagic = 0xC104CAC3;
 const int kBlockHeaderSize = 8192;  // Two pages: almost 64k entries
diff --git a/net/disk_cache/v3/block_bitmaps.cc b/net/disk_cache/v3/block_bitmaps.cc
index 0d0317b..b68ecdd 100644
--- a/net/disk_cache/v3/block_bitmaps.cc
+++ b/net/disk_cache/v3/block_bitmaps.cc
@@ -2,143 +2,73 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "net/disk_cache/block_files.h"
+#include "net/disk_cache/v3/block_bitmaps.h"
 
-#include "base/atomicops.h"
-#include "base/file_util.h"
 #include "base/metrics/histogram.h"
-#include "base/strings/string_util.h"
-#include "base/strings/stringprintf.h"
-#include "base/threading/thread_checker.h"
 #include "base/time/time.h"
-#include "net/disk_cache/cache_util.h"
-#include "net/disk_cache/file_lock.h"
+#include "net/disk_cache/disk_format_base.h"
 #include "net/disk_cache/trace.h"
 
 using base::TimeTicks;
 
 namespace disk_cache {
 
-BlockFiles::BlockFiles(const base::FilePath& path)
-    : init_(false), zero_buffer_(NULL), path_(path) {
+BlockBitmaps::BlockBitmaps() {
 }
 
-BlockFiles::~BlockFiles() {
-  if (zero_buffer_)
-    delete[] zero_buffer_;
-  CloseFiles();
+BlockBitmaps::~BlockBitmaps() {
 }
 
-bool BlockFiles::Init(bool create_files) {
-  DCHECK(!init_);
-  if (init_)
-    return false;
-
-  thread_checker_.reset(new base::ThreadChecker);
-
-  block_files_.resize(kFirstAdditionalBlockFile);
-  for (int i = 0; i < kFirstAdditionalBlockFile; i++) {
-    if (create_files)
-      if (!CreateBlockFile(i, static_cast<FileType>(i + 1), true))
-        return false;
-
-    if (!OpenBlockFile(i))
-      return false;
-
-    // Walk this chain of files removing empty ones.
-    if (!RemoveEmptyFile(static_cast<FileType>(i + 1)))
-      return false;
-  }
-
-  init_ = true;
-  return true;
+void BlockBitmaps::Init(const BlockFilesBitmaps& bitmaps) {
+  bitmaps_ = bitmaps;
 }
 
-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;
-  if (!init_)
+bool BlockBitmaps::CreateBlock(FileType block_type,
+                               int block_count,
+                               Addr* block_address) {
+  DCHECK_NE(block_type, EXTERNAL);
+  DCHECK_NE(block_type, RANKINGS);
+  if (block_count < 1 || block_count > kMaxNumBlocks)
     return false;
 
-  MappedFile* file = FileForNewBlock(block_type, block_count);
-  if (!file)
+  int header_num = HeaderNumberForNewBlock(block_type, block_count);
+  if (header_num < 0)
     return false;
 
-  ScopedFlush flush(file);
-  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-
-  int target_size = 0;
-  for (int i = block_count; i <= 4; i++) {
-    if (header->empty[i - 1]) {
-      target_size = i;
-      break;
-    }
-  }
-
-  DCHECK(target_size);
   int index;
-  if (!CreateMapBlock(target_size, block_count, header, &index))
+  if (!bitmaps_[header_num].CreateMapBlock(block_count, &index))
+    return false;
+
+  if (!index && (block_type == BLOCK_ENTRIES || block_type == BLOCK_EVICTED) &&
+      !bitmaps_[header_num].CreateMapBlock(block_count, &index)) {
+    // index 0 for entries is a reserved value.
     return false;
+  }
 
-  Addr address(block_type, block_count, header->this_file, index);
+  Addr address(block_type, block_count, bitmaps_[header_num].FileId(), 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());
+void BlockBitmaps::DeleteBlock(Addr address) {
   if (!address.is_initialized() || address.is_separate_file())
     return;
 
-  if (!zero_buffer_) {
-    zero_buffer_ = new char[Addr::BlockSizeForFileType(BLOCK_4K) * 4];
-    memset(zero_buffer_, 0, Addr::BlockSizeForFileType(BLOCK_4K) * 4);
-  }
-  MappedFile* file = GetFile(address);
-  if (!file)
+  int header_num = GetHeaderNumber(address);
+  if (header_num < 0)
     return;
 
   Trace("DeleteBlock 0x%x", address.value());
-
-  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);
-  file->Flush();
-
-  if (!header->num_entries) {
-    // This file is now empty. Let's try to delete it.
-    FileType type = Addr::RequiredFileType(header->entry_size);
-    if (Addr::BlockSizeForFileType(RANKINGS) == header->entry_size)
-      type = RANKINGS;
-    RemoveEmptyFile(type);  // Ignore failures.
-  }
+  bitmaps_[header_num].DeleteMapBlock(address.start_block(),
+                                      address.num_blocks());
 }
 
-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]) {
-      block_files_[i]->Release();
-      block_files_[i] = NULL;
-    }
-  }
-  block_files_.clear();
+void BlockBitmaps::Clear() {
+  bitmaps_.clear();
 }
 
-void BlockFiles::ReportStats() {
-  DCHECK(thread_checker_->CalledOnValidThread());
+void BlockBitmaps::ReportStats() {
   int used_blocks[kFirstAdditionalBlockFile];
   int load[kFirstAdditionalBlockFile];
   for (int i = 0; i < kFirstAdditionalBlockFile; i++) {
@@ -155,176 +85,92 @@ void BlockFiles::ReportStats() {
   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_3", load[3], 101);
 }
 
-bool BlockFiles::IsValid(Addr address) {
+bool BlockBitmaps::IsValid(Addr address) {
 #ifdef NDEBUG
   return true;
 #else
   if (!address.is_initialized() || address.is_separate_file())
     return false;
 
-  MappedFile* file = GetFile(address);
-  if (!file)
+  int header_num = GetHeaderNumber(address);
+  if (header_num < 0)
     return false;
 
-  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-  bool rv = UsedMapBlock(address.start_block(), address.num_blocks(), header);
+  bool rv = bitmaps_[header_num].UsedMapBlock(address.start_block(),
+                                              address.num_blocks());
   DCHECK(rv);
-
-  static bool read_contents = false;
-  if (read_contents) {
-    scoped_ptr<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
 }
 
-MappedFile* BlockFiles::GetFile(Addr address) {
-  DCHECK(thread_checker_->CalledOnValidThread());
-  DCHECK(block_files_.size() >= 4);
+int BlockBitmaps::GetHeaderNumber(Addr address) {
+  DCHECK_GE(bitmaps_.size(), static_cast<size_t>(kFirstAdditionalBlockFileV3));
   DCHECK(address.is_block_file() || !address.is_initialized());
   if (!address.is_initialized())
-    return NULL;
+    return -1;
 
   int file_index = address.FileNumber();
-  if (static_cast<unsigned int>(file_index) >= block_files_.size() ||
-      !block_files_[file_index]) {
-    // We need to open the file
-    if (!OpenBlockFile(file_index))
-      return NULL;
-  }
-  DCHECK(block_files_.size() >= static_cast<unsigned int>(file_index));
-  return block_files_[file_index];
-}
-
-bool BlockFiles::GrowBlockFile(MappedFile* file, BlockFileHeader* header) {
-  if (kMaxBlocks == header->max_entries)
-    return false;
-
-  ScopedFlush flush(file);
-  DCHECK(!header->empty[3]);
-  int new_size = header->max_entries + 1024;
-  if (new_size > kMaxBlocks)
-    new_size = kMaxBlocks;
-
-  int new_size_bytes = new_size * header->entry_size + sizeof(*header);
-
-  if (!file->SetLength(new_size_bytes)) {
-    // Most likely we are trying to truncate the file, so the header is wrong.
-    if (header->updating < 10 && !FixBlockFileHeader(file)) {
-      // If we can't fix the file increase the lock guard so we'll pick it on
-      // the next start and replace it.
-      header->updating = 100;
-      return false;
-    }
-    return (header->max_entries >= new_size);
-  }
+  if (static_cast<unsigned int>(file_index) >= bitmaps_.size())
+    return -1;
 
-  FileLock lock(header);
-  header->empty[3] = (new_size - header->max_entries) / 4;  // 4 blocks entries
-  header->max_entries = new_size;
-
-  return true;
+  return file_index;
 }
 
-MappedFile* BlockFiles::FileForNewBlock(FileType block_type, int block_count) {
-  COMPILE_ASSERT(RANKINGS == 1, invalid_file_type);
-  MappedFile* file = block_files_[block_type - 1];
-  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
+int BlockBitmaps::HeaderNumberForNewBlock(FileType block_type,
+                                          int block_count) {
+  DCHECK_GT(block_type, 0);
+  int header_num = block_type - 1;
+  bool found = true;
 
   TimeTicks start = TimeTicks::Now();
-  while (NeedToGrowBlockFile(header, block_count)) {
-    if (kMaxBlocks == header->max_entries) {
-      file = NextFile(file);
-      if (!file)
-        return NULL;
-      header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-      continue;
+  while (bitmaps_[header_num].NeedToGrowBlockFile(block_count)) {
+    header_num = bitmaps_[header_num].NextFileId();
+    if (!header_num) {
+      found = false;
+      break;
     }
-
-    if (!GrowBlockFile(file, header))
-      return NULL;
-    break;
   }
-  HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", TimeTicks::Now() - start);
-  return file;
-}
 
-// Note that we expect to be called outside of a FileLock... however, we cannot
-// DCHECK on header->updating because we may be fixing a crash.
-bool BlockFiles::FixBlockFileHeader(MappedFile* file) {
-  ScopedFlush flush(file);
-  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-  int file_size = static_cast<int>(file->GetLength());
-  if (file_size < static_cast<int>(sizeof(*header)))
-    return false;  // file_size > 2GB is also an error.
-
-  const int kMinBlockSize = 36;
-  const int kMaxBlockSize = 4096;
-  if (header->entry_size < kMinBlockSize ||
-      header->entry_size > kMaxBlockSize || header->num_entries < 0)
-    return false;
-
-  // Make sure that we survive crashes.
-  header->updating = 1;
-  int expected = header->entry_size * header->max_entries + sizeof(*header);
-  if (file_size != expected) {
-    int max_expected = header->entry_size * kMaxBlocks + sizeof(*header);
-    if (file_size < expected || header->empty[3] || file_size > max_expected) {
-      NOTREACHED();
-      LOG(ERROR) << "Unexpected file size";
-      return false;
-    }
-    // We were in the middle of growing the file.
-    int num_entries = (file_size - sizeof(*header)) / header->entry_size;
-    header->max_entries = num_entries;
+  if (!found) {
+    // Restart the search, looking for any file with space. We know that all
+    // files of this type are low on free blocks, but we cannot grow any file
+    // at this time.
+    header_num = block_type - 1;
+    do {
+      if (bitmaps_[header_num].CanAllocate(block_count)) {
+        found = true;  // Make sure file 0 is not mistaken with a failure.
+        break;
+      }
+      header_num = bitmaps_[header_num].NextFileId();
+    } while (header_num);
+
+    if (!found)
+      header_num = -1;
   }
 
-  FixAllocationCounters(header);
-  int empty_blocks = EmptyBlocks(header);
-  if (empty_blocks + header->num_entries > header->max_entries)
-    header->num_entries = header->max_entries - empty_blocks;
-
-  if (!ValidateCounters(header))
-    return false;
-
-  header->updating = 0;
-  return true;
+  HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", TimeTicks::Now() - start);
+  return header_num;
 }
 
 // We are interested in the total number of blocks used by this file type, and
 // the max number of blocks that we can store (reported as the percentage of
 // used blocks). In order to find out the number of used blocks, we have to
 // substract the empty blocks from the total blocks for each file in the chain.
-void BlockFiles::GetFileStats(int index, int* used_count, int* load) {
+void BlockBitmaps::GetFileStats(int index, int* used_count, int* load) {
   int max_blocks = 0;
   *used_count = 0;
   *load = 0;
-  for (;;) {
-    if (!block_files_[index] && !OpenBlockFile(index))
-      return;
-
-    BlockFileHeader* header =
-        reinterpret_cast<BlockFileHeader*>(block_files_[index]->buffer());
-
-    max_blocks += header->max_entries;
-    int used = header->max_entries;
-    for (int i = 0; i < 4; i++) {
-      used -= header->empty[i] * (i + 1);
-      DCHECK_GE(used, 0);
-    }
+  do {
+    int capacity = bitmaps_[index].Capacity();
+    int used = capacity - bitmaps_[index].EmptyBlocks();
+    DCHECK_GE(used, 0);
+
+    max_blocks += capacity;
     *used_count += used;
 
-    if (!header->next_file)
-      break;
-    index = header->next_file;
-  }
+    index = bitmaps_[index].NextFileId();
+  } while (index);
+
   if (max_blocks)
     *load = *used_count * 100 / max_blocks;
 }
diff --git a/net/disk_cache/v3/block_bitmaps.h b/net/disk_cache/v3/block_bitmaps.h
index eaf8760..111d57b 100644
--- a/net/disk_cache/v3/block_bitmaps.h
+++ b/net/disk_cache/v3/block_bitmaps.h
@@ -4,43 +4,39 @@
 
 // See net/disk_cache/disk_cache.h for the public interface.
 
-#ifndef NET_DISK_CACHE_BLOCK_FILES_H_
-#define NET_DISK_CACHE_BLOCK_FILES_H_
-
-#include <vector>
+#ifndef NET_DISK_CACHE_V3_BLOCK_BITMAPS_H_
+#define NET_DISK_CACHE_V3_BLOCK_BITMAPS_H_
 
 #include "base/files/file_path.h"
-#include "base/gtest_prod_util.h"
-#include "base/memory/scoped_ptr.h"
 #include "net/base/net_export.h"
 #include "net/disk_cache/addr.h"
-#include "net/disk_cache/mapped_file.h"
+#include "net/disk_cache/block_files.h"
 
 namespace disk_cache {
 
-// This class handles the set of block-files open by the disk cache.
-class NET_EXPORT_PRIVATE BlockFiles {
+class BackendImplV3;
+
+// This class is the interface in the v3 disk cache to the set of files holding
+// cached data that is small enough to not be efficiently stored in a dedicated
+// file (i.e. < kMaxBlockSize). It is primarily used to allocate and free
+// regions in those files used to store data.
+class NET_EXPORT_PRIVATE BlockBitmaps {
  public:
-  explicit BlockFiles(const base::FilePath& path);
-  ~BlockFiles();
+  BlockBitmaps();
+  ~BlockBitmaps();
 
-  // Performs the object initialization. create_files indicates if the backing
-  // files should be created or just open.
-  bool Init(bool create_files);
+  void Init(const BlockFilesBitmaps& bitmaps);
 
   // Creates a new entry on a block file. block_type indicates the size of block
   // to be used (as defined on cache_addr.h), block_count is the number of
   // blocks to allocate, and block_address is the address of the new entry.
   bool CreateBlock(FileType block_type, int block_count, Addr* block_address);
 
-  // Removes an entry from the block files. If deep is true, the storage is zero
-  // filled; otherwise the entry is removed but the data is not altered (must be
-  // already zeroed).
-  void DeleteBlock(Addr address, bool deep);
+  // Removes an entry from the block files.
+  void DeleteBlock(Addr address);
 
-  // Close all the files and set the internal state to be initializad again. The
-  // cache is being purged.
-  void CloseFiles();
+  // Releases the internal bitmaps. The cache is being purged.
+  void Clear();
 
   // Sends UMA stats.
   void ReportStats();
@@ -50,26 +46,20 @@ class NET_EXPORT_PRIVATE BlockFiles {
   bool IsValid(Addr address);
 
  private:
-  // Returns the file that stores a given address.
-  MappedFile* GetFile(Addr address);
-
-  // Attemp to grow this file. Fails if the file cannot be extended anymore.
-  bool GrowBlockFile(MappedFile* file, BlockFileHeader* header);
-
-  // Returns the appropriate file to use for a new block.
-  MappedFile* FileForNewBlock(FileType block_type, int block_count);
+  // Returns the header number that stores a given address.
+  int GetHeaderNumber(Addr address);
 
-  // Restores the header of a potentially inconsistent file.
-  bool FixBlockFileHeader(MappedFile* file);
+  // Returns the appropriate header to use for a new block.
+  int HeaderNumberForNewBlock(FileType block_type, int block_count);
 
   // Retrieves stats for the given file index.
   void GetFileStats(int index, int* used_count, int* load);
 
-  bool init_;
+  BlockFilesBitmaps bitmaps_;
 
-  DISALLOW_COPY_AND_ASSIGN(BlockFiles);
+  DISALLOW_COPY_AND_ASSIGN(BlockBitmaps);
 };
 
 }  // namespace disk_cache
 
-#endif  // NET_DISK_CACHE_BLOCK_FILES_H_
+#endif  // NET_DISK_CACHE_V3_BLOCK_BITMAPS_H_
diff --git a/net/disk_cache/v3/block_bitmaps_unittest.cc b/net/disk_cache/v3/block_bitmaps_unittest.cc
index fa7c5db..981bdec 100644
--- a/net/disk_cache/v3/block_bitmaps_unittest.cc
+++ b/net/disk_cache/v3/block_bitmaps_unittest.cc
@@ -2,342 +2,64 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "base/file_util.h"
-#include "base/files/file_enumerator.h"
+#include "net/disk_cache/addr.h"
 #include "net/disk_cache/block_files.h"
-#include "net/disk_cache/disk_cache.h"
-#include "net/disk_cache/disk_cache_test_base.h"
-#include "net/disk_cache/disk_cache_test_util.h"
+#include "net/disk_cache/disk_format_base.h"
+#include "net/disk_cache/v3/block_bitmaps.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
-using base::Time;
-
-namespace {
-
-// Returns the number of files in this folder.
-int NumberOfFiles(const base::FilePath& path) {
-  base::FileEnumerator iter(path, false, base::FileEnumerator::FILES);
-  int count = 0;
-  for (base::FilePath file = iter.Next(); !file.value().empty();
-       file = iter.Next()) {
-    count++;
-  }
-  return count;
-}
-
-}  // namespace;
-
-namespace disk_cache {
-
-TEST_F(DiskCacheTest, BlockFiles_Grow) {
-  ASSERT_TRUE(CleanupCacheDir());
-  ASSERT_TRUE(file_util::CreateDirectory(cache_path_));
-
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(true));
-
-  const int kMaxSize = 35000;
-  Addr address[kMaxSize];
-
-  // Fill up the 32-byte block file (use three files).
-  for (int i = 0; i < kMaxSize; i++) {
-    EXPECT_TRUE(files.CreateBlock(RANKINGS, 4, &address[i]));
-  }
-  EXPECT_EQ(6, NumberOfFiles(cache_path_));
-
-  // Make sure we don't keep adding files.
-  for (int i = 0; i < kMaxSize * 4; i += 2) {
-    int target = i % kMaxSize;
-    files.DeleteBlock(address[target], false);
-    EXPECT_TRUE(files.CreateBlock(RANKINGS, 4, &address[target]));
-  }
-  EXPECT_EQ(6, NumberOfFiles(cache_path_));
-}
-
-// We should be able to delete empty block files.
-TEST_F(DiskCacheTest, BlockFiles_Shrink) {
-  ASSERT_TRUE(CleanupCacheDir());
-  ASSERT_TRUE(file_util::CreateDirectory(cache_path_));
-
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(true));
-
-  const int kMaxSize = 35000;
-  Addr address[kMaxSize];
-
-  // Fill up the 32-byte block file (use three files).
-  for (int i = 0; i < kMaxSize; i++) {
-    EXPECT_TRUE(files.CreateBlock(RANKINGS, 4, &address[i]));
-  }
-
-  // Now delete all the blocks, so that we can delete the two extra files.
-  for (int i = 0; i < kMaxSize; i++) {
-    files.DeleteBlock(address[i], false);
-  }
-  EXPECT_EQ(4, NumberOfFiles(cache_path_));
-}
-
-// Handling of block files not properly closed.
-TEST_F(DiskCacheTest, BlockFiles_Recover) {
-  ASSERT_TRUE(CleanupCacheDir());
-  ASSERT_TRUE(file_util::CreateDirectory(cache_path_));
-
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(true));
-
-  const int kNumEntries = 2000;
-  CacheAddr entries[kNumEntries];
-
-  int seed = static_cast<int>(Time::Now().ToInternalValue());
-  srand(seed);
-  for (int i = 0; i < kNumEntries; i++) {
-    Addr address(0);
-    int size = (rand() % 4) + 1;
-    EXPECT_TRUE(files.CreateBlock(RANKINGS, size, &address));
-    entries[i] = address.value();
-  }
-
-  for (int i = 0; i < kNumEntries; i++) {
-    int source1 = rand() % kNumEntries;
-    int source2 = rand() % kNumEntries;
-    CacheAddr temp = entries[source1];
-    entries[source1] = entries[source2];
-    entries[source2] = temp;
-  }
-
-  for (int i = 0; i < kNumEntries / 2; i++) {
-    Addr address(entries[i]);
-    files.DeleteBlock(address, false);
-  }
-
-  // At this point, there are kNumEntries / 2 entries on the file, randomly
-  // distributed both on location and size.
-
-  Addr address(entries[kNumEntries / 2]);
-  MappedFile* file = files.GetFile(address);
-  ASSERT_TRUE(NULL != file);
-
-  BlockFileHeader* header =
-      reinterpret_cast<BlockFileHeader*>(file->buffer());
-  ASSERT_TRUE(NULL != header);
-
-  ASSERT_EQ(0, header->updating);
-
-  int max_entries = header->max_entries;
-  int empty_1 = header->empty[0];
-  int empty_2 = header->empty[1];
-  int empty_3 = header->empty[2];
-  int empty_4 = header->empty[3];
-
-  // Corrupt the file.
-  header->max_entries = header->empty[0] = 0;
-  header->empty[1] = header->empty[2] = header->empty[3] = 0;
-  header->updating = -1;
-
-  files.CloseFiles();
-
-  ASSERT_TRUE(files.Init(false));
-
-  // The file must have been fixed.
-  file = files.GetFile(address);
-  ASSERT_TRUE(NULL != file);
-
-  header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-  ASSERT_TRUE(NULL != header);
-
-  ASSERT_EQ(0, header->updating);
-
-  EXPECT_EQ(max_entries, header->max_entries);
-  EXPECT_EQ(empty_1, header->empty[0]);
-  EXPECT_EQ(empty_2, header->empty[1]);
-  EXPECT_EQ(empty_3, header->empty[2]);
-  EXPECT_EQ(empty_4, header->empty[3]);
-}
-
-// Handling of truncated files.
-TEST_F(DiskCacheTest, BlockFiles_ZeroSizeFile) {
-  ASSERT_TRUE(CleanupCacheDir());
-  ASSERT_TRUE(file_util::CreateDirectory(cache_path_));
-
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(true));
-
-  base::FilePath filename = files.Name(0);
-  files.CloseFiles();
-  // Truncate one of the files.
-  {
-    scoped_refptr<File> file(new File);
-    ASSERT_TRUE(file->Init(filename));
-    EXPECT_TRUE(file->SetLength(0));
-  }
-
-  // Initializing should fail, not crash.
-  ASSERT_FALSE(files.Init(false));
-}
-
-// Handling of truncated files (non empty).
-TEST_F(DiskCacheTest, BlockFiles_TruncatedFile) {
-  ASSERT_TRUE(CleanupCacheDir());
-  ASSERT_TRUE(file_util::CreateDirectory(cache_path_));
-
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(true));
-  Addr address;
-  EXPECT_TRUE(files.CreateBlock(RANKINGS, 2, &address));
-
-  base::FilePath filename = files.Name(0);
-  files.CloseFiles();
-  // Truncate one of the files.
-  {
-    scoped_refptr<File> file(new File);
-    ASSERT_TRUE(file->Init(filename));
-    EXPECT_TRUE(file->SetLength(15000));
-  }
-
-  // Initializing should fail, not crash.
-  ASSERT_FALSE(files.Init(false));
-}
-
-// Tests detection of out of sync counters.
-TEST_F(DiskCacheTest, BlockFiles_Counters) {
-  ASSERT_TRUE(CleanupCacheDir());
-  ASSERT_TRUE(file_util::CreateDirectory(cache_path_));
-
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(true));
-
-  // Create a block of size 2.
-  Addr address(0);
-  EXPECT_TRUE(files.CreateBlock(RANKINGS, 2, &address));
-
-  MappedFile* file = files.GetFile(address);
-  ASSERT_TRUE(NULL != file);
-
-  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-  ASSERT_TRUE(NULL != header);
-  ASSERT_EQ(0, header->updating);
-
-  // Alter the counters so that the free space doesn't add up.
-  header->empty[2] = 50;  // 50 free blocks of size 3.
-  files.CloseFiles();
-
-  ASSERT_TRUE(files.Init(false));
-  file = files.GetFile(address);
-  ASSERT_TRUE(NULL != file);
-  header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-  ASSERT_TRUE(NULL != header);
-
-  // The file must have been fixed.
-  ASSERT_EQ(0, header->empty[2]);
-
-  // Change the number of entries.
-  header->num_entries = 3;
-  header->updating = 1;
-  files.CloseFiles();
-
-  ASSERT_TRUE(files.Init(false));
-  file = files.GetFile(address);
-  ASSERT_TRUE(NULL != file);
-  header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-  ASSERT_TRUE(NULL != header);
-
-  // The file must have been "fixed".
-  ASSERT_EQ(2, header->num_entries);
-
-  // Change the number of entries.
-  header->num_entries = -1;
-  header->updating = 1;
-  files.CloseFiles();
-
-  // Detect the error.
-  ASSERT_FALSE(files.Init(false));
-}
-
-// An invalid file can be detected after init.
-TEST_F(DiskCacheTest, BlockFiles_InvalidFile) {
-  ASSERT_TRUE(CleanupCacheDir());
-  ASSERT_TRUE(file_util::CreateDirectory(cache_path_));
-
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(true));
-
-  // Let's access block 10 of file 5. (There is no file).
-  Addr addr(BLOCK_256, 1, 5, 10);
-  EXPECT_TRUE(NULL == files.GetFile(addr));
-
-  // Let's create an invalid file.
-  base::FilePath filename(files.Name(5));
-  char header[kBlockHeaderSize];
-  memset(header, 'a', kBlockHeaderSize);
-  EXPECT_EQ(kBlockHeaderSize,
-            file_util::WriteFile(filename, header, kBlockHeaderSize));
-
-  EXPECT_TRUE(NULL == files.GetFile(addr));
-
-  // The file should not have been changed (it is still invalid).
-  EXPECT_TRUE(NULL == files.GetFile(addr));
-}
-
-// Tests that we generate the correct file stats.
-TEST_F(DiskCacheTest, BlockFiles_Stats) {
-  ASSERT_TRUE(CopyTestCache("remove_load1"));
-
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(false));
-  int used, load;
-
-  files.GetFileStats(0, &used, &load);
-  EXPECT_EQ(101, used);
-  EXPECT_EQ(9, load);
-
-  files.GetFileStats(1, &used, &load);
-  EXPECT_EQ(203, used);
-  EXPECT_EQ(19, load);
-
-  files.GetFileStats(2, &used, &load);
-  EXPECT_EQ(0, used);
-  EXPECT_EQ(0, load);
-}
-
 // Tests that we add and remove blocks correctly.
-TEST_F(DiskCacheTest, AllocationMap) {
-  ASSERT_TRUE(CleanupCacheDir());
-  ASSERT_TRUE(file_util::CreateDirectory(cache_path_));
+TEST(DiskCacheBlockBitmaps, V3AllocationMap) {
+  disk_cache::BlockBitmaps block_bitmaps;
+  disk_cache::BlockFilesBitmaps bitmaps;
+
+  const int kNumHeaders = 10;
+  disk_cache::BlockFileHeader headers[kNumHeaders];
+  for (int i = 0; i < kNumHeaders; i++) {
+    memset(&headers[i], 0, sizeof(headers[i]));
+    headers[i].magic = disk_cache::kBlockMagic;
+    headers[i].version = disk_cache::kBlockCurrentVersion;
+    headers[i].this_file = static_cast<int16>(i);
+    headers[i].empty[3] = 200;
+    headers[i].max_entries = 800;
+    bitmaps.push_back(disk_cache::BlockHeader(&headers[i]));
+  }
 
-  BlockFiles files(cache_path_);
-  ASSERT_TRUE(files.Init(true));
+  block_bitmaps.Init(bitmaps);
 
   // Create a bunch of entries.
   const int kSize = 100;
-  Addr address[kSize];
+  disk_cache::Addr address[kSize];
   for (int i = 0; i < kSize; i++) {
     SCOPED_TRACE(i);
     int block_size = i % 4 + 1;
-    EXPECT_TRUE(files.CreateBlock(BLOCK_1K, block_size, &address[i]));
-    EXPECT_EQ(BLOCK_1K, address[i].file_type());
+    ASSERT_TRUE(block_bitmaps.CreateBlock(disk_cache::BLOCK_1K, block_size,
+                                          &address[i]));
+    EXPECT_EQ(disk_cache::BLOCK_1K, address[i].file_type());
     EXPECT_EQ(block_size, address[i].num_blocks());
     int start = address[i].start_block();
+
+    // Verify that the allocated entry doesn't cross a 4 block boundary.
     EXPECT_EQ(start / 4, (start + block_size - 1) / 4);
   }
 
   for (int i = 0; i < kSize; i++) {
     SCOPED_TRACE(i);
-    EXPECT_TRUE(files.IsValid(address[i]));
+    EXPECT_TRUE(block_bitmaps.IsValid(address[i]));
   }
 
   // The first part of the allocation map should be completely filled. We used
-  // 10 bits per each four entries, so 250 bits total.
-  BlockFileHeader* header =
-      reinterpret_cast<BlockFileHeader*>(files.GetFile(address[0])->buffer());
-  uint8* buffer = reinterpret_cast<uint8*>(&header->allocation_map);
-  for (int i =0; i < 29; i++) {
+  // 10 bits per each of four entries, so 250 bits total. All entries should go
+  // to the third file.
+  uint8* buffer = reinterpret_cast<uint8*>(&headers[2].allocation_map);
+  for (int i = 0; i < 29; i++) {
     SCOPED_TRACE(i);
     EXPECT_EQ(0xff, buffer[i]);
   }
 
   for (int i = 0; i < kSize; i++) {
     SCOPED_TRACE(i);
-    files.DeleteBlock(address[i], false);
+    block_bitmaps.DeleteBlock(address[i]);
   }
 
   // The allocation map should be empty.
@@ -346,5 +68,3 @@ TEST_F(DiskCacheTest, AllocationMap) {
     EXPECT_EQ(0, buffer[i]);
   }
 }
-
-}  // namespace disk_cache