Como as variáveis ​​são armazenadas e recuperadas da pilha de programas?

47

Pedimos desculpas antecipadamente pela ingenuidade desta questão. Eu sou um artista de 50 anos tentando entender corretamente os computadores pela primeira vez. Então aqui vai.

Eu tenho tentado entender como os tipos e variáveis ​​de dados são manipulados por um compilador (em um sentido muito geral, eu sei que há muito). Estou sentindo falta de algo no meu entendimento da relação entre armazenamento na "pilha" e nos tipos de valor e armazenamento na "pilha" e nos tipos de referência (as aspas significam que eu entendo que esses termos são abstrações e não ser tomado literalmente em um contexto tão simplificado como o modo como estou estruturando esta questão). De qualquer forma, minha ideia simplista é que tipos como booleanos e inteiros continuam "na pilha" porque podem, porque são entidades conhecidas em termos de espaço de armazenamento e seu escopo é facilmente controlado de acordo.

Mas o que eu não entendo é como as variáveis ​​na pilha são lidas por um aplicativo - se eu declarar e atribuir xcomo um número inteiro, digamos x = 3, e o armazenamento for reservado na pilha e, em seguida, seu valor 3for armazenado lá, e então em a mesma função que eu declaro e atribuo ycomo, digamos 4, e depois que depois uso xem outra expressão, (digamos z = 5 + x) como o programa pode lerx para avaliar zquando está abaixoyna pilha? Estou claramente perdendo alguma coisa. Será que o local na pilha é apenas sobre o tempo de vida / escopo da variável e que toda a pilha está realmente acessível ao programa o tempo todo? Em caso afirmativo, isso implica que existe algum outro índice que retém os endereços apenas das variáveis ​​na pilha para permitir a recuperação dos valores? Mas então eu pensei que o ponto principal da pilha era que os valores eram armazenados no mesmo local que o endereço da variável? Na minha mente insignificante, parece que se houver esse outro índice, então estamos falando de algo mais parecido com um monte? Estou claramente muito confuso e só espero que haja uma resposta simples para minha pergunta simplista.

Obrigado por ler até aqui.

Celine Atwood
fonte
7
@ fade2black Não concordo - deve ser possível dar uma resposta de duração razoável que resuma os pontos importantes.
David Richerby
9
Você está cometendo o erro extremamente comum de combinar o tipo de valor com o local em que ele está armazenado . É simplesmente falso dizer que os bools vão para a pilha. Os bools entram em variáveis e as variáveis ​​vão para a pilha se seu tempo de vida for curto , e para o heap se seu tempo de vida não for curto. Para alguns pensamentos sobre como isso se relaciona com C #, consulte blogs.msdn.microsoft.com/ericlippert/2010/09/30/...
Eric Lippert
7
Além disso, não pense na pilha como uma pilha de valores em variáveis . Pense nisso como uma pilha de quadros de ativação para métodos . Dentro de um método, você pode acessar qualquer variável da ativação desse método, mas não pode acessar as variáveis ​​do chamador, porque elas não estão no quadro que está no topo da pilha .
Eric Lippert
5
Também: Aplaudo por tomar a iniciativa de aprender algo novo e aprofundar os detalhes de implementação de um idioma. Você está enfrentando um obstáculo interessante aqui: entende o que é uma pilha como um tipo de dados abstrato , mas não como um detalhe de implementação para reificar a ativação e continuação . O último não segue as regras do tipo de dados abstratos da pilha; trata-os mais como diretrizes do que como regras. O objetivo das linguagens de programação é garantir que você não precise entender esses detalhes abstraídos para resolver problemas de programação.
precisa
4
Obrigado Eric, Sava, Thumbnail, esses comentários e referências são extremamente úteis. Eu sempre sinto que pessoas como você devem gemer interiormente quando veem uma pergunta como a minha, mas, por favor, conheça a enorme emoção e satisfação em obter respostas!
Celine Atwood

Respostas:

24

Armazenar variáveis ​​locais em uma pilha é um detalhe de implementação - basicamente uma otimização. Você pode pensar dessa maneira. Ao inserir uma função, o espaço para todas as variáveis ​​locais é alocado em algum lugar. Você pode acessar todas as variáveis, pois conhece sua localização de alguma forma (isso faz parte do processo de alocação). Ao sair de uma função, o espaço é desalocado (liberado).

