Tree Borrows: um modelo de regras de aliasing para código unsafe em Rust

(plf.inf.ethz.ch)

1 pontos por GN⁺ 2025-07-10 | 1 comentários | Compartilhar no WhatsApp

Para que o compilador Rust use as garantias de aliasing de ponteiros em otimizações, é preciso definir com clareza onde o código unsafe viola as regras
O modelo existente Stacked Borrows apresentou esse critério, mas não consegue acomodar suficientemente padrões comuns em código unsafe Rust real nem recursos recentes do borrow checker
Tree Borrows altera a estrutura central do Stacked Borrows de uma pilha para uma árvore, permitindo representar mais padrões válidos
Em uma avaliação com 30.000 dos crates Rust mais usados, ele rejeitou 54% menos casos de teste do que o Stacked Borrows
Provas em Rocq confirmaram que é possível manter a maior parte das otimizações existentes e também habilitar novas otimizações, como reordenação read-read

Regras de aliasing necessárias em Rust unsafe

Rust oferece garantias fortes, como segurança de memória e prevenção de data races, por meio de um sistema de tipos baseado em ownership
Porém, em áreas de código unsafe, a segurança não é garantida automaticamente, e são necessárias regras separadas que o programador deve seguir
O compilador busca fortalecer otimizações dentro de funções usando as garantias do sistema de tipos, especialmente informações relacionadas a aliasing de ponteiros
Código unsafe escrito incorretamente pode quebrar essas otimizações, por isso é importante ter um critério claro para determinar que código deve ser considerado “badly behaved”
O trabalho anterior Stacked Borrows definiu esse critério, mas tem limitações
- Rejeita vários padrões comuns em código unsafe Rust real
- Não reflete recursos avançados introduzidos recentemente no borrow checker do Rust

Abordagem e resultados da avaliação do Tree Borrows

Tree Borrows é definido substituindo a pilha, estrutura central do Stacked Borrows, por uma árvore
Essa mudança estrutural relaxa as limitações do modelo anterior
- Em uma avaliação com 30.000 dos crates Rust mais usados, o número de casos de teste rejeitados caiu 54% em comparação com o Stacked Borrows
Provas em Rocq também confirmaram propriedades relacionadas a otimizações
- Mantém a maior parte das otimizações permitidas pelo Stacked Borrows
- Também permite uma nova otimização importante: read-read reorderings
Tree Borrows recebeu o PLDI'25 Distinguished Paper Award
Materiais relacionados

1 comentários

GN⁺ 2025-07-10

Opiniões no Hacker News

Um post recente de Ralf Jung acrescenta mais contexto: https://www.ralfj.de/blog/2025/07/07/tree-borrows-paper.html
Como bônus, há também uma apresentação recente do grupo de Ralf Jung sobre a tentativa de especificar com precisão, em forma executável, a semântica de execução do Rust em um dialeto de Rust: https://youtube.com/watch?v=yoeuW_dSe0o
Fico em dúvida sobre até que ponto é realmente verdade dizer que “o compilador quer aproveitar as garantias do sistema de tipos relacionadas a aliasing de ponteiros para abrir caminho a otimizações intrafuncionais poderosas”
Torvalds há muito argumenta que as regras estritas de aliasing do C causam mais prejuízo do que benefício, e isso soa convincente. Um exemplo está aqui: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... Se você se interessa pelo tema, vale ler a thread inteira
Pela minha experiência limitada, não parece que Rust seja fundamentalmente diferente. Pelo menos quando unsafe entra na história, ainda menos
- Concordo que as regras estritas de aliasing do C são péssimas, mas as regras propostas para Rust são muito diferentes
  Acho que elas são mais úteis para o compilador e menos pesadas para o programador. Além disso, há de fato uma forma de escapar dentro da linguagem: basta usar ponteiros brutos. E também há ferramentas para verificar o código
  No fim das contas, como tudo em design de linguagens, é uma questão de compromisso, e talvez o Rust tenha encontrado um novo sweet spot para esse tipo de otimização. O tempo dirá se isso está certo
- As regras de aliasing do Rust são bem diferentes das do C
  Em C existe aquele dispositivo meio “bomba nuclear” chamado restrict, que, pela minha experiência, só produziu algum efeito no clang e no gcc quando aplicado a argumentos de função. Análise de aliasing baseada em tipos é difícil de usar em geral, e não dá para criar infinitas cópias do tipo int64_t, nem você provavelmente gostaria disso. Também é irritante que seja obrigatório usar memcpy para reinterpretar como outro tipo
  Já as referências em Rust têm tempo de vida, escopo e mutabilidade delimitados de forma refinada, e não se importam tanto com o tipo “físico” em si. Por isso, é possível reinterpretar e alternar a mesma memória entre &mut i32/&i32 e &mut i64/&i64. Desde que uma abstração unsafe não forneça referências &mut simultaneamente sobrepostas, ou divida um único &mut em vários &mut que não se sobrepõem, é possível ler e escrever metade de um valor, ou vários valores, com leituras e escritas normais de Rust seguro
