Я только изучаю функции в ассемблере, фрейм стека и так далее, поэтому я смотрел на фрейм стека в 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 ?? ()
Мои вопросы:
Почему стек ведет себя не так, как в C?
Почему я иногда получаю этот последний, казалось бы, мусорный вывод?
Спасибо!
rbp
, его использование (например,mov [rbp-n], rdi
) немного эффективнее вместо доступа относительно RSP. Размер кода (дополнительный байт SIB для базы = RSP) и операции синхронизации стека из механизма стека. Вы можете ужесточить этот код несколькими способами, например.imul rax, [rbp-n]
и резервирует дополнительное пространство стека только вgreater
, а не сразу после входа. Также для частной рекурсии не беспокойтесь о выравнивании стека по 16 байт, потому что вы никогда не вызываете другие функции. так что простоpush rdi
, чтобы сохранить его. - person Peter Cordes   schedule 08.09.2018