Est-il possible de lire au-delà de la fin d'un tampon dans la même page sur x86 et x64 ?

Question

De nombreuses méthodes utilisées dans les algorithmes à haute performance pourraient être (et sont) simplifiées si elles étaient autorisées à lire une petite quantité au-delà de la fin des tampons d'entrée. Ici, "petite quantité" signifie généralement jusqu'à W - 1 octets après la fin, où W est la taille du mot en octets de l'algorithme (par exemple, jusqu'à 7 octets pour un algorithme traitant l'entrée en morceaux de 64 bits).

Il est clair que écrire après la fin d'un tampon d'entrée n'est jamais sûr, en général, puisque vous pouvez bloquer les données au-delà du tampon. 1 . Il est également clair que la lecture au-delà de la fin d'un tampon vers une autre page peut déclencher une erreur de segmentation/une violation d'accès, puisque la page suivante peut ne pas être lisible.

Dans le cas particulier de la lecture de valeurs alignées, cependant, un défaut de page semble impossible, du moins sur x86. Sur cette plate-forme, les pages (et donc les drapeaux de protection de la mémoire) ont une granularité de 4K (des pages plus grandes, par exemple 2MiB ou 1GiB, sont possibles, mais ce sont des multiples de 4K) et donc les lectures alignées n'accèdent qu'aux octets de la même page que la partie valide du tampon.

Voici un exemple canonique d'une boucle qui aligne son entrée et lit jusqu'à 7 octets après la fin du tampon :

int processBytes(uint8_t *input, size_t size) {

    uint64_t *input64 = (uint64_t *)input, end64 = (uint64_t *)(input + size);
    int res;

    if (size < 8) {
        // special case for short inputs that we aren't concerned with here
        return shortMethod();
    }

    // check the first 8 bytes
    if ((res = match(*input)) >= 0) {
        return input + res;
    }

    // align pointer to the next 8-byte boundary
    input64 = (ptrdiff_t)(input64 + 1) & ~0x7;

    for (; input64 < end64; input64++) {
        if ((res = match(*input64)) > 0) {
            return input + res < input + size ? input + res : -1;
        }
    }

    return -1;
}

La fonction interne int match(uint64_t bytes) n'est pas montré, mais c'est quelque chose qui cherche un octet correspondant à un certain modèle, et retourne la position la plus basse (0-7) si elle est trouvée ou -1 sinon.

Tout d'abord, les cas de taille < 8 sont confiés à une autre fonction pour simplifier l'exposition. Ensuite, une seule vérification est effectuée pour les 8 premiers (octets non alignés). Puis une boucle est faite pour les autres floor((size - 7) / 8) des morceaux de 8 octets 2 . Cette boucle peut lire jusqu'à 7 octets au-delà de la fin du tampon (le cas de 7 octets se produit quand input & 0xF == 1 ). Cependant, l'appel de retour comporte une vérification qui exclut toute correspondances erronées qui se produisent au-delà de la fin du tampon.

En pratique, une telle fonction est-elle sûre sur x86 et x86-64 ?

Ces types de dépasse les limites de sont courantes dans les codes de haute performance. Un code de queue spécial pour éviter de tels dépasse les limites de est également courant. Parfois, on voit ce dernier type remplacer le premier pour faire taire des outils comme valgrind. Parfois, vous voyez un proposition pour effectuer un tel remplacement, qui est rejeté au motif que l'idiome est sûr et que l'outil est en erreur (ou simplement trop conservateur). 3 .

Une note à l'intention des juristes linguistes :

