update_engine: UM: Incorporate backoff logic in UpdateCanStart.

This change adds backoff computation logic to UpdateCanStart. For the
most part, it is extending a private policy call (UpdateDownloadUrl) to
account for previously enacted backoff periods and to compute new ones
when an update failure is identified (accordingly, it is now called
UpdateBackoffAndDownloadUrl).

To conform with the pure nature of policy implementations, yet
minimizing the amount of "state" that needs to be managed and persisted
by the updater, we now consider download errors in bulks defined by the
most recent update failure (namely, the point in time when all URLs
where tried and failed). The updater is expected to keep track of the
update failure count, setting it to zero when a new update is seen, and
incrementing it (and recording the time it was incremented) when told to
do so by the policy. We therefore make some adjustments to the policy
API and its usage semantics.

BUG=chromium:396148
TEST=Unit tests.

Change-Id: If8787b8c41055779945f9b41368ec08ac5e6fcca
Reviewed-on: https://chromium-review.googlesource.com/210702
Reviewed-by: Alex Vakulenko <avakulenko@chromium.org>
Tested-by: Gilad Arnold <garnold@chromium.org>
Reviewed-by: Alex Deymo <deymo@chromium.org>
Commit-Queue: Gilad Arnold <garnold@chromium.org>
diff --git a/update_manager/chromeos_policy.cc b/update_manager/chromeos_policy.cc
index fc39bd7..9afc00d 100644
--- a/update_manager/chromeos_policy.cc
+++ b/update_manager/chromeos_policy.cc
@@ -21,6 +21,7 @@
 using base::Time;
 using base::TimeDelta;
 using chromeos_update_engine::ErrorCode;
+using std::get;
 using std::max;
 using std::min;
 using std::set;
