gdb backtrace mechanism

Question

The mechanism that allows gdb to perform backtrace 1 is well explained.

• Starting from the current frame, look at the return address
• Look for a function whose code section contains that address.

Theoretically, there might be hundreds of thousands of functions to consider. I was wondering if there are any inherent limitations that prevent gdb from creating a lookup table with return address -> function name.

Answer 1

The mechanism that allows gdb to perform backtrace 1 is well explained.

This isn't at all how GDB performs a backtrace.

The address stored in the rip register points to the current instruction, and has nothing to do with return address.

The return address is stored on the stack, or possibly in another register. To find where it is stored (on x86_64, and assuming e.g. Linux/ELF/DWARF file format), GDB looks up unwind descriptor that covers the current value of RIP. The unwind descriptor also tells GDB how to restore other registers to the state they were just before the current function was called.

You can see unwind descriptors with e.g. readelf -wf a.out command.

Once GDB knows how to find return address and restore registers, it can effectively perform an up command, stepping from current (called) frame into previous (caller) frame.

Now this process repeats, until either GDB finds a special unwind descriptor which says "I am the last, don't try to unwind past me", or some error occurs (e.g. restored RIP is 0).

Notably, nowhere in this process does GDB have to consider thousands of functions.

Answer 2

What makes you think GDB does a straight search through all functions? This isn't what happens. GDB organises symbols into a couple of different data structures that allow for more efficient mapping between addresses and the enclosing function.

A good place to start might be here: https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;a=blob;f=gdb/blockframe.c;h=d9c28e0a0176a1d91fec1df089fdc4aa382e8672;hb=HEAD#l118