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 34 matching lines @@
 BlockHeader::BlockHeader(MappedFile* file)
     : header_(reinterpret_cast<BlockFileHeader*>(file->buffer())) {
 }
 
 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;
   }
 
   TimeTicks start = TimeTicks::Now();
   // We are going to process the map on 32-block chunks (32 bits), and on every
   // chunk, iterate through the 8 nibbles where the new block can be located.
   int current = header_->hints[target - 1];
   for (int i = 0; i < header_->max_entries / 32; i++, current++) {
     if (current == header_->max_entries / 32)
@@ skipping 69 matching lines @@
     DCHECK_GE(header_->empty[bits_at_end - 1], 0);
   }
   base::subtle::MemoryBarrier();
   header_->num_entries--;
   DCHECK_GE(header_->num_entries, 0);
   HISTOGRAM_TIMES("DiskCache.DeleteBlock", TimeTicks::Now() - start);
 }
 
 // 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];
 
   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);
 }
 
 void BlockHeader::FixAllocationCounters() {
   for (int i = 0; i < kMaxNumBlocks; i++) {
     header_->hints[i] = 0;
     header_->empty[i] = 0;
   }
 
   for (int i = 0; i < header_->max_entries / 32; i++) {
     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 {
+  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;
   }
   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)
     return false;
 
   int empty_blocks = EmptyBlocks();
   if (empty_blocks + header_->num_entries > header_->max_entries)
     return false;
 
   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)
     : 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(),
+            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);
+  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]) {
-      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;
 }
 
 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