Index: include/llvm/IR/LLVMContext.h =================================================================== --- include/llvm/IR/LLVMContext.h +++ include/llvm/IR/LLVMContext.h @@ -31,6 +31,7 @@ template class SmallVectorImpl; class Function; class DebugLoc; +class RandomNumberGenerator; /// This is an important class for using LLVM in a threaded context. It /// (opaquely) owns and manages the core "global" data of LLVM's core @@ -136,6 +137,12 @@ void emitOptimizationRemark(const char *PassName, const Function &Fn, const DebugLoc &DLoc, const Twine &Msg); + /// Gets the RandomNumberGenerator for this thread. The RNG can be + /// seeded via -rng-seed= and is re-salted for every module that + /// is added to the context. This method relies on the assumption that + /// there is one LLVMContext per thread. + RandomNumberGenerator &getRNG() const; + private: LLVMContext(LLVMContext&) LLVM_DELETED_FUNCTION; void operator=(LLVMContext&) LLVM_DELETED_FUNCTION; Index: include/llvm/Support/RandomNumberGenerator.h =================================================================== --- /dev/null +++ include/llvm/Support/RandomNumberGenerator.h @@ -0,0 +1,50 @@ +//==- 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 + +namespace llvm { + +class RandomNumberGenerator { +public: + /// Seeds the underlying RNG engine, if -rng-seed= was given. + /// Note that this class should not be instantiated directly. + /// Instead, an instance can be retrieved from the current LLVMContext. + /// \see LLVMContext::getRNG + RandomNumberGenerator(); + + /// Adds additional entropy to the random number stream. This method is + /// intended to be called from LLVMContext::addModule. + void addSalt(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 Index: lib/IR/LLVMContext.cpp =================================================================== --- lib/IR/LLVMContext.cpp +++ lib/IR/LLVMContext.cpp @@ -20,7 +20,9 @@ #include "llvm/IR/DiagnosticPrinter.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Metadata.h" +#include "llvm/IR/Module.h" #include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/Path.h" #include "llvm/Support/SourceMgr.h" #include using namespace llvm; @@ -71,6 +73,14 @@ void LLVMContext::addModule(Module *M) { pImpl->OwnedModules.insert(M); + + // Re-salt the RNG every time we add a module to increase security. + // We want reproducible builds, but the module ID may be a full path so we + // just use the filename (although it is not guaranteed to be unique). + // This relies on the assumption that there is one LLVMContext per thread. + std::string ModuleID = M->getModuleIdentifier(); + StringRef Filename = sys::path::filename(ModuleID); + pImpl->RNG.addSalt(Filename); } void LLVMContext::removeModule(Module *M) { @@ -173,6 +183,10 @@ diagnose(DiagnosticInfoOptimizationRemark(PassName, Fn, DLoc, Msg)); } +RandomNumberGenerator &LLVMContext::getRNG() const { + return pImpl->RNG; +} + //===----------------------------------------------------------------------===// // Metadata Kind Uniquing //===----------------------------------------------------------------------===// Index: lib/IR/LLVMContextImpl.h =================================================================== --- lib/IR/LLVMContextImpl.h +++ lib/IR/LLVMContextImpl.h @@ -31,6 +31,7 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/ValueHandle.h" +#include "llvm/Support/RandomNumberGenerator.h" #include namespace llvm { @@ -368,6 +369,9 @@ typedef DenseMap PrefixDataMapTy; PrefixDataMapTy PrefixDataMap; + /// The Random Number Generator for this context. + RandomNumberGenerator RNG; + /// \brief Return true if the given pass name should emit optimization /// remarks. bool optimizationRemarksEnabledFor(const char *PassName) const; Index: lib/Support/CMakeLists.txt =================================================================== --- lib/Support/CMakeLists.txt +++ lib/Support/CMakeLists.txt @@ -40,6 +40,7 @@ MD5.cpp PluginLoader.cpp PrettyStackTrace.cpp + RandomNumberGenerator.cpp Regex.cpp SmallPtrSet.cpp SmallVector.cpp Index: lib/Support/RandomNumberGenerator.cpp =================================================================== --- /dev/null +++ lib/Support/RandomNumberGenerator.cpp @@ -0,0 +1,57 @@ +//===-- 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; + +// TODO(D3390) +// 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() : Generator(Seed.getValue()) { + errs() << Seed.getValue() << "\n"; + errs() << Seed << "\n"; + DEBUG( + if (Seed == 0) + errs() << "Warning! Using unseeded random number generator.\n" + ); +} + +uint64_t RandomNumberGenerator::next(uint64_t Max) { + std::uniform_int_distribution distribution(0, Max - 1); + return distribution(Generator); +} + +void RandomNumberGenerator::addSalt(StringRef Salt) { + DEBUG(dbgs() << "Salting RNG: " << Salt << "\n"); + + uint64_t S = Generator(); + + // Sequence: Seed-low, Seed-high, Salt... + size_t Size = Salt.size() + 2; + uint32_t Data[Size]; + Data[0] = S; + Data[1] = S >> 32; + std::copy_n(Salt.begin(), Salt.size(), Data + 2); + + std::seed_seq SeedSeq(Data, Data + Size); + Generator.seed(SeedSeq); +}