- É preciso filtrar um pouco o que Linus diz sobre compiladores. Ele escreve kernels de sistema operacional, não compiladores, e são áreas bem diferentes
  Análise de aliasing é muito importante para obter bom desempenho hoje em dia. Mas também é preciso lembrar que os maiores ganhos vêm das heurísticas mais simples. Por exemplo, duas cargas que usam o mesmo valor SSA como ponteiro necessariamente são aliases uma da outra
  Do ponto de vista do LLVM, é o BasicAA que cumpre esse papel. É um conjunto de heurísticas simples, próximo de “se for possível rastrear o ponto de alocação do objeto, resolva a consulta de aliasing de forma conclusiva; caso contrário, não sei”
  A verdadeira pergunta é qual é o valor da análise de aliasing além das verificações básicas e óbvias. Quando as consultas de aliasing deixam de ser resolvidas trivialmente, o que dá para fazer com o resultado também costuma diminuir bastante, ficando quase só em encontrar riscos de movimentação de código. O ganho disso é muito menor
  Um experimento que eu gostaria de fazer é medir o ganho total de velocidade que uma análise de aliasing teoricamente perfeita proporcionaria. Meu palpite é que, mesmo em código não HPC como o kernel Linux, seria algo em torno de 20%
  [1] Isso não inclui otimizações heroicas, como transformações de layout de dados, que não seriam tentadas sem uma análise de aliasing de alta qualidade. Como já sabemos que essa análise de aliasing não existe na prática, essas otimizações também não seriam tentadas, e acho que não vale incluí-las no ganho de velocidade esperado
- O aliasing estrito do C e o aliasing do Rust ambos tratam de aliasing, mas são coisas diferentes. Rust, de forma bastante explícita, não adotou o modelo do C
  O aliasing do C se baseia apenas em tipos, e por isso outro nome para ele é análise de aliasing baseada em tipos, ou TBAA
- Eu gostaria de ver uma análise mais completa, mas uma regra prática simples é remover do compilador todas as partes que passam informações de aliasing para o LLVM e ver o que acontece com o desempenho
  Encontrei uma afirmação de que noalias contribui com cerca de 5% de ganho de desempenho em tempo de execução, mas o material claramente é bem antigo
  https://github.com/rust-lang/rust/issues/54878#issuecomment-...
O Stacked Borrows mencionado também teve threads em 2020 e 2018
https://news.ycombinator.com/item?id=22281205
https://news.ycombinator.com/item?id=17715399
Também dá para ver a apresentação na PLDI: https://www.youtube.com/watch?v=CJi_Fcs4bak
Testei diretamente a afirmação, no exemplo 4 do artigo, de que determinado código Rust seria rejeitado, mas isso não parece acontecer na versão estável do compilador
Parecia que a explicação era que, ao criar um *mut i32 a partir de um &mut e usar *x = 10 em vez de write(x), não se usa o empréstimo implícito em duas fases, então o compilador deveria rejeitar; mas, na prática, ele aceita
- Stacked Borrows é o modelo de runtime do Miri. Ao rodar no Miri, a versão com *x = 10; reporta erro, enquanto a versão com write(x); não
  O erro é do tipo “Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location”

o próprio rustc não tem motivo para rejeitar nenhum dos dois. y é *mut e, do ponto de vista do sistema de tipos em tempo de compilação, não tem relação de empréstimo ou tempo de vida com x, que é &mut

