Stack (ou pilha) é uma estrutura de dados do tipo LIFO (last-in-first-out), ou seja, o último elemento a entrar na pilha é o primeiro a sair.

Para o compilador, o stack é uma região para armazenamento de dados temporários, como retornos de função e variáveis locais. O stack pode ser implementado através de registradores específicos na CPU (também chamado de hardware stack) ou pode ser implementado em RAM.

O primeiro microprocessador, o Intel 4004, possuia um hardware stack de 3 níveis (podia armazenar até 3 retornos de função). Seu sucessor, o 8008, aumentou o stack para 7 níveis. Os microcontroladores PIC (com exceção do PIC32), também trabalham com hardware stacks, sendo que a quantidade de níveis suportados depende do modelo do PIC. 

Já a maioria dos microprocessadores e microcontroladores atuais trabalham com o stack em RAM, dentre eles x86, ARM, MIPS, AVR e 8051 (salvo algumas exceções, onde o compilador usa registradores para salvar dados temporários, por questões de otimização e performance).

Apesar de apresentar aqui conceitos genéricos que possam ser aplicados também em arquiteturas que usam hardware stack, meu foco aqui é o stack implementado em RAM.

O stack na RAM normalmente possui um endereço fixo de origem, e um tamanho que pode variar de acordo com sua utilização. São usadas operações do tipo PUSH para inserir um byte no stack, e POP para remover um byte do STACK. Dependendo da arquitetura do hardware, o stack pode crescer para cima (de endereços menores para endereços maiores) ou para baixo (de endereços maiores para endereços menores) na RAM, e normalmente a posição atual do stack (também chamada de topo do stack) é representada por um registrador chamado Stack Pointer.

Por exemplo, imagine um stack que começa no endereço 100h e que cresce para baixo. Se a CPU receber uma instrução do tipo PUSH A5h, o byte A5h será armazenado no endereço 100h, e o Stack Pointer será decrementado para FFh. Neste momento o tamanho do stack é de 1 byte. Se a CPU receber outra instrução do tipo PUSH, o Stack Pointer será decrementado novamente para FEh, e o tamanho do Stack será de 2 bytes. Da mesma forma, se a CPU receber uma instrução do tipo POP, o Stack Pointer seré incrementando para FFh, removendo aquele byte da pilha. 

Quando trabalhamos diretamente com Assembly, temos uma visão melhor da utilização do stack, já que temos controle sobre as chamadas à PUSH e POP. Mas quando desenvolvemos em C, tudo isso fica transparente para o programador. 

Um compilador C pode utilizar o stack para salvar o endereço de retorno de funções, bem como seus parâmetros e seu retorno. Além disso, o stack também é usado para salvar variáveis automáticas (locais). Dependendo da disponibilidade de registradores, o compilador também pode usar o stack para armazenar operandos e resultados intermediários em determinadas operações aritméticas. Rotinas de tratamento de interrupção podem usar o stack para salvar o status atual dos registradores ao interromper determinada tarefa. E quando trabalhamos com um RTOS, o consumo do stack pode aumentar mais ainda, já que ele pode alocar uma parte do stack para cada tarefa instanciada.

Portanto, é essencial entender como o compilador gera o código, e o uso que ele faz do stack. Caso contrário, podemos cair num problema chamado stack overflow, onde ultrapassamos os limites máximos da pilha e sobrescrevemos indevidamente outras regiões de memória.

Precisamos também saber o quanto do stack nossa aplicação esta usando, através de métodos mais confiáveis do que o famoso “chutômetro”. Além disso, precisamos ter um controle do stack em tempo de execução, para se antecipar a possíveis problemas de stack overflow.

CUIDADOS COM A LINGUAGEM C

O inimigo número 1 do stack são as funções recursivas (quando uma função chama ela mesma). Dependendo da função e da quantidade de chamadas, e stack pode ser consumido de forma muito rápida. É por isso que padrões como o MISRA-C impedem o uso de funções deste tipo. Portanto, evite sempre o uso de algoritmos com funções recursivas, como o exemplo abaixo:

1
2
3
4
5
6
7

unsigned int fatorial(unsigned int n)
{
    if (n <= 1)
        return 1;
    else
        return n * fatorial(n - 1);
}

O recurso de funções inline é uma boa técnica para economizar o stack, ao mesmo tempo em que melhora a performance da aplicação (mas pode aumentar o tamanho do código). A função somaVetor() abaixo é um exemplo do uso de funções inline.

1
2
3
4
5
6
7
8
9
10
11
12
13

#define MAX_BUF 5
 
inline unsigned int soma(unsigned int a, unsigned int b);
 
unsigned int somaVetor(char buf[])
{
    unsigned int i, total = 0;
 
    for (i = 0; i < MAX_BUF; i++)
         total = soma(total, buf[i]);
 
    return total;
}

Lembrando que funções inline fazem parte do padrão C99, e devem estar disponíveis na maioria dos compiladores. Mas se você quiser compatibilidade com a especificação C89, pode implementar a função soma() usando uma macro (tomando sempre o devido cuidado com macros, conforme escrevi neste meu artigo aqui).

Sempre que possível, passe parâmetros de funções por referência. Passando parâmetros por valor, todo o conteúdo será copiado para o stack, e se você estiver trabalhando com estruturas muito grandes, pode causar um stack overflow.

No exemplo abaixo, a função readBuffer1() recebe o parâmetro por valor, e vai precisar alocar 2K para salvar a estrutura bigbuf. Já a função readBuffer2() precisa somente de 4 bytes (em uma arquitetura de 32 bits), pois apenas o ponteiro para a estrutura é armazenado no stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void readBuffer1(struct BB bigbuf);   // recebendo por valor
 
void readBuffer2(struct BB *bigbuf);  // recebendo por referencia
 
struct BB {
    char buf[2048];
} bigbuf;
 
int read()
{
    readBuffer1(bigbuf);   // passando por valor
 
    readBuffer2(&bigbuf);  // passando por referencia
}

Variáveis locais são outro problema para o stack. Às vezes abusamos do tamanho de buffers locais sem perceber que estamos consumindo muito espaço do stack. No exemplo abaixo, a função send() vai consumir 4K do stack só para armazenar a variável buf.

1
2
3
4
5
6

int send()
{
    char buf[4096];
 
    ....
}

Na segunda parte, vamos estudar métodos de cálculo do tamanho necessário do stack para a aplicação, e como podemos monitorá-lo para evitar problemas de stack overflow.

Até lá!

Sergio Prado