Disk cache: Reference CL for the implementation of file format version 3.

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/v3/block_bitmaps.h"
+
+#include "base/metrics/histogram.h"
+#include "base/string_util.h"
+#include "base/stringprintf.h"
+#include "base/threading/thread_checker.h"
+#include "base/time.h"
+#include "net/disk_cache/cache_util.h"
+#include "net/disk_cache/disk_format_base.h"
+#include "net/disk_cache/file_lock.h"
+#include "net/disk_cache/trace.h"
+#include "net/disk_cache/v3/backend_impl_v3.h"
+
+using base::TimeTicks;
+
+namespace disk_cache {
+
+BlockBitmaps::BlockBitmaps(BackendImplV3* backend) : backend_(backend) {
+}
+
+BlockBitmaps::~BlockBitmaps() {
+}
+
+void BlockBitmaps::Init(const BlockFilesBitmaps& bitmaps) {
+  bitmaps_ = bitmaps;
+  for (int i = 0; i < kFirstAdditionalBlockFileV3; i++)
+    empty_counts_[i] = EmptyBlocksForType(i);
+}
+
+int BlockBitmaps::GetHeader(Addr address) {
+  DCHECK(bitmaps_.size() >= kFirstAdditionalBlockFileV3);
+  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) >= bitmaps_.size() ||
+      !bitmaps_[file_index].Get()) {
+    return -1;
+  }
+  DCHECK(bitmaps_.size() >= static_cast<unsigned int>(file_index));
+  return file_index;
+}
+
+bool BlockBitmaps::CreateBlock(FileType block_type, int block_count,
+                             Addr* block_address) {
+  if (block_type < BLOCK_256 || block_type > BLOCK_EVICTED ||
+      block_count < 1 || block_count > 4)
+    return false;
+
+  int header_num = HeaderForNewBlock(block_type, block_count);
+  if (header_num < 0)
+    return false;
+
+  int target_size = 0;
+  for (int i = block_count; i <= 4; i++) {
+    if (bitmaps_[header_num]->empty[i - 1]) {
+      target_size = i;
+      break;
+    }
+  }
+
+  DCHECK(target_size);
+  int index;
+  if (!bitmaps_[header_num].CreateMapBlock(target_size, block_count, &index))
+    return false;
+
+  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;
+  }
+
+  // Yes, the count may be off by 1 when we start.
+  empty_counts_[target_size] -= block_count;
+  if (empty_counts_[target_size] < kNumExtraBlocks / 2)
+    backend_->GrowBlockFiles();
+
+  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 BlockBitmaps::DeleteBlock(Addr address) {
+  if (!address.is_initialized() || address.is_separate_file())
+    return;
+
+  int header_num = GetHeader(address);
+  if (header_num < 0)
+    return;
+
+  Trace("DeleteBlock 0x%x", address.value());  
+  bitmaps_[header_num].DeleteMapBlock(address.start_block(),
+                                      address.num_blocks());
+
+  if (!bitmaps_[header_num]->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.
+  }
+}
+
+void BlockBitmaps::Clear() {
+  bitmaps_.clear();
+}
+
+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 BlockBitmaps::IsValid(Addr address) {
+#ifdef NDEBUG
+  return true;
+#else
+  if (!address.is_initialized() || address.is_separate_file())
+    return false;
+
+  int header_num = GetHeader(address);
+  if (header_num < 0)
+    return false;
+
+  bool rv = bitmaps_[header_num].UsedMapBlock(address.start_block(),
+                                              address.num_blocks());
+  DCHECK(rv);
+  return rv;
+#endif
+}
+
+int BlockBitmaps::EmptyBlocksForType(int next_file) {
+  int empty_blocks = 0;
+  do {
+    empty_blocks += bitmaps_[next_file].EmptyBlocks();
+    next_file = bitmaps_[next_file]->next_file;
+  } while (next_file);
+  return empty_blocks;
+}
+
+int BlockBitmaps::HeaderForNewBlock(FileType block_type, int block_count) {
+  COMPILE_ASSERT(RANKINGS == 1, invalid_file_type);
+  int header_num = block_type - 1;
+  bool found = true;
+
+  TimeTicks start = TimeTicks::Now();
+  while (bitmaps_[header_num].NeedToGrowBlockFile(block_count)) {
+    header_num = bitmaps_[header_num]->next_file;
+    if (!header_num) {
+      found = false;
+      break;
+    }
+  }
+
+  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) {
+      NOTREACHED();
+      header_num = -1;
+    }
+  }
+
+  HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", TimeTicks::Now() - start);
+  return header_num;
+}
+
+// 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 BlockBitmaps::FixBlockFileHeader(MappedFile* file) {
+  ScopedFlush flush(file);
+  BlockHeader header(file);
+  int file_size = static_cast<int>(file->GetLength());
+  if (file_size < header.Size())
+    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 + header.Size();
+  if (file_size != expected) {
+    int max_expected = header->entry_size * kMaxBlocks + 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;
+    header->max_entries = num_entries;
+  }
+
+  header.FixAllocationCounters();
+  int empty_blocks = header.EmptyBlocks();
+  if (empty_blocks + header->num_entries > header->max_entries)
+    header->num_entries = header->max_entries - empty_blocks;
+
+  if (!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 BlockBitmaps::GetFileStats(int index, int* used_count, int* load) {
+  int max_blocks = 0;
+  *used_count = 0;
+  *load = 0;
+  for (;;) {
+    BlockFileHeader* header = bitmaps_[index].Get();
+
+    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);
+    }
+    *used_count += used;
+
+    if (!header->next_file)
+      break;
+    index = header->next_file;
+  }
+  if (max_blocks)
+    *load = *used_count * 100 / max_blocks;
+}
+
+}  // namespace disk_cache