Pilha de chamadas - Call stack

Em ciência da computação , uma pilha de chamadas é uma estrutura de pilha de dados que armazena informações sobre as sub - rotinas ativas de um programa de computador . Este tipo de pilha também é conhecido como uma pilha de execução , pilha do programa , pilha controle , pilha de tempo de execução , ou pilha máquina , e é muitas vezes abreviado para apenas " a pilha ". Embora a manutenção da pilha de chamadas seja importante para o funcionamento adequado da maioria dos softwares , os detalhes são normalmente ocultos e automáticos em linguagens de programação de alto nível . Muitos conjuntos de instruções de computador fornecem instruções especiais para a manipulação de pilhas.

Uma pilha de chamadas é usada para vários fins relacionados, mas o principal motivo para ter uma é manter o controle do ponto ao qual cada sub-rotina ativa deve retornar o controle quando terminar de ser executada. Uma sub-rotina ativa é aquela que foi chamada, mas ainda não concluiu a execução, após o que o controle deve ser devolvido ao ponto de chamada. Essas ativações de sub-rotinas podem ser aninhadas em qualquer nível (recursivo como um caso especial), daí a estrutura da pilha. Por exemplo, se uma sub-rotina DrawSquarechama uma sub DrawLine- rotina de quatro lugares diferentes, DrawLinedeve saber para onde retornar quando sua execução for concluída. Para fazer isso, o endereço que segue a instrução que salta para DrawLine, o endereço de retorno , é colocado no topo da pilha de chamadas com cada chamada.

Descrição

Como a pilha de chamadas é organizada como uma pilha , o chamador coloca o endereço de retorno na pilha e a sub-rotina chamada, quando termina, puxa ou retira o endereço de retorno da pilha de chamadas e transfere o controle para esse endereço. Se uma sub-rotina chamada chamar ainda outra sub-rotina, ela enviará outro endereço de retorno para a pilha de chamadas e assim por diante, com as informações sendo empilhadas e desempilhadas conforme o programa dita. Se o push consumir todo o espaço alocado para a pilha de chamadas, ocorrerá um erro denominado estouro de pilha , geralmente causando o travamento do programa . Adicionar uma entrada de sub-rotina à pilha de chamadas às vezes é chamado de "enrolamento"; inversamente, remover entradas é "desenrolar".

Geralmente, há exatamente uma pilha de chamadas associada a um programa em execução (ou, mais precisamente, a cada tarefa ou thread de um processo ), embora pilhas adicionais possam ser criadas para manipulação de sinal ou multitarefa cooperativa (como com setcontext ). Como há apenas um neste importante contexto, ele pode ser referido como a pilha (implicitamente, "da tarefa"); no entanto, na linguagem de programação Forth a pilha de dados ou pilha parâmetro é acessado de forma mais explícita do que a pilha de chamadas e é comumente referido como a pilha (ver abaixo).

Em linguagens de programação de alto nível , as especificações da pilha de chamadas geralmente são ocultadas do programador. Eles têm acesso apenas a um conjunto de funções, e não à memória da pilha em si. Este é um exemplo de abstração . A maioria das linguagens assembly , por outro lado, exige que os programadores se envolvam na manipulação da pilha. Os detalhes reais da pilha em uma linguagem de programação dependem do compilador , do sistema operacional e do conjunto de instruções disponível .

Funções da pilha de chamadas

Conforme observado acima, o objetivo principal de uma pilha de chamadas é armazenar os endereços de retorno . Quando uma sub-rotina é chamada, a localização (endereço) da instrução na qual a rotina de chamada pode ser retomada posteriormente precisa ser salva em algum lugar. Usar uma pilha para salvar o endereço de retorno tem vantagens importantes sobre as convenções de chamada alternativas . Uma delas é que cada tarefa pode ter sua própria pilha e, portanto, a sub-rotina pode ser thread-safe , ou seja, pode estar ativa simultaneamente para diferentes tarefas fazendo coisas diferentes. Outro benefício é que, ao fornecer reentrada , a recursão é automaticamente suportada. Quando uma função chama a si mesma recursivamente, um endereço de retorno precisa ser armazenado para cada ativação da função para que possa ser usado posteriormente para retornar da ativação da função. As estruturas de pilha fornecem esse recurso automaticamente.

