HttpCache::Transaction layer allowing parallel validation

net/http/http_cache.cc

 // 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.
 
 #include "net/http/http_cache.h"
 
 #include <algorithm>
 #include <utility>
 
 #include "base/bind.h"
@@ skipping 78 matching lines @@
                                         true,
                                         thread_,
                                         net_log,
                                         backend,
                                         callback);
 }
 
 //-----------------------------------------------------------------------------
 
 HttpCache::ActiveEntry::ActiveEntry(disk_cache::Entry* entry)
-    : disk_entry(entry),
-      writer(NULL),
-      will_process_pending_queue(false),
-      doomed(false) {
-}
+    : disk_entry(entry) {}
 
 HttpCache::ActiveEntry::~ActiveEntry() {
   if (disk_entry) {
     disk_entry->Close();
-    disk_entry = NULL;
+    disk_entry = nullptr;
   }
 }
 
 size_t HttpCache::ActiveEntry::EstimateMemoryUsage() const {
   // Skip |disk_entry| which is tracked in simple_backend_impl; Skip |readers|
-  // and |pending_queue| because the Transactions are owned by their respective
-  // URLRequestHttpJobs.
+  // and |add_to_entry_queue| because the Transactions are owned by their
+  // respective URLRequestHttpJobs.
   return 0;
 }
 
 bool HttpCache::ActiveEntry::HasNoTransactions() {
-  return !writer && readers.empty() && pending_queue.empty();
+  return !writer && readers.empty() && add_to_entry_queue.empty() &&
+         done_headers_queue.empty() && !headers_transaction;
+}
+
+bool HttpCache::ActiveEntry::HasNoActiveTransactions() {
+  return !writer && readers.empty() && !headers_transaction;
 }
 
 //-----------------------------------------------------------------------------
 
 // This structure keeps track of work items that are attempting to create or
 // open cache entries or the backend itself.
 struct HttpCache::PendingOp {
   PendingOp() : disk_entry(NULL) {}
   ~PendingOp() {}
 
@@ skipping 81 matching lines @@
   disk_cache::Backend** backend_;
 };
 
 //-----------------------------------------------------------------------------
 
 // This class encapsulates a transaction whose only purpose is to write metadata
 // to a given entry.
 class HttpCache::MetadataWriter {
  public:
   explicit MetadataWriter(HttpCache::Transaction* trans)
-      : transaction_(trans),
-        verified_(false),
-        buf_len_(0) {
-  }
+      : verified_(false), buf_len_(0), transaction_(trans) {}
 
   ~MetadataWriter() {}
 
   // Implements the bulk of HttpCache::WriteMetadata.
   void Write(const GURL& url,
              base::Time expected_response_time,
              IOBuffer* buf,
              int buf_len);
 
  private:
   void VerifyResponse(int result);
   void SelfDestroy();
   void OnIOComplete(int result);
 
-  std::unique_ptr<HttpCache::Transaction> transaction_;
   bool verified_;
   scoped_refptr<IOBuffer> buf_;
   int buf_len_;
   base::Time expected_response_time_;
   HttpRequestInfo request_info_;
+
+  // |transaction_| to come after |request_info_| so that |request_info_| is not
+  // destroyed earlier.
+  std::unique_ptr<HttpCache::Transaction> transaction_;
   DISALLOW_COPY_AND_ASSIGN(MetadataWriter);
 };
 
 void HttpCache::MetadataWriter::Write(const GURL& url,
                                       base::Time expected_response_time,
                                       IOBuffer* buf,
                                       int buf_len) {
   DCHECK_GT(buf_len, 0);
   DCHECK(buf);
   DCHECK(buf->data());
@@ skipping 79 matching lines @@
   session->SetServerPushDelegate(
       base::MakeUnique<HttpCacheLookupManager>(this));
 }
 
 HttpCache::~HttpCache() {
   // Transactions should see an invalid cache after this point; otherwise they
   // could see an inconsistent object (half destroyed).
   weak_factory_.InvalidateWeakPtrs();
 
   // If we have any active entries remaining, then we need to deactivate them.
-  // We may have some pending calls to OnProcessPendingQueue, but since those
-  // won't run (due to our destruction), we can simply ignore the corresponding
-  // will_process_pending_queue flag.
+  // We may have some pending tasks to process queued transactions ,but since
+  // those won't run (due to our destruction), we can simply ignore the
+  // corresponding flags.
   while (!active_entries_.empty()) {
     ActiveEntry* entry = active_entries_.begin()->second.get();
-    entry->will_process_pending_queue = false;
-    entry->pending_queue.clear();
+    entry->will_process_queued_transactions = false;
+    entry->add_to_entry_queue.clear();
     entry->readers.clear();
-    entry->writer = NULL;
+    entry->done_headers_queue.clear();
+    entry->headers_transaction = nullptr;
+    entry->writer = nullptr;
     DeactivateEntry(entry);
   }
 
   doomed_entries_.clear();
 
   // Before deleting pending_ops_, we have to make sure that the disk cache is
   // done with said operations, or it will attempt to use deleted data.
   disk_cache_.reset();
 
   for (auto pending_it = pending_ops_.begin(); pending_it != pending_ops_.end();
@@ skipping 240 matching lines @@
   // We keep track of doomed entries so that we can ensure that they are
   // cleaned up properly when the cache is destroyed.
   ActiveEntry* entry_ptr = entry.get();
   DCHECK_EQ(0u, doomed_entries_.count(entry_ptr));
   doomed_entries_[entry_ptr] = std::move(entry);
 
   entry_ptr->disk_entry->Doom();
   entry_ptr->doomed = true;
 
   DCHECK(entry_ptr->writer || !entry_ptr->readers.empty() ||
-         entry_ptr->will_process_pending_queue);
+         entry_ptr->headers_transaction ||
+         entry_ptr->will_process_queued_transactions);
   return OK;
 }
 
 int HttpCache::AsyncDoomEntry(const std::string& key, Transaction* trans) {
   std::unique_ptr<WorkItem> item =
       base::MakeUnique<WorkItem>(WI_DOOM_ENTRY, trans, nullptr);
   PendingOp* pending_op = GetPendingOp(key);
   if (pending_op->writer) {
     pending_op->pending_queue.push_back(std::move(item));
     return ERR_IO_PENDING;
@@ skipping 35 matching lines @@
   DCHECK(entry->doomed);
   DCHECK(entry->HasNoTransactions());
 
   auto it = doomed_entries_.find(entry);
   DCHECK(it != doomed_entries_.end());
   doomed_entries_.erase(it);
 }
 
 HttpCache::ActiveEntry* HttpCache::FindActiveEntry(const std::string& key) {
   auto it = active_entries_.find(key);
-  return it != active_entries_.end() ? it->second.get() : NULL;
+  return it != active_entries_.end() ? it->second.get() : nullptr;
 }
 
 HttpCache::ActiveEntry* HttpCache::ActivateEntry(
     disk_cache::Entry* disk_entry) {
   DCHECK(!FindActiveEntry(disk_entry->GetKey()));
   ActiveEntry* entry = new ActiveEntry(disk_entry);
   active_entries_[disk_entry->GetKey()] = base::WrapUnique(entry);
   return entry;
 }
 
 void HttpCache::DeactivateEntry(ActiveEntry* entry) {
-  DCHECK(!entry->will_process_pending_queue);
+  DCHECK(!entry->will_process_queued_transactions);
   DCHECK(!entry->doomed);
   DCHECK(entry->disk_entry);
   DCHECK(entry->HasNoTransactions());
 
   std::string key = entry->disk_entry->GetKey();
   if (key.empty())
     return SlowDeactivateEntry(entry);
 
   auto it = active_entries_.find(key);
   DCHECK(it != active_entries_.end());
@@ skipping 109 matching lines @@
 }
 
 void HttpCache::DestroyEntry(ActiveEntry* entry) {
   if (entry->doomed) {
     FinalizeDoomedEntry(entry);
   } else {
     DeactivateEntry(entry);
   }
 }
 
-int HttpCache::AddTransactionToEntry(ActiveEntry* entry, Transaction* trans) {
+int HttpCache::AddTransactionToEntry(ActiveEntry* entry,
+                                     Transaction* transaction) {
   DCHECK(entry);
   DCHECK(entry->disk_entry);
-
-  // We implement a basic reader/writer lock for the disk cache entry.  If
-  // there is already a writer, then everyone has to wait for the writer to
-  // finish before they can access the cache entry.  There can be multiple
-  // readers.
-  //
-  // NOTE: If the transaction can only write, then the entry should not be in
-  // use (since any existing entry should have already been doomed).
-
-  if (entry->writer || entry->will_process_pending_queue) {
-    entry->pending_queue.push_back(trans);
-    return ERR_IO_PENDING;
-  }
-
-  if (trans->mode() & Transaction::WRITE) {
-    // transaction needs exclusive access to the entry
-    if (entry->readers.empty()) {
-      entry->writer = trans;
-    } else {
-      entry->pending_queue.push_back(trans);
-      return ERR_IO_PENDING;
+  // Always add a new transaction to the queue to maintain FIFO order.
+  entry->add_to_entry_queue.push_back(transaction);
+  ProcessQueuedTransactions(entry);
+  return ERR_IO_PENDING;
+}
+
+int HttpCache::DoneWithResponseHeaders(ActiveEntry* entry,
+                                       Transaction* transaction,
+                                       bool is_partial) {
+  // If |transaction| is the current writer, do nothing. This can happen for
+  // range requests since they can go back to headers phase after starting to
+  // write.
+  if (entry->writer == transaction)
+    return OK;
+
+  CHECK_EQ(entry->headers_transaction, transaction);
+
+  entry->headers_transaction = nullptr;
+
+  // If transaction is responsible for writing the response body, then do not go
+  // through done_headers_queue for performance benefit. (Also, in case of
+  // writer transaction, the consumer sometimes depend on synchronous behaviour
+  // e.g. while computing raw headers size. (crbug.com/711766))
+  if (transaction->mode() & Transaction::WRITE) {
+    // Partial requests may have write mode even when there is a writer present
+    // since they may be reader for a particular range and writer for another
+    // range.
+    CHECK(is_partial || (!entry->writer && entry->done_headers_queue.empty()));

[Randy Smith (Not in Mondays), 2017/05/09 23:20:32]

This is a (check-level) behavior change.  Crashes used to happen if |is_partial
&& !entry->done_headers_queue.empty()| and no longer will.  The description of
this PS didn't mention a change in check behavior, just changing from
DCHECK->CHECK.  Why the change?

[shivanisha, 2017/05/10 14:46:03]

Ah right. I forgot to mention that in the patch description. The patch that
changed the behavior of the dcheck to include partial cases was originally patch
35, but it was incomplete because it made !entry->writer true only for
non-partial requests but not entry->done_headers_queue.empty(). Basically, in
case of partial , since any request can have write mode bit set irrespective of
whether there is a writer or not or whether there is a done_headers_queue
transaction or not.

Responding to the high level question here as well, my intention here was to
make these assertions as CHECKs permanently since these are important invariants
of the code and if they ever break in production , they should be easy to see
from the backtrace. I did find a few more CHECK assertions in net/. Let me know
if that's a concern.

[Randy Smith (Not in Mondays), 2017/05/10 21:34:26]

Gotcha; that makes sense.
Hmmm.  I don't think of that as the normal idiom.  I think of CHECKs being in
production code in two cases: a) We're doing a run against canary to figure out
where a particular failure is really happening, and b) the consequences of the
CHECK not being there and the code continuing to execute are clearly so bad that
it's better for the end user that the browser crash than that we blow through
the CHECK.  I don't think either applies here.  

I don't claim to be a complete authority on this issue--if you wanted to run it
by Matt, I'd happily accept his override.  But my call would be that these
CHECKs shouldn't be in on a long-term basis.

[shivanisha, 2017/05/11 19:58:24]

a) is true because speculatively most of canary crashes were because of these
assertions not being true and I would like to see if that's the case. In case
the crashes are still there with these CHECKs, that would lead to a better
investigation.
b) seems true because these checks assert that both the HC::T and entry are on
the same page. If not, that is bad for the code to proceed.

But I am also alright with adding a TODO to remove them eventually.

[Randy Smith (Not in Mondays), 2017/05/11 21:47:09]

I'm perfectly happy with you having CHECKs in to help diagnose canary crashes as
long as there's a bug-linked TODO to remove them when the bug is fixed.
We differ here.  It's a matter of relative badness--yes, the code proceeding
could result in ugly stuff happening.  But crashing will *definitely* result in
ugly stuff happening.  And once things are in the field, the user experience is
(IMO) the right metric.  So you have to believe that proceeding makes it likely
that, from the user's perspective, something worse than a browser crash will
occur before a CHECK() is appropriate.  There isn't a lot worse from the user's
perspective than a browser crash.

Another way to think of it is that, if you have a CHECK in the code and you push
it to stable, then you're using that CHECK() as an error handling mechanism, and
it's actually a pretty user-unfriendly error handling mechanism.  That doesn't
mean it's always wrong--if something is really unlikely it may not be worth the
effort to put in more user friendly error handling, and if something is really
bad it may be worth crashing the browser rather than letting it happen.  But for
me "really bad" means "Will expose cookies to untrusted third parties" or "may
create a security vulnerability allowing system perversion", not "Might crash
later because data structures get inconsistent".

But as I say, I don't consider myself perfectly grounded in what our guidelines
are in this space.  But if you want to go with consulting with just me, put in a
bug-linked TODO and put them back to DCHECKs after canary is clean.

[jkarlin, 2017/05/16 17:25:52]

The style guide makes the usage of CHECKS clear:

Use CHECK() if the consequence of a failed assertion would be a security
vulnerability, where crashing the browser is preferable. Because this takes down
the whole browser, sometimes there are better options than CHECK(). For example,
if a renderer sends the browser process a malformed IPC, an attacker may control
the renderer, but we can simply kill the offending renderer instead of crashing
the whole browser.

You can temporarily use CHECK() instead of DCHECK() when trying to force crashes
in release builds to sniff out which of your assertions is failing. Don‘t leave
these in the codebase forever; remove them or change them back once you’ve
solved the problem.

+
+    if (!entry->writer) {
+      entry->writer = transaction;
+      ProcessQueuedTransactions(entry);
+      return OK;
     }
-  } else {
-    // transaction needs read access to the entry
-    entry->readers.insert(trans);
-  }
-
-  // We do this before calling EntryAvailable to force any further calls to
-  // AddTransactionToEntry to add their transaction to the pending queue, which
-  // ensures FIFO ordering.
-  if (!entry->writer && !entry->pending_queue.empty())
-    ProcessPendingQueue(entry);
-
-  return OK;
-}
-
-void HttpCache::DoneWithEntry(ActiveEntry* entry, Transaction* trans,
-                              bool cancel) {
-  // If we already posted a task to move on to the next transaction and this was
-  // the writer, there is nothing to cancel.
-  if (entry->will_process_pending_queue && entry->readers.empty())
-    return;
-
-  if (entry->writer) {
-    DCHECK(trans == entry->writer);
-
+  }
+
+  // If this is not the first transaction in done_headers_queue, it should be a
+  // read-mode transaction except if it is a partial request.
+  CHECK(is_partial || (entry->done_headers_queue.empty() ||
+                       !(transaction->mode() & Transaction::WRITE)));
+
+  entry->done_headers_queue.push_back(transaction);
+  ProcessQueuedTransactions(entry);
+  return ERR_IO_PENDING;
+}
+
+void HttpCache::DoneWithEntry(ActiveEntry* entry,
+                              Transaction* transaction,
+                              bool process_cancel,
+                              bool is_partial) {
+  bool cancel = false;
+  if (process_cancel) {
+    cancel = IsTransactionExclusivelyWriting(entry, transaction, is_partial);
+    if (cancel && is_partial)
+      entry->disk_entry->CancelSparseIO();
+  }
+
+  // Transaction is waiting in the done_headers_queue.
+  auto it = std::find(entry->done_headers_queue.begin(),
+                      entry->done_headers_queue.end(), transaction);
+  if (it != entry->done_headers_queue.end()) {
+    entry->done_headers_queue.erase(it);
+    if (cancel)
+      ProcessEntryFailure(entry);
+    return;
+  }
+
+  // Transaction is removed in the headers phase.
+  if (transaction == entry->headers_transaction) {
+    // If the response is not written (cancel is true), consider it a failure.
+    DoneWritingToEntry(entry, !cancel, transaction);
+    return;
+  }
+
+  // Transaction is removed in the writing phase.
+  if (transaction == entry->writer) {
     // Assume there was a failure.
     bool success = false;
     if (cancel) {
       DCHECK(entry->disk_entry);
       // This is a successful operation in the sense that we want to keep the
       // entry.
-      success = trans->AddTruncatedFlag();
+      success = transaction->AddTruncatedFlag();
       // The previous operation may have deleted the entry.
-      if (!trans->entry())
+      if (!transaction->entry())
         return;
     }
-    DoneWritingToEntry(entry, success);
+    DoneWritingToEntry(entry, success, transaction);
+    return;
+  }
+
+  // Transaction is reading from the entry.
+  DoneReadingFromEntry(entry, transaction);
+}
+
+void HttpCache::DoneWritingToEntry(ActiveEntry* entry,
+                                   bool success,
+                                   Transaction* transaction) {
+  DCHECK(transaction == entry->writer ||
+         transaction == entry->headers_transaction);
+
+  if (transaction == entry->writer)
+    entry->writer = nullptr;
+  else
+    entry->headers_transaction = nullptr;
+
+  // If writer fails, restart the headers_transaction by setting its state.
+  // Since the headers_transactions is awaiting an asynchronous operation
+  // completion, when it's IO callback is invoked, it will be restarted.
+  if (!success && entry->headers_transaction) {
+    entry->headers_transaction->SetValidatingCannotProceed();
+    entry->headers_transaction = nullptr;
+    DCHECK(entry->HasNoActiveTransactions());
+  }
+  if (!success)
+    ProcessEntryFailure(entry);
+  else
+    ProcessQueuedTransactions(entry);
+}
+
+void HttpCache::DoneReadingFromEntry(ActiveEntry* entry,
+                                     Transaction* transaction) {
+  DCHECK(!entry->writer);
+  auto it = entry->readers.find(transaction);
+  DCHECK(it != entry->readers.end());
+  entry->readers.erase(it);
+
+  ProcessQueuedTransactions(entry);
+}
+
+void HttpCache::RemoveAllQueuedTransactions(ActiveEntry* entry,
+                                            TransactionList* list) {
+  // Process done_headers_queue before add_to_entry_queue to maintain FIFO
+  // order.
+  for (auto* transaction : entry->done_headers_queue)
+    list->push_back(transaction);
+  entry->done_headers_queue.clear();
+
+  for (auto* transaction : entry->add_to_entry_queue)
+    list->push_back(transaction);
+  entry->add_to_entry_queue.clear();
+}
+
+void HttpCache::ProcessEntryFailure(ActiveEntry* entry) {
+  // Failure case is either writer failing to completely write the response to
+  // the cache or validating transaction received a non-304 response.
+  TransactionList list;
+  if (entry->HasNoActiveTransactions() &&
+      !entry->will_process_queued_transactions) {
+    entry->disk_entry->Doom();
+    RemoveAllQueuedTransactions(entry, &list);
+    DestroyEntry(entry);
   } else {
-    DoneReadingFromEntry(entry, trans);
-  }
-}
-
-void HttpCache::DoneWritingToEntry(ActiveEntry* entry, bool success) {
-  DCHECK(entry->readers.empty());
-
-  entry->writer = NULL;
-
-  if (success) {
-    ProcessPendingQueue(entry);
+    DoomActiveEntry(entry->disk_entry->GetKey());
+    RemoveAllQueuedTransactions(entry, &list);
+  }
+  // ERR_CACHE_RACE causes the transaction to restart the whole process.
+  for (auto* transaction : list)
+    transaction->io_callback().Run(net::ERR_CACHE_RACE);
+}
+
+void HttpCache::ProcessQueuedTransactions(ActiveEntry* entry) {
+  // Multiple readers may finish with an entry at once, so we want to batch up
+  // calls to OnProcessQueuedTransactions. This flag also tells us that we
+  // should not delete the entry before OnProcessQueuedTransactions runs.
+  if (entry->will_process_queued_transactions)
+    return;
+
+  entry->will_process_queued_transactions = true;
+
+  // Post a task instead of invoking the io callback of another transaction here
+  // to avoid re-entrancy.
+  base::ThreadTaskRunnerHandle::Get()->PostTask(
+      FROM_HERE,
+      base::Bind(&HttpCache::OnProcessQueuedTransactions, GetWeakPtr(), entry));
+}
+
+void HttpCache::ProcessAddToEntryQueue(ActiveEntry* entry) {
+  DCHECK(!entry->add_to_entry_queue.empty());
+
+  // Note the entry may be new or may already have a response body written to
+  // it. In both cases, a transaction needs to wait since only one transaction
+  // can be in the headers phase at a time.
+  if (entry->headers_transaction) {
+    return;
+  }
+  Transaction* transaction = entry->add_to_entry_queue.front();
+  entry->add_to_entry_queue.erase(entry->add_to_entry_queue.begin());
+  entry->headers_transaction = transaction;
+
+  transaction->io_callback().Run(OK);
+}
+
+void HttpCache::ProcessDoneHeadersQueue(ActiveEntry* entry) {
+  DCHECK(!entry->writer);
+  DCHECK(!entry->done_headers_queue.empty());
+
+  Transaction* transaction = entry->done_headers_queue.front();
+
+  // If this transaction is responsible for writing the response body.
+  if (transaction->mode() & Transaction::WRITE) {
+    entry->writer = transaction;
   } else {
-    DCHECK(!entry->will_process_pending_queue);
-
-    // We failed to create this entry.
-    TransactionList pending_queue;
-    pending_queue.swap(entry->pending_queue);
-
-    entry->disk_entry->Doom();
-    DestroyEntry(entry);
-
-    // We need to do something about these pending entries, which now need to
-    // be added to a new entry.
-    while (!pending_queue.empty()) {
-      // ERR_CACHE_RACE causes the transaction to restart the whole process.
-      pending_queue.front()->io_callback().Run(ERR_CACHE_RACE);
-      pending_queue.pop_front();
-    }
-  }
-}
-
-void HttpCache::DoneReadingFromEntry(ActiveEntry* entry, Transaction* trans) {
-  DCHECK(!entry->writer);
-
-  auto it = entry->readers.find(trans);
-  DCHECK(it != entry->readers.end());
-
-  entry->readers.erase(it);
-
-  ProcessPendingQueue(entry);
-}
-
-void HttpCache::ConvertWriterToReader(ActiveEntry* entry) {
-  DCHECK(entry->writer);
-  DCHECK(entry->writer->mode() == Transaction::READ_WRITE);
-  DCHECK(entry->readers.empty());
-
-  Transaction* trans = entry->writer;
-
-  entry->writer = NULL;
-  entry->readers.insert(trans);
-
-  ProcessPendingQueue(entry);
+    // If a transaction is in front of this queue with only read mode set and
+    // there is no writer, it implies response body is already written, convert
+    // to a reader.
+    auto return_val = entry->readers.insert(transaction);
+    DCHECK_EQ(return_val.second, true);
+  }
+
+  // Post another task to give a chance to more transactions to either join
+  // readers or another transaction to start parallel validation.
+  ProcessQueuedTransactions(entry);
+
+  entry->done_headers_queue.erase(entry->done_headers_queue.begin());
+  transaction->io_callback().Run(OK);
+}
+
+bool HttpCache::CanTransactionWriteResponseHeaders(ActiveEntry* entry,
+                                                   Transaction* transaction,
+                                                   bool is_match) const {
+  if (transaction != entry->headers_transaction)
+    return false;
+
+  if (!(transaction->mode() & Transaction::WRITE))
+    return false;
+
+  // If its not a match then check if it is the transaction responsible for
+  // writing the response body.
+  if (!is_match) {
+    return !entry->writer && entry->done_headers_queue.empty() &&
+           entry->readers.empty();
+  }
+
+  return true;
+}
+
+bool HttpCache::IsTransactionExclusivelyWriting(ActiveEntry* entry,
+                                                Transaction* transaction,
+                                                bool is_partial) const {
+  if (transaction == entry->writer)
+    return true;
+
+  if (transaction->method() == "HEAD" || transaction->method() == "DELETE")
+    return false;
+
+  // Check if transaction is about to start writing to the cache.
+
+  // Transaction's mode may have been set to NONE if StopCaching was invoked.
+  if (!(transaction->mode() & Transaction::WRITE ||
+        transaction->mode() == Transaction::NONE)) {
+    return false;
+  }
+
+  if (!is_partial) {
+    // If a transaction is completing headers or done with headers phase with
+    // write mode then it should be the future writer. Just checking the front
+    // of done_headers_queue since the rest should anyways be READ mode
+    // transactions as they would be a result of validation match (for non-range
+    // requests).
+    return transaction == entry->headers_transaction ||
+           transaction == entry->done_headers_queue.front();
+  }
+
+  // Range requests specific cases.
+
+  // For range requests, it is possible to have WRITE mode set even if another
+  // transaction is the writer.
+  if (entry->writer)
+    return false;
+
+  if (transaction == entry->headers_transaction ||
+      transaction == entry->done_headers_queue.front()) {
+    return true;
+  }
+
+  // If transaction is not in front of done_headers_queue, see if its the first
+  // writer transaction in the queue.
+  for (auto* done_headers : entry->done_headers_queue) {
+    if (transaction == done_headers)
+      return true;
+    if (done_headers->mode() & Transaction::WRITE)
+      return false;
+  }
+
+  return false;
+}
+
+bool HttpCache::IsWritingInProgress(ActiveEntry* entry) const {
+  return entry->writer != nullptr;
 }
 
 LoadState HttpCache::GetLoadStateForPendingTransaction(
       const Transaction* trans) {
   auto i = active_entries_.find(trans->key());
   if (i == active_entries_.end()) {
     // If this is really a pending transaction, and it is not part of
     // active_entries_, we should be creating the backend or the entry.
     return LOAD_STATE_WAITING_FOR_CACHE;
   }
@@ skipping 29 matching lines @@
 
   for (auto k = doomed_entries_.begin(); k != doomed_entries_.end() && !found;
        ++k) {
     found = RemovePendingTransactionFromEntry(k->first, trans);
   }
 
   DCHECK(found) << "Pending transaction not found";
 }
 
 bool HttpCache::RemovePendingTransactionFromEntry(ActiveEntry* entry,
-                                                  Transaction* trans) {
-  TransactionList& pending_queue = entry->pending_queue;
+                                                  Transaction* transaction) {
+  TransactionList& add_to_entry_queue = entry->add_to_entry_queue;
 
-  auto j = find(pending_queue.begin(), pending_queue.end(), trans);
-  if (j == pending_queue.end())
+  auto j =
+      find(add_to_entry_queue.begin(), add_to_entry_queue.end(), transaction);
+  if (j == add_to_entry_queue.end())
     return false;
 
-  pending_queue.erase(j);
+  add_to_entry_queue.erase(j);
   return true;
 }
 
 bool HttpCache::RemovePendingTransactionFromPendingOp(PendingOp* pending_op,
                                                       Transaction* trans) {
   if (pending_op->writer->Matches(trans)) {
     pending_op->writer->ClearTransaction();
     pending_op->writer->ClearEntry();
     return true;
   }
   WorkItemList& pending_queue = pending_op->pending_queue;
 
   for (auto it = pending_queue.begin(); it != pending_queue.end(); ++it) {
     if ((*it)->Matches(trans)) {
       pending_queue.erase(it);
       return true;
     }
   }
   return false;
 }
 
