Rust's main-stack thread guard is implemented incorrectly; breaks nearly all Rust programs on 64KB-pagesize post-stack-clash Linux

[infinity0]

Rust implements its own userspace "stack guard", the purpose is to print a nice error message about "stack overflow" rather than segfault. This is applied to each new thread, as well as the main thread:

https://github.com/rust-lang/rust/blob/master/src/libstd/rt.rs#L44
https://github.com/rust-lang/rust/blob/master/src/libstd/sys/unix/thread.rs#L248
https://github.com/rust-lang/rust/blob/master/src/libstd/sys/unix/thread.rs#L229

The start address of the stack is calculated effectively via pthread_attr_getstack (pthread_getattr_np (pthread_self))

This is where the problems occur. pthread_getattr_np is not defined by POSIX and the manual page does not specifically define what the exact behaviour is when getting the attributes of the main thread. It works fine for non-main threads because they are usually created with a fixed-sized stack which does not automatically expand. So the start address is pre-defined on those threads.

However on Linux (and other systems) the real size of the main stack is not determined in advance; it starts off small and then gets automatically expanded via the process described in great detail in recent articles on the stack-clash bug. In practise, with glibc the above series of function calls returns top-of-stack - stack-rlimit when called on the main thread. This is 8MB by default on most machines I've seen.

However, most of the space in between is not allocated at the start of the program. For example, a test "Hello World" Rust program has this (after init):

3fffff800000-3fffff810000 ---p 00000000 00:00 0 
3ffffffd0000-400000000000 rw-p 00000000 00:00 0                          [stack]

with ulimit -s unlimited it looks like this:

1000002d0000-1000002e0000 ---p 00000000 00:00 0 
3ffffffd0000-400000000000 rw-p 00000000 00:00 0                          [stack]

OTOH, the Linux stack guard is not a physical guard page but just extra logic that prevents the stack from growing too close to another mmap allocation. If I understand correctly: Contrary to the get_stack_start function, it does not work based on the stack rlimit, because this could be unlimited. Instead, it works based on the real size of the existing allocated stack. The guard then ensures that the next-highest mapped page remains more than stack_guard_gap below the lowest stack address, and if not then it will trigger a segfault.

