Estou tentando obter uma compreensão mais profunda de como as operações de baixo nível das linguagens de programação funcionam e, especialmente, como elas interagem com o SO / CPU. Provavelmente li todas as respostas em todos os tópicos relacionados a pilha / heap aqui no Stack Overflow, e todas são brilhantes. Mas ainda há uma coisa que eu ainda não entendi totalmente.
Considere esta função em pseudo código que tende a ser um código Rust válido ;-)
fn foo() {
let a = 1;
let b = 2;
let c = 3;
let d = 4;
// line X
doSomething(a, b);
doAnotherThing(c, d);
}
É assim que presumo que a pilha se pareça na linha X:
Stack
a +-------------+
| 1 |
b +-------------+
| 2 |
c +-------------+
| 3 |
d +-------------+
| 4 |
+-------------+
Agora, tudo que li sobre como a pilha funciona é que ela obedece estritamente às regras LIFO (último a entrar, primeiro a sair). Assim como um tipo de dados de pilha em .NET, Java ou qualquer outra linguagem de programação.
Mas se for esse o caso, o que acontece depois da linha X? Porque, obviamente, a próxima coisa que precisamos é trabalhar com a
e b
, mas isso significaria que o SO / CPU (?) Tem que sair d
e c
primeiro voltar para a
eb
. Mas aí ia dar um tiro no pé, porque precisa c
e d
na próxima linha.
Então, eu me pergunto o que exatamente acontece nos bastidores?
Outra questão relacionada. Considere que passamos uma referência a uma das outras funções como esta:
fn foo() {
let a = 1;
let b = 2;
let c = 3;
let d = 4;
// line X
doSomething(&a, &b);
doAnotherThing(c, d);
}
Pelo que entendi, isso significaria que os parâmetros em doSomething
estão essencialmente apontando para o mesmo endereço de memória como a
e b
em foo
. Mas, novamente, isso significa que não há pop-up na pilha até chegarmos aa
eb
acontecer.
Esses dois casos me fazem pensar que não entendi totalmente como exatamente a pilha funciona e como segue estritamente as regras LIFO .
LIFO
significa que você pode adicionar ou remover elementos apenas no final da pilha, e você sempre pode ler / alterar qualquer elemento.Respostas:
A pilha de chamadas também pode ser chamada de pilha de quadros.
As coisas que são empilhadas após o princípio LIFO não são as variáveis locais, mas todos os quadros de pilha ("chamadas") das funções que estão sendo chamadas . As variáveis locais são enviadas e colocadas juntas com esses quadros no chamado prólogo e epílogo da função , respectivamente.
Dentro do quadro, a ordem das variáveis é completamente não especificada; Os compiladores "reordenam" as posições das variáveis locais dentro de um quadro de maneira apropriada para otimizar seu alinhamento, de forma que o processador possa buscá-las o mais rápido possível. O fato crucial é que o deslocamento das variáveis em relação a algum endereço fixo é constante ao longo da vida útil do quadro - portanto, é suficiente pegar um endereço de âncora, digamos, o endereço do próprio quadro e trabalhar com deslocamentos desse endereço para as variáveis. Tal endereço de âncora está realmente contido na chamada base ou ponteiro de quadroarmazenado no registro EBP. Os offsets, por outro lado, são claramente conhecidos em tempo de compilação e, portanto, são codificados no código de máquina.
Este gráfico da Wikipedia mostra como a pilha de chamadas típica é estruturada como 1 :
Adicione o deslocamento de uma variável que queremos acessar ao endereço contido no ponteiro do quadro e obteremos o endereço de nossa variável. Resumindo, o código apenas os acessa diretamente por meio de deslocamentos de tempo de compilação constantes do ponteiro base; É simples aritmética de ponteiro.
Exemplo
gcc.godbolt.org nos dá
.. para
main
. Eu dividi o código em três subseções. O prólogo da função consiste nas três primeiras operações:Em seguida,
cin
é movido para o registrador EDI 2 eget
é chamado; O valor de retorno está em EAX.Por enquanto, tudo bem. Agora o interessante acontece:
O byte de ordem inferior de EAX, designado pelo registrador de 8 bits AL, é obtido e armazenado no byte logo após o ponteiro de base : Ou seja
-1(%rbp)
, o deslocamento do ponteiro de base é-1
. Este byte é nossa variávelc
. O deslocamento é negativo porque a pilha cresce para baixo em x86. A próxima operação armazenac
em EAX: EAX é movido para ESI,cout
é movido para EDI e então o operador de inserção é chamado comcout
ec
sendo os argumentos.Finalmente,
main
é armazenado em EAX: 0. Isso se deve àreturn
declaração implícita . Você também pode ver emxorl rax rax
vez demovl
.leave
está abreviando este epílogo e implicitamenteApós esta operação e
ret
ter sido executada, o quadro foi efetivamente exibido, embora o chamador ainda tenha que limpar os argumentos, pois estamos usando a convenção de chamada cdecl. Outras convenções, por exemplo, stdcall, exigem que o receptor faça a limpeza, por exemplo, passando a quantidade de bytes pararet
.Omissão do Frame Pointer
Também é possível não usar deslocamentos do ponteiro de base / quadro, mas sim do ponteiro de pilha (ESB). Isso torna o registrador EBP que, de outra forma, conteria o valor do ponteiro do quadro disponível para uso arbitrário - mas pode tornar a depuração impossível em algumas máquinas e será implicitamente desativado para algumas funções . É particularmente útil ao compilar para processadores com apenas alguns registros, incluindo x86.
Essa otimização é conhecida como FPO (omissão de ponteiro de quadro) e definida por
-fomit-frame-pointer
no GCC e-Oy
no Clang; observe que ele é acionado implicitamente por cada nível de otimização> 0 se e somente se a depuração ainda for possível, uma vez que não tem nenhum custo além disso. Para mais informações, clique aqui e aqui .1 Conforme apontado nos comentários, o ponteiro do frame deve apontar para o endereço após o endereço do remetente.
2 Observe que os registros que começam com R são as contrapartes de 64 bits daqueles que começam com E. EAX designa os quatro bytes de ordem inferior de RAX. Usei os nomes dos registradores de 32 bits para maior clareza.
fonte
rbp
para fazer outro trabalho.Em resumo:
Não há necessidade de apresentar argumentos. Os argumentos passados pelo chamador
foo
para a funçãodoSomething
e as variáveis locais emdoSomething
podem ser referenciados como um deslocamento do ponteiro base .Assim,
Em detalhe:
A regra é que cada chamada de função resulta na criação de um quadro de pilha (com o mínimo sendo o endereço para o qual retornar). Portanto, se
funcA
chamadasfuncB
efuncB
chamadasfuncC
, três frames de pilha são configurados um em cima do outro. Quando uma função retorna, seu quadro se torna inválido . Uma função bem comportada atua apenas em seu próprio quadro de pilha e não invade o de outra. Em outras palavras, o POPing é executado para o frame da pilha no topo (ao retornar da função).A pilha em sua pergunta é configurada pelo chamador
foo
. QuandodoSomething
edoAnotherThing
são chamados, eles configuram sua própria pilha. A figura pode ajudá-lo a entender isso:Observe que, para acessar os argumentos, o corpo da função terá que percorrer para baixo (endereços superiores) a partir do local onde o endereço de retorno está armazenado, e para acessar as variáveis locais, o corpo da função terá que percorrer a pilha (endereços inferiores ) em relação ao local onde o endereço de retorno está armazenado. Na verdade, o código gerado pelo compilador típico para a função fará exatamente isso. O compilador dedica um registro chamado EBP para isso (Base Pointer). Outro nome para o mesmo é ponteiro de quadro. O compilador normalmente, como a primeira coisa para o corpo da função, envia o valor EBP atual para a pilha e define o EBP para o ESP atual. Isso significa que, uma vez feito isso, em qualquer parte do código da função, o argumento 1 está longe de EBP + 8 (4 bytes para cada EBP do chamador e o endereço de retorno), o argumento 2 está longe de EBP + 12 (decimal), variáveis locais estão a EBP-4n de distância.
Dê uma olhada no seguinte código C para a formação do frame da pilha da função:
Quando o chamador ligar
o seguinte código será gerado
e o código de montagem para a função será (configurado pelo receptor antes de retornar)
Referências:
fonte
EBP
eESP
?Como outros observaram, não há necessidade de alterar os parâmetros, até que saiam do escopo.
Vou colar um exemplo de "Ponteiros e memória" de Nick Parlante. Acho que a situação é um pouco mais simples do que você imaginou.
Aqui está o código:
Os pontos no tempo
T1, T2, etc
. são marcados no código e o estado da memória naquele momento é mostrado no desenho:fonte
Processadores e linguagens diferentes usam alguns designs de pilha diferentes. Dois padrões tradicionais no 8x86 e no 68000 são chamados de convenção de chamada Pascal e convenção de chamada C; cada convenção é tratada da mesma maneira em ambos os processadores, exceto pelos nomes dos registradores. Cada um usa dois registradores para gerenciar a pilha e as variáveis associadas, chamados stack pointer (SP ou A7) e frame pointer (BP ou A6).
Ao chamar a sub-rotina usando qualquer uma das convenções, quaisquer parâmetros são colocados na pilha antes de chamar a rotina. O código da rotina então empurra o valor atual do ponteiro do quadro para a pilha, copia o valor atual do ponteiro da pilha para o ponteiro do quadro e subtrai do ponteiro da pilha o número de bytes usados pelas variáveis locais [se houver]. Uma vez feito isso, mesmo se dados adicionais forem colocados na pilha, todas as variáveis locais serão armazenadas em variáveis com um deslocamento negativo constante do ponteiro da pilha, e todos os parâmetros que foram colocados na pilha pelo chamador podem ser acessados em um deslocamento positivo constante do ponteiro do quadro.
A diferença entre as duas convenções está na maneira como tratam uma saída da sub-rotina. Na convenção C, a função de retorno copia o ponteiro do quadro para o ponteiro da pilha [restaurando-o para o valor que tinha logo após o ponteiro do quadro antigo ser pressionado], exibe o valor do ponteiro do quadro antigo e executa um retorno. Todos os parâmetros que o chamador colocou na pilha antes da chamada permanecerão lá. Na convenção Pascal, após exibir o ponteiro do quadro antigo, o processador exibe o endereço de retorno da função, adiciona ao ponteiro da pilha o número de bytes dos parâmetros enviados pelo chamador e, a seguir, vai para o endereço de retorno exibido. No 68000 original, era necessário usar uma sequência de 3 instruções para remover os parâmetros do chamador; o 8x86 e todos os processadores 680x0 após o original incluíam um "ret N"
A convenção Pascal tem a vantagem de salvar um pouco de código no lado do chamador, pois o chamador não precisa atualizar o ponteiro da pilha após uma chamada de função. Requer, entretanto, que a função chamada saiba exatamente quantos bytes de parâmetros o chamador irá colocar na pilha. Falhar em colocar o número apropriado de parâmetros na pilha antes de chamar uma função que usa a convenção Pascal quase certamente causará um travamento. Isso é compensado, entretanto, pelo fato de que um pequeno código extra dentro de cada método chamado salvará o código nos locais onde o método é chamado. Por esse motivo, a maioria das rotinas originais da caixa de ferramentas do Macintosh usava a convenção de chamada Pascal.
A convenção de chamada C tem a vantagem de permitir que as rotinas aceitem um número variável de parâmetros, e ser robusta mesmo se uma rotina não usar todos os parâmetros que são passados (o chamador saberá quantos bytes de parâmetros ela empurrou, e assim será capaz de limpá-los). Além disso, não é necessário realizar a limpeza da pilha após cada chamada de função. Se uma rotina chamar quatro funções em sequência, cada uma das quais usando quatro bytes de parâmetros, ela pode - em vez de usar um
ADD SP,4
após cada chamada, usar umADD SP,16
após a última chamada para limpar os parâmetros de todas as quatro chamadas.Hoje em dia, as convenções de chamada descritas são consideradas um tanto antiquadas. Visto que os compiladores se tornaram mais eficientes no uso de registradores, é comum ter métodos que aceitem alguns parâmetros em registradores em vez de exigir que todos os parâmetros sejam colocados na pilha; se um método pode usar registradores para manter todos os parâmetros e variáveis locais, não há necessidade de usar um ponteiro de quadro e, portanto, não há necessidade de salvar e restaurar o antigo. Ainda assim, às vezes é necessário usar as convenções de chamada mais antigas ao chamar bibliotecas que foram vinculadas para usá-las.
fonte
(g==4)
thenint d = 3
eg
tomo a entrada usandoscanf
depois disso, defino outra variávelint h = 5
. Agora, como o compilador dád = 3
espaço na pilha. Como o deslocamento é feito, porque seg
não for4
, então não haveria memória para d na pilha e simplesmente o deslocamento seria fornecido parah
e se og == 4
deslocamento seria primeiro para ge depois parah
. Como o compilador faz isso em tempo de compilação, ele não conhece nossa entrada parag
Já existem algumas respostas muito boas aqui. No entanto, se você ainda está preocupado com o comportamento LIFO da pilha, pense nela como uma pilha de quadros, em vez de uma pilha de variáveis. O que pretendo sugerir é que, embora uma função possa acessar variáveis que não estão no topo da pilha, ela ainda está operando apenas no item no topo da pilha: um único quadro de pilha.
Claro, existem exceções a isso. As variáveis locais de toda a cadeia de chamadas ainda estão alocadas e disponíveis. Mas eles não serão acessados diretamente. Em vez disso, eles são passados por referência (ou por ponteiro, o que é realmente diferente apenas semanticamente). Nesse caso, uma variável local de um quadro de pilha muito mais abaixo pode ser acessada. Mas, mesmo neste caso, a função atualmente em execução ainda está operando apenas em seus próprios dados locais. Ele está acessando uma referência armazenada em seu próprio quadro de pilha, que pode ser uma referência a algo no heap, na memória estática ou mais abaixo na pilha.
Essa é a parte da abstração da pilha que torna as funções chamadas em qualquer ordem e permite a recursão. O quadro da pilha superior é o único objeto acessado diretamente pelo código. Qualquer outra coisa é acessada indiretamente (por meio de um ponteiro que fica no quadro da pilha superior).
Pode ser instrutivo observar a montagem de seu pequeno programa, especialmente se você compilar sem otimização. Acho que você verá que todo o acesso à memória em sua função acontece por meio de um deslocamento do ponteiro do frame da pilha, que é como o código da função será escrito pelo compilador. No caso de uma passagem por referência, você veria instruções de acesso indireto à memória por meio de um ponteiro armazenado em algum deslocamento do ponteiro do frame da pilha.
fonte
A pilha de chamadas não é realmente uma estrutura de dados de pilha. Nos bastidores, os computadores que usamos são implementações da arquitetura de máquina de acesso aleatório. Portanto, a e b podem ser acessados diretamente.
Nos bastidores, a máquina:
http://en.wikipedia.org/wiki/Random-access_machine
fonte
Aqui está um diagrama que criei para a pilha de chamadas de C. É mais preciso e contemporâneo do que as versões da imagem do Google
E correspondendo à estrutura exata do diagrama acima, aqui está uma depuração de notepad.exe x64 no Windows 7.
Os endereços inferiores e os endereços superiores são trocados de forma que a pilha esteja subindo neste diagrama. Vermelho indica o quadro exatamente como no primeiro diagrama (que usava vermelho e preto, mas o preto agora foi reaproveitado); preto é o espaço doméstico; azul é o endereço de retorno, que é um deslocamento da função do chamador para a instrução após a chamada; laranja é o alinhamento e rosa é para onde o ponteiro da instrução está apontando logo após a chamada e antes da primeira instrução. O valor homeSpace + return é o menor quadro permitido no windows e como o alinhamento rsp de 16 bytes logo no início da função chamada deve ser mantido, isso sempre inclui um alinhamento de 8 bytes também.
BaseThreadInitThunk
e assim por diante.Os quadros de função vermelhos delineiam o que a função do receptor logicamente 'possui' + lê / modifica (pode modificar um parâmetro passado na pilha que era muito grande para passar em um registro em -Ofast). As linhas verdes demarcam o espaço que a função aloca-se do início ao fim da função.
fonte
register
behind o parâmetro otimiza isso, mas você pensaria que isso seria otimizado de qualquer maneira, visto que o endereço nunca é obtido dentro da função. Vou consertar a moldura superior; admito que deveria ter colocado a elipse em um quadro em branco separado. 'um callee possui seus argumentos de pilha', incluindo aqueles que o chamador envia se eles não podem ser passados nos registradores?call
register
e asconst
otimizações só fazem diferença em -O0.