Tree Borrows: Ein Modell der Aliasing-Regeln für unsafe Code in Rust

 (plf.inf.ethz.ch)
1 Punkte von GN⁺ 2025-07-10 | 1 Kommentare | Auf WhatsApp teilen
  • Damit der Rust-Compiler Garantien für Pointer-Aliasing für Optimierungen nutzen kann, muss klar definiert sein, an welchen Stellen unsafe Code die Regeln verletzt
  • Das bisherige Modell Stacked Borrows lieferte diesen Maßstab, konnte aber gängige Muster in realem unsafe Rust-Code und neuere Funktionen des Borrow Checkers nicht ausreichend abbilden
  • Tree Borrows ersetzt die Kernstruktur von Stacked Borrows von einem Stack durch einen Baum und kann dadurch mehr gültige Muster ausdrücken
  • Bei der Auswertung von 30.000 der am häufigsten verwendeten Rust-Crates gab es im Vergleich zu Stacked Borrows 54 % weniger abgelehnte Testfälle
  • Mit einem Rocq-Beweis wurde gezeigt, dass die meisten bisherigen Optimierungen erhalten bleiben und auch neue Optimierungen wie Read-Read-Reorderings möglich sind

Notwendige Aliasing-Regeln in unsafe Rust

  • Rust bietet mit seinem eigentumsbasierten Typsystem starke Garantien wie Speichersicherheit und die Vermeidung von Data Races
  • Im Bereich von unsafe Code wird Sicherheit jedoch nicht automatisch garantiert; es braucht zusätzliche Regeln, die Programmierer einhalten müssen
  • Der Compiler möchte die Garantien des Typsystems, insbesondere Informationen über Pointer-Aliasing, nutzen, um Optimierungen innerhalb von Funktionen zu verbessern
  • Fehlerhaft geschriebener unsafe Code kann solche Optimierungen zunichtemachen, daher ist ein klarer Maßstab wichtig, welcher Code als „badly behaved“ gilt
  • Die bestehende Arbeit Stacked Borrows definierte diesen Maßstab, hat aber Grenzen
    • Sie lehnt mehrere Muster ab, die in echtem unsafe Rust-Code häufig vorkommen
    • Sie bildet neu eingeführte fortgeschrittene Funktionen des Rust-Borrow-Checkers nicht ab

