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 19 matching lines...) Expand all Loading... |
30 // number at the end of the file name is the block file number (in decimal). | 30 // number at the end of the file name is the block file number (in decimal). |
31 // | 31 // |
32 // There are three "special" types of blocks: normal entries, evicted entries | 32 // There are three "special" types of blocks: normal entries, evicted entries |
33 // and control data for external files. | 33 // and control data for external files. |
34 // | 34 // |
35 // The files that store internal information for the cache (blocks and index) | 35 // The files that store internal information for the cache (blocks and index) |
36 // are memory mapped. They have a location that is signaled every time the | 36 // are memory mapped. They have a location that is signaled every time the |
37 // internal structures are modified, so it is possible to detect (most of the | 37 // internal structures are modified, so it is possible to detect (most of the |
38 // time) when the process dies in the middle of an update. There are dedicated | 38 // time) when the process dies in the middle of an update. There are dedicated |
39 // backup files for cache bitmaps, used to detect entries out of date. | 39 // backup files for cache bitmaps, used to detect entries out of date. |
| 40 // |
| 41 // Although cache files are to be consumed on the same machine that creates |
| 42 // them, if files are to be moved accross machines, little endian storage is |
| 43 // assumed. |
40 | 44 |
41 #ifndef NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ | 45 #ifndef NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ |
42 #define NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ | 46 #define NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ |
43 | 47 |
44 #include "base/basictypes.h" | 48 #include "base/basictypes.h" |
45 #include "net/disk_cache/disk_format_base.h" | 49 #include "net/disk_cache/disk_format_base.h" |
46 | 50 |
47 namespace disk_cache { | 51 namespace disk_cache { |
48 | 52 |
49 const int kBaseTableLen = 0x10000; | 53 const int kBaseTableLen = 0x400; |
50 const uint32 kIndexMagicV3 = 0xC103CAC3; | 54 const uint32 kIndexMagicV3 = 0xC103CAC3; |
51 const uint32 kVersion3 = 0x30000; // Version 3.0. | 55 const uint32 kVersion3 = 0x30000; // Version 3.0. |
52 | 56 |
53 // Flags for a given cache. | 57 // Flags for a given cache. |
54 enum CacheFlags { | 58 enum CacheFlags { |
55 CACHE_EVICTION_2 = 1, // Keep multiple lists for eviction. | 59 SMALL_CACHE = 1 << 0, // See IndexCell. |
56 CACHE_EVICTED = 1 << 1 // Already evicted at least one entry. | 60 CACHE_EVICTION_2 = 1 << 1, // Keep multiple lists for eviction. |
| 61 CACHE_EVICTED = 1 << 2 // Already evicted at least one entry. |
57 }; | 62 }; |
58 | 63 |
59 // Header for the master index file. | 64 // Header for the master index file. |
60 struct IndexHeaderV3 { | 65 struct IndexHeaderV3 { |
61 uint32 magic; | 66 uint32 magic; |
62 uint32 version; | 67 uint32 version; |
63 int32 num_entries; // Number of entries currently stored. | 68 int32 num_entries; // Number of entries currently stored. |
64 int32 num_bytes; // Total size of the stored data. | 69 int32 num_bytes; // Total size of the stored data. |
65 int32 last_file; // Last external file created. | 70 int32 last_file; // Last external file created. |
66 int32 reserved1; | 71 int32 reserved1; |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
112 ENTRY_HIGH_USE, // The entry has high reuse. | 117 ENTRY_HIGH_USE, // The entry has high reuse. |
113 ENTRY_RESERVED, // Reserved for future use. | 118 ENTRY_RESERVED, // Reserved for future use. |
114 ENTRY_EVICTED // The entry was deleted. | 119 ENTRY_EVICTED // The entry was deleted. |
115 }; | 120 }; |
116 COMPILE_ASSERT(ENTRY_USED <= 7, group_uses_3_bits); | 121 COMPILE_ASSERT(ENTRY_USED <= 7, group_uses_3_bits); |
117 | 122 |
118 #pragma pack(push, 1) | 123 #pragma pack(push, 1) |
119 struct IndexCell { | 124 struct IndexCell { |
120 void Clear() { memset(this, 0, sizeof(*this)); } | 125 void Clear() { memset(this, 0, sizeof(*this)); } |
121 | 126 |
122 uint64 address : 22; | 127 // A cell is a 9 byte bit-field that stores 7 values: |
123 uint64 hash : 18; | 128 // address : 22 bits |
124 uint64 timestamp : 20; | 129 // hash : 18 bits |
125 uint64 reuse : 4; | 130 // timestamp : 20 bits |
126 uint8 state : 3; | 131 // reuse : 4 bits |
127 uint8 group : 3; | 132 // state : 3 bits |
128 uint8 sum : 2; | 133 // group : 3 bits |
| 134 // sum : 2 bits |
| 135 // The actual layout is as follows: |
| 136 // |
| 137 // first_part (low order 32 bits): |
| 138 // 0000 0000 0011 1111 1111 1111 1111 1111 : address |
| 139 // 1111 1111 1100 0000 0000 0000 0000 0000 : hash |
| 140 // |
| 141 // first_part (high order 32 bits): |
| 142 // 0000 0000 0000 0000 0000 0000 1111 1111 : hash |
| 143 // 0000 1111 1111 1111 1111 1111 0000 0000 : timestamp |
| 144 // 1111 0000 0000 0000 0000 0000 0000 0000 : reuse |
| 145 // |
| 146 // last_part: |
| 147 // 0000 0111 : state |
| 148 // 0011 1000 : group |
| 149 // 1100 0000 : sum |
| 150 // |
| 151 // The small-cache version of the format moves some bits from the address to |
| 152 // the hash fileds, like so: |
| 153 // address : 16 bits |
| 154 // hash : 24 bits |
| 155 // |
| 156 // first_part (low order 32 bits): |
| 157 // 0000 0000 0000 0000 1111 1111 1111 1111 : address |
| 158 // 1111 1111 1111 1111 0000 0000 0000 0000 : hash |
| 159 // |
| 160 // The actual bit distribution between address and hash is determined by the |
| 161 // table size (IndexHeaderV3.table_len). Tables smaller than 65536 entries |
| 162 // use the small-cache version; after that size, caches should have the |
| 163 // SMALL_CACHE flag cleared. |
| 164 // |
| 165 // To locate a given entry after recovering the address from the cell, the |
| 166 // file type and file number are appended (see disk_cache/addr.h). For a large |
| 167 // table only the file type is implied; for a small table, the file number |
| 168 // is also implied, and it should be the first file for that type of entry, |
| 169 // as determined by the EntryGroup (two files in total, one for active entries |
| 170 // and another one for evicted entries). |
| 171 |
| 172 uint64 first_part; |
| 173 uint8 last_part; |
129 }; | 174 }; |
130 COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell); | 175 COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell); |
131 | 176 |
| 177 const int kCellsPerBucket = 4; |
132 struct IndexBucket { | 178 struct IndexBucket { |
133 IndexCell cells[4]; | 179 IndexCell cells[kCellsPerBucket]; |
134 int32 next; | 180 int32 next; |
135 uint32 hash : 24; // The last byte is only defined for buckets of | 181 uint32 hash; // The high order byte is reserved (should be zero). |
136 uint32 reserved : 8; // the extra table. | |
137 }; | 182 }; |
138 COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket); | 183 COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket); |
139 const int kBytesPerCell = 44 / 4; | 184 const int kBytesPerCell = 44 / kCellsPerBucket; |
140 | 185 |
141 // The main cache index. Backed by a file named index_tb1. | 186 // The main cache index. Backed by a file named index_tb1. |
142 // The extra table (index_tb2) has a similar format, but different size. | 187 // The extra table (index_tb2) has a similar format, but different size. |
143 struct Index { | 188 struct Index { |
144 // Default size. Actual size controlled by header.table_len. | 189 // Default size. Actual size controlled by header.table_len. |
145 IndexBucket table[kBaseTableLen / 4]; | 190 IndexBucket table[kBaseTableLen / kCellsPerBucket]; |
146 }; | 191 }; |
147 #pragma pack(pop) | 192 #pragma pack(pop) |
148 | 193 |
149 // Flags that can be applied to an entry. | 194 // Flags that can be applied to an entry. |
150 enum EntryFlags { | 195 enum EntryFlags { |
151 PARENT_ENTRY = 1, // This entry has children (sparse) entries. | 196 PARENT_ENTRY = 1, // This entry has children (sparse) entries. |
152 CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. | 197 CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. |
153 }; | 198 }; |
154 | 199 |
155 struct EntryRecord { | 200 struct EntryRecord { |
(...skipping 25 matching lines...) Expand all Loading... |
181 int32 key_len; | 226 int32 key_len; |
182 uint64 last_access_time; | 227 uint64 last_access_time; |
183 uint32 long_hash[5]; | 228 uint32 long_hash[5]; |
184 uint32 self_hash; | 229 uint32 self_hash; |
185 }; | 230 }; |
186 COMPILE_ASSERT(sizeof(ShortEntryRecord) == 48, bad_ShortEntryRecord); | 231 COMPILE_ASSERT(sizeof(ShortEntryRecord) == 48, bad_ShortEntryRecord); |
187 | 232 |
188 } // namespace disk_cache | 233 } // namespace disk_cache |
189 | 234 |
190 #endif // NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ | 235 #endif // NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ |
OLD | NEW |