# Fonctionnement d'un ordinateur/La pile d'appel et les fonctions

Dans ce chapitre, nous allons étudier une fonctionnalité du processeur appelée la pile d'appel. Son rôle est de simuler une mémoire de type LIFO (Last In, First Out), mais à l'intérieur d'une mémoire RAM. Sans elle, certaines fonctionnalités de nos langages de programmation actuels n'existeraient pas ! Pour les connaisseurs, cela signifierait qu'on ne pourrait pas utiliser de fonctions ré-entrantes ou de fonctions récursives.

## Les fonctions et procédures logicielles

Un programme contient souvent des suites d'instructions présentes en plusieurs exemplaires, qui servent souvent à effectuer une tâche bien précise : calculer un résultat bien précis, communiquer avec un périphérique, écrire un fichier sur le disque dur, ou autre chose encore. Sans utiliser de sous-programmes, ces suites d'instructions sont présentes en plusieurs exemplaires dans le programme. Le programmeur doit donc recopier à chaque fois ces suites d'instructions, ce qui ne lui facilite pas la tâche (sauf en utilisant l’ancêtre des sous-programmes : les macros). De plus, ces suites d'instructions sont présentes plusieurs fois dans le programme et elles prennent de la place inutilement !
Dans les langages de programmation modernes, il est possible de ne conserver qu'un seul exemplaire en mémoire et l'utiliser au besoin. L'exemplaire en question est ce qu'on appelle une fonction, ou encore un sous-programme. C'est au programmeur de « sélectionner » ces suites d'instructions et d'en faire des fonctions. Pour exécuter une fonction, il faut exécuter un branchement dont l'adresse de destination est celle de la fonction : on dit qu'on appelle la fonction. Toute fonction se termine aussi par un branchement, qui permet au processeur de revenir là où il en était avant d'appeler la fonction.
Les langages de programmation actuels ont des fonctionnalités liées aux fonctions, qui simplifient bien la vie des programmeurs.
En premier lieu, une fonction peut calculer des données temporaires, souvent appelées des variables locales. Ces variables locales sont des données accessibles par le code de la fonction mais invisibles pour tout autre code. La variable locale est dite déclarée dans le code de la fonction, mais inaccessible ailleurs. Les variables locales sont opposées aux variables globales, qui sont accessibles dans tout le programme, par toute fonction. L'usage des variables globales est déconseillé, mais on en a parfois besoin.
En second lieu, la fonction peut prendre des opérandes et/ou calculer un résultat. Les fonctions mathématiques complexes sont dans ce cas : elles prennent des opérandes en entrée et fournissent un résultat. Mais ce ne sont pas les seules. Par exemple, une fonction qui ouvre un fichier prend en opérande le nom de ce fichier. Les opérandes envoyées à une fonction sont appelés des arguments ou paramètres. On peut communiquer ces valeurs de deux manières, soit en en fournissant une copie, soit en fournissant leur adresse. Les résultats sont eux appelés des valeurs de retour et sont récupérés par le programme principal pour qu'il en fasse quelque chose. Généralement, c'est le programmeur qui décide de conserver une donnée et d'en faire une valeur de retour.
Implémenter des fonctions peut se faire sans support de la part du processeur. Cependant, tous les processeurs modernes incorporent des techniques pour accélérer les fonctions ou rendre leur implémentation plus simple. Au-delà des instructions d'appel et de retour de fonction, les processeurs modernes incorporent une technique appelée la pile d'appel, que nous allons voir dans la section suivante.

### La sauvegarde des registres