Ansatz von Tree Borrows und Ergebnisse der Evaluation

  • Tree Borrows wird definiert, indem der zentrale Stack in Stacked Borrows durch einen Baum ersetzt wird
  • Durch diese Strukturänderung werden die Einschränkungen des bisherigen Modells gelockert
    • Bei der Auswertung von 30.000 der am häufigsten verwendeten Rust-Crates sank die Zahl der im Vergleich zu Stacked Borrows abgelehnten Testfälle um 54 %
  • Ein Rocq-Beweis bestätigt außerdem Eigenschaften im Zusammenhang mit Optimierungen
    • Die meisten Optimierungen, die Stacked Borrows erlaubte, bleiben erhalten
    • Auch die wichtige neue Optimierung Read-Read-Reorderings wird möglich
  • Tree Borrows erhielt den PLDI'25 Distinguished Paper Award
  • Weiterführende Materialien

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-07-10
Kommentare auf Hacker News
  • Ein aktueller Beitrag von Ralf Jung liefert zusätzlichen Kontext: https://www.ralfj.de/blog/2025/07/07/tree-borrows-paper.html
    Als Bonus gibt es auch einen aktuellen Vortrag von Ralf Jungs Gruppe, die versucht, die Ausführungssemantik von Rust in einem Rust-Dialekt in ausführbarer Form präzise zu spezifizieren: https://youtube.com/watch?v=yoeuW_dSe0o
  • Ich frage mich, wie zutreffend die Aussage wirklich ist, dass „der Compiler Garantien des Typsystems zum Pointer-Aliasing nutzen will, um starke intraprozedurale Optimierungen zu ermöglichen“
    Torvalds argumentiert schon lange, dass die strikten Aliasing-Regeln von C mehr schaden als nutzen, und das klingt überzeugend. Ein Beispiel ist hier: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... Wer sich für das Thema interessiert, sollte auch den ganzen Thread lesen
    Ob Rust grundlegend anders ist, wirkt nach meiner begrenzten Erfahrung nicht so. Zumindest gilt das umso mehr, wenn unsafe ins Spiel kommt
    • Ich stimme zu, dass die strikten Aliasing-Regeln von C furchtbar sind, aber die für Rust vorgeschlagenen Regeln sind sehr anders
      Ich halte sie für den Compiler nützlicher und für Programmierer weniger belastend. Außerdem gibt es in der Sprache tatsächlich einen Ausweg: Man kann rohe Pointer verwenden. Und es gibt auch Werkzeuge, um Code zu prüfen
      Am Ende ist es, wie alles im Sprachdesign, ein Kompromiss, und vielleicht hat Rust hier einen neuen Sweet Spot für solche Optimierungen gefunden. Ob das stimmt, wird die Zeit zeigen
    • Rusts Aliasing-Regeln unterscheiden sich deutlich von denen in C
      C hat mit restrict eine Art nukleare Option, die meiner Erfahrung nach bei clang und gcc nur dann einen Effekt hatte, wenn sie an Funktionsargumenten stand. Typbasierte Alias-Analyse ist im Allgemeinen schwer zu nutzen, und man kann auch nicht unendlich viele Kopien des Typs int64_t erzeugen, noch würde man das wollen. Außerdem ist es lästig, dass memcpy erzwungen wird, wenn man etwas als anderen Typ neu interpretieren will
      Rust-Referenzen dagegen sind durch Lebensdauer, Gültigkeitsbereich und Veränderbarkeit fein abgegrenzt und kümmern sich wenig um den „physischen“ Typ selbst. Deshalb kann man denselben Speicher auch zwischen &mut i32/&i32 und &mut i64/&i64 neu interpretieren und hin- und herwechseln. Solange eine unsafe-Abstraktion nicht gleichzeitig überlappende &mut-Referenzen ausgibt oder eine einzelne &mut in mehrere nicht überlappende &mut aufteilt, kann man mit gewöhnlichen sicheren Rust-Lese- und Schreibzugriffen halbe Werte oder mehrere Werte lesen und schreiben
    • Was Linus über Compiler sagt, sollte man mit einer gewissen Vorsicht genießen. Er schreibt Betriebssystem-Kernel, keine Compiler, und das sind ziemlich unterschiedliche Bereiche
      Alias-Analyse ist heute sehr wichtig, um gute Performance zu erreichen. Man sollte aber auch bedenken, dass die größten Gewinne aus den einfachsten Heuristiken stammen. Zum Beispiel: Zwei Loads, die denselben SSA-Wert als Pointer verwenden, müssen zwangsläufig aliasen
      Aus LLVM-Sicht übernimmt BasicAA diese Rolle. Es ist eine Sammlung einfacher Heuristiken, die ungefähr sagt: „Wenn wir den Allokationspunkt eines Objekts verfolgen können, können wir Alias-Anfragen eindeutig beantworten, andernfalls wissen wir es nicht“
      Die eigentliche Frage ist der Wert von Alias-Analysen, die über grundlegende und offensichtliche Prüfungen hinausgehen. Sobald Alias-Anfragen nicht mehr trivial aufzulösen sind, schrumpft in der Regel auch das, was man mit dem Ergebnis tun kann, erheblich, und es läuft fast nur noch darauf hinaus, Risiken bei Codebewegungen zu finden. Der Nutzen ist deutlich kleiner
      Ein Experiment, das ich gern sehen würde, wäre, den gesamten Speedup zu messen, den eine theoretisch perfekte Alias-Analyse bringen würde. Meine Vermutung ist, dass es selbst bei Nicht-HPC-Code wie dem Linux-Kernel etwa 20% wären
      [1] Das schließt keine heroischen Optimierungen wie Datenlayout-Transformationen ein, die man ohne hochwertige Alias-Analyse gar nicht erst versuchen würde. Da wir bereits wissen, dass eine solche Alias-Analyse praktisch nicht existiert, würde man solche Optimierungen auch nicht versuchen, und ich halte es nicht für sinnvoll, sie in den erwarteten Speedup einzurechnen
    • Cs striktes Aliasing und Rusts Aliasing behandeln zwar beide Aliasing, sind aber verschiedene Dinge. Rust hat sich ziemlich ausdrücklich nicht für den C-Ansatz entschieden
      Cs Aliasing basiert ausschließlich auf Typen, daher auch der andere Name typbasierte Alias-Analyse oder TBAA
    • Ich würde gern eine gründlichere Analyse sehen, aber als einfache Faustprobe könnte man im Compiler alle Stellen entfernen, an denen Alias-Informationen an LLVM weitergereicht werden, und sich ansehen, was mit der Performance passiert
      Ich habe eine Behauptung gefunden, dass noalias zur Laufzeit ungefähr 5% Performancegewinn beiträgt, aber die Quelle ist eindeutig sehr alt
      https://github.com/rust-lang/rust/issues/54878#issuecomment-...
  • Zu den erwähnten Stacked Borrows gab es auch 2020 und 2018 Threads
    https://news.ycombinator.com/item?id=22281205
    https://news.ycombinator.com/item?id=17715399
  • Man kann sich auch den PLDI-Vortrag ansehen: https://www.youtube.com/watch?v=CJi_Fcs4bak
  • Ich habe die Behauptung aus Beispiel 4 des Papers, dass bestimmter Rust-Code abgelehnt werde, selbst ausprobiert, aber mit der stabilen Compiler-Version scheint das nicht der Fall zu sein
    Es klang so, als müsste der Compiler es ablehnen, wenn man aus &mut ein *mut i32 erstellt und statt write(x) *x = 10 verwendet, weil dann kein implizites zweiphasiges Borrowing genutzt wird; tatsächlich geht es aber durch
    • Stacked Borrows ist das Laufzeitmodell von Miri. Wenn man es in Miri ausführt, meldet die Version mit *x = 10; einen Fehler, die Version mit write(x); dagegen nicht
      Der Fehler hat die Form „Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location“

