Register scanning approach is not reliable

[rptb1]

This is a simple manual import of Perforce job004158 so that it can be discussed with collaborators such as @waywardmonkeys .

Description

Filip Strömbäck @fstromback reports [1] that setjmp is not a reliable method of spilling registers onto the stack.

Analysis

The analysis we gave in design.mps.sol.setjmp.justify is not correct. A compiler can arrange for longjmp to reconstruct the registers using (for example) debug information, and so avoid the need to spill all the registers to the jump buffer.

How-found

customer

Introduced-in

Perforce changelist 194595 / Git commit 76166b7 / version 1.117.

Evidence

[1] https://info.ravenbrook.com/mail/2019/05/20/13-08-23/0/ (also below)

Test

none

History:

• 2019-06-04 GDR Created.

Created-by

@gareth-rees

Creation-date

2019/06/04 11:43:26

Modified-date

2019/06/04 11:43:26

[rptb1]

Here is the original report of the problem from @fstromback at 2019-05-20 14:08, reproduced with his kind permission.

Dear Ravenbrook team,

Thank you for your work with the MPS. I have used it in my language Storm (which I mentioned in a previous e-mail) successfully for quite a while now that I have properly debugged my format code.

I have recently been playing around a bit with implementing parts of a garbage collector myself in order to better understand how the MPS is working, and how I can tune it better in the future. I implemented some simple code for stack scanning (similar to the code attached to this e-mail) that works similar to how the MPS seems to be doing it, i.e. using setjmp to save the relevant registers to the stack and then scanning the entire stack. This works perfectly on Windows, however I noted some problems when I compiled the same code on Linux for x86_64 (currently Linux Mint 17.3 based on Ubuntu 14.04, but also on Ubuntu 18.04 using GCC 7.0.4 and 7.1.0):

When I compile the provided sample with -O3, the compiler does not use the rbp register for a frame pointer, but rather uses it to store local variables, in this case the variable "b". This is all fine and well, since rbp is a register preserved by the callee. However, rbp seems to be treated differently by "setjmp", at least on the systems I've tried so far. When stepping through the "setjmp" function in GDB, it seems like a mangled version of rbp is stored rather than the pointer itself. What I see closely resembles this implementation that seems to be used by glibc: https://github.molgen.mpg.de/git-mirror/glibc/blob/20003c49884422da7ffbc459cdeee768a6fee07b/sysdeps/x86_64/setjmp.S

I do believe this has something to do with stack smashing cookies or similar mechanisms, but I am not sure. The source code there also seems to be compilable in two modes: one with the mangling and one without it. Furthermore, I did not notice this behaviour when running on an Arch Linux system, possibly due to the stack checking being turned off there, or other configuration options. This issue is shown by the provided code. When executed, it outputs all values that would be scanned by an implementation similar to the MPS, and since it stores the values 1 to 6 on the stack, they should all appear in the output. However, as can be seen in the output below, the number 2 does not appear at any point in the stack. This is due to the compiler storing the value 2 in the rbp register, which is not stored in its plain form in the jmpbuf on the stack. This is the output I get on my system when compiling the attached file with gcc -O3 test.c:

0x7ffc2db8d4c0: 1
0x7ffc2db8d4c8: 15620895844699340101
0x7ffc2db8d4d0: 3
0x7ffc2db8d4d8: 4
0x7ffc2db8d4e0: 5
0x7ffc2db8d4e8: 6
0x7ffc2db8d4f0: 2823978450607013189
0x7ffc2db8d4f8: 15620896394385554757
0x7ffc2db8d500: 0
0x7ffc2db8d508: 139886594614824
0x7ffc2db8d510: 139882789863425
0x7ffc2db8d518: 0
0x7ffc2db8d520: 1
0x7ffc2db8d528: 139886594818504
0x7ffc2db8d530: 0
0x7ffc2db8d538: 139886580098995
0x7ffc2db8d540: 139886580109056
0x7ffc2db8d548: 72704
0x7ffc2db8d550: 0
0x7ffc2db8d558: 139886594819360
0x7ffc2db8d560: 140721075574160
0x7ffc2db8d568: 140721075574144
0x7ffc2db8d570: 4131212846
0x7ffc2db8d578: 4195230
0x7ffc2db8d580: 24641422
0x7ffc2db8d588: 17
0x7ffc2db8d590: 1
0x7ffc2db8d598: 4195997
0x7ffc2db8d5a0: 0
0x7ffc2db8d5a8: 0
0x7ffc2db8d5b0: 0
0x7ffc2db8d5b8: 4195598
0x7ffc2db8d5c0: 140721075574480
0x7ffc2db8d5c8: 0
0x7ffc2db8d5d0: 0
0x7ffc2db8d5d8: 4195591
0x7ffc2db8d5e0: 140721075574480
1 2 3 4 5 6

