Fonctionnement d'un ordinateur/Le modèle mémoire : alignement et boutisme

Outre le jeu d'instruction et l'architecture interne, les processeurs différent par la façon dont ils lisent et écrivent la mémoire. On pourrait croire qu'il n'y a pas grande différence entre processeurs dans la façon dont ils gèrent la mémoire. Mais ce n'est pas le cas : des différences existent qui peuvent avoir un effet assez important. Dans ce chapitre, on va parler de l'endianess du processeur et de son alignement mémoire : on va s'intéresser à la façon dont le processeur va repartir en mémoire les octets des données qu'il manipule. Ces deux paramètres sont sûrement déjà connus de ceux qui ont une expérience de la programmation assez conséquente. Les autres apprendront ce que c'est dans ce chapitre.

Le boutisme

On peut introduire la notion de boutisme par une analogie avec les langues humaines : certaines s’écrivent de gauche à droite et d'autres de droite à gauche. Dans un ordinateur, c'est pareil avec les octets des mots mémoire : on peut les écrire soit de gauche à droite, soit de droite à gauche. Quand on veut parler de cet ordre d'écriture, on parle de boutisme (endianness).

Les différents types de boutisme

Les deux types de boutisme les plus simples sont le gros-boutisme et le petit-boutisme. Sur les processeurs gros-boutistes, la donnée est stockée des adresses les plus faibles vers les adresses plus grande. Pour rendre cela plus clair, prenons un entier qui prend plusieurs octets et qui est stocké entre deux adresses. L'octet de poids fort de l'entier est stocké dans l'adresse la plus faible, et inversement pour le poids faible qui est stocké dans l'adresse la plus grande. Sur les processeurs petit-boutistes, c'est l'inverse : l'octet de poids faible de notre donnée est stocké dans la case mémoire ayant l'adresse la plus faible. La donnée est donc stockée dans l'ordre inverse pour les octets.

Certains processeurs sont un peu plus souples : ils laissent le choix du boutisme. Sur ces processeurs, on peut configurer le boutisme en modifiant un bit dans un registre du processeur : il faut mettre ce bit à 1 pour du petit-boutiste, et à 0 pour du gros-boutiste, par exemple. Ces processeurs sont dits bi-boutistes.

Petit et gros-boutisme ont pour particularité que la taille des mots ne change pas vraiment l'organisation des octets. Peu importe la taille d'un mot, celui-ci se lit toujours de gauche à droite, ou de droite à gauche. Cela n’apparaît pas avec les techniques de boutismes plus compliquées.

Comparaison entre big-endian et little-endian, pour des tailles de 16 et 32 bits.

Comparaison entre un nombre codé en gros-boutiste pur, et un nombre gros-boutiste dont les octets sont rangés dans un groupe en petit-boutiste. Le nombre en question est 0x 0A 0B 0C 0D, en hexadécimal, le premier mot mémoire étant indiqué en jaune, le second en blanc.

Certains processeurs ont des boutismes plus compliqués, où chaque mot mémoire est découpé en plusieurs groupes d'octets. Il faut alors prendre en compte le boutisme des octets dans le groupe, mais aussi le boutisme des groupes eux-mêmes. On distingue ainsi un boutisme inter-groupe (le boutisme des groupes eux-même) et un boutisme intra-groupe (l'ordre des octets dans chaque groupe), tout deux pouvant être gros-boutiste ou petit-boutiste. Si l'ordre intra-groupe est identique à l'ordre inter-groupe, alors on retrouve du gros- ou petit-boutiste normal. Mais les choses changent si jamais l'ordre inter-groupe et intra-groupe sont différents. Dans ces conditions, on doit préciser un ordre d’inversion des mots mémoire (byte-swap), qui précise si les octets doivent être inversés dans un mot mémoire processeur, en plus de préciser si l'ordre des mots mémoire est petit- ou gros-boutiste.

Avantages, inconvénients et usage

Le choix entre petit boutisme et gros boutisme est généralement une simple affaire de convention. Il n'y a pas d'avantage vraiment probant pour l'une ou l'autre de ces deux méthodes. Cela ne veut pas dire que n'y a pas d'avantage ou d'inconvénient d'une méthode sur l'autre, mais que ceux-ci sont mineurs. Dans les faits, il y a autant d'architectures petit- que de gros-boutistes, la plupart des architectures récentes étant bi-boutistes. Précisons que le jeu d'instruction x86 est de type petit-boutiste. Si on quitte le domaine des jeu d'instruction, il faut savoir que les protocoles réseaux et les formats de fichiers imposent un boutisme particulier. Les protocoles réseaux actuels (TCP-IP) sont de type gros-boutiste, ce qui impose de convertir les données réseaux avant de les utiliser sur les PC modernes. Et au passage, si le gros-boutisme est utilisé dans les protocoles réseau, alors que le petit-boutisme est roi sur le x86, c'est pour des raisons pratiques, que nous allons aborder ci-dessous.

