blau_araujo/pbn
blau_araujo/pbn
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
pbn/curso/aula-05.org

685 lines
25 KiB
Org Mode
Raw Permalink Normal View History

conteúdo da aula 5
2025-05-22 14:15:24 -03:00
#+title: 5 -- Pilha de hardware e pilha de memória
#+author: Blau Araujo
#+email: cursos@blauaraujo.com
#+options: toc:3
* Objetivos
- Entender o que é uma pilha.
- Diferenciar pilha de hardware da pilha de memória.
- Explorar a movimentação do ponteiro da pilha.
- Observar a dinâmica dos quadros de pilha.
- Observar como a pilha se altera com a execução de sub-rotinas.
- Utilizar a pilha para salvar e restaurar estados de registradores.
- Escrever funções simples que manipulam a pilha explicitamente.
* O conceito de pilha (stack)
Pilhas são estruturas lineares de dados que seguem a política LIFO (/Last In,
First Out/), ou seja, o último elemento inserido é o primeiro a ser removido.
#+begin_example
┌──────────────┐ TOPO DA PILHA
│ ELEMENTO N │
├──────────────┤
│ ELEMENTO N-1 │
├──────────────┤
│ ···· │
├──────────────┤
│ ELEMENTO 3 │
├──────────────┤
│ ELEMENTO 2 │
├──────────────┤
│ ELEMENTO 1 │
└──────────────┘ BASE DA PILHA
#+end_example
Por analogia, podemos imaginar uma pilha de pratos: os pratos são colocados um
por cima do outro e, quando precisamos de um prato no meio da pilha, todos que
estiverem acima dele terão que ser retirados primeiro. Isso ilustra bem a
principal característica da estrutura, que é o acesso imediato restrito ao
elemento que estiver no topo da pilha.
** Implementação da pilha como estrutura de dados
Uma pilha pode ser implementada de duas formas principais: utilizando uma
área contígua de memória (como um vetor) ou uma estrutura que cresce conforme
a necessidade (como uma sequência de elementos ligados uns aos outros).
- Como um vetor ::
A pilha é representada por um arranjo fixo de elementos e um índice que
identifica o elemento que estiver no topo. Essa abordagem é simples e
eficiente, mas exige que o tamanho máximo da pilha seja definido
previamente.
- Como uma lista encadeada ::
Os elementos da pilha são criados conforme a necessidade, ligando cada
novo elemento ao que já estiver ocupando a posição do topo. Assim, a pilha
pode crescer ou diminuir dinamicamente, utilizando apenas o espaço de
memória realmente necessário.
** Aplicações típicas
As pilhas são amplamente utilizadas por serem simples e pela sua propriedade
de oferecerem acesso aos dados na ordem inversa de sua inserção. Algumas
aplicações comuns incluem:
- Avaliação de expressões em notação pós-fixada (notação polonesa reversa).
- Operações de desfazer e refazer em editores.
- Verificação do balanceamento de estruturas aninhadas (parêntesis, chaves
e colchetes).
- Algoritmos de busca e retrocesso (/backtracking/), como para explorar
labirintos ou solucionar problemas combinatórios por tentativa e erro.
- Controle de chamadas de funções durante a execução de um programa.
- Tratamento de interrupções de hardware e chamadas de funções e sub-rotinas.
Entre tantas outras. No entanto, as aplicações que nos interessam dizem
respeito às duas últimas da lista, como veremos um pouco mais adiante.
** Operações associadas às pilhas
De modo geral, as operações associadas a uma pilha são:
- *Push:* para inserir um novo elemento no topo da pilha;
- *Pop:* para acessar o elemento do topo da pilha e removê-lo;
- *Peek:* para acessar o elemento no topo da pilha sem removê-lo.
*Operação PUSH:*
#+begin_example
TOPO DA PILHA (novo)
┌──────┐
TOPO DA PILHA │ 23 │
┌──────┐ ├──────┤
│ 64 │ │ 64 │
├──────┤ ├──────┤
│ 42 │ PUSH 23 │ 42 │
├──────┤ ├──────┤
│ 16 │ │ 16 │
└──────┘ └──────┘
BASE DA PILHA BASE DA PILHA
#+end_example
*Operação POP:*
#+begin_example
TOPO DA PILHA
┌──────┐
│ 23 │ TOPO DA PILHA (removido)
├──────┤ ┌──────┐
│ 64 │ A = ??? │ 64 │ A = 23
├──────┤ ├──────┤
│ 42 │ POP A │ 42 │
├──────┤ ├──────┤
│ 16 │ │ 16 │
└──────┘ └──────┘
BASE DA PILHA BASE DA PILHA
#+end_example
*Operação PEEK:*
#+begin_example
TOPO DA PILHA TOPO DA PILHA (não alterado)
┌──────┐ ┌──────┐
│ 23 │ │ 23 │
├──────┤ ├──────┤
│ 64 │ A = ??? │ 64 │ A = 23
├──────┤ ├──────┤
│ 42 │ PEEK A │ 42 │
├──────┤ ├──────┤
│ 16 │ │ 16 │
└──────┘ └──────┘
BASE DA PILHA BASE DA PILHA
#+end_example
* Pilha de memória
No contexto de sistemas GNU/Linux, a /pilha de memória/ é uma região especial da
memória virtual associada a um processo que cresce dinamicamente no sentido dos
endereços mais baixo. Essa estrutura é usada para armazenar dados temporários
durante a execução de um programa, especialmente:
- Endereços de retorno de chamadas de função.
- Valores recebidos pelas funções como argumentos.
- Dados em variáveis locais de funções.
- Dados nos registradores da CPU (/registros/) que foram salvos durante chamadas
e interrupções.
A pilha de memória é controlada pelo hardware e pelo sistema operacional, e seu
comportamento segue a política LIFO, como em toda estrutura de pilha: o último
valor inserido é o primeiro a ser removido. Além disso, em arquiteturas x86_64,
a pilha é acessada principalmente pelos registradores =rsp= (/stack pointer/) e
=rbp= (/base pointer/), e seu uso está profundamente ligado à organização de
chamadas de função e à convenção de chamadas da ABI do sistema.
* Pilha de hardware
Além da pilha de memória, gerenciada pelo sistema e pelas convenções de
chamadas de função, o processador possui um mecanismo chamado /pilha de
hardware/. Trata-se de um recurso interno da CPU que suporta operações de
empilhar (/push/) e desempilhar (/pop/) valores diretamente, facilitando o
gerenciamento da pilha de memória no nível do hardware.
Em processadores Intel 64, as instruções =push= e =pop= operam sobre a pilha de
memória associada ao registrador =rsp= (/stack pointer/), que contém o endereço
do dado que se encontra no topo da pilha.
Quando a instrução =push= é executada, o processador decrementa o valor em =rsp=
(o endereço do dado no topo da pilha) e, em seguida, armazena o novo dado no
endereço resultante. Já a instrução =pop= realiza o oposto: ela lê o valor no
endereço atualmente indicado em =rsp=, copia esse valor para um registrador ou
para outro local na memória, e então incrementa o endereço em =rsp=.
Resumindo:
- *Instrução =push=:* /Decrementa/ do endereço em =rsp= e insere um novo valor no topo
da pilha (a pilha de memória cresce no sentido dos endereços mais baixos).
Exemplo:
#+begin_src asm
push rax ; Copia o valor em rax para um novo
; elemento no topo da pilha.
#+end_src
- *Instrução =pop=:* Copia o dado no topo da pilha para um destino e incrementa o
endereço em =rsp=, o que faz com que o dado no endereço anterior seja ignorado
(e eventualmente sobrescrito) em operações subsequentes.
Exemplo:
#+begin_src asm
pop rax ; Copia para rax o valor que será
; removido do topo da pilha.
#+end_src
#+begin_quote
A implementação em hardware torna operações de pilha muito eficientes, e é uma
das razões pelas quais a pilha de memória é utilizada para controle de fluxo,
armazenamento temporário de dados, e manipulação de chamadas de função. Mas,
embora a CPU tenha suporte para operações com a pilha, sua manipulação depende
também do sistema operacional, da ABI e do compilador, que definem regras para
uso, alinhamento e preservação de seus dados.
#+end_quote
* Registradores e a pilha de memória
Como vimos, registradores são pequenas unidades de armazenamento internas da
CPU para guardar valores temporários. Eles são utilizados constantemente
durante a execução de programas, pois permitem a manipulação de dados sem
depender da memória principal (RAM), que é bem mais lenta.
Antes da execução de funções e sub-rotinas, é comum que o conteúdo de alguns
desses registradores precise ser preservado para que, ao retomar o controle
da sua execução, o programa encontre os mesmos valores que estavam presentes
antes da chamada. Para isso, os valores dos registradores costumam ser salvos
na pilha de memória e restaurados posteriormente.
#+begin_quote
A especificação de quais registradores precisam ser salvos depende do contexto
e, principalmente, das convenções envolvidas, como veremos a seguir.
#+end_quote
* Convenções de chamadas de funções (System V AMD64 ABI)
Ao compilar programas em linguagens como C para sistemas Linux 64 bits, o
código gerado segue uma convenção de chamadas definida pela ABI (/Application
Binary Interface/) do sistema. Essa convenção especifica:
- Quais registradores são usados para passar argumentos.
- Qual registrador é usado para o valor de retorno.
- Quais registradores devem ser preservados entre chamadas de função.
- Como a pilha deve ser utilizada.
** Ordem dos argumentos
Os primeiros seis argumentos de uma função são passados em registradores, na
seguinte ordem:
| Argumento | Registrador |
|-----------+-------------|
| =arg1= | =RDI= |
| =arg2= | =RSI= |
| =arg3= | =RDX= |
| =arg4= | =RCX= |
| =arg5= | =R8= |
| =arg6= | =R9= |
#+begin_quote
Argumentos adicionais são passados na pilha.
#+end_quote
** Valor de retorno
O valor de retorno de uma função é armazenado em:
- =RAX=: para valores inteiros ou ponteiros.
- =RAX + RDX=: para estruturas de até 128 bits.
- =XMM0= (e seguintes): para valores em ponto flutuante.
** Registradores preservados e não preservados
Durante uma chamada de função, há uma distinção entre os registradores que
devem ser preservados e os que podem ser sobrescritos...
Preservados pela função chamada (/callee-saved/):
- =RBX=
- =RBP=
- =R12= a =R15=
#+begin_quote
=RSP= também deve ser restaurado à posição original.
#+end_quote
Não presenrvados (/caller-saved/):
- =RAX=
- =RCX=
- =RDX=
- =RSI=
- =RDI=
- =R8= a =R11=
Os registradores não preservados podem ser modificados pela função chamada.
Assim, se uma função chamadora deseja manter o valor de algum deles após a
chamada, ela será responsável por salvá-los antes.
** Exemplo em C
Arquivo: [[exemplos/05/soma.c][soma.c]]
#+begin_src c :tangle exemplos/05/soma.c
#include <stdio.h>
int soma(int a, int b) {
return a + b;
}
int main() {
int x = 10;
int y = 20;
int r = soma(x, y);
printf("Soma: %d\n", r);
return 0;
}
#+end_src
Durante a execução de =soma(x, y)=, os valores de =x= e =y= são passados via =RDI=
e =RSI=, respectivamente. O resultado é retornado em =RAX=. Se a função =soma=
quiser usar, por exemplo, =RBX=, ela deverá salvá-lo na pilha no início da
função (com =push rbx=) e restaurá-lo (com =pop rbx=) antes de retornar.
** Quadro de pilha (/stack frame/)
Em geral, cada função chamada cria seu próprio /quadro de pilha/, que inclui:
- Valores salvos de registradores preservados.
- Variáveis locais.
- Espaço para armazenar argumentos extras ou retorno de funções chamadas.
A base do quadro costuma ser registrada em =RBP=, como podemos demonstrar
compilando o programa do exemplo e analisando o assembly desmontado pelo
GDB.
*Compilação:*
#+begin_example
:~$ gcc -O0 -no-pie -g -o soma soma.c
#+end_example
Aqui, nós desabilitamos as otimizações (=-O0=) e a geração de um executável
independente de posição (=-no-pie=) para facilitar a análise dos endereços
absolutos das instruções.
*Início do GDB:*
#+begin_example
correção do exemplo em c
2025-05-23 12:17:06 -03:00
:~$ gdb soma
conteúdo da aula 5
2025-05-22 14:15:24 -03:00
Reading symbols from soma...
#+end_example
*Desmontagem da função =soma=:*
#+begin_example
(gdb) disassemble soma
Dump of assembler code for function soma:
0x0000000000401126 <+0>: push rbp
0x0000000000401127 <+1>: mov rbp,rsp
0x000000000040112a <+4>: mov DWORD PTR [rbp-0x4],edi
0x000000000040112d <+7>: mov DWORD PTR [rbp-0x8],esi
0x0000000000401130 <+10>: mov edx,DWORD PTR [rbp-0x4]
0x0000000000401133 <+13>: mov eax,DWORD PTR [rbp-0x8]
0x0000000000401136 <+16>: add eax,edx
0x0000000000401138 <+18>: pop rbp
0x0000000000401139 <+19>: ret
End of assembler dump.
#+end_example
Logo nas duas primeiras instruções, nós podemos ver a inicialização do quadro
de pilha:
#+begin_example
0x0000000000401126 <+0>: push rbp
0x0000000000401127 <+1>: mov rbp,rsp
#+end_example
Onde o endereço da base da pilha (em =rbp=) é inserido como um novo elemento no
topo da pilha. Em seguida, o novo endereço do topo da pilha (em =rsp=) é
copiado (em =rbp=) como o endereço da base da pilha, utilizado nas instruções
seguintes como referencial fixo para a inserção dos dados da função.
Antes do retorno (=ret=), o endereço do topo da pilha é decrementado e o
resultado, salvo em =rbp=, será o endereço que ele armazenava originalmente --
em outras palavras, o estado original de =rbp= é restaurado.
#+begin_example
0x0000000000401138 <+18>: pop rbp
0x0000000000401139 <+19>: ret
#+end_example
Repare também que, entre o início e a remoção do quadro de pilha, os
argumentos passados na chamada da função (registrados em =edi= e =esi=) são
copiados em endereços, respectivamente, 4 e 8 bytes mais baixos que o
endereço em =rbp=:
#+begin_example
0x000000000040112a <+4>: mov DWORD PTR [rbp-0x4],edi
0x000000000040112d <+7>: mov DWORD PTR [rbp-0x8],esi
#+end_example
Deste modo, os dados são inseridos na pilha sem que novos elementos sejam
empilhados, ou seja, para todos os efeitos, o endereço do topo da pilha ainda
será o registrado em =rbp=.
* Convenções de chamadas de sistema
Diferente das chamadas de função ,que utilizam a pilha de memória para
armazenar argumentos e preservar o estado dos registradores, chamadas de
sistema interagem diretamente com o kernel e seguem uma convenção distinta,
mais enxuta e orientada ao uso de registradores.
Em sistemas Linux x86-64, a transição entre espaço de usuário e espaço do
kernel é feita por meio da instrução =syscall=. Os argumentos são passados
exclusivamente por registradores:
| Registrador | Conteúdo |
|-------------+------------------------------|
| =rax= | Número da chamada de sistema |
| =rdi= | 1º argumento |
| =rsi= | 2º argumento |
| =rdx= | 3º argumento |
| =r10= | 4º argumento |
| =r8= | 5º argumento |
| =r9= | 6º argumento |
| =rax= | Valor de retorno |
A pilha permanece intacta durante a chamada de sistema — ou seja, não há
necessidade de alocar um novo quadro de pilha nem de salvar/restaurar
registradores preservados, como ocorre nas convenções de chamadas entre
funções. Em vez disso, o kernel assume que os registradores não preservados
(=rax=, =rcx= e =r11=) podem ser sobrescritos e o processo que realiza a chamada
é que deve se encarregar de salvar qualquer valor que deseje manter.
Essa característica destaca o papel dos registradores temporários: eles são
utilizados livremente pela chamada de sistema, e qualquer valor importante
deve ser salvo na pilha pelo chamador se necessário, o que geralmente é feito
com =push <registrador>=, antes da chamada de sistema, e =pop <registrador> após
a chamada.
** Exemplo em Assembly
Arquivo: [[exemplos/05/salve.asm][salve.asm]]
#+begin_src asm :tangle exemplos/05/salve.asm
section .rodata
msg db "Salve, simpatia!", 10
len equ $ - msg
section .text
global _start
_start:
mov rax, 1 ; syscall write
mov rdi, 1 ; stdout
mov rsi, msg
mov rdx, len
syscall
mov rax, 60 ; syscall exit
mov rdi, 0 ; código de saída 0
syscall
#+end_src
Com este exemplo, nós queremos demonstrar que, nas chamadas de sistema:
- Nenhum dado é empilhado.
- Nenhum registrador é preservado.
- O controle é transferido diretamente ao kernel por meio de =syscall=.
- Após o retorno do kernel, o processo continua sua execução ou é finalizado.
Para isso, vamos montá-lo e abrir o executável com o GDB:
#+begin_example
:~$ nasm -f elf64 -g salve.asm
:~$ ld -o salve salve.o
:~$ gdb salve
Reading symbols from salve...
(gdb)
#+end_example
Com o comando =list=, nós descobrimos que a instrução que processará a chamada
de sistema =write= (=sycall=) está na linha 13:
#+begin_example
(gdb) list
1 section .rodata
2 msg db "Salve, simpatia!", 10
3 len equ $ - msg
4
5 section .text
6 global _start
7
8 _start:
9 mov rax, 1 ; syscall write
10 mov rdi, 1 ; stdout
(gdb)
11 mov rsi, msg
12 mov rdx, len
13 syscall
14
15 mov rax, 60 ; syscall exit
16 mov rdi, 0 ; código de saída 0
17 syscall
#+end_example
Sendo assim, ela será o nosso ponto de parada:
#+begin_example
(gdb) break 13
Breakpoint 1 at 0x401019: file salve.asm, line 13.
#+end_example
Nosso objetivo é comparar o estado dos registradores antes e depois da
execução do ponto de parada para determinar o que mudou. Então, vamos
executar o programa e inspecionar o estado corrente dos registradores:
#+begin_example
(gdb) run
Starting program: /home/blau/git/pbn/curso/exemplos/05/salve
Breakpoint 1, _start () at salve.asm:13
13 syscall
(gdb) info registers
rax 0x1 1
rbx 0x0 0
rcx 0x0 0
rdx 0x11 17
rsi 0x402000 4202496
rdi 0x1 1
rbp 0x0 0x0
rsp 0x7fffffffdfd0 0x7fffffffdfd0
r8 0x0 0
r9 0x0 0
r10 0x0 0
r11 0x0 0
r12 0x0 0
r13 0x0 0
r14 0x0 0
r15 0x0 0
rip 0x401019 0x401019 <_start+25>
eflags 0x202 [ IF ]
cs 0x33 51
ss 0x2b 43
ds 0x0 0
es 0x0 0
fs 0x0 0
gs 0x0 0
fs_base 0x0 0
gs_base 0x0 0
#+end_example
Note que, até aqui, nós utilizamos apenas os registradores...
- =RAX=: Identificação da chamada de sistema =write= (=0x1=);
- =RDX=: Quantidade de bytes a serem impressos (=0x11 = 17=);
- =RSI=: O endereço do primeiro byte da mensagem (=0x402000=);
- =RDI=: O número do descritor de arquivos (=0x1 = stdout=).
Todos os demais estão em seus estados originais, menos =RIP=, o ponteiro de
instruções, que sempre é atualizado para indicar o endereço da próxima
instrução a ser executada. No caso, =RIP= contém o endereço =0x401019=, que é
exatamente o endereço da instrução =syscall=, no nosso ponto de parada.
Mas vejamos o que acontece quando a chamada de sistema é processada:
#+begin_example
(gdb) next
Salve, simpatia!
15 mov rax, 60 ; syscall exit
(gdb) info registers
rax 0x11 17
rbx 0x0 0
rcx 0x401004 4198404
rdx 0x11 17
rsi 0x402000 4202496
rdi 0x1 1
rbp 0x0 0x0
rsp 0x7fffffffdfd0 0x7fffffffdfd0
r8 0x0 0
r9 0x0 0
r10 0x0 0
r11 0x302 770
r12 0x0 0
r13 0x0 0
r14 0x0 0
r15 0x0 0
rip 0x40101b 0x40101b <_start+27>
eflags 0x202 [ IF ]
cs 0x33 51
ss 0x2b 43
ds 0x0 0
es 0x0 0
fs 0x0 0
gs 0x0 0
fs_base 0x0 0
gs_base 0x0 0
#+end_example
Observe que apenas três registradores foram alterados:
| Registrador | Antes | Depois |
|-------------+-------+-----------|
| =RAX= | =0x1= | =0x11 (17)= |
| =RCX= | =0x0= | =0x401004= |
| =R11= | =0x0= | =0x302= |
*Causa da mudança em RAX:*
O registrador =RAX= é utilizado como retorno da chamada de sistema =write= e
recebe a quantidade de bytes impressos (17).
*Causa da mudança em RCX:*
Quando uma chamada de sistema é processada, o endereço da instrução seguinte
(originalmente em =RIP=) é salvo em =RCX= e restaurado para =RIP= antes do retorno
da chamada, mas isso não significa que, no espaço de usuário, após a linha de
=syscall=, nós encontraremos em =RCX= o mesmo endereço registrado em =RIP=. Not
e que os valores em =RCX= e =RIP= são diferentes após a chamada de sistema:
#+begin_example
(gdb) info registers rcx rip
rcx 0x401004 4198404
rip 0x40101b 0x40101b <_start+27>
#+end_example
Acontece que, depois de restaurado o endereço em =RIP=, o kernel está livre
para utilizar =RCX= antes de retornar ao espaço de usuário. Por isso, em
chamadas de sistema, =RCX= é considerado um registrador /volátil/, ou seja, seu
conteúdo pode ser alterado a qualquer momento pelos próprios mecanismos
internos da transição entre os modos de execução, sem qualquer garantia de
preservação.
*Causa da mudança em R11:*
Internamente, em uma chamada de sistema, =R11= é utilizado para salvar e
restaurar o estado do registrador =RFLAGS= (=eflags= no GDB). Contudo, assim
como acontece com =RCX=, após a restauração de =RFLAGS= o kernel está livre
para utilizar =R11= no processo de transição de volta ao espaço de usuário,
o que justifica a diferença encontrada nesses dois registradores:
#+begin_example
(gdb) info registers r11 eflags
r11 0x302 770
eflags 0x202 [ IF ]
#+end_example
** Preservação de registradores com a pilha
Se for necessário, é possível salvar e restaurar os registradores =RAX=, =RCX= e
=R11= para a execução de uma chamada de sistema. A técnica mais comum em
arquiteturas x86_64 envolve a utilização da pilha de memória:
#+begin_src asm
push rax ; salva rax como elemento N da pilha
push rcx ; salva rcx como elemento N+1 da pilha
push r11 ; salva r11 como elemento N+2 da pilha (atual topo)
; código da chamada de sistema...
pop r11 ; restaura e remove elemento N+2 da pilha (atual topo)
pop rcx ; restaura e remove elemento N+1 da pilha
pop rax ; restaura e remove elemento N da pilha
#+end_src
É importante observar a ordem de salvamento e restauração, porque estamos
lidando com uma pilha, e o elemento em seu topo sempre será o último que
tiver sido empilhado.
** Resumo comparativo com chamadas de funções
Finalmente, aqui está uma tabela comparando as principais diferenças entre
as convenções de chamadas de funções e a ABI do kernel para chamadas de
sistema:
| Aspecto | Chamadas de função | Chamadas de sistema |
|------------------------+-----------------------+---------------------------------|
| Interface | Conveção System V ABI | ABI do kernel (syscall ABI) |
| Usa a pilha de memória | Sim (quadro de pilha) | Não (usa registradores) |
| Preserva registradores | Sim | Não (registradores temporários) |
| Instrução de transição | =call=, =ret= | =syscall= |
| Participação do kernel | Não | Sim |
* Exercícios propostos
...
* Referências
- man 2 syscall
- [[https://wiki.osdev.org/Calling_Conventions][OS Dev: Calling Conventions]]
- [[https://wiki.osdev.org/Stack][OS Dev: Stack]]
Reference in a new issue Copy permalink