Futurelock: o sutil risco de deadlock em Rust assíncrono

• Futurelock é um fenômeno de deadlock que ocorre quando uma tarefa gerencia vários Futures ao mesmo tempo, e um deles precisa de um recurso de outro Future, mas não é mais polado
• Pode acontecer facilmente quando, na sintaxe tokio::select!, um Future referenciado (&mut future) é usado junto com um ramo que inclui await
• Esse problema surge de uma falha em separar as responsabilidades entre tarefa e Future; como a mesma tarefa espera pelos dois Futures, mas só pola um deles, ela entra em estado de paralisação
• Formas semelhantes também podem ocorrer com FuturesUnordered, bounded channel, Stream etc.
• Para um design assíncrono seguro, o ponto principal é separar o Future em uma tarefa distinta com tokio::spawn ou evitar o uso de await dentro do select

---

Conceito e exemplo de Futurelock

• Futurelock ocorre quando o recurso mantido pelo Future A é necessário para o Future B, mas a tarefa responsável pelos dois Futures deixa de polar A
• No código de exemplo, dentro de tokio::select!, espera-se ao mesmo tempo por &mut future1 e sleep; se sleep terminar primeiro, future1 permanece aguardando o lock
• Depois, future3 solicita o mesmo lock, mas o lock foi atribuído a future1, e como future1 não está sendo polado, o programa para permanentemente

Interação entre tokio::select! e Mutex

• tokio::sync::Mutex é um lock justo (fair), concedendo o lock na ordem de espera
• O lock é entregue a future1, mas a tarefa já está polando apenas future3, então future1 não é executado
• O Mutex apenas desperta a próxima tarefa em espera e não consegue saber qual Future está realmente sendo polado

Causas gerais de Futurelock

• Uma estrutura de dependência cíclica em que a tarefa T espera pelo Future F1, F1 depende de F2, e F2 por sua vez precisa que T o pole novamente
• Ocorre principalmente nas situações a seguir
  • usar &mut future em tokio::select! e depois executar await em outro ramo
  • executar outro trabalho assíncrono após a conclusão de alguns Futures em FuturesOrdered ou FuturesUnordered
  • comportamento semelhante em Futures implementados manualmente

Casos em Streams e outras estruturas

• Em FuturesOrdered ou FuturesUnordered, pode ocorrer Futurelock ao retirar um Future e depois esperar por outro Future que use um recurso relacionado a ele
• join_all não sofre Futurelock porque continua polando todos os Futures

Casos reais e depuração

• No caso Omicron#9259, todos os Futures de acesso ao banco de dados entraram em Futurelock, fazendo com que requisições HTTP aguardassem indefinidamente
• O envio no canal mpsc estava bloqueado, mas o lado receptor parecia vazio, o que dificultou descobrir a causa
• Na depuração, ferramentas como tokio-console podem ajudar, mas na maioria dos casos rastrear a causa é extremamente difícil

Diretrizes para evitar Futurelock

• Quando uma tarefa pola vários Futures, tenha cuidado para não interromper a polagem de um Future já iniciado
• Sempre que possível, faça spawn do Future em uma nova tarefa para que ele execute de forma independente
  • Passar um JoinHandle para tokio::select! elimina o risco de Futurelock
• Pontos de atenção ao usar tokio::select!
  • não use &mut future e await ao mesmo tempo
  • se ambos estiverem presentes, o risco de Futurelock é alto
• Ao usar Stream, utilize JoinSet para executar cada Future em uma tarefa separada
• Aumentar a capacidade de um bounded channel não é uma solução fundamental
  • em vez disso, é possível evitar bloqueio usando try_send()

Padrões incorretos de evasão

• Aumentar indefinidamente a capacidade do canal é irrealista e causa efeitos colaterais, como latência e aumento de memória
• Tentar eliminar dependências entre Futures é frágil, pois novas dependências podem surgir durante a manutenção
• O único método realmente seguro é separar as tarefas com tokio::spawn

Melhorias futuras e considerações de segurança

• Foi sugerida a possibilidade de fornecer avisos por meio de lint do Clippy ao usar &mut future dentro de tokio::select! ou incluir await
• Futurelock pode ser explorado na forma de negação de serviço (DoS), mas como é essencialmente um comportamento anômalo, precisa ser prevenido

[GN⁺]

Comentários do Hacker News

