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

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

0 голосов
/ 07 сентября 2018

Я просто изучаю функции в сборке, фрейм стека и т. Д., Поэтому я смотрел на фрейм стека в 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. Почему я иногда получаю последний, казалось бы, мусор, вывод?

Спасибо!

1 Ответ

0 голосов
/ 08 сентября 2018

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

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

То, что не ведет себя одинаково, является интерпретацией GDB значения стека.

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

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

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

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

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

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

...