Na primeira parte deste artigo falei sobre os conceitos de pilha, como o compilador gera o código e usa o stack, e dei alguns exemplos de como minimizar seu uso em código desenvolvido em linguagem C.

Agora vamos estudar algumas metodologias para calcular o tamanho do stack necessário por determinada aplicação.

CALCULANDO O USO DO STACK

Qual o tamanho do stack necessário para sua aplicação? Vamos desperdiçar muita memória alocando um espaço bem grande para o stack, ou iremos alocar um espaço mais reduzido, e correr o risco de um stack overflow?

Não é fácil responder à estas perguntas. Não existe receita de bolo, e muito menos um caminho das pedras.

O tamanho do stack depende de muitas variáveis e eventos assíncronos, como chamadas aninhadas de funções, tamanho de variáveis automáticas, chamadas à funções do sistema operacional, bibliotecas e interrupções. E o problema vai ficando cada vez pior conforme aumentamos a complexidade e a quantidade de linhas de código.

Para analisar então o tamanho do stack necessário pela aplicação, também chamado de profundidade do stack, podemos usar dois tipos de técnicas: análise estática de código e análise dinâmica de código – cada uma com seus prós e contras. Vamos dar uma olhada melhor nestas técnicas.

ANÁLISE ESTÁTICA

O objetivo da análise estática é calcular a profundidade máxima alcançada pelo stack, varrendo o código-fonte (ou arquivo binário) da aplicação, passando por cada caminho dentro das chamadas de função e interrupção, contabilizando basicamente as instruções de PUSH e POP.

Usar os fontes da aplicação não é uma técnica muito recomendada por diversos fatores, dentre eles:

1. É muito mais complicado fazer a análise sintática e semântica do código-fonte do que interpretar e converter o arquivo binário em mnemônicos assembly. Quem já desenvolveu ou trabalhou com compiladores sabe como esta tarefa é complexa.
2. A análise fica incompleta se o código-fonte do sistema operacional e de bibliotecas não estiverem disponíveis.
3. É difícil prever o que o compilador fará com o código-fonte. Por exemplo, uma chamada de função, que poderia gerar algumas instruções de PUSH, pode ser otimizada pelo compilador para uma função inline, não gerando nenhuma instrução de PUSH.

O ideal então é usar o binário final para fazer esta análise. Mas isso não deixa a solução mais fácil.

A ferramenta precisa lidar com problemas como ponteiros dinâmicos de função, funções recursivas, funções de callback, etc. As interrupções também são outro problema, já que são eventos assíncronos. Como prever quais interrupções irão acontecer, e quando? Quantas interrupções ao mesmo tempo? Elas são reentrantes?

Mesmo com todos esses desafios, existem ferramentas que tentam chegar num valor aproximado de utilização do stack.

O Stacktool foi desenvolvido pelo John Regehr para fins educacionais. Esta ferramenta é um script em Perl que analisa o binário de uma aplicação desenvolvida para microcontroladores AVR. A saída do programa parece interessante (clique na figura para vê-la em tamanho maior):

Outra ferramenta interessante, o Stack Analyser da AbsInt também promete o mesmo resultado, com um ambiente gráfico e suporte à diversas arquiteturas como PowerPC, HC12/HCS12, ARM, M68k, TMS320C3x/Texas, etc.

ANÁLISE DINÂMICA

O objetivo desta técnica é analisar o código dinamicamente em tempo de execução. Você pode adotar duas soluções:

1. Preencher o stack com uma “palavra mágica”.

Esta solução consiste em preencher e monitorar os valores do stack com uma ferramenta de debugger. No boot do seu código, antes da função main, desenvolva uma função que preencha todo o stack com um conjunto de caracteres, por exemplo “STACK123”. Um dump do stack no boot ficaria mais ou menos assim:

00001000   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001010   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001020   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001030   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001040   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001050   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001060   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001070   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123

Agora execute sua aplicação e realize testes completos, forçando inclusive a geração de eventos assíncronos como interrupções. Teste durante bastante tempo, simulando o comportamento real da aplicação. Finalizados os testes, tire outro dump do stack:

