Bonjour, Habr! Je vous présente la traduction de l'article "Les pointeurs sont compliqués, ou: qu'est-ce qu'un octet?" paternité de Ralf Jung.
Cet été, je travaille à nouveau à temps plein sur Rust, et je vais à nouveau (entre autres) travailler sur le «modèle de mémoire» pour Rust / MIR. Cependant, avant de parler de mes idées, je dois enfin dissiper le mythe selon lequel «les pointeurs sont simples: ce ne sont que des chiffres». Les deux parties de cette déclaration sont erronées, au moins dans les langages avec des fonctionnalités dangereuses, comme Rust ou C: les pointeurs ne peuvent pas être appelés nombres premiers ou (ordinaires).
Je voudrais également discuter de la partie du modèle de mémoire qui doit être abordée avant de parler des parties les plus complexes: sous quelle forme les données sont-elles stockées en mémoire? Une mémoire se compose d'octets, d'unités adressables minimales et des éléments les plus petits accessibles (au moins sur la plupart des plates-formes), mais quelles sont les valeurs d'octets possibles? Encore une fois, il s'avère que «c'est juste un nombre à 8 bits» ne convient pas comme réponse.
J'espère qu'après avoir lu ce post, vous serez d'accord avec moi concernant les deux déclarations.
Les pointeurs sont compliqués
Quel est le problème avec "les pointeurs sont des nombres réguliers"? Examinons l'exemple suivant: (J'utilise C ++ ici, car l'écriture de code non sécurisé en C ++ est plus facile que d'écrire en Rust, et le code non sécurisé est juste l'endroit où les problèmes apparaissent. Insecure Rust et C ont tous les mêmes problèmes que et C ++).
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; int i = ; auto x_ptr = &x[i]; *x_ptr = 23; return y[0]; }
Optimiser la dernière lecture de y [0] avec un retour de 42 est toujours très bénéfique. La justification de cette optimisation est que la modification de x_ptr qui pointe vers x ne peut pas changer y.
Cependant, lorsque nous traitons des langages de bas niveau tels que C ++, nous pouvons violer cette hypothèse en attribuant à i la valeur yx. Puisque & x [i] est identique à x + i, nous écrivons 23 dans & y [0].
Bien sûr, cela n'empêche pas les compilateurs C ++ d'effectuer de telles optimisations. Pour résoudre ce problème, la norme indique que notre code a UB .
Premièrement, il n'est pas autorisé d'effectuer des opérations arithmétiques sur des pointeurs (comme dans le cas de & x [i]), si dans ce cas le pointeur dépasse les limites du tableau . Notre programme viole cette règle: x [i] va au-delà de x, donc c'est UB. En d'autres termes, même le calcul de la valeur x_ptr est UB, donc nous n'arrivons même pas à l'endroit où nous voulons utiliser ce pointeur.
(Il s'avère que i = yx est également UB, car seuls les pointeurs pointant vers la même allocation de mémoire peuvent être soustraits . Cependant, nous pourrions écrire i = ((size_t) y - (size_t) x) / sizeof (int) pour contourner c'est une limitation.)
Mais nous n'avons pas encore fini: cette règle a la seule exception que nous pouvons utiliser à notre avantage. Si l'opération arithmétique calcule la valeur du pointeur vers l'adresse exactement après la fin du tableau, alors tout est en ordre. (Cette exception est nécessaire pour calculer vec.end () pour les boucles les plus courantes en C ++ 98.)
Modifions un peu l'exemple:
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; auto x_ptr = x+8;
Imaginez maintenant que x et y ont été alloués l' un après l'autre , y ayant une adresse plus grande. Alors x_ptr pointe vers le début de y! La condition est alors vraie et l'affectation se produit. Dans le même temps, il n'y a pas d'UB en raison de la sortie du pointeur à l'étranger.
Il semble que cela ne permette pas l'optimisation. Cependant, le standard C ++ a un autre atout dans sa manche pour aider les créateurs de compilateurs: en fait, il ne nous permet pas d'utiliser x_ptr. Selon ce que la norme dit sur l' ajout de nombres aux pointeurs , x_ptr pointe vers l'adresse après le dernier élément du tableau. Il ne pointe pas vers un élément spécifique d'un autre objet, même s'ils ont la même adresse . (Au moins, c'est une interprétation courante de la norme sur la base de laquelle LLVM optimise ce code .)
Et même si x_ptr et & y [0] pointent vers la même adresse , cela ne fait pas d'eux le même pointeur , c'est-à-dire qu'ils ne peuvent pas être utilisés de manière interchangeable: & y [0] pointe vers le premier élément de y; x_ptr pointe vers l'adresse après x. Si nous remplaçons * x_ptr = 23 par la chaîne * & y [0] = 0, nous changerons la valeur du programme, même si l'égalité des deux pointeurs a été vérifiée.
Cela mérite d'être répété:
Ce n'est pas parce que deux pointeurs pointent vers la même adresse qu'ils sont égaux et peuvent être utilisés de manière interchangeable.
Oui, cette différence est insaisissable. En fait, cela provoque toujours des différences dans les programmes compilés avec LLVM et GCC.
Notez également que cette règle one-after n'est pas le seul endroit en C / C ++ où l'on peut observer un tel effet. Un autre exemple est le mot-clé restrict en C, qui peut être utilisé pour exprimer que les pointeurs ne se chevauchent pas (ne sont pas égaux):
int foo(int *restrict x, int *restrict y) { *x = 42; if (x == y) { *y = 23; } return *x; } int test() { int x; return foo(&x, &x); }
L'appel test () appelle UB, car deux accès à la mémoire dans foo ne doivent pas se produire à la même adresse. En remplaçant * y par * x dans foo, nous changerons la valeur du programme, et il n'appellera plus UB. Encore une fois: bien que x et y aient la même adresse, ils ne peuvent pas être utilisés de manière interchangeable.
Les pointeurs ne sont certainement pas que des chiffres.
Modèle de pointeur simple
Alors qu'est-ce qu'un pointeur? Je ne connais pas la réponse complète. En fait, c'est un domaine ouvert pour la recherche.
Un point important: nous examinons ici un modèle de pointeur abstrait . Bien sûr, sur un vrai ordinateur, les pointeurs sont des nombres. Mais un véritable ordinateur n'effectue pas les optimisations que font les compilateurs C ++ modernes. Si nous écrivions les programmes ci-dessus dans l'assembleur, il n'y aurait pas d'UB, pas d'optimisations. C ++ et Rust adoptent une approche plus «supérieure» de la mémoire et des pointeurs, limitant le programmeur au compilateur. Lorsqu'il est nécessaire de décrire formellement ce qu'un programmeur peut et ne peut pas faire dans ces langages, le modèle des pointeurs sous forme de nombres est brisé, nous devons donc trouver autre chose. Ceci est un autre exemple d'utilisation d'une «machine virtuelle» différente d'un véritable ordinateur à des fins de spécification - une idée dont j'ai parlé plus tôt .
Voici une phrase simple (en fait, ce modèle de pointeurs est utilisé par CompCert et mon travail par RustBelt , ainsi que la façon dont l' interpréteur miri implémente les pointeurs ): un pointeur est une paire d'ID qui identifie de manière unique une zone mémoire (allocation), et le décalage est relatif à ce domaine. Si vous écrivez ceci en rouille:
struct Pointer { alloc_id: usize, offset: isize, }
Les opérations d'ajout (soustraction) d'un nombre à un pointeur (à partir d'un pointeur) n'affectent que le décalage, et par conséquent le pointeur ne peut jamais quitter la zone mémoire. La soustraction de pointeurs n'est possible que s'ils appartiennent à la même zone mémoire (conformément à C ++ ).
(Comme nous pouvons le voir, la norme C ++ applique ces règles aux tableaux, pas aux zones de mémoire. Cependant, LLVM les applique au niveau de la zone .)
Il s'avère (et miri montre la même chose) que ce modèle peut bien nous servir. Nous nous souvenons toujours de la région de mémoire à laquelle appartient le pointeur, afin de pouvoir distinguer le pointeur suivant d'une région de mémoire du pointeur au début d'une autre région. Ainsi miri peut trouver que notre deuxième exemple (avec & x [8]) a UB.
Notre modèle s'effondre
Dans notre modèle, les pointeurs, bien qu'ils ne soient pas des nombres, sont au moins simples. Cependant, ce modèle commencera à s'effondrer sous nos yeux, dès que vous vous souviendrez de la conversion des pointeurs en nombres. Dans miri, la conversion d'un pointeur en un nombre ne fait rien, nous obtenons simplement une variable numérique (c'est-à-dire que son type indique qu'il s'agit d'un nombre) dont la valeur est un pointeur (c'est-à-dire une paire de zone de mémoire et un décalage). Cependant, multiplier ce nombre par 2 conduit à une erreur, car on ne sait pas vraiment ce que signifie "multiplier un tel pointeur abstrait par 2".
Je dois préciser: ce n'est pas une bonne solution quand il s'agit de définir la sémantique d'un langage. Cependant, cela fonctionne bien pour l'interprète. C'est l'approche la plus simple, et nous l'avons choisie car il n'est pas clair comment cela peut être fait autrement (sauf pour ne pas prendre en charge de telles réductions du tout - mais avec leur support, miri peut exécuter plus de programmes): dans notre machine abstraite, il n'y a pas un seul "espace d'adressage", dans lequel toutes les zones de mémoire allouées seraient situées, et tous les pointeurs étaient mappés à des numéros différents spécifiques. Chaque zone de mémoire est identifiée par un ID (masqué). Maintenant, nous pouvons commencer à ajouter des données supplémentaires à notre modèle, telles que l'adresse de base pour chaque zone de mémoire, et l'utiliser d'une manière ou d'une autre pour ramener le numéro au pointeur ... et à ce stade, le processus devient vraiment très compliqué, et, en tout cas, une discussion de cela Les modèles ne visent pas à rédiger un article. Son objectif est de discuter de la nécessité d'un tel modèle. Si vous êtes intéressé, je vous recommande de lire ce document , qui examine de plus près l'idée ci-dessus d'ajouter une adresse de base.
En bref, les conversions de pointeurs et de nombres entre eux sont déroutants et difficiles à déterminer formellement, compte tenu des optimisations discutées ci-dessus. Il existe un conflit entre l'approche de haut niveau requise pour les optimisations et l'approche de bas niveau nécessaire pour décrire la conversion de pointeurs en nombres et vice versa. Pour la plupart, nous ignorons simplement ce problème dans miri et, dans la mesure du possible, essayons d'en faire autant que possible en utilisant le modèle simple avec lequel nous travaillons. Une définition complète de langages tels que C ++ ou Rust, bien sûr, ne peut pas aller d'une manière aussi simple, elle devrait expliquer ce qui se passe réellement. Pour autant que je sache, il n'y a pas de solution appropriée, mais la recherche universitaire approche de la vérité .
C'est pourquoi les pointeurs ne sont pas non plus simples.
Des pointeurs aux octets
J'espère avoir avancé un argument convaincant selon lequel les nombres ne sont pas le seul type de données à prendre en compte si nous voulons décrire formellement des langages de bas niveau comme C ++ ou la partie (non sécurisée) de Rust. Cependant, cela signifie qu'une opération simple comme la lecture d'un octet dans la mémoire ne peut pas simplement renvoyer u8. Imaginez que nous implémentions memcpy en lisant chaque octet de la source tour à tour dans une variable locale v, puis stockons cette valeur dans l'emplacement cible. Mais que faire si cet octet fait partie d'un pointeur? Si le pointeur est une paire d'ID de zone de mémoire et de décalage, alors quel sera son premier octet? Nous devons dire à quoi la valeur de v est égale, nous devrons donc en quelque sorte répondre à cette question. (Et c'est un problème complètement différent de celui de la multiplication, qui était dans la section précédente. Nous supposons simplement qu'il existe un type abstrait de Ponter.)
Nous ne pouvons pas représenter l'octet du pointeur comme une valeur de la plage 0..256 (remarque: ci-après 0 est activé, 256 ne l'est pas). En général, si nous utilisons un modèle de représentation de mémoire naïf, la partie «cachée» supplémentaire du pointeur (celle qui en fait plus qu'un simple nombre) sera perdue lorsque le pointeur est écrit en mémoire et relu. Nous devrons résoudre ce problème, et pour cela, nous devrons étendre notre concept d '«octet» pour représenter cet état supplémentaire. Ainsi, l'octet est maintenant soit la valeur de la plage 0..256 ("bits bruts"), soit le nième octet d'un pointeur abstrait. Si nous devions implémenter notre modèle de mémoire dans Rust, cela pourrait ressembler à ceci:
enum ByteV1 { Bits(u8), PtrFragment(Pointer, u8), }
Par exemple, PtrFragment (ptr, 0) représente le premier octet du pointeur ptr. Ainsi, memcpy peut "casser" le pointeur en octets séparés qui représentent ce pointeur en mémoire et les copier individuellement. Sur une architecture 32 bits, la représentation ptr complète contiendra 4 octets:
[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
Cette représentation prend en charge toutes les opérations de déplacement de données sur des pointeurs au niveau des octets, ce qui est tout à fait suffisant pour la mémorisation. Les opérations arithmétiques ou binaires ne sont pas entièrement prises en charge; comme indiqué ci-dessus, cela nécessiterait une représentation plus complexe des pointeurs.
Mémoire non initialisée
Cependant, nous n'avons pas fini avec notre définition de "octet". Pour décrire complètement le comportement du programme, nous devons considérer une autre option: un octet en mémoire peut être non initialisé . La dernière définition d'octet ressemblera à ceci (supposons que nous ayons un type de pointeur pour les pointeurs):
enum Byte { Bits(u8), PtrFragment(Pointer, u8), Uninit, }
Nous utilisons la valeur Uninit pour tous les octets de la mémoire allouée dans lesquels nous n'avons encore écrit aucune valeur. Il est possible de lire la mémoire non initialisée sans problème, mais toute autre action avec ces octets (par exemple, l'arithmétique numérique) conduit à UB.
Ceci est très similaire aux règles LLVM en ce qui concerne la valeur de poison spécial. Notez que LLVM a également une valeur undef, qui est utilisée pour la mémoire non initialisée et fonctionne un peu différemment. Cependant, la compilation de notre Uninit en undef est correcte (undef est à certains égards "plus faible"), et il existe des suggestions pour supprimer undef de LLVM et utiliser du poison à la place .
Vous vous demandez peut-être pourquoi nous avons une valeur spéciale Uninit. Pourquoi ne pas choisir un b: u8 arbitraire pour chaque nouvel octet, puis utiliser Bits (b) comme valeur initiale? C'est vraiment une option. Cependant, tout d'abord, tous les compilateurs sont arrivés à l'approche en utilisant une valeur spéciale pour la mémoire non initialisée. Ne pas suivre cette approche signifie non seulement causer des problèmes de compilation via LLVM, mais également passer en revue toutes les optimisations et s'assurer qu'elles fonctionnent correctement avec ce modèle modifié. Le point clé ici: vous pouvez toujours remplacer Uninit en toute sécurité par toute autre valeur: toute opération recevant cette valeur entraînera en tout cas UB.
Par exemple, ce code C est plus facile à optimiser avec Uninit:
int test() { int x; if (condA()) x = 1;
Avec Uninit, nous pouvons facilement dire que x a une valeur Uninit ou une valeur de 1, et puisque le remplacement de Uninit par 1 fonctionne, l'optimisation est facilement expliquée. Sans Uninit, x est «une sorte de motif binaire arbitraire» ou 1, et la même optimisation est plus difficile à expliquer.
(Nous pouvons affirmer que nous pouvons échanger des opérations lorsque nous faisons un choix non déterministe, mais nous devrons alors prouver que le code qui est difficile à analyser n'utilise en aucun cas x. Uninit évite ce problème avec des preuves inutiles.)
Enfin, Uninit est le meilleur choix pour les interprètes comme miri. Ces interprètes ont des problèmes avec des opérations telles que «sélectionner simplement l'une de ces valeurs» (c'est-à-dire des opérations non déterministes), car elles ont tendance à parcourir tous les chemins possibles d'exécution du programme, ce qui signifie qu'elles doivent essayer toutes les valeurs possibles. L'utilisation de Uninit au lieu d'un modèle de bits arbitraire signifie que miri peut vous dire après l'exécution d'un programme si votre programme utilise de manière incorrecte des valeurs non initialisées.
Conclusion
Nous avons vu que dans des langages comme C ++ et Rust (contrairement aux vrais ordinateurs) les pointeurs peuvent être différents même s'ils pointent vers la même adresse, et qu'un octet est plus qu'un simple nombre compris entre 0 et 256. Par conséquent, si en 1978 le langage C pouvait être "assembleur portable", c'est maintenant une affirmation incroyablement erronée.