Le gros-boutisme est très facile à lire pour les humains. Les nombres en gros-boutistes se lisent de droite à gauche, comme il est d'usage dans les langues indo-européennes, alors que les nombres en petit boutistes se lisent dans l'ordre inverse de lecture. Pour la lecture en hexadécimal, il faut inverser l'ordre des octets, mais il faut garder l'ordre des chiffres dans chaque octet. Par exemple, le nombre 0x015665 (87 653 en décimal) se lit 0x015665 en gros-boutiste, mais 0x655601 en petit-boutiste. Et je ne vous raconte pas ce que cela donne avec un byte-swap... Cette différence pose problème quand on doit lire des fichiers, du code machine ou des paquets réseau, avec un éditeur hexadécimal. Alors certes, la plupart des professionnels lisent directement les données en passant par des outils d'analyse qui se chargent d'afficher les nombres en gros-boutiste, voire en décimal. Un professionnel a à sa disposition du désassembleur pour le code machine, des analyseurs de paquets pour les paquets réseau, des décodeurs de fichiers pour les fichiers, des analyseurs de dump mémoire pour l'analyse de la mémoire, etc. Cependant, le gros-boutisme reste un avantage quand on utilise un éditeur hexadécimal, quel que soit l'usage. En conséquence, le gros-boutiste a été historiquement pas mal utilisé dans les protocoles réseaux et les formats de fichiers. Par contre, cet avantage de lecture a dû faire face à divers désavantages pour les architectures de processeur.

Le petit-boutisme peut avoir des avantages dans certaines conditions bien précises, sur certains jeux d'instruction particuliers. En premier lieu, il est utile pour les architectures qui peuvent lire des mots de différentes tailles. C'est le cas sur le x86, où l'on peut décider de lire des mots de 8, 16, 32, voire 64 bits à partir d'une adresse mémoire. Avec le petit-boutisme, on s'assure qu'une telle lecture charge bien la même valeur, le même nombre. Par exemple, imaginons que je stocke le nombre 0x 14 25 36 48 sur un mot mémoire, en petit-boutiste. En petit-boutiste, une opération de lecture reverra soit les 8 bits de poids faible (0x 48), soit les 16 bits de poids faible (0x 36 48), soit le nombre complet. Ce ne serait pas le cas en gros-boutiste, où les lectures reverraient respectivement 0x 14, 0x 14 25 et 0x 14 25 36 48. Avec le gros-boutisme, de telles opérations de lecture n'ont pas vraiment de sens. À la rigueur, elles peuvent servir à obtenir une approximation d'un grand nombre entier, mais cela sert peu et peut se faire autrement avec des opérations bit-à-bit. En soit, cet avantage est assez limité et n'est utile que pour les compilateurs et les programmeurs en assembleur.

Un autre avantage est un gain de performance pour certaines opérations. Les instructions qui gagnent en performance sont les opérations où on doit additionner un nombre de plusieurs octets sur un processeur qui ne fait les calculs qu'octet par octet. En clair, le processeur dispose d'instructions de calcul qui additionnent des nombres de 16, 32 ou 64 bit, voire plus. Mais à l'intérieur du processeur, les calculs sont faits octets par octets, l'unité de calcul ne pouvant qu'additionner deux nombres de 8 bits à la fois. Dans ce cas, le petit-boutisme garantit que l'addition des octets se fait dans le bon ordre, en commençant par les octets de poids faible pour progresser vers les octets de poids fort. La gestion de la propagation de la retenue est alors assez simple : il suffit de mémoriser la retenue de l'addition précédente dans un registre, avant de passer à l'addition d'octets suivante. En gros-boutisme, la propagation de la retenue pose de plus gros problèmes...

Pour résumer, les avantages et inconvénients de chaque boutisme sont mineurs. Le gain en performance est nul sur les architectures modernes, qui ont des unités de calcul capables de faire des additions multi-octets. L'usage d'opérations de lecture de taille variable est aujourd'hui tombé en désuétude, vu que cela ne sert pas à grand chose et complexifie le jeu d'instruction. Enfin, l'avantage de lecture n'est utile que dans situations tellement rares qu'on peut légitimement questionner son statut d'avantage. En bref, les différentes formes de boutisme se valent.

