Pilha de chamada

Em ciência da computação, uma pilha de chamada (ou pilha de execução) é uma pilha que armazena informações sobre as sub-rotinas ativas num programa de computador. Seu principal uso é registrar o ponto em que cada sub-rotina ativa deve retornar o controle de execução quando termina de executar.

Por exemplo, se uma sub-rotina DesenhaQuadrado chama (invoca) a sub-rotina DesenhaLinha em quatro pontos diferentes, o código de DesenhaLinha deve saber como retornar a DesenhaQuadrado. Isso geralmente é feito adicionando o endereço de retorno na pilha de chamada após a chamada da sub-rotina.

Sendo organizada como uma pilha, quem invoca a sub-rotina empilha o endereço de retorno. Quando termina sua execução, a sub-rotina invocada desempilha o endereço de retorno, desviando a execução para aquele endereço. Se durante sua execução a sub-rotina invocada também invocar outra sub-rotina, o endereço de retorno também será empilhado, e assim por diante. Quando esse processo de empilhamento consome todo o espaço alocado para a pilha de chamada, ocorre um erro chamado estouro de pilha.

Existe um pilha de chamada para cada thread sendo executada, ainda que mais pilhas possam ser criadas para o tratamento de sinais ou para multitarefa cooperativa.

Em linguagens de alto nível, detalhes da pilha de chamada são geralmente escondidos do programador. Eles têm acesso somente a lista de sub-rotinas empilhadas, e não à memória da pilha de chamada em si. Por outro lado, a maioria das linguagens de montagem requerem que programador manipule a pilha de chamada.

Atribuições

Uma das principais atribuições duma pilha de chamada é armazenar o endereço de retorno. Quando uma sub-rotina é chamada, a localização da instrução a ser retornada deve ser salva. Usar uma pilha para salvar o endereço de retorno possui importantes vantagens. Uma delas é que cada tarefa possui sua própria pilha, o que permite reentrância. Outro benefício é o suporte automático a recursividade.

Outra atribuição é o armazenamento de variáveis locais. Uma sub-rotina frequentemente precisa de memória para armazenar variáveis locais, aquelas que são usadas somente durante a execução da sub-rotina. Geralmente aloca-se espaço na própria pilha de chamada para tal, o que é muito rápido comparado a alocação dinâmica de memória. Também relacionado a variáveis locais está a passagem de parâmetros, mais uma atribuição. Uma sub-rotina frequentemente precisa ser alimentada por parâmetros quando é invocada, e é comum usar a pilha de chamada para tal. De forma geral, se há poucos e pequenos parâmetros, registradores do processador são usados para passar os parâmetros. Mas se há muitos parâmetros, ou se eles ocupam muito espaço, a pilha de chamada é usada.

Operandos de operações aritméticas ou lógicas são manipulados a partir de registradores, de onde são calculados. Mas para casos específicos deve-se usar uma profundidade específica de operandos, algo que somente registradores não conseguem armazenar. A pilha de operações aritméticas e lógicas pode estar localizada na pilha de chamada.

Algumas linguagens orientadas a objeto armazenam o ponteiro this junto aos parâmetros dos métodos sendo invocados. Esse ponteiro indica a instância associada ao método sendo invocado, sendo essencial para fornecer contexto a execução. Também relacionado a contexto, algumas linguagens de programação suportam sub-rotinas aninhadas, permitindo que a rotina aninhada acesse o contexto externo, da rotina que a aninhou (parâmetros, variáveis locais). Tais linguagens geralmente aceitam a chamada recursiva da sub-rotina aninhada, sendo que todas as chamadas recursivas apontam para o mesmo contexto externo.

Além do endereço de retorno, alguns ambientes podem suportar outros estados que são restaurados no retorno duma sub-rotina, como níveis de privilégio, informação para o tratamento de exceções, entre outros.

Estrutura

Uma pilha de chamada é composta por quadros (muitas vezes chamados de registros de ativação^[1]), estruturas de dados que dependem da implementação e que contêm informações sobre o estado da sub-rotina. Cada quadro da pilha corresponde a uma chamada de sub-rotina que ainda não retornou. Por exemplo, se uma sub-rotina DesenhaLinha está em execução, e foi chamada por DesenhaQuadrado, o topo da pilha de chamada pode ser estruturada da seguinte forma:

Ponteiro da pilha →	topo da pilha
	Variáveis locais de DesenhaLinha	Quadro de DesenhaLinha
Ponteiro do quadro →	Endereço de retorno
	Parâmetros de DesenhaLinha
	Variáveis locais de DesenhaQuadrado	Quadro de DesenhaQuadrado
	Endereço de retorno
	Parâmetros de DesenhaQuadrado
	. . .

