# 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 : les 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.

### La pile d'adresse de retour

Avec des fonctions imbriqués, 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écent à 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. L'idée est d'organiser les adresses de retour de la même manière. 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.
Le nombre de manipulations possibles sur cette pile se résume donc à trois 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.
* utiliser l'adresse qui se situe au sommet de la pile.
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. Ce qui est exactement ce qu'on recherche pour la gestion des adresses de retour. Il s'agit d'un comportement dit LIFO : dernier arrivée, premier sorti.
Au fait, 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 !

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

La pile d'appel est une portion de mémoire qui simule une mémoire LIFO. On peut ajouter ou retirer une donnée de la pile d'appel, mais la donnée retirée est systématiquement la plus récente, la dernière qui fut ajoutée. La pile d'appel est souvent une partie de la mémoire RAM, mais c'est parfois une mémoire séparée. Certains processeurs sauvegardent une copie de la pile dans des registres cachés au lieu de tout mémoriser en RAM. Cette technique permet d'améliorer les performances, une partie de la pile étant mémorisée dans des registres rapides et non dans une mémoire RAM lente.

### Les cadres de pile

Les données sont organisées d'une certaine façon à l'intérieur. Les données sont regroupées dans la pile dans ce qu'on appelle des cadres de pile, des espèces de blocs de mémoire de taille fixe ou variable suivant le processeur.
Le contenu d'un cadre de pile varie fortement suivant le processeur. Certains processeurs se contentent d'y placer une adresse mémoire par cadre de pile. D'autres y placent plusieurs entiers ou adresses bien précises, avec une organisation fixe et immuable, ce qui donne des cadres de pile de taille fixe. Mais d'autres ont des cadres de pile de taille variable, ce qui permet aux logiciels d'y mettre ce qu'ils veulent. Les cadres de taille fixe sont surtout utilisées sur les processeurs anciens, alors que les piles d'appel programmables sont utilisées sur les processeurs modernes.

### L'ordre des cadres de pile : une structure de type LIFO

Les cadres sont créés un par uns et sont placés les uns à la suite des autres dans la mémoire. C'est une première contrainte : on ne peut pas créer de cadres n'importe où dans la mémoire. On peut comparer l'organisation des cadres à 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. Sur la pile de notre ordinateur, c'est la même chose : on ne peut accéder qu'à la donnée située au sommet de la pile. Comme pour une pile d'assiette, on peut rajouter ou enlever le cadre au sommet de la pile, mais pas toucher aux cadres en dessous, ni les manipuler.
Le nombre de manipulations possibles sur cette pile se résume donc à trois manipulations de base qu'on peut combiner pour créer des manipulations plus complexes. On peut ainsi :
* détruire le cadre de pile au sommet de la pile, et supprimer tout son contenu de la mémoire : on dépile.
* créer un cadre de pile immédiatement après le dernier cadre de pile existante : on empile.
* utiliser les données stockées dans le cadre de pile au sommet de la pile.
Au fait, 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 !

### La délimitation des cadres de pile

Pour gérer ces piles, on a besoin de sauvegarder deux choses : l'adresse à laquelle commence le cadre de pile en mémoire, et de quoi connaître l'adresse de fin. Le registre qui indique où est le sommet de la pile, quelle est son adresse, est appelé le pointeur de sommet, ou encore le Stack Pointer (SP). À ce registre, on peut rajouter un registre qui sert à donner l'adresse de début du cadre de pile : le Frame Pointer (FP), ou pointeur de contexte.
Pour localiser une donnée dans un cadre de pile, on utilise sa position par rapport au début ou la fin du cadre de pile. On peut donc calculer l'adresse de la donnée en additionnant cette position avec le contenu du pointeur de pile.
Certains processeurs possèdent deux registres spécialisés qui servent respectivement de pointeur de contexte et de pointeur de pile : on ne peut pas les utiliser pour autre chose. Si ce n'est pas le cas, on est obligé de stocker ces informations dans deux registres normaux, et se débrouiller avec les registres restants.
D'autres processeurs arrivent à se passer de Frame Pointer. Ceux-ci n'utilisent pas de registres pour stocker l'adresse de la base du cadre, mais préfèrent calculer cette adresse à partir de l'adresse de fin du cadre et de sa longueur. Cette longueur peut être stockée directement dans certaines instructions censées manipuler la pile : si chaque cadre a toujours la même taille, cette solution est clairement la meilleure. Cette solution est idéale si le cadre de pile a toujours la même taille. Mais il arrive que les cadres aient une taille qui ne soit pas constante : dans ce cas, on a deux solutions : soit stocker cette taille dans un registre, soit la stocker dans les instructions qui manipulent la pile, soit utiliser du code auto-modifiant.

## L'usage de la pile d'appel par les fonctions

