5 ms·

I just wrestled with this. You cannot effectively handle stack overflow situations if you use the system stack on Linux, because stack segments are in magical "

by titzer 5y ago

I just wrestled with this. You cannot effectively handle stack overflow situations if you use the system stack on Linux, because stack segments are in magical "MAP_GROWSDOWN" regions. These regions are managed by the kernel itself. There is a base address and a size, and the kernel initially only maps some small number of pages near the upper end (high addresses). Faulting accesses to addresses that are not mapped, but in the region, just below what is currently mapped cause the kernel to map in new pages automatically, "growing down". The customary way to handle stack overflow gracefully in userland is to install a SIGSEGV handler and check the faulting address to see if it is near the stack segment end, handling the signal on an alternate stack. Except that determining if the access was in the stack segment requires knowing the stack segment start. The signal API doesn't allow querying that; you'd have to query the process's mappings by other means. It's also not robust because a program with big frames might just stride too far and confuse the kernel's automatic growing, causing spurious SIGSEGVs when in fact, there is stack remaining. I found it was just easier to allocate my own stack segment and immediately switch to it and just leave the loader-provided stack segment alone. Virgil does this in the first 50 or so instructions upon entry. This also makes stack overflow very deterministic (only depends on the program) and controllable--there is a compiler option to set the stack size in KiB. There's no need for the compiler to insert strided accesses either, as the whole segment is mapped, and you can have more than a single guard page at the beginning (think: 1MiB guard region). Stack segments in C (and Linux) are madness if you use very much and want anything to be robust to overflow.

jeffbee 5y ago
Managing your own pthread stacks can make thread more costly though, can't it? Use of pthread_set_stack requires stack_size at least PTHREAD_STACK_MIN which on glibc linux tends to be 16384, four times larger than the initial cost of a demand-paged stack map. I understand that on musl this is 2048, so that's nice.
- titzer 5y ago
  Yeah, I think there would be some overhead, because it doesn't look like pthread_create allows specifying a stack segment. But I wouldn't be using pthread_create (or any C library for that matter), because Virgil goes all the way down to kernel; there is no C environment. I only experimented briefly[1] with getting Virgil threads to run on Linux. You need to call SYS_clone, which forks a lightweight process (i.e. shares all virtual memory), and specify a stack segment. The segment in question would of course, be mapped by Virgil and not have MAP_GROWSDOWN, so it could be made robust to stack overflow along the lines above. [1] https://github.com/titzer/virgil/blob/master/apps/Multi/Multi.v3 https://github.com/titzer/virgil/blob/master/apps/Multi/Mult...
whoisburbansky 5y ago
Tangent because this the first I’ve heard of Virgil. From the main README, what do you mean when you say you would like programs written in Virgil to be dependency-free?
- titzer 5y ago
  You can write programs that depend on no libraries at all, not even an SDK. They just need a compiler binary (and a machine to run that--x86-linux, x86-darwin, jvm, or even a Wasm engine) to compile, and compile to a binary that also only needs a machine to run--no shared objects, external jars, etc. The language has no builtin classes, interfaces, or functions. In contrast to say, Java, where the language (and compiler) know about java.lang.Object, java.lang.String, etc. The compiler knows how to compile classes, but it doesn't know the name of any built-in ones. Virgil is really designed to build the lowest level of software. Thus all my focus on low-level things like calling the kernel and mapping stacks, etc. The only thing that depends on more than just the kernel is the test suite, which uses bash and a little bit of C.
  - whoisburbansky 5y ago
    Ah, that's really cool. The clarification about it targeting the lowest level really helps explain the motivation, thanks, and all the best!
  - kragen 5y ago
    Interesting! Virgil looks really cool! I've been looking for something like it since about the time you started working on it, and I'm glad I've finally found it. For others reading this thread, to clarify the "no builtin functions" claim, although Virgil doesn't have any builtin values which refer to methods, it does have some built-in operations: ==, !=, +, -, *, /, %, <<, >>, >>>, &, |, and ^, as well as data structuring facilities like arrays and tuples and operations to access them.
matheusmoreira 5y ago
Nice to see you and the Virgil project again!! Really interesting to read about your Linux systems programming experiences. I learned a lot reading your source code but this bit about stacks escaped me. Also I see x86_64 Linux targets are supported now and that's awesome. Do you plan to support ARM architectures?
- titzer 5y ago
  Hey, thanks! I wrote about 1/3rd of an arm32 backend but it's languished because I've focused Virgil energy on only those things I need for my Wizard Engine project. Probably the next port I'll do will be arm64 to run on the M1 and Raspberry Pi, but that'll be some time in the future. Nice to hear someone has read the code. Glad you like it. Cheers :)
