Stack overflow

Em software, um estouro de pilha ocorre se o ponteiro de pilha de chamadas exceder o limite de pilha. A pilha de chamadas pode consistir em uma quantidade limitada de espaço de endereçamento, geralmente determinado no início do programa. O tamanho da pilha de chamadas depende de muitos fatores, incluindo a linguagem de programação, arquitetura da máquina, multithreading e quantidade de memória disponível. Quando um programa tenta usar mais espaço do que o disponível na pilha de chamadas (ou seja, quando tenta acessar a memória além dos limites da pilha de chamadas, que é essencialmente um estouro de buffer), a pilha é chamada de "estouro", normalmente resultando em uma falha do programa.^[1]

Causas[editar | editar código-fonte]

Recursão infinita[editar | editar código-fonte]

A causa mais comum de estouro de pilha é a recursão excessivamente profunda ou infinita, na qual uma função chama a si mesma tantas vezes que o espaço necessário para armazenar as variáveis e informações associadas a cada chamada é mais do que pode caber na pilha.^[2]

Um exemplo de recursão infinita em C.

int foo()
{
 return foo();
}

A função foo, quando é invocada, continua a invocar a si mesma, alocando espaço adicional na pilha a cada vez, até que a pilha transborde resultando em uma falha de segmentação.^[2] No entanto, alguns compiladores implementam otimização de chamada final, permitindo que a recursão infinita de uma recursão final de classificação específica ocorra sem estouro de pilha. Isso funciona porque as chamadas de recursão final não ocupam espaço de pilha adicional.^[3]

Algumas opções do compilador C irão efetivamente habilitar otimização da chamada final; por exemplo, compilar o programa simples acima usando gcc com -O1 resultará em uma falha de segmentação, mas não ao usar -O2 ou -O3, uma vez que esses níveis de otimização implicam na opção do compilador -foptimize-sibling-calls.^[4] Outras linguagens, como Scheme, exigem que todas as implementações incluam a recursão final como parte do padrão da linguagem.^[5]

Recursão muito profunda[editar | editar código-fonte]

Uma função recursiva que termina em teoria, mas causa um estouro do buffer da pilha de chamadas na prática, pode ser corrigida transformando a recursão em um loop e armazenando os argumentos da função em uma pilha explícita (em vez do uso implícito da pilha de chamadas). Isso sempre é possível, porque a classe de funções recursivas primitivas é equivalente à classe de funções computáveis LOOP. Considere este exemplo em C++ - como pseudocódigo:


void function (argument) { if (condition) function (argument.next); }	stack.push(argument); while (!stack.empty()) { argument = stack.pop(); if (condition) stack.push(argument.next); }

Uma função recursiva primitiva como a do lado esquerdo pode sempre ser transformada em um loop como a do lado direito.

Uma função como o exemplo acima à esquerda não seria um problema em um ambiente com suporte a otimização de chamada final; no entanto, ainda é possível criar uma função recursiva que pode resultar em um estouro de pilha nessas linguagens. Considere o exemplo abaixo de duas funções de exponenciação de número inteiro simples.

int pow(int base, int exp) {
 if (exp > 0)
 return base * pow(base, exp - 1);
 else
 return 1;
}

int pow(int base, int exp) {
 return pow_accum(base, exp, 1);
}

int pow_accum(int base, int exp, int accum) {
 if (exp > 0)
 return pow_accum(base, exp - 1, accum * base);
 else
 return accum;
}

Ambas as funções pow(base, exp) acima calculam um resultado equivalente, no entanto, a da esquerda está propensa a causar um estouro de pilha porque a otimização de chamada final não é possível para esta função. Durante a execução, a pilha para essas funções terá a seguinte aparência:

pow(5, 4)
5 * pow(5, 3)
5 * (5 * pow(5, 2))
5 * (5 * (5 * pow(5, 1)))
5 * (5 * (5 * (5 * pow(5, 0))))
5 * (5 * (5 * (5 * 1)))
625

pow(5, 4)
pow_accum(5, 4, 1)
pow_accum(5, 3, 5)
pow_accum(5, 2, 25)
pow_accum(5, 1, 125)
pow_accum(5, 0, 625)
625

Observe que a função à esquerda deve armazenar em sua pilha um número de exp inteiros, que será multiplicado quando a recursão terminar e a função retornar 1. Em contraste, a função à direita deve armazenar apenas 3 inteiros a qualquer momento e computar um resultado intermediário que é passado para sua próxima invocação. Como nenhuma outra informação fora da chamada de função atual deve ser armazenada, um otimizador de recursão final pode "descartar" os frames de pilha anteriores, eliminando a possibilidade de um estouro de pilha.

Variáveis de pilha muito grandes[editar | editar código-fonte]

A outra causa principal de um estouro de pilha resulta de uma tentativa de alocar mais memória na pilha do que caberia, por exemplo, criando variáveis de array locais que são muito grandes. Por esta razão, alguns autores recomendam que arrays maiores que alguns kilobytes sejam alocados dinamicamente em vez de como uma variável local.^[6]

Um exemplo de uma variável de pilha muito grande em C:

int foo()
{
 double x[1048576];
}

Em uma implementação C com flutuantes de precisão dupla de 8 bytes, a matriz declarada consome 8 megabytes de dados; se isto for mais memória do que a disponível na pilha (conforme definido pelos parâmetros de criação de thread ou limites do sistema operacional), ocorrerá um estouro de pilha.

Os estouros de pilha são agravados por qualquer coisa que reduza o tamanho efetivo da pilha de um determinado programa. Por exemplo, o mesmo programa executado sem vários threads pode funcionar bem, mas assim que o multi-threading for ativado, o programa irá travar. Isso ocorre porque a maioria dos programas com threads têm menos espaço na pilha por thread do que um programa sem suporte a threads. Como os kernels são geralmente multi-threaded, pessoas novas no desenvolvimento do kernel geralmente são desencorajadas de usar algoritmos recursivos ou grandes buffers de pilha.^[7]