HttpCache::Transaction layer allowing parallel validation

net/http/http_cache.h

 // Copyright (c) 2012 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.
 
 // This file declares a HttpTransactionFactory implementation that can be
 // layered on top of another HttpTransactionFactory to add HTTP caching.  The
 // caching logic follows RFC 7234 (any exceptions are called out in the code).
 //
 // The HttpCache takes a disk_cache::Backend as a parameter, and uses that for
 // the cache storage.
@@ skipping 220 matching lines @@
     kResponseInfoIndex = 0,
     kResponseContentIndex,
     kMetadataIndex,
 
     // Must remain at the end of the enum.
     kNumCacheEntryDataIndices
   };
 
   class MetadataWriter;
   class QuicServerInfoFactoryAdaptor;
+  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;
-  class WorkItem;
   friend class Transaction;
   friend class ViewCacheHelper;
   struct PendingOp;  // Info for an entry under construction.
 
   using TransactionList = std::list<Transaction*>;
   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;
 
     // 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 =
       std::unordered_map<std::string, std::unique_ptr<ActiveEntry>>;
   using PendingOpsMap = std::unordered_map<std::string, PendingOp*>;
   using ActiveEntriesSet = std::map<ActiveEntry*, std::unique_ptr<ActiveEntry>>;
   using PlaybackCacheMap = std::unordered_map<std::string, int>;
 
   // Methods ------------------------------------------------------------------
 
@@ skipping 28 matching lines @@
 
   // Dooms the entry associated with a GET for a given |url|.
   void DoomMainEntryForUrl(const GURL& url);
 
   // Closes a previously doomed entry.
   void FinalizeDoomedEntry(ActiveEntry* entry);
 
   // 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);
 
   // Deletes an ActiveEntry.
   void DeactivateEntry(ActiveEntry* entry);
 
   // Deletes an ActiveEntry using an exhaustive search.
   void SlowDeactivateEntry(ActiveEntry* entry);
 
@@ skipping 14 matching lines @@
   // ActiveEntry in |*entry|. |trans| will be notified via its IO callback if
   // this method returns ERR_IO_PENDING.
   int CreateEntry(const std::string& key, ActiveEntry** entry,
                   Transaction* trans);
 
   // Destroys an ActiveEntry (active or doomed).
   void DestroyEntry(ActiveEntry* entry);
 
   // Adds a transaction to an ActiveEntry. If this method returns ERR_IO_PENDING
   // 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
   // to completion.
   void DoneWithEntry(ActiveEntry* entry, Transaction* trans, bool cancel);
 
   // 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);
 
   // Removes the transaction |trans|, from the pending list of an entry
   // (PendingOp, active or doomed entry).
   void RemovePendingTransaction(Transaction* trans);
 
   // Removes the transaction |trans|, from the pending list of |entry|.
   bool RemovePendingTransactionFromEntry(ActiveEntry* entry,
                                          Transaction* trans);
 
   // 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 ----------------------------------------------------------------
 
   // Processes BackendCallback notifications.
   void OnIOComplete(int result, PendingOp* entry);
 
   // Helper to conditionally delete |pending_op| if the HttpCache object it
   // is meant for has been deleted.
   //
   // TODO(ajwong): The PendingOp lifetime management is very tricky.  It might
@@ skipping 37 matching lines @@
   std::unique_ptr<base::Clock> clock_;
 
   base::WeakPtrFactory<HttpCache> weak_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(HttpCache);
 };
 
 }  // namespace net
 
 #endif  // NET_HTTP_HTTP_CACHE_H_