folly: randomNumberSeed should be random wrt multiple threads

Summary:
Right now, it relies on process id rather than on thread id. Thus, it can
return the same seed when called from multiple threads over really short
period of time, and these unlucky threads will end up with identical "random"
sequences.

Test Plan: newly added test fails against trunk, passes against changes in the diff

Reviewed By: tudorb@fb.com

FB internal diff: D548129

diff --git a/folly/Random.cpp b/folly/Random.cpp
index 13664ce8420bbd1c3b68dbe7ef450dd4658b0717..981096214504417e9ec4710e306aeef7eff28386 100644 (file)
--- a/folly/Random.cpp
+++ b/folly/Random.cpp
@@ -16,18 +16,25 @@
 
 #include "folly/Random.h"
 
+#include <atomic>
 #include <unistd.h>
 #include <sys/time.h>
 
 namespace folly {
 
+namespace {
+std::atomic<uint32_t> seedInput(0);
+}
+
 uint32_t randomNumberSeed() {
   struct timeval tv;
   gettimeofday(&tv, NULL);
+  const uint32_t kPrime0 = 51551;
   const uint32_t kPrime1 = 61631;
   const uint32_t kPrime2 = 64997;
   const uint32_t kPrime3 = 111857;
-  return kPrime1 * static_cast<uint32_t>(getpid())
+  return kPrime0 * (seedInput++)
+       + kPrime1 * static_cast<uint32_t>(getpid())
        + kPrime2 * static_cast<uint32_t>(tv.tv_sec)
        + kPrime3 * static_cast<uint32_t>(tv.tv_usec);
 }

diff --git a/folly/test/RandomTest.cpp b/folly/test/RandomTest.cpp
new file mode 100644 (file)
index 0000000..c8b96d2
--- /dev/null
+++ b/folly/test/RandomTest.cpp
@@ -0,0 +1,52 @@
+/*
+ * Copyright 2012 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "folly/Random.h"
+
+#include <glog/logging.h>
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <thread>
+#include <vector>
+
+using namespace folly;
+
+TEST(Random, Simple) {
+  uint32_t prev = 0, seed = 0;
+  for (int i = 0; i < 1024; ++i) {
+    EXPECT_NE(seed = randomNumberSeed(), prev);
+    prev = seed;
+  }
+}
+
+TEST(Random, MultiThreaded) {
+  const int n = 1024;
+  std::vector<uint32_t> seeds(n);
+  std::vector<std::thread> threads;
+  for (int i = 0; i < n; ++i) {
+    threads.push_back(std::thread([i, &seeds] {
+      seeds[i] = randomNumberSeed();
+    }));
+  }
+  for (auto& t : threads) {
+    t.join();
+  }
+  std::sort(seeds.begin(), seeds.end());
+  for (int i = 0; i < n-1; ++i) {
+    EXPECT_LT(seeds[i], seeds[i+1]);
+  }
+}