A pilha é uma maneira de implementar esse processo - você pode pensar nele como uma espécie de "pilha rápida", que possui tamanho limitado e, portanto, é apropriada apenas para pequenas variáveis. Como uma otimização adicional, todas as variáveis ​​locais são armazenadas em um bloco. Como cada variável local possui tamanho conhecido, você sabe o deslocamento de cada variável no bloco e é assim que você a acessa. Isso contrasta com as variáveis ​​alocadas no heap, cujos endereços são armazenados em outras variáveis.

k

Finalmente, deixe-me mencionar que, na prática, algumas das variáveis ​​locais são armazenadas em registradores. Isso ocorre porque o acesso aos registradores é mais rápido que o acesso à pilha. Essa é outra maneira de implementar um espaço para variáveis ​​locais. Mais uma vez, sabemos exatamente onde uma variável é armazenada (desta vez não por deslocamento, mas pelo nome de um registro), e esse tipo de armazenamento é apropriado apenas para pequenos dados.

Yuval Filmus
fonte
1
"Alocado em um bloco" é outro detalhe da implementação. Não importa, no entanto. O compilador sabe como a memória é necessária para as variáveis ​​locais, aloca essa memória em um ou mais blocos e cria as variáveis ​​locais nessa memória.
MSalters
Obrigado, corrigido. De fato, alguns desses "blocos" são apenas registros.
Yuval Filmus
1
Você realmente só precisa da pilha para armazenar os endereços de retorno, se houver. Você pode implementar a recursão sem uma pilha facilmente, passando um ponteiro para o endereço de retorno na pilha.
Yuval Filmus
1
As pilhas @MikeCaron não têm quase nada a ver com recursão. Por que você "explodiria as variáveis" em outras estratégias de implementação?
gardenhead
1
@gardenhead a alternativa mais óbvia (e uma que realmente é / foi usada) é alocar estaticamente as variáveis ​​de cada procedimento. Rápido, simples, previsível ... mas nenhuma recursão ou reentrada é permitida. Isso e a pilha convencional não são as únicas alternativas de curso (alocar dinamicamente tudo é outro), mas eles são geralmente os únicos a discutir quando justificando pilhas :)
hobbs
23

Ter yna pilha não impede fisicamente o xacesso, o que, como você apontou, torna as pilhas de computadores diferentes das outras.

Quando um programa é compilado, as posições das variáveis ​​na pilha também são predeterminadas (dentro do contexto de uma função). No seu exemplo, se a pilha contiver xum y"em cima" dela, o programa saberá com antecedência que xhaverá 1 item abaixo do topo da pilha enquanto estiver dentro da função. Como o hardware do computador pode solicitar explicitamente um item abaixo da parte superior da pilha, o computador pode ser recuperado x, embora ytambém exista.

Será que o local na pilha é apenas sobre o tempo de vida / escopo da variável e que toda a pilha está realmente acessível ao programa o tempo todo?

Sim. Quando você sai de uma função, o ponteiro da pilha volta à sua posição anterior, efetivamente apagando xe y, mas tecnicamente eles ainda estarão lá até que a memória seja usada para outra coisa. Além disso, se sua função chamar outra função xe yainda assim estiver lá e puder ser acessada, intencionalmente indo muito longe na pilha.

aebabis
fonte
1
Até agora, essa parece ser a resposta mais limpa em termos de não falar além do conhecimento que o OP traz para a mesa. +1 para realmente segmentar OP!
Ben I.
1
Eu também concordo! Embora todas as respostas sejam extremamente úteis e sou muito grato, minha postagem original foi motivada porque sinto (d) que toda essa coisa de pilha / pilha é absolutamente fundamental para entender como a distinção entre tipo de valor / referência surge, mas não consegui ' Veja como se você pudesse apenas visualizar o topo da "pilha". Então sua resposta me liberta disso. (Tenho a mesma sensação que tive quando percebi que todas as várias leis dos quadrados inversos da física simplesmente caem da geometria da radiação que sai de uma esfera e você pode desenhar um diagrama simples para vê-la.)
Celine Atwood
Eu amo isso porque é sempre extremamente útil quando você pode ver como e por que algum fenômeno em um nível superior (por exemplo, na linguagem) é realmente devido a algum fenômeno mais básico um pouco mais abaixo na árvore de abstração. Mesmo que seja mantido bastante simples.
Celine Atwood
1
@CelineAtwood Observe que tentar acessar variáveis ​​"à força" depois de removidas da pilha fornecerá um comportamento imprevisível / indefinido e não deve ser feito. Observe que eu não disse "não posso" porque alguns idiomas permitem que você experimente. Ainda assim, seria um erro de programação e deve ser evitado.
code_dredd
12