• Ao passar pelo documento, pareceu um relatório bem transparente e minucioso
  Em especial, a seção de notas de rodapé foi interessante
  Achei marcante que muita gente não conhecia o problema de cancellation safety no Rust, e que há uma grande chance de esse tipo de problema estar espalhado pelo Omicron como um todo
  É irônico que Rust tenha sido escolhido para evitar os problemas de segurança de memória do C, mas agora surjam bugs de cancelamento difíceis de detectar em runtime
  Foi especialmente frustrante que o programador precise garantir manualmente propriedades dinâmicas que o compilador não consegue ajudar a verificar

  • Fiquei pensando se não seria necessário um nível mais alto de abstração para evitar esse tipo de problema
    Parece que ainda existe possibilidade de deadlock no modelo de concorrência do Rust
    A gestão de recursos no estilo RAII parece algo que deveria evitar esse tipo de problema, mas na prática não evita, e isso é confuso
    Fico curioso se isso é apenas uma coincidência de implementação ou uma limitação estrutural do modelo Rust/Tokio

• Isso parece uma variação sutil do deadlock descrito por withoutboats no post sobre FuturesUnordered
  Ao usar concorrência “intra-task”, é preciso tomar cuidado para que nenhum future entre em starvation
  Em geral, fazer spawn de tasks é mais seguro, e você pode tratar timeout com tokio::select!, desde que todos os futures pendentes sejam gerenciados dentro dele
  Eu realmente não recomendaria FuturesUnordered a menos que todos os casos de borda tenham sido testados

• Isso soa parecido com um problema de inversão de prioridade (priority inversion)
  Em sistemas operacionais, quando uma thread de baixa prioridade está segurando um lock e uma thread de alta prioridade fica esperando, a de baixa herda a prioridade para poder executar
  Fico curioso se algo parecido poderia ser aplicado no Tokio — por exemplo, se um future que não pode executar está segurando um Mutex, fazer poll dele de alguma outra forma
  Mas detectar o estado de “não pode executar” provavelmente teria um custo considerável

  • Essa abordagem talvez seja possível no nível de task no Tokio
    Mas não dá para aplicar isso a futures dentro da task
    O design básico do async em Rust é que “futures are inert” — um future é só uma struct, e o runtime não consegue ver seu interior
    O runtime só conhece a unidade da task, então não rastreia em absoluto o estado dos futures internos

  • O async do Rust usa um modelo de corrotina stackless, então não é seguro continuar arbitrariamente a execução de uma função async que já esteja em andamento
    No modelo stackless, o estado local fica armazenado numa pilha compartilhada, então só é seguro executar em ordem LIFO
    Por isso existe coloring, e não é possível fazer yield livremente como em corrotinas stackful

  • O código parece complexo demais
    Parece muito mais verboso do que seria em Erlang, Elixir, Go, ou até mesmo em C

  • Acho que isso é parecido com um deadlock básico de 2 locks
    A fila de espera do Mutex do Tokio e o agendamento de tasks acabam se entrelaçando e formando o impasse
    Se fosse um Mutex de SO, talvez fosse possível resolver acordando outra thread em espera, mas no async Rust isso parece difícil por causa da estrutura de máquina de estados dos futures
    Talvez desse para resolver fazendo poll sequencial dos futures na fila de espera, mas isso também poderia causar efeitos colaterais inesperados

• Já tive experiência lidando em conjunto com esse tipo de problema no ecossistema async do Rust
  Se select! não permitisse usar referências, esse problema poderia ser evitado, mas aí ficaria impossível usar o padrão de rodar select! repetidamente sem perder a posição na fila
  Junto com os problemas de cancelamento, isso pode virar uma armadilha inesperada até para especialistas em Rust
  Ainda assim, há muito menos surpresas do que em código baseado em callback

  • Sim, depois que nossa equipe analisou esse deadlock, também discutimos “como isso poderia ter sido evitado?”, mas chegamos à conclusão de que não foi culpa de ninguém
    Todos os primitivos do Tokio se comportaram como pretendido, e o código também foi escrito corretamente, mas a interação entre eles criou um deadlock inesperado
    Dá para impedir isso proibindo &mut future dentro de select!, mas aí muito código legítimo também deixaria de funcionar
    No fim, chegamos à conclusão amarga de que isso é algo com que “simplesmente é preciso tomar cuidado”
    A discussão continua neste comentário

  • Se select! retornasse os futures não selecionados sem dar drop neles, seria possível não perder o estado
    Mas isso seria incômodo e não resolveria o problema de forma fundamental
    A causa real, como explicado nesta thread, está na natureza incompleta do tratamento de cancelamento

