HttpCache::Transaction layer allowing parallel validation

net/http/http_cache.h

Index: net/http/http_cache.h
diff --git a/net/http/http_cache.h b/net/http/http_cache.h
index 635cb92d557d17c6c60ca459f4117deb075f71f7..75ae5fb7e2c6104a9a45c79376dd13a84421b961 100644
--- a/net/http/http_cache.h
+++ b/net/http/http_cache.h
@@ -238,8 +238,8 @@ class NET_EXPORT HttpCache : public HttpTransactionFactory,
 
   class MetadataWriter;
   class QuicServerInfoFactoryAdaptor;
-  class Transaction;
   class WorkItem;

[jkarlin, 2017/03/07 16:45:41]

This isn't alphabetical.

[jkarlin, 2017/03/07 17:22:59]

I actually don't know that they need to be alphabetical, but it's nicer if they
are :)

[shivanisha, 2017/03/08 21:42:12]

Done.

+  class Transaction;
   friend class Transaction;
   friend class ViewCacheHelper;
   struct PendingOp;  // Info for an entry under construction.
@@ -248,7 +248,8 @@ class NET_EXPORT HttpCache : public HttpTransactionFactory,
   using TransactionSet = std::unordered_set<Transaction*>;
   typedef std::list<std::unique_ptr<WorkItem>> WorkItemList;
 
