3 ms·

As long as there's a guard page and as long as you can assume that page is at least 4KB in size, you can detect C stack boundaries safely. Basically, don't use

As long as there's a guard page and as long as you can assume that page is at least 4KB in size, you can detect C stack boundaries safely. Basically, don't use alloca() or C99 VLAs, or huge automatics, or, if you do, touch a byte every 4KB in the direction of stack growth before you use bulky stack allocations. I have a macro for this somewhere. Also, this isn't limited to C... The real problem is not that the stack size is invisible to the program, or that you can run out. The real problem is that you can make a stack allocation so large that you might miss the end of the stack and scribble over some other memory. This is why you need to touch a byte ever guard-page-size bytes (in the direction of stack growth) in large stack allocations before using those allocations. What's specific to C is alloca() and C99 VLAs. Not that other languages don't have those, but that in their absence it's extremely unlikely that any function would have a frame so large as to run past the guard page. A maximum frame size can be computed by the compiler in the absence of alloca() or VLAs. Also, the compiler could (and arguably should) generate code to do this touching of a byte every guard-size-bytes thing for dynamically sized stack allocations, which would make the problem disappear. (You could still run out of stack space, but more safely.)

chrisseaton 5y ago
> As long as there's a guard page and as long as you can assume that page is at least 4KB in size, you can detect C stack boundaries safely. How do you do this in pure C?
- cryptonector 5y ago
  You're gonna make me dig it out, ain't ya. I don't know where I put it, but I've written a macro and function that does this. Basically, given a pointer and allocation size, if it's smaller than 4KB, do nothing, if it's larger, loop for allocation size div 4KB touching a byte from one end of the allocation to the other. The tricky things are: determining in which direction the stack grows, and the page size (which, arguably, you can hard-code to 4KB) if you really don't want to hard-code 4KB. You can determine stack growth direction by having one function call another with a pointer to a local variable in the former and then compare that to a pointer to a local variable in the latter. To do this correctly you have to cast to uintptr_t. And, yes, pure C does not even assume a stack, much less a bounded stack. In pure C it's possible to have every call frame allocated on the heap, which means that assuming that they are allocated contiguously is not safe. Moreover, even with stacks, the run-time could allocate a second stack when the first is exhausted and push new call frames on the second rather than die. In pure C the only assumptions about limits have to do with the size of size_t. The real world intrudes though, and in practice all C run-times allocate call frames on bounded stacks.
  - chrisseaton 5y ago
    None of this is possible in a well-defined pure C program. Pages with special memory protection aren't a thing C knows anything about. That's the point - you can't do it without sacrificing portability.
    - cryptonector 5y ago
      What I'm describing is portable. It may be unnecessary in C run-times that allocate call frames on the heap, but those aren't realistic C run-times.
      - chrisseaton 5y ago
        Say I ran your code on a special C implementation that tracks all memory access and disallows it when you try to read from stack memory that doesn't contain a live object. That'd be a completely standards-compliant C implementation. Your code wouldn't run on it. Your code would not be portable to my standards-complaint implementation. Therefore your code is not portable.
        cryptonector 5y ago
        You can almost certainly make it portable. After all, the allocation has a pointer, size, and type, and if it is at all an array, you could dereference every Nth element as needed, possibly with memcpy(), and avoid aliasing rules via casting to unsigned char *.
        chrisseaton 5y ago
        So you're going to touch every byte of the memory, to check it's been successfully allocated. What happens when you access memory which has not been successfully allocated?
        cryptonector 5y ago