Dependendo do idioma, sistema operacional e ambiente da máquina, uma pilha de chamadas pode servir a finalidades adicionais, incluindo, por exemplo:

Armazenamento de dados local
Veja também: Alocação de memória baseada em pilha
Uma sub-rotina freqüentemente precisa de espaço na memória para armazenar os valores das variáveis ​​locais , as variáveis ​​que são conhecidas apenas dentro da sub-rotina ativa e não retêm valores após seu retorno. Freqüentemente, é conveniente alocar espaço para esse uso simplesmente movendo o topo da pilha o suficiente para fornecer o espaço. Isso é muito rápido quando comparado à alocação de memória dinâmica , que usa o espaço de heap . Observe que cada ativação separada de uma sub-rotina obtém seu próprio espaço separado na pilha para locais.
Passagem de parâmetro
As sub-rotinas geralmente exigem que os valores dos parâmetros sejam fornecidos a eles pelo código que os chama, e não é incomum que o espaço para esses parâmetros seja disposto na pilha de chamadas. Geralmente, se houver apenas alguns parâmetros pequenos, os registros do processador serão usados ​​para passar os valores, mas se houver mais parâmetros do que podem ser tratados dessa forma, será necessário espaço na memória. A pilha de chamadas funciona bem como um local para esses parâmetros, especialmente porque cada chamada para uma sub-rotina, que terá valores diferentes para os parâmetros, receberá um espaço separado na pilha de chamadas para esses valores.
Pilha de avaliação
Operandos para operações aritméticas ou lógicas são mais freqüentemente colocados em registradores e operados neles. No entanto, em algumas situações, os operandos podem ser empilhados até uma profundidade arbitrária, o que significa que algo mais do que registros deve ser usado (é o caso do derramamento de registros ). A pilha de tais operandos, como em uma calculadora RPN , é chamada de pilha de avaliação e pode ocupar espaço na pilha de chamadas.
Ponteiro para a instância atual
Algumas linguagens orientadas a objetos (por exemplo, C ++ ), armazenam o ponteiro this junto com os argumentos da função na pilha de chamadas ao invocar métodos. O ponteiro this aponta para a instância do objeto associada ao método a ser chamado.
Contexto de sub-rotina envolvente
Algumas linguagens de programação (por exemplo, Pascal e Ada ) suportam a declaração de sub-rotinas aninhadas , que têm permissão para acessar o contexto de suas rotinas envolventes, ou seja, os parâmetros e variáveis ​​locais dentro do escopo das rotinas externas. Esse aninhamento estático pode se repetir - uma função declarada dentro de uma função declarada dentro de uma função ... A implementação deve fornecer um meio pelo qual uma função chamada em qualquer nível de aninhamento estático dado pode fazer referência ao quadro delimitador em cada nível de aninhamento delimitador. Normalmente, essa referência é implementada por um ponteiro para o quadro da instância ativada mais recentemente da função envolvente, chamada de "link de downstack" ou "link estático", para distingui-lo do "link dinâmico" que se refere ao chamador imediato ( que não precisa ser a função pai estática).

Em vez de um link estático, as referências aos quadros estáticos incluídos podem ser coletadas em uma matriz de ponteiros conhecida como exibição que é indexada para localizar um quadro desejado. A profundidade do aninhamento léxico de uma rotina é uma constante conhecida, portanto, o tamanho da exibição de uma rotina é fixo. Além disso, o número de escopos de contenção a serem percorridos é conhecido, o índice na exibição também é fixo. Normalmente, a exibição de uma rotina está localizada em seu próprio quadro de pilha, mas o Burroughs B6500 implementou tal exibição em hardware que suportava até 32 níveis de aninhamento estático.
As entradas de exibição que denotam escopos contendo são obtidas a partir do prefixo apropriado da exibição do chamador. Uma rotina interna que recorre cria quadros de chamada separados para cada invocação. Nesse caso, todos os links estáticos da rotina interna apontam para o mesmo contexto de rotina externa.
Outro estado de retorno
Ao lado do endereço de retorno, em alguns ambientes, pode haver outros estados de máquina ou software que precisam ser restaurados quando uma sub-rotina retorna. Isso pode incluir coisas como nível de privilégio, informações de tratamento de exceção, modos aritméticos e assim por diante. Se necessário, isso pode ser armazenado na pilha de chamadas, assim como o endereço de retorno.

