INSANE bug in my code from compiler optimization
HTML-код
- Опубликовано: 12 дек 2023
- For this quick video, I explain an oversight in my code, and how it caused undefined behavior. The bug provides an excellent case study for how compiler optimizations work, and why relying on unsoundness is bad in practice!
Music used in the video:
Corbyn Kites - Dusk Drive
Corbyn Kites - Birds Игры
#1 advice for debugging UB is Miri. For games, it probably won’t help that much, since it’s not exactly fast, but if you can extract the problem code into a standalone test, it can tell you precisely where the UB occurs.
Wouldn't the issue be fixed, if you used then instead of .then_some? .then takes a closure and only executes it, if the value is true.
I believe that would be valid, but the overhead of making that function and calling it might be bad in a performance-critical codebase, such as a game engine, when called in a loop. of course, the compiler will probably be able to optimize it away to make it be the same assembly as generated by the code at the end of the video
@@samuelgunterWouldn't that performance consideration be the same with the original then_some?
@@npip99 no. then_some takes a type T as it's input, .then takes a closure that returns type T. I don't know if rust constructs that closure each time or what it will do when compiled
There's no way the closure wouldn't be optimized away. It might even produce exactly the same code as the if version. That's the whole point of zero-cost abstractions. Ofc they don't always work perfectly but Rust can optimize much more advanced iterator combinations using multiple closures to optimal loops.
@@samuelgunter Rust closures are very heavily inlined if they can be known at compile time so it is almost sure it will be inlined
you could also use the `then` method on bools, instead of `then_some`, which takes a closure argument, meaning the variant would only be constructed if the test passes
also, why are you using so much unsafe? i believe it is meant to be a last resource, and not a commonly used thing
i expect you'll keep finding weird bugs like that, it's really easy to screw up in unsafe contexts
This "last resort" becomes often necessary when handling async code and needing speed above all else (going in with absolute confidence that your code is sound, of-course). I managed to make a(n admittedly basic) software-based particle simulation several times faster this way. He went in with absolute confidence that his code was sound (because really, it _does_ look like it!) in order to speed up this real-time application (game-engine where speed is paramount), his code was not sound, he encountered UB that made him bang his head against the wall (as I did, when using unsafe in said software-based particle simulation)
@@d-o-n-u-tI don’t know why people keep perpetuating this myth that you need to use unsafe everywhere to make Rust fast. Safe Rust code is just as fast as C++ in almost every instance I can think of. People just need to actually learn how Rust works rather than trying to use it like they would other languages.
A large amount of “unsafe” tells me that somebody was told to use Rust for something, but doesn’t actually like the language and doesn’t want to learn it properly.
@@Daktyl198 if you've looked at the standard library you'll see frequent usage of unsafe -- even doing basic things like initializing a vector or converting from one type into a String. The Rust Book itself acknowledges that 'safety is merely an abstraction'; *true* safety does not really exist -- the standard library is just a compilation of known-correct 'unsafe' functions.
I think the whole 'unsafe' keyword was just a gigantic misnomer where it should've been more like 'unchecked'. There isn't anything inherently *wrong* with it; it's simply better to have checked code.
@@d-o-n-u-tYes, there's nothing inherently wrong with the unsafe keyword if you know what you're doing. And if you know a certain function is "safe" for sure, using unsafe to make your code shorter and/or easier to read as is the case in the std library is fine.
The problem is that people who aren't so familiar with rust just use it to get the compiler to shut up about their very poorly written, extremely unsafe functions. They'd rather shut the compiler up than fix the issues.
Also, my original point was more about speed. You don't need to use unsafe to get Rust to perform at-speed or for "special optimizations". The compiler can do optimizations way better than any human working in unsafe brackets ever could.
scary! i’m sure similar situations can lead to your code working in debug but not release builds
I've had the opposite happen before....
@@bitten2uphappens with me multiple times when dealing with numbers, where the release behaviour of wrapping around was what I expected but I forgot it'll trap in debug.
This is quite common in C or C++, where undefined behaviour is quite easy to produce. There different compiler modes often produce different outcomes for undefined behaviour.
I tend to try and limit the scope of unsafe usage. I know it doesn't seem like much, but while you have `Octant::from_raw` I would also have `Octant::try_from_raw` which does what this method does. Also I wonder about the semantics of `get_child_reader_unchecked`, I wonder what invariant ensures that this is ok, is it that this iterator can only be constructed from a reader that has all child readers?
oh wow what a crazy bug!
thanks for sharing, learnt something new :)
it's crazy cool how the compiler can optimize so much
Thanks! Optimizations like these are yet another reason why Rust is the best programming language :)
I think you need to trust the optimizer way more than you do, 99% of the time safe code will be just as fast as the unsafe code.
Write your code in safe Rust first and only consider unsafe in parts of the code that will benefit from it.
actually you should only consider unsafe for optimizations if you do benchmarks and notice relevant improvements
this overuse of unsafe screams this guy isn't aware of rust practices (i mean no disrespect to him)
Yes, using a match statement in from_raw and making it return Option would totally work, even with -O1 it gets optimized to a conditional move. Only problem is when you extend the enum you'll need to update the code as well, but in this case that's probably never going to happen. Ideally the rust standard library should provide some kind of functionality for this like a derive(TryFrom)
@@spicybaguette7706 there's a crate that does that
@@jvcmarchm. maybe not ‘unaware’ - i think they just seem a bit overeager to optimize. that’s pretty common in low-level projects 🥹
@@spicybaguette7706 `num-traits` provides the `FromPrimitive` trait for precisely this, and it's 100% safe
I was able to follow this whole thing without looking at the screen. You have converted code directly to audio.
I am happy that my explanation was clear and satisfactory :)
I'd be interested if using bool::then instead of bool::then_some would fix this
Yep, that would be another solution!
Ah, so I'm not the first one to think that.
That's why unit tests are necessary, they would have cought this immediately
BTW great video, it's great to see real examples of where the optimizations are applied
It can tell you what to fix, not why it's broken to begin with.
Simple A/B testing of MIR output between the two versions of the compiler would've cleared so much up and would've taught him to never blindly trust that any updated version of the compiler is automatically better.
The language that's designed to be safe and easy requires extra shut from all over the place to be even close to the overall effectiveness of C/++
Rust idiots are so funny
@@wilfreddv well to be fair, technically this is not a fault of rust but of Douglas.
then_some takes a value which is computed independently of the condition, so what the compiler did here technically makes sense. The behavior is just unexpected because from_raw is unsafe (which in other languages is the default)
Also, rust is definitely not designed to be easy
@@igs8949The same can be said about every bug in C++ code. The problem is that Rust is limited and requires frequent use of unsafe. But then they have all these fancy methods like "then_else" that simply do not work in such environment. Mixing those concepts was a design mistake.
@@RenamedChannel The function "then_some" had nothing to do with why this was a bug. You could have the bug using standard if/else.
Very informative video! Thanks for sharing!
PSA: miri, the tool that evaluates MIR, can and does find that source of UB and should ALWAYS be used to run code that uses unsafe.
Thanks for the heads up. I typically avoid unsafe like the fucking plague, but now at least when I have no choice I've got an extra tool to use.
@@Bobbias You should have all your tests around unsafe be ran by MIRI, ideally. It does mean that they're much slower to run, but at least you can catch memory bugs (in a much less painful way than if you have to rely on valgrind)
Your problem here is more of an architectural problem. There's no way you can guarantee that a non-const value passed to `from_raw` will always produce a valid result. You should have returned a Result, or better yet, have a `try_from_raw` that does so (in case you still what to use `from_raw` with const values).
These kinds of unsafe uses are unnecessary, because they are track down and Rust's compiler can already prevent you from these types of bugs. What if you removed a variant from Octant? There's no type information to help you understand what code will break.
Isn’t that what the Option is for?
@@randomizednamme Depends on what you want to convey. There can be multiple reasons why parsing the raw value didn't work as intended. An Error is more explicit (one of multiple possible outcomes), whereas an Option is more implicit (only one of 2 outcomes, where the reason for the outcome is implicitly known)
I‘m pretty sure there is a clippy lint for that? If not, there probably should be.
Clippy has a lint for this, which will tell you to use `then` instead.
WOW, i had this exact issue happen to me when i was writing a kernel driver. I thought this was just one off thing and it was just me, but i got so surprised seeing someone deal with this exact thing. On my projects I usually dissasemble the code to compare it with C anyways, and its not very large scale, so i caught it early. The rust compiler is just too smart sometimes.
See imagine you had a bug of this complexity AND you had trouble reproducing it. That would be nightmare fuel
Back in the day I was working on an ARM v8 OS kernel in Rust for my thesis, and I switched to nightly to get some extra features related to constexpr and asm.
Thank god I spent a week getting JTAG to work on my hardware early on. Some of the optimizations were breaking process forking and interrupt handling in ways that were impossible to debug. Sometimes the bugs were dependent on how the code pieced together in the binary, and so adding a print statement would make the bug disappear, only to later appear after adding another line elsewhere.
Moral of the story: using nightly? Be ready to learn how to work with redare2.
This same bug occurs on stable. I just happen to use nightly for other reasons. But undefined behavior can sure be a pain :)
Is there a good reason to even use unsafe there? The int_enum crate provides a derive macro for IntEnum that implements try_from, for instance, but the naive match also works. Don't reach for unsafe code unless you actually have to
The difference between the erroneous code and the non-erroneous code was just when the Octet was constructed... I wouldn't've noticed that myself. Maybe a lazier version of `then_some` would've worked (with `|| unsafe { ... }` as the argument) but the if/else block does just that. Not the error I would've thought of, but neat to know exists.
There is a `then` method on bools that does just that
I’m not sure I get why you need the from raw_bits and the accompanying unsafe. Instead of something safe.
I’d have to look at more of the code. 0:15
It doesn’t seem like the general idea here would require unsafe.
Optimizers doing weird things while assuming code cannot exhibit undefined behaviour commonly affects C and C++ as well especially as programmers of those languages tend to do things that are potentially UB but do not realise it and compilers do not warn enough when doing it. I'm surprised the rust compiler didn't complain about this but I guess it assumes you know what you are doing with unsafe code.
My first encounter with such problems was actually in Swift. I was using a no-copy wrapper of an array as a "data" object so I could dump it to a file. It seemed safe because both variables were on the stack, so I thought the pointer would be valid until the end of the scope. Instead, the array got optimized away because using the pointer was not counted as using the array.
My solution would to make `from_raw` into a match statement that returns Some when the byte is valid, and None when the byte is invalid. That way there isn't any unsafe code.
I'd argue it's at least a bit of a footgun that the expression in then_some is evaluated irrespective of the boolean on which it's called.
I get *_why_* - outside of macros, Rust doesn't have the ability to lazy-evaluate expressions if they aren't explicitly inside a closure at the point where they appear in the code, but I think it'd be worth mentioning in the then_some docs that if you want lazy evaluation you should use then_with
The docs say "Arguments passed to then_some are eagerly evaluated; if you are passing the result of a function call, it is recommended to use then, which is lazily evaluated."
There are also clippy lints for similar operations, i.e. using unwrap_or with a function call instead of unwrap_or_else, but not for this specific case yet.
@@ksoeholm You're right, I was looking at the original implementation PR but it's been updated since.
I've been considering learning Rust;
Do you feel it generally do a good job of differentiating between safe & unsafe code at compile time?
Or is it more like classic C++ where the compiler doesn't prevent you from writing unsafe code?
When I say "writing unsafe code", I mean stuff like
- implicitly casting int to bool
- implicitly casting char to int
- allowing casting Foo to Bar when that can never succeed
- allowing variables to have no defined value (without marking them as unsafe in some way)
- etc
One of the main draws of Rust is you shouldn't be able to write memory unsafe code without using an unsafe block, period. In that sense, I'd say Rust does one of the best jobs of differentiating between safe & unsafe code out of all programming languages.
Rust does a *spectacular* job of differentiating safe and unsafe code at compile time through the use of the unsafe keyword. Unless a function is marked as unsafe, its behavior must be defined for all inputs - meaning that the function's contract is not defined implicitly (or in documentation) but defined in the code! I strongly recommend learning Rust, it's much more ergonomic than C++ in my view.
@@DouglasDwyer Oh that's super nice! I was hoping that's how they handled it. I'll have to start digging into it once I have time. Thanks!
@@MathewAldenFrom your second comment: Those things aren't even really doable in safe Rust. I'm not sure they're doable in unsafe either, because they're more so problems with language semantics of C/C++. As a general rule, Rust is pretty explicit about what's happening and how. The unsafe block is used when you're basically telling the compiler, "source: trust me" about memory management. 😂
but that self.octant is a u8 type it’s kinda weird imo even if I am constracting some enum type infering that the 'u8' would always be around the max enum value feels like "oversmarting"
It looks like some kind of counter, and you can't +=1 an enum.
@@vytah
impl std::ops::AddAssign says otherwise
@@vytah true i wonder if this a compiler issue or smth don’t know how then_some works
Some of it I think is just that Rusts types are different then Cs. Rusts types carry boundedness where C types use UB to Assert boundedness.
The best example I think is just a function call through pointer.
In C the pointer could be null but it's asserted through calling that it's valid. If the compiler knows its null that's UB and the compiler can handle it however it wants.
In Rust we don't really get into that situation since we know the "pointer" is garenteed not to be null by construction. We don't need to worry about an assertion at the function call sight. Though we have now added an assertion at construction for the lifetime of that pointer.
In Rust even if the pointer isn't used we still have the assertion which can be used to optimize. It's the same for the enum, not marked with "non exhaustive".
In this case the enum was always created even when false so the assertion was always present. It was trivial for the compiler to see two checks on the same value an optimize one away, EX "const_Assert(Oct < 8); if Oct < 8 {...}".
Hope that makes sense and is helpful
@@jolkert_ you cannot implement AddAssign on an enum in such a way that it overflows the enum. Counter goes from 0 to 8, so 9 values. The enum has 8 values.
Another solution would have been to use then instead of then_some, because the closure passed to it is only evaluated in the true case.
Oh my it clicked for me at 3:00. UB elimination is a nasty optimization when your code has unwanted UB and you're trying to pinpoint what causes a bug
cool
fascinating find, thanks for the video!
this highlights an interesting drawback to rust's approach of trying to have its cake (direct access performance) and eat it too (strict type safety).
there just _are_ situations where you know something about your data and want to shove it somewhere (`self.octant` into an enum), but it forces you to step outside the bounds of the rest of the system (type safety) that undermines and/or literally invalidates the potential gains from those bounds.
on one hand (c), you can be always-vigilant of the limits surrounding your data (exhausting, error prone)
on the other hand (rust), you can be always-vigilant of where you're stepping outside of type bounds and how that percolates through the rest of the system (exhausting, error prone).
imo the latter seems more complex!
Hahaha - love this take, exhausting and error prone either way!
In all seriousness, I find the latter to be preferable because it forces the "always-vigilance" into the code itself - you have to mark your unsafe functions as unsafe, which makes it clear when violating a function's contract can lead to UB. This is different than C, where functions may implicitly cause UB if used incorrectly (and this may, or may not, be written in the documentation). Also, I find that having to step outside the type system is a relatively rare occurrence; most application-level code doesn't require it. So Rust's strictness is a benefit in my eyes.
Maybe use `if ()` ?
That certainly makes the code more readable and probably would change the output of the compiler
if (self.octet < 0) {
and
if self.octet < 0 {
do the same thing in Rust!
@@ahdog8 ok =-=
if (you think that's more readable) then sure, go ahead
why use unsafe here? its uneccesary!
I don't understand why the optimizer would do this.
In the .then_some statement, isn't it implied that the check for self.octant < 7 happens before the unsafe code? Why would the compiler go back in time and optimize this check after you had run it, and is clearly dependant on it?
There's many cases of UB causing time travel. Raymond Chen has an article about it from 2014, and there's a StackOverflow question from around the same time. The TLDR is that because "undefined behaviour" is assumed to never happen, it can be exploited to perform aggressive optimisations, including reordering operations.
then_some is always called, no matter if the bool is true or false. It just discards the value given as a parameter in the false case. This also means that the argument is always evaluated (unlike in that if statement in the fix).
They are not dependant on each other. I don't know if Rust has parameter evaluation order rules, but even if it does, since those two parameters have no side effects, they can be evaluated in any order.
@@vytah Order of evaluation is not important here, since it's two separate expressions.
The argument for then_some is actually allocated on the stack, so his code actually looks like this to the compiler:
let __temp = unsafe { Octane::from_raw(self.octane) }:
(self.octane < 8).then_some(__temp);
When you look at it this way, since Octane MUST be less than 8 as it is illegal to construct an enum outside of it's range, then octange must be less an 8.
Not being familiar with the exact semantics of then_some(), I think the explanation would have benefited from mentioning the unsafe expression is being eagerly evaluated. Otherwise, the optimization makes no sense.
but you didn't use unsafe in your function? Why did it complain? Who's to say that it won't happen in any other code?
Hmm, I don't understand what you mean. I see an "unsafe" right there in the code
@@hemerythrin you're right I'm blind
is your project open source?
I eventually hope to turn the project into a publishable game or service, so I don't plan on open-sourcing the complete engine in the near future. However, many custom components of the engine (like the event library, networking library, etc.) are available and open-source on my GitHub!
1st rule of solving mystery bugs - turn off the optimizer. I've found at least a couple bugs in the past 35 years like this.
I think there is a function on `bool` that takes a closure and does the same as then_some? Regardless, very cool video covering a potential pitfall when writing unsafe and showing how parts outside of unsafe can be broken by unsafe blocks. This is also why unsafe justification comments are very useful, to explicitly acknowledge what you have done and why.
Yes, it is the `then` function.
Pretty sure, given your explanation of the error, that the compiler assumed it was true and didn't bother you, because you used "unsafe". Had you not used it and listened to the compiler, it would tell you that there's an issue.
its nightly duh
This same bug occurs on stable. I just happen to use nightly for other reasons :)
ohh I really didnt know srr @@DouglasDwyer
Make something work first, then optimize it later.
Use dark mode
no
@@DouglasDwyer I blew my eyes out.
Man disable that startup music.
unsafe Rust is a nightmare for a lot of reasons.
MY EYES (good video. the light mode just hurts my soul (and also remember that light attracts bugs :>.)(its just my preference I mean no offense))
Funny that all comments are about smth but not about ideotic UB in rust
That rare moment when you blame the compiler for a bug and its actually at fault.
Nasty bug, I do think they seem like they crossed a line… thanks for sharing
I do think that this is a bug in to compiler. It shouldn't apply optimizations near unsafe code. Or if it does, it should complain that your code contains something that is never executed.
to me the fact that the compiler is using knowledge from inside the unsafe block is a bug. compiler shouldn't pretend to understand what you're doing in an unsafe block - that's it's definition - I'm going to be doing UB
Who uses rust nowadays
Uh I think your fix has the exact same logical flaw, and a perfectly optimized compilation would recreate the same bug. You're still checking for something the type says will always be true, then unsafely creating something that might violate the type. You just switched to a syntax the compiler isn't yet smart enough to optimize, recreating the bug
that honestly seems like if its wrapping an unsafe, it should not optimize it out because it may be doing something important to make the unsafe code safe
The main problem was that the unsafe code *wasn't* safe, regardless of the check I put around it. I was creating an invalid Octant enum, which is never legal to do (no matter what other checks you make). So I was violating what you are "supposed" to be allowed to do inside that unsafe block, hence the undefined behavior :)
imagine there were greater indirection, though: let's say the unsafe enum was wrapped a few call stacks back and passed in. can it still no longer make the optimization? if so, then the presence of _any_ unsafe anywhere would be likely to undermine the optimizations made possible by the type system with extremely wide reach.
it's a bit of a lose-lose: either force actual safety by not optimizing anywhere unsafe, which will mean programmers essentially can't use the "unsafe" feature. or treat unsafe as though its safe, which will mean programmers can't rely on the safety guarantees (and in fact now have to be aware of a new complex category of bug that might come up even when you _are_ being safe within your "unsafe")
That's not how the unsafe block works. It's YOUR job as the programmer to make sure that your unsafe code is actually safe, you cannot rely on the compiler helping you out. The unsafe block is an escape hatch, it's basically you telling the compiler "trust me bro, I know what I'm doing". So the compiler just trusts you. With great power comes great responsibility.
Safe means the compiler ensures there's no undefined behavior. Unsafe means *you* have to ensure this yourself. In either case, having undefined behavior is never okay
@@hemerythrin and in this case the compiler got rid of a check that blocked an unsafe block from actually being unsafe
This is what you get when a compiler tries to outsmart the guy who's writing the code - instead of doing what it's told to do.
The actual optimization is just removal of redundant checks. Almost every language has it since its so simple and clear.
If you don't know how enum work in Rust this is a rough translation of the issue. "Assert(Oct < 8); if Oct < 8 {...}", since it's not volatile the second read is redundant and removed. It's not a complex optimization just somewhat unexpected transformation.
@@dynfoxx It's so "simple and clear" that it took the guy hours to figure it out.
except in this case, the compiler did what what the guy told it to do. It creates the enum regardless of if the check is true or not (the expression is evaluated before being passed to the `then_some` function). Rust's rules say that creating an enum outside its range is UB, and that's something you should know before using unsafe. Even if the check wasn't optimized out and it did return None at correct times, the expression is still evaluated and causes UB, as the guy told the compiler to do. The compiler is not at fault here.
@@dynfoxx That's exactly what I'm saying: I don't like compilers doing "unexpected transformations". You can either exceed the value of "7" in *self.octant* or you can't. If you can, the check is valid, if you can't, the check is superfluous. It's either or.
@@HansBezemer I should have been more clear, "somewhat unexpected transformation" has nothing to do with the compiler optimization. The compiler generated the exact code he told it to, it's unexpected that then_some is eager and that he would use it like this.
You can exceed the value of 7 in self. octant. The issue is not if the check is valid(it is) the issue is its redundant. EX. "X = 10; if X > 5 {...}", here the if statement will be removed by the same optimization, the if is valid its just redundant. We know X will be 10 for that if statement and can remove it entirely. If there is an outside reason its not then it needed to be a volatile read. In our case we wanted to only set X to 10 if it was more then 5, it's a logic error in both cases.
His code is basically doing a compile time assertion that during that function the value is less then 8. How do we make it not assume that? Either have the creation of the enum dependant on the check or make the enum valid for any value with non exhaustive.
EX. "If oct < 8 {const_assert(oct < 8);}" we still "assert" but now it's backed up by a runtime check. It may look as though we can propagate the const_assert up and remove the if but we can't. With that change what was 2 separate checks against the length becomes 1 connected check and can't be optimized out.
A more c/c++ example would be something like "auto array{...}; auto X{array[20]}; if(array.size() > 20) {...}" if going past the end of array is UB the same assertion "can" be made turning the code into this. Ex "constevalassert(array.size()> 20); if(array.size() > 20){...}". The same optimization is done and the if is removed.
Hopefully that makes sense.
C++ does not have this problem. Literally.
In C++ it is UB to set an enum value that is out of the defined range. If the compiler uses this then you will get the same issue or worse in C++.
@@dynfoxx at least C++ will not skip this condition
@@morglod It depends on how your write the code. For example a ternary operator is not eager and would limit the creation to the conditional. However something like value_or is eager even though documentation states it's equivalent to a ternary.
Either way C++ does have this issue since you can recreate it with a simple if else.
Thanks. It appears I will continue only writing c
I’m afraid I’ve got some bad news for you regarding C.
This can also happen in C
... did you just comment about using C on a Rust video? Prepare to get flamed. Your death will be "blazingly fast".
Jokes aside - undefined behavior is infinitely more prominent in C, so it's pretty much the worst language to make your point here. If anything, Rust and some other newer languages handle unsafe-ness much more cleanly. C# is one I recall having an unsafe block as well.
The difference is that in Rust, you could write this using safe code if you wanted
This kind of UB is a thing in every modern compiler, the difference is that in rust, all UB is only allowed to be located in unsafe blocks instead of literally anywhere.
google Undefined behavior can result in time travel by Raymond Chen
Basically, this:
#include
int table[4] = {0};
bool exists_in_table(int v)
{
for (int i = 0; i