index_table_v3.h revision a1401311d1ab56c4ed0a474bd38c108f75cb0cd9
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 3// found in the LICENSE file. 4 5#ifndef NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ 6#define NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ 7 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, 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 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 14// with the tables in memory. 15// 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 18// re-initialized with the new structures. Note that the IndexTable instance is 19// still functional while the backend performs file IO. 20 21#include <vector> 22 23#include "base/basictypes.h" 24#include "base/memory/ref_counted.h" 25#include "base/memory/scoped_ptr.h" 26#include "base/time/time.h" 27#include "net/base/net_export.h" 28#include "net/disk_cache/blockfile/addr.h" 29#include "net/disk_cache/blockfile/bitmap.h" 30#include "net/disk_cache/blockfile/disk_format_v3.h" 31 32namespace net { 33class IOBuffer; 34} 35 36namespace disk_cache { 37 38class BackendImplV3; 39struct InitResult; 40 41// An EntryCell represents a single entity stored by the index table. Users are 42// expected to handle and store EntryCells on their own to track operations that 43// they are performing with a given entity, as opposed to deal with pointers to 44// individual positions on the table, given that the whole table can be moved to 45// another place, and that would invalidate any pointers to individual cells in 46// the table. 47// 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 49// operation completes. In that case, the caller should consult the table again 50// using FindEntryCell(). 51class NET_EXPORT_PRIVATE EntryCell { 52 public: 53 ~EntryCell(); 54 55 bool IsValid() const; 56 57 int32 cell_num() const { return cell_num_; } 58 uint32 hash() const { return hash_; } 59 60 Addr GetAddress() const; 61 EntryState GetState() const; 62 EntryGroup GetGroup() const; 63 int GetReuse() const; 64 int GetTimestamp() const; 65 66 void SetState(EntryState state); 67 void SetGroup(EntryGroup group); 68 void SetReuse(int count); 69 void SetTimestamp(int timestamp); 70 71 static EntryCell GetEntryCellForTest(int32 cell_num, 72 uint32 hash, 73 Addr address, 74 IndexCell* cell, 75 bool small_table); 76 void SerializaForTest(IndexCell* destination); 77 78 private: 79 friend class IndexTable; 80 friend class CacheDumperHelper; 81 82 EntryCell(); 83 EntryCell(int32 cell_num, uint32 hash, Addr address, bool small_table); 84 EntryCell(int32 cell_num, 85 uint32 hash, 86 const IndexCell& cell, 87 bool small_table); 88 89 void Clear() { cell_.Clear(); } 90 void FixSum(); 91 92 // Returns the raw value stored on the index table. 93 uint32 GetLocation() const; 94 95 // Recalculates hash_ assuming that only the low order bits are valid and the 96 // rest come from cell_. 97 uint32 RecomputeHash(); 98 99 void Serialize(IndexCell* destination) const; 100 101 int32 cell_num_; 102 uint32 hash_; 103 IndexCell cell_; 104 bool small_table_; 105}; 106 107// Keeps a collection of EntryCells in order to be processed. 108struct NET_EXPORT_PRIVATE EntrySet { 109 EntrySet(); 110 ~EntrySet(); 111 112 int evicted_count; // The numebr of evicted entries in this set. 113 size_t current; // The number of the cell that is being processed. 114 std::vector<EntryCell> cells; 115}; 116 117// A given entity referenced by the index table is uniquely identified by the 118// combination of hash and address. 119struct CellInfo { uint32 hash; Addr address; }; 120typedef std::vector<CellInfo> CellList; 121 122// 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 124// the initial timestamp and direction; whet it is used with GetOldest, the 125// initial values are ignored. 126struct NET_EXPORT_PRIVATE IndexIterator { 127 IndexIterator(); 128 ~IndexIterator(); 129 130 CellList cells; 131 int timestamp; // The current low resolution timestamp for |cells|. 132 bool forward; // The direction of the iteration, in time. 133}; 134 135// Methods that the backend has to implement to support the table. Note that the 136// backend is expected to own all IndexTable instances, so it is expected to 137// outlive the table. 138class NET_EXPORT_PRIVATE IndexTableBackend { 139 public: 140 virtual ~IndexTableBackend() {} 141 142 // The index has to grow. 143 virtual void GrowIndex() = 0; 144 145 // Save the index to the backup file. 146 virtual void SaveIndex(net::IOBuffer* buffer, int buffer_len) = 0; 147 148 // Deletes or fixes an invalid cell from the backend. 149 virtual void DeleteCell(EntryCell cell) = 0; 150 virtual void FixCell(EntryCell cell) = 0; 151}; 152 153// The data required to initialize an index. Note that not all fields have to 154// be provided when growing the tables. 155struct NET_EXPORT_PRIVATE IndexTableInitData { 156 IndexTableInitData(); 157 ~IndexTableInitData(); 158 159 IndexBitmap* index_bitmap; 160 IndexBucket* main_table; 161 IndexBucket* extra_table; 162 scoped_ptr<IndexHeaderV3> backup_header; 163 scoped_ptr<uint32[]> backup_bitmap; 164}; 165 166// See the description at the top of this file. 167class NET_EXPORT_PRIVATE IndexTable { 168 public: 169 explicit IndexTable(IndexTableBackend* backend); 170 ~IndexTable(); 171 172 // 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 174 // 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 176 // making sure that the tables for re-init look the same as the tables to be 177 // replaced. 178 void Init(IndexTableInitData* params); 179 180 // Releases the resources acquired during Init(). 181 void Shutdown(); 182 183 // Locates a resouce on the index. Returns a list of all resources that match 184 // the provided hash. 185 EntrySet LookupEntries(uint32 hash); 186 187 // Creates a new cell to store a new resource. 188 EntryCell CreateEntryCell(uint32 hash, Addr address); 189 190 // Locates a particular cell. This method allows a caller to perform slow 191 // 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 193 // object will be invalid. 194 EntryCell FindEntryCell(uint32 hash, Addr address); 195 196 // Returns an IndexTable timestamp for a given absolute time. The actual 197 // 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 199 // of cells will share the same timestamp (see IndexIterator). 200 int CalculateTimestamp(base::Time time); 201 202 // Returns the equivalent time for a cell timestamp. 203 base::Time TimeFromTimestamp(int timestamp); 204 205 // Updates a particular cell. 206 void SetSate(uint32 hash, Addr address, EntryState state); 207 void UpdateTime(uint32 hash, Addr address, base::Time current); 208 209 // Saves the contents of |cell| to the table. 210 void Save(EntryCell* cell); 211 212 // Returns the oldest entries for each group of entries. The initial values 213 // for the provided iterators are ignored. Entries are assigned to iterators 214 // according to their EntryGroup. 215 void GetOldest(IndexIterator* no_use, 216 IndexIterator* low_use, 217 IndexIterator* high_use); 218 219 // Returns the next group of entries for the provided iterator. This method 220 // does not return the cells matching the initial iterator's timestamp, 221 // but rather cells after (or before, depending on the iterator's |forward| 222 // member) that timestamp. 223 bool GetNextCells(IndexIterator* iterator); 224 225 // 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 227 // is called, and that there is only one source of timming information, and 228 // that source is controlled by the owner of this object. 229 void OnBackupTimer(); 230 231 IndexHeaderV3* header() { return header_; } 232 const IndexHeaderV3* header() const { return header_; } 233 234 private: 235 EntryCell FindEntryCellImpl(uint32 hash, Addr address, bool allow_deleted); 236 void CheckState(const EntryCell& cell); 237 void Write(const EntryCell& cell); 238 int NewExtraBucket(); 239 void WalkTables(int limit_time, 240 IndexIterator* no_use, 241 IndexIterator* low_use, 242 IndexIterator* high_use); 243 void UpdateFromBucket(IndexBucket* bucket, int bucket_hash, 244 int limit_time, 245 IndexIterator* no_use, 246 IndexIterator* low_use, 247 IndexIterator* high_use); 248 void MoveCells(IndexBucket* old_extra_table); 249 void MoveSingleCell(IndexCell* current_cell, int cell_num, 250 int main_table_index, bool growing); 251 void HandleMisplacedCell(IndexCell* current_cell, int cell_num, 252 int main_table_index); 253 void CheckBucketList(int bucket_id); 254 255 uint32 GetLocation(const IndexCell& cell); 256 uint32 GetHashValue(const IndexCell& cell); 257 uint32 GetFullHash(const IndexCell& cell, uint32 lower_part); 258 bool IsHashMatch(const IndexCell& cell, uint32 hash); 259 bool MisplacedHash(const IndexCell& cell, uint32 hash); 260 261 IndexTableBackend* backend_; 262 IndexHeaderV3* header_; 263 scoped_ptr<Bitmap> bitmap_; 264 scoped_ptr<Bitmap> backup_bitmap_; 265 scoped_ptr<uint32[]> backup_bitmap_storage_; 266 scoped_ptr<IndexHeaderV3> backup_header_; 267 IndexBucket* main_table_; 268 IndexBucket* extra_table_; 269 uint32 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. 271 bool modified_; 272 bool small_table_; 273 274 DISALLOW_COPY_AND_ASSIGN(IndexTable); 275}; 276 277} // namespace disk_cache 278 279#endif // NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_ 280