L'alignement mémoire

Il arrive que le bus de données ait une largeur de plusieurs cases mémoire. Le processeur peut charger 2, 4 ou 8 cases mémoire d'un seul coup (parfois plus). Une donnée qui a la même taille que le bus de données est appelée un mot mémoire. Quand on veut accéder à une donnée sur un bus plus grand que celle-ci, le processeur ignore les mots mémoire en trop.

Exemple du chargement d'un octet dans un registre de trois octets.

Sur certains processeurs, il existe des restrictions sur la place de chaque mot en mémoire, restrictions résumées sous le nom d'alignement mémoire.

Sans alignement mémoire

Sans alignement, on peut lire ou écrire un mot, peu importe son adresse. Pour donner un exemple, je peux parfaitement lire une donnée de 16 bits localisée à l'adresse 4, puis lire une autre donnée de 16 bits localisée à l'adresse 5 sans aucun problème.

Chargement d'une donnée sur un processeur sans contraintes d'alignement.

Avec alignement mémoire

D'autres processeurs imposent des restrictions dans la façon de gérer ces mots : ils imposent un alignement mémoire. Tout se passe comme si la mémoire était découpée en blocs de la taille d'un mot mémoire et que le processeur accédait à des blocs en entier. Par contre, la capacité de la mémoire reste inchangée, ce qui fait que le nombre d'adresses utilisables diminue : il n'y a plus besoin que d'une adresse par mot mémoire et non par octet.

Chargement d'une donnée sur un processeur avec contraintes d'alignement.

La validité des adresses avec alignement mémoire

Avec cette technique, il y a une différence entre l'adresse d'un mot et l'adresses d'un octet. Les octets ont une adresse qui est gérée par le processeur, alors que la mémoire ne gère que les adresses des mots. Par convention, l'adresse d'un mot est l'adresse de son octet de poids faible. Les autres octets du mot ne sont pas adressables par la mémoire. Par exemple, si on prend un mot de 8 octets, on est certain qu'une adresse sur 8 disparaîtra. L'adresse du mot est utilisée pour communiquer avec la mémoire, mais cela ne signifie pas que l'adresse des octets est inutile au-delà du calcul de l'adresse du mot. En effet, l'accès à un octet précis est encore possible : le processeur lit un mot entier, sélectionne l'octet adéquat et oublie les autres. Et pour cela, il doit déterminer la position du octet dans le mot à partir de l'adresse du octet est utile. Ses bits de poids faibles donnent la position du octet dans le mot.

Prenons un processeur ayant des mots de 4 octets et répertorions les adresses utilisables. Le premier mot contient les octets d'adresse 0, 1, 2 et 3. L'adresse zéro est l'adresse de l'octet de poids faible et sert donc d'adresse au premier mot, les autres sont inutilisables sur le bus mémoire. Le second mot contient les adresses 4, 5, 6 et 7, l'adresse 4 est l'adresse du mot, les autres sont inutilisables. Et ainsi de suite. Si on fait une liste exhaustive des adresses valides et invalides, on remarque que seules les adresses multiples de 4 sont utilisables. Et ceux qui sont encore plus observateurs remarqueront que 4 est la taille d'un mot.

