Check for zero C struct memory

No I don't want to compare all fields to zero individually , I want to check that a memory , from address A to adress B is filled with zero, padding included!
Like C memcmp can do.

Generally relying on the values stored in the padding is a bad idea, but I suppose you could just call memcmp from libc?

2 Likes

Well thank you,

I though core::ptr that can write and read byte can also compare it... This seems legit.
A commun way to compare a continuous array of POD fast is to compare whole memory with memcmp instead of just iterating over and over.

I wonder if std::vec does this optimisation...

Thank you

When would vec do this optimization? I'm not aware of any operations on vec that check that all data including padding are zero.

Well It can just compare whole buffer of 2 std::vec with memcmp is it's type T can be compare like POD type ( byte comparison ).
In C++, when the T of vector do not implement comparison operator (Trivially comparable), you can just call memcmp on the whole buffer directly. ( This is what Unreal Engine do for exemple ).
If T is not trivially comparable you loop through all T and call the comparison operator.
Is Rust able to do the same? Or does every type need to implement Eq trait to be comparable?
What do Rust do if i try to compare a struct without implementing Eq?
If Rust type implement Copy they can be bitwire copyable, so they can also be bitwise comparable.

(I'm know C++, I begin with Rust :slight_smile: )

If the types do not implement PartialEq you cannot compare them. playground

When you type #[derive(PartialEq)] you ask for a default equality implementation, which just calls the equality operator on every field.

Regarding vec, I took a look at the source and it seems they use a feature called specialization to compare certain types with memcmp. It is only used for the types you see here.

This feature is currently unstable, so it cannot be used outside the standard library (i.e. for your own types) until they decide on a stable syntax. (unless you use the nightly compiler)

2 Likes

Well a big thank you!
This is exactly what I was looking for, they just limit bitwise comparison with listed types, but it's not possible to have this optimisation with a struct that contains only bitwise comparable attributes.

Thank you!

Remember that in Rust, padding does not matter for equality. So types with padding would not be correctly compared by memcmp. Rust also doesn't allow you to write an if that checks if a type uses derive to implement PartialEq or if they did so manually. And even if they used derive, they might have some field with a custom implementation of PartialEq.

2 Likes

Ok, but a Copy types is a type that can be bitwise copyable... So it can also be bitwise comparable if no PartialEq trait is implement for that type.
Is Rust able to check if a trait is not implemented at compile time?
This is my last question :smiley:
Thank you

Just because a type is copy does not mean memcmp is correct. One example is floating points for which NaN != NaN. Similarly the type

#[derive(Copy, PartialEq, Eq)]
struct A { 
    field1: u32,
    field2: u8,
}

is copy but has padding, so it can also not be compared correctly with memcmp.

If a type does not implement PartialEq, that means it doesn't make sense to compare it at all.

2 Likes

And let me just emphasize this again: If a type does not implement PartialEq, that means it doesn't make sense to compare it at all.

If you take the float as just 32 bits and compare it as a just bit is perfectly legit.
Yes (NaN != NaN) is false, but also this : (NaN float as int) == (NaN float as int) is true if both bit sign is same.
I don't talk about comparing float, i talk about comparing bucket of memory bit by bit!

Edit: In C++ there is proposal for this type of things : http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0732r0.pdf
P0732R0 and "trivially comparable" – Arthur O'Dwyer – Stuff mostly about C++

Is it really? According to standard, AFAIK NaN is defined only by exponent, so you have plenty of different bit patterns even for fixed sign.

So what I understand here is that in Rust you can compare 2 buckets of memory bit by bit?
So in an application where we don't care about NaN or not (Like performance application (game engine )), we can compare (in Rust) vec by doing memcmp? ( Lot of game engine did it in C++, Unreal Engine do for exemple ). Even if NaN is set, it's consider ok for performance reason! ( I don't remember exactly but I think NaN is treat at some strategic point in the code )
So Rust don't allow this?
Do we have to do like in C++ and don't use std?

In Unreal Engine for exemple here is the code, user is allow to say "Trust me you can bitwise compare":

template <typename T>
struct TIsArithmetic
{ 
	enum { Value = false };
};

template <> struct TIsArithmetic<float>       { enum { Value = true }; };
//....
template<typename T>
struct TTypeTraitsBase
{
	// There's no good way of detecting this so we'll just assume it to be true for certain known types and expect
	// users to customize it for their custom types.
	enum { IsBytewiseComparable = TOr<TIsEnum<T>, TIsArithmetic<T>, TIsPointer<T>>::Value };
};

//.....
template <typename ElementType>
FORCEINLINE typename TEnableIf<TTypeTraits<ElementType>::IsBytewiseComparable, bool>::Type CompareItems(const ElementType* A, const ElementType* B, int32 Count)
{
	return !FMemory::Memcmp(A, B, sizeof(ElementType) * Count);
}

//.....
/**
* Equality operator.
* @param OtherArray Array to compare.
* @returns True if this array is the same as OtherArray. False otherwise.
*/	 
bool operator==(const TArray& OtherArray) const
{
	int32 Count = Num();
	return Count == OtherArray.Num() && CompareItems(GetData(), OtherArray.GetData(), Count);
}

If you really need to compare floats using memcmp, there's nothing stopping you from just calling memcmp.

1 Like

Ok ok !
Thank you for everything :slight_smile:

Reading struct's padding bytes is defined behavior only if the struct is zero-initialized. This means it's perfectly legal for compilers to "optimize" the code comparing with zeroed struct to unconditionally return true. If the struct is zero-initialized, it has defined behavior and it should return true. If not it's UB so compiler can generate arbitrary code, and unconditionally returning true is the fastest code for non-UB path.

Bit-comparing floating point numbers is another case. They have neither padding bytes nor invalid representation(like bool with 2u8 value), it's legal to compare them by bits. Rust provides safe functions to convert them from/to unsigned integers with matching size. See f{32,64}::{from,to}_bits()

4 Likes

So, there are two questions at hand here:

How do we memcmp two "bags" of bytes ([u8]) to test for equality?

Easy, just use the == operator on these bytes: <[u8] as Eq>::eq() does use memcmp.

Can I see a struct as just a "bag of bytes"? If so, how?

Now, this is where things are subtle. The general answer is: "No, you cannot!"

Indeed, you can't go and feed a struct you know nothing about to the following function:

unsafe // Can be UB!
fn as_bag_of_bytes<T: ?Sized> (
    ptr: &'_ T,
) -> &'_ [u8]
{
    ::core::slice::from_raw_parts(
        // ptr
        ptr as *const T as *const u8,

        // len
        ::core::mem::size_of_val(ptr),
    )
}

The root cause of that being UB is that T may have padding bytes, as @Hyeonu said (I didn't know about the zero-initialized "exception" to the rule; anyways, since you won't be calling that function on a statically known zero-initialized struct, that exception in practice doesn't even count). So, if your struct has padding, you cannot call as_bag_of_bytes() on it.

That being said, it would be nice to have the above function for padding-less types, such as primitives or structs that have been carefully crafted to ensure they do not contain any padding.

And this is indeed possible:

  1. Define a new unsafe trait AsBytes (or NoPadding), that we will implement for types that have no padding. This way the above generic function can have a T : AsBytes bound and no longer be marked unsafe!

    /// Unsafe marker trait for types that are valid to cast as a slice of bytes.
    ///
    /// This is true of primitive types, and recursively for `#[repr(C)]`
    /// compositions of such types, **as long as there is no padding** (such as
    /// arrays).
    ///
    /// The derive macro takes care of deriving this trait with the necessary
    /// compile-time guards.
    unsafe trait AsBytes {
        fn as_bytes (self: &'_ Self)
            -> &'_ [u8]
        {
            unsafe {
                // # Safety
                //
                //   - contract of the trait
                ::core::slice::from_raw_parts(
                    self
                        as *const Self
                        as *const u8
                    ,
                    ::core::mem::size_of_val(self),
                )
            }
        }
    }
    
  2. unsafe impl AsBytes for:

    • primitive types:

      (
          unsafe
          impl $Trait:path, for primitive_types!() $(;)?
      ) => (
      impl_macro!(@impl_for_all
          unsafe
          impl $Trait, for [
              u8,     i8,
              u16,    i16,
              u32,    i32,
              usize,  isize,
              u64,    i64,
              u128,   i128,
              f32,
              f64,
              {T : ?Sized} *const T,
              {T : ?Sized} *mut T,
              (),
              {T : ?Sized} ::core::marker::PhantomData<T>,
              
              // the following are only safe to **view** as bytes,
              // do not create them from bytes!
              bool,
              ::core::num::NonZeroU8,     ::core::num::NonZeroI8,
              ::core::num::NonZeroU16,    ::core::num::NonZeroI16,
              ::core::num::NonZeroU32,    ::core::num::NonZeroI32,
              ::core::num::NonZeroUsize,  ::core::num::NonZeroIsize,
              ::core::num::NonZeroU64,    ::core::num::NonZeroI64,
              ::core::num::NonZeroU128,   ::core::num::NonZeroI128,
              {'a, T : 'a + ?Sized} &'a T,
              {'a, T : 'a + ?Sized} &'a mut T,
              {T : ?Sized} ::core::ptr::NonNull<T>,
              str,
          ]
      );
      
    • composite types; tuples are #[repr(Rust)] structs, so I do not include them, since their layout is allowed to change; we end up with composite types being arrays and slices:

      (
          unsafe
          impl $Trait:path, for array_types!() $(;)?
      ) => (
          impl_macro!(@impl_for_all
              unsafe
              impl $Trait, for [
                  {T : $Trait} [T],
                  {T         } [T;    0],
                  {T : $Trait} [T;    1],
                  {T : $Trait} [T;    2],
                  {T : $Trait} [T;    3],
                  {T : $Trait} [T;    4],
                  {T : $Trait} [T;    5],
                  {T : $Trait} [T;    6],
                  {T : $Trait} [T;    7],
                  {T : $Trait} [T;    8],
                  {T : $Trait} [T;    9],
                  {T : $Trait} [T;   10],
                  {T : $Trait} [T;   11],
                  {T : $Trait} [T;   12],
                  {T : $Trait} [T;   13],
                  {T : $Trait} [T;   14],
                  {T : $Trait} [T;   15],
                  {T : $Trait} [T;   16],
                  {T : $Trait} [T;   17],
                  {T : $Trait} [T;   18],
                  {T : $Trait} [T;   19],
                  {T : $Trait} [T;   20],
                  {T : $Trait} [T;   21],
                  {T : $Trait} [T;   22],
                  {T : $Trait} [T;   23],
                  {T : $Trait} [T;   24],
                  {T : $Trait} [T;   25],
                  {T : $Trait} [T;   26],
                  {T : $Trait} [T;   27],
                  {T : $Trait} [T;   28],
                  {T : $Trait} [T;   29],
                  {T : $Trait} [T;   30],
                  {T : $Trait} [T;   31],
                  {T : $Trait} [T;   32],
                  {T : $Trait} [T;   64],
                  {T : $Trait} [T;  128],
                  {T : $Trait} [T;  256],
                  {T : $Trait} [T;  512],
                  {T : $Trait} [T; 1024],
                  {T : $Trait} [T; 2048],
                  {T : $Trait} [T; 4096],
              ]
          );
      );
      
    impl_macro! {
        unsafe
        impl AsBytes, for primitive_types!()
    }
    impl_macro! {
        unsafe
        impl AsBytes, for array_types!()
    }
    
  3. Generate a #[derive(AsBytes)] procedural macro (macro_rules! macro for the playground) that checks:

    • that the struct is #[repr(C)] or #[repr(transparent)], since it is mandatory when wanting to rely on the layout of a struct (in the case of a macro_rules! macro for the playground, I have skipped the #[repr(transparent)] case;

    • that each field of the struct is AsBytes on its own:

      $(
          const_assert!(
              $field_ty : $crate::AsBytes,
          );
      )*
      
    • that there is no padding, by checking that the total size of the struct is equal to the sum of the sizes of its constituents:

      const_assert!(
          ::core::mem::size_of::<$StructName>() ==
          (0 $(+ ::core::mem::size_of::<$field_ty>())*)
      );
      
    • so that it can soundly unsafe impl AsBytes for that struct:

      unsafe impl $crate::AsBytes for $StructName {}
      

And now you can just call .as_bytes() on valid types and you'll get a zero-cost &[u8], that you can then == compare to get an efficienct memcmp!

derive_AsBytes! {
    #[repr(C)]
    struct Ok {
        a: u16,
        b: u8,
        c: u8,
    }
}

#[cfg(FALSE)] // Uncomment this line to get compilation errors
mod fails {
    derive_AsBytes! {
        #[repr(C)]
        struct InnerPadding {
            a: u8,
            // inner padding byte
            b: u16,
        }
    }
    
    derive_AsBytes! {
        #[repr(C)]
        struct TrailingPadding {
            a: u16,
            b: u8,
            // trailing padding byte
        }
    }
}

fn main ()
{
    dbg!(Ok { a: 10752, b: 27, c: 0 }.as_bytes());
}
  • yields

    [src/main.rs:260] Ok{a: 10752, b: 27, c: 0,}.as_bytes() = [
        0,
        42,
        27,
        0,
    ]
    
  • Playground


If that sounds like a tedious macro to write, and you think a crate should be exporting such functionality, then you are right! There already is such a crate, from which I've taken this idea:


There is another way to avoid padding, and that's by adding a #[repr(packed)] attribute on a struct. However, this adds a whole can of worms / bugs on itself, since now all the reads and writes on the fields of the struct need to be unaligned reads/writes using raw pointers, which is quite error-prone and thus unsafe. The only way this solution is easy to do is when all its fields have an alignment of 1, such as when using ::zerocopy::byteorder integer types. But in that case #[repr(packed)] is not doing anything, and we are back to a #[repr(C)] struct carefully crafted without padding bytes.

8 Likes

A big thank you! This is exactly what I need! With BytewiseEquality also!

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.