Support delta-compressed variations server responses.

chrome/browser/metrics/variations/variations_seed_store.cc

 // Copyright 2014 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 "chrome/browser/metrics/variations/variations_seed_store.h"
 
 #include "base/base64.h"
 #include "base/metrics/histogram_macros.h"
+#include "base/numerics/safe_math.h"
 #include "base/prefs/pref_registry_simple.h"
 #include "base/prefs/pref_service.h"
 #include "base/sha1.h"
 #include "base/strings/string_number_conversions.h"
 #include "chrome/common/pref_names.h"
 #include "components/metrics/compression_utils.h"
 #include "components/variations/proto/variations_seed.pb.h"
 #include "crypto/signature_verifier.h"
+#include "third_party/protobuf/src/google/protobuf/io/coded_stream.h"
 
 namespace chrome_variations {
 
 namespace {
 
 // Signature verification is disabled on mobile platforms for now, since it
 // adds about ~15ms to the startup time on mobile (vs. a couple ms on desktop).
 bool SignatureVerificationEnabled() {
 #if defined(OS_IOS) || defined(OS_ANDROID)
   return false;
@@ skipping 48 matching lines @@
   UMA_HISTOGRAM_ENUMERATION("Variations.SeedEmpty", state,
                             VARIATIONS_SEED_EMPTY_ENUM_SIZE);
 }
 
 enum VariationsSeedStoreResult {
   VARIATIONS_SEED_STORE_SUCCESS,
   VARIATIONS_SEED_STORE_FAILED_EMPTY,
   VARIATIONS_SEED_STORE_FAILED_PARSE,
   VARIATIONS_SEED_STORE_FAILED_SIGNATURE,
   VARIATIONS_SEED_STORE_FAILED_GZIP,
+  VARIATIONS_SEED_STORE_DELTA_COUNT,

[rkaplow, 2015/08/04 22:37:05]

DELTA_COUNT is a bit unlike the rest (not really a result). Seems fine to keep
it in this histogram but maybe comment on it here to explain what it is about.

[Alexei Svitkine (slow), 2015/08/05 15:46:15]

Done.

+  VARIATIONS_SEED_STORE_FAILED_DELTA_READ_SEED,
+  VARIATIONS_SEED_STORE_FAILED_DELTA_APPLY,
+  VARIATIONS_SEED_STORE_FAILED_DELTA_STORE,
   VARIATIONS_SEED_STORE_RESULT_ENUM_SIZE,
 };
 
-void RecordVariationsSeedStoreHistogram(VariationsSeedStoreResult result) {
+void RecordSeedStoreHistogram(VariationsSeedStoreResult result) {
   UMA_HISTOGRAM_ENUMERATION("Variations.SeedStoreResult", result,
                             VARIATIONS_SEED_STORE_RESULT_ENUM_SIZE);
 }
 
 // Note: UMA histogram enum - don't re-order or remove entries.
 enum VariationsSeedDateChangeState {
   SEED_DATE_NO_OLD_DATE,
   SEED_DATE_NEW_DATE_OLDER,
   SEED_DATE_SAME_DAY,
   SEED_DATE_NEW_DAY,
@@ skipping 25 matching lines @@
     // The server date is earlier than the stored date, and they are from
     // different UTC days, so |server_seed_date| is a valid new day.
     return SEED_DATE_NEW_DAY;
   }
   return SEED_DATE_SAME_DAY;
 }
 
 }  // namespace
 
 VariationsSeedStore::VariationsSeedStore(PrefService* local_state)
-    : local_state_(local_state) {
+    : local_state_(local_state), seed_has_country_code_(false) {
 }
 
 VariationsSeedStore::~VariationsSeedStore() {
 }
 
 bool VariationsSeedStore::LoadSeed(variations::VariationsSeed* seed) {
   invalid_base64_signature_.clear();
 
   std::string seed_data;
   if (!ReadSeedData(&seed_data))
@@ skipping 22 matching lines @@
   }
 
   // Migrate any existing country code from the seed to the pref, if the pref is
   // empty. TODO(asvitkine): Clean up the code in M50+ when sufficient number
   // of clients have migrated.
   if (seed->has_country_code() &&
       local_state_->GetString(prefs::kVariationsCountry).empty()) {
     local_state_->SetString(prefs::kVariationsCountry, seed->country_code());
   }
   variations_serial_number_ = seed->serial_number();
+  seed_has_country_code_ = seed->has_country_code();
   RecordVariationSeedEmptyHistogram(VARIATIONS_SEED_NOT_EMPTY);
   return true;
 }
 
 bool VariationsSeedStore::StoreSeedData(
+    const std::string& data,
+    const std::string& base64_seed_signature,
+    const std::string& country_code,
+    const base::Time& date_fetched,
+    bool is_delta_compressed,
+    variations::VariationsSeed* parsed_seed) {
+  if (!is_delta_compressed) {
+    return StoreSeedDataNoDelta(data, base64_seed_signature, country_code,
+                                date_fetched, parsed_seed);
+  }
+
+  // If the data is delta compressed, first decode it.
+  DCHECK(invalid_base64_signature_.empty());
+  RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_DELTA_COUNT);
+
+  std::string existing_seed_data;
+  std::string updated_seed_data;
+  if (!ReadSeedData(&existing_seed_data)) {
+    RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_DELTA_READ_SEED);
+    return false;
+  }
+  if (!ApplyDeltaPatch(existing_seed_data, data, &updated_seed_data)) {
+    RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_DELTA_APPLY);
+    return false;
+  }
+
+  const bool result =
+      StoreSeedDataNoDelta(updated_seed_data, base64_seed_signature,
+                           country_code, date_fetched, parsed_seed);
+  if (result) {
+    // Note: |updated_seed_data.length()| is guaranteed to be non-zero, else
+    // result would be false.
+    int size_reduction = updated_seed_data.length() - data.length();
+    UMA_HISTOGRAM_PERCENTAGE("Variations.SeedDelta.SizeReductionPercent",
+                             100 * size_reduction / updated_seed_data.length());
+  } else {
+    RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_DELTA_STORE);
+  }
+  return result;
+}
+
+// TODO(asvitkine): Move this method down to match declaration order in a

