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