From b4840d7a4d357b3f79071cccdeaadefe278b912a Mon Sep 17 00:00:00 2001 From: JF Bastien Date: Wed, 25 Jun 2014 15:21:42 +0000 Subject: [PATCH] Random Number Generator (llvm) Provides an abstraction for a random number generator (RNG) that produces a stream of pseudo-random numbers. The current implementation uses C++11 facilities and is therefore not cryptographically secure. The RNG is salted with the text of the current command line invocation. In addition, a user may specify a seed (reproducible builds). In clang, the seed can be set via -frandom-seed=X In the back end, the seed can be set via -rng-seed=X This is the llvm part of the patch. clang part: D3391 URL: http://reviews.llvm.org/D3390 Author: yln I'm landing this for the second time, it broke Windows bots the first time around. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211705 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/Module.h | 8 +++ include/llvm/Support/RandomNumberGenerator.h | 54 +++++++++++++++++ lib/IR/Module.cpp | 15 ++++- lib/Support/CMakeLists.txt | 1 + lib/Support/RandomNumberGenerator.cpp | 61 ++++++++++++++++++++ 5 files changed, 138 insertions(+), 1 deletion(-) create mode 100644 include/llvm/Support/RandomNumberGenerator.h create mode 100644 lib/Support/RandomNumberGenerator.cpp diff --git a/include/llvm/IR/Module.h b/include/llvm/IR/Module.h index 7230df9f795..77e5d21e29a 100644 --- a/include/llvm/IR/Module.h +++ b/include/llvm/IR/Module.h @@ -29,6 +29,7 @@ namespace llvm { class FunctionType; class GVMaterializer; class LLVMContext; +class RandomNumberGenerator; class StructType; template struct DenseMapInfo; template class DenseMap; @@ -201,6 +202,8 @@ private: std::string ModuleID; ///< Human readable identifier for the module std::string TargetTriple; ///< Platform target triple Module compiled on void *NamedMDSymTab; ///< NamedMDNode names. + // Allow lazy initialization in const method. + mutable RandomNumberGenerator *RNG; ///< The random number generator for this module. // We need to keep the string because the C API expects us to own the string // representation. @@ -249,6 +252,11 @@ public: /// @returns a string containing the module-scope inline assembly blocks. const std::string &getModuleInlineAsm() const { return GlobalScopeAsm; } + /// Get the RandomNumberGenerator for this module. The RNG can be + /// seeded via -rng-seed= and is salted with the ModuleID. + /// The returned RNG should not be shared across threads. + RandomNumberGenerator &getRNG() const; + /// @} /// @name Module Level Mutators /// @{ diff --git a/include/llvm/Support/RandomNumberGenerator.h b/include/llvm/Support/RandomNumberGenerator.h new file mode 100644 index 00000000000..1ec2c7eca94 --- /dev/null +++ b/include/llvm/Support/RandomNumberGenerator.h @@ -0,0 +1,54 @@ +//==- llvm/Support/RandomNumberGenerator.h - RNG for diversity ---*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines an abstraction for random number generation (RNG). +// Note that the current implementation is not cryptographically secure +// as it uses the C++11 facilities. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_ +#define LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H_ + +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/DataTypes.h" // Needed for uint64_t on Windows. +#include + +namespace llvm { + +/// A random number generator. +/// Instances of this class should not be shared across threads. +class RandomNumberGenerator { +public: + /// Seeds and salts the underlying RNG engine. The salt of type StringRef + /// is passed into the constructor. The seed can be set on the command + /// line via -rng-seed=. + /// The reason for the salt is to ensure different random streams even if + /// the same seed is used for multiple invocations of the compiler. + /// A good salt value should add additional entropy and be constant across + /// different machines (i.e., no paths) to allow for reproducible builds. + /// An instance of this class can be retrieved from the current Module. + /// \see Module::getRNG + RandomNumberGenerator(StringRef Salt); + + /// Returns a random number in the range [0, Max). + uint64_t next(uint64_t Max); + +private: + // 64-bit Mersenne Twister by Matsumoto and Nishimura, 2000 + // http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine + std::mt19937_64 Generator; + + // Noncopyable. + RandomNumberGenerator(const RandomNumberGenerator &other) = delete; + RandomNumberGenerator &operator=(const RandomNumberGenerator &other) = delete; +}; +} + +#endif diff --git a/lib/IR/Module.cpp b/lib/IR/Module.cpp index eea14df3f38..9889f009742 100644 --- a/lib/IR/Module.cpp +++ b/lib/IR/Module.cpp @@ -24,6 +24,8 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/LeakDetector.h" #include "llvm/Support/Dwarf.h" +#include "llvm/Support/Path.h" +#include "llvm/Support/RandomNumberGenerator.h" #include #include #include @@ -44,7 +46,7 @@ template class llvm::SymbolTableListTraits; // Module::Module(StringRef MID, LLVMContext &C) - : Context(C), Materializer(), ModuleID(MID), DL("") { + : Context(C), Materializer(), ModuleID(MID), RNG(nullptr), DL("") { ValSymTab = new ValueSymbolTable(); NamedMDSymTab = new StringMap(); Context.addModule(this); @@ -59,6 +61,7 @@ Module::~Module() { NamedMDList.clear(); delete ValSymTab; delete static_cast *>(NamedMDSymTab); + delete RNG; } /// getNamedValue - Return the first global value in the module with @@ -355,6 +358,16 @@ const DataLayout *Module::getDataLayout() const { return &DL; } +// We want reproducible builds, but ModuleID may be a full path so we just use +// the filename to salt the RNG (although it is not guaranteed to be unique). +RandomNumberGenerator &Module::getRNG() const { + if (RNG == nullptr) { + StringRef Salt = sys::path::filename(ModuleID); + RNG = new RandomNumberGenerator(Salt); + } + return *RNG; +} + //===----------------------------------------------------------------------===// // Methods to control the materialization of GlobalValues in the Module. // diff --git a/lib/Support/CMakeLists.txt b/lib/Support/CMakeLists.txt index 354e2003b58..033eae041c5 100644 --- a/lib/Support/CMakeLists.txt +++ b/lib/Support/CMakeLists.txt @@ -41,6 +41,7 @@ add_llvm_library(LLVMSupport MD5.cpp PluginLoader.cpp PrettyStackTrace.cpp + RandomNumberGenerator.cpp Regex.cpp ScaledNumber.cpp SmallPtrSet.cpp diff --git a/lib/Support/RandomNumberGenerator.cpp b/lib/Support/RandomNumberGenerator.cpp new file mode 100644 index 00000000000..c50e7cb8fbe --- /dev/null +++ b/lib/Support/RandomNumberGenerator.cpp @@ -0,0 +1,61 @@ +//===-- RandomNumberGenerator.cpp - Implement RNG class -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements random number generation (RNG). +// The current implementation is NOT cryptographically secure as it uses +// the C++11 facilities. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "rng" +#include "llvm/Support/RandomNumberGenerator.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +// Tracking BUG: 19665 +// http://llvm.org/bugs/show_bug.cgi?id=19665 +// +// Do not change to cl::opt since this silently breaks argument parsing. +static cl::opt +Seed("rng-seed", cl::value_desc("seed"), + cl::desc("Seed for the random number generator"), cl::init(0)); + +RandomNumberGenerator::RandomNumberGenerator(StringRef Salt) { + DEBUG( + if (Seed == 0) + errs() << "Warning! Using unseeded random number generator.\n" + ); + + // Combine seed and salt using std::seed_seq. + // Entropy: Seed-low, Seed-high, Salt... + std::vector Data; + Data.reserve(2 + Salt.size()/4 + 1); + Data.push_back(Seed); + Data.push_back(Seed >> 32); + + uint32_t Pack = 0; + for (size_t I = 0; I < Salt.size(); ++I) { + Pack <<= 8; + Pack += Salt[I]; + + if (I%4 == 3) + Data.push_back(Pack); + } + Data.push_back(Pack); + + std::seed_seq SeedSeq(Data.begin(), Data.end()); + Generator.seed(SeedSeq); +} + +uint64_t RandomNumberGenerator::next(uint64_t Max) { + std::uniform_int_distribution distribution(0, Max - 1); + return distribution(Generator); +} -- 2.34.1