Infinite loops/recursion are optimised incorrectly

[sgebbie]

I accidentally coded a recursion which then results in a segmentation fault. The difficulty is not so much that it crashes, but that there is very little feedback as to why it crashed. In my case, since I did this completely inadvertently (some over enthusiastic copy-paste before I reworked the code), I wasn't expecting to find a recursion. Once I found it, it was obvious.

So, my question is really one of is there any way for the compiler detect and warn about the problem, or the run-time to provide better feedback rather than simply a segmentation fault.

The following code triggers a segmentation fault.

actor Main

        new create(env: Env) =>
                recursion()

        fun recursion() =>
                recursion()

When run this results in generally results in the following output under Linux:

$ ./recursion 
Segmentation fault (core dumped)

And on some occasions Linux responds with the following slightly more helpful response:

$ ./recursion 
*** stack smashing detected ***: ./recursion terminated
Aborted (core dumped)

Admittedly, this is no worse than 'C' so maybe I'm just being hopeful:

void r() {
	r();
}

int main() {
	r();
}

$ gcc r.c -o r
$ ./r
Segmentation fault (core dumped)

Where as Java would at least provide a StackOverflowError:

public class Recursion {

    public static void main(String[] args) {
	    r();
    }

    private static void r() {
	    r();
    }

}

$ javac Recursion.java
$ java Recursion
Exception in thread "main" java.lang.StackOverflowError
	at Recursion.r(Recursion.java:8)
        ...
	at Recursion.r(Recursion.java:8)

[Praetonus]

This is a hard problem, and I don't think there is an ideal solution.

is there any way for the compiler detect and warn about the problem

It is possible, but there is no general solution. The basic idea is to look for cycles in the program's Control Flow Graph (CFG, the compiler's view of the "atomic" blocks of code in the program, like a branch of a conditional). Trivial cases like your example can be solved with relative ease but the general case is equivalent to the halting problem, which is undecidable (with some subtleties on actual computers but that doesn't change anything for us).

LLVM is able to do some limited CFG analysis for infinite recursion (or infinite loops, which are the same problem), often for optimisation purposes. The current implementation can cause surprising and even undesirable behaviour. For example, with optimisations enabled, your code is compiled down to this:

; Function Attrs: norecurse nounwind readnone
define fastcc void @Main_tag_create_oo(%Main* nocapture dereferenceable(264), %Env* noalias nocapture readonly dereferenceable(64)) local_unnamed_addr #5 {
  ret void
}

The recursion was completely eliminated and if you run the program, it will simply exit immediately. This won't cause much trouble but some cases are much more concerning. For example:

actor Main
  new create(env: Env) =>
    foo()
    
  fun foo(): U32 =>
    foo()

The Main.foo method is compiled down to:

; Function Attrs: nounwind readnone
define fastcc i32 @Main_ref_foo_I(%Main* nocapture readnone dereferenceable(264)) #0 {
  ret i32 undef
}

undef is LLVM's language for a garbage value that could be anything. A program doing something like this could run for a really long time seemingly without any problem and then go boom 3 months later, resulting in a very confused dev team.

These problems aren't new in LLVM land, both Rust and Swift (and probably many others) have been (and still are) subject to them.

The undef problem and other similar ones definitely are cases that we should strive to eliminate. The best approach that I can see would be to do our own CFG analysis before handing things to LLVM. The hard part would be to ensure we're covering every case that LLVM would screw up, and I don't see a solution for that.

is there any way for [...] the run-time to provide better feedback rather than simply a segmentation fault

There are various ways to do that based on the platform. There is libsigsegv on Linux, structured exceptions on Windows, and probably something that I don't know of on OSX. I've not dug into it much further but I think it would be possible to integrate these systems into the Pony runtime, assuming that a stack overflow always causes a segmentation fault or a structured exception.

[sgebbie]

Right that makes sense with regard to the compile time checks causing more trouble than they might solve and therefore probably not being appropriate.

However, taking a quick look at libsigsegv, it does actually seem like a viable solution for providing better feedback - it also seems to support OSX. It looks like it would introduce essentially no extra overhead into the runtime and the binary footprint change is only around 4K apparently (for static linking). However, skimming over the docs it was not immediately clear how easy it is to introduce in a heavily multithreaded application.

Also, I assume that if one were to try provide more feedback than simply "stack overflow" then one would need to hook into internal Pony bookkeeping in order to find the actor that triggered the overflow, and possibly the method.

All in all, probably not a high priority, but possibly still a nice-to-have.

[agarman]

[off-topic]
Support for tail-call elimination is nice. Having yield or call/cc for coroutines is also nice. I'm not sure Pony needs either as while, for, or repeat should be used instead of recursion and an actor be should be used whenever you need to trampoline.

[Praetonus]

@sgebbie I do think that we'll need some compile-time stuff to solve some of the problems, particularly the undef stuff and the "semantics" of crashing (more on that below).

@agarman These are all very interesting subjects, but let's keep this issue on topic (the problems arising from infinite recursion). If you'd like to discuss an idea about the language, I'd suggest the development mailing list. Also, note that Pony already supports tail-cail elimination through LLVM's optimisations (and the crux of the problem here is that these optimisations aren't modeling infinite recursion as we'd like them to).

---

