Внешний вид стека во время рекурсии. С против сборки

Question

Я просто изучаю функции в сборке и фрейме стека и так далее, поэтому я смотрел на фрейм стека в gdb, когда запускаю рекурсивный алгоритм, чтобы посмотреть, что произойдет.

Если я запускаю некоторый рекурсивный код на C, стек выглядит так, как я и ожидал - объект в стеке для каждого вызова функции. На самом низком уровне рекурсии в рекурсивной факториальной функции кадр стека выглядит следующим образом: (Это обратная трассировка в GDB с точкой останова в первой строке функции.)

(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

Мой код C выглядит так:

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

Теперь я делаю то же самое в сборке (я скопировал этот код из книги Рэя Сейфарта "Введение в программирование на 64-битной сборке", поэтому я предполагаю, что это правильно), и, независимо от глубины рекурсии, кадр стека выглядит следующим образом: (Линия 50 - это линия call fact).

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

Код для факториальной функции выглядит следующим образом - точка останова в этом случае находится на sub rsp, 16 линия:

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

Фактически, вывод от backtrace действительно смущает меня в этом случае. Если я ставлю точку останова на линии перед вызовом функции факта (dec rdi) то результат обычно такой:

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

Но на пятом факте это так:

(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 ?? ()

а затем на седьмом звонке, это:

(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 ?? ()

Мои вопросы:

1. Почему стек не ведет себя так же, как в C?

2. Почему я иногда получаю последний, казалось бы, мусор?

Спасибо!

Answer 1

Почему стек не ведет себя так же, как в C?

Сам стек ведет себя точно так же - процессору все равно, является ли программа скомпилированным C или рукописной сборкой.

То,что не ведет себя так же, это интерпретация GDB того, что такое стек.

Наx86_64(В отличие отSPARC), невозможно правильно размотать стек, если вы не знаете, как каждая функция в текущей цепочке вызовов настроила его.

GDB использует дескрипторы размотки, которые компиляторы записывают в выходные данные именно для этой цели. Вот сообщение в блоге, объясняющее процесс раскручивания.

В вашей C-программе есть дескрипторы размотки (используйте readelf -wf a.out чтобы увидеть их), но ваша программа сборки нет.

Почему я иногда получаю последний, казалось бы, мусор?

В отсутствие дескрипторов раскрутки GDB пытается применить эвристику, чтобы сделать все возможное, и сдается, когда он сталкивается с уровнем стека, с которого он не может двигаться вверх. Точно, где это происходит, зависит от содержимого стека, но на самом деле это не имеет значения: GDB эффективно просматривает мусорные данные (потому что он не знает, где искать правильно).

PS Вы можете дополнить вашу программу сборки всего несколькими директивами CFI для создания правильных дескрипторов раскрутки, и тогда GDB с удовольствием с этим поработает, за исключением того, что YASM не поддерживает CFI. Конечно, тривиально переписать сборку в синтаксис GAS, а затем добавить туда директивы CFI.