Lorsqu'un sous-programme s'exécute, il va utiliser certains registres qui sont souvent déjà utilisés par le programme principal. Pour éviter d'écraser le contenu des registres, on doit donc conserver une copie de ceux-ci dans la mémoire RAM. Une fois que le sous-programme a fini de s'exécuter, il remet les registres dans leur état original en chargeant la sauvegarde dans les registres adéquats. Ce qui fait que lorsqu'un sous-programme a fini son exécution, tous les registres du processeur reviennent à leur ancienne valeur : celle qu'ils avaient avant que le sous-programme ne s'exécute. Rien n'est effacé !
La gestion des variables locales, des arguments et des valeurs de retour est gérée par la sauvegarde/restauration des registres du processeur. Les arguments sont passés à une fonction dans un registre, qui est préparé avant l'exécution de la fonction. Lorsque la fonction est appelée, elle lit ce registre pour récupérer l'opérande/argument. Les registres pour les arguments ne sont pas sauvegardés ni restaurés après la fin de la fonction. Les valeurs de retour sont gérées de la même manière. Elles sont placées dans un registre spécifique, qui est lu par le programme principal pour consulter cette valeur de retour. Ce registre de retour n'est pas restauré à la fin de la fonction.
La sauvegarde des registres est le plus souvent effectuée par le logiciel, par un petit morceau de code se chargeant de sauvegarder les registres un par un. Plus rarement, certains processeurs ont une instruction pour sauvegarder les registres. C'est le cas sur les processeurs ARM1, qui ont une instruction pour sauvegarder n'importe quel sous-ensemble des registres du processeur. On peut par exemple choisir de sauvegarder le premier et le troisième registre en RAM, sans toucher aux autres. Le processeur se charge alors automatiquement de sauvegarder les registres uns par un en mémoire, bien que cela ne prenne qu'une seule instruction pour le programmeur.
    L'implémentation matérielle de cette instruction est décrite dans les deux articles suivants :
* Counting bits in hardware: reverse engineering the silicon in the ARM1 processor
* More ARM1 processor reverse engineering: the priority encoder

### La sauvegarde de l'adresse de retour

Une fois le sous-programme fini, il faut reprendre l’exécution du programme principal là où il s'était arrêté. Plus précisément, le programme doit reprendre à l'instruction qui est juste après le branchement d'appel de fonction. L'adresse de celle-ci étant appelée l'adresse de retour. Reprendre au bon endroit demande d'exécuter un branchement inconditionnel vers cette adresse de retour.
Mais vu qu'une fonction apparaît plusieurs fois dans notre programme, il y a plusieurs possibilités de retour, qui dépend de où est appelé la fonction. Mais comment savoir à quelle instruction reprendre l'exécution de notre programme, une fois le sous-programme terminé ? La seule solution est de sauvegarder l'adresse de retour lorsqu'on appelle la fonction. Et cela peut se faire de plusieurs manières différentes, suivant là où est mémorisée l'adresse de retour.
La solution la plus évidente consiste à sauvegarder l'adresse de retour dans les registres, sans faire usage d'un registre dédié. N'importe quel registre peut mémoriser l'adresse de retour, le programme est codé pour en choisir un bien précis. Quelques processeurs disposent d'une instruction pour faire cela automatiquement avec une instruction de branchement spéciale, souvent appelée Branch And Link. Elle effectue un branchement pour appeler la fonction et mémorise l'adresse de retour dans un registre. La fin d’une fonction se fait en utilisant un branchement inconditionnel indirect. Ce dernier prend comme opérande le registre contenant l'adresse de retour et branche alors vers celle-ci.
Une autre solution dédie un registre spécialisé pour l'adresse de retour, appelé le registre d'adresse de retour. Lorsque le processeur appelle une fonction, l'adresse de retour est sauvegardée dans ce registre, grâce à une instruction Branch And Link. Lorsqu'une fonction termine, l'adresse dans ce registre est utilisée par le branchement qui termine la fonction. La technique a été utilisée sur le processeur TMS 1000 de Texas Instrument, et quelques autres processeurs très peu puissants. Ce sont tous des processeurs anciens.

## La pile d'adresse de retour de certaines architectures embarquées