The issue with the optimisation here is the absence of side-effects. That is, LLVM transforms any infinite recursion (or infinite loop) that doesn't contain side-effects into something that "doesn't happen". We can exploit that behaviour by making the code generator add no-op side-effects (an equivalent to a Pony DoNotOptimise.observe() call) to infinitely recursive functions.
Another issue here is that other optimisations can transform a seemingly halting construct into an infinite one. The naive answer to that would be to add our no-op side-effect to every function and to every loop but that would simply kill optimisation, even in halting cases (example in C++ with a loop). We could add a custom IR transformation pass running at key points between LLVM's passes and adding side-effects at the correct places. I'm not sure where these key points would be, we'd have to investigate.
Also, this seems very likely to change between different versions of LLVM. Because of that and other issues with optimisation changes across various versions of LLVM, maybe the right thing to do would be to support only one version of LLVM at a time and upgrade only when we have a plan to adapt our custom optimisation stuff. I'll give some more thoughts to that idea and probably open an issue for discussion at some point.

Also, I think there is an underlying semantic issue with crashes related to memory exhaustion (whether it is exhaustion of the heap due to too many allocations or exhaustion of the stack due to too much recursion) and crashes in general. My biggest problem is with the "no crashes" claim, which is very good from a marketing standpoint but isn't accurate.
First, we aren't preventing memory exhaustion crashes and I don't think we realistically can. Because of that, I think memory exhaustion crashes should be treated as a separate category of crashes. There also is a problem with the semantics of an overflowing collection that we should discuss at some point.
Second, there are cases where we want to do something that could crash in order to save a runtime check (e.g. /~ (unsafe division), which doesn't prevent division-by-zero crashes), and we don't want to do that thing in C for some reason (the most compelling one being that Pony offers better optimisations in some cases (e.g. alias analysis)). In these cases the imprecise "no crashes" claim is a problem.
A possible reformulation of the claim could be "no non-memory exhaustion crashes by default". What I mean by "by default" is that the user should intentionally go out of their way and badly use a particular feature documented as causing crashes if used outside of its contract in order to cause a crash. This kind of feature should be guarded either via object capabilities or the --safe compiler flag. I think it should also have a convoluted syntax in order to discourage the user from using it unless they really need to. By this logic, the unsafe arithmetic sugar (op~) should be removed and unsafe operations should be guarded in some way. This ties into another idea I've been exploring for some time, which is compiler intrinsics exposed to the user with FFI-like syntax and guarded with --safe.
The last thing to consider is the semantics of crashes with regards to undefined results and the trust boundary (which we discussed a while back.) That is, which crashes should be considered deterministic "side-effects" of the program and which should be left as possible results of violating the trust boundary (i.e. in undefined behaviour land). Ideally, every crash should be deterministic but that's not possible in every case. An unsafe division crash could be deterministic (and that solves the problem in the undefined results definition about hardware traps), but if we were to give direct access to Pointer manipulation to users, crashes from that would have to be results of undefined behaviour and trust bounday violation. To sum it up, the various categories of nasty stuff from unsafe operations could look like this:

• Undefined result: a garbage value that should be stable (i.e. not magically change between evaluations). There are some complications here, see this for example
• Deterministic crash: A crash that should always happen regardless of the underlying implementation (i.e. by resulting from a scenario that the specification defines as provoking abnormal program termination)
• Trust boundary violation: Anything can happen

And then we'd have memory exhaustion crashes aside of that. Infinite recursion would be defined as possibly causing a memory exhaustion crash ("possibly" because of tail-call elimination).

[Praetonus]

Summary of everything that has been said around this problem.

There is ongoing effort in the LLVM community to fix the various issues with infinite loops and infinite recursion. See the list of links below. At our level, there isn't much we can do. Detecting trivial infinite constructs in the compiler is certainly possible but I'm not sure it'll be useful, as real-world example are usually more complex.

https://bugs.llvm.org/show_bug.cgi?id=965
https://lists.llvm.org/pipermail/llvm-dev/2015-July/088095.html
https://lists.llvm.org/pipermail/llvm-dev/2017-October/118558.html

[SeanTAllen]

This is blocked.

[ergl]

This has been fixed in LLVM 12. Compilling the original code should now produce an infinite loop. Compiling in debug mode might still throw "bus error" when run.

This is the resulting IR when compiling @Praetonus code with optimizations enabled:

define dso_local void @Main_Dispatch(i8* %0, %1* nocapture readnone dereferenceable(8) %1, %3* nocapture readonly dereferenceable(8) %2) unnamed_addr #7 !pony.abi !2 {
  ; snip (a bunch of setup)
  br label %12

12:                                            
  br label %12
}

And this with optimizations disabled (note the recursive call on %0 =):

define fastcc i32 @Main_ref_foo_I(%Main* dereferenceable(256) %this) unnamed_addr !dbg !140 !pony.abi !4 {
entry:
  %this1 = alloca %Main*, align 8
  store %Main* %this, %Main** %this1, align 8
  call void @llvm.dbg.declare(metadata %Main** %this1, metadata !143, metadata !DIExpression()), !dbg !144
  %0 = call fastcc i32 @Main_ref_foo_I(%Main* %this), !dbg !145
  ret i32 %0, !dbg !145
}

[SeanTAllen]

When we upgrade to LLVM 12, we should include a CHANGELOG entry for closing this as part of that PR.

@ergl @jemc @kulibali

[ergl]

Note: #2592 can be reverted when we upgrade to LLVM 12