Tableaux et adresses

Les dix instructions employées ici

Ce chapitre n'introduit aucune instruction nouvelle : les dix qu'il emploie ont toutes été rencontrées avant. Elles reviennent en revanche toutes les trois ou quatre lignes, et un lecteur qui les a croisées il y a quelques jours a le droit de ne plus se souvenir de leur forme exacte. Les voici rassemblées une fois pour toutes, à garder sous les yeux le temps du chapitre.

Le détail de chaque famille, avec les variantes que ce chapitre n'emploie pas, se trouve dans le mémento du jeu d'instructions.

Un mot enfin sur les figures, qui ne sont pas seulement à regarder tourner. Le bouton « Modifier le programme » ouvre le texte du programme affiché : chaque frappe le réassemble et le relance, et un autre bouton ramène à la version d'origine. Les consignes qui demandent de changer une valeur et de relancer se suivent donc sans quitter la page, et une instruction dont le rôle reste flou se comprend souvent mieux en la supprimant pour voir ce qui manque ensuite.

Charger une adresse, puis lire à travers elle

Une déclaration données: pose des valeurs en mémoire et donne un nom à l'adresse de la première. Ce nom n'est pas une variable : c'est une adresse, et elle doit passer par un registre avant que quoi que ce soit ne soit lu. Le geste tient en deux temps, la puis lw, et il ne changera plus de tout le module.

Cinq pas, t1 à 12 et t2 à 5. La figure signale les deux accès, à l'adresse 0x1000 puis à l'adresse 0x1004 : quatre octets d'écart pour un élément d'écart. Entre les deux, addi t0, t0, 4 a fait passer t0 de 4096 à 4100, c'est-à-dire de 0x1000 à 0x1004. Le registre t0 ne contient pas une note : il contient l'endroit où en chercher une.

La colonne des instructions réelles mérite un regard. La ligne la t0, notes y donne lui t0, 1, suivie d'un addi zero, zero, 0 qui ne fait rien : l'assembleur réserve deux instructions pour charger une adresse, parce qu'une adresse ne tient pas toujours sur douze bits, et comble avec une instruction neutre quand une seule suffit.

L'indice n'existe pas, il se calcule

L'accès t[i] d'un langage de haut niveau se décompose en quatre choses, dont aucune n'est cachée ici : une adresse de base, un indice, une taille d'élément, et une addition. L'adresse cherchée vaut base plus indice multiplié par la taille de l'élément. Pour des mots de quatre octets, multiplier par quatre revient à décaler de deux bits vers la gauche, ce que slli fait en une instruction, faute de multiplication dans RV32I.

Le registre t1 vaut 8 après le décalage, 4104 après l'addition, et la lecture rapporte -3, le troisième élément. Les trois instructions du milieu sont exactement ce qu'un compilateur produit pour t[i], et elles expliquent d'un coup plusieurs mystères : pourquoi un tableau est indexé à partir de zéro, puisque l'élément zéro est celui qui se trouve à l'adresse de base plus rien ; pourquoi la taille d'élément doit être connue à la compilation ; et pourquoi l'accès à un élément quelconque coûte le même temps quel que soit l'indice.

Parcourir plutôt que recalculer

Rien n'oblige à repartir de la base à chaque tour. Un parcours complet se fait plus simplement en déplaçant le registre d'adresse, une boucle du chapitre précédent tenant le compte des éléments restants.

Trente-cinq pas, t2 à 61, et cinq lectures aux adresses 0x1000, 0x1004, 0x1008, 0x100c et 0x1010. Deux registres suffisent à tenir le parcours : t0 dit où lire, t1 dit combien de fois encore. Le registre t0 finit à 4116, une case au-delà du dernier élément, ce qui est normal et mérite d'être noté : après un parcours, le pointeur désigne la fin, pas le dernier élément.

Écrire dans le tableau se fait avec la même adresse, et l'instruction symétrique.

Trente-deux pas, et le tableau contient à la fin 24, 10, -6 et 80. Chaque tour lit, calcule, range au même endroit. La figure signale les écritures avec la valeur précédente, ce qui rend visible le fait qu'un tableau modifié sur place perd ses valeurs d'origine sans laisser de trace.

Une chaîne est un tableau d'octets

