Tree Borrows

• Rust भाषा में unsafe code optimization की सीमाओं को पार करने के लिए एक नए memory model, Tree Borrows, का प्रस्ताव किया गया है
• मौजूदा Stacked Borrows तरीका, जो practical Rust code में अक्सर इस्तेमाल होने वाले कई patterns को अनुमति नहीं दे पाता था, उसे Tree Borrows tree structure के जरिए हल करता है, और अधिक वास्तविक तथा लचीले नियम प्रदान करता है
• Tree Borrows, Stacked Borrows की तुलना में 54% अधिक real-world code test cases पास करता है
• यह Rust memory safety और optimization possibilities (खासकर read-read reordering आदि) को अधिकांशतः बनाए रखते हुए, आधुनिक Rust borrow checker की advanced features को भी प्रतिबिंबित करता है
• tree-based state machine model को अपनाकर, यह Rust optimization और safety verification research में एक महत्वपूर्ण मील का पत्थर प्रस्तुत करता है

---

Rust की ownership system और unsafe code की सीमाएँ

• Rust, ownership-based type system के माध्यम से memory safety और data race prevention जैसी मजबूत guarantees प्रदान करता है
• लेकिन Rust में unsafe escape hatch मौजूद है, और इस स्थिति में safety verification की ज़िम्मेदारी compiler के बजाय developer पर आ जाती है
• compiler, मजबूत optimization के लिए pointer alias नियमों का उपयोग करना चाहता है, लेकिन गलत unsafe code की वजह से ऐसे optimization निष्प्रभावी हो सकते हैं

Stacked Borrows और उसकी सीमाएँ

• अब तक Stacked Borrows नामक मॉडल unsafe code के 'गलत व्यवहार' को परिभाषित करता था और optimization के लिए मानदंड देता था
• लेकिन यह तरीका वास्तविक Rust code में आम कई unsafe patterns को अनुमति नहीं देता, और Rust के हाल में जोड़े गए borrow checker features को भी प्रतिबिंबित नहीं कर पाता

Tree Borrows का आगमन

• Tree Borrows, Stacked (stack) structure के बजाय tree structure के जरिए memory permissions को track करने वाला नया मॉडल है
• इसके कारण अधिक practical Rust code patterns को सुरक्षित रूप से अनुमति मिलती है, और borrow rules की flexibility तथा real-world applicability काफ़ी बढ़ती है
• 30,000 लोकप्रिय Rust crates के मूल्यांकन में यह Stacked Borrows से 54% अधिक test cases पास करता है

Tree Borrows की विशेषताएँ और फायदे

• यह मौजूदा Stacked Borrows के मुख्य optimization (जैसे read-read reorderings) को अधिकांशतः बनाए रखता है
• साथ ही, आधुनिक Rust borrow checker की advanced features (जैसे non-standard borrow patterns, complex pointer manipulation आदि) को भी शामिल कर सकता है
• tree-based state machine model को अपनाकर, यह safety और optimization potential के बीच संतुलन स्थापित करता है

निष्कर्ष और महत्व

• Tree Borrows, Rust compiler के unsafe code handling और optimization research के लिए एक नया मानक प्रस्तुत करता है
• इसे practical Rust code और आधुनिक borrow checker policies दोनों को समेटने वाले यथार्थवादी और मजबूत memory model के रूप में देखा जाता है
• संबंधित paper, artifact और source code सार्वजनिक किए गए हैं, और इनसे Rust compiler तथा verification research community पर बड़ा प्रभाव पड़ने की उम्मीद है

[GN⁺]

Hacker News राय

• हाल की Ralf Jung की ब्लॉग पोस्ट में और ज़्यादा संदर्भ दिया गया है लिंक
  बोनस: Rust की execution semantics को Rust की ही एक dialect में स्पष्ट रूप से specify करने की कोशिश करने वाले रिसर्च ग्रुप की हाल की प्रस्तुति भी सुझाता हूँ YouTube