Para fornecer um exemplo concreto de como um compilador gerencia a pilha e como os valores na pilha são acessados, podemos ver representações visuais, além do código gerado GCCem um ambiente Linux com o i386 como arquitetura de destino.

1. Quadros de pilha

Como você sabe, a pilha é um local no espaço de endereço de um processo em execução usado por funções ou procedimentos , no sentido de que o espaço é alocado na pilha para variáveis ​​declaradas localmente, bem como argumentos passados ​​para a função ( espaço para variáveis ​​declaradas fora de qualquer função (ou seja, variáveis ​​globais) é alocado em uma região diferente na memória virtual). O espaço alocado para todos os dados de uma função é referido a um quadro de pilha . Aqui está uma representação visual de vários quadros de pilha (de Computer Systems: A Programmer's Perspective ):

Quadro de pilha CSAPP

2. Gerenciamento de quadros de pilha e localização variável

Para que os valores gravados na pilha em um quadro de pilha específico sejam gerenciados pelo compilador e lidos pelo programa, deve haver algum método para calcular as posições desses valores e recuperar seu endereço de memória. Os registradores na CPU referidos como ponteiro de pilha e o ponteiro base ajudam nisso.

O ponteiro de base, ebppor convenção, contém o endereço de memória da parte inferior ou base da pilha. As posições de todos os valores dentro do quadro da pilha podem ser calculadas usando o endereço no ponteiro base como referência. Isso é mostrado na figura acima: %ebp + 4é o endereço de memória armazenado no ponteiro base mais 4, por exemplo.

3. Código gerado pelo compilador

Mas o que eu não entendo é como as variáveis ​​na pilha são lidas por um aplicativo - se eu declarar e atribuir x como um número inteiro, digamos x = 3, e o armazenamento for reservado na pilha e seu valor 3 for armazenado lá e, em seguida, na mesma função, declaro e atribuo y como, digamos 4, e depois utilizo x em outra expressão (digamos z = 5 + x) como o programa pode ler x para avaliar z quando está abaixo de y na pilha?

Vamos usar um programa de exemplo simples escrito em C para ver como isso funciona:

int main(void)
{
        int x = 3;
        int y = 4;
        int z = 5 + x;

        return 0;
}

Vamos examinar o texto de montagem produzido pelo GCC para este texto de origem C (limpei-o um pouco por uma questão de clareza):

main:
    pushl   %ebp              # save previous frame's base address on stack
    movl    %esp, %ebp        # use current address of stack pointer as new frame base address
    subl    $16, %esp         # allocate 16 bytes of space on stack for function data
    movl    $3, -12(%ebp)     # variable x at address %ebp - 12
    movl    $4, -8(%ebp)      # variable y at address %ebp - 8
    movl    -12(%ebp), %eax   # write x to register %eax
    addl    $5, %eax          # x + 5 = 9
    movl    %eax, -4(%ebp)    # write 9 to address %ebp - 4 - this is z
    movl    $0, %eax
    leave

O que observamos é que as variáveis X, Y e Z estão localizados em endereços %ebp - 12, %ebp -8e %ebp - 4, respectivamente. Em outras palavras, os locais das variáveis ​​no quadro da pilha main()são calculados usando o endereço de memória salvo no registro da CPU %ebp.

4. Os dados na memória além do ponteiro da pilha estão fora do escopo

Estou claramente perdendo alguma coisa. Será que o local na pilha é apenas sobre o tempo de vida / escopo da variável e que toda a pilha está realmente acessível ao programa o tempo todo? Em caso afirmativo, isso implica que existe algum outro índice que mantém os endereços apenas das variáveis ​​na pilha para permitir que os valores sejam recuperados? Mas então eu pensei que o ponto principal da pilha era que os valores eram armazenados no mesmo local que o endereço da variável?

A pilha é uma região na memória virtual, cujo uso é gerenciado pelo compilador. O compilador gera código de maneira que valores além do ponteiro da pilha (valores além do topo da pilha) nunca sejam referenciados. Quando uma função é chamada, a posição do ponteiro da pilha muda para criar espaço na pilha considerado não "fora dos limites", por assim dizer.

À medida que as funções são chamadas e retornam, o ponteiro da pilha é decrementado e incrementado. Os dados gravados na pilha não desaparecem depois que estão fora do escopo, mas o compilador não gera instruções referenciando esses dados porque não há como o compilador calcular os endereços desses dados usando %ebpou %esp.

5. Resumo

O código que pode ser executado diretamente pela CPU é gerado pelo compilador. O compilador gerencia a pilha, quadros de pilha para funções e registros da CPU. Uma estratégia usada pelo GCC para rastrear os locais das variáveis ​​nos quadros de pilha no código destinado à execução na arquitetura i386 é usar o endereço de memória no ponteiro base do quadro de pilha %ebp, como referência e escrever valores de variáveis ​​nos locais nos quadros de pilha em deslocamentos para o endereço em %ebp.

juliano
fonte
Meu se eu perguntar de onde veio essa imagem? Parece desconfiado familiar ... :-) Pode ter sido em um livro do passado.
The Great Duck
1
nvmd. Acabei de ver o link. Foi o que eu pensei. +1 para compartilhar esse livro.
The Great Duck
1
+1 para o gcc montagem demonstração :)
flow2k
9

