Image - www.freepik.com
Beberapa tahun lalu saya banyak berpikir dan menulis tentang matematika floating point. Itu sangat menarik, dan dalam proses penelitian, saya belajar banyak, tetapi kadang-kadang saya lama tidak menggunakan dalam praktek semua keterampilan ini mendapat kerja berat. Oleh karena itu, saya sangat senang setiap kali saya harus menangani bug yang membutuhkan berbagai pengetahuan khusus. Pada artikel ini, saya akan menceritakan tiga cerita tentang bug floating point yang saya pelajari di Chromium.
Bagian 1: ekspektasi yang tidak realistis
Bug disebut "JSON tidak mengurai 64-bit Integers dengan benar"; Ini tidak terlihat seperti masalah floating point atau browser pada awalnya, tetapi itu telah diposting ke crbug.com jadi saya diminta untuk melihatnya. Cara termudah untuk membuatnya kembali adalah dengan membuka alat pengembang Chrome (F12 atau Ctrl + Shift + I) dan menempelkan kode berikut ke konsol pengembang:
json = JSON.parse(‘{“x”: 2940078943461317278}’); alert(json[‘x’]);Memasukkan kode yang tidak dikenal ke jendela konsol adalah cara yang bagus untuk diretas, tetapi kodenya sangat sederhana sehingga saya tahu itu tidak berbahaya. Dalam laporan bug, penulis dengan ramah menunjukkan ekspektasi dan hasil aktualnya:
Apa perilaku yang diharapkan? Nilai integer 2940078943461317278 harus dikembalikan.
Apa kesalahannya? Integer 2940078943461317000 dikembalikan sebagai gantinya.
"Bug" ditemukan di Linux, dan saya sedang mengerjakan Chrome untuk Windows, tetapi perilaku ini bersifat lintas platform, dan saya memiliki pengetahuan tentang angka floating point, jadi saya menelitinya.
Perilaku integer ini berpotensi menjadi bug floating point, karena sebenarnya tidak ada tipe integer dalam JavaScript. Dan untuk alasan yang sama, ini sebenarnya bukan bug.
Angka yang dimasukkan cukup besar, kira-kira sama dengan 2.9e18. Dan itulah masalahnya. Karena JavaScript tidak memiliki tipe integer, JavaScript menggunakan presisi ganda floating-point IEEE-754 untuk angka . Format titik mengambang biner ini memiliki bit tanda, eksponen 11-bit dan mantissa 53-bit (ya, itu 65 bit, satu bit disembunyikan oleh sihir). Tipe ganda ini sangat bagus dalam menyimpan integer sehingga banyak programmer JavaScript tidak pernah memperhatikan bahwa tidak ada tipe integer. Namun, jumlah yang sangat besar menghancurkan ilusi ini.
Nomor JavaScript dapat menyimpan nilai integer apa pun hingga 2 ^ 53 dengan presisi. Setelah itu, dapat menyimpan semua bilangan genap hingga 2 ^ 54. Setelah itu, dapat menyimpan semua kelipatan empat angka hingga 2 ^ 55, dan seterusnya.
Nomor soal dinyatakan dalam notasi eksponensial basis 2, yang kira-kira 1,275 * 2 ^ 61. Hanya sejumlah kecil bilangan bulat yang dapat diekspresikan dalam interval ini - jarak antara bilangan tersebut adalah 512. Berikut adalah tiga bilangan yang sesuai:
- 2 940 078 943 461 317 278 adalah nomor yang ingin disimpan oleh pembuat laporan bug
- 2 940 078 943 461 317 120 - angka ganda terdekat dengan angka ini (kurang dari itu)
- 2 940 078 943 461 317632 - yang paling dekat dengan angka ganda (lebih besar dari itu)
Angka yang kita butuhkan berada dalam interval antara dua ganda ini dan modul JSON (misalnya, JavaScript itu sendiri atau fungsi lain yang diimplementasikan dengan benar untuk mengubah teks menjadi ganda) melakukan yang terbaik dan mengembalikan ganda terdekat. Sederhananya, nomor yang ingin disimpan oleh penulis laporan tidak dapat disimpan dalam tipe numerik JavaScript bawaan .
Sejauh ini, semuanya jelas: jika Anda mencapai batas bahasa, Anda perlu tahu lebih banyak tentang cara kerjanya. Tapi masih ada satu misteri lagi. Laporan bug mengatakan bahwa sebenarnya nomor berikut dikembalikan:
2 940 078 943 461 317 000
Situasinya aneh, karena ini bukan angka yang dimasukkan, bukan ganda terdekat dan, pada kenyataannya, bukan angka yang dapat direpresentasikan sebagai ganda!
Teka-teki ini juga dijelaskan oleh spesifikasi JavaScript. Spesifikasi mengatakan bahwa ketika mencetak angka, implementasi harus menghasilkan angka yang cukup untuk mengidentifikasinya secara unik, dan tidak lebih. Ini berguna untuk mencetak angka seperti 0,1, yang tidak dapat secara akurat direpresentasikan sebagai ganda. Misalnya, jika JavaScript membutuhkan 0,1 untuk menjadi keluaran sebagai nilai yang disimpan, maka itu akan menghasilkan:
0.1000000000000000055511151231257827021181583404541015625
Ini akan menjadi hasil yang akurat , tetapi itu hanya akan membingungkan orang dengan tidak menambahkan sesuatu yang berguna. Aturan khusus dapat ditemukan di sini (cari baris "ToString yang Diterapkan ke Jenis Nomor"). Saya tidak berpikir speknya membutuhkan angka nol di belakang, tapi memang begitu.
Jadi, saat program dijalankan, JavaScript mengeluarkan 2.940.078.943.461.317.000 karena:
- Nilai nomor asli hilang saat disimpan sebagai nomor JavaScript
- Nomor yang ditampilkan cukup dekat dengan nilai yang disimpan untuk mengidentifikasinya secara unik
- Angka yang ditampilkan adalah angka paling sederhana yang secara unik mengidentifikasi nilai yang disimpan
Semuanya bekerja sebagaimana mestinya, ini bukan bug, masalahnya ditutup sebagai WontFix ("unrecoverable"). Bug asli dapat ditemukan di sini .
Bagian 2: epsilon buruk
Kali ini saya benar-benar memperbaiki bugnya, pertama di Chromium lalu di googletest, untuk menghindari kebingungan bagi generasi pengembang di masa mendatang.
Bug ini adalah kegagalan pengujian non-deterministik yang mulai terjadi secara tiba-tiba. Kami benci kegagalan pengujian fuzzy ini. Mereka sangat membingungkan ketika mulai terjadi dalam ujian yang tidak berubah selama bertahun-tahun. Beberapa minggu kemudian, saya dibawa untuk menyelidiki. Pesan kesalahan (sedikit diubah untuk panjang baris) dimulai seperti ini:
Perbedaan antara expected_microseconds dan convert_microseconds adalah 512, yang melebihi 1.0 [Perbedaan antara expected_microseconds dan convert_microseconds adalah 512, yang melebihi 1.0]
Ya, kedengarannya buruk. Ini adalah pesan kesalahan googletest yang mengatakan bahwa dua nilai floating point yang seharusnya tidak lebih dari 1,0 sebenarnya terpisah 512. Bukti
pertama adalah perbedaan antara bilangan floating point. Tampaknya sangat mencurigakan bahwa kedua angka tersebut dipisahkan oleh 2 ^ 9. Kebetulan? Saya kira tidak. Sisa posting, yang menunjukkan dua nilai yang dibandingkan, meyakinkan saya lebih banyak tentang alasannya:
expected_microseconds mengevaluasi ke 4.2934311416234112e + 18,
convert_microseconds mengevaluasi ke 4.2934311416234107e + 18
Jika Anda sudah cukup lama bertarung dengan IEEE 754 , Anda akan segera memahami apa yang terjadi.
Anda sudah membaca bagian pertama, jadi Anda bisa merasakan déjà vu karena angka yang sama. Namun, ini murni kebetulan - saya hanya menggunakan angka yang saya temui. Kali ini mereka ditampilkan dalam format eksponensial, yang membuat artikelnya sedikit beragam.
Masalah utamanya adalah variasi masalah dari bagian pertama: bilangan floating point di komputer berbeda dengan bilangan real yang digunakan oleh ahli matematika. Mereka menjadi kurang akurat saat mereka meningkat, dan semua ganda tentu kelipatan 512 dalam kisaran angka gagal. Ganda memiliki presisi 53 bit, dan angka ini jauh lebih besar dari 2 ^ 53, jadi pengurangan presisi yang signifikan tidak terhindarkan. Dan sekarang kita bisa mengerti masalahnya.
Tes tersebut menghitung nilai yang sama dengan dua cara berbeda. Kemudian dia memeriksa untuk melihat apakah hasilnya mendekati, dan dengan "kedekatan" berarti perbedaan dalam 1,0. Metode kalkulasi memberikan jawaban yang sangat mirip, jadi dalam banyak kasus, hasilnya dibulatkan ke nilai yang sama dengan presisi ganda. Namun , dari waktu ke waktujawaban yang benar ada di sebelah infleksi, dan satu kalkulasi berputar ke satu arah, dan yang lainnya berputar ke arah lain.
Secara lebih spesifik, sebagai hasilnya, angka-angka berikut dibandingkan:
- 4293431141623410688
- 4293431141623411200
Tanpa eksponen, lebih terlihat bahwa keduanya dipisahkan tepat 512. Dua hasil yang sangat tepat yang dihasilkan oleh fungsi pengujian selalu berbeda kurang dari 1.0, yaitu, jika nilainya seperti 429 ... 10653.5 dan 429 ... 10654.3, keduanya dibulatkan menjadi 429 ... 10688. Masalahnya terjadi ketika hasil yang sangat tepat mendekati nilai seperti 4293431141623410944. Nilai ini persis setengah jalan antara dua ganda. Jika satu fungsi menghasilkan 429 ... 10943.9, dan lainnya 429 ... 10944.1, maka hasil ini, dibagi dengan nilai hanya 0,2, dibulatkan ke arah yang berbeda dan berakhir pada jarak 512!
Ini adalah sifat infleksi, atau fungsi langkah. Anda bisa mendapatkan dua hasil, saling berdekatan secara acak, tetapi terletak di sisi berlawanan dari infleksi - titik tepat di tengah antara keduanya - dan karena itu membulat ke arah yang berbeda. Seringkali disarankan untuk mengubah mode pembulatan, tetapi ini tidak membantu - ini hanya memindahkan titik belok.
Ini seperti memiliki bayi sekitar tengah malam - penyimpangan kecil dapat secara permanen mengubah tanggal (mungkin satu tahun, abad, atau milenium) dari pendaftaran acara.
Mungkin catatan komitmen saya terlalu dramatis, tetapi tidak salah lagi. Saya merasa seperti seorang spesialis unik yang mampu menangani situasi ini:
commit 6c2427457b0c5ebaefa5c1a6003117ca8126e7bc
Penulis: Bruce Dawson
Tanggal: Jum 08 Des 21:58:50 2017
Perbaiki perhitungan epsilon untuk perbandingan besar-ganda
Seluruh hidup saya telah mengarah ke perbaikan bug ini. [Seluruh hidup saya telah membuat saya memperbaiki bug ini.]
Memang, saya jarang berhasil membuat perubahan di Chromium dengan catatan komitmen yang cukup menautkan ke dua (2!) Dari posting saya .
Perbaikan dalam kasus ini adalah menghitung selisih antara dua ganda bertetangga dengan besarnya nilai yang dihitung. Ini dilakukan dengan fungsi nextafter yang jarang digunakan . Kurang lebih seperti ini:
epsilon = nextafter(expected, INFINITY) – expected;
if (epsilon < 1.0)
epsilon = 1.0;The nextafter fungsi menemukan berikutnya ganda (dalam hal ini, ke arah infinity), dan pengurangan (yang dilakukan tepat, dan ini sangat nyaman) kemudian menemukan perbedaan antara ganda pada nilai mereka. Algoritme yang diuji memberikan kesalahan 1,0, jadi epsilon seharusnya tidak lebih dari nilai ini. Perhitungan epsilon ini membuatnya sangat mudah untuk memeriksa apakah nilainya kurang dari 1,0 atau ganda yang berdekatan.
Saya belum menyelidiki alasan mengapa tes tiba-tiba mulai gagal, tetapi saya menduga bahwa frekuensi pengatur waktu atau perubahan titik awal pengatur waktu yang menyebabkan angkanya menjadi lebih besar.
. QueryPerformanceCounter (QPC), <int64>::max(), 2^63-1. , . , , QPC 2 148 . , QPC, , , , , 3 . QPC 2^63-1 , .
, , QueryPerformanceCounter.
googletest
Saya kesal karena memahami masalah ini membutuhkan pengetahuan esoterik tentang spesifik titik mengambang, jadi saya ingin memperbaiki googletest . Upaya pertama saya berakhir dengan buruk.
Awalnya saya mencoba memperbaiki googletest dengan membuat EXPECT_NEAR gagal ketika melewati epsilon yang sangat kecil, namun tampaknya banyak tes di dalam Google, dan mungkin banyak lagi di luar Google, menyalahgunakan EXPECT_NEAR pada nilai ganda. Mereka meneruskan nilai epsilon yang terlalu kecil untuk digunakan, tetapi angka yang mereka bandingkan sama, sehingga pengujian berhasil. Saya memperbaiki selusin poin dalam menggunakan EXPECT_NEAR tanpa mendekati untuk memecahkan masalah, jadi saya menyerah.
Tidak sampai saya menulis posting ini (hampir tiga tahun setelah bug muncul!) Saya menyadari betapa aman dan mudahnya memperbaiki googletest. Jika kode menggunakan EXPECT_NEAR dengan epsilon yang terlalu sedikit dan pengujian berhasil (artinya, nilainya sebenarnya sama), maka ini bukan masalah. Ini menjadi masalah hanya ketika pengujian gagal, jadi cukup bagi saya untuk mencari nilai epsilon yang terlalu kecil hanya jika terjadi kegagalan dan menampilkan pesan informatif pada saat yang sama.
Saya membuat perubahan ini dan sekarang pesan kesalahan untuk kecelakaan 2017 ini terlihat seperti ini:
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.
Perhatikan bahwa EXPECT_DOUBLE_EQ tidak benar-benar memeriksa kesetaraan, ia memeriksa apakah dua kali lipat sama dengan empat unit di digit terakhir (unit di tempat terakhir, ULP). Anda dapat membaca lebih lanjut tentang konsep ini di posting saya Membandingkan Angka Titik Mengambang .
Saya berharap sebagian besar pengembang perangkat lunak melihat pesan kesalahan baru ini dan mengambil jalan yang benar, dan saya yakin bahwa memperbaiki googletest pada akhirnya lebih penting daripada memperbaiki uji Chromium.
Bagian 3: ketika x + y = x (y! = 0)
Ini adalah variasi lain pada masalah presisi saat mendekati batas: Mungkin saya hanya menemukan bug floating point yang sama berulang kali?
Pada bagian ini saya juga akan menjelaskan teknik debugging yang dapat Anda terapkan jika Anda ingin menyelidiki kode sumber Chromium atau menyelidiki penyebab crash.
Ketika saya menemukan masalah ini, saya memposting laporan bug berjudul " Crash with OOM (Out of Memory) error di chrome: // tracing when zooming in "; itu tidak terdengar seperti bug floating point.
Seperti biasa, saya sendiri tidak mencari masalah, tetapi hanya mempelajari chrome: // tracing, mencoba memahami beberapa peristiwa; tab sedih tiba-tiba muncul - terjadi kegagalan.
Anda dapat melihat dan mengunduh kerusakan terbaru untuk Chrome di chrome: // crashes, tetapi saya ingin memuat dump kerusakan ke debugger, jadi saya melihat di mana mereka disimpan secara lokal:
% localappdata% \ Google \ Chrome \ Data Pengguna \ Crashpad \ laporan
Saya mengunggah crash dump terbaru ke windbg (Visual Studio akan melakukannya juga) dan kemudian melanjutkan untuk menyelidikinya. Karena saya telah mengkonfigurasi server simbol Chrome dan Microsoft dan server sumber diaktifkan, debugger secara otomatis mengunduh PDB (informasi debug) dan file sumber yang diperlukan. Perhatikan bahwa skema ini tersedia untuk semua orang - Anda tidak perlu menjadi karyawan Google atau pengembang Chromium agar keajaiban ini berfungsi. Petunjuk untuk menyiapkan proses debug Chrome / Chromium dapat ditemukan di sini . Download otomatis kode sumber memerlukan instalasi Python.
Analisis kerusakan menunjukkan bahwa kesalahan kehabisan memori disebabkan oleh fakta bahwa v8 (mesin JavaScript) berfungsi NewFixedDoubleArraymencoba mengalokasikan larik dengan 75.209.227 elemen, dan ukuran maksimum yang diperbolehkan dalam konteks ini adalah 67.108.863 (0x3FFFFFF dalam hex).
Hal yang menyenangkan tentang gangguan yang saya sebabkan adalah Anda dapat mencoba membuatnya kembali dengan pemantauan yang lebih cermat. Eksperimen menunjukkan bahwa ketika diperbesar, memori tetap stabil sampai saya mencapai titik kritis, setelah itu penggunaan memori tiba-tiba melonjak dan tab macet bahkan jika saya tidak melakukan apa-apa.
Masalahnya di sini adalah saya dapat dengan mudah melihat tumpukan panggilan untuk kegagalan ini, tetapi hanya sebagian dari kode Chrome C ++. Namun, tampaknya, bug itu sendiri muncul di kode JavaScript chrome: // tracing. Saya mencoba mengujinya dengan build kenari Chrome (harian) di bawah debugger dan mendapatkan pesan aneh berikut:
==== Jejak tumpukan JS =====================================
Sayangnya, tidak ada jejak tumpukan di balik garis yang menarik ini. Setelah mengembara sedikit di belantara git , saya menemukan bahwa kemampuan untuk mengeluarkan tumpukan panggilan JS melalui OOM telah ditambahkan pada 2015 dan kemudian dihapus pada Desember 2019 .
Saya meneliti bug ini pada awal Januari 2020 (ingat masa lalu yang indah ketika semuanya tidak bersalah dan lebih mudah?), Dan itu berarti kode pelacakan tumpukan OOM telah dihapus dari pembuatan harian, tetapi masih tetap pada perakitan yang stabil ...
Oleh karena itu, langkah saya selanjutnya adalah mencoba membuat ulang bug di versi stabil Chrome. Ini memberi saya hasil berikut (saya mengeditnya sedikit untuk kejelasan):
0: ExitFrame [pc: 00007FFDCD887FBD]
1: drawGrid_ [000016011D504859] [chrome: //tracing/tracing.js: ~ 4750]
2: draw [000016011D504821] [chrome: //tracing/tracing.js: 4750]
Singkatnya, error OOM disebabkan oleh drawGrid_ , yang saya temukan (menggunakan halaman pencarian kode Chromium ) di x_axis_track.html. Setelah sedikit mengubah file ini, saya mempersempitnya menjadi memanggil updateMajorMarkData . Fungsi ini berisi loop yang memanggil fungsi majorMarkWorldPositions_.push , yang merupakan biang keladi masalah.
Perlu disebutkan di sini bahwa meskipun saya mengembangkan browser, saya tetap menjadi programmer JavaScript terburuk di dunia. Keterampilan dalam pemrograman sistem C ++ tidak memberi saya keajaiban "frontend". Meretas JavaScript untuk memahami bug ini adalah proses yang cukup menyakitkan bagi saya.
Loop (yang dapat dilihat di sini ) terlihat seperti ini:
for (let curX = firstMajorMark;
curX < viewRWorld;
curX += majorMarkDistanceWorld) {
this.majorMarkWorldPositions_.push(
Math.floor(MAJOR_MARK_ROUNDING_FACTOR * curX) /
MAJOR_MARK_ROUNDING_FACTOR);
}Saya menambahkan pernyataan keluaran debug sebelum loop dan mendapatkan data yang ditunjukkan di bawah ini. Ketika saya memperbesar gambar, angka-angka yang penting, tetapi tidak cukup untuk menyebabkan crash, terlihat seperti ini:
firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 1e-13
Lalu saya memperbesar untuk menyebabkan crash, dan saya mendapatkan angka seperti ini:
firstMajorMark: 885.0999999642371
majorMarkDistanceWorld: 5e-14
885 dibagi 5e-14 adalah 1.8e16, dan presisi angka floating point presisi ganda adalah 2 ^ 53, yaitu 9.0e15. Oleh karena itu, bug terjadi ketika majorMarkDistanceWorld (jarak antara titik kisi) sangat kecil dibandingkan dengan firstMajorMark (lokasi tanda kisi utama pertama) yang menambahkan dalam satu lingkaran ... tidak melakukan apa pun. Artinya, jika kita menambahkan angka kecil ke besar, maka ketika angka kecil "terlalu kecil", angka besar bisa (dalam pembulatan standar / waras ke terdekat) tetap sama dengan nilai yang sama.
Karenanya, loop berjalan tanpa batas, dan perintah push dijalankan hingga larik dibatasi ukurannya. Jika tidak ada batasan ukuran, perintah push akan terus berjalan hingga seluruh mesin kehabisan memori. Jadi hore, masalah terpecahkan?
Perbaikannya ternyata cukup sederhana - jangan tampilkan label kisi jika kita tidak bisa:
if (firstMajorMark / majorMarkDistanceWorld > 1e15) return;
Seperti yang sering terjadi dengan perubahan yang saya buat, perbaikan bug saya terdiri dari satu baris kode dan komentar enam baris. Saya hanya terkejut bahwa tidak ada catatan komit pentameter iambik 50 baris, notasi notasi, dan posting blog. Tunggu sebentar ...
Sayangnya, JavaScript stack frames masih belum ditampilkan pada OOM crash, karena dibutuhkan memori untuk menulis call stack, yang artinya tidak aman pada tahap ini. Saya tidak begitu mengerti bagaimana saya akan menyelidiki bug ini hari ini, ketika frame tumpukan OOM benar-benar dihapus, tetapi saya yakin saya akan menemukan cara.
Jadi, jika Anda adalah pengembang JavaScript yang mencoba menggunakan angka yang sangat besar, penulis pengujian yang mencoba menggunakan nilai bilangan bulat terbesar, atau mengimplementasikan UI dengan zoom tak terbatas, maka penting untuk diingat bahwa saat Anda mendekati batas matematika floating point, batas tersebut dapat dilanggar.
Periklanan
Server pembangunan yang epik dari Vdsina.
Kami menggunakan drive NVMe yang sangat cepat dari Intel dan tidak menghemat perangkat keras - hanya peralatan bermerek dan solusi paling modern di pasaran!