Dans l'exemple précédent, les adresses utilisables sont multiples de la taille d'un mot. Sachez que cela fonctionne quelle que soit la taille du mot. Si N est la taille d'un mot, alors seules les adresses multiples de N seront utilisables. Avec ce résultat, on peut trouver une procédure qui nous donne l'adresse d'un mot à partir de l'adresse d'un octet : il suffit de diviser l'adresse du octet par N (le nombre d'octets dans un mot). Et le reste de cette division donne la position du octet dans le mot : un reste de 0 nous dit que l'octet est le premier du mot, un reste de 1 nous dit qu'il est le second, etc.

Adresse d'un mot avec alignement mémoire strict.

L'usage d'octets qui ne sont pas des puissances de 2 posent quelques problèmes techniques en termes d’adressage, ce qui fait que tous les mots ont une taille égale à une puissance de deux. La première raison est que cela permet d'économiser des fils sur le bus d'adresse. Si la taille d'un mot est égale à $2^{n}$, seules les adresses multiples de $2^{n}$ seront utilisables. Or, ces adresses se reconnaissent facilement : leurs n bits de poids faibles valent zéro. On n'a donc pas besoin de câbler les fils correspondant à ces bits de poids faible. En second lieu, cela permet de simplifier le calcul de l'adresse d'un mot, ainsi que le calcul de la position du octet dans le mot. Rappelons que pour un mot de N octets, le calcul de l'adresse du mot est une division, alors que celui de la position du octet est un modulo. Avec $N=2^{n}$, la division est un simple décalage et le modulo est un simple ET logique, deux opérations très rapides par rapport à une division généraliste. Les calculs d'adresse sont donc beaucoup plus rapides et très simples.

Les accès mémoire non-alignés

Maintenant imaginons un cas particulier : je dispose d'un processeur utilisant des mots de 4 octets. Je dispose aussi d'un programme qui doit manipuler un caractère stocké sur 1 octet, un entier de 4 octets et une donnée de deux octets. Mais un problème se pose : le programme qui manipule ces données a été programmé par quelqu'un qui n'était pas au courant de ces histoire d'alignement, et il a répartit mes données un peu n'importe comment. Supposons que cet entier soit stocké à une adresse non-multiple de 4. Par exemple :

Adresse	Octet 4	Octet 3	Octet 2	Octet 1
0x 0000 0000	Caractère	Entier	Entier	Entier
0x 0000 0004	Entier	Donnée	Donnée
0x 0000 0008

Pour charger mon caractère dans un registre, pas de problèmes : celui-ci tient dans un mot. Il me suffit alors de charger mon mot dans un registre en utilisant une instruction de mon processeur qui charge un octet. Pour ma donnée de 2 octets, pas de problèmes non plus ! Le processeur charge le mot entier en ne sélectionne que les octets utiles, chose possible avec quelques décalage et un masque. Mais les problèmes arrivent quand il s'agit de charger l'entier. L'entier est en effet stocké sur deux mots différents, et on ne peut le charger en une seule fois : on dit que l'entier n'est pas aligné en mémoire.

Dans ce cas, il peut se passer des tas de choses suivant le processeur. Sur certains processeurs, la donnée est chargée en deux fois : c'est légèrement plus lent que la charger en une seule fois, mais ça passe. Mais sur d'autres processeurs, la situation devient nettement plus grave : le processeur ne peut en effet gérer ce genre d'accès mémoire dans ses circuits et considère qu'il est face à une erreur, similaire à une division par zéro ou quelque chose dans le genre. Il va alors interrompre le programme en cours d’exécution et exécuter un petit sous-programme qui gérera cette erreur. On dit que notre processeur effectue une exception matérielle. Si on est chanceux, ce programme de gestion d'erreur chargera cette donnée en deux fois : ça prend beaucoup de temps. Mais sur d'autres processeurs, le programme responsable de cet accès mémoire en dehors des clous se fait sauvagement planter. Par exemple, essayez de manipuler une donnée qui n'est pas "alignée" dans un mot de 16 octets avec une instruction SSE, vous aurez droit à un joli petit crash !

Pour éviter ce genre de choses, les compilateurs utilisés pour des langages de haut niveau préfèrent rajouter des données inutiles (on dit aussi du bourrage) de façon à ce que chaque donnée soit bien alignée sur le bon nombre d'octets. En reprenant notre exemple du dessus, et en notant le bourrage X, on obtiendrait ceci :

Adresse	Octet 4	Octet 3	Octet 2	Octet 1
0x 0000 0000	Caractère	X	X	X
0x 0000 0004	Entier	Entier	Entier	Entier
0x 0000 0008	Donnée	Donnée	X	X

Comme vous le voyez, ça prend un peu plus de place, et de la mémoire est gâchée inutilement. C'est pas grand chose, mais quand on sait que de la mémoire cache est gâchée ainsi, ça peut jouer un peu sur les performances. Il y a cependant des situations dans lesquelles rajouter du bourrage est une bonne chose et permet des gains en performances assez abominables (une sombre histoire de cache dans les architectures multiprocesseurs ou multi-cœurs, mais je n'en dit pas plus). Cet alignement se gère dans certains langages (comme le C, le C++ ou l'ADA), en gérant l'ordre de déclaration de vos variables. Essayez toujours de déclarer vos variables de façon à remplir un mot intégralement ou le plus possible. Renseignez-vous sur le bourrage, et essayez de savoir quelle est la taille de vos données en regardant la norme de vos langages.