OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 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 #ifndef NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ | 5 #ifndef NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ |
6 #define NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ | 6 #define NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ |
7 | 7 |
8 // The IndexTable class is in charge of handling all the details about the main | 8 // The IndexTable class is in charge of handling all the details about the main |
9 // index table of the cache. It provides methods to locate entries in the cache, | 9 // index table of the cache. It provides methods to locate entries in the cache, |
10 // create new entries and modify existing entries. It hides the fact that the | 10 // create new entries and modify existing entries. It hides the fact that the |
11 // table is backed up across multiple physical files, and that the files can | 11 // table is backed up across multiple physical files, and that the files can |
12 // grow and be remapped while the cache is in use. However, note that this class | 12 // grow and be remapped while the cache is in use. However, note that this class |
13 // doesn't do any direct management of the backing files, and it operates only | 13 // doesn't do any direct management of the backing files, and it operates only |
14 // with the tables in memory. | 14 // with the tables in memory. |
15 // | 15 // |
16 // When the current index needs to grow, the backend is notified so that files | 16 // When the current index needs to grow, the backend is notified so that files |
17 // are extended and remapped as needed. After that, the IndexTable should be | 17 // are extended and remapped as needed. After that, the IndexTable should be |
18 // re-initialized with the new structures. Note that the IndexTable instance is | 18 // re-initialized with the new structures. Note that the IndexTable instance is |
19 // still functional while the backend performs file IO. | 19 // still functional while the backend performs file IO. |
20 | 20 |
| 21 #include <stdint.h> |
| 22 |
21 #include <vector> | 23 #include <vector> |
22 | 24 |
23 #include "base/basictypes.h" | 25 #include "base/macros.h" |
24 #include "base/memory/ref_counted.h" | 26 #include "base/memory/ref_counted.h" |
25 #include "base/memory/scoped_ptr.h" | 27 #include "base/memory/scoped_ptr.h" |
26 #include "base/time/time.h" | 28 #include "base/time/time.h" |
27 #include "net/base/net_export.h" | 29 #include "net/base/net_export.h" |
28 #include "net/disk_cache/blockfile/addr.h" | 30 #include "net/disk_cache/blockfile/addr.h" |
29 #include "net/disk_cache/blockfile/bitmap.h" | 31 #include "net/disk_cache/blockfile/bitmap.h" |
30 #include "net/disk_cache/blockfile/disk_format_v3.h" | 32 #include "net/disk_cache/blockfile/disk_format_v3.h" |
31 | 33 |
32 namespace net { | 34 namespace net { |
33 class IOBuffer; | 35 class IOBuffer; |
(...skipping 13 matching lines...) Expand all Loading... |
47 // However, note that it is also possible for an entity to be moved from one | 49 // However, note that it is also possible for an entity to be moved from one |
48 // position to another, so an EntryCell may be invalid by the time a long | 50 // position to another, so an EntryCell may be invalid by the time a long |
49 // operation completes. In that case, the caller should consult the table again | 51 // operation completes. In that case, the caller should consult the table again |
50 // using FindEntryCell(). | 52 // using FindEntryCell(). |
51 class NET_EXPORT_PRIVATE EntryCell { | 53 class NET_EXPORT_PRIVATE EntryCell { |
52 public: | 54 public: |
53 ~EntryCell(); | 55 ~EntryCell(); |
54 | 56 |
55 bool IsValid() const; | 57 bool IsValid() const; |
56 | 58 |
57 int32 cell_num() const { return cell_num_; } | 59 int32_t cell_num() const { return cell_num_; } |
58 uint32 hash() const { return hash_; } | 60 uint32_t hash() const { return hash_; } |
59 | 61 |
60 Addr GetAddress() const; | 62 Addr GetAddress() const; |
61 EntryState GetState() const; | 63 EntryState GetState() const; |
62 EntryGroup GetGroup() const; | 64 EntryGroup GetGroup() const; |
63 int GetReuse() const; | 65 int GetReuse() const; |
64 int GetTimestamp() const; | 66 int GetTimestamp() const; |
65 | 67 |
66 void SetState(EntryState state); | 68 void SetState(EntryState state); |
67 void SetGroup(EntryGroup group); | 69 void SetGroup(EntryGroup group); |
68 void SetReuse(int count); | 70 void SetReuse(int count); |
69 void SetTimestamp(int timestamp); | 71 void SetTimestamp(int timestamp); |
70 | 72 |
71 static EntryCell GetEntryCellForTest(int32 cell_num, | 73 static EntryCell GetEntryCellForTest(int32_t cell_num, |
72 uint32 hash, | 74 uint32_t hash, |
73 Addr address, | 75 Addr address, |
74 IndexCell* cell, | 76 IndexCell* cell, |
75 bool small_table); | 77 bool small_table); |
76 void SerializaForTest(IndexCell* destination); | 78 void SerializaForTest(IndexCell* destination); |
77 | 79 |
78 private: | 80 private: |
79 friend class IndexTable; | 81 friend class IndexTable; |
80 friend class CacheDumperHelper; | 82 friend class CacheDumperHelper; |
81 | 83 |
82 EntryCell(); | 84 EntryCell(); |
83 EntryCell(int32 cell_num, uint32 hash, Addr address, bool small_table); | 85 EntryCell(int32_t cell_num, uint32_t hash, Addr address, bool small_table); |
84 EntryCell(int32 cell_num, | 86 EntryCell(int32_t cell_num, |
85 uint32 hash, | 87 uint32_t hash, |
86 const IndexCell& cell, | 88 const IndexCell& cell, |
87 bool small_table); | 89 bool small_table); |
88 | 90 |
89 void Clear() { cell_.Clear(); } | 91 void Clear() { cell_.Clear(); } |
90 void FixSum(); | 92 void FixSum(); |
91 | 93 |
92 // Returns the raw value stored on the index table. | 94 // Returns the raw value stored on the index table. |
93 uint32 GetLocation() const; | 95 uint32_t GetLocation() const; |
94 | 96 |
95 // Recalculates hash_ assuming that only the low order bits are valid and the | 97 // Recalculates hash_ assuming that only the low order bits are valid and the |
96 // rest come from cell_. | 98 // rest come from cell_. |
97 uint32 RecomputeHash(); | 99 uint32_t RecomputeHash(); |
98 | 100 |
99 void Serialize(IndexCell* destination) const; | 101 void Serialize(IndexCell* destination) const; |
100 | 102 |
101 int32 cell_num_; | 103 int32_t cell_num_; |
102 uint32 hash_; | 104 uint32_t hash_; |
103 IndexCell cell_; | 105 IndexCell cell_; |
104 bool small_table_; | 106 bool small_table_; |
105 }; | 107 }; |
106 | 108 |
107 // Keeps a collection of EntryCells in order to be processed. | 109 // Keeps a collection of EntryCells in order to be processed. |
108 struct NET_EXPORT_PRIVATE EntrySet { | 110 struct NET_EXPORT_PRIVATE EntrySet { |
109 EntrySet(); | 111 EntrySet(); |
110 ~EntrySet(); | 112 ~EntrySet(); |
111 | 113 |
112 int evicted_count; // The numebr of evicted entries in this set. | 114 int evicted_count; // The numebr of evicted entries in this set. |
113 size_t current; // The number of the cell that is being processed. | 115 size_t current; // The number of the cell that is being processed. |
114 std::vector<EntryCell> cells; | 116 std::vector<EntryCell> cells; |
115 }; | 117 }; |
116 | 118 |
117 // A given entity referenced by the index table is uniquely identified by the | 119 // A given entity referenced by the index table is uniquely identified by the |
118 // combination of hash and address. | 120 // combination of hash and address. |
119 struct CellInfo { uint32 hash; Addr address; }; | 121 struct CellInfo { |
| 122 uint32_t hash; |
| 123 Addr address; |
| 124 }; |
120 typedef std::vector<CellInfo> CellList; | 125 typedef std::vector<CellInfo> CellList; |
121 | 126 |
122 // An index iterator is used to get a group of cells that share the same | 127 // An index iterator is used to get a group of cells that share the same |
123 // timestamp. When this structure is passed to GetNextCells(), the caller sets | 128 // timestamp. When this structure is passed to GetNextCells(), the caller sets |
124 // the initial timestamp and direction; whet it is used with GetOldest, the | 129 // the initial timestamp and direction; whet it is used with GetOldest, the |
125 // initial values are ignored. | 130 // initial values are ignored. |
126 struct NET_EXPORT_PRIVATE IndexIterator { | 131 struct NET_EXPORT_PRIVATE IndexIterator { |
127 IndexIterator(); | 132 IndexIterator(); |
128 ~IndexIterator(); | 133 ~IndexIterator(); |
129 | 134 |
(...skipping 23 matching lines...) Expand all Loading... |
153 // The data required to initialize an index. Note that not all fields have to | 158 // The data required to initialize an index. Note that not all fields have to |
154 // be provided when growing the tables. | 159 // be provided when growing the tables. |
155 struct NET_EXPORT_PRIVATE IndexTableInitData { | 160 struct NET_EXPORT_PRIVATE IndexTableInitData { |
156 IndexTableInitData(); | 161 IndexTableInitData(); |
157 ~IndexTableInitData(); | 162 ~IndexTableInitData(); |
158 | 163 |
159 IndexBitmap* index_bitmap; | 164 IndexBitmap* index_bitmap; |
160 IndexBucket* main_table; | 165 IndexBucket* main_table; |
161 IndexBucket* extra_table; | 166 IndexBucket* extra_table; |
162 scoped_ptr<IndexHeaderV3> backup_header; | 167 scoped_ptr<IndexHeaderV3> backup_header; |
163 scoped_ptr<uint32[]> backup_bitmap; | 168 scoped_ptr<uint32_t[]> backup_bitmap; |
164 }; | 169 }; |
165 | 170 |
166 // See the description at the top of this file. | 171 // See the description at the top of this file. |
167 class NET_EXPORT_PRIVATE IndexTable { | 172 class NET_EXPORT_PRIVATE IndexTable { |
168 public: | 173 public: |
169 explicit IndexTable(IndexTableBackend* backend); | 174 explicit IndexTable(IndexTableBackend* backend); |
170 ~IndexTable(); | 175 ~IndexTable(); |
171 | 176 |
172 // Initializes the object, or re-initializes it when the backing files grow. | 177 // Initializes the object, or re-initializes it when the backing files grow. |
173 // Note that the only supported way to initialize this objeect is using | 178 // Note that the only supported way to initialize this objeect is using |
174 // pointers that come from the files being directly mapped in memory. If that | 179 // pointers that come from the files being directly mapped in memory. If that |
175 // is not the case, it must be emulated in a convincing way, for example | 180 // is not the case, it must be emulated in a convincing way, for example |
176 // making sure that the tables for re-init look the same as the tables to be | 181 // making sure that the tables for re-init look the same as the tables to be |
177 // replaced. | 182 // replaced. |
178 void Init(IndexTableInitData* params); | 183 void Init(IndexTableInitData* params); |
179 | 184 |
180 // Releases the resources acquired during Init(). | 185 // Releases the resources acquired during Init(). |
181 void Shutdown(); | 186 void Shutdown(); |
182 | 187 |
183 // Locates a resouce on the index. Returns a list of all resources that match | 188 // Locates a resouce on the index. Returns a list of all resources that match |
184 // the provided hash. | 189 // the provided hash. |
185 EntrySet LookupEntries(uint32 hash); | 190 EntrySet LookupEntries(uint32_t hash); |
186 | 191 |
187 // Creates a new cell to store a new resource. | 192 // Creates a new cell to store a new resource. |
188 EntryCell CreateEntryCell(uint32 hash, Addr address); | 193 EntryCell CreateEntryCell(uint32_t hash, Addr address); |
189 | 194 |
190 // Locates a particular cell. This method allows a caller to perform slow | 195 // Locates a particular cell. This method allows a caller to perform slow |
191 // operations with some entries while the index evolves, by returning the | 196 // operations with some entries while the index evolves, by returning the |
192 // current state of a cell. If the desired cell cannot be located, the return | 197 // current state of a cell. If the desired cell cannot be located, the return |
193 // object will be invalid. | 198 // object will be invalid. |
194 EntryCell FindEntryCell(uint32 hash, Addr address); | 199 EntryCell FindEntryCell(uint32_t hash, Addr address); |
195 | 200 |
196 // Returns an IndexTable timestamp for a given absolute time. The actual | 201 // Returns an IndexTable timestamp for a given absolute time. The actual |
197 // resolution of the timestamp should be considered an implementation detail, | 202 // resolution of the timestamp should be considered an implementation detail, |
198 // but it certainly is lower than seconds. The important part is that a group | 203 // but it certainly is lower than seconds. The important part is that a group |
199 // of cells will share the same timestamp (see IndexIterator). | 204 // of cells will share the same timestamp (see IndexIterator). |
200 int CalculateTimestamp(base::Time time); | 205 int CalculateTimestamp(base::Time time); |
201 | 206 |
202 // Returns the equivalent time for a cell timestamp. | 207 // Returns the equivalent time for a cell timestamp. |
203 base::Time TimeFromTimestamp(int timestamp); | 208 base::Time TimeFromTimestamp(int timestamp); |
204 | 209 |
205 // Updates a particular cell. | 210 // Updates a particular cell. |
206 void SetSate(uint32 hash, Addr address, EntryState state); | 211 void SetSate(uint32_t hash, Addr address, EntryState state); |
207 void UpdateTime(uint32 hash, Addr address, base::Time current); | 212 void UpdateTime(uint32_t hash, Addr address, base::Time current); |
208 | 213 |
209 // Saves the contents of |cell| to the table. | 214 // Saves the contents of |cell| to the table. |
210 void Save(EntryCell* cell); | 215 void Save(EntryCell* cell); |
211 | 216 |
212 // Returns the oldest entries for each group of entries. The initial values | 217 // Returns the oldest entries for each group of entries. The initial values |
213 // for the provided iterators are ignored. Entries are assigned to iterators | 218 // for the provided iterators are ignored. Entries are assigned to iterators |
214 // according to their EntryGroup. | 219 // according to their EntryGroup. |
215 void GetOldest(IndexIterator* no_use, | 220 void GetOldest(IndexIterator* no_use, |
216 IndexIterator* low_use, | 221 IndexIterator* low_use, |
217 IndexIterator* high_use); | 222 IndexIterator* high_use); |
218 | 223 |
219 // Returns the next group of entries for the provided iterator. This method | 224 // Returns the next group of entries for the provided iterator. This method |
220 // does not return the cells matching the initial iterator's timestamp, | 225 // does not return the cells matching the initial iterator's timestamp, |
221 // but rather cells after (or before, depending on the iterator's |forward| | 226 // but rather cells after (or before, depending on the iterator's |forward| |
222 // member) that timestamp. | 227 // member) that timestamp. |
223 bool GetNextCells(IndexIterator* iterator); | 228 bool GetNextCells(IndexIterator* iterator); |
224 | 229 |
225 // Called each time the index should save the backup information. The caller | 230 // Called each time the index should save the backup information. The caller |
226 // can assume that anything that needs to be saved is saved when this method | 231 // can assume that anything that needs to be saved is saved when this method |
227 // is called, and that there is only one source of timming information, and | 232 // is called, and that there is only one source of timming information, and |
228 // that source is controlled by the owner of this object. | 233 // that source is controlled by the owner of this object. |
229 void OnBackupTimer(); | 234 void OnBackupTimer(); |
230 | 235 |
231 IndexHeaderV3* header() { return header_; } | 236 IndexHeaderV3* header() { return header_; } |
232 const IndexHeaderV3* header() const { return header_; } | 237 const IndexHeaderV3* header() const { return header_; } |
233 | 238 |
234 private: | 239 private: |
235 EntryCell FindEntryCellImpl(uint32 hash, Addr address, bool allow_deleted); | 240 EntryCell FindEntryCellImpl(uint32_t hash, Addr address, bool allow_deleted); |
236 void CheckState(const EntryCell& cell); | 241 void CheckState(const EntryCell& cell); |
237 void Write(const EntryCell& cell); | 242 void Write(const EntryCell& cell); |
238 int NewExtraBucket(); | 243 int NewExtraBucket(); |
239 void WalkTables(int limit_time, | 244 void WalkTables(int limit_time, |
240 IndexIterator* no_use, | 245 IndexIterator* no_use, |
241 IndexIterator* low_use, | 246 IndexIterator* low_use, |
242 IndexIterator* high_use); | 247 IndexIterator* high_use); |
243 void UpdateFromBucket(IndexBucket* bucket, int bucket_hash, | 248 void UpdateFromBucket(IndexBucket* bucket, int bucket_hash, |
244 int limit_time, | 249 int limit_time, |
245 IndexIterator* no_use, | 250 IndexIterator* no_use, |
246 IndexIterator* low_use, | 251 IndexIterator* low_use, |
247 IndexIterator* high_use); | 252 IndexIterator* high_use); |
248 void MoveCells(IndexBucket* old_extra_table); | 253 void MoveCells(IndexBucket* old_extra_table); |
249 void MoveSingleCell(IndexCell* current_cell, int cell_num, | 254 void MoveSingleCell(IndexCell* current_cell, int cell_num, |
250 int main_table_index, bool growing); | 255 int main_table_index, bool growing); |
251 void HandleMisplacedCell(IndexCell* current_cell, int cell_num, | 256 void HandleMisplacedCell(IndexCell* current_cell, int cell_num, |
252 int main_table_index); | 257 int main_table_index); |
253 void CheckBucketList(int bucket_id); | 258 void CheckBucketList(int bucket_id); |
254 | 259 |
255 uint32 GetLocation(const IndexCell& cell); | 260 uint32_t GetLocation(const IndexCell& cell); |
256 uint32 GetHashValue(const IndexCell& cell); | 261 uint32_t GetHashValue(const IndexCell& cell); |
257 uint32 GetFullHash(const IndexCell& cell, uint32 lower_part); | 262 uint32_t GetFullHash(const IndexCell& cell, uint32_t lower_part); |
258 bool IsHashMatch(const IndexCell& cell, uint32 hash); | 263 bool IsHashMatch(const IndexCell& cell, uint32_t hash); |
259 bool MisplacedHash(const IndexCell& cell, uint32 hash); | 264 bool MisplacedHash(const IndexCell& cell, uint32_t hash); |
260 | 265 |
261 IndexTableBackend* backend_; | 266 IndexTableBackend* backend_; |
262 IndexHeaderV3* header_; | 267 IndexHeaderV3* header_; |
263 scoped_ptr<Bitmap> bitmap_; | 268 scoped_ptr<Bitmap> bitmap_; |
264 scoped_ptr<Bitmap> backup_bitmap_; | 269 scoped_ptr<Bitmap> backup_bitmap_; |
265 scoped_ptr<uint32[]> backup_bitmap_storage_; | 270 scoped_ptr<uint32_t[]> backup_bitmap_storage_; |
266 scoped_ptr<IndexHeaderV3> backup_header_; | 271 scoped_ptr<IndexHeaderV3> backup_header_; |
267 IndexBucket* main_table_; | 272 IndexBucket* main_table_; |
268 IndexBucket* extra_table_; | 273 IndexBucket* extra_table_; |
269 uint32 mask_; // Binary mask to map a hash to the hash table. | 274 uint32_t mask_; // Binary mask to map a hash to the hash table. |
270 int extra_bits_; // How many bits are in mask_ above the default value. | 275 int extra_bits_; // How many bits are in mask_ above the default value. |
271 bool modified_; | 276 bool modified_; |
272 bool small_table_; | 277 bool small_table_; |
273 | 278 |
274 DISALLOW_COPY_AND_ASSIGN(IndexTable); | 279 DISALLOW_COPY_AND_ASSIGN(IndexTable); |
275 }; | 280 }; |
276 | 281 |
277 } // namespace disk_cache | 282 } // namespace disk_cache |
278 | 283 |
279 #endif // NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ | 284 #endif // NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ |
OLD | NEW |