La solution précédente sauvegarde l'adresse de retour d'une fonction dans un registre. Elle gère le cas à une seule fonction, mais ne marche pas si une fonction en exécute une autre. C'est une situation très courant, que tout programmeur rencontre dès les premiers cours/exercices portant sur les fonctions. Pour donner un exemple, une fonction mathématique qui calcule le nombre de permutations d'un ensemble devra exécuter la fonction de calcul de la factorielle (une opération mathématique). Ou encore une fonction qui vérifie si un numéro de sécurité sociale est correct devra utiliser plusieurs fonctions, chacune faisant une vérification indépendante (on vérifie que telle partie du numéro colle bien, au nom, telle autre au sexe, telle autre à la date de naissance, et ainsi de suite). Une telle situation porte le nom de fonctions imbriquées.
Et gérer les fonctions imbriquées demande de l'aide de la part du processeur. Il existe plusieurs méthodes pour cela. La solution la plus utilisée de nos jours, utilise une fonctionnalité des processeurs appelée la pile d'appel. Mais nous n'allons pas voir la pile d'appel immédiatement. A la place, nous allons en voir une variante fortement simplifiée, utilisée sur certaines architectures embarquées faible performance. Cette solution simplifiée gère les fonctions imbriquées, mais ne gère pas les fonctions dites récursives, terme qu'on expliquera plus bas.

### Les piles : une structure de données ordonnée

Avec des fonctions imbriquées, il faut sauvegarder plusieurs adresses de retour, une par fonction appelée. Par exemple, si une fonction A exécute une fonction B, qui elle-même exécute une fonction C, il faut sauvegarder trois adresses de retour : celle où retourner à la fin de la fonction A (dans le programme principal), celle où retourner à la fin de la fonction B (dans la fonction A), celle où retourner à la fin de la fonction C (dans la fonction B).
De plus, elles doivent être sauvegardées dans un certain ordre : de la plus récente à la plus ancienne. Elles doivent être sauvegardées dans l'ordre A, B, C. Par contre, elles seront utilisées dans l'ordre inverse lors du retour de la fonction. En clair, une fois que la fonction C termine, on utilise l'adresse de retour C associée, puis celle de la fonction B quand elle termine, puis celle de A quand elle termine.
Une manière de décrire ce fonctionnement est de le comparer à une pile d'assiette : on peut parfaitement rajouter une assiette au sommet de la pile d'assiette, ou enlever celle qui est au sommet, mais on ne peut pas toucher aux autres assiettes. On ne peut accéder qu'à l'adresse située au sommet de la pile. Comme pour une pile d'assiette, on peut rajouter ou enlever une adresse au sommet de la pile, mais pas toucher aux adresses en dessous, ni les manipuler. L'idée est d'organiser les adresses de retour de la même manière, en utilisant une structure de donnée appelée une pile, qui est bien connue des programmeurs.
Le nombre de manipulations possibles sur cette pile d'adresse se résume donc à deux manipulations de base qu'on peut combiner pour créer des manipulations plus complexes. On peut ainsi :
* retirer l'adresse de pile au sommet de la pile, pour l'utiliser : on dépile.
* ajouter une adresse au-dessus des adresses existantes : on empile.
Si vous regardez bien, vous remarquerez que l'adresse au sommet de la pile est la dernière donnée à avoir été ajoutée (empilée) sur la pile. Ce sera aussi la prochaine à être dépilée (si on n'empile pas d'adresse au-dessus). Ainsi, on sait que dans cette pile, les données sont dépilées dans l'ordre inverse d'empilement. Il s'agit d'un comportement dit LIFO : dernier arrivé, premier sorti. Ce qui est exactement ce qu'on recherche pour la gestion des adresses de retour.

### La pile d'adresse de retour