• Achei interessante a pergunta do FAQ: “future1 não é cancelado?”
  O cancelamento tem duas etapas — interromper o poll e dar drop
  Neste exemplo, o drop é adiado, então o guard continua sendo mantido e isso gera o efeito colateral
  Fico pensando se seria possível garantir que essas duas ações sempre aconteçam ao mesmo tempo

• Tenho vontade de perguntar aos projetistas do Rust: por que escolheram o padrão async em vez do modelo de atores
  Quando uso Erlang, o modelo de atores parece muito mais limpo e seguro
  O JS foi meio que forçado a usar async pela estrutura da linguagem, mas Rust era uma linguagem nova, então fico curioso sobre por que seguiram esse caminho

  • Um grande motivo do design async do Rust foi o suporte a ambientes embarcados
    Como precisava funcionar sem malloc nem threads, o modelo de atores não era viável
    Dá para escrever código em estilo actor com Tokio, mas não é algo natural

  • Outro motivo é desempenho
    O modelo de atores tem alto custo de cópia de mensagens, e Rust, como linguagem de sistemas focada em performance, buscou zero-cost abstraction com máquinas de estado async
    Erlang e Go são linguagens que fizeram trade-offs diferentes

  • Como Rust não queria aceitar overhead em chamadas via C FFI, o modelo baseado em green threads foi descartado
    async/await é compilado em máquinas de estado, então o overhead é baixo
    O Go também teve problemas parecidos de starvation no começo, quando ainda não havia preempção, e depois o scheduler resolveu isso
    No fim, cada linguagem tinha objetivos e restrições diferentes

  • Eu também me surpreendi que a Oxide tenha adotado async
    Em embarcados ou servidores HTTP isso já é familiar, mas não imaginava que uma empresa de sistemas como a Oxide usaria isso tão a fundo

• A parte que não entendi ao ler o documento foi por que a thread principal, e não o future que segurava o lock, é que acorda
  Com um lock justo, seria de esperar que o future1 acordasse, então fico em dúvida sobre por que o runtime escolheu outra thread

• O texto foi realmente muito interessante
  O código de exemplo também estava claro, e encontrar um bug desses deve ser um pesadelo, mas quando ele finalmente aparece dá aquela sensação de encaixe das peças do quebra-cabeça

  • Na nossa empresa, todas as reuniões e sessões de depuração são gravadas, e exatamente esse “momento em que o quebra-cabeça se encaixa” ficou registrado em vídeo
    Foi marcante ver Eliza, Sean, John e Dave fazendo brainstorming juntos até chegar à causa
    Na segunda-feira vamos publicar um episódio de podcast sobre isso
    O vídeo relacionado pode ser visto no RFD 537 e neste link do evento

• Parece difícil de entender, e até propenso a bugs, que o Rust não faça todos os tasks ativos progredirem ao mesmo tempo
  Algo como structured concurrency, como no Trio do Python, parece mais intuitivo
  Fico curioso se Rust poderia adotar um modelo assim

  • Em Rust também é possível ter structured concurrency, mas só no nível de task
    Um future é apenas uma struct que precisa receber poll para avançar, então nem existe realmente o conceito de “future ativo”
    Fazer spawn de tudo como task parece resolver, mas isso também bloqueia alguns padrões úteis

  • A distinção entre task e future é importante
    Se um future não recebe poll, ele não faz nada
    Se definirmos cancelamento como “o estado em que ele não recebe poll até ser dropado”, então surgem casos como este, em que o future para segurando o lock
    Na filosofia RAII do Rust, esperamos cleanup no drop, mas se o poll para, nem isso acontece

• Ultimamente tenho pensado se o async do Rust não foi lançado cedo demais

  • Eu também acho que há muito a melhorar, mas vejo o design fundamental como uma base excelente
    Dá para refinar coisas como Pin ou parte da sintaxe, mas não é necessário mudar a estrutura central
    Ainda estamos mais na fase de “fundação da casa que ainda não foi terminada”, não foi exatamente um resultado de pressa
    Ainda assim, acho que faltam mais camadas inferiores, como corrotinas generalizadas