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 |