Disk cache: Introduce BlockBitmaps for V3.

net/disk_cache/v3/block_bitmaps.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 "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.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_)
+void BlockBitmaps::Init(const BlockFilesBitmaps& bitmaps) {
+  bitmaps_ = bitmaps;
+}
+
+bool BlockBitmaps::CreateBlock(FileType block_type,
+                               int block_count,
+                               Addr* block_address) {
+  if (block_type < BLOCK_256 || block_count < 1 || block_count > kMaxNumBlocks)

[gavinp, 2013/06/28 21:47:45]

block_type < BLOCK_256 is hard for me to understand. Could we do that test
instead with equality comparisons, so the list of invalid types is in the test?

     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;
-}
-
-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_)
+  int header_num = HeaderNumberForNewBlock(block_type, block_count);
+  if (header_num < 0)
     return false;
 
-  MappedFile* file = FileForNewBlock(block_type, block_count);
-  if (!file)
-    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]) {
+  for (int i = block_count; i <= kMaxNumBlocks; i++) {
+    if (bitmaps_[header_num]->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(target_size, block_count, &index))
     return false;
 
-  Addr address(block_type, block_count, header->this_file, index);
+  if (!index && (block_type == BLOCK_ENTRIES || block_type == BLOCK_EVICTED) &&
+      !bitmaps_[header_num].CreateMapBlock(target_size, block_count, &index)) {
+    // index 0 for entries is a reserved value.
+    return false;
+  }
+
+  Addr address(block_type, block_count, bitmaps_[header_num]->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());
+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)

[gavinp, 2013/06/28 21:47:45]

Why isn't this a DCHECK?

[rvargas (doing something else), 2013/07/11 19:54:55]

Same reason I mentioned before: (this way) DeleteBlock can be called with an
address that doesn't contain data (or is not even the address of a block) and if
there's nothing to do this function doesn't do anything.

That behavior is valuable when cleaning up a mess.

     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++) {
     GetFileStats(i, &used_blocks[i], &load[i]);
   }
   UMA_HISTOGRAM_COUNTS("DiskCache.Blocks_0", used_blocks[0]);
   UMA_HISTOGRAM_COUNTS("DiskCache.Blocks_1", used_blocks[1]);
   UMA_HISTOGRAM_COUNTS("DiskCache.Blocks_2", used_blocks[2]);
   UMA_HISTOGRAM_COUNTS("DiskCache.Blocks_3", used_blocks[3]);
 
   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_0", load[0], 101);
   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_1", load[1], 101);
   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_2", load[2], 101);
   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(bitmaps_.size() >= 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;
+  if (static_cast<unsigned int>(file_index) >= bitmaps_.size() ||
+      !bitmaps_[file_index].Get()) {
+    return -1;
   }
-  DCHECK(block_files_.size() >= static_cast<unsigned int>(file_index));
-  return block_files_[file_index];
+  DCHECK(bitmaps_.size() >= static_cast<unsigned int>(file_index));
+  return file_index;
 }
 