• यह दावा किया जाता है कि compiler के नज़रिए से pointer aliasing से जुड़े type system के मजबूत guarantees का उपयोग करके बहुत शक्तिशाली optimizations किए जा सकते हैं, लेकिन असल में यह कितना असरदार है, यह जानने की जिज्ञासा है
  Linus Torvalds लंबे समय से कहते आए हैं कि C का strict aliasing नियम खास उपयोगी नहीं है और उल्टा समस्याएँ पैदा करता है
  उनकी example पोस्ट भी दिलचस्प है
  सोचता हूँ कि क्या Rust मूल रूप से C से बुनियादी तौर पर अलग है; मेरे निजी अनुभव में, खासकर जब unsafe जुड़ता है, तो बहुत फर्क महसूस नहीं होता

  • मुझे लगता है कि C का strict aliasing नियम सच में काफी खराब है
    Rust में प्रस्तावित नियम उससे बहुत अलग हैं, compiler के नज़रिए से ज़्यादा उपयोगी हैं, और programmer के लिए भी कम बोझिल लगते हैं
    raw pointer का इस्तेमाल करके in-language opt-out किया जा सकता है, और code को check करने वाले tools भी हैं
    आखिरकार हर language design की तरह यह भी एक compromise है
    लगता है Rust ने optimization के इस क्षेत्र में एक नया balance खोजा है, और यह फैसला कितना सही है, यह समय बताएगा

  • Rust के aliasing नियम C से काफी अलग हैं
    C में restrict keyword का मतलब लगभग सिर्फ function arguments पर ही होता है, और type-based aliasing वास्तव में या तो कम इस्तेमाल होता है या इस्तेमाल करने में असुविधाजनक है
    Rust में lifetimes, mutability को बारीकी से व्यक्त किया जा सकता है, और type से स्वतंत्र कई तरीकों से memory को सुरक्षित ढंग से handle किया जा सकता है
    यह बड़ी बात है कि overlapping &mut references नहीं बनने चाहिए, लेकिन उसे कई non-overlapping &mut में बाँटकर इस्तेमाल किया जा सकता है

  • यह वास्तव में performance को कितना प्रभावित करता है, इस पर और व्यापक analysis देखना चाहूँगा
    यदि compiler से LLVM को aliasing information देने वाला हिस्सा पूरी तरह हटा दिया जाए और फिर performance compare की जाए, तो बात तुरंत साफ हो जाएगी
    यह दावा भी है कि 'noalias' annotation runtime में लगभग 5% performance सुधार देती है; इस बारे में एक comment है (हालाँकि data पुराना है)

  • compiler के बारे में Linus जो कहते हैं, उसे थोड़ा सावधानी से लेना चाहिए
    OS kernel और compiler पूरी तरह अलग क्षेत्र हैं
    आजकल alias analysis वास्तव में बड़े performance gains की कुंजी है
    सबसे बड़ा असर साधारण heuristics से आता है, और जटिल alias queries अपने आप में बहुत कम उपयोगी होती हैं
    सैद्धांतिक रूप से perfect alias analysis performance को कितना बढ़ा सकती है, यह प्रयोग करके देखना दिलचस्प होगा, लेकिन सामान्य code में भी शायद लगभग 20% की सीमा होगी
    बेशक बहुत advanced optimizations (जैसे data layout transforms) ऐसी भी हैं जिन्हें alias analysis के बिना आज़माने की कोशिश भी नहीं की जाती

  • C का strict aliasing और Rust का aliasing अवधारणात्मक रूप से अलग हैं
    C में type-based analysis (TBAA) केंद्रीय है, और Rust ने इसे जानबूझकर नहीं अपनाया

• Stacked Borrows पर पुराने threads 2020 और 2018 में भी आए थे
  2020 thread
  2018 thread

• कुछ साल पहले मैंने Nevin की website पर Tree Borrows specification पढ़ी थी, और यह देखकर प्रभावित हुआ था कि वह जटिल समस्याओं को भी कितनी सुरुचिपूर्ण तरह से हल करती है
  असल अनुभव में Tree Borrows ऐसा वाजिब code संभव बनाता है जो Stacked Borrows में संभव नहीं था
  Rust standard library का यह example code भी देखने लायक है

• सोचता हूँ कि क्या Rust या अगली पीढ़ी की PL इस दिशा में विकसित हो सकती है कि अलग-अलग borrow checker implementations में से चुनाव किया जा सके, जिनकी विशेषताएँ और लक्ष्य अलग हों, जैसे compile speed, runtime speed, algorithmic flexibility वगैरह

  • Rust पहले से ही borrow checker implementation बदलने का समर्थन करता है
    यह scope-based से non-lexical में बदल चुका है, और Polonius नाम का एक experimental implementation भी option के रूप में मौजूद है
    जब नया implementation तैयार हो जाता है, तो पुराने version को ज़बरदस्ती बनाए रखने की ज़रूरत नहीं रहती
    Rc, RefCell जैसी चीज़ों के साथ runtime checks के जरिए इसे ज़्यादा flexible तरीके से भी इस्तेमाल किया जा सकता है

  • affine type (जिसका Rust उपयोग करता है), linear type, effect systems, dependent types, formal proofs जैसे कई तरीके पहले से मौजूद हैं
    हर तरीके की अपनी implementation cost, performance और developer experience जैसी विशेषताएँ हैं
    Rust के अलावा भी यह रुझान है कि resource auto-management को मजबूत type systems के साथ जोड़ा जाए और उसे practical productivity के साथ हासिल किया जाए

  • वास्तव में ज़रूरत separation logic की है, जिससे function की preconditions को बारीकी से specify किया जा सके और बीच के conditions के proofs भी किए जा सकें
    Rust का approach उन सामान्य invariants को systematize करता है जिन्हें लोग वास्तव में चाहते हैं, और उसी के आधार पर मजबूत optimization guarantees देता है

  • जिज्ञासा है कि क्या borrow checker का नतीजा ऐसा होता है कि उसमें केवल false negatives हों और false positives न हों
    अगर ऐसा है, तो क्या कई implementations को threads में parallel चलाकर जो जल्दी result दे, उसका उपयोग करना संभव हो सकता है?

  • अगर कई borrow checker implementations को एक साथ अनुमति दी जाए, तो ecosystem के बिखरने की आशंका रहती है, इसलिए यह वांछनीय नहीं लगता

