суббота, 16 января 2016 г.

Изучаем содержимое стека в программе на Assembler: вычисления факториала

В качестве примера возьмём программу вычисления факториала из книги Programming from the Ground Up и исследуем стек программы во время её выполнения.

.text                        # Здесь начинается текст программы.

.globl _start                # Указываем, где расположена точка входа.

.type factorial, @function   # Помечаем factorial как функцию.
factorial:
                             # (S2), (S7)
    nop                      # Нулевая операция, удобно для отладки.
    pushl %ebp               # Сохраняем %ebp в стек. (S3), (S8)
    movl  %esp, %ebp         # Теперь %ebp указывает на вершину стека.
    movl  8(%ebp), %eax      # Помещаем в %eax 1-й аргумент функции.
    cmpl  $1, %eax           # Если он равен 1 (базовый случай),
    je    end_factorial      # то переходим к выходу из функции.

    decl  %eax               # Уменьшаем на единицу аргумент функции и
    pushl %eax               # помещаем его в стэк. (S6)
    call  factorial          # Вызываем саму себя из функции.
    movl  8(%ebp), %ebx      # Помещаем 1-й аргумент функции в %ebx.

    imull %ebx, %eax         # В %eax помещаем результат %eax * %ebx.

    end_factorial:        
        movl %ebp, %esp      # Делаем %ebp вершиной стека. (S12)
        popl %ebp            # Помещаем из стека в %ebp. (S10), (S13)
        ret                  # Выходим из функции. (S11), (S14)

_start:
    pushl $2         # Помещаем аргумент функции factorial
                     # в стек. (S1)

    call factorial   # Вызываем функцию factorial.     
    addl $4, %esp    # Очищаем стек от аргумента функции. (S15)

    movl %eax, %ebx  # Результат функции используем как код
                     # выхода из программы.

    movl $1, %eax    # Заказываем системный вызов exit
    int $0x80        # и вызываем его.
Собираем и запускаем программу:
as --gstabs -o fact.o fact.s && ld -o func fact.o && ./func
Изучаем стек с использованием отладчика: $ gdb func.

Шаг 1

Запускаем программу и помещаем аргумент функции в стек. Для простоты
изучения будем исследовать 2!.
(gdb) disassemble _start 
Dump of assembler code for function _start:
   0x08048071 <+0>: push   $0x2
=> 0x08048073 <+2>: call   0x8048054 
   0x08048078 <+7>: add    $0x4,%esp
   0x0804807b <+10>: mov    %eax,%ebx
   0x0804807d <+12>: mov    $0x1,%eax
   0x08048082 <+17>: int    $0x80
End of assembler dump.

******************** Stack content ***********************************
(gdb) x/8xw $esp  |-- arg1
0xbfffef9c: 0x00000002 0x00000001 0xbffff199  0x00000000
0xbfffefac: 0xbffff1bd 0xbffff1d2 0xbffff1dd  0xbffff1ef
**********************************************************************

(gdb) print $esp
$1 = (void *) 0xbfffef9c

(gdb) print $ebp
$2 = (void *) 0x0

 

Шаг 2

Вызываем функцию. Находимся внутри функции.
******************** Stack content ***********************************
(gdb) x/8xw $esp   
                |-- ret1        |-- arg1
0xbfffef98: 0x08048078 0x00000002 0x00000001  0xbffff199                                
0xbfffefa8: 0x00000000 0xbffff1bd 0xbffff1d2  0xbffff1dd
**********************************************************************

(gdb) print $esp
$3 = (void *) 0xbfffef98    - адрес стека уменьшился на 4 байта

(gdb) print $ebp
$2 = (void *) 0x0

 

Шаг 3

Помещаем %ebp в стек.
(gdb) disassemble factorial 
Dump of assembler code for function factorial:
   0x08048054 <+0>: nop
   0x08048055 <+1>: push   %ebp
=> 0x08048056 <+2>: mov    %esp,%ebp
   0x08048058 <+4>: mov    0x8(%ebp),%eax
   0x0804805b <+7>: cmp    $0x1,%eax
   0x0804805e <+10>: je     0x804806d 
   0x08048060 <+12>: dec    %eax
   0x08048061 <+13>: push   %eax
   0x08048062 <+14>: call   0x8048054 
   0x08048067 <+19>: mov    0x8(%ebp),%ebx
   0x0804806a <+22>: imul   %ebx,%eax
End of assembler dump.

******************** Stack content ***********************************
(gdb) x/8xw $esp
                |-- %ebp        |-- ret 1       |-- arg 1
0xbfffef94: 0x00000000 0x08048078 0x00000002  0x00000001
0xbfffefa4: 0xbffff199 0x00000000 0xbffff1bd  0xbffff1d2
**********************************************************************

(gdb) print $esp
$6 = (void *) 0xbfffef94

(gdb) print $ebp
$7 = (void *) 0x0

 

Шаг 4

Делаем %ebp вершиной стека.
(gdb) x/8xw $esp
0xbfffef94: 0x00000000 0x08048078 0x00000002  0x00000001
0xbfffefa4: 0xbffff199 0x00000000 0xbffff1bd  0xbffff1d2

(gdb) x/8xw $ebp
0xbfffef94: 0x00000000 0x08048078 0x00000002  0x00000001
0xbfffefa4: 0xbffff199 0x00000000 0xbffff1bd  0xbffff1d2

 

