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 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;
+struct IndexIterator {

[Randy Smith (Not in Mondays), 2013/11/05 22:31:13]

Index iterators look to me to be used in a very specific way, which is 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.  This seems a general enough concept to be worth
documenting; willing to throw in a comment discussing that here?

[rvargas (doing something else), 2013/11/06 02:23:03]

Done.

+  CellList cells;
+  int timestamp;  // The cerrent 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 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);
+
+  // 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.
+  int CalculateTimestamp(base::Time time);

[Randy Smith (Not in Mondays), 2013/11/05 22:31:13]

The existence of this function (and the fact that it's breaching the abstraction
boundary around index table timestamps) bothers me a little bit.  In an ideal
world, I'd think that either this class interface should only take base::Time
values, or we should define somewhere (maybe just in a comment) the minutes
since base value style of timestamps, and this class interface should only take
those values.

It looks to me from the target CL that the only place this function is (will
eventually be) used for iterator timestamp values, which suggests we could do
the abstraction cleanup by making the interface for IndexIterators be base::Time
(probably plus an IndexTable, possibly in the constructor).  

I'm not strongly in favor of that (there could very easily be complexities
having to do with threading and access to the base value that I'm not seeing),
but I wanted to raise the possibility in case it appealed to you.

[rvargas (doing something else), 2013/11/06 02:23:03]

The issue is that I intentionally wanted to keep the iterators as dumb structs
(even though now they have hidden ctor/dtors for reasons beyond my comprehension
at this time). And the time on the iterator cannot be a high resolution
variable, it has to be a low resolution timestamp, otherwise time comparisons
will fail.

Modifying the iterators to provide comparison functions and keep a pointer back
to the table to do translations seem like a high burden to hide the fact that
the resolution is lower on the table... and having a Time interface may make the
caller assume that things have a higher resolution.

I don't completely follow the first suggestion. Do you mean a typedef of int to
minutes or to timestamp?

[Randy Smith (Not in Mondays), 2013/11/06 18:16:15]

Why keep them as dumb structs?  I understand the motivation for the disk format
structs, but why the iterator?
Yep, I get that.  That's not the same as converting from a high resolution value
on construction or initialization, though (though I think we're clear on this
from your comments below).
Yeah, that makes sense.  I will say that since an IndexIterator only makes sense
in the context of a specific IndexTable (because the minutes it stores are
relevant to that IndexTable), I think a pointer from iterator to table actually
wouldn't be an unreasonable thing.

To be clear, my goal was not to hide the fact that the resolution is lower on
the table--it's to make the interface consistent.  If everything on the index
table took ints that were minutes since some fixed time, I'd be happy.  It's the
fact that consumes of the IndexTable interface both use base::Time and have to
understand and use the minutes-since-header_->base_time concept (in manipulating
the iterators).  
typedef of int to minutes would do it, or just a comment explaining that certain
arguments (maybe named index_minutes?  :-}) were minutes since
header_->base_time.  But that's not really ideal either, because
header_->base_time is a concept that's pretty far internal to the IndexTable. 
So this may not be worth it.  I just wanted to call out what I saw as an
abstraction breaking (that the minutes since base time concept escapes outside
the boundary of the IndexTable/IndexIterator interface) and explore whether
there was some way of fixing that.

[rvargas (doing something else), 2013/11/07 02:02:07]

It's just that I see this as a storage for iteration-related data, not really as
an object that is trying to encapsulate something. It's main purpose is to avoid
passing a bunch of separate arguments to all the functions that are involved
with enumerations.
it's certainly not unreasonable :)
I tried the typedef (Timestamp) but I didn't liked it!. I agree that I don't
want code outside of this class worrying about the actual resolution of the
timestamp... if it is 30 seconds, or 1 minute of whatever... and that's why I
don't want to make it part of the contract that it is actually 1 minute
(although there's a unit test for that)... but I still like the simple idea of
having the caller be aware of the existence of a low resolution time without
trying to hide that detail behind a full iterator interface. So I added a longer
comment.

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

Hmmm.  Makes sense.  I think part of why I pull in the other direction is just
because I find it useful to conceptually bundle groups of related functions
together.  Specifically InitIterator and UpdateIterator are very much "work with
the iterator data structure", so I feel a pull to declare them as methods of
iterator.  (InitIterator() could be the Iterator constructor with just a bit of
tweaking).  I could imagine those being fine as methods on a struct, but that's
a slippery slope to full class status.  So it's your call.

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

I thought you were going to say something like that :)

The thing is that both methods would be private to the iterator, because what
they do is an implementation detail of the code that returns iterators... is not
something that the reader of the header (user of the class) should worry
about... or ever directly use. That leads directly to making the struct a class,
with a friend, and for the caller to benefit it would now need actual public
methods thrown into the mix.

I think I still prefer the trivial, fully open view for the caller.

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

[Randy Smith (Not in Mondays), 2013/11/05 22:31:13]

I presume this is part of the class interface because the backup of the index
needs to be synchronized with other backend backup activities.  If that's
accurate, willing to put in a comment to that effect?  (Something like "Exposed
so that index backup can be synchronized with the backup of the IndexBackend
that owns the index."?)

[rvargas (doing something else), 2013/11/06 02:23:03]

Kind of. I can add more comments but I want to understand what you mean first. I
considered having a more direct command from the backend instead (DoFoo), but I
wanted to keep the essence of being a general purpose timer tick that can be
used by this class if it wants to (and for whatever it wants to)... and that
happens to be the same timer that other parts of the code use for other things
(which is _sort of_ required for things to work nicely).

... and the timer is provided from outside because it makes testing much easier
than just having an independent timer private to this class (plus seems more
wasteful).

So in terms of the need for synchronization that is just tangential... as in the
backend will delay operations for a while that should be enough for the index to
update the backup... so a number of choices would work for that.

So I don't know exactly how to frame the comment.

[Randy Smith (Not in Mondays), 2013/11/06 18:16:15]

"Interface exposed for testing, and in case backup of these data structures
should be synchronized with other backup operations."?  I'm mostly reacting to
the fact that when I read through the code I was initially confused as to why
this wasn't internal with its own timer--your reasons make sense to me, but I
think there's some use in making them explicit.

(I'll admit that hearing that the synchronization is "sort of" required for
things to work nicely makes me nervous; that's something I'd very much like to
have explained in its own comment in the code.  But I suspect that comment
doesn't belong here or in this CL.)

[rvargas (doing something else), 2013/11/07 02:02:07]

How about now?

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