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

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.

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.

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.

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 ):

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.

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.

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.

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.

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.

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 :)