Existem dois registros especiais: ESP (ponteiro de pilha) e EBP (ponteiro de base). Quando um procedimento é chamado, as duas primeiras operações são geralmente

push        ebp  
mov         ebp,esp 

A primeira operação salva o valor do EBP na pilha e a segunda operação carrega o valor do ponteiro da pilha no ponteiro base (para acessar as variáveis ​​locais). Portanto, o EBP aponta para o mesmo local que o ESP.

Assembler converte nomes de variáveis ​​em compensações de EBP. Por exemplo, se você tiver duas variáveis ​​locais x,ye algo como

  x = 1;
  y = 2;
  return x + y;

então pode ser traduzido para algo como

   push        ebp  
   mov         ebp,esp
   mov  DWORD PTR [ ebp + 6],  1   ;x = 1
   mov  DWORD PTR [ ebp + 14], 2   ;y = 2
   mov  eax, [ ebp + 6 ]
   add  [ ebp + 14 ], eax          ; x + y 
   mov  eax, [ ebp + 14 ] 
   ...  

Os valores de deslocamento 6 e 14 são calculados em tempo de compilação.

É assim que funciona. Consulte um livro do compilador para obter detalhes.

fade2black
fonte
14
Isso é específico para o intel x86. No ARM, o registro SP (R13) é usado, bem como o FP (R11). E no x86, a falta de registros significa que os compiladores agressivos não usarão EBP, pois podem ser derivados do ESP. Isso fica claro no último exemplo, onde todo o endereçamento relativo ao EBP pode ser traduzido para relativo ao ESP, sem nenhuma outra alteração necessária.
MSalters
Você não está perdendo um SUB no ESP para abrir espaço para x, y em primeiro lugar?
Hagen von Eitzen
@HagenvonEitzen, provavelmente. Eu só queria expressar a idéia de como as variáveis ​​alocadas na pilha são acessadas usando registros de hardware.
Fade2black
Downvoters, comentários por favor !!!
Fade2black
8

Você está confuso porque as variáveis ​​locais armazenadas na pilha não são acessadas com a regra de acesso da pilha: First In Last Out, ou apenas FILO .

O fato é que a regra FILO se aplica a seqüências de chamadas de função e quadros de pilha , em vez de variáveis ​​locais.

O que é um quadro de pilha?

Quando você insere uma função, recebe uma quantidade de memória na pilha, denominada frame da pilha. Variáveis ​​locais da função são armazenadas no quadro da pilha. Você pode imaginar que o tamanho do quadro da pilha varia de função para função, pois cada função tem números e tamanhos diferentes de variáveis ​​locais.