This does not currently appear to be an issue for the MPS, as the compiler seems to spill rbp to the stack before executing setjmp, even at high optimization levels. However, other implementations, such as the one used by libunwind: https://github.com/libunwind/libunwind/blob/master/src/setjmp/setjmp.c which may be used on some systems either now or in the future, only save the frame pointer and the instruction pointer in the jmpbuf structure, and compute the state of the preserved registers by information in the DWARF unwind tables. While this works well according to the setjmp/longjmp specification, it could break scanning in the MPS quite badly as most of the callee-preserved registers would not be scanned if such an implementation is used. I don't know if this implementation is used in many systems currently, or if it will be adapted. Libunwind is, however, used for unwinding regarding C++ exceptions on Linux currently, so it could theoretically be used as a default in the future or on some systems.

I don't know if you have found out this issue already and mitigated it in the MPS in some way (e.g. by making sure rbp is spilled), but I do not se anything obvious in the code or documentation that indicates this. Since this could cause incomplete scanning of the stack in the client program if the compiler decides not to spill rbp in some cases, I thought I would share my findings with you so you can decide if and how to migitate this potential issue. As I said earlier, I have not noticed any issues when using the MPS with Storm so far, so this is more of a warning of potential future issues when using a high level of compiler optimizations.

Thank you once again for your excellent work on the MPS, and have a good day!

With kind regards
Filip Strömbäck

Here is main.c mentioned in the message.

/**
 * Note: We're assuming we're executing under Unix and being compiled by GCC.
 */

#include <setjmp.h>
#include <stdlib.h>
#include <stdio.h>

#define NOINLINE __attribute__((noinline))

NOINLINE int create_value() {
	static int val = 1;
	return val++;
}

NOINLINE void scan_stack(size_t *cold) {
	jmp_buf buf;
	setjmp(buf);

	void *hot = &buf;
	for (size_t *at = (size_t *)hot; at < cold; at++)
		printf("%p: %lu\n", at, *at);
}

NOINLINE void test_scan(size_t *cold) {
	int a = create_value();
	int b = create_value();
	int c = create_value();
	int d = create_value();
	int e = create_value();
	int f = create_value();

	// printf("%d %d %d %d %d %d\n", a, b, c, d, e, f);
	scan_stack(cold);
	printf("%d %d %d %d %d %d\n", a, b, c, d, e, f);
}

int main() {
	size_t cold = 0;
	test_scan(&cold);
	return 0;
}

[rptb1]

At 2019-05-29, 15:41, @NickBarnes responded:

This is an excellent point which occurred to me when writing up all that zero-cost exception handling stuff, but I forgot to mention it. Basically setjmp ... longjmp is equivalent to try/finally ... throw, so in a "zero-cost" exception framework setjmp might not actually do anything explicit at all. I don't think there's any way around this except explicitly (and in a platform-dependent way) spilling the state we might need to scan.

[waywardmonkeys]

Laying out some preliminaries, some of which are essential and some are not.

There are 3 possible things that can be meant when saying setjmp / longjmp. These are:

• The compiler built-ins or primitives.
• Implementations of functions called setjmp and longjmp (and related functions) in libunwind.
• The implementation within the C library.

Compiler built-ins / primitives

These are in GCC as __builtin_setjmp and __builtin_longjmp. These are not actually compatible with the C library implementations and shouldn't typically be used unless you know exactly what you're doing: https://gcc.gnu.org/onlinedocs/gcc/Nonlocal-Gotos.html

