Tree Borrows

 (plf.inf.ethz.ch)
1 pontos por GN⁺ 2025-07-10 | 1 comentários | Compartilhar no WhatsApp
  • Tree Borrows, um novo modelo de memória para superar os limites de otimização de código unsafe na linguagem Rust, foi proposto
  • O Tree Borrows resolve com uma estrutura em árvore o problema de o método Stacked Borrows existente não permitir vários padrões frequentemente usados em código Rust de produção, oferecendo regras mais realistas e flexíveis
  • O Tree Borrows passa em 54% mais casos de teste de código do mundo real do que o Stacked Borrows
  • Ao mesmo tempo, preserva a maior parte dos principais aspectos de segurança de memória e potencial de otimização do Rust, especialmente read-read reordering, além de refletir recursos avançados do borrow checker mais recente do Rust
  • Com a introdução de um modelo de máquina de estados baseado em árvore, apresenta um marco importante para a pesquisa em otimização de Rust e verificação de segurança

O sistema de ownership do Rust e os limites do código unsafe

  • O Rust fornece garantias fortes, como segurança de memória e prevenção de data races, por meio de um sistema de tipos baseado em ownership
  • No entanto, o Rust possui uma unsafe escape hatch e, nesse caso, a responsabilidade pela verificação de segurança deixa de ser do compilador e passa para o desenvolvedor
  • O compilador quer aproveitar regras de alias de ponteiros para aplicar otimizações agressivas, mas código unsafe incorreto pode inviabilizar essas otimizações

Stacked Borrows e suas limitações

  • Até então, o modelo Stacked Borrows definia o “comportamento incorreto” em código unsafe e fornecia um critério para otimização
  • Porém, essa abordagem não permite vários padrões unsafe comuns em código Rust real e também não reflete recursos do borrow checker introduzidos recentemente no Rust

O surgimento do Tree Borrows

  • O Tree Borrows é um novo modelo que rastreia permissões de memória com uma estrutura em árvore em vez de uma estrutura empilhada
  • Com isso, permite com segurança mais padrões de código Rust usados na prática, aumentando bastante a flexibilidade das regras de borrow e sua aplicabilidade no mundo real
  • Em uma avaliação com 30.000 crates populares de Rust, passou em 54% mais casos de teste do que o Stacked Borrows

Características e vantagens do Tree Borrows

  • Mantém a maior parte das otimizações principais do Stacked Borrows existentes, como read-read reorderings
  • Além disso, consegue refletir recursos avançados do borrow checker mais recente do Rust, como padrões de borrow não estruturados e manipulações complexas de ponteiros
  • Introduz um modelo de máquina de estados baseado em árvore para equilibrar segurança e potencial de otimização

Conclusão e significado

  • O Tree Borrows apresenta um novo padrão de referência para o tratamento e a pesquisa de otimização de código unsafe no compilador Rust
  • É avaliado como um modelo de memória realista e robusto que abrange tanto código Rust de produção quanto as políticas mais recentes do borrow checker
  • O artigo, os artefatos e o código-fonte relacionados foram publicados e devem ter grande impacto na comunidade de pesquisa sobre compiladores Rust e verificação

Leituras relacionadas

