Appeler

Sauter, et savoir revenir

Un saut ordinaire, j fin, va quelque part et ne revient pas. Pour qu'un fragment de code puisse servir depuis plusieurs endroits, il faut qu'il sache où repartir, et cette information change à chaque appel. Elle ne peut donc pas être écrite dans le fragment : il faut la lui donner.

L'instruction jal fait les deux choses d'un coup. Elle range dans un registre l'adresse de l'instruction qui suit l'appel, puis elle saute. Le registre utilisé par convention est ra, pour return address, l'adresse de retour.

Le premier pas range 4 dans ra, c'est-à-dire 0x4, et le compteur ordinal saute à 0x8 où commence doubler. Cette valeur 4 n'a pas été choisie par qui a écrit le programme : elle est calculée à l'exécution à partir de l'adresse de l'appel. Le même code appelé depuis un autre endroit y trouverait une autre adresse.

Le retour s'écrit ret, et la figure affiche l'instruction réelle à côté : jalr zero, ra, 0. Ce n'est pas un hasard de notation. jalr est la sœur de jal : elle saute à une adresse contenue dans un registre au lieu d'une adresse écrite dans l'instruction, et elle range elle aussi l'adresse de retour, ici dans zero, c'est-à-dire nulle part. Revenir d'une fonction, c'est sauter à l'adresse que ra contient, sans rien mémoriser.

Une seule case pour l'adresse de retour

ra est un registre, donc une case unique. Une fonction qui en appelle une autre exécute un second jal, qui range une nouvelle adresse dans cette même case. L'adresse qui s'y trouvait est perdue, et la première fonction ne sait plus où revenir.

Le programme suivant contient exactement cette faute. La fonction f est appelée par le programme principal, puis elle appelle g. Rien d'autre.

Les deux valeurs prises par ra racontent toute l'histoire. Au premier appel, ra reçoit 4, l'adresse du j fin qui suit. Quand f appelle g, ra reçoit 16, soit 0x10 : l'adresse du addi a0, a0, 10 situé à l'intérieur de f. Le 4 a disparu.

g revient correctement, puisque ra contient bien ce qu'il faut pour elle. Puis f exécute son ret, qui saute à ra, c'est-à-dire à 0x10, c'est-à-dire à l'intérieur de f juste après l'appel de g. Le programme ajoute dix, revient à 0x10, ajoute dix, revient à 0x10. La figure s'arrête sur le message de limite parce que ce programme ne se termine jamais.

Ce comportement est inhabituel, et c'est ce qui le rend instructif : le programme ne plante pas, ne refuse rien, et boucle sur trois instructions bien écrites. La faute n'est dans aucune d'elles ; elle est dans l'idée qu'un registre unique pourrait retenir deux adresses à la fois.

Sauver ra sur la pile

Il faut donc mettre l'adresse de retour à l'abri pendant l'appel imbriqué, et la reprendre avant de revenir. La pile du chapitre précédent est faite pour cela : un mot réservé à l'entrée, rendu à la sortie.

Quatre instructions ajoutées, et le programme se termine. Les deux premières forment le prologue de f : réserver un mot, y ranger ra. Les deux dernières forment son épilogue : reprendre ra, rendre le mot. Entre les deux, f peut appeler qui elle veut et autant de fois qu'elle veut, puisque son adresse de retour n'est plus dans un registre que l'appel écrase, mais dans une case de pile qui lui appartient.

La fonction g, elle, n'a pas de prologue et n'en a pas besoin : elle n'appelle personne, donc rien n'écrase son ra. Une fonction qui n'appelle aucune autre fonction s'appelle une fonction feuille, et elle se passe de cadre de pile.

L'accord qui rend un code appelable

Deux fonctions écrites par deux personnes différentes doivent se mettre d'accord sur trois points : où l'appelant dépose les arguments, où l'appelé dépose le résultat, et quels registres survivent à l'appel. Aucun de ces points n'est imposé par le matériel. Les registres n'ont pas de rôle câblé, a0 et t0 sont deux cases identiques, et le processeur exécuterait sans broncher n'importe quelle autre répartition.

L'accord en vigueur pour RISC-V répartit les registres ainsi.

La fonction total ne contient aucune indication sur ses arguments : elle additionne a0, a1 et a2 parce que la convention dit que c'est là qu'ils se trouvent. Elle range son résultat dans a0 pour la même raison. L'appelant, de son côté, remplit a0 à a2 avant chaque appel et lit a0 après. Ni l'un ni l'autre n'a besoin de connaître le code de l'autre.

