How do I determine detailed call-stack information in C++?

2
votes

I’d like to understand the call-stack a bit better, and in an effort to do so, I’d like to work with it some more.

What will I do with this information? I have no idea! It’s fun to learn new things though, and this is my new thing for today.

I don’t like the call-stack in my programs being this mystical entity that I know nothing about. How big is it? How much memory is available on my current call-stack? Where is it? I don't know! And, I would like to know.

My current way to deal with the call-stack is to be aware of it, but to not knowingly interact with it until I hit a stack overflow error. That's just not good enough!

So in my quest, I’d like to figure out how to do the following:

  1. I'd like to know the total size of the current call-stack that I'm operating on.

  2. I'd like to calculate the total available memory available on my current call-stack.

  3. I’d like to be able to find the address of where my call-stack starts.

The declaration could look like this, and be filled in for various platforms:

class call_stack
{
    inline static void* base_address();
    inline static void* end_address();
    inline static std::size_t size();
    inline static std::size_t remaining();
};

How is stack information defined on current desktop and mobile platforms, and how can I access it? How can I code this at compile time, or determine it at runtime?

Looking into this reminds me of a talk that Herb Sutter gave about atomics. He said something along the lines of “as C++ programmers, we like to push the big red buttons that say don’t touch.”

I realize there are many questions about the call-stack, and I believe that mine is both meaningful and unique.

Other questions on the call-stack topic don't ask about the call-stack in a similarly broad manner to what I'm asking here.

4
c++memorycallstack
which operating system? - Richard Hodges
@RichardHodges Current desktop and mobile - Windows, OS X, Linux, iOS, Android. Maybe some more... - Michael Gazonda
The google terms you are looking for are "backtrace" and "stacktrace". there are already many examples of code to dump the stack trace to cout in stackoverflow. - Richard Hodges
That's a very broad scope for a SO question. - eerorika
@Richard Hodges, a backtrace is only a small part of what Michael is asking about. The backtrace only covers the return address for each function call in the stack. It doesn't include any of the information on the rest of the contents of the call frames or how large they are. - Russell Reed

4 Answers

1
votes

None of what you ask can be done in standard c++ since the stack is not specified in the standard.

You may be able to access that information by reading cpu registers in assembly language. How to do that depends on the cpu architecture, the OS and possibly the calling convention used by the compiler. Best place to find the information you're looking for is the manual for the architecture, OS, etc. The platfrom may also provide the information through system calls or virtual filesystems.

As an example, here's a quick look at the wikipedia page for the common x86 architecture

SP/ESP/RSP: Stack pointer for top address of the stack.

BP/EBP/RBP: Stack base pointer for holding the address of the current stack frame.

You can unwind the stack and find find the top of the stack in the first call frame. How to unwind the stack is again, specific to calling convention used. Subtracting the base of the first stack frame with the current stack pointer would give you the current size of the stack. Also remember that each thread has their own call stack so you must subtract from the bottom of the stack of the correct thread.

But keep in mind that:

Although the main registers (with the exception of the instruction pointer) are "general-purpose" in the 32-bit and 64-bit versions of the instruction set and can be used for anything...

You should check the manual of your target platform before assuming what the registers are used for.

Getting the remaining / total maximum stack space can be a bit trickier. In Linux the stack size is typically limited during runtime. The limit can be accessed through the /proc/ filesystem or using system calls. In Windows, the maximum stack size can be set at linktime and should be accessible in the executable file headers.

Below is an example program that works on Linux. I read the start of stack from /proc/<pid>/stat. I also provide an example for unwinding and for that I use a library that abstracts away all the OS / architecture specific assembly code. The stack is unwound all the way up to the initialization code before main and the stack space used by that is accounted for.

I use SP register instead of BP to get the bottom of the stack in the fisrt call frame because BP does not exist in some architectures and on my platform it was zero in the initialization frames. That means that the bottom is off by the size of the first call frame and is therefore just an approximation. See it on coliru, unfortunately access to /proc/<pid>/stat is denied there.

#include <iostream>
using namespace std;

#include <fstream>
#include <sstream>
#include <unistd.h>
// read bottom of stack from /proc/<pid>/stat
unsigned long bottom_of_stack() {
    unsigned long bottom = 0;
    ostringstream path;
    path << "/proc/" << getpid() << "/stat";
    ifstream stat(path.str());
    // possibly not the best way to parse /proc/pid/stat
    string ignore;
    if(stat.is_open()) {
        // startstack is the 28th field
        for(int i = 1; i < 28; i++)
            getline(stat, ignore, ' ');
        stat >> bottom;
    }
    return bottom;
}

#include <sys/resource.h>
rlim_t get_max_stack_size() {
    rlimit limits;
    getrlimit(RLIMIT_STACK, &limits);
    return limits.rlim_cur;
}

#define UNW_LOCAL_ONLY
#include <libunwind.h>

// using global variables for conciseness
unw_cursor_t frame_cursor;
unw_context_t unwind_context;

// approximate bottom of stack using SP register and unwinding
unw_word_t appr_bottom_of_stack() {
    unw_word_t bottom;
    unw_getcontext(&unwind_context);
    unw_init_local(&frame_cursor, &unwind_context);
    do {
        unw_get_reg(&frame_cursor, UNW_REG_SP, &bottom);
    } while(unw_step(&frame_cursor) > 0);
    return bottom;
}