La pile d'adresse de retour est une pile, qui mémorise des adresses de retour des fonctions. Lorsqu'une fonction est exécutée, elle empile son adresse de retour au sommet de la pile. Lorsqu'elle se termine, elle dépile l'adresse de retour, celle qui est au sommet de la pile, et effectue un branchement vers celle-ci. Reste à implémenter la pile d'adresse de retour. Pour cela, il y a deux solutions : l'intégrer au processeur, la placer dans la mémoire RAM;
La première utilise une mémoire LIFO, qui n'est autre qu'une pile implémentée avec des transistors. Toute écriture dans ces mémoires ajoute/empile une donnée dedans, toute lecture dépile la donnée la plus récente. Pour rappel, une mémoire LIFO est fabriquée à partir d'une RAM dédiée, qui utilise une case mémoire par adresse. L'idée est de commencer à remplir les cases mémoires à partir de l'adresse 0, à partir du début de la mémoire. La première adresse est placée dans l'adresse 0, la suivante est empilée à l'adresse suivante (l'adresse 1), celle qui suit est placée dans l'adresse encore suivante (l'adresse 2), et ainsi de suite. Les adresses seront alors naturellement mémorisées dans l'ordre, il y a juste à mémoriser où se trouve le sommet de la pile. Pour cela, la mémoire RAM est couplée à un registre qui mémorise où se situe le sommet de la pile dans la mémoire RAM. Le registre est incrémenté à chaque fois qu'on empile une donnée, décrémenté quand on dépile une donnée.
Si quelques architectures à pile ont utilisé une pile séparée du processeur, c'était une solution loin d'être idéale. Il fallait ajouter un bus dédié entre la mémoire LIFO et le processeur, donc beaucoup de broches. Une alternative est d'intégrer la mémoire LIFO au processeur. Avec l'augmentation du nombre de transistors, intégrer une pile d'adresse de retour au processeur n'est plus un problème. De nombreux microcontrôleurs et microprocesseurs embarqués utilisent cette technique. Mais elle a un défaut : la pile peut contenir un nombre maximal d'adresses, ce qui peut poser certains problèmes. Si l'on souhaite utiliser plus de cadres de pile que possible, il se produit un débordement de pile. En clair, l'ordinateur plante !
Une autre solution place la pile d'adresse de retour en mémoire RAM. L'avantage est qu'on n’est pas limité par la taille de la mémoire LIFO. Le problème est qu'il faut émuler une piler à partir d'un morceau de mémoire RAM. Et la solution est très simple, bien qu'elle vous paraitra un peu contrintuitive. L'idée s'inspire beaucoup de l'implémentation d'une mémoire LIFO, à savoir qu'on commence à remplir la RAM à partir d'une adresse, et qu'on mémorise où se trouve le sommet de la pile.
Cependant, on ne peut pas commencer à remplir la RAM à partir de l'adresse 0 : le programme à exécuter ou des données sont à cet endroit-là. La solution est alors de commencer à remplir à partir de l'adresse haute, la dernière adresse de la mémoire RAM. On remplit alors la pile du haut de la mémoire vers le bas. Les adresses sont empilées dans l'ordre décroissant des adresses, de la dernière adresse vers la première. Le tout est illustré ci-contre.
Une fois cela fait, il suffit d'ajouter un registre qui mémorise où se situe le sommet de la pile. Le registre qui indique où est le sommet de la pile, quelle est son adresse, est appelé le pointeur de pile, ou encore le Stack Pointer (SP). Il est décrémenté lorsqu'on empile une adresse, incrémenté lorsqu'on en dépile une. Il est incrémenté/décrémenté de X si une adresse prend X bytes.

### Les instructions d'appel et de retour de fonction

Disposer d'une pile d'adresses de retour est un premier pas. Mais il manque de quoi la manipuler, pour empiler ou dépiler des adresses de retour. Pour cela, une solution est d'utiliser des instructions spécialisées pour les appels et retour de fonction, qui modifient automatiquement la pile d'adresse. Les instructions en question sont des améliorations de l'instruction branch and link vue plus haut.
Appeler une fonction demande d’empiler l'adresse de retour, de modifier le pointeur de pile, puis de brancher vers l'adresse de la fonction. Il existe une instruction pour empiler l'adresse de retour et décrémenter le pointeur de pile. Elle est suivie par un branchement pour appeler la fonction. Le branchement d'appel de fonction, la sauvegarde de l'adresse de retour et la gestion du pointeur de pile sont fusionnés en une seule instruction d'appel de fonction.
De même, le retour de la fonction demande de faire un branchement vers l'adresse de retour et de restaurer le pointeur de pile, etc. Là encore, certains processeurs disposent d'une instruction de retour de fonction dédiée.
Des processeurs émulent ces instructions d'appel/retour de fonction avec un branchement complété par d'autres instructions.

