From bed94589f27d7fdfa34ede5988203369d170cec3 Mon Sep 17 00:00:00 2001 From: Laramie Leavitt Date: Thu, 2 Jun 2022 10:08:08 -0700 Subject: Rework NonsecureURBGBase seed sequence. Decompose RandenPoolSeedSeq from NonsecureURBGBase. Adjust how the RandenPoolSeedSeq detects contiguous buffers passed to the generate function. Previously it made incorrect assumptions regarding the contiguous concept, which have been replaced with some type-based tests for a small number of known contiguous random access iterator types, including raw pointers. PiperOrigin-RevId: 452564114 Change-Id: Idab1df9dd078d8e5c565c7fa7ccb9c0d3d392ad2 --- absl/random/CMakeLists.txt | 2 +- absl/random/internal/BUILD.bazel | 2 +- absl/random/internal/nonsecure_base.h | 107 +++++++++++++++------------- absl/random/internal/nonsecure_base_test.cc | 66 +++++++---------- absl/random/internal/salted_seed_seq.h | 50 +++++++------ 5 files changed, 109 insertions(+), 118 deletions(-) (limited to 'absl/random') diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index b4ada69b..c3f0b450 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt @@ -727,7 +727,7 @@ absl_cc_library( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::core_headers - absl::optional + absl::inlined_vector absl::random_internal_pool_urbg absl::random_internal_salted_seed_seq absl::random_internal_seed_material diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index 73535e5b..69f9f80c 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel @@ -222,8 +222,8 @@ cc_library( ":salted_seed_seq", ":seed_material", "//absl/base:core_headers", + "//absl/container:inlined_vector", "//absl/meta:type_traits", - "//absl/types:optional", "//absl/types:span", ], ) diff --git a/absl/random/internal/nonsecure_base.h b/absl/random/internal/nonsecure_base.h index 730fa2ea..c7d7fa4b 100644 --- a/absl/random/internal/nonsecure_base.h +++ b/absl/random/internal/nonsecure_base.h @@ -17,28 +17,82 @@ #include #include -#include #include -#include -#include #include +#include #include #include "absl/base/macros.h" +#include "absl/container/inlined_vector.h" #include "absl/meta/type_traits.h" #include "absl/random/internal/pool_urbg.h" #include "absl/random/internal/salted_seed_seq.h" #include "absl/random/internal/seed_material.h" -#include "absl/types/optional.h" #include "absl/types/span.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace random_internal { +// RandenPoolSeedSeq is a custom seed sequence type where generate() fills the +// provided buffer via the RandenPool entropy source. +class RandenPoolSeedSeq { + private: + struct ContiguousTag {}; + struct BufferTag {}; + + // Generate random unsigned values directly into the buffer. + template + void generate_impl(ContiguousTag, Contiguous begin, Contiguous end) { + const size_t n = std::distance(begin, end); + auto* a = &(*begin); + RandenPool::Fill( + absl::MakeSpan(reinterpret_cast(a), sizeof(*a) * n)); + } + + // Construct a buffer of size n and fill it with values, then copy + // those values into the seed iterators. + template + void generate_impl(BufferTag, RandomAccessIterator begin, + RandomAccessIterator end) { + const size_t n = std::distance(begin, end); + absl::InlinedVector data(n, 0); + RandenPool::Fill(absl::MakeSpan(data.begin(), data.end())); + std::copy(std::begin(data), std::end(data), begin); + } + + public: + using result_type = uint32_t; + + size_t size() { return 0; } + + template + void param(OutIterator) const {} + + template + void generate(RandomAccessIterator begin, RandomAccessIterator end) { + // RandomAccessIterator must be assignable from uint32_t + if (begin != end) { + using U = typename std::iterator_traits::value_type; + // ContiguousTag indicates the common case of a known contiguous buffer, + // which allows directly filling the buffer. In C++20, + // std::contiguous_iterator_tag provides a mechanism for testing this + // capability, however until Abseil's support requirements allow us to + // assume C++20, limit checks to a few common cases. + using TagType = absl::conditional_t< + (std::is_pointer::value || + std::is_same::iterator>::value), + ContiguousTag, BufferTag>; + + generate_impl(TagType{}, begin, end); + } + } +}; + // Each instance of NonsecureURBGBase will be seeded by variates produced // by a thread-unique URBG-instance. -template +template class NonsecureURBGBase { public: using result_type = typename URBG::result_type; @@ -85,49 +139,6 @@ class NonsecureURBGBase { } private: - // Seeder is a custom seed sequence type where generate() fills the provided - // buffer via the RandenPool entropy source. - struct Seeder { - using result_type = uint32_t; - - size_t size() { return 0; } - - template - void param(OutIterator) const {} - - template - void generate(RandomAccessIterator begin, RandomAccessIterator end) { - if (begin != end) { - // begin, end must be random access iterators assignable from uint32_t. - generate_impl( - std::integral_constant{}, - begin, end); - } - } - - // Commonly, generate is invoked with a pointer to a buffer which - // can be cast to a uint32_t. - template - void generate_impl(std::integral_constant, - RandomAccessIterator begin, RandomAccessIterator end) { - auto buffer = absl::MakeSpan(begin, end); - auto target = absl::MakeSpan(reinterpret_cast(buffer.data()), - buffer.size()); - RandenPool::Fill(target); - } - - // The non-uint32_t case should be uncommon, and involves an extra copy, - // filling the uint32_t buffer and then mixing into the output. - template - void generate_impl(std::integral_constant, - RandomAccessIterator begin, RandomAccessIterator end) { - const size_t n = std::distance(begin, end); - absl::InlinedVector data(n, 0); - RandenPool::Fill(absl::MakeSpan(data.begin(), data.end())); - std::copy(std::begin(data), std::end(data), begin); - } - }; - static URBG ConstructURBG() { Seeder seeder; return URBG(seeder); diff --git a/absl/random/internal/nonsecure_base_test.cc b/absl/random/internal/nonsecure_base_test.cc index 698027fc..3502243e 100644 --- a/absl/random/internal/nonsecure_base_test.cc +++ b/absl/random/internal/nonsecure_base_test.cc @@ -15,6 +15,7 @@ #include "absl/random/internal/nonsecure_base.h" #include +#include #include #include #include @@ -192,54 +193,35 @@ TEST(NonsecureURBGBase, EqualSeedSequencesYieldEqualVariates) { } } -// This is a PRNG-compatible type specifically designed to test -// that NonsecureURBGBase::Seeder can correctly handle iterators -// to arbitrary non-uint32_t size types. -template -struct SeederTestEngine { - using result_type = T; +TEST(RandenPoolSeedSeqTest, SeederWorksForU32) { + absl::random_internal::RandenPoolSeedSeq seeder; - static constexpr result_type(min)() { - return (std::numeric_limits::min)(); - } - static constexpr result_type(max)() { - return (std::numeric_limits::max)(); - } - - template ::value>> - explicit SeederTestEngine(SeedSequence&& seq) { - seed(seq); - } - - SeederTestEngine(const SeederTestEngine&) = default; - SeederTestEngine& operator=(const SeederTestEngine&) = default; - SeederTestEngine(SeederTestEngine&&) = default; - SeederTestEngine& operator=(SeederTestEngine&&) = default; + uint32_t state[2] = {0, 0}; + seeder.generate(std::begin(state), std::end(state)); + EXPECT_FALSE(state[0] == 0 && state[1] == 0); +} - result_type operator()() { return state[0]; } +TEST(RandenPoolSeedSeqTest, SeederWorksForU64) { + absl::random_internal::RandenPoolSeedSeq seeder; - template - void seed(SeedSequence&& seq) { - std::fill(std::begin(state), std::end(state), T(0)); - seq.generate(std::begin(state), std::end(state)); - } + uint64_t state[2] = {0, 0}; + seeder.generate(std::begin(state), std::end(state)); + EXPECT_FALSE(state[0] == 0 && state[1] == 0); + EXPECT_FALSE((state[0] >> 32) == 0 && (state[1] >> 32) == 0); +} - T state[2]; -}; +TEST(RandenPoolSeedSeqTest, SeederWorksForS32) { + absl::random_internal::RandenPoolSeedSeq seeder; -TEST(NonsecureURBGBase, SeederWorksForU32) { - using U32 = - absl::random_internal::NonsecureURBGBase>; - U32 x; - EXPECT_NE(0, x()); + int32_t state[2] = {0, 0}; + seeder.generate(std::begin(state), std::end(state)); + EXPECT_FALSE(state[0] == 0 && state[1] == 0); } -TEST(NonsecureURBGBase, SeederWorksForU64) { - using U64 = - absl::random_internal::NonsecureURBGBase>; +TEST(RandenPoolSeedSeqTest, SeederWorksForVector) { + absl::random_internal::RandenPoolSeedSeq seeder; - U64 x; - EXPECT_NE(0, x()); + std::vector state(2); + seeder.generate(std::begin(state), std::end(state)); + EXPECT_FALSE(state[0] == 0 && state[1] == 0); } diff --git a/absl/random/internal/salted_seed_seq.h b/absl/random/internal/salted_seed_seq.h index 5953a090..06291865 100644 --- a/absl/random/internal/salted_seed_seq.h +++ b/absl/random/internal/salted_seed_seq.h @@ -22,6 +22,7 @@ #include #include #include +#include #include "absl/container/inlined_vector.h" #include "absl/meta/type_traits.h" @@ -65,15 +66,19 @@ class SaltedSeedSeq { template void generate(RandomAccessIterator begin, RandomAccessIterator end) { + using U = typename std::iterator_traits::value_type; + // The common case is that generate is called with ContiguousIterators // to uint arrays. Such contiguous memory regions may be optimized, // which we detect here. - using tag = absl::conditional_t< - (std::is_pointer::value && - std::is_same, uint32_t>::value), + using TagType = absl::conditional_t< + (std::is_same::value && + (std::is_pointer::value || + std::is_same::iterator>::value)), ContiguousAndUint32Tag, DefaultTag>; if (begin != end) { - generate_impl(begin, end, tag{}); + generate_impl(TagType{}, begin, end, std::distance(begin, end)); } } @@ -89,8 +94,15 @@ class SaltedSeedSeq { struct DefaultTag {}; // Generate which requires the iterators are contiguous pointers to uint32_t. - void generate_impl(uint32_t* begin, uint32_t* end, ContiguousAndUint32Tag) { - generate_contiguous(absl::MakeSpan(begin, end)); + // Fills the initial seed buffer the underlying SSeq::generate() call, + // then mixes in the salt material. + template + void generate_impl(ContiguousAndUint32Tag, Contiguous begin, Contiguous end, + size_t n) { + seq_->generate(begin, end); + const uint32_t salt = absl::random_internal::GetSaltMaterial().value_or(0); + auto span = absl::Span(&*begin, n); + MixIntoSeedMaterial(absl::MakeConstSpan(&salt, 1), span); } // The uncommon case for generate is that it is called with iterators over @@ -98,27 +110,13 @@ class SaltedSeedSeq { // case we allocate a temporary 32-bit buffer and then copy-assign back // to the initial inputs. template - void generate_impl(RandomAccessIterator begin, RandomAccessIterator end, - DefaultTag) { - return generate_and_copy(std::distance(begin, end), begin); - } - - // Fills the initial seed buffer the underlying SSeq::generate() call, - // mixing in the salt material. - void generate_contiguous(absl::Span buffer) { - seq_->generate(buffer.begin(), buffer.end()); - const uint32_t salt = absl::random_internal::GetSaltMaterial().value_or(0); - MixIntoSeedMaterial(absl::MakeConstSpan(&salt, 1), buffer); - } - - // Allocates a seed buffer of `n` elements, generates the seed, then - // copies the result into the `out` iterator. - template - void generate_and_copy(size_t n, Iterator out) { - // Allocate a temporary buffer, generate, and then copy. + void generate_impl(DefaultTag, RandomAccessIterator begin, + RandomAccessIterator, size_t n) { + // Allocates a seed buffer of `n` elements, generates the seed, then + // copies the result into the `out` iterator. absl::InlinedVector data(n, 0); - generate_contiguous(absl::MakeSpan(data.data(), data.size())); - std::copy(data.begin(), data.end(), out); + generate_impl(ContiguousAndUint32Tag{}, data.begin(), data.end(), n); + std::copy(data.begin(), data.end(), begin); } // Because [rand.req.seedseq] is not required to be copy-constructible, -- cgit v1.2.3