1 comentários

 
GN⁺ 2025-07-10
Comentários do Hacker News

  • O post recente no blog de Ralf Jung dá mais contexto link
    Bônus: também recomendo a apresentação recente do grupo de pesquisa que está tentando especificar claramente a semântica de execução do Rust em um dialeto de Rust YouTube

  • Há a alegação de que, do ponto de vista do compilador, as garantias fortes do sistema de tipos sobre aliasing de ponteiros permitem otimizações poderosas, mas fico curioso sobre o quanto isso é realmente eficaz na prática
    Linus Torvalds há muito tempo argumenta que a regra de strict aliasing do C tem pouca utilidade e, em vez disso, causa problemas
    O texto dele com exemplo também é interessante
    Fico pensando se Rust é essencialmente muito diferente de C nesse aspecto, mas pela minha experiência pessoal, especialmente quando unsafe entra na jogada, não parece tão diferente assim

    • Acho que a regra de strict aliasing do C é realmente bem ruim
      As regras propostas no Rust são bem diferentes, mais úteis do ponto de vista do compilador e menos pesadas para o programador
      Há um opt-out dentro da própria linguagem com o uso de raw pointers, e também existem ferramentas para verificar o código
      No fim, como todo design de linguagem, é um compromisso
      Parece que Rust encontrou um novo equilíbrio nessa área de otimização, e o tempo dirá como essa escolha vai se sair

    • As regras de aliasing do Rust são bem diferentes das de C
      Em C, a palavra-chave restrict praticamente só faz sentido em argumentos de função, e aliasing baseado em tipo (type-based aliasing) na prática quase não é usado ou é incômodo de usar
      Em Rust, lifetimes, mutabilidade e outras formas refinadas de expressar acesso à memória permitem tratá-la com segurança de várias maneiras, independentemente do tipo em si
      O fato de só não poder haver referências &mut sobrepostas, enquanto ainda é possível dividir em várias &mut sem sobreposição, é um ponto importante

    • Gostaria de ver uma análise mais ampla sobre quanto isso realmente impacta o desempenho
      Daria para descobrir rapidamente removendo do compilador toda a parte que passa informações de aliasing ao LLVM e comparando a performance
      Também há a alegação de que a anotação noalias melhora em cerca de 5% o desempenho em runtime; há um comentário relacionado sobre isso (embora os dados já estejam meio antigos)

    • Convém filtrar o que o Linus diz sobre compiladores
      Kernel de sistema operacional e compiladores são áreas completamente diferentes
      Hoje em dia, análise de aliasing é realmente uma peça central para ganhos fortes de desempenho
      Os maiores efeitos vêm de heurísticas simples, e consultas complexas de aliasing por si só costumam ter utilidade limitada
      Eu adoraria testar experimentalmente quanto uma análise de aliasing teoricamente perfeita melhoraria a performance, mas imagino que o limite em código comum seja algo como 20%
      Claro, otimizações muito avançadas, como transformação de layout de dados, têm a limitação de nem sequer serem tentadas sem análise de aliasing

    • O strict aliasing de C e o aliasing de Rust são conceitos diferentes
      Em C, o centro da questão é a análise baseada em tipo (TBAA), e Rust deliberadamente não adotou isso

  • Já houve threads antigas sobre Stacked Borrows em 2020 e 2018
    Thread de 2020
    Thread de 2018

  • Li a especificação de Tree Borrows no site do Nevin há alguns anos, e fiquei impressionado com a forma elegante como ela resolve problemas complexos
    Na minha experiência, Tree Borrows permite código razoável que não seria possível com Stacked Borrows
    Também vale ver este exemplo de código da biblioteca padrão do Rust

  • Fico curioso se Rust ou linguagens PL de próxima geração podem evoluir para permitir escolher entre várias implementações de borrow checker, com características e objetivos diferentes, como velocidade de compilação, velocidade de runtime, flexibilidade algorítmica etc.

    • Rust já suporta trocar a implementação do borrow checker
      Ele saiu de um modelo baseado em escopo para o modelo non-lexical, e também existe a implementação experimental chamada Polonius como opção
      Quando uma nova implementação fica pronta, a antiga não é mantida por necessidade
      Também dá para usar formas mais flexíveis com checagens em runtime, como Rc e RefCell

    • Já existem várias abordagens, como affine types (usado por Rust), linear types, sistemas de efeitos, dependent types e prova formal
      Cada abordagem tem características diferentes em custo de implementação, desempenho, experiência de desenvolvimento etc.
      Mesmo fora do Rust, há uma tendência de buscar combinações entre gerenciamento automático de recursos e sistemas de tipos

    • O que realmente seria necessário é separation logic, capaz de especificar com precisão as preconditions de uma função e até provar condições intermediárias
      A abordagem do Rust é sistematizar invariantes comuns que as pessoas realmente querem e, com isso, garantir otimizações fortes

    • Fico me perguntando se o resultado do borrow checker só tem false negatives e não false positives
      Se for assim, talvez desse até para rodar várias implementações em paralelo em threads e usar o resultado da que terminar primeiro

    • Permitir várias implementações de borrow checker ao mesmo tempo provavelmente não seria desejável, porque o ecossistema tenderia a se fragmentar

  • Testei de fato o código Rust citado no artigo e confirmei que ele não é rejeitado pelo compilador estável mais recente
    Código de exemplo:

    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 é o modelo de runtime do miri
      Se você executar o código acima no miri, ele reporta erro em *x = 10;, mas não ocorre erro em write(x);
      rustc, do ponto de vista do sistema de tipos, não tem motivo para rejeitar nenhuma das duas versões, porque y é um *mut

  • O artigo usa o exemplo abaixo 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}");
}

    Fico em dúvida se isso é realmente possível
    Usar referências mutáveis múltiplas para a mesma variável via ponteiros é claramente UB, então imagino que devo estar entendendo algo errado

    • O ponto central dessa pesquisa é justamente definir com precisão os limites de UB (comportamento indefinido)
      O compilador Rust aceita esse código, mas ele ainda viola as regras
      Quais regras?

  • Código que passa no borrow checker é legal

  • unsafe também pode expressar coisas ilegais/UB

  • Existe um conjunto de regras mais amplo do que o escopo do borrow checker, mas que ainda assim continua sendo legal
    O objetivo dessa pesquisa é especificar esse limite com rigor
    O artigo sobre Stacked Borrows é mais simples, mas tinha limitações para código unsafe real; Tree Borrows reconhece uma faixa mais ampla de segurança

    • Está claro que “não podem existir vários ponteiros para referências mutáveis ao mesmo tempo”, mas não há uma regra explicitada com precisão dizendo exatamente qual regra isso viola
      Tree Borrows propõe justamente esse tipo de definição
      Quando se diz “o código pode fazer esse tipo de coisa”, isso significa que você de fato pode escrever e executar esse código, mas sem uma definição como Tree Borrows fica difícil fundamentar por que exatamente isso está errado
      Parece que você mesmo já aceita a necessidade de regras claras como as do Tree Borrows

    • Código unsafe assim é realmente possível na prática, e é justamente isso que o torna UB
      Exemplo: link do playground

    • Se quiser entender o contexto, o começo do parágrafo logo seguinte no artigo mostra bem a intenção

Se os desenvolvedores do compilador Rust quiserem otimizações de aliasing, precisam de uma forma de excluir contraexemplos de código como o acima

  • Sim, esse é exatamente o ponto
    É difícil impor na prática a regra que proíbe múltiplas referências mutáveis, e unsafe permite muito mais do que aquilo que o sistema de lifetimes do Rust garante

  • Um dos autores, Neven Villani, é filho de Cédric Villani, vencedor da Medalha Fields de 2010
    Vem à mente a metáfora de que a maçã não cai longe da árvore

    • E também dá vontade de brincar dizendo que “as qualidades também foram emprestadas da árvore”

    • Eu já tive o escritório perto do do pai dele (vencedor da Medalha Fields)
      Isso foi antes de ele entrar para a política

  • Esse modelo é realmente excelente
    Pretendo implementá-lo na linguagem que estou criando

  • Não pode ser déjà vu
    Tenho a sensação de ver este post de novo a cada 2 ou 3 meses

    • O artigo foi preparado ao longo de vários anos e finalmente foi publicado oficialmente agora