Rust vector guarantees
doc.rust-lang.org
doc.rust-lang.org
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.
I would assume that in Rust it would fall apart just the same, except perhaps at compile-time rather than at run-time?
No, because Rust gives you the tools to compartmentalize this stuff pretty well. Yes, if you write an unsound program it will fail to compile, but the language also guides you in the direction of not writing one, so huge complicated codebases written in 100% safe rust are possible and do compile. With C++ as complexity grows it's harder to keep stuff safe, in my experience. YMMV.
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…
I don't think it does. It might.
> Does C++ do this?
IIRC C++ is allowed to perform the optimization. I don't recall if any current implementations do. They might.
Edit: I'm wrong, it's not, however std::string is allowed to.
> How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust?
Because Rust has an entire system of ownership and borrowing which exists at compile time to ensure these things don't happen.
If you don't have a mutable borrow active, you can immutably borrow it as many times as you like and iterate over it to your heart's content in as many scopes as you like, but you can't mutate it.
These borrows are lexically scoped.
This is a start to explaining ownership: https://doc.rust-lang.org/book/second-edition/ch04-01-what-i...
Basically, in Rust, this happens:
let x = vec![1,2,3,4];
let iterator = vec.iter();
vec.push(5); // will not compile, until iterator goes out of scopeThat means you can think of it as push(&mut vec, 5) - you need to pass a mutable reference to the vec as the first a argument and the iterator is already holding one of them. So you're not allowed to.
The iterator is an immutable reference. push() is a mutating method. These don't work together.
Rust is "aliasing XOR mutability"
They are close to being equivalent, but maybe with weird-sized objects, the (pointer, pointer, pointer) version requires some divisions, and the other one only requires multiplications?
The reason is that std::swap(v1, v2) must never invalidate existing iterators and/or references to elements into either vector, which the optimization would clearly break.
std::string is the type you may be thinking of, where the standard does make a special exception to enable the SSO.
Yeah, I knew string can do SSO, so I assumed std::vector was allowed to as well.
> How are you guaranteeing this? C++ doesn't, so what is going on behind the scenes to make this work in Rust?
Rust's lifetimes.
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.
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);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.
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.
If memory safety isn't broken, no matter what the attacker does the memory is only going to be accessible through the container that allocated it. Parent's point still stands.
You're missing the facts that (a) your unsafe code won't be safe, and (b) your program will generally invoke external code that can be also buggy and hence not memory-safe.
Based on the code I've seen, I think you're simply protecting your experiences and fears from C++. You are of course free to use an allocator that zeroes on dealloc in your own code.
In such a case, I believe a clearing allocator (or a set of custom allocators) sounds like the way to go. There may be a performance penalty, but you will be certain that all instances are covered, not just Vec<_>. Alternatively, a typed allocator (I wanted to link to a paper on the topic, but I can't find it) can, for a very small price, perform reasonably good mitigation on such exploits.
That comment had two parts, it first said that if your code is memory safe (even explicitly calling out unsafe code!) then it's not a problem, and then saying you can do it at a lower level if you have to. You can do it at a lower level either by changing the allocator, or by having a hardened vec that does a volatile write in its destructor.
Look again at the text right before your quote "then the contents of deallocated memory shouldn't be internally observable."; it explicitly addresses this exact concern.
However, it's worth noting that at this level of "everything is unsafe" the problem is intractable. Just as you trust Rust's stdlib to have safely-crafted syscalls, you trust Rust's compiler to generate the right code if you tell it to do a volatile clear on a drop/resize.
You have to define your trust level somewhere. For some, it is "I have audited my small amount of unsafe code (if any), and I trust Rust's stdlib". The parent's comment was addressing that level of trust. If you're not trusting the stdlib, you also probably don't trust the compiler to generate the right code; at which point the most you can do is try to keep things safe, you can never succeed short of auditing the generated asm extensively.
...what? Did you read the discussion? The entire discussion was about the need to zero memory for security, despite the safety of the programming language. This entire time I've been claiming the ability to zero memory is necessary because you cannot guarantee control flow integrity when you have syscalls, external libraries, etc. Nowhere did I ever throw my hands up and make a blanket claim that secure programs cannot exist. That wasn't even the subject of the discussion.
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.
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.
> 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?
Sure, sounds fine to me. What's wrong with this? The pointer would need to change on every copy anyway, since it'd need to point to a new buffer even if it were pointing to the heap.
Also, when a Rust object is moved, there's no move constructor; it's purely a memory copy, so there would be no way to update the pointer for the new location.
Sure, but that still doesn't mean you'd get an extra branch?
> Also, when a Rust object is moved, there's no move constructor; it's purely a memory copy, so there would be no way to update the pointer for the new location.
Ah, this would seem like a complete deal-breaker. But if this is the case then why didn't they mention this instead of the other reasons? It seems far more compelling and fundamental than the other two?
[EDIT: Ignore this last part. I think I confused the issue here with something else when adding this final sentence.] A̶l̶s̶o̶,̶ ̶t̶h̶i̶s̶ ̶̶s̶t̶i̶l̶l̶̶ ̶d̶o̶e̶s̶n̶'̶t̶ ̶m̶e̶a̶n̶ ̶t̶h̶e̶r̶e̶ ̶w̶o̶u̶l̶d̶ ̶b̶e̶ ̶a̶ ̶b̶r̶a̶n̶c̶h̶ ̶o̶n̶ ̶e̶v̶e̶r̶y̶ ̶a̶c̶c̶e̶s̶s̶,̶ ̶r̶i̶g̶h̶t̶?̶
Yes it does, without a move constructor the only way to do a small vector optimization is to detect when the vector has been packed in the indexing operation and do the pointer math internal to the stack part of the vector.
With move constructors you keep the pointer up to date, without them you have to recalculate this information on any kind of access, and for this you need to know when stuff must be recalculated which leads to the extra branch.
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)
C++ has a bit of a different safety model that somewhat relies on move constructors to work. Rust builds this in, with some crucial changes.
For one, all C++ values are forced to have a zero state; e.g. when you move out of a unique_ptr (in certain ways, not all of them) the old one must be zeroed, because the destructor will still be run on it. Use after move leads to unspecified but not necessarily undefined. Rust OTOH does not have null as a valid value for its pointers. In case of conditional moves Rust will use an extra bit on the stack called a "drop flag" to track whether or not the destructor needs to be run, but only when needed, and usually it isn't so this complexity is abstracted away and also doesn't impact the runtime for the majority of times it isn't necessary.
99% of the move constructors in C++ are focused on making this work correctly. It's not necessary in Rust.
There are the 1% that do stuff like the small string optimization. Yes, you can't do this as neatly in Rust. But it's worth noting that move constructors have a significant cost, both in runtime (things like vectors need to deal with this correctly -- in particular vector<smart_object<_>> can't memcpy on resize anymore), and in compile time -- if you want to build good generic abstractions you have to guard against the fact that moves (and copies) can do anything. This would completely destroy Rust's ability to easily compartmentalize safety because now you have to worry about arbitrary code running every other line of your generic code. In C++ you don't care about this as much; since compartmentalizing safety is more of a best-effort thing and blame is harder to assign, whereas in Rust your generic datastructure must be safe when you throw any (safely implemented) type at it.
So yeah, sounds painful, but not really, and from a Rust POV what C++ has in this space is really painful.
Hm, so let's say had this binary tree in C++:
template<class T>
class Node {
Node(Node const &) = delete; // don't worry about copying for now
Node &operator =(Node const &) = delete;
unique_ptr<Node> a, b;
Node *parent;
T value;
public:
Node(Node &&other) : a(move(other.a)), b(move(other.b)), parent(move(other.parent)), value(move(other.value)) {
if (parent) {
if (parent->a == &other) { parent->a = this; }
if (parent->b == &other) { parent->b = this; }
}
other.parent = NULL;
}
}
you can't implement it _this_ way, but you can still implement a binary search tree (Btreemap is a b-tree, which is a generalization of a binary tree).
Normally in Rust for a tree like structure with parent pointers you'd either use unsafe code or use Rc/Weak, depending on what you need.
As far as binary search trees are concerned IIRC you can implement them without parent pointers, you'd move your relocation method to something called on the parent node.
Note that this isn't just limited to trees. Even doubly-linked lists would have this issue, as would other more-complex data structures.
I guess my larger point is, it seems like the repercussions aren't just limited to missing low-level optimizations like small-string optimization like you claim, but they extend to your entire global object model as well as to what operations & time complexities you can support without the compiler yelling at you. That seems quite painful to me. Who wants to constantly argue with the compiler as to whether or not he should be allowed to have parent/sibling/other pointers?
People who value "I'm sure this can't explode", over "I'm pretty sure it won't explode, but at least it's a fast template that can stack-allocate" ;-)
But seriously - you can still do a lot of that if you really need to for some reason. Either use an external library in C++ or write some unsafe code which won't restrict your pointers.
How would unsafe code help here? The problem we were talking about was the lack of move constructors, and I just gave an example of their usefulness with parent pointers. How would unsafe code help? Unsafe code doesn't suddenly give you move constructors does it?
(As for writing external C++ code and linking to it... I mean yeah, but if the entire object model you have to interact with has to be in C++, then you might as well write the whole code in C++ at that point...)
Unsafe code lets you store parent pointers as raw pointers and update them manually when you move things. You don't actually _want_ a move constructor here; your btree values are on the heap anyway; what you want is a .move() method that chains correctly, and you can write this in Rust. In C++ the move constructor is a convenient way of doing this but not the only way.
Move constructors are how you organize the code in C++. Rust will not support the same code organization. This does not mean it's not doable in Rust, just that you have to design it differently. Rust is not C++; this is ok.
You learn to structure your code in a certain way. Design patterns from C++ will not necessarily carry over.
It certainly is painful to program in Rust if you design your code as if it were C++. In practice, the stuff you talk of doesn't end up being a problem; Rust still lets you do all that just that it's different.
> You learn to structure your code in a certain way. Design patterns from C++ will not necessarily carry over.
Er... data structures with parent pointers and sibling pointers are "design patterns from C++" to you?
Most such datastructures either get implemented with Rc/Weak (which has a performance cost but often not a problem), or with "unsafe", which lets you write Rust as if it were more like C++ (you still have types, but you now also have certain dangerous abilities that you use carefully). Rust provides you the tools to properly abstract this unsafe such that it stays within the implementation and doesn't leak. This is true for Vec and BTreeMap, for example.
You're talking about arguing with the compiler but unsafe Rust is not much worse than regular C++ in this aspect (there are some differences), so you always have the ability to drop down to this place where the compiler won't fight you to do stuff like this. Generally you can abstract away low level datastructures as unsafe code that's safe to use from the outside (this is usually something you can manageably audit) and everything else stays safe. Most such datastructures exist as libraries or in the stdlib already.
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...
> ... 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?
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)