### La sauvegarde des registres et la gestion des arguments sans récursivité

La sauvegarde des registres est réalisée par la fonction elle-même, grâce à un code de sauvegarde au tout début de la fonction et un code de restauration à sa toute fin. Pour cela, le compilateur alloue une petite portion de mémoire, dans laquelle les registres sont copiés lors d'un appel de fonction. La zone de mémoire en question n'a pas de nom consacré par la terminologie, mais je vais l'appeler la register save area. Chaque fonction a sa propre portion de mémoire allouée rien que pour elle. Elle contient juste ce qu'il faut pour sauvegarder les registres, rien de plus. Chaque registre a sa position attitrée dans cette portion de RAM, le code de sauvegarder/restauration des registres en tient compte.
Pour la gestion des arguments, la même méthode peut être utilisée. Le compilateur attribue à chaque fonction une petite portion de RAM où les arguments sont écrits avant l'appel de la fonction. Là encore, la zone de mémoire en question n'a pas de nom consacré par la terminologie, mais je vais l'appeler la function argument area. Le code qui appelle la fonction écrit les arguments dans cette portion de RAM, chaque argument a sa position attitrée, le code est conçu pour en tenir compte. Puis il appelle la fonction et celle-ci lit les arguments en RAM quand elle en a besoin, elle connait leur adresse à l'avance.
Et même chose pour les variables locales, avec une function local area.
Dans les deux cas, le processeur ne se préoccupe pas vraiment de la sauvegarde des registres ou des arguments. Il n'a aucun moyen d'accélérer le processus. La seule possibilité est de fournir des instructions dédiées à la sauvegarde des registres, qu'on a mentionné plus haut.

## La pile d'appel : le support des fonctions récursives

L'usage d'une pile d'adresses de retour est une solution intelligente, simple, mais avec un gros défaut qu'il faut aborder. Le problème est qu'elle ne gère pas les fonctions dites récursives. Les fonctions récursives sont des fonctions qui s'appellent elles-mêmes. Elles sont assez rares, mais les programmeurs ont tous eu un cours sur le sujet lors de leurs études, c'est un passage obligé. Il existe aussi des fonctions dites indirectement récursives, où une fonction A appelle une fonction B, qui appelle une fonction C, qui appelle la fonction A (mais avec des opérandes/arguments différents).

### Les cadres de pile

En soi, une pile d'adresse de retour fonctionne avec des fonctions récursives. Mais le mécanisme de sauvegarde des registres et de gestion des arguments ne fonctionne pas. Un exemple : imaginez une fonction A qui appelle la fonction B, qui appelle la fonction C, qui elle-même appelle la fonction B. Il y a deux instances de la fonction B en même temps : celle appelée par la fonction A, celle appelée par la fonction C. Et les deux instances ont chacune avec ses propres arguments, sans compter que chacune doit sauvegarder les registres qu'elle modifie. Le même problème a lieu dans le cas général : avec une fonction récursive, il est possible que plusieurs instances de la fonction s'exécutent.
Idéalement, il faudrait plusieurs register save area, plusieurs function local area et plusieurs function argument area, une par instance de la fonction. Mais on ne peut pas préallouer plusieurs register save area, plusieurs function local area et plusieurs function argument area, cela prendrait trop de place, sans compter qu'on sera limité en terme de nombre d'instances par fonction. Une autre solution réalloue dynamiquement plusieurs function local area/register save area/function argument area, exactement autant qu'il y a d'instances. C'est ce qui est fait sur les processeurs modernes, qui utilisent pour ce faire une pile d'appel.
L'idée est d'élargir la pile d'adresse de retour, de manière à ce qu'elle mémorise aussi des register save area, des function local area et des function argument area. Précisément, la pile mémorise des cadres de pile, des espèces de blocs de mémoire de taille fixe ou variable suivant le processeur. Chaque cadre de pile mémorise l'adresse de retour d'un appel de fonction, une register save area, une function local area et une function argument area, avec parfois des informations en plus.
Les cadres sont créés à chaque appel de fonction et respectent l'organisation en pile. La pile d'adresse de retour est remplacée par une pile appelée la pile d'appel, qui contient plusieurs cadres de pile placés les uns à la suite des autres dans la mémoire. Et comme pour la pile d'adresses de retour, la pile d'appel démarre à l'adresse maximale, et descend vers les adresses plus basses, au fur et à mesure qu'on ajoute des cadres de pile, comme illustré ci-dessous.
La pile peut contenir un nombre maximal de cadres, ce qui peut poser certains problèmes. Si l'on souhaite utiliser plus de cadres de pile que possible, il se produit un débordement de pile. En clair, l'ordinateur plante !
Quelques compilateurs gardent une trace des limites de chaque cadre de pile. Pour cela, ils complémentent le pointeur de pile avec une autre adresse, qui indique la base du cadre de pile. Elle est appelée le Frame Pointer (FP), ou pointeur de contexte. Il est surtout utile pour les outils de debogages, mais est souvent omis dans les codes optimisés.