-void HttpCache::ProcessPendingQueue(ActiveEntry* entry) {
-  // Multiple readers may finish with an entry at once, so we want to batch up
-  // calls to OnProcessPendingQueue.  This flag also tells us that we should
-  // not delete the entry before OnProcessPendingQueue runs.
-  if (entry->will_process_pending_queue)
-    return;
-  entry->will_process_pending_queue = true;
+void HttpCache::OnProcessQueuedTransactions(ActiveEntry* entry) {
+  entry->will_process_queued_transactions = false;
 
-  base::ThreadTaskRunnerHandle::Get()->PostTask(
-      FROM_HERE,
-      base::Bind(&HttpCache::OnProcessPendingQueue, GetWeakPtr(), entry));
-}
-
-void HttpCache::OnProcessPendingQueue(ActiveEntry* entry) {
-  entry->will_process_pending_queue = false;
-  DCHECK(!entry->writer);
+  // Note that this function should only invoke one transaction's IO callback
+  // since its possible for IO callbacks' consumers to destroy the cache/entry.
 
   // If no one is interested in this entry, then we can deactivate it.
   if (entry->HasNoTransactions()) {
     DestroyEntry(entry);
     return;
   }
 
-  if (entry->pending_queue.empty())
+  if (entry->done_headers_queue.empty() && entry->add_to_entry_queue.empty())
     return;
 
-  // Promote next transaction from the pending queue.
-  Transaction* next = entry->pending_queue.front();
-  if ((next->mode() & Transaction::WRITE) && !entry->readers.empty())
-    return;  // Have to wait.
+  // To maintain FIFO order of transactions, done_headers_queue should be
+  // checked for processing before add_to_entry_queue.
 
-  entry->pending_queue.erase(entry->pending_queue.begin());
+  // If another transaction is writing the response, let validated transactions
+  // wait till the response is complete. If the response is not yet started, the
+  // done_headers_queue transaction should start writing it.
+  if (!entry->writer && !entry->done_headers_queue.empty()) {
+    ProcessDoneHeadersQueue(entry);
+    return;
+  }
 
-  int rv = AddTransactionToEntry(entry, next);
-  if (rv != ERR_IO_PENDING) {
-    next->io_callback().Run(rv);
-  }
+  if (!entry->add_to_entry_queue.empty())
+    ProcessAddToEntryQueue(entry);
 }
 
 void HttpCache::OnIOComplete(int result, PendingOp* pending_op) {
   WorkItemOperation op = pending_op->writer->operation();
 
   // Completing the creation of the backend is simpler than the other cases.
   if (op == WI_CREATE_BACKEND)
     return OnBackendCreated(result, pending_op);
 
   std::unique_ptr<WorkItem> item = std::move(pending_op->writer);
@@ skipping 126 matching lines @@
     building_backend_ = false;
     DeletePendingOp(pending_op);
   }
 
   // The cache may be gone when we return from the callback.
   if (!item->DoCallback(result, disk_cache_.get()))
     item->NotifyTransaction(result, NULL);
 }
 
 }  // namespace net