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

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;

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));

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;
}

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;
    }
}

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;

        // ...
    }
}

Now we can finally remove the get_return_address() function.

Future plans

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