[rkaplow, 2015/08/04 22:37:05]

did you leave it as is as to make the diff more readable? You are truly a
gentlemen.

[Alexei Svitkine (slow), 2015/08/05 15:46:15]

Yep. :)

+// follow-up CL.
+bool VariationsSeedStore::StoreSeedDataNoDelta(
     const std::string& seed_data,
     const std::string& base64_seed_signature,
+    const std::string& country_code,
     const base::Time& date_fetched,
     variations::VariationsSeed* parsed_seed) {
   if (seed_data.empty()) {
-    RecordVariationsSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_EMPTY);
+    RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_EMPTY);
     return false;
   }
 
   // Only store the seed data if it parses correctly.
   variations::VariationsSeed seed;
   if (!seed.ParseFromString(seed_data)) {
-    RecordVariationsSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_PARSE);
+    RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_PARSE);
     return false;
   }
 
   const VerifySignatureResult result =
       VerifySeedSignature(seed_data, base64_seed_signature);
   if (result != VARIATIONS_SEED_SIGNATURE_ENUM_SIZE) {
     UMA_HISTOGRAM_ENUMERATION("Variations.StoreSeedSignature", result,
                               VARIATIONS_SEED_SIGNATURE_ENUM_SIZE);
     if (result != VARIATIONS_SEED_SIGNATURE_VALID) {
-      RecordVariationsSeedStoreHistogram(
-          VARIATIONS_SEED_STORE_FAILED_SIGNATURE);
+      RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_SIGNATURE);
       return false;
     }
   }
 
   // Compress the seed before base64-encoding and storing.
   std::string compressed_seed_data;
   if (!metrics::GzipCompress(seed_data, &compressed_seed_data)) {
-    RecordVariationsSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_GZIP);
+    RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_FAILED_GZIP);
     return false;
   }
 
   std::string base64_seed_data;
   base::Base64Encode(compressed_seed_data, &base64_seed_data);
 
   // TODO(asvitkine): This pref is no longer being used. Remove it completely
   // in M45+.
   local_state_->ClearPref(prefs::kVariationsSeed);
 
   // Update the saved country code only if one was returned from the server.
-  if (seed.has_country_code())
+  // Prefer the country code that was transmitted in the header over the one in
+  // the seed (which is deprecated).
+  if (!country_code.empty())
+    local_state_->SetString(prefs::kVariationsCountry, country_code);
+  else if (seed.has_country_code())
     local_state_->SetString(prefs::kVariationsCountry, seed.country_code());
 
   local_state_->SetString(prefs::kVariationsCompressedSeed, base64_seed_data);
   UpdateSeedDateAndLogDayChange(date_fetched);
   local_state_->SetString(prefs::kVariationsSeedSignature,
                           base64_seed_signature);
   variations_serial_number_ = seed.serial_number();
   if (parsed_seed)
     seed.Swap(parsed_seed);
 