- shadowgovt 5y ago
  In pure C, there is no stack abstraction. Technically speaking, the stack is an extremely common implementation detail shared by almost all C runtimes. There's no real way to answer this question at that layer of abstraction; the minute you add any library calls that deal with a stack at all (such as alloca), we're no longer talking about pure C.
  - cryptonector 5y ago
    Correct. Note that alloca() can be an alias for malloc() in stackless Cs. If the stack assumption is invalid, then a checker will not trip over a guard page, and it will at best trip over memory over-commit (which may still be desirable). If the guard page assumption is invalid, then a checker will cause failure just as surely as not checking (provided you intended to use the whole allocation anyways), and either way the failure will be undefined, therefore this is still portable C!
  - chrisseaton 5y ago
    I was going to reply that alloca is a standard function, but then I checked and it's actually not is it!
    - cryptonector 5y ago
      However VLAs are in C99 and up. They're rather similar to alloca() in that whatever mechanism you'd use to implement alloca() (automatic stack allocation, or heap allocation), you'd also use to implement VLAs.
      - wahern 5y ago
        Except alloca'd space is only dropped at the end of a function. VLAs are dropped at the end of a block. This makes a huge difference in loops as alloca can quickly exhaust the stack.
        cryptonector 5y ago
        No real difference: for (size_t i = 1; i < WHATEVER; i <<= 1) { char vla[i]; vla[0] = 0; vla[i - 1] = 0; ... } that is, you can still exhaust your stack trivially with VLAs. Sure, the two things have a different "API", but as far as allocating arbitrary amounts of memory goes, they both let you do it.
Joker_vD 5y ago
> touch a byte every 4KB in the direction of stack growth before you use bulky stack allocations. I have a macro for this somewhere. > you need to touch a byte ever guard-page-size bytes (in the direction of stack growth) in large stack allocations before using those allocations > Also, the compiler could (and arguably should) generate code to do this touching of a byte every guard-size-bytes thing for dynamically sized stack allocations, which would make the problem disappear. That's precisely what MSVC does since 1995 or so: inserting the calls to the _chkstk() function that touches the guard pages. I believe gcc also does this when it targets Windows.
- cryptonector 5y ago
  Excellent. Thanks for the tip. Some references: https://docs.microsoft.com/en-us/windows/win32/devnotes/-win32-chkstk https://docs.microsoft.com/en-us/windows/win32/devnotes/-win... https://metricpanda.com/rival-fortress-update-45-dealing-with-__chkstk-__chkstk_ms-when-cross-compiling-for-windows/ https://metricpanda.com/rival-fortress-update-45-dealing-wit...
titzer 5y ago
This doesn't work in practice, see my above comment. You can't put guard pages into the middle of stack segment (using mprotect()--the kernel will just override that mapping, happily growing right over top of it). Even putting a guard page at the end doesn't work, as you can still have spurious SIGSEGVs, as you mention, because programs might just stride more than 4KiB at a time; you can't trust a C compiler to insert strided accesses for you, and that's just overhead. The only way you can reliably do this, I've found, is to allocate your own stack segment.
- cryptonector 5y ago
  Of course you can have a SIGSEGV when you exceed the max stack size. That's fine and to be expected. What's NOT fine is for a large stack allocation to cause the program to silently scribble over another stack or heap.
  - masklinn 5y ago
    > Of course you can have a SIGSEGV when you exceed the max stack size. That's fine and to be expected. It's more that you can't expect anything better, having an actual stack overflow error would be a lot more helpful.
    - cryptonector 5y ago
      Right. With 64-bit ISAs you can address 2^64 bytes, but... you can't exactly have 2^64 bytes. At some point the system will fail. How it fails is important. A ran-out-of-resources errors is a lot better than undefined behavior resulting from random memory corruption. And yes, portable C has finite size_t. Therefore portable C must fail in some way when limits are exceeded.
- gpderetta 5y ago
  Have you considered --split-stack? It provides infinitely growable stacks (up to the heap limit I guess) and a defined ABI to find the stack boundaries. The cost is slower function calls and an ABI break.
