| OLD | NEW |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "net/disk_cache/blockfile/block_files.h" | 5 #include "net/disk_cache/blockfile/block_files.h" |
| 6 | 6 |
| 7 #include <limits> |
| 8 |
| 7 #include "base/atomicops.h" | 9 #include "base/atomicops.h" |
| 8 #include "base/files/file_path.h" | 10 #include "base/files/file_path.h" |
| 9 #include "base/metrics/histogram_macros.h" | 11 #include "base/metrics/histogram_macros.h" |
| 10 #include "base/strings/string_util.h" | 12 #include "base/strings/string_util.h" |
| 11 #include "base/strings/stringprintf.h" | 13 #include "base/strings/stringprintf.h" |
| 12 #include "base/threading/thread_checker.h" | 14 #include "base/threading/thread_checker.h" |
| 13 #include "base/time/time.h" | 15 #include "base/time/time.h" |
| 14 #include "net/disk_cache/blockfile/file_lock.h" | 16 #include "net/disk_cache/blockfile/file_lock.h" |
| 15 #include "net/disk_cache/blockfile/stress_support.h" | 17 #include "net/disk_cache/blockfile/stress_support.h" |
| 16 #include "net/disk_cache/blockfile/trace.h" | 18 #include "net/disk_cache/blockfile/trace.h" |
| 17 #include "net/disk_cache/cache_util.h" | 19 #include "net/disk_cache/cache_util.h" |
| 18 | 20 |
| 19 using base::TimeTicks; | 21 using base::TimeTicks; |
| 20 | 22 |
| 21 namespace { | 23 namespace { |
| 22 | 24 |
| 23 const char kBlockName[] = "data_"; | 25 const char kBlockName[] = "data_"; |
| 24 | 26 |
| 25 // This array is used to perform a fast lookup of the nibble bit pattern to the | 27 // 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). | 28 // 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}; | 29 const char s_types[16] = {4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}; |
| 28 | 30 |
| 29 // Returns the type of block (number of consecutive blocks that can be stored) | 31 // Returns the type of block (number of consecutive blocks that can be stored) |
| 30 // for a given nibble of the bitmap. | 32 // for a given nibble of the bitmap. |
| 31 inline int GetMapBlockType(uint32 value) { | 33 inline int GetMapBlockType(uint32_t value) { |
| 32 value &= 0xf; | 34 value &= 0xf; |
| 33 return s_types[value]; | 35 return s_types[value]; |
| 34 } | 36 } |
| 35 | 37 |
| 36 } // namespace | 38 } // namespace |
| 37 | 39 |
| 38 namespace disk_cache { | 40 namespace disk_cache { |
| 39 | 41 |
| 40 BlockHeader::BlockHeader() : header_(NULL) { | 42 BlockHeader::BlockHeader() : header_(NULL) { |
| 41 } | 43 } |
| (...skipping 26 matching lines...) Expand all Loading... |
| 68 return false; | 70 return false; |
| 69 } | 71 } |
| 70 | 72 |
| 71 TimeTicks start = TimeTicks::Now(); | 73 TimeTicks start = TimeTicks::Now(); |
| 72 // We are going to process the map on 32-block chunks (32 bits), and on every | 74 // 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. | 75 // chunk, iterate through the 8 nibbles where the new block can be located. |
| 74 int current = header_->hints[target - 1]; | 76 int current = header_->hints[target - 1]; |
| 75 for (int i = 0; i < header_->max_entries / 32; i++, current++) { | 77 for (int i = 0; i < header_->max_entries / 32; i++, current++) { |
| 76 if (current == header_->max_entries / 32) | 78 if (current == header_->max_entries / 32) |
| 77 current = 0; | 79 current = 0; |
| 78 uint32 map_block = header_->allocation_map[current]; | 80 uint32_t map_block = header_->allocation_map[current]; |
| 79 | 81 |
| 80 for (int j = 0; j < 8; j++, map_block >>= 4) { | 82 for (int j = 0; j < 8; j++, map_block >>= 4) { |
| 81 if (GetMapBlockType(map_block) != target) | 83 if (GetMapBlockType(map_block) != target) |
| 82 continue; | 84 continue; |
| 83 | 85 |
| 84 disk_cache::FileLock lock(header_); | 86 disk_cache::FileLock lock(header_); |
| 85 int index_offset = j * 4 + 4 - target; | 87 int index_offset = j * 4 + 4 - target; |
| 86 *index = current * 32 + index_offset; | 88 *index = current * 32 + index_offset; |
| 87 STRESS_DCHECK(*index / 4 == (*index + size - 1) / 4); | 89 STRESS_DCHECK(*index / 4 == (*index + size - 1) / 4); |
| 88 uint32 to_add = ((1 << size) - 1) << index_offset; | 90 uint32_t to_add = ((1 << size) - 1) << index_offset; |
| 89 header_->num_entries++; | 91 header_->num_entries++; |
| 90 | 92 |
| 91 // Note that there is no race in the normal sense here, but if we enforce | 93 // 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 | 94 // 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 | 95 // can assert that even if we crash here, num_entries will never be less |
| 94 // than the actual number of used blocks. | 96 // than the actual number of used blocks. |
| 95 base::subtle::MemoryBarrier(); | 97 base::subtle::MemoryBarrier(); |
| 96 header_->allocation_map[current] |= to_add; | 98 header_->allocation_map[current] |= to_add; |
| 97 | 99 |
| 98 header_->hints[target - 1] = current; | 100 header_->hints[target - 1] = current; |
| (...skipping 14 matching lines...) Expand all Loading... |
| 113 return false; | 115 return false; |
| 114 } | 116 } |
| 115 | 117 |
| 116 void BlockHeader::DeleteMapBlock(int index, int size) { | 118 void BlockHeader::DeleteMapBlock(int index, int size) { |
| 117 if (size < 0 || size > kMaxNumBlocks) { | 119 if (size < 0 || size > kMaxNumBlocks) { |
| 118 NOTREACHED(); | 120 NOTREACHED(); |
| 119 return; | 121 return; |
| 120 } | 122 } |
| 121 TimeTicks start = TimeTicks::Now(); | 123 TimeTicks start = TimeTicks::Now(); |
| 122 int byte_index = index / 8; | 124 int byte_index = index / 8; |
| 123 uint8* byte_map = reinterpret_cast<uint8*>(header_->allocation_map); | 125 uint8_t* byte_map = reinterpret_cast<uint8_t*>(header_->allocation_map); |
| 124 uint8 map_block = byte_map[byte_index]; | 126 uint8_t map_block = byte_map[byte_index]; |
| 125 | 127 |
| 126 if (index % 8 >= 4) | 128 if (index % 8 >= 4) |
| 127 map_block >>= 4; | 129 map_block >>= 4; |
| 128 | 130 |
| 129 // See what type of block will be available after we delete this one. | 131 // See what type of block will be available after we delete this one. |
| 130 int bits_at_end = 4 - size - index % 4; | 132 int bits_at_end = 4 - size - index % 4; |
| 131 uint8 end_mask = (0xf << (4 - bits_at_end)) & 0xf; | 133 uint8_t end_mask = (0xf << (4 - bits_at_end)) & 0xf; |
| 132 bool update_counters = (map_block & end_mask) == 0; | 134 bool update_counters = (map_block & end_mask) == 0; |
| 133 uint8 new_value = map_block & ~(((1 << size) - 1) << (index % 4)); | 135 uint8_t new_value = map_block & ~(((1 << size) - 1) << (index % 4)); |
| 134 int new_type = GetMapBlockType(new_value); | 136 int new_type = GetMapBlockType(new_value); |
| 135 | 137 |
| 136 disk_cache::FileLock lock(header_); | 138 disk_cache::FileLock lock(header_); |
| 137 STRESS_DCHECK((((1 << size) - 1) << (index % 8)) < 0x100); | 139 STRESS_DCHECK((((1 << size) - 1) << (index % 8)) < 0x100); |
| 138 uint8 to_clear = ((1 << size) - 1) << (index % 8); | 140 uint8_t to_clear = ((1 << size) - 1) << (index % 8); |
| 139 STRESS_DCHECK((byte_map[byte_index] & to_clear) == to_clear); | 141 STRESS_DCHECK((byte_map[byte_index] & to_clear) == to_clear); |
| 140 byte_map[byte_index] &= ~to_clear; | 142 byte_map[byte_index] &= ~to_clear; |
| 141 | 143 |
| 142 if (update_counters) { | 144 if (update_counters) { |
| 143 if (bits_at_end) | 145 if (bits_at_end) |
| 144 header_->empty[bits_at_end - 1]--; | 146 header_->empty[bits_at_end - 1]--; |
| 145 header_->empty[new_type - 1]++; | 147 header_->empty[new_type - 1]++; |
| 146 STRESS_DCHECK(header_->empty[bits_at_end - 1] >= 0); | 148 STRESS_DCHECK(header_->empty[bits_at_end - 1] >= 0); |
| 147 } | 149 } |
| 148 base::subtle::MemoryBarrier(); | 150 base::subtle::MemoryBarrier(); |
| 149 header_->num_entries--; | 151 header_->num_entries--; |
| 150 STRESS_DCHECK(header_->num_entries >= 0); | 152 STRESS_DCHECK(header_->num_entries >= 0); |
| 151 LOCAL_HISTOGRAM_TIMES("DiskCache.DeleteBlock", TimeTicks::Now() - start); | 153 LOCAL_HISTOGRAM_TIMES("DiskCache.DeleteBlock", TimeTicks::Now() - start); |
| 152 } | 154 } |
| 153 | 155 |
| 154 // Note that this is a simplified version of DeleteMapBlock(). | 156 // Note that this is a simplified version of DeleteMapBlock(). |
| 155 bool BlockHeader::UsedMapBlock(int index, int size) { | 157 bool BlockHeader::UsedMapBlock(int index, int size) { |
| 156 if (size < 0 || size > kMaxNumBlocks) | 158 if (size < 0 || size > kMaxNumBlocks) |
| 157 return false; | 159 return false; |
| 158 | 160 |
| 159 int byte_index = index / 8; | 161 int byte_index = index / 8; |
| 160 uint8* byte_map = reinterpret_cast<uint8*>(header_->allocation_map); | 162 uint8_t* byte_map = reinterpret_cast<uint8_t*>(header_->allocation_map); |
| 161 uint8 map_block = byte_map[byte_index]; | 163 uint8_t map_block = byte_map[byte_index]; |
| 162 | 164 |
| 163 if (index % 8 >= 4) | 165 if (index % 8 >= 4) |
| 164 map_block >>= 4; | 166 map_block >>= 4; |
| 165 | 167 |
| 166 STRESS_DCHECK((((1 << size) - 1) << (index % 8)) < 0x100); | 168 STRESS_DCHECK((((1 << size) - 1) << (index % 8)) < 0x100); |
| 167 uint8 to_clear = ((1 << size) - 1) << (index % 8); | 169 uint8_t to_clear = ((1 << size) - 1) << (index % 8); |
| 168 return ((byte_map[byte_index] & to_clear) == to_clear); | 170 return ((byte_map[byte_index] & to_clear) == to_clear); |
| 169 } | 171 } |
| 170 | 172 |
| 171 void BlockHeader::FixAllocationCounters() { | 173 void BlockHeader::FixAllocationCounters() { |
| 172 for (int i = 0; i < kMaxNumBlocks; i++) { | 174 for (int i = 0; i < kMaxNumBlocks; i++) { |
| 173 header_->hints[i] = 0; | 175 header_->hints[i] = 0; |
| 174 header_->empty[i] = 0; | 176 header_->empty[i] = 0; |
| 175 } | 177 } |
| 176 | 178 |
| 177 for (int i = 0; i < header_->max_entries / 32; i++) { | 179 for (int i = 0; i < header_->max_entries / 32; i++) { |
| 178 uint32 map_block = header_->allocation_map[i]; | 180 uint32_t map_block = header_->allocation_map[i]; |
| 179 | 181 |
| 180 for (int j = 0; j < 8; j++, map_block >>= 4) { | 182 for (int j = 0; j < 8; j++, map_block >>= 4) { |
| 181 int type = GetMapBlockType(map_block); | 183 int type = GetMapBlockType(map_block); |
| 182 if (type) | 184 if (type) |
| 183 header_->empty[type -1]++; | 185 header_->empty[type -1]++; |
| 184 } | 186 } |
| 185 } | 187 } |
| 186 } | 188 } |
| 187 | 189 |
| 188 bool BlockHeader::NeedToGrowBlockFile(int block_count) const { | 190 bool BlockHeader::NeedToGrowBlockFile(int block_count) const { |
| (...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 272 } | 274 } |
| 273 | 275 |
| 274 bool BlockFiles::Init(bool create_files) { | 276 bool BlockFiles::Init(bool create_files) { |
| 275 DCHECK(!init_); | 277 DCHECK(!init_); |
| 276 if (init_) | 278 if (init_) |
| 277 return false; | 279 return false; |
| 278 | 280 |
| 279 thread_checker_.reset(new base::ThreadChecker); | 281 thread_checker_.reset(new base::ThreadChecker); |
| 280 | 282 |
| 281 block_files_.resize(kFirstAdditionalBlockFile); | 283 block_files_.resize(kFirstAdditionalBlockFile); |
| 282 for (int16 i = 0; i < kFirstAdditionalBlockFile; i++) { | 284 for (int16_t i = 0; i < kFirstAdditionalBlockFile; i++) { |
| 283 if (create_files) | 285 if (create_files) |
| 284 if (!CreateBlockFile(i, static_cast<FileType>(i + 1), true)) | 286 if (!CreateBlockFile(i, static_cast<FileType>(i + 1), true)) |
| 285 return false; | 287 return false; |
| 286 | 288 |
| 287 if (!OpenBlockFile(i)) | 289 if (!OpenBlockFile(i)) |
| 288 return false; | 290 return false; |
| 289 | 291 |
| 290 // Walk this chain of files removing empty ones. | 292 // Walk this chain of files removing empty ones. |
| 291 if (!RemoveEmptyFile(static_cast<FileType>(i + 1))) | 293 if (!RemoveEmptyFile(static_cast<FileType>(i + 1))) |
| 292 return false; | 294 return false; |
| (...skipping 157 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 450 | 452 |
| 451 scoped_refptr<File> file(new File(base::File(name, flags))); | 453 scoped_refptr<File> file(new File(base::File(name, flags))); |
| 452 if (!file->IsValid()) | 454 if (!file->IsValid()) |
| 453 return false; | 455 return false; |
| 454 | 456 |
| 455 BlockFileHeader header; | 457 BlockFileHeader header; |
| 456 memset(&header, 0, sizeof(header)); | 458 memset(&header, 0, sizeof(header)); |
| 457 header.magic = kBlockMagic; | 459 header.magic = kBlockMagic; |
| 458 header.version = kBlockVersion2; | 460 header.version = kBlockVersion2; |
| 459 header.entry_size = Addr::BlockSizeForFileType(file_type); | 461 header.entry_size = Addr::BlockSizeForFileType(file_type); |
| 460 header.this_file = static_cast<int16>(index); | 462 header.this_file = static_cast<int16_t>(index); |
| 461 DCHECK(index <= kint16max && index >= 0); | 463 DCHECK(index <= std::numeric_limits<int16_t>::max() && index >= 0); |
| 462 | 464 |
| 463 return file->Write(&header, sizeof(header), 0); | 465 return file->Write(&header, sizeof(header), 0); |
| 464 } | 466 } |
| 465 | 467 |
| 466 bool BlockFiles::OpenBlockFile(int index) { | 468 bool BlockFiles::OpenBlockFile(int index) { |
| 467 if (block_files_.size() - 1 < static_cast<unsigned int>(index)) { | 469 if (block_files_.size() - 1 < static_cast<unsigned int>(index)) { |
| 468 DCHECK(index > 0); | 470 DCHECK(index > 0); |
| 469 int to_add = index - static_cast<int>(block_files_.size()) + 1; | 471 int to_add = index - static_cast<int>(block_files_.size()) + 1; |
| 470 block_files_.resize(block_files_.size() + to_add); | 472 block_files_.resize(block_files_.size() + to_add); |
| 471 } | 473 } |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 567 break; | 569 break; |
| 568 } | 570 } |
| 569 LOCAL_HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", | 571 LOCAL_HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", |
| 570 TimeTicks::Now() - start); | 572 TimeTicks::Now() - start); |
| 571 return file; | 573 return file; |
| 572 } | 574 } |
| 573 | 575 |
| 574 MappedFile* BlockFiles::NextFile(MappedFile* file) { | 576 MappedFile* BlockFiles::NextFile(MappedFile* file) { |
| 575 ScopedFlush flush(file); | 577 ScopedFlush flush(file); |
| 576 BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer()); | 578 BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer()); |
| 577 int16 new_file = header->next_file; | 579 int16_t new_file = header->next_file; |
| 578 if (!new_file) { | 580 if (!new_file) { |
| 579 // RANKINGS is not reported as a type for small entries, but we may be | 581 // RANKINGS is not reported as a type for small entries, but we may be |
| 580 // extending the rankings block file. | 582 // extending the rankings block file. |
| 581 FileType type = Addr::RequiredFileType(header->entry_size); | 583 FileType type = Addr::RequiredFileType(header->entry_size); |
| 582 if (header->entry_size == Addr::BlockSizeForFileType(RANKINGS)) | 584 if (header->entry_size == Addr::BlockSizeForFileType(RANKINGS)) |
| 583 type = RANKINGS; | 585 type = RANKINGS; |
| 584 | 586 |
| 585 new_file = CreateNextBlockFile(type); | 587 new_file = CreateNextBlockFile(type); |
| 586 if (!new_file) | 588 if (!new_file) |
| 587 return NULL; | 589 return NULL; |
| 588 | 590 |
| 589 FileLock lock(header); | 591 FileLock lock(header); |
| 590 header->next_file = new_file; | 592 header->next_file = new_file; |
| 591 } | 593 } |
| 592 | 594 |
| 593 // Only the block_file argument is relevant for what we want. | 595 // Only the block_file argument is relevant for what we want. |
| 594 Addr address(BLOCK_256, 1, new_file, 0); | 596 Addr address(BLOCK_256, 1, new_file, 0); |
| 595 return GetFile(address); | 597 return GetFile(address); |
| 596 } | 598 } |
| 597 | 599 |
| 598 int16 BlockFiles::CreateNextBlockFile(FileType block_type) { | 600 int16_t BlockFiles::CreateNextBlockFile(FileType block_type) { |
| 599 for (int16 i = kFirstAdditionalBlockFile; i <= kMaxBlockFile; i++) { | 601 for (int16_t i = kFirstAdditionalBlockFile; i <= kMaxBlockFile; i++) { |
| 600 if (CreateBlockFile(i, block_type, false)) | 602 if (CreateBlockFile(i, block_type, false)) |
| 601 return i; | 603 return i; |
| 602 } | 604 } |
| 603 return 0; | 605 return 0; |
| 604 } | 606 } |
| 605 | 607 |
| 606 // We walk the list of files for this particular block type, deleting the ones | 608 // We walk the list of files for this particular block type, deleting the ones |
| 607 // that are empty. | 609 // that are empty. |
| 608 bool BlockFiles::RemoveEmptyFile(FileType block_type) { | 610 bool BlockFiles::RemoveEmptyFile(FileType block_type) { |
| 609 MappedFile* file = block_files_[block_type - 1]; | 611 MappedFile* file = block_files_[block_type - 1]; |
| (...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 722 } | 724 } |
| 723 | 725 |
| 724 base::FilePath BlockFiles::Name(int index) { | 726 base::FilePath BlockFiles::Name(int index) { |
| 725 // The file format allows for 256 files. | 727 // The file format allows for 256 files. |
| 726 DCHECK(index < 256 && index >= 0); | 728 DCHECK(index < 256 && index >= 0); |
| 727 std::string tmp = base::StringPrintf("%s%d", kBlockName, index); | 729 std::string tmp = base::StringPrintf("%s%d", kBlockName, index); |
| 728 return path_.AppendASCII(tmp); | 730 return path_.AppendASCII(tmp); |
| 729 } | 731 } |
| 730 | 732 |
| 731 } // namespace disk_cache | 733 } // namespace disk_cache |
| OLD | NEW |