00001000   FF 02 05 09  12 01 01 03  08 DE A7 C3  C9 F3 04 E9  ................
00001010   03 08 DE A7  C3 C9 F3 04  E9 09 12 01  01 03 C9 F3  ................
00001020   F3 04 E9 09  4B 31 32 33  53 54 41 43  4B 31 32 33  ....K123STACK123
00001030   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001040   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001050   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001060   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123
00001070   53 54 41 43  4B 31 32 33  53 54 41 43  4B 31 32 33  STACK123STACK123

Os bytes com os caracteres alterados indicam a região do stack usada pela aplicação. Veja que neste exemplo 36 bytes foram consumidos do stack.

2. Monitorar o stack pointer

Se você não tiver um debugger para tirar dumps do stack, você pode desenvolver uma função que monitore o conteúdo do Stack Pointer e armazene o maior valor. Exemplo:

1
2
3
4
5
6
7

volatile int stackDepth = 0;
 
void stackMonitor()
{
    if (stackDepth < STACK_POINTER)
        stackDepth = STACK_POINTER;
}

Coloque esta função para ser executada em um timer do sistema na menor resolução possível. E crie uma forma de visualizar este valor, através de um display, ou transmitindo por uma interface de comunicação.

QUAL A MELHOR SOLUÇÃO?

Depende! 

Na análise estática, sempre será considerado o pior dos cenários. Se uma interrupção é reentrante, a análise pode chegar a conclusão de que o stack usado será infinito! Ou seja, prevendo os piores caminhos (dentre eles os improváveis e os impossíveis), esta técnica poderá sugerir um tamanho de stack maior do que o necessário, desperdiçando memória RAM. Por outro lado, este método é mais rápido e seguro.

Na análise dinâmica, o resultado poderá estar mais próximo do real. Porém, dependendo do tamanho do programa, você pode não conseguir simular todos os caminhos possíveis, e o stack pode não ser estimado corretamente. É mais dificil também prever eventos assíncronos como interrupções. Existe então um risco de subestimar o valor necessário para o stack, correndo o risco de Stack Overflow.

Na prática, use os dois métodos. Considere um valor para o stack que esteja entre os valores encontrados na análise estática e na analise dinâmica.

Análise estática > Tamanho do Stack > Análise Dinâmica

Dependendo do seu projeto, pode ser que não exista uma ferramenta de análise estática no mercado. E desenvolver uma também pode estar fora dos seus planos. Neste caso, quando temos apenas a análise dinâmica como parâmetro, adicione à sua medida uma margem de segurança de mais ou menos 30%. Por exemplo, se você mediu o uso de 100 bytes no stack, configure-o com 130 bytes.

É claro que não existe nada científico que comprove o uso desta margem de segurança de 30%. Poderia ser 20%, 40% ou mesmo 100%! Tudo vai depender do nível de confiança (e paranóia) que você tem nos testes que executou. A decisão da quantidade de bytes a serem alocados para o stack será sempre um trade-off entre a economia de memória RAM e o risco de acontecer um stack overflow.

PROTEGENDO O STACK

Se você tiver sorte, terá em mãos uma CPU com MMU (Memory Management Unit). Neste caso, configure na MMU uma região para o stack e proteja as áreas acima e abaixo desta região alocada para o stack. Qualquer acesso fora do stack causará uma exceção que poderá ser tratada por software.

Com um debugger conectado ao equipamento, você pode identificar em qual chamada o stack overflow aconteceu. Fica muito mais fácil de identificar, analisar e resolver o problema.

MAIS UMA VEZ, USE FERRAMENTAS

Sempre ressalto aqui a importância de aproveitar as funcionalidades das ferramentas que usamos no dia-a-dia.

O ambiente de desenvolvimento da IAR possui um plugin para analisar o stack que usa uma técnica parecida com a descrita na primeira solução de análise dinâmica, preenchendo o stack com 0xCD e monitorando-o durante a execução do programa. Se chegar a um limite pré-definido pelo usuário (90% por exemplo) irá avisar.

Já o µVision Simulator da Keil usa a técnica descrita na segunda solução da análise dinâmica, monitorando o valor máximo do stack pointer e armazenando em uma variável chamada sp_max. A responsabilidade de analisar esta variável e ajustar o stack é do desenvolvedor.

Você deve ter percebido que a análise do uso do stack é um problema sem uma solução simples. O ideal é unir um conjunto de técnicas, ferramentas e bom senso.

Se você conhece mais alguma técnica ou ferramenta, deixe seus comentários!

Um abraço,

Sergio Prado.