Como as variáveis ​​locais são armazenadas no quadro da pilha não tem nada a ver com o FILO. (Mesmo a ordem de aparência de suas variáveis ​​locais no seu código-fonte não garante que as variáveis ​​locais sejam armazenadas nessa ordem.) Como você deduziu corretamente na sua pergunta, "há algum outro índice que mantém os endereços apenas das variáveis na pilha para permitir que os valores sejam recuperados ". Os endereços das variáveis ​​locais são normalmente calculados com um endereço base , como o endereço limite do quadro da pilha e os valores de deslocamento específicos para cada variável local.

Então, quando esse comportamento do FILO aparece?

Agora, o que acontece se você chamar outra função? A função de chamada deve ter seu próprio quadro de pilha e é esse quadro de pilha que é empurrado na pilha . Ou seja, o quadro de pilha da função de chamada é colocado em cima do quadro de pilha da função de chamada. E se essa função de chamada chamar outra função, seu quadro de pilha será empurrado, novamente, no topo da pilha.

O que acontece se uma função retornar? Quando uma função callee retorna para a função de chamadas, quadro de pilha da função receptor é estalado fora da pilha, liberando espaço para uso futuro.

Então, da sua pergunta:

Será que o local na pilha é apenas sobre o tempo de vida / escopo da variável e que toda a pilha está realmente acessível ao programa o tempo todo?

você está certo aqui porque os valores das variáveis ​​locais no quadro da pilha não são realmente apagados quando a função retorna. O valor permanece lá, embora o local da memória em que está armazenado não pertença ao quadro de pilha de nenhuma função. O valor é apagado quando alguma outra função obtém seu quadro de pilha que inclui o local e grava sobre outro valor nesse local da memória.

Então o que diferencia as pilhas da pilha?

Pilha e pilha são iguais no sentido de que ambos são nomes que se referem a algum espaço na memória. Como podemos acessar qualquer local na memória com seu endereço, você pode acessar qualquer local na pilha ou pilha.

A diferença vem da promessa que o sistema de computador faz sobre como usá-lo. Como você disse, heap é para o tipo de referência. Como os valores na pilha não têm relação com nenhum quadro de pilha específico, o escopo do valor não está vinculado a nenhuma função. Uma variável local, no entanto, tem o escopo definido dentro de uma função e, embora você possa acessar qualquer valor de variável local localizado fora do quadro de pilha da função atual, o sistema tentará garantir que esse tipo de comportamento não ocorra, usando empilhar quadros. Isso nos dá algum tipo de ilusão de que a variável local está com escopo definido para uma função específica.

nglee
fonte
4

Existem várias maneiras de implementar variáveis ​​locais por um sistema de runtime de idioma. Usar uma pilha é uma solução eficiente comum, usada em muitos casos práticos.

Intuitivamente, um ponteiro de pilha spé mantido em tempo de execução (em um endereço fixo ou em um registro - isso realmente importa). Suponha que cada "push" incrementa o ponteiro da pilha.

No tempo de compilação, o compilador determina o endereço de cada variável como sp - Konde Ké uma constante que depende apenas do escopo da variável (portanto, pode ser calculada em tempo de compilação).

Observe que estamos usando a palavra "pilha" aqui em um sentido amplo. Essa pilha não é acessada apenas através de operações push / pop / top, mas também é acessada usando sp - K.

Por exemplo, considere este pseudocódigo:

procedure f(int x, int y) {
  print(x,y);    // (1)
  if (...) {
    int z=x+y; // (2)
    print(x,y,z);  // (3)
  }
  print(x,y); // (4)
  return;
}

Quando o procedimento é chamado, argumentos x,y podem ser transmitidos na pilha. Por uma questão de simplicidade, suponha que a convenção é a que o chamador pressiona xprimeiro e depois y.

Em seguida, o compilador no ponto (1) pode encontrar xem sp - 2ey em sp - 1.

No ponto (2), uma nova variável é trazida no escopo. O compilador gera código que soma x+y, ou seja, o que é apontado porsp - 2 e sp - 1, e empurra o resultado da soma na pilha.

No ponto (3), zé impresso. O compilador sabe que é a última variável no escopo, por isso é apontada por sp - 1. Isso não é mais y, pois spmudou. Ainda assim, para imprimir yo compilador sabe que pode encontrá-lo, nesse escopo, em sp - 2. Similarmente,x agora é encontrado em sp - 3.

