Use a different algorithm with the low entropy source for field trials.
The new algorithm maps the original 13-bit low entropy source to a
new 13-bit entropy value using a mapping that is shuffled using the
trial name as a seed.
The algorithm is roughly as follows:
Take the low entropy source as an integer between 0-8191.
Generate an identity mapping of size 8192 where mapping[i] == i.
Seed a Mersenne Twister random number generator with the hash of the field trial name.
Use the seeded random number generator to shuffle the mapping array.
Map the low entropy source using the mapping array, i.e. entropy' = mapping[entropy].
Divide the resulting entropy' by 8192 to produce a double in the range of [0, 1) that
will be used for bucketing in field_trial.cc.
The above algorithm improves uniformity over the existing entropy provider when
the 13-bit entropy source is used while still providing very little overlaps of
buckets between different field trials.
Adds third_party library mt19937ar, an implementation of Mersenne Twister, for
the seeded random number generation. This is needed until C++11 becomes available
for use in Chromium, at which point C++11's <random> could be used.
BUG=143239
TEST=Unit tests. Additionally, verified that the new algorithm produces uniform results
with very little overlap of buckets between different field trials.
Review URL: https://chromiumcodereview.appspot.com/10830318
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@153322 0039d316-1c4b-4281-b951-d872f2087c98
diff --git a/chrome/browser/metrics/metrics_service.cc b/chrome/browser/metrics/metrics_service.cc
index 61a42b9..d89c9cba 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 @@
// 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 @@
return codes;
}
-}
+} // namespace
// static
MetricsService::ShutdownCleanliness MetricsService::clean_shutdown_status_ =
@@ -539,7 +540,8 @@
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 @@
// 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() {