jeffffff 5y ago
i think maybe you can do it with userfaultfd, performance won't be as good as using a signal handler because of the context switch but you aren't restricted in what you can do in in the handler thread like you are with a signal handler.
stedolan 5y ago
The way to handle stack overflow gracefully on Linux is to check in your signal handler whether the faulting address was between the beginning of the stack and the current stack pointer. You can read the stack pointer register from the signal handler's third parameter. This is also how the kernel grows the stack. When there's a fault, it compares the faulting address to the stack pointer register. This way, big frames don't confuse the automatic growing. (On Windows, by contrast, stack growth is detected using a single 4k guard page, so compilers must be careful with big frames and insert strided accesses)
sydthrowaway 5y ago
What is Virgil?
- muthdra 5y ago
  https://github.com/titzer/virgil https://github.com/titzer/virgil I assume.

by titzer 5y ago

jeffbee 5y ago

Managing your own pthread stacks can make thread more costly though, can't it? Use of pthread_set_stack requires stack_size at least PTHREAD_STACK_MIN which on glibc linux tends to be 16384, four times larger than the initial cost of a demand-paged stack map. I understand that on musl this is 2048, so that's nice.

titzer 5y ago
Yeah, I think there would be some overhead, because it doesn't look like pthread_create allows specifying a stack segment. But I wouldn't be using pthread_create (or any C library for that matter), because Virgil goes all the way down to kernel; there is no C environment. I only experimented briefly[1] with getting Virgil threads to run on Linux. You need to call SYS_clone, which forks a lightweight process (i.e. shares all virtual memory), and specify a stack segment. The segment in question would of course, be mapped by Virgil and not have MAP_GROWSDOWN, so it could be made robust to stack overflow along the lines above. [1] https://github.com/titzer/virgil/blob/master/apps/Multi/Multi.v3 https://github.com/titzer/virgil/blob/master/apps/Multi/Mult...

whoisburbansky 5y ago

Tangent because this the first I’ve heard of Virgil. From the main README, what do you mean when you say you would like programs written in Virgil to be dependency-free?

titzer 5y ago
You can write programs that depend on no libraries at all, not even an SDK. They just need a compiler binary (and a machine to run that--x86-linux, x86-darwin, jvm, or even a Wasm engine) to compile, and compile to a binary that also only needs a machine to run--no shared objects, external jars, etc. The language has no builtin classes, interfaces, or functions. In contrast to say, Java, where the language (and compiler) know about java.lang.Object, java.lang.String, etc. The compiler knows how to compile classes, but it doesn't know the name of any built-in ones. Virgil is really designed to build the lowest level of software. Thus all my focus on low-level things like calling the kernel and mapping stacks, etc. The only thing that depends on more than just the kernel is the test suite, which uses bash and a little bit of C.
- whoisburbansky 5y ago
  Ah, that's really cool. The clarification about it targeting the lowest level really helps explain the motivation, thanks, and all the best!
- kragen 5y ago
  Interesting! Virgil looks really cool! I've been looking for something like it since about the time you started working on it, and I'm glad I've finally found it. For others reading this thread, to clarify the "no builtin functions" claim, although Virgil doesn't have any builtin values which refer to methods, it does have some built-in operations: ==, !=, +, -, *, /, %, <<, >>, >>>, &, |, and ^, as well as data structuring facilities like arrays and tuples and operations to access them.

matheusmoreira 5y ago

Nice to see you and the Virgil project again!! Really interesting to read about your Linux systems programming experiences. I learned a lot reading your source code but this bit about stacks escaped me. Also I see x86_64 Linux targets are supported now and that's awesome. Do you plan to support ARM architectures?

titzer 5y ago
Hey, thanks! I wrote about 1/3rd of an arm32 backend but it's languished because I've focused Virgil energy on only those things I need for my Wizard Engine project. Probably the next port I'll do will be arm64 to run on the M1 and Raspberry Pi, but that'll be some time in the future. Nice to hear someone has read the code. Glad you like it. Cheers :)

jeffffff 5y ago

i think maybe you can do it with userfaultfd, performance won't be as good as using a signal handler because of the context switch but you aren't restricted in what you can do in in the handler thread like you are with a signal handler.

stedolan 5y ago

The way to handle stack overflow gracefully on Linux is to check in your signal handler whether the faulting address was between the beginning of the stack and the current stack pointer. You can read the stack pointer register from the signal handler's third parameter. This is also how the kernel grows the stack. When there's a fault, it compares the faulting address to the stack pointer register. This way, big frames don't confuse the automatic growing. (On Windows, by contrast, stack growth is detected using a single 4k guard page, so compilers must be careful with big frames and insert strided accesses)

sydthrowaway 5y ago

What is Virgil?

muthdra 5y ago
https://github.com/titzer/virgil https://github.com/titzer/virgil I assume.