rustc selbst hat keinen Grund, eines von beidem abzulehnen. y ist ein *mut, und aus Sicht des Typsystems zur Compile-Zeit hat es keine Borrow- oder Lebensdauerbeziehung zu x, dem &mut.

  • Das Paper beschreibt nicht die aktuelle Implementierung des Borrow-Checkers, sondern das Verhalten im vorgeschlagenen Tree-Borrows-Modell.
    Der aktuelle Borrow-Checker verwendet eine restriktivere Analyse und erkennt genau diesen Konflikt zwischen Raw Pointer und veränderlicher Referenz nicht.
  • Hervorragende Arbeit. Ich erinnere mich, dass ich vor ein paar Jahren auf Nevins Website die Tree-Borrows-Spezifikation gelesen habe und sehr beeindruckt war, wie elegant sie ein ziemlich kniffliges Problem löst.
    Nach praktischer Erfahrung ließ sie auch in [1] [2] sinnvollen Code zu, der unter Stacked Borrows illegal wäre.
    [1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... Miri-Spalte
    [2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
  • Die Miri-Implementierung für Interessierte ist hier: https://github.com/rust-lang/miri/tree/master/src/borrow_tra...
  • Ich frage mich, ob Rust oder künftige Programmiersprachen sich dahin entwickeln werden, mehrere Borrow-Checker-Implementierungen mit unterschiedlichen Eigenschaften wie Compile-Geschwindigkeit, Laufzeitgeschwindigkeit und algorithmischer Flexibilität zuzulassen und Projekte auswählen zu lassen.
    • Rust unterstützt bereits den Wechsel der Borrow-Checker-Implementierung.
      Es ist vom bereichsbasierten Borrow-Checker zum Borrow-Checker mit nicht-lexikalischen Lebensdauern gewechselt, und als nächste experimentelle Implementierung gibt es Polonius ebenfalls als Option. Sobald eine neue Implementierung produktionsreif ist, wird die alte allerdings verworfen, weil es keinen Grund gibt, sie auszuwählen.
      Borrow-Checking ist schnell, und neue Implementierungen akzeptieren strikt mehr korrekte Programme.
      Außerdem gibt es die Typen Rc und RefCell, mit denen man zum Preis von Runtime-Checks mehr Flexibilität bekommt.
    • Es gibt bereits mehrere Ansätze: affine Typen, wie Rust sie verwendet, lineare Typen, Effekte, abhängige Typen und formale Beweise.
      Sie unterscheiden sich alle bei Kosten und Fähigkeiten hinsichtlich Implementierung, Performance und Developer Experience.
      Und was die meisten außerhalb von Rust tatsächlich anstreben, ist die Produktivität automatischer Ressourcenverwaltung: Man nutzt automatische Ressourcenverwaltung, wie auch immer sie umgesetzt ist, und kombiniert nur auf performancekritischen Pfaden eines der obigen Typsysteme damit.
    • Was man eigentlich will, ist vermutlich die zugrunde liegende Separation Logic: Funktionsvorbedingungen präzise spezifizieren, Zwischenbedingungen innerhalb der Funktion beweisen, und der Optimierer nimmt diese „Lemmata“ entgegen und optimiert frei bis an die Grenzen der angegebenen Invarianten.
      In diesem Kontext kann man „Rust“ als nichts weiter ansehen als „die Invarianten, die Menschen normalerweise wollen“ plus „eine Sammlung von Optimierungen, die genau diese üblichen Invarianten annehmen, nicht mehr und nicht weniger“.
    • Rusts Borrow-Checker hat relativ geringe Compile-Time-Kosten und wirkt sich überhaupt nicht auf die Codegenerierung aus.
      Der Großteil der Compile-Zeit geht für Trait-Resolution, Monomorphisierung, LLVM-Optimierungspässe und Linking drauf.
    • Nach meinem Verständnis hat der Borrow-Checker nur False Negatives und keine False Positives, oder?
      Vielleicht ist das eine dumme Frage, aber könnte man nicht mehrere Implementierungen in parallelen Threads laufen lassen und diejenige gewinnen lassen, die zuerst ein positives Ergebnis liefert?
  • Im Paper steht, dass unsafe Code mehrere veränderliche Referenzen auf dieselbe Variable über Pointer gleichzeitig existieren lassen kann. Ist das nicht undefiniertes Verhalten?
    Mehrere veränderliche Referenzen auf dieselbe Variable gleichzeitig per Pointer existieren zu lassen, ist undefiniertes Verhalten. So sieht es zumindest aus, falls ich die Absicht des Papers nicht missverstanden habe.
    • Der Kern dieser Arbeit ist, die exakte Grenze von undefiniertem Verhalten festzulegen.
      Der obige Code wird vom Rust-Compiler akzeptiert, verletzt aber Regeln. Die Frage ist, welche Regeln er verletzt.
      Im Wesentlichen gilt: Was der Borrow-Checker akzeptiert, ist legal; unsafe kann auch Illegales oder undefiniertes Verhalten ausdrücken; und es gibt eine Regelmenge, die weiter ist als das, was der Borrow-Checker prüfen kann, aber dennoch legal und wohldefiniert bleibt.
      Ziel dieser Forschung ist es, diese Regelmenge präzise zu spezifizieren. In groben Zügen läuft es auf „schreibbare Pointer dürfen keine Aliases haben“ hinaus, aber Details wie innere Pointer, Iterator-Invalidierung oder ob schon das Erzeugen eines schlechten Pointers problematisch ist oder erst dessen Verwendung, sind sehr schwierig.
      Das frühere Stacked-Borrows-Paper war einfacher, aber restriktiver, sodass realer unsafe Code häufig nicht durch die Regeln kam. Tree Borrows ist weiter gefasst und erlaubt mehr Code, bleibt aber beweisbar sicher.
    • Stimmt, aber die Frage ist, welche Regel genau verletzt wird. Was ist die genaue Definition, die uns sagt, dass es undefiniertes Verhalten ist?
      Tree Borrows schlägt genau eine solche Definition vor.
      Wenn hier gesagt wird, „Code kann so etwas tun“, bedeutet das: „Man kann diesen Code schreiben, kompilieren und ausführen, und ohne etwas wie Tree Borrows gibt es keine Grundlage, um zu behaupten, dass mit diesem Code etwas nicht stimmt.“
      Damit ist bereits akzeptiert, dass man sagen muss, dass solcher Code undefiniertes Verhalten ist – also dass etwas wie Tree Borrows nötig ist. Dieser Teil des Papers argumentiert, warum so etwas gebraucht wird.
    • Du hast hier wohl „kann“ missverstanden. In unsafe Code kann man das tatsächlich tun. Und ja, genau das ist undefiniertes Verhalten.
      https://play.rust-lang.org/?version=stable&mode=debug&editio...
    • Am Anfang des folgenden Absatzes wird die Absicht am klarsten.
      Dort heißt es, dass Rust-Compiler-Entwickler offensichtlich Alias-Optimierungen unterstützen wollen und daher eine Möglichkeit brauchen, Gegenbeispiele wie das obige aus dem Betrachtungsbereich „auszuschließen“.
    • Genau das ist meiner Meinung nach der Punkt. Es ist viel zu leicht, Beschränkungen wie die, die mehrere veränderliche Referenzen nicht erlauben, zu verletzen.

unsafe ist für Fälle gedacht, in denen es schwierig ist, die Gültigkeit von Code mit Rusts Lebensdaueranalyse nachzuweisen, kann aber missbraucht werden, um weit mehr zu tun.

  • Ich habe gerade erfahren, dass einer der Autoren, Neven Villani, der Sohn von Cédric Villani ist, dem Fields-Medal-Gewinner von 2010. Da passt das Sprichwort, dass der Apfel nicht weit vom Stamm fällt, perfekt.