Is there a cheaper way to find the depth of the call stack than using backtrace()?

Question

My logging code uses the return value of backtrace() to determine the current stack depth (for pretty printing purposes), but I can see from profiling that this is a pretty expensive call.

I don't suppose there's a cheaper way of doing this? Note that I don't care about the frame addresses, just how many of them there are.

edit: These logging functions are used all over a large code-base, so manually tracking the stack depth isn't really an option.

Proconsulate

Answer 1

Walking the stack yourself is pretty quick - most of the slowness in backtrace() is from looking up symbol names. On x86, you can do the following:

inline uint32_t get_ebp(void)
{
    __asm__ __volatile__("mov %%ebp, %%eax");
}

int get_stack_depth(void)
{
    uint32_t ebp = get_ebp();
    int stack_depth = 0;
    while(ebp != 0)
    {
        ebp = *(uint32_t *)ebp;
        stack_depth++;
    }
    return stack_depth;
}

This will walk the chain of ebp pointers. Keep in mind that this is extremely non-portable. Also note that this will not count any functions which have been inlined or tail-call optimized (of course, backtrace() has the same problem).

Another important issue is the termination condition -- once you backtrace up to main(), there often aren't guarantees about what you'll find in the stack. So, if libc doesn't put a null frame pointer, you'll very likely segfault. You can get the termination value by looking at it at the very beginning of main().

Trigonometry

Answer 2

If your pretty-printing functions are reasonably contained, then pass in the indent (or indent size) as a parameter, and just increment it when you call other display functions.

Phelgon

If the idea of adding another parameter to your function scares you, you can also use a static variable. This is usually not a great idea, in my opinion. This would work the same way as Douglas's solution. – Lanctot

Answer 3

Can't you just carry a TLS variable around with you called "depth" and increment it / decrement it every function? While you could write your own code to walk the stack quicker, it's still going to be slower than just carrying the variable around with you.

Keynote

No, I think incrementing/decrementing a TLS variable every function call is going to be quite a lot more expensive, depending on how often you need to do a backtrace. – Trigonometry

He was doing a backtrace every call - there's no way that integer inc/dec is slower – Keynote

If anyone has the rep for a 1-character edit and is reading this, the linked URL now has an https version - please edit this answer and update it! – Havard

Answer 4

For arm architectures :

register unsigned long *rfp asm("fp");
unsigned long *fp = rfp;
unsigned long depth = 0;

while(fp)
{
    fp = (unsigned long *)(*(fp -3));
    depth++;
}

return depth;

Gusta