• मैंने paper में दिए Rust code को सचमुच test किया, और पुष्टि की कि इसे latest stable compiler reject नहीं करता
  उदाहरण code:

  fn write(x: &mut i32) {*x = 10}
  
  fn main() {
    let x = &mut 0;
    let y = x as *mut i32;
    //write(x); 
    *x = 10; 
    unsafe {*y = 15 };
  }
  

  • Stacked Borrows, miri का runtime model है
    miri में ऊपर वाला code चलाने पर *x = 10; पर error रिपोर्ट होती है, लेकिन write(x); में error नहीं आती
    rustc के type-system नज़रिए से, क्योंकि y एक *mut है, इसलिए दोनों versions को reject करने की कोई वजह नहीं है

• paper में unsafe code की समस्या के रूप में यह उदाहरण दिया गया है:

  fn main() {
    let mut x = 42;
    let ptr = &mut x as *mut i32;
    let val = unsafe { write_both(&mut *ptr, &mut *ptr) };
    println!("{val}");
  }
  

  संदेह है कि क्या यह वास्तव में संभव है
  एक ही variable पर pointers के जरिए कई mutable references का इस्तेमाल करना स्पष्ट रूप से UB है, इसलिए लगता है शायद मैं कुछ गलत समझ रहा हूँ

  • इस research का मुख्य बिंदु UB (undefined behavior) की सीमा को ठीक-ठीक define करना है
    ऊपर वाला code Rust compiler स्वीकार कर सकता है, लेकिन फिर भी यह नियमों का उल्लंघन करता है
    कौन से नियम?

• borrow checker से pass होने वाला code वैध है

• unsafe के जरिए अवैध/UB चीज़ें भी व्यक्त की जा सकती हैं

• borrow checker की सीमा से बाहर, लेकिन फिर भी वैध, ऐसे नियमों का एक बड़ा सेट मौजूद है
  इस research का उद्देश्य उसी सीमा को सख्ती से निर्धारित करना है
  Stacked Borrows paper सरल है, लेकिन वास्तविक unsafe code पर उसकी सीमाएँ थीं, जबकि Tree Borrows सुरक्षित दायरे को और व्यापक रूप से मान्यता देता है

  • यह तो स्पष्ट है कि "कई mutable reference pointers एक साथ मौजूद नहीं हो सकते", लेकिन ठीक किस नियम का उल्लंघन हो रहा है, यह साफ तौर पर कहीं लिखा नहीं है
    Tree Borrows उसी परिभाषा को प्रस्तावित करता है
    जब कहा जाता है कि "code ऐसा कर सकता है", तो मतलब यह है कि वास्तव में ऐसा code लिखा और चलाया जा सकता है, लेकिन Tree Borrows जैसी परिभाषा के बिना यह स्थापित करना कठिन है कि यह गलत क्यों है
    लगता है कि आप खुद भी Tree Borrows जैसे स्पष्ट नियमों की ज़रूरत को पहले ही स्वीकार कर रहे हैं

  • unsafe code इस तरह वास्तव में संभव है, और यही बात उसे UB बनाती है
    उदाहरण: playground link

  • अगर संबंधित संदर्भ चाहिए, तो paper के ठीक अगले paragraph की शुरुआत मंशा को अच्छी तरह स्पष्ट करती है

अगर Rust compiler developers aliasing optimizations चाहते हैं, तो उन्हें ऊपर जैसे counterexample code को बाहर करने का कोई तरीका चाहिए

• हाँ, यही तो असली बात है
  कई mutable references को न मानने वाले नियम का पालन करना कठिन है, और unsafe यह दर्शाता है कि वह Rust के lifetime system द्वारा guaranteed चीज़ों से कहीं अधिक की अनुमति दे सकता है

• लेखकों में से एक Neven Villani, 2010 Fields medal विजेता Cédric Villani के बेटे हैं
  यह कहावत याद आती है कि सेब पेड़ से दूर नहीं गिरता

  • और यह चुटकी भी ली जा सकती है कि "qualities भी tree से borrow की गई हैं"

  • कभी मेरा office उनके पिता (Fields medal विजेता) के office के काफ़ी पास था
    यह उनकी राजनीति में आने से पहले की बात है

• यह model सचमुच शानदार है
  मैं इसे अपनी बनाई जा रही language में भी implement करने वाला हूँ

• यह deja vu नहीं हो सकता
  लगता है मैं इस post को हर 2–3 महीने में बार-बार देखता रहता हूँ

  • paper कई सालों तक तैयार किया गया था, और अब जाकर आधिकारिक रूप से प्रकाशित हुआ है