diff options
24 files changed, 1038 insertions, 206 deletions
@@ -185,6 +185,7 @@ v8.log /third_party/mingw-w64 /third_party/mkl /third_party/mozc +/third_party/mt19937ar /third_party/nacl_sdk_binaries/ /third_party/nss /third_party/openssl diff --git a/base/metrics/field_trial.cc b/base/metrics/field_trial.cc index e2d7491..94c013a 100644 --- a/base/metrics/field_trial.cc +++ b/base/metrics/field_trial.cc @@ -56,34 +56,39 @@ int FieldTrialList::kExpirationYearInFuture = 0; FieldTrial::FieldTrial(const std::string& name, const Probability total_probability, const std::string& default_group_name) - : name_(name), - divisor_(total_probability), - default_group_name_(default_group_name), - random_(static_cast<Probability>(divisor_ * RandDouble())), - accumulated_group_probability_(0), - next_group_number_(kDefaultGroupNumber + 1), - group_(kNotFinalized), - enable_field_trial_(true), - forced_(false) { + : name_(name), + divisor_(total_probability), + default_group_name_(default_group_name), + random_(static_cast<Probability>(divisor_ * RandDouble())), + accumulated_group_probability_(0), + next_group_number_(kDefaultGroupNumber + 1), + group_(kNotFinalized), + enable_field_trial_(true), + forced_(false) { DCHECK_GT(total_probability, 0); DCHECK(!name_.empty()); DCHECK(!default_group_name_.empty()); } +FieldTrial::EntropyProvider::~EntropyProvider() { +} + void FieldTrial::UseOneTimeRandomization() { // No need to specify randomization when the group choice was forced. if (forced_) return; DCHECK_EQ(group_, kNotFinalized); DCHECK_EQ(kDefaultGroupNumber + 1, next_group_number_); - if (!FieldTrialList::IsOneTimeRandomizationEnabled()) { + const EntropyProvider* entropy_provider = + FieldTrialList::GetEntropyProviderForOneTimeRandomization(); + if (!entropy_provider) { NOTREACHED(); Disable(); return; } random_ = static_cast<Probability>( - divisor_ * HashClientId(FieldTrialList::client_id(), name_)); + divisor_ * entropy_provider->GetEntropyForTrial(name_)); } void FieldTrial::Disable() { @@ -198,27 +203,6 @@ void FieldTrial::SetGroupChoice(const std::string& name, int number) { DVLOG(1) << "Field trial: " << name_ << " Group choice:" << group_name_; } -// static -double FieldTrial::HashClientId(const std::string& client_id, - const std::string& trial_name) { - // SHA-1 is designed to produce a uniformly random spread in its output space, - // even for nearly-identical inputs, so it helps massage whatever client_id - // and trial_name we get into something with a uniform distribution, which - // is desirable so that we don't skew any part of the 0-100% spectrum. - std::string input(client_id + trial_name); - unsigned char sha1_hash[kSHA1Length]; - SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()), - input.size(), - sha1_hash); - - COMPILE_ASSERT(sizeof(uint64) < sizeof(sha1_hash), need_more_data); - uint64 bits; - memcpy(&bits, sha1_hash, sizeof(bits)); - bits = base::ByteSwapToLE64(bits); - - return BitsToOpenEndedUnitInterval(bits); -} - //------------------------------------------------------------------------------ // FieldTrialList methods and members. @@ -228,9 +212,13 @@ FieldTrialList* FieldTrialList::global_ = NULL; // static bool FieldTrialList::used_without_global_ = false; -FieldTrialList::FieldTrialList(const std::string& client_id) +FieldTrialList::Observer::~Observer() { +} + +FieldTrialList::FieldTrialList( + const FieldTrial::EntropyProvider* entropy_provider) : application_start_time_(TimeTicks::Now()), - client_id_(client_id), + entropy_provider_(entropy_provider), observer_list_(new ObserverListThreadSafe<FieldTrialList::Observer>( ObserverListBase<FieldTrialList::Observer>::NOTIFY_EXISTING_ONLY)) { DCHECK(!global_); @@ -446,22 +434,19 @@ size_t FieldTrialList::GetFieldTrialCount() { } // static -bool FieldTrialList::IsOneTimeRandomizationEnabled() { +const FieldTrial::EntropyProvider* + FieldTrialList::GetEntropyProviderForOneTimeRandomization() { if (!global_) { used_without_global_ = true; - return false; + return NULL; } - return !global_->client_id_.empty(); + return global_->entropy_provider_.get(); } // static -const std::string& FieldTrialList::client_id() { - DCHECK(global_); - if (!global_) - return EmptyString(); - - return global_->client_id_; +bool FieldTrialList::IsOneTimeRandomizationEnabled() { + return GetEntropyProviderForOneTimeRandomization() != NULL; } FieldTrial* FieldTrialList::PreLockedFind(const std::string& name) { diff --git a/base/metrics/field_trial.h b/base/metrics/field_trial.h index d9a8a4a..f075f5d 100644 --- a/base/metrics/field_trial.h +++ b/base/metrics/field_trial.h @@ -95,6 +95,18 @@ class BASE_EXPORT FieldTrial : public RefCounted<FieldTrial> { public: typedef int Probability; // Probability type for being selected in a trial. + // EntropyProvider is an interface for providing entropy for one-time + // randomized (persistent) field trials. + class BASE_EXPORT EntropyProvider { + public: + virtual ~EntropyProvider(); + + // Returns a double in the range of [0, 1) based on |trial_name| that will + // be used for the dice roll for the specified field trial. A given instance + // should always return the same value given the same input |trial_name|. + virtual double GetEntropyForTrial(const std::string& trial_name) const = 0; + }; + // A pair representing a Field Trial and its selected group. struct SelectedGroup { std::string trial; @@ -203,12 +215,6 @@ class BASE_EXPORT FieldTrial : public RefCounted<FieldTrial> { // Returns the group_name. A winner need not have been chosen. std::string group_name_internal() const { return group_name_; } - // Calculates a uniformly-distributed double between [0.0, 1.0) given - // a |client_id| and a |trial_name| (the latter is used as salt to avoid - // separate one-time randomized trials from all having the same results). - static double HashClientId(const std::string& client_id, - const std::string& trial_name); - // The name of the field trial, as can be found via the FieldTrialList. const std::string name_; @@ -274,16 +280,17 @@ class BASE_EXPORT FieldTrialList { const std::string& group_name) = 0; protected: - virtual ~Observer() {} + virtual ~Observer(); }; // This singleton holds the global list of registered FieldTrials. // - // |client_id| should be an opaque, diverse ID for this client that does not - // change between sessions, to enable one-time randomized trials. The empty - // string may be provided, in which case one-time randomized trials will - // not be available. - explicit FieldTrialList(const std::string& client_id); + // To support one-time randomized field trials, specify a non-NULL + // |entropy_provider| which should be a source of uniformly distributed + // entropy values. Takes ownership of |entropy_provider|. If one time + // randomization is not desired, pass in NULL for |entropy_provider|. + explicit FieldTrialList(const FieldTrial::EntropyProvider* entropy_provider); + // Destructor Release()'s references to all registered FieldTrial instances. ~FieldTrialList(); @@ -389,17 +396,16 @@ class BASE_EXPORT FieldTrialList { // Return the number of active field trials. static size_t GetFieldTrialCount(); + // If one-time randomization is enabled, returns a weak pointer to the + // corresponding EntropyProvider. Otherwise, returns NULL. + static const FieldTrial::EntropyProvider* + GetEntropyProviderForOneTimeRandomization(); + // Returns true if you can call |FieldTrial::UseOneTimeRandomization()| - // without error, i.e. if a non-empty string was provided as the client_id - // when constructing the FieldTrialList singleton. + // without error, i.e. if a non-NULL entropy provider was specified when + // constructing the FieldTrialList singleton. static bool IsOneTimeRandomizationEnabled(); - // Returns an opaque, diverse ID for this client that does not change - // between sessions. - // - // Returns the empty string if one-time randomization is not enabled. - static const std::string& client_id(); - private: // A map from FieldTrial names to the actual instances. typedef std::map<std::string, FieldTrial*> RegistrationList; @@ -429,9 +435,9 @@ class BASE_EXPORT FieldTrialList { base::Lock lock_; RegistrationList registered_; - // An opaque, diverse ID for this client that does not change - // between sessions, or the empty string if not initialized. - std::string client_id_; + // Entropy provider to be used for one-time randomized field trials. If NULL, + // one-time randomization is not supported. + scoped_ptr<const FieldTrial::EntropyProvider> entropy_provider_; // List of observers to be notified when a group is selected for a FieldTrial. scoped_refptr<ObserverListThreadSafe<Observer> > observer_list_; diff --git a/base/metrics/field_trial_unittest.cc b/base/metrics/field_trial_unittest.cc index f5c03c42..fae2749 100644 --- a/base/metrics/field_trial_unittest.cc +++ b/base/metrics/field_trial_unittest.cc @@ -2,22 +2,17 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -// Test of FieldTrial class - #include "base/metrics/field_trial.h" - #include "base/rand_util.h" #include "base/stringprintf.h" #include "base/string_number_conversions.h" #include "testing/gtest/include/gtest/gtest.h" -#include <limits> - namespace base { class FieldTrialTest : public testing::Test { public: - FieldTrialTest() : trial_list_("client_id") { + FieldTrialTest() : trial_list_(NULL) { Time now = Time::NowFromSystemTime(); TimeDelta oneYear = TimeDelta::FromDays(365); Time::Exploded exploded; @@ -374,96 +369,6 @@ TEST_F(FieldTrialTest, MakeName) { FieldTrial::MakeName("Histogram", "Field Trial")); } -TEST_F(FieldTrialTest, HashClientId) { - double results[] = { - FieldTrial::HashClientId("hi", "1"), - FieldTrial::HashClientId("there", "1"), - }; - ASSERT_NE(results[0], results[1]); - for (size_t i = 0; i < arraysize(results); ++i) { - ASSERT_LE(0.0, results[i]); - ASSERT_GT(1.0, results[i]); - } - - ASSERT_EQ(FieldTrial::HashClientId("yo", "1"), - FieldTrial::HashClientId("yo", "1")); - ASSERT_NE(FieldTrial::HashClientId("yo", "something"), - FieldTrial::HashClientId("yo", "else")); -} - -TEST_F(FieldTrialTest, HashClientIdIsUniform) { - // Choose a random start number but go sequentially from there, so - // that each test tries a different range but we never provide uniformly - // distributed input data. - int current_number = RandInt(0, std::numeric_limits<int>::max()); - - // The expected value of a random distribution is the average over all - // samples as the number of samples approaches infinity. For a uniform - // distribution from [0.0, 1.0) this would be 0.5. - // - // We do kSamplesBetweenChecks at a time and check if the value has converged - // to a narrow interval around 0.5. A non-uniform distribution would likely - // converge at something different, or not converge consistently within this - // range (i.e. the test would start timing out occasionally). - int kSamplesBetweenChecks = 300; - int num_samples = 0; - double total_value = 0.0; - while (true) { - for (int i = 0; i < kSamplesBetweenChecks; ++i) { - total_value += FieldTrial::HashClientId( - IntToString(current_number++), "salt"); - num_samples++; - } - - double average = total_value / num_samples; - double kExpectedMin = 0.48; - double kExpectedMax = 0.52; - - if (num_samples > 1000 && - (average < kExpectedMin || average > kExpectedMax)) { - // Only printed once we have enough samples that it's very unlikely - // things haven't converged. - printf("After %d samples, the average was %f, outside the expected\n" - "range (%f, %f). We will add more samples and check after every\n" - "%d samples. If the average does not converge, something\n" - "is broken. If it does converge, the test will pass.\n", - num_samples, average, - kExpectedMin, kExpectedMax, kSamplesBetweenChecks); - } else { - // Success. - break; - } - } -} - -TEST_F(FieldTrialTest, UseOneTimeRandomization) { - // Simply asserts that two trials using one-time randomization - // that have different names, normally generate different results. - // - // Note that depending on the one-time random initialization, they - // _might_ actually give the same result, but we know that given - // the particular client_id we use for unit tests they won't. - scoped_refptr<FieldTrial> trials[] = { - FieldTrialList::FactoryGetFieldTrial("one", 100, "default", - next_year_, 1, 1, NULL), - FieldTrialList::FactoryGetFieldTrial("two", 100, "default", - next_year_, 1, 1, NULL), - }; - - for (size_t i = 0; i < arraysize(trials); ++i) { - trials[i]->UseOneTimeRandomization(); - - for (int j = 0; j < 100; ++j) { - trials[i]->AppendGroup("", 1); - } - } - - // The trials are most likely to give different results since they have - // different names. - ASSERT_NE(trials[0]->group(), trials[1]->group()); - ASSERT_NE(trials[0]->group_name(), trials[1]->group_name()); -} - TEST_F(FieldTrialTest, DisableImmediately) { int default_group_number = -1; FieldTrial* trial = FieldTrialList::FactoryGetFieldTrial( diff --git a/chrome/browser/chrome_browser_main.cc b/chrome/browser/chrome_browser_main.cc index 6c30a1f..7513faa 100644 --- a/chrome/browser/chrome_browser_main.cc +++ b/chrome/browser/chrome_browser_main.cc @@ -547,7 +547,7 @@ void ChromeBrowserMainParts::SetupMetricsAndFieldTrials() { metrics->ForceClientIdCreation(); // Needed below. field_trial_list_.reset( new base::FieldTrialList( - metrics->GetEntropySource(metrics_reporting_enabled))); + metrics->CreateEntropyProvider(metrics_reporting_enabled).release())); // Ensure any field trials specified on the command line are initialized. // Also stop the metrics service so that we don't pollute UMA. diff --git a/chrome/browser/chrome_browser_main_unittest.cc b/chrome/browser/chrome_browser_main_unittest.cc index 1ed3adf..11c1422 100644 --- a/chrome/browser/chrome_browser_main_unittest.cc +++ b/chrome/browser/chrome_browser_main_unittest.cc @@ -33,12 +33,14 @@ TEST_F(BrowserMainTest, WarmConnectionFieldTrial_WarmestSocket) { scoped_ptr<content::MainFunctionParams> params( new content::MainFunctionParams(command_line_)); - scoped_ptr<content::BrowserMainParts> bw( + scoped_ptr<content::BrowserMainParts> browser_main_parts( content::GetContentClient()->browser()->CreateBrowserMainParts(*params)); - ChromeBrowserMainParts* cbw = static_cast<ChromeBrowserMainParts*>(bw.get()); - EXPECT_TRUE(cbw); - if (cbw) { - cbw->browser_field_trials_.WarmConnectionFieldTrial(); + ChromeBrowserMainParts* chrome_main_parts = + static_cast<ChromeBrowserMainParts*>(browser_main_parts.get()); + EXPECT_TRUE(chrome_main_parts); + if (chrome_main_parts) { + base::FieldTrialList field_trial_list_(NULL); + chrome_main_parts->browser_field_trials_.WarmConnectionFieldTrial(); EXPECT_EQ(0, net::GetSocketReusePolicy()); } } @@ -46,20 +48,23 @@ TEST_F(BrowserMainTest, WarmConnectionFieldTrial_WarmestSocket) { TEST_F(BrowserMainTest, WarmConnectionFieldTrial_Random) { scoped_ptr<content::MainFunctionParams> params( new content::MainFunctionParams(command_line_)); - scoped_ptr<content::BrowserMainParts> bw( + scoped_ptr<content::BrowserMainParts> browser_main_parts( content::GetContentClient()->browser()->CreateBrowserMainParts(*params)); - ChromeBrowserMainParts* cbw = static_cast<ChromeBrowserMainParts*>(bw.get()); - EXPECT_TRUE(cbw); - if (cbw) { + ChromeBrowserMainParts* chrome_main_parts = + static_cast<ChromeBrowserMainParts*>(browser_main_parts.get()); + EXPECT_TRUE(chrome_main_parts); + if (chrome_main_parts) { const int kNumRuns = 1000; for (int i = 0; i < kNumRuns; i++) { - cbw->browser_field_trials_.WarmConnectionFieldTrial(); + base::FieldTrialList field_trial_list_(NULL); + chrome_main_parts->browser_field_trials_.WarmConnectionFieldTrial(); int val = net::GetSocketReusePolicy(); EXPECT_LE(val, 2); EXPECT_GE(val, 0); } } } + #if GTEST_HAS_DEATH_TEST TEST_F(BrowserMainTest, WarmConnectionFieldTrial_Invalid) { command_line_.AppendSwitchASCII(switches::kSocketReusePolicy, "100"); @@ -68,22 +73,23 @@ TEST_F(BrowserMainTest, WarmConnectionFieldTrial_Invalid) { new content::MainFunctionParams(command_line_)); // This test ends up launching a new process, and that doesn't initialize the // ContentClient interfaces. - scoped_ptr<content::BrowserMainParts> bw; + scoped_ptr<content::BrowserMainParts> browser_main_parts; if (content::GetContentClient()) { - bw.reset(content::GetContentClient()->browser()->CreateBrowserMainParts( - *params)); + browser_main_parts.reset(content::GetContentClient()->browser()-> + CreateBrowserMainParts(*params)); } else { - chrome::ChromeContentBrowserClient ccbc; - bw.reset(ccbc.CreateBrowserMainParts(*params)); + chrome::ChromeContentBrowserClient client; + browser_main_parts.reset(client.CreateBrowserMainParts(*params)); } - ChromeBrowserMainParts* cbw = static_cast<ChromeBrowserMainParts*>(bw.get()); - EXPECT_TRUE(cbw); - if (cbw) { + ChromeBrowserMainParts* parts = + static_cast<ChromeBrowserMainParts*>(browser_main_parts.get()); + EXPECT_TRUE(parts); + if (parts) { #if defined(NDEBUG) && defined(DCHECK_ALWAYS_ON) - EXPECT_DEATH(cbw->browser_field_trials_.WarmConnectionFieldTrial(), + EXPECT_DEATH(parts->browser_field_trials_.WarmConnectionFieldTrial(), "Not a valid socket reuse policy group"); #else - EXPECT_DEBUG_DEATH(cbw->browser_field_trials_.WarmConnectionFieldTrial(), + EXPECT_DEBUG_DEATH(parts->browser_field_trials_.WarmConnectionFieldTrial(), "Not a valid socket reuse policy group"); #endif } diff --git a/chrome/browser/metrics/metrics_service.cc b/chrome/browser/metrics/metrics_service.cc index 61a42b9..d89c9cb 100644 --- a/chrome/browser/metrics/metrics_service.cc +++ b/chrome/browser/metrics/metrics_service.cc @@ -185,6 +185,7 @@ #include "chrome/common/chrome_notification_types.h" #include "chrome/common/chrome_result_codes.h" #include "chrome/common/chrome_switches.h" +#include "chrome/common/metrics/entropy_provider.h" #include "chrome/common/metrics/metrics_log_manager.h" #include "chrome/common/net/test_server_locations.h" #include "chrome/common/pref_names.h" @@ -274,12 +275,12 @@ ResponseStatus ResponseCodeToStatus(int response_code) { // The argument used to generate a non-identifying entropy source. We want no // more than 13 bits of entropy, so use this max to return a number between 1 // and 2^13 = 8192 as the entropy source. -const uint32 kMaxEntropySize = (1 << 13); +const uint32 kMaxLowEntropySize = (1 << 13); // Generates a new non-identifying entropy source used to seed persistent // activities. int GenerateLowEntropySource() { - return base::RandInt(1, kMaxEntropySize); + return base::RandInt(0, kMaxLowEntropySize - 1); } // Converts an exit code into something that can be inserted into our @@ -344,7 +345,7 @@ std::vector<int> GetAllCrashExitCodes() { return codes; } -} +} // namespace // static MetricsService::ShutdownCleanliness MetricsService::clean_shutdown_status_ = @@ -539,7 +540,8 @@ std::string MetricsService::GetClientId() { return client_id_; } -std::string MetricsService::GetEntropySource(bool reporting_will_be_enabled) { +scoped_ptr<const base::FieldTrial::EntropyProvider> + MetricsService::CreateEntropyProvider(bool reporting_will_be_enabled) { // For metrics reporting-enabled users, we combine the client ID and low // entropy source to get the final entropy source. Otherwise, only use the low // entropy source. @@ -547,17 +549,22 @@ std::string MetricsService::GetEntropySource(bool reporting_will_be_enabled) { // 1) It makes the entropy source less identifiable for parties that do not // know the low entropy source. // 2) It makes the final entropy source resettable. - std::string low_entropy_source = base::IntToString(GetLowEntropySource()); if (reporting_will_be_enabled) { if (entropy_source_returned_ == LAST_ENTROPY_NONE) entropy_source_returned_ = LAST_ENTROPY_HIGH; DCHECK_EQ(LAST_ENTROPY_HIGH, entropy_source_returned_); - return client_id_ + low_entropy_source; + const std::string high_entropy_source = + client_id_ + base::IntToString(GetLowEntropySource()); + return scoped_ptr<const base::FieldTrial::EntropyProvider>( + new metrics::SHA1EntropyProvider(high_entropy_source)); } + if (entropy_source_returned_ == LAST_ENTROPY_NONE) entropy_source_returned_ = LAST_ENTROPY_LOW; DCHECK_EQ(LAST_ENTROPY_LOW, entropy_source_returned_); - return low_entropy_source; + return scoped_ptr<const base::FieldTrial::EntropyProvider>( + new metrics::PermutedEntropyProvider(GetLowEntropySource(), + kMaxLowEntropySize)); } void MetricsService::ForceClientIdCreation() { diff --git a/chrome/browser/metrics/metrics_service.h b/chrome/browser/metrics/metrics_service.h index aa4bf9e..ff2d5eb 100644 --- a/chrome/browser/metrics/metrics_service.h +++ b/chrome/browser/metrics/metrics_service.h @@ -16,6 +16,7 @@ #include "base/gtest_prod_util.h" #include "base/memory/scoped_ptr.h" #include "base/memory/weak_ptr.h" +#include "base/metrics/field_trial.h" #include "base/process_util.h" #include "chrome/browser/metrics/metrics_log.h" #include "chrome/browser/metrics/tracking_synchronizer_observer.h" @@ -86,16 +87,21 @@ class MetricsService // recording is not currently running. std::string GetClientId(); - // Returns the preferred entropy source used to seed persistent activities - // based on whether or not metrics reporting will permitted on this client. + // Returns the preferred entropy provider used to seed persistent activities + // based on whether or not metrics reporting will be permitted on this client. // The caller must determine if metrics reporting will be enabled for this - // client and pass that state in as |reporting_will_be_enabled|. If - // |reporting_will_be_enabled| is true, this method returns the client ID - // concatenated with the low entropy source. Otherwise, this method just - // returns the low entropy source. Note that this reporting state can not be - // checked by reporting_active() because this method may need to be called - // before the MetricsService needs to be started. - std::string GetEntropySource(bool reporting_will_be_enabled); + // client and pass that state in as |reporting_will_be_enabled|. + // + // If |reporting_will_be_enabled| is true, this method returns an entropy + // provider that has a high source of entropy, partially based on the client + // ID. Otherwise, an entropy provider that is based on a low entropy source + // is returned. + // + // Note that this reporting state can not be checked by reporting_active() + // because this method may need to be called before the MetricsService needs + // to be started. + scoped_ptr<const base::FieldTrial::EntropyProvider> CreateEntropyProvider( + bool reporting_will_be_enabled); // Force the client ID to be generated. This is useful in case it's needed // before recording. diff --git a/chrome/chrome_common.gypi b/chrome/chrome_common.gypi index 2291fda..693c618 100644 --- a/chrome/chrome_common.gypi +++ b/chrome/chrome_common.gypi @@ -49,6 +49,7 @@ '<(DEPTH)/third_party/icu/icu.gyp:icui18n', '<(DEPTH)/third_party/icu/icu.gyp:icuuc', '<(DEPTH)/third_party/libxml/libxml.gyp:libxml', + '<(DEPTH)/third_party/mt19937ar/mt19937ar.gyp:mt19937ar', '<(DEPTH)/third_party/sqlite/sqlite.gyp:sqlite', '<(DEPTH)/third_party/zlib/zlib.gyp:zlib', '<(DEPTH)/ui/ui.gyp:ui_resources', @@ -231,6 +232,8 @@ 'common/mac/objc_method_swizzle.mm', 'common/mac/objc_zombie.h', 'common/mac/objc_zombie.mm', + 'common/metrics/entropy_provider.cc', + 'common/metrics/entropy_provider.h', 'common/metrics/metrics_log_base.cc', 'common/metrics/metrics_log_base.h', 'common/metrics/metrics_log_manager.cc', diff --git a/chrome/chrome_tests.gypi b/chrome/chrome_tests.gypi index c285485..2b2d4cea 100644 --- a/chrome/chrome_tests.gypi +++ b/chrome/chrome_tests.gypi @@ -1998,6 +1998,7 @@ 'common/mac/mock_launchd.h', 'common/mac/objc_method_swizzle_unittest.mm', 'common/mac/objc_zombie_unittest.mm', + 'common/metrics/entropy_provider_unittest.cc', 'common/metrics/metrics_log_base_unittest.cc', 'common/metrics/metrics_log_manager_unittest.cc', 'common/metrics/variations/variations_util_unittest.cc', diff --git a/chrome/common/DEPS b/chrome/common/DEPS index d88605d..fa87567 100644 --- a/chrome/common/DEPS +++ b/chrome/common/DEPS @@ -23,6 +23,7 @@ include_rules = [ # Other libraries. "+chrome/third_party/xdg_user_dirs", "+third_party/bzip2", + "+third_party/mt19937ar", "+third_party/npapi", "+third_party/sqlite", "+third_party/zlib", diff --git a/chrome/common/metrics/entropy_provider.cc b/chrome/common/metrics/entropy_provider.cc new file mode 100644 index 0000000..ac7c063 --- /dev/null +++ b/chrome/common/metrics/entropy_provider.cc @@ -0,0 +1,124 @@ +// 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 "chrome/common/metrics/entropy_provider.h" + +#include <algorithm> +#include <limits> +#include <vector> + +#include "base/logging.h" +#include "base/rand_util.h" +#include "base/sha1.h" +#include "base/sys_byteorder.h" + +namespace metrics { + +namespace internal { + +SeededRandGenerator::SeededRandGenerator(uint32 seed) { + mersenne_twister_.init_genrand(seed); +} + +SeededRandGenerator::~SeededRandGenerator() { +} + +uint32 SeededRandGenerator::operator()(uint32 range) { + // Based on base::RandGenerator(). + DCHECK_GT(range, 0u); + + // We must discard random results above this number, as they would + // make the random generator non-uniform (consider e.g. if + // MAX_UINT64 was 7 and |range| was 5, then a result of 1 would be twice + // as likely as a result of 3 or 4). + uint32 max_acceptable_value = + (std::numeric_limits<uint32>::max() / range) * range - 1; + + uint32 value; + do { + value = mersenne_twister_.genrand_int32(); + } while (value > max_acceptable_value); + + return value % range; +} + +uint32 HashName(const std::string& name) { + // SHA-1 is designed to produce a uniformly random spread in its output space, + // even for nearly-identical inputs. + unsigned char sha1_hash[base::kSHA1Length]; + base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(name.c_str()), + name.size(), + sha1_hash); + + uint32 bits; + COMPILE_ASSERT(sizeof(bits) < sizeof(sha1_hash), need_more_data); + memcpy(&bits, sha1_hash, sizeof(bits)); + + return base::ByteSwapToLE32(bits); +} + +void PermuteMappingUsingTrialName(const std::string& trial_name, + std::vector<uint16>* mapping) { + for (size_t i = 0; i < mapping->size(); ++i) + (*mapping)[i] = static_cast<uint16>(i); + + SeededRandGenerator generator(HashName(trial_name)); + std::random_shuffle(mapping->begin(), mapping->end(), generator); +} + +} // namespace internal + +SHA1EntropyProvider::SHA1EntropyProvider(const std::string& entropy_source) + : entropy_source_(entropy_source) { +} + +SHA1EntropyProvider::~SHA1EntropyProvider() { +} + +double SHA1EntropyProvider::GetEntropyForTrial( + const std::string& trial_name) const { + // Given enough input entropy, SHA-1 will produce a uniformly random spread + // in its output space. In this case, the input entropy that is used is the + // combination of the original |entropy_source_| and the |trial_name|. + // + // Note: If |entropy_source_| has very low entropy, such as 13 bits or less, + // it has been observed that this method does not result in a uniform + // distribution given the same |trial_name|. When using such a low entropy + // source, PermutedEntropyProvider should be used instead. + std::string input(entropy_source_ + trial_name); + unsigned char sha1_hash[base::kSHA1Length]; + base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()), + input.size(), + sha1_hash); + + uint64 bits; + COMPILE_ASSERT(sizeof(bits) < sizeof(sha1_hash), need_more_data); + memcpy(&bits, sha1_hash, sizeof(bits)); + bits = base::ByteSwapToLE64(bits); + + return base::BitsToOpenEndedUnitInterval(bits); +} + +PermutedEntropyProvider::PermutedEntropyProvider( + uint16 low_entropy_source, + size_t low_entropy_source_max) + : low_entropy_source_(low_entropy_source), + low_entropy_source_max_(low_entropy_source_max) { + DCHECK_LT(low_entropy_source, low_entropy_source_max); + DCHECK_LE(low_entropy_source_max, std::numeric_limits<uint16>::max()); +} + +PermutedEntropyProvider::~PermutedEntropyProvider() { +} + +double PermutedEntropyProvider::GetEntropyForTrial( + const std::string& trial_name) const { + std::vector<uint16> mapping(low_entropy_source_max_); + internal::PermuteMappingUsingTrialName(trial_name, &mapping); + + return mapping[low_entropy_source_] / + static_cast<double>(low_entropy_source_max_); +} + +} // namespace metrics diff --git a/chrome/common/metrics/entropy_provider.h b/chrome/common/metrics/entropy_provider.h new file mode 100644 index 0000000..2058457 --- /dev/null +++ b/chrome/common/metrics/entropy_provider.h @@ -0,0 +1,95 @@ +// 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. + +#ifndef CHROME_COMMON_METRICS_ENTROPY_PROVIDER_H_ +#define CHROME_COMMON_METRICS_ENTROPY_PROVIDER_H_ + +#include <functional> +#include <string> +#include <vector> + +#include "base/base_export.h" +#include "base/basictypes.h" +#include "base/compiler_specific.h" +#include "base/metrics/field_trial.h" +#include "third_party/mt19937ar/mt19937ar.h" + +namespace metrics { + +// Internals of entropy_provider.cc exposed for testing. +namespace internal { + +// A functor that generates random numbers based on a seed, using the Mersenne +// Twister algorithm. Suitable for use with std::random_shuffle(). +struct SeededRandGenerator : std::unary_function<uint32, uint32> { + explicit SeededRandGenerator(uint32 seed); + ~SeededRandGenerator(); + + // Returns a random number in range [0, range). + uint32 operator()(uint32 range); + + MersenneTwister mersenne_twister_; +}; + +// Creates unique identifier for the trial by hashing a name string, whether +// it's for the field trial or the group name. +// TODO(asvitkine): Share the implementation with variations_util.cc. +uint32 HashName(const std::string& name); + +// Fills |mapping| to create a bijection of values in the range of +// [0, |mapping.size()|), permuted based on |trial_name|. +void PermuteMappingUsingTrialName(const std::string& trial_name, + std::vector<uint16>* mapping); + +} // namespace internal + +// SHA1EntropyProvider is an entropy provider suitable for high entropy +// sources. It works by taking the first 64 bits of the SHA1 hash of the +// entropy source concatenated with the trial name and using that for the +// final entropy value. +class SHA1EntropyProvider : public base::FieldTrial::EntropyProvider { + public: + // Creates a SHA1EntropyProvider with the given |entropy_source|, which + // should contain a large amount of entropy - for example, a textual + // representation of a persistent randomly-generated 128-bit value. + explicit SHA1EntropyProvider(const std::string& entropy_source); + virtual ~SHA1EntropyProvider(); + + // base::FieldTrial::EntropyProvider implementation: + virtual double GetEntropyForTrial(const std::string& trial_name) const + OVERRIDE; + + private: + std::string entropy_source_; + + DISALLOW_COPY_AND_ASSIGN(SHA1EntropyProvider); +}; + +// PermutedEntropyProvider is an entropy provider suitable for low entropy +// sources (below 16 bits). It uses the field trial name to generate a +// permutation of a mapping array from an initial entropy value to a new value. +// Note: This provider's performance is O(2^n), where n is the number of bits +// in the entropy source. +class PermutedEntropyProvider : public base::FieldTrial::EntropyProvider { + public: + // Creates a PermutedEntropyProvider with the given |low_entropy_source|, + // which should have a value in the range of [0, low_entropy_source_max). + PermutedEntropyProvider(uint16 low_entropy_source, + size_t low_entropy_source_max); + virtual ~PermutedEntropyProvider(); + + // base::FieldTrial::EntropyProvider implementation: + virtual double GetEntropyForTrial(const std::string& trial_name) const + OVERRIDE; + + private: + uint16 low_entropy_source_; + size_t low_entropy_source_max_; + + DISALLOW_COPY_AND_ASSIGN(PermutedEntropyProvider); +}; + +} // namespace metrics + +#endif // CHROME_COMMON_METRICS_ENTROPY_PROVIDER_H_ diff --git a/chrome/common/metrics/entropy_provider_unittest.cc b/chrome/common/metrics/entropy_provider_unittest.cc new file mode 100644 index 0000000..b54a5d5 --- /dev/null +++ b/chrome/common/metrics/entropy_provider_unittest.cc @@ -0,0 +1,337 @@ +// 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 <cmath> +#include <limits> +#include <numeric> + +#include "base/basictypes.h" +#include "base/guid.h" +#include "base/memory/scoped_ptr.h" +#include "base/rand_util.h" +#include "base/string_number_conversions.h" +#include "chrome/common/metrics/entropy_provider.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace metrics { + +namespace { + +// Size of the low entropy source to use for the permuted entropy provider +// in tests. +const size_t kMaxLowEntropySize = (1 << 13); + +// Field trial names used in unit tests. +const std::string kTestTrialNames[] = { "TestTrial", "AnotherTestTrial", + "NewTabButton" }; + +// Computes the Chi-Square statistic for |values| assuming they follow a uniform +// distribution, where each entry has expected value |expected_value|. +// +// The Chi-Square statistic is defined as Sum((O-E)^2/E) where O is the observed +// value and E is the expected value. +double ComputeChiSquare(const std::vector<int>& values, + double expected_value) { + double sum = 0; + for (size_t i = 0; i < values.size(); ++i) { + const double delta = values[i] - expected_value; + sum += (delta * delta) / expected_value; + } + return sum; +} + +// Computes SHA1-based entropy for the given |trial_name| based on +// |entropy_source| +double GenerateSHA1Entropy(const std::string& entropy_source, + const std::string& trial_name) { + SHA1EntropyProvider sha1_provider(entropy_source); + return sha1_provider.GetEntropyForTrial(trial_name); +} + +// Generates permutation-based entropy for the given |trial_name| based on +// |entropy_source| which must be in the range [0, entropy_max). +double GeneratePermutedEntropy(uint16 entropy_source, + size_t entropy_max, + const std::string& trial_name) { + PermutedEntropyProvider permuted_provider(entropy_source, entropy_max); + return permuted_provider.GetEntropyForTrial(trial_name); +} + +// Helper interface for testing used to generate entropy values for a given +// field trial. Unlike EntropyProvider, which keeps the low/high entropy source +// value constant and generates entropy for different trial names, instances +// of TrialEntropyGenerator keep the trial name constant and generate low/high +// entropy source values internally to produce each output entropy value. +class TrialEntropyGenerator { + public: + virtual ~TrialEntropyGenerator() {} + virtual double GenerateEntropyValue() const = 0; +}; + +// An TrialEntropyGenerator that uses the SHA1EntropyProvider with the high +// entropy source (random GUID with 128 bits of entropy + 13 additional bits of +// entropy corresponding to a low entropy source). +class SHA1EntropyGenerator : public TrialEntropyGenerator { + public: + explicit SHA1EntropyGenerator(const std::string& trial_name) + : trial_name_(trial_name) { + } + + ~SHA1EntropyGenerator() { + } + + virtual double GenerateEntropyValue() const OVERRIDE { + // Use a random GUID + 13 additional bits of entropy to match how the + // SHA1EntropyProvider is used in metrics_service.cc. + const int low_entropy_source = + static_cast<uint16>(base::RandInt(0, kMaxLowEntropySize - 1)); + const std::string high_entropy_source = + base::GenerateGUID() + base::IntToString(low_entropy_source); + return GenerateSHA1Entropy(high_entropy_source, trial_name_); + } + + private: + const std::string& trial_name_; + + DISALLOW_COPY_AND_ASSIGN(SHA1EntropyGenerator); +}; + +// An TrialEntropyGenerator that uses the permuted entropy provider algorithm, +// using 13-bit low entropy source values. +class PermutedEntropyGenerator : public TrialEntropyGenerator { + public: + explicit PermutedEntropyGenerator(const std::string& trial_name) + : mapping_(kMaxLowEntropySize) { + // Note: Given a trial name, the computed mapping will be the same. + // As a performance optimization, pre-compute the mapping once per trial + // name and index into it for each entropy value. + internal::PermuteMappingUsingTrialName(trial_name, &mapping_); + } + + ~PermutedEntropyGenerator() { + } + + virtual double GenerateEntropyValue() const OVERRIDE { + const int low_entropy_source = + static_cast<uint16>(base::RandInt(0, kMaxLowEntropySize - 1)); + return mapping_[low_entropy_source] / + static_cast<double>(kMaxLowEntropySize); + } + + private: + std::vector<uint16> mapping_; + + DISALLOW_COPY_AND_ASSIGN(PermutedEntropyGenerator); +}; + +// Tests uniformity of a given |entropy_generator| using the Chi-Square Goodness +// of Fit Test. +void PerformEntropyUniformityTest( + const std::string& trial_name, + const TrialEntropyGenerator& entropy_generator) { + // Number of buckets in the simulated field trials. + const size_t kBucketCount = 20; + // Max number of iterations to perform before giving up and failing. + const size_t kMaxIterationCount = 100000; + // The number of iterations to perform before each time the statistical + // significance of the results is checked. + const size_t kCheckIterationCount = 10000; + // This is the Chi-Square threshold from the Chi-Square statistic table for + // 19 degrees of freedom (based on |kBucketCount|) with a 99.9% confidence + // level. See: http://www.medcalc.org/manual/chi-square-table.php + const double kChiSquareThreshold = 43.82; + + std::vector<int> distribution(kBucketCount); + + for (size_t i = 1; i <= kMaxIterationCount; ++i) { + const double entropy_value = entropy_generator.GenerateEntropyValue(); + const size_t bucket = static_cast<size_t>(kBucketCount * entropy_value); + ASSERT_LT(bucket, kBucketCount); + distribution[bucket] += 1; + + // After |kCheckIterationCount| iterations, compute the Chi-Square + // statistic of the distribution. If the resulting statistic is greater + // than |kChiSquareThreshold|, we can conclude with 99.9% confidence + // that the observed samples do not follow a uniform distribution. + // + // However, since 99.9% would still result in a false negative every + // 1000 runs of the test, do not treat it as a failure (else the test + // will be flaky). Instead, perform additional iterations to determine + // if the distribution will converge, up to |kMaxIterationCount|. + if ((i % kCheckIterationCount) == 0) { + const double expected_value_per_bucket = + static_cast<double>(i) / kBucketCount; + const double chi_square = + ComputeChiSquare(distribution, expected_value_per_bucket); + if (chi_square < kChiSquareThreshold) + break; + + // If |i == kMaxIterationCount|, the Chi-Square statistic did not + // converge after |kMaxIterationCount|. + EXPECT_NE(i, kMaxIterationCount) << "Failed for trial " << + trial_name << " with chi_square = " << chi_square << + " after " << kMaxIterationCount << " iterations."; + } + } +} + +} // namespace + +class EntropyProviderTest : public testing::Test { +}; + +TEST_F(EntropyProviderTest, UseOneTimeRandomizationSHA1) { + // Simply asserts that two trials using one-time randomization + // that have different names, normally generate different results. + // + // Note that depending on the one-time random initialization, they + // _might_ actually give the same result, but we know that given + // the particular client_id we use for unit tests they won't. + base::FieldTrialList field_trial_list(new SHA1EntropyProvider("client_id")); + scoped_refptr<base::FieldTrial> trials[] = { + base::FieldTrialList::FactoryGetFieldTrial("one", 100, "default", + base::FieldTrialList::kExpirationYearInFuture, 1, 1, NULL), + base::FieldTrialList::FactoryGetFieldTrial("two", 100, "default", + base::FieldTrialList::kExpirationYearInFuture, 1, 1, NULL) }; + + for (size_t i = 0; i < arraysize(trials); ++i) { + trials[i]->UseOneTimeRandomization(); + + for (int j = 0; j < 100; ++j) + trials[i]->AppendGroup("", 1); + } + + // The trials are most likely to give different results since they have + // different names. + EXPECT_NE(trials[0]->group(), trials[1]->group()); + EXPECT_NE(trials[0]->group_name(), trials[1]->group_name()); +} + +TEST_F(EntropyProviderTest, UseOneTimeRandomizationPermuted) { + // Simply asserts that two trials using one-time randomization + // that have different names, normally generate different results. + // + // Note that depending on the one-time random initialization, they + // _might_ actually give the same result, but we know that given + // the particular client_id we use for unit tests they won't. + base::FieldTrialList field_trial_list( + new PermutedEntropyProvider(1234, kMaxLowEntropySize)); + scoped_refptr<base::FieldTrial> trials[] = { + base::FieldTrialList::FactoryGetFieldTrial("one", 100, "default", + base::FieldTrialList::kExpirationYearInFuture, 1, 1, NULL), + base::FieldTrialList::FactoryGetFieldTrial("two", 100, "default", + base::FieldTrialList::kExpirationYearInFuture, 1, 1, NULL) }; + + for (size_t i = 0; i < arraysize(trials); ++i) { + trials[i]->UseOneTimeRandomization(); + + for (int j = 0; j < 100; ++j) + trials[i]->AppendGroup("", 1); + } + + // The trials are most likely to give different results since they have + // different names. + EXPECT_NE(trials[0]->group(), trials[1]->group()); + EXPECT_NE(trials[0]->group_name(), trials[1]->group_name()); +} + +TEST_F(EntropyProviderTest, SHA1Entropy) { + const double results[] = { GenerateSHA1Entropy("hi", "1"), + GenerateSHA1Entropy("there", "1") }; + + EXPECT_NE(results[0], results[1]); + for (size_t i = 0; i < arraysize(results); ++i) { + EXPECT_LE(0.0, results[i]); + EXPECT_GT(1.0, results[i]); + } + + EXPECT_EQ(GenerateSHA1Entropy("yo", "1"), + GenerateSHA1Entropy("yo", "1")); + EXPECT_NE(GenerateSHA1Entropy("yo", "something"), + GenerateSHA1Entropy("yo", "else")); +} + +TEST_F(EntropyProviderTest, PermutedEntropy) { + const double results[] = { + GeneratePermutedEntropy(1234, kMaxLowEntropySize, "1"), + GeneratePermutedEntropy(4321, kMaxLowEntropySize, "1") }; + + EXPECT_NE(results[0], results[1]); + for (size_t i = 0; i < arraysize(results); ++i) { + EXPECT_LE(0.0, results[i]); + EXPECT_GT(1.0, results[i]); + } + + EXPECT_EQ(GeneratePermutedEntropy(1234, kMaxLowEntropySize, "1"), + GeneratePermutedEntropy(1234, kMaxLowEntropySize, "1")); + EXPECT_NE(GeneratePermutedEntropy(1234, kMaxLowEntropySize, "something"), + GeneratePermutedEntropy(1234, kMaxLowEntropySize, "else")); +} + +TEST_F(EntropyProviderTest, PermutedEntropyProviderResults) { + // Verifies that PermutedEntropyProvider produces expected results. This + // ensures that the results are the same between platforms and ensures that + // changes to the implementation do not regress this accidentally. + + EXPECT_DOUBLE_EQ(2194 / static_cast<double>(kMaxLowEntropySize), + GeneratePermutedEntropy(1234, kMaxLowEntropySize, "XYZ")); + EXPECT_DOUBLE_EQ(5676 / static_cast<double>(kMaxLowEntropySize), + GeneratePermutedEntropy(1, kMaxLowEntropySize, "Test")); + EXPECT_DOUBLE_EQ(1151 / static_cast<double>(kMaxLowEntropySize), + GeneratePermutedEntropy(5000, kMaxLowEntropySize, "Foo")); +} + +TEST_F(EntropyProviderTest, SHA1EntropyIsUniform) { + for (size_t i = 0; i < arraysize(kTestTrialNames); ++i) { + SHA1EntropyGenerator entropy_generator(kTestTrialNames[i]); + PerformEntropyUniformityTest(kTestTrialNames[i], entropy_generator); + } +} + +TEST_F(EntropyProviderTest, PermutedEntropyIsUniform) { + for (size_t i = 0; i < arraysize(kTestTrialNames); ++i) { + PermutedEntropyGenerator entropy_generator(kTestTrialNames[i]); + PerformEntropyUniformityTest(kTestTrialNames[i], entropy_generator); + } +} + +TEST_F(EntropyProviderTest, SeededRandGeneratorIsUniform) { + // Verifies that SeededRandGenerator has a uniform distribution. + // + // Mirrors RandUtilTest.RandGeneratorIsUniform in base/rand_util_unittest.cc. + + const uint32 kTopOfRange = (std::numeric_limits<uint32>::max() / 4ULL) * 3ULL; + const uint32 kExpectedAverage = kTopOfRange / 2ULL; + const uint32 kAllowedVariance = kExpectedAverage / 50ULL; // +/- 2% + const int kMinAttempts = 1000; + const int kMaxAttempts = 1000000; + + for (size_t i = 0; i < arraysize(kTestTrialNames); ++i) { + const uint32 seed = internal::HashName(kTestTrialNames[i]); + internal::SeededRandGenerator rand_generator(seed); + + double cumulative_average = 0.0; + int count = 0; + while (count < kMaxAttempts) { + uint32 value = rand_generator(kTopOfRange); + cumulative_average = (count * cumulative_average + value) / (count + 1); + + // Don't quit too quickly for things to start converging, or we may have + // a false positive. + if (count > kMinAttempts && + kExpectedAverage - kAllowedVariance < cumulative_average && + cumulative_average < kExpectedAverage + kAllowedVariance) { + break; + } + + ++count; + } + + ASSERT_LT(count, kMaxAttempts) << "Expected average was " << + kExpectedAverage << ", average ended at " << cumulative_average << + ", for trial " << kTestTrialNames[i]; + } +} + +} // namespace metrics diff --git a/chrome/common/metrics/variations/variations_util_unittest.cc b/chrome/common/metrics/variations/variations_util_unittest.cc index 24d8fd4..63567f3 100644 --- a/chrome/common/metrics/variations/variations_util_unittest.cc +++ b/chrome/common/metrics/variations/variations_util_unittest.cc @@ -30,7 +30,7 @@ chrome_variations::VariationID GetIDForTrial(base::FieldTrial* trial) { class VariationsHelperTest : public ::testing::Test { public: - VariationsHelperTest() { + VariationsHelperTest() : field_trial_list_(NULL) { // Since the API can only be called on the UI thread, we have to fake that // we're on it. ui_thread_.reset(new content::TestBrowserThread( @@ -49,6 +49,7 @@ class VariationsHelperTest : public ::testing::Test { int next_year_; private: + base::FieldTrialList field_trial_list_; MessageLoop message_loop_; scoped_ptr<content::TestBrowserThread> ui_thread_; }; diff --git a/chrome_frame/chrome_tab.cc b/chrome_frame/chrome_tab.cc index 68e553e..2611d69 100644 --- a/chrome_frame/chrome_tab.cc +++ b/chrome_frame/chrome_tab.cc @@ -28,6 +28,7 @@ #include "base/win/windows_version.h" #include "chrome/common/chrome_constants.h" #include "chrome/common/chrome_switches.h" +#include "chrome/common/metrics/entropy_provider.h" #include "chrome/installer/util/google_update_settings.h" #include "chrome_frame/bho.h" #include "chrome_frame/chrome_active_document.h" @@ -860,7 +861,7 @@ extern "C" BOOL WINAPI DllMain(HINSTANCE instance, // Initialize the field test infrastructure. Must be done somewhere that // can only get called once. For Chrome Frame, that is here. g_field_trial_list = new base::FieldTrialList( - MetricsService::GetClientID()); + new metrics::SHA1EntropyProvider(MetricsService::GetClientID())); } else if (reason == DLL_PROCESS_DETACH) { delete g_field_trial_list; g_field_trial_list = NULL; diff --git a/chrome_frame/test/run_all_unittests.cc b/chrome_frame/test/run_all_unittests.cc index 88e6f5c..b0f502e 100644 --- a/chrome_frame/test/run_all_unittests.cc +++ b/chrome_frame/test/run_all_unittests.cc @@ -11,6 +11,7 @@ #include "base/threading/platform_thread.h" #include "base/win/scoped_com_initializer.h" #include "chrome/common/chrome_paths.h" +#include "chrome/common/metrics/entropy_provider.h" #include "chrome/test/logging/win/test_log_collector.h" #include "chrome_frame/crash_server_init.h" #include "chrome_frame/test/chrome_frame_test_utils.h" @@ -54,7 +55,7 @@ int main(int argc, char **argv) { // Set up a FieldTrialList to keep any field trials we have going in // Chrome Frame happy. - base::FieldTrialList field_trial_list("42"); + base::FieldTrialList field_trial_list(new metrics::SHA1EntropyProvider("42")); base::TestSuite test_suite(argc, argv); diff --git a/content/renderer/renderer_main.cc b/content/renderer/renderer_main.cc index cba9a31..e827686 100644 --- a/content/renderer/renderer_main.cc +++ b/content/renderer/renderer_main.cc @@ -185,10 +185,10 @@ int RendererMain(const content::MainFunctionParams& parameters) { // Initialize histogram statistics gathering system. base::StatisticsRecorder::Initialize(); - // Initialize statistical testing infrastructure. We set client_id to the - // empty string to disallow the renderer process from creating its own - // one-time randomized trials; they should be created in the browser process. - base::FieldTrialList field_trial(EmptyString()); + // Initialize statistical testing infrastructure. We set the entropy provider + // to NULL to disallow the renderer process from creating its own one-time + // randomized trials; they should be created in the browser process. + base::FieldTrialList field_trial_list(NULL); // Ensure any field trials in browser are reflected into renderer. if (parsed_command_line.HasSwitch(switches::kForceFieldTrials)) { std::string persistent = parsed_command_line.GetSwitchValueASCII( diff --git a/third_party/mt19937ar/LICENSE b/third_party/mt19937ar/LICENSE new file mode 100644 index 0000000..ad6051b4 --- /dev/null +++ b/third_party/mt19937ar/LICENSE @@ -0,0 +1,35 @@ + A C-program for MT19937, with initialization improved 2002/1/26. + Coded by Takuji Nishimura and Makoto Matsumoto. + + Before using, initialize the state by using init_genrand(seed) + or init_by_array(init_key, key_length). + + Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + 3. The names of its contributors may not be used to endorse or promote + products derived from this software without specific prior written + permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/third_party/mt19937ar/README.chromium b/third_party/mt19937ar/README.chromium new file mode 100644 index 0000000..75cf4bcb9 --- /dev/null +++ b/third_party/mt19937ar/README.chromium @@ -0,0 +1,19 @@ +Name: mt19937ar +URL: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html +Version: 0 +Date: 2002/1/26 +License: BSD +Security Critical: yes + +Description: +This is Chrome's locally patched copy of Takuji Nishimura and Makoto +Matsumoto's Mersenne Twister pseudorandom number generator. + +Note: Once Chromium moves to C++11, this can be removed in favor +of C++'s <random>. + +Local Modifications: +Renamed mt19937ar.c to mt19937ar.cc and modified it to encapsulate its +state in a C++ class, rather than using global state. Changed the code to +use uint32 types instead of unsigned longs. Added a header file. +Additionally, unnecessary functions (in particular, main) were removed. diff --git a/third_party/mt19937ar/mt19937ar.cc b/third_party/mt19937ar/mt19937ar.cc new file mode 100644 index 0000000..d121e99 --- /dev/null +++ b/third_party/mt19937ar/mt19937ar.cc @@ -0,0 +1,140 @@ +/* + A C-program for MT19937, with initialization improved 2002/1/26. + Coded by Takuji Nishimura and Makoto Matsumoto. + + Before using, initialize the state by using init_genrand(seed) + or init_by_array(init_key, key_length). + + Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + 3. The names of its contributors may not be used to endorse or promote + products derived from this software without specific prior written + permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + + Any feedback is very welcome. + http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html + email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space) +*/ + +#include "mt19937ar.h" + +/* Period parameters */ +#define N 624 +#define M 397 +#define MATRIX_A 0x9908b0dfUL /* constant vector a */ +#define UPPER_MASK 0x80000000UL /* most significant w-r bits */ +#define LOWER_MASK 0x7fffffffUL /* least significant r bits */ + +MersenneTwister::MersenneTwister() : mt(N), mti(N+1) { +} + +MersenneTwister::~MersenneTwister() { +} + +/* initializes mt[N] with a seed */ +void MersenneTwister::init_genrand(uint32 s) +{ + mt[0]= s & 0xffffffffUL; + for (mti=1; mti<N; mti++) { + mt[mti] = + (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); + /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ + /* In the previous versions, MSBs of the seed affect */ + /* only MSBs of the array mt[]. */ + /* 2002/01/09 modified by Makoto Matsumoto */ + mt[mti] &= 0xffffffffUL; + /* for >32 bit machines */ + } +} + +/* initialize by an array with array-length */ +/* init_key is the array for initializing keys */ +/* key_length is its length */ +/* slight change for C++, 2004/2/26 */ +void MersenneTwister::init_by_array(uint32 init_key[], int key_length) +{ + int i, j, k; + init_genrand(19650218UL); + i=1; j=0; + k = (N>key_length ? N : key_length); + for (; k; k--) { + mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL)) + + init_key[j] + j; /* non linear */ + mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ + i++; j++; + if (i>=N) { mt[0] = mt[N-1]; i=1; } + if (j>=key_length) j=0; + } + for (k=N-1; k; k--) { + mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL)) + - i; /* non linear */ + mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ + i++; + if (i>=N) { mt[0] = mt[N-1]; i=1; } + } + + mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */ +} + +/* generates a random number on [0,0xffffffff]-interval */ +uint32 MersenneTwister::genrand_int32(void) +{ + uint32 y; + static uint32 mag01[2]={0x0UL, MATRIX_A}; + /* mag01[x] = x * MATRIX_A for x=0,1 */ + + if (mti >= N) { /* generate N words at one time */ + int kk; + + if (mti == N+1) /* if init_genrand() has not been called, */ + init_genrand(5489UL); /* a default initial seed is used */ + + for (kk=0;kk<N-M;kk++) { + y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); + mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL]; + } + for (;kk<N-1;kk++) { + y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); + mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL]; + } + y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK); + mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL]; + + mti = 0; + } + + y = mt[mti++]; + + /* Tempering */ + y ^= (y >> 11); + y ^= (y << 7) & 0x9d2c5680UL; + y ^= (y << 15) & 0xefc60000UL; + y ^= (y >> 18); + + return y; +} diff --git a/third_party/mt19937ar/mt19937ar.gyp b/third_party/mt19937ar/mt19937ar.gyp new file mode 100644 index 0000000..6ea8d31 --- /dev/null +++ b/third_party/mt19937ar/mt19937ar.gyp @@ -0,0 +1,19 @@ +# 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. + +{ + 'targets': [ + { + 'target_name': 'mt19937ar', + 'type': 'static_library', + 'sources': [ + 'mt19937ar.cc', + 'mt19937ar.h', + ], + 'include_dirs': [ + '../..', + ], + }, + ], +} diff --git a/third_party/mt19937ar/mt19937ar.h b/third_party/mt19937ar/mt19937ar.h new file mode 100644 index 0000000..31c6960 --- /dev/null +++ b/third_party/mt19937ar/mt19937ar.h @@ -0,0 +1,65 @@ +/* + A C-program for MT19937, with initialization improved 2002/1/26. + Coded by Takuji Nishimura and Makoto Matsumoto. + + Before using, initialize the state by using init_genrand(seed) + or init_by_array(init_key, key_length). + + Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + 3. The names of its contributors may not be used to endorse or promote + products derived from this software without specific prior written + permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + + Any feedback is very welcome. + http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html + email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space) + */ + +#ifndef THIRD_PARTY_MT19937AR_MT19937AR_H_ +#define THIRD_PARTY_MT19937AR_MT19937AR_H_ + +#include <vector> + +#include "base/basictypes.h" + +class MersenneTwister { + public: + MersenneTwister(); + ~MersenneTwister(); + + void init_genrand(uint32 s); + void init_by_array(uint32 init_key[], int key_length); + uint32 genrand_int32(void); + + private: + std::vector<uint32> mt; /* the array for the state vector */ + int mti; /* mti==N+1 means mt[N] is not initialized */ +}; + +#endif // THIRD_PARTY_MT19937AR_MT19937AR_H_ diff --git a/third_party/mt19937ar/readme-mt.txt b/third_party/mt19937ar/readme-mt.txt new file mode 100644 index 0000000..c3a9c41 --- /dev/null +++ b/third_party/mt19937ar/readme-mt.txt @@ -0,0 +1,74 @@ +This is a Mersenne Twister pseudorandom number generator +with period 2^19937-1 with improved initialization scheme, +modified on 2002/1/26 by Takuji Nishimura and Makoto Matsumoto. + +Contents of this tar ball: +readme-mt.txt this file +mt19937ar.c the C source (ar: initialize by ARray) +mt19937ar.out Test outputs of six types generators. 1000 for each + +1. Initialization + The initialization scheme for the previous versions of MT +(e.g. 1999/10/28 version or earlier) has a tiny problem, that +the most significant bits of the seed is not well reflected +to the state vector of MT. + +This version (2002/1/26) has two initialization schemes: +init_genrand(seed) and init_by_array(init_key, key_length). + +init_genrand(seed) initializes the state vector by using +one unsigned 32-bit integer "seed", which may be zero. + +init_by_array(init_key, key_length) initializes the state vector +by using an array init_key[] of unsigned 32-bit integers +of length key_kength. If key_length is smaller than 624, +then each array of 32-bit integers gives distinct initial +state vector. This is useful if you want a larger seed space +than 32-bit word. + +2. Generation +After initialization, the following type of pseudorandom numbers +are available. + +genrand_int32() generates unsigned 32-bit integers. +genrand_int31() generates unsigned 31-bit integers. +genrand_real1() generates uniform real in [0,1] (32-bit resolution). +genrand_real2() generates uniform real in [0,1) (32-bit resolution). +genrand_real3() generates uniform real in (0,1) (32-bit resolution). +genrand_res53() generates uniform real in [0,1) with 53-bit resolution. + +Note: the last five functions call the first one. +if you need more speed for these five functions, you may +suppress the function call by copying genrand_int32() and +replacing the last return(), following to these five functions. + +3. main() +main() is an example to initialize with an array of length 4, +then 1000 outputs of unsigned 32-bit integers, +then 1000 outputs of real [0,1) numbers. + +4. The outputs +The output of the mt19937ar.c is in the file mt19937ar.out. +If you revise or translate the code, check the output +by using this file. + +5. Cryptography +This generator is not cryptoraphically secure. +You need to use a one-way (or hash) function to obtain +a secure random sequence. + +6. Correspondence +See: +URL http://www.math.keio.ac.jp/matumoto/emt.html +email matumoto@math.keio.ac.jp, nisimura@sci.kj.yamagata-u.ac.jp + +7. Reference +M. Matsumoto and T. Nishimura, +"Mersenne Twister: A 623-Dimensionally Equidistributed Uniform +Pseudo-Random Number Generator", +ACM Transactions on Modeling and Computer Simulation, +Vol. 8, No. 1, January 1998, pp 3--30. + +------- +Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, +All rights reserved. |