DEV Community

Václav Hajšman
Václav Hajšman

Posted on

Moving forward on stack trace and symbols

#stacktrace #stack #debug #osdev

In the last post, we talked about stack, stack trace and symbols, and how to make use of these. I've mentioned that in future i would like to focus on replacing GCC __builtin_return_address() with frame-pointer unwinding and improving symbol lookup performance with binary search. So, lets begin.

What even is frame pointer unwinding

Frame pointer unwinding is a method which can be used to get backtrace (iterate through stack trace). It assumes that every function has stored the frame of previously called function using frame pointer (in our case ebp register, because we're on x86 - or for example rbp on x86_64, fp (aka x29) on AArch64, etc.).

This creates a linked list of frames, where each frame points to the one below it (i.e., the caller's frame). That allows us to traverse the call stack in a straightforward way — just by following the chain of saved frame pointers.

To prevent compiler from doing optimization, make sure to pass these as CFLAGS: -fno-omit-frame-pointer -fno-optimize-sibling-calls -mno-omit-leaf-frame-pointer. This ensures ebp is kept for each function, including the most optimized ones.

Implementing unwinder

On x86 architecture, the structure of stack frame looks like this

+-------------------+
| address on return | ← saved on `call`
+-------------------+
| previous `EBP`    | ← stored by function when start
+-------------------+ ← `EBP` points here
Enter fullscreen mode Exit fullscreen mode

So implementing the structure in C is not even much hard

typedef struct kernel_stack_frame {
    struct kernel_stack_frame* ebp;
    void* ret_addr;
} kernel_stack_frame_t;
Enter fullscreen mode Exit fullscreen mode

As long as the compiler doesn't optimize this away (using -fomit-frame-pointer), each function:

  1. saves previous value of ebp on stack,
  2. sets new value setting value of ebp to current value of esp - this creates the frame,
  3. when the function ends, ebp and esp restores to unwind back to the caller.

So now, lets actually code the unwinder.
First, you set frame pointer address from ebp

kernel_stack_frame_t* frame;
asm volatile("movl %%ebp, %0" : "=r" (frame));
Enter fullscreen mode Exit fullscreen mode

Then, you simply just iterate through these frames, copy current frame's return address and set frame to the next one

for(unsigned int i = 0; i < maxFrames; i++) {
    if(frame == NULL || frame->ebp == NULL)
        break;

    buffer[i] = frame->ret_addr;
    frame = frame->ebp;
}
Enter fullscreen mode Exit fullscreen mode

And yeah, that's all. The final function should look somehow like this. Easy, right?

void debug_captureStackTrace(void** buffer, unsigned int maxFrames) {
    if(maxFrames == 0 || buffer == NULL) {
        debug_message("debug_captureStackTrace(): invalid parameters", "debug", KERNEL_ERROR);
        return;
    }

    kernel_stack_frame_t* frame;

    // get EBP register value
    asm volatile("movl %%ebp, %0" : "=r" (frame));

    for(unsigned int i = 0; i < maxFrames; i++) {
        if(frame == NULL || frame->ebp == NULL)
            break;

        buffer[i] = frame->ret_addr;
        frame = frame->ebp;
    }
}
Enter fullscreen mode Exit fullscreen mode

Using in debug_dumpStackTrace()

Remember that ugly, goofy, switch based "iterator"? No more of that. In debug_dumpStackTrace(), capture the stack trace to the preallocated buffer and just dump the buffer instead.

void debug_dumpStackTrace(u8 depth, void (*_fn_print)(unsigned char*)) {
    // ...

    void* trace[depth];
    memset(trace, 0x00, sizeof(trace));

    debug_captureStackTrace(trace, depth);

    for(unsigned int i = 0; i < depth; i++) {
        void* addr = trace[i];
        if(!addr || (uintptr_t) addr < 0x10000)
            break;

        // ...
    }
}
Enter fullscreen mode Exit fullscreen mode

Now we can finally remove the get_return_address() function.

Future plans

  • Allow mapping source file + line using DWARF or ELF debug info

Top comments (3)

Collapse
 
nathan_tarbert profile image
Nathan Tarbert •

this is extremely impressive, been through these stack headaches myself and seeing it coded out like this actually helps me connect the dots
you think pushing this approach to DWARF mapping will hit any serious hurdles

Collapse
 
thatosdeveloper profile image
ThatOSDeveloper •

Hello I am curious on how you plan to implement function name resolving, since having to run addr2line every time is quite annoying to be frank, and I have to do the same (also and OS developer), are you going to try to parse ELF debug symbols or are you going to use a .map file and read it from an initramfs/filesystem? What is your plan on how to do it? Just curious to see what you think on doing it (since its been a problem plaguing me for WEEKS, and I have not yet found a single method yet that I can decide and stick with)

Collapse
 
vhajsman profile image
Václav Hajšman •

Hey there, thanks for your comment.

As mentioned in last post (which I recommend you reading if you haven't done so yet), where I have implemented stack traces and symbol lookup:

  • First, we link our kernel into temporary ELF binary so you can access all the function memory addresses
  • using nm and awk commands, we can generate a C source file with something like "a lookup table" of addresses and symbol names ({addr, name}) The output should like somehow like this: 
symbol_t kernel_symbols[] = {
    { 0x00100000, "__code" },
    { 0x00100000, "_code" },
    { 0x00100000, "code" },
    // ...
    { 0x00100000, "__kernel_text_section_start" },
    { 0x0011a000, "__kernel_text_section_end" },
    { 0x0011a000, "__x86.get_pc_thunk.bx" },
    // ...
};
size_t kernel_symbol_count = sizeof(kernel_symbols) / sizeof(kernel_symbols[0]);
Enter fullscreen mode Exit fullscreen mode
  • this table is then compiled to object file and kernel is linked again, but this time with the symbols table included.

Thanks to this, the kernel has symbols inside, so debug function can get function/symbol name just by looking up to the table and finding it by its address.

So instead of parsing ELF or shipping a .map file, i decided to generate a static lookup table at build time and compile it into the kernel. That way symbol resolution is fast, self-contained, and doesn’t depend on external tools at runtime.

Reading .map file from initial ramdisk?

I must say i actually like your idea, although i would not do that.

I understand this may have some benefits such as less build steps, some flexibility and smaller binary size. But there are also some reasons for not doing it that way:

  • a lot of things it would rely on - you would need to initialize initial ramdisk and filesystem APIs, read and mount the initrd image, then find the file headers, read the file, parse it and generate the lookup table. That is a lot of things that could possibly fail. If some of these fail and something in the kernel brokes or crashes, a lookup table will become unaccessible (because it simply does not exist), which can not only lead to debug information loss, but also an undefined behavior if these bugs are not handled correctly. You should always assume if something may fail, then it fails.

  • it's unnecessarily difficult - there is not much to talk about. It is always easier when the lookup table is already included in the kernel binary and not parsed while startup.

  • synchronization related issues - you would need to always make sure that the .map file actually is correct according to kernel binary contents. A little mismatch would result in debugging hell.

  • potential security risk - you possibly give potential hackers the addresses of kernel functions and also implement potentially unsafe parser directly to the kernel. Just like telling the thief where the money is instead of trying to get him out of the house.