La pile d’appels : cadres, adresses de retour et débordements

Appeler une fonction, c’est effectuer quelques écritures en mémoire. En revenir, c’est sauter à une adresse relue dans cette mémoire. Exécutez pas à pas l’un des quatre petits programmes et observez la pile, où les adresses les plus élevées figurent en haut. Les écritures apparaissent en ambre, les lectures en bleu. Les emplacements d’un cadre dépilé restent visibles, en atténué : leur contenu n’a pas été effacé.

Exemple résolu — La pile d’appels : cadres, adresses de retour et débordements

Nombre d’appels	5
Nombre maximal de cadres empilés	5
Occupation maximale de la pile	60 octets sur 128
Résultat	120

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — La pile d’appels : cadres, adresses de retour et débordements

La pile d’appels est une zone de mémoire où chaque appel de fonction dispose d’un cadre. Celui-ci contient ici l’argument, l’adresse de retour, où la fonction appelante reprendra son exécution, le pointeur de cadre sauvegardé de cette fonction et les variables locales. Le pointeur de pile indique la plus basse adresse utilisée. Un appel le fait descendre de la taille d’un cadre ; un retour le fait remonter. Une récursion de profondeur d, avec des cadres de f octets, occupe d·f octets dans la pile.

Ce que signifie chaque symbole

d: la profondeur : le nombre de cadres présents simultanément dans la pile
f: la taille d’un cadre en octets : ici 12, plus 4 par variable locale

Suppose: Le modèle représente une machine 32 bits avec une convention d’appel classique du C : des emplacements de 4 octets, une pile qui croît vers les adresses basses, des arguments transmis par la pile et un pointeur de cadre conservé dans chaque cadre. Les conventions d’appel des machines 64 bits transmettent les premiers arguments dans des registres. Les compilateurs peuvent omettre le pointeur de cadre. Sur ARM, une fonction qui n’en appelle aucune autre peut conserver son adresse de retour dans un registre. La taille et l’organisation des cadres réels peuvent donc différer de ce modèle à trois emplacements.

L’adresse de retour est un nombre en mémoire qu’un tableau peut écraser 🖖

Cliquez sur Six dans quatre. Le tableau buf de copy peut contenir quatre int. Comme buf[0] occupe l’adresse la plus basse, buf[4] et buf[5] correspondent simplement aux deux emplacements suivants, vers le haut. L’appel y a placé le pointeur de cadre sauvegardé, puis l’adresse de retour. La boucle ne vérifie jamais son indice : la cinquième valeur remplace le pointeur de cadre et la sixième, 0x46464646, remplace l’adresse de retour. À la fin de copy, le processeur lit cet emplacement et saute à l’adresse qu’il contient. Avec quatre valeurs, l’exécution reprend à 0x08048400, comme prévu. Avec cinq, elle reprend encore à cette adresse, mais main récupère un pointeur de cadre corrompu. Il s’agit d’un débordement de tampon dans la pile. En novembre 1988, le ver Morris a exploité cette faille dans fingerd : ce programme lisait son entrée dans un tampon de 512 octets sans limiter la quantité de données lues.

Une variable non initialisée conserve ce que l’appel précédent a laissé 🖖

Cliquez sur Valeur laissée en mémoire. set écrit 42 dans sa variable locale, puis se termine. Le pointeur de pile remonte sans que rien soit effacé. peek est ensuite appelée depuis le même endroit : son cadre occupe les mêmes adresses et sa variable locale y se trouve à l’adresse 1008, exactement à la place de x. peek n’écrit jamais dans y ; sa lecture renvoie donc 42. En C, lire une variable non initialisée relève du comportement indéfini. Le langage ne garantit aucun résultat, et un compilateur qui optimise le programme peut même supprimer cette lecture en mémoire. Si la lecture a effectivement lieu, elle retrouve le contenu laissé par la dernière écriture à cette adresse.

La pile contient une seule chaîne d’appels 🖖

Réglez n sur 10 pour fib. La fonction effectue 177 appels, mais la pile contient au maximum 10 cadres, soit 120 octets. Le cadre d’un appel est dépilé avant que celui de l’appel suivant, au même niveau, soit empilé. À tout instant, la pile contient donc la chaîne qui relie fib(10) à l’appel en cours. fact(11) effectue 11 appels, environ seize fois moins, et déborde : sa chaîne de 11 cadres exige 132 octets. Dans ces deux fonctions, chaque appel accomplit une quantité fixe de travail en dehors de ses appels récursifs. Le nombre d’appels mesure donc le temps d’exécution ; la profondeur de la plus longue chaîne détermine l’espace occupé dans la pile.

Problème entièrement résolu

Jusqu’à quelle profondeur peut-on aller en récursion ? 4 étapes
Cliquez sur fact(11) déborde. La pile de cette page contient 128 octets. Par défaut, l’éditeur de liens de Microsoft réserve 1 Mo de pile à un programme. Prenez ici 1 Mio, soit 1 048 576 octets, avec les cadres de cette page. Quelle profondeur fact peut-elle atteindre ? Et si chaque appel possède en plus une variable locale de 4 octets ? Enfin, combien d’espace fib(30) occupe-t-elle dans la pile, pour combien d’appels ?

Ouvrez ce problème dans l'outil
1. Un cadre contient ici un argument, une adresse de retour et un pointeur de cadre sauvegardé : 3 × 4 = 12 octets. Comme 128 / 12 = 10,67, la pile peut accueillir 10 cadres. fact(11) exige 11 × 12 = 132 octets. Le tableau des résultats indique le débordement.
  
  $f = 3 \times 4 = 12, ⌊ \frac{128}{12} ⌋ = 10, 11 \times 12 = 132 > 128$
2. 1 048 576 / 12 = 87 381,33 : la pile peut accueillir 87 381 cadres. fact pourrait donc atteindre 87 381 niveaux de récursion avant d’épuiser la pile. Son résultat dépasserait bien plus tôt la capacité d’un int de 32 bits, dès 13! = 6 227 020 800.
  
  $⌊ \frac{1 048 576}{12} ⌋ = 87381$
3. Avec une variable locale de 4 octets, chaque cadre occupe 16 octets. Or 1 048 576 / 16 = 65 536 exactement.
  
  $f = 16 : \frac{1 048 576}{16} = 65536$
4. La plus longue chaîne de fib(30) contient 30 cadres, soit 30 × 12 = 360 octets. Le nombre d’appels vaut 2·F(31) − 1, où F(31) = 1 346 269 est le 31e nombre de Fibonacci. On obtient 2 692 537 appels.
  
  $d = 30 : 30 \times 12 = 360, 2 F_{31} - 1 = 2 \times 1346269 - 1 = 2692537$
Réponse

87 381 niveaux, ou 65 536 avec une variable locale. fib(30) utilise 360 octets de pile pour 2 692 537 appels. La profondeur détermine l’espace occupé dans la pile ; pour fib, le nombre d’appels détermine le temps d’exécution.

$d_{m a x} = ⌊ \frac{S}{f} ⌋ = 87381 (f = 12), 65536 (f = 16)$

Parcours

Comment un ordinateur exécute un programme

Références (2)

The worked problem's stack size: the linker's default reservation: Microsoft Learn, "/STACK (Stack allocations)," C/C++ build reference, updated 23 February 2022.
The first insight's 1988 example: fingerd's unbounded read into a 512-byte buffer on the stack: Bob Page, "A Report on the Internet Worm." University of Lowell, 7 November 1988 (copy hosted at Toronto Metropolitan University).

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.