Disk cache: Add base files for 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/block_files.h"
 
 #include "base/atomicops.h"
-#include "base/files/file_path.h"
+#include "base/file_util.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/file_lock.h"
 #include "net/disk_cache/trace.h"
 
 using base::TimeTicks;
 
-namespace {
-
-const char* kBlockName = "data_";
-
-// This array is used to perform a fast lookup of the nibble bit pattern to the
-// type of entry that can be stored there (number of consecutive blocks).
-const char s_types[16] = {4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
-
-// Returns the type of block (number of consecutive blocks that can be stored)
-// for a given nibble of the bitmap.
-inline int GetMapBlockType(uint8 value) {
-  value &= 0xf;
-  return s_types[value];
-}
-
-void FixAllocationCounters(disk_cache::BlockFileHeader* header);
-
-// 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, disk_cache::BlockFileHeader* header,
-                    int* index) {
-  if (target <= 0 || target > disk_cache::kMaxNumBlocks ||
-      size <= 0 || size > disk_cache::kMaxNumBlocks) {
-    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)
-      current = 0;
-    uint32 map_block = header->allocation_map[current];
-
-    for (int j = 0; j < 8; j++, map_block >>= 4) {
-      if (GetMapBlockType(map_block) != target)
-        continue;
-
-      disk_cache::FileLock lock(header);
-      int index_offset = j * 4 + 4 - target;
-      *index = current * 32 + index_offset;
-      DCHECK_EQ(*index / 4, (*index + size - 1) / 4);
-      uint32 to_add = ((1 << size) - 1) << index_offset;
-      header->num_entries++;
-
-      // Note that there is no race in the normal sense here, but if we enforce
-      // the order of memory accesses between num_entries and allocation_map, we
-      // can assert that even if we crash here, num_entries will never be less
-      // than the actual number of used blocks.
-      base::subtle::MemoryBarrier();
-      header->allocation_map[current] |= to_add;
-
-      header->hints[target - 1] = current;
-      header->empty[target - 1]--;
-      DCHECK_GE(header->empty[target - 1], 0);
-      if (target != size) {
-        header->empty[target - size - 1]++;
-      }
-      HISTOGRAM_TIMES("DiskCache.CreateBlock", TimeTicks::Now() - start);
-      return true;
-    }
-  }
-
-  // It is possible to have an undetected corruption (for example when the OS
-  // crashes), fix it here.
-  LOG(ERROR) << "Failing CreateMapBlock";
-  FixAllocationCounters(header);
-  return false;
-}
-
-// Deletes the block pointed by index from allocation_map, and updates the
-// relevant counters on the header.
-void DeleteMapBlock(int index, int size, disk_cache::BlockFileHeader* header) {
-  if (size < 0 || size > disk_cache::kMaxNumBlocks) {
-    NOTREACHED();
-    return;
-  }
-  TimeTicks start = TimeTicks::Now();
-  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;
-
-  // See what type of block will be availabe after we delete this one.
-  int bits_at_end = 4 - size - index % 4;
-  uint8 end_mask = (0xf << (4 - bits_at_end)) & 0xf;
-  bool update_counters = (map_block & end_mask) == 0;
-  uint8 new_value = map_block & ~(((1 << size) - 1) << (index % 4));
-  int new_type = GetMapBlockType(new_value);
-
-  disk_cache::FileLock lock(header);
-  DCHECK((((1 << size) - 1) << (index % 8)) < 0x100);
-  uint8  to_clear = ((1 << size) - 1) << (index % 8);
-  DCHECK((byte_map[byte_index] & to_clear) == to_clear);
-  byte_map[byte_index] &= ~to_clear;
-
-  if (update_counters) {
-    if (bits_at_end)
-      header->empty[bits_at_end - 1]--;
-    header->empty[new_type - 1]++;
-    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);
-}
-
-#ifndef NDEBUG
-// Returns true if the specified block is used. Note that this is a simplified
-// version of DeleteMapBlock().
-bool UsedMapBlock(int index, int size, disk_cache::BlockFileHeader* header) {
-  if (size < 0 || size > disk_cache::kMaxNumBlocks) {
-    NOTREACHED();
-    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);
-}
-#endif  // NDEBUG
-
-// Restores the "empty counters" and allocation hints.
-void FixAllocationCounters(disk_cache::BlockFileHeader* header) {
-  for (int i = 0; i < disk_cache::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]++;
-    }
-  }
-}
-
-// 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(const disk_cache::BlockFileHeader* header,
-                         int block_count) {
-  bool have_space = false;
-  int empty_blocks = 0;
-  for (int i = 0; i < disk_cache::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 < disk_cache::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;
-}
-
-// Returns the number of empty blocks for this file.
-int EmptyBlocks(const disk_cache::BlockFileHeader* header) {
-  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 false;
-  }
-  return empty_blocks;
-}
-
-// Returns true if the counters look OK.
-bool ValidateCounters(const disk_cache::BlockFileHeader* header) {
-  if (header->max_entries < 0 || header->max_entries > disk_cache::kMaxBlocks ||
-      header->num_entries < 0)
-    return false;
-
-  int empty_blocks = EmptyBlocks(header);
-  if (empty_blocks + header->num_entries > header->max_entries)
-    return false;
-
-  return true;
-}
-
-}  // namespace
-
 namespace disk_cache {
 
 BlockFiles::BlockFiles(const base::FilePath& path)
     : init_(false), zero_buffer_(NULL), path_(path) {
 }
 
 BlockFiles::~BlockFiles() {
   if (zero_buffer_)
     delete[] zero_buffer_;
   CloseFiles();
@@ skipping 166 matching lines @@
     size_t offset = address.start_block() * address.BlockSize() +
                     kBlockHeaderSize;
     bool ok = file->Read(buffer.get(), size, offset);
     DCHECK(ok);
   }
 
   return rv;
 #endif
 }
 