No ponto (4), saímos do escopo. zaparece e yé novamente encontrado no endereço sp - 1ex está em sp - 2.

Quando retornamos, um fou o chamador aparecex,y da pilha.

Portanto, calcular Kpara o compilador é uma questão de contar quantas variáveis ​​estão no escopo, aproximadamente. No mundo real, isso é realmente mais complexo, pois nem todas as variáveis ​​têm o mesmo tamanho; portanto, o cálculo de Ké um pouco mais complexo. Às vezes, a pilha também contém o endereço de retorno para f, entãoK deve "pular" também. Mas esses são detalhes técnicos.

Observe que, em algumas linguagens de programação, as coisas podem se tornar ainda mais complexas se recursos mais complexos precisarem ser tratados. Por exemplo, procedimentos aninhados requerem uma análise muito cuidadosa, pois Kagora é necessário "pular" muitos endereços de retorno, especialmente se o procedimento aninhado for recursivo. As funções de fechamento / lambdas / anônimas também requerem algum cuidado para manipular variáveis ​​"capturadas". Ainda assim, o exemplo acima deve ilustrar a idéia básica.

chi
fonte
3

A idéia mais fácil é pensar nas variáveis ​​como nomes de correção para endereços na memória. De fato, alguns montadores exibem o código da máquina dessa maneira ("armazene o valor 5 no endereço i", ondei é um nome de variável).

Alguns desses endereços são "absolutos", como variáveis ​​globais, outros são "relativos", como variáveis ​​locais. Variáveis ​​(ou seja, endereços) nas funções são relativas a algum lugar na "pilha" que é diferente para cada chamada de função; dessa maneira, o mesmo nome pode se referir a diferentes objetos reais, e chamadas circulares para a mesma função são invocações independentes trabalhando na memória independente.

Peter - Restabelecer Monica
fonte
2

Os itens de dados que podem ir para a pilha são colocados na pilha - Sim! É um espaço premium. Além disso, uma vez que entramos xna pilha e depois yentramos na pilha, o ideal é que não possamos acessar xaté que ychegue lá. Precisamos aparecer ypara acessar x. Você os acertou.

A pilha não é de variáveis, mas de frames

Onde você entendeu errado é sobre a própria pilha. Na pilha, não são os itens de dados que são enviados diretamente. Em vez disso, na pilha, algo chamado stack-frameé enviado. Esse quadro de pilha contém os itens de dados. Embora não seja possível acessar os quadros no fundo da pilha, você pode acessar o quadro superior e todos os itens de dados contidos nele.

Digamos que temos nossos itens de dados agrupados em dois quadros de pilha frame-xe frame-y. Empurramos eles um após o outro. Agora, enquanto estiver frame-yem cima frame-x, não é possível acessar idealmente nenhum item de dados frame-x. Somente frame-yé visível. MAS, dado que frame-yé visível, você pode acessar todos os itens de dados incluídos nele. Todo o quadro é visível, expondo todos os itens de dados contidos nele.

Fim da resposta. Mais (discurso retórico) sobre esses quadros

Durante a compilação, é feita uma lista de todas as funções no programa. Em seguida, para cada função é feita uma lista de itens de dados empilháveis . Então, para cada função, a stack-frame-templateé feita. Este modelo é uma estrutura de dados que contém todas as variáveis ​​escolhidas, espaço para dados de entrada da função, dados de saída etc. Agora, durante o tempo de execução, sempre que uma função é chamada, uma cópia disso templateé colocada na pilha - junto com todas as variáveis ​​de entrada e intermediárias . Quando essa função chama outra função, uma cópia nova dessa função stack-frameé colocada na pilha. Agora, enquanto essa função estiver em execução, os itens de dados dessa função serão preservados. Uma vez que função termina, seu quadro de pilha é exibido. Agoraesse quadro de pilha está ativo e esta função pode acessar todas as suas variáveis.

Observe que a estrutura e composição de um quadro de pilha varia de linguagem de programação para linguagem de programação. Mesmo dentro de um idioma, pode haver diferenças sutis em diferentes implementações.


Obrigado por considerar o CS. Eu sou um programador hoje em dia tendo aulas de piano :)

inquisitivo
fonte