### Les instructions PUSH et POP pour gérer la pile

Lorsqu'on appelle une fonction, on crée un cadre de pile qui une taille suffisante pour stocker toutes les informations nécessaires pour que l'appel de fonction se passe comme prévu : l'adresse de retour, les arguments/paramètres, la copie de sauvegarde des registres du processeur, les variables locales, etc. Cependant, il nous manque un mécanisme pour ajouter ces données dans un cadre de pile. Les instructions d'appel/retour de fonction permettent d'empiler/dépiler l'adresse de retour, mais pas plus. Heureusement, le processeur intègre des instructions pour empiler ou dépiler des données sur la pile d'appel.
Les données sont ajoutés ou retirés de la pile grâce à deux instructions nommées PUSH et POP.
* L'instruction PUSH permet d'empiler une donnée. Elle prend l'adresse de la donnée à empiler, charge la donnée, et met à jour le pointeur de pile.
* L'instruction POP dépile la donnée au sommet de la pile, la stocke à l'adresse indiquée dans l'instruction, et met à jour le pointeur de pile.
Les instructions PUSH/POP ont une source et une destination. L'instruction PUSH prend une source, et empile son contenu sur le sommet de la pile, qui est la destination. La source peut être un registre ou une adresse mémoire, éventuellement une constante intégrée dans l'instruction. L'instruction POP fait l'inverse. Sa source est le sommet de la pile, il est envoyé vers une destination qui est soit un registre, soit une adresse mémoire.
Une instruction PUSH/POP effectue un accès mémoire pour transférer la source vers la destination. Mais elles altèrent aussi le pointeur de pile. Il est décrémenté à chaque instruction PUSH, incrémenté à chaque instruction POP. Il est incrémenté/décrémenté de la taille d'un registre, donc de 2 octets sur un processeur 16 bits, 4 octets sur un processeur 32 bits, 8 sur un processeur 64 bits. L'incrémentation/décrémentation du pointeur de pile est donc une vulgaire opération arithmétique, réalisée soit dans des circuits spécialisés, soit dans les circuits de calcul normaux.

### La sauvegarde/restauration des registres et la valeur de retour

