Unsafe Rust is... tough?

help
1

Unsafe Rust is... tough?

While I was practicing rust, I stumbled upon a task to implement circular
buffer. It turned out to be really easy with VecDeque, since it somewhat
already a circular buffer. So, for educational purposes, I decided to implement
it in an unsafe way by manually managing memory. I stick to stable channel. I've
never used any unsafe features of the language before, but already familiar with
this concept from C++ so I thought it couldn't be harder in user-friendly
language, comparing to brutal corner-case hell of C++. Oh God how wrong I was
naively thinking that.

First of all I need to say I haven't read the Rustonomicon (probably I should)
before proceeding to solving this task since I have minimal understanding of
unsafe basics from other source, like reddit posts/questions, blogs dedicated
to rust, reading rust code, etc. But when I started looking for information on
how to implement such structure turned out from rust perspective I lack
knowledge so I tried to collect this information piece by piece from some online
sources.

Initial attempt was to go along with the chapter from Rustonomicon,
implementing Vec. Layout section suggests:

  1. You must make sure your data structure maintains covariance (by using
    PhantomData<T> when appropriate).
  2. Should drop any manually managed values.
  3. Implement Send/Sync by hand if we are holing a pointer (* mut|const _)
    since it inhibited by fields of such type.
  4. Optionally, maintain null-pointer-optimization for enums with 2 variants
    (e.g. size_of::<MyVec>() == size_of::<Option<MyVec>>()).

Also, about last clause book says that you can't do it in stable rust! How come
rust advertise itself as capable to be low level as C++, but such easy thing is
unavailable? After some digging I've found NonNull type from standard library,
which is a pointer wrapper which purpose is solely to enable this concrete
optimization, should I assume that Rustonomicon is out of date with current rust
state?

By reading further chapter suggest you to never allocate above isize::MAX
items since GEP instruction from LLVM IR (primary backend of rustc) accepts
signed integer as offset. As a consequence method
offset from pointer type accepts an isize, few methods from Vec
documentations also constrain you to capacity <= isize::MAX. This is a really
deep detail of implementation exposed and carved into standard library API, I
think it was a compromise of some kind to do so. On the other hand, allocator
interface completely lacks knowledge of this detail and allows you to allocate
usize bytes. It looks like you can cast pointers to unsigned integer (usize)
directly and work your way out with integer arithmetic taking in consideration
data available in Layout with a price of some valuable
optimizations. size_of<T> is already padded to alignment and ready to be used
as offset between array elements, according to reference.

Turning back to Vec implementation chapter, it suggests to use Unique<T> which
is internal detail of standard library and available only (by the time of
writing this) in nightly by enabling a feature gate. This is disappointing since
my goal was to write implementation for stable rust. So I abandoned this chapter
and proceed to searching further.

Closest to C/C++ thing was std::alloc::alloc, so
straightforward way appeared to me was to just use it. Group of free functions
from std::alloc module allows you to work with global allocator,
chosen by the user of your library with #[global_allocator] attribute, same
allocator used by Box, Vec, etc. Same suggestions from Rustonomicon chapter
applied here (covariance, manual drop, Send/Sync,
null-pointer-optimization). Covariance and NPO you can get from NonNull, just
need to make sure you pass non-zero allocation size (use
NonNull::dangling() as a placeholder for well-behaved
non-zero unknown value). Continuous elements layout can be build with
Layout::array(usize).

