Hacker News Reader

> 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.

Excellent. Thanks for the tip. Some references:

https://docs.microsoft.com/en-us/windows/win32/devnotes/-win...

https://metricpanda.com/rival-fortress-update-45-dealing-wit...

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.

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.

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.

> 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.

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.

> 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?

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.

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.

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.

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.

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 *.

Wouldn't the compiler be allowed to elide the memory accesses that are being used to poke the memory region? If you are doing the poking before the memory has been initialized, then I'm not sure there are any guarantees that the compiler will read from the actual memory region (since it's uninitialized). And if you do writes to do the poking then there might be similar issues if the result of the write is never used. Even for reads you would have to make sure that the result gets used. Also not sure if casting to volatile is allowed if the object itself is not volatile. This is all true regardless of UB.

It seems to me like it is impossible to do poking in a way that could not be elided by the compiler, because removing poking never alters the semantics of the program (stack overflow or guard pages are not part of the semantics of C, I believe).

Of course, in practice you'll probably get the right behavior, but I'm personally always interested in language lawyery questions. I do believe that there are cases of security issues introduced by compilers eliding memset operations on password buffers, because the compiler can tell that the result of memset is never used and so it doesn't actually clear the memory. These sorts of things are tricky to get right.

Yes, you need to find a way to have the compiler not elide memset() or this particular function. That part is probably not portable.

You can cast to volatile, but casting away volatile-ness and dereferencing the resulting pointer is UB.

> That part is probably not portable.

If you need that part, and that part is not portable, then your solution is not portable is it!

This wouldn't work for exotic architectures like a Symbolics Lisp machine where pointers aren't numeric indices into memory. C has been kept loosey-goosey about platform requirements to avoid ruling out future architectural possibilities that haven't been anticipated yet. You can't assume anything about memory organization and still be truly portable.

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?

> So you're going to touch every byte of the memory, to check it's been successfully allocated.

Strictly less (not more than every 4KB), but, yes :)

> What happens when you access memory which has not been successfully allocated?

Portable C has finite size_t. Actual machines, virtual or otherwise, have finite resources. At some point you may run out of resources. With a dynamic stack allocation checker you'll fail with a segmentation fault when you run out. Without a dynamic stack allocation checker (but with dynamic stack allocations) you may well fail in random ways due to corruption of other stacks, heap, mmaps, etc.

If your C run-time doesn't have stacks then a dynamic stack allocation checker may be pointless... unless your OS is over-committing memory, then it may cause failure to happen sooner than it might otherwise.

> you'll fail with a segmentation fault

Who says you will?

Nothing in the C specification says that.

The C specs assume unlimited (up to size_t) resources.

Real life has no machines with 64-bit ISAs and 2^64 bytes' worth of resources.

Real life isn't portable. Who knew.

If there's no guard pages, no segmentation faults, no OOM killers, etc., then an allocation checker will cause failure in much the same kinds of undefined ways as not having the checker.

A segmentation fault is what you can expect in real systems, and it's absolutely better than undefined behavior.

You can do this portably, in C. It may not do you any good, and it may waste CPU cycles and memory bus usage. But it shouldn't harm. If the alternative is to not use alloca() or VLAs, and to make it so you can statically know your program's resource needs (which is very limiting, and not really attempted outside contexts where that such limitations are very strongly desired), then do that.

You're saying 'if run on a system that does things in a way I expect then it works' but the point of the article is 'but what about if you want to run on a system that's not as you expect and you want to run pure C'.

We all know what you're saying works in practice on most machines.

But it's not pure C and it's not portable if you follow the spec.

It's portably assuming that you can cast an allocation's pointer to a pointer to unsigned char. It's like assuming you can memset(), since that's effectively what it's doing. In the absence of memory over-commit, this will have no effect beyond wasting resources. In the presence of over-commit -bounded stacks resemble memory over-commitment!- it will have the effect of committing the memory OR failing in whatever way the machine fails when resources are exhausted. However, in the latter case, and when the machine uses stacks for C function calls, the failure will be defined by the machine rather than undefined (due to memory corruption).

Also, in the absence of stacks, there's no "direction in which the stack grows", and any attempt to determine that direction will yield a nonsensical result, but doing memset() in one direction or the other will also then be equivalent anyways.

EDIT: There is one non-portable thing here: the assumption that machines are more limited than size_t implies. However, that's a distinction without a difference for any 64-bit ABIs or larger because all such machines must be more limited than size_t implies. That there is any failure mode when resources are exhausted is a non-portable assumption is uselessly true. Not being able to assume defined resource exhaustion failure modes would be destructive -- that the C spec does not is irrelevant.

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.

This is undefined behavior.

See n1570.pdf, Annex J page 560, J.2 Undefined behavior

Pointers that do not point to the same aggregate or union (nor just beyond the same array object) are compared using relational operators (6.5.8).

Comparing the uintptr_t cast of two disparate pointers is not undefined behavior. A comparison may not yield a portable result because the integer representation of pointers may not be as plain memory addresses.

So such a simplistic stack growth detector may get the wrong answer, but it's not undefined behavior:

  char stack_grows_up(uintptr_t callers_local) {
    char my_local = (uintptr_t)&my_local > callers_local;
    return my_local;
  }

EDIT: Ah, and uintptr_t is an optional type. If the platform doesn't have it (e.g., because it's a segmented memory architecture) then this won't work, so it's not portable, but aside from that it's not undefined behavior, it's just that the computation of stack growth direction may well be wrong.

> A segmentation fault is what you can expect in real systems,

Nope. Just today I've seen a stack corruption bug that instead of producing a segmentation fault caused the process to go into uninterruptible sleep, somehow.

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.

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!

I was going to reply that alloca is a standard function, but then I checked and it's actually not is it!

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.

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.

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.

I'm not sure what your point is. You could replace the VLA with malloc in that example and exhaust your entire VM space.

In the rare cases where VLAs might prove useful, e.g. a vector math library (IIRC, a major reason for VLAs was to help FORTRAN programmers transition to C), this difference absolutely does matter in reality.

Maybe I missed the point of your comment. Mine is that the scoping difference between VLAs and alloca() isn't relevant to the question at hand of how to protect against memory corruption due to large stack allocations.

Notably, C11 moved alloca to an optional feature, not a required one.

> 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.

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.