Tree Borrows: Model Aturan Aliasing untuk Kode `unsafe` Rust

• Agar kompiler Rust dapat memanfaatkan jaminan aliasing pointer untuk optimasi, perlu ada definisi yang jelas tentang di mana kode unsafe melanggar aturan
• Stacked Borrows yang ada sebelumnya memberikan tolok ukur tersebut, tetapi belum cukup mengakomodasi pola umum dalam kode unsafe Rust di dunia nyata maupun fitur terbaru borrow checker
• Tree Borrows mengubah struktur inti Stacked Borrows dari stack menjadi tree sehingga dapat merepresentasikan lebih banyak pola yang valid
• Dalam evaluasi terhadap 30.000 crate Rust yang paling banyak digunakan, jumlah test case yang ditolak 54% lebih sedikit dibandingkan Stacked Borrows
• Pembuktian dengan Rocq mengonfirmasi bahwa sebagian besar optimasi yang ada tetap dipertahankan, sambil memungkinkan optimasi baru seperti read-read reordering

---

Aturan aliasing yang dibutuhkan di unsafe Rust

• Rust memberikan jaminan kuat seperti keamanan memori dan pencegahan data race melalui sistem tipe berbasis ownership
• Namun, di area kode unsafe, keamanan tidak dijamin secara otomatis, sehingga diperlukan aturan terpisah yang harus dipatuhi programmer
• Kompiler berupaya memperkuat optimasi di dalam fungsi dengan memanfaatkan jaminan dari sistem tipe, khususnya informasi terkait aliasing pointer
• Kode unsafe yang ditulis keliru dapat merusak optimasi ini, sehingga penting untuk memiliki kriteria yang jelas tentang kode mana yang dianggap “badly behaved”
• Riset sebelumnya, Stacked Borrows, mendefinisikan kriteria ini tetapi memiliki keterbatasan
  • Menolak berbagai pola yang umum ditemukan dalam kode unsafe Rust nyata
  • Tidak mencerminkan fitur lanjutan borrow checker Rust yang baru diperkenalkan

Pendekatan Tree Borrows dan hasil evaluasinya

• Tree Borrows didefinisikan dengan mengganti stack, yang merupakan struktur pusat Stacked Borrows, menjadi tree
• Perubahan struktur ini melonggarkan batasan model sebelumnya
  • Dalam evaluasi terhadap 30.000 crate Rust yang paling banyak digunakan, jumlah test case yang ditolak berkurang 54% dibandingkan Stacked Borrows
• Pembuktian dengan Rocq juga memverifikasi sifat-sifat terkait optimasi
  • Mempertahankan sebagian besar optimasi yang diizinkan oleh Stacked Borrows
  • Juga memungkinkan optimasi baru yang penting, yaitu read-read reorderings
• Tree Borrows menerima PLDI'25 Distinguished Paper Award
• Materi terkait
  • Full paper
  • Conference talk
  • Artifact
  • Source code

[GN⁺]

Komentar Hacker News

• Tulisan terbaru Ralf Jung memberi konteks tambahan: https://www.ralfj.de/blog/2025/07/07/tree-borrows-paper.html
  Sebagai bonus, ada juga presentasi terbaru dari grup Ralf Jung yang mencoba menspesifikasikan secara presisi semantik eksekusi Rust dalam bentuk yang dapat dijalankan, menggunakan dialek Rust: https://youtube.com/watch?v=yoeuW_dSe0o
