Merge Chromium + Blink git repositories

[chromium-blink-merge.git] / net / disk_cache / blockfile / index_table_v3.h

// 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_