Qual é a direção do crescimento da pilha na maioria dos sistemas modernos?

102

Estou preparando alguns materiais de treinamento em C e quero que meus exemplos se encaixem no modelo de pilha típico.

Em que direção uma pilha C cresce no Linux, Windows, Mac OSX (PPC e x86), Solaris e Unixes mais recentes?

Uri
fonte
3
Uma versão do porque para baixo: stackoverflow.com/questions/2035568/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Respostas:

147

O crescimento da pilha geralmente não depende do próprio sistema operacional, mas do processador em que está sendo executado. Solaris, por exemplo, funciona em x86 e SPARC. Mac OSX (como você mencionou) é executado em PPC e x86. O Linux roda em tudo, desde meu grande honkin 'System z no trabalho a um pequeno relógio de pulso insignificante .

Se a CPU fornece qualquer tipo de escolha, a convenção de chamada / ABI usada pelo sistema operacional especifica qual escolha você precisa fazer se quiser que seu código chame o código de todos os outros.

Os processadores e sua direção são:

  • x86: inativo.
  • SPARC: selecionável. O ABI padrão usa para baixo.
  • PPC: para baixo, eu acho.
  • System z: em uma lista vinculada, não estou brincando (mas ainda assim, pelo menos para zLinux).
  • ARM: selecionável, mas Thumb2 tem codificações compactas apenas para baixo (LDMIA = incremento depois, STMDB = decremento antes).
  • 6502: inativo (mas apenas 256 bytes).
  • RCA 1802A: da maneira que você quiser, sujeito a implementação de SCRT.
  • PDP11: para baixo.
  • 8051: up.

Mostrando minha idade nesses últimos, o 1802 foi o chip usado para controlar os primeiros lançadores (detectando se as portas estavam abertas, eu suspeito, com base no poder de processamento que tinha :-) e meu segundo computador, o COMX-35 ( seguindo meu ZX80 ).

Detalhes do PDP11 coletados a partir daqui , 8051 detalhes a partir daqui .

A arquitetura SPARC usa um modelo de registro de janela deslizante. Os detalhes arquitetonicamente visíveis também incluem um buffer circular de janelas de registro que são válidas e armazenadas em cache internamente, com armadilhas quando há over / underflows. Veja aqui os detalhes. Como o manual SPARCv8 explica , as instruções SAVE e RESTORE são como instruções ADD mais a rotação da janela de registro. Usar uma constante positiva em vez da negativa usual resultaria em uma pilha crescente.

A técnica SCRT mencionada anteriormente é outra - o 1802 usava alguns ou seus dezesseis registradores de 16 bits para SCRT (técnica de chamada e retorno padrão). Um era o contador do programa, você poderia usar qualquer registro como o PC com a SEP Rninstrução. Um era o ponteiro da pilha e dois eram definidos sempre para apontar para o endereço do código SCRT, um para chamada e um para retorno. Nenhum registro foi tratado de forma especial. Lembre-se de que esses detalhes são de memória, eles podem não estar totalmente corretos.

Por exemplo, se R3 era o PC, R4 era o endereço de chamada SCRT, R5 era o endereço de retorno SCRT e R2 era a "pilha" (aspas conforme implementado no software), SEP R4definiria R4 como o PC e iniciaria a execução do SCRT código de chamada.

Em seguida, ele armazenaria R3 na "pilha" de R2 (acho que R6 foi usado para armazenamento temporário), ajustando-o para cima ou para baixo, pegaria os dois bytes seguintes a R3, carregaria em R3 SEP R3e executaria e executaria no novo endereço.

Para retornar, ele iria SEP R5puxar o endereço antigo da pilha R2, adicionar dois a ele (para pular os bytes de endereço da chamada), carregá-lo em R3 e SEP R3começar a executar o código anterior.

Muito difícil de entender inicialmente depois de todo o código baseado em pilha 6502/6809 / z80, mas ainda elegante de uma forma tipo "bang-sua-cabeça-contra-a-parede". Além disso, uma das características de maior venda do chip foi um conjunto completo de 16 registradores de 16 bits, apesar do fato de você ter perdido imediatamente 7 deles (5 para SCRT, dois para DMA e interrupções da memória). Ahh, o triunfo do marketing sobre a realidade :-)

O System z é bastante semelhante, usando seus registradores R14 e R15 para chamada / retorno.

paxdiablo
fonte
3
Para adicionar à lista, ARM pode crescer em qualquer direção, mas pode ser definido para uma ou outra por uma implementação de silício particular (ou pode ser selecionado à esquerda por software). Os poucos com os quais lidei sempre estiveram em modo de crescimento.
Michael Burr de
1
No pequeno mundo ARM que vi até agora (ARM7TDMI), a pilha é inteiramente controlada por software. Os endereços de retorno são armazenados em um registro que é salvo pelo software se necessário, e as instruções pré / pós-incremento / decremento permitem colocá-lo e outras coisas na pilha em qualquer direção.
starblue
1
Com o HPPA, a pilha cresceu! Bastante raro entre arquiteturas razoavelmente modernas.
tml
2
Para os curiosos, aqui está um bom recurso sobre como a pilha funciona no z / OS: www-03.ibm.com/systems/resources/Stack+and+Heap.pdf
Dillon Cower
1
Obrigado @paxdiablo pela sua compreensão. Às vezes, as pessoas acham que é uma afronta pessoal quando você faz esse comentário, especialmente quando é mais antigo. Só sei que há uma diferença porque cometi o mesmo erro no passado. Cuidar.
CasaDeRobison
23

Em C ++ (adaptável a C) stack.cc :

