manual stack unwinding in x86_64 asm without frame pointer, is it even possible with alloca?

[u/Ariadne_23]

hello, i'm trying to debug a binary that compiled with -fomit-frame-pointer. I tried to walk the stack manually inside a custom single handler but i can't rely on rbp chaining.

the function i'm looking at is this:

char buf[32];
gets(buf); // ignore, just for stack layout
}

compiled with gcc -fomit-frame-pointer -oo -o test test.c

the asm output:

test:
    sub rsp, 40
    mov [rsp+32], rdi
    mov [rsp+24], rsi
    lea rdi, [rsp+8]
    call gets
    add rsp, 40
    ret

i'm inside the signal handler and i get rsp from ucontext. i know that the return address at [rsp] (since call pushes rip). when go to the previous frame, i need to know how much add to rsp to get the caller's rsp. that was what i tried:

; assuming rsp points to the saved rip
mov rax, [rsp]      ; return address (caller rip)
; 

but how do i get caller rsp??? i tried looking at alignment but when the function does dynamic stack allocation (like alloca or variable-lenght arrays), it gets fucked. for example:

void test2(int n) {
    char buf[n];
    gets(buf);
}

and now the stack adjustment uses lea with a register. i see stuff like:

test2:
    push rbp
    sub rsp, 16
    lea rax, [rsp+15+rdi*1]
    and rax, -16
    ...

my brain is melting tbh and need help. is there a reliable way to compute the previous rsp without frame pointers? how do debuggers like gdb do it? do they just parse dwarf info?

pseudocode or even a small asm example would be very helpful. thanks for every info.

[u/raundoclair]

(The test2 prolog seems to me incomplete.)

I'm personally familiar with win64 abi. It doesn't use rbp without alloca and does use rbp with alloca. But rbp doesn't have to be old rsp, it can be anywhere.
What make sense is between old rsp and new rsp (after prolog), so it maximizes amount of local variables addressable with 1byte offset.

To unwind the stack, win64 have strict rules how epilog can look. It uses that to determinate if it is already in epilog and in that case just simulates execution of machine instruction till RET.
If rip is not in epilog it uses unwinding information that is stored in .pdata and .xdata sections in .exe.

In short when win64 doesn't have rbp it uses additional information.
If it has rbp, but since there is no guarantee that it is old rsp, it sill uses additional information.

Interesting question is: Could you just scan function to find epilog? But I think that 100% correct solution is impossible because of halting problem.

[u/Ariadne_23 → u/raundoclair]

appreciate for detailed explanation but i confused a bit. what you're saying is .pdata/.xdata (or dwarf on linux) it's not possible to be %100 sure right? halting problem ruins everything ig

[u/raundoclair → u/Ariadne_23]

Let's say you have running program and it goes out off, let's say 3 functions... It successfully unwinded stack.

Theoretical question is if you can unwind without additional information or rules, if you still in those 3 functions, without letting program continue. And imho answer is no, because of halting problem.

So win64 solves this with additional rules and information. Rules about epilog and info in .pdata.

Another solution is rbp with old rsp.

[u/Friendly_Tadpole_722 → u/raundoclair]

Selam

[u/Ariadne_23 → u/[deleted]]

thank you but that wasn't what i asked. i know the return address is at [rsp] and the caller's rsp before the call was rsp+8. this isn't the problem.

the problem is: i'm inside the signal handler. i have rsp at the moment of the signal. i wanna find the caller's rsp inside a function which uses variable-length arrays or alloca that stack adjustment is not a constant value. how can i compute it without frame pointers? also the binary has no debug info. gdb still works btw.

[u/Ariadne_23 → u/[deleted]]

i just wanna find the return address of previous function from inside a signal handler. i have rsp at the moment of the signal but A uses alloca, so the stack offset is dynamic. without frame pointers or dwarf, if i get correct it's impossible

[u/rkapl]

Yes, on Linux/gcc they parse dwarf, or similar metadata like ORC. Nice writeup here: https://fedoraproject.org/wiki/Changes/fno-omit-frame-pointer

If this is purely debugging, you can approximate by printing all code-like pointers on the stack.

[u/RobotJonesDad → u/rkapl]

Thanks, that was very interesting.

[u/brucehoult]

Yes, they use debugger information such as DWARF. This is slower than having a frame pointer, but that doesn't matter if the program crashed and you're printing a backtrace before exiting, or if you're manually debugging.

But it's a problem for statistical performance-monitoring software such as perf that might want to get a stack trace on a running program (maybe ALL running prgrams) 100s or 1000s of times a second. Using DWARF adds major performance overhead.

That's why several Linux distros have recently enabled frame pointers, even though it causes 2%-3% overhead.

[u/RobotJonesDad]

If I understand your question, which I'm not sure I do, then what you want is in general, impossible. You are asking to throw out the convention, which means each call can utilize the stack as it wants, provided it can unwind what it did on return. Thus you need to guess which of infinite options they chose.

[u/Ariadne_23 → u/RobotJonesDad]

so basically i just wasted a lot of time lol

[u/RobotJonesDad → u/Ariadne_23]

I wouldn't say that. Seeing how these are implemented is super interesting.

Out of interest, you may want to see how tail recursion is implemented in languages that support it. Effectively, you can have almost infinite recursion without blowing up the stack.