Stack frame appearance during recursion. C vs assembly

Question

I'm just learning about functions in assembly and the stack frame and so on, so I've been looking at the stack frame in gdb as I run a recursive algorithm to see what happens.

If I run some recursive code in C, the stack looks like I expect it to - an object on the stack for each call of the function. At the lowest level of recursion in a recursive factorial function, the stack frame looks like this: (This is a backtrace in gdb with a breakpoint at the first line of the function.)

(gdb) bt
#0  factorial (n=1) at recursion.c:20
#1  0x00005555555551c7 in factorial (n=2) at recursion.c:21
#2  0x00005555555551c7 in factorial (n=3) at recursion.c:21
#3  0x00005555555551c7 in factorial (n=4) at recursion.c:21
#4  0x00005555555551c7 in factorial (n=5) at recursion.c:21
#5  0x00005555555551c7 in factorial (n=6) at recursion.c:21
#6  0x00005555555551c7 in factorial (n=7) at recursion.c:21
#7  0x00005555555551c7 in factorial (n=8) at recursion.c:21
#8  0x00005555555551c7 in factorial (n=9) at recursion.c:21
#9  0x00005555555551c7 in factorial (n=10) at recursion.c:21
#10 0x000055555555517f in main (argc=2, args=0x7fffffffe768) at recursion.c:13

My C code is like this:

int factorial (int n)
{   
    if (n <= 1) return 1;
    return n * factorial(n-1);
}

Now I do the same in assembly (I've copied this code from Rey Seyfarth's book "Introduction to 64 bit assembly programming" so I am assuming it's correct) and, regardless of the depth of recursion, the stack frame looks like this: (Line 50 is the line call fact).

(gdb) bt
#0  fact () at fact.asm:40
#1  0x00000000004011a8 in greater () at fact.asm:50
#2  0x0000000000000000 in ?? ()

The code for the factorial function is like this - the breakpoint in this case is at the sub rsp, 16 line:

fact:                                   ; recursive function
n       equ     8

        push    rbp
        mov     rbp, rsp
        sub     rsp, 16                 ; make room for n
        cmp     rdi, 1                  ; end recursion if n=1
        jg      greater
        mov     eax, 1
        leave
        ret

greater:
        mov     [rsp+n], rdi            ; save n
        dec     rdi                     ; call fact with n-1
        call    fact
        mov     rdi, [rsp+n]            ; restore original n
        imul    rax, rdi
        leave
        ret

In fact, the output from backtrace is really confusing me in this case. If I place the breakpoint on the line before calling the fact function (dec rdi) then the result is usually this:

(gdb) bt
#0  greater () at fact.asm:49
#1  0x0000000000000000 in ?? ()

But on the fifth call of fact it's this:

(gdb) bt
#0  greater () at fact.asm:49
#1  0x00007ffff7f94be0 in ?? () from /usr/lib/libc.so.6
#2  0x0000000000000006 in ?? ()
#3  0x00007fffffffe5f0 in ?? ()
#4  0x00000000004011a8 in greater () at fact.asm:50
#5  0x0000000000000000 in ?? ()

and then on the seventh call, this:

(gdb) bt
#0  greater () at fact.asm:49
#1  0x0000003000000008 in ?? ()
#2  0x0000000000000004 in ?? ()
#3  0x00007fffffffe5b0 in ?? ()
#4  0x00000000004011a8 in greater () at fact.asm:50
#5  0x0000000000000000 in ?? ()

My questions:

1. Why is the stack not behaving similarly to in C?

2. Why am I getting that last, seemingly garbage, output occasionally?

Thanks!

Answer 1

Why is the stack not behaving similarly to in C?

The stack itself is behaving exactly the same -- the processor doesn't care whether the program is a compiled C, or hand-written assembly.

What isn't behaving the same is GDB's interpretation of what the stack is.

On x86_64 (unlike SPARC), it is impossible to properly unwind the stack, unless you know how each function in the current call stack chain has adjusted it.

GDB uses unwind descriptors, which compilers write to the output precisely for that purpose. Here is a blog post explaining the unwinding process.

Your C program has unwind descriptors (use readelf -wf a.out to see them), but your assembly program doesn't.

Why am I getting that last, seemingly garbage, output occasionally?

In the absence of unwind descriptors, GDB tries to apply heuristics to do as best as it can, and gives up when it encounters a stack level from which it can't move up. Exactly where this happens depends on stack contents, but really doesn't matter: GDB is effectively looking at garbage data (because it doesn't know where to look properly).

P.S. You can augment your assembly program with just a handful of CFI directives to create proper unwind descriptors, and then GDB will happily work on it, except it looks like YASM doesn't support CFI. It is of course trivial to rewrite the assembly into GAS syntax, and then add CFI directives there.