Tree Borrows

 (plf.inf.ethz.ch)
1 puntos por GN⁺ 2025-07-10 | 1 comentarios | Compartir por WhatsApp
  • Tree Borrows, un nuevo modelo de memoria para Rust, fue propuesto para superar los límites de optimización del código unsafe en el lenguaje
  • El enfoque previo de Stacked Borrows no permitía varios patrones usados con frecuencia en código Rust del mundo real, y Tree Borrows resuelve esto con una estructura en árbol, ofreciendo reglas más realistas y flexibles
  • Tree Borrows supera en un 54% más casos de prueba de código real que Stacked Borrows
  • Mantiene la mayor parte de la seguridad de memoria y la capacidad de optimización clave de Rust, especialmente en casos como read-read reordering, al mismo tiempo que incorpora funciones avanzadas del borrow checker más reciente de Rust
  • Introduce un modelo de máquina de estados basado en árboles, marcando un hito importante para la investigación sobre optimización de Rust y verificación de seguridad

El sistema de ownership de Rust y los límites del código unsafe

  • Rust ofrece garantías sólidas como seguridad de memoria y prevención de data races mediante un sistema de tipos basado en ownership
  • Sin embargo, Rust incluye una unsafe escape hatch, y en ese caso la validación de seguridad deja de ser responsabilidad del compilador y pasa al desarrollador
  • El compilador quiere aprovechar reglas de aliasing de punteros para aplicar optimizaciones agresivas, pero el código unsafe incorrecto puede inutilizar esas optimizaciones

Stacked Borrows y sus limitaciones

  • Hasta ahora, el modelo Stacked Borrows definía qué se considera “comportamiento incorrecto” en código unsafe y servía como criterio para optimización
  • Pero este enfoque no permite varios patrones unsafe comunes en código Rust real, ni refleja funciones recientes del borrow checker de Rust

La aparición de Tree Borrows

  • Tree Borrows es un nuevo modelo que rastrea permisos de memoria con una estructura en árbol en lugar de una estructura apilada
  • Gracias a esto, permite de forma segura más patrones de código Rust usados en la práctica, aumentando mucho la flexibilidad y aplicabilidad real de las reglas de préstamo
  • En una evaluación de 30,000 crates populares de Rust, superó en un 54% más casos de prueba que Stacked Borrows

Características y ventajas de Tree Borrows

  • Conserva la mayoría de las optimizaciones principales de Stacked Borrows (por ejemplo, read-read reorderings)
  • Además, puede reflejar funciones avanzadas del borrow checker más reciente de Rust (por ejemplo, patrones de préstamo no estructurados y manipulación compleja de punteros)
  • Introduce un modelo de máquina de estados basado en árboles para equilibrar seguridad y capacidad de optimización