• Saya meragukan seberapa benar pernyataan bahwa “compiler ingin memanfaatkan jaminan type system terkait aliasing pointer untuk membuka optimisasi intrafungsi yang kuat”
  Torvalds sudah lama berpendapat bahwa strict aliasing rules di C lebih banyak mudaratnya daripada manfaatnya, dan itu terdengar meyakinkan. Contohnya di sini: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... Kalau tertarik pada topik ini, seluruh thread-nya juga layak dibaca
  Dari pengalaman saya yang terbatas, Rust tampaknya tidak berbeda secara mendasar. Setidaknya makin begitu jika unsafe ikut terlibat
  • Saya setuju bahwa strict aliasing rules C buruk, tetapi aturan yang diusulkan untuk Rust sangat berbeda
    Menurut saya ini lebih berguna bagi compiler dan tidak terlalu membebani programmer. Selain itu, di dalam bahasanya benar-benar ada jalan keluar: gunakan raw pointer. Dan ada juga alat untuk memeriksa kode
    Pada akhirnya, seperti semua hal dalam desain bahasa, ini adalah kompromi, dan menurut saya Rust mungkin telah menemukan sweet spot baru untuk optimisasi semacam ini. Waktu yang akan membuktikan apakah itu benar
  • Aturan aliasing Rust cukup berbeda dari C
    C punya perangkat seperti bom nuklir bernama restrict, yang dari pengalaman saya hanya benar-benar berdampak di clang dan gcc ketika ditempelkan pada argumen fungsi. Type-based alias analysis umumnya sulit digunakan, dan Anda tidak bisa membuat salinan tipe int64_t tanpa batas, juga kemungkinan tidak ingin melakukannya. Keharusan memakai memcpy untuk menafsirkan ulang sebagai tipe lain juga menyebalkan
    Sebaliknya, referensi Rust memiliki batasan lifetime, scope, dan mutability yang terperinci, dan tidak terlalu peduli pada tipe “fisik” itu sendiri. Jadi, dimungkinkan juga untuk menafsirkan ulang dan beralih pada memori yang sama sebagai &mut i32/&i32 dan &mut i64/&i64. Selama abstraksi unsafe tidak memberikan referensi &mut yang tumpang tindih secara bersamaan, atau selama satu &mut dibagi menjadi beberapa &mut yang tidak tumpang tindih, Anda bisa membaca dan menulis setengah nilai atau beberapa nilai dengan operasi baca-tulis Rust aman yang biasa
  • Apa yang dikatakan Linus tentang compiler perlu disaring sampai batas tertentu. Ia menulis kernel sistem operasi, bukan orang yang menulis compiler, dan keduanya merupakan ranah yang cukup berbeda
    Alias analysis sangat penting untuk mendapatkan performa yang baik saat ini. Namun perlu diingat juga bahwa manfaat terbesar datang dari heuristic yang paling sederhana. Misalnya, dua load yang menggunakan nilai SSA yang sama sebagai pointer pasti saling alias
    Dari sudut pandang LLVM, BasicAA menjalankan peran itu. Ini adalah kumpulan heuristic sederhana yang kurang lebih berbunyi “jika titik alokasi objek bisa dilacak, selesaikan alias query secara pasti; jika tidak, tidak tahu”
    Pertanyaan sebenarnya adalah nilai alias analysis yang melampaui pemeriksaan dasar dan jelas. Ketika alias query tidak lagi bisa diselesaikan secara trivial, hal yang bisa dilakukan dari hasilnya pun biasanya sangat berkurang, dan hampir hanya sebatas menemukan risiko code motion. Manfaatnya jauh lebih kecil
    Salah satu eksperimen yang ingin saya coba adalah mengukur total peningkatan kecepatan yang akan diberikan oleh alias analysis yang secara teoretis sempurna. Dugaan saya, bahkan pada kode non-HPC seperti kernel Linux pun angkanya sekitar 20%
    [1] Ini tidak mencakup optimisasi heroik seperti transformasi tata letak data yang tidak akan dicoba tanpa alias analysis berkualitas tinggi. Karena kita sudah tahu bahwa alias analysis seperti itu pada praktiknya tidak ada, optimisasi semacam itu juga tidak akan dicoba, dan menurut saya tidak layak dimasukkan ke estimasi peningkatan kecepatan
  • Strict aliasing C dan aliasing Rust sama-sama menangani aliasing, tetapi keduanya berbeda. Rust cukup eksplisit tidak mengadopsi pendekatan C
    Aliasing C hanya berbasis tipe, sehingga nama lainnya adalah type-based alias analysis atau TBAA
  • Saya ingin melihat analisis yang lebih menyeluruh, tetapi aturan praktis sederhana adalah menghapus semua bagian compiler yang meneruskan informasi aliasing ke LLVM, lalu melihat bagaimana performanya
    Saya menemukan klaim bahwa noalias berkontribusi pada peningkatan performa sekitar 5% berdasarkan waktu eksekusi, tetapi jelas datanya sudah sangat lama
    https://github.com/rust-lang/rust/issues/54878#issuecomment-...
