PM: Get a random value between [min, max].
This is required for generating random values used for scattering. In
doing so, we shift to using an STL provided generator and distribution
function.
BUG=chromium:358323
TEST=Unit tests.
Change-Id: I6e758605f1d8123ab73a81906ecf7ad83c5e6cb9
Reviewed-on: https://chromium-review.googlesource.com/198780
Tested-by: Gilad Arnold <garnold@chromium.org>
Reviewed-by: Alex Vakulenko <avakulenko@chromium.org>
Commit-Queue: Gilad Arnold <garnold@chromium.org>
diff --git a/policy_manager/chromeos_policy.cc b/policy_manager/chromeos_policy.cc
index 436dc73..eb50887 100644
--- a/policy_manager/chromeos_policy.cc
+++ b/policy_manager/chromeos_policy.cc
@@ -5,6 +5,7 @@
#include "update_engine/policy_manager/chromeos_policy.h"
#include "update_engine/policy_manager/policy_utils.h"
+#include <algorithm>
#include <string>
using base::Time;
@@ -87,18 +88,13 @@
}
TimeDelta ChromeOSPolicy::FuzzedInterval(PRNG* prng, int interval, int fuzz) {
+ DCHECK_GE(interval, 0);
+ DCHECK_GE(fuzz, 0);
int half_fuzz = fuzz / 2;
- int lower_bound = interval - half_fuzz;
- int upper_bound = interval + half_fuzz + 1;
-
// This guarantees the output interval is non negative.
- if (lower_bound < 0)
- lower_bound = 0;
-
- int fuzzed_interval = lower_bound;
- if (upper_bound - lower_bound > 0)
- fuzzed_interval = lower_bound + prng->rand() % (upper_bound - lower_bound);
- return TimeDelta::FromSeconds(fuzzed_interval);
+ int interval_min = std::max(interval - half_fuzz, 0);
+ int interval_max = interval + half_fuzz;
+ return TimeDelta::FromSeconds(prng->RandMinMax(interval_min, interval_max));
}
} // namespace chromeos_policy_manager
diff --git a/policy_manager/prng.h b/policy_manager/prng.h
index 2922e9f..2063bb2 100644
--- a/policy_manager/prng.h
+++ b/policy_manager/prng.h
@@ -5,25 +5,31 @@
#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_PRNG_H_
#define CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_PRNG_H_
-#include <cstdlib>
+#include <random>
-#include <base/basictypes.h>
+#include <base/logging.h>
namespace chromeos_policy_manager {
-// An unsecure Pseudo-Random Number Generator class based on rand_r(3), which
-// is thread safe and doesn't interfere with other calls to rand().
+// A thread-safe, unsecure, 32-bit pseudo-random number generator based on
+// std::mt19937.
class PRNG {
public:
- // Creates the object using the passed |seed| value as the initial state.
- explicit PRNG(unsigned int seed) : state_(seed) {}
+ // Initializes the generator with the passed |seed| value.
+ explicit PRNG(uint32_t seed) : gen_(seed) {}
- // Returns a pseudo-random integer in the range [0, RAND_MAX].
- int rand() { return rand_r(&state_); }
+ // Returns a random unsigned 32-bit integer.
+ uint32_t Rand() { return gen_(); }
+
+ // Returns a random integer uniformly distributed in the range [min, max].
+ int RandMinMax(int min, int max) {
+ DCHECK_LE(min, max);
+ return std::uniform_int_distribution<>(min, max)(gen_);
+ }
private:
- // The internal state of the PRNG.
- unsigned int state_;
+ // A pseudo-random number generator.
+ std::mt19937 gen_;
DISALLOW_COPY_AND_ASSIGN(PRNG);
};
diff --git a/policy_manager/prng_unittest.cc b/policy_manager/prng_unittest.cc
index 4bdf836..cbe7690 100644
--- a/policy_manager/prng_unittest.cc
+++ b/policy_manager/prng_unittest.cc
@@ -17,7 +17,7 @@
PRNG b(42);
for (int i = 0; i < 1000; ++i) {
- EXPECT_EQ(a.rand(), b.rand()) << "Iteration i=" << i;
+ EXPECT_EQ(a.Rand(), b.Rand()) << "Iteration i=" << i;
}
}
@@ -25,12 +25,12 @@
PRNG a(42);
PRNG b(5);
- vector<int> values_a;
- vector<int> values_b;
+ vector<uint32_t> values_a;
+ vector<uint32_t> values_b;
for (int i = 0; i < 100; ++i) {
- values_a.push_back(a.rand());
- values_b.push_back(b.rand());
+ values_a.push_back(a.Rand());
+ values_b.push_back(b.Rand());
}
EXPECT_NE(values_a, values_b);
}
@@ -38,10 +38,10 @@
TEST(PmPRNGTest, IsNotConstant) {
PRNG prng(5);
- int initial_value = prng.rand();
+ uint32_t initial_value = prng.Rand();
bool prng_is_constant = true;
for (int i = 0; i < 100; ++i) {
- if (prng.rand() != initial_value) {
+ if (prng.Rand() != initial_value) {
prng_is_constant = false;
break;
}
@@ -49,4 +49,19 @@
EXPECT_FALSE(prng_is_constant) << "After 100 iterations.";
}
+TEST(PmPRNGTest, RandCoversRange) {
+ PRNG a(42);
+ int hits[11] = { 0 };
+
+ for (int i = 0; i < 1000; i++) {
+ int r = a.RandMinMax(0, 10);
+ ASSERT_LE(0, r);
+ ASSERT_GE(10, r);
+ hits[r]++;
+ }
+
+ for (auto& hit : hits)
+ EXPECT_LT(0, hit);
+}
+
} // namespace chromeos_policy_manager