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