-  RecordVariationsSeedStoreHistogram(VARIATIONS_SEED_STORE_SUCCESS);
+  RecordSeedStoreHistogram(VARIATIONS_SEED_STORE_SUCCESS);
   return true;
 }
 
 void VariationsSeedStore::UpdateSeedDateAndLogDayChange(
     const base::Time& server_date_fetched) {
   VariationsSeedDateChangeState date_change = SEED_DATE_NO_OLD_DATE;
 
   if (local_state_->HasPrefPath(prefs::kVariationsSeedDate)) {
     const int64 stored_date_value =
         local_state_->GetInt64(prefs::kVariationsSeedDate);
     const base::Time stored_date =
         base::Time::FromInternalValue(stored_date_value);
 
     date_change = GetSeedDateChangeState(server_date_fetched, stored_date);
   }
 
   UMA_HISTOGRAM_ENUMERATION("Variations.SeedDateChange", date_change,
                             SEED_DATE_ENUM_SIZE);
 
   local_state_->SetInt64(prefs::kVariationsSeedDate,
                          server_date_fetched.ToInternalValue());
 }
 
+
+std::string VariationsSeedStore::GetInvalidSignature() const {
+  return invalid_base64_signature_;
+}
+
 // static
 void VariationsSeedStore::RegisterPrefs(PrefRegistrySimple* registry) {
   registry->RegisterStringPref(prefs::kVariationsCompressedSeed, std::string());
   registry->RegisterStringPref(prefs::kVariationsSeed, std::string());
   registry->RegisterInt64Pref(prefs::kVariationsSeedDate,
                               base::Time().ToInternalValue());
   registry->RegisterStringPref(prefs::kVariationsSeedSignature, std::string());
 }
 
 void VariationsSeedStore::ClearPrefs() {
@@ skipping 57 matching lines @@
     return VARIATIONS_SEED_SIGNATURE_INVALID_SIGNATURE;
   }
 
   verifier.VerifyUpdate(reinterpret_cast<const uint8*>(seed_bytes.data()),
                         seed_bytes.size());
   if (verifier.VerifyFinal())
     return VARIATIONS_SEED_SIGNATURE_VALID;
   return VARIATIONS_SEED_SIGNATURE_INVALID_SEED;
 }
 
-std::string VariationsSeedStore::GetInvalidSignature() const {
-  return invalid_base64_signature_;
+// static
+bool VariationsSeedStore::ApplyDeltaPatch(const std::string& existing_data,
+                                          const std::string& patch,
+                                          std::string* output) {
+  output->clear();
+
+  google::protobuf::io::CodedInputStream in(
+      reinterpret_cast<const uint8*>(patch.data()), patch.length());
+  // Temporary string declared outside the loop so it can be re-used between
+  // different iterations (rather than allocating new ones).
+  std::string temp;
+
+  const uint32 existing_data_size = static_cast<uint32>(existing_data.size());
+  while (in.CurrentPosition() != static_cast<int>(patch.length())) {
+    uint32 value;
+    if (!in.ReadVarint32(&value))
+      return false;
+
+    if (value == 0) {

[rkaplow, 2015/08/04 22:37:05]

hm, maybe I'm not familiar enough with data diffs, but I didn't know about this
pattern of a 0, followed by a offset,length to determine which parts to get from
original data.
Might be worth a little bit of english so it's obvious for the reader. If you
could also link to where this is defined that would be great.

[Alexei Svitkine (slow), 2015/08/05 15:46:15]

It's actually just the format of the diff produced by the "bm" library we use.
This is its re-implementation in C++.

I've reversed the if and added comments to both branches to explain the format
more.

+      uint32 offset;
+      uint32 length;
+      if (!in.ReadVarint32(&offset) || !in.ReadVarint32(&length))
+        return false;
+
+      // Check for |offset + length| being out of range and for overflow.
+      base::CheckedNumeric<uint32> end_offset(offset);
+      end_offset += length;
+      if (!end_offset.IsValid() || end_offset.ValueOrDie() > existing_data_size)
+        return false;
+      output->append(existing_data, offset, length);
+    } else {
+      // No need to guard against bad data (i.e. very large |value|) because the
+      // call below will fail if |value| is greater than the size of the patch.
+      if (!in.ReadString(&temp, value))
+        return false;
+      output->append(temp);
+    }
+  }
+  return true;
 }
 
 }  // namespace chrome_variations