A pilha de chamadas típica é usada para o endereço de retorno, locais e parâmetros (conhecidos como quadro de chamada ). Em alguns ambientes, pode haver mais ou menos funções atribuídas à pilha de chamadas. Na linguagem de programação Forth , por exemplo, normalmente apenas o endereço de retorno, parâmetros de loop contados e índices e, possivelmente, variáveis ​​locais são armazenados na pilha de chamadas (que nesse ambiente é chamada de pilha de retorno ), embora quaisquer dados possam ser colocados temporariamente usando código especial de tratamento de pilha de retorno, desde que as necessidades de chamadas e retornos sejam respeitadas; parâmetros são normalmente armazenados em um separar pilha de dados ou pilha de parâmetro , normalmente chamado a pilha na terminologia Forth, embora haja uma pilha de chamadas, uma vez que geralmente é acessada de forma mais explícita. Alguns Forths também têm uma terceira pilha para parâmetros de ponto flutuante .

Estrutura

Layout de pilha de chamadas para pilhas crescentes

Uma pilha de chamadas é composta de quadros de pilha (também chamados de registros de ativação ou quadros de ativação ). Estas são estruturas de dados dependentes de máquina e de ABI contendo informações de estado de sub-rotina. Cada quadro de pilha corresponde a uma chamada a uma sub-rotina que ainda não terminou com um retorno. Por exemplo, se uma sub-rotina nomeada DrawLineestá atualmente em execução, tendo sido chamada por uma sub-rotina DrawSquare, a parte superior da pilha de chamadas pode ser disposta como na imagem adjacente.

Um diagrama como este pode ser desenhado em qualquer direção, desde que o posicionamento do topo e, assim, a direção do crescimento da pilha seja entendida. Além disso, independentemente disso, as arquiteturas diferem quanto ao fato de as pilhas de chamadas crescerem para endereços mais altos ou mais baixos. A lógica do diagrama é independente da escolha de endereçamento.

O quadro de pilha no topo da pilha é para a rotina em execução no momento. O frame da pilha geralmente inclui pelo menos os seguintes itens (em ordem push):

  • os argumentos (valores de parâmetros) passados ​​para a rotina (se houver);
  • o endereço de retorno de volta para o chamador da rotina (por exemplo, no DrawLinequadro de pilha, um endereço no DrawSquarecódigo de); e
  • espaço para as variáveis ​​locais da rotina (se houver).

Ponteiros de pilha e quadro

Quando os tamanhos dos quadros da pilha podem ser diferentes, como entre funções diferentes ou entre chamadas de uma função específica, retirar um quadro da pilha não constitui um decréscimo fixo do ponteiro da pilha . No retorno da função, o ponteiro da pilha é restaurado ao ponteiro do quadro , o valor do ponteiro da pilha pouco antes de a função ser chamada. Cada quadro de pilha contém um ponteiro de pilha para o topo do quadro imediatamente abaixo. O ponteiro da pilha é um registro mutável compartilhado entre todas as invocações. Um ponteiro de quadro de uma determinada chamada de uma função é uma cópia do ponteiro da pilha como era antes de a função ser chamada.

As localizações de todos os outros campos no quadro podem ser definidas em relação ao topo do quadro, como deslocamentos negativos do ponteiro da pilha, ou em relação ao topo do quadro abaixo, como deslocamentos positivos do ponteiro do quadro. A localização do próprio ponteiro do quadro deve ser inerentemente definida como um deslocamento negativo do ponteiro da pilha.

Armazenando o endereço no frame do chamador

Na maioria dos sistemas, um quadro de pilha tem um campo para conter o valor anterior do registrador de ponteiro de quadro, o valor que ele tinha enquanto o chamador estava executando. Por exemplo, o frame da pilha de DrawLineteria um local de memória contendo o valor do ponteiro do frame que DrawSquareusa (não mostrado no diagrama acima). O valor é salvo na entrada na sub-rotina e restaurado no retorno. Ter tal campo em um local conhecido no quadro de pilha permite que o código acesse cada quadro sucessivamente abaixo do quadro da rotina em execução no momento e também permite que a rotina restaure facilmente o ponteiro do quadro para o quadro do chamador , logo antes de retornar.