-bool BlockFiles::GrowBlockFile(MappedFile* file, BlockFileHeader* header) {
-  if (kMaxBlocks == header->max_entries)
-    return false;
+int BlockBitmaps::HeaderNumberForNewBlock(FileType block_type,
+                                          int block_count) {
+  COMPILE_ASSERT(RANKINGS == 1, invalid_file_type);

[gavinp, 2013/06/28 21:47:45]

What does this do?

[rvargas (doing something else), 2013/07/11 19:54:55]

Makes sure that the next line doesn't result in a negative number. To be honest,
this was mostly for a reader thinking that we may end up using a negative index.

I'm sad Rietveld is not doing a better job showing actual changes, but this
function should have been aligned with line 236 of the old file.

[gavinp, 2013/07/15 18:23:35]

Why not:

DCHECK_GT(0, block_type);

I'm at least one reader who would get that more easily than a discussion of the
ordering of the FileType enum, which is what the COMPILE_ASSERT ends up being.

+  int header_num = block_type - 1;
+  bool found = true;
 
-  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;
+  TimeTicks start = TimeTicks::Now();
+  while (bitmaps_[header_num].NeedToGrowBlockFile(block_count)) {
+    header_num = bitmaps_[header_num]->next_file;
+    if (!header_num) {
+      found = false;
+      break;
     }
-    return (header->max_entries >= new_size);
   }
 
-  FileLock lock(header);
-  header->empty[3] = (new_size - header->max_entries) / 4;  // 4 blocks entries
-  header->max_entries = new_size;
-
-  return true;
-}
-
-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());
-
-  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;
+  if (!found) {
+    // Restart the search, looking for any file with space.
+    header_num = block_type - 1;
+    do {
+      if (bitmaps_[header_num].CanAllocate(block_count))
+        found = true;
+      else
+        header_num = bitmaps_[header_num]->next_file;
+    } while (header_num && !found);
+    if (!found) {

[gavinp, 2013/06/28 21:47:45]

It took me a few passes to understand the logic of the nested loop here; the use
of "found" in the test inside of the test, and the assertion/test confused me.

Is this code equivalent:

do {
  if (bitmaps_[header_num].CanAllocate(block_count))
    break;
  header_num = bitmaps_[header_num]->next_file;
} while (header_num);
if (!header_num)
  header_num = -1;

[rvargas (doing something else), 2013/07/11 19:54:55]

Yes and no. In general it is not the same because we may start looking at the
first file (header_num = 0), and find space... which would make us think that we
failed to find space.

It can be the same if we ignore the general case and assume that this code will
never be called with block_type = RANKINGS... that condition is true today, but
it may become false in the future after we delete the code for V2 and may decide
to reuse that file type for something else. I didn't want to restrict this code
that way.

I can add a comment to point out why it looks this way.

[gavinp, 2013/07/15 18:23:35]

The two loops could be made a lot more clear if we renamed
"NeedToGrowBlockFile". Maybe "NeedToGrowBlockFileToStoreThisManyMoreBlocks ?
Once I went and reread the definition things made a bit more sense to me. Or
perhaps expand the comment right in "if (!found)", what weren't we searching
before?

+      NOTREACHED();

[gavinp, 2013/06/28 21:47:45]

This scares me a bit. Is this an assertion, or an error case? It is coded as
both.

[rvargas (doing something else), 2013/07/11 19:54:55]

Not that uncommon pattern. It is an assertion in that tests or developer
versions should break into a debugger if this happens. On the other hand, I
expect a reasonable action if this happens on the field... as in creation of the
current entry to fail.

[gavinp, 2013/07/15 18:23:35]

Why not crash in the field? If this is impossible (a DCHECK), then the crash
will be really diagnostic, right?

[rvargas (doing something else), 2013/08/05 19:50:45]

I din't say it was impossible to get here. All is needed is to get really behind
growing the files. That's no reason to crash the whole browser.

[gavinp, 2013/08/06 01:11:02]

Aha, so should this be a DLOG, then. Recall that the Chomium style guide says
that "you should not handle DCHECK() failures." This code is handling a DCHECK
failure.

+      header_num = -1;
     }
-
-    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;
   }
 
-  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);

[gavinp, 2013/06/28 21:47:45]

Should we be separating out v3 histograms by name? This histogram is strongly
parallel to an existing one, but I'm not seeing the benefit of mixing them. What
do you think?

[rvargas (doing something else), 2013/07/11 19:54:55]

This histogram is exactly the same one as before and I see no reason to rename
it. In the short term we can tell them apart by version and or experiment.

+  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());
+    BlockFileHeader* header = bitmaps_[index].Get();
 
     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);
     }
     *used_count += used;
 
     if (!header->next_file)
       break;
     index = header->next_file;
   }
   if (max_blocks)
     *load = *used_count * 100 / max_blocks;
 }
 
 }  // namespace disk_cache