5 ms·

It's interesting that nobody has mentioned the fact that "stack" is a word that is not mentioned in the C standard (caveat: I don't own it. but I just checked i

by unwind 5y ago

It's interesting that nobody has mentioned the fact that "stack" is a word that is not mentioned in the C standard (caveat: I don't own it. but I just checked in a draft copy). In other words, there is no assumption/guarantee that a C compiler will rely on the machine stack in order to implement certain fetures (i.e. automatic variables, parameter passing, and function call/return). So I guess that means that an imaginary API to query these things should not talk about "stack", since that is making an assumption that is a bit out of line. That does not make naming any easier ... and, as pointed out by vasama, it would be hard to use an API that queries about the current function only. Perhaps something like "autosizeof f" where f is a function could return, at compile-time, the projected "automatic storage size" of the given function (perhaps making it into a compilation error if f() uses VLAs, or calls functions that do), and a runtime "autoleft()" function could be used to determine how much space is left. Uh, no, probably not. These things are hard, and I'm making assumptions about code analysis capabilities that are probably not realistic.

Joker_vD 5y ago
LLVM-MOS targets 6502 and so goes out of its way to use as few of the hardware stack as possible: it does global program optimization, figuring out what calls what, and what functions don't need to be reentrant so it could allocate as many of activation records as possible statically, FORTRAN-style.
silon42 5y ago
I can easily imagine compiler+linker being able to forbid recursion and statically calculate maximum stack needed. Probably you need to ban general function invocation via pointers... methods on objects could be fine, you just evaluate all virtual method override combinations.
- noneeeed 5y ago
  The SPARK Ada language prevents recursion by only allowing you to call methods that are defined above the method you are in. It has a similar rule to prevent recursive calls between packages although I forget the details of that. From this you can calculate the worst case stack size. As all other memory has to be statically allocated you can always caclculate the maximum memory footprint of any progam. Obviously those restrictions mean you have to write your code without recursion, but in practice the uses that SPARK is put to don't tend to need it. A statically allocated stack in your code and a loop can solve a lot of problems (along with suitable logic for gracefully handling that stack filling up).
cryptonector 5y ago
You ask for an automatic allocation of N bytes. You can use alloca() if you have that available, or VLAs if you have that available. If you have neither, then you still have to worry that fixed sized automatic allocations might be too large, but at least this can be checked statically. Given either alloca() or VLAs, those can be allocated on a stack or on a heap, and the spec does not say either way. The OS might over-commit memory, too, and if the C run-time has fixed-sized stacks there may or may not be a guard page at the end. However, even with all of that, using memcpy() or similar (see elsewhere in this thread) to touch every byte or every 4KB's worth of bytes in what might be the direction of stack growth (if there's a stack, otherwise the direction is irrelevant), is something you can do to make sure that the memory allocated is committed, and that any failure due to over-committing (bounded stacks look like over-committed unbounded stacks) is detected as early as possible and without corrupting memory (e.g., by wildly exceeding stack bounds). Failure may ensue, but it should be behavior defined by the machine rather than undefined behavior.
- alcover 5y ago
  > fixed sized automatic allocations [...] can be checked statically May I ask how you'd do this ? I need this for optimizing a C project.
  - cryptonector 5y ago
    Check every function's automatic variables' sizes, add them all up, and add whatever function call frame size the compiler and ABI are using. Getting an exact accounting of function call stack memory usage is tricky because you might have framepointer-less code, and you might have inlining of function calls, but you can figure it out assuming no inlining and assuming you don't enable framepointer-less-ness.
    - alcover 5y ago
      Thank you. It doesn't err.. look super straightforward. I was hoping for an automated way of some sort. This stack affair of `local arrays are super fast! but keep it small, 1024 should be okay` is very puzzling to aspiring C lovers like me.
b3morales 5y ago
Conversely, I don't think `malloc` et al. say anything about a "heap". All they promise is they'll allocate some memory, with certain size/alignment and lifetime guarantees. It's up to the platform to figure out how to fulfill those guarantees.
Ironlikebike 5y ago
The stack isn't in the C-standard, but it is often minimally defined in the psABIs (e.g., the ELF ABI on Linux) for the architecture. The psABI is generally trying to balance performance of addressability (on the architecture), with security (position-independence), while constraining the toolchain developers' implementation as little as possible. As a programmer you don't have to implement to the ABI, but if you want interoperability and you want to use a C language compiler, you should (good luck creating your own ABI otherwise). I'm not aware of any way to programmatically query the rules laid out in the psABI. The implementation of the corner cases is often based on mutual agreement (convention) between the compiler and the link-editor. You could probably write a tool that maintains a representation of these rules and returns the results in some sort of parse-friendly EBNF, but you'd need a convention linter to make sure that the implementation of your tool tracks the change in convention in the toolchain components. On-the-other hand, you could write an extension to the compiler that warns you when certain C code results in behaviors around the stack that might be undesirable, i.e., if you're passing too many parameters to a function and it's going to spill those to the stack. The standard way to avoid unknown behavior in this regard is to explicitly tell the compiler what you want to accomplish by not relying on auto-allocation or parameter passing rules (as stated in the top thread). This means explicit allocation on the heap, rather than than allowing the compiler to auto-allocate on the stack, and using pass-by-reference to avoid parameters spilling to the stack. All of this is slower since accessing values in the stack is often a single instruction operation (small number of cycles), vs multi-instruction loads from far-away addresses (large number of cycles).
pjc50 5y ago
Yeah, I've written C for the PIC16 which has a hardware stack .. of depth 8. https://electronics.stackexchange.com/questions/158307/is-there-stack-available-in-pic-isrs https://electronics.stackexchange.com/questions/158307/is-th... I'm not entirely sure it was a standards-compliant compiler though. I think it may have denied recursion? Mind you, I also think people have unreasonably high expectations of the C standard; in order to get things done you inevitably have to make compromises and use features that aren't available on every platform. Which leads to autoconf hell, but if you're still developing on C you've accepted its imperfections.

