Ask not what the compiler can do for you

https://github.com/juspay/hyperswitch/wiki/Ask-not-what-the-compiler-can-do-for-you

by manojr13 • 3 years ago

100 79 3 years ago

github.com

Nars0883• 3 years ago

Is this the case with all statically typed languages? I think I have faced the same issue with PureScript

(PS: I'm a contributor)

kibwen11• 3 years ago

With exclusively static dispatch I feel like it should be possible to unconditionally detect at least the presence of recursion at compile-time, but in the presence of dynamic dispatch (as in the article) I think it might be impossible for a compiler to guarantee that it can statically detect recursion. (I have no basis for these claims other than gut feeling.)

duped• 3 years ago

With exclusively static dispatch I feel like it should be possible to unconditionally detect at least the presence of recursion at compile-time,

This is equivalent to solving the halting problem, and therefore impossible in the general case.

Tools can use heuristics to make a guess. Dynamic dispatching to mutually recursive functions is one example where those tools fail. But that also includes things like checking a conditional before calling a function. The tool can check unconditional infinite recursion, but it can't tell you for certain that a branch that may be infinite is always taken.

munificent3• 3 years ago

Even without object-oriented dynamic dispatch, if the language supports closures or function pointers, you still lose the ability to statically analyze all call targets.

hoosieree• 3 years ago

I'm not an expert on fuzzing, but I think a fuzzer would be able to discover this issue.

loeg5• 3 years ago

I don't think the recursion in this case is dynamically dispatched. It returns a dyn Future, but that isn't the same thing.

itsnishant• 3 years ago

With exclusively static dispatch I feel like it should be possible to unconditionally detect at least the presence of recursion at compile-time,

That's true, and Rust as a language does do so, but in case of recursion for `async` function rust itself suggests to go the `dyn` route. Adding more to the post, it seems that the use of `async-trait` was the reason that they didn't have any choice in the matter to choose static dispatch, as the language as a whole doesn't support async traits, (just yet! ^-^)

thala• 3 years ago

Are there any tools to identify stack sizes and function traces?

Atlas22• 3 years ago

Have not used it myself but looks like there is StackAnalyzer[0]. Have done it myself by adding analysis to angr[1] but it pretty much boils down to trying to solving the halting problem for many large programs (an unbounded recursion or alloca makes the max stack size infinite)

[0] https://www.absint.com/stackanalyzer/index.htm

[1] https://angr.io/

hra5th• 3 years ago

For rust code, I have found https://github.com/japaric/cargo-call-stack to be the best available option, as it does take advantage of how Rust types are implemented in LLVM-IR to handle function pointers / dynamic dispatch a little better. An even better solution would try to use MIR type information as well to further narrow down targets of dynamic calls in a Rust-specific way, but no such tool exists that I know of.

pdimitar2• 3 years ago

Not sure rustc can do a lot about this case but maybe a static analysis tool can complement it.

richardwhiuk2• 3 years ago

To some extent, all compilers are static analysis tools.

I think clippy could be enhanced to spot this.

pdimitar2• 3 years ago

Yep, it likely could. Spotting something that usually is an error now being wrapped in `Pin<Box<...>>` would hopefully be not too hard.

loeg5• 3 years ago

If it can detect the recursion in the non-dyn return case, it seems like it ought to be able to do the same once dyn is added.

munificent3• 3 years ago

I don't mean this to sound superior or critical.

I found this article a little surprising because the authors seem to have an intuition about the compiler that I have never had. I've never expected potential stack overflows from unbounded recursion to be caught by the compiler. I've been delighted every now and then when a compiler gives me a warning when it can detect it. But I have always had stack overflows in my mental bucket of "stuff it's my responsibility to think about".

Maybe this says something about how compilers have gotten smarter and more helpful since I first cut my teeth on them.

humanrebar3• 3 years ago

The branding (or at least the zeitgeist) around Rust is that it is a "safe language", which implies that bugs are all logic bugs or somehow the fault of the programmer for doing something "unsafe" (hence the keyword).

Anyone who thinks about it for a bit knows there are limits to guarantees of safety. It's notoriously impossible to prove that a program terminates appropriately, for instance.

So I can understand some shock to run into the arcane all of a sudden. It must be especially shocking because it feels especially out of place.

ecshafer• 3 years ago

Rust is a safe language for a specific definition of safe regarding a class of memory errors.

bobbylarrybobby• 3 years ago

Rust is pretty clear about “safe” meaning no memory unsafety in unsafe-free code. It certainly doesn't market that code without unsafe will be bug free (this would force the safe subset to no longer be Turing complete).

hinkley• 3 years ago

I have chosen this as a hill to die upon:

Philosophically, the Halting Problem and the Pigeonhole Principle are very similar. They both talk about what is not possible with arbitrary input, but they have very little to say about practical input. You can't compress a random number generator. You can compress human communication, in any form, some of them famously. The existence of PP or HP are only boundary conditions, as entropy goes to infinity.

Humans also call entropy 'chaos', which has a connotation that's doubly meaningful in information theory. Chaos obfuscates. It's only useful when obfuscation is the point (encryption). We run away from it as fast as we can, and the farther we get from in the more interesting opportunities open up. Languages that disallow certain patterns can solve the halting problem for pieces of the application, maybe even entire 'useful' applications.

kccqzy• 3 years ago

I have the same thought! But then again when I tried a simple example in clang the -Winfinite-recursion warning triggered. In the compiled code, clang compiled the function as just `ret`, which is alright because C++ standard says if a thread does not eventually do an atomic op or call certain functions then it's undefined behavior.

Still wouldn't recommend anyone to rely on the compiler to catch this.

m463• 3 years ago

But I have always had stack overflows in my mental bucket of "stuff it's my responsibility to think about".

I remember working on kernel modules, and coming from userland being surprised to find kernel stacks of 16k or 24k are common. Anything that could help with that without having to do kernel debugging on weird errors would be great.

rcxdude2• 3 years ago

Static stack analysis is a thing, though it's a thing which annoyingly lacks any real open-source implementation, and any good tooling whatsoever in my experience. It does limit what you can do though, since dynamic dispatch and recursion can quickly make it fail.

Arnavion2• 3 years ago

It's actually very easy for rustc to raise a compiler error if you have recursion inside an async fn. It naturally falls out from the way async is implemented, because the resulting Future type would be infinitely sized.

An `async fn` essentially compiles to a state machine where each `.await` is a transition to another state, and local variables and the future being `.await`'d are data of that state. If a future were to `.await` itself, that state data would contain the future itself, which means the future would need to be larger than itself, which is impossible. Similarly corecursion would simultaneously require that `FooFuture` contain `BarFuture and `BarFuture` contain `FooFuture`, which would require both to be bigger than the other, which is again impossible.

The solution to the infinite size problem is to wrap the future in `Box<dyn Future>` before `.await`ing it, so that the state data is a fixed size (`Box<dyn Trait>` is always two pointers long, a data pointer and a vtable pointer). Since TFA was using the `#[async_trait]` macro which changes the function to return `Box<dyn Future>` (as the stable alternative to async-fn-in-traits / TAIT), it ended up suppressing the recursion error too.

bilekas• 3 years ago

It's certainly a Rust thing, and definitely a part of the appeal.

It doesn't remove the "stuff it's my responsibility to think about" but it certainly alleviates it. Your comment actually sounds like the first step to becoming a 'Rustacean'.

chubot4• 3 years ago

What I also think is weird is that people think seg faults and crashes are "unsafe".

In the terms of Cardelli, a stack overflow is a trapped runtime error -- and thus a SAFE behavior of a language runtime.

What's not safe is when your program keeps running in an unknown state:

- buffer overflows - who knows what it does after memory corruption?

- integer overflows, especially in C where the behavior isn't defined. But in Rust's release mode, these runtime checks are omitted, so that's unsafe too.

---

On the other hand, the behavior of null pointer exceptions and a stack overflows is SAFE. It protects you from undefined behavior at runtime.

Crashing is a DEFINED behavior -- it's also what happens on divide-by-zero by default, and apparently when Rust's allocators run out of heap memory.

This isn't a theoretical distinction, because diagnosing and fixing NPEs and stack overflows is easy compared to the other two.

And crashes can lead to denial of service, but not remote code execution, which is WAY worse.

btilly2• 3 years ago

I think that you're the weird one here.

The most common reason to GET a segmentation fault is memory corruption. Frequently from a buffer overflow. Which makes them the canary in the coal mine for bugs that often turn out to be exploitable security vulnerabilities.

So if a program segfaults on me and I don't know exactly why, I should dial my paranoia up and expect that it is insecure. That an attacker who looked at it could use it to take over my computer instead of simply leaving me with a core dump.

bombcar• 3 years ago

And crashes can lead to denial of service, but not remote code execution, which is WAY worse.

Some crashes in the past have lead to remote code execution, because a program that was supposed to be guarding/filtering something was caused to die, and the system failed open.

EE84M3i• 3 years ago

Rust has a particular definition of unsafe that they've documented here: https://doc.rust-lang.org/nomicon/what-unsafe-does.html

They have also documented some frequently discussed behavior that is not considered unsafe here: https://doc.rust-lang.org/reference/behavior-not-considered-...

For each of the items on the second list, I believe there are languages that would consider those behaviors "unsafe", but rust doesn't - ultimately it's an arbitrary choice. So, it's important to be clear about what model of "unsafety" we're talking about.

MindSpunk• 3 years ago

Dereferencing a null pointer is safe only on systems with an MMU to mark the 0 page as inaccessible so the processor can trap when it's accessed. On embedded systems with no MMU then 0 is a valid address just like any other.

By making null pointer dereference unsafe the compiler doesn't have to insert null checks for every single pointer access to maintain the same behavior as a CPU with an MMU.

kobebrookskC3• 3 years ago

how is integer overflow unsafe? integer overflow in rust is not ub, unless you opt into the *_unchecked methods

Someone• 3 years ago

On the other hand, the behavior of null pointer exceptions and a stack overflows is SAFE.

For many languages only if the OS (sometimes with a bit of help from the runtime/ compiler) protects you against them. Not all language specs require programs to abort when they occur, if only because checking for them on systems without a MMU is expensive.

stefanos82• 3 years ago

Is there any flag in Rust's compiler, like GCC's `-fstack-check` that checks for such behavior?

LegionMammal9783• 3 years ago

rustc already tells LLVM to use stack probing for sufficiently large stack frames, so it can give a short error message on stderr ("thread 'whatever' has overflowed its stack") before aborting the program. But the author is looking for a backtrace here.

The problem is that printing a backtrace is the responsibility of the program, as part of the global panic hook. But running arbitrary user code (e.g., Backtrace::capture()) during a stack overflow would be extremely unsafe, since the thread could be in the middle of some operation that does not expect to be interrupted.

The soundness criteria would likely be very similar to those for async signal handlers, which are extremely platform-dependent, so it would be a challenge to document all the safety preconditions. An alternative would be to especially bless backtrace-rs for stack overflows alongside the default panic hook, but I don't think even it can guarantee complete safety on all supported OSes.

loeg5• 3 years ago

The problem is that printing a backtrace is the responsibility of the program, as part of the global panic hook. But running arbitrary user code (e.g., Backtrace::capture()) during a stack overflow would be extremely unsafe, since the thread could be in the middle of some operation that does not expect to be interrupted.
The soundness criteria would likely be very similar to those for async signal handlers, which are extremely platform-dependent

This is more or less exactly the same as any stack-print-on-crash handler you might be familiar with. In theory you should be able to unwind using DWARF eh_frame data from anywhere. In practice this stuff isn't always perfect and it's much easier to rely on framepointers, if your compiler emits them. But switching to an alternative signal handler stack and unwinding your main stack is mostly worth trying -- worst case, you're already crashing.

cat-whisperer• 3 years ago

I don't fully understand the context or the overview of the problem, but for a large codebase, if you are using `tokio` runtime, which most rust based application go with. `tokio-console` is good for profiling and debugging, have you folks looked into that during the whole debugging process? I personally trust debuggers and debugging tools in such circumstances, as they can easily help zeroing down on such issues.

flooow• 3 years ago

Fortunately this particular problem should go away soon. Async-fn-in-traits is due to be stabilized in the next few months [1], which means that the use of #[async_trait] will no longer be necessary, which means the compiler will correctly surface a warning for unbounded recursion.

[1] https://blog.rust-lang.org/inside-rust/2023/05/03/stabilizin...

Nars0883• 3 years ago

Check this out: https://github.com/rust-lang/rust/issues/111177

loeg5• 3 years ago

The lack of warning does not seem to be related to #[async_trait] -- it's reproducible on a bare function, as shown in the post and in sibling comment's 2nd link.

Arnavion2• 3 years ago

The lack of warning is from returning `Box<dyn Future>`, which `#[async_trait]` emits. ( https://news.ycombinator.com/item?id=35834091 )

With async-fn-in-trait that flooow linked to (and more generally type-alias-impl-trait) there won't be a motication to use `Box<dyn Future>` in the first place.

nurettin• 3 years ago

Is this what happens when we are too complicit and entirely depend on our tooling to find mistakes?

lsampras• 3 years ago

I guess we can never expect the tools to find all the mistakes only the straight-forward ones (which seems to be a moving target)...

This could be an example of when things fall through the crack, while rust & its tooling eliminates most of the errors during compile time, it's not entirely impervious...

Overall I'd prefer depending on tooling to catch a subset of errors (which could miss 1 out of 20 times), rather than the added manual review effort with each change...

lukebitts• 3 years ago

What happens? We debug and find the error exactly like we would have to if the tooling was “worse”

Nars0883• 3 years ago

We spent decades trying to invent a sufficiently smart compiler when we should have been inventing a sufficiently empathetic one - @ekuber

It all makes sense now

xiaodai• 3 years ago

ask what ChatGPT can do for you instead.

Ask not what the compiler can do for you

Related Stories