Image - www.freepik.com
Il y a plusieurs années, j'ai beaucoup réfléchi et écrit sur les mathématiques en virgule flottante. C'était très intéressant, et dans le processus de recherche, j'ai beaucoup appris, mais parfois je n'ai pas utilisé pendantlongtempsdans la pratique toutes ces compétences ont reçu un travail lourd. Par conséquent, je suis extrêmement heureux à chaque fois que je dois travailler sur un bogue qui nécessite diverses connaissances spécialisées. Dans cet article, je vais raconter trois histoires sur les bogues en virgule flottante que j'ai apprises dans Chromium.
Partie 1: attentes irréalistes
Le bogue s'appelait "JSON n'analyse pas correctement les entiers 64 bits"; Cela ne ressemble pas à un problème de virgule flottante ou de navigateur au début, mais il a été publié sur crbug.com, alors on m'a demandé de jeter un coup d'œil. Le moyen le plus simple de le recréer consiste à ouvrir les outils de développement Chrome (F12 ou Ctrl + Maj + I) et à coller le code suivant dans la console développeur:
json = JSON.parse(‘{“x”: 2940078943461317278}’); alert(json[‘x’]);L'insertion de code inconnu dans la fenêtre de la console est un excellent moyen d'être piraté, mais le code était si simple que je pouvais comprendre qu'il n'était pas malveillant. Dans le rapport de bogue, l'auteur a gentiment indiqué ses attentes et ses résultats réels:
Quel est le comportement attendu? Une valeur entière de 2940078943461317278 doit être renvoyée.
Quelle est l'erreur? Un entier 2940078943461317000 est renvoyé à la place.
Le "bogue" a été trouvé sur Linux, et je travaille sur Chrome pour Windows, mais ce comportement est multiplateforme, et j'avais connaissance des nombres à virgule flottante, alors je l'ai recherché.
Ce comportement des entiers est potentiellement un bogue en virgule flottante, car il n'y a vraiment pas de type entier dans JavaScript. Et pour la même raison, ce n'est pas réellement un bug.
Le nombre saisi est assez grand, il est approximativement égal à 2,9e18. Et c'est ça le problème. Comme JavaScript n'a pas de type entier, il utilise la double précision à virgule flottante IEEE-754 pour les nombres . Ce format binaire à virgule flottante a un bit de signe, un exposant de 11 bits et une mantisse de 53 bits (oui, c'est 65 bits, un bit est caché par magie). Ce type double est si efficace pour stocker des entiers que de nombreux programmeurs JavaScript n'ont jamais remarqué qu'il n'y avait pas de type entier. Cependant, un très grand nombre détruit cette illusion.
Le numéro JavaScript peut stocker n'importe quelle valeur entière jusqu'à 2 ^ 53 avec précision. Après cela, il peut stocker tous les nombres pairs jusqu'à 2 ^ 54. Après cela, il peut stocker tous les multiples de quatre nombres jusqu'à 2 ^ 55, et ainsi de suite.
Le numéro du problème est exprimé en notation exponentielle de base 2, soit environ 1,275 * 2 ^ 61. Seul un très petit nombre d'entiers peut être exprimé dans cet intervalle - la distance entre les nombres est de 512. Voici les trois nombres correspondants:
- 2940 078 943461317278 est le numéro que l'auteur du rapport de bogue souhaitait conserver
- 2940078943461317120 - le double le plus proche de ce nombre (inférieur à lui)
- 2940078943461317632 - le prochain le plus proche du nombre double (supérieur à lui)
Le nombre dont nous avons besoin est dans l'intervalle entre ces deux doubles et le module JSON (par exemple, JavaScript lui-même ou toute autre fonction correctement implémentée pour convertir du texte en double) a fait de son mieux et a renvoyé le double le plus proche. En termes simples, le numéro que l'auteur du rapport souhaitait stocker ne peut pas être stocké dans le type numérique JavaScript intégré .
Jusqu'à présent, tout est clair: si vous atteignez les limites de la langue, vous devez en savoir plus sur son fonctionnement. Mais il reste encore un mystère. Le rapport de bogue indique qu'en fait le numéro suivant est renvoyé:
2 940 078 943461317 000
La situation est curieuse, car ce n'est pas un nombre saisi, pas le double le plus proche et, en fait, même pas un nombre qui peut être représenté comme un double!
Ce puzzle est également expliqué par la spécification JavaScript. La spécification indique que lors de l'impression d'un nombre, l'implémentation doit produire un nombre suffisant de chiffres pour l'identifier de manière unique, et pas plus. Ceci est utile pour imprimer des nombres tels que 0,1, qui ne peuvent pas être représentés avec précision par un double. Par exemple, si JavaScript exigeait que 0,1 soit généré en tant que valeur stockée, il produirait:
0,1000000000000000055511151231257827021181583404541015625
Ce serait un résultat précis , mais cela ne ferait que dérouter les gens sans rien ajouter d'utile. Des règles spécifiques peuvent être trouvées ici (recherchez la ligne "ToString Applied to the Number Type"). Je ne pense pas que la spécification nécessite des zéros à la fin, mais c'est certainement le cas.
Ainsi, lorsque le programme s'exécute, JavaScript génère 2,940,078,943,461,317,000 parce que:
- La valeur numérique d'origine a été perdue lors de l'enregistrement en tant que numéro JavaScript
- Le nombre affiché est suffisamment proche de la valeur stockée pour l'identifier de manière unique
- Le nombre affiché est le nombre le plus simple qui identifie de manière unique la valeur stockée
Tout fonctionne comme il se doit, ce n'est pas un bug, le problème est fermé comme WontFix ("irrécupérable"). Le bogue original peut être trouvé ici .
Partie 2: mauvais epsilon
Cette fois, j'ai en fait corrigé le bogue, d'abord dans Chromium, puis dans googletest, pour éviter toute confusion pour les générations futures de développeurs.
Ce bogue était un échec de test non déterministe qui a commencé à se produire soudainement. Nous détestons ces échecs de test flous. Ils sont particulièrement déroutants lorsqu'ils commencent à se produire dans un test qui n'a pas changé depuis des années. Quelques semaines plus tard, ils m'ont fait entrer dans l'enquête. Les messages d'erreur (légèrement modifiés pour les longueurs de ligne) ont commencé quelque chose comme ceci:
La différence entre les microsecondes attendues et les microsecondes converties est de 512, ce qui dépasse 1,0 [La différence entre les microsecondes attendues et les microsecondes converties est de 512, ce qui dépasse 1,0]
Oui, ça sonne mal. Il s'agit d'un message d'erreur googletest disant que deux valeurs à virgule flottante qui ne devraient pas être distantes de plus de 1,0 sont en fait espacées de 512. La
première preuve était la différence entre les nombres à virgule flottante. Il semblait très suspect que les deux nombres soient séparés par exactement 2 ^ 9. Coïncidence? Je ne pense pas. Le reste de l'article, qui indiquait les deux valeurs comparées, m'a encore plus convaincu de la raison:
attendu_microsecondes prend la valeur 4,2934311416234112e + 18,
converti_microsecondes est évalué à 4,2934311416234107e + 18
Si vous vous êtes battu avec IEEE 754 assez longtemps , vous comprendrez immédiatement ce qui se passe.
Vous avez lu la première partie, vous pouvez donc ressentir du déjà vu à cause des mêmes chiffres. Cependant, c'est une pure coïncidence - j'utilise simplement les chiffres que j'ai rencontrés. Cette fois, ils étaient affichés au format exponentiel, ce qui rend l'article un peu diversifié.
Le problème principal est une variation du problème par rapport à la première partie: les nombres à virgule flottante dans les ordinateurs sont différents des nombres réels utilisés par les mathématiciens. Ils deviennent moins précis à mesure qu'ils augmentent, et tous les doubles étaient nécessairement des multiples de 512 dans la gamme des nombres défaillants. Double a 53 bits de précision et ces nombres étaient beaucoup plus grands que 2 ^ 53, donc une réduction significative de la précision était inévitable. Et maintenant, nous pouvons comprendre le problème.
Le test a calculé la même valeur de deux manières différentes. Puis il a vérifié pour voir si les résultats étaient proches, avec «proximité» signifiant une différence de 1,0. Les méthodes de calcul ont donné des réponses très similaires, de sorte que dans la plupart des cas, les résultats ont été arrondis à la même valeur avec une double précision. Cependant , de temps en tempsla bonne réponse est proche de l'inflexion, et un calcul arrondit dans un sens et l'autre arrondit une autre.
Plus précisément, en conséquence, les chiffres suivants ont été comparés:
- 4293431141623410688
- 4293431141623411200
Sans exponentielles, il est plus visible qu'ils sont séparés par exactement 512. Les deux résultats infiniment précis générés par les fonctions de test différaient toujours de moins de 1,0, c'est-à-dire quand ils étaient des valeurs comme 429 ... 10653,5 et 429 ... 10654,3, les deux étaient arrondis à 429 ... 10688. Le problème s'est produit lorsque des résultats infiniment précis étaient proches d'une valeur telle que 4293431141623410944. Cette valeur est exactement à mi-chemin entre deux doubles. Si une fonction génère 429 ... 10943,9 et l'autre 429 ... 10944,1, alors ces résultats, divisés par une valeur de seulement 0,2, ont été arrondis dans des directions différentes et se sont retrouvés à une distance de 512!
C'est la nature de la flexion ou de la fonction de pas. Vous pouvez obtenir deux résultats, arbitrairement proches l'un de l'autre, mais situés sur des côtés opposés de l'inflexion - des points exactement au milieu entre les deux - et donc arrondis dans des directions différentes. Il est souvent recommandé de changer le mode d'arrondi, mais cela n'aide pas - cela déplace simplement le point d'inflexion.
C'est comme avoir un bébé vers minuit - un petit écart peut changer de façon permanente la date (peut-être un an, un siècle ou un millénaire) d'inscription à l'événement.
Peut-être que ma note de commit était trop dramatique, mais infaillible. Je me sentais comme un spécialiste unique, capable de gérer cette situation:
commit 6c2427457b0c5ebaefa5c1a6003117ca8126e7bc
Auteur: Bruce Dawson
Date: Fri Dec 08 21:58:50 2017
Correction du calcul epsilon pour les comparaisons grand-double
Toute ma vie a conduit à ce correctif de bogue. [Toute ma vie m'a amené à corriger ce bug.]
En effet, j'arrive rarement à faire un changement dans Chromium avec une note de commit qui lie assez raisonnablement à deux (2!) De mes messages .
Le correctif dans ce cas était de calculer la différence entre deux doubles voisins avec la magnitude des valeurs calculées. Cela a été fait avec la fonction nextafter rarement utilisée . Plus ou moins comme ceci:
epsilon = nextafter(expected, INFINITY) – expected;
if (epsilon < 1.0)
epsilon = 1.0;La fonction nextafter trouve le double suivant (dans ce cas, dans le sens de l'infini), et la soustraction (ce qui est fait exactement, et c'est très pratique) trouve alors la différence entre les doubles à leur valeur. L'algorithme testé a donné une erreur de 1.0, donc epsilon ne doit pas dépasser cette valeur. Ce calcul de epsilon permet de vérifier très facilement si les valeurs sont distantes de moins de 1,0 ou si les doubles sont adjacents.
Je n’ai pas étudié la raison pour laquelle le test a soudainement commencé à échouer, mais je soupçonne que c’est une fréquence de minuterie ou un changement du point de départ de la minuterie qui a entraîné une augmentation des nombres.
. QueryPerformanceCounter (QPC), <int64>::max(), 2^63-1. , . , , QPC 2 148 . , QPC, , , , , 3 . QPC 2^63-1 , .
, , QueryPerformanceCounter.
googletest
J'étais ennuyé par le fait que la compréhension du problème nécessitait une connaissance ésotérique des spécificités de la virgule flottante, alors je voulais corriger googletest . Ma première tentative s'est mal terminée.
J'ai initialement essayé de corriger googletest en faisant échouer EXPECT_NEAR lors de la transmission d'un epsilon insignifiant, mais il semble que beaucoup de tests à l'intérieur de Google, et probablement beaucoup plus en dehors de Google, abusent de EXPECT_NEAR sur des valeurs doubles. Ils passent une valeur epsilon qui est trop petite pour être utile, mais les nombres qu'ils comparent sont les mêmes, donc le test réussit. J'ai corrigé une douzaine de points d'utilisation de EXPECT_NEAR sans me rapprocher de la résolution du problème, alors j'ai abandonné.
Ce n'est que lorsque j'écrivais cet article (près de trois ans après l'apparition du bogue!) Que j'ai réalisé à quel point il était facile et sûr de corriger googletest. Si le code utilise EXPECT_NEAR avec trop peu d'epsilon et que le test réussit (c'est-à-dire que les valeurs sont en fait égales), alors ce n'est pas un problème. Cela ne devient un problème que lorsque le test échoue, il me suffisait donc de rechercher des valeurs epsilon trop petites uniquement en cas d' échec et d'afficher un message informatif en même temps.
J'ai effectué ce changement et maintenant le message d'erreur pour ce crash de 2017 ressemble à ceci:
expected_microseconds converted_microseconds 512,
expected_microseconds 4.2934311416234112e+18,
converted_microseconds evaluates to 4.2934311416234107e+18.
abs_error 1.0, double , 512; EXPECT_NEAR EXPECT_EQUAL. EXPECT_DOUBLE_EQ.
Notez que EXPECT_DOUBLE_EQ ne vérifie pas réellement l'égalité, il vérifie si les doubles sont égaux à quatre unités dans le dernier chiffre (unités en dernier lieu, ULP). Vous pouvez en savoir plus sur ce concept dans mon article Comparaison des nombres à virgule flottante .
J'espère que la plupart des développeurs de logiciels verront ce nouveau message d'erreur et prendront le bon chemin, et je pense que la correction de googletest est finalement plus importante que la correction du test Chromium.
Partie 3: quand x + y = x (y! = 0)
Ceci est une autre variante des problèmes de précision à l'approche des limites: peut-être que je trouve le même bogue en virgule flottante encore et encore?
Dans cette partie, je décrirai également les techniques de débogage que vous pouvez appliquer si vous souhaitez étudier le code source de Chromium ou rechercher la cause d'un crash.
Quand je suis tombé sur ce problème, j'ai posté un rapport de bogue intitulé " Crash with OOM (Out of Memory) error in chrome: // tracing when zooming "; ce n'est pas comme un bug en virgule flottante.
Comme d'habitude, je ne cherchais pas moi-même les problèmes, mais j'étudiais juste chrome: // tracing, essayant de comprendre certains des événements; un onglet triste est soudainement apparu - il y a eu un échec.
Vous pouvez afficher et télécharger les derniers plantages pour Chrome sur chrome: // plantages, mais je voulais charger le vidage sur incident dans le débogueur, j'ai donc regardé où ils sont stockés localement:
% localappdata% \ Google \ Chrome \ User Data \ Crashpad \ reports
J'ai téléchargé le vidage sur incident le plus récent sur windbg (Visual Studio le fera également), puis j'ai procédé à une enquête. Depuis que j'ai configuré les serveurs de symboles Chrome et Microsoft et activé le serveur source, le débogueur a automatiquement téléchargé le PDB (informations de débogage) et les fichiers source requis. Notez que ce programme est disponible pour tout le monde - vous n'avez pas besoin d'être un employé de Google ou un développeur Chromium pour que cette magie fonctionne. Vous trouverez ici les instructions de configuration du débogage Chrome / Chromium . Le téléchargement automatique du code source nécessite l'installation de Python.
L'analyse du crash a montré que l'erreur de mémoire insuffisante est due au fait que la fonction v8 (moteur JavaScript) NewFixedDoubleArrayessaie d'allouer un tableau avec 75 209 227 éléments, et la taille maximale autorisée dans ce contexte est 67 108 863 (0x3FFFFFF en hexadécimal).
Ce qui est bien avec les problèmes que je me suis causés, c'est que vous pouvez essayer de les recréer avec une surveillance plus attentive. Des expériences ont montré qu'en zoomant, la mémoire restait stable jusqu'à ce que j'arrive au point critique, après quoi l'utilisation de la mémoire a soudainement explosé et l'onglet s'est écrasé même si je ne faisais rien.
Le problème ici était que je pouvais facilement afficher la pile d'appels pour cet échec, mais seulement en partie du code Chrome C ++. Cependant, apparemment, le bogue lui-même est apparu dans le code JavaScript chrome: // traçant. J'ai essayé de le tester avec une version canari de Chrome (quotidiennement) sous le débogueur et j'ai reçu le message curieux suivant:
==== trace de pile JS =====================================
Malheureusement, il n'y avait aucune trace de pile derrière cette ligne intéressante. Après avoir erré un peu dans la nature de git , j'ai découvert que la possibilité de générer des piles d'appels JS sur OOM avait été ajoutée en 2015 , puis supprimée en décembre 2019 .
J'ai recherché ce bogue début janvier 2020 (vous vous souvenez de ce bon vieux temps où tout était innocent et plus facile?), Et cela signifiait que le code de trace de pile OOM a été supprimé de la construction quotidienne, mais est toujours resté à un assemblage stable ...
Par conséquent, ma prochaine étape consistait à essayer de recréer le bogue dans la version stable de Chrome. Cela m'a donné les résultats suivants (je les ai édités un peu pour plus de clarté):
0: ExitFrame [pc: 00007FFDCD887FBD]
1: drawGrid_ [000016011D504859] [chrome: //tracing/tracing.js: ~ 4750]
2: draw [000016011D504821] [chrome: //tracing/tracing.js: 4750]
En bref, le crash du MOO a été causé par drawGrid_ , que j'ai trouvé (en utilisant la page de recherche de code Chromium ) dans x_axis_track.html. Après avoir légèrement modifié ce fichier, je l'ai réduit à appeler updateMajorMarkData . Cette fonction contient une boucle qui appelle la fonction majorMarkWorldPositions_.push , qui est à l'origine du problème.
Il convient de mentionner ici que bien que je développe un navigateur, je reste le pire programmeur JavaScript au monde. La compétence en programmation de systèmes C ++ ne me donne pas la magie du "frontend". Hacker JavaScript pour comprendre ce bogue a été un processus assez pénible pour moi.
La boucle (qui peut être visualisée ici ) ressemblait à ceci:
for (let curX = firstMajorMark;
curX < viewRWorld;
curX += majorMarkDistanceWorld) {
this.majorMarkWorldPositions_.push(
Math.floor(MAJOR_MARK_ROUNDING_FACTOR * curX) /
MAJOR_MARK_ROUNDING_FACTOR);
}J'ai ajouté des instructions de sortie de débogage avant la boucle et j'ai obtenu les données ci-dessous. Lorsque j'ai zoomé sur l'image, les chiffres qui étaient critiques, mais pas suffisants pour provoquer un crash, ressemblaient à ceci:
firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 1e-13
Ensuite, j'ai zoomé pour provoquer un crash, et j'ai obtenu des chiffres comme celui-ci:
firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 5e-14
885 divisé par 5e-14 est 1,8e16 et la précision d'un nombre à virgule flottante double précision est 2 ^ 53, soit 9,0e15. Par conséquent, un bug se produit lorsque le majorMarkDistanceWorld (distance entre les points de grille) est si petit par rapport à firstMajorMark (l'emplacement de la première marque de grille majeure) que l'ajout d'une boucle ... ne fait rien. Autrement dit, si nous ajoutons un petit nombre à un grand, alors quand le petit est "trop petit", le grand nombre peut (dans l'arrondi standard / sain au mode le plus proche) rester égal à la même valeur.
Pour cette raison, la boucle s'exécute indéfiniment et la commande push est exécutée jusqu'à ce que le tableau soit limité à sa taille. S'il n'y avait pas de limite de taille, la commande push continuerait à s'exécuter jusqu'à ce que la machine entière soit à court de mémoire. Alors hourra, problème résolu?
Le correctif s'est avéré assez simple - n'affichez pas les étiquettes de grille si nous ne pouvons pas:
if (firstMajorMark / majorMarkDistanceWorld > 1e15) return;
Comme c'est souvent le cas avec les modifications que j'apporte , mon correctif consistait en une ligne de code et un commentaire de six lignes. Je suis seulement surpris qu'il n'y ait pas de notes de commit de pentamètre iambique de cinquante lignes, de notation de notation et de billet de blog. Attendez une minute ...
Malheureusement, les cadres de pile JavaScript ne sont toujours pas affichés sur les pannes de MOO, car il faut de la mémoire pour écrire des piles d'appels, ce qui signifie que ce n'est pas sûr à ce stade. Je ne comprends pas très bien comment j'étudierais ce bogue aujourd'hui, lorsque les cadres de la pile MOO ont été complètement supprimés, mais je suis sûr que je trouverais un moyen.
Donc, si vous êtes un développeur JavaScript essayant d'utiliser des nombres extrêmement grands, un écrivain de test essayant d'utiliser la plus grande valeur entière ou implémentant une interface utilisateur avec un zoom illimité, alors il est important de se rappeler que lorsque vous approchez des limites des mathématiques en virgule flottante, ces limites peuvent être dépassées.
La publicité
Les serveurs de développement sont épiques de Vdsina.
Nous utilisons des disques NVMe extrêmement rapides d'Intel et n'économisons pas sur le matériel - uniquement des équipements de marque et les solutions les plus modernes du marché!