O artigo descreve o comportamento no modelo Tree Borrows proposto, não na implementação atual do verificador de empréstimos
O verificador de empréstimos atual usa uma análise mais restritiva e não consegue detectar esse conflito específico entre um ponteiro bruto e uma referência mutável
Excelente trabalho. Lembro que, há alguns anos, li a especificação do Tree Borrows no site do Nevin e fiquei muito impressionado com a forma elegante como ela resolvia um problema bastante complicado
Na minha experiência prática [1] [2], ele também permitiu código razoável que seria ilegal no Stacked Borrows
[1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... coluna Miri
[2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
Para quem tiver interesse, a implementação no Miri está aqui: https://github.com/rust-lang/miri/tree/master/src/borrow_tra...
Fico curioso para saber se Rust, ou linguagens de programação futuras, vão evoluir para permitir várias implementações do verificador de empréstimos com características diferentes, como velocidade de compilação, velocidade de execução e flexibilidade algorítmica, deixando o projeto escolher
- Rust já dá suporte à troca de implementação do verificador de empréstimos
  Ele passou do verificador de empréstimos baseado em escopo para o verificador com tempos de vida não lexicais, e a próxima implementação experimental, Polonius, também existe como opção. Mas, quando uma nova implementação fica pronta para produção, a antiga é descartada. Não há motivo para escolher a antiga
  A verificação de empréstimos é rápida, e a nova implementação aceita estritamente mais programas corretos
  Além disso, existem os tipos Rc e RefCell, que permitem obter mais flexibilidade pagando o custo de verificações em tempo de execução
- Já existem várias abordagens. São métodos como os tipos afins usados por Rust, tipos lineares, efeitos, tipos dependentes e provas formais
  Todos têm custos e capacidades diferentes em implementação, desempenho e experiência do desenvolvedor
  E o que a maior parte do mundo fora de Rust realmente busca é a produtividade do gerenciamento automático de recursos. Usa-se gerenciamento automático de recursos, seja qual for o método, e combina-se um desses sistemas de tipos apenas nos caminhos em que desempenho é importante
- O que você provavelmente quer de fato é a lógica de separação subjacente. Uma estrutura em que se especificam com precisão as pré-condições das funções, provam-se condições intermediárias dentro das funções, e o otimizador recebe esses “lemas” e otimiza à vontade até o limite permitido pelos invariantes especificados
  Nesse contexto, “Rust” pode ser visto apenas como “os invariantes que as pessoas normalmente querem” e “um conjunto de otimizações que assume esses invariantes comuns, nem mais nem menos”
- O verificador de empréstimos de Rust tem um custo de tempo de compilação bem pequeno e não afeta em nada a geração de código
  A maior parte do tempo de compilação é gasta com resolução de traits, monomorfização, passes de otimização do LLVM e linking
- Pelo que entendo, o verificador de empréstimos só tem falsos negativos, não falsos positivos, certo?
  Talvez seja uma pergunta idiota, mas fico me perguntando se não daria para rodar várias implementações em threads paralelas e deixar vencer a que der primeiro um resultado positivo
O artigo diz que código unsafe pode fazer várias referências mutáveis à mesma variável coexistirem como ponteiros, mas isso não é comportamento indefinido?
Usar ponteiros para fazer várias referências mutáveis à mesma variável existirem ao mesmo tempo é comportamento indefinido. A menos que eu tenha entendido errado a intenção do artigo, é isso que parece
- O ponto central deste trabalho é fixar os limites exatos do comportamento indefinido
  O código acima é aceito pelo compilador Rust, mas viola regras. A questão é: quais regras ele viola?
  Essencialmente, aquilo que o verificador de empréstimos aceita é legal; unsafe pode expressar coisas ilegais ou comportamento indefinido; e existe um conjunto de regras mais amplo do que o que o verificador de empréstimos consegue checar, mas que ainda é legal e tem comportamento definido
  O objetivo desta pesquisa é especificar esse conjunto de regras com precisão. Em linhas gerais, ele se aproxima de “ponteiros graváveis não podem ter aliases”, mas detalhes como ponteiros internos, invalidação de iteradores e se o problema é criar um ponteiro ruim ou usá-lo são muito difíceis
  O artigo anterior sobre Stacked Borrows era mais simples, mas também mais restritivo, então código unsafe real frequentemente não passava nas regras. Tree Borrows é mais amplo e permite mais código, ao mesmo tempo que continua sendo comprovadamente seguro
- Correto, mas a questão é exatamente quais regras são violadas. Qual é a definição precisa que nos diz que isso é comportamento indefinido?
  Tree Borrows propõe justamente esse tipo de definição
  Aqui, “o código pode fazer isso” significa “é possível escrever, compilar e executar esse código, e, sem algo como Tree Borrows, não há base para afirmar que há um problema nele”
  Você já aceitou que devemos dizer que esse código é comportamento indefinido, ou seja, que algo como Tree Borrows é necessário. Esta parte do artigo é a argumentação de por que algo assim é necessário
- Parece que você entendeu mal a expressão “pode fazer”. Em código unsafe, é realmente possível fazer isso. E, corretamente, isso é comportamento indefinido
  https://play.rust-lang.org/?version=stable&mode=debug&editio...
- A intenção fica mais clara no início do parágrafo seguinte
  Ele diz que, como os desenvolvedores do compilador Rust claramente querem dar suporte a otimizações baseadas em aliasing, é necessário ter uma forma de “excluir” contraexemplos como o de cima da consideração
- Acho que esse é exatamente o ponto. É fácil demais violar restrições como a de não permitir várias referências mutáveis

unsafe é destinado a casos em que é difícil provar a validade do código pela análise de lifetimes do Rust, mas pode ser abusado para fazer muito mais do que isso

Acabei de descobrir que um dos autores, Neven Villani, é filho de Cédric Villani, vencedor da Medalha Fields de 2010. A expressão de que a maçã não cai longe da árvore se aplica perfeitamente aqui