Tree Borrows: โมเดลกฎ aliasing สำหรับโค้ด unsafe ของ Rust
(plf.inf.ethz.ch)- หากคอมไพเลอร์ Rust ต้องการใช้ การรับประกันเรื่อง pointer aliasing ในการปรับแต่งประสิทธิภาพ จำเป็นต้องนิยามให้ชัดเจนว่าโค้ด unsafe ละเมิดกฎตรงไหน
- Stacked Borrows เดิมได้เสนอเกณฑ์ดังกล่าวไว้ แต่ยังไม่รองรับแพตเทิร์นที่พบบ่อยในโค้ด unsafe Rust จริง และฟีเจอร์ล่าสุดของ borrow checker ได้เพียงพอ
- Tree Borrows เปลี่ยนโครงสร้างหลักของ Stacked Borrows จากสแต็กเป็นทรี ทำให้สามารถแสดงแพตเทิร์นที่ถูกต้องได้มากขึ้น
- จากการประเมิน Rust crate ที่ใช้งานแพร่หลายที่สุด 30,000 รายการ พบว่าปฏิเสธเทสต์เคสน้อยกว่า Stacked Borrows 54%
- การพิสูจน์ด้วย Rocq ยืนยันว่า สามารถคงการปรับแต่งประสิทธิภาพเดิมส่วนใหญ่ไว้ได้ พร้อมเปิดทางให้การปรับแต่งใหม่อย่าง read-read reordering
กฎ aliasing ที่จำเป็นใน unsafe Rust
- Rust ให้การรับประกันที่แข็งแกร่ง เช่น ความปลอดภัยของหน่วยความจำและการป้องกัน data race ด้วย ระบบชนิดข้อมูลแบบอิง ownership
- อย่างไรก็ตาม ในพื้นที่ของ โค้ด unsafe ความปลอดภัยจะไม่ได้รับการรับประกันโดยอัตโนมัติ และจำเป็นต้องมีกฎแยกต่างหากที่โปรแกรมเมอร์ต้องปฏิบัติตาม
- คอมไพเลอร์ต้องการใช้ประโยชน์จากการรับประกันของระบบชนิดข้อมูล โดยเฉพาะข้อมูลที่เกี่ยวกับ aliasing ของพอยน์เตอร์ เพื่อเพิ่มประสิทธิภาพการปรับแต่งภายในฟังก์ชัน
- โค้ด unsafe ที่เขียนผิดอาจทำให้การปรับแต่งเหล่านี้ใช้ไม่ได้ ดังนั้นเกณฑ์ที่ชัดเจนว่าโค้ดแบบใดถือว่า “badly behaved” จึงสำคัญ
- งานวิจัยเดิมอย่าง Stacked Borrows ได้นิยามเกณฑ์นี้ไว้ แต่ยังมีข้อจำกัด
- ปฏิเสธแพตเทิร์นหลายแบบที่พบบ่อยในโค้ด unsafe Rust จริง
- ไม่สะท้อนฟีเจอร์ขั้นสูงของ Rust borrow checker ที่เพิ่งถูกนำเข้ามา
แนวทางของ Tree Borrows และผลการประเมิน
- Tree Borrows ถูกนิยามโดยแทนที่สแต็ก ซึ่งเป็นโครงสร้างหลักของ Stacked Borrows ด้วย ทรี
- การเปลี่ยนโครงสร้างนี้ช่วยผ่อนคลายข้อจำกัดของโมเดลเดิม
- จากการประเมิน Rust crate ที่ใช้งานแพร่หลายที่สุด 30,000 รายการ พบว่าจำนวนเทสต์เคสที่ถูกปฏิเสธลดลง 54% เมื่อเทียบกับ Stacked Borrows
- การพิสูจน์ด้วย Rocq ยังยืนยันคุณสมบัติที่เกี่ยวข้องกับการปรับแต่งประสิทธิภาพ
- คงการปรับแต่งส่วนใหญ่ที่ Stacked Borrows อนุญาตไว้ได้
- รองรับการปรับแต่งใหม่ที่สำคัญอย่าง read-read reorderings ด้วย
- Tree Borrows ได้รับ PLDI'25 Distinguished Paper Award
- แหล่งข้อมูลที่เกี่ยวข้อง
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
แถมยังมีการนำเสนอล่าสุดจากกลุ่มของ Ralf Jung ที่พยายามระบุสเปกอย่างแม่นยำของ semantics การทำงานของ Rust ในรูปแบบที่รันได้ โดยใช้ภาษาถิ่นของ Rust: https://youtube.com/watch?v=yoeuW_dSe0o
Torvalds โต้แย้งมานานแล้วว่ากฎ strict aliasing ของ C ให้โทษมากกว่าประโยชน์ และฟังดูน่าเชื่อ ตัวอย่างอยู่ที่นี่: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... ถ้าสนใจหัวข้อนี้ เธรดเต็มก็ควรค่าแก่การอ่าน
จากประสบการณ์ที่จำกัด ยังไม่เห็นว่า Rust จะแตกต่างโดยพื้นฐาน อย่างน้อยเมื่อมี unsafe เข้ามาเกี่ยวข้องก็ยิ่งเป็นแบบนั้น
มองว่ามันมีประโยชน์ต่อคอมไพเลอร์มากกว่า และเป็นภาระต่อโปรแกรมเมอร์น้อยกว่า อีกทั้งในภาษาก็มีทางออกจริง ๆ ด้วย: ใช้ raw pointer ได้ และยังมีเครื่องมือสำหรับตรวจโค้ดด้วย
สุดท้ายแล้วก็เหมือนทุกอย่างในการออกแบบภาษา คือเป็นการประนีประนอม และใน Rust อาจเจอ sweet spot ใหม่สำหรับ optimization แบบนี้ก็ได้ ถูกหรือไม่ เวลาจะเป็นเครื่องพิสูจน์
ใน C มีอุปกรณ์ระดับระเบิดนิวเคลียร์อย่าง
restrictซึ่งจากประสบการณ์ ใน clang และ gcc ดูเหมือนจะได้ผลก็ต่อเมื่อใส่ไว้กับพารามิเตอร์ของฟังก์ชันเท่านั้น การวิเคราะห์ aliasing ตามชนิดข้อมูลโดยทั่วไปใช้ยาก และคุณก็สร้างสำเนาของชนิดint64_tได้ไม่จำกัดไม่ได้ และคงไม่อยากทำด้วย การที่ต้องบังคับใช้memcpyเมื่อต้องการ reinterpret เป็นชนิดอื่นก็น่ารำคาญในทางกลับกัน reference ของ Rust ถูกกำหนดขอบเขตอย่างละเอียดตาม lifetime, scope และ mutability และไม่ได้สนใจ “ชนิดทางกายภาพ” เองมากนัก ดังนั้นจึงสามารถ reinterpret และสลับหน่วยความจำเดียวกันระหว่าง
&mut i32/&i32กับ&mut i64/&i64ได้ ตราบใดที่ abstraction แบบ unsafe ไม่ให้ reference&mutที่ซ้อนทับกันพร้อมกัน หรือแบ่ง&mutหนึ่งตัวออกเป็น&mutหลายตัวที่ไม่ซ้อนทับกัน ก็สามารถอ่านและเขียนค่าครึ่งหนึ่งหรือหลายค่าได้ด้วยการอ่าน/เขียน Rust แบบ safe ปกติการวิเคราะห์ aliasing สำคัญมากต่อการได้ performance ที่ดีในปัจจุบัน อย่างไรก็ดี ควรจำไว้ว่าผลได้ที่มากที่สุดมาจาก heuristic ที่ง่ายที่สุด เช่น load สองครั้งที่ใช้ค่า SSA เดียวกันเป็นพอยน์เตอร์ ย่อม alias กันแน่นอน
ในมุมของ LLVM นั้น BasicAA ทำหน้าที่แบบนั้น เป็นชุด heuristic ง่าย ๆ ที่ใกล้เคียงกับ “ถ้าตามจุดจัดสรรของ object ได้ ก็แก้ alias query ได้แบบแน่ชัด ไม่อย่างนั้นก็ไม่รู้”
คำถามจริง ๆ คือคุณค่าของการวิเคราะห์ aliasing ที่เกินกว่าการตรวจพื้นฐานและชัดเจน เมื่อ alias query เข้าสู่ขั้นที่ไม่สามารถแก้ได้แบบง่าย ๆ แล้ว สิ่งที่ทำได้จากผลลัพธ์นั้นโดยมากก็ลดลงมาก และแทบเหลือแค่การหาความเสี่ยงในการย้ายโค้ด ประโยชน์จึงเล็กกว่ามาก
หนึ่งในการทดลองที่อยากทำคือวัด speedup รวมที่การวิเคราะห์ aliasing ที่สมบูรณ์แบบตามทฤษฎีจะให้ได้ เดาว่าแม้แต่โค้ดที่ไม่ใช่ HPC อย่างเคอร์เนล Linux ก็น่าจะอยู่ราว 20%
[1] ตรงนี้ไม่รวม optimization ระดับวีรบุรุษอย่างการแปลง layout ของข้อมูล ซึ่งจะไม่ลองทำหากไม่มีการวิเคราะห์ aliasing คุณภาพสูง ในทางปฏิบัติเรารู้อยู่แล้วว่าไม่มีการวิเคราะห์ aliasing แบบนั้น จึงคงไม่ลองทำ optimization เหล่านั้น และมองว่าไม่ควรนับรวมใน speedup ที่คาดไว้
aliasing ของ C อิงตามชนิดข้อมูลเท่านั้น จึงมีอีกชื่อว่า type-based alias analysis หรือ TBAA
เจอข้ออ้างว่า
noaliasช่วยเพิ่ม performance ตามเวลารันได้ประมาณ 5% แต่ชัดเจนว่าเอกสารนั้นเก่ามากhttps://github.com/rust-lang/rust/issues/54878#issuecomment-...
https://news.ycombinator.com/item?id=22281205
https://news.ycombinator.com/item?id=17715399
คำอธิบายดูเหมือนจะบอกว่า ถ้าสร้าง
*mut i32จาก&mutแล้วใช้*x = 10แทนwrite(x)ก็จะไม่ใช้ two-phase borrow แบบ implicit ดังนั้นคอมไพเลอร์ควรปฏิเสธ แต่จริง ๆ แล้วผ่าน*x = 10;จะรายงานข้อผิดพลาด แต่เวอร์ชันwrite(x);จะไม่เป็นข้อผิดพลาดอยู่ในรูป “Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location”
ไม่มีเหตุผลที่ตัว rustc เองจะปฏิเสธทั้งสองกรณี เพราะ
yเป็น*mutและจากมุมมองของระบบชนิดข้อมูลในเวลาคอมไพล์ มันไม่มีความสัมพันธ์ด้านการยืมหรืออายุการใช้งานกับ&mutที่เป็นxตัวตรวจสอบการยืมปัจจุบันใช้การวิเคราะห์ที่จำกัดกว่า จึงตรวจไม่พบความขัดแย้งเฉพาะกรณีนี้ระหว่างพอยน์เตอร์ดิบกับ mutable reference
จากประสบการณ์จริง [1] [2] ก็อนุญาตให้ใช้โค้ดที่ใน Stacked Borrows ถือว่าผิดกฎ แต่สมเหตุสมผลได้
[1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... คอลัมน์ Miri
[2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
เคยย้ายจากตัวตรวจสอบการยืมแบบอิงขอบเขตไปเป็นตัวตรวจสอบการยืมแบบ อายุการใช้งานที่ไม่เป็นไปตามศัพท์ (non-lexical lifetimes) และยังมีการใช้งาน Polonius รุ่นทดลองถัดไปเป็นตัวเลือกด้วย เพียงแต่เมื่อการใช้งานใหม่พร้อมสำหรับโปรดักชันแล้ว การใช้งานเก่าก็จะถูกทิ้งไป เพราะไม่มีเหตุผลให้เลือกใช้
การตรวจสอบการยืมนั้นรวดเร็ว และการใช้งานใหม่ยอมรับโปรแกรมที่ถูกต้องได้มากขึ้นอย่างเคร่งครัด
นอกจากนี้ยังมีชนิด
RcและRefCellที่ทำให้ได้ความยืดหยุ่นมากขึ้นโดยแลกกับต้นทุนการตรวจสอบตอนรันไทม์ทั้งหมดมีต้นทุนและความสามารถต่างกันในด้านการนำไปใช้ ประสิทธิภาพ และประสบการณ์ของนักพัฒนา
และสิ่งที่ภาษาส่วนใหญ่ที่ไม่ใช่ Rust มุ่งไปจริง ๆ คือผลิตภาพจากการจัดการทรัพยากรอัตโนมัติ กล่าวคือใช้การจัดการทรัพยากรอัตโนมัติไม่ว่าจะด้วยวิธีใด แล้วผสานหนึ่งในระบบชนิดข้างต้นเฉพาะกับเส้นทางที่สำคัญต่อประสิทธิภาพเท่านั้น
ในบริบทนี้ “Rust” อาจมองได้ว่าเป็นเพียง “invariant ที่คนทั่วไปมักต้องการ” และ “ชุด optimization ที่สมมติ invariant ทั่วไปเหล่านั้น—ไม่มากไปกว่านั้นและไม่น้อยไปกว่านั้น”
เวลาคอมไพล์ส่วนใหญ่ถูกใช้ไปกับการตีความ trait, monomorphization, LLVM optimization passes และการลิงก์
อาจเป็นคำถามโง่ ๆ ก็ได้ แต่สงสัยว่าทำไมไม่รันหลาย implementation บนเธรดคู่ขนาน แล้วให้ตัวที่ให้ผลบวกก่อนเป็นฝ่ายชนะ
การใช้พอยน์เตอร์เพื่อทำให้มี mutable references หลายตัวไปยังตัวแปรเดียวกันในเวลาเดียวกันเป็น undefined behavior ถ้าไม่ได้เข้าใจเจตนาของบทความผิด ก็ดูเหมือนจะเป็นอย่างนั้น
โค้ดข้างต้นคอมไพเลอร์ Rust ยอมรับ แต่ละเมิดกฎ คำถามคือมันละเมิดกฎอะไร
โดยเนื้อแท้ สิ่งที่ตัวตรวจสอบการยืมยอมรับคือสิ่งที่ถูกกฎหมาย ส่วน unsafe สามารถแสดงสิ่งที่ผิดกฎหมายหรือเป็น undefined behavior ได้ และยังมีชุดกฎที่กว้างกว่าสิ่งที่ตัวตรวจสอบการยืมตรวจได้ แต่ยังคงถูกกฎหมายและมีพฤติกรรมที่กำหนดชัดเจน
เป้าหมายของงานวิจัยนี้คือการระบุชุดกฎนั้นอย่างแม่นยำ ภาพรวมใหญ่ ๆ ใกล้เคียงกับ “พอยน์เตอร์ที่เขียนได้ต้องไม่มี alias” แต่รายละเอียดอย่าง interior pointers, iterator invalidation และคำถามว่าปัญหาอยู่ที่การสร้างพอยน์เตอร์เสีย ๆ หรือการใช้งานพอยน์เตอร์นั้น เป็นเรื่องยากมาก
บทความ Stacked Borrows ก่อนหน้านั้นเรียบง่ายกว่าแต่ก็จำกัดกว่า ทำให้ unsafe code ในโลกจริงมักไม่ผ่านกฎ Tree Borrows กว้างกว่าและอนุญาตโค้ดได้มากกว่า ขณะเดียวกันก็ยังพิสูจน์ได้ว่าปลอดภัย
Tree Borrows เสนอคำจำกัดความแบบนั้นพอดี
ที่นี่คำว่า “โค้ดสามารถทำแบบนี้ได้” หมายถึง “สามารถเขียนโค้ดนี้ คอมไพล์ และรันได้ และถ้าไม่มีสิ่งอย่าง Tree Borrows ก็ไม่มีหลักฐานให้ยืนยันว่าโค้ดนี้มีปัญหา”
ในเมื่อยอมรับแล้วว่าต้องบอกว่าโค้ดแบบนี้เป็น undefined behavior กล่าวคือจำเป็นต้องมีสิ่งอย่าง Tree Borrows ส่วนนี้ของบทความจึงเป็นการโต้แย้งว่าทำไมจึงต้องมีสิ่งนั้น
https://play.rust-lang.org/?version=stable&mode=debug&editio...
เนื้อหาคือเห็นได้ชัดว่านักพัฒนาคอมไพเลอร์ Rust ต้องการรองรับ aliasing optimization ดังนั้นจึงต้องมีวิธี “ตัด” ตัวอย่างโต้แย้งแบบข้างต้นออกจากขอบเขตที่พิจารณา
unsafe มีไว้สำหรับกรณีที่พิสูจน์ความถูกต้องของโค้ดด้วยการวิเคราะห์อายุการใช้งานของ Rust ได้ยาก แต่ก็อาจถูกนำไปใช้ในทางที่เกินกว่านั้นมากได้