Un détail passe souvent inaperçu : la fonction écrase a0, qui contenait un argument. C'est permis, et c'est même la norme. Les registres d'arguments appartiennent à l'appelé pendant l'exécution de l'appel, et l'appelant qui tient à son argument doit le recopier ailleurs avant d'appeler.

Les registres que l'appelé peut détruire

La ligne de partage entre les registres t et les registres s n'est pas un raffinement théorique. Elle décide de qui doit recopier quoi, et l'ignorer produit des résultats faux qu'aucun outil ne signale.

Le programme suivant additionne le double de trois valeurs. L'appelant garde son total dans t0. La fonction doubler se sert elle aussi de t0, ce que la convention l'autorise à faire.

Le total annoncé est 36, le total juste est 40. Rien n'a été signalé. L'appelant a confié à t0 une valeur qui devait survivre à trois appels, alors que t0 est précisément un registre dont la convention dit qu'il ne survit pas. La fonction appelée n'a commis aucune faute ; l'appelant en a commis une, et c'est lui qui obtient un résultat faux.

La même chose dans les règles

Il suffit de déplacer le total dans un registre sauvegardé. L'appelant range son cumul dans s0, et la convention garantit qu'aucune fonction bien écrite ne le touchera. La contrepartie est du côté de l'appelé : une fonction qui veut utiliser un registre s doit le sauver sur la pile et le rendre tel qu'elle l'a trouvé.

Le total est maintenant juste. Le prix payé est visible dans la figure : à chaque appel, doubler empile s1, s'en sert, le reprend et rend la place. Deux accès mémoire par appel, pour une fonction qui ne fait qu'une addition. C'est la raison d'être de la distinction entre t et s : elle laisse le programmeur choisir quelle moitié du coût il paie, la recopie par l'appelant pour les t, la sauvegarde par l'appelé pour les s.

La récursion, une fois la pile comprise

Une fonction récursive est une fonction qui s'appelle elle-même. Elle ne demande aucun mécanisme nouveau : l'adresse de retour se sauve comme avant, et les valeurs locales se rangent dans un cadre de pile qui appartient à cet appel-là. Deux appels en cours ont deux cadres à deux adresses différentes, et ne se marchent pas dessus.

La fonction suivante calcule la somme des entiers de 1 à a0. Le jeu d'instructions de base ne sait pas multiplier, et cette somme n'en a pas besoin : elle s'écrit avec une addition par appel.

Le cadre réservé par chaque appel fait huit octets : un mot pour l'adresse de retour à 4(sp), un mot pour l'argument à 0(sp). L'argument doit être sauvé parce que l'appel récursif va écraser a0, d'abord en le décrémentant, puis en y déposant son résultat. Après le retour de l'appel imbriqué, lw t0, 0(sp) reprend l'argument de cet appel-ci, et l'addition compose le résultat.

La figure montre la pile descendre de 0x1ff8 à 0x1fe0 pendant la descente, puis remonter case par case pendant les retours. Les adresses de retour rangées dans les cadres se lisent aussi : celle du premier cadre vaut 4, l'adresse dans le programme principal, et les trois autres valent 32, c'est-à-dire 0x20, l'adresse de l'instruction qui suit l'appel récursif. Trois appels récursifs, trois copies de la même adresse de retour, chacune rangée dans son propre cadre.

Avec registres: a0 = 5, le même programme rend 15 et la pile descend jusqu'à 0x1fd0. La profondeur de la pile est proportionnelle à l'argument, et c'est la raison pour laquelle une récursion trop profonde finit par rencontrer les données. Le message qu'un langage de haut niveau affiche alors, en parlant de profondeur maximale de récursion, est la traduction de ce qui se voit ici.

L'adresse de retour et les variables locales partagent la pile

Voici le point qui justifie le chapitre entier, et qui n'a rien d'une curiosité.

Un cadre de pile contient l'adresse de retour et les variables locales de la fonction. Ces deux choses sont côte à côte dans la même zone, gérées par le même registre, écrites par les mêmes instructions. Rien ne les sépare, rien ne les distingue, et rien ne vérifie qu'une écriture destinée à une variable locale reste dans les limites de cette variable.

La fonction suivante réserve un cadre de douze octets : deux mots de tampon, à 0(sp) et 4(sp), et l'adresse de retour au-dessus, à 8(sp). Elle remplit ensuite le tampon d'autant de mots que a0 en demande. Avec deux, tout se passe bien.

La valeur écrite, 0x41414141, est le mot formé de quatre octets valant 0x41, le code de la lettre A. Elle est choisie pour être reconnaissable, et la figure montre d'ailleurs que li la produit en deux instructions, lui puis addi, puisqu'elle dépasse largement les douze bits d'un immédiat.

