I implemented recursive fibonacci as an exercise, and the program seems to work perfectly except for one thing: when stepping through the function with gdb, the "backtrace" command just doesn't work
Here's the source
# fib.s
.data
.text
.globl fib
fib:
stp x29, x30, [sp, #-16]!
mov x29, sp
# Recursive compute fib(n). Even though this is a really dumb way to do Fibonacci,
# this exercise is practically mandatory
# x0: uint64_t -> Result in x0
mov x1, #1
cmp x0, x1
ble root
# Gotta do some recursive shenanigans
stp x19, x20, [sp, #-16]!
sub x0, x0, 1
mov x19, x0
bl fib
mov x20, x0
mov x0, x19
sub x0, x0, 1
bl fib
add x0, x0, x20
ldp x19, x20, [sp], #16
root:
ldp x29, x30, [sp], #16
ret
# main.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
extern uint64_t fib(uint64_t);
int main() {
uint64_t i;
printf("Enter a number please: ");
if (scanf("%lu", &i) == EOF) {
printf("HOLY MOLY That's not a number");
exit(1);
}
printf("Fib(%lu) = %lu\n", i, fib(i));
exit(0);
}
and steps to build
mkdir -p build
gcc -g -Wall -Wextra -c main.c -o build/ul5_1.o
as -g fib.s -o ul5_2.o
ld -lc --entry main build/ul5* -o build/l5.o
But when you start stepping through the code with gdbtui (provide 4 when the program asks for it), you'll see that bt only works as expected up until you hit that second stp. After that though, bt will start showing the following error
Backtrace stopped: Previous frame identical to this frame (corrupt stack?)
I thought fib conforms to AAPCS64, and I think the stack management is correct: so what am I missing/doing wrong?
Your code isn't wrong, but it sets up its stack frame differently from C-compiled code, and this is probably confusing gdb.
You pushed x29, x30 to the stack at entry, and then later pushed the call-preserved registers x19, x20 below that. But the typical stack frame setup has x29, x30 at the bottom of the stack frame, and all local variables (including spilled registers) above that. This means in particular that the saved frame pointer can always be found at [sp], and the return address at [sp, #8], and it might be that gdb expects to see this.
The advantage of this scheme is that it results in slightly more efficient code. It would look like
fib:
stp x29, x30, [sp, #-32]! // includes 16 bytes for locals
mov x29, sp
// more code
stp x19, x20, [sp, #16] // note, no writeback
// code
ldp x19, x20, [sp, #16]
ldp x29, x30, [sp], #32
ret
This way, only the initial stp of x29, x30 has to use the more expensive writeback indexed store instruction. All other accesses to the stack frame don't need to adjust sp. In particular, they don't create a write dependency on sp, making it possible for them to execute concurrently out-of-order.
If I change your code to use that scheme, then in my tests bt works as expected at all points in the code.
I believe it is possible, using .cfi directives or similar, to annotate the code to inform a debugger (as well as throw/catch stack unwinding in languages where it exists) when sp points somewhere other than its usual location. This would be needed even in C-compiled code if, for instance, you called a function with a large number of arguments, such that they have to be passed on the stack. I'm not familiar with the details, but perhaps someone else is?