THESE SHOULD NOT BE USED BY THE MPS.

libunwind implementations

These are actually in a separate library libunwind-setjmp which must be explicitly linked against. These do take advantage of DWARF unwind info so that setjmp can be faster, but the corresponding longjmp will be slower. This is for software that makes a lot of calls to setjmp, but makes many fewer calls to longjmp:

https://www.nongnu.org/libunwind/man/libunwind-setjmp(3).html

These are not portable across all targets (without adding an additional dependency) and aren't something that is slated for broader inclusion in the standard implementations.

THESE SHOULD NOT BE USED BY THE MPS.

C Library

This is the only one that we actually care about currently.

While this is the current solution, they have a variety of issues for the MPS:

• The behavior that is specified is different from what the MPS needs.
• They often do extra work. The extra work varies from platform to platform.
• Pointer "encryption" has rendered these increasingly unfit for the purpose required by the MPS.

Specification

This is documented at https://en.cppreference.com/w/c/program/setjmp which then indicates the actual sections from the various standards documents. setjmp is defined to save the calling environment or current execution context into a variable of type jmp_buf. As we'll see shortly, this lack of definition of the jmp_buf and how the data is encoded is what will cause problems.

Extra work

Some implementations of setjmp save the sigprocmask. This is more costly and not useful for the MPS. This is why _setjmp is to be preferred over setjmp, as the former explicitly does not save the sigprocmask. (And when you do want the mask to be saved, you should use sigsetjmp instead of setjmp to make it explicit and clear.)

Others save things like the floating point environment, such as FreeBSD:

https://github.com/freebsd/freebsd-src/blob/dc6df546be29a468ae21b1b7604e85b703ad6779/lib/libc/amd64/gen/_setjmp.S

It is worth noting that this is a historical artifact and a deviation from the relevant standards by FreeBSD. The standard explicitly says:

It does not include the state of the floating-point status flags, of open files, or of any other component of the abstract machine.

This FPU state is also saved on macOS:

https://github.com/apple/darwin-libplatform/blob/215b09856ab5765b7462a91be7076183076600df/src/setjmp/x86_64/_setjmp.s

Additionally, the extra work can vary from architecture to architecture. For example, on FreeBSD on 64 bit ARM, it may save the VFP registers as well (I don't know what `_STANDALONE means here or if it is enabled by default or not):

https://github.com/freebsd/freebsd-src/blob/dc6df546be29a468ae21b1b7604e85b703ad6779/lib/libc/aarch64/gen/_setjmp.S

Pointer Encryption

None of the above about the C library implementation actually matters.

As described here (from an OpenBSD frame of reference, but still relevant as it provides a background and summary of other platforms), some pointers are obfuscated when returned from system APIs to try to limit attack surface area:

https://isopenbsdsecu.re/mitigations/setjmp_longjmp/

This is also briefly described by Ulrich Drepper after he added some of this to the GNU libc implementation:

https://udrepper.livejournal.com/13393.html

And in the GNU libc wiki:

https://sourceware.org/glibc/wiki/PointerEncryption

Apple also does this within their setjmp implementation (linked above) using OS_PTR_MUNGE and similar calls, which are defined here:

https://github.com/apple/darwin-xnu/blob/2ff845c2e033bd0ff64b5b6aa6063a1f8f65aa32/libsyscall/os/tsd.h#L177-L209

In short, pointers are obfuscated on multiple platforms, but this has been evolving over time and across software versions. It is not reliable to assume that the jmp_buf will contain the actual pointer values that are stored in the registers.

THIS SHOULD no longer BE USED IN THE MPS.

Next Steps

The best option is probably going to be to write a custom macro that does the right thing on each platform in a platform-specific way.

This is not specific to Linux and FreeBSD. As we see above, macOS is also doing similar things with pointer encryption.

There is a pull request, #38, which starts down this path, but as we can see with things like the longjmp hardening in Microsoft Windows as part of pointer encryption, the exact implementation method used there would need to be examined.