Range-based mem_ops #3715

reneme · 2023-09-27T09:29:54Z

This adds C++20 range-based overloads to the relevant functions in mem_ops.h. This header is public, so I kept the legacy ptr-based overloads (also because they are still used throughout the code base). But perhaps those should be deprecated and removed at one point, @randombit?

For convenience, this adds a few helpers to concepts.h. Details can be found in their doxygen comments.

coveralls · 2023-09-27T10:11:26Z

coverage: 92.075% (-0.007%) from 92.082%
when pulling dd160f3 on Rohde-Schwarz:span/memops
into dc4ac41 on randombit:master.

randombit · 2023-09-27T11:42:17Z

Let's hold on this for a little bit: NDK 26 and XCode 15 are both out now, I have been meaning to do a CI upgrade

reneme · 2023-09-28T10:09:44Z

src/lib/utils/mem_ops.cpp

+uint8_t ct_compare_u8(std::span<const uint8_t> x, std::span<const uint8_t> y) {
+   const auto min_size = CT::Mask<size_t>::is_lte(x.size(), y.size()).select(x.size(), y.size());

-   for(size_t i = 0; i != len; ++i) {
+   volatile uint8_t difference = 0;
+   for(size_t i = 0; i != min_size; ++i) {
      difference = difference | (x[i] ^ y[i]);
   }



@randombit please triple-check for constant time correctness. :)

reneme · 2023-09-28T10:11:02Z

src/lib/utils/mem_ops.h

+   requires std::is_same_v<std::ranges::range_value_t<OutR>, std::ranges::range_value_t<InR>> &&
+            std::is_trivially_copyable_v<std::ranges::range_value_t<InR>>
+{
+   ranges::assert_equal_byte_lengths(out, in);


If both in and out have static extents (e.g. static-extent std::span<> and/or std::array<>), assert_equal_byte_lengths will only verify the extents statically. There won't be another check during runtime.

src/lib/utils/mem_ops.h

devnexen · 2023-09-28T12:17:26Z

So I gave a shot with the NDK 26 locally and got this

In file included from build/include/botan/buf_comp.h:11:
build/include/botan/concepts.h:148:94: error: use of undeclared identifier 'uint8_t'
   contiguous_container<T> && resizable_container<T> && std::same_as<typename T::value_type, uint8_t>;
                                                                                             ^
In file included from src/lib/base/buf_comp.cpp:7:
build/include/botan/buf_comp.h:76:27: error: no type named 'resizable_byte_buffer' in namespace 'Botan::concepts'
      template <concepts::resizable_byte_buffer T = secure_vector<uint8_t>>
                ~~~~~~~~~~^
build/include/botan/buf_comp.h:76:75: error: expected '(' for function-style cast or type construction
      template <concepts::resizable_byte_buffer T = secure_vector<uint8_t>>

once fixed locally, everything else passes.

reneme · 2023-09-29T07:26:20Z

once fixed locally, everything else passes.

I'm guessing this was just lacking an include to <cstdint> somewhere, right?

randombit · 2023-10-11T11:53:40Z

One thing we should consider here is if we want to have these additions in the public mem_ops.h at all.

This header is kind of a grab bag of various things, some of which are required to be public for API or ABI reasons (especially allocate_memory which is used by the secure_vector) but much of this is not really intended to be for use by applications.

It might be better to add a new internal header which contains the span versions, convert the library internals to use this, and then deprecate most of the functions in mem_ops.h which were never intended for end users.

reneme · 2023-10-11T12:13:21Z

One thing we should consider here is if we want to have these additions in the public mem_ops.h at all.

I think it makes a lot of sense to split this header for a cleaner structure. The challenge with making it private, though, is that it'll prevent us from using these helpers in templates of other (public) headers.

randombit · 2023-10-11T13:06:13Z

This is true. I'll take the first step here - split the parts that are required to implement secmem.h into a new header allocator.h, and modify secmem.h to no longer include mem_ops.h [*] This will force all headers or source files which use functionality from this header to include the header explicitly. At that point it will be easier to evaluate how to split everything else out.

[*] And to maintain compatability mem_ops.h just additionally includes allocator.h

See #3715 for context

lieser · 2023-10-12T12:55:06Z

The challenge with making it private, though, is that it'll prevent us from using these helpers in templates of other (public) headers.

A solution could be to keep what is needed in the public header, but in a e.g. a detailed namespace. That should make it clear to users that it is not part of the public API.

reneme · 2023-10-18T14:20:28Z

Rebased to master after #3760 conflicted with the changes in here.

See #3715 for context

randombit · 2023-10-31T10:06:02Z

@reneme This needs a rebase with #3752 merged but I'll review after

reneme · 2023-11-01T09:01:16Z

src/lib/utils/mem_ops.h

+/**
+ * Copy a rande of a trivially copyable type into another range of trivially
+ * copyable type of matching byte length.
+ */
+template <ranges::contiguous_output_range ToR, ranges::contiguous_range FromR>
+inline constexpr void typecast_copy(ToR&& out, FromR&& in)
+   requires std::is_trivially_copyable_v<std::ranges::range_value_t<FromR>> &&
+            std::is_trivially_copyable_v<std::ranges::range_value_t<ToR>>


This is very closely related to C++20's std::bit_cast, right? I didn't find a way to use std::bit_cast on arbitrary ranges, though. Probably that's by design, as it is supposed to work closely with the type system.

But given that Botan's typecast_copy and STL's bit_cast are so closely related: Perhaps we should adopt the naming here and deprecate typecast_copy in the public API. For instance, we could call these functions bitcast_copy or bitcast_range.

reneme · 2023-11-01T09:23:27Z

src/lib/utils/mem_ops.h

+BOTAN_DEPRECATED("This function is deprecated, use constant_time_compare()")
 BOTAN_PUBLIC_API(2, 9) uint8_t ct_compare_u8(const uint8_t x[], const uint8_t y[], size_t len);


We don't use it anywhere in the code base anymore. Okay to deprecate?

Yeah fine to deprecate

FAlbertDev

All in all, LGTM. Some improvements of this PR and #3707 will be very helpful for implementing Classic McEliece :)

FAlbertDev · 2023-11-16T07:53:06Z

src/lib/utils/concepts.h

+/**
+ * Check whether a given range type has a length known at compile time.
+ */
+template <spanable_range R>
+bool consteval has_static_extent() {
+   return decltype(std::span{std::declval<R>()})::extent != std::dynamic_extent;
+}


When I try this in godbolt I cannot call this on non-span types like std::array or std::vector. When implementing this logic as a concept it works for me using the following example code:

template <typename S> concept static_extent_span = S::extent != std::dynamic_extent; template <typename R> concept static_extent_range = requires(R r) { {std::span(r)} -> static_extent_span; }; template <spanable_range R> consteval bool has_static_extent_alt() { return static_extent_range<R>; }

I really like your approach, apart from being fairly verbose. In the hope that we won't need this in many more places: I had another pass at this, and ended up simply spelling it out, like:

const std::span s{r}; if constexpr(decltype(s)::extent != std::dynamic_extent) { /*...*/ } // ...

No idea why has_static_extent<R>() seemed to work for me, before.

FAlbertDev · 2023-11-16T08:10:07Z

src/lib/utils/concepts.h

+template <size_t expected, spanable_range R>
+inline constexpr void assert_exact_byte_length(R&& r) {
+   const std::span s{r};
+   if constexpr(has_static_extent<R>()) {
+      static_assert(s.size_bytes() == expected, "memory region does not have expected byte lengths");
+   } else {
+      BOTAN_ARG_CHECK(s.size_bytes() == expected, "memory region does not have expected byte lengths");
+   }
+}


It's interesting, because a call of this method works, but only with type deduction. For example:

std::array<uint8_t,32> a; // Does not work assert_exact_byte_length<32, std::array<uint8_t,32>>(a); // Works assert_exact_byte_length<32>(a);

It seems the input type is implicitly converted to a span.

That's somewhat expected, because of the forwarding reference (R&&). When passing a with type deduction, you'll end up with R = std::array<>& (an lvalue reference). I.e. If you were to add the & to your explicit declaration, it should work. Here's some reading: https://medium.com/factset/modern-c-in-depth-perfect-forwarding-570f242261f8

src/lib/utils/concepts.h

FAlbertDev · 2023-11-16T08:28:07Z

src/lib/utils/mem_ops.h

+ * @param y another range of bytes
+ * @return true iff x and y have equal lengths and x[i] == y[i] forall i in [0...n)
+ */
+BOTAN_PUBLIC_API(3, 3) bool constant_time_compare(std::span<const uint8_t> x, std::span<const uint8_t> y);


Do you think we want to move this to ct_utils.h?

Probably. This PR has more than enough complexity, though. Let's keep the interface stable, at least. I suggest we do that as a follow up.

ct_utils is our internal header while constant_time_compare is intended for library users since this comes up for application also.

~~All internal uses should use CT::Mask instead - I have a WIP branch on this somewhere.~~

Actually this was done already in #3760

FAlbertDev · 2023-11-16T08:44:56Z

src/lib/utils/mem_ops.h

+// TODO: deprecate and replace, use .subspan()
 inline void xor_buf(std::span<uint8_t> out, std::span<const uint8_t> in, size_t n) {


I agree this function interface is somehow weird...

FAlbertDev

👍

reneme · 2023-11-20T07:24:40Z

@randombit Could we go ahead with this? I'd love to have this and #3707 merged before doing another pass over the Kyber/Dilithium implementations.

randombit

Yeah fine to merge, sorry I've been sick since early Nov so way behind on reviews right now.

randombit · 2023-11-20T13:33:40Z

src/lib/utils/mem_ops.h

+BOTAN_DEPRECATED("This function is deprecated, use constant_time_compare()")
 BOTAN_PUBLIC_API(2, 9) uint8_t ct_compare_u8(const uint8_t x[], const uint8_t y[], size_t len);


Yeah fine to deprecate

randombit · 2023-11-20T13:34:20Z

src/lib/utils/mem_ops.h

+ * @param y another range of bytes
+ * @return true iff x and y have equal lengths and x[i] == y[i] forall i in [0...n)
+ */
+BOTAN_PUBLIC_API(3, 3) bool constant_time_compare(std::span<const uint8_t> x, std::span<const uint8_t> y);


ct_utils is our internal header while constant_time_compare is intended for library users since this comes up for application also.

~~All internal uses should use CT::Mask instead - I have a WIP branch on this somewhere.~~

Actually this was done already in #3760

reneme · 2023-11-21T08:09:41Z

sorry I've been sick since early Nov so way behind on reviews right now

No worries at all. Hope you're feeling better now. 😄
Thanks for the review

reneme added this to the Botan 3.3.0 milestone Sep 27, 2023

reneme force-pushed the span/memops branch from 01cfa85 to 0def3ba Compare September 28, 2023 10:05

reneme commented Sep 28, 2023

View reviewed changes

reneme force-pushed the span/memops branch from 0def3ba to 9ca3c15 Compare September 28, 2023 11:07

reneme commented Sep 28, 2023

View reviewed changes

src/lib/utils/mem_ops.h Show resolved Hide resolved

reneme requested a review from devnexen September 28, 2023 11:17

reneme force-pushed the span/memops branch 3 times, most recently from 7bfafa2 to 7c8601c Compare September 29, 2023 07:16

reneme force-pushed the span/memops branch 2 times, most recently from 126262c to aa7b79b Compare September 29, 2023 07:30

reneme marked this pull request as ready for review September 29, 2023 07:30

reneme mentioned this pull request Sep 29, 2023

[std::span] {load,store}_{le,be} #3707

Merged

reneme requested a review from randombit September 29, 2023 07:59

reneme mentioned this pull request Sep 29, 2023

Extend/Update (public) APIs with std::span overloads #3318

Open

47 tasks

reneme force-pushed the span/memops branch from aa7b79b to 6ccd49e Compare September 29, 2023 11:19

This was referenced Oct 5, 2023

HSS-LMS Signature Algorithm Implementation #3716

Merged

FIX: out-of-bounds access of std::array #3736

Merged

randombit added a commit that referenced this pull request Oct 11, 2023

Split out allocator helpers to allocator.h

5a5b8a2

See #3715 for context

randombit mentioned this pull request Oct 11, 2023

Split out allocator helpers to allocator.h #3752

Merged

randombit added a commit that referenced this pull request Oct 11, 2023

Split out allocator helpers to allocator.h

361aa76

See #3715 for context

randombit added a commit that referenced this pull request Oct 11, 2023

Split out allocator helpers to allocator.h

a8dcef8

See #3715 for context

reneme force-pushed the span/memops branch from 6ccd49e to 96ddaf0 Compare October 18, 2023 14:19

randombit added a commit that referenced this pull request Oct 18, 2023

Split out allocator helpers to allocator.h

d515127

See #3715 for context

randombit added a commit that referenced this pull request Oct 18, 2023

Split out allocator helpers to allocator.h

20630bc

See #3715 for context

randombit added a commit that referenced this pull request Oct 18, 2023

Split out allocator helpers to allocator.h

048f6a1

See #3715 for context

randombit added a commit that referenced this pull request Oct 19, 2023

Split out allocator helpers to allocator.h

a6091cf

See #3715 for context

randombit added a commit that referenced this pull request Oct 26, 2023

Split out allocator helpers to allocator.h

6c2245c

See #3715 for context

randombit added a commit that referenced this pull request Oct 29, 2023

Split out allocator helpers to allocator.h

49dbbcb

See #3715 for context

reneme force-pushed the span/memops branch from 96ddaf0 to 0a88269 Compare October 31, 2023 18:45

This comment was marked as outdated.

Sign in to view

reneme commented Nov 1, 2023

View reviewed changes

reneme force-pushed the span/memops branch from 0a88269 to 41f40b7 Compare November 1, 2023 09:15

reneme commented Nov 1, 2023

View reviewed changes

FAlbertDev reviewed Nov 16, 2023

View reviewed changes

reneme added 4 commits November 16, 2023 16:22

add a few helpers for ranges to concepts.h

3ab7159

range-based basic memory operations

6c0e12b

range-based typecast_copy<>() overloads

6486bfa

range-based xor_buf()

dd160f3

reneme force-pushed the span/memops branch from 41f40b7 to dd160f3 Compare November 16, 2023 15:22

FAlbertDev approved these changes Nov 17, 2023

View reviewed changes

randombit approved these changes Nov 20, 2023

View reviewed changes

reneme merged commit 3005ae6 into randombit:master Nov 21, 2023

reneme deleted the span/memops branch November 21, 2023 08:08

		BOTAN_DEPRECATED("This function is deprecated, use constant_time_compare()")
		BOTAN_PUBLIC_API(2, 9) uint8_t ct_compare_u8(const uint8_t x[], const uint8_t y[], size_t len);

		// TODO: deprecate and replace, use .subspan()
		inline void xor_buf(std::span<uint8_t> out, std::span<const uint8_t> in, size_t n) {

Range-based mem_ops #3715

Range-based mem_ops #3715

Uh oh!

Conversation

reneme commented Sep 27, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

coveralls commented Sep 27, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

randombit commented Sep 27, 2023

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

devnexen commented Sep 28, 2023 • edited by reneme Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

reneme commented Sep 29, 2023

Uh oh!

randombit commented Oct 11, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

reneme commented Oct 11, 2023

Uh oh!

randombit commented Oct 11, 2023

Uh oh!

lieser commented Oct 12, 2023

Uh oh!

reneme commented Oct 18, 2023

Uh oh!

randombit commented Oct 31, 2023

Uh oh!

This comment was marked as outdated.

reneme Nov 1, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

FAlbertDev left a comment

Choose a reason for hiding this comment

Uh oh!

FAlbertDev Nov 16, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

reneme Nov 16, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

randombit Nov 20, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

FAlbertDev left a comment

Choose a reason for hiding this comment

Uh oh!

reneme commented Nov 20, 2023

Uh oh!

randombit left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

reneme commented Sep 27, 2023 •

edited

Loading

coveralls commented Sep 27, 2023 •

edited

Loading

devnexen commented Sep 28, 2023 •

edited by reneme

Loading

randombit commented Oct 11, 2023 •

edited

Loading

reneme Nov 1, 2023 •

edited

Loading

FAlbertDev Nov 16, 2023 •

edited

Loading

reneme Nov 16, 2023 •

edited

Loading

randombit Nov 20, 2023 •

edited

Loading

randombit Nov 20, 2023 •

edited

Loading