Writing a Linux Debugger Part 8: Stack unwinding
Sometimes the most important information you need to know about what your current program state is how it got there. This is typically provided with a
backtrace command, which gives you the chain of function calls which have lead to the the program is right now. This post will show you how to implement stack unwinding on x86_64 to generate such a backtrace.
- Registers and memory
- Elves and dwarves
- Source and signals
- Source-level stepping
- Source-level breakpoints
- Stack unwinding
- Handling variables
- Advanced topics
Take the following program as an example:
If the debugger is stopped at the
//stopped here line, there are two ways which it could have got there:
main->c->a. If we set a breakpoint there with LLDB, continue, and ask for a backtrace, then we get the following:
* frame #0: 0x00000000004004da a.out`a() + 4 at bt.cpp:3 frame #1: 0x00000000004004e6 a.out`b() + 9 at bt.cpp:6 frame #2: 0x00000000004004fe a.out`main + 9 at bt.cpp:14 frame #3: 0x00007ffff7a2e830 libc.so.6`__libc_start_main + 240 at libc-start.c:291 frame #4: 0x0000000000400409 a.out`_start + 41
This says that we are currently in function
a, which we got to from function
b, which we got to from
main and so on. Those final two frames are just how the compiler has bootstrapped the
The question now is how we implement this on x86_64. The most robust way to do this is to parse the
.eh_frame section of the ELF file and work out how to unwind the stack from there, but this is a pain. You could use
libunwind or something similar to do it for you, but that’s boring. Instead, we’ll assume that the compiler has laid out the stack in a certain way and we’ll just walk it manually. In order to do this, we first need to understand how the stack is laid out.
High | ... | +---------+ +24| Arg 1 | +---------+ +16| Arg 2 | +---------+ + 8| Return | +---------+ EBP+--> |Saved EBP| +---------+ - 8| Var 1 | +---------+ ESP+--> | Var 2 | +---------+ | ... | Low
As you can see, the frame pointer for the last stack frame is stored at the start of current stack frame, creating a linked list of frame pointers. The stack is unwound by following this linked list. We can find out which function the next frame in the list belongs to by looking up the return address in the DWARF info. Some compilers will omit tracking the frame base with the
EBP, since this can be represented as an offset from
ESP and it frees up an extra register. Passing
-fno-omit-frame-pointer to GCC or Clang should force it to follow the convention we’re relying on, even when optimisations are enabled.
We’ll do all our work in a
Something to decide early is what format to print out the frame information in. I used a little lambda to push this out the way:
The first frame to print out will be the one which is currently being executed. We can get the information for this frame by looking up the current program counter in the DWARF:
Next we need to get the frame pointer and return address for the current function. The frame pointer is stored in the
rbp register, and the return address is 8 bytes up the stack from the frame pointer.
Now we have all the information we need to unwind the stack. I’m just going to keep unwinding until the debugger hits
main, but you could also choose to stop when the frame pointer is
0x0, which will get you the functions which your implementation called before
main as well. We’ll to grab the frame pointer and return address from each frame and print out the information as we go.
That’s it! The whole function is here for your convenience:
Of course, we have to expose this command to the user.
Testing it out
A good way to test this functionality is by writing a test program with a bunch of small functions which call each other. Set a few breakpoints, jump around the code a bit, and make sure that your backtrace is accurate.
We’ve come a long way from a program which can merely spawn and attach to other programs. The penultimate post in this series will finish up the implementation of the debugger by supporting the reading and writing of variables. Until then you can find the code for this post here.
Let me know what you think of this article on twitter @TartanLlama or leave a comment below!