net/disk_cache/blockfile/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/blockfile/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/blockfile/file_lock.h"
  15 #include "net/disk_cache/blockfile/stress_support.h"
  16 #include "net/disk_cache/blockfile/trace.h"
  17 #include "net/disk_cache/cache_util.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(uint32 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       LOCAL_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   LOCAL_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 (int16 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 = force ? base::File::FLAG_CREATE_ALWAYS : base::File::FLAG_CREATE;
 449   flags |= base::File::FLAG_WRITE | base::File::FLAG_EXCLUSIVE_WRITE;
 450
 451   scoped_refptr<File> file(new File(base::File(name, flags)));
 452   if (!file->IsValid())
 453     return false;
 454
 455   BlockFileHeader header;
 456   memset(&header, 0, sizeof(header));
 457   header.magic = kBlockMagic;
 458   header.version = kBlockVersion2;
 459   header.entry_size = Addr::BlockSizeForFileType(file_type);
 460   header.this_file = static_cast<int16>(index);
 461   DCHECK(index <= kint16max && index >= 0);
 462
 463   return file->Write(&header, sizeof(header), 0);
 464 }
 465
 466 bool BlockFiles::OpenBlockFile(int index) {
 467   if (block_files_.size() - 1 < static_cast<unsigned int>(index)) {
 468     DCHECK(index > 0);
 469     int to_add = index - static_cast<int>(block_files_.size()) + 1;
 470     block_files_.resize(block_files_.size() + to_add);
 471   }
 472
 473   base::FilePath name = Name(index);
 474   scoped_refptr<MappedFile> file(new MappedFile());
 475
 476   if (!file->Init(name, kBlockHeaderSize)) {
 477     LOG(ERROR) << "Failed to open " << name.value();
 478     return false;
 479   }
 480
 481   size_t file_len = file->GetLength();
 482   if (file_len < static_cast<size_t>(kBlockHeaderSize)) {
 483     LOG(ERROR) << "File too small " << name.value();
 484     return false;
 485   }
 486
 487   BlockHeader file_header(file.get());
 488   BlockFileHeader* header = file_header.Header();
 489   if (kBlockMagic != header->magic || kBlockVersion2 != header->version) {
 490     LOG(ERROR) << "Invalid file version or magic " << name.value();
 491     return false;
 492   }
 493
 494   if (header->updating || !file_header.ValidateCounters()) {
 495     // Last instance was not properly shutdown, or counters are out of sync.
 496     if (!FixBlockFileHeader(file.get())) {
 497       LOG(ERROR) << "Unable to fix block file " << name.value();
 498       return false;
 499     }
 500   }
 501
 502   if (static_cast<int>(file_len) <
 503       header->max_entries * header->entry_size + kBlockHeaderSize) {
 504     LOG(ERROR) << "File too small " << name.value();
 505     return false;
 506   }
 507
 508   if (index == 0) {
 509     // Load the links file into memory.
 510     if (!file->Preload())
 511       return false;
 512   }
 513
 514   ScopedFlush flush(file.get());
 515   DCHECK(!block_files_[index]);
 516   file.swap(&block_files_[index]);
 517   return true;
 518 }
 519
 520 bool BlockFiles::GrowBlockFile(MappedFile* file, BlockFileHeader* header) {
 521   if (kMaxBlocks == header->max_entries)
 522     return false;
 523
 524   ScopedFlush flush(file);
 525   DCHECK(!header->empty[3]);
 526   int new_size = header->max_entries + 1024;
 527   if (new_size > kMaxBlocks)
 528     new_size = kMaxBlocks;
 529
 530   int new_size_bytes = new_size * header->entry_size + sizeof(*header);
 531
 532   if (!file->SetLength(new_size_bytes)) {
 533     // Most likely we are trying to truncate the file, so the header is wrong.
 534     if (header->updating < 10 && !FixBlockFileHeader(file)) {
 535       // If we can't fix the file increase the lock guard so we'll pick it on
 536       // the next start and replace it.
 537       header->updating = 100;
 538       return false;
 539     }
 540     return (header->max_entries >= new_size);
 541   }
 542
 543   FileLock lock(header);
 544   header->empty[3] = (new_size - header->max_entries) / 4;  // 4 blocks entries
 545   header->max_entries = new_size;
 546
 547   return true;
 548 }
 549
 550 MappedFile* BlockFiles::FileForNewBlock(FileType block_type, int block_count) {
 551   static_assert(RANKINGS == 1, "invalid file type");
 552   MappedFile* file = block_files_[block_type - 1];
 553   BlockHeader file_header(file);
 554
 555   TimeTicks start = TimeTicks::Now();
 556   while (file_header.NeedToGrowBlockFile(block_count)) {
 557     if (kMaxBlocks == file_header.Header()->max_entries) {
 558       file = NextFile(file);
 559       if (!file)
 560         return NULL;
 561       file_header = BlockHeader(file);
 562       continue;
 563     }
 564
 565     if (!GrowBlockFile(file, file_header.Header()))
 566       return NULL;
 567     break;
 568   }
 569   LOCAL_HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock",
 570                         TimeTicks::Now() - start);
 571   return file;
 572 }
 573
 574 MappedFile* BlockFiles::NextFile(MappedFile* file) {
 575   ScopedFlush flush(file);
 576   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
 577   int16 new_file = header->next_file;
 578   if (!new_file) {
 579     // RANKINGS is not reported as a type for small entries, but we may be
 580     // extending the rankings block file.
 581     FileType type = Addr::RequiredFileType(header->entry_size);
 582     if (header->entry_size == Addr::BlockSizeForFileType(RANKINGS))
 583       type = RANKINGS;
 584
 585     new_file = CreateNextBlockFile(type);
 586     if (!new_file)
 587       return NULL;
 588
 589     FileLock lock(header);
 590     header->next_file = new_file;
 591   }
 592
 593   // Only the block_file argument is relevant for what we want.
 594   Addr address(BLOCK_256, 1, new_file, 0);
 595   return GetFile(address);
 596 }
 597
 598 int16 BlockFiles::CreateNextBlockFile(FileType block_type) {
 599   for (int16 i = kFirstAdditionalBlockFile; i <= kMaxBlockFile; i++) {
 600     if (CreateBlockFile(i, block_type, false))
 601       return i;
 602   }
 603   return 0;
 604 }
 605
 606 // We walk the list of files for this particular block type, deleting the ones
 607 // that are empty.
 608 bool BlockFiles::RemoveEmptyFile(FileType block_type) {
 609   MappedFile* file = block_files_[block_type - 1];
 610   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
 611
 612   while (header->next_file) {
 613     // Only the block_file argument is relevant for what we want.
 614     Addr address(BLOCK_256, 1, header->next_file, 0);
 615     MappedFile* next_file = GetFile(address);
 616     if (!next_file)
 617       return false;
 618
 619     BlockFileHeader* next_header =
 620         reinterpret_cast<BlockFileHeader*>(next_file->buffer());
 621     if (!next_header->num_entries) {
 622       DCHECK_EQ(next_header->entry_size, header->entry_size);
 623       // Delete next_file and remove it from the chain.
 624       int file_index = header->next_file;
 625       header->next_file = next_header->next_file;
 626       DCHECK(block_files_.size() >= static_cast<unsigned int>(file_index));
 627       file->Flush();
 628
 629       // We get a new handle to the file and release the old one so that the
 630       // file gets unmmaped... so we can delete it.
 631       base::FilePath name = Name(file_index);
 632       scoped_refptr<File> this_file(new File(false));
 633       this_file->Init(name);
 634       block_files_[file_index]->Release();
 635       block_files_[file_index] = NULL;
 636
 637       int failure = DeleteCacheFile(name) ? 0 : 1;
 638       UMA_HISTOGRAM_COUNTS("DiskCache.DeleteFailed2", failure);
 639       if (failure)
 640         LOG(ERROR) << "Failed to delete " << name.value() << " from the cache.";
 641       continue;
 642     }
 643
 644     header = next_header;
 645     file = next_file;
 646   }
 647   return true;
 648 }
 649
 650 // Note that we expect to be called outside of a FileLock... however, we cannot
 651 // DCHECK on header->updating because we may be fixing a crash.
 652 bool BlockFiles::FixBlockFileHeader(MappedFile* file) {
 653   ScopedFlush flush(file);
 654   BlockHeader file_header(file);
 655   int file_size = static_cast<int>(file->GetLength());
 656   if (file_size < file_header.Size())
 657     return false;  // file_size > 2GB is also an error.
 658
 659   const int kMinHeaderBlockSize = 36;
 660   const int kMaxHeaderBlockSize = 4096;
 661   BlockFileHeader* header = file_header.Header();
 662   if (header->entry_size < kMinHeaderBlockSize ||
 663       header->entry_size > kMaxHeaderBlockSize || header->num_entries < 0)
 664     return false;
 665
 666   // Make sure that we survive crashes.
 667   header->updating = 1;
 668   int expected = header->entry_size * header->max_entries + file_header.Size();
 669   if (file_size != expected) {
 670     int max_expected = header->entry_size * kMaxBlocks + file_header.Size();
 671     if (file_size < expected || header->empty[3] || file_size > max_expected) {
 672       NOTREACHED();
 673       LOG(ERROR) << "Unexpected file size";
 674       return false;
 675     }
 676     // We were in the middle of growing the file.
 677     int num_entries = (file_size - file_header.Size()) / header->entry_size;
 678     header->max_entries = num_entries;
 679   }
 680
 681   file_header.FixAllocationCounters();
 682   int empty_blocks = file_header.EmptyBlocks();
 683   if (empty_blocks + header->num_entries > header->max_entries)
 684     header->num_entries = header->max_entries - empty_blocks;
 685
 686   if (!file_header.ValidateCounters())
 687     return false;
 688
 689   header->updating = 0;
 690   return true;
 691 }
 692
 693 // We are interested in the total number of blocks used by this file type, and
 694 // the max number of blocks that we can store (reported as the percentage of
 695 // used blocks). In order to find out the number of used blocks, we have to
 696 // substract the empty blocks from the total blocks for each file in the chain.
 697 void BlockFiles::GetFileStats(int index, int* used_count, int* load) {
 698   int max_blocks = 0;
 699   *used_count = 0;
 700   *load = 0;
 701   for (;;) {
 702     if (!block_files_[index] && !OpenBlockFile(index))
 703       return;
 704
 705     BlockFileHeader* header =
 706         reinterpret_cast<BlockFileHeader*>(block_files_[index]->buffer());
 707
 708     max_blocks += header->max_entries;
 709     int used = header->max_entries;
 710     for (int i = 0; i < kMaxNumBlocks; i++) {
 711       used -= header->empty[i] * (i + 1);
 712       DCHECK_GE(used, 0);
 713     }
 714     *used_count += used;
 715
 716     if (!header->next_file)
 717       break;
 718     index = header->next_file;
 719   }
 720   if (max_blocks)
 721     *load = *used_count * 100 / max_blocks;
 722 }
 723
 724 base::FilePath BlockFiles::Name(int index) {
 725   // The file format allows for 256 files.
 726   DCHECK(index < 256 && index >= 0);
 727   std::string tmp = base::StringPrintf("%s%d", kBlockName, index);
 728   return path_.AppendASCII(tmp);
 729 }
 730
 731 }  // namespace disk_cache