block_files.cc revision e5d81f57cb97b3b6b7fccc9c5610d21eb81db09d 
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
19using base::TimeTicks;
20
21namespace {
22
23const 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).
27const 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.
31inline int GetMapBlockType(uint8 value) {
32  value &= 0xf;
33  return s_types[value];
34}
35
36}  // namespace
37
38namespace disk_cache {
39
40BlockHeader::BlockHeader() : header_(NULL) {
41}
42
43BlockHeader::BlockHeader(BlockFileHeader* header) : header_(header) {
44}
45
46BlockHeader::BlockHeader(MappedFile* file)
47    : header_(reinterpret_cast<BlockFileHeader*>(file->buffer())) {
48}
49
50BlockHeader::BlockHeader(const BlockHeader& other) : header_(other.header_) {
51}
52
53BlockHeader::~BlockHeader() {
54}
55
56bool 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
116void 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().
155bool 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
171void 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
188bool 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
206bool 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
216int 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
226int BlockHeader::MinimumAllocations() const {
227  return header_->empty[kMaxNumBlocks - 1];
228}
229
230int BlockHeader::Capacity() const {
231  return header_->max_entries;
232}
233
234bool 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
246int BlockHeader::FileId() const {
247  return header_->this_file;
248}
249
250int BlockHeader::NextFileId() const {
251  return header_->next_file;
252}
253
254int BlockHeader::Size() const {
255  return static_cast<int>(sizeof(*header_));
256}
257
258BlockFileHeader* BlockHeader::Header() {
259  return header_;
260}
261
262// ------------------------------------------------------------------------
263
264BlockFiles::BlockFiles(const base::FilePath& path)
265    : init_(false), zero_buffer_(NULL), path_(path) {
266}
267
268BlockFiles::~BlockFiles() {
269  if (zero_buffer_)
270    delete[] zero_buffer_;
271  CloseFiles();
272}
273
274bool 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
299MappedFile* 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
318bool 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
348void 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
384void 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
398void 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
416bool 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
446bool 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
468bool 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.
512    if (!file->Preload())
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
522bool 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
552MappedFile* 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
575MappedFile* 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
599int 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.
609bool 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.
653bool 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.
698void 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
725base::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
733