Aliasing (informatique)
Pour les articles homonymes, voir Aliasing.
En informatique, l'aliasing décrit une situation où un emplacement mémoire est accessible depuis différents noms symboliques dans le programme. Ainsi, on peut modifier des données à partir de plusieurs noms, appelées alias. En conséquence, l’alias rend particulièrement difficile la compréhension, l’analyse et l’optimisation des programmes. Les analyseurs d'alias ont pour objectif de créer et de calculer des informations utiles pour comprendre l'alias dans les programmes.
Exemples
[modifier | modifier le code]Débordement de tampon
[modifier | modifier le code]La plupart des implémentations du langage de programmation C n'effectuent pas de vérification des bornes des tableaux. On peut alors exploiter l'implémentation du langage de programmation par le compilateur et les conventions du langage assembleur de l'architecture informatique, pour obtenir des effets d'alias en écrivant en dehors du tableau (une sorte de dépassement de tampon). Cela invoque un comportement non défini selon la spécification du langage C ; cependant, de nombreuses implémentations de C montreront les effets d'alias décrits ici.
Par exemple, considérons que la pile contienne un tableau arr d'entiers int de taille 2, suivi directement d'une variable i de type entier int. Alors on peut modifier la variable i également en modifiant arr[2]. On dit que arr[2] et i sont des alias.
#include <stdio.h>
int main()
{
int arr[2] = { 1, 2 };
int i=10;
/* Write beyond the end of arr. Undefined behaviour in standard C, will write to i in some implementations. */
arr[2] = 20;
printf("element 0: %d \t", arr[0]); // outputs 1
printf("element 1: %d \t", arr[1]); // outputs 2
printf("element 2: %d \t", arr[2]); // outputs 20, if aliasing occurred
printf("i: %d \t\t", i); // might also output 20, not 10, because of aliasing, but the compiler might have i stored in a register and print 10
/* arr size is still 2. */
printf("arr size: %lu \n", (long) (sizeof(arr) / sizeof(int)));
}
Ceci est possible dans certaines implémentations de C car un tableau est un bloc de mémoire contigu et les éléments du tableau sont simplement référencés par des décalages par rapport à l'adresse du début de ce bloc multipliés par la taille d'un seul élément. Puisque C n’a pas de vérification des bornes, l’indexation et l’adressage en dehors du tableau sont possibles. Notez que le comportement d'alias mentionné ci-dessus est un comportement indéfini. Certaines implémentations peuvent laisser de l'espace entre les tableaux et les variables sur la pile, par exemple pour aligner les variables sur des emplacements mémoire qui sont un multiple de la taille des mots natifs de l'architecture. Le standard C ne précise généralement pas comment les données doivent être disposées en mémoire (ISO/CEI 9899:1999, section 6.2.6.1).
Il est considéré comme correct pour un compilateur d'omettre les effets d'alias pour les accès qui se situent en dehors des limites d'un tableau.
Pointeurs alias
[modifier | modifier le code]Une autre variété d'alias peut se produire dans n'importe quel langage pouvant faire référence à un emplacement en mémoire avec plusieurs noms (par exemple, avec des pointeurs). Il s'agit d'un problème courant avec les fonctions qui acceptent des arguments de pointeur, et leur tolérance (ou son absence) pour l'alias doit être soigneusement documentée, en particulier pour les fonctions qui effectuent des manipulations complexes sur les zones mémoire qui leur sont transmises.
Aliasing spécifié
[modifier | modifier le code]
L'alias est parfois souhaitable. C'est une pratique courante en Fortran. Le langage de programmation Perl spécifie, dans certaines constructions, un comportement d'alias, comme dans les boucles foreach . Cela permet de modifier directement certaines structures de données avec moins de code. Par exemple, le programme
my @array = (1, 2, 3);
foreach my $element (@array) {
# Increment $element, thus automatically
# modifying @array, since $element is ''aliased''
# to each of @array's elements in turn.
$element++;
}
print "@array \n";
affiche "2 3 4". Si l'on voulait contourner les effets d'alias, on pourrait copier le contenu de la variable d'index dans une autre et modifier la copie.
Conflits avec l'optimisation
[modifier | modifier le code]Avant d'optimiser le code, on doit souvent faire des hypothèses prudentes sur les variables lorsque l'alias est possible. Par exemple, connaître la valeur d'une variable (comme x vaut 5) permet normalement certaines optimisations (comme la propagation constante). Cependant, le compilateur ne peut pas utiliser ces informations après une affectation à une autre variable (par exemple, en C, *y = 10 ) car il se pourrait que *y soit un alias de x. Cela pourrait être le cas après une affectation comme y = &x. En raison de cette affectation à *y, la valeur de x serait également modifiée, donc propager l'information selon laquelle x vaut 5 aux instructions suivant *y = 10 serait potentiellement erroné (si *y est effectivement un alias de x ). Cependant, s'il existe des informations sur les pointeurs, le processus de propagation constante pourrait effectuer une requête du type : x peut-il être un alias de *y ? Alors, si la réponse est non, x = 5 peut se propager en toute sécurité.
Quand il n'y a pas d'alias, on peut réorganiser le code. Si le compilateur sait que x n'est pas alias par *y, alors le code qui utilise ou modifie la valeur de x peut être déplacé avant l'affectation *y = 10, si cela améliore l'ordonnancement ou permet d'effectuer davantage d'optimisations de boucles.
Pour permettre de telles optimisations de manière prévisible, la norme ISO pour le langage de programmation C (y compris sa nouvelle édition C99, voir section 6.5, paragraphe 7) stipule qu'il est illégal (à quelques exceptions près) d'accéder au même emplacement mémoire en utilisant des pointeurs de différents types. Un compilateur peut donc supposer que ces pointeurs ne créent pas d'alias. Cette règle, connue sous le nom de règle d'alias strict, permet parfois des augmentations impressionnantes des performances[1], mais est connue pour casser du code autrement valide. Plusieurs projets logiciels violent intentionnellement cette partie de la norme C99. Par exemple, Python 2.x l'a fait pour implémenter le comptage de références[2], et a nécessité des modifications des structures d'objet de base dans Python 3 pour permettre cette optimisation. Le noyau Linux fait cela parce que l'alias strict entraîne des problèmes d'optimisation du code intégré[3]. Dans de tels cas, lors de la compilation avec gcc, l'option -fno-strict-aliasing est invoquée pour empêcher les optimisations indésirables qui pourraient produire du code inattendu.
Aliasing au niveau matériel
[modifier | modifier le code]Le terme aliasing est aussi utilisé pour décrire la situation dans laquelle, en raison d'un choix de conception matérielle ou d'une panne matérielle, un ou plusieurs bits d'adresse disponibles ne sont pas utilisés dans le processus de sélection de mémoire[4]. Cela peut être une décision de conception s'il y a plus de bits d'adresse disponibles que nécessaire pour prendre en charge le(s) périphérique(s) de mémoire installé. En cas de panne, un ou plusieurs bits d'adresse peuvent être court-circuités ensemble, ou peuvent être forcés à la masse (logique 0) ou à la tension d'alimentation (logique 1).
Par exemple, considérons une mémoire avec 8 emplacements, ne nécessitant que 3 lignes d'adresse (ou bits, puisque 2 3 = 8). Les bits d'adresse (nommés A2 à A0) sont décodés pour sélectionner des emplacements de mémoire uniques comme suit, à la manière d'un compteur binaire standard :
| A2 | A1 | A0 | Emplacement mémoire |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
| 1 | 0 | 0 | 4 |
| 1 | 0 | 1 | 5 |
| 1 | 1 | 0 | 6 |
| 1 | 1 | 1 | 7 |
Dans la table ci-dessus, chacune des 8 combinaisons uniques de bits d'adresse sélectionne un emplacement mémoire différent. Cependant, si un bit d'adresse (par exemple A2) devait être court-circuité à la masse, le tableau serait modifié comme suit :
| A2 | A1 | A0 | Emplacement mémoire |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
Dans ce cas, A2 est toujours nul. Ainsi les quatre premiers emplacements mémoire sont dupliqués et réapparaissent comme les quatre seconds. Les emplacements mémoire 4 à 7 sont devenus inaccessibles.
Si ce changement se produisait sur un bit d'adresse différent, les résultats du décodage seraient différents, mais en général l'effet serait le même : la perte d'un seul bit d'adresse réduit de moitié l'espace mémoire disponible, ce qui entraîne une duplication (autrement de l'aliasing) de l'espace restant.
Voir aussi
[modifier | modifier le code]- Anti crénelage
- Alias pour les utilisations du mot lorsqu'il est appliqué au traitement du signal, y compris l'infographie
Références
[modifier | modifier le code]- Mike Acton, « Understanding Strict Aliasing »,
- Neil Schemenauer, « ANSI strict aliasing and Python »,
- Linus Torvalds, « Re: Invalid compilation without -fno-strict-aliasing »,
- Michael Barr, « Software Based Memory Testing »,
Liens externes
[modifier | modifier le code]- Comprendre l'alias strict – article de Mike Acton
- Aliasing, conversions de pointeurs et gcc 3.3 – article d'information sur la liste de diffusion NetBSD
- Analyse d'alias basée sur le type en C++ – Article d'information sur l'analyse d'alias basée sur le type en C++
- Comprendre l'alias strict C/C++ – article sur l'alias strict provenant du wiki du développeur boost