I noticed that Vec documentation suggests that you can use
vector as a base for your custom data structure, but information on this topic
is obscure and scattered through documentation. Doing so would be nice and can
lift some burden discussed above. My attempt was to maintain a Vec inside my
data structure. You can construct a Vec<T>
with custom capacity and if size_of<T> != 0 produced
vector has exact capacity. My guess is that I can just obtain a pointer to the
internal memory by as_mut_ptr and manage it by hands. But
some parts of documentation hints that you must use
from_raw_parts, so as consequence you need to
deconstruct the vector into ptr-len-capacity triplet? Also, vector has no
guarantees about maintaining it's uninitialized memory. The only promise it
has is that you can initialize memory beyond len() and then adjust length
accordingly and it will be sound to do so. But can you just use available memory
without modifying the vector by obtaining access through as_mut_ptr method?
Unfortunately, signature suggest it may modify internal state and allocated
memory. So looks like salvaging the vector is the most sane thing to do. But we
achieve not much with such approach. GEP problem still persist since we tied to
use offset with isize value. Neither there is any info if value returned
from as_mut_ptr is never null. You can be sure value held by a vector is never
null, but does this method perform any transformation from internal
representation?

The last step is to manually drop initialized values. It turned out to be
non-trivial too. First of all, if you stare carefully on Vec documentation it
says no particular order of dropping guaranteed. Other collections just
completely silent about it.

Another problem are panics during dropping. From my experience, it is
unreasonable and bad to panic during destruction of a value. However,
drop does NOT prohibit such behavior. The only caveat is if a
value has panicked mid-drop, it is considered dropped, so you must not drop more
than once.

So if you drop something generic, it may panic, and you should be aware of it.
I've peeked into VecDeque source "how do they do it":

    struct Dropper<'a, T>(&'a mut [T]);
    
    impl<'a, T> Drop for Dropper<'a, T> {
        fn drop(&mut self) {
            unsafe {
                ptr::drop_in_place(self.0);
            }
        }
    }
    
    let (front, back) = self.as_mut_slices();
    unsafe {
        let _back_dropper = Dropper(back);
        // use drop for [T]
        ptr::drop_in_place(front);
    }

Dropping performed by using drop_in_place. Since VecDeque
consist of two allocation units, it performs it twice. But here is the tricky
part: Dropper's purpose is to make sure other part was dropped if there was a
panic during dropping first part. But what happens if multiple elements panic
during drop? Even with a single allocated array what are consequences? Sadly,
drop_in_place docs says nothing about panics (except 1 mention in example).
So I've written a sample code to test it myself. Turns out after
first panic it attempts during unwinding drop the rest of elements. But if
another drop panics as well then this causes panic during panic situation we
discussed before and program terminates.

Another issue I haven't found any information if it sound to cast allocated
memory to slice and drop it in place. Also, I think, you can't use code above as
a language user since it exhibits undefined behavior: it is unsound to have a
reference to invalid value. Passing back to Dropper doesn't consume it. I'm
not even sure about passing front to drop_in_place. Reference here coerces
into fat pointer, but continues to live after the call until the end of function
block. Am I right or wrong? UPDATE: as @alice and @Yandros figured out, you can have invalid values, but can't "produce" them, as described in the reference.