-  struct ActiveEntry {
+  class ActiveEntry {

[jkarlin, 2017/03/07 16:45:42]

If it's a class the members need to be private and have a _ suffix. This is
still reasonable as a struct.

[shivanisha, 2017/03/08 21:42:12]

Reverted it to being a struct. I initially thought it would have a weak_ptr_ and
thus perhaps better as a class, but I didn't need it later.

+   public:
     explicit ActiveEntry(disk_cache::Entry* entry);
     ~ActiveEntry();
     size_t EstimateMemoryUsage() const;
@@ -256,12 +257,32 @@ class NET_EXPORT HttpCache : public HttpTransactionFactory,
     // Returns true if no transactions are associated with this entry.
     bool HasNoTransactions();
 
-    disk_cache::Entry* disk_entry;
-    Transaction*       writer;
+    // Returns true if the given transaction is a reader.
+    bool IsReader(Transaction* transaction);
+
+    disk_cache::Entry* disk_entry = nullptr;
+
+    // Transaction currently reading from the network and writing to the cache.
+    Transaction* writer = nullptr;
+
+    // Transactions that can only read from the cache. Only one of writer or
+    // readers can exist at a time.
     TransactionSet readers;
-    TransactionList    pending_queue;
-    bool               will_process_pending_queue;
-    bool               doomed;
+
+    // Transactions waiting to be added to entry.

[Randy Smith (Not in Mondays), 2017/03/07 22:54:30]

nit: Thank you for the extra comments; they help!  Would you be willing to
expand them with the queue/element transition pathways?   I'm guessing that
transactions move from pending_queue -> validating_transaction ->
validated_queue -> {writer/readers}, but I'm not sure and it would be wonderful
to have that here.
 

[Randy Smith (Not in Mondays), 2017/03/08 19:11:23]

minor additional nit/suggestion: Ordering the members in the basic order a
transaction goes through them might be useful.

[shivanisha, 2017/03/08 21:42:12]

Done

+    TransactionList pending_queue;

[jkarlin, 2017/03/07 16:45:41]

pending_queue seems a bit vague now. Perhaps add_to_entry_queue?

[shivanisha, 2017/03/08 21:42:12]

Changed. add_to_entry_queue seems more consistent with HCT's states
STATE_ADD_TO_ENTRY and STATE_ADD_TO_ENTRY_COMPLETE which is when a transaction
is in this queue.

Also renaming will_process_pending_queue, ProcessPendingQueue and
OnProcessPendingQueue since they also process validated_queue. Renaming them to
will_process_waiting_transactions, ProcessWaitingTransactions and
OnProcessWaitingTransactions respectively.

+
+    // Transaction currently validating the response. This can exist
+    // simultaneously with writer or readers.
+    Transaction* validating_transaction = nullptr;
+
+    // Transactions that have completed their validation phase and are waiting
+    // to read the response body.
+    TransactionList validated_queue;
+
+    bool will_process_pending_queue = false;
+    bool will_process_parallel_validation = false;
+    bool doomed = false;
   };
 
   using ActiveEntriesMap =
@@ -310,6 +331,9 @@ class NET_EXPORT HttpCache : public HttpTransactionFactory,
   // Returns an entry that is currently in use and not doomed, or NULL.
   ActiveEntry* FindActiveEntry(const std::string& key);
 
+  // Returns true if given entry is still active.

[jkarlin, 2017/03/07 16:45:41]

What does it mean for an entry to be active? It's called "ActiveEntry" ;)

Perhaps Doomed() or IsDoomed?

[shivanisha, 2017/03/08 21:42:12]

Actually, it needs to search if the entry is alive, either as an active or
doomed entry. Changed the implementation to reflect this and the name to
IsEntryAlive()

+  bool IsEntryActive(const std::string& key, const ActiveEntry* entry);
+
   // Creates a new ActiveEntry and starts tracking it. |disk_entry| is the disk
   // cache entry.
   ActiveEntry* ActivateEntry(disk_cache::Entry* disk_entry);
@@ -346,8 +370,28 @@ class NET_EXPORT HttpCache : public HttpTransactionFactory,
   // the transaction will be notified about completion via its IO callback. This
   // method returns ERR_CACHE_RACE to signal the transaction that it cannot be

[jkarlin, 2017/03/07 16:45:41]

I don't think this actually does return ERR_CACHE_RACE. Can you remove that part
of the comment?

[shivanisha, 2017/03/08 21:42:12]

done

   // added to the provided entry, and it should retry the process with another
-  // one (in this case, the entry is no longer valid).
-  int AddTransactionToEntry(ActiveEntry* entry, Transaction* trans);
+  // one (in this case, the entry is no longer valid). validation_done should

[jkarlin, 2017/03/07 16:45:41]

|validation_done|. We wrap variable names in ||'s.

[shivanisha, 2017/03/08 21:42:12]

N/A now after refactoring.

+  // be passed as true if this transaction has already passed the validation
+  // phase, new_transaction should be passed as true if this transaction is a

[jkarlin, 2017/03/07 16:45:41]

same with |new_transaction|

[shivanisha, 2017/03/08 21:42:12]

N/A now after refactoring. Removed these from the comment.

+  // new transaction and not already added to queued in the entry.
+  int AddTransactionToEntry(ActiveEntry* entry,
+                            Transaction* transaction,
+                            bool validation_done = false,

[jkarlin, 2017/03/07 16:45:41]

nit: s/validation_done/validation_needed/

[shivanisha, 2017/03/08 21:42:12]

N/A now after refactoring.

+                            bool new_transaction = false);

[jkarlin, 2017/03/07 16:45:41]

nit: is_new_transaction to make it clear that it's a bool and not a transaction
type

[jkarlin, 2017/03/07 16:45:41]

This method has few enough existing callers that I don't think we should use
default values and instead update the callers.

[Randy Smith (Not in Mondays), 2017/03/08 19:11:23]

The style guide generally recommends against default arguments (which they
equivalence to overloaded functions).  See
https://google.github.io/styleguide/cppguide.html#Function_Overloading and the
following.  Can you give a sense as to why this should be an exception?  It's
often better to have separate functions with descriptive names, since that makes
it easier for people reading at the call site to understand exactly what's being
done.

[shivanisha, 2017/03/08 21:42:12]

Thanks for the link. 
Removed default arguments as part of refactoring this function.

[shivanisha, 2017/03/08 21:42:12]

N/A now after refactoring.

+
+  // Transaction invokes this when its validation matches the entry so another
+  // transaction can now start validation. write_this_response should be passed
+  // as true if this transaction is also responsible for writing the response
+  // body to the cache. Returns OK if the transaction is an active writer or
+  // reader and ERR_IO_PENDING if the transaction should wait to be able to read
+  // from the network or cache.
+  int OnValidationMatch(ActiveEntry* entry,

[jkarlin, 2017/03/07 16:45:41]

In keeping with the naming scheme, perhaps DoneWithValidation? You could combine
these two functions into one.

[shivanisha, 2017/03/08 21:42:12]

Done. Created DoneValidationWithEntry() and merged the match and no match cases.

Also created a separate DoneValidationWriteEntry() for the case where this
transaction is responsible for writing to the cache, thus eliminating the need
for write_this_response.

+                        Transaction* transaction,
+                        bool write_this_response);
+
+  // Transaction invokes this when its validation does not match the entry.
+  // Leads to dooming the entry and restarting the pending transactions.
+  void OnValidationNoMatch(ActiveEntry* entry, Transaction* transaction);
 
   // Called when the transaction has finished working with this entry. |cancel|
   // is true if the operation was cancelled by the caller instead of running
@@ -356,14 +400,22 @@ class NET_EXPORT HttpCache : public HttpTransactionFactory,
 
   // Called when the transaction has finished writing to this entry. |success|
   // is false if the cache entry should be deleted.
-  void DoneWritingToEntry(ActiveEntry* entry, bool success);
+  void DoneWritingToEntry(ActiveEntry* entry,
+                          bool success,
+                          Transaction* transaction);
+
+  // Processes other transactions when a transaction is done writing to the
+  // entry, based on success or failure of this transaction.
+  void DoneWritingToEntryProcessOtherTransactions(ActiveEntry* entry,
+                                                  bool success);
 
   // Called when the transaction has finished reading from this entry.
-  void DoneReadingFromEntry(ActiveEntry* entry, Transaction* trans);
+  void DoneReadingFromEntry(ActiveEntry* entry, Transaction* transaction);
 
-  // Converts the active writer transaction to a reader so that other
-  // transactions can start reading from this entry.
-  void ConvertWriterToReader(ActiveEntry* entry);
+  // Converts the active writer/validating transaction to a reader so that other
+  // transactions can start reading from this entry. Returns true if the
+  // transaction was added to readers.

[Randy Smith (Not in Mondays), 2017/03/07 22:54:30]

It's not clear to me what this documentation means; it's sorta "Do this thing. 
If you don't do this thing, return false".  Which makes it sound like false is
returned in an error case.  But if I look at the code, it's more that this
function moves a transaction out of a state in which its either the writer or
the validating transaction into whatever the right next state is (reader or
pending), and we return true/false to indicate what state it's actually moved
into.  Could we change the name and documentation to make this clearer?  Looking
at the calling locations, I actually think "DoneValidatingEntry" may make sense
as a name, with the doc being "Signals that a transaction's cache update
(writing/validation) is done and it should be moved into its next state. 
Returns true if the entry is now a reader".

This is a specific instance of a general issue that I care about a lot.  I
really want header comments to make sense from the viewpoint of the consumer
*without* the consumer having to look at the code of the producing class.  The
producing class should implement some abstraction that's higher level than its
member variables, and should talk in the comments on its methods in the language
of that higher layer abstraction.  If that isn't true, that's a layering
violation.  Sometimes that's the best thing (sometimes avoiding layering
violations require way too much effort to make it worthwhile) but I'm usually
going to treat comments that leak information about the class implementation the
same way I'd treat code, i.e. with a "Is there a better way to do this?"
question.