Шаг 5

Помещаем первый аргумент в %eax.
(gdb) print $eax
$10 = 2

 

Шаг 6

Помещаем уменьшенный на единицу %eax в стек.
(gdb) x/8xw $esp
                |-- arg1-1      |-- %ebp        |-- ret 1   |-- arg1
0xbfffef90: 0x00000001 0x00000000 0x08048078  0x00000002
0xbfffefa0: 0x00000001 0xbffff199 0x00000000  0xbffff1bd

(gdb) print $esp
$11 = (void *) 0xbfffef90
(gdb) print $ebp
$12 = (void *) 0xbfffef94

 

Шаг 7

Вызываем функцию снова.
(gdb) print $esp
$16 = (void *) 0xbfffef8c
(gdb) print $ebp
$17 = (void *) 0xbfffef94

(gdb) x/8xw $esp
                |-- ret 2       |-- arg1-1      |-- %ebp    |-- ret 1
0xbfffef8c: 0x08048067 0x00000001 0x00000000  0x08048078
                |-- arg1
0xbfffef9c: 0x00000002 0x00000001 0xbffff199  0x00000000

 

Шаг 8

Помещаем %ebp в стек.
(gdb) print $esp
$18 = (void *) 0xbfffef88
(gdb) print $ebp
$19 = (void *) 0xbfffef94

(gdb) x/8xw $esp                    %eax - keep it usually
                |-- %ebp_2      |-- ret 2       |-- arg1-1  |-- %ebp_1
0xbfffef88: 0xbfffef94 0x08048067 0x00000001  0x00000000
                |-- ret 1       |-- arg1
0xbfffef98: 0x08048078 0x00000002 0x00000001  0xbffff19

 

Шаг 9

%ebp теперь указывает на вершину стека.
(gdb) print $esp
$20 = (void *) 0xbfffef88
(gdb) print $ebp
$21 = (void *) 0xbfffef88

 

Шаг 10

Забираем %ebp из стека.
(gdb) print $esp
$27 = (void *) 0xbfffef8c
(gdb) print $ebp
$28 = (void *) 0xbfffef94

(gdb) x/8xw $esp
                |-- ret 2       |-- arg1-1      |-- %ebp    |-- ret 1
0xbfffef8c: 0x08048067 0x00000001 0x00000000  0x08048078
                |-- arg1
0xbfffef9c: 0x00000002 0x00000001 0xbffff199  0x00000000

 

Шаг 11

Первый выход из программы.
(gdb) print $esp
$29 = (void *) 0xbfffef90
(gdb) print $ebp
$30 = (void *) 0xbfffef94

(gdb) x/8xw $esp
                |-- arg1-1      |-- %ebp        |-- ret 1   |-- arg1
0xbfffef90: 0x00000001 0x00000000 0x08048078  0x00000002
0xbfffefa0: 0x00000001 0xbffff199 0x00000000  0xbffff1bd

 

Шаг 12

Восстанавливаем значение %esp, сохранённое в %ebp.
(gdb) x/8xw $esp
                |-- %ebp        |-- ret 1       |-- arg1
0xbfffef94: 0x00000000 0x08048078 0x00000002  0x00000001
0xbfffefa4: 0xbffff199 0x00000000 0xbffff1bd  0xbffff1d2

 

Шаг 13

Забираем %ebp из стека.
(gdb) x/8xw $esp
                |-- ret 1       |-- arg1
0xbfffef98: 0x08048078 0x00000002 0x00000001  0xbffff199
0xbfffefa8: 0x00000000 0xbffff1bd 0xbffff1d2  0xbffff1dd

 

Шаг 14

Выходим из функции окончательно и получаем результат.
(gdb) x/8xw $esp
0xbfffef9c: 0x00000002 0x00000001 0xbffff199  0x00000000
0xbfffefac: 0xbffff1bd 0xbffff1d2 0xbffff1dd  0xbffff1ef

 

Шаг 15

Возвращаем стек в первоначальное состояние.
(gdb) x/8xw $esp
0xbfffefa0: 0x00000001 0xbffff199 0x00000000  0xbffff1bd
0xbfffefb0: 0xbffff1d2 0xbffff1dd 0xbffff1ef  0xbffff206

 

Схематичное изображение стека

SN - номер шага N.
Pushing
####################################################################
| ARG |  | RET1 |  | %EBP_1 |  | ARG - 1 |  | RET2    |  | %EBP_2  |
| ... |  | ARG  |  | RET1   |  | %EBP    |  | ARG - 1 |  | RET2    |
         | ...  |  | ARG    |  | RET1    |  | %EBP    |  | ARG - 1 |
                   | ...    |  | ARG     |  | RET1    |  | %EBP    |
                               | ...     |  | ARG     |  | RET1    |
                                            | ...     |  | ARG     |
                                                         | ...     |

S1       S2         S3         S6           S7           S8

Fetching
###############################################################
| RET2    |  | ARG - 1 |  | %EBP    |  | RET1    |  | ARG     |
| ARG - 1 |  | %EBP    |  | RET1    |  | ARG     |  | ...     |
| %EBP    |  | RET1    |  | ARG     |  | ...     |
| RET1    |  | ARG     |  | ...     |
| ARG     |  | ...     |
| ...     |
           
           
S10          S11          S12          S13          S14        

Комментариев нет:

Отправить комментарий