OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 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 // The cache is stored on disk as a collection of block-files, plus an index | 5 // The cache is stored on disk as a collection of block-files, plus an index |
6 // plus a collection of external files. | 6 // plus a collection of external files. |
7 // | 7 // |
8 // Any data blob bigger than kMaxBlockSize (disk_cache/addr.h) will be stored in | 8 // Any data blob bigger than kMaxBlockSize (disk_cache/addr.h) will be stored in |
9 // a separate file named f_xxx where x is a hexadecimal number. Shorter data | 9 // a separate file named f_xxx where x is a hexadecimal number. Shorter data |
10 // will be stored as a series of blocks on a block-file. In any case, CacheAddr | 10 // will be stored as a series of blocks on a block-file. In any case, CacheAddr |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
56 | 56 |
57 // Flags for a given cache. | 57 // Flags for a given cache. |
58 enum CacheFlags { | 58 enum CacheFlags { |
59 SMALL_CACHE = 1 << 0, // See IndexCell. | 59 SMALL_CACHE = 1 << 0, // See IndexCell. |
60 CACHE_EVICTION_2 = 1 << 1, // Keep multiple lists for eviction. | 60 CACHE_EVICTION_2 = 1 << 1, // Keep multiple lists for eviction. |
61 CACHE_EVICTED = 1 << 2 // Already evicted at least one entry. | 61 CACHE_EVICTED = 1 << 2 // Already evicted at least one entry. |
62 }; | 62 }; |
63 | 63 |
64 // Header for the master index file. | 64 // Header for the master index file. |
65 struct IndexHeaderV3 { | 65 struct IndexHeaderV3 { |
66 uint32 magic; | 66 uint32 magic; |
67 uint32 version; | 67 uint32 version; |
68 int32 num_entries; // Number of entries currently stored. | 68 int32 num_entries; // Number of entries currently stored. |
69 int32 num_bytes; // Total size of the stored data. | 69 int32 num_bytes; // Total size of the stored data. |
70 int32 last_file; // Last external file created. | 70 int32 last_file; // Last external file created. |
71 int32 reserved1; | 71 int32 reserved1; |
72 CacheAddr stats; // Storage for usage data. | 72 CacheAddr stats; // Storage for usage data. |
73 int32 table_len; // Actual size of the table. | 73 int32 table_len; // Actual size of the table. |
74 int32 crash; // Signals a previous crash. | 74 int32 crash; // Signals a previous crash. |
75 int32 experiment; // Id of an ongoing test. | 75 int32 experiment; // Id of an ongoing test. |
76 int32 max_bytes; // Total maximum size of the stored data. | 76 int32 max_bytes; // Total maximum size of the stored data. |
77 uint32 flags; | 77 uint32 flags; |
78 int32 used_cells; | 78 int32 used_cells; |
79 int32 max_bucket; | 79 int32 max_bucket; |
80 uint64 create_time; // Creation time for this set of files. | 80 uint64 create_time; // Creation time for this set of files. |
81 uint64 base_time; // Current base for timestamps. | 81 uint64 base_time; // Current base for timestamps. |
82 uint64 old_time; // Previous time used for timestamps. | 82 uint64 old_time; // Previous time used for timestamps. |
83 int32 max_block_file; | 83 int32 max_block_file; |
84 int32 num_no_use_entries; | 84 int32 num_no_use_entries; |
85 int32 num_low_use_entries; | 85 int32 num_low_use_entries; |
86 int32 num_high_use_entries; | 86 int32 num_high_use_entries; |
87 int32 reserved; | 87 int32 reserved; |
88 int32 num_evicted_entries; | 88 int32 num_evicted_entries; |
89 int32 pad[6]; | 89 int32 pad[6]; |
90 }; | 90 }; |
91 | 91 |
92 const int kBaseBitmapBytes = 3968; | 92 const int kBaseBitmapBytes = 3968; |
93 // The IndexBitmap is directly saved to a file named index. The file grows in | 93 // The IndexBitmap is directly saved to a file named index. The file grows in |
94 // page increments (4096 bytes), but all bits don't have to be in use at any | 94 // page increments (4096 bytes), but all bits don't have to be in use at any |
95 // given time. The required file size can be computed from header.table_len. | 95 // given time. The required file size can be computed from header.table_len. |
96 struct IndexBitmap { | 96 struct IndexBitmap { |
97 IndexHeaderV3 header; | 97 IndexHeaderV3 header; |
98 uint32 bitmap[kBaseBitmapBytes / 4]; // First page of the bitmap. | 98 uint32 bitmap[kBaseBitmapBytes / 4]; // First page of the bitmap. |
99 }; | 99 }; |
100 COMPILE_ASSERT(sizeof(IndexBitmap) == 4096, bad_IndexHeader); | 100 COMPILE_ASSERT(sizeof(IndexBitmap) == 4096, bad_IndexHeader); |
101 | 101 |
102 // Possible states for a given entry. | 102 // Possible states for a given entry. |
103 enum EntryState { | 103 enum EntryState { |
104 ENTRY_FREE = 0, // Available slot. | 104 ENTRY_FREE = 0, // Available slot. |
105 ENTRY_NEW, // The entry is being created. | 105 ENTRY_NEW, // The entry is being created. |
106 ENTRY_OPEN, // The entry is being accessed. | 106 ENTRY_OPEN, // The entry is being accessed. |
107 ENTRY_MODIFIED, // The entry is being modified. | 107 ENTRY_MODIFIED, // The entry is being modified. |
108 ENTRY_DELETED, // The entry is being deleted. | 108 ENTRY_DELETED, // The entry is being deleted. |
109 ENTRY_FIXING, // Inconsistent state. The entry is being verified. | 109 ENTRY_FIXING, // Inconsistent state. The entry is being verified. |
110 ENTRY_USED // The slot is in use (entry is present). | 110 ENTRY_USED // The slot is in use (entry is present). |
111 }; | 111 }; |
112 COMPILE_ASSERT(ENTRY_USED <= 7, state_uses_3_bits); | 112 COMPILE_ASSERT(ENTRY_USED <= 7, state_uses_3_bits); |
113 | 113 |
114 enum EntryGroup { | 114 enum EntryGroup { |
115 ENTRY_NO_USE = 0, // The entry has not been reused. | 115 ENTRY_NO_USE = 0, // The entry has not been reused. |
116 ENTRY_LOW_USE, // The entry has low reuse. | 116 ENTRY_LOW_USE, // The entry has low reuse. |
117 ENTRY_HIGH_USE, // The entry has high reuse. | 117 ENTRY_HIGH_USE, // The entry has high reuse. |
118 ENTRY_RESERVED, // Reserved for future use. | 118 ENTRY_RESERVED, // Reserved for future use. |
119 ENTRY_EVICTED // The entry was deleted. | 119 ENTRY_EVICTED // The entry was deleted. |
120 }; | 120 }; |
121 COMPILE_ASSERT(ENTRY_USED <= 7, group_uses_3_bits); | 121 COMPILE_ASSERT(ENTRY_USED <= 7, group_uses_3_bits); |
122 | 122 |
123 #pragma pack(push, 1) | 123 #pragma pack(push, 1) |
124 struct IndexCell { | 124 struct IndexCell { |
125 void Clear() { memset(this, 0, sizeof(*this)); } | 125 void Clear() { memset(this, 0, sizeof(*this)); } |
126 | 126 |
127 // A cell is a 9 byte bit-field that stores 7 values: | 127 // A cell is a 9 byte bit-field that stores 7 values: |
128 // location : 22 bits | 128 // location : 22 bits |
129 // id : 18 bits | 129 // id : 18 bits |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
173 // | 173 // |
174 // For example, a small table may store something like 0x1234 as the location | 174 // For example, a small table may store something like 0x1234 as the location |
175 // field. That means it stores the entry number 0x1234. If that record belongs | 175 // field. That means it stores the entry number 0x1234. If that record belongs |
176 // to a deleted entry, the regular cache address may look something like | 176 // to a deleted entry, the regular cache address may look something like |
177 // BLOCK_EVICTED + 1 block + file number 6 + entry number 0x1234 | 177 // BLOCK_EVICTED + 1 block + file number 6 + entry number 0x1234 |
178 // so Addr = 0xf0061234 | 178 // so Addr = 0xf0061234 |
179 // | 179 // |
180 // If that same Addr is stored on a large table, the location field would be | 180 // If that same Addr is stored on a large table, the location field would be |
181 // 0x61234 | 181 // 0x61234 |
182 | 182 |
183 uint64 first_part; | 183 uint64 first_part; |
184 uint8 last_part; | 184 uint8 last_part; |
185 }; | 185 }; |
186 COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell); | 186 COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell); |
187 | 187 |
188 const int kCellsPerBucket = 4; | 188 const int kCellsPerBucket = 4; |
189 struct IndexBucket { | 189 struct IndexBucket { |
190 IndexCell cells[kCellsPerBucket]; | 190 IndexCell cells[kCellsPerBucket]; |
191 int32 next; | 191 int32 next; |
192 uint32 hash; // The high order byte is reserved (should be zero). | 192 uint32 hash; // The high order byte is reserved (should be zero). |
193 }; | 193 }; |
194 COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket); | 194 COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket); |
195 const int kBytesPerCell = 44 / kCellsPerBucket; | 195 const int kBytesPerCell = 44 / kCellsPerBucket; |
196 | 196 |
197 // The main cache index. Backed by a file named index_tb1. | 197 // The main cache index. Backed by a file named index_tb1. |
198 // The extra table (index_tb2) has a similar format, but different size. | 198 // The extra table (index_tb2) has a similar format, but different size. |
199 struct Index { | 199 struct Index { |
200 // Default size. Actual size controlled by header.table_len. | 200 // Default size. Actual size controlled by header.table_len. |
201 IndexBucket table[kBaseTableLen / kCellsPerBucket]; | 201 IndexBucket table[kBaseTableLen / kCellsPerBucket]; |
202 }; | 202 }; |
203 #pragma pack(pop) | 203 #pragma pack(pop) |
204 | 204 |
205 // Flags that can be applied to an entry. | 205 // Flags that can be applied to an entry. |
206 enum EntryFlags { | 206 enum EntryFlags { |
207 PARENT_ENTRY = 1, // This entry has children (sparse) entries. | 207 PARENT_ENTRY = 1, // This entry has children (sparse) entries. |
208 CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. | 208 CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. |
209 }; | 209 }; |
210 | 210 |
211 struct EntryRecord { | 211 struct EntryRecord { |
212 uint32 hash; | 212 uint32 hash; |
213 uint32 pad1; | 213 uint32 pad1; |
214 uint8 reuse_count; | 214 uint8 reuse_count; |
215 uint8 refetch_count; | 215 uint8 refetch_count; |
216 int8 state; // Current EntryState. | 216 int8 state; // Current EntryState. |
217 uint8 flags; // Any combination of EntryFlags. | 217 uint8 flags; // Any combination of EntryFlags. |
218 int32 key_len; | 218 int32 key_len; |
219 int32 data_size[4]; // We can store up to 4 data streams for each | 219 int32 data_size[4]; // We can store up to 4 data streams for each |
220 CacheAddr data_addr[4]; // entry. | 220 CacheAddr data_addr[4]; // entry. |
221 uint32 data_hash[4]; | 221 uint32 data_hash[4]; |
222 uint64 creation_time; | 222 uint64 creation_time; |
223 uint64 last_modified_time; | 223 uint64 last_modified_time; |
224 uint64 last_access_time; | 224 uint64 last_access_time; |
225 int32 pad[3]; | 225 int32 pad[3]; |
226 uint32 self_hash; | 226 uint32 self_hash; |
227 }; | 227 }; |
228 COMPILE_ASSERT(sizeof(EntryRecord) == 104, bad_EntryRecord); | 228 COMPILE_ASSERT(sizeof(EntryRecord) == 104, bad_EntryRecord); |
229 | 229 |
230 struct ShortEntryRecord { | 230 struct ShortEntryRecord { |
231 uint32 hash; | 231 uint32 hash; |
232 uint32 pad1; | 232 uint32 pad1; |
233 uint8 reuse_count; | 233 uint8 reuse_count; |
234 uint8 refetch_count; | 234 uint8 refetch_count; |
235 int8 state; // Current EntryState. | 235 int8 state; // Current EntryState. |
236 uint8 flags; | 236 uint8 flags; |
237 int32 key_len; | 237 int32 key_len; |
238 uint64 last_access_time; | 238 uint64 last_access_time; |
239 uint32 long_hash[5]; | 239 uint32 long_hash[5]; |
240 uint32 self_hash; | 240 uint32 self_hash; |
241 }; | 241 }; |
242 COMPILE_ASSERT(sizeof(ShortEntryRecord) == 48, bad_ShortEntryRecord); | 242 COMPILE_ASSERT(sizeof(ShortEntryRecord) == 48, bad_ShortEntryRecord); |
243 | 243 |
244 } // namespace disk_cache | 244 } // namespace disk_cache |
245 | 245 |
246 #endif // NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_ | 246 #endif // NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_ |
OLD | NEW |