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 238 matching lines @@
   typedef std::list<std::unique_ptr<WorkItem>> WorkItemList;
 
   struct ActiveEntry {
     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 no active readers/writer transactions are associated
+    // with this entry.
+    bool HasNoActiveTransactions();
+
+    // Returns true if the given transaction is a reader.
+    bool IsReader(Transaction* transaction);
+
+    disk_cache::Entry* disk_entry = nullptr;
+
+    // The following variables represent the various transactions associated
+    // with this entry in different stages. A transaction goes through these
+    // transitions. [] signifies an optional stage.
+    //
+    // Write mode transactions:
+    // [add_to_entry_queue]-> validating_transaction & writer -> writer
+    // [add_to_entry_queue]-> validating_transaction -> validated_queue ->
+    // readers (once the data is written to the cache by another writer)
+    // [add_to_entry_queue]-> validating_transaction -> writer
+    // (if the original writer could not write to the cache because of
+    // failure/cancellation)
+    //
+    // Read only transactions:
+    // [add_to_entry_queue]-> readers (once the data is written to the cache by
+    // the writer)

[jkarlin, 2017/03/09 17:42:56]

How about the following design for the progression of ActiveEntry states? How
far off is this from what is already implemented?

1. Writing Response Headers
2. Writing Response Body 
3. Reading

The first two states are optional (e.g., if no writing is necessary). But the
state can only move forward (e.g., if the writing fails in state one, abort
entry and restart transactions, else abort entry and all transactions). Once in
the Reading state, no writing should occur (including writing back 304 response
headers of validating transaction?), and any transaction that doesn't validate
leaves and moves on to a new transaction.

While in states 2 or 3, parallel validation may occur.

+
+    // Transactions waiting to be added to entry.
+    TransactionList add_to_entry_queue;
+
+    // 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;
+
+    // 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;
+
+    // The following variables are true if OnProcessWaitingTransactions or
+    // OnProcessParallelValidation is set to true.
+    bool will_process_waiting_transactions = false;
+    bool will_process_parallel_validation = false;
+
+    // True if entry is doomed.
+    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 alive, either as an active or doomed
+  // entry.
+  bool IsEntryAlive(const std::string& key, 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 13 matching lines @@
   // Creates the disk cache entry associated with |key|, returning an
   // 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
-  // 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);
+  // the transaction will be notified about completion via its IO callback.
+
+  int AddTransactionToEntry(ActiveEntry* entry, Transaction* transaction);
+  int AddTransactionToEntryImpl(ActiveEntry* entry, Transaction* transaction);
+  int AddTransactionToEntryForRead(ActiveEntry* entry,
+                                   Transaction* transaction);
+  int AddTransactionToEntryForWrite(ActiveEntry* entry,
+                                    Transaction* transaction);

[jkarlin, 2017/03/09 17:42:57]

The above 3 methods don't need to be class methods. They can live in the cc file
in the anonymous namespace.

[shivanisha, 2017/03/14 17:34:45]

N/A after recent refactoring.

+
+  // Transaction invokes this when its validation matches the entry so another
+  // transaction can now start validation. is_match should be passed
+  // as true if the validation was a match.
+  // If its not a match, this entry is doomed and pending transactions are
+  // restarted. Returns OK.
+  // If it is a match, either the transaction becomes a reader if the entry is
+  // already written to the cache and returns OK or the transaction is added to
+  // a queue if response is being written to the cache by another transaction
+  // and returns ERR_IO_PENDING.
+  int DoneValidationWithEntry(ActiveEntry* entry,
+                              Transaction* transaction,
+                              bool is_match);
+
+  // Transaction invokes this when it has completed validation and it is
+  // proceeding to start writing the response body to the cache. This is done so
+  // that another waiting transaction can start validating the headers in
+  // parallel.
+  void DoneValidationWriteEntry(ActiveEntry* entry, Transaction* transaction);

[jkarlin, 2017/03/09 17:42:56]

So at this point the Writer is done with the response (e.g., it has written or
validated the response headers)? In which case, let's call this one something
like DoneWritingResponseHeadersToEntry.

[shivanisha, 2017/03/14 17:34:45]

Renamed to DoneResponseHeaders because in case of no match, the headers are not
written to the entry.

 
   // 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,

[jkarlin, 2017/03/09 17:42:56]

Should be in anonymous namespace?

[shivanisha, 2017/03/14 17:34:45]

This function no longer exists

+                                                  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. It is invoked in the
+  // validation phase of a transaction when the current entry is validated. It
+  // needs to differentiate between the scenarios when the entry is already
+  // completely written to by another transaction or is currently being written.
+  // In the latter case, the transaction cannot become a reader at this time and
+  // the function will return false, else it will return true.
+  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|.
-  void ProcessPendingQueue(ActiveEntry* entry);
+  // Resumes processing the pending list of |entry|. This should always be
+  // called when the response is already written to the cache.
+  void ProcessWaitingTransactions(ActiveEntry* entry);

[jkarlin, 2017/03/09 17:42:56]

Should be in anonymous namespace?

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

[jkarlin, 2017/03/09 17:42:57]

Should be in anonymous namespace?

 
   // Events (called via PostTask) ---------------------------------------------
 
-  void OnProcessPendingQueue(ActiveEntry* entry);
+  void OnProcessWaitingTransactions(const std::string& key, ActiveEntry* entry);

[jkarlin, 2017/03/09 17:42:57]

Should be in anonymous namespace?

+
+  void OnProcessParallelValidation(const std::string& key, ActiveEntry* entry);

[jkarlin, 2017/03/09 17:42:57]

Should be in anonymous namespace?

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

[jkarlin, 2017/03/09 17:42:57]

Should be in anonymous namespace? Also, why is this in the "Events" section of
the header?

[shivanisha, 2017/03/14 17:34:45]

Since ActiveEntry is a private structure in HttpCache, cannot keep it in
anonymous namespace.

+
+  // Helper function for restarting all pending transactions by invoking their
+  // IO callbacks with ERR_CACHE_RACE.
+  void RestartPendingTransactions(const TransactionList& list);

[jkarlin, 2017/03/09 17:42:57]

Should be in anonymous namespace?

[shivanisha, 2017/03/14 17:34:45]

done

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