Replace stack overflow checking with stack probes

[Zoxc]

We currently abuse LLVM segmented stack support to check for stack overflows. It would be more efficient to use guard pages to detect these. We already have guard pages on all the stacks. However to ensure that the code doesn't skip the guard pages, we need to insert stack probes. LLVM already can generate code for that on x86 and ARM for Windows. We'd just need to expose that as an option on other platforms.

It would be nice if support for stack probes could be added to MIPS in LLVM too, so we can get rid of the runtime support for the stack overflow checking.

Using stack probes is also easy and desirable to support in freestanding mode.

[alexcrichton]

Here's a comment in the past about this. Sadly I don't think "just use a guard page will cut it" for the reasons outlined in that comment. That being said, I'd love to stop using segmented stacks!

[Zoxc]

I do think printing out a error message is a bad thing. On Windows it means interfering with the dialog which informs the user about an error and allows developers to debug the application. On Linux it interferes with debugging. If such a message desired for some reason, we can support it, but the POSIX solution probably isn't very pretty.

I was wondering what the impact of this would be, so I commented out the code generating the split stack attributes and did some simple benchmarks:

2.35% reduced size of librustc
4.11% less time compiling libcore
19.3% less time running shootout-fibo

[thestinger]

Printing an error message on stack overflow would be trivial if there weren't green threads. It's as simple as installing a signal handler and print out an error if the address is located in the guard page range. It's yet another case where green threads make the language significantly worse than C++. I don't think there's a sane way to do it without horrific spin locks in today's Rust unless printing a special error message is not a requirement.

[thestinger]

Anyway... the segmented stack support only catches overflow when it happens to occur on the Rust side rather than in C code that's being called. It doesn't actually work. For example, an infinitely recursive function may be allocating memory and there's a good chance it will be jemalloc triggering the overflow.

[Zoxc]

We can give error messages for libgreen by having it inform libnative about the active guard page. Foreign code might skip guard pages on non-Windows platforms, so we won't catch all stack overflows.

[thestinger]

It's the platform's problem if it doesn't build with -fcheck-stack. Stack frames that large aren't common in C code anyway.

[pcwalton]

@thestinger Knock off the general comments about how Rust is a better or worse language than C++ please.

[pcwalton]

Anyway, I totally agree with the thrust of using guard pages here, and would like us to move away from segmented stacks as soon as possible. I personally don't think good error messages in libgreen should block us. The fibo benchmark is particularly compelling.

I don't see why libgreen is relevant anyway; if there's a guard page either way, just have libgreen handle it in the same way as libnative. It should be easy to run enough of Rust from the signal handler to print out an error message before dying.

[huonw]

There was some discussion on the LLVM mailing list about this:

• http://article.gmane.org/gmane.comp.compilers.llvm.devel/75230
• http://article.gmane.org/gmane.comp.compilers.llvm.devel/75399 (response)

[Zoxc]

That may have been me.

[thestinger]

http://togototo.wordpress.com/2014/08/05/fibonacci-numbers-on-the-galaxy-s3-arm-benchmarks-of-rust-ocaml-haskell-go-racket-lua-c-and-java/

[Zoxc]

I do have an implementation of the LLVM part for x86 and perhaps ARM (not sure how comprehensive that support is).
Zoxc/llvm@llvm-mirror:master...stprobe

I don't know enough about MIPS to implement that in LLVM or enough about MIPS and ARM to implement the __probestack support function.

[huonw]

http://togototo.wordpress.com/2014/08/05/fibonacci-numbers-on-the-galaxy-s3-arm-benchmarks-of-rust-ocaml-haskell-go-racket-lua-c-and-java/

That fibonacci implementation is tail recursive, and optimises to a loop:

else-block.i.i.i:                                 ; preds = %else-block.i.i.i.preheader, %else-block.i.i.i
  %.tr710.i.i.i = phi i64 [ %107, %else-block.i.i.i ], [ %104, %else-block.i.i.i.preheader ]
  %.tr69.i.i.i = phi i64 [ %106, %else-block.i.i.i ], [ 1, %else-block.i.i.i.preheader ]
  %.tr8.i.i.i = phi i64 [ %.tr69.i.i.i, %else-block.i.i.i ], [ 0, %else-block.i.i.i.preheader ]
  %106 = add i64 %.tr8.i.i.i, %.tr69.i.i.i
  %107 = add i64 %.tr710.i.i.i, -1
  %108 = icmp eq i64 %107, 0
  br i1 %108, label %_ZN3fib20hcf5cee5c8487747eOaaE.exit.i.loopexit, label %else-block.i.i.i