HttpCache::Transaction layer allowing parallel validation

net/http/http_cache_transaction.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_transaction.h"
 
 #include "build/build_config.h"  // For OS_POSIX
 
 #if defined(OS_POSIX)
 #include <unistd.h>
@@ skipping 163 matching lines @@
       truncated_(false),
       is_sparse_(false),
       range_requested_(false),
       handling_206_(false),
       cache_pending_(false),
       done_reading_(false),
       vary_mismatch_(false),
       couldnt_conditionalize_request_(false),
       bypass_lock_for_test_(false),
       fail_conditionalization_for_test_(false),
+      write_this_response_(false),
       io_buf_len_(0),
       read_offset_(0),
       effective_load_flags_(0),
       write_len_(0),
       cache_entry_status_(CacheEntryStatus::ENTRY_UNDEFINED),
       validation_cause_(VALIDATION_CAUSE_UNDEFINED),
       total_received_bytes_(0),
       total_sent_bytes_(0),
       websocket_handshake_stream_base_create_helper_(NULL),
       weak_factory_(this) {
@@ skipping 399 matching lines @@
 //   CacheWriteResponse* -> TruncateCachedData* -> TruncateCachedMetadata* ->
 //   PartialHeadersReceived
 //
 //   Read():
 //   NetworkRead* -> CacheWriteData*
 //
 // 2. Cached entry, no validation:
 //   Start():
 //   GetBackend* -> InitEntry -> OpenEntry* -> AddToEntry* -> CacheReadResponse*
 //   -> CacheDispatchValidation -> BeginPartialCacheValidation() ->
-//   BeginCacheValidation() -> SetupEntryForRead()
+//   BeginCacheValidation() -> SetupEntryForRead() -> WaitBeforeRead*
 //
 //   Read():
 //   CacheReadData*
 //
 // 3. Cached entry, validation (304):
 //   Start():
 //   GetBackend* -> InitEntry -> OpenEntry* -> AddToEntry* -> CacheReadResponse*
 //   -> CacheDispatchValidation -> BeginPartialCacheValidation() ->
 //   BeginCacheValidation() -> SendRequest* -> SuccessfulSendRequest ->
 //   UpdateCachedResponse -> CacheWriteUpdatedResponse* ->
 //   UpdateCachedResponseComplete -> OverwriteCachedResponse ->
-//   PartialHeadersReceived
+//   PartialHeadersReceived -> WaitBeforeRead*
 //
 //   Read():
 //   CacheReadData*
 //
 // 4. Cached entry, validation and replace (200):
 //   Start():
 //   GetBackend* -> InitEntry -> OpenEntry* -> AddToEntry* -> CacheReadResponse*
 //   -> CacheDispatchValidation -> BeginPartialCacheValidation() ->
 //   BeginCacheValidation() -> SendRequest* -> SuccessfulSendRequest ->
 //   OverwriteCachedResponse -> CacheWriteResponse* -> DoTruncateCachedData* ->
@@ skipping 79 matching lines @@
 //   BeginPartialCacheValidation() -> BeginCacheValidation() ->
 //   SetupEntryForRead()
 //
 //   Read():
 //   CacheReadData*
 //
 // 14. Cached entry more than 5 minutes old, unused_since_prefetch is true:
 //   Like examples 2-4, only CacheToggleUnusedSincePrefetch* is inserted between
 //   CacheReadResponse* and CacheDispatchValidation.
 int HttpCache::Transaction::DoLoop(int result) {
+  int rv = DoLoopImpl(result);
+
+  // If its the end of the Start() state machine, the transaction might have to
+  // wait before it can read from the cache if there is another transaction
+  // writing to the cache currently. This is being done to enable parallelizing
+  // the validation phase of a transaction while another transaction is still
+  // writing the response to the cache.
+  // Checking reading_ will make sure that we do not enter the wait state for
+  // partial requests that have already started reading and re-entered the
+  // start() state machine.
+  if (!reading_ && rv == OK) {

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

How many ways can we get here? Can we just call 'return WaitBeforeRead()' which
either returns OK or sets the next state to STATE_WAIT_BEFORE_READ from the
necessary locations?

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

There are a lot of conditional paths that can lead to the end of Start() state
machine, some of them being: all the places where SetUpEntryForRead,
ConvertWriterToReader and PartialHeadersReceived is invoked. Instead of taking
care of all of them and remembering to do it whenever a code change impacting
that is done, its better to detach it from the "start" state machine and treat
it as a separate "wait" state machine. I started out following the former
approach but encountered a lot of failing tests while putting it here
significantly simplified the design conceptually as well as in the
implementation.
It also means there does not need to be any careful ordering between calling
this function and doing other things with the entry like doom/call
DoneWithEntry, this always gets called after everything else required by the
particular control flow is already done with the entry.

+    next_state_ = STATE_WAIT_BEFORE_READ;
+    rv = DoLoopImpl(rv);
+  }
+
+  if (rv != ERR_IO_PENDING && !callback_.is_null()) {
+    read_buf_ = NULL;  // Release the buffer before invoking the callback.

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

s/NULL/nullptr/

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

done

+    base::ResetAndReturn(&callback_).Run(rv);
+  }
+
+  return rv;
+}
+
+int HttpCache::Transaction::DoLoopImpl(int result) {
   DCHECK(next_state_ != STATE_NONE);
 
   int rv = result;
   do {
     State state = next_state_;
     next_state_ = STATE_NONE;
     switch (state) {
       case STATE_GET_BACKEND:
         DCHECK_EQ(OK, rv);
         rv = DoGetBackend();
@@ skipping 119 matching lines @@
         DCHECK_EQ(OK, rv);
         rv = DoPartialHeadersReceived();
         break;
       case STATE_CACHE_READ_METADATA:
         DCHECK_EQ(OK, rv);
         rv = DoCacheReadMetadata();
         break;
       case STATE_CACHE_READ_METADATA_COMPLETE:
         rv = DoCacheReadMetadataComplete(rv);
         break;
+      case STATE_WAIT_BEFORE_READ:
+        DCHECK_EQ(OK, rv);
+        rv = DoWaitBeforeRead();
+        break;
+      case STATE_WAIT_BEFORE_READ_COMPLETE:
+        rv = DoWaitBeforeReadComplete(rv);
+        break;
       case STATE_NETWORK_READ:
         DCHECK_EQ(OK, rv);
         rv = DoNetworkRead();
         break;
       case STATE_NETWORK_READ_COMPLETE:
         rv = DoNetworkReadComplete(rv);
         break;
       case STATE_CACHE_READ_DATA:
         DCHECK_EQ(OK, rv);
         rv = DoCacheReadData();
@@ skipping 14 matching lines @@
       case STATE_CACHE_WRITE_TRUNCATED_RESPONSE_COMPLETE:
         rv = DoCacheWriteTruncatedResponseComplete(rv);
         break;
       default:
         NOTREACHED() << "bad state";
         rv = ERR_FAILED;
         break;
     }
   } while (rv != ERR_IO_PENDING && next_state_ != STATE_NONE);
 
-  if (rv != ERR_IO_PENDING && !callback_.is_null()) {
-    read_buf_ = NULL;  // Release the buffer before invoking the callback.
-    base::ResetAndReturn(&callback_).Run(rv);
-  }
-
   return rv;
 }
 
 int HttpCache::Transaction::DoGetBackend() {
   cache_pending_ = true;
   next_state_ = STATE_GET_BACKEND_COMPLETE;
   net_log_.BeginEvent(NetLogEventType::HTTP_CACHE_GET_BACKEND);
   return cache_->GetBackendForTransaction(this);
 }
 
@@ skipping 587 matching lines @@
     UpdateCacheEntryStatus(CacheEntryStatus::ENTRY_NOT_IN_CACHE);
   }
 
   // Invalidate any cached GET with a successful PUT or DELETE.
   if (mode_ == WRITE &&
       (request_->method == "PUT" || request_->method == "DELETE")) {
     if (NonErrorResponse(new_response->headers->response_code())) {
       int ret = cache_->DoomEntry(cache_key_, NULL);
       DCHECK_EQ(OK, ret);
     }
-    cache_->DoneWritingToEntry(entry_, true);
+    cache_->DoneWritingToEntry(entry_, true, this);
     entry_ = NULL;
     mode_ = NONE;
   }
 
   // Invalidate any cached GET with a successful POST.
   if (!(effective_load_flags_ & LOAD_DISABLE_CACHE) &&
       request_->method == "POST" &&
       NonErrorResponse(new_response->headers->response_code())) {
     cache_->DoomMainEntryForUrl(request_->url);
   }