Someone 5y ago
> touch a byte every 4KB in the direction of stack growth before you use bulky stack allocations I don’t think you can portably (1) do that. You have to allocate before you can touch those bytes. Also, if you do before, I don’t think there’s a guarantee that you won’t hit some volatile memory that interacts with hardware, and of course, there’s no portable way to get the stack pointer, in the first place (if only because it, conceptually, doesn’t exist in C) (1) specific compilers can safely do that because they know how they are implemented, and many compilers are fairly similar, so one can make this “quite portable”, but not really portable.
- cryptonector 5y ago
  One way is to allocate first. alloca(1GB) typically isn't going to cause a SEGV, so you can check the allocation after making it. With VLAs you have to make sure (this is not portable) that the compiler will put your loop iterator state variables ahead of the VLA. If you can assume a linear stack (which is kinda the whole point of this discussion) then you can call a function that will repeatedly alloca() in small chunks and touch a byte and return on success or SEGV on failure, and then when it returns it will release that memory but then you know you can safely alloca() that much.

chrisseaton 5y ago

> As long as there's a guard page and as long as you can assume that page is at least 4KB in size, you can detect C stack boundaries safely. How do you do this in pure C?

cryptonector 5y ago
You're gonna make me dig it out, ain't ya. I don't know where I put it, but I've written a macro and function that does this. Basically, given a pointer and allocation size, if it's smaller than 4KB, do nothing, if it's larger, loop for allocation size div 4KB touching a byte from one end of the allocation to the other. The tricky things are: determining in which direction the stack grows, and the page size (which, arguably, you can hard-code to 4KB) if you really don't want to hard-code 4KB. You can determine stack growth direction by having one function call another with a pointer to a local variable in the former and then compare that to a pointer to a local variable in the latter. To do this correctly you have to cast to uintptr_t. And, yes, pure C does not even assume a stack, much less a bounded stack. In pure C it's possible to have every call frame allocated on the heap, which means that assuming that they are allocated contiguously is not safe. Moreover, even with stacks, the run-time could allocate a second stack when the first is exhausted and push new call frames on the second rather than die. In pure C the only assumptions about limits have to do with the size of size_t. The real world intrudes though, and in practice all C run-times allocate call frames on bounded stacks.
- chrisseaton 5y ago
  None of this is possible in a well-defined pure C program. Pages with special memory protection aren't a thing C knows anything about. That's the point - you can't do it without sacrificing portability.
  - cryptonector 5y ago
    What I'm describing is portable. It may be unnecessary in C run-times that allocate call frames on the heap, but those aren't realistic C run-times.
    - chrisseaton 5y ago
      Say I ran your code on a special C implementation that tracks all memory access and disallows it when you try to read from stack memory that doesn't contain a live object. That'd be a completely standards-compliant C implementation. Your code wouldn't run on it. Your code would not be portable to my standards-complaint implementation. Therefore your code is not portable.
      - cryptonector 5y ago
        You can almost certainly make it portable. After all, the allocation has a pointer, size, and type, and if it is at all an array, you could dereference every Nth element as needed, possibly with memcpy(), and avoid aliasing rules via casting to unsigned char *.
        chrisseaton 5y ago
        So you're going to touch every byte of the memory, to check it's been successfully allocated. What happens when you access memory which has not been successfully allocated?
        cryptonector 5y ago
shadowgovt 5y ago
In pure C, there is no stack abstraction. Technically speaking, the stack is an extremely common implementation detail shared by almost all C runtimes. There's no real way to answer this question at that layer of abstraction; the minute you add any library calls that deal with a stack at all (such as alloca), we're no longer talking about pure C.
- cryptonector 5y ago
  Correct. Note that alloca() can be an alias for malloc() in stackless Cs. If the stack assumption is invalid, then a checker will not trip over a guard page, and it will at best trip over memory over-commit (which may still be desirable). If the guard page assumption is invalid, then a checker will cause failure just as surely as not checking (provided you intended to use the whole allocation anyways), and either way the failure will be undefined, therefore this is still portable C!
