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 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.
+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);

[Randy Smith (Not in Mondays), 2013/11/13 21:14:12]

I tried to grok the different usages of CreateEntryCell() and FindEntryCell() by
looking at the reference v3 CL, but I couldn't get it.  They look different
enough that my initial thought of "Would a single FindOrCreate interface work?"
almost certainly wasn't a good one.  But I'm not certain I understand why; could
you give me a sense as to how these will usually be used?  Specifically, it
seems like if you're doing a CreateEntryCell(), you've already done the hard
work if you've figured out the address, so it sounds like CreateEntryCell should
only be called from code that actually does allocation within the cache (which
is the backend??).  FindEntryCell you can do when you have the address, but
where are you likely to have gotten the address from, if not the cache?

[rvargas (doing something else), 2013/11/14 02:54:19]

There should be only two callers for CreateEntryCell and that is the backend
creating a new entry (after making sure that the entry doesn't exist), and
creating an evicted entry record, when evicting a normal entry.

On the other hand, FindEntryCell is used to make sure that something that was
valid some time ago is still valid right now (this is explained with the
declaration of EntryCell).

Basically, after calling LookupEntries you end up with a bunch of records that
exist right now (hopefully just one), but the caller now has to go open that
file and read it, and that takes time. By the time that operation completes, the
caller should not use the same EntryCell right away, or at least not write to
it, because it may have moved. So it has to grab the hash and address and do a
quick look up to get the current location of the cell, and then it can write to
it.

[Randy Smith (Not in Mondays), 2013/11/18 20:37:04]

So to reflect back, CreateEntryCell creates a new entry in the bucket chain for
the given hash given the address, and FindEntryCell confirms that there already
exists an entry in the bucket chain for the given hash that matches the address,
and returns it, returning a null EntryCell() if there is no such entry?  That
makes sense.  Would you be willing to add a note about the null EntryCell()
return case in the comment in the .h file, and possibly about the normal usage
for FindEntryCell() to be to confirm the existence of the given entry at that
location after an asynchronous operation?

[rvargas (doing something else), 2013/11/18 23:43:34]

I had already modified the comment to reflect use (not sure if you saw that).
Added the point about return on failure.

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

Yeah, sorry, missed the mod.  This looks good.

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

[Randy Smith (Not in Mondays), 2013/11/13 21:14:12]

Where is the boundary between low usage and high usage defined?

[rvargas (doing something else), 2013/11/14 02:54:19]

That's an implementation detail of the eviction algorithm (eviction_v3.cc)

[Randy Smith (Not in Mondays), 2013/11/18 20:37:04]

So why is it exposed on a public interface?  (Not a question for this CL, more
of an overall design question.)   If it's exposed on a public interface, it
seems like it should have some sort of, maybe handwavy, definition for the
callers of that interface.

[rvargas (doing something else), 2013/11/18 23:43:34]

I'm not sure I follow. It is not defined in an interface, but clearly the caller
should be able to get the data out of the table. What is defined is that each
entry has a use counter, a fetch counter and a group. (cells don't have fetch
counter, but have a group). The caller is able to set the group and counter at
will, retrieve it from a particular cell, and get all cells from all groups
given a time constrain (this method). The mapping of counters to groups is the
detail that is private to the eviction code.

The only detail about the arguments is that the method doesn't return evicted
entries, in part because I have not written the code to delete evicted entries
yet. In that sense, this method provides strictly what the caller needs so it's
not really general purpose, but I think that's fine.

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

Ah, ok, I think I follow.  The category that an entry is in can be set
externally to that entry, but is limited to values in the EntryGroup enum.  The
eviction code is the only code that sets those values, and is the only consumer
of this interface.  So there's a way in which this interface is hiding consumer
information from the producer, not the other way around.

Just looking at this interface in isolation, I'd value having a comment
reference indicating that the iterator into which individual entries are placed
depends in the EntryGroup value associated with them.  But I could easily
imagine that anyone who was doing any extended work in the cache would recognize
that *_use referred to EntryGroup, and hence wouldn't need the reference.  So
I'll raise that as an idea and leave it up to you whether to take it or not.
Yeah, I agree.  It's also very much targeted at the eviction code--no other
caller will really have any use for it.  In an ideal world, there'd be a private
pipe for that information from IndexTable->eviction code so that other consumers
wouldn't be distracted by/have access to the interface, but I think that's way
more trouble than it's worth.

[rvargas (doing something else), 2013/11/26 19:54:40]

done

+  void GetOldest(IndexIterator* no_use,
+                 IndexIterator* low_use,
+                 IndexIterator* high_use);
+
+  // 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,

[Randy Smith (Not in Mondays), 2013/11/13 21:14:12]

nit(s): I'd leave out the "keep in mind" since I don't think that information is
actually given anywhere else, change "the provided timestamp" to "the iterator's
timestamp", and change "(or before)" to "(or before, depending on the value of
the iterator's forward member)".  With that, I think this documentation + the
iterator documentation is good; are those changes ok with you?

[rvargas (doing something else), 2013/11/14 02:54:19]

I meant it to be "as implied by the name" (otherwise it would be GetCurrentCells
or something like that) :) dropped.
changed the wording slightly because I think it is important to keep the
distinction between the value when it is called and on return.

[Randy Smith (Not in Mondays), 2013/11/18 20:37:04]

The revised doc looks good to me.

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