4 ms·

How can you write a program that runs without at least some guaranteed stack size? Are you at fault if you program doesn't run in a 1kb stack? And how do you wo

How can you write a program that runs without at least some guaranteed stack size? Are you at fault if you program doesn't run in a 1kb stack? And how do you work out what stack size your program takes from looking at the source code? I guess make sure your required stack size is not a function of input, and test against a minimum stack size.

viraptor 5y ago
Unless you do alloca() or dynamically sized local arrays, you can measure your stack usage in the deepest call stack. Add some space in each frame for potential instrumentation and you have your minimum. Keep in mind that this is just for thread stacks - you can set the size for them yourself, so ideally you'd always do it. Then a guaranteed minimum size becomes irrelevant.
- chrisseaton 5y ago
  > Unless you do alloca() or dynamically sized local arrays, you can measure your stack usage in the deepest call stack. How does a normal working programmer calculate the size of each of their stack frames? I'm a compiler researcher and I'd struggle to do that. How are application developers going to do it? And how do you design a program to have a deterministic maximum call stack depth? I don't think these things are as easy as you're making out.
  - mjw1007 5y ago
    Not easy at all. I know that in the small-embedded world, people do work on such things. Eg https://github.com/japaric/cargo-call-stack https://github.com/japaric/cargo-call-stack
  - viraptor 5y ago
    You have 2 options: either your functions are recursive and you can hope and pray, or they're not and you can figure out which of your functions are the bottom of the call graph. In those leaf functions you can check &local_var and compare it to pthread_attr_getstack(pthread_getattr_np()). (Of course that's not precise for many reasons.) > And how do you design a program to have a deterministic maximum call stack depth? If you're running only your code - don't use recursion, or alloca. If you use external libraries, you have to research what they do and add some extra in case of updates. Bounded stack size is also a common issue if you're targeting small microprocessors. For non-critical apps it should be pretty easy to figure out the needed stack size. For cases when you want to guarantee it... that gets more tricky. Edit: just learned that clang has the option -fstack-usage which should help a lot.
    - CodesInChaos 5y ago
      Dynamic dispatch (e.g. function pointers/delegates, virtual methods) is another case that makes figuring out the call graph and thus the maximum stack size difficult (via whole-program data-flow analysis) to impossible (function pointers come from outside your codebase or are constructed in ways analysis can't handle).
    - creata 5y ago
      > You have 2 options: either your functions are recursive and you can hope and pray Or you can try to figure out the maximum number of times it'll recurse: for example, the height of a red-black tree with less than 2^64 nodes is less than 128, iirc.
      - lanstin 5y ago
        One rather quickly runs into halting-problem type issues, especially in the function dispatch method. Imagine a DSL that does stuff, and is implemented by function pointers in the parser/interpreter, and then the question becomes one of program inputs. In any case, having such a small limit is crazy, and defending it with references to correctness smells of Ulrich Drepper and the memmove issue. The whole "sucks less" movement is a little too focused on purity for my taste. The only time I'm sad when I look at my memory usage on my personal laptop is when I have unused memory. Please, pre-fetch some news.ycombinator, cache some more inodes for my next ncdu or find command; I have already paid for the memory, not using it is silly. Sure, we software engineers get lazy, but, except in AWS, use all your memory, all your processors upto throttling, all the time. Why not? I remember one day in the 90s counting out like max address len and max zip code len and so and trying to figure out how long to make my target stack allocated buffer, and i was like fuck it, I have more important things to do, all my stack buffers are hence forth 65536 bytes long.
  - MaxBarraclough 5y ago
    If we forbid things like recursion (including mutual recursion), function pointers, dynamic dispatch, and unbounded use of alloca, doesn't it then follow from the call graph and the per-function worst-case stack-usage numbers (which the compiler presumably knows)? Is that mistaken, or is the difficulty in generalising this approach to where those restrictions are lifted? I tried googling for how SPARK Ada provides assurances against exceeding stack-size limits, but I couldn't find a decent answer. I presume it does so, though. edit: forgot about alloca edit 2: Turns out the AdaCore folks have a tool specifically for static analysis of stack-space requirements of Ada/C/C++ code: https://www.adacore.com/gnatpro/toolsuite/gnatstack https://www.adacore.com/gnatpro/toolsuite/gnatstack
  - megous 5y ago
    You ask a compiler, since it knows the max stack requirements of every function it compiled, if it's fixed. If it's not fixed it may give you at least the minimum. For total depth, keeping you program simple and predictable helps. People certainly manage to do it even for large programs like Linux itself, where stack size is like 16KiB or so. https://elixir.bootlin.com/linux/v5.2/source/arch/x86/include/asm/page_64_types.h#L16 https://elixir.bootlin.com/linux/v5.2/source/arch/x86/includ... and less on other archs. 8 KiB on arm https://elixir.bootlin.com/linux/v5.13-rc7/source/arch/arm/include/asm/thread_info.h#L25 https://elixir.bootlin.com/linux/v5.13-rc7/source/arch/arm/i...
    - chrisseaton 5y ago
      But the compiler may not compile simple 'functions' as the user understands them - it may compile loop bodies, functions with other functions compiled in them, individual branches of functions, multiple versions of functions based on where they're called from... If I tell you as a compiler writer that this loop body from this function, but with this branch and this branch outlined, but only when called from this context, takes n bytes... I don't get what most working programmers are going to usefully do with that information.
      - megous 5y ago
        Where's the problem? Compiler will tell you what amount of stack a function will use, if it's inlined it may not tell you for that function, but it will tell you for the function the function was inlined to, which is what matters. If the language is complicated and has generics or whatever, the programmer will have to do more work to understand it. It's not a huge issue in C.
        chrisseaton 5y ago
        > Compiler will tell you what amount of stack a function will use If you ask a compiler how much stack a function will use the answer for a non-trivial compiler for a complicated language is always going to be 'it depends...'
- bsdetector 5y ago
  > Add some space in each frame for potential instrumentation and you have your minimum. On exit just scan from the maximum stack to minimum looking for non-zero. If you have tests it should be easy to get within a few bytes of max stack used, which is probably just as good as instrumenting everything.
  - viraptor 5y ago
    It's possible, but you need to watch out for some cases. For example let's say your furthest function declares char foo[4096], but uses only a few bytes of it in your testing. Your measurement will be 4k short.
    - bsdetector 5y ago
      It has to be a leaf function or there would be stack frames after, and no local variables after the array, and the function doesn't push anything onto the stack, and it has to be possible in ways not covered by tests to actually use that space. Sure, that could happen. But what the other guy was saying about being a compiler developer and being unsure how to calculate the maximum depth is that there are many, many ways to arrive at the wrong result. Resursion, argv/envp, varags, alloca, and so on. So unless you are going to spend a great deal of energy proving maximum depth you're going to be using an estimate of some sort. Thus, 'probably just as good'.
simias 5y ago
If you have to work in an environment where stack size is very limited (typically a few KiB) you have to pay attention to certain things that you can brush away in more generous environment. In particular you need to be very careful with recursive functions and you probably want to use the heap or static storage for any object bigger than a couple dozens bytes. But in my experience you don't really compute a "guaranteed" stack size, you use your experience and knowledge of the program to make an educated guess, and then you apply a reasonable multiplier to give you some security margin. If you don't use (or severely limit) recursive calls you can usually just check that your deepest call stack fits within the bounds. Although finding the deepest call stack in the first place can be tricky given that compilers can aggressively inline function calls.
saagarjha 5y ago
In general, you just can't. This means that any function call in C can bust the stack, unfortunately. You can try to use heuristics to try to avoid using up large amounts of space (avoid alloca and large stack arrays, be careful about recursion) but other than that there isn't much you can do.
sesuximo 5y ago
GCC has “-fstack-usage”

viraptor 5y ago

Unless you do alloca() or dynamically sized local arrays, you can measure your stack usage in the deepest call stack. Add some space in each frame for potential instrumentation and you have your minimum. Keep in mind that this is just for thread stacks - you can set the size for them yourself, so ideally you'd always do it. Then a guaranteed minimum size becomes irrelevant.

chrisseaton 5y ago
> Unless you do alloca() or dynamically sized local arrays, you can measure your stack usage in the deepest call stack. How does a normal working programmer calculate the size of each of their stack frames? I'm a compiler researcher and I'd struggle to do that. How are application developers going to do it? And how do you design a program to have a deterministic maximum call stack depth? I don't think these things are as easy as you're making out.
- mjw1007 5y ago
  Not easy at all. I know that in the small-embedded world, people do work on such things. Eg https://github.com/japaric/cargo-call-stack https://github.com/japaric/cargo-call-stack
- viraptor 5y ago
  You have 2 options: either your functions are recursive and you can hope and pray, or they're not and you can figure out which of your functions are the bottom of the call graph. In those leaf functions you can check &local_var and compare it to pthread_attr_getstack(pthread_getattr_np()). (Of course that's not precise for many reasons.) > And how do you design a program to have a deterministic maximum call stack depth? If you're running only your code - don't use recursion, or alloca. If you use external libraries, you have to research what they do and add some extra in case of updates. Bounded stack size is also a common issue if you're targeting small microprocessors. For non-critical apps it should be pretty easy to figure out the needed stack size. For cases when you want to guarantee it... that gets more tricky. Edit: just learned that clang has the option -fstack-usage which should help a lot.
  - CodesInChaos 5y ago
    Dynamic dispatch (e.g. function pointers/delegates, virtual methods) is another case that makes figuring out the call graph and thus the maximum stack size difficult (via whole-program data-flow analysis) to impossible (function pointers come from outside your codebase or are constructed in ways analysis can't handle).
  - creata 5y ago
    > You have 2 options: either your functions are recursive and you can hope and pray Or you can try to figure out the maximum number of times it'll recurse: for example, the height of a red-black tree with less than 2^64 nodes is less than 128, iirc.
    - lanstin 5y ago
      One rather quickly runs into halting-problem type issues, especially in the function dispatch method. Imagine a DSL that does stuff, and is implemented by function pointers in the parser/interpreter, and then the question becomes one of program inputs. In any case, having such a small limit is crazy, and defending it with references to correctness smells of Ulrich Drepper and the memmove issue. The whole "sucks less" movement is a little too focused on purity for my taste. The only time I'm sad when I look at my memory usage on my personal laptop is when I have unused memory. Please, pre-fetch some news.ycombinator, cache some more inodes for my next ncdu or find command; I have already paid for the memory, not using it is silly. Sure, we software engineers get lazy, but, except in AWS, use all your memory, all your processors upto throttling, all the time. Why not? I remember one day in the 90s counting out like max address len and max zip code len and so and trying to figure out how long to make my target stack allocated buffer, and i was like fuck it, I have more important things to do, all my stack buffers are hence forth 65536 bytes long.
- MaxBarraclough 5y ago
  If we forbid things like recursion (including mutual recursion), function pointers, dynamic dispatch, and unbounded use of alloca, doesn't it then follow from the call graph and the per-function worst-case stack-usage numbers (which the compiler presumably knows)? Is that mistaken, or is the difficulty in generalising this approach to where those restrictions are lifted? I tried googling for how SPARK Ada provides assurances against exceeding stack-size limits, but I couldn't find a decent answer. I presume it does so, though. edit: forgot about alloca edit 2: Turns out the AdaCore folks have a tool specifically for static analysis of stack-space requirements of Ada/C/C++ code: https://www.adacore.com/gnatpro/toolsuite/gnatstack https://www.adacore.com/gnatpro/toolsuite/gnatstack
- megous 5y ago
  You ask a compiler, since it knows the max stack requirements of every function it compiled, if it's fixed. If it's not fixed it may give you at least the minimum. For total depth, keeping you program simple and predictable helps. People certainly manage to do it even for large programs like Linux itself, where stack size is like 16KiB or so. https://elixir.bootlin.com/linux/v5.2/source/arch/x86/include/asm/page_64_types.h#L16 https://elixir.bootlin.com/linux/v5.2/source/arch/x86/includ... and less on other archs. 8 KiB on arm https://elixir.bootlin.com/linux/v5.13-rc7/source/arch/arm/include/asm/thread_info.h#L25 https://elixir.bootlin.com/linux/v5.13-rc7/source/arch/arm/i...
  - chrisseaton 5y ago
    But the compiler may not compile simple 'functions' as the user understands them - it may compile loop bodies, functions with other functions compiled in them, individual branches of functions, multiple versions of functions based on where they're called from... If I tell you as a compiler writer that this loop body from this function, but with this branch and this branch outlined, but only when called from this context, takes n bytes... I don't get what most working programmers are going to usefully do with that information.
    - megous 5y ago
      Where's the problem? Compiler will tell you what amount of stack a function will use, if it's inlined it may not tell you for that function, but it will tell you for the function the function was inlined to, which is what matters. If the language is complicated and has generics or whatever, the programmer will have to do more work to understand it. It's not a huge issue in C.
      - chrisseaton 5y ago
        > Compiler will tell you what amount of stack a function will use If you ask a compiler how much stack a function will use the answer for a non-trivial compiler for a complicated language is always going to be 'it depends...'
bsdetector 5y ago
> Add some space in each frame for potential instrumentation and you have your minimum. On exit just scan from the maximum stack to minimum looking for non-zero. If you have tests it should be easy to get within a few bytes of max stack used, which is probably just as good as instrumenting everything.
- viraptor 5y ago
  It's possible, but you need to watch out for some cases. For example let's say your furthest function declares char foo[4096], but uses only a few bytes of it in your testing. Your measurement will be 4k short.
  - bsdetector 5y ago
    It has to be a leaf function or there would be stack frames after, and no local variables after the array, and the function doesn't push anything onto the stack, and it has to be possible in ways not covered by tests to actually use that space. Sure, that could happen. But what the other guy was saying about being a compiler developer and being unsure how to calculate the maximum depth is that there are many, many ways to arrive at the wrong result. Resursion, argv/envp, varags, alloca, and so on. So unless you are going to spend a great deal of energy proving maximum depth you're going to be using an estimate of some sort. Thus, 'probably just as good'.

simias 5y ago

If you have to work in an environment where stack size is very limited (typically a few KiB) you have to pay attention to certain things that you can brush away in more generous environment. In particular you need to be very careful with recursive functions and you probably want to use the heap or static storage for any object bigger than a couple dozens bytes. But in my experience you don't really compute a "guaranteed" stack size, you use your experience and knowledge of the program to make an educated guess, and then you apply a reasonable multiplier to give you some security margin. If you don't use (or severely limit) recursive calls you can usually just check that your deepest call stack fits within the bounds. Although finding the deepest call stack in the first place can be tricky given that compilers can aggressively inline function calls.

saagarjha 5y ago

In general, you just can't. This means that any function call in C can bust the stack, unfortunately. You can try to use heuristics to try to avoid using up large amounts of space (avoid alloca and large stack arrays, be careful about recursion) but other than that there isn't much you can do.

sesuximo 5y ago

GCC has “-fstack-usage”