@@ skipping 12 matching lines @@
     if (new_response->headers->response_code() == 304 || handling_206_) {
       UpdateCacheEntryStatus(CacheEntryStatus::ENTRY_VALIDATED);
       next_state_ = STATE_UPDATE_CACHED_RESPONSE;
       return OK;
     }
     UpdateCacheEntryStatus(CacheEntryStatus::ENTRY_UPDATED);
     mode_ = WRITE;
   }
 
   next_state_ = STATE_OVERWRITE_CACHED_RESPONSE;
+
+  if (!entry_)
+    return OK;
+
+  if (entry_->writer == this && request_->method != "HEAD") {
+    write_this_response_ = true;
+    return OK;
+  }
+
+  // Invalidate any current entry with a successful response.
+  if (new_response->headers->response_code() != 304) {
+    DCHECK_EQ(entry_->validating_transaction, this);
+    cache_->OnValidationNoMatch(entry_, this);
+    entry_ = nullptr;
+    mode_ = NONE;
+    return OK;
+  }
+
   return OK;
 }
 
 // We received 304 or 206 and we want to update the cached response headers.
 int HttpCache::Transaction::DoUpdateCachedResponse() {
   TRACE_EVENT0("io", "HttpCacheTransaction::DoUpdateCachedResponse");
   next_state_ = STATE_UPDATE_CACHED_RESPONSE_COMPLETE;
   int rv = OK;
   // Update the cached response based on the headers and properties of
   // new_response_.
@@ skipping 49 matching lines @@
     DCHECK(!handling_206_);
     // We got a "not modified" response and already updated the corresponding
     // cache entry above.
     //
     // By closing the cached entry now, we make sure that the 304 rather than
     // the cached 200 response, is what will be returned to the user.
     DoneWritingToEntry(true);
   } else if (entry_ && !handling_206_) {
     DCHECK_EQ(READ_WRITE, mode_);
     if (!partial_ || partial_->IsLastRange()) {
-      cache_->ConvertWriterToReader(entry_);
-      mode_ = READ;
+      if (cache_->ConvertWriterToReader(entry_, this))
+        mode_ = READ;
     }
     // We no longer need the network transaction, so destroy it.
     ResetNetworkTransaction();
   } else if (entry_ && handling_206_ && truncated_ &&
              partial_->initial_validation()) {
     // We just finished the validation of a truncated entry, and the server
     // is willing to resume the operation. Now we go back and start serving
     // the first part to the user.
     ResetNetworkTransaction();
     new_response_ = NULL;
@@ skipping 115 matching lines @@
       next_state_ = STATE_CACHE_READ_DATA;
     }
   } else if (mode_ != NONE) {
     // We are about to return the headers for a byte-range request to the user,
     // so let's fix them.
     partial_->FixResponseHeaders(response_.headers.get(), true);
   }
   return OK;
 }
 
