Disk cache v3: The main index table.

net/disk_cache/v3/index_table.h

+// Copyright (c) 2013 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_V3_INDEX_TABLE_H_
+#define NET_DISK_CACHE_V3_INDEX_TABLE_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/addr.h"
+#include "net/disk_cache/bitmap.h"
+#include "net/disk_cache/v3/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_id() const { return cell_id_; }
+  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_id,
+                                       uint32 hash,
+                                       Addr address,
+                                       IndexCell* cell,
+                                       bool small_table);
+  void SerializaForTest(IndexCell* destination);
+
+ private:
+  friend class IndexTable;
+  friend class CacheDumperHelper;
+
+  EntryCell();
+  EntryCell(int32 cell_id, uint32 hash, Addr address, bool small_table);
+  EntryCell(int32 cell_id,
+            uint32 hash,
+            const IndexCell& cell,
+            bool small_table);
+
+  void Clear() { cell_.Clear(); }
+  void FixSum();
+
+  // Returns the raw value stored on the index table.
+  uint32 GetAddressValue() 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_id_;
+  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 all of which have the same
+// timestamp, and when passed back in again to the appropriate function, to get
+// the oldest / youngest group of cells from the current timestamp. When this

[Randy Smith (Not in Mondays), 2013/11/11 20:54:54]

nit, suggestion: "the oldest / youngest" -> "the next older / younger"?

+// structure is passed to GetNextCells(), the caller sets the initial timestamp
+// and the desired direction, and the function returns the cells and the actual
+// timestamp for them.

[Randy Smith (Not in Mondays), 2013/11/11 20:54:54]

I'm still finding this comment a bit confusing, both in the references to
functions above ("appropriate function" vs. "GetNextCells") and in the
description of what IndexIterator does and how its used.  The only interfaces
that this can be used with by the consumer are GetNextCells() and GetOldest(),
so if it's consumer targeted we should either refer to both those functions or
make an abstract reference to what they each do.  So I think I'd drop back a
couple of yards, and describe what the iterator is/can be used for in the
context of those functions.  How about something like:

"An index iterator holds a group of cells, all of which have the same timestamp.
 It can be used to iterate through the cells in an IndexTable  in a given
direction (forward or backward in time) via calls to GetNextCells(), returning
on each call all the cells with the same timestamp."

(See below as to why I'm leaving out GetOldest().)

[rvargas (doing something else), 2013/11/12 00:24:04]

Another attempt :)

+struct NET_EXPORT_PRIVATE IndexIterator {
+  IndexIterator();
+  ~IndexIterator();
+
+  CellList cells;
+  int timestamp;  // The current low resolution timestamp for |cells|.

[Randy Smith (Not in Mondays), 2013/11/11 20:54:54]

Did you have any reaction to my suggestion of cross references to/from
CalculateTimestamp below?

[rvargas (doing something else), 2013/11/12 00:24:04]

I don't particularly want to cross reference individual members... and the
structure itself is already cross referenced with the methods that return it; I
added some reference to the timestamp on the description of GetNextCells. I'm
adding an explicit reference to the iterator from CalculateTimestamp.

Note that I'm not really trying to hide the existence of a table/cell timestamp,
so both the table and the cell have methods that return a timestamp.

+  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.
+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.
+  void Init(IndexTableInitData* params);
+
+  // Releases the resources acquired during Init(). This method should not be
+  // called just to reinitialize the object.
+  void Reset();
+
+  // 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.
+  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.
+  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.
+  void GetOldest(IndexIterator* no_use,
+                 IndexIterator* low_use,
+                 IndexIterator* high_use);

[Randy Smith (Not in Mondays), 2013/11/11 20:54:54]

The implementation of this function initializes all the iterators and set the
forward variable, which I believe means that the caller really doesn't care
about the |forward| and |timestamp| portions of the IndexIterator.  Looking at 
https://codereview.chromium.org/17507006, it looks like the interface to this
function used to be CellLists.  Why isn't it in this CL?  That would seem to
capture the information being passed back to the caller more precisely.

[rvargas (doing something else), 2013/11/12 00:24:04]

Up to patch set 4, this method returned just the cells. However, unifying what
to do with a cell when doing enumerations meant that the signature of this
method had to change because otherwise the whole returned lists would have to be
copied just before returning (an iterator cannot keep a reference to a list, it
is the owner of the list). OK, I could swap the lists at that time... but the
caller is keeping the timestamps anyway because they are needed to select what
to delete, so the only thing that is really not used is the direction... or to
view it from the other side, this method returns three iterators, it just
ignores their initial values. I believe the reason this method was using lists
directly is that I probably wrote it before creating the iterators.

+
+  // Returns the next group of entries for the provided iterator. Keep in mind
+  // that this method does not return the cells matching the provided timestamp,
+  // but rather cells after (or before) 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 GetOldestFromBucket(IndexBucket* bucket, int bucket_hash,
+                           IndexIterator* no_use,
+                           IndexIterator* low_use,
+                           IndexIterator* high_use);
+  void GetNewestFromBucket(IndexBucket* bucket, int bucket_hash,
+                           int limit_time, IndexIterator* iterator);
+  void MoveCells(IndexBucket* old_extra_table);
+  void MoveSingleCell(IndexCell* current_cell, int cell_id,
+                      int main_table_index, bool growing);
+  void HandleMisplacedCell(IndexCell* current_cell, int cell_id,
+                           int main_table_index);
+  void CheckBucketList(int bucket_id);
+
+  uint32 GetAddressValue(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_V3_INDEX_TABLE_H_