| OLD | NEW |
| 1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved. | 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 | 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/block_files.h" | 5 #include "net/disk_cache/block_files.h" |
| 6 | 6 |
| 7 #include "base/file_util.h" | 7 #include "base/file_util.h" |
| 8 #include "base/histogram.h" | 8 #include "base/histogram.h" |
| 9 #include "base/string_util.h" | 9 #include "base/string_util.h" |
| 10 #include "base/time.h" | 10 #include "base/time.h" |
| 11 #include "net/disk_cache/cache_util.h" | 11 #include "net/disk_cache/cache_util.h" |
| 12 #include "net/disk_cache/file_lock.h" | 12 #include "net/disk_cache/file_lock.h" |
| 13 | 13 |
| 14 using base::Time; | 14 using base::Time; |
| 15 using base::TimeTicks; |
| 15 | 16 |
| 16 namespace { | 17 namespace { |
| 17 | 18 |
| 18 const char* kBlockName = "data_"; | 19 const char* kBlockName = "data_"; |
| 19 | 20 |
| 20 // This array is used to perform a fast lookup of the nibble bit pattern to the | 21 // 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 // 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 const char s_types[16] = {4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}; |
| 23 | 24 |
| 24 // Returns the type of block (number of consecutive blocks that can be stored) | 25 // Returns the type of block (number of consecutive blocks that can be stored) |
| 25 // for a given nibble of the bitmap. | 26 // for a given nibble of the bitmap. |
| 26 inline int GetMapBlockType(uint8 value) { | 27 inline int GetMapBlockType(uint8 value) { |
| 27 value &= 0xf; | 28 value &= 0xf; |
| 28 return s_types[value]; | 29 return s_types[value]; |
| 29 } | 30 } |
| 30 | 31 |
| 31 void FixAllocationCounters(disk_cache::BlockFileHeader* header); | 32 void FixAllocationCounters(disk_cache::BlockFileHeader* header); |
| 32 | 33 |
| 33 // Creates a new entry on the allocation map, updating the apropriate counters. | 34 // 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 // target is the type of block to use (number of empty blocks), and size is the |
| 35 // actual number of blocks to use. | 36 // actual number of blocks to use. |
| 36 bool CreateMapBlock(int target, int size, disk_cache::BlockFileHeader* header, | 37 bool CreateMapBlock(int target, int size, disk_cache::BlockFileHeader* header, |
| 37 int* index) { | 38 int* index) { |
| 38 if (target <= 0 || target > disk_cache::kMaxNumBlocks || | 39 if (target <= 0 || target > disk_cache::kMaxNumBlocks || |
| 39 size <= 0 || size > disk_cache::kMaxNumBlocks) { | 40 size <= 0 || size > disk_cache::kMaxNumBlocks) { |
| 40 NOTREACHED(); | 41 NOTREACHED(); |
| 41 return false; | 42 return false; |
| 42 } | 43 } |
| 43 | 44 |
| 44 Time start = Time::Now(); | 45 TimeTicks start = TimeTicks::Now(); |
| 45 // We are going to process the map on 32-block chunks (32 bits), and on every | 46 // 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 // chunk, iterate through the 8 nibbles where the new block can be located. |
| 47 int current = header->hints[target - 1]; | 48 int current = header->hints[target - 1]; |
| 48 for (int i = 0; i < header->max_entries / 32; i++, current++) { | 49 for (int i = 0; i < header->max_entries / 32; i++, current++) { |
| 49 if (current == header->max_entries / 32) | 50 if (current == header->max_entries / 32) |
| 50 current = 0; | 51 current = 0; |
| 51 uint32 map_block = header->allocation_map[current]; | 52 uint32 map_block = header->allocation_map[current]; |
| 52 | 53 |
| 53 for (int j = 0; j < 8; j++, map_block >>= 4) { | 54 for (int j = 0; j < 8; j++, map_block >>= 4) { |
| 54 if (GetMapBlockType(map_block) != target) | 55 if (GetMapBlockType(map_block) != target) |
| 55 continue; | 56 continue; |
| 56 | 57 |
| 57 disk_cache::FileLock lock(header); | 58 disk_cache::FileLock lock(header); |
| 58 int index_offset = j * 4 + 4 - target; | 59 int index_offset = j * 4 + 4 - target; |
| 59 *index = current * 32 + index_offset; | 60 *index = current * 32 + index_offset; |
| 60 uint32 to_add = ((1 << size) - 1) << index_offset; | 61 uint32 to_add = ((1 << size) - 1) << index_offset; |
| 61 header->allocation_map[current] |= to_add; | 62 header->allocation_map[current] |= to_add; |
| 62 | 63 |
| 63 header->hints[target - 1] = current; | 64 header->hints[target - 1] = current; |
| 64 header->empty[target - 1]--; | 65 header->empty[target - 1]--; |
| 65 DCHECK(header->empty[target - 1] >= 0); | 66 DCHECK(header->empty[target - 1] >= 0); |
| 66 header->num_entries++; | 67 header->num_entries++; |
| 67 if (target != size) { | 68 if (target != size) { |
| 68 header->empty[target - size - 1]++; | 69 header->empty[target - size - 1]++; |
| 69 } | 70 } |
| 70 HISTOGRAM_TIMES("DiskCache.CreateBlock", Time::Now() - start); | 71 HISTOGRAM_TIMES("DiskCache.CreateBlock", TimeTicks::Now() - start); |
| 71 return true; | 72 return true; |
| 72 } | 73 } |
| 73 } | 74 } |
| 74 | 75 |
| 75 // It is possible to have an undetected corruption (for example when the OS | 76 // It is possible to have an undetected corruption (for example when the OS |
| 76 // crashes), fix it here. | 77 // crashes), fix it here. |
| 77 LOG(ERROR) << "Failing CreateMapBlock"; | 78 LOG(ERROR) << "Failing CreateMapBlock"; |
| 78 FixAllocationCounters(header); | 79 FixAllocationCounters(header); |
| 79 return false; | 80 return false; |
| 80 } | 81 } |
| 81 | 82 |
| 82 // Deletes the block pointed by index from allocation_map, and updates the | 83 // Deletes the block pointed by index from allocation_map, and updates the |
| 83 // relevant counters on the header. | 84 // relevant counters on the header. |
| 84 void DeleteMapBlock(int index, int size, disk_cache::BlockFileHeader* header) { | 85 void DeleteMapBlock(int index, int size, disk_cache::BlockFileHeader* header) { |
| 85 if (size < 0 || size > disk_cache::kMaxNumBlocks) { | 86 if (size < 0 || size > disk_cache::kMaxNumBlocks) { |
| 86 NOTREACHED(); | 87 NOTREACHED(); |
| 87 return; | 88 return; |
| 88 } | 89 } |
| 89 Time start = Time::Now(); | 90 TimeTicks start = TimeTicks::Now(); |
| 90 int byte_index = index / 8; | 91 int byte_index = index / 8; |
| 91 uint8* byte_map = reinterpret_cast<uint8*>(header->allocation_map); | 92 uint8* byte_map = reinterpret_cast<uint8*>(header->allocation_map); |
| 92 uint8 map_block = byte_map[byte_index]; | 93 uint8 map_block = byte_map[byte_index]; |
| 93 | 94 |
| 94 if (index % 8 >= 4) | 95 if (index % 8 >= 4) |
| 95 map_block >>= 4; | 96 map_block >>= 4; |
| 96 | 97 |
| 97 // See what type of block will be availabe after we delete this one. | 98 // See what type of block will be availabe after we delete this one. |
| 98 int bits_at_end = 4 - size - index % 4; | 99 int bits_at_end = 4 - size - index % 4; |
| 99 uint8 end_mask = (0xf << (4 - bits_at_end)) & 0xf; | 100 uint8 end_mask = (0xf << (4 - bits_at_end)) & 0xf; |
| 100 bool update_counters = (map_block & end_mask) == 0; | 101 bool update_counters = (map_block & end_mask) == 0; |
| 101 uint8 new_value = map_block & ~(((1 << size) - 1) << (index % 4)); | 102 uint8 new_value = map_block & ~(((1 << size) - 1) << (index % 4)); |
| 102 int new_type = GetMapBlockType(new_value); | 103 int new_type = GetMapBlockType(new_value); |
| 103 | 104 |
| 104 disk_cache::FileLock lock(header); | 105 disk_cache::FileLock lock(header); |
| 105 DCHECK((((1 << size) - 1) << (index % 8)) < 0x100); | 106 DCHECK((((1 << size) - 1) << (index % 8)) < 0x100); |
| 106 uint8 to_clear = ((1 << size) - 1) << (index % 8); | 107 uint8 to_clear = ((1 << size) - 1) << (index % 8); |
| 107 DCHECK((byte_map[byte_index] & to_clear) == to_clear); | 108 DCHECK((byte_map[byte_index] & to_clear) == to_clear); |
| 108 byte_map[byte_index] &= ~to_clear; | 109 byte_map[byte_index] &= ~to_clear; |
| 109 | 110 |
| 110 if (update_counters) { | 111 if (update_counters) { |
| 111 if (bits_at_end) | 112 if (bits_at_end) |
| 112 header->empty[bits_at_end - 1]--; | 113 header->empty[bits_at_end - 1]--; |
| 113 header->empty[new_type - 1]++; | 114 header->empty[new_type - 1]++; |
| 114 DCHECK(header->empty[bits_at_end - 1] >= 0); | 115 DCHECK(header->empty[bits_at_end - 1] >= 0); |
| 115 } | 116 } |
| 116 header->num_entries--; | 117 header->num_entries--; |
| 117 DCHECK(header->num_entries >= 0); | 118 DCHECK(header->num_entries >= 0); |
| 118 HISTOGRAM_TIMES("DiskCache.DeleteBlock", Time::Now() - start); | 119 HISTOGRAM_TIMES("DiskCache.DeleteBlock", TimeTicks::Now() - start); |
| 119 } | 120 } |
| 120 | 121 |
| 121 // Restores the "empty counters" and allocation hints. | 122 // Restores the "empty counters" and allocation hints. |
| 122 void FixAllocationCounters(disk_cache::BlockFileHeader* header) { | 123 void FixAllocationCounters(disk_cache::BlockFileHeader* header) { |
| 123 for (int i = 0; i < disk_cache::kMaxNumBlocks; i++) { | 124 for (int i = 0; i < disk_cache::kMaxNumBlocks; i++) { |
| 124 header->hints[i] = 0; | 125 header->hints[i] = 0; |
| 125 header->empty[i] = 0; | 126 header->empty[i] = 0; |
| 126 } | 127 } |
| 127 | 128 |
| 128 for (int i = 0; i < header->max_entries / 32; i++) { | 129 for (int i = 0; i < header->max_entries / 32; i++) { |
| (...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 307 header->max_entries = new_size; | 308 header->max_entries = new_size; |
| 308 | 309 |
| 309 return true; | 310 return true; |
| 310 } | 311 } |
| 311 | 312 |
| 312 MappedFile* BlockFiles::FileForNewBlock(FileType block_type, int block_count) { | 313 MappedFile* BlockFiles::FileForNewBlock(FileType block_type, int block_count) { |
| 313 COMPILE_ASSERT(RANKINGS == 1, invalid_fily_type); | 314 COMPILE_ASSERT(RANKINGS == 1, invalid_fily_type); |
| 314 MappedFile* file = block_files_[block_type - 1]; | 315 MappedFile* file = block_files_[block_type - 1]; |
| 315 BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer()); | 316 BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer()); |
| 316 | 317 |
| 317 Time start = Time::Now(); | 318 TimeTicks start = TimeTicks::Now(); |
| 318 while (NeedToGrowBlockFile(header, block_count)) { | 319 while (NeedToGrowBlockFile(header, block_count)) { |
| 319 if (kMaxBlocks == header->max_entries) { | 320 if (kMaxBlocks == header->max_entries) { |
| 320 file = NextFile(file); | 321 file = NextFile(file); |
| 321 if (!file) | 322 if (!file) |
| 322 return NULL; | 323 return NULL; |
| 323 header = reinterpret_cast<BlockFileHeader*>(file->buffer()); | 324 header = reinterpret_cast<BlockFileHeader*>(file->buffer()); |
| 324 continue; | 325 continue; |
| 325 } | 326 } |
| 326 | 327 |
| 327 if (!GrowBlockFile(file, header)) | 328 if (!GrowBlockFile(file, header)) |
| 328 return NULL; | 329 return NULL; |
| 329 break; | 330 break; |
| 330 } | 331 } |
| 331 HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", Time::Now() - start); | 332 HISTOGRAM_TIMES("DiskCache.GetFileForNewBlock", TimeTicks::Now() - start); |
| 332 return file; | 333 return file; |
| 333 } | 334 } |
| 334 | 335 |
| 335 MappedFile* BlockFiles::NextFile(const MappedFile* file) { | 336 MappedFile* BlockFiles::NextFile(const MappedFile* file) { |
| 336 BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer()); | 337 BlockFileHeader* header = reinterpret_cast<BlockFileHeader*>(file->buffer()); |
| 337 int new_file = header->next_file; | 338 int new_file = header->next_file; |
| 338 if (!new_file) { | 339 if (!new_file) { |
| 339 // RANKINGS is not reported as a type for small entries, but we may be | 340 // RANKINGS is not reported as a type for small entries, but we may be |
| 340 // extending the rankings block file. | 341 // extending the rankings block file. |
| 341 FileType type = Addr::RequiredFileType(header->entry_size); | 342 FileType type = Addr::RequiredFileType(header->entry_size); |
| (...skipping 137 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 479 int num_entries = (file_size - sizeof(*header)) / header->entry_size; | 480 int num_entries = (file_size - sizeof(*header)) / header->entry_size; |
| 480 header->max_entries = num_entries; | 481 header->max_entries = num_entries; |
| 481 } | 482 } |
| 482 | 483 |
| 483 FixAllocationCounters(header); | 484 FixAllocationCounters(header); |
| 484 header->updating = 0; | 485 header->updating = 0; |
| 485 return true; | 486 return true; |
| 486 } | 487 } |
| 487 | 488 |
| 488 } // namespace disk_cache | 489 } // namespace disk_cache |
| OLD | NEW |