Un texte suit exactement la même convention, avec deux différences. La taille d'un élément vaut un octet et non quatre, donc l'adresse avance de un en un. Et la longueur n'est écrite nulle part : la fin est signalée par un octet nul posé après le dernier caractère. Le parcours ne compte donc pas, il cherche.

Cinquante-cinq pas, et t1 finit à 10, la longueur du mot. Les valeurs prises par t2 sont 97, 115, 115, 101, 109, 98, 108, 101, 117, 114, puis 0 : les codes des lettres, lus un octet à la fois par lb, et le zéro terminal trouvé à l'adresse 0x100a. Le décalage est de 1 à chaque tour, jamais de 4, parce que la taille d'un élément est ici d'un octet.

La taille d'élément n'est donc pas une propriété de la mémoire, c'est un choix de lecture. Rien n'empêche de lire quatre octets d'un texte d'un seul coup.

Les deux lectures d'octet donnent 65 et 68, les codes de A et de D. La lecture de mot, à la même adresse de base, donne 1 145 258 561. Ce nombre n'a aucun sens en tant que nombre, et il est pourtant la lecture exacte des mêmes quatre octets, assemblés dans l'ordre où le processeur les range. Les octets ne changent pas : c'est l'instruction qui décide de les voir comme un caractère ou comme un nombre de trente-deux bits.

Noter au passage le décalage écrit dans l'instruction, 3(t0), qui évite de déplacer le registre. Les deux écritures sont équivalentes, et la première est préférable quand l'adresse de base doit être conservée.

Sortir du tableau ne provoque rien

Voici la différence la plus nette entre ce module et un langage de haut niveau. En Python, lire t[7] dans une liste de trois éléments lève une exception qui arrête tout. Ici, il ne se passe rien du tout.

Le tableau notes occupe douze octets, de 0x1000 à 0x100b. La première lecture, au décalage 8, atteint son dernier élément et donne -3. La deuxième, au décalage 12, sort du tableau et donne 777 : c'est la valeur de seuil, déclarée juste après et posée à l'adresse 0x100c. La troisième, au décalage 16, atteint une case où rien n'a jamais été écrit et donne 0. Aucune des trois n'est signalée comme une faute, et le programme se termine normalement.

La mémoire n'a pas de bord. Un tableau n'existe pas pour le processeur, donc sa fin n'existe pas davantage. Lire au-delà rapporte ce qui se trouve à côté : une autre donnée, un reste d'exécution précédente, ou des octets jamais écrits. Le programme continue avec une valeur fausse, et la faute se manifeste bien plus loin, sous une forme qui n'a plus aucun rapport avec sa cause. C'est le mécanisme de fond des vulnérabilités de lecture hors limites, et l'explication de pourquoi les langages qui vérifient l'indice acceptent d'en payer le prix.

Une erreur est bien signalée, mais elle porte sur autre chose : l'alignement. Un mot de quatre octets se lit à une adresse multiple de quatre, et le moteur refuse toute autre adresse.

L'exécution s'interrompt avec le message qui désigne 0x1001 comme non multiple de quatre. La contrainte vient du matériel, qui va chercher la mémoire par blocs alignés, et elle explique une part des règles de disposition que les langages système imposent aux structures de données. Il est donc parfaitement possible de sortir d'un tableau sans être inquiété, et parfaitement impossible de lire un mot une case trop loin dans le mauvais sens.

Deux dimensions dans une seule suite de cases

Une grille n'a pas d'existence propre non plus. Elle est rangée ligne après ligne dans la même suite de cases, et l'élément de coordonnées ligne et colonne occupe l'indice ligne × largeur + colonne. La formule ajoute une multiplication à celle qui convertit l'indice en octets.

Sept pas, et t2 reçoit 31. Le registre t1 passe par 8, la ligne multipliée par la largeur, puis 9, l'indice dans la suite, puis 36, le même indice converti en octets, puis 4132, soit 0x1024, l'adresse finale. Les deux slli valent tous deux « multiplier par quatre », mais pour des raisons distinctes : le premier parce que la grille a quatre colonnes, le second parce qu'un mot occupe quatre octets. Les deux coïncident ici, et il serait imprudent d'en tirer une règle. Une grille de trois colonnes demanderait une multiplication par trois, donc des additions répétées, puisque RV32I ne multiplie pas.