• Stacked Borrows yang disebutkan juga pernah dibahas dalam thread pada 2020 dan 2018
  https://news.ycombinator.com/item?id=22281205
  https://news.ycombinator.com/item?id=17715399
• Presentasi PLDI juga bisa ditonton: https://www.youtube.com/watch?v=CJi_Fcs4bak
• Saya mencoba sendiri klaim dalam contoh 4 makalah bahwa kode Rust tertentu ditolak, tetapi pada versi compiler stabil tampaknya tidak demikian
  Penjelasannya terlihat seperti: jika membuat *mut i32 dari &mut, lalu melakukan *x = 10 alih-alih write(x), maka compiler semestinya menolaknya karena tidak memakai implicit two-phase borrow, tetapi pada praktiknya lolos
  • Stacked Borrows adalah model runtime Miri. Jika dijalankan di Miri, versi *x = 10; melaporkan error, sedangkan versi write(x); tidak
    Error-nya berbentuk “Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location”

rustc sendiri tidak punya alasan untuk menolak salah satu dari keduanya. y adalah *mut, dan dari sudut pandang sistem tipe pada waktu kompilasi, ia tidak memiliki hubungan peminjaman atau lifetime dengan &mut yaitu x

• Makalah ini menjelaskan perilaku dalam model Tree Borrows yang diusulkan, bukan implementasi borrow checker saat ini
  Borrow checker saat ini menggunakan analisis yang lebih restriktif, sehingga tidak dapat mendeteksi konflik spesifik ini antara pointer mentah dan referensi mutable
