4 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. How do you do this

> 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
        > 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.
        5y ago
- deleted 5y ago
  [deleted]
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.

> 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
        > 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.
        5y ago
deleted 5y ago
[deleted]

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.