Anyway, here is my attempt to apply gathered knowledge for solving
exercism task called "Circular Buffer" using unsafe means:
https://gist.github.com/DaTa-/9e701ff720dcb2839bcf41314b911e34 It won't surprise
me if it's implemented with undefined behavior since it's really hard to write
sound unsafe code with rust (it's not so easy even in C++).

If you found anything incorrect from my understanding displayed here - please,
correct me. Any links to good "unsafe" articles would be nice too. Thank you for
your time, sorry for bad English since I'm not a native speaker.

6 Likes
2

You ask many questions, but I can only address a few.

Yeah, no :sweat_smile: Data structures in Rust, if you're trying to make them generic and robust, are usually harder than what you would typically do in C++. That's partly because in C++ you usually expose an API that lets the user do whatever and if they cause undefined behavior it's their own fault, whereas in Rust you make it actually impossible to cause UB. That's the point of unsafe: to gather all the tricky unsafe bits in one place and conceal them behind an interface that doesn't allow misusing them.

That said, you can write basically the same thing in Rust as you would write in C++. Use raw pointers everywhere, and no slices, only pointer arithmetic. You'll need to write some extra code around zero-sized types, and the resulting API will be unsafe, but the memory model is essentially the same so there's not a huge difference. The problem is you haven't sequestered the unsafety, so it bleeds out into the user's code and forces them to deal with it instead of you.

This is why it's usually better to build your data structures on top of existing abstractions like Vec, because there's already been a lot of effort put into proving those abstractions are sound.

That's not a correct comparison. C++ does no struct layout optimization (for compatibility with C). std::variant (the closest thing C++ has to enum) can't encode the tag into a niche in a variant, because C++ types don't have niches, not that it matters, because variants can't be zero-sized, so the optimization Rust does wouldn't ever apply to std::variant anyway. The "null pointer optimization" that we're talking about with NonNull is not an "easy thing" in C++ -- it's doesn't even fit into C++'s concept of what a type is.

Yes, that section of the Nomicon mentions Rust 1.9.0, which is nearly four and a half years old. It's safe to assume a number of things have changed with regard to unstable and experimental features on nightly. For instance...

Unique was more-or-less replaced in the public API by NonNull a while back. They are slightly different because Unique<T> implements auto traits Send and Sync as if it were T, whereas NonNull<T> does not. (However, both are covariant in T.)

11 Likes
4

As I understand it, the reference just has to be valid during any use of the reference. It's just that creating a reference is considered a use of that reference, which is why we sometimes talk about insta-UB when creating references you never otherwise use.

2 Likes
5

Yes. And this is something completely underestimated by many people that come from a C/C++ background and thus think that by using unsafe, they get to transpose their C idioms into Rust and be fine doing so.

  • (The main culprit being the "&mut _ == mutable reference" approximation that many official books suggest, and which leads to many instances of UB in unsafe code).

That's a very legitimate thing to do, since that's what present Rust is about. Whenever a feature is available on nightly Rust it means it may be stabilized and become available in the future, which means that we should be optimistic about what we will eventually be able to do. But as of today, there are still a bunch of things that aren't doable in stable Rust (e.g., get the offset to the field of some struct without an instance of such struct).

Knowing some footguns is never bad, and it can definitely help. There are even some of those that don't even exist in Rust, not even unsafe Rust :muscle:. But there is a new class of pitfalls in Rust, akin to aliasing issues in C++, which are thus very subtle.

It's rather the opposite: you should make sure your data structure does not accidentally maintain covariance when it shouldn't :sweat_smile:. An invariant type is never unsound, it may just be unnecessarily unergonomic.

I'll repeat again here the basic rules regarding variance, that are missing from the official book:

  1. Invariance is never unsound. So, when in doubt, go for that. That can be achieved with a PhantomData<fn(Box<T>) -> Box<T>> (or PhantomData<fn(&T) -> &T> if no ::alloc available), or with the more simple (PhantomData<&'static mut T>, PhantomData<*mut T>, but the former requires that T : 'static and the latter removes Send / Sync (which is also a fine conservative choice).

  2. Covariance is sound:

    • when borrowing stuff in an immutable manner,

    • or when owning stuff.

    • it is unsound for borrows that allow mutation, such as &'borrow mut T, &'borrow Cell<T>, &'borrow Mutex<T>, RefMut<'borrow, T>, etc.

Also, once a type is not-covariant w.r.t. some parameter (say T), any type containing that one will be infected with that non-covariance.

  • That's why NonNull<T> is covariant, otherwise it would have been overly restrictive many times.
    But that also means one has to be very careful when using NonNull, since the moment it is used for a borrow that allows mutation, such as when hand-rolling some IterMut-like abstraction, if one does not explicitly opt-out of that covariance, they will be offering an unsound abstraction :warning:

But more importantly, you should be careful not to drop those when it is not appropriate! Since arbitrary Rust code may panic and unwind, if safety measures are applied "too late", these may not be reached when unwinding causing a drop that was not desirable.

  • Example

    Imagine wanting to hand-roll a .for_each() function for Vec<T>:

    //! This example is unsound.

impl<T> /* SomeHelperTraitForCoherence for */ Vec<T> {
    /// Same as `.into_iter().for_each`, but hand-rolled.
    fn for_each (mut self: Vec<T>, mut f: impl FnMut(T))
    {
        // self.into_iter().for_each(f); /* too easy, let's do something more "educational" */
        unsafe {
            for i in 0 .. self.len() {
                let at_cur: *const T = &self[i];
                let cur_owned: T = at_cur.read();
                f(cur_owned);
            }
            self.set_len(0); // avoid dropping the values that `f` has already taken ownership of.
        }
       // drop(self); /* Free the underlying allocation */
   }
}

    Then, of course, the set_len() call here is incorrectly located after the weird shenanigans rather than before, leading to unsound code: if f() panics, then (each) cur_owned will be dropped twice!

    That being said, people coming from C++ should already know of this pitfall, so nihil novi sub sole here.

    By the way, there is a very nice blog post about it here: Pre-Pooping Your Pants With Rust

Again, true, but only when relevant. For instance, RwLock{Read,Write}Guard<T> & co. don't get to be Send since on some OSes the underlying implementations may rely on thread-local or be thread-tied for some other reason.

Again, just an optimization, but a welcome one. This one is currently one of the easiest to achieve, thanks to ptr::NonNull. One thing that can be done sometimes is to internally rely on this optimization, even when not offering it externally.
That is, if you have some ptr: *const T field that may be initially unset and thus NULL, it is safer to use the Option<ptr::NonNull<T>> type since it ensures you don't forget to check against that NULL case (represented as None).

  • Note that, if you have been following from what I wrote before, this "improvement" is sadly a bit dangerous in the *mut T case, since we may be introducing covariance where we shouldn't...

Indeed! Something quite dangerous here, an unfortunate side-effect of relying on LLVM as a backend. But at least one can always start with an assert!(count <= isize::MAX as usize);, so the "fix" is simple (but easy to miss, I'll grant you that).

:ok_hand:

Using Vec<T> to allocate instances of type T is indeed a nice pattern, which can even lead to using only non-unsafe code.

  • But note that using Vec<T> to allocate instances of other types (most in-famous example being Vec<u8> + indices as a hand-rolled allocator of any kind of T).

    That's actually quite dangerous, since there are alignments concerns to be aware of.

Note that if you preallocate a high enough quantity, or if you use Vec<AliasableBox<T>>,

  • (AliasableBox is another required workaround for one of these subtle Rust things I was hinting about before: You shouldn't be handing out *const T or *mut T pointers derived from a Box<T> if that Box, in and on itself, may be moving. Even if it's just the pointer itself that is moving, that pointer has lack-of-aliasing guarantees that invalidate other pointers. Which makes things like owning_ref - Rust unsound when used with Box)

then you can get truly implement quite powerful things, since the initially so-allocated items won't be moving. A helper crate to manage the underlying API is ::uninit::extension_traits::VecCapacity

Indeed!

So, there are two kinds of "bad" in Rust: logic-wise bad, and memory-safety-wise bad. The latter is unsound, but the former technically isn't. So one shouldn't let the former escalate to the latter.

A Drop impl that panics falls into the former category, for a very simple reason: you cannot forbid non-unsafe behavior within a trait implementation unless the trait itself is marked unsafe.

  • So, in the same fashion that you can implement absurd Eq and/or Hash behavior for a custom type, and observe how badly it behaves when used in a HashMap / HashSet, you will notice that neither collection is allowed to UB in that case.

But neither leaking memory, nor panic!-king or aborting is memory-unsafe, so for these cases it is an acceptable thing to do. If it is, by the way, the only way to achieve soundness, then so be it.

  • It is, however, advisable to to tell users of your library that such bad things can happen, should they provide a bad implementor of the contracts.

For the record, panic!-king within a destructor triggered while unwinding / already panicking does cause an abort.

There are two kind of "invalid" values to be aware of:

  • truly invalid values:

    • uninitialized memory (memory returned by alloc, or by calls to MaybeUninit::assume_init (or the deprecated mem::uninitialized));

    • invalid bit-patterns (such as 0b00_00_00_10 for bool, or NULL for a Rust reference or Box).

  • "exhausted" values (I have invented that word, nothing official). That would be a value whose logical contents have already been dropped. But that doesn't make it uninit, so it is valid to have such values exist, provided they are not used.

The current phrasing for this distinction is that invalid values are unsound to ever produce (since they cause instant UB); whereas other values, such as "exhausted" ones or valeus that violate library invariants (such as the byte contents of a str being valid UTF-8) are unsound to use.

So, regarding VecDeque, we are fine: the only thing "pointing" to Ts is RawVec<T>, which can be seen as a Box<[MaybeUninit<T>]>, that is, a pointer that owns the backing allocation, but which does not presume anything about the validity of the contents (or in other words, MaybeUninit<...> can never be invalid). So the validity of T in this case is a safety invariant, which is not violated from within their drop impl.

:thinking: so may questions, so many things to talk about that :sweat_smile: I have the impression I have forgotten to talk about many things, so feel free to shoot more targeted questions :wink:

20 Likes
Rayon like library
6

Now complexity starts to make sense for me. Indeed, typical C++ API is unsafe to the brim. Thank you for pointing this out.

It may be unfair comparison, but I expect such things intrinsic to rust to just be available. Fortunately, it is available.

That's a shame. Everyone recommends this book, but no one mentions it's a bit obsolete. Thank you for enlightening me on that.

Oh. It actually even said so in the reference, but I completely missed that. Thank you!

To be honest, I'm completely lost when it comes to variance, this is a hard topic to, although I've read subtyping section in nomicon. I'll return to your suggestion how to opt-out of variance later to inspect them more carefully, for now my understanding is too blurry to actually absorb every detail. However, I get it why you should opt-out of variance with IterMut<T> alike. It would cause same problems as with &mut T.

Another hidden footgun in my arsenal, thank you for the link! It was surprising to me that such problem exists and lack of scoped threads in std now starts to make sense.

Unfortunately, I do not understand this part :slightly_frowning_face: Somewhere I can read about it?

Yep, that's already figured out above. Thank your for providing good categorizing of this problem, now it fits better.

Thank you all for answering for my questions! Now I understand it all a bit better.

The parts are missing for me are

  1. Whether or not you can use allocated vector memory without adjusting it's len.
  2. Can you really cast continuous elements to slice and drop it with drop_in_place?
1 Like
7

You can definitely use the allocated capacity of a vector regardless of its len -- that will be easier in future with an API like Vec in std::vec - Rust

2 Likes
8

Interacting with the box asserts exclusive access, which is trouble if there are also raw pointers to it.

You can, it's just that calling methods on the vector may mess with it, so if you start pushing or popping, don't expect it to stay as is.

Yes.

1 Like
9

And in stable, there is ::uninit::extension_traits::VecCapacity (in this case, .split_at_extra_cap())

2 Likes
10

Thanks, that's good to know! I'd rather use that than raw memory management.

I think, I'm just too stupid to understand. Thanks for the attempt through.

Cool. That's convenient and seems like the only optimal way.

Seems like my questions has exhausted, thank you all for your time and help!
I can mark as the solution only 1 answer so I marked one with the most information in it, although other post contains solutions too.

11

Yes, it's tough, and best avoided when possible. Expecting unsafe code in Rust to be easy to write is a bit like expecting a compiler to generate efficient code when all the debugging flags are turned on.

12

Not at all! It's actually a very subtle topic, which I just briefly mentioned since I didn't have the time to dwelve into a detailed explanation of the problem :smile: Now, luckily, @alice has, in the meantime, already explained this very issue in some other post, so I'll just link to it here:

2 Likes
13

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.