- chrisseaton 5y ago
  I was going to reply that alloca is a standard function, but then I checked and it's actually not is it!
  - cryptonector 5y ago
    However VLAs are in C99 and up. They're rather similar to alloca() in that whatever mechanism you'd use to implement alloca() (automatic stack allocation, or heap allocation), you'd also use to implement VLAs.
    - wahern 5y ago
      Except alloca'd space is only dropped at the end of a function. VLAs are dropped at the end of a block. This makes a huge difference in loops as alloca can quickly exhaust the stack.
      - cryptonector 5y ago
        No real difference: for (size_t i = 1; i < WHATEVER; i <<= 1) { char vla[i]; vla[0] = 0; vla[i - 1] = 0; ... } that is, you can still exhaust your stack trivially with VLAs. Sure, the two things have a different "API", but as far as allocating arbitrary amounts of memory goes, they both let you do it.

Joker_vD 5y ago

> touch a byte every 4KB in the direction of stack growth before you use bulky stack allocations. I have a macro for this somewhere. > you need to touch a byte ever guard-page-size bytes (in the direction of stack growth) in large stack allocations before using those allocations > Also, the compiler could (and arguably should) generate code to do this touching of a byte every guard-size-bytes thing for dynamically sized stack allocations, which would make the problem disappear. That's precisely what MSVC does since 1995 or so: inserting the calls to the _chkstk() function that touches the guard pages. I believe gcc also does this when it targets Windows.

cryptonector 5y ago
Excellent. Thanks for the tip. Some references: https://docs.microsoft.com/en-us/windows/win32/devnotes/-win32-chkstk https://docs.microsoft.com/en-us/windows/win32/devnotes/-win... https://metricpanda.com/rival-fortress-update-45-dealing-with-__chkstk-__chkstk_ms-when-cross-compiling-for-windows/ https://metricpanda.com/rival-fortress-update-45-dealing-wit...

titzer 5y ago

This doesn't work in practice, see my above comment. You can't put guard pages into the middle of stack segment (using mprotect()--the kernel will just override that mapping, happily growing right over top of it). Even putting a guard page at the end doesn't work, as you can still have spurious SIGSEGVs, as you mention, because programs might just stride more than 4KiB at a time; you can't trust a C compiler to insert strided accesses for you, and that's just overhead. The only way you can reliably do this, I've found, is to allocate your own stack segment.

cryptonector 5y ago
Of course you can have a SIGSEGV when you exceed the max stack size. That's fine and to be expected. What's NOT fine is for a large stack allocation to cause the program to silently scribble over another stack or heap.
- masklinn 5y ago
  > Of course you can have a SIGSEGV when you exceed the max stack size. That's fine and to be expected. It's more that you can't expect anything better, having an actual stack overflow error would be a lot more helpful.
  - cryptonector 5y ago
    Right. With 64-bit ISAs you can address 2^64 bytes, but... you can't exactly have 2^64 bytes. At some point the system will fail. How it fails is important. A ran-out-of-resources errors is a lot better than undefined behavior resulting from random memory corruption. And yes, portable C has finite size_t. Therefore portable C must fail in some way when limits are exceeded.
gpderetta 5y ago
Have you considered --split-stack? It provides infinitely growable stacks (up to the heap limit I guess) and a defined ABI to find the stack boundaries. The cost is slower function calls and an ABI break.

Someone 5y ago

> touch a byte every 4KB in the direction of stack growth before you use bulky stack allocations I don’t think you can portably (1) do that. You have to allocate before you can touch those bytes. Also, if you do before, I don’t think there’s a guarantee that you won’t hit some volatile memory that interacts with hardware, and of course, there’s no portable way to get the stack pointer, in the first place (if only because it, conceptually, doesn’t exist in C) (1) specific compilers can safely do that because they know how they are implemented, and many compilers are fairly similar, so one can make this “quite portable”, but not really portable.

cryptonector 5y ago
One way is to allocate first. alloca(1GB) typically isn't going to cause a SEGV, so you can check the allocation after making it. With VLAs you have to make sure (this is not portable) that the compiler will put your loop iterator state variables ahead of the VLA. If you can assume a linear stack (which is kinda the whole point of this discussion) then you can call a function that will repeatedly alloca() in small chunks and touch a byte and return on success or SEGV on failure, and then when it returns it will release that memory but then you know you can safely alloca() that much.