Les opérations bit à bit/Les débordements de puissance de deux

Comme vous le savez peut-être, certaines architectures demandent aux accès mémoire de respecter des contraintes d'alignement. Pour rappel, la mémoire est alors découpée en blocs dont la taille est égale à la largeur du bus de données. Quand on accède à une donnée, il est préférable que celle-ci soit intégralement contenue dans un bloc : l'accès mémoire est alors dit aligné. Mais si la donnée est à cheval sur deux blocs, l'accès mémoire est dit non-aligné et cela peut poser problème. Si certaines architectures gèrent parfaitement les accès non-alignés, d'autres ne permettent pas de tels accès. Pour diverses raisons, il est possible pour un programmeur de détecter si un accès mémoire sera ou non aligné.

Un problème similaire apparait lorsque l'on doit charger une donnée depuis la mémoire RAM, sur les systèmes à mémoire virtuelle. Cette fois-ci, la mémoire virtuelle divise la RAM en pages, les données pouvant être à cheval sur deux pages. Détecter de tels chevauchements est alors une nécessité pour le système d’exploitation. Il se trouve qu'aussi bien la taille des pages que la largeur des blocs de RAM alignés sont des puissances de deux.

Gérer les accès non-alignés demande donc de détecter quand une donnée est à cheval entre deux blocs. Détecter les accès non-alignés est primordial et, fort heureusement, se fait avec quelques calculs particulièrement simples. Pour cela, il existe plusieurs solutions différentes.

La méthode avec des divisions

L'adresse $A$ peut se calculer à partir d'autres paramètres, comme la taille des blocs. Déjà, il faut savoir que chaque bloc a une taille qui s'exprime en bytes. Avec un système d'alignement ou de page, chaque bloc est numéroté en partant de zéro, ce numéro étant l'équivalent de l'adresse pour les bytes. L'adresse d'un bloc est par convention l'adresse du premier byte du bloc, celui dont l'adresse est la plus basse. Elle se calcule donc en multipliant le numéro du bloc par sa taille. Une donnée à l'intérieur d'un bloc est généralement localisée à une certaine distance de l'adresse de base, elle est placée quelques bytes plus loin que la base du bloc. Dit autrement, l'adresse $A$ d'une donnée s'écrit comme suit :

$A=N\times T+P$, avec $T$ la taille d'un bloc, $N$ le numéro du bloc et $P$ la position de la donnée par rapport à l'adresse de base du bloc.

Pages et blocs ont une taille qui est presque toujours une puissance de deux, ce qui est une norme tacite. Ce qui fait que l'on a :

$A=N\times 2^{n}+P$

L'adresse de $A+L$ s'écrit de la même manière, sauf que le numéro du bloc et la position dans le bloc sont potentiellement différents.

Notons que l'on peut trouver N et P à partir de A assez simplement. Il suffit en effet de diviser A par $2^{n}$ : N sera alors le quotient et P sera le reste de la division. Et c'est très utile pour détecter un accès non-aligné. Il suffit de diviser $A$ et $A+L$ par $2^{n}$, et de comparer les numéro de bloc obtenus. Si les deux numéros de bloc sont identiques, cela signifie que la donnée est toute entière dans le même bloc. Par contre, si les deux sont différents, cela signifie que le début de la donnée à l'adresse $A$ est dans un bloc, mais que la fin de la donnée $A+L$ est dans un autre bloc : il y a donc débordement.

Notons que faire la division en question demande juste de faire un décalage vers la droite, du moins sous condition que la taille du bloc soit une puissance de deux. C'est d'ailleurs une des raisons pour lesquelles les blocs/pages ont une taille égale à une puissance de deux. Faire ainsi simplifie de nombreux calculs d'adresse et permet des simplifications assez utiles.

La méthode avec le modulo

Il existe une seconde méthode qui une logique très simple. La donnée à charger commence à une adresse que nous noterons $A$ et a une longueur $L$. Un débordement de page/bloc a lieu quand il existe un multiple de $2^{n}$ entre $A$ et $A+L$. Cela traduit le fait que la donnée commence dans un premier bloc, atteint la limite du bloc (donc, une adresse multiple de $2^{n}$) et se poursuit au-delà. Reste à voir comment les opérations bit à bit nous aident pour détecter une telle situation.

Rappelons que l'on a :

$A=N\times 2^{n}+P_{0}$

Un débordement a lieu si, en ajoutant $L$, on passe au multiple de $2^{n}$ suivant. En clair, un débordement a lieu si :

$A+L=(N+1)\times 2^{n}+P_{1}$, avec $P_{1}\geq 0$

Soustrayons la première équation de la seconde :

$(A+L)-A=\left[(N+1)\times 2^{n}+r_{2}\right]-\left[N\times 2^{n}+P_{0}\right]$

Réorganisons les termes :

$L=\left[(N+1)\times 2^{n}-N\times 2^{n}\right]+\left[P_{1}-P_{0}\right]$

Simplifions :

$L=2^{n}+P_{1}-P_{0}$

Ajoutons $r_{0}$ des deux cotés :

$L+P_{0}=2^{n}+P_{1}$, avec, rappelons-le, $r_{2}\geq 0$

Pour le reformuler, le débordement implique que $P_{1}\geq 0$, ce qui implique que l'équation précédente est équivalente à l'inégalité suivante :

$L+P_{0}>2^{n}$

L'équation précédente dit que si la longueur dépasse ce qu'il manque à l'adresse pour atteindre le prochain multiple de $2^{n}$, alors c'est un débordement.

Sachant que le reste vaut par définition $P_{0}=A\mod 2^{n}$, on a :

$(A\mod 2^{n})+L\geq 2^{n}$

La méthode avec débordement d'entier

Une seconde méthode effectue un calcul similaire, si ce n'est que la comparaison est remplacée par un débordement d'entier. Le principe est très simple et se contente de remplacer l'adresse par le multiple de $2^{n}$ le plus grand possible qui soit adressable. Prenons par exemple une mémoire de 2^32 adresses, adressée par des adresses de 32 bits, découpée en page de 4096 octets. On suppose aussi que la machine travaille sur les mots/registres de 32 bits, comme les adresses. Sur 32 bits, l'adresse la plus grande qui soit multiple de 4096 est de 4294963200. Si à cette adresse on ajoute $L+A\mod 2^{n}$, un débordement se produit si $L+A\%2^{n}>4096$. En clair, le débordement d'entier traduit un débordement de page. On détecte donc un débordement de page si :

$4294963200+L+(A\%4096)>2^{32}$

Il se trouve que le calcul de $4294963200+(A\%4096)$ peut se réaliser sans faire l'addition. En effet, 4294963200 a déjà ses 12 bits de poids faible à 0. Tout ce qu'il faut faire est de remplacer les bits de poids forts de l'adresse par des 1, sans toucher aux bits sélectionnés par le modulo. L'application d'un masque est alors obligatoire, ce qui donne le code suivant :

$(A|4294963200)+L>2^{32}$

Ou encore :

$(A|-4096)+L>2^{32}$

On peut bien sûr généraliser les résultats précédents à toute autre valeur. Pour des adresses de $n$ bits et des pages/blocs de $m$ octets, on a :

$(A|-m)+L>2^{n}$