// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_
#define NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_
// The IndexTable class is in charge of handling all the details about the main
// index table of the cache. It provides methods to locate entries in the cache,
// create new entries and modify existing entries. It hides the fact that the
// table is backed up across multiple physical files, and that the files can
// grow and be remapped while the cache is in use. However, note that this class
// doesn't do any direct management of the backing files, and it operates only
// with the tables in memory.
//
// When the current index needs to grow, the backend is notified so that files
// are extended and remapped as needed. After that, the IndexTable should be
// re-initialized with the new structures. Note that the IndexTable instance is
// still functional while the backend performs file IO.
#include <vector>
#include "base/basictypes.h"
#include "base/memory/ref_counted.h"
#include "base/memory/scoped_ptr.h"
#include "base/time/time.h"
#include "net/base/net_export.h"
#include "net/disk_cache/blockfile/addr.h"
#include "net/disk_cache/blockfile/bitmap.h"
#include "net/disk_cache/blockfile/disk_format_v3.h"
namespace net {
class IOBuffer;
}
namespace disk_cache {
class BackendImplV3;
struct InitResult;
// An EntryCell represents a single entity stored by the index table. Users are
// expected to handle and store EntryCells on their own to track operations that
// they are performing with a given entity, as opposed to deal with pointers to
// individual positions on the table, given that the whole table can be moved to
// another place, and that would invalidate any pointers to individual cells in
// the table.
// However, note that it is also possible for an entity to be moved from one
// position to another, so an EntryCell may be invalid by the time a long
// operation completes. In that case, the caller should consult the table again
// using FindEntryCell().
class NET_EXPORT_PRIVATE EntryCell {
public:
~EntryCell();
bool IsValid() const;
int32 cell_num() const { return cell_num_; }
uint32 hash() const { return hash_; }
Addr GetAddress() const;
EntryState GetState() const;
EntryGroup GetGroup() const;
int GetReuse() const;
int GetTimestamp() const;
void SetState(EntryState state);
void SetGroup(EntryGroup group);
void SetReuse(int count);
void SetTimestamp(int timestamp);
static EntryCell GetEntryCellForTest(int32 cell_num,
uint32 hash,
Addr address,
IndexCell* cell,
bool small_table);
void SerializaForTest(IndexCell* destination);
private:
friend class IndexTable;
friend class CacheDumperHelper;
EntryCell();
EntryCell(int32 cell_num, uint32 hash, Addr address, bool small_table);
EntryCell(int32 cell_num,
uint32 hash,
const IndexCell& cell,
bool small_table);
void Clear() { cell_.Clear(); }
void FixSum();
// Returns the raw value stored on the index table.
uint32 GetLocation() const;
// Recalculates hash_ assuming that only the low order bits are valid and the
// rest come from cell_.
uint32 RecomputeHash();
void Serialize(IndexCell* destination) const;
int32 cell_num_;
uint32 hash_;
IndexCell cell_;
bool small_table_;
};
// Keeps a collection of EntryCells in order to be processed.
struct NET_EXPORT_PRIVATE EntrySet {
EntrySet();
~EntrySet();
int evicted_count; // The numebr of evicted entries in this set.
size_t current; // The number of the cell that is being processed.
std::vector<EntryCell> cells;
};
// A given entity referenced by the index table is uniquely identified by the
// combination of hash and address.
struct CellInfo { uint32 hash; Addr address; };
typedef std::vector<CellInfo> CellList;
// An index iterator is used to get a group of cells that share the same
// timestamp. When this structure is passed to GetNextCells(), the caller sets
// the initial timestamp and direction; whet it is used with GetOldest, the
// initial values are ignored.
struct NET_EXPORT_PRIVATE IndexIterator {
IndexIterator();
~IndexIterator();
CellList cells;
int timestamp; // The current low resolution timestamp for |cells|.
bool forward; // The direction of the iteration, in time.
};
// Methods that the backend has to implement to support the table. Note that the
// backend is expected to own all IndexTable instances, so it is expected to
// outlive the table.
class NET_EXPORT_PRIVATE IndexTableBackend {
public:
virtual ~IndexTableBackend() {}
// The index has to grow.
virtual void GrowIndex() = 0;
// Save the index to the backup file.
virtual void SaveIndex(net::IOBuffer* buffer, int buffer_len) = 0;
// Deletes or fixes an invalid cell from the backend.
virtual void DeleteCell(EntryCell cell) = 0;
virtual void FixCell(EntryCell cell) = 0;
};
// The data required to initialize an index. Note that not all fields have to
// be provided when growing the tables.
struct NET_EXPORT_PRIVATE IndexTableInitData {
IndexTableInitData();
~IndexTableInitData();
IndexBitmap* index_bitmap;
IndexBucket* main_table;
IndexBucket* extra_table;
scoped_ptr<IndexHeaderV3> backup_header;
scoped_ptr<uint32[]> backup_bitmap;
};
// See the description at the top of this file.
class NET_EXPORT_PRIVATE IndexTable {
public:
explicit IndexTable(IndexTableBackend* backend);
~IndexTable();
// Initializes the object, or re-initializes it when the backing files grow.
// Note that the only supported way to initialize this objeect is using
// pointers that come from the files being directly mapped in memory. If that
// is not the case, it must be emulated in a convincing way, for example
// making sure that the tables for re-init look the same as the tables to be
// replaced.
void Init(IndexTableInitData* params);
// Releases the resources acquired during Init().
void Shutdown();
// Locates a resouce on the index. Returns a list of all resources that match
// the provided hash.
EntrySet LookupEntries(uint32 hash);
// Creates a new cell to store a new resource.
EntryCell CreateEntryCell(uint32 hash, Addr address);
// Locates a particular cell. This method allows a caller to perform slow
// operations with some entries while the index evolves, by returning the
// current state of a cell. If the desired cell cannot be located, the return
// object will be invalid.
EntryCell FindEntryCell(uint32 hash, Addr address);
// Returns an IndexTable timestamp for a given absolute time. The actual
// resolution of the timestamp should be considered an implementation detail,
// but it certainly is lower than seconds. The important part is that a group
// of cells will share the same timestamp (see IndexIterator).
int CalculateTimestamp(base::Time time);
// Returns the equivalent time for a cell timestamp.
base::Time TimeFromTimestamp(int timestamp);
// Updates a particular cell.
void SetSate(uint32 hash, Addr address, EntryState state);
void UpdateTime(uint32 hash, Addr address, base::Time current);
// Saves the contents of |cell| to the table.
void Save(EntryCell* cell);
// Returns the oldest entries for each group of entries. The initial values
// for the provided iterators are ignored. Entries are assigned to iterators
// according to their EntryGroup.
void GetOldest(IndexIterator* no_use,
IndexIterator* low_use,
IndexIterator* high_use);
// Returns the next group of entries for the provided iterator. This method
// does not return the cells matching the initial iterator's timestamp,
// but rather cells after (or before, depending on the iterator's |forward|
// member) that timestamp.
bool GetNextCells(IndexIterator* iterator);
// Called each time the index should save the backup information. The caller
// can assume that anything that needs to be saved is saved when this method
// is called, and that there is only one source of timming information, and
// that source is controlled by the owner of this object.
void OnBackupTimer();
IndexHeaderV3* header() { return header_; }
const IndexHeaderV3* header() const { return header_; }
private:
EntryCell FindEntryCellImpl(uint32 hash, Addr address, bool allow_deleted);
void CheckState(const EntryCell& cell);
void Write(const EntryCell& cell);
int NewExtraBucket();
void WalkTables(int limit_time,
IndexIterator* no_use,
IndexIterator* low_use,
IndexIterator* high_use);
void UpdateFromBucket(IndexBucket* bucket, int bucket_hash,
int limit_time,
IndexIterator* no_use,
IndexIterator* low_use,
IndexIterator* high_use);
void MoveCells(IndexBucket* old_extra_table);
void MoveSingleCell(IndexCell* current_cell, int cell_num,
int main_table_index, bool growing);
void HandleMisplacedCell(IndexCell* current_cell, int cell_num,
int main_table_index);
void CheckBucketList(int bucket_id);
uint32 GetLocation(const IndexCell& cell);
uint32 GetHashValue(const IndexCell& cell);
uint32 GetFullHash(const IndexCell& cell, uint32 lower_part);
bool IsHashMatch(const IndexCell& cell, uint32 hash);
bool MisplacedHash(const IndexCell& cell, uint32 hash);
IndexTableBackend* backend_;
IndexHeaderV3* header_;
scoped_ptr<Bitmap> bitmap_;
scoped_ptr<Bitmap> backup_bitmap_;
scoped_ptr<uint32[]> backup_bitmap_storage_;
scoped_ptr<IndexHeaderV3> backup_header_;
IndexBucket* main_table_;
IndexBucket* extra_table_;
uint32 mask_; // Binary mask to map a hash to the hash table.
int extra_bits_; // How many bits are in mask_ above the default value.
bool modified_;
bool small_table_;
DISALLOW_COPY_AND_ASSIGN(IndexTable);
};
} // namespace disk_cache
#endif // NET_DISK_CACHE_BLOCKFILE_INDEX_TABLE_V3_H_