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 FIFO, 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.
La pile d'appel
[modifier | modifier le wikicode]La pile d'appel est une portion de mémoire qui simule une mémoire FIFO. 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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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.
Si vous regardez bien, vous remarquerez que la donnée 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 donnée à être dépilée (si on n'empile pas de données au-dessus). Ainsi, on sait que dans cette pile, les données sont dépilées dans l'ordre inverse d'empilement. Ainsi, la donnée au sommet de la pile est celle qui a été ajoutée le plus récemment.
_LIFO.svg)
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
[modifier | modifier le wikicode]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 automodifiant.
Les fonctions et procédures logicielles
[modifier | modifier le wikicode]La pile est très utilisée pour faciliter l'implémentation des fonctions, des fonctionnalités très communes des langages de programmation. Pour comprendre ce que sont ces fonctions, il faut faire quelques rappels.
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.
Les langages de programmation actuels ont des fonctionnalités liées aux fonctions, qui simplifient bien la vie des programmeurs.
- En premier lieu, la fonction peut calculer un ou plusieurs résultats, qui sont récupérés par le programme principal et seront utilisés dans divers calculs. Ces résultats sont appelés des valeurs de retour. Généralement, c'est le programmeur qui décide de conserver une donnée et d'en faire une valeur de retour. Celui-ci peut avoir besoin de conserver le résultat d'un calcul pour pouvoir l'utiliser plus tard, par exemple. Ce résultat dépend fortement du sous-programme, et peut être n'importe quelle donnée : nombre entier, nombre flottant, tableau, objet, ou pire encore.
- En second lieu, il est possible de communiquer des valeurs à une fonction : ce sont 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.
- Enfin, 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.
Les instructions d'appel et de retour de fonction
[modifier | modifier le wikicode]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.
Lors de l'appel d'une fonction, outre le branchement, il est parfois nécessaire d'effectuer d'autres opérations dont on ne peut pas encore parler à ce stade. Sur beaucoup de processeurs, ces opérations sont effectuées par le programme. Le branchement qui appelle le sous-programme est précédé par d'autres instructions qui s'en occupent. Mais sur d'autres processeurs, ces opérations et le branchement d'appel sont fusionnés en une seule instruction d'appel de fonction.
De même, outre le branchement, d'autres opérations sont parfois nécessaires pour que le retour de la fonction se passe normalement. Là encore, certains processeurs disposent d'une instruction de retour de fonction dédiée, alors que d'autres non. Ces derniers émulent l'instruction de retour avec un branchement complété par d'autres instructions.
La sauvegarde de l'adresse de retour
[modifier | modifier le wikicode]Le programme doit donc 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. 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 alors, comment savoir à quelle instruction reprendre l'exécution de notre programme, une fois notre sous-programme terminé ? La seule solution est de sauvegarder l'adresse de retour lorsqu'on appelle la fonction ! Une fois le sous-programme fini, faut reprendre l’exécution de notre programme principal là où il s'était arrêté pour laisser la place au sous-programme. Pour cela, il suffit de charger l'adresse de retour dans un registre et d’exécuter un branchement inconditionnel vers cette adresse de retour.
La sauvegarde de l'adresse de retour est effectuée soit par l'instruction d'appel de fonction, soit par une instruction de branchement spéciale. L'instruction de branchement spéciale est souvent appelée branch and link, elle effectue un branchement et mémorise l'adresse de retour dans un registre. L'instruction d'appel de fonction fait cela, mais aussi d'autres choses (voir plus bas).
Pour la restauration de l'adresse de retour dans le program counter, c'est la même chose. Sur certains processeurs, il faut charger l'adresse de retour dans un registre et utiliser un branchement inconditionnel vers cette adresse. Le branchement inconditionnel en question est un branchement inconditionnel indirect. Sur d'autres, l’instruction de retour de fonction fait cela automatiquement. C'est un branchement inconditionnel, mais l'adresse de retour est adressée implicitement.
La sauvegarde des registres
[modifier | modifier le wikicode]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 pile, une sauvegarde de ceux-ci. 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é !
Cette sauvegarde peut être effectuées automatiquement par l'instruction d'appel de fonction, mais c'est plutôt rare. La plupart du temps, elle est effectuée registre par registre par le logiciel, un petit morceau de code se chargeant de sauvegarder les registres. Plus rarement, certains processeurs ont une instruction pour sauvegarder les registres du processeur. 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
L'usage de la pile d'appel par les fonctions
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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.
