Rust vector guarantees

https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees

by chewbacha • 9 years ago

68 75 9 years ago

doc.rust-lang.org

saagarjha6• 9 years ago

Just curious: what are differences between the guarantees provided by Rust's vectors and std::vector from C++?

Manishearth17• 9 years ago

It's hard to know what really you're asking for, and how much you know about Rust.

Rust itself has a bunch of guarantees. Rust's vector is guaranteed to work well within that framework. So,

- No dangling pointers / UAF from stuff it gives you

- No iterator invalidation from iterators you get from it

- You can't push to it and invalidate references to its insides (this is really the iterator invalidation one over again)

- You can't use it in a way that will not be data race safe

These are all Rust guarantees; Vec just adheres to them. You can say that these guarantees are Vec guarantees too (which is why I'm saying "I'm not sure what you're asking for).

c++ std::vector does not have these guarantees because c++ does not have these guarantees. You can get some of these guarantees by restricting yourself to coding a certain way but they kinda fall apart when stuff gets complex in my experience.

Aside from that it's basically the same guarantees as std::vector, i.e. "will store stuff in contiguous space", "will allocate buffer with extra capacity as it grows" (this isn't actually a guarantee, but it's not going to change for either).

One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated.

Rust's vector also never implicitly performs deep copies, but this isn't really a guarantee.

Rust also has a concept of zero sized types, which C++ does not, and Rust's vector deals with them in a certain way, however since C++ doesn't have these types you can't really compare.

It's possible C++ guarantees a drop order for where Rust's vector does not. I'm not sure.

mehrdadn17• 9 years ago

You can get some of these guarantees by restricting yourself to coding a certain way but they kinda fall apart when stuff gets complex in my experience.

I would assume that in Rust it would fall apart just the same, except perhaps at compile-time rather than at run-time?

saagarjha6• 9 years ago

how much you know about Rust

Very little, so please bear with me ;)

For example, from the linked page:

Most fundamentally, Vec is and always will be a (pointer, capacity, length) triplet. No more, no less.

Does C++ also provide this guarantee?

Vec will never perform a "small optimization" where elements are actually stored on the stack for two reasons:

Does C++ do this?

and from your response:

No iterator invalidation from iterators you get from it

How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust?

As you can see, I don't know enough about C++ as I would like either…

smitherfield• 9 years ago

One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated.

I believe this is incorrect and small-vector optimization is in fact disallowed by the C++ standard. In any case, standard or not, no implementation is ever going to do SVO because it would require a branch on every access, making them incompatible with SIMD instructions.

Rust also has a concept of zero sized types, which C++ does not

No, C++ allows this optimization too, it just requires that the "sizeof" operator always returns an integer >= 1.

Matthias247• 9 years ago

One thing Rust's vector guarantees that C++ doesn't is that Rust's vector will not store elements inline; anything (with nonzero size) you push into it will be heap allocated.

Does C++ really not guarantee this? If yes then I probably have written quite a bit of "broken" code, which assumes that element addresses stay constant during moves of the container.

    std::vector<A> vec1; // And initialize it
    A* a = &vec1[0];
    auto vec2 = std::move(vec1);
    A* b = &vec2[0];
    assert(a == b);

mehrdadn17• 9 years ago

This seems wrong to me:

Vec will never perform a "small optimization" where elements are actually stored on the stack [because] it would penalize the general case, incurring an additional branch on every access.

I don't follow this. I can see appending to a vector requiring an extra branch, but why would every access (like, say , vec[i] = 0) need an extra branch?

barrkel3• 9 years ago

if (vec.size < THRESHOLD) { vec.local[index] = value; } else { vec->heap[index] = value; }

mehrdadn17• 9 years ago

Didn't they say Vec is a (pointer, capacity, length) triplet though? Wouldn't it just be vec.pointer[index] = value regardless of whether the pointer points to the stack or the heap?

Manishearth17• 9 years ago

This would be true in C++.

However, Rust has no move constructor; so the small vector optimization can't be implemented as "make the pointer point to itself and fix it up every time you move things", it must be implemented by having some check and then changing how you refer to elements.

Note that in C++ the move constructor has a similar cost whenever it gets moved around (and the cost can become problematic in cases like nested vectors where resizing is no longer a memcpy).

(moves are also implicit and more common in Rust so the impact would be more even if Rust did have move constructors. Which isn't really a workable hypothetical, since Rust's model is not designed in a way that that would be consistent anyway)