La lecture d'un pointeur au-delà de sa taille allouée n'est absolument pas autorisée dans la norme. J'apprécie les réponses des avocats du langage, et je les écris même occasionnellement les écrire moi-même, et je serai même heureux quand quelqu'un déterrera le chapitre et les versets qui montrent que le code ci-dessus est comportement indéfini et donc pas sûr au sens strict (et je copierai les détails ici). Mais en fin de compte, ce n'est pas ce que ce que je recherche. En pratique, beaucoup d'idiomes communs impliquant la conversion de pointeurs, l'accès à la structure par ces pointeurs, etc. conversion de pointeur, l'accès aux structures à travers de tels pointeurs et donc sont techniquement non définis, mais sont très répandus dans le code de haute qualité et de haute performance. Souvent, il n'y a pas d'alternative, ou l'alternative fonctionne à la moitié de la vitesse ou moins.

Si vous le souhaitez, vous pouvez envisager une version modifiée de cette question, à savoir :

Après que le code ci-dessus a été compilé en assembleur x86/x86-64, et que l'utilisateur a vérifié qu'il est compilé de la manière attendue (c'est-à-dire que le compilateur n'a pas utilisé d'accès partiellement hors limites prouvable), il est possible de vérifier que le code a bien été compilé, le compilateur n'a pas utilisé un accès partiellement hors limites prouvable pour faire quelque chose vraiment intelligent , l'exécution du programme compilé est-elle sûre ?

À cet égard, cette question est à la fois une question sur le langage C et une question sur l'assemblage x86. La plupart du code utilisant cette astuce que j'ai vu est écrit en C, et le C est toujours le langage dominant pour les bibliothèques de haute performance, éclipsant facilement les choses de plus bas niveau comme asm, et les choses de plus haut niveau comme <tout le reste>. Du moins en dehors de la niche numérique hardcore où FORTRAN joue encore le jeu. Je suis donc intéressé par le Compilateur C et inférieur C'est pourquoi je ne l'ai pas formulée comme une question portant uniquement sur l'assemblage x86.

Tout ceci étant dit, alors que je ne suis que modérément intéressé par un lien vers le norme montrant qu'il s'agit d'UD, je suis très intéressé par tous les détails des des implémentations réelles qui peuvent utiliser cette UD particulière pour produire code inattendu. Maintenant, je ne pensez à cela peut arriver sans une profonde assez profonde analyse inter-procédures, mais le débordement de gcc a surpris beaucoup de gens aussi...

---

1 Même dans des cas apparemment inoffensifs, par exemple lorsque la même valeur est réécrite, on peut briser le code concurrent .

2 Notez que pour que ce chevauchement fonctionne, il faut que cette fonction et la match() pour qu'elle se comporte d'une manière idempotente spécifique - en particulier que la valeur de retour supporte des vérifications superposées. Ainsi, un "trouver le premier octet correspondant au motif" fonctionne puisque tous les octets de la fonction match() sont toujours d'actualité. Une méthode consistant à "compter les octets correspondant au motif" ne fonctionnerait cependant pas, car certains octets pourraient être comptés deux fois. Par ailleurs, certaines fonctions telles que l'appel "retourner l'octet minimum" fonctionneraient même sans la restriction de l'ordre, mais elles doivent examiner tous les octets.

3 Il est intéressant de noter ici que pour le Memcheck de valgrind il y a un drapeau , --partial-loads-ok qui contrôle si de telles lectures sont en fait rapportées comme une erreur. La valeur par défaut est oui signifie qu'en général, ces chargements ne sont pas traités comme des erreurs immédiates, mais qu'un effort est fait pour suivre l'utilisation ultérieure des octets chargés, dont certains sont valides et d'autres non, une erreur étant signalée si les octets hors limites sont utilisé . Dans des cas comme celui de l'exemple ci-dessus, où l'on accède à l'intégralité du mot en match() Une telle analyse conclura que les octets ont été consultés, même si les résultats sont finalement rejetés. Valgrind ne peut pas en général déterminer si les octets invalides d'un chargement partiel sont effectivement utilisés (et la détection en général est probablement très dur).

Answer 1

Oui, c'est sûr dans l'asm x86, et libc existant strlen(3) en tirent parti dans l'asm écrit à la main. Et même C de repli de la glibc mais il compile sans LTO et ne peut donc jamais être en ligne. Il s'agit essentiellement d'utiliser le C comme un assembleur portable pour créer du code machine pour une fonction, et non pas comme une partie d'un plus grand programme C avec inlining. Mais c'est surtout parce qu'il a aussi un potentiel de strict-aliasing UB, voir ma réponse sur le lien Q&A. Vous voulez probablement aussi un programme GNU C __attribute__((may_alias)) typedef au lieu d'un simple unsigned long comme type plus large, comme __m128i etc. déjà utilisés.

C'est sûr parce que une charge alignée ne franchira jamais une limite d'alignement supérieure et la protection de la mémoire se fait avec des pages alignées, donc au moins 4k limites. 1 Toute charge naturellement alignée qui touche au moins un octet valide ne peut pas faire de faute. Il est également possible de vérifier si vous êtes suffisamment loin de la prochaine limite de page pour effectuer un chargement de 16 octets, par exemple if (p & 4095 > (4096 - 16)) do_special_case_fallback . Voir la section ci-dessous à ce sujet pour plus de détails.

---

Il est aussi généralement sûr en C compilé pour x86, pour autant que je sache. Lire à l'extérieur d'un objet est bien sûr un comportement indéfini en C, mais fonctionne en C ciblant x86. Je ne pense pas que les compilateurs aient explicitement / volontairement définir le comportement, mais dans la pratique, c'est ainsi que cela fonctionne.

Je pense que ce n'est pas le genre d'UB que les compilateurs agressifs vont assumer ne peut pas se faire en optimisant mais une confirmation de la part d'un compilateur-écrivain sur ce point serait bien, surtout pour les cas où il est facilement prouvable au moment de la compilation qu'un accès va au-delà de la fin d'un objet. (Voir la discussion dans les commentaires avec @RossRidge : une version précédente de cette réponse affirmait que c'était absolument sûr, mais l'article du blog LLVM ne se lit pas vraiment de cette façon).

C'est requis en asm pour aller plus vite qu'un octet à la fois en traitant une chaîne de longueur implicite. En C, en théorie, un compilateur pourrait savoir comment optimiser une telle boucle, mais en pratique, il ne le fait pas et il faut donc faire des bidouillages comme celui-ci. Jusqu'à ce que cela change, je soupçonne que les compilateurs dont les gens se soucient éviteront généralement de casser le code qui contient ce potentiel UB.

Il n'y a pas de danger lorsque l'overread n'est pas visible pour le code qui connaît la longueur d'un objet. Un compilateur doit faire un asm qui fonctionne pour le cas où il y a des éléments de tableau aussi loin que nous lisons réellement. Le danger plausible que je peux voir avec les futurs compilateurs possibles est : après l'inlining, un compilateur pourrait voir l'UB et décider que ce chemin d'exécution ne doit jamais être emprunté. Ou que la condition de terminaison doit être trouvée avant le vecteur non complet final et laisser cela de côté lors du déroulement complet.

---

Les données que vous obtenez sont des déchets imprévisibles, mais il n'y aura pas d'autres effets secondaires potentiels. Tant que votre programme n'est pas affecté par les octets inutiles, tout va bien. (par exemple, utilisez bithacks pour trouver si l'un des octets d'un uint64_t sont nuls puis une boucle d'octets pour trouver le premier octet nul, sans tenir compte des déchets qui se trouvent au-delà).

