A pilha de chamadas: registos de ativação, endereços de retorno e transbordamentos

Uma chamada de função faz algumas escritas na memória. O retorno salta para um endereço lido dessa mesma memória. Escolha um dos quatro pequenos programas e avance passo a passo, observando a pilha, com o endereço mais alto no topo. Cada escrita aparece a âmbar; cada leitura, a azul. As posições deixadas por um registo de ativação retirado da pilha continuam visíveis, esbatidas: nada as apagou.

Exemplo resolvido — A pilha de chamadas: registos de ativação, endereços de retorno e transbordamentos

Chamadas efetuadas	5
Profundidade máxima, em registos de ativação	5
Memória ocupada na pilha à profundidade máxima	60 de 128 bytes
Resultado	120

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — A pilha de chamadas: registos de ativação, endereços de retorno e transbordamentos

A pilha de chamadas é uma região de memória onde cada chamada de função recebe um registo de ativação. Aqui, esse registo contém o argumento, o endereço de retorno (o ponto onde a função chamadora retoma a execução), o ponteiro de registo de ativação da função chamadora, guardado para posterior reposição, e as variáveis locais. O ponteiro da pilha indica o endereço mais baixo em uso. Uma chamada fá-lo descer o espaço de um registo; o retorno fá-lo subir de novo. Uma recursão com d chamadas de profundidade e registos de f bytes exige d·f bytes de pilha.

O que significa cada símbolo

d: profundidade: registos de ativação simultaneamente na pilha
f: bytes por registo de ativação: aqui, 12 mais 4 por variável local

Pressupõe: Uma máquina de 32 bits com a convenção clássica de chamadas em C: posições de 4 bytes, pilha a crescer para endereços mais baixos, argumentos passados pela pilha e um ponteiro de registo de ativação em cada registo. Nas convenções de 64 bits usadas na prática, os primeiros argumentos passam por registos do processador. Os compiladores podem omitir o ponteiro de registo de ativação e, em ARM, uma função que não chama outras pode manter o endereço de retorno num registo do processador. Por isso, o tamanho e a disposição dos registos de ativação reais diferem deste modelo de três posições.

O endereço de retorno é um número na memória que um vetor pode sobrescrever 🖖

Carregue em Seis em quatro. Em buf, copy tem espaço para quatro valores do tipo int. Como buf[0] ocupa o endereço mais baixo, buf[4] e buf[5] correspondem às duas posições imediatamente acima do vetor. A chamada colocou aí o ponteiro de registo de ativação guardado e, a seguir, o endereço de retorno. O ciclo nunca verifica o índice: o quinto valor substitui o ponteiro e o sexto, 0x46464646, substitui o endereço de retorno. Quando copy termina, o processador lê essa posição e salta para o endereço que lá encontrar. Com quatro valores, regressa a 0x08048400, como previsto. Com cinco, ainda regressa ao mesmo endereço, mas devolve a main um ponteiro de registo de ativação corrompido. Trata-se de um transbordamento de buffer na pilha. Em novembro de 1988, o worm Morris explorou uma falha deste tipo para invadir fingerd: o programa lia a entrada para um buffer de 512 bytes sem limitar a quantidade de dados lidos.

Uma variável sem valor atribuído conserva o que a chamada anterior deixou 🖖

Carregue em Valor que ficou. set escreve 42 na sua variável local e termina. O retorno faz subir o ponteiro da pilha, sem apagar nada. A seguir, peek é chamada a partir do mesmo ponto, pelo que o seu registo de ativação ocupa os mesmos endereços. A variável local y fica no endereço 1008, precisamente onde estava x. Como peek nunca escreve em y, a leitura devolve 42. Em C, ler uma variável não inicializada constitui comportamento indefinido: a linguagem não dá qualquer garantia, e um compilador com otimizações pode nem sequer ler essa posição. Quando a leitura ocorre, encontra o valor deixado pela última escrita nesse endereço.

A pilha guarda um percurso pelas chamadas 🖖

Defina o argumento de fib como 10. A função faz 177 chamadas, mas a pilha atinge apenas 10 registos de ativação, ou 120 bytes. O registo de uma chamada é retirado antes de se inserir o da chamada irmã; em cada instante, a pilha contém apenas a cadeia que vai de fib(10) à chamada em execução. fact(11) faz 11 chamadas, cerca de um dezasseis avos desse total, e transborda: a sua cadeia tem 11 registos e exige 132 bytes. Nestas duas funções, cada chamada realiza uma quantidade fixa de trabalho além das chamadas recursivas. Assim, o número de chamadas mede o tempo de execução; a profundidade da cadeia mais longa mede a memória necessária na pilha.

Problema resolvido na íntegra

Até que profundidade pode ir a recursão? 4 passos
Carregue em fact(11) transborda. A pilha desta página tem 128 bytes. Por predefinição, o editor de ligações da Microsoft reserva 1 MB de pilha para um programa. Considere esse valor como 1 MiB, ou 1 048 576 bytes, com os registos de ativação usados nesta página. Até que profundidade pode ir fact? E se cada chamada tiver também uma variável local de 4 bytes? Compare ainda a memória de pilha necessária para fib(30) com o número de chamadas que faz.

Abrir este problema na ferramenta
1. Aqui, cada registo de ativação contém um argumento, um endereço de retorno e um ponteiro de registo de ativação guardado: 3 × 4 = 12 bytes. Como 128 / 12 = 10,67, cabem 10 registos. fact(11) exige 11 × 12 = 132 bytes. A tabela de resultados indica o transbordamento.
  
  $f = 3 \times 4 = 12, ⌊ \frac{128}{12} ⌋ = 10, 11 \times 12 = 132 > 128$
2. 1 048 576 / 12 = 87 381,33, pelo que cabem 87 381 registos de ativação. fact poderia atingir 87 381 níveis de recursão antes de esgotar a pilha. Muito antes disso, o resultado já deixaria de caber num int de 32 bits: isso acontece em 13! = 6 227 020 800.
  
  $⌊ \frac{1 048 576}{12} ⌋ = 87381$
3. Com uma variável local de 4 bytes, cada registo de ativação ocupa 16 bytes, e 1 048 576 / 16 = 65 536, exatamente.
  
  $f = 16 : \frac{1 048 576}{16} = 65536$
4. A cadeia mais longa de fib(30) tem 30 registos de ativação: 30 × 12 = 360 bytes. O número de chamadas é 2·F(31) − 1, com F(31) = 1 346 269, o 31.º número de Fibonacci. São 2 692 537 chamadas.
  
  $d = 30 : 30 \times 12 = 360, 2 F_{31} - 1 = 2 \times 1346269 - 1 = 2692537$
Resposta

87 381 níveis, ou 65 536 com uma variável local. fib(30) precisa de 360 bytes de pilha para 2 692 537 chamadas. A profundidade determina a memória necessária na pilha; em fib, o número de chamadas determina o tempo de execução.

$d_{m a x} = ⌊ \frac{S}{f} ⌋ = 87381 (f = 12), 65536 (f = 16)$

Percurso de aprendizagem

Como um computador executa um programa

Referências (2)

The worked problem's stack size: the linker's default reservation: Microsoft Learn, "/STACK (Stack allocations)," C/C++ build reference, updated 23 February 2022.
The first insight's 1988 example: fingerd's unbounded read into a 512-byte buffer on the stack: Bob Page, "A Report on the Internet Worm." University of Lowell, 7 November 1988 (copy hosted at Toronto Metropolitan University).

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.