text: // 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/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 FilePath& path)
      : init_(false), zero_buffer_(NULL), path_(path) {
  }
  
  BlockFiles::~BlockFiles() {
    if (zero_buffer_)
      delete[] zero_buffer_;
    CloseFiles();
  }
  
  bool BlockFiles::Init(bool create_files) {
    DCHECK(!init_);
    if (init_)
      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;
  }
  
  MappedFile* BlockFiles::GetFile(Addr address) {
    DCHECK(thread_checker_->CalledOnValidThread());
    DCHECK(block_files_.size() >= 4);
    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));
    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)
      return false;
    if (!init_)
      return false;
  
    MappedFile* file = FileForNewBlock(block_type, block_count);
    if (!file)
      return false;
  
    BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
  
    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 (!CreateMapBlock(target_size, block_count, header, &index))
      return false;
  
    Addr address(block_type, block_count, 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);
  
    BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    DeleteMapBlock(address.start_block(), address.num_blocks(), header);
  
    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.
    }
  }
  
  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 BlockFiles::ReportStats() {
    DCHECK(thread_checker_->CalledOnValidThread());
    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) {
  #ifdef NDEBUG
    return true;
  #else
    if (!address.is_initialized() || address.is_separate_file())
      return false;
  
    MappedFile* file = GetFile(address);
    if (!file)
      return false;
  
    BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    bool rv = UsedMapBlock(address.start_block(), address.num_blocks(), header);
    DCHECK(rv);
  
    static bool read_contents = false;
    if (read_contents) {
      scoped_array<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
  }
  
  bool BlockFiles::CreateBlockFile(int index, FileType file_type, bool force) {
    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);
    }
  
    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_array<char> buf(new char[file_len]);
      if (!file->Read(buf.get(), file_len, 0))
        return false;
    }
  
    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;
  
    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;
      }
      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 (!GrowBlockFile(file, header))
        return NULL;
      break;
    }
    HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", TimeTicks::Now() - start);
    return file;
  }
  
  MappedFile* BlockFiles::NextFile(const MappedFile* 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));
  
        // We get a new handle to the file and release the old one so that the
        // file gets unmmaped... so we can delete it.
        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) {
    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;
  }
  
  // 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++) {
        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;
  }
  
  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
  