O quadro de pilha no topo da pilha se refere a sub-rotina em execução. Geralmente o quadro inclui espaço para as variáveis locais, o endereço de retorno para a sub-rotina que invocou a outra (quadro de pilha seguinte) e os parâmetros passados para a sub-rotina. A pilha é geralmente acessada através do registrador "ponteiro da pilha", que também serve para indicar o topo da pilha. Alternativamente, a memória do quadro pode ser acessada por outro registrador, o "ponteiro do quadro", que geralmente aponta para um ponto específico do quadro, como o endereço de retorno.

Cada quadro possui um tamanho específico, determinado pelo número e tamanho de parâmetros e variáveis locais, ainda que o tamanho seja fixo para diferentes chamadas duma mesma sub-rotina. Entretanto, algumas linguagens suportam alocação dinâmica de memória para variáveis locais na pilha de chamada, de forma que o tamanho do quadro duma sub-rotina não seja fixo, variando de acordo com a chamada. Com esse tipo de alocação dinâmica, o tamanho do quadro não pode ser obtido em tempo de compilação. Portanto, o acesso ao quadro é feito pelo ponteiro de quadro ao invés do ponteiro da pilha.

Em alguns sistemas o quadro de pilha possui um campo que contém o valor anterior do registrador "ponteiro de quadro", isto é, o valor desse registrador enquanto o quadro anterior estava em execução. Por exemplo, no diagrama anterior, o quadro de DesenhaLinha teria uma área de memória para o valor do ponteiro de quadro de DesenhaQuadrado. Isso permite que se acesse por código os quadros abaixo do atual. Linguagens de programação que suportam sub-rotinas aninhadas possuem um campo no quadro que aponta para o quadro da sub-rotina que começou o aninhamento. Isso permite que as sub-rotinas aninhadas acessem as variáveis locais e os parâmetros da sub-rotina que as invocou.

Estouro de pilha

Ver artigo principal: Estouro de pilha

Quando a pilha de chamada usa mais memória do que suporta, ocorre um estouro de pilha. Em diversas linguagens de programação a pilha de chamada possui uma área limitada de memória, geralmente determinada no início do programa. O resultado do uso excessivo de memória é o estouro, o que geralmente resulta no aborto do programa.^[2]

Uma das causas mais comuns desse bug é a recursividade infinita, em que o ponto de parada da recursividade não ocorre antes do enchimento da pilha. Outra causa é a tentativa de alocar mais memória na pilha do que ela suporta. Como variáveis locais e parâmetros são alocados na pilha de chamada, o uso excessivo de memória nesses casos pode levar ao estouro da pilha. Uma alternativa é alocar a memória dinamicamente.^[3]

Como programas com suporte a threads geralmente possuem uma área de pilha menor que programas sem suporte, o bug geralmente se manifesta mais nesses ambientes multitarefa. Da mesma forma, no desenvolvimento de núcleo é desencorajado o uso de algoritmos recursivos ou de buffers muito grandes na pilha de chamada.^[4][5]

Exemplos

Segue abaixo alguns exemplos em C:

Recursividade infinita

void f(void); 
void g(void);
 
int main(void) { f(); return 0; }
 
void f(void) { g(); }
 
void g(void) { f(); }

f() invoca g(), que invoca f() e assim por diante. Em dado momento a pilha de chamada estoura.

Alocação excessiva de memória

int main(void) {
  int n[10000000]; /* vetor muito grande */

  int j = 0; /* endereço de j excede o limite da pilha, erro */
}

Referências

1. GUEZZI, Carlo; JAZAYERI, Mehdi (1998). Programming Languages Concepts (em inglês) 3ª ed. New York: John Wiley & Sons. 52 páginas. ISBN 0-471-10426-4 !CS1 manut: Nomes múltiplos: lista de autores (link)
2. James Craig Burley (1 de junho de 1991). «Using and Porting GNU Fortran» (em inglês). Consultado em 9 de julho de 2008. Arquivado do original em 5 de outubro de 2012
3. Howard Feldman (23 de novembro de 2005). «Modern Memory Management, Part 2» (em inglês)
4. «Kernel Programming Guide: Performance and Stability Tips» (em inglês). Apple Inc. 7 de novembro de 2006
5. Randy Dunlap (19 de maio de 2005). «Linux Kernel Development: Getting Started» (PDF) (em inglês). Consultado em 9 de julho de 2008. Arquivado do original (PDF) em 27 de fevereiro de 2012