On ppc64el Debian and other systems (Fedora aarch64, Fedora ppc64be, etc) the page size is 64KB. Previously, stack_guard_gap was equal to PAGESIZE. Now, it is 256 * PAGESIZE = 16MB, compared to the default stack size limit of 8MB. So now when Linux tries to expand the stack, it sees that the stack is only (8MB - $existing-size) away from the next-highest mmapped page (Rust's own stack guard) which is smaller than stack_guard_gap (16MB) and so it segfaults.

The logic only "didn't fail" before because the stack_guard_gap was much lower than the default stack rlimit. But even here, it would not have been able to perform its intended purpose of being able to detect a stack overflow, since the kernel's stack-guard logic would have caused a segfault before the real stack ever expanded into Rust's own stack guard.

In case my words aren't the best, here is a nice diagram instead:

-16MB-x     -16MB                           -8MB                x           top
|           |                               |                   |           |
--------------------------------------------[A]-----------------[<--   stack]
G                                                               S

[..] are mapped pages. Now, Linux's stack guard will segfault if there is anything between G and S. For Rust, its own stack guard page at A causes this. Previously, G-S was much smaller and A was lower than G.

AIUI, Linux developers are talking at the moment about the best way to "unbreak" programs that do this - they try not to break userspace. But it is nevertheless incorrect behaviour by Rust to do this anyways, and a better way of doing it should be found. Unfortunately I don't have any better ideas at the moment, since the very notion of "stack start address" for main threads is apparently not set in stone by POSIX or other standards, leading to this sort of misunderstanding between kernel vs userspace on where the "start" really is.

I'm not sure about the details of other systems, but if they implement stack guards like how Linux does it (i.e. against the real allocated stack rather than against a stack rlimit), and the relevant numbers match up like they do above, then Rust's main stack guard would also problems there.

CC @arielb1 @bwhacks @cuviper

This causes rust-lang/cargo#4197

[infinity0]

Some test code in case someone wants to play with it themselves on a 64KB-pagesize system:

const SZ : usize = 24576;
fn main() {
  let ys: [u64; SZ] = [0; SZ]; // 192KB of space
  println!("Hello world! {} {}", ys[0], ys[SZ-1]);
  println!("Address: {:p} {:p}", &ys[0], &ys[SZ-1]);
}

#!/bin/sh
exec gdb -d ~/glibc-2.19/debian/ -d ~/glibc-2.19/malloc -d ~/glibc-2.19/nptl -d ~/glibc-2.19/sysdeps -q "$@" -ex 'run' ./test

[jonas-schievink]

The logic only "didn't fail" before because the stack_guard_gap was much lower than the default stack rlimit. But even here, it would not have been able to perform its intended purpose of being able to detect a stack overflow, since the kernel's stack-guard logic would have caused a segfault before the real stack ever expanded into Rust's own stack guard.

Just to clarify: Does this mean that this mechanism has always caused a segfault when the stack grew to the page just before (or after, since it grows backwards) the guard page? This would mean that Rust's guard page was never hit on Linux.

[infinity0]

It seems so - you can set up a similar test even on amd64 (4KB pagesize) pre-stack-clash with fn main() { println!("Hello world!"); } and sh -c 'ulimit -s 24; ./test', if I set this to 20 or 16 I start seeing occasional segfaults, I never see any "stack overflow" message from Rust. Non-main threads should be fine, though.

[cuviper]

That may just be that you're setting that amd64 stack too small for even the init calls to work. I can get the message from the main thread trivially with recursion, on an older kernel:

$ echo 'fn main() { main() }' | rustc -
warning: function cannot return without recurring
 --> <anon>:1:1
  |
1 | fn main() { main() }
  | ^^^^^^^^^^^^^^^^^^^^
  |
  = note: #[warn(unconditional_recursion)] on by default
note: recursive call site
 --> <anon>:1:13
  |
1 | fn main() { main() }
  |             ^^^^^^
  = help: a `loop` may express intention better if this is on purpose

$ ./rust_out

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted

But on an x86_64 stack-clash-patched kernel, that just seg-faults.

So I guess we can say that stack-clash kernels make the guard page useless with 4KB pages, and actively harmful with 64KB kernels. I think it's reasonable to blame the kernel's behavior though.

[cuviper]

cc @alexcrichton and #42816. While stack probing is currently x86-only, I think it will also have the effect of hitting the kernel's safety margin before anything will reach the custom guard page.

[infinity0]

I can confirm that your test program prints the stack overflow message, but it seems that the rust guard page is still not getting hit, the segfault gets raised and caught by rust without hitting rust's guard page:

$ uname -a # pre-stack-clash
Linux myhost 4.9.0-3-amd64 #1 SMP Debian 4.9.30-2 (2017-06-12) x86_64 GNU/Linux
$ gdb -q -ex 'set disable-randomization off' rust_out
Reading symbols from rust_out...done.
(gdb) run
Starting program: /home/infinity0/rust_out 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x00005585a6e63833 in rust_out::main::h2ca3ad78a267f4b5 ()
(gdb) i i
  Num  Description       Executable        
* 1    process 8722      /home/infinity0/rust_out 
(gdb) shell cat /proc/8722/maps
[..]
7ffd4d4f6000-7ffd4d4f7000 ---p 00000000 00:00 0 
7ffd4d4f8000-7ffd4dcf6000 rw-p 00000000 00:00 0                          [stack]
[..]
(gdb) p $_siginfo._sifields._sigfault.si_addr
$1 = (void *) 0x7ffd4d4f7ff8
^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not in the guard page range 7ffd4d4f6000-7ffd4d4f7000 
(gdb) p/x $rsp
$2 = 0x7ffd4d4f8000
(gdb) c
Continuing.

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
51	../sysdeps/unix/sysv/linux/raise.c: No such file or directory.

I wonder why this doesn't happen on the post-stack-clash kernels though..

[cuviper]

Ah, I think it's because the init ends up using an offset two pages above its base, and then the signal handler looks for faults only one page below that. So in fact it's never looking for the real guard page, but the one above it that the kernel triggers itself. And in post-stack-clash kernels, the kernel now triggers SIGSEGV many pages above, so it doesn't even match that offset=2 any more.

[infinity0]

Ahhh, OK. So it actually sounds like, whoever originally wrote this code, knew about the actual Linux stack guard behaviour as described above, and hardcoded these offsets in appropriately. They just didn't expect it to change from kernel to kernel. If there is a way to get the kernel stack guard size at runtime, rust's stack guard could actually be made to work without additional kernel patches, we would just need to adjust the offsets in the two pieces of code that you linked. (edit: Though, the behaviour in the case of an unlimited stack would not be very reliable.)

[cuviper]

I think at least on Linux, we might be better not to add our own guard page to the main thread at all. We only need a way to determine if a particular fault was stack-related for reporting purposes.

[infinity0]

@aturon It looks like you wrote the original code in 2b3477d, do you have any comments?

[alexcrichton]

Hm I'm a little confused and don't quite understand the OP. It makes sense to me that the main thread has "special stack growth functionality" which manually unmapping some page inbetween messes with. What I don't understand is how this relates to page size or what the meaning of a "post-stack-clash kernel" is. What was changed in the kernel? This is just a problem of error reporting, right?

@cuviper note that #42816 can't land right now due to a test failing on Travis but it's passing locally for me (specifically a test that the main thread stack overflowing prints a message). I wonder if that's related to this?

Is there a recourse for us to deterministically catch stack overflow on the main thread? Or can we only do that for child threads?

[tavianator]

@alexcrichton "Stack Clash" is a series of vulnerabilities reported recently in a bunch of different projects. Ultimately they came down to triggering some stack overflow vulnerabilities to jump over the stack guard page directly into the heap, resulting in exploits rather than just crashes.

A mitigation was added to recent Linux kernels that significantly widens the size of the stack guard, making this exploitation technique much more difficult. The new size of the guard is 256 pages instead of 1 page, hence the relation to the page size (though Linus recently suggested a hard-coded 1MiB gap instead of a page-size-dependent gap).

I don't think this is just a problem of error reporting. The issue is that if the main thread stack ever needs to grow, even if there is room above Rust's "manual" guard page, there is no longer room for the stack plus the kernel's new gigantic guard area. This results in a stack overflow segfault for any stack usage above the initially mapped area, well below the expected limit of 8MiB.

[cuviper]

I'll try to restate it.

When a program starts, only a relatively small stack is actually mapped to begin with. If you page-fault past the end, the kernel will dynamically add more pages up to the rlimit. But if a new stack page would end up right on top of some existing mapping, the kernel will refuse and you'll get a SIGSEGV. Nobody wants the stack to seemlessly flow into an unrelated mapping, after all.

Rust is adding a PROT_NONE guard page at the "bottom" of the rlimited stack. As far as the kernel is concerned, this is an unrelated mapping, so now it starts enforcing that the stack can't grow to a point that would neighbor that mapping. So with our page in place, the kernel will fault when the stack reaches the page above it. That's why our handler has to use offset=2 for seeing if a faulting address is a stack overflow.

The new kernel behavior is that instead of enforcing just a one page gap between stack growth and other mappings, the kernel now enforces 256 pages. So now our guard page causes the kernel to fault any access in any of the 256 pages above that. We do get the right SIGSEGV, but our handler doesn't recognize it as a stack overflow. (I guess it still would if you happened to jump right to the page above our guard.)

On 4KB systems, 256 pages is 1MB, so the placement of our guard page makes the last 1MB of stack unusable. On 64KB systems, 256 pages makes 16MB unusable. With rlimit typically only 8MB, our guard page makes it so the stack effectively can't grow at all.

And yes, it does seem likely that this is why #42816 is getting raw SIGSEGVs instead of reporting the stack overflow nicely. I'd guess your own kernel does not have these updates yet, and CI does.

[alexcrichton]

Thanks for the info @cuviper and @tavianator! That all makes sense to me.

Sounds like detection of a stack overflow on the main thread right now basically isn't possible? It seems to me that we should remove the main thread guard page on Linux (as the kernel already has it anyway) and rely on #42816 to guarantee for sure we hit it. Does that sound right?

[jonas-schievink]

@alexcrichton Your conclusion seems correct, but I don't think Linux adds a guard page automatically (at least I couldn't see one with a quick test and didn't find documentation either). It's just pthreads that can add guard pages to threads.

However, the mechanism outlined by @infinity0 should result in the same outcome after stack probes land: Linux will simply refuse to grow the stack if it comes too close to another region in memory or if the stack limit is hit. These 2 conditions ensure that the stack stays in bounds and that there will always be an unmapped page below the stack, which will cause a segfault when hit, acting like the guard page (but actually getting hit, unlike the current guard page implementation).

[cuviper]

Right, Linux doesn't have a literal guard page mapping, but it enforces guard pages in effect.

I do think we need to stop adding our own guard page to the main thread. Even apart from the current issue, it worries me to have a blind mmap at an address that's probably not stack-mapped yet, and even could be mapped to something else entirely. We're shoving a PROT_NONE at an address based on rlimit-stack, but who knows if anything might already be there.

That just leaves us with the error reporting. #42816 will make sure we get a properly signaled fault, but we won't know how to report it as a stack overflow. I'm not sure how to distinguish this now...

[tavianator]

Presumably you can check if si_addr points directly below the stack mapping? This will detect failed stack probes anyway.

[cuviper]

Ok, but is there a better way to find that stack mapping than parsing /proc/self/maps?

I think it's OK if this only detects properly-strided stack probes. We're aborting in any case, so the stack overflow message is just a courtesy to help the user figure out why.

[tavianator]

Parsing /proc/self/maps was what I had in mind.

The other way would be if you knew the address of every stack probe instruction. Just check if uc_mcontext.gregs[REG_RIP] is in that set. Technically that's the only 100% precise way to detect a stack overflow -- you can always hit the guard page with a grossly out-of-bounds heap access too.

[cuviper]

Well, AIUI only growth greater than a page will invoke stack probing at all, so RIP could be anything -- that main-recursion I posted will just overflow on its own.

I think such parsing is OK, but it needs to be async-signal-safe. (e.g. no malloc!)

[aidanhs]

/proc may also not exist, e.g. if you're trying to run a statically linked binary inside a chroot.

[alexcrichton]

While parsing something in /proc can opportunistically allow us to give an error message @aidanhs is right in that we can't rely on it. I'm going to send a PR that just disables the "map an unmapped page at the end of the stack" on Linux and it seems we have no choice but to lose the error messages here for detection of stack overflow for now.

[alexcrichton]

Hm well so another option is that we could whitelist architectures with 4kb page sizes. That way on x86/x86_64 and maybe arm you'd at least get good error messages, and programs would be functional at all on powerpc64.

Just to make sure I understand, let's say we did this. We'd have to detect this by "any faulting address at most 1mb above the guard page" indicates a stack overflow, and we'd basically be subtracting 1mb from the default stack size on the system, right? Are there downsides to doing so?

[cuviper]

Maybe we can just note the address that we expect rlimit to start faulting, without literally mapping our own page there? Then we can still match something in the handler, but we won't trigger the extra padding heuristics. I think the "offset" will then be -1 as it will be able to use the full 8MB/whatever and only fault after that.

[cuviper]

Rather, offset=0 since we match the page below that saved address.

[alexcrichton]

Makes sense to me!

[cuviper]

I have it working without a guard page on x86_64; testing on ppc64 now.

[cuviper]

It works on ppc64 too! My fn main() { main() } fills the 8MB stack completely:

  0x3fffff800000     0x400000000000   0x800000        0x0 [stack]

and then aborts as desired with Rust's "stack overflow" message.

I'll open a PR soon...

[alexcrichton]

Awesome thanks @cuviper!

[tavianator]

@cuviper What about the ulimit -s unlimited case?

[cuviper]

@tavianator I think the unlimited case is already handled poorly, and the update will just mean we stop stuffing a guard page at a very distant address. Right now we start with something like this:

100000180000-100000380000 r-xp 00000000 fd:00 918327   /usr/lib64/power7/libc-2.24.so
100000380000-100000390000 r--p 001f0000 fd:00 918327   /usr/lib64/power7/libc-2.24.so
100000390000-1000003a0000 rw-p 00200000 fd:00 918327   /usr/lib64/power7/libc-2.24.so
1000003a0000-1000003b0000 ---p 00000000 00:00 0 
3ffffffd0000-400000000000 rw-p 00000000 00:00 0        [stack]

With the update, we'll stop mapping that 1000003a0000 guard page, but still remember that address for reporting "stack overflow". If the "unlimited" stack really does grow that far (almost 50TB!), it will fault rather than hitting libc, and we should indeed identify that as a stack overflow.

If something else got mapped anywhere in that space , then you'll overflow sooner, but we wouldn't have identified that with or without our guard page. I don't think you can without looking at the current mappings.

[tavianator]

@cuviper Makes sense, thanks!

[bwhacks]

This regression is likely to be fixed on the kernel side soon with some heuristic to allow for guard page mappings installed by user-space. However, I think any attempt by Rust or other language run-time to implement its own guard pages on the main thread stack is unlikely to do much good. Also, the size of the stack guard gap is currently (and will probably continue to be) configurable, so please don't make any assumptions about this.

[cuviper]

@bwhacks Pull #43072 will get rid of Rust's guard page entirely, so we'll just rely on the kernel guard.

[est31]

Could #43102 be caused by this bug?

[Zoxc]

The kernel is definitely doing something undesirable/stupid here.

Before removing our guard page on Linux, we also need to ensure that all kernel versions which Rust programs will not immediately crash on actually has an effective guard page.

[tavianator]

@Zoxc, @cuviper seems to have checked that in #43072.

[jrmuizel]

FWIW, we should probably skip adding our own guard on OS X too. Our current guard page is ending up in the middle of the main thread stack. See #43347.