Il n'est pas rare qu'un programme imbrique des fonctions, c'est à dire qu'une fonction peut appeler une autre fonction, qui elle-même en appelle une autre, et ainsi de suite. Pour exécuter plusieurs fonctions imbriquées les unes dans les autres, la totalité des langages de programmation actuels utilise la ou les pile d'appel du processeur. C'est d'ailleurs ce qui lui vaut son nom : elle sert pour les appels de fonction, ce qui fait qu'elle s'appelle pile d'appel (de fonctions).
Le principe est simple : lorsqu'on appelle une fonction, on crée un cadre de pile qui va 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. Une autre méthode utilise une pile séparée pour les appels de retour, une autre pour les arguments, etc. Mais passons, voyons maintenant comment cela fonctionne.

### La pile d'adresse de retour

En premier lieu, on doit sauvegarder plusieurs adresses de retour, les unes à la suite des autres dans l'ordre d'appel des fonctions.Ainsi, si une fonction F1 appelle une fonction F2, puis une fonction F3, les adresses de retour doivent se trouver dans le même ordre. De plus, quand une fonction se termine, l'adresse de retour est utilisée et doit être supprimée. On voit bien que ce comportement correspond à une pile. Si on stocke les adresses de retour dans une pile, l'adresse de retour à utiliser est située au sommet de la pile. La pile d'appel sert donc pour les fonctions imbriquées et est une pile d'adresses de retour pour les fonctions. Il est primordial que les adresses de retour soient stockées dans le bon ordre, pour que le programme reprenne au bon endroit.
Sur certains processeurs, la pile d'appel gère les adresses de retour et tout le reste des données. Mais sur d'autres, la pile d'appel est découpée en plusieurs piles séparées : la pile d'adresses de retour et une seconde pile appelée la pile de données. Cette séparation a des avantages et des inconvénients. Les avantages sont que la gestion des données est plus simple pour le programmeur, bien qu'elle manque de flexibilité. Un autre avantage est que 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.

### Les autres piles/données du cadre d'appel

Outre l'adresse de retour, il faut aussi sauvegarder les registres du processeur avant l'appel de la fonction. Là encore, les registres à sauvegarder sont mémorisés dans une pile, pour les mêmes raisons. Là encore, on peut sauvegarder ces registres dans une pile d'appel unique, ou dans une pile de sauvegarde des registres séparée.
La transmission des arguments à une fonction peut se faire en les copiant soit dans la pile, soit dans les registres. Dans le cas d'un passage par les registres, les registres qui contiennent les paramètres ne sont pas sauvegardés lors de l'appel de la fonction. Généralement, 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. Si on utilise le passage par les registres, il faut que le nombre de registres soit suffisant. La plupart des fonctions ayant peu d'arguments, cela ne pose que rarement problème. Mais si une fonction a plus d'arguments que de registres, ou que la fonction utilise beaucoup de variables locales, les arguments en trop doivent être passés par la pile.
On a le même genre de compromis à faire avec la valeur de retour d'une 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. Mais cela ne marche que si la valeur de retour tient dans un registre : un registre contenant 64 bits pourra difficilement contenir une valeur de retour de 5 kilo-octets. Une autre solution consiste à stocker ces valeurs de retour dans la pile d'appel, plus rarement dans une pile des valeurs de retour dédiée (à condition que ces valeurs de retour aient toutes une taille fixe, ce qui n'est pas possible avec certains langages de programmation).
Pour gérer les variables locales, il est possible de réserver une portion de la mémoire statique pour chaque, dédiée au stockage de ces variables locales, mais cela gère mal le cas où une fonction s'appelle elle-même (fonctions récursives). Une autre solution est de réserver un cadre de pile pour les variables locales. Cela demande cependant d'avoir des cadres de pile de taille variable, ce que le processeur et/ou le langage de programmation doit gérer nativement. Le processeur dispose de modes d'adressages spécialisés pour adresser les variables automatiques d'un cadre de pile. Ces derniers ajoutent une constante au pointeur de pile.
Pour résumer, les processeurs processeurs possèdent soit une pile pour tout, soit plusieurs piles spécialisées. La plupart des processeurs ne possèdent qu'une seule pile à la fois pour les adresses de retour, les variables locales, les paramètres, et le reste. La pile utilise alors des cadres de pile de taille variable, dans lesquels on peut ranger plusieurs données. Les variables locales sont souvent regroupées, de même que les arguments, le reste étant placé à une position bien précise dans le cadre de pile.

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

Exécuter une fonction avec une pile demande de faire beaucoup de choses. Au minimum sauvegarder l'adresse de retour, préparer les cadres de pile, gérer le pointeur de pile. Parfois, il est parfois nécessaire d'effectuer d'autres opérations spécifiques. Sur beaucoup de processeurs, ces opérations sont effectuées par le programme lui-même. Le branchement qui appelle le sous-programme est précédé par d'autres instructions s'occupent de sauvegarder l'adresse de retour et faire d'autres opérations préliminaires. Mais sur d'autres processeurs, le branchement d'appel, 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, restaurer le pointeur de pile, etc. Là encore, certains processeurs disposent d'une instruction de retour de fonction dédiée, alors que d'autres font tout en logiciel. Ces derniers émulent l'instruction de retour avec un branchement complété par d'autres instructions. Pour la restauration de l'adresse de retour dans le program counter, l’instruction de retour de fonction fait cela automatiquement.