Recently I interviewed with Intel, and I was asked this question
How would you measure the stack space without using the task manager, when an application is running on a computer? Write an algorithm if possible
I have no idea how to approach the question. I have even searched the internet but have not found any sort of related answer. So I am looking for help from the people of StackOverflow to help me understand the question and how to approach the solution.
First of all, I'd note that a great deal here relies on how C++ is most often implemented. What I'm going to describe will almost always work on any real implementation on an Intel x86, or anything remotely similar--but it'll probably break completely on something like an IBM mainframe or an early Cray (neither of which really supported a stack in hardware). For that matter, it's not really guaranteed to work on anything--but it will work about as expected on most current hardware (especially: just about anything with an Intel x86 processor).
A great deal here depends on whether we're trying to do this from inside the program, or from the outside (i.e., from another program).
If we're doing it from inside the program, we can start main with something like this:
char *stack_bottom;
int main() {
int a;
stack_bottom = &a;
This gives us an address at the bottom of the stack (well, technically, not quite the bottom, but really close to it anyway).
Then at any given point that we want to know the current stack depth, we can call a function something like this:
ptrdiff_t stack_size() {
char a;
return abs(stack_bottom - &a);
}
This creates a variable at the top of the stack, then subtracts the two to get the size. The stack usually grows downward in memory, so the "top" of the stack will typically be at a lower address than the top. Since we only care about the magnitude of the difference, we take the absolute value of the difference (though we can avoid that if we know which direction the stack grows).
Since this seems to be targeting Windows, we can use VirtualQuery to get similar information about stack memory.
From the "outside" of a program the basic idea is pretty much the same: find the bottom of the stack, find the top of the stack, subtract to find the size. But, chances are pretty good that we have to find the top and bottom a bit differently.
This tends to get into much more OS-specific territory though. For example, on Windows you'd probably use StackWalk64 to walk the stack and tell you the addresses of the top and bottom. On Linux, you'd typically use backtrace instead. On some other OS, chances are pretty good you'll use a function with some other name, producing data in some other format. But most will provide something on the same general order.
Once we have the addresses of the top and bottom of the stack, we're back to pretty much the same situation though: subtract the addresses of the top and bottom to find the size.
Another possibility would be to run the program under a debugger. Although we usually want to run the startup code before we do any debugging, in this case we can just load the program, and look at the ESP register to see where the stack is to start with. Then when we want to find the stack size we break, get the value in ESP and (of course) subtract to get the size.
If you want to get technical, what I've shown in the first won't be precisely the entire entire size of the stack. There's typically some startup routine that does things like retrieving environment variables and the command line, formatting them as expected, calling constructors of global objects, etc., that runs before main. So there's some small amount of space this won't capture. But what it misses is a small (and usually fixed) quantity, so usually we simply won't care about it. But if we really need to know the precise amount, we can (for one example) look at the source code to the startup to figure it out.