Les instructions PUSH et POP sont utilisées pour sauvegarder les registres et les restaurer. Pour cela, imaginons qu'ils sont sauvegardés et restaurés à l'intérieur de la fonction. Ils sont sauvegardés au tout début de la fonction, la restauration a lieu à la toute fin, juste avant l'instruction de retour de fonction. Sauvegarder un registre se fait avec une instruction PUSH, qui a pour source le registre à sauvegarder. Le registre est alors placé au sommet de la pile, juste après les données déjà empilées. La restauration se fait avec une instruction POP ayant pour destination ce même registre. Les registres sont sauvegardés dans un ordre précis, avec les instructions PUSH dans un certain ordre, les instructions POP pour dépiler se font dans l'ordre inverse.
Par exemple, pour un processeur avec 4 registres nommés R0, R1, R2 et R3, voici ce que donnerait le code de la fonction :
Cependant, la restauration doit tenir compte de la valeur de retour de la fonction, qui peut être conservée soit dans les registres, soit dans la pile d'appel. Il est théoriquement possible de la stocker dans un registre, mais il faut faire attention à ce qu'elle ne soit pas écrasée lors de la restauration des registres. Dans ce cas, un registre au moins n'est pas restauré directement, mais laisse la place à la valeur de retour. C'est le code après la fonction qui gère la situation et qui restaure lui-même le registre en question.
Une autre solution est de mettre la valeur de retour sur la pile d'appel, en l'empilant. La valeur de retour est transférée dans la pile avec une instruction PUSH, le code appelant la récupére avec une instruction POP.

### Les arguments, les variables locales et la valeur de retour

La transmission des arguments à une fonction peut se faire en les copiant soit dans la pile, soit dans les registres. Avec le passage par la pile, les arguments sont empilés sur la pile et la fonction les récupéré dans la pile directement. Avec le passage par les registres, les paramètres sont copiés dans des registres, qui ne sont pas sauvegardés lors de l'appel de la fonction. Si on utilise le passage par les registres, il faut que le nombre de registres soit suffisant, ce qui dépend du nombre d'argument, mais aussi du nombre de registres. En conséquence, le passage par la pile est très utilisé sur les processeurs avec peu de registres, alors que les processeurs avec beaucoup de registres privilégient le passage par les registres.
La gestion des variables locales, arguments et valeurs de retour sont assez complexes. Et surtout, il y a beaucoup de manière de faire, qui dépendent de comment les compilateurs utilisent la pile d'appel. Les différentes manières sont appelées des conventions d'appel, calling convention en anglais. Ils standardisent des choses assez variées : comment sont organisées les données dans un cadre de pile, dans quel ordre sont envoyés les arguments, etc.
Voyons une version simplifiée de la convention d'appel des processeurs x86, sans frame pointer. Pour simplifier les explications, nous allons introduire les termes de code appelant et de code appelé. Le code appelant est celui qui exécute la fonction, le code appelé est la fonction elle-même.
Voici comment se déroule un appel de fonction :
* En premier lieu, le code appelant PUSH les arguments sur la pile. Il pourrait les passer par les registres, comme c'est le cas sur d'autres architectures avec plus de registres comme les architectures RISC-V, mais passons. Les arguments sont empilés avant d'appeler la fonction, car celle-ci ne sait pas dans quels registres ils sont, ni à quelles adresses.
* En second lieu, une instruction d'appel de fonction est émise. Elle sauvegarde l'adresse de retour et effectue un branchement vers l'adresse de la fonction.
* En troisième lieu, le pointeur de pile est modifié de manière à faire de la place aux variables locales sur la pile, ainsi qu'à la register save area. La zone réservée regroupe la register save area et la function local area. Les variables locales ne sont pas empilées sur la pile, ni dépilées. Le code appelant réserve juste de la place et il lira/écrira dedans comme bon lui semble. Pour cela, on soustrait la taille de la function local area au pointeur de pile.
La pile ressemble donc à ceci :
Il faut noter que lors de la fin de la fonction, les arguments ne sont pas dépilés, ils sont simplement effacés/oubliés. Et même chose pour les variables locales. La function local area et la function argument area ne sont pas dépilées, juste effacées. On parle de nettoyage de la pile. L'idée est de modifier le pointeur de pile de manière à ce qu'il pointe avant la function argument area/function local area, plutôt que après. Mais cela n'est possible que si le pointeur de pile est un registre nommé ou adressable explicitement.
La function local area et la function argument area sont donc deux zones mémoire séparées, mais placées dans un cadre de pile. Le problème est de récupérer les arguments ou les variables locales pour les charger dans les registres, quand on en a besoin. Pour cela, les instructions LOAD et STORE ne peuvent pas utiliser leur adresse mémoire, vu qu'elle change selon la position dans le cadre de pile. A la place, les instructions LOAD et STORE disposent de modes d'adressages spécialisés, qui adressent arguments et variables locales par leur position dans le cadre de pile. Ils disent que telle variable locale est 8 octets avant le sommet de la pile, que tel argument est 16 octets avant, etc. Une instruction LOAD/STORE ajoute alors automatiquement cette position au pointeur de pile, pour générer l'adresse à lire/écrire.

