Home | History | Annotate | Download | only in disk_cache 
      1 // Copyright (c) 2006-2008 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/file_util.h"
      8 #include "base/histogram.h"
      9 #include "base/string_util.h"
     10 #include "base/time.h"
     11 #include "net/disk_cache/cache_util.h"
     12 #include "net/disk_cache/file_lock.h"
     13 
     14 using base::Time;
     15 
     16 namespace {
     17 
     18 const char* kBlockName = "data_";
     19 
     20 // This array is used to perform a fast lookup of the nibble bit pattern to the
     21 // type of entry that can be stored there (number of consecutive blocks).
     22 const char s_types[16] = {4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
     23 
     24 // Returns the type of block (number of consecutive blocks that can be stored)
     25 // for a given nibble of the bitmap.
     26 inline int GetMapBlockType(uint8 value) {
     27   value &= 0xf;
     28   return s_types[value];
     29 }
     30 
     31 void FixAllocationCounters(disk_cache::BlockFileHeader* header);
     32 
     33 // Creates a new entry on the allocation map, updating the apropriate counters.
     34 // target is the type of block to use (number of empty blocks), and size is the
     35 // actual number of blocks to use.
     36 bool CreateMapBlock(int target, int size, disk_cache::BlockFileHeader* header,
     37                     int* index) {
     38   if (target <= 0 || target > disk_cache::kMaxNumBlocks ||
     39       size <= 0 || size > disk_cache::kMaxNumBlocks) {
     40     NOTREACHED();
     41     return false;
     42   }
     43 
     44   Time start = Time::Now();
     45   // We are going to process the map on 32-block chunks (32 bits), and on every
     46   // chunk, iterate through the 8 nibbles where the new block can be located.
     47   int current = header->hints[target - 1];
     48   for (int i = 0; i < header->max_entries / 32; i++, current++) {
     49     if (current == header->max_entries / 32)
     50       current = 0;
     51     uint32 map_block = header->allocation_map[current];
     52 
     53     for (int j = 0; j < 8; j++, map_block >>= 4) {
     54       if (GetMapBlockType(map_block) != target)
     55         continue;
     56 
     57       disk_cache::FileLock lock(header);
     58       int index_offset = j * 4 + 4 - target;
     59       *index = current * 32 + index_offset;
     60       uint32 to_add = ((1 << size) - 1) << index_offset;
     61       header->allocation_map[current] |= to_add;
     62 
     63       header->hints[target - 1] = current;
     64       header->empty[target - 1]--;
     65       DCHECK(header->empty[target - 1] >= 0);
     66       header->num_entries++;
     67       if (target != size) {
     68         header->empty[target - size - 1]++;
     69       }
     70       HISTOGRAM_TIMES("DiskCache.CreateBlock", Time::Now() - start);
     71       return true;
     72     }
     73   }
     74 
     75   // It is possible to have an undetected corruption (for example when the OS
     76   // crashes), fix it here.
     77   LOG(ERROR) << "Failing CreateMapBlock";
     78   FixAllocationCounters(header);
     79   return false;
     80 }
     81 
     82 // Deletes the block pointed by index from allocation_map, and updates the
     83 // relevant counters on the header.
     84 void DeleteMapBlock(int index, int size, disk_cache::BlockFileHeader* header) {
     85   if (size < 0 || size > disk_cache::kMaxNumBlocks) {
     86     NOTREACHED();
     87     return;
     88   }
     89   Time start = Time::Now();
     90   int byte_index = index / 8;
     91   uint8* byte_map = reinterpret_cast<uint8*>(header->allocation_map);
     92   uint8 map_block = byte_map[byte_index];
     93 
     94   if (index % 8 >= 4)
     95     map_block >>= 4;
     96 
     97   // See what type of block will be availabe after we delete this one.
     98   int bits_at_end = 4 - size - index % 4;
     99   uint8 end_mask = (0xf << (4 - bits_at_end)) & 0xf;
    100   bool update_counters = (map_block & end_mask) == 0;
    101   uint8 new_value = map_block & ~(((1 << size) - 1) << (index % 4));
    102   int new_type = GetMapBlockType(new_value);
    103 
    104   disk_cache::FileLock lock(header);
    105   DCHECK((((1 << size) - 1) << (index % 8)) < 0x100);
    106   uint8  to_clear = ((1 << size) - 1) << (index % 8);
    107   DCHECK((byte_map[byte_index] & to_clear) == to_clear);
    108   byte_map[byte_index] &= ~to_clear;
    109 
    110   if (update_counters) {
    111     if (bits_at_end)
    112       header->empty[bits_at_end - 1]--;
    113     header->empty[new_type - 1]++;
    114     DCHECK(header->empty[bits_at_end - 1] >= 0);
    115   }
    116   header->num_entries--;
    117   DCHECK(header->num_entries >= 0);
    118   HISTOGRAM_TIMES("DiskCache.DeleteBlock", Time::Now() - start);
    119 }
    120 
    121 // Restores the "empty counters" and allocation hints.
    122 void FixAllocationCounters(disk_cache::BlockFileHeader* header) {
    123   for (int i = 0; i < disk_cache::kMaxNumBlocks; i++) {
    124     header->hints[i] = 0;
    125     header->empty[i] = 0;
    126   }
    127 
    128   for (int i = 0; i < header->max_entries / 32; i++) {
    129     uint32 map_block = header->allocation_map[i];
    130 
    131     for (int j = 0; j < 8; j++, map_block >>= 4) {
    132       int type = GetMapBlockType(map_block);
    133       if (type)
    134         header->empty[type -1]++;
    135     }
    136   }
    137 }
    138 
    139 // Returns true if the current block file should not be used as-is to store more
    140 // records. |block_count| is the number of blocks to allocate.
    141 bool NeedToGrowBlockFile(const disk_cache::BlockFileHeader* header,
    142                          int block_count) {
    143   bool have_space = false;
    144   int empty_blocks = 0;
    145   for (int i = 0; i < disk_cache::kMaxNumBlocks; i++) {
    146     empty_blocks += header->empty[i] * (i + 1);
    147     if (i >= block_count - 1 && header->empty[i])
    148       have_space = true;
    149   }
    150 
    151   if (header->next_file && (empty_blocks < disk_cache::kMaxBlocks / 10)) {
    152     // This file is almost full but we already created another one, don't use
    153     // this file yet so that it is easier to find empty blocks when we start
    154     // using this file again.
    155     return true;
    156   }
    157   return !have_space;
    158 }
    159 
    160 }  // namespace
    161 
    162 namespace disk_cache {
    163 
    164 BlockFiles::~BlockFiles() {
    165   if (zero_buffer_)
    166     delete[] zero_buffer_;
    167   CloseFiles();
    168 }
    169 
    170 bool BlockFiles::Init(bool create_files) {
    171   DCHECK(!init_);
    172   if (init_)
    173     return false;
    174 
    175   block_files_.resize(kFirstAdditionlBlockFile);
    176   for (int i = 0; i < kFirstAdditionlBlockFile; i++) {
    177     if (create_files)
    178       if (!CreateBlockFile(i, static_cast<FileType>(i + 1), true))
    179         return false;
    180 
    181     if (!OpenBlockFile(i))
    182       return false;
    183 
    184     // Walk this chain of files removing empty ones.
    185     RemoveEmptyFile(static_cast<FileType>(i + 1));
    186   }
    187 
    188   init_ = true;
    189   return true;
    190 }
    191 
    192 void BlockFiles::CloseFiles() {
    193   init_ = false;
    194   for (unsigned int i = 0; i < block_files_.size(); i++) {
    195     if (block_files_[i]) {
    196       block_files_[i]->Release();
    197       block_files_[i] = NULL;
    198     }
    199   }
    200   block_files_.clear();
    201 }
    202 
    203 FilePath BlockFiles::Name(int index) {
    204   // The file format allows for 256 files.
    205   DCHECK(index < 256 || index >= 0);
    206   std::string tmp = StringPrintf("%s%d", kBlockName, index);
    207   return path_.AppendASCII(tmp);
    208 }
    209 
    210 bool BlockFiles::CreateBlockFile(int index, FileType file_type, bool force) {
    211   FilePath name = Name(index);
    212   int flags =
    213       force ? base::PLATFORM_FILE_CREATE_ALWAYS : base::PLATFORM_FILE_CREATE;
    214   flags |= base::PLATFORM_FILE_WRITE | base::PLATFORM_FILE_EXCLUSIVE_WRITE;
    215 
    216   scoped_refptr<File> file(new File(
    217       base::CreatePlatformFile(name, flags, NULL)));
    218   if (!file->IsValid())
    219     return false;
    220 
    221   BlockFileHeader header;
    222   header.entry_size = Addr::BlockSizeForFileType(file_type);
    223   header.this_file = static_cast<int16>(index);
    224   DCHECK(index <= kint16max && index >= 0);
    225 
    226   return file->Write(&header, sizeof(header), 0);
    227 }
    228 
    229 bool BlockFiles::OpenBlockFile(int index) {
    230   if (block_files_.size() - 1 < static_cast<unsigned int>(index)) {
    231     DCHECK(index > 0);
    232     int to_add = index - static_cast<int>(block_files_.size()) + 1;
    233     block_files_.resize(block_files_.size() + to_add);
    234   }
    235 
    236   FilePath name = Name(index);
    237   scoped_refptr<MappedFile> file(new MappedFile());
    238 
    239   if (!file->Init(name, kBlockHeaderSize)) {
    240     LOG(ERROR) << "Failed to open " << name.value();
    241     return false;
    242   }
    243 
    244   if (file->GetLength() < static_cast<size_t>(kBlockHeaderSize)) {
    245     LOG(ERROR) << "File too small " << name.value();
    246     return false;
    247   }
    248 
    249   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    250   if (kBlockMagic != header->magic || kCurrentVersion != header->version) {
    251     LOG(ERROR) << "Invalid file version or magic";
    252     return false;
    253   }
    254 
    255   if (header->updating) {
    256     // Last instance was not properly shutdown.
    257     if (!FixBlockFileHeader(file))
    258       return false;
    259   }
    260 
    261   DCHECK(!block_files_[index]);
    262   file.swap(&block_files_[index]);
    263   return true;
    264 }
    265 
    266 MappedFile* BlockFiles::GetFile(Addr address) {
    267   DCHECK(block_files_.size() >= 4);
    268   DCHECK(address.is_block_file() || !address.is_initialized());
    269   if (!address.is_initialized())
    270     return NULL;
    271 
    272   int file_index = address.FileNumber();
    273   if (static_cast<unsigned int>(file_index) >= block_files_.size() ||
    274       !block_files_[file_index]) {
    275     // We need to open the file
    276     if (!OpenBlockFile(file_index))
    277       return NULL;
    278   }
    279   DCHECK(block_files_.size() >= static_cast<unsigned int>(file_index));
    280   return block_files_[file_index];
    281 }
    282 
    283 bool BlockFiles::GrowBlockFile(MappedFile* file, BlockFileHeader* header) {
    284   if (kMaxBlocks == header->max_entries)
    285     return false;
    286 
    287   DCHECK(!header->empty[3]);
    288   int new_size = header->max_entries + 1024;
    289   if (new_size > kMaxBlocks)
    290     new_size = kMaxBlocks;
    291 
    292   int new_size_bytes = new_size * header->entry_size + sizeof(*header);
    293 
    294   FileLock lock(header);
    295   if (!file->SetLength(new_size_bytes)) {
    296     // Most likely we are trying to truncate the file, so the header is wrong.
    297     if (header->updating < 10 && !FixBlockFileHeader(file)) {
    298       // If we can't fix the file increase the lock guard so we'll pick it on
    299       // the next start and replace it.
    300       header->updating = 100;
    301       return false;
    302     }
    303     return (header->max_entries >= new_size);
    304   }
    305 
    306   header->empty[3] = (new_size - header->max_entries) / 4;  // 4 blocks entries
    307   header->max_entries = new_size;
    308 
    309   return true;
    310 }
    311 
    312 MappedFile* BlockFiles::FileForNewBlock(FileType block_type, int block_count) {
    313   COMPILE_ASSERT(RANKINGS == 1, invalid_fily_type);
    314   MappedFile* file = block_files_[block_type - 1];
    315   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    316 
    317   Time start = Time::Now();
    318   while (NeedToGrowBlockFile(header, block_count)) {
    319     if (kMaxBlocks == header->max_entries) {
    320       file = NextFile(file);
    321       if (!file)
    322         return NULL;
    323       header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    324       continue;
    325     }
    326 
    327     if (!GrowBlockFile(file, header))
    328       return NULL;
    329     break;
    330   }
    331   HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", Time::Now() - start);
    332   return file;
    333 }
    334 
    335 MappedFile* BlockFiles::NextFile(const MappedFile* file) {
    336   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    337   int new_file = header->next_file;
    338   if (!new_file) {
    339     // RANKINGS is not reported as a type for small entries, but we may be
    340     // extending the rankings block file.
    341     FileType type = Addr::RequiredFileType(header->entry_size);
    342     if (header->entry_size == Addr::BlockSizeForFileType(RANKINGS))
    343       type = RANKINGS;
    344 
    345     new_file = CreateNextBlockFile(type);
    346     if (!new_file)
    347       return NULL;
    348 
    349     FileLock lock(header);
    350     header->next_file = new_file;
    351   }
    352 
    353   // Only the block_file argument is relevant for what we want.
    354   Addr address(BLOCK_256, 1, new_file, 0);
    355   return GetFile(address);
    356 }
    357 
    358 int BlockFiles::CreateNextBlockFile(FileType block_type) {
    359   for (int i = kFirstAdditionlBlockFile; i <= kMaxBlockFile; i++) {
    360     if (CreateBlockFile(i, block_type, false))
    361       return i;
    362   }
    363   return 0;
    364 }
    365 
    366 // We walk the list of files for this particular block type, deleting the ones
    367 // that are empty.
    368 void BlockFiles::RemoveEmptyFile(FileType block_type) {
    369   MappedFile* file = block_files_[block_type - 1];
    370   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    371 
    372   while (header->next_file) {
    373     // Only the block_file argument is relevant for what we want.
    374     Addr address(BLOCK_256, 1, header->next_file, 0);
    375     MappedFile* next_file = GetFile(address);
    376     if (!next_file)
    377       return;
    378 
    379     BlockFileHeader* next_header =
    380         reinterpret_cast<BlockFileHeader*>(next_file->buffer());
    381     if (!next_header->num_entries) {
    382       DCHECK_EQ(next_header->entry_size, header->entry_size);
    383       // Delete next_file and remove it from the chain.
    384       int file_index = header->next_file;
    385       header->next_file = next_header->next_file;
    386       DCHECK(block_files_.size() >= static_cast<unsigned int>(file_index));
    387       block_files_[file_index]->Release();
    388       block_files_[file_index] = NULL;
    389 
    390       FilePath name = Name(file_index);
    391       int failure = DeleteCacheFile(name) ? 0 : 1;
    392       UMA_HISTOGRAM_COUNTS("DiskCache.DeleteFailed2", failure);
    393       if (failure)
    394         LOG(ERROR) << "Failed to delete " << name.value() << " from the cache.";
    395       continue;
    396     }
    397 
    398     header = next_header;
    399     file = next_file;
    400   }
    401 }
    402 
    403 bool BlockFiles::CreateBlock(FileType block_type, int block_count,
    404                              Addr* block_address) {
    405   if (block_type < RANKINGS || block_type > BLOCK_4K ||
    406       block_count < 1 || block_count > 4)
    407     return false;
    408   if (!init_)
    409     return false;
    410 
    411   MappedFile* file = FileForNewBlock(block_type, block_count);
    412   if (!file)
    413     return false;
    414 
    415   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    416 
    417   int target_size = 0;
    418   for (int i = block_count; i <= 4; i++) {
    419     if (header->empty[i - 1]) {
    420       target_size = i;
    421       break;
    422     }
    423   }
    424 
    425   DCHECK(target_size);
    426   int index;
    427   if (!CreateMapBlock(target_size, block_count, header, &index))
    428     return false;
    429 
    430   Addr address(block_type, block_count, header->this_file, index);
    431   block_address->set_value(address.value());
    432   return true;
    433 }
    434 
    435 void BlockFiles::DeleteBlock(Addr address, bool deep) {
    436   if (!address.is_initialized() || address.is_separate_file())
    437     return;
    438 
    439   if (!zero_buffer_) {
    440     zero_buffer_ = new char[Addr::BlockSizeForFileType(BLOCK_4K) * 4];
    441     memset(zero_buffer_, 0, Addr::BlockSizeForFileType(BLOCK_4K) * 4);
    442   }
    443   MappedFile* file = GetFile(address);
    444   if (!file)
    445     return;
    446 
    447   size_t size = address.BlockSize() * address.num_blocks();
    448   size_t offset = address.start_block() * address.BlockSize() +
    449                   kBlockHeaderSize;
    450   if (deep)
    451     file->Write(zero_buffer_, size, offset);
    452 
    453   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    454   DeleteMapBlock(address.start_block(), address.num_blocks(), header);
    455   if (!header->num_entries) {
    456     // This file is now empty. Let's try to delete it.
    457     FileType type = Addr::RequiredFileType(header->entry_size);
    458     if (Addr::BlockSizeForFileType(RANKINGS) == header->entry_size)
    459       type = RANKINGS;
    460     RemoveEmptyFile(type);
    461   }
    462 }
    463 
    464 bool BlockFiles::FixBlockFileHeader(MappedFile* file) {
    465   BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer());
    466   int file_size = static_cast<int>(file->GetLength());
    467   if (file_size < static_cast<int>(sizeof(*header)))
    468     return false;  // file_size > 2GB is also an error.
    469 
    470   int expected = header->entry_size * header->max_entries + sizeof(*header);
    471   if (file_size != expected) {
    472     int max_expected = header->entry_size * kMaxBlocks + sizeof(*header);
    473     if (file_size < expected || header->empty[3] || file_size > max_expected) {
    474       NOTREACHED();
    475       LOG(ERROR) << "Unexpected file size";
    476       return false;
    477     }
    478     // We were in the middle of growing the file.
    479     int num_entries = (file_size - sizeof(*header)) / header->entry_size;
    480     header->max_entries = num_entries;
    481   }
    482 
    483   FixAllocationCounters(header);
    484   header->updating = 0;
    485   return true;
    486 }
    487 
    488 }  // namespace disk_cache
    489