Rotinas lexicamente aninhadas

Mais informações: função aninhada e variável não local

As linguagens de programação que suportam sub-rotinas aninhadas também têm um campo no quadro de chamada que aponta para o quadro de pilha da última ativação do procedimento que encapsula mais de perto o receptor, ou seja, o escopo imediato do receptor. Isso é chamado de link de acesso ou link estático (uma vez que mantém o controle do aninhamento estático durante chamadas dinâmicas e recursivas) e fornece à rotina (bem como quaisquer outras rotinas que ela possa invocar) acesso aos dados locais de suas rotinas de encapsulamento em cada aninhamento nível. Algumas arquiteturas, compiladores ou casos de otimização armazenam um link para cada nível de inclusão (não apenas o imediatamente envolvente), de forma que rotinas profundamente aninhadas que acessam dados superficiais não tenham que atravessar vários links; esta estratégia é freqüentemente chamada de "display".

Os links de acesso podem ser otimizados quando uma função interna não acessa nenhum dado local (não constante) no encapsulamento, como é o caso com funções puras que se comunicam apenas por meio de argumentos e valores de retorno, por exemplo. Alguns computadores históricos, como os grandes sistemas Burroughs , tinham "registros de exibição" especiais para suportar funções aninhadas, enquanto os compiladores para a maioria das máquinas modernas (como o onipresente x86) simplesmente reservam algumas palavras na pilha para os ponteiros, conforme necessário.

Sobreposição

Para alguns propósitos, o frame da pilha de uma sub-rotina e o de seu chamador podem ser considerados sobrepostos, a sobreposição consistindo na área onde os parâmetros são passados ​​do chamador para o receptor. Em alguns ambientes, o chamador coloca cada argumento na pilha, estendendo assim sua estrutura de pilha e, em seguida, invoca o receptor. Em outros ambientes, o chamador tem uma área pré-alocada no topo de sua estrutura de pilha para conter os argumentos que fornece a outras sub-rotinas que chama. Essa área às vezes é denominada área de argumentos de saída ou área de texto explicativo . Sob essa abordagem, o tamanho da área é calculado pelo compilador para ser o maior necessário para qualquer sub-rotina chamada.

Usar

Processamento do site da chamada

Normalmente, a manipulação da pilha de chamadas necessária no local de uma chamada para uma sub-rotina é mínima (o que é bom, pois pode haver muitos sites de chamada para cada sub-rotina a ser chamada). Os valores dos argumentos reais são avaliados no site da chamada, uma vez que são específicos para a chamada em particular, e colocados na pilha ou colocados em registradores, conforme determinado pela convenção de chamada usada . A instrução de chamada real, como "branch and link", é normalmente executada para transferir o controle para o código da sub-rotina de destino.

Processamento de entrada de subrotina

Na sub-rotina chamada, o primeiro código executado é geralmente denominado prólogo da sub - rotina , uma vez que faz a manutenção necessária antes que o código para as instruções da rotina seja iniciado.

Para arquiteturas de conjunto de instruções em que a instrução usada para chamar uma sub-rotina coloca o endereço de retorno em um registrador, em vez de colocá-lo na pilha, o prólogo normalmente salvará o endereço de retorno colocando o valor na pilha de chamadas, embora se o chamado a sub-rotina não chama nenhuma outra rotina, ela pode deixar o valor no registrador. Da mesma forma, o ponteiro da pilha atual e / ou os valores do ponteiro do quadro podem ser empurrados.

Se ponteiros de quadro estiverem sendo usados, o prólogo normalmente definirá o novo valor do registro de ponteiro de quadro a partir do ponteiro da pilha. O espaço na pilha para variáveis ​​locais pode então ser alocado alterando incrementalmente o ponteiro da pilha.

A linguagem de programação Forth permite o enrolamento explícito da pilha de chamadas (chamada aqui de "pilha de retorno").

Processamento de devolução