@@ -28,12 +29,13 @@
 
 namespace {
 
-// Increment |url_idx|, |url_num_failures| or none of them based on the provided
-// error code. If |url_idx| is incremented, then sets |url_num_failures| to zero
-// and returns true; otherwise, returns false.
+// Examines |err_code| and decides whether the URL index needs to be advanced,
+// the error count for the URL incremented, or none of the above. In the first
+// case, returns true; in the second case, increments |*url_num_error_p| and
+// returns false; otherwise just returns false.
 //
 // TODO(garnold) Adapted from PayloadState::UpdateFailed() (to be retired).
-bool HandleErrorCode(ErrorCode err_code, int* url_idx, int* url_num_failures) {
+bool HandleErrorCode(ErrorCode err_code, int* url_num_error_p) {
   err_code = chromeos_update_engine::utils::GetBaseErrorCode(err_code);
   switch (err_code) {
     // Errors which are good indicators of a problem with a particular URL or
@@ -64,8 +66,6 @@
       LOG(INFO) << "Advancing download URL due to error "
                 << chromeos_update_engine::utils::CodeToString(err_code)
                 << " (" << static_cast<int>(err_code) << ")";
-      *url_idx += 1;
-      *url_num_failures = 0;
       return true;
 
     // Errors which seem to be just transient network/communication related
@@ -84,7 +84,7 @@
       LOG(INFO) << "Incrementing URL failure count due to error "
                 << chromeos_update_engine::utils::CodeToString(err_code)
                 << " (" << static_cast<int>(err_code) << ")";
-      *url_num_failures += 1;
+      *url_num_error_p += 1;
       return false;
 
     // Errors which are not specific to a URL and hence shouldn't result in
@@ -141,9 +141,9 @@
   return false;
 }
 
-// Checks whether |download_url| can be used under given download restrictions.
-bool DownloadUrlIsUsable(const string& download_url, bool http_allowed) {
-  return http_allowed || !StartsWithASCII(download_url, "http://", false);
+// Checks whether |url| can be used under given download restrictions.
+bool IsUrlUsable(const string& url, bool http_allowed) {
+  return http_allowed || !StartsWithASCII(url, "http://", false);
 }
 
 }  // namespace
@@ -154,6 +154,8 @@
 const int ChromeOSPolicy::kTimeoutPeriodicInterval = 45 * 60;
 const int ChromeOSPolicy::kTimeoutMaxBackoffInterval = 4 * 60 * 60;
 const int ChromeOSPolicy::kTimeoutRegularFuzz = 10 * 60;
+const int ChromeOSPolicy::kAttemptBackoffMaxIntervalInDays = 16;
+const int ChromeOSPolicy::kAttemptBackoffFuzzInHours = 12;
 
 EvalStatus ChromeOSPolicy::UpdateCheckAllowed(
     EvaluationContext* ec, State* state, string* error,
@@ -265,16 +267,20 @@
     State* state,
     string* error,
     UpdateDownloadParams* result,
-    const bool interactive,
     const UpdateState& update_state) const {
-  // Set the default return values.
+  // Set the default return values. Note that we set persisted values (backoff,
+  // scattering) to the same values presented in the update state. The reason is
+  // that preemptive returns, such as the case where an update check is due,
+  // should not clear off the said values; rather, it is the deliberate
+  // inference of new values that should cause them to be reset.
   result->update_can_start = true;
-  result->p2p_allowed = false;
   result->cannot_start_reason = UpdateCannotStartReason::kUndefined;
-  result->scatter_wait_period = kZeroInterval;
-  result->scatter_check_threshold = 0;
   result->download_url_idx = -1;
-  result->download_url_num_failures = 0;
+  result->p2p_allowed = false;
+  result->do_increment_failures = false;
+  result->backoff_expiry = update_state.backoff_expiry;
+  result->scatter_wait_period = update_state.scatter_wait_period;
+  result->scatter_check_threshold = update_state.scatter_check_threshold;
 
   // Make sure that we're not due for an update check.
   UpdateCheckParams check_result;
@@ -288,6 +294,27 @@
     return EvalStatus::kSucceeded;
   }
 
+  // Check whether backoff applies, and if not then which URL can be used for
+  // downloading. These require scanning the download error log, and so they are
+  // done together.
+  UpdateBackoffAndDownloadUrlResult backoff_url_result;
+  EvalStatus backoff_url_status = UpdateBackoffAndDownloadUrl(
+      ec, state, error, &backoff_url_result, update_state);
+  if (backoff_url_status != EvalStatus::kFailed) {
+    result->download_url_idx = backoff_url_result.url_idx;
+    result->download_url_num_errors = backoff_url_result.url_num_errors;
+    result->do_increment_failures = backoff_url_result.do_increment_failures;
+    result->backoff_expiry = backoff_url_result.backoff_expiry;
+  }
+  if (backoff_url_status != EvalStatus::kSucceeded ||
+      !backoff_url_result.backoff_expiry.is_null()) {
+    if (backoff_url_status != EvalStatus::kFailed) {
+      result->update_can_start = false;
+      result->cannot_start_reason = UpdateCannotStartReason::kBackoff;
+    }
+    return backoff_url_status;
+  }
+
   DevicePolicyProvider* const dp_provider = state->device_policy_provider();
 
   const bool* device_policy_is_loaded_p = ec->GetValue(
@@ -302,7 +329,9 @@
     // presence of this attribute is merely indicative of an OOBE update, during
     // which we suppress scattering anyway.
     bool scattering_applies = false;
-    if (!interactive) {
+    result->scatter_wait_period = kZeroInterval;
+    result->scatter_check_threshold = 0;
+    if (!update_state.is_interactive) {
       const bool* is_oobe_enabled_p = ec->GetValue(
           state->config_provider()->var_is_oobe_enabled());
       if (is_oobe_enabled_p && !(*is_oobe_enabled_p)) {
@@ -344,21 +373,12 @@
     result->p2p_allowed = updater_p2p_enabled_p && *updater_p2p_enabled_p;
   }
 
-  // Determine the URL to download the update from. Note that a failure to find
-  // a download URL will only fail this policy iff no other means of download
-  // (such as P2P) are enabled.
-  UpdateDownloadUrlResult download_url_result;
-  EvalStatus download_url_status = UpdateDownloadUrl(
-      ec, state, error, &download_url_result, update_state);
-  if (download_url_status == EvalStatus::kSucceeded) {
-    result->download_url_idx = download_url_result.url_idx;
-    result->download_url_num_failures = download_url_result.url_num_failures;
-  } else if (!result->p2p_allowed) {
-    if (download_url_status != EvalStatus::kFailed) {
-      result->update_can_start = false;
-      result->cannot_start_reason = UpdateCannotStartReason::kCannotDownload;
-    }
-    return download_url_status;
+  // Store the download URL and failure increment flag. Note that no URL will
+  // only terminate evaluation if no other means of download (such as P2P) are
+  // enabled.
+  if (result->download_url_idx < 0 && !result->p2p_allowed) {
+    result->update_can_start = false;
+    result->cannot_start_reason = UpdateCannotStartReason::kCannotDownload;
   }
 
   return EvalStatus::kSucceeded;
@@ -537,29 +557,48 @@
   return TimeDelta::FromSeconds(prng->RandMinMax(interval_min, interval_max));
 }
 
-EvalStatus ChromeOSPolicy::UpdateDownloadUrl(
+EvalStatus ChromeOSPolicy::UpdateBackoffAndDownloadUrl(
     EvaluationContext* ec, State* state, std::string* error,
-    UpdateDownloadUrlResult* result, const UpdateState& update_state) const {
-  int url_idx = 0;
-  int url_num_failures = 0;
-  if (update_state.num_checks > 1) {
-    // Ignore negative URL indexes, which indicate that no previous suitable
-    // download URL was found.
-    url_idx = max(0, update_state.download_url_idx);
-    url_num_failures = update_state.download_url_num_failures;
+    UpdateBackoffAndDownloadUrlResult* result,
+    const UpdateState& update_state) const {
+  // Sanity checks.
+  DCHECK_GE(update_state.download_errors_max, 0);
+
+  // Set default result values.
+  result->do_increment_failures = false;
+  result->backoff_expiry = update_state.backoff_expiry;
+  result->url_idx = -1;
+  result->url_num_errors = 0;
+
+  const bool* is_official_build_p = ec->GetValue(
+      state->system_provider()->var_is_official_build());
+  bool is_official_build = (is_official_build_p ? *is_official_build_p : true);
+
+  // Check whether backoff is enabled.
+  bool may_backoff = false;
+  if (update_state.is_backoff_disabled) {
+    LOG(INFO) << "Backoff disabled by Omaha.";
+  } else if (update_state.is_interactive) {
+    LOG(INFO) << "No backoff for interactive updates.";
+  } else if (update_state.is_delta_payload) {
+    LOG(INFO) << "No backoff for delta payloads.";
+  } else if (!is_official_build) {
+    LOG(INFO) << "No backoff for unofficial builds.";
+  } else {
+    may_backoff = true;
   }
 
-  // Preconditions / sanity checks.
-  DCHECK_GE(update_state.download_failures_max, 0);
-  DCHECK_LT(url_idx, static_cast<int>(update_state.download_urls.size()));
-  DCHECK_LE(url_num_failures, update_state.download_failures_max);
+  // If previous backoff still in effect, block.
+  if (may_backoff && !update_state.backoff_expiry.is_null() &&
+      !ec->IsWallclockTimeGreaterThan(update_state.backoff_expiry)) {
+    LOG(INFO) << "Previous backoff has not expired, waiting.";
+    return EvalStatus::kAskMeAgainLater;
+  }
 
   // Determine whether HTTP downloads are forbidden by policy. This only
   // applies to official system builds; otherwise, HTTP is always enabled.
   bool http_allowed = true;
-  const bool* is_official_build_p = ec->GetValue(
-      state->system_provider()->var_is_official_build());
-  if (is_official_build_p && *is_official_build_p) {
+  if (is_official_build) {
     DevicePolicyProvider* const dp_provider = state->device_policy_provider();
     const bool* device_policy_is_loaded_p = ec->GetValue(
         dp_provider->var_device_policy_is_loaded());
@@ -571,30 +610,140 @@
     }
   }
 
-  // Process recent failures, stop if the URL index advances.
-  for (auto& err_code : update_state.download_url_error_codes) {
-    if (HandleErrorCode(err_code, &url_idx, &url_num_failures))
-      break;
-    if (url_num_failures > update_state.download_failures_max) {
-      url_idx++;
-      url_num_failures = 0;
-      break;
+  int url_idx = update_state.last_download_url_idx;
+  if (url_idx < 0)
+    url_idx = -1;
+  bool do_advance_url = false;
+  bool is_failure_occurred = false;
+  Time err_time;
+
+  // Scan the relevant part of the download error log, tracking which URLs are
+  // being used, and accounting the number of errors for each URL. Note that
+  // this process may not traverse all errors provided, as it may decide to bail
+  // out midway depending on the particular errors exhibited, the number of
+  // failures allowed, etc. When this ends, |url_idx| will point to the last URL
+  // used (-1 if starting fresh), |do_advance_url| will determine whether the
+  // URL needs to be advanced, and |err_time| the point in time when the last
+  // reported error occurred.  Additionally, if the error log indicates that an
+  // update attempt has failed (abnormal), then |is_failure_occurred| will be
+  // set to true.
+  const int num_urls = update_state.download_urls.size();
+  int prev_url_idx = -1;
+  int url_num_errors = update_state.last_download_url_num_errors;
+  Time prev_err_time;
+  bool is_first = true;
+  for (const auto& err_tuple : update_state.download_errors) {
+    // Do some sanity checks.
+    int used_url_idx = get<0>(err_tuple);
+    if (is_first && url_idx >= 0 && used_url_idx != url_idx) {
+      LOG(WARNING) << "First URL in error log (" << used_url_idx
+                   << ") not as expected (" << url_idx << ")";
     }
-  }
-  url_idx %= update_state.download_urls.size();
+    is_first = false;
+    url_idx = used_url_idx;
+    if (url_idx < 0 || url_idx >= num_urls) {
+      LOG(ERROR) << "Download error log contains an invalid URL index ("
+                 << url_idx << ")";
+      return EvalStatus::kFailed;
+    }
+    err_time = get<2>(err_tuple);
+    if (!(prev_err_time.is_null() || err_time >= prev_err_time)) {
+      // TODO(garnold) Monotonicity cannot really be assumed when dealing with
+      // wallclock-based timestamps. However, we're making a simplifying
+      // assumption so as to keep the policy implementation straightforward, for
+      // now. In general, we should convert all timestamp handling in the
+      // UpdateManager to use monotonic time (instead of wallclock), including
+      // the computation of various expiration times (backoff, scattering, etc).
+      // The client will do whatever conversions necessary when
+      // persisting/retrieving these values across reboots. See chromium:408794.
+      LOG(ERROR) << "Download error timestamps not monotonically increasing.";
+      return EvalStatus::kFailed;
+    }
+    prev_err_time = err_time;
 
-  // Scan through URLs until a usable one is found.
-  const int start_url_idx = url_idx;
-  while (!DownloadUrlIsUsable(update_state.download_urls[url_idx],
-                              http_allowed)) {
-    url_idx = (url_idx + 1) % update_state.download_urls.size();
-    url_num_failures = 0;
-    if (url_idx == start_url_idx)
-      return EvalStatus::kFailed;  // No usable URLs.
+    // Ignore errors that happened before the last known failed attempt.
+    if (!update_state.failures_last_updated.is_null() &&
+        err_time <= update_state.failures_last_updated)
+      continue;
+
+    if (prev_url_idx >= 0) {
+      if (url_idx < prev_url_idx) {
+        LOG(ERROR) << "The URLs in the download error log have wrapped around ("
+                   << prev_url_idx << "->" << url_idx
+                   << "). This should not have happened and means that there's "
+                      "a bug. To be conservative, we record a failed attempt "
+                      "(invalidating the rest of the error log) and resume "
+                      "download from the first usable URL.";
+        url_idx = -1;
+        is_failure_occurred = true;
+        break;
+      }
+
+      if (url_idx > prev_url_idx) {
+        url_num_errors = 0;
+        do_advance_url = false;
+      }
+    }
+
+    if (HandleErrorCode(get<1>(err_tuple), &url_num_errors) ||
+        url_num_errors > update_state.download_errors_max)
+      do_advance_url = true;
+
+    prev_url_idx = url_idx;
   }
 
+  // If required, advance to the next usable URL. If the URLs wraparound, we
+  // mark an update attempt failure. Also be sure to set the download error
+  // count to zero.
+  if (url_idx < 0 || do_advance_url) {
+    url_num_errors = 0;
+    int start_url_idx = -1;
+    do {
+      if (++url_idx == num_urls) {
+        url_idx = 0;
+        // We only mark failure if an actual advancing of a URL was required.
+        if (do_advance_url)
+          is_failure_occurred = true;
+      }
+
+      if (start_url_idx < 0)
+        start_url_idx = url_idx;
+      else if (url_idx == start_url_idx)
+        url_idx = -1;  // No usable URL.
+    } while (url_idx >= 0 &&
+             !IsUrlUsable(update_state.download_urls[url_idx], http_allowed));
+  }
+
+  // If we have a download URL but a failure was observed, compute a new backoff
+  // expiry (if allowed). The backoff period is generally 2 ^ (num_failures - 1)
+  // days, bounded by the size of int and kAttemptBackoffMaxIntervalInDays, and
+  // fuzzed by kAttemptBackoffFuzzInHours hours. Backoff expiry is computed from
+  // the latest recorded time of error.
+  Time backoff_expiry;
+  if (url_idx >= 0 && is_failure_occurred && may_backoff) {
+    CHECK(!err_time.is_null())
+        << "We must have an error timestamp if a failure occurred!";
+    const uint64_t* seed = ec->GetValue(state->random_provider()->var_seed());
+    POLICY_CHECK_VALUE_AND_FAIL(seed, error);
+    PRNG prng(*seed);
+    int exp = std::min(update_state.num_failures,
+                       static_cast<int>(sizeof(int)) * 8 - 2);
+    TimeDelta backoff_interval = TimeDelta::FromDays(
+        std::min(1 << exp, kAttemptBackoffMaxIntervalInDays));
+    TimeDelta backoff_fuzz = TimeDelta::FromHours(kAttemptBackoffFuzzInHours);
+    TimeDelta wait_period = FuzzedInterval(&prng, backoff_interval.InSeconds(),
+                                           backoff_fuzz.InSeconds());
+    backoff_expiry = err_time + wait_period;
+
+    // If the newly computed backoff already expired, nullify it.
+    if (ec->IsWallclockTimeGreaterThan(backoff_expiry))
+      backoff_expiry = Time();
+  }
+
+  result->do_increment_failures = is_failure_occurred;
+  result->backoff_expiry = backoff_expiry;
   result->url_idx = url_idx;
-  result->url_num_failures = url_num_failures;
+  result->url_num_errors = url_num_errors;
   return EvalStatus::kSucceeded;
 }
 
@@ -642,7 +791,7 @@
         prng.RandMinMax(1, scatter_factor_p->InSeconds()));
   }
 
-  // If we surpass the wait period or the max scatter period associated with
+  // If we surpassed the wait period or the max scatter period associated with
   // the update, then no wait is needed.
   Time wait_expires = (update_state.first_seen +
                        min(wait_period, update_state.scatter_wait_period_max));
diff --git a/update_manager/chromeos_policy.h b/update_manager/chromeos_policy.h
index 846bf57..8b858a2 100644
--- a/update_manager/chromeos_policy.h
+++ b/update_manager/chromeos_policy.h
@@ -15,13 +15,21 @@
 
 namespace chromeos_update_manager {
 
-// Parameters for update download URL, as determined by UpdateDownloadUrl.
-struct UpdateDownloadUrlResult {
+// Output information from UpdateBackoffAndDownloadUrl.
+struct UpdateBackoffAndDownloadUrlResult {
+  // Whether the failed attempt count (maintained by the caller) needs to be
+  // incremented.
+  bool do_increment_failures;
+  // The current backoff expiry. Null if backoff is not in effect.
+  base::Time backoff_expiry;
+  // The new URL index to use and number of download errors associated with it.
+  // Significant iff |do_increment_failures| is false and |backoff_expiry| is
+  // null. Negative value means no usable URL was found.
   int url_idx;
-  int url_num_failures;
+  int url_num_errors;
 };
 
-// Parameters for update scattering, as determined by UpdateNotScattering.
+// Parameters for update scattering, as returned by UpdateScattering.
 struct UpdateScatteringResult {
   bool is_scattering;
   base::TimeDelta wait_period;
@@ -44,7 +52,6 @@
       State* state,
       std::string* error,
       UpdateDownloadParams* result,
-      const bool interactive,
       const UpdateState& update_state) const override;
 
   EvalStatus UpdateDownloadAllowed(
@@ -90,6 +97,10 @@
   static const int kTimeoutMaxBackoffInterval;
   static const int kTimeoutRegularFuzz;
 
+  // Maximum update attempt backoff interval and fuzz.
+  static const int kAttemptBackoffMaxIntervalInDays;
+  static const int kAttemptBackoffFuzzInHours;
+
   // A private policy implementation returning the wallclock timestamp when
   // the next update check should happen.
   // TODO(garnold) We should probably change that to infer a monotonic
@@ -105,21 +116,33 @@
   // TimeDelta.
   static base::TimeDelta FuzzedInterval(PRNG* prng, int interval, int fuzz);
 
-  // A private policy for determining which download URL to use. Within
-  // |update_state|, |download_urls| should contain the download URLs as listed
-  // in the Omaha response; |download_failures_max| the maximum number of
-  // failures per URL allowed per the response; |download_url_idx| the index of
-  // the previously used URL; |download_url_num_failures| the previously known
-  // number of failures associated with that URL; and |download_url_error_codes|
-  // the list of failures occurring since the latest evaluation.
+  // A private policy for determining backoff and the download URL to use.
+  // Within |update_state|, |backoff_expiry| and |is_backoff_disabled| are used
+  // for determining whether backoff is still in effect; if not,
+  // |download_errors| is scanned past |failures_last_updated|, and a new
+  // download URL from |download_urls| is found and written to |result->url_idx|
+  // (-1 means no usable URL exists); |download_errors_max| determines the
+  // maximum number of attempts per URL, according to the Omaha response. If an
+  // update failure is identified then |result->do_increment_failures| is set to
+  // true; if backoff is enabled, a new backoff period is computed (from the
+  // time of failure) based on |num_failures|. Otherwise, backoff expiry is
+  // nullified, indicating that no backoff is in effect.
   //
-  // Upon successfully deciding a URL to use, returns |EvalStatus::kSucceeded|
-  // and writes the current URL index and the number of failures associated with
-  // it in |result|. Otherwise, returns |EvalStatus::kFailed|.
-  EvalStatus UpdateDownloadUrl(EvaluationContext* ec, State* state,
-                               std::string* error,
-                               UpdateDownloadUrlResult* result,
-                               const UpdateState& update_state) const;
+  // If backing off but the previous backoff expiry is unchanged, returns
+  // |EvalStatus::kAskMeAgainLater|. Otherwise:
+  //
+  // * If backing off with a new expiry time, then |result->backoff_expiry| is
+  //   set to this time.
+  //
+  // * Else, |result->backoff_expiry| is set to null, indicating that no backoff
+  //   is in effect.
+  //
+  // In any of these cases, returns |EvalStatus::kSucceeded|. If an error
+  // occurred, returns |EvalStatus::kFailed|.
+  EvalStatus UpdateBackoffAndDownloadUrl(
+      EvaluationContext* ec, State* state, std::string* error,
+      UpdateBackoffAndDownloadUrlResult* result,
+      const UpdateState& update_state) const;
 
   // A private policy for checking whether scattering is due. Writes in |result|
   // the decision as to whether or not to scatter; a wallclock-based scatter
diff --git a/update_manager/chromeos_policy_unittest.cc b/update_manager/chromeos_policy_unittest.cc
index 25a091e..e3f7acf 100644
--- a/update_manager/chromeos_policy_unittest.cc
+++ b/update_manager/chromeos_policy_unittest.cc
@@ -6,6 +6,7 @@
 
 #include <set>
 #include <string>
+#include <tuple>
 #include <vector>
 
 #include <base/time/time.h>
@@ -20,8 +21,10 @@
 using base::TimeDelta;
 using chromeos_update_engine::ErrorCode;
 using chromeos_update_engine::FakeClock;
+using std::make_tuple;
 using std::set;
 using std::string;
+using std::tuple;
 using std::vector;
 
 namespace chromeos_update_manager {
@@ -118,17 +121,39 @@
     fake_clock_.SetWallclockTime(curr_time);
   }
 
-  // Returns a default UpdateState structure: first seen time is calculated
-  // backward from the current wall clock time, update was seen just once;
-  // there's a single HTTP download URL with a maximum of 10 allowed failures;
-  // there is no scattering wait period and the max allowed is 7 days, there is
-  // no check threshold and none is allowed.
-  UpdateState GetDefaultUpdateState(TimeDelta update_first_seen_period) {
-    UpdateState update_state = {
-      fake_clock_.GetWallclockTime() - update_first_seen_period, 1,
-      vector<string>(1, "http://fake/url/"), 10, 0, 0, vector<ErrorCode>(),
-      TimeDelta(), TimeDelta::FromDays(7), 0, 0, 0
-    };
+  // Returns a default UpdateState structure:
+  UpdateState GetDefaultUpdateState(TimeDelta first_seen_period) {
+    Time first_seen_time = fake_clock_.GetWallclockTime() - first_seen_period;
+    UpdateState update_state = UpdateState();
+
+    // This is a non-interactive check returning a delta payload, seen for the
+    // first time (|first_seen_period| ago). Clearly, there were no failed
+    // attempts so far.
+    update_state.is_interactive = false;
+    update_state.is_delta_payload = false;
+    update_state.first_seen = first_seen_time;
+    update_state.num_checks = 1;
+    update_state.num_failures = 0;
+    update_state.failures_last_updated = Time();  // Needs to be zero.
+    // There's a single HTTP download URL with a maximum of 10 retries.
+    update_state.download_urls = vector<string>{"http://fake/url/"};
+    update_state.download_errors_max = 10;
+    // Download was never attempted.
+    update_state.last_download_url_idx = -1;
+    update_state.last_download_url_num_errors = 0;
+    // There were no download errors.
+    update_state.download_errors = vector<tuple<int, ErrorCode, Time>>();
+    // No active backoff period, backoff is not disabled by Omaha.
+    update_state.backoff_expiry = Time();
+    update_state.is_backoff_disabled = false;
+    // There is no active scattering wait period (max 7 days allowed) nor check
+    // threshold (none allowed).
+    update_state.scatter_wait_period = TimeDelta();
+    update_state.scatter_check_threshold = 0;
+    update_state.scatter_wait_period_max = TimeDelta::FromDays(7);
+    update_state.scatter_check_threshold_min = 0;
+    update_state.scatter_check_threshold_max = 0;
+
     return update_state;
   }
 
@@ -436,7 +461,7 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kFailed,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartNotAllowedCheckDue) {
@@ -449,7 +474,7 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kCheckDue, result.cannot_start_reason);
 }
@@ -465,11 +490,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedBlankPolicy) {
@@ -482,11 +508,223 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
+}
+
+TEST_F(UmChromeOSPolicyTest,
+       UpdateCanStartNotAllowedBackoffNewWaitPeriodApplies) {
+  // The UpdateCanStart policy returns false; failures are reported and a new
+  // backoff period is enacted.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_FALSE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kBackoff, result.cannot_start_reason);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_LT(curr_time, result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest,
+       UpdateCanStartNotAllowedBackoffPrevWaitPeriodStillApplies) {
+  // The UpdateCanStart policy returns false; a previously enacted backoff
+  // period still applies.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.failures_last_updated = curr_time;
+  update_state.backoff_expiry = curr_time + TimeDelta::FromMinutes(3);
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kAskMeAgainLater, &Policy::UpdateCanStart,
+                     &result, update_state);
+  EXPECT_FALSE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kBackoff, result.cannot_start_reason);
+  EXPECT_FALSE(result.do_increment_failures);
+  EXPECT_LT(curr_time, result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedBackoffSatisfied) {
+  // The UpdateCanStart policy returns true; a previously enacted backoff period
+  // has elapsed, we're good to go.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.failures_last_updated = curr_time - TimeDelta::FromSeconds(1);
+  update_state.backoff_expiry = curr_time - TimeDelta::FromSeconds(1);
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart,
+                     &result, update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedBackoffDisabled) {
+  // The UpdateCanStart policy returns false; failures are reported but backoff
+  // is disabled.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.is_backoff_disabled = true;
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedNoBackoffInteractive) {
+  // The UpdateCanStart policy returns false; failures are reported but this is
+  // an interactive update check.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.is_interactive = true;
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedNoBackoffDelta) {
+  // The UpdateCanStart policy returns false; failures are reported but this is
+  // a delta payload.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.is_delta_payload = true;
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedNoBackoffUnofficialBuild) {
+  // The UpdateCanStart policy returns false; failures are reported but this is
+  // an unofficial build.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+
+  fake_state_.system_provider()->var_is_official_build()->
+      reset(new bool(false));
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartFailsScatteringFailed) {
@@ -497,13 +735,16 @@
 
   // Override the default seed variable with a null value so that the policy
   // request would fail.
+  // TODO(garnold) This failure may or may not fail a number
+  // sub-policies/decisions, like scattering and backoff. We'll need a more
+  // deliberate setup to ensure that we're failing what we want to be failing.
   fake_state_.random_provider()->var_seed()->reset(nullptr);
 
   // Check that the UpdateCanStart fails.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(1));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kFailed,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
 }
 
 TEST_F(UmChromeOSPolicyTest,
@@ -523,7 +764,7 @@
   // generated.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kScattering, result.cannot_start_reason);
   EXPECT_LT(TimeDelta(), result.scatter_wait_period);
@@ -547,7 +788,7 @@
   // generated.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kAskMeAgainLater, &Policy::UpdateCanStart,
-                     &result, false, update_state);
+                     &result, update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kScattering, result.cannot_start_reason);
   EXPECT_EQ(TimeDelta::FromSeconds(35), result.scatter_wait_period);
@@ -573,7 +814,7 @@
   // Check that the UpdateCanStart returns false.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kScattering, result.cannot_start_reason);
   EXPECT_LE(2, result.scatter_check_threshold);
@@ -597,7 +838,7 @@
   // Check that the UpdateCanStart returns false.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kScattering, result.cannot_start_reason);
   EXPECT_EQ(3, result.scatter_check_threshold);
@@ -622,12 +863,13 @@
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_EQ(TimeDelta(), result.scatter_wait_period);
   EXPECT_EQ(0, result.scatter_check_threshold);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest,
@@ -641,6 +883,7 @@
       new TimeDelta(TimeDelta::FromSeconds(1)));
 
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(1));
+  update_state.is_interactive = true;
   update_state.scatter_check_threshold = 0;
   update_state.scatter_check_threshold_min = 2;
   update_state.scatter_check_threshold_max = 5;
@@ -648,12 +891,13 @@
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     true, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_EQ(TimeDelta(), result.scatter_wait_period);
   EXPECT_EQ(0, result.scatter_check_threshold);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest,
@@ -668,6 +912,7 @@
   fake_state_.system_provider()->var_is_oobe_complete()->reset(new bool(false));
 
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(1));
+  update_state.is_interactive = true;
   update_state.scatter_check_threshold = 0;
   update_state.scatter_check_threshold_min = 2;
   update_state.scatter_check_threshold_max = 5;
@@ -675,12 +920,13 @@
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     true, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_EQ(TimeDelta(), result.scatter_wait_period);
   EXPECT_EQ(0, result.scatter_check_threshold);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithAttributes) {
@@ -699,11 +945,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_TRUE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithP2PFromUpdater) {
@@ -720,11 +967,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_TRUE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest,
@@ -745,11 +993,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithHttpsUrl) {
@@ -764,16 +1013,47 @@
 
   // Add an HTTPS URL.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
-  update_state.download_urls.push_back("https://secure/url/");
+  update_state.download_urls.emplace_back("https://secure/url/");
 
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(1, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedMaxErrorsNotExceeded) {
+  // The UpdateCanStart policy returns true; the first URL has download errors
+  // but does not exceed the maximum allowed number of failures, so it is stilli
+  // usable.
+
+  SetUpdateCheckAllowed(false);
+
+  // Add a second URL; update with this URL attempted and failed enough times to
+  // disqualify the current (first) URL.
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
+  update_state.num_checks = 5;
+  update_state.download_urls.emplace_back("http://another/fake/url/");
+  Time t = fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(12);
+  for (int i = 0; i < 5; i++) {
+    update_state.download_errors.emplace_back(
+        0, ErrorCode::kDownloadTransferError, t);
+    t += TimeDelta::FromSeconds(1);
+  }
+
+  // Check that the UpdateCanStart returns true.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_FALSE(result.p2p_allowed);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(5, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithSecondUrlMaxExceeded) {
@@ -783,26 +1063,26 @@
   SetUpdateCheckAllowed(false);
 
   // Add a second URL; update with this URL attempted and failed enough times to
-  // disqualify the current (first) URL. This tests both the previously
-  // accounted failures (download_url_num_failures) as well as those occurring
-  // since the last call (download_url_error_codes).
+  // disqualify the current (first) URL.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   update_state.num_checks = 10;
-  update_state.download_urls.push_back("http://another/fake/url/");
-  update_state.download_url_num_failures = 9;
-  update_state.download_url_error_codes.push_back(
-      ErrorCode::kDownloadTransferError);
-  update_state.download_url_error_codes.push_back(
-      ErrorCode::kDownloadWriteError);
+  update_state.download_urls.emplace_back("http://another/fake/url/");
+  Time t = fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(12);
+  for (int i = 0; i < 11; i++) {
+    update_state.download_errors.emplace_back(
+        0, ErrorCode::kDownloadTransferError, t);
+    t += TimeDelta::FromSeconds(1);
+  }
 
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(1, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithSecondUrlHardError) {
@@ -815,18 +1095,20 @@
   // causes it to switch directly to the next URL.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   update_state.num_checks = 10;
-  update_state.download_urls.push_back("http://another/fake/url/");
-  update_state.download_url_error_codes.push_back(
-      ErrorCode::kPayloadHashMismatchError);
+  update_state.download_urls.emplace_back("http://another/fake/url/");
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kPayloadHashMismatchError,
+      fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(1));
 
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(1, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedUrlWrapsAround) {
@@ -836,27 +1118,35 @@
   SetUpdateCheckAllowed(false);
 
   // Add a second URL; update with this URL attempted and failed in a way that
-  // causes it to switch directly to the next URL.
+  // causes it to switch directly to the next URL. We must disable backoff in
+  // order for it not to interfere.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
-  update_state.num_checks = 10;
-  update_state.download_urls.push_back("http://another/fake/url/");
-  update_state.download_url_idx = 1;
-  update_state.download_url_error_codes.push_back(
-      ErrorCode::kPayloadHashMismatchError);
+  update_state.num_checks = 1;
+  update_state.is_backoff_disabled = true;
+  update_state.download_urls.emplace_back("http://another/fake/url/");
+  update_state.download_errors.emplace_back(
+      1, ErrorCode::kPayloadHashMismatchError,
+      fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(1));
 
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartNotAllowedNoUsableUrls) {
   // The UpdateCanStart policy returns false; there's a single HTTP URL but its
   // use is forbidden by policy.
+  //
+  // Note: In the case where no usable URLs are found, the policy should not
+  // increment the number of failed attempts! Doing so would result in a
+  // non-idempotent semantics, and does not fall within the intended purpose of
+  // the backoff mechanism anyway.
 
   SetUpdateCheckAllowed(false);
 
@@ -867,14 +1157,21 @@
   // Check that the UpdateCanStart returns false.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
-  ExpectPolicyStatus(EvalStatus::kFailed, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_FALSE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kCannotDownload,
+            result.cannot_start_reason);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedNoUsableUrlsButP2PEnabled) {
   // The UpdateCanStart policy returns true; there's a single HTTP URL but its
   // use is forbidden by policy, however P2P is enabled. The result indicates
   // that no URL can be used.
+  //
+  // Note: The number of failed attempts should not increase in this case (see
+  // above test).
 
   SetUpdateCheckAllowed(false);
 
@@ -888,11 +1185,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_TRUE(result.p2p_allowed);
   EXPECT_GT(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateDownloadAllowedEthernetDefault) {
diff --git a/update_manager/default_policy.cc b/update_manager/default_policy.cc
index 98c2786..5a07900 100644
--- a/update_manager/default_policy.cc
+++ b/update_manager/default_policy.cc
@@ -41,4 +41,31 @@
   return EvalStatus::kAskMeAgainLater;
 }
 
+EvalStatus DefaultPolicy::UpdateCanStart(
+    EvaluationContext* ec,
+    State* state,
+    std::string* error,
+    UpdateDownloadParams* result,
+    const UpdateState& update_state) const {
+  result->update_can_start = true;
+  result->cannot_start_reason = UpdateCannotStartReason::kUndefined;
+  result->download_url_idx = 0;
+  result->download_url_num_errors = 0;
+  result->p2p_allowed = false;
+  result->do_increment_failures = false;
+  result->backoff_expiry = base::Time();
+  result->scatter_wait_period = base::TimeDelta();
+  result->scatter_check_threshold = 0;
+  return EvalStatus::kSucceeded;
+}
+
+EvalStatus DefaultPolicy::UpdateDownloadAllowed(
+    EvaluationContext* ec,
+    State* state,
+    std::string* error,
+    bool* result) const {
+  *result = true;
+  return EvalStatus::kSucceeded;
+}
+
 }  // namespace chromeos_update_manager
diff --git a/update_manager/default_policy.h b/update_manager/default_policy.h
index 526476c..f3f663c 100644
--- a/update_manager/default_policy.h
+++ b/update_manager/default_policy.h
@@ -57,30 +57,13 @@
       UpdateCheckParams* result) const override;
 
   EvalStatus UpdateCanStart(
-      EvaluationContext* ec,
-      State* state,
-      std::string* error,
+      EvaluationContext* ec, State* state, std::string* error,
       UpdateDownloadParams* result,
-      const bool interactive,
-      const UpdateState& update_state) const override {
-    result->update_can_start = true;
-    result->p2p_allowed = false;
-    result->download_url_idx = 0;
-    result->download_url_num_failures = 0;
-    result->cannot_start_reason = UpdateCannotStartReason::kUndefined;
-    result->scatter_wait_period = base::TimeDelta();
-    result->scatter_check_threshold = 0;
-    return EvalStatus::kSucceeded;
-  }
+      const UpdateState& update_state) const override;
 
   EvalStatus UpdateDownloadAllowed(
-      EvaluationContext* ec,
-      State* state,
-      std::string* error,
-      bool* result) const override {
-    *result = true;
-    return EvalStatus::kSucceeded;
-  }
+      EvaluationContext* ec, State* state, std::string* error,
+      bool* result) const override;
 
  protected:
   // Policy override.
diff --git a/update_manager/mock_policy.h b/update_manager/mock_policy.h
index f6acb7f..4fff97e 100644
--- a/update_manager/mock_policy.h
+++ b/update_manager/mock_policy.h
@@ -24,10 +24,10 @@
                      EvalStatus(EvaluationContext*, State*, std::string*,
                                 UpdateCheckParams*));
 
-  MOCK_CONST_METHOD6(UpdateCanStart,
+  MOCK_CONST_METHOD5(UpdateCanStart,
                      EvalStatus(EvaluationContext*, State*, std::string*,
                                 UpdateDownloadParams*,
-                                const bool, const UpdateState&));
+                                const UpdateState&));
 
   MOCK_CONST_METHOD4(UpdateCanStart,
                      EvalStatus(EvaluationContext*, State*, std::string*,
diff --git a/update_manager/policy.h b/update_manager/policy.h
index 8ec5c9e..40586c3 100644
--- a/update_manager/policy.h
+++ b/update_manager/policy.h
@@ -6,6 +6,7 @@
 #define UPDATE_ENGINE_UPDATE_MANAGER_POLICY_H_
 
 #include <string>
+#include <tuple>
 #include <vector>
 
 #include "update_engine/error_code.h"
@@ -41,38 +42,67 @@
 
 // Input arguments to UpdateCanStart.
 //
-// A snapshot of the state of the current update process.
+// A snapshot of the state of the current update process. This includes
+// everything that a policy might need and that occurred since the first time
+// the current payload was first seen and attempted (consecutively).
 struct UpdateState {
-  // Information pertaining to the Omaha update response.
+  // Information pertaining to the current update payload and/or check.
   //
-  // Time when update was first offered by Omaha.
+  // Whether the current update check is an interactive one. The caller should
+  // feed the value returned by the preceding call to UpdateCheckAllowed().
+  bool is_interactive;
+  // Whether it is a delta payload.
+  bool is_delta_payload;
+  // Wallclock time when payload was first (consecutively) offered by Omaha.
   base::Time first_seen;
-  // Number of update checks returning the current update.
+  // Number of consecutive update checks returning the current update.
   int num_checks;
+  // Number of update payload failures and the wallclock time when it was last
+  // updated by the updater. These should both be nullified whenever a new
+  // update is seen; they are updated at the policy's descretion (via
+  // UpdateDownloadParams.do_increment_failures) once all of the usable download
+  // URLs for the payload have been used without success. They should be
+  // persisted across reboots.
+  int num_failures;
+  base::Time failures_last_updated;
 
-  // Information pertaining to the update download URL.
+  // Information pertaining to downloading and applying of the current update.
   //
   // An array of download URLs provided by Omaha.
   std::vector<std::string> download_urls;
-  // Max number of failures allowed per download URL.
-  int download_failures_max;
-  // The index of the URL to use, as previously determined by the policy. This
-  // number is significant iff |num_checks| is greater than 1.
-  int download_url_idx;
-  // The number of failures already associated with this URL.
-  int download_url_num_failures;
-  // An array of failure error codes that occurred since the latest reported
-  // ones (included in the number above).
-  std::vector<chromeos_update_engine::ErrorCode> download_url_error_codes;
+  // Max number of errors allowed per download URL.
+  int download_errors_max;
+  // The index of the URL to download from, as determined in the previous call
+  // to the policy. For a newly seen payload, this should be -1.
+  int last_download_url_idx;
+  // The number of successive download errors pertaining to this last URL, as
+  // determined in the previous call to the policy. For a newly seen payload,
+  // this should be zero.
+  int last_download_url_num_errors;
+  // An array of errors that occurred while trying to download this update since
+  // the previous call to this policy has returned, or since this payload was
+  // first seen, or since the updater process has started (whichever is later).
+  // Includes the URL index attempted, the error code, and the wallclock-based
+  // timestamp when it occurred.
+  std::vector<std::tuple<int, chromeos_update_engine::ErrorCode, base::Time>>
+      download_errors;
+
+  // Information pertaining to update backoff mechanism.
+  //
+  // The currently known (persisted) wallclock-based backoff expiration time;
+  // zero if none.
+  base::Time backoff_expiry;
+  // Whether backoff is disabled by Omaha.
+  bool is_backoff_disabled;
 
   // Information pertaining to update scattering.
   //
-  // Scattering wallclock-based wait period, as returned by the policy.
+  // The currently knwon (persisted) scattering wallclock-based wait period and
+  // update check threshold; zero if none.
   base::TimeDelta scatter_wait_period;
+  int scatter_check_threshold;
   // Maximum wait period allowed for this update, as determined by Omaha.
   base::TimeDelta scatter_wait_period_max;
-  // Scattering update check threshold, as returned by the policy.
-  int scatter_check_threshold;
   // Minimum/maximum check threshold values.
   // TODO(garnold) These appear to not be related to the current update and so
   // should probably be obtained as variables via UpdaterProvider.
@@ -88,29 +118,46 @@
   kUndefined,
   kCheckDue,
   kScattering,
+  kBackoff,
   kCannotDownload,
 };
 
 struct UpdateDownloadParams {
   // Whether the update attempt is allowed to proceed.
   bool update_can_start;
+  // If update cannot proceed, a reason code for why it cannot do so.
+  UpdateCannotStartReason cannot_start_reason;
 
   // Attributes pertaining to the case where update is allowed. The update
   // engine uses them to choose the means for downloading and applying an
   // update.
-  bool p2p_allowed;
-  // The index of the download URL to use, and the number of failures associated
-  // with this URL. An index value of -1 indicates that no suitable URL is
-  // available, but there may be other means for download (like P2P).
+  //
+  // The index of the download URL to use, or -1 if no suitable URL was found;
+  // in the latter case, there may still be other means for download (like P2P).
+  // This value needs to be persisted and handed back to the policy on the next
+  // time it is called.
   int download_url_idx;
-  int download_url_num_failures;
+  // The number of download errors associated with this download URL. This value
+  // needs to be persisted and handed back to the policy on the next time it is
+  // called.
+  int download_url_num_errors;
+  // Whether P2P downloads are allowed.
+  bool p2p_allowed;
 
-  // Attributes pertaining to the case where update is not allowed. Some are
-  // needed for storing values to persistent storage, others for
-  // logging/metrics.
-  UpdateCannotStartReason cannot_start_reason;
-  base::TimeDelta scatter_wait_period;  // Needs to be persisted.
-  int scatter_check_threshold;  // Needs to be persisted.
+  // Other values that need to be persisted and handed to the policy as need on
+  // the next call.
+  //
+  // Whether an update failure has been identified by the policy. The client
+  // should increment and persist its update failure count, and record the time
+  // when this was done; it needs to hand these values back to the policy
+  // (UpdateState.{num_failures,failures_last_updated}) on the next time it is
+  // called.
+  bool do_increment_failures;
+  // The current backof expiry.
+  base::Time backoff_expiry;
+  // The scattering wait period and check threshold.
+  base::TimeDelta scatter_wait_period;
+  int scatter_check_threshold;
 };
 
 // The Policy class is an interface to the ensemble of policy requests that the
@@ -165,22 +212,20 @@
   // processed, or the attempt needs to be aborted. In cases where the update
   // needs to wait for some condition to be satisfied, but none of the values
   // that need to be persisted has changed, returns
-  // EvalStatus::kAskMeAgainLater. Arguments include an |interactive| flag that
-  // tells whether the update is user initiated, and an |update_state| that
+  // EvalStatus::kAskMeAgainLater. Arguments include an |update_state| that
   // encapsulates data pertaining to the current ongoing update process.
   virtual EvalStatus UpdateCanStart(
       EvaluationContext* ec,
       State* state,
       std::string* error,
       UpdateDownloadParams* result,
-      const bool interactive,
       const UpdateState& update_state) const = 0;
 
   // Checks whether downloading of an update is allowed; currently, this checks
   // whether the network connection type is suitable for updating over.  May
   // consult the shill provider as well as the device policy (if available).
   // Returns |EvalStatus::kSucceeded|, setting |result| according to whether or
-  // not the current connection can be used; on failure, returns
+  // not the current connection can be used; on error, returns
   // |EvalStatus::kFailed| and sets |error| accordingly.
   virtual EvalStatus UpdateDownloadAllowed(
       EvaluationContext* ec,
diff --git a/update_manager/update_manager_unittest.cc b/update_manager/update_manager_unittest.cc
index f6a1c01..9e21716 100644
--- a/update_manager/update_manager_unittest.cc
+++ b/update_manager/update_manager_unittest.cc
@@ -6,6 +6,7 @@
 
 #include <algorithm>
 #include <string>
+#include <tuple>
 #include <utility>
 #include <vector>
 
@@ -31,6 +32,7 @@
 using chromeos_update_engine::FakeClock;
 using std::pair;
 using std::string;
+using std::tuple;
 using std::vector;
 using testing::Return;
 using testing::StrictMock;
@@ -161,15 +163,29 @@
 }
 
 TEST_F(UmUpdateManagerTest, PolicyRequestCallUpdateCanStart) {
-  const UpdateState update_state = {
-    FixedTime(), 1,
-    vector<string>(1, "http://fake/url/"), 10, 0, 0, vector<ErrorCode>(),
-    TimeDelta::FromSeconds(15), TimeDelta::FromSeconds(60),
-    4, 2, 8
-  };
+  UpdateState update_state = UpdateState();
+  update_state.is_interactive = true;
+  update_state.is_delta_payload = false;
+  update_state.first_seen = FixedTime();
+  update_state.num_checks = 1;
+  update_state.num_failures = 0;
+  update_state.failures_last_updated = Time();
+  update_state.download_urls = vector<string>{"http://fake/url/"};
+  update_state.download_errors_max = 10;
+  update_state.last_download_url_idx = -1;
+  update_state.last_download_url_num_errors = 0;
+  update_state.download_errors = vector<tuple<int, ErrorCode, Time>>();
+  update_state.backoff_expiry = Time();
+  update_state.is_backoff_disabled = false;
+  update_state.scatter_wait_period = TimeDelta::FromSeconds(15);
+  update_state.scatter_check_threshold = 4;
+  update_state.scatter_wait_period_max = TimeDelta::FromSeconds(60);
+  update_state.scatter_check_threshold_min = 2;
+  update_state.scatter_check_threshold_max = 8;
+
   UpdateDownloadParams result;
   EXPECT_EQ(EvalStatus::kSucceeded,
-            umut_->PolicyRequest(&Policy::UpdateCanStart, &result, true,
+            umut_->PolicyRequest(&Policy::UpdateCanStart, &result,
                                  update_state));
 }