Desbordament de la pila

Imatge que mostra la pila del programa abans del desbordament de la memòria intermèdia.

Al programari, es produeix un desbordament de la pila si el punter de la pila de crides supera el límit de la pila. La pila de crides pot consistir en una quantitat limitada d' espai d'adreces, sovint determinada a l'inici del programa. La mida de la pila de crides depèn de molts factors, com ara el llenguatge de programació, l'arquitectura de la màquina, el multiprocés i la quantitat de memòria disponible. Quan un programa intenta utilitzar més espai del que hi ha disponible a la pila de crides (és a dir, quan intenta accedir a la memòria més enllà dels límits de la pila de crides, que és essencialment un desbordament de memòria intermèdia), es diu que la pila es desborda, la qual cosa normalment resulta en un bloqueig del programa.

Imatge que mostra la pila de programes amb dades normals i sense desbordament.

Causes

Recursió infinita

La causa més comuna del desbordament de la pila és la recursivitat excessivament profunda o infinita, en què una funció s'anomena a si mateixa tantes vegades que l'espai necessari per emmagatzemar les variables i la informació associada a cada crida és més del que pot cabre a la pila.

Un exemple de recursivitat infinita en C:

int foo() 
{
   return foo();
}

La funció foo, quan s'invoca, continua invocant-se a si mateixa, assignant espai addicional a la pila cada vegada, fins que la pila es desborda provocant un error de segmentació. Tanmateix, alguns compiladors implementen l'optimització de la crida a la cua, permetent que es produeixi una recursió infinita d'un tipus específic— recursivitat de la cua— sense desbordament de la pila. Això funciona perquè les crides de recursivitat a la cua no ocupen espai de pila addicional.

Algunes opcions del compilador C permetran efectivament l'optimització de la crida de cua ; per exemple, compilar el programa senzill anterior amb gcc amb -O1 donarà lloc a un error de segmentació, però no quan s'utilitza -O2 o -O3, ja que aquests nivells d'optimització impliquen l'opció del compilador -foptimize-sibling-calls. Altres idiomes, com Scheme, requereixen que totes les implementacions incloguin la recurrència de la cua com a part de l'estàndard lingüístic.

Recursivitat molt profunda

Una funció recursiva que acaba en teoria però provoca un desbordament de memòria intermèdia de la pila de crides a la pràctica es pot solucionar transformant la recursivitat en un bucle i emmagatzemant els arguments de la funció en una pila explícita (en lloc de l'ús implícit de la pila de crides). Això sempre és possible perquè la classe de funcions recursives primitives és equivalent a la classe de funcions computables LOOP. Considereu aquest exemple en pseudocodi semblant a C++:

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

Imatge que mostra la pila del programa després del desbordament de la memòria intermèdia.

Una funció recursiva primitiva com la del costat esquerre sempre es pot transformar en un bucle com al costat dret.

Una funció com l'exemple anterior a l'esquerra no seria un problema en un entorn que suporti l'optimització de la crida de cua; no obstant això, encara és possible crear una funció recursiva que pot provocar un desbordament de la pila en aquests idiomes. Considereu l'exemple següent de dues funcions simples d'exponenciació de nombres enters.

Variables de pila molt grans

L'altra causa principal d'un desbordament de la pila resulta d'un intent d'assignar més memòria a la pila de la que s'adapta, per exemple, creant variables de matriu locals massa grans. Per aquest motiu, alguns autors recomanen que les matrius més grans d'uns pocs kilobytes s'assignin dinàmicament en comptes de ser una variable local.