by unwind 5y ago

Joker_vD 5y ago

LLVM-MOS targets 6502 and so goes out of its way to use as few of the hardware stack as possible: it does global program optimization, figuring out what calls what, and what functions don't need to be reentrant so it could allocate as many of activation records as possible statically, FORTRAN-style.

silon42 5y ago

I can easily imagine compiler+linker being able to forbid recursion and statically calculate maximum stack needed. Probably you need to ban general function invocation via pointers... methods on objects could be fine, you just evaluate all virtual method override combinations.

noneeeed 5y ago
The SPARK Ada language prevents recursion by only allowing you to call methods that are defined above the method you are in. It has a similar rule to prevent recursive calls between packages although I forget the details of that. From this you can calculate the worst case stack size. As all other memory has to be statically allocated you can always caclculate the maximum memory footprint of any progam. Obviously those restrictions mean you have to write your code without recursion, but in practice the uses that SPARK is put to don't tend to need it. A statically allocated stack in your code and a loop can solve a lot of problems (along with suitable logic for gracefully handling that stack filling up).

cryptonector 5y ago

You ask for an automatic allocation of N bytes. You can use alloca() if you have that available, or VLAs if you have that available. If you have neither, then you still have to worry that fixed sized automatic allocations might be too large, but at least this can be checked statically. Given either alloca() or VLAs, those can be allocated on a stack or on a heap, and the spec does not say either way. The OS might over-commit memory, too, and if the C run-time has fixed-sized stacks there may or may not be a guard page at the end. However, even with all of that, using memcpy() or similar (see elsewhere in this thread) to touch every byte or every 4KB's worth of bytes in what might be the direction of stack growth (if there's a stack, otherwise the direction is irrelevant), is something you can do to make sure that the memory allocated is committed, and that any failure due to over-committing (bounded stacks look like over-committed unbounded stacks) is detected as early as possible and without corrupting memory (e.g., by wildly exceeding stack bounds). Failure may ensue, but it should be behavior defined by the machine rather than undefined behavior.

alcover 5y ago
> fixed sized automatic allocations [...] can be checked statically May I ask how you'd do this ? I need this for optimizing a C project.
- cryptonector 5y ago
  Check every function's automatic variables' sizes, add them all up, and add whatever function call frame size the compiler and ABI are using. Getting an exact accounting of function call stack memory usage is tricky because you might have framepointer-less code, and you might have inlining of function calls, but you can figure it out assuming no inlining and assuming you don't enable framepointer-less-ness.
  - alcover 5y ago
    Thank you. It doesn't err.. look super straightforward. I was hoping for an automated way of some sort. This stack affair of `local arrays are super fast! but keep it small, 1024 should be okay` is very puzzling to aspiring C lovers like me.

b3morales 5y ago

Conversely, I don't think `malloc` et al. say anything about a "heap". All they promise is they'll allocate some memory, with certain size/alignment and lifetime guarantees. It's up to the platform to figure out how to fulfill those guarantees.

Ironlikebike 5y ago

The stack isn't in the C-standard, but it is often minimally defined in the psABIs (e.g., the ELF ABI on Linux) for the architecture. The psABI is generally trying to balance performance of addressability (on the architecture), with security (position-independence), while constraining the toolchain developers' implementation as little as possible. As a programmer you don't have to implement to the ABI, but if you want interoperability and you want to use a C language compiler, you should (good luck creating your own ABI otherwise). I'm not aware of any way to programmatically query the rules laid out in the psABI. The implementation of the corner cases is often based on mutual agreement (convention) between the compiler and the link-editor. You could probably write a tool that maintains a representation of these rules and returns the results in some sort of parse-friendly EBNF, but you'd need a convention linter to make sure that the implementation of your tool tracks the change in convention in the toolchain components. On-the-other hand, you could write an extension to the compiler that warns you when certain C code results in behaviors around the stack that might be undesirable, i.e., if you're passing too many parameters to a function and it's going to spill those to the stack. The standard way to avoid unknown behavior in this regard is to explicitly tell the compiler what you want to accomplish by not relying on auto-allocation or parameter passing rules (as stated in the top thread). This means explicit allocation on the heap, rather than than allowing the compiler to auto-allocate on the stack, and using pass-by-reference to avoid parameters spilling to the stack. All of this is slower since accessing values in the stack is often a single instruction operation (small number of cycles), vs multi-instruction loads from far-away addresses (large number of cycles).

pjc50 5y ago

Yeah, I've written C for the PIC16 which has a hardware stack .. of depth 8. https://electronics.stackexchange.com/questions/158307/is-there-stack-available-in-pic-isrs https://electronics.stackexchange.com/questions/158307/is-th... I'm not entirely sure it was a standards-compliant compiler though. I think it may have denied recursion? Mind you, I also think people have unreasonably high expectations of the C standard; in order to get things done you inevitably have to make compromises and use features that aren't available on every platform. Which leads to autoconf hell, but if you're still developing on C you've accepted its imperfections.