From 68a546c7cdd7df99b436a0d26c2ef7bb766fe435 Mon Sep 17 00:00:00 2001
From: Sergey Doroshenko <sdoroshenko@fb.com>
Date: Tue, 14 Aug 2012 12:54:49 -0700
Subject: [PATCH] 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
---
 folly/Random.cpp          |  9 ++++++-
 folly/test/RandomTest.cpp | 52 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 60 insertions(+), 1 deletion(-)
 create mode 100644 folly/test/RandomTest.cpp

diff --git a/folly/Random.cpp b/folly/Random.cpp
index 13664ce8..98109621 100644
--- 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
index 00000000..c8b96d2d
--- /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]);
+  }
+}
-- 
2.34.1