mehrdadn17• 9 years ago

Wow, this seems like a very painful restriction coming from the C++ side. Thanks for the explanation.

dbrgn2• 9 years ago

If you want opt-in small vector optimization you could also use this crate written by the Servo team:

https://github.com/servo/rust-smallvec

You can take a look at their implementation. If I'm reading this correctly, access by index goes through deref, which matches on the self.data type: https://github.com/servo/rust-smallvec/blob/5758c25663da2421...

OtterCoder• 9 years ago

The one part of the spec that gives me pause is the fact that dropped memory isn't cleared. That sort of behavior has been the cause of so many network exploits. Is it worth worrying about here?

JoshTriplett• 9 years ago

If you want memory cleared on drop, you could do that by setting the global allocator to one that clears memory on free, rather than changing individual data structures.

mehrdadn17• 9 years ago

I suspect he doesn't want to pay the performance penalty on all containers, just for a particular container.

cwzwarich2• 9 years ago

If your language (and program in Rust's case, since Rust has unsafe code) is memory safe, then the contents of deallocated memory shouldn't be internally observable. Technically speaking, you could add an API to Rust that returns an Option of a buffer by virtual address, and this would be completely safe.

If you're truly concerned about the implications of preserving the contents of existing memory, you need to do it at a lower level in the allocator anyways. In the case that a pushing elements on a Vec causes the Vec's buffer to be reallocated, the allocator is free to either extent the existing allocation of the buffer or make a new allocation. If the allocator chooses the latter, then clearing the memory upon drop doesn't clear the old copy.

mehrdadn17• 9 years ago

then the contents of deallocated memory shouldn't be internally observable.

Only as long as you can assume control flow integrity. As soon as the control-flow gets diverted then an attacker can read the memory. That's the root of the security concern to begin with.

dbrgn2• 9 years ago

If you're worried about secrets leaking, you can also use crates like https://crates.io/crates/secrets or https://crates.io/crates/secstr that clear memory on drop and also prevent active memory from being swapped, and other things.

TheDong• 9 years ago

That sort of behavior has been the cause of so many network exploits

No, the thing that caused those issues was not that memory wasn't zeroed, but that the language was memory unsafe and the dirty memory was accessible again later due to a buffer overrun or other pointer messup.

Rust tackled the problem of memory unsafety thoroughly, so there's no reason to worry about it.

You don't hear people complain about Java or python not zeroing out memory as much since those languages, like rust, are memory safe.

There are places where you do need memory to be zeroed (cryptographic operations where secrets should not live in memory longer than needed for fear or local attackers), but network attackers / because there might be buffer-overruns is not one.

viraptor3• 9 years ago

That's not exactly true. I've dealt multiple times with situations in python where I wanted a guarantee that the stored value is cleared. As in actually overwritten, because it was used for temporarily holding certificate keys.

This is doable, but usually via a native extensions. The problem being avoided here is not that python will fail. It's that openssl will get heartbleed and start leaking "freed" python contents from the same process. This very much applies to network attackers as well.

tom_mellior2• 9 years ago

I don't understand the following sentence:

... it is strongly recommended that you only free memory allocated by a Vec by creating a new Vec and dropping it.

Could someone parse this for me? To me, it reads like "to free memory allocated by a Vec v, create a new Vec w and drop it (i.e., w)".

This is obviously not what it is intended. What's the role of the second Vec? Is this only in a context where v is empty but its memory not yet freed? If so, why wouldn't shrink_to_fit work in that case?

Manishearth17• 9 years ago

This is in case you turn the Vec into a raw pointer (using as_ptr() and mem::forget) so that you can pass ownership over FFI or something. In this case it is not recommended that you free it by calling free(), it is recommended that you free it by using from_raw_parts to reconstruct a new vector and let it drop.

You need the second vec because the first vec is gone at this point. If it wasn't gone you could just let the destructor run.

In Rust Vec and Box also work as the malloc primitives; if you absolutely need to allocate contiguous memory of runtime-known size the best way to do it is to allocate a Vec and then extract the pointer from it. (There is a proper allocation API coming soon; and of course you can just call malloc/free, but this is the recommended way of doing it)

steveklabnik• 9 years ago

I've filed a bug to elaborate, thanks! https://github.com/rust-lang/rust/issues/46879

tom_mellior2• 9 years ago

Cool, thanks to both of you for the quick report and fix!

Rust vector guarantees

Related Stories