Quando uma sub-rotina está pronta para retornar, ela executa um epílogo que desfaz as etapas do prólogo. Isso normalmente restaurará os valores de registro salvos (como o valor do ponteiro do quadro) do quadro de pilha, retirará todo o quadro da pilha alterando o valor do ponteiro da pilha e, finalmente, desviará para a instrução no endereço de retorno. Sob muitas convenções de chamada, os itens retirados da pilha pelo epílogo incluem os valores do argumento original, caso em que geralmente não há mais manipulações de pilha que precisem ser feitas pelo chamador. Com algumas convenções de chamada, entretanto, é responsabilidade do chamador remover os argumentos da pilha após o retorno.

Desenrolando

Retornar da função chamada irá retirar o quadro superior da pilha, talvez deixando um valor de retorno. O ato mais geral de retirar um ou mais quadros da pilha para retomar a execução em outro lugar no programa é chamado de desenrolamento da pilha e deve ser executado quando estruturas de controle não locais são usadas, como aquelas usadas para tratamento de exceções . Nesse caso, o quadro de pilha de uma função contém uma ou mais entradas especificando manipuladores de exceção. Quando uma exceção é lançada, a pilha é desfeita até que seja encontrado um manipulador que esteja preparado para tratar (capturar) o tipo da exceção lançada.

Algumas linguagens possuem outras estruturas de controle que requerem um desdobramento geral. Pascal permite que uma instrução goto global transfira o controle de uma função aninhada para uma função externa invocada anteriormente. Esta operação requer que a pilha seja desenrolada, removendo quantos frames de pilha forem necessários para restaurar o contexto apropriado para transferir o controle para a instrução de destino dentro da função externa envolvente. Da mesma forma, C tem as funções setjmpelongjmp que atuam como gotos não locais. Common Lisp permite controlar o que acontece quando a pilha é desfeita usando o unwind-protectoperador especial.

Ao aplicar uma continuação , a pilha é (logicamente) desenrolada e depois rebobinada com a pilha da continuação. Esta não é a única maneira de implementar continuações; por exemplo, usando várias pilhas explícitas, a aplicação de uma continuação pode simplesmente ativar sua pilha e encerrar um valor a ser passado. A linguagem de programação Scheme permite que thunks arbitrários sejam executados em pontos especificados no "desenrolamento" ou "retrocesso" da pilha de controle quando uma continuação é chamada.

Inspeção

Veja também: Profiling (programação de computador)

A pilha de chamadas às vezes pode ser inspecionada enquanto o programa está sendo executado. Dependendo de como o programa é escrito e compilado, as informações na pilha podem ser usadas para determinar valores intermediários e rastreamentos de chamadas de função. Isso foi usado para gerar testes automatizados de baixa granularidade e, em casos como Ruby e Smalltalk, para implementar continuações de primeira classe. Como exemplo, o GNU Debugger (GDB) implementa a inspeção interativa da pilha de chamadas de um programa C em execução, mas pausado.

Obter amostras de tempo regular da pilha de chamadas pode ser útil na criação de perfil de desempenho de programas, porque se o ponteiro de uma sub-rotina aparecer nos dados de amostragem da pilha de chamadas muitas vezes, é provável que seja um gargalo de código e deve ser inspecionado para problemas de desempenho.

Segurança

Artigo principal: Stack buffer overflow

Em uma linguagem com ponteiros livres ou gravações de array não verificadas (como em C), a mistura de dados de fluxo de controle que afetam a execução do código (os endereços de retorno ou os ponteiros de quadro salvos) e dados de programa simples (parâmetros ou valores de retorno ) em uma pilha de chamadas é um risco de segurança, possivelmente explorável por meio de estouros de buffer de pilha como o tipo mais comum de estouros de buffer .

Um desses ataques envolve preencher um buffer com código executável arbitrário e, em seguida, estourar o mesmo ou algum outro buffer para substituir algum endereço de retorno com um valor que aponta diretamente para o código executável. Como resultado, quando a função retorna, o computador executa esse código. Este tipo de ataque pode ser facilmente bloqueado com W ^ X . Ataques semelhantes podem ter sucesso mesmo com a proteção W ^ X habilitada, incluindo o ataque return-to-libc ou os ataques vindos da programação orientada a retorno . Várias mitigações foram propostas, como o armazenamento de matrizes em um local completamente separado da pilha de retorno, como é o caso da linguagem de programação Forth.

Veja também

Referências

Leitura adicional

links externos