static int
find_stack_direction ()
{
    static char *addr = 0;
    auto char dummy;
    if (addr == 0)
    {
        addr = &dummy;
        return find_stack_direction ();
    }
    else
    {
        return ((&dummy > addr) ? 1 : -1);
    }
}
jfs
fonte
14
Uau, já faz muito tempo que não vejo a palavra-chave "auto".
paxdiablo
9
(& dummy> addr) é indefinido. O resultado de alimentar dois ponteiros para um operador relacional é definido apenas se os dois ponteiros apontam para a mesma matriz ou estrutura.
sigjuice
2
Tentar investigar o layout de sua própria pilha - algo que C / C ++ não especifica de forma alguma - é "não portável" para começar, então eu realmente não me importaria com isso. Parece que essa função só funcionará corretamente uma vez.
efêmero
9
Não há necessidade de usar um staticpara isso. Em vez disso, você pode passar o endereço como um argumento para uma chamada recursiva.
R .. GitHub PARAR DE AJUDAR O ICE
5
além disso, usando um static, se você chamar isso mais de uma vez, as chamadas subsequentes podem falhar ...
Chris Dodd
7

A vantagem de diminuir o crescimento é que, em sistemas mais antigos, a pilha ficava normalmente no topo da memória. Os programas normalmente enchiam a memória começando da parte inferior, portanto, esse tipo de gerenciamento de memória minimizava a necessidade de medir e colocar a parte inferior da pilha em algum lugar adequado.

mP.
fonte
3
Não é uma 'vantagem', na verdade uma tautologia.
Marquês de Lorne,
1
Não é uma tautologia. O objetivo é ter duas regiões de memória crescente não interferindo (a menos que a memória esteja cheia), como @valenok apontou.
YvesgereY
6

A pilha diminui em x86 (definido pela arquitetura, ponteiro de pilha de incrementos de pop, decrementos de push).

Michael
fonte
5

Em MIPS e em muitas arquiteturas RISC modernas (como PowerPC, RISC-V, SPARC ...) não há instruções pushe pop. Essas operações são feitas explicitamente ajustando manualmente o ponteiro da pilha e depois carrega / armazena o valor em relação ao ponteiro ajustado. Todos os registradores (exceto o registrador zero) são de propósito geral, então em teoria qualquer registrador pode ser um ponteiro de pilha, e a pilha pode crescer em qualquer direção que o programador desejar

Dito isso, a pilha geralmente diminui na maioria das arquiteturas, provavelmente para evitar o caso em que a pilha e os dados do programa ou os dados do heap aumentam e colidem entre si. Há também os grandes motivos de endereçamento mencionados na resposta de sh- . Alguns exemplos: MIPS ABIs cresce para baixo e usa $29(AKA $sp) como o ponteiro da pilha, RISC-V ABI também cresce para baixo e usa x2 como o ponteiro da pilha

No Intel 8051, a pilha cresce, provavelmente porque o espaço de memória é tão pequeno (128 bytes na versão original) que não há heap e você não precisa colocar a pilha no topo para que seja separada do crescente heap Do fundo

Você pode encontrar mais informações sobre o uso da pilha em várias arquiteturas em https://en.wikipedia.org/wiki/Calling_convention

Veja também

phuclv
fonte
2

Apenas um pequeno acréscimo às outras respostas, que até onde posso ver não tocaram neste ponto:

Ter a pilha crescendo para baixo faz com que todos os endereços dentro da pilha tenham um deslocamento positivo em relação ao ponteiro da pilha. Não há necessidade de deslocamentos negativos, pois eles apontariam apenas para o espaço de pilha não utilizado. Isso simplifica o acesso aos locais da pilha quando o processador suporta endereçamento relativo ao ponteiro da pilha.

Muitos processadores têm instruções que permitem acessos com um deslocamento apenas positivo em relação a algum registro. Isso inclui muitas arquiteturas modernas, bem como algumas antigas. Por exemplo, o ARM Thumb ABI fornece acessos relativos ao ponteiro da pilha com um deslocamento positivo codificado em uma única palavra de instrução de 16 bits.

Se a pilha crescesse para cima, todos os deslocamentos úteis relativos ao ponteiro da pilha seriam negativos, o que é menos intuitivo e menos conveniente. Também está em desacordo com outras aplicações de endereçamento relativo a registradores, por exemplo, para acessar campos de uma estrutura.

sh-
fonte
2

Na maioria dos sistemas, a pilha diminui e meu artigo em https://gist.github.com/cpq/8598782 explica POR QUE ela diminui. É simples: como fazer o layout de dois blocos de memória crescentes (heap e pilha) em um bloco fixo de memória? A melhor solução é colocá-los nas extremidades opostas e deixar crescer um em direção ao outro.

Valenok
fonte
essa essência parece estar morta agora :(
Ven
@Ven - Eu posso chegar lá
Brett Holman
1

Ele diminui porque a memória alocada para o programa tem os "dados permanentes", ou seja, o código do próprio programa na parte inferior e a pilha no meio. Você precisa de outro ponto fixo a partir do qual fazer referência à pilha, de modo que você fique no topo. Isso significa que a pilha diminui até ficar potencialmente adjacente aos objetos no heap.

Kai
fonte
0

Esta macro deve detectá-lo em tempo de execução sem UB:

#define stk_grows_up_eh() stk_grows_up__(&(char){0})
_Bool stk_grows_up__(char *ParentsLocal);

__attribute((__noinline__))
_Bool stk_grows_up__(char *ParentsLocal) { 
    return (uintptr_t)ParentsLocal < (uintptr_t)&ParentsLocal;
}
PSkocik
fonte