#+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 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 :~$ gdb soma 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 =, antes da chamada de sistema, e =pop 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]]