// must not inline since that would change behaviour
unw_word_t __attribute__((noinline)) current_sp() {
    unw_word_t sp;
    unw_getcontext(&unwind_context);
    unw_init_local(&frame_cursor, &unwind_context);
    unw_step(&frame_cursor); // step to frame before this function
    unw_get_reg(&frame_cursor, UNW_REG_SP, &sp);
    return sp;
}

// a little helper for absolute delta of unsigned integers
#include <algorithm>
template<class UI>
UI abs_udelta(UI left, UI right) {
    return max(left,right) - min(left,right);
}

unsigned long global_bottom;
rlim_t global_max;

// a test function to grow the call stack
int recurse(int index) {
    if(index < 2 ) {
        auto stack_size = abs_udelta(current_sp(), global_bottom);
        cout << "Current stack size: " << stack_size
             << "\tStack left: " << global_max - stack_size << '\n';
        return index;
    }
    return recurse(index - 1) + recurse(index - 2); // do the fibonacci
}

int main() {
    global_max = get_max_stack_size();
    global_bottom = bottom_of_stack();
    auto appr_bottom = appr_bottom_of_stack();
    cout << "Maximum stack size: "
         << global_max << '\n';
    cout << "Approximate bottom of the stack by unwinding: "
         << (void*)appr_bottom << '\n';
    if(global_bottom > 0) {
        cout << "Bottom of the stack in /proc/<pid>/stat: "
             << (void*)global_bottom << '\n';
        cout << "Approximation error: "
             << abs_udelta(global_bottom, appr_bottom) << '\n';
    } else {
        global_bottom = appr_bottom;
        cout << "Could not parse /proc/<pid>/stat" << '\n';
    }
    // use the result so call won't get optimized out
    cout << "Result of recursion: " << recurse(6);
}

Output:

Maximum stack size: 8388608
Approximate bottom of the stack by unwinding: 0x7fff64570af8
Bottom of the stack in /proc/<pid>/stat: 0x7fff64570b00
Approximation error: 8
Current stack size: 640 Stack left: 8387968
Current stack size: 640 Stack left: 8387968
Current stack size: 576 Stack left: 8388032
Current stack size: 576 Stack left: 8388032
Current stack size: 576 Stack left: 8388032
Current stack size: 576 Stack left: 8388032
Current stack size: 576 Stack left: 8388032
Current stack size: 512 Stack left: 8388096
Current stack size: 576 Stack left: 8388032
Current stack size: 576 Stack left: 8388032
Current stack size: 512 Stack left: 8388096
Current stack size: 512 Stack left: 8388096
Current stack size: 512 Stack left: 8388096
Result of recursion: 8
0
votes

The Stack

In modern platforms, the stack structure is simplified to using a pointer to where the next item should be inserted. And most platforms use a register to do this. 

+---+  
|   |  
+---+  
|   |  
+---+  
|   |  
+---+  
|   |  <-- Next available stack slot
+---+

An item is written at the present location of the stack pointer, then the stack pointer is incremented.

The CALL Stack

The minimum that needs to be pushed onto the stack is the return address or address of next instruction after the call. This is about as common as you get. Anything else that is pushed onto the stack depends on the protocol set up by the compiler or operating system.

For example, the compiler my choose to place parameters into registers rather than pushing them onto the stack.

The order of the parameters depends ultimately on the compiler (and language). The compiler may push the leftmost value first or the last parameter first.

Stack Starting Address

The Stack Starting Address is usually determined by the operating systems, or on embedded systems, at a fixed location. There is no guarantee that the operating system will place your program's stack in the same location for every invocation.

Stack Size

There are two terms here: capacity and content. Stack size can refer to the number of elements in the stack (content) or the capacity that the stack can hold.

There is no fixed, common limit here. Platforms differ. Usually the OS is involved in allocating the capacity of the stack. And on many platforms, the OS doesn't check to see if you have exceeded the capacity.

Some Operating Systems provide mechanisms so that the executable can adjust the capacity of the stack. Most OS providers usually provide an average amount.

Sharing Memory with Heap

A common setup is to have the stack grow towards the heap. So all the extra memory for a process is allocated so that, for example, the stack grows from the beginning of the extra memory down and the heap allocates from the bottom up. This allows for programs that use little dynamic memory to have more stack space and those that use little stack space to have more dynamic memory. The big issue is when they cross. No notification, just undefined behavior.

Accessing Stack Information

Most of the time, I never look at the values of the stack pointer or register. This is usually on performance critical systems that have restricted memory capacities (like embedded systems).

The stack is usually reviewed by the debugger to provide a call trace.

0
votes

Here's a way to get a rough estimate of the size of the current call stack.

In main(), save the address of argc to a global variable. This is somewhat close to where your stack starts. Then when you want to check the current size, take the address of the first argument to your current function and subtract it from your saved value. This will be less accurate if you have a large amount of data in automatic variables in main() or the current function (I'm not sure which one - it may vary by platform).

There are probably cases where the stack grows dynamically by chaining blocks, in which case this technique will not be accurate.

In a multithreaded program, you would have to track the start of each thread's stack separately. Similarly to main, get the address of one of the parameters to the top-level thread function when the thread starts up.

I wish I had thought to save the link to the page where I found someone doing something similar. They got the address of one of the automatic variables instead of one of the parameters, which would still give a very similar result.