### La pile fantôme pour vérifier les adresses de retour

Les compilateurs modernes peuvent complémenter la pile d'appel avec une pile d'adresse de retour. La pile d'appel stocke toujours les adresses stockées dans la pile d'appel, ce qui fait que la pile d'appel est redondante. Et c'est justement cette redondance qui est utile, dans le sens où certaines techniques de sécurité sont plus faciles à implémenter avec une pile d'appel séparée, comme on le verra plus bas. Par contre, la séparation a divers désavantages. Le principal est que les deux piles séparées sont potentiellement éloignées en mémoire, ce qui ne respecte pas très bien le principe de localité spatiale. Les performances sont alors réduites sur les processeurs avec une mémoire cache.
Si une fonction retourne et que l'adresse de retour n'est pas la bonne, le programme ne fonctionne pas comme prévu et cela peut donner des plantages ou tout autre conséquence fâcheuse. Diverses attaques informatiques cherchent justement à modifier l'adresse de retour d'une fonction pour exécuter du code malicieux. L'attaque demande d'insérer un morceau de code malicieux dans un programme (par exemple, un virus) et de l’exécuter lors d'un retour de fonction. Pour cela, l'assaillant trouve un moyen de modifier l'adresse de retour d'une fonction mal codée, puis en détourne le retour pour que le processeur ne reprenne pas là où il le devrait, mais reprenne l’exécution sur le virus/code malicieux. Le code malicieux est programmé pour que, une fois son travail accompli, le programme reprenne là où il devait une fois la fonction détournée terminée.
Il existe diverses techniques pour éviter cela et certaines de ces techniques se basent sur des procédés matériels, intégrés dans le processeur. Le premier de ces procédé est l'usage d'une shadow stack, une pile fantôme. Celle-ci est une simple copie de la pile d'appel, mémorisée en mémoire ou dans le processeur, qui est utilisée pour vérifier que les retours de fonction se passent bien. Sauf que là où la pile d'appel a des cadres volumineux, la pile fantôme ne mémorise que les adresses de retour. L'avantage est que ces attaques consistent généralement à injecter des données volumineuses dans un cadre de pile, afin de déborder d'un cadre de pile, voire de déborder de la mémoire allouée à la pile. Autant c'est possible avec les cadres de la pile d'appel, autant ce n'est pas possible avec la pile fantôme, vu qu'on n'y insère pas ces données. De plus, les deux piles d'appel sont éloignées en mémoire, ce qui fait que toute modification de l'une a peu de chances de se répercuter sur l'autre. Notons que les failles de sécurité de ce type sont plus compliquées si la pile d'adresse de retour est séparée de la pile d'appel, mais que ce n'est pas le cas sur les PC actuels.
La pile d'appel fantôme peut être gérée soit au niveau logiciel, par le langage de programmation ou le système d'exploitation, mais aussi directement en matériel. C'est le cas sur les processeurs x86 récents, depuis l'intégration par Intel de la technologie Control-flow Enforcement Technology. Il s'agit d'une pile fantôme gérée directement par le processeur. Quand le processeur exécute une instruction de retour de fonction RET, il vérifie automatiquement que l'adresse de retour est la même dans la pile d'appel et la pile fantôme. Si il y a une différence, il stoppe l’exécution du programme et prévient le système d'exploitation (pour ceux qui a ont déjà lu le chapitre sur les interruptions : il démarre une exception matérielle spécialisée appelée Control Flow Protection Fault.