Il suffit maintenant de demander trois mots au lieu de deux. Une seule valeur change dans tout le programme.

Le troisième tour de boucle écrit à 8(sp), qui n'est plus du tampon mais la case où le prologue avait rangé l'adresse de retour. Le 4 qui s'y trouvait est remplacé par 1 094 795 585, c'est-à-dire 0x41414141. Aucune erreur n'est signalée à ce moment-là : une écriture en mémoire est une écriture en mémoire, et cette case est aussi légitime qu'une autre.

L'épilogue s'exécute ensuite normalement. lw ra, 8(sp) recharge consciencieusement ce qu'il trouve, addi sp, sp, 12 rend le cadre, et ret saute à l'adresse contenue dans ra. Le compteur ordinal prend donc la valeur 0x41414140, et le programme s'arrête là : il n'y a aucune instruction à cette adresse.

Ce qui se produit ensuite dépend de la machine. Ici, le compteur ordinal tombe sur une adresse vide et la figure le dit. Sur un ordinateur ordinaire, l'adresse existe, elle contient des octets, et le processeur les exécute comme des instructions : soit il rencontre très vite quelque chose d'impossible et le système arrête le programme, soit l'adresse a été choisie avec soin et le programme continue de tourner en faisant autre chose que ce que son auteur a écrit.

Les protections modernes ne suppriment pas ce mécanisme, elles le rendent difficile à exploiter : disposition de la mémoire tirée au hasard à chaque lancement, valeur témoin posée devant l'adresse de retour et vérifiée avant le ret, zones de mémoire marquées comme non exécutables. Chacune de ces défenses se comprend d'un coup quand on a vu la figure précédente, et reste une formule creuse tant qu'on ne l'a pas vue.

La méthode

1. Écrire le prologue et l'épilogue avant le corps de toute fonction qui contient un appel : réserver le cadre, y ranger ra, et taper immédiatement les deux instructions symétriques de sortie.
2. Compter le cadre en mots : un mot pour ra, un mot par valeur locale qui doit survivre à un appel, arrondi au multiple de quatre octets.
3. Choisir les registres selon leur durée de vie, et non selon leur nom : un t pour ce qui ne franchit aucun appel, un s pour ce qui doit survivre, sachant qu'un s employé par une fonction doit être sauvé par elle.
4. Relever ra dans la figure juste après chaque jal, et vérifier que la valeur correspond bien à l'adresse de l'instruction suivante dans la colonne de gauche.
5. Vérifier que sp retrouve sa valeur d'entrée à la sortie de chaque fonction, exactement comme au chapitre précédent : un écart signale un cadre mal rendu, qui fera revenir la fonction n'importe où.
6. Comparer la taille réservée et la quantité écrite dès qu'un tampon local est rempli par une boucle, puisque c'est la seule chose qui sépare un programme correct d'un programme dont un tiers choisit la suite.

Synthèse

• jal range dans ra l'adresse de l'instruction suivante, puis saute. ret est jalr zero, ra, 0 : le compteur ordinal prend la valeur de ra. Il n'existe aucune instruction « appeler une fonction » au-delà de cela.
• ra est une case unique : une fonction qui en appelle une autre perd son adresse de retour et revient à l'intérieur d'elle-même, ce qui produit une boucle sans fin plutôt qu'une erreur. La solution est de sauver ra sur la pile à l'entrée et de le reprendre à la sortie.
• La convention d'appel place les arguments dans a0 à a7 et le résultat dans a0, laisse t0 à t6 à la disposition de l'appelé, et exige que s0 à s11 soient rendus intacts. Ce n'est pas une règle du matériel : c'est un accord, et l'enfreindre rend simplement un code inappelable.
• Confier une valeur à un registre t pendant un appel donne un résultat faux sans message : le programme annonce 36 là où la somme vaut 40.
• Une fonction récursive réserve un cadre par appel, ce qui permet à plusieurs exécutions de la même fonction de coexister. La pile descend pendant la descente et remonte pendant les retours, et sa profondeur suit celle de la récursion.
• L'adresse de retour et les variables locales partagent le même cadre. Une écriture qui dépasse un tampon local écrase l'adresse de retour, et le ret saute là où la donnée écrite le dit : ici 0x41414140, où il n'y a aucune instruction.

Tout ce que ce chapitre construit à la main, un compilateur l'écrit des milliers de fois par programme. Ce que le compilateur écrit met une fonction de haut niveau en regard de l'assembleur qu'elle devient, et y retrouve le prologue, le cadre et l'épilogue.