As a secondary point, I do wonder why the HttpCache::Transaction can't switch to
read mode without the transaction actually being in the readers set in the
HttpCache::ActiveEntry.  When we later finish up with a writer transaction,
won't we check the modes of the transactions in pending_transactions before we
set a new writer?  So shouldn't it be safe to just unilaterally change the mode
to READ in the transaction even if the cache didn't transition it into the
readers queue?  This would allow getting rid of the bool completely.

[shivanisha, 2017/03/08 21:42:12]

-- We want to preserve their original mode till we are sure that they can be
readers i.e. entry was successfully written to the cache. In case of a failure
we want these transactions to start afresh and then we would need their original
mode. HttpCache.SimpleGET_ManyWriters_CancelFirst is a test that crashes if we
don't preserve their original modes.
The implementation is now greatly simplified in the new patch and improved the
documentation as well.

+  bool ConvertWriterToReader(ActiveEntry* entry, Transaction* transaction);
 
   // Returns the LoadState of the provided pending transaction.
   LoadState GetLoadStateForPendingTransaction(const Transaction* trans);
@@ -379,12 +431,32 @@ class NET_EXPORT HttpCache : public HttpTransactionFactory,
   // Removes the transaction |trans|, from the pending list of |pending_op|.
   bool RemovePendingTransactionFromPendingOp(PendingOp* pending_op,
                                              Transaction* trans);
-  // Resumes processing the pending list of |entry|.
+  // Resumes processing the pending list of |entry|. This should always be
+  // called when the response is already written to the cache.
   void ProcessPendingQueue(ActiveEntry* entry);
 
+  // Invoked when a transaction can start validating the entry when there may be
+  // a writer/readers writing/reading to/from the entry.
+  void ProcessParallelValidation(ActiveEntry* entry);
+
   // Events (called via PostTask) ---------------------------------------------
 
-  void OnProcessPendingQueue(ActiveEntry* entry);
+  void OnProcessPendingQueue(const std::string& key, ActiveEntry* entry);
+
+  void OnProcessParallelValidation(const std::string& key, ActiveEntry* entry);
+
+  // Dooms the entry and restarts all the pending transactions.
+  void DoomEntryRestartPendingTransactions(ActiveEntry* entry);
+
+  // Destroys the entry and restarts all the pending transactions.
+  void DestroyEntryRestartPendingTransactions(ActiveEntry* entry);
+
+  // Retrieves all pending transactions from entry in a single list.
+  TransactionList GetAllPendingTransactions(ActiveEntry* entry);
+
+  // Helper function for restarting all pending transactions by invoking their
+  // IO callbacks with ERR_CACHE_RACE.

[jkarlin, 2017/03/07 16:45:41]

Is this actually a cache race though? Seems like a misuse of the flag.

[shivanisha, 2017/03/08 21:42:12]

This error code is used whenever we want the HCT state machine to restart. Its
more like ERR_CACHE_ENTRY_CREATE_FAILURE

+  void RestartPendingTransactions(const TransactionList& list);
 
   // Callbacks ----------------------------------------------------------------