-bool BlockFiles::CreateBlockFile(int index, FileType file_type, bool force) {
-  base::FilePath name = Name(index);
-  int flags =
-      force ? base::PLATFORM_FILE_CREATE_ALWAYS : base::PLATFORM_FILE_CREATE;
-  flags |= base::PLATFORM_FILE_WRITE | base::PLATFORM_FILE_EXCLUSIVE_WRITE;
-
-  scoped_refptr<File> file(new File(
-      base::CreatePlatformFile(name, flags, NULL, NULL)));
-  if (!file->IsValid())
-    return false;
-
-  BlockFileHeader header;
-  header.entry_size = Addr::BlockSizeForFileType(file_type);
-  header.this_file = static_cast<int16>(index);
-  DCHECK(index <= kint16max && index >= 0);
-
-  return file->Write(&header, sizeof(header), 0);
-}
-
-bool BlockFiles::OpenBlockFile(int index) {
-  if (block_files_.size() - 1 < static_cast<unsigned int>(index)) {
-    DCHECK(index > 0);
-    int to_add = index - static_cast<int>(block_files_.size()) + 1;
-    block_files_.resize(block_files_.size() + to_add);
-  }
-
-  base::FilePath name = Name(index);
-  scoped_refptr<MappedFile> file(new MappedFile());
-
-  if (!file->Init(name, kBlockHeaderSize)) {
-    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;
-  }
-
-  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-  if (kBlockMagic != header->magic || kCurrentVersion != header->version) {
-    LOG(ERROR) << "Invalid file version or magic " << name.value();
-    return false;
-  }
-
-  if (header->updating || !ValidateCounters(header)) {
-    // Last instance was not properly shutdown, or counters are out of sync.
-    if (!FixBlockFileHeader(file)) {
-      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();
-    return false;
-  }
-
-  if (index == 0) {
-    // Load the links file into memory with a single read.
-    scoped_ptr<char[]> buf(new char[file_len]);
-    if (!file->Read(buf.get(), file_len, 0))
-      return false;
-  }
-
-  ScopedFlush flush(file);
-  DCHECK(!block_files_[index]);
-  file.swap(&block_files_[index]);
-  return true;
-}
-
 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;
 
@@ skipping 33 matching lines @@
     }
 
     if (!GrowBlockFile(file, 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());
-  int new_file = header->next_file;
-  if (!new_file) {
-    // RANKINGS is not reported as a type for small entries, but we may be
-    // extending the rankings block file.
-    FileType type = Addr::RequiredFileType(header->entry_size);
-    if (header->entry_size == Addr::BlockSizeForFileType(RANKINGS))
-      type = RANKINGS;
-
-    new_file = CreateNextBlockFile(type);
-    if (!new_file)
-      return NULL;
-
-    FileLock lock(header);
-    header->next_file = new_file;
-  }
-
-  // Only the block_file argument is relevant for what we want.
-  Addr address(BLOCK_256, 1, new_file, 0);
-  return GetFile(address);
-}
-
-int BlockFiles::CreateNextBlockFile(FileType block_type) {
-  for (int i = kFirstAdditionalBlockFile; i <= kMaxBlockFile; i++) {
-    if (CreateBlockFile(i, block_type, false))
-      return i;
-  }
-  return 0;
-}
-
-// We walk the list of files for this particular block type, deleting the ones
-// that are empty.
-bool BlockFiles::RemoveEmptyFile(FileType block_type) {
-  MappedFile* file = block_files_[block_type - 1];
-  BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
-
-  while (header->next_file) {
-    // Only the block_file argument is relevant for what we want.
-    Addr address(BLOCK_256, 1, header->next_file, 0);
-    MappedFile* next_file = GetFile(address);
-    if (!next_file)
-      return false;
-
-    BlockFileHeader* next_header =
-        reinterpret_cast<BlockFileHeader*>(next_file->buffer());
-    if (!next_header->num_entries) {
-      DCHECK_EQ(next_header->entry_size, header->entry_size);
-      // Delete next_file and remove it from the chain.
-      int file_index = header->next_file;
-      header->next_file = next_header->next_file;
-      DCHECK(block_files_.size() >= static_cast<unsigned int>(file_index));
-      file->Flush();
-
-      // We get a new handle to the file and release the old one so that the
-      // file gets unmmaped... so we can delete it.
-      base::FilePath name = Name(file_index);
-      scoped_refptr<File> this_file(new File(false));
-      this_file->Init(name);
-      block_files_[file_index]->Release();
-      block_files_[file_index] = NULL;
-
-      int failure = DeleteCacheFile(name) ? 0 : 1;
-      UMA_HISTOGRAM_COUNTS("DiskCache.DeleteFailed2", failure);
-      if (failure)
-        LOG(ERROR) << "Failed to delete " << name.value() << " from the cache.";
-      continue;
-    }
-
-    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);
   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;
@@ skipping 53 matching lines @@
     *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