Imagem - www.freepik.com
Vários anos atrás, pensei e escrevi muito sobre matemática de ponto flutuante. Foi muito interessante, e no processo de pesquisa, aprendi muito, mas às vezes muito tempo não utilizava na prática todas essas habilidades recebia trabalho pesado. Portanto, fico extremamente satisfeito cada vez que tenho que trabalhar em um bug que requer vários conhecimentos especializados. Neste artigo, contarei três histórias sobre bugs de ponto flutuante que aprendi no Chromium.
Parte 1: expectativas irrealistas
O bug foi chamado de "JSON não analisa inteiros de 64 bits corretamente"; Não parece um ponto flutuante ou problema de navegador no início, mas foi postado em crbug.com, então me pediram para dar uma olhada. A maneira mais fácil de recriá-lo é abrindo as ferramentas de desenvolvedor do Chrome (F12 ou Ctrl + Shift + I) e colando o seguinte código no console do desenvolvedor:
json = JSON.parse(‘{“x”: 2940078943461317278}’); alert(json[‘x’]);Inserir código desconhecido na janela do console é uma ótima maneira de ser hackeado, mas o código era tão simples que pude descobrir que não era malicioso. No relatório de bug, o autor gentilmente indicou suas expectativas e resultados reais:
Qual é o comportamento esperado? Deve ser devolvido um valor inteiro de 2940078943461317278.
Qual é o erro? Em vez disso, é retornado um número inteiro 2940078943461317000.
O "bug" foi encontrado no Linux, e estou trabalhando no Chrome para Windows, mas esse comportamento é multiplataforma e eu tinha conhecimento de números de ponto flutuante, então pesquisei.
Este comportamento de inteiros é potencialmente um bug de ponto flutuante, porque realmente não existe nenhum tipo de inteiro em JavaScript. E pelo mesmo motivo, isso não é realmente um bug.
O número inserido é bastante grande, é aproximadamente igual a 2,9e18. E esse é o problema. Como o JavaScript não tem um tipo inteiro, ele usa precisão dupla de ponto flutuante IEEE-754 para números . Este formato de ponto flutuante binário tem um bit de sinal, um expoente de 11 bits e uma mantissa de 53 bits (sim, são 65 bits, um bit está escondido por magia) Este tipo duplo é tão bom em armazenar inteiros que muitos programadores de JavaScript nunca perceberam que não havia tipo inteiro. No entanto, um número muito grande destrói essa ilusão.
O número JavaScript pode armazenar qualquer valor inteiro até 2 ^ 53 com precisão. Depois disso, ele pode armazenar todos os números pares até 2 ^ 54. Depois disso, ele pode armazenar todos os múltiplos de quatro números até 2 ^ 55 e assim por diante.
O número do problema é expresso em notação exponencial de base 2, que é aproximadamente 1,275 * 2 ^ 61. Somente um número muito pequeno de números inteiros pode ser expresso neste intervalo - a distância entre os números é 512. Aqui estão os três números correspondentes:
- 2 940 078 943 461 317 278 é o número que o autor do relatório de bug queria manter
- 2 940 078 943 461 317 120 - o dobro mais próximo deste número (menos que isso)
- 2 940 078 943 461 317 632 - o próximo mais próximo do número duplo (maior que ele)
O número de que precisamos está no intervalo entre esses dois duplos e o módulo JSON (por exemplo, o próprio JavaScript ou qualquer outra função implementada corretamente para converter texto em duplo) fez o melhor e retornou o duplo mais próximo. Simplificando, o número que o autor do relatório deseja salvar não pode ser armazenado no tipo numérico JavaScript integrado .
Até agora, está tudo claro: se você atinge os limites da linguagem, precisa saber mais sobre como funciona. Mas ainda há mais um mistério. No relatório de bug está escrito que de fato o seguinte número é retornado:
2 940 078 943 461 317 000
A situação é curiosa, porque não se trata de um número introduzido, nem do duplo mais próximo e, na verdade, nem mesmo de um número que possa ser representado como um duplo!
Este quebra-cabeça também é explicado pela especificação JavaScript. A especificação diz que, ao imprimir um número, uma implementação deve produzir um número suficiente de dígitos para identificá-lo exclusivamente, e nada mais. Isso é útil para imprimir números como 0,1, que não podem ser representados com precisão como um duplo. Por exemplo, se o JavaScript exigisse 0,1 para ser gerado como um valor armazenado, ele produziria:
0,1000000000000000055511151231257827021181583404541015625
Seria um resultado preciso , mas apenas confundiria as pessoas por não adicionar nada útil. Regras específicas podem ser encontradas aqui (procure a linha "ToString Aplicado ao Tipo de Número"). Não acho que a especificação exija zeros à direita, mas certamente exige .
Portanto, quando o programa é executado, o JavaScript gera 2.940.078.943.461.317.000 porque:
- O valor do número original foi perdido quando salvo como número JavaScript
- O número exibido é próximo o suficiente do valor armazenado para identificá-lo exclusivamente
- O número exibido é o número mais simples que identifica exclusivamente o valor armazenado
Tudo funciona como deveria, isso não é um bug, o problema está fechado como WontFix ("irrecuperável"). O bug original pode ser encontrado aqui .
Parte 2: épsilon ruim
Desta vez, resolvi o bug, primeiro no Chromium e depois no googletest, para evitar confusão para as futuras gerações de desenvolvedores.
Este bug foi uma falha de teste não determinística que começou a acontecer repentinamente. Odiamos essas falhas de teste difuso. Eles ficam especialmente confusos quando começam a acontecer em um teste que não muda há anos. Algumas semanas depois, fui chamado para investigar. As mensagens de erro (ligeiramente modificadas para comprimentos de linha) começaram assim:
A diferença entre esperados_microsegundos e convertidos_microsegundos é 512, que excede 1.0 [A diferença entre esperados_microsegundos e convertidos_microsegundos é 512, que excede 1.0]
Sim, isso soa mal. Esta é uma mensagem de erro mais googletest dizendo que dois valores de vírgula flutuante que não deveriam estar separados por mais de 1,0 estão na verdade separados por 512. A
primeira evidência foi a diferença entre os números de ponto flutuante Pareceu muito suspeito que os dois números sejam separados por exatamente 2 ^ 9. Coincidência? Acho que não. O resto da postagem, que indicava os dois valores sendo comparados, me convenceu ainda mais do motivo:
esperados_microsegundos avaliada em 4,2934311416234112e + 18,
convertido_microsegundos avaliada em 4,2934311416234107e + 18
Se você lutou com o IEEE 754 por tempo suficiente , compreenderá imediatamente o que está acontecendo.
Você leu a primeira parte, então pode sentir um déjà vu por causa dos mesmos números. No entanto, isso é pura coincidência - eu apenas uso os números que encontrei. Desta vez foram apresentados em formato exponencial, o que torna o artigo um pouco diversificado.
O problema principal é uma variação do problema da primeira parte: os números de ponto flutuante em computadores são diferentes dos números reais usados por matemáticos. Eles se tornam menos precisos à medida que aumentam, e todos os duplos eram necessariamente múltiplos de 512 no intervalo dos números com falha. Double tem 53 bits de precisão e esses números eram muito maiores do que 2 ^ 53, portanto, uma redução significativa na precisão era inevitável. E agora podemos entender o problema.
O teste calculou o mesmo valor de duas maneiras diferentes. Ele então verificou se os resultados estavam próximos, com “proximidade” significando uma diferença dentro de 1,0. Os métodos de cálculo deram respostas muito semelhantes, portanto, na maioria dos casos, os resultados foram arredondados para o mesmo valor com precisão dupla. No entanto , de vez em quandoa resposta correta está perto da inflexão, e um cálculo arredonda para um lado e o outro arredonda para outro.
Mais especificamente, como resultado, os seguintes números foram comparados:
- 4293431141623410688
- 4293431141623411200
Sem expoentes, é mais perceptível que eles estão separados por exatamente 512. Os dois resultados infinitamente precisos gerados pelas funções de teste sempre diferiram em menos de 1,0, ou seja, quando eram valores como 429 ... 10653,5 e 429 ... 10654,3, ambos foram arredondados para 429 ... 10688. O problema ocorria quando resultados infinitamente precisos estavam próximos de um valor como 4293431141623410944. Esse valor está exatamente no meio do caminho entre duas duplas. Se uma função gerar 429 ... 10943,9 e a outra 429 ... 10944,1, esses resultados, divididos por um valor de apenas 0,2, foram arredondados em direções diferentes e terminaram a uma distância de 512!
Essa é a natureza da inflexão, ou função degrau. Você pode obter dois resultados, arbitrariamente próximos um do outro, mas localizados em lados opostos da inflexão - pontos exatamente no meio entre os dois - e, portanto, arredondados em direções diferentes. Freqüentemente, é recomendado alterar o modo de arredondamento, mas isso não ajuda - apenas move o ponto de inflexão.
É como ter um bebê por volta da meia-noite - um pequeno desvio pode mudar permanentemente a data (ou talvez um ano, século ou milênio) do evento.
Talvez minha nota de confirmação tenha sido dramática demais, mas infalível. Eu me senti como um especialista único capaz de lidar com esta situação:
commit 6c2427457b0c5ebaefa5c1a6003117ca8126e7bc
Autor: Bruce Dawson
Data: Sex Dec 08 21:58:50 2017
Corrigir cálculo de epsilon para comparações grandes e duplas
Minha vida inteira levou a essa correção de bug. [Minha vida inteira me levou a consertar esse bug.]
Na verdade, eu raramente consigo fazer uma alteração no Chromium com uma nota de confirmação que vincula razoavelmente a duas (2!) Das minhas postagens .
A solução neste caso era calcular a diferença entre dois duplos vizinhos com a magnitude dos valores calculados. Isso foi feito com a função nextafter raramente usada . Mais ou menos assim:
epsilon = nextafter(expected, INFINITY) – expected;
if (epsilon < 1.0)
epsilon = 1.0;O nextafter função encontra a próxima dupla (neste caso, no sentido infinito), e a subtração (que é feito exatamente, e isso é muito conveniente), em seguida, encontra a diferença entre as duplas pelo seu valor. O algoritmo testado deu um erro de 1.0, portanto, epsilon não deve ser maior que esse valor. Este cálculo de epsilon torna muito fácil verificar se os valores estão separados por menos de 1,0 ou duplicados adjacentes.
Não investiguei o motivo pelo qual o teste começou a falhar repentinamente, mas suspeito que seja uma frequência do cronômetro ou uma mudança no ponto inicial do cronômetro que fez com que os números aumentassem.
. QueryPerformanceCounter (QPC), <int64>::max(), 2^63-1. , . , , QPC 2 148 . , QPC, , , , , 3 . QPC 2^63-1 , .
, , QueryPerformanceCounter.
googletest
Fiquei aborrecido porque a compreensão do problema exigia um conhecimento esotérico das especificações do ponto flutuante, então eu queria consertar o googletest . Minha primeira tentativa terminou mal.
Eu originalmente tentei consertar o googletest fazendo EXPECT_NEAR falhar ao transmitir epsilon insignificantemente pequeno, no entanto, parece que muitos testes dentro do Google, e provavelmente muitos outros fora do Google, usam EXPECT_NEAR incorretamente em valores duplos. Eles passam um valor epsilon que é muito pequeno para ser útil, mas os números que eles comparam são os mesmos, portanto, o teste é bem-sucedido. Eu consertei uma dúzia de pontos de usar EXPECT_NEAR sem chegar perto de resolver o problema, então desisti.
Foi só quando escrevi este post (quase três anos depois que o bug apareceu!) Que percebi como era seguro e fácil consertar o googletest. Se o código usar EXPECT_NEAR com muito pouco epsilon e o teste for bem-sucedido (ou seja, os valores são realmente iguais), isso não é um problema. Isso só se torna um problema quando o teste falha, então bastava eu pesquisar por valores de epsilon muito pequenos apenas em caso de falha e exibir uma mensagem informativa ao mesmo tempo.
Fiz essa alteração e agora a mensagem de erro para esta falha de 2017 é assim:
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.
Observe que EXPECT_DOUBLE_EQ não verifica realmente a igualdade, ele verifica se os duplos são iguais a quatro unidades no último dígito (unidades na última posição, ULP). Você pode ler mais sobre esse conceito em minha postagem Comparando números de ponto flutuante .
Espero que a maioria dos desenvolvedores de software veja essa nova mensagem de erro e siga o caminho certo, e acredito que corrigir o googletest é, em última análise, mais importante do que corrigir o teste do Chromium.
Parte 3: quando x + y = x (y! = 0)
Esta é outra variação dos problemas de precisão ao se aproximar dos limites: Talvez eu apenas encontre o mesmo bug de ponto flutuante repetidamente?
Nesta parte, também descreverei as técnicas de depuração que você pode aplicar se quiser investigar o código-fonte do Chromium ou investigar a causa da falha.
Quando me deparei com esse problema, postei um relatório de bug intitulado "Erro de falha com OOM (falta de memória) em chrome: // tracing when zooming in "; não parece um bug de ponto flutuante.
Como sempre, eu não estava procurando por problemas, mas apenas estudando chrome: // tracing, tentando entender alguns dos eventos; uma triste guia apareceu de repente - houve uma falha.
Você pode ver e fazer o download das falhas mais recentes do Chrome em chrome: // crashes, mas eu queria carregar o despejo de memória no depurador, então olhei onde eles estão armazenados localmente:
% localappdata% \ Google \ Chrome \ User Data \ Crashpad \ reports
Carreguei o despejo de memória mais recente para windbg (o Visual Studio também servirá) e, em seguida, comecei a investigar. Como eu tinha os servidores de símbolos Chrome e Microsoft configurados e o servidor de origem habilitado, o depurador baixou automaticamente o PDB (informações de depuração) e os arquivos de origem necessários. Observe que esse esquema está disponível para todos - você não precisa ser um funcionário do Google ou um desenvolvedor do Chromium para que essa mágica funcione. As instruções para configurar a depuração do Chrome / Chromium podem ser encontradas aqui . O download automático do código-fonte requer a instalação do Python.
A análise de falha mostrou que o erro de falta de memória se deve ao fato de que a função NewFixedDoubleArray v8 (mecanismo JavaScript)tenta alocar uma matriz com 75.209.227 elementos, e o tamanho máximo permitido neste contexto é 67.108.863 (0x3FFFFFF em hexadecimal).
O bom dos problemas que eu mesmo causei é que você pode tentar recriá-los com um monitoramento mais cuidadoso. Experimentos mostraram que, quando ampliada, a memória permanecia estável até que eu chegasse ao ponto crítico, após o qual o uso da memória disparou repentinamente e a guia travou, mesmo que eu não fizesse nada.
O problema aqui era que eu podia facilmente visualizar a pilha de chamadas para essa falha, mas apenas na parte C ++ do código do Chrome. No entanto, aparentemente, o próprio bug apareceu no código JavaScript chrome: // tracing. Tentei testá-lo com uma versão canário do Chrome (diariamente) no depurador e recebi a seguinte mensagem curiosa:
==== Rastreio de pilha JS =========================================
Infelizmente, não houve rastreamento de pilha por trás dessa linha interessante. Depois de vagar um pouco nas florestas do git , descobri que a capacidade de gerar pilhas de chamadas JS sobre OOM foi adicionada em 2015 e removida em dezembro de 2019 .
Eu pesquisei esse bug no início de janeiro de 2020 (lembra daqueles bons velhos tempos quando tudo era inocente e mais fácil?), E isso significava que o código de rastreamento de pilha OOM foi removido da compilação diária, mas ainda permaneceu em uma montagem estável ...
Portanto, minha próxima etapa foi tentar recriar o bug na versão estável do Chrome. Isso me deu os seguintes resultados (eu os editei um pouco para maior clareza):
0: ExitFrame [pc: 00007FFDCD887FBD]
1: drawGrid_ [000016011D504859] [chrome: //tracing/tracing.js: ~ 4750]
2: draw [000016011D504821] [chrome: //tracing/tracing.js: 4750]
Resumindo, a falha do OOM foi causada por drawGrid_ , que encontrei (usando a página de pesquisa de código do Chromium ) em x_axis_track.html. Depois de ajustar um pouco esse arquivo, reduzi-o a chamar updateMajorMarkData . Esta função contém um loop que chama a função majorMarkWorldPositions_.push , que é a culpada do problema.
Vale a pena mencionar aqui que, embora eu desenvolva um navegador, continuo o pior programador de JavaScript do mundo. Habilidade em programação de sistemas C ++ não me dá a magia do "frontend". Hackear o JavaScript para entender esse bug foi um processo muito doloroso para mim.
O loop (que pode ser visto aqui ) era mais ou menos assim:
for (let curX = firstMajorMark;
curX < viewRWorld;
curX += majorMarkDistanceWorld) {
this.majorMarkWorldPositions_.push(
Math.floor(MAJOR_MARK_ROUNDING_FACTOR * curX) /
MAJOR_MARK_ROUNDING_FACTOR);
}Eu adicionei instruções de saída de depuração antes do loop e obtive os dados mostrados abaixo. Quando aumentei o zoom da imagem, os números que eram críticos, mas não o suficiente para causar um travamento, ficavam assim:
firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 1e-13
Então, aumentei o zoom para causar uma falha e obtive números como este:
firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 5e-14
885 dividido por 5e-14 é 1,8e16, e a precisão de um número de ponto flutuante de precisão dupla é 2 ^ 53, que é 9,0e15. Portanto, um bug ocorre quando o majorMarkDistanceWorld (distância entre os pontos da grade) é tão pequeno em relação ao firstMajorMark (a localização da primeira marca da grade principal) que adicionar um loop ... não faz nada. Ou seja, se adicionarmos um número pequeno a um grande, então quando o pequeno for "muito pequeno", o número grande pode (no arredondamento padrão / lógico para o modo mais próximo) permanecer igual ao mesmo valor.
Por causa disso, o loop é executado indefinidamente e o comando push é executado até que a matriz seja limitada ao seu tamanho. Se não houvesse limites de tamanho, o comando push continuaria a ser executado até que toda a máquina ficasse sem memória. Então, hooray, problema resolvido?
A correção acabou sendo muito simples - não exiba rótulos de grade se não pudermos:
if (firstMajorMark / majorMarkDistanceWorld > 1e15) return;
Como costuma ser o caso com as alterações que faço, minha correção de bug consistia em uma linha de código e um comentário de seis linhas. Estou apenas surpreso que não houve nenhuma nota de commit de pentâmetro iâmbico de 50 linhas, notação de notação e postagem de blog. Espere um minuto ...
Infelizmente, os stack frames do JavaScript ainda não são exibidos em travamentos OOM, porque leva memória para gravar as pilhas de chamadas, o que significa que não é seguro neste estágio. Não entendo muito bem como investigaria esse bug hoje, quando os stack frames OOM foram completamente removidos, mas tenho certeza de que encontraria uma maneira.
Portanto, se você é um desenvolvedor de JavaScript tentando usar números extremamente grandes, um escritor de teste tentando usar o maior valor inteiro ou implementando uma IU com zoom ilimitado, é importante lembrar que, conforme você se aproxima dos limites da matemática de ponto flutuante, esses limites podem ser quebrados.
Publicidade
Os servidores de desenvolvimento da Vdsina são épicos .
Usamos drives NVMe extremamente rápidos da Intel e não economizamos em hardware - apenas equipamentos de marca e as soluções mais modernas do mercado!
