Disk cache: Introduce BlockBitmaps for V3.

net/disk_cache/block_files.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 "base/atomicops.h"
 #include "base/files/file_path.h"
 #include "base/metrics/histogram.h"
 #include "base/strings/string_util.h"
@@ skipping 159 matching lines @@
     uint32 map_block = header_->allocation_map[i];
 
     for (int j = 0; j < 8; j++, map_block >>= 4) {
       int type = GetMapBlockType(map_block);
       if (type)
         header_->empty[type -1]++;
     }
   }
 }
 
-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++) {
     empty_blocks += header_->empty[i] * (i + 1);
     if (i >= block_count - 1 && header_->empty[i])
       have_space = true;
   }
 
   if (header_->next_file && (empty_blocks < kMaxBlocks / 10)) {
     // This file is almost full but we already created another one, don't use
     // this file yet so that it is easier to find empty blocks when we start
     // using this file again.
     return true;
   }
   return !have_space;
 }
 
+bool BlockHeader::CanAllocate(int block_count) const {
+  for (int i = 0; i < kMaxNumBlocks; i++) {

[gavinp, 2013/08/05 17:06:15]

I did a real double take reading this loop. Why do we initialize i = 0 and not
with block_count - 1?

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

To avoid a negative values?

done

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

Is it possible for block_count to have a zero or negative value? Should that be
a DCHECK?

[rvargas (doing something else), 2013/08/08 02:50:01]

Do you mean like the first line of this method (on the version posted when I
sent this comment)

+    if (i >= (block_count - 1) && header_->empty[i])
+      return true;
+  }
+
+  return false;
+}
+
 int BlockHeader::EmptyBlocks() const {
   int empty_blocks = 0;
   for (int i = 0; i < disk_cache::kMaxNumBlocks; i++) {
     empty_blocks += header_->empty[i] * (i + 1);
     if (header_->empty[i] < 0)
       return 0;
   }
   return empty_blocks;
 }
 
 bool BlockHeader::ValidateCounters() const {
   if (header_->max_entries < 0 || header_->max_entries > kMaxBlocks ||
       header_->num_entries < 0)
     return false;
 
   int empty_blocks = EmptyBlocks();
   if (empty_blocks + header_->num_entries > header_->max_entries)
     return false;
 
   return true;
 }
 
 int BlockHeader::Size() const {
   return static_cast<int>(sizeof(*header_));
 }
 
+BlockFileHeader* BlockHeader::Header() {
+  return header_;
+}
+
 // ------------------------------------------------------------------------
 
 BlockFiles::BlockFiles(const base::FilePath& path)
     : init_(false), zero_buffer_(NULL), path_(path) {
 }
 
 BlockFiles::~BlockFiles() {
   if (zero_buffer_)
     delete[] zero_buffer_;
   CloseFiles();
@@ skipping 19 matching lines @@
     if (!RemoveEmptyFile(static_cast<FileType>(i + 1)))
       return false;
   }
 
   init_ = true;
   return true;
 }
 
 MappedFile* BlockFiles::GetFile(Addr address) {
   DCHECK(thread_checker_->CalledOnValidThread());
-  DCHECK(block_files_.size() >= 4);
+  DCHECK_GE(block_files_.size(),

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

Convention is to put the constant first, and the thing being tested second, so
this needs to be reversed into a DCHECK_LE.

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

I believe you are confusing the requirements of EXPECT_LE with the one of
DCHECK_LE.

The test macros expect the first argument to be the constant value. On the other
hand, the recommended convention for the runtime macros is to follow the pattern
used when coding (and that means make the code more readable, usually by having
the constant after the variable)

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

I am not aware of this recommended convention, and this contradicts what I've
been told. Can you please provide me with a link to this recommendation and how
it was shared with us?

[rvargas (doing something else), 2013/08/08 02:50:01]

I have not access to all emails that have talked about style issues (and
honestly looking up that is not a great use of time), but the current style
guide says
Prefer (foo == 0) to (0 == foo).

The reasoning being that it is generally easier to follow the flow that way.

I'm positive I've seen more than once the point about using regular (as opposed
to "test") ordering for dchecks.

+            static_cast<size_t>(kFirstAdditionalBlockFile));
   DCHECK(address.is_block_file() || !address.is_initialized());
   if (!address.is_initialized())
     return NULL;
 
   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));
+  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);

[gavinp, 2013/08/05 17:06:15]

This code changes from runtime checks to debug assertions on the block type
here. If these cases are impossible, AWESOME, good change.

+  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;
 
   MappedFile* file = FileForNewBlock(block_type, block_count);
   if (!file)
     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]) {
+  for (int i = block_count; i <= kMaxNumBlocks; i++) {
+    if (file_header.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(target_size, block_count, &index))
     return false;
 
-  Addr address(block_type, block_count, header->this_file, index);
+  Addr address(block_type, block_count, file_header.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;
 
   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)
     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);
 
-  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.
   }
 }
 
 void BlockFiles::CloseFiles() {
   if (init_) {
     DCHECK(thread_checker_->CalledOnValidThread());
   }
   init_ = false;
   for (unsigned int i = 0; i < block_files_.size(); i++) {
@@ skipping 89 matching lines @@
     LOG(ERROR) << "Failed to open " << name.value();
     return false;
   }
 
   size_t file_len = file->GetLength();
   if (file_len < static_cast<size_t>(kBlockHeaderSize)) {
     LOG(ERROR) << "File too small " << name.value();
     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();
       return false;
     }
   }
 
   if (static_cast<int>(file_len) <
       header->max_entries * header->entry_size + kBlockHeaderSize) {
     LOG(ERROR) << "File too small " << name.value();
@@ skipping 39 matching lines @@
   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];
-  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;
   }
   HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", TimeTicks::Now() - start);
   return file;
 }
 
 MappedFile* BlockFiles::NextFile(MappedFile* file) {
   ScopedFlush flush(file);
   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
@@ skipping 67 matching lines @@
     header = next_header;
     file = next_file;
   }
   return true;
 }
 
 // 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);
-  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;
   return true;
 }
 
 // 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) {
   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++) {
+    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;
 }
 
 base::FilePath BlockFiles::Name(int index) {
   // The file format allows for 256 files.
   DCHECK(index < 256 || index >= 0);
   std::string tmp = base::StringPrintf("%s%d", kBlockName, index);
   return path_.AppendASCII(tmp);
 }
 
 }  // namespace disk_cache