1

And is there a way to easily monitor your stack depth in a linux environment?

Consider the case of a basic app in C, compiled with gcc, in Ubuntu.

How about if you do NOT allow dynamic memory allocation (no malloc/free-ing)?

tarabyte
  • 17,837
  • 15
  • 76
  • 117
  • Similar to http://stackoverflow.com/questions/1678803/how-to-determine-stack-size-of-a-program-in-linux. And dynamic memory allocation via `malloc` doesn't use stack space. It allocates from the heap. – lurker May 02 '14 at 16:24

2 Answers2

2

Can you know your max stack depth after you compile?

No. Consider a recursive function that might call itself any number of times, depending on input. You can't know how many times the function might be invoked, one inside the last, without knowing what the input to the program is.

I expect that it might be possible to determine the max stack depth for some programs, but you can't determine that for all programs.

And is there a way to easily monitor your stack depth in a linux environment?

I don't know about an easy way to monitor the stack depth continuously, but you can determine the stack depth at any point using gdb's -stack-info-depth command.

How about if you do NOT allow dynamic memory allocation (no malloc/free-ing)?

That doesn't make a difference. Consider a recursive Fibonacci function -- that wouldn't need to allocate any memory dynamically, but the number of stack frames will still vary depending on input.

Caleb
  • 124,013
  • 19
  • 183
  • 272
  • Dynamic memory allocation doesn't make a difference because it doesn't allocate memory from the stack. Nothing really to do with recursive functions. – lurker May 02 '14 at 16:26
  • What if you do NOT have any recursive calls in your program? Is that a sufficient restriction of a case to where you can know your max stack depth? – tarabyte May 02 '14 at 16:30
  • @lurker I agree. A recursive function is just a good example of why stack depth can't be determined at compile time. With just one function to think about, it's easy to see how the stack depth varies depending only on input. And `fib()` is a simple, widely understood example of such a function that doesn't allocate any memory dynamically. – Caleb May 02 '14 at 16:30
  • @Caleb yes, I see what you mean, and I agree. – lurker May 02 '14 at 16:33
  • 1
    @tarabyte Again, no. Consider two functions `a()` and `b()` where `a` calls `b` and `b` calls `a`. They're not *recursive*, exactly, but the stack depth still varies depending on conditions not known at compile time. Next, consider that instead of 2 functions in the group, there might be 30 or 40. You could only determine max stack depth if you can establish that there are *no* cycles in the call graph. – Caleb May 02 '14 at 16:33
  • @Caleb Your a() and b() case is not direct recursion - it is called indirect recursion. – Avi Berger May 02 '14 at 17:16
  • @AviBerger I've also heard it called "mutual recursion" (that's why I added the "exactly"). My point was simply that if you have a cycle in your call graph that involves maybe a dozen functions, or even more, it's not what most people think of as "recursive" code. – Caleb May 02 '14 at 17:24
0

It is possible to do a call-graph analysis. The longest path in the graph is the maximum stack depth. However, there are limitations.

With recursive functions, all bets are off, the depth of recursion depends on the run time input, it is not possible to deduce that in compile time analysis. [It is possible to detect the presence of recursive function by analyzing the call graph and looking for self edges, i.e. edges with same source and destination.]

Furthermore, the same issue is present if there are loops/cycles in the call graph. [As mentioned by @Caleb: a()->b()->c()->d()->e()->f()->g()->c()] [Using algorithms from graph theory, it is possible to detect the presence of cycles as well.]

References for call graph:

Community
  • 1
  • 1
Arun
  • 19,750
  • 10
  • 51
  • 60
  • 2
    It's not just recursive functions that make it impossible to determine stack depth, but *any* cycle in the call graph. That is, not just "self edges", but loops like `a()->b()->c()->d()->e()->f()->g()->c()`, need to be considered. – Caleb May 02 '14 at 16:38
  • @Caleb: Good point, thanks, I have updated the answer with your input. – Arun May 02 '14 at 16:45
  • So if call-graph analysis returns "no cycles", I can know the max stack depth? Fair enough restriction? – tarabyte May 02 '14 at 18:14
  • As long as you make no opaque lib calls or, on some OS, no system calls and ensure you are not interrupted, then maybe... – Martin James May 02 '14 at 18:19