Remove partial blockfile v3 disk_cache implementation.

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 <stddef.h>
-#include <stdint.h>
-
-#include <memory>
-#include <vector>
-
-#include "base/macros.h"
-#include "base/memory/ref_counted.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_t cell_num() const { return cell_num_; }
-  uint32_t 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_t cell_num,
-                                       uint32_t hash,
-                                       Addr address,
-                                       IndexCell* cell,
-                                       bool small_table);
-  void SerializaForTest(IndexCell* destination);
-
- private:
-  friend class IndexTable;
-  friend class CacheDumperHelper;
-
-  EntryCell();
-  EntryCell(int32_t cell_num, uint32_t hash, Addr address, bool small_table);
-  EntryCell(int32_t cell_num,
-            uint32_t hash,
-            const IndexCell& cell,
-            bool small_table);
-
-  void Clear() { cell_.Clear(); }
-  void FixSum();
-
-  // Returns the raw value stored on the index table.
-  uint32_t GetLocation() const;
-
-  // Recalculates hash_ assuming that only the low order bits are valid and the
-  // rest come from cell_.
-  uint32_t RecomputeHash();
-
-  void Serialize(IndexCell* destination) const;
-
-  int32_t cell_num_;
-  uint32_t hash_;
-  IndexCell cell_;
-  bool small_table_;
-};
-
-// Keeps a collection of EntryCells in order to be processed.
-struct NET_EXPORT_PRIVATE EntrySet {
-  EntrySet();
-  EntrySet(const EntrySet& other);
-  ~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_t 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;
-  std::unique_ptr<IndexHeaderV3> backup_header;
-  std::unique_ptr<uint32_t[]> 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_t hash);
-
-  // Creates a new cell to store a new resource.
-  EntryCell CreateEntryCell(uint32_t 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_t 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_t hash, Addr address, EntryState state);
-  void UpdateTime(uint32_t 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_t 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_t GetLocation(const IndexCell& cell);
-  uint32_t GetHashValue(const IndexCell& cell);
-  uint32_t GetFullHash(const IndexCell& cell, uint32_t lower_part);
-  bool IsHashMatch(const IndexCell& cell, uint32_t hash);
-  bool MisplacedHash(const IndexCell& cell, uint32_t hash);
-
-  IndexTableBackend* backend_;
-  IndexHeaderV3* header_;
-  std::unique_ptr<Bitmap> bitmap_;
-  std::unique_ptr<Bitmap> backup_bitmap_;
-  std::unique_ptr<uint32_t[]> backup_bitmap_storage_;
-  std::unique_ptr<IndexHeaderV3> backup_header_;
-  IndexBucket* main_table_;
-  IndexBucket* extra_table_;
-  uint32_t 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_