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

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

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

Спасибо!


person jezza    schedule 07.09.2018    source источник
comment
Вы не предоставляете отладочную информацию. Тем не менее, поскольку вы используете стандартные фреймы стека, я ожидаю, что gdb сможет это понять. Очевидно, это не так. Просто осмотрите стек самостоятельно.   -  person Jester    schedule 07.09.2018
comment
Есть ли способ предоставить отладочную информацию? Я компилирую с помощью yasm -g dwarf2...   -  person jezza    schedule 07.09.2018
comment
Судя по этому вопросу, по-видимому, нет.   -  person Jester    schedule 07.09.2018
comment
хорошо спасибо за помощь   -  person jezza    schedule 07.09.2018
comment
Попробуйте objdump -d вашего приложения c и сравните вывод с вашим ассемблерным кодом.   -  person    schedule 07.09.2018
comment
Если у вас есть обычный кадр стека с использованием rbp, его использование (например, mov [rbp-n], rdi) немного эффективнее вместо доступа относительно RSP. Размер кода (дополнительный байт SIB для базы = RSP) и операции синхронизации стека из механизма стека. Вы можете ужесточить этот код несколькими способами, например. imul rax, [rbp-n] и резервирует дополнительное пространство стека только в greater, а не сразу после входа. Также для частной рекурсии не беспокойтесь о выравнивании стека по 16 байт, потому что вы никогда не вызываете другие функции. так что просто push rdi, чтобы сохранить его.   -  person Peter Cordes    schedule 08.09.2018


Ответы (1)


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

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

Что отличается от других, так это интерпретация GDB того, что такое стек.

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

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

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

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

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

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

person Employed Russian    schedule 08.09.2018
comment
Программа сборки OP написана на YASM (а не на GAS), поэтому (согласно комментариям к вопросу) для этого ассемблера нет директив CFI. (И, возможно, не NASM, который использует тот же синтаксис/директивы.) - person Peter Cordes; 09.09.2018
comment
Эта программа использует стандартные фреймы стека, поэтому эвристика gdb не очень хороша. Создание обратной трассировки должно быть тривиальным. Ирония в том, что gdb не может этого сделать, поскольку одним из распространенных аргументов в пользу стандартных кадров стека является лучшая отладка. - person Jester; 09.09.2018