Tree Borrows: un modelo de reglas de aliasing para código unsafe de Rust
(plf.inf.ethz.ch)- Para que el compilador de Rust pueda aprovechar las garantías de aliasing de punteros en las optimizaciones, es necesario definir con claridad en qué casos el código unsafe viola las reglas
- El modelo existente, Stacked Borrows, estableció ese criterio, pero no logra aceptar suficientemente los patrones comunes del código unsafe real en Rust ni las funciones más recientes del borrow checker
- Tree Borrows cambia la estructura central de Stacked Borrows de una pila a un árbol, lo que permite representar más patrones válidos
- En una evaluación de 30,000 crates de Rust de uso más extendido, rechazó 54% menos casos de prueba que Stacked Borrows
- Con una demostración en Rocq, se confirmó que conserva la mayoría de las optimizaciones previas y además permite nuevas optimizaciones como read-read reorderings
Reglas de aliasing necesarias en unsafe Rust
- Rust ofrece fuertes garantías como seguridad de memoria y prevención de data races mediante un sistema de tipos basado en ownership
- Sin embargo, en el área de código unsafe la seguridad no está garantizada automáticamente, y se necesitan reglas aparte que el programador debe respetar
- El compilador busca reforzar las optimizaciones dentro de las funciones aprovechando las garantías del sistema de tipos, en especial la información relacionada con el aliasing de punteros
- Un código unsafe mal escrito puede romper estas optimizaciones, por lo que es importante tener un criterio claro para decidir qué código debe considerarse “badly behaved”
- El trabajo previo, Stacked Borrows, definió ese criterio, pero tiene limitaciones
- Rechaza varios patrones frecuentes en código unsafe real de Rust
- No refleja funciones avanzadas del borrow checker introducidas recientemente
Enfoque de Tree Borrows y resultados de la evaluación
- Tree Borrows se define reemplazando por un árbol la pila que era la estructura central de Stacked Borrows
- Este cambio estructural relaja las limitaciones del modelo anterior
- En una evaluación sobre 30,000 crates de Rust de uso más extendido, la cantidad de casos de prueba rechazados se redujo en 54% frente a Stacked Borrows
- También se verificaron propiedades relacionadas con optimización mediante una demostración en Rocq
- Conserva la mayoría de las optimizaciones que permitía Stacked Borrows
- También habilita una nueva optimización importante: read-read reorderings
- Tree Borrows recibió el PLDI'25 Distinguished Paper Award
- Material relacionado
1 comentarios
Opiniones en Hacker News
Como bonus, también hay una presentación reciente del grupo de Ralf Jung sobre un intento de especificar con precisión, en forma ejecutable, la semántica de ejecución de Rust en un dialecto de Rust: https://youtube.com/watch?v=yoeuW_dSe0o
Torvalds lleva mucho tiempo sosteniendo que las reglas estrictas de aliasing de C hacen más daño que bien, y suena convincente. Un ejemplo está aquí: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... Si te interesa este tema, también vale la pena leer todo el hilo
Por mi experiencia limitada, no parece que Rust sea fundamentalmente distinto. Al menos, aún menos cuando entra unsafe
Creo que son más útiles para el compilador y menos gravosas para el programador. Además, dentro del lenguaje sí hay una forma real de escaparse: usar punteros raw. Y también hay herramientas para revisar el código
Al final, como todo en el diseño de lenguajes, es un compromiso, y creo que Rust quizá haya encontrado un nuevo sweet spot para este tipo de optimizaciones. El tiempo dirá si es así
En C existe ese artefacto nuclear llamado
restrict, que por experiencia en clang y gcc solo parecía tener algún efecto cuando se aplicaba a argumentos de funciones. El análisis de aliasing basado en tipos suele ser difícil de usar, y no se pueden crear infinitas copias del tipoint64_t, ni querrías hacerlo. También es molesto que te obligue a usarmemcpypara reinterpretar como otro tipoEn cambio, las referencias de Rust están delimitadas con precisión por lifetime, alcance y mutabilidad, y no les importa demasiado el tipo “físico” en sí. Por eso también es posible reinterpretar la misma memoria alternando entre
&mut i32/&i32y&mut i64/&i64. Mientras una abstracción unsafe no entregue referencias&mutque se solapen simultáneamente, o divida una sola&muten varias&mutque no se solapen, se pueden leer y escribir medios valores o varios valores con lecturas y escrituras normales de Rust seguroEl análisis de aliasing es muy importante para obtener buen rendimiento hoy en día. Pero también hay que recordar que las mayores ganancias vienen de las heurísticas más simples. Por ejemplo, dos cargas que usan el mismo valor SSA como puntero necesariamente se aliasan entre sí
Desde el punto de vista de LLVM, BasicAA cumple ese papel. Es un conjunto de heurísticas simples, cercano a “si se puede rastrear el punto de asignación del objeto, se resuelve la consulta de aliasing de forma concluyente; si no, no se sabe”
La verdadera pregunta es el valor del análisis de aliasing más allá de las comprobaciones básicas y obvias. Cuando una consulta de aliasing deja de resolverse de forma trivial, lo que se puede hacer con ese resultado suele reducirse mucho y casi se limita a encontrar riesgos de movimiento de código. El beneficio es mucho menor
Uno de los experimentos que me gustaría hacer es medir la mejora total de velocidad que daría, en teoría, un análisis de aliasing perfecto. Mi conjetura es que incluso en código no HPC como el kernel de Linux sería de alrededor de 20%
[1] Esto no incluye optimizaciones heroicas como transformaciones de disposición de datos que no se intentarían sin un análisis de aliasing de alta calidad. Como ya sabemos que en la práctica ese análisis no existe, tampoco se intentarían esas optimizaciones, y no creo que valga la pena incluirlas en la mejora de velocidad esperada
El aliasing de C se basa únicamente en tipos, por eso su otro nombre es análisis de aliasing basado en tipos o TBAA
Encontré una afirmación de que
noaliascontribuye con una mejora de rendimiento de alrededor del 5% en tiempo de ejecución, aunque está claro que el material es bastante antiguohttps://github.com/rust-lang/rust/issues/54878#issuecomment-...
https://news.ycombinator.com/item?id=22281205
https://news.ycombinator.com/item?id=17715399
La explicación parecía decir que, si se crea un
*mut i32a partir de&muty se usa*x = 10en lugar dewrite(x), entonces no se usa el préstamo implícito en dos fases, así que el compilador debería rechazarlo; pero en la práctica pasa*x = 10;reporta un error y la versión conwrite(x);noEl error tiene la forma “Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location”
rustc en sí no tiene motivo para rechazar ninguno de los dos.
yes*mut, y desde la perspectiva del sistema de tipos en tiempo de compilación no tiene relación de préstamo ni de vida útil conx, que es&mutEl verificador de préstamos actual usa un análisis más restrictivo y no detecta este conflicto específico entre punteros sin procesar y referencias mutables
En mi experiencia práctica [1] [2], también permitía código razonable que era ilegal bajo Stacked Borrows
[1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... columna Miri
[2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
Pasó de un verificador de préstamos basado en alcances al verificador de préstamos con vidas útiles no léxicas, y la siguiente implementación experimental, Polonius, también está disponible como opción. Pero cuando una implementación nueva está lista para producción, la anterior se descarta, porque no hay razón para elegirla
La verificación de préstamos es rápida, y la nueva implementación acepta estrictamente más programas correctos
Además, existen los tipos
RcyRefCell, que permiten obtener más flexibilidad a cambio de pagar el costo de verificaciones en tiempo de ejecuciónTodos tienen costos y capacidades distintos en implementación, rendimiento y experiencia de desarrollo
Y lo que la mayoría de los lenguajes fuera de Rust realmente busca es la productividad de la gestión automática de recursos. Es decir, usar gestión automática de recursos, sea cual sea el método, y combinar uno de estos sistemas de tipos solo en las rutas críticas para el rendimiento
En este contexto, “Rust” puede verse simplemente como “las invariantes que la gente normalmente quiere” y “un conjunto de optimizaciones que asume esas invariantes normales, ni más ni menos”
La mayor parte del tiempo de compilación se va en la resolución de traits, la monomorfización, los pases de optimización de LLVM y el enlazado
Quizá sea una pregunta tonta, pero me pregunto si no se podrían ejecutar varias implementaciones en hilos paralelos y hacer que gane la primera que dé un resultado positivo
Usar punteros para hacer que existan simultáneamente varias referencias mutables a la misma variable es comportamiento indefinido. Si no estoy malinterpretando la intención del artículo, eso parece
El código anterior es aceptado por el compilador de Rust, pero rompe reglas. La cuestión es qué reglas rompe
En esencia, lo que acepta el verificador de préstamos es legal; unsafe puede expresar cosas ilegales o comportamiento indefinido; y existe un conjunto de reglas más amplio que lo que el verificador de préstamos puede comprobar, pero que aun así sigue siendo legal y de comportamiento definido
El objetivo de esta investigación es especificar con precisión ese conjunto de reglas. A grandes rasgos, se parece a “los punteros escribibles no deben tener alias”, pero detalles como punteros internos, invalidación de iteradores, o si el problema es crear un puntero malo o usarlo, son muy difíciles
El artículo anterior de Stacked Borrows era más simple, pero también más restrictivo, por lo que el código unsafe del mundo real a menudo no pasaba sus reglas. Tree Borrows es más amplio y permite más código, a la vez que sigue siendo demostrablemente seguro
Tree Borrows propone justamente una definición de ese tipo
Aquí, “el código puede hacer esto” significa “se puede escribir, compilar y ejecutar este código, y sin algo como Tree Borrows no hay base para afirmar que este código tiene un problema”
Ya se está aceptando que hay que decir que este código es comportamiento indefinido, es decir, que hace falta algo como Tree Borrows. Esta parte del artículo argumenta por qué se necesita algo así
https://play.rust-lang.org/?version=stable&mode=debug&editio...
Dice que, como está claro que los desarrolladores del compilador de Rust quieren admitir optimizaciones basadas en aliasing, hace falta una forma de “excluir” contraejemplos como el de arriba de la consideración
unsafeestá pensado para los casos en que resulta difícil demostrar la validez del código mediante el análisis de tiempos de vida de Rust, pero puede abusarse de él para hacer mucho más que eso.