Conclusión e importancia

  • Tree Borrows propone un nuevo referente para el manejo de código unsafe y la investigación en optimización del compilador de Rust
  • Se considera un modelo de memoria realista y robusto que abarca tanto el código Rust de producción como las políticas del borrow checker más reciente
  • El artículo relacionado, el artefacto y el código fuente fueron publicados y se espera que tengan un gran impacto en la comunidad de investigación de compiladores y verificación de Rust

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-07-10
Comentarios en Hacker News

  • La publicación reciente del blog de Ralf Jung da más contexto enlace
    Bonus: también recomiendo una charla reciente de un grupo de investigación que intenta especificar claramente la semántica de ejecución de Rust en un dialecto de Rust YouTube

  • Se dice que, desde la perspectiva del compilador, se pueden hacer optimizaciones potentes aprovechando las fuertes garantías del sistema de tipos sobre el aliasing de punteros, pero me pregunto qué tan efectivo es eso en la práctica
    Linus Torvalds lleva mucho tiempo diciendo que las reglas de strict aliasing de C sirven de poco y más bien causan problemas
    También es interesante su texto de ejemplo
    Me pregunto si Rust es esencialmente distinto de C en este aspecto; por experiencia personal, especialmente cuando entra unsafe, no se siente tan diferente

    • Creo que las reglas de strict aliasing de C realmente son bastante malas
      Las reglas propuestas en Rust son muy distintas, más útiles para el compilador y menos pesadas para el programador
      Hay un opt-out dentro del lenguaje usando raw pointers, y también existen herramientas para revisar el código
      Al final, como todo diseño de lenguaje, es un compromiso
      Parece que Rust encontró un nuevo equilibrio en esta área de optimización, y el tiempo dirá qué tan acertada fue esa decisión

    • Las reglas de aliasing de Rust son muy diferentes de las de C
      En C, la palabra clave restrict casi solo tiene sentido en argumentos de función, y el aliasing basado en tipos (type-based aliasing) en la práctica casi no se usa o es incómodo de usar
      En Rust, se pueden expresar con precisión los lifetimes y la mutabilidad, y se puede manipular memoria de forma segura de muchas maneras sin depender del tipo en sí
      Es importante que no existan referencias &mut superpuestas, y que sí se pueda dividir en varias &mut que no se solapan

    • Me gustaría ver un análisis más amplio de cuánto impacta esto realmente en el rendimiento
      Se podría saber enseguida si se quitara del compilador toda la parte que transmite información de aliasing a LLVM y luego se comparara el rendimiento
      También hay quien afirma que la anotación noalias mejora el rendimiento alrededor de un 5% en tiempo de ejecución; hay un comentario al respecto (aunque los datos ya son algo antiguos)

    • Conviene tomar con cautela lo que dice Linus sobre compiladores
      Los kernels de SO y los compiladores son áreas completamente distintas
      Hoy en día, el análisis de aliasing sí es una pieza clave para mejorar el rendimiento
      Los mayores beneficios salen de heurísticas simples, y las consultas complejas de aliasing por sí mismas suelen tener menos utilidad
      Me gustaría experimentar cuánto mejoraría el rendimiento un análisis de aliasing teóricamente perfecto, pero incluso en código general sospecho que el límite rondaría el 20%
      Claro, hay optimizaciones muy avanzadas (por ejemplo, transformaciones del layout de datos) que ni siquiera se intentarían sin análisis de aliasing

    • El strict aliasing de C y el aliasing de Rust son conceptos distintos
      C se basa en el análisis por tipos (TBAA), y Rust decidió explícitamente no adoptar eso

  • Hubo hilos anteriores sobre Stacked Borrows en 2020 y 2018
    Hilo de 2020
    Hilo de 2018

  • Leí la especificación de Tree Borrows en el sitio web de Nevin hace unos años, y me impresionó porque resolvía problemas complejos de forma elegante
    Por experiencia práctica, Tree Borrows permite código razonable que no era posible con Stacked Borrows
    También vale la pena ver este código de ejemplo de la biblioteca estándar de Rust

  • Me pregunto si Rust o un PL de próxima generación podrían evolucionar para permitir elegir entre varias implementaciones de borrow checker con distintas características y objetivos, como velocidad de compilación, velocidad de ejecución o flexibilidad algorítmica

    • Rust ya soporta cambiar la implementación del borrow checker
      Pasó de uno basado en scopes a uno no léxico, y también existe una implementación experimental llamada Polonius como opción
      Cuando una implementación nueva está lista, no hay mucha razón para conservar la anterior
      Además, se puede usar de forma más flexible con Rc, RefCell y otros mecanismos que requieren verificaciones en tiempo de ejecución

    • Ya existen muchos enfoques, como affine type (usado por Rust), linear type, sistemas de efectos, dependent types y pruebas formales
      Cada enfoque tiene diferencias en costo de implementación, rendimiento y experiencia de desarrollo
      Más allá de Rust, también hay una tendencia a buscar combinaciones entre gestión automática de recursos y sistemas de tipos

    • Lo que realmente se necesita es separation logic, para poder especificar con precisión las precondiciones de una función y hasta demostrar condiciones intermedias
      El enfoque de Rust consiste en sistematizar invariantes comunes que la gente realmente quiere, para así garantizar optimizaciones potentes

    • Me pregunto si el resultado del borrow checker tiene solo falsos negativos y no falsos positivos
      Si fuera así, quizá sería posible ejecutar varias implementaciones en paralelo en distintos hilos y usar el resultado del ganador más rápido

    • Permitir varias implementaciones del borrow checker al mismo tiempo no sería deseable, porque facilitaría la fragmentación del ecosistema

  • Probé de verdad el código Rust del paper y confirmé que el compilador estable más reciente no lo rechaza
    Código de ejemplo:

    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 es el modelo de ejecución de miri
      Si ejecutas ese código en miri, reporta un error en *x = 10;, pero no ocurre error con write(x);
      Desde la perspectiva del sistema de tipos, rustc no tiene motivo para rechazar ninguna de las dos versiones porque y es *mut

  • El paper presenta el siguiente ejemplo como problema de código unsafe:

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

    Me pregunto si esto de verdad es posible
    Usar referencias mutables múltiples al mismo valor mediante punteros claramente es UB, así que siento que quizá estoy entendiendo algo mal

    • El punto central de esta investigación es definir con precisión los límites de UB (comportamiento indefinido)
      Ese código viola las reglas aunque el compilador de Rust lo acepte
      ¿Pero qué reglas exactamente?

  • El código que pasa el borrow checker es legal

  • unsafe también puede expresar cosas ilegales/UB

  • Existe un conjunto de reglas más amplio que el alcance del borrow checker, pero que sigue siendo legal
    El objetivo de esta investigación es especificar ese límite con rigor
    El paper de Stacked Borrows es más simple, pero tenía limitaciones con código unsafe real, mientras que Tree Borrows reconoce un rango más amplio de seguridad

    • Está claro que “no pueden existir varios punteros de referencias mutables al mismo tiempo”, pero no hay una parte donde se diga explícitamente qué regla exacta se viola
      Tree Borrows propone precisamente esa definición
      Cuando se dice “el código puede hacer este tipo de cosas”, significa que realmente se puede escribir y ejecutar ese código, pero sin una definición como Tree Borrows es difícil fundamentar por qué está mal
      Parece que tú mismo ya aceptas la necesidad de reglas claras como las de Tree Borrows

    • El código unsafe sí puede escribirse realmente de esa forma, y justo por eso es UB
      Ejemplo: enlace al playground

    • Si quieres más contexto, el inicio del siguiente párrafo en el paper deja muy clara la intención

Si los desarrolladores del compilador de Rust quieren optimizaciones de aliasing, necesitan una forma de excluir códigos de contraejemplo como el de arriba

  • Sí, ese es exactamente el punto
    Es difícil hacer cumplir la regla de no permitir múltiples referencias mutables, y unsafe puede permitir mucho más de lo que garantiza el sistema de lifetimes de Rust

  • Uno de los autores, Neven Villani, es hijo de Cédric Villani, ganador de la Medalla Fields 2010
    Hace pensar en la idea de que la manzana no cae lejos del árbol

    • Y también dan ganas de decir con humor que “las cualidades también fueron borroweadas del árbol”

    • Incluso llegué a tener la oficina cerca de la de su padre (ganador de la Medalla Fields)
      Fue antes de que entrara en política

  • Este modelo es realmente excelente
    Pienso implementarlo también en el lenguaje que estoy creando

  • No puede ser déjà vu
    Siento que veo este post una y otra vez cada 2 o 3 meses

    • El paper se preparó durante varios años y por fin fue publicado oficialmente ahora