---

Les situations inhabituelles où cette ne serait pas être sûr en asm x86

• Points d'arrêt des données matérielles (watchpoints) qui se déclenchent sur un chargement d'une adresse donnée. Si vous surveillez une variable juste après un tableau, vous risquez d'obtenir une réponse erronée. Il s'agit d'une gêne mineure pour quelqu'un qui débogue un programme normal. Si votre fonction fait partie d'un programme qui utilise les registres de débogage D0-D3 du x86 et les exceptions qui en résultent pour quelque chose qui pourrait affecter la correction, alors faites attention.

  De même, un vérificateur de code comme valgrind pourrait se plaindre de la lecture en dehors d'un objet.

• Dans le cadre d'un hypothétique système d'exploitation 16 ou 32 bits qui pourrait utiliser la segmentation : A limite de segment peut utiliser Granularité 4k ou 1-byte Il est donc possible de créer un segment dont le premier offset de défaut est impair (le fait que la base du segment soit alignée sur une ligne ou une page de cache n'a aucune importance, sauf pour les performances). Tous les systèmes d'exploitation x86 courants utilisent des modèles de mémoire plats. et x86-64 supprime la prise en charge des limites de segment pour le mode 64 bits.

• Registres d'E/S mappés en mémoire juste après le tampon que vous vouliez boucler avec des charges larges, surtout la même ligne de cache de 64B. C'est extrêmement improbable, même si vous appelez des fonctions comme celle-ci depuis un pilote de périphérique (ou un programme en espace utilisateur comme un serveur X qui a mappé un espace MMIO).

Si vous traitez un tampon de 60 octets et que vous devez éviter de lire un registre MMIO de 4 octets, vous le saurez et vous utiliserez une commande volatile T* . Ce genre de situation ne se produit pas pour un code normal.

---

strlen est l'exemple canonique d'une boucle qui traite un tampon de longueur implicite et ne peut donc pas vectoriser sans lire au-delà de la fin d'un tampon. Si vous avez besoin d'éviter de lire au-delà de la terminaison 0 vous ne pouvez lire qu'un seul octet à la fois.

Par exemple, l'implémentation de la glibc utilise un prologue pour gérer les données jusqu'à la première limite d'alignement de 64B. Puis, dans la boucle principale (lien gitweb vers le source asm) il charge une ligne entière de cache de 64B en utilisant quatre chargements alignés SSE2. Il les fusionne en un seul vecteur avec pminub (min des octets non signés), de sorte que le vecteur final aura un élément zéro seulement si l'un des quatre vecteurs avait un zéro. Après avoir constaté que la fin de la chaîne se trouvait quelque part dans cette ligne de cache, il revérifie chacun des quatre vecteurs séparément pour voir où. (En utilisant la méthode typique pcmpeqb contre un vecteur de tous les zéros, et pmovmskb / bsf pour trouver la position dans le vecteur.) La glibc disposait auparavant de deux versions différentes de Choix de stratégies de strates mais la version actuelle est valable pour tous les processeurs x86-64.

Habituellement, les boucles de ce type évitent de toucher toutes les lignes de cache supplémentaires qu'elles n'ont pas besoin de toucher, pas seulement les pages, pour des raisons de performance, comme strlen de la glibc.

Le chargement de 64B à la fois n'est bien sûr possible qu'à partir d'un pointeur aligné sur 64B, puisque les accès alignés naturellement ne peuvent pas croiser des pointeurs alignés sur 64B. limites de la ligne de cache ou de la ligne de page .

---

Si vous connaissez à l'avance la longueur d'un tampon, vous pouvez éviter de lire au-delà de la fin en traitant les octets au-delà du dernier entièrement alignés en utilisant un chargement non aligné qui se termine au dernier octet du tampon.

(Encore une fois, cela ne fonctionne qu'avec des algorithmes idempotents, comme memcpy, qui ne se soucient pas d'effectuer des stockages superposés dans la destination. Les algorithmes modifiés sur place ne peuvent souvent pas le faire, sauf avec quelque chose comme conversion d'une chaîne de caractères en majuscules avec SSE2 où il est acceptable de retraiter des données qui ont déjà été mises en valeur. A part le blocage du transfert de magasin si vous faites un chargement non aligné qui chevauche votre dernier magasin aligné).

Ainsi, si vous vectorisez sur un tampon de longueur connue, il est souvent préférable d'éviter la surlecture de toute façon.

La surlecture sans faute d'un objet est le genre d'UB qui ne peut certainement pas faire de mal si le compilateur ne peut pas le voir au moment de la compilation. L'asm résultant fonctionnera comme si les octets supplémentaires faisaient partie d'un objet.

Mais même si elle est visible au moment de la compilation, elle n'est généralement pas nuisible avec les compilateurs actuels.

---

PS : une version précédente de cette réponse affirmait que les déréférencements non alignés de int * était également sûr en C compilé pour x86. C'est-à-dire pas vrai . J'ai été un peu trop cavalier il y a 3 ans en écrivant cette partie. Vous avez besoin d'un __attribute__((aligned(1))) typedef, ou memcpy pour le rendre sûr.

L'ensemble des choses que l'ISO C laisse indéfinies mais que les intrinsèques d'Intel demandent aux compilateurs de définir inclut la création de pointeurs non alignés (au moins avec des types comme __m128i* ), mais sans les déréférencer directement. Le `reinterpret_cast` entre le pointeur vectoriel SIMD matériel et le type correspondant est-il un comportement non défini ?

---

Vérifier si un pointeur est suffisamment éloigné de la fin d'une page de 4k

Ceci est utile pour le premier vecteur de strlen ; après cela, vous pouvez p = (p+16) & -16 pour passer au vecteur aligné suivant. Cela se chevauchera partiellement si p n'était pas aligné sur 16 octets, mais faire du travail redondant est parfois le moyen le plus compact de mettre en place une boucle efficace. L'éviter pourrait signifier boucler 1 octet à la fois jusqu'à une limite d'alignement, et c'est certainement pire.

par exemple, vérifier ((p + 15) ^ p) & 0xFFF...F000 == 0 (LEA / XOR / TEST) qui vous indique que le dernier octet d'un chargement de 16 octets a les mêmes bits d'adresse de page que le premier octet. Ou encore p+15 <= p|0xFFF (LEA / OR / CMP avec un meilleur ILP) vérifie que le dernier octet-adresse du chargement est <= le dernier octet de la page contenant le premier octet.

Ou plus simplement, p & 4095 > (4096 - 16) (MOV / AND / CMP), soit p & (pgsize-1) < (pgsize - vecwidth) vérifie que le décalage dans la page est suffisamment éloigné de la fin d'une page.

Vous pouvez utiliser une taille d'opération de 32 bits pour économiser de la taille de code (préfixes REX) pour cette vérification ou toute autre, car les bits de poids fort n'ont pas d'importance. Certains compilateurs ne remarquent pas cette optimisation, vous pouvez donc convertir en unsigned int au lieu de uintptr_t Cependant, pour faire taire les avertissements concernant le code qui n'est pas propre à 64 bits, vous pouvez avoir besoin d'utiliser la fonction (unsigned)(uintptr_t)p . Un gain de taille de code supplémentaire peut être obtenu avec ((unsigned int)p << 20) > ((4096 - vectorlen) << 20) (MOV / SHL / CMP), car shl reg, 20 est de 3 octets, contre and eax, imm32 étant 5, ou 6 pour tout autre registre. (L'utilisation d'EAX permet également d'utiliser la forme abrégée no-modrm de la fonction cmp eax, 0xfff .)

Si vous faites cela en GNU C, vous voudrez probablement typedef unsigned long aliasing_unaligned_ulong __attribute__((aligned(1),may_alias)); pour sécuriser les accès non alignés.

Answer 2

Si vous autorisez la prise en compte des périphériques non-CPU, un exemple d'opération potentiellement dangereuse est l'accès à des régions hors limites de la mémoire de l'ordinateur. Mémoire mappée PCI pages. Il n'y a aucune garantie que le périphérique cible utilise la même taille de page ou le même alignement que le sous-système de mémoire principale. En essayant d'accéder, par exemple, à l'adresse [cpu page base]+0x800 peut déclencher un défaut de page de périphérique si le périphérique est en mode page 2KiB. Cela provoque généralement un bugcheck du système.