// 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;

#ifdef ARCH_CPU_BIG_ENDIAN
  // Every four bytes are a group (index type is uint32) and at this point
  // the index are based on little endian, so we need to xor the last 2 bits
  byte_index = byte_index ^ 0x03;
#endif
  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;
#ifdef ARCH_CPU_BIG_ENDIAN
  // Every four bytes are a group (index type is uint32) and at this point
  // the index are based on little endian, so we need to xor the last 2 bits
  byte_index = byte_index ^ 0x03;
#endif
  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;

  ScopedFlush flush(file);
  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);
  file->Flush();

  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;
  }

  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;

  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(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.
      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;
  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