+int HttpCache::Transaction::DoWaitBeforeRead() {
+  if (!entry_)
+    return OK;
+
+  next_state_ = STATE_WAIT_BEFORE_READ_COMPLETE;
+
+  // If this is the writer, give chance to another transaction to start
+  // validation.
+  if (write_this_response_) {

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

Seems clearer to call entry_->writer == this && request_->method != "HEAD" here

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

Apart from the conditions entry_->writer == this && request_->method != "HEAD",
its also where we are in the state machine (state
STATE_OVERWRITE_CACHED_RESPONSE) that matters. Removed write_this_response_
though as part of refactoring OnValidationMatch. Now I am calling a new function
DoneValidationWriteEntry at the point where write_this_response_ was set to true
and just returning from here if this transaction is the writer.

+    cache_->OnValidationMatch(entry_, this, true);

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

OnValidationMatch(entry_, this, true /* write_this_response */);

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

N/A after the code refactoring of OnValidationMatch.

+    return OK;
+  }
+
+  // If the transaction was converted to a reader but not in readers yet, then
+  // it must be added to the queue.
+  bool should_wait = false;
+  if (entry_->writer != this && entry_->validating_transaction != this &&
+      !entry_->IsReader(this))
+    should_wait = true;
+
+  // Notify cache_ about completed validation so that another transaction can
+  // start validation.
+  if (entry_->validating_transaction == this && response_.headers &&
+      response_.headers->response_code() == 304)
+    should_wait = true;
+
+  if (should_wait)
+    return cache_->OnValidationMatch(entry_, this, false);

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

OnValidationMatch(entry_, this, false /* write_this_response */);

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

N/A after the code refactoring of OnValidationMatch.

+
+  return OK;
+}
+
+int HttpCache::Transaction::DoWaitBeforeReadComplete(int rv) {
+  if (rv == ERR_CACHE_RACE) {
+    next_state_ = STATE_INIT_ENTRY;
+    cache_entry_status_ = CacheEntryStatus::ENTRY_UNDEFINED;
+    entry_ = nullptr;
+    return OK;
+  }
+
+  if (rv != OK)
+    return rv;
+
+  // If successful then this must be either be the writer or a reader as the
+  // response must have completely been written to the cache.
+  if (entry_->writer == this)
+    return OK;
+
+  mode_ = READ;

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

I'd have thought that the existing code would have already marked this
transaction as a reader if the validation matched. It looks like
SetupEntryForRead does. But perhaps the 304 path does not? Should it? If so,
then we can just DCHECK the mode here.

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

Simplified DoWaitBeforeRead to not have an additional 304 case since
ConvertWriterToReader() gets called for all cases where validation is a match.
(I am still looking in the case when couldnt_conditionalize_request_ is set to
true. I just want to make sure that if couldnt_conditionalize_request_ is set
then we never have a validation match case)

We cannot set the mode_ as READ when ConvertWriterToReader() gets called and
could not add it as the reader because we need to retain the original mode until
we are sure that the response data was written completely to the cache. If not ,
this transaction will be restarted and it will need to have its original mode
then.

+  if (network_trans_)
+    ResetNetworkTransaction();

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

Likewise, shouldn't this be taken care of already?

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

I am looking into this. I am not sure if the couldnt_conditionalize_request_
case is handled.

+  return OK;
+}
+
 int HttpCache::Transaction::DoCacheReadMetadata() {
   TRACE_EVENT0("io", "HttpCacheTransaction::DoCacheReadMetadata");
   DCHECK(entry_);
   DCHECK(!response_.metadata.get());
   next_state_ = STATE_CACHE_READ_METADATA_COMPLETE;
 
   response_.metadata =
       new IOBufferWithSize(entry_->disk_entry->GetDataSize(kMetadataIndex));
 
   net_log_.BeginEvent(NetLogEventType::HTTP_CACHE_READ_INFO);
@@ skipping 809 matching lines @@
   if (partial_) {
     if (truncated_ || is_sparse_ || !invalid_range_) {
       // We are going to return the saved response headers to the caller, so
       // we may need to adjust them first.
       next_state_ = STATE_PARTIAL_HEADERS_RECEIVED;
       return OK;
     } else {
       partial_.reset();
     }
   }
-  cache_->ConvertWriterToReader(entry_);
-  mode_ = READ;
+
+  // This might or might not be able to add it as an active reader based on
+  // whether this is the active writer or not. If not, it will be added to a
+  // wait queue in DoWaitBeforeRead.
+  if (cache_->ConvertWriterToReader(entry_, this))

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

I see, this is why we had to change mode_ = READ in DoWaitBeforeReadComplete.

Perhaps we can set mode_ = READ reagardless?

Also, ConvertWriterToReader now handles cases where the current transaction
isn't actually a writer. Perhaps we should be calling a different function if
it's not the writer?

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

Simplified ConvertWriterToReader so it doesn't do anything if the current
transaction isn't actually a writer because everything needed to be done will be
done in DoWaitBeforeRead.

+    mode_ = READ;
 
   if (request_->method == "HEAD")
     FixHeadersForHead();
 
   if (entry_->disk_entry->GetDataSize(kMetadataIndex))
     next_state_ = STATE_CACHE_READ_METADATA;
   return OK;
 }
 
 int HttpCache::Transaction::WriteToEntry(int index, int offset,
@@ skipping 64 matching lines @@
   }
   return OK;
 }
 
 void HttpCache::Transaction::DoneWritingToEntry(bool success) {
   if (!entry_)
     return;
 
   RecordHistograms();
 
-  cache_->DoneWritingToEntry(entry_, success);
+  cache_->DoneWritingToEntry(entry_, success, this);
   entry_ = NULL;
   mode_ = NONE;  // switch to 'pass through' mode
 }
 
 int HttpCache::Transaction::OnCacheReadError(int result, bool restart) {
   DLOG(ERROR) << "ReadData failed: " << result;
   const int result_for_histogram = std::max(0, -result);
   if (restart) {
     UMA_HISTOGRAM_SPARSE_SLOWLY("HttpCache.ReadErrorRestartable",
                                 result_for_histogram);
@@ skipping 335 matching lines @@
     default:
       NOTREACHED();
   }
 }
 
 void HttpCache::Transaction::OnIOComplete(int result) {
   DoLoop(result);
 }
 
 }  // namespace net