• Ini karya yang hebat. Saya ingat beberapa tahun lalu membaca spesifikasi Tree Borrows di situs web Nevin dan sangat terkesan dengan cara elegannya menyelesaikan masalah yang cukup rumit
  Berdasarkan pengalaman nyata [1] [2], ia juga mengizinkan kode yang masuk akal tetapi ilegal di Stacked Borrows
  [1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... kolom Miri
  [2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
• Implementasi Miri bagi yang tertarik ada di sini: https://github.com/rust-lang/miri/tree/master/src/borrow_tra...
• Saya penasaran apakah Rust atau bahasa pemrograman masa depan akan berkembang dengan mengizinkan beberapa implementasi borrow checker dengan karakteristik berbeda seperti kecepatan kompilasi, kecepatan eksekusi, dan fleksibilitas algoritme, lalu membiarkan proyek memilihnya
  • Rust sudah mendukung pergantian implementasi borrow checker
    Rust telah berpindah dari borrow checker berbasis scope ke borrow checker dengan lifetime non-leksikal, dan implementasi eksperimental Polonius berikutnya juga tersedia sebagai opsi. Namun ketika implementasi baru siap untuk produksi, implementasi lama ditinggalkan. Sebab tidak ada alasan untuk memilihnya
    Pemeriksaan peminjaman itu cepat, dan implementasi baru menerima secara ketat lebih banyak program yang benar
    Selain itu ada tipe Rc dan RefCell, yang memungkinkan fleksibilitas lebih besar dengan membayar biaya pemeriksaan runtime
  • Sudah ada beberapa pendekatan. Misalnya tipe affine yang digunakan Rust, tipe linear, efek, tipe dependen, dan pembuktian formal
    Semuanya memiliki biaya dan kemampuan berbeda dalam hal implementasi, performa, dan pengalaman developer
    Dan yang sebenarnya dituju oleh kebanyakan bahasa selain Rust adalah produktivitas dari manajemen sumber daya otomatis. Apa pun metodenya, mereka memakai manajemen sumber daya otomatis, lalu menggabungkannya dengan salah satu sistem tipe di atas hanya pada jalur yang kritis terhadap performa
  • Yang sebenarnya diinginkan mungkin adalah logika pemisahan sebagai fondasinya. Strukturnya adalah menspesifikasikan prasyarat fungsi secara presisi, membuktikan kondisi-kondisi antara di dalam fungsi, lalu membiarkan optimizer menerima “lemma” itu dan mengoptimalkan sesuka hati hingga batas yang diizinkan oleh invariant yang dinyatakan
    Dalam konteks ini, “Rust” bisa dilihat tidak lebih dari “invariant yang biasanya diinginkan orang” dan “sekumpulan optimisasi yang mengasumsikan invariant umum itu, tidak lebih dan tidak kurang”
  • Borrow checker Rust memiliki biaya waktu kompilasi yang cukup kecil dan sama sekali tidak memengaruhi code generation
    Sebagian besar waktu kompilasi dipakai untuk resolusi trait, monomorfisasi, pass optimisasi LLVM, dan linking
  • Sejauh yang saya pahami, bukankah borrow checker hanya memiliki false negative dan tidak memiliki false positive?
    Mungkin ini pertanyaan bodoh, tetapi saya penasaran apakah tidak bisa menjalankan beberapa implementasi di thread paralel dan membiarkan yang pertama memberikan hasil positif menjadi pemenangnya
• Makalah itu mengatakan kode unsafe dapat membuat beberapa referensi mutable terhadap variabel yang sama hidup berdampingan sebagai pointer, tetapi bukankah itu perilaku tak terdefinisi?
  Menggunakan pointer untuk membuat beberapa referensi mutable terhadap variabel yang sama ada secara bersamaan adalah perilaku tak terdefinisi. Kecuali saya salah memahami maksud makalahnya, begitulah kelihatannya
  • Inti dari pekerjaan ini adalah menetapkan batas yang tepat dari perilaku tak terdefinisi
    Kode di atas diterima oleh compiler Rust, tetapi melanggar aturan. Pertanyaannya adalah aturan mana yang dilanggar
    Pada dasarnya, apa yang diterima borrow checker itu legal, unsafe dapat mengekspresikan hal yang ilegal atau perilaku tak terdefinisi, dan ada himpunan aturan yang lebih luas daripada yang dapat diperiksa borrow checker tetapi tetap legal dan merupakan perilaku terdefinisi
    Tujuan riset ini adalah menspesifikasikan himpunan aturan itu secara presisi. Garis besarnya kurang lebih “pointer yang dapat ditulis tidak boleh beralias”, tetapi detail seperti pointer internal, invalidasi iterator, dan apakah yang bermasalah itu membuat pointer buruk atau menggunakannya, sangat sulit
    Makalah Stacked Borrows sebelumnya lebih sederhana tetapi lebih restriktif, sehingga kode unsafe di dunia nyata sering gagal melewati aturannya. Tree Borrows lebih luas dan mengizinkan lebih banyak kode, sambil tetap aman secara dapat dibuktikan
  • Benar, tetapi masalahnya adalah aturan persis mana yang dilanggar. Apa definisi tepat yang mengatakan bahwa itu adalah perilaku tak terdefinisi?
    Tree Borrows justru mengusulkan definisi semacam itu
    Di sini, “kode dapat melakukan hal seperti ini” berarti “Anda dapat menulis, mengompilasi, dan menjalankan kode ini, dan tanpa sesuatu seperti Tree Borrows, tidak ada dasar untuk menyatakan bahwa kode ini bermasalah”
    Anda pada dasarnya sudah menerima bahwa kode seperti ini harus dikatakan sebagai perilaku tak terdefinisi, yaitu bahwa sesuatu seperti Tree Borrows diperlukan. Bagian makalah ini adalah bagian yang berargumen mengapa hal semacam itu diperlukan
  • Tampaknya ada salah paham soal kata “dapat melakukan” di sini. Dalam kode unsafe, Anda memang benar-benar bisa melakukannya. Dan memang, itu adalah perilaku tak terdefinisi
    https://play.rust-lang.org/?version=stable&mode=debug&editio...
  • Maksudnya paling jelas terlihat dari awal paragraf berikutnya
    Isinya mengatakan bahwa karena para pengembang compiler Rust jelas ingin mendukung optimisasi aliasing, diperlukan cara untuk “mengecualikan” contoh kontra seperti di atas dari pertimbangan
  • Saya rasa memang itulah intinya. Terlalu mudah melanggar batasan seperti tidak mengizinkan beberapa referensi mutable

unsafe dimaksudkan untuk kasus ketika sulit membuktikan validitas kode melalui analisis lifetime Rust, tetapi bisa disalahgunakan untuk melakukan jauh lebih banyak hal daripada itu

• Saya baru tahu bahwa salah satu penulisnya, Neven Villani, adalah putra Cédric Villani, peraih Fields Medal tahun 2010. Pepatah “buah jatuh tak jauh dari pohonnya” benar-benar pas