src/net/disk_cache/block_files.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/disk_cache/block_files.h"
   6
   7 #include "base/atomicops.h"
   8 #include "base/files/file_path.h"
   9 #include "base/metrics/histogram.h"
  10 #include "base/strings/string_util.h"
  11 #include "base/strings/stringprintf.h"
  12 #include "base/threading/thread_checker.h"
  13 #include "base/time/time.h"
  14 #include "net/disk_cache/cache_util.h"
  15 #include "net/disk_cache/file_lock.h"
  16 #include "net/disk_cache/stress_support.h"
  17 #include "net/disk_cache/trace.h"
  18
  19 using base::TimeTicks;
  20
  21 namespace {
  22
  23 const char* kBlockName = "data_";
  24
  25 // This array is used to perform a fast lookup of the nibble bit pattern to the
  26 // type of entry that can be stored there (number of consecutive blocks).
  27 const char s_types[16] = {4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
  28
  29 // Returns the type of block (number of consecutive blocks that can be stored)
  30 // for a given nibble of the bitmap.
  31 inline int GetMapBlockType(uint8 value) {
  32   value &= 0xf;
  33   return s_types[value];
  34 }
  35
  36 }  // namespace
  37
  38 namespace disk_cache {
  39
  40 BlockHeader::BlockHeader() : header_(NULL) {
  41 }
  42
  43 BlockHeader::BlockHeader(BlockFileHeader* header) : header_(header) {
  44 }
  45
  46 BlockHeader::BlockHeader(MappedFile* file)
  47     : header_(reinterpret_cast<BlockFileHeader*>(file->buffer())) {
  48 }
  49
  50 BlockHeader::BlockHeader(const BlockHeader& other) : header_(other.header_) {
  51 }
  52
  53 BlockHeader::~BlockHeader() {
  54 }
  55
  56 bool BlockHeader::CreateMapBlock(int size, int* index) {
  57   DCHECK(size > 0 && size <= kMaxNumBlocks);
  58   int target = 0;
  59   for (int i = size; i <= kMaxNumBlocks; i++) {
  60     if (header_->empty[i - 1]) {
  61       target = i;
  62       break;
  63     }
  64   }
  65
  66   if (!target) {
  67     STRESS_NOTREACHED();
  68     return false;
  69   }
  70
  71   TimeTicks start = TimeTicks::Now();
  72   // We are going to process the map on 32-block chunks (32 bits), and on every
  73   // chunk, iterate through the 8 nibbles where the new block can be located.
  74   int current = header_->hints[target - 1];
  75   for (int i = 0; i < header_->max_entries / 32; i++, current++) {
  76     if (current == header_->max_entries / 32)
  77       current = 0;
  78     uint32 map_block = header_->allocation_map[current];
  79
  80     for (int j = 0; j < 8; j++, map_block >>= 4) {
  81       if (GetMapBlockType(map_block) != target)
  82         continue;
  83
  84       disk_cache::FileLock lock(header_);
  85       int index_offset = j * 4 + 4 - target;
  86       *index = current * 32 + index_offset;
  87       STRESS_DCHECK(*index / 4 == (*index + size - 1) / 4);
  88       uint32 to_add = ((1 << size) - 1) << index_offset;
  89       header_->num_entries++;
  90
  91       // Note that there is no race in the normal sense here, but if we enforce
  92       // the order of memory accesses between num_entries and allocation_map, we
  93       // can assert that even if we crash here, num_entries will never be less
  94       // than the actual number of used blocks.
  95       base::subtle::MemoryBarrier();
  96       header_->allocation_map[current] |= to_add;
  97
  98       header_->hints[target - 1] = current;
  99       header_->empty[target - 1]--;
 100       STRESS_DCHECK(header_->empty[target - 1] >= 0);
 101       if (target != size) {
 102         header_->empty[target - size - 1]++;
 103       }
 104       HISTOGRAM_TIMES("DiskCache.CreateBlock", TimeTicks::Now() - start);
 105       return true;
 106     }
 107   }
 108
 109   // It is possible to have an undetected corruption (for example when the OS
 110   // crashes), fix it here.
 111   LOG(ERROR) << "Failing CreateMapBlock";
 112   FixAllocationCounters();
 113   return false;
 114 }
 115
 116 void BlockHeader::DeleteMapBlock(int index, int size) {
 117   if (size < 0 || size > kMaxNumBlocks) {
 118     NOTREACHED();
 119     return;
 120   }
 121   TimeTicks start = TimeTicks::Now();
 122   int byte_index = index / 8;
 123   uint8* byte_map = reinterpret_cast<uint8*>(header_->allocation_map);
 124   uint8 map_block = byte_map[byte_index];
 125
 126   if (index % 8 >= 4)
 127     map_block >>= 4;
 128
 129   // See what type of block will be available after we delete this one.
 130   int bits_at_end = 4 - size - index % 4;
 131   uint8 end_mask = (0xf << (4 - bits_at_end)) & 0xf;
 132   bool update_counters = (map_block & end_mask) == 0;
 133   uint8 new_value = map_block & ~(((1 << size) - 1) << (index % 4));
 134   int new_type = GetMapBlockType(new_value);
 135
 136   disk_cache::FileLock lock(header_);
 137   STRESS_DCHECK((((1 << size) - 1) << (index % 8)) < 0x100);
 138   uint8  to_clear = ((1 << size) - 1) << (index % 8);
 139   STRESS_DCHECK((byte_map[byte_index] & to_clear) == to_clear);
 140   byte_map[byte_index] &= ~to_clear;
 141
 142   if (update_counters) {
 143     if (bits_at_end)
 144       header_->empty[bits_at_end - 1]--;
 145     header_->empty[new_type - 1]++;
 146     STRESS_DCHECK(header_->empty[bits_at_end - 1] >= 0);
 147   }
 148   base::subtle::MemoryBarrier();
 149   header_->num_entries--;
 150   STRESS_DCHECK(header_->num_entries >= 0);
 151   HISTOGRAM_TIMES("DiskCache.DeleteBlock", TimeTicks::Now() - start);
 152 }
 153
 154 // Note that this is a simplified version of DeleteMapBlock().
 155 bool BlockHeader::UsedMapBlock(int index, int size) {
 156   if (size < 0 || size > kMaxNumBlocks)
 157     return false;
 158
 159   int byte_index = index / 8;
 160   uint8* byte_map = reinterpret_cast<uint8*>(header_->allocation_map);
 161   uint8 map_block = byte_map[byte_index];
 162
 163   if (index % 8 >= 4)
 164     map_block >>= 4;
 165
 166   STRESS_DCHECK((((1 << size) - 1) << (index % 8)) < 0x100);
 167   uint8  to_clear = ((1 << size) - 1) << (index % 8);
 168   return ((byte_map[byte_index] & to_clear) == to_clear);
 169 }
 170
 171 void BlockHeader::FixAllocationCounters() {
 172   for (int i = 0; i < kMaxNumBlocks; i++) {
 173     header_->hints[i] = 0;
 174     header_->empty[i] = 0;
 175   }
 176
 177   for (int i = 0; i < header_->max_entries / 32; i++) {
 178     uint32 map_block = header_->allocation_map[i];
 179
 180     for (int j = 0; j < 8; j++, map_block >>= 4) {
 181       int type = GetMapBlockType(map_block);
 182       if (type)
 183         header_->empty[type -1]++;
 184     }
 185   }
 186 }
 187
 188 bool BlockHeader::NeedToGrowBlockFile(int block_count) const {
 189   bool have_space = false;
 190   int empty_blocks = 0;
 191   for (int i = 0; i < kMaxNumBlocks; i++) {
 192     empty_blocks += header_->empty[i] * (i + 1);
 193     if (i >= block_count - 1 && header_->empty[i])
 194       have_space = true;
 195   }
 196
 197   if (header_->next_file && (empty_blocks < kMaxBlocks / 10)) {
 198     // This file is almost full but we already created another one, don't use
 199     // this file yet so that it is easier to find empty blocks when we start
 200     // using this file again.
 201     return true;
 202   }
 203   return !have_space;
 204 }
 205
 206 bool BlockHeader::CanAllocate(int block_count) const {
 207   DCHECK_GT(block_count, 0);
 208   for (int i = block_count - 1; i < kMaxNumBlocks; i++) {
 209     if (header_->empty[i])
 210       return true;
 211   }
 212
 213   return false;
 214 }
 215
 216 int BlockHeader::EmptyBlocks() const {
 217   int empty_blocks = 0;
 218   for (int i = 0; i < kMaxNumBlocks; i++) {
 219     empty_blocks += header_->empty[i] * (i + 1);
 220     if (header_->empty[i] < 0)
 221       return 0;
 222   }
 223   return empty_blocks;
 224 }
 225
 226 int BlockHeader::MinimumAllocations() const {
 227   return header_->empty[kMaxNumBlocks - 1];
 228 }
 229
 230 int BlockHeader::Capacity() const {
 231   return header_->max_entries;
 232 }
 233
 234 bool BlockHeader::ValidateCounters() const {
 235   if (header_->max_entries < 0 || header_->max_entries > kMaxBlocks ||
 236       header_->num_entries < 0)
 237     return false;
 238
 239   int empty_blocks = EmptyBlocks();
 240   if (empty_blocks + header_->num_entries > header_->max_entries)
 241     return false;
 242
 243   return true;
 244 }
 245
 246 int BlockHeader::FileId() const {
 247   return header_->this_file;
 248 }
 249
 250 int BlockHeader::NextFileId() const {
 251   return header_->next_file;
 252 }
 253
 254 int BlockHeader::Size() const {
 255   return static_cast<int>(sizeof(*header_));
 256 }
 257
 258 BlockFileHeader* BlockHeader::Header() {
 259   return header_;
 260 }
 261
 262 // ------------------------------------------------------------------------
 263
 264 BlockFiles::BlockFiles(const base::FilePath& path)
 265     : init_(false), zero_buffer_(NULL), path_(path) {
 266 }
 267
 268 BlockFiles::~BlockFiles() {
 269   if (zero_buffer_)
 270     delete[] zero_buffer_;
 271   CloseFiles();
 272 }
 273
 274 bool BlockFiles::Init(bool create_files) {
 275   DCHECK(!init_);
 276   if (init_)
 277     return false;
 278
 279   thread_checker_.reset(new base::ThreadChecker);
 280
 281   block_files_.resize(kFirstAdditionalBlockFile);
 282   for (int i = 0; i < kFirstAdditionalBlockFile; i++) {
 283     if (create_files)
 284       if (!CreateBlockFile(i, static_cast<FileType>(i + 1), true))
 285         return false;
 286
 287     if (!OpenBlockFile(i))
 288       return false;
 289
 290     // Walk this chain of files removing empty ones.
 291     if (!RemoveEmptyFile(static_cast<FileType>(i + 1)))
 292       return false;
 293   }
 294
 295   init_ = true;
 296   return true;
 297 }
 298
 299 MappedFile* BlockFiles::GetFile(Addr address) {
 300   DCHECK(thread_checker_->CalledOnValidThread());
 301   DCHECK_GE(block_files_.size(),
 302             static_cast<size_t>(kFirstAdditionalBlockFile));
 303   DCHECK(address.is_block_file() || !address.is_initialized());
 304   if (!address.is_initialized())
 305     return NULL;
 306
 307   int file_index = address.FileNumber();
 308   if (static_cast<unsigned int>(file_index) >= block_files_.size() ||
 309       !block_files_[file_index]) {
 310     // We need to open the file
 311     if (!OpenBlockFile(file_index))
 312       return NULL;
 313   }
 314   DCHECK_GE(block_files_.size(), static_cast<unsigned int>(file_index));
 315   return block_files_[file_index];
 316 }
 317
 318 bool BlockFiles::CreateBlock(FileType block_type, int block_count,
 319                              Addr* block_address) {
 320   DCHECK(thread_checker_->CalledOnValidThread());
 321   DCHECK_NE(block_type, EXTERNAL);
 322   DCHECK_NE(block_type, BLOCK_FILES);
 323   DCHECK_NE(block_type, BLOCK_ENTRIES);
 324   DCHECK_NE(block_type, BLOCK_EVICTED);
 325   if (block_count < 1 || block_count > kMaxNumBlocks)
 326     return false;
 327
 328   if (!init_)
 329     return false;
 330
 331   MappedFile* file = FileForNewBlock(block_type, block_count);
 332   if (!file)
 333     return false;
 334
 335   ScopedFlush flush(file);
 336   BlockHeader file_header(file);
 337
 338   int index;
 339   if (!file_header.CreateMapBlock(block_count, &index))
 340     return false;
 341
 342   Addr address(block_type, block_count, file_header.FileId(), index);
 343   block_address->set_value(address.value());
 344   Trace("CreateBlock 0x%x", address.value());
 345   return true;
 346 }
 347
 348 void BlockFiles::DeleteBlock(Addr address, bool deep) {
 349   DCHECK(thread_checker_->CalledOnValidThread());
 350   if (!address.is_initialized() || address.is_separate_file())
 351     return;
 352
 353   if (!zero_buffer_) {
 354     zero_buffer_ = new char[Addr::BlockSizeForFileType(BLOCK_4K) * 4];
 355     memset(zero_buffer_, 0, Addr::BlockSizeForFileType(BLOCK_4K) * 4);
 356   }
 357   MappedFile* file = GetFile(address);
 358   if (!file)
 359     return;
 360
 361   Trace("DeleteBlock 0x%x", address.value());
 362
 363   size_t size = address.BlockSize() * address.num_blocks();
 364   size_t offset = address.start_block() * address.BlockSize() +
 365                   kBlockHeaderSize;
 366   if (deep)
 367     file->Write(zero_buffer_, size, offset);
 368
 369   BlockHeader file_header(file);
 370   file_header.DeleteMapBlock(address.start_block(), address.num_blocks());
 371   file->Flush();
 372
 373   if (!file_header.Header()->num_entries) {
 374     // This file is now empty. Let's try to delete it.
 375     FileType type = Addr::RequiredFileType(file_header.Header()->entry_size);
 376     if (Addr::BlockSizeForFileType(RANKINGS) ==
 377         file_header.Header()->entry_size) {
 378       type = RANKINGS;
 379     }
 380     RemoveEmptyFile(type);  // Ignore failures.
 381   }
 382 }
 383
 384 void BlockFiles::CloseFiles() {
 385   if (init_) {
 386     DCHECK(thread_checker_->CalledOnValidThread());
 387   }
 388   init_ = false;
 389   for (unsigned int i = 0; i < block_files_.size(); i++) {
 390     if (block_files_[i]) {
 391       block_files_[i]->Release();
 392       block_files_[i] = NULL;
 393     }
 394   }
 395   block_files_.clear();
 396 }
 397
 398 void BlockFiles::ReportStats() {
 399   DCHECK(thread_checker_->CalledOnValidThread());
 400   int used_blocks[kFirstAdditionalBlockFile];
 401   int load[kFirstAdditionalBlockFile];
 402   for (int i = 0; i < kFirstAdditionalBlockFile; i++) {
 403     GetFileStats(i, &used_blocks[i], &load[i]);
 404   }
 405   UMA_HISTOGRAM_COUNTS("DiskCache.Blocks_0", used_blocks[0]);
 406   UMA_HISTOGRAM_COUNTS("DiskCache.Blocks_1", used_blocks[1]);
 407   UMA_HISTOGRAM_COUNTS("DiskCache.Blocks_2", used_blocks[2]);
 408   UMA_HISTOGRAM_COUNTS("DiskCache.Blocks_3", used_blocks[3]);
 409
 410   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_0", load[0], 101);
 411   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_1", load[1], 101);
 412   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_2", load[2], 101);
 413   UMA_HISTOGRAM_ENUMERATION("DiskCache.BlockLoad_3", load[3], 101);
 414 }
 415
 416 bool BlockFiles::IsValid(Addr address) {
 417 #ifdef NDEBUG
 418   return true;
 419 #else
 420   if (!address.is_initialized() || address.is_separate_file())
 421     return false;
 422
 423   MappedFile* file = GetFile(address);
 424   if (!file)
 425     return false;
 426
 427   BlockHeader header(file);
 428   bool rv = header.UsedMapBlock(address.start_block(), address.num_blocks());
 429   DCHECK(rv);
 430
 431   static bool read_contents = false;
 432   if (read_contents) {
 433     scoped_ptr<char[]> buffer;
 434     buffer.reset(new char[Addr::BlockSizeForFileType(BLOCK_4K) * 4]);
 435     size_t size = address.BlockSize() * address.num_blocks();
 436     size_t offset = address.start_block() * address.BlockSize() +
 437                     kBlockHeaderSize;
 438     bool ok = file->Read(buffer.get(), size, offset);
 439     DCHECK(ok);
 440   }
 441
 442   return rv;
 443 #endif
 444 }
 445
 446 bool BlockFiles::CreateBlockFile(int index, FileType file_type, bool force) {
 447   base::FilePath name = Name(index);
 448   int flags =
 449       force ? base::PLATFORM_FILE_CREATE_ALWAYS : base::PLATFORM_FILE_CREATE;
 450   flags |= base::PLATFORM_FILE_WRITE | base::PLATFORM_FILE_EXCLUSIVE_WRITE;
 451
 452   scoped_refptr<File> file(new File(
 453       base::CreatePlatformFile(name, flags, NULL, NULL)));
 454   if (!file->IsValid())
 455     return false;
 456
 457   BlockFileHeader header;
 458   memset(&header, 0, sizeof(header));
 459   header.magic = kBlockMagic;
 460   header.version = kBlockVersion2;
 461   header.entry_size = Addr::BlockSizeForFileType(file_type);
 462   header.this_file = static_cast<int16>(index);
 463   DCHECK(index <= kint16max && index >= 0);
 464
 465   return file->Write(&header, sizeof(header), 0);
 466 }
 467
 468 bool BlockFiles::OpenBlockFile(int index) {
 469   if (block_files_.size() - 1 < static_cast<unsigned int>(index)) {
 470     DCHECK(index > 0);
 471     int to_add = index - static_cast<int>(block_files_.size()) + 1;
 472     block_files_.resize(block_files_.size() + to_add);
 473   }
 474
 475   base::FilePath name = Name(index);
 476   scoped_refptr<MappedFile> file(new MappedFile());
 477
 478   if (!file->Init(name, kBlockHeaderSize)) {
 479     LOG(ERROR) << "Failed to open " << name.value();
 480     return false;
 481   }
 482
 483   size_t file_len = file->GetLength();
 484   if (file_len < static_cast<size_t>(kBlockHeaderSize)) {
 485     LOG(ERROR) << "File too small " << name.value();
 486     return false;
 487   }
 488
 489   BlockHeader file_header(file.get());
 490   BlockFileHeader* header = file_header.Header();
 491   if (kBlockMagic != header->magic || kBlockVersion2 != header->version) {
 492     LOG(ERROR) << "Invalid file version or magic " << name.value();
 493     return false;
 494   }
 495
 496   if (header->updating || !file_header.ValidateCounters()) {
 497     // Last instance was not properly shutdown, or counters are out of sync.
 498     if (!FixBlockFileHeader(file.get())) {
 499       LOG(ERROR) << "Unable to fix block file " << name.value();
 500       return false;
 501     }
 502   }
 503
 504   if (static_cast<int>(file_len) <
 505       header->max_entries * header->entry_size + kBlockHeaderSize) {
 506     LOG(ERROR) << "File too small " << name.value();
 507     return false;
 508   }
 509
 510   if (index == 0) {
 511     // Load the links file into memory with a single read.
 512     scoped_ptr<char[]> buf(new char[file_len]);
 513     if (!file->Read(buf.get(), file_len, 0))
 514       return false;
 515   }
 516
 517   ScopedFlush flush(file.get());
 518   DCHECK(!block_files_[index]);
 519   file.swap(&block_files_[index]);
 520   return true;
 521 }
 522
 523 bool BlockFiles::GrowBlockFile(MappedFile* file, BlockFileHeader* header) {
 524   if (kMaxBlocks == header->max_entries)
 525     return false;
 526
 527   ScopedFlush flush(file);
 528   DCHECK(!header->empty[3]);
 529   int new_size = header->max_entries + 1024;
 530   if (new_size > kMaxBlocks)
 531     new_size = kMaxBlocks;
 532
 533   int new_size_bytes = new_size * header->entry_size + sizeof(*header);
 534
 535   if (!file->SetLength(new_size_bytes)) {
 536     // Most likely we are trying to truncate the file, so the header is wrong.
 537     if (header->updating < 10 && !FixBlockFileHeader(file)) {
 538       // If we can't fix the file increase the lock guard so we'll pick it on
 539       // the next start and replace it.
 540       header->updating = 100;
 541       return false;
 542     }
 543     return (header->max_entries >= new_size);
 544   }
 545
 546   FileLock lock(header);
 547   header->empty[3] = (new_size - header->max_entries) / 4;  // 4 blocks entries
 548   header->max_entries = new_size;
 549
 550   return true;
 551 }
 552
 553 MappedFile* BlockFiles::FileForNewBlock(FileType block_type, int block_count) {
 554   COMPILE_ASSERT(RANKINGS == 1, invalid_file_type);
 555   MappedFile* file = block_files_[block_type - 1];
 556   BlockHeader file_header(file);
 557
 558   TimeTicks start = TimeTicks::Now();
 559   while (file_header.NeedToGrowBlockFile(block_count)) {
 560     if (kMaxBlocks == file_header.Header()->max_entries) {
 561       file = NextFile(file);
 562       if (!file)
 563         return NULL;
 564       file_header = BlockHeader(file);
 565       continue;
 566     }
 567
 568     if (!GrowBlockFile(file, file_header.Header()))
 569       return NULL;
 570     break;
 571   }
 572   HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", TimeTicks::Now() - start);
 573   return file;
 574 }
 575
 576 MappedFile* BlockFiles::NextFile(MappedFile* file) {
 577   ScopedFlush flush(file);
 578   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
 579   int new_file = header->next_file;
 580   if (!new_file) {
 581     // RANKINGS is not reported as a type for small entries, but we may be
 582     // extending the rankings block file.
 583     FileType type = Addr::RequiredFileType(header->entry_size);
 584     if (header->entry_size == Addr::BlockSizeForFileType(RANKINGS))
 585       type = RANKINGS;
 586
 587     new_file = CreateNextBlockFile(type);
 588     if (!new_file)
 589       return NULL;
 590
 591     FileLock lock(header);
 592     header->next_file = new_file;
 593   }
 594
 595   // Only the block_file argument is relevant for what we want.
 596   Addr address(BLOCK_256, 1, new_file, 0);
 597   return GetFile(address);
 598 }
 599
 600 int BlockFiles::CreateNextBlockFile(FileType block_type) {
 601   for (int i = kFirstAdditionalBlockFile; i <= kMaxBlockFile; i++) {
 602     if (CreateBlockFile(i, block_type, false))
 603       return i;
 604   }
 605   return 0;
 606 }
 607
 608 // We walk the list of files for this particular block type, deleting the ones
 609 // that are empty.
 610 bool BlockFiles::RemoveEmptyFile(FileType block_type) {
 611   MappedFile* file = block_files_[block_type - 1];
 612   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
 613
 614   while (header->next_file) {
 615     // Only the block_file argument is relevant for what we want.
 616     Addr address(BLOCK_256, 1, header->next_file, 0);
 617     MappedFile* next_file = GetFile(address);
 618     if (!next_file)
 619       return false;
 620
 621     BlockFileHeader* next_header =
 622         reinterpret_cast<BlockFileHeader*>(next_file->buffer());
 623     if (!next_header->num_entries) {
 624       DCHECK_EQ(next_header->entry_size, header->entry_size);
 625       // Delete next_file and remove it from the chain.
 626       int file_index = header->next_file;
 627       header->next_file = next_header->next_file;
 628       DCHECK(block_files_.size() >= static_cast<unsigned int>(file_index));
 629       file->Flush();
 630
 631       // We get a new handle to the file and release the old one so that the
 632       // file gets unmmaped... so we can delete it.
 633       base::FilePath name = Name(file_index);
 634       scoped_refptr<File> this_file(new File(false));
 635       this_file->Init(name);
 636       block_files_[file_index]->Release();
 637       block_files_[file_index] = NULL;
 638
 639       int failure = DeleteCacheFile(name) ? 0 : 1;
 640       UMA_HISTOGRAM_COUNTS("DiskCache.DeleteFailed2", failure);
 641       if (failure)
 642         LOG(ERROR) << "Failed to delete " << name.value() << " from the cache.";
 643       continue;
 644     }
 645
 646     header = next_header;
 647     file = next_file;
 648   }
 649   return true;
 650 }
 651
 652 // Note that we expect to be called outside of a FileLock... however, we cannot
 653 // DCHECK on header->updating because we may be fixing a crash.
 654 bool BlockFiles::FixBlockFileHeader(MappedFile* file) {
 655   ScopedFlush flush(file);
 656   BlockHeader file_header(file);
 657   int file_size = static_cast<int>(file->GetLength());
 658   if (file_size < file_header.Size())
 659     return false;  // file_size > 2GB is also an error.
 660
 661   const int kMinBlockSize = 36;
 662   const int kMaxBlockSize = 4096;
 663   BlockFileHeader* header = file_header.Header();
 664   if (header->entry_size < kMinBlockSize ||
 665       header->entry_size > kMaxBlockSize || header->num_entries < 0)
 666     return false;
 667
 668   // Make sure that we survive crashes.
 669   header->updating = 1;
 670   int expected = header->entry_size * header->max_entries + file_header.Size();
 671   if (file_size != expected) {
 672     int max_expected = header->entry_size * kMaxBlocks + file_header.Size();
 673     if (file_size < expected || header->empty[3] || file_size > max_expected) {
 674       NOTREACHED();
 675       LOG(ERROR) << "Unexpected file size";
 676       return false;
 677     }
 678     // We were in the middle of growing the file.
 679     int num_entries = (file_size - file_header.Size()) / header->entry_size;
 680     header->max_entries = num_entries;
 681   }
 682
 683   file_header.FixAllocationCounters();
 684   int empty_blocks = file_header.EmptyBlocks();
 685   if (empty_blocks + header->num_entries > header->max_entries)
 686     header->num_entries = header->max_entries - empty_blocks;
 687
 688   if (!file_header.ValidateCounters())
 689     return false;
 690
 691   header->updating = 0;
 692   return true;
 693 }
 694
 695 // We are interested in the total number of blocks used by this file type, and
 696 // the max number of blocks that we can store (reported as the percentage of
 697 // used blocks). In order to find out the number of used blocks, we have to
 698 // substract the empty blocks from the total blocks for each file in the chain.
 699 void BlockFiles::GetFileStats(int index, int* used_count, int* load) {
 700   int max_blocks = 0;
 701   *used_count = 0;
 702   *load = 0;
 703   for (;;) {
 704     if (!block_files_[index] && !OpenBlockFile(index))
 705       return;
 706
 707     BlockFileHeader* header =
 708         reinterpret_cast<BlockFileHeader*>(block_files_[index]->buffer());
 709
 710     max_blocks += header->max_entries;
 711     int used = header->max_entries;
 712     for (int i = 0; i < kMaxNumBlocks; i++) {
 713       used -= header->empty[i] * (i + 1);
 714       DCHECK_GE(used, 0);
 715     }
 716     *used_count += used;
 717
 718     if (!header->next_file)
 719       break;
 720     index = header->next_file;
 721   }
 722   if (max_blocks)
 723     *load = *used_count * 100 / max_blocks;
 724 }
 725
 726 base::FilePath BlockFiles::Name(int index) {
 727   // The file format allows for 256 files.
 728   DCHECK(index < 256 && index >= 0);
 729   std::string tmp = base::StringPrintf("%s%d", kBlockName, index);
 730   return path_.AppendASCII(tmp);
 731 }
 732
 733 }  // namespace disk_cache