Halo, Habr! Saya mempersembahkan kepada Anda terjemahan artikel "Pointers Are Complicated, atau: Apa yang ada dalam Byte?" kepenulisan Ralf Jung.
Musim panas ini saya sedang mengerjakan Rust penuh waktu lagi, dan saya akan lagi (antara lain) mengerjakan "model memori" untuk Rust / MIR. Namun, sebelum saya berbicara tentang ide-ide saya, saya akhirnya harus menghilangkan mitos bahwa "petunjuk itu sederhana: mereka hanya angka." Kedua bagian dari pernyataan ini salah, setidaknya dalam bahasa dengan fitur yang tidak aman, seperti Rust atau C: pointer tidak bisa disebut nomor prima atau (biasa).
Saya juga ingin membahas bagian dari model memori yang perlu ditangani sebelum kita dapat berbicara tentang bagian yang lebih kompleks: dalam bentuk apa data disimpan dalam memori? Memori terdiri dari byte, unit minimum yang dapat dialamatkan dan elemen terkecil yang dapat diakses (setidaknya pada sebagian besar platform), tetapi apa nilai byte yang mungkin? Sekali lagi, ternyata "itu hanya angka 8-bit" tidak cocok sebagai jawaban.
Saya harap setelah membaca posting ini, Anda akan setuju dengan saya mengenai kedua pernyataan tersebut.
Pointer rumit
Apa masalah dengan "pointer adalah angka reguler"? Mari kita lihat contoh berikut: (Saya menggunakan C ++ di sini, karena menulis kode yang tidak aman di C ++ lebih mudah daripada menulis di Rust, dan kode yang tidak aman hanyalah tempat di mana masalah muncul. Insecure Rust dan C memiliki semua masalah yang sama yang dan 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]; }
Mengoptimalkan pembacaan terakhir y [0] dengan pengembalian 42 selalu sangat bermanfaat. Alasan untuk optimasi ini adalah bahwa mengubah x_ptr yang menunjuk ke x tidak dapat mengubah y.
Namun, ketika berhadapan dengan bahasa tingkat rendah seperti C ++, kita dapat melanggar asumsi ini dengan menetapkan nilai yx. Karena & x [i] sama dengan x + i, kita menulis 23 di & y [0].
Tentu saja, ini tidak mencegah kompiler C ++ melakukan optimasi seperti itu. Untuk mengatasi ini, standar mengatakan bahwa kode kami memiliki UB .
Pertama, itu tidak diperbolehkan untuk melakukan operasi aritmatika pada pointer (seperti dalam kasus & x [i]), jika dalam kasus ini pointer melampaui salah satu batas array . Program kami melanggar aturan ini: x [i] melampaui x, jadi itu adalah UB. Dengan kata lain, bahkan menghitung nilai x_ptr adalah UB, jadi kami bahkan tidak sampai ke tempat di mana kami ingin menggunakan pointer ini.
(Ternyata i = yx juga UB, karena hanya pointer yang menunjuk ke alokasi memori yang sama yang boleh dikurangi . Namun, kita bisa menulis i = ((size_t) y - (size_t) x - / sizeof (int) untuk memotong ini adalah batasan.)
Tetapi kita belum selesai: aturan ini memiliki satu-satunya pengecualian yang dapat kita gunakan untuk keuntungan kita. Jika operasi aritmatika menghitung nilai pointer ke alamat tepat setelah akhir array, maka semuanya dalam urutan. (Pengecualian ini diperlukan untuk menghitung vec.end () untuk loop paling umum di C ++ 98.)
Mari kita ubah sedikit contoh:
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; auto x_ptr = x+8;
Sekarang bayangkan x dan y dialokasikan satu demi satu , dengan y memiliki alamat yang lebih besar. Kemudian x_ptr menunjuk ke awal y! Maka kondisinya benar dan tugas terjadi. Pada saat yang sama, tidak ada UB karena keluarnya pointer di luar negeri.
Tampaknya ini tidak akan memungkinkan pengoptimalan. Namun, standar C ++ memiliki kartu as lainnya untuk membantu pembuat kompiler: nyatanya, ia tidak memungkinkan kami untuk menggunakan x_ptr. Menurut apa yang dikatakan standar tentang menambahkan angka ke pointer , x_ptr menunjuk ke alamat setelah elemen terakhir dari array. Itu tidak menunjuk ke elemen tertentu dari objek lain, bahkan jika mereka memiliki alamat yang sama . (Setidaknya ini adalah interpretasi umum dari standar berdasarkan yang LLVM mengoptimalkan kode ini .)
Dan meskipun x_ptr dan & y [0] menunjuk ke alamat yang sama, ini tidak menjadikan mereka penunjuk yang sama , yaitu, mereka tidak dapat digunakan secara bergantian: & y [0] menunjuk ke elemen pertama y; x_ptr menunjuk ke alamat setelah x. Jika kita mengganti * x_ptr = 23 dengan string * & y [0] = 0, kita akan mengubah nilai program, meskipun kedua pointer diperiksa untuk kesetaraan.
Ini layak diulangi:
Hanya karena dua petunjuk menunjuk ke alamat yang sama tidak berarti bahwa mereka sama dan dapat digunakan secara bergantian.
Ya, perbedaan ini sulit dipahami. Bahkan, ini masih menyebabkan perbedaan dalam program yang dikompilasi dengan LLVM dan GCC.
Perhatikan juga bahwa aturan satu-kali bukan satu-satunya tempat di C / C ++ di mana kita dapat mengamati efek seperti itu. Contoh lain adalah pembatasan kata kunci dalam C, yang dapat digunakan untuk menyatakan bahwa pointer tidak tumpang tindih (tidak sama):
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); }
Panggilan tes () memanggil UB, karena dua akses memori di foo seharusnya tidak terjadi pada alamat yang sama. Mengganti * y dengan * x di foo, kami akan mengubah nilai program, dan tidak akan lagi memanggil UB. Sekali lagi: walaupun x dan y memiliki alamat yang sama, mereka tidak dapat digunakan secara bergantian.
Pointer jelas bukan hanya angka.
Model penunjuk sederhana
Jadi apa itu pointer? Saya tidak tahu jawaban lengkapnya. Bahkan, ini adalah area terbuka untuk penelitian.
Satu poin penting: di sini kita melihat model pointer abstrak . Tentu saja, di komputer sungguhan, pointer adalah angka. Tetapi komputer sungguhan tidak melakukan optimisasi yang dilakukan oleh kompiler C ++ modern. Jika kita menulis program-program di atas dalam assembler, maka tidak akan ada UB, tidak ada optimasi. C ++ dan Rust mengambil pendekatan yang lebih "tingkat tinggi" untuk memori dan pointer, membatasi programmer ke kompiler. Ketika perlu untuk menggambarkan secara formal apa yang bisa dan tidak bisa dilakukan oleh seorang programmer dalam bahasa-bahasa ini, model pointer sebagai angka dihancurkan, jadi kita perlu menemukan sesuatu yang lain. Ini adalah contoh lain dari menggunakan "mesin virtual" yang berbeda dari komputer nyata untuk keperluan spesifikasi - sebuah ide yang saya tulis sebelumnya .
Berikut ini adalah kalimat sederhana (pada kenyataannya, model pointer ini digunakan oleh CompCert dan pekerjaan saya oleh RustBelt , serta cara penerjemah miri mengimplementasikan pointer ): pointer adalah sepasang ID yang secara unik mengidentifikasi area memori (alokasi), dan offset relatif terhadap daerah ini. Jika Anda menulis ini di Rust:
struct Pointer { alloc_id: usize, offset: isize, }
Operasi penambahan (pengurangan) angka ke penunjuk (dari penunjuk) hanya memengaruhi offset, dan karena itu penunjuk tidak pernah dapat meninggalkan area memori. Mengurangi pointer hanya mungkin jika mereka termasuk dalam area memori yang sama (sesuai dengan C ++ ).
(Seperti yang dapat kita lihat, standar C ++ menerapkan aturan-aturan ini ke array, bukan area memori. Namun, LLVM menerapkannya di tingkat area .)
Ternyata (dan miri menunjukkan hal yang sama) bahwa model ini dapat melayani kita dengan baik. Kami selalu mengingat wilayah memori yang menjadi tempat penunjuk, sehingga kami dapat membedakan penunjuk satu-setelah dari satu wilayah memori dari penunjuk ke awal wilayah lain. Dengan demikian miri dapat menemukan bahwa contoh kedua kami (dengan & x [8]) memiliki UB.
Model kami berantakan
Dalam model kami, pointer, meskipun bukan angka, setidaknya sederhana. Namun, model ini akan mulai berantakan di depan mata kita, segera setelah Anda mengingat konversi pointer ke angka. Dalam miri, casting pointer ke angka sebenarnya tidak melakukan apa-apa, kita hanya mendapatkan variabel numerik (mis., Tipenya mengatakan itu angka) yang nilainya pointer (mis., Sepasang area memori dan offset). Namun, mengalikan angka ini dengan 2 menyebabkan kesalahan, karena sama sekali tidak jelas apa artinya "mengalikan pointer abstrak dengan 2".
Saya harus mengklarifikasi: ini bukan solusi yang baik untuk mendefinisikan semantik bahasa. Namun, ini bekerja dengan baik untuk penerjemah. Ini adalah pendekatan yang paling sederhana, dan kami memilihnya karena tidak jelas bagaimana hal itu dapat dilakukan sebaliknya (kecuali untuk tidak mendukung pengurangan seperti itu sama sekali - tetapi dengan dukungan mereka miri dapat menjalankan lebih banyak program): di mesin abstrak kami tidak ada "ruang alamat" tunggal, di mana semua area memori yang dialokasikan akan ditempatkan, dan semua pointer dipetakan ke nomor yang berbeda. Setiap area memori diidentifikasi oleh ID (tersembunyi). Sekarang kita dapat mulai menambahkan data tambahan ke model kita, seperti alamat pangkalan untuk setiap area memori, dan entah bagaimana menggunakannya untuk membawa nomor kembali ke pointer ... dan pada titik ini prosesnya menjadi sangat sangat rumit, dan, bagaimanapun, diskusi tentang ini Model bukan tujuan menulis posting. Tujuannya adalah untuk membahas perlunya model seperti itu. Jika Anda tertarik, saya sarankan Anda membaca dokumen ini , yang lebih dekat melihat gagasan di atas untuk menambahkan alamat basis.
Singkatnya, gips dari pointer dan angka satu sama lain membingungkan dan sulit untuk ditentukan secara formal, mengingat optimisasi yang dibahas di atas. Ada konflik antara pendekatan tingkat tinggi yang diperlukan untuk optimasi dan pendekatan tingkat rendah yang diperlukan untuk menggambarkan penunjuk penunjuk ke angka dan sebaliknya. Untuk sebagian besar, kita cukup mengabaikan masalah ini dalam miri dan, jika memungkinkan, cobalah untuk melakukan sebanyak mungkin menggunakan model sederhana yang bekerja dengan kita. Definisi bahasa yang lengkap seperti C ++ atau Rust, tentu saja, tidak bisa begitu sederhana, itu harus menjelaskan apa yang sebenarnya terjadi. Sejauh yang saya tahu, tidak ada solusi yang cocok, tetapi penelitian akademis mendekati kebenaran .
Itu sebabnya pointer juga tidak sederhana.
Dari pointer ke byte
Saya harap saya telah membuat argumen yang meyakinkan bahwa angka bukan satu-satunya tipe data yang perlu dipertimbangkan jika kita ingin secara formal menggambarkan bahasa tingkat rendah seperti C ++ atau bagian (tidak aman) dari Rust. Namun, ini berarti bahwa operasi sederhana seperti membaca byte dari memori tidak bisa hanya mengembalikan u8. Bayangkan kita menerapkan memcpy dengan membaca setiap byte dari sumber itu pada gilirannya menjadi beberapa variabel lokal v, dan kemudian menyimpan nilai ini di lokasi target. Tetapi bagaimana jika byte ini adalah bagian dari sebuah pointer? Jika pointer adalah sepasang ID area memori dan offset, lalu apa yang akan menjadi byte pertama? Kita perlu mengatakan apa nilai v sama dengan, jadi kita harus entah bagaimana menjawab pertanyaan ini. (Dan ini adalah masalah yang sama sekali berbeda dari masalah dengan perkalian, yang ada di bagian sebelumnya. Kami hanya berasumsi bahwa ada beberapa jenis abstrak Ponter.)
Kami tidak dapat merepresentasikan byte dari pointer sebagai nilai rentang 0..256 (catatan: selanjutnya 0 dihidupkan, 256 tidak). Secara umum, jika kita menggunakan model representasi memori yang naif, bagian "tersembunyi" tambahan dari pointer (yang membuatnya lebih dari sekadar angka) akan hilang ketika pointer ditulis ke memori dan dibaca kembali dari itu. Kami harus memperbaiki ini, dan untuk ini kami harus memperluas konsep "byte" kami untuk mewakili keadaan tambahan ini. Jadi, byte sekarang adalah nilai kisaran 0..256 ("bit mentah"), atau byte ke-n dari beberapa pointer abstrak. Jika kami harus menerapkan model memori kami di Rust, itu bisa terlihat seperti ini:
enum ByteV1 { Bits(u8), PtrFragment(Pointer, u8), }
Misalnya, PtrFragment (ptr, 0) mewakili byte pertama dari pointer ptr. Dengan demikian, memcpy dapat "memecah" pointer menjadi byte terpisah yang mewakili pointer ini dalam memori, dan menyalinnya satu per satu. Pada arsitektur 32-bit, representasi ptr penuh akan berisi 4 byte:
[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
Representasi ini mendukung semua operasi pemindahan data melalui pointer pada level byte, yang cukup untuk memcry. Operasi aritmatika atau bit tidak sepenuhnya didukung; seperti disebutkan di atas, ini akan membutuhkan representasi pointer yang lebih kompleks.
Memori tidak diinisialisasi
Namun, kami belum selesai dengan definisi "byte" kami. Untuk sepenuhnya menggambarkan perilaku program, kita perlu mempertimbangkan opsi lain: satu byte dalam memori dapat diinisialisasi . Definisi byte terakhir akan terlihat seperti ini (misalkan kita memiliki tipe Pointer untuk pointer):
enum Byte { Bits(u8), PtrFragment(Pointer, u8), Uninit, }
Kami menggunakan nilai Uninit untuk semua byte di memori yang dialokasikan di mana kami belum menulis nilai apa pun. Dimungkinkan untuk membaca memori yang tidak diinisialisasi tanpa masalah, tetapi tindakan lain dengan byte ini (misalnya, aritmatika numerik) mengarah ke UB.
Ini sangat mirip dengan aturan LLVM sehubungan dengan nilai racun khusus. Perhatikan bahwa LLVM juga memiliki nilai undef, yang digunakan untuk memori yang tidak diinisialisasi dan bekerja sedikit berbeda. Namun, mengkompilasi Uninit kami ke undef benar (undef dalam beberapa hal “lebih lemah”), dan ada saran untuk menghapus undef dari LLVM dan menggunakan racun sebagai gantinya .
Anda mungkin bertanya-tanya mengapa kami memiliki nilai Uninit khusus sama sekali. Mengapa tidak memilih sembarang b: u8 untuk setiap byte baru, dan kemudian gunakan Bit (b) sebagai nilai awal? Ini benar-benar satu opsi. Namun, pertama-tama, semua penyusun datang ke pendekatan menggunakan nilai khusus untuk memori yang tidak diinisialisasi. Tidak mengikuti pendekatan ini berarti tidak hanya menyebabkan masalah kompilasi melalui LLVM, tetapi juga meninjau semua optimisasi dan memastikan bahwa mereka bekerja dengan benar dengan model yang dimodifikasi ini. Poin kunci di sini: Anda selalu dapat dengan aman mengganti Uninit dengan nilai lain: operasi apa pun yang menerima nilai ini akan mengarah ke UB.
Misalnya, kode C ini lebih mudah dioptimalkan dengan Uninit:
int test() { int x; if (condA()) x = 1;
Dengan Uninit, kita dapat dengan mudah mengatakan bahwa x memiliki nilai Uninit atau nilai 1, dan karena menggantikan Uninit dengan 1 karya, optimasi mudah dijelaskan. Tanpa Uninit, x adalah "semacam pola bit arbitrer" atau 1, dan optimasi yang sama lebih sulit untuk dijelaskan.
(Kita dapat berargumen bahwa kita dapat menukar operasi ketika kita membuat pilihan yang tidak deterministik, tetapi kemudian kita perlu membuktikan bahwa kode yang sulit dianalisis tidak menggunakan x dengan cara apa pun. Uninit menghindari masalah ini dengan bukti yang tidak perlu.)
Akhirnya, Uninit adalah pilihan terbaik untuk penerjemah seperti miri. Penerjemah tersebut memiliki masalah dengan operasi seperti "cukup pilih salah satu dari nilai-nilai ini" (yaitu, operasi non-deterministik), karena mereka cenderung melalui semua jalur yang mungkin dari pelaksanaan program, yang berarti bahwa mereka perlu mencoba semua nilai yang mungkin. Menggunakan Uninit sebagai ganti pola bit arbitrer berarti bahwa miri dapat memberi tahu Anda setelah satu program dijalankan apakah program Anda menggunakan nilai yang tidak diinisialisasi dengan salah.
Kesimpulan
Kami melihat bahwa dalam bahasa seperti C ++ dan Rust (tidak seperti komputer nyata) pointer dapat berbeda bahkan jika mereka menunjuk ke alamat yang sama, dan bahwa byte lebih dari sekedar angka dalam kisaran 0..256. Karena itu, jika pada tahun 1978 bahasa C bisa menjadi "assembler portabel", sekarang ini adalah pernyataan yang sangat keliru.