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.

[Randy Smith (Not in Mondays), 2013/11/07 20:25:15]

This doesn't seem quite right to me / doesn't match the code as I read it.  As I
read the code, what's happening is that when you call GetNextCells, you note the
current timestamp, trash the current set of cells, and get all cells that are in
the next timestamp that has any cells in it in the direction you're going.  That
right?  If so, I find "from the current timestamp" confusing; it's really from
the next oldest/youngest timestamp.  

It also looks to me as if currently, GetNextCells() is the only function that
takes/uses iterators.  If that's true and is likely to stay true for a while,
referring directly to that function would make sense to me. 

I also have a slight tug towards making this a nested class for IndexTable,
since it's only ever used with IndexTable.  I remember that nested classes are
discouraged, but my memory as to why is that often their definitions aren't
needed in the header files, and this definition is in the header file anyway. 
But it might be worth avoiding because it's not a common pattern, so this is
just a suggestion.

[rvargas (doing something else), 2013/11/08 04:22:30]

I'll clarify the comment. It doesn't mean that the caller sets the timestamp and
the callee returns cells that match it... it means that when the iterator is
returned, the cells in the iterator share the timestamp (as it is set on
return). So GetNext(from 0) will returns cells with 1, or 2 or n as timestamp,
not 0.

I'll also link the comment with the API.

As for a nested class, I don't mind it either way, but I know the guide applies
even to Delegates, which are tightly tied to the class that declares it and are
always going to be part of the same header... and we have lots of nested
delegates, but AFAIK we want to go in the other direction. But given that I
don't mind either way I'll leave it up to you.

+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/07 20:25:15]

Worth having a reference to IndexTable::CalculateTimestamp?

+  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);
+
+  // 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 LookupEntry(uint32 hash);

[Randy Smith (Not in Mondays), 2013/11/07 20:25:15]

nit, suggestion: This is a bit dependent on the definition of "Entry", but to
me, it's looking up multiple entries (all entries that share the same hash).  So
based on my current understanding of the abstractions, I think it would be
better as LookupEntries().  WDYT?

[rvargas (doing something else), 2013/11/08 04:22:30]

sure

+
+  // 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.

[Randy Smith (Not in Mondays), 2013/11/07 20:25:15]

The comment looks good to me.  Is it worthwhile having a reference to
IndexIterator here, since that's the only place that the consumer would use the
low resolution timestamp?

+  int CalculateTimestamp(base::Time time);
+
+  // 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(CellList* no_use, CellList* low_use, CellList* high_use);
+
+  // Returns the next group of entries for the provided iterator.
+  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,
+                           CellList* no_use, int* no_use_time,
+                           CellList* low_use, int* low_use_time,
+                           CellList* high_use, int* high_use_time);
+  void GetNewestFromBucket(IndexBucket* bucket, int bucket_hash,
+                           int limit_time, IndexIterator* iterator);

[Randy Smith (Not in Mondays), 2013/11/07 20:25:15]

I'm bothered by the parallel names here for two functions that do fairly
different things.  Maybe rename GetNewestFromBucket to UpdateIteratorFromBucket?

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

I still feel this way; what are your thoughts?

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

Sorry, I missed this after the last refactor.

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