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.
> 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?
> 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.
Well, I must be misunderstanding how iterators work in Rust, then. AFAIK in C++ an iterator is a thin wrapper around a pointer in memory, and resizing the container can cause the underlying "base" array to move around to somewhere else if it's reallocated–thus, the invalidation of the old iterator. What is a Rust iterator doing in this case?
To expand (hopefully correctly, I'm still learning Rust): You can have a single "mutable borrow" in a single lexical scope where you can mutate the vector _and its contents_ to your liking, but you can't pass a vector mid-mutation to another scope to read the vector while that borrow is active. It is safe to mutate the vector and its contents, as the vector owns the items inside it and there is only one active user of the collection.
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.
So, sorry for being not bright. But if I may ask, if I have a Vec<B> A, then, it has I have a mutable reference to it in the form of A. Now, I take a const iterator to an object in A, say it, then, though the iterator is const for object of type B, it is a mutable reference for the Vec<B> A, and hence, I now cannot reallocate A till all the iterators have died(most probably because of scope). Is that true?
I don't really understand the scenario you're putting out. Why would the iterator be a mutable reference? (there are mutable iterators but you explicitly said const).
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 scope
Yes. So I'm asking the logic behind this in context of ownership model. How can you derive the above behavior from the principle that only one mutable reference is allowed? If const iterator is not a mutable reference to a Vec, then A itself is the only mutable reference, and push back should be allowed.
That 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.
You are allowed at most one mutable reference or multiple immutable references. Additionally, taking an immutable reference locks the object from mutation (and taking a mutable one locks it for reading from anywhere other than that reference).
The iterator is an immutable reference. push() is a mutating method. These don't work together.
In Rust you can have as many const references to a thing as you like, but you can only have a mutable reference to a thing if there are no other references (mutable or not) to the same thing. Hence it's not possible to have an iterator over a vector while trying to mutate it.
In the article, it sounded like there is actually a guarantee that the (pointer, integer, integer) representation is used in rust.
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?
C++ is not allowed to do the small buffer optimization for std::vector<T>. You'll find a number of small_vector<T> classes from third parties, though.
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.
If you have 10 minutes or so, this is an excellent talk that explains how Rust's Vec<T> works by comparing it to Java and C++: https://youtu.be/ksirw1v5gXk?t=748 (The rest of the talk is great too, but it's 50mins in total!)
I haven't been exposed to how ownership/borrowing worked, so this video was great! Thanks for sharing it, since it made many of the other comments in this thread more clear.
>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.
> 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);
> 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?
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?
> pointer would be pointing at internal structure memory, it would need to change on every copy then.
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.
I don't understand. I asked why there is a mandatory branch, you said otherwise the pointer would need to change on every copy, I said that's fine, and now you rebutted that copying isn't even worth it? So what is the problem and where is the extra branch? I don't understand where the discussion is going.
In the "small vector optimization", the storage on the stack would be in place of the `(pointer, capacity, length)` except for a tag byte, so keeping the pointer would waste nearly 1/3 of the potential space.
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.
> so keeping the pointer would waste nearly 1/3 of the potential space.
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̶?̶
> Also, this still doesn't mean there would be a branch on every access, right?
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.
> 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.
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're saying I... can't have my binary tree in Rust?
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.
Oh, the parent pointer (or even the BST nature) wasn't really the point. The parent pointer was just an example that was easy to understand. For BSTs specifically, in C++, IIRC they use threading (= sibling pointers) to allow iterators O(1)-time access to the siblings in constant space, and those would have the same problems. And I didn't even mean to limit this to the BST case (I edited my comment while you were probably typing yours so you probably saw the version where I mentioned BSTs). In other non-BST binary trees you may well need a parent pointer for good time/space complexity, not merely find it convenient.
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?
> 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.
> 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...)
> How would unsafe code help? Unsafe code doesn't suddenly give you move constructors does it?
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.
> Who wants to constantly argue with the compiler as to whether or not he should be allowed to have parent/sibling/other pointers?
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.
Using move constructors to keep them updated is a design pattern.
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.
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?
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.
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.
> 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.
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.
Half the point of Rust is to drive the amount of unsafe code as close to zero as possible so we don't have to worry about crap like that.
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.
To be fair, Rust code can link to (entirely unsafe) C/C++ code or even JIT-compiled code, in which case you also want some runtime guarantees to mitigate exploits in case they happen.
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.
You cannot assume memory safety; the entire point of this security concern is that you cannot assume memory safety. There will in general be unsafe Rust code and non-Rust code that you cannot verify in external libraries, etc.
In which case you can always implement a hardened vec that clears itself, like the parent commenter said.
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.
What I am trying to say is that that "if the program is memory-safe" condition is never satisfied in reality. You will be calling unsafe code no matter what you do -- not only will any non-trivial program itself have unsafe code as already called out, but because even a trivial "hello, world" would need to invoke a syscall which will not be written in Rust (until the time comes when we get a Rust kernel...) and hence not proven memory-safe. Does this make sense? Yes, if your program was secure then you wouldn't need to worry about security, but that's not the world we live in.
Sure. At which point, again, there is still a solution, just that Vec itself won't help here.
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.
> You have to define your trust level somewhere. If you're not trusting the stdlib, you also probably don't trust the compiler to generate the right code.
Aw, come on. Why are you resorting to these inane arguments? Yes, people trust their compilers to be bug-free. No, that does not -- in any way, shape or form -- logically imply that they should also trust every single version of every kernel and ALSO every single kernel-module from every possible vendor and ALSO every single user-level library that their program might run on top of, whether from the past or the future, to be bug-free. To just throw your hands up and claim the threat levels are somehow comparable to each other is just disingenuous.
> To just throw your hands up and claim the threat levels are somehow comparable to each other is just disingenuous
I'm not, I'm saying they are for some. Different folks have different trust models.
I'm saying that it's a logical threat/trust model where you both trust the compiler and the kernel. This isn't everyone's model. This is clearly not yours. But this wasn't clear in the original comment and cwzwarich addressed this model (as well as yours!) and that's what I was saying.
Defense in depth is good, but, again, that wasn't what was being _asked for_. You forcibly took a discussion in a different direction from what was originally being discussed, reframing everything to a strictly absolutist view of trust, and are somehow bewildered that folks aren't understanding what you're saying.
I don't really see the point in this discussion -- it's a metadiscussion about whether or not including an "assuming safety" portion in a comment was appropriate, and doesn't add anything.
> You forcibly took a discussion in a different direction from what was originally being discussed, reframing everything to a strictly absolutist view of trust, and are somehow bewildered that folks aren't understanding what you're saying.
Huh? My trust model was the same as that of those who want memory to be zero'd, like the one earlier [1]. People ask for that because so many attacks we see today are in external libraries and kernel-mode, and hence people are worried about that. That is not something in my fantasy; that's the model of the world we live in. You guys decided to deliberately ignore that and pretend a safe language implies worrying about attacks in external code is ridiculous. I was trying to steer back the discussion to that model. Apparently I failed; you guys win. Rust programs are invincible by definition.
> Apparently I failed; you guys win. Rust programs are invincible by definition.
This is not what I'm saying, and you're being deliberately obtuse at this point.
> My trust model was the same as that of those who want memory to be zero'd, like the one earlier [1].
This person was asking about network exploits where this has been a problem. Rust helps prevent those exploits. Does it fix the problem completely? Of course not. Does it fix the problem to the point where it's "not worth worrying about"? Depends, depends on where you stop worrying about things, and this is why the original commented addressed both cases.
Revisit the first comment and consider if others perhaps interpreted it more broadly than you.
I am done discussing this. You're putting words into my mouth, and being deliberately obtuse.
Security is a spectrum. It appears your argument has become, "no secure programs can exist because of syscalls". Seems circular and overly reductionist.
> Security is a spectrum. It appears your argument has become, "no secure programs can exist because of syscalls". Seems circular and overly reductionist.
...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.
> 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.
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.
> ... 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?
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)
81 comments
[ 3.4 ms ] story [ 138 ms ] threadRust 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:
That 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.
> 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++:
You're saying I... can't have my binary tree in Rust?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...
https://github.com/cesarb/clear_on_drop
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.
Aw, come on. Why are you resorting to these inane arguments? Yes, people trust their compilers to be bug-free. No, that does not -- in any way, shape or form -- logically imply that they should also trust every single version of every kernel and ALSO every single kernel-module from every possible vendor and ALSO every single user-level library that their program might run on top of, whether from the past or the future, to be bug-free. To just throw your hands up and claim the threat levels are somehow comparable to each other is just disingenuous.
I'm not, I'm saying they are for some. Different folks have different trust models.
I'm saying that it's a logical threat/trust model where you both trust the compiler and the kernel. This isn't everyone's model. This is clearly not yours. But this wasn't clear in the original comment and cwzwarich addressed this model (as well as yours!) and that's what I was saying.
Defense in depth is good, but, again, that wasn't what was being _asked for_. You forcibly took a discussion in a different direction from what was originally being discussed, reframing everything to a strictly absolutist view of trust, and are somehow bewildered that folks aren't understanding what you're saying.
I don't really see the point in this discussion -- it's a metadiscussion about whether or not including an "assuming safety" portion in a comment was appropriate, and doesn't add anything.
Huh? My trust model was the same as that of those who want memory to be zero'd, like the one earlier [1]. People ask for that because so many attacks we see today are in external libraries and kernel-mode, and hence people are worried about that. That is not something in my fantasy; that's the model of the world we live in. You guys decided to deliberately ignore that and pretend a safe language implies worrying about attacks in external code is ridiculous. I was trying to steer back the discussion to that model. Apparently I failed; you guys win. Rust programs are invincible by definition.
[1] https://news.ycombinator.com/item?id=15967604
This is not what I'm saying, and you're being deliberately obtuse at this point.
> My trust model was the same as that of those who want memory to be zero'd, like the one earlier [1].
This person was asking about network exploits where this has been a problem. Rust helps prevent those exploits. Does it fix the problem completely? Of course not. Does it fix the problem to the point where it's "not worth worrying about"? Depends, depends on where you stop worrying about things, and this is why the original commented addressed both cases.
Revisit the first comment and consider if others perhaps interpreted it more broadly than you.
I am done discussing this. You're putting words into my mouth, and being deliberately obtuse.
...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.
> ... 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)